沃爾什函數

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

自然順序（哈德碼得順序）和 序數順序 （沃爾什順序），大小皆為16。 前者通常稱作沃爾什矩陣.
後者每行的符號變更是連續的，可以用於頻譜分析。

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

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

定義

我們定義沃爾什函數的序列 $W_{k}:[0,1]\rightarrow \{-1,1\}$, $k\in \mathbb {N} _{0}$如下:

對於任何 $k\in \mathbb {N} _{0}$, $x\in [0,1]$ 令:

$k=\sum _{j=0}^{\infty }k_{j}2^{j},k_{j}\in \{0,1\}$,   $x=\sum _{j=1}^{\infty }x_{j}2^{-j},x_{j}\in \{0,1\}$

使得只有有限多個非零的 k_j 和 x_j 等於 1, 也分別是整數 k 和實數 x的 二進位 表示。 根據定義

$W_{k}(x)=(-1)^{\sum _{j=0}^{\infty }k_{j}x_{j+1}}$

特別得，$W_{0}(x)=1$ 對於所有範圍內的 x 都成立。

注意到 $W_{2^{m}}$ 正好是拉德马赫函數 r_m。 因此拉德马赫系統是沃爾什系統的一個子集合。 另外，每一個沃爾什函數都能透過拉德马赫函數的乘積得到。

$W_{k}(x)=\prod _{j=0}^{\infty }r_{j}(x)^{k_{j}}$

性質

• 沃爾什函數是片段常數，

證明:

考慮

$k=\sum _{j=0}^{a}k_{j}2^{j},k_{j}\in \{0,1\}$,

$x=\sum _{j=1}^{\infty }x_{j}2^{-j},x_{j}\in \{0,1\}$

$y=\sum _{j=1}^{\infty }y_{j}2^{-j},y_{j}\in \{0,1\}$

$W_{k}(x)=(-1)^{\sum _{j=0}^{a}k_{j}x_{j+1}}$

考慮 $x,y\in [r2^{-a},(r+1)2^{-a})$

只要對於 j ≤ a， $x_{j}=y_{j}$

$W_{k}(x)=(-1)^{\sum _{j=0}^{a}k_{j}x_{j+1}}=(-1)^{\sum _{j=0}^{a}k_{j}y_{j+1}}=W_{k}(y)$

因此 $W_{k}(x)$ 在 $[r2^{-a},(r+1)2^{-a})$ 中是常數。

• 沃爾什系統是一個 希尔伯特空间$L^{2}[0,1]$的標準正交基，標準正交的定義如下:

$\int _{0}^{1}W_{k}(x)W_{l}(x)dx=\delta _{kl}$,

證明:

當 k= l, $\int _{0}^{1}W_{k}(x)W_{l}(x)dx=\int _{0}^{1}1dx=1$

當 k ≠ l,

$k=\sum _{j=0}^{a}k_{j}2^{j},k_{j}\in \{0,1\}$,

$l=\sum _{j=0}^{b}l_{j}2^{j},l_{j}\in \{0,1\}$,

不失一般性，令 a ≥ b，

$\int _{0}^{1}W_{k}(x)W_{l}(x)dx$

$=2^{-a}\sum _{r=0}^{2^{a}-1}W_{k}(r2^{-a})W_{l}(r2^{-a})$

$=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}}}}$

因為 k ≠ l ，一定存在 i 使得 $k_{i}$ ≠ $l_{i}$，假設 $k_{i_{0}}$ ≠ $l_{i_{0}}$，

那麼 $k_{i_{0}}+l_{i_{0}}=1$，那麼

$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$

因此得到 $\int _{0}^{1}W_{k}(x)W_{l}(x)dx=0$ 對於 k ≠ l。 Q.E.D.

而基的定義是, 對於所有的 $f\in L^{2}[0,1]$, 我們讓 $f_{k}=\int _{0}^{1}f(x)W_{k}(x)dx$ 那麼

$\int _{0}^{1}(f(x)-\sum _{k=0}^{N}f_{k}W_{k}(x))^{2}dx{\xrightarrow[{N\rightarrow \infty }]{}}0$

對於所有的 $f\in L^{2}[0,1]$, 序列 $\sum _{k=0}^{\infty }f_{k}W_{k}(x)$ 收斂到 $f(x)$ 對於幾乎所有的 $x\in [0,1]$.

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

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

• 沃爾什系統$\{W_{k}\},k\in \mathbb {N} _{0}$是一個連續離散的群組和 $\coprod _{n=0}^{\infty }\mathbb {Z} /2\mathbb {Z}$ 同構，

費米子沃爾什系統

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

和沃爾什-阿達瑪轉換的關係

• 二點阿達瑪矩陣：

${\boldsymbol {W_{2}}}={\begin{bmatrix}1&1\\1&-1\end{bmatrix}}$

• 四點阿達瑪矩陣：

${\boldsymbol {W_{4}}}={\begin{bmatrix}1&1&1&1\\1&1&-1&-1\\1&-1&-1&1\\1&-1&1&-1\end{bmatrix}}$

• 八點阿達瑪矩陣：

${\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}}.$

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

而阿達瑪轉換式子如下:

$F[m]=\sum _{n=0}^{N-1}f[n]W[m,n]$

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

Step 1 定義$V_{2^{k+1}}={\begin{pmatrix}W_{2^{k}}&W_{2^{k}}\\W_{2^{k}}&-W_{2^{k}}\\\end{pmatrix}}$

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

優缺點比較

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

優點

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

${\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}},$

其中 $F\left[n\right]$ 與 $f\left[n\right]$ 分別都為行向量 (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·沃爾什

外部連結

• Walsh functions at MathWorld （页面存档备份，存于互联网档案馆）
• Walsh functions at Stanford Exploration Project （页面存档备份，存于互联网档案馆）
• Walsh functions I. Orthonormality and completeness （页面存档备份，存于互联网档案馆）

參考資料

• 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.