Error Correcting Ability of Linear Block Codes

Rossitza Dodunekova, S.M. Dodunekov

Claude Berrou, Sandrine Vaton, Michel Jézéquel +1 more

A new method for computing the minimum distances of linear error-correcting codes is proposed and justified. Unlike classical techniques that rely on exhaustive or partial enumeration of codewords, this new method is based on the ability of the Soft-In decoder to overcome Error Impulse input patterns. It is shown that the maximum magnitude of the Error Impulse that can be corrected by the decoder is directly related to the minimum distance. This leads to a very fast algorithm to obtain minimum distances of any linear code whatever the block size and the code rate considered. In particular, the method can be advantageously worked out for turbo-like concatenated codes.

Juewei Wang, Chao Chen, Xiao Ma

In this paper, a new forward error correcting (FEC) scheme is proposed for optical fiber communication system, which takes the algebraic quasi-cyclic low-density parity-check (QC-LDPC) codes as the component codes in the block Markov superposition transmission (BMST) system. The excellent error-correction ability of the algebraic QC-LDPC codes is then further improved by the use of BMST coding. The encoding algorithm and the two-stage decoding algorithm are also presented, both having linear complexity. It is predicted that, for the simulated high-rate codes, the frame error rate (FER) can be lower than 10−17in the high signal-to-noise (SNR) region according to the numerical results. The excellent performance in error-correction and decoding latency suggests that the proposed scheme may find applications in optical fiber communications.

Abdullah A. Hashim

Sarah J. Johnson

Introduction In this chapter we introduce low-density parity-check (LDPC) codes, a class of error correction codes proposed by Gallager in his 1962 PhD thesis 12 years after error correction codes were first introduced by Hamming (published in 1950). Both Hamming codes and LDPC codes are block codes: the messages are broken up into blocks to be encoded at the transmitter and similarly decoded as separate blocks at the receiver. While Hamming codes are short and very structured with a known, fixed, error correction ability, LDPC codes are the opposite, usually long and often constructed pseudo-randomly with only a probabilistic notion of their expected error correction performance. The chapter begins by presenting parity bits as a means to detect and, when more than one is employed, to correct errors in digital data. Block error correction codes are described as a linear combination of parity-check equations and thus defined by their parity-check matrix representation. The graphical representation of codes by Tanner graphs is presented and the necessary graph theoretic concepts introduced. In Section 2.4 iterative decoding algorithms are introduced using a hard decision algorithm (bit flipping), so that the topic is developed first without reference to probability theory. Subsequently the sum–product decoding algorithm is presented. This chapter serves as a self-contained introduction to LDPC codes and their decoding. It is intended that the material presented here will enable the reader to implement LDPC encoders and iterative decoders.

David A. Huffman