(57)【要約】      （修正有）【課題】妥当な時間で長いブロック長のＬＤＰＣ符号の最適なＭＬ復号を実行することができる復号方法を提供する。【解決手段】通信路を介して受信されるシンボルの系列から対数尤度比を確定する。対数尤度比に従って制約のセットを初期化する。誤り訂正符号に従って制約のセット及び対数尤度比に対し適応線形計画法復号器を適用し、符号語の推定値と更新された制約のセットとを生成する。符号語の推定値が非整数擬似符号語である場合、更新された制約のセットを整数制約のセットでさらに更新し、適用するステップに進み、そうでない場合、符号語の推定値を最終符号語として生成する。【選択図】図６
2009005343.tif 000002
【特許請求の範囲】
【請求項１】
通信路を介して受信されるシンボルの系列を誤り訂正符号の符号語に復号する方法であって、
通信路を介して受信されるシンボルの系列から対数尤度比を確定するステップと、
前記対数尤度比に従って制約のセットを初期化するステップと、
誤り訂正符号に従って前記制約のセット及び前記対数尤度比に対し適応線形計画法復号器を適用し、前記符号語の推定値と更新された制約のセットとを生成するステップと、
前記符号語の前記推定値が非整数擬似符号語であるか否かを確定するステップと、
前記符号語の前記推定値が前記非整数擬似符号語である場合、前記更新された制約のセットを整数制約のセットでさらに更新し、適応線形計画法復号器を適用する前記ステップに進み、そうでない場合、前記符号語の前記推定値を最終符号語として生成するステップと、
を含む方法。
【請求項２】
前記通信路は、雑音により前記シンボルの系列を破損させる請求項１に記載の方法。
【請求項３】
最も確実性の低いシンボルとして、０．５に最も近い値を有するシンボル
【数１】
2009005343.tif 000022
を識別するステップであって、前記最も確実性の低いシンボル
【数２】
2009005343.tif 000023
の添え字i＊は、以下の通りであるものと、
【数３】
2009005343.tif 000024
前記更新された制約のセットに整数制約
【数４】
2009005343.tif 000025
を追加するステップと
をさらに含む請求項１に記載の方法。
【請求項４】
Ｃが前記誤り訂正符号である場合、符号語ｘ∈Ｃを前記通信路を介して送信するステップと、
前記符号語ｘの、前記通信路によって歪まされたバージョンである符号語ｙを受信するステップであって、
【数５】
2009005343.tif 000026
は、前記符号語ｙが受信されるとすると特定の符号語
【数６】
2009005343.tif 000027
が送信された確率であるもの
をさらに含む請求項１に記載の方法。
【請求項５】
ｉ番目のシンボルに対する前記対数尤度比は、
【数７】
2009005343.tif 000028
である請求項４に記載の方法。
【請求項６】
通信路を介して受信されるシンボルの系列を誤り訂正符号の符号語に復号するシステムであって、
通信路を介して受信されるシンボルの系列から対数尤度比を確定する手段と、
前記対数尤度比に従って制約のセットを初期化する手段と、
誤り訂正符号に従って前記制約のセット及び前記対数尤度比に対し適用して、前記符号語の推定値と更新された制約のセットとを生成するように構成された適応線形計画法復号器と、
前記符号語の前記推定値が非整数擬似符号語であるか否かを確定する手段と、
前記符号語の前記推定値が前記非整数擬似符号語である場合、前記更新された制約のセットを整数制約のセットでさらに更新し、適応線形計画法復号器を適用し、そうでない場合、前記符号語の前記推定値を最終符号語として生成する手段と、
を備えるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には誤り訂正符号の符号語を復号することに関し、特に、線形計画法を使用して符号語を最適に復号することに関する。
【背景技術】
【０００２】
データ通信システムは、雑音の影響を相殺するために二元線形符号を使用することが多い。理想的な目的は、通信路のシャノン限界に達することである。シャノン限界は、通信路を介して可能な誤りのない伝送の最高レートである。
【０００３】
非常に優れた性能を示す符号の１つのクラスは、低密度パリティ検査(low-density parity-check)(ＬＤＰＣ)符号である。ＬＤＰＣ符号のための従来の復号器は、反復確率伝播(belief-propagation)(ＢＰ)復号に基づく。代替的な復号方法は、線形計画法(ＬＰ)に基づく。これについては、参照により本明細書に援用される、J. Feldman、M. J. Wainwright及びD. Karger著、「Using linear programming to decoding binary linear codes」(IEEE Trans. Inform. Theory, 51:954-972, March 2005)を参照されたい。
【０００４】
ＬＰ復号にはいくつかの魅力的な特徴がある。ＬＰ復号器は、決定論的に収束し、復号器が整数解に収束する場合、最適な最尤(ＭＬ)符号語が見つかったことが分かる。ＬＰ復号が非整数解に収束する場合、明確な非整数「擬似符号語(pseudo codeword)」が見つかっている。不都合なことに、ＬＰ復号は、ＢＰ復号より複雑である。Feldman他によって最初に述べられた公式化では、ＬＰ復号問題における制約の数は、最大検査ノード次数により指数関数的に増大し、結果としての計算負荷は極端に重いものとなる可能性がある。
【０００５】
ＬＰ復号の非常に大きい計算負担は、適応線形計画法(adaptive linear programming)(ＡＬＰ)復号の導入の動機付けとなった。これについては、参照により本明細書に援用される、M. H. Taghavi N.及びP. H. Siegel著、「Adaptive linear programming decoding」(In Proc. Int. Symp. Inform. Theory, pages 1374-1378, July 2006)を参照されたい。ＬＰ制約のすべてで開始する代わりに、彼らはまず、二元符号語シンボルの値が０より大きく且つ１より小さいようにのみ制約される問題のＬＰ最適値に対し解く。結果としての最適値において、彼らは、各検査ノードに対し、違反される局所制約を確定する。彼らは、違反制約を問題に再び加えることにより、結果としてのＬＰを解く。このプロセスを、いずれの局所制約も違反されなくなるまで反復する。結果は、元の制約のわずかな部分のみが使用される場合であっても、解を元のＬＰに正確に一致させることが保証される。彼らは、線形符号に対して使用される制約の数が、高検査次数の符号に対してさえ、パリティ検査の数ｍのわずかな倍数(１．１〜１．５)でしかないこと、及び、ＡＬＰ復号は、標準ＬＰ復号より大幅に、時に数桁も効率的であることを認める。
【０００６】
線形計画法及び適応線形計画法復号器の詳細
復号しなければならない符号が長さｎの二元線形符号Ｃであるものとする。二元符号語ｘ∈Ｃが、メモリレス通信路を介して送信元から宛先まで送信されるものとする。宛先は、符号語ｘの、通信路によって歪まされたバージョンである符号語ｙを受信する。
【０００７】
【数１】
2009005343.tif 000003
【０００８】
は、ｙが受信されるものとして特定の符号語
【０００９】
【数２】
2009005343.tif 000004
【００１０】
が送信された確率である。すべての符号語が送信される可能性が等しく高い場合、ＭＬ復号問題は以下の問題に整理される。
【００１１】
最小化
【００１２】
【数３】
2009005343.tif 000005
【００１３】
制約条件
【００１４】
【数４】
2009005343.tif 000006
【００１５】
ここで、γｉは、以下のように定義されるｉ番目の負の対数尤度比である。
【００１６】
【数５】
2009005343.tif 000007
【００１７】
ここで、
【００１８】
【数６】
2009005343.tif 000008
【００１９】
は、候補符号語
【００２０】
【数７】
2009005343.tif 000009
【００２１】
のｉ番目のシンボルであり、ｙｉは、受信系列ｙのｉ番目のシンボルであり、ｘｉは、送信符号語ｘのｉ番目のシンボルである。たとえば、通信路がビット反転確率ｐの二元対称通信路(binary symmetric channel)(ＢＳＣ)である場合、受信ビットｙｉ＝１の場合、γｉ＝ｌｏｇ(ｐ／(１−ｐ))であり、受信ビットｙｉ＝０の場合、γｉ＝ｌｏｇ((１−ｐ)／ｐ)である。他の通信路に対しても、適当な負の対数尤度比γｉを同様に計算することができる。
【００２２】
最小化問題(１)に対する制約(２)は二元である。Feldman他は、(２)の二元制約が、連続した変数にわたるより御しやすい制約に置き換わる、この最小化問題の緩和(relaxed)バージョンを説く概念を導入した。特に、シンボル
【００２３】
【数８】
2009005343.tif 000010
【００２４】
は、０以上１以下の任意の値をとることが可能である。この最小化問題の緩和バージョンは線形問題である。
【００２５】
符号Ｃにおける各パリティ検査は、その符号の符号語が満たさなければならない複数の局所線形制約を含む。これら制約の共通部分は、線形計画法(ＬＰ)復号器が動作する「多面体(polytope)」を定義する。多面体は、整数頂点と非整数頂点とを共に有する。整数頂点は、すべてのｉに対し、
【００２６】
【数９】
2009005343.tif 000011
【００２７】
が０又は１であるものであり、非整数頂点は、０より大きく且つ１より小さい
【００２８】
【数１０】
2009005343.tif 000012
【００２９】
の値を含むものである。
【００３０】
多面体の整数頂点は、Ｃにおける符号語に対応する。ＬＰ最適値が整数頂点にある場合、最小化問題の緩和バージョンのみが解かれた場合であっても、式(２)が満たされ、ＭＬ解が見つかる。しかしながら、ＬＰ最適値が非整数頂点にある場合、式(２)は満たされず、ＬＰ解はＭＬ符号語ではない。このような非整数解を、「擬似符号語」と呼ぶ。
【００３１】
Taghavi他によって使用された多面体を定義するパリティ検査制約の厳密な形式は以下の通りである。まず、すべてのビットｉに対し、
【００３２】
【数１１】
2009005343.tif 000013
【００３３】
は連続値であり、以下の不等式を満たす。
【００３４】
【数１２】
2009005343.tif 000014
【００３５】
そして、すべての検査ｊ＝１，…，ｍに対し、隣接する変数Ｎ(ｊ)⊂｛１，２，…，ｎ｝の集合のすべての配列は、以下のパリティ検査不等式制約を満たさなければならない。すなわち、|Ω|が奇数であるようなすべての部分集合Ω⊆Ｎ(ｊ)に対し、
【００３６】
【数１３】
2009005343.tif 000015
【００３７】
である。
【００３８】
Taghavi他は、違反制約を「カット(cut)」として定義する。反復ＡＬＰ復号方法は、すべてのＬＰ制約のうちの小数しか含まない単純な初期問題を解くことにより得られる頂点で開始し、反復的に違反制約を追加し、いずれの制約も違反されなくなるまで再び解く。Taghavi他は、違反制約を効率的に分類し見つけることができることを示す。
【００３９】
単純な初期問題は、制約
【００４０】
【数１４】
2009005343.tif 000016
【００４１】
のみを使用することを含む。
【００４２】
この単純な初期問題の最適解は、硬判定復号によって即座に見つけられる。
【００４３】
図５に示すように、従来のＡＬＰ法は以下のように動作する。
式(６)における制約を使用して初期問題を初期化する(５１０)
ＬＰ復号を実行する(５２０)
現在の解の違反制約すべてを見つける(５３０)
１つ又は複数の違反制約が見つかる場合、それら違反制約を問題制約に追加し(５４０)、真である場合、ステップ５２０に進む
一方、偽である場合、現在の解は最終ＡＬＰ符号語５４１の推定値である。
【００４４】
ＡＬＰ復号法は、標準ＬＰ復号器と同じ符号語又は擬似符号語を取得し、相違は、ＡＬＰ復号器の方が消費時間が短いということのみである。
【００４５】
ＬＰ又はＡＬＰ復号器の解が非整数である場合、ＭＬ符号語は見つかっておらず、元のＬＰ緩和の引締め(tightening)を見つけるよう誘導される。
【００４６】
元のＬＰ緩和を引き締める１つの方法は、冗長パリティ検査式からもたらされる追加の線形制約を導入するというものである。その手法は、Feldman他により、「Using linear programming to decoding binary linear codes」において、且つTaghavi他により、「Adaptive linear programming decoding」において述べられている。冗長パリティ検査式のすべてが性能を向上させるとは限らない。したがって、有用な冗長パリティ検査式を探索しなければならない。その探索の計算負荷及び探索結果の質は、結果としてのアルゴリズムの有用性に大きい影響を与える。今までのところ、それら手法は使用できるＭＬ復号器をもたらしていない。
【００４７】
別の方法は、整数制約のセットを強制する。その手法は、Feldman他により、「Using linear programming to decoding binary linear codes」において、且つK. Yang、J. Feldman及びX. Wangにより、「Nonlinear programming approaches to decoding low-density parity-check codes」(IEEE J. Select. Areas Commun. 24: 1603-1613, August 2006)において述べられている。混合整数ＬＰソルバが使用されるが、複雑性制約により、その方法の適用性は、短いブロック長に制限される。Feldman他は、６０ビットまでのブロック長及びわずか１０−４までのワード誤り率に対する復号結果を述べているのみである。
【００４８】
別の関連方法は、拡張(augmented)ＢＰ手法である。これについては、N. Varnica、M. Fossorier及びA. Kavcic著、「Augmented belief-propagation decoding of low-density parity check codes」(IEEE Trans. Commun, Volume 54, Issue 10, pages 1896-1896, Oct. 2006)を参照されたい。彼らは、ＢＰで開始し、最も確実性の低いビットを累進的に確定する。しかしながら、その方法はＢＰを使用するため、復号器は、妥当な時間で符号語をうまく返さない可能性があり、且つ、符号語を返す場合、最適なＭＬ符号語である保証はない。
【発明の開示】
【発明が解決しようとする課題】
【００４９】
従来技術による復号方法はいずれも、たとえば、１０−６以下までのワード誤り率に対しＭＬ復号結果を生成することができるように、妥当な時間で、長いブロック長(たとえば、１００を上回るブロック長)のＬＤＰＣ符号の最適なＭＬ復号を実行することができる、復号方法を提供していない。このような復号方法が強く望まれている。
【課題を解決するための手段】
【００５０】
本発明の実施の形態は、構成要素として適応ＬＰ復号器を使用する最適最尤(ＭＬ)復号器を提供する。適応ＬＰ復号器が、符号語ではなく擬似符号語を返す時はいつでも、擬似符号語の最も確実性の低いシンボルに対し整数制約が追加される。より一般的には、整数制約のセットを追加することができる。
【００５１】
いくつかの符号に対し、特に高ＳＮＲエラーフロア領域(error floor regime)においては、結果としての混合整数ＬＰを強制的にＭＬ解にするために必要な整数制約はわずかである。たとえば、本発明は、実際に重要な雑音領域(noise regime)全体を通して、(１５５，６４)ＬＤＰＣ符号を効率的に且つ最適に復号することができる。(１５５，６４)ＬＤＰＣ符号は、２６４の符号語を有し、それは、明らかに、いかなる従来の方法を使用しても探索するには数が多すぎる。
【００５２】
ＬＰ復号器に冗長パリティ検査を追加することに焦点を当てるいくつかの従来技術による復号器とは対照的に、本方法は、復号問題に対し、わずかな数の整数制約を追加する。また、整数制約を追加するいくつかの従来技術とは対照的に、本方法は、選択された整数制約を適応線形計画法復号器に統合する。
【００５３】
各二元制約を選択する方法は以下の通りである。最適な擬似符号語の「最も確実性の低い」シンボルが選択される。非常に多くの場合、復号器に対しＭＬ解をもたらさせるために必要な整数制約はほんのわずかである。
【発明の効果】
【００５４】
本方法の予想外の効果は、特に、低雑音領域において著しい。たとえば、(１５５，６４)ＬＤＰＣ符号の場合、誤り率は、従来のＬＰ復号と従来の確率伝播(ＢＰ)復号との両方と比較して約１００万分の１に低減する。もっとも予想外であるのは、この低雑音領域において、本発明の実施の形態によるＭＬ方法に必要な復号時間の増大は、従来のＬＰ復号に比較して、ごくわずかである、ということである。したがって、本発明により、ＭＬ復号は、従来の汎用プロセッサに実装される場合であっても、はるかに長いブロック長に対して実際的となる。
【発明を実施するための最良の形態】
【００５５】
方法概要
図６は、本発明による、通信路６０１を介して受信されたシンボルの系列６０７を誤り訂正符号６０４の符号語６０５に復号する方法を示す。通信路６０１を介して受信されたシンボルの系列で開始する。ここでは、通信路が、雑音及び他の要因によりシンボルを破損させる可能性があるものと想定する。したがって、誤り訂正符号を使用する。
【００５６】
シンボルの系列から、対数尤度比６０３を確定する(６０２)。ここでは、対数尤度比を使用して、制約のセット６２０を、本発明による適応線形計画法復号器で使用するために初期化する(６１０)。ＡＬＰ復号器は、複数の手続き、すなわちＬＰ復号器６３０と、すべての違反制約を見つけるために現在の解を符号６０４に適用する手続きとを含む。違反制約が見つかると(６５０)、対応する追加の制約６６０を使用して、制約セット６２０を更新する(６７０)。
【００５７】
それ以上違反制約が見つからない場合(６５０)、結果は、推定されたＡＬＰ符号語である。この推定符号語が整数でない場合(６８０)、整数制約Ｉ＊が識別される(６９０)。この整数制約を使用して、制約セット６２０を更新する(６７０)。一方、ＡＬＰ解が整数である場合、復号はＭＬ解に収束している。この場合、現在のＡＬＰ解が、最終的な推定符号語６０５である。
【００５８】
ここで、本発明による復号方法についてより詳細に説明する。
【００５９】
混合整数適応ＬＰ復号を介する最適ＭＬ復号
適応線形計画法(ＡＬＰ)復号器は、失敗すると、「擬似符号語」を返す。擬似符号語は、実現可能な多面体の非整数頂点であることを想起されたい。ＡＬＰ復号器がこのような頂点に収束する場合、ＭＬ符号語が見つかっていないことが分かる。したがって、追加の整数制約を追加する。
【００６０】
ＡＬＰ復号器がＭＬ解を見つけられなかった場合、整数制約６６０を追加する６７０。最も確実性の低いシンボルとして、値が０．５に最も近いシンボル
【００６１】
【数１５】
2009005343.tif 000017
【００６２】
を識別する。シンボル
【００６３】
【数１６】
2009005343.tif 000018
【００６４】
の添え字i＊は、以下の通りである。
【００６５】
【数１７】
2009005343.tif 000019
【００６６】
そして、制約
【００６７】
【数１８】
2009005343.tif 000020
【００６８】
を、ここでは混合整数ＬＰ問題である問題に追加し、ＡＬＰ復号を繰り返す。ＬＰソルバ６３０が整数制約に対応しない場合、整数制約をさらに以下のように追加することができる。すなわち、
【００６９】
【数１９】
2009005343.tif 000021
【００７０】
の２つのあり得る値の各々に対しＬＰ問題を別々に解き、その後、可能性の高い方の解を選択する。
【００７１】
整数制約を含む問題を解決した後、本発明による解は依然として擬似符号語である可能性があり、その場合、再び擬似符号語解の最も確実性の低いシンボルに対して別の整数制約６８０を追加する(６７０)。
【００７２】
混合整数線形計画の複雑性は、強制される整数制約の数により指数関数的に増大する。したがって、本方法は、追加される整数制約の必要な数が比較的小さい場合においてのみ、妥当な時間での復号に成功する。都合のいいことに、いくつかの符号、特に低雑音適用におけるＬＤＰＣ符号の場合、必要な整数制約の数が比較的少ない。このため、一般的なＭＬ復号問題がＮＰハードであっても、実際的且つ最適なＭＬ復号器を得ることができる。
【００７３】
結果の概要
R.M. Tanner、D. Sridhara及びT. Fujaにより、参照により本明細書に援用される「A class of group-structured LDPC codes」(In Proc. ICSTA, Ambleside, UK, 2001)において述べられているような(Ｎ＝１５５，ｋ＝６４，ｄ＝２０)ＬＤＰＣ符号に対し、本発明による混合整数ＡＬＰ法を使用する結果について説明する。このＬＤＰＣ符号は、その次元及びブロック長に対して優れた最小距離を有する。しかしながら、この符号は、ＢＰ又はＬＰ復号器の性能を非常に低下させる擬似符号語を有する。「拡張ＢＰ」等の従来技術による方法とは対照的に、本方法は、高い確実性で最適な性能を与え、擬似符号語の負の影響を回避するＭＬ復号器をもたらす。
【００７４】
図２は、二元対称通信路に対する本手法の性能向上を要約した。ここでは、「従来の」ＡＬＰ復号、すなわちいかなる追加の整数制約もない式(６)及び(７)のＡＬＰ緩和を使用するＬＰ復号２０１のワード誤り率(ＷＥＲ)を、従来のＢＰ復号２０２と、図６に示すような本発明による混合整数ＡＬＰ復号器を使用して得られるＭＬ復号２０３と比較する。雑音レベルを、低雑音(交叉確率(cross-over probability)が小さい)２１１、中間雑音２１２及び高雑音(交叉確率が大きい)２１３として分類する。
【００７５】
ＬＰ又はＢＰと比較したＭＬ復号のＷＥＲの向上は、低雑音レベルの中間において約１０５である。低雑音領域における低端部では、向上は１００万倍以上であり得る。中間雑音レベル及び高雑音レベルでは、向上はそれぞれ１０３及び１０である。さらに驚くべきことは、これら向上を、本方法がもたらす計算複雑性のほんのわずかな増大により得ることができる、ということである。また、従来技術とは対照的に、本方法はより高い交叉確率で失敗しないということも留意されるべきである。
【００７６】
図３は、ビット反転の数に対する復号時間統計を要約した。列３０１に列挙される行は、統計のタイプを示し、列３０２は、ビット反転の数によって分類されるその統計に対する結果を示す。１２ビット反転、１４ビット反転及び１６ビット反転に対し、ＬＰ復号の平均復号時間は、それぞれ０．１２秒、０．１５秒及び０．２３秒である。混合整数ＡＬＰを介するＭＬ復号の本方法の場合、対応する平均復号時間は０．１４秒、０．２２秒及び０．８７秒である。本方法では、ＷＥＲを５〜６桁向上させるために必要な平均復号時間の増大は非常にわずかである。
【００７７】
試験結果の詳細
また、ＭＬ解を得るために必要なＡＬＰ反復の数及び必要な二元制約の数についても説明し、本発明によるＭＬ復号器の計算時間要件に対する統計を提供する。
【００７８】
ここでは、二元対称通信路に対する符号性能をシミュレートするが、本発明による復号器は、付加白色ガウス雑音(ＡＷＧＮ)通信路等、他の通信路にも作用することに留意する。(１５５，６４)ＬＤＰＣ符号の最小距離は２０である。したがって、ＭＬ復号器は、９以下のビットが反転される場合に成功することが保証される。１０以上のビットが反転される場合、送信符号語ではなく別の符号語である可能性が高いため、ＭＬ符号器は失敗する可能性がある。本発明者らは、必要な整数制約及びＡＬＰ復号反復の数が、ビット反転の数によって増大するが、２３までのすべてのビット反転に対して管理可能であることが分った。特定の受信語を、復号するには時間がかかり過ぎるものとして見切りを付ける前に、上限２００のＡＬＰ復号反復(解かれる線形計画、すなわち純粋な線形計画又は混合整数ＬＰの全体の数として定義される)を採用する。
【００７９】
(１５５，６４)符号のレートは０．４１２９である。ほぼ限界能力で動作することができる場合、約２２のビット反転を訂正するようにしか期待できない。図２に示すような本発明による分析を簡略化するために、各々が固定数のビット反転に対応する複数の雑音レベルにおける誤り率を推定する。２３までのビット反転をシミュレートし、単純に、復号は、２３を上回るビット反転の非常に高い雑音領域に対して確率１で失敗するものとする。これは、ＭＬワード誤り率(ＷＥＲ)が２３ビット反転に対して「わずか」約０．７３であるとすると、わずかに悲観的であるが、また、２４以上のビット反転の場合に復号器が非常に低速に動作するものとすると、現実的である。各ビット反転レベルにおいて２００のＭＬ復号誤りを累積するまで、２３から１２までのビット反転の各数において復号試験を実行する。これら試験からもたらされるＷＥＲを図１に示す。
【００８０】
１０及び１１ビット反転の場合、ＭＬ復号器は非常によく実行する。しかしながら、シミュレーションを通して十分な失敗を得ることは困難である。１１ビット反転では、７９のＭＬ復号誤りしか集められなかった。したがって、以下のように性能を推定する。たとえば１２ビット反転の失敗において、反転の少なくとも１０が別の符号語とオーバラップしなければならず、そうでなければ、ＭＬ復号器は、送信された符号語に復号することを留意することによって開始する。経験的に、正確に１０ビットがオーバラップする場合、ほとんどすべての失敗がもたらされ、１１ビット及び１２ビットがオーバラップする場合ははるかに可能性が低くなる。このような場合、１２ビット失敗パターンで開始し、ビット反転の数を１ずつ低減する。そして、まだ失敗を有するように２つの(オーラバップしない)ビットのうちの１つを取り上げる確率は(２／１２)である。１１ビット反転に対する８．３×１０−７＝(２／１２)５．９×１０−６という結果としての推定誤り率は、わずか７９の復号失敗に基づく本発明による試験測定値１．１×１０−６とおおまかに一致する。同じ概念を使用して、１０ビット反転におけるＷＥＲを、１１ビット反転における推定ＷＥＲの(１／１１)番目であるものとして推定する。
【００８１】
図２を生成するために、或る範囲の交叉確率に対してＭＬ  ＷＥＲを推定する必要がある。これら推定値を作成するために、ここでまた、９以下のビット反転に対してＷＥＲは０であることに留意し、２４以上のビット反転に対してＷＥＲは１に等しいものとする。そして、特定の交叉確率に対して各数のビット反転を実現する確率を計算し、適当な二項係数によって固定数のビット反転において経験的ＷＥＲを平均化する。９以下のビット反転に対してＭＬ誤りが発生しないという知識と、より大きい数のビット反転に対する誤り統計との組合せにより、ビット反転の数を確率論的に生成した場合にあり得るよりはるかに低いＷＥＲまでＭＬ性能を推定することができる。
【００８２】
別の重要な量は、本発明による混合整数ＡＬＰ復号の時間要件である。図３は、本発明による結果をもたらすための復号時間に対する統計の表を示す。第１行はビット反転の数を示し、後続する行は、全シミュレーション、正しい復号及び誤った復号それぞれに対する平均復号時間及び復号時間中央値を示す。
【００８３】
ここでは、また、復号するために必要な整数制約の数に対する統計も収集する。整数制約は、通常の線形制約に比較して大幅にＬＰソルバを低速化する。図４は、ビット反転の数の関数としての整数制約の数を示す。最上の線４０１は、最悪の場合の反復数であり、次の線４０２は、ＭＬ符号語を見つけるために最大限指示された数の整数制約において取得された各ビット反転レベルでのシミュレーションの第９５百分位数、すなわち９５％を示す。また、第９０百分位数４０３及び第５０百分位数４０４(中央値)も示す。最悪の場合は、第９５百分位数よりはるかに悪いことに留意されたい。これらの数は、すべての復号(成功及び失敗)を組み合わせる。本発明による復号器には上限２００のＡＬＰ復号反復を課したことに留意されたい。この上限は、非常にまれにしか達せられず、最高ビット反転レベルにおいてのみ達せられる。本発明者らによるシミュレーションでは、上限は、２０ビット反転、２２ビット反転及び２３ビット反転において少なくとも１回のみ達せられる。ビット反転の他のすべての数に対し、上限は決して達せられない。
【００８４】
図４及び図３の表を比較することにより、整数制約の数が復号時間に大きい影響を与えることが分かる。図４は、１２ビット反転、１４ビット反転及び１６ビット反転に対する中央値の場合、整数制約が０であることを示す。これは、中央値の場合が、整数制約なしにＡＬＰ復号を実行していることを意味する。
【００８５】
図３の表を参照すると、これは、対応する中央復号時間、すなわち０．１２秒、０．１５秒、０．２３秒が、整数制約のないＡＬＰ復号の復号時間要件を示すことを意味する。対照的に、対応する平均復号時間、すなわち０．１４秒、０．２２秒、０．８７秒は、混合整数ＡＬＰ復号を介するＭＬ復号の平均復号時間要件を示す。このように、誤り率の１０３〜１０５の向上に必要な平均復号時間の増大はほんのわずかである。
【００８６】
より高い雑音レベル、たとえば１８又は２０ビット反転がある場合、中央値の場合は正の数の整数制約を使用する。対応する中央復号時間は、それぞれ１．３３秒及び２０．６秒まで急速に増大する。
【００８７】
発明の効果
ＭＬ符号語を見つけるためにＡＬＰ復号器に整数制約を追加する方法について述べた。本発明による方法を高速化するために、適応ＬＰ復号の計算効率を利用する。本発明では、ＭＬ復号性能を得るには驚くほど長い符号である(１５５，６４)ＬＤＰＣ符号に対して復号器を適用する。
【００８８】
好ましい実施の形態の例を用いて本発明について説明したが、本発明の精神及び範囲内で他のさまざまな適応及び変更を行うことができる、ということが理解されるべきである。したがって、添付の特許請求の範囲の目的は、本発明の真の精神及び範囲内にあるこのような変形及び変更のすべてを包含することである。
【図面の簡単な説明】
【００８９】
【図１】従来のＬＰ復号と本発明の一実施の形態によるＭＬ復号とのビット反転の関数としてのワード誤り率を比較するグラフである。
【図２】従来のＬＰ復号と、従来のＢＰ復号と、本発明の一実施の形態によるＭＬ復号との交叉確率の関数としてのワード誤り率を比較するグラフである。
【図３】ビット反転の数の関数としての、本発明の一実施の形態によるＭＬ復号器の計算時間要件に対する統計の表である。
【図４】本発明の一実施の形態によるビット反転の数の関数としての二元制約の数のグラフである。
【図５】従来技術による適応線形計画法復号のフローチャートである。
【図６】本発明の一実施の形態による適応線形計画法復号を使用する最尤復号のフローチャートである。
【図１】
2009005343.tif 000029
【図２】
2009005343.tif 000030
【図３】
2009005343.tif 000031
【図４】
2009005343.tif 000032
【図５】
2009005343.tif 000033
【図６】
2009005343.tif 000034
【外国語明細書】
2009005343.tif 000035
2009005343.tif 000036
2009005343.tif 000037
2009005343.tif 000038
2009005343.tif 000039
2009005343.tif 000040
2009005343.tif 000041
2009005343.tif 000042
2009005343.tif 000043
2009005343.tif 000044
2009005343.tif 000045
2009005343.tif 000046
2009005343.tif 000047
2009005343.tif 000048
2009005343.tif 000049
2009005343.tif 000050
2009005343.tif 000051
2009005343.tif 000052
2009005343.tif 000053
2009005343.tif 000054
2009005343.tif 000055
2009005343.tif 000056
2009005343.tif 000057
2009005343.tif 000058
2009005343.tif 000059
2009005343.tif 000060
2009005343.tif 000061