(57)【要約】変換を実行するためのデータ処理ユニットを作動させる方法は、少なくとも第１入力データ値および第２入力データ値に基づいて第１出力データ値および第２出力データ値を計算する工程を含む。上記方法は、第１バッファの位置から第１入力データ値および第２入力データ値を読み出す工程を含み、上記位置は、第１読み出しインデックスおよび第２読み出しインデックスに基づいて、第１読み出しアドレスおよび第２読み出しインデックスによって定められる。上記方法はまた、１つの書き込み周期の間に第２バッファの隣接するメモリ位置に上記第１出力データ値および上記第２出力データ値を書き込む工程も含む。さらに、上記方法は、上記第２バッファの位置から第３入力データ値および第４入力データ値を読み出す工程を含み、上記位置は、上記第１読み出しインデックス、上記第２読み出しインデックスそれぞれの、上記ビットのうちの少なくとも２つを交換することにより定められる第３読み出しアドレスおよび第４読み出しアドレスによって定められる。変換を実行するデータ処理ユニット、変換計算ユニット、および電子装置も記載される。【選択図】図２Ｂ
2010531504.tif 000002
【特許請求の範囲】
【請求項１】
変換を実行するためのデータ処理ユニットを作動させる方法であって、
前記方法は、
第１バッファ（３０２）の位置から第１入力データ値（ｘ１）を読み出す工程（４３０）であって、前記位置は、第１読み出しインデックスに基づいて第１読み出しアドレス（４２０）によって定められる、前記読み出し工程（４３０）と、
前記第１バッファ（３０２）の位置から第２入力データ値（ｘ２）を読み出す工程（４６０）であって、前記位置は、第２読み出しインデックスに基づいて第２読み出しアドレス（４５０）によって定められる、前記読み出し工程（４６０）と、
少なくとも前記第１入力データ値と前記第２入力データ値に基づいて、第１出力データ値および第２出力データ値（ｙ１、ｙ２）を計算する工程（４８０）と、
前記第１出力データ値および前記第２出力データ値を第２バッファ（３０３）に書き込む工程（４９０）と、
前記第２バッファ（３０３）の位置から第３入力データ値（ｘ１）を読み出す工程（４３０）であって、前記位置は、前記第１読み出しインデックスに基づいて第３読み出しアドレス（４２０）によって定められる、前記読み出し工程（４３０）と、
前記第２バッファ（３０３）の位置から第４入力データ値（ｘ２）を読み出す工程（４６０）であって、前記位置は、前記第２読み出しインデックスに基づいて第４アドレス（４５０）によって定められる、前記読み出し工程（４６０）と、
を含み、
前記第１出力データ値および前記第２出力データ値は、１つの書き込み周期の間に前記第２バッファの隣接するメモリ位置に書き込まれ、前記隣接する位置は第１書き込みアドレスによって定められ、前記第３読み出しアドレスは、前記第１読み出しインデックスの前記ビットのうちの少なくとも２つを交換する工程（５３０）によって定められ、前記第４の読み出しアドレスは、前記第２読み出しインデックスの前記ビットのうちの少なくとも２つを交換する工程（５３０）によって定められることを特徴とする、方法。
【請求項２】
前記第３読み出しアドレスは、前記第１読み出しインデックスの前記ビットのうちの２つを交換する工程によって定められ、前記第４読み出しアドレスは、前記第２読み出しインデックスの前記ビットのうちの２つを交換する工程によって定められる、請求項１に記載の方法。
【請求項３】
前記第１出力データ値および前記第２出力データ値を計算する工程はさらに、少なくとも１つ回転因子に基づいている、請求項１または請求項２のいずれか１項に記載の方法。
【請求項４】
第３バッファ（３０４）の位置から前記少なくとも１つの回転因子を読み出す工程（４７０）をさらに含む、請求項３に記載の方法。
【請求項５】
前記変換はサイズＮの変換であり、前記第１入力データ値および前記第２入力データ値を読み出す工程と、前記第１出力データ値および前記第２出力データ値を計算する工程と、１つの書き込み周期の間に前記第２バッファの隣接するメモリ位置に前記第１出力データ値および前記第２出力データ値を書き込む工程とは、前記変換の第１段階（２０１）の間にＮ／２回実行される、請求項１〜請求項４のいずれか１項に記載の方法。
【請求項６】
少なくとも前記第３入力データ値および前記第４入力データ値に基づいて第３出力データ値および第４出力データ値（ｙ１、ｙ２）を計算する工程（４８０）と、
前記第３出力データ値および前記第４出力データ値を、１つの書き込み周期の間に前記第１バッファ（３０２）の隣接するメモリ位置に書き込む工程（４９０）と、
をさらに含む、請求項１〜請求項５のいずれか１項に記載の方法。
【請求項７】
前記変換はサイズＮの変換であり、前記第３入力データ値および前記第４入力データ値を読み出す工程と、前記第３出力データ値および前記第４出力データ値を計算する工程と、１つの書き込み周期の間に前記第１バッファの隣接するメモリ位置に前記第３出力データ値および前記第４出力データ値を書き込む工程とは、前記変換の第２段階（２０２）の間にＮ／２回実行される、請求項６に記載の方法。
【請求項８】
２つの入力データ値を読み出す工程と、２つの出力データ値を計算する工程と、１つの書き込み周期の間にバッファの隣接するメモリ位置に前記２つの出力データ値を書き込む工程とは、前記変換の各段階（２０１、２０２、２０３）の間にＮ／２回実行される、請求項６または請求項７のいずれか１項に記載の方法。
【請求項９】
前記第１読み出しアドレスは、前記第１読み出しインデックスの前記ビットの順序を反転させることにより定められ、前記第２読み出しアドレスは、前記第２読み出しインデックスの前記ビットの順序を反転させることにより定められる、請求項１〜請求項８のいずれか１項に記載の方法。
【請求項１０】
前記変換は高速フーリエ変換である、請求項１〜請求項９のいずれか１項に記載の方法。
【請求項１１】
前記第１読み出しインデックスおよび前記第２読み出しインデックスは、前記第１データバッファと前記第２データバッファとのうちの少なくとも１つのアドレス値を含む、請求項１〜請求項１０のいずれか１項に記載の方法。
【請求項１２】
変換を実行するためのデータ処理ユニットであって、回路（３０１）を備え、
前記回路（３０１）は、
データ値を格納するための第１バッファ（３０２）の位置から第１入力データ値を読み出し、前記位置は第１読み出しインデックスに基づいて第１読み出しアドレスによって定められ、
前記第１バッファ（３０２）の位置から第２入力データ値を読み出し、前記位置は第２読み出しインデックスに基づいて第２読み出しアドレスによって定められ、
少なくとも前記第１入力データ値および前記第２入力データ値に基づいて、第１出力データ値および第２出力データ値を計算し、
前記第１出力データ値および前記第２出力データ値を、データ値を格納するための第２バッファ（３０３）に書き込み、
前記第２バッファ（３０３）の位置から第３入力データ値を読み出し、前記位置は前記第１読み出しインデックスに基づいて第３読み出しアドレスによって定められ、
前記第２バッファ（３０３）の位置から第４入力データ値を読み出すように適合され、前記位置は前記第２読み出しインデックスに基づいて第４アドレスによって定められ、
１つの書き込み周期の間に前記第２バッファの隣接するメモリ位置に前記第１出力データ値および前記第２出力データ値を書き込むように適合され、前記隣接する位置は第１書き込みアドレスによって定められる、前記回路（３０１）と、
前記第１読み出しインデックスの前記ビットのうちの少なくとも２つを交換することによって前記第３読み出しアドレスを定め、前記第２読み出しインデックスの前記ビットのうちの少なくとも２つを交換することによって前記第４読み出しアドレスを定めるように適合されるアドレス生成器（３０５）と、
を特徴とする、データ処理ユニット。
【請求項１３】
前記アドレス生成器は、前記第１読み出しインデックスの前記ビットのうちの２つを交換することによって前記第３読み出しアドレスを定め、前記第２読み出しインデックスの前記ビットのうちの２つを交換することによって前記第４読み出しアドレスを定めるように適合される、請求項１２に記載のデータ処理ユニット。
【請求項１４】
前記回路はさらに、少なくとも１つ回転因子に基づいて前記第１出力データ値および前記第２出力データ値を計算するように適合される、請求項１２または請求項１３のいずれか１項に記載のデータ処理ユニット。
【請求項１５】
前記回路はさらに、回転因子を格納するための第３バッファ（３０４）の位置から前記少なくとも１つの回転因子を読み出すように適合される、請求項１４に記載のデータ処理ユニット。
【請求項１６】
前記変換はサイズＮの変換であり、前記回路は前記変換の第１段階の間にＮ／２回、前記第１入力データ値および前記第２入力データ値を読み出し、前記第１出力データ値および前記第２出力データ値を計算し、１つの書き込み周期の間に前記第２バッファの隣接するメモリ位置に前記第１出力データ値および前記第２出力データ値を書き込むように適合される、請求項１２〜請求項１５のいずれか１項に記載のデータ処理ユニット。
【請求項１７】
前記回路はさらに、少なくとも前記第３入力データ値および前記第４入力データ値に基づいて第３出力データ値および第４出力データ値を計算し、前記第３出力データ値および前記第４出力データ値を、１つの書き込み周期の間に前記第１バッファの隣接するメモリ位置に書き込むように適合される、請求項１２〜請求項１６のいずれか１項に記載のデータ処理ユニット。
【請求項１８】
前記変換はサイズＮの変換であり、前記回路は前記変換の第２段階の間にＮ／２回、前記第３入力データ値および前記第４入力データ値を読み出し、前記第３出力データ値および前記第４出力データ値を計算し、１つの書き込み周期の間に前記第１バッファの隣接するメモリ位置に前記第３出力データ値および前記第４出力データ値を書き込むように適合される、請求項１７に記載のデータ処理ユニット。
【請求項１９】
前記回路は前記変換の各段階の間にＮ／２回、２つの入力データ値を読み出し、２つの出力データ値を計算し、１つの書き込み周期の間にバッファの隣接するメモリ位置に前記２つの出力データ値を書き込むように適合される、請求項１７または請求項１８のいずれか１項に記載のデータ処理ユニット。
【請求項２０】
前記第１入力データ値と、
前記第２入力データ値と、
前記第１出力データ値と、
前記第２出力データ値と、
前記第１出力データ値および前記第２出力データ値の前記計算の中間結果と、
のうちの少なくとも１つを一時的に格納するように適合される少なくとも１つのレジスタユニット（３０６）をさらに含む、請求項１２〜請求項１９のいずれか１項に記載のデータ処理ユニット。
【請求項２１】
前記アドレス生成器は、制御信号を受信するように適合される入力ポートを含み、前記アドレス生成器は、前記制御信号に基づいて、前記第１読み出しインデックスの前記ビットのうちの少なくとも２つを交換し、前記第２読み出しインデックスの前記ビットのうちの少なくとも２つを交換するように適合される、請求項１２〜請求項２０のいずれか１項に記載のデータ処理ユニット。
【請求項２２】
前記アドレス生成器は、前記第１読み出しインデックスの前記ビットの順序を反転させることにより前記第１読み出しアドレスを定め、前記第２読み出しインデックスの前記ビットの順序を反転させることにより前記第２読み出しアドレスを定めるように適合される、請求項１２〜請求項２１のいずれか１項に記載のデータ処理ユニット。
【請求項２３】
前記変換は高速フーリエ変換である、請求項１２〜請求項２２のいずれか１項に記載のデータ処理ユニット。
【請求項２４】
前記第１読み出しインデックスおよび前記読み出し第２インデックスは、前記第１データバッファと前記第２データバッファとのうちの少なくとも１つのアドレス値を含む、請求項１２〜請求項２３に記載のデータ処理ユニット。
【請求項２５】
請求項１２〜請求項２４のいずれか１項に記載のデータ処理ユニットを含む変換計算ユニット。
【請求項２６】
請求項１２〜請求項２４のいずれか１項に記載のデータ処理ユニットと、
請求項２５に記載の変換計算ユニットと、
の少なくとも１つを含む電子装置。
【請求項２７】
前記電子装置は、携帯型または手持ち型の移動無線通信機器、移動無線端末、携帯電話（６００）、ポケットベル、発信機、電子手帳、スマートフォン、コンピュータ、組込み型ドライブ、携帯型ゲーム機、時計、基地局、または、基地局コントローラである、請求項２６に記載の電子装置。
【請求項２８】
前記電子装置は、ユニバーサル移動通信システム・ロングタームエボリューションの規格に則する、請求項２６または請求項２７のいずれか１項に記載の電子装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、デジタルデータプロセッサ分野に関し、特に、デジタルデータプロセッサにおける変換の計算に関する。
【背景技術】
【０００２】
様々な変換が、例えば、ユニバーサル移動通信システム・ロングタームエボリューション（ＵＭＴＳ  ＬＴＥ：Ｕｎｉｖｅｒｓａｌ  Ｍｏｂｉｌｅ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｙｓｔｅｍ  Ｌｏｎｇ  Ｔｅｒｍ  Ｅｖｏｌｕｔｉｏｎ）などの、直交周波数分割変調（ＯＦＤＭ：Ｏｒｔｈｏｇｏｎａｌ  Ｆｒｅｑｕｅｎｃｙ  Ｄｉｖｉｓｉｏｎ  Ｍｏｄｕｌａｔｉｏｎ）を利用する無線アクセス標準規格に則した装置における受信信号のデジタル信号処理のような、非常に様々なデータ処理アプリケーションにおいて利用されている。様々な変換はまた、例えば、信号解析、圧縮アルゴリズム、およびフィルタリングにおいて利用することも出来る。さらに、変換は、例えば、ユニバーサル移動通信システム（ＵＭＴＳ：Ｕｎｉｖｅｒｓａｌ  Ｍｏｂｉｌｅ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｓｙｓｔｅｍ）、移動通信のためのグローバルシステム（ＧＳＭ：Ｇｌｏｂａｌ  Ｓｙｓｔｅｍ  Ｆｏｒ  Ｍｏｂｉｌｅ  ｃｏｍｍｕｎｉｃａｔｉｏｎｓ)、汎用パケット無線サービス（ＧＰＲＳ：Ｇｅｎｅｒａｌ  Ｐａｃｋｅｔ  Ｒａｄｉｏ  Ｓｅｒｖｉｃｅ）、デジタル映像放送（ＤＶＢ：Ｄｉｇｉｔａｌ  Ｖｉｄｅｏ  Ｂｒｏａｄｃａｓｔｉｎｇ）のような、ＵＭＴＳ  ＬＴＥ以外の標準規格に則する装置における利用にも適用可能でありうる。変換を計算することは、比較的計算が複雑なデータ処理タスクであることもあり、従って、変換計算が可能な限り最適化されていることが処理性能全般にとって非常に重要であることが多い。
【０００３】
例えばフーリエ変換では、Ｎが２のべき乗である場合に、Ｎ／２、サイズ２の変換からなるそれぞれにおいて、対数ｌｏｇ２Ｎの計算段階でサイズＮの変換を低減することが出来ることは、当業者にはよく知られている。この計算の再構成は、Ｎ２からＮｌｏｇ２Ｎへと上記問題の大きさを低減する。フーリエ変換の場合、得られる計算方法は、高速フーリエ変換（ＦＦＴ：ｆａｓｔ  Ｆｏｕｒｉｅｒ  ｔｒａｎｓｆｏｒｍ）を意味する。
【０００４】
変換は、いわゆるバタフライダイアグラム（ｂｕｔｔｅｒｆｌｙ  ｄｉａｇｒａｍ）で表されることが多い。例示的なバタフライダイアグラムを、後に図２Ａとの関連において記載する。バタフライダイアグラムは、複数の計算カーネルを含む。こうした計算カーネル１００の例が図１において与えられている。図において、蝶に似ているように計算カーネルが示されうることが分かるであろう。
【０００５】
計算カーネル１００において実施されるバタフライ計算（ｂｕｔｔｅｒｆｌｙ  ｃａｌｃｕｌａｔｉｏｎ）への２つの入力データがｘ１およびｘ２で示されており、入力口１０１および１０２それぞれに供給される。バタフライ計算からの２つの出力データがｙ１およびｙ２で示されおり、出力口１０３および１０４それぞれにおいて見出されうる。この例示的なバラフライ演算の出力口１０３における出力データ値は、加算器１０５において、入力口１０１での入力データ値を入力口１０２での入力データ値に加算することによって得られる。出力口１０４での出力データ値は、乗算器１０７において、入力口１０２での入力データ値の符号を変更し、加算器１０６において、入力口１０１での入力データ値を乗算器１０７の結果に加算し、乗算器１０８において、加算器１０６の結果に、いわゆる回転因子（ＴＦ：ｔｗｉｄｄｌｅ  ｆａｃｔｏｒ）を乗じることによって得られる。
【０００６】
図１に示される計算カーネルの実現は単に、複数の可能な様々な実現のうちの１つの例を表しているにすぎないことが強調される。例示的な実現として、乗算は乗算器以外の手段によって行なわれてもよい。乗算は、シフト演算または加算演算のような、現在公知のいかなる方法に従っても行なわれてもよく、または、将来発見される乗算のためのいかなる方法によっても行なわれてもよい。
【０００７】
変換計算全体は蝶のような（Ｎ／２）ｌｏｇ２Ｎで構成されており、このことが、サイズ８のＦＦＴ計算２００が示される図２Ａにおいて例示されている。図２Ａでは蝶の描写が単純化されているため、図があまり雑然としていない。しかし、当然のことながら、例えば図１に示される加算器および乗算器が、図２Ａの実現においても存在する。
【０００８】
図２Ａには、３つの（＝ｌｏｇ２８）計算段階２０１、２０２、２０３があり、それぞれの計算段階は、４つの（＝８／２）バタフライ計算で構成されることに注意されたい。従って、変換演算の実行は、外部ループがｌｏｇ２Ｎ回反復され（変換段階ごとに１回の反復）、内部ループがＮ／２回反復される（バタフライ計算ごとに１回の反復）入れ子型ループ（ｎｅｓｔｅｄ  ｌｏｏｐ）として表わされうる。代替的に、変換演算の実行は、ｌｏｇ２Ｎ回の反復（変換段階ごとに１回の反復）とＮ／２回のバタフライ計算とが並行して計算される１つのループとして表されてもよい。図２Ａでは、変換計算の中間結果が、バッファ２０４、２０５、２０６に格納され、変換計算の最終結果が、バッファ２０７に格納される。幾つかの実現は、このタスクを遂行するために２つのバッファ全体を使用する。２つのバッファは、変換計算の異なる段階を通じて、読み出しバッファおよび書き込みバッファとしての役割を交互に果たす。さらなる幾つかの実現、いわゆる定位置変換（ｉｎ−ｐｌａｃｅ  ｔｒａｎｓｆｏｒｍ）は、１つのバッファのみを使用する。バッファ２０４、２０５、２０７内の異なる位置のアドレス２０８が、明確にするために、１０進表示およびビット表示の双方において与えられている。図２Ａには、各読み出し周期の間にどのバッファアドレスから読み出すのかを決定するために利用される、例示的な読み出しインデックス２０９、２１０、２１１も示されている。例えば、図２Ａにおいて与えられているインデックスおよびアドレスに従って、第１段階の（値が０および１の読み出しインデックス２０９に対応する）第１バタフライ計算は、バッファアドレス０および４からの入力データを使用するべきであり、第１段階の（値が２および３の読み出しインデックス２０９に対応する）第２バタフライ計算は、バッファアドレス２および６からの入力バッファを利用するべきである。さらに例示すれば、第２段階の（値が０および１の読み出しインデックス２１０に対応する）第１バタフライ計算は、図２Ａによれば、バッファアドレス０および２からの入力データを使用し、第２段階の（値が２および３の読み出しインデックス２１０に対応する）第２バタフライ計算は、バッファアドレス４および６からの入力データを使用するべきである。
【０００９】
図２Ａに示されるような変換演算の入力は、入力バッファ２０４から、ビットを反転させた（ｂｉｔ−ｒｅｖｅｒｓｅｄ）順序において読み出されるべきであることは、当業者には公知である。図では、第１段階の読み出しインデックス２０９のビット表示は、反転された場合のバッファアドレス２０８のビット表示に対応することが分かる。幾つかの変形が存在する。例えば、変換計算の入力は、入力バッファ２０４から、元の順序で読み出されてもよい。しかし、このことによって、結果的に、図２Ａに示されるものとは異なる実現となるであろう。
【００１０】
変換計算のための既存のソリューションに伴う１つの問題は、時間の消費である。例えば、各バタフライ計算について、２つの読み出しアクセスが、２つの入力バッファを取り出すために必要であり、２つの書き込みアクセスが、結果、すなわち２つの出力データを格納するために必要である。これにより、一般的に、各バタフライ計算のために少なくとも４つの周期が必要とされる。変換の大きさが非常に大きい（Ｎが１０２４〜８１９２の大きさであるのが一般的である）ので、各変換計算は、大量のバタフライ計算を含む。従って、バタフライ計算が大抵パイプライン方式により実行されるとしても、各バタフライ計算の実行時間は、変換の全計算時間にとって非常に重要である。
【００１１】
幾つかの実現は、１つの周期に２つの読み出しアクセスおよび／または２つの書き込みアクセスを処理することが可能なバッファ、例えば、２つ以上のアドレス入力、いわゆる２ポートメモリまたはデュアルポートメモリを含むバッファを使用する。このことが全計算時間を低減しうるとしても、この種のバッファは、一般的に、アドレス入力が１つのバッファより高価であり、従って、こうしたソリューションが常に望ましいわけではない。
【００１２】
他の実現は、各バッファを２つ以上のメモリバンクに分けることもあるが、これもまた、１つの周期に２つの読み出しアクセスおよび／または２つの書き込みアクセスを可能にする。こうしたソリューションによって、一般的に、バッファがメモリバンクに分けられないソリューションと比較して複雑さが増すことになる。
【００１３】
このように、全計算時間を低減するデータ処理の実現、および変換計算の方法に対する必要性がある。これは、望ましくは、実現に掛かるコストおよび複雑さが全く増すことなく、または、実現に掛かるコストおよび／または複雑さが僅かに増して達成されるべきであろう。
【発明の概要】
【発明が解決しようとする課題】
【００１４】
本発明の目的は、上記の不利益の少なくとも幾つかを未然に防ぎ、変換計算のための改善された方法およびプロセッサを提供することである。
【課題を解決するための手段】
【００１５】
本発明の第１の観点によれば、このことは、変換を実行するためのデータ処理ユニットを作動させる方法により達成される。上記方法は、第１バッファの位置から第１入力データ値を読み出す工程であって、上記位置は第１読み出しインデックスに基づいて第１読み出しアドレスによって定められる、上記読み出し工程と、上記第１バッファの位置から第２入力データ値を読み出す工程であって、上記位置は第２読み出しインデックスに基づいて第２読み出しアドレスによって定められる、上記読み出し工程と、を含む。上記方法は、少なくとも上記第１入力データ値と上記第２入力データ値に基づいて、第１出力データ値および第２出力データ値を計算する工程と、上記第１出力データ値および上記第２出力データ値を第２バッファに書き込む工程と、を含む。上記第１出力データ値および上記第２出力データ値は、１つの書き込み周期の間に上記第２バッファの隣接するメモリ位置に書き込まれ、上記隣接する位置は第１書き込みアドレスによって定められる。上記方法は、上記第２バッファの位置から第３入力データ値を読み出す工程であって、上記位置は上記第１読み出しインデックスに基づいて第３読み出しアドレスによって定められる、上記読み出し工程と、上記第２バッファの位置から第４入力データ値を読み出す工程であって、上記位置は上記第２読み出しインデックスに基づいて第４アドレスによって定められる、上記読み出し工程と、を含む。上記第３読み出しアドレスは、上記第１読み出しインデックスの上記ビットのうちの少なくとも２つを交換する工程によって定められ、上記第４の読み出しアドレスは、上記第２読み出しインデックスの上記ビットのうちの少なくとも２つを交換する工程によって定められる。データ処理ユニットはこれらの方法のステップを実施する。データ処理ユニットは１つ以上の物理的要素を含んでもよい。
【００１６】
本発明の第１の観点の幾つかの実施形態において、上記第３読み出しアドレスは、上記第１読み出しインデックスの上記ビットのうちの２つを交換する工程によって定められ、上記第４読み出しアドレスは、上記第２読み出しインデックスの上記ビットのうちの２つを交換する工程によって定められる。上記第１読み出しアドレスは、上記第１読み出しインデックスの上記ビットの順序を反転させることにより定められ、上記第２読み出しアドレスは、上記第２読み出しインデックスの上記ビットの順序を反転させることにより定められる。
【００１７】
上記第１出力データ値および上記第２出力データ値はさらに、少なくとも１つ回転因子に基づいてもよい。本発明の第１の観点に従った方法は、第３バッファの位置から上記少なくとも１つの回転因子を読み出す工程をさらに含んでもよい。
【００１８】
本発明の第１の観点に従った方法は、少なくとも上記第３入力データ値および上記第４入力データ値に基づいて第３出力データ値および第４出力データ値を計算する工程と、上記第３出力データ値および上記第４出力データ値を、１つの書き込み周期の間に上記第１バッファの隣接するメモリ位置に書き込む工程と、をさらに含んでもよい。
【００１９】
上記変換はサイズＮの変換であり、上記第１入力データ値および上記第２入力データ値を読み出す工程と、上記第１出力データ値および上記第２出力データ値を計算する工程と、１つの書き込み周期の間に上記第２バッファの隣接するメモリ位置に上記第１出力データ値および上記第２出力データ値を書き込む工程とは、上記変換の第１段階の間にＮ／２回実行されてもよい。上記第３入力データ値および上記第４入力データ値を読み出す工程と、上記第３出力データ値および上記第４出力データ値を計算する工程と、１つの書き込み周期の間に上記第１バッファの隣接するメモリ位置に上記第３出力データ値および上記第４出力データ値を書き込む工程とは、上記変換の第２段階の間にＮ／２回実行されてもよい。２つの入力データ値を読み出す工程と、２つの出力データ値を計算する工程と、１つの書き込み周期の間にバッファの隣接するメモリ位置に上記２つの出力データ値を書き込む工程とは、上記変換の各段階の間にＮ／２回実行されてもよい。
【００２０】
上記変換は高速フーリエ変換であってもよい。さらに、上記第１読み出しインデックスおよび上記第読み出し２インデックスは、上記第１データバッファと上記第２データバッファとのうちの少なくとも１つのアドレス値を含んでもよい。本発明の第２の観点によれば、変換を実行するためのデータ処理ユニットは、アドレス生成器と、回路と、を含んでもよく、上記回路は、データ値を格納するための第１バッファの位置から第１入力データ値を読み出し、上記位置は第１読み出しインデックスに基づいて第１読み出しアドレスによって定められ、上記第１バッファの位置から第２入力データ値を読み出すように適合され、上記位置は第２読み出しインデックスに基づいて第２読み出しアドレスによって定められる。上記回路は、少なくとも上記第１入力データ値および上記第２入力データ値に基づいて、第１出力データ値および第２出力データ値を計算し、１つの書き込み周期の間に、上記第１出力データ値および上記第２出力データ値を、データ値を格納するための第２バッファの隣接するメモリ位置に書き込むように適合され、上記隣接する位置は第１書き込みアドレスによって定められる。上記回路はまた、上記第２バッファの位置から第３入力データ値を読み出し、上記位置は上記第１読み出しインデックスに基づいて第３読み出しアドレスによって定められ、上記第２バッファの位置から第４入力データ値を読み出すように適合され、上記位置は上記第２読み出しインデックスに基づいて第４アドレスによって定められる。上記アドレス生成器は、上記第１読み出しインデックスの上記ビットのうちの少なくとも２つを交換することによって上記第３読み出しアドレスを定め、上記第２読み出しインデックスの上記ビットのうちの少なくとも２つを交換することによって上記第４読み出しアドレスを定めるように適合される。
【００２１】
本発明の第２の観点の幾つかの実施形態によれば、データ処理ユニットは、上記第１入力データ値と、上記第２入力データ値と、上記第１出力データ値と、上記第２出力データ値と、上記第１出力データ値および上記第２出力データ値の上記計算の中間結果と、のうちの少なくとも１つを一時的に格納するように適合される少なくとも１つのレジスタユニットをさらに含んでもよい。
【００２２】
上記アドレス生成器は、制御信号を受信するように適合される入力ポートを含んでもよく、上記アドレス生成器は、上記制御信号に基づいて、上記第１読み出しインデックスの上記ビットのうちの少なくとも２つを交換し、上記第２読み出しインデックスの上記ビットのうちの少なくとも２つを交換するように適合されてもよい。
【００２３】
さらに、第２の観点に従ったデータ処理ユニットは、第１の観点に従った実施形態の様々な特徴に対応する機能的特徴を有してもよい。
【００２４】
本発明の第３の観点によれば、変換計算ユニットは、本発明の第２の観点に従ったデータ処理ユニットを含んでもよい。
【００２５】
本発明の第４の観点によれば、電子装置は、本発明の第２の観点に従ったデータ処理ユニット、または、本発明の第３の観点に従った変換計算ユニットと、の少なくとも１つを含む。上記電子装置は、携帯型または手持ち型の移動無線通信機器、移動無線端末、携帯電話、ポケットベル、発信機、電子手帳、スマートフォン、コンピュータ、組込み型ドライブ、携帯型ゲーム機、時計、基地局、または、基地局コントローラであってもよく、ユニバーサル移動通信システム・ロングタームエボリューションの規格に則してもよい。
【００２６】
本発明の更なる実施形態は、従属請求項において定義されている。
【発明の効果】
【００２７】
本発明の効果の１つは、変換計算を行なうために必要な書き込み周期の数を低減しうるということである。さらに正確には、変換計算を行なうために必要な書き込み周期の数を半減しうる。本発明の効果は、実現に掛かるコストおよび／または複雑さがほとんど増すことなく、または全く増すことなく達成されうるが、その場合、実現に掛かるコストは、追加的なハードウェア、および／または追加的な計算負荷によるパワー消費を指しこともある。
【００２８】
本明細書で利用される場合「含む／含んでいる」（“ｃｏｍｐｒｉｓｅｓ／ｃｏｍｐｒｉｓｉｎｇ”）という語は、述べている特徴、整数、ステップ、または構成要素の存在を特定するために利用されるが、１つ以上の複数の他の特徴、整数、ステップ、または構成要素、またその集合の存在を排除するものではないことが強調される。
【図面の簡単な説明】
【００２９】
本発明の更なる目的、特徴、および効果は、添付の図面を参照して、以下の本発明の詳細な記載から明らかとなろう。
【図１】例示的な計算カーネルを示す図である。
【図２Ａ】サイズ８のＦＦＴ計算の例示的な実現を示すバタフライダイアグラムである。
【図２Ｂ】本発明の幾つかの実施形態に従った例示的な読み出し演算および書き込み演算を示す図である。
【図２Ｃ】本発明の幾つかの実施形態に従ったサイズ８のＦＦＴ計算の例示的な実現を示すバタフライダイアグラムである。
【図２Ｄ】本発明の幾つかの実施形態に従ったインデックスにおけるビット交換の例を示す図である。
【図３】本発明の幾つかの実施形態に従った変換を計算するためのデータ処理ユニットを示すブロック図である。
【図４】本発明の幾つかの実施形態に従ったバタフライ計算ユニットにより実施される方法を示すフローチャートである。
【図５】本発明の幾つかの実施形態に従ったアドレス生成器により実施される方法を示すフローチャートである。
【図６】本発明の幾つかの実施形態に従った１つ以上の変換計算ユニットを含みうる移動端末の正面図である。
【発明を実施するための形態】
【００３０】
記載を通じて、変換計算のための異なる実施形態を、高速フーリエ変換の演算にいくらか焦点を置きながら記載することにする。しかし、本発明は数多くの他の変換タイプにも同様に適用可能であることが強調される。例えば、本発明は、バタフライダイアグラムを通じて表されうる全ての変換に適用可能である。こうした変換の例は、ＦＦＴに加えて、離散コサイン変換（ＤＣＴ：Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）、離散サイン変換（ＤＳＴ：Ｄｉｓｃｒｅｔｅ  Ｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）、およびそれらの逆変換である。
【００３１】
以下では、バタフライ計算からの２つの出力データが１つの書き込み周期の間にバッファに書き込まれる、本発明の実施形態を提示することにする。１つのアドレス入力を含む標準メモリ、いわゆるシングルポートメモリがバッファとして使用されると考える場合に、１つの書き込み周期の間の２つの出力データの書き込みは、本発明の幾つかの実施形態に従って、バッファ内の隣接するメモリ位置への２つの出力データの書き込みにより達成することが出来る。
【００３２】
このことが、図２Ｂに示されている。図１との関連で説明したように、バタフライ計算ユニット１７０は、２つの入力データ（ｘ１およびｘ２）から、２つの出力データ（ｙ１、ｙ２）を生成する。以前のように、図があまり雑然とならないようにバタフライの描写が単純化されている。複数個のデータ（ｘ１、ｘ２、ｙ１およびｙ２）すべては、一定のワード長（ｗ：ｗｏｒｄ  ｌｅｎｇｔｈ）を有する。
【００３３】
従って、本発明の実施形態において、複数個のデータのそれぞれはワード長Ｗを有してもよく、バッファの（２つの隣接するメモリ位置を含む）メモリセルは、データの２倍の幅であってもよく、すなわち２Ｗであってもよい。従って、メモリセルは、２つのデータを格納することが可能であってもよい。さらに、バッファは、メモリセル内に、２つの隣接するメモリ位置のうちの１つ（すなわち、２つのデータのうちの１つ）を選択するための手段を有してもよい。この性能は、例えば、読み出し演算の間に使用されうる。
【００３４】
幾つかの実施形態において、この機能は、バッファをアドレス指定する際に幾つかの最下位ビットを破棄することによって実現される。例えば、各アドレスが幅Ｗのメモリ位置を指し、ビット０がバッファのアドレス指定の際に破棄されるアドレス方式が与えられている場合に、（それぞれがワード長Ｗの２つのデータを格納することが可能な）幅２Ｗのメモリセルへの参照が結果として起きる。メモリセルに含まれる２つのメモリ位置のうちの特定の一方が、アドレスビット０が０の場合にメモリセルの下半分を選択し、アドレスビット０が１の場合にメモリセルの上半分を選択することによって、アドレス指定されてもよい。
【００３５】
バタフライ計算ユニット１７０は、バッファ１５０から２つの入力データを読み出してもよい。バッファ１５０は、幾つかのバッファ位置に分けられていてもよく、そのそれぞれは、ワード長Ｗのデータを格納することが可能であり、アドレスにより定められるバッファ内に一定の位置を有する。先に説明したように、２つの隣接するバッファ位置は、ワード長２Ｗのバッファセル内に含まれていてもよく、バッファ内の各セルの位置は、アドレスにおいてビット０を破棄することにより定められてもよい。読み出し演算においては、アドレスビット０が０の場合にバッファから読み出された２Ｗのデータビットの下半分を選択し、アドレスビット０が１の場合にバッファから読み出された２Ｗのデータビットの上半分を選択することによって、データの正しい部分が得られる。図２Ｂの例において、計算ユニット１７０は、バッファ位置１５１および１５２から、２つの入力データを読み出す。
【００３６】
バタフライ計算ユニット１７０が、それぞれワード長Ｗを有する２つの出力データを計算した場合に、これら２つのデータは、ワード長２Ｗを有する１つの連結された出力データ（ｙ）を生成するために連結される。連結は、図に示されるようにバタフライ計算ユニット１７０によって行なわれてもよい。ｙ１およびｙ２のビットを互いに隣接させて置くことは、純粋な書き込みとして実現されてもよいので、連結は、ハードウェアにおける無演算命令（“ｎｏ−ｏｐ”）（ｎｏ  ｏｐｅｒａｔｉｏｎの省略）として実現されうることに注意されたい。
【００３７】
連結された出力データｙは、その後バッファ１６０に書き込まれる。バッファ１６０は、バッファ１５０と同様に、幾つかのバッファ位置および対応するバッファセルに分けられていてもよい。各バッファ位置は、ワード長Ｗのデータを格納することが可能であってもよく、アドレスにより定められるバッファ内に一定の位置を有してもよい。各バッファセルは、ワード長２Ｗのデータを格納することが可能であってもよく、アドレスのビット０を破棄することにより定められるバッファ内に一定の位置を有してもよい。ｙは２Ｗのワード長を有するので、連結された出力データｙをバッファに格納するためには、長さ２Ｗのバッファセル全体が必要である。書き込み演算においては、書き込みアドレスにおけるビット０が、先に説明したように破棄される。２つのデータは連結されているので、アドレスにおいてビット０を破棄することから起こる参照により示されるバッファセルに含まれる、２つの隣接するバッファ位置に書き込まれる。従って、バッファ１６０へのｙの書き込みは、隣接するメモリ位置への２つの出力データの書き込みと同等であり、データがどこに書き込まれるべきかを示すために１つのバッファアドレスのみ必要なので、１つの書き込み周期のみが必要となる。図２Ｂの例では、連結された出力データがバッファ位置１６１に書き込まれる。
【００３８】
従って、例えば、２つの出力データを連結し、１つの書き込みアドレスを使用することによって、１つの書き込み周期において２つの出力データを書き込むことが可能である。このソリューションは、２ポートメモリを使用するよりも安価であり、メモリバンクに分けられたバッファを使用するよりも複雑ではなく、同じ量の書き込み周期を必要とする。
【００３９】
従って、上記のソリューションを利用すると、中間結果は、変換計算を構成する大部分のバタフライ計算について図２Ａのサイズ８のＦＦＴの例のために示される順序では書き込まれえない。代わりに、隣接するメモリ位置への２つの出力データの書き込みの結果、「偏った」（“ｓｋｅｗｅｄ”）バタフライ構造が浮かび上がる。これが、本発明の幾つかの実施形態に従ったサイズ８のＦＦＴ計算２００’が示される図２Ｃにおいて例示されている。
【００４０】
図２Ｃにおいて、バッファ２０４、２０５、２０６、２０７、バッファアドレス２０８、および、計算段階２０１、２０２、２０３は、図２Ａのものと同様であり、従って、同じ参照番号が付されている。図２Ａにおけるように、図２Ｃにおいて、ＦＦＴ計算の中間結果が、バッファ２０４、２０５、２０６に格納され、ＦＦＴ計算の最終結果がバッファ２０７に格納される。以前に述べたように、幾つかの実現は、このタスクを遂行するために、交互に入れ替わる２つのバッファ全体を使用する。
【００４１】
図２Ｃには、本発明の実施形態が実施される際に、各読み出し周期の間にどのバッファアドレスから読み出すのかについて定めるために使用される、読み出しインデックス２０９’、２１０’、２１１’も示されている。図２Ｃでは、中間結果が図２Ａと同じ位置に格納されないことに注意することが不可欠である。このことは、第１段階の後に、それぞれのバタフライ計算において利用されるデータが、図２Ａと比較して異なるバッファ位置から読み出される必要があることを意味している。
【００４２】
例示すると、図２Ｃにおいて与えられたインデックスおよびアドレスによれば、第１段階の（値が０および１の読み出しインデックス２０９’に対応する）第１バタフライ計算は、バッファアドレス０および４からの入力データを使用し（かつ、出力バッファのアドレス０および１にバタフライ計算の結果を書き込み）、第１段階の（値が２および３の読み出しインデックス２０９’に対応する）第２バタフライ計算は、アドレス２および６からの入力データを使用する（かつ、出力バッファのアドレス２および３に結果を書き込む）べきである。第２段階の（値が０および１の読み出しインデックス２１０’に対応する）第１バタフライ計算は、図２Ｃによれば、バッファアドレス０および２からの入力データを使用し、第２段階の（値が２および３のインデックス２１０’に対応する）第２バタフライ計算は、バッファアドレス１および３からの入力データを使用するべきである。
【００４３】
実際に、図２Ｃのバッファアドレス２０８、および読み出しインデックス２１０’のビット表示を検討することにより、段階２では、あるバッファ位置の読み出しアドレス２０８が、読み出しインデックス２１０’のビット０と１を交換することによって見出されることに気付くであろう。さらに、段階３では、あるバッファ位置の読み出しアドレス２０８が、読み出しインデックス２１１’のビット０と２を交換することによって見出されることに気付くであろう。これは、いかなるサイズＮの変換にも有効な、一般的な観察である。このように、段階Ｍ＋１において、読み出しインデックスのビット０とＭ、Ｍ＝１、２、・・・、（ｌｏｇ２Ｎ）−１とを交換することによって、バッファ位置の読み出しアドレスが見出されうる。
【００４４】
図２Ｄには、インデックス２４０におけるビット０（２２０）とビットＭ（２３０）との交換の例が示されている。図３との関連で後に説明されるように、アドレスが、ビット交換インデックス（ｂｉｔ−ｓｗａｐｐｅｄ  ｉｎｄｅｘ）に基づいて生成される。幾つかの実施形態において、インデックス値は、バッファのメモリ位置を示す実際のアドレスである。
【００４５】
図２Ｄには、アドレス２４１におけるビットＸ（２２１）とビットＸ＋Ｍ（２３１）との交換の例も示されている。これは、本発明の幾つかの実施形態に従った操作を示している。これらの実施形態において、インデックス値は、バッファの（例えば２つのメモリ位置を含む）メモリセルへの実際のアドレスである。図２Ｂとの関連において説明したように、１つ以上の最下位ビットが、本実施形態において、メモリセル内の２つの隣接するメモリ位置のうちの１つを選択するために使用されている。従って、これらビットは、図２Ｄの下の例のビット交換においては含まれていない。代わりに、ビット０、・・・、Ｘ−１がメモリセル内の位置を選択するために予約され、正しい読み出しアドレスを生成するために、ビットＸとＸ＋Ｍとが交換される。
【００４６】
図２Ｃを再び参照すると、第１段階における読み出しアドレスは、（以前のように）、読み出しインデックス２０９’のビット順を予約し、ビット反転インデックス２０９’に基づいてアドレス値を生成することによって見出される。ビット反転インデックスは、それ自身が、ビット交換インデックスとの関連で先に説明されたものと同様に、メモリ位置またはメモリセルへのアドレスであってもよい。
【００４７】
本発明を実施する際に、全変換計算の結果を構成する複数個のデータの、出力バッファ（２０７）における順序は、一般に、従来の変換計算から生じうる順序とは異なっていてもよいことにも注意されたい。このことは、後続の処理が可変的であり、結果の、異なる順序に合わせるために調整されうる場合には懸念することではない。一方、後続の処理が固定のものであり、結果の、異なる順序に合わせるために調整されえない場合には、変換計算の後と後続の処理の前に、追加的な並べ替えの段階を追加することが必要であろう。このような並び替えの段階の実現に掛かるコストは、本発明を実施する際に得られる効果と比較して、ごく僅かであることが多い。
【００４８】
図３は、本発明の幾つかの実施形態に従ったデータ処理ユニット（ＤＰＵ：ｄａｔａ−ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）３１２を含む、例示的な変換計算ユニット３００を示している。データ処理ユニット３１２は、例えば、デジタル信号プロセッサ（ＤＳＰ：ｄｉｇｉｔａｌ  ｓｉｇｎａｌ  ｐｒｏｃｅｓｓｏｒ）、中央処理ユニット（ＣＰＵ：ｃｅｎｔｒａｌ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）、コプロセッサユニット、画像処理ユニット（ＧＰＵ：ｇｒａｐｈｉｃｓ  ｐｒｏｃｅｓｓｉｎｇ  ｕｎｉｔ）、加速器、または、特定用途向け集積回路（ＡＳＩＣ：ａｐｐｌｉｃａｔｉｏｎ−ｓｐｅｃｉｆｉｃ  ｉｎｔｅｇｒａｔｅｄ
ｃｉｒｃｕｉｔ）として実現されてもよく、または、デジタル信号プロセッサ（ＤＳＰ）、中央処理ユニット（ＣＰＵ）、コプロセッサユニット、画像処理ユニット（ＧＰＵ）、加速器、または、特定用途向け集積回路（ＡＳＩＣ）内に含まれていてもよい。データ処理ユニット３１２は、バタフライ計算を行なうバタフライ計算ユニット（ＢＣＵ：ｂｕｔｔｅｒｆｌｙ  ｃａｌｃｕｌａｔｉｏｎ  ｕｎｉｔ）３０１を含む。バタフライ計算自体は技術において公知であり、バタフライ計算ユニットにより行なわれる計算は、現在公知の如何なる方法に従ってもよく、または、将来に発見されるバタフライ計算のための如何なる方法に従ってもよい。バタフライ計算ユニット３０１は、第１データバッファ３０２、第２データバッファ３０３に動作可能に接続されている（ｏｐｅｒａｔｉｖｅｌｙ  ｃｏｎｎｅｃｔｅｄ）。データバッファ３０２、３０３は、読み出し／書き込みメモリであってもよい。本実施形態において、バタフライ計算ユニット３０１は、第３データバッファ３０４にも動作可能に接続されている。データバッファ３０４は、読み出し専用メモリであってもよい。第３データバッファは本発明の幾つかの実施形態において排除されてもよいことに注意されたい。データバッファ３０２、３０３、３０４は、データ処理ユニット３１２に外付けされてよく、または、代替的に、データ処理ユニット３１２の組み込まれた部分であってもよい。２つ以上のデータバッファは、同じメモリユニットの一部であってもよく、または、同じメモリユニットの一部でなくてもよい。データ処理ユニット３１２はアドレス生成器（ＡＤＤＲ  ＧＥＮ：ａｄｄｒｅｓｓ  ｇｅｎｅｒａｔｏｒ）３０５を含み、さらに、１つ以上のレジスタユニット（ＲＥＧ：ｒｅｇｉｓｔｅｒ  ｕｎｉｔ）３０６と、制御ユニット（ＣＵ：ｃｏｎｔｒｏｌ  ｕｎｉｔ）３０７とを含んでもよい。アドレス生成器３０５は、バタフライ計算ユニット３０１と、バッファ３０２、３０３、３０４とに動作可能に接続されている。制御ユニット３０７は、例えば、アドレス生成器３０５に動作可能に接続されてもよい。
【００４９】
バタフライ計算ユニット３０１は、第１データバッファ３０２、および第２データバッファ３０３からデータを読み出す。例として、バタフライ計算ユニット３０１は、第１読み出し周期および第２読み出し周期それぞれにおいて、第１データバッファ３０２から、２つの入力データを読み出すことが可能である。このデータは、図１に示されるバタフライ計算の入力口１０１および１０２における入力データ値と対応してもよい。バタフライ計算が回転因子を含む場合に、この回転因子は、第１読み出し周期または第２読み出し周期の間に、第１データバッファ３０２からの読み出しと並行して、バタフライ計算ユニット３０１によってデータバッファ３０４から読み出されてもよい。回転因子は、第３読み出し周期の間にバタフライ計算ユニット３０１によって読み出されてもよい。代替的に、回転因子は既に、例えば、１つ以上のレジスタユニット３０６に格納されていてもよい。複数の入力データと、回転因子とは、図３に示されるようにワード長Ｗであってもよい。
【００５０】
バタフライ計算ユニット３０１は、さらに、少なくとも２つの入力データに基づいて、２つの出力データを計算する。この出力データの部分は、図１に示されるバタフライ計算の出力口１０３および１０４における出力値に対応してもよい。２つの出力データの計算の間に、中間結果、および／または、２つの出力データのうちの１つ以上が、１つ以上のレジスタユニット３０６に一時的に格納されてもよい。２つの出力データの計算が完了すると、１つの書き込み周期の間に、バタフライ計算ユニットによって、第２データバッファ３０３の隣接するメモリ位置に、２つの出力データが書き込まれる。１つの書き込み周期の間の２つの出力データの書き込みは、例えばバタフライ計算ユニット３０１内で、２つの出力データを連結することによって達成される。このように、バッファ３０３に書き込まれる出力データは、図３に示すようにワード長２Ｗであってもよい。以前に述べたように、連結は、ハードウェアにおける純粋な書き込みとして実現されてもよい。
【００５１】
この工程は、変換計算のある段階の全てのバタフライ計算が完了するまで継続する。その後、次の段階のバタフライ計算が同じように実行される。しかし、ここでは、バタフライ計算ユニット３０１は、第２データバッファ３０３から２つの入力データを読み出し、第１データバッファ３０２へと２つの出力データを書き込む。
【００５２】
アドレス生成器３０５は、データバッファ３０２、３０３のうちの１つから、入力データの第１部分および第２部分を読み出すためのアドレスを生成する。アドレスの生成は、例えば、制御ユニット３０７によって開始されてもよい。代替的に、アドレスの生成は、バタフライ計算ユニット３０１によって開始されてもよく、または、アドレス生成器は、例えば、各クロック周期の間にアドレスを生成してもよい。生成は、アドレス生成器に外付けされたユニットによるアクティブなアクションによって開始される必要はない。
【００５３】
いずれの場合にせよ、アドレス生成器は、ビット交換インデックス値（ｂｉｔ−ｓｗａｐｐｅｄ  ｉｎｄｅｘ  ｖａｌｕｅ）を生成するためにインデックス値を使用する。インデックス値は、例えば、制御ユニット３０７またはバタフライ計算ユニット３０１によって、アドレス生成器に供給されてもよい。アドレス生成器３０５にはさらに、ビット交換モードを示す制御信号が用意されている。ビット交換モードは、ビット交換インデックス値を生成するために、インデックス値におけるどのビットが交換されるべきかについて定める。この制御信号は、接続３１０を通じて制御ユニット３０７によって、または、接続３１１を通じてバタフライ計算ユニット３０１によって供給されてもよい。制御信号は、
アドレス生成のビット交換モードを構成するために、変換計算の新しい段階に入る前に活性化されてもよい。制御信号およびインデックス値は、ビット交換器（ＢＳ：ｂｉｔ−ｓｗａｐｐｅｒ）３０８に供給されてよく、このビット交換器３０８は、例えば、アドレス生成器３０５に不可欠であってもよい。ビット交換器３０８は、制御信号により示されるインデックス値においてビットを交換することによって、ビット交換インデックス（ｂｉｔ−ｓｗａｐｐｅｄ  ｉｎｄｅｘ）を作成してもよい。
【００５４】
アドレス生成器３０５は、その後、ビット交換インデックスに基づいてアドレスを生成する。ビット交換インデックスの値は、それ自体がメモリ位置のうちの１つのアドレスであってもよく、または、先に説明したように、データバッファ３０２、３０３のうちの１つの、メモリセルのうちの１つのアドレスであってもよい。この場合に、アドレス生成器３０５は単に、生成されたアドレスとしてビット交換インデックスを出力する。
【００５５】
生成されたアドレスは、バッファ３０２および３０３をアドレス指定するために利用され、バタフライ計算ユニット３０１は、生成されたアドレスにより示されるバッファのうちの１つのメモリ位置からデータ値を読み出す。
【００５６】
アドレス生成器はさらに、ビット反転インデックス値（ｂｉｔ−ｒｅｖｅｒｓｅｄ  ｉｎｄｅｘ  ｖａｌｕｅ）を生成する。このために、インデックス値は、ビット反転器（ＢＲ：ｂｉｔ−ｒｅｖｅｒｓｅｒ）３０９によって供給されてもよく、このビット反転器３０９は、例えば、アドレス生成器３０５に不可欠であってもよい。ビット反転器３０９は、インデックス値におけるビットを反転させることによって、ビット反転インデックスを生成してもよい。
【００５７】
アドレス生成器３０５は、その後、ビット反転インデックスに基づいてアドレスを生成する。ビット反転インデックス値は、それ自体がデータバッファ３０２、３０３、３０４のうちの１つの、メモリ位置のうちの１つのアドレスであってもよい。この場合、アドレス生成器３０５は単に、生成されたアドレスとしてビット反転インデックスを出力する。
【００５８】
生成されたアドレスは、バッファ３０２、３０３、３０４をアドレス指定するために利用され、バタフライ計算ユニット３０１は、生成されたアドレスにより示されるバッファのうちの１つのメモリ位置から、データ値を読み出す。変換計算の第１段階において、バタフライ計算ユニット３０１は、ビット反転インデックスに基づくアドレスにより示されるバッファ３０２、３０３のうちの１つのメモリ位置から入力データ値を読み出す。
【００５９】
ビット交換器およびビット反転器は、代替的に、１つのユニットとして実現されうることに注意されたい。
【００６０】
アドレス生成器３０５はさらに、連結された２つの出力データをバッファ３０２と３０３のうちの１つに書き込むための書き込みアドレスを生成してもよい。
【００６１】
図４には、変換計算のための方法４００がフローチャートで示されている。方法４００は、例えば、図３のようなデータ処理ユニットのバタフライ計算ユニットによって、実施されうる。
【００６２】
本方法は、ステップ４１０において開始し、ステップ４１０では、第１インデックス値がアドレス生成ユニットへと供給され、このアドレス生成ユニットは、図３のアドレス生成器３０５と同様であってもよく、または、アドレス生成器３０５と同一であってもよい。以前に述べたように、このステップは、幾つかの実現において、例えば、インデックス値が制御ユニットにより供給される場合、またはアドレス生成ユニット自体の内部で生成される場合に省略される。
【００６３】
ステップ４２０において、第１読み出しアドレスが、例えばアドレス生成ユニットから獲得され、ステップ４３０において、第１入力データ値が第１読み出しアドレスにより示されるデータバッファのメモリ位置から読み出される。
【００６４】
本法はステップ４４０に進み、ステップ４４０において、第２インデックス値が、アドレス生成ユニットに供給される。以前のように、このステップは幾つかの実現において省略される。ステップ４５０において、第２読み出しアドレスが獲得され、ステップ４６０において、第２入力データ値が、第２読み出しアドレスにより示されるデータバッファのメモリ位置から読み出される。
【００６５】
その後、本発明の幾つかの実施形態において、１つ以上の回転因子が、ステップ４７０においてデータバッファから読み出されてもよく、このデータバッファは、ステップ４３０および４６０においてアドレス指定されたデータバッファと同一であってもよく、または、ステップ４３０および４６０においてアドレス指定されたデータバッファと異なっていてもよい。当然のことながら、このステップは、代替的に、ステップ４３０またはステップ４６０のどちらか一方と同時に実施されてもよい。
【００６６】
バタフライ計算は、ステップ４８０において実施される。２つの得られた出力データ値は、ステップ４８５において連結され、ステップ４９０において、１つの書き込み周期の間に、データバッファの隣接するメモリ位置に書き込まれる。再度、連結はハードウェアにおける純粋な書き込みとして実現可能であり、従って、図４のフローチャートでは破線のボックスで示されていることに注意されたい。
【００６７】
図５には、読み出しアドレス生成のための方法５００がフローチャートで示されている。方法５００は、例えば、図３のようなデータ処理ユニットのアドレス生成器によって実施されてもよい。
【００６８】
本方法は、インデックス値が獲得されるステップ５１０において開始し、ステップ５２０に進む。ステップ５２０では、ビット交換モードが獲得される。ステップ５３０において、ビット交換インデックスが、インデックス値およびビット交換モードに基づいて生成される。例えば、ビット交換モードがＭであり、このことが、変換計算が段階Ｍ＋１を実施していることを示す場合に、ビットが図２Ｄに示されるように交換されうる。ステップ５４０において、アドレスは、ビット交換インデックスに基づいて生成され、ステップ５５０において、生成されたアドレスがアドレス生成器によって出力される。
【００６９】
本発明の記載された実施形態およびその均等物は、デジタル信号プロセッサ（ＤＳＰ）、中央処理ユニット（ＣＰＵ）、コプロセッサユニット、グラフィック処理ユニット（ＧＰＵ）、加速器のような汎用回路によって、または、例えば特定用途向け集積回路（ＡＳＩＣ）のような特殊回路によって、部分的に、または完全に実施されうる。すべてのこうした形態は、本発明の範囲内にあるものとする。本発明は、記載された実施形態のいずれかに従った１つ以上のデータ処理ユニットを含む電子装置として実現されうる。電子装置は、例えば、携帯型または手持ち型の移動無線通信機器、移動無線端末、携帯電話、ポケットベル、発信機、電子手帳、スマートフォン、コンピュータ、組込み型ドライブ、携帯型ゲーム機、または（腕）時計であってもよい。電子装置は、代替的に、通信システムにおける基地局、または、基地局コントローラであってもよい。
【００７０】
図６は、先に記載した少なくとも１つの変換計算ユニット３００を含む例示的な電子装置としての携帯電話６００を示している。携帯電話６００の正面図が示されている。この例示的な携帯電話６００は、装置の筐体に取り付けられたアンテナ６０１を含んでいる。代替的に、携帯電話６００は、装置の筐体内に取り付けられた国際アンテナを有してもよい。携帯電話６００はさらに、携帯電話６００を操作するためにマンマシン・インタフェース（ｍａｎ−ｍａｃｈｉｎｅ  ｉｎｔｅｒｆａｃｅ）を共に提供する、ディスプレイ６０４、キーボード６０５、スピーカ６０２、およびマイクロホン６０６を含んでもよい。
【００７１】
携帯電話６００は、無線基地局（基地局）への無線リンクを介して移動通信ネットワークに接続する。従って、携帯電話６００のユーザは、音声呼、データ通話、映像通話、およびファックス送信のような、従来の回線交換通信サービスと同様に、電子メッセージ、インターネット閲覧、電子商取引などのようなパケットに基づくサービスを利用することが可能である。このために、携帯電話は、例えば、移動通信のためのグローバルシステム（ＧＳＭ）、汎用パケット無線サービス（ＧＰＲＳ）、ＥＤＧＥ（Ｅｎｈａｎｃｅｄ  Ｄａｔａ  ｒａｔｅｓ  ｆｏｒ  ＧＳＭ
Ｅｖｏｌｕｔｉｏｎ）、ユニバーサル移動通信システム（ＵＭＴＳ)、またはＵＭＴＳ  ＬＴＥのような移動通信規格に則している。
【００７２】
様々な実施形態を参照しながら本発明を本明細書に解説してきた。しかし、当業者は、本発明の範囲に依然として収まる、記載された実施形態に対する数多くの変形が分かるであろう。例えば、本明細書に記載される方法の実施形態は、ある一定の順序に従って実行される本方法のステップを通じて、本方法を記載している。しかし、これらのイベントのシーケンスが、本発明の範囲から逸脱することなく、他の順序で行なわれることも可能であることが認識される。さらに、本発明の実施形態の記載を通じて、特定のユニットへの機能ブロックの配分は、決して、本発明を制限するものではないことに注意されたい。反対に、これらの配分は単なる例である。１つのユニットとして本明細書に記載される機能ブロックは、２つ以上のユニットに分けられてもよい。同様に、２つ以上のユニットとして実現されるものとして本明細書に記載されている機能ブロックは、本発明の範囲を逸脱することなく、単一ユニットとして実現されてもよい。従って、当然のことながら、記載される実施形態の限定は、単に例示することを目的としており、決して制限を目的とするものではない。反対に、本発明は、添付の請求項と、その全ての妥当な均等物によってのみ制限されるものと解釈される。
【図１】
2010531504.tif 000003
【図２Ａ】
2010531504.tif 000004
【図２Ｂ】
2010531504.tif 000005
【図２Ｃ】
2010531504.tif 000006
【図２Ｄ】
2010531504.tif 000007
【図３】
2010531504.tif 000008
【図４】
2010531504.tif 000009
【図５】
2010531504.tif 000010
【図６】
2010531504.tif 000011
【国際調査報告】
2010531504.tif 000012
2010531504.tif 000013
2010531504.tif 000014