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.     

Distributed decoding of cyclic block codes using a generalizationof majority-logic decoding

One-step majority-logic decoding is one of the simplest algorithms for decoding cyclic block codes. However, it is an effective decoding scheme for very few codes. This paper presents a generalization based on the “common-symbol decoding problem.” Suppose one is given M (possibly corrupted) codewords from M (possibly different) codes over the same field; suppose further that the codewords share a single symbol in common. The common-symbol decoding problem is that of estimating the symbol in the common position. This is equivalent to one-step majority logic decoding when each of the “constituent” codes is a simple parity check. This paper formulates conditions under which this decoding is possible and presents a simple algorithm that accomplishes the same. When applied to decoding cyclic block codes, this technique yields a decoder structure ideal for parallel implementation. Furthermore, this approach frequently results in a decoder capable of correcting more errors than one-step majority-logic decoding. To demonstrate the simplicity of the resulting decoders, an example is presented     

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.     

Note on majority-logic decoding of finite geometry codes (Corresp.)

In a recent paper [1], techniques for reducing the number of majority-logic decoding steps for finite geometry codes have been proposed. However, the lower bound of [1, lemma 4] is incorrect; finite geometry codes, in general, cannot be decoded in less than or equal to three steps of orthogonalization, as was claimed. This correspondence presents a decoding procedure for finite geometry codes that requires as few decoding steps as possible. It is shown that the minimum number of steps is a logarithmic function of the dimension of the associated geometry.     

Multifold Euclidean geometry codes

This paper presents a class of majority-logic decodable codes whose structure is based on the structural properties of Euclidean geometries (EG) and codes that are invariant under the affine group of permutations. This new class of codes contains the ordinary EG codes and some generalized EG codes as subclasses. One subclass of new codes is particularly interesting: they are the most efficient majority-logic decodable codes that have been constructed.     

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.     

Single-symbol maximum likelihood decodable linear STBCs

Space-time block codes (STBCs) from orthogonal designs (ODs) and coordinate interleaved orthogonal designs (CIOD) have been attracting wider attention due to their amenability for fast (single-symbol) maximum-likelihood (ML) decoding, and full-rate with full-rank over quasi-static fading channels. However, these codes are instances of single-symbol decodable codes and it is natural to ask, if there exist codes other than STBCs form ODs and CIODs that allow single-symbol decoding? In this paper, the above question is answered in the affirmative by characterizing all linear STBCs, that allow single-symbol ML decoding (not necessarily full-diversity) over quasi-static fading channels-calling them single-symbol decodable designs (SDD). The class SDD includes ODs and CIODs as proper subclasses. Further, among the SDD, a class of those that offer full-diversity, called Full-rank SDD (FSDD) are characterized and classified. We then concentrate on square designs and derive the maximal rate for square FSDDs using a constructional proof. It follows that 1) except for N=2, square complex ODs are not maximal rate and 2) a rate one square FSDD exist only for two and four transmit antennas. For nonsquare designs, generalized coordinate-interleaved orthogonal designs (a superset of CIODs) are presented and analyzed. Finally, for rapid-fading channels an equivalent matrix channel representation is developed, which allows the results of quasi-static fading channels to be applied to rapid-fading channels. Using this representation we show that for rapid-fading channels the rate of single-symbol decodable STBCs are independent of the number of transmit antennas and inversely proportional to the block-length of the code. Significantly, the CIOD for two transmit antennas is the only STBC that is single-symbol decodable over both quasi-static and rapid-fading channels.     

Suboptimum decoding of decomposable block codes

To decode a long block code with a large minimum distance by maximum likelihood decoding is practically impossible because the decoding complexity is simply enormous. However, if a code can be decomposed into constituent codes with smaller dimensions and simpler structure, it is possible to devise a practical and yet efficient scheme to decode the code. This paper investigates a class of decomposable codes, their distance and structural properties. It is shown that this class includes several classes of well-known and efficient codes as subclasses. Several methods for constructing decomposable codes or decomposing codes are presented. A two-stage (soft-decision or hard-decision) decoding scheme for decomposable codes, their translates or unions of translates is devised, and its error performance is analyzed for an AWGN channel. The two-stage soft-decision decoding is suboptimum. Error performances of some specific decomposable codes based on the proposed two-stage soft-decision decoding are evaluated. It is shown that the proposed two-stage suboptimum decoding scheme provides an excellent trade-off between the error performance and decoding complexity for codes of moderate and long block length     

TETRA中Reed-Muller码的大数逻辑译码方法

TETRA数字集群移动通信系统的物理层协议中采用了缩短Reed-Muller(RM)码,它与经典RM码的差异极大,无法采用Reed大数逻辑译码算法.根据正交校验矩阵的特点,提出了一种一般线性分组码的正交校验矩阵的穷举搜索算法.使用该算法搜索了缩短RM码的正交校验矩阵,对搜索速度进行了分析.证明了该码是两步完全可正交码,给出了它的Massey大数逻辑译码方法.仿真结果表明,无论是硬判决还是软判决,该译码方法的纠错性能都优于伴随式译码方法.     

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.     

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

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

High-rate burst-error-correcting recurrent codes (Corresp.)

A bound and construction are presented for high-rate burst-error-correcting recurrent codes. The bound is an upper bound on the block length in terms of the total redundancy used in decoding, the redundancy per block, and the burst length. The construction uses a block-code parity-check matrix as the first block of the recurrent code parity-check matrix. For a block code it is typical to find that only a portion of the redundancy need be used to detect a burst. Any block code for which this is true can be used in the construction. The recurrent code is then related as follows to the block code from which it is constructed. 1) The recurrent code block length is the same as the block-code block length. 2) The total redundancy used in decoding the recurrent code is the same as the block-code redundancy per block. 3) The recurrent code redundancy per block is the same as the block-code redundancy required for burst detection only. 4) The recurrent code is of higher rate than the block code. 5) The recurrent code requires a guard space between bursts but otherwise corrects the same bursts as the block code. It is shown that, when certain well-known cyclic codes are used in the construction, the resulting recurrent codes are close to the upper bound.     

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.     

Product accumulate codes: a class of codes with near-capacity performance and low decoding complexity

We propose a novel class of provably good codes which are a serial concatenation of a single-parity-check (SPC)-based product code, an interleaver, and a rate-1 recursive convolutional code. The proposed codes, termed product accumulate (PA) codes, are linear time encodable and linear time decodable. We show that the product code by itself does not have a positive threshold, but a PA code can provide arbitrarily low bit-error rate (BER) under both maximum-likelihood (ML) decoding and iterative decoding. Two message-passing decoding algorithms are proposed and it is shown that a particular update schedule for these message-passing algorithms is equivalent to conventional turbo decoding of the serial concatenated code, but with significantly lower complexity. Tight upper bounds on the ML performance using Divsalar's (1999) simple bound and thresholds under density evolution (DE) show that these codes are capable of performance within a few tenths of a decibel away from the Shannon limit. Simulation results confirm these claims and show that these codes provide performance similar to turbo codes but with significantly less decoding complexity and with a lower error floor. Hence, we propose PA codes as a class of prospective codes with good performance, low decoding complexity, regular structure, and flexible rate adaptivity for all rates above 1/2.     

Nonhomogeneous Trellis codes for the Quasi-Synchronous Multiple-Access Binary adder channel with Two Users

A trellis code is {em homogeneous} if the number of branches emanating from each node (or state) in the trellis diagram is constant. For example, convolutional codes are linear homogeneous trellis codes. A trellis code is {em nonhomogeneous} if the number of branches emanating from each node in the trellis diagram is not the same. The two-user binary adder channel is a multiple-access channel with two binary inputs,x_{1}andx_{2}, and one ternary output,y = x_{1} + x_{2}, where the addition is done in the real number field. The adder channel is synchronous if both encoders and the decoder maintain block (frame) synchronism. It is quasi-synchronous if the encoders do not start their blocks at the same time, but the decoder knows the position of each block. The difference between the starting times of the blocks is called the slippage. The channel is asynchronous if no block synchronism exists among the encoders and the decoder. Some uniquely decodable code pairs(C_{1}, C_{2})are presented that can be used to transmit information reliably over the quasi-synchronous binary adder channel with two users. One of the codes is a nonhomogeneous trellis code, the other is a common block code. Our code rates are better than Deaett-Wolf codes and are close to or equal to the asymptotic rates of Kasami {em et al}. A method for calculating the rates of nonhomogeneous trellis codes is described. An algorithm for finding more uniquely decodable code pairs for the quasi-synchronous binary adder channel is formulated.     

Leveraging coherent space-time codes for noncoherent communication via training

Training codes are introduced for the multiple-antenna, noncoherent, multiple block-Rayleigh-fading channel in which the fading coefficients, which are constant over a fixed number of dimensions (coherence interval) for each block and then change independently to a new realization, are known neither at the transmitter nor at the receiver. Each codeword of a training code consists of a part known to the receiver-used to form a minimum mean-squared error (MMSE) estimate of the channel-and a part that contains codeword(s) of a space-time block or trellis code designed for the coherent channel (in which the receiver has perfect knowledge of the channel). The channel estimate is used as if it were error-free for decoding the information-bearing part of the training codeword. Training codes are hence easily designed to have high rate and low decoding complexity by choosing the underlying coherent code to have high rate and to be efficiently decodable. Conditions for which the estimator-detector (E-D) receiver is equivalent to the optimal noncoherent receiver are established. A key performance analysis result of this paper is that the training codes when decoded with the E-D receiver achieve a diversity order of the error probability that is equal to the diversity order of the underlying coherent code. In some cases, the performance of training codes can be measured relative to coherent reception via "training efficiency," which is then optimized over the energy allocation between the training and data phases. In the limit of increasing block lengths, training codes always achieve the performance of coherent reception. The examples of training codes provided in this work have polynomial complexity in rate but an error rate comparable to the best performing unitary designs available, even though the latter require exponential decoding complexity.     

Majority-logic-like decoding of vector symbols

The use of the structure of one-step decodable majority logic codes for enhanced and simplified vector symbol decoding, such as outer code decoding of concatenated codes, is proposed. For J equations checking a particular symbol, the technique to be described almost always corrects the symbol if there are J-1 or fewer symbol errors, and often corrects cases of far more than J symbol errors. Ordinarily, majority level decoding with J equations for a symbol corrects the symbol in all cases where there are up to [J/2] errors. The decoding power is comparable to Reed-Solomon codes, but decoding is simpler than for Reed-Solomon codes     

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.     

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.