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

Câu hỏi

Chơi đàn dương cầm — chẳng hạn như C và E. 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. Cochlea tách chúng ra — các tế bào tóc khác nhau cộng hưởng với nhau ở 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 lãnh thổ thời gian — vô hạn như một chức năng thời gian.

FFT chuyển đổi điều này sang miền tần số ** — cường độ như một hàm 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ố đó — bao nhiêu của mỗi tần số trong 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 nó thành N.log2(N) — khoảng 10.000 thao tác 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 tính toán 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 thanh nhảy theo âm nhạc — mỗi thanh tượng trưng 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. Đây là lý do tại sao sóng vuông nghe có vẻ như "luzzy" - chúng chứa năng lượng tần số cao mà sin tinh khiết không có.
• ** 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 (tiếng ném bạn nghe) cộng với các dạng hình mẫu — những đỉnh kết hợp với hình dạng của đường thanh quản phân biệt các nguyên âm.

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 ta có hạ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 một 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.

được rồi

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 những thanh chắn - bạn sẽ thấy những âm thanh kỳ lạ rơi xuống như 1/n. Chuyển sang một cái cưa răng cưa — bây giờ tất cả các âm thanh hiện hữu, rơi xuống như 1/n. Chuyển sang tiếng ồn — quang phổ phẳng, mỗi tần số tương tự.

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 Blackman — đỉnh hẹp hơn nhưng 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. (1991). Tiêu chuẩn nén JPEG vẫn còn. Cmunications of the ACM, 34(4), 3044.

---

PinePaper của FFT là một bộ lọc thông thường và cầu cao. Thử miễn phí ở [PPPPP. studio/ditor].