(57)【要約】【課題】簡単な構成で短時間に誤り訂正符号を復号する。【解決手段】開示される誤り訂正符号の復号方法は、フォワード処理と、バックワード処理と、外部情報値算出処理とからなる復号を繰り返し行う誤り訂正符号の復号方法において、前記バックワード処理では、前回繰り返し復号を行った際のウィンドウ境界の第２のパスメトリック値を今回のウィンドウ境界の第２のパスメトリック値の初期値として利用して繰り返し復号を行っている。【選択図】図２
2006115534.tif 000002
【特許請求の範囲】
【請求項１】
所定情報長の受信データ及び外部情報値に基づいて、トレリス線図上の始点から終点の方向にビタビ復号を行って第１のパスメトリック値を算出するフォワード処理と、前記トレリス線図を一定期間毎に分割したウィンドウ毎に前記受信データ及び前記外部情報値に基づいて前記フォワード処理とは逆方向に前記トレリス線図上で前記ビタビ復号を行って第２のパスメトリック値を算出するバックワード処理と、前記第１及び第２のパスメトリック値に基づいた前記外部情報値の算出を行う外部情報値算出処理とからなる復号処理を前記所定情報長の受信データに対して複数回繰り返し行う誤り訂正符号の復号方法であって、
前記バックワード処理では、前回繰り返し復号を行った際の前記ウィンドウ境界の前記第２のパスメトリック値を今回の前記ウィンドウ境界の前記第２のパスメトリック値の初期値として利用して繰り返し復号を行い、かつ、
前記フォワード処理、前記バックワード処理及び前記外部情報値算出処理では、符号語を構成するシンボル列の正負を反転させたトレリス線図を用いて前記ビタビ復号を行うとともに、最小値となるパスを選択することを特徴とする誤り訂正符号の復号方法。
【請求項２】
所定情報長の受信データ及び外部情報値に基づいて、トレリス線図上の始点から終点の方向にビタビ復号を行って第１のパスメトリック値を算出するフォワード処理と、前記トレリス線図を一定期間毎に分割したウィンドウ毎に前記受信データ及び前記外部情報値に基づいて前記フォワード処理とは逆方向に前記トレリス線図上で前記ビタビ復号を行って第２のパスメトリック値を算出するバックワード処理と、前記第１及び第２のパスメトリック値に基づいた前記外部情報値の算出を行う外部情報値算出処理とからなる復号処理を前記所定情報長の受信データに対して複数回繰り返し行う誤り訂正符号の復号方法であって、
前記フォワード処理では、前回ウィンドウ分の前記フォワード処理が終了した時点の前記ウィンドウ境界の前記第１のパスメトリック値を今回の前記ウィンドウ境界の前記第１のパスメトリック値の初期値として利用して繰り返し復号を行い、前記バックワード処理では、前回繰り返し復号を行った際の前記ウィンドウ境界の前記第２のパスメトリック値を今回の前記ウィンドウ境界の前記第２のパスメトリック値の初期値として利用して繰り返し復号を行い、かつ、
前記フォワード処理、前記バックワード処理及び前記外部情報値算出処理では、符号語を構成するシンボル列の正負を反転させたトレリス線図を用いて前記ビタビ復号を行うとともに、最小値となるパスを選択することを特徴とする誤り訂正符号の復号方法。
【請求項３】
前記外部情報値として、０．５以上０．９以下の範囲の正規化係数を乗算したものを用いることを特徴とする請求項１又は２記載の誤り訂正符号の復号方法。
【請求項４】
前記外部情報値を算出する際に用いる通信路定数は、１．５以上２．５以下の範囲の値であることを特徴とする請求項１乃至３のいずれか１に記載の誤り訂正符号の復号方法。
【請求項５】
前記ウィンドウのサイズは、拘束長の４倍以上であって、要求される最大情報ビット数の２分の１以下の値であることを特徴とする請求項１乃至４のいずれか１に記載の誤り訂正符号の復号方法。
【請求項６】
コンピュータに請求項１乃至５のいずれか１に記載の機能を実現させるための誤り訂正符号の復号プログラム。
【請求項７】
所定情報長の受信データ及び外部情報値に基づいて、トレリス線図上の始点から終点の方向にビタビ復号を行って第１のパスメトリック値を算出するフォワード処理を行うフォワード処理モジュールと、前記トレリス線図を一定期間毎に分割したウィンドウ毎に前記受信データ及び前記外部情報値に基づいて前記フォワード処理とは逆方向に前記トレリス線図上で前記ビタビ復号を行って第２のパスメトリック値を算出するバックワード処理を行うバックワード処理モジュールと、前記第１及び第２のパスメトリック値に基づいた前記外部情報値を算出する外部情報値算出処理を行う外部情報値算出処理モジュールと備え、前記フォワード処理、前記バックワード処理及び前記外部情報値算出処理とからなる復号処理を前記所定情報長の受信データに対して複数回繰り返し行う誤り訂正符号の復号装置であって、
前記バックワード処理モジュールが前回の繰り返し復号時に算出した前記ウィンドウ境界の前記第２のパスメトリック値が一時保持されるメモリを有し、前記バックワード処理モジュールは、前記メモリから前記ウィンドウ境界の前記第２のパスメトリック値を読み出して今回の前記ウィンドウ境界の前記第２のパスメトリック値の初期値として利用して繰り返し復号を行い、かつ、
前記フォワード処理モジュール、前記バックワード処理モジュール及び前記外部情報値算出処理モジュールは、符号語を構成するシンボル列の正負を反転させたトレリス線図を用いて前記ビタビ復号を行うとともに、最小値となるパスを選択することを特徴とする誤り訂正符号の復号装置。
【請求項８】
所定情報長の受信データ及び外部情報値に基づいて、トレリス線図上の始点から終点の方向にビタビ復号を行って第１のパスメトリック値を算出するフォワード処理と、前記トレリス線図を一定期間毎に分割したウィンドウ毎に前記受信データ及び前記外部情報値に基づいて前記フォワード処理とは逆方向に前記トレリス線図上で前記ビタビ復号を行って第２のパスメトリック値を算出するバックワード処理とを交互に行うフォワード処理・バックワード処理共用モジュールと、
前記第１及び第２のパスメトリック値に基づいて前記外部情報値を算出する外部情報値算出処理を行う外部情報値算出処理モジュールと、
前記フォワード処理モジュールが前回ウィンドウ分の前記フォワード処理が終了した時点の前記ウィンドウ境界の前記第１のパスメトリック値が一時保持される第１のメモリと、
前記バックワード処理モジュールが前回の繰り返し復号時に算出した前記ウィンドウ境界の前記第２のパスメトリック値が一時保持される第２のメモリとを備え、
前記フォワード処理・バックワード処理共用モジュールは、前記第１のメモリから前記ウィンドウ境界の前記第１のパスメトリック値を読み出して今回の前記ウィンドウ境界の前記第１のパスメトリック値の初期値として利用して繰り返し復号を行うとともに、前記第２のメモリから前記ウィンドウ境界の前記第２のパスメトリック値を読み出して今回の前記ウィンドウ境界の前記第２のパスメトリック値の初期値として利用して繰り返し復号を行い、かつ、
前記フォワード処理モジュール、前記バックワード処理モジュール及び前記外部情報値算出処理モジュールは、符号語を構成するシンボル列の正負を反転させたトレリス線図を用いて前記ビタビ復号を行うとともに、最小値となるパスを選択することを特徴とする誤り訂正符号の復号装置。
【請求項９】
前記外部情報値として、０．５以上０．９以下の範囲の正規化係数を乗算したものを用いることを特徴とする請求項７又は８記載の誤り訂正符号の復号装置。
【請求項１０】
前記外部情報値を算出する際に用いる通信路定数は、１．５以上２．５以下の範囲の値であることを特徴とする請求項７乃至９のいずれか１に記載の誤り訂正符号の復号装置。
【請求項１１】
前記ウィンドウのサイズは、拘束長の４倍以上であって、要求される最大情報ビット数の２分の１以下の値であることを特徴とする請求項７乃至１０のいずれか１に記載の誤り訂正符号の復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、誤り訂正符号を復号する誤り訂正符号の復号方法、そのプログラム及びその装置に関し、特に、携帯電話などのデジタル移動体通信システム等に適用して好適な誤り訂正符号の復号方法、そのプログラム及びその装置に関する。
【背景技術】
【０００２】
誤り訂正符号としては、最近では、情報理論の限界（これをシャノン限界という）に近い伝送特性を現実的な処理で実現するターボ符号が開発されている。以下、ターボ符号について説明する。
まず、図１７に並列連接畳込み符号(ＰＣＣＣｓ： Parallel Concatenated Convolutional Codes)のターボ符号（Turbo Codes）を生成するための符号化装置の一例を示す。この例の符号化装置は、２個の畳込み符号化器１及び２をインターリーバ３を介して並列に連接して構成されている。畳込み符号化器１は、外部から供給される情報系列（組織部）ｕから第１冗長部ｐを符号化する。インターリーバ３は、組織部ｕの各ビットの順序を並べ替えた組織部ｕ'を生成（これをインターリーブという）し、畳込み符号化器２に供給する。畳込み符号化器２は、組織部ｕ'から第２冗長部ｐ'を符号化する。組織部ｕと第１冗長部ｐの組を第１要素符号（ｕ，ｐ）と呼び、組織部ｕ'と第２冗長部ｐ'の組を第２要素符号（ｕ'，ｐ'）と呼ぶ。
【０００３】
一方、ターボ符号の復号方法は、第１要素符号（ｕ，ｐ）と第２要素符号（ｕ'，ｐ'）との間で信頼度情報である事前情報を交換しながら繰り返し復号を行うことを特徴とする復号方法である。このターボ符号の復号方法には軟入力軟出力復号方法が用いられている。軟入力軟出力復号方法には、大きく分けて、ＳＯＶＡ（soft-output Viterbi algorithm）復号方法と、ＭＡＰ（maximum a posteriori）復号方法の２つの方法がある。以下では、ＭＡＰ復号方法の一種であるＭａｘ−Ｌｏｇ−ＭＡＰアルゴリズムについて説明する。Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムでは、トレリス（Trellis）線図上でビタビ復号（Viterbi Decoding）を行い、パスメトリック（Path Metric）値を算出する。
【０００４】
図１８にトレリス線図を、図１９に通常の復号の手順を示す。トレリス線図上の始点から終点の方向にビタビ復号を行ってパスメトリック値を算出する処理をフォワード処理といい、フォワード処理で算出されるパスメトリック値をαパスメトリック値（αＰＭ）（第１のパスメトリック値）と呼ぶ。αパスメトリック値は、図１９に示すメモリに一時記憶される。一方、フォワード処理とは逆方向にビタビ復号を行ってパスメトリック値を算出する処理をバックワード処理といい、バックワード処理で算出されるパスメトリック値をβパスメトリック値（βＰＭ）（第２のパスメトリック値）と呼ぶ。また、αパスメトリック値、βパスメトリック値及びブランチメトリック値から事前情報を算出し、さらに外部情報値を算出する処理を外部情報値算出処理という。ここで、外部情報値とは、情報系列に対する信頼度の増分を表す。この外部情報値は、実際上、上記した第１要素符号（ｕ，ｐ）と第２要素符号（ｕ'，ｐ'）との間の復号処理で交換される事前情報として用いられる。
【０００５】
以下、Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムについて詳細に説明する。まず、時点ｋにおける畳込み符号化器の出力は、組織符号であるために、（ｕｋ，ｐｋ）∈｛±１｝（ｐｋは冗長部）とし、対応する畳込み復号器の入力をｙｋ＝（ｙｋｕ，ｙｋｐ）とする。また、推定情報系列をｕｈｋ＝（ｕｈ１，ｕｈ２，…，ｕｈＮ）とする。図２０にトレリス線図上の時点（ｋ−１）から時点ｋへ遷移する場合における遷移モデルを示す。時点ｋにおけるトレリス線図上の特定の状態を状態Ｓｋ、時点（ｋ−１）におけるトレリス線図上の特定の状態を状態Ｓｋ−１と定義すると、Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムにおける事前情報Ｌ（ｕｈｋ）は、式（１）で表される。
【０００６】
【数１】
2006115534.tif 000003
【０００７】
式（１）において、ｐ（ｓｋ−１，ｓｋ、ｙ）は、畳込み復号器の入力ｙと状態ｓｋ−１から状態ｓｋへの遷移に関する同時生起確率である。すなわち、ｋ番目の情報ビットｕｋに関わる事前情報Ｌ（ｕｈｋ）は、ｕｋ＝＋１により生じるすべての遷移（ｓｋ−１→ｓｋ）に関する同時生起確率ｐ（ｓｋ−１，ｓｋ、ｙ）の中で最大の確率と、ｕｋ＝−１により生じるすべての遷移（ｓｋ−１→ｓｋ）に関する同時生起確率ｐ（ｓｋ−１，ｓｋ、ｙ）の中で最大の確率との差において定義される。時点ｉから供給される時点ｊまでの畳込み復号器の入力を式（２）で表し、符号語長をＮとすると、無記憶通信路での伝送において同時生起確率ｐ（ｓｋ−１，ｓｋ、ｙ）は、式（３）で表される独立な確率の和として与えられる。
Ｙｉｊ＝（ｙｉ，ｙｉ＋１，…，ｙｊ）……（２）
ｐ（ｓｋ−１，ｓｋ、ｙ）＝ｐ（ｓｋ−１，Ｙ１ｋ−１）＋ｐ（ｓｋ，ｙｋ｜ｓｋ−１）＋ｐ（ＹｋＮ｜ｓｋ）……（３）
式（３）において、右辺の各項を左から順にαｋ−１（ｓｋ−１）、γ（ｓｋ、ｓｋ−１）及びβ（ｓｋ）とおく。これらのうち、γ（ｓｋ、ｓｋ−１）は、存在するすべての遷移（ｓｋ−１→ｓｋ）に関するブランチメトリック値である。また、αｋ−１（ｓｋ−１）はフォワード処理で算出されるパスメトリック値、β（ｓｋ）はバックワード処理で算出されるβパスメトリック値であり、各々再帰的に式（４）及び式（５）により算出することができる。
【０００８】
【数２】
2006115534.tif 000004
【０００９】
【数３】
2006115534.tif 000005
【００１０】
図２１にトレリス線図上の時点（ｋ−１）から時点ｋへ遷移する場合におけるαｋ−１（ｓｋ−１）及びβ（ｓｋ）の算出モデルを示す。ただし、トレリス線図上の始点と終点は一意であり、式（６）で示すように初期化される。
【００１１】
【数４】
2006115534.tif 000006
【００１２】
また、外部情報値は、事前情報Ｌ（ｕｈｋ）から式（７）及び式（８）を用いて算出される。
Ｌｉ（ｕｋ）＝Ｌａ（ｕｋ）＋Ｌｃ×ｙｋｕ……（７）
Ｌｅ（ｕｈｋ）＝Ｌ（ｕｈｋ）−Ｌｉ（ｕｋ）……（８）
式（７）で表されるＬｉ（ｕｋ）は、式（８）で表される外部情報Ｌｅ（ｕｈｋ）に対して内部情報と呼ばれる。また、式（７）において、Ｌａ（ｕｋ）は、他方の要素符号の復号の過程において算出された外部情報値である。さらに、Ｌｃは、通信路により決まる定数であり、白色ガウス通信路（平均０、分散Ｎ０／２、信号電力Ｅｂ）の場合では、式（９）で表される。
Ｌｃ＝４Ｅｂ／Ｎ０……（９）
この定数Ｌｃは、通信路の雑音状態に依存する値である。
【００１３】
以上説明した通常のターボ符号の復号方法においては、トレリス線図の全時点及び全状態におけるパスメトリック値を一旦保持する必要があり、その保持のためのメモリの記憶容量が非常に大きくなるという問題があった。この問題を解決するために、トレリス線図の一定時点（これをウィンドウという）を用いて局所的な復号を行い、上記したパスメトリック値を保持するためのメモリの記憶容量を削減する方法が提案されている。この場合、トレリス線図の始点から復号を開始する通常の復号シーケンスにおいては、局所的なバックワード処理におけるパスメトリック値の初期値の与え方が問題となる。この問題に関しては、まずウィンドウ先のすべての状態を等確率としてバックワード処理を行い、このバックワード処理によりパスメトリック値の初期値を得る期間を学習期間とする復号方法（これをスライディングウィンドウ方法という）が、"Soft-Output Decoding Algorithms for Continuous Decoding of Parallel Concatenated Convolutional Codes", S. Benedetto et al., Proceeding of IEEE International Conference on Communications, pp. 112-117, 1996に開示されている。このスライディングウィンドウ方法において、１サイクルごとに軟出力生成を行う１つの方法として、バックワード処理モジュールをウィンドウ時点分だけ設け、それらをパイプライン化する復号装置が、"VLSI architectures for turbo codes", IEEE Transactions on VLSI systems, pp. 369-379, 1999に開示されている。しかし、この復号装置は、ウィンドウ時点分のバックワード処理モジュールを設ける必要があり、その回路規模が増大するという欠点がある。
【００１４】
図２２は、"An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes", A. J. Viterbi, IEEE Journal on Selected Areas on Communications, pp. 260-264, 1998から導かれる従来のターボ符号の復号装置の構成例を示すブロック図である。この例のターボ符号の復号装置は、上記したスライディングウィンドウ方法において学習処理を行う学習処理モジュールが設けられており、ウィンドウの大きさの時点分だけタイミングをずらして動作する復号スケジュールが構成されることにより、１サイクルごとの軟出力生成をすることができる。この例のターボ符号の復号装置は、フォワード処理モジュール１１と、バックワード処理モジュール１２と、学習処理モジュール１３と、外部情報値算出処理モジュール１４と、スイッチ１５と、メモリ１６〜１９とから構成されている。
【００１５】
フォワード処理モジュール１１は、フォワード処理を行う。バックワード処理モジュール１２は、バックワード処理を行う。学習処理モジュール１３は、学習処理を行う。外部情報値算出処理モジュール１４は、外部情報値を算出する。スイッチ１５は、通常はバックワード処理モジュール１２側に接続されているが、学習モジュール１３による学習結果をパスメトリック値の初期値としてバックワード処理モジュール１１に供給する場合には学習モジュール１３側に接続される。メモリ１６は、フォワード処理モジュール１１、バックワード処理モジュール１２及び学習処理モジュール１３のそれぞれに要素符号及び外部情報値を供給するために設けられている。メモリ１７は、フォワード処理モジュール１１が算出したパスメトリック値を外部情報値算出処理モジュール１４に供給するために設けられている。メモリ１８は、外部情報値算出処理モジュール１４が算出した外部情報値をメモリ１６に供給するために設けられている。すなわち、メモリ１８は、第１要素符号（ｕ，ｐ）と第２要素符号（ｕ'，ｐ'）との間で事前情報として用いられる外部情報値を交換するために設けられている。メモリ１９は、インターリーブパターンＩＬＰを一時保持しておくために設けられている。なお、メモリ１６及び１９は４面バッファ構造、メモリ１７及び１８は２面バッファ構造となっている。
【００１６】
次に、上記構成のターボ符号の復号装置の動作について、図２３を参照して説明する。図２３において、ＦＷＰはフォワード処理を、ＢＷＰはバックワード処理を、ＳＴＰは学習処理をそれぞれ表している。
（１）  時間０〜２Ｌｔでは、後述する学習処理を行うために、図２３に示すトレリス線図上の０時点（始点）から２Ｌｐ時点までの要素符号及び外部情報をメモリ１６に一時保持するための前処理を行う。なお、第２要素符号（ｕ'，ｐ'）を復号する場合は、上記前処理の他、インターリーブパターンＩＬＰをメモリ１９に一時保持する処理を行う必要がある。
（２）  時間２Ｌｔ〜３Ｌｔでは、フォワード処理モジュール１１は、図２３に示すトレリス線図上の０時点（始点）からＬｐ時点までフォワード処理を行う。また同時に、学習処理モジュール１３は、図２３に示すトレリス線図上の２Ｌｐ時点からＬｐ時点まで学習処理を行う。なお、学習処理におけるパスメトリック値の初期値はウィンドウ先のすべての状態を等確率とする。
【００１７】
（３）  時間３Ｌｔ〜４Ｌｔでは、フォワード処理モジュール１１は、図２３に示すトレリス線図上のＬｐ時点から２Ｌｐ時点までフォワード処理を行う。また同時に、バックワード処理モジュール１２は、図２３に示すトレリス線図上の上記（２）に示す学習処理に続けてＬｐ時点から０時点（始点）までのバックワード処理を行う。また同時に、外部情報値算出処理モジュール１４は、外部情報値を算出する。さらに同時に、学習処理モジュール１３は、図２３に示すトレリス線図上の３Ｌｐ時点から２Ｌｐ時点までの学習処理を行う。
（４）  時間４Ｌｔ〜５Ｌｔでは、フォワード処理モジュール１１は、図２３に示すトレリス線図上の２Ｌｐ時点から３Ｌｐ時点までフォワード処理を行う。また同時に、バックワード処理モジュール１２は、図２３に示すトレリス線図上の上記（３）に示す学習処理に続けて２Ｌｐ時点からＬｐ時点までのバックワード処理を行う。また同時に、外部情報値算出処理モジュール１４は、外部情報値を算出する。さらに同時に、学習処理モジュール１３は、図２３に示すトレリス線図上の４Ｌｐ時点から３Ｌｐ時点までの学習処理を行う。
【００１８】
（５）  時間５Ｌｔ〜（Ｎｔ−Ｍｔ＋３Ｌｔ）（Ｍｔ≦Ｌｔ）では、上記した（３）及び（４）の処理と同様の処理を行う。
（６）  時間（Ｎｔ−Ｍｔ＋３Ｌｔ）〜（Ｎｔ＋３Ｌｔ）では、バックワード処理モジュール１２は、図２３に示すトレリス線図上の（Ｎｐ−Ｍｐ）時点からＮｐ時点（終点）までのバックワード処理を行う。また同時に、外部情報値算出処理モジュール１４は、外部情報値を算出する。
（７）  以上説明した（１）〜（６）の処理を第１要素符号（ｕ，ｐ）に対する復号処理とし、続いて第２要素符号（ｕ'，ｐ'）に対する復号処理を同様に行い、繰り返し復号１回とする。
（８）  適当な回数（１０回程度）の繰り返し復号を終了した後に、第２要素符号（ｕ'，ｐ'）に対する復号処理の対数尤度比（ＬＬＲ： Log Likelihood Ratio）の符号ビットを用いて各組織部ｕの硬判定を行う。
【非特許文献１】"Soft-Output Decoding Algorithms for Continuous Decoding of Parallel Concatenated Convolutional Codes", S. Benedetto et al., Proceeding of IEEE International Conference on Communications, pp. 112-117, 1996
【非特許文献２】"VLSI architectures for turbo codes", IEEE Transactions on VLSI systems, pp. 369-379, 1999
【非特許文献３】"An Intuitive Justification and a Simplified Implementation of the MAP Decoder for Convolutional Codes", A. J. Viterbi, IEEE Journal on Selected Areas on Communications, pp. 260-264, 1998
【発明の開示】
【発明が解決しようとする課題】
【００１９】
しかしながら、従来のターボ符号の復号装置においては、学習処理モジュール１３を設ける必要がある。また、フォワード処理モジュール１１、バックワード処理モジュール１２及び学習処理モジュール１３のそれぞれに要素符号及び外部情報値を供給するためのメモリ１６と、インターリーブパターンＩＬＰを一時保持しておくためのメモリ１９は、４面バッファ構造とする必要がある。さらに、復号を開始するための前処理である学習処理においては、２Ｌｐ時点分の要素符号及び外部情報値をメモリに一時保持する期間が必要である。
このような不都合は、ターボ符号を復号する復号装置だけでなく、一般に、畳込み符号を用いた符号に対して、ＭＡＰ系の軟入力軟出力復号方法を用いて繰返し復号を行う復号装置においても同様に発生するおそれがある。
【００２０】
この発明は、上述の事情に鑑みてなされたもので、簡単な構成で短時間に誤り訂正符号を復号することができる誤り訂正符号の復号方法、そのプログラム及びその装置を提供することを目的としている。
【課題を解決するための手段】
【００２１】
上記課題を解決するために、請求項１記載の発明は、所定情報長の受信データ及び外部情報値に基づいて、トレリス線図上の始点から終点の方向にビタビ復号を行って第１のパスメトリック値を算出するフォワード処理と、前記トレリス線図を一定期間毎に分割したウィンドウ毎に前記受信データ及び前記外部情報値に基づいて前記フォワード処理とは逆方向に前記トレリス線図上で前記ビタビ復号を行って第２のパスメトリック値を算出するバックワード処理と、前記第１及び第２のパスメトリック値に基づいた前記外部情報値の算出を行う外部情報値算出処理とからなる復号処理を前記所定情報長の受信データに対して複数回繰り返し行う誤り訂正符号の復号方法に係り、前記バックワード処理では、前回繰り返し復号を行った際の前記ウィンドウ境界の前記第２のパスメトリック値を今回の前記ウィンドウ境界の前記第２のパスメトリック値の初期値として利用して繰り返し復号を行い、かつ、前記フォワード処理、前記バックワード処理及び前記外部情報値算出処理でが、符号語を構成するシンボル列の正負を反転させたトレリス線図を用いて前記ビタビ復号を行うとともに、最小値となるパスを選択することを特徴としている。
【００２２】
また、請求項２記載の発明は、所定情報長の受信データ及び外部情報値に基づいて、トレリス線図上の始点から終点の方向にビタビ復号を行って第１のパスメトリック値を算出するフォワード処理と、前記トレリス線図を一定期間毎に分割したウィンドウ毎に前記受信データ及び前記外部情報値に基づいて前記フォワード処理とは逆方向に前記トレリス線図上で前記ビタビ復号を行って第２のパスメトリック値を算出するバックワード処理と、前記第１及び第２のパスメトリック値に基づいた前記外部情報値の算出を行う外部情報値算出処理とからなる復号処理を前記所定情報長の受信データに対して複数回繰り返し行う誤り訂正符号の復号方法に係り、前記フォワード処理では、前回ウィンドウ分の前記フォワード処理が終了した時点の前記ウィンドウ境界の前記第１のパスメトリック値を今回の前記ウィンドウ境界の前記第１のパスメトリック値の初期値として利用して繰り返し復号を行い、前記バックワード処理では、前回繰り返し復号を行った際の前記ウィンドウ境界の前記第２のパスメトリック値を今回の前記ウィンドウ境界の前記第２のパスメトリック値の初期値として利用して繰り返し復号を行い、かつ、前記フォワード処理、前記バックワード処理及び前記外部情報値算出処理では、符号語を構成するシンボル列の正負を反転させたトレリス線図を用いて前記ビタビ復号を行うとともに、最小値となるパスを選択することを特徴としている。
【００２３】
また、請求項３記載の発明は、請求項１又は２記載の誤り訂正符号の復号方法に係り、上記外部情報値として、０．５以上０．９以下の範囲の正規化係数を乗算したものを用いることを特徴としている。
【００２４】
また、請求項４記載の発明は、請求項１乃至３のいずれか１に記載の誤り訂正符号の復号方法に係り、上記外部情報値を算出する際に用いる通信路定数は、１．５以上２．５以下の範囲の値であることを特徴としている。
【００２５】
また、請求項５記載の発明は、請求項１乃至４のいずれか１に記載の誤り訂正符号の復号方法に係り、上記ウィンドウのサイズは、拘束長の４倍以上であって、要求される最大情報ビット数の２分の１以下の値であることを特徴としている。
【００２６】
また、請求項６記載の発明は、誤り訂正符号の復号プログラムに係り、コンピュータに請求項１乃至５のいずれか１に記載の機能を実現させることを特徴としている。
【００２７】
また、請求項７記載の発明は、所定情報長の受信データ及び外部情報値に基づいて、トレリス線図上の始点から終点の方向にビタビ復号を行って第１のパスメトリック値を算出するフォワード処理を行うフォワード処理モジュールと、前記トレリス線図を一定期間毎に分割したウィンドウ毎に前記受信データ及び前記外部情報値に基づいて前記フォワード処理とは逆方向に前記トレリス線図上で前記ビタビ復号を行って第２のパスメトリック値を算出するバックワード処理を行うバックワード処理モジュールと、前記第１及び第２のパスメトリック値に基づいた前記外部情報値を算出する外部情報値算出処理を行う外部情報値算出処理モジュールと備え、前記フォワード処理、前記バックワード処理及び前記外部情報値算出処理とからなる復号処理を前記所定情報長の受信データに対して複数回繰り返し行う誤り訂正符号の復号装置に係り、前記バックワード処理モジュールが前回の繰り返し復号時に算出した前記ウィンドウ境界の前記第２のパスメトリック値が一時保持されるメモリを有し、前記バックワード処理モジュールは、前記メモリから前記ウィンドウ境界の前記第２のパスメトリック値を読み出して今回の前記ウィンドウ境界の前記第２のパスメトリック値の初期値として利用して繰り返し復号を行い、かつ、前記フォワード処理モジュール、前記バックワード処理モジュール及び前記外部情報値算出処理モジュールは、符号語を構成するシンボル列の正負を反転させたトレリス線図を用いて前記ビタビ復号を行うとともに、最小値となるパスを選択することを特徴としている。
【００２８】
また、請求項８記載の発明は、誤り訂正符号の復号装置に係り、所定情報長の受信データ及び外部情報値に基づいて、トレリス線図上の始点から終点の方向にビタビ復号を行って第１のパスメトリック値を算出するフォワード処理と、前記トレリス線図を一定期間毎に分割したウィンドウ毎に前記受信データ及び前記外部情報値に基づいて前記フォワード処理とは逆方向に前記トレリス線図上で前記ビタビ復号を行って第２のパスメトリック値を算出するバックワード処理とを交互に行うフォワード処理・バックワード処理共用モジュールと、前記第１及び第２のパスメトリック値に基づいて前記外部情報値を算出する外部情報値算出処理を行う外部情報値算出処理モジュールと、前記フォワード処理モジュールが前回ウィンドウ分の前記フォワード処理が終了した時点の前記ウィンドウ境界の前記第１のパスメトリック値が一時保持される第１のメモリと、前記バックワード処理モジュールが前回の繰り返し復号時に算出した前記ウィンドウ境界の前記第２のパスメトリック値が一時保持される第２のメモリとを備え、前記フォワード処理・バックワード処理共用モジュールは、前記第１のメモリから前記ウィンドウ境界の前記第１のパスメトリック値を読み出して今回の前記ウィンドウ境界の前記第１のパスメトリック値の初期値として利用して繰り返し復号を行うとともに、前記第２のメモリから前記ウィンドウ境界の前記第２のパスメトリック値を読み出して今回の前記ウィンドウ境界の前記第２のパスメトリック値の初期値として利用して繰り返し復号を行い、かつ、前記フォワード処理モジュール、前記バックワード処理モジュール及び前記外部情報値算出処理モジュールは、符号語を構成するシンボル列の正負を反転させたトレリス線図を用いて前記ビタビ復号を行うとともに、最小値となるパスを選択することを特徴としている。
【００２９】
また、請求項９記載の発明は、請求項７又は８記載の誤り訂正符号の復号装置に係り、上記外部情報値として、０．５以上０．９以下の範囲の正規化係数を乗算したものを用いることを特徴としている。
【００３０】
また、請求項１０記載の発明は、請求項７乃至９のいずれか１に記載の誤り訂正符号の復号装置に係り、上記外部情報値を算出する際に用いる通信路定数は、１．５以上２．５以下の範囲の値であることを特徴としている。
【００３１】
また、請求項１１記載の発明は、請求項７乃至１０のいずれか１に記載の誤り訂正符号の復号装置に係り、上記ウィンドウのサイズは、拘束長の４倍以上であって、要求される最大情報ビット数の２分の１以下の値であることを特徴としている。
【発明の効果】
【００３２】
この発明の構成によれば、フォワード処理と、バックワード処理と、外部情報値算出処理とからなる復号を繰り返し行う誤り訂正符号の復号方法において、バックワード処理では、前回繰り返し復号を行った際のウィンドウ境界の第２のパスメトリック値を今回のウィンドウ境界の第２のパスメトリック値の初期値として利用して繰り返し復号を行っているので、簡単な構成で短時間に誤り訂正符号を復号することができる。
また、この発明の別の構成によれば、コンピュータが誤り訂正符号の復号プログラムを実行するので、コンピュータの演算量、記憶装置の記憶容量及びコンピュータにおける消費電流を削減することができ、処理時間も短縮することができる。
また、この発明の別の構成によれば、フォワード処理、バックワード処理及び外部情報値算出処理では、符号語を構成するシンボル列の正負を反転させたトレリス線図を用いてビタビ復号を行うとともに、最小値となるパスを選択しているので、復号装置を構成するメモリの記憶容量や回路規模をより削減することができる。
【発明を実施するための最良の形態】
【００３３】
フォワード処理、バックワード処理及び外部情報値算出処理では、符号語を構成するシンボル列の正負を反転させたトレリス線図を用いて前記ビタビ復号を行うとともに、最小値となるパスを選択する。
【実施例】
【００３４】
以下、図面を参照して、この発明の実施の形態について説明する。説明は、参考例及び実施例を用いて具体的に行う。
Ａ．第１の参考例
まず、この発明の第１の参考例について説明する。
図１は、この発明の第１の参考例であるターボ符号の復号装置の構成を示すブロック図である。
この例のターボ符号の復号装置は、フォワード処理モジュール２１と、バックワード処理モジュール２２と、外部情報値算出処理モジュール２３と、メモリ２４〜２８とから構成されている。
【００３５】
フォワード処理モジュール２１は、フォワード処理を行う。バックワード処理モジュール２２は、バックワード処理を行う。外部情報値算出処理モジュール２３は、外部情報値を算出する。メモリ２４は、バックワード処理モジュール２２に要素符号及び外部情報値を供給するために設けられている。メモリ２５は、バックワード処理モジュール２２が算出したウィンドウ境界のパスメトリック値を一時保持するために設けられている。メモリ２６は、フォワード処理モジュール２１が算出したパスメトリック値を外部情報値算出処理モジュール２３に供給するために設けられている。メモリ２７は、外部情報値算出処理モジュール２３が算出した外部情報値をメモリ２４に供給するために設けられている。すなわち、メモリ２７は、第１要素符号（ｕ，ｐ）と第２要素符号（ｕ'，ｐ'）との間で事前情報として用いられる外部情報値を交換するために設けられている。メモリ２８は、インターリーブパターンＩＬＰを一時保持しておくために設けられている。
なお、メモリ２４、２６、２７及び２８は２面バッファ構造となっている。
【００３６】
次に、上記構成のターボ符号の復号装置の動作について、図２を参照して説明する。図２において、ＦＷＰはフォワード処理を、ＢＷＰはバックワード処理をそれぞれ表している。
（１）  時間０〜Ｌｔでは、フォワード処理モジュール２１は、図２に示すトレリス線図上の０時点（始点）からＬｐ時点までフォワード処理を行う。
（２）  時間Ｌｔ〜２Ｌｔでは、フォワード処理モジュール２１は、図２に示すトレリス線図上の上記（１）に示すフォワード処理に続けてＬｐ時点から２Ｌｐ時点までフォワード処理を行う。また同時に、バックワード処理モジュール２２は、図２に示すトレリス線図上のＬｐ時点から０時点（始点）までバックワード処理を行う。また同時に、外部情報値算出処理モジュール２３は、外部情報値を算出する。この時、バックワード処理におけるウィンドウ境界（Ｌｐ時点）のβパスメトリック値の初期値はウィンドウ先のすべての状態を等確率とする。
【００３７】
（３）  時間２Ｌｔ〜３Ｌｔでは、フォワード処理モジュール２１は、図２に示すトレリス線図上の上記（２）に示すフォワード処理に続けて２Ｌｐ時点から３Ｌｐ時点までフォワード処理を行う。また同時に、バックワード処理モジュール２２は、図２に示すトレリス線図上の２Ｌｐ時点からＬｐ時点までバックワード処理を行う。また同時に、外部情報値算出処理モジュール２３は、外部情報値を算出する。この時、バックワード処理におけるウィンドウ境界（２Ｌｐ時点）のβパスメトリック値の初期値も、上記した（２）の場合と同様に、ウィンドウ先のすべての状態を等確率とする。また、図２に示すトレリス線図上のウィンドウ境界（Ｌｐ時点）のβパスメトリック値は、次回繰り返し復号時におけるバックワード処理におけるβパスメトリック値の初期値として利用するために、メモリ２５に一時保持される（図２（１）参照）。
（４）  時間３Ｌｔ〜（Ｎｔ−Ｍｔ＋Ｌｔ）（Ｍｔ≦Ｌｔ）では、フォワード処理モジュール２１、バックワード処理モジュール２２及び外部情報値算出処理モジュール２３は、フォワード処理が図２に示すトレリス線図上のＮｐ時点（終点）に達するまで上記した（３）の処理を繰り返す。
【００３８】
（５）  時間（Ｎｔ−Ｍｔ＋Ｌｔ）〜（Ｎｔ＋Ｌｔ）では、バックワード処理モジュール２２は、図２に示すトレリス線図上のＮｐ時点（終点）から（Ｎｐ−Ｍｐ）（Ｍｐ≦Ｌｐ）時点までバックワード処理を行う。また同時に、外部情報値算出処理モジュール２３は、外部情報値を算出する。また、図２に示すトレリス線図上のウィンドウ境界（（Ｎｐ−Ｍｐ）時点）におけるβパスメトリック値は、次回繰り返し復号時におけるバックワード処理のβパスメトリック値の初期値として利用するために、メモリ２５に一時保持される。
（６）  以上説明した（１）〜（５）の処理を第１要素符号（ｕ，ｐ）に対する復号処理とし、続いて第２要素符号（ｕ'，ｐ'）に対する復号処理を同様に行い、繰り返し復号１回とする。これ以降は、バックワード処理モジュール２２は、バックワード処理におけるウィンドウ境界のβパスメトリック値の初期値として前回繰り返し復号時においてメモリ２５に一時保持されたウィンドウ境界におけるβパスメトリック値を利用して、繰り返し復号処理を行う（図２（２）参照）。
（７）  適当な回数（１０回程度）の繰り返し復号を終了した後に、第２要素符号（ｕ'，ｐ'）に対する復号処理の対数尤度比（ＬＬＲ）（事前情報）の符号ビットを用いて各組織部ｕの硬判定を行う。
【００３９】
ここで、図３に、この例の復号装置の復号特性（曲線ａ）と、従来のスライディングウィンドウ方法による復号装置の復号特性（曲線ｂ）とを比較するための図を示す。縦軸はビット誤り率ＢＥＲ（Bit Error Rate）及びブロック誤り率ＢＬＥＲ（Block Error Rate）である。また、横軸は復号装置直前における信号対雑音比を通信路のシンボル当たり情報ビット数で割った値である（正確には、１ビット当たりの信号エネルギＥｂと、片側パワスペクトル密度Ｎ０との比Ｅｂ／Ｎ０である）。データ数は６５６、繰り返し復号回数は８回、ウィンドウサイズは６４時点である。図３から分かるように、スライディングウィンドウ方法による復号装置の復号特性（曲線ｂ）と、この例の復号装置の復号特性（曲線ａ）との間には有意的な差はない。
【００４０】
また、外部情報値に乗算する正規化係数（外部情報値正規化係数）、外部情報値を算出する際に組織部に乗算する通信路定数、ウィンドウサイズのそれぞれをパラメータにしてシミュレーションを行った結果を図４〜図６に示す。このシミュレーションは、第３世代の技術標準を策定するためのパートナーシップ・プロジェクトである３ＧＰＰ（3rd Generation Partnership Project）において規定されている「ＲＭＣ６４」の条件において、繰り返し復号回数を８回とし、Ｅｂ／Ｎ０が０．４ｄＢである場合及びＥｂ／Ｎ０が０．８ｄＢである場合のそれぞれについて行った。
図４は、外部情報値正規化係数に対するビット誤り率ＢＥＲ及びブロック誤り率ＢＬＥＲの特性のシミュレーション結果である。図４において、曲線ａはＥｂ／Ｎ０が０．４ｄＢである場合の外部情報値正規化係数に対するビット誤り率ＢＥＲの特性、曲線ｂはＥｂ／Ｎ０が０．８ｄＢである場合の外部情報値正規化係数に対するビット誤り率ＢＥＲの特性、曲線ｃはＥｂ／Ｎ０が０．４ｄＢである場合の外部情報値正規化係数に対するブロック誤り率ＢＬＥＲの特性、曲線ｂはＥｂ／Ｎ０が０．８ｄＢである場合の外部情報値正規化係数に対するブロック誤り率ＢＬＥＲの特性である。Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムにおいては、ＭＡＰアルゴリズムに比べて大きな軟出力値を出力する傾向に有る。よって、外部情報値に正規化係数を乗算することによりＭＡＰアルゴリズムの復号特性に近づけることができる。図４から分かるように、外部情報値正規化係数が０．５〜０．９の範囲、特に、０．７程度である場合に最良の復号特性が得られる。
【００４１】
また、図５は、通信路定数に対するビット誤り率ＢＥＲ及びブロック誤り率ＢＬＥＲの特性のシミュレーション結果である。図５において、曲線ａはＥｂ／Ｎ０が０．４ｄＢである場合の通信路定数に対するビット誤り率ＢＥＲの特性、曲線ｂはＥｂ／Ｎ０が０．８ｄＢである場合の通信路定数に対するビット誤り率ＢＥＲの特性、曲線ｃはＥｂ／Ｎ０が０．４ｄＢである場合の通信路定数に対するブロック誤り率ＢＬＥＲの特性、曲線ｄはＥｂ／Ｎ０が０．８ｄＢである場合の通信路定数に対するブロック誤り率ＢＬＥＲの特性である。通信路定数は通信状態（Ｅｂ／Ｎ０）の値により決まるがこの例では定数としている。図５から分かるように、通信路定数が１．５〜２．５の範囲、特に、２程度である場合に最良の復号特性が得られる。
【００４２】
さらに、図６は、ウィンドウサイズに対するビット誤り率ＢＥＲ及びブロック誤り率ＢＬＥＲの特性のシミュレーション結果である。図６において、曲線ａはＥｂ／Ｎ０が０．４ｄＢである場合のウィンドウサイズに対するビット誤り率ＢＥＲの特性、曲線ｂはＥｂ／Ｎ０が０．８ｄＢである場合のウィンドウサイズに対するビット誤り率ＢＥＲの特性、曲線ｃはＥｂ／Ｎ０が０．４ｄＢである場合のウィンドウサイズに対するブロック誤り率ＢＬＥＲの特性、曲線ｄはＥｂ／Ｎ０が０．８ｄＢである場合のウィンドウサイズに対するブロック誤り率ＢＬＥＲの特性である。図６から分かるように、ウィンドウサイズを大きくすると復号特性が向上するが、収束傾向が見られる。すなわち、ウィンドウサイズが拘束長の４倍以上であって、要求される最大情報ビット数の２分の１以下の値である場合に、回路規模を増大させることなく、良好な復号特性が得られる。
【００４３】
このように、この例の構成によれば、前回繰り返し復号時における、バックワード処理において得られるウィンドウ境界のβパスメトリック値を一時保持するメモリ２５を設け、このβパスメトリック値を、次回繰り返し復号時における、バックワード処理におけるβパスメトリック値の初期値として利用している。したがって、図２２に示す従来のターボ符号の符号化装置では必要であったパスメトリック値の初期値を算出するための学習処理が不要となる。これにより、図２２に示す学習処理モジュール１３が不要となり、また４面バッファ構造であったメモリ１６及び１９（図２２参照）に換えて、２面バッファ構造のメモリ２４及び２８を設けるだけで１サイクルごとの軟出力生成を実現することができる。さらに、従来のターボ符号の符号化装置では必要であった前処理期間も不要となる。
さらに、フォワード処理モジュール２１とバックワード処理モジュール２２が独立に設けられており、バックワード処理をフォワード処理からウィンドウ分遅らせて開始しているので、１サイクルごとの外部情報値算出が可能である。
【００４４】
ここで、具体例を示す。３ＧＰＰでは最大情報ビット数は５，１１４ビットである。したがって、受信データのビット幅が８ビット、ウィンドウサイズが１２８の場合、この例の復号装置を構成するメモリ２５の記憶容量は、βパスメトリック値の初期値（１３ビット）を一時保持するために、８，３２０（４０ワード×１３ビット×８状態×２）ビット分が必要となる。しかし、従来必要であった、要素符号（１６ビット）及び外部情報値（１４ビット）を一時保持するための７，６８０（１２８ワード×（１６ビット＋１４ビット）×２）ビットの記憶容量を有するメモリと、インターリーブパターン（１３ビット）を一時保持するための３，３２８（１２８ワード×１３ビット×２）ビットの記憶容量を有するメモリとは不要となる。よって、この例の構成によれば、合計で（７，６８０＋３，３２８）−８，３２０＝２，６８８ビットの記憶容量を削減することができる。
一方、論理回路に関しては、図２２に示す学習処理モジュール１３が１個分、約５ｋゲートの回路規模を削減することができる。また、処理時間に関しては、ウィンドウサイズをＬとし、１サイクルごとに軟出力を生成すると、第１要素符号及び第２要素符号を復号すると、それぞれ２Ｌ・ＣＫ（ＣＫは基本クロックの１周期の時間）だけ短縮することができる。例えば、ウィンドウサイズが１２８の場合、３ＧＰＰに規定されている「ＲＭＣ６４」の条件の下では、各要素符号の１回の復号について、（１２８×２）／（１，２９６＋（１２８×３））  ＝０．１５２３…となり、処理時間を約１５．２％だけ短縮することができる。
この結果、この例の復号装置を携帯電話等の携帯用電子機器に適用した場合には、回路規模が削減されるとともに、処理時間が短縮されバッテリ等の寿命も伸長し、ひいては携帯用電子機器を安価に構成することができる。
【００４５】
Ｂ．第２の参考例
次に、この発明の第２の参考例について説明する。
図７は、この発明の第２の参考例である誤り訂正符号の復号装置の構成を示すブロック図である。
この例のターボ符号の復号装置は、フォワード処理・バックワード処理共用モジュール３１と、外部情報値算出処理モジュール３２と、メモリ３３〜３７と、スイッチ３８及び３９とから構成されている。フォワード処理・バックワード処理共用モジュール３１は、フォワード処理とバックワード処理とを交互に行う。外部情報値算出処理モジュール３２は、外部情報値を算出する。
【００４６】
メモリ３３は、フォワード処理・バックワード処理共用モジュール３１がフォワード処理において算出したウィンドウ境界のαパスメトリック値を一時保持するために設けられている。メモリ３４は、フォワード処理・バックワード処理共用モジュール３１がバックワード処理において算出したウィンドウ境界のβパスメトリック値を一時保持するために設けられている。メモリ３５は、フォワード処理・バックワード処理共用モジュール３１がフォワード処理において算出したパスメトリック値を外部情報値算出処理モジュール３２に供給するために設けられている。メモリ３６は、外部情報値算出処理モジュール３２が算出した外部情報値をフォワード処理・バックワード処理共用モジュール３１に供給するために設けられている。すなわち、メモリ３６は、第１要素符号（ｕ，ｐ）と第２要素符号（ｕ'，ｐ'）との間で事前情報として用いられる外部情報値を交換するために設けられている。メモリ３７は、インターリーブパターンＩＬＰを一時保持しておくために設けられている。なお、フォワード処理と、バックワード処理及び外部情報値算出処理とを時分割で交互に行うために、メモリ３７は１面バッファ構造となっている。
【００４７】
スイッチ３８は、通常はメモリ３５とフォワード処理・バックワード処理共用モジュール３１とを接続しているが、フォワード処理・バックワード処理共用モジュール３１がフォワード処理において２つ目以降のウィンドウの処理を開始する場合にフォワード処理のウィンドウ境界のパスメトリック値の初期値をフォワード処理・バックワード処理共用モジュール３１に供給するためにメモリ３３とフォワード処理・バックワード処理共用モジュール３１とを接続する。また、スイッチ３８は、フォワード処理・バックワード処理共用モジュール３１が繰り返し復号が２回目以降のバックワード処理を開始する場合にバックワード処理のウィンドウ境界のパスメトリック値の初期値をフォワード処理・バックワード処理共用モジュール３１に供給するためにメモリ３４とフォワード処理・バックワード処理共用モジュール３１とを接続する。スイッチ３９は、外部情報値算出処理モジュール３２がインターリーブパターンＩＬＰを用いる場合にメモリ３７と外部情報値算出処理モジュール３２とを接続し、インターリーブパターンＩＬＰを外部に供給する場合にメモリ３７と出力端子とを接続する。
【００４８】
次に、上記構成のターボ符号の復号装置の動作について、図８を参照して説明する。図８において、ＦＷＰはフォワード処理を、ＢＷＰはバックワード処理をそれぞれ表している。
（１）  時間０〜２Ｌｔでは、フォワード処理・バックワード処理共用モジュール３１は、図８に示すトレリス線図上の０時点（始点）からＬｐ時点までフォワード処理を行う。そして、フォワード処理・バックワード処理共用モジュール３１は、フォワード処理が終了した時点のαパスメトリック値をウィンドウ境界のαパスメトリック値の初期値としてメモリ３３に一時保持する。
（２）  時間２Ｌｔ〜４Ｌｔでは、フォワード処理・バックワード処理共用モジュール３１は、図８に示すトレリス線図上のＬｐ時点から０時点（始点）までバックワード処理を行う。また同時に、外部情報値算出処理モジュール３２は、外部情報値を算出する。この時、バックワード処理におけるウィンドウ境界（Ｌｐ時点）のβパスメトリック値の初期値はウィンドウ先のすべての状態を等確率とする。
【００４９】
（３）  時間４Ｌｔ〜６Ｌｔでは、フォワード処理・バックワード処理共用モジュール３１は、（１）の処理においてメモリ３３に一時保持されたウィンドウ境界のαパスメトリック値をαパスメトリック値の初期値として利用して、図８に示すトレリス線図上のＬｐ時点から２Ｌｐ時点までフォワード処理を行う。
（４）  時間６Ｌｔ〜８Ｌｔでは、フォワード処理・バックワード処理共用モジュール３１は、図８に示すトレリス線図上の２Ｌｐ時点からＬｐ時点までバックワード処理を行う。また同時に、外部情報値算出処理モジュール３２は、外部情報値を算出する。そして、フォワード処理・バックワード処理共用モジュール３１は、バックワード処理が終了した時点のβパスメトリック値をウィンドウ境界のβパスメトリック値の初期値としてメモリ３４に一時保持する（図８（１）参照）。
【００５０】
（５）  時間８Ｌｔ〜（４Ｎｔ−Ｍｔ）（Ｍｔ≦２Ｌｔ）では、フォワード処理・バックワード処理共用モジュール３１は、フォワード処理が図８に示すトレリス線図上の２Ｌｐ時点からＮｐ時点（終点）に達するまで上記した（３）及び（４）の処理を交互に行う。
（６）  時間（４Ｎｔ−Ｍｔ）〜４Ｎｔでは、フォワード処理・バックワード処理共用モジュール３１は、図８に示すトレリス線図上のＮｐ時点（終点）から（Ｎｐ−Ｍｐ時点までバックワード処理を行う。また同時に、外部情報値算出処理モジュール３２は、外部情報値を算出する。
【００５１】
（７）  以上説明した（１）〜（６）の処理を第１要素符号（ｕ，ｐ）に対する復号処理とし、続いて第２要素符号（ｕ'，ｐ'）に対する復号処理を同様に行い、繰り返し復号１回とする。これ以降は、フォワード処理・バックワード処理共用モジュール３１は、バックワード処理におけるウィンドウ境界のβパスメトリック値の初期値として前回繰り返し復号時においてメモリ３４に一時保持されたウィンドウ境界におけるβパスメトリック値を利用して、繰り返し復号処理を行う（図８（２）参照）。
（８）  適当な回数（１０回程度）の繰り返し復号を終了した後に、第２要素符号（ｕ'，ｐ'）に対する復号処理の対数尤度比（ＬＬＲ）（事前情報）の符号ビットを用いて各組織部ｕの硬判定を行う。
【００５２】
このように、この例の構成によれば、フォワード処理とバックワード処理とを交互に行うフォワード処理・バックワード処理共用モジュール３１が設けられている。さらに、フォワード処理・バックワード処理共用モジュール３１は、ＡＣＳ演算を２クロックで行っている。また、前回繰り返し復号時における、フォワード処理において得られるウィンドウ境界のαパスメトリック値を一時保持するメモリ３３を設け、このαパスメトリック値を、次回繰り返し復号時における、フォワード処理におけるαパスメトリック値の初期値として利用するとともに、前回繰り返し復号時における、バックワード処理において得られるウィンドウ境界のβパスメトリック値を一時保持するメモリ３４を設け、このβパスメトリック値を、次回繰り返し復号時における、バックワード処理におけるβパスメトリック値の初期値として利用している。したがって、図２２に示す従来のターボ符号の復号装置では必要であったパスメトリック値の初期値を算出するための学習処理が不要となる。これにより、図２２に示す学習処理モジュール１３が不要となり、また４面バッファ構造であったメモリ１６及び１９（図２２参照）に換えて、１面バッファ構造のメモリ３３〜３７を設けるだけで２サイクルごとの軟出力生成を実現することができる。さらに、従来のターボ符号の復号装置では必要であった前処理期間も不要となる。
【００５３】
Ｃ．実施例
次に、この発明の実施例について説明する。
上記した第１及び第２の参考例においては、ブランチメトリック値の算出方法については特に言及せず、従来の算出方法を用いることを前提としている。Ｍａｘ−Ｌｏｇ−ＭＡＰアルゴリズムでは、ブランチメトリック値は、符号語を構成するシンボル列と受信語のシンボル列との相関値（ユークリッド距離）及び外部情報値に基づいて算出される。このブランチメトリック値は、符号語に対する受信語の尤もらしさを表すものであり、値が大きいほど尤もらしいということになる。したがって、従来では、ブランチメトリック値を算出した以降のＡＣＳ演算及びデルタ算出において、複数の演算結果又は算出結果の中から最大値を選択して復号処理を行っていた。ここではパスメトリック値が最大のパスが最尤パスとなる。
しかし、この従来の算出方法では値の大きなものを選択してパスメトリック値の積算が行われるため、結果としてパスメトリック値が非常に大きくなり、復号装置を構成するメモリの記憶容量や各モジュールの回路規模が大きくなってしまう。
【００５４】
そこで、この実施例では、図１に示すフォワード処理モジュール２１、バックワード処理モジュール２２及び外部情報値算出処理モジュール２３における処理（上記した第１の参考例の構成）及び、図７に示すフォワード処理・バックワード処理共用モジュール３１及び外部情報値算出処理モジュール３２での処理（上記した第２の参考例の構成）において、符号語を構成するシンボル列の「０」と「１」とを反転させたトレリス線図を用いてビタビ復号を行う、すなわち、ＡＣＳ演算及びデルタ算出において、複数の演算結果又は算出結果の中から最小値を選択し、さらに、フォワード処理、バックワード処理及び外部情報値算出処理のそれぞれにおいて最小値となるパスを選択することにより、演算ビット幅を削減し、復号装置を構成するメモリの記憶容量や各モジュールの回路規模を削減する。
【００５５】
図９に従来の算出方法（これを最大値選択方法と呼ぶ）を用いた場合のトレリス線図を示し、図１０にこの実施例の算出方法（これを最小値選択方法と呼ぶ）を用いた場合のトレリス線図を示す。図９及び図１０において、ステップ０の右側に示された"００"、"１１"、"０１"及び"１０"は、符号語を構成するシンボル列（組織部及び冗長部）を表しており、また各楕円の左側の数値は各パスメトリック値を表しており、各数値でアンダーラインが付されている数値は、ＡＣＳ演算の結果選択されたパスメトリック値を表している。また、各楕円の右側の数値はＡＣＳ演算の結果選択されたパスメトリック値に後述するトランケーションを施した結果を表している。
【００５６】
最小値選択方法では、「０」と「１」を反転させた符号語を構成するシンボル列と受信語のシンボル列との相関値及び外部情報に基づいて算出されたブランチメトリック値は、符号語に対する受信語の尤もらしさの反対を表すものであり、値が小さい程尤もらしいということになる。したがって、最小値選択方法では、パスメトリック値が最小のパスが最尤パスとなる。また、最小値選択方法では、パスメトリック値の初期値が最大値選択方法と異なる。すなわち、最大値選択方法では、ＡＣＳ演算で間違ったパスを選択しないために、十分に大きな値を状態"０００"の初期値として与え、その他の状態"００１"〜"１１１"には最小値である「０」を初期値としていた。これに対し、最小値選択方法では、逆に、状態"０００"に最小値である「０」を初期値として与え、その他の状態"００１"〜"１１１"には十分に大きな値を初期値として与える。これにより、最小値選択方法においても間違ったパスを選択する可能性を排除する。
【００５７】
ここで、最大値選択方法及び最小値選択方法について、トランケーション（Truncation）前の各状態のパスメトリック値を、ステップ０〜ステップ２についてプロットした図を図１１〜図１３に示す。また、最大値選択方法及び最小値選択方法について、トランケーション後の各状態のパスメトリック値を、ステップ０〜ステップ２についてプロットした図を図１４〜図１６に示す。トランケーションとは、最小値を求めて減算する処理である。図１１〜図１６において、曲線ａが最大値選択方法、曲線ｂが最小値選択方法に関するものである。また、図１１及び図１４がステップ０、図１２及び図１５がステップ１、図１３及び図１６がステップ２に関するものである。
【００５８】
図１１〜図１３から分かるように、最小値選択方法の曲線ｂは、横軸に平行な直線を対称線として、最大値選択方法の曲線ａと線対称の関係になっており、最大値選択方法では尤もらしいパスのパスメトリック値を最大にとっているのに対し、最小値選択方法では尤もらしいパスのパスメトリック値を最小にとっている。
これにより、理想的なトランケーション処理を行うことができる。すなわち、外部情報値の元になる軟出力値は最も「０」らしい確率と最も「１」らしい確率の差で求められる。よって、重要なのは各状態のパスメトリック値そのものではなく差分情報である。従って、最大値選択方法と最小値選択方法において算出される外部情報値は同一であり、復号特性についての差はない。
なお、ターボ符号の復号装置の構成自体については、上記した第１又は第２の参考例の構成、すなわち、図１又は図７の構成をそのまま使用することができる。
【００５９】
以上、この発明の実施例を図面を参照して詳述してきたが、具体的な構成はこの実施例に限られるものではなく、この発明の要旨を逸脱しない範囲の設計の変更等があってもこの発明に含まれる。
例えば、上述の実施例においては、この発明をターボ符号を復号する復号装置に適用する例を示したが、これに限定されず、この発明は、一般に、畳込み符号を用いた符号に対して、ＭＡＰ系の軟入力軟出力復号を用いて繰返し復号を行う復号装置にも適用することができる。
【００６０】
また、上述の実施例においては、各手段をハードウェアで構成した例を示したが、これに限定されない。すなわち、上記誤り訂正符号の復号装置を、プロセッサ（演算装置）と、ＲＯＭやＲＡＭ等の内部記憶装置と、ＦＤＤ（フレキシブル・ディスク・ドライバ）、ＨＤＤ（ハード・ディスク・ドライバ）、ＣＤ−ＲＯＭドライバ等の外部記憶装置と、出力手段と、入力手段とを有するコンピュータによって構成し、上記フォワード処理モジュール２１、上記バックワード処理モジュール２２又は上記フォワード処理・バックワード処理共用モジュール３１並びに上記外部情報値算出処理モジュール２３又は３２がプロセッサによって構成され、これらの機能が誤り訂正符号の復号プログラムとして、ＲＯＭ等の半導体メモリや、ＦＤ、ＨＤＤやＣＤ−ＲＯＭ等の記憶媒体に記憶されていると構成しても良い。この場合、上記内部記憶装置、あるいは外部記憶装置が上記メモリ２４〜２８又はメモリ３３〜３７となり、誤り訂正符号の復号プログラムは、記憶媒体からプロセッサに読み込まれ、プロセッサの動作を制御する。プロセッサは、誤り訂正符号の復号プログラムが起動されると、上記フォワード処理モジュール２１、上記バックワード処理モジュール２２又は上記フォワード処理・バックワード処理共用モジュール３１並びに上記外部情報値算出処理モジュール２３又は３２として機能し、誤り訂正符号の復号プログラムの制御により、上記した処理を実行するのである。
このような構成によれば、上記したように学習処理が不要となるので、その学習処理に関するプロセッサの演算量を削減することができる。フォワード処理、バックワード処理、外部情報処理及び学習処理のそれぞれのプロセッサの演算量はほぼ同一であるので、上記構成によれば単純計算で従来より演算量を４分の３以下に削減することができる。これに応じて記憶装置の記憶容量、特に、命令を格納するためのインストラクションメモリの記憶容量を削減することができるとともに、処理時間も短縮することができ、コンピュータにおける消費電流も削減することができる。
【図面の簡単な説明】
【００６１】
【図１】この発明の第１の参考例であるターボ符号の復号装置の構成を示すブロック図である。
【図２】同装置の動作を説明するためのトレリス線図である。
【図３】同装置の復号特性と従来のスライディングウィンドウ方法による復号装置の復号特性とを比較するための図である。
【図４】外部情報値正規化係数に対するビット誤り率ＢＥＲ及びブロック誤り率ＢＬＥＲの特性のシミュレーション結果を示す図である。
【図５】通信路定数に対するビット誤り率ＢＥＲ及びブロック誤り率ＢＬＥＲの特性のシミュレーション結果を示す図である。
【図６】ウィンドウサイズに対するビット誤り率ＢＥＲ及びブロック誤り率ＢＬＥＲの特性のシミュレーション結果を示す図である。
【図７】この発明の第２の参考例であるターボ符号の復号装置の構成を示すブロック図である。
【図８】同装置の動作を説明するためのトレリス線図である。
【図９】この発明の実施例である最大値選択方法を用いた場合のトレリス線図である。
【図１０】同最小値選択方法を用いた場合のトレリス線図である。
【図１１】同最大値選択方法及び最小値選択方法について、トランケーション前の各状態のパスメトリック値をステップ０についてプロットした図である。
【図１２】同最大値選択方法及び最小値選択方法について、トランケーション前の各状態のパスメトリック値をステップ１についてプロットした図である。
【図１３】同最大値選択方法及び最小値選択方法について、トランケーション前の各状態のパスメトリック値をステップ２についてプロットした図である。
【図１４】同最大値選択方法及び最小値選択方法について、トランケーション後の各状態のパスメトリック値をステップ０についてプロットした図である。
【図１５】同最大値選択方法及び最小値選択方法について、トランケーション後の各状態のパスメトリック値をステップ１についてプロットした図である。
【図１６】同最大値選択方法及び最小値選択方法について、トランケーション後の各状態のパスメトリック値をステップ２についてプロットした図である。
【図１７】従来のターボ符号の符号化装置の構成例を示すブロック図である。
【図１８】トレリス線図の一例を示す図である。
【図１９】ターボ符号の通常の復号の手順を示す概念図である。
【図２０】トレリス線図上の時点（ｋ−１）から時点ｋへ遷移する場合における遷移モデルを示す図である。
【図２１】トレリス線図上の時点（ｋ−１）から時点ｋへ遷移する場合におけるαｋ−１（ｓｋ−１）及びβ（ｓｋ）の算出モデルを示す図である。
【図２２】従来のターボ符号の復号装置の構成例を示すブロック図である。
【図２３】同装置の動作を説明するためのトレリス線図である。
【符号の説明】
【００６２】
２１  フォワード処理モジュール
２２  バックワード処理モジュール
２３，３２  外部情報値算出処理モジュール
２４〜２８，３３〜３７  メモリ
３１  フォワード処理・バックワード処理共用モジュール
【図１】
2006115534.tif 000007
【図２】
2006115534.tif 000008
【図３】
2006115534.tif 000009
【図４】
2006115534.tif 000010
【図５】
2006115534.tif 000011
【図６】
2006115534.tif 000012
【図７】
2006115534.tif 000013
【図８】
2006115534.tif 000014
【図９】
2006115534.tif 000015
【図１０】
2006115534.tif 000016
【図１１】
2006115534.tif 000017
【図１２】
2006115534.tif 000018
【図１３】
2006115534.tif 000019
【図１４】
2006115534.tif 000020
【図１５】
2006115534.tif 000021
【図１６】
2006115534.tif 000022
【図１７】
2006115534.tif 000023
【図１８】
2006115534.tif 000024
【図１９】
2006115534.tif 000025
【図２０】
2006115534.tif 000026
【図２１】
2006115534.tif 000027
【図２２】
2006115534.tif 000028
【図２３】
2006115534.tif 000029