(57)【要約】【課題】入力された信号の中から最小または最大である第１順位を短時間で推定することができる第１順位推定装置およびこれを用いた復号装置を提供する。【解決手段】第１変換部３２は、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する。ビット論理演算部３４は、複数個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成する。第２変換部３６は、第２の変換規則に基づいて、論理演算信号を変換して、複数個の入力信号のうちの第１順位の信号の値を表わす第２変換信号を生成する。【選択図】図１
2007335992.tif 000002
【特許請求の範囲】
【請求項１】
複数個の入力信号のうち、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定装置であって、
第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、
前記複数個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、
第２の変換規則に基づいて、前記論理演算信号を変換して、前記複数個の入力信号のうちの第１順位の信号の値を表わす第２変換信号を生成する第２変換部とを備え、
前記第１の変換規則では、前記入力信号の１個が前記第１変換信号の１個に対応し、
前記第２の変換規則では、前記論理演算信号の１個が前記第２変換信号の１個に対応し、
前記第２の変換規則において前記論理演算信号に対応する前記第２変換信号の値は、前記第１の変換規則において前記論理演算信号と同一の値の前記第１変換信号に対応する前記入力信号の値と同一である、第１順位推定装置。
【請求項２】
前記第１の変換規則では、前記入力信号の取り得る値の範囲は０からＮまでであり、かつ前記第１変換信号の取り得る値はＮビットで表わされ、
前記第１の変換規則では、前記入力信号の値がｋ（０≦ｋ≦Ｎ）のときに、前記第１変換信号の下位のｋ個のビットの値が第１の論理値であり、かつその他のビットの値が第２の論理値であるように変換され、
前記ビット論理演算部は、前記ビット単位の論理演算として、各ビットにつき、前記複数個の第１変換信号の前記ビットの値がすべて前記第１の論理値のときには前記第１の論理値を出力し、それ以外のときには前記第２の論理値を出力する論理演算を行なう、請求項１記載の第１順位推定装置。
【請求項３】
前記第１の変換規則では、前記入力信号の取り得る値は大きい順または小さい順に順序づけられる第１番目から第Ｎ番目までのＮ種類であり、かつ前記第１変換信号の取り得る値はＭビット（Ｍ≧（Ｎ−１））で表わされ、
前記第１の変換規則では、前記取り得る値のうちの第Ｋ番目の入力信号に対応する前記第１変換信号のビットのうち、値が第１の論理値であるビットが存在する場合に、
前記取り得る値のうちの第（Ｋ＋１）番目の入力信号に対応する前記第１変換信号については、値が第１の論理値であるビットの位置は、前記第Ｋ番目の入力信号に対応する第１変換信号のビットのうちの値が第１の論理値であるビットの位置と、さらに少なくとも１つのビットの位置とからなり、
前記ビット論理演算部は、前記ビット単位の論理演算として、各ビットにつき、前記複数個の第１変換信号の前記ビットの値がすべて前記第１の論理値のときには前記第１の論理値を出力し、それ以外のときには前記第２の論理値を出力する論理演算を行なう、
ただし、Ｋは、１以上かつ（Ｎ−１）以下のすべての自然数である、請求項１記載の第１順位推定装置。
【請求項４】
複数個の入力信号のうち、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定装置であって、
第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、
前記複数個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、
第２の変換規則に基づいて、前記論理演算信号を変換して、前記複数個の入力信号のうちの第１順位の信号の値または前記第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを備え、
前記第１の変換規則では、前記入力信号の１個または複数個が前記第１変換信号の１個に対応し、
前記第２の変換規則では、前記論理信号の１個が前記第２変換信号の１個に対応し、
前記第２の変換規則において前記論理演算信号に対応する前記第２変換信号の値は、前記第１の変換規則において前記論理演算信号と同一の値の前記第１変換信号に対応する前記入力信号が１個のときには、前記１個の入力信号の値と同一であり、前記論理演算信号と同一の値の前記第１変換信号に対応する前記入力信号が複数個のときには、前記複数個の入力信号のうちの１つの値と同一である、第１順位推定装置。
【請求項５】
前記第１の変換規則では、前記入力信号の取り得る値はＮビットで表わされ、かつ前記第１変換信号の取り得る値はＮビットで表わされ、
前記第１の変換規則では、前記入力信号のビットのうち、値が１である最も上位ビットが最下位ビットからｋ番目（１≦ｋ≦Ｎ）のビットのときに、前記第１変換信号の下位のｋ個のビットの値が第１の論理値であり、かつその他のビットの値が第２の論理値であるように変換され、前記入力信号のビットのうち、すべてのビットの値が０のときには、前記第１変換信号のすべてのビットの値が第２の論理値であるように変換され、
前記ビット論理演算部は、前記ビット単位の論理演算として、各ビットにつき、前記複数個の第１変換信号の前記ビットの値がすべて前記第１の論理値のときには前記第１の論理値を出力し、それ以外のときには前記第２の論理値を出力する論理演算を行なう、請求項４記載の第１順位推定装置。
【請求項６】
前記第２の変換規則では、前記論理演算信号の取り得る値はＮビットで表わされ、かつ前記第２変換信号の取り得る値はＮビットで表わされ、
前記第２の変換規則では、前記論理演算信号のビットのうち、値が第１の論理値である最も上位ビットが最下位ビットからｋ番目（１≦ｋ≦Ｎ）のビットのときに、前記第２変換信号の最下位ビットからｋ番目のビットの値が１であり、かつその他のビットの値が０であるように変換され、前記論理演算信号のビットのうち、すべてのビットの値が第２の論理値のときには、前記第２変換信号のすべてのビットの値が０であるように変換される、請求項４記載の第１順位推定装置。
【請求項７】
前記第１の変換規則では、前記入力信号の取り得る値は大きい順または小さい順に順序づけられる第１番目から第Ｎ番目までのＮ種類であり、前記第１変換信号の取り得る値は第１番目から第Ｍ番目までのＭ種類（Ｍ＜Ｎ）であり、
順番が小さい前記第１変換信号ほど、順番が小さい前記入力信号に対応し、
第（Ｋ＋１）番目の前記第１変換信号に対応する前記入力信号の個数は、第Ｋ番目の前記第１変換信号に対応する前記入力信号の個数以上であり、
前記第１の変換規則では、第Ｋ番目の前記第１変換信号のビットのうち、値が第１の論理値であるビットが存在する場合に、第（Ｋ＋１）番目の第１変換信号については、値が第１の論理値であるビットの位置は、前記第Ｋ番目の第１変換信号のビットのうちの値が第１の論理値であるビットの位置と、さらに少なくとも１つのビットの位置とからなり、
前記ビット論理演算部は、前記ビット単位の論理演算として、各ビットにつき、前記複数個の第１変換信号の前記ビットの値がすべて前記第１の論理値のときには前記第１の論理値を出力し、それ以外のときには前記第２の論理値を出力する論理演算を行なう、
ただし、Ｋは、１以上かつ（Ｍ−１）以下のすべての自然数である、請求項４記載の第１順位推定装置。
【請求項８】
Ｎ個の入力信号のうち１個を除いて、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定装置であって、
第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、
前記Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、
第２の変換規則に基づいて、前記論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの前記第１順位の信号の値または前記第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを備え、
前記ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について前記演算を行なって、Ｎ個の論理演算信号を出力し、
前記第２変換部は、前記Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成する、第１順位推定装置。
【請求項９】
前記ビット論理演算部は、
前記Ｎ個の第１変換信号のうちの２個の第１変換信号のビット単位の論理演算を行なう第１種類の論理素子と、
前記第１種類の論理素子の出力と前記Ｎ個の第１変換信号のうちの他の１個の第１変換信号とのビット単位の論理演算を行なう第２種類の論理素子とを含む、請求項８記載の第１順位推定装置。
【請求項１０】
前記第１変換部は、前記複数個の入力信号の変換を同時に並列して行ない、
前記ビット論理演算部は、前記第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なう、請求項１〜９のいずれか１項に記載の第１順位推定装置。
【請求項１１】
所定数の信号単位で復号を行なう復号装置であって、
Ｎ個の尤度を表わす入力信号のうち１個を除いて、小さなものから第１順位の信号の値を推定する第１順位推定部と、
前記第１順位推定部で推定された値と前記１単位内の信号の符号とから新たな信号を生成して前記１単位内の信号の推定信号系列を生成する受信信号推定部とを備え、
前記第１順位推定部は、
第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、
前記Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、
第２の変換規則に基づいて、前記論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの前記第１順位の信号の値または前記第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを含み、
前記ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について前記演算を行なって、Ｎ個の論理演算信号を生成し、
前記第２変換部は、前記Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成し、
前記受信信号推定部は、前記Ｎ個の第２変換信号に基づいて、前記推定信号系列を生成する、復号装置。
【請求項１２】
所定数の信号単位で復号を行なう復号装置であって、
Ｎ個の尤度を表わす入力信号のうち１個を除いて、大きなものから第１順位の信号の値を推定する第１順位推定部と、
前記第１順位推定部で推定された値と前記１単位内の信号の符号とから新たな信号を生成して前記１単位内の信号の推定信号系列を生成する受信信号推定部とを備え、
前記第１順位推定部は、
第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、
前記Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、
第２の変換規則に基づいて、前記論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの前記第１順位の信号の値または前記第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを含み、
前記ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について前記演算を行なって、Ｎ個の論理演算信号を生成し、
前記第２変換部は、前記Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成し、
前記受信信号推定部は、前記Ｎ個の第２変換信号に基づいて、前記推定信号系列を生成する、復号装置。
【請求項１３】
複数個の入力信号のうち、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定プログラムであって、
コンピュータを、
第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、
前記複数個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、
第２の変換規則に基づいて、前記論理演算信号を変換して、前記複数個の入力信号のうちの第１順位の信号の値を表わす第２変換信号を生成する第２変換部として機能させ、
前記第１の変換規則では、前記入力信号の１個が前記第１変換信号の１個に対応し、
前記第２の変換規則では、前記論理演算信号の１個が前記第２変換信号の１個に対応し、
前記第２の変換規則において前記論理演算信号に対応する前記第２変換信号の値は、前記第１の変換規則において前記論理演算信号と同一の値の前記第１変換信号に対応する前記入力信号の値と同一である、第１順位推定プログラム。
【請求項１４】
前記第１の変換規則では、前記入力信号の取り得る値の範囲は０からＮまでであり、かつ前記第１変換信号の取り得る値はＮビットで表わされ、
前記第１の変換規則では、前記入力信号の値がｋ（０≦ｋ≦Ｎ）のときに、前記第１変換信号の下位のｋ個のビットの値が第１の論理値であり、かつその他のビットの値が第２の論理値であるように変換され、
前記ビット論理演算部は、前記ビット単位の論理演算として、各ビットにつき、前記複数個の第１変換信号の前記ビットの値がすべて前記第１の論理値のときには前記第１の論理値を出力し、それ以外のときには前記第２の論理値を出力する論理演算を行なう、請求項１３記載の第１順位推定プログラム。
【請求項１５】
前記第１の変換規則では、前記入力信号の取り得る値は大きい順または小さい順に順序づけられる第１番目から第Ｎ番目までのＮ種類であり、かつ前記第１変換信号の取り得る値はＭビット（Ｍ≧（Ｎ−１））で表わされ、
前記第１の変換規則では、前記取り得る値のうちの第Ｋ番目の入力信号に対応する前記第１変換信号のビットのうち、値が第１の論理値であるビットが存在する場合に、
前記取り得る値のうちの第（Ｋ＋１）番目の入力信号に対応する前記第１変換信号については、値が第１の論理値であるビットの位置は、前記第Ｋ番目の入力信号に対応する第１変換信号のビットのうちの値が第１の論理値であるビットの位置と、さらに少なくとも１つのビットの位置とからなり、
前記ビット論理演算部は、前記ビット単位の論理演算として、各ビットにつき、前記複数個の第１変換信号の前記ビットの値がすべて前記第１の論理値のときには前記第１の論理値を出力し、それ以外のときには前記第２の論理値を出力する論理演算を行なう、
ただし、Ｋは、１以上かつ（Ｎ−１）以下のすべての自然数である、請求項１３記載の第１順位推定プログラム。
【請求項１６】
複数個の入力信号のうち、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定プログラムであって、
コンピュータを、
第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、
前記複数個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、
第２の変換規則に基づいて、前記論理演算信号を変換して、前記複数個の入力信号のうちの第１順位の信号の値または前記第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部として機能させ、
前記第１の変換規則では、前記入力信号の１個または複数個が前記第１変換信号の１個に対応し、
前記第２の変換規則では、前記論理信号の１個が前記第２変換信号の１個に対応し、
前記第２の変換規則において前記論理演算信号に対応する前記第２変換信号の値は、前記第１の変換規則において前記論理演算信号と同一の値の前記第１変換信号に対応する前記入力信号が１個のときには、前記１個の入力信号の値と同一であり、前記論理演算信号と同一の値の前記第１変換信号に対応する前記入力信号が複数個のときには、前記複数個の入力信号のうちの１つの値と同一である、第１順位推定プログラム。
【請求項１７】
前記第１の変換規則では、前記入力信号の取り得る値はＮビットで表わされ、かつ前記第１変換信号の取り得る値はＮビットで表わされ、
前記第１の変換規則では、前記入力信号のビットのうち、値が１である最も上位ビットが最下位ビットからｋ番目（１≦ｋ≦Ｎ）のビットのときに、前記第１変換信号の下位のｋ個のビットの値が第１の論理値であり、かつその他のビットの値が第２の論理値であるように変換され、前記入力信号のビットのうち、すべてのビットの値が０のときには、前記第１変換信号のすべてのビットの値が第２の論理値であるように変換され、
前記ビット論理演算部は、前記ビット単位の論理演算として、各ビットにつき、前記複数個の第１変換信号の前記ビットの値がすべて前記第１の論理値のときには前記第１の論理値を出力し、それ以外のときには前記第２の論理値を出力する論理演算を行なう、請求項１６記載の第１順位推定プログラム。
【請求項１８】
前記第２の変換規則では、前記論理演算信号の取り得る値はＮビットで表わされ、かつ前記第２変換信号の取り得る値はＮビットで表わされ、
前記第２の変換規則では、前記論理演算信号のビットのうち、値が第１の論理値である最も上位ビットが最下位ビットからｋ番目（１≦ｋ≦Ｎ）のビットのときに、前記第２変換信号の最下位ビットからｋ番目のビットの値が１であり、かつその他のビットの値が０であるように変換され、前記論理演算信号のビットのうち、すべてのビットの値が第２の論理値のときには、前記第２変換信号のすべてのビットの値が０であるように変換される、請求項１６記載の第１順位推定プログラム。
【請求項１９】
前記第１の変換規則では、前記入力信号の取り得る値は大きい順または小さい順に順序づけられる第１番目から第Ｎ番目までのＮ種類であり、前記第１変換信号の取り得る値は第１番目から第Ｍ番目までのＭ種類（Ｍ＜Ｎ）であり、
順番が小さい前記第１変換信号ほど、順番が小さい前記入力信号に対応し、
第（Ｋ＋１）番目の前記第１変換信号に対応する前記入力信号の個数は、第Ｋ番目の前記第１変換信号に対応する前記入力信号の個数以上であり、
前記第１の変換規則では、第Ｋ番目の前記第１変換信号のビットのうち、値が第１の論理値であるビットが存在する場合に、第（Ｋ＋１）番目の第１変換信号については、値が第１の論理値であるビットの位置は、前記第Ｋ番目の第１変換信号のビットのうちの値が第１の論理値であるビットの位置と、さらに少なくとも１つのビットの位置とからなり、
前記ビット論理演算部は、前記ビット単位の論理演算として、各ビットにつき、前記複数個の第１変換信号の前記ビットの値がすべて前記第１の論理値のときには前記第１の論理値を出力し、それ以外のときには前記第２の論理値を出力する論理演算を行なう、
ただし、Ｋは、１以上かつ（Ｍ−１）以下のすべての自然数である、請求項１６記載の第１順位推定プログラム。
【請求項２０】
Ｎ個の入力信号のうち１個を除いて、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定プログラムであって、
コンピュータを、
第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、
前記Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、
第２の変換規則に基づいて、前記論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの前記第１順位の信号の値または前記第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部として機能させ、
前記ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について前記演算を行なって、Ｎ個の論理演算信号を出力し、
前記第２変換部は、前記Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成する、第１順位推定プログラム。
【請求項２１】
所定数の信号単位で復号を行なう復号プログラムであって、
コンピュータを、
Ｎ個の尤度を表わす入力信号のうち１個を除いて、小さなものから第１順位の信号の値を推定する第１順位推定部と、
前記第１順位推定部で推定された値と前記１単位内の信号の符号とから新たな信号を生成して前記１単位内の信号の推定信号系列を生成する受信信号推定部として機能させ、
前記第１順位推定部は、
第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、
前記Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、
第２の変換規則に基づいて、前記論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの前記第１順位の信号の値または前記第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを含み、
前記ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について前記演算を行なって、Ｎ個の論理演算信号を生成し、
前記第２変換部は、前記Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成し、
前記受信信号推定部は、前記Ｎ個の第２変換信号に基づいて、前記推定信号系列を生成する、復号プログラム。
【請求項２２】
所定数の信号単位で復号を行なう復号プログラムであって、
コンピュータを、
Ｎ個の尤度を表わす入力信号のうち１個を除いて、大きなものから第１順位の信号の値を推定する第１順位推定部と、
前記第１順位推定部で推定された値と前記１単位内の信号の符号とから新たな信号を生成して前記１単位内の信号の推定信号系列を生成する受信信号推定部として機能させ、
前記第１順位推定部は、
第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、
前記Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、
第２の変換規則に基づいて、前記論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの前記第１順位の信号の値または前記第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを含み、
前記ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について前記演算を行なって、Ｎ個の論理演算信号を生成し、
前記第２変換部は、前記Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成し、
前記受信信号推定部は、前記Ｎ個の第２変換信号に基づいて、前記推定信号系列を生成する、復号プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、第１順位推定装置およびその第１順位推定装置を用いた低密度パリティ検査符号を復号する復号装置に関する。
【背景技術】
【０００２】
信号の通信システムを構築する場合には、高速通信、低消費電力、高通信品質（低ビット誤り率）等が要求される。受信符号の誤りを検出して訂正する誤り訂正技術は、これらの要求を満たす１つの技術として、無線、有線および記録システム等において幅広く利用されている。
【０００３】
近年、この誤り訂正技術の１つとして、低密度パリティ検査（ＬＤＰＣ：Low-Density Parity-Check）符号と、sum-product復号法とが注目されている。このＬＤＰＣ符号を利用する復号操作は、Chung等の非特許文献１において議論されている。この非特許文献１においては、符号化率１／２のイレギュラーＬＤＰＣ符号を利用して白色ガウス通信路のシャノン（Shannon）限界まで０．０４ｄＢという復号特性が得られることが示されている。イレギュラーＬＤＰＣ符号は、パリティ検査行列の行重み（行において１が立つ数）および列重み（列において１が立つ数）が、一定ではない符号を示す。行重みおよび列重みが各行および各列において一定のＬＤＰＣ符号は、レギュラーＬＤＰＣ符号と呼ばれる。
【０００４】
この非特許文献１においては、ＬＤＰＣ符号をsum-product復号法に従って復号する数学的なアルゴリズムが示されているものの、その膨大な計算を具体的に行なう回路構成については何ら示していない。
【０００５】
Yeo等の非特許文献２は、ＬＤＰＣ符号の復号装置の回路構成について検討している。この非特許文献２においては、受信系列に基づいて情報シンボルの事後確率を、トレリスに基づくＭＡＰ（最大事後確率）アルゴリズム、すなわちＢＣＪＲアルゴリズムに従って計算する。このトレリスにおいて前方向および後方向の繰返しを各状態について計算し、これらの前方向および後方向の繰返し値に基づいて、事後確率を求めている。この計算式において、加算／比較／選択／加算装置を用いて計算する。ＬＤＰＣ符号の算出においては、sum-product復号法に基づき、検査行列を生成し、異なるチェックノードからの値を利用して、推定値を算出するように回路を構成している。
【０００６】
また、非特許文献３においては、ＬＤＰＣ符号とsum-product復号法を解説し、また対数領域でのmin-sum復号法が解説されている。この非特許文献３においては、加算、最小、正負の判定および正負の符号の乗算という４種類の基本演算のみでギャラガー（Gallager）のｆ関数に従う処理を実装することができることが示されている。
【０００７】
上述の非特許文献２および３においては、パリティ検査行列を生成して１次推定語を算出するために、sum-product法に従ってギャラガー（Gallager）のｆ関数を用いて外部値対数比αを更新し、次いで、この外部値対数比に基づいてシンボルの事前値対数比βを算出する処理が行なわれる。このため、ギャラガー関数の演算に長時間を有し、また回路規模も増大する。
【０００８】
上述の非特許文献３においては、sum-product復号法とmin-sum復号法とは等価であり、min-sum復号法を利用することにより、実装時の回路構成を簡略化することができることを示している。
【非特許文献１】S. Y. Chung et al.,“On the Design of Low-Density Parity-Check Codes within 0.0045dB of the Shannon Limit”IEEE COMUNICATIONS LETTERS, VOL.5, No.2, Feb. 2001, pp.58-60
【非特許文献２】E. Yeo et al.,“VLSI Architectures for Iterative Decoders inMagnetic Recording Channels”IEEE Trans. Magnetics, Vol,37, No.2, March 2001, pp.748-755
【非特許文献３】和田山正、「低密度パリティ検査符号とその復号法について」、信学技報、ＭＲ２００１−８３、２００１年１２月
【発明の開示】
【発明が解決しようとする課題】
【０００９】
しかしながら、このmin-sum復号法を利用する場合においても、パリティ検査用の検査行列を用いて最小値を算出するＭｉｎ演算処理においては、各要素ごとにＭｉｎ演算を行なって最小値を求めており、符号の長さが増大するのに応じて、演算対象の要素数が増大し、処理時間が長時間となる。
【００１０】
それゆえに、本発明の目的は、入力された信号の中から最小または最大である第１順位を短時間で推定することができる第１順位推定装置およびこれを用いた復号装置を提供することである。
【課題を解決するための手段】
【００１１】
上記課題を解決するために、本発明は、複数個の入力信号のうち、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定装置であって、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、複数個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、第２の変換規則に基づいて、論理演算信号を変換して、複数個の入力信号のうちの第１順位の信号の値を表わす第２変換信号を生成する第２変換部とを備え、第１の変換規則では、入力信号の１個が第１変換信号の１個に対応し、第２の変換規則では、論理演算信号の１個が第２変換信号の１個に対応し、第２の変換規則において論理演算信号に対応する第２変換信号の値は、第１の変換規則において論理演算信号と同一の値の第１変換信号に対応する入力信号の値と同一である。
【００１２】
好ましくは、第１の変換規則では、入力信号の取り得る値の範囲は０からＮまでであり、かつ第１変換信号の取り得る値はＮビットで表わされ、第１の変換規則では、入力信号の値がｋ（０≦ｋ≦Ｎ）のときに、第１変換信号の下位のｋ個のビットの値が第１の論理値であり、かつその他のビットの値が第２の論理値であるように変換され、ビット論理演算部は、ビット単位の論理演算として、各ビットにつき、複数個の第１変換信号のビットの値がすべて第１の論理値のときには第１の論理値を出力し、それ以外のときには第２の論理値を出力する論理演算を行なう。
【００１３】
好ましくは、第１の変換規則では、入力信号の取り得る値は大きい順または小さい順に順序づけられる第１番目から第Ｎ番目までのＮ種類であり、かつ第１変換信号の取り得る値はＭビット（Ｍ≧（Ｎ−１））で表わされ、第１の変換規則では、取り得る値のうちの第Ｋ番目の入力信号に対応する第１変換信号のビットのうち、値が第１の論理値であるビットが存在する場合に、取り得る値のうちの第（Ｋ＋１）番目の入力信号に対応する第１変換信号については、値が第１の論理値であるビットの位置は、第Ｋ番目の入力信号に対応する第１変換信号のビットのうちの値が第１の論理値であるビットの位置と、さらに少なくとも１つのビットの位置とからなり、ビット論理演算部は、ビット単位の論理演算として、各ビットにつき、複数個の第１変換信号のビットの値がすべて第１の論理値のときには第１の論理値を出力し、それ以外のときには第２の論理値を出力する論理演算を行なう、ただし、Ｋは、１以上かつ（Ｎ−１）以下のすべての自然数である。
【００１４】
また、本発明は、複数個の入力信号のうち、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定装置であって、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、複数個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、第２の変換規則に基づいて、論理演算信号を変換して、複数個の入力信号のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを備え、第１の変換規則では、入力信号の１個または複数個が第１変換信号の１個に対応し、第２の変換規則では、論理信号の１個が第２変換信号の１個に対応し、第２の変換規則において論理演算信号に対応する第２変換信号の値は、第１の変換規則において論理演算信号と同一の値の第１変換信号に対応する入力信号が１個のときには、１個の入力信号の値と同一であり、論理演算信号と同一の値の第１変換信号に対応する入力信号が複数個のときには、複数個の入力信号のうちの１つの値と同一である。
【００１５】
好ましくは、第１の変換規則では、入力信号の取り得る値はＮビットで表わされ、かつ第１変換信号の取り得る値はＮビットで表わされ、第１の変換規則では、入力信号のビットのうち、値が１である最も上位ビットが最下位ビットからｋ番目（１≦ｋ≦Ｎ）のビットのときに、第１変換信号の下位のｋ個のビットの値が第１の論理値であり、かつその他のビットの値が第２の論理値であるように変換され、入力信号のビットのうち、すべてのビットの値が０のときには、第１変換信号のすべてのビットの値が第２の論理値であるように変換され、ビット論理演算部は、ビット単位の論理演算として、各ビットにつき、複数個の第１変換信号のビットの値がすべて第１の論理値のときには第１の論理値を出力し、それ以外のときには第２の論理値を出力する論理演算を行なう。
【００１６】
好ましくは、第２の変換規則では、論理演算信号の取り得る値はＮビットで表わされ、かつ第２変換信号の取り得る値はＮビットで表わされ、第２の変換規則では、論理演算信号のビットのうち、値が第１の論理値である最も上位ビットが最下位ビットからｋ番目（１≦ｋ≦Ｎ）のビットのときに、第２変換信号の最下位ビットからｋ番目のビットの値が１であり、かつその他のビットの値が０であるように変換され、論理演算信号のビットのうち、すべてのビットの値が第２の論理値のときには、第２変換信号のすべてのビットの値が０であるように変換される。
【００１７】
好ましくは、第１の変換規則では、入力信号の取り得る値は大きい順または小さい順に順序づけられる第１番目から第Ｎ番目までのＮ種類であり、第１変換信号の取り得る値は第１番目から第Ｍ番目までのＭ種類（Ｍ＜Ｎ）であり、順番が小さい第１変換信号ほど、順番が小さい入力信号に対応し、第（Ｋ＋１）番目の第１変換信号に対応する入力信号の個数は、第Ｋ番目の第１変換信号に対応する入力信号の個数以上であり、第１の変換規則では、第Ｋ番目の第１変換信号のビットのうち、値が第１の論理値であるビットが存在する場合に、第（Ｋ＋１）番目の第１変換信号については、値が第１の論理値であるビットの位置は、第Ｋ番目の第１変換信号のビットのうちの値が第１の論理値であるビットの位置と、さらに少なくとも１つのビットの位置とからなり、ビット論理演算部は、ビット単位の論理演算として、各ビットにつき、複数個の第１変換信号のビットの値がすべて第１の論理値のときには第１の論理値を出力し、それ以外のときには第２の論理値を出力する論理演算を行なう、ただし、Ｋは、１以上かつ（Ｍ−１）以下のすべての自然数である。
【００１８】
また、本発明は、Ｎ個の入力信号のうち１個を除いて、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定装置であって、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、第２の変換規則に基づいて、論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを備え、ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について演算を行なって、Ｎ個の論理演算信号を出力し、第２変換部は、Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成する。
【００１９】
好ましくは、ビット論理演算部は、Ｎ個の第１変換信号のうちの２個の第１変換信号のビット単位の論理演算を行なう第１種類の論理素子と、第１種類の論理素子の出力とＮ個の第１変換信号のうちの他の１個の第１変換信号とのビット単位の論理演算を行なう第２種類の論理素子とを含む。
【００２０】
好ましくは、第１変換部は、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部は、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なう。
【００２１】
また、本発明は、所定数の信号単位で復号を行なう復号装置であって、Ｎ個の尤度を表わす入力信号のうち１個を除いて、小さなものから第１順位の信号の値を推定する第１順位推定部と、第１順位推定部で推定された値と１単位内の信号の符号とから新たな信号を生成して１単位内の信号の推定信号系列を生成する受信信号推定部とを備え、第１順位推定部は、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、第２の変換規則に基づいて、論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを含み、ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について演算を行なって、Ｎ個の論理演算信号を生成し、第２変換部は、Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成し、受信信号推定部は、Ｎ個の第２変換信号に基づいて、推定信号系列を生成する。
【００２２】
また、本発明は、所定数の信号単位で復号を行なう復号装置であって、Ｎ個の尤度を表わす入力信号のうち１個を除いて、大きなものから第１順位の信号の値を推定する第１順位推定部と、第１順位推定部で推定された値と１単位内の信号の符号とから新たな信号を生成して１単位内の信号の推定信号系列を生成する受信信号推定部とを備え、第１順位推定部は、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、第２の変換規則に基づいて、論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを含み、ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について演算を行なって、Ｎ個の論理演算信号を生成し、第２変換部は、Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成し、受信信号推定部は、Ｎ個の第２変換信号に基づいて、推定信号系列を生成する。
【００２３】
また、本発明は、複数個の入力信号のうち、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定プログラムであって、コンピュータを、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、複数個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、第２の変換規則に基づいて、論理演算信号を変換して、複数個の入力信号のうちの第１順位の信号の値を表わす第２変換信号を生成する第２変換部として機能させ、第１の変換規則では、入力信号の１個が第１変換信号の１個に対応し、第２の変換規則では、論理演算信号の１個が第２変換信号の１個に対応し、第２の変換規則において論理演算信号に対応する第２変換信号の値は、第１の変換規則において論理演算信号と同一の値の第１変換信号に対応する入力信号の値と同一である。
【００２４】
好ましくは、第１の変換規則では、入力信号の取り得る値の範囲は０からＮまでであり、かつ第１変換信号の取り得る値はＮビットで表わされ、第１の変換規則では、入力信号の値がｋ（０≦ｋ≦Ｎ）のときに、第１変換信号の下位のｋ個のビットの値が第１の論理値であり、かつその他のビットの値が第２の論理値であるように変換され、ビット論理演算部は、ビット単位の論理演算として、各ビットにつき、複数個の第１変換信号のビットの値がすべて第１の論理値のときには第１の論理値を出力し、それ以外のときには第２の論理値を出力する論理演算を行なう。
【００２５】
好ましくは、第１の変換規則では、入力信号の取り得る値は大きい順または小さい順に順序づけられる第１番目から第Ｎ番目までのＮ種類であり、かつ第１変換信号の取り得る値はＭビット（Ｍ≧（Ｎ−１））で表わされ、第１の変換規則では、取り得る値のうちの第Ｋ番目の入力信号に対応する第１変換信号のビットのうち、値が第１の論理値であるビットが存在する場合に、取り得る値のうちの第（Ｋ＋１）番目の入力信号に対応する第１変換信号については、値が第１の論理値であるビットの位置は、第Ｋ番目の入力信号に対応する第１変換信号のビットのうちの値が第１の論理値であるビットの位置と、さらに少なくとも１つのビットの位置とからなり、ビット論理演算部は、ビット単位の論理演算として、各ビットにつき、複数個の第１変換信号のビットの値がすべて第１の論理値のときには第１の論理値を出力し、それ以外のときには第２の論理値を出力する論理演算を行なう、ただし、Ｋは、１以上かつ（Ｎ−１）以下のすべての自然数である。
【００２６】
また、本発明は、複数個の入力信号のうち、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定プログラムであって、コンピュータを、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、複数個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、第２の変換規則に基づいて、論理演算信号を変換して、複数個の入力信号のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部として機能させ、第１の変換規則では、入力信号の１個または複数個が第１変換信号の１個に対応し、第２の変換規則では、論理信号の１個が第２変換信号の１個に対応し、第２の変換規則において論理演算信号に対応する第２変換信号の値は、第１の変換規則において論理演算信号と同一の値の第１変換信号に対応する入力信号が１個のときには、１個の入力信号の値と同一であり、論理演算信号と同一の値の第１変換信号に対応する入力信号が複数個のときには、複数個の入力信号のうちの１つの値と同一である。
【００２７】
好ましくは、第１の変換規則では、入力信号の取り得る値はＮビットで表わされ、かつ第１変換信号の取り得る値はＮビットで表わされ、第１の変換規則では、入力信号のビットのうち、値が１である最も上位ビットが最下位ビットからｋ番目（１≦ｋ≦Ｎ）のビットのときに、第１変換信号の下位のｋ個のビットの値が第１の論理値であり、かつその他のビットの値が第２の論理値であるように変換され、入力信号のビットのうち、すべてのビットの値が０のときには、第１変換信号のすべてのビットの値が第２の論理値であるように変換され、ビット論理演算部は、ビット単位の論理演算として、各ビットにつき、複数個の第１変換信号のビットの値がすべて第１の論理値のときには第１の論理値を出力し、それ以外のときには第２の論理値を出力する論理演算を行なう。
【００２８】
好ましくは、第２の変換規則では、論理演算信号の取り得る値はＮビットで表わされ、かつ第２変換信号の取り得る値はＮビットで表わされ、第２の変換規則では、論理演算信号のビットのうち、値が第１の論理値である最も上位ビットが最下位ビットからｋ番目（１≦ｋ≦Ｎ）のビットのときに、第２変換信号の最下位ビットからｋ番目のビットの値が１であり、かつその他のビットの値が０であるように変換され、論理演算信号のビットのうち、すべてのビットの値が第２の論理値のときには、第２変換信号のすべてのビットの値が０であるように変換される。
【００２９】
好ましくは、第１の変換規則では、入力信号の取り得る値は大きい順または小さい順に順序づけられる第１番目から第Ｎ番目までのＮ種類であり、第１変換信号の取り得る値は第１番目から第Ｍ番目までのＭ種類（Ｍ＜Ｎ）であり、順番が小さい第１変換信号ほど、順番が小さい入力信号に対応し、第（Ｋ＋１）番目の第１変換信号に対応する入力信号の個数は、第Ｋ番目の第１変換信号に対応する入力信号の個数以上であり、第１の変換規則では、第Ｋ番目の第１変換信号のビットのうち、値が第１の論理値であるビットが存在する場合に、第（Ｋ＋１）番目の第１変換信号については、値が第１の論理値であるビットの位置は、第Ｋ番目の第１変換信号のビットのうちの値が第１の論理値であるビットの位置と、さらに少なくとも１つのビットの位置とからなり、ビット論理演算部は、ビット単位の論理演算として、各ビットにつき、複数個の第１変換信号のビットの値がすべて第１の論理値のときには第１の論理値を出力し、それ以外のときには第２の論理値を出力する論理演算を行なう、ただし、Ｋは、１以上かつ（Ｍ−１）以下のすべての自然数である。
【００３０】
また、本発明は、Ｎ個の入力信号のうち１個を除いて、大きいものから第１順位の信号、または小さなものから第１順位の信号の値を推定する第１順位推定プログラムであって、コンピュータを、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、第２の変換規則に基づいて、論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部として機能させ、ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について演算を行なって、Ｎ個の論理演算信号を出力し、第２変換部は、Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成する。
【００３１】
また、本発明は、所定数の信号単位で復号を行なう復号プログラムであって、コンピュータを、Ｎ個の尤度を表わす入力信号のうち１個を除いて、小さなものから第１順位の信号の値を推定する第１順位推定部と、第１順位推定部で推定された値と１単位内の信号の符号とから新たな信号を生成して１単位内の信号の推定信号系列を生成する受信信号推定部として機能させ、第１順位推定部は、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、第２の変換規則に基づいて、論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを含み、ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について演算を行なって、Ｎ個の論理演算信号を生成し、第２変換部は、Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成し、受信信号推定部は、Ｎ個の第２変換信号に基づいて、推定信号系列を生成する。
【００３２】
また、本発明は、所定数の信号単位で復号を行なう復号プログラムであって、コンピュータを、Ｎ個の尤度を表わす入力信号のうち１個を除いて、大きなものから第１順位の信号の値を推定する第１順位推定部と、第１順位推定部で推定された値と１単位内の信号の符号とから新たな信号を生成して１単位内の信号の推定信号系列を生成する受信信号推定部として機能させ、第１順位推定部は、第１の変換規則に基づいて、複数個の入力信号のそれぞれを変換して、複数個の第１変換信号を生成する第１変換部と、Ｎ個の第１変換信号のうちの、１個を除いて（Ｎ−１）個の第１変換信号のビット単位の論理演算を行なって、論理演算信号を生成するビット論理演算部と、第２の変換規則に基づいて、論理演算信号を変換して、（Ｎ−１）個の入力信号のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号を生成する第２変換部とを含み、ビット論理演算部は、除かれる１個がそれぞれ相違するＮ種類の（Ｎ−１）個の第１変換信号について演算を行なって、Ｎ個の論理演算信号を生成し、第２変換部は、Ｎ個の論理演算信号を変換して、Ｎ個の第２変換信号を生成し、受信信号推定部は、Ｎ個の第２変換信号に基づいて、推定信号系列を生成する。
【発明の効果】
【００３３】
本発明によれば、入力された信号の中から最小または最大である第１順位を短時間で推定することができる。また、これにより復号に要する時間を短くすることができる。
【発明を実施するための最良の形態】
【００３４】
以下、本発明に係る実施の形態について図面を参照して説明する。
［第１の実施形態］
（構成）
図１は、第１の実施形態の第１順位推定装置３０の構成を表わす図である。
【００３５】
図１を参照して、この第１順位推定装置３０は、４個の入力信号の中から最小値を推定して出力する装置であって、第１変換部３２と、ビット論理演算部３４と、第２変換部３６とを備える。
【００３６】
第１変換部３２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する。入力信号と第１変換信号との対応関係は、第１の変換テーブルで規定される。
【００３７】
図２は、第１の実施形態の第１の変換テーブルの例を表わす図である。
図２を参照して、第１の変換テーブルでは、１個の入力信号が１個の第１変換信号に対応している。
【００３８】
第１の変換テーブルでは、入力信号の取り得る値の範囲が０〜７であり、第１変換信号の取り得る値は７ビットで表わされる。図２において、第１変換信号の７ビットのうち、最下位ビットを最も左側に示している。本明細書における以下の説明でも、これと同様に、最下位ビットを左側に記す。
【００３９】
入力信号の値がｋ（０≦ｋ≦７）のときに、第１変換信号の下位のｋ個のビットが「１」となり、それ以外のビットが「０」となる。たとえば、入力信号の値が「０」ときには、第１変換信号のすべてのビットが「０」となる。入力信号の値が「１」のときには、第１変換信号の最下位ビットのみが「１」となる。入力信号の値が「２」のときには、第１変換信号の下位の２個のビットのみが「１」となる。
【００４０】
再び、図１を参照して、ビット論理演算部３４は、第１変換部３２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚを生成する。
【００４１】
第２変換部３６は、ビット論理演算部３４から出力される論理積信号ｚを受けて、これを変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値を表わす第２変換信号ｗを生成する。論理積信号と第２変換信号との対応関係は、第２の変換テーブルで規定される。
【００４２】
図３は、図２の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
図３を参照して、論理積信号と第２変換信号との対応関係は、図２の第１の変換テーブルの対応関係を逆にしたものである。すなわち、第２の変換テーブルにおいて論理積信号に対応する第２変換信号の値は、第１の変換テーブルにおいてその論理積信号と同一の値の第１変換信号に対応する入力信号の値と同一である。
【００４３】
第２の変換テーブルでは、１個の論理積信号が１個の第２変換信号に対応している。
論理積信号の下位のｋ個（０≦ｋ≦７）のビットが「１」で、それ以外のビットが「０」のときに、第２変換信号の値がｋとなる。たとえば、論理積信号のすべてのビットが「０」のときには、第２変換信号の値が「０」となる。論理積信号の最下位ビットのみが「１」のときには、第２変換信号の値が「１」となる。論理積信号の下位の２個のビットのみが「１」のときには、第２変換信号の値が「２」となる。
【００４４】
（各部の具体的な構成の第１の例）
次に、第１順位推定装置３０の具体的な構成の一例を説明する。
【００４５】
図４は、第１変換部３２の具体的な構成の一例を表わす図である。
図４を参照して、第１変換部３２は、複数個の入力信号の変換を同時に並列して行なう。第１変換部３２は、入力信号の個数分の第１のメモリ部で構成される。ここでは、入力信号の個数が４個であるので、第１変換部３２は、第１メモリ部（領域Ａ）３１ａと、第１メモリ部（領域Ｂ）３１ｂと、第１メモリ部（領域Ｃ）３１ｃと、第１メモリ部（領域Ｄ）３１ｄとを含む。
【００４６】
第１メモリ部（領域Ａ）３１ａでは、入力信号ｘ１がアドレスとして用いられ、入力信号ｘ１で指定される領域に第１変換信号ｙ１の値が格納されている。入力信号ｘ１と第１変換信号ｙ１との関係は、図２の第１の変換テーブルにしたがう。第１メモリ部（領域Ａ）３１ａは、３ビットの入力信号ｘ１を受けて、入力信号ｘ１に対応する７ビットの第１変換信号ｙ１（＝｛ｙ１７、ｙ１６、ｙ１５、ｙ１４、ｙ１３、ｙ１２、ｙ１１｝）を出力する。
【００４７】
第１メモリ部（領域Ｂ）３１ｂでは、入力信号ｘ２がアドレスとして用いられ、入力信号ｘ２で指定される領域に第１変換信号ｙ２の値が格納されている。入力信号ｘ２と第１変換信号ｙ２との関係は、図２の第１の変換テーブルにしたがう。第１メモリ部（領域Ｂ）３１ｂは、３ビットの入力信号ｘ２を受けて、入力信号ｘ２に対応する７ビットの第１変換信号ｙ２（＝｛ｙ２７、ｙ２６、ｙ２５、ｙ２４、ｙ２３、ｙ２２、ｙ２１｝）を出力する。
【００４８】
第１メモリ部（領域Ｃ）３１ｃでは、入力信号ｘ３がアドレスとして用いられ、入力信号ｘ３で指定される領域に第１変換信号ｙ３の値が格納されている。入力信号ｘ３と第１変換信号ｙ３との関係は、図２の第１の変換テーブルにしたがう。第１メモリ部（領域Ｃ）３１ｃは、３ビットの入力信号ｘ３を受けて、入力信号ｘ３に対応する７ビットの第１変換信号ｙ３（＝｛ｙ３７、ｙ３６、ｙ３５、ｙ３４、ｙ３３、ｙ３２、ｙ３１｝）を出力する。
【００４９】
第１メモリ部（領域Ｄ）３１ｄでは、入力信号ｘ４がアドレスとして用いられ、入力信号ｘ４で指定される領域に第１変換信号ｙ４の値が格納されている。入力信号ｘ４と第１変換信号ｙ４の関係は、図２の第１の変換テーブルにしたがう。第１メモリ部（領域Ｄ）３１ｄは、３ビットの入力信号ｘ４を受けて、入力信号ｘ４に対応する７ビットの第１変換信号ｙ４（＝｛ｙ４７、ｙ４６、ｙ４５、ｙ４４、ｙ４３、ｙ４２、ｙ４１｝）を出力する。
【００５０】
図５は、ビット論理演算部３４の具体的な構成を表わす図である。
図５を参照して、ビット論理演算部３４は、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なう。ビット論理演算部３４は、７個の論理積回路ＡＮＤ１〜ＡＮＤ７を含む。
【００５１】
第１ビット用論理積回路ＡＮＤ１は、４個の第１変換信号の第１ビット（つまり、最下位ビット）ｙ１１、ｙ２１、ｙ３１、ｙ４１の論理積ｚ１を出力する。第２ビット用論理積回路ＡＮＤ２は、４個の第１変換信号の第２ビットｙ１２、ｙ２２、ｙ３２、ｙ４２の論理積ｚ２を出力する。第３ビット用論理積回路ＡＮＤ３は、４個の第１変換信号の第３ビットｙ１３、ｙ２３、ｙ３３、ｙ４３の論理積ｚ３を出力する。第４ビット用論理積回路ＡＮＤ４は、４個の第１変換信号の第４ビットｙ１４、ｙ２４、ｙ３４、ｙ４４の論理積ｚ４を出力する。第５ビット用論理積回路ＡＮＤ５は、４個の第１変換信号の第５ビットｙ１５、ｙ２５、ｙ３５、ｙ４５の論理積ｚ５を出力する。第６ビット用論理積回路ＡＮＤ６は、４個の第１変換信号の第６ビットｙ１６、ｙ２６、ｙ３６、ｙ４６の論理積ｚ６を出力する。第７ビット用論理積回路ＡＮＤ７は、４個の第１変換信号の第７ビットｙ１７、ｙ２７、ｙ３７、ｙ４７の論理積ｚ７を出力する。このようにして生成された論理積ｚ１、ｚ２、ｚ３、ｚ４、ｚ５、ｚ６、ｚ７によって、論理積信号ｚが構成される。
【００５２】
図６は、第２変換部３６の具体的な構成を表わす図である。
図６を参照して、第２変換部３６は、第２メモリ部３５を含む。第２メモリ部３５では、論理積信号ｚがアドレスとして用いられ、論理積信号ｚで指定される領域に第２変換信号の値ｗが格納されている。論理積信号ｚと第２変換信号ｗとの関係は、図３の第２の変換テーブルにしたがう。第２メモリ部３５は、７ビットの論理積信号ｚを受けて、論理積信号ｚに対応する３ビットの第２変換信号ｗ（＝｛ｗ３、ｗ２、ｗ１｝）を出力する。このようにして出力された第２変換信号ｗが、入力信号ｘ１、ｘ２、ｘ３、ｘ４の中の最小値を表わす信号となる。
【００５３】
以上のように、第１変換部３２が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部３４が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【００５４】
（各部の具体的な構成の第２の例）
第１順位推定装置３０は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、第１順位装置３０の機能を実現することとしてもよい。この場合、第１順位推定プログラムは、図７のフローチャートで示される動作手順で動作する。
【００５５】
まず、第１変換部３２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、図２に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳ１００１）。
【００５６】
次に、ビット論理演算部３４は、第１変換部３２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚを生成する（ステップＳ１００２）。
【００５７】
次に、第２変換部３６は、ビット論理演算部３４から出力される論理積信号ｚを受けて、これを図２に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値を表わす第２変換信号ｗを生成する（ステップＳ１００３）。
【００５８】
（動作の具体例）
次に、この第１順位推定装置３０の動作を具体例を図８を用いて説明する．図８（ａ）に示すように、入力信号ｘ１が「１」、入力信号ｘ２が「３」、入力信号ｘ３が「５」、入力信号ｘ４が「６」とする。
【００５９】
第１変換部３２は、図８（ｂ）に示すような第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を出力する。すなわち、第１変換部３２の第１メモリ部（領域Ａ）３１ａは、入力信号ｘ１（＝「１」）を受けて、第１変換信号ｙ１（＝「００００００１」）を出力する。第１変換部３２の第１メモリ部（領域Ｂ）３１ｂは、入力信号ｘ２（＝「３」）を受けて、第１変換信号ｙ２（＝「００００１１１」）を出力する。第１変換部３２の第１メモリ部（領域Ｃ）３１ｃは、入力信号ｘ３（＝「５」）を受けて、第１変換信号ｙ３（＝「００１１１１１」）を出力する。第１変換部３２の第１メモリ部（領域Ｄ）３１ｄは、入力信号ｘ４（＝「６」）を受けて、第１変換信号ｙ４（＝「０１１１１１１」）を出力する。
【００６０】
次に、ビット論理演算部３４は、図８（ｃ）に示すような論理積信号ｚを出力する。すなわち、ビット論理演算部３４の第１ビット用論理積回路ＡＮＤ１は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第１ビットｙ１１（＝「１」）、ｙ２１（＝「１」）、ｙ３１（＝「１」）、ｙ４１（＝「１」）の論理積ｚ１（＝「１」）を出力する。ビット論理演算部３４の第２ビット用論理積回路ＡＮＤ２は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第２ビットｙ１２（＝「０」）、ｙ２２（＝「１」）、ｙ３２（＝「１」）、ｙ４２（＝「１」）の論理積ｚ２（＝「０」）を出力する。ビット論理演算部３４の第３ビット用論理積回路ＡＮＤ３は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第３ビットｙ１３（＝「０」）、ｙ２３（＝「１」）、ｙ３３（＝「１」）、ｙ４３（＝「１」）の論理積ｚ３（＝「０」）を出力する。ビット論理演算部３４の第４ビット用論理積回路ＡＮＤ４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第４ビットｙ１４（＝「０」）、ｙ２４（＝「０」）、ｙ３４（＝「１」）、ｙ４４（＝「１」）の論理積ｚ４（＝「０」）を出力する。ビット論理演算部３４の第５ビット用論理積回路ＡＮＤ５は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第５ビットｙ１５（＝「０」）、ｙ２５（＝「０」）、ｙ３５（＝「１」）、ｙ４５（＝「１」）の論理積ｚ５（＝「０」）を出力する。ビット論理演算部３４の第６ビット用論理積回路ＡＮＤ６は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第６ビットｙ１６（＝「０」）、ｙ２６（＝「０」）、ｙ３６（＝「０」）、ｙ４６（＝「１」）の論理積ｚ６（＝「０」）を出力する。ビット論理演算部３４の第７ビット用論理積回路ＡＮＤ７は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第７ビットｙ１７（＝「０」）、ｙ２７（＝「０」）、ｙ３７（＝「０」）、ｙ４７（＝「０」）の論理積ｚ７（＝「０」）を出力する。
【００６１】
次に、第２変換部３６は、図８（ｄ）に示すような第２変換信号ｗを出力する。すなわち、第２変換部３６の第２メモリ部３５は、論理積信号ｚ（＝「００００００１」）を受けて、第２変換信号ｗ（＝「００１」）を出力する。これによって、入力信号ｘ１（＝「００１」）、入力信号ｘ２（＝「０１１」）、入力信号ｘ３（＝「１０１」）、入力信号ｘ４（＝「１１０」）の中の最小値が第２変換信号ｗ（＝「００１」）であると検出される。
【００６２】
以上のように、第１の実施形態の第１順位推定装置によれば、要素間の比較を行なわずに、ビット単位の論理演算によって、入力された信号の中から最小または最大である第１順位を推定するので、短時間に第１順位を推定できる。また、第１の変換テーブルにおいて入力信号と第１変換信号は１対１に対応し、かつ第２の変換テーブルにおいて論理積信号と第２変換信号が１対１に対応するので、第１順位の正確な値（つまり近似値でない）を検出できる。
【００６３】
［第１の実施形態の変形例１］
図９は、第１の実施形態の変形例１の第１順位推定装置１３０の構成を表わす図である。
【００６４】
図９を参照して、この第１順位推定装置１３０は、４個の入力信号の中から最小値を推定して出力する装置であって、第１変換部１３２と、ビット論理演算部１３４と、第２変換部１３６とを備える。
【００６５】
第１変換部１３２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する。入力信号と第１変換信号との対応関係は、第１の変換テーブルで規定される。
【００６６】
図１０は、第１の実施形態の変形例１の第１の変換テーブルを表わす図である。
図１０を参照して、第１の変換テーブルの変形例１では、１個の入力信号が１個の第１変換信号に対応している。第１の変換テーブルでは、入力信号の取り得る値の範囲が０〜７であり、第１変換信号の取り得る値は７ビットで表わされる。
【００６７】
入力信号の値がｋ（０≦ｋ≦７）のときに、第１変換信号の下位のｋ個のビットが「０」となり、それ以外のビットが「１」となる。たとえば、入力信号の値が「０」ときには、第１変換信号のすべてのビットが「１」となる。入力信号の値が「１」のときには、第１変換信号の最下位ビットのみが「０」となる。入力信号の値が「２」のときには、第１変換信号の下位の２個のビットのみが「０」となる。
【００６８】
再び、図９を参照して、ビット論理演算部１３４は、第１変換部１３２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理和を算出して、各ビットの論理和からなる論理和信号ｚを生成する。
【００６９】
第２変換部１３６は、ビット論理演算部１３４から出力される論理和信号ｚを受けて、これを変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値を表わす第２変換信号ｗを生成する。論理和信号と第２変換信号との対応関係は、第２の変換テーブルで規定される。
【００７０】
図１１は、図１０の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【００７１】
図１１を参照して、論理和信号と第２変換信号との対応関係は、図１０の第１の変換テーブルの対応関係を逆にしたものである。すなわち、第２の変換テーブルにおいて論理和信号に対応する第２変換信号の値は、第１の変換テーブルにおいてその論理和信号と同一の値の第１変換信号に対応する入力信号の値と同一である。
【００７２】
第２の変換テーブルでは、１個の論理和信号が１個の第２変換信号に対応している。
論理和信号の下位のｋ個（０≦ｋ≦７）のビットが「０」で、それ以外のビットが「１」のときに、第２変換信号の値がｋとなる。たとえば、論理和信号のすべてのビットが「１」のときには、第２変換信号の値が「０」となる。論理和信号の最下位ビットのみが「０」のときには、第２変換信号の値が「１」となる。論理和信号の下位の２個のビットのみが「０」のときには、第２変換信号の値が「２」となる。
【００７３】
（各部の具体的な構成の第１の例）
次に、第１順位推定装置１３０の具体的な構成の一例を説明する。
【００７４】
第１変換部１３２の具体的な構成は、図４に示す第１の実施形態の第１変換部３２と同様である。ただし、図４の第１の実施形態の第１変換部３２では、入力信号と第１変換信号との関係は、図２の第１の変換テーブルにしたがうのに対して、本変形例の第１変換部１３２では、入力信号と第１変換信号との関係は、図１０の第１の変換テーブルにしたがう。
【００７５】
図１２は、ビット論理演算部１３４の具体的な構成を表わす図である。
図１２を参照して、ビット論理演算部１３４は、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なう。ビット論理演算部１３４は、７個の論理和回路ＯＲ１１〜ＯＲ１７を含む。
【００７６】
第１ビット用論理和回路ＯＲ１１は、４個の第１変換信号の第１ビット（つまり、最下位ビット）ｙ１１、ｙ２１、ｙ３１、ｙ４１の論理和ｚ１を出力する。第２ビット用論理和回路ＯＲ１２は、４個の第１変換信号の第２ビットｙ１２、ｙ２２、ｙ３２、ｙ４２の論理和ｚ２を出力する。第３ビット用論理和回路ＯＲ１３は、４個の第１変換信号の第３ビットｙ１３、ｙ２３、ｙ３３、ｙ４３の論理和ｚ３を出力する。第４ビット用論理和回路ＯＲ１４は、４個の第１変換信号の第４ビットｙ１４、ｙ２４、ｙ３４、ｙ４４の論理和ｚ４を出力する。第５ビット用論理和回路ＯＲ１５は、４個の第１変換信号の第５ビットｙ１５、ｙ２５、ｙ３５、ｙ４５の論理和ｚ５を出力する。第６ビット用論理和回路ＯＲ１６は、４個の第１変換信号の第６ビットｙ１６、ｙ２６、ｙ３６、ｙ４６の論理和ｚ６を出力する。第７ビット用論理和回路ＯＲ１７は、４個の第１変換信号の第７ビットｙ１７、ｙ２７、ｙ３７、ｙ４７の論理和ｚ７を出力する。このようにして生成された論理和ｚ１、ｚ２、ｚ３、ｚ４、ｚ５、ｚ６、ｚ７によって、論理和信号ｚが構成される。
【００７７】
第２変換部１３６の具体的な構成は、図６に示す第１の実施形態の第２変換部３６と同様である。ただし、図６の第１の実施形態の第２変換部３６では、論理積信号と第２変換信号との関係が図３の第２の変換テーブルにしたがうのに対して、本変形例の第２変換部１３２では、論理和信号と第２変換信号との関係が、図１１の第２の変換テーブルにしたがう。
【００７８】
以上のように、第１変換部１３２が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部１３４が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【００７９】
（各部の具体的な構成の第２の例）
第１順位推定装置１３０は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、第１順位装置１３０の機能を実現することとしてもよい。この場合、第１順位推定プログラムは、図７のフローチャートで示される動作手順で動作する。
【００８０】
まず、第１変換部１３２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、図１０に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳ１００１）。
【００８１】
次に、ビット論理演算部１３４は、第１変換部１３２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理和を算出して、各ビットの論理和からなる論理和信号ｚを生成する（ステップＳ１００２）。
【００８２】
次に、第２変換部１３６は、ビット論理演算部１３４から出力される論理和信号ｚを受けて、これを図１１に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値を表わす第２変換信号ｗを生成する（ステップＳ１００３）。
【００８３】
以上のように、第１の実施形態の変形例１の第１順位推定装置によれば、第１の実施形態と同様に、短時間に第１順位を推定でき、第１順位の正確な値（つまり近似値でない）を検出できる。
【００８４】
［第１の実施形態の変形例２］
図１３は、第１の実施形態の変形例２の第１順位推定装置２３０の構成を表わす図である。
【００８５】
図１３を参照して、この第１順位推定装置２３０は、４個の入力信号の中から最小値を検出して出力する装置であって、第１変換部２３２と、ビット論理演算部２３４と、第２変換部２３６とを備える。
【００８６】
第１変換部２３２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する。入力信号と第１変換信号との対応関係は、第１の変換テーブルで規定される。
【００８７】
図１４は、第１の実施形態の変形例２の第１の変換テーブルを表わす図である。
図１４を参照して、第１の変換テーブルでは、１個の入力信号が１個の第１変換信号に対応している。
【００８８】
この第１の変換テーブルでは、入力信号の取り得る値の範囲が小さい順に順序づけられた第１番目〜第８番目の８種類であり、第１変換信号の取り得る値は１０ビットで表わされるが、これに限定されず、第１変換信号のビット数は、入力信号の取り得る値がＮ種類のときに、Ｍビット（Ｍ≧（Ｎ−１））であればよい。また、入力信号の第１番目〜第８番目は、小さいものから第１順位の信号を推定するので、小さい順に順序づけられているが、大きいものから第１順位の信号を推定する場合には、入力信号の第１番目〜第８番目は大きい順に順序づけられたものとすればよい。
【００８９】
第１の変換テーブルにおいては、取り得る値のうちの第Ｋ番目（１≦Ｋ≦（Ｎ−１））の入力信号に対応する第１変換信号のビットのうち、値が１であるビットが存在する場合に、取り得る値のうちの第（Ｋ＋１）番目の入力信号に対応する第１変換信号については、値が１であるビットの位置は、第Ｋ番目の入力信号に対応する第１変換信号のビットのうちの値が１であるビットの位置と、さらに１つのビットの位置とからなる。ここでは、「１」となるビットが１個ずつ増加するとしたが、１個以上であれば、任意の個数でもよい。また、増加する個数は一定でなくてもよい。
【００９０】
具体的には、入力信号の値が第１番目のときには、第１変換信号の第１、第２、第３ビットが「１」となり、その他のビットが「０」となる。入力信号の値が第２番目のときには、第１変換信号の第１、第２、第３ビットに加えて、さらに第６ビットが「１」となり、その他のビットが「０」となる。入力信号の値が第３番目のときには、第１変換信号の第１、第２、第３、第６ビットに加えて、さらに第８ビットが「１」となり、その他のビットが「０」となる。入力信号の値が第４番目のときには、第１変換信号の第１、第２、第３、第６、第８ビットに加えて、さらに第１０ビットが「１」となり、その他のビットが「０」となる。入力信号の値が第５番目のときには、第１変換信号の第１、第２、第３、第６、第８、第１０ビットに加えて、さらに第９ビットが「１」となり、その他のビットが「０」となる。入力信号の値が第６番目のときには、第１変換信号の第１、第２、第３、第６、第８、第１０、第９ビットに加えて、さらに第４ビットが「１」となり、その他のビットが「０」となる。入力信号の値が第７番目ときには、第１変換信号の第１、第２、第３、第６、第８、第１０、第９、第４ビットに加えて、さらに第７ビットが「１」となり、その他のビットが「０」となる。入力信号の値が第８番目のときには、第１変換信号の第１、第２、第３、第６、第８、第１０、第９、第４、第７ビットに加えて、さらに第５ビットが「１」となり、その他のビットが「０」となる
再び、図１３を参照して、ビット論理演算部２３４は、第１変換部２３２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚを生成する。
【００９１】
第２変換部２３６は、ビット論理演算部２３４から出力される論理積信号ｚを受けて、これを変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値を表わす第２変換信号ｗを生成する。論理積信号と第２変換信号との対応関係は、第２の変換テーブルで規定される。
【００９２】
図１５は、図１４の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【００９３】
図１５を参照して、論理積信号と第２変換信号との対応関係は、図１４の第１の変換テーブルの対応関係を逆にしたものである。
すなわち、第２の変換テーブルにおいて論理積信号に対応する第２変換信号の値は、第１の変換テーブルにおいてその論理積信号と同一の値の第１変換信号に対応する入力信号の値と同一である。第２の変換テーブルでは、１個の論理積信号が１個の第２変換信号に対応している。
【００９４】
具体的には、論理積信号の第１、第２、第３ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第１番目の値となる。論理積信号の第１、第２、第３ビットに加えて、さらに第６ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第２番目の値となる。論理積信号の第１、第２、第３、第６ビットに加えて、さらに第８ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第３番目の値となる。論理積信号の第１、第２、第３、第６、第８ビットに加えて、さらに第１０ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第４番目の値となる。論理積信号の第１、第２、第３、第６、第８、第１０ビットに加えて、さらに第９ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第５番目の値となる。論理積信号の第１、第２、第３、第６、第８、第１０、第９ビットに加えて、さらに第４ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第６番目の値となる。論理積信号の第１、第２、第３、第６、第８、第１０、第９、第４ビットに加えて、さらに第７ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第７番目の値となる。論理積信号の第１、第２、第３、第６、第８、第１０、第９、第４、第７ビットに加えて、さらに第５ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第８番目の値となる。
【００９５】
（各部の具体的な構成の第１の例）
次に、第１順位推定装置２３０の具体的な構成の一例を説明する。
【００９６】
第１変換部２３２の具体的な構成は、図４に示す第１の実施形態の第１変換部３２と同様である。ただし、図４の第１の実施形態の第１変換部３２では、入力信号と第１変換信号との関係は、図２の第１の変換テーブルにしたがうのに対して、本変形例の第１変換部２３２では、入力信号と第１変換信号との関係は、図１４の第１の変換テーブルにしたがう。
【００９７】
ビット論理演算部２３４の具体的な構成は、図５に示す第１の実施形態のビット論理演算部３４と同様である。
【００９８】
第２変換部２３６の具体的な構成は、図６に示す第１の実施形態の第２変換部３６と同様である。ただし、図６の第１の実施形態の第２変換部３６では、論理積信号と第２変換信号との関係が図３の第２の変換テーブルにしたがうのに対して、本変形例の第２変換部２３６では、論理積信号と第２変換信号との関係が、図１５の第２の変換テーブルにしたがう。
【００９９】
以上のように、第１変換部２３２が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部２３４が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【０１００】
（各部の具体的な構成の第２の例）
第１順位推定装置２３０は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、第１順位装置２３０の機能を実現することとしてもよい。この場合、第１順位推定プログラムは、図７のフローチャートで示される動作手順で動作する。
【０１０１】
まず、第１変換部２３２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、図１４に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳ１００１）。
【０１０２】
次に、ビット論理演算部２３４は、第１変換部２３２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚを生成する（ステップＳ１００２）。
【０１０３】
次に、第２変換部２３６は、ビット論理演算部２３４から出力される論理積信号ｚを受けて、これを図１５に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値を表わす第２変換信号ｗを生成する（ステップＳ１００３）。
【０１０４】
（動作の具体例）
次に、この第１順位推定装置２３０の動作を具体例を図１６を用いて説明する．図１６（ａ）に示すように、入力信号ｘ１が第４番目の値、入力信号ｘ２が第７番目の値、入力信号ｘ３が第６番目の値、入力信号ｘ４が第２番目の値とする。
【０１０５】
第１変換部２３２は、図１６（ｂ）に示すような第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を出力する。すなわち、第１変換部２３２は、入力信号ｘ１（＝第４番目）を受けて、第１変換信号ｙ１（＝「１０１０１００１１１」）を出力する。第１変換部２３２は、入力信号ｘ２（＝第７番目）を受けて、第１変換信号ｙ２（＝「１１１１１０１１１１」）を出力する。第１変換部２３２は、入力信号ｘ３（＝第６番目）を受けて、第１変換信号ｙ３（＝「１１１０１０１１１１」）を出力する。第１変換部２３２は、入力信号ｘ４（＝第２番目）を受けて、第１変換信号ｙ４（＝「００００１００１１１」）を出力する。
【０１０６】
次に、ビット論理演算部２３４は、図１６（ｃ）に示すような論理積信号ｚを出力する。すなわち、ビット論理演算部２３４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第１ビットｙ１１（＝「１」）、ｙ２１（＝「１」）、ｙ３１（＝「１」）、ｙ４１（＝「１」）の論理積ｚ１（＝「１」）を出力する。ビット論理演算部２３４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第２ビットｙ１２（＝「１」）、ｙ２２（＝「１」）、ｙ３２（＝「１」）、ｙ４２（＝「１」）の論理積ｚ２（＝「１」）を出力する。ビット論理演算部２３４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第３ビットｙ１３（＝「１」）、ｙ２３（＝「１」）、ｙ３３（＝「１」）、ｙ４３（＝「１」）の論理積ｚ３（＝「１」）を出力する。ビット論理演算部２３４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第４ビットｙ１４（＝「０」）、ｙ２４（＝「１」）、ｙ３４（＝「１」）、ｙ４４（＝「０」）の論理積ｚ４（＝「０」）を出力する。ビット論理演算部２３４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第５ビットｙ１５（＝「０」）、ｙ２５（＝「０」）、ｙ３５（＝「０」）、ｙ４５（＝「０」）の論理積ｚ５（＝「０」）を出力する。ビット論理演算部２３４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第６ビットｙ１６（＝「１」）、ｙ２６（＝「１」）、ｙ３６（＝「１」）、ｙ４６（＝「１」）の論理積ｚ６（＝「１」）を出力する。ビット論理演算部２３４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第７ビットｙ１７（＝「０」）、ｙ２７（＝「１」）、ｙ３７（＝「０」）、ｙ４７（＝「０」）の論理積ｚ７（＝「０」）を出力する。ビット論理演算部２３４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第８ビットｙ１８（＝「１」）、ｙ２８（＝「１」）、ｙ３８（＝「１」）、ｙ４８（＝「０」）の論理積ｚ８（＝「０」）を出力する。ビット論理演算部２３４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第９ビットｙ１９（＝「０」）、ｙ２９（＝「１」）、ｙ３９（＝「１」）、ｙ４９（＝「０」）の論理積ｚ９（＝「０」）を出力する。ビット論理演算部２３４は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第１０ビットｙ１，１０（＝「１」）、ｙ２，１０（＝「１」）、ｙ３，１０（＝「１」）、ｙ４，１０（＝「０」）の論理積ｚ１０（＝「０」）を出力する。
【０１０７】
次に、第２変換部２３６は、図１６（ｄ）に示すような第２変換信号ｗを出力する。すなわち、第２変換部２３６は、論理積信号ｚ（＝「００００１００１１１」）を受けて、第２変換信号ｗ（＝入力信号の第２番目）を出力する。これによって、入力信号ｘ１（＝第４番目）、入力信号ｘ２（＝第７番目）、入力信号ｘ３（＝第６番目）、入力信号ｘ４（＝第２番目）の中の最小値が第２変換信号ｗ（＝第２番目）であると検出される。
【０１０８】
以上のように、第１の実施形態の変形例２の第１順位推定装置によれば、第１の実施形態と同様に、短時間に第１順位を推定でき、第１順位の正確な値（つまり近似値でない）を検出できる。
【０１０９】
［第１の実施形態の変形例３］
図１７は、第１の実施形態の変形例３の第１順位推定装置３３０の構成を表わす図である。
【０１１０】
図１７を参照して、この第１順位推定装置３３０は、４個の入力信号の中から最小値を検出して出力する装置であって、第１変換部３３２と、ビット論理演算部３３４と、第２変換部３３６とを備える。
【０１１１】
第１変換部３３２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する。入力信号と第１変換信号との対応関係は、第１の変換テーブルで規定される。
【０１１２】
図１８は、第１の実施形態の変形例３の第１の変換テーブルを表わす図である。
図１８は、図１４の第１変換信号の「０」と「１」を反転させたものである。
【０１１３】
この第１の変換テーブルでは、入力信号の取り得る値の範囲が小さい順に順序づけられた第１番目〜第８番目の８種類であり、第１変換信号の取り得る値は１０ビットで表わされるが、これに限定されず、第１変換信号のビット数は、入力信号の取り得る値がＮ種類のときに、Ｍビット（Ｍ≧（Ｎ−１））であればよい。また、第１番目〜第８番目は、小さいものから第１順位の信号を推定するので、小さい順に順序づけられているが、大きいものから第１順位の信号を推定する場合には、入力信号の第１番目〜第８番目は大きい順に順序づけられたものとすればよい。
【０１１４】
第１の変換テーブルにおいては、取り得る値のうちの第Ｋ番目（１≦Ｋ≦（Ｎ−１））の入力信号に対応する第１変換信号のビットのうち、値が０であるビットが存在する場合に、取り得る値のうちの第（Ｋ＋１）番目の入力信号に対応する第１変換信号については、値が０であるビットの位置は、第Ｋ番目の入力信号に対応する第１変換信号のビットのうちの値が０であるビットの位置と、さらに１つのビットの位置とからなる。ここでは、「０」となるビットが１個ずつ増加するとしたが、１個以上であれば、任意の個数でもよい。また、増加する個数は一定でなくてもよい。
【０１１５】
具体的には、入力信号の値が第１番目のときには、第１変換信号の第１、第２、第３ビットが「０」となり、その他のビットが「１」となる。入力信号の値が第２番目のときには、第１変換信号の第１、第２、第３ビットに加えて、さらに第６ビットが「０」となり、その他のビットが「１」となる。入力信号の値が第３番目のときには、第１変換信号の第１、第２、第３、第６ビットに加えて、さらに第８ビットが「０」となり、その他のビットが「１」となる。入力信号の値が第４番目のときには、第１変換信号の第１、第２、第３、第６、第８ビットに加えて、さらに第１０ビットが「０」となり、その他のビットが「１」となる。入力信号の値が第５番目のときには、第１変換信号の第１、第２、第３、第６、第８、第１０ビットに加えて、さらに第９ビットが「０」となり、その他のビットが「１」となる。入力信号の値が第６番目のときには、第１変換信号の第１、第２、第３、第６、第８、第１０、第９ビットに加えて、さらに第４ビットが「０」となり、その他のビットが「１」となる。入力信号の値が第７番目ときには、第１変換信号の第１、第２、第３、第６、第８、第１０、第９、第４ビットに加えて、さらに第７ビットが「０」となり、その他のビットが「１」となる。入力信号の値が第８番目のときには、第１変換信号の第１、第２、第３、第６、第８、第１０、第９、第４、第７ビットに加えて、さらに第５ビットが「０」となり、その他のビットが「１」となる
再び、図１７を参照して、ビット論理演算部３３４は、第１変換部３３２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理和を算出して、各ビットの論理和からなる論理和信号ｚを生成する。
【０１１６】
第２変換部３３６は、ビット論理演算部２３４から出力される論理和信号ｚを受けて、これを変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値を表わす第２変換信号ｗを生成する。論理積和信号と第２変換信号との対応関係は、第２の変換テーブルで規定される。
【０１１７】
図１９は、図１８の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【０１１８】
図１９を参照して、論理和信号と第２変換信号との対応関係は、図１８の第１の変換テーブルの対応関係を逆にしたものである。
【０１１９】
すなわち、第２の変換テーブルにおいて論理和信号に対応する第２変換信号の値は、第１の変換テーブルにおいてその論理和信号と同一の値の第１変換信号に対応する入力信号の値と同一である。第２の変換テーブルでは、１個の論理和信号が１個の第２変換信号に対応している。
【０１２０】
具体的には、論理和信号の第１、第２、第３ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第１番目の値となる。論理和信号の第１、第２、第３ビットに加えて、さらに第６ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第２番目の値となる。論理和信号の第１、第２、第３、第６ビットに加えて、さらに第８ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第３番目の値となる。論理和信号の第１、第２、第３、第６、第８ビットに加えて、さらに第１０ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第４番目の値となる。論理和信号の第１、第２、第３、第６、第８、第１０ビットに加えて、さらに第９ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第５番目の値となる。論理和信号の第１、第２、第３、第６、第８、第１０、第９ビットに加えて、さらに第４ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第６番目の値となる。論理和信号の第１、第２、第３、第６、第８、第１０、第９、第４ビットに加えて、さらに第７ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第７番目の値となる。論理和信号の第１、第２、第３、第６、第８、第１０、第９、第４、第７ビットに加えて、さらに第５ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第８番目の値となる。
【０１２１】
（各部の具体的な構成の第１の例）
次に、第１順位推定装置３３０の具体的な構成の一例を説明する。
【０１２２】
第１変換部３３２の具体的な構成は、図４に示す第１の実施形態の第１変換部３２と同様である。ただし、図４の第１の実施形態の第１変換部３２では、入力信号と第１変換信号との関係は、図２の第１の変換テーブルにしたがうのに対して、本変形例の第１変換部３３２では、入力信号と第１変換信号との関係は、図１８の第１の変換テーブルにしたがう。
【０１２３】
ビット論理演算部３３４の具体的な構成は、図１２に示す第１の実施形態の変形例１のビット論理演算部１３４と同様である。
【０１２４】
第２変換部３３６の具体的な構成は、図６に示す第１の実施形態の第２変換部３６と同様である。ただし、図６の第１の実施形態の第２変換部３６では、論理積信号と第２変換信号との関係が図３の第２の変換テーブルにしたがうのに対して、本変形例の第２変換部３３６では、論理和信号と第２変換信号との関係が、図１９の第２の変換テーブルにしたがう。
【０１２５】
以上のように、第１変換部３３２が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部３３４が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【０１２６】
（各部の具体的な構成の第２の例）
第１順位推定装置３３０は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、第１順位装置３３０の機能を実現することとしてもよい。この場合、第１順位推定プログラムは、図７のフローチャートで示される動作手順で動作する。
【０１２７】
まず、第１変換部３３２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、図１８に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳ１００１）。
【０１２８】
次に、ビット論理演算部３３４は、第１変換部３３２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理和を算出して、各ビットの論理和からなる論理和信号ｚを生成する（ステップＳ１００２）。
【０１２９】
次に、第２変換部３３６は、ビット論理演算部３３４から出力される論理和信号ｚを受けて、これを図１９に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値を表わす第２変換信号ｗを生成する（ステップＳ１００３）。
【０１３０】
以上のように、第１の実施形態の変形例３の第１順位推定装置によれば、第１の実施形態と同様に、短時間に第１順位を推定でき、第１順位の正確な値（つまり近似値でない）を検出できる。
【０１３１】
［第２の実施形態］
図２０は、第２の実施形態の第１順位推定装置４０の構成を表わす図である。
【０１３２】
図２０を参照して、この第１順位推定装置４０は、４個の入力信号の中から最小値またはその近似値を推定して出力する装置であって、第１変換部４２と、ビット論理演算部４４と、第２変換部４６とを備える。
【０１３３】
第１変換部４２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する。入力信号と第１変換信号との対応関係は、第１の変換テーブルで規定される。
【０１３４】
図２１は、第２の実施形態の第１の変換テーブルの例を表わす図である。
図２１を参照して、第１の変換テーブルでは、１個または複数個の入力信号が１個の第１変換信号に対応している。
【０１３５】
第１の変換テーブルでは、入力信号の取り得る値は３ビットで表わされ、第１変換信号の取り得る値は３ビットで表わされる。
【０１３６】
入力信号を構成するビットのうち、値が「１」である最も上位ビットが最下位ビットからｋ番目（１≦ｋ≦Ｎ）のビットのときに、第１変換信号の下位のｋ個のビットが「１」となり、それ以外のビットが「０」となる。また、入力信号を構成するビットのうち、すべてのビットが「０」のときに、第１変換信号のすべてのビットが「０」となる。
【０１３７】
具体的には、入力信号が「０００」のときには、第１変換信号は「０００」となる。入力信号が「００１」のときには、第１変換信号は「００１」となる。入力信号が「０１０」または「０１１」のときには、第１変換信号は「０１１」となる。入力信号が「１００」、「１０１」、「１１０」、「１１１」のときには、第１変換信号は「１１１」となる。
【０１３８】
ビット論理演算部４４は、第１変換部４２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚを出力する。
【０１３９】
第２変換部４６は、ビット論理演算部４４から出力される論理積信号ｚを受けて、これを変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗを生成する。論理積信号と第２変換信号との対応関係は、第２の変換テーブルで規定される。
【０１４０】
図２２は、図２１の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【０１４１】
図２２を参照して、論理積信号と第２変換信号との対応関係は、図２１の第１の変換テーブルの対応関係を逆にしたものである。すなわち、第２の変換テーブルにおいて論理積信号に対応する第２変換信号の値は、第１の変換テーブルにおいてその論理積信号と同一の値の第１変換信号に対応する入力信号が１個のときには、その１個の入力信号の値と同一であり、その論理積信号と同一の値の第１変換信号に対応する入力信号が複数個のときには、複数個の入力信号のうちの１つの値と同一である。
【０１４２】
第２の変換テーブルでは、１個の論理積信号が１個の第２変換信号に対応している。
論理積信号を構成するビットのうち、値が「１」である最も上位ビットが最下位ビットから第ｋ番目（１≦ｋ≦Ｎ）のビットのときに、第２変換信号の最下位ビットから第ｋ番目のビットのみが「１」となり、その他のビットが「０」となる。論理積信号を構成するビットのうち、すべてのビットが「０」のときには、第２変換信号のすべてのビットが「０」となる。
【０１４３】
具体的には、論理積信号が「０００」のときには、第２変換信号の値が「０００」となる。論理積信号が「００１」のときには、第２変換信号の値が「００１」となる。論理積信号が「０１１」のときには、第２変換信号の値が「０１０」となる。論理積信号が「１１１」のときには、第２変換信号が「１００」となる。
【０１４４】
（各部の具体的な構成の第１の例）
次に、第１順位推定装置４０の具体的な構成の一例を説明する。
【０１４５】
図２３は、第１変換部４２の具体的な構成を表わす図である。
図２３を参照して、第１変換部４２は、複数個の入力信号の変換を同時に並列して行なう。第１変換部４２は、入力信号の個数分の変換回路で構成される。ここでは、入力信号の個数が４個であるので、第１変換部４２は、変換回路４１ａと、変換回路４１ｂと、変換回路４１ｃと、変換回路４１ｄとを有する。
【０１４６】
変換回路４１ａは、次のようにして、入力信号ｘ１を第１変換信号ｙ１に変換する。すなわち、論理和回路ＯＲ１には、入力信号ｘ１の第１ビットと、入力信号ｘ１の第２ビットと、入力信号ｘ１の第３ビットとが入力されて、それらの論理和が第１変換信号ｙ１の第１ビットｙ１１として出力される。論理和回路ＯＲ２には、入力信号ｘ１の第２ビットと、入力信号ｘ１の第３ビットとが入力されて、それらの論理和が第１変換信号ｙ１の第２ビットｙ１２として出力される。入力信号ｘ１の第３ビットがそのまま第１変換信号ｙ１の第３ビットｙ１３として出力される。
【０１４７】
変換回路４１ｂは、次のようにして、入力信号ｘ２を第１変換信号ｙ２に変換する。すなわち、論理和回路ＯＲ３には、入力信号ｘ２の第１ビットと、入力信号ｘ２の第２ビットと、入力信号ｘ２の第３ビットとが入力されて、それらの論理和が第１変換信号ｙ２の第１ビットｙ２１として出力される。論理和回路ＯＲ４には、入力信号ｘ２の第２ビットと、入力信号ｘ２の第３ビットとが入力されて、それらの論理和が第１変換信号ｙ２の第２ビットｙ２２として出力される。入力信号ｘ２の第３ビットがそのまま第１変換信号ｙ２の第３ビットｙ２３として出力される。
【０１４８】
変換回路４１ｃは、次のようにして、入力信号ｘ３を第１変換信号ｙ３に変換する。すなわち、論理和回路ＯＲ５には、入力信号ｘ３の第１ビットと、入力信号ｘ３の第２ビットと、入力信号ｘ３の第３ビットとが入力されて、それらの論理和が第１変換信号ｙ３の第１ビットｙ３１として出力される。論理和回路ＯＲ５には、入力信号ｘ３の第２ビットと、入力信号ｘ３の第３ビットとが入力されて、それらの論理和が第１変換信号ｙ３の第２ビットｙ３２として出力される。入力信号ｘ３の第３ビットがそのまま第１変換信号ｙ３の第３ビットｙ３３として出力される。
【０１４９】
変換回路４１ｄは、次のようにして、入力信号ｘ４を第１変換信号ｙ４に変換する。すなわち、論理和回路ＯＲ６には、入力信号ｘ４の第１ビットと、入力信号ｘ４の第２ビットと、入力信号ｘ４の第３ビットとが入力されて、それらの論理和が第１変換信号ｙ４の第１ビットｙ４１として出力される。論理和回路ＯＲ７には、入力信号ｘ４の第２ビットと、入力信号ｘ４の第３ビットとが入力されて、それらの論理和が第１変換信号ｙ４の第２ビットｙ４２として出力される。入力信号ｘ４の第３ビットがそのまま第１変換信号ｙ４の第３ビットｙ４３として出力される。
【０１５０】
図２４は、ビット論理演算部４４の具体的な構成を表わす図である。
図２４を参照して、ビット論理演算部４４は、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なう。ビット論理演算部４４は、３個の論理積回路ＡＮＤ８〜ＡＮＤ１０を含む。
【０１５１】
第１ビット用論理積回路ＡＮＤ８は、４個の第１変換信号の第１ビット（つまり、最下位ビット）ｙ１１、ｙ２１、ｙ３１、ｙ４１の論理積ｚ１を出力する。第２ビット用論理積回路ＡＮＤ９は、４個の第１変換信号の第２ビットｙ１２、ｙ２２、ｙ３２、ｙ４２の論理積ｚ２を出力する。第３ビット用論理積回路ＡＮＤ１０は、４個の第１変換信号の第３ビットｙ１３、ｙ２３、ｙ３３、ｙ４３の論理積ｚ３を出力する。このようにして生成された論理積ｚ１、ｚ２、ｚ３によって、論理積信号ｚが構成される。
【０１５２】
図２５は、第２変換部４６の具体的な構成を表わす図である。
図２５を参照して、第２変換部４６は、変換回路４５を含む。
【０１５３】
変換回路４４５は、次のようにして、論理積信号ｚを第２変換信号ｗに変換する。
インバータＩＶ１には、論理積信号ｚの第２ビットｚ２が入力されて、それを反転した信号を出力する。インバータＩＶ２には、論理積信号ｚの第３ビットｚ３が入力されて、それを反転した信号を出力する。論理積回路ＡＮＤ１１には、論理積信号ｚの第１ビットｚ１と、インバータＩＶ１の出力信号と、インバータＩＶ２の出力信号とが入力されて、それらの論理積が第２変換信号ｗの第１ビットｗ１として出力される。論理積回路ＡＮＤ１２には、論理積信号ｚの第２ビットｚ２と、インバータＩＶ２の出力信号とが入力されて、それらの論理積が第２変換信号ｗの第２ビットｗ２として出力される。論理積信号ｚの第３ビットがそのまま第２変換信号ｗの第３ビットｗ３として出力される。
【０１５４】
このようにして出力された第２変換信号ｗが、入力信号ｘ１、ｘ２、ｘ３、ｘ４の中の最小値またはその近似値を表わす信号となる。
【０１５５】
以上のように、第１変換部４２が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部４４が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【０１５６】
（各部の具体的な構成の第２の例）
第１順位推定装置４０は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、第１順位装置４０の機能を実現することとしてもよい。この場合、第１順位推定プログラムは、図７のフローチャートで示される動作手順で動作する。
【０１５７】
まず、第１変換部４２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、図２１に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳ１００１）。
【０１５８】
次に、ビット論理演算部４４は、第１変換部４２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚを生成する（ステップＳ１００２）。
【０１５９】
次に、第２変換部４６は、ビット論理演算部４４から出力される論理積信号ｚを受けて、これを図２２に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗを生成する（ステップＳ１００３）。
【０１６０】
（動作の具体例）
次に、この第１順位推定装置４０の動作を具体例を図２６を用いて説明する。図２６（ａ）に示すように、入力信号ｘ１が「００１」、入力信号ｘ２が「０１１」、入力信号ｘ３が「１０１」、入力信号ｘ４が「１１０」とする。
【０１６１】
第１変換部４２は、図２６（ｂ）に示すような第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を出力する。すなわち、第１変換部４２の変換回路４１ａは、入力信号ｘ１（＝「００１」）を受けて、第１変換信号ｙ１（＝「００１」）を出力する。第１変換部４２の変換回路４１ｂは、入力信号ｘ２（＝「０１１」）を受けて、第１変換信号ｙ２（＝「０１１」）を出力する。第１変換部４２の変換回路４１ｃは、入力信号ｘ３（＝「１０１」）を受けて、第１変換信号ｙ３（＝「１１１」）を出力する。第１変換部４２の変換回路４１ｄは、入力信号ｘ４（＝「１１０」）を受けて、第１変換信号ｙ４（＝「１１１」）を出力する。
【０１６２】
次に、ビット論理演算部４４は、図２６（ｃ）に示すような論理積信号ｚを出力する。すなわち、ビット論理演算部４４の第１ビット用論理積回路ＡＮＤ８は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第１ビットｙ１１（＝「１」）、ｙ２１（＝「１」）、ｙ３１（＝「１」）、ｙ４１（＝「１」）の論理積ｚ１（＝「１」）を出力する。ビット論理演算部４４の第２ビット用論理積回路ＡＮＤ９は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第２ビットｙ１２（＝「０」）、ｙ２２（＝「１」）、ｙ３２（＝「１」）、ｙ４２（＝「１」）の論理積ｚ２（＝「０」）を出力する。ビット論理演算部４４の第３ビット用論理積回路ＡＮＤ１０は、４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４の第３ビットｙ１３（＝「０」）、ｙ２３（＝「０」）、ｙ３３（＝「１」）、ｙ４３（＝「１」）の論理積ｚ３（＝「０」）を出力する。
【０１６３】
次に、第２変換部４６は、図２６（ｄ）に示すような第２変換信号ｗを出力する。すなわち、第２変換部４６の変換回路４５は、論理積信号ｚ（＝「００１」）を受けて、第２変換信号ｗ（＝「００１」）を出力する。これによって、入力信号ｘ１（＝「００１」）、入力信号ｘ２（＝「０１１」）、入力信号ｘ３（＝「１０１」）、入力信号ｘ４（＝「１１０」）の中の最小値またはその近似値が第２変換信号ｗ（＝「００１」）であると推定される。
【０１６４】
以上のように、第２の実施形態の第１順位推定装置によれば、要素間の比較を行なわずに、ビット単位の論理演算によって、入力された信号の中から最小または最大である第１順位またはその近似値を推定するので、短時間に第１順位またはその近似値を推定できる。また、第１の変換テーブルにおいて入力信号のビット数と第１変換信号のビット数は同一であり、かつ第２の変換テーブルにおいて論理積信号と第２変換信号のビット数が同一であるので、専用の装置での処理の場合（具体的な構成の例１）、回路の規模（素子数および配線数）を小さくすることができ、コンピュータによる処理の場合（具体的な構成の例２）、処理時間を短かくできる。さらに、入力信号の値が小さいなところでは、１個の第１変換信号に対応する入力信号の個数が少ないので、入力信号の値が小さいときには、細かい精度での第１順位の推定が可能となる。
【０１６５】
［第２の実施形態の変形例］
図２７は、第２の実施形態の変形例の第１順位推定装置１４０の構成を表わす図である。
【０１６６】
図２７を参照して、この第１順位推定装置１４０は、４個の入力信号の中から最小値またはその近似値を推定して出力する装置であって、第１変換部１４２と、ビット論理演算部１４４と、第２変換部１４６とを備える。
【０１６７】
第１変換部１４２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、それぞれを変換した第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する。入力信号と第１変換信号との対応関係は、第１の変換テーブルで規定される。
【０１６８】
図２８は、第２の実施形態の変形例の第１の変換テーブルの例を表わす図である。
図２８を参照して、第１の変換テーブルでは、１個または複数個の入力信号が１個の第１変換信号に対応している。
【０１６９】
第１の変換テーブルでは、入力信号の取り得る値は３ビットで表わされ、第１変換信号の取り得る値は３ビットで表わされる。
【０１７０】
入力信号を構成するビットのうち、値が「１」である最も上位ビットが最下位ビットからｋ番目（１≦ｋ≦Ｎ）のビットのときに、第１変換信号の下位のｋ個のビットが「０」となり、それ以外のビットが「１」となる。また、入力信号を構成するビットのうち、すべてのビットが「０」のときに、第１変換信号のすべてのビットが「１」となる。
【０１７１】
具体的には、入力信号が「０００」のときには、第１変換信号は「１１１」となる。入力信号が「００１」のときには、第１変換信号は「１１０」となる。入力信号が「０１０」または「０１１」のときには、第１変換信号は「１００」となる。入力信号が「１００」、「１０１」、「１１０」、「１１１」のときには、第１変換信号は「０００」となる。
【０１７２】
ビット論理演算部１４４は、第１変換部１４２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理和を算出して、各ビットの論理和からなる論理和信号ｚを生成する。
【０１７３】
第２変換部１４６は、ビット論理演算部１４４から出力される論理和信号ｚを受けて、これを変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗを生成する。論理和信号と第２変換信号との対応関係は、第２の変換テーブルで規定される。
【０１７４】
図２９は、図２８の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【０１７５】
図２９を参照して、論理和信号と第２変換信号との対応関係は、図２８の第１の変換テーブルの対応関係を逆にしたものである。すなわち、第２の変換テーブルにおいて論理和信号に対応する第２変換信号の値は、第１の変換テーブルにおいてその論理和信号と同一の値の第１変換信号に対応する入力信号が１個のときには、その１個の入力信号の値と同一であり、その論理和信号と同一の値の第１変換信号に対応する入力信号が複数個のときには、複数個の入力信号のうちの１つの値と同一である。
【０１７６】
第２の変換テーブルでは、１個の論理和信号が１個の第２変換信号に対応している。
論理和信号を構成するビットのうち、値が「０」である最も上位ビットが最下位ビットから第ｋ番目（１≦ｋ≦Ｎ）のビットのときに、第２変換信号の最下位ビットから第ｋ番目のビットのみが「１」となり、その他のビットが「０」となる。論理和信号を構成するビットのうち、すべてのビットが「１」のときには、第２変換信号のすべてのビットが「０」となる。
【０１７７】
具体的には、論理和信号が「１１１」のときには、第２変換信号の値が「０００」となる。論理和信号が「１１０」のときには、第２変換信号の値が「００１」となる。論理和信号が「１００」のときには、第２変換信号の値が「０１０」となる。論理和信号が「０００」のときには、第２変換信号が「１００」となる。
【０１７８】
（各部の具体的な構成の第１の例）
次に、第１順位推定装置１４０の具体的な構成の一例を説明する。
【０１７９】
図３０は、第１変換部１４２の具体的な構成を表わす図である。
図３０を参照して、第１変換部１４２は、複数個の入力信号の変換を同時に並列して行なう。第１変換部１４２は、入力信号の個数分の変換回路で構成される。ここでは、入力信号の個数が４個であるので、第１変換部１４２は、変換回路１４１ａと、変換回路１４１ｂと、変換回路１４１ｃと、変換回路１４１ｄとを有する。
【０１８０】
変換回路１４１ａは、次のようにして、入力信号ｘ１を第１変換信号ｙ１に変換する。すなわち、論理和回路ＯＲ２１には、入力信号ｘ１の第１ビットと、入力信号ｘ１の第２ビットと、入力信号ｘ１の第３ビットとが入力されて、それらの論理和がインバータＩＶ２１を介して第１変換信号ｙ１の第１ビットｙ１１として出力される。論理和回路ＯＲ２２には、入力信号ｘ１の第２ビットと、入力信号ｘ１の第３ビットとが入力されて、それらの論理和がインバータＩＶ２２を介して第１変換信号ｙ１の第２ビットｙ１２として出力される。入力信号ｘ１の第３ビットがインバータＩＶ２３を介して第１変換信号ｙ１の第３ビットｙ１３として出力される。
【０１８１】
変換回路１４１ｂは、次のようにして、入力信号ｘ２を第１変換信号ｙ２に変換する。すなわち、論理和回路ＯＲ２３には、入力信号ｘ２の第１ビットと、入力信号ｘ２の第２ビットと、入力信号ｘ２の第３ビットとが入力されて、それらの論理和がインバータＩＶ２４を介して第１変換信号ｙ２の第１ビットｙ２１として出力される。論理和回路ＯＲ２４には、入力信号ｘ２の第２ビットと、入力信号ｘ２の第３ビットとが入力されて、それらの論理和がインバータＩＶ２５を介して第１変換信号ｙ２の第２ビットｙ２２として出力される。入力信号ｘ２の第３ビットがインバータＩＶ２６を介して第１変換信号ｙ２の第３ビットｙ２３として出力される。
【０１８２】
変換回路１４１ｃは、次のようにして、入力信号ｘ３を第１変換信号ｙ３に変換する。すなわち、論理和回路ＯＲ２５には、入力信号ｘ３の第１ビットと、入力信号ｘ３の第２ビットと、入力信号ｘ３の第３ビットとが入力されて、それらの論理和がインバータＩＶ２７を介して第１変換信号ｙ３の第１ビットｙ３１として出力される。論理和回路ＯＲ２５には、入力信号ｘ３の第２ビットと、入力信号ｘ３の第３ビットとが入力されて、それらの論理和がインバータＩＶ２８を介して第１変換信号ｙ３の第２ビットｙ３２として出力される。入力信号ｘ３の第３ビットがインバータＩＶ２９を介して第１変換信号ｙ３の第３ビットｙ３３として出力される。
【０１８３】
変換回路１４１ｄは、次のようにして、入力信号ｘ４を第１変換信号ｙ４に変換する。すなわち、論理和回路ＯＲ２６には、入力信号ｘ４の第１ビットと、入力信号ｘ４の第２ビットと、入力信号ｘ４の第３ビットとが入力されて、それらの論理和がインバータＩＶ３０を介して第１変換信号ｙ４の第１ビットｙ４１として出力される。論理和回路ＯＲ２７には、入力信号ｘ４の第２ビットと、入力信号ｘ４の第３ビットとが入力されて、それらの論理和がインバータＩＶ３１を介して第１変換信号ｙ４の第２ビットｙ４２として出力される。入力信号ｘ４の第３ビットがインバータＩＶ３２を介して第１変換信号ｙ４の第３ビットｙ４３として出力される。
【０１８４】
図３１は、ビット論理演算部１４４の具体的な構成を表わす図である。
図３１を参照して、ビット論理演算部１４４は、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なう。ビット論理演算部１４４は、３個の論理和回路ＯＲ３１〜ＯＲ３３を含む。
【０１８５】
第１ビット用論理和回路ＯＲ３１は、４個の第１変換信号の第１ビット（つまり、最下位ビット）ｙ１１、ｙ２１、ｙ３１、ｙ４１の論理和ｚ１を出力する。第２ビット用論理和回路ＯＲ３２は、４個の第１変換信号の第２ビットｙ１２、ｙ２２、ｙ３２、ｙ４２の論理和ｚ２を出力する。第３ビット用論理和回路ＯＲ３３は、４個の第１変換信号の第３ビットｙ１３、ｙ２３、ｙ３３、ｙ４３の論理和ｚ３を出力する。このようにして生成された論理和ｚ１、ｚ２、ｚ３によって、論理和信号ｚが構成される。
【０１８６】
図３２は、第２変換部１４６の具体的な構成を表わす図である。
図３２を参照して、第２変換部１４６は、変換回路１４５を含む。
【０１８７】
変換回路１４５は、次のようにして、論理積信号ｚを第２変換信号ｗに変換する。
インバータＩＶ４１は、論理積信号ｚの第１ビットｚ１を反転して論理積回路ＡＮＤ４１に送る。インバータＩＶ４２は、論理積信号ｚの第２ビットｚ２を反転して論理積回路ＡＮＤ４２とインバータＩＶ４４に送る。インバータＩＶ４３は、論理積信号ｚの第３ビットｚ３を反転して、インバータＩＶ４５に送る。インバータＩＶ４４は、インバータＩＶ４２の出力を反転して論理積回路ＡＮＤ４１に送る。インバータＩＶ４５は、インバータＩＶ４３の出力を反転して論理積回路ＡＮＤ４１と論理積回路ＡＮＤ４２に送る。論理積回路ＡＮＤ４１には、論理積信号ｚの第１ビットｚ１の反転と、論理積信号ｚの第２ビットｚ２と、論理積信号ｚの第３ビットｚ３とが入力されて、それらの論理積が第２変換信号ｗの第１ビットｗ１として出力される。論理積回路ＡＮＤ４２には、論理積信号ｚの第２ビットｚ２の反転と、論理積信号ｚの第３ビットｚ３とが入力されて、それらの論理積が第２変換信号ｗの第２ビットｗ２として出力される。インバータＩＶ４３の出力、すなわち論理積信号ｚの第３ビットｚ３の反転は第２変換信号ｗの第３ビットｗ３として出力される。このようにして出力された第２変換信号ｗが、入力信号ｘ１、ｘ２、ｘ３、ｘ４の中の最小値またはその近似値を表わす信号となる。
【０１８８】
以上のように、第１変換部１４２が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部１４４が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【０１８９】
（各部の具体的な構成の第２の例）
第１順位推定装置１４０は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、第１順位装置１４０の機能を実現することとしてもよい。この場合、第１順位推定プログラムは、図７のフローチャートで示される動作手順で動作する。
【０１９０】
まず、第１変換部１４２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、図２８に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳ１００１）。
【０１９１】
次に、ビット論理演算部１４４は、第１変換部１４２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理和を算出して、各ビットの論理和からなる論理和信号ｚを生成する（ステップＳ１００２）。
【０１９２】
次に、第２変換部１４６は、ビット論理演算部１４４から出力される論理和信号ｚを受けて、これを図２９に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗを生成する（ステップＳ１００３）。
【０１９３】
以上のように、第２の実施形態の変形例の第１順位推定装置によれば、第２の実施形態と同様に、短時間に第１順位またはその近似値を推定できるともに、専用の装置での処理の場合（具体的な構成の例１）、回路の規模（素子数および配線数）を小さくすることができ、コンピュータによる処理の場合（具体的な構成の例２）、処理時間を短くできる。また、入力信号の値が小さいときには、細かい精度での第１順位の推定が可能となる。
【０１９４】
［第３の実施形態］
（構成）
図３３は、第３の実施形態の第１順位推定装置７０の構成を表わす図である。
【０１９５】
図３３を参照して、この第１順位推定装置７０は、４個の入力信号の中から最小値を推定して出力する装置であって、第１変換部７２と、ビット論理演算部７４と、第２変換部７６とを備える。
【０１９６】
第１変換部７２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を出力する。入力信号と第１変換信号との対応関係は、第１の変換テーブルで規定される。
【０１９７】
図３４は、第３の実施形態の第１の変換テーブルの例を表わす図である。
図３４を参照して、第１の変換テーブルでは、１個または複数個の入力信号が１個の第１変換信号に対応している。
【０１９８】
第１の変換テーブルでは、入力信号の取り得る値の範囲は小さい順に順序づけられる第１番目から第１４番目までの１４種類であり、第１変換信号の取り得る値は第１番目から第５番目までの５種類であるが、これに限定されず、入力信号の取り得る値が第１番目から第Ｎ番目までのＮ種類のときに、第１変換信号は、第１番目から第Ｍ番目（Ｍ＜Ｎ）までのＭ種類であればよい。また、入力信号の第１番目〜第１４番目は、小さいものから第１順位の信号を推定するので、小さい順に順序づけられているが、大きいものから第１順位の信号を推定する場合には、入力信号の第１番目〜第１４番目は大きい順に順序づけられたものとすればよい。
【０１９９】
また、順番が小さい第１変換信号ほど、順番が小さい入力信号に対応している。
第（Ｋ＋１）番目（１≦Ｋ≦（Ｍ−１））の第１変換信号に対応する入力信号の個数は、第Ｋ番目の第１変換信号に対応する入力信号の個数以上である。また、第Ｋ番目の第１変換信号のビットのうち、値が１であるビットが存在する場合に、第（Ｋ＋１）番目の第１変換信号については、値が１であるビットの位置は、第Ｋ番目の第１変換信号のビットのうちの値が１であるビットの位置と、さらに１つのビットの位置とからなる。ここでは、「１」となるビットが１個ずつ増加するとしたが、１個以上であれば、任意の個数でもよい。また、増加する個数は一定でなくてもよい。
【０２００】
具体的には、入力信号の値が取り得る値の中で第１番目のときには、第１変換信号のすべてのビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の１種類が対応する。入力信号の値が取り得る値の中で第２番目および第３番目のときには、第１変換信号の第１ビットが「１」であり、かつその他のビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の２種類が対応する。入力信号の値が取り得る値の中で第４番目および第５番目のときには、第１変換信号の第１ビットに加えて、さらに第２ビットが「１」であり、かつその他のビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の２種類が対応する。入力信号の値が取り得る値の中で第６番目、第７番目、第８番目および第９番目のときには、第１変換信号の第１、第２ビットに加えて、さらに第３ビットが「１」であり、かつその他のビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の４種類が対応する。入力信号の値が取り得る値の中で第１０番目、第１１番目、第１２番目、第１３番目および第１４番目のときには、第１変換信号の第１、第２、第３ビットに加えて、さらに第４ビットが「１」であり、かつその他のビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の４種類が対応する。
【０２０１】
再び、図３３を参照して、ビット論理演算部７４は、第１変換部３２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚを生成する。
【０２０２】
第２変換部７６は、ビット論理演算部７４から出力される論理積信号ｚを受けて、これを変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗを生成する。論理積信号と第２変換信号との対応関係は、第２の変換テーブルで規定される。
【０２０３】
図３５は、図３４の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【０２０４】
図３５を参照して、論理積信号と第２変換信号との対応関係は、図３４の第１の変換テーブルの一部の対応関係を逆にしたものである。すなわち、第２の変換テーブルにおいて論理積信号に対応する第２変換信号の値は、第１の変換テーブルにおいてその論理積信号と同一の値の第１変換信号に対応する入力信号が１個のときには、その１個の入力信号の値と同一であり、その論理積信号と同一の値の第１変換信号に対応する入力信号が複数個のときには、複数個の入力信号のうちの１つの値と同一である。
【０２０５】
第２の変換テーブルでは、１個の論理積信号が１個の第２変換信号に対応している。
具体的には、論理積信号のすべてのビットが「０」のときには、第２変換信号の値は、入力信号の第１番目の値となる。また、論理積信号の第１ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第２番目の値となる。また、論理積信号の第１ビットに加えて、さらに第２ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第４番目の値となる。
【０２０６】
また、論理積信号の第１ビット、第２ビットに加えて、さらに第３ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第６番目の値となる。論理積信号の第１、第２、第３ビットに加えて、さらに第４ビットが「１」であるときには、第２変換信号の値は、入力信号の第１０番目の値となる。
【０２０７】
（各部の具体的な構成の第１の例）
次に、第１順位推定装置７０の具体的な構成の一例を説明する。
【０２０８】
図３６は、第１変換部の具体的な構成を表わす図である。
図３６を参照して、第１変換部７２は、複数個の入力信号の変換を同時に並列して行なう。第１変換部７２は、入力信号の個数分の第１のメモリ部で構成される。ここでは、入力信号の個数が４個であるので、第１変換部７２は、第１メモリ部（領域Ａ）７１ａと、第１メモリ部（領域Ｂ）７１ｂと、第１メモリ部（領域Ｃ）７１ｃと、第１メモリ部（領域Ｄ）７１ｄとを含む。
【０２０９】
第１メモリ部（領域Ａ）７１ａでは、入力信号ｘ１がアドレスとして用いられ、入力信号ｘ１で指定される領域に第１変換信号ｙ１の値が格納されている。入力信号ｘ１と第１変換信号ｙ１との関係は、図３４の第１の変換テーブルにしたがう。第１メモリ部（領域Ａ）７１ａは、３ビットの入力信号ｘ１を受けて、入力信号ｘ１に対応する４ビットの第１変換信号ｙ１（＝｛ｙ１４、ｙ１３、ｙ１２、ｙ１１｝）を出力する。
【０２１０】
第１メモリ部（領域Ｂ）７１ｂでは、入力信号ｘ２がアドレスとして用いられ、入力信号ｘ２で指定される領域に第１変換信号ｙ２の値が格納されている。入力信号ｘ２と第１変換信号ｙ２との関係は、図３４の第１の変換テーブルにしたがう。第１メモリ部（領域Ｂ）７１ｂは、３ビットの入力信号ｘ２を受けて、入力信号ｘ２に対応する５ビットの第１変換信号ｙ２（＝｛ｙ２４、ｙ２３、ｙ２２、ｙ２１｝）を出力する。
【０２１１】
第１メモリ部（領域Ｃ）７１ｃでは、入力信号ｘ３がアドレスとして用いられ、入力信号ｘ３で指定される領域に第１変換信号ｙ３の値が格納されている。入力信号ｘ３と第１変換信号ｙ３との関係は、図３４の第１の変換テーブルにしたがう。第１メモリ部（領域Ｃ）７１ｃは、３ビットの入力信号ｘ３を受けて、入力信号ｘ３に対応する５ビットの第１変換信号ｙ３（＝｛ｙ３４、ｙ３３、ｙ３２、ｙ３１｝）を出力する。
【０２１２】
第１メモリ部（領域Ｄ）７１ｄでは、入力信号ｘ４がアドレスとして用いられ、入力信号ｘ４で指定される領域に第１変換信号ｙ４の値が格納されている。入力信号ｘ４と第１変換信号ｙ４との関係は、図３４の第１の変換テーブルにしたがう。第１メモリ部（領域Ｄ）７１ｄは、３ビットの入力信号ｘ４を受けて、入力信号ｘ４に対応する５ビットの第１変換信号ｙ４（＝｛ｙ４４、ｙ４３、ｙ４２、ｙ４１｝）を出力する。
【０２１３】
図３７は、ビット論理演算部７４の具体的な構成を表わす図である。
図３７を参照して、ビット論理演算部７４は、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なう。ビット論理演算部７４は、４個の論理積回路ＡＮＤ７１〜ＡＮＤ７４を含む。
【０２１４】
第１ビット用論理積回路ＡＮＤ７１は、４個の第１変換信号の第１ビット（つまり、最下位ビット）ｙ１１、ｙ２１、ｙ３１、ｙ４１の論理積ｚ１を出力する。第２ビット用論理積回路ＡＮＤ７２は、４個の第１変換信号の第２ビットｙ１２、ｙ２２、ｙ３２、ｙ４２の論理積ｚ２を出力する。第３ビット用論理積回路ＡＮＤ７３は、４個の第１変換信号の第３ビットｙ１３、ｙ２３、ｙ３３、ｙ４３の論理積ｚ３を出力する。第４ビット用論理積回路ＡＮＤ７４は、４個の第１変換信号の第４ビットｙ１４、ｙ２４、ｙ３４、ｙ４４の論理積ｚ４を出力する。このようにして生成された論理積ｚ１、ｚ２、ｚ３、ｚ４、によって、論理積信号ｚが構成される。
【０２１５】
図３８は、第２変換部７６の具体的な構成を表わす図である。
図３８を参照して、第２変換部７６は、第２メモリ部７５を含む。第２メモリ部７５では、論理積信号ｚがアドレスとして用いられ、論理積信号ｚで指定される領域に第２変換信号の値ｗが格納されている。論理積信号ｚと第２変換信号ｗとの関係は、図３５の第２の変換テーブルにしたがう。第２メモリ部７５は、４ビットの論理積信号ｚを受けて、論理積信号ｚに対応する３ビットの第２変換信号ｗ（＝｛ｗ３、ｗ２、ｗ１｝）を出力する。このようにして出力された第２変換信号ｗが、入力信号ｘ１、ｘ２、ｘ３、ｘ４の中の最小値を表わす信号となる。
【０２１６】
以上のように、第１変換部７２が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部７４が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【０２１７】
（各部の具体的な構成の第２の例）
第１順位推定装置７０は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、第１順位装置７０の機能を実現することとしてもよい。この場合、第１順位推定プログラムは、図７のフローチャートで示される動作手順で動作する。
【０２１８】
まず、第１変換部７２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、図３４に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳ１００１）。
【０２１９】
次に、ビット論理演算部７４は、第１変換部７２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚを生成する（ステップＳ１００２）。
【０２２０】
次に、第２変換部７６は、ビット論理演算部７４から出力される論理積信号ｚを受けて、これを図３５に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗを生成する（ステップＳ１００３）。
【０２２１】
以上のように、第３の実施形態の第１順位推定装置によれば、要素間の比較を行なわずに、ビット単位の論理演算によって、入力された信号の中から最小または最大である第１順位またはその近似値を推定するので、短時間に第１順位またはその近似値を推定できる。また、入力信号の値が小さなところでは、１個の第１変換信号に対応する入力信号の個数が少ないので、入力信号の値が小さいときには、細かい精度での第１順位の推定が可能となる。
【０２２２】
［第３の実施形態の変形例１］
本変形の構成は、図示しないが、図３３に示す第３の実施形態の構成とほぼ同様である。ただし、本変形例では、第１変換部は、図３４の第１の変換テーブルとは異なる変換テーブルを用いる。また、第２変換部は、図３５の第２の変換テーブルとは異なる変換テーブルを用いる。
【０２２３】
また、ビット論理演算部は、第１変換部から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理和を算出して、各ビットの論理和からなる論理和信号ｚを生成する。
【０２２４】
図３９は、第３の実施形態の変形例１の第１の変換テーブルの例を表わす図である。
図３９を参照して、第１の変換テーブルでは、入力信号の取り得る値の範囲は小さい順に順序づけられる第１番目から第１４番目までの１４種類であり、第１変換信号の取り得る値は第１番目から第５番目までの５種類であるが、これに限定されず、入力信号の取り得る値が第１番目から第Ｎ番目までのＮ種類のときに、第１変換信号は、第１番目から第Ｍ番目（Ｍ＜Ｎ）までのＭ種類であればよい。また、入力信号の第１番目〜第１４番目は、小さいものから第１順位の信号を推定するので、小さい順に順序づけられているが、大きいものから第１順位の信号を推定する場合には、入力信号の第１番目〜第１４番目は大きい順に順序づけられたものとすればよい。
【０２２５】
また、順番が小さい第１変換信号ほど、順番が小さい入力信号に対応している。
第（Ｋ＋１）番目（１≦Ｋ≦（Ｍ−１））の第１変換信号に対応する入力信号の個数は、第Ｋ番目の第１変換信号に対応する入力信号の個数以上である。また、第Ｋ番目の第１変換信号のビットのうち、値が０であるビットが存在する場合に、第（Ｋ＋１）番目の第１変換信号については、値が０であるビットの位置は、第Ｋ番目の第１変換信号のビットのうちの値が０であるビットの位置と、さらに少なくとも１つのビットの位置とからなる。ここでは、「０」となるビットが１個ずつ増加するとしたが、１個以上であれば、任意の個数でもよい。また、増加する個数は一定でなくてもよい。
【０２２６】
具体的には、入力信号の値が取り得る値の中で第１番目の値のときには、第１変換信号のすべてのビットが「１」となる。この場合は、第１変換信号の１種類に対して、入力信号の１種類が対応する。入力信号の値が取り得る値の中で第２番目の値および第３番目の値のときには、第１変換信号の第１ビットが「０」であり、かつその他のビットが「１」となる。この場合は、第１変換信号の１種類に対して、入力信号の２種類が対応する。入力信号の値が取り得る値の中で第４番目、および第５番目の値のときには、第１変換信号の第１ビットに加えて、さらに第２ビットが「０」であり、かつその他のビットが「１」となる。この場合は、第１変換信号の１種類に対して、入力信号の２種類が対応する。入力信号の値が取り得る値の中で第６番目、第７番目、第８番目および第９番目の値のときには、第１変換信号の第１、第２ビットに加えて、さらに第３ビットが「０」であり、かつその他のビットが「１」となる。この場合は、第１変換信号の１種類に対して、入力信号の４種類が対応する。入力信号の値が取り得る値の中で第１０番目、第１１番目、第１２番目、第１３番目および第１４番目の値のときには、第１変換信号の第１、第２、第３ビットに加えて、さらに第４ビットが「０」であり、かつその他のビットが「１」となる。この場合は、第１変換信号の１種類に対して、入力信号の４種類が対応する。
【０２２７】
図４０は、図３９の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【０２２８】
図４０を参照して、論理和信号と第２変換信号との対応関係は、図３９の第１の変換テーブルの一部の対応関係を逆にしたものである。
【０２２９】
すなわち、第２の変換テーブルにおいて論理和信号に対応する第２変換信号の値は、第１の変換テーブルにおいてその論理和信号と同一の値の第１変換信号に対応する入力信号が１個のときには、その１個の入力信号の値と同一であり、その論理和信号と同一の値の第１変換信号に対応する入力信号が複数個のときには、複数個の入力信号のうちの１つの値と同一である。
【０２３０】
第２の変換テーブルでは、１個の論理和信号が１個の第２変換信号に対応している。
具体的には、論理和信号のすべてのビットが「１」のときには、第２変換信号の値は、入力信号の第１番目の値となる。論理和信号の第１ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第２番目の値となる。
【０２３１】
論理和信号の第１ビットに加えて、さらに第２ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第４番目の値となる。論理和信号の第１ビット、第２ビットに加えて、さらに第３ビットが「０」であり、かつその他のビットが「１」のときには、第２変換信号の値は、入力信号の第６番目の値となる。論理和信号の第１、第２、第３ビットに加えて、さらに第４ビットが「０」であるときには、第２変換信号の値は、入力信号の第１０番目の値となる。
【０２３２】
（各部の具体的な構成の第１の例）
次に、第１順位推定装置の具体的な構成の一例を説明する。
【０２３３】
第１変換部の具体的な構成の一例は、図３６に示すものと同様である。ビット論理演算部の具体的な構成の一例は、図３７に含まる論理積回路を論理和回路に変更することによって実現できる。第２変換部の具体的な構成の一例は、図３８に示すものと同様である。
【０２３４】
したがって、第１変換部が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【０２３５】
（各部の具体的な構成の第２の例）
第１順位推定装置は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、第１順位装置の機能を実現することとしてもよい。この場合、第１順位推定プログラムは、図７のフローチャートで示される動作手順で動作する。
【０２３６】
まず、第１変換部は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、図３９に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳ１００１）。
【０２３７】
次に、ビット論理演算部は、第１変換部から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理和を算出して、各ビットの論理和からなる論理和信号ｚを生成する（ステップＳ１００２）。
【０２３８】
次に、第２変換部は、ビット論理演算部から出力される論理和信号ｚを受けて、これを図４０に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗを生成する（ステップＳ１００３）。
【０２３９】
以上のように、第３の実施形態の変形例１の第１順位推定装置によれば、第３の実施形態と同様に、短時間に第１順位またはその近似値を推定できるとともに、入力信号の値が小さいときには、細かい精度での第１順位の推定が可能となる。
【０２４０】
［第３の実施形態の変形例２］
本変形の構成は、図示しないが、図３３に示す第３の実施形態の構成とほぼ同様である。ただし、本変形例では、第１変換部は、図３４の第１の変換テーブルとは異なる変換テーブルを用いる。また、第２変換部は、図３５の第２の変換テーブルとは異なる変換テーブルを用いる。
【０２４１】
図４１は、第３の実施形態の変形例２の第１の変換テーブルの例を表わす図である。
図４１を参照して、第１の変換テーブルでは、１個または複数個の入力信号が１個の第１変換信号に対応している。
【０２４２】
第１の変換テーブルでは、入力信号の取り得る値の範囲は小さい順に順序づけられる第１番目から第１４番目までの１４種類であり、第１変換信号の取り得る値は第１番目から第５番目までの６種類であるが、これに限定されず、入力信号の取り得る値が第１番目から第Ｎ番目までのＮ種類のときに、第１変換信号は、第１番目から第Ｍ番目（Ｍ＜Ｎ）までのＭ種類であればよい。また、入力信号の第１番目〜第１４番目は、小さいものから第１順位の信号を推定するので、小さい順に順序づけられているが、大きいものから第１順位の信号を推定する場合には、入力信号の第１番目〜第１４番目は大きい順に順序づけられたものとすればよい。
【０２４３】
また、順番が小さい第１変換信号ほど、順番が小さい入力信号に対応している。
第（Ｋ＋１）番目（１≦Ｋ≦（Ｍ−１））の第１変換信号に対応する入力信号の個数は、第Ｋ番目の第１変換信号に対応する入力信号の個数以上である。また、第Ｋ番目の第１変換信号のビットのうち、値が１であるビットが存在する場合に、第（Ｋ＋１）番目の第１変換信号については、値が１であるビットの位置は、第Ｋ番目の第１変換信号のビットのうちの値が１であるビットの位置と、さらに１つのビットの位置とからなる。ここでは、「１」となるビットが１個ずつ増加するとしたが、１個以上であれば、任意の個数でもよい。また、増加する個数は一定でなくてもよい。
【０２４４】
具体的には、入力信号の値が取り得る値の中で第１番目の値のときには、第１変換信号のすべてのビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の１種類が対応する。入力信号の値が取り得る値の中で第２番目および第３番目の値のときには、第１変換信号の第３ビットが「１」であり、かつその他のビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の２種類が対応する。入力信号の値が取り得る値の中で第４番目、および第５番目の値のときには、第１変換信号の第３ビットに加えて、さらに第２ビットが「１」であり、かつその他のビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の２種類が対応する。入力信号の値が取り得る値の中で第６番目、第７番目、および第８番目の値のときには、第１変換信号の第３、第２ビットに加えて、さらに第５ビットが「１」であり、かつその他のビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の３種類が対応する。入力信号の値が取り得る値の中で第９番目、第１０番目および第１１番目の値のときには、第１変換信号の第３、第２、第５ビットに加えて、さらに第１ビットが「１」であり、かつその他のビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の３種類が対応する。入力信号の値が取り得る値の中で第１２番目、第１３番目および第１４番目の値のときには、第１変換信号の第３、第２、第５、第１ビットに加えて、さらに第４ビットが「１」であり、かつその他のビットが「０」となる。この場合は、第１変換信号の１種類に対して、入力信号の３種類が対応する。
【０２４５】
図４２は、図４１の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【０２４６】
図４２を参照して、論理積信号と第２変換信号との対応関係は、図４１の第１の変換テーブルの一部の対応関係を逆にしたものである。
【０２４７】
すなわち、第２の変換テーブルにおいて論理積信号に対応する第２変換信号の値は、第１の変換テーブルにおいてその論理積信号と同一の値の第１変換信号に対応する入力信号が１個のときには、その１個の入力信号の値と同一であり、その論理積信号と同一の値の第１変換信号に対応する入力信号が複数個のときには、複数個の入力信号のうちの１つの値と同一である。
【０２４８】
第２の変換テーブルでは、１個の論理積信号が１個の第２変換信号に対応している。
具体的には、論理積信号のすべてのビットが「０」のときには、第２変換信号の値は、入力信号の第１番目の値となる。論理積信号の第３ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第２番目の値となる。論理積信号の第３ビットに加えて、さらに第２ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第４番目の値となる。論理積信号の第３ビット、第２ビットに加えて、さらに第５ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第６番目の値となる。論理積信号の第３、第２、第５ビットに加えて、さらに第１ビットが「１」であり、かつその他のビットが「０」のときには、第２変換信号の値は、入力信号の第９番目の値となる。論理積信号の第３、第２、第５、第１ビットに加えて、さらに第４ビットが「１」であるときには、第２変換信号の値は、入力信号の第１２番目の値となる。
【０２４９】
（各部の具体的な構成の第１の例）
次に、第１順位推定装置の具体的な構成の一例を説明する。
【０２５０】
第１変換部の具体的な構成の一例は、図３６に示す回路において、各メモリ部からの４個の出力を５個の出力に変更することによって実現できる。ビット論理演算部の具体的な構成の一例は、図３７に示す回路に含まれる４個の論理積回路を５個の論理積回路に変更することによって実現できる。第２変換部の具体的な構成の一例は、図３８に示す回路において、第２メモリ部への４個の入力を５個の入力に変更することによって実現できる。
【０２５１】
したがって、第１変換部が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【０２５２】
（各部の具体的な構成の第２の例）
第１順位推定装置は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、第１順位装置の機能を実現することとしてもよい。この場合、第１順位推定プログラムは、図７のフローチャートで示される動作手順で動作する。
【０２５３】
まず、第１変換部は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、図４１に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳ１００１）。
【０２５４】
次に、ビット論理演算部は、第１変換部から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚを生成する（ステップＳ１００２）。
【０２５５】
次に、第２変換部は、ビット論理演算部から出力される論理積信号ｚを受けて、これを図４２に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗを生成する（ステップＳ１００３）。
【０２５６】
以上のように、第３の実施形態の変形例２の第１順位推定装置によれば、第３の実施形態と同様に、短時間に第１順位またはその近似値を推定できるとともに、入力信号の値が小さいときには、細かい精度での第１順位の推定が可能となる。
【０２５７】
［第４の実施形態］
図４３は、第４の実施形態の第１順位推定装置５０の構成を表わす図である。
【０２５８】
図４３を参照して、この第１順位推定装置５０は、複数個の入力信号のうち、自分自身を除く入力信号の最小値またはその近似値を複数個推定して出力する装置であって、第１変換部４２と、ビット論理演算部５４と、第２変換部５６とを備える。
【０２５９】
第１変換部４２は、図２０に示す第２の実施形態の第１順位推定装置４０に含まれるものと同一であり、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、それぞれを図２１に示す第１の変換テーブルで規定される対応関係で変換した第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する。
【０２６０】
ビット論理演算部５４は、第１変換部４２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を受ける。ビット論理演算部５４は、第１変換信号ｙ１を除く３個の第１変換信号ｙ２、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚ１を生成する。また、ビット論理演算部５４は、第１変換信号ｙ２を除く３個の第１変換信号ｙ１、ｙ３、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚ２を生成する。また、ビット論理演算部５４は、第１変換信号ｙ３を除く３個の第１変換信号ｙ１、ｙ２、ｙ４のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚ３を生成する。また、ビット論理演算部５４は、第１変換信号ｙ４を除く３個の第１変換信号ｙ１、ｙ２、ｙ３のビット単位の論理積を算出して、各ビットの論理積からなる論理積信号ｚ４を生成する。
【０２６１】
第２変換部５６は、ビット論理演算部５４から出力される４個の論理積信号ｚ１、ｚ２、ｚ３、ｚ４を受けて、それぞれを変換して、３個の入力信号ｘ２、ｘ３、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗ１と、３個の入力信号ｘ１、ｘ３、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗ２と、３個の入力信号ｘ１、ｘ２、ｘ４のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗ３と、３個の入力信号ｘ１、ｘ２、ｘ３のうちの第１順位の信号の値または第１順位の信号の近似値を表わす第２変換信号ｗ４とを生成する。各論理積信号と各第２変換信号との対応関係は、第２の実施形態と同様に、図２２に示す第２の変換テーブルで規定される。
【０２６２】
（各部の具体的な構成の第１の例）
次に、第１順位推定装置５０の具体的な構成の一例を説明する。
【０２６３】
第１変換部４２の具体的な構成は、図２３に示すものと同様なので、ここでは説明を繰返さない。
【０２６４】
図４４は、ビット論理演算部５４の具体的な構成を表わす図である。
図４４を参照して、ビット論理演算部５４は、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なう。ビット論理演算部５４は、第１ビット用論理演算回路５３ａと、第２ビット用論理演算回路５３ｂと、第３ビット用論理演算回路５３ｃとを含む。
【０２６５】
第１ビット用論理演算回路５３ａは、論理積回路ＡＮＤ２０、ＡＮＤ２１、ＡＮＤ２２、ＡＮＤ２３を含む。論理積回路ＡＮＤ２０は、３個の第１変換信号の第１ビット（つまり、最下位ビット）ｙ２１、ｙ３１、ｙ４１の論理積ｚ１１を出力する。論理積回路ＡＮＤ２１は、３個の第１変換信号の第１ビットｙ１１、ｙ３１、ｙ４１の論理積ｚ２１を出力する。論理積回路ＡＮＤ２２は、３個の第１変換信号の第１ビット（つまり、最下位ビット）ｙ１１、ｙ２１、ｙ４１の論理積ｚ３１を出力する。論理積回路ＡＮＤ２３は、３個の第１変換信号の第１ビット（つまり、最下位ビット）ｙ１１、ｙ２１、ｙ３１の論理積ｚ４１を出力する。
【０２６６】
第２ビット用論理演算回路５３ｂは、論理積回路ＡＮＤ２４、ＡＮＤ２５、ＡＮＤ２６、ＡＮＤ２７を含む。論理積回路ＡＮＤ２４は、３個の第１変換信号の第２ビットｙ２２、ｙ３２、ｙ４２の論理積ｚ１２を出力する。論理積回路ＡＮＤ２５は、３個の第１変換信号の第２ビットｙ１２、ｙ３２、ｙ４２の論理積ｚ２２を出力する。論理積回路ＡＮＤ２６は、３個の第１変換信号の第２ビットｙ１２、ｙ２２、ｙ４２の論理積ｚ３２を出力する。論理積回路ＡＮＤ２７は、３個の第１変換信号の第２ビットｙ１２、ｙ２２、ｙ３２の論理積ｚ４２を出力する。
【０２６７】
第３ビット用論理演算回路５３ｃは、論理積回路ＡＮＤ２８、ＡＮＤ２９、ＡＮＤ３０、ＡＮＤ３１を含む。論理積回路ＡＮＤ２８は、３個の第１変換信号の第３ビットｙ２３、ｙ３３、ｙ４３の論理積ｚ１３を出力する。論理積回路ＡＮＤ２９は、３個の第１変換信号の第３ビットｙ１３、ｙ３３、ｙ４３の論理積ｚ２３を出力する。論理積回路ＡＮＤ３０は、３個の第１変換信号の第３ビットｙ１３、ｙ２３、ｙ４３の論理積ｚ３３を出力する。論理積回路ＡＮＤ３１は、３個の第１変換信号の第３ビットｙ１３、ｙ２３、ｙ３３の論理積ｚ４３を出力する。
【０２６８】
図４５は、第２変換部５６の具体的な構成を表わす図である。
図４５を参照して、第２変換部５６は、各論理積信号の第２変換信号への変換を同時に並列して行なう。第２変換部５６は、変換回路５５ａ、５５ｂ、５５ｃ、５５ｄを含む。
【０２６９】
変換回路５５ａは、次のようにして、論理積信号ｚ１を第２変換信号ｗ１に変換する。
インバータＩＶ８０には、論理積信号ｚ１の第２ビットｚ１２が入力されて、それを反転した信号を出力する。インバータＩＶ８１には、論理積信号ｚ１の第３ビットｚ１３が入力されて、それを反転した信号を出力する。論理積回路ＡＮＤ８０には、論理積信号ｚ１の第１ビットｚ１１と、インバータＩＶ８０の出力信号と、インバータＩＶ８１の出力信号とが入力されて、それらの論理積が第２変換信号ｗ１の第１ビットｗ１１として出力される。論理積回路ＡＮＤ８１には、論理積信号ｚ１の第２ビットｚ１２と、インバータＩＶ８１の出力信号とが入力されて、それらの論理積が第２変換信号ｗ１の第２ビットｗ１２として出力される。論理積信号ｚ１の第３ビットｚ１３がそのまま第２変換信号ｗ１の第３ビットｗ１３として出力される。このようにして出力された第２変換信号ｗ１（＝｛ｗ１３、ｗ１２、ｗ１１｝）が、入力信号ｘ２、ｘ３、ｘ４の中の最小値またはその近似値を表わす信号となる。
【０２７０】
変換回路５５ｂは、次のようにして、論理積信号ｚ２を第２変換信号ｗ２に変換する。
インバータＩＶ８２には、論理積信号ｚ２の第２ビットｚ２２が入力されて、それを反転した信号を出力する。インバータＩＶ８３には、論理積信号ｚ２の第３ビットｚ２３が入力されて、それを反転した信号を出力する。論理積回路ＡＮＤ８２には、論理積信号ｚ２の第１ビットｚ２１と、インバータＩＶ８２の出力信号と、インバータＩＶ８３の出力信号とが入力されて、それらの論理積が第２変換信号ｗ２の第１ビットｗ２１として出力される。論理積回路ＡＮＤ８３には、論理積信号ｚ２の第２ビットｚ２２と、インバータＩＶ８３の出力信号とが入力されて、それらの論理積が第２変換信号ｗ２の第２ビットｗ２２として出力される。論理積信号ｚ２の第３ビットｚ２３がそのまま第２変換信号ｗ２の第３ビットｗ２３として出力される。このようにして出力された第２変換信号ｗ２（＝｛ｗ２３、ｗ２２、ｗ２１｝）が、入力信号ｘ１、ｘ３、ｘ４の中の最小値またはその近似値を表わす信号となる。
【０２７１】
変換回路５５cは、次のようにして、論理積信号ｚ３を第２変換信号ｗ３に変換する。
インバータＩＶ８４には、論理積信号ｚ３の第２ビットｚ３２が入力されて、それを反転した信号を出力する。インバータＩＶ８５には、論理積信号ｚ３の第３ビットｚ３３が入力されて、それを反転した信号を出力する。論理積回路ＡＮＤ８４には、論理積信号ｚ３の第１ビットｚ３１と、インバータＩＶ８４の出力信号と、インバータＩＶ８５の出力信号とが入力されて、それらの論理積が第２変換信号ｗ３の第１ビットｗ３１として出力される。論理積回路ＡＮＤ８５には、論理積信号ｚ３の第２ビットｚ３２と、インバータＩＶ８５の出力信号とが入力されて、それらの論理積が第２変換信号ｗ３の第２ビットｗ３２として出力される。論理積信号ｚ３の第３ビットｚ３３がそのまま第２変換信号ｗ３の第３ビットｗ３３として出力される。このようにして出力された第２変換信号ｗ３（＝｛ｗ３３、ｗ３２、ｗ３１｝）が、入力信号ｘ１、ｘ２、ｘ４の中の最小値またはその近似値を表わす信号となる。
【０２７２】
変換回路５５ｄは、次のようにして、論理積信号ｚ４を第２変換信号ｗ４に変換する。
インバータＩＶ８２には、論理積信号ｚ４の第２ビットｚ４２が入力されて、それを反転した信号を出力する。インバータＩＶ８３には、論理積信号ｚ４の第３ビットｚ４３が入力されて、それを反転した信号を出力する。論理積回路ＡＮＤ８２には、論理積信号ｚ４の第１ビットｚ４１と、インバータＩＶ８２の出力信号と、インバータＩＶ８３の出力信号とが入力されて、それらの論理積が第２変換信号ｗ４の第１ビットｗ４１として出力される。論理積回路ＡＮＤ８３には、論理積信号ｚ４の第２ビットｚ４２と、インバータＩＶ８３の出力信号とが入力されて、それらの論理積が第２変換信号ｗ４の第２ビットｗ４２として出力される。論理積信号ｚ４の第３ビットｚ４３がそのまま第２変換信号ｗ４の第３ビットｗ４３として出力される。このようにして出力された第２変換信号ｗ４（＝｛ｗ４３、ｗ４２、ｗ４１｝）が、入力信号ｘ１、ｘ２、ｘ３の中の最小値またはその近似値を表わす信号となる。
【０２７３】
以上のように、第１変換部５２が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部５４が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【０２７４】
（各部の具体的な構成の第２の例）
第１順位推定装置５０は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、第１順位装置５０の機能を実現することとしてもよい。この場合、第１順位推定プログラムは、図７のフローチャートで示される動作手順で動作する。
【０２７５】
まず、第１変換部４２は、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４を受けて、図２１に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳ１００１）。
【０２７６】
次に、ビット論理演算部５４は、第１変換部４２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４について、１個を除いた３個の第１変換信号のビット単位の論理積を、除く１個が相違するＮ種類について算出して、論理積信号ｚ１、ｚ２、ｚ３、ｚ４を生成する（ステップＳ１００２）。
【０２７７】
次に、第２変換部５６は、ビット論理演算部５４から出力される論理積信号ｚ１、ｚ２、ｚ３、ｚ４を受けて、これらをそれぞれ図２２に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの１個を除いた３個の第１順位の信号の値または第１順位の信号の近似値を表わす４個の第２変換信号ｗ１、ｗ２、ｗ３、ｗ４を生成する（ステップＳ１００３）。
【０２７８】
（動作の具体例）
次に、この第１順位推定装置５０の動作を具体例を図４６を用いて説明する。図４６（ａ）に示すように、入力信号ｘ１が「００１」、入力信号ｘ２が「０１１」、入力信号ｘ３が「１０１」、入力信号ｘ４が「１１０」とする。
【０２７９】
第１変換部４２は、図４６（ｂ）に示すような第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を出力する。すなわち、第１変換部４２の変換回路４１ａは、入力信号ｘ１（＝「００１」）を受けて、第１変換信号ｙ１（＝「００１」）を出力する。第１変換部４２の変換回路４１ｂは、入力信号ｘ２（＝「０１１」）を受けて、第１変換信号ｙ２（＝「０１１」）を出力する。第１変換部４２の変換回路４１ｃは、入力信号ｘ３（＝「１０１」）を受けて、第１変換信号ｙ３（＝「１１１」）を出力する。第１変換部４２の変換回路４１ｄは、入力信号ｘ４（＝「１１０」）を受けて、第１変換信号ｙ４（＝「１１１」）を出力する。
【０２８０】
次に、ビット論理演算部５４は、図４６（ｃ）に示すような論理積信号ｚ１、ｚ２、ｚ３、ｚ４を出力する。
【０２８１】
ビット論理演算部５４の第１ビット用論理演算回路５３ａでは、次のようにして、論理積信号ｚ１、ｚ２、ｚ３、ｚ４の第１ビット目が出力される。
【０２８２】
論理積回路ＡＮＤ２０は、３個の第１変換信号ｙ２、ｙ３、ｙ４の第１ビットｙ２１（＝「１」）、ｙ３１（＝「１」）、ｙ４１（＝「１」）の論理積ｚ１１（＝「１」）を出力する。論理積回路ＡＮＤ２１は、３個の第１変換信号ｙ１、ｙ３、ｙ４の第１ビットｙ１１（＝「１」）、ｙ３１（＝「１」）、ｙ４１（＝「１」）の論理積ｚ２１（＝「１」）を出力する。論理積回路ＡＮＤ２２は、３個の第１変換信号ｙ１、ｙ２、ｙ４の第１ビットｙ１１（＝「１」）、ｙ２１（＝「１」）、ｙ４１（＝「１」）の論理積ｚ３１（＝「１」）を出力する。論理積回路ＡＮＤ２３は、３個の第１変換信号ｙ１、ｙ２、ｙ３の第１ビットｙ１１（＝「１」）、ｙ２１（＝「１」）、ｙ３１（＝「１」）の論理積ｚ４１（＝「１」）を出力する。
【０２８３】
ビット論理演算部５４の第２ビット用論理演算回路５３ｂでは、次のようにして、論理積信号ｚ１、ｚ２、ｚ３、ｚ４の第２ビット目が出力される。
【０２８４】
論理積回路ＡＮＤ２４は、３個の第１変換信号ｙ２、ｙ３、ｙ４の第２ビットｙ２２（＝「１」）、ｙ３２（＝「１」）、ｙ４２（＝「１」）の論理積ｚ１２（＝「１」）を出力する。論理積回路ＡＮＤ２５は、３個の第１変換信号ｙ１、ｙ３、ｙ４の第２ビットｙ１２（＝「０」）、ｙ３２（＝「１」）、ｙ４２（＝「１」）の論理積ｚ２２（＝「０」）を出力する。論理積回路ＡＮＤ２６は、３個の第１変換信号ｙ１、ｙ２、ｙ４の第２ビットｙ１２（＝「０」）、ｙ２２（＝「１」）、ｙ４２（＝「１」）の論理積ｚ３２（＝「０」）を出力する。論理積回路ＡＮＤ２７は、３個の第１変換信号ｙ１、ｙ２、ｙ３の第１ビットｙ１２（＝「０」）、ｙ２２（＝「１」）、ｙ３２（＝「１」）の論理積ｚ４２（＝「０」）を出力する。
【０２８５】
ビット論理演算部５４の第２ビット用論理演算回路５３ｃでは、次のようにして、論理積信号ｚ１、ｚ２、ｚ３、ｚ４の第２ビット目が出力される。
【０２８６】
論理積回路ＡＮＤ２８は、３個の第１変換信号ｙ２、ｙ３、ｙ４の第３ビットｙ２３（＝「０」）、ｙ３３（＝「１」）、ｙ４３（＝「１」）の論理積ｚ１３（＝「０」）を出力する。論理積回路ＡＮＤ２９は、３個の第１変換信号ｙ１、ｙ３、ｙ４の第３ビットｙ１３（＝「０」）、ｙ３３（＝「１」）、ｙ４４（＝「１」）の論理積ｚ２３（＝「０」）を出力する。論理積回路ＡＮＤ３０は、３個の第１変換信号ｙ１、ｙ２、ｙ４の第３ビットｙ１３（＝「０」）、ｙ２３（＝「１」）、ｙ４３（＝「１」）の論理積ｚ３３（＝「０」）を出力する。論理積回路ＡＮＤ３１は、３個の第１変換信号ｙ１、ｙ２、ｙ３の第１ビットｙ１３（＝「０」）、ｙ２３（＝「０」）、ｙ３３（＝「１」）の論理積ｚ４３（＝「０」）を出力する。
【０２８７】
次に、第２変換部５６は、図４６（ｄ）に示すような第２変換信号ｗ１、ｗ２、ｗ３、ｗ４を出力する。
【０２８８】
すなわち、第２変換部５６の変換回路５５ａは、論理積信号ｚ１（＝「０１１」）を受けて、第２変換信号ｗ１（＝「０１０」＝２）を出力する。
【０２８９】
第２変換部５６の変換回路５５ｂは、論理積信号ｚ２（＝「００１」）を受けて、第２変換信号ｗ２（＝「００１」＝１）を出力する。
【０２９０】
第２変換部５６の変換回路５５ｃは、論理積信号ｚ３（＝「００１」）を受けて、第２変換信号ｗ３（＝「００１」＝１）を出力する。
【０２９１】
第２変換部５６の変換回路５５ｄは、論理積信号ｚ４（＝「００１」）を受けて、第２変換信号ｗ２（＝「００１」＝１）を出力する。
【０２９２】
以上によって、入力信号ｘ１（＝「００１」）、入力信号ｘ２（＝「０１１」）、入力信号ｘ３（＝「１０１」）、入力信号ｘ４（＝「１１０」）の中で、入力信号ｘ１を除く最小値またはその近似値が第２変換信号ｗ１（＝「０１０」＝２）であると推定され、入力信号ｘ２を除く最小値またはその近似値が第２変換信号ｗ２（＝「００１」＝１）であると推定され、入力信号ｘ３を除く最小値またはその近似値が第２変換信号ｗ３（＝「００１」＝１）であると推定され、入力信号ｘ４を除く最小値またはその近似値が第２変換信号ｗ４（＝「００１」＝１）であると推定される。
【０２９３】
以上のように、第４の実施形態の第１順位推定装置によれば、入力された信号の中のうちの１個を除く信号の最小または最大である第１順位またはその近似値を複数個推定するが、要素間の比較を行なわずにビット単位の論理演算によって、これらの推定を行なうので、短時間での推定が可能となる。
【０２９４】
［第４の実施形態の変形例１］
第４の実施形態では、第１変換部は、第２の実施形態で説明した図２１の第１の変換テーブルで変換を行ない、第２変換部は、第２の実施形態で説明した図２２の第２の変換テーブルで変換を行なうこととしたが、これに限定するものではない。第１変換部および第２変換部は、第１の実施形態、第１の実施形態の変形例、第２の実施形態の変形例、第３の実施形態、第３の実施形態の変形例で説明した変換テーブルで変換を行なうものとしてもよい。
【０２９５】
［第４の実施形態の変形例２］
図４７は、第４の実施形態の変形例２の第１順位推定装置６０の構成を表わす図である。
【０２９６】
図４７を参照して、この第１順位推定装置６０は、第３の実施形態と同様に、複数個の入力信号のうち、自分自身を除く入力信号の最小値またはその近似値を複数個推定して出力する装置であって、第１変換部４２と、ビット論理演算部６４と、第２変換部５６とを備える。
【０２９７】
第１変換部４２および第２変換部５６は、図４３に示す第４の実施形態の第１順位推定装置５０に含まれるものと同様である。
【０２９８】
ビット論理演算部６４は、第４の実施形態のビット論理演算部５４と同様に、第１変換部４２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を受けて、論理積信号ｚ１、ｚ２、ｚ３、ｚ４を生成する。本変形例のビット論理演算部６４は、第４の実施形態のビット論理演算部５４と具体的な構成において相違する。
【０２９９】
（ビット論理演算部６４の具体的な構成）
図４８は、ビット論理演算部６４の具体的な構成を表わす図である。
【０３００】
図４８を参照して、ビット論理演算部６４は、第１ビット用論理演算回路６３ａと、第２ビット用論理演算回路６３ｂと、第３ビット用論理演算回路６３ｃとを含む。
【０３０１】
第１ビット用論理演算回路６３ａは、論理積回路ＡＮＤ５０、ＡＮＤ５１、ＡＮＤ５２、ＡＮＤ５３、ＡＮＤ５４、ＡＮＤ５５を含む。論理積回路ＡＮＤ５０は、第１変換信号ｙ１の第１ビットｙ１１と、第１変換信号ｙ２の第１ビットｙ２１との論理積を出力する。論理積回路ＡＮＤ５１は、第１変換信号ｙ１の第１ビットｙ１１と、論理積回路ＡＮＤ５３の出力信号との論理積ｚ２１を出力する。論理積回路ＡＮＤ５２は、第１変換信号ｙ２の第１ビットｙ２１と、論理積回路ＡＮＤ５３の出力信号との論理積ｚ１１を出力する。論理積回路ＡＮＤ５３は、第１変換信号ｙ３の第１ビットｙ３１と、第１変換信号ｙ４の第１ビットｙ４１との論理積を出力する。論理積回路ＡＮＤ５４は、第１変換信号ｙ３の第１ビットｙ３１と、論理積回路ＡＮＤ５０の出力信号との論理積ｚ４１を出力する。論理積回路ＡＮＤ５５は、第１変換信号ｙ４の第１ビットｙ４１と、論理積回路ＡＮＤ５０の出力信号との論理積ｚ３１を出力する。
【０３０２】
第２ビット用論理演算回路６３ｂは、論理積回路ＡＮＤ５６、ＡＮＤ５７、ＡＮＤ５８、ＡＮＤ５９、ＡＮＤ６０、ＡＮＤ６１を含む。論理積回路ＡＮＤ５６は、第１変換信号ｙ１の第２ビットｙ１２と、第１変換信号ｙ２の第２ビットｙ２２との論理積を出力する。論理積回路ＡＮＤ５７は、第１変換信号ｙ１の第２ビットｙ１２と、論理積回路ＡＮＤ５９の出力信号との論理積ｚ２２を出力する。論理積回路ＡＮＤ５８は、第１変換信号ｙ２の第２ビットｙ２２と、論理積回路ＡＮＤ５９の出力信号との論理積ｚ１２を出力する。論理積回路ＡＮＤ５９は、第１変換信号ｙ３の第２ビットｙ３２と、第１変換信号ｙ４の第２ビットｙ４２との論理積を出力する。論理積回路ＡＮＤ６０は、第１変換信号ｙ３の第２ビットｙ３２と、論理積回路ＡＮＤ５６の出力信号との論理積ｚ４２を出力する。論理積回路ＡＮＤ６１は、第１変換信号ｙ４の第２ビットｙ４２と、論理積回路ＡＮＤ５６の出力信号との論理積ｚ３２を出力する。
【０３０３】
第３ビット用論理演算回路６３ｃは、論理積回路ＡＮＤ６２、ＡＮＤ６３、ＡＮＤ６４、ＡＮＤ６５、ＡＮＤ６６、ＡＮＤ６７を含む。論理積回路ＡＮＤ６２は、第１変換信号ｙ１の第３ビットｙ１３と、第１変換信号ｙ２の第３ビットｙ２３との論理積を出力する。論理積回路ＡＮＤ６３は、第１変換信号ｙ１の第３ビットｙ１３と、論理積回路ＡＮＤ６５の出力信号との論理積ｚ２３を出力する。論理積回路ＡＮＤ６４は、第１変換信号ｙ２の第３ビットｙ２３と、論理積回路ＡＮＤ６５の出力信号との論理積ｚ１３を出力する。論理積回路ＡＮＤ６５は、第１変換信号ｙ３の第３ビットｙ３３と、第１変換信号ｙ４の第３ビットｙ４３との論理積を出力する。論理積回路ＡＮＤ６６は、第１変換信号ｙ３の第３ビットｙ３３と、論理積回路ＡＮＤ６２の出力信号との論理積ｚ４３を出力する。論理積回路ＡＮＤ６７は、第１変換信号ｙ４の第３ビットｙ４３と、論理積回路ＡＮＤ６２の出力信号との論理積ｚ３３を出力する。
【０３０４】
以上のように、第１変換部４２が、複数個の入力信号の変換を同時に並列して行ない、ビット論理演算部６４が、第１変換信号の全ビットについて、ビット単位の論理演算を同時に並列して行なうので、第１順位推定を高速に行なえる。
【０３０５】
また、第４の実施形態の変形例２の第１順位推定装置によれば、第４の実施形態と同様に、入力された信号の中のうちの１個を除く信号の最小または最大である第１順位またはその近似値を複数個短時間に推定することができる。
【０３０６】
また、本変形例では、第４の実施形態よりも、ビット論理演算部の回路構成を簡易にすることができる。すなわち、図４４に示す第４の実施形態の各ビット論理演算部５３ａ〜５３ｄは、それぞれ４個の３入力の論理積回路を含んでいる。１個の３入力論理積回路は、２個の２入力の論理積回路に置き換えることができるので、図４４の各ビット論理演算部５３ａ〜５３ｄは、それぞれ４×２＝８個の２入力論理積回路を含む。一方、図４８に示す本変形例のビット論理演算部６３ａ〜６３ｄは、それぞれ６個の２入力の論理積回路を含み、第４の実施形態に比べて２個少ない。
【０３０７】
［第５の実施形態］
図４９は、この発明に従う復号装置を用いる通信システムの構成の一例を示す図である。図４９において、通信システムは、送信側において、送信情報に誤り訂正用の冗長ビットを付加して送信符号を生成する符号化器１と、この符号化器１からの（Ｋ＋Ｍ）（＝Ｎ）ビットの符号を所定の方式に従って変調して通信路３へ出力する変調器２とを含む。
【０３０８】
符号化器１は、Ｋビットの情報に対し、パリティ計算用の冗長ビットＭビットを付加して、（Ｋ＋Ｍ）ビットのＬＤＰＣ符号（低密度パリティ検査符号）を生成する。パリティ検査行列においては、行が冗長ビットに対応し、列が符号ビットに対応する。
【０３０９】
変調器２は、この通信路３の構成に応じて、振幅変調、位相変調、コード変調、周波数変調または直行周波数分割多重変調などの変調を行なう。たとえば、通信路３が、光ファイバの場合、変調器２においては、レーザダイオードの輝度を送信情報ビット値に応じて変更させることにより、光の強度変調（一種の振幅変調）を行なっている。たとえば、送信信号ビットが“０”の場合には、このレーザダイオードの発光強度を強くして“＋１”として送信し、また送信信号ビットが“１”の場合、レーザダイオードの発光強度を弱くして、“−１”に変換して送信する。
【０３１０】
受信部においては、通信路３を介して送信された変調信号に復調処理を施して、（Ｋ＋Ｍ）ビットのデジタル符号を復調する復調器４と、この復調器４からの（Ｋ＋Ｍ）ビットの符号にパリティ検査行列演算処理を施して元のＫビットの情報を再生する復号化器５が設けられる。
【０３１１】
復調器４は、この通信路３における送信形態に応じて復調処理を行なう。たとえば、振幅変調、位相変調、コード変調、周波数変調および直行周波数分割多重変調等の場合、復調器４において、振幅復調、位相復調、コード復調、および周波数復調等の処理が行なわれる。
【０３１２】
図５０は、通信路３が光ファイバの場合の変調器２および復調器４の出力信号の対応関係を一覧にして示す図である。図５０において、上述のように、通信路３が光ファイバの場合、変調器２においては、送信信号が“０”のときには、送信用のレーザダイオード（発光ダイオード）の発光強度を強くし、“１”を出力し、また送信信号ビットが“１”のときには、この発光強度を弱くしてビット“−１”を送信する。
【０３１３】
この通信路３における伝送損失等により、復調器４に伝達される光強度は、最も強い強度から最も弱い強度までの間のアナログ的な強度分布を有する。復調器４においては、この入力された光信号を量子化処理（アナログ／デジタル変換）を行なって、この受光レベルを検出する。図５０においては、８段階に受光レベルが量子化された場合の受信信号強度を示す。すなわち、受光レベルが信号“７”のときには、発光強度がかなり強く、受光レベルが“０”のときには、光強度がかなり弱い状態である。各受光レベルは、符号付き信号に対応づけられ、復調器４から出力される。この復調器４の出力は、受光レベルが“７”のときには信号“３”が出力され、受光レベルが“０”のときには、信号“−４”が出力される。したがってこの復調器４からは、１ビットの受信信号に対し、多値量子化された信号が出力される。
【０３１４】
復号化器５は、この復調器４から与えられた（Ｋ＋Ｍ）ビットの受信情報（各ビットは、多値情報を含む）を入力し、後に詳細に説明する、min-sum復号法に従ってＬＤＰＣパリティ検査行列を適用して、元のＫビットの情報を復元する。パリティ検査行列の行の数をＭ、列の数をＮ、行重みをＳとする。ここで、行重みとは、行方向の１の数である。
【０３１５】
図５１は、この発明に従う復号化器５の構成を概略的に示す図である。この図５１においては、復調器４および通信路３も併せて示す。復調器４は、通信路３から与えられた信号を復調する復調回路４ａと、この復調回路４ａにより生成されたアナログ復調信号をデジタル信号に変換するアナログ／デジタル変換回路４ｂを含む。このアナログ／デジタル変換回路４ｂの出力信号Ｘｎが復号化器５へ与えられる。この復号化器５へ与えられる信号Ｘｎは、Ｌ値（Ｌ≧２）の信号である。以下、信号Ｘｎは、多値量子化信号であるため、シンボルと称す。復号化器５は、この入力シンボルＸｎ系列に対してmin-sum復号法に従って復号処理を行なって符号ビットＣｎを生成する。
【０３１６】
復号化器５は、復調器４からの復調シンボルＸｎの対数尤度比λｎを生成する対数尤度比算出部１０と、パリティ検査行列の行処理を行なう行処理部１２と、パリティ検査行列の列処理を行なう列処理部１４と、対数尤度比算出部１０からの対数尤度比λｎと行処理部１２の出力ビット（外部値対数比）αｍｎとに従って符号を生成するループ判定部１６を含む。
【０３１７】
対数尤度比算出部１０は、この受信信号のノイズ情報と独立に、対数尤度比λｎを生成する。通常、ノイズ情報を考慮した場合、この対数尤度比λｎは、Ｘｎ／２×σで与えられる。ここで、σは、ノイズの分散を示す。しかしながら、本実施の形態１においては、この対数尤度比算出部１０は、バッファ回路または定数乗算回路で形成され、対数尤度比λｎは、Ｘｎ×ｆで与えられる。ここで、fは非ゼロの正の数である。このノイズ情報を
利用せずに、対数尤度比を算出することにより、回路構成が簡略化され、また計算処理も簡略化される。min-sum復号方法においては、検査行列の処理において、最小値を利用して演算を行なうため、信号処理において線形性が維持される。このため、ノイズ情報に従って出力信号を正規化するなどの処理は不要である。
【０３１８】
行処理部１２および列処理部１４は、それぞれ、次式（１）および（２）に従って、演算処理を行ない、パリティ検査行列の行の各要素についての処理（行処理）および列についての各要素についての処理（列処理）を実行する。行処理部１２において、列処理部１４から与えられる事前値対数比βｍｎと対数尤度比λｎとに従って外部値対数比αｍｎを更新する。
【数１】
2007335992.tif 000003
ここで、上式（１）および（２）それぞれにおいて、ｎ′∈Ａ（ｍ）＼ｎおよびｍ′∈Ｂ（ｎ）＼ｍは、自身を除く要素を意味する。外部値対数比αｍｎについては、ｎ′≠ｎであり、事前値対数比βｍｎについては、ｍ′≠ｍである。また、αおよびβの行列内の位置を示す添え字“ｍｎ”は、通常は下付文字で示されるが、本明細書においては、読みやすさのために、「横並びの文字」で示す。
【０３１９】
また、関数ｓｉｇｎ（ｘ）は、次式（３）で定義される。
【数２】
2007335992.tif 000004
ここで、関数ｍｉｎは、最小値を求める演算を示す。
【０３２０】
また、集合Ａ（ｍ）およびＢ（ｎ）は、２元Ｍ・Ｎ行列Ｈ＝［Ｈｍｎ］を復号対象のＬＤＰＣ符号の検査行列とした場合、集合［１，Ｎ］＝｛１，２，…，Ｎ｝の部分集合である。
Ａ（ｍ）＝｛ｎ：Ｈｍｎ＝１｝  …（４）
Ｂ（ｎ）＝｛ｍ：Ｈｍｎ＝１｝  …（５）
すなわち、部分集合Ａ（ｍ）は、検査行列Ｈの第ｍ行目において１が立っている列インデックスの集合を意味し、部分集合Ｂ（ｎ）は、検査行列Ｈの第ｎ列目において１が立っている行インデックスの集合を示す。
【０３２１】
ループ判定部１６は、これらの行処理部１２および列処理部１４における演算処理結果に基づいて、１次推定語を生成し、これらの１次推定語が符号語を構成しているかを検査する。このパリティ検査時において、シンドロームが“０”とならない場合には、再び処理を繰返し実行する。この処理の繰返し回数が所定値に到達すると、そのときの１次推定語を符号語として出力する。ループ判定部１６は、この行処理部１２で生成される外部値対数比αｍｎと対数尤度比算出部１０からの対数尤度比λｎとを用いて、複数の符号で構成される符号語を生成する。符号の数は、検査行列の列の数に対応する。
【０３２２】
これらの求められた外部値対数比αｍｎは、図５１に示す列処理部１４およびループ判定部１６へ供給される。
【０３２３】
列処理部１４は、先の式（２）において示された演算処理を行ない、検査行列Ｈの各行において生成された外部値対数比を用いて、自身を除く行以外の対応の列の“１”が立っている位置の外部値対数比を加算する。
【０３２４】
図５２は、行処理部１２の構成を表わす図である。
図５２を参照して、行処理部１２は、第１行処理部１８−１〜第Ｍ行処理部１８−Ｍを有する。
【０３２５】
図５３は、第ｍ行処理部１８−ｍの構成を示す図である。他の行の行処理部もこれと同様である。
【０３２６】
図５３を参照して、第ｍ行処理部１８−ｍは、加算部２０と、符号計算部２１と、絶対値計算部２２と、符号乗算部２３とを備える。
【０３２７】
加算部２１は、Ｓ個の信号｛βmn′：ｎ′はＨｍｎ′＝１を満たす、Ｓ個の異なる数である｝を受けて、それらと対数尤度比λn′とを加算して、加算結果｛（λn′＋βｍn′）：ｎ′はＨｍｎ′＝１を満たす、Ｓ個の異なる数である｝を出力する。
【０３２８】
符号計算部２１は、Ｓ個の信号｛（λn′＋βｍn′）：ｎ′はＨｍｎ′＝１を満たす、Ｓ個の異なる数である｝に基づいて、式（１）の符号部分（これをＳｍｎとする）の計算を行なう。
【０３２９】
絶対値計算部２２は、Ｓ個の信号｛（λn′＋βｍn′）：ｎ′はＨｍｎ′＝１を満たす、Ｓ個の異なる数である｝に基づいて、式（１）の絶対値部分（これをＲｍｎとする）の計算を行なう。
【０３３０】
符号乗算部２３は、符号計算部２１から出力されるＳｍｎが正のときに、絶対値計算部２２から出力されるＲｍｎの符号を正とした外部値対数比αｍｎを出力する。また、符号乗算部２３は、符号計算部２１から出力されるＳｍｎが負のときに、絶対値計算部２２から出力されるＲｍｎの符号を負とした外部値対数比αｍｎを出力する。
【０３３１】
図５４は、絶対値計算部２２の構成を表わす図である。
図５４を参照して、絶対値計算部２２は、絶対値出力部２４と、第１順位推定部２５とを有する。
【０３３２】
絶対値出力部２４は、加算部２１から出力されるＳ個の加算結果｛（λn′＋βｍn′）：ｎ′はＨｍｎ′＝１を満たす、Ｓ個の異なる数である｝の絶対値Ｒｍｎを出力する。
【０３３３】
第１順位推定部２５は、絶対値出力部２４から出力されるＳ個の信号｛｜λn′＋βｍn′｜：ｎ′はＨｍｎ′＝１を満たす、Ｓ個の異なる数である｝の中から、１つを除く（Ｓ−１）個の信号のうちの最小値をＳ個推定する。
【０３３４】
この第１順位推定部２５として、第４の実施形態またはその変形例で説明した第１順位推定装置を用いることができる。行重みＳが４の場合には図４３または図４７で表わされる第１順位推定装置をそのまま用いることができる。すなわち、入力信号ｘ１〜ｘ４を４個の信号｛｜λn′＋βｍn′｜：ｎ′はＨｍｎ′＝１を満たす、４個の異なる数である｝とみなし、出力される第２変換信号ｗ１〜ｗ４をＲm，n1、Ｒm,n2、Ｒm,n3、Ｒm,n3とみなせばよい。ただし、Ａ（ｍ）＝｛ｎ１，ｎ２，ｎ３，ｎ４｝とする。
【０３３５】
行重みＳが４以外の場合についても、図４３で表わされる第１順位推定装置を入力信号数および出力信号数について変形した装置を用いればよい。
【０３３６】
以上のように、第５の実施形態の復号装置によれば、Ｓ個の信号｛｜λn′＋βｍn′｜：ｎ′はＨｍｎ′＝１を満たす、Ｓ個の異なる数である｝の中の最小値を短時間に推定することができるので、低密度パリティ検査符号をmin-sum復号法で復号するのに要する時間を短くすることができる。
【０３３７】
（変形例１）
復号装置５０は、上述のように専用のハードウエア装置で実現されるものに限られない。外部から第１順位推定プログラムをメモリにインストールし、コンピュータがこのプログラムをメモリから読出して実行することによって、復号装置５０の機能を実現することとしてもよい。この場合、復号プログラムは、図５５のフローチャートで示される動作手順で動作する。
【０３３８】
まず、初期動作として、ループ回数および事前値対数比βｍｎの初期設定が行なわれる。このループ回数は、列処理部１４で生成された事前値対数比βｍｎを用いて再び行処理部１２で外部値対数比αｍｎを生成するループにおける演算回数を示す。このループ回数においては、最大値が予め定められる。事前値対数比βｍｎは、“０”に初期設定される（ステップＳＰ１）。
【０３３９】
次いで、受信シンボル系列に従って、対数尤度比算出部１０が対数尤度比λｎを算出する（ステップＳＰ２）。
【０３４０】
次に、行番号を表わすｍが１とされる（ステップＳＰ３）。
次に、行処理部１２の第１変換部４２は、４個の信号｛（λn′＋βｍn′）：ｎ′はＨｍｎ′＝１を満たす、４個の異なる数である｝を受けて、図２１に示す第１の変換テーブルに基づいて、それぞれを変換した４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４を生成する（ステップＳＰ４）。
【０３４１】
次に、行処理部１２のビット論理演算部５４は、第１変換部４２から出力される４個の第１変換信号ｙ１、ｙ２、ｙ３、ｙ４について、１個を除いた３個の第１変換信号のビット単位の論理積を、除く１個が相違するＮ種類について算出して、論理積信号ｚ１、ｚ２、ｚ３、ｚ４を生成する（ステップＳＰ５）。
【０３４２】
次に、行処理部１２の第２変換部５６は、ビット論理演算部５４から出力される論理積信号ｚ１、ｚ２、ｚ３、ｚ４を受けて、これらをそれぞれ図２２に示す第２の変換テーブルに基づいて変換して、４個の入力信号ｘ１、ｘ２、ｘ３、ｘ４のうちの１個を除いた第１順位の信号の値または第１順位の信号の近似値を表わす４個の第２変換信号ｗ１、ｗ２、ｗ３、ｗ４を生成して、式（１）の絶対値部分Ｒm，n1、Ｒm,n2、Ｒm,n3、Ｒm,n3として出力する。ただし、Ａ（ｍ）＝｛ｎ１，ｎ２，ｎ３，ｎ４｝とする（ステップＳＰ６）。
【０３４３】
次に、符号計算部２１は、４個の信号｛（λn′＋βｍn′）：ｎ′はＨｍｎ′＝１を満たす、４個の異なる数である｝に基づいて、式（１）の符号部分（これをＳｍｎとする）の計算を行なう（ステップＳＰ７）。
【０３４４】
次に、符号乗算部２３は、符号計算部２１から出力されるＳｍｎが正のときに、絶対値計算部２２の第２変換部５６から出力されるＲｍｎの符号を正とした外部値対数比αｍｎを出力する。また、符号乗算部２３は、符号計算部２１から出力されるＳｍｎが負のときに、絶対値計算部２２の第２変換部５６から出力されるＲｍｎの符号を負とした外部値対数比αｍｎを出力する（ステップＳＰ８）。
【０３４５】
次に、ｍ＝Ｍでない場合には（ステップＳＰ９でＮＯ）、ｍをインクリメントして、（ステップＳＰ１０）、ステップＳＰ４に戻る。
【０３４６】
次に、列処理部１４が、式（２）にしたがって、事前値対数比βｍｎを算出する（ステップＳＰ１１）。
【０３４７】
次に、ループ判定部１６は、こ対数尤度比λｎおよび外部値対数比αｍｎに従って、演算λｎ＋Σαｍｎを行なって推定受信語Ｑｎを算出する（ステップＳＰ１２）。ここで、総和Σは、部分集合Ｂ（ｎ）の要素ｍについて実行される。
【０３４８】
このステップＳＰ１２において算出された値Ｑｎの正負の符号を判定し（ステップＳＰ３）、１次推定符号Ｃｎを生成する（ステップＳＰ４）。この符号の正／負判定においては、たとえば、推定受信語Ｑｎが２の補数表示されているときには、最上位ビット（符号ビット）のビット値を見ることにより、正および負の判定を行なうことができる。
【０３４９】
１次推定符号Ｃｎが全て生成され、１次推定語（Ｃ１，・・・，ＣＮ）が生成されると、次いでパリティ検査を実行する（ステップＳＰ１５）。このパリティ検査においては、先の検査行列Ｈの転置行列を用いて、（Ｃ１，…，ＣＮ）・Ｈt＝０を計算する。この計算により、生成されるシンドロームが０であれば、１次推定語（Ｃ１，…，ＣＮ）を復号語として出力する（ステップＳＰ１８）。
【０３５０】
一方、この生成されたシンドロームが０と異なる場合には、ループ回数が最大値であるかの判定が行なわれる（ステップＳＰ１６）。すなわち、この１次推定語の生成回数をカウントし、その生成回数が所定の最大回数に到達すると、その符号についての算出をそれ以上をやめて、現在生成されている１次推定語を復号語として出力する（ステップＳＰ１８）。これにより、収束性の悪いノイジーな符号に対して、不必要に演算処理時間が要するのを防止する。
【０３５１】
ステップＳＰ１６において、ループ回数が最大値に到達していないと判定されると、このループ回数を１だけインクリメントして（ステップＳＰ１７）、再びステップＳＰ２からの処理を実行する。
【０３５２】
（変形例２）
本発明の実施形態では、第１順位推定部２５として、第４の実施形態またはその変形例で説明した第１順位推定装置を用いることとしたが、第１〜第３の実施形態およびその変形例の第１順位推定装置を用いることとしてもよい。
【０３５３】
ただし、これらの第１順位推定装置は、４個の入力信号が入力されて、４個の入力信号全部のうちの第１順位が１個出力される。したがって、第１順位推定部２５として用いるためには、４個の第１順位推定装置を用意する必要がある。
【０３５４】
すなわち、入力信号ｘ２、ｘ３、ｘ４が入力されて、これらの第１順位を出力する第１順位推定装置と、入力信号ｘ１、ｘ３、ｘ４が入力されて、これらの第１順位を出力する第１順位推定装置と、入力信号ｘ１、ｘ２、ｘ４が入力されて、これらの第１順位を出力する第１順位推定装置と、入力信号ｘ１、ｘ２、ｘ３が入力されて、これらの第１順位を出力する第１順位推定装置とが必要となる。
【０３５５】
このように、第１順位推定部２５として本発明の実施形態で説明したすべてのものを用いることができるが、第１順位推定部２５として、第１の実施形態およびその変形例以外を用いた場合には、第１変換信号のビット数が少ないので、装置の規模、または計算時間を短縮できる。また、これらを用いた場合には、入力信号が小さいときに、１個の第１変換信号に対応する入力信号の個数が少ないので、尤度を表わす入力信号の値が小さいときに細かい精度での推定が必要となるmin-sum復号法に適している。
【０３５６】
（全体を通じての変形例）
本発明は、上記の実施の形態に限定されるものではなく、たとえば以下のような変形例を含む。
【０３５７】
（１）  最大値の推定
本発明の実施形態で説明した例では、小さいものから第１順位である最小値またはその近似値を推定したが、これに限定されるものではなく、大きいものから第１順位である最大値またはその近似値を推定するものであってもよい。
【０３５８】
最大値またはその近似値を推定するように変形するためには、第１の変換テーブルにおいて、入力信号の順番を逆にし、かつ第２の変換テーブルにおいて、第２変換信号の順序を逆にすればよい。そして、第１変換部の具体的な構成は、この第１の変換テーブルで変換が行なわれるような回路に変形し、第２変換部の具体的な構成を、この第２の変換テーブルで変換が行なわれるような回路に変形すればよい。
【０３５９】
たとえば、図２の第１の変換テーブルにおいて、入力信号の「７」、「６」、「５」、「４」、「３」、「２」、「１」、「０」が、それぞれ、第１変換信号の「０００００００」、「００００００１」、「０００００１１」、「００００１１１」、「０００１１１１」、「００１１１１１」、「０１１１１１１」、「１１１１１１１」に対応するように変形し、図３の第２の変換テーブルにおいて、論理積信号の「０００００００」、「００００００１」、「０００００１１」、「００００１１１」、「０００１１１１」、「００１１１１１」、「０１１１１１１」、「１１１１１１１」が、それぞれ、第２変換信号の「７」、「６」、「５」、「４」、「３」、「２」、「１」、「０」に対応するように変形すればよい。
【０３６０】
（２）  尤度の高い信号を用いた復号
本発明の第５の実施形態およびその変形例では、尤度が最小の信号を用いて低密度パリティ検査符号を復号する方法を説明した。この方法は、誤りがありそうな信号から順に誤り訂正を行なうので、迅速に一定精度の誤り訂正を行なうことができる。
【０３６１】
しかしながら、尤度が高い所定個数の信号を用いて、誤り訂正を行なうようにしてもよい。例えばターボ符号や畳み込み符号では，BCJRアルゴリズム，ビタビ復号アルゴリズムなどがあり，尤度の高い信号を基に誤り訂正を行なうＭＡＰ（最大事後確率）アルゴリズムがある。これらの方法は、確実な信号を基準にして、誤りのありそうなところを訂正するので、より確実に誤りの訂正が可能となる。
【０３６２】
たとえば、LDPCの復号においても自身を除いて最も大きい信号を用いる復号法（これをmax-sum復号法と呼ぶことにする）を用いてもよい。
【０３６３】
max-sum復号法では、min-sum復号法における式（１）の最小値を出力する演算minが、最大値を出力する演算maxに置き換えられる。
【０３６４】
この変形例の具体的な構成は、第５の形態で説明したものと同様である。また、この変形例は、第５の実施形態の変形例１と同様にして、コンピュータで第１順位推定プログラムを実行することによっても実現できる。ただし、変形例（１）で説明したように、第１の変換テーブルにおいて、入力信号の順番を逆にし、かつ第２の変換テーブルにおいて、第２変換信号の順番を逆にすることが必要となる。
【０３６５】
（本願の発明をプログラムで実行する場合の具体的な効果）
一般に、複数の要素の最小値または最大値を検出する方法として、各要素の大小比較を行なうプログラムがある。このプログラムは、ＩＦ文などの分岐命令を必要とするが、分岐命令処理は、プログラムの実行クロック数を多く必要とする。そのため、このプログラムでは、最小値または最大値を検出するのに要する時間が長くなる。これに対して、本発明の実施形態のプログラムでは、最小値または最大値の探索をビット論理演算によって行なうため分岐命令が不要となる。その結果、本発明の実施形態のプログラムでは、大小比較を実施する一般的なプログラムよりも、短時間で最小値または最大値を検出することができる。
【０３６６】
今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【図面の簡単な説明】
【０３６７】
【図１】第１の実施形態の第１順位推定装置の構成を表わす図である。
【図２】第１の実施形態の第１の変換テーブルの例を表わす図である。
【図３】図２の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【図４】第１変換部の具体的な構成の一例を表わす図である。
【図５】ビット論理演算部の具体的な構成を表わす図である。
【図６】第２変換部の具体的な構成を表わす図である。
【図７】第１順位推定プログラムの処理手順を表わすフローチャートである。
【図８】第１順位推定装置の動作を具体例を説明するための図である。
【図９】第１の実施形態の変形例１の第１順位推定装置の構成を表わす図である。
【図１０】第１の実施形態の変形例１の第１の変換テーブルを表わす図である。
【図１１】図１０の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【図１２】ビット論理演算部の具体的な構成を表わす図である。
【図１３】第１の実施形態の変形例２の第１順位推定装置の構成を表わす図である。
【図１４】第１の実施形態の変形例２の第１の変換テーブルを表わす図である。
【図１５】図１４の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【図１６】第１順位推定装置の動作を具体例を説明するための図である。
【図１７】第１の実施形態の変形例３の第１順位推定装置の構成を表わす図である。
【図１８】第１の実施形態の変形例３の第１の変換テーブルを表わす図である。
【図１９】図１８の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【図２０】第２の実施形態の第１順位推定装置の構成を表わす図である。
【図２１】第２の実施形態の第１の変換テーブルの例を表わす図である。
【図２２】図２１の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【図２３】第１変換部の具体的な構成を表わす図である。
【図２４】ビット論理演算部の具体的な構成を表わす図である。
【図２５】第２変換部の具体的な構成を表わす図である。
【図２６】第１順位推定装置の動作を具体例を説明するための図である。
【図２７】第２の実施形態の変形例の第１順位推定装置の構成を表わす図である。
【図２８】第２の実施形態の変形例の第１の変換テーブルの例を表わす図である。
【図２９】図２８の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【図３０】第１変換部の具体的な構成を表わす図である。
【図３１】ビット論理演算部の具体的な構成を表わす図である。
【図３２】第２変換部の具体的な構成を表わす図である。
【図３３】第３の実施形態の第１順位推定装置の構成を表わす図である。
【図３４】第３の実施形態の第１の変換テーブルの例を表わす図である。
【図３５】図３４の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【図３６】第１変換部の具体的な構成を表わす図である。
【図３７】ビット論理演算部の具体的な構成を表わす図である。
【図３８】第２変換部の具体的な構成を表わす図である。
【図３９】第３の実施形態の変形例１の第１の変換テーブルの例を表わす図である。
【図４０】図３９の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【図４１】第３の実施形態の変形例２の第１の変換テーブルの例を表わす図である。
【図４２】図４１の第１の変換テーブルに対応する第２の変換テーブルを表わす図である。
【図４３】第４の実施形態の第１順位推定装置の構成を表わす図である。
【図４４】ビット論理演算部の具体的な構成を表わす図である。
【図４５】第２変換部の具体的な構成を表わす図である。
【図４６】第１順位推定装置の動作を具体例を説明するための図である。
【図４７】第４の実施形態の変形例２の第１順位推定装置の構成を表わす図である。
【図４８】ビット論理演算部の具体的な構成を表わす図である。
【図４９】通信システムの構成の一例を示す図である。
【図５０】通信路が光ファイバの場合の変調器２よび復調器の出力信号の対応関係を一覧にして示す図である。
【図５１】復号化器の構成を概略的に示す図である。
【図５２】行処理部の構成を表わす図である。
【図５３】第ｍ行処理部の構成を示す図である。
【図５４】絶対値計算部の構成を表わす図である。
【図５５】復号プログラムの処理手順を表わすフローチャートである。
【符号の説明】
【０３６８】
１  符号化器、２  変調器、３  通信路、４  復調器、４ａ  復調回路、４ｂ  アナログ／デジタル変調回路、５  復号化器、１０  対数尤度比算出部、１２  行処理部、１４  列処理部、１６  ループ判定部、１８−１  第１行処理部、１８−２  第２行処理部、１８−ｍ  第ｍ行処理部、１８−Ｍ  第Ｍ行処理部、２０  加算部、２１  符号計算部、２２  絶対値計算部、２３  符号乗算部、２４  絶対値出力部、２５  第１順位推定部、３０，４０，５０，６０，７０，１３０，１４０，２３０，３３０  第１順位推定装置、３１ａ，７１ａ  第１メモリ部（領域Ａ）、３１ｂ，７１ｂ  第１メモリ部（領域Ｂ）、３１ｃ，７１ｃ  第１メモリ部（領域Ｃ）、３１ｄ，７１ｄ  第１メモリ部（領域Ｄ）、３２，４２，７２，１３２，１４２，２３２，３３２  第１変換部、３４，４４，５４，６４，７４，１３４，１４４，２３４，３３４  ビット論理演算部、３５，７５  第２メモリ部、３６，４６，５６，７６，１３６，１４６，２３６，３３６  第２変換部、４１ａ，４１ｂ，４１ｃ，４１ｄ，１４１ａ，１４１ｂ，１４１ｃ，１４１ｄ，５５ａ，５５ｂ，５５ｃ，５５ｄ  変換回路、５３ａ，６３ａ  第１ビット用論理演算回路、５３ｂ，６３ｂ  第２ビット用論理演算回路、５３ｃ，６３ｃ  第３ビット用論理演算回路、５３ｄ，６３ｄ  第４ビット用論理演算回路、ＡＮＤ１〜ＡＮＤ１２，ＡＮＤ２０〜ＡＮＤ３１，ＡＮＤ４１，ＡＮＤ４２，ＡＮＤ５０〜ＡＮＤ６７，ＡＮＤ７１〜ＡＮＤ７４，ＡＮＤ８０〜ＡＮＤ８７  論理積回路、ＯＲ１〜ＯＲ８，ＯＲ１１〜ＯＲ１７，ＯＲ２１〜ＯＲ２８，ＯＲ３１〜ＯＲ３３  論理和回路、ＩＶ１，ＩＶ２，ＩＶ２１〜ＩＶ３２，ＩＶ４１〜ＩＶ４５，ＩＶ８０〜ＩＶ８７  インバータ。
【図１】
2007335992.tif 000005
【図２】
2007335992.tif 000006
【図３】
2007335992.tif 000007
【図４】
2007335992.tif 000008
【図５】
2007335992.tif 000009
【図６】
2007335992.tif 000010
【図７】
2007335992.tif 000011
【図８】
2007335992.tif 000012
【図９】
2007335992.tif 000013
【図１０】
2007335992.tif 000014
【図１１】
2007335992.tif 000015
【図１２】
2007335992.tif 000016
【図１３】
2007335992.tif 000017
【図１４】
2007335992.tif 000018
【図１５】
2007335992.tif 000019
【図１６】
2007335992.tif 000020
【図１７】
2007335992.tif 000021
【図１８】
2007335992.tif 000022
【図１９】
2007335992.tif 000023
【図２０】
2007335992.tif 000024
【図２１】
2007335992.tif 000025
【図２２】
2007335992.tif 000026
【図２３】
2007335992.tif 000027
【図２４】
2007335992.tif 000028
【図２５】
2007335992.tif 000029
【図２６】
2007335992.tif 000030
【図２７】
2007335992.tif 000031
【図２８】
2007335992.tif 000032
【図２９】
2007335992.tif 000033
【図３０】
2007335992.tif 000034
【図３１】
2007335992.tif 000035
【図３２】
2007335992.tif 000036
【図３３】
2007335992.tif 000037
【図３４】
2007335992.tif 000038
【図３５】
2007335992.tif 000039
【図３６】
2007335992.tif 000040
【図３７】
2007335992.tif 000041
【図３８】
2007335992.tif 000042
【図３９】
2007335992.tif 000043
【図４０】
2007335992.tif 000044
【図４１】
2007335992.tif 000045
【図４２】
2007335992.tif 000046
【図４３】
2007335992.tif 000047
【図４４】
2007335992.tif 000048
【図４５】
2007335992.tif 000049
【図４６】
2007335992.tif 000050
【図４７】
2007335992.tif 000051
【図４８】
2007335992.tif 000052
【図４９】
2007335992.tif 000053
【図５０】
2007335992.tif 000054
【図５１】
2007335992.tif 000055
【図５２】
2007335992.tif 000056
【図５３】
2007335992.tif 000057
【図５４】
2007335992.tif 000058
【図５５】
2007335992.tif 000059