JPH0148583B2 - - Google Patents

Description

【発明の詳細な説明】

本発明はウオルシユ関数系を多値化かつ複素数
化した関数系による変換である多値ウオルシユ変
換装置に関する。 従来、信号を直交変換する手段としては、フー
リエ変換やウオルシユ変換などがあつた。通常よ
く用いられているフーリエ変換は、三角関数系に
より直交変換であり、その演算には乗業器を必要
としていた。一方、ウオルシユ変換は、ウオルシ
ユ関数系による直交変換であり、ウオルシユ関数
系はその要素が＋１と−１のみであるため、ウオ
ルシユ変換の演算は加減算のみで行える利点があ
り、フーリエ変換の近似として用いられていたが
近似が荒いという欠点があつた。 次にこのウオルシユ関数について説明する。(1)
式で定義される2ⁱ行2ⁱ列の行列（アダマール行列
と呼ばれる） H_i＝H_i-1H₁ ……(1) ただしH₁＝（１ １−１）であり、はクロネツカ
積を意味する。 の各行を第１図に示すように区間（−1/2、1/2）
の波形として見なすとHiより2ⁱ個の波形を生成す
ることができる。これらの波形がウオルシユ関数
である。ウオルシユ関数のゼロと交差する回数を
交番数と呼び、(1)式より生成される2ⁱ個のウオル
シユ関数は０〜2ⁱ−１の交番数を持つている。こ
のウオルシユ関数系は完備な正規直交関数系を成
しており、フーリエ変換は周波数分析と呼ばれる
ように、ウオルシユ変換は交番数分析と呼ばれ
る。また、フーリエ変換の結果はフーリエスペク
トルと呼ばれるように、ウオルシユ変換の結果を
ウオルシユスペクトルと呼ばれる。 さらに、ウオルシユ変換を高速に計算する高速
ウオルシユ変換（FWTと略称する）が知られて
おり、高速フーリエ変換（FFTと略称する）と
対応して行列にて表現する方法が、昭和51年12月
電子通信学会論文誌Vol.59−Ａ、No.12の第1134頁
〜第1135頁の「フーリエ変換とウオルシユ変換に
関する一検討」に記載されている。入力時系列を
逆２進順に並べた列ベクトルをＸ、変換行列を
Ａ、フーリエスペクトルをＦとすれば、FFTは Ｆ＝Ａ・Ｘ＝P_o・P_o-1・…P₁・Ｘ ……(2) とｎ回の行列の積として表現できる。ここで各P_i
は(3)、(4)、(5)、式より決定される。 ただしa_i＝exp（−jπ／2ⁱ）とし、I_iは2ⁱ行2ⁱ列の
単位行列であり、diag（・）は括弧内を対角要素
とする対角行列である。 ここで逆２進順序とは自然数を２進表現し、そ
の桁を逆転させた数を考え、その数の順序に並ら
べることであり、ｎ＝３の場合Ｘ＝（x₀、x₄、x₂、
x₆、x₁、x₅、x₃、x₇）となる。また、P_iはFFT
のｉ段目の演算を表現しており、ｎ＝３の場合
P₁、P₂、P₃は となり、各行ともゼロでない要素は２つでありバ
タフライ演算を表現している。 同様に、入力時系列を逆２進順に並べた列ベク
トルをＸ、変換行列をＣ、ウオルシユスペクトル
の列ベクトルをＷとすれば、FWTは Ｗ＝Ｃ・Ｘ＝C_o・G_o-1・…G₁・Ｘ ……(7) とｎ回の行列の積として表現できる。ここで各G_i
は(8)、(9)、(10)式より決定される。 ｎ＝３の場合、ウオルシユスペクトルはＷ＝
（W₀、W₂、W₄、W₆、W₇、W₅、W₃、W₁）であ
る。さらに各段の演算G₁、G₂、G₃は G₁＝P₁ となる。以上説明したようにFWTは、FFTにお
けるD_iの要素a^k _iをa^k _i＝exp（−jθ）とし ０Θ＜π／２なるとき a_i ^k→１と置き換え π／２Θ＜πなるとき a_i ^k→−１と置き換え たものと考えることができる。 このようにウオルシユ変換はフーリエ変換にお
ける三角関数値を±１に量子化したものと考えら
れ、乗算のない演算でフーリエスペクトラムの近
似が求められる。しかし、量子化が荒いためフー
リエスペクトラムのよい近似値が得られない欠点
があつた。 本発明の目的は、加減算器またはシフタと加減
算器のみで求められ、かつウオルシユスペクトル
よりよりフーリエスペクトルに近い多値ウオルシ
ユスペクトルを求めることのできる多値ウオルシ
ユ変換装置を提供することにある。 本発明の多値ウオルシユ変換装置は、入力時系
列データを保持するバツフアメモリ部と、バツフ
アメモリ部より読み出されたデータを用いて多値
ウオルシユスペクトラムを求めるための加減算器
またはシフタと加減算器による多値ウオルシユ演
算部と、前記のバツフアメモリ部と、多値ウオル
シユ演算部を制御する制御部を有している。 本発明の多値ウオルシユ変換装置は、ウオルシ
ユ関数の多値化および複素数化をその要素を１ま
たは1/2に限定することにより加減算器またはシ
フタと加減算器による簡単な演算で構成すること
ができる。さらに、多値ウオルシユ変換装置はフ
ーリエスペクトラムとの近似度がウオルシユスペ
クトラムより高い多値ウオルシユスペクトラムを
得ることができる利点を持つている。 次に本発明の原理である多値ウオルシユ変換に
ついて説明する。ウオルシユ関数は三角関数を±
１へ量子化したものであるので、より細かい量子
化による多値ウオルシユ関数を導入することによ
つてよりフーリエスペクトラムへ近づけることが
できる。多値化の方法として、複素平面の単位円
上の数個の点へ対応させることが考えられる。例
えば第２図に示した の８個の要素を持つ多値ウオルシユ関数が考えら
れる。しかし、前記の方法による多値ウオルシユ
関数はe〓^/4jなどの要素を持つため、その変換には
乗算を必要とする。ここでe〓^/4jの代わりに１＋ｊ
を用いる方法を提案する。すなわち第３図に示し
た（１、１＋ｊ、ｊ、−１＋ｊ、−１、−１−ｊ、−
ｊ、１−ｊ）の８個の要素を持つ８値ウオルシユ
関数を提案する。この関数系による８値ウオルシ
ユ変換の演算は（±１、±ｊ）との積の演算であ
るため加減算のみで実行可能である。具体的な計
算方法は(2)、(3)、(4)、(5)式に示したFFTによる
計算手順の内より(5)式を(11)式へ変えたものとな
る。 Di＝diag（１、〔a_i〕、〔a_i ²〕、…、〔a_i ^2i-1〕）…
…(11) ただしa_i＝exp（jπ／2ⁱ）、a_i ^k＝e^j〓とし 〔e^j〓〕＝１、０Θ＜π／４のとき ＝１＋ｊ、π／４Θ＜π／２のとき ＝ｊ、π／２Θ＜3π／４のとき ＝−１＋ｊ、3π／４Θ＜πのとき さらにフーリエスペクトラムの近似度を高める
ことのできる16値ウオルシユ関数を提案する。 すなわち、第４図に示した （１、１＋１／２ｊ、１＋ｊ、１／２＋ｊ、ｊ、−１
／２ ＋ｊ、−１＋ｊ、−１＋１／２ｊ、−１、−１−１／２
ｊ、 −１−ｊ、−１／２−ｊ、−ｊ、１／２−ｊ、１−ｊ、
１ −１／２ｊ）の16個の要素を持つ16値ウオルシユ関 数を提案する。 これによる関数系を用いる16値ウオルシユ変換
の演算は（±１／±１／２、±ｊ／±１／２ｊ）の積の 演算であるためシフタによる1/2化と加減算のみ
で実行可能である。具体的な計算方法は８値ウオ
ルシユ変換の方法と同様であり(11)式の代わりに(12)
式を用いる。 Di＝diag（１、〔a_i〕、〔a_i ²〕、…、〔a_i ^2i-1〕）…
…(12) ただし〔e^j〓〕＝１、０Θ＜π／８のとき ＝１＋１／２ｊ、π／８Θ＜π／４のとき ＝１＋ｊ、π／４Θ＜3π／８のとき ＝１／２＋ｊ、3π／８Θ＜π／２のとき ｊ＝、π／２Θ＜5π／８のとき ＝−１／２＋ｊ、5π／８Θ＜3π／４のとき ＝−１＋ｊ、3π／４Θ＜7π／８のとき ＝−１＋１／２ｊ、7π／８Θ＜πのとき 次に本発明の装置の具体的な構成を図面を参照
しながら説明する。 本発明の第１の実施例は第５図に示すように、
バツフアメモリ部１、多値ウオルシユ演算部２、
制御部３より構成され、(2)、(3)、(4)、(11)式による
８値ウオルシユ変換を実行する装置である。 始めに一般に複素数の時系列データがバツフア
メモリ部１へ入力され、一時記憶される。第８図
ａはｎ＝４の場合の計算の流れ図であり、この図
に従つた制御部３の制御信号により、第１段より
順に第ｎ段まで計算が進められる。第ｋ段の処理
は、第８図ａに示した第ｋ段の2^n-1個のバタフラ
イ演算を実行することであり、(2)式におけるP_k
の行列を乗することを意味している。 各段の処理はバツフアメモリ部１よりデータを
読み出し、バタフライ演算を行い、その結果は再
びバツフアメモリ部１へ書き込まれる。 バタフライ演算は第８図ｂに示すように y_i＝x_i＋x_j・a_k ……（13） y_j＝x_i−x_j・a_k ……（14） であり、第６図に示す多値ウオルシユ演算部２に
て求められる。 バタフライ演算では始めにx_i、x_jがバツフアメ
モリ部１より読み出され、x_iの実数部、虚数部が
レジスタ２０１，２０２へ、x_jの実数部、虚数部
がレジスタ２０３，２０４へそれぞれ一時格納さ
れる。 x_j・a_kの複素数乗算は次の４通りの加減算にて
実行される。 （Z_R＋jZ_I）＝（x_jR＋jx_jI）・a_kとすると、８値ウ
オルシユ変換の場合、 a₀＝a₁＝１、a₂＝a₃＝１＋ｊ、a₄＝a₅＝ｊ、a₆＝
a₇＝−１＋ｊとなることを考えると、 a₀＝a₁＝１のとき Z_R＝x_jR ……（15） Z_I＝x_jI ……（16） a₂＝a₃＝１＋ｊのとき Z_R＝x_jR−x_jI ……（17） Z_I＝x_jR＋x_jI ……（18） a₄＝a₅＝ｊのとき Z_R＝−x_jI ……（19） Z_I＝x_jR ……（20） a₆＝a₇＝−１＋ｊのとき Z_R＝−x_jR−x_jI ……（21） Z_I＝x_jR−x_jI ……（22） となる。 これらの演算は制御部３の制御信号のもとでス
イツチ２１１と加減算器２２１と２２２により求
められる。すなわちスイツチ２１１は加減算器２
２１と２２２の入力をx_jR、x_jI、０のどれかを選
択し、加減算器２２１と２２２は加算又は減算又
は加算と符号反転を行い前記の（15）〜（22）式
の演算を行う。 つづいて（13）、（14）式の加算および減算は、
実数部、虚数部に分けて実行され、加算器２３１
と２３２および減算器２３３と２３４にて求めら
れる。得られた結果y_i、y_jはバツフアメモリ部１
のx_i、x_jが記憶されていた場所へ書かれる。 最終段である第ｎ段の処理の結果が、８値ウオ
ルシユ変換された８値ウオルシユスペクトルF_iで
ある。 次に本発明の第２の実施例は、(2)、(3)、(4)、(12)
式による16値ウオルシユ変換を実行する装置であ
り、第１の実施例の多値ウオルシユ演算部２を第
７図に示す構成へ変更したものである。計算は第
１の実施例と同様に進められる。 第２の実施例と第１の実施例の異なる点は、制
御部３が第９図に示した計算の流れ図に従つて制
御信号を出力することとバタフライ演算における
乗算要素a_kの値が８種類あることである。第２の
実施例におけるバタフライ演算は第７図に示す多
値ウオルシユ演算部２にて求められる。バタフラ
イ演算では始めにx_i、x_jがバツフアメモリ部１よ
り読み出され、x_iの実数部、虚数部がレジスタ２
０１，２０２へ、x_jの実数部、虚数部がレジスタ
２０３，２０４へそれぞれ一時格納される。 ところで、x_j・a_kの複素数乗算は次の８通りの
演算にて実行される。 （Z_R＋jZ_I）＝（x_jR＋jx_jI）・a_kとし、 a₀＝１のとき Z_R＝x_jR ……（23） Z_I＝x_jI ……（24） a₁＝１＋１／２ｊのとき Z_R＝x_jR−１／２x_jI ……（25） Z_I＝１／２x_jR＋x_jI ……（26） a₂＝１＋ｊのとき Z_R＝x_jR−x_jI ……（27） Z_I＝x_jR＋x_jI ……（28） a₃＝１／２＋ｊのとき Z_R＝１／２x_jR−x_jI ……（29） Z_I＝x_jR−１／２x_jI ……（30） a₄＝ｊのとき Z_R＝−x_jI ……（31） Z_I＝x_jR ……（32） a₅＝−１／２＋ｊのとき Z_R＝−１／２x_jR−x_jI ……（33） Z_I＝x_jR−１／２x_jI ……（34） a₆＝−１＋ｊのとき Z_R＝−x_jR−x_jI ……（35） Z_I＝x_jR−x_jI ……（36） a₇＝−１＋１／２ｊのとき Z_R＝−x_jR−１／２x_jI ……（37） Z_I＝１／２x_jR−x_jI ……（38） これらの演算は制御部３の制御信号のもとで、
シフタ２４１と２４２スイツチ２１２と加減算器
２２１と２２２により求められる。すなわち、シ
フタ２４１と２４２は１ビツト右シフトすること
により１／２x_jRおよび１／２x_jIを求めることができ、 スイツチ２１２は加減算器２２１と２２２の入力
をx_jR、x_jI、１／２x_jR、１／２x_jI、０のどれかを選択 し、加減算器２２１と２２２は加算又は減算又は
加算と符号反転を行い、前記の（23）〜（38）式
の演算を行う。 つづいて（13）、（14）式の加算および減算は、
実数部、虚数部に分けて実行され、加算器２３１
と２３２および減算器２３３と２３４にて求めら
れる。得られた結果y_i、y_jはバツフアメモリ部１
のx_i、x_jが記憶されていた場所へ書かれる。 最終段である第ｎ段の処理の結果が、16値ウオ
ルシユ変換された16値ウオルシユスペクトルF_iで
ある。 次に第１０図は本発明の第３の実施例のブロツ
ク図であり、(2)式の行列Ａを直接乗算して求める
８値ウオルシユ変換装置であり、フーリエスペク
トラムを求める１方法であるDFTと同様な方法
で求める。今、(2)式の行列Ａのｋ行ｉ列の要素を
a_kiとし、Ｘ＝（x₀、x₁、…、x_i、…、x_2o-1）とす
れば F_k＝_2o-1 〓ⁱ⁼⁰ a_ki・x_i ……（39） のようにa_kiと入力時系列x_iとの積和を求めること
により多値ウオルシユスペクトルF_kが求められ
る。 ここでＡ＝P₁・P₂…・P_oであるのでa_kiは８値
ウオルシユ変換の場合第３図に示した（１、１＋
ｊ、ｊ、−１＋ｊ、−１、−１−ｊ、−ｊ、１−ｊ）
の８個の内の１つである。従つて（39）式の積は
加減算器にて演算できる。始めに第１１図に示す
タイムチヤートに従つて制御部３よりの信号Clが
アキユムレータ２６１と２６２をクリアする。続
いて０より2ⁿ−１まで変化する信号ｉに従つてバ
ツフアメモリ部より入力時系列データx_iを順次読
み出す。ここで多値ウオルシユ演算部２は、第１
２図に示すように実部用アキユムレータ２６１と
虚部用アキユムレータ２６２と、実部用加減算器
２５１と虚部用加減算器２５２と、データx_iまた
はゼロを実部用加減算器２５１または虚部用加減
算器２５２へ入力するスイツチ２１３より構成さ
れ、制御部の制御により次の８通りの動作をす
る。実部用アキユムレータ２６１と虚部用アキユ
ムレータ２６２の内容をそれぞれACC_R、ACC_Iと
すると a_ki＝１のとき ACC_R＋x_i→ACC_R ACC_I＋０→ACC_I a_ki＝１＋ｊのとき ACC_R＋x_i→ACC_R ACC_I＋x_i→ACC_I a_ki＝ｊのとき ACC_R＋０→ACC_R ACC_I＋x_i→ACC_I a_ki＝−１＋ｊのとき ACC_R−x_i→ACC_R ACC_I＋x_i→ACC_I a_ki＝−１のとき ACC_R−x_i→ACC_R ACC_I−０→ACC_I a_ki＝−１−ｊのとき ACC_R−x_i→ACC_R ACC_I−x_i→ACC_I a_ki＝−ｊのとき ACC_R＋０→ACC_R ACC_I−x_i→ACC_I a_ki＝１−ｊのとき ACC_R＋x_i→ACC_R ACC_I−x_i→ACC_I の演算を行うようスイツチ２１３と加減算器２５
１と２５２が制御される。 信号ｉが2ⁿ−１となつた時アキユムレータ２６
１と２６２に多値ウオルシユスペクトラムのｋ次
項であるF_kの実部と虚部がそれぞれ得られる。 次に第４の実施例は（39）式に従つてa_kiと入
力時系列x_iとの積和を直接求める16値ウオルシユ
変換装置である。（39）式のa_kiは16値ウオルシユ
変換の場合第４図に示した（１、１＋１／２ｊ、１ ＋ｊ、１／２＋ｊ、ｊ、−１／２＋ｊ、−１＋ｊ、−１
＋ １／２ｊ、−１、−１−１／２ｊ、−１−ｊ、−１／２
−ｊ、− ｊ、１／２−ｊ、１−ｊ、１−１／２ｊ）の16個の内の １つであり、（39）式の積はシフタと加減算器に
て求められる。このため、第４の実施例における
多値ウオルシユ演算部２は、第３の実施例の多値
ウオルシユ演算部２を第１３図に示すようにスイ
ツチ２１４の前にシフタ２４３を挿入した構成で
ある。第３の実施例と同様にして制御部３の制御
により次の16通りの動作をする。

【表】 ２
２
の演算を行うようスイツチ２１４とシフタ２４３
と加減算器２５１と２５２が制御される。シフタ
２７は１／２x_iを出力するものである。信号ｉが2ⁿ −１となつた時アキユムレータ２６１と２６２に
多値ウオルシユスペクトラムF_kの実部と虚部が
それぞれ得られる。 以上、本発明を実施例に基づき説明したが、こ
れらの記載は本発明の範囲を限定するものではな
い。特に本発明の実施例ではFFTアルゴ リズ
ムとして、入力時系列を逆２進順へ並びかえ、
P₁よりP_oへ乗算し、正順序に結果を得る方法で
あるが、入力時系列をそのままの順でP^T _oよりP^T ₁
を乗算し、結果が２進逆順に得る方法も採用でき
ることは明白である。ここまでに８値、16値ウオ
ルシユ変換について説明したが、８値、16値の拡
張として第４図に示した原点を中心とした単位正
方形上の点を32値、64値…等用いる多値ウオルシ
ユ関数が考えられ、これらはシフタによる1/2、
１／４、…等と加減算によつて求められることは明
白である。

【図面の簡単な説明】

第１図はウオルシユ変換行列とウオルシユ関数
を示した図であり、第２図は本発明の多値ウオル
シユ関数の関数値を表示した図であり、第３図は
８値ウオルシユ関数の関数値を表示した図であ
り、第４図は16値ウオルシユ関数の関数値を表示
した図であり、第５図は本発明の第１および第２
の実施例のブロツク図であり、第６図は第１の実
施例の多値ウオルシユ演算部２のブロツク図であ
り、第７図は第２の実施例の多値ウオルシユ演算
部２のブロツク図であり、第８図ａは第１の実施
例の計算の流れ図であり、第８図ｂはバタフライ
演算の計算の流れ図であり、第９図は第２の実施
例の計算の流れ図であり、第１０図は第３および
第４の実施例のブロツク図であり、第１１図は第
３および第４の実施例における制御信号のタイム
チヤートであり、第１２図は第３の実施例の多値
ウオルシユ演算部２のブロツク図であり、第１３
図は第４の実施例の多値ウオルシユ演算部２のブ
ロツク図である。 第５図、第６図、第７図、第１０図、第１２
図、第１３図において、１はバツフアメモリ部、
２は多値ウオルシユ演算部、３は制御部、２０
１，２０２，２０３，２０４はレジスタ、２１
１，２１２，２１３，２１４はスイツチ、２２
１，２２２，２５１，２５２は加減算器、２３
１，２３２は加算器、２３３，２３４は減算器、
２４１，２４２，２４３はシフタ、２６１，２６
２はアキユムレータである。

Claims (1)

1. 【特許請求の範囲】 １ ウオルシユ関数を多値化かつ複素数化した多
   値ウオルシユ関数による変換を入力時系列信号に
   行なう多値ウオルシユ変換装置であつて、入力時
   系列データを保持するバツフアメモリ部と、前記
   バツフアメモリ部より読み出されたデータと制御
   部より与えられる複素定数とを乗算する多値ウオ
   ルシユ演算部と、前記多値ウオルシユ演算部へ複
   素平面の単位正方形の各辺を2ⁿ（ｎは自然数）分
   割した点の複素数を与え前記バツフアメモリ部と
   多値ウオルシユ演算部を制御する制御部を持つこ
   とを特徴とする多値ウオルシユ変換装置。 ２ 前記多値ウオルシユ演算部における複素定数
   との乗算を加減算器より構成する特許請求の範囲
   第１項記載の多値ウオルシユ変換装置。 ３ 前記多値ウオルシユ演算部における複素定数
   との乗算を加減算器およびシフタより構成する特
   許請求の範囲第１項記載の多値ウオルシユ変換装
   置。