信号处理 / 系统课时

用多相结构减少无效运算

用多相结构减少无效运算

直接重采样常会先算出大量最终要丢弃的样本,或对插值产生的零执行乘法。本节从三倍抽取的例子拆解多相分解,把 FIR 系数按相位重排,只计算真正会保留的输出,并用运算计数验证收益。

学习目标

  • 把 FIR 系数按抽取因子拆成多个多相子滤波器
  • 解释直接“先滤波再抽取”为什么包含无效计算
  • 用等价输出和乘法次数比较直接实现与多相实现

无效运算从哪里来

设 FIR 长度为 KK,抽取因子为 MM。最直接的实现会以输入采样率计算每一个滤波输出,然后只保留每隔 MM 个结果。这样大约有 (M−1)/M(M-1)/M 的完整滤波结果刚算完就被丢弃。

对插值也有类似问题:显式插零后,许多乘法的一端恒为零。多相结构的目标不是改变滤波器,而是重新安排同一组系数的计算顺序,跳过这些已知无用的运算。

把 FIR 系数按相位拆开

以三倍抽取为例,把系数 h[k]h[k] 按 k mod 3 分成三组:e0[q]=h[3q]e_0[q]=h[3q]、e1[q]=h[3q+1]e_1[q]=h[3q+1]、e2[q]=h[3q+2]e_2[q]=h[3q+2]。只在最终需要的时刻 n=3mn=3m 计算输出,就可以写成:

y[m]=∑r=02∑qer[q]x[3m−(3q+r)]y[m]=\sum_{r=0}^{2}\sum_q e_r[q]x[3m-(3q+r)]

这只是对卷积求和重新分组,因此只要边界处理一致,输出与“完整 FIR 卷积后每三点取一点”完全相同。

三倍抽取的直接 FIR 与多相计算对比

用代码验证输出等价与运算量

下面故意使用短序列和短 FIR,分别实现“完整卷积后抽取”和“按多相分组只计算保留点”。为了让计数可核对,每次有效的系数乘样本都记为一次乘法。

python
x = [1, 2, 3, 4, 5, 6, 7, 8]
h = [1, 2, 1, 0, -1, 1]
M = 3

def direct_decimate(x, h, m):
    full = []
    multiplies = 0
    for n in range(len(x) + len(h) - 1):
        acc = 0
        for k, coeff in enumerate(h):
            j = n - k
            if 0 <= j < len(x):
                acc += coeff * x[j]
                multiplies += 1
        full.append(acc)
    return full[::m], multiplies

def polyphase_decimate(x, h, m):
    phases = [h[r::m] for r in range(m)]
    out = []
    multiplies = 0

    for n in range(0, len(x) + len(h) - 1, m):
        acc = 0
        # 每个相位只贡献当前保留输出真正需要的项。
        for r, phase in enumerate(phases):
            for q, coeff in enumerate(phase):
                k = q * m + r
                j = n - k
                if 0 <= j < len(x):
                    acc += coeff * x[j]
                    multiplies += 1
        out.append(acc)
    return out, multiplies

direct_y, direct_ops = direct_decimate(x, h, M)
poly_y, poly_ops = polyphase_decimate(x, h, M)

print("direct   =", direct_y, "multiplies =", direct_ops)
print("polyphase=", poly_y, "multiplies =", poly_ops)
print("same output:", direct_y == poly_y)

预期输出

text
direct   = [1, 12, 23, 7, 8] multiplies = 48
polyphase= [1, 12, 23, 7, 8] multiplies = 16
same output: True

这个小例子恰好减少到三分之一,因为直接实现计算了全部卷积点,而多相版本只计算每三个位置中的一个。真实库还会通过向量化、缓存和专用 upfirdn 内核进一步优化,但减少无效数学运算的原理相同。

估算什么时候值得使用

对于纯抽取,若直接实现每个输入时刻都做长度为 KK 的 FIR,再每 MM 点保留一个输出,那么折算到每个保留输出大约要做 MKMK 次乘法;按多相方式直接形成保留输出,则约为 KK 次,理论上可减少到原来的约 1/M1/M。

对有理数 L/ML/M 重采样,多相结构还能同时避免“对插值零做乘法”和“计算随后会被抽取丢弃的输出”。因此当 LL、MM 较大或 FIR 较长时,不应手工构造插零序列再完整卷积;应优先使用基于 polyphase 或 upfirdn 的实现,让计算只落在真正会影响输出的样本与系数上。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用多相结构减少无效运算

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通