Comment faire une convolution en fa #?

Question

Je voudrais convoluer un signal discret avec un filtre discret. Le signal et le filtre sont des séquences de float en F #.

Le seul moyen de comprendre comment faire est d'utiliser deux boucles for imbriquées et un tableau mutable pour stocker le résultat, mais cela ne semble pas très fonctionnel.

Voici comment je le ferais non fonctionnel:

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) 

Answer 1

Essayez cette fonction:

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]))

Ce n’est probablement pas la solution la plus intéressante, mais elle devrait faire l'affaire. Je doute qu'il existe une solution purement fonctionnelle qui corresponde à l'impératif de rapidité.

L’espoir que cela aide.

Remarque: la fonction n’a pas encore été testée (bien que je l’aie confirmée compilée). Faites-moi savoir s'il ne fait pas ce qu'il devrait faire. Notez également que les variables i et j ne font pas référence aux mêmes choses que votre message d'origine.

Answer 2

Je ne sais pas F #, mais je posterai du Haskell et j'espère que ce sera assez proche pour être utilisé. (Je n'ai que VS 2005 et une ancienne version de F #, je pense donc que ce serait plus déroutant de publier quelque chose qui fonctionne sur ma machine)

Permettez-moi de commencer par publier une implémentation Python de votre pseudocode pour m'assurer d'obtenir la bonne réponse:

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

Maintenant convolve ([1,1,1], [1,2,3]) donne [3, 5, 6, 3, 1] . Si cela ne va pas, merci de me le dire.

La première chose à faire est de transformer la boucle interne en zipWith; nous ajoutons essentiellement une série de lignes de manière spéciale, dans l'exemple ci-dessus: [[3,2,1], [3,2,1], [3,2,1]] . Pour générer chaque ligne, compressons chaque i dans le signal avec le filtre inversé:

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

(Remarque: selon un rapide Google, zipAvec est map2 en F #. Vous devrez peut-être utiliser une compréhension de liste au lieu de répéter ) Maintenant:

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

Pour obtenir cela pour tous les i , nous devons mapper le signal:

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

Bien. Nous avons maintenant besoin d’un moyen de combiner correctement les lignes. Nous pouvons le faire en remarquant que la combinaison ajoute la nouvelle ligne au tableau existant, à l’exception du premier élément, qui est collé au premier plan. Par exemple:

[[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]

Il suffit donc d'écrire du code qui le fasse dans le cas général:

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

Maintenant que nous avons un moyen de générer toutes les lignes et d'associer une nouvelle ligne à un tableau existant, il ne reste plus qu'à coller les deux avec un pli:

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

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

Donc, c'est une version fonctionnelle. Je pense que c'est assez clair, tant que vous comprenez foldr et zipWith . Mais c'est au moins aussi long que la version impérative et, comme l'ont dit d'autres commentateurs, probablement moins efficace en fa #. Voici le tout au même endroit.

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)

Modifier:

Comme promis, voici une version F #. Ceci a été écrit en utilisant une version sérieusement ancienne (1.9.2.9) sur VS2005, alors soyez prudent. De plus, je n'ai pas trouvé splitAt dans la bibliothèque standard, mais je ne connais pas très bien 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)

Answer 3

En effet, vous souhaitez généralement éviter les boucles (simples, imbriquées, peu importe) et tout élément modifiable en programmation fonctionnelle.

Il existe une solution très simple en fa # (et probablement presque tous les autres langages fonctionnels):

let convolution = Seq.zip seq1 seq2

La fonction zip combine simplement les deux séquences en une des paires contenant l'élément de seq1 et l'élément de seq2 . Il est à noter qu’il existe également des fonctions zip similaires pour les modules List et Array , ainsi que des variantes permettant de combiner trois listes en triples ( zip3 ). Si vous voulez insérer généralement des listes zip (ou "convolues") dans une liste de n-uplets, vous devrez écrire votre propre fonction, mais elle est assez simple.

(Je suis passé par cette description de convolution en passant - Dis-moi si tu veux dire autre chose.)

Answer 4

En principe, il devrait être possible d’utiliser la transformation de Fourier (rapide) ou la transformation de cosinus (discrète) associée pour calculer la convolution de deux fonctions avec une efficacité raisonnable. Vous calculez la FFT pour les deux fonctions, vous les multipliez et appliquez la FFT inverse au résultat.

contexte mathématique

C'est la théorie. Dans la pratique, vous feriez probablement mieux de choisir une bibliothèque mathématique qui l'implémentera pour vous.