Chương trình C++ tính biến đổi Fourier rời rạc (DFT) bằng phương pháp trực tiếp

Trong biến đổi Fourier rời rạc (DFT), một danh sách hữu hạn được chuyển đổi thành các mẫu cách đều nhau của một hàm thành danh sách các hệ số của một tổ hợp hữu hạn của sóng sin phức. Chúng được sắp xếp theo tần số của chúng, có các giá trị mẫu giống nhau, để chuyển đổi hàm được lấy mẫu từ miền ban đầu (thường là thời gian hoặc vị trí dọc theo một đường) sang miền tần số.

Thuật toán

Bắt đầu
    Lấy một biến M và khởi tạo nó bằng một số nguyên
    Khai báo mảng function[M]
    Với i = 0 đến M-1 thực hiện
        function[i] = (((a * (double) i) + (b * (double) i)) - c)
    Kết thúc
    Khai báo mảng sine[M]
    Khai báo mảng cosine[M]
    Với i = 0 đến M-1 thực hiện
        cosine[i] = cos((2 * i * k * PI) / M)
        sine[i] = sin((2 * i * k * PI) / M)
    Kết thúc
    Khai báo DFT_Coeff dft_value[k]
    Với j = 0 đến k-1 thực hiện
        Với i = 0 đến M-1 thực hiện
            dft_value.real += function[i] * cosine[i]
            dft_value.img += function[i] * sine[i]
        Kết thúc
    Kết thúc
    In giá trị
Kết thúc

Mã ví dụ

#include<iostream> 
#include<math.h> 
using namespace std; 

#define PI 3.14159265 

class DFT_Coeff { 
    public: 
    double real, img; 
    DFT_Coeff() { 
        real = 0.0; 
        img = 0.0; 
    } 
}; 

int main(int argc, char **argv) { 
    int M = 10; 
    cout << "Nhập hệ số của hàm tuyến tính đơn giản:\n"; 
    cout << "ax + by = c\n"; 
    double a, b, c; 
    cin >> a >> b >> c; 
    double function[M]; 
    for (int i = 0; i < M; i++) { 
        function[i] = (((a * (double) i) + (b * (double) i)) - c); 
    } 
    cout << "Nhập giá trị K tối đa: "; 
    int k; 
    cin >> k; 
    double cosine[M]; 
    double sine[M]; 
    for (int i = 0; i < M; i++) { 
        cosine[i] = cos((2 * i * k * PI) / M); 
        sine[i] = sin((2 * i * k * PI) / M); 
    } 
    DFT_Coeff dft_value[k]; 
    cout << "Các hệ số là: "; 
    for (int j = 0; j < k; j++) { 
        for (int i = 0; i < M; i++) { 
            dft_value[j].real += function[i] * cosine[i]; 
            dft_value[j].img += function[i] * sine[i]; 
        } 
        cout << "(" << dft_value[j].real << ") - " << "(" << dft_value[j].img << " i)\n"; 
    } 
}

Kết quả

Nhập hệ số của hàm tuyến tính đơn giản: 
ax + by = c 
4 5 6 
Nhập giá trị K tối đa: 10 
Các hệ số là: 
(345) - (-1.64772e-05 i) 
(345) - (-1.64772e-05 i) 
(345) - (-1.64772e-05 i) 
(345) - (-1.64772e-05 i) 
(345) - (-1.64772e-05 i) 
(345) - (-1.64772e-05 i) 
(345) - (-1.64772e-05 i) 
(345) - (-1.64772e-05 i) 
(345) - (-1.64772e-05 i) 
(345) - (-1.64772e-05 i)