当前位置：首页 > PHP

php实现fft

2026-01-29 00:56:40PHP

PHP 实现 FFT（快速傅里叶变换）

快速傅里叶变换（FFT）是一种高效计算离散傅里叶变换（DFT）的算法。PHP 中可以通过自定义函数或调用外部库来实现 FFT。以下是两种实现方式：

自定义 FFT 函数

以下是一个基于递归的 Cooley-Tukey FFT 算法的 PHP 实现：

php实现fft

function fft($real, $imaginary) {
    $n = count($real);
    if ($n <= 1) {
        return [$real, $imaginary];
    }

    $even_real = [];
    $even_imag = [];
    $odd_real = [];
    $odd_imag = [];

    for ($i = 0; $i < $n; $i += 2) {
        $even_real[] = $real[$i];
        $even_imag[] = $imaginary[$i];
        $odd_real[] = $real[$i + 1];
        $odd_imag[] = $imaginary[$i + 1];
    }

    list($even_real, $even_imag) = fft($even_real, $even_imag);
    list($odd_real, $odd_imag) = fft($odd_real, $odd_imag);

    $new_real = array_fill(0, $n, 0);
    $new_imag = array_fill(0, $n, 0);

    for ($k = 0; $k < $n / 2; $k++) {
        $angle = -2 * M_PI * $k / $n;
        $cos = cos($angle);
        $sin = sin($angle);

        $odd_real_k = $odd_real[$k] * $cos - $odd_imag[$k] * $sin;
        $odd_imag_k = $odd_real[$k] * $sin + $odd_imag[$k] * $cos;

        $new_real[$k] = $even_real[$k] + $odd_real_k;
        $new_imag[$k] = $even_imag[$k] + $odd_imag_k;
        $new_real[$k + $n / 2] = $even_real[$k] - $odd_real_k;
        $new_imag[$k + $n / 2] = $even_imag[$k] - $odd_imag_k;
    }

    return [$new_real, $new_imag];
}

使用外部库

PHP 可以通过扩展或调用外部程序实现更高效的 FFT：

php实现fft

FFTW 扩展：FFTW 是一个高效的 FFT 库，可以通过 PHP 的 FFI（Foreign Function Interface）调用。

$ffi = FFI::cdef("
    typedef struct { double real, imag; } fftw_complex;
    fftw_complex* fftw_malloc(size_t n);
    void fftw_free(void *p);
    void fftw_execute(const fftw_plan plan);
    fftw_plan fftw_plan_dft_1d(int n, fftw_complex *in, fftw_complex *out, int sign, unsigned flags);
", "libfftw3.so");

$n = 1024;
$in = $ffi->fftw_malloc($n * FFI::sizeof("fftw_complex"));
$out = $ffi->fftw_malloc($n * FFI::sizeof("fftw_complex"));
$plan = $ffi->fftw_plan_dft_1d($n, $in, $out, -1, 64); // 64 = FFTW_ESTIMATE
$ffi->fftw_execute($plan);

调用 Python 或 MATLAB：通过 shell 调用其他语言的 FFT 实现。

$input = json_encode([1, 2, 3, 4]);
$result = shell_exec("python3 -c 'import numpy as np; import json; print(json.dumps(np.fft.fft(json.loads(\"{$input}\")).tolist()))'");
$fft_result = json_decode($result, true);

注意事项

输入数据长度应为 2 的幂次（如 256, 512, 1024），否则需要补零。
自定义实现的性能较低，适合小规模数据或教学用途。
对于生产环境，建议使用 FFTW 或其他高性能库。

示例调用

$real = [1, 1, 1, 1, 0, 0, 0, 0];
$imag = array_fill(0, count($real), 0);
list($fft_real, $fft_imag) = fft($real, $imag);
print_r($fft_real);
print_r($fft_imag);