(57)【特許請求の範囲】
【請求項１】
所定のデータ入力タイミングでそれぞれ入力される量子化ビット数ｐからなる入力データあるいは（ｐ＋ｌｏｇ2ｎ）（ｎは自然数）ビットのシリアルデータのいずれか一方を順次１ビットずつ所定のシフトタイミングでシフトする第１〜第ｎのシフトレジスタ部と、
第（２ｉ−１）（ただし、１≦ｉ≦ｎ／２、ｉは自然数）および第（２ｉ）のシフトレジスタ部によって１ビットずつ順次シフト出力された１ビットデータの加算および減算を行って、加算結果および減算結果をそれぞれ第ｉおよび第（ｉ＋ｎ／２）のシフトレジスタ部に対して前記シリアルデータとして出力する第１〜第（ｎ／２）のバタフライ演算部と、
これら第１〜第（ｎ／２）のバタフライ演算部それぞれの入力元および出力先を前記シフトによりデータが１周するたびに切り替える入力元出力先切替スイッチ
とを具備することを特徴とする高速アダマール変換器。
【請求項２】
前記バタフライ演算部は、第（２ｉ−１）のシフトレジスタ部によってシフト出力された１ビットデータと第（２ｉ）のシフトレジスタ部によってシフト出力された１ビットデータと前回の前記シフトタイミングで生成されたキャリーとを加算する加算手段と、この加算手段によって生成されたキャリーを１シフトタイミングだけ遅延する第１の遅延手段と、第（２ｉ−１）のシフトレジスタ部によってシフト出力された１ビットデータから第（２ｉ）のシフトレジスタ部によってシフト出力された１ビットデータと前回の前記シフトタイミングで生成されたボローを減算する減算手段と、この減算手段によって生成されたボローを１シフトタイミングだけ遅延する第２の遅延手段とを備えることを特徴とする請求項１記載の高速アダマール変換器。
【請求項３】
前記シフトレジスタ部それぞれは、所定のデータ出力タイミングで前記シフトレジスタ部でシフトされる（ｐ＋ｌｏｇ2ｎ）ビットを選択出力する（ｐ＋ｌｏｇ2ｎ）個の出力スイッチを備えることを特徴とする請求項１または請求項２記載の高速アダマール変換器。
【請求項４】
前記第１および第２の遅延手段は、（ｌｏｇ2ｎ×（ｐ＋ｌｏｇ2ｎ））シフトタイミングごとに初期化されるものであることを特徴とする請求項２または請求項３記載の高速アダマール変換器。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、高速アダマール変換器に関わり、例えば符号分割多元接続方式の移動体通信システムにおける拡散符号の直交変調に好適な高速アダマール変換器に関する。
【０００２】
【従来の技術】
次世代の移動体通信の標準方式として注目されている符号分割多元接続（Code Division Multiple Access：以下、ＣＤＭＡと略す。）方式の移動体通信システムの移動体通信端末では、スペクトラム拡散技術により同じ周波数帯域の信号を使って同時に複数チャネルの通信を行う。これは、例えばチャネルごとに相互相関関数が“０”になるウォルッシュ（Walsh）符号を使用したウォルッシュ直交変調を行うことにより実現される。このウォルッシュ符号は、“＋１”と“−１”の要素からなるアダマール変換（Hadamard transform）行列により表現できる。ウォルッシュ直交変調は、このアダマール変換行列を用いたアダマール変換を行うことによって、バタフライ演算に基づく高速な演算処理が可能となる。このようなバタフライ演算に基づく高速なアダマール変換を行うものを、高速アダマール変換（Fast Hadamard Transform：ＦＨＴ）器と呼ぶ。
【０００３】
図７は、従来の高速アダマール変換器の構成の概要を表わしたものである。ここでは、量子化ビット数をｐとし、８次（次元数ｎが８）の高速アダマール変換を行うものとする。この高速アダマール変換器は、８次元の入力ベクトルＸの各成分データｘ1〜ｘ8ごとにビット直列入力され、それぞれ第１〜第８の入力ラッチ１０1〜１０8でラッチされる。これら第１〜第８の入力ラッチ１０1〜１０8は、図示しない入力ラッチ出力イネーブル信号によって、その出力端子がハイインピーダンスにされる。第１および第２の入力ラッチ１０1、１０2の出力端子は、ともに（ｐ−１＋ｌｏｇ2ｎ）加算器１１1と（ｐ−１＋ｌｏｇ2ｎ）減算器１２1とに接続される。同様に第３および第４の入力ラッチ１０3、１０4の出力端子、第５および第６の入力ラッチ１０5、１０6の出力端子、第７および第８の入力ラッチ１０7、１０8の出力端子は、それぞれ（ｐ−１＋ｌｏｇ2ｎ）加算器１１2と（ｐ−１＋ｌｏｇ2ｎ）減算器１２2、（ｐ−１＋ｌｏｇ2ｎ）加算器１１3と（ｐ−１＋ｌｏｇ2ｎ）減算器１２3、（ｐ−１＋ｌｏｇ2ｎ）加算器１１4と（ｐ−１＋ｌｏｇ2ｎ）減算器１２4とに接続される。
【０００４】
（ｐ−１＋ｌｏｇ2ｎ）加算器１１1の出力端子は、第１の出力ラッチ１３1と第１のセレクタ無ラッチ１４1に接続される。（ｐ−１＋ｌｏｇ2ｎ）減算器１２1の出力端子は、第５の出力ラッチ１３5と第１のセレクタ有ラッチ１５1に接続される。（ｐ−１＋ｌｏｇ2ｎ）加算器１１2の出力端子は、第２の出力ラッチ１３2と第２のセレクタ有ラッチ１５2に接続される。（ｐ−１＋ｌｏｇ2ｎ）減算器１２2の出力端子は、第６の出力ラッチ１３6と第３のセレクタ有ラッチ１５3に接続される。（ｐ−１＋ｌｏｇ2ｎ）加算器１１3の出力端子は、第３の出力ラッチ１３3と第４のセレクタ有ラッチ１５4に接続される。（ｐ−１＋ｌｏｇ2ｎ）減算器１２3の出力端子は、第７の出力ラッチ１３7と第５のセレクタ有ラッチ１５5に接続される。（ｐ−１＋ｌｏｇ2ｎ）加算器１１4の出力端子は、第４の出力ラッチ１３4と第６のセレクタ有ラッチ１５6に接続される。（ｐ−１＋ｌｏｇ2ｎ）減算器１２4の出力端子は、第８の出力ラッチ１３8と第２のセレクタ無ラッチ１４2に接続される。
【０００５】
これら（ｐ−１＋ｌｏｇ2ｎ）加算器１１1〜１１4および（ｐ−１＋ｌｏｇ2ｎ）減算器１２1〜１２4は、各１個でバタフライ演算器を構成する。
【０００６】
第１および第２のセレクタ無ラッチ１４1、１４2は、図示しないセレクタラッチ信号により（ｐ−１＋ｌｏｇ2ｎ）加算器あるいは（ｐ−１＋ｌｏｇ2ｎ）減算器の出力をラッチする。また、第１および第２のセレクタ無ラッチ１４1、１４2の出力端子は、それぞれ第１および第８の入力ラッチ１０1、１０8の出力端子に接続され、それぞれ図示しないセレクタ有無ラッチ出力イネーブル信号によって、ハイインピーダンスにされる。第１〜第６のセレクタ有ラッチ１５1〜１５6は、図示しないセレクタラッチ信号により（ｐ−１＋ｌｏｇ2ｎ）加算器あるいは（ｐ−１＋ｌｏｇ2ｎ）減算器の出力をラッチする。これら第１〜第６のセレクタ有ラッチ１５1〜１５6は、それぞれ２つの出力端子Ａ、Ｂを有し、図示しないセレクタ有ラッチ切替信号によりラッチしているデータを選択出力する。また、これらの出力端子は、第２〜第７の入力ラッチ１０2〜１０7の出力端子に接続され、それぞれ上述したセレクタ有無ラッチ出力イネーブル信号によって、ハイインピーダンスにされる。
【０００７】
第１〜第８の出力ラッチ１３1〜１３8は、それぞれ図示しない出力ラッチ信号により、対応する（ｐ−１＋ｌｏｇ2ｎ）加算器あるいは（ｐ−１＋ｌｏｇ2ｎ）減算器の出力をラッチし、８次元の出力ベクトルＹの各成分データｙ1〜ｙ8として出力する。
【０００８】
図８は、図７に示した高速アダマール変換器の動作タイミングを表わしたものである。まずタイミングｔ1の入力ラッチクロックにより、第１〜第８の入力ラッチ１０1〜１０8は、８次元の入力ベクトルＸの各成分データをラッチする（図８（ａ））。このとき入力ラッチ出力イネーブル信号を“Ｌ”（同図（ｃ））、セレクタ有無ラッチ出力イネーブル信号を“Ｈ”（同図（ｅ））にして、各入力ラッチに格納されたラッチデータを、（ｐ−１＋ｌｏｇ2ｎ）加算器１１1〜１１4あるいは（ｐ−１＋ｌｏｇ2ｎ）減算器１２1〜１２4に対して出力させる。また、セレクタ有ラッチ切替信号により、第１〜第６のセレクタ有ラッチ１５1〜１５6の出力端子Ａを選択させている（同図（ｄ））。このとき各（ｐ−１＋ｌｏｇ2ｎ）加算器あるいは（ｐ−１＋ｌｏｇ2ｎ）減算器が出力するフィードバックデータは、次のようになる。
【０００９】
ｗ1（ｔ1）＝ｘ1＋ｘ2
ｗ2（ｔ1）＝ｘ1−ｘ2
ｗ3（ｔ1）＝ｘ3＋ｘ4
ｗ4（ｔ1）＝ｘ3−ｘ4
ｗ5（ｔ1）＝ｘ5＋ｘ6
ｗ6（ｔ1）＝ｘ5−ｘ6
ｗ7（ｔ1）＝ｘ7＋ｘ8
ｗ8（ｔ1）＝ｘ7−ｘ8
【００１０】
次にタイミングｔ2のセレクタラッチにより、フィードバックデータｗ1（ｔ1）とｗ8（ｔ1）とが第１および第２のセレクタ無ラッチ１４1、１４2に、フィードバックデータｗ2（ｔ1）〜ｗ7（ｔ1）が第１〜第６のセレクタ有ラッチ１５1〜１５6にそれぞれ格納される（同図（ｆ））。このとき入力ラッチ出力イネーブル信号を“Ｈ”（同図（ｃ））、セレクタ有無ラッチ出力イネーブル信号を“Ｌ”（同図（ｅ））にして、第１および第２のセレクタ無ラッチ１４1、１４2と第１〜第６のセレクタ有ラッチ１５1〜１５6のラッチデータを、（ｐ−１＋ｌｏｇ2ｎ）加算器１１1〜１１4あるいは（ｐ−１＋ｌｏｇ2ｎ）減算器１２1〜１２4に対して出力させる。このとき各（ｐ−１＋ｌｏｇ2ｎ）加算器あるいは（ｐ−１＋ｌｏｇ2ｎ）減算器が出力するフィードバックデータは、次のようになる。
【００１１】
ｗ1（ｔ2）＝ｗ1（ｔ1）＋ｗ3（ｔ1）＝ｘ1＋ｘ2＋ｘ3＋ｘ4
ｗ2（ｔ2）＝ｗ1（ｔ1）−ｗ3（ｔ1）＝ｘ1＋ｘ2−ｘ3−ｘ4
ｗ3（ｔ2）＝ｗ2（ｔ1）＋ｗ4（ｔ1）＝ｘ1−ｘ2＋ｘ3−ｘ4
ｗ4（ｔ2）＝ｗ2（ｔ1）−ｗ4（ｔ1）＝ｘ1−ｘ2−ｘ3＋ｘ4
ｗ5（ｔ2）＝ｗ5（ｔ1）＋ｗ7（ｔ1）＝ｘ5＋ｘ6＋ｘ7＋ｘ8
ｗ6（ｔ2）＝ｗ5（ｔ1）−ｗ7（ｔ1）＝ｘ5＋ｘ6−ｘ7−ｘ8
ｗ7（ｔ2）＝ｗ6（ｔ1）＋ｗ8（ｔ1）＝ｘ5−ｘ6＋ｘ7−ｘ8
ｗ8（ｔ2）＝ｗ6（ｔ1）−ｗ8（ｔ1）＝ｘ5−ｘ6−ｘ7＋ｘ8
【００１２】
次にタイミングｔ3のセレクタラッチにより、フィードバックデータｗ1（ｔ2）とｗ8（ｔ2）とが第１および第２のセレクタ無ラッチ１４1、１４2に、フィードバックデータｗ2（ｔ2）〜ｗ7（ｔ2）が第１〜第６のセレクタ有ラッチ１５1〜１５6にそれぞれ格納される（同図（ｇ））。タイミングｔ2以降、セレクタ有ラッチ切替信号により、第１〜第６のセレクタ有ラッチ１５1〜１５6の出力端子Ｂを選択させ（同図（ｄ））、各（ｐ−１＋ｌｏｇ2ｎ）加算器あるいは（ｐ−１＋ｌｏｇ2ｎ）減算器が出力するフィードバックデータは、次のようになる。
【００１３】
0003716695.tif 000002
【００１４】
その後、次のタイミングｔ1の入力ラッチクロックと共通の出力ラッチクロックで、フィードバックデータｗ1（ｔ3）〜ｗ8（ｔ3）を、対応する第１〜第８の出力ラッチ１３1〜１３8にラッチし、次の各成分データｙ1〜ｙ8からなる出力データＹとして出力する。
【００１５】
ｙ1＝ｗ1（ｔ3）＝ｘ1＋ｘ2＋ｘ3＋ｘ4＋ｘ5＋ｘ6＋ｘ7＋ｘ8
ｙ2＝ｗ3（ｔ3）＝ｘ1−ｘ2＋ｘ3−ｘ4＋ｘ5−ｘ6＋ｘ7−ｘ8
ｙ3＝ｗ5（ｔ3）＝ｘ1＋ｘ2−ｘ3−ｘ4＋ｘ5＋ｘ6−ｘ7−ｘ8
ｙ4＝ｗ7（ｔ3）＝ｘ1−ｘ2−ｘ3＋ｘ4＋ｘ5−ｘ6−ｘ7＋ｘ8
ｙ5＝ｗ2（ｔ3）＝ｘ1＋ｘ2＋ｘ3＋ｘ4−ｘ5−ｘ6−ｘ7−ｘ8
ｙ6＝ｗ4（ｔ3）＝ｘ1−ｘ2＋ｘ3−ｘ4−ｘ5＋ｘ6−ｘ7＋ｘ8
ｙ7＝ｗ6（ｔ3）＝ｘ1＋ｘ2−ｘ3−ｘ4−ｘ5−ｘ6＋ｘ7＋ｘ8
ｙ8＝ｗ8（ｔ3）＝ｘ1−ｘ2−ｘ3＋ｘ4−ｘ5＋ｘ6＋ｘ7−ｘ8
【００１６】
このように従来の高速アダマール変換器では、量子化ビット数ｐのｎ次元入力ベクトルの各成分データに対して、各ｎ／２個の（ｐ−１＋ｌｏｇ2ｎ）ビット加算器および減算器によるバタフライ演算処理で加減算を施し、ｎ次のアダマール変換をして、ｎ次元出力ベクトルの各成分データを生成する。このような高速アダマール変換器に関する技術は、例えば特開平６−３０１７１１号公報「高速アダマール変換器」に開示されている。
【００１７】
【発明が解決しようとする課題】
しかしながら従来提案された高速アダマール変換器は、演算するビット数がｋ倍になったとき、ビットごとに入力ラッチ、セレクタ有ラッチおよび出力ラッチの３つのラッチが必要であるため、単純計算で回路規模が３ｋ倍になってしまう。また、バタフライ演算処理における加減算処理をパラレル処理しているため、加減算器のビット数を（ｐ−１＋ｌｏｇ2ｎ）ビット必要とするばかりでなく、ラッチのレジスタビット数も（ｐ−１＋ｌｏｇ2ｎ）ビット必要とする。このような高速アダマール変換器をゲートアレイ化する場合、回路規模の増大により、非常にコストがかかり、ゲートアレイには不向きである。また、成分データに応じてセレクタ有ラッチやセレクタ無ラッチ等異なる機能を有するブロックを必要とするため、各ブロックごとの検証が必要となるばかりでなく、同一ブロックの繰り返し配置配線に適する集積化にも開発工数がかかり、開発ＴＡＴの短縮化が望ましい。
【００１８】
そこで本発明の目的は、演算すべきビット数が増加した場合であっても回路規模の増大を最小限に抑えるとともに開発ＴＡＴの短縮化を図ることができる高速アダマール変換器を提供することにある。
【００１９】
【課題を解決するための手段】
請求項１記載の発明では、（イ）所定のデータ入力タイミングでそれぞれ入力される量子化ビット数ｐからなる入力データあるいは（ｐ＋ｌｏｇ2ｎ）（ｎは自然数）ビットのシリアルデータのいずれか一方を順次１ビットずつ所定のシフトタイミングでシフトする第１〜第ｎのシフトレジスタ部と、（ロ）第（２ｉ−１）（ただし、１≦ｉ≦ｎ／２、ｉは自然数）および第（２ｉ）のシフトレジスタ部によって１ビットずつ順次シフト出力された１ビットデータの加算および減算を行って、加算結果および減算結果をそれぞれ第ｉおよび第（ｉ＋ｎ／２）のシフトレジスタ部に対してシリアルデータとして出力する第１〜第（ｎ／２）のバタフライ演算部と、（ハ）これら第１〜第（ｎ／２）のバタフライ演算部それぞれの入力元および出力先をシフトによりデータが１周するたびに切り替える入力元出力先切替スイッチとを高速アダマール変換器に具備させる。
【００２０】
すなわち請求項１記載の発明では、ｎ個のシフトレジスタ部と（ｎ／２）個のバタフライ演算部とから構成され、量子化ビットｐからなるｎ次元の入力データについて、各シフトレジスタ部では各次元の入力データあるいは（ｐ＋ｌｏｇ2ｎ）（ｎは自然数）ビットのシリアルデータのいずれか一方を順次１ビットずつ所定のシフトタイミングでシフトさせる。そして、第ｉのバタフライ演算部では、第（２ｉ−１）および第（２ｉ）のシフトレジスタ部によって１ビットずつ順次シフト出力された１ビットデータの加算および減算を行って、加算結果および減算結果をそれぞれ第ｉおよび第（ｉ＋ｎ／２）のシフトレジスタ部に対してシリアルデータとして出力する。
【００２１】
請求項２記載の発明では、請求項１記載の高速アダマール変換器で、バタフライ演算部は、第（２ｉ−１）のシフトレジスタ部によってシフト出力された１ビットデータと第（２ｉ）のシフトレジスタ部によってシフト出力された１ビットデータと前回のシフトタイミングで生成されたキャリーとを加算する加算手段と、この加算手段によって生成されたキャリーを１シフトタイミングだけ遅延する第１の遅延手段と、第（２ｉ−１）のシフトレジスタ部によってシフト出力された１ビットデータから第（２ｉ）のシフトレジスタ部によってシフト出力された１ビットデータと前回のシフトタイミングで生成されたボローを減算する減算手段と、この減算手段によって生成されたボローを１シフトタイミングだけ遅延する第２の遅延手段とを備えることを特徴としている。
【００２２】
すなわち請求項２記載の発明では、バタフライ演算部を、１ビットの加算器と減算器と、第１および第２の遅延手段でのみ構成するようにしたので、回路の簡素化と規模の縮小化のみならず、回路の高速化を図ることができる。
【００２３】
請求項３記載の発明では、請求項１または請求項２記載の高速アダマール変換器で、シフトレジスタ部それぞれは、所定のデータ出力タイミングでシフトレジスタ部でシフトされる（ｐ＋ｌｏｇ2ｎ）ビットを選択出力する（ｐ＋ｌｏｇ2ｎ）個の出力スイッチを備えることを特徴としている。
【００２４】
すなわち請求項３記載の発明では、各シフトレジスタ部では、所定のデータ出力タイミングでシフトレジスタ部でシフトされる（ｐ＋ｌｏｇ2ｎ）ビットを選択出力する（ｐ＋ｌｏｇ2ｎ）個の出力スイッチを備え、所定のデータ出力タイミングごとに高速アダマール変換結果を取り出せるようにした。
【００２５】
請求項４記載の発明では、請求項２または請求項３記載の高速アダマール変換器で、第１および第２の遅延手段は、（ｌｏｇ2ｎ×（ｐ＋ｌｏｇ2ｎ））シフトタイミングごとに初期化されるものであることを特徴としている。
【００２６】
すなわち請求項４記載の発明では、（ｌｏｇ2ｎ×（ｐ＋ｌｏｇ2ｎ））シフトタイミングごとに第１および第２の遅延手段で遅延されるデータを初期化するようにしたので、（ｌｏｇ2ｎ×（ｐ＋ｌｏｇ2ｎ））シフトタイミングごとに連続して高速アダマール変換を行うことができる。
【００２７】
【発明の実施の形態】
【００２８】
【実施例】
以下実施例につき本発明を詳細に説明する。
【００２９】
図１は、本発明の一実施例における高速アダマール変換器の構成の概要を表わしたものである。本実施例における高速アダマール変換器は、量子化ビット数ｐのｎ次元高速アダマール変換を行う場合、ｎ個のシフトレジスタ部２０1〜２０nと、ｎ／２個のバタフライ演算部２１1〜２１n/2とから構成される。
【００３０】
シフトレジスタ部２０1〜２０nは、それぞれ２つの入力端子ＤＩＮ、ＬＩＮと、２つの出力端子ＤＯＵＴ、ＬＯＵＴとを有している。ＤＩＮにはｎ次元の入力データＶ1〜Ｖnが入力され、ＤＯＵＴからはｎ次元の出力データＷ1〜Ｗnが出力される。ＬＯＵＴからは、ＤＩＮから入力された入力データがシリアルデータとして１ビットずつバタフライ演算部に対して出力される。ＬＩＮには、バタフライ演算部によって演算された結果である１ビットデータが入力される。このようなシフトレジスタ部２０1〜２０nは、セレクタを設けて入力ラッチおよび出力ラッチを共用化して所定の入力タイミングでＤＩＮからの入力データＶ1〜Ｖnを取り込み、シフトレジスタ部でシリアル変換されて１ビットずつバタフライ演算部で加減算処理され、最終的にバタフライ演算処理された結果が所定の出力タイミングでＤＯＵＴから出力データＷ1〜Ｗnとして出力されるようになっている。
【００３１】
バタフライ演算部は、２つの入力端子ＡＤＤＩＮ、ＳＵＢＩＮと、２つの出力端子ＡＤＤＯＵＴ、ＳＵＢＯＵＴとを有し、シフトレジスタ部のＬＯＵＴから入力された入力データに対して１ビットずつバタフライ演算を行って、その結果をシフトレジスタ部のＬＩＮに供給する。このとき、図示しない入力元出力先切替スイッチによってバタフライ演算部の入力元と出力先が切り替えられるようになっている。
【００３２】
以下、本実施例における高速アダマール変換器の要部について説明する。ここでは、量子化ビット数ｐを“４”、次元数ｎを“８”とする。すなわち、この高速アダマール変換器は、シフトレジスタ部２０1〜２０8と、バタフライ演算部２１1〜２１4とを備えている。シフトレジスタ部２０1〜２０8は、それぞれ同一構成をなしている。バタフライ演算部２１1〜２１4は、それぞれ同一構成をなしている。シフトレジスタ部２０1〜２０8のＤＩＮには、入力データＶ1〜Ｖ8が入力され、ＤＯＵＴからは出力データＷ1〜Ｗ8が出力される。シフトレジスタ部２０2q-1（１≦ｑ≦４、ｑは自然数）のＬＯＵＴは、バタフライ演算部２１qのＡＤＤＩＮに接続される。またシフトレジスタ部２０2qのＬＯＵＴは、バタフライ演算部２１qのＳＵＢＩＮに接続される。バタフライ演算部２１r（１≦ｒ≦４、ｒは自然数）のＡＤＤＯＵＴは、シフトレジスタ部２０rのＬＩＮに接続される。また、バタフライ演算部２１rのＳＵＢＯＵＴは、シフトレジスタ部２０r+4のＬＩＮに接続される。
【００３３】
図２は、シフトレジスタ部２０の構成要部を表わしたものである。シフトレジスタ部２０は、ｍを“ｐ＋ｌｏｇ2ｎ”とすると、ｍ個の１ビットのフリップフロップ３０1〜３０mと、ｍ個の入力スイッチ３１1〜３１mと、ｍ個の出力スイッチ３２1〜３２mとを備えている。フリップフロップ３０1〜３０mは所定のラッチクロックでＤ端子の入力データをラッチしてＱ端子から出力する。入力スイッチ３１1〜３１mは、所定の入力スイッチ切替信号により、ＩＮ端子から入力されたデータをＯ1端子あるいはＯ2端子から出力させる。出力スイッチ３２1〜３２mは、所定の出力スイッチ切替信号により、Ｉ1端子あるいはＩ2端子のいずれか一方から入力されたデータを、ＯＵＴ端子から出力させる。
【００３４】
入力スイッチ３１1のＩＮ端子には、ＬＩＮから入力されたデータが入力される。入力スイッチ３１1のＯ1端子からは、ＤＯＵＴの１ビットが出力される。入力スイッチ３１1のＯ2端子は、出力スイッチ３２1のＩ2端子に接続される。出力スイッチ３２1のＩ1端子には、ＤＩＮの最上位ビット（Most Significant Bit：以下、ＭＳＢと略す。）が入力される。出力スイッチ３２1のＯＵＴ端子は、フリップフロップ３０1のＤ端子に接続される。
【００３５】
入力スイッチ３１2〜３１7のＩＮ端子には、それぞれ前段のフリップフロップ３０1〜３０6のＱ端子が接続される。入力スイッチ３１2〜３１7のＯ1端子は、ＤＯＵＴの１ビットとして出力される。入力スイッチ３１2〜３１7のＯ2端子は、それぞれ出力スイッチ３２2〜３２7のＩ2端子に接続される。出力スイッチ３２2〜３２7のＩ1端子は、それぞれＤＩＮのＭＳＢの次の上位ビットから順に最下位ビット（Least Significant Bit：以下、ＬＳＢと略す。）まで入力される。出力スイッチ３２2〜３２7のＯＵＴ端子は、フリップフロップ３０2〜３０7のＤ端子に接続される。フリップフロップ３０7のＱ端子は、ＬＯＵＴとして出力される。
【００３６】
このような構成のフリップフロップはｎ次の高速アダマール変換における各段の変換結果を１ビットごとに保持し、入力スイッチおよび出力スイッチは本実施例における高速アダマール変換器へのデータ入力と演算結果としてのデータ出力を行う際の信号の流れを制御する。すなわち、所定のデータ入力タイミングにおける入力スイッチ切替信号により、出力スイッチ３２1〜３２7はＩ1端子とＯＵＴ端子とを接続し、ＤＩＮから入力される入力データをフリップフロップ３０1〜３０7に取り込む。また、所定のデータ出力タイミングにおける出力スイッチ切替信号により、入力スイッチ３１1〜３１7はＩＮ端子とＯ1端子とを接続し、ＬＩＮから入力されるバタフライ演算結果をＤＯＵＴとして出力する。それ以外では、入力スイッチ３１1〜３１7はＩＮ端子とＯ2端子を接続し、出力スイッチ３２1〜３２7はＩ2端子とＯＵＴ端子を接続し、フリップフロップ３０1〜３０7で所定のラッチクロックごとに１ビットずつシフトさせ、順次ＬＯＵＴとしてバタフライ演算部に供給する。
【００３７】
図３は、バタフライ演算部２１の構成要部を表わしたものである。このバタフライ演算部２１は、１ビットのキャリー入出力付きの加算器４０と、１ビットのボロー入出力付きの減算器４１と、１ビットのリセット付きフリップフロップ４２と、１ビットのセット付きフリップフロップ４３とを有している。シフトレジスタ部から入力されるＡＤＤＩＮは、加算器４０および減算器４１のＡＤＤ0端子に入力される。シフトレジスタ部から入力されるＳＵＢＩＮは、それぞれ加算器４０のＡＤＤ1端子および減算器４１のＳＵＢ0端子に入力される。
【００３８】
図４は、加算器４０の論理レベルの動作を示す真理値表を表わしたものである。加算器４０は、ＡＤＤ0端子およびＡＤＤ1端子から入力された１ビットデータとＣＩＮ端子から入力される１ビットのキャリーとの加算結果をＯＵＴ端子から出力するとともに、１ビットのキャリー出力をＣＯＵＴ端子から出力する。ＯＵＴ端子から出力された加算結果は、ＡＤＤＯＵＴとしてシフトレジスタ部に供給される。ＣＯＵＴ端子はフリップフロップ４２のＤ端子に接続され、このフリップフロップ４２のＱ端子は加算器４０のＣＩＮ端子に接続される。
【００３９】
図５は、減算器４１の論理レベルの動作を示す真理値表を表わしたものである。減算器４１は、ＡＤＤ0端子およびＳＵＢ0端子から入力された１ビットデータとＢＩＮ端子から入力される１ビットのボローとの減算結果をＯＵＴ端子から出力するとともに、１ビットのボロー出力をＢＯＵＴ端子から出力する。ＯＵＴ端子から出力された減算結果は、ＳＵＢＯＵＴとしてシフトレジスタ部に供給される。ＢＯＵＴ端子はフリップフロップ４３のＤ端子に接続され、このフリップフロップ４３のＱ端子は減算器４１のＢＩＮ端子に接続される。
【００４０】
フリップフロップ４２は、初期状態においてＲ端子に入力されたリセット信号により“０”が出力され、通常の動作時において１ビットのキャリーをラッチクロックの１クロック分遅延させて加算器４０に供給することで、１ビットの桁上がり計算を行う。フリップフロップ４３は、初期状態においてＳ端子に入力されたセット信号により“１”が出力され、通常の動作時において１ビットのボローをラッチクロックの１クロック分遅延させて減算器４１に供給することで、１ビットの桁下がりの計算を行う。
【００４１】
次に、図６を参照しながら、上述した構成要部を有する本実施例における高速アダマール変換器の動作について説明する。
【００４２】
図６は、本実施例における高速アダマール変換器の動作タイミングの概要を表わしたものである。同図（ａ）は、ラッチクロックのタイミングを示す。同図（ｂ）は、入力ベクトルのデータ入力タイミングを示す。同図（ｃ）は、高速アダマール変換によるデータ出力タイミングを示す。同図（ｄ）は、入力スイッチおよび出力スイッチのスイッチ切替タイミングを示す。同図（ｅ）は、バタフライ演算部の加算器のリセットタイミングおよび減算器のセットタイミングを示す。
【００４３】
量子化ビット数ｐが“４”のデータ系列に８次元の高速アダマール変換を行う場合、同図（ｂ）に示すタイミングで、本実施例における高速アダマール変換器には、それぞれＭＳＢ側からｂ3、ｂ2、ｂ1、ｂ0で表現される８次元の入力ベクトルＶ0〜Ｖ7からなる入力データ５０が、ＬＳＢ側から順にＬＯＵＴとしてバタフライ演算部に供給されるようにＤＩＮとして入力される。具体的には、ＤＩＮのｂ3が入力スイッチ３２4のＩ1端子、ｂ2が入力スイッチ３２5のＩ1端子、ｂ1が入力スイッチ３２6のＩ1端子、ｂ0が入力スイッチ３２7のＩ1端子それぞれに入力される。入力スイッチは、７ビット分備えているが、これはバタフライ演算により桁上がりが発生するためであり、データ入力時には上位３ビットは“０”が入力される。したがって、データ入力時における入力スイッチ３２1〜３２3のＩ1端子には、“０”が入力される。
【００４４】
このようなデータ入力に対応して、入力スイッチ３２1〜３２7に同図（ｄ）に示すタイミングの入力スイッチ切替信号が入力される（スイッチ切替５１）。この入力スイッチ切替信号が“Ｌ”のとき、入力スイッチ３２1〜３２7では、Ｉ1端子とＯＵＴ端子が接続され、Ｉ1端子に供給される入力データがフリップフロップ３０1〜３０7のＤ端子に入力される。また、出力スイッチ切替信号が、同図（ｄ）に示す入力スイッチ切替信号と同一タイミングで出力スイッチ３１1〜３１7に入力されるようになっており、出力スイッチ切替信号が“Ｌ”のとき、出力スイッチ３１1〜３１7ではＩＮ端子とＯ1端子が接続され、ＩＮ端子に入力されるデータがＤＯＵＴとして出力される。このＤＯＵＴは、前サイクルの高速アダマール変換結果である出力データ５２として出力される。さらにまた、同図（ｅ）に示すように、バタフライ演算部にリセット信号およびセット信号が入力されるので、バタフライ演算部のフリップフロップ４２、４３が初期化されるようになっている（クリア５３）。
【００４５】
上述したように、入力スイッチ切替信号が“Ｈ”のとき、シフトレジスタ部２０1〜２０8は、それぞれ７段のシフトレジスタを構成する。この間、出力スイッチ切替信号も“Ｈ”であるため、ＬＩＮにはバタフライ演算部の出力であるＡＤＤＯＵＴあるいはＳＵＢＯＵＴからの１ビットデータが接続され、ＬＯＵＴからはバタフライ演算部のＡＤＤＩＮあるいはＳＵＢＩＮに対してシフトレジスタ結果として１ビットずつ出力される。そして、７回シフトによりデータが１周することによって、３（＝ｌｏｇ2ｎ）段の計算を行う高速アダマール変換の１段目の計算が行われるようになっている。
【００４６】
すなわち、所定のデータ入力タイミングでシフトレジスタ部のフリップフロップ３０1〜３０7に格納されたデータは、最初の１クロック目でＬＳＢの１ビット加算を行う。例えば、バタフライ演算部２１1のＡＤＤＯＵＴからは“Ｖ1＋Ｖ2”のＬＳＢの計算結果が出力され、ＳＵＢＯＵＴからは“Ｖ1−Ｖ2”のＬＳＢのＬＳＢの計算結果が出力される。ここで、それぞれｂ3〜ｂ0で表現されるＶ1とＶ2（ｂ5〜ｂ7は“０”）について、ＡＤＤＯＵＴから出力される“Ｖ1＋Ｖ2”に着目すると、次のようになる。
【００４７】
１クロック目：Ｖ1（ｂ0）＋Ｖ2（ｂ0）
２クロック目：Ｖ1（ｂ1）＋Ｖ2（ｂ1）＋（ｂ0加算時のキャリー）
３クロック目：Ｖ1（ｂ2）＋Ｖ2（ｂ2）＋（ｂ1加算時のキャリー）
４クロック目：Ｖ1（ｂ3）＋Ｖ2（ｂ3）＋（ｂ2加算時のキャリー）
５クロック目：Ｖ1（ｂ4）＋Ｖ2（ｂ4）＋（ｂ3加算時のキャリー）
６クロック目：Ｖ1（ｂ5）＋Ｖ2（ｂ5）＋（ｂ4加算時のキャリー）
７クロック目：Ｖ1（ｂ6）＋Ｖ2（ｂ6）＋（ｂ5加算時のキャリー）
【００４８】
入力データが取り込まれてから最初の７クロックで、シフトレジスタ部のフリップフロップ３０1〜３０7に格納されている演算結果を、フリップフロップ３０1をＭＳＢ、フリップフロップ１０7をＬＳＢとした量子化データとしたとき、これらフィードバックデータｗ1（１）〜ｗ8（１）は、次のようになる。なお、各段で、前記した入力元出力先切替スイッチによるバタフライ演算部２１1〜２１4の入力元出力先が切り替わることになるが、これらについての図示は省略し、フィードバックデータｗ1（１）〜ｗ8（１）、ｗ1（２）〜ｗ8（２）、ｗ1（３）〜ｗ8（３）のみを順に示していくことにする。
【００４９】
ｗ1（１）＝Ｖ1＋Ｖ2
ｗ2（１）＝Ｖ1−Ｖ2
ｗ3（１）＝Ｖ3＋Ｖ4
ｗ4（１）＝Ｖ3−Ｖ4
ｗ5（１）＝Ｖ5＋Ｖ6
ｗ6（１）＝Ｖ5−Ｖ6
ｗ7（１）＝Ｖ7＋Ｖ8
ｗ8（１）＝Ｖ7−Ｖ8
【００５０】
そして、入力データが取り込まれてから７クロック目に、図６（ｅ）に示すようにバタフライ演算部にリセット信号およびセット信号が入力され、バタフライ演算部の加算器および減算器が初期化される。以降シフトレジスタ部のデータを１ビットごとに同様の計算を行う。したがって、次の７クロック目におけるフィードバックデータｗ1（２）〜ｗ8（２）は、次のようになる。
【００５１】
ｗ1（２）＝Ｖ1＋Ｖ2＋Ｖ3＋Ｖ4
ｗ2（２）＝Ｖ5＋Ｖ6＋Ｖ7＋Ｖ8
ｗ3（２）＝Ｖ1−Ｖ2＋Ｖ3−Ｖ4
ｗ4（２）＝Ｖ5−Ｖ6＋Ｖ7−Ｖ8
ｗ5（２）＝Ｖ1＋Ｖ2−Ｖ3−Ｖ4
ｗ6（２）＝Ｖ5＋Ｖ6−Ｖ7−Ｖ8
ｗ7（２）＝Ｖ1−Ｖ2−Ｖ3＋Ｖ4
ｗ8（２）＝Ｖ5−Ｖ6−Ｖ7＋Ｖ8
【００５２】
同様に、７クロックごとに入力されるリセット信号およびセット信号により、バタフライ演算部が初期化され、さらに次の７クロック目におけるフィードバックデータｗ1（３）〜ｗ8（３）は、次のようになる。
【００５３】
ｗ1（３）＝Ｖ1＋Ｖ2＋Ｖ3＋Ｖ4＋Ｖ5＋Ｖ6＋Ｖ7＋Ｖ8
ｗ2（３）＝Ｖ1−Ｖ2＋Ｖ3−Ｖ4＋Ｖ5−Ｖ6＋Ｖ7−Ｖ8
ｗ3（３）＝Ｖ1＋Ｖ2−Ｖ3−Ｖ4＋Ｖ5＋Ｖ6−Ｖ7−Ｖ8
ｗ4（３）＝Ｖ1−Ｖ2−Ｖ3＋Ｖ4＋Ｖ5−Ｖ6−Ｖ7＋Ｖ8
ｗ5（３）＝Ｖ1＋Ｖ2＋Ｖ3＋Ｖ4−Ｖ5−Ｖ6−Ｖ7−Ｖ8
ｗ6（３）＝Ｖ1−Ｖ2＋Ｖ3−Ｖ4−Ｖ5＋Ｖ6−Ｖ7＋Ｖ8
ｗ7（３）＝Ｖ1＋Ｖ2−Ｖ3−Ｖ4−Ｖ5−Ｖ6＋Ｖ7＋Ｖ8
ｗ8（３）＝Ｖ1−Ｖ2−Ｖ3＋Ｖ4−Ｖ5＋Ｖ6＋Ｖ7−Ｖ8
【００５４】
このようにして、シフトレジスタ部のフリップフロップによりパラレル−シリアル変換を行い、“ｌｏｇ2ｎ×（ｐ＋ｌｏｇ2ｎ）”クロックによりバタフライ演算部で加減算を行う。例えば量子化ビット数ｐが“４”で、８次元の入力ベクトルデータに対して、２１クロックで８次のアダマール変換を完了することができる。そして、同図（ｄ）に示すように２１クロックごとにスイッチ切替信号により入力スイッチおよび出力スイッチを切り替えて、シフトレジスタ部のフリップフロップに格納された量子化データをＤＯＵＴとして出力するとともに、次の入力ベクトルデータを取り込んでデータの入れ替えを行う。
【００５５】
このように本実施例における高速アダマール変換器では、量子化ビット数ｐのｎ次元の入力データに対してそれぞれ同様の構成をなし、入力ラッチと出力ラッチを共用化する切替スイッチを用いて“ｐ＋ｌｏｇ2ｎ”段の１ビットシフトレジスタを構成するｎ個のシフトレジスタ部と、１ビットごとに加減算を行う“ｎ／２”個のバタフライ演算部を備えるようにした。これにより、従来のように複数ビットの加減算器と複数ビットのラッチレジスタを複数個必要としていたのに対して、ラッチレジスタの個数を１／３にし、回路規模が１／“３×（量子化ビット数）”以下に削減することができる。したがって、演算すべきビット数が増加した場合であっても回路規模の増大を最小限に抑えることができる。また、高速アダマール変換器を構成するブロックは、各データともに同一の構成をなしているので、開発工数の削減および開発ＴＡＴの短縮化を図ることができ、最適な構成の高速アダマール変換器を提供することができるようになる。さらに、また１ビット構成により回路構成を非常に簡素化したので、従来のような多ビット構成よりも個々の高速化が容易となって、高速アダマール変換器をさらに高速なラッチクロックで動作させることができるようになる。
【００５６】
【発明の効果】
以上説明したように請求項１記載の発明によれば、量子化ビット数ｐのｎ次元の入力データに対してそれぞれ同様の構成をなし、入力ラッチと出力ラッチを共用化する切替スイッチを用いて“ｐ＋ｌｏｇ2ｎ”段の１ビットシフトレジスタを構成するｎ個のシフトレジスタ部と、１ビットごとに加減算を行う“ｎ／２”個のバタフライ演算部を備えるようにしたので、従来のように複数ビットの加減算器と複数ビットのラッチレジスタを複数個必要としていたのに対して、ラッチレジスタの個数を１／３にし、回路規模が１／“３×（量子化ビット数）”以下に削減することができる。したがって、演算すべきビット数が増加した場合であっても回路規模の増大を最小限に抑えることができる。また、高速アダマール変換器を構成するブロックは、各データともに同一の構成をなしているので、開発工数の削減および開発ＴＡＴの短縮化を図ることができ、最適な構成の高速アダマール変換器を提供することができるようになる。
【００５７】
また請求項２または請求項３記載の発明によれば、１ビットの加算器と減算器と、第１および第２の遅延手段でのみ構成し、あるいは各シフトレジスタ部では、所定のデータ出力タイミングでシフトレジスタ部でシフトされる（ｐ＋ｌｏｇ2ｎ）ビットを選択出力する（ｐ＋ｌｏｇ2ｎ）個の出力スイッチを備え、所定のデータ出力タイミングごとに高速アダマール変換結果を取り出せるようにしたので、回路の簡素化と規模の縮小化のみならず、回路の高速化を図ることができる。
【００５８】
さらにまた請求項４記載の発明によれば、（ｌｏｇ2ｎ×（ｐ＋ｌｏｇ2ｎ））シフトタイミングごとに第１および第２の遅延手段で遅延されるデータを初期化するようにしたので、（ｌｏｇ2ｎ×（ｐ＋ｌｏｇ2ｎ））シフトタイミングごとに連続して容易に高速アダマール変換を行うことができる。
【図面の簡単な説明】
【図１】本実施例における高速アダマール変換器の構成の概要を示すブロック図である。
【図２】本実施例におけるシフトレジスタ部の構成要部を示すブロック図である。
【図３】本実施例におけるバタフライ演算部の構成要部を示すブロック図である。
【図４】本実施例における加算器の論理レベルの動作を示す真理値表を示す説明図である。
【図５】本実施例における減算器の論理レベルの動作を示す真理値表を示す説明図である。
【図６】本実施例における高速アダマール変換器の動作タイミングを示すタイミング図である。
【図７】従来提案された高速アダマール変換器の構成の概要を示すブロック図である。
【図８】従来の高速アダマール変換器の動作タイミングを示すタイミング図である。
【符号の説明】
２０、２０1〜２０8  シフトレジスタ部
２１、２１1〜２１4  バタフライ演算部
３０1〜３０7  フリップフロップ
３１1〜３１7  出力スイッチ
３２1〜３２7  入力スイッチ
４０  キャリー入出力付き加算器
４１  ボロー入出力付き減算器
４２  リセット付きフリップフロップ
４３  セット付きフリップフロップ
【図１】
0003716695.tif 000003
【図２】
0003716695.tif 000004
【図３】
0003716695.tif 000005
【図４】
0003716695.tif 000006
【図５】
0003716695.tif 000007
【図６】
0003716695.tif 000008
【図７】
0003716695.tif 000009
【図８】
0003716695.tif 000010