| |
Abstract
Two approaches to the analysis of low-density parity-check (LDPC) codes were presented which consisted of the selected code approach and the ensemble approach. The iterative decoding algorithms for the two families of LDPC codes were analyzed. The problem of proving that the iteratively decoded symbols met Shannon's condition was overcome by eliminating the symbols participating in short cycles. ...
Note (first note only)
Low-density parity-check (LDPC) codes;
|
| |
Abstract
A new class of rate 1/2 convolutional codes called strongly MDS convolutional codes are introduced and studied. These are codes having optimal column distances. Properties of these codes are given and a concrete construction is provided. ...
|
| |
Abstract
The weight of a code is the number of coordinate positions where no codeword is zero. The rth minimum weight d<sub>r</sub> is the least weight of an r-dimensional subcode. Wei and Yang gave a conjecture about the minimum weights for some product codes. In this correspondence, we will find a relation between product codes and the Segre embedding of a pair of projective systems, and we use this to prove the conjecture. ...
Note (first note only)
Product codes;Weight hierarchy;Projective system;Serge embedding;
|
| |
Abstract
We use projective multisets (projective systems) to find upper bounds on the weight hierarchies for a special class of codes, namely the extremal non-chain codes. Several code constructions exist meeting the bounds with equality. ...
Note (first note only)
Projective multisets;Upper bounds;Nonchain codes;Linear q-ary code;Hamming weight;Extremal nonchain difference sequence;
|
| |
Abstract
The relation between product codes and projective multisets is addressed. A lower bound on the greedy weights of product codes is given and demonstrated. ...
Note (first note only)
Product codes;Projective multisets;Greedy weights;Lower bounds;Linear codes;
|
| |
Abstract
Separating codes find applications in many fields including automata theory and digital fingerprinting. It is known that the Kerdock code of sufficient order is (2, 1)- and (2, 2)-separating, but the separating weight is only known by a lower bound due to Sagalovich. In this correspondence, we prove that the lower bound on the (2, 1)-separating weight is met with equality. © 2004 IEEE. ...
Note (first note only)
Kerdock code;Fingerprinting;Linear codes;Separating systems;
|
| |
IEEE International Symposium on Information Theory - Proceedings (2004)
Abstract
Collusion-secure codes are used in digital finger-printing and traitor tracing. Scattering codes were recently introduced by Sebe and Domingo-Ferrer, and used to contstruct a family of codes allegedly collusion-secure against three pirates. We prove that their codes are insecure against optimal pirate strategies, and we present a new secure construction. ...
Note (first note only)
Fingerprinting;Codewords;Traitor tracing;
|
| |
Note (first note only)
Kasami codes;Support weight distribution;
|
| |
Abstract
The combinatorial concept of separating systems has numerous applications, such as automata theory, digital fingerprinting, group testing, and hashing. In this correspondence, we derive upper bounds on the size of codes with various separating properties. ...
Note (first note only)
Hashing;Separating system;Superimposed code;
|
| |
Abstract
A greedy 1-subcode is a one-dimensional subcode of minimum (support) weight. A greedy r-subcode is an r-dimensional subcode with minimum support weight under the constraint that it contain a greedy (r - 1)-subcode. The r-th greedy weight e<sub>r</sub> is the support weight of a greedy r-subcode. The greedy weights are related to the weight hierarchy. We use recent results on the weight hierarchy of product codes to develop a lower bound on the greedy weights of product codes. ...
Note (first note only)
Product code;Projective multiset;Weight hierarchy;Segre embedding;Greedy weight;
|
| |
Applicable Algebra in Engineering, Communications and Computing, Vol. 10, No. 1. (1999)
Abstract
A maximum distance separable (MDS) block code is a linear code whose distance is maximal among all linear block codes of rate k/n. It is well known that MDS block codes do exist if the field size is more than n. In this paper we generalize this concept to the class of convolutional codes of a fixed rate k/n and a fixed code degree $\δ$. In order to achieve this result we will introduce a natural upper bound for the free ...
|
| |
Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Vol. 15 (2004)
Abstract
We present several new algorithms for detecting short fixed length cycles in digraphs. The new algorithms utilize fast rectangular matrix multiplication algorithms together with a dynamic programming approach similar to the one used in the solution of the classical chain matrix product problem. The new algorithms are instantiations of a generic algorithm that we present for finding a directed C<sub>k</sub>, i.e., a directed cycle of length k, in a digraph, for any fixed k greater than or equal 3. This algorithm ...
Note (first note only)
Matrix multiplication algorithms;Polyalgorithmic factors;
|
| |
Abstract
This paper presents a simple construction of a class of LDPC codes generalizing [BHS01] and gives necessary and sufficient, easy to implement, conditions for avoiding 2m cycles, m greater than or equal 2. The parity check matrix is formed by square blocks, with each block a sum of three permutation matrices, chosen such that the block is (3, 3) regular. The resulting codes have rate (s - 1)/s. ...
|
| |
Abstract
In this correspondence we present a special class of quasi-cyclic low-density parity-check (QC-LDPC) codes, called block-type LDPC (B-LDPC) codes, which have an efficient encoding algorithm due to the simple structure of their parity-check matrices. Since the parity-check matrix of a QC-LDPC code consists of circulant permutation matrices or the zero matrix, the required memory for storing it can be significantly reduced, as compared with randomly constructed LDPC codes. We show that the girth of a QC-LDPC code is upper-bounded by a ...
Note (first note only)
Fast encoding;Low-density parity-check (LDPC) codes;Quasi-cyclic codes;Block cycle;Circulant permutation matrix;Efficient encoding;
|
| |
Abstract
We construct an incidence structure using certain points and lines in finite projective spaces. The structural properties of the associated bipartite incidence graphs are analyzed. These n × n bipartite graphs provide constructions of C<sub>6</sub>-free graphs with Ω(n<sup>4/3</sup>) edges, C<sub>10</sub>-free graphs with Ω(n<sup>6/5</sup>) edges, and Θ(7,7,7)-free graphs with Ω(n<sup>8/7</sup>) edges. Each of these bounds is sharp in order of magnitude. © 2005 wiley Periodicals, Inc. ...
|
| |
Abstract
We present a new class of systematic, time-invariant, convolutional encoders suitable for low delay burst erasure correction. Specifically, we show that the new encoders have the shortest possible decoding delay required to correct all bursts of a given length with a fixed redundancy. By comparing the new encoders to maximum distance separable (MDS) codes, we show that the latter generally require either more redundancy or more delay to correct bursts of a given length. In addition, we show that the new ...
|
| |
Abstract
LT codes are the first realization of a class of erasure codes called universal erasure codes. LT codes are universal in the sense that they are simultaneously near optimal for every erasure channel and they are very efficient as the data length grows. The key to the design and analysis of the LT codes is the introduction and analysis of the LT process. A full analysis of the behavior of the LT process using first principles of probability theory precisely captures ...
|
| |
Abstract
We derive upper bounds on the number of errors that can be corrected by list decoding of maximum-distance separable (MDS) codes using small lists. We show that the performance of Reed-Solomon (RS) codes, for certain parameter values, is limited by worst case codeword configurations, but that with randomly chosen codes over large alphabets, more errors can be corrected. ...
|
| |
IEEE International Symposium on Information Theory - Proceedings (2004)
Abstract
A new method is given to construct low-density parity check codes the graphs of which are of designed girth. We give examples to illustrate the new method, and also present performance diagrams that suggest that these codes are as good as random codes in low SNR, and preferable to random codes at higher SNR. ...
|
| |
Abstract
In this correspondence, the construction of low-density parity-check (LDPC) codes from circulant permutation matrices is investigated. It is shown that such codes cannot have a Tanner graph representation with girth larger than 12, and a relatively mild necessary and sufficient condition for the code to have a girth of 6, 8, 10, or 12 is derived. These results suggest that families of LDPC codes with such girth values are relatively easy to obtain and, consequently, additional parameters such as the minimum ...
|
| |
IEEE International Conference on Communications, Vol. 2 (2004)
Abstract
A modification of Blahut algorithm is proposed for decoding of Reed-Solomon codes beyond half the minimum distance. An effective method is offered for the searching of unknown discrepancies needed for analytical continuation of the Berlekamp-Massey algorithm through two additional iterations. This reduces the search time compared to Blahut algorithm considerably. An architecture of a searcher for unknown discrepancies is given. The coding gain and implementation complexity of the proposed algorithm is shown for some practical codes. ...
|
| |
Abstract
We consider Gallager's soft-decoding (belief propagation) algorithm for decoding low-density parity-check (LDPC) codes, when applied to an arbitrary binary-input symmetric-output channel. By considering the expected values of the messages, we derive both lower and upper bounds on the performance of the algorithm. We also derive various properties of the decoding algorithm, such as a certain robustness to the details of the channel noise. Our results apply both to regular and irregular LDPC codes. ...
|
| |
Abstract
This paper explores relationships between optimal erasure-burst-correcting convolutional codes, arrays of integers within which all submatrices whose upper left corner lies on a certain boundary have determinant one, and enumerations of certain parts within such arrays. ...
|
| |
Abstract
We derive upper bounds on the maximum achievable rate of low-density parity-check (LDPC) codes used over the binary erasure channel (BEC) under Gallager's decoding algorithm, given their right-degree distribution. We demonstrate the bounds on the ensemble of right-regular LDPC codes and compare them with an explicit left-degree distribution constructed from the given right degree. © 2004 IEEE. ...
|
| |
Abstract
We consider uni-parametric LDPC decoding schemes, i.e., the class of decoding algorithms for which an extrinsic information transfer (EXIT) chart analysis of the decoder is exact. We treat the general case of code design for a desired convergence behavior and provide necessary conditions and sufficient conditions that the EXIT chart of the maximum rate low-density parity-check code must satisfy. Our results generalize some of the existing results for the binary erasure channel: our results apply to all uni-parametric decoding schemes and ...
Note (first note only)
Low density parity check (LDPC) codes;Extrinsic information transfer (EXIT) chart;Binary erasure channel;Uni-parametric decoding;Monotonic decoders;
|
| |
Abstract
The Moore-Penrose inverse of a real matrix having no square submatrix with two or more diagonals is described in terms of bipartite graphs. For such a matrix, the sign of every entry of the Moore-Penrose inverse is shown to be determined uniquely by the signs of the matrix entries; i.e., the matrix has a signed generalized inverse. Necessary and sufficient conditions on an acyclic bipartite graph are given so that each nonnegative matrix with this graph has a nonnegative Moore-Penrose inverse. ...
Note (first note only)
Moore-Penrose inverse;Bipartite graph;Sign pattern;Signed generalized inverse;Nearly reducible matrix;Minimally strongly connected digraph;
|
| |
Abstract
Extrinsic information transfer (EXIT) charts are a tool for predicting the convergence behavior of iterative processors for a variety of communication problems. A model is introdueed that applies to decoding problems, including the iterative decoding of parallel concatenated (turbo) codes, serially concatenated codes, low-density parity-check (LDPC) codes, and repeat-accumulate (RA) codes. EXIT functions are defined using the model, and several properties of such functions are proved for erasure channels. One property expresses the area under an EXIT function in terms of ...
|
