A bidirectional multiple stack algorithm

Bidirectional sequential decoding (BSD) substantially reduces the computational variability of conventional sequential decoding without compromising the error performance. However, BSD does not completely eliminate the erasure problem. We propose an erasure-free decoding algorithm which combines the idea of BSD in conjunction with that of the multiple stack algorithm (MSA). It is found that the new bidirectional multiple stack algorithm (BMSA) offers substantial advantages over the MSA in terms of computational effort, memory requirements, and error performance. The BMSA appears as an attractive alternative to the Viterbi algorithm (VA) where low error probabilities and high decoding speeds are required     

The Multiple Stack Algorithm Implemented on a Zilog Z-80 Microcomputer

A sequential algorithm for decoding convolutional codes, the multiple stack algorithm or MSA devised by Chevillat and Costello, has been implemented and tested on a Zilog Z-80 microcomputer system. The results of this implementation, when compared to those of a (2, 1)8 Viterbi algorithm implemented on the same microcomputer system, show that the MSA obtains significantly higher data throughput. The results of the MSA implementation of a (2, 1)15 code suggest that the MSA is a practical choice for codes having longer constraint lengths than are normally used with Viterbi decoding. The comparative results may serve as guidelines for future implementation of the MSA algorithm on faster, more capable microprocessors.     

A constraint-length based modified Viterbi algorithm with adaptiveeffort

A modified Viterbi (1971) algorithm for convolutional codes is described that provides for signal-to-noise ratio (SNR) adaptive computational effort. The algorithm has three levels of prioritized effort. Movement from one level to the next is controlled by parameters that can be selected according to desired output bit error rate performance. For 3-bit soft decision detected signals, a coding gain within 0.06 dB of Viterbi at a 3-dB SNR is achieved for the same constraint-length code with modest parameter values and computational effort. At values of SNR above 6 dB, the algorithm decodes with very low computational effort. Effort levels are controlled by spanning the decoding trellis in steps that are one constraint-length long     

软输出Viterbi译码的矩阵算法

本文在软输出Viterbi算法的基础上给出了一种新的软输出Viterbi算法,此算法使软输出Viterbi算法中求度量差和后验概率的复杂计算转化成一系列简单的适合于大规模集成电路实现的矩阵运算,从而使运算速度得到相应的提高,并使软输出Viterbi算法中复杂的数据存取和传输得到进一步简化。     

A new sequential decoding algorithm based on branch metric

A new sequential decoding algorithm with an adjustable threshold and a new method of moving through the decoding tree is proposed. Instead of the path metric of the conventional sequential decoding algorithms, the proposed algorithm uses a branch metric based on maximum-likelihood criterion. Two new parameters, the jumping-back distance and going-back distance, are also introduced. The performance of the algorithm for long constraint length convolutional codes is compared to those of the other sequential decoding algorithms and the Viterbi algorithm. The results show that the proposed algorithm is a good candidate for decoding of convolutional codes due to its fast decoding capability and good bit error rate (BER) performance. This work was supported in part by the Research Foundation at Karadeniz Technical University under Grant 2004.112.004.01 and 2005.112.009.2.     

A 40 Mb/s soft-output Viterbi decoder

Soft-output decoding has evolved as a key technology for new error correction approaches with unprecedented performance as well as for improvement of well established transmission techniques. In this paper, we present a high-speed VLSI implementation of the soft-output Viterbi algorithm, a low complexity soft-output algorithm, for a 16-state convolutional code. The 43 mm² standard cell chip achieves a simulated throughput of 40 Mb/s, while tested samples achieved a throughput of 50 Mb/s. The chip is roughly twice as big as a 16-state Viterbi decoder without soft outputs. It is thus shown with the design that transmission schemes using soft-output decoding can be considered practical even at very high throughput. Since such decoding systems are more complex to design than hard output systems, special emphasis is placed on the employed design methodology     

Decoding algorithms for noncoherent trellis coded modulation

Noncoherent decoding of trellis codes using multiple-symbol overlapped observations was shown previously to achieve close to the coherent performance. Optimal decoding by the Viterbi algorithm for L-symbol observations requires a number of states which grows exponentially with L. Two novel suboptimal algorithms are presented, for which the number of states is the same as the original code, yielding a complexity depending weakly on L. For practical values of L, both algorithms are substantially less complex than the optimal algorithm. The first algorithm, the basic decision feedback algorithm (BDFA), is a low complexity feedback decoding scheme, based on the Viterbi algorithm. This algorithm is shown to suffer from increased error probability and from error propagation. A slight modification to this algorithm can, in most cases, reduce these effects significantly. The second algorithm uses the BDFA as a basic building block. This algorithm is based on a novel concept called “estimated future” and its performance is very close to optimum for most practical eases with some additional complexity and memory requirements as compared to the first algorithm. Performance analysis and simulation results are also given     

State Transparent Convolutional Codes and Their Novel Maximum-Likelihood Decoding Algorithm

Almost all the probabilistic decoding algorithms known for convolutional codes, perform decoding without prior knowledge of the error locations. Here, we introduce a novel maximum-likelihood decoding algorithm for a new class of convolutional codes named as the state transparent convolutional (STC) codes, which due to their properties error detection and error locating is possible prior to error correction. Hence, their decoding algorithm, termed here as the STC decoder, allows an error correcting algorithm to be applied only to the erroneous portions of the received sequence referred to here as the error spans (ESPs). We further prove that the proposed decoder, which locates the ESPs and applies the Viterbi algorithm (VA) only to these portions, always yields a decoded path in trellis identical to the one generated by the Viterbi decoder (VD). Due to the fact that the STC decoder applies the VA only to the ESPs, hence percentage of the single-stage (per codeword) trellis decoding performed by the STC decoder is considerably less than the VD, which is applied to the entire received sequence and this reduction is overwhelming for the fading channels, where the erroneous codewords are mostly clustered. Furthermore, through applying the VA only to the ESPs, the resulting algorithm can be viewed as a new formulation of the VD for the STC codes that analogous to the block decoding algorithms provides a predecoding error detection and error locating capabilities, while performing less single-stage trellis decoding.     

A burst-error-correcting Viterbi algorithm

A dual-mode burst-error-correcting algorithm that combines maximum-likelihood decoding with a burst detection scheme is presented. The decoder nominally operates as a Viterbi decoder and switches to time diversity error recovery whenever an uncorrectable error pattern is identified. It is demonstrated that the new scheme outperforms interleaving strategies under the constraint of a fixed overall decoding delay. It also proves to be more powerful than known adaptive burst decoding schemes, such as the Gallager burst finding scheme. As the new method can be used with soft decision decoding, it is mainly intended for use on random-error channels affected by occasional severe bursts     

Performance evaluation of list sequence MAP decoding

List-sequence (LS) decoding has the potential to yield significant coding gain additional to that of conventional single-sequence decoding, and it can be implemented with full backward compatibility in systems where an error-detecting code is concatenated with an error-correcting code. LS maximum-likelihood (ML) decoding provides a list of estimated sequences in likelihood order. For convolutional codes, this list can be obtained with the serial list Viterbi algorithm (SLVA). Through modification of the metric increments of the SLVA, an LS maximum a posteriori (MAP) probability decoding algorithm is obtained that takes into account bitwise a priori probabilities and produces an ordered list of sequence MAP estimates. The performance of the resulting LS-MAP decoding algorithm is studied in this paper. Computer simulations and approximate analytical expressions, based on geometrical considerations of the decision domains of LS decoders, are presented. We focus on the frame-error performance of LS-MAP decoding, with genie-assisted error detection, on the additive white Gaussian noise channel. It is concluded that LS-MAP decoding exploits a priori information more efficiently, in order to achieve performance improvements, than does conventional single-sequence MAP decoding. Interestingly, LS-MAP decoding can provide significant improvements at low signal-to-noise ratios, compared with LS-ML decoding. In this environment, it is furthermore observed that feedback convolutional codes offer performance improvements over their feedforward counterparts. Since LS-MAP decoding can be implemented in existing systems at a modest complexity increase, it should have a wide area of applications, such as joint source-channel decoding and other kinds of iterative decoding.     

基于FPGA的高速Viterbi译码器设计与实现

Viterbi算法是卷积码最常用的译码算法,在卷积码约束长度较大,译码时延要求较高的场合,如何实现低硬件复杂度的Viterbi译码器成为新的课题。本文提出新颖的Viterbi路径权重算法、双蝶形译码单元结构、高效的状态度量存储器等技术,使Viterbi算法充分和FPGA灵活原片内存储和逻辑单元配置方法相结合,发挥出最佳效率。用本算法在32MHz时钟下实现的256状态的Viterbi译码器译码速率可达400Kbps以上,且仅占用很小的硬件资源,可以方便地和Furbo译码单元等集成在单片FPGA,形成单片信道译码单元。     

Soft-Decision Decoding of Punctured Convolutional Codes in Asynchronous-CDMA Communications Under Perfect Phase-Tracking Conditions

In this paper, the performance of punctured convolutional codes of short constraint lengths is discussed. The punctured codes are used to provide error protection to a particular user in an asynchronous CDMA system. A perfect phase reference is assumed to be available throughout this paper. A slow fading Rician channel is assumed. Maximum likelihood decoding through a Viterbi algorithm is used to decode the information symbols. Soft-decision decoding of punctured convolutional codes is considered in this paper. The upper bounds with Viterbi decoding are derived and plotted for the various punctured codes considered. The simulated results are found to agree very well with their upper and lower bounds.     

Pattern-Flipping Chase-Type Decoders with Error Pattern Extracting Viterbi Algorithm over Partial Response Channels

Towards the goal of achieving better error correction performance in data storage systems, iterative soft decoding of low density parity check (LDPC) codes and soft-decision decoding of Reed-Solomon (RS) codes have started receiving increasing research attention. However, even with increased computing power, complexities of soft-decision decoding algorithms are still too high for real products which require high throughput and small hardware area. Another problem is that the performance gains of those approaches are smaller for magnetic recording channels than they are for memoryless additive white Gaussian noise (AWGN) channels. We propose a new soft-decision decoding algorithm (based on the Chase algorithm), which takes advantage of pattern reliability instead of symbol reliability or bit reliability. We also present a modified Viterbi algorithm that provides probable error patterns with corresponding reliabilities. Simulation results of the proposed algorithms over the partial response (PR) channel show attractive performance gains. The proposed algorithm dramatically reduces the number of iterations compared to the conventional Chase2 algorithm over the PR channel.     

低复杂度的TBCC自适应循环VA译码算法

咬尾是一种将卷积码转换为块码的技术,它消除了归零状态所造成的码率损失,同时避免了截尾带来的性能降低,在短块编码中具有明显优势.针对咬尾卷积码(TBCC)现有译码算法复杂度过大和收敛性问题,提出一种低复杂度的TBCC自适应循环维特比(VA)译码算法.该算法根据信道变化自适应调整译码迭代次数,使咬尾路径收敛到最佳.通过仿真...     

Décodage pondéré optimal des codes linéaires en blocs

Maximum likelihood, word-by-word soft decoding of linear q-ary block codes is considered. All codewords are represented by a trellis which is precisely defined using multiindeterminate polynomial representation of the code. A metric is defined in terms of the a priori probabilities, associated with the paths at the trellis nodes, such that it is a nonincreasing function of the node level and that the word of largest metric at the terminal node level (terminal metric) is the best one according to the maximum likelihood criterion. Then decoding may use the Viterbi algorithm but, if the terminal metric of a particular path is known, only nodes of larger metric need be considered. Moreover, once a path better than the initial one is determined, its terminal metric sets a new threshold, below which they have no longer to be considered. For setting the initial threshold, the path determined by the hard decision on the first k symbols is used (k is the code dimension). The author shows that computing its terminal metric is related to syndrome computation. He discusses the strategy for exploring the other paths. Minimizing the decoding effort results if the symbols are reordered in terms of their reliability. Finally, means for further simplifying at the expense of optimality are briefly discussed.     

Real-Time Minimal-Bit-Error Probability Decoding of Convolutional Codes

A recursive procedure is derived for decoding of rateR = 1/nbinary convolutional codes which minimizes the probability of the individual decoding decisions for each information bit, subject to the constraint that the decoding delay be limited to Δ branches. This new decoding algorithm is similar to, but somewhat more complex than, the Viterbi decoding algorithm. A "real-time," i.e., fixed decoding delay, version of the Viterbi algorithm is also developed and used for comparison to the new algorithm on simulated channels. It is shown that the new algorithm offers advantages over Viterbi decoding in soft-decision applications, such as in the inner coding system for concatenated coding.     

Generalized threshold chase algorithms

 Three generalized threshold Chase algorithms called GTC Ⅰ,GTC Ⅱ and STC are proposed in this paper.They are the combination of the generalized minimum distance(GMD)decoding algorithm with the Chase algorithm.Although the decoding error probabilities of these algorithms are very close to that of the Chase algorithm,the decoding speeds are faster,especially at higher signal-to-noise ratio(SNR),hence they are of greater practical value.The results of computer simulations are given,showing the advantages of these algorithms.     

相关跳频序列的Viterbi译码算法及其纠错性能分析

该文分析了相关跳频通信系统中频率转移函数的纠错性能,将Viterbi算法应用于接收端跳变频点序列的译码,并结合相关跳频转移函数的特点对译码过程作出了改进.针对满足最大相关纠错性能的频率转移函数,详细分析了Viterbi算法的译码性能.仿真结果表明,通过相关纠错,对随机错误在低信噪比条件下可以获得5-8dB的增益.     

A coded ARQ scheme with the generalized Viterbi algorithm

A coded automatic repeat request (ARQ) scheme based on a generalized Viterbi decoding algorithm is proposed. The scheme utilizes the error propagation, which is commonly observed in reduced-complexity decoding, as a means of error detection. It is shown that a small undetectable error probability is obtained with a small retransmission probability for a discrete memoryless channel, contrary to the conventional convolutionally coded ARQ schemes with Viterbi decoding where a compromise between the retransmission probability and the undetectable error probability must be reached