(57)【要約】【目的】複数のデータ値の内から最小値及びこの最小値の次に小なる次最小値を高速に検出することが可能な最小値検出回路及び最小値検出方法を提供することを目的とする。【構成】第１のデータ値と第２のデータ値とを大小比較して小なる方を第１値、大なる方を第２値とすると共に、データ値各々の内の第３のデータ値と第４のデータ値とを大小比較して小なる方を第３値、大なる方を第４値とする。この際、上記第１値及び第３値の内で小なる方を第１〜第４のデータ値における最小値とする。また、上記第１値及び第３値の内の大なる方を第１の次最小値候補とし、この第１値が第３値より小なる場合には第２値を第２の次最小値候補とする一方、第１値が第３値より大なる場合には第４値を第２の次最小値候補とする。この際、第１の次最小値候補及び第２の次最小値候補の内で小なる方を第１〜第４のデータ値における次最小値とする。。【選択図】  図１
2012209632.tif 000002
【特許請求の範囲】
【請求項１】
複数のデータ値の内から最小値及び当該最小値の次に小なる次最小値を夫々検出する最小値検出回路であって、
前記データ値の内の第１のデータ値と第２のデータ値とを大小比較して小なる方を第１値、大なる方を第２値とする第１比較部と、
前記データ値の内の第３のデータ値と第４のデータ値とを大小比較して小なる方を第３値、大なる方を第４値とする第２比較部と、
前記第１値及び前記第３値の内で小なる方を前記第１〜第４のデータ値における最小値とすると共に、前記第１値及び前記第３値の内の大なる方を第１の次最小値候補とし、前記第１値が前記第３値より小なる場合には前記第２値を第２の次最小値候補とする一方、前記第１値が前記第３値より大なる場合には前記第４値を前記第２の次最小値候補とし、前記第１の次最小値候補及び前記第２の次最小値候補の内で小なる方を前記第１〜第４のデータ値における次最小値とする判定部と、を有することを特徴とする最小値検出回路。
【請求項２】
前記データ値は、低密度パリティ検査符号をＭｉｎ−Ｓｕｍアルゴリズムに従って復号する復号器におけるギャラガー関数で表される複数の変数値であることを特徴とする請求項１記載の最小値検出回路。
【請求項３】
４ｎ（ｎは２以上の整数）個のデータ値の内から最小値及び当該最小値の次に小なる次最小値を夫々検出する最小値検出回路であって、
前記４ｎ個のデータ値を２つずつの２ｎ個のグループに群分けし各グループ毎にデータ値同士の大小比較を行って小なる方を暫定最小値、大なる方を暫定次最小値として夫々出力する２ｎ個の比較部と、
前記２ｎ個の比較部を２つずつのｎ個のグループに群分けし各グループ毎に、前記比較部の一方から出力された前記暫定最小値及び前記暫定次最小値を夫々第１値及び第２値とし、前記比較部の他方から出力された前記暫定最小値及び前記暫定次最小値を夫々第３値及び第４値とし、前記第１値〜前記第４値の内から最小値及び次最小値を判定し、当該最小値及び次最小値を夫々暫定最小値及び暫定次最小値として中継出力するｎ個の初段判定部と、
前記ｎ個の初段判定部を２つずつのｎ／２個のグループに群分けし各グループ毎に、前記初段判定部の一方から出力された前記暫定最小値及び前記暫定次最小値を夫々第１値及び第２値とし、前記初段判定部の他方から出力された前記暫定最小値及び前記暫定次最小値を夫々第３値及び第４値とし、前記第１値〜前記第４値の内から最小値及び次最小値を判定し、当該最小値及び次最小値を夫々暫定最小値及び暫定次最小値として中継出力するｎ／２個の次段判定部と、を含み、
前記初段判定部及び前記次段判定部の各々は、前記第１値及び前記第３値の内で小なる方を前記暫定最小値とすると共に、前記第１値及び前記第３値の内の大なる方を第１の次最小値候補とし、前記第１値が前記第３値より小なる場合には前記第２値を第２の次最小値候補とする一方、前記第１値が前記第３値より大なる場合には前記第４値を前記第２の次最小値候補とし、前記第１の次最小値候補及び前記第２の次最小値候補の内で小なる方を前記暫定次最小値とすることを特徴とする最小値検出回路。
【請求項４】
前記データ値は、低密度パリティ検査符号をＭｉｎ−Ｓｕｍアルゴリズムに従って復号する復号器におけるギャラガー関数で表される複数の変数値であることを特徴とする請求項２記載の最小値検出回路。
【請求項５】
複数のデータ値の内から最小値及び当該最小値の次に小なる次最小値を夫々検出する最小値検出方法であって、
前記データ値各々の内の第１のデータ値と第２のデータ値とを大小比較して小なる方を第１値、大なる方を第２値とすると共に、前記データ値各々の内の第３のデータ値と第４のデータ値とを大小比較して小なる方を第３値、大なる方を第４値とする第１ステップと、
前記第１値及び前記第３値の内で小なる方を前記第１〜第４のデータ値における最小値とすると共に、前記第１値及び前記第３値の内の大なる方を第１の次最小値候補とし、前記第１値が前記第３値より小なる場合には前記第２値を第２の次最小値候補とする一方、前記第１値が前記第３値より大なる場合には前記第４値を前記第２の次最小値候補とし、前記第１の次最小値候補及び前記第２の次最小値候補の内で小なる方を前記第１〜第４のデータ値における次最小値とする第２ステップと、を有することを特徴とする最小値検出方法。
【請求項６】
前記データ値は、低密度パリティ検査符号をＭｉｎ−Ｓｕｍアルゴリズムに従って復号する復号器におけるギャラガー関数で表される複数の変数値であることを特徴とする請求項５記載の最小値検出方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ数が有限のデータ系列中から最小値及びこの最小値の次に小なる次最小値を検出する最小値検出回路及び最小値検出方法に関する。
【背景技術】
【０００２】
近年、データ通信システムを構築する際に採用される誤り訂正符号として、ギャラガー（Gallager）によって提案された低密度パリティ検査符号、いわゆるＬＤＰＣ（low-density parity-check code）が着目されている。ＬＤＰＣによる符号化処理では、伝送すべき情報データに対して、論理レベル１のビットが各行及び各列に一定数ずつ含まれており、その他は論理レベル０となるパリティ検査行列を生成し、これを情報データに付加したものを符号データとして生成する。かかる符号データに対する復号は、符号語の各ビットに対応するバリアブルノードと、パリティ検査和に対応するチェックノードとが枝で結ばれた形状を有するいわゆるタナーグラフ上において、確率伝播によるメッセージ・パッシング・アルゴリズムに基づき実施される。メッセージ・パッシング・アルゴリズムとして、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズム及びＭｉｎ−Ｓｕｍアルゴリズムが知られている。
【０００３】
Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムの１つとして、受信シンボルに対応した対数尤度比λｎ及び事前値対数比βｍｎに基づくギャラガー関数ｆに従って外部値対数比αｍｎを更新しつつ、パリティ検査を行なうようにしたものが知られている（特許文献１の段落［００３６］〜［００６１］の記載参照）。このＳｕｍ−Ｐｒｏｄｕｃｔアルゴリズムにづく復号処理では、上記した外部値対数比αｍｎに従って事前値対数比βｍｎを更新しつつ、この外部値対数比αｍｎと対数尤度比λｎとを用いて、複数の符号で構成される１次推定語を生成し、これら１次推定語のパリティ検査を行なう。パリティ検査によってシンドロームが０とならない場合には１次推定語に誤りがあると判断し、上記した処理を繰返し実行する。この処理の繰返し回数が所定値に到達すると、そのときの１次推定語を最終的な復号語として出力する。
【０００４】
また、Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズムで用いられる関数を近似した簡易な数式のみでギャラガー関数ｆに従った処理を実現する処理として、Ｍｉｎ−Ｓｕｍアルゴリズムが提案されている。このＭｉｎ−Ｓｕｍアルゴリズムの１つとして、外部値対数比αｍｎを、ギャラガー関数ｆにて表される複数の変数値中における最小値及びこの最小値の次に小なる最小値（以下、次最小値と称する）で近似するようにしたものが提案されている（特許文献１の段落［００６３］〜［００８２］の記載参照）。したがって、このＭｉｎ−Ｓｕｍアルゴリズムを採用してＬＤＰＣデータを復号するには、複数の変数値の系列中から最小値と次最小値とを夫々検出する最小値検出回路が必要となる。
【０００５】
この際、複数の変数値の系列中から次最小値を検出するには、先ず、変数値の系列中から最小値を検出し（第１段目）、この最小値に対応した変数値をマスクした状態で、再びこの変数値の系列中から最小値の検出を行う（第２段目）。
【０００６】
従って、外部値対数比αｍｎの絶対値Ｒｍを更新する度に、上記した如き２段階に亘る最小値検出処理を実行しなければならない為、誤り訂正処理に時間が掛かるという問題が生じた。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００７−３０６４９５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本願発明は、上記の如き問題を解決すべく為されたものであり、複数のデータ値の内から最小値及びこの最小値の次に小なる次最小値を高速に検出することが可能な最小値検出回路及び最小値検出方法を提供することである。
【課題を解決するための手段】
【０００９】
本発明による最小値検出回路は、複数のデータ値の内から最小値及び当該最小値の次に小なる次最小値を夫々検出する最小値検出回路であって、前記データ値の内の第１のデータ値と第２のデータ値とを大小比較して小なる方を第１値、大なる方を第２値とする第１比較部と、前記データ値の内の第３のデータ値と第４のデータ値とを大小比較して小なる方を第３値、大なる方を第４値とする第２比較部と、前記第１値及び前記第３値の内で小なる方を前記第１〜第４のデータ値における最小値とすると共に、前記第１値及び前記第３値の内の大なる方を第１の次最小値候補とし、前記第１値が前記第３値より小なる場合には前記第２値を第２の次最小値候補とする一方、前記第１値が前記第３値より大なる場合には前記第４値を前記第２の次最小値候補とし、前記第１の次最小値候補及び前記第２の次最小値候補の内で小なる方を前記第１〜第４のデータ値における次最小値とする判定部と、を有する。
【００１０】
本発明による最小値検出方法は、複数のデータ値の内から最小値及び当該最小値の次に小なる次最小値を夫々検出する最小値検出方法であって、前記データ値各々の内の第１のデータ値と第２のデータ値とを大小比較して小なる方を第１値、大なる方を第２値とすると共に、前記データ値各々の内の第３のデータ値と第４のデータ値とを大小比較して小なる方を第３値、大なる方を第４値とする第１ステップと、前記第１値及び前記第３値の内で小なる方を前記第１〜第４のデータ値における最小値とすると共に、前記第１値及び前記第３値の内の大なる方を第１の次最小値候補とし、前記第１値が前記第３値より小なる場合には前記第２値を第２の次最小値候補とする一方、前記第１値が前記第３値より大なる場合には前記第４値を前記第２の次最小値候補とし、前記第１の次最小値候補及び前記第２の次最小値候補の内で小なる方を前記第１〜第４のデータ値における次最小値とする第２ステップと、を有する。
【発明の効果】
【００１１】
本発明においては、第１のデータ値と第２のデータ値とを大小比較して小なる方を第１値、大なる方を第２値とすると共に、第３のデータ値と第４のデータ値とを大小比較して小なる方を第３値、大なる方を第４値とし、上記第１値及び第３値の内で小なる方を第１〜第４のデータ値における最小値とする。更に、上記第１値及び第３値の内の大なる方を第１の次最小値候補とし、この第１値が第３値より小なる場合には第２値を第２の次最小値候補とする一方、第１値が第３値より大なる場合には第４値を第２の次最小値候補とし、第１の次最小値候補及び第２の次最小値候補の内で小なる方を第１〜第４のデータ値における最小値の次に小なる次最小値としている。
【００１２】
かかる最小値検出処理によれば、データ値各々の内から最小値を検出し、この最小値に対応したデータ値をマスクした状態で再びデータ値各々の内から最小値を検出し、これを次最小値とする従来の最小値検出回路に比して、高速に複数のデータ値の内から最小値及び次最小値を検出することが可能となる。
【図面の簡単な説明】
【００１３】
【図１】本発明による最小値検出回路の構成の一例を示すブロック図である。
【図２】コンパレータセレクタの内部構成を示すブロック図である。
【図３】最小値次最小値判定部の内部構成を示すブロック図である。
【図４】最小値検出回路の構成の他の一例を示すブロック図である。
【図５】図４に示す最小値検出回路の変形例を示す図である。
【発明を実施するための形態】
【００１４】
本発明においては、第１のデータ値と第２のデータ値とを大小比較して小なる方を第１値、大なる方を第２値とすると共に、データ値各々の内の第３のデータ値と第４のデータ値とを大小比較して小なる方を第３値、大なる方を第４値とする。この際、上記第１値及び第３値の内で小なる方を第１〜第４のデータ値における最小値とする。また、上記第１値及び第３値の内の大なる方を第１の次最小値候補とし、この第１値が第３値より小なる場合には第２値を第２の次最小値候補とする一方、第１値が第３値より大なる場合には第４値を第２の次最小値候補とする。この際、第１の次最小値候補及び第２の次最小値候補の内で小なる方を第１〜第４のデータ値における次最小値とする。
【実施例】
【００１５】
図１は、本発明による最小値検出回路の基本となる構成を示すブロック図である。
【００１６】
図１において、コンパレータセレクタ１１及び１２は共に図２に示す如き内部構成を有する。
【００１７】
図２において、比較器１０１は、入力端子ａに供給されたデータの値と、入力端子ｂに供給されたデータの値との大小比較を行い、その大小比較結果に応じた比較結果信号ＣＭ１をセレクタ１０２に供給する。セレクタ１０２は、入力端子ａ及びｂの内で入力端子ａに供給されたデータ値の方が小であることを示す比較結果信号ＣＭ１が供給された場合には、入力端子ａに供給されたデータ値を暫定最小値Ｍ１として出力すると共に、入力端子ｂに供給されたデータ値を暫定次最小値Ｍ２として出力する。一方、入力端子ａ及びｂの内で入力端子ｂに供給されたデータ値の方が小であることを示す比較結果信号ＣＭ１が供給された場合には、セレクタ１０２は、入力端子ｂに供給されたデータ値を暫定最小値Ｍ１として出力すると共に、入力端子ａに供給されたデータ値を暫定次最小値Ｍ２として出力する。尚、セレクタ１０２は、入力端子ａ及びｂに夫々供給されたデータ値が同一値である場合には、その値を暫定最小値Ｍ１及び暫定次最小値Ｍ２として出力する。
【００１８】
かかる構成により、コンパレータセレクタ１１は、データ値Ｘ０及びＸ１の内で小なる方を暫定最小値Ｍ１Ａとして最小値・次最小値判定部２１の入力端子Ａ１に供給すると共に、データ値Ｘ０及びＸ１の内で大なる方を暫定次最小値Ｍ２Ａとして最小値・次最小値判定部２１の入力端子Ａ２に供給する。
【００１９】
コンパレータセレクタ１２は、データ値Ｘ２及びＸ３の内で小なる方を暫定最小値Ｍ１Ｂとして最小値・次最小値判定部２１の入力端子Ｂ１に供給すると共に、データ値Ｘ３及びＸ３の内で大なる方を暫定次最小値Ｍ２Ｂとして最小値・次最小値判定部２１の入力端子Ｂ２に供給する。
【００２０】
最小値・次最小値判定部２１は、図３に示す如き内部構成を有する。
【００２１】
図３において、比較器２０１は、入力端子Ａ１に供給されたデータ値と、入力端子Ｂ１に供給されたデータ値との大小比較を行い、その大小比較結果に応じた比較結果信号ＣＭ２をセレクタ２０３〜２０５の各々に供給する。セレクタ２０３は、かかる比較結果信号ＣＭ２が、入力端子Ａ１に供給されたデータ値の方が入力端子Ｂ１に供給されたデータ値より小であることを示す場合には、入力端子Ａ１に供給されたデータ値を、４個のデータ値Ｘ０〜Ｘ４の中で最も小なる値を暫定的に示す暫定最小値Ｍ１として出力する。一方、この比較結果信号ＣＭ２が、入力端子Ａ１に供給されたデータ値よりも入力端子Ｂ１に供給されたデータ値の方が小である又は両者が同一であることを示す場合には、セレクタ２０３は、入力端子Ｂ１に供給されたデータ値を上記暫定最小値Ｍ１として出力する。
【００２２】
すなわち、セレクタ２０３は、入力端子Ａ１に供給されたデータ値及び入力端子Ｂ１に供給されたデータ値の内で小なる方を、上記データ値Ｘ０〜Ｘ３の内で最も小なる値を示す最小値Ｍ１として出力するのである。
【００２３】
セレクタ２０４は、比較結果信号ＣＭ２が、入力端子Ａ１に供給されたデータ値が入力端子Ｂ１に供給されたデータ値以上であることを示す場合には、入力端子Ａ１に供給されたデータ値を次最小値候補Ｍ２ａとして比較器２０２及びセレクタ２０６の各々に供給する。一方、この比較結果信号ＣＭ２が、入力端子Ａ１に供給されたデータ値よりも入力端子Ｂ１に供給されたデータ値の方が大であることを示す場合には、セレクタ２０４は、入力端子Ｂ１に供給されたデータ値を次最小値候補Ｍ２ａとして比較器２０２及びセレクタ２０６の各々に供給する。
【００２４】
すなわち、セレクタ２０４は、入力端子Ａ１に供給されたデータ値及び入力端子Ｂ１に供給されたデータ値各々の内で大なる方を上記次最小値候補Ｍ２ａとして比較器２０２及びセレクタ２０６の各々に供給するのである。
【００２５】
セレクタ２０５は、上記比較結果信号ＣＭ２が、入力端子Ｂ１に供給されたデータ値が入力端子Ａ１に供給されたデータ値以下であることを示す場合には、入力端子Ｂ２に供給されたデータ値を次最小値候補Ｍ２ｂとして比較器２０２及びセレクタ２０６の各々に供給する。一方、この比較結果信号ＣＭ２が、入力端子Ｂ１に供給されたデータ値が入力端子Ａ１に供給されたデータ値よりも大であることを示す場合には、セレクタ２０５は、入力端子Ａ２に供給されたデータ値を次最小値候補Ｍ２ｂとして比較器２０２及びセレクタ２０６の各々に供給する。
【００２６】
比較器２０２は、次最小値候補Ｍ２ａと、次最小値候補Ｍ２ｂとの大小比較を行い、その大小比較結果を示す比較結果信号ＣＭ３をセレクタ２０６に供給する。
【００２７】
セレクタ２０６は、かかる比較結果信号ＣＭ３が、次最小値候補Ｍ２ａよりも次最小値候補Ｍ２ｂが小であることを示す場合には、次最小値候補Ｍ２ａ及びＭ２ｂの内から次最小値候補Ｍ２ｂを選択しこれを暫定次最小値Ｍ２として出力する。一方、比較結果信号ＣＭ３が、次最小値候補Ｍ２ｂよりも次最小値候補Ｍ２ａが小であることを示す場合には、セレクタ２０６は、次最小値候補Ｍ２ａ及びＭ２ｂの内から次最小値候補Ｍ２ａを選択しこれを暫定次最小値Ｍ２として出力する。
【００２８】
すなわち、セレクタ２０６は、次最小値候補Ｍ２ａ及び次最小値候補Ｍ２ｂの内で小なる方を、上記データ値Ｘ０〜Ｘ３の内で第２番目に小なる値を暫定的に示す暫定次最小値Ｍ２として出力するのである。
【００２９】
このように、最小値・次最小値判定部２１では、その入力端子Ａ１、Ａ２、Ｂ１及びＢ２に供給されたデータ値の大小関係に基づき、以下の如く、暫定最小値Ｍ１、次最小値候補Ｍ２ａ及びＭ２ｂ、暫定次最小値Ｍ２の各々を検出する。
【００３０】
Ｍ１ ：Ａ１及びＢ１の内の小なる方
Ｍ２ａ：Ａ１及びＢ１の内の大なる方
Ｍ２ｂ：Ａ１＜Ｂ１の場合にはＡ２、Ａ１＞Ｂ１の場合にはＢ２
Ｍ２：Ｍ２ａ及びＭ２ｂの内の小なる方
【００３１】
ここで、図１に示すように、最小値・次最小値判定部２１の入力端子Ａ１、Ａ２、Ｂ１及びＢ２の各々には、コンパレータセレクタ１１から供給された暫定最小値Ｍ１Ａ及び暫定次最小値Ｍ２Ａ、コンパレータセレクタ１２から供給された暫定最小値Ｍ１Ｂ及び暫定次最小値Ｍ２Ｂの各々が、以下の如く供給される。
【００３２】
Ａ１：暫定最小値Ｍ１Ａ
Ａ２：暫定次最小値Ｍ２Ａ
Ｂ１：暫定最小値Ｍ１Ｂ
Ｂ２：暫定次最小値Ｍ２Ｂ
【００３３】
この際、暫定最小値Ｍ１Ａはデータ値Ｘ０及びＸ１の内の小なる方の値であり、暫定次最小値Ｍ２Ａはデータ値Ｘ０及びＸ１の内の大なる方の値である。また、暫定最小値Ｍ１Ｂはデータ値Ｘ２及びＸ３の内の小なる方の値であり、暫定次最小値Ｍ２Ｂはデータ値Ｘ２及びＸ３の内の大なる方の値である。
【００３４】
よって、最小値・次最小値判定部２１は、データ値Ｘ０〜Ｘ３の内で最も小なる値を暫定的に示す暫定最小値Ｍ１をそのまま最小値として出力すると共に、データ値Ｘ０〜Ｘ３の内で第２番目に小なる値を示す暫定次最小値Ｍ２をそのまま次最小値として出力する。
【００３５】
以上の如く、図１に示す最小値検出回路においては、先ず、第１比較部（１１）により、複数のデータ値各々の内の第１及び第２のデータ値（Ｘ０、Ｘ１）同士を大小比較して、小なる方を第１値（Ｍ１Ａ）、大なる方を第２値（Ｍ２Ａ）とする。更に、第２比較部（１２）により、第３及び第４のデータ値（Ｘ２、Ｘ３）同士を大小比較して、小なる方を第１値（Ｍ１Ｂ）、大なる方を第２値（Ｍ２Ｂ）とする。次に、最小値・次最小値判定部（２１）により、上記第１値及び第３値の内で小なる方を第１〜第４のデータ値における最小値とする。また、この最小値・次最小値判定部（２１）により、上記第１値及び第３値の内の大なる方を第１の次最小値候補（Ｍ２ａ）とし、この第１値が第３値より小なる場合には第２値を第２の次最小値候補（Ｍ２ｂ）とする一方、第１値が第３値より大なる場合には第４値を第２の次最小値候補（Ｍ２ｂ）とする。この際、最小値・次最小値判定部（２１）では、第１の次最小値候補（Ｍ２ａ）及び第２の次最小値候補（Ｍ２ｂ）の内で小なる方を第１〜第４のデータ値における次最小値としている。
【００３６】
ここで、図１に示す最小値検出回路における各コンパレータセレクタは、図２に示す如く１段分の２入力比較器（１０１）と、１段分の２入力セレクタ（１０２）とからなる。また、最小値・次最小値判定部は、図３に示す如く２段分の２入力比較器（２０１、２０２）と、２段分の２入力セレクタ（２０３〜２０６）とからなる。この際、２入力比較器（１０１、２０１、２０２）単独で費やされる処理時間をＴＣ、２入力セレクタ（１０２、２０３〜２０６）単独で費やされる処理時間をＴＳとすると、コンパレータセレクタ１１、１２では処理時間（ＴＣ＋ＴＳ）、最小値・次最小値判定部２１では処理時間（２ＴＣ＋２ＴＳ）が費やされる。つまり、図１に示す最小値検出回路では、入力された４個のデータ値Ｘ０〜Ｘ３に対して、処理時間（３ＴＣ＋３ＴＳ）を費やすことにより最小値及び次最小値が得られるのである。
【００３７】
これに対して、従来の最小値検出回路では、先ず、データ値Ｘ０〜Ｘ３から最小値を検出し、この最小値に対応したデータ値Ｘをマスクした状態で再びデータ値Ｘ０〜Ｘ３中から最小値を検出し、これを次最小値としている。つまり、従来の最小値検出回路では、データ値Ｘ０〜Ｘ３中から最小値を検出する際の処理時間（２ＴＣ＋２ＴＳ）と、最小値に対応したデータ値Ｘをマスクする際に費やされる処理時間ＴＭと、データ値Ｘをマスクした状態で再びデータ値Ｘ０〜Ｘ３中から最小値を検出する際の処理時間（２ＴＣ＋２ＴＳ）との合計時間（４ＴＣ＋４ＴＳ＋ＴＭ）を経て最小値及び次最小値が求まる。
【００３８】
よって、図１に示す最小値検出回路によれば、従来のものに比して高速に４つのデータ値Ｘ０〜Ｘ３の内から最小値及び次最小値を検出することが可能となる。
【００３９】
尚、図１に示す最小値検出回路では、４つのデータ値Ｘ０〜Ｘ３の内から最小値及び次最小値を検出するものであるが、これを複数個組み合わせることにより、４・２ｎ−１（ｎは自然数）個のデータ値の中から最小値及び次最小値を検出する最小値検出回路を構築することも可能である。
【００４０】
図４は、１６個のデータ値Ｘ０〜Ｘ１５の内から最小値及び次最小値の検出を行う最小値検出回路の構成を示すブロック図である。
【００４１】
図４において、コンパレータセレクタ１１〜１８の各々は同一の内部構成、つまり夫々が図２に示す内部構成を有する。又、最小値・次最小値判定部２１〜２７の各々は同一の内部構成、つまり夫々が図３に示す如き内部構成を有する。
【００４２】
コンパレータセレクタ１１は、データ値Ｘ０及びＸ１の内で小なる方を暫定最小値Ｍ１Ａとして最小値・次最小値判定部２１の入力端子Ａ１に供給すると共に、データ値Ｘ０及びＸ１の内で大なる方を暫定次最小値Ｍ２Ａとして最小値・次最小値判定部２１の入力端子Ａ２に供給する。コンパレータセレクタ１２は、データ値Ｘ２及びＸ３の内で小なる方を暫定最小値Ｍ１Ｂとして最小値・次最小値判定部２１の入力端子Ｂ１に供給すると共に、データ値Ｘ２及びＸ３の内で大なる方を暫定次最小値Ｍ２Ｂとして最小値・次最小値判定部２１の入力端子Ｂ２に供給する。コンパレータセレクタ１３は、データ値Ｘ４及びＸ５の内で小なる方を暫定最小値Ｍ１Ｃとして最小値・次最小値判定部２２の入力端子Ａ１に供給すると共に、データ値Ｘ４及びＸ５の内で大なる方を暫定次最小値Ｍ２Ｃとして最小値・次最小値判定部２２の入力端子Ａ２に供給する。コンパレータセレクタ１４は、データ値Ｘ６及びＸ７の内で小なる方を暫定最小値Ｍ１Ｄとして最小値・次最小値判定部２２の入力端子Ｂ１に供給すると共に、データ値Ｘ６及びＸ７７の内で大なる方を暫定次最小値Ｍ２Ｄとして最小値・次最小値判定部２２の入力端子Ｂ２に供給する。コンパレータセレクタ１５は、データ値Ｘ８及びＸ９の内で小なる方を暫定最小値Ｍ１Ｅとして最小値・次最小値判定部２３の入力端子Ａ１に供給すると共に、データ値Ｘ８及びＸ９の内で大なる方を暫定次最小値Ｍ２Ｅとして最小値・次最小値判定部２３の入力端子Ａ２に供給する。コンパレータセレクタ１６は、データ値Ｘ１０及びＸ１１の内で小なる方を暫定最小値Ｍ１Ｆとして最小値・次最小値判定部２３の入力端子Ｂ１に供給すると共に、データ値Ｘ１０及びＸ１１の内で大なる方を暫定次最小値Ｍ２Ｆとして最小値・次最小値判定部２３の入力端子Ｂ２に供給する。コンパレータセレクタ１７は、データ値Ｘ１２及びＸ１３の内で小なる方を暫定最小値Ｍ１Ｇとして最小値・次最小値判定部２４の入力端子Ａ１に供給すると共に、データ値Ｘ１２及びＸ１３の内で大なる方を暫定次最小値Ｍ２Ｇとして最小値・次最小値判定部２４の入力端子Ａ２に供給する。コンパレータセレクタ１８は、データ値Ｘ１４及びＸ１５の内で小なる方を暫定最小値Ｍ１Ｈとして最小値・次最小値判定部２４の入力端子Ｂ１に供給すると共に、データ値Ｘ１４及びＸ１５の内で大なる方を暫定次最小値Ｍ２Ｈとして最小値・次最小値判定部２４の入力端子Ｂ２に供給する。
【００４３】
最小値・次最小値判定部２１〜２７の各々は、その入力端子Ａ１、Ａ２、Ｂ１及びＢ２に供給されたデータ値の大小関係に基づき、以下の如く、暫定最小値Ｍ１、次最小値候補Ｍ２ａ及びＭ２ｂ、暫定次最小値Ｍ２を求める。
【００４４】
Ｍ１ ：Ａ１及びＢ１の内の小なる方
Ｍ２ａ：Ａ１及びＢ１の内の大なる方
Ｍ２ｂ：Ａ１＜Ｂ１の場合にはＡ２、Ａ１＞Ｂ１の場合にはＢ２
Ｍ２：Ｍ２ａ及びＭ２ｂの内の小なる方
【００４５】
図４に示すように、最小値・次最小値判定部２１の入力端子Ａ１、Ａ２、Ｂ１及びＢ２の各々には、コンパレータセレクタ１１から供給された暫定最小値Ｍ１Ａ及び暫定次最小値Ｍ２Ａ、コンパレータセレクタ１２から供給された暫定最小値Ｍ１Ｂ及び暫定次最小値Ｍ２Ｂの各々が、以下の如く供給される。
【００４６】
Ａ１：暫定最小値Ｍ１Ａ
Ａ２：暫定次最小値Ｍ２Ａ
Ｂ１：暫定最小値Ｍ１Ｂ
Ｂ２：暫定次最小値Ｍ２Ｂ
【００４７】
この際、暫定最小値Ｍ１Ａはデータ値Ｘ０及びＸ１の内の小なる方の値であり、暫定次最小値Ｍ２Ａはデータ値Ｘ０及びＸ１の内の大なる方の値である。また、暫定最小値Ｍ１Ｂはデータ値Ｘ２及びＸ３の内の小なる方の値であり、暫定次最小値Ｍ２Ｂはデータ値Ｘ２及びＸ３の内の大なる方の値である。
【００４８】
よって、最小値・次最小値判定部２１は、データ値Ｘ０〜Ｘ３の内で最も小なる値を暫定最小値Ｍ１Ｊ、第２番目に小なる値を暫定次最小値Ｍ２Ｊとして、夫々を最小値・次最小値判定部２５の入力端子Ａ１及びＡ２に供給する。
【００４９】
また、図４に示されるように、最小値・次最小値判定部２２の入力端子Ａ１、Ａ２、Ｂ１及びＢ２の各々には、コンパレータセレクタ１３から供給された暫定最小値Ｍ１Ｃ及び暫定次最小値Ｍ２Ｃ、コンパレータセレクタ１４から供給された暫定最小値Ｍ１Ｄ及び暫定次最小値Ｍ２Ｄの各々が、以下の如く供給される。
【００５０】
Ａ１：暫定最小値Ｍ１Ｃ
Ａ２：暫定次最小値Ｍ２Ｃ
Ｂ１：暫定最小値Ｍ１Ｄ
Ｂ２：暫定次最小値Ｍ２Ｄ
【００５１】
この際、暫定最小値Ｍ１Ｃはデータ値Ｘ４及びＸ５の内の小なる方の値であり、暫定次最小値Ｍ２Ｃはデータ値Ｘ４及びＸ５の内の大なる方の値である。また、暫定最小値Ｍ１Ｄはデータ値Ｘ６及びＸ７の内の小なる方の値であり、暫定次最小値Ｍ２Ｄはデータ値Ｘ６及びＸ７の内の大なる方の値である。
【００５２】
よって、最小値・次最小値判定部２２は、データ値Ｘ４〜Ｘ７の内で最も小なる値を暫定最小値Ｍ１Ｋ、第２番目に小なる値を暫定次最小値Ｍ２Ｋとして、夫々を最小値・次最小値判定部２５の入力端子Ｂ１及びＢ２に供給する。
【００５３】
また、図４に示されるように、最小値・次最小値判定部２３の入力端子Ａ１、Ａ２、Ｂ１及びＢ２の各々には、コンパレータセレクタ１５から供給された暫定最小値Ｍ１Ｅ及び暫定次最小値Ｍ２Ｅ、コンパレータセレクタ１６から供給された暫定最小値Ｍ１Ｆ及び暫定次最小値Ｍ２Ｆの各々が、以下の如く供給される。
【００５４】
Ａ１：暫定最小値Ｍ１Ｅ
Ａ２：暫定次最小値Ｍ２Ｅ
Ｂ１：暫定最小値Ｍ１Ｆ
Ｂ２：暫定次最小値Ｍ２Ｆ
【００５５】
この際、暫定最小値Ｍ１Ｅはデータ値Ｘ８及びＸ９の内の小なる方の値であり、暫定次最小値Ｍ２Ｅはデータ値Ｘ８及びＸ９の内の大なる方の値である。また、暫定最小値Ｍ１Ｆはデータ値Ｘ１０及びＸ１１の内の小なる方の値であり、暫定次最小値Ｍ２Ｆはデータ値Ｘ１０及びＸ１１の内の大なる方の値である。
【００５６】
よって、最小値・次最小値判定部２３は、データ値Ｘ８〜Ｘ１１の内で最も小なる値を暫定最小値Ｍ１Ｌ、第２番目に小なる値を暫定次最小値Ｍ２Ｌとして、夫々を最小値・次最小値判定部２６の入力端子Ａ１及びＡ２に供給する。
【００５７】
また、図４に示されるように、最小値・次最小値判定部２４の入力端子Ａ１、Ａ２、Ｂ１及びＢ２の各々には、コンパレータセレクタ１７から供給された暫定最小値Ｍ１Ｇ及び暫定次最小値Ｍ２Ｇ、コンパレータセレクタ１８から供給された暫定最小値Ｍ１Ｈ及び暫定次最小値Ｍ２Ｈの各々が、以下の如く供給される。
【００５８】
Ａ１：暫定最小値Ｍ１Ｇ
Ａ２：暫定次最小値Ｍ２Ｇ
Ｂ１：暫定最小値Ｍ１Ｈ
Ｂ２：暫定次最小値Ｍ２Ｈ
【００５９】
この際、暫定最小値Ｍ１Ｇはデータ値Ｘ１２及びＸ１３の内の小なる方の値であり、暫定次最小値Ｍ２Ｇはデータ値Ｘ１２及びＸ１３の内の大なる方の値である。また、暫定最小値Ｍ１Ｈはデータ値Ｘ１４及びＸ１５の内の小なる方の値であり、暫定次最小値Ｍ２Ｈはデータ値Ｘ１４及びＸ１５の内の大なる方の値である。
【００６０】
よって、最小値・次最小値判定部２４は、データ値Ｘ１２〜Ｘ１５の内で最も小なる値を暫定最小値Ｍ１Ｍ、第２番目に小なる値を暫定次最小値Ｍ２Ｍとして、夫々を最小値・次最小値判定部２６の入力端子Ｂ１及びＢ２に供給する。
【００６１】
最小値・次最小値判定部２５の入力端子Ａ１、Ａ２、Ｂ１及びＢ２の各々には、最小値・次最小値判定部２１から供給された暫定最小値Ｍ１Ｊ及び暫定次最小値Ｍ２Ｊ、最小値・次最小値判定部２２から供給された暫定最小値Ｍ１Ｋ及び暫定次最小値Ｍ２Ｋの各々が、以下の如く供給される。
【００６２】
Ａ１：暫定最小値Ｍ１Ｊ
Ａ２：暫定次最小値Ｍ２Ｊ
Ｂ１：暫定最小値Ｍ１Ｋ
Ｂ２：暫定次最小値Ｍ２Ｋ
【００６３】
この際、暫定最小値Ｍ１Ｊは、データ値Ｘ０〜Ｘ３の内で最も小なる値であり、暫定次最小値Ｍ２Ｊはデータ値Ｘ０〜Ｘ３の内で第２番目に小なる値である。また、暫定最小値Ｍ１Ｋは、データ値Ｘ４〜Ｘ７の内で最も小なる値であり、暫定次最小値Ｍ２Ｈはデータ値Ｘ４〜Ｘ７の内で第２番目に小なる値である。
【００６４】
よって、最小値・次最小値判定部２５は、データ値Ｘ０〜Ｘ７の内で最も小なる値を暫定最小値Ｍ１Ｎ、第２番目に小なる値を暫定次最小値Ｍ２Ｎとして、夫々を最小値・次最小値判定部２７の入力端子Ａ１及びＡ２に供給する。
【００６５】
最小値・次最小値判定部２６の入力端子Ａ１、Ａ２、Ｂ１及びＢ２の各々には、最小値・次最小値判定部２３から供給された暫定最小値Ｍ１Ｌ及び暫定次最小値Ｍ２Ｌ、最小値・次最小値判定部２４から供給された暫定最小値Ｍ１Ｍ及び暫定次最小値Ｍ２Ｍの各々が、以下の如く供給される。
【００６６】
Ａ１：暫定最小値Ｍ１Ｌ
Ａ２：暫定次最小値Ｍ２Ｌ
Ｂ１：暫定最小値Ｍ１Ｍ
Ｂ２：暫定次最小値Ｍ２Ｍ
【００６７】
この際、暫定最小値Ｍ１Ｌは、データ値Ｘ８〜Ｘ１１の内で最も小なる値であり、暫定次最小値Ｍ２Ｌはデータ値Ｘ８〜Ｘ１１の内で第２番目に小なる値である。また、暫定最小値Ｍ１Ｍは、データ値Ｘ１２〜Ｘ１５の内で最も小なる値であり、暫定次最小値Ｍ２Ｍはデータ値Ｘ１２〜Ｘ１５の内で第２番目に小なる値である。
【００６８】
よって、最小値・次最小値判定部２６は、データ値Ｘ８〜Ｘ１５の内で最も小なる値を暫定最小値Ｍ１Ｎ、第２番目に小なる値を暫定次最小値Ｍ２Ｎとして、夫々を最小値・次最小値判定部２７の入力端子Ｂ１及びＢ２に供給する。
【００６９】
最小値・次最小値判定部２７の入力端子Ａ１、Ａ２、Ｂ１及びＢ２の各々には、最小値・次最小値判定部２５から供給された暫定最小値Ｍ１Ｎ及び暫定次最小値Ｍ２Ｎ、最小値・次最小値判定部２６から供給された暫定最小値Ｍ１Ｐ及び暫定次最小値Ｍ２Ｐの各々が、以下の如く供給される。
【００７０】
Ａ１：暫定最小値Ｍ１Ｎ
Ａ２：暫定次最小値Ｍ２Ｎ
Ｂ１：暫定最小値Ｍ１Ｐ
Ｂ２：暫定次最小値Ｍ２Ｐ
【００７１】
この際、暫定最小値Ｍ１Ｎは、データ値Ｘ０〜Ｘ７の内で最も小なる値であり、暫定次最小値Ｍ２Ｎはデータ値Ｘ０〜Ｘ７の内で第２番目に小なる値である。また、暫定最小値Ｍ１Ｐは、データ値Ｘ８〜Ｘ１５の内で最も小なる値であり、暫定次最小値Ｍ２Ｐはデータ値Ｘ８〜Ｘ１５の内で第２番目に小なる値である。
【００７２】
その結果、最小値・次最小値判定部２７は、データ値Ｘ０〜Ｘ１５の内で最も小なる値を示す暫定最小値Ｍ１を最終的な最小値として出力すると共に、データ値Ｘ０〜Ｘ１５の内で第２番目に小なる値を示す暫定次最小値Ｍ２を最終的な次最小値として出力する。
【００７３】
ここで、図４に示す最小値検出回路において、コンパレータセレクタ１１〜１８では処理時間（ＴＣ＋ＴＳ）、最小値・次最小値判定部２１〜２４では処理時間（２ＴＣ＋２ＴＳ）、最小値・次最小値判定部２５及び２６では処理時間（２ＴＣ＋２ＴＳ）、最小値・次最小値判定部２７では処理時間（２ＴＣ＋２ＴＳ）が費やされる。よって、図４に示す最小値検出回路では、入力された１６個のデータ値Ｘ０〜Ｘ１５に対して、処理時間（７ＴＣ＋７ＴＳ）を費やすことにより最小値及び次最小値が得られるのである。
【００７４】
これに対して、従来の最小値検出回路では、先ず、データ値Ｘ０〜Ｘ１５から最小値を検出し、この最小値に対応したデータ値Ｘをマスクした状態で再びデータ値Ｘ０〜Ｘ１５中から最小値を検出し、これを次最小値としている。つまり、従来の最小値検出回路では、データ値Ｘ０〜Ｘ１５中から最小値を検出する際の処理時間（４ＴＣ＋４ＴＳ）と、最小値に対応したデータ値Ｘをマスクする際に費やされる処理時間ＴＭと、データ値Ｘをマスクした状態で再びデータ値Ｘ０〜Ｘ１５中から最小値を検出する際の処理時間（４ＴＣ＋４ＴＳ）との合計時間（８ＴＣ＋８ＴＳ＋ＴＭ）を経て最小値及び次最小値が求まる。
【００７５】
よって、図４に示す最小値検出回路によれば、従来のものに比して高速に１６個のデータ値Ｘ０〜Ｘ１５の内から最小値及び次最小値を検出することが可能となる。
【００７６】
従って、図１又は図４に示す最小値検出回路を、Ｍｉｎ−Ｓｕｍアルゴリズムを採用したＬＤＰＣ復号器に搭載することにより、復号処理の高速化を図ることが可能となる。
【００７７】
すなわち、Ｍｉｎ−Ｓｕｍアルゴリズムを採用したＬＤＰＣ復号器では、受信シンボルにノイズ情報を考慮した対数尤度比及び事前値対数比を用いたギャラガー関数に従って外部値対数比を更新しつつ、パリティ検査を行なう。この際、かかるＬＤＰＣ復号器では、外部値対数比をギャラガー関数にて表される複数の変数値中における最小値及び次最小値で近似する。つまり、ギャラガー関数にて表される複数の変数値中から最小値及び次最小値を検出べく、図１又は図４に示す如き最小値検出回路が用いられる。例えば、ギャラガー関数にて表される複数の変数値の数が１６個である場合には、図４に示す構造を有する最小値検出回路によって検出された最小値及び次最小値に基づき、外部値対数比が求まるのである。尚、ギャラガー関数にて表される複数の変数値の数が９〜１５個である場合には、図４に示す構造を有する最小値検出回路を採用し、入力空き状態となるコンパレータセレクタの入力端子ａ又はｂには、変数値の内の１つを共通に供給する。例えば、ギャラガー関数にて表される複数の変数値の数が１２個である場合には、図５に示すように、各変数値に対応したデータ値Ｘ０〜Ｘ１１を夫々コンパレータセレクタ１１〜１６各々の入力端子ａ及びｂに供給し、残りのコンパレータセレクタ１７及び１８各々の入力端子ａ及びｂに、データ値Ｘ１１を共通に供給する。
【００７８】
尚、上記実施例においては、最小値及び次最小値の検出処理を図１〜図５に示す如きハードウェアで実現する際の動作を説明したが、図１〜図５に示される動作をソフトウェアにて実現するようにしても良い。ただし、図１〜図５に示されるが如きハードウェアで実現することにより、ソフトウェア構築した場合に比して高速な処理が為されるようになる。
【符号の説明】
【００７９】
１１〜１８                コンパレータセレクタ
２１〜２７                最小値・次最小値判定部
１０１、２０１、２０２    比較器
１０２、２０３〜２０６    セレクタ
【図１】
2012209632.tif 000003
【図２】
2012209632.tif 000004
【図３】
2012209632.tif 000005
【図４】
2012209632.tif 000006
【図５】
2012209632.tif 000007