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

arXiv:2512.12591

Linear Binary Codes Correcting One or More Errors

Timofei Izhitskii

Published Dec 14, 2025• 0 citations
arXivHTMLPDF

Abstract

This paper examines linear binary codes capable of correcting one or more errors. For the single-error-correcting case, it is shown that the Hamming bound is achieved by a constructive method, and an exact expression for the minimal codeword length is derived. For the general case, a simple lower bound for the parameters of linear codes is derived from an analysis of the coset structure.

DOI
10.48550/arxiv.2512.12591

Related papers

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

Low-complexity error correction of Hamming-code-based LDPC codes

Victor Zyablov, Rolf Johannesson, Matea Lončar

Ensembles of binary random LDPC block codes constructed using Hamming codes as constituent codes are studied for communicating over the binary symmetric channel. These ensembles are known to contain codes that asymptotically almost meet the Gilbert-Varshamov bound. It is shown that in these ensembles there exist codes which can correct a number of errors that grows linearly with the code length, when decoded with a low-complexity iterative decoder, which requires a number of iterations that is a logarithmic function of the code length. The results are supported by numerical examples, for various choices of the code parameters.

Problems of Information Transmission•Jun 1, 2009•17 citations

Estimates of the bit error probabilities for linear block codes and symmetric binary-input memoryless channels

Vladimir B. Balakirsky

A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.

IEEE Information Theory Workshop (ITW)•Aug 27, 2003•1 citation

Binary linear codes

Jürgen Bierbrauer

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.

Chapman & Hall/CRC eBooks•Oct 12, 2016•0 citations

Lifting an $[n,k,d]$ Binary Linear Code to an $[[n,k,d]]$ Quantum Stabilizer Code

Thamadathil Aswanth, Navin Kashyap

The codeword stabilized (CWS) framework provides a systematic method for constructing quantum error correcting codes from a simple undirected graph and a classical code. When the underlying classical code is linear, the resulting quantum code is a stabilizer code. In this work, we investigate the conditions under which an arbitrary $[n,k,d]$ classical binary linear code can be lifted to an $[[n,k,d]]$ quantum stabilizer code using the CWS framework. We analyze the random CWS code constructed from a given $[n,k,d]$ binary linear code $\mathcal{C}$ and an Erdős-Rényi random graph $\mathrm{G}(n, \frac12)$. We establish a lower bound on the probability that the resulting quantum code preserves the minimum distance $d$ of the classical code. This probabilistic analysis yields a Gilbert-Varshamov-type condition on the $n,k,d$ parameters of the classical code that guarantees the existence of a graph resulting in a quantum code with the same $n,k,d$ parameters.

quant-pharXiv:2610.14192•Oct 13, 2026•0 citations

Upper Bound on Correcting Partial Random Errors

Ankita Gaur, Bhu Dev Sharma

Abstract Since coding has become a basic tool for practically all communication/electronic devices, it is important to carefully study the error patterns that actually occur. This allows correction of only partial errors rather than those which have been studied using Hamming distance, in non-binary cases. The paper considers a class of distances, SK-distances, in terms of which partial errors can be defined. Examining the sufficient condition for the existence of a parity check matrix for a given number of parity-checks, the paper contains an upper bound on the number of parity check digits for linear codes with property that corrects all partial random errors of an (n, k ) code with minimum SK-distance at least d. The result generalizes the rather widely used Varshamov-Gilbert bound, which follows from it as a particular case.

Cybernetics and Information Technologies•Sep 1, 2013•1 citation
This paper examines linear binary codes capable of correcting one or more errors. For the single-error-correcting case, it is shown that the Hamming bound is achieved by a constructive method, and an exact expression for the minimal codeword length is derived. For the general case, a simple lower bound for the parameters of linear codes is derived from an analysis of the coset structure.
Ensembles of binary random LDPC block codes constructed using Hamming codes as constituent codes are studied for communicating over the binary symmetric channel. These ensembles are known to contain codes that asymptotically almost meet the Gilbert-Varshamov bound. It is shown that in these ensembles there exist codes which can correct a number of errors that grows linearly with the code length, when decoded with a low-complexity iterative decoder, which requires a number of iterations that is a logarithmic function of the code length. The results are supported by numerical examples, for various choices of the code parameters.
A coset representation of the bit error probabilities for binary linear block codes and arbitrary symmetric memoryless channels is derived. Such a representation leads to simple upper bounds on the bit error probabilities for code components expressed via 2n code spectra, where n is the code length, and to a "bounded distance decoding" algorithm. The performance of the algorithm is illustrated for the (23,12) Golay code and a particular channel having non-binary output alphabet where it attains a sub-optimum performance.
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.
Lifting an [n,k,d][n,k,d][n,k,d] Binary Linear Code to an [[n,k,d]][[n,k,d]][[n,k,d]] Quantum Stabilizer Code
The codeword stabilized (CWS) framework provides a systematic method for constructing quantum error correcting codes from a simple undirected graph and a classical code. When the underlying classical code is linear, the resulting quantum code is a stabilizer code. In this work, we investigate the conditions under which an arbitrary [n,k,d][n,k,d][n,k,d] classical binary linear code can be lifted to an [[n,k,d]][[n,k,d]][[n,k,d]] quantum stabilizer code using the CWS framework. We analyze the random CWS code constructed from a given [n,k,d][n,k,d][n,k,d] binary linear code C\mathcal{C}C and an Erdős-Rényi random graph G(n,12)\mathrm{G}(n, \frac12)G(n,21​). We establish a lower bound on the probability that the resulting quantum code preserves the minimum distance ddd of the classical code. This probabilistic analysis yields a Gilbert-Varshamov-type condition on the n,k,dn,k,dn,k,d parameters of the classical code that guarantees the existence of a graph resulting in a quantum code with the same n,k,dn,k,dn,k,d parameters.
Abstract Since coding has become a basic tool for practically all communication/electronic devices, it is important to carefully study the error patterns that actually occur. This allows correction of only partial errors rather than those which have been studied using Hamming distance, in non-binary cases. The paper considers a class of distances, SK-distances, in terms of which partial errors can be defined. Examining the sufficient condition for the existence of a parity check matrix for a given number of parity-checks, the paper contains an upper bound on the number of parity check digits for linear codes with property that corrects all partial random errors of an (n, k ) code with minimum SK-distance at least d. The result generalizes the rather widely used Varshamov-Gilbert bound, which follows from it as a particular case.