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

Chapman & Hall/CRC eBooks

Binary linear codes

Jürgen Bierbrauer

Published Oct 12, 2016• 0 citations
Publisher

Abstract

A binary code is linear if it is closed under addition. It is a basic fact from linear algebra that each linear code has a basis. Linear algebra applies to arbitrary fields. There is a general tendency to restrict attention to linear codes. One reason is that these are much easier to describe and to work with than codes in general. For a binary linear code, the minimum distance equals the minimum of the weights of nonzero codewords. Binary linear codes are particularly handy for block coding. In block coding the length of bitstrings is increased from k to n. That means that k/n of the bits sent through the channel represent pure information, whereas the rest is redundancy that we have cleverly introduced for the purposes of error correction.

DOI
10.1201/9781315371993-3

Related papers

Binary linear codes

Juergen Bierbrauer

Binary linear codes are particularly handy for block coding. This chapter describes how block coding works: the incoming data is divided into consecutive blocks of length k . In block coding the length of bitstrings is increased from k to n . The chapter compares the error probabilities with and without coding in a special case, based on the binary symmetric channel. It examines how to describe binary linear codes using either a generator matrix or a check matrix. It is natural to concentrate on the rows of these matrices. However, it will turn out very profitable to change the point of view and read these matrices column wise. The notion of an orthogonal array originated not in information theory but in statistics. It plays a central role in the design of experiments and has many more applications in theoretical computer science and cryptology.

Chapman & Hall/CRC eBooks•Oct 3, 2018•0 citations

On decoding algorithms for binary linear block codes

Bruce L. Montgomery

This dissertation investigates the complexity of minimum-distance decoding (MDD) algorithms for general binary linear block codes, and also investigates the use of such codes in constructing error correcting/detecting codes that are effective against both random and unidirectional errors. A new MDD algorithm is proposed, and its complexity is analyzed and compared to that of other such algorithms. The question of whether all good codes satisfy certain properties required for efficient implementation of the algorithm is also considered. The performance of decoding algorithms, with the information bit error rate as the criterion instead of the block error rate, is also studied. New decoding rules which can yield lower information bit error rates than the MDD rule are proposed and evaluated. A new class of binary codes is developed which corrects random errors and detects all unidirectional errors. These codes are obtained by appending a suffix to each codeword of a linear block code. To evaluate the efficiency of the new codes, a thorough comparison with the best previously obtained codes is made.

•Jan 1, 1987•0 citations

On the Pseudocodeword Redundancy of Binary Linear Codes

Jens Zumbrägel, Vitaly Skachek, Mark F. Flanagan

For a binary linear code, the pseudocodeword redundancy with respect to the additive white Gaussian noise channel, the binary symmetric channel, or the max-fractional weight is defined to be the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. It is shown that most codes do not have a finite pseudocodeword redundancy. Also, upper bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs, are provided. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Furthermore, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.

arXiv:1103.3641•IEEE Transactions on Information Theory•Apr 5, 2012•21 citations

Error-Correction Capability of Binary Linear Codes

Tor Helleseth, Torleiv Kløve, V.I. Levenshtein

The monotone structure of correctable and uncorrectable errors given by the complete decoding for a binary linear code is investigated. New bounds on the error-correction capability of linear codes beyond half the minimum distance are presented, both for the best codes and for arbitrary codes under some restrictions on their parameters. It is proved that some known codes of low rate are as good as the best codes in an asymptotic sense.

IEEE Transactions on Information Theory•Apr 1, 2005•30 citations

Pseudoredundancy for the Bit-Flipping Algorithm

Jens Zumbrägel

The analysis of the decoding failure rate of the bit-flipping algorithm has received increasing attention. For a binary linear code we consider the minimum number of rows in a parity-check matrix such that the bit-flipping algorithm is able to correct errors up to the minimum distance without any decoding failures. We initiate a study of this bit-flipping redundancy, which is akin to the stopping set, trapping set or pseudocodeword redundancy of binary linear codes, and focus in particular on codes based on finite geometries.

arXiv:2402.01403•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•1 citation

Error detection, correction and decoding

San Ling, Chaoping Xing

We saw in Chapter 1 that the purpose of channel coding is to introduce redundancy to information messages so that errors that occur in the transmission can be detected or even corrected. In this chapter, we formalize and discuss the notions of error-detection and error-correction. We also introduce some well known decoding rules, i.e., methods that retrieve the original message sent by detecting and correcting the errors that have occurred in the transmission. Communication channels We begin with some basic definitions. Definition 2.1.1 Let A = { a 1 , a 2 , …, a q } be a set of size q , which we refer to as a code alphabet and whose elements are called code symbols . (i) A q-ary word of length n over A is a sequence w = w 1 w 2 … w n with each w i ∈ A for all i . Equivalently, w may also be regarded as the vector ( w 1 , …, w n ). (ii) A q-ary block code of length n over A is a nonempty set C of q -ary words having the same length n . (iii) An element of C is called a codeword in C . (iv) The number of codewords in C , denoted by ∣ C ∣, is called the size of C . (v) The (information) rate of a code C of length n is defined to be (log q ∣ C ∣)/ n . (vi) A code of length n and size M is called an (n, M)-code .

Cambridge University Press eBooks•Feb 12, 2004•0 citations
A binary code is linear if it is closed under addition. It is a basic fact from linear algebra that each linear code has a basis. Linear algebra applies to arbitrary fields. There is a general tendency to restrict attention to linear codes. One reason is that these are much easier to describe and to work with than codes in general. For a binary linear code, the minimum distance equals the minimum of the weights of nonzero codewords. Binary linear codes are particularly handy for block coding. In block coding the length of bitstrings is increased from k to n. That means that k/n of the bits sent through the channel represent pure information, whereas the rest is redundancy that we have cleverly introduced for the purposes of error correction.
Binary linear codes are particularly handy for block coding. This chapter describes how block coding works: the incoming data is divided into consecutive blocks of length k . In block coding the length of bitstrings is increased from k to n . The chapter compares the error probabilities with and without coding in a special case, based on the binary symmetric channel. It examines how to describe binary linear codes using either a generator matrix or a check matrix. It is natural to concentrate on the rows of these matrices. However, it will turn out very profitable to change the point of view and read these matrices column wise. The notion of an orthogonal array originated not in information theory but in statistics. It plays a central role in the design of experiments and has many more applications in theoretical computer science and cryptology.
This dissertation investigates the complexity of minimum-distance decoding (MDD) algorithms for general binary linear block codes, and also investigates the use of such codes in constructing error correcting/detecting codes that are effective against both random and unidirectional errors. A new MDD algorithm is proposed, and its complexity is analyzed and compared to that of other such algorithms. The question of whether all good codes satisfy certain properties required for efficient implementation of the algorithm is also considered. The performance of decoding algorithms, with the information bit error rate as the criterion instead of the block error rate, is also studied. New decoding rules which can yield lower information bit error rates than the MDD rule are proposed and evaluated. A new class of binary codes is developed which corrects random errors and detects all unidirectional errors. These codes are obtained by appending a suffix to each codeword of a linear block code. To evaluate the efficiency of the new codes, a thorough comparison with the best previously obtained codes is made.
For a binary linear code, the pseudocodeword redundancy with respect to the additive white Gaussian noise channel, the binary symmetric channel, or the max-fractional weight is defined to be the smallest number of rows in a parity-check matrix such that the corresponding minimum pseudoweight is equal to the minimum Hamming distance of the code. It is shown that most codes do not have a finite pseudocodeword redundancy. Also, upper bounds on the pseudocodeword redundancy for some families of codes, including codes based on designs, are provided. The pseudocodeword redundancies for all codes of small length (at most 9) are computed. Furthermore, comprehensive results are provided on the cases of cyclic codes of length at most 250 for which the eigenvalue bound of Vontobel and Koetter is sharp.
The analysis of the decoding failure rate of the bit-flipping algorithm has received increasing attention. For a binary linear code we consider the minimum number of rows in a parity-check matrix such that the bit-flipping algorithm is able to correct errors up to the minimum distance without any decoding failures. We initiate a study of this bit-flipping redundancy, which is akin to the stopping set, trapping set or pseudocodeword redundancy of binary linear codes, and focus in particular on codes based on finite geometries.
We saw in Chapter 1 that the purpose of channel coding is to introduce redundancy to information messages so that errors that occur in the transmission can be detected or even corrected. In this chapter, we formalize and discuss the notions of error-detection and error-correction. We also introduce some well known decoding rules, i.e., methods that retrieve the original message sent by detecting and correcting the errors that have occurred in the transmission. Communication channels We begin with some basic definitions. Definition 2.1.1 Let A = { a 1 , a 2 , …, a q } be a set of size q , which we refer to as a code alphabet and whose elements are called code symbols . (i) A q-ary word of length n over A is a sequence w = w 1 w 2 … w n with each w i ∈ A for all i . Equivalently, w may also be regarded as the vector ( w 1 , …, w n ). (ii) A q-ary block code of length n over A is a nonempty set C of q -ary words having the same length n . (iii) An element of C is called a codeword in C . (iv) The number of codewords in C , denoted by ∣ C ∣, is called the size of C . (v) The (information) rate of a code C of length n is defined to be (log q ∣ C ∣)/ n . (vi) A code of length n and size M is called an (n, M)-code .