少なくとも２つの並列編集方法及び改良された置換方法を備えたコーディング方法及び装置、並びに対応するディコーディング方法及び装置
【課題】 より優れた置換特性を有する、並列連結のコーディング方法（またはターボコード）を提供する。
【解決手段】 本発明は、ディジタルのソースデータをコーディングする方法及び装置に関する。本発明は、それぞれがソースデータ（１５）のセット全体を含む少なくとも２つの基本的なコーディングステップ（１１，１２）を使用し、基本的なコーディングステップ（１１，２３）の間のソースデータの組込み順序を変更する置換ステップ（１３）を備えている。本発明は、ソースデータ（１５）が、それぞれが２以上のｎのバイナリのソース素子を含むソースのコードワードの中で編成され、置換ステップ（１３）が、少なくともいくつかのソースのコードワードの内容を可逆的に変更して、変更されたコードワードを出力するステップ（１３２）と、変更された又はソースのコードワードの順序を置換するステップ（１３１）とを含む。
【解決手段】 本発明は、ディジタルのソースデータをコーディングする方法及び装置に関する。本発明は、それぞれがソースデータ（１５）のセット全体を含む少なくとも２つの基本的なコーディングステップ（１１，１２）を使用し、基本的なコーディングステップ（１１，２３）の間のソースデータの組込み順序を変更する置換ステップ（１３）を備えている。本発明は、ソースデータ（１５）が、それぞれが２以上のｎのバイナリのソース素子を含むソースのコードワードの中で編成され、置換ステップ（１３）が、少なくともいくつかのソースのコードワードの内容を可逆的に変更して、変更されたコードワードを出力するステップ（１３２）と、変更された又はソースのコードワードの順序を置換するステップ（１３１）とを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、特に回路上に過渡現象が存在する中で、送信又は放送される１つ以上のソースデータの順序に属するディジタルデータをコーディングする分野、及びこのように送信されたコード化されたデータをディコーディングする分野である。より詳細には、本発明は、特に「ターボコード（turbo codes）」（登録商標）として周知のコーディング方法の改良に関し、特に、これにより実行される置換動作の改良に関する。
【背景技術】
【０００２】
この種のコーディングの一般的な原理は、特に、特許文献１と、C. Berrou 及び A. Glavieuxによる「Near Optimum Error Correcting Coding and Decoding: Turbo Codes」という題名の文献（IEEE Transactions on Communications、第４４巻、Ｎｏ．１０、ページ１２６１−１２７０、１９９６年１０月）との中で紹介されている。
【０００３】
この技術によれば、少なくとも２つの基本的なエンコーダの使用に基づく、「並列連結（parallel concatenation）」によるコーディングの実現が提案されている。ディコーディングする場合、これにより、２つの別個のエンコーダからの２つの冗長的な符号を持つことが可能になる。２つの基本的なエンコーダの間で、これらの基本的なエンコーダの各々が同じディジタルのソースデータを供給されるが、順序が変化して受け取られるように、置換手段が実行される。
【０００４】
ブロックコーディング（block coding）（製品コード）についてのこの種の技術の改良は、特許文献２と、O. Aitsab 及び R. Pyndiahによる文献「Performance of Reed Solomon block turbo code」（IEEE Globecom '96 Conference、第１／３巻、１２１〜１２５頁、ロンドン、１９９６年１１月）との中で説明されている。
【０００５】
並列連結の畳み込み「ターボコード（turbo codes）」の性能は、比較的大きな範囲まで、実行された置換機能に依存する。実際には、この機能の最適化されない選択によって、特にエラー率曲線が１０−５及び１０−６以下の勾配変化の発生を含む、「ターボコード」の劣化をもたらすことがあると思われる。
【０００６】
この現象は、検討中の「ターボコード」の効率が高ければ高いほど、そしてコード化する情報ブロックが短ければ短いほど、なお一層強調される。
【０００７】
引用される種々のドキュメントの中で、「ターボコード」を優れた性能で構築することができる置換機能が提案されている。
【０００８】
特許文献１では、基本的な畳み込みコードはバイナリであり、このため、置換はバイナリ素子上に直接発生する。より一般的には、バイナリの畳み込みコードを実行する並列連結の「ターボコード」の中で置換機能を実行することについての多くの解決策は、第三世代の携帯電話（ＵＭＴＳ）の一環として提案されている。
【０００９】
特許文献２と、C. Berrou 及び M. Jezequelによる文献「Non-binary convolutional codes for turbo coding」（Electronics Letters、第３５巻、ｎｏ．１、３９〜４０頁、１９９９年１月）とにおいても、「ターボコード」を構築するために非バイナリの畳み込みコードを使用することを提案している。この場合、置換機能がこのためバイナリワード（ビットセット、例えば、ペア又はより一般的にはｎ−ペア）に適用される。
【００１０】
一般的に言うと、置換機能は、もちろん、強いランダム効果を作り出すために、情報源からの要素の良好な分散及び種々の並列のエンコーダへの供給を提供できることが必要である。このため、複合エンコーダの距離特性を最適化する必要があり、特にその最短距離を最大にする必要がある。
【特許文献１】フランス国特許第９ １０５ ２８０号明細書
【特許文献２】フランス国特許第９ ３１３ ８５８号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従って、本発明の目的は、特に、非バイナリの畳み込みコードから構築され、周知の「ターボコード」よりも優れた置換特性を有する、並列連結のコーディング方法（「ターボコード」）を提供することである。
【００１２】
特に、本発明の目的は、複合エンコーダの距離特性を最適にする（「ターボコード」）、すなわち、特にその最小距離を最大にする、並列連結のコーディング方法を提供することである。
【００１３】
本発明の別の目的は、もちろん、分散効果を変更せずに、種々の基本的なエンコーダに取り込まれるデータ上に強いランダム効果を作り出すコーディング方法を提供することである。
【００１４】
また、本発明の目的は、例えば、集積回路のように安価であり、実際的に容易に実行できるコーディング方法を提供することである。
【００１５】
本発明のさらに別の目的は、極めて大きな数のアプリケーションの種類に対して容易に実行できるコーディング方法を提供することである。
【課題を解決するための手段】
【００１６】
これらの目的、及び、この後よりはっきりと明白になる他の目的は、本発明に基づいて、少なくとも２つの基本的なコーディングステップを並列に実行する、ディジタルのソースデータのコーディング方法によって実現される。これらのコーディングステップのそれぞれは、全てのソースデータを考慮し、これらの基本的なコーディングステップ間のこれらのソースデータを考慮する順序を変更する置換ステップを含んでいる。ここで、このソースデータは、それぞれがｎのバイナリのソース素子からなるソースのコードワードの中で編成される。ｎは、２以上の数である。本発明によれば、この置換ステップは、以下のステップ、すなわち、
少なくともいくつかのこれらのソースのコードワードの内容を可逆的に変更して、変更されたコードワードを出力するステップと、
これらのソースのコード又は変更されたコードワードの順序を置換するステップと
を備えている。
【００１７】
言い換えると、本発明は置換ステップの間に、２つのレベルで効力を発することを提案する（「置換」という視覚的な用語は本願では維持されるが、後で明らかになるように、いくつかのバイナリ素子の値を変更することができるため、「シャフリング（shuffling）」又は「処理」という用語を都合よく使用することができる）。実際、一方では、コードワードの順序（又はｎの倍数）、及び他方においては、後者の内容（ワード間の変更）が影響を受ける。
【００１８】
ワードの置換は、ワードをそのように処理する前又は後で都合よく実行することができることに注意されたい。
【００１９】
好適な実施形態によれば、このコードワードの順序を置換するステップは、Ｎ個の連続したコードワードのブロックに加えられた一様な置換を実行する。
【００２０】
この技術は実行することが極めて容易であり、ほぼ最適な効率を達成することができる。
【００２１】
０からＮ−１までの順序で入力され、Ｊ＝Ｐ．ｉからの順序で再読されるＮ個のコードワードを含むメモリを用いて、この技術を都合よく実行することができる。ここで、ｉは０からＮ−１まで変化し、Ｐ及びＮは互いに素数である。
【００２２】
好ましくは、この場合、Ｐは、√Ｎに近い値である。
【００２３】
本発明の好ましい仕方によれば、この内容変更は、いくつかのコードワードのみに適用される。例えば、この内容変更は、１つおきのコードワードに適用される。
【００２４】
好都合なことに、この内容変更は、検討中のコードワード内のバイナリ素子の順序の置換を含んでいる。
【００２５】
別の好適な態様によれば、この内容変更は、検討中のコードワードのバイナリソースの素子の少なくとも１つを、少なくとも２つのバイナリソースの素子の組み合わせと置き換えるステップを含んでいる。
【００２６】
これらのコードワードは、特に、ペアとすることができる。しかしながら、それらは、もちろん、より一般的には、ｎの値を問わず、２以上のｎの倍数とすることができる。
【００２７】
ペアの場合には、組み合わせは、以下の変更されたペアである、
−（ａ，ｂ）
−（ｂ，ａ）
−（ａ＋ｂ，ｂ）
−（ｂ，ａ＋ｂ）
−（ａ，ａ＋ｂ）
−（ａ＋ｂ，ａ）
の少なくとも１つのソースのペア｛ａ，ｂ｝と関連付けることができる。
【００２８】
本発明の実施形態によれば、これらの基本的なコーディングステップの少なくとも１つは、系統的で帰納的な畳み込みコードを実行して、ｎ＋ｍのバイナリ出力をｎのバイナリ入力に関連付けるｎ／（ｎ＋ｍ）を必然的に生ずる。ここで、ｎ＞２、かつ、ｍ＞１である。
【００２９】
好ましくは、この方法は、ｎ＋ｍ１＋ｍ２のバイナリ出力を、以下を含むｎのバイナリ入力のコードワード、すなわち、
ｎのバイナリ入力と、
第１の基本的なコーディングステップによって供給されたｍ１のバイナリ出力と、
第２の基本的なコーディングステップによって供給されたｍ２のバイナリ出力と
に関連付ける。
【００３０】
本発明は、スタンピングステップを提供することができる。
【００３１】
もちろん、本発明は、対応するコーディング装置とも関連がある。そのような装置は、以下の手段を含む置換手段、すなわち、
少なくともいくつかのこれらのソースのコードワードの内容を可逆的に変更して、変更されたコードワードを提供する手段と、
これらのソース又は変更されたコードワードの順序を置換する手段と
によって実現される。
【００３２】
本発明はさらに、前述した仕方に基づいてコード化されたデータを発行又は送信する装置に関する。
【００３３】
本発明の別の態様によれば、本発明は対応するディコーディング方法及び装置に関する。コーディングとは対称的に、このディコーディング方法は、以下のステップ、すなわち、
受信されたコードワードの少なくともいくつかの内容を、コーディングの間に実行された変更とは反対に変更するステップと、
受信されたコードワードの順序を、初期の順序に戻すために置換するステップと
を含む。
【発明の効果】
【００３４】
本発明の他の特徴及び利点は、本発明の好ましい実施形態の以下の説明を読むことにより、より明白になるであろう。この説明は、例証となるがこれに限定されない実施例、及び、本発明によるエンコーダの一般的な着想を図示している唯一の添付した図面によって与えられる。
【発明を実施するための最良の形態】
【００３５】
本発明は、これにより、基本的なコードの並列連結するエンコーダに対して新規な置換機能を提供する。この置換機能は、ｎ−２及びｎ−１でｎ／（ｎ＋ｍ）を必然的に生じる、非バイナリの系統的、帰納的で基本的な畳み込みコードに関連して、理論的な限界に近い性能を結果として生ずる。この性能は、「ターボコード」に対して考慮された効率及びコード化する情報ブロックの長さによらない。
【００３６】
本発明の範囲の中で、検討中の基本的なコードは必然的に非バイナリである、すなわち、それらのコードはｎ−２のバイナリの入力及びｍ−１でｎ＋ｍのバイナリの出力を有していることを想起されたい。
【００３７】
本発明によるサンプルのコーディング装置が、図１に示されている。対応するコーディング方法を、直接それから引き出すことができる。
【００３８】
この実施例では、２つの基本的なコードＣ１及びＣ２、１１及び１２、の並列連結から組み立てられたコードを検討する。これらの２つの基本的なコードは、置換機能１３によって分離され、同一、畳み込み、帰納的、系統的、非バイナリで２／３を生じる（ｎ＝２のバイナリ入力であり、そのコードワードはペアである）。
【００３９】
さらに、コード化すべきデータのブロックは、ｐのバイナリのデータから構成すると仮定する。ここでｐは偶数であるか又は、同様に、Ｎ＝ｐ／２のバイナリのペアである。
【００４０】
複合のエンコーダがスタンプされない場合は、そのコーディングの効率は１／２に等しくなる。もちろん、スタンピング１４を従来通りに実行することができる。
【００４１】
前述したように、本発明によれば、置換機能１３は、次の２つの動作、すなわち、
コードワードの順序を置換する動作１３１（実施例ではペアであるが、より一般的には、ｎの任意の倍数）と、
データブロックの少なくともいくつかを処理する動作１３２と
に基づいている。
【００４２】
情報源１５からのＮのペアは基本的なエンコーダＣ１に供給され、次ぎに置換１３の後で、エンコーダＣ２に供給される。
【００４３】
置換機能は、情報源１５からのペアの（より一般的にはｎの倍数の）良好な分散を提供し、また強力なランダム効果を作り出すことを可能にする必要がある。達成すべき目的の１つは、実際は、複合エンコーダの距離特性を最適にすること、また特に、その最小距離を最大にすることである。
【００４４】
分散の基準については、置換１３の後で、情報源１５の出力において隣接するペア（より一般的にはｎの倍数）を、できるだけ多く分離する必要がある。この目的は、ペアのレベルにおいて（より一般的には、ｎの倍数のレベルにおいて）一様な置換１３１を用いることによって、ほぼ最適に達成することができる。
【００４５】
この一様な置換１３１は、Ｎのバイナリのペア（より一般的には、ｎの倍数）をＮの位置（位置０〜Ｎ−１）のメモリ１３１１内に一様に書き込み、また引き続いて、アドレスｊにおいてこれらのＮのペアを次のルールである、
ｊ＝ｐｉ ｍｏｄ Ｎ ｉ＝０，１ ．．． （Ｎ−１） （１）
を用いて読み出すこと（１３１２）によって実現することができる。
【００４６】
一度また一度だけメモリ１３１１のＮの位置を通り抜けるためには、Ｐ及びＮは互いに２つの素数であることが必要である（すなわち、それらは、１以外の公約数を持たないことが必要である）。さらに、情報源１５の出力において隣接するペア（より一般的には、ｎの倍数）の間に最適な間隔を提供するためには、パラメータＰは、√Ｎに近いことが好ましい。
【００４７】
この見地を例証するために、例えば、コード化すべきＮ＝９のバイナリのペアのブロックを考える。Ｐを４に設定する（４は、√９＝３に近い）。次の表が得られる。
【００４８】
【表１】
【００４９】
このため、エンコーダＣ２によってコード化すべきＮのペアは、アドレス０，４，８，３，７，２，６，１，５においてそれぞれ読み取られる。
【００５０】
このランダム効果を作り出すために、分散効果を変更することなく、（少なくとも）いくつかのペア（より一般的には、ｎの倍数）のバイナリデータは、処理動作１３２又は適当な変更を受ける。
【００５１】
簡単で極めて効果的な処理動作１３２は、ペア内のバイナリデータを、例えば、次のルール、すなわち、｛ａｋ，ｂｋ｝を、メモリ内の位置ｋ，ｋ＝０，１，．．．（Ｎ−１）に記憶されたバイナリのペアとするというルールに基づいて、それを基本的なエンコーダＣ２に渡す前に、定期的に置換する動作を構成する。変数ｉの奇数の値に対して、ルール（１）に基づいてアドレスｊで読み込まれたペアのバイナリデータは、エンコーダＣ２に渡される前に置換される。
【００５２】
前述の実施例に戻って参照すると、エンコーダＣ２によってコード化すべきＮ＝９のペアは、以下の順序、
｛ａ０，ｂ０｝，｛ｂ４，ａ４｝，｛ａ８，ｂ８｝，｛ｂ３，ａ３｝，｛ａ７，ｂ７｝，｛ｂ２，ａ２｝，｛ａ６，ｂ６｝，｛ｂ１，ａ１｝，｛ａ５，ｂ５｝
によって表される。
【００５３】
置換を受けたペアは、太字でプリントされている。
【００５４】
もちろん、ペアのバイナリデータを置換する動作以外の動作は、例えば、次のような、
｛ａｋ，ｂｋ｝−｛ａｋ＋ｂｋ，ｂｋ｝又は｛ａｋ，ｂｋ｝−｛ｂｋ，ａｋ＋ｂｋ｝ｍｏｄ２
又は
｛ａｋ，ｂｋ｝−｛ａｋ，ａｋ＋ｂｋ｝又は｛ａｋ，ｂｋ｝−｛ａｋ＋ｂｋ，ａｋ｝ｍｏｄ２
が可能である。
【００５５】
もちろん、各ペアのバイナリデータ上で実行された動作を逆にすることができる。実際に、例えば、｛ａｋ＋ｂｋ，ｂｋ｝を知れば、素子｛ａｋ＋ｂｋ｝及び｛ｂｋ｝を加算することによって、ａｋを得ることができる。
【００５６】
場合によっては、いくつかの動作をまとめる、及び／又は、代わりに使用することができる。
【００５７】
図１に示した実施例では、データブロックの処理１３２は、これらの同じブロックの置換１３１の後で実行される。しかしながら、これらの動作の順序を逆にすることができることは明白である。まず始めにコードワード（ｎの倍数）に対して処理動作を実行してから、その置換を行うことが可能である。
【００５８】
このため、この置換方法により、ｎ−２及びｎ−１でｎ／（ｎ＋ｍ）を必然的に生じる、系統的で帰納的な畳み込みコードの並列連結から「ターボコード」を構築することが可能になる。
【００５９】
これらの「ターボコード」の距離及び特に最小距離の特性は、周知の畳み込み「ターボコード」の特性よりも優れている。「ターボコード」のコーディング効率が高くなればなるほど、またコード化すべきバイナリデータのブロックが短ければそれだけ、この結果は一層明白になる。
【００６０】
このため、この置換機能は、データが短いフレーム内で構造化される（例えば、ＡＴＭ）送信用コーディングに対して、畳み込みブロックの「ターボコード」を構築するように特に設計されている。
【００６１】
ディコーディングは、以下のような、コーディングの間に実行された動作の逆の動作、すなわち、
最初のコードワードを復元するために（送信チャネルによる混信を除く）、受信されたコードワードの内容を変更する動作（逆の変更）と、
受信されたコードワードの順序を、初期の順序に戻すために置換する動作と
を実行する。
【００６２】
完全なコーディングの一般的な着想は、好ましくは、前述したフランス特許国第９ １０５ ２８０号明細書において説明されたものと同様である。しかしながら、基本的なデコーダによって交換された基本的な情報（外部情報と呼ぶ）は、もちろん、もはやバイナリ値ではなくコードワード又はｎの倍数である。
【００６３】
外部情報は、このため、ｎの倍数に対して可能な２ｎの場合に対応する、２ｎ値によって実行される。このためペアについては、前述したように、基本的なデコーダは一度に４つのデータを交換する。
【図面の簡単な説明】
【００６４】
【図１】本発明の好ましい実施態様を示す概念図である。
【符号の説明】
【００６５】
１３１ 置換ブロック
１３２ 変更ブロック
【技術分野】
【０００１】
本発明は、特に回路上に過渡現象が存在する中で、送信又は放送される１つ以上のソースデータの順序に属するディジタルデータをコーディングする分野、及びこのように送信されたコード化されたデータをディコーディングする分野である。より詳細には、本発明は、特に「ターボコード（turbo codes）」（登録商標）として周知のコーディング方法の改良に関し、特に、これにより実行される置換動作の改良に関する。
【背景技術】
【０００２】
この種のコーディングの一般的な原理は、特に、特許文献１と、C. Berrou 及び A. Glavieuxによる「Near Optimum Error Correcting Coding and Decoding: Turbo Codes」という題名の文献（IEEE Transactions on Communications、第４４巻、Ｎｏ．１０、ページ１２６１−１２７０、１９９６年１０月）との中で紹介されている。
【０００３】
この技術によれば、少なくとも２つの基本的なエンコーダの使用に基づく、「並列連結（parallel concatenation）」によるコーディングの実現が提案されている。ディコーディングする場合、これにより、２つの別個のエンコーダからの２つの冗長的な符号を持つことが可能になる。２つの基本的なエンコーダの間で、これらの基本的なエンコーダの各々が同じディジタルのソースデータを供給されるが、順序が変化して受け取られるように、置換手段が実行される。
【０００４】
ブロックコーディング（block coding）（製品コード）についてのこの種の技術の改良は、特許文献２と、O. Aitsab 及び R. Pyndiahによる文献「Performance of Reed Solomon block turbo code」（IEEE Globecom '96 Conference、第１／３巻、１２１〜１２５頁、ロンドン、１９９６年１１月）との中で説明されている。
【０００５】
並列連結の畳み込み「ターボコード（turbo codes）」の性能は、比較的大きな範囲まで、実行された置換機能に依存する。実際には、この機能の最適化されない選択によって、特にエラー率曲線が１０−５及び１０−６以下の勾配変化の発生を含む、「ターボコード」の劣化をもたらすことがあると思われる。
【０００６】
この現象は、検討中の「ターボコード」の効率が高ければ高いほど、そしてコード化する情報ブロックが短ければ短いほど、なお一層強調される。
【０００７】
引用される種々のドキュメントの中で、「ターボコード」を優れた性能で構築することができる置換機能が提案されている。
【０００８】
特許文献１では、基本的な畳み込みコードはバイナリであり、このため、置換はバイナリ素子上に直接発生する。より一般的には、バイナリの畳み込みコードを実行する並列連結の「ターボコード」の中で置換機能を実行することについての多くの解決策は、第三世代の携帯電話（ＵＭＴＳ）の一環として提案されている。
【０００９】
特許文献２と、C. Berrou 及び M. Jezequelによる文献「Non-binary convolutional codes for turbo coding」（Electronics Letters、第３５巻、ｎｏ．１、３９〜４０頁、１９９９年１月）とにおいても、「ターボコード」を構築するために非バイナリの畳み込みコードを使用することを提案している。この場合、置換機能がこのためバイナリワード（ビットセット、例えば、ペア又はより一般的にはｎ−ペア）に適用される。
【００１０】
一般的に言うと、置換機能は、もちろん、強いランダム効果を作り出すために、情報源からの要素の良好な分散及び種々の並列のエンコーダへの供給を提供できることが必要である。このため、複合エンコーダの距離特性を最適化する必要があり、特にその最短距離を最大にする必要がある。
【特許文献１】フランス国特許第９ １０５ ２８０号明細書
【特許文献２】フランス国特許第９ ３１３ ８５８号明細書
【発明の開示】
【発明が解決しようとする課題】
【００１１】
従って、本発明の目的は、特に、非バイナリの畳み込みコードから構築され、周知の「ターボコード」よりも優れた置換特性を有する、並列連結のコーディング方法（「ターボコード」）を提供することである。
【００１２】
特に、本発明の目的は、複合エンコーダの距離特性を最適にする（「ターボコード」）、すなわち、特にその最小距離を最大にする、並列連結のコーディング方法を提供することである。
【００１３】
本発明の別の目的は、もちろん、分散効果を変更せずに、種々の基本的なエンコーダに取り込まれるデータ上に強いランダム効果を作り出すコーディング方法を提供することである。
【００１４】
また、本発明の目的は、例えば、集積回路のように安価であり、実際的に容易に実行できるコーディング方法を提供することである。
【００１５】
本発明のさらに別の目的は、極めて大きな数のアプリケーションの種類に対して容易に実行できるコーディング方法を提供することである。
【課題を解決するための手段】
【００１６】
これらの目的、及び、この後よりはっきりと明白になる他の目的は、本発明に基づいて、少なくとも２つの基本的なコーディングステップを並列に実行する、ディジタルのソースデータのコーディング方法によって実現される。これらのコーディングステップのそれぞれは、全てのソースデータを考慮し、これらの基本的なコーディングステップ間のこれらのソースデータを考慮する順序を変更する置換ステップを含んでいる。ここで、このソースデータは、それぞれがｎのバイナリのソース素子からなるソースのコードワードの中で編成される。ｎは、２以上の数である。本発明によれば、この置換ステップは、以下のステップ、すなわち、
少なくともいくつかのこれらのソースのコードワードの内容を可逆的に変更して、変更されたコードワードを出力するステップと、
これらのソースのコード又は変更されたコードワードの順序を置換するステップと
を備えている。
【００１７】
言い換えると、本発明は置換ステップの間に、２つのレベルで効力を発することを提案する（「置換」という視覚的な用語は本願では維持されるが、後で明らかになるように、いくつかのバイナリ素子の値を変更することができるため、「シャフリング（shuffling）」又は「処理」という用語を都合よく使用することができる）。実際、一方では、コードワードの順序（又はｎの倍数）、及び他方においては、後者の内容（ワード間の変更）が影響を受ける。
【００１８】
ワードの置換は、ワードをそのように処理する前又は後で都合よく実行することができることに注意されたい。
【００１９】
好適な実施形態によれば、このコードワードの順序を置換するステップは、Ｎ個の連続したコードワードのブロックに加えられた一様な置換を実行する。
【００２０】
この技術は実行することが極めて容易であり、ほぼ最適な効率を達成することができる。
【００２１】
０からＮ−１までの順序で入力され、Ｊ＝Ｐ．ｉからの順序で再読されるＮ個のコードワードを含むメモリを用いて、この技術を都合よく実行することができる。ここで、ｉは０からＮ−１まで変化し、Ｐ及びＮは互いに素数である。
【００２２】
好ましくは、この場合、Ｐは、√Ｎに近い値である。
【００２３】
本発明の好ましい仕方によれば、この内容変更は、いくつかのコードワードのみに適用される。例えば、この内容変更は、１つおきのコードワードに適用される。
【００２４】
好都合なことに、この内容変更は、検討中のコードワード内のバイナリ素子の順序の置換を含んでいる。
【００２５】
別の好適な態様によれば、この内容変更は、検討中のコードワードのバイナリソースの素子の少なくとも１つを、少なくとも２つのバイナリソースの素子の組み合わせと置き換えるステップを含んでいる。
【００２６】
これらのコードワードは、特に、ペアとすることができる。しかしながら、それらは、もちろん、より一般的には、ｎの値を問わず、２以上のｎの倍数とすることができる。
【００２７】
ペアの場合には、組み合わせは、以下の変更されたペアである、
−（ａ，ｂ）
−（ｂ，ａ）
−（ａ＋ｂ，ｂ）
−（ｂ，ａ＋ｂ）
−（ａ，ａ＋ｂ）
−（ａ＋ｂ，ａ）
の少なくとも１つのソースのペア｛ａ，ｂ｝と関連付けることができる。
【００２８】
本発明の実施形態によれば、これらの基本的なコーディングステップの少なくとも１つは、系統的で帰納的な畳み込みコードを実行して、ｎ＋ｍのバイナリ出力をｎのバイナリ入力に関連付けるｎ／（ｎ＋ｍ）を必然的に生ずる。ここで、ｎ＞２、かつ、ｍ＞１である。
【００２９】
好ましくは、この方法は、ｎ＋ｍ１＋ｍ２のバイナリ出力を、以下を含むｎのバイナリ入力のコードワード、すなわち、
ｎのバイナリ入力と、
第１の基本的なコーディングステップによって供給されたｍ１のバイナリ出力と、
第２の基本的なコーディングステップによって供給されたｍ２のバイナリ出力と
に関連付ける。
【００３０】
本発明は、スタンピングステップを提供することができる。
【００３１】
もちろん、本発明は、対応するコーディング装置とも関連がある。そのような装置は、以下の手段を含む置換手段、すなわち、
少なくともいくつかのこれらのソースのコードワードの内容を可逆的に変更して、変更されたコードワードを提供する手段と、
これらのソース又は変更されたコードワードの順序を置換する手段と
によって実現される。
【００３２】
本発明はさらに、前述した仕方に基づいてコード化されたデータを発行又は送信する装置に関する。
【００３３】
本発明の別の態様によれば、本発明は対応するディコーディング方法及び装置に関する。コーディングとは対称的に、このディコーディング方法は、以下のステップ、すなわち、
受信されたコードワードの少なくともいくつかの内容を、コーディングの間に実行された変更とは反対に変更するステップと、
受信されたコードワードの順序を、初期の順序に戻すために置換するステップと
を含む。
【発明の効果】
【００３４】
本発明の他の特徴及び利点は、本発明の好ましい実施形態の以下の説明を読むことにより、より明白になるであろう。この説明は、例証となるがこれに限定されない実施例、及び、本発明によるエンコーダの一般的な着想を図示している唯一の添付した図面によって与えられる。
【発明を実施するための最良の形態】
【００３５】
本発明は、これにより、基本的なコードの並列連結するエンコーダに対して新規な置換機能を提供する。この置換機能は、ｎ−２及びｎ−１でｎ／（ｎ＋ｍ）を必然的に生じる、非バイナリの系統的、帰納的で基本的な畳み込みコードに関連して、理論的な限界に近い性能を結果として生ずる。この性能は、「ターボコード」に対して考慮された効率及びコード化する情報ブロックの長さによらない。
【００３６】
本発明の範囲の中で、検討中の基本的なコードは必然的に非バイナリである、すなわち、それらのコードはｎ−２のバイナリの入力及びｍ−１でｎ＋ｍのバイナリの出力を有していることを想起されたい。
【００３７】
本発明によるサンプルのコーディング装置が、図１に示されている。対応するコーディング方法を、直接それから引き出すことができる。
【００３８】
この実施例では、２つの基本的なコードＣ１及びＣ２、１１及び１２、の並列連結から組み立てられたコードを検討する。これらの２つの基本的なコードは、置換機能１３によって分離され、同一、畳み込み、帰納的、系統的、非バイナリで２／３を生じる（ｎ＝２のバイナリ入力であり、そのコードワードはペアである）。
【００３９】
さらに、コード化すべきデータのブロックは、ｐのバイナリのデータから構成すると仮定する。ここでｐは偶数であるか又は、同様に、Ｎ＝ｐ／２のバイナリのペアである。
【００４０】
複合のエンコーダがスタンプされない場合は、そのコーディングの効率は１／２に等しくなる。もちろん、スタンピング１４を従来通りに実行することができる。
【００４１】
前述したように、本発明によれば、置換機能１３は、次の２つの動作、すなわち、
コードワードの順序を置換する動作１３１（実施例ではペアであるが、より一般的には、ｎの任意の倍数）と、
データブロックの少なくともいくつかを処理する動作１３２と
に基づいている。
【００４２】
情報源１５からのＮのペアは基本的なエンコーダＣ１に供給され、次ぎに置換１３の後で、エンコーダＣ２に供給される。
【００４３】
置換機能は、情報源１５からのペアの（より一般的にはｎの倍数の）良好な分散を提供し、また強力なランダム効果を作り出すことを可能にする必要がある。達成すべき目的の１つは、実際は、複合エンコーダの距離特性を最適にすること、また特に、その最小距離を最大にすることである。
【００４４】
分散の基準については、置換１３の後で、情報源１５の出力において隣接するペア（より一般的にはｎの倍数）を、できるだけ多く分離する必要がある。この目的は、ペアのレベルにおいて（より一般的には、ｎの倍数のレベルにおいて）一様な置換１３１を用いることによって、ほぼ最適に達成することができる。
【００４５】
この一様な置換１３１は、Ｎのバイナリのペア（より一般的には、ｎの倍数）をＮの位置（位置０〜Ｎ−１）のメモリ１３１１内に一様に書き込み、また引き続いて、アドレスｊにおいてこれらのＮのペアを次のルールである、
ｊ＝ｐｉ ｍｏｄ Ｎ ｉ＝０，１ ．．． （Ｎ−１） （１）
を用いて読み出すこと（１３１２）によって実現することができる。
【００４６】
一度また一度だけメモリ１３１１のＮの位置を通り抜けるためには、Ｐ及びＮは互いに２つの素数であることが必要である（すなわち、それらは、１以外の公約数を持たないことが必要である）。さらに、情報源１５の出力において隣接するペア（より一般的には、ｎの倍数）の間に最適な間隔を提供するためには、パラメータＰは、√Ｎに近いことが好ましい。
【００４７】
この見地を例証するために、例えば、コード化すべきＮ＝９のバイナリのペアのブロックを考える。Ｐを４に設定する（４は、√９＝３に近い）。次の表が得られる。
【００４８】
【表１】
【００４９】
このため、エンコーダＣ２によってコード化すべきＮのペアは、アドレス０，４，８，３，７，２，６，１，５においてそれぞれ読み取られる。
【００５０】
このランダム効果を作り出すために、分散効果を変更することなく、（少なくとも）いくつかのペア（より一般的には、ｎの倍数）のバイナリデータは、処理動作１３２又は適当な変更を受ける。
【００５１】
簡単で極めて効果的な処理動作１３２は、ペア内のバイナリデータを、例えば、次のルール、すなわち、｛ａｋ，ｂｋ｝を、メモリ内の位置ｋ，ｋ＝０，１，．．．（Ｎ−１）に記憶されたバイナリのペアとするというルールに基づいて、それを基本的なエンコーダＣ２に渡す前に、定期的に置換する動作を構成する。変数ｉの奇数の値に対して、ルール（１）に基づいてアドレスｊで読み込まれたペアのバイナリデータは、エンコーダＣ２に渡される前に置換される。
【００５２】
前述の実施例に戻って参照すると、エンコーダＣ２によってコード化すべきＮ＝９のペアは、以下の順序、
｛ａ０，ｂ０｝，｛ｂ４，ａ４｝，｛ａ８，ｂ８｝，｛ｂ３，ａ３｝，｛ａ７，ｂ７｝，｛ｂ２，ａ２｝，｛ａ６，ｂ６｝，｛ｂ１，ａ１｝，｛ａ５，ｂ５｝
によって表される。
【００５３】
置換を受けたペアは、太字でプリントされている。
【００５４】
もちろん、ペアのバイナリデータを置換する動作以外の動作は、例えば、次のような、
｛ａｋ，ｂｋ｝−｛ａｋ＋ｂｋ，ｂｋ｝又は｛ａｋ，ｂｋ｝−｛ｂｋ，ａｋ＋ｂｋ｝ｍｏｄ２
又は
｛ａｋ，ｂｋ｝−｛ａｋ，ａｋ＋ｂｋ｝又は｛ａｋ，ｂｋ｝−｛ａｋ＋ｂｋ，ａｋ｝ｍｏｄ２
が可能である。
【００５５】
もちろん、各ペアのバイナリデータ上で実行された動作を逆にすることができる。実際に、例えば、｛ａｋ＋ｂｋ，ｂｋ｝を知れば、素子｛ａｋ＋ｂｋ｝及び｛ｂｋ｝を加算することによって、ａｋを得ることができる。
【００５６】
場合によっては、いくつかの動作をまとめる、及び／又は、代わりに使用することができる。
【００５７】
図１に示した実施例では、データブロックの処理１３２は、これらの同じブロックの置換１３１の後で実行される。しかしながら、これらの動作の順序を逆にすることができることは明白である。まず始めにコードワード（ｎの倍数）に対して処理動作を実行してから、その置換を行うことが可能である。
【００５８】
このため、この置換方法により、ｎ−２及びｎ−１でｎ／（ｎ＋ｍ）を必然的に生じる、系統的で帰納的な畳み込みコードの並列連結から「ターボコード」を構築することが可能になる。
【００５９】
これらの「ターボコード」の距離及び特に最小距離の特性は、周知の畳み込み「ターボコード」の特性よりも優れている。「ターボコード」のコーディング効率が高くなればなるほど、またコード化すべきバイナリデータのブロックが短ければそれだけ、この結果は一層明白になる。
【００６０】
このため、この置換機能は、データが短いフレーム内で構造化される（例えば、ＡＴＭ）送信用コーディングに対して、畳み込みブロックの「ターボコード」を構築するように特に設計されている。
【００６１】
ディコーディングは、以下のような、コーディングの間に実行された動作の逆の動作、すなわち、
最初のコードワードを復元するために（送信チャネルによる混信を除く）、受信されたコードワードの内容を変更する動作（逆の変更）と、
受信されたコードワードの順序を、初期の順序に戻すために置換する動作と
を実行する。
【００６２】
完全なコーディングの一般的な着想は、好ましくは、前述したフランス特許国第９ １０５ ２８０号明細書において説明されたものと同様である。しかしながら、基本的なデコーダによって交換された基本的な情報（外部情報と呼ぶ）は、もちろん、もはやバイナリ値ではなくコードワード又はｎの倍数である。
【００６３】
外部情報は、このため、ｎの倍数に対して可能な２ｎの場合に対応する、２ｎ値によって実行される。このためペアについては、前述したように、基本的なデコーダは一度に４つのデータを交換する。
【図面の簡単な説明】
【００６４】
【図１】本発明の好ましい実施態様を示す概念図である。
【符号の説明】
【００６５】
１３１ 置換ブロック
１３２ 変更ブロック
【特許請求の範囲】
【請求項１】
それぞれがソースデータ（２５）の全てを考慮に入れる少なくとも２つの基本的なコーディングステップ（１１，１２）を並列に実行し、該基本的なコーディングステップ（１１，１２）間の前記ソースデータを考慮する順序を変更する置換ステップ（１３）を備える前記ディジタルのソースデータをコーディングする方法であって、
前記ソースデータ（１５）が、それぞれが２以上のｎのバイナリのソース素子を含むソースのコードワードの中で編成されており、前記置換ステップ（１３）が、
少なくともいくつかの前記ソースのコードワードの内容を可逆的に変更して、変更されたコードワードを出力するステップ（１３２）と、
前記ソース又は変更されたコードワードの順序を置換するステップ（１３１）と
を備えるコーディング方法。
【請求項２】
前記コードワードの順序を置換する前記ステップ（１３１）が、Ｎの連続的なコードワードのブロックに適用された一様な置換を実行するものである、請求項１に記載のコーディング方法。
【請求項３】
前記一様な置換が、０からＮ−１までの順序で入力され、ｉが０からＮ−１まで変化するＪ＝Ｐ．ｉからの順序で再び読み取られるＮのコードワードを含むメモリ（１３１１）を使用するものであり、Ｐ及びＮは互いに素数である、請求項２に記載のコーディング方法。
【請求項４】
Ｐが、√Ｎに近いものである請求項３に記載のコーディング方法。
【請求項５】
前記内容の変更（１３２）が、前記コードワードのいくつかにのみ適用されるものである、請求項１から４のいずれかに記載のコーディング方法。
【請求項６】
前記内容の変更（１３２）が、１つおきのコードワードに適用されるものである、請求項５に記載のコーディング方法。
【請求項７】
前記内容の変更（１３２）が、検討されるコードワード内のバイナリ素子の順序を置換する動作を含むものである、請求項１から６のいずれかに記載のコーディング方法。
【請求項８】
前記内容の変更（１３２）が、前記検討されるコードワードの前記バイナリのソース素子の少なくとも１つを、前記バイナリのソース素子の少なくとも２つの組み合わせと交換する動作を含むものである、請求項１から７のいずれかに記載のコーディング方法。
【請求項９】
前記コードワードがバイナリ素子のペアである、請求項１から８のいずれかに記載のコーディング方法。
【請求項１０】
前記内容を変更するステップ（１３２）が、以下の変更されたペアである、
（ａ，ｂ）
（ｂ，ａ）
（ａ＋ｂ，ｂ）
（ｂ，ａ＋ｂ）
（ａ，ａ＋ｂ）
（ａ＋ｂ，ａ）
の少なくとも１つのソースのペア｛ａ，ｂ｝と関連付けるものである、請求項９に記載のコーディング方法。
【請求項１１】
前記基本的なコーディングステップ（１３，１２）の少なくとも１つが、系統的で帰納的な畳み込みコードを実行して、ｎ＞２、かつ、ｍ＞１であり、ｎ＋ｍのバイナリ出力をｎのバイナリ入力に関連付けるｎ／（ｎ＋ｍ）を必然的に生ずるものである、請求項１から１０のいずれかに記載のコーディング方法。
【請求項１２】
前記コーディング方法が、ｎ＋ｍ１＋ｍ２のバイナリ出力を、
前記ｎのバイナリ入力と、
第１の基本的なコーディングステップによって供給されたｍ１のバイナリ出力と、
第２の基本的なコーディングステップによって供給されたｍ２のバイナリ出力と
を含むｎのバイナリ入力のコードワードに関連付けるものである、請求項１から１１のいずれかに記載のコーディング方法。
【請求項１３】
前記コーディング方法がスタンピングステップ（１４）を実行するものである、請求項１から請求項１２のいずれかに記載のコーディング方法。
【請求項１４】
それぞれがソースデータ（１５）の全てを考慮に入れる少なくとも２つの基本的なエンコーダ（１１，１２）と、前記ソースデータの検討の順序を前記各基本的なエンコーダによって変更する置換手段（１３）とを備えるディジタルソースをコーディングする装置であって、前記ソースデータが、それぞれが２以上のｎのバイナリのソース素子からなるソースのコードワードの中で編成され、前記置換手段（１３）が、
少なくともいくつかの前記ソースのコードワードの内容を可逆的に変更して、変更されたコードワードを出力する手段（１３２）と、
前記ソース又は変更されたコードワードの順序を置換する手段（１３１）と
を備えてなる、ディジタルソースをコーディングする装置。
【請求項１５】
受信されたコードワードの少なくともいくつかの内容を、コーディングの間に実行された変更とは反対に変更するステップと、
前記受信されたコードワードの順序を、初期の順序に戻すために置換するステップと
を備える置換ステップを含む、請求項１から１３のいずれかのコーディング方法に基づいてコード化されたディジタルデータをディコーディングする方法。
【請求項１６】
受信されたコードワードの少なくともいくつかの内容を、コーディングの間に実行された変更とは反対に変更する手段と、
前記受信されたコードワードの順序を、初期の順序に戻すために置換する手段と
を備える置換手段を含む、請求項１から１３のいずれかのコーディング方法に基づいてコード化されたディジタルデータをディコーディングする装置。
【請求項１７】
請求項１から１３のいずれかのコーディング方法に基づいてコード化された、又は請求項１５のディコーディング方法に基づいてデコードされたディジタルデータを送信、及び／又は、受信する装置。
【請求項１】
それぞれがソースデータ（２５）の全てを考慮に入れる少なくとも２つの基本的なコーディングステップ（１１，１２）を並列に実行し、該基本的なコーディングステップ（１１，１２）間の前記ソースデータを考慮する順序を変更する置換ステップ（１３）を備える前記ディジタルのソースデータをコーディングする方法であって、
前記ソースデータ（１５）が、それぞれが２以上のｎのバイナリのソース素子を含むソースのコードワードの中で編成されており、前記置換ステップ（１３）が、
少なくともいくつかの前記ソースのコードワードの内容を可逆的に変更して、変更されたコードワードを出力するステップ（１３２）と、
前記ソース又は変更されたコードワードの順序を置換するステップ（１３１）と
を備えるコーディング方法。
【請求項２】
前記コードワードの順序を置換する前記ステップ（１３１）が、Ｎの連続的なコードワードのブロックに適用された一様な置換を実行するものである、請求項１に記載のコーディング方法。
【請求項３】
前記一様な置換が、０からＮ−１までの順序で入力され、ｉが０からＮ−１まで変化するＪ＝Ｐ．ｉからの順序で再び読み取られるＮのコードワードを含むメモリ（１３１１）を使用するものであり、Ｐ及びＮは互いに素数である、請求項２に記載のコーディング方法。
【請求項４】
Ｐが、√Ｎに近いものである請求項３に記載のコーディング方法。
【請求項５】
前記内容の変更（１３２）が、前記コードワードのいくつかにのみ適用されるものである、請求項１から４のいずれかに記載のコーディング方法。
【請求項６】
前記内容の変更（１３２）が、１つおきのコードワードに適用されるものである、請求項５に記載のコーディング方法。
【請求項７】
前記内容の変更（１３２）が、検討されるコードワード内のバイナリ素子の順序を置換する動作を含むものである、請求項１から６のいずれかに記載のコーディング方法。
【請求項８】
前記内容の変更（１３２）が、前記検討されるコードワードの前記バイナリのソース素子の少なくとも１つを、前記バイナリのソース素子の少なくとも２つの組み合わせと交換する動作を含むものである、請求項１から７のいずれかに記載のコーディング方法。
【請求項９】
前記コードワードがバイナリ素子のペアである、請求項１から８のいずれかに記載のコーディング方法。
【請求項１０】
前記内容を変更するステップ（１３２）が、以下の変更されたペアである、
（ａ，ｂ）
（ｂ，ａ）
（ａ＋ｂ，ｂ）
（ｂ，ａ＋ｂ）
（ａ，ａ＋ｂ）
（ａ＋ｂ，ａ）
の少なくとも１つのソースのペア｛ａ，ｂ｝と関連付けるものである、請求項９に記載のコーディング方法。
【請求項１１】
前記基本的なコーディングステップ（１３，１２）の少なくとも１つが、系統的で帰納的な畳み込みコードを実行して、ｎ＞２、かつ、ｍ＞１であり、ｎ＋ｍのバイナリ出力をｎのバイナリ入力に関連付けるｎ／（ｎ＋ｍ）を必然的に生ずるものである、請求項１から１０のいずれかに記載のコーディング方法。
【請求項１２】
前記コーディング方法が、ｎ＋ｍ１＋ｍ２のバイナリ出力を、
前記ｎのバイナリ入力と、
第１の基本的なコーディングステップによって供給されたｍ１のバイナリ出力と、
第２の基本的なコーディングステップによって供給されたｍ２のバイナリ出力と
を含むｎのバイナリ入力のコードワードに関連付けるものである、請求項１から１１のいずれかに記載のコーディング方法。
【請求項１３】
前記コーディング方法がスタンピングステップ（１４）を実行するものである、請求項１から請求項１２のいずれかに記載のコーディング方法。
【請求項１４】
それぞれがソースデータ（１５）の全てを考慮に入れる少なくとも２つの基本的なエンコーダ（１１，１２）と、前記ソースデータの検討の順序を前記各基本的なエンコーダによって変更する置換手段（１３）とを備えるディジタルソースをコーディングする装置であって、前記ソースデータが、それぞれが２以上のｎのバイナリのソース素子からなるソースのコードワードの中で編成され、前記置換手段（１３）が、
少なくともいくつかの前記ソースのコードワードの内容を可逆的に変更して、変更されたコードワードを出力する手段（１３２）と、
前記ソース又は変更されたコードワードの順序を置換する手段（１３１）と
を備えてなる、ディジタルソースをコーディングする装置。
【請求項１５】
受信されたコードワードの少なくともいくつかの内容を、コーディングの間に実行された変更とは反対に変更するステップと、
前記受信されたコードワードの順序を、初期の順序に戻すために置換するステップと
を備える置換ステップを含む、請求項１から１３のいずれかのコーディング方法に基づいてコード化されたディジタルデータをディコーディングする方法。
【請求項１６】
受信されたコードワードの少なくともいくつかの内容を、コーディングの間に実行された変更とは反対に変更する手段と、
前記受信されたコードワードの順序を、初期の順序に戻すために置換する手段と
を備える置換手段を含む、請求項１から１３のいずれかのコーディング方法に基づいてコード化されたディジタルデータをディコーディングする装置。
【請求項１７】
請求項１から１３のいずれかのコーディング方法に基づいてコード化された、又は請求項１５のディコーディング方法に基づいてデコードされたディジタルデータを送信、及び／又は、受信する装置。
【図１】
【公開番号】特開２００７−３１８７７２（Ｐ２００７−３１８７７２Ａ）
【公開日】平成１９年１２月６日（２００７．１２．６）
【国際特許分類】
【出願番号】特願２００７−１６４０２８（Ｐ２００７−１６４０２８）
【出願日】平成１９年６月２１日（２００７．６．２１）
【分割の表示】特願２００１−５１０９９７（Ｐ２００１−５１０９９７）の分割
【原出願日】平成１２年７月１９日（２０００．７．１９）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【出願人】（５０２０６９３６３）
【Ｆターム（参考）】
【公開日】平成１９年１２月６日（２００７．１２．６）
【国際特許分類】
【出願日】平成１９年６月２１日（２００７．６．２１）
【分割の表示】特願２００１−５１０９９７（Ｐ２００１−５１０９９７）の分割
【原出願日】平成１２年７月１９日（２０００．７．１９）
【出願人】（５９１０３４１５４）フランス テレコム (290)
【出願人】（５０２０６９３６３）
【Ｆターム（参考）】
[ Back to top ]