Groups | Search | Server Info | Login | Register

Groups > comp.dsp > #33842

Re: How to downsample this signal?

Show all headers | View raw

eric.jacobsen@ieee.org writes:

> On Tue, 16 May 2017 13:11:25 -0400, Randy Yates
> <randyy@garnerundergroundinc.com> wrote:
>
>>rickman <gnuarm@gmail.com> writes:
>>
>>> On 5/15/2017 11:49 AM, Randy Yates wrote:
>>>> rickman <gnuarm@gmail.com> writes:
>>>>
>>>>> On 5/15/2017 1:21 AM, Piotr Wyderski wrote:
>>>>>> rickman wrote:
>>>>>>
>>>>>>> Are the 248 words for data or also program?
>>>>>>
>>>>>> Data only, there are dedicated code memories. The control part
>>>>>> is totally crazy: there are two separate code memories working
>>>>>> in parallel (they take both paths simultaneosly in order to
>>>>>> provide instructions with no delay in the case of a branch).
>>>>>> But there is no such thing as a program counter, the code
>>>>>> memories store instructions at consecutive addresses without
>>>>>> any deeper structure. A run of instructions is called a block
>>>>>> and is ended with the presence of a jump instruction. There
>>>>>> is also a third control memory which stores the information
>>>>>> where the i-th block begins and to which j-th state the FSM
>>>>>> should go in the case of a branch. In short, hardware basic
>>>>>> blocks. The data path is a VLIW with exposed pipelining,
>>>>>> which adds fun.
>>>>>>
>>>>>>> That should be plenty of room for coefficients.
>>>>>>
>>>>>> But doesn't the FIR require a lot of cells for
>>>>>> the past data values?
>>>>>
>>>>> Like I said, I wrote this a long time ago, so I am not the resource to
>>>>> be asking.  I can't picture how it works, but I specifically remember
>>>>> NOT needing to store previous data inputs.  I am thinking you store
>>>>> outputs which will be fewer because of the decimation.  As the input
>>>>> data comes in the output samples can be built up and when one is
>>>>> complete it is outputted and replaced by a new one.
>>>>>
>>>>> But read a proper reference.  If I wasn't busy today I'd dig this up
>>>>> for you.
>>>>
>>>> Yes you do need to store N-1 previous inputs (plus 1 current input) for
>>>> a length N polyphase FIR decimation by M. Just think first principles:
>>>> for any output y[k], you need N inputs to compute it, even if k = n*M.
>>>
>>> I am pretty sure that conclusion is not correct.  When I was asked to
>>> implement a polyphase filter that was the part I had trouble getting
>>> my head around but finally understood how it worked.  At the time this
>>> was being done on a very early DSP chip with very limited memory, so
>>> storing the N-1 previous samples was not an option.  The guy
>>> presenting the problem to me was the classic engineer who could read
>>> and understand things, but couldn't explain anything to other people.
>>> So I had to take the paper he gave me and finally figure it out for
>>> myself.
>>>
>>> I will dig around when I get a chance and figure out exactly how this
>>> worked.  But the basic idea is that instead of saving multiple inputs
>>> and calculating the outputs one at a time (iterating over the stored
>>> inputs) - as each input comes in it is iterated over the stored
>>> outputs and each output is ... well output, when it has been fully
>>> calculated. Since there are fewer outputs than inputs (by the
>>> decimation factor of M) you store fewer outputs than you would inputs.
>>>
>>> This is not hard to understand if you just stop thinking it *has* to
>>> be the way you are currently seeing it.  (shown here with simplified
>>> notation since it is too messy to show the indexes with decimation)
>>>
>>> y(k)   = a(0)x(i)   + a(1)x(i-1) + a(2)x(i-2) + ...
>>> y(k+1) = a(0)x(i+1) + a(1)x(i)   + a(2)x(i-1) + ...
>>> y(k+2) = a(0)x(i+2) + a(1)x(i+1) + a(2)x(i)   + ...
>>> y(k+3) = a(0)x(i+3) + a(1)x(i+2) + a(2)x(i+1) + ...
>>>
>>> Instead of thinking you have to calculate all the terms of y(k) at one
>>> time (and so store the last N*M values of x), consider that when x(i)
>>> arrives, you can calculate the x(i) terms and add them into y(k)
>>> (which is then output) and y(k+1), y(k+2)...  This allows the storage
>>> of fewer values by a factor of M.  It does require more memory fetches
>>> than the standard MAC calculation since you have to fetch not only the
>>> coefficient and the input, but also the intermediate output value
>>> being calculated on each MAC operation.
>>>
>>> Maybe I won't have to dig it up.  I'm pretty sure this is how it
>>> worked. It ties in nicely with the "polyphase" aspect to allow a
>>> minimum number of calculations on arrival of each input since not all
>>> the coefficients are used on each input.  So the coefficients are
>>> divided into "phases" (N/M coefficients) with only one phase used for
>>> any given input sample.
>>
>>Counter-example: Consider M = 8, N = 8 (8 coefficients and decimating by
>>8). Then each output y(k) depends on x(k*M + n), 0 < n < M - 1, and thus
>>the sets of input values for different outputs are disjoint.
>
> How each input will be used for each output is known when that input
> arrives, so if all possible ouputs for that input have their own
> partial product accumulator, the input can be multiplied by the
> various coefficients for each partial product and accumulated in each,
> and then forgotten.
>
> It's just another way to do it, but it can save a lot of hardware in a
> hardware implementation, especially in an FPGA where the
> multiply-accumulators are already built and just laying around,
> anyway.

So are you asserting this is not a counter-example? 

To state that an N-tap FIR decimator does not require all N inputs for
an output at time k is, in general, not true, as I have shown. 

I believe what you are claiming is that IN CERTAIN CASES you can get
away with not using all N inputs at output time k. That I can agree
with. However, neither you nor Rick put a constraint on your assertion.

And I can see that, in certain situations, this can be mo' better,
namely when you have one or more MACs sitting around not being used (as
you said) and N > M. But in general it hardly seems a storage saver as a
MAC is a storage element+.
-- 
Randy Yates, Embedded Firmware Developer
Garner Underground, Inc.
866-260-9040, x3901
http://www.garnerundergroundinc.com

Back to comp.dsp | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

How to downsample this signal? Piotr Wyderski <peter.pan@neverland.mil> - 2017-05-13 09:23 +0200
  Re: How to downsample this signal? Evgeny Filatov <filatov.ev@mipt.ru> - 2017-05-13 15:42 +0300
  Re: How to downsample this signal? bitterlemon40@yahoo.ie - 2017-05-13 07:53 -0700
  Re: How to downsample this signal? rickman <gnuarm@gmail.com> - 2017-05-13 11:48 -0400
  Re: How to downsample this signal? Randy Yates <yates@digitalsignallabs.com> - 2017-05-13 12:58 -0400
    Re: How to downsample this signal? rickman <gnuarm@gmail.com> - 2017-05-13 16:04 -0400
      Re: How to downsample this signal? Randy Yates <yates@digitalsignallabs.com> - 2017-05-14 14:19 -0400
    Re: How to downsample this signal? Piotr Wyderski <peter.pan@neverland.mil> - 2017-05-15 00:42 +0200
      Re: How to downsample this signal? rickman <gnuarm@gmail.com> - 2017-05-15 00:46 -0400
        Re: How to downsample this signal? Piotr Wyderski <peter.pan@neverland.mil> - 2017-05-15 07:21 +0200
          Re: How to downsample this signal? rickman <gnuarm@gmail.com> - 2017-05-15 10:51 -0400
            Re: How to downsample this signal? Randy Yates <randyy@garnerundergroundinc.com> - 2017-05-15 11:49 -0400
              Re: How to downsample this signal? Randy Yates <randyy@garnerundergroundinc.com> - 2017-05-15 17:20 -0400
              Re: How to downsample this signal? rickman <gnuarm@gmail.com> - 2017-05-16 02:59 -0400
                Re: How to downsample this signal? eric.jacobsen@ieee.org - 2017-05-16 15:59 +0000
                Re: How to downsample this signal? rickman <gnuarm@gmail.com> - 2017-05-16 15:36 -0400
                Re: How to downsample this signal? Randy Yates <randyy@garnerundergroundinc.com> - 2017-05-16 13:11 -0400
                Re: How to downsample this signal? eric.jacobsen@ieee.org - 2017-05-16 18:08 +0000
                Re: How to downsample this signal? Randy Yates <randyy@garnerundergroundinc.com> - 2017-05-16 15:35 -0400
                Re: How to downsample this signal? Randy Yates <randyy@garnerundergroundinc.com> - 2017-05-16 15:45 -0400
                Re: How to downsample this signal? Randy Yates <randyy@garnerundergroundinc.com> - 2017-05-16 15:50 -0400
                Re: How to downsample this signal? rickman <gnuarm@gmail.com> - 2017-05-16 21:36 -0400
                Re: How to downsample this signal? rickman <gnuarm@gmail.com> - 2017-05-16 15:35 -0400
                Re: How to downsample this signal? Randy Yates <randyy@garnerundergroundinc.com> - 2017-05-16 15:36 -0400
                Re: How to downsample this signal? Randy Yates <randyy@garnerundergroundinc.com> - 2017-05-16 15:40 -0400
                Re: How to downsample this signal? rickman <gnuarm@gmail.com> - 2017-05-16 22:06 -0400
                Re: How to downsample this signal? Randy Yates <yates@digitalsignallabs.com> - 2017-05-17 01:25 -0400
      Re: How to downsample this signal? Evgeny Filatov <filatov.ev@mipt.ru> - 2017-05-15 14:51 +0300
      Re: How to downsample this signal? Randy Yates <randyy@garnerundergroundinc.com> - 2017-05-15 10:37 -0400
  Re: How to downsample this signal? makolber@yahoo.com - 2017-05-15 06:27 -0700
    Re: How to downsample this signal? Piotr Wyderski <peter.pan@neverland.mil> - 2017-05-15 20:39 +0200

csiph-web