XIII. Walsh Transform (Hadamard Transform)

Presentation on theme: "XIII. Walsh Transform (Hadamard Transform)"— Presentation transcript:

1 XIII. Walsh Transform (Hadamard Transform)
 13-A Ideas of Walsh Transforms  8-point Walsh transform  Advantages of the Walsh transform: (1) Real (2) No multiplication is required (3) Some properties are similar to those of the DFT

2  Forward and inverse Walsh transforms are similar.
forward: , inverse:  Alternative names of the Walsh transform: Hadamard transform, Walsh-Hadamard transform  Orthogonal Property if m0  m1  Zero-Crossing Property  Even / Odd Property Useful for spectrum analysis Sometimes also useful for implementing the convolution

3 Walsh transform 和 DFT, DCT 有許多相似處
, DFT[m, n] = exp(j2 m n/N),

4 References for Walsh Transforms
[1] K. G. Beanchamp, Walsh Functions and Their Applications, Academic Press, New York, 1975. [2] B. I. Golubov, A. Efimov, and V. Skvortsov, Walsh Series and Transforms: Theory and Applications, Kluwer Academic Publishers, Boston, 1991. [3] H. F. Harmuth, “Applications of Walsh functions in communications,” IEEE Spectrum, vol. 6, no. 11, pp , Nov [4] H. F. Harmuth, Transmission of Information by Orthogonal Functions, Springer-Verlag, New York, 1972.

5  13-B Generate the Walsh Transform
2-point Walsh transform 4-point Walsh transform How do we obtain the 2k+1-point Walsh transform from the 2k-point Walsh transform ? Step 1 Step 2 根據 sign changes 將 rows 的順序重新排列

6 已知 每個 row 的 sign change 數，由上到下分別為
0, 1, 2, 3, ….., 2k−1 則 每個 row 的 sign change 數，由上到下分別為 0, 3, 4, 7, ….., 2k+1−1, 1, 2, 5, 6, ….., 2k+1−2, 若 row 的index 由0 開始 則 第 n 個 row (n is even and n < N/2) 的 sign change 為 2n (n is odd and n < N/2) 的 sign change 為 2n + 1 (n is even and n  N/2) 的 sign change 為 2n+1−N (n is odd and n  N/2) 的 sign change 為 2n−N 要根據 sign change 的數目將 的 row 重新排列

7 sign changes 3 1 2 sign changes 3 4 7 1 2 5 6

8 Constraint for the number of points of the Walsh transform:
N must be a power of 2 (2, 4, 8, 16, 32, ……..) Although in Matlab it is possible to define the 12 2k point or the 20 2k point Walsh transform, the inverse transform require the floating-point operation.

9  13-C Alternative Forms of the Walsh Transform
標準定義  Sequency ordering (i.e., Walsh ordering) ……. using for signal processing  Dyadic ordering (i.e., Paley ordering) ………... using for control  Natural ordering (i.e., Hadamard ordering) ……using for mathematics Sequency ordering Dyadic ordering Natural ordering W[m, n] (Gray Code) (Bit Reversal) row 0 [1, 1, 1, 1, 1, 1, 1, 1] row 1 row 4 [1, 1, 1, 1, 1, 1, 1, 1] row 2 row 3 row 6 [1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1] row 5 row 7 [1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1] [1, 1, 1, 1, 1, 1, 1, 1]

10  Dyadic ordering Walsh transform
 Natural ordering Walsh transform

11  binary code to gray code
When N = 2k gk = bk, gq = XOR(bq+1, bq) for q = k 1, k 2, …., 1  gray code to binary code bk = gk, bq = XOR(bq+1, gq) for q = k 1, k 2, …., 1

12  13-D Properties (1) Orthogonal Property (2) Zero-Crossing Property
(3) Even / Odd Property (4) Linear Property If f[n]  F[m], g[n]  G[m], ( means the Walsh transform) then a f[n] + b g[n]  a F[m] + b G[m]

13 (5) Addition Property 註： Addition modulo 2 (denoted by ) 0  0 = 1  1 = 0, 0  1 = 1  0 = 1, Example: , therefore 3  7 = 4

14 (6) Special functions [n] = 1 when n = 0, [n] = 0 when n  0 [n]  1, 1  N[n] (7) Shifting property If f[n]  F[m], then f[n  k]  W(k, m)F[m] (8) Modulation property If f[n]  F[m], then W(k, n)f[n]  F[m  k] (9) Parseval’s Theorem If f[n]  F[m], If f[n]  F[m], g[n]  G[m],

15 (10) Convolution Property
If f[n]  F[m], g[n]  G[m], then h[n] = f[n]  g[n]  F[m] G[m]    means the “logical convolution” h[n] = f[n]  g[n] = = For example, when N = 8, h[3] = f[0]g[3] + f[1]g[2] + f[2]g[1] + f[3]g[0] + f[4]g[7] + f[5]g[6] + f[6]g[5] + f[7]g[4] h[2] = f[0]g[2] + f[1]g[3] + f[2]g[0] + f[3]g[1] + f[4]g[6] + f[5]g[7] + f[6]g[4] + f[7]g[5]

16  13-E Butterfly Fast Algorithm
(Method 1) John L. Shark’s Algorithm x[0] x[1] x[2] x[3] x[4] x[5] x[6] x[7] X[0] X[7] X[3] X[4] X[1] X[6] X[2] X[5] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

17 (Method 2) Manz’s Sequence Algorithm
x[0] x[4] x[2] x[6] x[1] x[5] x[3] x[7] X[0] X[1] X[2] X[3] X[4] X[5] X[6] X[7] -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 There are other fast implementation algorithm for the Walsh transform.

18  13-F Applications Walsh transform 適合作 spectrum analysis，但未必適合作convolution Applications of the Walsh transform Bandwidth reduction High resolution Multiplexing Information coding Feature extraction ECG signal (in medical signal processing) analysis Hadamard spectrometer Avoiding quantization error

19 The Walsh transform is suitable for the function that is a combination of Step functions
New Applications: CDMA (code division multiple access)

20  13-G Jacket Transform 把部分的 1 用 取代 4-point Jacket transform
把部分的 1 用 取代 4-point Jacket transform 2k+1-point Jacket P: row permutation [Ref] M.H. Lee, “A new reverse Jacket transform and its fast algorithm”, IEEE Trans. Circuits Syst.-II , vol 47, pp.39-46, 2000.

21  13-H Haar Transform N = 2 N = 4 N = 8
[Ref] H. F. Harmuth, Transmission of Information by Orthogonal Functions, Springer-Verlag, New York, 1972

22 N = 16

23 terms required for NRMSE < 105
H[m, n] 的值 (m = 0, 1, …, 2k −1, n = 0, 1, …, 2k −1)： H[0, n] = 1 for all n If 2h  m < 2h+1 H[m, n] = 1 for (m − 2h)2k−h  n < (m − 2h +1/2)2k−h H[m, n] = −1 for (m − 2h +1/2)2k−h  n < (m − 2h +1)2k−h H[m, n] = 0 otherwise 運算量比 Walsh transforms 更少 Applications: localized spectrum analysis, edge detection Transforms Running Time terms required for NRMSE < 105 DFT 9.5 sec 43 Walsh Transform 2.2 sec 65 Haar Transform 0.3 sec 128

24 XIV. Number Theoretic Transform (NTT)
 14-A Definition Number Theoretic Transform and Its Inverse Note： (1) M is a prime number , (mod M): 是指除以 M 的餘數 (2) N is a factor of M−1 (Note: when N  1, N must be prime to M) (3) N−1 is an integer that satisfies (N−1)N mod M = 1 (When N = M −1, N−1 = M −1)

25 (4) α is a root of unity of order N
When α satisfies the above equations and N = M −1, we call α the “primitive root”.

26 Example 1: M = 5  = 2 1 = 2 (mod 5) 2 = 4 (mod 5) 3 = 3 (mod 5) 4 = 1 (mod 5) When N = 4 When N = 2

27 Example 2: M = 7  cannot be 2 but can be 3.  = 2: 1 = 2 (mod 7) 2 = 4 (mod 7) 3 = 1 (mod 7)  = 3: 1 = 3 (mod 7) 2 = 2 (mod 7) 3 = 6 (mod 7) 4 = 4 (mod 7) 5 = 5 (mod 7) 6 = 1 (mod 7)

28 Advantages of the NTT: Disadvantages of the NTT:

29 附錄十三 SCI Papers 查詢方式 我們經常聽到 SCI 論文，impact factor….那麼什麼是 SCI 和 impact factor？什麼樣的論文是 SCI Papers? Impact factor 號如何查詢？ SCI 全名： Science Citation Index (A) SCI 相關網站：ISI Web of Knowledge 連結至 ISI Web of Knowledge 若出現「You do not have a session」 則按 establish a new session 註：必需要在台大上網，或是在其他有付錢給 ISI 的學術單位上網， 才可以使用 ISI Web of Knowledge

30 (B) 若要找某個期刊是否為 SCI journal，以及它的 impact factor
先點選 Search for a specific journal，再按 SUBMIT 再輸入期刊的名稱，再按 SEARCH 建議用 Title Word，這樣只需知道部分期刊名稱即可查詢

31 若有搜尋到，則代表這個期刊是 SCI 期刊 並且會顯示出這個期刊的 impact factor Impact Factor (影響係數)

32 (C) 關於 impact factor (影響係數)：
若一個 journal 裡面的文章，被別人引用的次數越多，則這個 journal 的 impact factor 越高 一般而言， impact factor 在 1.5 以上的 journals，已經算是高水準的期刊 Nature 的 impact factor 為 36.1 Science 的 impact factor 為 31.4 IEEE 系列的期刊的 impact factors 通常在 1 到 5 之間 IEEE Trans. Image Processing的 impact factors 在 3.0 左右 IEEE Trans. Signal Processing的 impact factors 在 2.65 左右 中等水準的期刊的 impact factors 在 0.6 到 1.5 之間

33 (D) 要查詢一個領域有哪些 SCI journals
方法一 連結至 ISI Web of Knowledge 之後，點選 View a group of journals by 「Subject Category」，再按 SUBMIT

34 接著，再點選要查詢的 category，再按 SUBMIT，即可顯示出這一類的 SCI journals

35 要查詢一個領域有哪些 SCI journals
方法二 連結至 ISI Web of Knowledge 之後，點選 Search for a specific journal，SUBMIT 之後 左邊選用 Title Word，右邊輸入關鍵字 再按 Search 之後，即可找到所有期刊名稱當中有包含這個關鍵字的 journals

36 (E) EI (Engineering Village)
官方網站： 查詢期刊或研討會是否為 EI (F) SSCI (Social Science Citation Index) 比較偏向於社會科學

37 寫論文和投稿的經驗談 研究生經常會寫論文並且投稿。要如何讓論文投稿之後能夠順利的被接受，相信是同學們所期盼的，畢竟每篇論文都是大家花了不少時間的心血結晶，若論文能夠順利的被接受，也代表了自己的成果總算獲得了肯定。然而，影響論文是否被接受的因素很多，一個好的研究成果，還是配合好的編寫技巧，才可以被一流的期刊或研討會所接受。以下是個人關於論文編寫與投稿的經驗談： (1) 你的論文的「賣點」(優點) 是什麼？人家有沒有辦法一眼看得出來你論文的「賣點」？ 寫論文其實就是在推銷商品，而所謂的「商品」，就是你的「研究成果」。要說服人家接受你的商品，首先就是要強調你的商品的「賣點」。 (2) 和既有的方法的比較是否足夠？ 要證明你所提出的方法是有效的，最好的方式，就是和既有的方法相比較，而且比較的對象越多越好，越新越好。

38 (3) 和前人的方法相比，你的方法創新的地方在何處？ 審稿者是否能看得出來你論文創新的地方？
(4) 就算你的文章和理論相關，最好也多提出實際應用的例子 (5) 參考資料越多越好，越新越好 (6) Previous work (前人已經提出的概念) 精簡介紹即可，多強調自己的貢獻。Introduction 加上 Previous work 最好不要超過一篇論文的四分之一 (7) 英文表達能力要有一定的水準 (8)可以多用數學式和圖來解釋概念，有時會比文字還清楚 通常東方人英文表達能力有限。審稿者經常會看你們的圖表和數學式(而非文字) 來判斷你們論文的品質 (9) 同樣的道理，可以用「條列式」的方式來取代一大段文字來描述方法的觀念、流程、或優點

39 (10) 可以用 Conference 的期限來要求自己多寫研討會論文，之後再一個一個改成期刊論文投稿，如此一年的論文量將很可觀
(11)多注意格式，不同的期刊或研討會，對格式的要求也不同 (12) 最後，問自己一個問題： 如果你是審稿者，你會滿意你寫的這一篇論文嗎？ 若答案是肯定的再投稿