Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cambridge University Press eBooks

Linear Codes

Ron M. Roth

Published Feb 23, 2006• 0 citations
Publisher

Abstract

In this chapter, we consider block codes with a certain structure, which are defined over alphabets that are fields. Specifically, these codes, which we call linear codes, form linear spaces over their alphabets. We associate two objects with these codes: a generator matrix and a parity-check matrix. The first matrix is used as a compact representation of the code and also as a means for efficient encoding. The parity-check matrix will be used as a tool for analyzing the code (e.g., for computing its minimum distance) and will also be part of the general framework that we develop for the decoding of linear codes. As examples of linear codes, we will mention the repetition code, the parity code, and the Hamming code with its extensions. Owing to their structure, linear codes are by far the predominant block codes in practical usage, and virtually all codes that will be considered in subsequent chapters are linear. Definition Denote by GF( q ) a finite ( Galois ) field of size q . For example, if q is a prime, the field GF( q ) coincides with the ring of integer residues modulo q , also denoted by ℤ q . We will see more constructions of finite fields in Chapter 3. An ( n, M, d ) code C over a field F = GF( q ) is called linear if C is a linear subspace of F n over F ; namely, for every two codewords c 1 , c 2 ∈ C and two scalars a 1 , a 2 ∈ F we have a 1 c 1 + a 2 c 2 ∈ C .

DOI
10.1017/cbo9780511808968.003

Related papers

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 eBooks•Nov 19, 2009•5 citations

A New Linear Programming Approach to Decoding Linear Block Codes

Kai Yang, Xiaodong Wang, Jon Feldman

In this paper, we propose a new linear programming formulation for the decoding of general linear block codes. Different from the original formulation given by Feldman, the number of total variables to characterize a parity-check constraint in our formulation is less than twice the degree of the corresponding check node. The equivalence between our new formulation and the original formulation is proven. The new formulation facilitates to characterize the structure of linear block codes, and leads to new decoding algorithms. In particular, we show that any fundamental polytope is simply the intersection of a group of the so-called minimum polytopes, and this simplified formulation allows us to formulate the problem of calculating the minimum Hamming distance of any linear block code as a simple linear integer programming problem with much less auxiliary variables. We then propose a branch-and-bound method to compute a lower bound to the minimum distance of any linear code by solving a corresponding linear integer programming problem. In addition, we prove that, for the family of single parity-check (SPC) product codes, the fractional distance and the pseudodistance are both equal to the minimum distance. Finally, we propose an efficient algorithm for decoding SPC product codes with low complexity and maximum-likelihood (ML) decoding performance.

IEEE Transactions on Information Theory•Feb 29, 2008•78 citations

Linear codes

Robert J. McEliece

Introduction: The generator and parity-check matrices We have already noted that the channel coding theorem (Theorem 2.4) is unsatisfactory from a practical standpoint. This is because the codes whose existence is proved there suffer from at least three distinct defects: (a) They are hard to find (although the proof of Theorem 2.4 suggests that a code chosen “at random” is likely to be pretty good, provided its length is large enough). (b) They are hard to analyze . (Given a code, how are we to know how good it is? The impossibility of computing the error probability for a fixed code is what led us to the random coding artifice in the first place!) (c) They are hard to implement . (In particular, they are hard to decode: the decoding algorithm suggested in the proof of Theorem 2.4–search the region S (y) for codewords, and so on–is hopelessly complex unless the code is trivially small.) In fact, virtually the only coding scheme we have encountered so far which suffers from none of these defects is the (7, 4) Hamming code of the Introduction. In this chapter we show that the Hamming code is a member of a very large class of codes, the linear codes , and in Chapters 7–9 we show that there are some very good linear codes which are free from the three defects cited above.

Cambridge University Press eBooks•Jul 15, 2004•0 citations

Linear codes

Robert J. McEliece

Introduction: The generator and parity-check matrices We have already noted that the channel coding Theorem 2.4 is unsatisfactory from a practical standpoint. This is because the codes whose existence is proved there suffer from at least three distinct defects: (a) They are hard to find (although the proof of Theorem 2.4 suggests that a code chosen “at random” is likely to be pretty good, provided its length is large enough). (b) They are hard to analyze . (Given a code, how are we to know how good it is? The impossibility of computing the error probability for a fixed code is what led us to the random coding artifice in the first place!) (c) They are hard to implement . (In particular, they are hard to decode: the decoding algorithm sugggested in the proof of Theorem 2.4—search the region S (y) for codewords, and so on—is hopelessly complex unless the code is trivially small.) In fact, virtually the only coding scheme we have encountered so far which suffers from none of these defects is the (7, 4) Hamming code of the Introduction. In this chapter we show that the Hamming code is a member of a very large class of codes, the linear codes , and in Chapters 7–9 we show that there are some very good linear codes which are free from the three defects cited above.

Cambridge University Press eBooks•Apr 18, 2002•0 citations

Definitions, Concepts, and Fundamental Characteristics of LDPC Codes

Juane Li, Shu Lin, Khaled Abdel-Ghaffar +2 more

In this chapter, we first present some definitions and concepts of matrices which are relevant for later developments of various algebraic-based and graph-theoretic-based constructions of LDPC codes. Then, we give a brief presentation of LDPC codes and characterize their fundamental structural properties that affect their error performance over the AWGNC and the BEC. Good coverage of the fundamentals of LDPC codes and the major iterative algorithms for decoding these codes can be found in [74, 97, 95]. Matrices and Matrix Dispersions of Finite Field Elements Let GF( q ) be a finite field with q elements, where q is a power of a prime [73]. GF( q ) is called a NB field if q ≠ 2 and a binary field if q = 2. A matrix A is said to be regular if every row has the same weight, called the row weight, every column has the same weight, called the column weight, and the row weight equals the column weight. If the row weight (or column weight) of a regular matrix A is w , we say that A has weight w and call it a weight- w regular matrix. For w ≠ 0, a weight- w regular matrix must be a square matrix. A binary weight-1 regular matrix is a permutation matrix (PM). It is clear that a weight- w regular matrix is the sum of w disjoint PMs. More generally, a rectangular matrix with constant column weight w c and constant row weight w r is said to be ( w c , w r ) -regular. A square matrix over GF( q ) is called a circulant if every row of the matrix is the cyclic-shift of the row above it one place to the right, and the top row is the cyclic-shift of the last row one place to the right. It is clear that a circulant is a regular matrix whose weight equals the weight of its top row. The top row of a circulant is called the generator of the circulant. A binary circulant of weight 1 is a binary circulant permutation matrix (CPM). It is clear that a weight- w circulant is the sum of w disjoint CPMs.

Cambridge University Press eBooks•Dec 1, 2016•0 citations

Codes based on dyadic matrices and their generalizations

Meraiah Martinez, Tefjol Pllaha, Christine A. Kelley

Codes based on algebraically structured parity check matrices are desirable in applications due to their compact representations, practical implementation advantages, and tractable decoder performance analysis. In this paper, we examine codes based on parity check matrices that are dyadic, $ n $-adic, or quasi-dyadic (QD), meaning the parity check matrix representation is block structured with dyadic matrices as blocks. Depending on the number of nonzero positions in the leading row of each matrix or block, these codes may be either low density or moderate density. We examine basic code properties of dyadic, $ n $-adic, and QD parity check codes, including reproducibility, bounds on the dimension and minimum distance, cycle structure of the corresponding Tanner graph, and their possible use in quantum code constructions.

Advances in Mathematics of Communications•Dec 16, 2024•3 citations
In this chapter, we consider block codes with a certain structure, which are defined over alphabets that are fields. Specifically, these codes, which we call linear codes, form linear spaces over their alphabets. We associate two objects with these codes: a generator matrix and a parity-check matrix. The first matrix is used as a compact representation of the code and also as a means for efficient encoding. The parity-check matrix will be used as a tool for analyzing the code (e.g., for computing its minimum distance) and will also be part of the general framework that we develop for the decoding of linear codes. As examples of linear codes, we will mention the repetition code, the parity code, and the Hamming code with its extensions. Owing to their structure, linear codes are by far the predominant block codes in practical usage, and virtually all codes that will be considered in subsequent chapters are linear. Definition Denote by GF( q ) a finite ( Galois ) field of size q . For example, if q is a prime, the field GF( q ) coincides with the ring of integer residues modulo q , also denoted by ℤ q . We will see more constructions of finite fields in Chapter 3. An ( n, M, d ) code C over a field F = GF( q ) is called linear if C is a linear subspace of F n over F ; namely, for every two codewords c 1 , c 2 ∈ C and two scalars a 1 , a 2 ∈ F we have a 1 c 1 + a 2 c 2 ∈ C .
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.
In this paper, we propose a new linear programming formulation for the decoding of general linear block codes. Different from the original formulation given by Feldman, the number of total variables to characterize a parity-check constraint in our formulation is less than twice the degree of the corresponding check node. The equivalence between our new formulation and the original formulation is proven. The new formulation facilitates to characterize the structure of linear block codes, and leads to new decoding algorithms. In particular, we show that any fundamental polytope is simply the intersection of a group of the so-called minimum polytopes, and this simplified formulation allows us to formulate the problem of calculating the minimum Hamming distance of any linear block code as a simple linear integer programming problem with much less auxiliary variables. We then propose a branch-and-bound method to compute a lower bound to the minimum distance of any linear code by solving a corresponding linear integer programming problem. In addition, we prove that, for the family of single parity-check (SPC) product codes, the fractional distance and the pseudodistance are both equal to the minimum distance. Finally, we propose an efficient algorithm for decoding SPC product codes with low complexity and maximum-likelihood (ML) decoding performance.
Introduction: The generator and parity-check matrices We have already noted that the channel coding theorem (Theorem 2.4) is unsatisfactory from a practical standpoint. This is because the codes whose existence is proved there suffer from at least three distinct defects: (a) They are hard to find (although the proof of Theorem 2.4 suggests that a code chosen “at random” is likely to be pretty good, provided its length is large enough). (b) They are hard to analyze . (Given a code, how are we to know how good it is? The impossibility of computing the error probability for a fixed code is what led us to the random coding artifice in the first place!) (c) They are hard to implement . (In particular, they are hard to decode: the decoding algorithm suggested in the proof of Theorem 2.4–search the region S (y) for codewords, and so on–is hopelessly complex unless the code is trivially small.) In fact, virtually the only coding scheme we have encountered so far which suffers from none of these defects is the (7, 4) Hamming code of the Introduction. In this chapter we show that the Hamming code is a member of a very large class of codes, the linear codes , and in Chapters 7–9 we show that there are some very good linear codes which are free from the three defects cited above.
Introduction: The generator and parity-check matrices We have already noted that the channel coding Theorem 2.4 is unsatisfactory from a practical standpoint. This is because the codes whose existence is proved there suffer from at least three distinct defects: (a) They are hard to find (although the proof of Theorem 2.4 suggests that a code chosen “at random” is likely to be pretty good, provided its length is large enough). (b) They are hard to analyze . (Given a code, how are we to know how good it is? The impossibility of computing the error probability for a fixed code is what led us to the random coding artifice in the first place!) (c) They are hard to implement . (In particular, they are hard to decode: the decoding algorithm sugggested in the proof of Theorem 2.4—search the region S (y) for codewords, and so on—is hopelessly complex unless the code is trivially small.) In fact, virtually the only coding scheme we have encountered so far which suffers from none of these defects is the (7, 4) Hamming code of the Introduction. In this chapter we show that the Hamming code is a member of a very large class of codes, the linear codes , and in Chapters 7–9 we show that there are some very good linear codes which are free from the three defects cited above.
In this chapter, we first present some definitions and concepts of matrices which are relevant for later developments of various algebraic-based and graph-theoretic-based constructions of LDPC codes. Then, we give a brief presentation of LDPC codes and characterize their fundamental structural properties that affect their error performance over the AWGNC and the BEC. Good coverage of the fundamentals of LDPC codes and the major iterative algorithms for decoding these codes can be found in [74, 97, 95]. Matrices and Matrix Dispersions of Finite Field Elements Let GF( q ) be a finite field with q elements, where q is a power of a prime [73]. GF( q ) is called a NB field if q ≠ 2 and a binary field if q = 2. A matrix A is said to be regular if every row has the same weight, called the row weight, every column has the same weight, called the column weight, and the row weight equals the column weight. If the row weight (or column weight) of a regular matrix A is w , we say that A has weight w and call it a weight- w regular matrix. For w ≠ 0, a weight- w regular matrix must be a square matrix. A binary weight-1 regular matrix is a permutation matrix (PM). It is clear that a weight- w regular matrix is the sum of w disjoint PMs. More generally, a rectangular matrix with constant column weight w c and constant row weight w r is said to be ( w c , w r ) -regular. A square matrix over GF( q ) is called a circulant if every row of the matrix is the cyclic-shift of the row above it one place to the right, and the top row is the cyclic-shift of the last row one place to the right. It is clear that a circulant is a regular matrix whose weight equals the weight of its top row. The top row of a circulant is called the generator of the circulant. A binary circulant of weight 1 is a binary circulant permutation matrix (CPM). It is clear that a weight- w circulant is the sum of w disjoint CPMs.
Codes based on algebraically structured parity check matrices are desirable in applications due to their compact representations, practical implementation advantages, and tractable decoder performance analysis. In this paper, we examine codes based on parity check matrices that are dyadic, $ n $-adic, or quasi-dyadic (QD), meaning the parity check matrix representation is block structured with dyadic matrices as blocks. Depending on the number of nonzero positions in the leading row of each matrix or block, these codes may be either low density or moderate density. We examine basic code properties of dyadic, $ n $-adic, and QD parity check codes, including reproducibility, bounds on the dimension and minimum distance, cycle structure of the corresponding Tanner graph, and their possible use in quantum code constructions.