Tim Wescott <tim@seemywebsite.com> writes:> On 09/15/2010 08:52 AM, Jake wrote: >>> You don't need to actually stuff zeros in your input for an >>> interpolator. Google for "polyphase filter" or "multirate filter". >> >> Isn't that only true if the filter in your interpolator is an FIR filter ? > > Actually no -- but I'm not aware of any literature on the subject that > I could quote. The interpolated values when there's no input will be > wholly determined by the state of the filter at the end of the last > update with an input and the number of output sample times that has > occurred.I'd never thought of that - great idea! Sounds like it's the stuff of a good paper. -- Randy Yates % "So now it's getting late, Digital Signal Labs % and those who hesitate mailto://yates@ieee.org % got no one..." http://www.digitalsignallabs.com % 'Waterfall', *Face The Music*, ELO
memset or not ?
Started by ●September 15, 2010
Reply by ●September 15, 20102010-09-15
Reply by ●September 15, 20102010-09-15
On 09/15/2010 10:53 AM, Randy Yates wrote:> Tim Wescott<tim@seemywebsite.com> writes: > >> On 09/15/2010 08:52 AM, Jake wrote: >>>> You don't need to actually stuff zeros in your input for an >>>> interpolator. Google for "polyphase filter" or "multirate filter". >>> >>> Isn't that only true if the filter in your interpolator is an FIR filter ? >> >> Actually no -- but I'm not aware of any literature on the subject that >> I could quote. The interpolated values when there's no input will be >> wholly determined by the state of the filter at the end of the last >> update with an input and the number of output sample times that has >> occurred. > > I'd never thought of that - great idea! Sounds like it's the stuff of a > good paper.Except it's already been done, in the 1950's. Maybe the 1960's if people weren't on the ball. How do I know? Because I thought of it just now. (I'm cursed that way). The state-space analysis that I gave is sound, unless I've just had a micro-stroke in the mathematical part of my brain. What's missing are examples for the state-space version, and for someone to go through the tedious math to show how to arrive at a solution that lets you use a cascade of biquads for the actual filtering, deriving the intermediate values from the states of the biquads*. * Assuming that such a solution exists. I strongly suspect it does -- so much so that I'd wager a pitcher of beer at a local brew pub. I think I'm too lazy to pursue it just now, but if I ever have to implement a polyphase IIR I'll certainly look into it. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●September 15, 20102010-09-15
On 15 Sep., 16:07, "Jake" <j...@nospam.invalid.com> wrote:> I have a workbuffer with values that needs to be re-arranged, > so...initially...I did it like this: > > for (i = (N - 1); i >= 0; i--) > { > � �workbuffer[Q * i] = workbuffer[i]; > � �memset(&workbuffer[(Q * i) + 1], 0, (Q-1) * sizeof(int16)); > > } > > but I was told not to use memset. I don't know exactly why I am not allowed > to use memset in a loop. > I guess it's not efficient enough? So I changed the code to this: > > for (i = (N - 1); i >= 0; i--) > { > � �workbuffer[Q * i] = workbuffer[i]; > � �for (j = 0; j < (Q - 1); j++) > � �{ > � � � workbuffer[(Q * i) + 1 + j] = 0; > � �} > > } > > Let's say we have a 16 cell workbuffer B. > > Four values have been stored in the first 4 cells in the workbuffer: B[0], > B[1], B[2] and B[3] the remaining B[k] for k=4 to k=15 are undefined. The > code must re-arrange the 4 values so the workbuffer looks like this: > > B[0],0,0,0,B[1],0,0,0,B[2],0,0,0,B[3],0,0,0 > > The code is for an interpolator and in the above example N is the number of > samples in the workbuffer before re-arrangement. So N would be 4! And Q > would be an interpolation factor equal to 4. > > Any suggestions for improvement? > > Comments about not using memset in a loop are also welcomed. > > Thank you.Usually memset/memcpy are optimized very well (way better than looping) when used on big chunks of memory. So if you resist on using a zero-stuffed array I would do the following (pseudo-code): memset(interp_buffer,0,sizeof(interp_buffer)); for(int ncnt = 0;ncnt < nmax;ncnt++) { interp_buffer[ncnt*nstride] = working_buffer[ncnt]; } It is not the most efficient way but should be faster than using memset on small memory chunks. It also makes sure interp_buffer is initialized with valid values and stays readable. Greetz, Sebastian
Reply by ●September 15, 20102010-09-15
On 15 Sep., 16:07, "Jake" <j...@nospam.invalid.com> wrote:> I have a workbuffer with values that needs to be re-arranged, > so...initially...I did it like this: > > for (i = (N - 1); i >= 0; i--) > { > � �workbuffer[Q * i] = workbuffer[i]; > � �memset(&workbuffer[(Q * i) + 1], 0, (Q-1) * sizeof(int16)); > > } > > but I was told not to use memset. I don't know exactly why I am not allowed > to use memset in a loop. > I guess it's not efficient enough? So I changed the code to this: > > for (i = (N - 1); i >= 0; i--) > { > � �workbuffer[Q * i] = workbuffer[i]; > � �for (j = 0; j < (Q - 1); j++) > � �{ > � � � workbuffer[(Q * i) + 1 + j] = 0; > � �} > > } > > Let's say we have a 16 cell workbuffer B. > > Four values have been stored in the first 4 cells in the workbuffer: B[0], > B[1], B[2] and B[3] the remaining B[k] for k=4 to k=15 are undefined. The > code must re-arrange the 4 values so the workbuffer looks like this: > > B[0],0,0,0,B[1],0,0,0,B[2],0,0,0,B[3],0,0,0 > > The code is for an interpolator and in the above example N is the number of > samples in the workbuffer before re-arrangement. So N would be 4! And Q > would be an interpolation factor equal to 4. > > Any suggestions for improvement? > > Comments about not using memset in a loop are also welcomed. > > Thank you.Usually memset/memcpy are optimized very well (way better than looping) when used on big chunks of memory. So if you resist on using a zero-stuffed array I would do the following (pseudo-code): memset(interp_buffer,0,sizeof(interp_buffer)); for(int ncnt = 0;ncnt < nmax;ncnt++) { interp_buffer[ncnt*nstride] = working_buffer[ncnt]; } It is not the most efficient way but should be faster than using memset on small memory chunks. It also makes sure interp_buffer is initialized with valid values and stays readable. Greetz, Sebastian
Reply by ●September 15, 20102010-09-15
On 9/15/2010 11:18 AM, Tim Wescott wrote:> On 09/15/2010 10:53 AM, Randy Yates wrote: >> Tim Wescott<tim@seemywebsite.com> writes: >> >>> On 09/15/2010 08:52 AM, Jake wrote: >>>>> You don't need to actually stuff zeros in your input for an >>>>> interpolator. Google for "polyphase filter" or "multirate filter". >>>> >>>> Isn't that only true if the filter in your interpolator is an FIR >>>> filter ? >>> >>> Actually no -- but I'm not aware of any literature on the subject that >>> I could quote. The interpolated values when there's no input will be >>> wholly determined by the state of the filter at the end of the last >>> update with an input and the number of output sample times that has >>> occurred. >> >> I'd never thought of that - great idea! Sounds like it's the stuff of a >> good paper. > > Except it's already been done, in the 1950's. Maybe the 1960's if people > weren't on the ball. > > How do I know? Because I thought of it just now. > > (I'm cursed that way). > > The state-space analysis that I gave is sound, unless I've just had a > micro-stroke in the mathematical part of my brain. What's missing are > examples for the state-space version, and for someone to go through the > tedious math to show how to arrive at a solution that lets you use a > cascade of biquads for the actual filtering, deriving the intermediate > values from the states of the biquads*. > > * Assuming that such a solution exists. I strongly suspect it does -- so > much so that I'd wager a pitcher of beer at a local brew pub. I think > I'm too lazy to pursue it just now, but if I ever have to implement a > polyphase IIR I'll certainly look into it. >Crochiere and Rabiner. Multirate Digital Signal Processing. Prentice-Hall: 1983. "Multistage Decimators and Interpolators Based on IIR Filter Designs" pp. 235-244. -- Rob Gaddi, Highland Technology Email address is currently out of order
Reply by ●September 15, 20102010-09-15
On 09/15/2010 11:51 AM, Rob Gaddi wrote:> On 9/15/2010 11:18 AM, Tim Wescott wrote: >> On 09/15/2010 10:53 AM, Randy Yates wrote: >>> Tim Wescott<tim@seemywebsite.com> writes: >>> >>>> On 09/15/2010 08:52 AM, Jake wrote: >>>>>> You don't need to actually stuff zeros in your input for an >>>>>> interpolator. Google for "polyphase filter" or "multirate filter". >>>>> >>>>> Isn't that only true if the filter in your interpolator is an FIR >>>>> filter ? >>>> >>>> Actually no -- but I'm not aware of any literature on the subject that >>>> I could quote. The interpolated values when there's no input will be >>>> wholly determined by the state of the filter at the end of the last >>>> update with an input and the number of output sample times that has >>>> occurred. >>> >>> I'd never thought of that - great idea! Sounds like it's the stuff of a >>> good paper. >> >> Except it's already been done, in the 1950's. Maybe the 1960's if people >> weren't on the ball. >> >> How do I know? Because I thought of it just now. >> >> (I'm cursed that way). >> >> The state-space analysis that I gave is sound, unless I've just had a >> micro-stroke in the mathematical part of my brain. What's missing are >> examples for the state-space version, and for someone to go through the >> tedious math to show how to arrive at a solution that lets you use a >> cascade of biquads for the actual filtering, deriving the intermediate >> values from the states of the biquads*. >> >> * Assuming that such a solution exists. I strongly suspect it does -- so >> much so that I'd wager a pitcher of beer at a local brew pub. I think >> I'm too lazy to pursue it just now, but if I ever have to implement a >> polyphase IIR I'll certainly look into it. >> > > Crochiere and Rabiner. Multirate Digital Signal Processing. > Prentice-Hall: 1983. "Multistage Decimators and Interpolators Based on > IIR Filter Designs" pp. 235-244.'83?!? Wow -- I'm moving up! Of course, that's when it found it's way into a book. I remember the first time I thought of some cool and 'unique' innovation in sampled data systems, only to find it in the literature -- for implementation on vacuum tubes. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com Do you need to implement control loops in software? "Applied Control Theory for Embedded Systems" was written for you. See details at http://www.wescottdesign.com/actfes/actfes.html
Reply by ●September 15, 20102010-09-15
Jake <jake@nospam.invalid.com> wrote:>> Comments? You are the imbecile indeed.> I appreciate your help, but your attitude really sucks. > You must be very lonely.> Anyway...Thank you for the code snippet.You get used to it after a while. If you don't read this group often, then likely it hasn't happened yet. As far as memset(), one generally assumes that it is optimized for large blocks, and so might be slower for smaller ones. Vladamir's loops fill the buffer from the back, which may or may not be optimal on a system with cache. Though for 16 words, cache isn't likely to be the big problem. -- glen
Reply by ●September 15, 20102010-09-15
Tim Wescott <tim@seemywebsite.com> wrote: (snip)> '83?!? Wow -- I'm moving up! Of course, that's when it found it's way > into a book.> I remember the first time I thought of some cool and 'unique' innovation > in sampled data systems, only to find it in the literature -- for > implementation on vacuum tubes.Better than Cooley and Tukey who found out, years later, that their algorithm had been published by Gauss in 1805. (Without looking it up, I believe 1805 is before vacuum tubes.) -- glen
Reply by ●September 15, 20102010-09-15
On Sep 15, 4:13�pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:> Jake <j...@nospam.invalid.com> wrote: > >> Comments? �You are the imbecile indeed. > > I appreciate your help, but your attitude really sucks. > > You must be very lonely. > > Anyway...Thank you for the code snippet. > > You get used to it after a while. �If you don't read this group > often, then likely it hasn't happened yet.Vlad is sorta like that. he hasn't called me a pathetic imbecile lamer yet. (kinda hard to be all three at the same time, sorta like being called a "commie fag junkie".) at least not that i noticed.> As far as memset(), one generally assumes that it is optimized > for large blocks, and so might be slower for smaller ones.i dunno even what memset() is. what is it? will i have to google it? is it in the stdClib? r b-j
Reply by ●September 15, 20102010-09-15
On Sep 15, 9:22�pm, robert bristow-johnson <r...@audioimagination.com> wrote:> i dunno even what memset() is. �what is it? �will i have to google > it? �is it in the stdClib?okay, so now i looked it up, so now the question is "why is it?". similar to memcopy(). i could see an inline macro for it. but not a library function. Vlad, am i a lamer because i didn't know about memset()? r b-j
