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

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

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