-----------------------------------------------------------------------------
-- |
-- Module      :  DSP.FastConvolution
-- Copyright   :  (c) Matthew Donadio 2003
-- License     :  GPL
--
-- Maintainer  :  m.p.donadio@ieee.org
-- Stability   :  experimental
-- Portability :  portable
--
-- Module to perform fast linear convolution of two sequences
--
-----------------------------------------------------------------------------

module DSP.FastConvolution (fast_conv) where

import Data.Array
import Data.Complex

import Numeric.Transform.Fourier.FFT

-- * Functions

-- | @fast_conv@ convolves two finite sequences using DFT relationships

fast_conv :: (RealFloat b) => Array Int (Complex b) -> Array Int (Complex b) -> Array Int (Complex b)
fast_conv :: forall b.
RealFloat b =>
Array Int (Complex b)
-> Array Int (Complex b) -> Array Int (Complex b)
fast_conv Array Int (Complex b)
h1 Array Int (Complex b)
h2 = Array Int (Complex b)
h3
    where m1 :: Int
m1  = forall a b. (a, b) -> b
snd forall a b. (a -> b) -> a -> b
$ forall i e. Array i e -> (i, i)
bounds Array Int (Complex b)
h1
	  m2 :: Int
m2  = forall a b. (a, b) -> b
snd forall a b. (a -> b) -> a -> b
$ forall i e. Array i e -> (i, i)
bounds Array Int (Complex b)
h2
	  m3 :: Int
m3  = Int
m1 forall a. Num a => a -> a -> a
+ Int
m2
	  h1' :: Array Int (Complex b)
h1' = forall a b.
(Ix a, Integral a, RealFloat b) =>
Array a (Complex b) -> Array a (Complex b)
fft forall a b. (a -> b) -> a -> b
$ forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (Int
0,Int
m3) forall a b. (a -> b) -> a -> b
$ forall i e. Array i e -> [e]
elems Array Int (Complex b)
h1 forall a. [a] -> [a] -> [a]
++ forall a. Int -> a -> [a]
replicate Int
m2 Complex b
0
          h2' :: Array Int (Complex b)
h2' = forall a b.
(Ix a, Integral a, RealFloat b) =>
Array a (Complex b) -> Array a (Complex b)
fft forall a b. (a -> b) -> a -> b
$ forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (Int
0,Int
m3) forall a b. (a -> b) -> a -> b
$ forall i e. Array i e -> [e]
elems Array Int (Complex b)
h2 forall a. [a] -> [a] -> [a]
++ forall a. Int -> a -> [a]
replicate Int
m1 Complex b
0
          h3' :: Array Int (Complex b)
h3' = forall i e. Ix i => (i, i) -> [e] -> Array i e
listArray (Int
0,Int
m3) forall a b. (a -> b) -> a -> b
$ forall a b c. (a -> b -> c) -> [a] -> [b] -> [c]
zipWith forall a. Num a => a -> a -> a
(*) (forall i e. Array i e -> [e]
elems Array Int (Complex b)
h1') (forall i e. Array i e -> [e]
elems Array Int (Complex b)
h2')
          h3 :: Array Int (Complex b)
h3  = forall a b.
(Ix a, Integral a, RealFloat b) =>
Array a (Complex b) -> Array a (Complex b)
ifft Array Int (Complex b)
h3'