(57)【特許請求の範囲】
【請求項１】
複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算手段と、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算手段と、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算手段と、を含み、
前記第一加算手段は、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで前記乗算手段に出力し、
前記乗算手段は、前記前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで前記第二加算手段に出力し、
前記第二加算手段は、前記乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記第一加算手段は、
前記第一タイミングで前記複数のデータを受け付けると、前記制御信号に従って、前記複数のデータ同士を選択的に加算する、もしくは、前記複数のデータをそのまま出力する第一演算手段と、
前記第一タイミングよりも遅く前記第二タイミングよりも早い第四タイミングで入力されたデータを、前記制御信号に従って、選択的に並べ替える、もしくは、そのまま出力する並び替え手段と、
前記第四タイミングよりも遅く前記第二タイミングよりも早い第五タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第二演算手段と、
前記第五タイミングよりも遅く前記第二タイミングよりも早い第六タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第三演算手段と、を有し、
前記第一演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第四タイミングで前記並び替え手段に出力し、
前記並び替え手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第五タイミングで前記第二演算手段に出力し、
前記第二演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第六タイミングで前記第三演算手段に出力し、
前記第三演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第二タイミングで前記乗算手段に出力する、離散フーリエ変換装置。
【請求項２】
前記乗算手段は、
前記ポイント数ごとに、当該ポイント数に対応する前記離散フーリエ変換用の乗算係数および当該ポイント数に対応する前記離散逆フーリエ変換用の乗算係数を格納する記憶手段と、
前記制御信号が示すポイント数および処理に対応する乗算係数を、前記記憶手段から読み出す読出し手段と、
前記第一加算手段の出力に、前記読出し手段が読み出した乗算係数を乗算する第一乗算手段と、
前記第一乗算手段の乗算結果に対し、前記制御信号に従って、選択的に純虚数を乗算する第二乗算手段と、を有する、請求項１に記載の離散フーリエ変換装置。
【請求項３】
複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算手段と、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算手段と、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算手段と、を含み、
前記第一加算手段は、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで前記乗算手段に出力し、
前記乗算手段は、前記前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで前記第二加算手段に出力し、
前記第二加算手段は、前記乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記乗算手段は、
前記ポイント数ごとに、当該ポイント数に対応する前記離散フーリエ変換用の乗算係数および当該ポイント数に対応する前記離散逆フーリエ変換用の乗算係数を格納する記憶手段と、
前記制御信号が示すポイント数および処理に対応する乗算係数を、前記記憶手段から読み出す読出し手段と、
前記第一加算手段の出力に、前記読出し手段が読み出した乗算係数を乗算する第一乗算手段と、
前記第一乗算手段の乗算結果に対し、前記制御信号に従って、選択的に純虚数を乗算する第二乗算手段と、を有する離散フーリエ変換装置。
【請求項４】
前記第二加算手段は、
前記第三タイミングで前記乗算手段の出力を受け付けると、前記制御信号に従って、前記乗算手段の出力同士を選択的に加算する、もしくは、前記乗算手段の出力をそのまま出力する第四演算手段と、
前記第三タイミングよりも遅い第七タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、そのまま出力する、もしくは、選択的に加算した加算結果に選択的に純虚数を乗算する第五演算手段と、
前記第七タイミングよりも遅い第八タイミングで入力されたデータを、前記制御信号に従って、選択的に並べ替える、もしくは、そのまま出力するデータ並び替え手段と、
前記第八タイミングよりも遅い第九タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第六演算手段と、を有し、
前記第四演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第七タイミングで前記第五演算手段に出力し、
前記第五演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第八タイミングで前記データ並び替え手段に出力し、
前記データ並び替え手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第九タイミングで前記第六演算手段に出力し、
前記第六演算手段は、自己の出力を、前記複数のデータに対して前記制御信号にて示されたポイント数の前記処理を実行した結果として出力する、請求項１から３のいずれか１項に記載の離散フーリエ変換装置。
【請求項５】
複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算手段と、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算手段と、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算手段と、を含み、
前記第一加算手段は、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで前記乗算手段に出力し、
前記乗算手段は、前記前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで前記第二加算手段に出力し、
前記第二加算手段は、前記乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記第二加算手段は、
前記第三タイミングで前記乗算手段の出力を受け付けると、前記制御信号に従って、前記乗算手段の出力同士を選択的に加算する、もしくは、前記乗算手段の出力をそのまま出力する第四演算手段と、
前記第三タイミングよりも遅い第七タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、そのまま出力する、もしくは、選択的に加算した加算結果に選択的に純虚数を乗算する第五演算手段と、
前記第七タイミングよりも遅い第八タイミングで入力されたデータを、前記制御信号に従って、選択的に並べ替える、もしくは、そのまま出力するデータ並び替え手段と、
前記第八タイミングよりも遅い第九タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第六演算手段と、を有し、
前記第四演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第七タイミングで前記第五演算手段に出力し、
前記第五演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第八タイミングで前記データ並び替え手段に出力し、
前記データ並び替え手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第九タイミングで前記第六演算手段に出力し、
前記第六演算手段は、自己の出力を、前記複数のデータに対して前記制御信号にて示されたポイント数の前記処理を実行した結果として出力する、離散フーリエ変換装置。
【請求項６】
複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置での離散フーリエ変換・離散逆フーリエ変換方法であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算ステップと、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算ステップと、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算ステップと、を含み、
前記第一加算ステップでは、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで出力し、
前記乗算ステップでは、前記前段加算処理の結果を前記第二タイミングで受け付け、当該前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで出力し、
前記第二加算ステップでは、前記乗算処理の結果を前記第三タイミングで受け付け、当該乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記第一加算ステップは、
前記第一タイミングで前記複数のデータを受け付けると、前記制御信号に従って、前記複数のデータ同士を選択的に加算する、もしくは、前記複数のデータをそのまま出力する第一演算ステップと、
前記第一タイミングよりも遅く前記第二タイミングよりも早い第四タイミングで入力されたデータを、前記制御信号に従って、選択的に並べ替える、もしくは、そのまま出力する並び替えステップと、
前記第四タイミングよりも遅く前記第二タイミングよりも早い第五タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第二演算ステップと、
前記第五タイミングよりも遅く前記第二タイミングよりも早い第六タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第三演算ステップと、を有し、
前記第一演算ステップでは、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第四タイミングで出力し、
前記並び替えステップでは、前記第一演算ステップでの出力を前記第四タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第五タイミングで出力し、
前記第二演算ステップでは、前記並び替えステップでの出力を前記第五タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第六タイミングで出力し、
前記第三演算ステップは、前記第二演算ステップでの出力を前記第六タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第二タイミングで出力し、
前記乗算ステップでは、前記第三演算ステップでの出力を、前記前段加算処理の結果として前記第二タイミングで受け付け、当該前段加算処理の結果に対して前記乗算処理を実行する、離散フーリエ変換・離散逆フーリエ変換方法。
【請求項７】
前記乗算ステップは、
前記ポイント数ごとに、当該ポイント数に対応する前記離散フーリエ変換用の乗算係数および当該ポイント数に対応する前記離散逆フーリエ変換用の乗算係数を記憶手段に格納する記憶ステップと、
前記制御信号が示すポイント数および処理に対応する乗算係数を、前記記憶手段から読み出す読出しステップと、
前記第一加算ステップでの出力に、前記読み出された乗算係数を乗算する第一乗算ステップと、
前記乗算の結果に対し、前記制御信号に従って、選択的に純虚数を乗算する第二乗算ステップと、を有する請求項６に記載の離散フーリエ変換・離散逆フーリエ変換方法。
【請求項８】
複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置での離散フーリエ変換・離散逆フーリエ変換方法であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算ステップと、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算ステップと、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算ステップと、を含み、
前記第一加算ステップでは、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで出力し、
前記乗算ステップでは、前記前段加算処理の結果を前記第二タイミングで受け付け、当該前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで出力し、
前記第二加算ステップでは、前記乗算処理の結果を前記第三タイミングで受け付け、当該乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記乗算ステップは、
前記ポイント数ごとに、当該ポイント数に対応する前記離散フーリエ変換用の乗算係数および当該ポイント数に対応する前記離散逆フーリエ変換用の乗算係数を記憶手段に格納する記憶ステップと、
前記制御信号が示すポイント数および処理に対応する乗算係数を、前記記憶手段から読み出す読出しステップと、
前記第一加算ステップでの出力に、前記読み出された乗算係数を乗算する第一乗算ステップと、
前記乗算の結果に対し、前記制御信号に従って、選択的に純虚数を乗算する第二乗算ステップと、を有する離散フーリエ変換・離散逆フーリエ変換方法。
【請求項９】
前記第二加算ステップは、
前記第三タイミングで前記乗算ステップでの出力を受け付けると、前記制御信号に従って、当該出力同士を選択的に加算する、もしくは、当該出力をそのまま出力する第四演算ステップと、
前記第三タイミングよりも遅い第七タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、そのまま出力する、もしくは、選択的に加算した加算結果に選択的に純虚数を乗算する第五演算ステップと、
前記第七タイミングよりも遅い第八タイミングで入力されたデータを、前記制御信号に従って、選択的に並べ替える、もしくは、そのまま出力するデータ並び替えステップと、
前記第八タイミングよりも遅い第九タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第六演算ステップと、を有し、
前記第四演算ステップでは、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第七タイミングで出力し、
前記第五演算ステップでは、前記第四演算ステップでの出力を前記第七タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第八タイミングで出力し、
前記データ並び替えステップでは、前記第五演算ステップでの出力を前記第八タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第九タイミングで出力し、
前記第六演算ステップでは、前記データ並び替えステップでの出力を前記第九タイミングで受け付け、自己の出力を前記複数のデータに対して前記処理を実行した結果として出力する、請求項６から８のいずれか１項に記載の離散フーリエ変換・離散逆フーリエ変換方法。
【請求項１０】
複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置での離散フーリエ変換・離散逆フーリエ変換方法であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算ステップと、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算ステップと、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算ステップと、を含み、
前記第一加算ステップでは、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで出力し、
前記乗算ステップでは、前記前段加算処理の結果を前記第二タイミングで受け付け、当該前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで出力し、
前記第二加算ステップでは、前記乗算処理の結果を前記第三タイミングで受け付け、当該乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記第二加算ステップは、
前記第三タイミングで前記乗算ステップでの出力を受け付けると、前記制御信号に従って、当該出力同士を選択的に加算する、もしくは、当該出力をそのまま出力する第四演算ステップと、
前記第三タイミングよりも遅い第七タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、そのまま出力する、もしくは、選択的に加算した加算結果に選択的に純虚数を乗算する第五演算ステップと、
前記第七タイミングよりも遅い第八タイミングで入力されたデータを、前記制御信号に従って、選択的に並べ替える、もしくは、そのまま出力するデータ並び替えステップと、
前記第八タイミングよりも遅い第九タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第六演算ステップと、を有し、
前記第四演算ステップでは、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第七タイミングで出力し、
前記第五演算ステップでは、前記第四演算ステップでの出力を前記第七タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第八タイミングで出力し、
前記データ並び替えステップでは、前記第五演算ステップでの出力を前記第八タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第九タイミングで出力し、
前記第六演算ステップでは、前記データ並び替えステップでの出力を前記第九タイミングで受け付け、自己の出力を前記複数のデータに対して前記処理を実行した結果として出力する、離散フーリエ変換・離散逆フーリエ変換方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、離散フーリエ変換装置および離散フーリエ変換方法に関し、特には、点数（ポイント数）が異なる離散フーリエ変換（DFT）を実行できる離散フーリエ変換装置および離散フーリエ変換方法に関する。
【背景技術】
【０００２】
周波数領域の信号を時間領域の信号に変換する処理と、時間領域の信号を周波数領域の信号に変換する処理と、を含む変復調処理を行う無線通信信号処理装置が知られている。変復調処理の例としては、LTE（Long Term Evolution）で用いられる離散フーリエ変換（DFT）と離散逆フーリエ変換（IDFT）とを行う処理が挙げられる。
【０００３】
一般に、DFTは以下の式で表わされる。
【０００４】
【数１】
0005493646.tif 000002
【０００５】
ここで、Xは入力、Yは出力、NはDFTの点数である。また、
【０００６】
【数２】
0005493646.tif 000003
【０００７】
である。
【０００８】
DFTを高速に実行する手法として、ある点数のDFTを、その点数より少ない点数のDFT処理の組み合わせとして処理するウィノグラードの方法がある。
【０００９】
図４９は、ウィノグラードの方法を用いて、１５点DFTを３点及び５点のDFTに分割して処理する手法を示した図である。
【００１０】
ウィノグラードの方法によれば、１５点のDFTは、３点DFTの前段演算部、５点DFTの前段演算部、乗算段、５点DFTの後段演算部、及び３点DFTの後段演算部から構成することができる。
【００１１】
まず、３点DFTの前段演算部が、X(k)で示される入力データに対し、入力データ同士の加算処理を行う。
【００１２】
次に、３点DFTの前段演算部は、加算処理結果を５点DFTの前段演算部に出力し、５点DFTの前段演算部が、３点DFTの前段演算部からの加算処理結果について加算処理を行う。
【００１３】
次に、５点DFTの前段演算部は、加算処理結果を乗算段に送り、乗算段は、５点DFTの前段演算部からの加算処理結果と、あらかじめ用意しておいた乗算係数と、の乗算を行う。
【００１４】
次に、乗算段は、乗算結果を５点DFTの後段演算部に送り、５点DFTの後段演算部は、入力されたデータ同士の加算処理を行う。
【００１５】
最後に、５点DFTの後段演算部は、加算処理結果を３点DFTの後段演算部に送り、３点DFTの後段演算部が、入力されたデータ同士の加算処理を行い、結果を出力する。
【００１６】
ウィノグラードの方法を修正した手法とアーキテクチャがいくつか提案されている。
【００１７】
特許文献１には、デジタルチャネライザで用いられるDFTを効率よく処理するためのアーキテクチャが提案されている。特許文献１に開示の方法では、DFT以後の処理において、不必要なDFT出力を計算するDFT回路を削減することによって、後段演算部の加算器が削減されている。
【００１８】
また、特許文献２には、特定のポイント数kのFFT回路がL個並列に配置され、k、2*k、．．、L*kポイントのいずれのFFTも行えるサイズ可変離散フーリエ変換処理装置が記載されている。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】特開２０００−２５２９３４号公報
【特許文献２】特開２０００−１２３０００号公報
【発明の概要】
【発明が解決しようとする課題】
【００２０】
特許文献１に開示されたDFT処理方法は、ポイント数に対して汎用性がなく、複数種類のポイント数のフーリエ変換に対応するためには、ポイント数ごとに、個別にDFT回路を設計しなければならない。このため、ポイント数の種類が増加するほど、DFT回路を構成する加算器および乗算器の個数が増加し、回路規模が大きくなってしまうという課題がある。また、DFTの点数毎に個別に回路を設計しなければならないため、設計に時間がかかってしまう。
【００２１】
特許文献２に開示されたサイズ可変離散フーリエ変換処理装置は、ポイント数kのFFT回路をL個用いることによって、L種類のポイント数のフーリエ変換に対応している。このため、ポイント数の種類が増加するほど、DFT回路を構成する加算器および乗算器の個数が増加し、回路規模が大きくなってしまうという課題がある。
【００２２】
つまり、特許文献１、２に開示された技術では、ポイント数の種類が増加するほど、DFT回路を構成する加算器および乗算器の個数が増加し、回路規模が大きくなってしまうという課題がある。
【００２３】
本発明の目的は、上記課題を解決可能な離散フーリエ変換装置および離散フーリエ変換方法を提供することである。
【課題を解決するための手段】
【００２４】
本発明の離散フーリエ変換装置は、  複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算手段と、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算手段と、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算手段と、を含み、
前記第一加算手段は、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで前記乗算手段に出力し、
前記乗算手段は、前記前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで前記第二加算手段に出力し、
前記第二加算手段は、前記乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記第一加算手段は、
前記第一タイミングで前記複数のデータを受け付けると、前記制御信号に従って、前記複数のデータ同士を選択的に加算する、もしくは、前記複数のデータをそのまま出力する第一演算手段と、
前記第一タイミングよりも遅く前記第二タイミングよりも早い第四タイミングで入力されたデータを、前記制御信号に従って、選択的に並べ替える、もしくは、そのまま出力する並び替え手段と、
前記第四タイミングよりも遅く前記第二タイミングよりも早い第五タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第二演算手段と、
前記第五タイミングよりも遅く前記第二タイミングよりも早い第六タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第三演算手段と、を有し、
前記第一演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第四タイミングで前記並び替え手段に出力し、
前記並び替え手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第五タイミングで前記第二演算手段に出力し、
前記第二演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第六タイミングで前記第三演算手段に出力し、
前記第三演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第二タイミングで前記乗算手段に出力する。また、
本発明の離散フーリエ変換装置は、複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算手段と、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算手段と、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算手段と、を含み、
前記第一加算手段は、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで前記乗算手段に出力し、
前記乗算手段は、前記前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで前記第二加算手段に出力し、
前記第二加算手段は、前記乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記乗算手段は、
前記ポイント数ごとに、当該ポイント数に対応する前記離散フーリエ変換用の乗算係数および当該ポイント数に対応する前記離散逆フーリエ変換用の乗算係数を格納する記憶手段と、
前記制御信号が示すポイント数および処理に対応する乗算係数を、前記記憶手段から読み出す読出し手段と、
前記第一加算手段の出力に、前記読出し手段が読み出した乗算係数を乗算する第一乗算手段と、
前記第一乗算手段の乗算結果に対し、前記制御信号に従って、選択的に純虚数を乗算する第二乗算手段と、を有する。また、
本発明の離散フーリエ変換装置は、複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算手段と、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算手段と、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算手段と、を含み、
前記第一加算手段は、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで前記乗算手段に出力し、
前記乗算手段は、前記前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで前記第二加算手段に出力し、
前記第二加算手段は、前記乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記第二加算手段は、
前記第三タイミングで前記乗算手段の出力を受け付けると、前記制御信号に従って、前記乗算手段の出力同士を選択的に加算する、もしくは、前記乗算手段の出力をそのまま出力する第四演算手段と、
前記第三タイミングよりも遅い第七タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、そのまま出力する、もしくは、選択的に加算した加算結果に選択的に純虚数を乗算する第五演算手段と、
前記第七タイミングよりも遅い第八タイミングで入力されたデータを、前記制御信号に従って、選択的に並べ替える、もしくは、そのまま出力するデータ並び替え手段と、
前記第八タイミングよりも遅い第九タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第六演算手段と、を有し、
前記第四演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第七タイミングで前記第五演算手段に出力し、
前記第五演算手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第八タイミングで前記データ並び替え手段に出力し、
前記データ並び替え手段は、前記制御信号にて示されたポイント数に関わらず、自己の出力を、前記第九タイミングで前記第六演算手段に出力し、
前記第六演算手段は、自己の出力を、前記複数のデータに対して前記制御信号にて示されたポイント数の前記処理を実行した結果として出力する。
【００２５】
本発明の離散フーリエ変換・離散逆フーリエ変換方法は、複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置での離散フーリエ変換・離散逆フーリエ変換方法であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算ステップと、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算ステップと、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算ステップと、を含み、
前記第一加算ステップでは、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで出力し、
前記乗算ステップでは、前記前段加算処理の結果を前記第二タイミングで受け付け、当該前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで出力し、
前記第二加算ステップでは、前記乗算処理の結果を前記第三タイミングで受け付け、当該乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記第一加算ステップは、
前記第一タイミングで前記複数のデータを受け付けると、前記制御信号に従って、前記複数のデータ同士を選択的に加算する、もしくは、前記複数のデータをそのまま出力する第一演算ステップと、
前記第一タイミングよりも遅く前記第二タイミングよりも早い第四タイミングで入力されたデータを、前記制御信号に従って、選択的に並べ替える、もしくは、そのまま出力する並び替えステップと、
前記第四タイミングよりも遅く前記第二タイミングよりも早い第五タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第二演算ステップと、
前記第五タイミングよりも遅く前記第二タイミングよりも早い第六タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第三演算ステップと、を有し、
前記第一演算ステップでは、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第四タイミングで出力し、
前記並び替えステップでは、前記第一演算ステップでの出力を前記第四タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第五タイミングで出力し、
前記第二演算ステップでは、前記並び替えステップでの出力を前記第五タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第六タイミングで出力し、
前記第三演算ステップは、前記第二演算ステップでの出力を前記第六タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第二タイミングで出力し、
前記乗算ステップでは、前記第三演算ステップでの出力を、前記前段加算処理の結果として前記第二タイミングで受け付け、当該前段加算処理の結果に対して前記乗算処理を実行する。また、
本発明の離散フーリエ変換・離散逆フーリエ変換方法は、複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置での離散フーリエ変換・離散逆フーリエ変換方法であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算ステップと、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算ステップと、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算ステップと、を含み、
前記第一加算ステップでは、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで出力し、
前記乗算ステップでは、前記前段加算処理の結果を前記第二タイミングで受け付け、当該前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで出力し、
前記第二加算ステップでは、前記乗算処理の結果を前記第三タイミングで受け付け、当該乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記乗算ステップは、
前記ポイント数ごとに、当該ポイント数に対応する前記離散フーリエ変換用の乗算係数および当該ポイント数に対応する前記離散逆フーリエ変換用の乗算係数を記憶手段に格納する記憶ステップと、
前記制御信号が示すポイント数および処理に対応する乗算係数を、前記記憶手段から読み出す読出しステップと、
前記第一加算ステップでの出力に、前記読み出された乗算係数を乗算する第一乗算ステップと、
前記乗算の結果に対し、前記制御信号に従って、選択的に純虚数を乗算する第二乗算ステップと、を有する。また、
本発明の離散フーリエ変換・離散逆フーリエ変換方法は、複数種類のポイント数のうちの一つと、処理が離散フーリエ変換であるのか離散逆フーリエ変換であるのかと、を示した制御信号と、複数のデータと、を受け付け、前記複数のデータに対して、前記制御信号にて示されたポイント数の離散フーリエ変換または離散逆フーリエ変換を実行する離散フーリエ変換装置での離散フーリエ変換・離散逆フーリエ変換方法であって、
前記複数のデータが、クロックにて規定される第一タイミングで入力されると、前記複数のデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた前段加算処理を実行する第一加算ステップと、
前記第一タイミングよりも遅い第二タイミングで入力されたデータに対して、前記制御信号が示した処理に応じた乗算処理を実行する乗算ステップと、
前記第二タイミングよりも遅い第三タイミングで入力されたデータに対して、前記離散フーリエ変換および前記離散逆フーリエ変換に応じた後段加算処理を実行する第二加算ステップと、を含み、
前記第一加算ステップでは、前記前段加算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第二タイミングで出力し、
前記乗算ステップでは、前記前段加算処理の結果を前記第二タイミングで受け付け、当該前段加算処理の結果に対して前記乗算処理を実行し、当該乗算処理の結果を、前記制御信号にて示されたポイント数に関わらず、前記第三タイミングで出力し、
前記第二加算ステップでは、前記乗算処理の結果を前記第三タイミングで受け付け、当該乗算処理の結果に対して前記後段加算処理を行い、当該後段加算処理の結果を、前記複数のデータに対して前記処理を実行した結果として出力し、
前記第二加算ステップは、
前記第三タイミングで前記乗算ステップでの出力を受け付けると、前記制御信号に従って、当該出力同士を選択的に加算する、もしくは、当該出力をそのまま出力する第四演算ステップと、
前記第三タイミングよりも遅い第七タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、そのまま出力する、もしくは、選択的に加算した加算結果に選択的に純虚数を乗算する第五演算ステップと、
前記第七タイミングよりも遅い第八タイミングで入力されたデータを、前記制御信号に従って、選択的に並べ替える、もしくは、そのまま出力するデータ並び替えステップと、
前記第八タイミングよりも遅い第九タイミングで入力されたデータを、前記制御信号に従って、選択的に加算する、もしくは、そのまま出力する第六演算ステップと、を有し、
前記第四演算ステップでは、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第七タイミングで出力し、
前記第五演算ステップでは、前記第四演算ステップでの出力を前記第七タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第八タイミングで出力し、
前記データ並び替えステップでは、前記第五演算ステップでの出力を前記第八タイミングで受け付け、前記制御信号にて示されたポイント数に関わらず、自己の出力を前記第九タイミングで出力し、
前記第六演算ステップでは、前記データ並び替えステップでの出力を前記第九タイミングで受け付け、自己の出力を前記複数のデータに対して前記処理を実行した結果として出力する。
【発明の効果】
【００２６】
本発明によれば、離散フーリエ変換のポイント数の種類の増加に伴い加算器および乗算器の個数が増加することを防止することが可能になる。
【図面の簡単な説明】
【００２７】
【図１】離散フーリエ変換装置２００の構成を示した図である。
【図２】前段第一加算ユニット２０４の構成を示す図である。
【図３】前段転置ユニット２０５の構成を示す図である。
【図４】前段第二加算ユニット２０６の構成を示す図である。
【図５】前段第三加算ユニット２０７の構成を示す図である。
【図６】乗算ユニット２０２の構成を示す図である。
【図７】後段第一加算ユニット２１０の構成を示す図である。
【図８】後段第二加算ユニット２１１の構成を示す図である。
【図９】後段転置ユニット２１２の構成を示す図である。
【図１０】後段第三加算ユニット２１３の構成を示す図である。
【図１１】３点DFT/IDFTのデータフローを示す図である。
【図１２】５点DFT/IDFTのデータフローを示す図である。
【図１３】９点DFT/IDFTのデータフローを示す図である。
【図１４】１５点DFT/IDFTのデータフローを示す図である。
【図１５】制御信号C_sigの内容を示す図である。
【図１６】点数信号とDFT/IDFT点数の対応、及びDFT/IDFT選択信号とDFT, IDFTの対応を示す図である。
【図１７】オフセットテーブル７０２の内容を示す図である。
【図１８】DFT乗算係数メモリ７０４、IDFT乗算係数メモリ７０５の内容を示す図である。
【図１９】３、５、９、１５点DFT/IDFTの離散フーリエ変換装置２００への入出力フォーマットを示す図である。
【図２０】３点DFT/IDFTの前段第一加算ユニット２０４における処理内容を示すタイムチャートである。
【図２１】３点DFT/IDFTの前段転置ユニット２０５における処理内容を示すタイムチャートである。
【図２２】３点DFT/IDFTの前段第二加算ユニット２０６における処理内容を示すタイムチャートである。
【図２３】３点DFT/IDFTの前段第三加算ユニット２０７における処理内容を示すタイムチャートである。
【図２４】３点DFT/IDFTの乗算ユニット２０２における処理内容を示すタイムチャートである。
【図２５】３点DFT/IDFTの後段第一加算ユニット２１０における処理内容を示すタイムチャートである。
【図２６】３点DFT/IDFTの後段第二加算ユニット２１１における処理内容を示すタイムチャートである。
【図２７】３点DFT/IDFTの後段転置ユニット２１２における処理内容を示すタイムチャートである。
【図２８】３点DFT/IDFTの後段第三加算ユニット２１３における処理内容を示すタイムチャートである。
【図２９】５点DFT/IDFTの前段第一加算ユニット２０４における処理内容を示すタイムチャートである。
【図３０】５点DFT/IDFTの前段転置ユニット２０５における処理内容を示すタイムチャートである。
【図３１】５点DFT/IDFTの前段第二加算ユニット２０６における処理内容を示すタイムチャートである。
【図３２】５点DFT/IDFTの前段第三加算ユニット２０７における処理内容を示すタイムチャートである。
【図３３】５点DFT/IDFTの乗算ユニット２０２における処理内容を示すタイムチャートである。
【図３４】５点DFT/IDFTの後段第一加算ユニット２１０における処理内容を示すタイムチャートである。
【図３５】５点DFT/IDFTの後段第二加算ユニット２１１における処理内容を示すタイムチャートである。
【図３６】５点DFT/IDFTの後段転置ユニット２１２における処理内容を示すタイムチャートである。
【図３７】５点DFT/IDFTの後段第三加算ユニット２１３における処理内容を示すタイムチャートである。
【図３８】９点DFT/IDFTの前段第一加算ユニット２０４における処理内容を示すタイムチャートである。
【図３９】９点DFT/IDFTの前段転置ユニット２０５における処理内容を示すタイムチャートである。
【図４０】９点DFT/IDFTの前段第二加算ユニット２０６における処理内容を示すタイムチャートである。
【図４１】９点DFT/IDFTの前段第三加算ユニット２０７における処理内容を示すタイムチャートである。
【図４２】９点DFT/IDFTの乗算ユニット２０２における処理内容を示すタイムチャートである。
【図４３】９点DFT/IDFTの後段第一加算ユニット２１０における処理内容を示すタイムチャートである。
【図４４】９点DFT/IDFTの後段第二加算ユニット２１１における処理内容を示すタイムチャートである。
【図４５】９点DFT/IDFTの後段転置ユニット２１２における処理内容を示すタイムチャートである。
【図４６】９点DFT/IDFTの後段第三加算ユニット２１３における処理内容を示すタイムチャートである。
【図４７】１５点DFT/IDFTの乗算ユニット２０２における処理内容を示すタイムチャートである。
【図４８】本発明の第二の実施形態の構成を示す図である。
【図４９】ウィノグラードの方法を用いた、１５点DFTの処理方法を示す図である。
【発明を実施するための形態】
【００２８】
次に、本発明の実施形態の離散フーリエ変換装置について図面を参照して詳細に説明する。
【００２９】
（第１実施形態）
図１は、本発明の第１実施形態の離散フーリエ変換装置（以下「演算装置」とも称する）２００を示すブロック図である。
【００３０】
図１において、演算装置２００は、前加算ユニット２０１と、乗算ユニット２０２と、後加算ユニット２０３と、を含む。
【００３１】
前加算ユニット２０１は、前段第一加算ユニット２０４と、前段転置ユニット２０５と、前段第二加算ユニット２０６と、前段第三加算ユニット２０７と、を含む。乗算ユニット２０２は、乗算器２０８と、制御ユニット２０９と、を含む。後加算ユニット２０３は、後段第一加算ユニット２１０と、後段第二加算ユニット２１１と、後段転置ユニット２１２と、後段第三加算ユニット２１３と、を含む。
【００３２】
演算装置２００は、複数種類のポイント数のうちの１つを示した制御信号と、複数のデータと、を受け付けると、複数のデータに対して、制御信号にて示されたポイント数の離散フーリエ変換（DFT）を実行する。
【００３３】
本実施形態では、複数種類のポイント数は、３点、５点、９点および１５点にて構成される。複数のデータのそれぞれは、DFTが施される複素数データである。
【００３４】
演算装置２００は、制御信号と複数のデータとを受け付けると、まず、制御信号が示すポイント数のDFTに応じた前段加算処理を、複素数データに対して実行して、前段加算処理結果を生成する。
【００３５】
続いて、演算装置２００は、制御信号が示すポイント数のDFTに応じた乗算処理を、その前段加算処理結果に対して実行して、乗算処理結果を生成する。
【００３６】
続いて、演算装置２００は、制御信号が示すポイント数のDFTに応じた後段加算処理を、その乗算処理結果に対して実行して、制御信号にて示されたポイント数のDFTの結果を出力する。
【００３７】
前段加算処理は、乗算処理の前に行われるべき加算処理であり、後段加算処理は、乗算処理の後に行われるべき加算処理である。
【００３８】
なお、DFTの処理を、前段加算処理と乗算処理と後段加算処理とに分けて行うことは、例えば、ウィノグラードの方法等により公知である（図４９参照）
前加算ユニット２０１は、一般的に第一加算手段と呼ぶことができる。
【００３９】
前加算ユニット２０１は、複数のデータが、第一タイミングで入力されると、その複数のデータに対して、制御信号が示すポイント数の離散フーリエ変換に応じた前段加算処理を実行する。
【００４０】
乗算ユニット２０２は、一般的に乗算手段と呼ぶことができる。
【００４１】
乗算ユニット２０２は、第一タイミングよりも遅い第二タイミングで入力されたデータに対して、制御信号が示すポイント数の離散フーリエ変換に応じた乗算処理を実行する。
【００４２】
後加算ユニット２０３は、一般的に第二加算手段と呼ぶことができる。
【００４３】
後加算ユニット２０３は、第二タイミングよりも遅い第三タイミングで入力されたデータに対して、制御信号が示すポイント数の離散フーリエ変換に応じた後段加算処理を実行する。
【００４４】
なお、前加算ユニット２０１は、前段加算処理の結果を、制御信号にて示されたポイント数に関わらず、第二タイミングで、乗算ユニット２０２に出力する。
【００４５】
また、乗算ユニット２０２は、前段加算処理の結果に対して乗算処理を実行し、その乗算処理の結果を、制御信号にて示されたポイント数に関わらず、第三タイミングで、後加算ユニット２０３に出力する。
【００４６】
また、後加算ユニット２０３は、乗算処理の結果に対して後段加算処理を行い、その後段加算処理の結果を、複数のデータに対して制御信号にて示されたポイント数の離散フーリエ変換を実行した結果として出力する。
【００４７】
前段第一加算ユニット２０４は、一般的に第一演算手段と呼ぶことができる。
【００４８】
前段第一加算ユニット２０４は、第一タイミングで複数のデータを受け付けると、制御信号に従って、複数のデータ同士を選択的に加算する（加算処理）、もしくは、複数のデータをそのまま出力する。
【００４９】
前段転置ユニット２０５は、一般的に並び替え手段と呼ぶことができる。
【００５０】
前段転置ユニット２０５は、第一タイミングよりも遅く第二タイミングよりも早い第四タイミングで入力されたデータを、制御信号に従って、選択的に並べ替える（転置処理）、もしくは、そのまま出力（スルー処理）する。
【００５１】
前段第二加算ユニット２０６は、一般的に第二演算手段と呼ぶことができる。
【００５２】
前段第二加算ユニット２０６は、第四タイミングよりも遅く第二タイミングよりも早い第五タイミングで入力されたデータを、制御信号に従って、選択的に加算する（加算処理）、もしくは、そのまま出力する。
【００５３】
前段第三加算ユニット２０７は、一般的に第三演算手段と呼ぶことができる。
【００５４】
前段第三加算ユニット２０７は、第五タイミングよりも遅く第二タイミングよりも早い第六タイミングで入力されたデータを、制御信号に従って、選択的に加算する（加算処理）、もしくはそのまま出力する。
【００５５】
なお、前段第一加算ユニット２０４は、制御信号にて示されたポイント数に関わらず、自己の出力を、第四タイミングで、前段転置ユニット２０５に出力する。
【００５６】
前段転置ユニット２０５は、制御信号にて示されたポイント数に関わらず、自己の出力を、第五タイミングで、前段第二加算ユニット２０６に出力する。
【００５７】
前段第二加算ユニット２０６は、制御信号にて示されたポイント数に関わらず、自己の出力を、第六タイミングで、前段第三加算ユニット２０７に出力する。
【００５８】
前段第三加算ユニット２０７は、制御信号にて示されたポイント数に関わらず、自己の出力を、第二タイミングで、乗算ユニット２０２に出力する。
【００５９】
乗算器２０８は、制御ユニット２０９から乗算係数を読み出し、その乗算係数を前段第三加算ユニット２０７の出力に乗算する乗算処理を行う。
【００６０】
制御ユニット２０９は、ポイント数ごとに、そのポイント数に対応する複素数の乗算係数を蓄えたメモリ（記憶手段）と、制御信号が示すポイント数に対応する乗算係数をメモリから読み出すためのアドレスを生成するアドレス生成ユニット（読み出し手段）と、を含む。
【００６１】
後段第一加算ユニット２１０は、一般的に第四演算手段と呼ぶことができる。
【００６２】
後段第一加算ユニット２１０は、第三タイミングで乗算ユニット２０２の出力を受け付けると、制御信号に従って、乗算ユニット２０２の出力同士を選択的に加算する（加算処理）、もしくは、乗算ユニット２０２の出力をそのまま出力する。
【００６３】
後段第二加算ユニット２１１は、一般的に第五演算手段と呼ぶことができる。
【００６４】
後段第二加算ユニット２１１は、第三タイミングよりも遅い第七タイミングで入力されたデータを、制御信号に従って、選択的に加算する（加算処理）、そのまま出力する、または、選択的に加算した加算結果に選択的に純虚数を乗算する。
【００６５】
後段転置ユニット２１２は、一般的にデータ並び替え手段と呼ぶことができる。
【００６６】
後段転置ユニット２１２は、第七タイミングよりも遅い第八タイミングで入力されたデータを、制御信号に従って、選択的に並べ替える（転置処理）、もしくは、そのまま出力（スルー処理）する。
【００６７】
後段第三加算ユニット２１３は、一般的に第六演算手段と呼ぶことができる。
【００６８】
後段第三加算ユニット２１３は、第八タイミングよりも遅い第九タイミングで入力されたデータを、制御信号に従って、選択的に加算する（加算処理）、もしくは、そのまま出力する。
【００６９】
なお、後段第一加算ユニット２１０は、制御信号にて示されたポイント数に関わらず、自己の出力を、第七タイミングで、後段第二加算ユニット２１１に出力する。
【００７０】
後段第二加算ユニット２１１は、制御信号にて示されたポイント数に関わらず、自己の出力を、第八タイミングで、後段転置ユニット２１２に出力する。
【００７１】
後段転置ユニット２１２は、制御信号にて示されたポイント数に関わらず、自己の出力を、第九タイミングで、後段第三加算ユニット２１３に出力する。
【００７２】
後段第三加算ユニット２１３は、自己の出力を、複数のデータに対して制御信号にて示されたポイント数の離散フーリエ変換を実行した結果として出力する。
【００７３】
図２は、前段第一加算ユニット２０４を示したブロック図である。
【００７４】
図２において、前段第一加算ユニット２０４は、遅延回路Dと、クロスバ（Xbar）３１および３７と、加算器３２、３３、３５および３６と、セレクタ（Sel）３４と、を含む。
【００７５】
なお、前段第一加算ユニット２０４は、入力された制御信号C_sigを取り込み、また、制御信号C_sigをC_outとして出力する。
【００７６】
遅延回路Dは、演算装置２００へ入力された複素数データin3を１クロック分遅延する。
【００７７】
クロスバ３１は、制御信号C_sigに従って、遅延回路Dからの出力regr及び複素数データin1、in2、in3のそれぞれを、sel1、sel2、sel3、sel4、sel6、sel7、sel8のいずれかとして出力する。
【００７８】
加算器３２は、sel3とsel4とを加算する加算処理を行う。
【００７９】
加算器３３は、sel3と符号を反転したsel4とを加算する加算処理を行う。
【００８０】
セレクタ３４は、制御信号C_sigに従って、sel2か加算器３２の出力add_o_3かを選択して出力する。
【００８１】
加算器３５は、sel1とセレクタ３４の出力sel5とを加算する加算処理を行う。
【００８２】
加算器３６は、sel1と符号を反転したsel5とを加算する加算処理を行う。
【００８３】
クロスバ３７には、加算器３５の出力add_o_1、加算器３６の出力add_o_2、加算器３２の出力add_o_3、加算器３３の出力add_o_4、sel6、sel7、および、sel8が、入力可能である。
【００８４】
クロスバ３７は、入力された信号のそれぞれを、制御信号C_sigに従って、out1、out2、out3、 out4として出力する。
【００８５】
図３は、前段転置ユニット２０５を示したブロック図である。
【００８６】
図３において、複素数データin1は、前段第一加算ユニット２０４からのout1であり、複素数データin2は、前段第一加算ユニット２０４からのout2であり、複素数データin3は、前段第一加算ユニット２０４からのout3であり、複素数データin4は、前段第一加算ユニット２０４からのout4であり、制御信号C_sigは、前段第一加算ユニット２０４からのC_outである。
【００８７】
図３において、前段転置ユニット２０５は、複数の遅延回路Dと、クロスバ（Xbar）４１、４２および４３と、を含む。なお、図３内の各遅延回路Dは、入力されたデータを１クロック遅延させる。
【００８８】
前段転置ユニット２０５は、入力された複素数データin1, in2, in3およびin4と、同じく入力された制御信号C_sigと、をペアとして扱う。すなわち、前段転置ユニット２０５内のクロスバなどに入力される個々の複素数データには、制御信号C_sigが付加されることになる。
【００８９】
前段転置ユニット２０５は、制御信号と複素数データとの入力時に、制御信号と複素数データをペアにする処理を行う。以下では、この処理を「統合」と呼ぶこととする。
【００９０】
クロスバ４１は、複素数データin1からin4の各々を、それぞれの複素数データに統合された制御信号C_sigに従って、Sel_1_1からSel_1_7のいずれかとして出力する。
【００９１】
クロスバ４２は、遅延回路Dからの出力D_Sel_1_1からD_Sel_1_4を、各データに統合されている制御信号C_sigに従って、Sel_2_1からSel_2_4のいずれかとして出力する。
【００９２】
クロスバ４３は、D_dt_1からD_dt_11の各信号を、それぞれに統合された制御信号に従って、Sel_3_1からSel_3_4のいずれかとして出力する。
【００９３】
Sel_3_1からSel_3_4の各信号は、制御信号と複素数データとに分離される。この分離された信号のうち、複素数データのみが、本ユニットからの出力out1、out2、out3、out4として出力される。一方、制御信号は、図３のGNDで示したグラウンドに入力され、以降使用されることはない。また、制御信号C_sigは、10クロック遅延され、C_outとして出力される。
【００９４】
図４は、前段第二加算ユニット２０６を示したブロック図である。
【００９５】
図４において、複素数データin1は、前段転置ユニット２０５からのout1であり、複素数データin2は、前段転置ユニット２０５からのout2であり、複素数データin3は、前段転置ユニット２０５からのout3であり、複素数データin4は、前段転置ユニット２０５からのout4であり、制御信号C_sigは、前段転置ユニット２０５からのC_outである。
【００９６】
図４において、前段第二加算ユニット２０６は、複数の遅延回路Dと、クロスバ（Xbar）&符号反転器５１と、加算器５２、５３、５４および５５と、を含む。
【００９７】
クロスバ（Xbar）&符号反転器５１は、制御信号C_sigに従って、入力in1からin4と、遅延回路Dの出力regr1からregr5と、の符号を反転し、それぞれを、sel1からsel9のいずれかとして出力する。
【００９８】
加算器５２は、sel1とsel2とsel3とを加算する加算処理を行う。加算器５３は、sel4とsel5とを加算する加算処理を行う。加算器５４は、sel6とsel7とを加算する加算処理を行う。加算器５５は、sel8とsel9とを加算する加算処理を行う。
【００９９】
これら加算器の出力は、それぞれ、out1, out2, out3, out4として、本ユニットから出力される。
【０１００】
また、制御信号C_sigは、１クロック遅延されて、C_outとして出力される。
【０１０１】
図５は、前段第三加算ユニット２０７を示したブロック図である。
【０１０２】
図５において、複素数データin1は、前段第二加算ユニット２０６からのout1であり、複素数データin2は、前段第二加算ユニット２０６からのout2であり、複素数データin3は、前段第二加算ユニット２０６からのout3であり、複素数データin4は、前段第二加算ユニット２０６からのout4であり、制御信号C_sigは、前段第二加算ユニット２０６からのC_outである。
【０１０３】
前段第三加算ユニット２０７は、複数の遅延回路Dと、クロスバ（Xbar）&符号反転器６１と、加算器６２、６３、６４および６５と、を含む。
【０１０４】
クロスバ（Xbar）&符号反転器６１は、制御信号C_sigに従って、入力in1からin4と、遅延回路Dの出力regr1からregr4と、の符号を反転し、それぞれを、sel1からsel10のいずれかとして出力する。
【０１０５】
加算器６２は、sel1とsel2とsel3とを加算する加算処理を行う。加算器６３は、sel4とsel5とを加算する加算処理を行う。加算器６４は、sel6とsel7とsel8とを加算する加算処理を行う。加算器６５は、sel9とsel10とを加算する加算処理を行う。
【０１０６】
これら加算器の出力は、それぞれ、out1, out2, out3, out4として出力される。
【０１０７】
また、制御信号C_sigは、C_outとして出力される。
【０１０８】
図６は、制御ユニット２０９と乗算器２０８を示したブロック図である。
【０１０９】
図６において、複素数データin1は、前段第三加算ユニット２０７からのout1であり、複素数データin2は、前段第三加算ユニット２０７からのout2であり、複素数データin3は、前段第三加算ユニット２０７からのout3であり、複素数データin4は、前段第三加算ユニット２０７からのout4であり、制御信号C_sigは、前段第三加算ユニット２０７からのC_outである。
【０１１０】
図６において、制御ユニット２０９は、後述するクロック数信号に加算するオフセットを格納したオフセットテーブル７０２と、乗算係数メモリ７０４および７０５と、加算器７０３と、セレクタ７０６と、を含む。
【０１１１】
乗算器２０８は、クロスバ（Xbar）７０１と、入力信号と乗算係数の、実数部と虚数部をそれぞれ乗算する並列乗算器７０７、７０８、７０９および７１０と、純虚数を乗算する純虚数乗算器７１１、７１２、７１３および７１４と、セレクタ７１５、７１６、７１７および７１８と、を含む。
【０１１２】
制御ユニット２０９においては、制御信号C_sigが入力されると、C_sigに従ってオフセットテーブル７０２からオフセットが出力される。加算器７０３は、そのオフセットとクロック数信号とを加算する。この加算結果に従って、乗算係数メモリ７０４および７０５のそれぞれから、乗算係数が出力される。セレクタ７０６は、後述のDFT/IDFT選択信号に従って、乗算係数メモリ７０４からの乗算係数と乗算係数メモリ７０５からの乗算係数とのいずれかを、mult_cf1からmult_cf4として出力する。
【０１１３】
なお、クロック数信号、DFT/IDFT選択信号、および、メモリやテーブルの構成とそのアクセス方法については、後で詳細を説明する。
【０１１４】
乗算器２０８では、クロスバ（Xbar）７０１は、制御信号C_sigに従って、入力in1からin4のそれぞれを、sel1からsel5のいずれかとして出力する。
【０１１５】
並列乗算器７０７、７０８、７０９および７１０は、それぞれ、sel2とmult_cf4、sel3とmult_cf3、sel4とmult_cf2、sel5とmult_cf1を乗算し、それら乗算結果を、mult_sel1からmult_sel4のいずれかとして出力する。
【０１１６】
純虚数乗算器７１１、７１２、７１３および７１４は、それぞれ、mult_sel1からmult_sel4に対し、純虚数を乗算し、それら乗算結果を、mult_i_sel1からmult_i_sel4のいずれかとして出力する。
【０１１７】
セレクタ７１５、７１６、７１７および７１８は、それぞれ、C_sigに従って、mult_sel1からmult_sel4と、mult_i_sel1からmult_i_sel4とを、それぞれ選択的にout1からout4として出力する。
【０１１８】
なお、クロスバ（Xbar）７０１の出力sel1は、out1として出力される。また、制御信号C_sigは、C_outとして出力される。
【０１１９】
図７は、後段第一加算ユニット２１０を示したブロック図である。
【０１２０】
図７において、複素数データin1は、乗算器２０８からのout1であり、複素数データin2は、乗算器２０８からのout2であり、複素数データin3は、乗算器２０８からのout3であり、複素数データin4は、乗算器２０８からのout4であり、複素数データin5は、乗算器２０８からのout5であり、制御信号C_sigは、乗算器２０８からのC_outである。
【０１２１】
図７において、後段第一加算ユニット２１０は、クロスバ（Xbar）８１および８５と、加算器８２、８３および８４と、を含む。
【０１２２】
クロスバ（Xbar）８１は、制御信号C_sigに従って、入力in1からin6のそれぞれを、sel1からsel9のいずれかとして出力する。
【０１２３】
加算器８２は、sel4とsel5を加算し、その加算結果add_s1を出力する。加算器８３は、sel6とsel7を加算し、その加算結果add_s2を出力する。加算器８４は、sel8とsel9を加算し、その加算結果add_s3を出力する。
【０１２４】
クロスバ（Xbar）８５は、sel1、sel2、sel3、add_s1、add_s2およびadd_s3を入力可能である。クロスバ（Xbar）８５は、C_sigに従って、入力信号のそれぞれを、out1からout4のいずれかとして出力する。
【０１２５】
また、制御信号C_sigは、C_outとして出力される。
【０１２６】
図８は、後段第二加算ユニット２１１を示したブロック図である。
【０１２７】
図８において、複素数データin1は、後段第一加算ユニット２１０からのout1であり、複素数データin2は、後段第一加算ユニット２１０からのout2であり、複素数データin3は、後段第一加算ユニット２１０からのout3であり、複素数データin4は、後段第一加算ユニット２１０からのout4であり、制御信号C_sigは、後段第一加算ユニット２１０からのC_outである。
【０１２８】
図８において、後段第二加算ユニット２１１は、複数の遅延回路Dと、クロスバ（Xbar）９０１と、加算器９０２、９０３、９０４および９０５と、純虚数乗算器９０６、９０７、９０８および９０９と、Sel（セレクタ）９１０、９１１、９１２および９１３と、を含む。
【０１２９】
クロスバ（Xbar）９０１は、制御信号C_sigに従って、入力in1からin4と遅延回路Dの出力regr1からregr10とのそれぞれを、sel1からsel12のいずれかとして出力する。
【０１３０】
加算器９０２は、sel1とsel2とsel3とを加算して、加算結果add_s1を出力する。加算器９０３は、sel4とsel5とsel6とを加算して、加算結果add_s2を出力する。加算器９０４は、sel7とsel8とsel9とを加算して、加算結果add_s3を出力する。加算器９０４は、sel10とsel11とsel12とを加算して、加算結果add_s4を出力する。
【０１３１】
純虚数乗算器９０６は、加算結果add_s1に純虚数を乗算して、乗算結果add_i_s1を出力する。純虚数乗算器９０７は、加算結果add_s2に純虚数を乗算して、乗算結果add_i_s2を出力する。純虚数乗算器９０８は、加算結果add_s3に純虚数を乗算して、乗算結果add_i_s3を出力する。純虚数乗算器９０９は、加算結果add_s4に純虚数を乗算して、乗算結果add_i_s4を出力する。
【０１３２】
セレクタSel９１０は、C_sigに従って、加算器９０２の出力か純虚数乗算器９０６の出力かを選択して、その選択結果を、out1として出力する。セレクタSel９１１は、C_sigに従って、加算器９０３の出力か純虚数乗算器９０７の出力かを選択して、その選択結果を、out2として出力する。セレクタSel９１２は、C_sigに従って、加算器９０４の出力か純虚数乗算器９０８の出力かを選択して、その選択結果を、out3として出力する。セレクタSel９１３は、C_sigに従って、加算器９０５の出力か純虚数乗算器９０９の出力かを選択して、その選択結果を、out4として出力する。
【０１３３】
C_sigは、２クロック遅延され、C_outとして出力される。
【０１３４】
図９は、後段転置ユニット２１２を示したブロック図である。
【０１３５】
図９において、複素数データin1は、後段第二加算ユニット２１１からのout1であり、複素数データin2は、後段第二加算ユニット２１１からのout2であり、複素数データin3は、後段第二加算ユニット２１１からのout3であり、複素数データin4は、後段第二加算ユニット２１１からのout4であり、制御信号C_sigは、後段第二加算ユニット２１１からのC_outである。
【０１３６】
図９において、後段転置ユニット２１２は、複数の遅延回路Dと、クロスバ（Xbar）１００１、１００２、１００３および１００４と、を含む。
【０１３７】
後段転置ユニット２１２では、まず、入力in1、in2、in3、in4が、制御信号C_sigと統合される。
【０１３８】
クロスバ（Xbar）１００１は、これらの信号を、それぞれ、Sel1_1からSel1_7のいずれかとして出力する。
【０１３９】
クロスバ（Xbar）１００２は、Sel1_1と、遅延回路Dの出力D_Sel1_1からD_Sel1_3を、それぞれが有する制御信号に従って、Sel2_1からSel2_4のいずれかに振り分ける。
【０１４０】
クロスバ（Xbar）１００３は、遅延回路Dの出力D_Sel2_1からD_Sel2_3を、それぞれが有する制御信号に従って、Sel3_1、Sel3_2、Sel3_3のいずれかに振り分ける。
【０１４１】
クロスバ（Xbar）１００４は、D_Sel3_1からD_Sel3_3と、D_Sel2_1からD_Sel2_3と、Sel2_4、Sel1_5、Sel1_6、および、Sel1_7を、それぞれが有する制御信号に従って、Sel4_1からSel4_4のいずれかに振り分ける。
【０１４２】
Sel4_1からSel4_4は、制御信号と複素数データに分離される。複素数データのそれぞれは、out1、out2、out3、out4のいずれかとして出力される。一方、制御信号は、図９のGNDで示されるグラウンドへと出力され、以降使用されることはない。
【０１４３】
また、制御信号C_sigは、遅延回路Dによって３クロック遅延され、C_outとして出力される。
【０１４４】
図１０は、後段第三加算ユニット２１３を示したブロック図である。
【０１４５】
図１０において、複素数データin1は、後段転置ユニット２１２からのout1であり、複素数データin2は、後段転置ユニット２１２からのout2であり、複素数データin3は、後段転置ユニット２１２からのout3であり、複素数データin4は、後段転置ユニット２１２からのout4であり、制御信号C_sigは、後段転置ユニット２１２からのC_outである。
【０１４６】
図１０において、後段第三加算ユニット２１３は、複数の遅延回路Dと、クロスバ（Xbar）１１０１および１１０８と、加算器１１０２、１１０３、１１０６および１１０７と、Sel（セレクタ）１１０４および１１０５と、を含む。
【０１４７】
クロスバ（Xbar）１１０１は、制御信号C_sigに従って、入力in1からin4と遅延回路Dの出力regr1からregr5とのそれぞれを、sel1からsel7のいずれかとして出力する。
【０１４８】
加算器１１０２は、sel1とsel2を加算して、加算結果add_o_1を出力する。加算器１１０３は、sel1と符号を反転したsel2とを加算し、加算結果add_o_2を出力する。
【０１４９】
セレクタSel１１０４は、制御信号C_sigに従って、sel1とadd_o_2のいずれかを選択し、その選択結果をadd_sel1として出力する。セレクタSel１１０５は、制御信号C_sigに従って、sel3とadd_o_1のいずれかを選択し、その選択結果をadd_sel2として出力する。
【０１５０】
加算器１１０６は、add_sel2とsel4を加算して、加算結果add_o_3を出力する。加算器１１０７は、add_sel2と符号を反転したsel4を加算して、加算結果add_o_4を出力する。
【０１５１】
クロスバ（Xbar）１１０８は、add_sel1、add_o_1、add_o_3、add_o_4、sel5、sel6およびsel7を入力可能である。クロスバ（Xbar）１１０８は、制御信号C_sigに従って、入力信号のそれぞれを、out1からout4のいずれかとして出力する。
【０１５２】
次に、演算装置２００が、制御信号に従って、３、５、９、１５点DFT/IDFTを行う例を説明する。
【０１５３】
まず、演算装置２００が処理する３点DFT/IDFT、５点DFT/IDFT、９点DFT/IDFT、１５点DFT/IDFTのデータフローのそれぞれを、図１１、図１２、図１３、図１４に示す。
【０１５４】
なお、DFTとIDFTは、後述の乗算係数を変えるだけで、その他は同じデータフローで処理することができる。このため、本説明では、各点数のDFTとIDFTを、それぞれの点数について、１つの図、すなわち、３点DFT/IDFTを図１１、５点DFT/IDFTを図１２、９点DFT/IDFTを図１３、１５点DFT/IDFTを図１４を用いて説明する。
【０１５５】
図１１、図１２、図１３、図１４において、矢印が重なる箇所は加算を示し、“−”で示すボックスは、そこを通過した信号の符号を反転することを意味し、“ｉ”で示すボックスは、そこを通過した信号に純虚数を乗算することを示し、“×”で示す記号は、そこを通過する信号と、×記号の上部に矢印で示された乗算係数と、を乗算することを示す。
【０１５６】
また、１５点DFT/IDFTは、処理の途中で並べ替えを行う必要があるが、その処理は、図１４の“並べ替え”と記載された箇所で行われる。
【０１５７】
また、各DFT/IDFTの入力Xおよび出力Yのインデクスは、数１で示した式のX、Yのインデクスに対応する。
【０１５８】
次に、入力される信号について説明する。
【０１５９】
演算装置２００に入力されるデータは、複素数データであり、実数部と虚数部は、それぞれ、浮動小数形式で表されたデータであるものとする。
【０１６０】
また、本ユニットに入力される制御信号C_sigは、図１５に記載のフォーマットを使用する。図１５に示したとおり、C_sigは、DFT/IDFTの３、５、９、１５点のいずれかを２ビットで示す点数信号と、点数信号で示されたDFT/IDFTが開始されてから経過したクロック数を３ビットで示すクロック数信号と、制御信号で行う処理がDFTであるのかIDFTであるのかを１ビットで示すDFT/IDFT選択信号と、を含む。なお、点数信号とDFT/IDFT点数の対応、および、DFT/IDFT選択信号とDFT、IDFTの対応は、図１６に示すとおりである。
【０１６１】
次に、図６に記載のオフセットテーブル７０２の構成を図１７に示す。
【０１６２】
オフセットテーブル７０２は、図１５に示す点数信号をアドレスとして用い、各アドレスが示す内容には、乗算係数メモリ７０４、７０５にアクセスするためのオフセットが格納されている。すなわち、外部よりオフセットテーブル７０２に点数信号が入力されると、それに対応したオフセットがオフセットテーブル７０２より読み出され、オフセットテーブル７０２の外部へと出力される。
【０１６３】
次に、DFT乗算係数メモリ７０４、及びIDFT乗算係数メモリ７０５について図１８を用いて説明する。
【０１６４】
図１８に示すように、DFT乗算係数メモリ７０４およびIDFT乗算係数メモリ７０５は、それぞれ４つのメモリを持つ。また、これら４つのメモリにアドレスが入力されると、図１８の“アドレス”に記載の値に対応した行の、各メモリに格納された４つの値が読み出され、図６のmult_cf1, mult_cf2, mult_cf3, mult_cf4として、それぞれ出力される。
【０１６５】
例として、DFT乗算係数メモリ７０４にアドレス“２”が入力されたとすると、メモリ１からは0.559017、メモリ２からは1.538842、メモリ３からは-0.36327、メモリ４からは-0.58779が読み出される。
【０１６６】
なお、図１８には、図１１、図１２、図１３、図１４に示した乗算係数の係数名も併記した。また、表内の斜線は、その箇所に値が格納されていないことを示すものである。さらに、DFT乗算係数メモリおよびIDFT乗算係数メモリの４つのメモリに入力されるアドレスとは、クロック数信号と、オフセットテーブル７０２から読み出されたオフセット値と、を加算したものである。
【０１６７】
演算装置２００への３点、５点、９点、１５点のDFT/IDFTのデータの入力フォーマットを、図１９を用いて説明する。
【０１６８】
図１９は、３点、５点、９点、１５点DFT/IDFTの入力XをDFT/IDFT回路に入力して、出力Yを得る様子を示した図である。
【０１６９】
なお、入力Xの上部に示したCは、制御信号を示しており、C（DFT/IDFT選択信号値、クロック数、点数信号）のフォーマットとなっている。なお、本説明においては、DFTを例として説明を行うが、IDFTは後述する乗算ユニット部以外はDFTと同一の処理であるため、説明を省略する。
【０１７０】
なお、５点DFT/IDFTについて、演算装置２００では３つの系列を同時に行うことができる。
【０１７１】
ここで、系列とは、図１２に示す処理を１回分とする処理である。よって、３つの系列とは、図１２に示す処理を３つ同時に行うことを意味する。
【０１７２】
以下では３つの系列のそれぞれを、系列０、系列１、系列２として呼ぶこととする。
【０１７３】
図１９のXの（）内のインデクスは、（図１２の各信号に付されたインデクス、系列番号）を示している。例として、X(0,0)は、系列0のX0を示すものである。
【０１７４】
（３点DFT/IDFT）
次に、演算装置２００による３点DFT/IDFTの処理を説明する。
【０１７５】
図２０を用いて、前段第一加算ユニット２０４の処理を説明する。なお、図２０において、何も記述されていない箇所の値は0値をとるものとし、以降に示すタイムチャートも同様であるとする。
【０１７６】
前段第一加算ユニット２０４では、図１１に示すb0、b1、b2を算出する処理を、１サイクルで行う。
【０１７７】
具体的には、入力されたC_sigに従って、クロスバ（Xbar）３１が、sel1としてX(0)を、sel3としてX(1)を、sel4としてX(2)を出力する。
【０１７８】
次に、加算器３５がb0を出力し、加算器３２がb1を出力し、加算器３３がb2を出力する。
【０１７９】
最後に、Xbar３７が、制御信号C_sigに従って、b0をout1に出力し、b1をout2に出力し、b2をout3に出力する。
【０１８０】
このように、Xbarおよびセレクタは、入力されたC_sigによって、入力の出力先を変更する。以下では、各Xbarやセレクタの詳しい説明は省略し、信号名に出力される信号値のみを説明中で示すこととする。
【０１８１】
図２１を用いて、前段転置ユニット２０５の処理を説明する。
【０１８２】
前段転置ユニット２０５では、まず、入力されたデータin1、in2、in3を、クロスバ（Xbar）４１が、D_Sel_1_1、D_Sel_1_2、D_Sel_1_3として出力する。
【０１８３】
次に、クロスバ（Xbar）４２が、D_Sel_1_1からD_Sel_1_3を、それぞれSel_2_1からSel_2_3として出力し、クロスバ（Xbar）４３が、out1、out2、out3を出力する。
【０１８４】
図２２を用いて、前段第二加算ユニット２０６の処理内容を説明する。
【０１８５】
前段転置ユニット２０５では、特に加算処理を行わず、入力されたデータを遅延回路Dによって遅延させ、次のユニットに出力する。
【０１８６】
図２３を用いて、前段第三加算ユニット２０７の処理内容を説明する。
【０１８７】
前段第三加算ユニット２０７では、特に加算処理を行わず、入力されたデータをスルーさせ、次のユニットに出力する。
【０１８８】
図２４を用いて、制御ユニット２０９、乗算器２０８の処理内容を説明する。
【０１８９】
制御ユニット２０９は、１サイクル目で乗算係数T_3_1およびT_3_2を読み出し、乗算器２０８は、それをb1、b2に乗算して、out2、out3に出力する。なお、乗算器２０８は、b0には、特に係数を乗算せず、out1として出力する。
【０１９０】
図２５を用いて、後段第一加算ユニット２１０の処理内容を説明する。
【０１９１】
後段第一加算ユニット２１０は、特に処理を行わず、入力データin1、in2、in3を、それぞれsel1、sel2、sel3として出力し、それをout1、out2、out3として出力する。
【０１９２】
図２６を用いて、後段第二加算ユニット２１１の処理内容を説明する。
【０１９３】
後段第二加算ユニット２１１は、特に加算処理を行わないが、入力されたデータを２クロック遅延させて出力する。具体的には、後段第二加算ユニット２１１は、入力データin1、in2、in3をそれぞれregr2、regr5、regr7として出力し、さらに、それらをsel1、sel4、sel7として出力する。その後、各加算器８２および８４は、それぞれ、sel4、sel7に0を加算することによって、sel4、sel7と同じ値のadd_s1、add_s2を出力する。最終的にout1、out2、out3が出力される。
【０１９４】
図２７を用いて、後段転置ユニット２１２の処理内容を説明する。
【０１９５】
後段転置ユニット２１２では、入力されたデータin1、in2、in3を、Sel_1_1、Sel_1_2、Sel_1_3として出力し、その後、遅延回路Dによって遅延された信号を、クロスバ（Xbar）１００２が、Sel_2_1、Sel_2_2、Sel_2_3として出力する。
【０１９６】
このとき、後段転置ユニット２１２は、特に入力されたデータを入れ替える処理などは行わない。その後、それぞれの信号は、D_Sel_2_1、D_Sel_2_2、D_Sel_2_3として出力され、その後、クロスバ（Xbar）１００４およびSel_4_1、Sel_4_2、Sel_4_3を通過してout1、out2、out3として出力される。
【０１９７】
図２８を用いて、後段第三加算ユニット２１３の処理内容を説明する。
【０１９８】
後段第三加算ユニット２１３では、入力されたデータを１クロック遅延させた上で加算処理を行う。具体的には、入力データin1、in2、in3は、それぞれ、regr2、regr3、reg4として出力される。その後、加算器１１０２がm0+m1の計算を行い、加算器１１０７がm0+m1-m2の計算を行う。また、m0はsel5として出力される。最後に、クロスバ（Xbar）１１０８から、３点DFT/IDFT結果y0、y1およびy2が、それぞれ、out1、out2、out3として出力される。
【０１９９】
このように、演算装置２００は、３点DFT/IDFTを指示する制御信号を受け付けると、３点DFT/IDFTを実行する。
【０２００】
（５点DFT/IDFT）
次に、演算装置２００による５点DFT/IDFTの処理を説明する。
【０２０１】
図２９を用いて、前段第一加算ユニット２０４の処理内容を説明する。
【０２０２】
前段第一加算ユニット２０４は、特に加算処理を行わず、データをスルーして出力する。具体的には、前段第一加算ユニット２０４は、入力データin1、in2、in3を、それぞれ、sel6、sel7、sel8として出力する。また、制御信号は、第１サイクル目より１クロックずつ順に出力される。
【０２０３】
図３０を用いて、前段転置ユニット２０５の処理内容を説明する。
【０２０４】
前段転置ユニット２０５は、５点DFT/IDFTのデータの転置処理を行う。
【０２０５】
具体的には、第１サイクルにおいて、in1、in2、in3として入力されたデータX(0,0)、X(0,1)、X(0,2)が、それぞれ、Sel_1_5、Sel_1_6、Sel_1_7として出力され、遅延回路Dに入力される。
【０２０６】
次に、第２サイクルにおいては、in1、in2、in3として入力されたデータX(1,0)、X(1,1)、X(1,2)が、それぞれ、Sel_1_1、Sel_1_2、Sel_1_4として出力され、遅延回路Dに入力される。
【０２０７】
次に、第３サイクルにおいては、in1、in2、in3として入力されたデータX(2,0)、X(2,1)、X(2,2)が、それぞれ、Sel_1_1、Sel_1_2、Sel_1_4として出力され、遅延回路Dに入力される。
【０２０８】
次に、第４サイクルにおいては、in1、in2、in3として入力されたデータX(3,0)、X(3,1)、X(3,2)が、それぞれ、Sel_1_1、Sel_1_2、Sel_1_4として出力され、遅延回路Dに入力される。
【０２０９】
次に、第５サイクルにおいては、in1、in2、in3として入力されたデータX(4,0)、X(4,1)、X(4,2)が、それぞれ、Sel_1_1、Sel_1_2、Sel_1_4として出力され、遅延回路Dに入力される。同時に、D_Sel_1_1として、C(0,01,1)と統合されたX(1,0)が出力され、これはSel_2_1として出力される。
【０２１０】
次に、第６サイクルにおいては、D_Sel_1_1、D_Sel_1_2として、C(0,01,2)と統合されたX(2,0)、C(0,01,1)と統合されたX(1,1)が、それぞれ、出力される。このうち、C(0,01,2)と統合されたX(2,0)は、Sel_2_2として出力される。一方、C(0,01,1)と統合されたX(1,1)は、Sel_2_1として出力される。このように、前段転置ユニット２０５は、入力されたデータの順序を入れ替えて出力する。
【０２１１】
次に、第７サイクルにおいては、D_Sel_1_1、D_Sel_1_2として、C(0,01,3)と統合されたX(3,0)、C(0,01,1)と統合されたX(2,1)が、それぞれ、出力される。また、C(0,01,3)と統合されたX(3,0)は、Sel_2_3として出力される。C(0,01,1)と統合されたX(2,1)は、Sel_2_2として出力される。
【０２１２】
次に、第８サイクルにおいては、D_Sel_1_1、D_Sel_1_2、D_Sel_1_4として、C(0,01,4)と統合されたX(4,0)、C(0,01,1)と統合されたX(3,1)、 C(0,01,1)と統合されたX(1,2)が、それぞれ、出力される。また、C(0,01,4)と統合されたX(4,0)は、Sel_2_4として出力される。C(0,01,1)と統合されたX(3,1)は、Sel_2_3として出力される。C(0,01,1)と統合されたX(1,2)は、Sel_2_1として出力される。
【０２１３】
次に、第９サイクルにおいては、D_Sel_1_2、D_Sel_1_4として、C(0,01,1)と統合されたX(4,1)、C(0,01,1)と統合されたX(2,2)が、それぞれ、出力される。また、C(0,01,1)と統合されたX(4,1)は、Sel_2_4として出力される。C(0,01,1)と統合されたX(2,2)は、Sel_2_2として出力される。
【０２１４】
次に、第１０サイクルおいては、D_Sel_1_4として、C(0,01,1)と統合されたX(3,2)が出力される。ここで、このデータはSel_2_3としても出力される。
【０２１５】
次に、第１１サイクルにおいては、D_Sel_1_4として、C(0,01,1)と統合されたX(4,2)が出力される。ここで、このデータは、Sel_2_4としても出力される。また、同時にSel_3_1として、C(0,01,1)と統合されたX(1,0)が出力され、Sel_3_2として、C(0,01,2)と統合されたX(2,0)が出力され、Sel_3_3として、C(0,01,3)と統合されたX(3,0)が出力され、 Sel_3_4として、C(0,01,4)と統合されたX(4,0)が出力される。これらデータからは制御信号が分離され、データだけがoutとして出力される。すなわち、out1としてX(1,0)が出力され、out2としてX(2,0)が出力され、out3としてX(3,0)が出力され、out4としてX(4,0)が出力される。さらに、C_outとしてC(0,01,0)が出力される。
【０２１６】
次に、第１２サイクルにおいては、Sel_3_1として、C(0,01,1)と統合されたX(1,1)が出力される。また、Sel_3_2として、C(0,01,2)と統合されたX(2,1)が出力される。また、Sel_3_3として、C(0,01,3)と統合されたX(3,1)が出力される。また、Sel_3_4として、C(0,01,4)と統合されたX(4,1)が出力される。これらデータからは制御信号が分離され、データだけがoutとして出力される。すなわち、out1としてX(1,1)が出力され、out2としてX(2,1)が出力され、out3としてX(3,1)が出力され、out4としてX(4,1)が出力される。さらに、C_outとして、C(0,01,1)が出力される。
【０２１７】
次に、第１３サイクルにおいては、Sel_3_1として、C(0,01,0)と統合されたX(0,0)が出力される。また、Sel_3_2として、C(0,01,1)と統合されたX(0,1)が出力される。これらデータからは制御信号が分離され、データだけがoutとして出力される。すなわち、out1としてX(0,0)が出力され、out2としてX(0,1)が出力される。さらに、C_outとしてC(0,01,2)が出力される。
【０２１８】
次に、第１４サイクルにおいては、Sel_3_1として、C(0,01,1)と統合されたX(1,2)が出力される。また、Sel_3_2として、C(0,01,2)と統合されたX(2,2)が出力される。また、Sel_3_3として、C(0,01,3)と統合されたX(3,2)が出力される、また、Sel_3_4としてC(0,01,4)と統合されたX(4,2)が出力される。これらデータからは制御信号が分離され、データだけがoutとして出力される。すなわち、out1としてX(1,2)が出力され、out2としてX(2,2)が出力され、out3としてX(3,2)が出力され、out4としてX(4,2)が出力される。
【０２１９】
さらに、C_outとしてC(0,01,3)が出力される。
【０２２０】
最後に、第１５サイクルにおいては、Sel_3_1として、C(0,01,0)と統合されたX(0,2)が出力される。このデータからは制御信号が分離され、データだけがoutとして出力される。すなわち、out1として、X(0,2)が出力される。さらに、C_outとしてC(0,01,4)が出力される。
【０２２１】
また、制御信号は、第１１サイクル目より、１クロックごとに１つずつ出力される。
【０２２２】
図３１を用いて、前段第二加算ユニット２０６の処理内容を説明する。
【０２２３】
前段第二加算ユニット２０６は、図１２に示したa0、a1、a2、a3、a4を算出する処理を行う。
【０２２４】
具体的には、前段第二加算ユニット２０６での５点DFT/IDFT用処理での２サイクル目に、regr1、regr3、regr4、 regr5として、それぞれ、X(1,0)、X(2,0)、X(3,0)、X(4,0)が出力される。また、加算器５２がX(1,0)+X(2,0)を計算し、その計算結果a1(0)をout1として出力する。また、加算器５３がX(1,0)-X(2,0)を計算し、その計算結果a4(0)をout2として出力する。また、加算器５４がX(3,0)+X(4,0)を計算し、その計算結果a2(0)をout3として出力する。また、加算器５５がX(3,0)-X(4,0)を計算し、その計算結果a3(0)をout4として出力する。ここで、aに付随する()内の数字は系列番号を示す。例として、a1(0)は、系列0の入力Xの途中計算結果a1であることを示す。
【０２２５】
３サイクル目では２サイクル目と同様の処理が行われ、a1(1)、a4(1)、a2(1)、a3(1)が出力される。
【０２２６】
４サイクル目では、前段第二加算ユニット２０６は、a(0)、a(1)を出力する。具体的には、regr1、regr3として、それぞれ、X(0,0)、X(0,1)が出力される。それらは、それぞれsel1、sel4として出力される。加算器５２および加算器５３は、それぞれ、sel1、sel4に０を加算し、その加算された値を、out1、out2として出力する。
【０２２７】
５サイクル目では、２、３サイクル目と同様の処理が行われ、a1(2)、a4(2)、a2(2)、a3(2)が出力される。
【０２２８】
６サイクル目では、a(2)が出力される。具体的には、regr1としてX(0,2)が出力され、X(0,2)がsel1として出力され、加算器５２が、sel1に０を加算し、その加算結果をout1として出力する。
【０２２９】
また、制御信号は、第２サイクル目より１クロックごとに１つずつ出力される。
【０２３０】
図３２を用いて、前段第三加算ユニット２０７の処理内容を説明する。
【０２３１】
前段第三加算ユニット２０７では、図１２に示したc0からc5を算出する処理を行う。
【０２３２】
具体的には、第１サイクル目において、加算器６２は、a1(0)-a2(0)を行って算出結果c2(0)を得て、c2(0)をout1として出力する。また、加算器６５は、a3(0)+a(4)を行って算出結果c5(0)を得て、c5(0)をout4として出力する。また、クロスバ６１は、a3(0)、a4(0)を、それぞれ、sel4、sel7として出力する。加算器６３は、sel4に０を加算し、加算結果c3(0)をout2として出力する。また、加算器６４は、sel7に０を加算し、加算結果c4(0)をout3として出力する。
【０２３３】
次に、第２サイクル目においては、第１サイクル目と同様の処理が行われ、c2(1)、c3(1)、c4(1)、c5(1)が、それぞれ、out1、out2、out3、out4として出力される。
【０２３４】
次に、第３サイクル目においては、in1、in2のデータa0(0)とa0(1)、および、regr1、regr2、regr3、regr4としてそれぞれ出力されるa1(0)、a2(0)、a1(1)、a2(1)を使い、c0(0)、c1(0)、c0(1)、c1(1)が、それぞれ算出される。
【０２３５】
具体的には、加算器６２が、a0(0)+a1(0)+a2(0)を計算して計算結果c0(0)を得て、c0(0)をout1として出力する。また、加算器６３が、a1(0)+a2(0)を計算して計算結果c1(0)を得て、c1(0)をout2として出力する。また、加算器６４が、a0(1)+a1(1)+a2(1)を計算して計算結果c0(1)を得て、c0(1)をout3として出力する。また、加算器６５が、a1(1)+a2(1)を計算して計算結果c1(1)を得て、c1(1)をout4として出力する。
【０２３６】
次に、第４サイクル目においては、第１、２サイクル目と同様の処理が行われ、c2(2)、 c3(2)、c4(2)、c5(2)が、それぞれ、out1、out2、out3、out4として出力される。
【０２３７】
最後に、第５サイクル目においては、第３サイクル目と同様のほぼ同様の処理が行われ、c0(2)、c1(2)が得られる。
【０２３８】
また、制御信号は、第１サイクル目より１クロックごとに１つずつ出力される。
【０２３９】
図３３を用いて、制御ユニット２０９、乗算器２０８の処理内容を説明する。制御ユニット２０９と乗算器２０８では、図１２に示したm0からm5までの係数を求める処理を行う。
【０２４０】
具体的には、第１サイクル目では、乗算器２０８は、入力されたc2(0)、c3(0)、c4(0)、c5(0)に、それぞれ、T5_2、T5_3、T_5_4、T5_5の係数を乗算する。さらに、乗算器２０８は、c3(0)、c4(0)、c5(0)に関しては、上記係数をかけた後に、純虚数を乗算する。以上により、m2(0)、m3(0)、m4(0)、m5(0)が算出され、これらは、それぞれ、out1、out2、out3、out4として出力される。
【０２４１】
第２サイクル目では、第１サイクル目と同様の処理が行われ、m2(1)、m3(1)、m4(1)、m5(1)のそれぞれが算出され、これらはout1、out2、out3、out4として出力される。
【０２４２】
第３サイクル目では、乗算器２０８は、入力されたc0(0)、c1(0)、c0(1)、c1(1)に対し、それぞれ、T5_0、T5_1、T5_0、T5_1の係数を乗算する処理を行い、m0(0)、m1(0)、m0(1)、m1(1)を得る。これらはそれぞれ、out1、out2、out3、out4として出力される。
【０２４３】
第４サイクル目では、第１サイクル目と同様の処理が行われ、m2(2)、m3(2)、m4(2)、m5(2)が算出され、これらは、それぞれ、out1、out2、out3、out4として出力される。
【０２４４】
第５サイクル目では、第３サイクル目と同様の処理が行われ、m0(2)、m1(2)が得られる。これらは、それぞれ、out1、out2として出力される。
【０２４５】
また、制御信号は、第１サイクル目より１クロックごとに１つずつ出力される。
【０２４６】
図３４を用いて、後段第一加算ユニット２１０の処理内容を説明する。本ユニットでは図１２に示したn0からn4を求める処理を行う。
【０２４７】
具体的には、第１サイクル目では、m2(0)が、sel1さらに言えばn2(0)として出力される。さらに、加算器８２が、m3(0)+m5(0)を計算し、その計算結果n3(0)をadd_s1として出力する。また、加算器８３が、m4(0)+m5(0)を計算し、その計算結果n4(0)をadd_s2として出力する。クロスバ８５は、n2(0)、n3(0)、n4(0)を、それぞれ、out1、out2、out3として出力する。
【０２４８】
第２サイクル目では、第１サイクルと同様の処理が行われ、n2(1)、n3(1)、n4(1)が得られる。これらはそれぞれ、out1、out2、out3として出力される。
【０２４９】
第３サイクル目では、sel1、sel2さらに言えばn0(0), n0(1)として、m0(0)、m0(1)がそれぞれ出力される。さらに、加算器８２が、m0(0)+m1(0)を計算し、その計算結果n1(0)をadd_s1として出力する。また、加算器８３が、m0(1)+m1(1)を計算し、その計算結果n1(1)をadd_s2として出力する。クロスバ８５は、n0(0)、n0(1)、n1(0)、n1(1)を、それぞれ、out1、out2、out3、out4に出力する。
【０２５０】
第４サイクル目では、第１、２サイクル目と同様の処理が行われ、n2(2)、n3(2)、n4(2)が得られる。これらはそれぞれ、out1、out2、out3として出力される。
【０２５１】
第５サイクル目では、第３サイクル目と同様の処理が行われ、n0(2)、n1(2)が得られる。これらはそれぞれ、out1、out2として出力される。
【０２５２】
また、制御信号は、第１サイクル目より、１クロックごとに１つずつ出力される。
【０２５３】
図３５を用いて、後段第二加算ユニット２１１の処理内容を説明する。
【０２５４】
後段第二加算ユニット２１１では、図１２に示したy0からy4を計算する。
【０２５５】
具体的には、後段第二加算ユニット２１１は、第１サイクル目、第２サイクル目では、特に加算処理を行わず、第３サイクル目において、加算器９０２がn1(0)+n2(0)+n4(0)を計算し、その計算結果y1(0)をadd_s1として出力する。また、加算器９０３がn1(0)+n2(0)-n4(0)を計算し、その計算結果y4(0)をadd_s2として出力する。また、加算器９０４がn1(0)-n2(0)+n3(0)を計算し、その計算結果y2(0)をadd_s3として出力する。また、加算器９０５がn1(0)-n2(0)-n3(0)を計算し、その計算結果y3(0)をadd_s4として出力する。これらはそれぞれ、out1、out2、out3、out4として出力される。
【０２５６】
第４サイクル目においては、第３サイクル目と同様の処理が行われ、y(1,1)、y(4,1)、y(2,1)、y(3,1)が得られる。これらはそれぞれ、out1、out2、out3、out4として出力される。
【０２５７】
第５サイクル目においては、第３、４サイクル目と同様の処理が行われ、y(1,2)、y(4,2)、y(2,2)、y(3,2)が得られる。これらはそれぞれ、out1、out2、out3、out4として出力される。
【０２５８】
第６サイクル目においては、sel1、sel4、sel7として、それぞれ、n0(0)、n0(1)、n0(2)が出力される。また、加算器９０２は、sel1に０を加算し、その加算結果y(0,0)をadd_s1として出力する。また、加算器９０３は、sel4に０を加算し、その加算結果y(0,1)をadd_s2として出力する。また、加算器９０４は、sel7に０を加算し、その加算結果y(0,2)をadd_s3として出力する。これらはそれぞれ、out1、out2、out3として出力される。
【０２５９】
また、制御信号は、第３サイクル目より１クロックごとに１つずつ出力される。
【０２６０】
図３６を用いて、後段転置ユニット２１２の処理内容を説明する。
【０２６１】
後段転置ユニット２１２は、入力されたデータを並べ替える処理を行う。
【０２６２】
具体的には、第１サイクル目では、入力されたy(1,0)、y(4,0)、y(2,0)、y(3,0)は、それぞれ、制御信号C(0,01,0)と統合され、Sel_1_1、Sel_1_2、Sel_1_3、Sel_1_4として出力される。また、y(1,0)は、Sel_2_1として出力される。
【０２６３】
第２サイクル目では、入力されたy(1,1)、y(4,1)、y(2,1)、y(3,1)は、それぞれ、制御信号C(0,01,1)と統合され、Sel_1_1、Sel_1_2、Sel_1_3、Sel_1_4として出力される。また、D_Sel_1_1として、C(0,01,0)と統合されたy(4,0)が出力され、このデータは、さらにSel_2_1としても出力される。一方、Sel_1_1として出力されたy(1,1)は、Sel_2_2としても出力される。
【０２６４】
第３サイクル目では、入力されたy(1,2)、y(4,2)、y(2,2)、y(3,2)は、それぞれ、制御信号C(0,01,2)と統合され、Sel_1_1、Sel_1_2、Sel_1_3、Sel_1_4として出力される。また、D_Sel_1_1、D_Sel_1_2として、それぞれ、C(0,01,1)と統合されたy(4,1)、C(0,01,0)と統合されたy(2,0)が出力される。さらに、Sel_2_1、Sel_2_2、Sel_2_3として、それぞれ、C(0,01,0)と統合されたy(2,0)、C(0,01,1)と統合されたy(4,1)、C(0,01,2)と統合されたy(1,2)が出力される。
【０２６５】
第４サイクル目では、入力されたy(0,0)、y(0,1)、y(0,2)は、それぞれ、制御信号C(0,01,3)と統合され、Sel_1_5、Sel_1_6、Sel_1_7として出力され、その後、Sel_4_1、Sel_4_2、Sel_4_3として出力される。これらの信号では、制御信号とデータが分離され、データだけがoutとして出力される。すなわち、y(0,0)、y(0,1)、y(0,2)が、それぞれ、out1、out2、out3として出力される。一方、D_Sel_1_1、D_Sel_1_2、D_Sel_1_3としては、それぞれ、C(0,01,2)と統合されたy(4,2)、C(0,01,1)と統合されたy(2,1)、C(0,01,0)と統合されたy(3,0)が出力される。これらは、それぞれ、Sel_2_3、Sel_2_2、Sel_2_1として出力される。さらに、D_Sel_2_1、D_Sel_2_2、D_Sel_2_3として、C(0,01,0)と統合されたy(1,0)、C(0,01,1)と統合されたy(1,1)、C(0,01,2)と統合されたy(1,2)が出力され、これらはそれぞれSel_3_1、 Sel_3_2、Sel_3_3として出力される。
【０２６６】
第５サイクル目では、D_Sel_1_2、D_Sel_1_3として、それぞれ、C(0,01,2)と統合されたy(2,2)、C(0,01,1)と統合されたy(3,1)が出力され、これらはそれぞれ、Sel_2_3、 Sel_2_2として出力される。一方、D_Sel_2_1、D_Sel_2_2、D_Sel_2_3としては、C(0,01,0)と統合されたy(4,0)、C(0,01,1)と統合されたy(4,1)、C(0,01,2)と統合されたy(4,2)が出力され、これらはそれぞれ、Sel_3_1、Sel_3_2、Sel_3_3として出力される。さらに、Sel_4_1、Sel_4_2、Sel_4_3としては、それぞれ、C(0,01,0)と統合されたy(1,0)、C(0,01,1)と統合されたy(1,1)、C(0,01,2)と統合されたy(1,2)が出力される。これらの信号では制御信号とデータが分離され、データだけがoutとして出力される。すなわち、y(1,0)、y(1,1)、y(1,2)が、out1、out2、out3として出力される。
【０２６７】
第６サイクル目では、D_Sel_1_3として、C(0,01,2)と統合されたy(3,2)が出力され、これはSel_2_3として出力される。また、D_Sel_2_1、D_Sel_2_2、D_Sel_2_3としては、C(0,01,0)と統合されたy(2,0)、C(0,01,1)と統合されたy(2,1)、C(0,01,2)と統合されたy(2,2)が出力され、これらはそれぞれ、Sel_3_1、Sel_3_2、Sel_3_3として出力される。さらに、Sel_4_1、Sel_4_2、Sel_4_3としては、それぞれ、C(0,01,0)と統合されたy(4,0)、C(0,01,1)と統合されたy(4,1)、C(0,01,2)と統合されたy(4,2)が出力される。これらの信号では、制御信号とデータが分離され、データだけがoutとして出力される。すなわち、y(4,0)、y(4,1)、y(4,2)が、out1、out2、out3として出力される。
【０２６８】
第７サイクル目では、D_Sel_2_1、D_Sel_2_2、D_Sel_2_3として、C(0,01,0)と統合されたy(3,0)、C(0,01,1)と統合されたy(3,1)、C(0,01,2)と統合されたy(3,2)が出力され、これらはそれぞれSel_3_1、Sel_3_2、Sel_3_3として出力される。さらに、Sel_4_1、Sel_4_2、Sel_4_3としては、それぞれ、C(0,01,0)と統合されたy(2,0)、C(0,01,1)と統合されたy(2,1)、C(0,01,2)と統合されたy(2,2)が出力される。これらの信号では、制御信号とデータが分離され、データだけがoutとして出力される。すなわち、y(2,0)、y(2,1)、y(2,2)が、out1、out2、out3に出力される。
【０２６９】
第８サイクル目では、Sel_4_1、Sel_4_2、Sel_4_3として、それぞれ、C(0,01,0)と統合されたy(3,0)、C(0,01,1)と統合されたy(3,1)、C(0,01,2)と統合されたy(3,2)が出力される。これらの信号では、制御信号とデータが分離され、データだけがoutとして出力される。すなわち、y(3,0)、y(3,1)、y(3,2)が、out1、out2、out3として出力される。
【０２７０】
また、制御信号は、４サイクル目より、１クロックごとに１つずつ出力される。
【０２７１】
図３７を用いて、後段第三加算ユニット２１３の処理内容を説明する。
【０２７２】
後段第三加算ユニット２１３では、入力されたデータを１クロックの遅延をつけて出力するだけで、特に加算処理を行わない。具体的には、遅延回路Dによって1クロック遅延されたin1、in2、in3のデータが、sel5、sel6、sel7として出力され、その後、out1、out2、out3として出力される。
【０２７３】
このように、演算装置２００は、５点DFT/IDFTを指示する制御信号を受け付けると、５点DFT/IDFTを実行する。
【０２７４】
（９点DFT/IDFT）
次に、演算装置２００による９点DFT/IDFTの処理を説明する。
【０２７５】
図３８を用いて、前段第一加算ユニット２０４の処理内容を説明する。
【０２７６】
前段第一加算ユニット２０４は、図１３に示したa1からa8の係数を算出する処理を行う。
【０２７７】
具体的には、第１サイクル目では、加算器３５および加算器３６が、それぞれ、X(1)+X(8)、X(1)-X(8)の処理を行うことにより、a1、a2を算出し、それらを、out1、out2として出力する。
【０２７８】
次に、第２サイクル目では、加算器３２、加算器３３、加算器３５、および、加算器３６が、それぞれ、X(4)+X(5)、X(4)-X(5)、X(2)+X(7)、X(2)-X(7)を行うことにより、a3、a4、a5、a6をそれぞれ算出する。これらデータは、それぞれ、out1、out2、out3、out4として出力される。
【０２７９】
次に第３サイクル目では、加算器３５および加算器３６が、それぞれ、X(3)+X(6)、X(3)-X(6)を計算し、a7、a8を得る。これらはout3、out4として出力される。さらに、X(0)がsel6として出力され、その後、out1として出力する。
【０２８０】
図３９を用いて、前段転置ユニット２０５の処理内容を説明する。
【０２８１】
前段転置ユニット２０５は、特にデータの並べ替え処理などは行わずに、入力されたデータを出力する。具体的には、 in1、in2、in3、in4として入力されたデータは、それぞれ、Sel_1_1、Sel_1_2、Sel_1_3、Sel_1_4として出力され、次に、Sel_2_1、Sel_2_2、Sel_2_3、Sel_2_4として出力され、さらに、D_dt_1、D_dt_2、D_dt3、D_dt_4として出力され、最後にout1、out2、out3、out4として出力される。
【０２８２】
図４０を用いて、前段第二加算ユニット２０６の処理内容を説明する。
【０２８３】
前段第二加算ユニット２０６は、図１３に示したa7'、a8'、および、a9からa16を算出する処理を行う。
【０２８４】
具体的には、第1サイクル目では、加算処理が行われず、第２サイクル目において、加算器５２、加算器５３、加算器５４、加算器５５が、それぞれ、a1+a3+a5、a5-a1、a1-a3、a5-a3を計算して、算出結果a15、a9、a10、a11を出力する。それらはout1、out2、out3、out4として出力される。
【０２８５】
次に、第３サイクル目において、加算器５２、加算器５３、加算器５４、加算器５５が、それぞれ、a6-a4+a2、-a6-a4、a2-a6、a2-a4を計算して、算出結果a16、a14、a12、a13を出力する。これらはout1、out2、out3、out4として出力される。
【０２８６】
最後に、第４サイクル目においては、X0'、a7、a8は、それぞれ、sel1、sel4、sel6として出力され、その後、加算器５２、加算器５３、加算器５４において０が加算され、その後、それぞれ、out1、out2、out3として出力される。
【０２８７】
図４１を用いて、前段第三加算ユニット２０７の処理内容を説明する。本処理では、図 １３に示したa17が算出される。
【０２８８】
具体的には、第１サイクル目においては、入力されたデータin1、in2、in3、in4が、それぞれ、sel1、sel4、sel6、sel9として出力され、その後、加算器６２、加算器６３、加算器６４、加算器６５にて０と加算され、その後、それぞれ、out1、out2、out3、out4として出力される。
【０２８９】
第２サイクル目においては、第１サイクル目と同様の処理が行われる。
【０２９０】
第３サイクル目においては、加算器６２が、a15+x0''+a7'を行い、加算結果a17をout1として出力する。さらに、x0''、a7'、a8が、第１、第２サイクル目と同様の方法で、それぞれ、out2、out3、out4として出力される。
【０２９１】
図４２を用いて、制御ユニット２０９、乗算器２０８の処理内容を説明する。
【０２９２】
制御ユニット２０９と乗算器２０８は、図１３においてmで示された係数を算出する処理を行う。
【０２９３】
具体的には、第１サイクル目において、乗算器２０８は、a15'、a9'、a10'、a11'と乗算係数T9_9、T9_1、T9_2、T9_3の乗算処理を行い、それぞれ、算出結果m9、m1、m2、m3を出力する。これらはそれぞれout2、out3、out4、out5として出力される。
【０２９４】
第２サイクル目においては、第１サイクル目と同様の処理が行われ、m10、m6、m4、m5という係数が得られる。
【０２９５】
第３サイクル目においては、第１、２サイクル目と同様の処理が行われ、a7'''、m7、m8、a17'という係数が得られる。さらに、X0'''係数が、sel1として出力され、その後、out1として出力される。
【０２９６】
図４３を用いて、後段第一加算ユニット２１０の処理内容を説明する。
【０２９７】
後段第一加算ユニット２１０は、図１３におけるc、および、xa0で示される係数を求める処理を行う。
【０２９８】
具体的には、第１サイクル目において、m9が、sel1として出力され、その後out1として出力される。さらに、加算器８２、加算器８３、加算器８４が、それぞれ、m1+m2、m2-m3、m1+m3を計算し、それぞれ、計算結果c4、c2、c3を得る。これらは、それぞれ、out2、out3、out4として出力される。
【０２９９】
第２サイクル目においては、m10が、sel1として出力され、その後out1として出力される。さらに、加算器８２、加算器８３、加算器８４が、それぞれ、m4-m6、m5-m6、m4-m5を計算し、それぞれ、計算結果c8、c9、c10を得る。これらは、それぞれ、out2、out3、out4として出力される。
【０３００】
第３サイクル目においては、m8、a17'が、それぞれ、sel1、sel2として出力され、その後out1、out2として出力される。さらに、加算器８２、加算器８３が、それぞれ、x0''''-m7、x0''''+a7'''を計算し、それぞれ、計算結果c1、xa0を得る。これらは、それぞれ、out3、out4として出力される。
【０３０１】
図４４を用いて、後段第二加算ユニット２１１の処理内容を説明する。
【０３０２】
後段第二加算ユニット２１１は、図１３に示した、c7、c6、c5、c14、c11*i、c12*i、c13*i、および、m10''*iを算出する処理を行う。
【０３０３】
具体的には、第１サイクル、第２サイクル目では、特に加算処理は行われず、第３サイクル目において、加算器９０２がc1-c4-c2を行い、加算器９０３がc1+4+c3を行い、加算器９０４がc1+c2-c3を行い、加算器９０５がxa0-m9'を行い、それぞれ、c7、c6、c5、c14を得る。これらは、out1、out2、out3、out4にそれぞれ出力される。
【０３０４】
第４サイクル目においては、加算器９０２がc8+c9+m8'を計算し、加算器９０３がc8+c10-m8'を計算し、加算器９０４が-c9+c10+m8'を計算する。さらに、これらに対して、純虚数乗算器９０６、９０７、９０８が、それぞれ、純虚数を乗算し、その乗算結果を、それぞれ、out1、out2、ou3として出力する。
【０３０５】
第５サイクル目においては、a17''、m10'が、それぞれ、sel1、sel4として出力され、その後、加算器９０２、９０３にて０が加算されて出力される。さらに、これらに対して、純虚数乗算器９０６、９０７が、それぞれ、純虚数を乗算し、その乗算結果を、それぞれout1、out2として出力する。
【０３０６】
図４５を用いて、後段転置ユニット２１２の処理内容について説明する。
【０３０７】
後段転置ユニット２１２は、特に、入力されたデータの並べ替え処理などを行わない。
【０３０８】
具体的には、in1、in2、in3、in4として入力されたデータは、それぞれ、Sel_1_1、Sel_1_2、Sel_1_3、Sel_1_4として出力され、次に、Sel_2_1、Sel_2_2、Sel_2_3、Sel_2_4として出力され、さらに、Sel_1_1、Sel_4_2、Sel_4_3、Sel_4_4として出力され、最後にout1、out2、out3、out4として出力される。
【０３０９】
図４６を用いて、後段第三加算ユニット２１３の処理内容を説明する。
【０３１０】
後段第三加算ユニット２１３は、図１３においてyで示される出力を算出する。
【０３１１】
具体的には、第１サイクル目では特に加算処理は行われず、第２サイクル目において、加算器１１０２、加算器１１０３、加算器１１０６、加算器１１０７が、それぞれ、c5+c11*i、c5-c11*i、c6+c12*i、c6-c12*iを計算し、計算結果y8、y1、y7、y2を得る。これらは、それぞれ、out1、out2、out3、out4として出力される。
【０３１２】
第３サイクル目では、第２サイクル目と同様の処理が行われ、y5、y4、y6、y3が計算され、それぞれ、out1、out2、out3、out4として出力される。
【０３１３】
第４サイクル目では、a17'''が、sel5として出力され、その後、out1として出力される。
【０３１４】
このように、演算装置２００は、９点DFT/IDFTを指示する制御信号を受け付けると、９点DFT/IDFTを実行する。
【０３１５】
（１５点DFT/IDFT）
次に、演算装置２００による１５点DFT/IDFT処理内容を説明する。ここで、１５点DFT/IDFTは、乗算ユニットを除いては、３点DFT/IDFT処理及び５点DFT/IDFT処理の組み合わせで行うことができる。よって以降では、乗算ユニット以外のユニットでは３点DFT/IDFT、５点DFT/IDFTのどちらの処理を行うかについて示し、詳細な説明は省略する。
【０３１６】
まず、前段第一加算ユニット２０４は、３点DFT/IDFTの処理を行う。ここで、３点DFT/IDFTでは、１サイクルで入出力が完了するのに対し、１５点DFT/IDFTでは、３点DFT/IDFTの処理を５サイクル分繰り返して計算及び出力が行われる。
【０３１７】
前段転置ユニット２０５は、５点DFT/IDFTの処理を行う。
【０３１８】
前段第二加算ユニット２０６は、５点DFT/IDFTの処理を行う。
【０３１９】
前段第三加算ユニット２０７は、５点DFT/IDFTの処理を行う。
【０３２０】
図４７を用いて、制御ユニット２０９、乗算器２０８の処理内容の説明を行う。
【０３２１】
制御ユニット２０９と乗算器２０８は、図１４においてeで示される係数に乗算係数をかけ、mで示される係数を算出する処理を行う。
【０３２２】
具体的には、第１サイクル目では、乗算器２０８は、e2に対してT15_2を乗算し、m2係数を得る。これはout1として出力される。同時に、e3、e4、e5係数が入力され、乗算器２０８は、これらにT15_3、T15_4、T15_5を乗算する。さらに、これら係数に関しては、純虚数を乗算する処理を純虚数乗算器９０７、９０８、９０９が行いm3、m4、m5を得る。これらは、out2、out3、out4として出力される。
【０３２３】
第２サイクル目では、第１サイクル目と同様の処理が行われ、m8、m9、m10、m11係数が得られる。これらは、それぞれ、out1、out2、out3、out4として出力される。
【０３２４】
第３サイクル目では、e0、e1、e6、e7係数が入力され、それぞれにT15_0、T15_1、T15_6、T15_7が乗算され、m0、m1、m6、m7が算出される。これらはそれぞれ、out1、out2、out3、out4として出力される。
【０３２５】
第４サイクル目では、e15、e16、e17係数が入力され、これらにT15_15、T15_16、T15_17が乗算され、m15、m16、m17が算出される。これらはout2、out3、out4として出力される。同時にe14が入力され、これにT15_14係数が乗算される。さらに、純虚数乗算器９０６が、その乗算結果に純虚数を乗算し、その乗算結果をout1として出力する。
【０３２６】
第５サイクル目には、e12、e13係数が入力され、これにT15_12、T15_13係数が乗算される。さらに、純虚数乗算器９０６、９０７が、それぞれ、その乗算結果に純虚数を乗算し、その乗算結果を、out1、out2として出力する。
【０３２７】
後段第一加算ユニット２１０は、５点DFT/IDFTの処理を行う。
【０３２８】
後段第二加算ユニット２１１は、５点DFT/IDFTの処理を行う。
【０３２９】
後段転置ユニット２１２は、５点DFT/IDFTの処理を行う。
【０３３０】
後段第三加算ユニット２１３は、３点DFT/IDFTの処理を行う。
【０３３１】
このように、演算装置２００は、１５点DFT/IDFTを指示する制御信号を受け付けると、１５点DFT/IDFTを実行する。
【０３３２】
（その他の実施形態）
図２８に本発明の第２実施形態を示す。本実施形態は、離散フーリエ変換装置（演算装置）２００と、離散フーリエ変換装置２００を制御するＣＰＵ１と、データを格納するメモリユニット２と、を含む。
【０３３３】
本実施形態においては、ＣＰＵ１が、ＣＰＵ-メモリユニットアドレス信号にて、メモリユニット２にアクセスするアドレスを発行すると、メモリユニット２は、ＣＰＵ-メモリユニットデータ信号にて、発行されたアドレスに対応したデータをＣＰＵ１に出力する。
【０３３４】
次に、ＣＰＵ１は、上記の３、５、９、１５点DFT/IDFTの制御信号とともにデータを離散フーリエ変換装置２００に出力する。
【０３３５】
離散フーリエ変換装置２００は、ＣＰＵ１から制御信号とデータを受け取ると、制御信号に従ってDFT/IDFTを実行し、その結果をＣＰＵ１に返す。
【０３３６】
このような実施形態においては、離散フーリエ変換装置２００がサポートする３、５、９、１５点DFT/IDFT以外の点数のDFT/IDFTをCPU１が行うことにより、さらにDFT点数の種類を増やすことができる。
【０３３７】
上記各実施形態によれば、３、５、９、１５点のDFT/IDFTを共通の回路で処理できる。このため、３、５、９、１５点のDFT/IDFTの回路を、それぞれ、個別の回路で構成した場合と比較して、乗算器と加算器の数を削減することができる点である。
【０３３８】
また、３、５、９、１５点のDFT/IDFTに対し、設計する回路は１つの回路で済む。このため、３、５、９、１５点のDFT/IDFTの回路を、それぞれ、個別の回路で構成した場合と比較して、設計及び実装に要する時間が短縮できる。
【０３３９】
また、３、５、９、１５点という異なる点数のDFT/IDFTが行われても、データが各ユニットに出力されるタイミングを合わせているので、各ユニットは、DFT/IDFTのポイント数に関わらず、予め定められたタイミングで動作することができる。このため、各ユニットの動作開始タイミングを、DFT/IDFTのポイント数に応じて変更するような制御を行うことなく、異なる点数のDFT/IDFTを共通の回路を用いて行うことが可能になる。
［産業上の利用可能性］
本実施形態の活用例として、LTEで必要となる無線信号処理を実行する基地局装置が挙げられる。
【符号の説明】
【０３４０】
１      ＣＰＵ
２      メモリユニット
２００      離散フーリエ変換装置（演算装置）
２０１      前加算ユニット
２０２      乗算ユニット
２０３      後加算ユニット
２０４      前段第一加算ユニット
２０５      前段転置ユニット
２０６      前段第二加算ユニット
２０７      前段第三加算ユニット
２０８      乗算器
２０９      制御ユニット
２１０      後段第一加算ユニット
２１１      後段第二加算ユニット
２１２      後段転置ユニット
２１３      後段第三加算ユニット
【図１】
0005493646.tif 000004
【図２】
0005493646.tif 000005
【図３】
0005493646.tif 000006
【図４】
0005493646.tif 000007
【図５】
0005493646.tif 000008
【図６】
0005493646.tif 000009
【図７】
0005493646.tif 000010
【図８】
0005493646.tif 000011
【図９】
0005493646.tif 000012
【図１０】
0005493646.tif 000013
【図１１】
0005493646.tif 000014
【図１２】
0005493646.tif 000015
【図１３】
0005493646.tif 000016
【図１４】
0005493646.tif 000017
【図１５】
0005493646.tif 000018
【図１６】
0005493646.tif 000019
【図１７】
0005493646.tif 000020
【図１８】
0005493646.tif 000021
【図１９】
0005493646.tif 000022
【図２０】
0005493646.tif 000023
【図２１】
0005493646.tif 000024
【図２２】
0005493646.tif 000025
【図２３】
0005493646.tif 000026
【図２４】
0005493646.tif 000027
【図２５】
0005493646.tif 000028
【図２６】
0005493646.tif 000029
【図２７】
0005493646.tif 000030
【図２８】
0005493646.tif 000031
【図２９】
0005493646.tif 000032
【図３０】
0005493646.tif 000033
【図３１】
0005493646.tif 000034
【図３２】
0005493646.tif 000035
【図３３】
0005493646.tif 000036
【図３４】
0005493646.tif 000037
【図３５】
0005493646.tif 000038
【図３６】
0005493646.tif 000039
【図３７】
0005493646.tif 000040
【図３８】
0005493646.tif 000041
【図３９】
0005493646.tif 000042
【図４０】
0005493646.tif 000043
【図４１】
0005493646.tif 000044
【図４２】
0005493646.tif 000045
【図４３】
0005493646.tif 000046
【図４４】
0005493646.tif 000047
【図４５】
0005493646.tif 000048
【図４６】
0005493646.tif 000049
【図４７】
0005493646.tif 000050
【図４８】
0005493646.tif 000051
【図４９】
0005493646.tif 000052