Soft-decision decoding of Reed-Muller codes as generalized multipleconcatenated codes

Constructs Reed-Muller codes by generalized multiple concatenation of binary block codes of length 2. As a consequence of this construction, a new decoding procedure is derived that uses soft-decision information. The algorithm is designed for low decoding complexity and is applicable to all Reed-Muller codes. It gives better decoding performance than soft-decision bounded-distance decoding. Its decoding complexity is much lower than that of maximum-likelihood trellis decoding of Reed-Muller codes, especially for long codes     

Class of majority decodable real-number codes

A majority decoding algorithm for a class of real-number codes is presented. Majority decoding has been a relatively simple and fast decoding technique for codes over finite fields. When applied to decode real-number codes, the robustness of the majority decoding to the presence of background noise, which is usually an annoying problem for existing decoding algorithms for real-number codes, is its most prominent property. The presented class of real-number codes has generator matrices similar to those of the binary Reed-Muller codes and is decoded by similar majority logic     

Decoding with Early Termination for Raptor Codes

Rateless codes, and especially Raptor codes, have received considerable attention in the recent past due to their inherent ability to adapt to channel conditions and their capacity- approaching performance. Since decoding of rateless codes typically involves multiple decoding attempts, early termination of such attempts is mandatory for overall efficient decoding. In this letter, we propose a new decoding scheme with early termination that is particularly suited for rateless codes. Simulation results for the example of the binary symmetric channel show complexity reductions (in terms of the total required number of decoding iterations) by 87% compared to conventional message-passing decoding and 54% compared to a recently proposed incremental decoding scheme for Raptor codes.     

New decoding algorithm for Reed - Muller codes (Corresp.)

We interpret Reed-Muller codes in terms of superimposition and present a new decoding algorithm for Reed-Muller codes. Before presenting this algorithm, we propose a decoding algorithm for a class of simple iterated codes (SI codes) that will play an important role in our new decoding algorithm. Finally, we compare our algorithm with the conventional algorithm for the cyclic Reed-Muller codes from the standpoint of decoding delay.     

基于删余等效的高码率卷积码的低复杂度译码方法

根据删余卷积码具有较低的译码复杂度这一特征,提出了一种适用于普通高码率卷积码的低复杂度译码方法。通过多项式生成矩阵表示法,推导了删余卷积码的等效多项式生成矩阵,给出了等效多项式生成矩阵的计算准则。在分析删余卷积码与相同码率普通卷积码的等效关系和区别的基础上,提出了高码率卷积码的删余等效并给出了计算高码率卷积码删余等效后原始码和删余矩阵的方法。以原始码和删余矩阵构成的删余等效结构为译码基础,实现了高码率卷积码的低复杂度译码,其译码复杂度与原始码相当。仿真结果表明,删余等效译码方法相对于正常译码方法,其性能损失很小。     

Symbol-by-symbol MAP decoding algorithm for high-rate convolutionalcodes that use reciprocal dual codes

A symbol-by-symbol maximum a posteriori (MAP) decoding algorithm for high-rate convolutional codes applying reciprocal dual convolutional codes is presented. The advantage of this approach is a reduction of the computational complexity since the number of codewords to consider is decreased. All requirements for iterative decoding schemes are fulfilled. Since tail-biting convolutional codes are equivalent to quasi-cyclic block codes, the decoding algorithm for truncated or terminated convolutional codes is modified to obtain a soft-in/soft-out decoder for high-rate quasi-cyclic block codes which also uses the dual code because of complexity reasons. Additionally, quasi-cyclic block codes are investigated as component codes for parallel concatenation. Simulation results obtained by iterative decoding are compared with union bounds for maximum likelihood decoding. The results of a search for high-rate quasi-cyclic block codes are given in the appendix     

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     

On decoding unequal error protection product codes

The decoding of unequal error protection product codes, which are a combination of linear unequal error protection (UEP) codes and product codes, is addressed. A nonconstructive proof of the existence of a good error-erasure-decoding algorithm is presented; however, obtaining the decoding procedure is still an open research problem. A particular subclass of UEP product codes is considered, including a decoding algorithm that is an extension of the Blokh-Zyablov decoding algorithm for product codes. For this particular subclass the decoding problem is solved     

Iterative decoding of one-step majority logic deductible codesbased on belief propagation

Previously, the belief propagation (BP) algorithm has received a lot of attention in the coding community, mostly due to its near-optimum decoding for low-density parity check (LDPC) codes and its connection to turbo decoding. In this paper, we investigate the performance achieved by the BP algorithm for decoding one-step majority logic decodable (OSMLD) codes. The BP algorithm is expressed in terms of likelihood ratios rather than probabilities, as conventionally presented. The proposed algorithm fits better the decoding of OSMLD codes with respect to its numerical stability due to the fact that the weights of their check sums are often much higher than that of the corresponding LDPC codes. Although it has been believed that OSMLD codes are far inferior to LDPC codes, we show that for medium code lengths (say between 200-1000 bits), the BP decoding of OSMLD codes can significantly outperform BP decoding of their equivalent LDPC codes. The reasons for this behavior are elaborated     

Codes defined on graphs

Low-density parity-check codes, turbo codes, and indeed most practically decodable capacity-approaching error correcting codes can all be understood as codes defined on graphs. Graphs not only describe the codes, but, more important, they structure the operation of the sum-product decoding algorithm (or one of many possible variations), which can be used for iterative decoding. Such coding schemes have the potential to approach channel capacity, while maintaining reasonable decoding complexity. In this tutorial article we review factor graphs, which can be used to describe codes and the joint probability distributions that must be dealt with in decoding. We also review the sum-product algorithm, and show how this algorithm leads to iterative decoding algorithms for codes defined on graphs.     

Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

Maximum-likelihood decoding is one of the central algorithmic problems in coding theory. It has been known for over 25 years that maximum-likelihood decoding of general linear codes is NP-hard. Nevertheless, it was so far unknown whether maximum-likelihood decoding remains hard for any specific family of codes with nontrivial algebraic structure. In this paper, we prove that maximum-likelihood decoding is NP-hard for the family of Reed-Solomon codes. We moreover show that maximum-likelihood decoding of Reed-Solomon codes remains hard even with unlimited preprocessing, thereby strengthening a result of Bruck and Naor.     

大约束度卷积码快速译码方法的研究

针对Viterbi译码算法的计算复杂度随着卷积码约束长度的增加呈指数增加,译码延迟过大,只适用于约束长度较小的卷积码译码的缺陷,提出了适用于大约束度的卷积码译码方法.采用了改进粒子群优化算法,弥补传统粒子群优化算法在解决离散问题方面的缺陷--对卷积码快速译码.该方法通过设定种群规模M来确定译码路径数,极大地缩小了译码网格中的路径搜索范围,使译码延迟减小,更适用于约束长度较大的卷积码.还提出了译码宽度自适应的卷积码译码方法,对Viterbi译码算法进行了改进,把固定的译码路径宽度改进为随信道噪声的变化而变化,大大降低译码计算复杂度.仿真实验表明提出的2种译码方法的有效性.     

On decoding of low-density parity-check codes over the binary erasure channel

This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.     

Gaussian integers and interleaved rank codes for space–time block codes

This paper presents the design of space–time block codes (STBCs) over maximum rank distance (MRD) codes, energy‐efficient STBCs, STBCs using interleaved‐MRD codes, the use of Gaussian integers for STBCs modulation, and Gabidulin's decoding algorithm for decoding STBCs. The design fundamentals of STBCs using MRD codes are firstly put forward for different number of transmit antennas. Extension finite fields (Galois fields) are used to design these linear block codes. Afterward, a comparative study of MRD‐based STBCs with corresponding orthogonal and quasi‐orthogonal codes is also included in the paper. The simulation results show that rank codes, for any number of transmit antennas, exhibit diversity gain at full rate contrary to orthogonal codes, which give diversity gain at full rate only for two transmit antennas case. Secondly, an energy‐efficient MRD‐STBC is proposed, which outperforms orthogonal STBC at least for 2 × 1 antenna system. Thirdly, interleaved‐MRD codes are used to construct higher‐order transmit antenna systems. Using interleaved‐MRD codes further reduces the complexity (compared with normal MRD codes) of the decoding algorithm. Fourthly, the use of Gaussian integers is utilized in mapping MRD‐based STBCs to complex constellations. Furthermore, it is described how an efficient and computationally less complex Gabidulin's decoding algorithm can be exploited for decoding complex MRD‐STBCs. The decoding results have been compared against hard‐decision maximum likelihood decoding. Under this decoding scheme, MRD‐STBCs have been shown to be potential candidate for higher transmit antenna systems as the decoding complexity of Gabidulin's algorithm is far less, and its performance for decoding MRD‐STBCs is somewhat reasonable. Copyright © 2015 John Wiley & Sons, Ltd.     

TRELLIS STRUCTURES OF BLOCK CODES AND THEIR DECODING

Trellis structures of block codes are discussed. L-section trellis structures of some BCH codes are presented. A fast maximum likelihood decoding algorithm for BCH codes is proposed correspondingly, the decoding problem of q-ary images of qm-ary block codes is also discussed. The direct-sum partition and the associated decoding algorithms are given for the images.     

Soft-decision and erasure decoding in fast frequency-hoppingsystems with convolutional, turbo, and Reed-Solomon codes

In this contribution we present an exhaustive treatment of various coding and decoding techniques for use in fast frequency-hopping/multiple frequency shift keying multiple-access systems. One of the main goals is to show how reliability information on each received bit can be derived to enable soft-decision decoding. Convolutional codes as well as turbo codes are considered applying soft-decision, erasure, and hard-decision decoding. Their performance is compared to that of previously proposed Reed-Solomon with either errors-only or errors-and-erasures decoding. A mobile radio environment yielding a frequency-selective fading channel is assumed. It is shown that the application of turbo codes and convolutional codes with soft decision decoding can allow for a comparable number of simultaneously transmitting users to Reed-Solomon codes with errors-and-erasures decoding. Furthermore, the advantage of soft decisions is shown, which can be applied to a widely and growing range of channel codes. The pertinent technique of calculating soft decisions is described in the paper     

Decoding spherical codes for the Gaussian channel

A decoding algorithm for permutation codes that is equivalent to maximum-likelihood decoding, but less complex than the correlation decoder, is presented. A general construction for iteratively maximum-likelihood decodable (IMLD) codes is proved and used to construct IMLD codes for every dimension n. D. Slepian (1965) defined permutation modulation codes and presented an efficient algorithm for their decoding. Slepian's decoding scheme is one of the principal components of the permutation code decoding algorithm presented     

Generalized minimum distance decoding algorithms forQary output channels (Corresp.)

A new condition for a generalized minimum distance decoder to guarantee correct decoding is developed. Based on this condition, decoding algorithms for block codes, product codes, and completely orthogonalizable codes onQary output channels are presented. The results of computer simulations comparing the performance of these decoding algorithms with several other soft-decision decoding algorithma are also presented.     

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