Advanced Digital Signal Processing 高等數位訊號處理

Presentation on theme: "Advanced Digital Signal Processing 高等數位訊號處理"— Presentation transcript:

1 Advanced Digital Signal Processing 高等數位訊號處理
授課者： 丁 建 均 Office：明達館723室, TEL： 助教信箱： 課程網頁： 歡迎大家來修課，也歡迎有問題時隨時聯絡！

2  評分方式： Basic: 15 scores 原則上每位同學都可以拿到 12 分以上， 另外，上課回答問題，每回答一次加1分 Homework: 60 scores (5 times, 每 3 週一次) 請自己寫，和同學內容極高度相同 ，將扣 70% 的分數 就算寫錯但好好寫也會給 40~95% 的分數， 遲交分數打 8 折，不交不給分。 不知道如何寫，可用 和我聯絡，或於上課時發問 禁止 Ctrl-C Ctrl-V 的情形。 Term paper 25 scores

3 Term paper 25 scores 方式有四種 (1) 書面報告 10頁以上(不含封面)，中英文皆可，11或12的字體，題目可選擇和課 程有關的任何一個主題。 格式和一般寫期刊論文或碩博士論文相同，包括 abstract, conclusion, 及 references，並且要分 sections，必要時有subsections。 References 的寫法, 可參照一般 IEEE 的論文的寫法 鼓勵多做實驗及模擬，有創新更好。 嚴禁 Ctrl-C Ctrl-V 的情形，否則扣 70% 的分數 (2) Tutorial (對既有領域做淺顯易懂的整理) 限十七個名額，和書面報告格式相同，但頁數限制為18頁以上(若為 加強前人的 tutorial，則頁數為 (2/3)N + 13 以上，N 為前人 tutorial 之 頁數)，題目由老師指定，以清楚且有系統的介紹一個主題的基本概 念和應用為要求，為上課內容的進一步探討和補充，交 Word 檔。 選擇這個項目的同學，學期成績加 4分

4 (3) 編輯 Wikipedia 中文或英文網頁皆可，至少 2 個條目，但不可同一個條目翻成中文和英 文。總計 80行以上。限和課程相關者，自由發揮，越有條理、有系統的 越好 選擇編輯 Wikipedia 的同學，請於 6月14日前，向我登記並告知我要編緝的條目(2 個以上)，若有和其他同學選擇相同條目的情形，則較晚向我登記的同學將更換要編緝的條目 書面報告和編輯 Wikipedia，期限是 6月28日

5 Tutorial 可供選擇的題目(共 17 個，可以略做修改)
(1) Guided Filter (2) Recent Development of Signal Sampling Methods (3) Vector Quantization (4) Echo Cancellation (5) Learning Based Denoising Techniques (6) Quantum Signal Processing (7) Learning Based Image Superresolution (8) Learning Based Image Compression Techniques (9) Log-Gabor Transform for Texture Extraction (10) Sparse Representation (11) Image Stitching

6 Tutorial 可供選擇的題目(可以略做修改)
(12) Multimedia Security (13) Image Shadow Removal (14) Topology (15) Image Sharpness (16) Image Registration (17) Speech Enhancement

7 上課時間：14 週 2/22, 3/8, 3/15, 出 HW1 3/22, 3/29, 交 HW1 4/12, 出 HW2 4/19, 4/26, 交 HW2 5/3, 出 HW3 5/10, 5/17, 交 HW3 5/24, 出 HW4 5/31, 6/14, 交 HW4,出 HW5 6/28, 交 HW5 及 term paper 3/1, 4/5, 6/7 放假 原則上: 3n 週出作業, 3n+2 週繳交

8 Matlab Download: 請洽台大各系所 參考書目
預計看書學習所花時間： 3~5 天

9 研究所和大學以前追求知識的方法有什麼不同？
研究所 : 觀念的學習 大學 :

10 Why should we use the Fourier transform?
Question: Why should we use the Fourier transform? Is the Fourier transform the best choice in any condition?

11 I. Introduction Outline Introduction (1.3W) FIR (2W) 1. Filter Design
IIR, Others (1.7W) 2. Homomorphic Signal Processing (1W) Acoustics (1W) 3. Applications Compression, Image (1.3 W) Basic (1W) 4. Fast Algorithms FFT and Convolution (2W) Others (0.3W) Walsh Transform (1W) 5. Orthogonal Transforms Number Theory (0.7 W) OFDM, CDMA (0.7 W)

12 目標： (1) 對 Digital Signal Processing 作更有系統且深入的了解 (2) 學習 Digital Signal Processing 幾個重要子領域的基礎知識

13 Part 1: Filter  Filter 的分類 IIR digital (考慮aliasing) MSE (mean square error) filter FIR minimax frequency sampling analog (技術較早開發)

14 IIR filter 的優點：(1) easy to design
(2) (sometimes) easy to implement 缺點： FIR filter 的優點： 缺點： An FIR filter is impossible to have the ideal frequency response of

15 15 Part 2: Homomorphic Signal Processing  概念：把 convolution 變成 addition Part 3: Applications of DSP filter design, data compression (image, video, text), acoustics (speech, music), image analysis (structural similarity, sharpness), 3D accelerometer

16 16  Part 4: Fast Algorithms  Basic Implementation Techniques Example: one complex number multiplication = ? Real number multiplication. Trade-off: “Multiplication” takes longer than “addition”

17 17  FFT and Convolution Due to the Cooley-Tukey algorithm (butterflies), the complexity of the FFT is: The complexity of the convolution is: 3個 DFTs,

18 18  Part 5: Orthogonal Transforms DFT 的兩個主要用途: Question: DFT 的缺點是什麼？  Walsh Transform (CDMA)  Number Theoretic Transform Orthogonal Frequency-Division Multiplexing (OFDM) Code Division Multiple Access (CDMA)

19 Review 1: Four Types of the Fourier Transform
19 Review 1: Four Types of the Fourier Transform (1) Fourier Transform , Alternative definitions (2) Fourier series (suitable for period function) possible periods: T: 週期 possible frequencies: 頻率和 m 之間的關係： 整數倍

20 20 (3) Discrete-time Fourier transform (DSP 常用) , t : sampling interval (4) Discrete Fourier transform (DFT) (DSP 常用) 頻率和 m 之間的關係： where fs = 1/t (sampling frequency)

21 21  四種 Fourier transforms 的比較 time domain frequency domain (1) Fourier transform continuous, aperiodic continuous, aperiodic (2) Fourier series continuous, periodic (or continuous, only the value in a finite duration is known) discrete, aperiodic (3) discrete-time Fourier transform discrete , aperiodic continuous, periodic (4) discrete Fourier transform discrete, periodic (or discrete, only the value in a finite duration is known) discrete, periodic

22 Review 2: Normalized Frequency
22 Review 2: Normalized Frequency (1) Definition of normalized frequency F: where fs = 1/t (sampling frequency) t : sampling interval (2) folding frequency f0 若以 normalized frequency 來表示， folding frequency = 1/2

23 23 For the discrete time Fourier transform (1) G(f) = G(f + fs) i.e., G(F) = G(F + 1). (2) If g[n] is real G(F) = G*(F) (* means conjugation) 只需知道 G(F) for 0  F  ½ (即 0 < f < f0) 就可以知道全部的 G(F) (3) If g[n] = g[n] (even) G(F) = G(F), g[n] = g[n] (odd) G(F) = G(F) Analog filter: H(f)

24 24  Discrete time Fourier transform of the lowpass, highpass, and band pass filters low pass filter ( pass band 在 fs 的整數倍附近 ) fs (F = 1) (F = 0) fs (F = 1) high pass filter fs (F = 1) F =  (F = 0) F = fs (F = 1) f = fs/2 band pass filter fs (F = 1) F =  (F = 0) F = fs (F = 1)

25 Review 3: Z Transform and Laplace Transform
25 Review 3: Z Transform and Laplace Transform  Z-Transform suitable for discrete signals Compared with the discrete time Fourier transform:

26  Laplace Transform 26 suitable for continuous signals One-sided form
Two-sided form Compared with the Fourier transform:

27 Review 4: IIR Filter Design
27 Review 4: IIR Filter Design Two types of digital filter: (1) IIR filter (infinite impulse response filter) (2) FIR filer (finite impulse response filer) There are 3 popular methods to design the IIR filter.

28 28 Method 1: Impulse Invariance 白話一點，就是直接做 sampling analog filter ha(t) digital filter h[n] Advantage : Simple Disadvantage : (1) infinite (2)

29 29 Method 2: Step Invariance 對 step function 的 response 作 sampling analog filter ha(t) digital filter h[n] step function (continuous form) Laplace transform of u(t): 1 u(t) Fourier transform of u(t): t = 0 step function (discrete form) 1 1 1 1 1 u[n] Z transform of u[n]: n=0

30 30 Step 1 Calculate the convolution of ha(t) and u(t) (其實就是對 ha(t) 做積分) Step 2 Perform sampling for ha,u(t) Step 3 Calculate h[n] from Note: Since so

31 31 Advantage of the step invariance method: ＊主要 Advantage: Disadvantage of the step invariance method: 較為間接，設計上稍微複雜

32 32 Method 3: Bilinear Transform Suppose that we have known an analog filter ha(t) whose frequency response is Ha(f). To design the digital filter h[n] with the frequency response H(f), fold  (, ) fnew  (fs/2, fs/2) fs = 1/t (sampling frequency)  The relation between fnew and fold is determined by the mapping function s: index of the Laplace transform z: index of the Z transform c: some constant

33 The Z transform of the digital filter h[n] is Hz(z)
33 代入 參考page 25、page26 f f  Suppose that the Laplace transform of the analog filter ha(t) is Ha,L(s) The Z transform of the digital filter h[n] is Hz(z)

34 34 fold −  1 fnew fnew/fs c = 2 fold

35 35 analog filter Ha(f) − −fc fc  mapping digital filter H(f) mapping −fs/2 −fc,1 fc,1 fs/2 Advantage of the bilinear transform Disadvantage of the bilinear transform

36 附錄一： 學習 DSP 知識把握的要點 36 (1) Concepts: 這個方法的核心概念、基本精神是什麼
(2) Comparison: 這方法和其他方法之間，有什麼相同的地方？ 有什麼相異的地方 (3) Advantages: 這方法的優點是什麼 (3-1) Why? 造成這些優點的原因是什麼 (4) Disadvantages: 這方法的缺點是什麼 (4-1) Why? 造成這些缺點的原因是什麼 (5) Applications: 這個方法要用來處理什麼問題，有什麼應用 (6) Innovations: 這方法有什麼可以改進的地方 或是可以推廣到什麼地方