FFT — อธิบาย Fast Fourier Transform แบบเข้าใจง่าย

FFT หรือ fast Fourier transform คือวิธีที่รวดเร็วในการคำนวณ discrete Fourier transform (DFT) ถ้าคุณเริ่มจากค่าตัวอย่างที่เว้นระยะเท่ากัน DFT จะบอกว่ามีรูปแบบความถี่ไม่ต่อเนื่องแต่ละแบบอยู่ในค่าตัวอย่างเหล่านั้นมากแค่ไหน

ประเด็นสำคัญคือ FFT ไม่ได้เปลี่ยนผลลัพธ์ มันให้ค่า DFT เดียวกันกับสูตรคำนวณตรงๆ แต่ไปถึงคำตอบนั้นด้วยงานที่ซ้ำซ้อนน้อยกว่ามาก

FFT ในประโยคเดียว

FFT คืออัลกอริทึมที่เร็วกว่า สำหรับหาค่าจำนวนในโดเมนความถี่ชุดเดียวกับที่ DFT นิยามไว้

DFT วัดอะไร

สมมติว่าคุณมีค่าตัวอย่าง $x_0, x_1, \dots, x_{N-1}$ แล้ว DFT จะสร้างค่า $X_0, X_1, \dots, X_{N-1}$ ที่นิยามโดย

$$X_k = \sum_{n=0}^{N-1} x_n e^{-i 2 \pi kn / N}$$

แต่ละค่า $X_k$ วัดว่าข้อมูลสอดคล้องกับรูปแบบความถี่ไม่ต่อเนื่องแบบหนึ่งมากเพียงใด

ถ้าค่าตัวอย่างถูกเก็บอย่างสม่ำเสมอด้วยอัตราการสุ่มตัวอย่าง $f_s$ ช่องความถี่ที่อยู่ติดกันจะห่างกันเป็น

$$\frac{f_s}{N}$$

เงื่อนไขนี้สำคัญมาก ถ้าไม่รู้อัตราการสุ่มตัวอย่าง คุณยังมี bin ของ DFT อยู่ แต่จะยังระบุไม่ได้ว่า bin เหล่านั้นตรงกับความถี่จริงทางกายภาพ เช่น เฮิรตซ์

ทำไม FFT จึงเร็วกว่า

FFT เป็นตระกูลของอัลกอริทึมสำหรับคำนวณ DFT อย่างมีประสิทธิภาพ เคล็ดลับหลักคือใช้โครงสร้างซ้ำในตัวประกอบเลขชี้กำลังเชิงซ้อนให้เกิดประโยชน์ แทนที่จะคำนวณผลรวมที่เกือบเหมือนกันใหม่ตั้งแต่ต้น

เวอร์ชันที่นึกภาพง่ายที่สุดคือ radix-2 FFT ซึ่งทำงานได้เป็นธรรมชาติที่สุดเมื่อ $N$ เป็นกำลังของ $2$ และมันจะแยกทรานส์ฟอร์มความยาว $N$ หนึ่งชุดออกเป็นทรานส์ฟอร์มความยาว $N/2$ สองชุดก่อนจะรวมผลลัพธ์กลับ

สำหรับ DFT แบบคำนวณตรงๆ ปริมาณงานคำนวณจะโตในระดับ $N^2$ แต่สำหรับ FFT ที่ใช้กันทั่วไป จะลดลงเหลือประมาณ $N \log N$

ช่องว่างนี้เองที่ทำให้ FFT สำคัญในทางปฏิบัติ สำหรับอินพุตขนาดเล็ก ทั้งสองวิธีอาจดูพอรับได้ แต่เมื่อข้อมูลมีขนาดใหญ่ FFT จะเร็วกว่าอย่างชัดเจนมาก

FFT แยกงานอย่างไร

แทนที่จะเปรียบเทียบทุกค่าตัวอย่างกับทุกรูปแบบความถี่โดยตรง FFT จะแยกปัญหาออกเป็นทรานส์ฟอร์มที่เล็กลง แล้วค่อยรวมกลับด้วยตัวประกอบเฟส

การแยกแบบมาตรฐานคือ:

1. นำค่าตัวอย่างที่มีดัชนีคู่ไปไว้ในรายการหนึ่ง
2. นำค่าตัวอย่างที่มีดัชนีคี่ไปไว้อีกรายการหนึ่ง
3. คำนวณทรานส์ฟอร์มขนาดเล็กบนแต่ละรายการ
4. รวมผลลัพธ์จากสองส่วนเข้าด้วยกัน

นี่คือแนวคิด divide-and-conquer ที่นำมาใช้กับการวิเคราะห์ความถี่

ตัวอย่าง FFT แบบ 4 จุด

พิจารณาสัญญาณ 4 จุด

$$x = [1, 0, 1, 0]$$

รูปแบบนี้สลับระหว่าง $1$ กับ $0$ ดังนั้นเราคาดว่าจะเห็นโครงสร้างด้านความถี่บางอย่าง แทนที่จะได้ผลลัพธ์ที่แบนราบทั้งหมด

แยกเป็นดัชนีคู่และคี่ได้ดังนี้:

$$x_{\text{even}} = [1, 1], \qquad x_{\text{odd}} = [0, 0]$$

DFT แบบ 2 จุดของส่วนคู่คือ

$$E = [2, 0]$$

และ DFT แบบ 2 จุดของส่วนคี่คือ

$$O = [0, 0]$$

สำหรับ FFT แบบ 4 จุด ขั้นตอนการรวมคือ

$$X_k = E_k + W_4^k O_k, \qquad X_{k+2} = E_k - W_4^k O_k, \qquad k = 0,1$$

โดยที่

$$W_4 = e^{-i 2 \pi / 4}$$

เนื่องจาก $O_k = 0$ การรวมจึงง่ายเป็นพิเศษ:

$$X = [2, 0, 2, 0]$$

ทีนี้มาตีความผลลัพธ์กัน

$X_0 = 2$ คือพจน์ความถี่ศูนย์ ดังนั้นมันสะท้อนค่าเฉลี่ยที่ไม่เป็นศูนย์ของค่าตัวอย่าง ส่วนค่าที่ไม่เป็นศูนย์ที่ $X_2$ จับองค์ประกอบแบบสลับของรูปแบบนี้ในกรณี 4 จุด ถ้าคุณลบค่าเฉลี่ยออกก่อน พจน์ $X_0$ จะหายไป และองค์ประกอบที่สลับกันจะเด่นชัดขึ้น

ตัวอย่างนี้มีขนาดเล็ก แต่แนวคิดเดียวกันใช้ได้กับกรณีใหญ่กว่า คือแก้ทรานส์ฟอร์มย่อยก่อน แล้วค่อยรวมผล แทนที่จะสร้างผลรวมทั้งหมดใหม่ทุกครั้ง

ข้อผิดพลาดที่พบบ่อยเกี่ยวกับ FFT

คิดว่า FFT และ DFT ให้ผลลัพธ์คนละอย่าง

ไม่ใช่ FFT เป็นเพียงวิธีที่เร็วกว่าในการคำนวณ DFT

อ่านค่า bin เป็นความถี่จริงเร็วเกินไป

ตำแหน่งของ bin จะกลายเป็นความถี่จริงได้ก็ต่อเมื่อรู้ระยะห่างของการเก็บตัวอย่างแล้ว ถ้าอัตราการสุ่มตัวอย่างคือ $f_s$ ระยะห่างระหว่าง bin จะเป็น $f_s/N$ สำหรับข้อมูลที่เก็บอย่างสม่ำเสมอ

คิดว่าการ zero-padding เพิ่มข้อมูลใหม่

การ zero-padding อาจทำให้สเปกตรัมดูเรียบขึ้น เพราะเป็นการสุ่มดูทรานส์ฟอร์มพื้นฐานอย่างละเอียดขึ้น แต่ไม่ได้เพิ่มข้อมูลที่วัดมาใหม่

มองข้ามการเตรียมสัญญาณ

การลบค่าเฉลี่ย การใช้หน้าต่าง และการเลือกการสุ่มตัวอย่างอย่างระมัดระวัง อาจมีผลมาก ถ้ามองข้ามเงื่อนไขเหล่านี้ เอาต์พุตของ FFT อาจยังถูกต้องทางคณิตศาสตร์สำหรับค่าตัวอย่างที่ให้มา แต่ทำให้ตีความผิดได้

FFT ใช้ที่ไหนบ้าง

FFT ปรากฏอยู่ทุกที่ที่ต้องการข้อมูลในโดเมนความถี่จากข้อมูลตัวอย่างอย่างรวดเร็ว ตัวอย่างที่พบบ่อยคือการวิเคราะห์สเปกตรัม การกรองสัญญาณ การประมวลผลภาพ การวิเคราะห์การสั่นสะเทือน การแก้สมการเชิงอนุพันธ์เชิงตัวเลข และการคำนวณพหุนามหรือคอนโวลูชันอย่างรวดเร็ว

เหตุผลเป็นเรื่องเชิงปฏิบัติ เพราะหลายการดำเนินการจะง่ายขึ้นหรือเร็วขึ้นหลังจากย้ายจากโดเมนตัวอย่างไปยังโดเมนความถี่

ลองกรณีที่คล้ายกัน

ลองใช้ค่าตัวอย่าง 8 จุดที่เว้นระยะเท่ากันของคลื่นไซน์หนึ่งลูกเต็มคาบ แล้วคำนวณ DFT ด้วยเครื่องคิดเลขหรือสคริปต์ จากนั้นเพิ่มค่าออฟเซ็ตคงที่เข้าไปแล้วเปรียบเทียบเอาต์พุตใหม่ ค่าที่แรงขึ้นที่ $X_0$ เป็นวิธีง่ายๆ ที่ช่วยให้เห็นว่า FFT แยกอะไรออกมา