(57)【要約】【課題】動作周波数を低減することができ、また、繰り返し数を増やしたりすることが可能な復号方法および復号装置、並びにプログラムを提供する。【解決手段】受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号装置３０であって、受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理の際に、信頼性順のソートが完了した時点で、次の内側繰り返しで対角化対象列と対角化非対象列の間で入れ替える列を強制的に決定する処理部３２，３３，３５を有する【選択図】図６
2008205546.tif 000002
【特許請求の範囲】
【請求項１】
受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号方法であって、
受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理ステップを有し、
信頼性順のソートが完了した時点で、次の内側繰り返しで対角化対象列と対角化非対象列の間で入れ替える列を強制的に決定する
復号方法。
【請求項２】
信頼性伝播（ＢＰ）処理と対角化処理とを並列的に行う
請求項１記載の復号方法。
【請求項３】
対角化処理で要探索、掃き出しのために読み出したパリティ検査行を、信頼性伝播処理の入力とする
請求項２記載の復号方法。
【請求項４】
対角化処理で読み出すパリティ検査行の順において、次の内側繰り返しで新しく対角化対象から外れる列の要行を先に読み出す
請求項３記載の復号方法。
【請求項５】
信頼性のソートを行う際に、前回の内側繰り返しで既に決定した本内側繰り返しで新しく対角化対象から外れる列以外の中から次の内側繰り返しで新しく対角化対象から外れる列を選択する
請求項４記載の復号方法。
【請求項６】
信頼性のソートを行う際に、前回の内側繰り返しで既に決定した本内側繰り返しで新しく対角化対象から外れる列以外のうち信頼性の大きい列を次の内側繰り返しで新しく対角化対象から外れる列とする
請求項５記載の復号方法。
【請求項７】
受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号装置であって、
受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理の際に、信頼性順のソートが完了した時点で、次の内側繰り返しで対角化対象列と対角化非対象列の間で入れ替える列を強制的に決定する処理部を有する
復号装置。
【請求項８】
前記処理部は、
信頼性伝播（ＢＰ）処理と対角化処理とを並列的に行う
請求項７記載の復号装置。
【請求項９】
前記処理部は、
対角化処理で要探索、掃き出しのために読み出したパリティ検査行を、信頼性伝播処理の入力とする
請求項８記載の復号装置。
【請求項１０】
前記処理部は、
対角化処理で読み出すパリティ検査行の順において、次の内側繰り返しで新しく対角化対象から外れる列の要行を先に読み出す
請求項９記載の復号装置。
【請求項１１】
前記処理部は、
信頼性のソートを行う際に、前回の内側繰り返しで既に決定した本内側繰り返しで新しく対角化対象から外れる列以外の中から次の内側繰り返しで新しく対角化対象から外れる列を選択する
請求項１０記載の復号装置。
【請求項１２】
前記処理部は、
信頼性のソートを行う際に、前回の内側繰り返しで既に決定した本内側繰り返しで新しく対角化対象から外れる列以外のうち信頼性の大きい列を次の内側繰り返しで新しく対角化対象から外れる列とする
請求項１１記載の復号装置。
【請求項１３】
受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号処理において、
受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理ステップで、
信頼性順のソートが完了した時点で、次の内側繰り返しで対角化対象列と対角化非対象列の間で入れ替える列を強制的に決定する処理を
コンピュータに実行させるプログラム。
【請求項１４】
信頼性伝播（ＢＰ）処理と対角化処理とを並列的に行う処理をコンピュータに実行させる
請求項１３記載のプログラム。
【請求項１５】
対角化処理で要探索、掃き出しのために読み出したパリティ検査行を、信頼性伝播処理の入力とする処理をコンピュータに実行させる
請求項１４記載のプログラム。
【請求項１６】
対角化処理で読み出すパリティ検査行の順において、次の内側繰り返しで新しく対角化対象から外れる列の要行を先に読み出す処理をコンピュータに実行させる
請求項１５記載のプログラム。
【請求項１７】
信頼性のソートを行う際に、前回の内側繰り返しで既に決定した本内側繰り返しで新しく対角化対象から外れる列以外の中から次の内側繰り返しで新しく対角化対象から外れる列を選択する処理をコンピュータに実行させる
請求項１６記載のプログラム。
【請求項１８】
信頼性のソートを行う際に、前回の内側繰り返しで既に決定した本内側繰り返しで新しく対角化対象から外れる列以外のうち信頼性の大きい列を次の内側繰り返しで新しく対角化対象から外れる列とする処理をコンピュータに実行させる
請求項１７記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、たとえば代数的手法を用いた誤り訂正符号技術を実現するための回路およびプログラム記憶媒体に関して適用される復号方法および復号装置、並びにプログラムに関するものである。
【背景技術】
【０００２】
代数幾何符号、たとえばリードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ）符号やその部分体部分符号としてのＢＣＨ符号には、その代数的性質を利用した、性能・計算コスト共に良い復号法が知られている。
【０００３】
たとえば、符号長ｎ、情報長ｋ、定義体ＧＦ（ｑ）（ｑ＝ｐｍ，ｐ：素数）、最小距離ｄ＝ｎ−ｋのＲｅｅｄ−Ｓｏｌｏｍｏｎ符号をＲＳ（ｎ，ｋ）とすると、硬判定受信語をハミング（Ｈａｍｍｉｎｇ）距離が最小の符号語に復号する最小距離復号（通常復号）はｔ＜ｄ／２を満たすｔ個の誤りシンボルの訂正を保証するものとして良く知られている。
【０００４】
また、グルスワミ−スーダン（Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ）によるリスト復号（以下Ｇ−Ｓリスト復号）は、ｔ＜√ｎｋを満たすｔ個の誤りシンボルの訂正を保証している（非特許文献１参照）。
【０００５】
Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎのリスト復号の拡張版として軟判定受信語を用いたコータ−バルディ（Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ）によるリスト復号（以下Ｋ−Ｖリスト復号）は、Ｇｕｒｕｓｗａｍｉ−Ｓｕｄａｎ同様に（１）受信情報から各シンボルの信頼性を算出、（２）信頼性から２変数多項式補間条件の抽出、（３）２変数多項式の補間、（４）補間多項式の因数分解を行い復号語リスト作成、の４つの手順により構成され、硬判定復号時に比べてより高い性能を持つことが知られている（非特許文献２参照）。
【０００６】
また、リエンコード（Ｒｅ−ｅｎｃｏｄｅ）により、その計算コストも現実的な範囲まで削減できることが知られている（非特許文献３参照）。
【０００７】
一方、線形符号としては、信頼性伝播（ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を用いた繰り返し復号により限界性能に近い高性能を得られる低密度パリティ検査符号（Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅ，ＬＤＰＣ符号）が昨今注目されている（非特許文献４参照）。
【０００８】
ＬＤＰＣ符号に用いられる信頼性伝播（ＢＰ）は、一般に低密度なパリティ検査行列を持つ線形符号にしか有効でないことが理論的に知られており、また、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号のパリティ検査行列を低密度化することはＮＰ−ｈａｒｄであることが知られている（非特許文献５参照）。
【０００９】
よって、Ｒｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号に信頼性伝播（ＢＰ）を適用することは困難であるとされてきた。
【００１０】
しかし、２００４年、受信語の信頼性に応じて対角化を行ったパリティ検査行列を用いてＲｅｅｄ−Ｓｏｌｏｍｏｎ符号やＢＣＨ符号、その他低密度でないパリティ検査行列を持つ線形符号への信頼性伝播（ＢＰ）の適用が効果的であることがナラヤナン(Ｎａｒａｙａｎａｎ)等によって紹介された（非特許文献６参照）。
【００１１】
この手法は、適応的信頼性伝播（ＡＢＰ：Ａｄａｐｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ）復号と呼ばれる。以下、このＡＢＰ復号法について説明する。
【００１２】
たとえば、符号長ｎ＝６、情報長ｋ＝３、符号化率ｒ＝１／２の符号で、以下の３×６行列Ｈをパリティ検査行列として持つような線形符号Ｃを考える。
【００１３】
【数１】
2008205546.tif 000003
【００１４】
符号空間Ｃは、次のように表される。
【００１５】
【数２】
2008205546.tif 000004
【００１６】
ある符号語があるチャネル、たとえばＢＰＳＫ変調＋ＡＷＧＮチャネル（Ａｄｄｉｔｉｖｅ  Ｗｈｉｔｅ  Ｇａｕｓｓｉａｎ  Ｎｏｉｓｅチャネル）を通った後、次のような受信語ｒとして受信機が受け取ったとする。
【００１７】
【数３】
2008205546.tif 000005
【００１８】
このとき、受信値の各絶対値の大きさは受信語の信頼性の高さを表す。つまり、信頼性の低い順に番号をつけると以下のようになる。
【００１９】
【数４】
2008205546.tif 000006
【００２０】
次に、信頼性の低いシンボルに対応する列より順にパリティ検査行列Ｈの対角化を行う。この例においては、信頼性の低いシンボルに対応する列は順に第３列、第５列、第１列、第４または第６列、第２列となるので、その優先順位に従ってＨの対角化を行う。
【００２１】
【数５】
2008205546.tif 000007
【００２２】
【数６】
2008205546.tif 000008
【００２３】
【数７】
2008205546.tif 000009
【００２４】
対角化を試みた列がそれ以前に対角化した列と線形従属であった場合は、その列はそのまま残し、次の順位の列で対角化を試みる。
このようにして行列Ｈのランク分対角化が行われた結果得られる新たなパリティ検査行列Ｈｎｅｗを用いて、信頼性伝播（ＢＰ）による信頼性の更新を行う。
【００２５】
図１はパリティ検査行列Ｈｎｅｗに対応するタナーグラフである。
信頼性伝播（ＢＰ）はタナーグラフのエッジに沿ってメッセージを行き来させることによって実現される。
行列の各列に対応するノードを可変（ｖａｒｉａｂｌｅ：バリアブル）ノード１、各行に対応するノードを検査（ｃｈｅｃｋ：チェック）ノード２と呼ぶ。
【００２６】
ｉ番目のバリアブルノードからｊ番目のチェックノードへのメッセージをＱi,j、ｊ番目のチェックノードからｉ番目のバリアブルノードへのメッセージをＲｉ,j、さらにｉ番目のバリアブルノードに連接するチェックノードのインデックス集合をＪ（ｉ）、ｊ番目のチェックノードに連接するバリアブルノードのインデックス集合をＩ（ｊ）とした場合、それぞれの更新式は以下のようになる。
【００２７】
【数８】
2008205546.tif 000010
【００２８】
ここで、θはバーティカルステップダンピングファクタ（ｖｅｒｔｉｃａｌ  ｓｔｅｐ  ｄａｍｐｉｎｇ  ｆａｃｔｏｒ）と呼ばれる係数を示し、０＜θ≦１なる条件を満足する。Ｑi,jの初期値はｒjが設定され、外部情報（ｅｘｔｒｉｎｓｉｃ  ｉｎｆｏｒｍａｔｉｏｎ）Λｉｘ更新は次式により行われる。
【００２９】
【数９】
2008205546.tif 000011
【００３０】
さらに、各符号ビットのＬＬＲΛｉｑの更新は、次式により行われる。
【００３１】
【数１０】
2008205546.tif 000012
【００３２】
ここで、α１は適応的信頼性伝播ダンピングファクタ（ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ  ｄａｍｐｉｎｇ  ｆａｃｔｏｒ）と呼ばれる係数を示し、０＜α１≦１なる条件を満足する。
この信頼性伝播（ＢＰ）によるＬＬＲの更新は事前に用意された繰り返し停止条件を満たすまで、たとえば最大繰り返し数ＩｔＨに達成するまで繰り返される。
また、ＬＬＲを更新する列は、全ての列を対象とせずとも一部の列、たとえば対角化の対象となった列についてのみ行ってもよい。
【００３３】
信頼性伝播（ＢＰ）によって更新されたＬＬＲの信頼性を用いて、つまり、ＬＬＲの絶対値の大きさを信頼性として、信頼性の低いシンボルに対応する列順に対角化を行うことにより、新たな信頼性伝播（ＢＰ）による繰り返し復号を行うことができる。
これを内側繰り返し復号と呼ぶ。このＬＬＲの更新は事前に用意された内側繰り返し復号停止条件ＳＣ１を満たすまで繰り返される。
【００３４】
さらに、パリティ検査行列の列の対角化優先順位の初期値として、受信値の信頼性順以外の順位を複数用意する。複数の順位を用いて、シリアルもしくはパラレルに繰り返し内側繰り返し復号を行う。
これを外側繰り返し復号と呼ぶ。このＬＬＲ更新は事前に用意された外側繰り返し復号停止条件ＳＣ２を満たすまで繰り返される。
【００３５】
以上のＡＢＰ（ａｄａｐｔｉｖｅ  ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）手順により繰り返し更新されたＬＬＲを入カとして、復号器により復号を行う。
今、対象となる線形符号がＲｅｅｄ−Ｓｏｌｏｍｏｎ符号であった場合、繰り返し復号停止条件ＳＣ１、ＳＣ２として、たとえば以下のものが考えられる。
【００３６】
（Ａ）  Ｈ・ｄ  ＝＝  ０または繰り返し数ｔ≧Ｎ、
（Ｂ）  限界距離復号成功または繰り返し数ｔ≧Ｎ、
（Ｃ）  Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ軟判定リスト復号成功または繰り返し数ｔ≧Ｎ。
【００３７】
ここで、ｄ＝（ｄ１，ｄ２，・・・，ｄ６）はΛｉの硬判定結果、ｄｉ＝｛Λｉｑ＞０なら１，Λｉｑ≦０なら０｝であり、Ｎは事前に決めた最大繰り返し回数である。
また、復号方法として、たとえば以下のものが考えられる。
【００３８】
（ａ）  硬判定復号
（ｂ）  限界距離復号
（ｃ）  Ｋｏｅｔｔｅｒ−Ｖａｒｄｙ軟判定リスト復号
【００３９】
図２は、ＡＢＰ復号法を用いた繰り返し復号のフローチャートである。
【００４０】
受信語の信頼性順の探索を行い（ＳＴ１）、順序変換を行う（ＳＴ２）。
変換した順序に応じてパリティ検査行列の対角化を行い（ＳＴ３）、このパリティ検査行列を用いて信頼性伝播（ＢＰ）を行う（ＳＴ４）。
次に、ＬＬＲを計算し（ＳＴ５）、計算したＬＬＲの信頼性順を探索し（ＳＴ６）、復号を行い、復号語をリストへ追加する（ＳＴ７）。
そして、繰り返し復号停止条件Ｎ１，Ｎ２を満足するまで以上の処理を繰り返す（ＳＴ８、ＳＴ９）。
そして、復号語を１つ選択する（ＳＴ１０）。
【００４１】
【非特許文献１】Ｖ．Ｇｕｒｕｓｗａｍｉ，Ｍ．Ｓｕｄａｎ，Ｉｍｐｒｏｖｅ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ａｎｄ  Ａｌｇｅｂｒａｉｃ−Ｇｅｏｍｅｔｒｙ  ｃｏｄｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．４５，ｐｐ．１７５７−１７６７，１９９９
【非特許文献２】Ｒ．Ｋｏｅｔｔｅｒ，Ａ．Ｖａｒｄｙ，Ａｌｇｅｂｒａｉｃ  ｓｏｆｔ−ｄｅｃｉｓｉｏｎ  ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，２００１
【非特許文献３】Ｒ．Ｋｏｅｔｔｅｒ，Ｊ．Ｍａ，Ａ．Ｖａｒｄｙ，Ａ，Ａｈｍｅｄ，Ｅｆｆｃｉｅｎｔ  Ｉｎｔｅｒｐｏｌａｔｉｏｎ  ａｎｄ  Ｆａｃｔｏｒｉｚａｔｉｏｎ  ｉｎ  Ａｌｇｅｂｒａｉｃ  Ｓｏｆｔ−Ｄｅｃｉｓｉｏｎ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｒｅｅｄ−Ｓｏｌｏｍｏｎ  ｃｏｄｅｓ，Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＩＳＩＴ２００３
【非特許文献４】Ｄ．ＭａｃＫａｙ，Ｇｏｏｄ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ  Ｂａｓｅｄ  ｏｎ  Ｖｅｒｙ  Ｓｐａｒｓｅ  Ｍａｔｒｉｃｅｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，１９９９
【非特許文献５】Ｂｅｒｌｅｋａｍｐ，Ｒ．ＭｃＥｌｉｅｃｅ，Ｈ．ｖａｎ  Ｔｉｌｂｏｒｇ，Ｏｎ  ｔｈｅ  ｉｎｈｅｒｅｎｔ  ｉｎｔｒａｃｔａｂｉｌｉｔｙ  ｏｆ  ｃｅｒｔａｉｎ  ｃｏｄｉｎｇ  ｐｒｏｂｌｅｍｓ，ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．２４，ｐｐ．３８４−３８６，Ｍａｙ，１９７８）。
【非特許文献６】Ｊｉｎｇ  Ｊｉａｎｇ，Ｋ．Ｒ．Ｎａｒａｙａｎ，Ｓｏｆｔ  Ｄｅｃｉｓｉｏｎ  Ｄｅｃｏｄｉｎｇ  ｏｆ  ＲＳ  Ｃｏｄｅｓ  Ｕｓｉｎｇ  Ａｄａｐｔｉｖｅ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｍａｔｒｉｃｅｓ，Ｐｒｏｃｅｅｄｉｎｇ  ｏｆ  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ  ２００４
【発明の開示】
【発明が解決しようとする課題】
【００４２】
ところで、上述の技術では、受信ＬＬＲの大きさ順に列インデックスをソートする作業、および信頼性伝播（ＢＰ）によって更新されたＬＬＲを用いて再び列インデックスをソートしなおす作業を行うソート装置が必要となる。
【００４３】
また、ソートを行った後に、後段の対角化装置が望むタイミングで列インデックスを出力する必要や、更新されたＬＬＲをソートする際に、一部の列のみＬＬＲが更新され、更新されたインデックスのみ入力される場合は、更新前のソートされたインデックス順の中にＬＬＲが更新されたインデックスを反映していく必要があるなど、様々な制約条件がある。
【００４４】
また、実際には、ＲＳ（204，188）といったＨよりも符号長の大きいＲＳ符号を対象としたシステムが多く、これについて、既存の技術を用いて現実的な動作周波数で実現することは困難である。
【００４５】
図３は、ＡＢＰ復号装置の繰り返し毎のフローの一列を示す図である。
【００４６】
受信語が到来したらそれを信頼度の大きさに従いソートし、信頼度の小さい１２８列についてパリティ検査行列Ｈの対角化を行い、対角化後のパリティ検査行列をＨ１とする。
このＨ１を利用して信頼性伝播（ＢＰ）を行う。この場合、対角化対象となった１２８列のみ信頼度を更新する。繰り返し二回目以降も同様に、更新信頼度をソートし直し、信頼度の小さい１２８列についてパリティ検査行列Ｈを対角化し、信頼性伝播（ＢＰ）を行うことを繰り返す。
【００４７】
以上のようなＡＢＰ復号装置を実現したい場合、以下のように所要動作周波数を想定できる。
たとえば、ＲＳ（240，188）を想定し、内側繰り返し復号を装置で実現することを想定した場合、内側繰り返し数を１０回、ＬＬＲの更新を対角化対象となった列１２８列にのみ限定し、信頼性伝播（ＢＰ）の繰り返し数を１回にする条件において、ＡＢＰ復号するための必要なクロックサイクル数は、次のようになる。
【００４８】
【数１１】
2008205546.tif 000013
【００４９】
ここで、Ｔ１は繰り返し一回目に必要とするクロックサイクル数、Ｔ２は繰り返し二回目以降に必要とするクロックサイクル数を示している。
Ｔ１は、次式で示すようなクロックサイクル数が必要となる。
【００５０】
【数１２】
2008205546.tif 000014
【００５１】
ここで、Ｔsort1は、ソートに必要とするクロックサイクル数を示し、逆写像ソートを利用した場合、最低でも入力ビット数１６３２クロックサイクルが必要となる。また、Ｔdiagは、対角化に必要とするクロックサイクル数を示し、一回の行読出しで要探索と掃き出しを一度に行い、かつ並列に複数列、たとえばここでは４列の基本変形を行う対角化装置を利用した場合、今回R列パラレルに基本変形すると、最低でも１２８×１２８／４＝４０９６クロックサイクル数必要とする。また、Ｔbpは、信頼性伝播（ＢＰ）に必要とするクロックサイクル数を示し、対角化対象となった１２８列のみＬＬＲ更新を行うので、最低１２８クロックサイクル数必要となる。
【００５２】
以上より、Ｔ１は次のようになる
【００５３】
【数１３】
2008205546.tif 000015
【００５４】
また、内側繰り返し二回目以降のＴ２は次のようになる。
【００５５】
【数１４】
2008205546.tif 000016
【００５６】
ここで、Ｔsort2は、内側繰り返し二回目以降のソートに必要とするクロックサイクル数を示し、ＬＬＲが更新される列インデックスが１２８列とすると、Ｔsort2＝１２８と考えうる。
しかし、繰り返し二回目以降は、前繰り返しの信頼性伝播（ＢＰ）により、毎クロックサイクル１列ずつ更新された信頼度をソート装置に入力すれば、信頼性伝播（ＢＰ）とソートはほぼ同時に行うことが可能なためＴsort2＝０とすることができる。つまり、Ｔ２は次のようになる。
【００５７】
【数１５】
2008205546.tif 000017
【００５８】
このように、内側繰り返し二回目以降は、繰り返し一回につき４２２４サイクルかかることから、既存の技術では実現し得ないような動作周波数が必要になり、また、繰り返し数を増やしたりすることが極めて困難である。
【００５９】
本発明は、動作周波数を低減することができ、また、繰り返し数を増やしたりすることが可能な復号方法および復号装置、並びにプログラムを提供することにある。
【課題を解決するための手段】
【００６０】
本発明の第１の観点は、受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号方法であって、受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理ステップを有し、信頼性順のソートが完了した時点で、次の内側繰り返しで対角化対象列と対角化非対象列の間で入れ替える列を強制的に決定する。
【００６１】
本発明の第２の観点は、受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号装置であって、受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理の際に、信頼性順のソートが完了した時点で、次の内側繰り返しで対角化対象列と対角化非対象列の間で入れ替える列を強制的に決定する処理部を有する。
【００６２】
本発明の第３の観点は、受信語の信頼度の大きさに従いソートし、その順番に対角化されたパリティ検査行列を用いて、信頼性伝播（Ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ：ＢＰ）を行って信頼度を更新し、その更新された値に対して、再び上記動作を繰り返す復号処理において、受信値の信頼度（ＬＬＲ）の小さいシンボルに対応する列順に対角化されたパリティ検査行列を用いて信頼性伝播を行い、更新された信頼度に基づきこの動作を繰り返す内側繰り返し復号処理ステップで、信頼性順のソートが完了した時点で、次の内側繰り返しで対角化対象列と対角化非対象列の間で入れ替える列を強制的に決定する処理をコンピュータに実行させるプログラムである。
【００６３】
本発明によれば、ソート処理と対角化処理と信頼性伝播（ＢＰ）処理をパラレルに動作させる。そのために、信頼性伝播（ＢＰ）処理のために読み出しているパリティ行を同時に対角化処理の要探索、掃き出し系へ送り込む方法が適用可能である。
しかし、この時点で、次回の繰り返しで新しく対角化対象列になる複数列（たとえば４列）は決定しているが、次回の繰り返しで新しく対角化対象から外れる４列が決定しておらず、つまりは要行リストから外れる４行について決定できないため、信頼性伝播（ＢＰ）が行われている時点で次の繰り返しのパリティ検査行列を生成するのは困難である。
そのため、ソート後の信頼性の順番により、次回の繰り返しで新しく対角化対象列になる４列だけでなく、次回の繰り返しで新しく対角化対象から外れる４列も決定する。
これにより、ソート処理と対角化処理と信頼性伝播（ＢＰ）処理が並列（パラレル）に行われる。
【発明の効果】
【００６４】
本発明によれば、ソート処理と対角化処理と信頼性伝播（ＢＰ）処理が並列（パラレル）に動作させることが可能になり、動作周波数を低減したり、繰り返し数を増やしたりすることが可能となる。
【発明を実施するための最良の形態】
【００６５】
以下、本発明の実施形態を図面に関連付けて説明する。
【００６６】
本発明の実施形態に係る復号装置は、代数的手法を用いた誤り訂正符号技術を実現するための回路、たとえば適応的信頼性伝播（Ａｄａｐｔｉｖｅ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ：ＡＢＰ）復号器に応用できる。
ＡＢＰ復号は、リードソロモン（Ｒｅｅｄ−Ｓｏｌｏｍｏｎ：ＲＳ）符号やＢＣＨ符号、その他低密度でないパリティ検査行列を持つ線形符号に対する復号法であり、ある伝送路から符号語を受信すると、その受信語をより信頼できる値に更新する。
【００６７】
以下、ＡＢＰ復号における復号装置の通信システム上の位置づけについて説明した後、本実施形態に係る復号装置の具体的な構成および機能について説明する。
【００６８】
図４は、デジタル信号受信機、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた通信システムの構成例を示す図である。
【００６９】
本通信システム１０は、図４に示すように、ＲＳ符号化器１１、インタリーバ１２、畳み込み符号器１３、畳み込み符号の軟出力復号器１４、デインタリーバ１５、ＲＳ符号の既知情報付きＡＢＰ繰り返し復号器１６、およびチャネル１７を有する。
【００７０】
本通信システム１０では、ＲＳ符号化、畳み込み符号化された送信語に対して、畳み込み符号の軟出力復号をした後にＡＢＰ復号を行っている。
ここで言う畳み込み符号の軟出力復号とは、たとえばＢＣＪＲアルゴリズムやＳＯＶＡによる復号のことである。
ＡＢＰ復号器１６においては、ＡＢＰによる信頼性の更新後、硬判定後限界距離復号、リスト復号、もしくは、軟値をそのまま入力として軟判定リスト復号を行う。
【００７１】
図５は、ＭＡＰ復号が後段についたＡＢＰ復号器の構成例を示す図である。
この復号器２０は、図５に示すように、ＡＢＰ復号部２１、限界距離（ＢＤ）復号部２２、受信信頼度（ＬＬＲ）保持部２３、およびＭＡＰ復号部２４を有している。
【００７２】
復号器２０においては、ＡＢＰ復号部２１による信頼性（ＬＬＲ）の更新後、硬判定してＢＤ復号部２２において、限界距離復号を行い、この結果をリストに集め、最終的にＭＡＰ復号部２４において最大事後確率復号（Ｍａｘｉｍｕｍ  ａ  ｐｏｓｔｅｒｉｏｒｉ  Ｐｒｏｂａｂｉｌｉｔｙ：ＭＡＰ）復号を行う。
【００７３】
図６は、ＡＢＰ復号器の構成例を示す図である。
【００７４】
図５のＡＢＰ復号器３０は、図４のＡＢＰ復号器１６や図５のＡＢＰ復号部２１に適用可能であり、ソート入力選択部３１、ソート部３２、パリティ検査行列の対角化部３３、信頼度（ＬＬＲ）保持部３４、および信頼性伝播（ＢＰ）部３５を有している。
なお、ソート部３２、対角化部３３、および信頼性伝播（ＢＰ）部３５により、本実施形態に係る処理部が構成される。
【００７５】
ＡＢＰ復号器３０においては、入力として、受信ＬＬＲＳ３２が入力される。
列インデックスＳ３１は、入力された受信ＬＬＲの符号語の始まりからカウンタで０、１、２、３、、とカウントアップされた値を生成し利用する。
ソート入力選択部３１で、初回は、列インデックスＳ３１と受信ＬＬＲＳ３２を選択し、繰り返し二回目以降は信頼性伝播（ＢＰ）後、更新ＬＬＲＳ４０とその列インデックスＳ３９を選択する。
【００７６】
図５に示すように、受信語が入力されたら、まず、ソート部３２において、その信頼度（ＬＬＲ）の大きさに応じて列インデックスのソートを行う。
次に、信頼度の低いシンボルに対応する列より順に、対角化部３３でパリティ検査行列の対角化を行う。
最後に、対角化されたパリティ検査行列を用いて、信頼性伝播（ＢＰ）を行うことにより、値が更新される。
更新された値に対して、再びソート、対角化、信頼性伝播（ＢＰ）を行う。繰り返し数が予め決められており、その繰り返し数だけこれを繰り返す。
【００７７】
この復号器３０の処理部を構成する対角化部３３は以下のように実現される。
本実施形態においては、例として、以下の４×６-行列Ｈを第１、２、３、４列について対角化を行う例を考える。
【００７８】
【数１６】
2008205546.tif 000018
【００７９】
これを、第１、２、３、４列について対角化すると、以下のＨnewのようになる。
【００８０】
【数１７】
2008205546.tif 000019
【００８１】
この対角化を実現する装置例を以下で説明する。
基本原理は、対角化を行う際、各列の基本変形で、ある行が要行になる度にその行を行列の後段に回すことにより、対象となる列を基本変形するときに、要探索の対象となる行をまだ要になっていない行に限定でき、これにより、その列ではじめて見つかった非零要素を要とでき、各列の各要素を要探索と掃き出しのどちらかのみ対象とすればよいこと、さらに、対角化対象列を複数列同時に要探索、掃き出すことに基づく。
【００８２】
図７は、本発明の実施形態に係るＡＢＰ復号器の行列対角化部の第１の構成例を示す図である。
【００８３】
本実施形態に係る行列対角化部１００は、図７に示すように、行のインデックスを記憶する行インデックスメモリ１１０と、行列を記憶する行列メモリ１２０と、第１要探索、掃き出し回路１３０と、第１行保持部１４０と、第１要フラグ保持部１５０と、第２要探索、掃き出し回路１６０と、第２行保持部１７０と、第２要フラグ保持部１８０とを有している。
【００８４】
図７の行列対角化部１００は、行インデックスメモリ１１０から順に行インデックスを読み出し、その行インデックスが指定する行を行列メモリ１２０から読み出し、その行の対角化の対象となる列の要素を見て、要探索、掃き出しを行う。
また、要探索、掃出しは一行読出すごとにパラレル（並列）に行い、要行同士の掃出しは行読出しの最後に行うことにより高速に対角化される。これにより、たとえば３列並列に基本変形を行うと行読出し回数をおよそ１／３に減らすことができる。
さらに、対象となる列を要探索、掃き出す際、行インデックスメモリ１１０から行インデックスを先頭アドレスから順番に読み出し、読み出した行が要行にならなかった場合、その行インデックスを行インデックスメモリ１１０の先頭アドレスから順に書き込み、読み出した行が要行になった場合のみ、その行インデックスを要行インデックス保持部１７０，１８０に書き込み、最後に行インデックスメモリ１１０の後ろのアドレスにそのインデックスを書き込む。
これにより、次の基本変形から未だ要になっていない行を優先的に読み出せるため、はじめて見つかった対象列の非零要素を要とでき、各列の基本変形に対して、各行は要探索か掃き出しのいずれかの対象となればよいので、より高速な対角化が可能となる。
以上の方法により、ｔ列パラレルで対角化を行った場合、およそ行数×列数／ｔ回の行読出しで対角化が可能となる。
【００８５】
以下、本実施形態に係る行列対角化方法の全体の処理を図７〜図１７に関連付けて説明する。図７〜図１５は、行列を２列パラレルに要探索、掃き出しを行う対角化フローを表す。
【００８６】
図７に示すように、初期に行インデックスメモリ１１０にはアドレスと同じ値が格納されている。
これを先頭アドレスから順に１、２、３、４と読出していき行列メモリ１２０の読出しアドレスＳ１２とし、これを用いて行列メモリ１２０から行Ｓ１３を読み出す。
読出した行Ｓ１３に対し、２列分の要探索、掃き出しが施され、これを４列分行うと対角化は完了する。
ここでは、まず、第１列、第２列を並列に要探索、掃き出す。第１要探索、掃き出し回路１３０では第１列、第２要探索、掃き出し回路１６０では第２列を対角化の対象とする。
【００８７】
ここで、第１列、第２列の基本変形を開始する。
まず、図８に示すように、行インデックスメモリ１１０から、読出し行インデックスＳ１２に１が読み出される。これが行列メモリ１２０に与えられると第１行が読み出され、第１要探索、掃き出し回路１３０へ送られる。
第１要探索、掃き出し回路１３０においては、第１列の要素が零か非零かを調べ、今回は零であるため、要にはならず、第１行はそのまま第１行保持部１４０へ送信され、第１要フラグ保持部１５０には０が送信される。
【００８８】
次に、図９に示すように、第２要探索、掃き出し回路１６０には第１行が送られ、この第２列は零であるため、第２行保持部１７０には第１行がそのまま送られ、第２要フラグ保持部１８０には０が送られる。
また、行インデックスメモリ１１０から、読出し行インデックスＳ１２に２が読み出され、行列メモリ１２０から第２行が読み出される。
読み出された行Ｓ１３は第１要探索、掃き出し回路１３０で第１列が零か非零か調べられ、非零であるため、この行を要とし、内部に一時的に格納される。
また、第１行保持部１４０に第２行が、第１要フラグ保持部１５０には１が送られる。
【００８９】
次に、図１０に示すように、第２要探索、掃き出し回路１６０には、第２行が要フラグ１と共に入力され、要フラグが１であり、また、第２列の要行は未だ見つかっていないので、第２行をそのまま第２行保持部１７０へ送り、第２要フラグ保持部１８０に１を送る。
また、行列メモリ１２０から第３行が同様に読み出され、第１要探索、掃き出し回路１３０に送られる。第１要探索、掃き出し回路１３０は既に要行を確保しているので、第３行が掃き出しの対象となるかを判断する。
第３行第１列は非零であるので、第３行に対し確保した要行で掃き出す、具体的には第３行から要行を減算した行を新たな第３行とし第１行保持部１３０へ送られる。また、第１要フラグ保持部１５０には０が送られる。
さらに、第２行保持部１６０から読み出される第１行を行列メモリ１２０に書き込む。また、行インデックスメモリ１１０に到来する書込み行インデックスＳ１１である１とともに第２要フラグ保持部１８０から０が到来するため、読出し行インデックス保持部１１１の先頭に１を書き込む。
【００９０】
次に、図１１に示すように、第２要探索、掃き出し回路１６０には、第３行が要フラグ０と共に入力され、第２列の要行は未だ見つかっていない上、第３行第２列は非零であるため、これを要行とし、内部に第３行を確保し、またその行を第２行保持部１７０へ送り、第２要フラグ保持部１８０に１を送る。
また、行列メモリ１２０から第４行が同様に読み出され、第１要探索、掃き出し回路１３０に送られる。第１要探索、掃き出し回路１３０は既に要行を確保しているので、第４行を掃き出す。第４行第１列は零であるので、そのまま第４行を第１行保持部１４０へ送られる。また、第１要フラグ保持部１５０には０が送られる。
また、第２要探索、掃き出し回路１６０から読み出される第２行を行列メモリ１２０に書き込む。
行インデックスメモリ１１０に戻ってくる書込み行インデックスＳ１１である２とともに第２要フラグ保持部１８０から１が到来するため、要行インデックス保持部１１２に２を書き込む。
【００９１】
次に、図１２に示すように、第２要探索、掃き出し回路１６０には、第４行が要フラグ０と共に入力され、第２列の要行は既に見つかっているので、第４行を掃き出した後、その行を第２行保持部１７０へ送り、また第２要フラグ保持部１８０に０を送る。
行列メモリ１２０からは何も読み出されず、第１要探索、掃き出し回路１３０から内部に保持した要行を第１行保持部１４０へ送る。また、第２要探索、掃き出し回路１６０から読み出される第３行を行列メモリ１２０に書き込む。
さらに、行インデックスメモリ１１０に到来する書込み行インデックスＳ１１である３とともに第２要フラグ保持部１８０から１が到来するため、要行インデックス保持部１１２に３を書き込む。
【００９２】
そして、図１３に示すように、第１行保持部１４０から到来した第２行に対して、第２要探索、掃き出し回路１６０において内部に確保した要行第３行で掃き出しを行う。つまり、この時に要行同士の掃き出しを行う。
掃き出された第２行は第２行保持部１７０へ送られる。また、第２行保持部１７０から読み出される第４行を行列メモリ１２０に書き込む。
さらに、行インデックスメモリ１１０に戻ってくる書込み行インデックスＳ１１である４とともに第２要フラグ保持部１８０から０が到来するため、読出し行インデックス保持部１１１に４を書き込む。
【００９３】
さらに、図１４に示すように、第２要探索、掃き出し回路１６０の内部に確保した要行第３行を第２行保持部１７０へ送る。また、第２行保持部１７０から読み出される第１列要行である第２行を行列メモリ１２０に書き込む。
また、要行インデックス保持部１１２から読出し行インデックス保持部１１１の下位アドレスに値を移す。
まず、行インデックス２を読出し行インデックス保持部１１１に書き込む。この値は行列メモリ１２０の書き込み行インデックスＳ１１にも用いられる。
【００９４】
最後に、図１５に示しように、第２行保持部１７０から読み出される第２列要行である第３行を行列メモリ１２０に書き込む。
また、要行インデックス保持部１１２から読出し行インデックス保持部１１１の下位アドレスに値を移す。今回は、行インデックス３を読出し行インデックス保持部１１１に書き込む。
また、この値を行列メモリ１２０の書き込み行インデックスＳ１１にも用いる。
以上で、第１列、第２列の要探索、掃き出しは完了する。
【００９５】
第３列、第４列を要探索する際は、行列メモリ１２０から行を読み出す際に、行インデックスメモリ１１０の先頭アドレスから順に行インデックスを読み出せば、未だ要になっていない行を優先的に読み出せるので、はじめて見つかった対象列の非零要素を要とできる。
また、各列の基本変形に対して、各行は要探索か掃き出しのいずれかの対象となればよいので、より高速な対角化が可能となる。第３列、第４列の要探索、掃き出しについても、同様に第１要探索、掃き出し回路が第３列、第２要探索、掃き出し回路が第４列の要探索、掃き出しを担当することにより、より高速な対角化が可能になり、これが完了すれば、図１６に示すように、行列の対角化は完了する。
【００９６】
要探索、掃き出し回路１３０，１６０は具体的には図１７のようになる。図１７に示す構成は、行列が０か１の要素しか持たない場合の要探索、掃き出し回路である。
【００９７】
図１７の要探索、掃き出し回路１３０（１６０）は、セレクタ１３１、状態遷移保持部１３２、要行選択セレクタ１３３、要行保持部１３４、アンドゲート１３５、および掃き出し部１３６を主構成要素として有している。
【００９８】
図１７の要探索、掃き出し回路１３０においては、まず対角化が開始したら、状態遷移保持部１３２において、要探索状態になる。
入力される行Ｓ３１に対し、対角化対象要素を取り出すためのセレクタ１３１を通り対角化対象列の要素Ｓ３２のみ取り出し、この対象要素が零の場合は、状態遷移保持部１３２は、要探索状態を維持し、要フラグＳ３３は０、掃き出しフラグＳ３４は０を出力する。
初めて対象要素Ｓ３２が非零要素であった場合、要フラグＳ３３は１、掃き出しフラグＳ３４は０を出力し、要行選択セレク１３３によって、入力行Ｓ３１が要行として要行保持部２０４に取り込まれる。
また、状態遷移保持部１３２は要探索状態から掃き出し状態へ遷移する。なお、入力要フラグＳ３９が０の場合は上記の通り動作するが、１の場合は入力行をそのまま出力行とし、出力要フラグＳ３３にも入力要フラグ１をそのまま出力する。状態も要探索状態のまま変わらない。
【００９９】
掃き出し状態では、要フラグＳ３３には基本的に０を出力し、要行を要行保持部１３４に保持し続ける。
対象要素Ｓ３２が非零の場合、掃き出しフラグＳ３４に１を出力し、掃き出し部１３６で入力行と要行の排他的論理和が計算され、掃き出し部から行Ｓ３８が出力され行列メモリ１２０に書き込まれる。
対象要素Ｓ３２が零の場合は掃き出しフラグＳ３４に０を出力し、入力行Ｓ３１はそのままＳ３８へ出力され、再び行列メモリにその行が書き込まれる。
掃き出しが完了すると、要探索状態へ戻るか、その行列の対角化が終了した場合はアイドル（ＩＤＬＥ）状態へ戻る。なお、入力要フラグＳ３９が０の場合も１の場合も上記の通り動作するが、入力要フラグＳ３９が１の場合のみ、出力要フラグＳ３３にはそのまま１を出力する。
また、第１要探索、掃き出し回路１３０の場合は、入力要フラグに常に０を入力しておけばよい。
【０１００】
なお、行列が０か１以外の要素を持つ要探索、掃き出しは、要と掃き出し対象となる行の対象要素を比べ、掃き出し対象となる行の対角要素を要で割った値を、要行保持部の後段で掛け算して、掃き出すことにより実現される。
また、初期に行列メモリ１２０から行を読み出す際は、行インデックスメモリ１１０にわざわざアドレスと同じ値を書き込んでおかなくとも、直接１、２、３、４と値をインクリメントして直接行列メモリ１２０から行を読み出してもよい。
【０１０１】
なお、この方法は、どんな行列の大きさでもパラレルに処理する対角化列数が何列でも適用が可能である。
また、この方法は、行を読み出して列毎に基本変形する場合以外に、列を読み出して行毎に基本変形をする場合にも適用できる。
【０１０２】
以上説明したように、行列対角化部１００によれば、要探索、掃出しは一行読出すごとにパラレルに行い、要行同士の掃出しは行読出しの最後に行うことにより高速に対角化される。これにより、たとえば３列並列に基本変形を行うと行読出し回数をおよそ１／３に減らすことができる。
また、次の基本変形から未だ要になっていない行を優先的に読み出せるため、はじめて見つかった対象列の非零要素を要とでき、各列の基本変形に対して、各行は要探索か掃き出しのいずれかの対象となればよいので、より高速な対角化が可能となる。
以上の方法により、ｔ列パラレルで対角化を行った場合、およそ行数×列数／ｔ回の行読出しで対角化が可能となる。
【０１０３】
ところで、ＡＢＰ復号器（復号装置）については、動作周波数低減のため、内側繰り返し復号二回目以降については、対角化を限られた列のみ行うような以下の方法を用いている。
【０１０４】
図１８は、ＲＳ（２０４，１８８）を対象としたＡＢＰ復号器の第１の内側繰り返しフローを示す図である。
【０１０５】
内側繰り返し二回目以降の対角化対象となる列と対角化対象とならない列の集合の分割方法を、前繰り返しの両集合の一部の入れ替えに限定し、その時に入れ替えられ新しく対角化対象となった列についてのみ前対角化で更新されたパリティ検査行列を対象として対角化を行う。
【０１０６】
この場合は、図１８では、繰り返し一回目の復号が行われた後、二回目のソート時、信頼度が更新された１２８列のうち、信頼度の最も大きい４列のみ、対角化対象から外し、残り１５０４列のうち信頼度の小さい４列を新しく対角化対象１２８列の集合に加える。
この新しい対角化対象４列について、前繰り返しで対角化された後のパリティ検査行列に対して対角化を行う。
このとき、今回新しく対角化対象から外れた列に対応する要行は、既要行リストからは外され、新しい対角化対象４列に対して改めて要行になることができる。そしてそのパリティ検査行列を用いて信頼性伝播（ＢＰ）を行う。
以降の繰り返しではこれを繰り返す。
【０１０７】
ＡＢＰ復号装置の所要動作クロックサイクル数を低減できれば、より繰り返し数を増やすことができ、動作周波数も低減することも可能である。
たとえば、繰り返し二回目以降の動作所要クロックサイクル数を見積もる。Ｔ２を繰り返し二回目以降に各繰り返しで必要とするクロックサイクル数とする。
ここで、Ｔ２は以下のように表すことができる。
【０１０８】
【数１８】
2008205546.tif 000020
【０１０９】
ここで、Ｔsortは、内側繰り返し二回目以降のソートに必要とするクロックサイクル数を示し、Ｔdiagは、対角化に必要とするクロックサイクル数を示し、Ｔbpは、信頼性伝播（ＢＰ）に必要とするクロックサイクル数を示している。
【０１１０】
上述したように、ここではＲＳ（２０４，１８８）を想定し、対角化回路は４列パラレルに基本変形するとする。
Ｔsortとしては、逆写像ソートを利用した場合、入力数分の１２８クロックサイクルが必要となる。また、Ｔdiagとしては、一回の行読出しで要探索と掃き出しを一度に行い、今回４列パラレルに基本変形するので、かつ繰り返し二回目以降は４列のみ対角化するので、最低４×１２８／４＝１２８クロックサイクル数必要となる。
また、信頼性伝播（ＢＰ）に必要とするクロックサイクル数Ｔbpは、対角化対象となった１２８列のみＬＬＲ更新を行うので、１２８クロックサイクル数必要となる。
ただし、前繰り返しの信頼性伝播（ＢＰ）により、毎クロックサイクル１列ずつ更新された信頼度をソート装置に入力すれば、信頼性伝播（ＢＰ）とソートはほぼ同時に行うことが可能なため、Ｔsort＝０とすることができる。
【０１１１】
これに対応してＡＢＰ復号器を図６の回路に関連付けると、図１９に示すように表すことができ、図２０に示すように、信頼性伝播（ＢＰ）部３５の動作を行いながら、ソートも同時並列的に動作でき、これが１２８クロックサイクルかかる。
しかし、新しく要行になれる行インデックスＳ４１はソート部３２の処理が完了しないと確定しないため、ソート部３２の処理動作が完了後、図２１に示すようにパリティ検査行列の対角化を１２８クロックサイクルかけて行われることになる。
つまり、Ｔ２は次のようになり、内側繰り返し二回目以降は、繰り返し一回につき２５６クロックサイクルかかる。
【０１１２】
【数１９】
2008205546.tif 000021
【０１１３】
これをさらに少ないクロックサイクルで動作できれば、動作周波数を低減したり繰り返し数を増やしたりすることが可能である。
【０１１４】
好適な本実施形態においては、ソート部３２と対角化部３３と信頼性伝播（ＢＰ）部３５をパラレル（並列）に動作させる。そのために、信頼性伝播（ＢＰ）部３５に読み出しているパリティ行を同時に対角化部３３の要探索、掃き出し回路へ送り込む方法が考えられる。
しかし、この時点で、次回の繰り返しで新しく対角化対象列になる４列は決定しているが、次回の繰り返しで新しく対角化対象から外れる４列が決定しておらず、つまりは要行リストから外れる４行について決定できないため、信頼性伝播（ＢＰ）が行われている時点で次の繰り返しのパリティ検査行列を生成するのは困難である。
そのため、本実施形態においては、ソート後の信頼性の順番により、次回の繰り返しで新しく対角化対象列になる４列だけでなく、次回の繰り返しで新しく対角化対象から外れる４列も決定する方法を新たに用いて、ソート部３２と対角化部３３と信頼性伝播（ＢＰ）部３５のパラレル動作を実現している。
これにより、ソート部３２と対角化部３３と信頼性伝播（ＢＰ）部３５をパラレルに動作させることが可能になり、動作周波数を低減したり、繰り返し数を増やしたりすることが可能となる。
【０１１５】
以下、具体例を挙げて説明する。
図２２は、本実施形態に係るＡＢＰ復号器の第２の内側繰り返しフローを示す図である。
【０１１６】
この第２の内側繰り返しフローは、図１８の第１の例と同様、ＲＳ（２０４，１８８）を例としている。
内側繰り返し二回目以降の対角化対象となる列と対角化対象とならない列の集合の分割方法を、前繰り返しの両集合の一部の入れ替えに限定し、その時に入れ替えられ新しく対角化対象となった列についてのみ前対角化で更新されたパリティ検査行列を対象として対角化を行う。
さらに、本実施形態では、対角化対象から外れる４列を前回の繰り返しの時点で決定する。具体的には、図２２に示すように、受信語を信頼度にしたがってソートしたら、その対角化対象１２８列のうち信頼度の大きい方から４列を、この時点で、繰り返し二回目に対角化対象列から新たに外れる４列と決定する。
【０１１７】
繰り返し一回目の信頼性伝播（ＢＰ）復号が行われた後、二回目のソート時、信頼度が更新された１２８列のうち、繰り返し一回目に決定した４列を本二回目では対角化対象から外し、その今回対角化対象から外れる４列以外で信頼度の最も大きい４列を繰り返し三回目に対角化対象から外れる４列と新たに決定する。以降これを繰り返す。
逆に、対角化対象に新たに加わる４列については、図１８の例と同様で、対角化対象でない１５０４列のうち信頼度の小さい４列を新しく対角化対象１２８列の集合に加える。これについても、対角化非対象１５０４列はＬＬＲ更新されないため、例えば繰り返し一回目のソートの時点で繰り返し二回目の新たに対角化対象に加わる４列は決定している。この新しい対角化対象４列について、前繰り返しで対角化された後のパリティ検査行列に対して対角化を行う。このとき、今回新しく対角化対象から外れた列に対応する要行は、既要行リストからは外され、新しい対角化対象４列に対して改めて要行になることができる。
そしてそのパリティ検査行列を用いて信頼性伝播（ＢＰ）を行う。以降の繰り返しではこれを繰り返す。
【０１１８】
以上より、ある内側繰り返しＮ回目のソート完了時点で、（Ｎ＋１）回目の新たに対角化対象になる４列と新たに対角化対象から外れる４列とそれに対応する要行が決定できる。
なお、図１８の例でも対角化対象１２８列中信頼度最大の４列は誤っている可能性が低いとして対角化対象列から強制的に外れるように、図２２の例において、本繰り返しで対角化対象から外れる４列以外の１２４列の中から信頼度が最大の４列を誤っている可能性が低いとして次の内側繰り返しにおいて強制的に新しく対角化対象から外すとしても特に問題はない。
【０１１９】
図２３は、シミュレーションモデルを示す図である。
このシミュレーションモデル４０は、図２３に示すように、ＲＳ符号化器４１、ＢＰＳＫ変調器４２、ＡＷＧＮチャネル４３、ＢＰＳＫ復調器４４、およびＡＢＰ復号器４５を有する。
図２４は、シミュレーション結果を示す図である。
図２４は、ＲＳ（２０４，１８８）を想定した場合のフレームエラーレート（Ｆｒａｍｅ  Ｅｒｒｏｒ  Ｒａｔｅ）を示す図であって、Ａで示す曲線が既存手法の復号性能を示し、Ｂで示す曲線が本実施形態に手法における復号性能を示している。
【０１２０】
既存技術と比較して、図２３に示すようなＢＰＳＫ変調、ＡＷＧＮチャネルを用いたシミュレーションモデルにおいて、図２４に示すように性能劣化はないことがわかる。
これにより、信頼性伝播（ＢＰ）とソートを行っているのと同時並列的に、次の信頼性伝播（ＢＰ）のためのパリティ検査行列を生成するための対角化作業を行うことが可能になる。
つまり、Ｔ２は次のようになる。
【０１２１】
【数２０】
2008205546.tif 000022
【０１２２】
その結果、繰り返し復号二回目以降の動作が高速化される。
【０１２３】
図２５は本発明の内側繰り返し方法の二回目以降のＡＢＰ復号器の動作状態例を示す図である。
【０１２４】
この例においては、信頼性伝播（ＢＰ）部３５が動作している時点で、次のパリティ検査行列対角化のための新しい対角化対象列インデックスＳ３５だけでなく、新しく対角化対象列から外れる列に対応する要行、つまり新しく要になれる行インデックスＳ４１も決定している。
このため、本繰り返しのＬＬＲ更新のために信頼性伝播（ＢＰ）部３５に読み出しているパリティ検査行Ｓ３７を次の繰り返しの対角化のために要探索、掃き出し回路にも同時に読み出すことで、対角化と信頼性伝播（ＢＰ）を同時並列的に行うことができる。
【０１２５】
ここで、新しく対角化対象となった列についてのみ対角化するフロー例を、行列を使って説明する。
今回は簡単のため、以下の４×６-行列Ｈを、繰り返し一回目において第１、２、３、４列について対角化を行った後、繰り返し二回目において第５、６列について対角化する例を考える。
このとき、新しく対角化対象から外れる二列を第２、３列とすると、対応する要行は第３、４行なので、新しく第３、４行は要になることができる。
【０１２６】
【数２１】
2008205546.tif 000023
【０１２７】
行列Ｈを第１、２、３、４列について対角化すると、以下のＨnewのようになる。
【０１２８】
【数２２】
2008205546.tif 000024
【０１２９】
二回目で第３、４列が新しく対角化対象から外れ、第５、６列が新しく対角化対象となる。この時、第２、３列の元要行である第３、４は新しく要行になることができる。
まず、第５列について次のように基本変形する。
【０１３０】
【数２３】
2008205546.tif 000025
【０１３１】
次に、第６列について次のように基本変形する。
【０１３２】
【数２４】
2008205546.tif 000026
【０１３３】
以上で、新たに第５、６列についての対角化が完了する。
この処理に対応した具体的な構成について説明する。
【０１３４】
図２６は、本発明の実施形態に係るＡＢＰ復号器の行列対角化部の第２の構成例を示す図である。
【０１３５】
本第２の構成例に係る対角化部１００Ａが図７の第１の構成例に係る対角化部１００と異なる点は、第１要探索、掃き出し回路１３０と第２要探索、掃き出し回路１６０との間に、第１要列保持部１９０が、第１行保持部１４０および第１要フラグ保持部１５０に並列に配置され、第２要探索、掃き出し回路１６０の出力側に、第２要列保持部２００が、第２行保持部１７０および第２要保持部１８０に並列に配置され、さらに、要フラグＳ２１、読出し行インデックスＳ１２、書込み行インデックスＳ１１、および要列インデックスを保持可能な要列インデックスメモリ２１０が配置されている点にある。
【０１３６】
以下、図２６並びに図２７〜図３４に関連付けて繰り返し二回目以降の具体的な対角化部の動作について説明する。
【０１３７】
対角化部３３の内部の要探索、掃き出し回路に送るパリティ検査行の順番は、過去要になっていない行を先に読み出す必要がある。つまり、繰り返し二回目以降の対角化においては、新しく要になれる行を先に読み出すことになる。
信頼性伝播（ＢＰ）については、パリティ検査行Ｓ３７と列インデックスＳ３６さえ対応していれば、順番は任意なので、行の順は要探索、掃き出し回路へ送る行の順番にあわせ、新しく要になれる行を先に読み出す。
【０１３８】
図２６に示すように、第２の構成例に係る対角化部１００Ａでは、第１の構成例に係る対角化部１００（図７）と同様、行インデックスメモリ１１０、行列メモリ１２０、要探索、掃き出し回路１３０，１６０が存在し、それに加えて要列インデックスメモリ２１０が存在する。
特に、繰り返し二回目では、行インデックスメモリ１１０からは、はじめは入力の新しく要行になれる行インデックスＳ１２を読み出し、その後読出し行インデックス保持部１１１の先頭から順に、新しく要行になれる行インデックスＳ１０を除いて行インデックスＳ１２が読み出される。
また、要列インデックスメモリ２１０には、行インデックスＳ１２が対応するアドレスに、その行インデックスＳ１２と対応する要列が保持されている。さらに、第１要探索、掃き出し回路１３０からは要行が見つかったときに、その対象となる列Ｓ２２を第１要列保持部１９０に出力する。第２要探索、掃き出し回路１６０についても同様である。
【０１３９】
図７の構成例の場合と同様に、Ｈを第１、２、３、４列について対角化し終わった後に、図２６に示すように、行列メモリ１２０には対角化された行列、行インデックスメモリ１１０には、行インデックスが図１６と同様に保持される。
さらに、要列インデックスメモリ２１０には、第２要探索、掃き出し回路１６０の出力の要フラグＳ２１が１の場合に書き込みアドレスを要行Ｓ１１として対応する要列Ｓ２５が書き込まれる。
その結果、図２６に示すように、アドレス１、つまり第１行の要列は第４列、アドレス２、つまり第２行の要列は第２列というように書き込まれる。
【０１４０】
次に、次の繰り返し二回目で新しく要になれる行インデックスＳ１０と新しい対角化列インデックスＳ２６が入力される場合を考える。ここでは、例として、第２、３列が対角化対象から外れ、つまり対応する第３、４行が新しく要になることができ、第５、６列が新しく対角化対象になる場合を考える。
つまり、入力として、新しく要行になれる行インデックスＳ１０＝｛３，４｝、新しい対角化対象列インデックスＳ２６＝｛５，６｝が行インデックスメモリ１１０に入力される。このとき、本繰り返しで信頼性伝播（ＢＰ）部３５に送るべき対角化されたパリティ検査行列は既に前繰り返しで対角化され行列メモリ１２０に保持されているので、次回繰り返しのパリティ検査行列対角化のためにパリティ検査行Ｓ３７を要探索、掃き出し回路に送りながら、その行を信頼性伝播（ＢＰ）部３５に送って今回の繰り返しのＬＬＲ更新も同時に行うことができる。
【０１４１】
図２７に示すように、まず新しい対角化対象列インデックス５、６が前もって入力され、要探索、掃き出し回路二つにそれぞれ対角化対象列５、６が設定されている。
ここに、新しく要になれる行インデックスＳ１０である３が入力されると、これが行列メモリ１２０に読み込まれ、パリティ検査行列第３行Ｓ１３が出力される。
このパリティ検査行Ｓ１３は、まず要探索、掃き出し回路へ送られ、第１の構成例の場合と同様に、対象列が非零なら要とし、その行を内部に保持し、要が見つかった後は入力される行に対して掃き出しを行う。
さらに、本例においては、要行が見つかった場合、要フラグに１を出力する以外に、要列として対応する列を出力するので、ここでは、第１要探索、掃き出し回路１３０は、要フラグＳ１８である１と共に要列Ｓ２２である５を出力する。
さらに、今回の繰り返しのＬＬＲ更新のために、信頼性伝播（ＢＰ）部３５へ読み出されたパリティ検査行列第３行が出力される。また、要列インデックスメモリ２１０から行インデックスＳ１２である３に対応する要列２が信頼性伝播（ＢＰ）部３５に出力される。
【０１４２】
次に、図２８に示すように、新しく要行になれる行インデックスＳ１０である４が入力され、パリティ検査行列第４行が行列メモリ１２０から読み出される。
このパリティ検査行Ｓ１３も同様に要探索、掃き出し回路へ送られるのと同時並列的に、信頼性伝播（ＢＰ）部３５にも出力される。また、要列インデックスメモリ２１０から行インデックスＳ１２である４に対応する要列３が信頼性伝播（ＢＰ）部３５に出力される。
【０１４３】
次に、図２９に示すように、以降は新しく要行になれる行インデックスＳ１０が入力されないため、行インデックスメモリ１１０の読出し行インデックス保持部１１１の先頭から行インデックスを読み出す。
ただし、既に新しく要行になれる行インデックスＳ１０に入っていた行インデックスについては、読み出しをスキップする。ここでは、行インデックス１を読み出し、パリティ検査行列第１行が行列メモリ１２０から読み出される。
この行も同様に要探索、掃き出し回路へ送られるのと同時に、信頼性伝播（ＢＰ）部３５にも出力される。また、要列インデックスメモリ２１０から行インデックスＳ１２である１に対応する要列４が信頼性伝播（ＢＰ）部３５に出力される。
また、このとき、要フラグＳ２１として１が要列インデックスに入力されるため、要列インデックスメモリ２１０の書き込み行インデックスＳ１１である３のアドレスに新たな対応する列インデックスＳ２５の５を書き込む。
【０１４４】
次に、図３０に示すように、行インデックスメモリ１１０から行インデックスＳ１２を読み出す。ただし、行インデックス４は既に新しく要になれる行インデックスＳ１０に入っていたため、読出し行インデックス保持部１１１の次の行インデックス２を読み出し、パリティ検査第２行が行列メモリ１２０から読み出される。
これも同様に要探索、掃き出し回路へ送られるのと同時並列的に、信頼性伝播（ＢＰ）部３５にもパリティ検査行が出力される。また、要列インデックスメモリ２１０から行インデックスＳ１２である２に対応する要列１が信頼性伝播（ＢＰ）部３５に出力される。
また、このとき、要フラグ１が要列インデックスメモリ２１０に入力されるため、要列インデックス２１の書き込み行インデックスＳ１１である４に新たな対応する列インデックスＳ２５である６を書き込む。なお、ここで行列メモリ１２０からの行読出しは終了する。
【０１４５】
次に、図３１〜図３３に示すように、新しい要行どうしの掃き出しを行い、図３４に示すように対角化も完了する。
以上で内側繰り返し二回目以降の動作は完了する。
これにより、ＲＳ（２０４，１８８）を想定し、対角化回路で４列パラレルに基本変形を行う場合を考えると、繰り返し二回目以降に各繰り返しで必要とするクロックサイクル数は、Ｔ２は１２８となり、図７の第１の構成例と比べて、半分の動作クロックサイクル数で繰り返しを実現できる。
なお、ソート部では、本繰り返しで新しく対角化対象から外れる４列以外の１２４列の中から、信頼性の大きい４列を次の繰り返しで新しく対角化対象から外れる４列とする必要がある。
また、ソート部３２から新しく要になれる行インデックスを得るには、ソート部３２が列インデックスに対応する要行インデックスを知る必要がある。この場合、たとえば列インデックスだけでなく、対応する要行インデックスもソート部３２に送る方法などが適用可能である。
【０１４６】
以上説明したように、本実施形態においては、ソート後の信頼性の順番により、次回の繰り返しで新しく対角化対象列になる４列だけでなく、次回の繰り返しで新しく対角化対象から外れる４列も決定する方法を新たに用いて、ソート部３２と対角化部３３と信頼性伝播（ＢＰ）部３５のパラレル動作を実現している。
これにより、ソート部３２と対角化部３３と信頼性伝播（ＢＰ）部３５をパラレルに動作させることが可能になり、動作周波数を低減したり、繰り返し数を増やしたりすることが可能となる利点がある。
【０１４７】
なお、以上詳細に説明した方法は、上記手順に応じたプログラムとして形成し、ＣＰＵ等のコンピュータで実行するように構成することも可能である。
また、このようなプログラムは、半導体メモリ、磁気ディスク、光ディスク、フロッピー（登録商標）ディスク等の記録媒体、この記録媒体をセットしたコンピュータによりアクセスし上記プログラムを実行するように構成可能である。
【図面の簡単な説明】
【０１４８】
【図１】パリティ検査行列Ｈｎｅｗに対応するタナーグラフである。
【図２】ＡＢＰ復号法を用いた繰り返し復号のフローチャートである。
【図３】ＡＢＰ復号装置の繰り返し毎のフローの一列を示す図である。
【図４】デジタル信号受信機、たとえばデジタルテレビなどの誤り訂正システムにＡＢＰ復号器を用いた通信システムの構成例を示す図である。
【図５】ＭＡＰ復号が後段についたＡＢＰ復号器の構成例を示す図である。
【図６】ＡＢＰ復号器の構成例を示す図である。
【図７】本発明の実施形態に係るＡＢＰ復号器の対角化部の第１の構成例を示す図であり、処理を説明するための第１図である。
【図８】第１の構成例に係る対角化部の処理を説明するための第２図である。
【図９】第１の構成例に係る対角化部の処理を説明するための第３図である。
【図１０】第１の構成例に係る対角化部の処理を説明するための第４図である。
【図１１】第１の構成例に係る対角化部の処理を説明するための第５図である。
【図１２】第１の構成例に係る対角化部の処理を説明するための第６図である。
【図１３】第１の構成例に係る対角化部の処理を説明するための第７図である。
【図１４】第１の構成例に係る対角化部の処理を説明するための第８図である。
【図１５】第１の構成例に係る対角化部の処理を説明するための第９図である。
【図１６】第１の構成例に係る対角化部の処理を説明するための第１０図である。
【図１７】本実施系形態に係る要探索、掃き出し回路の構成例を示す図である。
【図１８】、ＲＳ（２０４，１８８）を対象としたＡＢＰ復号器の第１の内側繰り返しフローを示す図である。
【図１９】内側繰り返しフローに関するＡＢＰ復号器の動作状態を説明するため第１図である。
【図２０】内側繰り返しフローに関するＡＢＰ復号器の動作状態を説明するため第２図である。
【図２１】内側繰り返しフローに関するＡＢＰ復号器の動作状態を説明するため第３図である。
【図２２】本実施形態に係るＡＢＰ復号器の第２の内側繰り返しフローを示す図である。
【図２３】シミュレーションモデルを示す図である。
【図２４】シミュレーション結果を示す図である。
【図２５】本発明の内側繰り返し方法の二回目以降のＡＢＰ復号器の動作状態例を示す図である。
【図２６】本発明の実施形態に係る対角化部の第２の構成例を示す図であり、処理を説明するための第１図である。
【図２７】第２の構成例に係る対角化部の処理を説明するための第２図である。
【図２８】第２の構成例に係る対角化部の処理を説明するための第３図である。
【図２９】第２の構成例に係る対角化部の処理を説明するための第４図である。
【図３０】第２の構成例に係る対角化部の処理を説明するための第５図である。
【図３１】第２の構成例に係る対角化部の処理を説明するための第６図である。
【図３２】第２の構成例に係る対角化部の処理を説明するための第７図である。
【図３３】第２の構成例に係る対角化部の処理を説明するための第８図である。
【図３４】第２の構成例に係る対角化部の処理を説明するための第９図である。
【符号の説明】
【０１４９】
１０・・・通信システム、１１・・・ＲＳ符号化器、１２・・・インタリーバ、１３・・・畳み込み符号器、１４・・・畳み込み符号の軟出力復号器、１５・・・デインタリーバ、１６・・・ＡＢＰ繰り返し復号器、１７・・・チャネル、２０・・・復号器、２１・・・ＡＢＰ復号部、２２・・・限界距離（ＢＤ）復号部、２３・・・受信信頼度（ＬＬＲ）保持部、２４・・・ＭＡＰ復号部、３０・・・ＡＢＰ復号器、３１・・・ソート入力選択部、３２・・・ソート部、３３・・・パリティ検査行列の対角化部、３４・・・信頼度（ＬＬＲ）保持部、３５・・・信頼性伝播（ＢＰ）部、１００・・・行列対角化部、１１０・・・行インデックスメモリ、１２０・・・行列メモリ、１３０・・・第１要探索・掃き出し回路、１４０・・・第１行保持部、１５０・・・第１要フラグ保持部、１６０・・・第２要探索、掃き出し回路、１７０・・・第２行保持部、１８０・・・第２要フラグ保持部、１９０・・・第１要列保持部、２００・・・第２要列保持部、２１０・・・要列インデックスメモリ。
【図１】
2008205546.tif 000027
【図２】
2008205546.tif 000028
【図３】
2008205546.tif 000029
【図４】
2008205546.tif 000030
【図５】
2008205546.tif 000031
【図６】
2008205546.tif 000032
【図７】
2008205546.tif 000033
【図８】
2008205546.tif 000034
【図９】
2008205546.tif 000035
【図１０】
2008205546.tif 000036
【図１１】
2008205546.tif 000037
【図１２】
2008205546.tif 000038
【図１３】
2008205546.tif 000039
【図１４】
2008205546.tif 000040
【図１５】
2008205546.tif 000041
【図１６】
2008205546.tif 000042
【図１７】
2008205546.tif 000043
【図１８】
2008205546.tif 000044
【図１９】
2008205546.tif 000045
【図２０】
2008205546.tif 000046
【図２１】
2008205546.tif 000047
【図２２】
2008205546.tif 000048
【図２３】
2008205546.tif 000049
【図２４】
2008205546.tif 000050
【図２５】
2008205546.tif 000051
【図２６】
2008205546.tif 000052
【図２７】
2008205546.tif 000053
【図２８】
2008205546.tif 000054
【図２９】
2008205546.tif 000055
【図３０】
2008205546.tif 000056
【図３１】
2008205546.tif 000057
【図３２】
2008205546.tif 000058
【図３３】
2008205546.tif 000059
【図３４】
2008205546.tif 000060