共查询到20条相似文献,搜索用时 625 毫秒
1.
2.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》1978,24(1):76-80
It is shown that soft decision maximum likelihood decoding of any(n,k) linear block code overGF(q) can be accomplished using the Viterbi algorithm applied to a trellis with no more thanq^{(n-k)} states. For cyclic codes, the trellis is periodic. When this technique is applied to the decoding of product codes, the number of states in the trellis can be much fewer thanq^{n-k} . For a binary(n,n - 1) single parity check code, the Viterbi algorithm is equivalent to the Wagner decoding algorithm. 相似文献
3.
Qi Wang Lei Wei 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2001,47(3):1062-1074
We construct parity-concatenated trellis codes in which a trellis code is used as the inner code and a simple parity-check code is used as the outer code. From the Tanner-Wiberg-Loeliger (1981, 1996) graph representation, several iterative decoding algorithms can be derived. However, since the graph of the parity-concatenated code contains many short cycles, the conventional min-sum and sum-product algorithms cannot achieve near-optimal decoding. After some simple modifications, we obtain near-optimal iterative decoders. The modifications include either (a) introducing a normalization operation in the min-sum and sum-product algorithms or (b) cutting the short cycles which arise in the iterative Viterbi algorithm (IVA). After modification, all three algorithms can achieve near-optimal performance, but the IVA has the least average complexity. We also show that asymptotically maximum-likelihood (ML) decoding and a posteriori probability (APP) decoding can be achieved using iterative decoders with only two iterations. Unfortunately, this asymptotic behavior is only exhibited when the bit-energy-to-noise ratio is above the cutoff rate. Simulation results show that with trellis shaping, iterative decoding can perform within 1.2 dB of the Shannon limit at a bit error rate (BER) of 4×10-5 for a block size of 20000 symbols. For a block size of 200 symbols, iterative decoding can perform within 2.1 dB of the Shannon limit 相似文献
4.
Amat A.Gi. Montorsi G. Benedetto S. 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2004,50(5):867-881
This correspondence deals with the design and decoding of high-rate convolutional codes. After proving that every (n,n-1) convolutional code can be reduced to a structure that concatenates a block encoder associated to the parallel edges with a convolutional encoder defining the trellis section, the results of an exhaustive search for the optimal (n,n-1) convolutional codes is presented through various tables of best high-rate codes. The search is also extended to find the "best" recursive systematic convolutional encoders to be used as component encoders of parallel concatenated "turbo" codes. A decoding algorithm working on the dual code is introduced (in both multiplicative and additive form), by showing that changing in a proper way the representation of the soft information passed between constituent decoders in the iterative decoding process, the soft-input soft-output (SISO) modules of the decoder based on the dual code become equal to those used for the original code. A new technique to terminate the code trellis that significantly reduces the rate loss induced by the addition of terminating bits is described. Finally, an inverse puncturing technique applied to the highest rate "mother" code to yield a sequence of almost optimal codes with decreasing rates is proposed. Simulation results applied to the case of parallel concatenated codes show the significant advantages of the newly found codes in terms of performance and decoding complexity. 相似文献
5.
6.
7.
SISO decoding for block codes can be carried out based on a trellis representation of the code. However, the complexity entailed
by such decoding is most often prohibitive and thus prevents practical implementation. This paper examines a new decoding
scheme based on the soft-output Viterbi algorithm (SOVA) applied to a sectionalized trellis for linear block codes. The computational
complexities of the new SOVA decoder and of the conventional SOVA decoder, based on a bit-level trellis, are theoretically
analyzed and derived for different linear block codes. These results are used to obtain optimum sectionalizations of a trellis
for SOVA. For comparisons, the optimum sectionalizations for Maximum A Posteriori (MAP) and Maximum Logarithm MAP (Max-Log-MAP)
algorithms, and their corresponding computational complexities are included. The results confirm that the new SOVA decoder
is the most computationally efficient SISO decoder, in comparisons to MAP and Max-Log-MAP algorithms. The simulation results
of the bit error rate (BER) performance, assuming binary phase -- shift keying (BPSK) and additive white Gaussian noise (AWGN)
channel, demonstrate that the performance of the new decoding scheme is not degraded. The BER performance of iterative SOVA
decoding of serially concatenated block codes shows no difference in the quality of the soft outputs of the new decoding scheme
and of the conventional SOVA. 相似文献
8.
We derive a linear correspondence between the variables of an encoder and those of a corresponding syndrome former. Using the derived correspondence, we show that the log-likelihood ratio of an information bit conditioned on a received sequence can be equally calculated using the syndrome trellis. It is shown that the proposed method also applies to recursive systematic convolutional codes which are typical constituent codes for turbo codes. Moreover, we show that soft-in syndrome decoding considering a priori probabilities of information bits is possible in the same way as for Viterbi decoding based on the code trellis. Hence, the proposed method can be applied to iterative decoding such as turbo decoding. We also show that the proposed method is effective for high-rate codes by making use of trellis modification. 相似文献
9.
This paper introduces an efficient iterative decoding method for high‐dimensional block turbo codes. To improve the decoding performance, we modified the soft decision Viterbi decoding algorithm, which is a trellis‐based method. The iteration number can be significantly reduced in the soft output decoding process by applying multiple usage of extrinsic reliability information from all available axes and appropriately normalizing them. Our simulation results reveal that the proposed decoding process needs only about 30% of the iterations required to obtain the same performance with the conventional method at a bit error rate range of 10?5 to 10?6. 相似文献
10.
We consider the iterative decoding of generalized low-density (GLD) parity-check codes where, rather than employ an optimal subcode decoder, a Chase (1972) algorithm decoder more commonly associated with "turbo product codes" is used. GLD codes are low-density graph codes in which the constraint nodes are other than single parity-checks. For extended Hamming-based GLD codes, we use bit error rates derived by simulation to demonstrate this new strategy to be successful at higher code rates. For long block lengths, good performance close to capacity is possible with decoding costs reduced further since the Chase decoder employed is an efficient implementation. 相似文献
11.
This paper introduces a new class of space-time codes that achieve coding gain without a trellis or any form of inter-block dependency. The construction of the new codes starts from an existing (parent) space-time block code (STBC). Then by increasing the constellation size followed by expurgation of the expanded codebook, a better code is obtained at the original transmission rate. This method can be applied to a wide variety of space-time block codes, including orthogonal codes and quasi-orthogonal codes. A multi-stage design algorithm is presented, and for orthogonal parent codes, an efficient decoding algorithm is developed, and its decoding complexity is analyzed. Despite altering the regular structure of the orthogonal code, the decoding complexity is only affected by a constant factor. 相似文献
12.
The general concept of closest coset decoding (CCD) is presented, and a soft-decoding technique for block codes that is based on partitioning a code into a subcode and its cosets is described. The computational complexity of the CCD algorithm is significantly less than that required if a maximum-likelihood detector (MLD) is used. A set-partitioning procedure and details of the CCD algorithm for soft decoding of |u |u +v | codes are presented. Upper bounds on the bit-error-rate (BER) performance of the proposed algorithm are combined, and numerical results and computer simulation tests for the BER performance of second-order Reed-Muller codes of length 16 and 32 are presented. The algorithm is a suboptimum decoding scheme and, in the range of signal-to-noise-power-density ratios of interest, its BER performance is only a few tenths of a dB inferior to the performance of the MLD for the codes examined 相似文献
13.
14.
In this paper we present a new method to simplify trellis‐based decoding of linear block codes. Our method is based on removing (pruning) some edges and states from the trellis representation of the code; the trellis is pruned through some hard‐decisions that are made on received bits whose likelihood exceeds a predefined threshold. We show in this paper how this simplification can be accounted for by a new generator matrix (and sometimes a coset leader) that totally parametrize the new trellis, or, equivalently, the set of allowed codewords after simplification. Extensive simulations show that significant computational savings can be achieved, at a very small loss in coding performance, as long as the operating point and threshold are carefully chosen. Moreover, the application of this technique to iterative decoding of product codes is outlined, and our results show that the simplifications do not hinder the convergence, again, as long as proper parameters are chosen. Copyright © 2007 John Wiley & Sons, Ltd. 相似文献
15.
《IEEE transactions on information theory / Professional Technical Group on Information Theory》2008,54(3):1036-1049
16.
Jun Lee Jaejin Lee 《Electronics letters》2001,37(17):1074-1075
A construction method of error correcting run-length limited (EC-RLL) codes using a high rate recursive systematic code (RSC) or turbo code for storage systems is proposed. The EC-RLL codes can be constructed by a concatenating conventional modulation code and RSC or turbo code with puncturing. The benefit of the scheme is the utilisation of soft decision and iterative detection algorithms for decoding 相似文献
17.
并行级联分组码比串行级联分组码具有更高的码率,基于LLR计算的Turbo迭代译码算法使其内外分量码均做到了软判决译码。通过引入校正因子a(m),将接收信息与子译码器的输出软信息进行线性叠加反馈能在省去繁琐的LLR计算的情况下实现并行级联分组码的Turbo迭代译码。仿真研究表明,若将译码器的输出进行简单的相关运算,可进一步改善译码器性能。 相似文献
18.
本文研究多带正交频分复用瑞利衰落信道中,空时网格编码发射天线间空间相关性的分集性能.空时网格编码将单个输出的编码符号转换成多个编码符号,并通过多个发射天线传输,在接收端,Viterbi优化软判决算法用于译码.我们分析了MB-OFDM系统在quasi-static和interleaved两种信道中相关空间衰落对误码率的影响.在空间相关性较小时,分集阶数能得到保持;而在空间相关性较大时,interleaved信道能保持分集阶数,quasi-static信道的分集阶数将减小.空时编码总体上对空间相关性表现出鲁棒性. 相似文献
19.
Iterative reliability-based decoding of linear block codes with adaptive belief propagation 总被引:1,自引:0,他引:1
In this letter, an iterative decoding algorithm for linear block codes combining reliability-based decoding with adaptive belief propagation decoding is proposed. At each iteration, the soft output values delivered by the adaptive belief propagation algorithm are used as reliability values to perform reduced order reliability-based decoding of the code considered. This approach allows to bridge the gap between the error performance achieved by the lower order reliability-based decoding algorithms which remain sub-optimum, and the maximum likelihood decoding, which is too complex to be implemented for most codes employed in practice. Simulations results for various linear block codes are given and elaborated. 相似文献
20.
Gil Wiechman Igal Sason 《IEEE transactions on information theory / Professional Technical Group on Information Theory》2007,53(2):550-579
The moderate complexity of low-density parity-check (LDPC) codes under iterative decoding is attributed to the sparseness of their parity-check matrices. It is therefore of interest to consider how sparse parity-check matrices of binary linear block codes can be a function of the gap between their achievable rates and the channel capacity. This issue was addressed by Sason and Urbanke, and it is revisited in this paper. The remarkable performance of LDPC codes under practical and suboptimal decoding algorithms motivates the assessment of the inherent loss in performance which is attributed to the structure of the code or ensemble under maximum-likelihood (ML) decoding, and the additional loss which is imposed by the suboptimality of the decoder. These issues are addressed by obtaining upper bounds on the achievable rates of binary linear block codes, and lower bounds on the asymptotic density of their parity-check matrices as a function of the gap between their achievable rates and the channel capacity; these bounds are valid under ML decoding, and hence, they are valid for any suboptimal decoding algorithm. The new bounds improve on previously reported results by Burshtein and by Sason and Urbanke, and they hold for the case where the transmission takes place over an arbitrary memoryless binary-input output-symmetric (MBIOS) channel. The significance of these information-theoretic bounds is in assessing the tradeoff between the asymptotic performance of LDPC codes and their decoding complexity (per iteration) under message-passing decoding. They are also helpful in studying the potential achievable rates of ensembles of LDPC codes under optimal decoding; by comparing these thresholds with those calculated by the density evolution technique, one obtains a measure for the asymptotic suboptimality of iterative decoding algorithms 相似文献