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.
New upper bounds on the rate of low-density parity-check (LDPC) codes as a function of the minimum distance of the code are derived. The bounds apply to regular LDPC codes, and sometimes also to right-regular LDPC codes. Their derivation is based on combinatorial arguments and linear programming. The new bounds improve upon the previous bounds due to Burshtein et al. It is proved that at least for high rates, regular LDPC codes with full-rank parity-check matrices have worse relative minimum distance than the one guaranteed by the Gilbert-Varshamov bound.
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.
The concepts of pseudocodeword and pseudoweight play a fundamental role in the finite-length analysis of LDPC codes. The pseudoredundancy of a binary linear code is defined as the minimum number of rows in a parity-check matrix such that the corresponding minimum pseudoweight equals its minimum Hamming distance. By using the value assignment of Chen and Kløve we present new results on the pseudocodeword redundancy of binary linear codes. In particular, we give several upper bounds on the pseudoredundancies of certain codes with repeated and added coordinates and of certain shortened subcodes. We also investigate several kinds of k-dimensional binary codes and compute their exact pseudocodeword redundancy.
It is now well known that the performance of a linear code
C under iterative decoding on a binary erasure channel (and other channels) is determined by the size of the smallest stopping set in the Tanner graph for
C. Several recent papers refer to this parameter as the \emph{stopping distance}
s of
C. This is somewhat of a misnomer since the size of the smallest stopping set in the Tanner graph for
C depends on the corresponding choice of a parity-check matrix. It is easy to see that
s≤d, where
d is the minimum Hamming distance of
C, and we show that it is always possible to choose a parity-check matrix for
C (with sufficiently many dependent rows) such that
s=d. We thus introduce a new parameter, termed the \emph{stopping redundancy} of
C, defined as the minimum number of rows in a parity-check matrix
H for
C such that the corresponding stopping distance
s(H) attains its largest possible value, namely
s(H)=d. We then derive general bounds on the stopping redundancy of linear codes. We also examine several simple ways of constructing codes from other codes, and study the effect of these constructions on the stopping redundancy. Specifically, for the family of binary Reed-Muller codes (of all orders), we prove that their stopping redundancy is at most a constant times their conventional redundancy. We show that the stopping redundancies of the binary and ternary extended Golay codes are at most 35 and 22, respectively. Finally, we provide upper and lower bounds on the stopping redundancy of MDS codes.
We address the problem of error correction by linear block codes under the assumption that the syndrome of a received vector is found with errors. We propose a construction of parity-check matrices which allow to solve the syndrome equation even with an erroneous syndrome, in particular, parity-check matrices with minimum redundancy, which are analogs of Reed-Solomon codes for this problem. We also establish analogs of classical coding theory bounds, namely the Hamming, Singleton, and Gilbert-Varshamov bounds. We show that the new problem can be considered as a generalization of the well-known Ulam’s problem on searching with a lie and as a discrete analog of the compressed sensing problem.