(57)【要約】【課題】所定データに対してそれぞれ異なる複数の演算を行なう演算回路を構成する場合に、当該演算回路を小規模に構成できる回路構成方法を提供する。【解決手段】所定のデータに対してそれぞれ異なる複数の第１の演算を施す演算回路を設計する場合に、複数の第１の演算のそれぞれを構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する（ＳＴ１３）。そして、複数の第１の演算で共用されＳＴ１３で特定された第２の演算を行う演算回路を有する演算回路を構成する（Ｔ１４）。【選択図】  図８
2004164465.tif 000002
【特許請求の範囲】
【請求項１】
所定のデータに対してそれぞれ異なる複数の第１の演算を施す演算回路の回路設計方法であって、
前記複数の第１の演算のそれぞれを構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する第１の工程と、
前記複数の第１の演算で共用され前記第１の工程で特定された前記第２の演算を行う第１の演算回路と、前記複数の第１の演算のそれぞれを構成する前記複数の第２の演算のうち前記第１の工程で特定された前記第２の演算以外の演算を行う第２の演算回路とからなる前記演算回路を構成する第２の工程と
を有する回路構成方法。
【請求項２】
前記第１の演算は、線形変換の演算であり、
前記第２の演算は、加算である
請求項１に記載の回路構成方法。
【請求項３】
前記複数の第１の演算が、前記所定のデータに対して第１の線形変換をそれぞれ異なる所定の回数施す演算である場合に、
前記複数の第１の演算のそれぞれについて、前記所定の回数に対応する数の前記第１の線形変換を合成した第２の線形変換を規定する第３の工程
をさらに有し、
前記第１の工程において、前記第３の工程で前記複数の第１の演算のそれぞれについて規定された前記第２の線形変換を構成する前記複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する
請求項１に記載の回路構成方法。
【請求項４】
前記第２の工程において、前記第３の工程で規定された前記第２の線形変換を基に、前記所定のデータに対して前記複数の第１の演算を並列に行うように前記演算回路を構成する
請求項３に記載の回路構成方法。
【請求項５】
前記所定データは、所定の線形空間上の所定の基底により、ベクトルで表現されたものであり、
前記線形変換は、前記線形空間上で規定された変換である
請求項３に記載の回路構成方法。
【請求項６】
前記所定の線形空間を下記（１−１）で示し、前記所定の基底として下記（１−２）に示す基底を用い、下記（１−２）に示す基底を基に前記所定のデータであるデータａが下記（１−３）のように示されるとき、当該データａをｍ次元ベクトルとして下記（１−４）で示し、前記第１の線形変換を下記（１−１）に示す線形空間上の線形変換Ｄとし、前記複数の演算の結果であるデータｂをｋ次元ベクトルとして下記（１−５）で示し、下記（１−５）に示すデータｂを構成する各演算の結果を示すデータｂｉをｄｉ次元ベクトルとして下記（１−６）で示した場合に
前記第３の工程において、ｄｉ行ｍ列の行列Ｄで構成され前記第２の線形変換を行う下記（１−７）で示される行列Ｍを規定し、
前記第１の工程において、前記第３の工程で規定された下記（１−７）を基に、前記複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する
請求項３に記載の回路構成方法。
ここで、ｍ，ｄｉは２以上の整数であり、前記複数の演算の少なくとも一つに対応する前記所定の回数が２以上であり、ｋは２以上の整数である。
【数１】
2004164465.tif 000029
【数２】
2004164465.tif 000030
【数３】
2004164465.tif 000031
【数４】
2004164465.tif 000032
【数５】
2004164465.tif 000033
【数６】
2004164465.tif 000034
【数７】
2004164465.tif 000035
【請求項７】
前記所定の基底として下記（１−８）に示す基底を用い、前記データａが下記（１−９）のように示されるとき、前記データａをｍ次元ベクトルとして下記（１−１０）の示す
請求項６に記載の回路構成方法。
【数８】
2004164465.tif 000036
【数９】
2004164465.tif 000037
【数１０】
2004164465.tif 000038
【請求項８】
前記第３の工程において、前記線形空間上の元γを基にγｒ  倍の演算を行う前記行列Ｄで構成された前記行列Ｍを規定する
請求項６に記載の回路構成方法。
【請求項９】
所定のデータに対してそれぞれ異なる複数の第１の演算を施す演算回路の回路設計装置であって、
前記複数の第１の演算のそれぞれを構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する第１の手段と、
前記複数の第１の演算で共用され前記第１の手段で特定された前記第２の演算を行う第１の演算回路と、前記複数の第１の演算のそれぞれを構成する前記複数の第２の演算のうち前記第１の手段で特定された前記第２の演算以外の演算を行う第２の演算回路とからなる前記演算回路を構成する第２の手段と
を有する回路構成装置。
【請求項１０】
所定のデータに対してそれぞれ異なる複数の第１の演算を施す演算回路の回路設計装置で実行されるプログラムであって、
前記複数の第１の演算のそれぞれを構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する第１の手順と、
前記複数の第１の演算で共用され前記第１の手順で特定された前記第２の演算を行う第１の演算回路と、前記複数の第１の演算のそれぞれを構成する前記複数の第２の演算のうち前記第１の手順で特定された前記第２の演算以外の演算を行う第２の演算回路とからなる前記演算回路を構成する第２の手順と
を有するプログラム。
【発明の詳細な説明】
【０００１】
【発明が属する技術分野】
本発明は、例えば、誤り訂正符号や復号などを行う場合に用いられる線形変換などの演算を行う演算回路の回路構成方法、その装置およびそのプログラムに関する。
【０００２】
【従来の技術】
例えば、ハミング符号などの誤り訂正符号や復号では、有限体上で規定された線形空間で種々の線形変換の演算が行われる。
このような線形変換の演算は、例えば、線形空間上の所定の基底により、線形空間上の元をベクトルで表現し、このベクトルに対して線形変換の演算を施して新たなベクトルを得る。
上述した誤り訂正符号や復号では、例えば、複数ビットの所定データに対してそれぞれ異なる線形変換の複数の演算を行なう場合がある。
従来では、例えば、上記複数の演算をそれぞれ独立して行なうように演算回路を構成（設計）している。
【０００３】
【発明が解決しようとする課題】
しかしながら、上述したように、上記複数の演算をそれぞれ独立して行なうように演算回路を構成すると、演算回路が大規模になるという問題がある。
【０００４】
本発明は上述した従来技術の問題点に鑑みてなされ、所定データに対してそれぞれ異なる複数の演算を行なう演算回路を構成する場合に、当該演算回路を小規模に構成できる回路構成方法、その装置およびそのプログラムを提供することを目的とする。
【０００５】
【課題を解決するための手段】
上述した従来技術の問題点を解決し、上述した目的を達成するために、第１の発明の回路設計方法は、所定のデータに対してそれぞれ異なる複数の第１の演算を施す演算回路の回路設計方法であって、前記複数の第１の演算のそれぞれを構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する第１の工程と、前記複数の第１の演算で共用され前記第１の工程で特定された前記第２の演算を行う第１の演算回路と、前記複数の第１の演算のそれぞれを構成する前記複数の第２の演算のうち前記第１の工程で特定された前記第２の演算以外の演算を行う第２の演算回路とからなる前記演算回路を構成する第２の工程とを有する。
【０００６】
第１の発明の回路構成方法では、先ず、第１の工程において、複数の第１の演算のそれぞれを構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算が特定される。
そして、第２の工程において、前記複数の第１の演算で共用され前記第１の工程で特定された前記第２の演算を行う第１の演算回路と、前記複数の第１の演算のそれぞれを構成する前記複数の第２の演算のうち前記第１の工程で特定された前記第２の演算以外の演算を行う第２の演算回路とからなる前記演算回路が構成される。
【０００７】
第２の発明の回路構成装置は、所定のデータに対してそれぞれ異なる複数の第１の演算を施す演算回路の回路設計装置であって、前記複数の第１の演算のそれぞれを構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する第１の手段と、前記複数の第１の演算で共用され前記第１の手段で特定された前記第２の演算を行う第１の演算回路と、前記複数の第１の演算のそれぞれを構成する前記複数の第２の演算のうち前記第１の手段で特定された前記第２の演算以外の演算を行う第２の演算回路とからなる前記演算回路を構成する第２の手段とを有する。
【０００８】
第２の発明の回路構成装置では、第１の手段が、複数の第１の演算のそれぞれを構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する。
そして、第２の手段が、前記複数の第１の演算で共用され前記第１の手段で特定された前記第２の演算を行う第１の演算回路と、前記複数の第１の演算のそれぞれを構成する前記複数の第２の演算のうち前記第１の手段で特定された前記第２の演算以外の演算を行う第２の演算回路とからなる前記演算回路を構成する。
【０００９】
第３の発明のプログラムは、所定のデータに対してそれぞれ異なる複数の第１の演算を施す演算回路の回路設計装置で実行されるプログラムであって、前記複数の第１の演算のそれぞれを構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する第１の手順と、前記複数の第１の演算で共用され前記第１の手順で特定された前記第２の演算を行う第１の演算回路と、前記複数の第１の演算のそれぞれを構成する前記複数の第２の演算のうち前記第１の手順で特定された前記第２の演算以外の演算を行う第２の演算回路とからなる前記演算回路を構成する第２の手順とを有する。
【００１０】
【発明の実施の形態】
以下、本発明の実施形態について説明する。
〔本発明の関連技術〕
図１は、本発明の関連技術に係わる演算回路１０１の構成図である。
演算回路１０１は、データａを入力として、データｂ１  〜ｂｋ  を出力する。
演算回路１０１は、ｉを１≦ｉ≦ｋを満たす２以上の自然数、ｌｉ  を自然数とした場合に、各系統で行列Ｍｉ，１  〜Ｍｉ，ｌｉによって規定された演算Ｃｉ，１  〜Ｃｉ，ｌｉを順に行う複数系統の演算回路モジュールを有し、これらの演算回路モジュールで並列に演算を行う。
各演算モジュールは、演算Ｃｉ，１  〜Ｃｉ，ｌｊをそれぞれ行う複数の演算回路２ｉｌｊ  を直接に接続して構成される。
演算回路１０１は、線形空間上の基底によりベクトル表現されたデータａを入力し、演算回路２１ｌ１  〜２ｋｌｋ  でデータａに線形演算を施し、演算回路２１ｌ１  〜２ｋｌｋ  からそれぞれｂ１  〜ｂｋ  を出力する。
【００１１】
図１に示す演算回路１は、各演算回路モジュール内の演算Ｃｉ，１  〜Ｃｉ，ｌｉを図２に示すように合成した演算回路モジュールｉｌｊ  （ｊは２以上の整数）を用いた演算回路２０１のように構成することで、小規模化および高速化が図れる。
この場合に、図２および下記（２−１）に示すように規定された線形変換列が、下記（２−２）に示すように合成される。
【００１２】
【数１１】
2004164465.tif 000003
【００１３】
【数１２】
2004164465.tif 000004
【００１４】
このとき、上記（２−１）に示す演算Ｃｉ，１  〜Ｃｉ，ｌｉを線形変換を行う行列Ｍｉ，１  〜Ｍｉ，ｌｉとすると、上記（２−１），（２−２）は、それぞれ下記（２−３），（２−４）のように示される。
【００１５】
【数１３】
2004164465.tif 000005
【００１６】
【数１４】
2004164465.tif 000006
【００１７】
これにより、演算回路２０１を、下記（２−５）に示す行列を行う回路として構成できる。
【００１８】
【数１５】
2004164465.tif 000007
【００１９】
次に、入力したデータＦＳ０に対して、第１の線形変換Ｄをそれぞれ異なる所定の回数施す複数の演算を行い、当該演算の結果であるデータｂ１  〜ｂｋ  を出力する演算回路の構成方法について説明する。
図３は、このような演算回路３０１、並びにその周辺回路を説明するための図である。
【００２０】
図３に示すように、セレクタ３１２において選択信号ＳＥＬを基に、入力データａとデータＭＬＳとのうち一方のデータが選択され、当該選択されたデータＦＳ０がレジスタ３１３０  および演算回路３０１に出力される。
演算回路３０１は、セレクタ１２から入力したデータＦＳ０に対して、第１の線形変換Ｄをそれぞれ異なる所定の回数施す複数の演算を行い、当該演算の結果であるデータｂ１  〜ｂｋ  をそれぞれレジスタ３１３１  〜３１３ｋ  に出力する。
レジスタ３１３０  〜３１３ｋ  は、入力したデータＦＳ０，ｂ１  〜ｂｋ  を保持し、所定のタイミングで、これらをデータＯＵＴ０  〜ＯＵＴＫ  として出力する。
演算回路３１４は、データＯＵＴｋ  を入力し、これに第１の線形演算Ｄを施して、その結果であるデータＭＳＬをセレクタ３１２に出力する。
【００２１】
演算回路３０１は、例えば、図３に示すように、それぞれ線形変換Ｄを行う複数の演算回路３２１１  〜３２１ｋ  を直列に接続し、データａを初段の回路３２１１  に入力し、個々の演算回路３２１１  〜３２１ｋ  で生成されたデータｂ１  〜ｂｋをレジスタ３１３１  〜３１３ｋ  に出力するように構成（設計）される。
【００２２】
ここで、図３に示す演算回路３０１は、有限体Ｆ（２４  ）の元、α，α２  ＋α＋１＝０に対してα倍演算を行なうものである場合、図４に示すように構成される。
この場合に、図３に示すように、あるタイミングで入力されたデータａに対して、データＯＵＴ０  ，ＯＵＴ１  ，ＯＵＴ２  は、以下のようになる。
【００２３】
【表１】
ＯＵＴ０  ：ａ，ａ×αｋ＋１  ，ａ×α２ｋ＋２，・・・，
ＯＵＴ１  ：    ａ×α，ａ×αＫ＋２  ，ａ×α２Ｋ＋３，・・・，
ＯＵＴ２  ：            ａ×α２  ，ａ×αＫ＋３  ，ａ×α２Ｋ＋４，・・・，
【００２４】
ここで、ＦＳ０＝Ａ０＋Ａ１αとすると、以下のようになる。
ＦＳ０・α＝Ａ１＋（Ａ０＋Ａ１）α
ＦＳ０・α２  ＝（Ａ０＋Ａ１）＋Ａ０α
【００２５】
従って、図４に示す演算回路３２１１  ，３２１２  は、図５に示すように、それぞれ１個の加算回路３５１１  ，３５１２  によって構成される。
【００２６】
しかしながら、上述したように、演算回路３０１を設計すると、回路規模が大きくなるという問題がある。
また、演算回路３０１において、データａを初段の回路３２１１  に入力してから最終段の回路３２１ｋ  からデータｂｋ  が出力されるまでの時間が長くなり、高性能な演算回路３０１を設計できないという問題がある。
【００２７】
以下、上述した関連技術の問題点を解決する本発明の実施形態を説明する。
〔第１実施形態〕
図６は、本実施形態の回路構成方法で構成（設計）される演算回路１１の周辺回路を説明するための図である。
図６に示すように、セレクタ１２において選択信号ＳＥＬを基に、入力データａとデータＭＬＳとのうち一方のデータが選択され、当該選択されたデータＦＳ０がレジスタ１３０  および演算回路１１に出力される。
演算回路１１は、セレクタ１２から入力したデータＦＳ０に対して、第１の線形変換Ｄをそれぞれ異なる所定の回数施す複数の演算を行い、当該演算の結果であるデータｂ１  〜ｂｋ  をそれぞれレジスタ１３１  〜１３ｋ  に出力する。
レジスタ１３０  〜１３ｋ  は、入力したデータＦＳ０，ｂ１  〜ｂｋ  を保持し、所定のタイミングで、これらをデータＯＵＴ０  〜ＯＵＴＫ  として出力する。
演算回路１４は、データＯＵＴｋ  を入力し、これに第１の線形演算Ｄを施して、その結果であるデータＭＳＬをセレクタ１２に出力する。
【００２８】
本実施形態の回路構成方法は、図６に示す演算回路１１を構成（設計）するものである。
【００２９】
本実施形態では、所定の線形空間が、ｑを素数とした場合に有限体Ｆｑ  のｍ次拡大であり、その元がＦｑ  上のｍ次ベクトルで表現された場合に、当該所定の線形空間を下記（３−１）、あるいはＦ（ｑｍ  ）で示す。
【００３０】
【数１６】
2004164465.tif 000008
【００３１】
また、所定の基底として下記（３−２）に示す基底を用い、下記（３−２）に示す基底を基に前記所定のデータであるデータａを下記（３−３）のように示す。
【００３２】
【数１７】
2004164465.tif 000009
【００３３】
【数１８】
2004164465.tif 000010
【００３４】
また、上記データａをｍ次元ベクトルとして下記（３−４）のように示す。
【００３５】
【数１９】
2004164465.tif 000011
また、上記第１の線形変換Ｄを上記（３−１）に示す線形空間上の線形変換Ｄとする。
【００３６】
また、上記複数の演算の結果であるデータｂをｋ次元ベクトルとして下記（３−５）で示し、下記（３−５）に示すデータｂを構成するの各演算の結果を示すデータｂｉをｄｉ次元ベクトルとして下記（３−６）で示す。
ここで、ｍ，ｄｉは２以上の整数であり、前記複数の演算の少なくとも一つに対応する前記所定の回数が２以上であり、ｋは２以上の整数である。
【００３７】
【数２０】
2004164465.tif 000012
【００３８】
【数２１】
2004164465.tif 000013
【００３９】
ここで、上記複数の演算を、それぞれＯＰ１  〜ＯＰＫ  とすると、これらは下記（３−７）で示される。
【００４０】
【数２２】
2004164465.tif 000014
【００４１】
そして、第１の線形変換Ｄを表すｄｉ行ｍ列の行列をＭｄとすると、上記（３−７）は、下記（３−８）で示される。
【００４２】
【数２３】
2004164465.tif 000015
【００４３】
上記ＯＰ１  〜ＯＰＫ  によって規定される変換列の合成を表したｄｉ行ｍ列の行列Ｍｄ〜Ｍｄｋ  を縦に並べたｋ・ｄｉ×ｍの行列Ｍは、下記（３−９）で示される。
【００４４】
【数２４】
2004164465.tif 000016
【００４５】
上記（３−９）に示すように、行列Ｍが、データａに対して第１の線形変換と、第２の変換Ｄ２  〜Ｄｋ  をそれぞれ行うｋ個の演算を規定している。
【００４６】
図７は、本実施形態の回路構成方法を実行するコンピュータ２９を説明するための図である。
図７に示すように、コンピュータ２９は、例えば、操作部３１、ディスプレイ３２、メモリ３３およびＣＰＵ３４を有し、これらがバス３０を介して接続されている。
操作部３１は、キーボードやマウスなどの操作手段であり、ＣＰＵ３４にプログラムの実行指示、データ選択指示、並びにデータ入力を行うために用いられる。
ディスプレイ３２は、ＣＰＵ３４の処理結果を表示する。
メモリ３３は、ＣＰＵ３４によって実行されるプログラム４１と、プログラム４１の実行に用いられるデータ４２とを記憶する。
【００４７】
ＣＰＵ３４は、プログラム４１を実行して以下に示す処理を行い、プログラム４１の実行過程でデータ４２を用いて、演算回路１１の回路を構成（設計）する処理を行う。
プログラム４１は、本発明のプログラムに対応し、以下に示す各ステップの内容を示す手順を記述している。
また、ＣＰＵ３４がプログラム４１を実行することで、本発明の回路構成装置が構成され、ＣＰＵ３４がステップＳＴ１２を実行して本発明の第１の手段を構成し、ＣＰＵ３４がステップＳＴ１３を実行して本発明の第２の手段を構成する。
【００４８】
以下、本実施形態の回路構成方法の動作例を、ＣＰＵ３４の処理と関連付けて説明する。
図８は、本実施形態の回路構成方法の動作例を説明するためのフローチャートである。
ステップＳＴ１１：
ＣＰＵ３４は、例えば、ユーザによる操作部３１の操作に応じて、上記（３−４），（３−５），（３−６）に示すように演算回路１１が行う演算の入力および出力の形式、並びに上記（３−７）に示すように演算回路１１が行うそれぞれ所定の回数に対応する数の第１の線形変換Ｄをデータａに施す複数の演算の内容を規定するデータを入力する。
【００４９】
ステップＳＴ１２：
ＣＰＵ３４が、ステップＳＴ１１で入力した上記（３−７）に示す演算回路１１が行う複数の演算のそれぞれについて、上記所定の回数に対応する数の第１の線形変換Ｄを合成して得られる第２の線形変換（第１の演算）を行う上記（３−９）に示す行列Ｍを生成する処理を行う。
【００５０】
ステップＳＴ１３：
ＣＰＵ３４が、上記ステップＳＴ１２で規定された複数の第２の線形変換（第１の演算）を構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う前記第２の演算を特定する。
【００５１】
ステップＳＴ１４：
ＣＰＵ３４が、複数の第２の線形演算（第１の演算）で共用されステップＳＴ１３で特定された上記第２の演算を行う第１の演算回路と、上記複数の第１の演算のそれぞれを構成する上記複数の第２の演算のうちステップＳＴ１３で特定された上記第２の演算以外の演算を行う第２の演算回路とからなる図９に示す演算回路１１を構成する。
このとき、ＣＰＵ３４が、上記（３−９）に示すステップＳＴ１２で生成された行列Ｍを基に、データＦＳ０に対して第１の線形変換Ｄ〜Ｄｋ  をそれぞれ行うｋ個の演算を並列に行うように演算回路１１の構成（設計）データを生成する。
具体的には、ＣＰＵ３４が、図９に示すように、データＦＳ０に対して第１の線形変換Ｄ〜Ｄｋ  をそれぞれ行う演算回路２１１  〜２１ｋ  を並列に配置した演算回路１１の構成を示す構成データを生成する。
【００５２】
これにより、ＣＰＵ３４は、入力したデータＦＳ０に上記（３−９）に示す行列Ｍで規定された線形変換を施し、データｂ１  〜ｂｋ  を出力するように構成された演算回路１１の構成データを生成する。
【００５３】
図９に示すように演算回路１１を構成することで、レジスタ１３０  〜１３ｋ  からの出力は、横方向を時間として、図１０に示すようになる。
すなわち、演算回路１から、データｂ１  〜ｂｋ  が略同じタイミングで出力されるため、データＯＵＴ０  〜ＯＵＴＫ  も略同じタイミングで出力される。
このとき、演算回路１１が行う行列Ｍの演算と、演算回路１１に入力されるデータＦＳ０と、データＯＵＴ０  〜ＯＵＴＫ  との関係は、下記（３−１０）で示される。
【００５４】
【数２５】
2004164465.tif 000017
【００５５】
ここで、上記行列Ｍは上記（３−１）で規定された線形空間の元によって構成されるため、データＯＵＴ１  〜ＯＵＴＫ  （データｂ１  〜ｂｋ  ）は、上記線形空間の元とデータＦＳ０の各要素との積、並びにそれらの和として規定される。そのため、それらの組み合わせは、高々有限となり、例えば、値ｋが値ｍに対して大きい場合に、図８に示すように、演算回路１１から出力されたデータｂｋ  を演算回路１４およびセレクタ１２を介して演算回路１１にフィーロバックすることで、多様な演算に対応可能な演算回路１１を小規模な構成で構築できる。
【００５６】
以下、ここで、図９に示す演算回路１１の演算回路２１１  ，２１Ｋ  は、有限体Ｆ（２４  ）の元、α，α２  ＋α＋１＝０に対してα倍演算を行なうものである場合、図１１に示す演算回路２２１のように構成される。
この場合に、図３に示すように、あるタイミングで入力されたデータａに対して、データＯＵＴ０  ，ＯＵＴ１  ，ＯＵＴ２  は、以下のようになる。
【００５７】
ＯＵＴ０  ：ａ，ａ×αｋ＋１  ，ａ×α２ｋ＋２，・・・，
ＯＵＴ１  ：ａ×α，ａ×αＫ＋２  ，ａ×α２Ｋ＋３，・・・，
ＯＵＴ２  ：ａ×α２  ，ａ×αＫ＋３  ，ａ×α２Ｋ＋４，・・・，
すなわち、ＦＳ０＝Ａ０＋Ａ１αとすると、次のクロックサイクルにおけるデータＯＵＴ０  ，ＯＵＴ１  ，ＯＵＴ２  は、以下のようになる。
【００５８】
ＯＵＴ０  ：ＦＳ０＝Ａ０＋Ａ１α
ＯＵＴ１  ：ＦＳ０・α＝Ａ１＋（Ａ０＋Ａ１）α
ＯＵＴ２  ：ＦＳ０・α・α＝（Ａ０＋Ａ１）＋Ａ０α
【００５９】
この場合に、前述した図８に示すステップＳＴ１３において、ＣＰＵ３４が、上記α倍演算を構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う上記第２の演算、すなわち、演算「Ａ０＋Ａ１」を特定する。
そして、図８に示すステップＳＴ１４において、ＣＰＵ３４が、複数のα倍演算（すなわち、α倍演算と、α２  倍演算）で共用されステップＳＴ１３で特定された演算「Ａ０＋Ａ１」を行う図１１に示す第１の演算回路１１５（図１１では加算回路）と、複数のα倍演算のそれぞれを構成する上記複数の第２の演算のうちステップＳＴ１３で特定された上記第２の演算以外の演算を行う第２の演算回路（図１１に示す例では無し）とからなる図１１に示す演算回路１１ａを構成する。
【００６０】
なお、上述した実施形態において、上記第１の線形変換が、上記（３−１）で規定した線形空間の元γに対してγｒ  倍演算（×γｒ  ）を行うものである場合には、上記複数の演算を、それぞれＯＰ１  〜ＯＰＫ  とすると、これらは下記（３−１１）で示される。
【００６１】
【数２６】
2004164465.tif 000018
【００６２】
そして、第１の線形変換Ｄを表すｄｉ行ｍ列の行列をＭｒとすると、上記（３−１１）は、下記（３−１２）で示される。
【００６３】
【数２７】
2004164465.tif 000019
【００６４】
上記ＯＰ１  〜ＯＰＫ  によって規定される変換列の合成を表したｄｉ行ｍ列の行列Ｍｒ〜Ｍｒｋ  を縦に並べたｋ・ｄｉ×ｍの行列Ｍｒは、下記（３−１３）で示される。
ここで、Ｍｒｘ  （ｘは１≦ｘ≦ｋを満たす整数）は、Ｘ個のＭｒを合成した行列である。
【００６５】
【数２８】
2004164465.tif 000020
【００６６】
上記（３−１３）に示すように、行列Ｍが、データａに対してγｒ  〜ｒｋｒ倍演算（×γｒ  ）をそれぞれ行うｋ個の演算を規定している。
【００６７】
この場合には、図１２に示すように、ＣＰＵ３４が、データＦＳ０に対してγｒ  〜ｒｋｒ倍演算（×γｒ  ）をそれぞれ行う演算回路２１１  〜２１ｋ  を有する演算回路１１の構成を示す構成データを生成する。
【００６８】
以上説明したように、本実施形態の回路構成方法では、上述したように図８に示すステップＳＴ１３において、複数の第１の演算（Ｄ倍演算、α倍演算）を構成する複数の第２の演算のうち、同じデータに対して同じ演算を行う上記第２の演算を特定する。
そして、ステップＳＴ１４において、上記複数の第１の演算で共用され上記特定された上記第２の演算を行う第１の演算回路と、上記複数の第１の演算のそれぞれを構成する上記複数の第２の演算のうち上記特定された上記第２の演算以外の演算を行う第２の演算回路とからなる演算回路１１，１１ａを構成する。
そのため、本実施形態の回路構成方法によれば、演算回路１１，１１ａを小規模に構成できる。
【００６９】
また、本実施形態の回路構成方法では、図８に示すステップＳＴ１２で、ステップＳＴ１１で入力した上記（３−７）に示す演算回路１１が行う複数の演算のそれぞれについて、上記所定の回数に対応する数の第１の線形変換Ｄを合成して得られる第２の線形変換（第１の演算）を行う上記（３−９）に示す行列Ｍを生成し、これに対して上述したステップＳＴ１３，ＳＴ１４の処理を行う。
そのため、本実施形態の回路構成方法によれば、演算回路１１，１１ａを小規模に構成できると共に、演算時間を短縮できる。
また、本実施形態の回路構成方法では、図９および図１１に示すように、演算回路１１が、データＦＳ０に対して、第１の演算を並列に行うため、演算時間をさらに短縮できる。
すなわち、演算回路２１１  〜２１ｋ  においてデータＦＳ０（データａ）を並列に処理するため、データｂ１  〜ｂｋ  （データＯＵＴ１  〜ＯＵＴＫ  ）の全てを略同じタイミングで得ることができる。
そのため、データＦＳ０を入力してからデータｂ２  〜ｂｋ  を得るまでの時間を図３に示す構成に比べて短縮した演算回路１１を構成（設計）できる。
【００７０】
〔第２実施形態〕
本実施形態では、有限体Ｆ（２４  ）上の元として扱われる４ビットのデータＤ（＝Ｄ〔３〕，Ｄ〔２〕，Ｄ〔１〕，Ｄ〔０〕）を縦ベクトルと見なし、当該データＤに対して下記（３−１４），（３−１５）で示す行列Ｍ１，Ｍ２で示される２つの線形変換を施す回路を構成する場合を例示する。
【００７１】
【数２９】
2004164465.tif 000021
【００７２】
【数３０】
2004164465.tif 000022
【００７３】
従来では、出力値Ｅ１＝Ｍ１・Ｄ、Ｅ２＝Ｍ２・Ｄは、それぞれ縦ベクトルとして表現され、下記（３−１６），（３−１７）で示される。
【００７４】
【数３１】
2004164465.tif 000023
【００７５】
【数３２】
2004164465.tif 000024
【００７６】
従来の回路構成方法では、図１３に示すように、上記（３−１６）に示す演算を行う演算回路４０２と、上記（３−１７）に示す演算を行う演算回路４０３とを有する演算回路４０１が構成される。
演算回路４０２は、加算回路４１１，４１２，４１３，４１４で構成される。
また、演算回路４０３は、加算回路４２１，４２２，４２３で構成される。
【００７７】
本実施形態の回路構成方法は、上記（３−１４），（３−１５）に示す行列Ｍ１，Ｍ２によって表現される線形変換を，有限体Ｆ（２４  ）上の元として扱われる４ビットのデータＤ（＝Ｄ〔３〕，Ｄ〔２〕，Ｄ〔１〕，Ｄ〔０〕）に施すことは同じである。
本実施形態では、２つの４×４行列を用いる代わりに、行列Ｍ１とＭ２とを連結した下記（３−１８）に示される行列Ｍを用いる。
【００７８】
【数３３】
2004164465.tif 000025
【００７９】
本実施形態の回路構成方法では、上記行列Ｍの演算を行い、上記（３−１６），（３−１７）内の演算において、行列Ｍ１に相当する第１の演算と行列Ｍ２に相当する第１の演算とを構成する複数の第２の演算のうち、共通する第２の演算である「Ｄ〔０〕＋Ｄ〔２〕」、並びに「Ｄ〔１〕＋Ｄ〔２〕」を特定する。
そして、図１４に示すように、第２の演算「Ｄ〔０〕＋Ｄ〔２〕」を行う図１３に示す加算回路４１２と４２１と、第２の演算「Ｄ〔１〕＋Ｄ〔２〕」を行う図１３に示す加算回路４１３と４２２が共用化され、加算回路４１２，４１３が削減され、図１３に示す演算回路４０１に比べて、回路規模が縮小された演算回路４０３が構成される。
これにより、図１３に示す演算回路４０１と同じ演算を行う図１４に示す演算回路４０３を、演算回路４０１に比べて小規模に構成できる。
【００８０】
本発明は上述した実施形態には限定されない。
その他の実施形態として、上記所定の基底として下記（３−１９）に示す基底を用い、上記データａを下記（３−２０）のように示し、前記データａをｍ次元ベクトルとして下記（３−２１）のように示してもよい。
【００８１】
【数３４】
2004164465.tif 000026
【００８２】
【数３５】
2004164465.tif 000027
【００８３】
【数３６】
2004164465.tif 000028
【００８４】
【発明の効果】
以上説明したように、本発明によれば、所定データに対してそれぞれ異なる複数の演算を行なう演算回路を構成する場合に、当該演算回路を小規模に構成できる回路構成方法、その装置およびそのプログラムを提供することができる。
【図面の簡単な説明】
【図１】図１は、本発明の関連技術を説明するための図である。
【図２】図２は、本発明の関連技術を説明するための図である。
【図３】図３は、本発明の関連技術を説明するための図である。
【図４】図４は、本発明の関連技術を説明するための図である。
【図５】図５は、本発明の関連技術を説明するための図である。
【図６】図６は、本発明の第１実施形態の回路構成方法で構成（設計）される演算回路の周辺回路を説明するための図である。
【図７】図７は、本発明の第１実施形態の回路構成方法を実行するコンピュータを説明するための図である。
【図８】図８は、本発明の第１実施形態の回路構成方法の手順によって演算回路を構成する場合を説明するためのフローチャートである。
【図９】図９は、本発明の第１実施形態の回路構成方法で構成（設計）される演算回路を説明するための図である。
【図１０】図１０は、図９に示す演算回路のデータ出力タイミングを説明するための図である。
【図１１】図１１は、図９に示す演算回路の具体例を説明するための図である。
【図１２】図１２は、本発明の第１実施形態の回路構成方法によって構成されるγｒ  〜ｒｋｒ倍演算（×γｒ  ）を行う演算回路を説明するための図である。
【図１３】図１３は、本発明の第２実施形態の回路構成方法の関連技術を説明するための図である。
【図１４】図１４は、本発明の第２実施形態の回路構成方法を説明するための図である。
【符号の説明】
１１…演算回路、１２…セレクタ、１３０  〜１３ｋ  …レジスタ、１４…演算回路、２１１  〜２１ｋ  …演算回路、３０…バス、３１…操作部、３２…ディスプレイ、３３…メモリ、４１…プログラム、４２…データ
【図１】
2004164465.tif 000039
【図２】
2004164465.tif 000040
【図３】
2004164465.tif 000041
【図４】
2004164465.tif 000042
【図５】
2004164465.tif 000043
【図６】
2004164465.tif 000044
【図７】
2004164465.tif 000045
【図８】
2004164465.tif 000046
【図９】
2004164465.tif 000047
【図１０】
2004164465.tif 000048
【図１１】
2004164465.tif 000049
【図１２】
2004164465.tif 000050
【図１３】
2004164465.tif 000051
【図１４】
2004164465.tif 000052