Kotlin实现FFT

FFT简介

FFT（Fast Fourier Transform，快速傅里叶变换）是一种高效计算离散傅里叶变换（DFT）及其逆变换的算法实现。
FFT广泛应用于信号处理、图像处理、数据压缩等领域。

DFT公式

离散傅里叶变换的数学定义如下：
$$X(k) = \sum_{n=0}^{N-1} x(n) \cdot e^{-i 2\pi k n / N}$$
其中：

字母	意义	备注/理解
X(k)	第 k 个频率分量的复数值	频域输出
x(n)	第 n 个时域采样点	时域输入信号
N	总采样点数	决定频率分辨率 f_k = k/N * F_s
n	时域采样索引	n = 0,1,…,N-1，表示时间位置
F_s	采样频率	信号的采样频率
f_k	第k个频率分量的实际频率	f_k = k/N * F_s
k	频率索引	k = 0,1,…,N-1，对应实际频率 f_k = k/N * F_s
e	自然指数底数	用于复指数表达旋转（欧拉公式）
i	虚数单位	i^2 = -1，使指数表示复平面旋转
2π	一圈角度（弧度）	将比例 k n / N 转换为角度 θ
−	顺时针旋转	DFT 分析方向，IDFT 用 + 号
2π k n / N	相位角	控制旋转速度和旋转量，随 k、n 变化

复数类定义

/**
 * 复数数据类
 *
 * @param re 实部
 * @param im 虚部
 *
 * @property magnitude 复数的模
 * @property phase 复数的相位 (弧度)
 */
data class Complex(
    val re: Double,
    val im: Double,
) {
    val magnitude: Double
        get() = sqrt(re * re + im * im)

    val phase: Double
        get() = atan2(im, re)
}

Kotlin实现FFT

下面是一个使用Kotlin实现 Radix-2 FFT的简单示例：

private fun nextPowerOfTwo(v: Int): Int {
    if (v <= 1) return 1
    var n = 1
    while (n < v) n = n shl 1
    return n
}

/**
 * 计算一维离散傅里叶变换 (FFT)
 * 输入信号长度不必是 2 的幂次方，函数会自动补零至下一个 2 的幂次方长度。
 * @param signal 输入信号
 * @return 频域复数数组
 */
fun fft(signal: List<Double>): Array<Complex> {
    val fftSize = nextPowerOfTwo(signal.size)
    val x = DoubleArray(fftSize) { i -> if (i < signal.size) signal[i] else 0.0 }
    val xArr = Array(fftSize) { i -> Complex(x[i], 0.0) }

    // 计算 bits（log2(fftSize)）
    var bits = 0
    var tmp = fftSize
    while (tmp > 1) {
        tmp = tmp shr 1
        bits++
    }
    // Bit-reversal
    for (i in 0 until fftSize) {
        val j = reverseBits(i, bits)
        if (j > i) {
            val tmp = xArr[i]
            xArr[i] = xArr[j]
            xArr[j] = tmp
        }
    }

    // Iterative FFT (蝶形运算)
    var len = 2
    while (len <= fftSize) {
        val halfLen = len / 2
        val theta = -2.0 * PI / len
        val wLen = Complex(cos(theta), sin(theta))

        for (i in 0 until fftSize step len) {
            var w = Complex(1.0, 0.0)
            for (j in 0 until halfLen) {
                val u = xArr[i + j]
                val t =
                    Complex(
                        w.re * xArr[i + j + halfLen].re - w.im * xArr[i + j + halfLen].im,
                        w.re * xArr[i + j + halfLen].im + w.im * xArr[i + j + halfLen].re,
                    )
                xArr[i + j] = Complex(u.re + t.re, u.im + t.im)
                xArr[i + j + halfLen] = Complex(u.re - t.re, u.im - t.im)
                w =
                    Complex(
                        w.re * wLen.re - w.im * wLen.im,
                        w.re * wLen.im + w.im * wLen.re,
                    )
            }
        }
        len *= 2
    }
    return xArr
}

/** 按位反转 */
private fun reverseBits(
    x: Int,
    bits: Int,
): Int {
    var res = 0
    for (i in 0 until bits) {
        if ((x shr i) and 1 == 1) res = res or (1 shl (bits - 1 - i))
    }
    return res
}