Project topics and materials
Get Complete Project Material File(s) Now! »
Review of existing non-binary LDPC codes and compari-son with their binary counterparts
In 1962, Robert Gallager developed a new structure of error correction codes, based on the use of LDPC [15] matrices. However, this work was set aside for a while, since its decoding algorithm was too complex to be implemented at that time. With the introduction of TC by Berrou in 1993 [3], the first practical error correcting codes and decoders able to perform very close to channel capacity were proposed. In the light of the iterative decoding process of TCs, several researchers got interested in re-discovering LDPC codes in order to decode them with such decoding algorithms, mainly David Mackay in [4] and Michael Sipser in [35].
LDPC codes are block codes having sparse parity-check matrices. Usually, block codes are designed for short frame sizes, since their decoding algorithms are based on Maximum Likelihood (ML) decoding, whose complexity increases exponentially with the codeword size. On the contrary, due to the sparseness of their parity-check matrix, LDPC codes can be decoded using an iterative process. This helps reduce the decoding complexity, making decoders practically implementable, even for large block sizes. They have been the main competitors of TCs for many years. The iterative decoding for the LDPC codes is based on its graphical representation, known as bipartite graph or Tanner graph [36].
As an extension to the NB domain, NB-LDPC codes were first introduced in [19]. These codes have shown promising error correction capabilities, alongside with a reason-able hardware complexity for nowadays, making them of high importance to the coding research community.
Performance comparison of binary and non-binary LDPC codes
As shown in [37], the proposed NB-LDPC codes outperform their binary counterparts when combined with a binary modulation, for different coding rates. Fig. 1.2 shows the comparison of the designed NB-LDPC codes over GF(256) in [37] with protograph irregular binary LDPC codes [38]. Obviously, it is shown that NB-LDPC codes can outperform the binary codes with more than 0.25 dB in all the proposed scenarios.
Moreover, different studies were conducted in order to design NB-LDPC codes asso-ciated with high order modulations [39, 40, 41]. NB-LDPC codes were also shown to outperform their binary counterparts when mapped to high-oder modulations. The re-sults in [41] show interesting performance gains for non-binary codes over binary codes for high coding rates and with the use of high order modulation.
In Fig. 1.3, performance comparison between a NB-LDPC code over GF(256) with a binary LDPC is conducted over a rotated 256-QAM constellation. Obviously, NB-LDPC is shown to outperform the binary codes by almost 0.4 dB in the context of the high order modulation.
Preliminaries on the calculation in Galois fields
Definition: A Galois Field GF(q) is a finite field that contains q elements, with q = pm, where p is a prime number and m a positive integer. In practical coding applications, p is commonly taken equal to 2. A Galois field GF(2m) can be constructed using a polynomial m(x), called primitive polynomial, provided that:
1. the coefficients of m(x) belong to GF(2), i.e. are binary.
2. the degree of m(x) is m, which defines the order of the finite field.
3. m(x) is irreducible over GF(2).
The field GF(2m) can then be defined as the set of residues modulo m(x), i.e the set of all polynomials of degree n < m. If denotes a primitive element of the field, i.e is a non-zero root of the primitive polynomial m(x) (m() = 0), every non-zero element of GF(2m) can be written as k , k = 0 : : : 2m 1 and GF(2m)=f0;1;;2; :::;2m2g, with 2m1 = 1 since m(x) divides x2m1 + 1 and m() =0. In other words, the powers of a primitive element generate all the non-zero elements of GF(2m).
Taking GF(4) as an example, the only primitive polynomial of degree 2 is 2(x) = x2 + x + 1. Since the four elements of GF(4) can be written as polynomials with degree n < 2, they can be represented in the form a + b, where is the considered primitive element, while a and b belong to GF(2). Therefore, since 2() = 0, 2 = + 1 and GF(4) = f0;1;;2g can also be expressed as GF(4) = f0;1;;1 + g. Table 2.1 shows examples of primitive polynomials that can be used for the definition of different GF(q).
mbinar y convolutional and turbo codes: an intermediate design between binary and non-binary codes
In [31, 74], mbinar y turbo codes were designed based on the NB-CCs defined in [75]. In this proposal, m bits enter the convolutional code structure of memory elements, with m . The data bits are connected to the possible entries of the CC via a connection grid, which is defined jointly with the generator polynomial of the CC in order to design a code achieving a Hamming distance as high as possible.
The authors of [31] have stated several advantages that could be obtained with m binar y TCs based on the component encoders in Fig. 2.1:
1. Better convergence: in [76, 31], it was shown that the correlation is reduced when m binar y codes are defined with respect to binary codes, and this reduction is found to be interesting when m = 2. Double-binary codes [31, 74], defined with 2 input bits (m=2), have shown better convergence when compared to binary codes, due to lower correlation problems in the decoding process.
2. Larger minimum distance: a new degree of freedom is introduced in the mbinar y TCs, intra-symbol interleaving. When well designed, the total interleaving function, which is composed from an inter-symbol and an intra-symbol permutations, can help the code achieve high Hamming distances. Therefore, better performance can be expected.
3. Less sensitivity to puncturing: when high coding rates have to be achieved, mbinar y TCs offer the possibility of lower parity puncturing, which reduces the performance degradation when increasing the coding rate.
4. Reduced latency: obviously, TCs based on the convolutional codes of Fig. 2.1 perform the decoding of m bits at each trellis stage, and thus, lower latency can be achieved.
5. Robustness of the decoder: it is shown in [31] that the gap in performance between the reduced-complexity decoder and the full MAP decoder is reduced when mbinar y codes are introduced. The authors in [31] suppose that this property is due to the reduction of the number of trellis stages for the same information frame size K, and then the decoder can perform closer to the Maximum Likelihood (ML) decoder. Consequently, the design proposed in [31, 75] offers many coding advantages in comparison with binary TCs. Also, the performance of double-binary TCs, for different coding rates, was provided in [31] and they showed interesting gains when compared with binary TCs. These promising advantages and performance justified the interest of studying nonbinary TCs. The proposed codes in [75, 31] are not defined over rings, groups or fields, and data processing in their structures remains at the bit level. NB-TCs designed over algebraic structures, where information data are processed in the symbol domain, can offer more degrees of freedom and thus may yield better performance especially when mapped to their corresponding constellation as stated in Section 1.2.3.
Non-binary convolutional and turbo codes for impulsive noise channels
In [46], the design of NB-CCs over GF(4) is investigated. A structure similar to the one shown in Fig. 2.3 is used, with more than one memory element. The proposed structure is non-systematic and non-recursive, the data entries Ii are in the considered GF(q), and the generator polynomials a1 i , a2 i are defined in order to optimize the waterfall performance, targeting Physical-Layer Network Coding (PNC) over an impulsive conventional Two-Way Relay Channel (TWRC). In this paper, a comparison is conducted with 4-state binary convolutional codes. It is shown that NB-CCs outperform the binary codes by more than 1 dB. No further design clarifications are shown in this paper, as for instance the technique for the identification of the generator polynomials.
In [47], Zhao et al. have used the structure from [46] to design NB-TCs over GF(4). However, since the NB-CCs in [46] are non-recursive, they have proposed a modified structure of NB-CCs over GF(4) as shown in Fig. 2.6. This structure is systematic, with a feedback coefficient equal to 1. The feed-forward coefficients are and 2, where is a primitive element in GF(4).
Table of contents :
Contents
List of Figures
List of Tables
Abbreviations
Notations
Résumé de la thèse
Introduction
1 Channel coding and non-binary codes
1.1 Generalities on channel coding
1.1.1 Channel Capacity
1.1.2 Motivation for studying new error correcting codes
1.2 Capacity-approaching non-binary codes
1.2.1 Motivation for the study of non-binary codes
1.2.2 Review of existing non-binary LDPC codes and comparison with their binary counterparts
1.2.2.1 Construction of NB-LDPC codes over GF(q)
1.2.2.2 Performance comparison of binary and non-binary LDPC codes
1.2.3 Motivation for the study of non-binary turbo codes
1.2.3.1 Codes mapped to high-order modulations: an information theoretic approach
1.2.3.2 Comparison of CM and BICM capacities for high-order modulations
1.3 Turbo codes in a nutshell
1.3.1 Recursive Systematic Convolutional codes
1.3.2 Parallel concatenation of RSC codes
1.3.3 Puncturing turbo codes
1.3.4 Turbo code interleaver
1.3.4.1 Random interleaver
1.3.4.2 Partially Random interleaver
1.3.4.3 Algebraic interleaver
1.3.5 Distance spectrum of turbo codes
1.4 Conclusion
2 Design of convolutional codes over GF(q)
2.1 Preliminaries on the calculation in Galois fields
2.2 State of the art on non-binary convolutional and turbo codes
2.2.1 mbinar y convolutional and turbo codes: an intermediate design between binary and non-binary codes
2.2.2 Convolutional codes over rings
2.2.3 Turbo codes based on time-variant non-binary convolutional codes .
2.2.3.1 Parallel concatenation
2.2.3.2 Serial concatenation
2.2.4 Non-binary convolutional and turbo codes for impulsive noise channels
2.3 Proposed structures of non-binary recursive systematic convolutional codes
2.3.1 Structure of non-binary RSC code targeting low rate codes
2.4 Selection of the generator polynomials for memory-1 convolutional codes over GF(q)
2.4.1 Design Criterion
2.4.2 DC sequence enumeration and truncated distance spectrum calculation
2.4.3 Discussion on the impact of the constellation mapping
2.4.3.1 Case 1 – parameters of the code are constant and changes 43
2.4.3.2 Case 2 – is constant and the parameters of the code change 43
2.4.4 Search results for R = 1=2 NB-CCs over GF(q) combined with q- QAM, q= 4, 16, 64 and simulation results
2.4.5 Application to NB-CCs over GF(q) with code rates R < 1=2.
2.5 Constellation downsizing technique
2.6 Optimizing the NB-CC coefficients for binary modulations
2.7 Conclusion
3 Towards the design of non-binary turbo codes: interleaving, puncturing, union bound
3.1 Study of the influence of different interleaving techniques on NB-TCs
3.1.1 Random interleaver
3.1.2 S-random interleaver
3.1.3 ARP interleaver
3.1.4 Reducing the correlation effect in NB-TCs using ARP interleavers .
3.1.4.1 Minimizing the multiplicity of length-g correlation cycles .
3.1.4.2 Maximizing the information exchange between component decoders in the minimum correlation cycles
3.1.4.3 Minimizing the multiplicity of symbol couples in minimum correlation cycles
3.1.4.4 Numerical results
3.2 Puncturing NB-TCs
3.2.1 Symbol puncturing
3.2.2 Bit puncturing
3.3 Distance spectrum evaluation of NB-TCs and computation of the truncated union bounds
3.3.1 Union bounds formulation for NB codes
3.3.2 Identification of low-distance DC sequences for a NB-TC
3.3.2.1 Effect of short correlation cycles on the error events of NB-TCs
3.3.2.2 Error events resilient to interleaver spread
3.3.3 Estimation of the truncated distance spectrum of NB-TCs
3.3.3.1 Computation of the Euclidean distance of type-A sequences
3.3.3.2 Computation of the minimum achievable Euclidean distance of type-B sequences
3.3.3.3 Computation of the truncated union bound
3.3.4 Numerical results
3.4 Conclusion
4 Enhancing performance of non-binary turbo codes via symbol transformation
4.1 Modified structure of the NB turbo encoder
4.2 Symbol transformation design criterion
4.3 Application example 1: NB-TC defined over GF(64) and mapped to a 64-QAM constellation
4.3.1 Distance distribution in a 64-QAM constellation
4.3.2 Unequal error protection in a 64-QAM constellation
4.3.3 Proposed algorithm
4.4 Application example 2: NB-TC defined over GF(64) and mapped to a
4-QAM constellation
4.5 Results and discussion
4.5.1 Application example 1: NB-TC defined over GF(64) and mapped to a 64-QAM constellation
4.5.2 Application example 2: NB-TC defined over GF(64) and mapped to a 4-QAM constellation
4.6 Error correction performance of NB-TCs and comparison with state-of-theart codes
4.6.1 Comparison with binary turbo codes
4.6.1.1 Comparison with LTE TCs
4.6.1.2 Comparison with enhanced binary TCs
4.6.2 Comparison with binary LDPC codes
4.6.3 Comparison with NB-LDPC codes
4.6.4 Comparison with 5G-polar codes
4.6.5 Capacity achieving codes
4.7 Conclusion
5 Design of low complexity decoders for non-binary turbo codes
5.1 State of the art in low-complexity decoders for NB-LDPC codes
5.1.1 The belief propagation decoding algorithm
5.1.2 The extended min-sum algorithm
5.1.3 The bubble check algorithm
5.2 Min-Log-MAP decoding of NB-TCs and related complexity limitations
5.2.1 Algorithm description
5.2.2 Storage requirements of the Min-Log-MAP algorithm in the case of NB-TCs
5.2.3 Computational complexity of the decoding algorithm in the case of NB-TCs
5.3 Proposed low-complexity decoding algorithm for non-binary turbo codes .
5.3.1 Reduction of the storage requirements
5.3.1.1 Fixed-point representation of decoder data
5.3.1.2 Vector truncation of decoder parameters
5.3.2 Simplified min-sum processing for NB-TCs
5.3.2.1 Simplified integer array sorting by addresses
5.3.2.2 Reduced complexity decoding of NB-TCs
5.3.2.2.1 Preliminary complexity reduction step
5.3.2.2.2 Bubble processing
5.3.3 Computational complexity analysis
5.4 Simulation and complexity results
5.4.1 Simulation settings
5.4.2 Upper bound on computational complexity
5.4.3 Performance and complexity comparisons for NB-TCs using C1 as NB-CC
5.4.4 Performance and complexity comparisons for NB-TCs using C3 as NB-CC
5.4.5 Discussion
5.5 Conclusion
Conclusions and future works
List of publications
Bibliography
