Bandwidth-Efficient Modulation Codes Based on Nonbinary Irregular Repeat–Accumulate Codes

Using nonbinary low-density parity-check (LDPC) codes with random-coset mapping, Bennatan and Burshtein constructed bandwidth-efficient modulation codes with remarkable performance under belief propagation (BP) decoding. However, due to the random nature of LDPC codes, most of the good LDPC codes found in the literature do not have a simple encoding structure. Thus, the encoding complexity of those LDPC codes can be as high as O(N ²), where N is the codeword length. To reduce the encoding complexity, in this paper, nonbinary irregular repeat-accumulate (IRA) codes with time-varying characteristic and random-coset mapping are proposed for bandwidth-efficient modulation schemes. The time-varying characteristic and random-coset mapping result in both permutation-invariance and symmetry properties, respectively, in the densities of decoder messages. The permutation-invariance and symmetry properties of the proposed codes enable the approximations of densities of decoder messages using Gaussian distributions. Under the Gaussian approximation, extrinsic information transfer (EXIT) charts for nonbinary IRA codes are developed and several codes of different spectral efficiencies are designed based on EXIT charts. In addition, by proper selection of nonuniform signal constellations, the constructed codes are inherently capable of obtaining shaping gains, even without separate shaping codes. Simulation results indicate that the proposed codes not only have simple encoding schemes, but also have remarkable performance that is even better than that constructed using nonbinary LDPC codes.     

BIBD循环置换矩阵的多进制LDPC码构造

提出了基于均衡不完全区组设计(Balanced Incomplete Block Design,BIBD)的多进制准循环LDPC(Low-Density Parity-Check)码代数构造方法。在该构造方法中提出了广义多进制位置向量的概念,并根据广义多进制位置向量和BIBD法对指数矩阵进行广义二维扩展,构造出具有循环置换子矩阵的多进制校验矩阵,由此得到girth不小于6的多进制LDPC码。仿真结果表明,采用FFT-QSPA(基于快速傅里叶变换的多进制和积算法)对构造出的LDPC码进行译码,在AWGN信道下相比于同参数的RS码来说可以取得明显的编码增益,并且优于多进制Mackay码。     

Construction of nonbinary cyclic, quasi-cyclic and regular LDPC codes: a finite geometry approach

This paper presents five methods for constructing nonbinary LDPC codes based on finite geometries. These methods result in five classes of nonbinary LDPC codes, one class of cyclic LDPC codes, three classes of quasi-cyclic LDPC codes and one class of structured regular LDPC codes. Experimental results show that constructed codes in these classes decoded with iterative decoding based on belief propagation perform very well over the AWGN channel and they achieve significant coding gains over Reed-Solomon codes of the same lengths and rates with either algebraic hard-decision decoding or Kotter-Vardy algebraic soft-decision decoding at the expense of a larger decoding computational complexity.     

低密度奇偶校验码构造及编译码研究进展

低密度奇偶校验(LDPC)码具有接近Shannon限的良好性能,能有效提高数据传输的可靠性.为提高LDPC码的性能,对码字的研究多集中于构造、编码和译码这几方面的基础研究.首先简要给出了LDPC码的基本描述,然后对二进制和多进制LDPC码的关键技术进行了系统归纳和全新分类,分别从构造、编码和译码3个方面进行了详细探讨,重点对最新的研究成果进行了全面分析和总结,对LDPC码今后的研究具有指导意义.     

A Unified Approach to the Construction of Binary and Nonbinary Quasi-Cyclic LDPC Codes Based on Finite Fields

A unified approach for constructing binary and nonbinary quasi-cyclic LDPC codes under a single framework is presented. Six classes of binary and nonbinary quasi-cyclic LDPC codes are constructed based on primitive elements, additive subgroups, and cyclic subgroups of finite fields. Numerical results show that the codes constructed perform well over the AWGN channel with iterative decoding.     

On the application of LDPC codes to arbitrary discrete-memoryless channels

We discuss three structures of modified low-density parity-check (LDPC) code ensembles designed for transmission over arbitrary discrete memoryless channels. The first structure is based on the well-known binary LDPC codes following constructions proposed by Gallager and McEliece, the second is based on LDPC codes of arbitrary (q-ary) alphabets employing modulo-q addition, as presented by Gallager, and the third is based on LDPC codes defined over the field GF(q). All structures are obtained by applying a quantization mapping on a coset LDPC ensemble. We present tools for the analysis of nonbinary codes and show that all configurations, under maximum-likelihood (ML) decoding, are capable of reliable communication at rates arbitrarily close to the capacity of any discrete memoryless channel. We discuss practical iterative decoding of our structures and present simulation results for the additive white Gaussian noise (AWGN) channel confirming the effectiveness of the codes.     

A fast LDPC encoder/decoder for small/medium codes

Although Low-Density Parity-Check (LDPC) codes perform admirably for large block sizes — being mostly resilient to low levels of channel SNR and errors in channel equalization — real time operation and low computational effort require small and medium sized codes, which tend to be affected by these two factors. For these small to medium codes, a method for designing efficient regular codes is presented and a new technique for reducing the dependency of correct channel equalization, without much change in the inner workings or architecture of existing LDPC decoders is proposed. This goal is achieved by an improved intrinsic Log-Likelihood Ratio (LLR) estimator in the LDPC decoder — the ILE-Decoder, which only uses LDPC decoder-side information gathered during standard LDPC decoding. This information is used to improve the channel parameters estimation, thus improving the reliability of the code correction, while reducing the number of required iterations for a successful decoding. Methods for fast encoding and decoding of LDPC codes are presented, highlighting the importance of assuring low encoding/decoding latency with maintaining high throughput. The assumptions and rules that govern the estimation process via subcarrier corrected-bit accounting are presented, and the Bayesian inference estimation process is detailed. This scheme is suitable for application to multicarrier communications, such as OFDM. Simulation results in a PLC-like environment that confirm the good performance of the proposed LDPC coder/decoder are presented.     

Next Generation FEC for High-Capacity Communication in Optical Transport Networks

Codes on graphs of interest for next generation forward error correction (FEC) in high-speed optical networks, namely turbo codes and low-density parity-check (LDPC) codes, are described in this invited paper. We describe both binary and nonbinary LDPC codes, their design, and decoding. We also discuss an FPGA implementation of decoders for binary LDPC codes. We then explain how to combine multilevel modulation and channel coding optimally by using coded modulation. Also, we describe an LDPC-coded turbo-equalizer as a candidate for dealing simultaneously with fiber nonlinearities, PMD, and residual chromatic dispersion.      

High-Rate Nonbinary Regular Quasi-Cyclic LDPC Codes for Optical Communications

The parity-check matrix of a nonbinary (NB) low-density parity-check (LDPC) code over Galois field GF(q) is constructed by assigning nonzero elements from GF(q) to the 1s in corresponding binary LDPC code. In this paper, we state and prove a theorem that establishes a necessary and sufficient condition that an NB matrix over GF(q), constructed by assigning nonzero elements from GF(q) to the 1s in the parity-check matrix of a binary quasi-cyclic (QC) LDPC code, must satisfy in order for its null-space to define a nonbinary QC-LDPC (NB-QC-LDPC) code. We also provide a general scheme for constructing NB-QC-LDPC codes along with some other code construction schemes targeting different goals, e.g., a scheme that can be used to construct codes for which the fast-Fourier-transform-based decoding algorithm does not contain any intermediary permutation blocks between bit node processing and check node processing steps. Via Monte Carlo simulations, we demonstrate that NB-QC-LDPC codes can achieve a net effective coding gain of 10.8 dB at an output bit error rate of 10^-12. Due to their structural properties that can be exploited during encoding/decoding and impressive error rate performance, NB-QC-LDPC codes are strong candidates for application in optical communications.     

Performance Bounds for Nonbinary Linear Block Codes Over Memoryless Symmetric Channels

The performance of nonbinary linear block codes is studied in this paper via the derivation of new upper bounds on the block error probability under maximum-likelihood (ML) decoding. The transmission of these codes is assumed to take place over a memoryless and symmetric channel. The new bounds, which are based on the Gallager bounds and their variations, are applied to the Gallager ensembles of nonbinary and regular low-density parity-check (LDPC) codes. These upper bounds are also compared with sphere-packing lower bounds. This study indicates that the new upper bounds are useful for the performance evaluation of coded communication systems which incorporate nonbinary coding techniques.      

Decoder Design for RS-Based LDPC Codes

This brief studies very large-scale integration (VLSI) decoder architectures for RS-based low-density parity-check (LDPC) codes, which are a special class of LDPC codes based on Reed-Solomon codes. The considered code ensemble is well known for its excellent error-correcting performance and has been selected as the forward error correction coding scheme for 10GBase-T systems. By exploiting the shift-structured properties hidden in the algebraically generated parity-check matrices, novel decoder architectures are developed with significant advantages of high level of parallel decoding, efficient usage of memory, and low complexity of interconnection. To demonstrate the effectiveness of the proposed techniques, we completed a high-speed decoder design for a (2048, 1723) regular RS-LDPC code, which achieves 10-Gb/s throughput with only 820 000 gates. Furthermore, to support all possible RS-LDPC codes, two special cases in code construction are considered, and the corresponding extensions of the decoder architecture are investigated.     

Quasi-cyclic LDPC codes using overlapping matrices and their layered decoders

Quasi-cyclic (QC) low-density parity-check (LDPC) codes have the parity-check matrices consisting of circulant matrices. Since QC LDPC codes whose parity-check matrices consist of only circulant permutation matrices are difficult to support layered decoding and, at the same time, have a good degree distribution with respect to error correcting performance, adopting multi-weight circulant matrices to parity-check matrices is useful but it has not been much researched. In this paper, we propose a new code structure for QC LDPC codes with multi-weight circulant matrices by introducing overlapping matrices. This structure enables a system to operate on dual mode in an efficient manner, that is, a standard QC LDPC code is used when the channel is relatively good and an enhanced QC LDPC code adopting an overlapping matrix is used otherwise. We also propose a new dual mode parallel decoder which supports the layered decoding both for the standard QC LDPC codes and the enhanced QC LDPC codes. Simulation results show that QC LDPC codes with the proposed structure have considerably improved error correcting performance and decoding throughput.     

Transactions Papers - Constructions of Nonbinary Quasi-Cyclic LDPC Codes: A Finite Field Approach

This paper is concerned with construction of efficiently encodable nonbinary quasi-cyclic LDPC codes based on finite fields. Four classes of nonbinary quasi-cyclic LDPC codes are constructed. Experimental results show that codes constructed perform well with iterative decoding using a fast Fourier transform based q-ary sum-product algorithm and they achieve significant coding gains over Reed-Solomon codes of the same lengths and rates decoded with either algebraic hard- decision Berlekamp-Massey algorithm or algebraic soft-decision Kotter-Vardy algorithm.     

带宽有效传输下多进制LDPC码的不等错误保护

针对频谱有效的多进制低密度奇偶校验（Low-Density Parity-Check,LDPC）码编码调制系统,本文提出了一种在带宽有效传输下的两级不等保护方案,两级不等错误保护分别来自码字特性和高阶调制,充分利用了码字变量节点的度和高阶调制中比特的不等可靠性。编码调制系统采用多进制LDPC码与高阶调制匹配结合,无需信息转换,针对不同误符号率和误比特率的需求,可在符号级和比特级提供不同可靠性达到不等错误保护的目的。仿真结果表明,在AWGN信道下,采用16QAM调制方式的性能优于16PSK调制方式,利用变量节点的度和高阶调制提供的信息,码字的误符号率和误比特率具有明显的不等错误保护区分度,对于重要的比特给予了较强的保护。      

基于平均概率和停止准则的多元LDPC码加权符号翻转译码算法

为了提高多元低密度奇偶校验(LDPC, low density parity-check)码符号翻转译码算法的性能并降低译码的复杂度,提出了基于平均概率和停止准则的多元LDPC码加权符号翻转译码(APSCWSF, average probability and stopping crite-rion weighted symbol flipping)算法。该算法将校验节点邻接符号节点的平均概率信息作为权重,使翻转函数更加有效,提高符号的翻转效率,进而改善译码性能。并且通过设置迭代停止准则进一步加快算法的收敛速度。仿真结果显示,在加性高斯白噪声信道下,误符号率为10?5时,相比WSF算法、NSCWSF算法(Osc=10)和NSCWSF算法(Osc=6),APSCWSF算法(Osc=10)分别获得约0.68 dB、0.83 dB和0.96 dB的增益。同时,APSCWSF算法(Osc=6)的平均迭代次数也分别降低78.60% ~79.32%、74.89% ~ 75.95% 和67.20% ~70.80%。     

Power Reduction Techniques for LDPC Decoders

This paper investigates VLSI architectures for low-density parity-check (LDPC) decoders amenable to low- voltage and low-power operation. First, a highly-parallel decoder architecture with low routing overhead is described. Second, we propose an efficient method to detect early convergence of the iterative decoder and terminate the computations, thereby reducing dynamic power. We report on a bit-serial fully-parallel LDPC decoder fabricated in a 0.13-$mu{hbox{m}}$ CMOS process and show how the above techniques affect the power consumption. With early termination, the prototype is capable of decoding with 10.4 pJ/bit/iteration, while performing within 3 dB of the Shannon limit at a BER of 10$^{-5}$ and with 3.3 Gb/s total throughput. If operated from a 0.6 V supply, the energy consumption can be further reduced to 2.7 pJ/bit/iteration while maintaining a total throughput of 648 Mb/s, due to the highly-parallel architecture. To demonstrate the applicability of the proposed architecture for longer codes, we also report on a bit-serial fully-parallel decoder for the (2048, 1723) LDPC code in 10GBase-T standard synthesized with a 90-nm CMOS library.      

Low Complexity Decoder Architecture for Low-Density Parity-Check Codes

In this paper, we propose a low complexity decoder architecture for low-density parity-check (LDPC) codes using a variable quantization scheme as well as an efficient highly-parallel decoding scheme. In the sum-product algorithm for decoding LDPC codes, the finite precision implementations have an important tradeoff between decoding performance and hardware complexity caused by two dominant area-consuming factors: one is the memory for updated messages storage and the other is the look-up table (LUT) for implementation of the nonlinear function Ψ(x). The proposed variable quantization schemes offer a large reduction in the hardware complexities for LUT and memory. Also, an efficient highly-parallel decoder architecture for quasi-cyclic (QC) LDPC codes can be implemented with the reduced hardware complexity by using the partially block overlapped decoding scheme and the minimized power consumption by reducing the total number of memory accesses for updated messages. For (3, 6) QC LDPC codes, our proposed schemes in implementing the highly-parallel decoder architecture offer a great reduction of implementation area by 33% for memory area and approximately by 28% for the check node unit and variable node unit computation units without significant performance degradation. Also, the memory accesses are reduced by 20%.     

On turbo decoding of nonbinary codes

Symbol-by-symbol maximum a posteriori (MAP) decoding algorithms for nonbinary block and convolutional codes over an extension field GF(p ^a) are presented. Equivalent MAP decoding rules employing the dual code are given which are computationally more efficient for high-rate codes. It is shown that these algorithms meet all requirements needed for iterative decoding as the output of the decoder can be split into three independent estimates: soft channel value, a priori term and extrinsic value. The discussed algorithms are then applied to a parallel concatenated coding scheme with nonbinary component codes in conjunction with orthogonal signaling     

低秩循环矩阵的构造方法及其关联的多元LDPC码

在图像处理中,低秩矩阵的冗余信息可用于图像恢复和图像特征提取,而在迭代译码中,校验矩阵的冗余行可以加快译码收敛速度。该文研究一类易于硬件实现的低秩循环矩阵。首先将循环矩阵转换为位置集合,并基于同构理论简化了位置集合的搜索空间,从而基于比特移位方法提出了循环矩阵的构造方法。考虑非零域元素的列赋值与矩阵秩之间的关系,选取Tanner图中没有长度为4的环的循环矩阵,基于非零域元素的列赋值思想提出了不同阶数、不同码率的多元LDPC码构造方法。数值仿真结果表明,与基于PEG算法构造的二元LDPC码比较,所构造的多元LDPC码在BPSK调制方式下在误码字率10–5附近有0.9 dB的增益;在与高阶调制相结合时,有更大的性能提升。此外,所构造的多元LDPC码在迭代5次与50次下的性能几乎一致,这为低时延高可靠通信提供了一种有效的候选编码方案。