A novel approach for evaluating the performance of SPC productcodes under erasure decoding

Product codes are powerful codes that can be used to correct errors or recover erasures. The simplest form of a product code is that where every row and every column is terminated by a single parity bit, referred to as single parity check (SPC) product code. This code has a minimum distance of four and is thus guaranteed to recover all single, double, and triple erasure patterns. Judging the code performance based on its minimum distance is very pessimistic because the code is actually capable of recovering many higher erasure patterns. This paper develops a novel approach for deriving an upper bound on the post-decoding erasure rate for the SPC product code with iterative decoding. Simulation shows that the derived bound is very tight     

On the performance of high-rate TPC/SPC codes and LDPC codes overpartial response channels

This paper evaluates two-dimensional turbo product codes based on single-parity check codes (TPC/SPC) and low-density parity check (LDPC) codes for use in digital magnetic recording systems. It is first shown that the combination of a TPC/SPC code and a precoded partial response (PR) channel results in a good distance spectrum due to the interleaving gain. Then, density evolution is used to compute the thresholds for TPC/SPC codes and LDPC codes over PR channels. Analysis shows that TPC/SPC codes have a performance close to that of LDPC codes for large codeword lengths. Simulation results for practical block lengths show that TPC/SPC codes perform as well as LDPC codes in terms of bit error rate, but possess better burst error statistics which is important in the presence of an outer Reed-Solomon code. Further, the encoding complexity of TPC/SPC codes is only linear in the codeword length and the generator matrix does not have to be stored explicitly. Based on. the results in the paper and these advantages, TPC/SPC codes seem like a viable alternative to LDPC codes     

Product accumulate codes: a class of codes with near-capacity performance and low decoding complexity

We propose a novel class of provably good codes which are a serial concatenation of a single-parity-check (SPC)-based product code, an interleaver, and a rate-1 recursive convolutional code. The proposed codes, termed product accumulate (PA) codes, are linear time encodable and linear time decodable. We show that the product code by itself does not have a positive threshold, but a PA code can provide arbitrarily low bit-error rate (BER) under both maximum-likelihood (ML) decoding and iterative decoding. Two message-passing decoding algorithms are proposed and it is shown that a particular update schedule for these message-passing algorithms is equivalent to conventional turbo decoding of the serial concatenated code, but with significantly lower complexity. Tight upper bounds on the ML performance using Divsalar's (1999) simple bound and thresholds under density evolution (DE) show that these codes are capable of performance within a few tenths of a decibel away from the Shannon limit. Simulation results confirm these claims and show that these codes provide performance similar to turbo codes but with significantly less decoding complexity and with a lower error floor. Hence, we propose PA codes as a class of prospective codes with good performance, low decoding complexity, regular structure, and flexible rate adaptivity for all rates above 1/2.     

Asymptotically Gaussian weight distribution and performance of multicomponent turbo block codes and product codes

It was suggested by Battail that a good long linear code should have a weight distribution close to that of random coding, rather than a large minimum distance, and a turbo code should be also designed using a random-like criterion. In this paper, we first show that the weight distribution of a high-rate linear block code is approximately Gaussian if the code rate is close enough to one, and then proceed to construct a low-rate linear block code with approximately Gaussian weight distribution by using the turbo-coding technique. We give a sufficient condition under which the weight distribution of multicomponent turbo block (MCTB) codes (multicomponent product (MCP) codes, respectively) can approach asymptotically that of random codes, and further develop two classes of MCTB codes (MCP codes) satisfying this condition. Simulation results show that MCTB codes (MCP codes) having asymptotically Gaussian weight distribution can asymptotically approach Shannon's capacity limit. MCTB codes based on single parity-check (SPC) codes have a far poorer minimum distance than MCP codes based on SPC codes, but we show by simulation that when the bit-error rate is in the important range of 10/sup -1/-10/sup -5/, these codes can still offer similar performance for the additive white Gaussian noise channel, as long as the code length of the SPC codes is not very short. These facts confirm in a more precise way Battail's inference about the "nonimportance" of the minimum distance for a long code.     

Multiple serial and parallel concatenated single parity-check codes

Single parity-check (SPC) codes are applied in both parallel and serial concatenated structures to produce high-performance coding schemes. The number of concatenations or stages, M, is increased to improve system performance at moderate-to-low bit-error rates without changing the overall code parameters (namely, code rate and code block length). Analytical bounds are presented to estimate the performance at high signal-to-noise ratios. The SPC concatenated codes are considered with binary phase-shift keying and with 16-quadrature amplitude modulation bit-interleaved coded modulation on the additive white Gaussian noise channel and the independent Rayleigh fading channel. Simulations show that the four-stage serial or parallel concatenated SPC codes can, respectively, outperform or perform as well as 16-state turbo codes. Furthermore, decoding complexity is approximately 9-10 times less complex than that of 16-state turbo codes. The convergence behavior of both serial and parallel concatenated SPC codes is also discussed.     

A New Linear Programming Approach to Decoding Linear Block Codes

In this paper, we propose a new linear programming formulation for the decoding of general linear block codes. Different from the original formulation given by Feldman, the number of total variables to characterize a parity-check constraint in our formulation is less than twice the degree of the corresponding check node. The equivalence between our new formulation and the original formulation is proven. The new formulation facilitates to characterize the structure of linear block codes, and leads to new decoding algorithms. In particular, we show that any fundamental polytope is simply the intersection of a group of the so-called minimum polytopes, and this simplified formulation allows us to formulate the problem of calculating the minimum Hamming distance of any linear block code as a simple linear integer programming problem with much less auxiliary variables. We then propose a branch-and-bound method to compute a lower bound to the minimum distance of any linear code by solving a corresponding linear integer programming problem. In addition, we prove that, for the family of single parity-check (SPC) product codes, the fractional distance and the pseudodistance are both equal to the minimum distance. Finally, we propose an efficient algorithm for decoding SPC product codes with low complexity and maximum-likelihood (ML) decoding performance.      

Iterative decoding of parallel and serial concatenated single parity check product codes

An efficient, iterative soft-in-soft-out decoding scheme is employed for the parallel and serially concatenated single parity check (SPC) product codes, which has very low complexity, requiring only two addition-equivalent-operations per information bit. For a rate 0.8637 of parallel concatenated SPC product code, a performance of BER=10/sup -5/ at E/sub b//N/sub 0/=3.66 dB can be achieved using this decoding scheme, which is within 1 dB from the Shannon limit.     

SPC乘积码用于纠删译码的性能分析

SPC乘积码是一种既可以纠错,又可以恢复删除的高效码。该码的最小码距是4,能够恢复所有单阶,两阶和三阶的删除模式,实际上这种码能够恢复更高阶的删除模式。传统上是通过最小码间距来评价SPC乘积码译码性能,若从其空间结构入手,能够推导出SPC乘积码迭代译码后删除率的新上界。仿真显示这个上界更紧。     

一类性能好、复杂度低的纠错编码--乘加码

对一类性能好且复杂度低的纠错编码技术——乘加码进行了介绍。他是在单校验位的Turbo乘积码(Single Parity Check Turbo Product Code)的基础上改进而来的,即由单校验位的Turbo乘积码作为外码,码率为1的递归卷积码作为内码串行级联而成。介绍了乘加码的编码方式和译码方法,并给出了其性能分析。对于一定的分组长度,这类码表现出与Turbo码相近的性能,但其译码复杂度要远远低于Turbo码。     

Efficient soft-in-soft-out sub-optimal decoding rule for singleparity check codes

The authors present an efficient, sub-optimal, soft-in-soft-out decoding rule for single parity check (SPC) codes, which requires only three addition-equivalent-operations per information bit. Its application is demonstrated by the simulation results of a rate 5/6 four-dimensional concatenated SPC code, for which performance of BER=10 ^-5 at E_h/N₀=3.5 dB is observed, which is only ~1.2 dB from the theoretical limit     

Full-rate full-diversity space-frequency codes with optimum coding advantage

A general space-frequency (SF) block code structure is proposed that can guarantee full-rate (one channel symbol per subcarrier) and full-diversity transmission in multiple-input multiple-output-orthogonal frequency-division multiplexing (MIMO-OFDM) systems. The proposed method can be used to construct SF codes for an arbitrary number of transmit antennas, any memoryless modulation and arbitrary power-delay profiles. Moreover, assuming that the power-delay profile is known at the transmitter, we devise an interleaving method to maximize the overall performance of the code. We show that the diversity product can be decomposed as the product of the "intrinsic" diversity product, which depends only on the used signal constellation and the code design, and the "extrinsic" diversity product, which depends only on the applied interleaving method and the power delay profile of the channel. Based on this decomposition, we propose an interleaving strategy to maximize the "extrinsic" diversity product. Extensive simulation results show that the proposed SF codes outperform the previously existing codes by about 3-5 dB, and that the proposed interleaving method results in about 1-3-dB performance improvement compared to random interleaving.     

Nonlinear Product Codes and Their Low Complexity Iterative Decoding

This paper proposes encoding and decoding for nonlinear product codes and investigates the performance of nonlinear product codes. The proposed nonlinear product codes are constructed as N‐dimensional product codes where the constituent codes are nonlinear binary codes derived from the linear codes over higher order alphabets, for example, Preparata or Kerdock codes. The performance and the complexity of the proposed construction are evaluated using the well‐known nonlinear Nordstrom‐Robinson code, which is presented in the generalized array code format with a low complexity trellis. The proposed construction shows the additional coding gain, reduced error floor, and lower implementation complexity. The (64, 24, 12) nonlinear binary product code has an effective gain of about 2.5 dB and 1 dB gain at a BER of 10^?6 when compared to the (64, 15, 16) linear product code and the (64, 24, 10) linear product code, respectively. The (256, 64, 36) nonlinear binary product code composed of two Nordstrom‐Robinson codes has an effective gain of about 0.7 dB at a BER of 10^?5 when compared to the (256, 64, 25) linear product code composed of two (16, 8, 5) quasi‐cyclic codes.     

Turbo Product Codes Based on Convolutional Codes

In this article, we introduce a new class of product codes based on convolutional codes, called convolutional product codes. The structure of product codes enables parallel decoding, which can significantly increase decoder speed in practice. The use of convolutional codes in a product code setting makes it possible to use the vast knowledge base for convolutional codes as well as their flexibility in fast parallel decoders. Just as in turbo codes, interleaving turns out to be critical for the performance of convolutional product codes. The practical decoding advantages over serially‐concatenated convolutional codes are emphasized.     

Combined turbo codes and interleaver design

The impact of the distance spectrum and interleaver structure on the bit error probability of turbo codes is considered. A new turbo code design method for Gaussian channels is presented. The proposed method combines a search for good component codes with interleaver design. The optimal distance spectrum is used as the design criterion to construct good turbo component codes at low signal-to-noise ratios (SNRs). In addition, an interleaver design method is proposed. This design improves the code performance at high SNR. Search for good component codes at low SNR is combined with a code matched interleaver design. This results in new turbo codes with a superior error performance relative to the best known codes at both low and high SNR. The performance is verified by both analysis and simulation     

Enhanced Upper Bound for Erasure Recovery in SPC Product Codes

Single parity check (SPC) product codes are simple yet powerful codes that are used to correct errors and/or recover erasures. The focus of this paper is to evaluate the performance of such codes under erasure scenarios and to develop a closed‐form tight upper bound for the post‐decoding erasure rate. Closed‐form exact expressions are derived for up to seven erasures. Previously published closed‐form bounds assumed that all unrecoverable patterns should contain four erasures in a square. Additional non‐square patterns are accounted for in the proposed expressions. The derived expressions are verified using exhaustive search. Eight or more erasures are accounted for by using a bound. The developed expressions improve the evaluation of the recoverability of SPC product codes without the need for simulation or search algorithms, whether exhaustive or novel.     

On the Performance and Implementation Issues of Interleaved Single Parity Check Turbo Product Codes

In this paper, both performance and complexity aspects of two-dimensional single parity check turbo product codes (I-SPC-TPC) are investigated. Based on the proposed I-SPC-TPC coding scheme, a parallel decoding structure is developed to increase the decoding throughput with minor performance degradation compared with the serial structure. For both decoding architectures, a new helical interleaver is constructed to further improve the coding gain. In terms of decoding algorithm, the extremely simple Sign-Min decoding is alternatively derived with only three additions needed to compute each bit's extrinsic information. For performance evaluation, (16, 14, 2)² single parity check turbo product code with code rate 0.766 over AWGN channel using QPSK modulation is considered. The simulation results using Sign-Min decoding show that it can achieve bit-error-rate of 10^?5 at signal-to-noise ratio of 3.8 dB with 8 iterations. Compared to the same rate and codeword length turbo product code composed of extended Hamming codes, the considered scheme can achieve similar performance with much less complexity. Important implementation issues such as the finite precision analysis, efficient sorting circuit design and interleaver memory management are also presented.     

一种非规则广义LDPC码的构造方法

广义低密度奇偶校验(Generalized Low睤ensity Parity睠heck,GLDPC)码把低密度奇偶校验(Low睤ensity Parity睠heck,LDPC)码中的单奇偶校验(Single Parity睠heck,SPC)节点替换为校验能力更强的广义约束(Generalized Constraint,GC)节点,使其在中短码和低码率的条件下具有更低的误码率。传统GLDPC码要求基矩阵的行重等于分量码的码长,这限制了GLDPC码构造的灵活性。另外,相比于传统GLDPC码中GC节点位置的随机选取,GC节点的位置选择在GLDPC码的误码率性能上有一定的优化空间。针对以上两点,提出了一种基于渐进边增长(Progressive Edge-rowth,PEG)算法的非规则GLDPC码构造方法和一种基于Tanner图边数的GC节点位置选择算法。使用PEG算法生成的非规则LDPC码作为本地码,根据本地码的校验节点度使用多种分量码,结合GC节点位置选择算法构造非规则GLDPC码。仿真结果表明,与传统方法构造的GLDPC码相比,基于Tanner图边数的GC节点位置选择算法构造的非规则PEG-LDPC码在误码率和译码复杂度上均得到明显改善。     

基于多维乘积码的编码协作方案研究

多维乘积码是一种成熟的编码技术,其性能较好,且具有灵活的多维结构。本文提出一种基于多维乘积码的协作方案,利用不同维数的校验位进行协作,达到获取分集增益的目的。文中以分量码为扩展汉明码的多维乘积码为例,在慢衰落、快衰落瑞利信道下进行了理论性能分析和计算机仿真,仿真结果显示:慢衰落信道下,BER为10-3时,协作程度为50%,用户间信道SNR大于10dB时,增益大于8dB;在快衰落信道下,可以通过该协作方案可达到帮助上行信道较差的用户的目的。从实用性和良好性能的角度来看,该编码协作将具有较好的应用前景。      

乘积码迭代译码算法研究

介绍了在分组码的软输入软输出译码基础上以扩展BCH码为子码的乘积码的迭代译码算法,提出了在高带宽利用率调制方式下的算法应用方式,并给出了仿真结果。最后与传统的并联卷级码代译码方案比较,发现在高编码效率时,乘积码迭代译码方案有着较好的应用性。     

码率自适应的多维Turbo乘积码系统设计

对多维Turbo乘积码在码率、码型、维数各不相同的情况下的性能进行了仿真研究,得出结论:在相同码率的前提下,选择性能优良的码型,增加码的维数,都可以提高码的性能;并在此基础上提出了一种新型的针对无线信道的码率自适应系统;仿真结果显示,在误码率为10-5时,该系统与固定码率系统相比,在信息传输速率上有明显的优势。