(57)【要約】離散フーリエ変換を行う回路。回路は、固定論理デバイス内に提供することができる、またはプログラム可能論理デバイス等のプログラム可能集積回路デバイス内に構成することができる。回路は、離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段と、浮動小数点加算段の出力を回転因子で乗算するための固定小数点段と、を含む。固定小数点段は、複数のセットの回転因子を記憶するためのメモリを含み、それらのセットはそれぞれ、異なる量だけシフトされた個別の回転因子のコピーと、浮動小数点段の出力の指数間の差分を判定し、その差分をセットのそれぞれ内のその個別の回転因子のそれらのコピーから選択するためのインデックスとして使用するための回路と、を含む。
2013521575.tif 000002
【特許請求の範囲】
【請求項１】
離散フーリエ変換演算を行うための回路であって、
前記離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段と、
前記浮動小数点加算段の出力を回転因子によって乗算するための固定小数点段であって、
前記固定小数点段は、
複数のセットの回転因子を記憶するためのメモリであって、前記セットのそれぞれは、異なる量だけシフトされた個別の回転因子のコピーを含む、メモリと、
前記浮動小数点段の出力の指数間の差分を判定し、前記差分を前記セットのそれぞれ内の前記個別の回転因子のコピーから選択するためのインデックスとして使用するための回路と
を含む、固定小数点段と
を含む、回路。
【請求項２】
前記浮動小数点加算段は、前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器とを含む、請求項１に記載の回路。
【請求項３】
前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器とは、非正規化加算を行い、
前記浮動小数点加算段はさらに、前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器との非正規化出力を正規化するための正規化段を含む、
請求項２に記載の回路。
【請求項４】
前記正規化段は、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を正規化するための第１の正規化モジュールと、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を正規化するための第２の正規化モジュールと
を含む、請求項３に記載の回路。
【請求項５】
前記正規化段は、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力のための第１のシフタと、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力のための第２のシフタと、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力に関する第１の数の先行ゼロを判定するための第１の先行ゼロカウントモジュールと、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力に関する第２の数の先行ゼロを判定するための第２の先行ゼロカウントモジュールと、
前記第１および第２の数の先行ゼロのうちのいずれが、より小さいかを判定し、前記第１および第２の数の先行ゼロのうちのより小さい方を、前記第１および第２のシフタのそれぞれに、前記仮数の実数部を加算するための少なくとも１つの加算器の出力と、前記仮数の虚数部を加算するための少なくとも１つの加算器の出力とがシフトされる、いくつかの場所として、適用するための比較器と、
を含む、請求項３に記載の回路。
【請求項６】
前記回転因子は、実数回転因子と、虚数回転因子とを含み、
前記固定小数点段はさらに、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を実数回転因子によって乗算するための第１の乗算器と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を虚数回転因子によって乗算するための第２の乗算器と、
前記第２の乗算器の出力を前記第１の乗算器の出力から減算するための減算器と、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を虚数回転因子によって乗算するための第３の乗算器と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を実数回転因子によって乗算するための第４の乗算器と、
前記第４の乗算器の出力を前記第３の乗算器の出力に加算するための加算器と
を含む、請求項２に記載の回路。
【請求項７】
前記メモリは、異なる量だけシフトされた前記複数の回転因子を記憶するための２ポートメモリを含み、
前記２ポートメモリの第１のアドレス入力は、前記個別の回転因子のうちの１つを選択し、
前記差分は、前記個別の回転因子のうちの前記１つのシフトされたコピーのうちの１つを選択する前記２ポートメモリの第２のアドレス入力である、
請求項１に記載の回路。
【請求項８】
離散フーリエ変換演算を行うための回路として、プログラム可能集積回路デバイスを構成する方法であって、
前記方法は、
前記離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成することと、
前記浮動小数点加算段の出力を回転因子によって乗算するための固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成することであって、
前記固定小数点段は、
複数のセットの回転因子を記憶するためのメモリであって、前記セットのそれぞれは、異なる量だけシフトされた個別の回転因子のコピーを含む、メモリと、
前記浮動小数点段の出力の指数間の差分を判定し、前記差分を前記セットのそれぞれ内の前記個別の回転因子のコピーから選択するためのインデックスとして使用するための回路と
を含む、ことと
を含む、方法。
【請求項９】
浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器として、前記プログラム可能集積回路デバイスの論理を構成することを含む、請求項８に記載の方法。
【請求項１０】
前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器として、前記プログラム可能集積回路デバイスの論理を構成することは、非正規化加算を行うように、前記プログラム可能集積回路デバイスの論理を構成することを含み、
浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器の非正規化出力を正規化するための正規化段として、前記プログラム可能集積回路デバイスの論理を構成することを含む、
請求項９に記載の方法。
【請求項１１】
正規化段として、前記プログラム可能集積回路デバイスの論理を構成することは、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を正規化するための第１の正規化モジュールとして、前記プログラム可能集積回路デバイスの論理を構成することと、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を正規化するための第２の正規化モジュールとして、前記プログラム可能集積回路デバイスの論理を構成することと
を含む、請求項１０に記載の方法。
【請求項１２】
正規化段として、前記プログラム可能集積回路デバイスの論理を構成することは、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力のための第１のシフタとして、前記プログラム可能集積回路デバイスの論理を構成することと、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力のための第２のシフタとして、前記プログラム可能集積回路デバイスの論理を構成することと、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力に関する第１の数の先行ゼロを判定するための第１の先行ゼロカウントモジュールとして、前記プログラム可能集積回路デバイスの論理を構成することと、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力に関する第２の数の先行ゼロを判定するための第２の先行ゼロカウントモジュールとして、前記プログラム可能集積回路デバイスの論理を構成することと、
前記第１および第２の数の先行ゼロのうちのいずれが、より小さいかを判定し、前記第１および第２の数の先行ゼロのうちのより小さい方を、前記第１および第２のシフタのそれぞれに、前記仮数の実数部を加算するための少なくとも１つの加算器の出力と、前記仮数の虚数部を加算するための少なくとも１つの加算器の出力とがシフトされる、いくつかの場所として、適用するための比較器として、前記プログラム可能集積回路デバイスの論理を構成することと、
を含む、請求項１０に記載の方法。
【請求項１３】
前記回転因子は、実数回転因子と、虚数回転因子とを含み、
固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成することは、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を実数回転因子によって乗算するための第１の乗算器として、前記プログラム可能集積回路デバイスの論理を構成することと、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を虚数回転因子によって乗算するための第２の乗算器として、前記プログラム可能集積回路デバイスの論理を構成することと、
前記第２の乗算器の出力を前記第１の乗算器の出力から減算するための減算器として、前記プログラム可能集積回路デバイスの論理を構成することと、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を虚数回転因子によって乗算するための第３の乗算器として、前記プログラム可能集積回路デバイスの論理を構成することと、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を実数回転因子によって乗算するための第４の乗算器として、前記プログラム可能集積回路デバイスの論理を構成することと、
前記第４の乗算器の出力を前記第３の乗算器の出力に加算するための加算器として、前記プログラム可能集積回路デバイスの論理を構成することと
をさらに含む、請求項９に記載の方法。
【請求項１４】
前記メモリは、異なる量だけシフトされた前記複数の回転因子を記憶するための２ポートメモリを含み、
固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記個別の回転因子のうちの１つを選択するための前記２ポートメモリの第１のアドレス入力として、前記プログラム可能集積回路デバイスの論理を構成することを含み、
固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成することは、前記個別の回転因子のうちの前記１つのシフトされたコピーのうちの１つを選択する、前記２ポートメモリの第２のアドレス入力として、前記差分を使用するように、前記プログラム可能集積回路デバイスの論理を構成することを含む、
請求項８に記載の方法。
【請求項１５】
プログラム可能集積回路デバイスであって、
離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段として構成可能な論理と、
浮動小数点加算段の出力を回転因子によって乗算するための固定小数点段として構成可能な論理であって、
前記固定小数点段は、
複数のセットの回転因子を記憶するためのメモリであって、前記セットのそれぞれは、異なる量だけシフトされた個別の回転因子のコピーを含む、メモリと、
前記浮動小数点段の出力の指数間の差分を判定し、前記差分を前記セットのそれぞれ内の前記個別の回転因子のコピーから選択するためのインデックスとして使用するための回路と
を含む、論理と
を含む、プログラム可能集積回路デバイス。
【請求項１６】
浮動小数点加算段として構成可能な論理は、前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器として構成可能な論理を含む、請求項１５に記載のプログラム可能集積回路デバイス。
【請求項１７】
前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器としての前記プログラム可能集積回路デバイスは、非正規化加算を行うように構成可能な論理を含み、
浮動小数点加算段として構成可能な論理は、前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器との非正規化出力を正規化するための正規化段として構成可能な論理を含む、
請求項１６に記載のプログラム可能集積回路デバイス。
【請求項１８】
前記正規化段として構成可能な論理は、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を正規化するための第１の正規化モジュールとして構成可能な論理と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を正規化するための第２の正規化モジュールとして構成可能な論理と
を含む、請求項１７に記載のプログラム可能集積回路デバイス。
【請求項１９】
前記正規化段として構成可能な論理は、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力のための第１のシフタとして構成可能な論理と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力のための第２のシフタとして構成可能な論理と、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力に関する第１の数の先行ゼロを判定するための第１の先行ゼロカウントモジュールとして構成可能な論理と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力に関する第２の数の先行ゼロを判定するための第２の先行ゼロカウントモジュールとして構成可能な論理と、
前記第１および第２の数の先行ゼロのうちのいずれが、より小さいかを判定し、前記第１および第２の数の先行ゼロのうちのより小さい方を、前記第１および第２のシフタのそれぞれに、前記仮数の実数部を加算するための少なくとも１つの加算器の出力と、前記仮数の虚数部を加算するための少なくとも１つの加算器の出力とがシフトされる、いくつかの場所として、適用するための比較器として構成可能な論理と、
を含む、請求項１７に記載のプログラム可能集積回路デバイス。
【請求項２０】
前記回転因子は、実数回転因子と、虚数回転因子とを含み、
固定小数点段として構成可能な論理は、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を実数回転因子によって乗算するための第１の乗算器として構成可能な論理と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を虚数回転因子によって乗算するための第２の乗算器として構成可能な論理と、
前記第２の乗算器の出力を前記第１の乗算器の出力から減算するための減算器として構成可能な論理と、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を虚数回転因子によって乗算するための第３の乗算器として構成可能な論理と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を実数回転因子によって乗算するための第４の乗算器として構成可能な論理と、
前記第４の乗算器の出力を前記第３の乗算器の出力に加算するための加算器として構成可能な論理と
をさらに含む、請求項１６に記載のプログラム可能集積回路デバイス。
【請求項２１】
前記メモリは、異なる量だけシフトされた前記複数の回転因子を記憶するための２ポートメモリを含み、
前記固定小数点段として構成可能な論理は、前記個別の回転因子のうちの１つを選択するための前記２ポートメモリの第１のアドレス入力として構成可能な論理を含み、
前記固定小数点段として構成可能な論理は、前記個別の回転因子のうちの前記１つのシフトされたコピーのうちの１つを選択する、前記２ポートメモリの第２のアドレス入力として、前記差分を使用するように構成可能な論理を含む、
請求項１５に記載のプログラム可能集積回路デバイス。
【請求項２２】
離散フーリエ変換演算を行うための回路として、プログラム可能集積回路デバイスを構成するための機械実行可能命令によってエンコードされる、機械可読データ記憶媒体であって、前記命令は、
前記離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記浮動小数点加算段の出力を回転因子によって乗算するための固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成するための命令であって、
前記固定小数点段は、
複数のセットの回転因子を記憶するためのメモリであって、前記セットのそれぞれは、異なる量だけシフトされた個別の回転因子のコピーを含む、メモリと、
前記浮動小数点段の出力の指数間の差分を判定し、前記差分を前記セットのそれぞれ内の前記個別の回転因子のコピーから選択するためのインデックスとして使用するための回路と
を含む、命令と
を含む、機械可読データ記憶媒体。
【請求項２３】
浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令を含む、請求項２２に記載の機械可読データ記憶媒体。
【請求項２４】
前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、非正規化加算を行うように、前記プログラム可能集積回路デバイスの論理を構成するための命令を含み、
浮動小数点加算段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記仮数の実数部を加算するための少なくとも１つの加算器と、前記仮数の虚数部を加算するための少なくとも１つの加算器との非正規化出力を正規化するための正規化段として、前記プログラム可能集積回路デバイスの論理を構成するための命令を含む、
請求項２３に記載の機械可読データ記憶媒体。
【請求項２５】
正規化段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を正規化するための第１の正規化モジュールとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を正規化するための第２の正規化モジュールとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と
を含む、請求項２４に記載の機械可読データ記憶媒体。
【請求項２６】
正規化段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力のための第１のシフタとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力のための第２のシフタとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力に関する第１の数の先行ゼロを判定するための第１の先行ゼロカウントモジュールとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力に関する第２の数の先行ゼロを判定するための第２の先行ゼロカウントモジュールとして、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記第１および第２の数の先行ゼロのうちのいずれが、より小さいかを判定し、前記第１および第２の数の先行ゼロのうちのより小さい方を、前記第１および第２のシフタのそれぞれに、前記仮数の実数部を加算するための少なくとも１つの加算器の出力と、前記仮数の虚数部を加算するための少なくとも１つの加算器の出力とが、シフトされる、いくつかの場所として、適用するための比較器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
を含む、請求項２４に記載の機械可読データ記憶媒体。
【請求項２７】
前記回転因子は、実数回転因子と、虚数回転因子とを含み、
固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を実数回転因子によって乗算するための第１の乗算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を虚数回転因子によって乗算するための第２の乗算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記第２の乗算器の出力を前記第１の乗算器の出力から減算するための減算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記仮数の実数部を加算するための少なくとも１つの加算器の出力を虚数回転因子によって乗算するための第３の乗算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記仮数の虚数部を加算するための少なくとも１つの加算器の出力を実数回転因子によって乗算するための第４の乗算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と、
前記第４の乗算器の出力を前記第３の乗算器の出力に加算するための加算器として、前記プログラム可能集積回路デバイスの論理を構成するための命令と
をさらに含む、請求項２３に記載の機械可読データ記憶媒体。
【請求項２８】
前記メモリは、異なる量だけシフトされた前記複数の回転因子を記憶するための２ポートメモリを含み、
固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記個別の回転因子のうちの１つを選択するための前記２ポートメモリの第１のアドレス入力として、前記プログラム可能集積回路デバイスの論理を構成することを含み、
固定小数点段として、前記プログラム可能集積回路デバイスの論理を構成するための命令は、前記個別の回転因子のうちの前記１つのシフトされたコピーのうちの１つを選択する、前記２ポートメモリの第２のアドレス入力として、前記差分を使用するように、前記プログラム可能集積回路デバイスの論理を構成することを含む、
請求項２２に記載の機械可読データ記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（発明の背景）
本発明は、集積回路デバイスにおいて、特に、プログラム可能論理デバイス（ＰＬＤ）等のプログラム可能集積回路デバイスにおいて、離散フーリエ変換演算を行うことに関する。
【背景技術】
【０００２】
離散フーリエ変換（ＤＦＴ）は、サンプリングされた信号内に含有される周波数を分析し、偏微分方程式を解き、大きな整数の畳み込みまたは乗算等、他の演算を行うために、信号処理用途において使用され得る、フーリエ変換の一種である。ＤＦＴは、高速フーリエ変換（ＦＦＴ）を構成するために使用することができる。加えて、より小さいＤＦＴは、より大きなＤＦＴを構成するために使用することができる。これは、個々のより小さいＤＦＴが、個々のＤＳＰブロックにおいて算出されることができるため、ＤＦＴを、特に、プログラム可能論理デバイス（ＰＬＤ）等の集積回路デバイス内の専用デジタル信号処理（ＤＳＰ）回路ブロックにおいて、ＦＦＴを計算するために有用なものにする。
【発明の概要】
【課題を解決するための手段】
【０００３】
（発明の概要）
本発明は、浮動小数点乗算演算を固定小数点演算と置換することによる、ＤＦＴ演算を行うために必要とされるリソースの減少に関する。これは、ＤＦＴ計算における回転因子の数が、比較的に小さく、相互の小ビット数内にあるため、行うことができる。したがって、浮動小数点乗算器を使用して、ＤＦＴを算出する代わりに、固定小数点乗算器を使用することができる。必要とされる精度は、各回転因子の複数のコピーを記憶することによって得られ、各コピーは、異なる量だけシフトされる。乗算されるべき値の指数間の差分は、適切にシフトされた回転因子を読み出すための回転因子記憶へのインデックスとして使用される。
【０００４】
したがって、本発明によると、離散フーリエ変換を行うための回路が提供される。回路は、離散フーリエ変換演算の入力値の仮数を加算するための浮動小数点加算段と、浮動小数点加算段の出力を回転因子で乗算するための固定小数点段と、を含む。固定小数点段は、複数のセットの回転因子を記憶するためのメモリであって、それらのセットはそれぞれ、異なる量だけシフトされた個別の回転因子のコピーを含む、メモリと、浮動小数点段の出力の指数間の差分を判定し、その差分をセットのそれぞれ内のその個別の回転因子のそれらのコピーから選択するためのインデックスとして使用するための回路と、を含む。
【０００５】
プログラム可能デバイス上のそのような回路を構成するための方法、そのように構成可能なプログラム可能デバイス、および方法を行うためのソフトウェアでエンコードされた機械可読データ記憶媒体もまた、提供される。
【０００６】
本発明のさらなる特徴、その性質、および種々の利点は、全体を通して、同一参照文字が同一部品を指す付随の図面と関連して検討される、以下の発明を実施するための形態を考慮することによって、明白となるであろう。
【図面の簡単な説明】
【０００７】
【図１】図１は、基数４の離散フーリエ変換の論理構造を示す。
【図２】図２は、図１の論理構造の周知の改良を示す。
【図３】図３は、本発明の一実施形態による、基数４の離散フーリエ変換の論理構造を示す。
【図４】図４は、本発明のある実施形態による、図３の論理構造の実装の簡略化されたブロック図である。
【図５】図５は、図４の実装と関連する、アドレスオフセットの計算の実装の簡略化されたブロック図である。
【図６】図６は、本発明の別の実施形態による、基数４の離散フーリエ変換の論理構造を示す。
【図７】図７は、本発明による方法を行うための１セットの機械実行可能命令でエンコードされた磁気データ記憶媒体の断面図である。
【図８】図８は、本発明による方法を行うための１セットの機械実行可能命令でエンコードされた光可読データ記憶媒体の断面図である。
【図９】図９は、本発明を組み込むプログラム可能論理デバイスを採用する、例証的システムの簡略化されたブロック図である。
【発明を実施するための形態】
【０００８】
基数４のＤＦＴは、４つの複素入力（Ｒ１，Ｉ１）、（Ｒ２，Ｉ２）、（Ｒ３，Ｉ３）、および（Ｒ４，Ｉ４）を有する。図１から分かるように、第１の二進数（｛１，１，１，１｝）の計算１００では、実数部はすべて、加算器１０１、１０２、１０３を使用して加算され、虚数部はすべて、加算器１１１、１１２、１１３を使用して加算される。ＤＦＴの本部分は、加算器のみ必要とする。実数出力１０４は、実数和１０３と実数回転因子１０７の積１０６と、虚数和１１３と虚数回転因子１１７の積１１６との間の差分１０５として、計算される。虚数出力１１４は、実数和１０３と虚数回転因子１１７の積１２６と、虚数和１１３と実数回転因子１０７の積１３６の和１１５として、計算される。乗算器１０６、１１６、１２６、１３６以外、演算は、加算器を使用して、行うことができる。
【０００９】
基数４のＤＦＴの付加的二進数は、｛１，−ｊ，−１，ｊ｝、｛１，−１，１，−１｝、および｛１，ｊ，−１，−ｊ｝を入力値に適用することによって、計算される。浮動小数点演算では、論理否定は、容易に実装される（例えば、符号ビットを反転することによって）。同様に、ｊによる乗算は、マルチプレクサならびに排他的論理和関数を使用して実装され得る、ある数の実数と虚数成分をスワッピングすることによって、達成される。したがって、付加的二進数は、これらの付加的関数が追加された、図１に類似する構造で行われてもよい（図示せず）。
【００１０】
基数１６のＤＦＴの場合、２つの基数４の段が、必要とされるであろう。第１の段の出力上の複素乗算器は、限定数の複素回転因子、すなわち、Ｗ０、Ｗ１、Ｗ２、Ｗ３、Ｗ４、Ｗ６、Ｗ９（式中、Ｗｘ＝ｅ−２ｊπｘ／１６）が適用されるであろう。
【００１１】
図１に示される演算子は、浮動小数点計算のためのＩＥＥＥ７５４−１９８５規格に準拠した浮動小数点演算子であってもよい。図２は、図１の算出が、同時係属中の本発明の譲受人に譲渡された２００７年１月２２日出願の米国特許出願第１１／６２５，６５５号に説明されるような浮動小数点演算子を使用することによって、より少ないリソースを使用してどのように算出され得るかを示しており、浮動小数点数は、ほとんどの場合、非正規化形式に維持され、（ａ）前述のＩＥＥＥ７５４−１９８５規格に準拠した出力のために、または（ｂ）精度の損失が生じ得る場合、正規化される。
【００１２】
したがって、加算２０１、２０２、２０３、２１１、２１２、２１３は、浮動小数点演算子であるが、値は、それらの演算の間、正規化されない。しかしながら、結果として生じた和は、乗算段２０５の前に、２０６、２１６において、正規化される。乗算段２０５内では、乗算器２１５、２２５、２３５、２４５、加算器２５５、および減算器２６５は、浮動小数点演算子であるが、値は、それらの演算の間、正規化されない。しかしながら、結果は、２０４、２１４における出力のために、２０７、２１７において、正規化される。これは、図１の実装と比較して、約５０％のリソースの使用の削減をもたらし得る。
【００１３】
正規化ブロック２０６、２１６後、実数および虚数仮数は両方とも、２倍または相互の倍数以内にあるが、その指数は、異なってもよいことが観察され得る。次のＤＦＴブロック前の複素乗算のための回転因子も同様に、小値数を有する可能性が高いであろう。例えば、２つの基数４のＤＦＴ段を有する基数１６のＤＦＴの場合、実数および虚数回転因子を構成する値の小数の規模は、１、０．９２３９、０．７０７１、および０．３８２７であって、すべて、二進数として表される時、相互の２ビット以内である。
【００１４】
その結果、乗算器が、若干、浮動小数点仮数の精度を上回る場合、複素乗算は、ほとんどの場合、固定小数点演算を使用して、実装し、付加的リソースを節約することができる。
【００１５】
本発明による実施形態では、通常、単精度浮動小数点乗算のために使用される、３６ビット乗算器が、複数の回転因子の記憶のためのメモリとともに、利用可能である。本発明の本実施形態によると、ＤＦＴ計算のための回転因子は、異なる量だけシフトされた複数の固定小数点コピーとして、各回転因子を記憶することによって、固定小数点に変換されてもよい。ＤＦＴ入力は、計算に対する唯一の浮動小数点入力のままである。入力と回転因子との間の指数差分は、いかなる精度の損失も伴うことなく、回転因子メモリから適切にシフトされた回転因子を検索するためのインデックスとして、判定および使用することができる。
【００１６】
本論理的構成３００は、図３に示される。図２の場合のように、加算２０１、２０２、２０３、２１１、２１２、２１３は、浮動小数点演算子であるが、値は、それらの演算の間、正規化されない。再び、結果として生じた和は、乗算段３０５の前に、２０６、２１６において、正規化される。乗算段３０５では、乗算器３１５、３２５、３３５、３４５、加算器３５５、および減算器３６５は、固定小数点演算子である。乗算器３１５、３２５、３３５、３４５の出力は、加算器３５５および減算器３６５によって加算または減算され得るように、その相対値を相互に整列させる。
【００１７】
乗算器出力の整列は、回転因子をシフトすることによって、達成されてもよい。各回転因子のシフトの量は、乗算器入力の指数間の差分となるであろう。一実施形態では、各乗算器対（すなわち、実数出力を生成する対と、虚数出力を生成する対）の場合、一方の回転因子は、シフトされず、他方は、シフトされるであろう。論理的に、これは、図３に示されるシフタによって表され得るが、一物理的実装は、後述のように、図４に示される。
【００１８】
より大きな出力値は、１に近い（すなわち、１の２ビットの規模以内の）回転因子によって乗算される、正規化されたデータ値となるであろう。したがって、出力に必要とされる可能性として考えられる正規化が存在するであろうが、前述のように、基数４の小区分に分解される基数１６のＤＦＴの場合、最大３ビットの正規化が存在するであろう。出力指数３０８は、出力仮数正規化値によって調節され得る、正規化２０６、２１６後の最大指数から計算されてもよい。任意の調節に先立った指数値もまた、３０９において、適切にシフトされた回転因子を選択するためのインデックスとして使用される。
【００１９】
論理構成３００は、多くの論理を節約しないであろうが、待ち時間を短縮させ得る。しかしながら、論理構成３００の物理的実施形態４００が、図４に示される。非正規化浮動小数点加算器２０１、２０２、２０３、２１１、２１２、２１３、正規化モジュール２０６、２１６、固定小数点乗算器３１５、３２５、３３５、３４５、加算器３５５、および減算器３６５の配列は、論理構成３００と同一である。
【００２０】
メモリ４０１は、実数回転因子のために提供される一方、メモリ４０２は、虚数回転因子のために提供される。ほとんどの大きなＤＦＴ構成、例えば、基数１６のＤＦＴ内の第１の段のための１０個の回転因子（そのうち４個は、一意であってもよい）、および基数６４のＤＦＴ内の第１の段のための５１個の回転因子（そのうち約３５個は、一意であってもよい）に対する限定数の回転因子のため、シフトはすべて、事前に算出され、メモリ内に記憶することができる。例えば、Ａｌｔｅｒａ  Ｃｏｒｐｏｒａｔｉｏｎから市販のプログラム可能論理デバイスのＳＴＲＡＴＩＸ（Ｒ）ファミリーのプログラム可能論理デバイス等の集積回路デバイスでは、十分な数の内蔵メモリモジュールが、本機能を果たすために、デバイス上に提供される。メモリ４０１、４０２はそれぞれ、必要に応じて、複数のそのような内蔵メモリモジュールを含んでもよい。しかしながら、例証を容易にするために、メモリ４０１、４０２はそれぞれ、単一メモリモジュールとして、図４に示される。
【００２１】
示される実施例では、メモリ４０１、４０２はそれぞれ、デュアルポートメモリである。故に、それぞれ、個別の対のアドレス４１１、４２１および４１２、４２２によって、アドレスされてもよい。各アドレス対の要素は、単一アドレスの上位および低位部分と見なされてもよく、低位アドレス部分４１１、４１２は、いくつかの回転因子のうちのいずれがアクセスされているかを識別し、上位アドレス部分４２１、４２２は、その回転因子のシフトされたバージョンのうちのいずれがアクセスされているかを識別する。アドレスの生成は、以下のように行われる。
【００２２】
実数出力は、２つの乗算、すなわち、実数データ×実数回転因子および虚数データ×虚数回転因子を有する。アドレス１は、この場合、実数および虚数回転因子にアクセスするために使用されるであろう。
【００２３】
アドレス１の実数オフセット（実数回転因子メモリに対するオフセット）を計算するためには、実数データの指数が、虚数データの指数から減算される。この数が、ゼロまたは正数（虚数指数＞実数指数）である場合、これが、オフセット値である（かつ、シフト値でもある）。この数が、負数（実数指数＞虚数指数）である場合、この数は、ゼロにされる。
【００２４】
アドレス１の虚数オフセット（虚数回転因子メモリに対するオフセット）を計算するためには、虚数データの指数が、実数データの指数から減算される。この数が、ゼロまたは正数（実数指数＞虚数指数）である場合、これが、オフセット値である（かつ、シフト値でもある）。この数が、負数（虚数指数＞実数指数）である場合、この数は、ゼロにされる。
【００２５】
虚数出力は、２つの乗算、すなわち、実数データ×虚数回転因子および虚数データ×実数回転因子を有する。アドレス２は、この場合、実数および虚数回転因子にアクセスするために使用されるであろう。
【００２６】
アドレス２の実数オフセット（虚数回転因子メモリに対するオフセット）を計算するためには、実数データの指数が、虚数データの指数から減算される。この数が、ゼロまたは正数（虚数指数＞実数指数）である場合、これが、オフセット値である（かつ、シフト値でもある）。この数が、負数（実数指数＞虚数指数）である場合、この数は、ゼロにされる。
【００２７】
アドレス２の虚数オフセット（実数回転因子メモリに対するオフセット）を計算するためには、虚数データの指数が、実数データの指数から減算される。この数が、ゼロまたは正数（実数指数＞虚数指数）である場合、これが、オフセット値である（また、シフト値でもある）。この数が、負数（虚数指数＞実数指数）である場合、この数は、ゼロにされる。
【００２８】
以上のように、アドレス１およびアドレス２の両方の計算は、同一である。実数オフセットは、実数回転因子メモリの読み出しアドレス１および虚数回転因子メモリの読み出しアドレス２に移動する。虚数オフセットは、実数回転因子メモリの読み出しアドレス２および虚数回転因子メモリの読み出しアドレス１に移動する。実数および虚数オフセットを算出するための論理５００は、図５に示される。
【００２９】
以上のように、虚数オフセット５０１は、５０３において、虚数データの指数５０５を実数データの指数５０６から減算することによって、算出される。結果５１３は、５０８において、その最上位ビット５２３の逆数５０７とＡＮＤで連結され、結果５１３が、負数である場合、結果５０１をゼロにする。同様に、実数オフセット５０２は、５５３において、実数データの指数５０６を虚数データの指数５０５から減算することによって、算出される。結果５６３は、５５８において、その最上位ビット５７３の逆数５５７とＡＮＤで連結され、結果５６３が、負数である場合、結果５０２をゼロにする。
【００３０】
図６に示される代替実施形態６００では、図４におけるように、完全正規化２０６、２１６の代わりに、実数入力６０１および虚数入力６１１を正規化するために必要とされる個別のシフト量が、先行ゼロカウントモジュール６０２、６１２によって判定され、より小さいシフト（すなわち、値６０１、６１１の大きい方を正規化するために使用されるシフト）が、６０３において、先行ゼロカウントを比較することによって選択されるように、入力６０１、６１１の両方を左シフトさせるために、シフタ６０４、６１４において使用される。したがって、入力６０１、６１１の一方は、その完全規模を留保するであろうが、入力６０１、６１１の他方は、その部分的規模のみ留保するであろう。しかしながら、前述のように、回転因子はすべて、ほぼ同一の規模であるため、前述のＳＴＲＡＴＩＸ（Ｒ）ファミリーのプログラム可能論理デバイス等のデバイスを想定すると、乗算器６１５、６２５、６３５、６４５が、３６ビット幅である時、単精度（２３ビット仮数）値の正確性は、右シフトされる場合でも、維持することができる。
【００３１】
本発明の実装の実施例として、１ＫストリーミングＦＦＴを検討する。従来、これは、５つの基数４の段を使用して実装され、そのうちの最初の４つは、複素乗算器を必要とするであろう。２５６個の要素、合計数千の回転因子を必要とするであろう。
【００３２】
本発明を使用することによって、１ＫストリーミングＦＦＴは、基数１６の段、基数４の段、および基数１６の段を使用して実装され得る。第１の基数１６段は、出力上の標準的複素乗算器とともに、最適化された内部複素乗算器を使用するであろう。代替として、最適化された複素乗算器は、出力上で使用され得る。６４個の複素回転因子の場合、これは、シフトのすべてが、事前に計算されている時、約（３２または３６）×６４＝約２，０００個の複素回転因子メモリ場所を必要とするであろう。次の基数４の段は、シフトのすべてが、事前に計算されている時、１６個の回転因子のみ、すなわち、合計約（３２または３６）×１６＝約５１２個の複素回転因子メモリ場所が存在するであろうため、最適化された複素乗算器を使用し得る。最後の基数１６の段は、第１の段として、ほぼ同一数の回転因子とともに、内部最適化された複素乗算器を使用するであろう。
【００３３】
ＤＦＴを行うように、プログラム可能デバイスをプログラムするための本発明による方法を実行するための命令は、前述のように、加算および減算演算を行うように、ＰＬＤまたは他のプログラム可能デバイスをプログラミングあるいは構成するための本発明の方法を実装するために、好適なコンピュータまたは類似デバイスによって実行されるように、機械可読媒体上でエンコードされてもよい。例えば、パーソナルコンピュータは、ＰＬＤを接続することができる、インターフェースを備えてもよく、パーソナルコンピュータは、Ａｌｔｅｒａ  Ｃｏｒｐｏｒａｔｉｏｎ（ＳａｎＪｏｓｅ、Ｃａｌｉｆｏｒｎｉａ）から市販のＱＵＡＲＴＵＳ（Ｒ）ＩＩソフトウェア等、好適なソフトウェアツールを使用して、ＰＬＤをプログラムするために、ユーザによって使用することができる。
【００３４】
図７は、前述のパーソナルコンピュータ、または他のコンピュータ、または類似デバイス等のシステムによって実行することができる、機械実行可能プログラムでエンコードされ得る、磁気データ記憶媒体８００の断面を表す。媒体８００は、フロッピー（登録商標）ディスケットまたはハードディスク、あるいは従来のものであり得る、好適な基板８０１を有する、磁気テープ、および片側または両側に、その極性または配向を磁気的に改変することができる、磁気領域（不可視）を含有する、従来のものであり得る、好適なコーティング８０２であり得る。磁気テープの場合を除き、媒体８００はまた、ディスクドライブまたは他のデータ記憶デバイスの軸を受容するための開口部（図示せず）を有してもよい。
【００３５】
媒体８００のコーティング８０２の磁気領域は、本発明に従って、該当する場合、その特殊処理ブロックを含むＰＬＤの適切な部分を構成するために、プログラムされるべきＰＬＤが挿入され得るソケットまたは周辺付属装置を有する、パーソナルコンピュータ、または他のコンピュータ、または類似システム等のプログラムミングシステムによる実行のために、機械実行可能プログラムを、従来のものであり得る態様で、エンコードするように極性化または配向される。
【００３６】
図８は、また、前述のパーソナルコンピュータ、または他のコンピュータ、または類似デバイス等のシステムによって、実行することができる、そのような機械実行可能プログラムでエンコードされ得る、光可読データ記憶媒体８１０の断面を示す。媒体８１０は、従来のコンパクトディスク読取専用メモリ（ＣＤ−ＲＯＭ）、またはデジタルビデオディスク読取専用メモリ（ＤＶＤ−ＲＯＭ）、またはＣＤ−Ｒ、ＣＤ−ＲＷ、ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ、またはＤＶＤ−ＲＡＭ等の書換可能媒体、または光可読および磁気光書換可能である、磁気光ディスクであり得る。媒体８１０は、好ましくは、従来のものであり得る、好適な基板８１１と、通常、基板８１１の片側または両側の、従来のものであり得る、好適なコーティング８１２と、を有する。
【００３７】
ＣＤベースまたはＤＶＤベースの媒体の場合、周知のように、コーティング８１２は、反射性であって、１つ以上の層上に配列される、複数のピット８１３で刻印され、機械実行可能プログラムをエンコードする。ピットの配列は、レーザ光をコーティング８１２の表面に反射させることによって、読み出される。好ましくは、実質的に、透明である、保護コーティング８１４が、コーティング８１２の上部に提供される。
【００３８】
磁気光ディスクの場合、周知のように、コーティング８１２は、ピット８１３を有していないが、極性または配向が、レーザ（図示せず）によって等、ある温度を上回って加熱されると、磁気的に変化し得る、複数の磁気領域を有する。領域の配向は、コーティング８１２から反射されたレーザ光の偏光を測定することによって、読み出すことができる。本領域の配列は、前述のように、プログラムをエンコードする。
【００３９】
本発明に従ってプログラムされたＰＬＤ９０は、電子デバイスの多くの種類において使用されてもよい。可能性のある使用の１つは、図９に示されるデータ処理システム９００内である。データ処理システム９００は、プロセッサ９０１、メモリ９０２、Ｉ／Ｏ回路９０３、および周辺デバイス９０４構成可能のうちの１つ以上を含んでもよい。これらの構成可能は、システムバス９０５によって、ともに連結され、エンドユーザシステム９０７内に含有される、回路基板９０６上に取り込まれる。
【００４０】
システム９００は、コンピュータネットワーキング、データネットワーキング、計器、ビデオ処理、デジタル信号処理、あるいはプログラム可能または再プログラム可能論理を使用する利点が、望ましい任意の他の用途等、種々の用途で使用することができる。ＰＬＤ９０は、種々の異なる論理関数を行うために使用することができる。例えば、ＰＬＤ９０は、プロセッサ９０１と協働する、プロセッサまたはコントローラとして、構成することができる。ＰＬＤ９０はまた、システム９００内の共有リソースへのアクセスを調停するための調停回路として、使用されてもよい。さらに別の実施例では、ＰＬＤ９０は、プロセッサ９０１とシステム９００内の他の構成可能のうちの１つとの間のインターフェースとして、構成することができる。システム９００は、例示に過ぎず、本発明の真の範囲および精神は、以下の請求項によって示されるべきであることに留意されたい。
【００４１】
種々の技術を使用して、前述のように、本発明を組み込む、ＰＬＤ９０を実行するうことができる。
【００４２】
前述は、本発明の原理の例証に過ぎず、種々の修正が、本発明の範囲および精神から逸脱することなく、当業者によって行うことができることを理解されるであろう。例えば、本発明の種々の要素は、任意の所望の数および／または配列において、ＰＬＤ上に提供することができる。当業者は、本発明が、制限ではなく、例証目的のために提示される、説明された実施形態以外によって、実践することができ、本発明が、以下の請求項によってのみ、制限されることを理解するであろう。
【図７】
2013521575.tif 000003
【図８】
2013521575.tif 000004
【図１】
2013521575.tif 000005
【図２】
2013521575.tif 000006
【図３】
2013521575.tif 000007
【図４】
2013521575.tif 000008
【図５】
2013521575.tif 000009
【図６】
2013521575.tif 000010
【図９】
2013521575.tif 000011
【国際調査報告】
2013521575.tif 000012
2013521575.tif 000013