(57)【特許請求の範囲】
【請求項１】
計算システムを用いて、チャープＺ変換（ＣＺＴ）を反転する方法であって、
前記計算システムは、プロセッサ及びメモリデバイスを備え、
前記ＣＺＴは、パラメータＡイタリック及びパラメータＷイタリックを有し、前記パラメータＡイタリック及び前記パラメータＷイタリックは、ｋ＝０，１，２、…、Ｍ−１に対して式ＡイタリックＷイタリック−ｋを介して複素平面において対数らせん輪郭線を定義し、
前記ＣＺＴは、Ｘ＝ＷＡｘとして表されることができ、前記Ｗは、前記パラメータＷイタリック及びそのべき乗によって定義される次元Ｍ×Ｎのヴァンデルモンド行列であり、前記Ａは、前記パラメータＡイタリック及びそのべき乗によって定義される第１対角行列であり、
前記ｘは第１ベクトルであり、前記Ｘは、該Ｘのｋ番目の要素がｋ＝０、１，２、…、Ｍ−１に対して
【数ＣＬ０１】
0006928208.tif 000105
によって与えられるように、前記ＣＺＴを用いて前記第１ベクトルｘから計算される第２ベクトルであり（ここで、Ｗイタリック及びＡイタリックは、それぞれ、上記式においてイタリック体のＷ及びＡを示し）、
前記パラメータＡイタリック及び前記パラメータＷイタリックは、非ゼロの複素数であり、前記Ｘは、前記メモリデバイスに格納され、
前記方法は：
第２対角行列Ｐ、テプリッツ行列Ｗ＾、及び第３対角行列Ｑの積として前記行列Ｗを表すステップであって、前記ＣＺＴがＸ＝ＰＷ＾ＱＡｘとして表される、ステップと、
ｘ＝Ａ−１Ｑ−１Ｗ＾−１Ｐ−１Ｘとして逆ＣＺＴを表すステップであって、Ａ−１、Ｑ−１、Ｗ＾−１、及びＰ−１は、それぞれ、Ａ、Ｑ、Ｗ＾、及びＰの逆行列である、ステップと、
第３ベクトルｘ＾を計算するために前記Ａ−１Ｑ−１Ｗ＾−１Ｐ−１Ｘの積において右から左に乗算を、前記プロセッサを用いて、実行することによって前記逆ＣＺＴを計算するステップと
を備える、方法。
【請求項２】
前記第１ベクトルｘの各要素は、前記第３ベクトルｘ＾の対応する要素に実質的に等しい、請求項１に記載の方法。
【請求項３】
前記第１ベクトルｘの少なくとも１つの要素は、前記第３ベクトルｘ＾の対応する要素に等しくない、請求項１に記載の方法。
【請求項４】
前記方法は、計算する前記ステップに先だって、前記第２ベクトルＸに対する演算を実行するステップをさらに備え、該演算は、前記第２ベクトルＸの要素の少なくとも１つを修正する、請求項３に記載の方法。
【請求項５】
前記演算は、フィルタ処理の演算である、請求項４に記載の方法。
【請求項６】
前記方法は、Ｏ（ｎ２）より小さい又は等しい計算複雑性を有し、ｎ＝ｍａｘ（Ｍ、Ｎ）である、請求項１に記載の方法。
【請求項７】
前記計算複雑性はＯ（ｎｌｏｇ（ｎ））である、請求項６に記載の方法。
【請求項８】
前記行列Ｗ＾−１は、
Ｗ＾−１＝（１／ｕ０）×
【数ＣＬ０８１】
0006928208.tif 000106
として表されることができ、ここで
【数Ａ４】
0006928208.tif 000107
は、第１下三角テプリッツ行列であり、
【数Ａ４Ｔ】
0006928208.tif 000108
は、
【数Ａ４２】
0006928208.tif 000109
の転置に等しい第１上三角テプリッツ行列であり、
【数Ｄ４】
0006928208.tif 000110
は、第２上三角テプリッツ行列であり、
【数Ｄ４Ｔ】
0006928208.tif 000111
は、
【数Ｄ４２】
0006928208.tif 000112
の転置に等しい第２下三角テプリッツ行列であり、
ｕ０は、
【数ＣＬ０８２】
0006928208.tif 000113
に等しく、
ｎは、Ｍ又はＮの少なくとも一方に基づく、
請求項１に記載の方法。
【請求項９】
４つの前記行列
【数Ａ５】
0006928208.tif 000114
、
【数Ａ５Ｔ】
0006928208.tif 000115
、
【数Ｄ５Ｔ】
0006928208.tif 000116
、又は
【数Ｄ５】
0006928208.tif 000117
の各々のための生成ベクトルは、
【数ＣＬ０９】
0006928208.tif 000118
によって与えられるベクトルｕ＝（ｕ０、ｕ１、．．．、ｕｎ−１）から導かれることができる、
請求項８に記載の方法。
【請求項１０】
ベクトルと
Ｗ＾−１＝（１／ｕ０）×
【数ＣＬ１０】
0006928208.tif 000119
の積を計算するステップ中に、前記乗算は、別の行列で乗算される行列がないように右から左に実行される、請求項８に記載の方法。
【請求項１１】
前記テプリッツ行列
【数Ａ６】
0006928208.tif 000120
、
【数Ａ６Ｔ】
0006928208.tif 000121
、
【数Ｄ６Ｔ】
0006928208.tif 000122
、又は
【数Ｄ６】
0006928208.tif 000123
の少なくとも１つへのベクトルの乗算は、更に、
前記テプリッツ行列を循環行列に埋め込むステップであって、前記循環行列が、前記循環行列の生成ベクトルによって表され、前記循環行列の次元が、Ｍ又はＮの少なくとも一方に基づく、ステップと、
乗算に先立って前記ベクトルをゼロで詰め込むステップであって、前記循環行列の列数と同じ長さの詰め込まれたベクトルを生成する、ステップと、
前記循環行列に前記詰め込まれたベクトルを乗算することによって積ベクトルを計算するステップと、
前記テプリッツ行列が埋め込まれた前記循環行列の行に対応する前記積ベクトルの要素を含む結果ベクトルを抽出するステップと
を含む、請求項１０に記載の方法。
【請求項１２】
前記循環行列は、正方行列であり、前記循環行列の行数は、２のべき乗である、請求項１１に記載の方法。
【請求項１３】
前記テプリッツ行列
【数Ａ７】
0006928208.tif 000124
、
【数Ａ７Ｔ】
0006928208.tif 000125
、
【数Ｄ７Ｔ】
0006928208.tif 000126
、又は
【数Ｄ７】
0006928208.tif 000127
の少なくとも１つへのベクトルの乗算は、前記ベクトルとの乗算に先立って、前記行列のＰｕｓｔｙｌｎｉｋｏｖ分解を実行することを含む、
請求項１０に記載の方法。
【請求項１４】
前記テプリッツ行列
【数Ａ８】
0006928208.tif 000128
、
【数Ａ８Ｔ】
0006928208.tif 000129
、
【数Ｄ８Ｔ】
0006928208.tif 000130
、又は
【数Ｄ８】
0006928208.tif 000131
の少なくとも１つへのベクトルの乗算は、
拡張されたテプリッツ行列に前記テプリッツ行列を、前記されたテプリッツ行列のための生成ベクトルをゼロで詰め込むことによって埋め込むステップであって、前記拡張されたテプリッツ行列が、Ｍ又はＮの少なくとも一方に基づく次元を有する、ステップと、
前記テプリッツ行列に乗算される前記ベクトルにゼロを詰め込むステップであって、前記拡張されたテプリッツ行列における列数と同じ長さを有する詰め込まれたベクトルを生成する、ステップと、
Ｐｕｓｔｙｌｎｉｋｏｖ分解を用いて、前記拡張されたテプリッツ行列を、循環行列及びスキュー循環行列の和として表すステップと、
前記循環行列に前記詰め込まれたベクトルを乗算し、前記スキュー循環行列に前記詰め込まれたベクトルを乗算し、埋め込まれた結果ベクトルを生成するために該２つの結果ベクトルを加算するステップと、
前記テプリッツ行列が埋め込まれる前記拡張されたテプリッツ行列の行に対応する前記詰め込まれた結果ベクトルの要素を保持することによって、前記詰め込まれた結果ベクトルから結果ベクトルを抽出するステップと、
をさらに含む、請求項１０に記載の方法。
【請求項１５】
前記拡張されたテプリッツ行列における行数及び列数は、２のべき乗である、請求項１４に記載の方法。
【請求項１６】
前記方法の実行中に、行列Ａ−１、Ｑ−１、
【数Ａ９】
0006928208.tif 000132
、
【数Ａ９Ｔ】
0006928208.tif 000133
、
【数Ｄ９Ｔ】
0006928208.tif 000134
、
【数Ｄ９】
0006928208.tif 000135
、及びＰ−１のいずれも、メモリに完全に格納されない、請求項８に記載の方法。
【請求項１７】
前記方法を実行するために、Ｏ（ｎ）より大きいメモリは必要とされない、ここでｎ＝ｍａｘ（Ｍ、Ｎ）である、請求項１に記載の方法。
【請求項１８】
ＭがＮに等しい、請求項１に記載の方法。
【請求項１９】
ＭがＮに等しくない、請求項１に記載の方法。
【請求項２０】
前記第１ベクトルｘは、オーディオ信号から導出される、請求項１に記載の方法。
【請求項２１】
前記オーディオ信号は音声信号を含む、請求項２０に記載の方法。
【請求項２２】
前記オーディオ信号は、ソナー信号又は超音波信号のうちの少なくとも１つを含む、請求項２０に記載の方法。
【請求項２３】
前記第１ベクトルｘは、画像信号から導出される、請求項１に記載の方法。
【請求項２４】
前記画像信号が、コンピュータ断層撮影（ＣＴ）信号、陽電子放出断層撮影（ＰＥＴ）信号、又は磁気共鳴画像（ＭＲＩ）信号のうちの少なくとも１つを含む、請求項２３に記載の方法。
【請求項２５】
前記第１ベクトルｘは、レーダ系センサによって受信された信号から導出される、請求項１に記載の方法。
【請求項２６】
前記第１ベクトルｘは、レーダ系センサに送信される信号を生成するために使用される、請求項１に記載の方法。
【請求項２７】
前記第２ベクトルＸは、同じパラメータＡイタリック及びＷイタリックを持つ前記ＣＺＴを用いて特定の第１ベクトルｘから計算されない、請求項１に記載の方法。
【請求項２８】
式ＡイタリックＷイタリック−ｋの対数らせん輪郭線を対象に含めるために計算システムの範囲を拡張する方法であって、ここで、Ａイタリック及びＷイタリックは、非ゼロの複素数であり、ｋ＝０、１、…、Ｍ−１であり、前記計算システムは、１又は複数の過程において、高速フーリエ変換（ＦＦＴ）又は逆ＦＦＴ（ＩＦＦＴ）の少なくとも１つを用い、
前記計算システムは、プロセッサ及びメモリを備え、前記プロセッサは、前記ＦＦＴからの周波数ドメインベクトル又は前記ＩＦＦＴからの時間ドメインベクトルを計算し、前記周波数ドメインベクトル及び前記時間ドメインベクトルを前記メモリに格納し、
前記方法は、少なくとも１つの過程において、ＩＦＦＴに替えて逆チャープＺ変換（ＩＣＺＴ）を利用することによって前記プロセッサを用いて前記時間ドメインベクトルを計算するステップを備え、
前記ＩＣＺＴは、Ｍ×Ｎの次元を有するヴァンデルモンド行列の観点で表されることができ、前記計算システム上において前記ＩＣＺＴを用いることの計算複雑性は、Ｏ（ｎ２）に等しい又は未満であり、ここでｎ＝ｍａｘ（Ｍ、Ｎ）である、方法。
【請求項２９】
前記計算複雑性は、Ｏ（ｎｌｏｇ（ｎ））である、請求項２８に記載の方法。
【請求項３０】
前記計算システムは、ＩＣＺＴの実行中にほんのＯ（ｎ）のメモリを使用する、請求項２９に記載の方法。
【請求項３１】
Ｍ×Ｎの次元を有するヴァンデルモンド行列の観点で表されることができるチャープＺ変換（ＣＺＴ）を反転する計算システムの効率を高める方法であって、
前記計算システムはプロセッサ及びメモリを備え、前記方法は、前記ＣＺＴを反転して、前記メモリに格納される時間ドメインベクトルを生成する方法を使用するステップを備え、該方法は、前記プロセッサ上で実行されるときｎ＝ｍａｘ（Ｍ、Ｎ）においてＯ（ｎ２）に等しい又は未満である計算複雑性を有し、前記ＣＺＴは、２つの非ゼロの複素数Ａイタリック及びＷイタリックによってパラメータにより表現され、前記複素数Ａイタリック及びＷイタリックは、ｋ＝０、１、…、Ｍ−１における式ＡイタリックＷイタリック−ｋを介して対数らせん輪郭線を定義する、方法。
【請求項３２】
前記計算システムは、逆ＣＺＴの計算中にほんのＯ（ｎ）のメモリを必要とする、請求項３１に記載の方法。
【請求項３３】
前記ＣＺＴを反転するための前記方法は、Ｏ（ｎｌｏｇ（ｎ））の計算複雑性を有する、請求項３１に記載の方法。
【請求項３４】
計算システムの数値精度を向上する方法であって、前記計算システムは、前記計算システムのプロセッサを用いて、チャープＺ変換（ＣＺＴ）又は逆チャープＺ変換（ＩＣＺＴ）の少なくとも一方を、１又は複数の過程で、計算すると共に前記計算システムのメモリに時間ドメインベクトル又は周波数ドメインベクトルを格納するものであって、
前記ＣＺＴ、前記ＩＣＺＴ、又は前記ＣＺＴ及び前記ＩＣＺＴの両方は、ｋ＝０、１、…、Ｍ−１において式ＡイタリックＷイタリック−ｋを介して対数らせん輪郭線を定義する２つの非ゼロの複素数Ａイタリック及びＷイタリックによってパラメータにより表わされることができ、
｜Ｗイタリック｜＜１の場合に、当該方法は、少なくとも１つの過程において、前記対数らせん輪郭線の開始点及び終了点が交換されるように前記対数らせん輪郭線の方向を反転するステップを含み、
前記ＣＺＴの出力ベクトル、前記ＩＣＺＴの入力ベクトル、又は前記ＣＺＴの前記出力ベクトル及び前記ＩＣＺＴの前記入力ベクトルの両方における要素の順序が逆転される、方法。
【請求項３５】
計算システムのメモリに格納される長さＭの周波数領域ベクトルＸを、前記計算システムのメモリに格納される長さＮの時間領域ベクトルｘに変換する方法であって、
前記時間領域ベクトルｘを計算するために、ｘ＝（１／ｕ０）Ａ−１Ｑ−１
【数ＣＬ３６１】
0006928208.tif 000136
Ｐ−１Ｘとして表されることができる逆チャープＺ変換（ＩＣＺＴ）を、前記計算システムのプロセッサを用いて、右から左への乗算を実行することによって計算するステップを備え、
Ａ−１は、パラメータＡイタリック及びそれのべき乗によって定義される第１対角行列であり、
Ｑ−１は、パラメータＷイタリック及びそれのべき乗に基づく第２対角行列であり、
【数Ａ１０】
0006928208.tif 000137
は、第１下三角テプリッツ行列であり、
【数Ａ１０Ｔ】
0006928208.tif 000138
は、
【数Ａ１０２】
0006928208.tif 000139
の転置に等しい第１上三角テプリッツ行列であり、
【数Ｄ１０】
0006928208.tif 000140
は、第２上三角テプリッツ行列であり、
【数Ｄ１０Ｔ】
0006928208.tif 000141
は、
【数Ｄ１０２】
0006928208.tif 000142
の転置に等しい第２下三角テプリッツ行列であり、
Ｐ−１は、前記パラメータＷイタリック及びそれのべき乗に基づく第３対角行列であり、
前記パラメータＡイタリック及びＷイタリックは、非ゼロの複素数であり、該複素数は、ｋ＝０、１、…、Ｍ−１に対して式ＡイタリックＷイタリック−ｋを介して対数らせん輪郭線を定義し、
ｕ０は
【数ＣＬ３６２】
0006928208.tif 000143
に等しく（ここで、Ｗイタリックは、イタリック体のＷを示し）、
ｎは、Ｍ及びＮの少なくとも一方に基づく、方法。
【請求項３６】
前記周波数領域ベクトルＸは、Ｘ＝ＷＡｘ＾として表されることができ、ここでＷは、複素数パラメータＷイタリック及びそれのべき乗によって定義されるヴァンデルモンド行列であり、Ａは、ベクトルＡのｋ番目の要素が、ｋ＝０，１，２、…、Ｍ−１対して
【数ＣＬ３７】
0006928208.tif 000144
によって与えられるように，複素数パラメータＡイタリック及びそれのべき乗に基づく第４対角行列であり（ここで、Ａイタリックは、イタリック体のＡを示し）、ｘ＾は長さＮの第２時間領域ベクトルである、請求項３５に記載の方法。
【請求項３７】
前記行列Ｗは、前記周波数領域ベクトルＸが、行列形式におけるチャープＺ変換（ＣＺＴ）として表されるように、第５対角行列Ｐ、テプリッツ行列Ｗ＾、及び第６対角行列Ｑの積によって表されることができ、
ここで、Ｘ＝ＰＷ＾ＱＡｘである、請求項３６に記載の方法。
【請求項３８】
前記周波数領域ベクトルＸは、同じパラメータＡイタリック及びＷイタリックをチャープＺ変換を用いて特定の時間領域ベクトルｘから計算されない、請求項３５に記載の方法。
【請求項３９】
ほんのＯ（ｎ）の数が、前記方法の実行中にメモリに格納され、ｎ＝ｍａｘ（Ｍ、Ｎ）である、請求項３５に記載の方法。
【請求項４０】
行列Ａ−１、Ｑ−１、
【数Ａ１１】
0006928208.tif 000145
、
【数Ａ１１Ｔ】
0006928208.tif 000146
、
【数Ｄ１１Ｔ】
0006928208.tif 000147
、
【数Ｄ１１】
0006928208.tif 000148
、及びＰ−１のいずれも、前記方法の実行中にメモリに完全に格納されない、請求項３５に記載の方法。
【請求項４１】
前記方法の計算複雑性は、Ｏ（ｎ２）に等しい又はより小さい、ここで、ｎ＝ｍａｘ（Ｍ、Ｎ）である、請求項３５に記載の方法。
【請求項４２】
前記計算複雑性は、Ｏ（ｎｌｏｇ（ｎ））である、請求項４１に記載の方法。
【請求項４３】
メモリデバイスであって、前記メモリデバイスは長さＭの周波数領域ベクトルＸを格納するように構成されたメモリデバイスと、
プロセッサであって、前記プロセッサは逆チャープＺ変換（ＩＣＺＴ）を用いて前記周波数領域ベクトルＸを時間領域ベクトルｘに写像するように構成されたプロセッサと、
を備え、
前記ＩＣＺＴは、
ｘ＝（１／ｕ０）Ａ−１Ｑ−１
【数ＣＬ４４１】
0006928208.tif 000149
Ｐ−１Ｘとして表され、
ここで、前記プロセッサは、長さＮの前記時間領域ベクトルｘを計算するために、前記ＩＣＺＴの行列乗算を右から左に実行し、ここで、
Ａ−１は、パラメータＡイタリック及びそれのべき数によって定義された第１対角行列であり、
Ｑ−１は、パラメータＷイタリック及びそれのべき乗に基づく第２対角行列であり、
【数Ａ１２】
0006928208.tif 000150
は、第１下三角テプリッツ行列であり、
【数Ａ１２Ｔ】
0006928208.tif 000151
は、
【数Ａ１２２】
0006928208.tif 000152
の転置に等しい第１上三角テプリッツ行列であり、
【数Ｄ１２】
0006928208.tif 000153
は、第２上三角テプリッツ行列であり、
【数Ｄ１２Ｔ】
0006928208.tif 000154
は、
【数Ｄ１２２】
0006928208.tif 000155
の転置に等しい第２下三角テプリッツ行列であり、
Ｐ−１は、前記パラメータＷイタリック及びそれのべき乗に基づく第３対角行列であり、
Ｘが前記周波数領域ベクトルであり、
前記パラメータＡイタリック及びＷイタリックは、ｋ＝０、１、…、Ｍ−１に対して式ＡイタリックＷイタリック−ｋを介して対数らせん輪郭線を定義する非ゼロの複素数であり、
ｕ０は
【数ＣＬ４４２】
0006928208.tif 000156
に等しく（ここで、Ｗイタリックは、上記式においてイタリック体のＷを示し）、
ｎは、Ｍ及びＮの少なくとも一方に基づく、システム。
【請求項４４】
前記行列
【数Ａ１３】
0006928208.tif 000157
、
【数Ａ１３Ｔ】
0006928208.tif 000158
、
【数Ｄ１３Ｔ】
0006928208.tif 000159
、及び
【数Ｄ１３】
0006928208.tif 000160
の各々のための生成ベクトルは、
【数ＣＬ４５】
0006928208.tif 000161
によって与えられたベクトルｕ＝（ｕ０、ｕ１、．．．、ｕｎ−１）から導かれることができる、請求項４３に記載のシステム。
【請求項４５】
信号を受信するための入力デバイスを更に備え、前記プロセッサは、前記入力デバイスに結合され、前記プロセッサは、前記信号を時間領域ベクトルｘ＾に変換するように構成され、前記プロセッサは、チャープＺ変換を用いて前記時間領域ベクトルから前記周波数領域ベクトルＸを生成する、請求項４３に記載のシステム。
【請求項４６】
前記プロセッサは、前記ＩＣＺＴを用いて前記周波数領域ベクトルＸを前記時間領域ベクトルｘに写像する前に、前記周波数領域ベクトルＸに対して動作を実行するようにさらに構成されることができ、前記動作は、前記周波数領域ベクトルＸの要素の少なくとも１つを修正する、請求項４３に記載のシステム。
【請求項４７】
前記メモリデバイスは、前記プロセッサが前記ＩＣＺＴを用いて前記周波数領域ベクトルＸを前記時間領域ベクトルｘに写像している期間中に、行列Ａ−１、Ｑ−１、
【数Ａ１４】
0006928208.tif 000162
、
【数Ａ１４Ｔ】
0006928208.tif 000163
、
【数Ｄ１４Ｔ】
0006928208.tif 000164
、及び
【数Ｄ１４】
0006928208.tif 000165
、及びＰ−１のすべての要素を格納しない、請求項４３に記載のシステム。
【請求項４８】
前記プロセッサは、増加した浮動小数点精度を用いてそれの計算を実行することができる、請求項４３に記載のシステム。
【請求項４９】
前記プロセッサは、３２ビットより大きい増加した浮動小数点数を用いてそれの計算を実行することができる、請求項４８に記載のシステム。
【請求項５０】
前記メモリデバイスは、前記プロセッサが、前記ＩＣＺＴを用いて前記周波数領域ベクトルＸを前記時間領域ベクトルｘに写像している間中に、ほんのＯ（ｎ）のメモリを使用し、ここで、ｎ＝ｍａｘ（Ｍ、Ｎ）である、請求項４３に記載のシステム。
【請求項５１】
前記プロセッサは、前記プロセッサが前記ＩＣＺＴを用いて前記周波数領域ベクトルＸを前記時間領域ベクトルｘに写像する間中に、Ｏ（ｎ２）又はより少ない基本演算を実行し、ここで、ｎ＝ｍａｘ（Ｍ、Ｎ）である、請求項４３に記載のシステム。
【請求項５２】
前記プロセッサは、前記写像中にＯ（ｎｌｏｇ（ｎ））演算を実行する、請求項５１に記載のシステム。
【請求項５３】
前記システムは、パーソナルコンピュータ（ＰＣ）、システムオンチップ（ＳｏＣ）、特定用途向け集積回路（ＡＳＩＣ）を含むシステム、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）を含むシステム、又はグラフィックス処理ユニット（ＧＰＵ）を含むシステムのうちの少なくとも１つである、請求項４３に記載のシステム。
【請求項５４】
前記周波数領域ベクトルＸは、同じパラメータＡイタリック及びＷイタリックを持つチャープＺ変換を用いて特定の時間領域ベクトルｘから計算されない、請求項４３に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般には、逆チャープｚ変換に関し、より詳細には、Ｏ（ｎ×ｌｏｇ（ｎ））（以下「Ｏ（ｎｌｏｇ（ｎ））と記す」）時間及びびＯ（ｎ）メモリで逆チャープｚ変換を計算するための方法及びシステムに関する。
【背景技術】
【０００２】
チャープＺ変換（ＣＺＴ）は、単位円に替えて対数らせん輪郭線上にサンプルが配置されることを可能にすることによって、離散フーリエ変換（ＤＦＴ）を拡張する。より具体的には、該変換は、式ＡイタリックＷイタリック−ｋ（ｋ＝０、１、２、…、Ｍ−１）で定義される対数らせん輪郭線に沿ってサンプルを分布させる。非ゼロの複素数Ａイタリック及びＷイタリックは、スパイラル輪郭線の方向及び位置、並びに輪郭線上におけるサンプル点の間隔を指定する。より具体的には、Ｎ要素の入力ベクトルｘが与えられると、ＣＺＴは、Ｍ要素の出力ベクトルＸを計算し、ここで、Ｘのｋ番目の要素は、
【数１】
0006928208.tif 000002
で与えられる（ここで、Ｗイタリック及びＡイタリックは、それぞれ、上記式においてイタリック体のＷ及びＡを示す）。
【発明の概要】
【０００３】
順チャープｚ変換を計算できる効率的なアルゴリズムは、以前に説明された。そのアルゴリズムは、Ｏ（ｎｌｏｇ（ｎ））時間で動作し、ここで、ｎは変換のサイズである。入力数Ｎ及び出力数Ｍが異なり得るので、最も一般的なケースでは、ＣＺＴアルゴリズムの計算複雑性は、ｎ＝ｍａｘ（Ｍ、Ｎ）によって特定される。
【０００４】
効率的なＣＺＴアルゴリズムは、高速畳み込みを用いて変換を表現するためにインデックス置換を用いて導出されることができ、インデックス置換は、もともとは、「Ａ  ｌｉｎｅａｒ  ｆｉｌｔｅｒｉｎｇ  ａｐｐｒｏａｃｈ  ｔｏ  ｔｈｅ  ｃｏｍｐｕｔａｔｉｏｎ  ｏｆ  ｄｉｓｃｒｅｔｅ  Ｆｏｕｒｉｅｒ  ｔｒａｎｓｆｏｒｍ」、ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ａｕｄｉｏ  ａｎｄ  Ｅｌｅｃｔｒｏａｃｏｕｓｔｉｃｓ，１８（４）：４５１−４５５，１９７０，においてブルースタイン（Ｂｌｕｅｓｔｅｉｎ）によって提案されたものであって、これは、参照によりその全体が本明細書に組み込まれる。ＣＺＴアルゴリズムのために、様々な役立つ最適化が提案されてきた。それでも、計算複雑性はＯ（ｎｌｏｇ（ｎ））に留まったままである。
【０００５】
逆チャープＺ変換（ＩＣＺＴ）は、チャープｚ変換（ＣＺＴ）の逆である。つまり、ＩＣＺＴは、ＣＺＴの出力を逆向きに入力へ写像する。ＣＺＴは、線形変換であるので、ＣＺＴは、ＣＺＴ行列と入力ベクトルとの行列の積を用いて表現されることができる。この行列は、標準アルゴリズムを用いて反転されることができる。アルゴリズム形式においては、しかしながら、このプロセスは、最大でＯ（ｎ３）の演算を必要とすることがある。
【０００６】
Ｏ（ｎ３）よりも高速で動く効率的な行列反転アルゴリズムがあるとしても、少なくともｎ２の演算が、ｎ×ｎ行列（ｎ行ｎ列の行列）の各要素にアクセスするために必要である。これ故に、Ｏ（ｎ２）は、メモリ内の完全なｎ×ｎ行列と共に働くＩＣＺＴアルゴリズムの計算複雑性の下限である。
【０００７】
効率的であるために、ＩＣＺＴアルゴリズムは、ＣＺＴアルゴリズムと同じ計算複雑さ、つまりＯ（ｎｌｏｇ（ｎ））を有しなければならない。この要求は、変換行列をメモリに保存することを必要とするいかなる方法を排除する。
【０００８】
効率的なＩＣＺＴアルゴリズムを導き出すためのいくつかの試みが為されてきた。一のケース（Ｆｒｉｃｋｅｙ、「Ｕｓｉｎｇ  ｔｈｅ  ｉｎｖｅｒｓｅ  ｃｈｉｒｐ−ｚ  ｔｒａｎｓｆｏｒｍ  ｆｏｒ  ｔｉｍｅ−ｄｏｍａｉｎ  ａｎａｌｙｓｉｓ  ｏｆ  ｓｉｍｕｌａｔｅｄ  ｒａｄａｒ  ｓｉｇｎａｌｓ」、Ｔｅｃｈｎｉｃａｌ  ｒｅｐｏｒｔ，  Ｉｄａｈｏ  Ｎａｔｉｏｎａｌ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｌａｂ．，Ｉｄａｈｏ  Ｆａｌｌｓ，  ＩＤ，  １９９５、その全体が参照により本明細書に組み込まれる）に記載されたものでは、順ＣＺＴアルゴリズムの修正版は、ＩＣＺＴアルゴリズムとして説明されたものであって、その修正版では、対数らせん輪郭が反対方向に横断されている。しかしながら、この方法は、実際にはＣＺＴを反転しない。これは、いくつかの特別な場合のみ、例えばＡイタリック＝１及びＷイタリック＝ｅ−２πｉ／ｎの場合、に機能する。それは、ＣＺＴがＤＦＴに帰着する場合である。一般的な場合、つまりＡイタリック、Ｗイタリック∈Ｃ＼｛０｝の場合、この方法は、ＣＺＴを反転しない変換を生成する。
【０００９】
本願の実施は、ＩＣＺＴを計算するための効率的なＯ（ｎｌｏｇ（ｎ））方法を説明する。この方法は、Ｏ（ｎ）メモリでよりコンパクトに構造化された行列（例えば、対角行列、ヴァンデルモンド行列、テプリッツ行列、循環行列、又はスキュー循環行列）を表現するために、生成ベクトルを使用する。ＩＣＺＴは、単位円から外れた逆高速フーリエ変換（ＩＦＦＴ）の一般化としてみなされることができる。換言すれば、ＩＣＺＴの複素パラメータＡイタリック及びＷイタリックは、複素平面において対数らせん輪郭線を描写する。ＩＦＦＴのようではなく、ＩＣＺＴは、指数関数的に増加する又は指数関数的に減衰する周波数成分に対応しており単位円から外れた輪郭点を使用することができる。本願の実施は、ＣＺＴ又はＩＣＺＴの数値精度を改善するための方法を、｜Ｗイタリック｜＜１（「Ｗイタリック」の絶対値が１より小さいこと）であるケースの場合に説明し、この場合は、付録Ａに与えられる。
【００１０】
発明者らは、彼らの知る限り、本願が効率的なＩＣＺＴアルゴリズムの最初の開示であると考えている。特に、実用的なアルゴリズムが、そしてその導出も、説明される。更に、アルゴリズムの精度は、自動化されたテストケースを用いて検証される。
【００１１】
アルゴリズムは、構造化行列の乗算を用いてＣＺＴ式を表現すると共にそれからその式を逆転する方法を見つけることによって導出された。ＩＣＺＴ計算の本質は、特別に構築されたヴァンデルモンド行列Ｗを反転することに帰着する。この問題は、順に、Ｗから導出された特別に構成されたテプリッツ行列
【数２】
0006928208.tif 000003
（以下、文章中で「Ｗ＾」と記す）を反転することに帰着する。
【００１２】
本願の他の態様、目的、及び利点は、添付の図面と併せて以下の詳細な説明からより明らかになるであろう。
【図面の簡単な説明】
【００１３】
本明細書に組み込まれる共に該明細書の一部を形成する添付図面は、本願のいくつかの態様を示し、またその説明と共に、本願の原理を説明するために役立つ。図面において：
【００１４】
【図１Ａ】図１Ａは、３２点を持つ対数らせん輪郭線の例を描いており、ここで、輪郭の開始は、塗りつぶされていない円を用いて示されている。
【図１Ｂ】図１Ｂは、６４点を持つ対数らせん輪郭線の例を描いており、ここで、輪郭の開始は、塗りつぶされていない円を用いて示されている。
【００１５】
【図２】図２は、図１Ａ及び図１Ｂに示されるような形状を持つが異なる点数Ｍを持つ輪郭線の場合及び異なる浮動小数点精度を用いる計算の場合、ＩＣＺＴが後に続くＣＺＴを実行するための数値精度の例を提供するチャートである。
【００１６】
【図３】図３は、異なるタイプの構造化行列の行列形状及び生成ベクトルの例示を提供するチャートである。
【００１７】
【図４Ａ】図４Ａは、ＦＦＴ又はＩＦＦＴによって使用された固定振幅の複素指数関数を図示する例を与える。
【図４Ｂ】図４Ｂは、ＣＺＴ又はＩＣＺＴによって使用されることができる指数関数的に増加する又は指数関数的に減衰する複素指数関数を図示する例を与える。
【００１８】
【図５Ａ】図５Ａは、対数らせん輪郭線の例を示しており、該輪郭線の点は基準円の外側に置かれている。
【図５Ｂ】図５Ｂは、対数らせん輪郭線の例を示しており、該輪郭線の点は基準円の内側に置かれている。
【図５Ｃ】図５Ｃは、対数らせん輪郭線の例を示しており、該輪郭線の点は基準円の外側から始まり内側で終わる。
【図５Ｄ】図５Ｄは、対数らせん輪郭線の例を示しており、該輪郭線の点は基準円の内側から始まり外側で終わる。
【００１９】
【図６Ａ】図６Ａは、対数らせん輪郭線の例を示しており、該輪郭線の点は、９０度の範囲にわたる単位円上に置かれる。
【図６Ｂ】図６Ｂは、対数らせん輪郭線の例を示しており、該輪郭線の点は、１８０度の範囲にわたる単位円上に置かれる。
【図６Ｃ】図６Ｃは、対数らせん輪郭線の例を示しており、該輪郭線の点は、３６０度の範囲にわたる単位円上に置かれる。
【００２０】
【図７Ａ】図７Ａは、３６０度の２回の軸中心回転の範囲にわたる対数らせん輪郭線の例を示す。
【図７Ｂ】図７Ｂは、３６０度の５回の軸中心回転の範囲にわたる対数らせん輪郭線の例を示す。
【００２１】
本願は、特定の好ましい実施例に関連して説明される一方で、それらの実施例に限定する意図はない。それどころか、その意図は、添付の特許請求の範囲によって定義された本願の精神及び範囲内に含まれた全ての代替物、修正物、及び等価物を網羅することである。
【発明を実施するための形態】
【００２２】
本開示の実施例は、Ａイタリック、Ｗイタリック∈Ｃ＼｛０｝に対してＩＣＺＴを実施する効率的なＯ（ｎｌｏｇ（ｎ））ＩＣＺＴアルゴリズムを説明する。ＩＣＺＴは、単位円の替わりに複素平面上の対数らせん輪郭線にサンプル点を分布させることを許容することによって、高速逆フーリエ変換（ＩＦＦＴ）を一般化する。２つの例示的な対数らせん輪郭線が、図１Ａ及び図１Ｂに示される。サンプル点が単位円上にないときはいつでも、対応する周波数成分が指数関数的に増加又は減少する。図４Ａ、図４Ｂは、ＦＦＴ／ＩＦＦＴ及びＣＺＴ／ＩＣＺＴによって使用された増大する振幅、減衰する振幅、及び定振幅の周波数成分の例を示す。
【００２３】
ＩＣＺＴアルゴリズムは、構造化行列の積としてＣＺＴの定式を表すことと共に行列の式を反転する方法を見出すことによって導出された。より具体的には、ＩＣＺＴを計算することは、ヴァンデルモンド行列Ｗの特殊なケースを反転することに帰着する。これは、Ｗから派生したテプリッツ行列Ｗ＾の特殊なケースを反転することによって達成されることができる。
【００２４】
構造化行列は、それらの要素の総数よりも少ないパラメータを用いて説明されることができる行列である。構造化行列の例は、テプリッツ行列、ハンケル行列、ヴァンデルモンド行列、コーシー行列を包含する。他の例は、循環行列、スキュー循環行列、及びＤＦＴ行列を包含する。対角行列も、また構造化行列と見されることができる。図３は、これらの構造化行列のいくつかの一般的な形状を示す。図３に示された例は、３×３行列の場合である。さらに、図３は、各行列を生成するために使用されることができる生成ベクトルを例示する。ほとんどの場合、これらは、行列の第１行及び第１列を指定するｒ及びｃで表示される。
【００２５】
Ｇｏｈｂｅｒｇ及びＳｅｍｅｎｃｕｌは、テプリッツ行列の逆行列がテプリッツ行列の２つの積の差を用いて表現されることができることを示した。この研究は、Ｉ．Ｇｏｈｂｅｒｇ  ｅｔ  ａｌ．，  「Ｏｎ  ｔｈｅ  ｉｎｖｅｒｓｉｏｎ  ｏｆ  ｆｉｎｉｔｅ  Ｔｏｅｐｌｉｔｚ  ｍａｔｒｉｃｅｓ  ａｎｄ  ｔｈｅｉｒ  ｃｏｎｔｉｎｕｏｕｓ  ａｎａｌｏｇｓ」，Ｍａｔ．  ｉｓｓｌｅｄ，２（１）：２０１−２３３，１９７２、及びＷｉｌｌｉａｍ  Ｔｒｅｎｃｈ，「Ａｎ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｉｎｖｅｒｓｉｏｎ  ｏｆ  ｆｉｎｉｔｅ  Ｔｏｅｐｌｉｔｚ  ｍａｔｒｉｃｅｓ」，Ｊｏｕｒｎａｌ  ｏｆ  ｔｈｅ  Ｓｏｃｉｅｔｙ  ｆｏｒ  Ｉｎｄｕｓｔｒｉａｌ  ａｎｄ  Ａｐｐｌｉｅｄ  Ｍａｔｈｅｍａｔｉｃｓ，１２（３）：５１５−５２２，１９６４に見出され，これらの参考文献の両方は、参照によりその全体が本明細書に組み込まれる。該文献では、この結果は、しばしば「Ｇｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式」と参照される。この式における４つの行列は、上三角テプリッツ又は下三角テプリッツのいずれかであって、２つのベクトルｕ及びｖによって生成される。ＩＣＺＴの場合、反転されるべきテプリッツ行列も、また、対称である。これは、１つの生成ベクトルのみを用いて、つまりベクトルｕのみを用いて、逆行列を表現するＧｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式の簡易バージョンに至る。
【００２６】
本発明者らは、ＩＣＺＴの場合に、生成ベクトルｕを複素数Ｗイタリックの関数として定義する式を導出することが可能であることを特定した。この式は、効率的なＩＣＺＴアルゴリズムに至った。このアルゴリズムは、テプリッツ行列にベクトルを乗算するステップを含み、これは、Ｏ（ｎｌｏｇ（ｎ））で為され、全テプリッツ行列をメモリに保存することなく行われる。付録（Ａｐｐｅｎｄｉｘ）Ｃ、Ｄ、及びＥは、この積を計算できる該参考文献に基づき３つの異なるアルゴリズムを実施する。これらのアルゴリズムの各々は、ＩＣＺＴアルゴリズムのビルディングブロックとして使用されることができる。高速フーリエ変換（ＦＦＴ）アルゴリズムは、付録Ｂに記載されており、これら３つのアルゴリズムの各々において使用される。
【００２７】
より広いインパクト。
【００２８】
離散フーリエ変換（ＤＦＴ）、及び高速フーリエ変換（ＦＦＴ）を用いるその効率的な実施は、非常に多様な今日のアプリケーションにおいて深く組み込まれている。ＣＺＴは、ＤＦＴの一般化であると共に、ＩＣＺＴは、逆ＤＦＴの一般化であるので、本願の潜在的な用途の数は非常に多い。これまでのところ、ＣＺＴアルゴリズムのみが、ＦＦＴと同じ計算複雑性、つまりＯ（ｎｌｏｇ（ｎ））を有した。本願は、逆ＦＦＴ（ＩＦＦＴ）と同じ複雑性を有するＩＣＺＴアルゴリズムを導き、これもまた、Ｏ（ｎｌｏｇ（ｎ））である。
【００２９】
言い換えれば、本願は、変形可能であり、なぜなら、本願が逆ＦＦＴを一般化する変換を実施するためだけでなく、新しいアルゴリズムが、本願が一般化するアルゴリズムと実行時間の同じ複雑性を有するからである。
【００３０】
ＩＣＺＴと共に使用されることができる対数らせん輪郭線は、外形の曲線を含み、該外形曲線の点が単位円の外側に、単位円の内側にあり、また外形曲線は、単位円の外側で始まりその内側で終わり、単位円の内側で始まりその外側で終わる。そのような輪郭線の例は、図５Ａから図５Ｄに示されている。さらには、輪郭点は、単位円上の部分円弧、例えば９０度の円弧、１８０度の円弧、又は完全な３６０度回転を対象に含めるようにしてもよく、これらにおいて輪郭線は、ＦＦＴ／ＩＦＦＴによって使用された輪郭線と同等であることができる。そのような輪郭の例は、図６Ａから図６Ｃに示される。最終的には、輪郭点は、複数の３６０度回転でさえも対象に含めるようにしてもよい。図７Ａから図７Ｂは、２回及び５回の完全回転の例を示す。一般には、回転の数は、整数でさえない場合がある。
【００３１】
構造化行列を用いてチャープＺ変換を表す
【００３２】
行列形式で表現された４×４ＣＺＴの例
【００３３】
この例は、行列表記を用いて４つの入力及び４つの出力を持つ特別な場合のためのＣＺＴを説明する。この場合、ＣＺＴは、以下の式を用いて定義される（ここで、式中におけるイタリック体のＷ及びＡは、それぞれ、文章中のＷイタリック及びＡイタリックを示す）。
【数２０１】
0006928208.tif 000004
【００３４】
仮にｘ＝（ｘ０、ｘ１、ｘ２、ｘ３）Ｔが、ＣＺＴ入力ベクトルを標記するとし、Ｘ＝（Ｘ０、Ｘ１、Ｘ２、Ｘ３）Ｔが出力ベクトルを標記するとする。これら２つのベクトルを用いて、４×４のＣＺＴは、また、次の行列の式を用いて表現されることができる。
【数２０２】
0006928208.tif 000005
【００３５】
つまり、ＣＺＴの例は、複素パラメータＡイタリックの負のべき乗によって生成された対角行列を入力ベクトルｘに乗算すると共に、結果のベクトルにヴァンデルモンド行列Ｗを乗算するものと見ることができ、ヴァンデルモンド行列Ｗは、複素パラメータＷイタリックによって特定される。
【００３６】
この例では、行列Ｗは以下の形式を有する：
【数２０３】
0006928208.tif 000006
【００３７】
行列Ｗを反転することは、ＩＣＺＴに至る。
【００３８】
ヴァンデルモンド行列Ｗを用いてＣＺＴを表すこと
【００３９】
一般的な場合では、ＣＺＴは、典型的には、以下の式を用いて定義される。
【数２０４】
0006928208.tif 000007
【００４０】
この式において、Ａイタリック及びＷイタリックは、対数らせん輪郭線及び対数らせん輪郭線上のサンプルの位置を定義する変換のための複素パラメータである。パラメータＮは、入力ベクトルｘのサイズを指定する整数である。最終的には、パラメータＭは、出力ベクトルＸのサイズを指定する整数である。一般には、ＮはＭと等しくないことがある。つまり、入力の次元は、出力の次元と等しくなくてもよい。
【００４１】
ＣＺＴは、また、行列形式で表現されることができる：
【数２０５】
0006928208.tif 000008
【００４２】
式（２．５）は、以下の短縮形で言い換えられることができる：
【数２０６】
0006928208.tif 000009
【００４３】
ここで、Ｗは、以下のＭ×Ｎの行列である。
【数２０７】
0006928208.tif 000010
【００４４】
Ｗがヴァンデルモンド行列であることを分かることができる。つまり、Ｗの各行は、等比数列を形作る。さらには、これらの数列の各々の各進行の公比は、パラメータＷイタリックの対応する整数のべき乗に等しい。
【００４５】
式（２．６）のＡイタリックの負の整数のべき乗は、ヴァンデルモンド行列Ｗの列をスケーリング処理する。行列Ｗは、ヴァンデルモンド行列の特殊なケースであるので、以下のように、対角行列とテプリッツ行列Ｗ＾との積として表されることができる。
【００４６】
ヴァンデルモンド行列Ｗからテプリッツ行列Ｗ＾を導出する。
【００４７】
行列Ｗは、ヴァンデルモンド行列の特別な場合であるので、２つの対角行列とテプリッツ行列Ｗ＾との積として表されることができる。以下の式を用いて、行列Ｗの各要素においてパラメータＷイタリックのべき乗を表すことができる。
【数２０８】
0006928208.tif 000011
【００４８】
式（２．８）は、（２．４）の右辺が以下のように表現されることができることを意味する。
【数２０９】
0006928208.tif 000012
【００４９】
最後の式における項は、より簡単に該項が行列の積に変換されることができるために、再配置されることができる：
【数２１０】
0006928208.tif 000013
【００５０】
項Ｗｋ×ｋ／２は、Ｍ×Ｍ対角行列Ｐに換わる。項Ｗｊ×ｊ／２Ａ−ｊは、２つのＮ×Ｎ対角行列Ｑ及びＡの積に換わる。最後に、項Ｗ−（ｋ−ｊ）×（ｋ−ｊ）／２Ａ−ｊは、Ｍ×Ｎテプリッツ行列Ｗ＾に換わる。Ｗ＾は以下に示される。
【数２１１】
0006928208.tif 000014
【００５１】
これは、この演算（付録Ｃ、Ｄ、及びＥを参照する）を実施するいくつかのＯ（ｎｌｏｇ（ｎ））アルゴリズムの１つを用いて行列Ｗ＾とベクトルとの積を効率的に計算できることを意味する。換言すれば、式（２．１０）は、以下の行列形式を有する：
【数２１２】
0006928208.tif 000015
この式において、すべての行列−ベクトルの積は、Ｏ（ｎｌｏｇ（ｎ））で計算されることができ、ここで、ｎ＝ｍａｘ（Ｍ、Ｎ）である。
【００５２】
要約すると、ＣＺＴアルゴリズムは、以下の行列の式の効率的な実施として見なされることができる：
【数２１３】
0006928208.tif 000016
ここで、Ｐ＝ｄｉａｇ（Ｗイタリック０×０／２、Ｗイタリック１×１／２、．．．、Ｗイタリック（Ｍ−１）×（Ｍ−１）／２）、Ｑ＝ｄｉａｇ（Ｗイタリック０×０／２、Ｗイタリック１×１／２、．．．、Ｗイタリック（Ｎ−１）×（Ｎ−１）／２）、Ａ＝（Ａイタリック−０、Ａイタリック−１、．．．Ａイタリック−（Ｎ−１））であり、Ｗは、（２．７）において定義されたヴァンデルモンド行列の特殊なケースであり、Ｗ＾は、（２．１１）において定義されたテプリッツ行列の特殊なケースである。前に説明されたように、ｘは、ＣＺＴへの入力ベクトルであり、ＸはＣＺＴからの出力ベクトルである。
【００５３】
テプリッツ行列の逆行列を表す
【００５４】
４×４ケースの場合のＧｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式
【００５５】
仮にＴが４×４テプリッツ行列であるものとする。つまり、
【数３０１】
0006928208.tif 000017
ここで、ａ、ｂ、ｃ、ｄ、ｆ、ｇ、及びｈは、行列Ｔを生成する７つの複素数である。
【００５６】
Ｇｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式は、４×４の非特異テプリッツ行列Ｔが以下の式を用いて反転されることができることを明示している。
【数３０２】
0006928208.tif 000018
ここで、ｕ＝（ｕ０、ｕ１、ｕ２、ｕ３）は、ｕ０≠０を満たす４つの要素のベクトルであり、ｖ＝（ｖ０、ｖ１、ｖ２、ｖ３）は、ｖ３≠０を満たす別の４つの要素のベクトルである。これら２つのベクトルは、行列Ｔを生成する数ａ、ｂ、ｃ、ｄ、ｆ、ｇ、及びｈによって特定される。しかしながら、Ｔを生成する７つの数の関数として明示的に表現することは困難である。
【００５７】
要約すると、式（３．２）は、４つの構造化行列を用いた４×４テプリッツ行列Ｔの逆行列：
１）ベクトルｕによって生成された下三角テプリッツ行列
【数Ａ１】
0006928208.tif 000019
；２）ベクトルｖの反転によって生成された上三角テプリッツ行列、
【数Ｃ１】
0006928208.tif 000020
；３）ｖを右へ一要素分だけシフトすることによって得られたベクトル（０、ｖ０、ｖ１、ｖ２）によって生成された下三角テプリッツ行列
【数Ｂ１】
0006928208.tif 000021
；４）ｕの反転を右へ一要素分だけシフトすることによって得られたベクトル（０、ｕ３、ｕ２、ｕ１）によって生成された上三角形テプリッツ行列
【数Ｄ１】
0006928208.tif 000022
を表す。
【００５８】
Ｇｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式の一般的ケース
【００５９】
仮にＴが、第１行を指定するベクトルｒ＝（ｒ０、ｒ１、ｒ２、．．．、ｒｎ−１）及び第１列を指定するベクトルｃ＝（ｃ０、ｃ１、ｃ２、．．．、ｃｎ−１）によって生成されたｎ×ｎテプリッツ行列であるものとする。ｒ０＝ｃ０であると仮定される。より正式には、
【数３０３】
0006928208.tif 000023
【００６０】
テプリッツ行列Ｔの逆行列Ｔ−１は、テプリッツでないかもしれない。それにもかかわらず、Ｇｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式は、上三角及び下三角テプリッツ行列を用いてＴ−１を表すことを可能にする。
【００６１】
つまり、Ｇｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式は、以下の行列の式を満たすベクトルｕ＝（ｕ０、ｕ１、ｕ２、．．．、ｕｎ−１）及びｖ＝（ｖ０、ｖ１、ｖ２、．．．、ｖｎ−１）が存在することを明記している。
【数３０４】
0006928208.tif 000024
【００６２】
換言すると、逆行列Ｔ−１は、ベクトルｕ及びベクトルｖによって生成された構造化行列と見なされることができる。この類推は、Ｔ−１にベクトルを乗算することに及ぶ。生成ベクトルｕ及びｖが特定される場合、そのとき、行列Ｔ−１とベクトルとの積は、構造化行列の乗算を用いて（３．４）を実施することによってＯ（ｎｌｏｇ（ｎ））で計算されることができる。
【００６３】
構造化行列を用いてＩＣＺＴを表す
【００６４】
式（２．１３）は、ＣＺＴが、Ｗ＾を除いて全行列が対角である行列−ベクトルの一連の乗算に誘導されることができることを示し、Ｗ＾は以下のテプリッツ行列である。
【数４０１】
0006928208.tif 000025
【００６５】
これは、ＩＣＺＴが、対角行列、逆行列Ｗ＾−１、及びベクトルの積として見なされることができることを意味する（式（２．１３）を参照する）。
【００６６】
仮にｕ及びｖが、Ｇｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式を用いてＷ＾−１を生成する２つのベクトルであるとし、つまり
【数４０２】
0006928208.tif 000026
【数４０３】
0006928208.tif 000027
【００６７】
行列Ｗ＾が対称であるので、その逆行列Ｗ＾−１も対称である。Ｗ＾−１のための式は、Ｇｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式の特別なケースである。ｎの最初のいくつかの値に対する逆行列Ｗ＾−１の特殊なケースを精査することによって、３つの有用な仮定が示唆された。第１に、ベクトルｕはＷ＾−１の第１列に等しい。より正式には、
【数４０４】
0006928208.tif 000028
【００６８】
第２に、ベクトルｖは、Ｗ−１の最後の列に等しく、つまり、
【数４０５】
0006928208.tif 000029
【００６９】
第３に、ベクトルｖはベクトルｕの逆転に等しい。
【数４０６】
0006928208.tif 000030
【００７０】
換言すれば、ベクトルｕのみを、構造化行列の乗算を用いて逆行列Ｗ＾−１にベクトルを乗算できるように特定することを必要とする。
【００７１】
ベクトルｕを計算するための明示的な式を導出する１つのアプローチは、ｎの最初のいくつかの値のための特別な場合から明示的な式を導出することである。この帰納法が成功すれば、そのとき、有限ｎごとに結果の式を使用することが可能になるべきである。ｕがｖを特定するので、このことは、Ｇｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式及び構造化行列の乗算を用いてＩＣＺＴアルゴリズムを定式化するために十分である。
【００７２】
テプリッツ行列W＾を反転させるための定式化の特別なケース
【００７３】
ｎ＝１の場合の特別なケース
【００７４】
ｎ＝１であると仮定する。そのとき、Ｗ＾は、１に等しい単一の数からなる１×１行列である。より正式には、
【数４０７】
0006928208.tif 000031
【００７５】
これは、逆行列Ｗ−１も単一の数値１からなる１×１行列であることを意味する。つもり、
【数４０８】
0006928208.tif 000032
【００７６】
Ｗ＾−１の最初及び最後の行は同一であり、共に１に等しい単一の要素でから成る。より正式には、
【数４０９】
0006928208.tif 000033
【数４１０】
0006928208.tif 000034
【００７７】
これは、Ｇｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式の縮退（ｄｅｇｅｎｅｒａｔｅ）した特別なケースをもたらす：
【数４１１】
0006928208.tif 000035
【００７８】
ｎ＝２の場合の特別なケース
【００７９】
ｎ＝２であると仮定する。そのとき、Ｗ＾は、以下の式によって指定される２×２行列である：
【数４１２】
0006928208.tif 000036
これは、Ｗイタリック∈Ｃ＼｛０｝毎に明確に定義される。
【００８０】
この場合、逆行列Ｗ＾−１も２×２の行列であり、これは、その第１列ｕが２つの要素のベクトル、つまりｕ＝（ｕ０、ｕ１）Ｔであることを意味する。それの要素は、次の線形系を解くことによって、Ｗイタリックの関数として表されることができる。
【数４１３】
0006928208.tif 000037
【００８１】
この式において、ｅ０は、第１要素が１に設定される共に残りの要素がゼロに設定されるベクトルを示し、つまり、
【数４１４】
0006928208.tif 000038
【００８２】
換言すれば、Ｗ＾の第１行とベクトルｕとのドット積は、１に等しくなければならず、またＷ＾の第２行とベクトルｕとのドット積は、０に等しくなければならない。
【００８３】
線形系（４．１３）は、Ｗ＾の４要素及びｕの２要素の観点で表されることができる。これにより、次の（４．１３）の拡張形式に至る。
【数４１５】
0006928208.tif 000039
【００８４】
前の式は、また、２つのスカラ線形系の式として見られることできる。
【数４１６】
0006928208.tif 000040
【数４１７】
0006928208.tif 000041
【００８５】
これらの式の両方は、Ｗイタリック≠０であるときはいつでも明確に定義される。
【００８６】
項ｕ０Ｗ−１／２が（４．１７）の両側から差し引かれることができ、これは、Ｗイタリック及びｕ０の関数としてｕ１の値のための式を至る：
【数４１８】
0006928208.tif 000042
【００８７】
上記の式の右辺は、（４．１６）に当てはめられることができる。これにより、結果として、ｕ０及びＷイタリックのみに依存する式になる。
【数４１９】
0006928208.tif 000043
【００８８】
前の式の両側にＷイタリック／（Ｗイタリック−１）を乗算すると、Ｗイタリックの関数としてｕ０の値のための式になる：
【数４２０】
0006928208.tif 000044
【００８９】
この値を（４．１８）の右側に当てはめると、結果として、Ｗイタリックの関数としてｕ１の値を表す式になる。より正式には、
【数４２１】
0006928208.tif 000045
【００９０】
要約すると、２×２のケースでは、逆行列Ｗ＾−１の第１列を指定する列ベクトルｕは、パラメータＷイタリックの以下の関数として表されることができる。
【数４２２】
0006928208.tif 000046
【００９１】
ベクトルｖは、ｕの要素を逆転にすることによって取得されることができる。
つまり、
【数４２３】
0006928208.tif 000047
【００９２】
逆行列Ｗ＾−１のための閉形式表現は、ｕ及びｖのための式を組み合わせることによって導出されることができる。つまり、
【数４２４】
0006928208.tif 000048
【００９３】
この特別なケースでは、Ｇｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式は、以下の一連の行列変換を用いて検証されることができる。検証は、（３．４）に記載された式の左辺及び右辺の差分から始まり、この差がゼロに等しいことを示す。
【数４２５】
0006928208.tif 000049
【００９４】
ｎ＝３の場合の特別なケース
【００９５】
この特別なケースでは、Ｗ＾は、３×３のテプリッツ行列である。Ｗ＾の各要素は、変換パラメータＷイタリックの関数である。より正式には、
【数４２６】
0006928208.tif 000050
【００９６】
逆行列Ｗ＾−１は、また、３×３の行列であり、しかし２×２のケースとは異なり、もはやテプリッツではない。仮にｕがＷ＾−１の最初の列であるものとし、つまり
【数４２７】
0006928208.tif 000051
【００９７】
２×２ケースと同様に、ベクトルｕは、以下の線形系の解である：
【数４２８】
0006928208.tif 000052
【００９８】
前のケースとは対照的に、しかしながら、この場合にはｅ０は、２つの要素の代わりに３つの要素からなる列ベクトルを示す。ｅ０の最初の要素は１に等しい。ｅ０の残りの２つの要素は、０に等しい。換言すれば、
【数４２９】
0006928208.tif 000053
【００９９】
線形系（４．２８）は、Ｗ＾を構成する９つの要素及びｕを構成する３つの要素の観点で表現されることができる。この拡張の結果が以下に示される。
【数４３０】
0006928208.tif 000054
【０１００】
この線形系は、また、３つの未知数を持つ３方程式の系を用いてスカラ形式で表現されることもできる。これら３つの方程式の各々の左辺は、Ｗ＾の行とベクトルｕとの間のドット積に等しい。右辺は、ｅ０の対応する要素に等しい。より正式には、
【数４３１】
0006928208.tif 000055
【数４３２】
0006928208.tif 000056
【数４３３】
0006928208.tif 000057
【０１０１】
この線形方程式系を解くと、パラメータＷイタリックの関数としてベクトルｕを表す式に至り、これは以下に示される。
【数４３４】
0006928208.tif 000058
【０１０２】
逆行列Ｗ＾−１は、以下の形式を有する。
【数４３５】
0006928208.tif 000059
【０１０３】
ベクトルｖがＷ＾−１の最後の列を指定すると共にその列がベクトルｕの逆に等しいことに留意されたく、またベクトルｕは、行列の最初の列を指定する。換言すれば、前の式は、３つの仮定（４．４）、（４．５）、及び（４．６）を裏付けている。
【０１０４】
ｎの他の値に対してこのプロセスを繰り返すことにより、ｕを特定する一般式を導出することが可能になる。次のセクションでは、この定式を記述する。
【０１０５】
テプリッツ行列Ｗ＾を反転するための一般式
【０１０６】
一般的なケースでは、ベクトルｕは、Ｗ＾−１の最初の列を指定しており、ベクトルｕの要素は、以下の式を用いて計算されることができる。
【数４３６】
0006928208.tif 000060
【０１０７】
ｋ毎に、ｕｋの値が、（４．３６）の右辺の分母に現れる多項式の積の事前計算値を用いて、Ｏ（１）で計算されることができる。これらの値は、個別のループで計算され、該ループはＯ（ｎ）で動作する。
【０１０８】
ｕの結果値及びそれの逆転は、逆行列Ｗ＾−１を計算するためにＧｏｈｂｅｒｇ−Ｓｅｍｅｎｃｕｌの式（３．４）に当てはめられることができ、上記逆転は、ｖに等しいものである。それは、また、テプリッツ行列とベクトルとの積を計算する効率的なアルゴリズムのための生成ベクトルとして使用されることもできる。これらのアルゴリズムは、実際にメモリにＷ＾−１を格納することなく行列Ｗ＾−１にベクトルを乗算することを実行するシーケンスにおいて、呼び出されることができる。これにより、結果として、Ｏ（ｎｌｏｇ（ｎ））で動作するＩＣＺＴアルゴリズムになる。
【０１０９】
行列形式におけるＩＣＺＴ
【０１１０】
以下の式は、ＩＣＺＴを行列形式で示す：
【数４３７】
0006928208.tif 000061
ここで、Ａ−１＝ｄｉａｇ（Ａ０、Ａ１、．．．、ＡＮ−１）、Ｑ−１＝ｄｉａｇ（Ｗ０×０／２、Ｗ１×１／２、．．．、Ｗ（Ｎ−１）×（Ｎ−１）／２）、及びＰ−１＝ｄｉａｇ（Ｗ０×０／２、Ｗ１×１／２、．．．、Ｗ（Ｍ−１）×（Ｍ−１）／２）である。
【０１１１】
つまり、式は、ＣＺＴの入力ベクトルｘをその出力ベクトルＸから計算する方法を示す。この式は、順変換の式（２．１３）の対角行列を反転すると共に行列Ｗ＾をその逆Ｗ＾−１で置き換えることによって導出された。
【０１１２】
式（４．３７）における各行列は、対角行列であるか、又はテプリッツ行列の積の差として表されることができる。該式を実施すると、ＩＣＺＴを計算するためのＯ（ｎｌｏｇ（ｎ））アルゴリズムに至り、これは、アルゴリズム５．２において以下に与えられる。アルゴリズムは、中間の行列をメモリに格納することなく行列−ベクトルの全ての演算の結果を計算するために、生成ベクトルを用いて全ての行列計算を効率的に実行する。アルゴリズムは、動作するためにＯ（ｎ）メモリを必要とする。
【０１１３】
例
【０１１４】
３×３のケースでは、ＣＺＴは、以下の行列の方程式を用いて表現されることができる：
【数４３８】
0006928208.tif 000062
【０１１５】
そのケースでは、ＩＣＺＴのための拡張された行列方程式は、次のように見える：
【数４３９】
0006928208.tif 000063
【０１１６】
逆行列Ｗ＾−１は、（４．３５）において与えられる。アルゴリズムは、しかしながら、この行列を明示的には構築しない。上記のように、Ｗ＾−１は、次のように表されることができる。
【数４４０】
0006928208.tif 000064
ここで、ベクトルｕ＝（ｕ０、ｕ１、ｕ２）は（４．３４）によって与えられ、ベクトルｖ＝（ｖ０、ｖ１、ｖ２）＝（ｕ２、ｕ１、ｕ０）はｕの逆である。ｕ及びｖのこれらの値に対して、式（４．４０）は、以下の形式を有する：
【数４４１】
0006928208.tif 000065
【０１１７】
さらに、行列
【数Ｃ２】
0006928208.tif 000066
は、行列
【数Ａ２】
0006928208.tif 000067
の転置に等しく、また行列
【数Ｂ２】
0006928208.tif 000068
は、行列
【数Ｄ２】
0006928208.tif 000069
の転置に等しい。これ故に、逆行列W＾−１は、以下の簡単な形式
【数４４２】
0006928208.tif 000070
で表される。さらには、
【数Ａ３】
0006928208.tif 000071
及び
【数Ｄ３】
0006928208.tif 000072
の両方は、ベクトルｕの要素から生成されることができる。
【０１１８】
（４．４２）を（４．３７）に代入すると、ＩＣＺＴのための以下の行列方程式になる：
【数４４３】
0006928208.tif 000073
代わりに、式（４．４３）は、これらの行列の構造をうまく活用することによって効率的に計算される。上記のように、これら４つのテプリッツ行列は明示的に構築されていない。
【０１１９】
ＣＺＴアルゴリズム及びＩＣＺＴアルゴリズム
【０１２０】
アルゴリズム５．１は、ＣＺＴアルゴリズムの擬似コードを提供する。アルゴリズムは、テプリッツ行列にベクトルを乗算するために、畳み込み系のアルゴリズムＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹＣを使用し、これは、付録Ｅに説明されている。テプリッツ行列とベクトルとの積を計算するための他のアルゴリズムが、代わりに使用されることができる。例えば、付録Ｃにおいて説明されたＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹＥ及び付録Ｄにおいて説明されたＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹＰは、計算複雑性を変更することなく、アルゴリズム５．１におけるＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹＣに置き換わることができる。
【表５１】
0006928208.tif 000074
【０１２１】
アルゴリズム５．２は、ＩＣＺＴアルゴリズムのための擬似コードを与える。これは、実際にメモリに行列を保存せずに、逆行列の式（４．４２）を実施する。アルゴリズムは、Ｏ（ｎｌｏｇ（ｎ））で動作し、ここで、ｎ＝ｍａｘ（Ｍ、Ｎ）である。この実施は、ケースｎ＝Ｍ＝Ｎの場合のみをサポートする。上記のように、関数ＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹＣが、２３から２６行目上において使用されており、この関数は、アルゴリズムの計算複雑性を変更することなく、ＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹＥ又はＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹＰに置き換えられることができる。
【表５２】
0006928208.tif 000075
【０１２２】
図２は、計算中に浮動小数点数によって使用されたビット数及び変換サイズＭの関数としてＩＣＺＴの数値精度を与える。図１Ａ及び図１Ｂにおける２つの対数らせん輪郭線は、図２におけるＭ＝３２及びＭ＝６４に対応する。Ａイタリックの値は、図２の全ての行に対して１．１に設定された。Ｗイタリックの値は、式
【数３】
0006928208.tif 000076
を用いて特定された。数値精度は、ＩＣＺＴが続くＣＺＴを実行すると共にＣＺＴの入力とＩＣＺＴの出力との間のユークリッド距離を計算することによって計算された。最終的な精度は、１００個のランダムな入力ベクトルにわたって平均された。図２の第２列は、変換行列の条件数を示す。高い条件数にもかかわらず、この問題は、高精度の浮動小数点数が使用されている場合に、Ｍの大きい値でも可解である。
【０１２３】
アルゴリズム５．３は、ＩＣＺＴ−ＲＥＣＴアルゴリズムのための擬似コードを与え、このアルゴリズムは、Ｎ≦Ｍであるときのケースの場合に逆アルゴリズムを実施する。このアルゴリズムは、第２パラメータがＭに設定された状態でアルゴリズム５．２を呼び出し、その後に、その出力ベクトルの最初のＮ個の要素のみを返す。
【表５３】
0006928208.tif 000077
【０１２４】
ＩＣＺＴアルゴリズムを説明してきたので、アルゴリズムのための適用が、いまここに提供される。その観点において、以下は、ＩＣＺＴアルゴリズムの有用ないくつかの適用の一部のリストにすぎない。実施例では、ＩＣＺＴアルゴリズムは、レーダ系のセンサから受信され又はレーダ系のセンサへ送信されたデータを解析し又は生成するための用途において使用される。他の実施例では、ＩＣＺＴアルゴリズムは、ソナーセンサへ送信され又はソナーセンサから受信されたデータを生成し又は解析する用途において使用される。さらなる他の実施では、ＩＣＺＴアルゴリズムは、他の測距系センサから送信され又は他の測距系センサへ受信されたデータを生成し又は解析するための用途において使用される。
【０１２５】
さらに他の実施例では、ＩＣＺＴアルゴリズムは、ＩＣＺＴアルゴリズムのハードウェアの実施において使用される。実施例において、ハードウェア実施は、メモリデバイス及びプロセッサを含む様々なシステム、例えば、パーソナルコンピュータ、チップ（例えば、システムオンチップ）、特定用途向け集積回路（ＡＳＩＣ）を含むシステム、グラフィックス処理ユニット（ＧＰＵ）を含むシステム、又はフィールドプログラマブルゲートアレイ（ＦＰＧＡ）である。
【０１２６】
更なる実施では、ＩＣＺＴアルゴリズムは、明示的に定式化された線形系を解く又は行列を明示的に反転するより遅い方法を置き換えることによって、ＩＣＺＴを計算することを必要とするアプリケーションの速度を改善する際に使用される。加えて、ＩＣＺＴアルゴリズムは、従来使用されていたＦＦＴ及びＩＦＦＴを、全体又は一部において置き換えることができる。この置換により、計算システムの範囲を拡張して、単位円の内側又は外側にある対数らせん輪郭線上の点を対象に含めることができる。さらには、ＩＣＺＴの計算に先だって又は計算中に、周波数領域ベクトルは、ＩＣＺＴによって返される時間領域ベクトルが、周波数領域ベクトルを生成するために使用された時間領域ベクトルと異なるように、修正されることができる。例えば、演算は、周波数領域ベクトルに対して実行されることができ、ベクトルから特定の要素又は周波数をフィルタ処理するといったものである。
【０１２７】
さらに、実施例においては、ＩＣＺＴアルゴリズムは、医療画像化用途、例えばＣＴ、ＰＥＴ、又はＭＲＩにおいて使用される。加えて、ＩＣＺＴアルゴリズムは、信号処理、信号分析、信号合成、音声及び音声処理、並びに画像処理における用途において使用される。信号処理の用途では、ＣＺＴ又はＦＦＴの入力ベクトルは、信号をサンプリングすることといった、音声又は画像の信号から導かれた時間領域ベクトルである可能性がある。ＣＺＴ又はＦＦＴの出力ベクトルは、そのときには、それらの信号の周波数領域ベクトル表現であってもよい。
【０１２８】
以下の付録Ａ〜付録Ｅは、ＩＣＺＴアルゴリズムの実施に関する追加情報を提供する。
【０１２９】
付録（Ａｐｐｅｎｄｉｘ）Ａ：ＣＺＴ及びＩＣＺＴの数値精度を改善する対数らせん輪郭線の方向を反転すること
【０１３０】
この付録は、計算された変換の数値精度を改善するＣＺＴ及びＩＣＺＴアルゴリズムの代替バージョンを説明する。これは、｜Ｗイタリック｜（Ｗイタリックの絶対値）＜１のときチャープ輪郭線の方向を反転すること、及び｜Ｗイタリック｜（Ｗイタリックの絶対値）≧１のとき元の方向を保つことによって達成される。反転された輪郭線のためのパラメータは、Ｗイタリック′＝Ｗイタリック−１及びＡイタリック′＝ＡイタリックＷイタリック−（１−Ｍ）である。変換パラメータの具体的な値に依存して、数値の精度の改善は、数桁を超えることがある。
【０１３１】
アルゴリズムＡ．１は、｜Ｗイタリック｜（Ｗイタリックの絶対値）＜１のとき輪郭線の反転を実行するＣＺＴアルゴリズムの代替バージョンのための擬似コードを与える。アルゴリズムＡ．２は、その場合における輪郭線の反転をまた実行するＩＣＺＴアルゴリズムの代替バージョンのための擬似コードを与える。
【０１３２】
これらのアルゴリズムを用いて、ＣＺＴ及びＩＣＺＴの両方の数値精度は、増加する対数らせんであるチャープ輪郭に対して、つまり｜Ｗイタリック｜＜１の場合に、改善されることができる。それらの場合では、アルゴリズムＡ．１及びアルゴリズムＡ．２は、チャープ輪郭線の方向を反転する。さらにまた、この反転は、ベクトルＸにおける要素の順序の反転に伴って起こされ、これは、アルゴリズムＡ．１におけるＣＺＴ出力ベクトル及びアルゴリズムＡ．２におけるＩＣＺＴ入力ベクトルである。
【表Ａ１】
0006928208.tif 000078
【表Ａ２】
0006928208.tif 000079
【０１３３】
付録Ｂ：ＦＦＴ及び逆ＦＦＴのアルゴリズム
【０１３４】
この付録は、ＦＦＴアルゴリズム及び逆ＦＦＴアルゴリズムを記述する。アルゴリズムＢ．１は、高速フーリエ変換（ＦＦＴ）のための擬似コードを提供する。アルゴリズムＢ．２は、逆高速フーリエ変換（ＩＦＦＴ）のための擬似コードを提供する。ＦＦＴ及びＩＦＦＴの両方は、Ｏ（ｎｌｏｇ（ｎ））で動作する。
【表Ｂ１】
0006928208.tif 000080
【表Ｂ２】
0006928208.tif 000081
【０１３５】
付録Ｃ：テプリッツ行列にベクトルを乗算すること
【０１３６】
この付録は、テプリッツ行列にベクトルを乗算する一般向けの方法を説明する。仮にＡをｎ×ｎテプリッツ行列とすると共にｘがベクトルであるとする。行列Ａは、最初の行ｒ及び最初の列ｃによって指定され、ここで、ｒ０がｃ０に等しいと仮定される。この付録の例では、ｎが２のべき乗であると仮定する。このアプローチは、しかしながら、ｎの他の値に対しても働くように変更されることができる。より正式には、
【数Ｃ０１】
0006928208.tif 000082
【０１３７】
ＦＦＴ系のアルゴリズムを用いて積ｙ＝Ａｘを効率的に計算するために、以下に示されるように、Ａを、２ｎ×２ｎ循環行列
【数４】
0006928208.tif 000083
（以下、文章中で「Ａ＾」と記す）に埋め込むことが可能である：
【数Ｃ０２】
0006928208.tif 000084
【０１３８】
ベクトルｘは、最後にｎ個のゼロで埋められ、結果として、長さ２ｎのベクトル
【数５】
0006928208.tif 000085
（以下、文章中において「ｘ＾」と記す）になる：
【数Ｃ０３】
0006928208.tif 000086
【０１３９】
Ａ＾とｘ＾との積は、Ｏ（ｎｌｏｇ（ｎ））でＦＦＴ系のアルゴリズムを用いて計算されることができる。つまり、そのゴールは、長さ２ｎのベクトル
【数６】
0006928208.tif 000087
（以下、文章中で「ｙ＾」と記す）を計算することであり、そのベクトウは、Ａ＾ｘ＾に等しい。より正式には、
【数Ｃ０４】
0006928208.tif 000088
である。
【０１４０】
ｙ＾の最初のｎ個の要素は、ｙの対応する要素に等しく、つまり、各ｋ∈｛０、１、２、．．．、ｎ−１｝に対してｙｋ＝ｙ＾ｋである。
【０１４１】
ＦＦＴ及びＩＦＦＴを用いて（２ｎ）×（２ｎ）循環行列Ｂに長さ２ｎのベクトルｖを乗算する方法を示すことだけが残っている。行列Ｂは、最初の列ベクトルｂによって生成される。
より正式には、
【数Ｃ０５】
0006928208.tif 000089
と置く。
【０１４２】
この積は、ＤＦＴ及び逆ＤＦＴを用いて計算されることができ、これは、循環畳み込み定理から得られる。換言すれば、積の各要素（Ｂｖ）ｋは、ｂ及びｖの循環畳み込みにおけるｋ番目の要素に等しい。つまり、
【数Ｃ０６】
0006928208.tif 000090
ここで、×は要素ごとの乗算を表す。従って、
【数Ｃ０７】
0006928208.tif 000091
である。
【０１４３】
ＤＦＴ及び逆ＤＦＴは、ＦＦＴ及び逆ＦＦＴを用いて計算されることができ、つまり、
【数Ｃ０８】
0006928208.tif 000092
【０１４４】
要約すると、ｎ×ｎテプリッツ行列とベクトルとの積、ここでｎは２のべき乗であると仮定され、該積は、以下の６つのステップを用いて計算されることができる：１）最初の列、単一のゼロ、及び最初の行の最後のｎ−１要素の反転を連結することによって、テプリッツから循環に進む；２）末尾にｎ個のゼロでベクトルを埋める；３）循環行列の最初の列のＤＦＴを計算する；４）埋め込まれたベクトルのＤＦＴを計算する；５）２つのＤＦＴを要素毎に乗算する；６）要素毎の積の逆ＤＦＴを計算する；及び、７）逆ＤＦＴによって計算された結果ベクトルの最初のｎ個の要素を返す。ＤＦＴを計算するためにＦＦＴアルゴリズムを使用すると共に、逆ＤＦＴを計算するためにＩＦＦＴアルゴリズムを使用する。ステップ１）において、テプリッツ行列及び循環行列のいずれも明示的に計算されないことに着目すべきである。代わりに、生成ベクトルのみが、必要な計算を実行するために使用される。
【０１４５】
アルゴリズムＣ．１は、上記のアルゴリズムのための擬似コードを提供する。このアルゴリズムの計算複雑性は、Ｏ（ｎｌｏｇ（ｎ））である。関数の名前は、ＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹＥであり、ここで「Ｅ」は「埋め込み（ｅｍｂｅｄｄｉｎｇ）」の略である。
【０１４６】
アルゴリズムにＦＦＴ計算を含める代わりに、ＦＣＩＲＣＵＬＡＮＴＭＵＬＴＩＰＬＹ（以下のアルゴリズムＤ．２を参照する）を使用することが可能である。しかしながら、ＦＣＩＲＣＵＬＡＮＴＭＵＬＴＩＰＬＹは、ＦＦＴ計算のシーケンスより多くの作業Ｏ（ｎ）を行い、なぜならｋ∈｛０、１、…、ｎ−１毎に（ｆ）１／ｎ及び（ｆｋ）１／ｎを計算しなければならないからである。
【表Ｃ１】
0006928208.tif 000093
【０１４７】
付録Ｄ：Ｐｕｓｔｙｌｎｉｋｏｖ分解を用いたテプリッツとベクトルとの積
【０１４８】
テプリッツ行列にベクトルを乗算するためのアルゴリズムは、Ｐｕｓｔｙｌｎｉｋｏｖ分解を用いて定式化されることができる。このアルゴリズムは、付録Ｃにおいて説明されるように、テプリッツ行列を循環行列に埋め込まない。代わりに、この付録は、ＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹの異なるバージョンを説明する。
【０１４９】
このアルゴリズムを例証する一例が以下に示される。仮にＡが４×４のテプリッツ行列であるとし、これは最初の行ｒ及び最初の列ｃによって生成される。
【数Ｄ０１】
0006928208.tif 000094
【０１５０】
次に、Ａは、以下のように２つの行列の総和に分解されることができる。
【数Ｄ０２】
0006928208.tif 000095
ここで、Ａ´は、循環行列であり、Ａ´´は、ｆ＝−１を持つｆ循環行列（つまり、スキュー循環行列）である。この例の場合では、これら２つの行列は、以下の形式を有する：
【数Ｄ０３】
0006928208.tif 000096
【０１５１】
Ａ´及びＡ´´の値を計算するための式は、以下に提供される。仮にａ´＝（ａ´０、ａ´１、ａ´２、．．．、ａ´ｎ−１）がＡ´の第１列であるとし、つまり、
【数Ｄ０４】
0006928208.tif 000097
【０１５２】
同様に、仮にａ´´＝（ａ´´０、ａ´´１、ａ´´２、．．．、ａ´´ｎ−１）がＡ´´の第１列であるとする。つまり、
【数Ｄ０５】
0006928208.tif 000098
【０１５３】
次に、ａ´及びａ´´の要素は、以下の式を用いて計算されることができる。
【数Ｄ０６】
0006928208.tif 000099
【数Ｄ０７】
0006928208.tif 000100
ここで、ｒはＡの最初の行であり、ｃはそれの最初の列である。
【０１５４】
アルゴリズムＤ．１は、上記のアルゴリズムのための擬似コードを与える。関数の名前は、ＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹＰであり、ここで「Ｐ」は「Ｐｕｓｔｙｌｎｉｋｏｖ」の略である。行２７及び行２８は、アルゴリズムＤ．２を呼び出しており、これは以下で説明される。アルゴリズムは、Ｏ（ｎｌｏｇ（ｎ））時間で動作する。
【表Ｄ１】
0006928208.tif 000101
【０１５５】
アルゴリズムＤ．２は、関数ｆｃｉｒｃｕｌａｎｔｍｕｌｔｉｐｌｙのための（ｆ−循環行列にベクトルを乗算するための）擬似コードを与えており、これはアルゴリズムＤ．ｌで使用された。
それは、Ｏ（ｎｌｏｇ（ｎ））で動作する。
【表Ｄ２】
0006928208.tif 000102
【０１５６】
付録Ｅ：ＦＦＴ系の畳み込みを用いるテプリッツとベクトルとの積
【０１５７】
アルゴリズムＥ．１は、テプリッツ行列にベクトルを乗算するためのさらに別のアルゴリズムのための擬似コードを示す。このケースにおける関数名は、ＴＯＥＰＬＩＴＺＭＵＬＴＩＰＬＹＣであり、ここで「Ｃ」は畳み込みを略記する。該アルゴリズムのための計算複雑性は、Ｏ（ｎｌｏｇ（ｎ））である。このアルゴリズムは、循環埋め込みの形式として解釈されることができ、付録Ｃにおいて説明されたアプローチに類似している。
【表Ｅ１】
0006928208.tif 000103
【０１５８】
アルゴリズムＥ．２は、ＦＦＴ系の畳み込みアルゴリズムのための擬似コードを与えており、これは、離散畳み込みを計算するためのＯ（ｎｌｏｇ（ｎ））方法である。それは、アルゴリズムＥ．１において使用された。
【表Ｅ２】
0006928208.tif 000104
【０１５９】
（一側面）
式ＡイタリックＷイタリック−ｋの対数らせん輪郭線を対象に含めるために計算システムの範囲を拡張する方法では、ＡイタリックＷイタリックは、非ゼロの複素数であり、ｋ＝０、１、…、Ｍ−１である。計算システムは、１又は複数の過程において、高速フーリエ変換（ＦＦＴ）又は逆ＦＦＴ（ＩＦＦＴ）の少なくとも１つを用い、該方法は、少なくとも１つの過程において、ＩＦＦＴ又はＦＦＴに替えて逆チャープＺ変換（ＩＣＺＴ）を利用するステップを備えることができる。
該方法では、ＩＣＺＴは、Ｍ×Ｎの次元を有するヴァンデルモンド行列の観点で表されることができ、前記計算システム上において前記ＩＣＺＴを用いることの計算複雑性は、Ｏ（ｎ２）に等しい又は未満であり、ここでｎ＝ｍａｘ（Ｍ、Ｎ）である。
本明細書において引用される刊行物、特許出願、及び特許を含むすべての参考文献は、各参考文献が個別に及び具体的に示されて参照により組み込まれると共にその全体として本明細書に明記されるかのごとく同程度に、参照により組み込まれる。
【０１６０】
用語「ａ」及び「ａｎ」及び「ｔｈｅ」並びに類似の指示対象の使用は、本願を説明する文脈において（特に、以下の特許請求の範囲において）、本明細書における特段の指示又は文脈による明らかな矛盾のない限り、単数物及び複数物の両方を対象として含む。用語「備える（ｃｏｍｐｒｉｓｉｎｇ）」、「有する（ｈａｖｉｎｇ）」、「含む（ｉｎｃｌｕｄｉｎｇ）」、「含む（ｃｏｎｔａｉｎｉｎｇ）」は、特に断りのない限り、非限定の用語（つまり、「含み、しかしこれに限定されない」という意味）と解釈されるべきである。本明細書における値の範囲の列挙は、本明細書で特に明記しない限り、範囲内に入る各個別の値を個別に参照する短縮記法として機能することを意図しているだけであり、また個別の値の各々は、本明細書に個別に記載されているかのように明細書に組み込まれる。本明細書に記載されたすべての方法は、本明細書における特段の指示又は文脈による明らかな矛盾のない限り、任意の適切な順序で実行されることができる。本明細書で提供された任意のまた全ての例、又は例示的な言葉（例えば「といった」）の使用は、単に本願をより良く説明するために意図され、また特に請求されない限り、本願の範囲に関する限定を課するものではない。クレームされていない要素を本願の実現に不可欠であるとして示すとして解釈すべき明細書中における言葉はない。
【０１６１】
好ましい実施形態が本明細書に記載されており、本願を実施するために発明者に知られている最良の形態を含む。それらの好ましい実施例の変形が、前述の説明を読むことに際して、当業者に明らかになり得る。本発明者らは、当業者がそのような変形を適切に使用することを期待し、また本発明者は、本明細書に具体的に説明されたもの以外で実行されるべき発明を提供するように意図する。これに従って、本願は、適用される法律で許可されるものとして、本明細書に添付された特許請求の範囲に列挙された主題のすべての修正及び等価物を含む。さらに、そのすべての可能な変形における上述の要素の任意の組み合わせは、本明細書における特段の明記又は文脈による明らかに矛盾のない限り、本願によって包含される。
【符号の説明】
【０１６２】
ＩＣＺＴ  逆チャープＺ変換
ＣＺＴ  チャープｚ変換
【図１Ａ】
0006928208.tif 000166
【図１Ｂ】
0006928208.tif 000167
【図２】
0006928208.tif 000168
【図３】
0006928208.tif 000169
【図４Ａ】
0006928208.tif 000170
【図４Ｂ】
0006928208.tif 000171
【図５Ａ】
0006928208.tif 000172
【図５Ｂ】
0006928208.tif 000173
【図５Ｃ】
0006928208.tif 000174
【図５Ｄ】
0006928208.tif 000175
【図６Ａ】
0006928208.tif 000176
【図６Ｂ】
0006928208.tif 000177
【図６Ｃ】
0006928208.tif 000178
【図７Ａ】
0006928208.tif 000179
【図７Ｂ】
0006928208.tif 000180