SOVA算法对Viterbi算法的修正

在Viterbi算法中引入软值进行修正之后的算法称作SOVA算法(Soft Output Viterbi Algorithm)。SOVA算法在Viterbi算法的基础上,路径量度引入了比特先验信息,对每位译码比特以后验概率似然比的形式提供软输出,因而可提供更高的译码性能。特别,SOVA算法可用于级联码的迭代译码,采用Tuobo原理使不同分量码之间交换软信息,从而可显著提高这类码的纠错能力。     

一种简化的SOVA算法

软输出维特比(SOVA)算法广泛应用于硬盘读出、连接码和TURBO码.特别是TURBO码,目前已经被采用到第三代通信标准中.在这些应用中,特别是第三代通信终端应用中,虽然对性能有很高的要求,但对价格和功耗的要求更苛刻.降低算法复杂度是降低电路复杂度和功耗的主要手段.本文提出了一种简化的软输出维特比(SOVA)算法,显著减少了算法的复杂度,减少了L×(L-1)次比较运算.提出的算法对SOVA算法的纠错性能没有影响.新算法应用到TURBO码解码器中,纠错性能仅仅比传统的算法相差0.4 dB左右.     

High rate concatenated coding systems using bandwidth efficienttrellis inner codes

High-rate concatenated coding systems with bandwidth-efficient trellis inner codes and Reed-Solomon (RS) outer codes are investigated for application in high-speed satellite communication systems. Two concatenated coding schemes are proposed. In one the inner code is decoded with soft-decision Viterbi decoding, and the outer RS code performs error-correction-only decoding (decoding without side information). In the other the inner code is decoded with a modified Viterbi algorithm, which produces reliability information along with the decoded output. In this algorithm, path metrics are used to estimate the entire information sequence, whereas branch metrics are used to provide reliability information on the decoded sequence. This information is used to erase unreliable bits in the decoded output. An errors-and-erasures RS decoder is then used for the outer code. The two schemes have been proposed for high-speed data communication on NASA satellite channels. The rates considered are at least double those used in current NASA systems, and the results indicate that high system reliability can still be achieved     

List Viterbi algorithms for continuous transmission

The conventional list Viterbi algorithm (LVA) produces a list of the L best output sequences over a certain block length in decoding a terminated convolutional code. We show in this paper that the LVA with a sufficiently long list is an optimum maximum-likelihood decoder for the concatenated pair of a convolutional code and a cyclic redundancy check (CRC) block code with error detection. The CRC is used to select the output. New LVAs for continuous transmission are proposed and evaluated, where no termination bits are required for the convolutional code for every CRC block. We also present optimum and suboptimum LVAs for tailbiting convolutional codes. Convolutional codes with Viterbi decoding were proposed for so-called hybrid in band on channel (hybrid IBOC) systems for digital audio broadcasting compatible with the frequency modulation band. For high-quality audio signals, it is beneficial to use error concealment/error mitigation techniques to avoid the worst type of channel errors. This requires a reliable error flag mechanism (error detection feature) in the channel decoder. A CRC on a block of audio information bits provides this mechanism. We demonstrate how the LVA can significantly reduce the flag rate compared to the regular Viterbi algorithm (VA) for the same transmission parameters. At the expense of complexity, a receiver optional LVA can reduce the flag rate by more than an order of magnitude. The difference in audio quality is dramatic. The LVA is backward compatible with a VA     

CRC-assisted error correction in a convolutionally coded system

In communication systems employing a serially concatenated cyclic redundancy check (CRC) code along with a convolutional code (CC), erroneous packets after CC decoding are usually discarded. The list Viterbi algorithm (LVA) and the iterative Viterbi algorithm (IVA) are two existing approaches capable of recovering erroneously decoded packets. We here employ a soft decoding algorithm for CC decoding, and introduce several schemes to identify error patterns using the posterior information from the CC soft decoding module. The resultant iterative decoding-detecting (IDD) algorithm improves error performance by iteratively updating the extrinsic information based on the CRC parity check matrix. Assuming errors only happen in unreliable bits characterized by small absolute values of the log-likelihood ratio (LLR), we also develop a partial IDD (P-IDD) alternative which exhibits comparable performance to IDD by updating only a subset of unreliable bits. We further derive a soft-decision syndrome decoding (SDSD) algorithm, which identifies error patterns from a set of binary linear equations derived from CRC syndrome equations. Being noniterative, SDSD is able to estimate error patterns directly from the decoder output. The packet error rate (PER) performance of SDSD is analyzed following the union bound approach on pairwise errors. Simulations indicate that both IDD and IVA are better tailored for single parity check (PC) codes than for CRC codes. SDSD outperforms both IDD and LVA with weak CC and strong CRC. Applicable to AWGN and flat fading channels, our algorithms can also be extended to turbo coded systems.     

New Soft Output Viterbi Algorithm for Mobile Communication System

Soft output Viterbi algorithm(SOVA) is a turbo decoding algorithm that is suitable for hardware implementation. But its performance is not so good as maximum a posterior probability(MAP) algorithm. So it is very important to improve its performance. The non-correlation between minimum and maximum likelihood paths in SOVA is analyzed. The metric difference of both likelihood paths is used as iterative soft information, which is not the same as the traditional SOVA. The performance of the proposed SOVA is demonstrated by the simulations. For 1024-bit frame size and 9 iterations with signal to noise ratio from 1dB to 4dB, the experimental results show that the new SOVA algorithm obtains about more 0.4dB and 0.2dB coding gains more than the traditional SOVA and Bi-SOVA algorithms at bit error rate(BER) of 1×10~ -4 , while the latency is only half of the Bi-direction SOVA decoding.     

Truncated Turbo Decoding with Reduced Computational Complexity

The concept of concatenated codes and turbo decoding is well known and leads to a remarkably good performance in many applications. The resulting signal processing for this concept shows high complexity relative to conventional Viterbi decoding. This paper, therefore, considers an alternative concept of turbo decoding to reduce the computational complexity. In thiscase, those sections of the sequence to be decoded, where changes of bit decisions (compared to the previous iteration step) are very unlikely,are excluded from the soft-output viterbi algorithm (SOVA). This decoding is much easier to process and the loss of bit error rate (BER) performance isquite small or even negligible in comparison to conventional turbo decoding.     

多径信道下的软序列检测

本文提出一种基于软信息的序列检测算法,建立了状态转移条件下软信息的递推方程,并给出了计算不同时刻符号软信息的关系表达式.这种软序列检测算法与多径信道估计器配合,可以有效地解调发送符号序列.与传统的MLSE解调算法相比,软信息检测需要两个级连解调器,通过前后迭代来为每个发送符号计算边信息,因此误码率会得到很大的改善.此外,前端的信道估计可以由RLS算法及Kalman滤波器联合实时估计.仿真结果显示:软序列检测算法尽管在复杂度上增加了,但是误码性能远优于ML最佳准则下的解调算法.     

An integrated error correction and detection system for digitalaudio broadcasting

Hybrid in-band on-channel digital audio broadcasting systems deliver digital audio signals in such a way that is backward compatible with existing analog FM transmission. We present a channel error correction and detection system that is well-suited for use with audio source coders, such as the so-called perceptual audio coder (PAC), that have error concealment/mitigation capabilities. Such error mitigation is quite beneficial for high quality audio signals. The proposed system involves an outer cyclic redundancy check (CRC) code that is concatenated with an inner convolutional code. The outer CRC code is used for error detection, providing flags to trigger the error mitigation routines of the audio decoder. The inner convolutional code consists of so-called complementary punctured-pair convolutional codes, which are specifically tailored to combat the unique adjacent channel interference characteristics of the FM band. We introduce a novel decoding method based on the so-called list Viterbi algorithm (LVA). This LVA-based decoding method, which may be viewed as a type of joint or integrated error correction and detection, exploits the concatenated structure of the channel code to provide enhanced decoding performance relative to decoding methods based on the conventional Viterbi algorithm (VA). We also present results of informal listening tests and other simulations on the Gaussian channel. These results include the preferred length of the outer CRC code for 96-kb/s audio coding and demonstrate that LVA-based decoding can significantly reduce the error flag rate relative to conventional VA-based decoding, resulting in dramatically improved decoded audio quality. Finally, we propose a number of methods for screening undetected errors in the audio domain     

基于改进型SOVA的Turbo译码

第三代移动通信系统IMT-2000的高速率业务倾向于选择Turbo码,这就要求采用低时延、低复杂度的迭代译码技术,主要是软输出Viterbi算法(SOVA)和Max-Log-MAP算法.在先验等概和无限译码深度条件下,已证明略加修改的SOVA等效于Max-Log-MAP算法.由于在迭代译码中,先验概率须不断更新,本文证明了在存在先验概率的条件下改进型SOVA与Max-Log-MAP也是等效的,并讨论了有限译码深度限制下改进型SOVA与滑动窗口Max-Log-MAP算法的等效性.     

一种基于SOVA的改进的Turbo码译码方案

本文在研究Ｔｕｒｂｏ 码反向ＳＯＶＡ（Ｓｏｆｔ－Ｏｕｔｐｕｔ ＶｉｔｅｒｂｉＡｌｇｏｒｉｔｈｍ ）译码性能的基础上,提出了一种同时利用正向和反向ＳＯＶＡ译码软输出信息的基于ＳＯＶＡ 的改进译码结构及其相应的软输出修正公式。计算机模拟结果表明,所提出的改进方案与传统的ＳＯＶＡ算法相比,其译码性能有明显的改善,并略优于Ｍａｘ－Ｌｏｇ－ＭＡＰ的性能     

DSD (double soft decision) concatenated FEC scheme in mobilesatellite communication systems

In order to realize a higher-code-gain forward error correction scheme in mobile satellite communication systems, a novel concatenated coding scheme employing soft decision decoding for not only inner codes but also outer codes (double soft decision, or DSD, concatenated forward error correction scheme) is proposed. Soft-decision outer decoding can improve the bit error probability of inner decoded data. In this scheme, likelihood information from an inner Viterbi decoder is used in the decoding of outer codes. A technique using the path memory circuit status 1.0 ratio for likelihood information is proposed, and is shown to be the most reliable even though it requires the simplest hardware among the alternative methods. A computer simulation clarifies that the DSD scheme improves Pe performance to one-third of that of the conventional hard-decision outer decoding. Moreover, to reduce the interleaving delay time in fading channels or inner decoded data of concatenated codes, a parallel forward error correction scheme is proposed     

A simple remedy for the exaggerated extrinsic information produced by the SOVA algorithm

In this paper, we propose a novel and simple approach for dealing with the exaggerated extrinsic information produced by the soft-output Viterbi algorithm (SOVA). The proposed remedy is based on mathematical analysis and it involves using two attenuators, one applied to the immediate output of the SOVA and another applied to the extrinsic information before it is passed to the other decoder (assuming iterative decoding). The use of these attenuators aims at reducing the inherent strong correlation between the intrinsic information (input to the SOVA) and extrinsic information (output of the SOVA). We examine the modified SOVA (MSOVA) on additive white Gaussian noise (AWGN) and flat fading channels for parallel concatenated codes (PCCs) and serial concatenated codes (SCCs). We show that the MSOVA provides substantial performance improvements over both channels. For example, it provides improvements of about 0.8 to 1.0 dB at P/sub b/ = 10/sup -5/ in AWGN, and about 1.4 to 2.0 dB at P/sub b/ = 10/sup -5/ on fading channels. We also show that there are cases where the MSOVA is superior to the a posteriori probability (APP) algorithm. With this motivation, we extend the proposed modification to the APP algorithm with favorable results. We demonstrate that the modified APP (MAPP) provides performance improvements between 0.3 to 0.6 dB at P/sub b/ = 10/sup -5/ relative to the APP. We lastly mention that the proposed modifications, while they provide considerable performance improvements, keep the complexity of these decoders almost the same, which is remarkable.     

Complexity Reduction in SISO Decoding of Block Codes

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.     

Low complexity concatenated coding schemes for digital satellite communications

A study of reduced complexity concatenated coding schemes, for commercial digital satellite systems with low-cost earth terminals, is reported. The study explored trade-offs between coding gain, overall rate and decoder complexity, and compared concatenated schemes with single codes. It concentrated on short block and constraint length inner codes, with soft decision decoding, concatenated with a range of Reed-Solomon outer codes. The dimension of the inner code was matched to the outer code symbol size, and appropriate interleaving between the inner and outer codes was used. Very useful coding gains were achieved with relatively high-rate, low-complexity schemes. For example, concatenating the soft decision decoded (9,8) single parity check inner code with the CCSDS recommended standard Reed-Solomon outer code gives a coding gain of 4.8dB at a bit error probability of 10^?5, with an overall rate of 0-78.     

Turbo码的一种全新的SOVA译码算法

SOVA算法因其译码时延低于MAP算法已成为Turbo码的实用译码算法。本文提出了一种放弃软判决值更新处理的全新的SOVA算法。该算法的独到之处在于,综合利用对栅格图的正向和反向搜索,从而实现了通过全局路径比较来产生软输出值。仿真结果表明,与传统SOVA算法相比这种全新的SOVA算法在不会明显增加译码计算量的前提下,显著地改善了译码性能。同时,其误码率性能在高信噪比时略优于Max-Log-MAP算法,并且已经逼近MAP算法。     

联合判决估计在软判决Viterbi译码中的应用

该文利用相邻判决数据间的相互关系,提出了一种Viterbi截尾译码的改进算法,并将其应用到Turbo码的SOVA译码中。仿真表明,可以很好地降低复杂性和功耗。对Viterbi译码,可使留选存储的规模和功耗减少约20％,回溯单元的规模和功耗减少约30％。对Turbo码的SOVA译码,可使可靠值存储和输出单元的规模和功耗降低约15％,或迭代次数减少一半。     

Modification of branch metric calculation to improve iterative SOVA decoding of turbo codes

It is known that the performance of a SOVA (soft output Viterbi algorithm) turbo decoder can be improved, as the extrinsic information that is produced at its output is over-optimistic. A new parameter associated with the branch metrics calculation in the standard Viterbi algorithm is introduced that affects the turbo code performance. Different parameter values show a simulation improvement in the AWGN channel as well as in an uncorrelated Rayleigh fading channel. By choosing the best value of this parameter, a coding gain improvement of 0.25 dB at BER of 10/sup -5/ is achieved compared to existing schemes.