(57)【要約】      （修正有）【課題】新規標本化点の決定方法を提供する。【解決手段】Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得工程と、前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値取得決定工程と、前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程とを含む離散フーリエ変換に用いられる標本化点の決定方法。【選択図】図１
2004171253.tif 000002
【特許請求の範囲】
【請求項１】
Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得工程と、
前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、
前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値取得決定工程と、
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程と、
を含む離散フーリエ変換に用いられる標本化点の決定方法。
【請求項２】
前記２次元仮想周波数空間値取得決定工程において、
前記２次元仮想時間空間におけるｍ×ｎ個の格子点上の値（ｔ１，ｔ２）に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値（ｐ，ｑ）は、ハーモニックバランス法における非線形部分の電圧に関する下記式（Ｉ）によって対応づけられることを特徴とする請求項１に記載の標本化点の決定方法。
【式１】
2004171253.tif 000012
（ＶＮＬＲ（ｔ）は、時間ｔにおける電圧を表し、Ｘｐ，ｑＮＬＲは、ｐ、ｑの周波数成分の強度を表し、ｊは、虚数単位を表し、Ｎ２は、ｐ、ｑの最大周波数を表し、ω１、ω２は角周波数を表す。）
【請求項３】
前記１次元仮想周波数空間値決定工程における、ｒ軸からなる１次元仮想周波数空間での値は、下記式（ＩＩ）によって対応づけられることを特徴とする請求項１、又は請求項２に記載の標本点の決定方法。
【式２】
2004171253.tif 000013
（ここで、ｔ３は１次元仮想時間空間における１次元ループの経路（Ｔ３軸）上の座標値を表し、Ｎ３は１次元ループの経路（Ｔ３軸）上でＶＮＬＲを表現したときの最大周波数を表し、ｍ、ｎはそれぞれｔ１軸およびｔ２軸の分割値を表し、ｊは虚数単位を表す。）
【請求項４】
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値に変換する変換工程は、
下記式（ＩＩＩ）を用いて変換されることを特徴とする請求項１または２に記載の標本化点の決定方法。
【式３】
ｐｎ＋ｑｍ＝ｒ        （ＩＩＩ）
（式（ＩＩ）中、ｍ、ｎはそれぞれ、２次元仮想時間空間におけるＴ１軸およびＴ２軸方向の分割値を表し、ｐ、ｑは、２次元仮想周波数空間での座標値（ｐ，ｑ）を表す。）
【請求項５】
前記最高周波数算出工程は、２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除く請求項１〜４のいずれか１項に記載の標本化点の決定方法。
【請求項６】
離散フーリエ変換の代わりに離散コサイン変換に用いられる請求項１〜請求項５のいずれか１項に記載の標本化点の決定方法。
【請求項７】
離散フーリエ変換の代わりに離散サイン変換に用いられる請求項１〜請求項５のいずれか１項に記載の標本化点の決定方法。
【請求項８】
請求項１〜請求項７のいずれか１項に記載の標本化点の決定方法を用いた音情報の標本化方法。
【請求項９】
請求項１〜請求項７のいずれか１項に記載の標本化点の決定方法を用いた画像情報の標本化方法。
【請求項１０】
請求項１〜請求項７のいずれか１項に記載の標本化点の決定方法を用いた離散フーリエ変換方法。
【請求項１１】
コンピュータに、
Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得工程と、
前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、
前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値取得決定工程と、
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程と、
からなる離散フーリエ変換に用いられる標本化点の決定方法を実行させるためのプログラム。
【請求項１２】
コンピュータを、
自然数ｍとｎを入力する入力手段と、
Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得手段と、
前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定手段と、
前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値取得決定手段と、
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換手段と、
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出手段と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出手段により算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定手段として機能させ、
離散フーリエ変換に用いられる標本化点を決定するためのプログラム。
【請求項１３】
請求項１２に記載のプログラムを記録した記録媒体。
【請求項１４】
コンピュータに
Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得工程と、
前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、
前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値取得決定工程と、
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程と、
を含む離散フーリエ変換に用いられる標本化点の決定方法を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１５】
自然数ｍとｎを入力する入力手段と、
Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得手段と、
前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定手段と、
前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値決定手段と、
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換手段と、
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出手段と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出手段により算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を離散フーリエ変換に用いられる標本化点とする標本化点決定手段と、
を含むコンピュータ。
【請求項１６】
Ｔ１軸、Ｔ２軸及びＴ３軸からなる３次元仮想時間空間において、それぞれの軸をｍ個、ｎ個及びｌ個に分割し、ｍ×ｎ×ｌ個の格子点を得る格子点取得工程と、
前記３次元仮想時間空間におけるｍ×ｎ×ｌ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、
前記３次元仮想時間空間における各格子点上の値に対する、３次元仮想周波数空間での値を取得するか決定する３次元仮想周波数空間値取得決定工程と、
前記３次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、
前記３次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程と、
を含む離散フーリエ変換に用いられる標本化点の決定方法。
【請求項１７】
Ｎ個の軸からなるＮ次元仮想空間において、それぞれの軸を分割し複数の格子点を得る格子点取得工程と、
前記Ｎ次元仮想時間空間における全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、
前記Ｎ次元仮想時間空間における各格子点上の値に対する、Ｎ次元仮想周波数空間での値を取得するか決定するＮ次元仮想周波数空間値取得決定工程と、
前記Ｎ次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、
前記Ｎ次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程と、
を含む離散フーリエ変換に用いられる標本化点の決定方法。
【請求項１８】
請求項１６又は請求項１７に記載の標本化点の決定方法を用いた離散フーリエ変換方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、標本化点の決定方法などに関する。より詳しくは、離散フーリエ変換などにおける効率的な標本化方法、コンピュータにこのような標本化方法を実行させるためのプログラム、そのようなプログラムを記録した記録媒体、そのような標本化方法を実行可能なコンピュータ、そのような標本化方法を用いた音情報のデジタル化方法、画像情報のデジタル化方法などに関する。
【０００２】
【従来の技術】
自然界にある音や画像情報は、本来はアナログである。ただし、アナログ信号は、様々な周波数と強度を持った正弦波と余弦波の重ね合わせとして表現できる。
そして、フーリエ変換（ＦＴ）を用いると、アナログ信号にどの周波数の正弦波又は余弦波が、どの強度で含まれるかを計算できる。つまり、フーリエ変換を用いれば、アナログ信号を正弦波及び余弦波の情報として表現できるのである。そして、フーリエ変換された情報を、逆フーリエ変換（ＩＦＴ）すれば元のアナログ情報に戻すことができる。
【０００３】
アナログ信号を一度デジタル化した後に様々な処理を加えるデジタル処理が行われている。デジタル処理を行うためには、アナログ信号をデジタル情報に変換する必要がある。情報を、例えば「０」と「１」のようなデジタル符号に変換することを符号化（ｃｏｄｉｎｇ）といい、符号化された情報を元の情報に戻すことを復号化（ｄｅｃｏｄｉｎｇ）という。そして、符号化に用いられる装置を符号器（ｅｎｃｏｄｅｒ）といい、複号化する装置を復号器（ｄｅｃｏｄｅｒ）と呼ぶ。
このような、アナログ信号からデジタル信号への変換をＡ／Ｄ変換という。Ａ／Ｄ変換には、標本化（ｓａｍｐｌｉｎｇ）と、量子化（ｑｕａｎｔｉｚｉｎｇ）の２つのステップが必要となる。
【０００４】
時間軸上で連続した値をもつアナログ波形を、一定の時間間隔など離散的な値で表すことを標本化という。そして、標本化定理より、波は、その周波数の２倍以上の周波数で標本化することができる。すなわち、標本化周波数の２分の１以下の周波数をもつ波のみが標本化できることとなる。標本化点は、通常格子点上に位置する。この場合に、標本化できないもとの高周波成分は、予め取り除いておき、取り除かれた信号を標本化すればよい。すなわち、アナログ信号をフーリエ変換し、高周波成分を取り除いたものを標本化すればよい。このように、必要な周波数成分を取り除く処理を「フィルタ処理」という。
【０００５】
例えば、時間軸上で離散信号となった標本値は、振幅軸の上では連続的な値を取っている。そこで、振幅上でも有限個の離散的な値に変換する。すなわち、標本値の最大値と、最小値の間を一定の量子化幅（ｑｕａｎｔｉｚｉｎｇ  ｓｔｅｐ）で等分したときに、観測している標本値をそれと最も近い離散値に置き換える。この操作を量子化という。
【０００６】
例えば、同じフーリエ変換点数の基数２フーリエ変換パイプラインを複数個有し、入力データを並列に入力する前段部と、前段部から並列に出力される各データに捻り係数を乗算する乗算部と、前段部における基数２フーリエ変換パイプラインの個数に等しいフーリエ変換点数の並列フーリエ変換回路を２つ有し、乗算部から並列に出力されるデータを並列に入力する後段部と、を備えたことを特徴とするフーリエ変換装置が知られている（下記、特許文献１参照）。このように効率的なフーリエ変換の方法を確立することは、情報量を軽減する上でも重要である。
【０００７】
フーリエ変換の利用例としては、ハーモニックバランス法が挙げられる。
ハーモニックバランス法は、非線形電子要素を含む電子回路の振る舞いを解析するために良く用いられる。ハーモニックバランス法によれば、フーリエ変換を用いてそのような電子回路の特徴を評価できる。
【０００８】
ハーモニックバランス法においては、電子回路は、線形部分と非線形部分に分けて扱われる。非線形部分において、時間ｔにおける電流ＩＮＬＲ（ｔ）は、時間ｔにおける電圧をＶＮＬＲ（ｔ）として、以下の式（１）によって表すことができる。
【０００９】
【式】
ＩＮＬＲ（ｔ）＝ｆＮＬＲ（ＶＮＬＲ（ｔ））          ・・・（１）
【００１０】
フーリエ変換は、非線形部分及び線形部分の電圧である、ＶＮＬＲ（ｔ）とＶＬＲ（ｔ）を表すために用いられ、それぞれ下記式（２）で表される。
【００１１】
【式】
2004171253.tif 000003
【００１２】
式（２）において、ＸｐＮＬＲはｐの非線形部分の周波数成分の強度を表し、ＸｐＬＲはｐの線形部分の周波数成分の強度を表し、ω１は角周波数を、Ｎ１は周波数の最大オーダーを表し、ｊは虚数単位を表す。
【００１３】
ＸｐＮＬＲが既知の場合、式（１）及び式（２）によってＩＮＬＲ（ｔ）を求めることができる。そして、下記式（３）に示されるように、ＤＦＴ（離散フーリエ変換）によれば、非線形部分回路おける電流の周波数要素（以下単に要素ともいう。）を計算できる。
【００１４】
【式】
2004171253.tif 000004
【００１５】
線形部分回路の電流の周波数要素であるＹｐＬＲは、その線形関係により電圧要素であるＶｐＬＲを用いて簡単に求めることができる。
【００１６】
周波数マッピング（Ｆｒｅｑｕｅｎｃｙ  Ｍａｐｐｉｎｇ）技術（例えば、非特許文献１、非特許文献２参照。）や、ＡＰＦＴ（Ａｌｍｏｓｔｏ−Ｐｒｅｒｉｏｄｉｃ  Ｆｏｕｒｉｅｒ  Ｔｒａｎｓｆｏｒｍ）（例えば、非特許文献３、非特許文献４参照。）や、２次元ハーモニックバランス（２Ｄ−ＨＢ）（例えば、非特許文献５、非特許文献６参照）など、例えばω１とω２のような二つの周波数要素によって駆動される回路を分析するいくつかの方法が開発されている。
【００１７】
２次元ハーモニックバランス法は、２次元の仮想時間空間（ｔではなくて、ｔ１とｔ２を用いる）における電流と電圧とを扱う。ω１に関する要素は、実時間ｔ１におけるものとして取り扱い、ω２に関する要素は、仮想時間ｔ２におけるものとして取り扱う。この関係は、下記式（４）によって表される。
【００１８】
【式】
2004171253.tif 000005
【００１９】
式（４）中、ＶＮＬＲ（ｔ）は、時間ｔにおける電圧を表し、Ｘｐ，ｑＮＬＲは、ｐ、ｑの周波数成分の強度を表し、ｊは、虚数単位を表し、Ｎ２は、ｐ、ｑの最大周波数を表し、ω１、ω２は角周波数を表す。
式（４）に基づいた計算を終えると、ｔ１とｔ２はｔにされる。ω１とω２の周波数成分は、電圧と電流は、それぞれｔ１時間とｔ２時間で独立してふるまうため、標本点を選択することはたやすい。ＡＰＦＴにおける周波数マッピングにおける符号化を慎重に行うことや、標本点を適切なものに置き換えることは必要とされない。ただし、２Ｄ−ＨＢ法は、現実に要求されるよりも、ＤＦＴする際に多くのデータ点を必要とするという問題がある。
【００２０】
ω１とω２がともにＮ２であり、符号化の時間周期であるｔ１とｔ２が、それぞれＴ１（＝２π／ω１）、Ｔ２（＝２π／ω２）と与えられたとすれば、ナイキストの定理に従って、それぞれの時間空間において必要とされる標本点は（２Ｎ２＋１）個である。その結果、２次元ＤＦＴのためには（２Ｎ２＋１）２点が要求される（例えば、非特許文献５参照。）。
【００２１】
（２Ｎ＋１）２個の周波数の格子点のうちゼロでない大きさのＸｐ，ｑＮＬＲを持つのは（２Ｎ２＋２Ｎ＋１）個のみであり、下記式（５）を満たす（例えば、非特許文献５参照。）。
【００２２】
【式】
2004171253.tif 000006
【００２３】
その結果、２Ｎ２２＋２Ｎ２＋１個の周波数データを得るために（２Ｎ２＋１）２点の時間空間における標本点が用いられ、冗長である。一方で、周波数マッピングとＡＰＦＴ法においては、標本点の数と周波数データの数とが同じ２Ｎ２２＋２Ｎ２＋１個であり、効率的である。
【００２４】
【特許文献１】
特許第３０８８４７２号公報．
【非特許文献１】
Ｄ．  Ｈｅｎｔｅ  ａｎｄ  Ｒ．  Ｈ．  Ｊａｎｓｅｎ，  ’’Ｆｒｅｑｕｅｎｃｙ−ｄｏｍａｉｎ  ｃｏｎｔｉｎｕａｔｉｏｎ  ｍｅｔｈｏｄ  ｆｏｒｔｈｅ  ａｎａｌｙｓｉｓ  ａｎｄ  ｓｔａｂｉｌｉｔｙ  ｉｎｖｅｓｔｉｇａｔｉｏｎ  ｏｆ  ｎｏｎｌｉｎｅａｒ  ｍｉｃｒｏｗａｖｅ  ｃｉｒｃｕｉｔｓ’’，  Ｐｒｏｃ  ＩＥＥ，  ｐａｒｔ  Ｈ，  Ｖｏｌ．  １３３，  ｐｐ．  ３５１−３６２，  １９８６．
【非特許文献２】
Ｋ．  Ｓ．  Ｋｕｎｄｅｒｔ，  Ｊ．  Ｋ．  Ｗｈｉｔｅ  ａｎｄ  Ｓａｎｇｉｏｖａｎｎｉ−Ｖｉｎｃｅｎｔｉｌｌｉ，  ’’Ｓｔｅａｄｙ−ｓｔａｔｅｍｅｔｈｏｄｓ  ｆｏｒ  ｓｉｍｕｌａｔｉｎｇ  ａｎａｌｏｇ  ａｎｄ  ｍｉｃｒｏｗａｖｅ  ｃｉｒｃｕｉｔｓ’’  Ｋｌｕｗｅｒ  Ａｃａｄｅｍｉｃ  Ｐｕｂｌｉｓｈｅｒｅｓ，  １９９０．
【非特許文献３】
Ｌ．  Ｏ．  Ｃｈｕａ  ａｎｄ  Ａ．  Ｕｓｈｉｄａ，  ’’Ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｃｏｍｐｕｔｉｎｇ  ａｌｍｏｓｔ  ｐｅｒｉｏｄｉｃ  ｓｔｅａｄｙ  ｓｔａｔｅ  ｒｅｓｐｏｎｓｅ  ｏｆ  ｎｏｎｌｉｎｅａｒ  ｓｙｓｔｅｍｓ  ｔｏ  ｍｕｌｔｉｐｌｅ  ｉｎｐｕｔ  ｆｒｅｑｕｅｎｃｉｅｓ’’，  ＩＥＥＥ  ＣＡＳ−２８，  ｐｐ  ９５３−９７１，  １９８１．
【非特許文献４】
Ａ．  Ｕｓｈｉｄａ  ａｎｄ  Ｌ．  Ｏ．  Ｃｈｕａ，  ’’Ａ  ｓｕｂｓｔｉｔｕｔｉｏｎ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｓｏｌｖｉｎｇ  ｎｏｎｌｉｎｅａｒ  ｃｉｒｃｕｉｔｗｉｔｈ  ｍｕｌｔｉ−ｆｒｅｑｕｅｎｃｙ  ｃｏｍｐｏｎｅｎｔｓ’’，  ＩＥＥＥ  ＣＡＳ−３１，  ｐｐ  ７６６−７７９，  １９８４．
【非特許文献５】
Ｖ．  Ｒｉｚｚｏｌｉ  ｅｔ  ａｌ，  ’’Ｇｅｎｅｒａｌ−ｐｕｒｐｏｓｅ  ｈａｒｍｏｎｉｃ  ｂａｌａｎｃｅ  ａｎａｌｙｓｉｓ  ｏｆ  ｎｏｎｌｉｎｅａｒ  ｍｉｃｒｏｗａｖｅ  ｃｉｒｃｕｉｔｓ  ｕｎｄｅｒ  ｍｕｌｔｉｔｏｎｅ  ｅｘｃｉｔｉｏｎ’’  ＩＥＥＥ  Ｔｒａｎｓ．  ＭＴＴ，  Ｖｏｌ．
３６，  ｐｐ．  １６５０−１６６０，  １９８８．
【非特許文献６】
Ｒ．  Ｊ．  Ｇｉｌｍｏｒｅ  ａｎｄ  Ｍ．  Ｂ．  Ｓｔｅｅｒ，  ’’Ｎｏｎｌｉｎｅａｒ  ｃｉｒｃｕｉｔ  ａｎａｌｙｓｉｓ  ｕｓｉｎｇ  ｔｈｅ  ｍｅｔｈｏｄ  ｏｆ  ｈａｒｍｏｎｉｃ  ｂａｌａｎｃｅ  −  ａ  ｒｅｖｉｅｗ  ｏｆ  ｔｈｅ  ａｒｔ．  ＩＩ  ａｄｖａｎｃｅｄ  ｃｏｎｃｅｐｔｓ’’，  Ｉｎｔ．  Ｊ．  Ｍｉｃｒｏｗａｖｅ  ａｎｄ  ＭＭＷ  Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｅｎｇｉｎｅｅｒ，  Ｖｏｌ，  ｐｐ  １５９−１８０，  １９９１．
【００２５】
【発明が解決しようとする課題】
本発明は、計算に使用する情報量を軽減することのできる新たな標本化方法を提供することを目的とする。また、そのような標本化方法を用いた変形ＤＦＴ（ＭＤＦＴ）を提供することを別の目的とする。
【００２６】
【課題を解決するための手段】
上記の課題は、以下の本発明によって解決される。
（１）  Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得工程と（ｍ、ｎは互いに素である。）、
前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、
前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値取得決定工程と、
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程と、
を含む離散フーリエ変換に用いられる標本化点の決定方法。
【００２７】
（２）  前記２次元仮想周波数空間値取得決定工程において、
前記２次元仮想時間空間におけるｍ×ｎ個の格子点上の値（ｔ１，ｔ２）に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値（ｐ，ｑ）は、ハーモニックバランス法における非線形部分の電圧に関する下記式（Ｉ）によって対応づけられることを特徴とする上記（１）に記載の標本化点の決定方法。
【００２８】
【式】
2004171253.tif 000007
【００２９】
（ＶＮＬＲ（ｔ）は、時間ｔにおける電圧を表し、Ｘｐ，ｑＮＬＲは、ｐ、ｑの周波数成分の強度を表し、ｊは、虚数単位を表し、Ｎ２は、ｐ、ｑの最大周波数を表し、ω１、ω２は角周波数を表す。）
【００３０】
（３）  前記１次元仮想周波数空間値決定工程における、ｒ軸からなる１次元仮想周波数空間での値は、下記式（ＩＩ）によって対応づけられることを特徴とする上記（１）、又は上記（２）に記載の標本点の決定方法。
【００３１】
【式】
2004171253.tif 000008
【００３２】
（ここで、ｔ３は１次元仮想時間空間における１次元ループの経路（Ｔ３軸）上の座標値を表し、Ｎ３は１次元ループの経路（Ｔ３軸）上でＶＮＬＲを表現したときの最大周波数を表し、ｍ、ｎはそれぞれｔ１軸およびｔ２軸の分割値を表し、ｊは虚数単位を表す。）
【００３３】
（４）前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値に変換する変換工程は、
下記式（ＩＩＩ）を用いて変換されることを特徴とする上記（１）または（２）に記載の標本化点の決定方法。
【００３４】
【式】
ｐｎ＋ｑｍ＝ｒ        （ＩＩＩ）
（式（ＩＩ）中、ｍ、ｎはそれぞれ、２次元仮想時間空間におけるＴ１軸およびＴ２軸方向の分割値を表し、ｐ、ｑは、２次元仮想周波数空間での座標値（ｐ，ｑ）を表す。）
【００３５】
（５）前記最高周波数算出工程は、２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除く上記（１）〜（４）のいずれか１項に記載の標本化点の決定方法。
（６）離散フーリエ変換の代わりに離散コサイン変換に用いられる上記（１）〜上記（５）のいずれか１項に記載の標本化点の決定方法。
（７）離散フーリエ変換の代わりに離散サイン変換に用いられる上記（１）〜上記（５）のいずれか１項に記載の標本化点の決定方法。
（８）  上記（１）〜上記（７）のいずれか１項に記載の標本化点の決定方法を用いた音情報の標本化方法。
（９）  上記（１）〜上記（７）のいずれか１項に記載の標本化点の決定方法を用いた画像情報の標本化方法。
（１０）  上記（１）〜上記（７）のいずれか１項に記載の標本化点の決定方法を用いた離散フーリエ変換方法。
【００３６】
（１１）  コンピュータに、
Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得工程と、
前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、
前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値取得決定工程と、
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程と、
からなる離散フーリエ変換に用いられる標本化点の決定方法を実行させるためのプログラム。
【００３７】
（１２）  コンピュータを、
自然数ｍとｎを入力する入力手段と、
Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得手段と、
前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定手段と、
前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値取得決定手段と、
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換手段と、
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出手段と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出手段により算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定手段として機能させ、
離散フーリエ変換に用いられる標本化点を決定するためのプログラム。
【００３８】
（１３）  上記（１２）に記載のプログラムを記録した記録媒体。
（１４）コンピュータに
Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得工程と、
前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、
前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値取得決定工程と、
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程と、
を含む離散フーリエ変換に用いられる標本化点の決定方法を実行させるためのプログラムを記録したコンピュータ読み取り可能な記録媒体。
【００３９】
（１５）自然数ｍとｎを入力する入力手段と、
Ｔ１軸及びＴ２軸からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点を得る格子点取得手段と、
前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定手段と、
前記２次元仮想時間空間における各格子点上の値に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間での値を取得するか決定する２次元仮想周波数空間値決定手段と、
前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換手段と、
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出手段と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出手段により算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を離散フーリエ変換に用いられる標本化点とする標本化点決定手段と、
を含むコンピュータ。
【００４０】
（１６）Ｔ１軸、Ｔ２軸及びＴ３軸からなる３次元仮想時間空間において、それぞれの軸をｍ個、ｎ個及びｌ個に分割し、ｍ×ｎ×ｌ個の格子点を得る格子点取得工程と、
前記３次元仮想時間空間におけるｍ×ｎ×ｌ個の全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、
前記３次元仮想時間空間における各格子点上の値に対する、３次元仮想周波数空間での値を取得するか決定する３次元仮想周波数空間値取得決定工程と、
前記３次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、
前記３次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程と、
を含む離散フーリエ変換に用いられる標本化点の決定方法。
（１７）Ｎ個の軸からなるＮ次元仮想空間において、それぞれの軸を分割し複数の格子点を得る格子点取得工程と、
前記Ｎ次元仮想時間空間における全ての格子点を一度だけ通過する１次元ループの経路を少なくともひとつ決定し、１次元仮想時間空間を作成する経路決定工程と、
前記Ｎ次元仮想時間空間における各格子点上の値に対する、Ｎ次元仮想周波数空間での値を取得するか決定するＮ次元仮想周波数空間値取得決定工程と、
前記Ｎ次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる変換工程と、
前記Ｎ次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する最高周波数算出工程と、
前記１次元仮想時間空間を形成する１次元ループの経路を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点とする標本化点決定工程と、
を含む離散フーリエ変換に用いられる標本化点の決定方法。
（１８）（１６）又は（１７）に記載の標本化点の決定方法を用いた離散フーリエ変換方法。
【００４１】
本発明の２次元ＤＦＴのデータ標本化方法は、標本点の数と位置とを変えることにより、情報量を軽減できる。なお、以下では離散フーリエ変換について説明するが、本発明の標本化点は、離散コサイン変換および離散サイン変換にも用いることができる。
【００４２】
【発明の実施の形態】
以下、図３に示すフローチャートに従って、本発明の標本化点の決定方法の一例を示す。なお、図中Ｓは、ステップ（工程）を意味する。なお、図１（ａ）、図１（ｂ）、図１（ｃ）は、２次元フーリエ変換の標本化の様子を表し、図中の黒丸は標本化点を表す。そして、図２（ａ）、図２（ｂ１）、図２（ｂ２）、図２（ｃ）は、それぞれ図１（ａ）、図１（ｂ）、図１（ｂ）、図１（ｃ）に対応したフーリエ変換の要素を表す。
【００４３】
（格子点取得工程）
格子点取得工程では、例えば図１（ａ）に示されるように、Ｔ１軸１及びＴ２軸２からなる２次元仮想時間空間において、それぞれの軸をｍ個及びｎ個に分割し、ｍ×ｎ個の格子点３を得る（Ｓ１０１）。
【００４４】
（経路決定工程）
経路決定工程では、経路決定手段が、前記２次元仮想時間空間におけるｍ×ｎ個の全ての格子点を一度だけ通過する１次元ループの経路（例えば、図１（ｂ）の４）をひとつ決定し、１次元仮想時間空間を作成する（Ｓ１０２）。なお、図１（ｂ）の４で示される１次元ループの経路は、例えばＩとＩ’が同じ点を意味しているので、無限ループを形成する。
【００４５】
（２次元仮想周波数空間値取得決定工程）
２次元仮想周波数空間値取得決定工程では、前記２次元仮想時間空間における各格子点３上の値（座標値）に対する、ｐ軸とｑ軸とからなる２次元仮想周波数空間（例えば、図２（ａ））での値（従って座標値）を取得するか決定する（Ｓ１０３）。図２は２次元仮想周波数空間であり、５はｐ軸、６はｑ軸、７、８はそれぞれ２次元仮想周波数空間において、離散フーリエ変換する必要がない点と必要がある点を表す。
この座標値の決定にあたっては、例えば、上記式（４）を利用すればよい。
【００４６】
（１次元仮想周波数空間値決定工程）
１次元仮想周波数空間値決定工程では、前記１次元仮想空間における各格子点上の値に対してｒ軸からなる１次元仮想周波数空間での値を決定する（Ｓ１０４）。この工程は任意の工程であり、スキップしてもよい。
【００４７】
（変換工程）
変換工程では、前記２次元仮想周波数空間での値を前記１次元仮想周波数空間での値と対応させる（Ｓ１０５）。
変換式としては例えば、下記の式（ＩＩ）が挙げられる。
【式】
ｐｎ＋ｑｍ＝ｒ        （ＩＩ）
（式（ＩＩ）中、ｍ、ｎはそれぞれ、２次元仮想時間空間における座標値（ｔ１，ｔ２）を表し、ｐ、ｑは、２次元仮想周波数空間でのＴ１軸およびＴ２軸方向の分割値を表す。）
【００４８】
（最高周波数算出工程）
前記２次元仮想周波数空間において離散フーリエ変換する必要がない点を決定する手段が、前記２次元仮想周波数空間において離散フーリエ変換する必要がない点（図２（ａ）、図２（ｂ）の７）を決定する。このためには、予め離散フーリエ変換判断手段または離散フーリエ変換必要条件入力手段により離散フーリエ変換する必要のある周波数領域を決定しておき、２次元仮想周波数空間において離散フーリエ変換する必要がない点を決定することができることが好ましい。最高周波数算出工程では、前記２次元仮想周波数空間において離散フーリエ変換する必要がない点と対応する１次元仮想周波数空間上の点を少なくともひとつ取り除いた場合の（またはひとつも取り除かない場合の）、１次元仮想周波数空間の最高周波数を算出する（Ｓ１０６）。図２（ｂ２）の１０は、取り除かれる１次元仮想周波数空間上の点を表す。また、図２（ｂ２）と図２（ｃ）の９は、１次元仮想周波数空間における座標軸を表す。
【００４９】
（標本化点決定工程）
標本化点決定工程では、前記１次元仮想時間空間を形成する１次元ループの経路（図１（ｃ）の４）を上記最高周波数算出工程で算出された最高周波数の２倍に１を足した数で分割し、分割された前記１次元ループの経路上の点を標本化点（図１（ｃ）の１１）とする（Ｓ１０７）。このようにして２次元仮想時間空間における標本化点が定まる。
【００５０】
以下に、本発明の標本化方法を、２次元及び１次元ＤＦＴにおけるフーリエ変換要素と、ｔ１とｔ２時間空間における標本点について説明する。
式（４）中の周波数要素であるｐω１＋ｐωｔ２について、最大オーダーＮ２を簡単のために２として以下説明する。ここで、ナイキストの定理より、ｔ１とｔ２のどちらの時間空間においても、少なくとも２＊２＋１＝５点が、信号からの周波数データを計算するために必要とされる。図１（ａ）は、これに関連した符号化を示す。
【００５１】
ＤＦＴの特徴を把握するために、どのような一連のステップにより格子点（標本点）が訪問されたかという点を考慮する。図１（ａ）では、全ての５ステップで結局はスタート地点に戻るため、２５のステップにより、２５個全ての標本点を訪れることはできない。図１（ｂ）では、標本点が、６×５の格子点上にある。これら３０個の標本点は、図中のスタート（Ｓｔａｒｔ）からＪ地点まで、３０の連続したステップを経ることにより訪れることができる。なお、図中のＡとＡ’、ＢとＢ’などは、同じ点を表す。
【００５２】
ここで、議論を一般化するために６と５を一般的な数であるｍとｎにそれぞれ置き換える。そして、ｍとｎとは互いに素であると仮定する。もしも、ある標本点が２次元格子において、２つの連続したステップ。すなわち、ｍ＊ｎステップ以内のｋ１とｋ２ステップによって訪問されたとすると、下記式（６）は満たされ、ｋ１＝ｋ２が導かれる。
【００５３】
【式】
2004171253.tif 000009
これは、連続したｍ＊ｎステップの中で、それぞれの格子点が一度だけ訪れられることを意味している。
【００５４】
次に、２次元格子におけるｔ１とｔ２に関する二つのＤＦＴの積である２次元ＤＦＴを検討する。
ｔ１方向にＴ１／ｍ移動する時、ｅｘｐ（２πｊｋ１／ｍ）（０≦ｋ１＜ｍ）の位相差を有する周波数要素ｋ１が用いられる。ｔ２方向には同様な性質を有する周波数要素ｋ２が用いられる。このようにして、ｍ＊ｎ個の周波数要素が存在することとなる。
【００５５】
もうひとつのタイプは、１次元ＤＦＴであり、ｔ１方向にＴ１／ｍ移動し、ｔ２方向にＴ２／ｎ移動する動作を１ステップとしている。この移動は、ｍ＊ｎステップによる１次元の閉じたループ内で用いられる。一つのステップでｅｘｐ（２πｊｋ３／（ｍ＊ｎ））だけ位相の異なるｍ＊ｎ個の周波数要素が用いられる。
【００５６】
２次元ＤＦＴにおける二つの周波数要素が、１次元の１つの周波数要素と等価であれば、下記式（７）を満たし、ｐ１＝ｐ２とｑ１＝ｑ２とが導かれる。
【００５７】
【式】
2004171253.tif 000010
【００５８】
この式は、２次元ＤＦＴのそれぞれの周波数要素が、１次元ＤＦＴにおけるｍ＊ｎ個の周波数要素のいずれかと必ず対応し、その逆も成立することを意味する。例えば、式（７）より、ｍ＝６、ｎ＝５の場合、ｐ＝１とｑ＝０であれば、ｒ＝５である。また、ｐ＝０と、ｑ＝１であれば、ｒ＝６である。また、ｐ＝ｑ＝１であれば、ｒ＝１１である。さらに、ｒ＝１４であれば、ｐ＝４かつｑ＝４であり、ｒ＝２９（＝−１）であればｐ＝１かつｑ＝４である。
【００５９】
ここで、式（５）を満たす要素でのみ振幅が０ではないことに注意しなければならない（例えば、非特許文献５（Ｖ．  Ｒｉｚｚｏｌｉ  ｅｔ  ａｌ，  ’’Ｇｅｎｅｒａｌ−ｐｕｒｐｏｓｅ  ｈａｒｍｏｎｉｃ  ｂａｌａｎｃｅ  ａｎａｌｙｓｉｓ  ｏｆ  ｎｏｎｌｉｎｅａｒ  ｍｉｃｒｏｗａｖｅ  ｃｉｒｃｕｉｔｓ  ｕｎｄｅｒ  ｍｕｌｔｉｔｏｎｅ  ｅｘｃｉｔｉｏｎ’’  ＩＥＥＥ  Ｔｒａｎｓ．  ＭＴＴ，  Ｖｏｌ．  ３６，  ｐｐ．  １６５０−１６６０，  １９８８．））。図２（ａ）において、式（５）を満たす１３個のフーリエ変換する必要がある要素があり、式（５）を満たさない１２個のフーリエ変換する必要がない要素がある。図において、●はフーリエ変換する必要がある要素を意味し、×はフーリエ変換する必要がない要素を意味する。図２（ｂ１）では、振幅が０であり、フーリエ変換する必要がない要素が５つ、図２（ａ）に加えられている。
【００６０】
図２（ｂ２）においては、式（７）と関連し、１３の重要な点と１７の無視できる要素が、それぞれ●と×で表されている。図２（ｂ２）において、３０個の要素のうち最も高い周波数域にある１次元周波数は１２である。これは、１３個のフーリエ変換する必要がある要素に対しては、ナイキストの定理にしたがって２５（＝２×１２＋１）個だけのフーリエ変換点が必要ということを意味している。２５個の標本化点を、図１（ｃ）に示す。
【００６１】
図１（ｃ）に示された２５個の標本化点を１次元ＤＦＴした結果を、図２（ｃ）に示す。
【００６２】
図２（ａ）、図２（ｂ１）、図２（ｂ２）、図２（ｃ）を比較する。図２（ｃ）の２５個の要素には、１３個の重要な要素を含んでいる。振幅ゼロである要素を５つ加えて、１次元ループを作成したものが図２（ｂ２）である。式（７）を用いれば、図２（ｂ１）において得られた結果は、図２（ｂ２）において得られた結果と等価であることがわかる。その結果、図２（ａ）、図２（ｂ１）、図２（ｂ２）、及び図２（ｃ）における１３個の重要な要素は、図２（ａ）と図２（ｃ）では無視できる要素が異なるにもかかわらず、同一であることがわかる。このことは、図１（ｃ）における標本化点を用いた１次元ＤＦＴによれば、図２（ａ）における１３個の重要な周波数要素を全て得ることができることを意味している。単に、それぞれの標本化点を図１（ａ）に示された位置から図１（ｃ）に示された位置に移動するだけで、２次元ＤＦＴの２５点（５×５）の標本点を、１次元ＤＦＴの５＊５点に変換することができる。
【００６３】
（本発明のＤＦＴを用いた回路解析法）
電界効果トランジスタ（ＦＥＴ）を含む回路は、例えば、図４に示す等価回路で表される。同図に於いて、Ｚｉｎは入力インピーダンス、Ｚｏｕｔ  は出力インピーダンス、ＺＧ  はゲートインピーダンス、Ｚｄ  はドレインインピーダンス、ＺＳ  はソースインピーダンス、Ｚｄｓはドイレン・ソース間インピーダンス、Ｃｇｄはゲート・ドレイン間容量、Ｃｇｓはゲート・ソース間容量を示し、又Ｅは信号源の電圧、Ｉｉｎ１  ，Ｉｏｕｔ１はＦＥＴの入力電流及び出力電流（ノンリニア）、Ｉｄｓはドレイン・ソース間電流、Ｉｉｎ２  ，Ｉｏｕｔ２は回路の入力電流及び出力電流（リニア）、Ｐｉｎは入力パワー、Ｖ１  はゲート・ソース間の電圧、Ｖ２  はドレイン・ソース間の電圧を示す。
図Ｚの等価回路を参照して説明すると、この回路解析法は、入力電流Ｉｉｎ２  を、
Ｉｉｎ２  ＝（１／Ｚ１  ）〔Ｒｅ（Ｚ２  Ｖ２  −Ｖ１  ）±  ［｛Ｒｅ（Ｚ２  Ｖ２  −Ｖ１  ）｝２  ＋４Ｚ１  Ｐｉｎ  ］１／２  〕
但し、  Ｚ１  ＝２Ｒｅ〔ＺＧ  ＋ＺＳ  −｛ＺＳ  ２  ／（ＺＤ  ＋ＺＳ  ）｝
Ｚ２  ＝ＺＳ  ／（ＺＤ  ＋ＺＳ  ）
ＺＤ  ＝Ｚｏｕｔ  ＋Ｚｄ    Ｒｅ＝実数部を意味する。
として計算するものである。このような計算を行うことにより、入力インピーダンスを共役整合とすることができる。
以上により、ＦＥＴを能動素子とした回路解析に本発明のＭＤＦＴを応用した例を示したが、他のトランジスタを能動素子した回路の解析にも適用できる。
【００６４】
前述のようなＦＥＴを含む回路の解析は、例えば、図５に示すステップ（ａ）〜（ｉ）に示すハーモニックバランス法を用いて行うことができる。即ち、回路パラメータ，ＦＥＴパラメータ，周波数，入力パワーを入力し（ａ）、電圧Ｖ１  ，Ｖ２  を小信号解析により計算して求め（ｂ）、この電圧Ｖ１  ，Ｖ２  を用いて時間領域のＦＥＴ電流を計算し（ｃ）、時間領域のＦＥＴ電流のフーリエ変換により、周波数領域のＦＥＴ電流Ｉｉｎ１  ，Ｉｏｕｔ１を計算し（ｄ）、回路電流Ｉｉｎ２  ，Ｉｏｕｔ２を計算し（ｅ）、この回路電流Ｉｉｎ２  ，Ｉｏｕｔ２と、ＦＥＴ電流Ｉｉｎ１  ，Ｉｏｕｔ１との差をエラーとして算出し〔（Ｉｉｎ２  −Ｉｉｎ１  ）及び（Ｉｏｕｔ２−Ｉｏｕｔ１）〕（ｆ）、その自乗の平均の平方根のエラー（ＲＭＳエラー）が許容値Ｙより大きいか否かを判定し（ｇ）、エラーが大きい場合（＞Ｙ）、ニュートン法を利用してＶ１  ，Ｖ２  を計算し（ｈ）、再計算したＶ１  ，Ｖ２  を用いて時間領域のＦＥＴ電流を計算するステップ（ｃ）に戻り、又エラーが小さい場合（＜Ｙ）は、電圧，電流の入出力特性を出力する（ｉ）。（例えば、「ＩＥＥＥ  ＴＲＡＮＳＡＣＴＩＯＮＳ  ＯＮ  ＭＩＣＲＯＷＡＶＥ  ＴＨＥＯＲＹ  ＡＮＤ  ＴＥＣＨＮＩＱＵＥＳ，ＶＯＬ．ＭＴＴ−３３，ＮＯ．１２，ＤＥＣＥＭＢＥＲ１９８５，ｐ．１３８３〜１３９４」及び、「ＩＥＥＥ  ＴＲＡＮＳＡＣＴＩＯＮＳ  ＯＮＣＯＭＰＵＴＥＲ−ＡＩＤＥＤ  ＤＥＳＩＧＮ，ＶＯＬ．ＣＡＤ−５，ＮＯ．４，ＯＣＴＯＢＥＲ  １９８６，ｐ．５２１〜５３５」参照）。上記工程（ｄ）において、フーリエ変換を行う際に本発明のＭＤＦＴ法を用いることにより情報量を軽減し、効果的に回路の解析を行うことができる。
【００６５】
（Ｎ次元離散フーリエ変換）
以下に、以上に説明した２次元離散フーリエ変換の標本点決定方法が、Ｎ次元離散フーリエ変換（Ｎは３以上の整数）にも用いられることを、３次元仮想時間空間における標本化点決定方法を例にとって説明する。
Ｔ１軸、Ｔ２軸及びＴ３軸からなる３次元仮想時間空間において、それぞれの軸をｍ個、ｎ個及びｌ（エル）個に分割する。すると、ｍ×ｎ×ｌ個の格子点が得られる。ここで、ｎ、ｍ、ｌは互いに素であることが好ましい。互いに素でない場合には、いずれかに１を加え続け、それぞれが互いに素となるように変換すればよい。
【００６６】
例えば、基準点からベクトル（Ｔ１／ｍ，Ｔ２／ｎ，Ｔ３／ｌ）に従って、ｍ×ｎ×ｌステップ進むと、全ての格子点をとおりもとの基準点に戻ることとなる。この経路（ループ）が１次元仮想時間空間となる。
【００６７】
もし仮に、上記のステップが１次元ループとならず、同じ点を２度通るとする。すなわち、ｋ１ステップとｋ２ステップで同一の点（ａ，ｂ，ｃ）に到達したとする。
すると、以下の式（Ａ１）〜（Ａ６）が成り立つ。
【００６８】
【式】
ｋ１  ＝  ａ  ｍｏｄ  ｍ            ・・・（Ａ１）
ｋ１  ＝  ｂ  ｍｏｄ  ｎ            ・・・（Ａ２）
ｋ１  ＝  ｃ  ｍｏｄ  ｌ            ・・・（Ａ３）
ｋ２  ＝  ａ  ｍｏｄ  ｍ            ・・・（Ａ４）
ｋ２  ＝  ｂ  ｍｏｄ  ｎ            ・・・（Ａ５）
ｋ２  ＝  ｃ  ｍｏｄ  ｌ            ・・・（Ａ６）
上記の式（Ａ１）〜（Ａ６）において、ｍｏｄは、例えばｋ＝  ａ  ｍｏｄ  ｍであれば、ａはｋをｍで割った時の余りを意味する。
【００６９】
（Ａ１）と（Ａ４）とから、（ｋ１−ｋ２）  ＝  ０  ｍｏｄ  ｍがわかる。なお、ある数をｍで割ったときの余りが０ということはその数がｍの倍数であることを意味する。よって、（ｋ１−ｋ２）は、ｍの倍数であり、αを整数として、αｍと記述できる。
さらに、（Ａ２）と（Ａ５）とから、（ｋ１−ｋ２）  ＝  ０  ｍｏｄ  ｎであり、（ｋ１−ｋ２）は、ｎの倍数である。一方、ｎとｍとは互いに素であるから、βを整数としてα＝βｎが成り立つ。さらに、（Ａ３）と（Ａ６）とから、（ｋ１−ｋ２）  ＝  ０  ｍｏｄ  ｌでり、（ｋ１−ｋ２）は、ｌの倍数であることがわかる。ｍ、ｎとｌとは互いに素なので、γを整数として、β＝γｌを記述することができる。以上から、（ｋ１−ｋ２）  ＝γｍｎｌであることがわかる。
【００７０】
一方、（ｋ１−ｋ２）は０以上ｍｎｌ未満である。従って、γｍｎｌも０以上ｍｎｌ未満ということになる。この関係を満たす整数γとしては０以外に存在しない。したがって、γ＝０、よって（ｋ１−ｋ２）＝０から、ｋ１＝ｋ２ということになる。これは、ｋ１とｋ２とが異なるとする前提に矛盾する。この矛盾は、３次元仮想時間空間上での格子点をたどるステップが１次元ループとならず、同じ点を２度通るという仮定に起因するものである。したがって、３次元仮想時間空間上での格子点をたどるステップが１次元ループとなり、同じ点を２度通らないことが証明された。同様の理論をＮ次元仮想時間空間にまで拡張することができるため、Ｎ次元離散フーリエ変換においても本発明の標本化点の決定方法を用いることができるのである。
【００７１】
３次元ＤＦＴにおける２つの周波数要素が、１次元のひとつの周波数要素と等価であれば、下記式を満たす。
【００７２】
【式】
ｐ１ｎｌ＋ｑ１ｍｌ＋ｓ１ｍｎ＝ｒ
ｐ２ｎｌ＋ｑ２ｍｌ＋ｓ２ｍｎ＝ｒ
ここで、０≦ｐ１、ｐ２＜ｍ、０≦ｑ１、ｑ２＜ｎ、０≦ｓ１、ｓ２＜１である。
【００７３】
これからｐ１＝ｐ２、ｑ１＝ｑ２、ｓ１＝ｓ２が導かれる。また、この結果は、Ｎ次元（Ｎは４以上）のＤＦＴの場合にも同様に拡張される。
【００７４】
【実施例】
以下実施例を用いて本発明を具体的に説明する。
（実施例１）
図１（ａ）、図１（ｂ）、図１（ｃ）は、２次元フーリエ変換の標本化の様子を表し、図中の黒丸は標本化点を表す。そして、図２（ａ）、図２（ｂ１）、図２（ｂ２）、図２（ｃ）は、それぞれ図１（ａ）、図１（ｂ）、図１（ｂ）、図１（ｃ）に対応したフーリエ変換の要素を表す。
式（４）中の周波数要素であるｐω１＋ｐωｔ２について、最大オーダーＮ２を簡単のために２として以下説明する。ここで、ナイキストの定理より、ｔ１とｔ２のどちらの時間空間においても２＊２＋１＝５点が信号からの周波数データを計算するために必要とされる。図１（ａ）は、これに関連した符号化を示す。
図１（ａ）では、全てのステップが結局はスタート地点に戻るため、２５のステップにより、２５個全ての標本点を訪れることはできない。
図１（ｂ）では、標本点が、６×５の格子点上にある。これら３０個の標本点は、図中のスタート（Ｓｔａｒｔ）からＪ地点まで、３０の連続したステップを減ることにより訪れることができる。なお、図中のＡとＡ’、ＢとＢ’などは、同じ点を表す。
【００７５】
図１（ａ）上の２次元ＤＦＴ標本点は、図２（ａ）の●（黒点）、及び×（ばつ印）に変換される。
図１（ｂ）上の２次元ＤＦＴ標本点は、図２（ｂ１）の●（黒点）、及び×（ばつ印）に変換される。
ここで、●をフーリエ変換する必要がある要素とし、×をフーリエ変換する必要がない要素とする。図２（ｂ１）と、図２（ａ）とを比較すると、フーリエ変換する必要がない要素が５つ増えている。図２（ｂ１）の格子点を下記式にしたがって、変換すると図２（ｂ２）になる。
【００７６】
【式】
2004171253.tif 000011
なお、図２（ｂ１）においては、ｍ＝６、ｎ＝５である。
【００７７】
図２（ｂ２）においては、図２（ｂ１）において●（黒点）、及び×（ばつ印）だった点が、それぞれ●及び×に変換されている。すなわち、図２（ｂ２）と図２（ｂ１）は等価である。
この実施例において、高周波領域におけるフーリエ変換要素は、フーリエ変換する必要がない要素である。図２（ｂ２）において、ｒが−１２から１２までの範囲の２５点に、フーリエ変換する必要がある要素が集まっている。これは、１３個のフーリエ変換する必要がある要素に対しては、２５個以上のフーリエ変換点が必要ということになり、ナイキストの定理を満たす。そこで、ｒ＝−１４、−１３、１３、１４、１５（−１５と等価）の各点を除いた。このようにして作られた１次元のループが図２（ｃ）に示されるループである。
【００７８】
図２（ｃ）を２次元に表したものが、図１（ｃ）である。これは、図１（ｃ）上の矢印をたどった経路について、２５等分した点を標本点としたものである。図２（ａ）、と図２（ｃ）には、無視すべき点が、図２（ｂ１）、図２（ｂ２）の１７個に比べて、１３個と少ないけれども、図２（ａ）、図２（ｂ１）、図２（ｂ２）、図２（ｃ）は、１３個のフーリエ変換する必要がある要素について等価である。このことは、図１（ｃ）における標本点を用いた１次元のＤＦＴは、図２（ａ）におけるフーリエ変換する必要がある要素１３個を全て含んでいる。すなわち、図１（ａ）における標本点の位置を、図１（ｃ）の位置に少しずらしたことにより、２次元ＤＦＴの２５点（５×５）の標本点を、１次元ＤＦＴの５＊５点に変換することができる。
【００７９】
（本発明の標本化方法の利用）
本発明の標本化方法を用いて音情報や画像情報、動画情報などのアナログ情報をデジタル情報に変換し、所定の処理や通信を行った後、例えば、復号化してデジタル情報をアナログ情報に戻すことで所定の処理や効率的な処理を施した情報を得ることができる。これらの複合化方法は、公知の方法を用いることができる。
また、上記の標本化方法を可能とする回路やハードウェア、コンピュータを用いれば、情報処理を効率化できることとなる。
さらには、コンピュータを本発明の標本化方法を利用可能なように機能させるプログラム、およびそのようなプログラムを記録した記録媒体を用いれば、上記のとおり効率的に情報を処理できることとなる。
【００８０】
【発明の効果】
本発明によれば、標本点の位置（と数）をずらすことで、２次元ＤＦＴを等価な１次元ＤＦＴへと変換できる。そして、本発明の工程によれば、標本点の位置（と数）をずらすことにより、ＤＦＴによる計算を単純化することができる。
デジタルオーディオ技術や、動画圧縮技術など、アナログ／デジタル信号変換においては情報量を減らすことが重要であるが、本発明を用いれば、これらの情報量を軽減できる。
【図面の簡単な説明】
【図１】図１（ａ）は、２次元仮想時間空間を一例を示す。図１（ｂ）は、２次元仮想時間空間を一例を示す。図１（ｃ）は、２次元仮想時間空間を一例を示し、図中の標本点は本発明による標本点決定方法により決定された標本点の一例を示す。
【図２】図２（ａ）は、図１（ａ）に対応する２次元仮想周波数空間を示す。図２（ｂ１）は、図１（ｂ）に対応する２次元仮想周波数空間を示す。図２（ｂ２）は図１（ｂ）に対応する１次元仮想周波数空間を示す。図２（ｃ）は、図１（ｃ）に対応する１次元仮想周波数空間を示す。
【図３】図３は、本発明の標本化点の決定方法の一例を示すフローチャートである。
【図４】図４は、電界効果トランジスタの等価回路を示す。
【図５】図５は、本発明の標本点決定法の利用例を示す。
【符号の説明】
１  ２次元仮想時間空間におけるＴ１軸
２  ２次元仮想時間空間におけるＴ２軸
３  ２次元仮想時間空間における格子点
４  １次元仮想時間空間における１次元ループの経路（Ｔ３軸）（図１（ｂ）中、例えば、ＩとＩ’は同一の点を意味する。）
５  ２次元仮想時間空間におけるｐ軸
６  ２次元仮想時間空間におけるｑ軸
７  ２次元仮想周波数空間における格子点（離散フーリエ変換する必要がない点（この場合、高周波数の点））
８  ２次元仮想周波数空間における格子点（離散フーリエ変換する必要がある点（この場合、低周波数の点））
９  １次元仮想周波数空間におけるｒ軸
１０  取り除かれる１次元仮想周波数空間上の点
１１  １次元ループの経路（Ｔ３軸）上に配置された標本点
【図１】
2004171253.tif 000014
【図２】
2004171253.tif 000015
【図３】
2004171253.tif 000016
【図４】
2004171253.tif 000017
【図５】
2004171253.tif 000018