Bài 20: Spotify và YouTube nén âm thanh, video ra sao? Biến đổi Fourier giải thích đơn giản

Một bài hát trên đĩa CD nặng hàng chục MB, nhưng Spotify phát nó qua mạng 4G mượt mà. Bí mật là nén dữ liệu – và trái tim của nhiều thuật toán nén là một ý tưởng toán học từ năm 1822: mọi âm thanh đều có thể tách thành tổng của các "nốt" sóng đơn giản.

Bài thứ hai mươi của chuyên mục "Thuật toán trong đời sống": biến đổi Fourier và nén âm thanh, hình ảnh.

1. Âm thanh là một dãy số

Máy tính ghi âm bằng cách đo độ rung của âm thanh hàng chục nghìn lần mỗi giây. Đĩa CD dùng 44.100 mẫu/giây, mỗi mẫu 16 bit (chuẩn do Sony và Philips thống nhất năm 1979). Theo định lý lấy mẫu của Shannon (1949), muốn ghi lại đầy đủ âm thanh có tần số đến W thì cần lấy mẫu ít nhất 2W lần mỗi giây – tai người nghe được đến khoảng 20.000 Hz, nên 44.100 là đủ.

2. Ý tưởng của Fourier

Năm 1822, nhà toán học Pháp Joseph Fourier công bố công trình "Lý thuyết giải tích về nhiệt". Một ý tưởng then chốt trong đó: một tín hiệu phức tạp có thể được biểu diễn như tổng của các sóng sin với tần số khác nhau. Giống như một hợp âm piano là tổng của vài nốt nhạc.

• Biến đổi Fourier rời rạc (DFT): từ dãy mẫu âm thanh, tính ra "mỗi nốt tần số mạnh bao nhiêu".
• Biến đổi Fourier nhanh (FFT): năm 1965, Cooley và Tukey công bố thuật toán chỉ cần khoảng N log N phép tính thay vì N² – với N = 1 triệu mẫu, nhanh hơn hàng chục nghìn lần. FFT thường được xếp vào nhóm những thuật toán có ảnh hưởng lớn nhất thế kỷ 20.

3. Thử nén một "bài hát" tí hon

Chương trình dưới tạo một tín hiệu 64 mẫu gồm một nốt mạnh, một nốt yếu và chút nhiễu, rồi chỉ giữ lại những hệ số Fourier lớn nhất và khôi phục lại:

Nén tín hiệu bằng biến đổi Fourier

#include <bits/stdc++.h>
using namespace std;
typedef complex<double> cd;
const double PI = acos(-1.0);
vector<cd> dft(const vector<cd>& x, int sign){   // sign = -1: biến đổi; +1: biến đổi ngược
    int n = x.size(); vector<cd> X(n);
    for(int k = 0; k < n; k++)
        for(int t = 0; t < n; t++) X[k] += x[t] * polar(1.0, sign * 2 * PI * k * t / n);
    return X;
}
int main(){
    int n = 64; mt19937 rng(1); uniform_real_distribution<double> noise(-0.05, 0.05);
    vector<cd> x(n);
    for(int t = 0; t < n; t++)
        x[t] = sin(2*PI*3*t/n) + 0.5*sin(2*PI*10*t/n) + noise(rng);
    vector<cd> X = dft(x, -1);
    for(int keep : {64, 8, 4, 2}){
        vector<int> idx(n); iota(idx.begin(), idx.end(), 0);
        sort(idx.begin(), idx.end(), [&](int a, int b){ return abs(X[a]) > abs(X[b]); });
        vector<cd> Y(n);
        for(int i = 0; i < keep; i++) Y[idx[i]] = X[idx[i]];    // chỉ giữ hệ số lớn nhất
        vector<cd> y = dft(Y, +1);
        double err = 0;
        for(int t = 0; t < n; t++) err = max(err, abs(x[t].real() - y[t].real() / n));
        printf("Giu %2d/64 he so: sai so lon nhat = %.3f\n", keep, err);
    }
}

import cmath, math, random

def dft(x):
    # Biến đổi Fourier rời rạc: tách tín hiệu thành các "nốt" tần số
    n = len(x)
    return [sum(x[t] * cmath.exp(-2j * math.pi * k * t / n) for t in range(n)) for k in range(n)]

def idft(X):
    n = len(X)
    return [sum(X[k] * cmath.exp(2j * math.pi * k * t / n) for k in range(n)).real / n for t in range(n)]

random.seed(1)
n = 64
# Âm thanh giả lập: nốt 3 Hz mạnh + nốt 10 Hz yếu + chút nhiễu
x = [math.sin(2 * math.pi * 3 * t / n) + 0.5 * math.sin(2 * math.pi * 10 * t / n)
     + random.uniform(-0.05, 0.05) for t in range(n)]
X = dft(x)
for keep in [64, 8, 4, 2]:
    idx = sorted(range(n), key=lambda k: -abs(X[k]))[:keep]   # giữ các hệ số lớn nhất
    Y = [X[k] if k in idx else 0 for k in range(n)]
    y = idft(Y)
    err = max(abs(a - b) for a, b in zip(x, y))
    print(f"Giu {keep:2d}/64 he so ({keep / n:5.1%}): sai so lon nhat = {err:.3f}")

Kết quả chạy (bản Python):

Giu 64/64 he so (100.0%): sai so lon nhat = 0.000
Giu  8/64 he so (12.5%): sai so lon nhat = 0.047
Giu  4/64 he so ( 6.2%): sai so lon nhat = 0.051
Giu  2/64 he so ( 3.1%): sai so lon nhat = 0.546

Chỉ cần 4/64 hệ số (khoảng 6%), tín hiệu khôi phục gần như nguyên vẹn – phần sai số còn lại chủ yếu là nhiễu. (Mỗi nốt sin cần 2 hệ số, nên 2 nốt cần 4 hệ số; giữ 2 hệ số thì mất hẳn nốt yếu.) Đây chính là nguyên lý của nén có mất mát: bỏ đi những thành phần ít quan trọng.

4. MP3, Spotify, JPEG và YouTube

• MP3: theo Viện Fraunhofer IIS (Đức), nơi phát triển MP3, từ năm 1979 Karlheinz Brandenburg đã áp dụng các nguyên lý tâm lý học âm thanh – bỏ đi những âm thanh tai người khó nghe thấy. Một file MP3 chỉ chiếm khoảng 10% dung lượng file gốc.
• Spotify: theo trang hỗ trợ chính thức, chất lượng âm thanh có các mức khoảng 24, 96, 160 và 320 kbit/s; tài khoản Premium có thêm chất lượng lossless (không mất mát) đến 24-bit/44,1 kHz.
• JPEG: dùng biến đổi cosin rời rạc (DCT) – một "họ hàng" của Fourier do Nasir Ahmed và cộng sự công bố năm 1974 – áp dụng trên từng khối ảnh nhỏ.
• YouTube: theo trang hỗ trợ của YouTube, video có thể dùng các chuẩn nén như H.264 và VP9; các chuẩn này đều dựa trên những biến đổi tương tự DCT.

Nén có mất mát (MP3, JPEG, video) bỏ bớt chi tiết để file rất nhỏ. Nén không mất mát (ZIP, FLAC, mã Huffman ở Bài 8) giữ nguyên 100% dữ liệu nhưng nén được ít hơn.

5. Bạn học được gì từ đây?

• Đổi cách nhìn dữ liệu (từ thời gian sang tần số) có thể làm bài toán trở nên dễ.
• FFT cũng là "vũ khí" trong lập trình thi đấu: nhân hai đa thức bậc n trong O(n log n).
• Nén dữ liệu luôn là sự đánh đổi giữa dung lượng và chất lượng.

Bài tập luyện tập

• CSES – Signal Processing (giải nhanh bằng FFT)
• Sửa code: thêm một nốt thứ ba. Cần giữ bao nhiêu hệ số để khôi phục tốt?

📖 ĐỌC TIẾP: THUẬT TOÁN TRONG ĐỜI SỐNG

Bài 21: Chia tiền nhóm sao cho ít lần chuyển khoản nhất? Thuật toán tham lam

Đọc tiếp: chia tiền nhóm →

← Bài trước: giao thông & luồng cực đạiXem tất cả 27 bài →

Nguồn tham khảo

• Trinity College Dublin – Joseph Fourier (W. W. Rouse Ball)
• Cooley & Tukey (1965) – An Algorithm for the Machine Calculation of Complex Fourier Series
• Shannon (1949) – Communication in the Presence of Noise
• Fraunhofer IIS – MP3 history
• Spotify Support – Audio quality
• YouTube Help – Recommended upload encoding settings
• IEEE Spectrum – Compression algorithms (DCT, Nasir Ahmed)
• Purdue – JPEG Image Coding lab (DCT)