Slides:



Advertisements
Similar presentations
1 時 頻 分 析 近 年 來 的 發 展時 頻 分 析 近 年 來 的 發 展 丁 建 均 國立台灣大學電信工程學研究所 Recent Development of Time-Frequency Analysis.
Advertisements

Chapter 2 Combinatorial Analysis 主講人 : 虞台文. Content Basic Procedure for Probability Calculation Counting – Ordered Samples with Replacement – Ordered.
663 Chapter 14 Integral Transform Method Integral transform 可以表示成如下的積分式的 transform  kernel Laplace transform is one of the integral transform 本章討論的 integral.
Final Review Chapter 1 Discrete-time signal and system 1. 模拟信号数字化过程的原理框图 使用 ADC 变换器对连续信号进行采样的过程 使用 ADC 变换器对连续信号进行采样的过程 x(t) Analog.
數位訊號處理 第4章 離散時間訊號與LTI系統之傅利葉分析
無線傳輸 無線傳輸概念之媒介 無線傳輸模型 調變技術 多重存取
第十九课 旅行.
第一章 绪论.
-Artificial Neural Network- Hopfield Neural Network(HNN) 朝陽科技大學 資訊管理系 李麗華 教授.
XI. Hilbert Huang Transform (HHT)
A TIME-FREQUENCY ADAPTIVE SIGNAL MODEL-BASED APPROACH FOR PARAMETRIC ECG COMPRESSION 14th European Signal Processing Conference (EUSIPCO 2006), Florence,
Chapter three the Z Transform Z 变换
3-3 Modeling with Systems of DEs
Operators and Expressions
Euler’s method of construction of the Exponential function
RSA-256bit Digital Circuit Lab TA: Po-Chen Wu.
-Artificial Neural Network- Adaline & Madaline
AN INTRODUCTION TO OFDM
IV. Implementation IV-A Method 1: Direct Implementation 以 STFT 為例
Applications of Digital Signal Processing
期末考的範圍遠遠多於期中考,要了解的定理和觀念也非常多
V. Homomorphic Signal Processing
第 2 章 物理层.
模式识别 Pattern Recognition
Differential Equations (DE)
二、現代的加解密法:RSA 非對稱式密碼系統的一種。
Chapter 4 歸納(Induction)與遞迴(Recursion)
IX. Basic Implementation Techniques and Fast Algorithm
調變技術 Modulation 陳哲儀 老師 行 動 網 路 技 術 調變技術 Modulation 陳哲儀 老師 元培資管系 陳哲儀 老師.
期末考的範圍遠遠多於期中考,要了解的定理和觀念也非常多
Sampling Theory and Some Important Sampling Distributions
32位元處理器之定點數MFCC演算法的改進與探討 Improvement and Discussion of MFCC Algorithm on 32-bit Fixed-point Processors 學生:陳奕宏 指導教授:張智星.
X. Other Applications of Time-Frequency Analysis
Digital Terrain Modeling
無線通訊系統概論 行動通訊與網路 Chapter 7 多重分工技術.
II. Short-time Fourier Transform
無線通訊系統模擬 姓名:顏得洋 學號:B
主讲人: 吕敏 { } Spring 2016,USTC 算法基础 主讲人: 吕敏 { } Spring 2016,USTC.
聲轉電信號.
VI. Brief Introduction for Acoustics
第7章 展頻.
时分多路复用 统计时分多路复用 频分多路复用 波分多路复用 码分多路复用 总线结构多机系统的信道共享技术
一般論文的格式 註:這裡指的是一般 journal papers 和 conference papers 的格式。
4-5 数论基础.
Channel Multiplexing 陳洋升 (2018/9/10).
Advanced Digital Signal Processing 高等數位訊號處理
Chp.4 The Discount Factor
第三章 付里叶分析 离散付氏级数的数学解释(The Mathematical Explanation of DFS)
1 离散信号 2019/4/10.
XIV. Orthogonal Transform and Multiplexing
VII. Data Compression (A)
每周三交作业,作业成绩占总成绩的15%; 平时不定期的进行小测验,占总成绩的 15%;
Chp.4 The Discount Factor
公钥密码学与RSA.
Chp.4 The Discount Factor
WIRELESS LAN B 邱培哲 B 張宏安.
 14-B 餘數的計算 (1) x (mod M) 的值,必定為 0 ~ M −1 之間
Q & A.
名词从句(2).
96學年度第二學期電機系教學助理課後輔導進度表(三)(查堂重點)
IV. Implementation IV-A Method 1: Direct Implementation 以 STFT 為例
XIV. Orthogonal Transform and Multiplexing
本講義為使用「訊號與系統,王小川編寫,全華圖書公司出版」之輔助教材
II. Short-time Fourier Transform
LED可見光通訊技術 班級:微電三甲 學號:4A23A903 姓名:黃敏誠.
Principle and application of optical information technology
CDMA.
Gaussian Process Ruohua Shi Meeting
移动计算技术 (Mobile Computing,MC)
Presentation transcript:

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)

(4) α is a root of unity of order N When α satisfies the above equations and N = M −1, we call α the “primitive root”. 的求法與 N−1 一樣 is an integer that satisfies mod M = 1

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

Example 2: M = 7 , N = 6 :  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)

Advantages of the NTT: Disadvantages of the NTT:

 14-B 餘數的計算 (1) x (mod M) 的值,必定為 0 ~ M −1 之間 (2) a + b (mod M) = {a (mod M) + b (mod M)} (mod M) 例: 78 + 123 (mod 5) = 3 + 3 (mod 5) = 1 (Proof): If a = a1M + a2 and b = b1M + b2 , then a + b = (a1 + b1)M + a2 + b2 (3) a  b (mod M) = {a (mod M)  b (mod M)} (mod M) 例: 78  123 (mod 5) = 3  3 (mod 5) = 4 a  b = (a1 b1M + a1b2 + a2b1)M + a2b2

在 Number Theory 當中 只有 M2 個可能的加法, M2 個可能的乘法 可事先將加法和乘法的結果存在記憶體當中 需要時再 “LUT” LUT : lookup table

 14-C Properties of Number Theoretic Transforms P.1) Orthogonality Principle proof : P.2) The NTT and INTT are exact inverse proof :

f(n) = f(Nn) F(k) = F(Nk) f(n) = f(Nn) F(k) = F(Nk) P.3) Symmetry f(n) = f(Nn) F(k) = F(Nk) f(n) = f(Nn) F(k) = F(Nk) NTT NTT P.4) INNT from NTT  Algorithm for calculating the INNT from the NTT (1) F(-k) : time reverse F0, F1, F2, …, FN-1 F0, FN-1, …, F2, F1 (2) NTT[ F(k) ] (3) 乘上 time reverse

P.5) Shift Theorem P.6) Circular Convolution (the same as that of the DFT) P.7) Parseval’s Theorem

P.8) Linearity   P.9) Reflection If then

 14-D Efficient FFT-Like Structures for Calculating NTTs  If N (transform length) is a power of 2, then the radix-2 FFT butterfly algorithm can be used for efficient calculation for NTT. Decimation-in-time NTT Decimation-in-frequency NTT  The prime factor algorithm can also be applied for NTTs.

where One N-point NTT Two (N/2)-point NTTs plus twiddle factors

Original sequence f(n) = (1, 2, 0, 0) N = 4, M = 5 Permutation (1, 0, 2, 0) After the 1st stage (1, 1, 2, 2) After the 2nd stage F(k) = (3, 0, 4, 2) α0=1 α0=1 Bit reversal α2=4 α1=2 α2=4 α0 α2 α3=3

Inverse NTT by Forward NTT : 1) 1/N 2) Time reversal 3) permutation 4) After first stage 5) After 2nd stage α0=1 α0=1 Permutation Time reversal α2=4 α1=2 α2=4 α0 α2 α3=3

 14-E Convolution by NTT 假設 x[n] = 0 for n < 0 and n  K, h[n] = 0 for n < 0 and n  H 要計算 x[n]  h[n] = z[n] 且 z[n] 的值可能的範圍是 0  z[n] < A (more general, A1  z[n] < A1 + T) (1) 選擇 M (the prime number for the modulus operator), 滿足 (a) M is a prime number, (b) M  max(H+K, A) (2) 選擇 N (NTT 的點數), 滿足 (a) N is a factor of M1, (b) N  H+K 1 (3) 添 0: x1[n] = x[n] for n = 0, 1, ……, K 1, x1[n] = 0 for n = K, K +1, ……., N1 h1[n] = h[n] for n = 0, 1, ……, H 1, h1[n] = 0 for n = H, H +1, ……., N 1

(4) X1[m] = NTTN,M{x1[n]}, H1[m] = NTTN,M {h1[n]} NTTN,M 指 N-point 的 DFT (mod M) (5) Z1[m] = X1[m]H1[m], z1[n] = INTTN,M {Z1[m]}, (6) z[n] = z1[n] for n = 0, 1, …., H+K  1 (移去 n = H+K, H+K+1, …… N 1 的點)   (More general, if we have estimated the range of z[n] should be A1  z[n] < A1 + T, then z[n] = ((z1[n] − A1))M + A1

適用於 (1) x[n],h[n]皆為整數 (2) Max(z[n]) − min(z[n]) < M 的情形。 Consider the convolution of (1, 2, 3, 0) * (1, 2, 3, 4) Choose M = 17, N = 8,結果為:

 Max(z[n]) − min(z[n]) 的估測方法 假設 x1  x[n]  x2, 則 (Proof): where h1[m] = h[m] when h[m] > 0 , h1[m] = 0 otherwise h2[m] = h[m] when h[m] < 0 , h2[m] = 0 otherwise

 14-F Special Numbers Fermat Number :   P = 0, 1, 2, 3, 4, 5, ….. Mersenne Number : M = 2p − 1 P = 1, 2, 3, 5, 7, 13, 17, 19 M = 1, 3, 7, 31, 127, 8191, ….. If M = 2p − 1 is a prime number, p must be a prime number. However, if p is a prime number, M = 2p − 1 may not be a prime number.

The modulus operations for Mersenne and Fermat prime numbers are very easy for implementation. 2k  1 Example: 25 mod 7 a = −1 100

 14-G Complex Number Theoretic Transform (CNT) The integer field ZM can be extended to complex integer field If the following equation does not have a sol. in ZM 無解 This means (-1) does not have a square root When M = 4k +1, there is a solution for x2 = −1 (mod M). When M = 4k +3, there is no solution for x2 = −1 (mod M). For example, when M = 13, 82 = −1 (mod 13). 21 = 2, 22 = 4, 23 = 8, 24 = 3, 25 = 6, 26 = 12 = −1, 27 = 11, 28 = 9, 29 = 5, 210 = 10, 211 = 7, 212 = 1 When M = 11, there is no solution for x2 = −1 (mod M).

If there is no solution for x2 = −1 (mod M), we can define an imaginary number i such that i2 = −1 (mod M) Then, “i” will play a similar role over finite field ZM such that plays over the complex field.

 14-H Applications of the NTT NTT 適合作 convolution 但是有不少的限制 新的應用: encryption (密碼學) CDMA

References: (1) R. C. Agavard and C. S. Burrus, “Number theoretic transforms to implement fast digital convolution,” Proc. IEEE, vol. 63, no. 4, pp. 550- 560, Apr. 1975. (2) T. S. Reed & T. K Truoay, ”The use of finite field to compute convolution,” IEEE Trans. Info. Theory, vol. IT-21, pp.208-213, March 1975 (3) E.Vegh and L. M. Leibowitz, “Fast complex convolution in finite rings,” IEEE Trans ASSP, vol. 24, no. 4, pp. 343-344, Aug. 1976. (4) J. H. McClellan and C. M. Rader, Number Theory in Digital Signal Processing, Prentice-Hall, New Jersey, 1979. (5) 華羅庚, “數論導引”, 凡異出版社, 1997。

XIV. Orthogonal Transform and Multiplexing  14-A Orthogonal and Dual Orthogonal Any M  N discrete linear transform can be expressed as the matrix form: Y = A X inner product

Orthogonal: when k  h orthogonal transforms 的例子:  discrete Fourier transform  discrete cosine, sine, Hartley transforms  Walsh Transform, Haar Transform  discrete Legendre transform discrete orthogonal polynomial transforms Hahn, Meixner, Krawtchouk, Charlier

為什麼在信號處理上,我們經常用 orthogonal transform?

 If partial terms are used for reconstruction for orthogonal case, perfect reconstruction: partial reconstruction: K < N reconstruction error of partial reconstruction 由於 一定是正的,可以保證 K 越大, reconstruction error 越小

For non-orthogonal case, perfect reconstruction: partial reconstruction: B = A−1 K < N reconstruction error of partial reconstruction 由於 不一定是正的, 無法保證 K 越大, reconstruction error 越小

 14-B Frequency and Time Division Multiplexing 傳統 Digital Modulation and Multiplexing:使用 Fourier transform  Frequency-Division Multiplexing (FDM) Xn = 0 or 1 Xn can also be set to be −1 or 1 When (1) t  [0, T] (2) fn = n/T it becomes the orthogonal frequency-division multiplexing (OFDM).

Furthermore, if the time-axis is also sampled t ∈ [0,T] sampling for t-axis t = mT/N, m = 0, 1, 2, ….., N−1 then the OFDM is equivalent to the transform matrix of the inverse discrete Fourier transform (IDFT), which is one of the discrete orthogonal transform. Modulation:

Modulation: Demodulation: Example: N = 8 Xn = [1, 0, 1, 1, 0, 0, 1, 1] (n = 0 ~ 7)

 Time-Division Multiplexing (TDM) (also a discrete orthogonal transform)

思考: 既然 time-division multiplexing 那麼簡單 那為什麼要使用 frequency-division multiplexing 和 orthogonal frequency-division multiplexing (OFDM)?

 14-C Code Division Multiple Access (CDMA) 除了 frequency-division multiplexing 和 time-division multiplexing,是否還有其他 multiplexing 的方式? 使用其他的 orthogonal transforms 即 code division multiple access (CDMA) CDMA is an important topic in spread spectrum communication 參考資料 [1] M. A. Abu-Rgheff, Introduction to CDMA Wireless Communications, Academic, London, 2007 [2] 邱國書, 陳立民譯, “CDMA 展頻通訊原理”, 五南, 台北, 2002.

CDMA 最常使用的 orthogonal transform 為 Walsh transform channel 1 channel 2 channel 3 channel 4 channel 5 channel 6 channel 7 channel 8 channel 1

當有兩組人在同一個房間裡交談 (A 和B交談), (C 和D交談) , 如何才能夠彼此不互相干擾? (1) Different Time (2) Different Tone (3) Different Language

CDMA 分為: (1) Orthogonal Type (2) Pseudorandom Sequence Type   Orthogonal Type 的例子: 兩組資料 [1, 0, 1] [1, 1, 0] (1) 將 0 變為 −1 [1, −1, 1] [1, 1, −1] (2) 1, −1, 1 modulated by [1, 1, 1, 1, 1, 1, 1, 1] (channel 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 modulated by [1, 1, 1, 1, -1, -1, -1, -1] (channel 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] (3) 相合 [2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, -2, -2, -2, -2, 0, 0, 0, 0, 2, 2, 2, 2]

demodulation [2, 2, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, -2, -2, -2, -2, 0, 0, 0, 0, 2, 2, 2, 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] 內積 = 8

注意: (1) 使用 N-point Walsh transform 時,總共可以有N 個 channels (2) 除了 Walsh transform 以外,其他的 orthogonal transform 也可以使用 (3) 使用 Walsh transform 的好處

 Orthogonal Transform 共通的問題: 需要同步 synchronization   但是某些 basis, 就算不同步也近似 orthogonal <R1[n], R1[n]> = 8, <R1[n], Rk[n]> = 0 if k  1 <R1[n], Rk[n1]> = 2 or 0 if k  1. 這裡的shift為circular shift

Pseudorandom Sequence Type 不為 orthogonal,capacity 較少 但是不需要同步 (asynchronous) Pseudorandom Sequence 之間的 correlation b1p(t+ 1) + b2p(t + 2) recovered: (若 C(0) = 1, C(2  1)  0) 1, 2 不必一致 C() -axis

CDMA 的優點: (1) 運算量相對於 frequency division multiplexing 減少很多 (2) 可以減少 noise 及 interference的影響 (3) 可以應用在保密和安全傳輸上 (4) 就算只接收部分的信號,也有可能把原來的信號 recover 回來 (5) 相鄰的區域的干擾問題可以減少

相鄰的區域,使用差距最大的「語言」,則干擾最少 B 區 A 區 假設 A 區使用的 orthogonal basis 為 k[n], k = 0, 1, 2, …, N−1 B 區使用的 orthogonal basis 為 h[n], h = 0, 1, 2, …, N−1 設法使 為最小 k = 0, 1, 2, …, N−1, h = 0, 1, 2, …, N−1

附錄十四 3-D Accelerometer 的簡介 許多儀器(甚至包括智慧型手機) 都有配置三軸加速器 可以用來判別一個人的姿勢和動作 註:Gyrator (陀螺儀) 可以用來量測物體旋轉之方向,可補 3-D Accelerometer 之不足,許多儀器 (包括智慧型手機) 也內建陀螺儀之裝置, 3-D Accelerometer Signal Processing 和 gyrator signal processing 經常並用

z-axis y-axis x-axis 根據 x, y, z 三個軸的加速度的變化,來判斷姿勢和動作 平放且靜止時, z-axis 的加速度為 –g = – 9.8

z-axis y: 0 z: -9.8 y-axis tilted by θ z-axis y: -9.8sin θ z: -9.8cos θ y-axis 可藉由加速規傾斜的角度,來判斷姿勢和動作

例子:若將加速規放在腳上……………. 走路時,沿著其中一個軸的加速度變化

應用: 動作辨別 (遊戲機) 運動 (訓練,計步器) 醫療復健,如 Parkinson 患者照顧,傷患復原情形 其他 (如動物的動作,機器的運轉情形的偵測) 3-D Accelerometer Signal Processing 是訊號處理的重要課題之一 一方面固然是因為應用多,另一方面, 3-D Accelerometer Signal 容易受 noise 之干擾,要如何藉由 3-D Accelerometer Signal 來還原動作以及移動速度,仍是個挑戰

期末的勉勵  人生難免會有挫折,最重要的是,我們面對挫折的態度是什麼  長遠的願景要美麗,短期的目標要務實

祝各位同學暑假愉快!   各位同學在研究上或工作上,有任何和 digital signal processing 或 time frequency analysis 方面的問題,歡迎找我來一起討論。