Development of Maximum Likelihood Decoding for Linear Block Codes Using Trellis Structure and of Error Performance Analysis Algorithms

使用网格结构的线性分组码最大似然解码和错误性能分析算法的开发

• 批准号: 12650381
• 负责人: FUJIWARA Toru
• 金额: $ 2.18万
• 依托单位: Osaka University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2000
• 资助国家: 日本
• 起止时间: 2000 至 2001
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-12650381/
• 关键词: Error Correcting Code; Linear Block Code; Maximum Likelihood Decoding; Coset; Weight Distribution; Trellis Structure; 線形符号; 準最尤復号

(1) For Reed-Muller codes and BCH codes, implementation of ACS (Add-Select-Compare) circuits based on its trellis structure has been studied. As a result, good trade-off is obtained for the circuit size and decoding delay. Dividing the entire decoding circuit into several 1C chips are also studied. As an example, a recursive maximum likelihood decoder of an (64, 40) subcode of (64, 42) Reed-Muller code can be implemented with the same decoding delay and the half of the circuit complexity.(2) A divide and conquar algorithm has been devised to compute the weight distribution of the coset leadears. Although time complexity may be larger than known methods, the proposed method reduces the space complexity considerably. For the (64, 24), (64, 30), (128, 92), and (128, 99) extended primitive BCH codes, the (64, 22) and (128, 99) Reed-Muller codes and several other codes, we have computed the weight distribution of the coset leadears. For (64, 22) Reed-Muller codes, the space complexity becomes 1/40,000 of that of the conventional method. Also, it is shown for Reed-Muller codes that the natural symbol ordering and dividing the problem into half achieves the smallest space complexity.(3) For Reed-Muller codes, the error performance of hard-decision and soft-decision majority logic decoding has been studied detailedly. As a result, the most decoding results in error are relatively far from the received word. Using this, a two step decoding method combined with decoding method with good error performance is proposed. This method reduces the decoding complexity.

(1)针对Reed-Muller码和BCH码，研究了基于其网格结构的ACS（Add-Select-Compare）电路的实现。结果，对于电路大小和解码延迟获得了良好的折衷。对整个译码电路进行了单片化设计。作为一个例子，（64，42）Reed-Muller码的（64，40）子码的递归最大似然解码器可以用相同的解码延迟和一半的电路复杂度来实现。(2)设计了一种分治算法来计算陪集主节点的权值分布。虽然时间复杂度可能比已知的方法，所提出的方法大大降低了空间复杂度。对于（64，24），（64，30），（128，92）和（128，99）扩展本原BCH码，（64，22）和（128，99）Reed-Muller码以及其它几种码，我们计算了陪集首码的重量分布。对于（64，22）Reed-Muller码，空间复杂度变为传统方法的1/40，000。此外，它示出的Reed-Muller码的自然符号排序和划分成两半的问题实现了最小的空间复杂度。(3)对于Reed-Muller码，详细研究了硬判决和软判决择多逻辑译码的误码性能。结果，错误的大多数解码结果相对远离所接收的字。在此基础上，提出了一种两步译码方法，并结合译码方法进行了误码性能分析。该方法降低了译码复杂度。

项目成果

Masaya Maeda and Toru Fujiwara: "Weight, Distributions of the Coset Leaders of Some Reed-Muller Codes and BCH Codes"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. Vol.E84-A. 851-859 (2001)

Masaya Maeda 和 Toru Fujiwara：“一些 Reed-Muller 码和 BCH 码的陪集领导者的权重和分布”IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences。

Masaya Maeda, Toru Fujiwara: "Weight Distribution of the Coset Leaders of Some Reed-Muller Codes and BCH Codes"IEICE Trans. Fundamentals. E84-A. 851-859 (2001)

Masaya Maeda、Toru Fujiwara：“一些 Reed-Muller 码和 BCH 码的陪集首部的权重分布”IEICE Trans。

Masaya Maeda,Toru Fujiwara: "Weight Distributions of the Coset Leaders of Some Reed-Huller Codes and BCH Codes"IEICE Fundamentals. E84・A・3. 851-859 (2001)

Masaya Maeda，Toru Fujiwara：“一些 Reed-Huller 代码和 BCH 代码的陪集首部的权重分布”IEICE 基础知识 E84・A・3（2001 年）。