几类格的快速译码

本文通过研究１６维Ｂａｒｎｅｓ－Ｗａｌｌ格和基于构造Ａ的二元线性分组码、四元线性分组码的导出格的代数结构，将这些格的译码问题转化为在相应码的格图上求最短路径的问题，从而提出了这些格的快速译码算法，并分析了译码算法的时间复杂性。     

分组码的格图结构和译码

本文讨论了分组码的格图结构，给出了结ＢＣＨ码Ｌ段格图结构，并据此提出了ＢＣＨ码的快速最大似然译码算法，同时讨论了ｑ＾ｍ元分组码的ｑ元映象的译码问题，给出了元映象的直和划分结构和相应的译码算法。     

分组码的格图结构和译码

本文讨论了分组码的格图结构,给出了某些BCH码L段格图结构,并据此提出了BCH码的快速最大似然译码算法,同时讨论了q~m元分组码的q元映象的译码问题,给出了q元映象的直和划分结构和相应的译码算法。     

线性分组码与时空分组码级联的迭代译码

提出了线性分组码与时空分组码的级联编码方案,推导了时空分组码在比特级上的软输入软输出译码算法,进而给出了在线性分组码和时空分组码之间进行迭代译码的算法。仿真结果表明这种方案与现有方案相比在能够获得最大分集增益的同时还能获得更大的编码增益。     

一种优化的CJS型快速相关攻击算法

快速相关攻击是序列密码的重要分析方法,本文提出了一种基于CJS型算法的优化算法,利用线性分组码的译码方法来解决流密码的攻击问题,通过寻找校验等式对,构造子线性分组码,该码维数较小,译码速度提高。采用ML-译码算法对子码进行译码,通过对LFSR的状态进行分割,独立实施ML-译码,可最终获得序列的初始状态,该算法显著降低了算法中的译码复杂度。     

用译码算法优化一类{1,-1}~n上的二次函数

{1,-1}~(?)上二次多项式的极大化是NP-难题,对研究这个问题所做的主要努力是识别出多项式时间可解的特殊情况,并给出近似方法。本文将一类系数取自{1,-1}上的{1,-1}~(?)上二次多项式极大化问题变成线性分组码的最小距离译码问题。线性分组码的最小距离译码是NP-难问题,但有些情况可解。本文研究了一类线性分组码的译码算法,这种算法可用来优化一类{1,-l}~(?)上的二次函数。     

软判决译码综述

本文首先介绍了纠错码中软判决译码算法提出的背景,概述了线性分组码的主要几类软判决译码算法的基本概念和发展过程,它们的优缺点和发展趋势。最后介绍了卷积码软判决译码算法发展概况。     

MIMO低复杂度空时分组码译码算法研究

研究了空时分组码译码算法的运算简化问题,提出了一种基于最大似然检测的改进空时分组码低复杂度译码算法,并进行了译码性能仿真和运算复杂度对比。本丈提出的改进方法,能够在不影响系统译码性能的基础上,有效地降低空时分组码的译码复杂度,且译码复杂度受调制星座图大小的影响很小。     

LDPC编译码算法分析

低密度奇偶校验(LDPC)码是一种线性分组码,其纠错能力可以接近香农极限。针对LDPC码的编译码问题,分析了校验矩阵的构造方法。给出了LDPC码的编码算法以及算法的实现结构。分析了基于软判决的置信传播(BP)译码算法,并给出了可以进一步降低计算复杂度的简化译码方法。通过仿真对比了不同的译码算法在高斯信道下的译码性能。     

并行级联分组码的一种新的迭代译码算法

并行级联分组码比串行级联分组码具有更高的码率,基于LLR计算的Turbo迭代译码算法使其内外分量码均做到了软判决译码。通过引入校正因子a（m）,将接收信息与子译码器的输出软信息进行线性叠加反馈能在省去繁琐的LLR计算的情况下实现并行级联分组码的Turbo迭代译码。仿真研究表明,若将译码器的输出进行简单的相关运算,可进一步改善译码器性能。     

Performance of sphere decoding of block codes

A sphere decoder searches for the closest lattice point within a certain search radius. The search radius provides a tradeoff between performance and complexity. We focus on analyzing the performance of sphere decoding of linear block codes. We analyze the performance of soft-decision sphere decoding on AWGN channels and a variety of modulation schemes. A hard-decision sphere decoder is a bounded distance decoder with the corresponding decoding radius. We analyze the performance of hard-decision sphere decoding on binary and q-ary symmetric channels. An upper bound on the performance of maximum-likelihood decoding of linear codes defined over F_q (e.g. Reed- Solomon codes) and transmitted over q-ary symmetric channels is derived and used in the analysis.We then discuss sphere decoding of general block codes or lattices with arbitrary modulation schemes. The tradeoff between the performance and complexity of a sphere decoder is then discussed.     

A New Linear Programming Approach to Decoding Linear Block Codes

In this paper, we propose a new linear programming formulation for the decoding of general linear block codes. Different from the original formulation given by Feldman, the number of total variables to characterize a parity-check constraint in our formulation is less than twice the degree of the corresponding check node. The equivalence between our new formulation and the original formulation is proven. The new formulation facilitates to characterize the structure of linear block codes, and leads to new decoding algorithms. In particular, we show that any fundamental polytope is simply the intersection of a group of the so-called minimum polytopes, and this simplified formulation allows us to formulate the problem of calculating the minimum Hamming distance of any linear block code as a simple linear integer programming problem with much less auxiliary variables. We then propose a branch-and-bound method to compute a lower bound to the minimum distance of any linear code by solving a corresponding linear integer programming problem. In addition, we prove that, for the family of single parity-check (SPC) product codes, the fractional distance and the pseudodistance are both equal to the minimum distance. Finally, we propose an efficient algorithm for decoding SPC product codes with low complexity and maximum-likelihood (ML) decoding performance.      

The hardness of decoding linear codes with preprocessing

The problem of maximum-likelihood decoding of linear block codes is known to be hard. The fact that the problem remains hard even if the code is known in advance, and can be preprocessed for as long as desired in order to device a decoding algorithm, is shown. The hardness is based on the fact that existence of a polynomial-time algorithm implies that the polynomial hierarchy collapses. Thus, some linear block codes probably do not have an efficient decoder. The proof is based on results in complexity theory that relate uniform and nonuniform complexity classes     

软判决译码研究进展

本文综述了软判决译码研究的发展概况，全文分四部分。第一部分简单地回顾了构造Ｓｈａｎｎｏｎ码的发展概况；第二部分在前一部分基础上叙述了线性分组码软判决译码的一般研究的状况；第三部分讨论了基于网络图上的线性分组码软判决译码的发展概况；最后描述了Ｔｒｕｂｏ码与迭代反馈软判决译码的研究状况与今后的发展方向     

Generalized rational interpolation over commutative rings and remainder decoding

We propose a new decoding procedure for Bose-Chaudhuri-Hocquenghem (BCH) and Reed-Solomon (RS) codes over Z/sub m/ where m is a product of prime powers. Our method generalizes the remainder decoding technique for RS codes originally introduced by Welch and Berlekamp and retains its key feature of not requiring the prior evaluation of syndromes. It thus represents a significant departure from other algorithms that have been proposed for decoding linear block codes over integer residue rings. Our decoding procedure involves a Welch-Berlekamp (WB)-type algorithm for solving a generalized rational interpolation problem over a commutative ring R with identity. The solution to this problem includes as a special case, the solution to the WB key equation over R which is central to our decoding procedure. A remainder decoding approach for decoding cyclic codes over Z/sub m/ up to the Hartmann-Tzeng bound is also presented.     

Optimal decoding of linear codes for minimizing symbol error rate (Corresp.)

The general problem of estimating the a posteriori probabilities of the states and transitions of a Markov source observed through a discrete memoryless channel is considered. The decoding of linear block and convolutional codes to minimize symbol error probability is shown to be a special case of this problem. An optimal decoding algorithm is derived.     

Iterative reliability-based decoding of linear block codes with adaptive belief propagation

In this letter, an iterative decoding algorithm for linear block codes combining reliability-based decoding with adaptive belief propagation decoding is proposed. At each iteration, the soft output values delivered by the adaptive belief propagation algorithm are used as reliability values to perform reduced order reliability-based decoding of the code considered. This approach allows to bridge the gap between the error performance achieved by the lower order reliability-based decoding algorithms which remain sub-optimum, and the maximum likelihood decoding, which is too complex to be implemented for most codes employed in practice. Simulations results for various linear block codes are given and elaborated.     

Nonlinear Programming Approaches to Decoding Low-Density Parity-Check Codes

We consider the decoding problem for low-density parity-check codes, and apply nonlinear programming methods. This extends previous work using linear programming (LP) to decode linear block codes. First, a multistage LP decoder based on the branch-and-bound method is proposed. This decoder makes use of the maximum-likelihood-certificate property of the LP decoder to refine the results when an error is reported. Second, we transform the original LP decoding formulation into a box-constrained quadratic programming form. Efficient linear-time parallel and serial decoding algorithms are proposed and their convergence properties are investigated. Extensive simulation studies are performed to assess the performance of the proposed decoders. It is seen that the proposed multistage LP decoder outperforms the conventional sum-product (SP) decoder considerably for low-density parity-check (LDPC) codes with short to medium block length. The proposed box-constrained quadratic programming decoder has less complexity than the SP decoder and yields much better performance for LDPC codes with regular structure.     

Scarce-state-transition error-trellis decoding of block codes withBPSK signals

A novel decoding technique for linear block codes with coherent BPSK signals is proposed. The new system has the same error performance as and similar complexity to the conventional trellis decoding of block codes. Like the scarce-state-transition Viterbi decoding of convolutional codes, the proposed system is also well suited for CMOS VLSI implementation and has a lower power consumption