Lattice constellations and codes from quadratic number fields

We propose new classes of linear codes over integer rings of quadratic extensions of Q, the field of rational numbers. The codes are considered with respect to a Mannheim metric, which is a Manhattan metric module a two-dimensional (2-D) grid, in particular, codes over Gaussian integers and Eisenstein-Jacobi integers are extensively studied. Decoding algorithms are proposed for these codes when up to two coordinates of a transmitted code vector are affected by errors of arbitrary Mannheim weight. Moreover, we show that the proposed codes are maximum-distance separable (MDS), with respect to the Hamming distance. The practical interest in such Mannheim-metric codes is their use in coded modulation schemes based on quadrature amplitude modulation (QAM)-type constellations, for which neither the Hamming nor the Lee metric is appropriate     

Multiple-phase codes for detection without carrier phase reference

We consider the construction and analysis of linear block codes for M-ary phase-shift keying that can be decoded without carrier phase synchronization. Under these circumstances, the function that has a significant impact on performance is the noncoherent distance, analogous to the Euclidean distance for the coherent case. The major difficulty in constructing and analyzing such codes lies in the fact that the noncoherent distance is not a true metric. For this reason, prior work mainly relies on numerical approaches to search for good codes and to determine the corresponding minimum noncoherent distance. We first present a theorem that links the noncoherent distance with the Euclidean and Lee (1958) distances. This theorem allows us to construct good codes and determine their minimum noncoherent distances analytically. Based on this theorem, we classify the codes whose duals consist of a cyclic group. These codes are of minimum redundancy. We further investigate codes with the flavor of Hamming and shortened Hamming codes. Many of these new codes provide significantly larger coding gains than previously known codes. Linear codes derived from code-division multiple-access (CDMA) sequences are considered as well. These codes in general provide rather large coding gains. Finally, an algorithm is introduced that can be appended to any suboptimal decoding technique to enhance the performance     

环F2+uF2上长度为2e的循环码的距离

确定码字的Hamming距离和Lee距离是解码的关键.本文对环F₂+uF₂上长度为2^e的循环码的结构进行了分类.确定了环F₂+uF₂上某些长度为2^e的循环码的Hamming距离和Lee距离.给出了环F₂+uF₂上长度为2^e的其它循环码的Hamming距离的上界及Lee距离的上界和下界.     

On Decoding Binary Perfect and Quasi-Perfect Codes over Markov Noise Channels

We study the decoding problem when a binary linear perfect or quasi-perfect code is transmitted over a binary channel with additive Markov noise. After examining the properties of the channel block transition distribution, we derive sufficient conditions under which strict maximum-likelihood decoding is equivalent to strict minimum Hamming distance decoding when the code is perfect. Additionally, we show a near equivalence relationship between strict maximum likelihood and strict minimum distance decoding for quasi-perfect codes for a range of channel parameters and the code's minimum distance. As a result, an improved (complete) minimum distance decoder is proposed and simulations illustrating its benefits are provided.     

Efficient Error Control Decoder Architectures for Noncoherent Random Linear Network Coding

Random linear network coding is an efficient technique for disseminating information in networks, but it is highly susceptible to errors. Kötter-Kschischang (KK) codes and Mahdavifar-Vardy (MV) codes are two important families of subspace codes that provide error control in noncoherent random linear network coding. List decoding has been used to decode MV codes beyond half distance. Existing hardware implementations of the rank metric decoder for KK codes suffer from limited throughput, long latency and high area complexity. The interpolation-based list decoding algorithm for MV codes still has high computational complexity, and its feasibility for hardware implementations has not been investigated. In this paper we propose efficient decoder architectures for both KK and MV codes and present their hardware implementations. Two serial architectures are proposed for KK and MV codes, respectively. An unfolded decoder architecture, which offers high throughput, is also proposed for KK codes. The synthesis results show that the proposed architectures for KK codes are much more efficient than rank metric decoder architectures, and demonstrate that the proposed decoder architecture for MV codes is affordable.     

Lower bound on minimum lee distance of algebraic?geometric codes over finite fields

Algebraic-geometric (AG) codes over finite fields with respect to the Lee metric have been studied. A lower bound on the minimum Lee distance is derived, which is a Lee-metric version of the well-known Goppa bound on the minimum Hamming distance of AG codes. The bound generalises a lower bound on the minimum Lee distance of Lee-metric BCH and Reed-Solomon codes, which have been successfully used for protecting against bitshift and synchronisation errors in constrained channels and for error control in partial-response channels.     

Turbo乘积码构造方法的研究

Turbo乘积码因其具有接近香农限的译码性能和适合高速译码的并行结构,已成为纠错编码领域的研究热点。Turbo乘积码的分量码一般由扩展汉明码构造而成,所以该类码字编码和译码的硬件实现比较简单。当Turbo乘积码采用扩展汉明码作为子码时,随着信噪比的提高,码字的最小码重对误帧率的影响会逐步增大。文中改进了Turbo乘积码编码结构,在只增加较小的编译码复杂度和时延的情况下,提高了码字的最小码重,并减少了最小码重码字在码字空间所占的比例。通过仿真和分析,比较了这种码和TPC码在误帧率性能、码字的最小码重分布以及最小码间距估计上的差异。     

Estimating the fraction of erasure patterns correctable by linear codes

The conditional probability (fraction) of the successful decoding of erasure patterns of high (greater than the code distance) weights is investigated for linear codes with the partially known or unknown weight spectra of code words. The estimated conditional probabilities and the methods used to calculate them refer to arbitrary binary linear codes and binary Hamming, Panchenko, and Bose–Chaudhuri–Hocquenghem (BCH) codes, including their extended and shortened forms. Error detection probabilities are estimated under erasure-correction conditions. The product-code decoding algorithms involving the correction of high weight erasures by means of component Hamming, Panchenko, and BCH codes are proposed, and the upper estimate of decoding failure probability is presented.     

A new sequential decoding algorithm based on branch metric

A new sequential decoding algorithm with an adjustable threshold and a new method of moving through the decoding tree is proposed. Instead of the path metric of the conventional sequential decoding algorithms, the proposed algorithm uses a branch metric based on maximum-likelihood criterion. Two new parameters, the jumping-back distance and going-back distance, are also introduced. The performance of the algorithm for long constraint length convolutional codes is compared to those of the other sequential decoding algorithms and the Viterbi algorithm. The results show that the proposed algorithm is a good candidate for decoding of convolutional codes due to its fast decoding capability and good bit error rate (BER) performance. This work was supported in part by the Research Foundation at Karadeniz Technical University under Grant 2004.112.004.01 and 2005.112.009.2.     

A robust decoding for long convolutional codes

Sequential decoding is an attractive technique to achieve the reliability of communication promised by the channel coding theory. But, because it utilizes the Fano metric, its performance is sensitive to channel parameter variations and it cannot simultaneously minimize both decoding effort and probability of decoding error. Based on the distance properties of the codes, we have derived a new set of metric which not only can overcome the two drawbacks caused by the Fano metric but also can significantly reduce the decoding effort required by sequential decoding.     

北斗导航信号BCH译码器中校正子辅助的列表译码算法

针对北斗卫星导航系统B1I信号中的BCH译码问题,该文提出一种校正子辅助的列表译码算法。首先,以校正子和汉明重量为准则构造若干错误模式列表;然后根据接收数据硬判决的校正子选择对应的错误模式列表;最后按照相关函数差测度搜索最优错误模式并译码。仿真结果表明,校正子辅助的列表译码算法在误码率10-5时,与最大似然译码算法的信噪比仅差0.08 dB,说明该方法是北斗B1I信号BCH码的一种近优译码方法;另外,该方法具有线性复杂度和可并行实现的特点。     

Lee metric decoding of alternant codes over /spl Zopf//sub q/

A multi-stage Lee metric list decoding approach for alternant codes over /spl Zopf/(p/sup l/ )where p is prime and l/spl ges/2 is proposed. It is demonstrated that the error-correcting capability of such a decoding scheme increasingly surpasses that of a single-stage decoding approach as the length of the code and l increases.     

Multilevel turbo coding with short interleavers

The impact of the interleaver, embedded in the encoder for a parallel concatenated code, called the turbo code, is studied. The known turbo codes consist of long random interleavers, whose purpose is to reduce the value of the error coefficients. It is shown that an increased minimum Hamming distance can be obtained by using a structured interleaver. For low bit-error rates (BERs), we show that the performance of turbo codes with a structured interleaver is better than that obtained with a random interleaver. Another important advantage of the structured interleaver is the short length required, which yields a short decoding delay and reduced decoding complexity (in terms of memory). We also consider the use of turbo codes as component codes in multilevel codes. Powerful coding structures that consist of two component codes are suggested. Computer simulations are performed in order to evaluate the reduction in coding gain due to suboptimal iterative decoding. From the results of these simulations we deduce that the degradation in the performance (due to suboptimal decoding) is very small     

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     

Pseudo-Codeword Analysis of Tanner Graphs From Projective and Euclidean Planes

We consider coded data transmission over a binary-input output-symmetric memoryless channel using a binary linear code. In order to understand the performance of maximum-likelihood (ML) decoding, one studies the codewords, in particular the minimal codewords, and their Hamming weights. In the context of linear programming (LP) decoding, one's attention needs to be shifted to the pseudo-codewords, in particular, to the minimal pseudo-codewords and their pseudo-weights. In this paper, we investigate some families of codes that have good properties under LP decoding, namely certain families of low-density parity-check (LDPC) codes that are derived from projective and Euclidean planes: we study the structure of their minimal pseudo-codewords and give lower bounds on their pseudo-weight. Besides this main focus, we also present some results that hold for pseudo-codewords and minimal pseudo-codewords of any Tanner graph, and we highlight how the importance of minimal pseudo-codewords under LP decoding varies depending on which binary-input output-symmetric memoryless channel is used.     

Fast generalized minimum-distance decoding of algebraic-geometryand Reed-Solomon codes

Generalized minimum-distance (GMD) decoding is a standard soft-decoding method for block codes. We derive an efficient general GMD decoding scheme for linear block codes in the framework of error-correcting pairs. Special attention is paid to Reed-Solomon (RS) codes and one-point algebraic-geometry (AG) codes. For RS codes of length n and minimum Hamming distance d the GMD decoding complexity turns out to be in the order O(nd), where the complexity is counted as the number of multiplications in the field of concern. For AG codes the GMD decoding complexity is highly dependent on the curve in consideration. It is shown that we can find all relevant error-erasure-locating functions with complexity O(o₁nd), where o₁ is the size of the first nongap in the function space associated with the code. A full GMD decoding procedure for a one-point AG code can be performed with complexity O(dn²)     

基于SISO的LDPC码盲译码算法研究

针对传统BP译码算法需要初始条件的缺点,本文提出了一种基于软输入软输出(SISO)的LDPC码盲译码算法,所提算法采用类似BP迭代译码算法步骤,通过对距离信息进行迭代处理,实现无需接收信号的信噪比和信道状态即可译码;同时,还将所提盲译码算法推广到多进制LDPC码的译码应用中。本文所提盲译码算法在初始状态难以确定以及接收信号信噪比难以估计的通信信道中具有重要价值。仿真结果表明,所提算法不论是在AWGN信道还是在瑞利衰落信道上都能取得优良的性能,不论是与标准BP译码算法还是与分层BP译码算法相比,在性能相近的情况下,计算复杂度都有所降低。     

On algebraic decoding of the Z4-linear Goethals-likecodes

The Z₄-linear Goethals-like code of length 2^m has 2^2m+1-3m-2 codewords and minimum Lee distance 8 for any odd integer m⩾3. We present an algebraic decoding algorithm for all Z₄-linear Goethals-like codes C_k introduced by Helleseth et al.(1995, 1996). We use Dickson polynomials and their properties to solve the syndrome equations     

Graphical codes revisited

The set of all even subgraphs of a connected graph G on p vertices with q edges forms a binary linear code C=C_E(G) with parameters [q,q-p+1,g], where g is the girth of G. Such codes were studied systematically by Bredeson and Hakimi (1967) and Hakimi and Bredeson (1968) who were concerned with the problems of augmenting C to a larger [q,k,g]-code and of efficiently decoding such augmented graphical codes. We give a new approach to these problems by requiring the augmented codes to be graphical. On one hand, we present two construction methods which turn out to contain the methods proposed by Hakimi and Bredeson as special cases. As we show, this not only gives a better understanding of their construction, it also results in augmenting codes of larger dimension. We look at the case of 1-error-correcting graphical codes in some detail. In particular, we show how to obtain the extended Hamming codes as “purely” graphical codes by our approach. On the other hand, we follow a suggestion of Ntafos and Hakimi (1981) and use techniques from combinatorial optimization to give decoding procedures for graphical codes which turn out to be considerably more efficient than the approach via majority logic decoding proposed by Bredeson and Hakimi. We also consider the decoding problem for the even graphical code based on the complete graph K_2n in more detail: we discuss an efficient hardware implementation of an encoding/decoding scheme for these codes and show that things may be arranged in such a way that one can also correct all adjacent double errors. Finally, we discuss nonlinear graphical codes     

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.