(57)【要約】【課題】異なる種類の複数の演算を行う演算回路を構成する場合に、演算回路全体として小規模化および演算時間の短縮を図ることが可能な回路構成方法を提供する。【解決手段】異なる種類の複数の演算を行う演算回路を構成する場合に、上記複数の演算のそれぞれについて、当該演算の種類に基づいて、当該演算で用いるデータ表現形式（例えば、基底表現）を決定する（ＳＴ２）。当該決定したデータ表現形式を用いて上記複数の演算の各々を行う複数の演算回路ブロックを有する演算回路を構成する（ＳＴ３）。【選択図】　図２
2004133617.tif 000002
【特許請求の範囲】
【請求項１】
異なる種類の複数の演算を行う演算回路を構成する回路構成方法であって、
前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いるデータ表現形式を決定する第１の工程と、
前記第１の工程で決定した前記データ表現形式を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の工程と
を有する回路構成方法。
【請求項２】
前記第１の工程において、前記複数の演算のそれぞれについて、当該演算を行う前記演算回路ブロックの小規模化および演算時間の短縮の少なくとも一方を図る観点から、前記データ表現形式を決定する
請求項１に記載の回路構成方法。
【請求項３】
前記第１の工程において、第１の前記演算で第１の前記データ表現形式を用いることを決定し、第２の前記演算で第２の前記データ表現形式を用いることを決定し、
前記第２の工程において、前記第２の演算が前記第１の演算の結果を用いる場合に、前記第１の演算を行う第１の前記演算回路ブロックの演算結果を、前記第１のデータ表現形式から第２のデータ表現形式に変換して前記第２の演算回路ブロックに出力する変換回路ブロックを有する前記演算回路を構成する
請求項１に記載の回路構成方法。
【請求項４】
前記複数の演算が、所定の線形空間上で線形写像を行う演算である場合に、
前記第１の工程において、前記データ表現形式として、前記線形空間上の基底を決定する
請求項１に記載の回路構成方法。
【請求項５】
前記線形空間は、有限体の有限次拡大体である
請求項４に記載の回路構成方法。
【請求項６】
前記有限次拡大体は、所定の有限体上のｍ（ｍは整数）次拡大体であり、次数ｍが、複数通りに因数分解できる場合に、
前記第１の工程において、
前記複数通りの因数分解のそれぞれについて、拡大タワーを生成し、
それぞれの前記拡大タワーについて、当該拡大タワーを構成する各拡大についての基底を要素とする第１の集合を生成し、
それぞれの前記拡大タワーについて、前記第１の集合の複数の要素を乗じて得られた基底を要素とする第２の集合を生成し、
複数の前記第２の集合のなかから、前記線形空間上の基底を決定する
請求項５に記載の回路構成方法。
【請求項７】
前記線形空間が、ｐを素数、ｑ＝ｐｍ　とした場合の有限次拡大体Ｆｑ　上の下記（１−１）で示されるｍ次拡大体であり、
【数１】
2004133617.tif 000052
次数ｍが、下記（１−２）に示すように、ｌ通りに因数分解可能であり、
【数２】
2004133617.tif 000053
上記（１−２）内の符号は下記（１−３）の要件を満たし、下記（１−３）のＮは自然数であり、
【数３】
2004133617.tif 000054
前記有限次拡大体Ｆｑ　から、それぞれｋｉ　回の拡大を行うことにより、下記（１−４）に示すｌ個の前記拡大タワーを生成し、
【数４】
2004133617.tif 000055
下記（１−５）で示される次数の拡大についての基底を要素とする下記（１−６）で示すｌ個の前記第１の集合を生成し、
各列を構成する基底は、下記（１−７）のように定義され、
【数５】
2004133617.tif 000056
【数６】
2004133617.tif 000057
【数７】
2004133617.tif 000058
上記（１−７）内のｄは、下記（１−８）のように定義され、
下記（１−８）において、「×」は、直積を示し、
下記（１−９）で示されるように、下記（１−８）のＺ／（ｎ）は、整数全体の集合Ｚのｎによる剰余群を示し、ｎは、自然数Ｎの要素であり、
【数８】
2004133617.tif 000059
【数９】
2004133617.tif 000060
前記演算回路が行う複数の演算のそれぞれについて、（１−１）で示されるｍ次拡大体の上記（１−６）から得られる下記（１−１０）で示されるｌ個の前記第２の集合のなかから、当該演算に用いるデータ表現形式である基底を選択（決定）し、
下記（１−１０）が示すｌ個の前記第２の集合の各々は、（１−６）で示される前記第１の集合の複数の要素を乗じて得られる基底を要素とし、
【数１０】
2004133617.tif 000061
上記（１−１０）における各ｄは、下記（１−１１）によって定義され、次数ｍは下記（１−１２）の関係を満たす
【数１１】
2004133617.tif 000062
【数１２】
2004133617.tif 000063
請求項６に記載の回路構成方法。
【請求項８】
それぞれの前記拡大タワーについて、各拡大の原始根を要素とする前記第１の集合を規定する
請求項６に記載の回路構成方法。
【請求項９】
異なる種類の複数の演算を行う演算回路を構成する回路構成装置であって、
前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いるデータ表現形式を決定する第１の手段と、
前記第１の手段が決定した前記データ表現形式を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の手段と
を有する回路構成装置。
【請求項１０】
前記第１の手段は、第１の前記演算で第１の前記データ表現形式を用いることを決定し、第２の前記演算で第２の前記データ表現形式を用いることを決定し、
前記第２の手段は、前記第２の演算が前記第１の演算の結果を用いる場合に、前記第１の演算を行う第１の前記演算回路ブロックの演算結果を、前記第１のデータ表現形式から第２のデータ表現形式に変換して前記第２の演算回路ブロックに出力する変換回路ブロックを有する前記演算回路を構成する
請求項９に記載の回路構成装置。
【請求項１１】
コンピュータによって実行され、異なる種類の複数の演算を行う演算回路を構成する手順を記述したプログラムであって、
前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いるデータ表現形式を決定する第１の手順と、
前記第１の手順で決定した前記データ表現形式を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の手順と
を有するプログラム。
【請求項１２】
前記第１の手順は、第１の前記演算で第１の前記データ表現形式を用いることを決定し、第２の前記演算で第２の前記データ表現形式を用いることを決定し、
前記第２の手順は、前記第２の演算が前記第１の演算の結果を用いる場合に、前記第１の演算を行う第１の前記演算回路ブロックの演算結果を、前記第１のデータ表現形式から第２のデータ表現形式に変換して前記第２の演算回路ブロックに出力する変換回路ブロックを有する前記演算回路を構成する
請求項１１に記載のプログラム。
【請求項１３】
異なる種類の複数の演算を行う演算回路であって、
前記演算の種類に応じて規定された相互に異なるデータ表現形式を用いて構成された複数の演算回路ブロック
を有する演算回路。
【請求項１４】
第１の前記データ表現形式を用いて構成された第１の前記演算回路ブロックの演算結果を、第２の演算回路ブロックが用いる第２の前記データ表現形式に変換して前記第２の演算回路ブロックに出力する変換回路ブロック
をさらに有する請求項１３記載の演算回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、例えば、誤り訂正符号や復号などを行う場合に用いられる演算回路を構成するための回路構成方法、その装置およびそのプログラムとその演算回路に関する。
【０００２】
【従来の技術】
例えば、ハミング符号などの誤り訂正符号や復号では、有限体演算が行われる。
有限体（ｆｉｎｉｔｅ　ｆｉｅｌｄ）とは、四則演算が定義されている有限集合を指し、有限体演算とは、有限体上で定義された、これらの演算を指す。
有限体演算を行うには、先ず、いくつかのデータ表現形式を決定し、有限体を表現する必要がある。
有限体の要素（元）の個数は、ｐを素数とし、ｍを正整数としてｐｍ　となる。この正整数ｍは拡大次数と呼ばれる。
有限体の要素を記述するには、素数ｐ、拡大次数ｍ、およびｍ次の既約多項式Ｆ（ｘ）によって定義される基底表現をデータ表現形式として用いる。
従来の演算回路では、予め決められた一つの固定のデータ表現形式を用いている。
例えば、図１１に示すように、演算回路２０１では、演算ＯＰ１を行う演算回路ブロック２０２と、演算ＯＰ２を行う演算回路ブロック２０３との双方において、同じデータ表現形式Ａが用いられている。
また、例えば、図１２に示すように、演算回路３０１では、演算ＯＰ１を行う演算回路ブロック３０２と、演算ＯＰ２を行う演算回路ブロック３０３との双方において、同じデータ表現形式Ｂが用いられている。
ここで、演算回路ブロックの小規模化および演算時間の短縮を図る観点から、演算ＯＰ１ではデータ表現形式Ａを用い、演算ＯＰ２ではデータ表現形式Ｂを用いることが望ましい場合がある。
【０００３】
【発明が解決しようとする課題】
しかしながら、上述した演算回路２０１，３０１のように、予め決められた一つの固定のデータ表現形式を用いると、演算回路２０１では、演算回路ブロック２０２を効率的に構成できるが、演算回路ブロック２０３を効率的に構成できないという問題がある。
また、演算回路３０１では、演算回路ブロック３０３を効率的に構成できるが、演算回路ブロック３０２を効率的に構成できないという問題がある。
【０００４】
本発明は上述した従来技術の問題点に鑑みてなされ、異なる種類の複数の演算を行う演算回路を構成する場合に、各演算が行う演算回路ブロックを当該演算の種類に適合したデータ表現形式を用いて構成することを可能にする回路構成方法、その装置およびそのプログラムと、その演算回路を提供することを目的とする。
【０００５】
【課題を解決するための手段】
上述した従来技術の問題点を解決し、上述した目的を達成するために、第１の発明の回路構成方法は、異なる種類の複数の演算を行う演算回路を構成する回路構成方法であって、前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いるデータ表現形式を決定する第１の工程と、前記第１の工程で決定した前記データ表現形式を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の工程とを有する。
【０００６】
第１の発明の回路構成方法では、先ず、第１の工程において、複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いるデータ表現形式を決定する。
そして、第２の工程において、前記第１の工程で決定した前記データ表現形式を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する演算回路を構成する。
【０００７】
第１の発明の回路構成方法は、好ましくは、前記第１の工程において、前記複数の演算のそれぞれについて、当該演算を行う前記演算回路ブロックの小規模化および演算時間の短縮の少なくとも一方を図る観点から、前記データ表現形式を決定する。
また、第１の発明の回路構成方法は、好ましくは、前記第１の工程において、第１の前記演算で第１の前記データ表現形式を用いることを決定し、第２の前記演算で第２の前記データ表現形式を用いることを決定し、前記第２の工程において、前記第２の演算が前記第１の演算の結果を用いる場合に、前記第１の演算を行う第１の前記演算回路ブロックの演算結果を、前記第１のデータ表現形式から第２のデータ表現形式に変換して前記第２の演算回路ブロックに出力する変換回路ブロックを有する前記演算回路を構成する。
【０００８】
第２の発明の回路構成装置は、異なる種類の複数の演算を行う演算回路を構成する回路構成装置であって、前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いるデータ表現形式を決定する第１の手段と、前記第１の手段が決定した前記データ表現形式を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の手段とを有する。
【０００９】
第２の発明の回路構成装置では、第１の手段が、複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いるデータ表現形式を決定する。
次に、第２の手段が、前記第１の手段が決定した前記データ表現形式を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する。
【００１０】
第３の発明のプログラムは、コンピュータによって実行され、異なる種類の複数の演算を行う演算回路を構成する手順を記述したプログラムであって、前記複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算で用いるデータ表現形式を決定する第１の手順と、前記第１の手順で決定した前記データ表現形式を用いて前記複数の演算の各々を行う複数の演算回路ブロックを有する前記演算回路を構成する第２の手順とを有する。
【００１１】
第４の発明の演算回路は、異なる種類の複数の演算を行う演算回路であって、前記演算の種類に応じて規定された相互に異なるデータ表現形式を用いて構成された複数の演算回路ブロックを有する。
【００１２】
【発明の実施の形態】
以下、本発明の実施形態の演算回路の回路構成方法について説明する。
本実施形態の回路構成方法は、異なる種類の複数の演算を行う演算回路を構成する回路構成方法である。
当該回路構成方法では、複数の演算のそれぞれについて、その種類に基づいて、当該演算を行う演算回路ブロックの小規模化および演算時間の短縮の少なくとも一方を図る観点から、当該演算で用いるデータ表現形式を決定する。
そして、当該回路構成方法では、上記決定した前記データ表現形式を用いて上記複数の演算の各々を行う複数の演算回路ブロックを有する演算回路の構成データを生成する。
ここで、本実施形態の回路構成方法では、上記複数の演算が所定の線形空間上で線形写像を行う演算である場合には、上記データ表現形式として線形空間上の基底を決定する。
当該線形空間は、例えば、有限体の有限次拡大体である。
【００１３】
第１実施形態
図１は、本実施形態の回路構成方法を実行するコンピュータ２９を説明するための図である。
図１に示すように、コンピュータ２９は、例えば、操作部３１、ディスプレイ３２、メモリ３３およびＣＰＵ３４を有し、これらがバス３０を介して接続されている。
操作部３１は、キーボードやマウスなどの操作手段であり、ＣＰＵ３４にプログラムの実行指示、並びにデータ入力を行うために用いられる。
ディスプレイ３２は、ＣＰＵ３４の処理結果を表示する。
メモリ３３は、ＣＰＵ３４によって実行されるプログラム４１と、プログラム４１の実行に用いられるデータ４２とを記憶する。
【００１４】
ＣＰＵ３４は、プログラム４１を実行して以下に示す処理を行い、プログラム４１の実行過程でデータ４２を用いて、演算回路の回路を構成（設計）する処理を行う。
プログラム４１は、本発明のプログラムに対応し、以下に示す各ステップの内容を示す手順を記述している。
また、ＣＰＵ３４がプログラム４１を実行することで、本発明の回路構成装置が構成され、ＣＰＵ３４が図２に示すステップＳＴ２を実行して本発明の第１の手段を構成し、ＣＰＵ３４が図２に示すステップＳＴ３を実行して本発明の第２の手段を構成する。
ここで、ステップＳＴ２およびＳＴ３が、それぞれ本発明の回路構成方法の第１の工程および第２の工程に対応している。
【００１５】
図２は、ＣＰＵ３４の処理を説明するためのフローチャートである。
図３は、ＣＰＵ３４によって生成された構成データから得られる演算回路１０１を説明するための図である。
【００１６】
ステップＳＴ１：
ＣＰＵ３４は、例えば、ユーザによる操作部３１の操作に応じて、設計対象の演算回路が行う複数の演算の内容を、その内容を示す演算内容データを入力するなどして特定する。
【００１７】
ステップＳＴ２：
ＣＰＵ３４が、ステップＳＴ１で入力した演算内容データを基に、上記演算回路が行う複数の演算のそれぞれについて、当該演算で用いるデータ表現形式を決定する。
このとき、ＣＰＵ３４は、上記複数の演算のそれぞれについて、当該演算を行う上記演算回路ブロックの小規模化および演算時間の短縮の少なくとも一方を図る観点から、上記データ表現形式を決定する。
当該データ表現形式は、例えば、線形空間である有限体の有限次拡大体上の基底（基底表現）である。
【００１８】
ステップＳＴ３：
ＣＰＵ３４が、ステップＳＴ２で決定したデータ表現形式を用いて、上記複数の演算の各々を行う複数の演算回路ブロックの構成データ（回路データ）を生成する。
この場合に、ＣＰＵ３４は、上記決定されたデータ表現形式を用いて、各演算回路ブロックを、既知の回路構成手法を基に、回路規模および演算時間の点で効率よく構成する。
当該既知の回路構成手法としては、例えば、Ｃｈｒｉｓｔｏｆ　Ｐａａｒ　著、Ａ　Ｎｅｗ　Ａｒｃｈｉｔｅｃｔｕｒｅ　ｆｏｒ　ａ　Ｐａｒａｌｌｅｌ　Ｆｉｎｉｔｅ　Ｆｉｅｌｄ　Ｍｕｌｔｉｐｌｉｅｒ　ｗｉｔｈ　Ｌｏｗ　Ｃｏｍｐｌｅｘｉｔｙ　Ｂａｓｅｄｏｎ　Ｃｏｍｐｏｓｉｔｅ　Ｆｉｅｌｄｓ　ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　ＣｏｍｐｕｔｅｒＲＳｆ，　Ｖｏｌ．４５，Ｎｏ．７，Ｊｕｌｙ　１９９６　などに開示されているものが用いられる。
ＣＰＵ３４は、例えば、図３に示すように、データ表現形式としてデータ表現形式Ａを用いて演算を行う演算回路ブロック１０２の構成データと、データ表現形式Ｂを用いて演算を行う演算回路ブロック１０３の構成データとを生成する。
【００１９】
ステップＳＴ４：
ＣＰＵ３４が、ステップＳＴ１で入力した演算内容データを基に、ステップＳＴ３で構成した演算回路ブロックのうち、第１の演算回路ブロックおよび第２の演算回路ブロックが異なるデータ表現形式を用いて構成され、第２の演算回路ブロックが第１の演算回路ブロックの演算結果を用いる場合に、第１の演算回路ブロックが用いるデータ表現形式から第２の演算回路ブロックが用いる前記データ表現形式への変換を特定する。
図３に示す例では、ＣＰＵ３４は、データ表現形式Ａからデータ表現形式Ｂへの変換を特定する。
当該変換は、例えば、上述した基底の変換である。
【００２０】
ステップＳＴ５：
ＣＰＵ３４が、ステップＳＴ４で特定した変換を基に、第１の演算回路ブロックの演算結果を入力し、当該演算結果を第１の演算回路ブロックが用いるデータ表現形式から第２の演算回路ブロックが用いる前記データ表現形式に変換して第２の演算回路ブロックに出力する変換回路ブロックの構成データを生成する。
これにより、図３に示す例では、ＣＰＵ３４が、データ表現形式Ａからデータ表現形式Ｂへの変換を行う変換回路ブロック１０４の構成データを生成する。
【００２１】
ステップＳＴ６：
ＣＰＵ３４が、ステップＳＴ３で生成した演算回路ブロックの構成データと、ステップＳＴ４で生成した変換回路ブロックの構成データとを基に、上記複数の演算を行う演算回路ブロックと、上記変換を行う変換回路ブロックとを有する演算回路の構成データ（回路データ）を生成する。
これにより、例えば、図３に示す演算回路１０１の構成データが生成される。
【００２２】
以下、図２に示すステップＳＴ２において、ＣＰＵ３４が行う処理内容について説明する。
上記線形空間が、ｐを素数、ｑ＝ｐｍ　とした場合の有限次拡大体Ｆｑ　上の下記（２−１）で示されるｍ次拡大体である場合を考える。
【００２３】
【数１３】
2004133617.tif 000003
【００２４】
ここで、次数ｍが、下記（２−２）に示すように、ｌ通りに因数分解可能であるとする。
【００２５】
【数１４】
2004133617.tif 000004
【００２６】
上記（２−２）内の符号は下記（２−３）の要件を満たしている。下記（２−３）のＮは自然数である。
【００２７】
【数１５】
2004133617.tif 000005
【００２８】
ＣＰＵ３４が、有限次拡大体Ｆｑ　から、それぞれｋｉ　回の拡大を行うことにより、下記（２−４）に示すｌ個の拡大タワーを構成（生成）する。
当該拡大タワーは、ＣＰＵ３４で生成するのではなく、メモリ３３内にデータ４２として予め保持していてもよい。
【００２９】
【数１６】
2004133617.tif 000006
【００３０】
ＣＰＵ３４が、上記（２−４）内の下記（２−５）で示される次数の拡大についての下記（２−６）で示すようにそれぞれ基底の列からなるｌ個の第１の集合を生成する。当該第１の集合構成する基底は、下記（２−７）のように定義される。
【００３１】
【数１７】
2004133617.tif 000007
【００３２】
【数１８】
2004133617.tif 000008
【００３３】
【数１９】
2004133617.tif 000009
【００３４】
上記（２−７）内のｄは、下記（２−８）のように定義される。
下記（２−８）において、「×」は、直積を示している。
また、下記（２−９）で示されるように、下記（２−８）のＺ／（ｎ）は、整数全体の集合Ｚのｎによる剰余群を示している。ｎは、自然数Ｎの要素である。
【００３５】
【数２０】
2004133617.tif 000010
【００３６】
【数２１】
2004133617.tif 000011
【００３７】
ＣＰＵ３４は、図２に示すステップＳＴ１で入力した演算内容データを基に、演算回路が行う複数の演算のそれぞれについて、（２−１）で示されるｍ次拡大体の上記（２−６）から得られる下記（２−１０）で示されるｌ個の第２の集合のなかから、当該演算に用いるデータ表現形式である基底（第２の集合）を選択（決定）する。
下記（２−１０）が示すｌ個の第２の集合の各々は、（２−６）で示される基底の各集合の要素を乗じて得られる基底を要素としている。
【００３８】
【数２２】
2004133617.tif 000012
【００３９】
上記（２−１０）における各ｄは、下記（２−１１）によって定義され、次数ｍは下記（２−１２）の関係を満たす。
【００４０】
【数２３】
2004133617.tif 000013
【００４１】
【数２４】
2004133617.tif 000014
【００４２】
以下、図２に示すステップＳＴ４において、ＣＰＵ３４が行う処理内容について説明する。
ここでは、ステップＳＴ２において、ｍ次元線形空間Ｖｍ　において、第１の演算回路ブロックのデータ表現形式として下記（３−１）で示される基底Ａが選択され、第２の演算回路ブロックのデータ表現形式として下記（３−２）で示される基底Ｂが選択された場合を考える。
【００４３】
【数２５】
2004133617.tif 000015
【００４４】
【数２６】
2004133617.tif 000016
【００４５】
ここで、上記基底Ａから上記基底Ｂへのデータが変換される過程で、上記ｍ次元線形空間Ｖｍ　の任意の元ａが、基底Ａ，Ｂをそれぞれ用いて、下記（３−３）のように表現される場合を考える。
【００４６】
【数２７】
2004133617.tif 000017
【００４７】
この場合に、上記（３−３）の各式を下記（３−４），（３−５）で示される列ベクトルで表現する。
【００４８】
【数２８】
2004133617.tif 000018
【００４９】
【数２９】
2004133617.tif 000019
【００５０】
そして、ＣＰＵ３４が、上記（３−４），（３−５）で示される列ベクトル間での変換を規定する下記（３−６）で示される行列を特定する。
【００５１】
【数３０】
2004133617.tif 000020
【００５２】
上記（３−６）で示される行列は、下記（３−７）で示される入力値に対して、下記（３−８）で示される出力値を得るものである。
【００５３】
【数３１】
2004133617.tif 000021
【００５４】
【数３２】
2004133617.tif 000022
【００５５】
ＣＰＵ３５は、上記ステップＳＴ４において、変換として、上記（３−６）〜（３−８）によって示される行列演算を特定する。
【００５６】
また、ＣＰＵ３４は、図２に示すステップＳＴ５において、上記（３−６）〜（３−８）によって示される行列演算を行う、高々ｍ（ｍ−１）個の加算器と、ｍ２　個の定数倍乗算器からなる上記変換回路ブロックの構成データを生成する。
【００５７】
以上説明したように、本実施形態によれば、図２に示すステップＳＴ２，ＳＴ３で説明したように、異なる種類の複数の演算のそれぞれについて、当該演算の前記種類に基づいて、当該演算を行う演算回路ブロックの小規模化および演算時間の短縮の少なくとも一方を図る観点から、当該演算で用いるデータ表現形式を決定する。
そのため、演算回路１０１を構成する各演算回路ブロックについて、それぞれ小規模化および演算時間の観点から適したデータ表現形式を用いることができ、演算回路１０１全体の素子数を削減できると共に、演算内容に適したパラメータを選択でき、回路規模の縮小、並びに演算時間の短縮を図ることができる。
また、本実施形態１によれば、図２に示すステップＳＴ４，ＳＴ５で説明したように、演算回路１０１内に変換回路ブロックを設けることで、演算回路１０１内で複数のデータ表現形式を用いた場合でも、正確な演算結果が得られる。
【００５８】
第２実施形態
当該実施形態は、上述した第１実施形態の回路構成方法における図２に示すステップＳＴ２の処理を具体的にした一形態である。
ＣＰＵ３４が、第１実施形態で説明した上記（２−５）で示される次数の拡大についての下記（４−１）で示す原始根の列からなるｌ個の第１の集合を生成する。第１の集合を構成する原始根γは、下記（４−２）のように定義される。
【００５９】
【数３３】
2004133617.tif 000023
【００６０】
【数３４】
2004133617.tif 000024
【００６１】
ＣＰＵ３４は、図２に示されるステップＳＴ１で入力した演算内容データを基に、演算回路が行う複数の演算のそれぞれについて、上記（２−１）で示されるｍ次拡大体の上記（４−１）から得られる下記（４−３）に示すｌ個の第２の集合のなかから、当該演算に用いるデータ表現形式である基底の集合を選択（決定）する。
下記（４−３）が示すｌ個の第２の集合は、上記（４−１）で示される基底の各集合の要素を乗じて得られる基底を要素としている。
【００６２】
【数３５】
2004133617.tif 000025
【００６３】
上記（４−３）内のｐは、下記（４−４）のように定義される。
下記（４−４）において、「×」は、直積を示している。
また、次数ｍが、下記（４−５）で示される条件を満たす。
【００６４】
【数３６】
2004133617.tif 000026
【００６５】
【数３７】
2004133617.tif 000027
【００６６】
本実施形態によっても、前述した第１実施形態と同様の効果が得られる。
【００６７】
第３実施形態
当該実施形態は、上述した第１実施形態の回路構成方法における図２に示すステップＳＴ２の処理を具体的にした一形態である。
ＣＰＵ３４が、第１実施形態で説明した上記（２−４）で示す拡大タワーとして、下記（５−１）の（Ａ），（Ｂ）で示す２つの拡大タワーを用いる。
ここで、次数ｍは、下記（５−２）のように定義される。
【００６８】
【数３８】
2004133617.tif 000028
【００６９】
【数３９】
2004133617.tif 000029
【００７０】
そして、ＣＰＵ３４が、上記（５−１）の拡大タワーに対応する下記（５−３）で定義される有限次拡大体Ｆｑ　上の上記（２−１）で示されるｍ次拡大体の下記（５−５）に示す２つの基底Ａ，Ｂのなかから、演算に用いるデータ表現形式である基底を選択（決定）する。
下記（５−３）内のｄは、下記（５−４）によって定義される。
また、下記（５−５）内のｄは、下記（５−６）によって定義される。
【００７１】
【数４０】
2004133617.tif 000030
【００７２】
【数４１】
2004133617.tif 000031
【００７３】
【数４２】
2004133617.tif 000032
【００７４】
【数４３】
2004133617.tif 000033
【００７５】
ＣＰＵ３４は、例えば、演算回路１０１を構成する演算のうち定数倍乗算については上記（５−５）の基底Ａを選択して、当該基底Ａをデータ表現形式として用いた定数倍乗算器である演算回路ブロックの構成データを生成する。
また、ＣＰＵ３４は、例えば、演算回路１０１を構成する演算のうち乗算については上記（５−５）の基底Ｂを選択して、当該基底Ｂをデータ表現形式として用いた乗算器である演算回路ブロックの構成データを生成する。
また、ＣＰＵ３４は、例えば、演算回路１０１を構成する演算のうち除算については上記（５−５）の基底Ｂを選択して、当該基底Ｂをデータ表現形式として用いた除算器である演算回路ブロックの構成データを生成する。
【００７６】
本実施形態によっても、前述した第１実施形態と同様の効果が得られる。
【００７７】
第４実施形態
当該実施形態では、上述した第３実施形態の回路構成方法における図２に示すステップＳＴ２の処理において、多項式基底の列を選択枠として用いた場合を説明する。
ＣＰＵ３４が、第１実施形態で説明した上記（２−４）で示す拡大タワーとして、下記（６−１）の（Ａ），（Ｂ）で示す２つの拡大タワーを用いる。
ここで、次数ｍは、下記（６−２）のように定義される。
【００７８】
【数４４】
2004133617.tif 000034
【００７９】
【数４５】
2004133617.tif 000035
【００８０】
そして、ＣＰＵ３４が、上記（６−１）の拡大タワーに対応する下記（６−３）で定義される有限次拡大体Ｆｑ　上の上記（２−１）で示されるｍ次拡大体の下記（６−５）に示す２つの基底Ａ，Ｂのなかから、演算に用いるデータ表現形式である基底を選択（決定）する。
下記（６−３）内のｄは、下記（６−４）によって定義される。
また、下記（６−５）内のｄは、下記（６−６）によって定義される。
【００８１】
【数４６】
2004133617.tif 000036
【００８２】
【数４７】
2004133617.tif 000037
【００８３】
【数４８】
2004133617.tif 000038
【００８４】
【数４９】
2004133617.tif 000039
【００８５】
ＣＰＵ３４は、例えば、演算回路１０１を構成する演算のうち定数倍乗算については上記（６−５）の基底Ａを選択して、当該基底Ａをデータ表現形式として用いた定数倍乗算器である演算回路ブロックの構成データを生成する。
また、ＣＰＵ３４は、例えば、演算回路１０１を構成する演算のうち乗算については上記（６−５）の基底Ｂを選択して、当該基底Ｂをデータ表現形式として用いた乗算器である演算回路ブロックの構成データを生成する。
また、ＣＰＵ３４は、例えば、演算回路１０１を構成する演算のうち除算については上記（６−５）の基底Ｂを選択して、当該基底Ｂをデータ表現形式として用いた除算器である演算回路ブロックの構成データを生成する。
【００８６】
本実施形態によっても、前述した第１実施形態と同様の効果が得られる。
【００８７】
第５実施形態
当該実施形態の回路構成方法では、以下に示す基底Ａ，Ｂをデータ表現形式として選択する。
ＣＰＵ３４が、第１実施形態で説明した上記（２−５）で示される次数の拡大についてのｍ次既約多項式の原始根αを用いた下記（７−１）で示す多項式基底を基底Ａとする。
【００８８】
【数５０】
2004133617.tif 000040
【００８９】
演算で扱うデータを、上記（２−１）で示される有限体の元として、基底Ａにより、下記（７−２）で表現する。
【００９０】
【数５１】
2004133617.tif 000041
【００９１】
そして、ＣＰＵ３４が、各基底の係数をｍ次元ベクトルとして下記（７−３）で示し、ｍ桁の信号線として扱うデータ表現形式を基底表現Ｂとする。
【００９２】
【数５２】
2004133617.tif 000042
【００９３】
このとき、上記（２−１）に示す有限体について、次数ｍが下記（７−４）のように因数分解可能である。
【００９４】
【数５３】
2004133617.tif 000043
【００９５】
そして、ＣＰＵ３４が、有限次拡大体Ｆｑ　から、それぞれｋ回の拡大を行うことにより、下記（７−５）に示す拡大タワーを構成する。
【００９６】
【数５４】
2004133617.tif 000044
【００９７】
そして、ＣＰＵ３４が、上記（７−５）のｍｉ　次拡大における既約ｎｉ　次多項式の原始根をγｉ　とした場合に、各拡大の多項式基底の合成によって得られる下記（７−６）に示すｍ次の基底を得る。これを基底Ｂとする。
【００９８】
【数５５】
2004133617.tif 000045
【００９９】
上記（７−６）では、下記（７−７），（７−８）に示す条件が満たされている。
【０１００】
【数５６】
2004133617.tif 000046
【０１０１】
【数５７】
2004133617.tif 000047
【０１０２】
そして、演算で扱うデータを、上記（２−１）で示される有限体の元として、基底Ｂにより、下記（７−９）で表現する。
【０１０３】
【数５８】
2004133617.tif 000048
【０１０４】
そして、各基底の係数をｍ次元ベクトルとして下記（７−１０）のように示しものをｍ桁の信号線として表現するデータ表現形式を基底表現Ｂとする。
【０１０５】
【数５９】
2004133617.tif 000049
【０１０６】
上記（７−１０）において、下記（７−１１），（７−１２）の要件が満たされている。
【０１０７】
【数６０】
2004133617.tif 000050
【０１０８】
【数６１】
2004133617.tif 000051
【０１０９】
以下、図１に示すコンピュータ２９が、例えば、複数の演算を図４に示す流れで行うことを示す演算内容データを入力した場合に行う回路構成方法について、図２に示す手順に従って説明する。
ステップＳＴ１：
ＣＰＵ３４は、例えば、ユーザによる操作部３１の操作に応じて、設計対象の演算回路が複数の演算を図４に示す流れで行うことを示す演算内容データを入力するなどして特定する。
図４に示すように、当該演算内容データは、以下の流れで複数の演算を行うことを示している。
すなわち、入力したデータに対して定数倍演算を行い（ＳＴ２１）、その結果のデータに対して逆元生成演算を行う（ＳＴ２２）。
続いて、上記逆元生成演算の結果と上記定数倍演算の結果との乗算を行う（ＳＴ２３）。
続いて、上記乗算の結果と、上記定数倍演算の結果との乗算を行う（ＳＴ２４）。
続いて、ステップＳＴ２４の乗算の結果に対して定数倍乗算を行い（ＳＴ２５）、その結果を出力する。
【０１１０】
ステップＳＴ２：
ＣＰＵ３４が、ステップＳＴ１で入力した演算内容データを基に、上記演算回路が行う複数の演算のそれぞれについて、各演算を行う回路の小規模化および演算時間の短縮の少なくとも一方を図る観点から、当該演算で用いるデータ表現形式を決定する。すなわち、ＣＰＵ３４が、図５に示すように、定数倍演算（ＳＴ２１，ＳＴ２５）は、データ表現形式として前述した基底表現Ａを用いて演算を行うことを決定する。
また、ＣＰＵ３４が、図５に示すように、逆元演算（ＳＴ２２）および乗算（ＳＴ２３，ＳＴ２４）は、データ表現形式として前述した基底表現Ｂを用いて演算を行うことを決定する。
【０１１１】
ステップＳＴ３：
ＣＰＵ３４が、上記演算内容データおよびステップＳＴ２で決定したデータ表現形式を用いて、上記複数の演算の各々を行う複数の演算回路ブロックの構成データ（回路データ）を生成する。
すなわち、ＣＰＵ３４が、ステップＳＴ２で決定したデータ表現形式を基に、図７に示すように、基底表現Ａを用いて定数倍演算を行う定数倍乗算器４０２、基底表現Ｂを用いて乗算を行う乗算器４０４，４０５、基底表現Ｂを用いて逆元生成演算を行う逆元生成器４０６、並びに基底表現Ａを用いて定数倍演算を行う定数倍乗算器４０３の構成データを生成する。
また、ＣＰＵ３４は、演算内容データに示される演算の流れを基に、各演算器間の接続関係（配線）を示す構成データも生成する。
【０１１２】
ステップＳＴ４：
ＣＰＵ３４が、上記演算内容データおよびステップＳＴ２で決定したデータ表現形式を基に、図６に示すように基底表現ＡからＢへの基底変換（ＳＴ３１，ＳＴ３２，ＳＴ３３）、並びに基底表現ＢからＡへの基底変換（ＳＴ３４）を行う必要があることを検出し、これらの基底変換を特定する。
【０１１３】
ステップＳＴ５：
ＣＰＵ３４が、ステップＳＴ４で特定した基底変換を基に、図７に示すように、基底表現ＡからＢへの基底変換（ＳＴ３１，ＳＴ３２，ＳＴ３３）を行う基底変換回路４０７，４０８，４０９、並びに基底表現ＢからＡへの基底変換（ＳＴ３４）を行う基底変換回路４１０の構成データを生成する。
ステップＳＴ６：
ＣＰＵ３４が、ステップＳＴ３で生成した構成データと、ステップＳＴ４で生成した構成データとを基に、図７に示す演算回路４０１の構成データ（回路データ）を生成する。
【０１１４】
図７に示すように、演算回路４０１は、定数倍乗算器４０２が、基底表現Ａのデータを入力し、このデータに対しての基底表現Ａで定数倍演算を施す。
定数倍乗算器４０２は、その演算結果を基底変換回路４０７，４０８，４０９に出力する。
基底変換回路４０７は、定数倍乗算器４０２から入力した基底表現Ａのデータを、基底表現Ｂに変換して乗算器４０４に出力する。
基底変換回路４０８は、定数倍乗算器４０２から入力した基底表現Ａのデータを、基底表現Ｂに変換して乗算器４０５に出力する。
基底変換回路４０９は、定数倍乗算器４０２から入力した基底表現Ａのデータを、基底表現Ｂに変換して逆元生成器４０６に出力する。
【０１１５】
逆元生成器４０６は、基底変換回路４０９からの基底表現Ｂのデータに対して逆元生成演算を施し、その結果を乗算器４０５に出力する。
乗算器４０５は、基底変換回路４０８から入力した基底表現Ｂのデータと、逆元生成器４０６から入力した基底表現Ｂのデータとの乗算を行い、その結果を乗算器４０４に出力する。
乗算器４０４は、基底変換回路４０７から入力した基底表現Ｂのデータと、乗算器４０５から入力した基底表現Ｂのデータとの乗算を行い、その結果を基底変換回路４１０に出力する。
基底変換回路４１０は、乗算器４０４から入力した基底表現Ｂのデータを、基底表現Ａに変換して定数倍乗算器４０３に出力する。
定数倍乗算器４０３は、基底変換回路４１０から入力した基底表現Ａのデータに対して定数倍演算を施し、その結果を出力する。
【０１１６】
以上説明したように、本実施形態によれば、効率面で基底表現Ａが適した定数倍乗算器４０２，４０３を基底表現Ａを用いて構成し、効率面で基底表現Ｂが適した乗算器４０４，４０５および逆元生成器４０６を基底表現Ｂを用いて構成でき、演算回路４０１全体を回路規模および演算時間の面で効率的に構成できる。
【０１１７】
第６実施形態
本発明の回路構成方法で構成する演算回路は、図３および図７に示す演算回路には限定されない。
本実施形態の回路構成方法では、例えば、図８に示す演算回路６０１を構成（設計）する。
図８に示すように、演算回路６０１は、それ自身は、データ表現形式としてデータ表現形式Ａを用い、データ表現形式Ａのデータを入力し、データ表現形式Ａのデータを出力する。
演算回路６０１は、データ表現形式Ａを用いる演算回路ブロック６０２と、データ表現形式Ｂを用いる演算回路ブロック６０３と、データ表現形式Ｃを用いる演算回路ブロック６０４とを有している。
また、演算回路６０１は、データ表現形式を変換する変換回路ブロック６０５，６０６，６０７，６０８を有する。
変換回路ブロック６０５は、入力したデータ表現形式Ａのデータをデータ表現形式Ｂのデータに変換して演算回路ブロック６０３に出力する。
変換回路ブロック６０６は、演算回路ブロック６０２から入力したデータ表現形式Ａのデータをデータ表現形式Ｃのデータに変換して演算回路ブロック６０４に出力する。
変換回路ブロック６０７は、演算回路ブロック６０３から入力したデータ表現形式Ｂのデータをデータ表現形式Ｃのデータに変換して演算回路ブロック６０４に出力する。
変換回路ブロック６０８は、演算回路ブロック６０４から入力したデータ表現形式Ｃのデータをデータ表現形式Ａのデータに変換して、演算回路６０１の外部に出力する。
【０１１８】
本実施形態の回路構成方法では、図８に示す演算回路６０１の回路データを、図２を用いて前述した手順で生成する。
ここで、データ表現形式Ａ，Ｂ，Ｃは、それぞれ基底表現Ａ，Ｂ，Ｃである。
また、演算回路ブロック６０２，６０３，６０４が行う演算は、それぞれ線形空間上で線形写像を行う演算である。
【０１１９】
第７実施形態
本実施形態の回路構成方法では、例えば、図９に示す演算回路７０１を構成（設計）する。
図９に示すように、演算回路７０１は、それ自身は、データ表現形式としてデータ表現形式Ａを用い、データ表現形式Ａのデータを入力し、データ表現形式Ａのデータを出力する。
演算回路６０１は、データ表現形式Ｂを用いる演算回路ブロック７０２を有している。
また、演算回路ブロック７０２は、データ表現形式Ａを用いる演算回路ブロック７０３を有している。
演算回路７０１は、変換回路ブロック７０４および７０７を有する。
変換回路ブロック７０４は、入力したデータ表現形式Ａのデータをデータ表現形式Ｂに変換して演算回路ブロック７０２に出力する。
変換回路ブロック７０７は、演算回路ブロック７０２から入力したデータ表現形式Ｂのデータをデータ表現形式Ａに変換して演算回路７０１の外部に出力する。
【０１２０】
演算回路ブロック７０２は、データ表現形式Ａを用いる演算回路ブロック７０３を有する。
また、演算回路ブロック７０２は、変換回路ブロック７０５および７０６を有する。
変換回路ブロック７０５は、入力したデータ表現形式Ｂのデータをデータ表現形式Ａに変換して演算回路ブロック７０３に出力する。
変換回路ブロック７０６は、演算回路ブロック７０３から入力したデータ表現形式Ａのデータをデータ表現形式Ｂに変換する。
【０１２１】
本実施形態の回路構成方法では、図９に示す演算回路７０１の構成データを、図２を用いて前述した手順で生成する。
ここで、データ表現形式Ａ，Ｂは、それぞれ基底表現Ａ，Ｂである。
また、演算回路ブロック７０２，７０３が行う演算は、それぞれ線形空間上で線形写像を行う演算である。
【０１２２】
第８実施形態
本実施形態の回路構成方法では、例えば、図１０に示す演算回路８０１を構成（設計）する。
図１０に示すように、演算回路８０１は、それ自身は、データ表現形式としてデータ表現形式Ａを用い、データ表現形式Ａのデータを入力し、データ表現形式Ａのデータを出力する。
演算回路８０１は、データ表現形式Ａを用いる演算回路ブロック８０２と、データ表現形式Ｂを用いる演算回路ブロック８０３と、データ表現形式の制限を受けない演算回路ブロック８０４とを有している。
また、演算回路８０１は、データ表現形式Ｂからデータ表現形式Ａへの変換を行って演算回路８０１の外部に出力する変換回路ブロック８０６を有する。
演算回路ブロック８０４内の任意の位置に、データ表現形式Ａからデータ表現形式Ｂに変換を行う変換回路ブロック８０５が配設されている。
【０１２３】
本実施形態の回路構成方法では、図１０に示す演算回路８０１の構成データを、図２を用いて前述した手順で生成する。
ここで、データ表現形式Ａ，Ｂは、それぞれ基底表現Ａ，Ｂである。
また、演算回路ブロック８０２，８０３が行う演算は、それぞれ線形空間上で線形写像を行う演算である。
【０１２４】
本発明は上述した実施形態には限定されない。
上述した実施形態では、演算回路内で２つ又は３つのデータ表現形式を用いる場合を例示したが、演算回路が用いるデータ表現形式の数は４つ以上であってもよい。
【０１２５】
【発明の効果】
以上説明したように、本発明によれば、異なる種類の複数の演算を行う演算回路を構成する場合に、各演算が行う演算回路ブロックを当該演算の種類に適合したデータ表現形式を用いて構成することを可能にする回路構成方法、その装置およびそのプログラムと、その演算回路を提供することができる。
【図面の簡単な説明】
【図１】図１は、本発明の実施形態の回路構成方法を実行するコンピュータを説明するための図である。
【図２】図２は、図１に示すＣＰＵの処理、本発明の実施形態の回路構成方法の手順を説明するためのフローチャートである。
【図３】図３は、本発明の第１実施形態の演算回路を説明するための図である。
【図４】図４は、図３に示す演算回路の回路構成方法を説明するための図である。
【図５】図５は、図３に示す演算回路の回路構成方法を説明するための図である。
【図６】図６は、図３に示す演算回路の回路構成方法を説明するための図である。
【図７】図７は、本発明の第５実施形態の演算回路を説明するための図である。
【図８】図８は、本発明の第６実施形態の演算回路を説明するための図である。
【図９】図９は、本発明の第７実施形態の演算回路を説明するための図である。
【図１０】図１０は、本発明の第８実施形態の演算回路を説明するための図である。
【図１１】図１１は、従来技術の問題点を説明するための図である。
【図１２】図１２は、従来技術の問題点を説明するための図である。
【符号の説明】
２９…コンピュータ、３１…操作部、３２…ディスプレイ、３３…メモリ、３４…ＣＰＵ、１０１，４０１…演算回路、１０２，１０３…演算回路ブロック、１０４，４０７，４０８，４０９，４１０，６０５，６０６，６０７，６０８，７０４，７０５，７０６，７０７，８０５，８０６…変換回路ブロック、４０２…定数倍乗算器、４０３…定数倍乗算器、４０４…乗算器、４０５…乗算器、４０６…逆元生成器、６０２，６０３，６０４，７０３，８０２，８０３…演算回路ブロック
【図１】
2004133617.tif 000064
【図２】
2004133617.tif 000065
【図３】
2004133617.tif 000066
【図４】
2004133617.tif 000067
【図５】
2004133617.tif 000068
【図６】
2004133617.tif 000069
【図７】
2004133617.tif 000070
【図８】
2004133617.tif 000071
【図９】
2004133617.tif 000072
【図１０】
2004133617.tif 000073
【図１１】
2004133617.tif 000074
【図１２】
2004133617.tif 000075