Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Toán cho CNTT] FFT cơ số 2 (Cooley-Tukey)

    FFT cơ số 2 (radix-2 Cooley-Tukey)

    Khi nnn là lũy thừa của 2, DFT tính được trong O(nlog⁡n)O(n\log n)O(nlogn) bằng cách chia đôi đệ quy:

    X[k]=E[k]+e−j2πk/nO[k],X[k+n/2]=E[k]−e−j2πk/nO[k]X[k] = E[k] + e^{-j2\pi k/n} O[k], \quad X[k+n/2] = E[k] - e^{-j2\pi k/n} O[k]X[k]=E[k]+e−j2πk/nO[k],X[k+n/2]=E[k]−e−j2πk/nO[k]

    với EEE là FFT các chỉ số chẵn, OOO là FFT các chỉ số lẻ. Kết quả phải trùng khớp DFT trực tiếp.

    Ví dụ

    Với x=[1,2,3,4]x = [1,2,3,4]x=[1,2,3,4]: X=[10, −2+2j, −2, −2−2j]X = [10,\ -2+2j,\ -2,\ -2-2j]X=[10, −2+2j, −2, −2−2j].

    • Định dạng đầu vào:

      Dòng 1: nnn (lũy thừa của 2). Dòng 2: nnn số thực x[t]x[t]x[t].

    • Ràng buộc đầu vào:

      n∈{1,2,4,8,16,32,64}n \in \{1,2,4,8,16,32,64\}n∈{1,2,4,8,16,32,64}; ∣x[t]∣≤1000|x[t]| \le 1000∣x[t]∣≤1000.

    • Định dạng đầu ra:

      Gồm nnn dòng, dòng kkk là phần thực và phần ảo của X[k]X[k]X[k], 4 chữ số thập phân.

    Ví dụ:

    Đầu vào:

    4
1 2 3 4

    Đầu ra:

    10.0000 0.0000
-2.0000 2.0000
-2.0000 0.0000
-2.0000 -2.0000

    Giải thích:

    FFT cho cung ket qua DFT: X=[10, -2+2j, -2, -2-2j].

    Đang tải editor...