Two new decoding algorithms for Reed-Solomon codes

The subject of decoding Reed-Solomon codes is considered. By reformulating the Berlekamp and Welch key equation and introducing new versions of this key equation, two new decoding algorithms for Reed-Solomon codes will be presented. The two new decoding algorithms are significant for three reasons. Firstly the new equations and algorithms represent a novel approach to the extensively researched problem of decoding Reed-Solomon codes. Secondly the algorithms have algorithmic and implementation complexity comparable to existing decoding algorithms, and as such present a viable solution for decoding Reed-Solomon codes. Thirdly the new ideas presented suggest a direction for future research. The first algorithm uses the extended Euclidean algorithm and is very efficient for a systolic VLSI implementation. The second decoding algorithm presented is similar in nature to the original decoding algorithm of Peterson except that the syndromes do not need to be computed and the remainders are used directly. It has a regular structure and will be efficient for implementation only for correcting a small number of errors. A systolic design for computing the Lagrange interpolation of a polynomial, which is needed for the first decoding algorithm, is also presented.This research was supported by a grant from the Canadian Institute for Telecommunications Research under the NCE program of the Government of Canada     

List decoding of repeated codes

Assuming that we have a soft-decision list decoding algorithm of a linear code, a new hard-decision list decoding algorithm of its repeated code is proposed in this article. Although repeated codes are not used for encoding data, due to their parameters, we show that they have a good performance with this algorithm. We compare, by computer simulations, our algorithm for the repeated code of a Reed–Solomon code against a decoding algorithm of a Reed–Solomon code. Finally, we estimate the decoding capability of the algorithm for Reed–Solomon codes and show that performance is somewhat better than our estimates.     

Modified sum-product algorithms for decoding low-density parity-check codes

The authors deal with the sum-product algorithm (SPA) based on the hyperbolic tangent (tanh) rule when it is applied for decoding low-density parity-check (LDPC) codes. Motivated by the finding that, because of the large number of multiplications required by the algorithm, an overflow in the decoder may occur, two novel modifications of the tanh function (and its inverse) are proposed. By means of computer simulations, both methods are evaluated using random-based LDPC codes with binary phase shift keying (BPSK) signals transmitted over the additive white Gaussian noise (AWGN) channel. It is shown that the proposed modifications improve the bit error rate (BER) performance up to 1 dB with respect to the conventional SPA. These results have also shown that the error floor is removed at BER lower than 10^-6. Furthermore, two novel approximations are presented to reduce the computational complexity of the tanh function (and its inverse), based on either a piecewise linear function or a quantisation table. It is shown that the proposed approximations can slightly improve the BER performance (up to 0.13 dB) in the former case, whereas small BER performance degradation is observed (<0.25 dB) in the latter case. In both cases, however, the decoding complexity is reduced significantly     

Construction and decoding of matrix-product codes from nested codes

We consider matrix-product codes ${[C_1\cdots C_s] \cdot A}$ , where ${C_1, \ldots , C_s}$ are nested linear codes and matrix A has full rank. We compute their minimum distance and provide a decoding algorithm when A is a non-singular by columns matrix. The decoding algorithm decodes up to half of the minimum distance.     

Improved parallel weighted bit-flipping decoding algorithm for LDPC codes

Aiming at seeking a low-complexity decoder with fast decoding convergence speed for short or medium low-density parity-check (LDPC) codes, an improved parallel weighted bit-flipping (IPWBF) algorithm, which is applied flexibly for two classes of codes is presented here. For LDPC codes with low column weight in their parity check matrix, both bootstrapping and loop detection procedures, described in the existing literature, are included in IPWBF. Furthermore, a novel delay-handling procedure is introduced to prevent the codeword bits of high reliability from being flipped too hastily. For large column weight finite geometry LDPC codes, only the delay-handling procedure is included in IPWBF to show its effectiveness. Extensive simulation results demonstrate that the proposed algorithm achieves a good tradeoff between performance and complexity.     

基于比特可靠性的LDPC码编译码算法

提出了一种基于比特可靠性的低密度奇偶校验(LDPC)码编码算法和一种加权置信传播(BP)译码算法.该编码算法首先利用蒙特卡罗仿真得到LDPC码各个比特节点的出错概率,然后用已知信息替换易出错比特节点进行编码;该译码算法根据比特节点可靠性的差异,在译码时为每个比特节点赋予相应的权值,以调整它们对译码的影响程度.仿真表明,新的编译码算法使得系统性能大大提高,同时加快了译码迭代收敛速度.     

LT码的一种BP/ML混合译码算法

针对LT码在短信息字长度时采用置信传播(BP)译码和最大似然(ML)译码存在大的性能差异问题,提出了一种BP/ML混合译码算法来实现LT码在二进制删除信道(BEC)中译码复杂度和性能的合理折中.此算法在BP译码失败时只需运用ML译码确定少数猜测比特就可实现成功译码.仿真结果显示,相比于BP译码,BP/ML混合译码的译码...     

Permutation decoding of codes from generalized Paley graphs

The generalized Paley graphs $\text{ GP }(q,k)$ GP ( q , k ) are a generalization of the well-known Paley graphs. Codes derived from the row span of adjacency and incidence matrices from Paley graphs have been studied in Ghinellie and Key (Adv Math Commun 5(1):93–108, 2011) and Key and Limbupasiriporn (Congr Numer 170:143–155, 2004). We examine the binary codes associated with the incidence designs of the generalized Paley graphs obtaining the code parameters $[\frac{qs}{2}, q-1, s]$ [ q s 2 , q - 1 , s ] or $[qs, q-1,2s]$ [ q s , q - 1 , 2 s ] where $s=\frac{q-1}{k}$ s = q - 1 k . By finding explicit PD-sets we show that these codes can be used for permutation decoding.     

Fast decoding of non-binary first order Reed-Muller codes

A minimum distance decoding algorithm for non-binary first order Reed-Muller codes is described. Suggested decoding is based on a generalization of the fast Hadamard transform to the non-binary case. We also propose a fast decoding algorithm for non-binary first order Reed-Muller codes with complexity proportional to the length of the code. This algorithm provides decoding within the limits guaranteed by the minimum distance of the code.Partly supported by the Guastallo Fellowship. This work was presented in part at the 9th International Symposium Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, New Orleans, USA, October 1991     

Tradeoff of complexity and latency of iterative decoding for orthogonal convolutional codes

The complexities and latencies of iterative belief propagation (BP) and threshold decoding techniques for a new class of convolutional self-orthogonal codes are analysed using forward-only pipeline architectures. Computer simulation results show that over the additive white Gaussian noise channel at moderate signal- to-noise ratios, BP decoding yields one half the decoding delay when compared with threshold decoding at essentially the same error performances. However, the reduction in the decoding delay using BP is obtained at the cost of an increase of the implementation complexity.     

Gradient projection decoding of LDPC codes and algorithmic variations

The current study proposes decoding algorithms for low density parity check codes (LDPC), which offer competitive performance-complexity trade-offs relative to some of the most efficient existing decoding techniques. Unlike existing low-complexity algorithms, which are essentially reduced complexity variations of the classical belief propagation algorithm, starting point in the developed algorithms is the gradient projections (GP) decoding technique, proposed by Kasparis and Evans (2007). The first part of this paper is concerned with the GP algorithm itself, and specifically with determining bounds on the step-size parameter, over which convergence is guaranteed. Consequently, the GP algorithm is reformulated as a message passing routine on a Tanner graph and this new formulation allows development of new low-complexity decoding routines. Simulation evaluations, performed mainly for geometry-based LDPC constructions, show that the new variations achieve similar performances and complexities per iteration to the state-of-the-art algorithms. However, the developed algorithms offer the implementation advantages that the memory-storage requirement is significantly reduced, and also that the performance and convergence speed can be finely traded-off by tuning the step-size parameter.     

极化码译码算法研究现状及发展前景

极化码是目前唯一被理论证明可以达到香农极限的线性纠错信道编码,已经成为5G标准的信道编码技术方案.针对具有线性复杂度的接续删除译码算法进行了仿真.针对接续删除算法的高译码时延,深入研究了每个时钟周期的计算特点,并且介绍了各种改进方案.针对上述存在的不足进行分析和总结得到了新的研究方向,最后说明了极化码与LDPC码、Turbo码多模译码器的研究可行性.     

Random-iteration algorithm-based optical parallel architecture for fractal-image decoding by use of iterated-function system codes

An optical parallel architecture for the random-iteration algorithm to decode a fractal image by use of iterated-function system (IFS) codes is proposed. The code value is first converted into transmittance in film or a spatial light modulator in the optical part of the system. With an optical-to-electrical converter, electrical-to-optical converter, and some electronic circuits for addition and delay, we can perform the contractive affine transformation (CAT) denoted in IFS codes. In the proposed decoding architecture all CAT's generate points (image pixels) in parallel, and these points then are joined for display purposes. Therefore the decoding speed is improved greatly compared with existing serial-decoding architectures. In addition, an error and stability analysis that considers nonperfect elements is presented for the proposed optical system. Finally, simulation results are given to validate the proposed architecture.     

基于协同优化算法的Reed-Solomon码迭代软判决译码

基于协同优化算法推导出一种Reed-Solomon(RS)码的迭代软判决译码(SDD)算法。该算法属于消息传递算法,具有严格的理论基础。仿真结果表明,该算法相对于硬判决译码(HDD)能够获得有效的软判决译码增益,对于(15,9)RS码在误帧率(FER)为4×10-4时有0.3~1.3dB的增益;同时译码复杂度低,具有很好的工程实用性。此外该算法是一类软输入软输出(SISO)译码算法,能够应用于以RS码为子码的复合码,如级连码和乘积码的迭代译码。     

Gröbner basis approach to list decoding of algebraic geometry codes

We show how our Gröbner basis algorithm, which was previously applied to list decoding of Reed Solomon codes, can be used in the hard and soft decision list decoding of Algebraic Geometry codes. In addition, we present a linear functional version of our Gröbner basis algorithm in order to facilitate comparisons with methods based on duality.     

Viterbi decoding and the power spectral densities of some rate one half binary DC free modulation codes

The Hamming distance properties are investigated, and some experimental results obtained with the following R = 1/2 binary dc free modulation codes are presented: the (b, l, C) = (1, 5, 3) Miller²code and codes with (b, l, C), respectively, (1, 4, 3), (0, 3, 3), and (0, 1, 2). A R = 3/6, (b, l, C) = (0, 3, 2) combined error-correcting/ modulation code is also investigated. State systems, power spectral densities, and the bit error rates after computer simulated decoding of these codes on both the binary symmetric channel and a burst erasure channel are presented.     

Indirect decoding edges for one-shot shape acquisition

Determining the correspondence in coded structured light is challenging, but it is very important in one-shot techniques for 3D shape reconstruction. The problem of decoding stripe patterns can be modeled as matching two code sequences. We propose decoding edges indirectly based on the property of the stripe pattern, which can be represented as edge code, color code, or mixed code sequences. While traditional methods match two edge code sequences, indirect decoding matches two color sequences or mixed code sequences. The advantages of the proposed method, including a higher Hamming distance, enforced local coherence, and more code information, make indirect decoding excellent in performance. Previously, the lack of ground truth has prevented direct comparisons of different decoding algorithms. Here we obtain six benchmark datasets using the robust space-time analysis. Five decoding methods are quantitatively evaluated using the ground truth. The comparison results show that our method is robust for complex code situations and that it outperforms the state-of-the-art technique in this area.     

矿用云台解码驱动器的设计

针对矿用云台解码驱动器工作环境恶劣的情况 ,采用MSP4 30芯片作为主要接收控制芯片 ,设计了矿用云台解码驱动器 ;同时 ,采用固态继电器 ,增强安全可靠性。