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