算法系列之二十四：离散傅立叶变换之音频播放与均衡器

在算法系列的第二十二篇，我们介绍了离散傅立叶变换算法的实现，将时域的音频信号转换到频域进行分析，获取拨号音频的频率特征。这一篇我们将介绍一种频域均衡器的实现方法，所谓的频域均衡器，就是在频域信号的基础上对音频数据进行调整，然后再将频域信号转换成时域信号在回放设备上播放，从而达到音色调节的目的。将频域信号转换成时域信号的算法，就是离散傅立叶逆变换算法。

1 离散傅立叶逆变换

有从时域转换到频域的方法，就必然有从频域转换到时域的方法，相对于离散傅里叶变换，这个反向转换就是离散傅里叶逆变换（IDFT）。和离散傅里叶变换一样，离散傅里叶逆变换也是连续傅里叶逆变换的离散形式，先来看看非周期信号连续傅里叶逆变换的公式：

(24-1)

连续傅里叶逆变换中的函数X(ω)是频域连续的，现在假设在X(ω)的某一段连续区间上按照频域抽取N个频率，得到N个采样点，则每个采样点的离散傅里叶逆变换公式就是：

(24-2)

如果引入常量，式(24-2)可以简单记为：

(24-3)

1.1 快速傅立叶逆变换的推导

对应于前面介绍的快速傅里叶变换，也存在与之对应的快速傅里叶逆变换（Inverse Fast Fourier Transform，IFFT）。和快速发傅里叶变换算法的推导过程一样，快速傅里叶逆变换算法的推导也是从式(24-3)开始，利用的周期性和对称性，将离散傅里叶逆变换逐级分解，减少计算量。具体的推导过程与快速傅里叶变换类似，读者可参考离散傅立叶变换算法的推导过程自行推导，此处不再赘述。

就IFFT算法的实现而言，其过程和FFT算法的实现一样，只需对FFT算法稍作修改，就成为了IFFT算法。将离散傅立叶逆变换公式(24-3)与离散傅立叶变换的公式对比，可以看出，二者的区别主要有两点：一个是蝶形变换的旋转因子不同，另一个是IFFT算法需要对整体结果除以N。FFT算法的蝶形变换旋转因子是 ，而IFFT算法的旋转因子是 ，除此之外，二者蝶形变换的距离和位置关系都是一样的，也就是说，最终位序重排的方法也一样。

1.2 快速傅里叶逆变换的算法实现

快速傅里叶逆变换算法的蝶形变换旋转因子是 ，其分解的复数形式中余弦项（实部）与FFT算法的余弦项相同，正弦项（虚部）的符号位与FFT算法的正弦项刚好相反，因此，算法实现仍然可以可用FFT_HANDLE中的正弦项和余弦项表。IFFT的算法实现如下：

void IFFT(FFT_HANDLE *hfft, COMPLEX * FD2TD)
{
    int i,j,k,butterfly,p;

    int power = NumberOfBits(hfft->count);

    for(k = 0; k < hfft->count; k++)
        FD2TD[k] = FD2TD[k] / COMPLEX(hfft->count, 0.0);

    /*蝶形运算*/
    for(k = 0; k < power; k++)
    {
        for(j = 0; j < 1<<k; j++)
        {
            butterfly = 1 << (power-k);
            p = j * butterfly;
            int s = p + butterfly / 2;
            for(i = 0; i < butterfly/2; i++)
            {
                COMPLEX t = FD2TD[i + p] + FD2TD[i + s];
                FD2TD[i + s] = (FD2TD[i + p] - FD2TD[i + s]) * COMPLEX(hfft->wt[i*(1<<k)].re,
                    -hfft->wt[i*(1<<k)].im);
                FD2TD[i + p] = t;
            }
        }
    }
    /*----按照倒位序重新排列变换后信号----*/
    for (k = 0; k < hfft->count; k++) 
    {
        int r = BitReverise(k, power);
        if (r > k) 
        {
            COMPLEX t = FD2TD[k];
            FD2TD[k] = FD2TD[r];
            FD2TD[r] = t;
        }
    }
}

2 利用傅里叶变换实现频域均衡器

调节均衡器改变声音的回放效果，就像在汤里放味精一样，掩盖了音乐原始的味道，也能获得一些意想不到的效果。但是，同学，你关注过它的实现原理吗？这一节，我们就来研究一下均衡器的实现原理，同时结合前面介绍的快速傅里叶变换和快速傅里叶逆变换，实现一个可以对各种频率的声音进行精准控制的频域均衡器算法。

从应用角度理解，音乐均衡器有两种常见类型，一种是图示均衡器（Graphic Equalizer），另一种是参量均衡器（Parametric Equalizer）。图示均衡器是一种按照一定的规律把全音频20～20000 Hz划分为若干的频段，每个频段对应一个可以对电平进行增益或衰减的调节器，可以根据需要，对输入的音频信号按照特定的频段进行单独的增益或衰减。参量均衡器不划分固定的波段，可对任意一个频率点（包括频点附近指定频率带宽内的所有点）进行控制，通过调整带宽，使得调节控制可精确（小带宽），也可模糊（大带宽），非常灵活。参量均衡器操作控制不直观，多用在对声音精确控制的专业场合。像Winamp和Foobar这样的音频播放器，多采用图示均衡器，通过一个带调节器的图形面板可以让用户很方便地对特定频段进行调节。

从信号形态角度理解，均衡器又可以分为时域均衡器和频域均衡器两种类型。时域均衡器对时域音频信号通过叠加一系列滤波器实现对音色的改变，无论是传统的音响设备还是众多音乐播放软件，绝大多数都是使用时域均衡器。时域均衡器通常由一系列二次IIR滤波器或FIR滤波器串联组合而成，每个波段对应一个滤波器，各个滤波器可以单独调节，串联在一起形成最终的效果。但是，传统的IIR滤波器具有反馈回路，会出现相位偏差，而FIR滤波器会造成比较大的时间延迟。另外，如果使用IIR或者FIR滤波器，均衡器波段越多，需要串联的滤波器的个数也越多，运算量也越大。频域均衡器是在频域内直接对指定频率的音频信号进行增益或衰减，从而达到改变音色的目的。频域均衡器没有相位误差和时间延迟，而且不固定波段，可以对任意频率进行调节，不仅适用于图示均衡器，也适用于参量均衡器。特别是采用快速傅里叶变换这样的算法，可以进行更快速的运算，即便是多段均衡器也不会引起运算量的增加。

2.1 频域均衡器的实现原理

总体上说，频域均衡器的实现原理很简单，就是将时域音频信号转换到频域，然后对特定频率进行增益或衰减计算，最后再将结果转换到时域，从而实现对音频音色的修改。如果是多个音轨的音频，需要对每个音轨单独做上述转换和调节。原理简单，但是实现起来并不简单，有很多细节问题需要解决。首先，用户在图示均衡器上拉动拉杆，调节了某个波段之后，这个调节的相对变化如何转化为对频域信号的处理？

2.2 杂项说明

图示均衡器允许用户调节每个波段的增益和衰减，调节的单位通常是dB（分贝）。dB是一个相对比值，用于表示两个值之间的比例关系。20 dB的信号的实际强度是0 dB信号的10倍，而－20 dB的信号的实际强度是0 dB信号的1/10。当用户调节了某个波段的增益值后，如何将这个相对增量转换成能在频域内直接对频域数据进行计算处理的增益强度，是频域均衡器需要解决的重点问题。

2.2.1 频域的增益和衰减

首先，增益或衰减是基于频率（频段）进行计算，所以这个问题需要在频域内处理。处理的方法就是根据功率相对强度与频域信号值的计算关系。与处理频谱的方式不同，这里要通过这个公式反推需要在频域信号叠加什么值才能使得功率达到指定的增益或衰减。具体来说，就是频域信号的实部和虚部各需要叠加什么值，以及这种叠加关系是什么。

为了给某个频率的信号增益个dB（若是小于0，表示是对信号进行衰减），根据频谱功率计算公式，需要叠加的量。现在对x和y赋予不同的权重，不妨设实部的权重是0.75，虚部的权重是0.25，也就是令x=0.75k，y=0.25k。将x和y代入频谱功率计算公式，简化后可以得到：

(24-4)

对于指定的增益（或衰减）值，可以利用上式计算出k的值。接下来，假设某个频率在频域的值是，其相对强度是，如果给其叠加一个增益（或衰减），需要的计算是：

由上式可知，需要给原始信号进行叠加的值是 ，叠加的方式是复数乘法。

前面给出的快速傅里叶变换和逆变换都是复数变换，但是处理音频数据时都只使用了复数的实部（虚部赋值为0.0），因此，叠加值在频域计算好之后，需要转换到时域，将虚部清0，只保留实部的值，然后再转换到频域，此时的叠加值才是最终参与复数乘法计算的值。根据增益值计算叠加量的算法实现如下：

bool UpdateFilter(EQUALIZER_HANDLE *hEQ, float *gain, int count)
{
    if((hEQ->hfft.count / 2) < count)
        return false;

    for(int i = 0; i < hEQ->hfft.count / 2; i++)
    {
        double dbk = pow(10.0, gain[i]/20.0);
        hEQ->filter[i].re = (float)(dbk * 0.75);
        hEQ->filter[i].im = (float)(dbk * 0.25);
        hEQ->filter[hEQ->hfft.count - 1 - i].re = hEQ->filter[i].re;
        hEQ->filter[hEQ->hfft.count - 1 - i].im = hEQ->filter[i].im;
    }

    IFFT(&hEQ->hfft, hEQ->filter); //to time-domain
    for(int i = 0; i < hEQ->hfft.count; i++)
    {
        hEQ->filter[i].im = (float)0.0;
    }
    FFT(&hEQ->hfft, hEQ->filter); //to freq-domain

    return true;
}

算法中只计算了前一半的叠加量，后一半采用的是对称赋值，这是由频域信号的对称性决定的。

2.2.2 应用三次样条曲线插值算法平滑增益与衰减

对均衡器调节，对应的是一个波段，不是一个频率。因此，在频域进行增益（或衰减）计算时，不应仅考虑一个频率，而应考虑以这个频率为中心的整个波段。当然，也不是整个波段都进行相同的增益（或衰减），最好的方法是波段的中心频率点执行最大增益（或衰减），然后按照波段带宽，从中心到边缘逐步降低增益（或衰减）的值。

从波段中心到边缘的变化可以采用线性方式，从示意图看起来就是多条折线。当然，也可以采用当前流行的方法，就是采用曲线插值的方法，使示意图起来想一条平滑的曲线。说到曲线插值，本系列会另起一篇专门介绍。本篇的均衡器例子就使用三次样条曲线插值算法，得到一条平滑的增益（或衰减）值曲线。生活中到处都是算法，不是吗？

2.3 均衡器的实现——仿Foobar的18段均衡器

有了以上的分析，均衡器算法的实现就水到渠成了，将音频数据按照FFT算法一次能处理的最大数据分块，对每一块音频数据用FFT算法将其转换到频域，对信号进行计算，然后在用IFFT算法将音频数据转换到时域，每一块的处理算法如下：

  FFT(&hEQ->hfft, leftData);
  if(channels > 1)
  {
        FFT(&hEQ->hfft, rightData);
  }

  SampleDataMpGain(leftData, rightData, hEQ->hfft.count, channels, hEQ->filter);
  IFFT(&hEQ->hfft, leftData);
  if(channels > 1)
  {
        IFFT(&hEQ->hfft, rightData);
  }

SampleDataMpGain()函数负责增益（或衰减）的计算，就是将信号与filter逐个做复数乘法运算，最终的结果将在逆变换后得到的音频数据中得到体现。

最后需要注意的是，对信号进行增益（或衰减）计算可能会导致信号超出合法值的范围，从听觉上理解就是会导致调整后的声音听起来有杂音，因此需要在转换过程中消除这种现象。在音频处理领域，有很多专门的算法应对这种情况，很多个人和组织都申请了很多这样的专利。如果要实现一个专业的均衡器，你需要研究这些算法，本章的例子只是为了演示用FFT算法实现频域均衡器的原理，所以采用了一种简单的处理方法，就是当有信号值越界后，简单调整成最大值。这个调整在ComplexToSampleData()函数中实现，这个函数与SampleDataToComplex()函数对应，用于将调整后的信号转换成PCM格式的音频数据。

void ComplexToSampleData(COMPLEX *cdl, COMPLEX *cdr, int channels, short *sampleData)
{
    if(cdl->re > 1.0)
        cdl->re = 1.0;
    if(cdl->re < -1.0)
        cdl->re = -1.0;

    *sampleData = short(cdl->re * 32768.0);
    if(channels != 1)
    {
        if(cdr->re > 1.0)
            cdr->re = 1.0;
        if(cdr->re < -1.0)
            cdr->re = -1.0;
        *(sampleData + 1) = short(cdr->re * 32768.0);
    }
}

至此，所有的核心算法都已经完成，按照惯例，可以做个例子演示一下了。是的，来一个仿Foobar的18段均衡器吧，顺带体现一下三次样条曲线插值算法的价值。图24-1就是演示程序，均衡器曲线是我随便调的，没人会这么调均衡器吧？完整的示例程序代码包含在本章的随书代码中，除了算法核心代码之外，剩下的都是常规的Windows编程，请大家自己研究吧。

图24-1 一个仿Foobar的18段均衡器的例子

这一系列文章介绍了离散傅里叶变换及其快速算法（FFT）的几个应用例子，都是生活中常见的功能，背后隐藏的却是如此简单的算法实现。其实离散傅里叶变换在工业和信号处理领域有非常广泛的应用，并不仅限于本章的例子。本章给出的算法不算最高效的算法实现，但是中规中矩，是研究算法原理的好例子，读者还可以从互联网上找到处理实数的更高效的FFT算法来研究。我的目的是让大家再次了解生活中隐藏的算法，解除对算法的神秘感，不知道是否达到了？