(57)【要約】【課題】  並列復号処理のパスメトリック値の初期化の改良を図って高速、高精度の復号を可能としたターボ復号方式を得る。【解決手段】  ターボ符号化コードデータを、第１〜第Ｎ（Ｎは２以上の整数）のサブコードブロックに分割してこれ等サブコードブロックを並列に復号処理するようにしたターボ復号方式において、第２以降の各サブコードブロックのフォワード方向のパスメトリックの算出のための初期値を、前段のサブコードブロックにおける最終演算値とし、第Ｎ−１以前の各サブコードブロックのバックワード方向のパスメトリックの算出のための初期値を、後段のサブコードブロックにおける最終演算値とする事前初期化処理手段４〜７（Ｎ＝４の場合）を設ける。このパスメトリック値の事前初期化処理の後、外部値計算＆硬判定処理ブロック８〜１１で、各サブコードブロックを並列に復号処理する。【選択図】      図１                                                  
2005210238.tif 000002
【特許請求の範囲】
【請求項１】
ターボ符号化コードデータを第１〜第Ｎ（Ｎは２以上の整数）のサブコードブロックに分割してこれ等サブコードブロックを並列に復号処理するようにしたターボ復号装置であって、
第２以降の各サブコードブロックのフォワード方向のパスメトリックの算出のための初期値を、前段のサブコードブロックにおける最終演算値とし、第Ｎ−１以前の各サブコードブロックのバックワード方向のパスメトリックの算出のための初期値を、後段のサブコードブロックにおける最終演算値とする初期化処理手段を含むことを特徴とするターボ復号装置。
【請求項２】
前記初期化処理手段は、
第１〜第Ｎのサブコードブロックの各々において、予め設定された初期値として、前記フォワード方向及びバックワード方向のパスメトリックを算出する第１の初期化処理ステージと、
第２以降のサブコードブロックの各々において、前段のサブコードブロックにおける前記フォワード方向のパスメトリックの最終演算値を初期値として、前記フォワード方向のパスメトリックを算出し、第Ｎ−１以前のサブコードブロックの各々において、後段のサブコードブロックにおける前記バックワード方向のパスメトリックの最終演算値を初期値として、前記バックワード方向のパスメトリックを算出する第２〜第Ｋ（Ｋは２以上の整数）の初期化処理ステージとを有することを特徴とする請求項１記載のターボ復号装置。
【請求項３】
前記第１及び第Ｎのサーブコードブロックの各々における前記第Ｋの初期化処理ステージでは、前記第１の初期化処理ステージでのフォワード方向及びバックワード方向の各パスメトリックの最終演算値を用いることを特徴とする請求項２記載のターボ復号装置。
【請求項４】
前記第１〜第Ｎのサブコードブロックの各々に対応して設けられ、前記初期化処理手段の前記第Ｋの初期化処理ステージにおける各サブコードブロックの前記フォワード方向及びバックワード方向の各パスメトリックの最終演算値をそれぞれ入力として対応サブコードブロックの復号処理をなす復号手段を、更に含むことを特徴とする請求項２または３記載のターボ復号装置。
【請求項５】
ターボ符号化コードデータを第１〜第Ｎ（Ｎは２以上の整数）のサブコードブロックに分割してこれ等サブコードブロックを並列に復号処理するようにしたターボ復号方法であって、
第２以降の各サブコードブロックのフォワード方向のパスメトリックの算出のための初期値を、前段のサブコードブロックにおける最終演算値とし、第Ｎ−１以前の各サブコードブロックのバックワード方向のパスメトリックの算出のための初期値を、後段のサブコードブロックにおける最終演算値とする初期化処理ステップを含むことを特徴とするターボ復号方法。
【請求項６】
前記初期化処理ステップは、
第１〜第Ｎのサブコードブロックの各々において、予め設定された初期値として、前記フォワード方向及びバックワード方向のパスメトリックを算出する第１のステップと、
第２以降のサブコードブロックの各々において、前段のサブコードブロックにおける前記フォワード方向のパスメトリックの最終演算値を初期値として、前記フォワード方向のパスメトリックを算出し、第Ｎ−１以前のサブコードブロックの各々において、後段のサブコードブロックにおける前記バックワード方向のパスメトリックの最終演算値を初期値として、前記バックワード方向のパスメトリックを算出する第２〜第Ｋ（Ｋは２以上の整数）のステップとを有することを特徴とする請求項５記載のターボ復号方法。
【請求項７】
前記第１及び第Ｎのサーブコードブロックの各々における前記第Ｋのステップでは、前記第１のステップのフォワード方向及びバックワード方向の各パスメトリックの最終演算値を用いることを特徴とする請求項６記載のターボ復号方法。
【請求項８】
前記初期化処理ステップの前記第Ｋのステップにおける各サブコードブロックの前記フォワード方向及びバックワード方向の各パスメトリックの最終演算値をそれぞれ入力として、前記第１及び第Ｎのサブコードブロックの各々の復号処理を並列になす復号ステップを、更に含むことを特徴とする請求項６または７記載のターボ復号方法。
【請求項９】
ターボ符号化コードデータを第１〜第Ｎ（Ｎは２以上の整数）のサブコードブロックに分割してこれ等サブコードブロックを並列に復号処理するようにしたターボ復号方法をコンピュータに実行させるためのプログラムであって、
第２以降の各サブコードブロックのフォワード方向のパスメトリックの算出のための初期値を、前段のサブコードブロックにおける最終演算値とし、第Ｎ−１以前の各サブコードブロックのバックワード方向のパスメトリックの算出のための初期値を、後段のサブコードブロックにおける最終演算値とする初期化処理を含むことを特徴とするプログラム。
【請求項１０】
前記初期化処理は、
第１〜第Ｎのサブコードブロックの各々において、予め設定された初期値として、前記フォワード方向及びバックワード方向のパスメトリックを算出する第１の処理と、
第２以降のサブコードブロックの各々において、前段のサブコードブロックにおける前記フォワード方向のパスメトリックの最終演算値を初期値として、前記フォワード方向のパスメトリックを算出し、第Ｎ−１以前のサブコードブロックの各々において、後段のサブコードブロックにおける前記バックワード方向のパスメトリックの最終演算値を初期値として、前記バックワード方向のパスメトリックを算出する第２〜第Ｋ（Ｋは２以上の整数）の処理とを有することを特徴とする請求項９記載のプログラム。
【請求項１１】
前記第１及び第Ｎのサーブコードブロックの各々における前記第Ｋの処理では、前記第１の処理のフォワード方向及びバックワード方向の各パスメトリックの最終演算値を用いることを特徴とする請求項１０記載のプログラム。
【請求項１２】
前記初期化処理の前記第Ｋの処理における各サブコードブロックの前記フォワード方向及びバックワード方向の各パスメトリックの最終演算値をそれぞれ入力として、前記第１及び第Ｎのサブコードブロックの各々の復号処理を並列になす復号処理を、更に含むことを特徴とする請求項１０または１１記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はターボ復号装置及びその方法並びにその動作プログラムに関し、特に通信システムや情報処理システムの分野において使用される高性能及び高信頼性のターボ符号を復号するターボ復号方式の改良に関するものである。
【背景技術】
【０００２】
近年、C. Berrou らによりシャノン限界に近い誤り訂正符号として、いわゆるターボ符号（Turbo codes ）方式があり、移動体通信システム、情報記録システム、ディジタル放送システム等を含む広範囲の通信分野や情報処理分野において用いられる高性能、高信頼性の符号化方式として研究開発が進められている。
【０００３】
ここで、まず、一般的なターボ符号器とターボ復号器について説明する。図６及び図７は公知のターボ符号器及びターボ復号器の構成を示すブロック図である。図６は符号化率＝１／３のターボ符号器の概略ブロック図を示しており、要素符号器Ｅ11及びＥ22と、インタリーバＥ21とを備えている。被符号化ビット（Information Bit to be encoded ）系列Ｅ01は分岐されて組織ビット（Systematic bit）系列Ｅ02として送出されると共に、要素符号器Ｅ11とインタリーバＥ21とに入力される。
【０００４】
要素符号器Ｅ11は、誤り訂正符号により被符号化ビット系列Ｅ01を符号化して、冗長ビット系列（Parity Bit）Ｅ12を出力する。インタリーバＥ21は、一般的に被符号化ビット系列Ｅ01を一度メモリに書込み、これを異なる順序で読出すことにより、データの順序を交錯して要素符号器Ｅ22に送出する。要素符号器Ｅ22は、インタリーブされた被符号化ビット系列を要素符号により符号化して冗長ビット系列Ｅ23を送出する。要素符号器Ｅ11，Ｅ22には、再帰的組織畳み込み符号器（ＲＳＣ:Recursive Systematic Convolutional Encoder ）が通常用いられる。
【０００５】
図７に示すターボ復号器は、要素復号器（Decoder ）Ｄ04，Ｄ16と、インタリーバＤ12と、デインタリーバＤ23と、硬判定出力ブロックＤ25とを備える。要素復号器Ｄ04には、組織ビット系列Ｅ02に対応する組織情報系列（Systematic Information）Ｄ01と、冗長ビット系列Ｅ12に対応する冗長情報系列（Parity Information）Ｄ02、及び外部情報（Extrinsic Information ）Ｄ03が入力される。そして、出力した外部情報Ｄ11は、次の要素復号器Ｄ16に利用される。
【０００６】
更に、得られた外部情報Ｄ11と組織情報系列Ｄ01は、インタリーバＤ12を介して、冗長ビット系列Ｅ23に対応する冗長情報系列（Parity Information）Ｄ14と共に、要素復号器Ｄ16に入力される。そして、要素復号器Ｄ16にて得られた軟出力情報（Soft Output Information ）Ｄ21と外部情報Ｄ22をデインタリーバＤ23に送出する。
【０００７】
デインタリーバＤ23は、インタリーバＤ12によるデータの入れ替え順番とは逆の順番に出力する。すなわち、インタリーブされた軟出力情報Ｄ21及び外部情報Ｄ22の各々をインタリーブ前の順序に戻し、軟出力情報Ｄ24及び外部情報Ｄ03として出力する。さらに、硬判定＆出力ブロックＤ25は、軟出力情報Ｄ24を硬判定して最終復号結果を出力する。外部情報Ｄ03は、次の復号処理のために、要素復号器Ｄ04にフィードバックされる。
【０００８】
以上のように、図７に示すターボ復号器では、二つの要素復号器の外部情報Ｄ03及びＤ15を更新しながら復号処理が繰り返し行なわれ、複数回のループの後、軟出力情報Ｄ24が硬判定される。
【０００９】
ターボ復号の要素復号器に適用される軟出力復号アルゴリズムとしては、最大事後確率復号法（以下、Maximum A Posteriori Probability：ＭＡＰと呼ぶ）を用いる方法が現在のところ最良であると言われているが、装置規模や処理量が格段に大きくなるので、実装に際しては送られてきたデータが‘１’か‘０’かを尤度の最大値に基づいて決定することで、処理を簡略化したMax-Log-MAP （Max Logarithmic Maximum A Posteriori）を使用した方式が一般的に広く用いられている。
【００１０】
ＭＡＰアルゴリズムは、トレリス線図を利用した最尤復号法アルゴリズムである。図８（ａ）はある要素符号器の構成の例であり、レジスタの数が３の場合を示している。トレリス線図とは、図８（ｂ）に示すように、この要素符号器に対して、ある値を入力した時の出力値と、レジスタ状態の関係を表したものである。
【００１１】
ＭＡＰアルゴリズムは大きく分けて次の３種類の処理から構成される。
（ａ）フォワード処理：トレリス線図の先頭から各時点の各状態へ到達する確率（フォワードパスメトリック）を算出する。
（ｂ）バックワード処理：トレリス線図の終端から各時点の各状態へ到達する確率（バックワードパスメトリック）を算出する。
（ｃ）軟出力生成処理および外部値計算：（ａ），（ｂ）の処理結果を用いて各時点における組織ビットの軟出力値を算出する。そして、この軟出力値を用いて、外部値計算を行う。
【００１２】
トレリス線図において、時点ｔ、状態ｓにおけるフォワード処理及びバックワード処理の各々で算出されるフォワードパスメトリック及びバックワードパスメトリックをそれぞれＡｌｐｈａ（ｔ，ｓ），Ｂｅｔａ（ｔ，ｓ）と表す。また、状態ｓから状態ｓ’への時点ｔにおける遷移の確率をＧａｍｍａ（ｔ，ｓ，ｓ’）と表す（ここで、Ｇａｍｍａはブランチメトリックと呼ばれる）。Ｇａｍｍａ（ｔ，ｓ，ｓ’）は、受信値（組織情報系列、冗長情報系列、外部情報）から求める確率である。
【００１３】
上述したフォワード処理、バックワード処理、軟出力生成処理及び外部値計算の各々は、次のように実行される。
（ａ）フォワード処理：
Ａｌｐｈａ（ｔ，ｓ）＝Ｍａｘ｛Ａｌｐｈａ（ｔ−１，ｓ’）
＋Ｇａｍｍａ（ｔ，ｓ’，ｓ）｝
なお、ここで、最大値を求める処理Ｍａｘはすべての状態ｓ’についてとることを意味する。
【００１４】
図９（ａ）に示すように、時点ｔのある状態Ｓｔａｔｅ（Ｓ３）に対するＡｌｐｈａ（ｔ，Ｓ３）は、次のように計算される。２つの前段Ｓｔａｔｅの持つパスメトリックＡｌｐｈａ（ｔ−１，Ｓ１），Ａｌｐｈａ（ｔ−１，Ｓ２）の各々に、それぞれのブランチメトリックＧａｍｍａ（ｔ，Ｓ１，Ｓ３），Ｇａｍｍａ（ｔ，Ｓ２，Ｓ３）を加算し、値の大きいほうがそのＳｔａｔｅのＡｌｐｈａ値となる（Ａｌｐｈａ  ＡＣＳ（Add-Compare-Select）演算と呼ぶ）。この処理を、全時間遷移ｔの全Ｓｔａｔｅに対して行い、全ＳｔａｔｅのＡｌｐｈａ値を保持しておく。
【００１５】
なお、Ａｌｐｈａ算出の初回では、前段のＡｌｐｈａ値が存在しないので、初期値の設定が必要となる。ここで、必ずトレリス線図中のＳｔａｔｅ＃０から遷移が開始されるため、Ａｌｐｈａの初期値としては、Ｓｔａｔｅ＃０のＡｌｐｈａが０、それ以外のＳｔａｔｅは−ＭＡＸ値（最小値）と規定する。
【００１６】
（ｂ）バックワード処理：
Ｂｅｔａ（ｔ，ｓ）＝Ｍａｘ｛Ｂｅｔａ（ｔ＋１，ｓ’）
＋Ｇａｍｍａ（ｔ＋１，ｓ，ｓ’）｝
【００１７】
図９（ｂ）に示すように、時点ｔのあるＳｔａｔｅ（Ｓ４）に対するＢｅｔａ（ｔ，Ｓ４）は、次のように計算される。２つの後段Ｓｔａｔｅの持つパスメトリックＢｅｔａ（ｔ＋１，Ｓ５），Ｂｅｔａ（ｔ＋１，Ｓ６）に、それぞれのブランチメトリックＧａｍｍａ（ｔ＋１，Ｓ４，Ｓ５），Ｇａｍｍａ（ｔ＋１，Ｓ４，Ｓ６）を加算し、値の大きいほうがそのＳｔａｔｅのＢｅｔａ値となる（Ｂｅｔａ  ＡＣＳ演算と呼ぶ）。
【００１８】
この処理を、全時間遷移ｔの全Ｓｔａｔｅに対して、Ａｌｐｈａとは逆方向から（トレリス最終Ｓｔａｔｅ側から）Ｂｅｔａ算出処理を行う。なお、Ｂｅｔａ算出の初回では、後段のＢｅｔａ値が存在しないので、初期値の設定が必要となる。ここで、トレリス線図の最終端において、Ｂｅｔａの初期値としては、Ｓｔａｔｅ＃０のＢｅｔａが０、それ以外のＳｔａｔｅは−ＭＡＸ値（最小値）と規定する。
【００１９】
（ｃ）軟出力生成処理及び外部値計算：
すでに算出しておいたＡｌｐｈａ（ｔ−１，ｓ’）の値とＢｅｔａ（ｔ，ｓ）およびＧａｍｍａ（ｔ，ｓ’，ｓ）を加算して、時点ｔにおける全パスメトリック値を求める。そして、‘デコード結果が０となるパスの最大パスメトリック’と‘デコード結果が１となるパスの最大パスメトリック’の差分が、時点ｔの軟出力値となる。
【００２０】
図１０を例として説明すると、時点ｔ＝５のすべての（ｓ，ｓ’）の組合せに対して、Ａｌｐｈａ（４，ｓ’），Ｂｅｔａ（５，ｓ）及びＧａｍｍａ（５，ｓ’，ｓ）を加算する。そのうち、デコード結果が０となるパスの最大パスメトリックＬ０（ｔ）を求める。この例では、
Ｌ０（ｔ＝５）＝Ａｌｐｈａ（ｔ＝４，ｓｔａｔｅ＃７）
＋Ｂｅｔａ（ｔ＝５，ｓｔａｔｅ＃６）
＋Ｇａｍｍａ（ｔ＝５，ｓｔｓｔｅ＃７，ｓｔａｔｅ＃６）
となっている。
【００２１】
一方、デコード結果が１となるパスの最大パスメトリックＬ１（ｔ）も求める。この例では、
Ｌ１（ｔ＝５）＝Ａｌｐｈａ（ｔ＝４，ｓｔａｔｅ＃４）
＋Ｂｅｔａ（ｔ＝５，ｓｔａｔｅ＃０）
＋Ｇａｍｍａ（ｔ＝５，ｓｔｓｔｅ＃４，ｓｔａｔｅ＃０）
となっている。そして、ｔ＝５の軟出力値は、
Ｌ（ｔ＝５）＝Ｌ０（ｔ＝５）−Ｌ１（ｔ＝５）
と計算される。
【００２２】
また、Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムでは，上で求めた軟出力値（事後値）から通信路値（受信値から求める値）と事前値（前段の復号器から与えられる外部情報）を減算した値が外部情報となる。
【００２３】
以上のように、理想Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムでは、Ａｌｐｈａ，Ｂｅｔａの演算を一度に全復号対象データに対して行う。
【００２４】
しかし、データ伝送ではデータ長の増大に伴って、Ｍａｘ−Ｌｏｇ−ＭＡＰ復号に膨大なメモリ領域が必要となる。特に、トレリス全体のパスメトリック情報を記憶するためのメモリ領域が必要となる。また、復号長の増加により、復号処理遅延も増えるため、実際のリアルタイムシステムに適用することが困難である。
【００２５】
そこで、スライディングウィンドウと呼ばれている方式が広く使用されている（非特許文献１参照）。この方法では、ウィンドウサイズ分のトレリス内の尤度情報のみ記憶しておき、このウィンドウ位置を復号長に達するまでシフトしていくことで、メモリの大幅な節約を図ることができる。
【００２６】
さらに、最近、一つのコードブロック（復号対象データ）を複数のサブコードブロックに分割し、それぞれのサブコードブロックを並列に復号する方式が知られている（非特許文献２参照）が、各サブ復号器の同時処理により、節目（各サブコードブロックの起点と終点）のパスメトリック（Ａｌｐｈａ及びＢｅｔａ）は不定なので、最初のサブコードブロックのＡｌｐｈａ初期値（理想Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムの設定と同じ）と、最終のサブコードブロックのＢｅｔａ初期値（理想Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムの設定と同じ）を除き、初回復号処理における各サブコードブロックのＡｌｐｈａ及びＢｅｔａの初期値が強制設定される。
【００２７】
【非特許文献１】A.J. Viterbi, “An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes,” IEEE J. Select. Areas Commun., Vol.16, pp.260-264, Feb. 1998.
【非特許文献２】S. Yoon, Y. Bar-Ness, “A Parallel MAP Algorithm for Low Latency Turbo Decoding,” IEEE Communications Letters, Vol.6, No.7, pp.288-290, July 2002.
【発明の開示】
【発明が解決しようとする課題】
【００２８】
非特許文献１の技術では、メモリの大幅な節約を図ることができるが、この復号装置では、各ウィンドウ順に処理するため、全体の復号処理時間を減少できないという欠点がある。また、非特許文献２の技術では、すべてのＡｌｐｈａ，Ｂｅｔａを０とするため、分割による節目における復号誤りの集中が問題となる。従って、有効な高速化ターボ復号を実現するため、並列復号処理の初期化の改良方法が課題となっている。
【００２９】
本発明の目的は、並列復号処理の初期化の改良を図って高速な復号を可能としたターボ復号装置及びその方法並びにその動作プログラムを提供することである。
【課題を解決するための手段】
【００３０】
本発明によるターボ復号装置は、ターボ符号化コードデータを第１〜第Ｎ（Ｎは２以上の整数）のサブコードブロックに分割してこれ等サブコードブロックを並列に復号処理するようにしたターボ復号装置であって、第２以降の各サブコードブロックのフォワード方向のパスメトリックの算出のための初期値を、前段のサブコードブロックにおける最終演算値とし、第Ｎ−１以前の各サブコードブロックのバックワード方向のパスメトリックの算出のための初期値を、後段のサブコードブロックにおける最終演算値とする初期化処理手段を含むことを特徴とする。
【００３１】
本発明によるターボ復号方法は、ターボ符号化コードデータを第１〜第Ｎ（Ｎは２以上の整数）のサブコードブロックに分割してこれ等サブコードブロックを並列に復号処理するようにしたターボ復号方法であって、第２以降の各サブコードブロックのフォワード方向のパスメトリックの算出のための初期値を、前段のサブコードブロックにおける最終演算値とし、第Ｎ−１以前の各サブコードブロックのバックワード方向のパスメトリックの算出のための初期値を、後段のサブコードブロックにおける最終演算値とする初期化処理ステップを含むことを特徴とする。
【００３２】
本発明によるプログラムは、ターボ符号化コードデータを第１〜第Ｎ（Ｎは２以上の整数）のサブコードブロックに分割してこれ等サブコードブロックを並列に復号処理するようにしたターボ復号方法をコンピュータに実行させるためのプログラムであって、第２以降の各サブコードブロックのフォワード方向のパスメトリックの算出のための初期値を、前段のサブコードブロックにおける最終演算値とし、第Ｎ−１以前の各サブコードブロックのバックワード方向のパスメトリックの算出のための初期値を、後段のサブコードブロックにおける最終演算値とする初期化処理を含むことを特徴とする。
【００３３】
本発明の作用を述べる。各サブ復号器の同時処理により、区切り目（各サブコードブロックの起点と終点）のパスメトリック（Ａｌｐｈａ及びＢｅｔａ）は隣のサブコードブロックで得られたパスメトリックの値を利用できないので、従来では、初回の復号処理にてその初期値をある固定値（例えば、０）と仮定しており、よって、この初期値設定に基づいて算出された外部情報は、理想的なＭａｘ−Ｌｏｇ−ＭＡＰアルゴリズムの結果と異なることになる。つまり、外部情報が不正確になるため、繰返し復号器の性能も悪くなる。
【００３４】
そこで、本発明では、外部値計算及び硬判定処理をなす復号ステージの前段において、複数の事前初期化処理ステージを設けて、これ等事前初期化処理ステージで、各サブブロックのパスメトリックの初期化処理を行うようにすることにより、各サブブロックの初期値は初期化処理ステージ数の増加に伴って改善されるので、復号の性能も良くなる。但し、初期化処理のステージ数の増加に伴ってハードウェアコスト及び回路遅延も増大するため、実際の設計を行う場合には、ステージ数の設定と復号性能、ハードウェアコストなどのトレードオフを考慮する必要がある。
【００３５】
このような高速化復号処理の効率は、携帯電話のような通信のリアルタイム性が厳格に要求される機器にターボ復号装置を搭載した場合に、特に要求されるものである。
【発明の効果】
【００３６】
本発明による効果は次の如くである。符号化されたコードブロックを複数のサブコードブロックに分割して復号処理する場合、これ等各サブコードブロックにおけるＡｌｐｈａ，Ｂｅｔａの各パスメトリックの初期値が不定となるが、事前初期化処理ブロックを用いて、これ等パスメトリックの初期値の不定をなくしているので、復号性能の改善ができると共に、これ等パスメトリック値の事前初期化処理後に、各サブコードブロックサブに対応して設けられているサブ復号器を同時に動作するようにしているので、反復復号の復号遅延を減少し、高速化復号処理を実現できるという効果がある。
【発明を実施するための最良の形態】
【００３７】
以下に図面を参照しつつ本発明の実施の形態について詳細に説明する。図１は本発明の実施の形態の概略ブロック図である。本発明では、長さＮＷのコードブロック（Ｎ，Ｗは２以上の整数）をＮ個の等しい長さＷのサブコードブロック＃１〜＃４に分割し、それぞれのサブコードブロックを並列に復号することを考える。本実施の形態では、図１に示すように、Ｎ＝４の例として説明する。
【００３８】
ターボ復号入力バッファ１から出力された組織情報２(Systematic information)、冗長情報３(Parity Information)及び繰返しにおける前回の復号にて得られた外部情報１４(External information)が、それぞれに第１〜第４のサブコードブロック＃１〜＃４に分割されて、各サブターボ復号器に入力される。第１サブコードブロック＃１を復号するサブターボ復号器は、事前初期化処理ブロック４と外部値計算＆硬判定処理ブロック８から構成される。
【００３９】
同様に、第２サブターボ復号器は事前初期化処理ブロック５と外部値計算＆硬判定処理ブロック９から構成される。第３サブターボ復号器は事前初期化処理ブロック６と外部値計算＆硬判定処理ブロック１０から構成される。第４サブターボ復号器は事前初期化処理ブロック７と外部値計算＆硬判定処理ブロック１１から構成される。
【００４０】
ＲＡＭ１２は外部値計算＆硬判定処理ブロック８〜１１の各外部情報を、インタリーバパターン情報部１３のインタリーバパターンに従って格納するものであり、また復号出力部１５は外部値計算＆硬判定処理ブロック８〜１１の各硬判定出力を、インタリーバパターン情報部１３のインタリーバパターンに従って導出するものである。
【００４１】
事前初期化処理ブロック４〜７における事前初期化処理によりそれぞれ得られた各サブコードブロックのＡｌｐｈａ，Ｂｅｔａパスメトリックを、それぞれの外部値計算＆硬判定処理ブロック８〜１１に渡す。各サブターボ復号器の構成が同一であるため、ここでは、一つのサブターボ復号器の詳細な構成要素を例として説明することにする。
【００４２】
図２は本実施の形態における第２サブターボ復号器の事前初期化処理５の構成例を示すブロック図である。フォワード処理における組織情報(Systematic information)２、冗長情報(Parity information)３および外部情報(External information)１４から、ＢＭ算出部(BM Calculation)５０１において、ブランチメトリック（ＢＭ）を算出する。また、この算出されたブランチメトリックはＡｌｐｈａ  ＡＣＳ演算部５０４に入力されると共に、Ｂｅｔａ  ＡＣＳ演算部５１２及び外部値計算＆硬判定処理ブロック９において使用されるために、メモリ５１１に保存される。
【００４３】
Ａｌｐｈａ  ＡＣＳ演算部５０４の入力は、ブランチメトリック計算部５０１の出力値であるブランチメトリック値と、前段（フォワード方向）＃１の初期化処理ブロック４にて得られたＡｌｐｈａパスメトリック値としての初期値と、前段のＳｔａｔｅまでのパスが持つＡｌｐｈａパスメトリック５０３とから構成される。算出されたこのサブコードブロック＃２における最後のＡｌｐｈａパスメトリック値はＡｌｐｈａ初期値メモリ５０６に書込まれて、初期値として次段＃３の初期化処理ブロック６に渡される。また、算出されたサブコードブロック内の全ＡｌｐｈａパスメトリックはＡｌｐｈａ  ＲＡＭ５０５に書込まれて、外部値計算＆硬判定処理ブロック９に渡される。
【００４４】
Ｂｅｔａ  ＡＣＳ演算部５１２の入力は、メモリ５１１から読込まれたブランチメトリック値と、前段（バックワード方向）＃３の初期化処理ブロック６にて得られたＢｅｔａパスメトリック値としての初期値と、前段のＳｔａｔｅまでのパスが持つＢｅｔａパスメトリック５１４とから構成される。算出されたこのサブコードブロックにおける最後のＢｅｔａパスメトリック値はＢｅｔａ初期値メモリ５１５に書込まれて、初期値として次段＃１の初期化処理ブロック４に渡される。Ｂｅｔａパスメトリック値９２が外部値計算＆硬判定ブロック９に渡される。
【００４５】
図３は、本発明の実施例における第２サブターボ復号器の外部値計算＆硬判定処理９の構成例を示すブロックである。初期化ブロック５にて得られたＡｌｐｈａ，Ｂｅｔａパスメトリック値９１，９２とブランチメトリック値９０とから軟出力値計算（Soft Output Value ）部９３で軟出力値の計算が行われる。通信路値計算部９６の入力は組織情報２であり、その出力は通信路情報９７である。外部値計算部９５の入力は、通信路情報９７、外部情報１４及び軟出力計算部９３にて得られた軟出力値である。算出された外部値は外部値ＲＡＭ１２（図１参照）に、インタリーバパターン情報部１３のパターンに従って書込まれる。また、軟出力計算部９３の出力値は硬判定処理部９４に入力され、硬判定処理が行われる。硬判定処理部９４の出力は、復号出力部１５に、インタリーバパターン情報部１３のパターンに従って復号結果として出力される。
【００４６】
次に、図１〜図３の回路の動作について、図４及び図５を参照して説明する。先ず、図４を参照すると、本発明の実施の形態の全体の動作の概略を示すフローチャートであり、符号化されたコードブロックの入力があると（ステップＳ１）、複数のサブコードブロックに分割されて（本実施の形態では、＃１〜＃４の４つのサブコードブロック）（ステップＳ２）、対応する事前初期化処理ブロック４〜７へそれぞれ供給される。
【００４７】
これ等事前初期化処理ブロック４〜７の各々において、各サブコードブロックのＡｌｐｈａパスメトリック及びＢｅｔａパスメトリックの事前初期化処理がなされることになる（ステップＳ３）。しかる後に、各サブコードブロックの並列的な復号処理が行われる（ステップＳ４）。そして、Ｍ回（Ｍは正の整数）の繰り返し復号（ステップＳ３〜Ｓ５）が行われ、最終的に当該コードブロックの復号出力が導出される（ステップＳ６）。そして、次のコードブロックの入力に対しても、同様な処理が行われる。
【００４８】
本例における事前初期化処理ブロック４〜７（図４のフローのステップＳ３）では、複数の初期化処理ステージが設定される。図５を参照すると、図の例では、この初期化処理ステージの数をＫ＝３と設定している。最後の初期化処理ステージ（Stage ３）を除く各ステージ（Stage １，２）では、Ａｌｐｈａ，Ｂｅｔａパスメトリックを計算するが、このとき、それぞれの前ステージで算出された前のサブコードブロック（フォワード方向）のＡｌｐｈａパスメトリックの最終値を初期値とし、Ａｌｐｈａ  ＡＣＳ演算部５０４でＡｌｐｈａパスメトリック値が算出される。
【００４９】
ここでの最終値は、Ａｌｐｈａ初期値メモリ５０６へ保存されて、次のステージにおける次のサブコートブロック（フォワード方向）に初期値として渡されるが、未だＡｌｐｈａ  ＲＡＭ５０５へは格納されないし、外部値計算＆硬判定ブロック９への出力処理もなされない。
【００５０】
同時に、前ステージで算出された前のサブコードブロック（バックワード方向）のＢｅｔａパスメトリックの最終値を初期値とし、Ｂｅｔａ  ＡＣＳ演算部５１２でＢｅｔａパスメトリック値が演算される。ここでの最終値は、Ｂｅｔａ初期値メモリ５１５に保存されて、次のステージにおいる次のサブコートブロック（バックワード方向）に初期値として渡されるが、外部値計算＆硬判定ブロック９への出力処理はなされない。
【００５１】
例えば、第２サブコードブロック＃２の初期化処理ステージ２において、Ａｌｐｈａパスメトリックの初期値は初期化処理ステージ１から得られた第一サブコードブロック＃１のＡｌｐｈａパスメトリックの最終値（＃１Ａ１）であり、Ｂｅｔａパスメトリックの初期値は初期化処理ステージ１から得られた第３サブコードブロック＃３のＢｅｔａパスメトリックの最終値（＃３Ｂ１）である。また、このステージ２で得られたＡｌｐｈａ、Ｂｅｔａのパスメトリックの各最終値（＃２Ａ２）、（＃２Ｂ２）が、それぞれ初期値として、ステージ３おいて、第３サブコードブロック＃３と第１サブコードブロック＃１とに渡される。
【００５２】
すなわち、初期化処理ステージ１，２では、全Ａｌｐｈａ，Ｂｅｔａパスメトリックを計算するが、使用されるのはＡｌｐｈａ，Ｂｅｔａの最終値だけである。従って、これ等初期化処理ステージ１，２の各々においては、図２のＢＭ算出部５０１、メモリ５１１、Ａｌｐｈａ及びＢｅｔａ  ＡＣＳ演算部５０４，５１２、Ａｌｐｈａ及びＢｅｔａ初期値メモリ５０６，５１５が動作し、Ａｌｐｈａ及びＢｅｔａ  ＡＣＳ演算部５０４，５１２における各最終値が、Ａｌｐｈａ及びＢｅｔａ初期値メモリ５０６，５１５にそれぞれ格納されて、次のステージの次のサブコードブロック＃３，＃１に、初期値としてそれぞれ渡されるのである。
【００５３】
ステージ３では、前のステージでのフォワード方向及びバックワード方向のＡｌｐｈａ及びＢｅｔａ初期値メモリ５０６，５１５からの最終値が、Ａｌｐｈａ及びＢｅｔａパスメトリックの各初期値として、Ａｌｐｈａ及びＢｅｔａ  ＡＣＳ演算部５０４，５１２にてそれぞれ演算され、Ａｌｐｈａ  ＡＣＳ演算結果がＡｌｐｈａ  ＲＡＭ５０５を介して（９１）、またＢｅｔａ  ＡＣＳ演算結果９２が、ブランチメトリック（メモリ５１１の出力）９０と共に、外部値計算＆硬判定ブロック９へ渡されることになる。
【００５４】
このステージ３において、第１のサブコードブロックのＡｌｐｈａパスメトリックに関しては、最初のステージ１で算出されたＡｌｐｈａパスメトリックの最終演算値が、そのままＡｌｐｈａ  ＲＡＭ５０５に格納されて、外部値計算＆硬判定ブロック８へ渡される。また、第４のサブコードブロックのＢｅｔａパスメトリックに関しては、最初のステージ１で算出されたＢｅｔａパスメトリックの最終演算値が、そのまま外部値計算＆硬判定ブロック１１へ渡されることになる。
【００５５】
なお、各サブコードブロックにおけるＡｌｐｈａパスメトリックを各サブコードブロックの左端から（フォワード方向に）計算を行う。全サブコードブロックのＡｌｐｈａ計算が終った後に、サブコードブロックの右端から（バックワード方向に）、Ｂｅｔａパスメトリックの計算を行う。
【００５６】
繰返しにおける第一回目の復号を行う時、最初の初期化処理ステージにて最左端サブブロック（＃１）のＡｌｐｈａパスメトリック初期値及び最右端サブブロック（＃４）のＢｅｔａパスメトリック初期値の設定は、理想Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムと同じである。すなわち、復号トレリスにおいて、Ｓｔａｔｅ＃０のＡｌｐｈａ及びＢｅｔａ値が０、それ以外のＳｔａｔｅは−ＭＡＸ値（最小値）とする。その他の初期値はコードブロックの分割により、不定であるが、ここでは、全て０と設定する（図５の初期化処理ステージ１参照）。
【００５７】
最終ステージである初期化ステージ３では、各サブ復号器のＡｌｐｈａ，Ｂｅｔａパスメトリックの計算を行う。すなわち、初期化処理ステージ３では全Ａｌｐｈａ，Ｂｅｔａを使用する。更に、外部値計算＆硬判定処理ブロックでは、初期化処理の最終ステージで得られたＡｌｐｈａ，Ｂｅｔａパスメトリックを用いて、軟出力及び外部情報の計算が行われる。そして、各外部値計算＆硬判定処理ブロックで得られた外部情報は、インタリーバパターン情報部１３のインタリーバパターンに従ってＲＡＭ１２へ格納され、次の要素復号器へと渡されることになる。
【００５８】
なお、説明上、図６のように、ターボ復号装置は二つの要素復号器から構成されるが、これらは構成が同じであるため、本発明では１つの処理回路で実現している。
【００５９】
また、ターボ復号装置はインタリーバを用いて繰り返し復号を行うため、第Ｍ回目（Ｍは２以上の整数）の復号時には、以下のように事前初期化処理ブロックにおける最初の（ステージ１）のＡｌｐｈａ，Ｂｅｔａ初期値の設定を行う。すなわち、最左端のサブコードブロック（＃１）のＡｌｐｈａパスメトリックの初期値、最右端（＃４）のサブコードブロックのＢｅｔａパスメトリックの初期値については、理想Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムの設定と同じである（図５のステージ１における最左端と最右端の初期値を参照）。
【００６０】
、その他のＡｌｐｈａ，Ｂｅｔａパスメトリックの初期値については、以下のとおりである。
Ａｌｐｈａパスメトリックの初期値は、第Ｍ−１回目の復号時の最後の初期化処理ステージ（ステージ３）において隣のサブコードブロック（第Ｎ−１サブコードブロック）から得られたＡｌｐｈａパスメトリックの最終値である。
Ｂｅｔａパスメトリックの初期値は、第Ｍ−１回目の復号時の最後の初期化処理ステージ（ステージ３）において隣のサブコードブロック（第Ｎ＋１サブコードブロック）から得られたＢｅｔａパスメトリックの最終値である。
【００６１】
本発明が例示的な実施形態および使用方法に関連して開示される一方で、それらの多くの代替例、改変例、および変形例が本発明から逸脱することなく可能である。例えば、本発明の適用復号アルゴリズムをＭａｘ−Ｌｏｇ−ＭＡＰと想定したが、本発明に従って、最大事後確率復号（Maximum A Posteriori Probability decoding ：ＭＡＰ復号）を忠実に実現するＬｏｇ−ＭＡＰアルゴリズムも適用できる。
【００６２】
また、本発明のコードブロック長さを複数の等しい長の区間に分割すると想定したが、実際の分割では等分割できないこともあり、最後のサブコードブロック長が他のサブコードブロックより短い場合、ダミーデータの追加で前述のような並列復号処理を実現できる。更に、図５に示した初期化処理ステージの段数は、Ｋ＝３としているが、上述したように、この段数Ｋの増加に伴って、各サーブコードブロックのＡｌｐｈａやＢｅｔａのパスメトリックの初期値が改善されるが、それに伴い、ハードウェアコストや回路遅延が増大するために、実際の設計では、ステージ段数の設定と復号性能、ハードウェアコストなどを考慮して設定されることになる。
【００６３】
更にはまた、上記実施の形態の動作は、特に図示していないが、ＣＰＵによる制御部によって、図１〜３のハードウェアが、図４や図５に示す処理を行うことになるが、予めこの動作手順をプログラムとしてメモリに格納しておき、これを当該ＣＰＵ（コンピュータ）に読取らせて実行させるようにしても良いことは勿論である。
【図面の簡単な説明】
【００６４】
【図１】本発明の実施の形態による並列ターボ復号装置の機能ブロック図である。
【図２】図１における事前初期値処理部の機能ブロック図である。
【図３】図１における外部値計算＆硬判定部の機能ブロック図である。
【図４】本発明の動作の概略を示すフローチャートである。
【図５】本発明の実施の形態による復号動作のプロセス図である。
【図６】一般的なターボ符号器の構成図である。
【図７】一般的なターボ復号器の構成図である。
【図８】要素符号器の構成（ａ）とそのトレリス線図の例（ｂ）を示す図である。
【図９】Ａｌｐｈａ（ａ）＆Ｂｅｔａ（ｂ）のＡＣＳ演算例を示す図である。
【図１０】軟出力値の計算例を示す図である。
【符号の説明】
【００６５】
１  入力バッファ
４〜７  事前初期値処理ブロック
８〜１１  外部値計算＆硬判定ブロック
１２  外部情報ＲＡＭ
１３  インタリーバパタン
５０１  ＢＭ（ブランチメトリック）算出部
５０４  Ａｌｐｈａ  ＡＣＳ演算部
５０５  Ａｌｐｈａ  ＲＡＭ
５０６  Ａｌｐｈａ初期値メモリ
５１１  メモリ
５１２  Ｂｅｔａ  ＡＣＳ演算部
５１５  Ｂｅｔａ初期値メモリ
【図１】
2005210238.tif 000003
【図２】
2005210238.tif 000004
【図３】
2005210238.tif 000005
【図４】
2005210238.tif 000006
【図５】
2005210238.tif 000007
【図６】
2005210238.tif 000008
【図７】
2005210238.tif 000009
【図８】
2005210238.tif 000010
【図９】
2005210238.tif 000011
【図１０】
2005210238.tif 000012