CRC Press eBooks

An Introduction to LDPC Codes

Bane Vasic, Erozan M. Kurtas

Published Nov 9, 2004• 15 citations

Abstract

Low-density parity-check (LDPC) codes are a class of linear block codes which provide near-capacity performance on a large collection of data transmission and storage channels while simultaneously admitting implementable decoders. LDPC codes were first proposed by Gallager in his 1960 doctoral dissertation [1] and were scarcely considered in the 35 years that followed. One notable exception is the important work of Tanner in 1981 [2] in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called Tanner graphs. The study of LDPC codes was resurrected in the mid1990s with the work of MacKay, Luby, and others [3-5] who noticed, apparently independently of the work of Gallager, the advantages of linear block codes which possess sparse (low-density) parity-check matrices.

DOI: 10.1201/9780203490310-39

Related papers

Low-Density Parity-Check Codes

W.E. Ryan, Shu Lin

Low-density parity-check (LDPC) codes are a class of linear block codes with implementable decoders, which provide near-capacity performance on a large set of data-transmission and data-storage channels. LDPC codes were invented by Gallager in his 1960 doctoral dissertation and were mostly ignored during the 35 years that followed. One notable exception is the important work of Tanner in 1981, in which Tanner generalized LDPC codes and introduced a graphical representation of LDPC codes, now called a Tanner graph. The study of LDPC codes was resurrected in the mid 1990s with the work of MacKay, Luby, and others [3–6], who noticed, apparently independently of Gallager's work, the advantages of linear block codes with sparse (low-density) parity-check matrices. This chapter introduces LDPC codes and creates a foundation for further study of LDPC codes in later chapters. We start with the fundamental representations of LDPC codes via parity-check matrices and Tanner graphs. We then learn about the decoding advantages of linear codes that possess sparse parity-check matrices. We will see that this sparseness characteristic makes the code amenable to various iterative decoding algorithms, which in many instances provide near optimal performance. Gallager of course recognized the decoding advantages of such low-density parity-check codes and he proposed a decoding algorithm for the BI-AWGNC and a few others for the BSC. These algorithms have received much scrutiny in the past decade, and are still being studied.

Cambridge University Press eBooksSep 17, 20096 citations

Low-density parity-check codes

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.

Cambridge University Press eBooksNov 19, 20095 citations

Performance evaluation of low-density parity-check codes

Paul Lauder

LDPC codes were first introduced by Robert Gallager in 1960. Due to the complexity of the codes and the limitations of the then rudimentary computer resources the codes were neglected as a viable form of FEC. LDPC codes were rediscovered by Tanner in 1981 when he generalized the codes and provided a means of graphical representation of LDPC codes. LDPC codes were again neglected until the work of MacKay et al in the mid to late 1990’s resurrected interest in the codes when they were discovered to out perform the then premium Turbo codes. This dissertation specifically describes the process of encoding and decoding LDPC codes and demonstrates the performance comparison between the various types of decoders in terms of bit error rate performance factors.

Jan 1, 20083 citations

Low-Density Parity-Check Codes

Enrico Paolini, Gianluigi Liva, Balázs Matuz +1 more

In Chapter 4, we introduce low-density parity-check (LDPC) codes, a class of powerful and efficient channel codes which admit a graphical representation based on sparse bipartite graphs. This chapter introduces fundamental concepts in LDPC coding theory and guides the reader through unstructured and structured LDPC code ensembles, including the important case of protograph-based LDPC code ensembles.

Cambridge University Press eBooksFeb 25, 20260 citations

Construction of Cycle-free LDPC Codes

Fengfan Yang

The linear block code is called a binary Low-Density Parity-Check code if whose parity-check matrix is a sparse matrix. For the features of parity-check matrix, a LDPC code can be illustrated by a Tanner graph. Cycles, especially short cycles in the Tanner graph, lead to inefficient decoding and prevent the decoding algorithm from converging to the optimal decoding result. In this paper, a simple algorithm of constructing four-cycle-free regular A(n,d_v,d_c)LDPC codes, d_v3, is introduced. And we analyse the relationship between the performance and the cycle.

Journal of Yunnan University for NationalitesJan 1, 20050 citations

Root LDPC Codes for Non Ergodic Transmission Channels

Tarique Inayat Bhutto

4 ABSTRACT Tremendous amount of research has been conducted in modern coding theory in the past few years and much of the work has been done in developing new coding techniques. Low density parity check (LDPC) codes are class of linear block error correcting codes which provide capacity performance on a large collection of data transmission and storage channels while Root LDPC codes in this thesis work are admitting implementable decoders with manageable complexity. Furthermore, work has been conducted to develop graphical methods to represent LDPC codes. This thesis implement one of the LDPC kind “Root LDPC code” using iterative method and calculate its threshold level for binary and non-binary Root LDPC code. This threshold value can serve as a starting point for further study on this topic. We use C++ as tool to simulate the code structure and parameters. The results show that non-binary Root LDPC code provides higher threshold value as compare to binary Root LDPC code.

Jan 1, 20110 citations