アダマール変換

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動
ブール関数ウォルシュ行列英語版はそのウォルシュスペクトラム[1]である。
(1,0,1,0,0,1,1,0) * H(8) = (4,2,0,−2,0,2,0,2)
高速ウォルシュ-アダマール変換英語版
これは(1,0,1,0,0,1,1,0)のウォルシュスペクトラムを早く計算するための方法である.
元の関数は多項式としてのウォルシュスペクトラムの平均によって表現することが出来る。

アダマール変換ウォルシュ–アダマール変換アダマール–ラーデマッヘル–ウォルシュ変換ウォルシュ変換ウォルシュ–フーリエ変換としても知られている)はフーリエ変換の一般化の1つである。直交行列対称行列対合線形写像に2m実数(もしくは複素数、しかしアダマール行列は実数である)上で作用する。

アダマール変換はサイズ2の離散フーリエ変換 (DFT) から構築されているとみなすことができ、実際、サイズがの多次元離散フーリエ変換と等価である。これは任意の入力ベクトルウォルシュ関数英語版重ね合わせに分解する。

この変換はフランス数学者ジャック・アダマールドイツの数学者ハンス・ラーデマッヘルアメリカの数学者ジョセフ・L・ウォルシュ英語版にちなんで命名されている。

定義[編集]

アダマール変換 Hm は 2m × 2m の行列であり、(正規化係数によって縮小された)アダマール行列であり、2m の実数 xn を 2m の実数Xkに変換する。アダマール変換は、再帰的に、もしくは指数 n 及び k二進表現を用いることによって定義される。

再帰的にはまず 1 × 1 のアダマール変換 H0単位行列 H0 = 1 によって定義する。その後 m > 0 のときの Hm

で定義する。ここで正規化係数 1/√2 はしばしば省略される。従って、この正規化係数以外のアダマール行列は全て 1 と −1 で構成される。

同様に、(kn) 番目のアダマール行列を

によって定義できる。ここで kjnj は2進数(0 もしくは 1)である。ここで左上の要素に注意して k = n = 0 と定義する。この場合、

となる。入力と出力を njkj で添字付けられた多次元配列とみなした際、これはユニタリ作用素となるように正規化された 次元DFTとなる。

アダマール行列のいくつかの例を以下に示す。

H1はサイズ2のDFTである。またZ/(2)の2要素の加法群上のフーリエ変換とみなすことが出来る)

ここでは数 ij の二進表現のビットごとの内積となる。例えば、ならば、

であり、(全体の定数を無視すれば)上記のアダマール行列に一致する。行列の最初の行と最初の列がで示されていることに注意する必要がある。

アダマール行列の行はウォルシュ関数である。

量子計算機への応用[編集]

量子情報科学ではよく知られたものとしてアダマールゲート量子論理ゲート英語版)と呼ばれるものがある。これは1つの量子ビットの回転であり、量子ビットの基底状態から、の2つの重みが等しい重ね合わせへの写像である。普通その状態はディラックの記法

と示される。これは変換行列

と一致する。

多くの量子アルゴリズム英語版でアダマール変換を初期段階として利用している。n 個の量子ビットをの重みが等しい2n個の直交状態の重ね合わせに初期化する。

アダマールゲート[編集]

アダマールゲートの応用の1つとして0か1の量子ビットが観測された場合(最初の2操作)、0か1の確率が全く等しい量子ビットを生成する(例えば表と裏が出る確率が同様に確からしいコインを投げるようなものである)。しかし、もしアダマールゲートが2回適用された場合(最後の2操作)、最終的な状態は初期状態に等しくなる(つまり恒等変換である)。

ケット であり、ケットである。

計算複雑性[編集]

アダマール変換は高速アダマール変換を用いると である。

他分野への応用[編集]

アダマール変換は暗号理論並びに多くの信号処理JPEG XRMPEG-4 AVCのようなデータ圧縮アルゴリズムで用いられる。ビデオ圧縮アプリケーションでは、普通は絶対変換差で使用される。また、量子アルゴリズムにおけるグローバーのアルゴリズムショアのアルゴリズム英語版でも重要である。アダマール変換はまた核磁気共鳴質量分析法結晶学といったような科学的方法にも適用される。

学習上の参考になる図書や文献[編集]

  • 遠藤靖:「ウォルシュ解析」、東京電気大学出版局、ISBN 4-501-61340-8 (1993年11月10日)。

関連項目[編集]

外部リンク[編集]

出典[編集]

  1. ^ Compare Figure 1 in Townsend, W. J.; Thornton, M. A.. Walsh Spectrum Computations Using Cayley Graphs. CiteSeerx10.1.1.74.8029.