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.     

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.     

Ternary codes from some reflexive uniform subset graphs

We examine the ternary codes \(C_3(A_i+I)\) from matrices \(A_i+I\) where \(A_i\) is an adjacency matrix of a uniform subset graph \(\Gamma (n,3,i)\) of \(3\) -subsets of a set of size \(n\) with adjacency defined by subsets meeting in \(i\) elements of \(\Omega \) , where \(0 \le i \le 2\) . Most of the main parameters are obtained; the hulls, the duals, and other subcodes of the \(C_3(A_i+I)\) are also examined.     

Partial permutation decoding for MacDonald codes

We show how to find s-PD-sets of the minimal size \(s+1\) for the \(\left[ \frac{q^n-q^u}{q-1},n,q^{n-1}-q^{u-1}\right] _q \) MacDonald q-ary codes \(C_{n,u}(q)\) where \(n \ge 3\) and \(1 \le u \le n-1\). The construction of [6] can be used and gives s-PD-sets for s up to the bound \(\lfloor \frac{q^{n-u}-1}{(n-u)(q-1)} \rfloor -1\), of effective use for u small; for \(u \ge \lfloor \frac{n}{2} \rfloor \) an alternative construction is given that applies up to a bound that depends on the maximum size of a set of vectors in \(V_u(\mathbb {F}_q)\) with each pair of vectors distance at least 3 apart.     

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     

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     

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     

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.     

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码各个比特节点的出错概率,然后用已知信息替换易出错比特节点进行编码;该译码算法根据比特节点可靠性的差异,在译码时为每个比特节点赋予相应的权值,以调整它们对译码的影响程度.仿真表明,新的编译码算法使得系统性能大大提高,同时加快了译码迭代收敛速度.     

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

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

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

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

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

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

适合行列合并译码算法的LDPC码的构造

针对低密度奇偶校验(LDPC)码译码器使用行列合并(RCJ)译码算法时存在的流水线冲突问题,提出了一种构造适合行列合并译码算法的LDPC码的方法。该构造方法在渐进添边(PEG)构造算法的基础上,加入行运算顺序的约束条件,使得利用该算法构造的LDPC码在行运算顺序上相邻两行内的非零块不同时共用一列,从而避免了硬件布局布线冲突,减少了流水线延时,提高了译码速率。仿真结果表明,用这种方法构造的LDPC码与全球微波互联接入(WiMAX)标准给出的LDPC码的译码性能相当,而且有效地减少了译码迭代次数,降低了硬件实现复杂度,提高了LDPC译码器吞吐率。     

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.     

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.     

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.     

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.     

有限长低密度奇偶校验码的去环分析

针对低密度奇偶校验码(LDPC)中环的存在影响LDPC码性能的问题,研究了基于校验阵的有限长LDPC码的去环和优化,指出搜索随机矩阵的方法比较直观,但计算量是码长和列重乘积的指数函数.给出了搜索并替换的去环方法,该方法能够显著减小短环对译码性能的影响.计算机仿真结果表明,去除长度为4和6的环能够在误比特率为10-5时获得0 5dB的编码增益.讨论了去环图的优化和判定准则,计算机仿真结果表明,优选的去环编码方案的性能要好于未经优选的方案.