ウォルシュ行列

数学において、ウォルシュ行列は次元 2 ⁿの特定の正方行列であり、n は特定の自然数です。行列の要素は+1 または -1 のいずれかであり、行と列は直交しています。ウォルシュ行列は1923 年にジョセフ・L・ウォルシュによって提案されました。^[1] ウォルシュ行列の各行はウォルシュ関数に対応します。

ウォルシュ行列は、行内の符号変化の数が昇順になるように行が並べ替えられたアダマール行列の特殊なケースです。つまり、アダマール行列は以下の再帰式で定義され、自然に順序付けられますが、ウォルシュ行列は順序付けられます。^[1]紛らわしいことに、さまざまな情報源がどちらの行列もウォルシュ行列と呼んでいます。

ウォルシュ行列 (およびウォルシュ関数) は、ウォルシュ変換の計算に使用され、特定の信号処理操作の効率的な実装に応用されています。

の次元のアダマール行列は、再帰式で与えられます (アダマール行列の最低次数は 2 です)。 ${\displaystyle 2^{k}}$${\displaystyle k\in \mathbb {N} }$

${\displaystyle {\begin{aligned}H\left(2^{1}\right)&={\begin{bmatrix}1&1\\1&-1\end{bmatrix}},\\H\left(2^{2}\right)&={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1\\\end{bmatrix}},\end{aligned}}}$

そして一般的に

${\displaystyle H\left(2^{k}\right)={\begin{bmatrix}H\left(2^{k-1}\right)&H\left(2^{k-1}\right)\\H\left(2^{k-1}\right)&-H\left(2^{k-1}\right)\end{bmatrix}}=H(2)\otimes H\left(2^{k-1}\right),}$

2 ≤  k  ∈  Nに対して、⊗ はクロネッカー積を表す。

アダマール行列からウォルシュ行列を得ることができます。そのためには、まず、特定の次元のアダマール行列を生成します。次に、各行の符号の変化の数を数えます。最後に、行列の行を、符号の変化の数に応じて昇順に並べ替えます。

例えば、次元が${\displaystyle 2^{2}}$

${\displaystyle H(4)={\begin{bmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&-1\\\end{bmatrix}}}$、

ここで、連続する行には 0、3、1、2 の符号変化があります (正の 1 から負の 1 に切り替わる回数を数えます、またその逆も同様です)。行を順序通りに並べ替えると、次のようになります。

${\displaystyle W(4)={\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&-1\\1&-1&-1&-1\\\end{bmatrix}},}$

連続する行では、符号が 0、1、2、3 変化します。

ウォルシュ行列の行の順序は、まずビット反転置換を適用し、次にグレイコード 置換を適用することで、アダマール行列の順序から導くことができる。^[2]

${\displaystyle W(8)={\begin{bmatrix}1&1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1&-1\\1&1&-1&-1&-1&-1&-1&-1&1&-1\\1&-1&-1&-1&-1&-1&-1&-1&-1\\1&-1&-1&-1&-1&-1&-1&-1&-1\\1&-1&-1&-1&-1&-1&-1&-1\\1&-1&-1&-1&-1&-1&-1&-1\\1&-1&-1&-1&-1&-1&-1&-1\\\end{bmatrix}},}$

連続する行では、0、1、2、3、4、5、6、7 の符号変化があります。

${\displaystyle W(8)={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&1&1&1&-1&-1&-1&-1\\1&1&-1&-1&1&1&-1&-1\\1&1&-1&-1&-1&-1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&-1&1&-1&-1&1&-1&1\\1&-1&-1&1&1&-1&-1&1\\1&-1&-1&1&-1&1&1&-1\\\end{bmatrix}},}$

連続する行では、0、1、3、2、7、6、4、5 の符号変化があります。

${\displaystyle H(8)={\begin{bmatrix}1&1&1&1&1&1&1&1\\1&-1&1&-1&1&-1&1&-1\\1&1&-1&-1&1&1&-1&-1\\1&-1&-1&1&1&-1&-1&1\\1&1&1&1&-1&-1&-1&-1\\1&-1&1&-1&-1&1&-1&1\\1&1&-1&-1&-1&-1&1&1\\1&-1&-1&1&-1&1&1&-1\\\end{bmatrix}},}$

ここで、連続する行には 0、7、3、4、1、6、2、5 の符号変化があります (アダマール行列)。

ウィキメディア・コモンズには、ウォルシュ行列に関連するメディアがあります。

• ハールウェーブレット
• 五点形マトリックス
• アダマール変換
• 符号分割多重アクセス
• OEIS : A228539 ( OEIS : A228540 ) – 逆バイナリ数値として読み取られた（否定された）バイナリウォルシュ行列の行
• OEIS : A197818 – 負のバイナリ ウォルシュ行列の反対角をバイナリ数として読み取る