Điều mà FFT thật sự cho bạn thấy

Câu hỏi

Chơi đàn dương cầm — c và E cùng nhau. Tai của bạn nghe thấy một âm thanh. Nhưng âm thanh đó là hai tần số cực đại: 261.6 Hz và 329.6 Hz. Cơ thể của bạn tách biệt — các tế bào tóc khác nhau cộng hưởng với tần số khác nhau, gửi tín hiệu khác nhau đến não.

Biến đổi nhanh hơn làm điều tương tự, nhưng với con số thay vì tế bào tóc. Cho nó một tín hiệu (một chuỗi các mẫu tần số theo thời gian) và nó trở lại danh sách tần số và sức mạnh của chúng. Nó trả lời: Tần số nào hiện diện, và bao nhiêu của mỗi thứ?

Điều gì đang thực sự xảy ra

Một dấu hiệu lấy mẫu qua thời gian là một danh sách các số: độ lớn ở mỗi điểm mẫu. Một đoạn phim 1 giây với tốc độ 44.100 Hz là 44.100 con số. Những con số này miêu tả tín hiệu trong miền ** — độ lớn như một chức năng của thời gian.

FFT chuyển sang miền tần số ** — độ lớn như một chức năng của tần số. Cùng thông tin, đại diện khác nhau. Giống như chuyển giao giữa các tọa độ Catesian và cực: không có gì được tạo ra hoặc phá hủy, chỉ được tái tạo.

Các lõi toán học: mỗi tín hiệu tuần hoàn có thể được viết như một tổng các sóng sin và cô sin ở tần số khác nhau. Đây là định lý Fourier (1807). FFT tính toán hệ số của tổng số đó — mỗi tần số đều có tín hiệu.

Sao lại là "Fast"

Cách ngây thơ để tính toán biến đổi Fourier yêu cầu Hoạt động N2 cho mẫu N. Với 1024 mẫu, đó là khoảng 1 triệu ca phẫu thuật. Thuật toán Cooley-Tukey (1965) giảm điều này thành N.log2(N) — khoảng 10.000 ca phẫu thuật cho cùng một đầu vào. Tăng tốc 100x. Với một triệu mẫu, tốc độ tăng tốc là 50.000x.

Thủ thuật: chia N-point ra làm hai biến đổi N/2 điểm, một cách đệ quy. Điều này đòi hỏi N phải là một mũ 2 (hoặc bạn pad với số không). Mỗi phần của vấn đề. Hoạt động "Bầy cánh" kết hợp các nửa:

X[k]     = Even[k] + W · Odd[k]
X[k+N/2] = Even[k] - W · Odd[k]

Nơi mà W là một số mũ phức tạp (một vòng quay trong máy bay phức tạp). Cùng hai điểm nhỏ cho bạn hai điểm xuất. Đó là lý do tại sao thuật toán là " Nhanh" - nó tái sử dụng mỗi phép tính hai lần.

PinePaper thực hiện là một sách giáo khoa Cooley-Tukey radix-2 DIT (giải quyết theo thời gian). 40 dòng JavaScript. Chúng tôi viết nó từ đầu thay vì nhập khẩu thư viện vì chúng tôi muốn học sinh có thể đọc được nguồn gốc và hiểu mọi dòng.

Những thanh gỗ này có nghĩa gì

Khi bạn thấy một máy phân tích quang phổ — thanh song nhảy theo âm nhạc — mỗi thanh đại diện cho một thùng rác tần số. Chiều cao là độ lớn (sức mạnh) của tần số đó trong tín hiệu hiện tại.

• Một làn sóng sin thuần khiết sản xuất một thanh cao ở tần số của nó và không có gì khác.
• Một làn sóng vuông tạo ra thanh ở cơ bản và tất cả các điều hòa kì lạ (số 3, 5, 7...), giảm xuống như 1/n. Đó là lý do tại sao sóng vuông nghe có vẻ "luzzy" - chúng chứa năng lượng tần số cao mà sin tinh khiết thì không.
• Tiếng ồn trắng tạo ra thanh cao bằng nhau ở khắp mọi nơi. Mỗi tần số hiện diện với xác suất tương đương.
• Một giọng nói của con người tạo ra một nguyên tắc cơ bản (các bạn nghe) cộng với các hình thức - những đỉnh điểm cộng hưởng từ hình dạng đường thanh quản của bạn phân biệt các nguyên âm.

Ba người đầu tiên ở dưới — nhấn vào giữa chúng. Độ cao là công thức, không phải là một bức vẽ: sin là 1 tại cơ bản, sóng vuông là chính xác 1/n về điều hòa kỳ lạ.

Cửa sổ: Tại sao quan trọng cạnh

Có một cái bẫy. FFT giả định tín hiệu lặp lại mãi mãi. Nhưng mẫu của chúng tôi có hạn — nó bắt đầu và dừng lại. Nếu tín hiệu không xuất hiện ở điểm 0 tại cả hai điểm cuối, sự cắt giảm đột ngột tạo ra mức độ cao nhân tạo. Cái này gọi là rò rỉ thông thường **.

Sửa chữa: nhân tín hiệu với một hàm window mà vòi bóng mịn đến 0 ở cạnh. Cửa sổ chung:

• Hannn (tiếng chuông: mục đích tốt chung, mất độ phân giải tần số
• Hamming: tương tự như Hann nhưng không đạt được zero tại cạnh, một chút tốt hơn sidelobe đàn áp
• Blackman: thùy chính hẹp hơn, tốt hơn để đàn áp, mất độ phân giải tần số

Lựa chọn luôn là sự đánh đổi giữa độ phân giải tần số (chính xác bạn có thể xác định tần số) và sự rò rỉ quang phổ (bao nhiêu năng lượng chảy vào các thùng kế cận). Không có cửa sổ hoàn hảo. Đây là hậu quả của nguyên tắc bấp bênh — bạn không thể có sự hiểu biết chính xác về thời gian và tần số cùng lúc.

Nơi FFT sống

Bạn tương tác với kết quả FFT liên tục:

• MP3 và AAC nén: chuyển đổi âm thanh thành miền tần số, bỏ tần số dưới ngưỡng thính giác, nén những gì còn lại. Sự biến đổi là toàn bộ cơ sở của việc nén âm thanh mất mát.
• JPEG nén: phiên bản 2D (DCT) biến 8×8 khối ảnh thành các miền tần số, định lượng thành các thành phần tần số cao. Đó là lý do đồ tạo tác JPEG xuất hiện như những khối.
• WiFi và 5G: Bộ mã DM chia dữ liệu qua nhiều tần số thấp hơn. FFT chuyển đổi giữa sự truyền tải thời gian và biểu tượng dữ liệu của tần số-domain.
• MRI hình ảnh: tín hiệu thô từ máy quét MRI trong không gian tần số. Nghịch đảo FFT tái tạo ảnh không gian. Mỗi lần chụp cộng hưởng từ bạn từng thấy là một biến đổi bốn đảo ngược.
• Shazam: tính toán chữ phổ (FFT trên cửa sổ trượt), chiết xuất đỉnh, khớp mẫu với cơ sở dữ liệu. FFT là bước đầu tiên trong việc nhận ra mọi bài hát.

Một thuật toán 60 tuổi, trong túi, chạy hàng tỉ lần mỗi ngày.

Thử đi

Mở PinePaper, chọn bộ phân tích Spectrum. Tạo ra một làn sóng vuông. Hãy nhìn thanh ngang — anh sẽ thấy những điều hòa kì lạ rơi xuống như 1/n. Chuyển sang cưa răng cưa — bây giờ tất cả các điều hòa có mặt, giảm xuống như 1/n. Chuyển sang tiếng ồn — quang phổ phẳng, mọi tần số đều có khả năng như nhau.

Thay đổi chức năng cửa sổ. Xem cách Hann làm mịn quang phổ bằng giá của đỉnh núi rộng hơn. Chuyển sang người da đen — những đỉnh hẹp hơn nhưng những quả cầu thấp hơn.

Anh không đọc về FFT. Bạn đang đo tín hiệu và quan sát những gì các biến thể tiết lộ. Đó là sự khác biệt giữa hiểu biết và hiểu biết.

Tham khảo

• Briggs, E.O. (1998). Biến hình nhanh và ứng dụng nhanh. Phòng khách.
• Cooley, J.W. & Tukey, J.W. (1965). Thuật toán cho sự tính toán của các bộ tứ phức tạp. Mathematics of Compution, 19(90), 297-301.
• Fourier, J. (1822). Véoreie analytique de la chaleur*. Paris: Firmin Didot.
• Harris F.J. (1978). Sử dụng các cửa sổ để phân tích Harmon với biến hình bộ tứ rời rạc. Procress of the IEE, 66(1), 51-83.
• Oppenheim, A.V. & Schafer, R.W. (2009). Dis ule-Time Tiến hành tín hiệu thời gian (3rd ed.). Phòng khách.
• Shannon, C.E. (1949). Liên lạc trong sự hiện diện của tiếng ồn. Thuyết phục của IRE, 37(1), 10-21.
• Smith, S.W. (1997). Hướng dẫn của các nhà khoa học và kỹ sư để xử lý tín hiệu kỹ thuật số. Nhà xuất bản kỹ thuật California.
• Wang, A., et al. (2003). Thuật toán tìm kiếm âm thanh công nghiệp-Strength. Dự đoán của ISMIR 2003. Thuật toán lấy dấu vân tay của Shazam
• Wallace, G.K. (1981). Tiêu chuẩn nén JPEG vẫn còn. Cmunications of the ACM, 34(4), 3044.

---

PinePaper's FFT là một bộ lọc thông thường và cầu cao. Hãy thử miễn phí tại [PPPP. studio/ditor].