haskell - 具有惰性语义的高效理性重采样

Question

要改变信号的采样率，需要上采样、滤波，然后下采样。简单地执行此操作意味着将零插入到输入信号中，与滤波器的脉冲响应相关联，然后丢弃除每个卷积的第 n 个样本之外的所有样本。

这种简单方法的问题在于存在大量无用的计算。当与滤波器进行卷积时，大多数滤波器抽头都乘以零，计算在下采样阶段将被丢弃的样本值是无用的。这就是为什么高效的理性重采样使用多相滤波器组，其中仅执行所需的计算。

我想知道是否可以使用惰性计算来避免无用的乘法，同时也避免显式构造多相滤波器组。我理想的解决方案类似于简单的方法(上采样，然后关联，然后下采样)，但执行与显式多相滤波器方法相同的计算。

下采样很容易，因为不需要的值不会被计算。但我不知道如何避免相关部分中的零乘法。我想出的最好的方法是使用 Maybe 类型并使用 Nothing(而不是零)进行上采样:

upsample n xs = upsample2' n xs 0
    where upsample' _ [] _ = []
          upsample' _ (x:_) 0 = Just x : upsample' n xs n
          upsample' n xs counter = Nothing : upsample' n xs (counter - 1)

correlate xs ys = sum $ catMaybes $ zipWith (fmap . (*)) xs ys

firFilter taps signal = map (correlate taps) (tails signal)

downsample _ [] = []
downsample n (x:xs) = x : downsample n (drop (n-1) xs)

upfirdn up down taps = (downsample down).(fir_filter taps).(upsample up)

upfirdn 函数确实只是简单的方法，下采样中的惰性避免了计算，但我认为处理器仍然需要检查值是否为 Nothing相关步骤。

有没有办法利用惰性来获得与多相滤波器方法相同的计算节省？如果没有，是否有根本原因无法完成？

Answer 1

我认为懒惰对解决此类问题没有帮助，原因有两个:

• 在 Haskell 中，惰性是通过在内存中构建未评估的 thunk 来实现的。这意味着懒惰并不是完全免费的:您仍然需要承担创建 thunk 的成本。如果 thunk 的评估成本很高，则此成本可以忽略不计。

  但是，在您的情况下，对于每个重击，您都为自己节省了乘法和加法，这只是一些 CPU 指令。创建 thunk 的成本可能是相同的数量级。

• 当您先验不知道将使用哪些元素时，惰性会很有帮助 - 通常是因为选择以某种复杂或未知的方式取决于输入/环境，因此您宁愿推迟到以后再做决定。

  就您的情况而言，您确切知道将使用哪些元素:元素的索引必须能被n整除。因此，仅迭代[0, n, 2 * n, 3 * n, ...]会更有效。

<小时/>

添加惰性的一种简单方法是定义惰性乘加运算:

(+*) :: Num a => a -> (a, a) -> a
z +* (_, 0) = z
z +* (x, y) = z + x * y

该操作是有偏差的，因此如果 y 为零，则跳过计算。

现在，当通过 upsample 生成掩码时，无需使用 Maybe:只需产生零而不是 Nothing。然后，要计算总和，只需使用:

correlate xs ys = foldl' (+*) 0 (zip xs ys)