4

我想将离散信号与离散滤波器进行卷积。信号和滤波器是 F# 中的浮点序列。

我能弄清楚如何做到这一点的唯一方法是使用两个嵌套的 for 循环和一个可变数组来存储结果，但感觉不是很实用。

以下是我将如何做到这一点：

conv = double[len(signal) + len(filter) - 1]
for i = 1 to len(signal)
  for j = 1 to len(filter)
    conv[i + j] = conv[i + j] + signal(i) * filter(len(filter) - j)
4

4 回答 4

7

我不知道 F#，但我会发布一些 Haskell，希望它足够接近使用。（我只有 VS 2005 和一个古老版本的 F#，所以我认为在我的机器上发布一些可以工作的东西会更加混乱）

让我首先发布你的伪代码的 Python 实现，以确保我得到正确的答案：

def convolve(signal, filter):
    conv = [0 for _ in range(len(signal) + len(filter) - 1)]
    for i in range(len(signal)):
        for j in range(len(filter)):
            conv[i + j] += signal[i] * filter[-j-1]
    return conv

现在convolve([1,1,1], [1,2,3])给[3, 5, 6, 3, 1]. 如果这是错误的，请告诉我。

我们可以做的第一件事就是把内循环变成一个 zipWith；在上面的示例中，我们本质上是以一种特殊的方式添加了一系列行：[[3,2,1], [3,2,1], [3,2,1]]. 为了生成每一行，我们将使用反向过滤器压缩每一i行signal：

makeRow filter i = zipWith (*) (repeat i) (reverse filter)

（注意：根据快速谷歌，zipWith在map2F# 中。您可能必须使用列表推导而不是repeat）现在：

makeRow [1,2,3] 1
=> [3,2,1]
makeRow [1,2,3] 2
=> [6,4,2]

为了得到这个i，我们需要映射信号：

map (makeRow filter) signal
=> [[3,2,1], [3,2,1], [3,2,1]]

好的。现在我们只需要一种正确组合行的方法。我们可以通过注意到组合将新行添加到现有数组中来做到这一点，除了第一个元素，它卡在前面。例如：

[[3,2,1], [6,4,2]] = 3 : [2 + 6, 1 + 4] ++ [2]
// or in F#
[[3; 2; 1]; [6; 4; 2]] = 3 :: [2 + 6; 1 + 4] @ [2]

所以我们只需要编写一些在一般情况下执行此操作的代码：

combine (front:combinable) rest =
    let (combinable',previous) = splitAt (length combinable) rest in
    front : zipWith (+) combinable combinable' ++ previous

现在我们有了一种生成所有行的方法以及一种将新行与现有数组组合的方法，我们所要做的就是将两者结合在一起并折叠：

convolve signal filter = foldr1 combine (map (makeRow filter) signal)

convolve [1,1,1] [1,2,3]
=> [3,5,6,3,1]

所以这是一个功能版本。我认为这是相当清楚的，只要你理解foldr和zipWith. 但它至少与命令式版本一样长，就像其他评论者所说的那样，在 F# 中可能效率较低。这是一个地方的全部内容。

makeRow filter i = zipWith (*) (repeat i) (reverse filter)
combine (front:combinable) rest =
    front : zipWith (+) combinable combinable' ++ previous
    where (combinable',previous) = splitAt (length combinable) rest
convolve signal filter = foldr1 combine (map (makeRow filter) signal)

编辑：

正如所承诺的，这是一个 F# 版本。这是在 VS2005 上使用非常古老的版本（1.9.2.9）编写的，所以要小心。我在标准库中也找不到splitAt，但是我不太了解 F#。

open List
let gen value = map (fun _ -> value)
let splitAt n l = 
  let rec splitter n l acc =
    match n,l with
    | 0,_ -> rev acc,l
    | _,[] -> rev acc,[]
    | n,x::xs -> splitter (n - 1) xs (x :: acc)
  splitter n l [] 
let makeRow filter i = map2 ( * ) (gen i filter) (rev filter)
let combine (front::combinable) rest =
  let combinable',previous = splitAt (length combinable) rest
  front :: map2 (+) combinable combinable' @ previous
let convolve signal filter = 
  fold1_right combine (map (makeRow filter) signal)
于 2009-04-30T14:32:39.697 回答
3

试试这个功能：

let convolute signal filter =
    [|0 .. Array.length signal + Array.length filter - 1|] |> Array.map (fun i ->
        [|0 .. i|] |> Array.sum_by (fun j -> signal.[i] * filter.[Array.length filter - (i - j) - 1]))

它可能不是最好的功能解决方案，但它应该可以完成这项工作。但是，我怀疑是否存在一种纯粹的功能解决方案，可以与速度的必要解决方案相匹配。

希望有帮助。

注意：该功能目前未经测试（尽管我已经确认它可以编译）。让我知道它是否没有完全做它应该做的事情。另外，请注意i和j变量与您的原始帖子所指的内容不同。

于 2009-04-29T19:41:41.600 回答
2

实际上，您通常希望避免循环（普通、嵌套等）和函数式编程中任何可变的东西。

F#（可能几乎所有其他函数式语言）中恰好有一个非常简单的解决方案：

let convolution = Seq.zip seq1 seq2

该zip函数只是将两个序列组合成一对，其中包含元素 fromseq1和元素 from seq2。List需要注意的是， and模块也存在类似的 zip 函数Array，以及将三个列表组合成三元组 ( zip3) 的变体。如果您希望将 tom ore 通常将 n 个列表压缩（或“卷积”）到一个 n 元组列表中，那么您需要编写自己的函数，但这非常简单。

（顺便说一下，我一直在按照卷积的描述进行说明——告诉我你是否还有别的意思。）

于 2009-04-29T16:12:18.607 回答
2

原则上，应该可以使用（快速）傅里叶变换或相关的（离散）余弦变换来合理有效地计算两个函数的卷积。您计算这两个函数的 FFT，将它们相乘，然后对结果应用逆 FFT。

数学背景

这就是理论。在实践中，您可能最好找到一个为您实现它的数学库。

于 2009-04-29T17:16:29.170 回答