From: Dave Arnett <Dave_Arnett@hp.com>
Newsgroups: comp.sys.hp48
Subject: Re: Convolution of discrete vectors
Date: Wed, 02 Sep 1998 12:03:43 -0700
Organization: HP Vancouver Site
Lines: 150
Message-ID: <35ED968F.16B1@hp.com>
References: <35EC5223.4115@hp.com>
Reply-To: Dave_Arnett@hp.com
NNTP-Posting-Host: vscdarnett1.vcd.hp.com
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 3.01C (Win95; I)
Xref: republic.btigate.com comp.sys.hp48:15387

Hello, frequency-domain fans-

I have a few corrections.

First, the vectors are not required to have the last half be zeroes.
The only requirement is that the convolved vector will fit in the
space alotted, and that the space alotted be a power of two.  If the
first vector has n elements, and the second has m elements, the
convolution will have n+m-1 significant elements.  Thus, both 
starting vectors should be padded with zeroes to be of length n+m-1.

This is my theory for today.  Counter-examples are welcomed.

Second, I can't seem to spell some days.  The command is CEIL, not 
CIEL.  Thanks, John.  John also pointed me to the RDM command, which 
greatly simplifies the padding routine. So the program to create the 
input vectors for the convolution routine looks more like this:

<<
DUP2 SIZE EVAL SWAP
SIZE EVAL + 1 -		Calculate minimum vector size
LN 2 LN / .0000001 -
CEIL 2 SWAP ^ 		Making sure it is a power of 2
1 ->LIST DUP 4 ROLLD	RDM wants a single-element list 
RDM SWAP ROT RDM	Expand both vectors
>>

This program leaves A and B swapped, but that doesn't matter in the
convolution.

Starting with
	[1 2 3 4 5]
and	[1 2 3 4]

we get 	[1 2 3 4 5 0 0 0]
	[1 2 3 4 0 0 0 0]

which convolves to

	[1 4 10 20 30 34 31 20]

The third example from the previus post would be:

	[1 3 5 3 1]
	[7 3 2 1]

	[1 3 5 3 1 0 0 0]
	[7 3 2 1 0 0 0 0]

	[7 24 46 43 29 14 5 1]

Bye!
Dave.

Some guy named Dave Arnett wrote:
> 
> Hi, Folks.
> 
> I read a message yesterday dealing with convolution of time-
> discrete functions.  I wanted to reply today but I couldn't find it.
> I hope the original questioner reads this.
> 
> The fellow who asked wanted a program or process to convolve two
> vectors, where the vector elements indicate the values of the
> functions to be convolved.  For example:
> 
> A = [ 1 1 1 1 ]
> 
> B = [ 1 1 1 1 ]
> 
> C= A*B = [ 1 2 3 4 3 2 1 ]  where * indicates convlution.
> 
> The theory states that convolution in the time domain is
> equivalent to multiplication in the frequency domain.  I use that
> principle in my proposed solution.  First, I require that the
> two input vectors be of equal length, having a power of 2 as the
> number of elements, and having at least the last half of the
> elements equal to zero.  Otherwise there is wrap-around in
> the Fast Fourrier Transform that makes things really ugly.
> 
> Start:  A on level 1, B on level 2.
> Result: C on level 1
> 
> <<
> FFT                             Change A to freq domain
> OBJ-> OBJ-> DROP ->LIST         Turn b(s) into a list
> SWAP FFT                        Change B to freq domain
> OBJ-> OBJ-> DROP ->LIST         Turn b(s) into list
> *                               Multiply in freq domain
> OBJ-> 1 ->LIST ->ARRY           Turn c(s) into vector
> IFFT                            Change c to time tomain
> >>
> 
> Here are my results.  I round any 1E-15 numbers to zero.
> 
> B:      [ 1 1 1 1 0 0 0 0 ]
> A:      [ 1 1 1 1 0 0 0 0 ]
> 
> C:      [ 1 2 3 4 3 2 1 0 ]
> 
> B:      [ 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 ]
> A:      [ 1 2 3 4 4 3 2 1 0 0 0 0 0 0 0 0 ]
> 
> C:      [ 1 4 10 20 34 51 70 90 101 102 92 70 44 23 8 0 ]
> 
> When the vactors are of different length, or not of length 2 exp(n),
> fake it.  Remember: same length; length is a power of 2; last half
> at least is all zeroes.
> 
> B:      [ 1 3 5 3 1 0 0 0 0 0 0 0 0 0 0 0 ]
> A:      [ 7 3 2 1 0 0 0 0 0 0 0 0 0 0 0 0 ]
> 
> C:      [ 7 24 46 43 29 14 5 1 0 0 0 0 0 0 0 0 ]
> 
> Given any two vectors, the following program will expand them and
> pad them to match the rules:
> 
> <<
> DUP2 SIZE EVAL SWAP
> SIZE EVAL MAX           Find the size of the longest vector
> LN 2 LN / .0000001 -
> CIEL 2 SWAP ^ 2 *       Determine the size necessary to fit rules
> -> B A SC               B Vector, A vector, Size of C vector
>   <<
>   B OBJ-> OBJ-> DROP    Open up the B vector
>   WHILE DUP SC <
>     REPEAT 0 SWAP 1 +   Pad it with zeroes
>     END
>   1 ->LIST ->ARRY       Wrap B up as a vector
> 
>   A OBJ-> OBJ-> DROP    Do the same with A
>   WHILE DUP SC <
>     REPEAT 0 SWAP 1 +
>     END
>   1 ->LIST ->ARRY
>   >>
> >>
> 
> So if I start with
> 
> 2:      [1 3 5 3 1]
> 1:        [7 3 2 1]
> 
> this second program gives me the vectors shown in the last
> example, and we are ready to convolve them.
> 
> Best of Success!
> Dave.
> ------
> I don't speak for HP when I post here.