Error detection and correction techniques are conventionally used to preserve integrity of data in computing and communication systems. Such techniques are extensively used to achieve reliable data storage and transfer in numerous applications comprising digital video, communication and storage in media devices and computers.
Error detection techniques enable the detection of errors caused by noise, interference or other impairments during the transmission of data from a transmitter to a receiver. Exemplary error detection techniques comprise repetition codes, parity bits and cyclic redundancy checks.
Error correction techniques not only enable the detection of errors but also reconstruction of the original error-free data. Exemplary error correction techniques comprise automatic repeat requests and forward error correcting codes.
Encoding process using error correcting codes (ECCs) is based on the addition of a redundant data to the original information data. The redundancy allows a receiver to detect and possibly correct transmission errors without requiring retransmissions of original data.
Existing error correcting codes comprise linear codes according to which any linear combination of a codeword is also a codeword. Linear codes are generally partitioned into ‘block codes’ and ‘convolutional codes’. Block codes process blocks of data of a fixed size while convolutional codes process data symbol-by-symbol. Linear block codes are widely used because they are less complex and easier to implement than convolutional codes. Exemplary linear block codes comprise Hamming codes, Reed-Solomon codes, Turbo codes and low-density parity-check (LDPC) codes.
A linear block code of length n and rank k encodes a block of symbols of length k into a vector, called ‘codeword’, of length n>k, by adding n−k redundancy symbols called ‘parity symbols’. The aim of the extra parity symbols is to detect and possibly correct any error that occurred during the transmission. Such codes may be represented using a ‘codebook’, a ‘matrix’ or a ‘graph’ representation.
The codebook representation defines the dictionary of allowable codewords and the linear space to which they belong. For example, for linear codes constructed on Galois fields of order q≥2, noted GF(q), the symbols comprised in a codeword take values in GF(q). A codeword is thus a vector of n symbols that belong each to GF(q). The code is binary if the symbols belong to GF(2). In contrast, when q>2, the code is said non-binary.
The matrix representation of a linear block code defines a generator matrix, generally denoted by G, and a parity-check matrix, generally denoted by H, linked by the relation G·Ht=0. Entries of the generator and parity-check matrices belong to the field over which is constructed the code. The parity-check matrix defines the parity-check constraints designed to be satisfied by the codewords. In particular, non-zero entries of each row of the parity-check matrix define a parity-check equation to be satisfied by any codeword.
Linear block codes may be equivalently represented by a bipartite graph, termed ‘Tanner graph’. Such representation comprises two sets of nodes: a first set of nodes referred to as ‘variable nodes’ and a second set of nodes referred to as ‘check nodes’. Variable nodes and check nodes are linked together by paths (hereinafter referred to as “edges”). Variable nodes and check nodes form processing units. Each variable node is associated with a column of the parity-check matrix. Each check node is associated with a row of the parity-check matrix, i.e. with a parity-check equation. The connections between variable nodes and check nodes are determined by the non-zero entries of the parity-check matrix. In particular, LDPC codes are specified by sparse parity-check matrices comprising a number of zero entries greatly higher than the number of non-zero entries. The corresponding Tanner graphs are generally characterized by a small number of edges. Such a property provides considerable advantages in terms of the computational complexity required for the decoding.
An iterative decoder may be used to decode data encoded using a linear block error correcting code. Given the channel output in a communication channel or a received sequence of symbols, an iterative decoder processes a signal during multiple iterations bringing it, at each iteration, closer to the original transmitted codeword.
Iterative decoding algorithms for linear block error correcting codes use the Tanner graph representation of the underlying code. Generally, each node in the Tanner graph maps to a processing unit in the hardware and/or software implementation. The iterative decoding process consists accordingly in exchanging messages between the variable node processing units and check node processing units and vice-versa via the different paths in the Tanner graph to estimate the most reliable codeword from the noisy received sequence of symbols. Each variable node processing unit or check node processing unit receives input messages from the corresponding connected nodes in the graph and delivers, after processing the input messages, output messages to at least one processing unit corresponding to a connected node in the Tanner graph.
The iterative decoding process comprises an initialization step during which the messages to be delivered by the variable node processing units are initialized from the channel output information. The exchange of messages involving the variable nodes and the check nodes is then performed iteratively. The decoding stops either if all parity-check constraints are satisfied, returning thus the decoded codeword, or by reaching a maximum number of iterations without meeting all parity check constraints.
The exchanged messages between the variable node and check node processing units carry representative information on the symbols. For example, in hard-decision decoding, exchanged messages may carry the value of the symbols. In soft-decision decoding, the symbols and metrics measuring their reliabilities (also referred to as ‘reliability metrics’) may be passed between the different processing units. The reliability metrics of a symbol may be for example its probability density function, measuring the probabilities that the symbol is equal to each value of GF(q).
In case of binary codes, a message is a vector comprising two values representative of the bit ‘0’ and the bit ‘1’. In case of non-binary codes constructed over Galois fields GF(q) with q>2, a message is a vector comprising q values representative of the symbols that belong to GF(q). In addition, in soft-decision decoding, a message is a vector comprising q pairs of symbols and their reliability metrics.
Early iterative decoding algorithms were designed for binary codes and apply to binary LDPC codes. They are the ‘sum-product’ algorithm (also known as ‘belief propagation’ or ‘message passing’ algorithm) and the ‘min-sum’ algorithm disclosed both in “N. Wiberg, H-A. Loeliger, and R. Kotter, Codes and Iterative Decoding on General Graphs, European Transactions on Telecommunications and Related Technologies, special issue on Turbo Coding, June 1995”. They provide near-optimal performance in terms of error decoding probability.
Decoding of non-binary linear block codes including non-binary LDPC codes can be also performed using iterative algorithms. Inspired by the sum-product algorithm, the ‘q-ary sum-product’ algorithm has been first proposed in “M. Davey and D. MacKay, Low-density parity check codes over GF(q), IEEE Communications Letters, vol. 2, no. 6, pages 165-167, June 1998”. The complexity of the q-ary algorithm was too high to be applied in hardware implementations. To overcome this limitation, several solutions have been developed targeting mainly the reduction of the computational complexity at the check node processing units, which involves 0(q2) operations per unit, the major part of the computational complexity of the decoding process.
First solutions have been independently disclosed in “D. J. C. Mackay and M. Davey, Evaluation of Gallager Codes for Short Block Length and High Rate Applications, In Proceedings of IMA Workshop on Codes, Systems and Graphical Models, 1999” and “L. Barnault and D. Declercq, Fast decoding algorithm for LDPC over GF(q), In Proceedings of IEEE Information Theory Workshop, pages 70-73, April 2003”. They consist in versions of the q-ary algorithm in the frequency-domain using Fourrier Transform enabling for a computational complexity reduction.
Other logarithm domain approaches were developed enabling for more reduction of the computational complexity by transforming product operations to simple summation operations. The reliability metrics passed during the messages exchange are in this case expressed in the logarithm scale. Main results in this avenue comprise the ‘max-log-map’ turbo codes decoder disclosed in “H. Sadjadpour, Maximum A Posteriori Decoding Algorithms For Turbo Codes, In Proceedings of SPIE, vol. 4045, 2000” and the ‘extended min-sum’ (EMS) algorithm and ‘min-max algorithm’ for non-binary LDPC codes decoding.
In addition to the computation in the log-domain, the EMS algorithm applies message sorting and truncation to further reduce the computational complexity and memory requirements at check node processing units. Accordingly, each message (vector of q components) delivered to a check node processing unit is first sorted according to an order of the reliability metrics associated with the q symbols comprised in the message. Then, the sorted message is truncated such that only a number N<<q of components is kept and processed by the check node processing unit receiving the message as input. Message truncation is performed such that the most reliable symbols are retained to contribute in the computation of the output messages delivered by a check node processing unit. For a detailed description on the EMS algorithm, one can refer to the article “D. Declercq and M. Fossorier, Decoding algorithms for non-binary LDPC codes over GF, IEEE Transactions on Communications, vol, 55, no. 4, pages 633-643, April 2007”.
The min-max algorithm is disclosed for example in “V. Savin, Min-max decoding for non-binary LDPC codes, In Proceedings of IEEE International Symposium on Information Theory, pages 960-964, July 2008”. The Min-max algorithm is similar to the EMS algorithm. The only difference between them is that the min-max algorithm replaces the sum operations in the check node processing by max operations.
The computation of output messages at the level of the check node processing units from the sorted and truncated input messages can be performed according to various architectures. For example, a forward-backward architecture may be used to divide up the computations performed by a single check node processing unit into multiple computations involving multiple elementary check node processing units. Each elementary check node processing unit processes two or more input messages to generate intermediary results that are subsequently used by remaining elementary check node processing units in later stages. Exemplary algorithms for elementary check node processing are the ‘Bubble check’ algorithm and its improved version known as ‘L-Bubble check’ disclosed respectively in “E. Boutillon and L. Conde-Canencia, Bubble check: a simplified algorithm for elementary check node processing in extended min-sum non-binary LDPC decoders, Electronics Letters, vol. 46, no. 9, pp. 633-634, April 2010” and “E. Boutillon, L. Conde-Canencia, and A. Al Ghouwayel, Design of a GF(64)-LDPC Decoder based on the EMS algorithm, IEEE Transactions on Circuits and Systems, vol. 60, no. 10, pages 2644-2656, October 2013”. The Bubble-check and L-Bubble check algorithms are in addition based on a reduction of the search space of the best intermediary results computed by an elementary check node processing unit from two input messages.
In another example, a recently developed architecture based on syndrome calculation may be used at check node processing units. Accordingly, the computation of output messages from the sorted and truncated input messages is performed in two steps. In the first step, the check node processing unit computes a set of values termed ‘syndromes’ involving all input messages. In a second step, a decorrelation operation is performed. In order to compute an output message to be delivered to a variable node processing unit, the contribution of the input message previously received from this variable node processing unit is cancelled from the computed syndromes through the decorrelation operation. The syndrome-based architecture is disclosed in “P. Schlafer, N. When, M. Alles, T. Lehnigk-Emden, and E. Boutillon, Syndrome based check node processing of high order NB-LDPC decoders, In Proceedings of the International Conference on Telecommunications, pages 156-162, April 2015” and “P. Schlafer, et al., A new Architecture for High Throughput, Low Latency NB-LDPC Check Node Processing, In Proceedings of IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, August 2015”. Syndrome-based check node processing allows an efficient parallel computation for higher-order Galois fields.
LDPC codes are very efficient linear block codes that can provide high transmission rates that approach the channel capacity, i.e. the theoretical maximum amount of information that can be transmitted over a communication channel. LDPC codes are finding expanding use in various applications including digital video broadcasting (DVB), long-haul optical communications, wireless local area network communications (e.g. standardized in Wi-Fi 802.11) and radio communications (3G, 4G/LTE, 5G and beyond).
Non-binary LDPC codes are particularly advantageous in applications requiring a high spectral efficiency. In addition, when the code length is moderate, non-binary LDPC codes can achieve better error-correcting performance than binary codes at the cost of higher decoding complexity. As the length of the code and/or the size of the field over which is constructed the code increases, the complicated computations in the check node processing and the large memory requirements put obstacles to efficient hardware implementations. Such implementations require excessive silicon area, making the decoder considerably expensive for practical designs. There is accordingly a need to reduce the computational complexity of the check node processing units for decoding non-binary linear block codes.