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.     

基于改进2-DGRS码的QC-LDPC码高效构造

利用GRS(generalized reed-solomon)码的生成多项式提出了基于改进的2-D GRS(two-dimensional GRS)码设计和构造QC-LDPC(quasi-cyclic low density parity-check)码的方法,使所构造的码具有较好的译码性能。同时在码的构造过程中,考虑到了准双对角线结构和合适的度分布。不同码率的LDPC码用于和新设计的QC-LDPC码进行测试和比较。实验结果表明,所提出的码构造方法可加快LDPC码校验矩阵的构造,同时基于所提出方法构造的QC-LDPC码可提高译码性能,并降低编码复杂度。     

DC-free error-correcting codes based on convolutional codes

A new construction of direct current (DC)-free error-correcting codes based on convolutional codes is proposed. The new code is constructed by selecting a proper subcode from a convolutional code composed of two different component codes. The encoder employs a Viterbi algorithm as the codeword selector so that the selected code sequences satisfy the DC constraint. A lower bound on the free distance of such codes is proposed, and a procedure for obtaining this bound is presented. A sufficient condition for these codes to have a bounded running digital sum (RDS) is proposed. Under the assumption of a simplified codeword selection algorithm, we present an upper bound on the maximum absolute value of the RDS and derive the sum variance for a given code. A new construction of standard DC-free codes, i.e., DC-free codes without error-correcting capability, is also proposed. These codes have the property that the decoder can be implemented by simple symbol-by-symbol hard decisions. Finally, under the new construction, we propose several codes that are suitable for the systems that require small sum variance and good error-correction capability     

Runlength-limited codes for mixed-error channels

The mixed-error channel (MC) combines the binary symmetric channel and the peak shift channel. The construction of (d, k) constrained t-MC-error-correcting block codes is described. It is demonstrated that these codes can achieve a code rate close to the ( d, k) capacity. The encoding and decoding procedures are described. The performance of the construction depends on a particular partitioning of (d, k) constrained block codes. This partitioning is discussed and various tables of codes are included. Examples on encoding/decoding and on code performance are given     

一种基于增强奇偶校验码级联极化码的新型编译码方法

极化码作为一种纠错码,具有较好的编译码性能,已成为5G短码控制信道的标准编码方案。但在码长较短时,其性能不够优异。提出一种基于增强奇偶校验码级联极化码的新型编译码方法,在原有的奇偶校验位后设立增强校验位,对校验方程中信道可靠度较低的信息位进行双重校验,辅助奇偶校验码在译码过程中对路径进行修剪,以此提高路径选择的可靠性。仿真结果表明,在相同信道、相同码率码长下,本文提出的新型编译码方法比循环冗余校验(cyclic redundancy check,CRC)码级联极化码、奇偶校验(parity check,PC)码级联极化码误码性能更优异。在高斯信道下,当码长为128、码率为1/2、误码率为10-3时,本文提出的基于增强PC码级联的极化码比PC码级联的极化码获得了约0.3dB增益,与CRC辅助的极化码相比获得了约0.4 dB增益。     

光通信系统中基于伽罗华域乘群的QC-LDPC码的一种新颖构造方法

基于Galois域GF(q)乘群,提出了一种构造简单且编码容易实现的新颖准循环低密度奇偶校验(QC-LDPC)码构造方法,可灵活地调整码长、码率,且编译码复杂度低。用本文方法构造了适用于光通信系统的非规则QC-LDPC(3843,3603)码,仿真表明,与已广泛用于光通信系统中的经典RS(255,239)码相比,用本文方法构造的码具有更好的纠错性能,且其性能优于用SCG方法构造的LDPC码和规则的QC-LDPC(4221,3956)码,适合用于高速长距离光通信系统。     

Quasi-cyclic generalized ldpc codes with low error floors

In this paper, a novel methodology for designing structured generalized LDPC (G-LDPC) codes is presented. The proposed design results in quasi-cyclic G-LDPC codes for which efficient encoding is feasible through shift-register-based circuits. The structure imposed on the bipartite graphs, together with the choice of simple component codes, leads to a class of codes suitable for fast iterative decoding. A pragmatic approach to the construction of G-LDPC codes is proposed. The approach is based on the substitution of check nodes in the protograph of a low-density parity-check code with stronger nodes based, for instance, on Hamming codes. Such a design approach, which we call LDPC code doping, leads to low-rate quasi-cyclic G-LDPC codes with excellent performance in both the error floor and waterfall regions on the additive white Gaussian noise channel.     

Rotationally invariant nonlinear trellis codes for two-dimensionalmodulation

A general parity-check equation is presented that defines rotationally invariant trellis codes of rate k/(k+1) for two-dimensional signal sets. This parity-check equation is used to find rate k/(k+1) codes for 4PSK, 8PSK, 16PSK, and QAM signal sets by systematic code searches. The MPSK codes exhibit smaller free Euclidean distances than nonrotationally invariant linear codes with the same number of states. However, since the nonlinear codes have a smaller number of nearest neighbors, their performance at moderate signal to noise ratios is close to that of the best linear codes. The rotationally invariant QAM codes with 8, 32, 64, and 256 states achieve the same free Euclidean distance as the best linear codes. Transparency of user information under phase rotations is accomplished either by conventional differential encoding and decoding, or by integrating this function directly into the code trellis     

The design of efficiently-encodable rate-compatible LDPC codes - [transactions papers]

We present a new class of irregular low-density parity-check (LDPC) codes for moderate block lengths (up to a few thousand bits) that are well-suited for rate-compatible puncturing. The proposed codes show good performance under puncturing over a wide range of rates and are suitable for usage in incremental redundancy hybrid-automatic repeat request (ARQ) systems. In addition, these codes are linear-time encodable with simple shift-register circuits. For a block length of 1200 bits the codes outperform optimized irregular LDPC codes and extended irregular repeat-accumulate (eIRA) codes for all puncturing rates 0.6~0.9 (base code performance is almost the same) and are particularly good at high puncturing rates where good puncturing performance has been previously difficult to achieve.     

Hybrid block- self-orthogonal convolutional codes

Two convolutional-code construction schemes that utilize block codes are given. In the first method the generators of a self-orthogonal convolutional code (SOCC) are expanded. The generators of a block code whose block length is longer than that of the SOCC code replace the nonzero blocks of the convolutional code. The zero blocks are extended to the longer block length. There results a convolutional code whose blocks are self-orthogonal and which has a lower transmission rate. In the second scheme the parity constraints of an SOCC are expanded. The parity constraints of a block code replace some of the individual nonzero elements of the SOCC parity-check matrix, so that the convolutional code rate is greater than the block code rate. The resulting codes retain the SOCC advantages of simple implementation and limited error propagation. Both the encoding and the decoding can be based on the underlying block code. If a block code is majority decodable, then the resulting "hybrid" codes are majority decodable. Optimum majority-decodable block codes with up to five information bits per block are given, and from these codes several majority-decodable convolutional codes that are "optimum" with respect to the proposed construction are obtained.     

On unequal error protection LDPC codes based on plotkin-type constructions

We introduce a new family of unequal error protection (UEP) codes, based on low-density parity-check (LDPC) component codes and Plotkin-type constructions. The codes are decoded iteratively in multiple stages, and the order of decoding determines the level of error protection. The level of UEP among the code bits is also influenced by the choice of the LDPC component codes and by some new reliability features incorporated into the decoding process. The proposed scheme offers a very good tradeoff between code performance on one side and encoding/decoding and storage complexity on the other side. The novel approach to UEP also allows for finding simple approximations for the achievable degrees of UEP, which can be used to govern practical code design implementations.     

Single parity check product codes

This paper considers the performance of iteratively decoded single parity check (SPC) multidimensional product codes in an additive white Gaussian noise channel. Asymptotic performance bounds are compared to simulation results. A new code structure based on SPC product codes is introduced. This structure involves interleaving between the encoding of each dimension in the product code. An analysis of the weight distribution is used to explain the good performance results for these randomly interleaved SPC product codes     

Binary multilevel coset codes based on Reed-Muller codes

We study the construction and decoding of binary multilevel coset codes. This construction, originally introduced by Blokh and Zyablov in 1974 and by Zinov'ev in 1976, shows remarkable analogies with most recent schemes of coded modulations. Basic elements of the construction are an inner code, head of a partition chain having suitable distance properties, and a set of outer codes, generally nonbinary. For each partition level there is an outer code whose alphabet has the same order of the partition: in this way it is possible to associate every partition subset to a code symbol. It is well known that these codes can be efficiently decoded by the so called “multistage decoding.” We show that good codes (in terms of performance/complexity) can be constructed using Reed-Muller (RM) codes as inner codes. To this aim RM codes are revisited in the framework of the above construction and decoding techniques. In particular we describe a family of decoders for RM codes which include Forney's (1988) and Hemmati's (1989) decoders as special cases. Finally, we present some examples of efficient binary codes based on RM codes, and assess their performance via computer simulation     

High-performance simple-encoding generator-based systematic irregular LDPC codes and resulted product codes

Low-Density Parity-Check (LDPC) code is one of the most exciting topics among the coding theory community.It is of great importance in both theory and practical communications over noisy channels.The most advantage of LDPC codes is their relatively lower decoding complexity compared with turbo codes,while the disadvantage is its higher encoding complexity.In this paper,a new ap- proach is first proposed to construct high performance irregular systematic LDPC codes based on sparse generator matrix,which can significantly reduce the encoding complexity under the same de- coding complexity as that of regular or irregular LDPC codes defined by traditional sparse parity-check matrix.Then,the proposed generator-based systematic irregular LDPC codes are adopted as con- stituent block codes in rows and columns to design a new kind of product codes family,which also can be interpreted as irregular LDPC codes characterized by graph and thus decoded iteratively.Finally, the performance of the generator-based LDPC codes and the resultant product codes is investigated over an Additive White Gaussian Noise (AWGN) and also compared with the conventional LDPC codes under the same conditions of decoding complexity and channel noise.     

Multilevel trellis MPSK modulation codes for the Rayleigh fadingchannel

The multilevel coding technique is used for constructing multilevel trellis M-ary phase-shift-keying (MPSK) modulation codes for the Rayleigh fading channel. In the construction of a code, all the factors which affect the code performance and its decoding complexity are considered. The error performance of some of these codes based on both one-stage optimum decoding and multistage suboptimum decoding has been simulated. The simulation results show that these codes achieve good error performance with small decoding complexity     

Transmission performance analysis of a new class of line codes for optical fiber systems

A family of mB(m+1)B binary, nonalphabetic, balanced line codes is presented that is suitable for high bit rate (>or=135 Mb/s) optical fiber transmission due to its relatively simple encoding and decoding rules. Here, B represents a block of m bits, where m is an odd number. The coding, decoding, and bit error rate (BER) performance of the codes are discussed. Statistical and spectral analysis for the specific case in which the number of bits, m, equals seven, is presented. This makes possible a detailed comparison of the proposed code with conventional 7B8B codes.<>     

Constructions of error-correcting DC-free block codes

Two DC-free codes are presented with distance 2d, b ⩾1 length 2n+2r(d-1) for d⩽3 and length 2n+2r(d-1)(2d -1) for d>3, where r is the least integer ⩾log₂ (2n+1). For the first code l=4, c=2, and the asymptotic rate of this code is 0.7925. For the second code l=6, c=3, and the asymptotic rate of this code is 0.8858. Asymptotically, these rates achieve the channel capacity. For small values of n these codes do not achieve the best rate. As an example of codes of short length with good rate, the author presents a (30, 10, 6, 4) DC-free block code with 2²¹ codewords. A construction is presented for which from a given code C ₁ of length n, even weight, and distance 4, the author obtains a (4n, l, c, 4) DC-free block code C₂, where l is 4, 5 or 6, and c is not greater than n+1 (but usually significantly smaller). The codes obtained by this method have good rates for small lengths. The encoding and decoding procedures for all the codes are discussed     

Multilevel block codes for Rayleigh-fading channels

New multilevel block codes for Rayleigh-fading channels are presented. At high signal-to-noise ratios (SNRs), the proposed block codes can achieve better bit error performance over TCM codes, optimum for fading channels, with comparable decoder complexity and bandwidth efficiency. The code construction is based on variant length binary component block codes. As component codes for the 8-PSK multilevel block construction, the authors propose two modified forms of Reed-Muller codes giving a good trade-off between the decoder complexity and the effective code rates. Code design criteria are derived from the error performance analysis. Multistage decoding shows very slight degradation of bit error performance relative to the maximum likelihood algorithm     

An improved construction algorithm of polar codes based on the frozen bits

In order to improve the problems that the minimum hamming weight(MHW) of the polar codes of the traditional Gaussian approximation(GA) construction is small and its performance is not good enough, an improved channel construction algorithm of polar codes based on frozen bits is proposed by combining the construction of the Reed-Muller(RM) code to effectively increase the MHW and analyzing the correcting and checking functions of the frozen bits in the successive cancellation list(SCL) decoding. ...