局所的な誤り検出符号を備えた誤り訂正符号化の方法、それに対応する復号化の方法、送信装置、受信装置、および、記憶装置、およびプログラム
本発明は、冗長データをソースデータに対応させ、かつ、少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する符号化方法に関し、前記局所的符号は、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、前記局所的符号は、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスは、基本符号を定義する。
【発明の詳細な説明】
【技術分野】
【０００１】
１．技術分野
本発明の分野は、特に、ディジタルデータの送信または記憶を鑑みて、そのディジタルデータを符号化する分野である。より詳細には、本発明は、誤り訂正符号に関する。
【０００２】
本発明は、誤り訂正符号を有することが必要なあるいは少なくとも望ましい全ての分野に適用されてもよい。したがって、本発明は、例えば、
- 例えば、ＤＥＣＴシステム、ＧＳＭシステム、ＵＭＴＳシステム、ローカルホームオートメーションネットワーク、衛星通信のような無線通信システムにおいて使用するために、物理的な送信チャンネルに固有の雑音および干渉による誤りからの保護（典型的な誤り訂正符号化および複数アンテナシステムのための空間時間符号）、
- ＣＤＭＡ符号化、
- 画像、音、信号、データ、などの情報源から到来する信号の圧縮、
- コンピュータディスクまたはマイクロプロセッサーのような大容量記憶装置にデータを記憶する際の誤りからの保護、
に適用されてもよい。
【背景技術】
【０００３】
２．背景技術
誤り訂正のための多くの符号化技術が、既知である。この主題に関する最初の研究は、１９４０年代にさかのぼる。なぜなら、それは、シャノンが、今日いまだに使用されている情報理論の基礎を提出した時であるからである。
【０００４】
そして、多くの種類の符号化が、提案された。現在の最先端の誤り訂正符号は、最新のターボ符号およびＬＤＰＣ符号によってうまく表現される。
【０００５】
ターボ符号は、１９９１年にＢｅｒｒｏｕおよびＧｌａｖｉｅｕｘ［３］によって考案された（引用された参考文献は、説明の最後の第９節にまとめられている）。
【０００６】
図１に示されるように、ターボ符号は、最初に、小さな数の状態（一般的には、８〜１６）を有するトレリスによって表現される畳み込み符号化（畳み込み符号化）１１によって情報ブロック（Ｘビットブロック）を符号化し（すなわち、冗長ビットＹ１のブロックを計算する）、そして、別の順序（１２）で情報ブロックを置換（permutate）しあるいは組み合わせ、再度、それらの情報ブロックを符号化し（１３）、冗長ビットＹ２のブロックを提供する。
【０００７】
したがって、送信される符号化ブロックは、Ｘ、Ｙ１、およびＹ２によって構成され、それどころか、置換されたその他のブロック１４またはさらなる冗長ビットＹｉの符号化ブロック１５によって構成される。
【０００８】
１９９０年代における大規模な民生用アプリケーションに使用される電子チップ技術と互換性を有する復号化の小さな複雑さのためのターボ符号の公表およびそれらのターボ符号の性能特性の発見は、誤り訂正符号およびそれらの軟判定反復復号化（soft-decision iterative decoding）に関する多くの論文を生み出した。最終的に、１９４８年に公表されたシャノンの限界に近づき、電気的な有線リンク、光ファイバーリンク、または、無線リンクのいずれにせよ、使用される通信路の最大ボーダーライン容量に近いビット率で情報を送信することができつつある。
【０００９】
情報理論の分野におけるこのリニューアルは、Ｇａｌｌａｇｅｒ［１］によって１９６０年に考案されたＬＤＰＣ（「低密度パリティー検査」）の１９９５年における再発見、および、これらの符号を一般化するＴａｎｎｅｒ［２］による１９８１年における研究、そして、様々なＬＤＰＣ符号、すなわち、ＤｉｖｓａｌａｒおよびＭｃＥｌｉｅｃｅによる１９９８年におけるＲＡ（「反復積算」Repeat-Accumulate）符号［４］の公表をもたらした。
【００１０】
ＬＤＰＣ符号は、パリティー検査マトリックスＨによって定義され、そのＨは、まばらであり、すなわち、少数の１と多数の０を備える（バイナリ符号の場合）。例えば、整数モジュロ４｛０、１、２、３｝の環Ｚ４のような４つの要素からなる文字を使用するような非バイナリＬＤＰＣ符号の場合、制御マトリックスは、多くの０ときわめて少ない非０のシンボル｛１、２、３｝とを有する。
【００１１】
マトリックスの定義をわかりやすくするために、初期バイナリＬＤＰＣまたは「正則ＬＤＰＣ」は、パラメータ［ｎ＝１２、ｋ＝８、ｄmin＝２］を備えた以下のＬＤＰＣ符号（４、２）の例の場合と同様に行あたりの《１》の数ｄcおよび列あたりの《１》の数ｄvを有するまばらなパリティー検査マトリックスによって定義される（すなわち、それぞれの行に４つの「１」およびそれぞれの列に２つの「１」を有する検査マトリックスを備えた長さ１２の符号）。
【数１】
【００１２】
ＬＤＰＣ符号の別の表現は、それらの二部（bipartite）Ｔａｎｎｅｒグラフであり、それは、グラフの左側に配置されたノード（または、頂点verticeｓ）によって変数を表現し、また、このグラフの右側に配置されかつバイナリ変数にアーム（または、稜線ridge）によって結合されたノードによって表現されるＸＯＲ値によって検査式（または、制約constraints）を表現する。
【００１３】
図２は、上述したマトリックスに対応する二部Ｔａｎｎｅｒグラフを示す。ｉ＝０、１、．．．、１１を備えた１２個の変数ｘiの頂点は、黒い点２１によって表現される。６つの制約２２（モジュロ和２）が、右側に配置され、Ｃjによって参照され、ｊ＝０、１、．．．，５である。置換（permutation）２３は、変数と制約とを相互接続するアームによって示される。
【００１４】
符号の検査マトリックスＨの１行における４に等しい１の数はまた、それぞれのＸＯＲ制約の入力の数であることがわかる。この数はまた、制約の次数または局所的符号の次数と呼ばれ、ｄcによって参照される。また、同様に、符号の検査マトリックスＨの１列における２に等しい１の数は、それぞれの変数の反復の回数である。また、この数は、変数の次数と呼ばれ、ｄvによって参照される。符号全体の率ｒ＝ｋ／ｎは、下限値：
【数２】
を有する。
【００１５】
一般的には、次数は、一方の変数から他方の変数へ変化してもよく、かつ、符号は、異なってもよい。ＸＯＲ制約が、「局所的」符号として知られている小さな符号に置き換えられるならば、符号全体は、Ｔａｎｎｅｒ符号と呼ばれる。
【００１６】
図３は、ＬＤＰＣ符号のアーキテクチャーよりも一般的なＴａｎｎｅｒ符号のアーキテクチャーを示す。符号Ｃｉ３１は、ＬＤＰＣ符号の場合と同様にＸＯＲ演算によって得られる簡単なパリティー符号よりもはるかに複雑な符号であってもよい。
【００１７】
３．これらの従来技術の欠点
ターボ符号、ＬＤＰＣ符号、および、それらの変形は、誤り訂正の点において、少なくとも数千かまたは数万の情報ビットを有する大きなブロックサイズに対してだけでなく、復号化するときの計算の大きな複雑さに対しても注目すべき性能特性を提供するが、その復号化は、今日のマイクロプロセッサーの絶え間なく増大する計算容量に依存したままである。
【００１８】
しかしながら、復号化の複雑さを大きく減少させることが、これらの誤り訂正符号化復号化機能を実施するコンポーネントの製造業者によって強く望まれている。なぜなら、それは、それらの機能を実施する電子チップのシリコン表面積、したがって、それらの製造コストを減少させ、その結果として、より安いコストを消費者に提供するからである。
【００１９】
また、この複雑さの減少は、全ての消費者によって望まれる。なぜなら、それは、また、例えば、携帯電話電池または移動無線通信ネットワークに接続されたラップトップ型パソコンによって提供される電力のより少ない消費をもたらし、それによって、携帯端末のより大きな自律性をもたらし、あるいは、より軽い端末をもたらすからである。
【００２０】
一般的なターボ符号は、長さの最良の対数で最小距離ｄminを有し、また、通信路の容量に近づくＬＤＰＣは、符号の長さの最良の対数で最小距離ｄminを有する。すなわち、
【数３】
【００２１】
多くの種類の符号は、符号の最小距離が符号の長さとともに線形に増加すれば、漸近的に良好（ＡＧ）であると言われる。すなわち、
【数４】
【００２２】
したがって、今日既知の符号の性能は、誤り訂正能力および復号化の複雑さを減少させることの両方の点において、最適なものではなく、さらに改善されてもよい。
【００２３】
さらに、今日の符号の既知の構造は、約百ビットから千ビット程度の小さなブロックサイズに対する誤り訂正の点において、きわめて低い性能を呈する。小さなパケットのディジタル通信伝送に対する広範囲にわたるきわめて大きな需要が、これらの短い長さの符号に興味を持たせる理由である。
【００２４】
バイナリ誤り率の点における性能の向上は、特に、ユーザに提供されるサービスの品質の向上をもたらすかもしれない。すなわち、
− 基地局の改善されたレンジ、
− 雑音の少ないデータ伝送、
− 得ることのできるより高い最大情報スループット率、
− 基地局によってカバーされる同一領域において同時に存在するより大きな数のユーザ。
【００２５】
４．本発明の目的
本発明は、特に、従来技術の様々な欠点を克服するように設計される。
【００２６】
より詳細には、本発明の目的は、従来技術の符号、特に、ターボ型符号またはＬＤＰＣ型符号よりも実施するのが簡単かつ効率的な誤り訂正符号化技術を提供することである。
【００２７】
したがって、本発明の目的は、符号の複雑さを減少させるのに使用することのできるこの種の符号化技術（したがって、それに対応する復号化演算）を提供することであり、それによって、例えば、コンポーネントに使用されるシリコン表面積および必要とされるエネルギー消費量を減少させる。
【００２８】
より詳細には、本発明の目的は、今日の最良の訂正符号の場合よりも複雑さと誤り訂正能力との有効な妥協点を提供する符号を組み立てるのを可能にすることである。それによって達成される目的の１つは、所与の通信路、すなわち、バイナリ対称通信路（ＢＳＣ）、バイナリ消失通信路（ＢＥＣ）、ガウス通信路、などに対してより小さな複雑さを得るための既存の最良のＬＤＰＣ符号およびターボ符号の情報伝送能力を最適化する際に、それらのＬＤＰＣ符号およびターボ符号の誤り訂正性能をさらに改善する誤り訂正符号を得ることである。
【００２９】
本発明のさらなる目的は、理論的な限界にできるだけ近づくきわめて良好な誤り訂正品質を有するこの種の符号化技術を提供することである。
【００３０】
より詳細には、本発明の目的は、小さなサイズのブロックにさえも有効な誤り訂正符号を提供することである。
【００３１】
したがって、本発明の目的は、最小距離ｄminを増加させることによって「ｅｒｒｏｒ−ｆｌｏｏｒ」現象を実際に除去するきわめて効率的な短い誤り訂正符号を組み立てるのを可能にすることである。「ｅｒｒｏｒ−ｆｌｏｏｒ」という用語は、バイナリ誤り率（ＢＥＲ）が高い信号対雑音比の場合には低い信号対雑音比の場合よりもそれほど急速には減少しないことを指し、ＢＥＴ曲線のその部分は、「ｗａｔｅｒｆａｌｌ」とも呼ばれる。
【００３２】
５．本発明の主たる特徴
これらの目的および以下でより明確になるその他のことは、冗長データをソースデータに対応させ、かつ、少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する符号化方法によって達成される。本発明によれば、局所的符号は、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、そして、前記局所的符号は、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスは、基本符号を定義する。
【００３３】
きわめて簡単な基本符号を使用することに頼るこの新しい進歩性のあるアプローチは、当業者の先入観に逆らうものである。包括的な誤り訂正符号（「全体符号」と呼ばれる）を組み立てるための、単なる誤り検出器符号である簡単な符号の使用は、自明のことではない。
【００３４】
しかしながら、この直観でわかるものではないアプローチは、意外にもきわめて良好な結果を得るのを可能にし、それらの結果は、上述した従来技術による符号のものよりも良好なものであり、それと同時に、複雑さを減少させる。以下からわかるように、本発明は、シャノン限界に近づくのを可能にする。
【００３５】
さらに、本発明は、多くの種類の符号に有効であり、特に、「ｅｒｒｏｒ−ｆｌｏｏｒ」現象として既知の現象を厳しく制限する短い誤り訂正器符号に有効である。
【００３６】
有利には、前記置換は、前記ラベル語に適用され、前記状態語には適用されない。
【００３７】
したがって、処理される変数の数を減少させる簡単なシステムが得られる。
【００３８】
第１の実施態様によれば、前記局所的符号は、２状態トレリスまたは４状態トレリスによって表現されるバイナリ符号である。
【００３９】
第２の実施態様によれば、前記局所的符号は、２n個の要素を備えた符号化文字に関して定義され、かつ、２n状態，２n+1状態、または、２n+2状態を備えたトレリスによって表現される（ｎは、２よりも大きな整数である）。例えば、４要素符号化の場合、それは、４状態トレリス、８状態トレリス、または、１６状態トレリスによって表現されてもよい。
【００４０】
いずれの場合においても、きわめて簡単な局所的符号が存在し、そのために、実施するのがきわめて容易であることに留意されたい。
【００４１】
好ましくは、前記基本符号のそれぞれは、ｍ個のシンボルからなる長さを備えた符号語を提供し、それぞれのシンボルは、符号化文字の少なくとも１つのビットに対応し、符号化文字は、
有意性２を備えた符号語の数は、ｍ／２よりも小さいかまたはｍ／２に等しく、
有意性３を備えた符号語の数は、０でない、
ように定義され、符号語の有意性は、それが含む０と異なるシンボルの数である。
【００４２】
この構造は、きわめて良好な符号化結果を提供する。
【００４３】
有利には、前記基本符号語の少なくとも１つは、少なくとも２つの符号セクションによって構成される。
【００４４】
本発明によれば、間引きを前記基本符号の少なくとも１つに実施することもできる。
【００４５】
この間引きは、変数に適用されてもよく、および／または、符号のブランチに適用されてもよい。
【００４６】
本発明の有利な態様によれば、トレリスの少なくとも１つは、巡回的トレリスである。
【００４７】
また、トレリスの少なくとも１つは、入力状態および出力状態が所定の値にセットされたトレリスであってもよい。
【００４８】
本発明の第１の実施形態によれば、前記局所的符号の少なくとも１つは、６つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（６、４、２）であり、
６は、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
４は、前記局所的符号のサイズであり、
２は、前記基本符号からの最小距離である。
【００４９】
この場合、前記基本符号は、有利には、前記符号（６、４、２）の３つのセクションによって構成される。
【００５０】
本発明の第２の実施形態によれば、前記局所的符号の少なくとも１つは、４つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（４、３、２）であり、
４は、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
３は、前記局所的符号のサイズであり、
２は、前記基本符号からの最小距離である。
【００５１】
この場合、前記基本符号は、有利には、前記符号（４、３、２）の２つのセクションによって構成される。
【００５２】
本発明の第３の実施形態によれば、前記局所的符号の少なくとも１つは、６つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（６、５、２）であり、
６は、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
５は、前記局所的符号のサイズであり、
２は、前記基本符号からの最小距離である。
【００５３】
この場合、前記基本符号は、有利には、前記符号（６、５、２）の３つのセクションによって構成される。
【００５４】
本発明の第４の実施形態によれば、前記局所的符号の少なくとも１つは、８つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する４状態符号（８、７、２）であり、
８は、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
７は、前記局所的符号のサイズであり、
２は、前記基本符号からの最小距離である。
【００５５】
本発明の第５の実施形態によれば、前記局所的符号の少なくとも１つは、８つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（８、７、２）であり、
８は、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
７は、前記局所的符号のサイズであり、
２は、前記基本符号からの最小距離である。
【００５６】
最後の２つの場合においては、前記基本符号は、有利には、前記符号（８、７、２）の８つのセクションによって構成される。
【００５７】
本発明は、また、上述した符号化方法によるデータを復号化するための方法に関する。
【００５８】
この種の復号化方法は、少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を符号化と対称的に提供し、前記局所的符号は、検出符号ではあるが、所定の符号化文字における誤り訂正符号ではなく、前記局所的符号は、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスは、基本符号を定義する。
【００５９】
本発明はまた、上述した符号化方法を実行する符号化されたデータを送信するための装置、符号化と対称的に動作する復号化手段を実行する、この符号化方法によって符号化されたデータを受信するための装置、および、上述した方法に基づいた符号化手段および／または復号化手段を含む符号化データ記憶装置に関する。
【００６０】
本発明は、また、上述した符号化方法および／または復号化方法を実行するコンピュータプログラムに関する。
【００６１】
本発明のその他の特徴および利点が、限定するものではない単なる例として提供される以下の本発明の好ましい実施形態の説明および添付の図面からより明確となる。
【発明を実施するための最良の形態】
【００６２】
７．発明の好ましい実施形態の説明
７．１ 序論
上述したように、本発明は、きわめて簡単な局所的符号を実施する誤り訂正器符号への新しいアプローチに頼るものであり、それらの局所的符号は、ただ単に誤り検出器符号であり、従来技術による符号よりも簡単かつ効率的な最終的な全体符号を提供するように組み合わせられる。
【００６３】
したがって、本発明の符号は、少ない数の状態（２つの状態および４つの状態）を備えたバイナリトレリスを使用することによる複雑さの減少によって区別されてもよい。これらの２つの状態（および、４つの状態）のトレリスによって組み立てられた符号の複雑さは、すでに標準的なものである１６個の状態を有するターボ符号および同等のＬＤＰＣ符号と比較すれば、１／８（および、１／４）ほどに減少することを推定することができる。
【００６４】
これらのトレリスの小さな複雑さにもかかわらず、得られる符号は、最良のターボ符号および現在使用されているＬＤＰＣ符号の複雑さ、誤り訂正能力、および、「ｅｒｒｏｒ−ｆｌｏｏｒ」の点において、より良好な妥協点を提供する。なぜなら、これらの新しい符号は、誤り率の点において少なくとも同じように効率的に実行し、かつ、実際に使用するのが同じように容易な「ｅｒｒｏｒ−ｆｌｏｏｒ」を有するからである。
【００６５】
以下の表は、以下に詳細に説明されるいくつかの達成される符号の性能特性および複雑さをまとめたものである。
【００６６】
局所的符号のパラメータは、（ラベルビットの数、寸法、この符号によって組み立てられた基本符号の最大ボーダーラインｄmin）である。
【００６７】
【表１】
【００６８】
また、バイナリ消失通信路（ＢＥＣ）に対する所与の消失訂正利得は、ガウス通信路において無視できない利得をもたらすことに留意されたい。
【００６９】
７．２ 本発明の主たる技術的要素
本発明による符号の組み立ては、トレリスセクションを「局所的符号」として知られる小さな符号Ｃjのきわめて少ない数の状態と連結することによって得られるトレリスによって記述される長さｍを有する「基本符号」に頼るものである。記述における曖昧さを回避するために、組み立てられた符号は、「全体符号」と呼ばれる。
【００７０】
このために、符号は、以下のようにして組み立てられる：
局所的符号の状態ビットが、互いに接続され、
変数の少なくとも大部分のビット（冗長ビットだけでなく、情報ビットも含む）が、反復され、そして、変数（新しくない）のそれらの反復されたビットの順序を変更する置換によって基本符号に接続される。
【００７１】
本発明の有利なアプローチは、以下の基準を満足するように、特定の局所的符号セクションを選択することである：
有意性２のｍビットの長さを有する基本符号語（大きなトレリス）の数は、ｍ／２よりも小さいかまたはｍ／２に等しい。
有意性３のｍビットの長さを有する基本符号語の数は、非ゼロである。
【００７２】
このアプローチは、以下に説明される６つの局所的符号に適用された。
【００７３】
これらの高性能特性の説明が、以下でなされる。きわめて小さい距離（それは、直観でわかるものではない）の誤り訂正符号を得ることが必要であり、最小値は、２である。この場合、符号は、訂正器符号ですらなく、１つの誤りだけを検出してもよい。
【００７４】
したがって、それらは、伝送雑音の存在下において最小可能閾値である情報抽出閾値を有する。有意性３の多数の語は、最小の大きな距離を有する「全体」訂正符号を得るのに使用されてもよい。したがって、誤り訂正符号が得られ、それは、シャノンの限界容量を達成してもよく、したがって、最小距離は、符号の長さに応じて線形に増加してもよい。
【００７５】
したがって、なされなければならないことは、ただ単に検出器符号である小さな符号を連結することである。
【００７６】
それぞれの局所的符号Ｃjは、小さな数のラベルビットｄＣjを有する：
【数５】
これらのｍビットの順序は、ｍビットの置換によって変更され、そして、結合され、次数ｄｘiの変数ｘi（ｉ＝０、１、ｎ−１）のビットを構成する。
【００７７】
したがって、基本的な技術的要素は、図４に示されるように接続された小さな局所的符号Ｃjによって構成されるトレリスの使用である。
【００７８】
局所的符号Ｃj４１のこの系列は、トレリスによって説明される基本符号４２を構成し、トレリスがループを形成すれば、そのトレリスは巡回的である、または《ｔａｉｌ−ｂｉｔｉｎｇ》であると言われる。
【００７９】
変数ｘi（ｉ＝０、１、ｎ−１）とも呼ばれるｎ個の符号ビット４３は、典型的には、図４に示される符号のＴａｎｎｅｒグラフの左側に配置される。これらの変数は、互いに異なってもよい次数ｄｘiによって反復され、これらの次数ｄｘiのベクトルは、変数の反復プロフィールと呼ばれる。
【００８０】
置換４４は、ターボ符号、ＬＤＰＣ符号、および、ＲＡ符号の場合と同様に、これらのビットの順序を変更する。図４の置換の右側には、いくつかのラベルシンボルｄＣjおよび入力状態ビットｖiおよび出力状態ビットｖi+1を有する局所的符号Ｃjによって構成された基本符号４２のトレリスが、配置される。
【００８１】
図５は、本発明のこの種の全体符号の例を表現するＴａｎｎｅｒのグラフであり、４つのラベルビットを備えた４つの局所的符号トレリスセクションに分解された長さｍ＝１６ビットの基本符号とともに一定の長さｎ＝８ビットの２次変数を有する。
【００８２】
局所的符号Ｃｉ間の１つ以上の「状態」ビットが、構成によってゼロに「セット」されていれば、「ｔａｉｌ−ｂｉｔｉｎｇ」トレリスは、典型的な非巡回的トレリスに関連づけられてもよい。ゼロ状態トレリス終結のこの技術は、復号化処理を簡素化するのに使用されてもよい周知の技術である。
【００８３】
図６からわかるように、トレリスをいくつかのサブトレリス６１および６２に分割することが可能である。これは、サブトレリスのそれぞれに対する復号化計算を並列処理するのを可能にし（これらの並列計算が統合される前に）、かつ、サブトレリスのそれぞれにおける相当な数のセクションを取り込むときに性能の大きな損失を伴うことなくなされる。
【００８４】
したがって、図６は、基本符号が２つのサブトレリス６１および６２に分割された「全体」符号を説明し、上部のサブトレリス（局所的符号Ｃ０〜Ｃj）６１は、終結状態６１１および６１２が０に等しい典型的なトレリスとして知られているトレリスであり、また、下部のサブトレリス（局所的符号Ｃj＋１〜Ｃｎｃ−１）６２は、終結条件が開始状態が到達状態に等しくなければならないということである「ｔａｉｌ−ｂｉｔｉｎｇ」トレリスである。
【００８５】
重要な組み立て要素は、高性能な置換、すなわち、最小の大きな距離を有する符号を与える置換を達成することである。これらの置換は、小さな局所的符号の「パターン」（または、いくつかのビットからなる部分集合、それらは、符号語内におけるそれらの位置に対して不変である）の特別な特性を使用する。
【００８６】
Ｔａｎｎｅｒのグラフのこの特定の構造をきわめて小さな状態数（バイナリシンボルの場合には２または４）を備えた小さな局所的符号のトレリスと組み合わせること、および、対応するそれらの置換は、全ての最良の敵対する符号よりも効率的な妥協点｛複雑さ、誤り訂正性能｝を提供する誤り訂正符号を提供する。
【００８７】
８．局所的符号の例
８．１ ２状態局所的符号（６、４、２）のトレリスセクション
図７に説明されるセクションは、ビットによってラベルを付されたブランチを通って開始状態の１つから到達状態の１つまで延びる一組のパスによって、パラメータの局所的符号からなる一組の符号語を表現する。
【００８８】
したがって、局所的符号（６、４、２）７１は、３つのトレリスセクション７２、７３、および、７４に分解され、それらのそれぞれは、２つのラベルビットを備える。
【００８９】
図８Ａ〜図８Ｃは、それぞれ、典型的な表現によってこれらの３つのセクションを示す。
【００９０】
トレリスセクションの概略的な表現は、入力状態０から出力状態０への遷移はラベルビットが００または１１に等しい場合に達成できることを意味する。これは、２重ラベルブランチであると言われる。
【００９１】
同じブランチのラベル（複数であろうとなかろうと）は、同じ入力状態に対応する同じ線上の括弧の中に配置され、連続する括弧は、同じ順序で、連続する到達状態に対応する。
【００９２】
図８Ｂのトレリスセクションをさらに説明すると、入力状態０から出力状態０への遷移は、ラベルビットが００または１１に等しい場合になすことができ、そして、入力状態０から出力状態１への遷移は、ラベルビットが０１または１０に等しい場合になすことができる。
【００９３】
２つの状態しか達成されないので、トレリスセクションは、きわめて小さな複雑さで軟判定反復器が復号化するのを可能にする。
【００９４】
さらに、有意性の遷移の代数的性質は、単独で考えれば、この符号はどのような誤りも訂正できるのではなく誤りをただ単に検出できるようなものである。しかしながら、トレリス内において集合的に組み立てられると、この符号は、それらのハミング重みパターンに適合された置換を備えた優れた符号となる。
【００９５】
図９は、２状態トレリス符号セクション（６、４、２）からなるトレリスによって組み立てられたこの基本符号の情報伝達曲線を示す。
【００９６】
８．２ ２状態局所的符号（４、３、２）のトレリスセクション
図１０は、上述したものと同じ原理に基づいて、局所的符号（４、３、２）を２つのトレリスセクションに分解することを示し、それらのトレリスセクションのそれぞれは、２つのラベルビットを備え、そして、図１１Ａおよび図１１Ｂは、２つの対応する状態を備えた局所的符号（４、３、２）からなるトレリスの２つのセクションを示す。
【００９７】
図１２からわかるように、情報伝達曲線は、原点において４５．３％の傾きを有する直線に対して接線方向にあり、これは、レート１／２符号に対する５０％の可能最大理論値に対して全体符号の消失を４５．３％だけ訂正する能力があることを意味する。
【００９８】
８．３ ２状態局所的符号（６、５、２）のトレリスセクション
図１３は、上述したものと同じ原理に基づいて、局所的符号（６、３、２）を２つのトレリスセクションに分解することを示し、それらのトレリスセクションのそれぞれは、３つのラベルビットを備え、そして、図１４Ａおよび図１４Ｂは、２つの対応する状態を備えた局所的符号（６、３、２）からなるトレリスの２つのセクションを示す。
【００９９】
この場合にも、図１５から、以下の情報伝達曲線は、原点において３０％の傾きを有する直線に対して接線方向にあることがわかり、これは、レート２／３符号に対する３３．３３％の可能最大理論値に対して全体符号の消失を３０％だけ訂正する能力があることを意味する。
【０１００】
８．４ ４状態局所的符号（８、７、２）のトレリスセクション
図１６は、８つのセクションに「爆発的に増加した」トレリスを説明し、それらのそれぞれは、１つのラベルビットを有する。ビット（ｂ0、ｂ1、ｂ2、ｂ3）およびビット（ｂ4、ｂ5、ｂ6、ｂ7）は、２つのセクションにグループとしてまとめられてもよく、それらのそれぞれは、図１７、図１８Ａ、および、図１８Ｂからわかるように、４つの入力状態および４つの出力状態を有する。
【０１０１】
図１９の情報伝達曲線は、原点において２１．５％の傾きを有する直線に対して接線方向にあり、これは、レート３／４（＝０．７５）符号に対する２５％の可能最大理論値に対して全体符号の消失を２１．５％だけ訂正する能力があることを意味する。これは、２状態局所的符号（８、７、２）の２２．１５％よりも小さいが、この種類の符号は、漸近的に良好（ＡＧ）である。
【０１０２】
８．５ ２状態局所的符号（８、７、２）のトレリスセクション
図２０は、上述したものと同じ原理に基づいて、局所的符号（８、７、２）を２つのトレリスセクションに分解することを示し、それらのトレリスセクションのそれぞれは、４つのラベルビットを備え、そして、図２１Ａおよび図２１Ｂは、２つの対応する状態を備えた局所的符号（６、３、２）からなるトレリスの２つのセクションを示す。
【０１０３】
図２２の情報伝達曲線は、原点において２２．１５％の傾きを有する直線に対して接線方向にあり、これは、レート３／４（＝０．７５）符号に対する２５％の可能最大理論値に対して全体符号の消失を２２．１５％だけ訂正する能力があることを意味する。
【０１０４】
８．６ 別の局所的符号（ｎ，ｋ，２）を構成するためのトレリスセクションの組み合わせ
パラメータ（６、４、２）および（４、３、２）を有する符号からなるトレリスを構成する２状態トレリスセクションをそれぞれ説明するこれまでの節に説明されるように、セクション１は、両方の符号において同一であり、また、符号（４、３、２）のセクション３と同一であり、同様に、セクション２は、両方の符号において同一であることがわかる。
【０１０５】
したがって、これまでに説明した様々な符号を構成する全てのセクションとそれらのセクション上においてラベルビットが間引かれまたは重複する可能性とを、全体符号の符号レートに関して多種多様な選択を可能にするパラメータ（ｎ，ｋ，２）を有する新しい局所的符号を組み立てるのに使用することができる。
【０１０６】
８．７ Ｚ４上における４状態符号（４、３、２）の例
Ｚ４は、加算モジュロ４を備えた一組の整数｛０、１、２、３｝である。符号のこの例は、その他の文字に容易に一般化することができる。なぜなら、それは、「Ｚ４への加算」法則を、考察される新しい文字への加算に関する法則に置き換えることを満足するからである。
【０１０７】
組み立てる方法は、文字、この場合には、Ｚ４上における反復符号によって開始することからなる：
Ｚ４への反復符号＝｛００、１１、２２、３３｝
【０１０８】
図２３は、この符号を２つのセクションに分解することを示し、そして、図２４Ａおよび図２４Ｂは、２つの対応するセクションを示す。
【０１０９】
複数のブランチのラベルは、同じ長さの語（横方向クラスを表現する「コセットリーダ」または語）を加算することによって、この反復符号から得られる。例えば、複数のブランチ（または、マルチブランチ）０１は、｛０１、１２、２３、３０｝をラベルとして有する。
【０１１０】
当然ながら、同じ一般化が、Ｚ８、Ｚ１６、．．．に適用されてもよい。
【０１１１】
９．参考文献
［１］Ｇａｌｌａｇｅｒ，《Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ ｃｏｄｅｓ》，Ｐｈ．Ｄ．Ｔｈｅｓｉｓ，ＭＩＴ，Ｊｕｌｙ １９６３．
［２］Ｒ．Ｍ．Ｔａｎｎｅｒ，《Ａ ｒｅｃｕｒｓｉｖｅ ａｐｐｒｏａｃｈ ｔｏ ｌｏｗ ｃｏｍｐｌｅｘｉｔｙ ｃｏｄｅｓ》，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ｖｏｌ ＩＴ−２７，ｐｐ．５３３−５４７，Ｓｅｐｔ １９８１．
［３］Ｃ．Ｂｅｒｒｏｕ，Ａ．Ｇｌａｖｉｅｕｘ ａｎｄ Ｐ．Ｔｈｉｔｉｍａｊｓｈｉｍａ，《Ｎｅａｒ Ｓｈａｎｎｏｎ ｌｉｍｉｔ ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｉｎｇ ａｎｄ ｄｅｃｏｄｉｎｇ：Ｔｕｒｂｏ ｃｏｄｅｓ》，ｐｐ．１０６４−１０７０，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｃｏｎｆｅｒｅｎｃｅ（ＩＣＣ），Ｍａｙ １９９３，Ｇｅｎｅｖａ．
［４］Ｄ．Ｄｉｖｓａｌａｒ ａｎｄ Ｒ．Ｊ．ＭｃＥｌｉｅｃｅ，《Ｃｏｄｉｎｇ ｔｈｅｏｒｅｍｓ ｆｏｒ ｔｕｒｂｏ−ｌｉｋｅ ｃｏｄｅｓ》，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ａｌｌｅｒｔｏｎ Ｃｏｎｆｅｒｅｎｃｅ（Ａｌｌｅｒｔｏｎ，Ｉｌｌｉｎｏｉｓ，ＵＳＡ），ｐｐ．２０１−２１０，Ｓｅｐｔ．１９９８．
［５］Ｔ．Ｒｉｃｈａｒｄｓｏｎ ａｎｄ Ｒ．Ｕｒｂａｎｋｅ，「Ｔｈｅ Ｃａｐａｃｉｔｙ ｏｆ Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ ｕｎｄｅｒ Ｍｅｓｓａｇｅ−Ｐａｓｓｉｎｇ Ｄｅｃｏｄｉｎｇ，」ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ｖｏｌ．４７，ｐｐ．５９９−６８１，Ｆｅｂｒｕａｒｙ ２００１．
［６］Ｔ．Ｒｉｃｈａｒｄｓｏｎ，Ａ．Ｓｈｏｋｒｏｌｌａｈｉ ａｎｄ Ｒ．Ｕｒｂａｎｋｅ，「Ｄｅｓｉｇｎ ｏｆ Ｃａｐａｃｉｔｙ Ａｐｐｒｏａｃｈｉｎｇ Ｉｒｒｅｇｕｌａｒ Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ，」ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ｖｏｌ．４７，ｐｐ．６１９−６３７，Ｆｅｂｒｕａｒｙ ２００１．
【図面の簡単な説明】
【０１１２】
【図１】序文において説明され、ターボ符号の原理の概略図を提供する。
【図２】同様に、序文において説明され、ＴａｎｎｅｒグラフによるＬＤＰＣ符号（４、２）の表現を提供する。
【図３】同様に、序文において説明され、ＴａｎｎｅｒグラフによるＴａｎｎｅｒ符号の概略図を提供する。
【図４】本発明による誤り訂正符号の原理を説明するＴａｎｎｅｒグラフである。
【図５】４つのラベルビットを備えた４つのセクションの局所的トレリス符号に分解された長さｍ＝１６ビットの基本符号とともに一定の長さｎ＝８ビットの２次変数を有する、本発明による典型的な符号のＴａｎｎｅｒグラフである。
【図６】本発明による別の典型的な符号のＴａｎｎｅｒグラフであり、基本符号のトレリスは、２つのサブトレリスに分割されており、一方は、ゼロ状態終結を備え、他方は、「ｔａｉｌ−ｂｉｔｉｎｇ」を備える。
【図７】本発明による全体符号において使用することのできる第１の局所的符号（６、４、２）を３つのトレリスセクションに分解することを示す図であり、それぞれのトレリスセクションは、２つのラベルビットを備える。
【図８Ａ】図７の局所的符号（６、４、２）のセクションを示す図である。
【図８Ｂ】図７の局所的符号（６、４、２）のセクションを示す図である。
【図８Ｃ】図７の局所的符号（６、４、２）のセクションを示す図である。
【図９】２状態トレリス符号セクション（６、４、２）からなるトレリスによって組み立てられた基本符号に関する情報伝達曲線である。
【図１０】本発明による全体符号において使用することのできる第２の局所的符号（４、３、２）を２つのトレリスセクションに分解することを示す図であり、それぞれのトレリスセクションは、２つのラベルビットを備える。
【図１１Ａ】図１０の局所的符号（４、３、２）のセクションを示す図である。
【図１１Ｂ】図１０の局所的符号（４、３、２）のセクションを示す図である。
【図１２】２状態トレリス符号セクション（４、３、２）からなるトレリスによって組み立てられた基本符号に関する情報伝達曲線である。
【図１３】本発明による全体符号において使用することのできる第３の局所的符号（６、５、２）を２つのトレリスセクションに分解することを示す図であり、それぞれのトレリスセクションは、３つのラベルビットを備える。
【図１４Ａ】図１３の局所的符号（６、５、２）のセクションを示す図である。
【図１４Ｂ】図１３の局所的符号（６、５、２）のセクションを示す図である。
【図１５】２状態トレリス符号セクション（６、５、２）からなるトレリスによって組み立てられた基本符号に関する情報伝達曲線である。
【図１６】本発明による全体符号において使用することのできる第４の局所的４状態符号（８、７、２）の《爆発的に増加した》非セクション化トレリスを示す図である。
【図１７】本発明による全体符号において使用することのできる第５の局所的符号（８、７、２）を２つのトレリスセクションに分解することを示す図であり、それぞれのトレリスセクションは、４つのラベルビットを備える。
【図１８Ａ】図１７の局所的符号（８、７、２）のセクションを示す図である。
【図１８Ｂ】図１７の局所的符号（８、７、２）のセクションを示す図である。
【図１９】４状態トレリス符号セクション（８、７、２）からなるトレリスによって組み立てられた基本符号に関する情報伝達曲線である。
【図２０】局所的符号（８、７、２）を２つのトレリスセクションに別の方法で分解することを示す図であり、それぞれのトレリスセクションは、４つのラベルビットを備える。
【図２１Ａ】図２０の局所的符号のセクションを示す図である。
【図２１Ｂ】図２０の局所的符号のセクションを示す図である。
【図２２】２状態トレリス符号セクション（８、７、２）からなるトレリスによって組み立てられた基本符号に関する情報伝達曲線である。
【図２３】第６の局所的符号（４、３、２）を分解することを示す図であり、Ｚ４上において４つの状態を備える。
【図２４Ａ】図２３のトレリスセクションを示す図である。
【図２４Ｂ】図２３のトレリスセクションを示す図である。
【技術分野】
【０００１】
１．技術分野
本発明の分野は、特に、ディジタルデータの送信または記憶を鑑みて、そのディジタルデータを符号化する分野である。より詳細には、本発明は、誤り訂正符号に関する。
【０００２】
本発明は、誤り訂正符号を有することが必要なあるいは少なくとも望ましい全ての分野に適用されてもよい。したがって、本発明は、例えば、
- 例えば、ＤＥＣＴシステム、ＧＳＭシステム、ＵＭＴＳシステム、ローカルホームオートメーションネットワーク、衛星通信のような無線通信システムにおいて使用するために、物理的な送信チャンネルに固有の雑音および干渉による誤りからの保護（典型的な誤り訂正符号化および複数アンテナシステムのための空間時間符号）、
- ＣＤＭＡ符号化、
- 画像、音、信号、データ、などの情報源から到来する信号の圧縮、
- コンピュータディスクまたはマイクロプロセッサーのような大容量記憶装置にデータを記憶する際の誤りからの保護、
に適用されてもよい。
【背景技術】
【０００３】
２．背景技術
誤り訂正のための多くの符号化技術が、既知である。この主題に関する最初の研究は、１９４０年代にさかのぼる。なぜなら、それは、シャノンが、今日いまだに使用されている情報理論の基礎を提出した時であるからである。
【０００４】
そして、多くの種類の符号化が、提案された。現在の最先端の誤り訂正符号は、最新のターボ符号およびＬＤＰＣ符号によってうまく表現される。
【０００５】
ターボ符号は、１９９１年にＢｅｒｒｏｕおよびＧｌａｖｉｅｕｘ［３］によって考案された（引用された参考文献は、説明の最後の第９節にまとめられている）。
【０００６】
図１に示されるように、ターボ符号は、最初に、小さな数の状態（一般的には、８〜１６）を有するトレリスによって表現される畳み込み符号化（畳み込み符号化）１１によって情報ブロック（Ｘビットブロック）を符号化し（すなわち、冗長ビットＹ１のブロックを計算する）、そして、別の順序（１２）で情報ブロックを置換（permutate）しあるいは組み合わせ、再度、それらの情報ブロックを符号化し（１３）、冗長ビットＹ２のブロックを提供する。
【０００７】
したがって、送信される符号化ブロックは、Ｘ、Ｙ１、およびＹ２によって構成され、それどころか、置換されたその他のブロック１４またはさらなる冗長ビットＹｉの符号化ブロック１５によって構成される。
【０００８】
１９９０年代における大規模な民生用アプリケーションに使用される電子チップ技術と互換性を有する復号化の小さな複雑さのためのターボ符号の公表およびそれらのターボ符号の性能特性の発見は、誤り訂正符号およびそれらの軟判定反復復号化（soft-decision iterative decoding）に関する多くの論文を生み出した。最終的に、１９４８年に公表されたシャノンの限界に近づき、電気的な有線リンク、光ファイバーリンク、または、無線リンクのいずれにせよ、使用される通信路の最大ボーダーライン容量に近いビット率で情報を送信することができつつある。
【０００９】
情報理論の分野におけるこのリニューアルは、Ｇａｌｌａｇｅｒ［１］によって１９６０年に考案されたＬＤＰＣ（「低密度パリティー検査」）の１９９５年における再発見、および、これらの符号を一般化するＴａｎｎｅｒ［２］による１９８１年における研究、そして、様々なＬＤＰＣ符号、すなわち、ＤｉｖｓａｌａｒおよびＭｃＥｌｉｅｃｅによる１９９８年におけるＲＡ（「反復積算」Repeat-Accumulate）符号［４］の公表をもたらした。
【００１０】
ＬＤＰＣ符号は、パリティー検査マトリックスＨによって定義され、そのＨは、まばらであり、すなわち、少数の１と多数の０を備える（バイナリ符号の場合）。例えば、整数モジュロ４｛０、１、２、３｝の環Ｚ４のような４つの要素からなる文字を使用するような非バイナリＬＤＰＣ符号の場合、制御マトリックスは、多くの０ときわめて少ない非０のシンボル｛１、２、３｝とを有する。
【００１１】
マトリックスの定義をわかりやすくするために、初期バイナリＬＤＰＣまたは「正則ＬＤＰＣ」は、パラメータ［ｎ＝１２、ｋ＝８、ｄmin＝２］を備えた以下のＬＤＰＣ符号（４、２）の例の場合と同様に行あたりの《１》の数ｄcおよび列あたりの《１》の数ｄvを有するまばらなパリティー検査マトリックスによって定義される（すなわち、それぞれの行に４つの「１」およびそれぞれの列に２つの「１」を有する検査マトリックスを備えた長さ１２の符号）。
【数１】
【００１２】
ＬＤＰＣ符号の別の表現は、それらの二部（bipartite）Ｔａｎｎｅｒグラフであり、それは、グラフの左側に配置されたノード（または、頂点verticeｓ）によって変数を表現し、また、このグラフの右側に配置されかつバイナリ変数にアーム（または、稜線ridge）によって結合されたノードによって表現されるＸＯＲ値によって検査式（または、制約constraints）を表現する。
【００１３】
図２は、上述したマトリックスに対応する二部Ｔａｎｎｅｒグラフを示す。ｉ＝０、１、．．．、１１を備えた１２個の変数ｘiの頂点は、黒い点２１によって表現される。６つの制約２２（モジュロ和２）が、右側に配置され、Ｃjによって参照され、ｊ＝０、１、．．．，５である。置換（permutation）２３は、変数と制約とを相互接続するアームによって示される。
【００１４】
符号の検査マトリックスＨの１行における４に等しい１の数はまた、それぞれのＸＯＲ制約の入力の数であることがわかる。この数はまた、制約の次数または局所的符号の次数と呼ばれ、ｄcによって参照される。また、同様に、符号の検査マトリックスＨの１列における２に等しい１の数は、それぞれの変数の反復の回数である。また、この数は、変数の次数と呼ばれ、ｄvによって参照される。符号全体の率ｒ＝ｋ／ｎは、下限値：
【数２】
を有する。
【００１５】
一般的には、次数は、一方の変数から他方の変数へ変化してもよく、かつ、符号は、異なってもよい。ＸＯＲ制約が、「局所的」符号として知られている小さな符号に置き換えられるならば、符号全体は、Ｔａｎｎｅｒ符号と呼ばれる。
【００１６】
図３は、ＬＤＰＣ符号のアーキテクチャーよりも一般的なＴａｎｎｅｒ符号のアーキテクチャーを示す。符号Ｃｉ３１は、ＬＤＰＣ符号の場合と同様にＸＯＲ演算によって得られる簡単なパリティー符号よりもはるかに複雑な符号であってもよい。
【００１７】
３．これらの従来技術の欠点
ターボ符号、ＬＤＰＣ符号、および、それらの変形は、誤り訂正の点において、少なくとも数千かまたは数万の情報ビットを有する大きなブロックサイズに対してだけでなく、復号化するときの計算の大きな複雑さに対しても注目すべき性能特性を提供するが、その復号化は、今日のマイクロプロセッサーの絶え間なく増大する計算容量に依存したままである。
【００１８】
しかしながら、復号化の複雑さを大きく減少させることが、これらの誤り訂正符号化復号化機能を実施するコンポーネントの製造業者によって強く望まれている。なぜなら、それは、それらの機能を実施する電子チップのシリコン表面積、したがって、それらの製造コストを減少させ、その結果として、より安いコストを消費者に提供するからである。
【００１９】
また、この複雑さの減少は、全ての消費者によって望まれる。なぜなら、それは、また、例えば、携帯電話電池または移動無線通信ネットワークに接続されたラップトップ型パソコンによって提供される電力のより少ない消費をもたらし、それによって、携帯端末のより大きな自律性をもたらし、あるいは、より軽い端末をもたらすからである。
【００２０】
一般的なターボ符号は、長さの最良の対数で最小距離ｄminを有し、また、通信路の容量に近づくＬＤＰＣは、符号の長さの最良の対数で最小距離ｄminを有する。すなわち、
【数３】
【００２１】
多くの種類の符号は、符号の最小距離が符号の長さとともに線形に増加すれば、漸近的に良好（ＡＧ）であると言われる。すなわち、
【数４】
【００２２】
したがって、今日既知の符号の性能は、誤り訂正能力および復号化の複雑さを減少させることの両方の点において、最適なものではなく、さらに改善されてもよい。
【００２３】
さらに、今日の符号の既知の構造は、約百ビットから千ビット程度の小さなブロックサイズに対する誤り訂正の点において、きわめて低い性能を呈する。小さなパケットのディジタル通信伝送に対する広範囲にわたるきわめて大きな需要が、これらの短い長さの符号に興味を持たせる理由である。
【００２４】
バイナリ誤り率の点における性能の向上は、特に、ユーザに提供されるサービスの品質の向上をもたらすかもしれない。すなわち、
− 基地局の改善されたレンジ、
− 雑音の少ないデータ伝送、
− 得ることのできるより高い最大情報スループット率、
− 基地局によってカバーされる同一領域において同時に存在するより大きな数のユーザ。
【００２５】
４．本発明の目的
本発明は、特に、従来技術の様々な欠点を克服するように設計される。
【００２６】
より詳細には、本発明の目的は、従来技術の符号、特に、ターボ型符号またはＬＤＰＣ型符号よりも実施するのが簡単かつ効率的な誤り訂正符号化技術を提供することである。
【００２７】
したがって、本発明の目的は、符号の複雑さを減少させるのに使用することのできるこの種の符号化技術（したがって、それに対応する復号化演算）を提供することであり、それによって、例えば、コンポーネントに使用されるシリコン表面積および必要とされるエネルギー消費量を減少させる。
【００２８】
より詳細には、本発明の目的は、今日の最良の訂正符号の場合よりも複雑さと誤り訂正能力との有効な妥協点を提供する符号を組み立てるのを可能にすることである。それによって達成される目的の１つは、所与の通信路、すなわち、バイナリ対称通信路（ＢＳＣ）、バイナリ消失通信路（ＢＥＣ）、ガウス通信路、などに対してより小さな複雑さを得るための既存の最良のＬＤＰＣ符号およびターボ符号の情報伝送能力を最適化する際に、それらのＬＤＰＣ符号およびターボ符号の誤り訂正性能をさらに改善する誤り訂正符号を得ることである。
【００２９】
本発明のさらなる目的は、理論的な限界にできるだけ近づくきわめて良好な誤り訂正品質を有するこの種の符号化技術を提供することである。
【００３０】
より詳細には、本発明の目的は、小さなサイズのブロックにさえも有効な誤り訂正符号を提供することである。
【００３１】
したがって、本発明の目的は、最小距離ｄminを増加させることによって「ｅｒｒｏｒ−ｆｌｏｏｒ」現象を実際に除去するきわめて効率的な短い誤り訂正符号を組み立てるのを可能にすることである。「ｅｒｒｏｒ−ｆｌｏｏｒ」という用語は、バイナリ誤り率（ＢＥＲ）が高い信号対雑音比の場合には低い信号対雑音比の場合よりもそれほど急速には減少しないことを指し、ＢＥＴ曲線のその部分は、「ｗａｔｅｒｆａｌｌ」とも呼ばれる。
【００３２】
５．本発明の主たる特徴
これらの目的および以下でより明確になるその他のことは、冗長データをソースデータに対応させ、かつ、少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する符号化方法によって達成される。本発明によれば、局所的符号は、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、そして、前記局所的符号は、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスは、基本符号を定義する。
【００３３】
きわめて簡単な基本符号を使用することに頼るこの新しい進歩性のあるアプローチは、当業者の先入観に逆らうものである。包括的な誤り訂正符号（「全体符号」と呼ばれる）を組み立てるための、単なる誤り検出器符号である簡単な符号の使用は、自明のことではない。
【００３４】
しかしながら、この直観でわかるものではないアプローチは、意外にもきわめて良好な結果を得るのを可能にし、それらの結果は、上述した従来技術による符号のものよりも良好なものであり、それと同時に、複雑さを減少させる。以下からわかるように、本発明は、シャノン限界に近づくのを可能にする。
【００３５】
さらに、本発明は、多くの種類の符号に有効であり、特に、「ｅｒｒｏｒ−ｆｌｏｏｒ」現象として既知の現象を厳しく制限する短い誤り訂正器符号に有効である。
【００３６】
有利には、前記置換は、前記ラベル語に適用され、前記状態語には適用されない。
【００３７】
したがって、処理される変数の数を減少させる簡単なシステムが得られる。
【００３８】
第１の実施態様によれば、前記局所的符号は、２状態トレリスまたは４状態トレリスによって表現されるバイナリ符号である。
【００３９】
第２の実施態様によれば、前記局所的符号は、２n個の要素を備えた符号化文字に関して定義され、かつ、２n状態，２n+1状態、または、２n+2状態を備えたトレリスによって表現される（ｎは、２よりも大きな整数である）。例えば、４要素符号化の場合、それは、４状態トレリス、８状態トレリス、または、１６状態トレリスによって表現されてもよい。
【００４０】
いずれの場合においても、きわめて簡単な局所的符号が存在し、そのために、実施するのがきわめて容易であることに留意されたい。
【００４１】
好ましくは、前記基本符号のそれぞれは、ｍ個のシンボルからなる長さを備えた符号語を提供し、それぞれのシンボルは、符号化文字の少なくとも１つのビットに対応し、符号化文字は、
有意性２を備えた符号語の数は、ｍ／２よりも小さいかまたはｍ／２に等しく、
有意性３を備えた符号語の数は、０でない、
ように定義され、符号語の有意性は、それが含む０と異なるシンボルの数である。
【００４２】
この構造は、きわめて良好な符号化結果を提供する。
【００４３】
有利には、前記基本符号語の少なくとも１つは、少なくとも２つの符号セクションによって構成される。
【００４４】
本発明によれば、間引きを前記基本符号の少なくとも１つに実施することもできる。
【００４５】
この間引きは、変数に適用されてもよく、および／または、符号のブランチに適用されてもよい。
【００４６】
本発明の有利な態様によれば、トレリスの少なくとも１つは、巡回的トレリスである。
【００４７】
また、トレリスの少なくとも１つは、入力状態および出力状態が所定の値にセットされたトレリスであってもよい。
【００４８】
本発明の第１の実施形態によれば、前記局所的符号の少なくとも１つは、６つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（６、４、２）であり、
６は、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
４は、前記局所的符号のサイズであり、
２は、前記基本符号からの最小距離である。
【００４９】
この場合、前記基本符号は、有利には、前記符号（６、４、２）の３つのセクションによって構成される。
【００５０】
本発明の第２の実施形態によれば、前記局所的符号の少なくとも１つは、４つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（４、３、２）であり、
４は、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
３は、前記局所的符号のサイズであり、
２は、前記基本符号からの最小距離である。
【００５１】
この場合、前記基本符号は、有利には、前記符号（４、３、２）の２つのセクションによって構成される。
【００５２】
本発明の第３の実施形態によれば、前記局所的符号の少なくとも１つは、６つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（６、５、２）であり、
６は、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
５は、前記局所的符号のサイズであり、
２は、前記基本符号からの最小距離である。
【００５３】
この場合、前記基本符号は、有利には、前記符号（６、５、２）の３つのセクションによって構成される。
【００５４】
本発明の第４の実施形態によれば、前記局所的符号の少なくとも１つは、８つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する４状態符号（８、７、２）であり、
８は、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
７は、前記局所的符号のサイズであり、
２は、前記基本符号からの最小距離である。
【００５５】
本発明の第５の実施形態によれば、前記局所的符号の少なくとも１つは、８つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（８、７、２）であり、
８は、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
７は、前記局所的符号のサイズであり、
２は、前記基本符号からの最小距離である。
【００５６】
最後の２つの場合においては、前記基本符号は、有利には、前記符号（８、７、２）の８つのセクションによって構成される。
【００５７】
本発明は、また、上述した符号化方法によるデータを復号化するための方法に関する。
【００５８】
この種の復号化方法は、少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を符号化と対称的に提供し、前記局所的符号は、検出符号ではあるが、所定の符号化文字における誤り訂正符号ではなく、前記局所的符号は、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスは、基本符号を定義する。
【００５９】
本発明はまた、上述した符号化方法を実行する符号化されたデータを送信するための装置、符号化と対称的に動作する復号化手段を実行する、この符号化方法によって符号化されたデータを受信するための装置、および、上述した方法に基づいた符号化手段および／または復号化手段を含む符号化データ記憶装置に関する。
【００６０】
本発明は、また、上述した符号化方法および／または復号化方法を実行するコンピュータプログラムに関する。
【００６１】
本発明のその他の特徴および利点が、限定するものではない単なる例として提供される以下の本発明の好ましい実施形態の説明および添付の図面からより明確となる。
【発明を実施するための最良の形態】
【００６２】
７．発明の好ましい実施形態の説明
７．１ 序論
上述したように、本発明は、きわめて簡単な局所的符号を実施する誤り訂正器符号への新しいアプローチに頼るものであり、それらの局所的符号は、ただ単に誤り検出器符号であり、従来技術による符号よりも簡単かつ効率的な最終的な全体符号を提供するように組み合わせられる。
【００６３】
したがって、本発明の符号は、少ない数の状態（２つの状態および４つの状態）を備えたバイナリトレリスを使用することによる複雑さの減少によって区別されてもよい。これらの２つの状態（および、４つの状態）のトレリスによって組み立てられた符号の複雑さは、すでに標準的なものである１６個の状態を有するターボ符号および同等のＬＤＰＣ符号と比較すれば、１／８（および、１／４）ほどに減少することを推定することができる。
【００６４】
これらのトレリスの小さな複雑さにもかかわらず、得られる符号は、最良のターボ符号および現在使用されているＬＤＰＣ符号の複雑さ、誤り訂正能力、および、「ｅｒｒｏｒ−ｆｌｏｏｒ」の点において、より良好な妥協点を提供する。なぜなら、これらの新しい符号は、誤り率の点において少なくとも同じように効率的に実行し、かつ、実際に使用するのが同じように容易な「ｅｒｒｏｒ−ｆｌｏｏｒ」を有するからである。
【００６５】
以下の表は、以下に詳細に説明されるいくつかの達成される符号の性能特性および複雑さをまとめたものである。
【００６６】
局所的符号のパラメータは、（ラベルビットの数、寸法、この符号によって組み立てられた基本符号の最大ボーダーラインｄmin）である。
【００６７】
【表１】
【００６８】
また、バイナリ消失通信路（ＢＥＣ）に対する所与の消失訂正利得は、ガウス通信路において無視できない利得をもたらすことに留意されたい。
【００６９】
７．２ 本発明の主たる技術的要素
本発明による符号の組み立ては、トレリスセクションを「局所的符号」として知られる小さな符号Ｃjのきわめて少ない数の状態と連結することによって得られるトレリスによって記述される長さｍを有する「基本符号」に頼るものである。記述における曖昧さを回避するために、組み立てられた符号は、「全体符号」と呼ばれる。
【００７０】
このために、符号は、以下のようにして組み立てられる：
局所的符号の状態ビットが、互いに接続され、
変数の少なくとも大部分のビット（冗長ビットだけでなく、情報ビットも含む）が、反復され、そして、変数（新しくない）のそれらの反復されたビットの順序を変更する置換によって基本符号に接続される。
【００７１】
本発明の有利なアプローチは、以下の基準を満足するように、特定の局所的符号セクションを選択することである：
有意性２のｍビットの長さを有する基本符号語（大きなトレリス）の数は、ｍ／２よりも小さいかまたはｍ／２に等しい。
有意性３のｍビットの長さを有する基本符号語の数は、非ゼロである。
【００７２】
このアプローチは、以下に説明される６つの局所的符号に適用された。
【００７３】
これらの高性能特性の説明が、以下でなされる。きわめて小さい距離（それは、直観でわかるものではない）の誤り訂正符号を得ることが必要であり、最小値は、２である。この場合、符号は、訂正器符号ですらなく、１つの誤りだけを検出してもよい。
【００７４】
したがって、それらは、伝送雑音の存在下において最小可能閾値である情報抽出閾値を有する。有意性３の多数の語は、最小の大きな距離を有する「全体」訂正符号を得るのに使用されてもよい。したがって、誤り訂正符号が得られ、それは、シャノンの限界容量を達成してもよく、したがって、最小距離は、符号の長さに応じて線形に増加してもよい。
【００７５】
したがって、なされなければならないことは、ただ単に検出器符号である小さな符号を連結することである。
【００７６】
それぞれの局所的符号Ｃjは、小さな数のラベルビットｄＣjを有する：
【数５】
これらのｍビットの順序は、ｍビットの置換によって変更され、そして、結合され、次数ｄｘiの変数ｘi（ｉ＝０、１、ｎ−１）のビットを構成する。
【００７７】
したがって、基本的な技術的要素は、図４に示されるように接続された小さな局所的符号Ｃjによって構成されるトレリスの使用である。
【００７８】
局所的符号Ｃj４１のこの系列は、トレリスによって説明される基本符号４２を構成し、トレリスがループを形成すれば、そのトレリスは巡回的である、または《ｔａｉｌ−ｂｉｔｉｎｇ》であると言われる。
【００７９】
変数ｘi（ｉ＝０、１、ｎ−１）とも呼ばれるｎ個の符号ビット４３は、典型的には、図４に示される符号のＴａｎｎｅｒグラフの左側に配置される。これらの変数は、互いに異なってもよい次数ｄｘiによって反復され、これらの次数ｄｘiのベクトルは、変数の反復プロフィールと呼ばれる。
【００８０】
置換４４は、ターボ符号、ＬＤＰＣ符号、および、ＲＡ符号の場合と同様に、これらのビットの順序を変更する。図４の置換の右側には、いくつかのラベルシンボルｄＣjおよび入力状態ビットｖiおよび出力状態ビットｖi+1を有する局所的符号Ｃjによって構成された基本符号４２のトレリスが、配置される。
【００８１】
図５は、本発明のこの種の全体符号の例を表現するＴａｎｎｅｒのグラフであり、４つのラベルビットを備えた４つの局所的符号トレリスセクションに分解された長さｍ＝１６ビットの基本符号とともに一定の長さｎ＝８ビットの２次変数を有する。
【００８２】
局所的符号Ｃｉ間の１つ以上の「状態」ビットが、構成によってゼロに「セット」されていれば、「ｔａｉｌ−ｂｉｔｉｎｇ」トレリスは、典型的な非巡回的トレリスに関連づけられてもよい。ゼロ状態トレリス終結のこの技術は、復号化処理を簡素化するのに使用されてもよい周知の技術である。
【００８３】
図６からわかるように、トレリスをいくつかのサブトレリス６１および６２に分割することが可能である。これは、サブトレリスのそれぞれに対する復号化計算を並列処理するのを可能にし（これらの並列計算が統合される前に）、かつ、サブトレリスのそれぞれにおける相当な数のセクションを取り込むときに性能の大きな損失を伴うことなくなされる。
【００８４】
したがって、図６は、基本符号が２つのサブトレリス６１および６２に分割された「全体」符号を説明し、上部のサブトレリス（局所的符号Ｃ０〜Ｃj）６１は、終結状態６１１および６１２が０に等しい典型的なトレリスとして知られているトレリスであり、また、下部のサブトレリス（局所的符号Ｃj＋１〜Ｃｎｃ−１）６２は、終結条件が開始状態が到達状態に等しくなければならないということである「ｔａｉｌ−ｂｉｔｉｎｇ」トレリスである。
【００８５】
重要な組み立て要素は、高性能な置換、すなわち、最小の大きな距離を有する符号を与える置換を達成することである。これらの置換は、小さな局所的符号の「パターン」（または、いくつかのビットからなる部分集合、それらは、符号語内におけるそれらの位置に対して不変である）の特別な特性を使用する。
【００８６】
Ｔａｎｎｅｒのグラフのこの特定の構造をきわめて小さな状態数（バイナリシンボルの場合には２または４）を備えた小さな局所的符号のトレリスと組み合わせること、および、対応するそれらの置換は、全ての最良の敵対する符号よりも効率的な妥協点｛複雑さ、誤り訂正性能｝を提供する誤り訂正符号を提供する。
【００８７】
８．局所的符号の例
８．１ ２状態局所的符号（６、４、２）のトレリスセクション
図７に説明されるセクションは、ビットによってラベルを付されたブランチを通って開始状態の１つから到達状態の１つまで延びる一組のパスによって、パラメータの局所的符号からなる一組の符号語を表現する。
【００８８】
したがって、局所的符号（６、４、２）７１は、３つのトレリスセクション７２、７３、および、７４に分解され、それらのそれぞれは、２つのラベルビットを備える。
【００８９】
図８Ａ〜図８Ｃは、それぞれ、典型的な表現によってこれらの３つのセクションを示す。
【００９０】
トレリスセクションの概略的な表現は、入力状態０から出力状態０への遷移はラベルビットが００または１１に等しい場合に達成できることを意味する。これは、２重ラベルブランチであると言われる。
【００９１】
同じブランチのラベル（複数であろうとなかろうと）は、同じ入力状態に対応する同じ線上の括弧の中に配置され、連続する括弧は、同じ順序で、連続する到達状態に対応する。
【００９２】
図８Ｂのトレリスセクションをさらに説明すると、入力状態０から出力状態０への遷移は、ラベルビットが００または１１に等しい場合になすことができ、そして、入力状態０から出力状態１への遷移は、ラベルビットが０１または１０に等しい場合になすことができる。
【００９３】
２つの状態しか達成されないので、トレリスセクションは、きわめて小さな複雑さで軟判定反復器が復号化するのを可能にする。
【００９４】
さらに、有意性の遷移の代数的性質は、単独で考えれば、この符号はどのような誤りも訂正できるのではなく誤りをただ単に検出できるようなものである。しかしながら、トレリス内において集合的に組み立てられると、この符号は、それらのハミング重みパターンに適合された置換を備えた優れた符号となる。
【００９５】
図９は、２状態トレリス符号セクション（６、４、２）からなるトレリスによって組み立てられたこの基本符号の情報伝達曲線を示す。
【００９６】
８．２ ２状態局所的符号（４、３、２）のトレリスセクション
図１０は、上述したものと同じ原理に基づいて、局所的符号（４、３、２）を２つのトレリスセクションに分解することを示し、それらのトレリスセクションのそれぞれは、２つのラベルビットを備え、そして、図１１Ａおよび図１１Ｂは、２つの対応する状態を備えた局所的符号（４、３、２）からなるトレリスの２つのセクションを示す。
【００９７】
図１２からわかるように、情報伝達曲線は、原点において４５．３％の傾きを有する直線に対して接線方向にあり、これは、レート１／２符号に対する５０％の可能最大理論値に対して全体符号の消失を４５．３％だけ訂正する能力があることを意味する。
【００９８】
８．３ ２状態局所的符号（６、５、２）のトレリスセクション
図１３は、上述したものと同じ原理に基づいて、局所的符号（６、３、２）を２つのトレリスセクションに分解することを示し、それらのトレリスセクションのそれぞれは、３つのラベルビットを備え、そして、図１４Ａおよび図１４Ｂは、２つの対応する状態を備えた局所的符号（６、３、２）からなるトレリスの２つのセクションを示す。
【００９９】
この場合にも、図１５から、以下の情報伝達曲線は、原点において３０％の傾きを有する直線に対して接線方向にあることがわかり、これは、レート２／３符号に対する３３．３３％の可能最大理論値に対して全体符号の消失を３０％だけ訂正する能力があることを意味する。
【０１００】
８．４ ４状態局所的符号（８、７、２）のトレリスセクション
図１６は、８つのセクションに「爆発的に増加した」トレリスを説明し、それらのそれぞれは、１つのラベルビットを有する。ビット（ｂ0、ｂ1、ｂ2、ｂ3）およびビット（ｂ4、ｂ5、ｂ6、ｂ7）は、２つのセクションにグループとしてまとめられてもよく、それらのそれぞれは、図１７、図１８Ａ、および、図１８Ｂからわかるように、４つの入力状態および４つの出力状態を有する。
【０１０１】
図１９の情報伝達曲線は、原点において２１．５％の傾きを有する直線に対して接線方向にあり、これは、レート３／４（＝０．７５）符号に対する２５％の可能最大理論値に対して全体符号の消失を２１．５％だけ訂正する能力があることを意味する。これは、２状態局所的符号（８、７、２）の２２．１５％よりも小さいが、この種類の符号は、漸近的に良好（ＡＧ）である。
【０１０２】
８．５ ２状態局所的符号（８、７、２）のトレリスセクション
図２０は、上述したものと同じ原理に基づいて、局所的符号（８、７、２）を２つのトレリスセクションに分解することを示し、それらのトレリスセクションのそれぞれは、４つのラベルビットを備え、そして、図２１Ａおよび図２１Ｂは、２つの対応する状態を備えた局所的符号（６、３、２）からなるトレリスの２つのセクションを示す。
【０１０３】
図２２の情報伝達曲線は、原点において２２．１５％の傾きを有する直線に対して接線方向にあり、これは、レート３／４（＝０．７５）符号に対する２５％の可能最大理論値に対して全体符号の消失を２２．１５％だけ訂正する能力があることを意味する。
【０１０４】
８．６ 別の局所的符号（ｎ，ｋ，２）を構成するためのトレリスセクションの組み合わせ
パラメータ（６、４、２）および（４、３、２）を有する符号からなるトレリスを構成する２状態トレリスセクションをそれぞれ説明するこれまでの節に説明されるように、セクション１は、両方の符号において同一であり、また、符号（４、３、２）のセクション３と同一であり、同様に、セクション２は、両方の符号において同一であることがわかる。
【０１０５】
したがって、これまでに説明した様々な符号を構成する全てのセクションとそれらのセクション上においてラベルビットが間引かれまたは重複する可能性とを、全体符号の符号レートに関して多種多様な選択を可能にするパラメータ（ｎ，ｋ，２）を有する新しい局所的符号を組み立てるのに使用することができる。
【０１０６】
８．７ Ｚ４上における４状態符号（４、３、２）の例
Ｚ４は、加算モジュロ４を備えた一組の整数｛０、１、２、３｝である。符号のこの例は、その他の文字に容易に一般化することができる。なぜなら、それは、「Ｚ４への加算」法則を、考察される新しい文字への加算に関する法則に置き換えることを満足するからである。
【０１０７】
組み立てる方法は、文字、この場合には、Ｚ４上における反復符号によって開始することからなる：
Ｚ４への反復符号＝｛００、１１、２２、３３｝
【０１０８】
図２３は、この符号を２つのセクションに分解することを示し、そして、図２４Ａおよび図２４Ｂは、２つの対応するセクションを示す。
【０１０９】
複数のブランチのラベルは、同じ長さの語（横方向クラスを表現する「コセットリーダ」または語）を加算することによって、この反復符号から得られる。例えば、複数のブランチ（または、マルチブランチ）０１は、｛０１、１２、２３、３０｝をラベルとして有する。
【０１１０】
当然ながら、同じ一般化が、Ｚ８、Ｚ１６、．．．に適用されてもよい。
【０１１１】
９．参考文献
［１］Ｇａｌｌａｇｅｒ，《Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ ｃｏｄｅｓ》，Ｐｈ．Ｄ．Ｔｈｅｓｉｓ，ＭＩＴ，Ｊｕｌｙ １９６３．
［２］Ｒ．Ｍ．Ｔａｎｎｅｒ，《Ａ ｒｅｃｕｒｓｉｖｅ ａｐｐｒｏａｃｈ ｔｏ ｌｏｗ ｃｏｍｐｌｅｘｉｔｙ ｃｏｄｅｓ》，ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ｖｏｌ ＩＴ−２７，ｐｐ．５３３−５４７，Ｓｅｐｔ １９８１．
［３］Ｃ．Ｂｅｒｒｏｕ，Ａ．Ｇｌａｖｉｅｕｘ ａｎｄ Ｐ．Ｔｈｉｔｉｍａｊｓｈｉｍａ，《Ｎｅａｒ Ｓｈａｎｎｏｎ ｌｉｍｉｔ ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｉｎｇ ａｎｄ ｄｅｃｏｄｉｎｇ：Ｔｕｒｂｏ ｃｏｄｅｓ》，ｐｐ．１０６４−１０７０，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｃｏｎｆｅｒｅｎｃｅ（ＩＣＣ），Ｍａｙ １９９３，Ｇｅｎｅｖａ．
［４］Ｄ．Ｄｉｖｓａｌａｒ ａｎｄ Ｒ．Ｊ．ＭｃＥｌｉｅｃｅ，《Ｃｏｄｉｎｇ ｔｈｅｏｒｅｍｓ ｆｏｒ ｔｕｒｂｏ−ｌｉｋｅ ｃｏｄｅｓ》，Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ａｌｌｅｒｔｏｎ Ｃｏｎｆｅｒｅｎｃｅ（Ａｌｌｅｒｔｏｎ，Ｉｌｌｉｎｏｉｓ，ＵＳＡ），ｐｐ．２０１−２１０，Ｓｅｐｔ．１９９８．
［５］Ｔ．Ｒｉｃｈａｒｄｓｏｎ ａｎｄ Ｒ．Ｕｒｂａｎｋｅ，「Ｔｈｅ Ｃａｐａｃｉｔｙ ｏｆ Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ ｕｎｄｅｒ Ｍｅｓｓａｇｅ−Ｐａｓｓｉｎｇ Ｄｅｃｏｄｉｎｇ，」ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ｖｏｌ．４７，ｐｐ．５９９−６８１，Ｆｅｂｒｕａｒｙ ２００１．
［６］Ｔ．Ｒｉｃｈａｒｄｓｏｎ，Ａ．Ｓｈｏｋｒｏｌｌａｈｉ ａｎｄ Ｒ．Ｕｒｂａｎｋｅ，「Ｄｅｓｉｇｎ ｏｆ Ｃａｐａｃｉｔｙ Ａｐｐｒｏａｃｈｉｎｇ Ｉｒｒｅｇｕｌａｒ Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ Ｃｏｄｅｓ，」ＩＥＥＥ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｈｅｏｒｙ，ｖｏｌ．４７，ｐｐ．６１９−６３７，Ｆｅｂｒｕａｒｙ ２００１．
【図面の簡単な説明】
【０１１２】
【図１】序文において説明され、ターボ符号の原理の概略図を提供する。
【図２】同様に、序文において説明され、ＴａｎｎｅｒグラフによるＬＤＰＣ符号（４、２）の表現を提供する。
【図３】同様に、序文において説明され、ＴａｎｎｅｒグラフによるＴａｎｎｅｒ符号の概略図を提供する。
【図４】本発明による誤り訂正符号の原理を説明するＴａｎｎｅｒグラフである。
【図５】４つのラベルビットを備えた４つのセクションの局所的トレリス符号に分解された長さｍ＝１６ビットの基本符号とともに一定の長さｎ＝８ビットの２次変数を有する、本発明による典型的な符号のＴａｎｎｅｒグラフである。
【図６】本発明による別の典型的な符号のＴａｎｎｅｒグラフであり、基本符号のトレリスは、２つのサブトレリスに分割されており、一方は、ゼロ状態終結を備え、他方は、「ｔａｉｌ−ｂｉｔｉｎｇ」を備える。
【図７】本発明による全体符号において使用することのできる第１の局所的符号（６、４、２）を３つのトレリスセクションに分解することを示す図であり、それぞれのトレリスセクションは、２つのラベルビットを備える。
【図８Ａ】図７の局所的符号（６、４、２）のセクションを示す図である。
【図８Ｂ】図７の局所的符号（６、４、２）のセクションを示す図である。
【図８Ｃ】図７の局所的符号（６、４、２）のセクションを示す図である。
【図９】２状態トレリス符号セクション（６、４、２）からなるトレリスによって組み立てられた基本符号に関する情報伝達曲線である。
【図１０】本発明による全体符号において使用することのできる第２の局所的符号（４、３、２）を２つのトレリスセクションに分解することを示す図であり、それぞれのトレリスセクションは、２つのラベルビットを備える。
【図１１Ａ】図１０の局所的符号（４、３、２）のセクションを示す図である。
【図１１Ｂ】図１０の局所的符号（４、３、２）のセクションを示す図である。
【図１２】２状態トレリス符号セクション（４、３、２）からなるトレリスによって組み立てられた基本符号に関する情報伝達曲線である。
【図１３】本発明による全体符号において使用することのできる第３の局所的符号（６、５、２）を２つのトレリスセクションに分解することを示す図であり、それぞれのトレリスセクションは、３つのラベルビットを備える。
【図１４Ａ】図１３の局所的符号（６、５、２）のセクションを示す図である。
【図１４Ｂ】図１３の局所的符号（６、５、２）のセクションを示す図である。
【図１５】２状態トレリス符号セクション（６、５、２）からなるトレリスによって組み立てられた基本符号に関する情報伝達曲線である。
【図１６】本発明による全体符号において使用することのできる第４の局所的４状態符号（８、７、２）の《爆発的に増加した》非セクション化トレリスを示す図である。
【図１７】本発明による全体符号において使用することのできる第５の局所的符号（８、７、２）を２つのトレリスセクションに分解することを示す図であり、それぞれのトレリスセクションは、４つのラベルビットを備える。
【図１８Ａ】図１７の局所的符号（８、７、２）のセクションを示す図である。
【図１８Ｂ】図１７の局所的符号（８、７、２）のセクションを示す図である。
【図１９】４状態トレリス符号セクション（８、７、２）からなるトレリスによって組み立てられた基本符号に関する情報伝達曲線である。
【図２０】局所的符号（８、７、２）を２つのトレリスセクションに別の方法で分解することを示す図であり、それぞれのトレリスセクションは、４つのラベルビットを備える。
【図２１Ａ】図２０の局所的符号のセクションを示す図である。
【図２１Ｂ】図２０の局所的符号のセクションを示す図である。
【図２２】２状態トレリス符号セクション（８、７、２）からなるトレリスによって組み立てられた基本符号に関する情報伝達曲線である。
【図２３】第６の局所的符号（４、３、２）を分解することを示す図であり、Ｚ４上において４つの状態を備える。
【図２４Ａ】図２３のトレリスセクションを示す図である。
【図２４Ｂ】図２３のトレリスセクションを示す図である。
【特許請求の範囲】
【請求項１】
冗長データをソースデータに対応させ、かつ、少なくとも１つのラベル語と少なくともいくつかの前記ラベル語に適用される置換とに基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する符号化方法であって、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、前記局所的符号が、それらの状態語によって互いに接続されて少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが基本符号を定義する、
ことを特徴とする符号化方法。
【請求項２】
前記置換が、前記ラベル語には適用されるが、前記状態語には適用されないことを特徴とする請求項１に記載の符号化方法。
【請求項３】
前記局所的符号が、２状態トレリスかまたは４状態トレリスによって表現されるバイナリ符号であることを特徴とする請求項１および２の一項に記載の符号化方法。
【請求項４】
前記局所的符号が、２ｎ個の要素を備えた符号化文字に関して定義され、かつ、２n状態，２n+1状態、または、２n+2状態を備えたトレリスによって表現されることを特徴とする請求項１および２の一項に記載の符号化方法。
【請求項５】
前記基本符号のそれぞれが、ｍ個のシンボルからなる長さを備えた符号語を提供し、それぞれが、符号化文字の少なくとも１つのビットに対応し、符号化文字が、
有意性２を備えた符号語の数が、ｍ／２よりも小さいかまたはｍ／２に等しく、
有意性３を備えた符号語の数が、０でない、
ように定義され、
符号語の有意性が、それが含む０と異なるシンボルの数である、
ことを特徴とする請求項１〜４の一項に記載の符号化方法。
【請求項６】
前記基本符号語の少なくとも１つが、少なくとも２つの符号セクションによって構成されることを特徴とする請求項１〜５の一項に記載の符号化方法。
【請求項７】
間引きが、前記基本符号の少なくとも１つに実施されることを特徴とする請求項１〜６の一項に記載の符号化方法。
【請求項８】
トレリスの少なくとも１つが、巡回的トレリスであることを特徴とする請求項１〜７の一項に記載の符号化方法。
【請求項９】
トレリスの少なくとも１つが、入力状態および出力状態が所定の値にセットされたトレリスであることを特徴とする請求項１〜８の一項に記載の符号化方法。
【請求項１０】
前記局所的符号の少なくとも１つが、６つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（６、４、２）であり、
６が、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
４が、前記局所的符号のサイズであり、
２が、前記基本符号からの最小距離である、
ことを特徴とする請求項１〜９の一項に記載の符号化方法。
【請求項１１】
前記基本符号が、前記符号（６、４、２）の３つのセクションによって構成されることを特徴とする請求項１０に記載の符号化方法。
【請求項１２】
前記局所的符号の少なくとも１つが、４つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（４、３、２）であり、
４が、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
３が、前記局所的符号のサイズであり、
２が、前記基本符号からの最小距離である、
ことを特徴とする請求項１〜９の一項に記載の符号化方法。
【請求項１３】
前記基本符号が、前記符号（４、３、２）の２つのセクションによって構成されることを特徴とする請求項１２に記載の符号化方法。
【請求項１４】
前記局所的符号の少なくとも１つが、６つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（６、５、２）であり、
６が、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
５が、前記局所的符号のサイズであり、
２が、前記基本符号からの最小距離である、
ことを特徴とする請求項１〜９の一項に記載の符号化方法。
【請求項１５】
前記基本符号が、前記符号（６、５、２）の３つのセクションによって構成されることを特徴とする請求項１４に記載の符号化方法。
【請求項１６】
前記局所的符号の少なくとも１つが、８つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する４状態符号（８、７、２）であり、
８が、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
７が、前記局所的符号のサイズであり、
２が、前記基本符号からの最小距離である、
ことを特徴とする請求項１〜９の一項に記載の符号化方法。
【請求項１７】
前記局所的符号の少なくとも１つが、８つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（８、７、２）であり、
８が、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
７が、前記局所的符号のサイズであり、
２が、前記基本符号からの最小距離である、
ことを特徴とする請求項１〜９の一項に記載の符号化方法。
【請求項１８】
前記基本符号が、前記符号（８、７、２）の８つのセクションによって構成されることを特徴とする請求項１６および１７の一項に記載の符号化方法。
【請求項１９】
請求項１〜１８の一項に記載の符号化方法によって符号化されたデータを復号化するための方法であって、
少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を符号化と対称的に提供し、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、前記局所的符号が、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが、基本符号を定義する、
ことを特徴とする復号化するための方法。
【請求項２０】
符号化されたデータを送信するための装置であって、
少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換の手段に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する、請求項１〜１８の一項に記載の符号化方法に基づいた手段を備え、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、
前記局所的符号が、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが、基本符号を定義する、
ことを特徴とする装置。
【請求項２１】
請求項１〜１８の一項に記載の符号化方法によって符号化されたデータを受信するための装置であって、
少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換の手段に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号によって符号化と対称的に動作する復号化手段を提供し、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、
前記局所的符号が、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが、基本符号を定義する、
ことを特徴とする装置。
【請求項２２】
符号化されたデータを記憶するための装置であって、
少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換の手段に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する請求項１〜１９までのいずれかに記載の符号化方法および／または復号化方法の手段を備え、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、前記局所的符号が、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが、基本符号を定義する、
ことを特徴とする装置。
【請求項２３】
コンピュータプログラムプロダクトであって、
少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換の手段に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する、請求項１〜１９までのいずれかに記載の符号化方法および／または復号化方法のためのプログラム命令を備え、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、前記局所的符号が、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが、基本符号を定義する、
ことを特徴とするコンピュータプログラムプロダクト。
【請求項１】
冗長データをソースデータに対応させ、かつ、少なくとも１つのラベル語と少なくともいくつかの前記ラベル語に適用される置換とに基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する符号化方法であって、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、前記局所的符号が、それらの状態語によって互いに接続されて少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが基本符号を定義する、
ことを特徴とする符号化方法。
【請求項２】
前記置換が、前記ラベル語には適用されるが、前記状態語には適用されないことを特徴とする請求項１に記載の符号化方法。
【請求項３】
前記局所的符号が、２状態トレリスかまたは４状態トレリスによって表現されるバイナリ符号であることを特徴とする請求項１および２の一項に記載の符号化方法。
【請求項４】
前記局所的符号が、２ｎ個の要素を備えた符号化文字に関して定義され、かつ、２n状態，２n+1状態、または、２n+2状態を備えたトレリスによって表現されることを特徴とする請求項１および２の一項に記載の符号化方法。
【請求項５】
前記基本符号のそれぞれが、ｍ個のシンボルからなる長さを備えた符号語を提供し、それぞれが、符号化文字の少なくとも１つのビットに対応し、符号化文字が、
有意性２を備えた符号語の数が、ｍ／２よりも小さいかまたはｍ／２に等しく、
有意性３を備えた符号語の数が、０でない、
ように定義され、
符号語の有意性が、それが含む０と異なるシンボルの数である、
ことを特徴とする請求項１〜４の一項に記載の符号化方法。
【請求項６】
前記基本符号語の少なくとも１つが、少なくとも２つの符号セクションによって構成されることを特徴とする請求項１〜５の一項に記載の符号化方法。
【請求項７】
間引きが、前記基本符号の少なくとも１つに実施されることを特徴とする請求項１〜６の一項に記載の符号化方法。
【請求項８】
トレリスの少なくとも１つが、巡回的トレリスであることを特徴とする請求項１〜７の一項に記載の符号化方法。
【請求項９】
トレリスの少なくとも１つが、入力状態および出力状態が所定の値にセットされたトレリスであることを特徴とする請求項１〜８の一項に記載の符号化方法。
【請求項１０】
前記局所的符号の少なくとも１つが、６つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（６、４、２）であり、
６が、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
４が、前記局所的符号のサイズであり、
２が、前記基本符号からの最小距離である、
ことを特徴とする請求項１〜９の一項に記載の符号化方法。
【請求項１１】
前記基本符号が、前記符号（６、４、２）の３つのセクションによって構成されることを特徴とする請求項１０に記載の符号化方法。
【請求項１２】
前記局所的符号の少なくとも１つが、４つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（４、３、２）であり、
４が、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
３が、前記局所的符号のサイズであり、
２が、前記基本符号からの最小距離である、
ことを特徴とする請求項１〜９の一項に記載の符号化方法。
【請求項１３】
前記基本符号が、前記符号（４、３、２）の２つのセクションによって構成されることを特徴とする請求項１２に記載の符号化方法。
【請求項１４】
前記局所的符号の少なくとも１つが、６つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（６、５、２）であり、
６が、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
５が、前記局所的符号のサイズであり、
２が、前記基本符号からの最小距離である、
ことを特徴とする請求項１〜９の一項に記載の符号化方法。
【請求項１５】
前記基本符号が、前記符号（６、５、２）の３つのセクションによって構成されることを特徴とする請求項１４に記載の符号化方法。
【請求項１６】
前記局所的符号の少なくとも１つが、８つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する４状態符号（８、７、２）であり、
８が、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
７が、前記局所的符号のサイズであり、
２が、前記基本符号からの最小距離である、
ことを特徴とする請求項１〜９の一項に記載の符号化方法。
【請求項１７】
前記局所的符号の少なくとも１つが、８つのラベルビットに応じて出力状態ビットを入力状態ビットに対応させることを確立する２状態符号（８、７、２）であり、
８が、前記局所的符号の長さであり、あるいは、前記局所的符号のラベルビットの数であり、
７が、前記局所的符号のサイズであり、
２が、前記基本符号からの最小距離である、
ことを特徴とする請求項１〜９の一項に記載の符号化方法。
【請求項１８】
前記基本符号が、前記符号（８、７、２）の８つのセクションによって構成されることを特徴とする請求項１６および１７の一項に記載の符号化方法。
【請求項１９】
請求項１〜１８の一項に記載の符号化方法によって符号化されたデータを復号化するための方法であって、
少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を符号化と対称的に提供し、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、前記局所的符号が、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが、基本符号を定義する、
ことを特徴とする復号化するための方法。
【請求項２０】
符号化されたデータを送信するための装置であって、
少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換の手段に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する、請求項１〜１８の一項に記載の符号化方法に基づいた手段を備え、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、
前記局所的符号が、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが、基本符号を定義する、
ことを特徴とする装置。
【請求項２１】
請求項１〜１８の一項に記載の符号化方法によって符号化されたデータを受信するための装置であって、
少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換の手段に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号によって符号化と対称的に動作する復号化手段を提供し、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、
前記局所的符号が、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが、基本符号を定義する、
ことを特徴とする装置。
【請求項２２】
符号化されたデータを記憶するための装置であって、
少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換の手段に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する請求項１〜１９までのいずれかに記載の符号化方法および／または復号化方法の手段を備え、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、前記局所的符号が、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが、基本符号を定義する、
ことを特徴とする装置。
【請求項２３】
コンピュータプログラムプロダクトであって、
少なくとも１つのラベル語および少なくともいくつかの前記語に適用される置換の手段に基づいて、少なくとも１つの出力状態語を少なくとも１つの入力状態語に対応させることを確立する複数の局所的符号を提供する、請求項１〜１９までのいずれかに記載の符号化方法および／または復号化方法のためのプログラム命令を備え、
前記局所的符号が、検出符号ではあるが、所定の符号化文字内における誤り訂正符号ではなく、前記局所的符号が、それらの状態語によって互いに接続され、それによって、少なくとも１つの符号化トレリスを構成し、それぞれのトレリスが、基本符号を定義する、
ことを特徴とするコンピュータプログラムプロダクト。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８Ａ】
【図１８Ｂ】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４Ａ】
【図２４Ｂ】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８Ａ】
【図１８Ｂ】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４Ａ】
【図２４Ｂ】
【公表番号】特表２００８−５０１２６６（Ｐ２００８−５０１２６６Ａ）
【公表日】平成２０年１月１７日（２００８．１．１７）
【国際特許分類】
【出願番号】特願２００７−５１３９９５（Ｐ２００７−５１３９９５）
【出願日】平成１７年５月１７日（２００５．５．１７）
【国際出願番号】ＰＣＴ／ＦＲ２００５／００１２３８
【国際公開番号】ＷＯ２００６／０００６６６
【国際公開日】平成１８年１月５日（２００６．１．５）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
【公表日】平成２０年１月１７日（２００８．１．１７）
【国際特許分類】
【出願日】平成１７年５月１７日（２００５．５．１７）
【国際出願番号】ＰＣＴ／ＦＲ２００５／００１２３８
【国際公開番号】ＷＯ２００６／０００６６６
【国際公開日】平成１８年１月５日（２００６．１．５）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【Ｆターム（参考）】
[ Back to top ]