線形ブロック符号に対する効率の良い最尤復号アルゴリズムの開発

线性分组码高效最大似然译码算法的开发

基本信息

批准号：
13750352
负责人：
楫勇一
金额：
$ 1.54万
依托单位：
Nara Institute of Science and Technology
依托单位国家：
日本
项目类别：
Grant-in-Aid for Young Scientists (B)
财政年份：
2001
资助国家：
日本
起止时间：
2001 至 2002
项目状态：
已结题

项目摘要

本研究では,線形ブロック符号に対する効率の良い最尤復号アルゴリズムの開発を行った.開発アルゴリズムでは,線形符号の構造的性質や遅延計算の考え方を利用することで,復号性能を劣化させること無く,計算量を劇的に削減することが可能である.平成13年度以前に試作していた方式では,復号アルゴリズム内部で用いられている局所的最尤ベクトルの探索方式に若干の問題があったため,たとえば長さ128以上,符号化率1/2付近の符号に対し,実用的な時間・空間計算量で復号を行うことは困難であった.平成13年度の研究では局所的最尤ベクトルの探索方式を改良し,分割統治的にベクトルの探索を行う方式を採用した.その結果,以前に試作していた方式に比べて大幅な計算量の削減が可能となり,長さ128のブロック符号の多くに対し,最尤復号を実現することが可能となった.また,符号の持つ線形構造をさらに積極的に利用する方式についても考察を行った.これらの結果については,ISIT2001,AAECC2001等の国際会議や国内のワークショップ等で研究成果の発表を行っている.また,開発方式における基本的な考え方をLog-MAP復号に適用する方式や,開発法を準最尤復号の一部として利用する方式についても検討し,一応の成果を得た(ISCTA2001,ISIT2002).一方,最尤復号の計算過程を詳細に解析したところ,最尤復号における最尤解の探索と,代数学の分野で近年盛んに研究されているGrobner基底を用いた剰余計算との間に深い相関関係があることが明らかとなった.主として数学的な視点から同関係について究明し,その成果の公表を行った(ISIT2002,IEICE Trans.).

在本研究中，我们开发了一种高效的线性分组码最大似然解码算法。所开发的算法利用了线性码的结构特性和延迟计算的概念，使得在不降低解码性能的情况下提高解码性能成为可能。在2001年之前原型的方法中，解码算法内部使用的局部最大似然向量搜索方法存在一些问题。因此，例如，以实际时间和空间复杂度很难解码长度为128或更长、编码率为1/2左右的代码。我们改进了搜索方法。我们采用了分而治之的向量搜索方法。结果，与之前的原型方法相比，可以显着减少计算量，并且对于许多长度为128的分组码，最大似然地实现解密我们还考虑了一种更积极地利用代码线性结构的方法。这些结果已在 ISIT2001 和 AAECC2001 等国际会议上进行了研究，并且在国内研讨会上我们正在展示我们的结果。我们还考虑了一种适用的方法。所开发的方法对Log-MAP解码的基本思想，以及使用所开发的方法作为准最大似然解码的一部分的方法。取得了一些成果(ISCTA2001, ISIT2002)。另一方面，对最大似然解码计算过程的详细分析表明，近年来在最大似然解码中寻找最大似然解以及代数领域的研究非常活跃。年。很明显，使用 robner 基进行余数计算之间存在着深刻的相关性。我们主要从数学角度研究了这种关系并发表了结果（ISIT2002，IEICE译）。