The undetected error probability of CRC combined with an error-correcting code with bounded-distance decoding is considered. It is shown that to minimize this probability, the CRC polynomial should be matched to the code. In particular, good CRC polynomials reported in the literature for pure CRC schemes may not be good when combined with coding. Guidelines to choose a good CRC polynomial to be combined with a given code are provided.

Partial geometries form an interesting branch in combinatorial mathematics, and recently they have been shown to be very effective in the construction of LDPC codes with distinct geometric and algebraic structures. This paper presents three specific cyclic classes of partial geometries. Based on these three classes of partial geometries, three classes of LDPC codes and three classes of constant-weight codes are constructed. Codes in these two categories are either cyclic or quasi-cyclic. Designs and constructions of these codes are straightforward and flexible without a need for extensive computer search. It is shown that long high-rate LDPC codes constructed based on the three classes of cyclic partial geometries perform well over the additive white Gaussian noise channel (AWGNC) with iterative decoding algorithm based on belief propagation. They can achieve low error-rates without visible error-floor and their decoding converges rapidly. These LDPC codes also perform well over the binary erasure channel (BEC) and are very effective in correcting phased-bursts of erasures. Based on cyclic partial geometries, a special type of constant-weight codes, called balanced codes, can be constructed. The constant-weight codes constructed based on partial geometries are either optimal or nearly optimal.

In his pioneering work on LDPC codes, Gallager dismissed codes with parity-check matrices of weight two after proving that their minimum Hamming distances grow at most logarithmically with their code lengths. In spite of their poor minimum Hamming distances, it is shown that quasi-cyclic LDPC codes with parity-check matrices of column weight two have good capability to correct phased bursts of erasures which may not be surpassed by using quasi-cyclic LDPC codes with parity-check matrices of column weight three or more. By modifying the parity-check matrices of column weight two and globally coupling them, the erasure correcting capability can be further enhanced. Quasi-cyclic LDPC codes with parity-check matrices of column weight three or more that can correct phased bursts of erasures and perform well over the AWGN channel are also considered. Examples of such codes based on Reed-Solomon and Gabidulin codes are presented.

A novel scheme is presented for encoding and iterative soft-decision decoding of cyclic codes of prime lengths. The encoding of a cyclic code of a prime length is performed on a collection of codewords which are mapped through Galois Fourier transform into a codeword in a low-density parity-check code with a binary parity-check matrix for transmission. Using this matrix, binary iterative soft-decision decoding algorithm is applied to jointly decode a collection of codewords from the cyclic code. The joint-decoding allows for information sharing among the received vectors corresponding to the codewords in the collection during the iterative decoding process. For decoding Reed-Solomon and BCH codes of prime lengths, the proposed decoding scheme not only requires much lower decoding complexity than other soft-decision decoding algorithms for these codes, but also yields superior performance. The proposed decoding scheme can also achieve a joint-decoding gain over the maximum likelihood decoding of individual codewords. The decoding scheme is also applied to quadratic residue codes.

This paper presents a construction of a class of partial geometries based on RS codes of prime lengths and shows that LDPC codes constructed based on Reed-Solomon codes of prime lengths are finite geometry LDPC codes. Furthermore, a new method for design and construction of nonbinary quasi-cyclic LDPC codes based on the conventional parity-check matrices of Reed-Solomon codes is presented. Simulation results show that the constructed nonbinary LDPC codes perform well over the additive white Gaussian channel.

This paper presents designs and constructions of two classes of binary quasi-cyclic LDPC codes for correcting multiple random phased-bursts of erasures over the binary erasure channel. The erasure correction of codes in both classes is characterized by the cycle and adjacency structure of their Tanner graphs. Erasure correction of these codes is a very simple process which requires only modulo-2 additions. The codes in the second class are capable of correcting locally and globally distributed phased-bursts of erasures with a two-phase iterative erasure-correction process.

Designs and constructions of quasi-cyclic (QC) LDPC codes for the AWGN channel are presented. The codes are constructed based on the conventional parity-check matrices of Reed-Solomon (RS) codes and are referred to as RS-QC-LDPC codes. Several classes of RS-QC-LDPC codes are given. Cycle structural properties of the Tanner graphs of codes in these classes are analyzed and specific methods for constructing codes with girth at least eight and reducing their short cycles are presented. The designed codes perform well in both waterfall and low error-rate regions.

The Cadambe-Mazumdar bound gives a necessary condition for a code to have a certain locality in case of a single erasure in terms of length, dimension, and Hamming distance of the code and of certain shortened codes. The bound has been generalized by Rawat, Mazumdar, and Vishwanath to recover multiple erasures in a cooperative repair scenario. In this paper, the generalized Hamming weights of the code and its shortened codes, which include the Hamming distance as one component, are incorporated to obtain bounds on locality to recover a single erasure or multiple erasures cooperatively. The new bounds give sharper necessary conditions than existing bounds.

This paper presents a special type of nonbinary LDPC codes which are constructed based on Reed-Solomon codes. For a code of this type, its Tanner graph is composed of a set of disjoint and identical Tanner graphs, which are coupled together by a group of global check-nodes. Such a code is called a globally coupled LDPC code. This type of codes are capable of correcting random symbol errors, multiple phased bursts of erasures, and a single long burst of erasures.

A novel scheme is presented for encoding and decoding of Reed-Solomon codes of prime lengths. Encoding is performed on a collection of codewords which are mapped through Galois Fourier transform into a codeword in a low-density parity-check code with a binary parity-check matrix for transmission. Using this matrix, a binary iterative soft-decision decoding algorithm is applied to jointly decode a collection of codewords in the Reed-Solomon code. By allowing information sharing among the received vectors corresponding to the code-words in the collection, the proposed decoding scheme achieves superior performance over algorithms decoding individual Reed-Solomon codewords including maximum likelihood decoding.

Fire codes are cyclic codes generated by the product of two polynomials: a binomial that characterizes the code's guaranteed burst-correcting capability and an irreducible polynomial that characterizes the code length. However, the true burst-correcting capability of a Fire code may exceed its guaranteed burst-correcting capability, which can be thought of as the designed burst-correcting capability of the Fire code. The true burst-correcting capability of a Fire code depends on the irreducible polynomial used in code construction. In this paper, the maximum true burst-correcting capabilities of Fire codes are considered. Fire codes are classified based on three parameters: their designed burst-correcting capabilities, the least common multiple of the periods of the binomials, and the irreducible polynomials used in their constructions, and the ratios of the periods of primitive polynomials of the same degrees as the irreducible polynomials to the periods of the irreducible polynomials. It is shown that the maximum true burst-correcting capability of each class, which pertains to an infinite number of codes, can be determined by checking whether or not a finite number of incongruences have a solution. It is also shown that in each class, there is an infinite number of Fire codes, with increasing code lengths, that attain this maximum. The maximum true burst-correcting capabilities of several classes of Fire codes are determined. It is also shown that there are infinite sequences of irreducible polynomials that generate cyclic codes of rates approaching one and with burst-correcting capabilities that exceed any given number.

The Rosenbloom-Tsfasman metric has attracted the attention of many researchers as a generalization of the Hamming metric that is relevant to practical problems. Codes for this metric were considered. In particular, Reed-Solomon codes were generalized to be compatible with this metric. In this paper, a generalization of BCH codes for the Rosenbloom-Tsfasman metric is proposed. This generalization is based on considering BCH codes as subfield subcodes of Reed-Solomon codes. By characterizing these subfield subcodes, an explicit construction of BCH codes for the Rosenbloom-Tsfasman metric is provided. Two important properties of Reed-Solomon codes and BCH codes for the Rosenbloom-Tsfasman metric are studied and compared with those for the Hamming metric. These properties are cyclic structure and duality. The approach is based on Galois-Fourier transforms associated with Hasse derivatives.

Recently, Karimi and Banihashemi proposed an algorithm based on message-passing to count cycles in a graph of lengths less than double its girth. The algorithm uses only integer additions and subtractions to compute messages at the nodes of the graph that are passed to adjacent nodes. The complexity of the algorithm, when applied to a bipartite graph of girth g that has E edges, is O(gE2). The algorithm is superior to many other existing algorithms in the literature. In this paper, an improvement of this algorithm is presented that cuts both the complexity and the computing time by a factor of two. The improved algorithm is also applied to Tanner graphs of quasi-cyclic codes and, in this case, the complexity can be further cut by a factor of p, where p is the size of the circulants in the parity-check matrix of the quasi-cyclic code.

Polar codes proposed by Arikan are based on a linear kernel of dimension two with exponent 0.5. In this paper, binary kernels of maximum exponents of dimensions up to 16 are presented except for the case of dimension 12 where the maximum exponent is shown to be attained by either a constructed linear kernel or a possible nonlinear kernel with a specified partial distance sequence. The results show that the minimum dimension for which there exists a kernel with exponent greater than 0.5, i.e., exceeds the exponent of the linear kernel proposed by Arikan, is 14. For dimensions 14, 15, 16, discussed by Presman et al., along with 13, there are nonlinear kernels with exponents larger than any of that of a linear kernel. The kernels of these dimensions that have maximum exponent, although nonlinear over GF(2), are ℤ4-linear or ℤ2ℤ4-linear.

Fire codes are cyclic codes generated by the product of two polynomials: a binomial that characterizes the code's guaranteed burst correcting capability and an irreducible polynomial that characterizes the code length. However, the true burst correcting capability of a Fire code may exceed its guaranteed burst correcting capability. The true burst correcting capability of primitive Fire codes, in which the irreducible polynomial is primitive, is studied. In particular, the true burst correcting capability maximized over all primitive Fire codes with a given guaranteed burst correcting capability and a given greatest common divisor of the periods of the two factors of its generator polynomial is considered. It is shown that this maximum is attained by an infinite number of such codes.

This paper presents two simple and very flexible methods for constructing non-binary (NB) quasi-cyclic (QC) LDPC codes. The proposed construction methods have several known ingredients including base array, masking, binary to nonbinary replacement, and matrix-dispersion. By proper choice and combination of these ingredients, NB-QC-LDPC codes with excellent performance can be constructed. The constructed codes can be decoded with a reduced-complexity iterative decoding scheme which significantly reduces the hardware implementation complexity.

Polar codes are constructed based on kernels with polarizing properties. The performance of a polar code is characterized asymptotically in terms of the exponent of its kernel. The pioneering work of Arıkan on polar codes is based on a linear kernel of dimension two and exponent 0.5. In this paper, constructions of linear and nonlinear binary kernels of dimensions up to 16 are presented. The kernels are obtained using computer search or by shortening longer kernels obtained by computer search and a computer program is used to determine their exponents. It is proved that the constructed kernels have maximum exponents except in the case of nonlinear kernels of dimension 12 where it is demonstrated that the maximum exponent either equals that of the presented construction or assumes another specified value. The results show that the minimum dimension for which there exists a linear kernel with exponent greater than 0.5, i.e., exceeds the exponent of the linear kernel proposed by Arıkan, is 15, while this minimum dimension is 14 for nonlinear kernels. Furthermore, it is shown that there is a linear kernel with maximum exponent up to dimension 11. For dimensions 13, 14, 15, and 16, there are nonlinear kernels with exponents larger than any of that of a linear kernel. The kernels of these dimensions that have maximum exponent, although nonlinear over GF(2), are ℤ4-linear or ℤ2ℤ4-linear.

This paper presents a reduced-complexity iterative scheme and an algorithm for decoding non-binary quasi-cyclic (QC) LDPC codes of a specific type. The proposed decoding scheme and the algorithm together significantly reduce the hardware implementation complexity of a decoder with no performance degradation. Also presented in the paper is a simple method for constructing a class of non-binary QC-LDPC codes.

Codes are presented that can correct the deletion or the insertion of a predetermined number of adjacent bits greater than or equal to three. This extends the constructions of codes beyond those proposed by Levenshtein fifty years ago to correct one or two adjacent deletions or insertions.

This paper presents a simple and flexible method for constructing QC-LDPC codes based on two arbitrary sets of a finite field. Based on this method, a high-rate, high-performance and very low error-floor QC-LDPC code is first constructed and then a class of rate-1/2 QC-LDPC codes whose Tanner graphs have girth 8 or larger is presented. Also presented is a reduced-complexity iterative decoding algorithm for QC-LDPC codes.

A well-known method for balancing binary sequences, in the sense of forcing them to have as many zeroes as ones, was proposed by Knuth. It is based on the inversion of all bits beyond a certain balancing index, and communicating this index via a prefix. This principle has also been applied to balance runlength-limited (RLL) sequences. Another Knuth-based approach exploits the insertion of a marker in the RLL sequence causing a deliberate runlength violation at the position of the balancing index. This marker method has an advantage over the prefix method, since its redundancy does not grow with the length of the source blocks. In this paper, the markers are optimized with respect to their length and the severeness of the runlength violation, for possible application in future (optical) recording systems.

This paper presents a simple and very flexible method for constructing quasi-cyclic (QC) low density paritycheck (LDPC) codes based on finite fields. The code construction is based on two arbitrary subsets of elements from a given field. Some well known constructions of QC-LDPC codes based on finite fields and combinatorial designs are special cases of the proposed construction. The proposed construction in conjunction with a technique, known as masking, results in codes whose Tanner graphs have girth 8 or larger. Experimental results show that codes constructed using the proposed construction perform well and have low error-floors. Also presented in the paper is a reduced-complexity iterative decoding scheme for QC-LDPC codes based on the section-wise cyclic structure of their parity-check matrices. The proposed decoding scheme is an improvement of an earlier proposed reduced-complexity iterative decoding scheme.

Linear codes over channels causing erasures and errors can be decoded by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. To facilitate decoding of MDS codes, parity-check matrices are proposed that contain, as submatrices, parity-check matrices of the punctured codes. Depending on the maximum number of erasures, the separating redundancy, which is the smallest number of rows in the proposed parity-check matrices, is determined.

It is shown that Euclidean geometry LDPC codes in conjunction with their shortened codes obtained by puncturing their parity-check matrices are effective in correcting combinations of errors and erasures with a two-phase decoding scheme. This is due to the large row redundancies of the parity-check matrices of these codes which are given by the incidence matrices of Euclidean geometries.

An effective reduced-complexity min-sum algorithm for decoding algebraic quasi-cyclic LDPC codes is presented. The proposed decoding algorithm significantly reduces the hardware implementation complexity, the size of memory required to store information, and the computational complexity of a decoder with no or a small loss in performance compared to the scaled min-sum algorithm.

Cyclic and quasi-cyclic algebraic LDPC codes constructed based on finite fields, finite geometries, and combinatorial designs can achieve excellent performance in terms of error rate, error floor and rate of decoding convergence with iterative decoding. However, the relatively high density of the parity-check matrix of an algebraic cyclic or quasi-cyclic LDPC code makes the hardware implementation complexity of the decoder quite large, which may be a critical issue in practical applications. This paper presents an effective reduced-complexity algorithm for decoding algebraic cyclic and quasi-cyclic LDPC codes based on the block cyclic structure and cyclic grouping of the rows of their parity-check matrices. The decoding of a code is carried out based on a single small submatrix of the parity-check matrix of the code in a revolving manner. The proposed decoding algorithm significantly reduces the hardware implementation complexity and the size of memory required to store information.

Most decoding algorithms of linear codes, in general, are designed to correct or detect errors. However, many channels cause erasures in addition to errors. In principle, decoding over such channels can be accomplished by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. For any given linear code and any given maximum number of correctable erasures, parity-check matrices are introduced that yield parity-check equations which do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. These matrices allow for the separation of erasures from errors to facilitate decoding. Several constructions of such separating parity-check matrices are presented. To reduce decoding complexity, separating parity-check matrices with small number of rows are preferred. The minimum number of rows in a parity-check matrix separating a given maximum number of erasures is called the separating redundancy. Upper and lower bounds on the separating redundancies are derived. In particular, it is shown that the separating redundancies tend to grow linearly with the number of rows in full-rank parity-check matrices of codes. The separating redundancies of some classes of codes are determined for some maximum numbers of erasures.

Many known constructions of LDPC codes can be placed in a general framework using the notion of partial geometries. Based on this notion, the structure of such LDPC codes can be analyzed using a geometric approach that illuminates important properties of their parity-check matrices. In this approach, trapping sets are represented by subgeometries of the geometry used to construct the code. Based on the incidence relations between lines and points in this geometry, the structure of trapping sets is investigated. On the other hand, it is shown that removing a subgeometry corresponding to a trapping set gives a punctured matrix which can be used as a parity-check matrix of an LDPC code. This relates trapping sets, represented by subgeometries, and punctured matrices, represented by the residual geometries. The null spaces of these punctured matrices are LDPC codes which inherit many of the good structural properties of the original code. Hence, new LDPC codes, with various lengths and rates, can be obtained by puncturing an LDPC code constructed based on a partial geometry. Furthermore, these punctured matrices and codes can be used in a two-phase decoding scheme to correct combinations of errors and erasures.

Insertion/deletion detecting codes were introduced by Konstantinidis In this paper we define insertion/deletion detecting codes in a slightly different manner, and based on this definition, we introduce multiple deletion and multiple insertion detecting codes. It is shown that these codes, which are systematic, are optimal in the sense that there exists no other systematic multiple deletion (insertion) detecting codes with a better rate. One of the limitations of number-theoretic code constructions intended to correct insertion/deletion errors, e.g., the Levenshtein code, is that they require received codeword boundaries to be known in order to successfully decode. In literature, a number of schemes have been proposed to deal with this problem. We show how insertion/deletion detecting codes as presented in this paper can be used to improve and/or extend some of these schemes.

The trapping set structure of LDPC codes constructed using finite geometries is analyzed. A trapping set is modeled as a sub-geometry of the geometry used to construct an LDPC code. The variable nodes of a trapping set are viewed as points of the geometry and the check nodes adjacent to the variable nodes are viewed as the lines passing through any of these points. Based on this geometrical representation of a trapping set, its configuration can be determined.

A proof that the Helberg code is capable of correcting multiple deletion/insertion errors is presented. This code is a generalization of the number-theoretic Levenshtein code which is capable of correcting a single deletion/insertion. However, apart from exhaustive testing of short codes, no proof was hitherto given to verify that the Helberg code is indeed capable of correcting multiple deletions and insertions.

A matrix-theoretic approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is developed. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is amicable to the analysis and construction of quasi-cyclic low-density parity-check codes since it takes into account the specific parity-check matrix used for decoding with iterative message-passing algorithms. Based on this approach, the dimension of the codes and parity-check matrices for the dual codes can be determined. Several algebraic and geometric constructions of quasi-cyclic codes are presented as applications along with simulation results showing their performance over additive white Gaussian noise channels decoded with iterative message-passing algorithms.

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances.

A code construction is proposed to add a multiple insertion/deletion error correcting capability to a run-length limited sequence. The codewords of this code are themselves run-length limited. The insertion/deletion correcting capability is achieved by requiring several weighted sums of run-lengths in the codewords to satisfy certain congruences modulo primes. The construction is similar to the number-theoretic code proposed by Dolecek and Anantharam, which can correct multiple repetition errors or, equivalently, multiple insertions of zeros. It is shown that if the codewords in this code are run-length limited, then the code is capable of correcting both insertions and deletions of zeros and ones. An algorithm is proposed for decoding over a multiple insertion/deletion channel. Following the work of Dolecek and Anantharam, a systematic encoding method is also proposed for the codes. Furthermore, it is shown that the proposed construction has a higher rate asymptotically than the Helberg code, which is unconstrained in terms of run-lengths, even though our construction has the additional run-length constraints. The need for run-length limited codes that can correct insertion/deletion errors is motivated by bit-patterned media for magnetic recording.

Several classes of quasi-cyclic LDPC codes have been proposed in the literature and shown to have excellent performance over noisy channels when decoded with iterative message-passing algorithms. However, by and large, important properties of the codes, including their dimensions, are only given for specific codes based on computer programming. Using Fourier transforms, it is shown that the ranks of parity-check matrices of quasi-cyclic codes can be computed. From these ranks, the dimensions of the codes can be determined. The approach, which unifies most of the known algebraic constructions, is given in detail for three large classes of quasi-cyclic LDPC codes which appear in the literature.

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. This paper analyzes trapping set structure of binary regular LDPC codes whose parity-check matrices satisfy the constraint that no two rows (or two columns) have more than one place where they both have non-zero components, which is called row-column (RC) constraint. For a (γ,ρ)-regular LDPC code whose parity-check matrix satisfies the RC-constraint, its Tanner graph contains no (κ, τ) trapping set with size κ ≤ γ and number τ of odd degree check nodes less than γ. For several classes of RC-constrained regular LDPC codes constructed algebraically, we show that their Tanner graphs contain no trapping sets of sizes smaller than their minimum weights.

Error-floors are the main reason for excluding LDPC codes from applications requiring very low bit-error rate. They are attributed to a particular structure in the codes' Tanner graphs, known as trapping sets, which traps the message-passing algorithms commonly used to decode LDPC codes, and prevents decoding from converging to the correct codeword. A technique is proposed to break trapping sets while decoding. Based on decoding results leading to a decoding failure, some bits are identified in a previous iteration and flipped and decoding is restarted. This backtracking may enable the decoder to get out of the trapped state. A semi-analytical method is also proposed to predict the error-floor after backtracking. Simulation results indicate the effectiveness of the proposed technique in lowering the error-floor. The technique, which has moderate complexity overhead, is applicable to any code without requiring a prior knowledge of the structure of its trapping sets.

A new class of quasi-cyclic LDPC codes whose parity-check matrices are arrays of circulant permutation matrices constructed based on cyclic subgroups of finite fields is presented. This class of codes contains several known classes of algebraic quasi-cyclic LDPC codes as subclasses. Experimental results show that the codes constructed perform very well over the AWGN channel when decoded with iterative decoding based on belief propagation. This class of new QC-LDPC codes contains a subclass of codes which have large minimum distances. Combinatorial expressions for the ranks of the parity-check matrices of a subclass of codes constructed based on fields of characteristic two are given.

Flash memory is a nonvolatile computer storage device which consists of blocks of cells. While increasing the voltage level of a single cell is fast and simple, reducing the level of a cell requires the erasing of the entire block containing the cell. Since block-erasures are costly, flash coding schemes have been developed to maximize the number of writes before a block-erasure is needed. A novel coding scheme based on error-correcting codes is presented that allows the cell levels to increase as evenly as possible and as a result, increases the number of writes before a block-erasure. The scheme is based on the premise that cells whose levels are higher than others need not be increased. This introduces errors in the recorded data which can be corrected by an error-correcting code provided that the number of erroneous cells is within the error-correcting capability of the code. The scheme is also capable of combating noise, causing additional errors and erasures, in flash memories in order to enhance data reliability. For added flexibility, the scheme can be combined with other flash codes to yield concatenated schemes of high memory rates.

Flash memory is a non-volatile computer storage device which consists of blocks of cells. While increasing the voltage level of a single cell is fast and simple, reducing the level of a cell requires the erasing of the entire block containing the cell. Since block erasures are costly, traditional flash coding schemes have been developed to maximize the number of writes before a block erasure is needed. A novel coding scheme based on error-correcting codes allows the cell levels to increase as evenly as possibly and as a result, increases the number of writes before a block erasure. The scheme is also capable of combating noise in flash memories in order to enhance data reliability.

Linear block codes over noisy channels causing both erasures and errors can be decoded by deleting the erased symbols and decoding the resulting vector with respect to a punctured code and then retrieving the erased symbols. This can be accomplished using separating parity-check matrices. For a given maximum number of correctable erasures, such matrices yield parity-check equations that do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. Separating parity-check matrices typically have redundant rows. An upper bound on the minimum number of rows in separating parity-check matrices, which is called the separating redundancy, is derived which proves that the separating redundancy tends to behave linearly as a function of the code length.

This paper consists of three parts. The first part presents a large class of new binary quasi-cyclic (QC)-LDPC codes with girth of at least 6 whose parity-check matrices are constructed based on cyclic subgroups of finite fields. Experimental results show that the codes constructed perform well over the binary-input AWGN channel with iterative decoding using the sum-product algorithm (SPA) and they outperform the corresponding pseudo-random QC-LDPC codes constructed with the PEG-algorithm. The second part analyzes the ranks of the parity-check matrices of codes constructed based on finite fields with characteristic of 2 and gives combinatorial expressions for these ranks. The third part identifies a subclass of constructed QC-LDPC codes that have large minimum distances. Decoding of codes in this subclass with the SPA converges very fast.

Quasi-cyclic LDPC codes are the most promising class of structured LDPC codes due to their ease of implementation and excellent performance over noisy channels when decoded with message-passing algorithms as extensive simulation studies have shown. In this paper, an approach for constructing quasi-cyclic LDPC codes based on Latin squares over finite fields is presented. By analyzing the parity-check matrices of these codes, combinatorial expressions for their ranks and dimensions are derived. Experimental results show that, with iterative decoding algorithms, the constructed codes perform very well over the AWGN and the binary erasure channels.

Linear and cyclic codes are typically used to combat substitution errors. However, synchronization errors, associated with the deletion and insertion of symbols, can cause severe performance degradation unless the coding scheme possesses the capability to recover from such errors. It is shown that linear codes of rate greater than 1/2 cannot correct deletion or insertion errors but there are linear codes of rate 1/2 that can correct these errors. Although cyclic codes, except for repetition codes, cannot correct deletion or insertion errors, two approaches are investigated to yield codes, based on cyclic codes, that can correct these errors. In the first approach, it is shown that a binary or nonbinary cyclic code of rate at most 1/3 or 1/2, respectively, can be extended by one symbol to make it capable of correcting synchronization errors. In the second approach, a cyclic code of rate at most 1/2 is expurgated by appropriately deleting codewords such that the expurgated code is capable of correcting synchronization errors. It is shown that deleting codewords costs at most two information bits if the code is binary and one information symbol if the code is nonbinary.

An error-burst correcting algorithm is developed based on a circulant parity-check matrix of a cyclic code. The proposed algorithm is more efficient than error trapping if the code rate is less than about 2/3. It is shown that for any (n, k) cyclic code, there is an n × n circulant parity-check matrix such that the algorithm, applied to this matrix, corrects error bursts of lengths up to the error-burst correction limit of the cyclic code. This same matrix can be used to efficiently correct erasure bursts of lengths up to n - k. The error-burst correction capabilities of a class of cyclic low-density parity-check (LDPC) codes constructed from finite geometries are also considered.

This paper presents two novel reliability-based iterative majority-logic decoding algorithms for LDPC codes. Both algorithms are binary message-passing algorithms and require only logical operations and integer additions. Consequently, they can be implemented with simple combinational logic circuits. They either outperform or perform just as well as the existing weighted bit-flipping or other reliability-based iterative decoding algorithms for LDPC codes in error performance with a faster rate of decoding convergence and less decoding complexity. Compared to the sum-product algorithm for LDPC codes, they offer effective trade-offs between performance and decoding complexity.

A unified approach for constructing binary and nonbinary quasi-cyclic LDPC codes under a single framework is presented. Six classes of binary and nonbinary quasi-cyclic LDPC codes are constructed based on primitive elements, additive subgroups, and cyclic subgroups of finite fields. Numerical results show that the codes constructed perform well over the AWGN channel with iterative decoding.

This paper presents two algebraic methods for constructing high performance and efficiently encodable nonbinary quasi-cyclic LDPC codes based on arrays of special circulant permutation matrices and multi-fold array dispersions. Codes constructed based on these methods perform well over the AWGN and other types of channels with iterative decoding based on belief-propagation. Experimental results show that over the AWGN channel, these non-binary quasi-cyclic LDPC codes significantly outperform Reed-Solomon codes of the same lengths and rates decoded with either algebraic hard-decision Berlekamp-Massey algorithm or algebraic soft-decision Kötter- Vardy algorithm. Also presented in this paper is a class of asymptotically optimal LDPC codes for correcting bursts of erasures. Codes constructed also perform well over flat fading channels. Non-binary quasi-cyclic LDPC codes have a great potential to replace Reed-Solomon codes in some applications in communication environments and storage systems for combating mixed types of noises and interferences.

Templates are constructed to extend arbitrary additive error correcting or constrained codes, i.e., additional redundant bits are added in selected positions to balance the moment of the codeword. The original codes may have error correcting capabilities or constrained output symbols as predetermined by the usual communication system considerations, which are retained after extending the code. Using some number theoretic constructions in the literature, insertion/deletion correction can then be achieved. If the template is carefully designed, the number of additional redundant bits for the insertion/deletion correction can be kept small-in some cases of the same order as the number of parity bits in a Hamming code of comparable length.

Most decoding algorithms of linear codes, in general, are designed to correct or detect errors. However, many channels cause erasures in addition to errors. In principle, decoding over such channels can be accomplished by deleting the erased symbols and decoding the resulting vector with respect to a punctured code. For any given linear code and any given maximum number of correctable erasures, we introduce parity-check matrices yielding parity-check equations that do not check any of the erased symbols and which are sufficient to characterize all punctured codes corresponding to this maximum number of erasures. This allows for the separation of erasures from errors to facilitate decoding. The parity-check matrices typically have redundant rows. We give several constructions of such matrices and prove general bounds on their minimum sizes.

This paper presents two new algebraic constructions of high performance non-binary quasi-cyclic LDPC codes based on array dispersions of matrices over non-binary fields. Codes constructed perform well over the AWGN channel with iterative decoding using aFastFourierTransformbased sum-product algorithm. They achieve significantly large coding gains over Reed-Solomon codes of the same lengths and rates decoded with either the hard-decision Berlekamp-Massey algorithm or the algebraic soft-decision Koetter-Vardy algorithm. Due to their quasi-cyclic structure, they can be efficiently encoded using simple shift-registers with linear complexity. They have a potential to replace RS codes for some applications in communication and storage systems.

This paper is concerned with construction of efficiently encodable nonbinary quasi-cyclic LDPC codes based on finite fields. Four classes of nonbinary quasi-cyclic LDPC codes are constructed. Experimental results show that codes constructed perform well with iterative decoding using a fast Fourier transform based q-ary sum-product algorithm and they achieve significant coding gains over Reed-Solomon codes of the same lengths and rates decoded with either algebraic hard- decision Berlekamp-Massey algorithm or algebraic soft-decision Kotter-Vardy algorithm.

This paper presents five methods for constructing nonbinary LDPC codes based on finite geometries. These methods result in five classes of nonbinary LDPC codes, one class of cyclic LDPC codes, three classes of quasi-cyclic LDPC codes and one class of structured regular LDPC codes. Experimental results show that constructed codes in these classes decoded with iterative decoding based on belief propagation perform very well over the AWGN channel and they achieve significant coding gains over Reed-Solomon codes of the same lengths and rates with either algebraic hard-decision decoding or Kotter-Vardy algebraic soft-decision decoding at the expense of a larger decoding computational complexity.

The performance of iterative decoding techniques for linear block codes correcting erasures depends very much on the sizes of the stopping sets associated with the underlying Tanner graph, or, equivalently, the parity-check matrix representing the code. In this correspondence, we introduce the notion of dead-end sets to explicitly demonstrate this dependency. The choice of the parity-check matrix entails a tradeoff between performance and complexity. We give bounds on the complexity of iterative decoders achieving optimal performance in terms of the sizes of the underlying parity-check matrices. Further, we fully characterize codes for which the optimal stopping set enumerator equals the weight enumerator.

The use of linear and cyclic codes for correcting synchronization errors is investigated. These codes are typically required to have the capability to correct substitution errors, which are the most common type of errors in most communication and storage systems. However, synchronization errors, associated with the deletion and insertion of symbols, can also occur and may cause severe performance degradation unless the coding scheme possesses the capability to recover from such errors. We show that linear codes of rate greater than 1/2 cannot correct deletion or insertion errors. Although cyclic codes, except for repetition codes, cannot correct deletion or insertion errors, we show that adding one extra symbol to the codewords of a binary or nonbinary cyclic code of rate at most 1/3 or 1/2, respectively, yields a code capable of correcting a single deletion or insertion.

The generalized iterative decoding concept offers attractive performance versus complexity trade-off opportunities in the spectrum between traditional iterative decoding and optimal decoding for linear block codes over the binary erasure channel. In each iteration, a system of equations is solved. The maximum number of equations to be solved in one iteration is called the order of the decoder. In case the order is just one, the generalized iterative decoder reduces to the traditional iterative decoder. On the other hand, if the order is set to the redundancy of the codes, the generalized iterative decoder gives the same performance as the optimal decoder. Varying the order between these two extremes allows for a better match to the system specifications. In this paper, we consider aspects regarding the implementation of generalized iterative decoding and we determine the minimum order (as a function of the girth) that can potentially lead to improvement over traditional iterative decoding.

We investigate extending a chosen block or convolutional code which has additive error correction capability, as predetermined by the usual communication systems or coding considerations. Our extension involves constructing a template to add additional redundant bits in positions, selected to balance the moment of the code word. Using some number theoretic constructions in the literature, insertion/deletion correction can then be achieved. If the template is carefully designed, the number of additional redundant bits for the insertion/deletion correction can be kept small - in some cases of the same order as for Hamming codes. Our construction technique can also be used for the systematic encoding of number theoretic codes, and furthermore have implications for other coding techniques utilizing the moment function, such as codes correcting asymmetrical errors, spectral shaping codes, or constant weight codes.

Stopping sets, and in particular their numbers and sizes, play an important role in determining the performance of iterative decoders of linear codes over binary erasure channels. In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this correspondence, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix.

In the late 1950s and early 1960s, finite fields were successfully used to construct linear block codes, especially cyclic codes, with large minimum distances for hard-decision algebraic decoding, such as Bose-Chaudhuri-Hocquenghem (BCH) and Reed-Solomon (RS) codes. This paper shows that finite fields can also be successfully used to construct algebraic low-density parity-check (LDPC) codes for iterative soft-decision decoding. Methods of construction are presented. LDPC codes constructed by these methods are quasi-cyclic (QC) and they perform very well over the additive white Gaussian noise (AWGN), binary random, and burst erasure channels with iterative decoding in terms of bit-error probability, block-error probability, error-floor, and rate of decoding convergence, collectively. Particularly, they have low error floors. Since the codes are QC, they can be encoded using simple shift registers with linear complexity.

Two algebraic methods for systematic construction of structured regular and irregular low-density parity-check (LDPC) codes with girth of at least six and good minimum distances are presented. These two methods are based on geometry decomposition and a masking technique. Numerical results show that the codes constructed by these methods perform close to the Shannon limit and as well as random-like LDPC codes. Furthermore, they have low error floors and their iterative decoding converges very fast. The masking technique greatly simplifies the random-like construction of irregular LDPC codes designed on the basis of the degree distributions of their code graphs

This paper investigates cyclic codes for correcting bursts of errors from a new point of view. A simple iterative algorithm for correcting bursts of errors is developed. This algorithm is optimal in the sense that it corrects burst of errors of lengths up to the burst-error-correction limit of a cyclic code. Also included in the paper is an iterative process for correcting bursts of erasures.

In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three for a full-rank parity-check matrix of the Hamming code. In this paper, we derive an expression for the number of stopping sets of any given size for the same parity-check matrix

LDPC codes have excellent performance when iteratively decoded based on sparse parity-check matrices over both the AWGN channel and the erasure channel. In this paper, we propose a simple burst-correction decoding scheme for cyclic LDPC codes based on the same sparse circulant parity-check matrices used to perform iterative decoding. Although the proposed scheme may not achieve the full burst-correcting capability of the codes, it is rather simple and fast. We also show that the full burst-correcting capabilities of some codes constructed from Euclidean and projective geometries are very close to the Reiger upper bound

This paper presents three algebraic methods for constructing nonbinary quasi-cyclic (QC)-LDPC codes. Three classes of efficiently encodable QC-LDPC codes over nonbinary finite fields are constructed. Experimental results show that constructed codes decoded with iterative decoding perform well over the AWGN channel and they achieve significant coding gains over Reed-Solomon (RS) codes of the same lengths and rates decoded with algebraic decoding

This paper is concerned with construction of quasi-cyclic (QC) low-density parity-check (LDPC) codes for three different types of channels: the additive white Gaussian noise, the binary random erasure, and the binary burst erasure channels. Two algebraic methods for systematic construction of QC-LDPC codes are presented. Codes constructed perform well over all three types of channels

Data allocation on multiple I/O devices manifests itself in many computing systems, both centralized and distributed. Data is partitioned on multiple I/O devices and clients issue various types of queries to retrieve relevant information. In this paper, we derive necessary and sufficient conditions for a data allocation method to be optimal for two important types of queries: partial match and bounded disagreement search queries. We formally define these query types and derive the optimality conditions based on coding-theoretic arguments. Although these conditions are fairly strict, we show how to construct good allocation methods for practical realistic situations. Not only are the response times bounded by a small value, but also the identification of the relevant answer set is efficient

This paper presents two algebraic methods for constructing efficiently encodable quasi-cyclic (QC) LDPC codes that perform well on both the AWGN and binary erasure channels with iterative decoding in terms of bit-error performance, block error performance and error-floor, collectively. The constructions are based on the cyclic subgroups of the multiplicative groups of finite fields and affine mappings

In the 2004 Shannon Lecture, McEliece presented an expression for the number of stopping sets of size three in a Hamming code. In this paper, we investigate how this number depends on the parity-check matrix used in the decoding process. First, we present basic results on stopping set enumerators for block codes in general. Next, we focus on stopping set enumerators for Hamming codes. Our main result is a parity-check matrix of relatively small size for which the number of stopping sets of size three equals the number of codewords of weight three in the Hamming code.

This paper presents a method for constructing structured LDPC codes based on finite fields and affine mappings. The Tanner graphs of these codes have girth at least six. Experimental results show that codes constructed based on this method with iterative decoding perform well on both the AWGN and binary erasure channels. Furthermore, codes constructed based on prime fields are quasi-cyclic.

New algebraic methods for constructing codes based on hyperplanes of two different dimensions in finite geometries are presented. The new construction methods result in a class of multistep majority-logic decodable codes and three classes of low-density parity-check (LDPC) codes. Decoding methods for the class of majority-logic decodable codes, and a class of codes that perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs, are presented. Most of the codes constructed can be either put in cyclic or quasi-cyclic form and hence their encoding can be implemented with linear shift registers.

Recently, Fu, Klove, and Wei (2003) have shown that the undetected error probability of a binary code is related to that of its complement, and the undetected error probability of a constant-weight binary code is related to that of its complement relative to the set of all constant-weight vectors. We generalize these relations to cover the complements of any binary or nonbinary code relative to a distance-invariant code containing the first code. We prove the generalization using a much simpler argument than the published proofs of the special cases.

This correspondence presents three algebraic methods for constructing low-density parity-check (LDPC) codes. These methods are based on the structural properties of finite geometries. The first method gives a class of Gallager codes and a class of complementary Gallager codes. The second method results in two classes of circulant-LDPC codes, one in cyclic form and the other in quasi-cyclic form. The third method is a two-step hybrid method. Codes in these classes have a wide range of rates and minimum distances, and they perform well with iterative decoding.

A framework is presented for generalized minimum distance (GMD) decoding with a limited number of decoding trials and a restricted set of reliability values. In GMD decoding, symbols received from the channel may be erased before being fed into an algebraic error-erasure decoder for error correction, in subsequent or simultaneous trials with different erasing patterns. The decision whether or not to erase a symbol in a certain trial is taken by an erasure-choosing algorithm which takes into account reliability information from the channel. The final GMD decoder output is a codeword which results from a decoding trial and satisfies a certain distance criterion. For various erasing strategies and reliability sets, the guaranteed error-correction radius and the unsuccessful decoding probability of this technique are studied. Both known and new results, with applications to concatenated coding, follow from the unified approach presented in this correspondence.

The undetected error probabilities of codes when used repeatedly to transmit sequences of messages are studied. It is shown that for any code whose rate is greater than zero but less than one, the coding scheme obtained by the repeated use of the code is bad, if used five times or more, and improper if used four times or more. Furthermore, the repeated use of any linear code, over an alphabet greater than five, more than once, is bad and improper.

We present a general version of the generalized minimum distance (GMD) decoding algorithm (see Forney, G.D., Jr, 1966) that accommodates different erasing strategies. This version is called reduced GMD decoding since, depending on the erasing strategy used, it can offer a reduction in complexity over Forney's GMD decoding. We apply reduced GMD decoding to concatenated codes. In particular, we study the error correction capability and the unsuccessful decoding probability of concatenated codes with reduced GMD decoding.

A general scheme for DC-free (d,k)-constrained block codes is considered. In this scheme, messages are mapped to nonzero dklr-sequences of fixed length. For any two dklr-sequences, two merging sequences of fixed length and of different weight parities are available such that each one of these sequences can be inserted between the two dklr-sequences to maintain the (d,k) constraint. One of these two merging sequences is chosen to ensure that the code is DC-free. For all (d,k) constraints with capacities at least equal to 0.5, optimal values of l and r that yield maximal code rates are specified.

We consider a concatenated coding scheme using a single inner code, a single outer code, and a fixed single-trial decoding strategy that maximizes the number of errors guaranteed to be corrected in a concatenated codeword. For this scheme, we investigate whether maximizing the guaranteed error correction rate, i.e., the number of correctable errors per transmitted symbol, necessitates pushing the code rate to zero. We show that this is not always the case for a given inner or outer code. Furthermore, to maximize the guaranteed error correction rate over all inner and outer codes of fixed dimensions and alphabets, the code rate of one (but not both) of these two codes should be pushed to zero.

Many scientific and engineering applications process large multidimensional datasets. An important access pattern for these applications is the retrieval of data corresponding to ranges of values in multiple dimensions. Performance is limited by disk largely due to high disk latencies. Tiling and distributing the data across multiple disks is an effective technique for improving performance through parallel I/O. The distribution of tiles across the disks is an important factor in achieving gains. Several schemes for declustering multidimensional data to improve the performance of range queries have been proposed in the literature. We extend the class of cyclic schemes which have been developed earlier for two-dimensional data to multiple dimensions. We establish important properties of cyclic schemes, based upon which we reduce the search space for determining good declustering schemes within the class of cyclic schemes. Through experimental evaluation, we establish that the cyclic schemes are superior to other declustering schemes, including the state-of-the-art, both in terms of the degree of parallelism and robustness.

Various proposals have been made for declustering 2D tiled data on multiple I/O devices. Strictly optimal solutions only exist under very restrictive conditions on the tiling of the 2D space or for very few I/O devices. In this paper, we explore allocation methods where no strictly optimal solution exists. We propose a general class of allocation methods, referred to as cyclic allocation methods, and show that many existing methods are instances of this class. As a result, various seemingly ad hoc and unrelated methods are presented in a single framework. Furthermore, the framework is used to develop new allocation methods that give better performance than any previous method and that approach the best feasible performance.

Substitution errors, where individual characters are altered, and transposition errors, where two consecutive characters are interchanged, are commonly caused by human operators. In this paper, codes that detect a single substitution error or a single transposition error are studied. In particular, it is shown that such codes of length n over an alphabet of q characters have at most qn−1 codewords if q ≤ 3 and at most [2n/3] codewords if q = 2. Codes which have that many codewords are called optimal codes. We present optimal codes for all values of n and q. Simple encoding techniques for these codes are also described.

We present a new construction of block codes for the (1-D)-PR (partial response) channel. The codewords in the code correspond to constant-sum subsets of a difference set. It is shown that at the output of a noiseless (1-D)-PR channel; the minimum squared Euclidean distance of such a code is at least six, compared to two for the uncoded system. This construction yields larger code rates than previously known codes with the same minimum distance for large code lengths. The construction technique also imposes upper bounds on the decoding complexity of the codes.

The maximum number of information bits that can be encoded systematically by the number-theoretic codes of Varshamov and Tenengol'ts (1965) is determined. This number is also studied for the more general class of the group-theoretic Constantin-Rao (1979) codes. Although these codes are at least as large as the Varshamov-Tenengol'ts codes, it is shown that the number of bits that can be systematically encoded using a Constantin-Rao code does not exceed the number of bits that can be systematically encoded using a Varshamov-Tenengol'ts code. In fact, in many cases, the largest Constantin-Rao code has the least number of bits that can be systematically encoded.

Error detection is a simple technique used in various communication and memory systems to enhance reliability. We study the probability that a q-ary (linear or nonlinear) block code of length n and size M fails to detect an error. A lower bound on this undetected error probability is derived in terms of q, n, and M. The new bound improves upon other bounds mentioned in the literature, even those that hold only for linear codes. Block codes whose undetected error probability equals the new lower bound are investigated. We call these codes strictly optimal codes and give a combinatorial characterization of them. We also present necessary and sufficient conditions for their existence. In particular, we find all values of n and M for which strictly optimal binary codes exist, and determine the structure of all of them. For example, we construct strictly optimal binary-coded decimal codes of length four and five, and we show that these are the only possible lengths of such codes.

Levenshtein (1966) proposed a class of single insertion/deletion correcting codes, based on the number-theoretic construction due to Varshamov and Tenengolt's (1965). We present several interesting results on the binary structure of these codes, and their relation to constrained codes with nulls in the power spectral density function. One surprising result is that the higher order spectral null codes of Immink and Beenker (1987) are sub-codes of balanced Levenshtein codes. Other spectral null sub-codes with similar coding rates, may also be constructed. We furthermore present some coding schemes and spectral shaping markers which alleviate the fundamental restriction on Levenshtein's codes that the boundaries of each codeword should be known before insertion/deletion correction can be effected.

Significant improvements in magnetic storage densities have been made feasible by the application of partial-response signaling combined with maximum-likelihood sequence estimation. To enhance the performance of this technique when applied to the class-IV partial-response channel, which is recognized as being appropriate to model the magnetic recording channel, it is often required to bound the number of consecutive zeros in the recorded data sequence and its odd and even subsequences. We investigate block codes that satisfy such a constraint. In particular, we look for a set of maximal number of fixed-length sequences such that any pair of them can be concatenated without violating the constraint. In many cases, depending on the constraint and the length of the sequences, we determine such a set, and in the remaining cases, we determine at most three candidates for it. These results are used to study the best possible constrained block codes.

Several techniques for constructing practical codes for noisy modulation channels represented by (d,k) constraints, such as in magnetic and optical recording, are analyzed. Concatenated schemes based on inner sliding-window codes are compared with concatenated schemes based on inner block codes in terms of efficiency and reliability. The performance of the schemes is investigated in detail for (1,7) constrained channels with different error characteristics. It is shown that for such channels, concatenated schemes based on inner sliding-window codes have higher code rates than concatenated schemes based on inner block codes for typical applications. However, if the channels are very noisy or extremely small decoding error probabilities are required, then the latter schemes tend to have higher code rates than the former ones.

The problem of detecting a corrupted page in a file with multiple copies is addressed. A lower bound is derived on the communication overhead and a protocol is developed that requires exactly the amount of communication specified by the lower bound. The lower bound and the protocol are the first optimality results for the detection of a corrupted page in a file with more than two copies.>

We study the problem of identifying corrupted pages between two remotely located copies of a file in a distributed system. An efficient deterministic algorithm is presented to identify up to any given number of differing pages. The algorithm requires a single exchange of messages and is based on the structure of the Reed-Solomon code. In order to identify up to f corrupted pages, 2f signatures are transmitted. The algorithm requires less communication costs than previously proposed solutions. In fact, we prove that our algorithm is optimal, in the sense that no other algorithm is guaranteed to identify with probability 1 the corrupted pages by exchanging less information.>

Article Free Access Share on Efficient detection of corrupted pages in a replicated file Authors: Khaled A. S. Abdel-Ghaffar View Profile , Amr El Abbadi View Profile Authors Info & Claims PODC '93: Proceedings of the twelfth annual ACM symposium on Principles of distributed computingSeptember 1993Pages 219–227https://doi.org/10.1145/164051.164076Published:01 September 1993Publication History 8citation184DownloadsMetricsTotal Citations8Total Downloads184Last 12 Months4Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

In magnetic or optical storage devices, it is often required to map the data into runlength-limited sequences. To ensure that cascading such sequences does not violate the runlength constraints, a number of merging bits are inserted between two successive sequences. A theory is developed in which the minimum number of merging bits is determined, and the efficiency of a runlength-limited fixed-length coding scheme is considered.>

The problem of disk allocation addresses the issue of how to distribute a file on several disks in order to maximize concurrent disk accesses in response to a partial match query. In this paper a coding-theoretic analysis of this problem is presented, and both necessary and sufficient conditions for the existence of strictly optimal allocation methods are provided. Based on a class of optimal codes, known as maximum distance separable codes, strictly optimal allocation methods are constructed. Using the necessary conditions proved, we argue that the standard definition of strict optimality is too strong and cannot be attained, in general. Hence, we reconsider the definition of optimality. Instead of basing it on an abstract definition that may not be attainable, we propose a new definition based on the best possible allocation method. Using coding theory, allocation methods that are optimal according to our proposed criterion are developed.

Unit constraint length convolutional codes are codes that can be generated by encoders with a single delay element. The maximal free distances of these codes are determined in terms of the maximal minimum distances of linear block codes. A formula for the weight enumerator of unit constraint-length convolution codes is derived and a MacWilliams identity to determine the weight enumerator state diagram of a code from the weight enumerator state diagram of its dual code is given.>

The authors present a coding architecture suitable for magnetic storage systems. In data storage devices, several types of errors may occur. This includes random errors as well as burst errors of different lengths. A class of error control codes is presented, based on a multilevel coding architecture, that can correct several types of errors. The parameters of the multilevel codes can be adjusted to match the probability of each error type. The decoding algorithms of these codes allow for fast-error recovery since they are based on decoding algorithms for simple codes. A class of multilevel codes is constructed, based on Reed-Solomon codes, whose redundancy is minimal.>

Block codes satisfying (d,k) constraints are studied. These runlength-limited codes are useful for strong data in magnetic recording devices. Since most devices are noisy, the codes are often required to have some error-control capability. The authors consider codes that can detect or correct symmetric, asymmetric, or bit-shift errors. Explicit construction methods for error-detecting codes are presented. Upper bounds on the sizes of error-correcting codes based on sphere packing arguments are derived. The construction methods and the upper bounds improve upon the best known results concerning optimal runlength-limited error-control block codes.>

In this paper we present a coding-theoretic analysis of the disk allocation problem. We provide both necessary and sufficient conditions for the existence of strictly optimal allocation methods. Based on a class of optimal codes, known as maximum distance separable codes, strictly optimal allocation methods are constructed. Using the necessary conditions proved, we argue that the standard definition of strict optimality is too strong, and cannot be attained in general. A new criterion for optimality is therefore defined whose objective is to design allocation methods that yield a response time of one for all queries with a minimum number of specified attributes. Using coding theory, we determined this minimum number for binary files, assuming that the number of disks is a power of two. In general, our approach provides better allocation methods than previous techniques.

The free distance of a convolutional code of rate 1/n is bounded by n times the constant length of its encoder. Two classes of convolutional codes whose free distances meet this bound are studied. A technique of constructing convolutional codes that meet this bound for all sufficiently large n is given.>

A cyclic b-burst correcting code over GF(q) of redundancy r and length n=(q/sup r-b+1/-1)/(q-1) is said to be optimum. It is proved that a necessary condition for the existence of such a code is the existence of a square-free polynomial in GF(q)(x) of degree b-1 which is not divisible by x such that its period and the degrees of its irreducible factors are relatively prime to q-1. Moreover, if such a polynomial exists, then there are an infinite number of optimum cyclic b-burst correcting codes over GF(q).>

A new class of codes, called burst identification codes, is defined and studied. These codes can be used to determine the patterns of burst errors. Two-dimensional burst correcting codes can be easily constructed from burst identification codes. The resulting class of codes is simple to implement and has lower redundancy than other comparable codes. The results are pertinent to the study of radiation effects on VLSI RAM chips, which can cause two-dimensional bursts of errors.>

A class of codes called finite-state (FS) codes is defined and investigated. The codes, which generalize both block and convolutional codes, are defined by their encoders, which are finite-state machines with parallel inputs and outputs. A family of upper bounds on the free distance of a given FS code is derived. A general construction for FS codes is given, and it is shown that in many cases the FS codes constructed in this way have a free distance that is the largest possible. Catastrophic error propagation (CEP) for FS codes is also discussed. It is found that to avoid CEP one must solve the graph-theoretic problem of finding a uniquely decodable edge labeling of the state diagram.>

It is shown that for each integerb \geq 1infinitely many optimum cyclicb-burst-correcting codes exist, i.e., codes whose lengthn, redundancyr, and burst-correcting capabilityb, satisfyn = 2^{r-b+1} - 1. Some optimum codes forb = 3, 4, and5are also studied in detail.