【手続補正書】
【提出日】平成17年9月30日(2005.9.30)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】０３４４
【補正方法】変更
【補正の内容】
【０３４４】
最後に、適切な展望を持つために、次のインプリメンテーションは、それらが本発明の多くの可能な効率的なインプリメンテーションの内のわずかな例であることを理解して読まれるべきである。
例１：０−１−２進の行列
次のステップのシーケンスは、本発明の０−１−行列の局面からみたインプリメンテーションについて記述する。データは、ｒ×ｎの０−１−行列  Ａ＝（ａij：０≦ｉ＜ｒ，０≦ｊ＜ｎ）、および実数または複素数入力ベクトルｘ＝（ｘ0，..........，ｘn-1）から成る。行列Ａの列は、ｖ0，..........，ｖn-1によって表示される。このステップのシーケンスは、積ｙ＝（ｙ0，..........，ｙr-1）Ｔ＝Ａ・ｘを計算する。すべての与えられたｋ−反復で、各場所は、ベクトルｘに依存して、１つの実数または複素数を含んでいる。割り付けられた読取りおよび書込みメモリは、各反復でプロセスに関係する列を表わして、１から２ｒ−１までラベル付けされた２ｒ−１のアドレスを含む。次の定義は、本発明の好適な実施例の記述の一部である。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０３４５
【補正方法】変更
【補正の内容】
【０３４５】
定義
１）全てのk≧0,
j≧1に対して、
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０３４７
【補正方法】変更
【補正の内容】
【０３４７】
を定義する。
２）全ての０≦ｍ＜ｒに対して、Ｙm＝２mを定義する。これらのアドレスは、Ｙ0がｙ0のアドレスであり、Ｙ1がｙ1のアドレスとなる場合のように、プロセスの終わりに、出力ベクトルｙ＝（ｙ0，..........，ｙr-1）Tのコンポーネントを含むであろう。
３）ｋ≧０およびｊ≧１に対して、以下のように各場所から次の場所へのデータの移動を制御する関数Ｆkj，Ｇkjを定義する。まず、ｌ＝ｌ（ｋ，ｊ），ｍ＝ｌ（ｋ＋ｌ，２ｊ），ｈ＝ｌ（ｋ，ｊ＋１）−１を置き、各整数ｖ≧０に対して、
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０３５２
【補正方法】変更
【補正の内容】
【０３５２】
そのとき、（ソース）アドレスｖ中に存在する値を（宛先）アドレスＧkj（ｖ）中の値へ加え、さらに、（ソース・アドレスｖの）この値を（宛先）アドレスＦkj（ｖ）中の値に加える。
４．出力の獲得：
このステージでは、すべてのアドレスＹ1は、すべての０≦ｉ＜ｒに対して、出力コンポーネントｙiの値を含む。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０３５５
【補正方法】変更
【補正の内容】
【０３５５】
Ｃ0,1r  ≡２r+1−２ｒ−２
この数はｒにのみ依存する。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０３５７
【補正方法】変更
【補正の内容】
【０３５７】
Ｃ0,1n,r  ≡ｎ＋Ｃ0,1r
チャート１：０−１−２進・行列
図１は、上記コードの主要部分を実行する装置によって使用されたメモリの内容を更新する動作を概略的に示すが、０−１−２進・行列は４つの行からなり、本発明の０−１−２進の特徴を好ましい手法でインプリメントする。各反復における各行列の列は、メモリ中のアドレスによって２進形式で表わされる。ボトム（０または１）コンポーネント（水平表示での最も右手のコンポーネント）はＭＳＢであり、また、トップ（０または１）コンポーネント（水平表示における最も左手のコンポーネント）はＬＳＢである。アドレスＹm＝２m，０・ｍ・３は、Ｙ0がｙ0のアドレスであり、Ｙ1がｙ1のアドレスになる場合のように、そのプロセスの終わりに出力ベクトルｙ＝（ｙ0，..........，ｙr-1）Tのコンポーネントを含む。矢印は、単一アドレスの内容をとり、別のアドレスの内容に加えられるためにそれを送る行為を示す。上記のコードによって示されるように、これは、反復の順序、および各反復に関係するアドレスの（増加）順序に従って行われる。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０３５８
【補正方法】変更
【補正の内容】
【０３５８】
例２：Ｕ行列
次のステップのシーケンスは、本発明のＵ行列の面からのインプリメンテーションについて記述する。そのデータは、ｒ×ｎＵ行列Ａ＝（ａij：０≦ｉ＜ｒ，０≦ｊ＜ｎ）および入力の実数ベクトルｘ＝（ｘ0，..........，ｘn-1）から成る。行列Ａの列は、ｗ，..........，ｗn-1によって表示されるであろう。このステップのシーケンスは、積ｙ＝（ｙ0，..........，ｙr-1）T＝Ａ・ｘを計算する。すべての与えられた反復では、各場所はベクトルｘに依存して、１つの実数または複素数を含む。割り当てられた読取りおよび書込みメモリは、０から２r-1＋ｒ−２までラベル付けされた２r-1＋ｒ−１個のアドレスを含む。次の定義および前例の定義は、本発明の好適な実施例の記述に必要である。
定義
１）各ｒ次元のＵベクトルに対し、ｕ＝（ｕ0，..........，ｕr-1）は：
Ｓｉｇｎ（ｕ）＝ｕr-1
ｈ（ｕ）＝（ｕ0・ｕr-1，..........，ｕr-1・ｕr-1）
を定義する。
２）バイポーラ２進セット、Ｕ＝｛１，−１｝およびロジック・ビットの２進セット、Ｂ＝（０，１）の間の一致を次式によって定義する。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】０３５９
【補正方法】変更
【補正の内容】
【０３５９】
（−１）’＝１
１’＝０
従って、ｒ次元のＵベクトルに対して、ｕ＝（ｕ0，..........，ｕr-1）は、
π（ｕ）＝Σ0≦j<r２jｕ’j
を定義する。
３）Ｙ0＝０、およびすべての１≦ｍ≦ｒ−ｌに対してＹm＝２r-1＋ｍ−１を定義する。これらのアドレスは、Ｙ0がアドレスであり、Ｙ1がｙ1のアドレスとなる場合のように、プロセスの終わりに出力ベクトルｙ＝（ｙ0，..........，ｙr-1）Tのコンポーネントを含むであろう。
４）すべてのｋ≧０およびｊ≧１に対し、マップＦkj、Ｇkj、Ｓｉｇｎkjは、以下のように定義される。
ｌ＝ｌ（ｋ，ｊ），ｍ＝ｌ（ｋ＋１，２ｊ）、ｈ＝ｌ（ｋ，ｊ＋１）−１とする。あらゆる整数ｖ≧０に対し、
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】０３６４
【補正方法】変更
【補正の内容】
【０３６４】
１）（ソース）アドレスｙl(kj)に存在する値を（宛先）アドレスＹl(k+1,2j)中の値へ加える。
２）for p going from 1
to 2l(kj+1)-l(kj)-1 -1 do
put u=2l(kj)・p
and for source address u do:
if Ｇkj（ｕ）＝ｕ
then
ソース・アドレスｕに存在する値を終点アドレスＹl(k+1,2j)中の値へ加える。
もし、Ｆkj（ｕ）＝ｕの場合、そのとき
（ソース）アドレスｕに存在する値を（宛先）アドレスＹl(kj)中の値へ加える。
もし、Ｇkj（ｕ）＝０の場合、そのとき
（−１）で乗じられた（ソース）アドレスｕに存在する値を（宛先）アドレスＹl(kj)中の値に加えて、また（アドレスｕの）この値をアドレスＦkj（ｕ）中の値にさらに加える。
ほかに、Ｓｉｇｎkj（ｕ）を掛けたソース・アドレスｕに存在する値を終点アドレスＧkj（ｕ）中の値に加えて、また（アドレスｕの）この値をアドレスＦkj（ｕ）中の値にさらに加える。
４．出力の獲得：
あらゆるアドレスＹiは、すべての０≦ｉ＜ｒに対して、ｙiの値を含む。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】０３６６
【補正方法】変更
【補正の内容】
【０３６６】
【数９５】
2005302033.tif 000001
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】０３６８
【補正方法】変更
【補正の内容】
【０３６８】
【数９６】
2005302033.tif 000002
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】０３７０
【補正方法】変更
【補正の内容】
【０３７０】
【数９７】
2005302033.tif 000003
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】０３７３
【補正方法】変更
【補正の内容】
【０３７３】
【数９８】
2005302033.tif 000004
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】０３７５
【補正方法】変更
【補正の内容】
【０３７５】
【数９９】
2005302033.tif 000005
【手続補正１５】
【補正対象書類名】明細書
【補正対象項目名】０３７７
【補正方法】変更
【補正の内容】
【０３７７】
例３：Ｕ1行列
ステップの次のシーケンスは、変換行列のエントリがセットＵ1≡｛１，−１，ｊ，−ｊ｝に属するときに、ＧＥＭ方法のインプリメンテーションについて記述する。これは、アプリケーションにしばしば現われるＧＥＭのサブケースの１つである。データは、ｒ×ｎのＵ1行列Ａ＝（ａij：０≦ｉ＜ｒ，０≦ｊ＜ｎ）および入力複素ベクトルｘ＝（ｘ0，..........，ｘn-1）から成る。行列の列は、ｗ0，..........，ｗn-1によって表示される。このステップのシーケンスは積ｙ＝（ｙ0，..........，ｙr-1）T＝Ａ・ｘを計算する。あらゆる与えられた反復で、各場所はベクトルｘに依存して、１つの実数または複素数を含む。割り付けられた読取りおよび書込みメモリは、０から４r-1＋ｒ−２までラベル付けされた４r-1＋ｒ−１個のアドレスを含む。この例は、次の定義と同様に、前例においてセットされた定義を使用する。
【手続補正１６】
【補正対象書類名】明細書
【補正対象項目名】０３８１
【補正方法】変更
【補正の内容】
【０３８１】
Ｓｉｇｎ（ｕ）＝ｕr-1
ｇ（ｕ）＝（ｕ0・（ｕr-1）-1，..........，ｕr-1・（ｕr-1）-1）
３）Ｙ0＝０およびすべての１≦ｍ＜ｒに対し、Ｙm＝４r-1＋ｍ−１を定義する。これらは出力ベクトルのコンポーネントのアドレスになるであろう。
４）すべてのｋ≧０、ｊ≧１に対し、マップＦkj、Ｇkjが次のように定義される。
【手続補正１７】
【補正対象書類名】明細書
【補正対象項目名】０３８６
【補正方法】変更
【補正の内容】
【０３８６】
１）アドレスＹl(k,j)に存在する値をアドレスＹl(k+1,2j)中の値に加える。
２）for p going from 1
to 4l(kj+1)-l(kj)-1 -1 do
put u=4l(kj)・p
and for source address u do:すなわち
Ｇkj（ｕ）＝ｕの場合
（ソース）アドレスｕに存在する値を（宛先）アドレスＹl(k+1,2j)中の値へ加える。
ほかに、Ｆkj（ｕ）＝ｕの場合、（ソース）アドレスｕに存在する値を（宛先）アドレスＹl(k,j)中の値へ加える。
ほかに、Ｇkj（ｕ）＝０の場合、Ｓｉｇｎkj（ｕ）を掛けた（ソース）アドレスｕに存在する値を（宛先）アドレスＹl(k,j)中の値に加えて、さらにこの値（アドレスｕの）をアドレスＦkj（ｕ）中の値に加える。
ほかに、Ｓｉｇｎkj（ｕ）を掛けた（ソース）アドレスｕに存在する値を（宛先）アドレスＧkj（ｕ）中の値に加えて、この値（アドレスｕの）をアドレスＦkj（ｕ）中の値に加える。
４．出力の獲得：
あらゆるアドレスＹiは、すべての０≦ｉ＜ｒに対して、ｙiの値を含む。
【手続補正１８】
【補正対象書類名】明細書
【補正対象項目名】０３８８
【補正方法】変更
【補正の内容】
【０３８８】
【数１０２】
2005302033.tif 000006
【手続補正１９】
【補正対象書類名】明細書
【補正対象項目名】０３９０
【補正方法】変更
【補正の内容】
【０３９０】
【数１０３】
2005302033.tif 000007
【手続補正２０】
【補正対象書類名】明細書
【補正対象項目名】０３９２
【補正方法】変更
【補正の内容】
【０３９２】
【数１０４】
2005302033.tif 000008
【手続補正２１】
【補正対象書類名】明細書
【補正対象項目名】０３９５
【補正方法】変更
【補正の内容】
【０３９５】
【数１０５】
2005302033.tif 000009
【手続補正２２】
【補正対象書類名】明細書
【補正対象項目名】０３９７
【補正方法】変更
【補正の内容】
【０３９７】
【数１０６】
2005302033.tif 000010
【手続補正２３】
【補正対象書類名】明細書
【補正対象項目名】０３９８
【補正方法】変更
【補正の内容】
【０３９８】
例４：トップリッツ  Ｕ行列
ステップの次のシーケンスは、Ｕ係数を備えた本発明のトップリッツ行列の面からインプリメンテーションについて記述する。データは、Ｕシーケンスｔ0，..........，ｔn-1、および入力実数または複素ベクトルｘ＝（ｘ0，..........，ｘn+r-2）から成る。Ｕシーケンスから、ｒ×（ｎ＋ｒ−１）のトップリッツ行列Ａ≡（ａij≡ｔi-j：０≦ｉ＜ｒ，０≦ｊ≦ｎ＋ｒ−２）が形成され、ここで、すべてのｋ＜０、または、ｋ≧ｎに対して、ｔk≡０である。これらのステップは、積ｙ＝（ｙ0，..........，ｙn-1）＝Ａ・ｘを計算する。最初のステージのみがＵ行列例のステージと異なり、したがって、このステージだけを紹介することが必要である。前例のインプリメンテーションでリストされた定義は、すべてここに適用可能である。
【手続補正２４】
【補正対象書類名】明細書
【補正対象項目名】０４０１
【補正方法】変更
【補正の内容】
【０４０１】
ＣTn,r  ≡ｎ＋３ｒ−３＋Ｃur
チャート３：トップリッツ行列
図３は、到来データを装置に使用される適切なメモリ位置へ送る動作を概略的に示すが、その装置は４つの行からなるトップリッツ行列を有して、上記コードの初期部分を実行する。この最初の部分を除いて、他のあらゆる面は、Ｕ行列インプリメンテーションおよび装置の面と同一であり、その記述がここにあてはまる。ここでまた、１つの矢印は符号が１であることを示し、そして２つの矢印は符号が−１であることを示す。
【手続補正２５】
【補正対象書類名】明細書
【補正対象項目名】０４０２
【補正方法】変更
【補正の内容】
【０４０２】
例５：トップリッツ  Ｕ1行列
本発明の次の好適な実施例は、Ｕ1係数を備えた本発明のトップリッツ行列の面からのインプリメンテーションである。データは、Ｕ1シーケンスｔ0，..........，ｔn-1、および入力複素ベクトルｘ＝（ｘ0，..........，ｘn+r-2）から成る。Ｕ1シーケンスから、ｒ×（ｎ＋ｒ−１）のトップリッツ行列Ａ≡（ａij≡ｔi-j：０≦ｉ＜ｒ，０≦ｊ≦ｎ＋ｒ−２）が形成され、ここで、すべてのｋ＜０、または、ｋ≧ｎに対して、ｔk≡０である。以下にリストされたステップのシーケンスは、積ｙ＝（ｙ0，..........，ｙn-1）＝Ａ・ｘを計算する。最初のステージのみがＵ1行列例のステージと異なり、したがって、このステージだけを紹介することが必要である。前例でリストされたすべての定義は、ここに適用可能である。
【手続補正２６】
【補正対象書類名】明細書
【補正対象項目名】０４０５
【補正方法】変更
【補正の内容】
【０４０５】
ＣT1n,r  ≡ｎ＋３ｒ−３＋ＣU1r
例６：実数の行列、２進０−１の表現
本発明の次の好適な実施例は、行列エントリの２進０−１表現を備えた本発明の実数行列の面からみたインプリメンテーションである。データは、負でないエントリを備えたｒ×ｎ実数行列Ａ＝（ａij：０≦ｉ＜ｒ，０≦ｊ＜ｎ）、および入力の実数または複素ベクトルｘ＝（ｘ0，..........，ｘn-1）から成る。アルゴリズムはｙ＝（ｙ0，..........，ｙn-1）＝Ａ・ｘを計算する。
【手続補正２７】
【補正対象書類名】明細書
【補正対象項目名】０４０６
【補正方法】変更
【補正の内容】
【０４０６】
行列のエントリが、すべての０≦ｉ＜ｒ，０≦ｊ＜ｎに対して、次の０−１の２進の表現で与えられると仮定される。
【手続補正２８】
【補正対象書類名】明細書
【補正対象項目名】０４０７
【補正方法】変更
【補正の内容】
【０４０７】
ａij＝Σ-m2≦k≦m1ｔijk・２k
ここで、すべての−ｍ2≦ｋ≦ｍ1に対しｔijk∈｛０，１｝
第１段階だけが、０−１−行列のインプリメンテーションのステージと異なっており、このステージについてだけ記述される必要がある。０−１−行列のインプリメンテーションのセクションにリストされた定義はすべて、ここで適用可能である。さらに次のｒ次元の｛０，１｝ベクトルをすべての０≦ｊ＜ｍ、−ｍ2≦ｋ≦ｍ1に対して定義する。
【手続補正２９】
【補正対象書類名】明細書
【補正対象項目名】０４１０
【補正方法】変更
【補正の内容】
【０４１０】
ＣRe-0-1≡（ｍ１＋ｍ2＋１）・ｎ＋Ｃ0,1r
例７：実数の行列、２進のＵ表現
本発明の次の好適な実施例は、行列エントリの２進Ｕ表現を備えた本発明の実数行列の面からみたインプリメンテーションである。データは、ｒ×ｎ実数行列Ａ＝（ａij：０≦ｉ＜ｒ，０≦ｊ＜ｎ）、および入力の実数または複素ベクトルｘ＝（ｘ0，..........，ｘn-1）から成る。そのアルゴリズムはｙ＝（ｙ0，..........，ｙn-1）＝Ａ・ｘを計算する。
【手続補正３０】
【補正対象書類名】明細書
【補正対象項目名】０４１１
【補正方法】変更
【補正の内容】
【０４１１】
行列のエントリは、すべての０≦ｉ＜ｒ，０≦ｊ＜ｎに対して、次のＵ表現で与えられると仮定される。
【手続補正３１】
【補正対象書類名】明細書
【補正対象項目名】０４１２
【補正方法】変更
【補正の内容】
【０４１２】
ａij＝Σ-m2-1≦k≦m1-1ｔijk・２k＋ｔijm1・（２m1−２-m2-1）
ここで、すべての−ｍ2−１≦ｋ≦ｍ1に対して、ｔijk∈Ｕ
この表現の存在は、本発明の実数行列の面から既に言及されている。第１段階だけが、Ｕ行列のインプリメンテーションのステージと異なっており、このステージについてだけ記述される必要がある。Ｕ行列のインプリメンテーションのセクションにリストされた定義はすべて、ここで適用可能である。さらに次のｒ次元のＵベクトルをすべての０≦ｊ＜ｎ、−ｍ2≦ｋ≦ｍ1に対して定義する。
【手続補正３２】
【補正対象書類名】明細書
【補正対象項目名】０４１５
【補正方法】変更
【補正の内容】
【０４１５】
ＣRe-Ur≡（ｍ1＋ｍ2＋１）・ｎ＋Ｃur
図４は、本発明の好適な実施例に従って、加算の回数を削減した線形変換を行なう典型的な装置のブロック図である。装置５００は、２つの入力および１つの出力を備えた乗算器１０、入力のうちの１つを選択しその出力に転送するためのマルチプレクサ（ＭＵＸ）９、２つの入力および１つの出力を備える加算器１１、その後ろに続く２つのアドレス・バス・ライン「ａｄｄ＿ａ」および「ａｄｄ＿ｂ」および２つの出力、「ｄａｔａ＿ａ」および「ｄａｔａ＿ｂ」を有するデュアル・ポート・ランダム・アクセス・メモリ（ＤＰＲＡＭ）１３を含む。ＭＵＸの動作は、アドレス・ジェネレータ５０１によって制御され、それは、さらにＤＰＲＡＭ１３中のメモリ・アドレスへのアクセスを可能にする。アドレス・ジェネレータの動作は、カウンタ３によって制御される。