(57)【特許請求の範囲】
【請求項１】
並列連結コンボルーション符号化方法であって、
該方法は、
ａ）並列連結に接続された複数個（Ｎ個）の成分符号化器と（Ｎ−１）個のインターリーブ装置とを含む並列連結符号化器にデータ・ビットのブロックを提供するステップと、
ｂ）該データ・ビットのブロックにテイルバイティング非再帰的系統的コンボルーション・コードを適用することによって、該データ・ビットのブロックを該Ｎ個の成分符号化器のうちの第１の成分符号化器において符号化し、それによって、該データ・ビットとパリティ・ビットとを含む対応する第１の成分コードワードを生成するステップと、
ｃ）該データ・ビットのブロックをインターリーブすることにより、並べ換えられたデータ・ビットのブロックを提供するステップと、
ｄ）該並べ換えられたデータ・ビットのブロックにテイルバイティング非再帰的系統的コンボルーション・コードを適用することによって、該並べ換えられたデータ・ビットのブロックを第２の成分符号化器において符号化し、それによって、該データ・ビットとパリティ・ビットとを含む対応する第２の成分コードワードを生成するステップと、
ｅ）該並べ換えられたデータ・ビットのブロックをインターリーブすることにより、次の並べ換えられたデータ・ビットのブロックを提供するステップと、
ｆ）該次の並べ換えられたデータ・ビットのブロックにテイルバイティング非再帰的系統的コンボルーション・コードを適用することによって、該次の並べ換えられたデータ・ビットのブロックを後続の成分符号化器において符号化し、それによって、該データ・ビットとパリティ・ビットをと含む対応する後続の成分コードワードを生成するステップと、
ｇ）ステップｅ）とｆ）とを残りの（Ｎ−３）個のインターリーブ装置と残りの（Ｎ−３）個の成分符号化器とに対して繰返し、それによって、該データ・ビットとパリティ・ビットとを含む成分コードワードを生成するステップと、
ｈ）該成分コードワードのビットをフォーマットすることにより、合成コードワードを提供するステップと
を包含する、方法。
【請求項２】
連結コンボルーション・コードを復号する方法であって、
該方法は、
連結符号化器においてデータ・ビットのブロックにテイルバイティング非再帰的系統的コンボルーション・コードを適用することによって生成された複数個（Ｎ個）の成分コードワードからのフォーマットされたビットの集合を含む合成コードワードを、チャネルから受信し、該受信した合成コードワードから受信成分コードワードを形成するステップであって、それぞれの受信成分コードワードは、合成復号器の複数個（Ｎ個）の成分復号器のうちの対応する１つによってそれぞれ受け取られ、それぞれの成分復号器はまた、該データ・ビットの値に対する１組の先験的ソフト判定情報を受け取る、ステップと、
該Ｎ個の成分復号器と（Ｎ−１）個のインターリーブ装置とに対する繰返し過程によって、該受信成分コードワードを復号することにより、該合成復号器からのソフト判定出力を提供するステップであって、該Ｎ個の成分復号器のそれぞれは、該対応する成分符号化器によって符号化された順序で該データ・ブロック内のそれぞれのデータ・ビットに関するソフト判定情報を提供し、該（Ｎ−１）個のインターリーブ装置のそれぞれは、先行する成分復号器からの該ソフト判定情報をインターリーブすることにより、後続の成分復号器に並べ換えられたソフト情報のブロックを提供し、該Ｎ個の成分復号器のうちの第１の成分復号器に対する該１組の先験的ソフト判定情報は、該データ・ビットの値が第１の繰返しでは同等に起こりうると仮定して計算され、その後は、該ソフト判定情報の第１の関数を含み、該ソフト判定情報の第１の関数は、該（Ｎ−１）個のインターリーブ装置に対応する（Ｎ−１）個のインターリーブ解除装置を含む第１のインターリーブ解除装置を介してＮ番目の成分復号器から該Ｎ個の成分復号器のうちの該第１の成分復号器にフィードバックされ、該第１のインターリーブ解除装置の（Ｎ−１）個のインターリーブ解除装置は、該（Ｎ−１）個のインターリーブ装置とは逆の順序で適用され、それぞれの他の成分復号器に提供される該１組の先験的ソフト判定情報は、前の逐次的成分復号器からの該ソフト判定情報の第１の関数を含む、ステップと、
該（Ｎ−１）個のインターリーブ装置に対応する（Ｎ−１）個のインターリーブ解除装置を用いて、第２のインターリーブ解除装置においてインターリーブ解除することにより、該Ｎ番目の成分復号器からの該ソフト判定出力の第２の関数を合成復号器のソフト判定出力として提供するステップであって、該第２のインターリーブ解除装置の（Ｎ−１）個のインターリーブ装置は、該（Ｎ−１）個のインターリーブ装置とは逆の順序で適用される、ステップと
を包含する、方法。
【請求項３】
並列連結に接続された複数個（Ｎ個）の成分符号化器及び複数個（（Ｎ−１）個）のインターリーブ装置であって、データ・ビットのブロックと該データ・ビットのブロックの種々の並べ換えとにテイルバイティング非再帰的系統的コンボルーション・コードを系統的に適用し、それによって、該データ・ビットとパリティ・ビットとを含む成分コードワードを生成する、複数個（Ｎ個）の成分符号化器及び複数個（（Ｎ−１）個）のインターリーブ装置と、
該成分コードワードからのビットの集合をフォーマットすることにより、合成コートワードを提供する合成コードワード・フォーマット装置と
を備え、
該複数の成分符号化器は、第１の成分符号化器と第２の成分符号化器と複数の他の符号化器（（Ｎ−２）個）とを備え、
該複数のインターリーブ装置は、第１のインターリーブ装置と複数の他のインターリーブ装置（（Ｎ−２）個）とを備え、
該第１の成分符号化器は、該データ・ビットのブロックにテイルバイティング非再帰的系統的コンボルーション・コードを適用することによって、該データ・ビットのブロックを符号化し、それによって、該データ・ビットとパリティ・ビットとを含む対応する第１の成分コードワードを生成し、
該第１のインターリーブ装置は、該データ・ビットのブロックをインターリーブすることにより、並べ換えられたデータ・ビットのブロックを提供し、
該第２の成分符号化器は、該並べ換えられたデータ・ビットのブロックにテイルバイティング非再帰的系統的コンボルーション・コードを適用することによって、該並べ換えられたデータ・ビットのブロックを符号化し、それによって、該データ・ビットとパリティ・ビットとを含む対応する第２の成分コードワードを生成し、
該複数の他のインターリーブ装置のそれぞれは、後続のインターリーブ装置から提供された並べ換えられたデータ・ビットのブロックをインターリーブし、
該複数の他の成分復号器のそれぞれは、該並べ換えられたデータ・ビットのブロックにテイルバイティング非再帰的系統的コンボルーション・コードを適用することによって、該後続のインターリーブ装置から提供された該並べ換えられたデータ・ビットのブロックを符号化し、それによって、該データ・ビットとパリティ・ビットをと含む対応する後続の成分コードワードを生成する、並列連結符号化器。
【請求項４】
連結コンボルーション・コードを復号する合成復号器であって、
該合成復号器は、
連結符号化器においてデータ・ビットのブロックにテイルバイティング非再帰的コンボルーション・コードを適用することによって生成された複数個（Ｎ個）の成分コードワードの選ばれたビットを含む合成コードワードを、チャネルから受信し、該合成コードワードから複数個（Ｎ個）の対応する受信成分コードワードを形成する合成コードワードから成分コードワードへの変換器と、
複数個（Ｎ個）の成分復号器であって、それぞれの復号器は、該合成コードワードから成分コードワードへの変換器から対応する受信成分コードワードをそれぞれ受け取り、それぞれの復号器はまた、該データ・ビットの値に対する１組の先験的ソフト判定情報を受け取り、該Ｎ個の成分復号器のそれぞれは、連結符号化器内の対応する成分符号化器によって符号化された順序で該データ・ブロック内のそれぞれのデータ・ビットに関するソフト判定情報を提供する、複数個（Ｎ個）の成分復号器と、
複数個（（Ｎ−１）個）のインターリーブ装置であって、それぞれのインターリーブ装置は、対応する成分復号器からの該ソフト判定情報をインターリーブすることにより、後続の成分復号器に並べ替えられたソフト情報のブロックを提供し、該受信コードワードは、該Ｎ個の成分復号器と該（Ｎ−１）個のインターリーブ装置とに対する繰返し過程によって、復号されることにより、該合成復号器からのソフト判定出力を提供する、複数個（（Ｎ−１）個）のインターリーブ装置と、
該（Ｎ−１）個のインターリーブ装置に対応する（Ｎ−１）個のインターリーブ解除装置を含む構成されている第１のインターリーブ解除装置であって、該第１のインターリーブ解除装置の該（Ｎ−１）個のインターリーブ解除装置は、該（Ｎ−１）個のインターリーブ装置とは逆の順序で適用され、該Ｎ個の成分復号器のうちの第１の成分復号器に対する該１組の先験的ソフト判定情報は、該データ・ビットの値が第１の繰返しでは同等に起こりうると仮定して計算され、その後は、該ソフト判定情報の第１の関数を含み、該ソフト判定情報の第１の関数は、Ｎ番目の復号器によって出力され、該第１のインターリーブ解除装置を介して該Ｎ個の成分復号器のうちの第１の成分復号器にフィードバックされ、それぞれの他の成分復号器に提供される該１組の先験的ソフト判定情報は、前の逐次的成分復号器からの該ソフト判定情報の第１の関数を含む、第１のインターリーブ解除装置と、
該（Ｎ−１）個のインターリーブ装置に対応する（Ｎ−１）個のインターリーブ解除装置を含む第２のインターリーブ解除装置であって、該第２のインターリーブ解除装置の（Ｎ−１）個のインターリーブ解除装置は、該（Ｎ−１）個のインターリーブ装置と逆の順序で適用され、該第２のインターリーブ解除装置は、該Ｎ番目の成分復号器からの該ソフト判定出力の第２の関数をインターリーブ解除することにより、合成復号器ソフトの判定出力を提供する、第２のインターリーブ解除装置と
を備えた、合成復号器。
【請求項５】
前記Ｎ個の成分復号器は、固有ベクトル問題を解くことによって復号を行う円形ＭＡＰ復号器を含む、請求項４記載の合成復号器。
【請求項６】
前記Ｎ個の成分復号器は、再帰法を用いることによって復号を行う円形ＭＡＰ復号器を含む、請求項４記載の合成復号器。
【発明の詳細な説明】
発明の分野
本発明は全般的に不良チャネルを介しての短いメッセージの通信の為の誤り訂正符号化に関し、更に具体的に云えば、並列連結コンボルーション符号化法及びその復号器に関する。
発明の背景
並列連結コンボルーション符号化（ＰＣＣＣ）又は「ターボ符号化（ｔｕｒｂｏ  ｃｏｄｉｎｇ）」と呼ばれる１形式の並列連結符号化が、１００００個以上のビットからなるブロックに適用された時に実証された印象的な符号化の利得の為に、最近、符号化の研究課題になっている。（プロシーディング・オブ・ＩＥＥＥ・インターナショナル・コンファレンス・オン・コミュニュケーションズ誌、１９９３年、１０６４−１０７０頁所載のシー・ベラウ、エー・グラビュ及びピー・チティマイシァの論文「シャンノン限界に近い誤り訂正符号化及び複合（Ｎｅａｒ  Ｓｈａｎｎｏｎ  Ｌｉｍｉｔ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｉｎｇ  ａｎｄ  Ｄｅｃｏｄｉｎｇ）」、デンマーク工科大学電気通信研究所報告ＩＴ−１４６  ＩＳＳＮ  ０１０５−８５４、１９９４年１２月号所載のジェー・ディー・アンデルセンの論文「ＴＵＲＢＯ符号化方式」、及び１９９４ＩＥＥＥ・グローブコム・コンファレンス、１２９８−１３０３頁所載のピー・ロバートソンの論文「並列連結の再帰的系統的（ターボ）コードのコード構造並びに復号器について（Ｉｌｌｕｍｉｎａｔｉｎｇ  ｔｈｅ  Ｓｔｒｕｃｔｕｒｅ  ｏｆ  Ｃｏｄｅ  ａｎｄ  Ｄｅｃｏｄｅｒ  ｏｆ  Ｐａｒａｌｌｅｌ  ｃｏｎｃａｔｅｎａｔｅｄ  Ｒｅｃｕｒｓｉｖｅ  Ｓｙｓｔｅｍａｔｉｃ  （Ｔｕｒｂｏ）  Ｃｏｄｅｓ）」参照。）
然し、ターボ・コードの性能は、符号化されるデータ・ブロックの長さが短くなるとき、実質的に劣化することが判っている。この効果は、その成分の再帰的系統的コンボルーション・コード（Ｒｅｃｕｒｓｉｖｅ  Ｓｙｓｔｅｍａｔｉｃ  Ｃｏｎｖｏｌｕｔｉｏｎａｌ  Ｃｏｄｅ）の重み構造がブロックの長さに強く依存する為である。２番目の問題は、ターボ符号化器に印加されるメッセージ・ブロックを適切に終了させることである。ＩＥＥ・エレクトロニクス・レターズ誌、３０巻１６号、１９９４年８月４日号、１２８５−１２８６頁所載のオー・ヨエルソン及びエッチ・メイルの論文「ターボ・コードの格子の終結（Ｔｅｒｍｉｎａｔｉｎｇ  ｔｈｅ  Ｔｒｅｌｌｉｓ  ｏｆ  Ｔｕｒｂｏ−Ｃｏｄｅｓ）」に記載されているように、ターボ符号化器に使われているインターリーブ操作が、１組の後尾（ｔａｉｌ）ビットによりインターリーブされた符号化器入力シーケンス及びインターリーブされなかった符号化器入力シーケンスの両方を終了させることが出来なくすることがあるからである。メッセージ構造に埋め込まれた第２の後尾シーケンスを使って、インターリーブされたデータ・シーケンスに対して作用する符号化器が適切に終了するようにすることが出来るが、こうすると、符号化器の終了に伴うオーバーヘッドが２倍になり、実効的なコード・レートが低下する。その代わりとしては、符号化器の一方のシーケンスを終了させないことであるが、こうすると、特に短いメッセージに適用した時、符号化器／復号器システムの性能が劣化する。ＩＥＥ・エレクトロニクス・レターズ誌、３１巻１号、１９９５年１月６日号、２２−２３頁所載のエー・エス・バーブレスキュ及びエス・エス・ピエトロボンの論文「ターボ・コードの格子の同じ状態での終了（Ｔｅｒｍｉｎａｔｉｎｇ  ｔｈｅ  Ｔｒｅｌｌｉｓ  ｏｆ  Ｔｕｒｂｏ−Ｃｏｄｅｓ  ｉｎ  ｔｈｅＳａｍｅ  Ｓｔａｔｅ）」には、単一の終了ビット・シーケンスにより２つの成分の再帰的系統的コンボルーション（ＲＳＣ）符号化器を終了させる為にインターリーブ装置の設計に制約を加える方法が報告されている。その性能結果は、最適化なインターリーブ装置が使用されたときに両方の符号化器を終了させることによって得られる性能に比べて、若干の劣化がある。更に、公表されたビット誤り率（ＢＥＲ）対ビット当たりエネルギ／雑音エネルギ・スペクトル密度比（Ｅb／Ｅ0）データは、ターボ符号化器にＲＳＣを利用したとき、Ｅb／Ｅ0値のある範囲に亘ってＢＥＲが平坦になることを示している。
従って、短いデータ・ブロックに対する改良された並列連結符号化方式を提供することが望ましい。
発明の概要
本発明による並列連結コンボルーション符号化方式は、テイルバイティング（ｔａｉｌ−ｂｉｔｉｎｇ）非再帰的系統的コンボルーション（ＮＳＣ）コードを利用する。関連する復号器は、反復的に円形最大帰納的（ＭＡＰ：ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ）複号を利用して、ハード及びソフト判定出力を作成する。テイルバイティング・コードを使うことにより、ターボ符号化で入力データ・シーケンスを終了させる問題が解決され、こうして、短いメッセージに対する関連する復号器の性能の劣化が避けられる。ＮＳＣコードは、データ・ブロック長が増加するにつれて、漸近的に同じメモリを持つ再帰的系統的コンボルーション（ＲＳＣ）コードより一般的に弱いが、ＮＳＣコードの自由距離は、データ・ブロック長に対してそれほど敏感ではない。その為、ＮＳＣコードを用いた並列連結符号化は、ある閾値データ・ブロック寸法より短いメッセージに対しては、同じメモリを持つＲＳＣコードより性能が一層良くなる。
本発明の特徴並びに利点は以下図面について詳しく説明するところから明らかになろう。
【図面の簡単な説明】
第１図は、並列連結符号化器を示す簡略ブロック図である。
第２図は、並列連結コードに対する復号器を示す簡略ブロック図である。
第３図は、本発明による符号化方式に使われるテイルバイティング非再帰的系統的コンボルーション符号化器の簡略ブロック図である。
第４図は、本発明による並列連結コンボルーション符号化方式のための復号器内の成分復号器として役立つ円形ＭＡＰ復号器の簡略ブロック図である。
第５図は、本発明による並列連結コンボルーション符号化方式のための成分復号器として役立つ円形ＭＡＰ復号器の別の実施態様を示す簡略ブロック図である。
発明の詳しい説明
第１図は、並列連結符号化方式に対する符号化器信号処理１０の全体的なブロック図である。複数個（Ｎ個）の成分符号化器１２が源からのデータ・ビットのブロックに対して作用する。これらのデータ・ブロックはインターリーブ装置１４によってインターリーブ・アルゴリズムにより並べ替えられる。図示のように、Ｎ個の成分符号化器１２に対して（Ｎ−１）個のインターリーブ装置がある。最後に、成分符号化器の出力が合成コードワード・フォーマット装置１６によって組合わされて、１個の合成コードワードが作成される。合成コードワード・フォーマット装置はチャネルの特性に合うように選ばれ、合成コードワード・フォーマット装置の後には、チャネル並びに通信システムのチャネル・アクセス方式に合うように選んだフレーム・フォーマット装置が続いていてもよい。フレーム・フォーマット装置は、制御ビット及び同期記号のようなこの他の必要なオーバーヘッドを挿入することができる。
成分コードが系統的なコードである場合、並列連結符号化によりかなりのコード・レートの利点を達成することが出来る。系統的符号化器によって作成されるコード・ワード（出力）は、符号化器に入力として供給された元のデータ・ビットと、追加のパリティ・ビットを含む（パリティ・ビットによって導入された冗長度がコードの誤り訂正能力を生み出すものになる）。従って、第１図に示す並列連結符号化器に系統的符号化器を使う時、全ての成分符号化器１２によって作成されるコード・ワードは入力データ・ビットを含む。フォーマット装置１６が、各々の成分符号化器１２によって作成されるパリティ・ビットと符号化しようとする情報ビットのブロックだけで構成される合成コードワード又はデータ・パケットを形成する場合、送信される合成コードワード中の情報ビットの繰返しを除くことにより、合成並列連結コードのレート（ｒａｔｅ）に実質的な改善が実現される。例えば、２つの成分コードを有する並列連結コンボルーション・コード（ＰＣＣＣ）符号化器の成分符号化器１及び成分符号化器２が両方ともレート１／２のコードである場合、合成並列連結コードのレートは非系統的成分コードに対する１／４から、系統的成分コードが使われるときの１／３へ増加する。
再帰的系統的コンボルーション（ＲＳＣ）コードを利用する並列連結符号化方式は、多くの研究にとって最近の話題であった。こういう並列連結コンボルーション・コード（ＰＣＣＳ）は、文献では「ターボ」コードの名前で普通に知られている。前に述べたように、こういうＰＣＣＣは、比較的大きなメッセージすなわち１００００個以上のビットの場合、ビット誤り率（ＢＥＲ）対ビット当たりエネルギ／雑音エネルギ・スペクトル密度比（Ｅb／Ｎ0）の点で印象的な性能を達成することが出来る。然し、ターボ・コードを用いて達成される符号化利得は、再帰的系統的コンボルーション成分コードの強さがデータ・ブロック長に非常に影響され易い為に、データ・ブロックの寸法が小さくなるにつれて、目立って劣化することも判っている。他方、非再帰的系統的テイルバイティング・コンボルーション・コードの性能は、大抵の実際的な目的にとって、データ・ブロックの長さに無関係である。達成し得る性能が劣化するのは、符号化されるデータ・ビットのブロックが、ＮＳＣの判定の奥行特性によって決定される最小寸法未満である場合だけである。
第２図は、並列連結コードに対する全体的な復号器２０をブロック図で示している。復号器２０は次に述べるもの、すなわち、チャネルから受信した合成コードワードを各々の成分復号器２４に対する個別の受信コードワードに変換する合成コードワードから成分コードワードへの変換器２２と、第１図のＮ個の成分符号化器に対応するＮ個の成分復号器２４と、並列連結符号化器（第１図）で使ったのと同じ種類の（又は同じ）インターリーブ装置１４と、第１及び第２のインターリーブ解除装置２８及び２９とを有する。インターリーブ解除装置２８及び２９の各々は、符号化に用いた（Ｎ−１）個のインターリーブ装置に対応する直列連結の（Ｎ−１）個のインターリーブ解除装置３０に相当するシーケンス順序換え特性を夫々持つ。これらのインターリーブ解除装置に必要な順序が第２図に示されており、該順序はインターリーブ装置の順序の逆である。成分復号器２４の出力は、受信コードワード内の各々のデータ・ビットの推定値に関する何等かの形式のソフト判定情報である。例えば、成分復号器の出力は、チャネルからの受信した記号（ｓｙｍｂｏｌ）のシーケンスで条件づけられて、復号ビットが０又は１である確率の第１の関数であってよい。このような第１の関数の１例は成分復号器のソフト判定出力から条件付き確率Ｐ{ｄtj＝０／Ｙtj}の影響を取除き、その成分復号器のソフト判定出力は適切な並べ換えの後で次に続く成分復号器に入力される。ここで、Ｐ{ｄtj＝０／Ｙtj}は、受信したチャネル出力記号Ｙtのｊ番目の（系統的な）ビットで条件づけられて、時刻ｔにｊ番目の情報ビットが０になる確率である。この代わりに、成分復号器２４から出力されるソフト判定情報は、下記の尤度比
0003857320.tif 000002
の関数、又は対数尤度比ｌｏｇ［Λ（ｄtj）］の関数であってよい。図示のように、Ｎ番目の成分復号器は第２の入力、すなわち上述の復号されたビット値に対する条件付き確率又は尤度比の第２の関数を持っている。この第２の関数の例は、Ｐ{ｄtj＝０／Ｙ1L}と、前の成分復号器から受け取るｄtj＝０である先験的（ａ  ｐｒｉｏｒｉ）確率との積である。
並列連結コードに対する復号器は次に述べるように反復的に作用する。最初の成分復号器（復号器１）が、受信したコードワード並びに送信された情報ビットに関する先験的情報に基づいて、最初の成分符号化器によって符号化された情報ビットのシーケンスに対する１組のソフト判定値を計算する。最初の繰返しでは、源（ｓｏｕｒｃｅ）の統計に関する先験的情報がない場合、ビットは同じ尤度で０又は１である（すなわち、Ｐ｛ビット＝０｝＝Ｐ｛ビット＝１｝＝１／２）と仮定する。その後、復号器１によって計算されたソフト判定値は、２番目の符号化器に対するデータ・ビットのブロックを並べ換える為に、符号化器で使われたのと同じ種類の（又は同じ）インターリーブ装置を使ってインターリーブされる。このように並べ換えられたソフト判定値並びにそれに対応する受信コードワードが、次の成分復号器（復号器２）に対する入力を構成する。前の成分復号器及びインターリーブ装置から受け取った並べ換えられたソフト判定値は、復号しようとするデータ・ビットに関する先験的情報として次の成分復号器で利用される。このようにして、符号化器によって符号化されたデータ・ビットのブロックに対する１組のソフト判定出力をＮ番目の復号器が計算するまで、成分復号器は逐次的に動作する。次のステップは、前に述べたようにＮ番目の復号器からのソフト判定値をインターリーブ解除することである。その時、最初の復号器が、やはりＮ番目の復号器からの新しいソフト判定値を先験的情報として使って、受信コードワードに作用する。このような復号器の動作が、所望の繰返し回数に亘って進められる。最後の繰返しが終わった時、Ｎ番目の復号器によって計算されたソフト判定出力の第２の関数である値のシーケンスが、データをＰＣＣＣ符号化器が受信した時の順序に戻す為にインターリーブ解除される。繰返しの回数は予め定められた回数にするか、或いは復号器の収歛を検出することによってダイナミックに決定することが出来る。
復号器は確率Ｐ｛ｄtj＝０／Ｙ1L｝の関数、すなわち、１組のチャネル出力Ｙ1L＝｛ｙ1，．．．，ｙL｝が受信されるとして、時刻ｔにおける符号化器に対するｋビットの記号入力中のｊ番目のデータ・ビットが０である条件付き確率の関数であるソフト判定出力を作成する。更に、復号器は、下記のような判定規則
0003857320.tif 000003
を実施する判定装置を通じて、ソフト判定出力の関数としてのハード判定情報を供給することが出来る。すなわち、Ｐ｛ｄtj＝０／Ｙ1L｝＞（１／２）であれば、
0003857320.tif 000004
であれば、
0003857320.tif 000005
それ以外の場合は、ｄtjにランダムに０又は１の値を割り当てる。
典型的なターボ復号器は、ＩＥＥＥ・トランザクションズ・オブ・インフォメーション・セオリ誌、１９７４年３月号、２８４−２８７頁所載のエル・アール・バール、ジェイ・コック、エフ・ジェリネク及びジェイ・ラビブの論文「記号誤り率を最小にする線形コードの最適復号（Ｏｐｔｉｍａｌ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｌｉｎｅａｒ  Ｃｏｄｅｓ  ｆｏｒ  Ｍｉｎｉｍｉｚｉｎｇ  Ｓｙｍｂｏｌ  Ｅｒｒｏｒ）」に記載されているような最大帰納的（ＭＡＰ）復号器、又は１９８９ＩＥＥＥ・グローブコム・コンファレンス誌、１６８０−１６８６頁所載のジェイ・ハゲナウエル及びピー・ヘーエルの論文「ソフト判定出力を持つビテルビ・アルゴリズムとその応用（Ａ  Ｖｉｔｅｒｂｉ  Ａｌｇｏｒｉｔｈｍ  ｗｉｔｈ  Ｓｏｆｔ−Ｄｅｃｉｓｉｏｎ  Ｏｕｔｐｕｔｓ  ａｎｄ  ｉｔｓ  Ａｐｐｌｉｃａｔｉｏｎｓ）」に記載されているようなソフト出力ビテルビ・アルゴリズム（ＳＯＶＡ）復号器を利用する。ＭＡＰ復号器は、復号されたビット値が０又は１である確率を作成する。他方、ＳＯＶＡ復号器は典型的には復号された各々のビットに対し尤度比Ｐ｛復号ビットが１｝／Ｐ｛復号ビットが０｝を計算する。この尤度比は、Ｐ｛復号ビットが０｝＝１−Ｐ｛復号ビットが１｝を使って、Ｐ｛復号ビットが０｝から、又はその逆に計算することが出来ることは明らかである。ＭＡＰ又はＳＯＶＡ復号器が尤度比の対数すなわちｌｏｇ［Ｐ｛復号ビットが１｝／Ｐ｛復号ビットが０｝］で働く時、計算上の利点があることが判った。
ターボ・コードを用いることによって得られる符号化利得（誤り訂正能力）は、データ・ブロックの寸法が減少するにつれて目立って劣化することが実証されている。何人かの著者はこれを主にＲＳＣコードの性質の為であるとしている。ＲＳＣコードの距離特性が、データ・ブロック長の増加につれて増加することが判っている。逆に、ＲＳＣコードの最小距離は、データ・ブロック長の減少につれて減少する。２番目の問題は、インターリーブの為に、ターボ符号化方式で構成された全てのＲＳＣコードを終了させることが困難なことである。都合の悪いことに、シーケンスの終わりの欠如又はインターリーブ装置の設計に制約が課せられる悪影響はかなりのものであって、データ・ブロック長の減少につれてなおさらひどくなる。
本発明では、並列連結コンボルーション符号化方式の成分コードが、テイルバイティング非再帰的系統的コンボルーション・コードで構成される。このようなテイルバイティング・コードを使うと、ターボ符号化における入力データ・シーケンスの終了の問題が解決され、こうして短いメッセージに対する符号化器の性能の劣化が避けられる。一般的に非再帰的系統的コンボルーション（ＮＳＣ）コードは同じメモリを持つＲＳＣコードより弱いが、ＮＳＣコードの自由距離はデータ・ブロック長に影響される度合いが少ない。従って、ＮＳＣコードで並列連結符号化を行えば、予定の閾値データ・ブロック寸法より短いメッセージに対し、同じメモリを持つＲＳＣコードより作用が良くなる。性能のクロスオーバー点は、所望の復号ビット誤り率、コード・レート及びコード・メモリの関数である。
第３図は、本発明の並列連結コンボルーション符号化（ＰＣＣＣ）方式に使われるレート＝１／２、メモリ＝ｍのテイルバイティング非再帰的系統的コンボルーション符号化器の一例を示す。以下の説明では、（ｎ，ｋ，ｍ）符号化器は、入力記号がｋビットで構成され、出力記号がｎビットで構成され、ｍがｋビット記号で表した符号化器のメモリである構成の符号化器を表す。例として、第３図は、２進入力記号、すなわちｋ＝１の場合を示してある。然し、本発明はｋ、ｎ及びｍの任意の値に用いることが出来る。
最初、スイッチ５０が下側位置にあり、Ｌ入力ビットが一度にｋ個ずつ（この例では一度に１入力記号ずつ）、シフトレジスタ５２にシフトされる。Ｌ番目のビットを符号化器にロードした後、スイッチが上側位置に移り、第２のシフトレジスタ５４からの最初のビットが非再帰的系統的符号化器にシフトすることにより符号化が開始される。この時の符号化器の状態は{ｂL，ｂL-1，．．．，ｂL-(km-1)}である。この例では、符号化器の出力は、現在の入力ビットと符号化器の状態及び現在の入力記号の関数としてブロック５６（この例では基数２の加算として示されている）で形成されるパリティ・ビットとで構成される。Ｌ番目のビットが符号化された時、符号化が終わる。
本発明のもう１つの面として、上に述べた並列連結符号化器に対する関連する復号器が、出願人に譲渡された系属中の米国特許出願（米国特許第５，７２１，７４５号）に本発明者によって記載されている円形ＭＡＰ復号器で構成される。特に、この米国特許出願には、テイルバイティング・コンボルーション・コードを復号するのに役立つ円形ＭＡＰ復号器が記載されている。円形ＭＡＰ復号器は、符号化データ・ブロックの推定値並びに信頼性情報の両方をデータ・シンクに、例えば、伝送の誤りを隠す為に使われる音声合成信号処理装置に、又は繰返し要請の判定に使う為のブロック誤り確率の目安としてのパケット・データに対するプロトコル処理装置に送り出すことが出来る。
特に、上に引用した系属中の米国特許出願に記載されているように、テイルバイティング方式の誤り訂正用格子コードに対する円形ＭＡＰ復号器が、ソフト判定出力を発生する。円形ＭＡＰ復号器が、格子の第１段における状態の確率の推定値を発生し、こういう確率が従来のＭＡＰ復号器における出発状態の先験的情報に代わるものである。円形ＭＡＰ復号器は、２通りの方法の何れかで、初期状態確率分布を作成する。その１番目は、その結果として得られる固有ベクトルが所望の初期状態確率分布であるような固有値問題を解くものである。出発状態が判れば、円形ＭＡＰ復号器は、残りの復号を従来のＭＡＰ復号アルゴリズムに従って実施する。２番目は、繰返しが出発状態分布に収歛するような再帰法に基づいている。十分な繰り返しをした後、円形状態シーケンス上にある状態は高い確率で判り、円形ＭＡＰ復号器は、残りの復号を従来のＭＡＰ復号アルゴリズムに従って実施する。
従来のＭＡＰ復号アルゴリズムの目的は下記の条件付き確率を見つけることである。
Ｐ｛時刻ｔの状態ｍ／受信チャネル出力ｙ1，．．．，ｙL｝
この表式の項目Ｌは、符号化器の記号数を単位として表したデータ・ブロックの長さを表す。（ｎ，ｋ）コードに対する符号化器は、ｋビット入力記号に作用して、ｎビット出力記号を作成する。項ｙtは時刻ｔにおけるチャネル出力（記号）である。
ＭＡＰ復号アルゴリズムは実際には最初に下記の確率を見つける。
λt（ｍ）＝Ｐ｛Ｓt＝ｍ；Ｙ1L｝  （１）
すなわち、時刻ｔの符号化器の状態Ｓtがｍであって、１組のチャネル出力Ｙ1L＝｛ｙ1，．．．，ｙL｝を受信する結合確率を見つける。これは、所望の確率に定数（Ｐ｛Ｙ1L｝、１組のチャネル出力｛ｙ1，．．．，ｙL｝を受信する確率）を乗じたものである。
次に、行列Γtの要素を次のように定義する。
Γt（ｉ，ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙt／時刻（ｔ−１）の状態ｉ｝
行列Γtは、チャネル遷移確率Ｒ（Ｙt，Ｘ）、符号化器が時刻ｔに状態ｍ′からｍに遷移する確率ｐt（ｍ／ｍ′）、及び符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′，ｍ）の関数として計算される。特に、Γtの各々の要素は、下に示すように、考えられる全ての符号化器の出力Ｘに亘って加算することによって計算される。
0003857320.tif 000006
ＭＡＰ復号器は、格子の各段毎に１つづつ、こういう行列のＬを計算する。それらは、受信したチャネル出力記号と、所定のコードに対する格子の枝路の性質から形成される。
次に行ベクトルαtのＭ個の結合確率要素を次のように定義する。
αt（ｊ）＝Ｐ｛時刻ｔの状態ｊ；ｙ1，．．．，ｙt｝  （３）
列ベクトルβtのＭ個の条件付き確率要素を次のように定義する。
βt（ｊ）＝Ｐ｛ｙt+1，．．．ｙL／時刻ｔの状態ｊ｝  （４）
ここでｊ＝０、１、．．．、（Ｍ−１）であり、Ｍは符号化器の状態の数である。（なお、行列及びベクトルは太字を用いて表していることに注意されたい。）
ＭＡＰ復号アルゴリズムのステップは次の通りである。
（ｉ）前向き再帰法により、α1，．．．，αLを計算する。
αt＝αt-1Γt      ；ｔ＝１，．．．，Ｌ  （５）
（ii）後ろ向き再帰法により、β1，．．．，βL-1を計算する。
βt＝Γt+1βt+1    ；ｔ＝Ｌ−１，．．．，１  （６）
（iii）次の式により、λtの要素を計算する。
λt（ｉ）＝αt（ｉ）βt（ｉ）
；全てのｉに対し、ｔ＝Ｌ−１，．．．，１  （７）
（iv）必要に応じて関係する量を見つける。例えば、Ａtjを状態Ｓt＝｛Ｓt1，Ｓt2，．．．，Ｓtkm｝の集合とし、Ｓtのｊ番目の要素Ｓtjが０に等しいとする。従来の非再帰型格子コードでは、Ｓtj＝ｄtj、すなわち時刻ｔにおけるｊ番目のデータ・ビットである。従って、復号器のソフト判定出力は次のようになる。
0003857320.tif 000007
但し、
0003857320.tif 000008
ｍは状態Ｓtに対応する指数である。
復号器のハード判定又は復号ビット出力は、Ｐ｛ｄtj＝０／Ｙ1L｝を下記の判定規則に適応することによって得られる。
0003857320.tif 000009
すなわち、Ｐ｛ｄtj＝０／Ｙ1L｝＞（１／２）であれば、
0003857320.tif 000010
それ以外の場合は、ｄtjにランダムに０又は１の値を割り当てる。
上記のステップ（iv）に対する関連する量の別の例として、確率の行列σtは下記に定義する要素で構成される。
σt（ｉ，ｊ）＝Ｐ｛Ｓt-1＝ｉ；Ｓt＝ｊ；Ｙ1L｝
＝αt-1（ｉ）γt（ｉ，ｊ）βt（ｊ）
これらの確率は符号化器の出力ビットの帰納的確率（ａ  ｐｏｓｔｅｒｉｏｒｉ  ｐｒｏｂａｂｉｌｉｔｙ）を決定したい時に役に立つ。
ＭＡＰ復号アルゴリズムを標準的に適用する場合、ベクトルα0＝（１，０，．．．０）によって前向き再帰法を初期設定し、βL＝（１，０，．．．０）Tによって後ろ向き再帰法を初期設定する。これらの初期条件は符号化器の初期状態Ｓ0＝０及びその終期状態ＳL＝０という仮定に基づいている。
１実施態様の円形ＭＡＰ復号器は、次に述べるように固有値問題を解くことにより、初期状態確率分布を決定する。αt、βt、Γt及びλtを前の通りとし、初期のα0及びβLを次のようにとる。
βLを列ベクトル（１１１．．．１）Tとする。
α0を未知の（ベクトル）変数とする。
次に
（ｉ）式（２）に従って、ｔ＝１，２，．．．Ｌに対し、Γtを計算する。
（ii）行列積Γ1Γ2．．．ΓLの最大の固有値を見つける。対応する固有ベクトルを正規化して、その成分の和が１になるようにする。このベクトルがα0に対する解である。固有値はＰ｛Ｙ1L｝である。
（iii）式（５）に示す前向きの再帰法により、次のαtを形成する。
（iv）前に述べたように初期設定したβLから出発して、式（６）に示す後ろ向き再帰法により、βtを形成する。
（ｖ）式（７）に示すようにλtを形成すると共に、例えば前に述べたソフト判定出力Ｐ｛ｄtj＝０／Ｙ1L｝又は確率行列σtのようなその他の所望の変数を形成する。
本発明者は、未知の変数α0が次の行列式を満たすことを示した。
0003857320.tif 000011
この式が確率の間の関係を表す事実から、右辺のΓt行列の積は、Ｐ｛Ｙ1L｝に等しい最大の固有値を持つこと、並びに対応する固有ベクトルが確率ベクトルでなければならないことが判る。
最初のβL＝（１１１．．．１）Tを用いて、式（６）からβL-1が得られる。従って、この後ろ向き再帰法を繰り返して適用すれば、全てのβtが得られる。一旦α0が判り、βLが設定されると、本発明の円形ＭＡＰ復号器の全ての計算は、従来のＭＡＰ復号アルゴリズムに従う。
第４図は、前に述べた固有ベクトル方法に従って、誤り訂正のテイルバイティング格子コードを復号する円形ＭＡＰ復号器１１０を示す簡略ブロック図である。復号器１１０は、チャネル出力ｙtの関数としてΓtを計算するΓt計算器１１２を有する。Γt計算器はメモリ１３０から入力として次に述べるものを受け取る。すなわち、入力として、チャネル遷移確率Ｒ（Ｙt，Ｘ）と、符号化器が時刻ｔに状態ｍ′からｍに遷移する確率ｐt（ｍ／ｍ′）と、符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′、ｍ）とを受取る。Γt計算器は、式（２）に従って、考えられる全ての符号化器の出力Ｘに亘って加算することにより、Γtの各々の要素を計算する。
Γtの計算された値を行列積計算器１１４に供給して、例えばメモリから受け取った恒等行列１１６、スイッチ１１８及び遅延回路１２０を使用して、行列積Γ1Γ2．．．ΓLが形成される。時刻ｔ＝１に、恒等行列は行列積計算器に対する１つの入力として印加される。ｔ＝２乃至ｔ＝Ｌまでのこの後の各々の時刻に行列積
0003857320.tif 000012
が遅延回路を介して行列式計算器にフィードバックされる。
その後、時刻ｔ＝Ｌに、こうして得られた行列積がスイッチ１２１を介して正規化固有ベクトル・コンピュータ１２２に供給される。このコンピュータは、それに入力された行列積の最も大きい固有値に対応する正規化された固有ベクトルを計算する。このようにしてα0を初期設定すると、すなわち、このように正規化された固有ベクトルが得られると、それに続くαtベクトルは、図示のように遅延回路１２６及びスイッチ１２８の回路を使用し、行列積計算器１２４で式（５）を用いて再帰的に決定される。Γtの適当な値が、メモリ１３０から検索され、この結果得られたαtがメモリ１３０に記憶される。
βtの値が、式（６）に従って、スイッチ１３４及び遅延回路１３６を使って、行列積計算器１３２で決定される。その後、式（７）に従って、要素毎の積の計算器１４０により、確率λtがαt及びβtの値から計算される。λtの値が復号ビット値確率計算器１５０に供給され、この計算器は、時刻ｔにｊ番目の復号ビットｄtjが０に等しい確率を決定する。この確率が閾値判定装置１５２に供給される。この判定装置は、次の判定規則を実施する。すなわち、計算器１５０からの確率が１／２より大きければ、復号ビットが０であると判定する。確率が１／２より小さければ、復号ビットが１であると判定する。それが１／２に等しければ、復号ビットにランダムに０又は１の値を割り当てる。閾値判定装置の出力が復号器の時刻ｔにおける出力ビットである。
また第４図に示されているように、復号ビットが０に等しい確率Ｐ｛ｄtj＝０／Ｙtj｝もソフト出力関数ブロック１５４に供給されて、復号器のソフト判定出力として、例えば
0003857320.tif 000013
のような確率関数すなわちｆ（Ｐ｛ｄtj＝０／Ｙtj｝）を発生する。Ｐ｛ｄtj＝０／Ｙtj｝の役に立つもう１つの関数は
0003857320.tif 000014
である。この代わりに、ブロック１５４に対して役に立つ関数は、恒等関数であって、ソフト出力が単にＰ｛ｄtj＝０／Ｙtj｝になるようにしてもよい。
別の実施例の円形ＭＡＰ復号器は、再帰法により、状態確率分布を決定する。特に、１実施態様（ダイナミック収歛方法）では、復号器の収歛が検出されるまで、再帰法が続けられる。この再帰法（又はダイナミック収歛）では、前に述べた固有ベクトル方法のステップ（ii）及び（iii）は次のように置き換えられる。（iiａ）Ｍを格子の中にある状態の数として、（１／Ｍ，．．．，１／Ｍ）に等しい最初のα0から出発して、前向き再帰法でＬ回計算する。その結果を正規化して、各々の新しいαtの要素の和が１になるようにする。Ｌ個のαtベクトルの全てを保持する。
（iiｂ）α0を前のステップからのαLに等しいとし、ｔ＝１から出発して、最初のＬwminαt確率ベクトルを再び計算する。すなわち、Ｌwminを格子の適当な最小段数として、ｍ＝０，１，．．．，Ｍ−１及びｔ＝１，２，．．．，Ｌwminに対し
0003857320.tif 000015
を計算する。前と同じ様に正規化を行う。ステップ（iiａ）及び（iiｂ）の再帰法で見つけられた最も最近の１組のＬ個のα、並びに前にステップ（iiａ）で見つけられたαLwminだけを残す。
（iiｃ）ステップ（iiｂ）からのαLwminをステップ（iiａ）からの前に見つけられた組と比較する。新しいαLwmin及び古いαLwminのＭ個の対応する要素が許容範囲内であれば、前に述べたステップ（iv）に進む。そうでなければ、ステップ（iiｄ）に続ける。
（iiｄ）ｔ＝ｔ＋１とし、αt＝αt-1Γtを計算する。前と同じ様に正規化する。計算された１番最近のＬ個のαの集合並びにステップ（iiａ）で前に見いだしたαtだけを残す。
（iiｅ）新しいαtを前に見つけた組と比較する。Ｍ個の新しいαt及び古いαtが許容範囲内であれば、ステップ（iv）に進む。そうでない場合、１番最近の２つのベクトルが許容範囲内で一致せず、再帰法の回数が特定された最大値（典型的には２Ｌ）を越えなければ、ステップ（iiｄ）を続け、それ以外の場合、ステップ（iv）に進む。
この後、この方法は固有ベクトル方法について前に述べたステップ（iv）及び（ｖ）に続き、ソフト判定出力並びに円形ＭＡＰ復号器の復号出力ビットを発生する。
前に引用した米国特許出願（出願人整理番号ＲＤ−２４，９２３）に記載される別の実施態様の円形ＭＡＰ復号器では、上に述べた再帰法を修正して、復号器が２回目には、予定の一定の格子の段数を処理するだけでよいように、すなわち予定のラップ深さを持つようにする。これは、実施の点では、復号の為に必要な計算の回数が、符号化されるメッセージ・ブロック毎に同じであるので有利である。この為、ハードウェア及びソフトウェアの複雑さが少なくなる。
テイルバイティング・コンボルーション・コードのＭＡＰ復号に対する必要なラップ深さを推定する１つの方法は、ハードウェア又はソフトウェア実験からそれを決定することであり、可変ラップ深さを持つ円形ＭＡＰ復号器を構成して、相次いで増加するラップ深さに対し、復号ビット誤り率対Ｅb／Ｎ0を測定する実験を実施することを必要とする。それ以上ラップ深さを増加しても、誤りの確率が減少しないとき、特定されたＥb／Ｎ0に対する復号ビット誤りの最小確率となる最小復号器ラップ深さが見つかる。
特定されたＥb／Ｎ0で達成し得る最小値より大きな復号ビット誤り率が許容可能であれば、円形ＭＡＰ復号器によって処理される格子の必要段数を減らすことが可能である。特に、前に述べたラップ深さ探索は、ビット誤りの所望の平均確率が達成された時に単に終了しても良い。
所定のコードに対するラップ深さを決定する別の方法は、コードの距離特性を使うことである。この目的の為には、２つの別異の復号器判定深さを定義することが必要である。この明細書で云う「正しいパス」という用語は、データ・ビットのブロックを符号化することによって生じる状態のシーケンス又は格子の中のパス（ｐａｔｈ）を指す。「節の不正確な部分集合」という用語は、正しいパスの節（ｎｏｄｅ）及びその子孫から出た全ての不正確な（格子の）枝路の集合を指す。これから定義する両方の判定深さは、コンボルーション符号化器に関係する。
判定深さは次のように定義する。
（ｉ）ｅ−誤り訂正に対する前向き判定深さＬＦ（ｅ）は、後で正しいパスに合流してもしなくても、正しいパスの最初の節の不正確な部分集合内にある全てのパスが、正しいパスからハミング距離２ｅより遠い所にあるような格子内の第１の深さと定義される。ＬＦ（ｅ）の意味は、最初の節より前向きにｅ又は更に少ない誤りがあって、符号化がそこで始まったと判っている場合、復号器が正しく復号しなければならないことである。コンボルーション・コードに対する前向き判定深さの公式の表が、ＩＥＥＥ・トランザクションズ・オン・インフォメーション・セオリ誌、ＩＴ−３５巻、１９８９年３月号、４５５−５９頁所載のジェー・ビー・アンダーソン及びケイ・バラカンドランの論文「コンボルーション・コードの判定深さ（Ｄｅｃｉｓｉｏｎ  Ｄｅｐｔｈ  ｏｆ  Ｃｏｎｖｏｌｕｔｉｎａｌ  Ｃｏｄｅｓ）」に記載されている。ＬＦ（ｅ）の多数の性質が、この文献と１９９１年にミネソタ州ノーウェルのクルワー・パブリッシャーズから出版されたジェー・ビー・アンダーソン及びエス・モーハンの著書「源及びチャネル符号化−アルゴリズム方式（（Ｓｏｕｒｃｅ  ａｎｄ  Ｃｈａｎｎｅｌ  Ｃｏｄｉｎｇ−Ａｌｇｏｒｉｔｈｍｉｃ  Ａｐｐｒｏａｃｈ）」に記載されている。こういう性質の中で主なものは、ＬＦとｅの間に、単純な線形関係が存在することである。例えば、レート１／２のコードでは、ＬＦは約９．０８ｅである。
（ii）次に、ｅ−誤り訂正に対する合流（ｍｅｒｇｅ）しない場合の判定深さＬＵ（ｅ）は、正しいパスに接触することのなかった格子内の全てのパスが、正しいパスからハミング距離２ｅより遠く離れているような格子内の最初の深さと定義される。
ソフト判定円形ＭＡＰ復号に対するＬＵ（ｅ）の意味は、復号器が格子のＬＵ（ｅ）段を処理した後、実際に送信されたパスにおける状態を確認する確率が高いということである。従って、円形ＭＡＰ復号に対する最小ラップ深さはＬＵ（ｅ）である。深さＬＵ（ｅ）の計算では、それが常にＬＦ（ｅ）より大きいが、同じ近似則に従うことを示している。これは、コードの合流しない場合の判定深さが判っていなくても、最小ラップ深さを前向き判定深さＬＦ（ｅ）として推定することが出来ることを意味する。
所定の符号化器に対する最小の合流しなかった場合の判定深さを見つけることにより、ソフト判定出力を発生する実際の円形復号器によって処理しなければならない格子の最も少ない段数が判る。前向き判定深さＬＦ（ｅ）を見つけるアルゴリズムが、上に引用したジェー・ビー・アンダーソン及びケイ・バラカンドランの論文「コンボルーション・コードの判定深さ」に記載されている。ＬＵ（ｅ）を見つけるには、
（ｉ）ゼロ状態を除いて、格子の全ての節から同時に出発して、コード格子を左から右へ進む。
（ii）各々のレベルで、正しい（全部０の）パスに合流するパスがあれば、それを全て削除し、正しい（ゼロの）状態の節からのパスを延ばさない。
（iii）レベルｋで、このレベルの節で終端するパスの中で、最小のハミング距離又は重みを見つける。
（iv）この最小の距離が２ｅを越える場合、停止する。この時、ＬＵ（ｅ）＝ｋである。
前に引用した米国特許出願（ＲＤ−２４，９２３）に記載されているように、コンピュータ・シミュレーションによる実験で、予想外の２つの結果が得られた。すなわち、（１）βtのラップ処理が復号器の性能を改善する。（２）ＬＵ（ｅ）＋ＬＦ（ｅ）≒２ＬＦ（ｅ）のラップ深さを使うと、性能がかなり改善される。従って、再帰法に基づく好ましい実施例の円形ＭＡＰ復号器のアルゴリズムは、次のステップで構成される。
（ｉ）式（２）に従って、ｔ＝１，２，．．．Ｌに対し、Γtを計算する。
（ii）Ｍを格子内の状態の数として、（１／Ｍ，．．．，１／Ｍ）に等しい最初のα0から出発して、Ｌwを復号器のラップ深さとして、ｕ＝１，２，．．．（Ｌ＋Ｌw）に対し、式（５）の前向き再帰法を（Ｌ＋Ｌw）回計算する。格子−レベル指数ｔは（（ｕ−１）ｍｏｄ Ｌ）＋１の値をとる。復号器がチャネルからの受信した記号のシーケンスで折り返す時、αLはα0として取り扱う。結果を正規化し、各々の新しいαtの要素の合計が１になるようにする。この再帰法によって見いだされたＬ個の最も最近のαベクトルを残す。
（iii）（１，．．．，１）Tに等しい最初のβLから出発して、ｕ＝１，２，．．．（Ｌ＋Ｌw）に対し、式（６）の後ろ向き再帰法を（Ｌ＋Ｌw）回計算する。格子−レベル指数ｔはＬ−（ｕ  ｍｏｄ  Ｌ）の値をとる。復号器が受信したシーケンスで折り返すとき、新しいβLを計算するのに、β1をβL+1として使い、Γ1をΓL+1として使う。結果を正規化して、各々の新しいβtの要素の合計が１になるようにする。この場合も、この再帰法によって見いだされたＬ個の最も最近のβベクトルを残す。
好ましい再帰法の次のステップは、円形ＭＡＰ復号器によってソフト判定及び復号ビット出力を発生する為の固有ベクトル方法について前に述べたステップ（ｖ）と同じである。
第５図は本発明の好ましい実施例による円形ＭＡＰ復号器１８０を示す簡略ブロック図である。復号器１８０は、チャネル出力ｙtの関数としてΓtを計算するΓt計算器１８２を有する。チャネル出力ｙ1，．．．，ｙLがスイッチ１８４を介してΓt計算器に供給される。このスイッチが下側位置にあるとき、Ｌ個のチャネル出力記号が１度に１つづつ、Γt計算器１８２及びシフトレジスタ１８６にロードされる。その後、スイッチ１８４を上側位置に切り替えて、シフトレジスタが、最初のＬw個の受取った記号を再びΓt計算器へシフトさせる、すなわち円形処理を行うことが出来るようにする。Γt計算器が、メモリ１３０からの入力として、チャネル遷移確率Ｒ（Ｙt，Ｘ）、時刻ｔに符号化器が状態ｍ′からｍへ遷移する確率ｐt（ｍ／ｍ′）、及び符号化器の前の状態がｍ′であり且つ符号化器の現在の状態がｍであるとして、符号化器の出力記号がＸである確率ｑt（Ｘ／ｍ′，ｍ）を受取る。Γt計算器が、式（２）に従って、考えられる全ての符号化器の出力Ｘに亘って加算することにより、Γtの各々の要素を計算する。
Γtの計算された値が行列積計算器１９０に供給され、この計算器は、Γt行列にαt-1行列を乗算する。αt-1行列は、遅延回路１９２及びデマルチプレクサ１９４の回路を介して再帰的に供給される。制御信号ＣＮＴＲＬ１により、デマルチプレクサ１９４は、ｔ＝１の時に行列積計算器１９０に対する１つの入力としてメモリ１９６からのα0を選ぶ。２≦ｔ≦Ｌの時、制御信号ＣＮＴＲＬ１により、デマルチプレクサ１９４は、行列積計算器１９０に対する１つの入力として遅延回路１９２からのαt-1を選択する。必要に応じて、Γt及びαtの値がメモリ１９６に記憶される。
βtベクトルが、遅延回路２０２及びデマルチプレクサ２０４の回路を通じて再帰的に行列積計算器２００で計算される。制御信号ＣＮＴＲＬ２により、デマルチプレクサ２０４は、ｔ＝Ｌ−１の時に行列積計算器２００に対する１つの入力としてメモリ１９６からのβLを選択する。Ｌ−２≧ｔ≧１の時、制御信号ＣＮＴＲＬ２により、デマルチプレクサ２０４は、行列積計算器２００に対する１つの入力として遅延回路２０２からのβt+1を選択する。この結果得られたαtの値に、要素毎の積の計算器２０６でメモリ１９６から得られたαtの値を乗算して、前に述べた確率λtを発生する。前に第４図について述べたのと同様に、λtの値は復号ビット値確率計算器１５０に供給され、その出力が閾値判定装置１５２に供給され、その結果として復号器の復号出力ビットが得られる。
復号ビットが０に等しい条件付き確率Ｐ｛ｄtj＝０／Ｙtj｝も、確率の関数を作る為、ソフト出力関数ブロック１５４に供給されることが、第５図に示されている。ソフト出力関数ブロック１５４は、復号器のソフト判定出力として、例えば
0003857320.tif 000016
のような確率関数すなわちｆ（Ｐ｛ｄtj＝０／Ｙtj｝）を発生する。Ｐ｛ｄtj＝０／Ｙtj｝の役に立つもう１つの関数は
0003857320.tif 000017
である。この代わりに、ブロック１５４に対して役に立つ関数は、恒等関数であって、ソフト出力が単にＰ｛ｄtj＝０／Ｙtj｝になるようにしてもよい。
本発明では、復号コードワード・フォーマット装置によって形成された復号コードワードを、チャネルを介して復号ワードのビットを送信する前に、有利に選ばれたパターンに従って削除することにより、テイルバイティング非再帰的系統的コードで構成される並列連結符号化方式のレートを高めることが可能である。この方式はパンクチュアリング（ｐｕｎｃｔｕｒｉｎｇ）の名前で知られている。このパンクチュアリング・パターンも復号器によって判る。受信した復号コードワードから成分コードワードへの変換器によって行われる下記の簡単な追加のステップにより、所望の復号器動作が行われる。すなわち、受信した復号コードワードから成分コードワードへの変換器は、受信復号コードワードを形成する際、判っているパンクチュアリングされた各ビットに対して中立の値を単に挿入する。例えば、中立の値は、相加的なガウス型ホワイトノイズ・チャネルを介しての対せき点信号方式（ａｎｔｉｐｏｄａｌ  ｓｉｇｎａｌｌｉｎｇ）の場合である。復号器動作の残りの部分は、前に述べた通りである。
非再帰的系統的コンボルーション・コードは、例えば、これから発行予定のＩＥＥＥ・トランズアクションズ・オン・コミュニケーションズ誌にエス・ベネデット及びジー・モントルシの論文に報告されているように、比較的大きなデータ・ブロック長に対するＲＳＣコードの距離特性が優れている為に、並列連結符号化方式の成分コードとしては役に立たないと従来広く考えられていた。然し、前に述べたように、本発明者は、ＮＳＣコードの最小距離がデータ・ブロック長にそれほど影響されず、その為、非常に雑音の多いチャネルでデータ・ビットの短いブロックを送信する通信システムに有利に使うことが出来ることが判った。更に、本発明者は、テイルバイティング・コードを使うと、ターボ・コードで入力データ・シーケンスを終了させる問題が解決されることが判った。テイルバイティング・コンボルーション・コードを並列連結符号化方式で成分コードとして使うことは、従来提案されていない。従って、本発明は、テイルバイティング成分コンボルーション・コードを復号する円形ＭＡＰ復号器で構成された復号器を持ち、ビット誤り率対信号対雑音比で測って、従来のターボ符号化方式よりも短いデータ・ブロック長に対する性能が一層良い並列連結のテイルバイティング非再帰的系統的コンボルーション符号化方式を提供する。
本発明の好ましい実施態様を図示し説明したが、これらの実施態様が例示に過ぎないことは云うまでもない。本発明を逸脱することなく、当業者であれば、種々の変更、置き換えが考えられよう。従って、本発明は請求の範囲によって限定されることを承知されたい。
【図１】
0003857320.tif 000018
【図２】
0003857320.tif 000019
【図３】
0003857320.tif 000020
【図４】
0003857320.tif 000021
【図５】
0003857320.tif 000022