Walshova matice

Přirozeně uspořádaná Hadamardova matice přerovnaná do sekvenčně uspořádané Walshovy matice. Počet změn znamének v řádku v přirozeně uspořádané matici je postupně 0, 15, 7, 8, 3, 12, 4, 11, 1, 14, 6, 9, 2, 13, 5 a 10. V přerovnané Walshově matici počet změn znamének postupně roste. První matice v součinu je permutační matice použitá pro přerovnání řádků původní Hadamardovy matice.

Walshova matice je v matematice je speciálním případem Hadamardových matic, a to s dodatečnou podmínkou, že řádky přerovnány tak, aby počet změn znamének v řádku postupně rostl. Jinými slovy, zatímco Hadamardova matice je definována níže uvedeným rekurentním předpisem a je tak přirozeně uspořádaná, je Walshova matice sekvenčně uspořádaná.^[1] Některé zdroje mohou označovat obě matice jako Walshovou matici.

Walshovy matice (a Walshovy funkce) se používají při výpočtu Walshovy transformace a mají aplikace při efektivní implementaci určitých operací zpracování signálu.

Walshovou matici navrhl Joseph L. Walsh v roce 1923.^[1]

Konstrukce

Hadamardova matice řádu $2^{k}$ pro $k\in \mathbb {N}$ je podle Sylvesterovy konstrukce dána rekurentním vzorcem:

{\boldsymbol {H}}_{2}={\begin{pmatrix}1&1\\1&-1\end{pmatrix}}

,

{\boldsymbol {H}}_{4}={\begin{pmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{pmatrix}}

,

a obecně

{\boldsymbol {H}}_{2^{k}}={\begin{pmatrix}{\boldsymbol {H}}_{2^{k-1}}&{\boldsymbol {H}}_{2^{k-1}}\\{\boldsymbol {H}}_{2^{k-1}}&-{\boldsymbol {H}}_{2^{k-1}}\end{pmatrix}}={\boldsymbol {H}}_{2}\otimes {\boldsymbol {H}}_{2^{k-1}}

,

kde $\otimes$ značí Kroneckerův součin matic.

Přerovnání

Walshovu matici lze získat z Hadamardovy matice tak, že se u každého řádku určí počet změn znaménka a řádky jsou pak přerovnány podle počtu změn ve vzestupném pořadí.

Například v Hadamardově matici řádu 4

{\boldsymbol {H}}_{4}={\begin{pmatrix}1&1&1&1\\1&-1&1&-1\\1&1&-1&-1\\1&-1&-1&1\\\end{pmatrix}}

mají po sobě jdoucí řádky postupně 0, 3, 1 a 2 změn znamének (z 1 na -1 nebo naopak). Po přerovnání do matice

{\boldsymbol {W}}_{4}={\begin{pmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&1\\1&-1&1&-1\\\end{pmatrix}}

mají po sobě jdoucí řádky postupně 0, 1, 2 a 3 změn znamének.

Přerovnání řádků odpovídá provedení bitově-reverzní permutace a poté permutace Grayova kódu.^[2]

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Walsh matrix na anglické Wikipedii.

↑ ^a ^b KANJILAL, P. P. Adaptive Prediction and Predictive Control. Stevenage: IET, 1995. Dostupné online. ISBN 0-86341-193-2. S. 210.
↑ LE DINH CHON TAM; GOULET, R.Y. On Arithmetical Shift for Walsh Functions. IEEE Transactions on Computers. 1972-12, roč. C-21, čís. 12, s. 1451–1452. Dostupné online [cit. 2025-01-02]. ISSN 0018-9340. doi:10.1109/T-C.1972.223524.

Související články

Externí odkazy

Obrázky, zvuky či videa k tématu Walshova matice na Wikimedia Commons

[kanjilal-1] KANJILAL, P. P. Adaptive Prediction and Predictive Control. Stevenage: IET, 1995. Dostupné online. ISBN 0-86341-193-2. S. 210.

[2] LE DINH CHON TAM; GOULET, R.Y. On Arithmetical Shift for Walsh Functions. IEEE Transactions on Computers. 1972-12, roč. C-21, čís. 12, s. 1451–1452. Dostupné online [cit. 2025-01-02]. ISSN 0018-9340. doi:10.1109/T-C.1972.223524.

[1]

[2]