(57)【要約】格子暗号および（または）マルチレベル剰余型暗号で符号化された信号を復号するために、復号システムが反復復号技術を使用する。【選択図】図１
2005507513.tif 000002
【特許請求の範囲】
【請求項１】
符号化入力信号に関して事前確率を決定するステップと、
前記符号化入力信号に関するコードワードを推定するために前記事前確率を使用して前記符号化入力信号の反復復号を実行するステップと、
前記コードワードに基づいて、前記符号化入力信号に関するセル変換を決定するステップと
を備え、
前記コードワードが、基底格子のベース・セル内に存在する、
信号を復号する方法。
【請求項２】
前記セル変換を使用して、前記コードワードを前記基底格子の適切なセルへ写像するステップを更に備える、請求項１に記載の方法。
【請求項３】
前記符号化入力信号が、マルチレベル剰余型暗号で符号化される、請求項１に記載の方法。
【請求項４】
前記符号化入力信号が、格子暗号で符号化される、請求項１に記載の方法。
【請求項５】
前記符号化入力信号が、少なくとも１つの構成暗号を有する暗号で符号化され、
事前確率を決定するステップが、前記符号化入力信号に基づいて、第１構成暗号の第１座標が所定の値を有する確率を決定するステップを備える、
請求項１に記載の方法。
【請求項６】
前記符号化入力信号が、インターフェアラによって修正され
事前確率を決定するステップが、前記インターフェアラに関する統計に基づいて確率を決定するステップを備える、請求項１に記載の方法。
【請求項７】
前記インターフェアラに関連する前記統計が既知である、請求項６に記載の方法。
【請求項８】
事前確率を決定するステップが、前記確率を決定する際に使用するための前記インターフェアラ用の統計を仮定するステップを備える、請求項６に記載の方法。
【請求項９】
統計を仮定するステップが、前記インターフェアラが格子のボロノイ・セル内に一様に分布すると仮定するステップを備える、請求項８に記載の方法。
【請求項１０】
統計を仮定するステップが、前記ボロノイ・セルが球状であると仮定するステップを備える、請求項９に記載の方法。
【請求項１１】
反復復号を行なうステップが、
第１情報を生成するために、前記事前確率を使用して第１復号反復を行なうステップと、
第２情報を生成するために、前記第１情報を使用して、第２復号反復を行なうステップと
を備える、請求項１に記載の方法。
【請求項１２】
反復復号を行なうステップが、複数の構成復号器間で情報を交換するステップを備える、請求項１に記載の方法。
【請求項１３】
複数の構成復号器間で情報を交換するステップが、外部情報を交換するステップを備える、請求項１２に記載の方法。
【請求項１４】
符号化入力信号に関して事前確率を決定する事前確率ジェネレータと、
前記事前確率を使用して、反復復号によって前記符号化入力信号に関するコードワードを決定する反復復号ユニットと、
前記コードワードに基づいて、前記符号化入力信号に関するセル変換を決定する変換決定ユニット
を備え、
前記コードワードが、基底格子のベース・セル内に存在する、
復号システム。
【請求項１５】
前記セル変換を使用して、前記コードワードを前記基底格子の適切なセルへ写像するセル写像ユニットを更に備える、請求項１４に記載の復号システム。
【請求項１６】
前記符号化入力信号が、マルチレベル剰余型暗号で符号化される、請求項１４に記載の復号システム。
【請求項１７】
前記符号化入力信号が、格子暗号で符号化される、請求項１４に記載の復号システム。
【請求項１８】
前記反復復号ユニットが、前記符号化入力信号の複数の構成暗号を復号するために、複数の構成復号器を備える、請求項１４に記載の復号システム。
【請求項１９】
前記複数の構成復号器が、前記反復復号中に軟情報を相互に交換する、請求項１８に記載の復号システム。
【請求項２０】
前記反復復号ユニットが、反復復号器である少なくとも１つの構成復号器を備える、請求項１８に記載の復号システム。
【請求項２１】
前記反復復号ユニットが、軟入力・軟出力（ＳＩＳＯ）復号器である少なくとも１つの構成復号器を備える、請求項１８に記載の復号システム。
【請求項２２】
前記事前確率ジェネレータが、インターフェアラに関する既知の統計に基づいて前記事前確率を生成する、請求項１４に記載の復号システム。
【請求項２３】
前記事前確率ジェネレータが、インターフェアラの統計を仮定し、前記仮定された統計に基づいて前記事前確率を生成する、請求項１４に記載の復号システム。
【請求項２４】
前記事前確率ジェネレータが、前記インターフェアラが格子のボロノイ・セル内に一様に分布されると仮定する、請求項２３に記載の復号システム。
【請求項２５】
前記事前確率ジェネレータが、前記ボロノイ・セルが球状であると仮定する、請求項２４に記載の復号システム。
【請求項２６】
前記事前確率ジェネレータが、前記インターフェアラが０平均および未知の分散を有するガウス分布を含むと仮定する、請求項２３に記載の復号システム。
【請求項２７】
関連するデータを有する機械可読媒体を備える物品であって、前記データがアクセスされた場合、信号を復号する方法を機械が実行し、前記方法が、
符号化入力信号に関して事前確率を決定するステップと、
前記符号化入力信号に関するコードワードを推定するために前記事前確率を使用して前記符号化入力信号の反復復号を実行するステップと、
前記コードワードに基づいて、前記符号化入力信号に関するセル変換を決定するステップと
を備え、
前記コードワードが、基底格子のベース・セル内に存在する、
物品。
【請求項２８】
前記方法が、前記セル変換を使用して、前記コードワードを前記基底格子の適切なセルへ写像するステップを更に備える、請求項２７に記載の物品。
【請求項２９】
前記符号化入力信号が、マルチレベル剰余型暗号で符号化される、請求項２７に記載の物品。
【請求項３０】
前記符号化入力信号が、格子暗号で符号化される、請求項２７に記載の物品。
【請求項３１】
反復復号を行なうステップが、前記複数の構成復号器間で情報を交換するステップを備える、請求項２７に記載の物品。
【請求項３２】
情報を交換するステップが、複数の構成復号器間で外部情報を交換するステップを備える、請求項３１に記載の物品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、広義には信号の復号に関し、より詳細には、格子暗号および（または）マルチレベル剰余型暗号で符号化された信号の復号に関する。
【背景技術】
【０００２】
最尤復号は、マルチレベル剰余型暗号および（または）格子暗号で符号化された信号を復号する際の最適解を示す。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
しかしながら、最尤復号は多くの場合において実際的ではない。例えば、暗号が複雑な格子を持っている場合、最尤復号は実際的ではない場合がある。例えば、マルチレベル剰余型暗号あるいは格子暗号内の構成暗号の個数が多い場合、あるいは、構成暗号の最小の格子数が多い場合、複雑な格子が存在し得る。複雑な格子は格納するのが（また引き出すのが）一般に困難であり、最尤復号が使用される場合、復号する段階で実施する計算の数が極めて多くなる。この理由のために、最尤復号技術よりも計算上の複雑度のより低いマルチレベル剰余型暗号および格子暗号のための復号方法が必要である。
【発明を実施するための最良の形態】
【０００４】
以下の詳細な説明において、本発明が実施され得る特定の実施形態を例示する添付の図面に参照が為される。これらの実施形態は、当業者が本発明を実施し得るために充分に詳細に記載されている。本発明の様々な実施形態は、相互に相違があるが、必ずしも相互に排他的である必要性は無い事が理解される。例えば、１つの実施形態に関連して本願明細書において記載されている特定の特徴、構成または特性は、本発明の精神と範囲から逸脱すること無く、他の実施形態の範囲内で実施され得る。加えて、開示された各実施形態の個々の要素の位置または配列は、本発明の精神と範囲から逸脱することなく修正され得る事が理解される。従って、以下の詳細な説明は、本発明を限定するようには解釈されず、本発明の範囲は添付の特許請求の範囲によってのみ確定され、特許請求の範囲が権利を与える均等物の全範囲と共に適切に解釈される。全ての図面において、同様の参照番号は、同一または同様の機能性を表す。
【０００５】
本発明は、マルチレベル剰余型暗号および（または）格子暗号によって符号化された信号を、反復復号技術を使用して復号する方法と構造に関する。本発明の技術は、例えば最尤復号のような最適復号解よりも計算上の複雑さが顕著に少なく、それでいて最適の方法に近い性能を達成する事が出来る。複雑度が低いので、本発明の技術は、高次元の暗号における使用に際して特に有用である。一実施形態において、モジュロ格子相加性雑音チャネルを通って受信されたデータワードは、多符号コードワードおよびインターフェアラの和として扱われる。インターフェアラの統計は、多符号コードワードに関する事前確率を決定するために使用される。その後、反復復号技術は、事前確率を使用して、多符号コードワードの個々の暗号要素を復号するために使用される。反復復号プロセスは、例えば、多くの構成復号器の間での情報（例えば外部情報）の交換を含んでいて良い。多符号コードワードが復号された後、セルの変換が決定され、多符号コードワードを適切な基底格子セルへ写像するために使用される。本願明細書の記載において、「多符号」と言う語は、は基底格子のベース・セル内に存在するマルチレベル剰余型暗号（あるいは格子暗号）のコードワードのセットを指す。また、「多符号コードワード」と言う語は、単一の多符号のコードワードの事である。本発明の原理は、マルチレベル剰余型暗号および（または）格子暗号を使用する通信システムおよび他のシステムへ適用される。
【０００６】
格子はいくつかの規則を満たさなければならない。即ち、加算に対して閉じており、各格子要素の逆元を含んでおり、零元を含んでおり（つまり、座標軸の起点がこの格子点である）、また、離散的でなければならない。従って、格子は、スペースの全領域におけるベース即ち単位格子の反復によって作成される、複数の点の離散的な無限集合である。格子暗号は、格子の有限部分集合である。そのため、格子暗号は、格子と、有界サポートの領域と交差として定義されて良い。境界域の影響を無視する復号規則は、格子復号と称される。境界域を考慮に入れる他の復号規則（例えば最小距離復号）が存在する。本発明の原理が、格子復号および最小距離復号技術の双方に関して使用されてもよい。格子は多くの異なる方法によって、１つ以上の個々のコードより構築される（例えば、Ｊ．Ｈ．コンウェイ（Ｊ．Ｈ．Ｃｏｎｗａｙ）等、「球状のパッキング、格子および群（Ｓｐｈｅｒｅ  Ｐａｃｋｉｎｇｓ，  Ｌａｔｔｉｃｅｓ  ａｎｄ  Ｇｒｏｕｐｓ）」、１３７〜１５６ページおよび２３２〜２３６ページ、シュプリンガー出版、ニューヨーク、１９９９年）。１つのアプローチにおいて、例えば、ｘがバイナリ線形符号Ｃのコードワードに２を法として合同である場合、点ｘ＝（ｘ１、ｘ２、…、ｘｎ）は格子点と見做される。本願明細書において、このような格子は「構造Ａ」格子として参照される。構造Ａ格子は数学的に以下のように表現され得る。
【０００７】
【数１】
2005507513.tif 000003
【０００８】
ここで、Ｃは長さｎのバイナリコードであり、ｎは格子の各点の座標の個数であり、２Ｚｎは、格子Λｎを形成するために暗号Ｃの複数の点を変換する格子である（Ｚは整数の集合である）。本願明細書において、格子２Ｚｎは格子Λｎの基底格子として参照される。暗号Ｃのコードワードが各々、基底格子のベース・セル（つまり起点を含むセル）内に生じる。本願明細書において構造Ｄと参照される、より一般的な格子構造は、次のように表現され得る。
【０００９】
【数２】
2005507513.tif 000004
【００１０】
構成暗号｛Ｃｉ｝ｉ＝１ｋは、ネストにされる（つまり、ＣｉのコードワードはさらにＣｉ＋１のコードワードでもある）線形のバイナリコードであり、ｋは構成暗号の数であり、また、２ｋＺｎは、格子Λｎを形成するために多符号（数３）の点を変換する基底格子である。前述されたように、多符号（数３）のコードワードが、基底格子２ｋＺｎのベース・セル内に生じる。単一成分の暗号の際は、構造Ｄ格子は上述された構造Ａ格子へ低減する。上述された複数の式のそれぞれの変換の値は、ｎ個の座標のそれぞれにおいて、同一であっても良いし、異なっていても良い。
【００１１】
【数３】
2005507513.tif 000005
【００１２】
剰余型暗号は、以下のように表現することができる無限コードブック・サイズの暗号である。
【００１３】
【数４】
2005507513.tif 000006
【００１４】
ここで、Λ⊇Λ１は格子であり、［Λ／Λ１］は、Λにおける剰余系代表値Λ１の有限の完全集合であり、Ｃ０⊆（［Λ／Λ１］）ｎが暗号である。上記の式中の格子（Λ１）ｎは、剰余型暗号Ｃを形成するために暗号Ｃ０の点を変換する基底格子である。マルチレベル剰余型暗号は次のように表現し得る無限コードブック・サイズの暗号である。
【００１５】
【数５】
2005507513.tif 000007
【００１６】
ここで、Λ⊇Λ１⊇Λ２⊇…⊇Λｋ＋１は格子であり、Ｃｋ⊆（［Λｋ／Λｋ＋１］）ｎ、……Ｃｋ−１⊆（［Λｋ−１／Λｋ］）ｎ、Ｃ１⊆（［Λ／Λ１］）ｎである。多符号の点（Ｃ１＋Ｃ２＋Ｃ３＋…＋Ｃｋ）が、基底格子（Λｋ＋１）ｎのベース・セル内に生じる。基底格子（Λｋ＋１）ｎの点は、マルチレベル剰余型暗号Ｃを形成するために多符号（Ｃ１＋Ｃ２＋Ｃ３＋…＋Ｃｋ）の点を変換する。格子（Λｋ＋１）ｎは時間変化するマルチレベル剰余型暗号を生成するために直積（数６）と置換可能である。数７の場合、マルチレベル剰余型暗号Ｃは、構造Ｄ格子に低減される。従って、構造Ｄ格子はマルチレベル剰余型暗号の１つの形式である。マルチレベル剰余型暗号は、構造Ｄ格子とは２つの一次領域において異なる。即ち、（１）構造Ｄ格子の構成暗号のネスト・プロパティは、マルチレベル剰余型暗号のために必要でなく、（２）マルチレベル剰余型暗号によって使用される集合は１次元である必要がない（つまり、Λｋ＋１はＺと同形である必要が無い）。後続の議論において、本発明の原理は、マルチレベル剰余型暗号の文脈における一般論としてその殆どが記載される。しかしながら、本発明の原理が、他の格子の種類と同様に構造Ａおよび構造Ｄ格子に等しく適用可能であることが認識されるべきである。
【００１７】
【数６】
2005507513.tif 000008
【００１８】
【数７】
2005507513.tif 000009
【００１９】
図１は、本発明の一実施形態における復号システム１０を示すブロック線図である。復号システム１０は、例えば雑音の多い通信路を伝送されてきた入力ワード（数１０）を受信する。この入力ワードを使用して、復号システム１０は、チャネルへ当初送信された対応するコードワード（数１１）を決定しなければならない。コードワード（数１２）は、システム内に使用されているマルチレベル剰余型暗号の有効なコードワードである。コードワード（数１２）は、マルチレベル剰余型暗号の構成暗号（数１３）のそれぞれからの要素と、ワードを適切な格子セルに変換する変換項（数１４）を含む。チャネルを伝播する間、コードワード（数１２）は、加算によってコードワードを修正する干渉信号（数１５）によって作用される。このプロセスは以下のように表現することができる。
【００２０】
【数８】
2005507513.tif 000010
【００２１】
干渉信号（数１６）は、例えば、既知の確率密度関数を有する付加白色ガウス雑音（ＡＷＧＮ）を含んで良い。上記の式の項を再整理する事によって、入力ワード（数２０）は以下のように表現することが出来る。
【００２２】
【数９】
2005507513.tif 000011
【００２３】
ここで、数１７は多符号コードワードであり、数１８がインターフェアラとして扱われる。後に詳述するように、１つのアプローチにおいて、多符号コードワード（数１９）は反復復号技術を使用して最初に復号され、次に、変換（数１４）が決定され、基底格子の適切なセルへ多符号コードワード（数１９）を写像するために使用される。
【００２４】
【数１０】
2005507513.tif 000012
【００２５】
【数１１】
2005507513.tif 000013
【００２６】
【数１２】
2005507513.tif 000014
【００２７】
【数１３】
2005507513.tif 000015
【００２８】
【数１４】
2005507513.tif 000016
【００２９】
【数１５】
2005507513.tif 000017
【００３０】
【数１６】
2005507513.tif 000018
【００３１】
【数１７】
2005507513.tif 000019
【００３２】
【数１８】
2005507513.tif 000020
【００３３】
【数１９】
2005507513.tif 000021
【００３４】
図１に示されるように、復号システム１０は、事前確率ジェネレータ１２と、反復復号ユニット１４と、セル変換決定ユニット１６と、セル写像ユニット１８とを備える。図１において示される個々のブロックはその性質において機能的であり、必ずしも離散的なハードウェア要素に相当しないことが認識されるべきである。例えば、本発明の一実施形態において、機能ブロックの１つ以上（あるいは全部）は、１つ以上のディジタル演算処理装置（例えば、汎用マイクロプロセッサ、デジタルシグナルプロセッサー（ＤＳＰ）、縮小命令型コンピュータ（ＲＩＳＣ）、複雑命令セットコンピュータ（ＣＩＳＣ）、フィールドプログラム可能なゲートアレイ（ＦＰＧＡ）および（または）その他）内のソフトウェア中で実施される。更に、全部及び一部にハードウェアを適用する事も可能である。
【００３５】
入力ワード（数２０）を使用して、事前確率ジェネレータ１２は、対応するマルチレベル剰余型暗号の構成暗号のそれぞれに対する確率を生成する。インターフェアラ（数１６）の統計が既知である場合（例えば確率密度関数）、これらの統計が事前確率を決定するために使用されてもよい。更に、後述されるように、インターフェアラの統計が既知で無い場合、複数の技術が、事前確率を決定するために提供される。反復復号ユニット１４は、反復復号技術を使用して、多符号コードワード（数１９）の構成暗号を復号するべく作用する。反復復号ユニット１４は、反復プロセスを初期化するために、事前確率ジェネレータ１２によって生成された事前確率を使用する。セル変換決定ユニット１６は、反復復号ユニット１４によって決定された入力ワード（数２０）および多符号コードワード（数１９）に基づいて、コードワード（数１２）の変換（数１４）を決定する。その後、セル写像ユニット１８は、コードワード（数１２）を出力するために、セル変換決定ユニット１６によって決定された変換（数１４）に基づいて、多符号コードワード（数１９）を適切な格子セルへ写像する。
【００３６】
【数２０】
2005507513.tif 000022
【００３７】
反復復号においては、コードワードのビットに関する２種類の情報が存在する。即ち、該ビットのチャネル監視に依存する情報と、暗号の性質により該ビットに反映する他のビットのチャネル監視に依存する情報である。後者の情報は「外部情報」として参照される。
【００３８】
本発明の一実施形態において、事前確率ジェネレータ１２は、入力ワード（数２０）の内容およびインターフェアラ（数１６）の統計に基づいて、個々の構成暗号の各座標が所定のバイナリ値（例えば０）を有する確率を決定する。１つのこのようなアプローチにおいて、先ず、１つのセットＳ（ｍ）が、ｍ番目の座標を２進法で表した場合が０である全てのシンボルｒのセットとして定義される。例えば、数２３の場合、数２４が成立する。その後、セットＳｉ（ｍ）は、時刻ｉ（つまりｒｉ）におけるシンボルに対応するセットＳ（ｍ）として定義される。続いて、ｍ番目の構成暗号のｉ番目の時刻の座標が０である事前確率が、次式より与えられる。
【００３９】
【数２１】
2005507513.tif 000023
【００４０】
記号が離散的な場合、項Ｐ（ｙ＋ｌ｜ｒ）が確率関数を表し、記号が連続的な場合は密度関数を表す事が認識される。格子復号の際は、全ての変換が有効であると仮定されている場合、確率（数２５）は定数であると認められ、数２１は以下のように簡略化される。
【００４１】
【数２２】
2005507513.tif 000024
【００４２】
【数２３】
2005507513.tif 000025
【００４３】
【数２４】
2005507513.tif 000026
【００４４】
【数２５】
2005507513.tif 000027
【００４５】
１つの適用において、これらの総和は、最も重要な項のみを含むように切り捨てられる。上述の議論において、事前確率は従来型の確率として表される。事前確率は、例えば公算比、対数尤度比（ＬＬＲ）、確率差および他の同様の形式を含む、本発明の他の多数の方法の中の任意の形式によって表され得るということが認識されるべきである。
【００４６】
本発明の少なくとも１つの実施形態において、反復復号ユニット１４は、マルチレベル剰余型暗号の構成暗号のそれぞれに対して個別の復号器を備える。これらの構成復号器のそれぞれは、入力において軟情報を受信し、出力において復号器の識別の信頼性を示す軟情報を生成するために入力を利用するような、軟入力軟出力（ＳＩＳＯ）復号器である事が好ましい。図２は、図１のシステム１０の中で使用され得る反復復号ユニット２８を示す図である。図示されるように、反復復号ユニット２８はマルチレベル剰余型暗号の構成暗号の対応する１つを復号するために各々使用される第１、第２、および第３の構成復号器２０、２２、２４（それぞれ、復号器１、復号器２および復号器３）を備える。構成復号器２０、２２、２４のそれぞれは、事前確率ジェネレータ１２によって生成された対応する事前確率を受信する。構成復号器２０、２２、２４は、対応する出力で柔情報やその他のものを生成するために、この入力情報を処理する。その後、構成復号器２０、２２、２４は相互に柔情報（例えば外部情報）を交換する。また、この新しい情報を用いて次回の処理が行なわれる。個々の復号器２０、２２、２４の識別の精度を上げて更新するために、このような処理が、数回あるいはそれ以上の回数反復される。少なくとも１つの実施形態において、この反復は所定の回数行なわれる。別のアプローチにおいて、反復の回数は、復号器の出力に依存するように為される。続いて、個々の構成復号器２０、２２、２４は、出力多符号コードワードの対応する部分の最良推定値（軟判定または硬判定のいずれか）を出力する。その後、多符号コードワード（例えば数２６）の推定が、反復復号ユニット２８から出力される。
【００４７】
【数２６】
2005507513.tif 000028
【００４８】
反復復号ユニット２８は、任意の個数の構成復号器を備えていて良い。反復復号ユニット２８の個々の構成復号器２０、２２、２４が、さらに多くの形態を採っても良い。例えば、少なくとも１つの実施形態において、１つ以上の構成復号器２０、２２、２４それ自体が反復復号器である。使用可能な幾つかの反復復号器の種類は、例えば、ターボ復号器および低密度パリティチェック（ＬＤＰＣ）復号器を含んでいる。反復復号ユニット２８の各反復については、反復する構成復号器が、１つ以上のそれ自身の反復の行なうことが出来る。その後、反復構成復号器は、例えば、他の構成復号器への分配のために、外部情報に加えて事後ＬＬＲ  （または硬判定）を出力してよい。反復しない構成復号器を使用することが出来る（例えば、最大事後確率（ＭＡＰ）復号器、フォワード・バックワード・アルゴリズム復号器、軟出力ビタビ・アルゴリズム復号器など）。反復しない構成復号器は、さらに他の構成復号器のために事後ＬＬＲ（または硬判定）および外部情報を出力して良い。構成復号器２０、２２、２４はすべて同一の物であって良いし、異なる種類の復号器を使用しても良い。本発明の一実施形態において、後の反復に先立って、ｍ番目の構成復号器（ｉ番目の時間座標の）に配信された情報は、次の確率を含んでいる。
【００４９】
【数２７】
2005507513.tif 000029
【００５０】
ここで、Ｄ（ｊ）（η）は、ｉ番目の時間座標におけるｊ番目の構成暗号（ｃｊ）のコードワードの値であり、もしηが多符号の値である場合、数２８はｊ番目の復号器から受信した事後情報である。簡潔さのために、ｉの従属は上記の式中で省略された。
【００５１】
【数２８】
2005507513.tif 000030
【００５２】
図１を再び参照して、単一の構成暗号のみを有するマルチレベル剰余型暗号が使用される時（例えば構造Ａ格子）、反復復号ユニット１４は通常は単一の反復復号器のみを備えるであろう。明らかなように、このような配置で構成される復号器間においては情報の交換は行なわれず、単に復号器の出力から入力までの情報のフィード・バックがあるに過ぎない。
【００５３】
セル変換決定ユニット１６は、入力ワード（数２０）に関する変換（例えば数２９）を決定するために、反復復号ユニット１４によって出力された多符号コードワード推定（数２６）および入力ワード（数２０）を使用する。１つのアプローチにおいて、この変換は数３０を決定することにより解かれる。幾つかの場合において、この表現は数３１とも表される。そのあと、セル写像ユニット１８は、推定された変換（数３２）を使用して、適切な格子セルへ多符号コードワード（数２６）を写像する。セル写像ユニット１８は硬値または軟値を出力して良い。
【００５４】
【数２９】
2005507513.tif 000031
【００５５】
【数３０】
2005507513.tif 000032
【００５６】
【数３１】
2005507513.tif 000033
【００５７】
【数３２】
2005507513.tif 000034
【００５８】
図１の復号システム１０の演算の例として、暗号の各格子点の座標の数が３（つまりｎ＝３）で、暗号の構成暗号の数が２（つまりｋ＝２）である、と仮定する。さらに第１構成暗号Ｃ１がコードワード（０００）および（１１１）を含み、第２構成暗号Ｃ２がコードワード（０００）、（０１１）、（１０１）、および（１１０）を含むと仮定する。これらの暗号の例は、例示の目的で記載されているのであって、実際の暗号を示すものではない事に注意されたい（例えば、暗号はネストにされない）。更に、チャネルから受信した入力ワードが数３４であると仮定する。決定される必要のある格子点（数３５）は次のように表現される。
【００５９】
【数３３】
2005507513.tif 000035
【００６０】
反復復号ユニット１４は、数３６のように決定する。従って、数３７が成立する。推定された変換（数３２）を決定するために、先ず数３８が決定される。その後、このベクトルは取り得る値４Ｚｎと比較され、適切な変換（数３２）が（４  ４  −４）（つまり数３９）である事を決定する。従って、この出力（数３５）は、数４０であると決定される。
【００６１】
【数３４】
2005507513.tif 000036
【００６２】
【数３５】
2005507513.tif 000037
【００６３】
【数３６】
2005507513.tif 000038
【００６４】
【数３７】
2005507513.tif 000039
【００６５】
【数３８】
2005507513.tif 000040
【００６６】
【数３９】
2005507513.tif 000041
【００６７】
【数４０】
2005507513.tif 000042
【００６８】
本発明の少なくとも１つの実施形態において、ターボ反復が行なわれる。すなわち、出力ワード数３５を生成する一回前に数２６と数３２を決定する代わりに、多くの反復が行なわれ、各反復において、前回の値の精度がより高められる。図３は、本発明の実施形態におけるターボ反復を行なうために適応される復号システム５０を示すブロック線図である。図示されるように、フィードバック・ループ５４は、数２６そして数３２の最新の値を生成するのに用いるために、数３２のその時点における値に関する情報を反復復号ユニット１４の入力にフィード・バックするためにフィードバック・ループ５４が付け加えられている。前述したように、所定の回数の反復が行なわれても良いし、反復の回数は出力に依存しても良い。
【００６９】
上記の記述では、インターフェアラの統計（数１６）が知られていたと仮定されていた。しかしながら、このようなインターフェアラの統計の特徴が存在しない場合、反復プロセスを初期化するための他の手段が開発されている必要がある。最小ユークリッド距離判定基準が使用されている場合（つまり、ユークリッド距離中で数２０に最も接近しているマルチレベル剰余型暗号点）、多くの初期設定のストラテジーが可能である。１つのアプローチにおいて、例えば、インターフェアラが０平均および未知の分散σ２を含むガウス分布を有すると仮定する。本ガウス分布はユークリッド距離の陽関数である。別のアプローチでにおいて、インターフェアラが基底格子のボロノイ・セル内に一様に分布されると仮定される。このアプローチの近似において、ボロノイ・セルΛｋ＋１は、半径Ｒのｖ次元の球であると仮定され得る。通常、高い次元数の格子において、これは良い近似を示すであろう。球の体積はＶｖ（Ｒ）と表され、Ｖｖ（Ｒ）＝Ｒｖ×定数であると言う事が公知である。従って、数４１およびインターフェアラによって２乗された距離の確率密度関数は、数４２によって与えられる。このアプローチが使用される場合、対数尤度比は半径Ｒに依存しない。従って、反復的アルゴリズムは、Ｒの値が既知である必要がない。Ｒの正確値が未知であり得るので、これは非常に好適である。
【００７０】
【数４１】
2005507513.tif 000043
【００７１】
【数４２】
2005507513.tif 000044
【００７２】
図４は、本発明の実施形態における信号を復号する方法を示すフローチャートである。本方法の一部または全部が、コンピュータ読取り可能な媒体  （例えばＣＤ−ＲＯＭ（ＣＤＲＯＭ）、フロッピディスク、テープ、半導体メモリなど）上に格納したソフトウェア・プログラムがとして実施および（または）配布されて良い。同様に、本方法の一部または全部は、特定用途向けＩＣ（ＡＳＩＣ）あるいは他のディジタル回路内に実施されても良い。先ず、マルチレベル剰余型暗号で符号化入力信号が受信される（ブロック３０）。次に、事前確率が入力信号を使用して決定される（ブロック３２）。インターフェアラに関連した統計が、事前確率を決定するために更に使用されてもよい。１つのアプローチにおいて、インターフェアラの統計が既知である。他のアプローチにおいて、統計はインターフェアラ用に仮定される。例えば、上述されたように、半径Ｒのｎ次元の球であるボロノイ・セル内にインターフェアラが一様に分布されると仮定することが出来る。更に、他の技術を使用することも可能である。
【００７３】
一旦事前確率が決定されると、多符号コードワード（数２６）を推定するべく、入力信号の反復復号プロセスを初期化するために使用される（ブロック３４）。複数の構成暗号が含まれている場合、反復復号プロセスは、２回以上の反復サイクルにおいての個々の構成復号器の間での情報交換を含んでいて良い。次に、反復復号プロセスの結果に基づいて、入力信号用の変換の推定（数３２）が決定される（ブロック３６）。随意に、変換および推定された多符号コードワードは、さらに１つ以上の追加の反復サイクルにおいて、反復復号プロセスの結果の精度を向上させるために使用することが出来る（ブロック３８）。最後に、変換は、基底格子の適切なセルへ反復復号プロセスの結果を写像するために使用される（ブロック４０）。
【００７４】
本発明の原理は、通信システム内の使用に制限されていないことが認識されるべきである。例えば、ベクトル量子化（例えば音声／画像圧縮）に依る任意の応用に対して、本発明における複雑性の減少した格子復号器の使用から利益を得ても良い。さらに、他の非通信ベースの適用が可能である。
【００７５】
本発明は特定の実施形態と連携して記載されているが、当業者が容易に理解するように、本発明の精神と範囲から逸脱することなく、修正および変更が為され得ることが理解される。この種の修正および変更は、本発明の添付の特許請求の範囲内であると見做される。
【図面の簡単な説明】
【００７６】
【図１】本発明の実施形態における復号システムを示すブロック線図である。
【図２】本発明の実施形態における反復復号ユニットを示す図である。
【図３】本発明の実施形態におけるターボ反復を行なうために適応される復号システムを示すブロック線図である。
【図４】本発明の実施形態における信号を復号する方法を示すフローチャートである。
【図１】
2005507513.tif 000045
【図２】
2005507513.tif 000046
【図３】
2005507513.tif 000047
【図４】
2005507513.tif 000048
【国際公開パンフレット】
2005507513.tif 000049
2005507513.tif 000050
2005507513.tif 000051
2005507513.tif 000052
2005507513.tif 000053
2005507513.tif 000054
2005507513.tif 000055
2005507513.tif 000056
2005507513.tif 000057
2005507513.tif 000058
2005507513.tif 000059
2005507513.tif 000060
2005507513.tif 000061
2005507513.tif 000062
2005507513.tif 000063
2005507513.tif 000064
2005507513.tif 000065
2005507513.tif 000066
2005507513.tif 000067
2005507513.tif 000068
2005507513.tif 000069
2005507513.tif 000070
【国際公開パンフレット（コレクトバージョン）】
2005507513.tif 000071
【国際調査報告】
2005507513.tif 000072
2005507513.tif 000073
2005507513.tif 000074