分组码的格图结构和译码

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

Reed-Muller码的大数逻辑译码及其与Viterbi算法的比较

文章首先介绍了Reed-Muller码的发展历史,以及构造其生成矩阵的特殊方法,从而对Reed-Muller进行编码。其次,重点讨论了Reed-Muller码的大数逻辑译码,这是一种适用于Reed-Muller码的简单又有效的译码方法,并举例进行了详细地阐述。Viterbi算法广泛应用于分组码、卷积码的译码,考虑到它的最优译码特性,文章运用Viterbi算法对ReedMuller码进行译码,将其性能与大数逻辑译码进行比较。由于Reed-Muller码的网格图比较复杂,文章提出一种方法,通过将线性分组码的生成矩阵转换成面向网格的形式,减少了网格图的状态数,从而降低了Viterbi译码的复杂性。     

用BCH等线性分组码构造McEliece纠错码公钥密码体制

McEliece公钥密码体制是用线性纠错码中的一种特殊码类Goppa码构造的。本文则表明采用BCH码或RS码等线性分组码也可构造安全的McEliece公钥密码体制。     

构造TCM好码的动态规划算法

本文提出了一种构造ＴＣＭ 好码的动态规划算法（ＤＰ）,ＤＰ算法在建立了ＴＣＭ 好码构造规则、编码器及信号网格图间的对应关系的基础上,采用动态规划算法进行寻优,从而获得ＴＣＭ好码。与常规ＴＣＭ 好码构造算法相比,本算法在精度、计算复杂度、灵活性上均有所改进     

嵌入法构造线性分组码咬尾网格

给出一种新的咬尾网格构造方法——嵌入法.该方法把一个线性分组码的咬尾网格嵌入到另一个线性分组码的传统网格中,从而很多咬尾网格问题可以转化为传统网格问题.证明每个咬尾网格都可以通过反复使用嵌入法从传统BCJR网格得到.最后讨论在网格中含有1个峰值情形时,采用嵌入法如何将峰值减半.     

几类格的快速译码

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

几类密码函数的线性结构研究

线性结构是度量密码函数安全性的一个重要指标。本文基于线性分组码理论，分析了文献[1～4]所构造的密码函数的线性结构，并指出这些函数均具有线性结构，且其线性结构集和构造这些函数所运用的线性分组码的对偶码有关。这就说明了文献[1～4]的密码函数本质上是密码学意义下的弱函数。     

一种自适应线性分散码方案的性能研究

针对线性分散码复杂度较高的问题,提出一种自适应线性分散码(ALDC),并将其应用于协作通信网络.该码可以根据当前信道状态,自适应地选择不同的调制阶数和分散矩阵,以在不同信噪比下获得最优的误码率性能,同时降低译码复杂度.分析了该码在协作系统中的编码与译码,并在误比特率性能上与传统空时分组码和LDC进行了仿真对比.结果表明,ALDC的误码率性能要优于传统的正交空时分组码和LDC,且译码复杂度较低.     

几类格的快速译码

本文通过研究16维Barnes-Wall格和基于构造A的二元线性分组码、四元线性分组码的导出格的代数结构,将这些格的译码问题转化为在相应码的格图上求最短路径的问题,从而提出了这些格的快速译码算法,并分析了译码算法的时间复杂性。     

TCM好码的结构分析及构造

TCM(Trellis Coded Modulation)好码的具体结构多种多样,该文从网格图的角度分析了TCM好码可能的结构。并应用分析结果构造了一种TCM好码的构造算法。它不仅缩小了所搜范围,提高了搜索效率,而且得到的结果性能较好。     

Good trellises for IC implementation of Viterbi decoders for linearblock codes

This paper investigates trellis structures of linear block codes for the integrated circuit (IC) implementation of Viterbi decoders capable of achieving high decoding speed while satisfying a constraint on the structural complexity of the trellis in terms of the maximum number of states at any particular depth. Only uniform sectionalizations of the code trellis diagram are considered. An upper-bound on the number of parallel and structurally identical (or isomorphic) subtrellises in a proper trellis for a code without exceeding the maximum state complexity of the minimal trellis of the code is first derived. Parallel structures of trellises with various section lengths for binary BCH and Reed-Muller (RM) codes of lengths 32 and 64 are analyzed. Next, the complexity of the IC implementation of a Viterbi decoder based on an L-section trellis diagram for a code is investigated. A structural property of a Viterbi decoder called add-compare-select (ACS)-connectivity which is related to state connectivity is introduced. This parameter affects the complexity of wire-routing (interconnections within the IC). The effect of five parameters namely: (1) effective computational complexity; (2) complexity of the ACS-circuit; (3) traceback complexity; (4) ACS-connectivity; and (5) branch complexity of a trellis diagram on the very large scale integration (VLSI) complexity of a Viterbi decoder is investigated. It is shown that an IC implementation of a Viterbi decoder based on a nonminimal trellis requires less area and is capable of operation at higher speed than one based on the minimal trellis when the commonly used ACS-array architecture is considered     

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.     

Linear tail-biting trellises, the square-root bound, andapplications for Reed-Muller codes

Linear tail-biting trellises for block codes are considered. By introducing the notions of subtrellis, merging interval, and sub-tail-biting trellis, some structural properties of linear tail-biting trellises are proved. It is shown that a linear tail-biting trellis always has a certain simple structure, the parallel-merged-cosets structure. A necessary condition required from a linear code in order to have a linear tail-biting trellis representation that achieves the square root bound is presented. Finally, the above condition is used to show that for r⩾2 and m⩾4r-1 or r⩾4 and r+3⩽m⩽[(4r+5)/3] the Reed-Muller code RM(r, m) under any bit order cannot be represented by a linear tail-biting trellis whose state complexity is half of that of the minimal (conventional) trellis for the code under the standard bit order     

Tailbiting codes: bounds and search results

Tailbiting trellis representations of linear block codes with an arbitrary sectionalization of the time axis are studied. The notations of regular and irregular tailbiting codes are introduced and their maximal state complexities are lower-bounded. The asymptotic behavior of the derived bound is investigated. Furthermore, for regular tailbiting codes the product state complexity is lower-bounded. Tables of new tailbiting trellis representations of linear block codes of rates 1/2, 1/3, and 1/4 are presented. Almost all found trellises are optimal in the sense of the new bound on the state complexity and for most codes with nonoptimal trellises there exist time-varying trellises which are optimal. Five of our newly found tailbiting codes are better than the previously known linear codes with the same parameters. Four of them are also superior to any previously known nonlinear code with the same parameters. Also, more than 40 other quasi-cyclic codes have been found that improve the parameter set of previously known quasi-cyclic codes     

On the redundancy of trellis lossy source coding

It is well known that trellis lossy source codes have better performance/complexity tradeoff than block codes, as shown by simulations. This makes the trellis coding technique attractive in practice. To get a better understanding of this fact, this paper studies the redundancy of trellis coding for memoryless sources and compares it with a similar result for block codes     

Low state complexity block codes via convolutional codes

A new class of block codes with low state complexity of their conventional trellis representations called double zero-tail terminated convolutional codes (DZT codes) is introduced. It is shown that there exist DZT-codes meeting the Varshamov-Gilbert bound on the minimum distance and having asymptotically optimal state complexity. Two ways of constructing DZT-codes are considered. Examples of DZT-codes meeting a lower bound on the state complexity are given.     

Complexity Reduction in SISO Decoding of Block Codes

SISO decoding for block codes can be carried out based on a trellis representation of the code. However, the complexity entailed by such decoding is most often prohibitive and thus prevents practical implementation. This paper examines a new decoding scheme based on the soft-output Viterbi algorithm (SOVA) applied to a sectionalized trellis for linear block codes. The computational complexities of the new SOVA decoder and of the conventional SOVA decoder, based on a bit-level trellis, are theoretically analyzed and derived for different linear block codes. These results are used to obtain optimum sectionalizations of a trellis for SOVA. For comparisons, the optimum sectionalizations for Maximum A Posteriori (MAP) and Maximum Logarithm MAP (Max-Log-MAP) algorithms, and their corresponding computational complexities are included. The results confirm that the new SOVA decoder is the most computationally efficient SISO decoder, in comparisons to MAP and Max-Log-MAP algorithms. The simulation results of the bit error rate (BER) performance, assuming binary phase -- shift keying (BPSK) and additive white Gaussian noise (AWGN) channel, demonstrate that the performance of the new decoding scheme is not degraded. The BER performance of iterative SOVA decoding of serially concatenated block codes shows no difference in the quality of the soft outputs of the new decoding scheme and of the conventional SOVA.     

An approximation to the weight distribution of binary linear codes

Binary primitive BCH codes form a large class of powerful error-correcting codes. The weight distributions of primitive BCH codes are unknown except for some special classes, such as the single, double, triple error-correcting codes and some very low-rate primitive BCH codes. However, asymptotic results for the weight distribution of a large subclass of primitive BCH codes have been derived by Sidel'nikov. These results provide some insight into the weight structure of primitive BCH codes. Sidel'nikov's approach is improved and applied to the weight distribution of any binary linear block code. Then Sidel'nikov's results on the weight distributions of binary primitive BCH codes are improved and it is shown that the weights of a binary primitive code have approximate binomial distribution.     

Decoding of alternant codes (Corresp.)

It is shown that the only modification of the Berlekamp algorithm required to decode the class of alternant codes consists of a linear transformation of the syndromes prior to the application of the algorithm. Since alternant codes include all Bose-Chaudhuri-Hocquenghem (BCH) and Goppa codes, the Chien-Choy generalized BCH codes, and the generalized Srivastava codes, all of these can be decoded with no increase in complexity over BCH decoding.