使用惰性语义进行高效的Rational重采样

Question

要更改信号的采样率,需要进行上采样,滤波,然后进行下采样.天真地这样做意味着在输入信号中插入零,与滤波器的脉冲响应相关,然后丢弃除n卷积的每个样本之外的所有样本.

天真方法的问题在于存在许多无用的计算.当与滤波器卷积时,大多数滤波器抽头乘以零,并且计算将在下采样阶段丢弃的样本的值是无用的.这就是为什么有效的合理重采样使用多相滤波器组,其中仅执行所需的计算.

我想知道是否可以使用延迟计算来避免无用的乘法,同时还避免明确地构造多相滤波器组.我理想的解决方案是类似于天真的方法(上采样,然后相关,然后下采样),但做了与显式多相滤波器方法相同的计算.

下采样很容易,因为不需要计算不需要的值.但我无法弄清楚如何避免相关部分中的乘数为零.我提出的最好的方法是使用Maybe类型和上传样本与Nothings(而不是零):

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的评估是昂贵的,则该成本可以忽略不计.

  但是,在你的情况下,对于每个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为零,则跳过计算.

现在,当生成掩码via时upsample,不需要使用Maybe:只需产生零而不是Nothing.然后,要计算总和,只需使用:

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