"離散フーリエ変換演算を行うための回路であって、前記離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段と、前記浮動小数点加算段の出力を回転因子によって乗算するための固定小数点段であって、前記固定小数点段は、複数のセットの回転因子を記憶するためのメモリであって、前記セットのそれぞれは、異なる量だけシフトされた個別の回転因子のコピーを含む、メモリと、前記浮動小数点段の出力の指数間の差分を判定し、前記差分を前記セットのそれぞれ内の前記個別の回転因子のコピーから選択するためのインデックスとして使用するための回路とを含む、固定小数点段とを含む、回路。前記浮動小数点加算段は、前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器とを含む、請求項1に記載の回路。前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器とは、非正規化加算を行い、前記浮動小数点加算段はさらに、前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器との非正規化出力を正規化するための正規化段を含む、請求項2に記載の回路。前記正規化段は、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を正規化するための第1の正規化モジュールと、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を正規化するための第2の正規化モジュールとを含む、請求項3に記載の回路。前記正規化段は、前記仮数の実数部を加算するための少なくとも1つの加算器の出力のための第1のシフタと、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力のための第2のシフタと、前記仮数の実数部を加算するための少なくとも1つの加算器の出力に関する第1の数の先行ゼロを判定するための第1の先行ゼロカウントモジュールと、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力に関する第2の数の先行ゼロを判定するための第2の先行ゼロカウントモジュールと、前記第1および第2の数の先行ゼロのうちのいずれが、より小さいかを判定し、前記第1および第2の数の先行ゼロのうちのより小さい方を、前記第1および第2のシフタのそれぞれに、前記仮数の実数部を加算するための少なくとも1つの加算器の出力と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力とがシフトされる、いくつかの場所として、適用するための比較器と、を含む、請求項3に記載の回路。前記回転因子は、実数回転因子と、虚数回転因子とを含み、前記固定小数点段はさらに、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を実数回転因子によって乗算するための第1の乗算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を虚数回転因子によって乗算するための第2の乗算器と、前記第2の乗算器の出力を前記第1の乗算器の出力から減算するための減算器と、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を虚数回転因子によって乗算するための第3の乗算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を実数回転因子によって乗算するための第4の乗算器と、前記第4の乗算器の出力を前記第3の乗算器の出力に加算するための加算器とを含む、請求項2に記載の回路。前記メモリは、異なる量だけシフトされた前記複数の回転因子を記憶するための2ポートメモリを含み、前記2ポートメモリの第1のアドレス入力は、前記個別の回転因子のうちの1つを選択し、前記差分は、前記個別の回転因子のうちの前記1つのシフトされたコピーのうちの1つを選択する前記2ポートメモリの第2のアドレス入力である、請求項1に記載の回路。離散フーリエ変換演算を行うための回路として、プログラム可能集積回路デバイスを構成する方法であって、前記方法は、前記離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成することと、前記浮動小数点加算段の出力を回転因子によって乗算するための固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成することであって、前記固定小数点段は、複数のセットの回転因子を記憶するためのメモリであって、前記セットのそれぞれは、異なる量だけシフトされた個別の回転因子のコピーを含む、メモリと、前記浮動小数点段の出力の指数間の差分を判定し、前記差分を前記セットのそれぞれ内の前記個別の回転因子のコピーから選択するためのインデックスとして使用するための回路とを含む、こととを含む、方法。浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器として、前記プログラム可能集積回路デバイスの論理を構成することを含む、請求項8に記載の方法。前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器として、前記プログラム可能集積回路デバイスの論理を構成することは、非正規化加算を行うように、前記プログラム可能集積回路デバイスの論理を構成することを含み、浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器の非正規化出力を正規化するための正規化段として、前記プログラム可能集積回路デバイスの論理を構成することを含む、請求項9に記載の方法。正規化段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を正規化するための第1の正規化モジュールとして、前記プログラム可能集積回路デバイスの論理を構成することと、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を正規化するための第2の正規化モジュールとして、前記プログラム可能集積回路デバイスの論理を構成することとを含む、請求項10に記載の方法。正規化段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記仮数の実数部を加算するための少なくとも1つの加算器の出力のための第1のシフタとして、前記プログラム可能集積回路デバイスの論理を構成することと、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力のための第2のシフタとして、前記プログラム可能集積回路デバイスの論理を構成することと、前記仮数の実数部を加算するための少なくとも1つの加算器の出力に関する第1の数の先行ゼロを判定するための第1の先行ゼロカウントモジュールとして、前記プログラム可能集積回路デバイスの論理を構成することと、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力に関する第2の数の先行ゼロを判定するための第2の先行ゼロカウントモジュールとして、前記プログラム可能集積回路デバイスの論理を構成することと、前記第1および第2の数の先行ゼロのうちのいずれが、より小さいかを判定し、前記第1および第2の数の先行ゼロのうちのより小さい方を、前記第1および第2のシフタのそれぞれに、前記仮数の実数部を加算するための少なくとも1つの加算器の出力と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力とがシフトされる、いくつかの場所として、適用するための比較器として、前記プログラム可能集積回路デバイスの論理を構成することと、を含む、請求項10に記載の方法。前記回転因子は、実数回転因子と、虚数回転因子とを含み、固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を実数回転因子によって乗算するための第1の乗算器として、前記プログラム可能集積回路デバイスの論理を構成することと、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を虚数回転因子によって乗算するための第2の乗算器として、前記プログラム可能集積回路デバイスの論理を構成することと、前記第2の乗算器の出力を前記第1の乗算器の出力から減算するための減算器として、前記プログラム可能集積回路デバイスの論理を構成することと、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を虚数回転因子によって乗算するための第3の乗算器として、前記プログラム可能集積回路デバイスの論理を構成することと、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を実数回転因子によって乗算するための第4の乗算器として、前記プログラム可能集積回路デバイスの論理を構成することと、前記第4の乗算器の出力を前記第3の乗算器の出力に加算するための加算器として、前記プログラム可能集積回路デバイスの論理を構成することとをさらに含む、請求項9に記載の方法。前記メモリは、異なる量だけシフトされた前記複数の回転因子を記憶するための2ポートメモリを含み、固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記個別の回転因子のうちの1つを選択するための前記2ポートメモリの第1のアドレス入力として、前記プログラム可能集積回路デバイスの論理を構成することを含み、固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記個別の回転因子のうちの前記1つのシフトされたコピーのうちの1つを選択する、前記2ポートメモリの第2のアドレス入力として、前記差分を使用するように、前記プログラム可能集積回路デバイスの論理を構成することを含む、請求項8に記載の方法。プログラム可能集積回路デバイスであって、離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段として構成可能な論理と、浮動小数点加算段の出力を回転因子によって乗算するための固定小数点段として構成可能な論理であって、前記固定小数点段は、複数のセットの回転因子を記憶するためのメモリであって、前記セットのそれぞれは、異なる量だけシフトされた個別の回転因子のコピーを含む、メモリと、前記浮動小数点段の出力の指数間の差分を判定し、前記差分を前記セットのそれぞれ内の前記個別の回転因子のコピーから選択するためのインデックスとして使用するための回路とを含む、論理とを含む、プログラム可能集積回路デバイス。浮動小数点加算段として構成可能な論理は、前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器として構成可能な論理を含む、請求項15に記載のプログラム可能集積回路デバイス。前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器としての前記プログラム可能集積回路デバイスは、非正規化加算を行うように構成可能な論理を含み、浮動小数点加算段として構成可能な論理は、前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器との非正規化出力を正規化するための正規化段として構成可能な論理を含む、請求項16に記載のプログラム可能集積回路デバイス。前記正規化段として構成可能な論理は、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を正規化するための第1の正規化モジュールとして構成可能な論理と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を正規化するための第2の正規化モジュールとして構成可能な論理とを含む、請求項17に記載のプログラム可能集積回路デバイス。前記正規化段として構成可能な論理は、前記仮数の実数部を加算するための少なくとも1つの加算器の出力のための第1のシフタとして構成可能な論理と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力のための第2のシフタとして構成可能な論理と、前記仮数の実数部を加算するための少なくとも1つの加算器の出力に関する第1の数の先行ゼロを判定するための第1の先行ゼロカウントモジュールとして構成可能な論理と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力に関する第2の数の先行ゼロを判定するための第2の先行ゼロカウントモジュールとして構成可能な論理と、前記第1および第2の数の先行ゼロのうちのいずれが、より小さいかを判定し、前記第1および第2の数の先行ゼロのうちのより小さい方を、前記第1および第2のシフタのそれぞれに、前記仮数の実数部を加算するための少なくとも1つの加算器の出力と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力とがシフトされる、いくつかの場所として、適用するための比較器として構成可能な論理と、を含む、請求項17に記載のプログラム可能集積回路デバイス。前記回転因子は、実数回転因子と、虚数回転因子とを含み、固定小数点段として構成可能な論理は、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を実数回転因子によって乗算するための第1の乗算器として構成可能な論理と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を虚数回転因子によって乗算するための第2の乗算器として構成可能な論理と、前記第2の乗算器の出力を前記第1の乗算器の出力から減算するための減算器として構成可能な論理と、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を虚数回転因子によって乗算するための第3の乗算器として構成可能な論理と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を実数回転因子によって乗算するための第4の乗算器として構成可能な論理と、前記第4の乗算器の出力を前記第3の乗算器の出力に加算するための加算器として構成可能な論理とをさらに含む、請求項16に記載のプログラム可能集積回路デバイス。前記メモリは、異なる量だけシフトされた前記複数の回転因子を記憶するための2ポートメモリを含み、前記固定小数点段として構成可能な論理は、前記個別の回転因子のうちの1つを選択するための前記2ポートメモリの第1のアドレス入力として構成可能な論理を含み、前記固定小数点段として構成可能な論理は、前記個別の回転因子のうちの前記1つのシフトされたコピーのうちの1つを選択する、前記2ポートメモリの第2のアドレス入力として、前記差分を使用するように構成可能な論理を含む、請求項15に記載のプログラム可能集積回路デバイス。離散フーリエ変換演算を行うための回路として、プログラム可能集積回路デバイスを構成するための機械実行可能命令によってエンコードされる、機械可読データ記憶媒体であって、前記命令は、前記離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記浮動小数点加算段の出力を回転因子によって乗算するための固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成するための命令であって、前記固定小数点段は、複数のセットの回転因子を記憶するためのメモリであって、前記セットのそれぞれは、異なる量だけシフトされた個別の回転因子のコピーを含む、メモリと、前記浮動小数点段の出力の指数間の差分を判定し、前記差分を前記セットのそれぞれ内の前記個別の回転因子のコピーから選択するためのインデックスとして使用するための回路とを含む、命令とを含む、機械可読データ記憶媒体。浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令を含む、請求項22に記載の機械可読データ記憶媒体。前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、非正規化加算を行うように、前記プログラム可能集積回路デバイスの論理を構成するための命令を含み、浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記仮数の実数部を加算するための少なくとも1つの加算器と、前記仮数の虚数部を加算するための少なくとも1つの加算器との非正規化出力を正規化するための正規化段として、前記プログラム可能集積回路デバイスの論理を構成するための命令を含む、請求項23に記載の機械可読データ記憶媒体。正規化段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を正規化するための第1の正規化モジュールとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を正規化するための第2の正規化モジュールとして、前記プログラム可能集積回路デバイスの論理を構成するための命令とを含む、請求項24に記載の機械可読データ記憶媒体。正規化段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記仮数の実数部を加算するための少なくとも1つの加算器の出力のための第1のシフタとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力のための第2のシフタとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記仮数の実数部を加算するための少なくとも1つの加算器の出力に関する第1の数の先行ゼロを判定するための第1の先行ゼロカウントモジュールとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力に関する第2の数の先行ゼロを判定するための第2の先行ゼロカウントモジュールとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記第1および第2の数の先行ゼロのうちのいずれが、より小さいかを判定し、前記第1および第2の数の先行ゼロのうちのより小さい方を、前記第1および第2のシフタのそれぞれに、前記仮数の実数部を加算するための少なくとも1つの加算器の出力と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力とが、シフトされる、いくつかの場所として、適用するための比較器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、を含む、請求項24に記載の機械可読データ記憶媒体。前記回転因子は、実数回転因子と、虚数回転因子とを含み、固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を実数回転因子によって乗算するための第1の乗算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を虚数回転因子によって乗算するための第2の乗算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記第2の乗算器の出力を前記第1の乗算器の出力から減算するための減算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記仮数の実数部を加算するための少なくとも1つの加算器の出力を虚数回転因子によって乗算するための第3の乗算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記仮数の虚数部を加算するための少なくとも1つの加算器の出力を実数回転因子によって乗算するための第4の乗算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、前記第4の乗算器の出力を前記第3の乗算器の出力に加算するための加算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令とをさらに含む、請求項23に記載の機械可読データ記憶媒体。前記メモリは、異なる量だけシフトされた前記複数の回転因子を記憶するための2ポートメモリを含み、固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記個別の回転因子のうちの1つを選択するための前記2ポートメモリの第1のアドレス入力として、前記プログラム可能集積回路デバイスの論理を構成することを含み、固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記個別の回転因子のうちの前記1つのシフトされたコピーのうちの1つを選択する、前記2ポートメモリの第2のアドレス入力として、前記差分を使用するように、前記プログラム可能集積回路デバイスの論理を構成することを含む、請求項22に記載の機械可読データ記憶媒体。発明の概要本発明は、浮動小数点乗算演算を固定小数点演算と置換することによる、DFT演算を行うために必要とされるリソースの減少に関する。これは、DFT計算における回転因子の数が、比較的に小さく、相互の小ビット数内にあるため、行うことができる。したがって、浮動小数点乗算器を使用して、DFTを算出する代わりに、固定小数点乗算器を使用することができる。必要とされる精度は、各回転因子の複数のコピーを記憶することによって得られ、各コピーは、異なる量だけシフトされる。乗算されるべき値の指数間の差分は、適切にシフトされた回転因子を読み出すための回転因子記憶へのインデックスとして使用される。したがって、本発明によると、離散フーリエ変換を行うための回路が提供される。回路は、離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段と、浮動小数点加算段の出力を回転因子で乗算するための固定小数点段と、を含む。固定小数点段は、複数のセットの回転因子を記憶するためのメモリであって、それらのセットはそれぞれ、異なる量だけシフトされた個別の回転因子のコピーを含む、メモリと、浮動小数点段の出力の指数間の差分を判定し、その差分をセットのそれぞれ内のその個別の回転因子のそれらのコピーから選択するためのインデックスとして使用するための回路と、を含む。プログラム可能デバイス上のそのような回路を構成するための方法、そのように構成可能なプログラム可能デバイス、および方法を行うためのソフトウェアでエンコードされた機械可読データ記憶媒体もまた、提供される。本発明のさらなる特徴、その性質、および種々の利点は、全体を通して、同一参照文字が同一部品を指す付随の図面と関連して検討される、以下の発明を実施するための形態を考慮することによって、明白となるであろう。基数4のDFTは、4つの複素入力R1,I1、R2,I2、R3,I3、およびR4,I4を有する。図1から分かるように、第1の二進数{1,1,1,1}の計算100では、実数部はすべて、加算器101、102、103を使用して加算され、虚数部はすべて、加算器111、112、113を使用して加算される。DFTの本部分は、加算器のみ必要とする。実数出力104は、実数和103と実数回転因子107の積106と、虚数和113と虚数回転因子117の積116との間の差分105として、計算される。虚数出力114は、実数和103と虚数回転因子117の積126と、虚数和113と実数回転因子107の積136の和115として、計算される。乗算器106、116、126、136以外、演算は、加算器を使用して、行うことができる。基数4のDFTの付加的二進数は、{1,-j,-1,j}、{1,-1,1,-1}、および{1,j,-1,-j}を入力値に適用することによって、計算される。浮動小数点演算では、論理否定は、容易に実装される例えば、符号ビットを反転することによって。同様に、jによる乗算は、マルチプレクサならびに排他的論理和関数を使用して実装され得る、ある数の実数と虚数成分をスワッピングすることによって、達成される。したがって、付加的二進数は、これらの付加的関数が追加された、図1に類似する構造で行われてもよい図示せず。基数16のDFTの場合、2つの基数4の段が、必要とされるであろう。第1の段の出力上の複素乗算器は、限定数の複素回転因子、すなわち、W0、W1、W2、W3、W4、W6、W9式中、Wx=e-2jπx/16が適用されるであろう。図1に示される演算子は、浮動小数点計算のためのIEEE754-1985規格に準拠した浮動小数点演算子であってもよい。図2は、図1の算出が、同時係属中の本発明の譲受人に譲渡された2007年1月22日出願の米国特許出願第11/625,655号に説明されるような浮動小数点演算子を使用することによって、より少ないリソースを使用してどのように算出され得るかを示しており、浮動小数点数は、ほとんどの場合、非正規化形式に維持され、a前述のIEEE754-1985規格に準拠した出力のために、またはb精度の損失が生じ得る場合、正規化される。したがって、加算201、202、203、211、212、213は、浮動小数点演算子であるが、値は、それらの演算の間、正規化されない。しかしながら、結果として生じた和は、乗算段205の前に、206、216において、正規化される。乗算段205内では、乗算器215、225、235、245、加算器255、および減算器265は、浮動小数点演算子であるが、値は、それらの演算の間、正規化されない。しかしながら、結果は、204、214における出力のために、207、217において、正規化される。これは、図1の実装と比較して、約50のリソースの使用の削減をもたらし得る。正規化ブロック206、216後、実数および虚数仮数は両方とも、2倍または相互の倍数以内にあるが、その指数は、異なってもよいことが観察され得る。次のDFTブロック前の複素乗算のための回転因子も同様に、小値数を有する可能性が高いであろう。例えば、2つの基数4のDFT段を有する基数16のDFTの場合、実数および虚数回転因子を構成する値の小数の規模は、1、0.9239、0.7071、および0.3827であって、すべて、二進数として表される時、相互の2ビット以内である。その結果、乗算器が、若干、浮動小数点仮数の精度を上回る場合、複素乗算は、ほとんどの場合、固定小数点演算を使用して、実装し、付加的リソースを節約することができる。本発明による実施形態では、通常、単精度浮動小数点乗算のために使用される、36ビット乗算器が、複数の回転因子の記憶のためのメモリとともに、利用可能である。本発明の本実施形態によると、DFT計算のための回転因子は、異なる量だけシフトされた複数の固定小数点コピーとして、各回転因子を記憶することによって、固定小数点に変換されてもよい。DFT入力は、計算に対する唯一の浮動小数点入力のままである。入力と回転因子との間の指数差分は、いかなる精度の損失も伴うことなく、回転因子メモリから適切にシフトされた回転因子を検索するためのインデックスとして、判定および使用することができる。本論理的構成300は、図3に示される。図2の場合のように、加算201、202、203、211、212、213は、浮動小数点演算子であるが、値は、それらの演算の間、正規化されない。再び、結果として生じた和は、乗算段305の前に、206、216において、正規化される。乗算段305では、乗算器315、325、335、345、加算器355、および減算器365は、固定小数点演算子である。乗算器315、325、335、345の出力は、加算器355および減算器365によって加算または減算され得るように、その相対値を相互に整列させる。乗算器出力の整列は、回転因子をシフトすることによって、達成されてもよい。各回転因子のシフトの量は、乗算器入力の指数間の差分となるであろう。一実施形態では、各乗算器対すなわち、実数出力を生成する対と、虚数出力を生成する対の場合、一方の回転因子は、シフトされず、他方は、シフトされるであろう。論理的に、これは、図3に示されるシフタによって表され得るが、一物理的実装は、後述のように、図4に示される。より大きな出力値は、1に近いすなわち、1の2ビットの規模以内の回転因子によって乗算される、正規化されたデータ値となるであろう。したがって、出力に必要とされる可能性として考えられる正規化が存在するであろうが、前述のように、基数4の小区分に分解される基数16のDFTの場合、最大3ビットの正規化が存在するであろう。出力指数308は、出力仮数正規化値によって調節され得る、正規化206、216後の最大指数から計算されてもよい。任意の調節に先立った指数値もまた、309において、適切にシフトされた回転因子を選択するためのインデックスとして使用される。論理構成300は、多くの論理を節約しないであろうが、待ち時間を短縮させ得る。しかしながら、論理構成300の物理的実施形態400が、図4に示される。非正規化浮動小数点加算器201、202、203、211、212、213、正規化モジュール206、216、固定小数点乗算器315、325、335、345、加算器355、および減算器365の配列は、論理構成300と同一である。メモリ401は、実数回転因子のために提供される一方、メモリ402は、虚数回転因子のために提供される。ほとんどの大きなDFT構成、例えば、基数16のDFT内の第1の段のための10個の回転因子そのうち4個は、一意であってもよい、および基数64のDFT内の第1の段のための51個の回転因子そのうち約35個は、一意であってもよいに対する限定数の回転因子のため、シフトはすべて、事前に算出され、メモリ内に記憶することができる。例えば、AlteraCorporationから市販のプログラム可能論理デバイスのSTRATIXRファミリーのプログラム可能論理デバイス等の集積回路デバイスでは、十分な数の内蔵メモリモジュールが、本機能を果たすために、デバイス上に提供される。メモリ401、402はそれぞれ、必要に応じて、複数のそのような内蔵メモリモジュールを含んでもよい。しかしながら、例証を容易にするために、メモリ401、402はそれぞれ、単一メモリモジュールとして、図4に示される。示される実施例では、メモリ401、402はそれぞれ、デュアルポートメモリである。故に、それぞれ、個別の対のアドレス411、421および412、422によって、アドレスされてもよい。各アドレス対の要素は、単一アドレスの上位および低位部分と見なされてもよく、低位アドレス部分411、412は、いくつかの回転因子のうちのいずれがアクセスされているかを識別し、上位アドレス部分421、422は、その回転因子のシフトされたバージョンのうちのいずれがアクセスされているかを識別する。アドレスの生成は、以下のように行われる。実数出力は、2つの乗算、すなわち、実数データ×実数回転因子および虚数データ×虚数回転因子を有する。アドレス1は、この場合、実数および虚数回転因子にアクセスするために使用されるであろう。アドレス1の実数オフセット実数回転因子メモリに対するオフセットを計算するためには、実数データの指数が、虚数データの指数から減算される。この数が、ゼロまたは正数虚数指数>実数指数である場合、これが、オフセット値であるかつ、シフト値でもある。この数が、負数実数指数>虚数指数である場合、この数は、ゼロにされる。アドレス1の虚数オフセット虚数回転因子メモリに対するオフセットを計算するためには、虚数データの指数が、実数データの指数から減算される。この数が、ゼロまたは正数実数指数>虚数指数である場合、これが、オフセット値であるかつ、シフト値でもある。この数が、負数虚数指数>実数指数である場合、この数は、ゼロにされる。虚数出力は、2つの乗算、すなわち、実数データ×虚数回転因子および虚数データ×実数回転因子を有する。アドレス2は、この場合、実数および虚数回転因子にアクセスするために使用されるであろう。アドレス2の実数オフセット虚数回転因子メモリに対するオフセットを計算するためには、実数データの指数が、虚数データの指数から減算される。この数が、ゼロまたは正数虚数指数>実数指数である場合、これが、オフセット値であるかつ、シフト値でもある。この数が、負数実数指数>虚数指数である場合、この数は、ゼロにされる。アドレス2の虚数オフセット実数回転因子メモリに対するオフセットを計算するためには、虚数データの指数が、実数データの指数から減算される。この数が、ゼロまたは正数実数指数>虚数指数である場合、これが、オフセット値であるまた、シフト値でもある。この数が、負数虚数指数>実数指数である場合、この数は、ゼロにされる。以上のように、アドレス1およびアドレス2の両方の計算は、同一である。実数オフセットは、実数回転因子メモリの読み出しアドレス1および虚数回転因子メモリの読み出しアドレス2に移動する。虚数オフセットは、実数回転因子メモリの読み出しアドレス2および虚数回転因子メモリの読み出しアドレス1に移動する。実数および虚数オフセットを算出するための論理500は、図5に示される。以上のように、虚数オフセット501は、503において、虚数データの指数505を実数データの指数506から減算することによって、算出される。結果513は、508において、その最上位ビット523の逆数507とANDで連結され、結果513が、負数である場合、結果501をゼロにする。同様に、実数オフセット502は、553において、実数データの指数506を虚数データの指数505から減算することによって、算出される。結果563は、558において、その最上位ビット573の逆数557とANDで連結され、結果563が、負数である場合、結果502をゼロにする。図6に示される代替実施形態600では、図4におけるように、完全正規化206、216の代わりに、実数入力601および虚数入力611を正規化するために必要とされる個別のシフト量が、先行ゼロカウントモジュール602、612によって判定され、より小さいシフトすなわち、値601、611の大きい方を正規化するために使用されるシフトが、603において、先行ゼロカウントを比較することによって選択されるように、入力601、611の両方を左シフトさせるために、シフタ604、614において使用される。したがって、入力601、611の一方は、その完全規模を留保するであろうが、入力601、611の他方は、その部分的規模のみ留保するであろう。しかしながら、前述のように、回転因子はすべて、ほぼ同一の規模であるため、前述のSTRATIXRファミリーのプログラム可能論理デバイス等のデバイスを想定すると、乗算器615、625、635、645が、36ビット幅である時、単精度23ビット仮数値の正確性は、右シフトされる場合でも、維持することができる。本発明の実装の実施例として、1KストリーミングFFTを検討する。従来、これは、5つの基数4の段を使用して実装され、そのうちの最初の4つは、複素乗算器を必要とするであろう。256個の要素、合計数千の回転因子を必要とするであろう。本発明を使用することによって、1KストリーミングFFTは、基数16の段、基数4の段、および基数16の段を使用して実装され得る。第1の基数16段は、出力上の標準的複素乗算器とともに、最適化された内部複素乗算器を使用するであろう。代替として、最適化された複素乗算器は、出力上で使用され得る。64個の複素回転因子の場合、これは、シフトのすべてが、事前に計算されている時、約32または36×64=約2,000個の複素回転因子メモリ場所を必要とするであろう。次の基数4の段は、シフトのすべてが、事前に計算されている時、16個の回転因子のみ、すなわち、合計約32または36×16=約512個の複素回転因子メモリ場所が存在するであろうため、最適化された複素乗算器を使用し得る。最後の基数16の段は、第1の段として、ほぼ同一数の回転因子とともに、内部最適化された複素乗算器を使用するであろう。DFTを行うように、プログラム可能デバイスをプログラムするための本発明による方法を実行するための命令は、前述のように、加算および減算演算を行うように、PLDまたは他のプログラム可能デバイスをプログラミングあるいは構成するための本発明の方法を実装するために、好適なコンピュータまたは類似デバイスによって実行されるように、機械可読媒体上でエンコードされてもよい。例えば、パーソナルコンピュータは、PLDを接続することができる、インターフェースを備えてもよく、パーソナルコンピュータは、AlteraCorporationSanJose、Californiaから市販のQUARTUSRIIソフトウェア等、好適なソフトウェアツールを使用して、PLDをプログラムするために、ユーザによって使用することができる。図7は、前述のパーソナルコンピュータ、または他のコンピュータ、または類似デバイス等のシステムによって実行することができる、機械実行可能プログラムでエンコードされ得る、磁気データ記憶媒体800の断面を表す。媒体800は、フロッピー登録商標ディスケットまたはハードディスク、あるいは従来のものであり得る、好適な基板801を有する、磁気テープ、および片側または両側に、その極性または配向を磁気的に改変することができる、磁気領域不可視を含有する、従来のものであり得る、好適なコーティング802であり得る。磁気テープの場合を除き、媒体800はまた、ディスクドライブまたは他のデータ記憶デバイスの軸を受容するための開口部図示せずを有してもよい。媒体800のコーティング802の磁気領域は、本発明に従って、該当する場合、その特殊処理ブロックを含むPLDの適切な部分を構成するために、プログラムされるべきPLDが挿入され得るソケットまたは周辺付属装置を有する、パーソナルコンピュータ、または他のコンピュータ、または類似システム等のプログラムミングシステムによる実行のために、機械実行可能プログラムを、従来のものであり得る態様で、エンコードするように極性化または配向される。図8は、また、前述のパーソナルコンピュータ、または他のコンピュータ、または類似デバイス等のシステムによって、実行することができる、そのような機械実行可能プログラムでエンコードされ得る、光可読データ記憶媒体810の断面を示す。媒体810は、従来のコンパクトディスク読取専用メモリCD-ROM、またはデジタルビデオディスク読取専用メモリDVD-ROM、またはCD-R、CD-RW、DVD-R、DVD-RW、DVDR、DVDRW、またはDVD-RAM等の書換可能媒体、または光可読および磁気光書換可能である、磁気光ディスクであり得る。媒体810は、好ましくは、従来のものであり得る、好適な基板811と、通常、基板811の片側または両側の、従来のものであり得る、好適なコーティング812と、を有する。CDベースまたはDVDベースの媒体の場合、周知のように、コーティング812は、反射性であって、1つ以上の層上に配列される、複数のピット813で刻印され、機械実行可能プログラムをエンコードする。ピットの配列は、レーザ光をコーティング812の表面に反射させることによって、読み出される。好ましくは、実質的に、透明である、保護コーティング814が、コーティング812の上部に提供される。磁気光ディスクの場合、周知のように、コーティング812は、ピット813を有していないが、極性または配向が、レーザ図示せずによって等、ある温度を上回って加熱されると、磁気的に変化し得る、複数の磁気領域を有する。領域の配向は、コーティング812から反射されたレーザ光の偏光を測定することによって、読み出すことができる。本領域の配列は、前述のように、プログラムをエンコードする。本発明に従ってプログラムされたPLD90は、電子デバイスの多くの種類において使用されてもよい。可能性のある使用の1つは、図9に示されるデータ処理システム900内である。データ処理システム900は、プロセッサ901、メモリ902、I/O回路903、および周辺デバイス904構成可能のうちの1つ以上を含んでもよい。これらの構成可能は、システムバス905によって、ともに連結され、エンドユーザシステム907内に含有される、回路基板906上に取り込まれる。システム900は、コンピュータネットワーキング、データネットワーキング、計器、ビデオ処理、デジタル信号処理、あるいはプログラム可能または再プログラム可能論理を使用する利点が、望ましい任意の他の用途等、種々の用途で使用することができる。PLD90は、種々の異なる論理関数を行うために使用することができる。例えば、PLD90は、プロセッサ901と協働する、プロセッサまたはコントローラとして、構成することができる。PLD90はまた、システム900内の共有リソースへのアクセスを調停するための調停回路として、使用されてもよい。さらに別の実施例では、PLD90は、プロセッサ901とシステム900内の他の構成可能のうちの1つとの間のインターフェースとして、構成することができる。システム900は、例示に過ぎず、本発明の真の範囲および精神は、以下の請求項によって示されるべきであることに留意されたい。種々の技術を使用して、前述のように、本発明を組み込む、PLD90を実行するうことができる。前述は、本発明の原理の例証に過ぎず、種々の修正が、本発明の範囲および精神から逸脱することなく、当業者によって行うことができることを理解されるであろう。例えば、本発明の種々の要素は、任意の所望の数および/または配列において、PLD上に提供することができる。当業者は、本発明が、制限ではなく、例証目的のために提示される、説明された実施形態以外によって、実践することができ、本発明が、以下の請求項によってのみ、制限されることを理解するであろう。"