(57)【特許請求の範囲】
【請求項１】
複数のデータのうち２以上の所定数ずつ逐次入力されるデータについて、絶対値が最も小さい第１最小値、及び、絶対値が２番目に小さい第２最小値を記憶する記憶部と、
前記所定数のデータ間の全ての大小関係を並列処理で比較する第１比較部と、
前記記憶された第１最小値と、前記所定数のデータの各々との大小関係、及び、前記記憶された第２最小値と、前記所定数のデータの各々との大小関係を、それぞれ比較する、前記第１比較部と並列処理される、前記所定数と同数の複数の第２比較部と、
前記第１比較部の比較結果と前記複数の第２比較部の比較結果とのパターンに基づいて、前記所定数のデータ、及び、前記記憶部に記憶された第１最小値及び第２最小値の中から、前記記憶部に記憶する新たな第１最小値及び新たな第２最小値を判定する判定部と、
を具備する最小値選択回路。
【請求項２】
前記所定数のデータの各々は、複数のグループの何れかに属し、
前記記憶部は、前記所定数のデータについて、前記複数のグループ毎の前記第１最小値及び前記第２最小値を記憶し、
前記複数の第２比較部の各々には、前記入力される各データが属するグループに対応する前記第１最小値及び前記第２最小値が前記記憶部から入力される、
請求項１に記載の最小値選択回路。
【請求項３】
ＬＤＰＣ符号の検査行列を用いて符号化されたデータを復号する復号器であって、
複数のデータ要素を含む入力データ又はシフタからのデータに対して、前記検査行列における列単位で列処理演算を行う列処理演算部と、
前記列処理演算後のデータに対して、前記検査行列における行単位で行処理演算を行う行処理演算部と、
を具備し、
前記行処理演算部は、前記行単位で、前記列処理演算により得られた列メッセージのデータから、絶対値が最も小さい第１最小値、及び、絶対値が２番目に小さい第２最小値を選択する最小値選択回路を具備し、
前記最小値選択回路は、
複数の前記列メッセージのデータのうち２以上の所定数ずつ逐次入力されるデータについて、絶対値が最も小さい第１最小値、及び、絶対値が２番目に小さい第２最小値を記憶する記憶部と、
前記所定数のデータ間の全ての大小関係を並列処理で比較する第１比較部と、
前記記憶された第１最小値と、前記所定数のデータの各々との大小関係、及び、前記記憶された第２最小値と、前記所定数のデータの各々との大小関係を、それぞれ比較する、前記第１比較部と並列処理される、前記所定数と同数の複数の第２比較部と、
前記第１比較部の比較結果と前記複数の第２比較部の比較結果とのパターンに基づいて、前記所定数のデータ、及び、前記記憶部に記憶された第１最小値及び第２最小値の中から、前記記憶部に記憶する新たな第１最小値及び新たな第２最小値を判定する判定部と、を具備する、
復号器。
【請求項４】
前記所定数のデータの各々は、前記検査行列の種類に応じて、複数のグループの何れかに属し、
前記記憶部は、前記所定数のデータについて、前記複数のグループ毎の前記第１最小値及び前記第２最小値を記憶し、
前記複数の第２比較部の各々には、前記入力される各データが属するグループに対応する前記第１最小値及び前記第２最小値が前記記憶部から入力される、
請求項３に記載の復号器。
【請求項５】
複数のデータのうち２以上の所定数ずつ逐次入力されるデータについて、絶対値が最も小さい第１最小値、及び、絶対値が２番目に小さい第２最小値を記憶し、
第１比較行程として、前記所定数のデータ間の全ての大小関係を並列処理で比較し、
前記第１比較行程と並列処理される第２比較行程として、前記記憶された第１最小値と、前記所定数のデータの各々との大小関係、及び、前記記憶された第２最小値と、前記所定数のデータの各々との大小関係を比較し、
前記第１比較工程の比較結果と前記第２比較工程の複数の比較結果とのパターンに基づいて、前記所定数のデータ、及び、前記記憶された第１最小値及び第２最小値の中から、新たな第１最小値及び新たな第２最小値を判定する、
最小値選択方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、最小値選択回路、復号器及び最小値選択方法に関する。
【背景技術】
【０００２】
シャノン限界に近いビット誤り率を実現でき、ＬＳＩ（Large Scale Integration）において復号器を実現できる誤り訂正符号化方法として、低密度パリティ検査（ＬＤＰＣ：Low Density Parity Check）符号が知られている。
【０００３】
ＬＤＰＣ符号は、IEEE802.11ac、IEEE802.11ad（無線通信）及びIEEE802.3an（有線通信）などの１Ｇｂｐｓを超える高速通信システムの規格において用いることが検討されている。
【０００４】
ＬＤＰＣ符号を用いた通信システムにおいて、受信機では、Ｍｉｎ−Ｓｕｍ復号法による復号処理が行われる。
【０００５】
Ｍｉｎ−Ｓｕｍ復号法では、行処理（チェックノード処理）と呼ばれる演算が行われる。具体的には、行処理では、２個以上のデータセットから値（絶対値）の大きさについて下位２個のデータを選択する演算が行われる。なお、選択されるデータ数は２個に限らず、データセットサイズより小さい数であればよい（選択されるデータ数として２個又は３個が設定されることが多い）。
【０００６】
以下の説明では、複数のデータのうち、絶対値が最も小さいデータを「第１最小値」と呼び、絶対値が２番目に小さいデータを「第２最小値」と呼ぶ。
【０００７】
第１最小値及び第２最小値を選択する最小値選択回路として、特許文献１には、木構造に配置された比較器に複数のデータが一度に入力され、第１最小値及び第２最小値を算出することが開示されている。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】米国特許第８２３４３２０号明細書
【発明の概要】
【発明が解決しようとする課題】
【０００９】
１Ｇｂｐｓを超えるような高速通信を行う受信機では、受信機での処理遅延及び消費電力を低減させることが望まれる。しかしながら、特許文献１に開示された最小値選択回路では、縦列接続された多数の比較器を必要とするので、最小値選択回路の処理遅延が大きくなるとともに、回路規模が増大し、消費電力が増大する。
【００１０】
本開示の一態様の目的は、遅延を低減するとともに、回路規模を小さくでき、消費電力を低減させることができる最小値選択回路、復号器及び最小値選択方法を提供することである。
【課題を解決するための手段】
【００１１】
本開示の一態様に係る最小値選択回路は、複数のデータのうち２以上の所定数ずつ逐次入力されるデータについて、絶対値が最も小さい第１最小値、及び、絶対値が２番目に小さい第２最小値を記憶する記憶部と、前記所定数のデータ間の大小関係を比較する第１比較部と、前記記憶された第１最小値と、前記所定数のデータの各々との大小関係、及び、前記記憶された第２最小値と、前記所定数のデータの各々との大小関係を、それぞれ比較する、前記所定数と同数の複数の第２比較部と、前記第１比較部の比較結果と前記複数の第２比較部の比較結果とのパターンに基づいて、前記所定数のデータ、及び、前記記憶部に記憶された第１最小値及び第２最小値の中から、前記記憶部に記憶する新たな第１最小値及び新たな第２最小値を判定する判定部と、を具備する構成を採る。
【００１２】
本開示の一態様に係る復号器は、ＬＤＰＣ符号の検査行列を用いて符号化されたデータを復号する復号器であって、複数のデータ要素を含む入力データ又はシフタからのデータに対して、前記検査行列における列単位で列処理演算を行う列処理演算部と、前記列処理演算後のデータに対して、前記検査行列における行単位で行処理演算を行う行処理演算部と、を具備し、前記行処理演算部は、前記行単位で、前記列処理演算により得られた列メッセージのデータから、絶対値が最も小さい第１最小値、及び、絶対値が２番目に小さい第２最小値を選択する最小値選択回路を具備し、前記最小値選択回路は、複数の前記列メッセージのデータのうち２以上の所定数ずつ逐次入力されるデータについて、絶対値が最も小さい第１最小値、及び、絶対値が２番目に小さい第２最小値を記憶する記憶部と、前記所定数のデータ間の大小関係を比較する第１比較部と、前記記憶された第１最小値と、前記所定数のデータの各々との大小関係、及び、前記記憶された第２最小値と、前記所定数のデータの各々との大小関係を、それぞれ比較する、前記所定数と同数の複数の第２比較部と、前記第１比較部の比較結果と前記複数の第２比較部の比較結果とのパターンに基づいて、前記所定数のデータ、及び、前記記憶部に記憶された第１最小値及び第２最小値の中から、前記記憶部に記憶する新たな第１最小値及び新たな第２最小値を判定する判定部と、を具備する構成を採る。
【００１３】
本開示の一態様に係る最小値選択方法は、複数のデータのうち２以上の所定数ずつ逐次入力されるデータについて、絶対値が最も小さい第１最小値、及び、絶対値が２番目に小さい第２最小値を記憶し、前記所定数のデータ間の大小関係を比較し、前記記憶された第１最小値と、前記所定数のデータの各々との大小関係、及び、前記記憶された第２最小値と、前記所定数のデータの各々との大小関係を比較し、前記第１比較工程の比較結果と前記第２比較工程の複数の比較結果とのパターンに基づいて、前記所定数のデータ、及び、前記記憶された第１最小値及び第２最小値の中から、新たな第１最小値及び新たな第２最小値を判定する。
【発明の効果】
【００１４】
本開示の一態様によれば、遅延を低減するとともに、回路規模を小さくでき、消費電力を低減させることができる。
【図面の簡単な説明】
【００１５】
【図１】木構造に配置された比較器を有する最小値選択回路の構成を示すブロック図
【図２】実施の形態１に係る最小値選択回路の構成を示すブロック図
【図３】実施の形態１に係る動作モードの一例を示す図
【図４】実施の形態１に係る第１選択比較部１０７の動作を示す図
【図５】実施の形態１に係る第２選択比較部１０８の動作を示す図
【図６】実施の形態１に係る判定部１０９の動作を示す真理値表
【図７】実施の形態２に係る最小値選択回路の構成を示すブロック図
【図８】実施の形態２に係る動作モードの一例を示す図
【図９】実施の形態２に係る第１選択比較部２０２の動作を示す図
【図１０】実施の形態２に係る第２選択比較部２０３の動作を示す図
【図１１】実施の形態２に係る第３選択比較部２０４の動作を示す図
【図１２】実施の形態２に係る第４選択比較部２０５の動作を示す図
【図１３】実施の形態２に係る判定部２０６の動作を示す真理値表
【図１４】実施の形態２に係る判定部２０６の動作を示す真理値表
【図１５】実施の形態２に係る判定部２０６の動作を示す真理値表
【図１６】実施の形態２に係る判定部２０６の動作を示す真理値表
【図１７】実施の形態２に係る判定部２０６の動作を示す真理値表
【図１８】実施の形態３に係る最小値選択回路の構成を示すブロック図
【図１９】実施の形態３に係る前処理部３０１の構成を示すブロック図
【図２０】実施の形態３に係る最小値選択部３０２の構成を示すブロック図
【図２１】実施の形態３に係る動作モードcase 5における入力データの一例を示す図
【図２２】実施の形態４に係るＬＤＰＣ復号器の構成を示すブロック図
【図２３】実施の形態４に係る検査行列の一例を示す図
【図２４】実施の形態４に係る各列処理演算器４０３への列グループの割当例を示す図
【図２５】実施の形態４に係る各行処理演算器４０６への行グループの割当例を示す図
【図２６】実施の形態４に係る行処理演算器４０６−１がｔ＝１において処理するサブマトリックスを示す図
【図２７】実施の形態４に係る各行処理演算器４０６への行グループの割当例を示す図
【図２８】実施の形態４に係る各行処理演算器４０６への行グループの割当例を示す図
【図２９】実施の形態４に係るデータ転送部４０５の動作例を示す図
【図３０】実施の形態４に係る行処理演算器４０６−１の構成を示すブロック図
【図３１】実施の形態４に係るデータ転送部４０８の動作例を示す図
【図３２】実施の形態５に係るＬＤＰＣ復号器の構成を示すブロック図
【図３３】実施の形態５に係る各行処理演算器５０６への行グループの割当例を示す図
【図３４】実施の形態５に係る各行処理演算器５０６への行グループの割当例を示す図
【図３５】実施の形態５に係る各行処理演算器５０６への行グループの割当例を示す図
【図３６】実施の形態５に係る行処理演算と従来技術の行処理演算との比較の説明に供する図
【発明を実施するための形態】
【００１６】
［本開示の一態様をするに至った経緯］
図１は、特許文献１に基づく木構造で配置された比較器を有する最小値選択回路の構成を示すブロック図である。図１に示す最小値選択回路は、一例として、入力データ数を１６とし、１６個の入力データから第１最小値及び第２最小値を算出する回路である。
【００１７】
図１に示す「4 to 2」回路は、４個の入力データに対する第１最小値及び第２最小値を算出する。つまり、図１に示す最小値選択回路は、「4 to 2」回路を木構造で３段備えることにより、１６個の入力データから第１最小値及び第２最小値を算出する。
【００１８】
また、図１に示す最小値選択回路では、高速な動作クロックによって動作させるために、木構造の「4 to 2」回路１段につき、１つのパイプラインレジスタが挿入されている。これは、パイプライン１段につき、比較器が１段となるようにした構成であると言える。
【００１９】
なお、「4 to 2」回路には、比較器の他にセレクタ及び制御回路なども含まれるが、これらは比較器よりも遅延が小さいので、ここでは比較器の段数に基づいてパイプライン構成が決定されている。
【００２０】
図１に示す最小値選択回路では、パイプラインが３段であるので、２クロックサイクルのパイプライン遅延が追加される。すなわち、図１に示す回路を用いて１６個の入力データから第１最小値及び第２最小値を算出するためには、３クロックサイクルを要する。
【００２１】
一方、図１に示す最小値選択回路において、１６個の入力データが４セット順次入力される場合、パイプライン動作により６クロックサイクルを要する。すなわち、Ｎセットの入力データが順次入力される場合、パイプライン動作により（Ｎ＋２）クロックサイクルを要する。
【００２２】
このように、図１に示す構成では、パイプライン動作による遅延（パイプライン遅延）によって処理遅延が増加するという課題がある。また、図１に示すようなパイプラインレジスタの追加による回路規模の増大及び消費電力の増加を招いてしまう。
【００２３】
本開示に係る一態様は、かかる課題を解決するものであって、最小値選択回路において、処理遅延を低減するとともに、回路規模及び消費電力を削減することを目的とする。
【００２４】
以下、本開示の一態様に係る実施の形態について、図面を参照して詳細に説明する。
【００２５】
（実施の形態１）
図２は、本実施の形態に係る最小値選択回路の構成を示すブロック図である。
【００２６】
図２に示す最小値選択回路１００は、複数のデータの中から絶対値が最も小さい第１最小値、及び、絶対値が２番目に小さい第２最小値を選択する。また、最小値選択回路１００には、複数のデータが２個のデータ（図２ではＤ１，Ｄ２）ずつ逐次入力される。
【００２７】
以下の説明では、入力データの１セットのサイズが１６である場合について説明する。ただし入力データの１セットのサイズは１６に限らず、その他のサイズでもよい。
【００２８】
例えば、最小値選択回路１００は、図３に示す４つの動作モード（case 1〜case 4）を有する。
【００２９】
case 1では、最小値選択回路１００は、１６個のデータの中から第１最小値（Xmin1）及び第２最小値（Xmin2）を選択する。最小値選択回路１００には、ステップ（クロックサイクル。ｔ＝１〜８）毎に２つのデータが入力される。すなわち、case 1では、８ステップで１つのデータセットに対する処理が完了する。
【００３０】
case 3では、１つのデータセットに含まれる１６個のデータが２つのグループに分けられている。図３では、奇数番目のデータを第１グループとし、偶数番目のデータを第２グループとしている。最小値選択回路１００は、第１グループの第１最小値（Xmin1）及び第２最小値（Xmin2）、及び、第２groupの第１最小値（Ymin1）及び第２最小値（Ymin2）をそれぞれ選択する。最小値選択回路１００には、ステップ（ｔ＝１〜８）毎に各グループに属するデータが１つずつ入力される。
【００３１】
case 2及びcase 4では、１６個のデータが、case 1及びcase 3の各データが属するグループを反転させたグループに分けられている。
【００３２】
また、１つのデータセットにおけるグループ分けは不規則であってもよい。例えば、図３に示す「実際の例」の各ステップにおいて、最小値選択回路１００には、上述したcase 1〜case 4の何れかにおけるデータの組み合わせが入力される。
【００３３】
例えば、最小値選択回路１００は、ＬＤＰＣ符号を用いたＭｉｎ−Ｓｕｍ復号法による復号処理のうち、行処理（チェックノード処理）に用いられる（詳細については実施の形態３，４において詳述する）。この場合、上述した入力データの組み合わせは、ＬＤＰＣ復号に使用される検査行列の構成によって決まる。
【００３４】
図２に示す最小値選択回路１００は、選択部１０１，１０２、記憶部１０３，１０４、総当たり比較部１０５、動作モード指示部１０６、第１選択比較部１０７、第２選択比較部１０８、判定部１０９を含む構成を採る。
【００３５】
図２では、一例として、図３に示すｔ＝１のステップにおいて最小値選択回路１００にデータＤ１，Ｄ２が入力される場合を示す。
【００３６】
また、図２では、一例として、データＤ１，Ｄ２を含む複数のデータ（１つのデータセットを構成するデータ）は、２つのグループ（第１グループ，第２グループ）のいずれかに属している。
【００３７】
選択部１０１は、判定部１０９から入力される判定結果に基づいて、入力データＤ１，Ｄ２、及び、記憶部１０３から入力される第１最小値Xmin1、第２最小値Xmin2のうち、２つの値を選択する。選択される２つの値は、Ｄ１，Ｄ２が入力された時点における第１グループの最も小さい値（絶対値）である新たな第１最小値Xmin1、及び、２番目に小さい値（絶対値）である新たな第２最小値Xmin2である。選択部１０１は、選択した２つの値を記憶部１０３へ出力する。
【００３８】
選択部１０２は、判定部１０９から入力される判定結果に基づいて、入力データＤ１，Ｄ２、及び、記憶部１０４から入力される第１最小値候補Ymin1、第２最小値候補Ymin2のうち、２つの値を選択する。選択される２つの値は、Ｄ１，Ｄ２が入力された時点における第２グループの最も小さい値（絶対値）である新たな第１最小値候補Ymin1、及び、２番目に小さい値（絶対値）である新たな第２最小値候補Ymin2である。選択部１０２は、選択した２つの値を記憶部１０４へ出力する。
【００３９】
記憶部１０３は、選択部１０１から入力される第１グループの第１最小値Xmin1及び第２最小値Xmin2を記憶する。具体的には、第１最小値Xmin1は、第１最小値記憶部１３１に記憶され、第２最小値Xmin2は、第２最小値記憶部１３２に記憶される。また、記憶部１０３は、記憶しているXmin1、Xmin2を選択部１０１、第１選択比較部１０７及び第２選択比較部１０８へ出力する。
【００４０】
記憶部１０４は、選択部１０２から入力される第２グループの第１最小値Ymin1及び第２最小値Xmin2を記憶する。具体的には、第１最小値Ymin1は、第１最小値記憶部１４１に記憶され、第２最小値Ymin2は、第２最小値記憶部１４２に記憶される。また、記憶部１０４は、記憶しているYmin1、Ymin2を選択部１０２、第１選択比較部１０７及び第２選択比較部１０８へ出力する。
【００４１】
つまり、記憶部１０３及び記憶部１０４において、複数のグループ毎の第１最小値及び第２最小値がそれぞれ記憶される。
【００４２】
最小値選択回路１００は、１つのデータセット（例えば、１６個のデータ）に対する処理の完了時に記憶部１０３又は記憶部１０４に記憶されている値（Xmin1、Xmin2、Ymin1又はYmin2）を当該データセットの最終的な第１最小値及び第２最小値として出力する。換言すると、記憶部１０３，１０４は、複数のデータが所定数（ここでは２個）のデータ毎に逐次入力される度に、最小値選択回路１００に入力されたデータについて、第１最小値及び第２最小値を更新して記憶する。
【００４３】
総当たり比較部１０５は、複数のデータのうち逐次入力される２以上の所定数のデータ間の大小関係を比較する第１比較部として機能する。総当たり比較部１０５は、同時（ステップ毎）に入力される所定数のデータ（図２ではＤ１，Ｄ２）の全ての組み合わせについて並列に（同時に）大小関係の比較を行う。例えば、総当たり比較部１０５は、Ｄ１＜Ｄ２の場合には比較結果Ｃ１２＝１を判定部１０９に出力し、Ｄ１≧Ｄ２の場合には比較結果Ｃ１２＝０を判定部１０９に出力する。図２では、最小値選択回路１００に同時に入力されるデータが２つであるので、総当たり比較部１０５は、１つの比較器を有する。例えば、最小値選択回路１００に同時に入力されるデータが４つである場合には、総当たり比較部１０５は６個の比較器を有する。
【００４４】
動作モード指示部１０６は、現ステップの動作モードが図３に示す動作モード（case 1〜case 4）の何れであるかを第１選択比較部１０７、第２選択比較部１０８及び判定部１０９に指示する。
【００４５】
最小値選択回路１００には、最小値選択回路１００に同時に入力されるデータ数（図２では２個）と同数の選択比較部（図２では、第１選択比較部１０７及び第２選択比較部１０８）が備えられる。各選択比較部は同時に入力されるデータの各々に対応する。すなわち、第１選択比較部１０７及び第２選択比較部１０８は、複数のデータのうち逐次入力される２以上の所定数のデータと同数の複数の第２比較部として機能する。
【００４６】
また、第１選択比較部１０７及び第２選択比較部１０８は、各々に対応するデータが属するグループに対応する第１最小値及び第２最小値を記憶部１０３又は記憶部１０４から選択し、選択された第１最小値及び第２最小値と、各々に対応するデータとを比較する。
【００４７】
つまり、第１選択比較部１０７は、記憶部１０３又は記憶部１０４に記憶された第１最小値及び第２最小値の各々とデータＤ１との比較を行う選択比較部である。また、第２選択比較部１０８は、記憶部１０３又は記憶部１０４に記憶された第１最小値及び第２最小値の各々とデータＤ２との比較を行う選択比較部である。
【００４８】
第１選択比較部１０７は、選択部１７１，１７２、及び、比較器１７３，１７４を備える。
【００４９】
第１選択比較部１０７において選択部１７１は、動作モード指示部１０６から指示される動作モードに従って、記憶部１０３から入力される第１グループの第１最小値Xmin1及び記憶部１０４から入力される第２グループの第１最小値Ymin1のうちいずれかを選択する。同様に、選択部１７２は、動作モード指示部１０６から指示される動作モードに従って、記憶部１０３から入力される第１グループの第２最小値Xmin2及び記憶部１０４から入力される第２グループの第２最小値Ymin2のうちいずれかを選択する。
【００５０】
そして、比較器１７３は、選択部１７１で選択されたデータ（以下、Zmin1とする）とデータＤ１とを比較し、比較結果Ｃｚ１を判定部１０９へ出力する。同様に、比較器１７４は、選択部１７２で選択されたデータ（以下、Zmin2とする）とデータＤ１とを比較し、比較結果Ｃｚ２を判定部１０９へ出力する。
【００５１】
例えば、第１選択比較部１０７は、Zmin1（又はZmin2）＜Ｄ１の場合には比較結果Ｃｚ１（又はＣｚ２）＝１を出力し、Zmin1（又はZmin2）≧Ｄ１の場合には比較結果Ｃｚ１（又はＣｚ２）＝０を出力する。
【００５２】
図４Ａ及び図４Ｂは、第１選択比較部１０７における動作例を示す。
【００５３】
図４Ａは、動作モード指示部１０６からcase 1又はcase 3が指示された場合の第１選択比較部１０７の動作を示し、図４Ｂは、動作モード指示部１０６からcase 2又はcase 4が指示された場合の第１選択比較部１０７の動作を示す。
【００５４】
図４Ａに示すように、動作モードがcase 1又はcase 3の場合、選択部１７１はXmin1をZmin1として選択し、選択部１７２はXmin2をZmin2として選択する。そして、比較器１７３はXmin1とデータＤ１とを比較し、比較器１７４はXmin2とデータＤ１とを比較する。
【００５５】
一方、図４Ｂに示すように、動作モードがcase 2又はcase 4の場合、選択部１７１はYmin1をZmin1として選択し、選択部１７２はYmin2をZmin2として選択する。そして、比較器１７３はYmin1とデータＤ１とを比較し、比較器１７４はYmin2とデータＤ１とを比較する。
【００５６】
図２に戻り、第２選択比較部１０８は、選択部１８１，１８２、及び、比較器１８３，１８４を備える。
【００５７】
第２選択比較部１０８において、選択部１８１は、動作モード指示部１０６から指示される動作モードに従って、記憶部１０３から入力される第１グループの第１最小値Xmin1及び記憶部１０４から入力される第２グループの第１最小値Ymin1のうちいずれかを選択する。同様に、選択部１８２は、動作モード指示部１０６から指示される動作モードに従って、記憶部１０３から入力される第１グループの第２最小値Xmin2及び記憶部１０４から入力される第２グループの第２最小値Ymin2のうちいずれかを選択する。
【００５８】
そして、比較器１８３は、選択部１８１で選択されたデータ（以下、Wmin1とする）とデータＤ２とを比較し、比較結果Ｃｗ１を判定部１０９へ出力する。同様に、比較器１８４は、選択部１８２で選択されたデータ（以下、Wmin2とする）とデータＤ２とを比較し、比較結果Ｃｗ２を判定部１０９へ出力する。
【００５９】
例えば、第２選択比較部１０８は、Wmin1（又はWmin2）＜Ｄ２の場合には比較結果Ｃｗ１（又はＣｗ２）＝１を出力し、Wmin1（又はWmin2）≧Ｄ２の場合には比較結果Ｃｗ１（又はＣｗ２）＝０を出力する。
【００６０】
図５Ａ及び図５Ｂは、第２選択比較部１０８における動作例を示す。
【００６１】
図５Ａは、動作モード指示部１０６からcase 1又はcase 4が指示された場合の第２選択比較部１０８の動作を示し、図５Ｂは、動作モード指示部１０６からcase 2又はcase 3が指示された場合の第２選択比較部１０８の動作を示す。
【００６２】
図５Ａに示すように、動作モードがcase 1又はcase 4の場合、選択部１８１はXmin1をWmin1として選択し、選択部１８２はXmin2をWmin2として選択する。そして、比較器１８３はXmin1とデータＤ２とを比較し、比較器１８４はXmin2とデータＤ２とを比較する。
【００６３】
一方、図５Ｂに示すように、動作モードがcase 2又はcase 3の場合、選択部１８１はYmin1をWmin1として選択し、選択部１８２はYmin2をWmin2として選択する。そして、比較器１８３は、Ymin1とデータＤ２とを比較し、比較器１８４は、Ymin2とデータＤ２とを比較する。
【００６４】
図２に戻り、判定部１０９は、動作モード１０６から入力される動作モード、総当たり比較部１０５から入力される比較結果Ｃ１２、第１選択比較部１０７から入力される比較結果Ｃｚ１、Ｃｚ２、及び、第２選択比較部１０８から入力される比較結果Ｃｗ１、Ｃｗ２に基づいて、記憶部１０３又は記憶部１０４に記憶された第１最小値（Xmin1、Ymin1）及び第２最小値（Xmin2、Ymin2）を更新する値を判定する。
【００６５】
すなわち、判定部１０９は、データＤ１，Ｄ２、及び、記憶部１０３又は記憶部１０４に記憶された第１最小値及び第２最小値の中から、記憶部１０３又は記憶部１０４に記憶する新たな第１最小値及び新たな第２最小値を判定する。
【００６６】
図６は、判定部１０９の動作を表す真理値表（比較結果のパターン）を示す。図６Ａ〜図６Ｄは、case 1〜case 4の場合の真理値表をそれぞれ示す。
【００６７】
なお、図６に示す真理値表には、最小値選択回路１００において起こりえない条件（比較結果の組み合わせ）は示されていない。一例として、比較結果（Ｃｚ１，Ｃｚ２，Ｃｗ１，Ｃｗ２，Ｃ１２）が（0,1,1,1,1）である場合とは、Xmin1≧Ｄ１であり、Xmin2＜Ｄ１である場合に相当する。すなわち、Xmin1≧Ｄ１＞Xmin2の関係となり、第１最小値（Xmin1）と第２最小値（Xmin2）との関係に矛盾が生じる。よって、組み合わせ（0,1,1,1,1）は最小値選択回路１００において起こりえない条件である。
【００６８】
また、図６Ｃ及び図６Ｄにおいて、「＊」は出力結果に影響を与えない値（ドントケア）を示す。
【００６９】
case 1（図６Ａ）の場合、記憶部１０３に記憶されるXmin1、Xmin2が更新対象であり、記憶部１０４に記憶されるYmin1、Ymin2は更新されない。
【００７０】
例えば、比較結果（Ｃｚ１，Ｃｚ２，Ｃｗ１，Ｃｗ２，Ｃ１２）のパターンが（0,0,0,0,0）である場合（図６Ａに示す条件番号１２の場合）、判定部１０９は、入力データＤ２を新たなXmin1とし、入力データＤ１を新たなXmin2とし、判定結果を選択部１０１へ出力する。
【００７１】
より詳細には、case 1では、Ｃｚ１＝０の場合、Xmin1≧Ｄ１であり、Ｃｚ１＝０の場合、Xmin2≧Ｄ１であり、Ｃｗ１＝０の場合、Xmin1≧Ｄ２であり、Ｃｗ２＝０の場合、Xmin2≧Ｄ２であり、Ｃ１２＝０の場合、Ｄ１≧Ｄ２である。よって、この場合、Ｄ１，Ｄ２，Xmin1，Xmin2は、Xmin2＞Xmin1≧Ｄ１≧Ｄ２の関係となる。よって、判定部１０９は、Ｄ２、Ｄ１が新たなXmin1,Xmin2であると判定する。
【００７２】
同様に、比較結果（Ｃｚ１，Ｃｚ２，Ｃｗ１，Ｃｗ２，Ｃ１２）のパターンが（1,1,1,1,1）である場合（図６Ａに示す条件番号１の場合）、判定部１０９は、Xmin1を新たなXmin1とし、Xmin2を新たなXmin2とし、判定結果を選択部１０１へ出力する。
【００７３】
より詳細には、case 1では、Ｃｚ１＝１の場合、Xmin1＜Ｄ１であり、Ｃｚ１＝１の場合、Xmin2＜Ｄ１であり、Ｃｗ１＝１の場合、Xmin1＜Ｄ２であり、Ｃｗ２＝１の場合、Xmin2＜Ｄ２であり、Ｃ１２＝１の場合、Ｄ１＜Ｄ２である。よって、この場合、Ｄ１，Ｄ２，Xmin1，Xmin2は、Ｄ２＞Ｄ１＞Xmin2＞Xmin1の関係となる。よって、判定部１０９は、Xmin1、Xmin2が新たなXmin1,Xmin2であると判定する。
【００７４】
なお、記憶部１０３に記憶されるXmin1及びXmin2が更新されない場合、判定部１０９は、記憶部１０３に対して更新指示（イネーブル信号）を無効（negate）としてもよい。また、記憶部１０４に記憶されるYmin1及びYmin2が更新されない場合、判定部１０９は、記憶部１０４に対して更新指示（イネーブル信号）を無効（negate）としてもよい。このとき、記憶部１０３又は記憶部１０４は、イネーブル付きフリップフロップ又はクロックイネーブル付きフリップフロップ又はライトイネーブル付きＲＡＭなどを用いてよい。
【００７５】
判定部１０９は、case 1の他の条件番号、及び、他のcaseについても同様にして新たな第１最小値（Xmin1,Ymin1）及び新たな第２最小値（Xmin2,Ymin2）を判定する。
【００７６】
ただし、case 2（図６Ｂ）の場合、記憶部１０４に記憶されるYmin1、Ymin2更新対象であり、記憶部１０３に記憶されるXmin1、Xmin2は更新されない。
【００７７】
また、case 3（図６Ｃ）の場合、比較結果Ｃｚ１及びＣｚ２の値（つまり、Ｄ１と第１グループとの比較結果）によって記憶部１０３における更新対象のデータが決定され（条件番号Ｚ１〜Ｚ３）、比較結果Ｃｗ１及びＣｗ２の値（つまり、Ｄ２と第２グループとの比較結果）によって記憶部１０４における更新対象のデータが決定される（条件番号Ｗ１〜Ｗ３）。
【００７８】
例えば、比較結果（Ｃｚ１，Ｃｚ２，Ｃｗ１，Ｃｗ２，Ｃ１２）のパターンが（0,0,0,0,0）である場合（図６Ｃに示す条件番号Ｚ３かつＷ３の場合）、判定部１０９は、入力データＤ１を新たなXmin1とし、記憶部１０３に記憶されているデータXmin1を新たなXmin2とし、判定結果を選択部１０１へ出力する。同時に、判定部１０９は、入力データＤ２を新たなYmin1とし、記憶部１０４に記憶されているデータYmin1を新たなYmin2とし、判定結果を選択部１０２へ出力する。
【００７９】
また、case 4（図６Ｄ）の場合、比較結果Ｃｚ１及びＣｚ２の値（つまり、Ｄ１と第２グループとの比較結果）によって記憶部１０４における更新対象のデータが決定され（条件番号Ｚ１〜Ｚ３）、比較結果Ｃｗ１及びＣｗ２の値（つまり、Ｄ２と第１グループとの比較結果）によって記憶部１０３における更新対象のデータが決定される（条件番号Ｗ１〜Ｗ３）。
【００８０】
以上のように、本実施の形態では、最小値選択回路１００は、複数のデータ入力（図２では２個のデータ入力）を同時に受け付ける入力端子、及び、入力されるデータに対して大小関係を総当たりで比較する総当たり比較部１０５を備える。また、最小値選択回路１００では、選択比較部（図２では第１選択比較部１０７及び第２選択比較部１０８）は、同時に入力されるデータ数と同数備えられる。
【００８１】
そして、最小値選択回路１００において、第１選択比較部１０７及び第２選択比較部１０８は、動作モード（つまり、データのグループ分け）に基づいて、記憶部１０３又は記憶部１０４に記憶されている第１最小値及び第２最小値の組の何れかを選択して、選択した第１最小値及び第２最小値の各々と入力データとの比較を行う。
【００８２】
これにより、最小値選択回路１００は、逐次的に入力されるデータについて、複数のグループ（第１グループ及び第２グループ）毎に第１最小値及び第２最小値を求めることができる。また、最小値選択回路１００に入力される複数のデータの各々が属するグループが時々刻々変わる場合でも、最小値選択回路１００は、複数のグループ毎に第１最小値及び第２最小値を求めることができる。
【００８３】
また、最小値選択回路１００では、入力データとの比較対象となる第１最小値及び第２最小値を選択するのであって、入力データの中から比較対象となるデータを選択するのではないので、入力データのパスにおけるクリティカルパスが長くなることを回避し、高速動作を実現することができる。
【００８４】
最小値選択回路１００では、case 3（図６Ｃ）及びcase 4（図６Ｄ）については、第１選択比較部１０７又は第２選択比較部１０８の比較結果によって第１最小値及び第２最小値の判定が可能である。最小値選択回路１００では、更に、総当たり比較部１０５を備えることにより、case 1（図６Ａ）及びcase 2（図６Ｂ）についても、第１選択比較部１０７、第２選択比較部１０８及び総当たり比較部１０５の比較結果のパターンによって第１最小値及び第２最小値の判定が可能となる。
【００８５】
また、特許文献１では、全てのデータ（例えば、図１では１６個）が入力されるまで最小値選択処理を行うことが困難である。これに対して、本実施の形態によれば、最小値選択回路１００は、全てのデータのうち一部のデータが入力された時点で最小値選択処理を行うことができ、データが入力される度に逐次的に処理を進めることができる。
【００８６】
また、本実施の形態によれば、最小値選択回路１００において、総当たり比較部１０５と、第１選択比較部１０７及び第２選択比較部１０８と、が並列に配置されている。つまり、総当たり比較部１０５、第１選択比較部１０７及び第２選択比較部１０８は、並列に処理が可能である。
【００８７】
これにより、最小値選択回路１００では、第１最小値及び第２最小値の選択（判定）処理を高速に行うことができる。例えば、最小値選択回路１００をＬＳＩなどの回路として実装した場合には、クリティカルパスを短くし、動作クロック周波数を上げることができるので、最小値選択回路１００では、第１最小値及び第２最小値の選択処理を高速に行うことができる。
【００８８】
例えば、特許文献１では、或る選択部では、他の比較器（前段の選択部の比較器）における比較結果に基づいて選択処理を行っているので（図１を参照）、複数の比較器の遅延に起因して、高速動作が困難であった。これに対して、本実施の形態では、最小値選択回路１００に含まれる比較器（１５１、１７３、１７４、１８３、１８４）は、それぞれ並列に配置されており、入力データ（図２ではＤ１，Ｄ２）、記憶部１０３に記憶されている値（Xmin1，Xmin2）又は記憶部１０４に記憶されている値（Ymin1，Ymin2）を用いて比較処理を行う。つまり、最小値選択回路１００に含まれる比較器は、他の比較器の比較結果を用いた処理を行わない。よって、最小値選択回路１００では、複数の比較器の動作による遅延が低減されるので、高速動作が可能となる。
【００８９】
また、本実施の形態では、最小値選択回路１００において第１最小値及び第２最小値を選択するために必要な比較器の数を削減することができる。具体的には、最小値選択回路１００は、入力データＤ１，Ｄ２、記憶部１０３に記憶されたXmin1，Xmin2、記憶部１０４に記憶されたYmin1，Ymin2の比較を総当たりで行わない。代わりに、最小値選択回路１００は、Ｄ１，Ｄ２の総当たりを行い、更に、第１選択比較部１０７及び第２選択比較部１０８において記憶部１０３又は記憶部１０４に記憶されたデータから比較対象の値を選択することにより、比較処理の回数を削減している。
【００９０】
例えば、当業者にとって自明な比較方法として、Xmin1,Xmin2,Ymin1,Ymin2の総当りを除く、D1,D2,Xmin1,Xmin2,Ymin1,Ymin2の総当りを行う方法が考えられる。この場合、９個の比較器が必要になる。これに対して、本実施の形態に係る最小値選択回路１００では、５個の比較器（１５１、１７３、１７４、１８３、１８４）ですむ。
【００９１】
以上のように、本実施の形態によれば、最小値選択回路において、遅延を低減するとともに、回路規模を小さくでき、消費電力を低減できる。
【００９２】
（実施の形態２）
実施の形態１では、同時に入力されるデータ数が２個の場合について説明した。これに対して、本実施の形態では、同時に入力されるデータ数が４個の場合について説明する。
【００９３】
図７は、本実施の形態に係る最小値選択回路の構成を示すブロック図である。図７において、実施の形態１（図２）と同一処理を行う構成部には同一符号を付し、その説明を省略する。
【００９４】
以下の説明では、本実施の形態に係る最小値選択回路２００は、図８に示す１６個の動作モード（case 1〜case 16）を有する。なお、図８に示すcase 1〜case 16は、１ステップ（クロックサイクル）におけるデータのグループ分けを示す。図８に示すcase 1〜case 4に示すグループ分けは、実施の形態１（図３）に示すcase 1〜case 4の２ステップ分（ｔ＝１，２）と同一である。
【００９５】
なお、最小値選択回路２００がＬＤＰＣ復号器の一部として使用される場合（実施の形態５において後述する）、検査行列及び復号器の構成によっては、最小値選択回路２００は図８に示す全ての動作モードに対応しなくてもよい場合もある。
【００９６】
図７に示す最小値選択回路２００は、選択部１０１，１０２、記憶部１０３，１０４、総当たり比較部２０１、動作モード指示部１０６、第１選択比較部２０２、第２選択比較部２０３、第３選択比較部２０４、第４選択比較部２０５、判定部２０６を含む構成を採る。
【００９７】
総当たり比較部２０１は、同時（ステップ毎）に入力される所定数のデータ（図７ではＤ１〜Ｄ４）の全ての組み合わせについて並列に（同時に）大小関係の比較を行う。図７では、同時に入力されるデータが４つであるので、総当たり比較部２０１は、６個（＝（４×３）／（２×１））の比較器を有する。
【００９８】
例えば、総当たり比較部２０１は、Ｄ１＜Ｄ２の場合には比較結果Ｃ１２＝１を出力し、Ｄ１≧Ｄ２の場合には比較結果Ｃ１２＝０を出力する。同様に、Ｄ１＜Ｄ３の場合には比較結果Ｃ１３＝１が出力され、Ｄ１≧Ｄ３の場合には比較結果Ｃ１３＝０が出力される。Ｄ２＜Ｄ３の場合には比較結果Ｃ２３＝１が出力され、Ｄ２≧Ｄ３の場合には比較結果Ｃ１４＝０が出力される。Ｄ１＜Ｄ４の場合には比較結果Ｃ２３＝１が出力され、Ｄ１≧Ｄ４の場合には比較結果Ｃ１４＝０が出力される。Ｄ２＜Ｄ４の場合には比較結果Ｃ２４＝１が出力され、Ｄ２≧Ｄ４の場合には比較結果Ｃ２４＝０が出力される。Ｄ３＜Ｄ４の場合には比較結果Ｃ３４＝１が出力され、Ｄ３≧Ｄ４の場合には比較結果Ｃ３４＝０が出力される。
【００９９】
つまり、比較結果Ｃ１２，Ｃ１３，Ｃ１４，Ｃ２３，Ｃ２４，Ｃ３４は、データＤ１〜Ｄ４間の大小関係を示す。
【０１００】
動作モード指示部１０６は、現ステップの動作モードが図８に示す動作モード（case 1〜case 16）の何れであるかを第１選択比較部２０２、第２選択比較部２０３、第３選択比較部２０４、第４選択比較部２０５及び判定部２０６に指示する。
【０１０１】
最小値選択回路２００において、選択比較部は、最小値選択回路２００に同時に入力されるデータ数と同数備えられ、各選択比較部は同時に入力されるデータの各々に対応する。具体的には、第１選択比較部２０２はデータＤ１に対応し、第２選択比較部２０３はデータＤ２に対応し、第３選択比較部２０４はデータＤ３に対応し、第４選択比較部２０５はデータＤ４に対応する。
【０１０２】
第１選択比較部２０２、第２選択比較部２０３、第３選択比較部２０４、第４選択比較部２０５は、各々に対応するデータが属するグループに対応する第１最小値及び第２最小値を記憶部１０３又は記憶部１０４から選択し、選択された第１最小値及び第２最小値と、各々に対応する入力データ（Ｄ１〜Ｄ４）とを比較する。
【０１０３】
第１選択比較部２０２、第２選択比較部２０３、第３選択比較部２０４、第４選択比較部２０５は、それぞれ、２つの選択部と、２つの比較器を備える。なお、選択部及び比較器の動作は、実施の形態１における第１選択比較部１０７及び第２選択比較部１０８が備える選択部及び比較器と同一である。
【０１０４】
図９〜図１２は、第１選択比較部２０２〜第４選択比較部２０５における動作例を示す。
【０１０５】
第１選択比較部２０２は、case 1,3,5,7,9,12,14,16の場合（図９Ａ）、Xmin1、Xmin2を選択し、case 2,4,6,8,10,11,13,15の場合（図９Ｂ）、Ymin1、Ymin2を選択する。そして、第１選択比較部２０２は、選択した値Zmin1、Zmin2とＤ１とをそれぞれ比較し、比較結果Ｃｚ１，Ｃｚ２を判定部２０６へ出力する。
【０１０６】
第２選択比較部２０３は、case 1,4,5,8,10,11,14,16の場合（図１０Ａ）、Xmin1、Xmin2を選択し、case 2,3,6,7,9,12,13,15の場合（図１０Ｂ）、Ymin1、Ymin2を選択する。そして、第２選択比較部２０３は、選択した値Wmin1、Wmin2とＤ２とをそれぞれ比較し、比較結果Ｃｗ１，Ｃｗ２を判定部２０６へ出力する。
【０１０７】
第３選択比較部２０４は、case 1,3,6,8,10,12,13,16の場合（図１１Ａ）、Xmin1、Xmin2を選択し、case 2,4,5,7,9,11,14,15の場合（図１１Ｂ）、Ymin1、Ymin2を選択する。そして、第３選択比較部２０４は、選択した値Umin1、Umin2とＤ３とをそれぞれ比較し、比較結果Ｃｕ１，Ｃｕ２を判定部２０６へ出力する。
【０１０８】
第４選択比較部２０５は、case 1,4,6,7,10,12,14,15の場合（図１２Ａ）、Xmin1、Xmin2を選択し、case 2,3,5,8,9,11,13,16の場合（図１２Ｂ）、Ymin1、Ymin2を選択する。そして、第４選択比較部２０５は、選択した値Vmin1、Vmin2とＤ４とをそれぞれ比較し、比較結果Ｃｖ１，Ｃｖ２を判定部２０６へ出力する。
【０１０９】
つまり、比較結果Ｃｚ１，Ｃｚ２，Ｃｗ１，Ｃｗ２，Ｃｕ１，Ｃｕ２，Ｃｖ１，Ｃｖ２は、データＤ１〜Ｄ４と第１最小値及び第２最小値との間の大小関係を示す。
【０１１０】
図７に戻り、判定部２０６は、動作モード１０６から入力される動作モード、総当たり比較部２０１から入力される比較結果と第１選択比較部２０２〜第４選択比較部２０５から入力される比較結果とのパターンに基づいて、記憶部１０３又は記憶部１０４に記憶された第１最小値（Xmin1、Ymin1）及び第２最小値（Xmin2、Ymin2）を更新する値を判定する。
【０１１１】
すなわち、判定部２０６は、データＤ１〜Ｄ２、及び、記憶部１０３又は記憶部１０４に記憶された第１最小値及び第２最小値の中から、記憶部１０３又は記憶部１０４に記憶する新たな第１最小値及び新たな第２最小値を判定する。
【０１１２】
図１３〜図１７は、判定部２０６の動作を表す真理値表（パターン）の一例を示す。
【０１１３】
図１３Ａはcase 1の場合、図１３Ｂはcase 2の場合、図１４Ａはcase 3の場合、図１４Ｂはcase 4の場合、図１５Ａはcase 5の場合、図１５Ｂはcase 6の場合、図１６Ａはcase 9の場合、図１６Ｂはcase 10の場合、図１７Ａはcase 11の場合、図１７Ｂはcase 12の場合の真理値表をそれぞれ示す。
【０１１４】
図１３ではいずれか１つの条件が選択される。空欄および*はドントケアである。図１４、図１５では、Aで始まる条件番号から１つ、Bで始まる条件番号から１つの条件がそれぞれ選択される。空欄及び斜線（図１４におけるＣ１２，Ｃ１４，Ｃ２３，Ｃ３４の列）はドントケアである。複数の条件に当てはまる場合は、小さい条件番号が選択される。たとえば、case 3（図１４Ａ）において、入力（Ｃｚ１，Ｃｚ２，Ｃｗ１，Ｃｗ２，Ｃｕ１，Ｃｕ２，Ｃｖ１，Ｃｖ２，Ｃ１３，Ｃ２４）がすべて１のとき、条件番号A3-1とA3-2、B3-1とB3-2が該当するが、条件番号A3-1とB3-1が選択され、出力としてXmin1,Xmin2,Ymin1,Ymin2が選択される。
【０１１５】
なお、図１３〜図１７では、一例として、IEEE802.11adの規格において使用される動作モードを例示し、使用されない動作モードについては省略する。
【０１１６】
判定部２０６は、case 1〜case 16において、各比較結果に基づいて新たな第１最小値（Xmin1,Ymin1）及び新たな第２最小値（Xmin2,Ymin2）を判定する。
【０１１７】
以上のように、本実施の形態では、最小値選択回路２００は、複数のデータ入力（図７では４個のデータ入力）を同時に受け付ける入力端子、及び、入力されるデータに対して大小関係を総当たりで比較する総当たり比較部２０１を備える。また、最小値選択回路２００では、選択比較部は、同時に入力されるデータ数と同数の４個備えられる。
【０１１８】
そして、最小値選択回路２００において、第１選択比較部２０２〜第４選択比較部２０５は、動作モードに基づいて、記憶部１０３又は記憶部１０４に記憶されている第１最小値及び第２最小値の組の何れかを選択して、選択した第１最小値及び第２最小値と入力データの各々との比較を行う。
【０１１９】
これにより、最小値選択回路２００は、逐次的に入力されるデータについて、複数のグループ（第１グループ及び第２グループ）毎に第１最小値及び第２最小値を求めることができる。また、最小値選択回路２００に入力される複数のデータの各々が属するグループが時々刻々変わる場合でも、最小値選択回路２００は、複数のグループ毎に第１最小値及び第２最小値を求めることができる。
【０１２０】
また、最小値選択回路２００では、入力データとの比較対象となる第１最小値及び第２最小値を選択するのであって、入力データの中から比較対象となるデータを選択するのではないので、入力データのパスにおけるクリティカルパスが長くなることを回避し、高速動作を実現することができる。
【０１２１】
また、本実施の形態によれば、最小値選択回路２００は、全てのデータのうち一部のデータが入力された時点で最小値選択処理を行うことができるので、実施の形態１と同様、データが入力される度に逐次的に処理を進めることができる。
【０１２２】
また、本実施の形態によれば、最小値選択回路２００において、総当たり比較部２０１と、第１選択比較部２０２〜第４選択比較部２０５と、が並列に配置されている。
【０１２３】
これにより、最小値選択回路２００では、第１最小値及び第２最小値の選択（判定）処理を高速に行うことができる。例えば、最小値選択回路２００をＬＳＩなどの回路として実装した場合には、クリティカルパスを短くし、動作クロック周波数を上げることができるので、最小値選択回路２００では、第１最小値及び第２最小値の選択処理を高速に行うことができる。
【０１２４】
また、本実施の形態によれば、実施の形態１と比較して、同時に入力されるデータの個数（並列度）が増加するものの、最小値選択回路２００に含まれる比較器は、実施の形態１と同様、他の比較器の比較結果に基づく処理を行わない。このため、最小値選択回路２００では比較器の遅延に起因する動作は発生しない。つまり、最小値選択回路２００では、比較器の深さが１段であるのでクリティカルパスが短く、高速動作を実現することができる。
【０１２５】
また、本実施の形態では、最小値選択回路２００において第１最小値及び第２最小値を選択するために必要な比較器の数を削減することができる。具体的には、最小値選択回路２００は、入力データＤ１〜Ｄ４、記憶部１０３に記憶されたXmin1，Xmin2、記憶部１０４に記憶されたYmin1，Ymin2の比較を総当たりで行わずに、Ｄ１〜Ｄ４の総当たりで行うとともに、第１選択比較部２０２〜第４選択比較部２０５において比較対象の値を選択する。
【０１２６】
例えば、当業者にとって自明な比較方法として、Xmin1,Xmin2,Ymin1,Ymin2の総当りを除く、D1,D2,D3,D4,Xmin1,Xmin2,Ymin1,Ymin2の総当りを行う方法が考えられる。この場合、２２個の比較器が必要になる。これに対して、図７に示す最小値選択回路２００では、１４個の比較器ですむ。
【０１２７】
以上のように、本実施の形態によれば、最小値選択回路において、遅延を低減するとともに、回路規模を小さくでき、消費電力を低減できる。
【０１２８】
（実施の形態３）
本実施の形態では、実施の形態１において説明した最小値選択回路を縦列に接続する場合について説明する。
【０１２９】
図１８は、本実施の形態に係る最小値選択回路の構成を示すブロック図である。
【０１３０】
図１８に示す最小値選択回路３００は、前処理部３０１及び最小値選択部３０２を備える。
【０１３１】
図１９は、図１８に示す前処理部３０１の内部構成を示すブロック図であり、図２０は、図１８に示す最小値選択部３０２の内部構成を示すブロック図である。
【０１３２】
なお、図１９及び図２０において、実施の形態１（図２）と同一処理を行う構成部には同一符号を付し、その説明を省略する。具体的には、図１９に示す前処理部３０１及び図２０に示す最小値選択部３０２は、基本的に実施の形態１に係る最小値選択回路１００と同様の構成を有する。
【０１３３】
ただし、双方を区別するために、前処理部３０１を構成する構成部の符号に「ａ」を付し、最小値選択部３０２を構成する構成部の符号に「ｂ」を付す。また、前処理部３０１を構成する構成部から出力されるパラメータ（例えば、Xmin1など）号に上添字「’」を付し（例えば、Xmin1'）、最小値選択部３０２を構成する構成部から出力されるパラメータと区別する。
【０１３４】
前処理部３０１と最小値選択部３０２は、パラメータXmin1,Xmin2,Ymin1,Ymin2とパラメータXmin1’,Xmin2’,Ymin1’,Ymin2’を相互に交換するよう接続される。最小値選択部３０２は、基本的に実施の形態１に係る最小値選択回路１００と同様の構成を有するが、最小値選択回路１００では選択部１０１ａ、１０２ａ、１７１ａ、１７２ａ、１８１ａ、１８２ａにXmin1,Xmin2,Ymin1,Ymin2のいずれかを入力するのに対し、最小値選択部３０２では選択部１０１ｂ、１０２ｂ、１７１ｂ、１７２ｂ、１８１ｂ、１８２ｂにXmin1’,Xmin2’,Ymin1’,Ymin2’のいずれかを入力する点が異なる。
【０１３５】
また、前処理部３０１は、記憶部１０３及び記憶部１０４に相当する構成部を備えない。前処理部３０１は選択部１０１ａ、１０２ａ、１７１ａ、１７２ａ、１８１ａ、１８２ａへの入力として、最小値選択部３０２が有する記憶部１０３ｂ、１０４ｂに保持されているXmin1,Xmin2,Ymin1,Ymin2を用いる。
【０１３６】
前処理部３０１には入力データＤ１，Ｄ２が入力され、最小値選択部３０２には入力データＤ３，Ｄ４が入力される。すなわち、最小値選択回路３００には、実施の形態２と同様、同時に４個のデータＤ１〜Ｄ４が入力される。
【０１３７】
例えば、図８に示す１クロックサイクルにつき４個のデータが同時に入力されるcase 5の動作モードの場合、Ｄ１，Ｄ２（第１グループ）が前処理部３０１に入力され、Ｄ３，Ｄ４のグループ（第２グループ）が最小値選択部３０２に入力される。すなわち、図２１に示すように、case 5の動作モードでは、１クロックサイクルにつき２個のデータが同時に入力されるcase 1に対応するグループが前処理部３０１に入力され、１クロックサイクルにつき２個のデータが同時に入力されるcase 2に対応するグループが最小値選択部３０２に入力されると言える。
【０１３８】
よって、case 5の動作モードでは、前処理部３０１の動作モード指示部１０６ａは、case 1を指示し、最小値選択部３０２の動作モード指示部１０６ｂは、case 2を指示すればよい。つまり、前処理部３０１及び最小値選択部３０２は、実施の形態１と同様に動作する。
【０１３９】
また、前処理部３０１は、入力データが入力され、第１最小値（Xmin1'又はYmin1'）及び第２最小値（Xmin2'又はYmin2'）が更新される度にXmin1'、Ymin1'、Xmin2'、Ymin2'を最小値選択部３０２へ出力する。
【０１４０】
前処理部３０１から入力される第１最小値（Xmin1'、Ymin1'）及び第２最小値（Xmin2'、Ymin2'）は、最小値選択部３０２の第１選択比較部１０７ｂ及び第２選択比較部１０８ｂにそれぞれ入力される。
【０１４１】
最小値選択部３０２は、入力データが入力され、第１最小値（Xmin1又はYmin1）及び第２最小値（Xmin2又はYmin2）が更新される度にXmin1、Ymin1、Xmin2、Ymin2を前処理部３０１へ出力する。
【０１４２】
最小値選択部３０２から入力される第１最小値（Xmin1、Ymin1）及び第２最小値（Xmin2、Ymin2）は、前処理部３０１の、選択部１０１ａ、選択部１０２ａ、第１選択比較部１０７ａ及び第２選択比較部１０８ａにそれぞれ入力される。
【０１４３】
すなわち、最小値選択回路３００では、最小値選択部３０２において選択された第１最小値及び第２最小値（Xmin1、Xmin2、Ymin1、Ymin2）と、前処理部３０１の入力データＤ１，Ｄ２とが比較され、前処理部３０１において選択された第１最小値及び第２最小値（Xmin1'、Xmin2'、Ymin1'、Ymin2'）と、最小値選択部３０２の入力データＤ３，Ｄ４とが比較される。そして、１ステップの処理結果として、実施の形態２と同様、最小値選択回路３００に入力されたデータ（データＤ１〜Ｄ４を含む）について第１最小値及び第２最小値が求まる。
【０１４４】
本実施の形態では、最小値選択回路３００では、実施の形態１の構成（図２を参照）と同様、複数の動作モードに対応しつつ、クリティカルパスを短くし、動作クロック周波数を上げることができるので、第１最小値及び第２最小値の選択処理を高速に行うことができる。
【０１４５】
また、本実施の形態では、最小値選択回路３００は、実施の形態１の構成（図２を参照）と同様の構成を有するので、実施の形態１と同様、最小値選択回路３００に含まれる比較器を削減することができる。
【０１４６】
よって、本実施の形態によれば、実施の形態２と同様、４個のデータが同時に入力される場合でも、最小値選択回路において、遅延を低減するとともに、回路規模を小さくでき、消費電力を低減できる。
【０１４７】
（実施の形態４）
本実施の形態では、実施の形態１に示す最小値選択回路１００（図２を参照）と同様の最小値選択回路を含むＬＤＰＣ復号器について説明する。
【０１４８】
図２２は、本実施の形態に係るＬＤＰＣ復号器の構成を示すブロック図である。
【０１４９】
ＬＤＰＣ復号器４００は、ＬＤＰＣ符号を用いて符号化されたデータ（ディジタル信号）を復号する。なお、ＬＤＰＣ符号は、線形符号の一例である。
【０１５０】
ＬＤＰＣ復号器４００は、検査行列（例えば後述する図２３を参照）に基づき符号化されたデータから元のデータを復号する。例えば、ＬＤＰＣ復号器４００は、Ｍｉｎ−Ｓｕｍ復号法に基づいて、１時点（クロックサイクル）につき検査行列４２列分の演算を並列に処理する。
【０１５１】
例えば、IEEE802.11ad規格では、図２３に示す、符号化率の異なる４つの検査行列が規定されている。
【０１５２】
符号化率とは、送信語のうち、情報ビットの占める割合である。符号化率が低いほど、誤り訂正能力が高く、無線通信における伝搬路品質に応じて適当な符号化率が選択される。よって、例えば、IEEE802.11ad規格に対応する場合、ＬＤＰＣ復号器４００は、４つの符号化率に対応して、使用する検査行列を切り替えて復号を行う必要がある。
【０１５３】
図２３に示す４つの検査行列において、数字が記載されている部分は、４２行４２列の単位行列を記載された数字行方向に巡回シフトした行列を表す。例えば、図２３に示す符号化率１／２の検査行列において丸で囲まれた部分の数字は「２４」であるので、当該部分は、単位行列を行方向に２４（つまり２４列）シフトした行列を表す。
【０１５４】
また、図２３に示す４つの検査行列において、空欄となっている部分は、４２行４２列の零行列を表す。
【０１５５】
以下の説明では、４２行４２列の行列を「サブマトリックス」と称することもある。
【０１５６】
また、一例として、図２３に示す符号化率１／２の検査行列は、１６個のサブマトリックスによって行が構成され、８個のサブマトリックスによって列が構成される。各行における１６個のサブマトリックスの集まりを「行グループ」と称することもある。また、各列における８個のサブマトリックスの集まりを「列グループ」と称することもある。
【０１５７】
すなわち、図２３に示す符号化率１／２の検査行列は、３３６行６７２列の行列である。
【０１５８】
図２２に示すＬＤＰＣ復号器４００は、入力メモリ４０１、出力メモリ４０２、２個の列処理演算器４０３、８個のシフタ４０４、データ転送部４０５、４個の行処理演算器４０６、８個の後処理部４０７、データ転送部４０８、８個のシフタ４０９、制御部４１０を含む構成を採る。
【０１５９】
入力メモリ４０１は、ＬＤＰＣ復号器４００への入力データを保持し、ＬＤＰＣ復号器４００の動作に応じて、列処理演算器４０３に必要なデータを供給する。
【０１６０】
出力メモリ４０２は、列処理演算器４０３から出力されるＬＤＰＣ復号の復号結果であるデータを保持する。
【０１６１】
なお、入力メモリ４０１が省略されてもデータがＬＤＰＣ復号器４００へ入力できればよく、出力メモリ４０２が省略されてもデータがＬＤＰＣ復号器４００から出力できればよい。
【０１６２】
シフタ４０４は、列処理演算器４０３から出力されるデータに対してシフト処理し、検査行列の各要素に対応するデータを順に出力する。
【０１６３】
シフタ４０９は、データ転送部４０８から出力されるデータ（つまり、行処理演算後のデータ）に対してシフト処理する。ただし、シフタ４０９は、シフタ４０４と同一のシフト量、シフタ４０４とは逆方向にデータをシフトする。
【０１６４】
列処理演算器４０３は、入力メモリ４０１から出力されるデータ、又は、シフタ４０９から出力されるデータを用いて、Ｍｉｎ−Ｓｕｍ復号法に基づいて列処理演算を行う。例えば、列処理演算器４０３は、式（１）に示す演算を行う。
【数１】
0006511284.tif 000002
【０１６５】
式（１）において、βmnは、列メッセージと呼ばれるデータを示す。ｍ、ｎは検査行列中の行番号、列番号をそれぞれ示すインデックスである。例えば、符号化率１／２の検査行列では、０≦ｍ＜６７２、０≦ｎ＜３３６となる。βmnについては、検査行列中のｍ行ｎ列の要素が１であるｍ，ｎの組み合わせに対して計算を行えばよい。
【０１６６】
また、式（１）において、Ａ（ｎ）は、検査行列のｎ列目において、要素が１である行番号の集合を表す。また、m'はＡ（ｎ）に含まれる行番号のうち行番号mを除く行番号を表す。
【０１６７】
また、αm'nは、行メッセージと呼ばれるデータを示す。例えば、行メッセージαm'nは、繰り返し復号の初期値として０が設定され、繰り返し復号中にはシフタ４０９から出力されるデータが設定される。また、λｎは、ＬＤＰＣ復号器４００に入力される入力データを示し、入力メモリ４０１に格納されている。通信機にＬＤＰＣ復号器４００が備えられる場合、λｎは、受信データに相当するので、「通信路値」と称されることもある。
【０１６８】
図２２に示すＬＤＰＣ復号器４００は、２つの列処理演算器４０３（以下、４０３−１、４０３−２とする）を備える。
【０１６９】
各列処理演算器４０３は、１つの列グループに対する列処理演算を１クロックサイクルで処理する能力を有する。１つの列グループは４２列で構成され、各列において１である要素は最大で４つであるから、１つの列処理演算器４０３は、式（１）に示す処理を１６８（＝４２×４）回分並列に行う。
【０１７０】
例えば、図２４に示すように、列処理演算器４０３−１は、奇数番号の列グループに対する列処理演算を行い、列処理演算器４０３−２は、偶数番号の列グループに対する列処理演算を行う。これにより、２つの列処理演算器４０３によって１クロックサイクルにつき２つの列グループに対する列処理演算が行われ、検査行列全体に対する列処理演算は、８クロックサイクルで完了する。
【０１７１】
図２４では、各列グループにおける非零のサブマトリックスは最大で４個である。したがって、１つの列処理演算器４０３に対する入力データ数は、最大でも４サブマトリックスに相当する行メッセージの個数（４２個×４＝１６８個）であり、１つの列処理演算器４０３からの出力データ数も同数である。
【０１７２】
行処理演算器４０６は、データ転送部４０５から出力されるデータを用いて、Ｍｉｎ−Ｓｕｍ復号法に基づいて行処理演算を行う。例えば、行処理演算器４０６は、式（２）に示す演算を行う。例えば、行処理演算器４０６では、計算を簡単にするため、式（２）の第２式が用いられる。
【数２】
0006511284.tif 000003
【０１７３】
具体的には、行処理演算器４０６は、式（２）に示すβｍｍｉｎ、βｍｍｉｎ２及びSｍを算出する。
【０１７４】
後処理部４０７は、式（２）に示す選択処理（｜βｍｎ｜とβｍｍｉｎとの比較を行い、式（２）の第２式の２つの値のいずれかを選択する）を行い、列処理演算器４０３は、式（２）に示すβｍｍｉｎ又はβｍｍｉｎ２と、ｓｉｇｎ（βｍｎ）との乗算を行う。
【０１７５】
なお、行処理演算器４０６において｜βｍｎ｜=βｍｍｉｎとなるｎの値（インデックスと称されることもある）を算出して後処理部４０７に渡すことにより、後処理部４０７における｜βｍｎ｜とβｍｍｉｎとの比較処理を省略しても良い。
【０１７６】
なお、ｓｉｇｎ（βmn）は、βmnの符号を表す。また、Ｂ（ｍ）は、検査行列のｍ行目において要素が１である列番号の集合を表す。また、n'はＢ（ｍ）に含まれる列番号のうち列番号nを除く列番号を表す。
【０１７７】
また、βｍｍｉｎは第１最小値であり、式（３）によって表され、βｍｍｉｎ２は第２最小値であり、式（４）によって表される。式（４）の関数ｍｉｎ＿２ｎｄ（）は第２最小値を求める関数である。
【数３】
0006511284.tif 000004
【数４】
0006511284.tif 000005
【０１７８】
すなわち、式（３）に示すβｍｍｉｎは、第ｍ行目のβmn'の絶対値のうち最も小さい値を表し、式（４）に示すβｍｍｉｎ2は、第ｍ行目のβmn'の絶対値のうち２番目に小さい値を表す。
【０１７９】
また、式（２）に示すSｍは、式（５）に従って算出される。ｓｉｇｎ（βｍｎ’）は、式（６）に従って算出される。
【数５】
0006511284.tif 000006
【数６】
0006511284.tif 000007
【０１８０】
図２２に示すＬＤＰＣ復号器４００は、４つの行処理演算器４０６（以下、４０６−１〜４０６−４とする）を備える。
【０１８１】
１つの行処理演算器４０６は、２つのサブマトリックス（１サブマトリックスは４２個の列メッセージに対応）に相当するデータを１クロックサイクルで処理する能力を有する。
【０１８２】
例えば、図２５に示すように符号化率１／２の場合、８個の行グループがあるので、４つの行処理演算器４０６−１〜４０６−４の各々には、２つの行グループが対応付けられる。このとき、各行処理演算器４０６に対応付けられる２つの行グループは、同一列グループにおいて非零のサブマトリックスが１つとなるように割り当てられている。
【０１８３】
そして、各行処理演算器４０６は、２つの列グループを１クロックサイクルで処理する。例えば、行処理演算器４０６−１は、ｔ＝１において、第１行グループの「４０」に相当するサブマトリックス、及び、第３行グループの「３６」に相当するサブマトリックスに対する行処理演算を行う。図２６は、行処理演算器４０６−１がｔ＝１において行処理演算を行う対象のサブマトリックス（「４０」、「３６」の非零行列及び零行列を含む）を示す。
【０１８４】
また、図２７に示すように符号化率５／８の場合、６個の行グループがあるので、２つの行処理演算器４０６−１，４０６−２の各々には、１つの行グループが対応付けられ、２つの行処理演算器４０６−３，４０６−４の各々には、２つの行グループが対応付けられる。このとき、行処理演算器４０６−３，４０６−４に対応付けられる２つの行グループは、同一列グループにおいて非零のサブマトリックスが１つとなるように割り当てられている。
【０１８５】
同様に、図２８に示すように符号化率３／４の場合、４個の行グループがあるので、４つの行処理演算器４０６−１〜４０６−４の各々には、１つの行グループが対応付けられる。
【０１８６】
上述した行処理演算器４０６と行グループとの対応付け（割当）は、データ転送部４０５によって行われる。
【０１８７】
図２９は、データ転送部４０５の動作例を示す。
【０１８８】
列処理演算器４０３−１から出力される、奇数番号の列グループの最大４サブマトリックス（非零）に相当する列メッセージ（B1e_1〜42、B2e_1〜42、B3e_1〜42、B4e_1〜42。式（１）のβmnに相当）は、シフタ４０４−１〜４０４−４を介して４つの行処理演算器４０６−１〜４０６−４に分配される。
【０１８９】
同様に、列処理演算器４０３−２から出力される、偶数番号の列グループの４サブマトリックスに相当する列メッセージ（B1o_1〜42、B2o_1〜42、B3o_1〜42、B4o_1〜42。式（１）のβmnに相当）は、シフタ４０４−５〜４０４−８を介して４つの行処理演算器４０６−１〜４０６−４に分配される。
【０１９０】
この結果、各行処理演算器４０６には、奇数番号の列グループ及び偶数番号の列グループの１サブマトリックスに相当するデータが入力される。
【０１９１】
例えば、図２５に示す符号化率１／２の検査行列を用いる場合、行処理演算器４０６−１には、第１行グループの各列に相当するサブマトリックス（図２５では「４０」、「３８」、「１３」、「５」、「１８」）に対応する列メッセージB1e_1〜B1e_42がステップ（ｔ＝１〜８）毎に順に入力される。同様に、行処理演算器４０６−１には、第３行グループの各列に相当するサブマトリックス（図２５では「３６」、「３１」、「７」、「３４」、「１０」、「４１」）に対応する列メッセージB1o_1〜B1o_42がステップ（ｔ＝１〜８）毎に入力される。
【０１９２】
その他の行処理演算器４０６−２〜４０６−４についても同様である。
【０１９３】
図３０は、行処理演算器４０６−１の構成を示すブロック図である。
【０１９４】
図３０に示す行処理演算器４０６−１は、サブマトリックスのサイズに応じて、４２個の演算器４６１−１〜４６１−４２が並列に配置された構成を採る。また、各演算器４６１は、最小値選択回路１００、分配回路４６２，４６３、符号算出回路４６４，４６５、レジスタ４６６，４６７を含む構成を採る。
【０１９５】
最小値選択回路１００は、実施の形態１と同様の処理を行うことにより、式（３）及び式（４）に示す第１最小値βｍｍｉｎ及び第２最小値βｍｍｉｎ２を求める。
【０１９６】
図２５、図２７、図２８に示すように、行処理演算器４０６では１クロックサイクルにつき２つの列グループが処理される。具体的には、図２５に示す検査行列が用いられた場合、演算器４６１−１の最小値選択回路１００には、１クロックサイクルにつき、第１行グループ（例えば実施の形態１の第１グループに対応）の列メッセージB1e_1（実施の形態１のＤ１に相当）と、第３行グループ（例えば実施の形態１の第２グループに対応）の列メッセージB1o_1（実施の形態１のＤ２に相当）と、が１クロックサイクルにつき処理される。
【０１９７】
そして、演算器４６１−１の最小値選択回路１００は、８クロックサイクルを要して、第１行グループの第１最小値A1min1_1（βｍｍｉｎ又は図２のXmin1に相当）及び第２最小値A1min2_1（βｍｍｉｎ２又は図２のXmin2に相当）を算出する。同様に、演算器４６１−１の最小値選択回路１００は、８クロックサイクルを要して、第３行グループの第１最小値A3min1_1（βｍｍｉｎ又は図２のYmin1に相当）及び第２最小値A3min2_1（βｍｍｉｎ２又は図２のYmin2に相当）を算出する。
【０１９８】
最小値選択回路１００における動作は実施の形態１と同様である。最小値選択回路１００の動作モード指示部１０６は、図２５、図２７、図２８に示すように検査行列（つまり符号化率）の種類及び時刻ｔに応じて、case 1〜4を各構成部に指示する。
【０１９９】
分配回路４６２，４６３は、図示しない制御部によって、動作モードcase 1〜4に応じて、入力されるデータの符号（符号ビット情報）を、対応する符号算出回路４６４，４６５に出力する。
【０２００】
例えば、分配回路４６２は、case 1,3（図２５、図２７、図２８を参照）では入力される符号ビット情報を、第１行グループに対応する符号算出回路４６４に出力する。また、分配回路４６２は、case 2（図２５を参照）では、入力される符号ビット情報を第３行グループに対応する符号算出回路４６５に出力する。一方に、分配回路４６３は、case 3（図２５を参照）では、入力される符号ビット情報を第３行グループに対応する符号算出回路４６５に出力する。
【０２０１】
符号算出回路４６４、４６５は、式（５）の計算を行う。
【０２０２】
レジスタ４６６は，４６７の各々は、最小値選択回路１００及び符号算出回路４６４，４６５から出力される第１行グループ及び第３行グループに関する出力データをそれぞれ保持し、後処理部４０７に出力する。
【０２０３】
例えば、演算器４６１−１の第１行グループの出力データには、第１行グループに含まれる列メッセージB1e_1の第１最小値A1min1_1（式（３）のβｍｍｉｎ）、第２最小値A1min2_1（式（４）のβｍｍｉｎ２）、符号A1idx1（式（２）において｜βｍｎ｜=βｍｍｉｎとなるｎの値）、符号A1sign_1（式（５）のSｍ）が含まれる。他の出力データについても同様である。
【０２０４】
なお、図３０では行処理演算器４０６−１（第１行グループ及び第３行グループに対応）の構成について説明したが、図示しない他の行処理演算器４０６−２〜４０６−４も同様の構成を採り、他の行グループに対する行処理演算を行う。
【０２０５】
図２２に戻り、データ転送部４０８は、上述した行処理演算器４０６と行グループとの対応付け（割当）に従って、後処理部４０７−１〜４０７−８から出力されるデータ（式（２）に示すβｍｍｉｎ（又はβｍｍｉｎ２）、Sｍ、sign（βmn））を、奇数番号の列グループと偶数番号の列グループとに分配し、シフタ４０９−１〜４０９−４（奇数番号の列グループに対応）及びシフタ４０９−５〜４０９−８（偶数番号の列グループに対応）にそれぞれ出力する。
【０２０６】
図３１は、データ転送部４０８の動作例を示す。
【０２０７】
図３１に示すセレクタ４８１−１，４８１−３，４８１−５，４８１−７は、後処理部４０７−１〜４０７−８から出力される各行グループのデータから奇数番号の列グループのデータを選択し、シフタ４０９−１〜４０９−４にそれぞれ出力する。
【０２０８】
同様に、図３１に示すセレクタ４８１−２，４８１−４，４８１−６，４８１−８は、後処理部４０７−１〜４０７−８から出力される各行グループのデータから偶数番号の列グループのデータを選択し、シフタ４０９−５〜４０９−８にそれぞれ出力する。
【０２０９】
以上より、本実施の形態において、ＬＤＰＣ復号器４００は、複数の列処理演算器４０３及び複数の行処理演算器４０６を備え、各行処理演算器４０６は、実施の形態１に係る構成を有する最小値選択回路１００を備える。これにより、ＬＤＰＣ復号器４００では、実施の形態１と同様にして行処理演算器４０６での比較器の数を低減できるので、複数の検査行列に対応しつつ、行処理演算器４０６の処理を高速に動作させることができる。
【０２１０】
また、図２２において制御部４１０は、選択された検査行列（例えば、図２３に示す４つの検査行列から１つを選択)に応じて、行処理演算器４０６−１〜４０６−４の各々に対して設定する動作モード（case）を制御する。例えば、図２５に示す符号化率１／２の検査行列が選択された場合、制御部４１０は、行処理演算器４０６−１に対して、case3（t=1のとき)、case3（t=2のとき）,・・・, case2（t=6のとき）の順に処理を行うように指示する。他の符号化率（例えば、図２７の符号化率５／８、図２８の符号化率３／４）の検査行列についても、同様にして、制御部４１０は、各行処理演算器４０６に対して動作モード（case 1〜4）を指示する。
【０２１１】
各行処理演算器４０６が備える最小値選択回路１００は、同時に入力される所定数のデータの各々を、制御部４１０によって指示される動作モード（例えば、図２５ではcase 1〜case 4）に応じて複数のグループにグループ分けする。つまり、最小値選択回路１００に同時に入力される所定数のデータの各々は、検査行列の種類に応じて、複数のグループの何れかに属する。そして、最小値選択回路１００の記憶部１０３，１０４は、上記所定数のデータについて、複数のグループ毎の第１最小値及び第２最小値を記憶する。また、第１選択比較部１０７及び第２選択比較部１０８（複数の第２比較部）の各々には、入力される各データが属するグループに対応する第１最小値及び第２最小値が記憶部１０３，１０４から入力される。
【０２１２】
こうすることで、各行処理演算器４０６が備える最小値選択回路１００は、複数の検査行列に応じて最小値選択処理を行うことができる。すなわち、検査行列の種類に応じて、最小値選択回路１００の構成を変更したり、複数の構成を備えたりする必要がない。よって、本実施の形態によれば、最小値選択回路１００を備える行処理演算機４０６の回路規模を小さくし、消費電力を低くすることができる。
【０２１３】
（実施の形態５）
実施の形態４では、実施の形態１に示す最小値選択回路１００を含むＬＤＰＣ復号器（同時に入力されるデータ数が２個の場合）について説明した。これに対して、本実施の形態では、実施の形態２，３に示す最小値選択回路２００，３００（図７、図１８を参照）と同様の最小値選択回路を含むＬＤＰＣ復号器（同時に入力されるデータ数が４個の場合）について説明する。
【０２１４】
図３２は、本実施の形態に係るＬＤＰＣ復号器の構成を示すブロック図である。
【０２１５】
図３２に示すＬＤＰＣ復号器５００は、基本的に実施の形態４に係るＬＤＰＣ復号器４００と同様の構成を備える。
【０２１６】
ＬＤＰＣ復号器５００は、列処理演算器５０３を４個備え、シフタ５０４，５０９及び後処理部５０７を、各行処理演算器５０６において同時に処理されるデータ数（４個）に対応して１６個備える点がＬＤＰＣ復号器４００と異なる。ＬＤＰＣ復号器５００が備える行処理演算器５０６の数は、実施の形態４（ＬＤＰＣ復号器４００）と同様の４個である。
【０２１７】
また、実施の形態４と同様、各列グループにおける非零のサブマトリックスは最大で４個である。したがって、１つの列処理演算器５０３に対する入力データ数は、最大でも４サブマトリックスに相当する行メッセージの個数（４２個×４＝１６８個）であり、１つの列処理演算器４０３からの出力データ数も同数である。
【０２１８】
また、図３３に示すように符号化率１／２の場合、８個の行グループがあるので、４つの行処理演算器５０６−１〜５０６−４の各々には、２つの行グループが対応付けられる。このとき、各行処理演算器５０６に対応付けられる２つの行グループは、同一列グループにおいて非零のサブマトリックスが１つとなるように割り当てられている。
【０２１９】
また、図３４に示すように符号化率５／８の場合、６個の行グループがあるので、２つの行処理演算器５０６−１，５０６−２の各々には、１つの行グループが対応付けられ、２つの行処理演算器５０６−３，５０６−４の各々には、２つの行グループが対応付けられる。このとき、行処理演算器５０６−３，５０６−４に対応付けられる２つの行グループは、同一列グループにおいて非零のサブマトリックスが１つとなるように割り当てられている。
【０２２０】
同様に、図３５に示すように符号化率３／４の場合、４個の行グループがあるので、４つの行処理演算器５０６−１〜５０６−４の各々には、１つの行グループが対応付けられる。
【０２２１】
次に、本実施の形態に係るＬＤＰＣ復号器５００の行処理演算器５０６の動作について説明する。
【０２２２】
各行処理演算器５０６は、最大で４つの列グループを１クロックサイクルで処理する。また、上述したように、各行処理演算器５０６は、最大で２つの行グループに対応する。よって、各行処理演算器５０６に含まれる最小値選択回路（最小値選択回路２００又は３００）は、図８に示す動作モードに応じて、同時に入力されるデータを、最大２つの行グループにグループ分けし、各グループの第１最小値及び第２最小値を求める。
【０２２３】
図３６Ａは、従来技術を用いた場合の行処理演算の動作タイミングを示すタイミングチャートであり、図３６Ｂは、本実施の形態に係る行処理演算器５０６の動作タイミングを示すタイミングチャートである。
【０２２４】
ここでは、４つの行グループに対する行処理演算を行う場合について説明する。
【０２２５】
図３６Ａに示す従来技術（例えば、図１を参照）では、１つの行グループに含まれる最大１６個のデータが１クロックサイクルで入力される。しかし、上述したようにパイプライン遅延が２クロックサイクル必要となるので、１つの行グループに対して、３クロックサイクルを要する。したがって、図３６Ａに示すように、４つの行グループに含まれる最大６４個のデータを処理するためには、６クロックサイクルを要する。
【０２２６】
これに対して、本実施の形態に係るＬＤＰＣ復号器５００の複数の行処理演算器５０６は、各々が最大で２つの行グループの行処理演算を行うので、図３６Ｂに示すように４つの行処理演算が並列に処理される。
【０２２７】
また、１つの行処理演算器５０６は、１クロックサイクルで４つのデータを同時に入力できる。したがって、１つの行グループに含まれる最大１６個のデータを処理するためには、４クロックサイクルを要する。
【０２２８】
すなわち、本実施の形態によれば、１クロックサイクルにつき、全ての列のうち一部の列に対する処理を行うものの、複数の行グループに対する処理を並列に行うことができるので、全体の処理に要する動作クロック（すなわち遅延）を低減することができる。
【０２２９】
つまり、本実施の形態によれば、実施の形態１〜３で述べたように、行処理演算器５０６に含まれる最小値選択回路において縦列に接続される比較器の段数を低減し、かつ、パイプラインレジスタを不要又は低減することで、パイプライン遅延を低減できる。このため、本実施の形態では、従来技術と比較して、ＬＤＰＣ復号処理（最小値選択処理）を短い遅延で高速に行うことができる。
【０２３０】
ここで、従来技術に係る構成（図１を参照）を２個以上用いることにより遅延の短縮を図ることは可能である。例えば、図１に示す構成の最小値選択回路を２個用いることにより、処理遅延を４クロックサイクルにすることができる。しかしながら、このように処理能力を向上させるためには、従来技術では、行処理演算器（最小値選択回路）に対して、クロックサイクルあたり３２個のデータを同時に供給しなければならない。
【０２３１】
すなわち、従来技術では、本実施の形態に係る最小値選択回路５００と同様の処理能力を得るには、行処理演算器でなく、列処理演算器、シフタなどのＬＤＰＣ復号器に含まれる回路の並列度を２倍に増加させる必要があり、回路規模の増大を招いてしまう。
【０２３２】
このように、本実施の形態によれば、処理速度及び遅延の制約を従来技術と同一条件とした場合、従来技術と比較して回路規模を低減できる。換言すると、本実施の形態によれば、回路規模の制約を従来技術と同一条件とした場合、従来技術と比較して低遅延かつ高速動作を実現できる。
【０２３３】
また、従来技術では、ＬＤＰＣ復号器（最小値選択回路）に１６個のデータを一度に入力する必要があるのに対して、本実施の形態では、ＬＤＰＣ復号器５００（最小値選択回路２００又は３００）に１６個のデータを４個ずつ分割して入力することができる。これにより、ＬＤＰＣ復号器５００において、１６個のデータを一度に処理する必要のある従来技術と比較して、列処理演算器５０３の構成を簡易で効率的な構成とすることができる。
【０２３４】
より詳細には、列処理演算は、検査行列の列内のデータを組み合わせて加減算を行う演算である。本実施の形態では、ＬＤＰＣ復号器５００が列処理演算器５０３を４つ備え（図３２を参照）、各々が１クロックサイクルにつき１つの列グループ（つまり、全体で４個の列グループ）を処理する構成とした。このため、列処理演算器５０３では、一時記憶のためのレジスタなどが不要となり、加減算の簡易な構成を採ることが可能となる。
【０２３５】
このように、１列以上の列処理演算を１クロックサイクルで行うＬＤＰＣ復号器は、「列並列ＬＤＰＣ復号器」又は「列ベース部分並列ＬＤＰＣ復号器」と呼ばれることもある。
【０２３６】
本開示の一態様に係るＬＤＰＣ復号器は、列並列ＬＤＰＣ復号器に適した回路である。
【０２３７】
上述したように本実施の形態に係るＬＤＰＣ復号器５００では、４個の列処理演算器５０３によって１クロックサイクルにつき４つの列グループ（１列グループあたり非零のサブマトリックスが最大４個）の列処理演算を行うのに対して、各行処理演算器５０６は、１クロックサイクルにつき４個のデータを入力することができる。つまり、ＬＤＰＣ復号器５００では、列処理演算器５０３から行処理演算器５０６へ過不足なくデータを供給することができる。
【０２３８】
一方、従来技術の行処理演算器における最小値選択回路のように、行グループの１６個のデータを一度に供給する必要があるＬＤＰＣ復号器は、「行並列ＬＤＰＣ復号器」又は「行ベース部分並列ＬＤＰＣ復号器」と呼ばれることもある。
【０２３９】
行並列ＬＤＰＣ復号器では、本来列グループ単位で行うべき列処理演算を、行グループ単位でデータ出力されるように工夫する必要がある。このため、列処理演算器においてデータを一時的に記憶するレジスタ、メモリ又はアキュムレータを備える方法が知られているが、これらは、列並列ＬＤＰＣ復号器における列処理演算器と比較して複雑な構成かつ回路規模が大きくなってしまう。
【０２４０】
以上より、本実施の形態において、ＬＤＰＣ復号器５００では、実施の形態２又は３と同様にして行処理演算器５０６での比較器の数を低減できるので、複数の検査行列に対応しつつ、行処理演算器４０６の処理を高速に動作させることができる。また、ＬＤＰＣ復号器５００では、従来技術と比較して列処理演算器の構成を簡易にすることができるので回路規模の増大を防ぐことができる。
【０２４１】
以上、本開示の一態様に係る各実施の形態について説明した。
【０２４２】
なお、上記実施の形態では、最小値選択回路に対して同時に入力されるデータ数は、２個（実施の形態１）又は４個（実施の形態２）に限定されず、２個及び４個以外の数でもよい。
【０２４３】
また、上記実施の形態では、最小値選択回路に入力される複数のデータが２つのグループの何れかに属する場合を一例として説明したが、複数のデータが属するグループの数は２個に限定されず、２個以外の数のグループでもよい。
【０２４４】
上記実施の形態では、本開示をハードウェアで構成する場合を例にとって説明したが、本開示はハードウェアとの連携においてソフトウェアによって実現することも可能である。
【０２４５】
また、上記実施の形態の説明に用いた各機能ブロックは、典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部又は全てを含むように１チップ化されてもよい。ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【０２４６】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路又は汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサを利用してもよい。
【０２４７】
さらには、半導体技術の進歩又は派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適用等が可能性としてありえる。
【産業上の利用可能性】
【０２４８】
本開示の一態様は、ＬＤＰＣ符号を用いる復号器等に適用できる。
【符号の説明】
【０２４９】
１００、２００，３００  最小値選択回路
１０１，１０１ａ，１０１ｂ，１０２，１０２ａ，１０２ｂ  選択部
１０３，１０３ａ，１０３ｂ，１０４，１０４ａ，１０４ｂ  記憶部
１０５，１０５ａ，１０５ｂ，２０１  総当たり比較部
１０６，１０６ａ，１０６ｂ  動作モード指示部
１０７，１０７ａ，１０７ｂ，２０２  第１選択比較部
１０８，１０８ａ，１０８ｂ，２０３  第２選択比較部
１０９，１０９ａ，１０９ｂ，２０６  判定部
１３１，１３１ａ，１３１ｂ，１４１，１４１ａ，１４１ｂ  第１最小値記憶部
１３２，１３２ａ，１３２ｂ，１４２，１４２ａ，１４２ｂ  第２最小値記憶部
１５１、１５１ａ，１５１ｂ，１７３，１７３ａ，１７３ｂ，１７４，１７４ａ，１７４ｂ，１８３，１８３ａ，１８３ｂ，１８４，１８４ａ，１８４ｂ  比較器
１７１，１７１ａ，１７１ｂ，１７２，１７２ａ，１７２ｂ，１８１，１８１ａ，１８１ｂ，１８２，１８２ａ，１８２ｂ  選択部
２０４  第３選択比較部
２０５  第４選択比較部
３０１  前処理部
３０２  最小値選択部
４００，５００  ＬＤＰＣ復号器
４０１，５０１  入力メモリ
４０２，５０２  出力メモリ
４０３，５０３  列処理演算器
４０４，４０９，５０４，５０９  シフタ
４０５，４０８，５０５，５０８  データ転送部
４０６，５０６  行処理演算器
４０７，５０７  後処理部
４１０  制御部
４６１  演算器
４６２，４６３  分配器
４６４，４６５  符号算出回路
４６６，４６７  レジスタ
４８１  セレクタ
【図１】
0006511284.tif 000008
【図２】
0006511284.tif 000009
【図３】
0006511284.tif 000010
【図４】
0006511284.tif 000011
【図５】
0006511284.tif 000012
【図６】
0006511284.tif 000013
【図７】
0006511284.tif 000014
【図８】
0006511284.tif 000015
【図９】
0006511284.tif 000016
【図１０】
0006511284.tif 000017
【図１１】
0006511284.tif 000018
【図１２】
0006511284.tif 000019
【図１３】
0006511284.tif 000020
【図１４】
0006511284.tif 000021
【図１５】
0006511284.tif 000022
【図１６】
0006511284.tif 000023
【図１７】
0006511284.tif 000024
【図１８】
0006511284.tif 000025
【図１９】
0006511284.tif 000026
【図２０】
0006511284.tif 000027
【図２１】
0006511284.tif 000028
【図２２】
0006511284.tif 000029
【図２３】
0006511284.tif 000030
【図２４】
0006511284.tif 000031
【図２５】
0006511284.tif 000032
【図２６】
0006511284.tif 000033
【図２７】
0006511284.tif 000034
【図２８】
0006511284.tif 000035
【図２９】
0006511284.tif 000036
【図３０】
0006511284.tif 000037
【図３１】
0006511284.tif 000038
【図３２】
0006511284.tif 000039
【図３３】
0006511284.tif 000040
【図３４】
0006511284.tif 000041
【図３５】
0006511284.tif 000042
【図３６】
0006511284.tif 000043