"Umutesi Faith" <ma_nz1@yahoo.com> wrote in message 
news:9aednWhxVvIrdKLeRVn-vw@giganews.com...
>I don't mean to be annoying , but here i am again with the same question!
> /*Input samples*/
> int Input[7] = {s0, s1, s2, s3, s4, s5, s6 ,s7};// array initialization in
> C language
>
> Input[0] = newestsample
>
> Knowing that the newestsample is a certain variable which is assigned to
> the Input[0] each time a next input sample is received,my concern is how
> then to assign these inputs samples to the variable newestsample each
> time!!(example,the first round would take newestsample = s0!!, and the
> next round after the shifting of s0 it would take s1 at Input[0] and so
> on....)
> thanks!

I'll give you the same answer that Jerry did but will try to stick to your 
notation.  I am not the best programmer so the goodness of the code should 
be questioned:

you said:
/*Input samples*/
> int Input[7] = {s0, s1, s2, s3, s4, s5, s6 ,s7};// array initialization in
> C language

I'm going to modify the variable name here for clarity:

k=0
/*Buffer samples*/
int Buffer[8]=[s0,s1, s2, s3, s4, s5, s6 ,s7};// array initialization in
> C language
/*Define filter*/
int filter[8]=[f0, f1, f2, f3, f4, f5, f6, f7];// filter initialization
/*compute filter output*/
y(k)=s0*f7 + s1*f6 + s2*f5 + s3*f4 + s4*f3 + s5*f2 + s6*f1 +s7*f0
k=k+1
"get newsample" ; however you do this....
s7=s6
s6=s5
s5=s4
s4=s3
s3=s2
s2=s1
s1=s0
s0=newsample; // note the order of replacement.  the sample that was in s7 
goes away.
/*compute filter output*/
y(k)=s0*f7 + s1*f6 + s2*f5 + s3*f4 + s4*f3 + s5*f2 + s6*f1 +s7*f0

...build this into a loop.

But, this is a pretty brute force approach so instead of doing all those 
replacements, we'll not move the data but index the buffer circularly 
instead:

k=0
/*Buffer samples*/
int Buffer[8]=[s0,s1, s2, s3, s4, s5, s6 ,s7};// array initialization in
> C language
/*Define filter*/
int filter[8]=[f0, f1, f2, f3, f4, f5, f6, f7];// filter initialization
/*compute filter output*/

y(k)=s0*f(7) + s1*f(6) + s2*f(5) + s3*f(4) + s4*f(3) + s5*f(2) + s6*f(1) 
+s7*f(0)
"get newsample" ; however you do this....
s(7+k)=newsample; //replaces the sample that will go away with the newest 
sample//
k=k+1
/*compute filter output*/
y(k)=s(0+k)*f(7) + s(1+k)*f(6) + s(2+k)*f(5) + s(3+k)*f(4) + s(4+k)*f(3) + 
s(5+k)*f(2) + s(6+k)*f(1) +s(7+k)*f(0);
// x+k has to be done modulo 8 and I've not shown that ... there are surely 
"good" programs on dspguru.com //
//repeat//
"get newsample" ; however you do this....
s(7+k)=newsample; //replaces the sample that will go away with the newest 
sample so now s(7) is the "zeroeth" sample, s(0) is the 1st sample, s(1) is 
the 2nd sample ... and s(6) is the 7th sample //
k=k+1
/*compute filter output*/
y(k)=s(0+k)*f(7) + s(1+k)*f(6) + s(2+k)*f(5) + s(3+k)*f(4) + s(4+k)*f(3) + 
s(5+k)*f(2) + s(6+k)*f(1) +s(7+k)*f(0);

//so the "beginning" of the data moves through the array as the oldest 
sample is replaced with the newest sample.//

I hope this is clear enough now.

Fred

Umutesi Faith wrote:
> I don't mean to be annoying , but here i am again with the same question!
> /*Input samples*/
> int Input[7] = {s0, s1, s2, s3, s4, s5, s6 ,s7};// array initialization in
> C language
>    
> Input[0] = newestsample
> 
> Knowing that the newestsample is a certain variable which is assigned to
> the Input[0] each time a next input sample is received,my concern is how 
> then to assign these inputs samples to the variable newestsample each
> time!!(example,the first round would take newestsample = s0!!, and the
> next round after the shifting of s0 it would take s1 at Input[0] and so
> on....)
> thanks!

Once you understand the what you need to do, the code will seem simple.

The naive approach shifts all the data in the buffer each time a new 
sample is inserted:

s7=s6; s6=s5; s5=s4; s4=s3; s3=s2; s2=s1; s1=s0; s0=newsample

Now, multiply each sn by the coefficient assigned to it and add the 
result to an initially zero accumulator. (This step is called a MAC; 
Multiply and ACcumulate. some processors support it as a single 
instruction.) The accumulator is the filter output when all the sn have 
been processed.

Then do it again for the next output.

One is tempted to code the buffer shift as a loop. Don't bother. 
Instead, get rid of the shift by using a circular buffer. (Q.V.) Some 
processors support circular buffering in hardware. circular buffers are 
not unique to DSP. That are also very useful, for example, for UART 
operation, especially when the UART service routine is interrupt driven.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������

I don't mean to be annoying , but here i am again with the same question!
/*Input samples*/
int Input[7] = {s0, s1, s2, s3, s4, s5, s6 ,s7};// array initialization in
C language
   
Input[0] = newestsample

Knowing that the newestsample is a certain variable which is assigned to
the Input[0] each time a next input sample is received,my concern is how 
then to assign these inputs samples to the variable newestsample each
time!!(example,the first round would take newestsample = s0!!, and the
next round after the shifting of s0 it would take s1 at Input[0] and so
on....)
thanks!

>"Umutesi Faith" <ma_nz1@yahoo.com> wrote in message 
>news:XJGdnSYHAtBNXaPeRVn-qA@giganews.com...
>>
>> Well, this is the most common form of array initialization in C
language.
>> This array has 8 elements running from s0 to s7!
>> My intention was just to make sure if i understood well "the pseudo
code"
>> so that i can continue with fixed ideas in my studying about the FIR
>> filter implementation!
>
>OK - I hope this helped then...
>
>Fred 
>
>
>


		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

"Umutesi Faith" <ma_nz1@yahoo.com> wrote in message 
news:XJGdnSYHAtBNXaPeRVn-qA@giganews.com...
>
> Well, this is the most common form of array initialization in C language.
> This array has 8 elements running from s0 to s7!
> My intention was just to make sure if i understood well "the pseudo code"
> so that i can continue with fixed ideas in my studying about the FIR
> filter implementation!

OK - I hope this helped then...

Fred 

Well, this is the most common form of array initialization in C language.
This array has 8 elements running from s0 to s7!
My intention was just to make sure if i understood well "the pseudo code"
so that i can continue with fixed ideas in my studying about the FIR
filter implementation!

>> /*input samples*/
 int Input[7] ={s0,s1,s2,s3,s4,s5,s6,s7};
>>
>> this would be like Input[0]=xnew;
>> How is this "xnew" accessing the data in the Input[7] array?
>> Thanks!
>>
>> Umutesi
>
>I don't understand your notation.  You seem to be using Input as both a 
>vector and a scalar.  That is, an array of multiple elements and an array
of 
>1 element.  Note that I'm not trying to write code for you, so this is
all 
>pseudo code gibberish that you have to put properly into the language of

>your choice.
>
>I said there is a very brute force and inefficient method that may be 
>instructive:
>
>b(n)=b(n-1)
>b(n-1)=b(n-2)
>.
>Fred 
>
>
>


		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

"Umutesi Faith" <ma_nz1@yahoo.com> wrote in message 
news:quKdnVpLQtqq8aPeRVn-vA@giganews.com...
> Hello
>
> I have tried to understand this shifting method you discribed below, if
> understood it correct ,xnew is the new sample. So if for instance
> /*input samples*/
> Input[7] ={s0,s1,s2,s3,s4,s5,s6,s7};
>
> this would be like Input[0]=xnew;
> How is this "xnew" accessing the data in the Input[7] array?
> Thanks!
>
> Umutesi

I don't understand your notation.  You seem to be using Input as both a 
vector and a scalar.  That is, an array of multiple elements and an array of 
1 element.  Note that I'm not trying to write code for you, so this is all 
pseudo code gibberish that you have to put properly into the language of 
your choice.

I said there is a very brute force and inefficient method that may be 
instructive:

b(n)=b(n-1)
b(n-1)=b(n-2)
.
.
b(1)=b(0)
b(0)=xnew
where "b()" is the buffer.
And, I was assuming this was a streaming implementation - so you get xnew at 
each time step and don't know what it is beforehand.

If you are doing this in something like Matlab and already have all the 
inputs in memory then it might look like this:

inputs=[1 2 3 4 3 4 3 5 6 5 4 3 2 1 2 ...... 8 5 9 3 4 6 9]
(and of course the number format can be anything you like - I just showed 
positive integers because I'm being lazy)

Now you have inputs(1) inputs(2), etc. and I will state that inputs(1) is 
the oldest / first data point / sample.

Then convolve the inputs vector with the filter unit sample response.
loop
k=1
y(k)=inputs(k)*filter(1) + inputs(1+k)*filter(2) .... + 
inputs(N-1+k)*filter(N)
k=k+1
continue until (N-1+k) is the maximum index in the array "inputs"

where "filter" is the array of filter coefficients (reversed I believe- that 
is, filter(N) is the first unit sample output value) and I have left out the 
startup and ending transient computations altogether for simplicity.
In this implementation, the filter slides along the data and the data of 
interest is whatever lines up with the filter coefficients at each sample 
time.

Since the data is all contained in the vector "inputs", the implementation 
just changes "k" to move the filter along the data.

Fred 

Hello

I have tried to understand this shifting method you discribed below, if
understood it correct ,xnew is the new sample. So if for instance
/*input samples*/
Input[7] ={s0,s1,s2,s3,s4,s5,s6,s7};

this would be like Input[0]=xnew;
How is this "xnew" accessing the data in the Input[7] array?
Thanks!

Umutesi
******************************************************************

Re: Odd symmetric FIR filter - Fred Marshall - 12:57 24-09-05

***So, the software version of one of these would have a number of memory

locations to represent the "buckets" or the locations in the shift
register.
A brute-force method will move the data in the same fashion like this:

b(n)=b(n-1)
b(n-1)=b(n-2)

Thank you all for your help. I did read quite a lot tutorial about these
FIR filters, but i guess there have been some missing details for me to
understand them properly. With all the help i got from here i hope 
finally to be able to do my implementation! I will keep posting once i get
stuck again!!
 
Umutesi
		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

"Umutesi Faith" <ma_nz1@yahoo.com> wrote in message 
news:XYSdnQCIAq5JiKjeRVn-uw@giganews.com...
> It was a typing mistake the FIR filter was intended to be odd symmetric!!

***Actually, I'm not used to the term "odd symmetric" and I'm a little 
concerned that you could mean:

- antisymmetric as in 1 2 3 0 -3 -2 -1  or in 1 2 3 -3 -2 -1

instead of:

- odd length *and* symmetric as in 1 2 3 4 3 2 1

That's because the latter is an Even sequence of Odd length (if you define 
time zero at the center anyway - for discussion purposes)
and
The former examples are both Odd sequences of Odd or Even length (again if 
you define time zero at the center).

> Thank you for your replies, at least i can have a small idea on how this
> filter was implemented! I'm myself trying to implement a FIR filter,i
> cannot use assembler as i don't know much about it, but i can try to do it
> in a simple C code, but so far i have found the following steps which are
> not obvious to understand :
> Basic Algorithm for implementing FIR filters
>
> -Put the input signal in the delay line.// what do they mean by this ??

***In the olden days the filters operated in continuous time using "analog" 
delay lines.
The delay lines had taps on them (that is, interim output points)
The outputs (which include the input and the final output as well as the 
interim outputs) were each weighted and then all the weighted results were 
summed to get the filter output.


> -Multiply each sample in the delay line by the corresponding coefficient
> and accumulate the result.

***Note that a discrete version of a delay line is a memory.  In the not 
quite so olden days we built FIR filters out of bucket-brigade delay lines 
(continuous values with discrete "buckets") and we built them out of 
shift-register types of memories (discrete values ... bits ... with discrete 
memory registers that were coupled together in a serial manner).  Both 
versions were clocked to accomplish the shifts.  So, if the shifting clock 
rate was the same as the sample rate the data would move along the chain as 
each new sample entered and as the oldest sample disappeared as it was 
replaced by the next oldest sample.
Note that this ties the sample rate and the delay values together .. which 
makes sense, eh?

***So, the software version of one of these would have a number of memory 
locations to represent the "buckets" or the locations in the shift register.
A brute-force method will move the data in the same fashion like this:

b(n)=b(n-1)
b(n-1)=b(n-2)
.
.
b(1)=b(0)
b(0)=xnew
then multiply the locations by the same coefficients each time

A more sophisticated method (look up "circular buffer") avoids moving all 
the data and moves a reference pointer /offset instead:

offset=k; 0<=k<=(n-1)
i=k to (n-1)+k modulo n
b(k)=xnew
then multiply the *offset* locations by the coefficients

> -Shift the delay line by one sample to make room for the next input
> sample.
>
> //this is how i see this algorithm
> For instance if the length of the filter is 4 and the number of input
> samples is 16, putting the input in the delay does it mean starting from
> input[0]?? .

***yes.  If the filter is a0 a1 a2 a3 and the data is d0 d1 d2 .... d15
then the multiplies start:
y0 = a0*d0
y1 = a0*d1 + a1*d0
y2 = a0*d2 + a1*d1 + a2*d0
y3 = a0*d3 + a1*d2 + a2*d1 + a3*d0
y4 = a0*d4 + a1*d3 + a2*d2 + a3*d1
.      .       .       .       .
.      .       .       .       .
y15 = a0*d15 + a1*d14 + a2*d13 + a3*d12
y16 =          a1*d15 + a2*d14 + a3*d13
y17=                    a2*d15 + a3*d14
y18=                             a3*d15

Note that the filter fills up in N-1, that is, 3 sample times and it 
"unloads" over 3 samples times.  These are startup and ending transients 
that are of length 1 less than the length of the filter.  You might well 
disregard these outputs.

> For the second step the multiply and accumulate is to sum up the the
> multiplication of the input sample and fir coefficients!
> So this shifting step , the filtering start at input[1] and the oldest
> sample is dropped??

Yes, as above.

> I am not sure if i do understand it in the correct way, why i am so
> struggling implementing these filters , are there some tricks to
> follow???

The address change vs. actually shifting the data is one.
If the filter is symmetrical then you might add two samples and multiply 
once - assuming that makes any difference in your machine.
Then there might be things about scaling and affects in roundoff errors.

Then you might modify the coefficients to be sums of powers of two to 
eliminate multiplies altogether in favor of shifts.  Again, it depends on 
your machine.  This works well in FPGA implementations, for example.
That is .. a coefficient of 0.50222 might be rounded to 0.5 and a simple 
shift will replace a multiply.  Or, 0.627 would be 0.5 + 0.125 which would 
be two shifts and and add to replace the multiply.

Do read the things that Jerry pointed to.

Fred 

Umutesi Faith wrote:
> It was a typing mistake the FIR filter was intended to be odd symmetric!!
> Thank you for your replies, at least i can have a small idea on how this
> filter was implemented! I'm myself trying to implement a FIR filter,i
> cannot use assembler as i don't know much about it, but i can try to do it
> in a simple C code, but so far i have found the following steps which are
> not obvious to understand :
> Basic Algorithm for implementing FIR filters
> 
> -Put the input signal in the delay line.// what do they mean by this ??
> -Multiply each sample in the delay line by the corresponding coefficient
> and accumulate the result.
> -Shift the delay line by one sample to make room for the next input
> sample.
> 
> //this is how i see this algorithm    
> For instance if the length of the filter is 4 and the number of input
> samples is 16, putting the input in the delay does it mean starting from
> input[0]?? .
> For the second step the multiply and accumulate is to sum up the the
> multiplication of the input sample and fir coefficients!
> So this shifting step , the filtering start at input[1] and the oldest
> sample is dropped??
> I am not sure if i do understand it in the correct way, why i am so
> struggling implementing these filters , are there some tricks to
> follow???
> Thanks 
> 
> Umutesi
> 		
> This message was sent using the Comp.DSP web interface on
> www.DSPRelated.com

You don't need tricks, but you do need to understand the process. You 
have most of it, with some missing details. Read Chapter 6 in 
http://www.dspguide.com/ and more starting with Chapter 14. To be sure 
you understand the details, follow the code examples. When confused, ask 
more questions here. You will also find good material at 
http://www.dspguru.com/ and the free on-line courses at 
http://www.bores.com/.

Jerry
-- 
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������