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

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

基本信息

批准号：
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的编码速率，很难解码实用的时间和空间计算复杂性。在2001年的研究中，我们改进了局部最大似然矢量的搜索方法，并采用了一种以分裂和征服方式搜索向量的方法。结果，与先前原型的方法相比，我们能够显着降低计算复杂性的量，并实现许多块代码（长度为128）的最大似然解码。这也已成为可能。我们还检查了更积极地使用代码线性结构的方法。这些结果已在ISIT2001和AAECC2001和国内研讨会等国际会议上提出。我们还检查了将开发方法中的基本概念应用于日志图解码的方法，以及将开发方法用作半最大可能性分解的一部分的方法。我们已经取得了一些Prima Facie结果（ISCTA2001，ISIT2002）。另一方面，当我们详细分析最大似然解码的计算过程时，发现在最大似然解码中搜索最大似然解决方案与使用Grobner的基础之间存在深厚的相关性，这是最近几年在Algebra领域进行了积极研究的。我们主要从数学角度研究了这种关系，并发布了结果（ISIT2002，IEICE）trans。）。