(57)【特許請求の範囲】
【請求項１】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成装置であって、
未修正の前記ｐｑ素子のうち出力側に最も近いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、を備えたことを特徴とする多段論理回路の再構成装置。
【請求項２】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成装置であって、
未修正の前記ｐｑ素子のうち出力側から最も遠いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGが最も出力側ではない場合において、当該ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該ｐｑ素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記ｐｑ素子EGが最も出力側の場合において、前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該ｐｑ素子EGを修正済みとする追加修正手段と、を備えていることを特徴とする多段論理回路の再構成装置。
【請求項３】
入力変数Xの目的論理関数Q(X)を演算する主論理回路について、前記入力変数Xとして入力される各入力ベクトルbのうち特定の対象入力ベクトルbiに対する主論理回路の出力ベクトルQ(bi)を、修正出力ベクトルQ'(bi)に変更する論理回路修正装置であって、
前記各対象入力ベクトルbiに対応して、前記各出力ベクトルQ(bi)を修正出力ベクトルQ'(bi)に修正するための修正用ベクトルPiが所定のアドレスAiに登録される補助メモリと、
前記補助メモリが出力する修正用ベクトルPiを出力した場合、当該修正用ベクトルPi及び前記主論理回路が出力する出力ベクトルQ(bi)に基づいて、前記修正出力ベクトルQ'(bi)を出力する修正手段と、
前記入力変数Xに対して、当該入力変数Xの値が前記対象入力ベクトルbiに等しい場合は前記修正用ベクトルPiが格納された前記補助メモリのアドレスAiを出力するアドレス生成関数F(X)の演算を行うアドレス生成回路と、を備え、
前記アドレス生成回路は、前記アドレス生成関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路により構成されており、
前記修正用ベクトルPiは、対象入力ベクトルbiに対する主論理回路の出力ベクトルQ(bi)との排他論理和が、前記修正出力ベクトルQ'(bi)となる値に設定され、
前記補助メモリは、前記アドレス生成回路が出力するアドレスAiが入力されると、前記修正手段に前記修正用ベクトルPiを出力し、それ以外の場合は０を出力するものであり、
前記修正手段は、前記補助メモリの出力値と前記主論理回路との排他論理和演算を行うＥＸＯＲゲートであることを特徴とする論理回路修正装置。
【請求項４】
入力変数Xの目的論理関数Q(X)を演算する主論理回路について、前記入力変数Xとして入力される各入力ベクトルbのうち特定の対象入力ベクトルbiに対する主論理回路の出力ベクトルQ(bi)を、修正出力ベクトルQ'(bi)に変更する論理回路修正装置であって、
前記各対象入力ベクトルbiに対応して、前記各出力ベクトルQ(bi)を修正出力ベクトルQ'(bi)に修正するための修正用ベクトルPiが所定のアドレスAiに登録される補助メモリと、
前記補助メモリが出力する修正用ベクトルPiを出力した場合、当該修正用ベクトルPi及び前記主論理回路が出力する出力ベクトルQ(bi)に基づいて、前記修正出力ベクトルQ'(bi)を出力する修正手段と、
前記入力変数Xに対して、当該入力変数Xの値が前記対象入力ベクトルbiに等しい場合は前記修正用ベクトルPiが格納された前記補助メモリのアドレスAiを出力するアドレス生成関数F(X)の演算を行うアドレス生成回路と、を備え、
前記アドレス生成回路は、前記アドレス生成関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路により構成されており、前記入力変数Xに対して、当該入力変数Xの値がいずれの前記対象入力ベクトルbiとも等しくない場合には、無効値を出力するものであり、
前記補助メモリは、前記アドレス生成回路が出力するアドレスAiが入力されると、前記修正手段に前記修正用ベクトルPiを出力し
前記修正手段は、前記主論理回路及び前記補助メモリの出力段にそれぞれ設けられたトライ・ステート・バッファであり、
前記主論理回路の出力段の前記トライ・ステート・バッファは、前記アドレス生成回路の出力値が無効値でない場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となり、
前記補助メモリの出力段の前記トライ・ステート・バッファは、前記アドレス生成回路の出力値が無効値の場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となることを特徴とする論理回路修正装置。
【請求項５】
前記補助メモリは、前記アドレス生成回路の最終段のｐｑ素子であることを特徴とする請求項３又は４記載の論理回路修正装置。
【請求項６】
前記アドレス生成回路において、入力ベクトルbに対する前記アドレス生成関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記アドレス生成回路の再構成を行う再構成装置を備え、
前記再構成装置は、
未修正の前記ｐｑ素子のうち出力側に最も近いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、を備えたことを特徴とする請求項３乃至５の何れか一記載の論理回路修正装置。
【請求項７】
前記アドレス生成回路において、前記アドレス生成関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記アドレス生成回路の再構成を行う再構成装置を備え、
前記再構成装置は、
未修正の前記ｐｑ素子のうち出力側から最も遠いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGが最も出力側ではない場合において、当該ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該ｐｑ素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記ｐｑ素子EGが最も出力側の場合において、前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該ｐｑ素子EGを修正済みとする追加修正手段と、を備えていることを特徴とする請求項３乃至５の何れか一記載の論理回路修正装置。
【請求項８】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成方法であって、
未修正の前記ｐｑ素子のうち出力側に最も近いｐｑ素子EGから順次選択する素子選択ステップと、
前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査ステップと、
前記ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正ステップと、
を繰り返し実行することを特徴とする多段論理回路の再構成方法。
【請求項９】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成方法であって、
未修正の前記ｐｑ素子のうち出力側から最も遠いｐｑ素子EGから順次選択する素子選択ステップと、
前記ｐｑ素子EGが最も出力側ではない場合において、当該ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該ｐｑ素子の出力ベクトルとして使用していないベクトル値に変更する対応付ステップと、
前記ｐｑ素子EGが最も出力側の場合において、前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該ｐｑ素子EGを修正済みとする追加修正ステップと、を繰り返し実行することを特徴とする多段論理回路の再構成方法。
【請求項１０】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された再構成可能な多段論理回路であって、
入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う再構成回路を備え、
前記再構成回路は、
未修正の前記ｐｑ素子のうち出力側に最も近いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、
を備えたことを特徴とする再構成可能な多段論理回路。
【請求項１１】
入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された再構成可能な多段論理回路であって、
前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う再構成回路を備え、
前記再構成回路は、
未修正の前記ｐｑ素子のうち出力側から最も遠いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGが最も出力側ではない場合において、当該ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該ｐｑ素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記ｐｑ素子EGが最も出力側の場合において、前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該ｐｑ素子EGを修正済みとする追加修正手段と、
を備えていることを特徴とする再構成可能な多段論理回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、論理関数の関数分解を繰り返して論理設計される多段論理回路の再構成を行う再構成装置と、それを用いた論理回路修正装置に関する。
【背景技術】
【０００２】
一般に、論理回路は専用のＬＳＩ（ＡＳＩＣ：Application Specific Integrated Circuit）を用いて構成されることが多い。しかしながら、ＡＳＩＣの開発コストは高価であり、その修正や費用にも時間がかかる。一方、論理構成の容易なＦＰＧＡ（Field Programmable Gate Array）も存在するが、現状では消費電力や性能の点で問題がある。【０００３】
そこで、通常、ＡＳＩＣは、修正を可能とする余分な論理回路をあらかじめ組み込んだ状態に設計される。これにより、軽微な機能変更にある程度柔軟に対応させることが可能となる。【０００４】
軽微な機能変更を行う論理回路修正装置としては、例えば、特許文献１に記載のものが公知である。特許文献１に記載の論理回路修正装置は、ＣＰＵで実行するプログラムが記憶されたＲＯＭの出力値を修正するためのものであり、ＦＰＧＡを用いて構成されている。【０００５】
図２０は、特許文献１に記載の論理回路修正装置１０３の構成を示す図である。ＲＯＭ１０１には、ＣＰＵ１０２で実行するプログラムが格納されている。ＣＰＵ１０２は、ＲＯＭ１０１に対してアドレスバス１０４を介してアドレスを送る。ＲＯＭ１０１は、当該アドレスに対し、第１のデータバス１０６にデータを出力する。【０００６】
論理回路修正装置１０３には、アドレスバス１０４からアドレスが入力され、それに対するデータが第１のデータバス１０６から入力される。論理回路修正装置１０３内の修正アドレス記憶部１１１には、修正を行うべきデータが格納されたＲＯＭ１０１のアドレスが登録されている。比較回路１１３は、修正アドレス記憶部１１１に記憶されたアドレス値にアドレスバス１０４から入力されるアドレス値に一致するものがあるか否かを判定し、一致するものがある場合は一致信号を、一致するものがない場合には不一致信号を出力する。一致信号又は不一致信号は、データ選択回路１１４に出力される。【０００７】
一方、修正データ格納部１１２には、修正アドレス記憶部１１１に登録された各アドレス値に対応して、修正を行うべきデータが登録されている。データ選択回路１１４は、比較回路１１３から一致信号が入力された場合には、修正データ格納部１１２から読み出したデータを第２のデータバス１０５に出力する。一方、不一致信号が入力された場合には、データ選択回路１１４は、第１のデータバス１０６から入力されるデータを第２のデータバス１０５に出力する。第２のデータバス１０５に出力されたデータは、読み出しデータとしてＣＰＵ１０２に入力される。【０００８】
このようにして、修正したいＲＯＭ１０１のアドレスを修正アドレス記憶部１１１に登録するとともに、修正したいデータを修正データ格納部１１２に登録することによって、ＲＯＭ１０１の内容の軽微な修正が行われる。
【特許文献１】特開２００２−２９７４０８号公報
【特許文献２】特開２００４−２５８７９９号公報
【非特許文献１】T. Sasao and M. Matsuura, "BDD representation for incompletely specified multiple-output logic functions and its applications to functional decomposition," Design Automation Conference, Anaheim, CA, June 13-17, 2005, pp.373-378.
【発明の開示】
【発明が解決しようとする課題】
【０００９】
ところで、設計段階においては、もとの論理回路のどの部分の修正が必要となるのかは分からない。従って、論理回路修正装置は、もとの論理回路の任意の出力に対して修正が可能であることが求められる。そのためには、回路の論理構成を自在に変更できることが必要である。【００１０】
一方で、論理回路修正装置は、論理回路の修正がない限り、本来の論理回路の動作には関係しない余分な回路である。従って、論理回路修正装置は、その実装面積ができる限り小さく、その消費電力も可能な限り小さいことが好ましい。【００１１】
上記従来の論理回路修正装置は、回路に汎用性を持たせるためにＦＰＧＡを用いて構成されている。そのため、広い配線領域が必要とされ、論理回路修正装置の実装に比較的大きなチップ面積が必要であるという問題がある。【００１２】
また、ＦＰＧＡの再構成を行う場合、一般に、配線の変更がなされる。従って、配線遅延の影響なども考慮に入れた変更が必要とされる。また、変更を誤ると、最悪の場合には回路を破損するおそれがあり、回路変更には十分な注意が必要とされる。更に、配線の変更を伴うことから、回路の変更は、論理回路の動作の停止中に行う必要がある。従って、論理回路の動作期間中にリアルタイムで動的な変更が要求されるような用途（例えば、辞書やニューラル・ネットワーク等における学習に伴う論理回路構成の変更。）に適用することは困難である。【００１３】
ところで、論理構造の再構成が可能な論理回路として、ＬＵＴカスケード論理回路が知られている（特許文献２，非特許文献１参照）。ＬＵＴカスケード論理回路は、二分決定グラフ（ＢＤＤ：binary decision diagram）を用いて目的論理関数を入出力関係が直列状態となる複数の部分関数に関数分解し、各部分関数をＬＵＴとしてメモリで実現したものである。ＬＵＴカスケード論理回路は、殆どがメモリにより構成されるため、高集積化が容易であり実装面積を小さくできる。【００１４】
しかしながら、ＬＵＴカスケード論理回路の再構成を行う場合、従来は、多くの計算処理が必要とされていた。再構成を行う場合、まず、目的論理関数のＢＤＤを作成し、ＢＤＤの分割と再構成を繰り返すことによって最適な関数分解方法を探索する。そして、その結果得られる部分関数をＬＵＴ化してメモリに格納する。目的論理関数の入力変数が多い場合、この処理には大容量メモリを備えたコンピュータで長時間かけて行う必要がある。そのため、簡易な書き換えが必要とされる論理回路修正装置にＬＵＴカスケード論理回路を適用することは、従来行われていない。【００１５】
しかしながら、ＬＵＴカスケード論理回路の論理構成の再構築を簡易化し、軽微な論理の修正を容易に行う手段があれば、論理回路修正装置をＬＵＴカスケード論理回路に適用すれば、小実装面積化と低消費電力化のアプローチと成り得ると考えられる。【００１６】
そこで、本発明の目的は、上記ＬＵＴカスケード論理回路と類似のＬＵＴ型の再構成可能な論理回路を用いて、回路の論理構成の変更の自由度を維持しつつ、従来に比べて実装面積を縮小することができ、消費電力も小さい論理回路修正装置を提供することにある。また、論理回路の動作期間中にリアルタイムで動的な修正を可能とする論理回路修正装置を提供することにある。【００１７】
また、本発明の他の目的は、上記論理回路修正装置などにおいて使用される、論理変更が可能で且つ小実装面積・低消費電力の多段論理回路の再構成を簡易に行うことが可能な多段論理回路の再構成装置を提供することにある。【００１８】
また、本発明の他の目的は、論理関数の軽微な再構成を容易に行うことができ、論理回路の動作期間中にリアルタイムで動的な再構成を実行することを可能とする再構成可能多段論理回路を提供することも目的としている。
【課題を解決するための手段】
【００１９】
〔１〕用語の説明及び本発明の原理的背景
まず、本明細書において使用される主な用語の定義を行い、本発明に関するいくつかの理論的背景について説明する。【００２０】
〔定義１〕（アドレス生成関数，アドレス生成論理関数）
関数F(X):Bn→{0,1,…,k}（Xはｎ次元ベクトル, B={0,1}）においてk個の異なる登録ベクトル（registered vector）ai∈Bn(i=1,2,…,k)に対して、F(ai)=i（i=1,2,…,k）が成立し、それ以外の(2n-k)個の入力ベクトルに対しては、F=0が成立するとき、F(X)を重みkのアドレス生成関数(address generation function)という。アドレス生成関数は、k個の異なる2値ベクトルに対して、１からkまでの固有アドレスを生成する。アドレス生成関数の出力値を2進数で表現する多出力論理関数をアドレス生成論理関数(address generation logic function)という。
（定義終り）
本明細書においては、kの値は入力ベクトルの組み合わせ総数２ｎに比べて十分に小さい（ｋ＜＜２ｎ）と仮定する。【００２１】
〔定義２〕（アドレス検出関数）
関数f(X):Bn→{0,1,…,k}（Xはｎ次元ベクトル）においてk個の異なる登録ベクトルai∈Bn(i=1,2,…,k)に対してf(ai)=1(i=1,2,…,k)が成立し、それ以外の(2n-k)個の入力ベクトルに対しては、f=0が成立するとき、f(X)を重みkのアドレス検出関数（address detection function）という。
（定義終り）【００２２】
〔定義３〕（アドレス表，アドレス生成回路）
アドレス生成論理関数F(X):Bn→{0,1,…,k}のk個の登録ベクトル{ai| i=1,2,…,k; ai∈Bn}に対し、出力ベクトルF(ai)（∈Bm）を対応させた表をアドレス表（address table）という。アドレス表を実現する回路をアドレス生成回路（address generation circuit）という。
（定義終り）【００２３】
〔定義４〕（分割）
入力ベクトルをＸ＝（ｘ１，ｘ２，…，ｘｎ）とする。Ｘの変数の集合を｛Ｘ｝で表す。｛Ｘ１｝∪｛Ｘ２｝＝｛Ｘ｝且つ｛Ｘ１｝∩｛Ｘ２｝＝φのとき、Ｘ＝（Ｘ１，Ｘ２）をＸの分割（partition）という。ここで、φは空集合を表す。
（定義終り）【００２４】
〔定義５〕（分解表，基本分解表，列複雑度）
完全定義関数ｆ（Ｘ）：Ｂｎ→Ｂｑ（Ｂ＝｛０，１｝，Ｘ＝（ｘ１，ｘ２，…，ｘｎ），ｎ，ｑ∈自然数）が与えられているとする。（ＸＬ，ＸＨ）をＸの分割とする。Ｘの次元（変数の個数）をｄ（Ｘ）と記す。関数ｆ（Ｘ）及びＸの分割Ｘ＝（ＸＬ，ＸＨ）に対して、以下の（１）〜（３）の条件を満たす表をｆの分解表（decomposition chart）という。
（１）２ｎＬ列２ｎＨ行の表である。ここで、ｎＬ＝ｄ（ＸＬ），ｎＨ＝ｄ（ＸＨ）とする。
（２）各行，各列に２進符号のラベルを持ち、列及び行のラベルの集合は、それぞれｎＬ，ｎＨビットのすべてのパターンを要素とする。
（３）表の各要素が、その要素に対応する列及び行のラベルの組み合わせ（ＸＬ，ＸＨ）に対するｆの真理値ｆ（ＸＬ，ＸＨ）である。
ＸＬを束縛変数（bound variables）、ＸＨを自由変数（free variables）という。分解表の異なる列パターンの個数を分解表の列複雑度（column multiplicity）といい、μと記す。分解表の特別な場合として、ＸＬ＝Ｘ，ＸＨ＝φの場合も考える。
また、関数ｆの分解表のうちで、ＸＬ＝（ｘ１，ｘ２，…，ｘｎＬ）且つＸＨ＝（ｘｎＬ＋１，ｘｎＬ＋２，…，ｘｎ）となるものを基本分解表（standard decomposition chart）という。
（定義終り）【００２５】
（例１）
（表１）の分解表では、ｎＬ＝３，ｎＨ＝２である。また、分解表の列パターンは、（０１１０）Ｔと（１１０１）Ｔの２つなのでμ＝２である。
（例終り）【００２６】
【表１】
0004742281.tif 000002
【００２７】
〔補題１〕
重みｋのアドレス生成（検出）関数の分解表の列複雑度は高々ｋ＋１である。
（補題終り）【００２８】
〔補題２〕
Fがアドレス生成関数のとき、次式（１）の関係を満たす二つのアドレス生成関数GとHは存在し、Fの重みとGの重みは等しい。【００２９】
【数１】
0004742281.tif 000003
（補題終り）【００３０】
（証明）
X1を束縛変数、X2を自由変数とする分解表を考える。分解表の各列の値の最大値の順位（最大値が０のときは、順位を０とする。）をH(Xi)の値とするアドレス生成関数Hを考える。このとき、関数Gでは、出力値がすべて零の列のみが縮約される。そのため、Gの非零出力の個数は、Fの非零出力の個数と等しい。また、Gもアドレス生成関数になっている。
（証明終り）【００３１】
（例２）
（表２）に示す5変数のアドレス生成関数F(X)の分解表を考える（図１参照）。いま、関数F(X)をF(X1,X2)=G(H(X1), X2)と分解する。ここで、X1=(x1,x2,x3,x4)，X2=(x5)である。このとき、（表２）の列複雑度は７である。Hは（表３）に示す４入力３出力関数であり、重み６のアドレス生成論理関数となっている。また、関数Gの分解表を（表４）に示す。このように、重み７のアドレス生成関数Fを分解して得られる関数Gもまた、重み７のアドレス生成関数となる。
（例終り）【００３２】
【表２】
0004742281.tif 000004
【００３３】
【表３】
0004742281.tif 000005
【００３４】
【表４】
0004742281.tif 000006
【００３５】
〔補題３〕
fがアドレス検出関数のとき、下式（２）の関係を満たす、アドレス検出関数gとアドレス生成関数Hが存在し、gの重みはfの重みを超えない。【００３６】
【数２】
0004742281.tif 000007
（補題終り）
これは、補題２と同様に証明できる。アドレス検出関数は単一出力であり、対応するアドレス生成回路よりも複雑になることはない。【００３７】
〔定義６〕（ｐｑ素子）
ｐｑ素子（pq-element）とは、任意のｐ入力ｑ出力論理関数を実現するメモリであり、そのメモリ量（memory size）は2pqである。
（定義終り）【００３８】
〔定理１〕
重みkのアドレス生成論理関数は、ｐｑ素子を下式（３）で表される個数だけ用いて合成可能である。【００３９】
【数３】
0004742281.tif 000008
（定理終り）【００４０】
（証明）
重みkのアドレス生成論理関数Fは、下式（４）のように関数分解が可能である。【００４１】
【数４】
0004742281.tif 000009
このとき、補題１より、G(X1',X2)も重みkのアドレス生成関数であり、入力数はn-(p-q)に減っている。この操作を【００４２】
【数５】
0004742281.tif 000010
繰り返すことにより、入力数をqまで削減することが可能である。従って、ｐｑ素子のみを用いて、アドレス生成回路を構成することが可能である。
（証明終り）【００４３】
（例３）
（表２）に示した5変数のアドレス生成関数F(X)の非零出力数は、k=7である。従って、式（６）となり、図１に示すように、４入力３出力素子で実現可能である。【００４４】
【数６】
0004742281.tif 000011
（例終り）【００４５】
ｐｑ素子を用いて回路合成をする際、pを大きくすると、回路を実現するために必要なpq素子の数は減るが、総メモリ量は増える。一方、pを小さくすると、総メモリ量は減るが、ｐｑ素子数は増える。アドレス生成回路をｐｑ素子で合成する場合、総メモリ量を増やさずに素子数を最小化するようなｐの決定方法は、次の定理により示される。【００４６】
〔定理２〕
アドレス生成論理関数をｐｑ素子の多段論理回路として実現する場合、総メモリ量の上限は、p-q=1又はp-q=2のときに最小となる。
（定理終り）【００４７】
（証明）
アドレス生成回路をｐｑ素子を用いて関数分解する場合、1回分解する毎に、回路の入力線をr=p-q本削減することができる。ｎ本の入力線をｑ本まで削減するためには、【００４８】
【数７】
0004742281.tif 000012
の関数分解が必要である。また、回路実現のためには、ｓ個のｐｑ素子が必要である。従って必要な総メモリ量は、【００４９】
【数８】
0004742281.tif 000013
となる。nが十分に大きい場合には、【００５０】
【数９】
0004742281.tif 000014
と近似できる。ｎとｐは与えられた問題により固定されているので、ｒのみを変化させることができる。2r/rは、r=1又はr=2のとき最小値をとる。従って、上記定理が証明される。
（証明終り）【００５１】
通常は、回路の段数は少ない方が望ましいので、r=p-q=2として回路を構成する。（定理１）は、関数分解を繰り返すことにより、アドレス生成回路をｐｑ素子の多段論理回路として合成可能であることを示している。次に示す（例３）は、関数分解の方法によって、LUTカスケード論理回路を含む、種々の多段論理回路を合成することが可能であることを示している。【００５２】
（例４）
入力数n=48、重みk=255のアドレス生成回路を構成する。【００５３】
【数１０】
0004742281.tif 000015
である。これより、メモリ量を最小にし, 段数も減らすpの値はp=10である。ｐｑ素子１個に対して、入力線数が２減るので、ｐｑ素子を２０個用いることで、入力数を８まで削減できる. ２０個のｐｑ素子で, 例えば, 図２のようなアドレス生成回路を実現可能である。この場合、段数は１０段, メモリ量は１６０kbitである。【００５４】
また、入力数の大きい素子を用いることにより、素子数と遅延時間を削減することができる。図３はｐ＝１１，ｑ＝８の例である。この場合、素子数は(48-8)/(11-8)=14、段数は8段、メモリ量は212kbitである。また、図４は、p=12,q=8の例である。この場合、素子数は(48-8)/(12-8)=10、段数は5段、メモリ量は320kbitである。
（例終り）【００５５】
定理２は、一般のアドレス生成関数を実現する際、総メモリ量の上限を最小とする条件を示している。特定のアドレス生成関数に対しては、p-q=2以外の場合に、総メモリ量が最小になることもある。【００５６】
次に、アドレス生成関数のアドレス表を変化させた場合におけるｐｑ素子の多段論理回路の再構成方法について説明する。多段論理回路の修正は、
（１）登録ベクトルの除去
（２）登録ベクトルの追加
の２つの基本操作に分解することができる。そこで、以下は上記（１）（２）の場合について考察する。【００５７】
また、上述したように、ｐｑ素子の多段論理回路は、目的論理関数Fに対して関数分解を繰り返したものである。従って、目的論理関数Fのアドレス表を変化させた場合に、関数分解F(X1,X2)=G(H(X1),X2)において、関数Hと関数Gの修正法を示せば十分である。【００５８】
尚、以下の説明において、「入力変数（input variable）」，「出力変数（output variable）」というときは、値がまだ決まっていない場合をいう。また、「入力ベクトル（input vector）」，「出力ベクトル（output vector）」というときは、入力変数，出力変数の具体的に決まった値をいう。【００５９】
（１）登録ベクトルの除去
入力変数X（∈Bn）の分割をX=(X1,X2)とおく。アドレス生成関数F(X)の関数分解をF(X1,X2)=G(H(X1),X2)と記す。ベクトルa（∈Bn）はアドレス生成関数F(X)の登録ベクトルであるとする。また、入力変数の分割X=(X1,X2)に対応するベクトルaの分割をa=(a1,a2)と記す。【００６０】
アドレス生成関数F(X)のアドレス表から登録ベクトルaを除去する場合を考える。尚、以下ではアドレス表がＬＵＴカスケード論理回路で実現されている場合について考える。【００６１】
アドレス表からベクトルaを除去した場合、F(a)=0となる。従って、G(H(a1),a2)=0である。【００６２】
一方、部分関数G(Y1,X2)の一方の変数Y1を固定値H(a1)として変数X2を変化させた場合、X2=a2以外にG(H(a1),X2)≠0となる変数X2が存在しない場合、もとのアドレス表においてベクトルa以外の登録ベクトルの出力ベクトルは、部分関数の値H(a1)には依存しない。従って、この場合、H(a1)は無効な値であるためH(a1)=0としてもよい。【００６３】
以上より、アドレス表からの登録ベクトルaの除去に伴うＬＵＴカスケード論理回路の修正は、次のようなアルゴリズムに従って行うことができる。【００６４】
（アルゴリズム１）
（Step 1）  未修正のｐｑ素子のうち、最も出力側に近いものを選択する。選択されたｐｑ素子をEGと記す。ｐｑ素子EGにより表される部分関数をG(H(X1),X2)とする。ここで、(X1, X2)⊆XかつX1∩X2=φである。（X1,X2)に対する入力ベクトルを(a1, a2)とする。但し、ｐｑ素子EGが最も出力側から遠い場合はX1=φ, H(X1)=φとする。【００６５】
（Step 2）  ｐｑ素子EGに記憶されたＬＵＴの出力ベクトルのうち、入力ベクトル(H(a1),a2)に対応する出力ベクトルをG(H(a1),a2)=0とする。ｐｑ素子EGを修正済とする。【００６６】
（Step 3）  出力ベクトルG(H(a1),X2)が非零となる部分変数X2に対する入力ベクトルa0が存在するか検査する。【００６７】
（Step 4）a0が存在しない場合、Step1に戻る。そうでなければ、処理を終了する。
（アルゴリズム終り）【００６８】
上記アルゴリズムを一般のｐｑ素子の多段論理関数の場合に拡張するのは容易である。一般のｐｑ素子の多段論理関数の場合は次のようになる。【００６９】
（アルゴリズム２）
（Step 1）  素子数がsのｐｑ回路網は、関数分解をs-1回繰り返し適用して構成できる。各関数分解で、入力側から順にｐｑ素子を抽出し、各ｐｑ素子に１からsまでの番号を付与する。出力のｐｑ素子の番号はsである。番号１の素子E1は、出力から最も離れている。【００７０】
（Step 2）  ｐｑ素子の集合をpとし、初期値をp={Es}とする。【００７１】
（Step 3）  多段論理回路において、pの要素とそれ以外の素子で構成された回路の関数分解G(H1(Y1), H2(Y2),…, Hm(Ym))を考える。ここで、Yiは中間変数で、特別な場合としてHk(Yk)=Ykも考える。【００７２】
（Step 4）  G(H1(a1), H2(a2),…, H2(a2))=0とする。ここで、a=(a1,a2,…,am)は、中間変数のベクトルである。Hi(ai)=d≠0のとき、他の登録ベクトルbに対して、Hi(ai)=dとなるものが存在しないとき、Hi(ai)=0とする。【００７３】
（Step 5）  ｐｑ素子の集合pの要素数がs-1ならば処理を終了する。そうでなければ、pに素子番号が最も大きい素子を追加して、Step3に戻る。
（アルゴリズム終り）【００７４】
（２）登録ベクトルの追加
次に、アドレス生成関数F(X)のアドレス表に登録ベクトルaを追加する場合を考える。新たに追加する登録ベクトルaに対する出力ベクトルをcとする。尚、以下ではアドレス表がＬＵＴカスケード論理回路で実現されている場合について考える。【００７５】
アドレス表にベクトルaを追加した場合、F(a)=cとなる。従って、G(H(a1),a2)=cである。【００７６】
ここで、登録ベクトルaに対してF(a)の値を一対一に対応させるためには、部分関数H(a1)の値は０であってはならない。そこで、もし部分関数H(a1)の出力ベクトルが０となっている場合には０以外の値に修正する必要がある。この際、他の登録ベクトルの出力に影響を及ぼさないようにする必要があるため、部分関数H(a1)の出力ベクトルは未使用の値に変更する。例えば、部分関数H(X1)の非零出力の最大値よりも大きい未使用の値のうち、最小のものを選択することができる。【００７７】
以上より、アドレス表への登録ベクトルaの追加に伴うＬＵＴカスケード論理回路の修正は、次のようなアルゴリズムに従って行うことができる。【００７８】
（アルゴリズム３）
（Step 1）  未修正のｐｑ素子のうち、最も出力側から遠いものを選択する。選択されたｐｑ素子をEGと記す。ｐｑ素子EGにより表される部分関数をG(H(X1),X2)とする。ここで、(X1, X2)⊆XかつX1∩X2=φである。（X1,X2)に対する入力ベクトルを(a1, a2)とする。但し、ｐｑ素子EGが最も出力側から遠い場合は、X1=φ, H(X1)=φとする。【００７９】
（Step 2）  e0=G(H(a1), a2)とする。pq素子EGが最も出力側の場合、e=c。そうでない場合、e0 ≠ 0ならばe=e0、e0=0ならばpq素子EGで可能な出力値のうち、未使用の正の出力値で、最小のものをeとする。【００８０】
（Step 3）  pq素子EGに記憶されたLUTの出力ベクトルのうち、入力ベクトル(H(a1), a2)に対応する出力ベクトルをG(H(a1),a2)=eとする。【００８１】
（Step 4）  未修正のｐｑ素子が残っていれば、Step 1に戻る。そうでなければ、処理を終了する。
（アルゴリズム終り）【００８２】
上記アルゴリズムを一般のｐｑ素子の多段論理関数の場合に拡張するのは容易である。一般のｐｑ素子の多段論理関数の場合は次のようになる。【００８３】
（アルゴリズム４）
（Step 1）  素子数がsのｐｑ回路網は、関数分解をs-1回繰り返し適用して構成できる。各関数分解で、入力側から順にｐｑ素子を抽出し、素子に１からｒまで番号を付与する。出力の素子の番号はsである。番号１の素子E1は、出力から最も離れている。入力変数Xに対する入力ベクトルをaとする。番号１のｐｑ素子E1をEGとする。
【００８４】
（Step 2）  多段論理回路に入力ベクトルaを入力する。このときのEGの出力ベクトルをe0とする。【００８５】
（Step 3）  ｐｑ素子EGが最も出力側の場合、e=c。そうでない場合、e0≠0ならばe=e0、e0=0ならばｐｑ素子EGで可能な出力値のうち、未使用の正の出力値で、最小のものをeとする。【００８６】
（Step 4）  ｐｑ素子EGに記憶されたＬＵＴの出力ベクトルのうち、入力ベクトルaに対応する出力ベクトルをeとする。【００８７】
（Step 5）  EGが最も出力側のｐｑ素子ならば、処理を終了する。そうでなければ、Step 1で順序づけた、EGの次のｐｑ素子をEGとして、Step 2に戻る。
（アルゴリズム終り）【００８８】
以上のような登録ベクトルの削除と登録ベクトルの追加を行うことにより、アドレス生成関数のアドレス表を変化させた場合におけるｐｑ素子の多段論理回路の再構成が可能となる。ｐｑ素子の多段論理回路がＬＵＴカスケードの場合、セル数及び登録ベクトル数（アドレス数）に比例する時間で、アドレス表のアドレスの追加及び除去が可能となる。【００８９】
〔２〕本発明の構成及び作用
本発明に係る多段論理回路の再構成装置の第１の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成装置であって、
未修正の前記ｐｑ素子のうち出力側に最も近いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、を備えたことを特徴とする。【００９０】
この構成によれば、
（１）まず、素子選択手段は未修正のｐｑ素子のうち出力側に最も近いｐｑ素子EGから順次選択する。
（２）次に、対応検査手段は、ｐｑ素子EGの入力ベクトルbに対する出力ベクトルcが入力ベクトルbと一対一対応か否かを検査する。
（３）次に、入力ベクトルbが前記出力ベクトルcに一対一に対応する場合には、削除修正手段は、ｐｑ素子EGのＬＵＴにおいて、入力ベクトルbに対する出力値を無効値に書き換え、当該ｐｑ素子EGを修正済みとする。【００９１】
以上のような（１）〜（３）の処理を繰り返すことにより、上述のアルゴリズム１又は２で説明したように、ｐｑ素子の多段論理回路において、入力ベクトルbに対する出力ベクトルF(b)を無効値に変更する論理変更を行うことができる。【００９２】
ここで、「多段論理回路」とは、上述したような複数のｐｑ素子がカスケード状又は樹形状に接続した論理回路であり、ＬＵＴカスケード論理回路も含まれる。「無効値」とは、出力ベクトルF(b)が無効であることを表す値であり、通常は０とされるが、必ずしもそれに限られるものではない。【００９３】
本発明に係る多段論理回路の再構成装置の第２の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成装置であって、
未修正の前記ｐｑ素子のうち出力側から最も遠いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGが最も出力側ではない場合において、当該ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該ｐｑ素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記ｐｑ素子EGが最も出力側の場合において、前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該ｐｑ素子EGを修正済みとする追加修正手段と、を備えていることを特徴とする。【００９４】
この構成によれば、
（１）まず、素子選択手段は、未修正のｐｑ素子のうち出力側から最も遠いｐｑ素子EGから順次選択する。
（２）次に、素子選択手段が選択したｐｑ素子EGが最も出力側ではない場合には、対応付手段は、当該ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該ｐｑ素子の出力ベクトルとして使用していないベクトル値に変更する。
（３）一方、素子選択手段が選択したｐｑ素子EGが最も出力側の場合、追加修正手段は、ｐｑ素子EGのＬＵＴにおいて、入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該ｐｑ素子EGを修正済みとする。
以上のような（１）〜（３）の処理を繰り返すことにより、上述のアルゴリズム３又は４で説明したように、ｐｑ素子の多段論理回路において、入力ベクトルbに対する出力ベクトルaを追加する論理変更を行うことができる。【００９５】
本発明に係る論理回路修正装置の第１の構成は、入力変数Xの目的論理関数Q(X)を演算する主論理回路について、前記入力変数Xとして入力される各入力ベクトルbのうち特定の対象入力ベクトルbiに対する主論理回路の出力ベクトルQ(bi)を、修正出力ベクトルQ'(bi)に変更する論理回路修正装置であって、
前記各対象入力ベクトルbiに対応して、前記各出力ベクトルQ(bi)を修正出力ベクトルQ'(bi)に修正するための修正用ベクトルPiが所定のアドレスAiに登録される補助メモリと、
前記補助メモリが出力する修正用ベクトルPiを出力した場合、当該修正用ベクトルPi及び前記主論理回路が出力する出力ベクトルQ(bi)に基づいて、前記修正出力ベクトルQ'(bi)を出力する修正手段と、
前記入力変数Xに対して、当該入力変数Xの値が前記対象入力ベクトルbiに等しい場合は前記修正用ベクトルPiが格納された前記補助メモリのアドレスAiを出力するアドレス生成関数F(X)の演算を行うアドレス生成回路と、を備え、
前記アドレス生成回路は、前記アドレス生成関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路により構成されており、
前記補助メモリは、前記アドレス生成回路が出力するアドレスAiが入力されると、前記修正手段に前記修正用ベクトルPiを出力することを特徴とする。【００９６】
この構成によれば、まず、主論理回路に入力変数Xとして入力ベクトルbが入力された場合、主論理回路は目的論理関数を演算し、出力ベクトルQ(b)を出力する。一方、アドレス生成回路は、入力ベクトルbに対してアドレス生成関数F(b)を演算する。入力ベクトルbが対象入力ベクトルbiであれば、アドレス生成回路は、アドレスAiを出力する。このアドレスAiは、補助メモリに入力される。補助メモリは、アドレスAiに対して修正用ベクトルPiを出力する。そして、修正手段は、修正用ベクトルPiと出力ベクトルQ(bi)に基づいて、修正出力ベクトルQ'(bi)を出力する。これにより、目的論理関数の出力値の変更が行われる。尚、入力ベクトルbが対象入力ベクトルbi以外の場合には、アドレス生成回路は、アドレスAiを出力しないため、補助メモリは修正用ベクトルPiを出力しない。従って、修正手段は、出力ベクトルQ(bi)の修正を行うことなく、出力ベクトルQ(bi)がそのまま出力される。【００９７】
本発明においては、アドレス生成回路としてｐｑ素子の多段論理回路を使用するため、上に説明したように少ないメモリ容量でアドレス生成回路を実現することが可能である。従って、論理回路修正装置の実装面積を小さくでき、省電力化も図られる。また、上述したアルゴリズム１，２及びアルゴリズム３，４により、アドレス生成回路の論理変更も可能であり、要求に応じて主論理回路の出力を自在に修正することができる。【００９８】
また、本発明に係る論理回路修正装置の場合、アドレス生成回路の再構成を行う際に、ｐｑ素子（メモリ）の内容を書き換えるのみであり、配線経路の変更は行う必要がない。従って、配線遅延の影響などを考慮する必要がなく容易にアドレス生成回路の変更を行うことができる。更に、配線の変更を伴わないことから、主論理回路の動作期間中にリアルタイムで動的な変更を行うことが可能である。【００９９】
本発明に係る論理回路修正装置の第２の構成は、前記第１の構成において、前記修正用ベクトルPiは、対象入力ベクトルbiに対する主論理回路の出力ベクトルQ(bi)との排他論理和が、前記修正出力ベクトルQ'(bi)となる値に設定され、
前記補助メモリは、前記アドレス生成回路が出力するアドレスAiが入力されると、前記修正手段に前記修正用ベクトルPiを出力し、それ以外の場合は０を出力するものであり、
前記修正手段は、前記補助メモリの出力値と前記主論理回路との排他論理和演算を行うＥＸＯＲゲートであることを特徴とする。【０１００】
本発明に係る論理回路修正装置の第３の構成は、前記第１の構成において、前記修正手段は、前記主論理回路及び前記補助メモリの出力段にそれぞれ設けられたトライ・ステート・バッファであり、
前記アドレス生成回路は、前記入力変数Xに対して、当該入力変数Xの値がいずれの前記対象入力ベクトルbiとも等しくない場合には、無効値を出力するものであり、
前記主論理回路の出力段の前記トライ・ステート・バッファは、前記アドレス生成回路の出力値が無効値でない場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となり、
前記補助メモリの出力段の前記トライ・ステート・バッファは、前記アドレス生成回路の出力値が無効値の場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となることを特徴とする。【０１０１】
本発明に係る論理回路修正装置の第４の構成は、前記第１乃至３の何れか一の構成において、前記補助メモリは、前記アドレス生成回路の最終段のｐｑ素子であることを特徴とする。但し、最終段の素子の出力数は、ｑ以上になってもよいと考える。【０１０２】
本発明に係る論理回路修正装置の第５の構成は、前記第１乃至４の何れか一の構成において、前記アドレス生成回路において、入力ベクトルbに対する前記アドレス生成関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記アドレス生成回路の再構成を行う再構成装置を備え、
前記再構成装置は、
未修正の前記ｐｑ素子のうち出力側に最も近いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、を備えたことを特徴とする。【０１０３】
本発明に係る論理回路修正装置の第６の構成は、前記第１乃至４の何れか一の構成において、前記アドレス生成回路において、前記アドレス生成関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記アドレス生成回路の再構成を行う再構成装置を備え、
前記再構成装置は、
未修正の前記ｐｑ素子のうち出力側から最も遠いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGが最も出力側ではない場合において、当該ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該ｐｑ素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記ｐｑ素子EGが最も出力側の場合において、前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該ｐｑ素子EGを修正済みとする追加修正手段と、を備えていることを特徴とする。【０１０４】
本発明に係る多段論理回路の再構成方法の第１の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成方法であって、
未修正の前記ｐｑ素子のうち出力側に最も近いｐｑ素子EGから順次選択する素子選択ステップと、
前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査ステップと、
前記ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正ステップと、
を繰り返し実行することを特徴とする。【０１０５】
本発明に係る多段論理回路の再構成方法の第２の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された多段論理回路において、前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う多段論理回路の再構成方法であって、
未修正の前記ｐｑ素子のうち出力側から最も遠いｐｑ素子EGから順次選択する素子選択ステップと、
前記ｐｑ素子EGが最も出力側ではない場合において、当該ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該ｐｑ素子の出力ベクトルとして使用していないベクトル値に変更する対応付ステップと、
前記ｐｑ素子EGが最も出力側の場合において、前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該ｐｑ素子EGを修正済みとする追加修正ステップと、を繰り返し実行することを特徴とする。【０１０６】
本発明に係る再構成可能多段論理回路の第１の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された再構成可能な多段論理回路であって、
入力ベクトルbに対する前記目的論理関数F(X)の出力ベクトルF(b)を無効値に変更する論理変更に伴い、前記多段論理回路の再構成を行う再構成回路を備え、
前記再構成回路は、
未修正の前記ｐｑ素子のうち出力側に最も近いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルをcとしたとき、当該出力ベクトルcに対応する入力ベクトルが、前記入力ベクトルb以外にも存在するか否かを検査する対応検査手段と、
前記ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴにおいて、前記入力ベクトルbが前記出力ベクトルcに一対一に対応する場合、前記入力ベクトルbに対する出力ベクトルcを無効値に書き換える削除修正手段と、を備えたことを特徴とする。【０１０７】
この構成により、上述したとおり、再構成回路はｐｑ素子（メモリ）の内容を書き換えるのみで、容易に目的論理関数F(X)の出力ベクトルF(b)を削除することができる。また、配線の変更を伴わないことから、論理回路の動作期間中にリアルタイムで動的な変更を行うことが可能である。【０１０８】
本発明に係る再構成可能多段論理回路の第１の構成は、入力変数をXとする目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶された複数のｐｑ素子が、前記各部分関数の入出力の接続関係に従って回路的に接続された再構成可能多段論理回路であって、
前記目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、前記多段論理回路の再構成を行う再構成回路を備え、
前記再構成回路は、
未修正の前記ｐｑ素子のうち出力側から最も遠いｐｑ素子EGから順次選択する素子選択手段と、
前記ｐｑ素子EGが最も出力側ではない場合において、当該ｐｑ素子EGを修正済みとするとともに、当該ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値の場合、当該出力ベクトルcを、当該ｐｑ素子の出力ベクトルとして使用していないベクトル値に変更する対応付手段と、
前記ｐｑ素子EGが最も出力側の場合において、前記ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcを出力ベクトルaに書き換え、当該ｐｑ素子EGを修正済みとする追加修正手段と、を備えていることを特徴とする。【０１０９】
この構成により、上述したとおり、再構成回路はｐｑ素子（メモリ）の内容を書き換えるのみで、容易に目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更を行うことができる。また、配線の変更を伴わないことから、論理回路の動作期間中にリアルタイムで動的な変更を行うことが可能である。
【発明の効果】
【０１１０】
以上のように、本発明に係る多段論理回路の再構成装置によれば、ｐｑ素子で構成される多段論理回路の論理変更に伴う再構成を、短時間に行うことができる。また、再構成処理は少ない計算量で短時間に行うことができ、再構成計算に必要とされるメモリ容量も小さいため、チップ内に専用回路として組み込むことが可能である。【０１１１】
また、本発明に係る論理回路修正装置によれば、アドレス生成回路としてｐｑ素子の多段論理回路を使用するため、上述したように少ないメモリ容量でアドレス生成回路を実現することが可能である。従って、論理回路修正装置の実装面積を小さくでき、省電力化も図られる。また、アドレス生成回路の論理変更も可能であり、要求に応じて主論理回路の出力を自在に修正することができる。
【図面の簡単な説明】
【０１１２】
【図１】アドレス生成論理関数Fの関数分解を示す図である。
【図２】ｐｑ素子によるアドレス生成回路（ｐ＝１０）の例を示す図である。
【図３】ｐｑ素子によるアドレス生成回路（ｐ＝１１）の例を示す図である。
【図４】ｐｑ素子によるアドレス生成回路（ｐ＝１２）の例を示す図である。
【図５】本発明の実施例１に係る再構成可能な多段論理回路の構成を表す図である。
【図６】ｓ個のｐｑ素子E(1), E(2), …, E(s)が直列に接続されたカスケード論理回路を示す図である。
【図７】再構成装置１による目的論理関数F(X)の登録ベクトルの削除処理を表すフローチャートである。
【図８】再構成装置１による目的論理関数F(X)の登録ベクトルの追加処理を表すフローチャートである。
【図９】例５のアドレス生成関数F(X)を実現するＬＵＴカスケード論理回路である。
【図１０】本発明の実施例２に係る論理回路修正装置２０の構成を示す図である。
【図１１】本発明の実施例３に係る論理回路修正装置２０の構成を示す図である。
【図１２】本発明の実施例４に係る再構成可能な多段論理回路の構成を表す図である。
【図１３】Xilinx社のＦＰＧＡで用いられている４入力ＬＵＴである。
【図１４】４入力ＬＵＴを３個用いた１２入力１出力の回路である。
【図１５】ＬＵＴカスケード論理回路を一般的に表したものである。
【図１６】参照テーブル９のテーブルの例である。
【図１７】インデックス・テーブルの例である。
【図１８】実施例４に係る再構成可能な多段論理回路の登録ベクトルの追加処理のフローチャートである。
【図１９】実施例４に係る再構成可能な多段論理回路の登録ベクトルの削除処理のフローチャートである。
【図２０】特許文献１に記載の論理回路修正装置１０３の構成を示す図である。
【符号の説明】
【０１１３】
１，１’  再構成回路
２  素子選択手段
３  素子選択手段
４  対応検査手段
５  削除修正手段
６  対応付手段
７  追加修正手段
８  インデックス・テーブル
９  参照テーブル
１０  多段論理回路
１１  入力データバス
１２  出力データバス
１３  ｐｑ素子
２０  論理回路修正装置
２１  アドレス生成回路
２２  補助メモリ
２３  修正回路
２４  ＥＸＯＲゲート
３０  主論理回路
３１  入力バス
３２  出力バス
４１＿０〜４１＿１５  Ｄフリップ・フロップ（ＤＦＦ）
４２  マルチプレクサ（ＭＵＸ）
４３  クロック線
４４  登録値入力線
４４  データ入力線
【発明を実施するための最良の形態】
【０１１４】
以下、本発明を実施するための最良の形態について、図面を参照しながら説明する。
【実施例１】
【０１１５】
図５は、本発明の実施例１に係る再構成可能な多段論理回路の構成を表す図である。この再構成可能な多段論理回路は、多段論理回路１０と再構成装置１とが組み合わされたシステムとして構成されている。再構成回路１は、多段論理回路１０の論理変更に伴い、多段論理回路１０の再構成を行う装置である。【０１１６】
多段論理回路１０は、入力変数をXとする目的論理関数F(X)の演算を行う論理回路である。この多段論理回路１０は、複数のｐｑ素子１３を備えている。各ｐｑ素子１３には、目的論理関数F(X)を関数分解して得られる部分関数のＬＵＴが記憶されている。また、それぞれのｐｑ素子１３は、各部分関数の入出力の接続関係に従って回路的に接続されている。多段論理回路１０の構造としては、ＬＵＴカスケードや図２〜図４に示したようなｐｑ回路網などを用いることができる。【０１１７】
入力変数Xはｎ次元の２値ベクトルの変数である。目的論理関数F(X)の出力変数Yはｍ次元の２値ベクトルの変数である。入力変数Xは２ｎ個の値を取り得る。そのうちのｋ個（ｋ＜２ｎ）の入力ベクトルを「登録ベクトル（registered vector）」と呼ぶ。それ以外のベクトルを「無効ベクトル（invalid vector）」と呼ぶ。【０１１８】
多段論理回路１０の入力データバス１１からは、入力変数Xとして入力ベクトルbが入力される。また、多段論理回路１０の出力データバス１２からは、出力変数Y=F(X)として出力ベクトルaが出力される。【０１１９】
再構成回路１は、素子選択手段２，３、対応検査手段４、削除修正手段５、対応付手段６、追加修正手段７、及び多段論理回路１０を備えている。【０１２０】
目的論理関数F(X)の入力ベクトルbに対する出力ベクトルF(b)を無効値にする論理変更に伴い、削除処理が実行され、多段論理回路１０の再構成が行われる。この削除処理において、素子選択手段２は、未修正の前記ｐｑ素子１３を、出力側に最も近いｐｑ素子EGから、順次選択する。対応検査手段４は、ｐｑ素子EGのＬＵＴにおいて、入力ベクトルbが出力ベクトルcに一対一に対応しているか否か検査する。削除修正手段５は、ｐｑ素子EGのＬＵＴにおいて、入力ベクトルbが出力ベクトルcに一対一に対応している場合に、入力ベクトルbに対する出力値を無効値に書き換え、当該ｐｑ素子EGを修正済みとする。【０１２１】
一方、目的論理関数F(X)の出力ベクトル集合に入力ベクトルbに対する出力ベクトルaを追加する論理変更に伴い、追加処理が実行され、多段論理回路１０の再構成が行われる。この追加処理において、素子選択手段３は、未修正のｐｑ素子１３を、出力側から最も遠いｐｑ素子EGから、順次選択する。対応付手段６は、ｐｑ素子EGが最も出力側ではない場合、当該ｐｑ素子EGを修正済みとする。更にこの場合において、対応付手段６は、当該ｐｑ素子EGのＬＵＴの出力ベクトルのうち前記入力ベクトルbに対する出力ベクトルcが無効値ならば、当該出力ベクトルcを、当該ｐｑ素子の出力ベクトルとして使用していないベクトル値に変更する。追加修正手段７は、ｐｑ素子EGが最も出力側の場合、ｐｑ素子EGのＬＵＴの入力ベクトルbに対する出力値を出力ベクトルaに書き換え、当該ｐｑ素子EGを修正済みとする。【０１２２】
以上のように構成された本実施例１に係る多段論理回路の再構成回路１について、以下その動作を説明する。【０１２３】
尚、以下の説明において、多段論理回路１０は、図６に示したようなｓ個のｐｑ素子E(1), E(2), …, E(s)が直列に接続されたカスケード論理回路とする。各ｐｑ素子は、入力側からE(1), E(2), …, E(s)の順に接続されている。【０１２４】
入力変数をXとする。入力変数Xの分割をX=(X1,X2,…,Xs)とする。また、入力変数Xに対する目的論理関数F(X)の出力変数をY=F(X)とする。目的論理関数F(X)を次式（１１）のように部分関数G1,G2,…,Gsに関数分解する。式（１１）においてUi（i=1，2，…，s-1）は中間変数である。【０１２５】
【数１１】
0004742281.tif 000016
【０１２６】
ｐｑ素子E(i)(i=1,2,…,s)には、中間関数GiのＬＵＴが記憶されている。ｐｑ素子E(1)は、入力変数X1が入力される。それに対し、ｐｑ素子E(1)は出力変数U1=G1(X1)を出力する。ｐｑ素子E(i)（i=2,3,…,s）は、前段のｐｑ素子E(i-1)の出力変数Ui-1と入力変数Xiが入力される。それに対し、ｐｑ素子E(i)は出力変数Ui=Gi(Xi, Ui-1)を出力する。また、ｐｑ素子E(s)の出力変数Usは出力変数Yである。【０１２７】
最初に、目的論理関数F(X)の登録ベクトルの削除処理について説明する。図７は、再構成回路１による目的論理関数F(X)の登録ベクトルの削除処理を表すフローチャートである。【０１２８】
ここでは、目的論理関数F(X)の登録ベクトルｂを削除する論理変更に伴う、多段論理回路１０の再構成について説明する。尚、入力変数Xの部分変数Xiに対応する入力ベクトルbの部分値をbiと記す。【０１２９】
まず、ステップＳ１において、削除する登録ベクトルｂが入力されると、素子選択手段２はインデックスｉをｓに設定する。インデックスｉはｐｑ素子の選択番号を示すインデックスである。これにより、最も出力側のｐｑ素子E(s)が選択される。【０１３０】
次に、ステップＳ２において、素子選択手段２は、ｐｑ素子E(i)のＬＵＴを読み出す。【０１３１】
次に、ステップＳ３において、削除修正手段５は、読み出されたＬＵＴにおいて、入力ベクトルｂに対応する出力ベクトルui(b)を０とする。入力ベクトルｂに対応する出力ベクトルui(b)は、前段のｐｑ素子E(i-1)の出力ベクトルui-1(b)及び部分値biに対応する出力ベクトルである。前段のｐｑ素子E(i-1)の出力ベクトルui-1(b)は、多段論理回路１０に入力ベクトルｂを入力して演算を行い、中間変数Ui-1を取り出すことにより得られる。【０１３２】
次に、ステップＳ４において、修正されたＬＵＴをｐｑ素子E(i)に書き込むことにより、ｐｑ素子E(i)を更新する。【０１３３】
次に、ステップＳ５において、素子選択手段２は、インデックスｉが２以上であるか否かを判定する。インデックスｉが１の場合には、登録ベクトルの削除処理を終了する。そうでない場合には、次のステップＳ６に移行する。【０１３４】
ステップＳ６において、素子選択手段２は、選択番号を示すインデックスｉを１だけデクリメントする。【０１３５】
次に、ステップＳ７において、素子選択手段２は、ｐｑ素子E(i)のＬＵＴを読み出す。【０１３６】
次に、ステップＳ８において、対応検査手段４は、ｐｑ素子E(i)の入力ベクトルｂに対する出力ベクトルui(b)を抽出する。入力ベクトルｂに対応する出力ベクトルui(b)は、前段のｐｑ素子E(i-1)の出力ベクトルui-1(b)及び部分値bi（i=1の場合は、部分値bi）に対応する出力ベクトルである。前段のｐｑ素子E(i-1)の出力ベクトルui-1(b)は、多段論理回路１０に入力ベクトルｂを入力して演算を行い、中間変数Ui-1を取り出すことにより得られる。【０１３７】
次に、ステップＳ９において、対応検査手段４は、出力ベクトルui(b)に対応する入力ベクトルが、入力ベクトルｂ以外にもあるか否かを判定する。これは、ＬＵＴの出力値を調べ、出力ベクトルui(b)と同じ値が２個以上あるか否かを検査すればよい。対応する入力ベクトルが２個以上あった場合には、登録ベクトルの削除処理を終了する。そうでない場合には、次のステップＳ３に戻る。【０１３８】
以上の一連の処理により、目的論理関数F(X)の登録ベクトルｂを削除する論理変更に伴う多段論理回路１０の再構成を行うことができる。この処理は、各ｐｑ素子E(i)のＬＵＴの読み出しと書き換えのみであり、高速に実行することができる。また、複雑な演算処理も必要としないため、素子選択手段２、対応検査手段４、及び削除修正手段５は簡単な回路で実現することができる。【０１３９】
次に、目的論理関数F(X)の登録ベクトルの追加処理について説明する。図８は、再構成回路１による目的論理関数F(X)の登録ベクトルの追加処理を表すフローチャートである。【０１４０】
ここでは、目的論理関数F(X)の登録ベクトルｂを追加する論理変更に伴い、多段論理回路１０の再構成を行う。登録ベクトルｂに対応する目的論理関数F(X)の出力ベクトルをaとする。尚、入力変数Xの部分変数Xiに対応する入力ベクトルbの部分値をbiと記す。【０１４１】
まず、ステップＳ１１において、追加する登録ベクトルb及び出力ベクトルをaが入力されると、素子選択手段３は、ｐｑ素子の選択番号を示すインデックスｉを１に設定する。これにより、最も入力側のｐｑ素子E(1)が選択される。【０１４２】
次に、ステップＳ１２において、素子選択手段３は、ｐｑ素子E(i)のＬＵＴを読み出す。【０１４３】
次に、ステップＳ１３において、対応付手段６は、インデックスｉが最大値ｓか否かを検査する。ｉ＝ｓの場合にはステップＳ２０に移行し、そうでない場合には次のステップＳ１４に移行する。【０１４４】
ステップＳ１４において、対応付手段６は、読み出されたＬＵＴにおいて、入力ベクトルｂに対応する出力ベクトルui(b)を計算する。入力ベクトルｂに対応する出力ベクトルui(b)は、前段のｐｑ素子E(i-1)の出力ベクトルui-1(b)及び部分値bi（i=1の場合は、部分値bi）に対応する出力ベクトルである。前段のｐｑ素子E(i-1)の出力ベクトルui-1(b)は、多段論理回路１０に入力ベクトルｂを入力して演算を行い、中間変数Ui-1を取り出すことにより得られる。【０１４５】
次に、ステップＳ１５において、対応付手段６は、出力ベクトルui(b)が０か否かを検査する。ui(b)≠０の場合には、ステップＳ１９に移行する。ｓ＝０の場合には、次のステップＳ１６に移行する。【０１４６】
ステップＳ１６において、対応付手段６は、ｐｑ素子E(i)のＬＵＴの出力ベクトルを検査し、出力ベクトルとして未使用の値のうち最小の値（ベクトル）ｅを抽出する。【０１４７】
次に、ステップＳ１７において、対応付手段６は、ｐｑ素子E(i)のＬＵＴの入力ベクトルｂに対応する出力ベクトルui(b)をeに変更する。【０１４８】
次に、ステップＳ１８において、対応付手段６は、ｐｑ素子E(i)に、更新したＬＵＴを書き込むことにより、ｐｑ素子E(i)を更新する。【０１４９】
次に、ステップＳ１９において、素子選択手段３は、選択番号を示すインデックスｉを１だけインクリメントし、ステップＳ１２に戻る。【０１５０】
一方、ステップＳ１３においてｉ＝ｓの場合、ステップＳ２０において、追加修正手段７は、ｐｑ素子E(i)のＬＵＴの入力ベクトルｂに対応する出力ベクトルui(b)を出力ベクトルaに変更する。【０１５１】
そして、ステップＳ２１において、追加修正手段７は、ｐｑ素子E(i)に、更新したＬＵＴを書き込むことにより、ｐｑ素子E(i)を更新する。【０１５２】
以上の一連の処理により、目的論理関数F(X)の登録ベクトルｂを追加する論理変更に伴う多段論理回路１０の再構成を行うことができる。この処理は、各ｐｑ素子E(i)のＬＵＴの読み出しと書き換えのみであり、高速に実行することができる。また、複雑な演算処理も必要としないため、素子選択手段２及び削除修正手段５は簡単な回路で実現することができる。【０１５３】
また、本実施例の多段論理回路１０では、再構成はメモリの書き換えのみによって実行される。すなわち、多段論理回路１０の再構成に伴う配線構造の変更はない。従って、再構成にあたり配線遅延の影響などをする必要がなく、容易に実行することができる。さらには、論理回路の動作期間中にリアルタイムで動的に論理回路の再構成を行うことも可能である。【０１５４】
（例５）
（表５）に示したような５変数のアドレス生成関数F(X)を考える。【０１５５】
【表５】
0004742281.tif 000017
【０１５６】
入力変数Xの分割X=(X1,X2), X1=(x5, x4, x3, x2), X2=(x1)について関数分解F(X)=G(H(X1), X2)を行い、図９に示したような２つのｐｑ素子から成るＬＵＴカスケード論理回路によりアドレス生成関数F(X)を実現する。このとき、部分関数H, Gの真理値表は（表６），（表７）のようになる。入力側のｐｑ素子には（表６）の部分関数Ｈの真理値表がＬＵＴとして格納される。また、出力側のｐｑ素子には（表７）の部分関数Ｇの真理値表がＬＵＴとして格納される。（表６）（表７）の各行の左側に付された数字は、その行に対応する登録ベクトルのインデックスを表す。【０１５７】
【表６】
0004742281.tif 000018
【０１５８】
【表７】
0004742281.tif 000019
【０１５９】
このアドレス生成関数F(X)について、登録ベクトルb7=(x5 x4 x3 x2 x1)=(11001)を追加する。（表８）は、登録ベクトルb7の真理値表を表す。登録ベクトルb7に対する出力ベクトルには(111)を割り当てることとする。【０１６０】
【表８】
0004742281.tif 000020
【０１６１】
次に、図８のフローチャートに示した方法に従って、各ｐｑ素子のＬＵＴの書き換えを行う。まず、入力側のｐｑ素子に格納された部分関数Ｈの入力ベクトルbに対応する出力ベクトルは、（表６）の(x5 x4 x3 x2)=(1100)の欄を参照すると、(h1, h2, h3)=(110)である。これは０ではないため、部分関数ＨのＬＵＴは変化させない。このとき、入力ベクトルbは（表９）に示したように、(x5 x4 x3 x2)=(1100)の欄に対応付けられる。【０１６２】
【表９】
0004742281.tif 000021
【０１６３】
次に、出力側のｐｑ素子に格納された部分関数Ｇについて考えると、入力ベクトルbに対応する部分関数Ｇの入力ベクトルは(h1, h2, h3 x1)=(1101)である。従って、（表１０）に示したように、部分関数ＧのＬＵＴに、(h1, h2, h3 x1 f1 f2 f3)=(1101111)を追加する。これにより、登録ベクトルb7の追加に伴う各ｐｑ素子の再構成が完了する。【０１６４】
【表１０】
0004742281.tif 000022
【０１６５】
次に、登録ベクトルの削除に伴う各ｐｑ素子の再構成について考える。例として、（表５）のアドレス表に登録された登録ベクトルから、登録ベクトルb3=(01100)を削除する場合について考える。【０１６６】
図７のフローチャートに示した方法に従って、まず出力側のｐｑ素子のＬＵＴの書き換えを行う。（表１０）を参照すると、登録ベクトルb3に対する部分関数Ｇの入力ベクトルは、(h1, h2, h3 x1)=(0110)である。これに対応する出力ベクトルを(000)に変更し、出力側のｐｑ素子のＬＵＴを（表１１）に示したように書き換える。【０１６７】
【表１１】
0004742281.tif 000023
【０１６８】
次に、入力側のｐｑ素子について考える。この場合、更新前の部分関数Ｇの真理値表（表１０）を参照すると、前段のＬＵＴの出力ベクトル(h1, h2, h3)が登録ベクトルb3に対する出力ベクトル(011)と同じで、非零の出力を持つ登録ベクトルとして、b3の他にb4=(01111)が存在する。従って、入力側のｐｑ素子についてはＬＵＴの書き換えは行われない。以上により、登録ベクトルb3の削除に伴う各ｐｑ素子の再構成が完了する。【０１６９】
次に、さらに登録ベクトルb4=(01101)を削除する場合について考える。図７のフローチャートに示した方法に従って、まず出力側のｐｑ素子のＬＵＴの書き換えを行う。（表９）を参照すると、登録ベクトルb4に対する部分関数Ｇの入力ベクトルは、(h1, h2, h3 x1)=(0111)である。これに対応する出力ベクトルを(000)に変更し、出力側のｐｑ素子のＬＵＴを（表１２）に示したように書き換える。【０１７０】
【表１２】
0004742281.tif 000024
【０１７１】
次に、入力側のｐｑ素子について考える。この場合、更新前の部分関数Ｇの真理値表（表１１）を参照すると、前段のＬＵＴの出力ベクトル(h1, h2, h3)が登録ベクトルb4に対する出力ベクトル(011)と同じで、非零の出力を持つ登録ベクトルは存在しない。従って、入力側のｐｑ素子について、登録ベクトルb4に対応する部分関数Ｈの入力ベクトル(x5 x4 x3 x2)=(0111)に対する出力ベクトル(h1, h2, h3)= (100)を(000)に変更する。従って、入力側のｐｑ素子のＬＵＴは（表１３）のように更新される。これにより、登録ベクトルb4の削除に伴う各ｐｑ素子の再構成が完了する。【０１７２】
【表１３】
0004742281.tif 000025
（例終り）
【実施例２】
【０１７３】
図１０は、本発明の実施例２に係る論理回路修正装置２０の構成を示す図である。図１０において、主論理回路３０は、論理修正の対象となる論理回路であり、専用のＬＳＩ（ＡＳＩＣ）として構成されたメモリ、ＣＰＵ等である。主論理回路３０の入力変数をX=(x1 x2 … xn)(∈Bn, B={0,1})、出力変数をQ=Q(X)=(q1 q2 … qm)（∈Bm）とし、論理回路修正装置２０により修正された出力変数をQ'=(q1' q2' … qm')（∈Bm）とする。主論理回路３０は、入力変数Xに対して目的論理関数Q(X)を演算する。【０１７４】
論理回路修正装置２０は、入力変数Xとして入力される各入力ベクトルbのうち特定の対象入力ベクトルbiに対する主論理回路３０の出力ベクトルQ(bi)を、修正出力ベクトルQ'(bi)に変更する。論理回路修正装置２０は、アドレス生成回路２１、補助メモリ２２、修正回路２３、及び再構成回路１を備えている。尚、再構成回路１は、実施例１において説明した多段論理回路の再構成回路１と同様のものである。【０１７５】
補助メモリ２２は、各対象入力ベクトルbiに対応して、各出力ベクトルQ(bi)を修正出力ベクトルQ'(bi)に修正するための修正用ベクトルPi=(pi1 pi2 … pim)が所定のアドレスAiに登録されるメモリである。補助メモリ２２は、修正用ベクトルPiが登録されたアドレスAiが入力された場合には、修正用ベクトルPiを出力し、それ以外の場合は、無効値として０を出力する。【０１７６】
修正回路２３は、補助メモリ２２が出力する修正用ベクトルPiを出力した場合、当該修正用ベクトルPi及び主論理回路３０が出力する出力ベクトルQ(bi)に基づいて、修正出力ベクトルQi'を出力する。ここで、本実施例２においては、修正回路２３は、主論理回路３０の各出力線に対応して設けられたＥＸＯＲゲート２４により構成されている。各ＥＸＯＲゲート２４は、出力ベクトルQの各成分q1 q2 … qmと、修正用ベクトルPiの各成分pi1 pi2 … pimとの排他論理和により、修正出力ベクトルQi'=(qi1' qi2' … qim')の演算を行う。【０１７７】
【数１２】
0004742281.tif 000026
【０１７８】
従って、修正用ベクトルPiの値は、上記式（１２）により目的とする修正出力ベクトルQi'が得られるような値に設定される。【０１７９】
アドレス生成回路２１は、入力変数Xとして入力される各入力ベクトルbに対して補助メモリ２２のアドレスを出力する回路である。ここで、アドレス生成回路２１は、各対象入力ベクトルbiに対しては修正用ベクトルPiが登録されたアドレスAiを出力し、それ以外の入力ベクトルbに対しては無効値（０）を出力するようなアドレス生成関数F(X)の演算を行う。【０１８０】
また、アドレス生成回路２１は、上述したようなｐｑ素子を多段に結合して構成された多段論理回路によって構成されている。【０１８１】
再構成回路１は、アドレス生成回路２１が演算するアドレス生成関数F(X)の修正に伴い、アドレス生成回路２１の各ｐｑ素子のＬＵＴの再構成を行う。尚、再構成の方法に関しては、実施例１において述べた通りである。【０１８２】
以上のように構成された本実施例２の論理回路修正装置２０について、以下その動作を説明する。【０１８３】
まず、入力変数Xとして、対象入力ベクトルbi以外の入力ベクトルbが入力された場合、アドレス生成回路２１は出力ベクトルaとして０（無効値）を出力する。従って、補助メモリ２２は、修正用ベクトルPとして０を出力する。各ＥＸＯＲゲート２４は、主論理回路３０の出力値qjと０との排他論理和、すなわち出力値qjを出力する。従って、この場合は出力ベクトルQは修正されず、そのまま出力されることになる。【０１８４】
一方、入力変数Xとして、対象入力ベクトルbiが入力された場合、アドレス生成回路２１は出力ベクトルaとして、修正用ベクトルPiが格納された補助メモリ２２のアドレス値Aiを出力する。従って、補助メモリ２２は、修正用ベクトルPとして修正用ベクトルPiを出力する。各ＥＸＯＲゲート２４は、主論理回路３０の出力値qjと修正用ベクトルの成分pijとの排他論理和qij'を出力する。これにより、出力ベクトルの修正が行われる。【０１８５】
本実施例においては、アドレス生成回路２１としてｐｑ素子を多段に結合して構成された多段論理回路を使用したことで、論理回路修正装置２０の実装面積を小さくすることが可能となる。また、論理変更が追加して行われた場合にも、再構成回路１を用いて容易にアドレス生成回路２１の再構成を行うことができる。
【実施例３】
【０１８６】
図１１は、本発明の実施例３に係る論理回路修正装置２０の構成を示す図である。図１１において、再構成回路１、アドレス生成回路２１、補助メモリ２２、及び主論理回路３０は、図１０と同様のものである。本実施例においては、補助メモリ２２には、各対象入力ベクトルbiに対して修正出力ベクトルQi'がそのまま格納されている。また、補助メモリ２２及び主論理回路３０の出力段には、修正手段としてトライ・ステート・バッファ（図示せず）が設けられている。【０１８７】
アドレス生成回路２１は、入力バス３１から入力される入力変数Xに対して、当該入力変数Xの値がいずれの対象入力ベクトルbiとも等しくない場合には、無効値を出力する。主論理回路３０の出力段のトライ・ステート・バッファは、アドレス生成回路２１の出力値が無効値でない場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となる。また、補助メモリ２２の出力段のトライ・ステート・バッファは、アドレス生成回路２１の出力値が無効値の場合にはハイ・インピーダンス、それ以外の場合にはロー・インピーダンス状態となる。【０１８８】
これにより、入力変数Xの値が対象入力ベクトルbi以外の場合には、出力バス３２には、主論理回路３０の出力ベクトルが出力され、入力変数Xの値が対象入力ベクトルbiの場合には、出力バス３２には、補助メモリ２２の出力ベクトルが出力される。
【実施例４】
【０１８９】
図１２は、本発明の実施例４に係る再構成可能な多段論理回路の構成を表す図である。図１２において、図５と同様な構成部分については、同符号を付す。【０１９０】
本実施例の再構成可能な多段論理回路においては、再構成回路１’に新たに、インデックス・テーブル８と参照テーブル９とが追加されている。【０１９１】
多段論理回路１０は、実施例１において説明したとおり、入力変数をXとする目的論理関数F(X)の演算を行う論理回路である。多段論理回路１０は、複数のｐｑ素子１３が多段に接続された論理回路である。この、多段論理回路１０の具体的な構造としては、複数のｐｑ素子１３がカスケード状に接続されたＬＵＴカスケード論理回路（図６，図１５参照）や、複数のｐｑ素子１３が樹形状に接続されたＬＵＴツリー論理回路（図２〜４参照）を用いることができる。【０１９２】
再構成回路１は、この多段論理回路１０の論理変更に伴って、多段論理回路１０の再構成を行う回路である。再構成回路１は、素子選択手段２，素子選択手段３，対応検査手段４，削除修正手段５，対応付手段６，追加修正手段７，インデックス・テーブル８，及び参照テーブル９を備えている。素子選択手段２，素子選択手段３，対応検査手段４，削除修正手段５，追加修正手段７，及び対応付手段６については、実施例１で既に説明をした通りであるので、説明は省略する。【０１９３】
尚、ｐｑ素子１３は、必ずしもメモリを用いて構成する必要はなく、メモリと同様の機能を有する回路であればどのような回路を用いてもよい。【０１９４】
例えば、図１３は、Xilinx社のＦＰＧＡで用いられている４入力ＬＵＴである。この４入力ＬＵＴは、１６個の同期型のＤフリップ・フロップ４１＿０〜４１＿１５と、１つの１６入力１出力のマルチプレクサ４２を備えている。【０１９５】
この４入力ＬＵＴでは、モードを切り替えることで、シフトレジスタとして使用でき、書き換えが可能である。【０１９６】
図１３（ａ）はＳＲＬ１６モードであり、このモードではクロック線４３から各ＤＦＦ４１＿０〜４１＿１５にクロックが入力される。従って、ＤＦＦ４１＿０〜４１＿１５はシフトレジスタとして機能する。この状態で登録値入力線４４から登録データをシリアルに入力することにより、各ＤＦＦ４１＿０〜４１＿１５に登録データが記憶される。【０１９７】
一方、図１３（ｂ）は４入力ＬＵＴモードであり、このモードではクロック線４３にクロックの入力はなく、この回路はＬＵＴとして機能する。データ入力線４５からＭＵＸ４２に４ビットのデータが入力されると、ＭＵＸ４２は、その入力データに応じてＤＦＦ４１＿０〜４１＿１５の何れか一つを選択し、選択したＤＦＦに記憶されたデータを出力する。従って、この回路は４入力１出力のＬＵＴとして機能する。【０１９８】
図１４に、４入力ＬＵＴを３個用いた１２入力１出力の回路を示す。図１４に示すように、ＦＰＧＡ内部のマルチプレクサと組み合わせることで、複数のLUT の出力の論理積を計算できる。尚、この回路は１出力なので、複数ビットの出力を得たい場合には、図１４の回路を必要なビット数だけ並列に並べればよい。【０１９９】
ｐｑ素子１３としては、図１３に示したようなＬＵＴを使用することも可能である。【０２００】
参照テーブル９は、各ｐｑ素子１３毎に割り当て済みのレイル・ベクトル（rail vector）を保持するテーブルである。【０２０１】
ここで、「レイル（rail）」とは、複数のｐｑ素子が多段に接続された多段論理回路において、前段のpq素子の出力線のうち、後段のｐｑ素子の入力に接続された接続線をいう。【０２０２】
図１５は、ＬＵＴカスケード論理回路を一般的に表したものである。図１５のｐｑ素子E(1)の出力線のうちｐｑ素子E(2)の入力に接続されたものがレイルである。また、ｐｑ素子E(2)の出力線のうちｐｑ素子E(3)の入力に接続されたものがレイルである。以下同様である。図２〜４のＬＵＴツリー論理回路についても、同様にレイルが定義される。【０２０３】
また、「レイル・ベクトル」とは、あるｐｑ素子の出力側のレイルに出力される出力変数のベクトルをいう。【０２０４】
参照テーブル９の例を図１６に示す。参照テーブル９は、多段論理回路１０の各ｐｑ素子毎につずつ設けられる。１つのｐｑ素子に対する参照テーブル９は、そのｐｑ素子の各レイル・ベクトルとそれに対応する参照ベクトル数とのテーブルとで構成される。尚、「参照ベクトル数」とは、そのレイル・ベクトルを参照する登録ベクトルの個数である。【０２０５】
インデックス・テーブル８は、ベクトルが登録済みであるか否かを記憶するテーブルである。インデックス・テーブル８は、１つだけ設けられる。図１７に、インデックス・テーブルの例を示す。インデックス・テーブル９は、登録可能な各ベクトルに割り当てられたインデックスと、そのインデックスに対応する登録ベクトルが登録済み（使用されている）か否かを示す登録済フラグとで構成される。【０２０６】
以上のように構成された本実施例に係る再構成可能な多段論理回路について、以下その登録ベクトルの追加・削除の動作について説明する。【０２０７】
尚、ここでは説明を分かりやすくするため、多段論理回路１０として、図６に示したようなＬＵＴカスケード論理回路が用いられていることとする。【０２０８】
（１）登録ベクトルの追加
本実施例の再構成可能な多段論理回路では、登録ベクトルを新たに追加する場合は、インデックス・テーブル８及び参照テーブル９を使用し、処理時間の短縮が図られる。【０２０９】
図１８は、実施例４に係る再構成可能な多段論理回路の登録ベクトルの追加処理のフローチャートである。【０２１０】
まず、ステップＳ３１において、登録する入力ベクトルｂが、再構成回路１’に入力される。【０２１１】
次に、ステップＳ３２において、追加修正手段７は、インデックス・テーブル８を参照し、入力ベクトルｂは多段論理回路１０に登録済みか否かを検査する。ここで、インデックス・テーブル８の入力ベクトルｂに対する登録済フラグが１の場合には終了する。【０２１２】
次に、ステップＳ３３において、素子選択手段３は、選択素子の番号を表すインデックスｉを１に設定する。【０２１３】
次に、ステップＳ３４において、対応付手段６は、多段論理回路１０に入力ベクトルｂを入力し、ｐｑ素子Ｅ（ｉ）の出力ベクトルｕｉ（ｂ）を読み出す。【０２１４】
次に、ステップＳ３５において、対応付手段６は、出力ベクトルｕｉ（ｂ）が０か否かを判定する。０の場合には、ステップＳ３８に移行し、０以外の場合には次のステップＳ３６に移行する。【０２１５】
次に、ステップＳ３６において、対応付手段６は、ｐｑ素子Ｅ（ｉ）に対応する参照テーブル９を検索し、未参照のレイル・ベクトルａを１つ索出する。そして、ステップＳ３６において、追加修正手段７は、ｐｑ素子Ｅ（ｉ）の出力ベクトルｕｉ（ｂ）がレイル・ベクトルａとなるようにｐｑ素子Ｅ（ｉ）のメモリ内容の書き換えを行う。【０２１６】
ステップＳ３８において、対応付手段６は、ｐｑ素子Ｅ（ｉ）に対応する参照テーブルの登録ベクトルｕｉ（ｂ）の参照ベクトル数を１だけインクリメントする。【０２１７】
次に、ステップＳ３９において、素子選択手段３は、選択素子の番号を表すインデックスｉを１だけインクリメントする。【０２１８】
次に、ステップＳ４０において、素子選択手段３は、ｉ＝ｓか否かを判定する。ｉ＜ｓならばステップＳ３４に戻り、ｉ＝ｓならば次のステップＳ４１に進む。【０２１９】
ステップＳ４１において、追加修正手段７は、ｐｑ素子Ｅ（ｓ）の出力ベクトルｕｓ（ｂ）をＦ（ｂ）とばるように、ｐｑ素子Ｅ（ｓ）のメモリ内容の書き換えを行う。【０２２０】
最後に、ステップＳ４２において、追加修正手段７は、インデックス・テーブル８の登録ベクトルｂに対する登録済フラグを１に設定して、登録ベクトル追加処理を終了する。【０２２１】
（２）登録ベクトルの削除
図１９は、実施例４に係る再構成可能な多段論理回路の登録ベクトルの削除処理のフローチャートである。【０２２２】
まず、ステップＳ５１において、削除する入力ベクトルｂが、再構成回路１’に入力される。【０２２３】
次に、ステップＳ５２において、削除修正手段５は、インデックス・テーブル８を参照し、入力ベクトルｂは多段論理回路１０に登録済みであるか否かを検査する。インデックス・テーブル８の入力ベクトルｂに対する登録済フラグが０の場合は、登録ベクトルの削除処理を終了する。【０２２４】
次に、ステップＳ５３において、素子選択手段２は、選択素子の番号を表すインデックスｉをｓに設定する。【０２２５】
次に、ステップＳ５４において、対応検査手段４は、多段論理回路１０に入力ベクトルｂを入力し、ｐｑ素子Ｅ（ｉ）の出力ベクトルｕｉ（ｂ）を読み出す。【０２２６】
次に、ステップＳ５５において、対応検査手段４は、ｐｑ素子Ｅ（ｉ）に対応する参照テーブルの登録ベクトルｕｉ（ｂ）の参照ベクトル数を１だけデクリメントする。但し、このとき登録ベクトルｕｉ（ｂ）の参照ベクトル数が０の場合には、登録ベクトルｕｉ（ｂ）の参照ベクトル数は０のままとする。【０２２７】
次に、ステップＳ５６において、削除修正手段５は、登録ベクトルｕｉ（ｂ）の参照ベクトル数が０か否かを判定する。登録ベクトルｕｉ（ｂ）の参照ベクトル数が０でないならばステップＳ５８に戻り、０ならば次のステップＳ５７に進む。【０２２８】
ステップＳ５７において、削除修正手段５は、ｐｑ素子Ｅ（ｉ）の出力ベクトルｕｉ（ｂ）が０となるように、ｐｑ素子Ｅ（ｉ）のメモリ内容の書き換えを行う。【０２２９】
ステップＳ５８において、素子選択手段２は、選択素子の番号を表すインデックスｉを１だけデクリメントする。【０２３０】
次に、ステップＳ５９において、素子選択手段２は、ｉ＝０か否かを判定する。ｉ＞０ならばステップＳ５４に戻り、ｉ＝０ならば次のステップＳ６０に進む。【０２３１】
ステップＳ６０において、削除修正手段５は、インデックス・テーブル８の登録ベクトルｂに対する登録済フラグを０に設定して、登録ベクトル削除処理を終了する。【０２３２】
以上の処理によって、多段論理回路１０に登録ベクトルを１つ追加するのに必要なステップ数は、以下の式で見積もることができる。【０２３３】
【数１３】
0004742281.tif 000027
【０２３４】
ここで、OP.CasはＬＵＴカスケードにアクセスするために必要なステップ数、Acc.Memは参照テーブルにアクセスするために必要なステップ数、sはセル数、kは登録ベクトル数を示す。第１項は、上記登録ベクトルの追加処理のうちステップＳ３１〜Ｓ３４の処理を行うのに必要なステップ数の見積りを示し、第２項はそれ以外の処理を行うのに必要なステップ数の見積りを示す。【０２３５】
同様に、多段論理回路１０から登録ベクトルを１つ削除するのに必要なステップ数は以下の式で見積もることができる。【０２３６】
【数１４】
0004742281.tif 000028
【０２３７】
第１項は上記登録ベクトルの削除処理のうちステップＳ５１〜Ｓ５４の処理を行うのに必要なステップ数の見積りを示し、第２項はそれ以外の処理を行うのに必要なステップ数の見積りを示す。【０２３８】
式（１３），（１４）より、多段論理回路１０がＬＵＴカスケード論理回路の場合、登録ベクトルの追加に要するステップ数はｓとｋに、削除に要するステップ数はｓにほぼ比例する事が分かる。
【図１】
0004742281.tif 000029
【図２】
0004742281.tif 000030
【図３】
0004742281.tif 000031
【図４】
0004742281.tif 000032
【図５】
0004742281.tif 000033
【図６】
0004742281.tif 000034
【図７】
0004742281.tif 000035
【図８】
0004742281.tif 000036
【図９】
0004742281.tif 000037
【図１０】
0004742281.tif 000038
【図１１】
0004742281.tif 000039
【図１２】
0004742281.tif 000040
【図１３】
0004742281.tif 000041
【図１４】
0004742281.tif 000042
【図１５】
0004742281.tif 000043
【図１６】
0004742281.tif 000044
【図１７】
0004742281.tif 000045
【図１８】
0004742281.tif 000046
【図１９】
0004742281.tif 000047
【図２０】
0004742281.tif 000048