2.10 小波变换并行算法优化
定理2.5 根据Mallat迭代公式
,设cj(k)=F[cj(n)],H(k)=F[h(n)],a(n)=IDFT[cj(k)H(k)],那么一定有下面算式成立:

证明:

定理2.5 表明小波变换向低分辨率空间分解时,可以合理利用二次抽取法则[38]。在用FFT作卷积运算时,可以更有效地利用此性质,减少运算以降低时间复杂度。具体到多项式算法,预先求出高通滤波器与低通滤波器的H0(k)=DFT[h0(n)],H1(k)=DFT[h1(n)],然后对离散数据cj(n)进行FFT矩阵变换得到离散向量DFT[cj(n)],再分别对内积求傅立叶逆变换:

因为只需对变换后的数据进行二次抽取,因此只要求出a(2k),b(2k),k=0,1,…,
就可以了。根据前面的讨论,在FFT矩阵算法中,序号为偶数的多项式明显可以合并相邻同类项,基向量减少了一半。当N=16 时,完成高通滤波与低通滤波两次,IDFT运算只需做28 次实数乘法;当N=32 时只要做140 次实数乘法;当N=64 时只要做620 次实数乘法。同时在对滤波器周期拓展时,需要让滤波器长度与数据段长度保持一致,并且等于2 的指数倍。设滤波器长度为
,然后再在后面补充
个0 作为周期扩充,根据多项式算法,多项式系数从
开始直到XN-1都为0,则多项式只剩下前
项。当N=16时,只需做12 次实数乘法,计算量减少50 次;当N=32 时只要做56 次实数乘法,计算量减少194 次;当N=64 时只要做240 次实数乘法,计算量减少752 次,效果十分明显。根据上述讨论,在MPSoC平台上并行小波变换,具体的算法如下。(https://www.daowen.com)
算法2.5 基于FFT矩阵的并行小波变换算法

对
个点进行FFT运算,需要复乘次数为:

相应实乘运算次数为:

直接算法的计算量为2N2 次实数乘法,将两者相比较,可得N≥16 时,上述快速DWT算法的计算量明显减少。