On the construction of a class of majority-logic decodable codes

The attractiveness of majority-logic decoding is its simple implementation. Several classes of majority-logic decodable block codes have been discovered for the past two decades. In this paper, a method of constructing a new class of majority-logic decodable block codes is presented. Each code in this class is formed by combining majority-logic decodable codes of shorter lengths. A procedure for orthogonalizing codes of this class is formulated. For each code, a lower bound on the number of correctable errors with majority-logic decoding is obtained. An upper bound on the number of orthogonalization steps for decoding each code is derived. Several majority-logic decodable codes that have more information digits than the Reed-Muller codes of the same length and the same minimum distance are found. Some results presented in this paper are extensions of the results of Lin and Weldon [11] and Gore [12] on the majority-logic decoding of direct product codes.     

Shortened finite geometry codes (Corresp.)

A method of shortening finite analytic geometry codes, projective-geometry (PG) codes, Euclidean-geometry (EG) codes, and 2-fold EG codes is presented. The shortened codes preserve the feature of being majority-logic decodable and they have the same error-correcting capability as the original codes. Combinatorial expressions for the parity-check symbols of the shortened codes are derived.     

Codes on finite geometries

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.     

On majority-logic decoding of finite geometry codes

In this paper, an improved decoding algorithm for codes that are constructed from finite geometries is introduced. The application of this decoding algorithm to Euclidean geometry (EG) and projective geometry (PG) codes is further discussed. It is shown that these codes can be orthogonalized in less than or equal to three steps. Thus, these codes are majority-logic decodable in no more than three steps. Our results greatly reduce the decoding complexity of EG and PG codes in most cases. They should make these codes very attractive for practical use in error-control systems.     

Polynomial codes

A class of cyclic codes is introduced by a polynomial approach that is an extension of the Mattson-Solomon method and of the Muller method. This class of codes contains several important classes of codes as subclasses, namely, BCH codes, Reed-Solomon codes, generalized primitive Reed-Muller codes, and finite geometry codes. Certain fundamental properties of this class of codes are derived. Some subclasses are shown to be majority-logic decodable.     

Error-erasure decoding of product codes (Corresp.)

Two error-erasure decoding algorithms for product codes that correct all the error-erasure patterns guaranteed correctable by the minimum Hamming distance of the product code are given. The first algorithm works when at least one of the component codes is majority-logic decodable. The second algorithm works for any product code. Both algorithms use the decoders of the component codes.     

On the stopping distance of finite geometry LDPC codes

In this letter, the stopping sets and stopping distance of finite geometry LDPC (FG-LDPC) codes are studied. It is known that FG-LDPC codes are majority-logic decodable and a lower bound on the minimum distance can be thus obtained. It is shown in this letter that this lower bound on the minimum distance of FG-LDPC codes is also a lower bound on the stopping distance of FG-LDPC codes, which implies that FG-LDPC codes have considerably large stopping distance. This may explain in one respect why some FG-LDPC codes perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs.     

一类一步多数逻辑可译码的广义汉明重量谱

线性码的广义汉明重量谱描述了码在第二类窃密信道中传输的密码学特征。该文针对一类循环码在仿射置换群之下不变的一步多数逻辑可译码的广义汉明重量谱进行了研究,提出了该类码的重量谱的估计方法,并通过实例作了说明。     

Generalized tensor product codes

A class of binary error-correcting codes, called generalized tensor product codes, is presented with their decoding algorithm. These codes are constructed by combining a number of codes on various extension fields with shorter binary codes. A general algorithm is provided to do bounded distance decoding for these codes. Simply decodable codes such as Wolf's tensor product codes are shown to be special cases of this class of codes. Simply decodable and more efficient codes than Wolf's codes are also included as special cases.     

Hybrid Golomb codes for a group of quantised GG sources

The authors develop a class of codes for quantised generalised Gaussian (GG) sources. This new class of codes, that are called hybrid Golomb (HG) codes, are hybrids of Golomb-Rice (GR) codes and exp-Golomb (EG) codes. They integrate the properties of both GR and EG codes, which makes their performance more robust under variable source parameters. The efficiencies of the three classes of codes are compared and it is shown that the set of HG codes have efficiencies of approximately 70% or greater for a wide range of parameter values, whereas GR and EG codes can have efficiencies lower than 20%. The efficiencies of the set of HG codes are also compared with the set of EG codes that have the best performance under parameter scaling. It is shown that this set of HG codes still achieve a higher efficiency.     

Braided Convolutional Codes: A New Class of Turbo-Like Codes

We present a new class of iteratively decodable turbo-like codes, called braided convolutional codes. Constructions and encoding procedures for tightly and sparsely braided convolutional codes are introduced. Sparsely braided codes exhibit good convergence behavior with iterative decoding, and a statistical analysis using Markov permutors shows that the free distance of these codes grows linearly with constraint length, i.e., they are asymptotically good.     

Errors-and-erasures decoding of binary majority-logic-decodable codes

The decoder of a binary majority-logic decodable code can be modified to enable the correction of erasures as well as errors. The changes required in both type-I and type-II decoders are described and compared in terms of increases in decoder complexity and internal clock rates.     

Development of an Error-Correction Method for Data Packet Multiplexed with TV Signals

By using the vertical blanking period of television signals, it is possible to transmit coded data such as teletext, telesoftware, music, etc. However, the quality of data transmission on television transmission channels is very poor and a powerful error-correction code is required to reliably transmit coded data. From the results of simulations using error pattern data collected in field tests and the comparison of various error-correction codes under many conditions, it has been determined that the shortened (272, 190) majority-logic decodable difference-set cyclic code is a suitable code for NTSC TV signals. By using error-correction codes proposed to date for teletext, it has been difficult to obtain a page error rate (PER) of 10^-1in many measurement points. However, PER's of less than 10^-2can be obtained in this system, even when random noise, ghost interference, or waveform distortion are present and bit error rates (BER's) are 10^-2. This paper also gives an empirical equation according to the error data and shows that the error-correction capability increased equivalently up to 11 error-bits in a packet by modifying the decoding algorithm.     

A class of high-speed decodable burst-correcting codes (Corresp.)

A class of high-speed decodable burst-correcting codes is presented. This class of codes is obtained by modifying burst-correcting convolutional codes into block codes and does not require any cyclic shifts in the decoding process. With the appropriate choices of parameters, the codes can approximate minimum-redundancy codes. The high-speed decodability is expected to make these codes suitable for application to computer systems.     

Spectrum of incorrectly decoded bursts for cyclic burst error codes

The enumeration of the incorrectly decoded bursts for cyclic burst error-correcting codes is reported here. The enumeration yields closed formulas for long bursts, whereas an efficient algorithm for the enumeration is given for the short bursts. The enumeration is carried out for two different decoding rules. Under the first rule, the cyclic code is a full length code, and split decodable patterns are decoded by the decoder in spite of the fact that a split decodable pattern can be a burst that exceeds the decoding capability of the decoder. The analysis for the second rule assumes split patterns are not decoded. This analysis is valid for the class of shortened cyclic codes.     

Ternary graph theoretic error-correcting codes (Corresp.)

It is shown that directed graphs can be used to generate a class of moderately efficient error-correcting codes, which are easily decodable.     

An error-correcting code for data broadcasting and its error-correction capability

By using the vertical blanking period of television signals, it is possible to transmit coded data such as teletext, newspaper, telesoftware, music score, etc. However, the quality of ordinary TV channels is very poor for digital communications and a powerful error-correcting code is required to reliably transmit coded data. From the results of simulations using error pattern data collected in field tests and the comparison of various error-correcting codes under many conditions, it has been determined that the shortened (272, 190) majority-logic decodable difference-set cyclic code is a suitable code for NTSC TV signals. Moreover, the decoding algorithm for this code has been improved in order to increase the error-correction capability and a new LSI with this function has been developed. By using error-correcting codes proposed to date for teletext, it has been difficult to obtain a page error rate (PER) of 10⁻¹in many measurement points. However, PERs of less than 10⁻² can be obtained in this system, even when random noise, ghost interference, or waveform distortion are present and bit error rates (BERs) are 10⁻². This paper also gives PERs according to the error-data collected in field tests and shows that the error-correction capability increased equivalently up to 11 error-bits in a 272-bit by improving the decoding algorithm and the results of indoor and outdoor tests.     

On majority-logic decoding for duals of primitive polynomial codes

The class of polynomial codes introduced by Kasami et al. has considerable inherent algebraic and geometric structure. It has been shown that this class of codes and their dual codes contain many important classes of cyclic codes as subclasses, such as BCH codes, Reed-Solomon codes, generalized Reed-Muller codes, projective geometry codes, and Euclidean geometry codes. The purpose of this paper is to investigate further properties of polynomial codes and their duals. First, majority-logic decoding for the duals of certain primitive polynomial codes is considered. Two methods of forming nonorthogonal parity-check sums are presented. Second, the maximality of Euclidean geometry codes is proved. The roots of the generator polynomial of an Euclidean geometry code are specified.     

Some results on arithmetic codes of composite length

A new upper bound on the minimum distance of binary cyclic arithmetic codes of composite length is derived. New classes of binary cyclic arithmetic codes of composite length are introduced. The error correction capability of these codes is discussed, and in some cases the actual minimum distance is found. Decoding algorithms based on majority-logic decision are proposed for these codes.     

New construction of majority logic decodable quasicyclic codes

A new construction of majority logic decodable quasicyclic codes is presented. As an example, an infinite family of quasicyclic codes with a minimum distance of four is constructed, and comparisons are made to show that they are better than selforthogonal quasicyclic codes and Shiva codes.<>