JP2574312B2 - 高速アダマ−ル変換装置 - Google Patents

Description

【発明の詳細な説明】

産業上の利用分野 本発明は、既存のデバイスで構成し得る高速かつ経済
的な高速アダマール変換装置に関する。 従来の技術 画像や音声等のアナログ信号を処理する際には、FFT
（高速フーリェ変換）やFHT（高速アダマール変換）等
の直交変換の手法が一般的に用いられている。そして、
これら直交変換のアルゴリズムも種々提案され、それな
りの効果を上げているが、高速性と経済性を両立させる
という点については、必ずしも十分とは言えない。 まず、この発明の高速アダマール変換装置の理解を助
けるために、その第一のアルゴリズムの一種を８次の場
合を例にとって、第10図の流れ図に基づいて説明する。 この図に於いて X₀（０）〜X₇は被変換入力、 X₃（０）〜X₃（７）は変換された出力を示し、X_h-1と
X_hは第11図に示す関係により結ばれる。X₃（０）〜X
₃（７）を更に交番数順に並べるためには、X₃（ｉ）に
於けるｉを２進法で表現し、ビットの順序を逆に並べ換
えたものを交番２進法で読み、その値を新しい番号とす
ればよい。例えば、ｉ＝011であれば、110を交番２進法
であればX₃（ｉ）は交番数４の成分を表すことになる。 また、X₃（０）〜X₃（７）そのものが交番数順に並ぶ
ように入力X₀（０）〜X₀（７）の順序の並べ換えてから
入力する方法もある。即ち、X₀（ｉ）に於けるｉを２進
法で表現し、ビットの順序を逆に並び換えたものを交番
２進法で読み、その値をｊとするとき、前記X₀（ｊ）を
ｉ番目の位置に移すことによって並べ換えた系列を入力
とすれば、その時得られるX₃（０）〜Ｘ（７）は交番数
順になっている。例えば、X₀（３）はｉ＝011であるか
ら上記説明に従えば、ｊ＝４となるのでX₃（３）をY
₀（４）で置換えることになる。 次数ｎ＝2^m（ｍ＝1,2,…）の場合も全く同様の流れ図
で実行することができ、これは次式で表わせる。 但し、ｉ＝0,1,2,…,n−１ ｈ＝1,2,…,m ｐ＝0,1,2,…,2^h-1−１ このアルリズムの特徴は、第10図からも明らかなよう
に、ｈ段目の変換におけるX_h（ｉ）,X_h（ｊ）は（ｈ−
１）段目に於けるX_h-1（ｉ）とX_h-1（ｊ）から求めるこ
とができ、以後X_h-1（ｉ）,X_h-1（ｊ）なる値は使用し
ていないから、X_h（ｉ）の記憶場所としてX_h-1（ｉ）と
同じ場所を使用することが出来る点にある。即ち、X
_h（ｉ）が求まるとX_h-1（ｉ）を記憶していた場所の内
容をX_h（ｉ）なる値に書き換えることが出来るから、ｎ
次の高速アダマール変換を求めるための変換の途中段階
で必要とする記憶場所はｎ個の数値を記憶する場所のみ
でよい。 同様な特徴を有する第２のアルゴリズムを第12図に示
す。この場合は、次式で表わせる。 但し、ｉ＝0,1,2,…,n−１ ｈ＝1,2,3,…,m ｐ＝0,1,2,…,2^m-h−１ 第13図はこの様なアルゴリズムをハード化した従来の
高速アダマール変換装置の概略ブロックを示すものであ
る（特公昭62−14133号参照）。 図中、30は変換の途中段階でデータを記憶するRAM、3
1はRAM30へ入力するデータを選択する入力データ選択回
路、32はRAM30のアドレスを選択するアドレス選択回
路、33は変換途中のデータのアドレスを発生するアドレ
ス発生回路、34,35はRAM30のデータを一時的に保存する
ラッチ、36はレジスタ34,35のデータを加減算する加算
回路である。また、40は高速アダマール変換されるべき
被変換データ、41は変換結果の出力を示す変換データ、
42はデータの書込読出時に必要とするアドレス信号であ
る。また、43はこの変換装置の動作モードを切換える書
込読出変換切換信号、44は加減算器36の加算モードまた
は減算モードを指定し、アドレス発生回路33にそのモー
ドを伝える加減算制御信号である。 以上の様に構成された高速アダマール変換装置につい
て、以下その動作について説明する。 最初は、書込読出変換切換信号43により、書込モード
となり、入力データ選択回路31を被変換データ40を選択
する様にし、アドレス選択回路32をアドレス（データ書
込時）42を選択する様にして、被変換データ40をRAM30
に書込む。 次に変換モードとなり、第10図または第12図のアルゴ
リズムにより、データは逐次変換される。即ち、変換途
中のアドレスをアドレス発生回路33で発生させ、このア
ドレスに対応したデータをRAM30より読出し、ラッチ3
4、35に一時保存し、加減算回路36にデータを送り、加
減算制御信号44により、加算または減算を行い、その結
果を入力データ選択回路31を経て、RAM30に書込む。こ
のサイクルをｎ×ｍ回繰返して、最後に書込読出変換切
換信号43により、アドレス選択回路32をアドレス（デー
タ読出時）42を選択する様にして、変換データ41を出力
して変換を完了する。 発明が解決しようとする問題点 しかし、ここで従来例の構成からわかる様に、記憶装
置RAM30のデータ線が入出力各１ワードしかない為、ア
ドレス操作により変換を行う。この為、変換サイクル数
がｎ×ｍ回と多くなり、画像データの如き高速データを
リアルタイムで処理することが困難となる問題点を有し
ていた。 本発明は、上記問題点に鑑み、高速アダマール変換に
於ける変換サイクル数をｍ回に減少せしめ、画像データ
の如き高速データをリアルタイムで処理できる高速アダ
マール変換装置を提供することを目的とするものであ
る。 問題点を解決するための手段 この目的を達成するために、本発明の高速アダマール
変換装置は記憶装置に夫々が各１ワードの入出力線を持
つｎ個のレジスタ群を使用し、データ選択操作と（n/
2）個の加減算器群により高速アダマール変換を行うこ
とを特徴とする。 作用 この構成によって、従来ｎ×ｍ回要していた変換サイ
クルをｍ回と大幅に減少せしめ、画像データの如き高速
データを既存のデバイスにより、リアルタイムで、経済
的に高速アダマール変換できることになる。 実 施 例 本発明は第12図のアルゴリズムを採用しており、以下
その一実施例を画面を参照しながら説明する。 第１図は本発明の一実施例（８次高速アダマール変換
装置）の概略ブロック図を示すものである。図中、１は
データ選択信号により、被変換データ群X₀（０）〜X
₀（７）と変換途中のデータ群S₀〜S₇を選択するデータ
セレクタ群D₀〜D₇、２はレジスタクロックC_Rにより前記
データセレクタ群１の出力を記憶するレジスタ群R₀〜
R₇、３はデータ選択ビットB_k〔ｑ〕（ｋ＝1,2,…,6:q＝
0,1,2）により前記レジスタ群２の出力を選択するマル
チプレクサ群M₁〜M₆、４は加減算器A₀被加減算入力
（＋）は前記レジスタ群２のレジスタR₀の出力に、また
加減算器A₃加減算入力（−）はレジスタR₇の出力に夫々
直接接続され、他の加減算器A₀〜A₃の被加減算入力
（＋）は前記マルチプレクサ群のM_k（ｋ＝2,4,6）の出
力に、加減算入力（−）はM_k（ｋ＝1,3,5）の出力に接
続されるか加減算器群A₀〜A₃、５は前記加減算器群４の
A_l（ｌ＝0,1,2,3）の出力をラッチL_2lL_2l+1に入力し、
その出力S₀〜S₇を前記データセレクタ群１に入力するラ
ッチ群L₀〜L₇である。 以上のように構成された８次高速アダマール変換装置
について、第２図のタイミング図を用いながら、以下そ
の動作について説明する。 まず初期状態に於てはデータセレクタ群１はデータ選
択信号Ｄにより、被変換データX₀（０）〜X₀（７）を選
択する。データセレクタ群１の出力はレジスタロックC_R
の立ち上りよりレジスタ群２に記憶される。引続いて変
換状態に入り、第12図の流れ図でも明らかな様に、レジ
スタR₀の出力は常に被加減数になるので、加減算器A₀の
被加減入力（＋）に直接入力され、またレジスタR₇の出
力は常に加減数になるので、加減算器A₃の加減数入力
（−）に直接入力される。また残りのレジスタR₁〜R₆の
出力はマルチプレクサ群３に供給され、データ選択ビッ
トB_k〔ｑ〕（ｋ＝12,…6,;q＝0,1,2）により、マルチプ
レクサ群３の出力は夫々レジスタR₁〜R₆を選択する。第
１図に示す如く、マルチプレクサM_k（ｋ＝1,3,5）の出
力は残りの加減算器群４の加減数入力（−）に、またマ
ルチプレクサM_k（ｋ＝2,4,6）の出力は被加減数入力
（＋）に供給される。加減算器群４は第２図の加減算制
御信号Ｐの（＋）と示す期間に加算モードとなり、その
出力はラッチL_k（ｋ＝0,2,4,6）に供給され、第２図の
偶数ラッチクロックC₊の立ち上りにより一時保存され
る。 一方、加減算制御信号Ｐの（−）と示す期間に減算モ
ードとなり、その出力はラッチL_k（ｋ＝1,3,5,7）に供
給され、奇数ラッチクロックC_-の立上りにより一時保存
される。ラッチ群５の出力S₀〜S₇はデータセレクタ群１
に供給され、データセレクタ群１はデータ選択信号によ
り、ラッチ群５の出力S₀〜S₇を選択し、レジスタ群２に
供給して、第一の変換サイクルを終了する。この変換サ
イクルをｍ回繰返えすことにより、高速アダマール変換
が完了し、第２図のレジスタクロックC_Rの最後のパルス
の立上りにより、レジスタ群２は変換データ群X₃（０）
〜X₃（７）を記憶し、その出力により変換データ群X
₃（０）〜X₃（７）を得る。 ここで、マルチプレクサ群M₁〜M₆のデータ選択ビット
B_k〔ｑ〕（ｋ＝１〜6;q＝0,1,2）を求めるアルゴリズム
を第６図に示す。第６図に於て、A_k〔ｑ〕（ｋ＝１〜6;
q＝0,1,2）はマルチプレクサM_kを添字ｋを２進数で表現
した固定ビットである。例えば、ｋ＝３とすれば、２進
数表現では011となるから、A₃

〔０〕＝1,A₃〔１〕＝1,A
₃〔２〕＝０となる。第６図からも明らかな様に、第12
図のX₀→X₁の変換時にはB_k〔ｑ〕＝Ak〔ｑ〕となり、X_h
→X_h+1（ｈ＝0,1,2）の変換時には、０番目のビット位
置とｈ番目のビット位置を変換することにより、B
_k〔ｑ〕（ｋ＝１〜6;q＝0,1,2）を得ることが出来る。
これを真理値図にしたのが第７図である。第７図に於い
て、カウンタ出力C₀,C₁、デコーダ出力a,b,cはデータ選
択ビットB_k〔ｑ〕（ｋ＝１〜6;q＝0,1,2）を生成する為
に設けられたもので、本実施例の場合、前記カウンタは
３進カウンタである。 また、16次高速アダマール変換に於いても同様のこと
が言え、データ選択ビットB_k〔ｑ〕（ｋ＝１〜14;q＝0,
1,2,3）の生成アルゴリズムを第８図に、また、その真
理値図を第９図に示す。第8,9図に於ける各変数は第6,7
図に於る各変数と同様の意味を持つ。このような手段に
よりｎ次（ｎ＝2^m）の高速アダマール変換に於ても同様
のデータ選択ビットの生成アルゴリズムが成立する。 このアルゴリズムを本実施例（８次高速アダマール変
換装置）に於いてハードウェアで構成したのが第３回で
ある。図中、６は３進カウンタ、７はデューダ、８〜16
はAND回路、17〜19はOR回路である。またC_Tは３進カウ
ンタクロック、Ｒは３進カウンタリセット信号、C₀,C₁
は３進カウンタ出力、a,b,cはデコーダ出力である。 以上の如く構成されたデータ選択ビット発生回路の動
作について、第２図のタイミング図を用いて以下説明す
る。３進カウンタ６は３進カウンタリセット信号により
リセットされ、その出力はC₀＝0,C₁＝０となり、デコー
ダ７に供給される。デコーダ７はこのC₀,C₁をデコード
し、ａ＝1,b＝0,c＝０となる。従って、第３図から明ら
かな様にB_k〔ｑ〕＝A_k〔ｑ〕（ｋ＝１〜6,q＝0,1,2）と
なる。引続いて、３進カウンタクロックの第一の立上り
で３進カウンタ出力はC₀＝1,C₁＝０となり、デコーダ出
力はａ＝0,b＝1,c＝０となって、B_k

〔０〕＝A_k〔１〕,B
_k〔１〕＝A_K

〔０〕,B_k〔２〕＝A_k〔２〕と０番目と１番
目のデータ選択ビットの位置が交換される。更に３進カ
ウンタクロックの最後の立合いで３進カウンタ出力はC₀
＝0,C₁＝１となり、デコーダ出力はａ＝0,b＝0,c＝１と
なり、 B_k

〔０〕＝A_k〔２〕,B_k〔１〕＝A_K

〔０〕,B_k〔２〕＝
A_k〔１〕となって、前記の状態より０番目と２番目のデ
ータ選択ビットの位置が変換される。 ここで本実施例の８次高速アダマール変換装置に於
て、第３図の回路は６個必要となるが、第４図の如く、 A_k〔ｑ〕（ｋ＝１〜6,q＝１〜２）は固定ビットである
ので、 B_k〔ｑ〕（ｋ＝１〜6,q＝0,1,2）は0,1あるいはデコ
ーダ出力a,b,の論理和で表現できるので、回路は大幅に
簡単化されて第５図の如くになる。図中、３進カウンタ
６およびデューダ７は第３図の同じ動作をし、20〜27は
OR回路である。なお、図中B₀〔ｑ〕（ｑ＝0,1,2）は全
て０となるから、常にレジスタR₀が選ばれ、 B₇〔ｑ〕（ｑ＝0,1,2）は全て１となるから、常にレ
ジスタR₇が選ばれるので、この点からもマレチプレクサ
M₀,M₇省略できる。 発明の効果 以上のように、本発明によれば、 ｎ次（ｎ＝2^m）の高速アダマール変換装置に於いて、従
来ｎ×ｍ回の変換サイクルを必要としたものが、ｍ回の
サイクルと大幅に短縮でき、画像データの如き高速デー
タをリアルタイムで取り扱うことが可能となり、その実
用的効果は大なるものである。

【図面の簡単な説明】

第１図は本発明の一実施例における高速アダマール変換
装置の概略ブロック図、第２図は第１図，第３図，第５
図に用いられる各種制御信号のタイミング図、第３図は
第１図におけるデータ選択ビット発生回路の回路図、第
４図は各データ選択ビットの論理説明図、第５図はデー
タ選択ビット発生回路の簡単化した回路図、第６図およ
び第８図はそれぞれ８次および16次の高速アダマール変
換装置に於ける本発明のデータ選択ビット生成のアルゴ
リズムを示すフローチャート、第７図および第９図はそ
れぞれ８次および16次の高速アダマール変換装置におけ
る本発明のデータ選択ビットの真理値説明図、第10図は
高速アダマール変換を行うためのアルゴリズムを示すフ
ローチャート、第11図は第10図および第12図の表記方法
を説明するための模式図、第12図は高速アダマール変換
を行うための他のアルゴリズムを示すフローチャート、
第13図は高速アダマール変換装置の従来例を示す概略ブ
ロック図である。 １……データセレクタ群、２……レジスタ群、３……マ
ルチプレクサ群、４……加減算器群、５……ラッチ群、
６……３進カウンタ、７……デコーダ。

Claims (2)

(57)【特許請求の範囲】
1. 【請求項１】ｎ次（ｎ＝2^m）の高速アダマール変換装置
   において、変換初期にはｎ個の被変換データ群を変換途
   中にはｎ個の変換途中のデータ群をそれぞれ選択するデ
   ータセレクタ群と、前記データセレクタの出力を記憶す
   るｎ個のレジスタ群とを備え、前記レジスタ群の０番目
   と（ｎ−１）番目のレジスタを除くレジスタ群の出力を
   それぞれｍビットのデータ選択ビットにより選択される
   （ｎ−２）個のマルチプレクサ群に入力し、前記レジス
   タ群の０番目のレジスタの出力を０番目の加減算器の被
   加減数入力に、ｎ番目のレジスタの出力を（（n/2）−
   １）番目の加減算器の加減数入力にそれぞれ直接入力
   し、前記マルチプレクサ群の偶数番目（2,4,6,…，｛ｎ
   −２））のマルチプレクサの出力を他の被加減数入力
   に、奇数番目（1,3,5,…，（ｎ−３））のマルチプレク
   サの出力を他の加減数入力にそれぞれ入力する（n/2）
   個の加減算器群を備え、前記加減算器群は加減算制御信
   号により加算モードまたは減算モードとなり、加算モー
   ド中には前記加減算器群の出力を偶数番目（0,2,4,…，
   （ｎ−２））のラッチに一時保存し、減算モード中には
   奇数番目（1,3,5,…，（ｎ−１））のラッチに一時保存
   するラッチ群を備え、前記ラッチ群の出力を変換途中の
   データとして前記データセレクタに入力し、このサイク
   ルをｍ回繰返すことにより変換データ群を前記レジスタ
   群の出力より得るようにしたことを特徴とする高速アダ
   マール変換装置。
2. 【請求項２】（ｎ−２）個のマルチプレクサ群のそれぞ
   れｍビットのデータ選択ビットをｈ番目（ｈ＝1,2,…,
   m）番目の変換サイクルにおいて決定するに際し、ｋ番
   目（ｋ＝1,2,3,…，（ｎ−２））のマルチプレクタ番号
   ｋを２進数ｍビットで表現し、０番目のビット位置とｈ
   番目のビット位置を交換することにより、ｈ番目の変換
   サイクルに於けるデータ選択線ビットを得るようにした
   ことを特徴とする特許請求の範囲第１項記載の高速アダ
   マール変換装置。