(57)【特許請求の範囲】
【請求項１】
元の２進データ系列（u）を符号化する方法であって、
第１のパディング２進データ系列（p1）により補填された前記元の２進データ系列（u）が除数多項式（g）で割り切れるように選択された第１のパディング２進データ系列（p1）によって、前記元の２進データ系列（u）を補填する少なくとも１回のパディング処理を実行する第１のパディング処理工程と、
前記第１のパディング２進データ系列（p1）により補填された前記第１の２進データ系列（u）を前記除数多項式（g）を使用する符号化技法によって符号化する少なくとも１回の再帰畳込み符号化処理を実行する第１の再帰畳込み符号化処理工程と、
前記元の２進データ系列（u）の２進データをインタリーブ系列（u*）を得るように特定の置換によって置換する少なくとも１回のインタリーブ動作を実行するインタリーブ工程と、
第２のパディング２進データ系列（p2）により補填された前記インタリーブ系列（u*）が前記除数多項式（g）により割り切れるように選択された当該第２のパディング２進データ系列（p2）で前記インタリーブ系列（u*）を補填する、少なくとも１回のパディング処理を実行する第２のパディング処理工程と、
前記第２のパディング２進データ系列（p2）により補填された前記インタリーブ系列（u*）を前記除数多項式（g）を使用する符号化技法によって符号化する、少なくとも１回の再帰畳込み符号化処理を実行する第２の再帰畳込み符号化処理工程とを備え、
前記特定の置換は、前記第１の除数多項式（g1）が多項式xNO＋１を割り切るような最小の整数をNOとし、且つ正の整数をMとするとき、前記元の２進データ系列（u）の２進データがNO列、M行の配列に行ごとに書き込まれ且つ読み取られるような表現において、前記除数多項式（g）で割り切れるという性質が維持され、前記元の２進データ系列（u）を表現する配列のNO個の列を互いに置換する列間置換と、それぞれが前記配列中の１つの列の中における記号の置換である任意の数の列内基本置換との合成である
ことを特徴とする符号化方法。
【請求項２】
前記第２のパディング２進データ系列（p2）の２進データは、前記第１のパディング２進データ系列（p1）の２進データの知識からのみ決定されることを特徴とする請求項１に記載の符号化方法。
【請求項３】
前記第２のパディング２進データ系列（p2）の２進データは、前記第１のパディング２進データ系列（p1）の関数として前記第２のパディング２進データ系列（p2）を表すあらかじめ作成された変換テーブルから決定されることを特徴とする請求項２に記載の符号化方法。
【請求項４】
前記第２のパディング２進データ系列（p2）の２進データは、前記第１のパディング２進データ系列（p1）の２進データの関数として決定されることを特徴とする請求項２に記載の符号化方法。
【請求項５】
前記第２のパディング処理工程において、前記除数多項式（g）の次数に等しいデータ数を有する前記第１のパディング２進データ系列（p1）から前記第２のパディング２進データ系列（p2）を構成するために、
NOに等しい長さの系列を得るように、前記第１のパディング２進データ系列（p1）を０で補填し、
第１のインタリーブパディング系列（p”1）を得るように、前記列間置換によって前記第1のパディング２進データ系列（p1）の２進データを置換し、
前記除数多項式（g）による前記第１のインタリーブパディング系列（p”1）の多項式除算の余りを判定し、且つ
前記余りを前記第２のパディング２進データ系列（p2）として選択することを特徴とする請求項１乃至４のいずれか１項に記載の符号化方法。
【請求項６】
前記列間置換は恒等式置換であり、前記前記第２のパディング２進データ系列（p2）は前記第１のパディング２進データ系列（p1）と等しいものとして判定されることを特徴とする請求項１記載の符号化方法。
【請求項７】
前記第１及び第２のパディング２進データ系列（p1、p2）の少なくとも一方はパンクチュアされることを特徴とする請求項１乃至６のいずれか１項に記載の符号化方法。
【請求項８】
前記第１及び第２のパディング２進データ系列（p1、p2）の少なくとも一方は、符号化系列が当該パディング２進データ系列の全てを表現したままである部分を含むようにパンクチュアされることを特徴とする請求項７記載の符号化方法。
【請求項９】
前記第１のパディング２進データ系列（p1）はその全体がパンクチュアされることを特徴とする請求項７又は８記載の符号化方法。
【請求項１０】
前記第２のパディング２進データ系列（p2）はその全体がパンクチュアされることを特徴とする請求項７又は８記載の符号化方法。
【請求項１１】
第１のパディング２進データ系列（p1）により補填された元の２進データ系列（u）が除数多項式（g）で割り切れるように選択された第１のパディング２進データ系列（p1）によって、当該元の２進データ系列（u）を補填する第１のパディング手段と、
前記第１のパディング２進データ系列（p1）により補填された前記元の２進データ系列（u）を前記除数多項式（g）を使用する符号化技法によって符号化する第１の再帰畳込み符号化手段と、
前記元の２進データ系列（u）の２進データをインタリーブ系列（u*）を得るように特定の置換によって置換する少なくとも第１のインタリーブ手段と、
第２のパディング２進データ系列（p2）により補填された前記インタリーブ系列（u*）が前記除数多項式（g）により割り切れるように選択された第２のパディング２進データ系列（p2）で前記インタリーブ系列（u*）を補填する第２のパディング手段と、
前記第２のパディング２進データ系列（p2）により補填された前記インタリーブ系列（u*）を前記除数多項式（g）を使用する符号化技法によって符号化する第２の再帰畳込み符号化手段とを備え、
前記特定の置換は、前記除数多項式（g）が多項式xNO＋１を割り切るような最小の整数をNOとし、且つ正の整数をMとするとき、前記元の２進データ系列（u）の２進データがNO列、M行の配列に行ごとに書き込まれ且つ読み取られるような表現において、前記除数多項式（g）で割り切れるという性質が維持され、前記元の２進データ系列（u）を表現する配列のNO個の列を互いに置換する列間置換と、それぞれが前記配列中の１つの列の中における記号の置換である任意の数の列内基本置換との合成である
ことを特徴とする符号化装置。
【請求項１２】
請求項１乃至１０のいずれか１項に記載の符号化方法によって前記元の２進データ系列（u）を符号化して得られた元の記号系列を復号することを特徴とする復号方法。
【請求項１３】
ソフト入力ソフト出力復号動作を実現することを特徴とする請求項１２に記載の復号方法。
【請求項１４】
前記元の記号系列の第１の部分系列を除数多項式（g）を使用する復号技法によって復号し、且つ第１及び第２のパディング２進データ系列（p1、p2）の関数である第１の２進データ系列（p'1）を考慮して、再帰畳込み符号を復号する少なくとも１回の第１の基本動作を繰り返し実行することを特徴とする請求項１２又は１３に記載の復号方法。
【請求項１５】
前記第１の２進データ系列（p'1）は、前記第１及び第２のパディング２進データ系列（p1、p2）の関数として第１の２進データ系列（p'1）を表すあらかじめ確立された恒等式の系から決定されることを特徴とする請求項１４記載の復号方法。
【請求項１６】
前記第１の２進データ系列（p'1）は、第１及び第２のパディング２進データ系列（p1、p2）の関数として第１の２進データ系列（p'1）を与え、且つ確立された恒等式の系から決定されることを特徴とする請求項１４に記載の復号方法。
【請求項１７】
前記元の記号系列の第１の部分系列を除数多項式（g）を使用する復号技法によって復号し、且つ第１及び第２のパディング２進データ系列（p1、p2）の関数である第２の２進データ系列（p'2）を考慮に入れて、再帰畳込み符号を復号する少なくとも１回の第２の基本動作を更に繰り返し実行することを特徴とする請求項１２乃至１６のいずれか１項に記載の復号方法。
【請求項１８】
前記第２の２進データ系列（p'2）は、第１及び第２のパディング２進データ系列（p1、p2）の関数として第２の２進データ系列（p'2）を表すあらかじめ確立された方程式系から決定されることを特徴とする請求項１７に記載の復号方法。
【請求項１９】
前記第２の２進データ系列（p'2）は、第１及び第２のパディング２進データ系列（p1、p2）の関数として第２の２進データ系列（p'2）を与え、且つ確立された恒等式の系から決定されることを特徴とする請求項１７に記載の復号方法。
【請求項２０】
元の系列を表現する系列をインタリーブする少なくとも１回のインタリーブ動作を更に繰り返し実行し、
前記第１の基本復号動作中、少なくとも１つの第１の付帯情報系列（wp1'）を判定し、
前記インタリーブ動作と並行して、第２の基本復号動作中に考慮に入れられる第１のアプリオリ情報系列（wp2）を前記第１の付帯情報系列（wp1'）の関数として計算する第１の計算動作を実行することを特徴とする請求項１７に記載の復号方法。
【請求項２１】
第１のアプリオリ情報系列（wp2）は、第１の付帯情報系列（wp1'）の関数として第１のアプリオリ情報系列（wp2）を与えるあらかじめ確立された恒等式の系から判定されることを特徴とする請求項２０記載の復号方法。
【請求項２２】
第１のアプリオリ情報系列（wp2）は、第１の付帯情報系列（wp1'）の関数として第１のアプリオリ情報系列（wp2）を与える瞬時に確立された恒等式の系から判定されることを特徴とする請求項２０記載の復号方法。
【請求項２３】
元のインタリーブ系列を表現する系列をデインタリーブする少なくとも１回のデインタリーブ動作を更に繰り返し実行し、
前記第２の基本復号動作中、少なくとも１つの第２の付帯情報系列（wp2'）を判定し、
前記デインタリーブ動作と並行して、前記第１の基本復号動作中に考慮に入れられる第２のアプリオリ情報系列（wp1）を前記第２の付帯情報系列（wp2'）の関数として計算する第２の計算動作を実行することを特徴とする請求項１７乃至２２のいずれか１項に記載の復号方法。
【請求項２４】
前記第２のアプリオリ情報系列（wp1）は、第２の付帯情報系列（wp2'）の関数として第２のアプリオリ情報系列（wp1）を与えるあらかじめ確立された方程式系から判定されることを特徴とする請求項２３に記載の復号方法。
【請求項２５】
前記第２のアプリオリ情報系列（wp1）は、第２の付帯情報系列（wp2'）の関数として第２のアプリオリ情報系列（wp1）を与える確立された恒等式の系から決定されることを特徴とする請求項２３に記載の復号方法。
【請求項２６】
前記第１のパディング２進データ系列（p1）は符号化の時点で完全にパンクチュアされており、前記第２の基本復号動作中に考慮に入れられる前記第２の２進データ系列（p'2）は前記第２のパディング２進データ系列（p2）と同一であることを特徴とする請求項１７乃至２５のいずれか１項に記載の復号方法。
【請求項２７】
前記第２のパディング２進データ系列（p2）は符号化の時点で完全にパンクチュアされており、前記第１の基本復号動作中に考慮に入れられる第１の２進データ系列（p'1）は第１のパディング２進データ系列（p1）と同一であることを特徴とする請求項１４乃至２６のいずれか１項に記載の復号方法。
【請求項２８】
請求項１１に記載の符号化装置によって前記元の２進データ系列（u）を符号化して得られた元の記号系列を復号する復号手段を有することを特徴とする復号装置。
【請求項２９】
コンピュータにより読み取り可能な情報記憶媒体であって、請求項１乃至１０のいずれか１項に記載の符号化方法をコンピュータに実行させるコンピュータプログラムを記憶したことを特徴とする情報記憶媒体。
【請求項３０】
コンピュータにより読み取り可能な情報記憶媒体であって、請求項１２乃至２７のいずれか１項に記載の復号方法をコンピュータに実行させるコンピュータプログラムを記憶したことを特徴とする情報記憶媒体。
【発明の詳細な説明】
【０００１】
本発明は、符号化方法及び装置、復号方法及び装置、並びにそれらを用いたシステムに関するものである。
【０００２】
一般的に、本発明は、割り切れるという性質を維持するインタリーバを伴う畳込み並列ターボ符号におけるパディングビットと呼ばれる２進要素（ビット）の特定の用途での利用を実現する。
【０００３】
従来より、ターボ符号器は３つの不可欠の部分、すなわち、２つの基本組織再帰畳込み符号器と、１つのインタリーバとから構成されている。
【０００４】
これに関連する復号器は畳込み符号器に対応する、いわゆるソフト入力及びソフト出力を伴う２つの基本復号器と、インタリーバと、その逆インタリーバ（「デインタリーバ」とも言う）とから構成される。
【０００５】
ターボ符号の説明については、１９９３年５月にジュネーブで開催されたICC会議の際にC. Berrou、A. Glavieux及びP. Thitimajshimaが行ったプレゼンテーションに対応する論文「Near Shannon limit error−correcting coding and decoding：turbo codes」を参照されたい。
【０００６】
符号器は組織再帰型符号器であるので、多くの場合に問題になるのが符号器のゼロ復帰である。
【０００７】
従来の技術においては、この問題に対処するために様々な方法がとられていた。そのいくつかを次に挙げる。
１．ゼロ復帰をなくす方法：符号器をヌル(null)状態に初期設定し、インタリーブなしにどのような状態へも移行できるままにする。
２．第１の符号器をゼロ復帰させる方法：符号器をヌル状態に初期設定し、第１の符号器にのみヌル最終状態を課すために、パディングビットを追加する。
３．「フレーム指向畳込みターボ符号（FOCTC）」：第１の符号器を初期設定し、第１の符号器の最終状態を第２の符号器の初期状態とする。ある特性を有するあるクラスのインタリーバを使用した場合、第２の符号器の最終状態はヌルである。この点に関しては、C. Berrou及びM. Jezequelによる論文「Frame oriented convolutional turbo−codes」（Electronics Letters,第３２刊、第１５号、１９９６年７月１８日、１３６２〜１３６４ページ、英国、Hert、Stevenage）を参照すると有益である。
４．２つの符号器の独立ゼロ復帰：符号器をヌル状態に初期設定し、それらの符号器に入力されるそれぞれの系列に独立してパディングビットを追加する。符号器の独立ゼロ復帰の概要は、D. Divsalar及びF. Pollaraによる論文「TDA progress report 42-123 On the design of turbo codes」（１９９５年１１月刊、JPL（Jet Propulsion Laboratory））に記載されている。
５．２つの符号器の固有ゼロ復帰：符号器をヌル状態に初期設定し、第１の符号器に入力する系列にパディングビットを追加する。フランス特許第A−２７７３２８７号に開示されているようなゼロ復帰を保証するインタリーバを利用し、且つパディングビットを含む系列をインタリーブする場合、第２の符号器は自動的に最終ヌル状態を有する。
【０００８】
以上挙げた従来の技術の方法は、いずれも、対応する復号器に適用される適応格子終端（trellis termination)を含む。これらの復号器は格子の終端を考慮に入れるか、又は考慮に入れず、適応可能であれば、２つの符号器がそれぞれ同じパディングビットを使用するという事実を考慮する。
【０００９】
１及び２の方法は、一般的には３から５の方法と比べて性能の点では劣っている。
【００１０】
しかし、３から５の方法にも欠点がある。
【００１１】
３の方法ではインタリーバの選択に制限があるため、性能が低下したり、インタリーバの設計が不必要に複雑になってしまうおそれがある。
【００１２】
インタリーバのサイズが小さい場合、４の方法では、５の方法と比較して性能が低下する。
【００１３】
５の方法に関しては、第２の符号器が符号化を開始できるようになる前に、パディングビットを判定することが必要である。
【００１４】
このように、従来の技術は、インタリーバのサイズが小さい場合でも、高い性能を保持し、且つ第１の符号器がパディングビットを判定する前であっても、第２の符号器が符号化を開始できるようにしつつ、
− 符号化中に、符号器を０にリセットし、且つ
− 復号中に、復号器で使用される格子を終端させることから成る問題を解決していない。
【００１５】
更に、場合によっては、符号化したいブロックのサイズに従って異なる種類のインタリーバを使用しつつ、独立した格子終端を有するコンパチビリティをもったターボ符号器又はターボ復号器構造を保持し、且つ特にブロックサイズが小さい場合に全体的に高い性能を有することが望まれるであろう。
【００１６】
本発明の目的は、上述の欠点を改善することである。
【００１７】
この目的を達成するために、本発明は、
− 第１のパディング２進データ系列により補填された元の２進データ系列が第１の除数多項式で割り切れるように選択された第１のパディング２進データ系列によって元の２進データ系列を補填することから成る少なくとも１回の第１のパディング動作を実行し、
− 第１のパディング２進データ系列により補填された元の２進データ系列を前記第１の除数多項式を使用する符号化技法によって符号化することから成る少なくとも１回の第１の再帰畳込み符号化動作を実行し、
− 元の２進データ系列の２進データをインタリーブ系列を得るように特定の置換によって置換することから成る少なくとも１回のインタリーブ動作を実行する、少なくとも１つの元の２進データ系列を符号化する方法であって、
− 特定の置換は、第１の除数多項式が多項式xNO＋１を割り切るような最小の整数をNOとし、且つ正の整数をMとするとき、元の２進データ系列の２進データがNO列、M行の配列に行ごとに書き込まれ且つ読み取られるような表現において、
生成多項式が第１の除数多項式である長さNOの巡回符号を、生成多項式が第２の除数多項式である巡回符号に変換し、元の２進データ系列を表現する配列のNO個の列を互いに置換する列間置換と、
それぞれが前記配列中の１つの列の中における記号の置換である任意の数の列内基本置換との合成であることと、
− 第２のパディング２進データ系列により補填されたインタリーブ系列が第２の除数多項式により割り切れるように選択された第２のパディング２進データ系列でインタリーブ系列を補填することから成る少なくとも１回の第２のパディング動作を実行し、且つ
− 第２のパディング２進データ系列により補填されたインタリーブ系列を第２の除数多項式を使用する符号化技法によって符号化することから成る少なくとも１回の第２の再帰畳込み符号化動作を実行することを特徴とする符号化方法を提案する。
【００１８】
従って、所定のブロックサイズに対して、
− ２つの符号器はヌル状態に初期設定され、
− 入力系列に関しては、２つの符号器の除数多項式により割り切れるという性質を維持するインタリーバのみを利用し、且つ
− 各々の符号器を０にリセットするために、各々の系列に独立してパディングビットを追加する。
【００１９】
これにより、復号時に高い性能が得られる。その結果、特に、復号中にパディングビットの間に存在する関係を利用することが可能になる。
【００２０】
特定の特徴によれば、第２のパディング２進データ系列の２進データは第１のパディング２進データ系列の２進データの知識(knowledge)からのみ判定される。
【００２１】
この特徴は符号化を簡単にすることができる。
【００２２】
第１の実施形態では、第２のパディング２進データ系列の２進データを、第１のパディング２進データ系列の関数として第２のパディング２進データ系列を表すあらかじめ作成された変換テーブルから判定することができる。
【００２３】
これにより、符号化を簡単にすることができる。
【００２４】
第２の実施形態では、第２のパディング２進データ系列の２進データを第１のパディング２進データ系列の２進データの関数として瞬時に判定することができる。
【００２５】
このことは、本発明の利用に大きな融通性を与える。
【００２６】
特定の特徴によれば、第１の除数多項式の次数に等しいデータ数を有する第１のパディング２進データ系列から第２のパディング２進データ系列を構成するために、
− NOに等しい長さの系列を得るように、第１のパディング２進データ系列を０で補填し、
− 第１のインタリーブパディング系列を得るように、列間置換によって第1のパディング２進データ系列の２進データを置換し、
− 第２の除数多項式による第１のインタリーブパディング系列の多項式除算の余りを判定し、且つ
− 前記余りを第２のパディング２進データ系列として選択する。
【００２７】
この方法により、第１のパディング２進データ系列の関数として第２のパディング２進データ系列を瞬時に計算することが可能になる。また、第１のパディング２進データ系列の関数として変換テーブルをあらかじめ構成しておくことも可能になる。更に、パディングビットを連結する方程式系を成立させるために、これを復号方法で利用することもできる。
【００２８】
特定の特徴によれば、第１の除数多項式と第２の除数多項式は同一である。
これにより、符号化を簡単にすることができる。
【００２９】
特定の特徴によれば、列間置換が恒等式置換であるとき、第２のパディング２進データ系列は第１のパディング２進データ系列と等しいものとして判定される。
【００３０】
これにより、符号化を簡単にすることができる。
【００３１】
特定の実施形態では、パディング２進データ系列の少なくとも一方はパンクチュアされる。
【００３２】
これにより、性能の損失を非常に小さく抑えて、符号効率を向上させることが可能になる。
【００３３】
パディング２進データ系列の少なくとも一方は、符号化系列が第１及び第２のパディング２進データ系列の、第１及び第２のパディング２進データ系列の全てを表現したままである部分を含むようにパンクチュアされると有利である。
【００３４】
この特徴により、高い性能を保持することが可能になる。
【００３５】
特定の特徴によれば、第１のパディング２進データ系列は完全にパンクチュアされる。
【００３６】
１つの特定の特徴によれば、第２のパディング２進データ系列は完全にパンクチュアされる。
【００３７】
上記の２つの特徴は方法を大きく単純化するという利点を有する。
【００３８】
左記に示したの同じ目的を達成するために、本発明は、
− 第１のパディング２進データ系列により補填された元の２進データ系列が第１の除数多項式で割り切れるように選択された第１のパディング２進データ系列によって元の２進データ系列を補填する少なくとも１つの第１のパディングモジュールと、
− 第１のパディング２進データ系列により補填された元の２進データ系列を第１の除数多項式を使用する符号化技法によって符号化する少なくとも１つの第１の再帰畳込み符号化モジュールと、
− 元の２進データ系列の２進データをインタリーブ系列を得るように特定の置換によって置換する少なくとも１つの第１のインタリーブモジュールとを有する、少なくとも１つの元の２進データ系列を符号化する装置であって、
− 特定の置換は、第１の除数多項式が多項式xNO＋１を割り切るような最小の整数をNOとし、且つ正の整数をMとするとき、元の２進データ系列の２進データがNO列、M行の配列に行ごとに書き込まれ且つ読み取られるような表現において、
生成多項式が第１の除数多項式である長さNOの巡回符号を、生成多項式が第２の除数多項式である巡回符号に変換し、元の２進データ系列を表現する配列のNO個の列を互いに置換する列間置換と、
それぞれが前記配列中の１つの列の中における記号の置換である任意の数の列内基本置換との合成であることと、
符号化装置は、
− 第２のパディング２進データ系列により補填されたインタリーブ系列が第２の除数多項式により割り切れるように選択された第２のパディング２進データ系列でインタリーブ系列を補填する少なくとも１つの第２のパディングモジュールと、
− 第２のパディング２進データ系列により補填されたインタリーブ系列を第２の除数多項式を使用する符号化技法によって符号化する少なくとも１つの第２の再帰畳込み符号化モジュールとを更に有することを特徴とする符号化装置を提案する。
【００３９】
この符号化装置の特定の特徴及び利点は本発明による符号化方法の特徴及び利点と同じであるので、ここでは繰り返さない。
【００４０】
同様に同じ目的を達成するために、本発明は、元の記号系列が左記に示したような符号化方法によって符号化された２進系列を表現することを特徴とする少なくとも１つの元の記号系列を復号する方法を更に提案する。
【００４１】
すなわち、独立ゼロ復帰方式を伴う符号器を処理するためのターボ復号器に類似しているが、２つのパディング系列のそれぞれに関わるアプリオリ情報を反復のたびに獲得するために、それらの系列の間の一般的関係を利用するようなターボ復号器を考える。
【００４２】
特定の特徴によれば、復号方法はソフト入力ソフト出力を伴う復号動作を使用する。
【００４３】
上記の復号方法は、高い性能を提供する符号によるターボ復号方法に特有の一般的利点を有する。
【００４４】
特定の特徴によれば、元の記号系列の第１の部分系列を第１の除数多項式を使用する復号技法によって復号し、且つ第１及び第２のパディング２進データ系列の関数である第１の２進データ系列を少なくとも考慮に入れることから成る、再帰畳込み符号を復号する少なくとも１回の第１の基本動作を繰り返し実行する。
【００４５】
特定の特徴によれば、第１の２進データ系列は、第１及び第２のパディング２進データ系列の関数として第１の２進データ系列を表すあらかじめ確立された恒等式の系から判定される。
【００４６】
上記の特徴により、パディングビットは完全に反復復号プロセスに関与することになる。また、パディングビットは十分に保護され、その他のビットよりも適切に保護されることにもなる。従って、ターボ復号の性能は向上する。
【００４７】
変形例では、第１の２進データ系列は、第１及び第２のパディング２進データ系列の関数として第１の２進データ系列を与え且つ瞬時に確立された方程式系から判定される。
【００４８】
この変形例は復号を単純化し且つスピードアップする。
【００４９】
特定の特徴によれば、元の記号系列の第１の部分系列を第２の除数多項式を使用する復号技法によって復号し、且つ第１及び第２のパディング２進データ系列の関数である第２の２進データ系列を少なくとも考慮に入れることから成り且つ再帰畳込み符号を復号する少なくとも１回の第２の基本動作を更に繰り返し実行する。
【００５０】
特定の特徴によれば、第２の２進データ系列は、第１及び第２のパディング２進データ系列の関数として第２の２進データ系列を表すあらかじめ確立された方程式系から判定される。
【００５１】
変形例として、第２の２進データ系列は、瞬時に確立された第１及び第２のパディング２進データ系列の関数として第２の２進データ系列を与える方程式系から判定される。
【００５２】
特定の特徴によれば、
− 元の系列を表現する系列をインタリーブする少なくとも１回の動作を更に繰り返し実行し、
− 第１の基本復号動作中、少なくとも１つの第１の付帯情報系列を判定し、且つ
− インタリーブ動作と並行して、第２の基本復号動作中に考慮に入れられる第１のアプリオリ情報系列を第１の付帯情報系列の関数として計算することから成る、第１の計算動作を実行する。
【００５３】
上記の特徴は、第１の基本復号動作及び第１の２進データ系列の判定に関連して述べたのと同じ利点を有する。
【００５４】
特定の特徴によれば、第１のアプリオリ情報系列は、第１の付帯情報系列の関数として第１のアプリオリ情報系列を与えるあらかじめ確立された方程式系から判定される。
【００５５】
変形例として、第１のアプリオリ情報系列は、第１の付帯情報系列の関数として第１のアプリオリ情報系列を与える瞬時に確立された方程式系から判定される。
【００５６】
特定の特徴によれば、
− 元のインタリーブ系列を表現する系列をデインタリーブする少なくとも１回の動作を更に繰り返し実行し、
− 第２の基本復号動作中、少なくとも１つの第２の付帯情報系列を判定し、且つ
− デインタリーブ動作と並行して、第１の基本復号動作中に考慮に入れられる第２のアプリオリ情報系列を前記第２の付帯情報系列の関数として計算する。
【００５７】
特定の特徴によれば、第２のアプリオリ情報系列は、第２の付帯情報系列の関数として第２のアプリオリ情報系列を与えるあらかじめ確立された方程式系から判定される。
【００５８】
変形例として、第２のアプリオリ情報系列は、第２の付帯情報系列の関数として第２のアプリオリ情報系列を与える瞬時に確立された方程式系から判定される。
【００５９】
特定の特徴によれば、第１のパディング２進データ系列は符号化の時点で完全にパンクチュアされており、第２の基本復号動作中に考慮に入れられる第２の２進データ系列は第２のパディング２進データ系列と同一である。
【００６０】
特定の特徴によれば、第２のパディング２進データ系列は符号化の時点で完全にパンクチュアされており、第１の基本復号動作中に考慮に入れられる第１の２進データ系列は第１のパディング２進データ系列と同一である。
【００６１】
先に示したのと同じ目的を達成するために、本発明は、元の記号系列が上記の符号化装置のような符号化装置によって符号化された２進系列を表現することを特徴とする少なくとも１つの元の記号系列を復号する装置を更に提案する。
【００６２】
この復号装置の特定の特徴及び利点は本発明による復号方法の特徴及び利点と同じであるので、ここでは繰り返さない。
【００６３】
本発明は、更に、先に記載したような符号化方法及び／又は復号方法を実現するための手段を有するデジタル信号処理装置にも関する。
【００６４】
本発明は、先に記載したような符号化装置及び／又は復号装置を有するデジタル信号処理装置にも関する。
【００６５】
本発明は、先に記載したような符号化方法及び／又は復号方法を実現するための手段を有する通信ネットワークにも関する。
【００６６】
本発明は、先に記載したような符号化装置及び／又は復号装置を有する通信ネットワークにも関する。
【００６７】
本発明は、先に記載したような符号化方法及び／又は復号方法を実現するための手段を有する通信ネットワークにおける移動局にも関する。
【００６８】
本発明は、先に記載したような符号化装置及び／又は復号装置を有する通信ネットワークにおける移動局にも関する。
【００６９】
本発明は、先に記載したような符号化装置及び／又は復号装置を有する、音声を表現する信号を処理する装置にも関する。
【００７０】
本発明は、先に記載したような符号化装置及び／又は復号装置及び／又は音声を表現する信号を処理する装置を有するパケット送信プロトコルを使用する送信器を有するデータ送信装置にも関する。
【００７１】
データ送信装置の特定の特徴によれば、パケット送信プロトコルはATM（「AsynchronousTransfer Mode」）型である。
【００７２】
変形例として、パケット送信プロトコルはIP（インターネットで使用される送信プロトコル、「Internet Protocol」）型である。
【００７３】
更に、本発明は、
− 先に記載したような本発明の符号化方法及び／又は復号方法を実現するためのコンピュータプログラムの命令を格納するコンピュータ又はマイクロプロセッサにより読み取り可能である情報記憶手段、及び
− 一部又は全体が出し入れ自在であり、先に記載したような本発明の符号化方法及び／又は復号方法の実現を可能にするコンピュータプログラムの命令を格納するコンピュータ又はマイクロプロセッサにより読み取り可能である情報記憶手段にも関する。
【００７４】
本発明は、先に記載したような符号化方法及び／又は復号方法を実現するための命令系列を含むコンピュータプログラムにも関する。
【００７５】
先に挙げた異なるデジタル信号処理装置、異なる通信ネットワーク、異なる移動局、音声を表現する信号を処理する装置、データ送信装置、情報記憶手段及びコンピュータプログラムの特定の特徴及び利点は本発明による符号化方法及び復号方法の特徴及び利点と同じであるので、ここでは繰り返さない。
【００７６】
本発明のその他の面及び利点は、限定的な意味を持たない以下の特定の実施形態の詳細な説明を読むことにより明らかになるであろう。以下の説明は添付の図面を参照している。
【００７７】
通常、本発明において現れる種類のターボ符号器は１／３の効率を有し、除数多項式を使用する１対の畳込み再帰符号器であると考えることができる。第１の符号器は符号化すべき記号の系列uを使用して検査系列を生成し、第２の符号器は、系列uをインタリーブすることにより得られるインタリーブ系列u*から検査系列を生成する。
【００７８】
第１の符号器の除数多項式をg1(x)とする。
【００７９】
多項式g1(x)の次数をmとし、g1(x)が多項式xNO＋１の除数であるような最小の整数をNOとする。この数NOをg1(x)の「周期(period)」という。
【００８０】
第２の符号器の除数多項式をg2(x)とする。
【００８１】
g1(x)及びg2(x)は次のような特性を有する。
【００８２】
Πi(x-xi)が２元体の拡大体におけるg1(x)の完全分解であるならば、この拡大体の自己同形写像（指数により示す）をψとするとき、g2(x)の完全分解はΠi(x-xiψ)である。以後、そのような多項式g2(x)をg1(x)とコンパチブルであるという。特に、多項式は常にそれ自身とコンパチブルである。尚、２つのコンパチブルな多項式は同じ次数、同じ周期を有する。
【００８３】
例えば、単位元の原始ｎ乗根をαとし、これが８元体に属する場合のg1(x)＝x3＋x＋１の分解g1(x)＝(x−α)(x−α2)(x−α2)を考える。この８元体の６つの自己同形写像ψi：α→αiを考える。ψ1、ψ2及びψ4はg2(x)＝g1(x)を生成し、ψ3、ψ6及びψ5は，g2(x)＝(x−α3)(x−α6)(x−α5)として分解されるg1(x)＝x3＋x＋１を生成することが立証される。
【００８４】
以下の説明中、g1(x)＝g2(x)であると仮定する。慣習により、g1(x)及びg2(x)をg(x)と表す。
【００８５】
NOの倍数をｎとする。ここで、Mを整数とするとき、ｎ＝M・NOである。
【００８６】
第１の符号器は、長さｎの符号化すべき２進情報シンボルの系列uから、そのゼロ復帰を保証するパディングビットと、検査系列とを生成する。
【００８７】
シンボルの系列uは、２進係数を伴う、次数n−１の多項式表現u(x)を有する。
【００８８】
すなわち、第１の符号器は系列ａ1(x)=u(x)+Σi=0m-1p1ixi+nを系列v1(x)＝a1(x)・h1(x)／g(x)として符号化する。式中、
− h1(x)及びg(x)は互いに素である２つの多項式であり、
− m個の２進シンボルp1i（パディングビット）は、a1(x)がg(x)の倍数となるように選択される。
【００８９】
更に、系列u(x)は、g(x)で割り切れるという性質を維持する置換によって系列u*(x)にインタリーブされる。
【００９０】
これらの置換は、除数多項式g(x)がxNO＋１を割り切るような最小の整数をNOとするとき、系列uの２進データがNO列、M行の配列に行ごとに書き込まれ、読み取られるような表現において、
− aiを表現する配列のNO列に置換によって作用を及ぼす、長さNOの巡回符号及び生成多項式g(x)の列間置換、自己同形写像と、
− それぞれが前記配列における１つの列の記号の何らかの置換である任意の数の列内基本置換の合成である。
【００９１】
第２の符号器は系列ａ2(x)=u*(x)+Σi=0m-1p2ixi+nを系列v2(x)＝a2(x)・h2(x)／g(x)として符号化する。式中、
− h2(x)及びg(x)は互いに素である２つの多項式であり、
− m個の２進記号p2ｉ（パディングビット）は、a2(x)がg(x)の倍数となるように選択される。
【００９２】
総じて、ターボ符号器は系列u、p1(＝Σi=0m-1P1ixi)、p2(=Σi=0m-1p2ixi)、v1及びv2を生成し、それらの系列はチャネルを介して送信される。
【００９３】
そこで、パディングビットは、インタリーバにのみ依存する線形方程式により、更に厳密に言えば、このインタリーバを記述する配列中のNO列を置換する合成置換にのみ依存する線形方程式により互いに連結される。
【００９４】
一例として、以下では、1＋x2＋x3に等しい除数多項式g(x)を考える。その周期NOは７に等しい。
【００９５】
１４７ビット（n＝１４７）の符号化すべき系列と、共に1＋x＋x3に等しい多項式h1(x)及びh2(x)とを考える。
【００９６】
変形例として、２つのパディング系列の間に線形関係が存在することから、パディング系列を部分的にパンクチュアすることも可能である。
【００９７】
このような条件の下で、g(x)で割り切れるという性質を維持するインタリーバは、７の倍数である大きさを有していなければならない。すなわち、データを行ごとに７列の配列に書き込む場合、置換データを行ごとに読み取る前に、g(x)で割り切れるという性質を維持するいくつかの条件に従って、各列内のそれらのデータを何らかの方式で置換することや列を互いに置換することができる。
【００９８】
列を０から６まで順に番号付けすると、番号b0の列を番号b1へ、番号b1の列を番号b2へ、・・・番号bkの列を番号b0へ移動させる置換は(b0，b1，．．．，bk)と表される。
【００９９】
２つの置換(c0，c1，．．．，ck)及び(d0，d1，．．．，dk')の合成は(c0，c1，．．．，ck)(d0，d1，．．．，dk')と表される。
【０１００】
以下の表Ｔは、g(x)で割り切れるという性質を維持する１６８の列間置換のリストを示す。
【０１０１】
0004508407.tif 000002
0004508407.tif 000003
0004508407.tif 000004
表Ｔ
使用するのが簡単なインタリーバは、例えば、次のように定義される「xからx32」インタリーバである。入力系列をｕとし、置換系列をu*とするとき、このインタリーバはuの位置ｉにある各ビットをu*の位置（３２・ｉモジュロ４７）へ置換する。
【０１０２】
このインタリーバは、（ｉ）上記の列間置換の表に現れている列間置換   と、（ii）列内置換との合成によって得られる。すなわち、このインタリーバは使用するのが簡単なままで、gにより割り切れるという性質を維持しているのである。
【０１０３】
通常、２モジュロｎの累乗をｅとするとき、「xからxe」の形態のインタリーバを使用することが可能である。
【０１０４】
これらのインタリーバは次のように定義される。
【０１０５】
入力系列をuとし、置換系列をu*とすると、インタリーバは、当初はuの位置ｉにあった各ビットをu*の位置（e・iモジュロn）へ置換する。
【０１０６】
符号化すべき各系列u及びu*に、３つのパディングビットが追加されるので、符号化すべき各系列と、それと関連する３つのパディングビットの系列との連結によって、そのようにして得られた各系列を符号化する各々の符号器のゼロ復帰が保証される。
− 第１の符号器により系列uに追加されるパディング系列をp1＝(p10，p11，p12)と表す。
− 第２の符号器により系列u*に追加されるパディング系列をp2＝(p20，p21，p22)と表す。
− 第１の符号器から発行されるパリティ系列をv1とし、
− 第２の符号器から発行されるパリティ系列をv2とする。
【０１０７】
系列(u，v1，v2，p1，p2)を送信する。
【０１０８】
次に、パディングビットの間に存在する関係を説明する。
【０１０９】
a1(x)はu(x)＋p1(x)・xnに等しく、g(x)で割り切れる。
【０１１０】
系列a1(x)をu*(x)＋p”1(x)・xnに等しい系列a1'(x)に変換する置換を考える。
【０１１１】
系列uを系列u*に置換し、ここでは、７ビットの系列に作用するグローバル置換を定義するために使用される列間置換Π＝（１ ４ ２）（３ ５ ６）を考える。
【０１１２】
系列p”1は[p10 p11 p12 ０ ０ ０ ０]に等しい７ビットに拡張された系列p1の置換Πにより得られる。
【０１１３】
すなわち、p”1(x)＝p10＋p11・x4＋p12・x＝p10＋p12・x＋p11・x4となる。
【０１１４】
構成上、置換Πはg(x)で割り切れるという性質を維持する置換である。すなわちa1'(x)はg(x)で割り切れる。
【０１１５】
p”1モジュロg(x)の余りはp”(x)＝(p10＋p11)＋(p10＋p12)・x＋p11・x2に等しい。
【０１１６】
従って、u*(x)＋p”(x)・xnに等しい系列a”(x)もg(x)で割り切れる。
【０１１７】
更に、a2(x)はu*(x)＋p2(x)・xnに等しく、g(x)で割り切れる。
【０１１８】
gは３次であり、p”及びp2は２次であるので、p”とp2とは等しい。
【０１１９】
そこから、p1とp2との間に、符号器のゼロ復帰を保証するインタリーバの列の置換にのみ依存する次のような関係が推論される。すなわち、この場合、Π＝（１ ４ ２）（３ ５ ６）で、
p20＝p10＋p11
p21＝p11＋p12
p22＝p11
この方程式の系は可逆である。すなわち、p1をp2の関数として求めることも容易である。
【０１２０】
この手続き方式は、gで割り切れるという性質を維持する列に作用する置換のたびに適用可能である。パディングビットを連係する方程式の求め方を次のように一般化することができる。
【０１２１】
− まず、帰還多項式g(x)の周期に等しい長さを持つ系列を得るために、第1のパディング系列p1を0で補填し、
− 次に、uをu*に変換するために定義された列に作用する合成置換によってパディング系列p1をインタリーブすることにより得られる系列p1”を判定し、
− 最後に、p1”モジュロgの余りを計算する。
【０１２２】
列間置換が恒等写像である特定のケースにおいては、系列p1とp2とは同一である。
【０１２３】
変形例として、系列(u、v1、v2、pp)を送信することによりパディング系列をパンクチュアする。ここで、ppはp1及びp2のパディングビットを含むが、p1及びp2のビットとは線形独立な組み合わせ、更に一般的に言えば、第1及び第2のパディング系列p1及びp2の部分であって、それら２つの系列を表現している部分、すなわち、２つの系列全体を見出すことを可能にする部分を含むのが有利である。
【０１２４】
第1のパディングビットの系列p1をその全体としてパンクチュアするか、又は第2のパディングビットの系列p2をその全体としてパンクチュアするかのいずれかとするのが好ましい。
【０１２５】
次に、ターボ復号器の概要を説明する。
【０１２６】
ターボ復号は当業者には良く知られた反復動作である。詳細については、
− J. Hagenauer、E. Offer及びL. Papkeによる論文「Iterative decoding of binary block and convolutional codes」（IEEE Transactions on Information Theory、１９９６年３月）、
− J. Hagenauer、P. Robertson及びL. Papkeによる論文「Iterative （turbo） decoding of systematic convolutional codes with the MAP and SOVA algorithms」（Informationstechnische Gesellschaft （ITG） Fachbericht、２１から２９ページ、１９９４年１０月）、及び
− １９９６年８月にTechnology Institute of Lund （Department of Applied Electronics）（スウェーデン）により催されたセミナー「Turbocoding」の議事録と共に発行されたC Berrou、S. Evano及びG. Battailによる論文「Turbo−block−codes」を参照すると有益である。
【０１２７】
しかしながら、従来の技術においては、パディングビットを連係させる特定の関係は存在していない。この場合、復号品質を最適にするために、ターボ復号器は、p1及びp2についてのアプリオリ情報を利用できる対応する基本復号器と、p1及びp2についての付帯情報が供給されるその出力の双方に関してp1及びp2を連係させる方程式系を使用する。
【０１２８】
次に、図１から図８を参照して、本発明の特定の一実施形態を説明する。
【０１２９】
図１は、ネットワークステーション又はコンピュータ符号化ステーションの構成をブロック線図の形態で概略的に示す。
【０１３０】
このステーションはキーボード１１１と、画面１０９と、外部情報源１１０と、無線送信器１０６とを有し、これらは全て処理カード１０１の入出力ポート１０３に接続している。
【０１３１】
処理カード１０１は、
− 中央処理装置１００と、
− ランダムアクセスメモリＲＡＭ１０４と、
− 読み取り専用メモリＲＯＭ１０５と、
− 入出力ポート１０３とを有し
これらはアドレス／データバス１０２より互いに接続されている。
【０１３２】
図１に示す要素はマイクロコンピュータ及び送信システム、より一般的には情報処理システムの分野の当業者にはそれぞれ良く知られている。従って、これらと共通の要素についてはここでは説明しないが、
− 情報源１１０は、例えば、インタフェース周辺装置、センサ、変復調器、外部メモリ又はその他の情報処理システム（図示せず）であり、音声、サービスメッセージ又はマルチメディアデータを表現する信号の系列を２進データの系列の形態で供給するものであると有利であり、且つ
− 無線送信器１０６は無線チャネルを介してパケット送信プロトコルを実現し、それらのパケットを無線チャネルを介して送信するものであることに注意すべきである。
【０１３３】
また、以下の説明中に使用される「レジスタ」という用語は、メモリ１０４及び１０５の各々において、容量の小さい（若干の２進データを格納する）メモリ領域と、容量の大きい（プログラム全体の格納を可能にする）メモリ領域の双方を指していることもわかるであろう。
【０１３４】
ランダムアクセスメモリ１０４はデータ、変数及び中間処理結果を、説明の中では格納しているデータと同じ名称を付されたメモリレジスタに格納する。ランダムアクセスメモリ１０４は、特に、
― 情報源１１０から入力してくる２進データを系列uの形態で、バス１０２への到着順に格納するレジスタ「source＿data」と、
− レジスタ「source＿data」の２進データの数に対応する整数を格納するレジスタ「N0＿data」と、
− 以下に図５を参照して説明する置換２進データを系列u*の形態でバス１０２への到着順に格納するレジスタ「permuted＿data」と、
− 送信すべき系列を格納するレジスタ「data＿to＿send」とを含む。
【０１３５】
読み取り専用メモリ１０５は、便宜上、格納しているデータと同じ名称を付されたレジスタにデータを格納する。すなわち、
− 中央処理装置１００の演算プログラムをレジスタ「program」に格納し、
− 系列gをレジスタ「g」に格納し、
− g(x)の次数mをレジスタ「m」に格納し、
− 系列h1をレジスタ「h1」に格納し、
− 系列h2をレジスタ「h2」に格納し、
− NOの値をレジスタ「NO」に格納し、
− nの値をレジスタ「n」に格納し、
− インタリーバを定義する配列をレジスタ「interleaver」に格納する。
【０１３６】
ＲＯＭ１０５のデータは、例えば、フロッピーディスク、ＣＤ−ＲＯＭ又はＤＶＤなどの出し入れ自在の記憶媒体から得られる。
【０１３７】
中央処理装置１００は図５に示す流れ図を実現する。
【０１３８】
図２からわかるように、本発明による並列畳込みターボ符号に対応する符号化装置は、特に、
− 情報源１１０が供給する送信すべき、すなわち、「符号化すべき」２進シンボルの系列uである、符号化すべき記号の入力２０１と、
− 系列uから、系列uを表現する２つのシンボルの系列p1及びv1を供給する第１の符号器２０２と、
− 系列uから、系列uのシンボルを異なる順序で含むインタリーブ系列u*を供給するインタリーバ２０３と
− インタリーブ系列u*から、インタリーブ系列u*を表現する２つのシンボルの系列p2及びv2を供給する第２の符号器２０４とを有する。
【０１３９】
変形例では、先に説明したように、列間置換Πを使用して、又はより好ましくはp1の係数としてp2を与える変換テーブルを使用して、計算によって系列p1の知識(knowledge)からのみ系列p2を判定することができる。この変換テーブルはあらかじめ作成されている。
【０１４０】
その後、５つの系列u、v1、v2、p1及びp2は復号のために送信される。
【０１４１】
以下の説明中、好ましいインタリーバとしてサイズが１４７の「x to x32」型のインタリーバを考えるが、本発明はこの型のインタリーバには限定されず、更に一般的にg(x)により割り切れるという特性を維持するあらゆるインタリーバに関する。
【０１４２】
図３は、ネットワークステーション又はコンピュータ復号ステーションの構成をブロック線図の形態で概略的に示したものである。
【０１４３】
このステーションはキーボード３１１と、画面３０９と、外部情報先３１０と、無線受信器３０６とを有し、これらは全て処理カード３０１の入出力ポート３０３に接続している。
【０１４４】
処理カード３０１は、
− 中央処理装置３００と、
− ランダムアクセスメモリＲＡＭ３０４と、
− 読み取り専用メモリＲＯＭ３０５と、
− 入出力ポート３０３とを有し
これらはアドレス／データバス３０２により互いに接続されている。
【０１４５】
図３に示す要素はマイクロコンピュータ及び送信システム、より一般的には情報処理システムの分野の当業者にはそれぞれ良く知られている。従って、これら共通の要素についてはここでは説明しないが、
− 情報先３１０は、例えば、インタフェース周辺装置、表示装置、変調器、外部メモリ又はその他の情報処理システム（図示せず）であり、音声、サービスメッセージ又はマルチメディアデータを表現する信号の系列を２進データの系列の形態で受信するものであると有利であり、且つ
− 無線受信器３０６は無線チャネルを介してパケット送信プロトコルを使用し、それらのパケットを無線チャネルを介して受信するものであることに注意すべきである。
【０１４６】
尚、以下の説明中に使用される「レジスタ」という用語は、メモリ３０４及び３０５の各々において、容量の小さい（若干の２進データを格納する）メモリ領域と、容量の大きい（プログラム全体の格納を可能にする）メモリ領域の双方を指していることに注意すべきである。
【０１４７】
ランダムアクセスメモリ３０４はデータ、変数及び中間処理結果を、説明の中では格納しているデータと同じ名称を付されたメモリレジスタに格納する。ランダムアクセスメモリ３０４は、特に、
− 送信チャネルから送信されて来る２進データの、信頼性の測定値と等価であるソフト評価をバス３０２への到着順に系列の形態で格納するレジスタ「received＿data」と、
− 所定の時点で、系列u、p1、及びp2に対応する付帯情報及びアプリオリ情報を格納するレジスタ「extrinsic＿inf」と、
− 所定の時点で、図４を参照して以下に説明するように本発明の復号装置により出力として供給される評価系列U^を格納するレジスタ「estimated＿data」と、
− 図４を参照して以下に説明するように受信系列uに関して復号装置により実行される反復のカウンタに対応する整数を格納するレジスタ「No＿iteration」と、− レジスタ「received＿data」の２進データの数に対応する整数を格納するレジスタ「No＿data」とを含む。
【０１４８】
読み取り専用メモリ３０５は、便宜上、格納しているデータと同じ名称を付されたレジスタにデータを格納する。すなわち、
− 中央処理装置３００の演算プログラムを格納するレジスタ「Program」、
− 系列gを格納するレジスタ「g」、
− g(x)の次数mを格納するレジスタ「m」、
− 系列h1を格納するレジスタ「h1」、
− 系列h2を格納するレジスタ「h2」、
− NOの値を格納するレジスタ「NO」、
− nの値を格納するレジスタ「n」、
− インタリーバ及びその逆インタリーバを定義する配列を格納するレジスタ「Interleaver」を有する。
【０１４９】
ＲＯＭ３０５のデータは、例えば、フロッピーディスク、ＣＤ−ＲＯＭ又はＤＶＤなどの出し入れ自在の記憶媒体により得られる。
【０１５０】
中央処理装置３００は図６に示す流れ図を実現する。
【０１５１】
図４からわかるように、復号装置は、特に、
− u、v1、v2、p1及びp2を表現する５つの系列の入力４０１、４０２、４０３、４１０及び４１１（便宜上、これら５つの系列から構成される受信系列はrで示される）と、
− 符号器２０２（図２）に対応する第１のソフト入出力復号器４０４とを有する。
【０１５２】
第１の復号器４０４は入力として、
− 系列u及びv1と、
− 以下に定義する系列p'1と、
− 以下に定義する２つのアプリオリ情報系列w4及びwp1とを受信する。
【０１５３】
第１の復号器４０４は出力として、
− ２つの付帯情報系列w1及びwp1'を供給すると共に、
− 推定系列u^を出力端子４１６で供給する。
【０１５４】
図４に示す復号装置は、更に、
− 符号化装置で使用されるインタリーバ２０３により定義されるのと同じ置換に基づき、入力として系列u及びw1を受信し、それらを２つの系列u*及びw2へとそれぞれインタリーブするインタリーバ４０５（図４には「Interleaver Π」として示されている）と、
− 付帯情報wp1'からアプリオリ情報wp2を判定する演算装置４１２と、
− 符号器２０４に対応する第２のソフト入出力復号器４０６とを有する。
【０１５５】
この第２の復号器４０６は入力として、
− 系列w2、wp2、p'2、u*及びv2を受信する。
【０１５６】
第２の復号器４０６は出力として、
− ２つの付帯情報系列w3及びwp2'と、
− 推定系列u^*とを供給する。
【０１５７】
図４に示す復号装置は、更に、
− インタリーバ４０５の逆であり、入力として系列u^*を受信し、出力として推定系列u^を出力端子４０９から供給する（この推定は出力端子４１６において供給される、先に半反復された推定と比較して改善されている）デインタリーバ４０８（図４では「Interleaver Π-1」として示されている）と、
− インタリーバ４０５の逆であり、入力として付帯情報系列w3を受信し、出力としてアプリオリ情報系列w4を供給するデインタリーバ（同様に、図４では「Interleaver Π-1」として示されている）４０７と、
− 系列p1及びp2から系列p'1を判定する演算装置４１４と、
− 系列p1及びp2から系列p'2を判定する演算装置４１５と、
− 付帯情報wp2'からアプリオリ情報wp1を判定する演算装置４１３と、
− デインタリーバ４０８の出力として復号装置が推定系列u^を供給する出力４０９とを有する。
【０１５８】
所定の回数の反復に続いて、推定系列u^のみを考慮に入れる（先に引用した論文「Near Shannon limit error−correcting coding and decoding：turbocodes」を参照）。
【０１５９】
ここで説明する好ましい実施形態では、復号器４０４及び４０６を初期設定するとき、符号器２０２及び２０４がそれぞれヌルの初期状態及び最終状態を有しているという事実を考慮する。
【０１６０】
図５は、図１に示す電子装置に含まれるような符号化装置の機能を示す。図５からわかるように、ランダムアクセスメモリ１０４のレジスタが初期設定される（No＿data＝「０」）初期設定処理５００の後、処理５０１中で、中央装置１００は受信するまで待機し、その後、送信すべき２進データ項目を受信し、それをランダムアクセスメモリ１０４のレジスタ「source＿data」に格納し、カウンタ「No＿data」を１単位増分する。
【０１６１】
次に、検査５０２中には、中央装置１００は、レジスタ「No＿data」に格納されている整数がn（読み取り専用メモリ１０５に格納されている値）と等しいか否かを判定する。
【０１６２】
検査５０２の結果が否定であれば、処理５０１を繰り返す。
【０１６３】
検査５０２の結果が肯定である場合には、処理５０８で、第１の符号器２０２（図２）はパディング系列p1と、系列uと系列p1を連結することにより得られる２進データの系列と関連する多項式a(x)のg(x)による除算（p1はこの除算の余りが0になるように定められている）と、この除算の結果とh1(x)との積とを同時に判定する。系列u、p1及びこの演算の結果v1をメモリのレジスタ「data＿to＿send」に格納する。
【０１６４】
処理５０８と並行して、処理５０６で、系列uの２進データは、読み取り専用メモリ１０５に格納されている配列「interleaver」により記述される順序で、レジスタ「received＿data」に順次読み込まれる。この読み込みから順次結果として得られるデータはランダムアクセスメモリ１０４のレジスタ「permuted＿data」のメモリに格納される。
【０１６５】
次に、処理５１０で、第２の符号器２０４はパディング系列p2と、系列u*と系列p2を連結することにより得られる２進データの系列と関連する多項式b(x)のg(x)による除算（p2はこの除算の余りが0になるように定められている）と、この除算の結果とh2(x)との積とを同時に判定する。系列p2及びこの演算の結果v2をメモリのレジスタ「data＿to＿send」に格納する。
【０１６６】
処理５０９中、系列u、p1、p2、v1及びv2は、この目的のために、送信器１０６を使用して送信される。次に、メモリ１０４のレジスタを再び初期設定する（ステップ５００に戻る）。特に、カウンタNo＿dataを「０」にリセットする。次に、処理５０１を再び繰り返す。
【０１６７】
変形例では、処理５０９中に、系列u、p1、p2、v1及びv2の全体を送信するのではなく、その部分集合のみを送信することである。この変形例はパンクチュアなどの分野の当業者には知られている。通常、パディングを伴うビットはパンクチュアされない。この場合、g(x)により割り切れるという性質を維持するインタリーバによって、パディングビットの間の関係を成立させることが可能である。従って、ある数のパディングビットをパンクチュアし、それらのビットの部分集合のみを送信することができるのである。系列p1及びp2に対し線形に依存していないが、依然としてそれらの系列を表現したままであるパディングビットの集合のみを送信すると有利である。言い換えれば、送信されるパディングビットの知識のみが全ての系列p1及びp2を再構成する上で必要であり、且つそれで十分である。
【０１６８】
図６は、図３に示す電子装置に含まれるような復号装置の機能を示す。図６からわかるように、ランダムアクセスメモリ３０４のレジスタを初期設定する（No＿data＝「０」）初期設定処理６００の後、処理６０１で、中央装置３００は受信するまで待機し、次に、送信器１０６により送信され、受信器３０６により受信されるデータ項目の信頼性の測定値に対応するソフト形態のデータ項目を受信し、それをランダムアクセスメモリ１０４のレジスタ「received＿data」に格納し、カウンタ「No＿data」を１単位増分する。
【０１６９】
次に、検査６０２で、中央装置３００は、レジスタ「No＿data」に格納されている整数が３n＋２m（n及びmは読み取り専用メモリ３０５に格納されている値である）に等しいか否かを判定する。尚、３n＋２mは送信器１０６により送信される２進データの総数である。
【０１７０】
検査６０２の結果が否定であれば、処理６０１を繰り返す。
【０１７１】
検査６０２の結果が肯定である場合には、以下に詳細に説明するターボ復号処理６０３中に、復号装置は送信系列uの推定u^を提供する。
【０１７２】
次に、処理６０４中に、中央装置３００はこの推定u^を情報宛先３１０に供給する。
【０１７３】
次に、メモリ３０４のレジスタを再び初期設定する。特に、カウンタNo＿dataを「０」にリセットし、処理６０１を再び繰り返す。
【０１７４】
ターボ復号動作６０３を詳細に示す図７からわかるように、初期設定処理７００中、ランダムアクセスメモリ３０４のレジスタが初期設定される。すなわち、カウンタNo＿data及びアプリオリ情報w2、w4、wp1及びwp2が０にリセットされる（ここでは、情報源のエントロピーが０であると仮定している）。更に、インタリーバ４０５は入力系列uをインタリーブし、系列u*を供給する。この系列u*はレジスタreceived＿dataに格納される。
【０１７５】
次に、処理７０１中に、演算装置４１４及び４１５が系列p2及びp1から系列p'1及びp'2をそれぞれ計算し、それらをレジスタreceived＿dataに格納する。
【０１７６】
次に、処理７０２中に、レジスタNO＿iterationを１単位増分する。
【０１７７】
次に、処理７０３中に、第１の復号器４０４（第１の基本符号器２０２に対応する）は、先に述べたBJCR、又はSOVA（「Soft Output Viterbi Algorithm」）などの、当業者には良く知られている「ソフト入力ソフト出力（SISO）」型のアルゴリズムを実現する。この場合、符号器のヌル初期状態及び最終状態を考慮に入れて、第１の復号器４０４は、ソフト入力として、受信系列u及びv1、系列p'1、並びに系列wp1及びw4（それぞれ、p1及びuについてのアプリオリ情報である）の推定を考慮し、一方では、wp1'及びw1（それぞれ、wp1'及びuについての付帯情報である）を供給し、他方では、系列uの推定u^を供給する。
【０１７８】
ターボ符号で使用される復号アルゴリズムの詳細については、
− ターボ符号に関連して一般に使用されるいわゆる「BCJR」アルゴリズムを説明しているL. R. Bahl、J. Cocke、F. Jelinek及びJ. Ravivによる論文「Optimal decoding of linear codes forminimizing symbol error rate」（IEEETransactions on Information Theoryに掲載、１９７４年３月）、又は
− IEEE GLOBECOM会議の議事録と同時に刊行されたJ.Hagenauer及びP. Hoeherによる論文「A Viterbi algorithm with soft decisionoutputs and its applications」（１６８０〜１６８６ページ、１９８９年１１月）を参照のこと。
動作７０５中に、インタリーバ４０５はu*についてのアプリオリ情報であるw2を生成するために、系列w1をインタリーブする。
【０１７９】
これと並行して、処理７０４中に、演算装置４１２は系列wp1'から系列wp2を計算する。
【０１８０】
次に、処理７０６中に、第２の復号器４０６（第２の基本符号器２０４に対応する）はソフト入力ソフト出力型のアルゴリズムを使用する。この場合、符号器のヌル初期状態及び最終状態を考慮して、第２の復号器４０６は、ソフト入力として、受信系列u*及びv2、系列p'2、並びに系列wp2及びw2（それぞれ、p2及びuについてのアプリオリ情報である）の推定を考慮し、一方では、wp2'及びw3（それぞれ、p2及びu*についての付帯情報である）を供給し、他方では、系列u*の推定u^*を供給する。
【０１８１】
処理７０８中に、デインタリーバ４０７（４０５の逆インタリーバ）は、uについてのアプリオリ情報であるw4を生成するために、情報系列w3をデインタリーブする。
【０１８２】
これと並行して、処理７０７中に、演算装置４１３は系列wp2'から系列wp1を計算する。
【０１８３】
ステップ７０３、７０４、７０６及び７０７中に生成される付帯情報及びアプリオリ情報は、ＲＡＭ３０４のレジスタ「extrinsic＿inf」に格納される。
【０１８４】
次に、検査７０９中、中央装置３００は、レジスタ「NO＿iteration」に格納されている整数がＲＯＭ３０５のレジスタ「max＿NO＿iteration」に格納されている、実行すべき所定の最大反復回数と等しいか否かを判定する。
【０１８５】
検査７０９の結果が否定であれば、処理７０２を繰り返す。
【０１８６】
検査７０９の結果が肯定である場合には、処理７１０中に、デインタリーバ４０８（デインタリーバ４０７と同一である）は、中央装置３００にデインタリーブ系列を供給するために、系列u^*をデインタリーブする。そこで、中央装置３００はソフト決定をuの推定である系列u^の形態のハード決定に変換する。
【０１８７】
次に、復号装置内部で実行される、本発明に特有の計算処理７０１、７０４及び７０７を詳細に説明する。
【０１８８】
この目的のために、符号化装置の詳細な説明で挙げた例を再び取り上げて、対応する復号装置を考えてみることにする。
【０１８９】
先に説明した例においては、パディングビットは次の２つの等価の方程式系のいずれか一方により連結されることがわかっている。
(１)p20＝p10＋p11
p21＝p11＋p12
p22＝p11
(２)p10＝p20＋p22
p12＝p22＋p21
p11＝p22
これらの関係は、パディングビット間の相互関係を説明した項に関連して先に説明した方法に従ってあらかじめ定めておくことができる。
【０１９０】
復号装置の側では、p1及びp2の推定しか存在しておらず、復号器４０４及び４０６はp2及びp1を共に利用する。
【０１９１】
従って、復号器４０４はp1又はp2について有している情報を直接には取り出さず、p'1を使用する。
【０１９２】
同様に、復号器４０６はp1又はp2について有している情報を直接には取り出さず、p'2を使用する。
【０１９３】
演算装置４１３及び４１４は系(２)を使用する。これは瞬時に計算できるが、wp2'からwp1を判定し且つp1及びp2からp'1を判定するために、変換テーブルの形でメモリに格納されるのが好ましい。しかしながら、wp1、wp2'、p2及びp'1はソフト情報であり、通常尤度比対数(likelihood ratio logarithms)に対応することに注意すべきである。そこで、平凡であるとは言えないが、復号器の分野の当業者には良く知られている方法に従ってソフト情報の追加を行うために注意を払う。例えば、J. Hagenauerの論文「Source controlled channel decoding」の中の一章「Likelihoodalgebra of a binary random variable」（IEEE Transactions on Communications第４３巻第９号、１９９５年９月）を参照されたい。
【０１９４】
同様に、演算装置４１２及び４１５は系(１)を使用する。これは瞬時に計算できるが、wp1'からwp2を判定し且つp1及びp2からp'2を判定するために、変換テーブルの形でメモリに格納されるのが好ましい。
【０１９５】
変形例として、符号化動作中にパディングビットがパンクチュアされている場合、それらのビットのソフト入力は0の値に初期設定される。系列p1が完全にパンクチュアされていれば、第２の復号器４０６の入力p'2はp2と同一になる。逆に、系列p2が完全にパンクチュアされていれば、第１の復号器４０４の入力p'1はp1と同一になる。
【０１９６】
より一般的な別の変形例においては、本発明は２つの符号器から構成されるターボ符号器又は入力が１つのターボ符号器には限定されず、冒頭で挙げたD. Divsalar及びF. Pollaraによるレポートに記載されているような、いくつかの基本符号器から構成されるターボ符号器又はいくつかの入力を伴うターボ符号器にも適用できる。
【０１９７】
この場合、使用されるインタリーバは使用される１つ又は複数の生成多項式により割り切れるという性質を確実に維持し、且つ基本符号器は0状態に初期設定され、パディングビットによって０に復帰し、パディングビットはインタリーブされないことが保証される。そこで、それらのパディングビットを連結する関係を成立させ、その関係を復号装置において先に開示したのと同じように利用することが可能になる。
【０１９８】
図８は、本発明によるいくつかの入力u1、u2、...uk−1、ukを伴うターボ符号器を有する符号化装置を示す。
【０１９９】
図中符号８０１から８０４により示されるインタリーバI1、I2、...、Ik−1、Ikは、符号器８０５及び８０６で使用される帰還多項式g(x)により割り切れるという性質を維持する。
【０２００】
パディング系列p1及びp2はインタリーブされない。
【０２０１】
１つの入力と、１つのインタリーバを考慮する場合に先に示した復号装置の説明に基づいて、符号化装置の説明から対応する復号装置を容易に導き出すことができる。
【図面の簡単な説明】
【図１】本発明の特定の一実施形態による符号化装置を含む電子装置を概略的に示す図である。
【図２】本発明の特定の一実施形態による並列畳込みターボ符号に対応する符号化装置をブロック線図の形態で概略的に示す図である。
【図３】本発明の特定の実施形態による復号装置を含む電子装置を概略的に示す図である。
【図４】本発明の特定の一実施形態による並列畳込みターボ符号に対応する復号装置をブロック線図の形態で概略的に示す図。
【図５】特定の実施形態による、図１の電子装置に含まれるような符号化装置の機能を概略的に示す流れ図である。
【図６】本発明の特定の一実施形態による、図３の電子装置に含まれるような復号装置により実現される復号動作を概略的に示す流れ図である。
【図７】本発明の特定の一実施形態による、図６の流れ図に含まれるターボ復号動作を概略的に示す流れ図である。
【図８】本発明の変形実施形態による、いくつかの入力を含む畳込みターボ符号に対応する符号化装置を概略的に示す図である。
【図１】
0004508407.tif 000005
【図２】
0004508407.tif 000006
【図３】
0004508407.tif 000007
【図４】
0004508407.tif 000008
【図５】
0004508407.tif 000009
【図６】
0004508407.tif 000010
【図７】
0004508407.tif 000011
【図８】
0004508407.tif 000012