Re: How to downsample this signal?

From	Randy Yates <randyy@garnerundergroundinc.com>
Newsgroups	comp.dsp
Subject	Re: How to downsample this signal?
Organization	Garner Underground, Inc.
References	(7 earlier) <ofe7r4$oc4$1@dont-email.me> <8760h0pw02.fsf@garnerundergroundinc.com> <591b3f08.489072937@news.eternal-september.org> <87vap0mw6m.fsf@garnerundergroundinc.com> <87d1b8mvqx.fsf@garnerundergroundinc.com>
Date	2017-05-16 15:50 -0400
Message-ID	<877f1gmvi4.fsf@garnerundergroundinc.com> (permalink)

Show all headers | View raw

Randy Yates <randyy@garnerundergroundinc.com> writes:

> Randy Yates <randyy@garnerundergroundinc.com> writes:
>
>> 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+.
>
> In light of the light coming on due to Rick's post that came about the
> same time as I was writing this, I'll have to retract. 

This is a type of systolic array?
-- 
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