(57)【要約】  【課題】  評価関数の最小化（または最大化）に対応する最適解、最適値、解の存在判定信号を求める回路を組合せ回路として実現することで、回路規模が小さく、遅延の少ない最適決定回路を実現し、通信分野などにおいて低消費電力で高速処理が可能な復号回路を提供する。  【解決手段】  評価関数の入力変数である係数とパラメータに対して、対応関係を調べるコンピュータプログラムによる手段または評価関数の最適解（最小値または最大値）に対する値と他のパラメータに対する値との引算の最上位キャリーの性質から成り立つブール方程式を解く手段により、入力を係数（および解変数）とし、出力を最適解、最適値、解存在条件とする論理関数を求め、組合せ回路として実現する。【選択図】図１
2005333500.tif 000002
【特許請求の範囲】
【請求項１】
係数およびパラメータを入力変数として定義された評価関数の値が、制約条件有り（または制約条件無し）で最適値である最小値（または最大値）になる入力パラメータを求める問題を対象とし、組合せ回路で実現した係数（および解変数）を入力とし、最適解を出力とする最適解決定回路、（および／または）最適値を出力する最適値決定回路、（および／または）ｐ個解存在条件信号を出力とするｐ個解存在条件回路、（および／または）解存在条件信号を出力する解存在条件回路を具備することを特徴とする最適決定回路。
【請求項２】
請求項１記載のパラメータをｎビットのＸ＝（ｘｎ−１，…，ｘ０）、係数をＭビットのＣ＝（ｃｎ−１，…，ｃ０）、評価関数がｌビットの数Ｅ（Ｘ，Ｃ）として表され、制約条件等価ブール方程式がｈ（Ｘ，Ｃ）＝０（制約条件無しでは常にｈ（Ｘ，Ｃ）＝０は成立）なる時、パラメータＸ，Ｙに対する引算を、最小値に対してはＥ（Ｘ，Ｃ）−Ｅ（Ｙ，Ｃ）、最大値に対してはＥ（Ｙ，Ｃ）−Ｅ（Ｘ，Ｃ）と考え、引算を行った時にｌビット目に現れるキャリー論理関数をｃｌ（Ｘ，Ｙ，Ｃ）とし、
【数１】
2005333500.tif 000030
なる論理関数を作成し、
【数２】
2005333500.tif 000031
をＸに就いてのブール方程式として解くことによって得られる係数Ｃの論理関数であるＸ０＝Ｆ０（Ｃ）および／または解存在条件の論理関数ｓｌ（Ｃ）から、組合せ回路で実現した最適解決定回路および／または唯一解存在条件回路を具備することを特徴とする請求項１記載の最適決定回路。
【請求項３】
請求項１記載のパラメータをｎビットのＸ＝（ｘｎ−１，…，ｘ０）、係数をｍビットのＣ＝（ｃｍ−１，…，ｃ０）、評価関数がｌビットの数Ｅ（Ｘ，Ｃ）として表され、制約条件等価ブール方程式がｈ（Ｘ，Ｃ）（制約条件無しでは常にｈ（Ｘ，Ｃ）＝０は成立）なる時、パラメータＸ，Ｙに対する引算を、最小値に対してはＥ（Ｙ，Ｃ）−Ｅ（Ｘ，Ｃ）、最大値に対してはＥ（Ｘ，Ｃ）−Ｅ（Ｙ，Ｃ）と考え、引算を行った時にｌビット目に現れるキャリー論理関数をｃ（Ｘ，Ｙ，Ｃ）とし、
【数３】
2005333500.tif 000032
なる論理関数を作成し、
【数４】
2005333500.tif 000033
をＸに就いてのブール方程式として解くことにより得られる係数Ｃと解変数Ｕ＝（ｕｎ−１，…，ｕ０）の論理関数であるＸ０＝Ｆ０（Ｃ，Ｕ）および／または解存在条件の論理関数ｓ（Ｃ）から、組合せ回路で実現した最適解決定回路および／または解存在条件回路を具備することを特徴とする請求項１記載の最適決定回路。
【請求項４】
数値に対する等式および／または不等式で表された最適化問題の制約条件を、等価なブール方程式
【数５】
2005333500.tif 000034
で構成し、請求項２乃至請求項３記載のブール方程式を作成したことを特徴とする請求項２乃至請求項３記載の最適決定回路。
【請求項５】
最適解決定回路の論理関数と評価関数の論理関数を論理合成することにより、組合せ回路で実現した係数を入力とし最小値（または最大値）を出力とする最適値決定回路を具備することを特徴とする請求項１記載の最適決定回路。
【請求項６】
請求項１乃至請求項４記載の最適解決定回路と最適解を入力とする評価関数論理回路を具備し、前記最適解決定回路の出力を評価関数論理回路の入力とすることで、最適解および最適値（最小値または最大値）を同時に出力することを可能にする請求項１記載の最適決定回路。
【請求項７】
最適解を１つまたは限定した複数種に絞り、入力変数を係数と解変数の制約された変数だけにし回路を簡単化した組合せ回路を具備することを特徴とする請求項１または請求項６記載の最適決定回路。
【請求項８】
請求項１乃至請求項７記載の最適決定回路を具備し、当該最適決定回路の出力から（またはさらに所定の処理を経て）復号結果を得る構成を特徴とする復号回路。
【請求項９】
最適解決定回路および唯一解存在条件回路（および唯一解存在条件回路の出力を反映する係数を変更する処理回路）を具備することを特徴とする請求項８記載の復号回路。
【請求項１０】
解変数の値に応じ出力される複数の復号結果を出力する最適決定回路（および外符号復号誤り判定選択回路）を具備し、復号誤り率を削減することを特徴とする請求項８記載の復号回路。
【請求項１１】
時系列データである受信データをブロック単位に分割し、過去の復号結果から得られる情報を記憶する記憶素子を具備し、前記情報とブロック内の受信データを請求項１乃至請求項４または請求項７記載の最適決定回路の入力とすることを特徴とする請求項８乃至請求項１０記載の復号回路。
【請求項１２】
時系列データをブロック単位に分割する時に、ブロック周期時間をブロック長よりも短くし、前後のブロックでオーバーラップさせ、最適決定回路の出力は次のブロックとの重なりが無い時間分だけとすることで、最適決定回路の回路規模を削減することを特徴とする請求項１１記載の復号回路。
【請求項１３】
最適決定回路を多段の組合せ回路の縦続接続に分解し、各段にパイプラインレジスタを設け、複数の受信データをパイプライン処理し、複数の受信データの処理を可能としたことを特徴とする請求項８乃至請求項１１記載の復号回路。
【請求項１４】
複数系統の受信データを時分割で最適決定回路に送り込み、複数系統の受信データの復号処理を可能としたことを特徴とする請求項８乃至請求項１２記載の復号回路。
【請求項１５】
複数種の符号化方式に対応した評価関数と切替係数とから合成評価関数を作成し、前記評価関数の係数および切替係数を全体の入力係数とし復号結果を出力とする最適決定回路を請求項１乃至請求項７により実現し、当該最適決定回路および符号化方式コントロール回路を具備することを特徴とする請求項８乃至請求項１４記載の復号回路。
【請求項１６】
畳込み符号の生成多項式形状係数とパンクチャ・モード係数および請求項８乃至請求項１４記載の係数を合わせたものを全体の入力係数とし復号結果を出力とする最適決定回路を請求項１乃至請求項７により実現し、当該最適決定回路および生成多項式コントロール回路（および／またはパンクチャ−モード・コントロール回路）を具備することを特徴とする請求項８乃至請求項１４記載の復号回路。
【請求項１７】
請求項１６における生成多項式形状係数およびパンクチャ−係数を限定することで回路を簡単化したことを特徴とする請求項１５記載の復号回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、評価関数の最適値（最小値または最大値）に対応する最適解および／または最適値および／またはｐ個解存在判定信号および／または解存在信号を出力する組合せ回路および当該組合せ回路により実現する復号回路に関する。
【背景技術】
【０００２】
評価関数が与えられた時に、評価関数の最適値（最小値または最大値）に対応する変数（および／または最適値）を決定する問題は、最適化問題として古くから研究されて来た。これらの最適化問題の従来の解法は、最急降下法や線形計画法やニューラルネットなどの探索的な方法が用いられている。
【０００３】
そして無線通信、有線通信、記録メディア、画像処理、音声処理などの多くの分野で必要とされるリアルタイムの最適化問題の解法にもこの探索的な解法が採用され、逐次処理の回路として実現されている。例えば探索的な従来方法として特許文献１の高速最適化回路などがある。
【０００４】
またその代表的な最適解を求める回路の１つは、無線通信、有線通信、記録メディアなどで用いられるビタビ復号アルゴリズムに代表される復号回路である。
【特許文献１】特開平１０−２４７１８６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００５】
一般に最適化問題の逐次処理的な解法はメモリ、比較器、演算器などを多用する為に、高速処理には不向きであり、ＬＳＩとして実現した場合には消費電力や回路規模の問題がある。
【０００６】
また畳込み符号に対する前述のビタビ復号回路は、畳込み符号の拘束長Ｋを増やすに従いビット誤り率が小さくなることが知られていが、符号化率や計算精度およびスループットを同じとした場合には回路規模は２ｋに比例して大きくなると云う問題がある。その為、コンシューマの用途のＬＳＩでは、Ｋ＝７が実用化の現時点の限界になっている。
【０００７】
また異なる符号化方式の１つとして近年注目されているものにターボ符号化方式がある。この復号回路は性能／回路規模では優れた方式と言われているが、繰返し処理に因る大きな遅延が避けられないと云う問題がある。
【０００８】
本発明は、このような問題点を解決するためになされたもので、回路規模、遅延が小さく高速な最適決定回路を実現し、最適化問題解法の性能／回路規模の高いソリューションを提供し、また低消費電力、低コスト、高速な復号回路を実現し、高速通信や、高密度な記録メディアに対してよりビット誤り率の少ない高性能、高速な復号回路を提供することを目的とする。
【課題を解決するための手段】
【０００９】
本発明の請求項１から請求項７の最適決定回路は、係数およびパラメータを入力変数として定義された評価関数が制約条件有り（または制約条件無し）で最小値（または最大値）になる入力パラメータを最適解として求める最適解決定問題と、前記最適解に対応する最適値（最小値または最大値）そのものを求める最適値決定問題と、各係数に対してｐ個の解が存在することを判定するｐ個解存在問題（ｐ＝１の場合を唯一解存在問題とする）と、制約条件が有る場合の解存在問題を対象にしている。
【００１０】
以後、混乱が無い場合には最適解決定問題、最適値決定問題、ｐ個存在問題、解存在問題をまとめて最適決定問題と呼び、また同様に最適解決定回路、最適値決定回路、ｐ個解存在判定回路、解存在判定回路をまとめて最適決定回路と呼ぶことにする。
【００１１】
［請求項１の発明］
請求項１の発明は、係数およびパラメータを入力変数として定義された評価関数の値が、制約条件有り（または制約条件無し）で最適値である最小値（または最大値）になる入力パラメータを求める問題を対象とし、組合せ回路で実現した係数（および解変数）を入力とし、最適解を出力とする最適解決定回路、（および／または）最適値を出力する最適値決定回路、（および／または）ｐ個解存在条件信号を出力とするｐ個解存在条件回路、（および／または）解存在条件信号を出力する解存在条件回路を最適決定回路として具備することを特徴とする。
【００１２】
請求項１の最適決定回路の１つの設計手段は、評価関数の算術値からフローに従い、コンピュータプログラムにより最適解（および／または最適値、および／またはｐ個解存在条件信号および／または解存在条件信号）を出力とする論理関数を生成することを特徴とする。
【００１３】
［請求項２の発明］
請求項２の発明は、請求項１記載のパラメータをｎビットのＸ＝（ｘｎ−１，…，ｘ０）、係数をＭビットのＣ＝（ｃｎ−１，…，ｃ０）、評価関数がｌビットの数Ｅ（Ｘ，Ｃ）として表され、制約条件等価ブール方程式がｈ（Ｘ，Ｃ）＝０（制約条件無しでは常にｈ（Ｘ，Ｃ）＝０は成立）なる時、パラメータＸ，Ｙに対する引算を、最小値に対してはＥ（Ｘ，Ｃ）−Ｅ（Ｙ，Ｃ）、最大値に対してはＥ（Ｙ，Ｃ）−Ｅ（Ｘ，Ｃ）と考え、引算を行った時にｌビット目に現れるキャリー論理関数をｃｌ（Ｘ，Ｙ，Ｃ）とし、
【数６】
2005333500.tif 000003
なる論理関数を作成し、
【数７】
2005333500.tif 000004
をＸに就いてのブール方程式として解くことによって得られる係数Ｃの論理関数であるＸ０＝Ｆ０（Ｃ）および／または解存在条件の論理関数ｓｌ（Ｃ）から組合せ回路で最適解決定回路（および／または唯一解存在条件回路）を実現することを特徴とする。
【００１４】
請求項２の発明では、上述の組合せ回路として実現した最適解決定回路（および／または唯一解存在条件回路）を具備することを特徴とする。
【００１５】
［請求項３の発明］
請求項３の発明は、請求項１記載のパラメータをｎビットのＸ＝（ｘｎ−１，…，ｘ０）、係数をｍビットのＣ＝（ｃｍ−１，…，ｃ０）、評価関数がｌビットの数Ｅ（Ｘ，Ｃ）として表され、制約条件等価ブール方程式がｈ（Ｘ，Ｃ）（制約条件無しでは常にｈ（Ｘ，Ｃ）＝０は成立）なる時、パラメータＸ，Ｙに対する引算を、最小値に対してはＥ（Ｙ，Ｃ）−Ｅ（Ｘ，Ｃ）、最大値に対してはＥ（Ｘ，Ｃ）−Ｅ（Ｙ，Ｃ）と考え、引算を行った時にｌビット目に現れるキャリー論理関数をｃ（Ｘ，Ｙ，Ｃ）とし、
【数８】
2005333500.tif 000005
なる論理関数を作成し、
【数９】
2005333500.tif 000006
をＸに就いてのブール方程式として解くことにより得られる係数Ｃと解変数Ｕ＝（ｕｎ−１，…，ｕ０）の論理関数であるＸ０＝Ｆ０（Ｃ，Ｕ）および／または解存在条件の論理関数ｓ（Ｃ）から組合せ回路で最適解決定回路（および／または解存在条件回路）を実現することを特徴とする。
【００１６】
請求項３の発明では、上述の組合せ回路として実現した最適解決定回路（および／または解存在条件回路）を具備することを特徴とする。
【００１７】
［請求項４の発明］
請求項４の発明は、数値に対する等式および／または不等式で表された最適化問題の制約条件を、等価なブール方程式
【数１０】
2005333500.tif 000007
で構成し、請求項２乃至請求項３記載のブール方程式を作成し、これを解くことによって請求項２乃至請求項３記載の最適決定回路を実現することを特徴とする。
【００１８】
請求項４の発明では、上述の組合せ回路として実現した請求項２乃至請求項３記載の最適決定回路を具備することを特徴とする。
【００１９】
［請求項５の発明］
請求項５の発明は、最適解決定回路の論理関数と評価関数の論理関数を論理合成することにより、係数を入力とし最小値（または最大値）を出力とする最適値決定回路を組合せ回路として実現することを特徴とする。
【００２０】
請求項５の発明では、上述の組合せ回路として実現した請求項１記載の最適決定回路を具備することを特徴とする。
【００２１】
［請求項６の発明］
請求項６の発明は、請求項１乃至請求項４記載の最適解決定回路の出力を評価関数論理回路の入力とすることで、最適解および最適値（最小値または最大値）を同時に出力することが可能な構成の組合せ回路を実現することを特徴とする。
【００２２】
請求項６の発明では、上述の組合せ回路として実現した請求項１記載の最適決定回路を具備することを特徴とする。
【００２３】
［請求項７の発明］
請求項７の発明は、請求項１または請求項６記載の最適解を１つまたは限定した複数種に絞り、入力変数を係数と解変数の制約された変数だけにすることで最適解決定回路を簡単化した組合せ回路として実現することを特徴とする。
【００２４】
請求項７の発明では、上述の組合せ回路として実現した請求項１乃至請求項６記載の最適決定回路を具備することを特徴とする。
【００２５】
次に本発明の復号回路に関する請求項８乃至請求項１７の手段に就いて述べる。
【００２６】
［請求項８の発明］
請求項８の発明は、組合せ回路として実現された請求項１乃至請求項７記載の最適決定回路を具備し、当該最適決定回路の出力から（またはさらに所定の処理を経て）復号結果を得ることを特徴とする。
【００２７】
［請求項９の発明］
請求項９の発明は、最適解決定回路および唯一解存在条件回路（および唯一解存在条件回路の出力を反映する係数を変更する処理回路）を具備することを特徴とする。
【００２８】
［請求項１０の発明］
請求項１０の発明は、解変数に応じた複数の解を出力する最適解決定回路（および外符号復号誤り判定選択回路）を具備し、復号誤り率を低減することを特徴とする。
【００２９】
［請求項１１の発明］
請求項１１の発明は、係数が時系列データとして入力される場合を対象とし、時系列データである受信データをブロック単位に分割し、過去の復号結果から得られる情報を記憶する記憶素子を具備し、過去の復号結果から得られる情報とブロック内の受信データを請求項１乃至請求項４または請求項７記載の最適解決定回路の入力とすることで復号器を実現することを特徴とする。
【００３０】
［請求項１２の発明］
請求項１２の発明は、時系列データをブロック単位に分割する時に、ブロック周期時間をブロック長よりも短くし、前後のブロックでオーバーラップさせ、入力は請求項１１と同じとし、出力変数は次のブロックとの重なりが無い時間分だけとすることで最適解決定回路の出力論理関数を減らし、最適決定回路の規模を削減することを特徴とする。
【００３１】
［請求項１３の発明］
請求項１３の発明は、最適決定回路を多段の組合せ回路の縦続接続に分解し、各段にパイプラインレジスタを設け、複数の受信データをパイプライン処理し、複数の受信データの処理を可能とすることを特徴とする。
【００３２】
［請求項１４の発明］
請求項１４の発明は、最適決定回路の遅延時間がブロック周期時間より十分小さい時に、複数系統の受信データを時分割で最適決定回路に送り込み、複数系統の受信データの復号処理を可能とすることを特徴とする。
【００３３】
［請求項１５の発明］
請求項１５の発明は、複数種の符号化方式に対応した評価関数と切替係数とから合成評価関数を作成し、前記評価関数の係数および切替係数を全体の入力係数とし復号結果を出力とする最適決定回路を請求項１乃至請求項７により実現することを特徴とする。
【００３４】
請求項１５の発明では、上述の組合せ回路として実現した最適決定回路および符号化方式コントロール回路を具備することを特徴とする。
【００３５】
［請求項１６の発明］
請求項１６の発明は、畳込み符号の生成多項式形状係数とパンクチャ・モード係数および請求項８乃至請求項１４記載の係数を合わせたものを全体の入力係数とし復号結果を出力とする最適決定回路を請求項１乃至請求項７により実現することを特徴とする。
【００３６】
請求項１６の発明では、上述の組合せ回路として実現した最適決定回路および生成多項式コントロール回路（および／またはパンクチャ−モード・コントロール回路）を具備することを特徴とする。
【００３７】
［請求項１７の発明］
請求項１７の発明は、請求項１６における生成多項式形状係数およびパンクチャ−係数を限定することで回路を簡単化することを特徴とする。
【００３８】
請求項１７の発明では、前記請求項１７の設計手段により組合せ回路として実現した最適決定回路および生成多項式コントロール回路（および／またはパンクチャ−モード・コントロール回路）を具備することを特徴とする。
【発明の効果】
【００３９】
本発明の最適決定回路は、対応関係を明確なフローにより記述したプログラム処理や最適解が満足するブール方程式に基づき最適解論理式、最適値論理式、ｐ個解存在条件論理式、解存在条件論理式を求める手段により、最適解決定回路、最適値決定回路、Ｐ個解存在条件回路、解存在条件回路を全て組合せ回路として実現することを特徴としていることから、中間データ用の記憶素子を必要とせず、逐次処理に必要な比較回路や制御回路などを必要とせず、回路が簡単化でき、１サイクルで結果を出す構成が可能であり、解変数により複数の最適解を求めることができる。
【００４０】
また本発明の復号回路は、組合せ回路として実現された前記の最適決定回路を採用した復号器であることから、回路規模が小さく、また１サイクルで復号結果を出す構成が可能であり、さらにパイプライン処理や時分割処理に対して自由度の大きな設計が可能となり、時系列データにおいては、高速処理や、複数系統の処理が可能となり、さらに解変数による複数の復号結果を出すことが可能であり、復号誤り率の小さな復号器の実現などが可能で、さらに符号化方式の違いや、パンクチャドの違いなどを最適解決定回路の入力係数の違いに対応させることができることから、複数の符号化方式や複数のパンクチャド方式に対して回路規模の増大を最低限に押さえた復号器が実現できる。
【発明を実施するための最良の形態】
【００４１】
以下、この発明について詳細に説明する。
【００４２】
【表１】
2005333500.tif 000008
【００４３】
［発明の構成］
以下、この発明の構成を図と式に基づいて詳しく説明する。
【００４４】
本発明の最適決定回路が対象とする最適化問題は、係数およびパラメータを入力変数として定義された評価関数が制約条件無し（または制約条件有り）で最適値（最小値または最大値）になる入力パラメータを最適解として求め、または最適値そのものを求める問題を対象にする。
【００４５】
この最適化問題の変数と評価関数（および制約条件）が２値表現された場合に就いて述べると、制約条件無しの場合には、ｎビットのパラメータＸ＝（ｘｎ−１，…，ｘ０）およびｍビットの係数Ｃ＝（ｃｍ−１，…，ｃ０）を入力変数として定義されたｌビットの数値を表す評価関数Ｅ（Ｘ，Ｃ）＝（ｅｌ−１（Ｘ，Ｃ），…，ｅ０（Ｘ，Ｃ））がある場合には、与えられた係数Ｃに対して最適値Ｅ０（最小値または最大値）となる入力パラメータＸ０（最適解）を求める問題になる。
【００４６】
制約条件有りの場合には、パラメータＸ＝（ｘｎ−１，…，ｘ０）および係数Ｃ＝（ｃｍ−１，…，ｃ０）の一部または全部を入力変数として定義されたｌビットの数値を表す評価関数Ｅ（Ｘ，Ｃ）＝（ｅｌ−１（Ｘ，Ｃ），…，ｅ０（Ｘ，Ｃ）および１つのブール方程式ｈ（Ｘ，Ｃ）＝０に等価な制約条件式に対して、与えられた係数Ｃに対して制約条件の下に最適値Ｅ０（最小値または最大値）となる入力パラメータＸ０（最適解）を求める問題になる。ここにＥ０，Ｘ０の添え字「Ｏ」はOptimal（最適な）の意味で付した。
【００４７】
以下２値論理に限定して説明するが、多値表現された場合も全く同様で、論理関数が多値論理関数になる違いがあるだけであり、設計段階では２値で論理関数を設計し、多値論理関数に変換すれば、以下に述べることは全て多値に移行できる。
（多値論理については樋口龍雄他著“多値情報処理”を参照）
【００４８】
［請求項１の構成］
図１は本発明の最適解決定回路ブロック図である。本発明の最適決定回路の基本は、図１に示すように入力を係数101（および解変数102）、出力を最適解104とした組合せ回路103で構成された最適決定回路である。尚、図１中では入力の解変数102が無い場合には破線矢印は無くなる。
【００４９】
図２は本発明の最適値決定回路ブロック図である。図２に示すように入力を係数201、出力を最適値203とした組合せ回路202で構成された最適値決定回路である。
【００５０】
図３は本発明のｐ個解存在判定回路ブロック図である。図３に示すように入力を係数301、出力をｐ個解存在判定信号303とした組合せ回路302で構成された最適決定回路である。
【００５１】
図４は本発明の解存在判定回路ブロック図である。図４に示すように入力を係数401、出力を解存在判定信号403とした組合せ回路402により構成された最適決定回路である。
【００５２】
本発明の基本的な構成は図１から図４のように全ての回路を組合せ回路として実現する点である。
【００５３】
以下本発明の最適決定回路の構成を詳述する。
【００５４】
評価関数はＸ，Ｃに対して１つの値が対応しており、
【表２】
2005333500.tif 000009
しかし各係数毎の最適値Ｅ０はパラメータの自由度がある為にそのままでは求めることはできない。さらにパラメータの一部である最適解は評価関数の入力側であることから、従来は最適解Ｘ０を論理関数の出力として表すという問題意識さえ無かったと考えられる。
【００５５】
従来の最適化回路などが探索的な方法を採用している理由の根源はここにあると考えられる。
【００５６】
本発明の最も新規な点は、最適解を論理関数の出力になるようにし、組合せ回路として実現する点にある。以下この組合せ回路としての実現の根幹を成す考えを示す。
【００５７】
評価関数の数値表現は本質的には何ら変わらないので、以下では値（ｅｌ−１，…，ｅ０）は非負整数を表すものとして説明する。
【００５８】
先ず前記評価関数Ｅ（Ｘ，Ｃ）は係数Ｃ毎の論理関数として考えることができる。この時、ＸがＢｎ全体を動いた場合に、制約条件無しの場合でも制約条件有りの場合でも、とり得る値の最適値（最小値または最大値）は、唯一の値であることは明白である。
従って評価関数の最適値Ｅ０は係数Ｃの関数と考えることができる。つまり２値表現ではＥ０＝Ｅ０（Ｃ）なる論理関数として表すことができる。
【００５９】
一方、この最適値Ｅ０に対応する最適解は必ずしも１つとは限らないが、制約条件無しの場合には明らかに少なくとも１つは存在する。従ってＣに対して唯一つ存在する最適解を求める場合に焦点を当てれば、その最適解Ｘ０はＣの論理関数として表すことができる。その時唯一の最適解が存在するＣは一般には限定される。このことは唯一解存在信号がＣの論理関数として表せることを意味する。
【００６０】
従ってコンピュータを利用するなどで、各Ｃ毎の最適値Ｅ０と同時に対応するパラメータの値Ｘ０が１個かどうかを調べることで、論理関数Ｘ０＝Ｆ０（Ｃ）と唯一解存在論理関数を導くことができる。
【００６１】
次にこの最適値に対応するパラメータが必ずしも１つで無い一般的な場合に就いて、図５に基づき説明する。図５は最適値は最小値とした例の評価関数真理値表である。図５においては、Ｃ＝(0,……,0,0)ではＸの値が(0,……,1,0)と(1,……,1,1)の２箇所で最適値Ｅ０＝(0,……,0,1,1)＝3をとり、Ｃ＝(0,……,0,1)ではＸの値が(0,……,1,0)の１箇所だけで最適値Ｅ０＝(0,……,1,0,0)＝4をとり、・・・・・・・、
Ｃ＝(1,……,1,1)ではＸの値が(0,……,0,0)と(0,……,1,0)と(1,……,1,0)の３箇所で最適値Ｅ０（Ｃ）＝(0,……,1,0,1)＝5をとる例を示している。（Ｃの途中は省略してある。）
【００６２】
従ってこの場合には、１つのＣに対して複数の最適解が対応し、１対多対応になっている。このことから、このままでは論理関数として表すことができないことが分かる。
【００６３】
そこで最適解の違いを表す解変数を導入する。その方法は各Ｃの最適解の数をＮＣとすると、Ｎｍａｘ＝ｍａｘ  ｃ｛ＮＣ｝を求め、Ｎｍａｘ＜＝２Ｓなる非負整数Ｓ個の解変数Ｕ＝（ｕｓ−１，…ｕ０）を導入する。図５では「丸印」を付した場所が最適値に対応するとして表しているので、Ｃ＝(0,……,0,0), (0,……,0,1), (1,……,1,1)に対応しＮＣ=2,1…,3のようになる。
Ｃの途中に最大数のＮｍａｘ＝４の箇所があるとすると、解変数の数はＳ＝２とすればよいのでＵ＝（ｕ１，ｕ２）となる。このように解変数を導入し、各Ｃ毎の２Ｓ種のＵに最適解Ｘ０を割り付け、全ての最適解Ｘ０が少なくとも１つの解変数Ｕに割り付けられるようする。
【００６４】
図６は図５の例に対する最適解の解変数への割り付け図である。図６の割り付けは、Ｕ，Ｘを非負整数と見なした時に、Ｘの小さい方から順にみて最適解をＵの小さい順に割り付け、与えられたＣで最適解の数がＮｍａｘ＝４未満の場合には、最後に現れた最適解を最後まで割り付けて行く方法をとった。この割り付けは一意ではなく、多くの変形があることは当然である。
【００６５】
このように最適解の解変数への割り付けを行うことで、各（Ｃ，Ｕ）に１つの最適解Ｘ０を対応させることができる。従って、Ｘ０は（Ｃ，Ｕ）の論理関数としてＸ０＝Ｆ０（Ｃ，Ｕ）のように表すことができる。
【００６６】
以上のように各係数Ｃに対して最適解Ｘ０が１つだけの場合も、１つ以上の場合も最適解を、前者はＸ０＝Ｆ０（Ｃ）、後者はＸ０＝Ｆ０（Ｃ，Ｕ）なる論理関数で表すことができ、組合せ回路として実現できる。尚、前者は後者のＮｍａｘ＝１（Ｓ＝０）の場合と考えれば、同じ枠組みで扱うことができる。
【００６７】
尚、複数の最適解を許す場合で、制約条件が無い場合には、全てのＣに対して最適解は常に存在することから、最適解の存在条件は出てこない。
【００６８】
最適解の存在条件が必要になるのは、与えられたＣがｐ個の最適解をもつかどうかを識別したい場合や、そもそも最適解が存在するかしないかを識別したい場合である。このｐ個解存在信号および解存在信号を出力する組合せ回路は、次のような方法で実現できる。
【００６９】
与えられたＣがｐ個の最適解をもつ場合かを識別したい場合は、
【数１１】
2005333500.tif 000010
となるＣの最小項の和（ＯＲ）をとり論理関数ｓｐ（Ｃ）を作り、また制約条件有りで複数の最適解を許す場合には、与えられたＣにおいて最適解の存在を識別したい場合には、ＮＣ＝０となるＣの最小項の和（ＯＲ）をとりｓ（Ｃ）を作る。
【００７０】
ｓｐ（Ｃ）はｐ個解存在論理関数となり、ｓ（Ｃ）は解存在信号になる。最適解がｐ個存在する時ｓｐ（Ｃ）＝０、存在しない時ｓｐ（Ｃ）＝１であり、数に関係無く最適解が存在する時ｓ（Ｃ）＝０、全く最適解が存在しない時ｓ（Ｃ）＝１となる。
【００７１】
図７は、本発明の最適値最適解決定フローである。図７は上述した図５から図６の割り付け法と同様の考えに基づくＥ０＝Ｅ０（Ｃ）およびＸ０＝Ｆ０（Ｃ，Ｕ）をコンピュータを利用して求める為のフローである。
【００７２】
図７は、開始701に始まり、破線で囲まれた処理１(702,703,704,705,706,708,709,710)、処理２(711,712,713,714,715,716,717,718,719,720,721)、処理３(722,723,724)、および処理４(725,726,727,728,729,730,731,732,733,734,735)の大きく４つの処理からなり、終了736で処理完了するフローである。
【００７３】
処理１は各Ｃの最適値を求めＥ０＝Ｅ０（Ｃ）を決定する処理であり、処理２はＮＣ，Ｎｍａｘを求める処理であり、処理３は解変数のビット数Ｓを求める処理であり、処理４は最適解Ｆ０（Ｃ，Ｕ）を求める処理である。終了時点でＥ０＝Ｅ０（Ｃ）、Ｘ０＝Ｆ０（Ｃ，Ｕ）およびＮＣ，Ｎｍａｘ，Ｓなどが得られるフローである。
【００７４】
尚、図７ではＸ，Ｃ，Ｅ（Ｘ，Ｃ），Ｅ０（Ｃ），ＮＣ，Ｎｍａｘ，Ｓ，Ｕ，Ｆ（Ｃ，Ｕ）などのベクトル型の論理変数や論理関数を非負整数と見なす扱いを行うことで、コンピュータ処理に適したフローとなっている。得られたＥ０（Ｃ），Ｆ０（Ｃ，Ｕ）は多入力多出力つまりベクトル入力変数のベクトル型論理関数の真理値表に直接対応していることから、論理合成などを用い組合せ回路を設計することが可能となる。
【００７５】
尚、図７中の＆ｈ＝０は“且つｈ（Ｘ，Ｃ）＝０”を意味する。従って制約条件有りの場合で示してある。しかし制約条件はｈ（Ｘ，Ｃ）＝０と等価であれば異なる表現に置き換えてもよい。例えば、線形計画などの最適化問題のように、数値を表すｋビット関数Ｈ（Ｘ，Ｃ）に対して、上限値Ｈ０を課し、Ｈ（Ｘ，Ｃ）＜＝Ｈ０のような不等式による制約条件の場合には、図７の＆ｈ（Ｘ，Ｃ）＝０の所を＆Ｈ（Ｘ，Ｃ）＜＝Ｈ０に置き換えれば同じフローで最適決定回路の論理関数を求めることができ、また図７から＆ｈ＝０を除くことによって制約条件無しのフローとになる。また解の存在条件は上述した方法により、ＮＣから解存在信号の論理関数ｓｐ（Ｃ）およびｓ（Ｃ）を作ることができる。
【００７６】
以上が請求項１の構成である。
【００７７】
次に請求項２および請求項３に関するブール方程式解法による構成を説明する。
【００７８】
［請求項２の構成］
与えられた係数Ｃに対し唯一の最適解を必要とし且つ制約条件が無い場合には、パラメータＸが評価関数Ｅ（Ｘ，Ｃ）の最小値（または最大値）Ｅ０を取るとすれば、その他の任意のパラメータＹに対して、Ｅ（Ｘ，Ｃ）＜Ｅ（Ｙ，Ｃ）（またはＥ（Ｘ，Ｃ）＞Ｅ（Ｙ，Ｃ））と考えることができる。
【００７９】
従って引算をＥ（Ｘ，Ｃ）−Ｅ（Ｙ，Ｃ）（またはＥ（Ｙ，Ｃ）−Ｅ（Ｘ，Ｃ））として論理式のままで計算すれば、ｌビット目のキャリーを最小値と最大値の場合で同じｃｌ（Ｘ，Ｙ，Ｃ）と表すことにすれば、キャリーはｃｌ（Ｘ，Ｙ，Ｃ）＝１とならねばならない。
【００８０】
これが
【数１２】
2005333500.tif 000011
なる全てのＹに対してなりたつことから、
【数１３】
2005333500.tif 000012
が成り立たねばならない。これは同値な
【数１４】
2005333500.tif 000013
と表せ、さらにこのＹに就いてのＸ以外に亘る和（ＯＲ）が、恒等写像の母関数
【数１５】
2005333500.tif 000014
を用いると、
【数１６】
2005333500.tif 000015
なる式としても表すことができる。(1),(1’) ,(1”)は全て同値な方程式である。
【００８１】
Ｘ，Ｃに関した制約条件があり、制約条件等価ブール方程式がｈ（Ｘ，Ｃ）＝０の場合には、前記のＸ，Ｙが共にこの制約条件を満足したものとすればよい。
従って(1”)に対応する方程式は
【数１７】
2005333500.tif 000016
と置けば
【数１８】
2005333500.tif 000017
となる。
【００８２】
制約条件が無い場合は全てのＸに対してｈ（Ｘ，Ｃ）＝０が成り立つことと等価であることに注意すると、結局、（丸１）、（Ｉ）は制約条件無しの場合も制約条件有りの場合も含めた各Ｃに対する唯一の最適解Ｘ０を求めるブール方程式と考えてよいことになる。
【００８３】
（丸１）はＹに関しては和（ＯＲ）が取られていることから、（Ｉ）は未知数Ｘと係数Ｃを含んだブール方程式であり、これを解くことで、任意変数Ｕ＝（ｕｎ−１，…，ｕ０）を含んだ最適解の論理関数Ｘ０＝Ｆ０（Ｃ，Ｕ）および解存在条件の論理関数ｓｌ（Ｃ）を得ることができる。この場合最適解は各Ｃに対して存在する場合には唯一であることに注意すると、この任意変数は何に決めても唯一に解が存在するＣに対しては同じ値になるので、例えばＵ＝(0,…,0)とすると、Ｕを含まないＸ０＝Ｆ０（Ｃ）なる形で表すことができる。
【００８４】
また解の存在条件は唯一解の存在条件であることに注意すると、請求項２の具体的な実現手段となっていることが分かる。
【００８５】
以上が請求項２の構成である。
【００８６】
［請求項３の構成］
次に与えられた係数Ｃに対し数を問わずに最適値を必要とし制約条件が無い場合には、パラメータＸが評価関数Ｅ（Ｘ，Ｃ）の最小値（または最大値）Ｅ０を取るとすれば、その他の任意のパラメータＹに対して、Ｅ（Ｘ，Ｃ）＜＝Ｅ（Ｙ，Ｃ）（またはＥ（Ｘ，Ｃ）＞＝Ｅ（Ｙ，Ｃ））と考えることができる。
【００８７】
従って引算をＥ（Ｙ，Ｃ）−Ｅ（Ｘ，Ｃ）（またはＥ（Ｘ，Ｃ）−Ｅ（Ｙ，Ｃ））として論理式のままで計算すれば、ｌビット目のキャリーを最小値と最大値の場合で同じｃ（Ｘ，Ｙ，Ｃ）と表すことにすれば、キャリーは
ｃ（Ｘ，Ｙ，Ｃ）＝０  (2)
とならねばならない。
【００８８】
Ｘ，Ｃに関した制約条件があり、制約条件等価ブール方程式がｈ（Ｘ，Ｃ）＝０の場合には、前記のＸ，Ｙが共にこの制約条件を満足したものとすればよいので(２)に対応する方程式は
【数１９】
2005333500.tif 000018
と置けば
【数２０】
2005333500.tif 000019
となる。
【００８９】
制約条件が無い場合は全てのＸに対してｈ（Ｘ，Ｃ）＝０が成り立つことと等価であることに注意すると、結局（丸２）、（ＩＩ）は制約条件無しの場合も制約条件有りの場合も含めた各Ｃに対する最適解Ｘ０を求めるブール方程式と考えてよいことになる。
【００９０】
（丸２）ではＹに関しては和（ＯＲ）が取られていることから、（ＩＩ）は未知数Ｘと係数Ｃを含んだブール方程式であり、これを解くことで、任意変数Ｕ＝（ｕｎ−１，…，ｕ０）を含んだ最適解の論理関数Ｘ０＝Ｆ０（Ｃ，Ｕ）および解存在条件の論理関数ｓ（Ｃ）を得ることができる。
【００９１】
この場合任意変数は図６および図７で述べた解変数に対応するが、ブール方程式では最適解の数が何であってもｎ個出て来る。つまり解変数を冗長に表したものに対応する。この場合の任意変数Ｕも解変数と呼ぶことにする。
【００９２】
以上が請求項３の構成である。
【００９３】
以上請求項２と請求項３のブール方程式として論理関数を求める手段を示したが、ブール方程式の解法に就いては、例えば“論理数学の基礎”尾崎弘、藤原秀雄共著（オーム社）に示されているように、逐次解いて行くことで確実に解と解の存在条件が得られることが分かる。
【００９４】
従ってどのように係数や変数のビット数が大きな最適化問題であったとしても、方程式の解法を規則的に解いて行くことを厭わなければ必ず解および解の存在条件を書き下すことが原理的に可能になり、書き下された論理関数の簡約化などの難易度の大小は変数等の規模に依存するが、基本的に組合せ回路として実現可能になる。
【００９５】
この点が請求項２および請求項３の大きな特徴点である。
【００９６】
［請求項４の構成］
制約条件付きの最適化問題を対象とした時に、制約条件式は一般に係数Ｃの一部または全部とパラメータＸの間の算術的な等式や不等式として与えられる。つまり一般に制約条件の左辺はｋビットの数値を表すＨ（Ｘ，Ｃ）と表すことができ、制約条件右辺は一般に定数Ｈ０と表され、Ｈ（Ｘ，Ｃ）＝Ｈ０またはＨ（Ｘ，Ｃ）＞＝Ｈ０またはＨ（Ｘ，Ｃ）＜＝Ｈ０のような制約条件で表される。
【００９７】
Ｈ（Ｘ，Ｃ）＝Ｈ０の場合には、移項したＨ（Ｘ，Ｃ）−Ｈ０＝０よりＨ（Ｘ，Ｃ），Ｈ０の各ビットをｈｉ（Ｘ，Ｃ），ｈ０ｉ（i=0,…,k-1）と置くと、各ビットで
【数２１】
2005333500.tif 000020
と表せるから、
【数２２】
2005333500.tif 000021
と定義すれば、制約条件の式Ｈ（Ｘ，Ｃ）＝Ｈ０はｈ（Ｘ，Ｃ）＝０なるブール方程式と等価に扱うことができる。
【００９８】
次にＨ（Ｘ，Ｃ）＞＝Ｈ０またはＨ（Ｘ，Ｃ）＜＝Ｈ０なる不等式の場合には
Ｈ（Ｘ，Ｃ）−Ｈ０またはＨ０−Ｈ（Ｘ，Ｃ）なる引算を考え、最上位のキャリーをｈ（Ｘ，Ｃ）とすると、前記不等式の制約条件はキャリーが出ないことであるから、この場合にもｈ（Ｘ，Ｃ）＝０なるブール方程式と等価に扱うことができる。
【００９９】
以上のように最適化問題の制約条件は１つのブール方程式ｈ（Ｘ，Ｃ）＝０（ＩＩＩ）として扱える。この制約式を請求項２乃至請求項３の制約条件有りの最適決定回路に適用する。
【０１００】
以上が請求項４の構成である。
【０１０１】
［請求項５の構成］
評価関数は係数とパラメータを入力とする論理関数であり、最適解はパラメータの一部に属すので、最適解を出力とする論理関数を評価関数の論理関数に代入し論理合成を行えば最適値の論理関数が実現できる。
【０１０２】
具体的には請求項１乃至請求項３に記載の最適解を出力する最適決定回路の出力を評価関数回路の入力として論理合成することにより請求項５記載の最適値決定回路を実現する。
【０１０３】
［請求項６の構成］
図８は本発明の最適解最適値同時出力回路ブロック図である。前段に請求項１乃至請求項３により実現された係数801（および解変数802）を入力とする最適解決定回路803を配し、その出力を最適解806を結果として出力し、同時に、解入力評価関数回路804は入力として係数801および最適解806を入力とし、最適値805を出力とする構成にしたことで、最適解806および最適値805を同時に出力できる構成にする。
【０１０４】
請求項５および請求項６の評価関数回路はパラメータ全体を入力とする評価関数に比べ入力が最適解に限定されていることから多くのdon’t care（不知）入力があることになり、このことから論理設計で大幅な簡単化ができる特徴がある。
【０１０５】
［請求項７の構成］
１つ以上の最適解を有する場合に、例えば請求項１または請求項３による実現手段で解変数（任意変数）を含んだ最適解決定論理関数を求め、解変数（任意変数）を最適解決定論理関数が簡単になる基準で１つまたは限定した複数種に絞る。以上が請求項７の構成である。
【０１０６】
［請求項８の構成］
請求項１乃至請求項４または請求項７記載の１つまたは複数の最適決定回路を具備し、前記１つまたは複数の最適決定回路の出力（および所定の処理を経た出力）を復号結果とする構成の復号回路である。
【０１０７】
たとえば、最尤復号方式の場合は、受信信号を請求項１乃至請求項４または請求項７記載の係数とし、符号化前のデータをパラメーターとする尤度関数を請求項１乃至請求項４または請求項７記載の評価関数とし、前記評価関数が制約条件なしで最大値をとる前記パラメーターを出力する請求項１乃至請求項４または請求項７記載の最適解決定回路の出力を復号結果とする構成が1つの例である。
【０１０８】
図９は、本発明の復号回路例ブロック図である。
【０１０９】
［請求項９の構成］
図１０は、請求項９記載の復号回路の構成例１のブロック図である。
図１１は、請求項９記載の復号回路の構成例２のブロック図である。
【０１１０】
図１０においては入力データ1001を最適決定回路1002と唯一解存在条件回路1003の両方に入力し、唯一解存在条件回路1003の出力を復号誤りがあるか否かを表す信号とし、最適決定回路1002の出力を復号結果としている。
【０１１１】
図１１においては、入力データ1101を唯一解存在条件回路1102の出力に応じて処理回路1103によって唯一解存在条件回路1102の出力が０になるように処理し、処理回路1103の出力を最適決定回路1104の入力とし、最適決定回路1104の出力を復号結果1105としている。
【０１１２】
［請求項１０の構成］
図１２は、請求項１０記載の復号回路の構成例のブロック図である。図１２において、請求項８乃至請求項９記載の復号回路1204は入力データ1202と解変数1201とを入力とし1208を出力し、1025は1202と1203を入力し1209を出力し、1208と1209は外符号復号誤り判定選択回路1206に入力され、1206は1208と1209とのうちビット誤り率が少ないほうを出力する。
【０１１３】
［請求項１１の構成］
図１３は、請求項１１記載の復号回路の構成例のブロック図である。図１３において、復号回路1304は請求項８乃至請求項１０記載の復号回路であって、1304は時系列データを所定の時間長ごとに区切ったブロック入力データ1301と記憶素子1302の内容を入力として1306を復号結果1305として出力し、情報生成回路1303は1302の内容と1306を入力とし所定の処理により1302の内容を書き換える。
【０１１４】
［請求項１２の構成］
図１４は、請求項１２記載の復号回路の構成例のブロック図である。シンボルを構成単位とする時系列データにおいてブロック長をNシンボル分、ＭをＮ未満の数としてブロック周期をMシンボル分とする。
【０１１５】
図１４において、復号回路1404は請求項８乃至請求項１０記載の復号回路であり、Ｎ個のシンボルからなる１ブロック分のデータ1401と記憶素子1402の内容を入力とし1406を出力する。1406はMシンボル分の復号結果として出力される。さらに1406と1402の内容は情報生成回路1403に入力され、1403は所定の処理によって1402の内容を書き換える。
【０１１６】
図１５は、請求項１３および請求項１４記載の２系統入力復号回路例１ブロック図である。図１６は、請求項１３および請求項１４記載の２系統入力復号回路例２ブロック図である。
【０１１７】
［請求項１３の構成］
図１５において、入力コントロール回路1503はクロック毎に第１系統入力1501と第２系統入力1502を交互に選択して２段パイプライン化された最適解決定回路1504に入力し、1504は1クロック遅れて復号結果1508を出力する。1508は出力コントロール回路1505によって交互に第１系統出力1507と第２系統出力1506に割り振られ出力される。
【０１１８】
図１６において、入力コントロール回路1604はクロック毎に第１系統入力1601および第１系統記憶素子1603の内容と第２系統入力1602および第２系統記憶素子1605の内容とを交互に２段パイプライン化された最適解決定回路1607に入力し、最適解決定回路1607は１クロック遅れて復号結果1612を出力する。復号結果1612は出力コントロール回路1609によって交互に第１系統出力1610と第２系統出力1611へ割り振られ出力される。
【０１１９】
第１系統出力1610と第１系統記憶素子1603の内容は第１系統情報生成回路1606に入力され、第１系統情報生成回路1606は第１系統記憶素子1603の内容を書き換える。第２系統出力1611と第２系統記憶素子1605の内容は第２系統情報生成回路1608に入力され、第２系統情報生成回路1608は第２系統記憶素子1605の内容を書き換える。
【０１２０】
上記例では２系統の入力の構成例で示したが、一般の複数の入力がある場合にも同様な構成が実現できることは明らかである。以上が請求項１３の構成である。
【０１２１】
［請求項１４の構成］
図１５において、入力コントロール回路1503はクロック毎に第１系統入力1501と第２系統入力1502を交互に選択して最適解決定回路1504に入力し、最適解決定回路1504は復号結果1508を出力する。1508は出力コントロール回路1505によって交互に第１系統出力1507と第２系統出力1506に割り振られ出力される。
【０１２２】
図１６において、入力コントロール回路1604はクロック毎に第１系統入力1601および第１系統記憶素子1603の内容と第２系統入力1602および第２系統記憶素子1605の内容とを交互に最適解決定回路1607に入力し、最適解決定回路1607は復号結果1612を出力する。
【０１２３】
復号結果1612は出力コントロール回路1609によって交互に第１系統出力1610と第２系統出力1611へ割り振られ出力される。
【０１２４】
第１系統出力1610と第１系統記憶素子1603の内容は第１系統情報生成回路1606に入力され、第１系統情報生成回路1606は第１系統記憶素子1603の内容を書き換える。
【０１２５】
第２系統出力1611と第２系統記憶素子1605の内容は第２系統情報生成回路1608に入力され、第２系統情報生成回路1608は第２系統記憶素子1605の内容を書き換える。
【０１２６】
上記例では２系統の入力の構成例で示したが、一般の複数系統の入力がある場合にも同様な構成が実現できることは明らかである。以上が請求項１４の構成である。
【０１２７】
［請求項１５の構成］
Ｉ種の符号化方式に対応した評価関数が
【数２３】
2005333500.tif 000022
と表される時に、切替係数ｃｉを導入し、合成評価関数
【数２４】
2005333500.tif 000023
を、例えば
【数２５】
2005333500.tif 000024
として作成し、この合成評価関数を請求項１乃至請求項７記載の評価関数として最適決定回路を実現する。このことでＩ種の符号化に対する最適決定回路を１つの組合せ回路として実現可能となる。
【０１２８】
図１７は、請求項１５記載の符号化切替型復号回路ブロック図である。
入力係数の一部の（ｃ０，ｃ１，…，ｃＩ−ｌ）である切替係数1702を出力する符号化方式コントロール回路1703を具備し、最適決定回路1704は切替係数1702およびＣ’である入力データ1701を入力とし、復号結果1705を出力する。
【０１２９】
尚、合成評価関数の作成は(3)式の形に限定されず種々の形がある。以上が請求項１５の構成である。
【０１３０】
［請求項１６の構成］
拘束長Ｋ、符号化率１／Ｒの畳込み符号の受信時系列データから得られる時刻ｔのＪビット精度のソフトバリューの各ビットをｃｊｒ（ｔ）（r=0,…,R-1;j=0,…,J-1)とした時、例えばブロックの始まり時刻をｔ＝０と表した場合にそのブロックの復号に対する最適決定問題の評価関数として
【数２６】
2005333500.tif 000025
なる形を考える。
【０１３１】
ここにＣｒ（ｔ）＝（ｃ０ｒ（ｔ），…ｃＪ−１ｒ（ｔ））（ｒ＝０，…，Ｒ−１）であり、ｐｒ（ｔ）は各時刻ｔのパンクチャ−の有り無し状況に応じて0,1をとるパンクチャ−ド・モード係数であり、またｇｒ（Ｘｔ）は時刻ｔの入力データｘｔと遅延素子の状態を合わせたＸｔ＝（ｘｔ，ｘｔ−１，…，ｘｔ−Ｋ＋１）に対する符号器からの生成符号に対応するもので、ｒ＝０，…，Ｒ−１なるＲ種の関数から成る。ｄ（Ｃ（ｔ），ｇｒ（Ｘｔ））はユークリッド距離や相関型距離などで定義された最尤復号などに用いられる一般的な距離である。
【０１３２】
そして時刻ｔの生成符号の各成分ｇｒ（Ｘｔ）に対して
【数２７】
2005333500.tif 000026
なる形で表現する。ここにｑｒ（ｋ）（ｒ＝０，…，Ｒ−１，ｋ＝０，…，ｋ−１）を生成多項式形状係数と呼ぶことにする。
【０１３３】
(5)式のように表現し、且つパンクチャ−ド・モード係数ｐｒ（ｔ）の値もコントロールすることで、(4)式を拘束長Ｋ以下、符号化率Ｒ以下の任意の畳込み符号の符号化方式に対応した評価関数と考えることができる。
【０１３４】
例えば
【数２８】
2005333500.tif 000027
とし、且つｑ０（１）＝ｑ０（４）＝ｑ１（４）＝ｑ１（５）＝０、その他の（ｒ，ｔ）に対応するｑｒ（ｔ）はｑｒ（ｔ）＝１とすれば無線ＬＡＮのIEEE802.11aで採用されている拘束長７、符号化率１／２の８進表記((171,133)oct)なる畳込み符号化に対応させることができ、また例えばｑ０（１）＝ｑ０（４）＝ｑ１（２）＝ｑ１（３）＝ｑ１（５）＝ｑ２（５）＝０、その他の（ｒ，ｔ）に対応するｑｒ（ｔ）はｑｒ（ｔ）＝１とすればMBOA(Multi-Band-OFDM-Alliance)が提案しているＵＷＢ(Ultra-Wide-Band)の拘束長７、符号化率１／３の８進表記((133,145,175)oct)なる畳込み符号化に対応させることができる。それぞれの符号化で定義されたパンクチャ−ド・モードは、前記パンクチャ−ド・モード係数の値を変えれば対応可能となり、またＫが７未満の場合も同様に対応可能である。
【０１３５】
そこで、ｒ＝０，…，Ｒ−１；ｊ＝０，…，Ｊ−１；ｔ＝０，…，Ｔ−１；ｋ＝０，…，ｋ−１とした時、ブロック内の全ｃｊｒ（ｔ）および過去の拘束長Ｋ分の復号結果ｘ−１，ｘ−２，…，ｘ−Ｋ＋１の計Ｒ×Ｊ×Ｔ＋Ｋ−１＝ｍ１ビットをＣ’＝（ｃ’ｍ１−１，ｃ’ｍ１−２，…，ｃ’１，ｃ’０）と表し、またパンクチャ−・モード係数ｐｒ（ｔ）のＲ×Ｔ＝ｍ２ビットをＣ’’＝（ｃ’’ｍ１−１，ｃ’’ｍ１−２，…，ｃ’’１，ｃ’’０）と表し、また生成多項式形状係数ｑｒ（ｋ）の計Ｒ×Ｋ＝ｍ３ビットをＣ’’’＝（ｃ’’’ｍ１−１，ｃ’’’ｍ１−２，…，ｃ’’’１，ｃ’’’０）と表し、上記の係数（Ｃ’，Ｃ’’，Ｃ’’’）の全ｍ１＋ｍ２＋ｍ３ビットを全ｍ１＋ｍ２＋ｍ３＝ｍとして、(4)式の左辺の評価関数の係数であるＣ＝（ｃｍ１−１，ｃｍ１−２，…，ｃ０）の全ｍビットに１対１に対応させる。
【０１３６】
この対応により、(4)式の評価関数を請求項１乃至請求項７の最適決定回路の論理関数として求め、請求項８乃至請求項１４記載の復号回路として実現する。
【０１３７】
図１８は、請求項１６記載の符号化切替型復号回路ブロック図である。
Ｃ’’’である生成多項式形状係数1803を出力する生成多項式コントロール回路1802とＣ’’であるパンクチャ−ド・モード係数1805を出力するパンクチャ−ド・モード・コントロール回路1804とを具備し、生成多項式形状係数1803およびパンクチャ−ド・モード係数1805およびＣ’である入力データ1801を最適解決定回路1806に入力し、出力として復号結果1807を出力する。
【０１３８】
尚、評価関数は(4)式の形に限定されず,例えば環境ノイズの測定結果を入力データとして反映させるなどの種々の形がある。以上が請求項１６の構成である。
【０１３９】
［請求項１７の構成］
請求項１６における生成多項式形状係数およびパンクチャ−ド・モード係数を限定することで組合せ回路の入力変数を減らし回路を簡単化することができる。
【０１４０】
例えば拘束長が７の場合だけに対応する一般に採用されている符号化に限定するならば、ｑｒ（０）＝Ｑｒ（６）＝と固定で考えることができ、最適解決定回路の入力変数の対応する部分は定数になる。このことで回路は一般に簡単化される。
【０１４１】
さらに専用であればｑｒ（ｋ）が固定値になる部分が増え、図１８において生成多項式コントロール回路を無くしたブロック図が実現形態となる。以上が請求項１７の構成である。
【０１４２】
以上請求項１から請求項１７までの実現手段も含めた構成を示した。
【実施例】
【０１４３】
次に本発明の実施例として、極簡単な畳込み符号の復号器の実施例を示す。
【０１４４】
時刻ｔの生成多項式が
【数２９】
2005333500.tif 000028
と表される拘束長Ｋ＝３、符号化率Ｒ＝２の畳込み符号による符号化された送信系に対して、送信は時刻ｔ＝０の全０状態（ｘ−１＝ｘ−２＝０）から符号化を行い、時刻ｔ＝２までの３ビットが送信され、受信側では２ビット時系列ｃｒ（ｔ）（ｒ＝０，１；ｔ＝０，１，２）として受信されたデータに対して、
【数３０】
2005333500.tif 000029
なる評価関数を最小化するような最適解Ｘ０＝（ｘ２，ｘ１，ｘ０）を決定する復号器を対象とする。
【０１４５】
この実施例の場合、パラメータはＸ０＝（ｘ２，ｘ１，ｘ０）でｎ＝３、受信データ時系列を係数Ｃ＝（ｃ５，…，ｃ０）に対しｃ０（０）＝ｃ０，ｃ１（０）＝ｃ１，ｃ０（１）＝ｃ２，ｃ１（１）＝ｃ３，ｃ０（２）＝ｃ４，ｃ１（２）＝ｃ５のように対応させる。評価関数Ｅ（Ｘ，Ｃ）＝（ｅｌ−１（Ｘ，Ｃ），…，ｅ０（Ｘ，Ｃ））の値は(6)から最大６の値をとり得ることからこの実施例ではｌ＝３である。
【０１４６】
図１９は、実施例復号回路図である。図１９は、前記評価関数が最小値をとるパラメータを決定する最適解決定回路を、請求項１に述べた設計手段により求めた真理値表から論理合成をして得た回路図である。
【０１４７】
論理合成の際にはTSMCの0.13μmプロセスのライブラリを使用した。前記実施例復号回路のゲート数は２入力NAND換算で約26ゲート、最大遅延は約0.53nsであった。
【０１４８】
本発明の効果を観る意味で、(6)の評価関数から従来の考えで設計したものと比較する。
【０１４９】
畳込み符号に対する最も一般的な復号器はビタビ復号回路であるが、(6)の評価関数は時間長が短い為、ビタビ復号回路よりも回路規模が小さくなる回路を比較対象として設計し比較した。
【０１５０】
図２０は、比較対象従来型回路ブロック図である。これは最適解ベクトルＸ０＝（ｘ２，ｘ１，ｘ０）がとり得る８種の値をカウンタ2002が生成し、前記ベクトル値と入力データ2001に対して評価関数計算器2003が評価関数Ｅ（Ｘ，Ｃ）の値を逐次計算し、前記評価関数の値を比較選択器2004が逐次比較して、より小さい前記評価関数の値を受け取った場合に対応するベクトル値を保持し出力する。結果として、前記カウンタが8回動いた後には求める最適解が出力されている。
【０１５１】
前記比較対象従来型回路をTSMCの0.13μmプロセスのライブラリを用いて論理合成した結果、ゲート数は２入力NAND換算で約140ゲート、最大遅延は約2.64nsであった。
【０１５２】
以上のように同じ評価関数(6)の最適解を求める回路で比較し、本発明の回路規模は前記従来型の回路規模の約26／140である。また遅延に就いては本発明の組合せ回路が約0.53nsであるのに対し、従来型回路は１サイクル辺りの遅延が約2.64nsである。従って８サイクル分の遅延を考慮すると約４０倍のスループットの違いがある。
【０１５３】
以上の発明の構成および実施例で示して来たように、請求項１乃至請求項７記載の本発明の最適決定回路は、最適解決定回路、最適値決定回路、ｐ個解存在判定回路、解判定回路を全て組合せ回路として実現することにより、回路規模が小さい最適決定回路が実現できる効果がある。
【０１５４】
また従来型の最適決定回路は、メモリやレジスタを多用する逐次処理型であることから、結果を出すまでに多くのサイクル数を必要とするのに対し、本発明の最適決定回路の場合には、遅延時間の小さな組合せ回路として実現できることから、十分に高速なクロック１サイクルで結果を出せる効果がある。
【０１５５】
また請求項８乃至請求項１７記載の本発明の復号回路の場合には、回路規模が小さく結果として低消費電力の復号回路が実現でき、また高速処理が必要な場合や、複数系統のデータの復号が必要な場合には回路のパイプライン化または時分割処理を適用することで対応できる効果がある。
【０１５６】
また複数種の最適解である復号結果を出すことが可能であることから復号時に性能改善ができる構成が可能である。さらに、１つの復号回路の最適決定回路部分の入力係数をコントロールすることで、パンクチャ−ド・モードの違いも含め複数の符号化方式を切り替える形態が実現でき、例えば第４世代携帯電話などで取り入れられる可能性の高いソフトウエア無線などにおいても回路規模の小さな復号回路が実現できる効果がある。
【図面の簡単な説明】
【０１５７】
【図１】本発明の最適解決定回路ブロック図である。
【図２】本発明の最適値決定回路ブロック図である。
【図３】本発明のｐ個解存在判定回路ブロック図である。
【図４】本発明の解存在判定回路ブロック図である。
【図５】最適値は最小値とした例の評価関数真理値表である。
【図６】図５の例に対する最適解の解変数への割り付け図である。
【図７】本発明の最適値最適解決定フローである。
【図８】本発明の最適解最適値同時出力回路ブロック図である。
【図９】本発明の復号回路例ブロック図である。
【図１０】請求項９記載の復号回路の構成例１のブロック図である。
【図１１】請求項９記載の復号回路の構成例２のブロック図である。
【図１２】請求項１０記載の復号回路の構成例のブロック図である。
【図１３】請求項１１記載の復号回路の構成例のブロック図である。
【図１４】請求項１２記載の復号回路の構成例のブロック図である。
【図１５】請求項１３および請求項１４記載の２系統入力復号回路例１ブロック図である。
【図１６】請求項１３および請求項１４記載の２系統入力復号回路例２ブロック図である。
【図１７】請求項１５記載の符号化切替型復号回路ブロック図である。
【図１８】請求項１６記載の符号化切替型復号回路ブロック図である。
【図１９】本発明の実施例復号回路図である。
【図２０】比較対象従来型回路ブロック図である。
【符号の説明】
【０１５８】
101      係数
102      解変数
103      組合せ回路
104      最適解
201      係数
202      組合せ回路
203      最適値
301      係数
302      組合せ回路
303      ｐ個解存在判定信号
401      係数
402      組合せ回路
403      解存在判定信号
801      係数
802      解変数
803      最適解決定回路
804      解入力評価関数回路
805      最適値
806      最適解
1001      入力データ
1002      最適決定回路
1003      唯一解存在条件回路
1101      入力データ
1102      唯一解存在条件回路
1103      処理回路
1104      最適決定回路
1105      復号結果
1201      解変数
1202      入力データ
1204      復号回路
1206      判定選択回路
1301      ブロック入力データ
1302      記憶素子
1303      情報生成回路
1304      復号回路
1305      復号結果
1401      Ｎシンボル分ブロック入力データ
1402      記憶素子
1403      情報生成回路
1404      Ｎシンボル分復号回路
1501      第１系統入力
1502      第２系統入力
1503      入力コントロール回路
1504      最適解決定回路
1505      出力コントロール回路
1506      第１系統出力
1507      第２系統出力
1508      復号結果
1601      第１系統入力
1602      第２系統入力
1603      第１系統記憶素子
11604      入力コントロール回路
1605      第２系統記憶素子
1606      第１系統情報生成回路
1607      最適解決定回路
1608      第２系統情報生成回路
1609      出力コントロール回路
1610      第１系統出力
1611      第２系統出力
1612      復号結果
1701      入力データ
1702      切替係数
1703      符号化方式コントロール回路
1704      最適決定回路
1705      復号結果
1801      入力データ
1802      生成多項式コントロール回路
1803      生成多項式形状係数
1804      パンクチャード・モード・コントロール回路
1805      パンクチャード・モード係数
1806      最適解決定回路
1807      復号結果
2001      入力データ
2002      カウンタ
2003      評価関数計算器
2004      比較選択器NAND
【図１】
2005333500.tif 000035
【図２】
2005333500.tif 000036
【図３】
2005333500.tif 000037
【図４】
2005333500.tif 000038
【図５】
2005333500.tif 000039
【図６】
2005333500.tif 000040
【図７】
2005333500.tif 000041
【図８】
2005333500.tif 000042
【図９】
2005333500.tif 000043
【図１０】
2005333500.tif 000044
【図１１】
2005333500.tif 000045
【図１２】
2005333500.tif 000046
【図１３】
2005333500.tif 000047
【図１４】
2005333500.tif 000048
【図１５】
2005333500.tif 000049
【図１６】
2005333500.tif 000050
【図１７】
2005333500.tif 000051
【図１８】
2005333500.tif 000052
【図１９】
2005333500.tif 000053
【図２０】
2005333500.tif 000054