查看“︁沃爾什函數”︁的源代码

[[File:Natural and sequency ordered Walsh 16.svg|thumb|480px|自然順序（哈德碼得順序）和 序數順序 （沃爾什順序），大小皆為16。 前者通常稱作[[沃爾什矩陣]].<br>後者每行的符號變更是連續的，可以用於頻譜分析。]]

'''沃爾什函數'''（{{lang-en|Walsh function}}，或称{{lang|en|Walsh system}}）可以被看作一個和連續類比系統的[[三角波]]相對應的系統，可以說是離散而且數位版本的三角波。和三角波不同，沃爾什函數只有部分連續。這個函數的值域只有 −1 和 +1 兩個值。有了沃爾什函數當作基礎，當我們要進行類似於[[傅立葉轉換]]的[[沃爾什轉換]]時，不需要做在虛數值域上的浮點數計算，而能夠減少計算量與誤差。

不論是三角波，或是沃爾什函數都能透過週期性延伸至整個實數空間<math>\mathbb R </math>。另外，傅立葉分析在數位系統所對應到的方波可以用沃爾什函數來表達。沃爾什函數，數列，和轉換，在物理和工程上面，都有相當多的應用，特別在數位語音處理上面。他的主要應用包含[[語音辨識]]，在生物醫學領域的[[影像處理]]，和其他領域。

歷史上，許多種類的沃爾什函數都曾被使用，而一般來說都各有優劣。在下文中，使用Walsh-Paley函数來代表沃爾什函數。

==定義==

我們定義沃爾什函數的序列 <math> W_k : [0,1] \rightarrow \{-1,1\} </math>, <math> k \in \mathbb N_0 </math>如下:

對於任何 <math> k \in \mathbb N_0 </math>, <math> x \in [0,1] </math> 令:

:<math> k = \sum_{j=0}^\infty k_j2^j, k_j \in \{0,1\} </math>, &nbsp; <math> x = \sum_{j=1}^\infty x_j2^{-j}, x_j \in \{0,1\} </math>

使得只有有限多個非零的 ''k''<sub>j</sub> 和 ''x''<sub>j</sub> 等於 1, 也分別是整數 ''k'' 和實數 ''x''的 [[二進位]] 表示。
根據定義

:<math> W_k(x) = (-1)^{\sum_{j=0}^\infty k_jx_{j+1}}</math>

特別得，<math> W_0(x)=1 </math> 對於所有範圍內的 ''x'' 都成立。

注意到 <math> W_{2^m} </math> 正好是{{link-en|拉德马赫函數|Rademacher system}} ''r''<sub>m</sub>。
因此拉德马赫系統是沃爾什系統的一個子集合。
另外，每一個沃爾什函數都能透過拉德马赫函數的乘積得到。
:<math> W_k(x) = \prod_{j=0}^\infty r_j(x)^{k_j} </math>

==性質==

*沃爾什函數是片段常數，
:證明:

::考慮

::<math> k = \sum_{j=0}^a k_j2^j, k_j \in \{0,1\} </math>, 
:: <math> x = \sum_{j=1}^\infty x_j2^{-j}, x_j \in \{0,1\} </math>
:: <math> y = \sum_{j=1}^\infty y_j2^{-j}, y_j \in \{0,1\} </math>
::<math> W_k(x) = (-1)^{\sum_{j=0}^a k_jx_{j+1}}</math>

::考慮  <math>x,y \in [r 2^{-a},(r+1) 2^{-a})</math>

::只要對於 j ≤ a， <math> x_j = y_j </math>

::<math> W_k(x) = (-1)^{\sum_{j=0}^a k_jx_{j+1}} 

= (-1)^{\sum_{j=0}^a k_jy_{j+1}} 

=  W_k(y)</math>

::因此 <math>W_k(x)</math> 在 <math>[r 2^{-a},(r+1) 2^{-a})</math> 中是常數。

*沃爾什系統是一個 [[希尔伯特空间]]<math> L^2[0,1] </math>的標準正交基，標準正交的定義如下:

:<math> \int_0^1 W_k(x)W_l(x)dx = \delta_{kl} </math>,

: 證明:

::當 k= l, <math> \int_0^1 W_k(x)W_l(x)dx =  \int_0^1 1 dx = 1 </math> 

::當 k ≠ l, 

::<math> k = \sum_{j=0}^a k_j2^j, k_j \in \{0,1\} </math>, 

::<math> l = \sum_{j=0}^b l_j2^j, l_j \in \{0,1\} </math>, 

::不失一般性，令 a ≥ b，

::<math> \int_0^1 W_k(x)W_l(x)dx</math>

::<math> =  2^{-a}\sum_{r=0}^{2^a-1}W_k(r 2^{-a})W_l(r 2^{-a})</math>

::<math> =  2^{-a}\prod_{i=0}^{a-1} {1/2 \sum_{r_{a-i-i}=0}^{1} {(-1)^{(k_i+l_i)r_{a-1-i}}}}</math>

::因為  k ≠ l ，一定存在 i 使得 <math>k_i</math> ≠ <math>l_i</math>，假設 <math>k_{i_0}</math> ≠ <math>l_{i_0}</math>，

::那麼 <math>k_{i_0} +  l_{i_0} =1 </math>，那麼

::<math>  2^{-a}\prod_{i=0}^{a-1} {1/2 \sum_{r_{a-i-i}=0}^{1} {(-1)^{(k_i+l_i)r_{a-1-i}}}} = 0</math>

::因此得到 <math> \int_0^1 W_k(x)W_l(x)dx = 0 </math> 對於  k ≠ l。 Q.E.D.

:而基的定義是, 對於所有的 <math> f \in L^2[0,1] </math>, 我們讓 <math> f_k = \int_0^1 f(x)W_k(x)dx </math> 那麼

:<math> \int_0^1 ( f(x) - \sum_{k=0}^N f_k W_k(x) )^2dx \xrightarrow[N\rightarrow\infty]{} 0 </math>

:對於所有的 <math> f \in L^2[0,1] </math>, 序列 <math> \sum_{k=0}^\infty f_k W_k(x) </math> 收斂到 <math> f(x) </math> 對於幾乎所有的 <math> x \in [0,1] </math>.

*沃爾什函數 都有種對稱性，一定是偶函數或者奇函數。

*沃爾什系統(Walsh-Paley) 會形成一個 {{link-en|Schauder basis|Schauder basis}} 在<math> L^p[0,1] </math>, &nbsp; <math> 1< p < \infty </math>。注意到，與 [[Haar wavelet|Haar system]]不同，而與三角波系統相似，這個基並不是[[Schauder basis|unconditional]]，他在<math> L^1[0,1] </math>中也不是一個 Schauder basis。 

*沃爾什系統<math> \{W_k\}, k \in \mathbb N_0 </math>是一個連續離散的群組和 <math> \coprod_{n=0}^\infty \mathbb Z / 2\mathbb Z </math> 同構，

==費米子沃爾什系統==

[[費米子]] 沃爾什系統是一個以"量子"版本的沃爾什系統。與後者不同，他包含了運算操作，而非函式。然而，兩種系統有許多相同的重要功能，像是都是一個[[希尔伯特空间]]的標準正交基，或是在相對應空間的 {{link-en|Schauder basis|Schauder basis}}。在費米子沃爾什系統的元素被稱做 "沃爾什操作元"。

==和沃爾什-阿達瑪轉換的關係==
*二點阿達瑪矩陣：

<math> \boldsymbol{W_2} = \begin{bmatrix} 1 & 1 \\ 1 & -1 \end{bmatrix} </math>    

*四點阿達瑪矩陣：

<math> \boldsymbol{W_4} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \\ 1 & -1 & 1 & -1 \end{bmatrix}</math>

*八點阿達瑪矩陣：
<math>\boldsymbol{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}. </math>

這些阿達瑪轉換的矩陣，其中每一行，都是一個沃爾什函數。

而阿達瑪轉換式子如下:
:<math>F[m]=\sum_{n=0}^{N-1} f[n]W[m,n]</math>

而得到阿達瑪矩陣的方法如下:

Step 1  定義<math>V_{2^{k+1}}=\begin{pmatrix} W_{2^k} & W_{2^k} \\ W_{2^k} & -W_{2^k} \\ \end{pmatrix}</math>

Step 2  根據變號次數的奇偶性把<math>V_{2^{k+1}}</math>轉換成為<math>W_{2^{k+1}}</math>

== 優缺點比較 ==
沃爾什函數和正餘弦函數的比較，也可以看成沃爾什轉換和傅立葉轉換的比較:

===優點===
*只有實數運算，不需要做複數運算。
*僅有0或1，因此不需[[乘法]]運算 (No multiplication) ，僅有加減法運算。
*有部分性質類似於[[離散傅立葉變換]] 。
*適合[[頻譜|頻譜分析]]。
*沃爾什轉換順向轉換 (Forward transform) 與沃爾什轉換逆向轉換 (Inverse transform ) 非常相似。

<math> \begin{cases} \begin{matrix} F\left[ m \right] &=& \sum_{n=0}^{N-1} W\left[ {m, n} \right] f\left[ n \right] & & (\mbox{Forward}) \\ f\left[ n \right] &=& \left( \frac{1}{N} \right) \sum_{n=0}^{N-1} W\left[ {m, n} \right]F\left[ m \right] & &(\mbox{Inverse}) \end{matrix} \end{cases}, </math>

其中 <math> F\left[ n \right] </math> 與 <math> f\left[ n \right] </math> 分別都為[[行向量]] (Column vector) 。

===缺點===
*收斂速度較慢。
*其加減法總量較多。
*摺積上性質無法取代離散傅立葉變換

==應用==

*在數學上的應用，可以再任何需要數字表示的時候使用，如[[沃爾什轉換]]。另外，也存在一個[[快速沃爾什轉換]]，和沃爾什轉換相比會有更高的效率。一些沃爾什轉換的應用如下:
**[[帶寬降低]] (Bandwidth reduction) 。
*** 在微處理器的硬體限制之下，沃爾什轉換能夠代替傅立葉轉換執行帶寬降低的功能。
**[[CDMA]] (Code division multiple access)。
*** 舉例而言，如果要把 [1 0 1] 和 [0 1 1] 要傳輸，可以選兩個沃爾什函數，如[1,1,1,1,1,1,1,1] 和 [1,1,1,1,-1,-1,-1,-1]
*** 1. 把 0轉成 -1， [1 0 1] 看作 [1 -1 1]，[0 1 1] 看作 [-1 1 1]
*** 2. [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]
*** 3. [-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]
*** 4. 把上面兩者相加，成為 [0,0,0,0,2,2,2,2,0,0,0,0,-2,-2,-2,-2,2,2,2,2,0,0,0,0]。
*** 5. 解調時，把 [0,0,0,0,2,2,2,2,0,0,0,0,-2,-2,-2,-2,2,2,2,2,0,0,0,0] 和 第一個沃爾什函數分三段內積，得到[8,-8,8]，得知第一個訊號是 [1 0 1]
*** 6. 解調時，把 [0,0,0,0,2,2,2,2,0,0,0,0,-2,-2,-2,-2,2,2,2,2,0,0,0,0] 和 第二個沃爾什函數分三段內積，得到[-8,8,8]，得知第二個訊號是 [0 1 1]
**[[資訊編碼]] (Information coding)。
**[[特徵識別]] (Feature extraction)。
*** 沃爾什函數的對稱性使得他很適合拿來抽取一些幾何的規律。
*** 摺積(convolution)在[[CNN]]中被拿來抽取圖形的資訊有很好的效果，而相類似的沃爾什函數也有不錯的效果。
**[[心電圖分析]] (ECG signal analysis in medical signal processing)。
*** 利用沃爾什函數的快速轉換能夠壓縮ECG訊號，隨著沃爾什函數係數的減少，壓縮率也會提高。
** 頻率調整 (frequency modulation)
**[[形狀分析]] (shape analysis)。

*沃爾什函數還被應用在[[雷達天文]]上來緩解不同天線訊號電子[[串擾]]的問題。這些在被動[[LCD]]的平面中，可以使得不同的傳輸訊號的相關性最低。

==参见==
* [[沃爾什轉換]]
* [[阿達馬矩陣]]
* [[阿達馬變換]]
* [[Exclusive or]]
* [[約瑟夫·L·沃爾什]]

==外部連結==
*[http://mathworld.wolfram.com/WalshFunction.html Walsh functions at MathWorld] {{Wayback|url=http://mathworld.wolfram.com/WalshFunction.html |date=20210301025412 }}
*[http://sepwww.stanford.edu/public/docs/sep70/carlos1/paper_html/node5.html  Walsh functions at Stanford Exploration Project] {{Wayback|url=http://sepwww.stanford.edu/public/docs/sep70/carlos1/paper_html/node5.html |date=20031121093944 }}
*[https://quasirandomideas.wordpress.com/2010/04/28/walsh-functions-i-orthonormality-and-completeness/ Walsh functions I. Orthonormality and completeness] {{Wayback|url=https://quasirandomideas.wordpress.com/2010/04/28/walsh-functions-i-orthonormality-and-completeness/ |date=20201111212407 }}

==參考資料==
{{reflist}}
*Jian-Jiun Ding, Advanced Digital Signal Processing class note,the Department of Electrical Engineering, National Taiwan University (NTU), Taipei, Taiwan, 2016.
*H. F. Harmuth,“Transmission of information by orthogonal functions,”1970.
*Moon-Hu. Lee,“A new reverse Jacket transform and its fast algorithm,”IEEE Trans. Circuits Syst.-II, vol. 47, pp.39-46, 2000.
*K.G.Beauchamp, "Walsh Functions and Their Applications," Academic Press,1975.
*H. F. Harmuth, "Transmission of Information by Orthogonal Functions," Springer, 1969.
* Alexandridis, N. A., and A. Klinger. "Walsh orthogonal functions in geometrical feature extraction." IEEE Transactions on Electromagnetic Compatibility 3 (1971): 18-25.
* Hutchinson, N. "Bandwidth reduction for speech transmission using a sixteen-bit microprocessor." Journal of microcomputer applications 5.2 (1982): 119-128.
* Kulkarni, P. K., Vinod Kumar, and H. K. Verma. "ECG data compression using fast Walsh transform and its clinical acceptability." International journal of systems science 28.8 (1997): 831-836.
* Romanuke, V. V. "On the Point of Generalizing the Walsh Functions to Surfaces." Bulletin of KhNU. Technical Sciences 6.1 (2007): 187-193.
[[Category:特殊函数]]