Reply by Greg Berchin June 11, 20062006-06-11
On Sun, 11 Jun 2006 20:48:23 GMT, robert bristow-johnson
<rbj@audioimagination.com> wrote:

>i guess i don't understand why or where there would be quantization errors >of larger than &#2013266097;1/2 LSB.
If "Eq" is the quantization error, and you allow EITHER "rounding up" OR "rounding down", then 0 <= |Eq| < |1 LSB|. If you constrain 0 <= |Eq| <= |&#2013266109; LSB|, then you must always "round toward nearest". Quantizing all filter coefficients by "rounding toward nearest" yields a unique solution that minimizes both the absolute error (DC component) and the total squared error, but offers no degrees of freedom to optimize the spectral characteristics of the quantized filter. Removing the "round toward nearest" constraint, but constraining 0 <= |Eq| < |1 LSB|, gives 2^N degrees of freedom for the entire set of N quantized coefficients. If you define some other measure of "goodness of fit", based for example upon the spectrum of the quantized filter, then there will be one of those 2^N sets of quantized coefficients that is "best" under your alternate figure of merit, even though it is not "best" for absolute error or total squared error. If you allow |Eq| to be even larger than |1 LSB| then you have even more degrees of freedom, but finding that "best" quantization scheme quickly becomes computationally untenable. Having |Eq| >= |1 LSB| is not without precedent -- it happens all the time in a noise-shaped quantizer like the one that you described, because of the feedback of previous error terms. Greg
Reply by robert bristow-johnson June 11, 20062006-06-11
in article kgco825bn1nsatbi8i5lgksv6eojqd7gdd@4ax.com, Greg Berchin at
76145.2455@compuswerve.com wrote on 06/11/2006 11:38:

> On Sat, 10 Jun 2006 01:14:53 GMT, robert bristow-johnson > <rbj@audioimagination.com> wrote: > >> |1 - (e^-jw)*G(e^jw)|^2 = A*|H(e^jw)|^2 >> >> for some real constant A>0 . >> >> so given the "ideal" FIR, h[n]. with spectrum H(e^jw), you want to design >> G(z) so that the above equation is as accurate as possible, then run your >> h[n] through the noise-shaped quantizer: >> >> >> .-------------. >> e1[n] .---| (z^-1)*G(z) |<----.----- e[n] = hq[n] - h1[n] >> | '-------------' | >> v - v >> h[n] ---->(+)-------------------->(+)-------> hq[n] >> + h1[n] > > I'm wondering about the practicality of this approach.
it's a good thing to wonder about. i'm still thinking about how to design G(z). the Jens J&#2013266168;rgen Nielsen paper deals with implementation a bit more.
> It seems like > h[n] might be highly constrained -- not only in word length, but in > number of coefficients. But hq[n] could be of infinite length, so you > have basically traded word length for filter length.
yup, but i don't think that, during the quantization process (where hq[n] gets discovered), that once h[n] goes to zero that the "ringing" of the 1 - (z^-1)*G(z) system will exceed the LSB step of the quantizer for very long (so those samples of hq[n] will be zero once e1[n] gets small enough). i have no proof of that, of course.
> For "small" filters it would be possible to "brute force" the answer. > If you constrain each quantization to either "round up" or "round down", > then for an N-length filter there are 2^N possible quantization sets. > With modern computational capabilities it would be possible to test > every one of them in a reasonable amount of time, for values of N up to > about 32 or so -- double that if there is symmetry in the coefficients > and quantization set.
probably something like adding some small random numbers before quantizing it and "annealing" the set could also be done. dunno how to optimize it. i think that Parks-McClellan could be modified to search for the extrema on the spectrum of the *quantized* h[n] during each particular recursive pass. i s'pose for those FPGA guys who like to zero some coefficients (us DSP guys wouldn't mind zeroing some regular set of coefs like in half-band filters), you could also reprogram P-McC in the later recursions to set the smallest coefs to zero and work with optimizing the remaining ones.
> For filters larger than that, or to accommodate individual quantization > errors larger than &#2013266097;1 LSB, some other approach would be necessary.
i guess i don't understand why or where there would be quantization errors of larger than &#2013266097;1/2 LSB. in article 448c5e14$0$5538$ba620e4c@news.skynet.be, NewLine at umts_remove_all_this@skynet.be wrote on 06/11/2006 14:16:
>> does that make sense? >> > > sure..tnx for all the effort describing this!
it beats finding any old posts where i or someone else went through it. (i made a mistake and typed "q[n]" when i meant to say "e[n]".) the Jens J&#2013266168;rgen Nielsen paper should probably be the next place to go with this. although i have done noise-shaping on signals in my life (and still do), i have never done this to get some kind of quantized h[n]. i just knew of its existence. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by NewLine June 11, 20062006-06-11
> does that make sense. >
sure..tnx for all the effort describing this!
Reply by Greg Berchin June 11, 20062006-06-11
On Sat, 10 Jun 2006 01:14:53 GMT, robert bristow-johnson
<rbj@audioimagination.com> wrote:

> |1 - (e^-jw)*G(e^jw)|^2 = A*|H(e^jw)|^2 > >for some real constant A>0 . > >so given the "ideal" FIR, h[n]. with spectrum H(e^jw), you want to design >G(z) so that the above equation is as accurate as possible, then run your >h[n] through the noise-shaped quantizer: > > > .-------------. > e1[n] .---| (z^-1)*G(z) |<----.----- e[n] = hq[n] - h1[n] > | '-------------' | > v - v > h[n] ---->(+)-------------------->(+)-------> hq[n] > + h1[n]
I'm wondering about the practicality of this approach. It seems like h[n] might be highly constrained -- not only in word length, but in number of coefficients. But hq[n] could be of infinite length, so you have basically traded word length for filter length. For "small" filters it would be possible to "brute force" the answer. If you constrain each quantization to either "round up" or "round down", then for an N-length filter there are 2^N possible quantization sets. With modern computational capabilities it would be possible to test every one of them in a reasonable amount of time, for values of N up to about 32 or so -- double that if there is symmetry in the coefficients and quantization set. For filters larger than that, or to accommodate individual quantization errors larger than &#2013266097;1 LSB, some other approach would be necessary. Greg
Reply by robert bristow-johnson June 10, 20062006-06-10
in article C0AF954C.153EA%rbj@audioimagination.com, robert bristow-johnson
at rbj@audioimagination.com wrote on 06/09/2006 21:14:

 
> otherwise, all i can recommend is Google.
Google: quantized FIR coefficients (no quotes) and you get a lot of nice hits including http://www.ece.vt.edu/fac_support/dspcl/docs/SPMag03.pdf and http://hjem.get2net.dk/jjn/quantfir.htm http://hjem.get2net.dk/jjn/download/quantfir.pdf the latter pair approaches this problem from the noise shaping POV as i had just previously. probably he does a better job. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by robert bristow-johnson June 9, 20062006-06-09
in article 4489e9fe$0$1216$ba620e4c@news.skynet.be, NewLine at
umts_remove_all_this@skynet.be wrote on 06/09/2006 17:37:

>> >> one way to do that is with noise shaping the impulse response as it is >> input to the 8-bit quantizer. but we steer the noise from the stopband >> (where the absolute error in the FIR gain is more of a problem) into >> the passband where it is less of a problem. >> > > Sounds interesting...do you have any more details on how to perform this > noise shaping, or a pointer to a paper/book?
quantizing: .------. x[n] ------>| Q{.} |---------> xq[n] '------' xq[n] = Q{ x[n] } = x[n] + e[n] Q{.} is the quantization operator (rounding or truncation) and e[n] =def xq[n] - x[n] = Q{x[n]} - x[n] is the quantization error (or "quantization noise"). it can be computed by taking the output of the quantizer and subtracting the input. what this does is model the quantizer as some kind of additive error source: .----- e[n] = xq[n] - x[n] | v x[n] ---------->(+)----------> xq[n] here, the transfer function from e[n] to xq[n] is Xq(z)/E(z) = 1 but e[n] is usually considered to be much smaller than x[n]. now if that is true (x[n] much larger than the round-off or truncation error of the quantizer), then the round-off error could be anything within -1/2 LSB and +1/2 LSB (and pretty random) and the q[n] error will be pretty white (up to Nyquist). so the spectrum of xq[n] is pretty much the same as x[n] except for some sorta flat white noise spectrum added in. if the spectrum of x[n] had some gaps in it where the energy got very low, then the whitish spectrum of e[n] fills in those gaps in the spectrum. noise shaping: .-------------. e1[n] .---| (z^-1)*G(z) |<----.----- e[n] = xq[n] - x1[n] | '-------------' | v - v x[n] ---->(+)-------------------->(+)-------> xq[n] + x1[n] notice that the output of the filter G(z) is subtracted from x[n] to result in x1[n] which is what is applied to the quantizer Q{.}. so the output now is xq[n] = Q{ x1[n] } = x1[n] + e[n] where x1[n] = x[n] - e1[n] and e1[n] = g[n] (*) e[n-1] (*) means discrete convolution also, the filter (z^-1)*G(z) must have at least one sample delay built in because it does not know the present roundoff error (the roundoff of the present sample hasn't happened yet) only the past roundoff errors, e[n-1], e[n-2], etc. G(z) can be any realizable (causal) filter and is actually the filter that is implemented (not (z^-1)*G(z)), but it only sees the past sample quantization errors, not the current quantization error. now the transfer function of quantization noise to output is Xq(z)/E(z) = 1 - (z^-1)*G(z) now G(z) has to be designed in such a way so that |Xq(z)/E(z)| will steer or "shape" the spectrum of the noise away from where you don't want it and put it where you don't care as much. the simplest noise shaper is one where G(z) = 1 so the noise shaping filter would be Xq(z)/E(z) = 1 - (z^-1) with frequency response: |Xq(e^jw)/E(e^jw)| = |1 - e^(-jw)| = 2*sin(w/2) and that is a high pass filter with no gain at DC at all. that means there is no noise at DC, little noise at low frequencies and increased quantization noise around Nyquist. now, for FIR filter design, what we are talking about is h[n] (with spectrum H(z) where z = e^jw) instead of x[n] and the quantized impulse response is hq[n] with spectrum Hq(z). if we look at the gain of the FIR filter with a "dB lens", we will care more about errors in the spectrum Hq(e^jw) at frequencies where |H(e^jw)| is small (resulting in bigger dB error) than where |H(e^jw)| is large. so we want |Hq(e^jw)/E(e^jw)| = |1 - (e^-jw)*G(e^jw)| proportional to |H(e^jw)| or |1 - (e^-jw)*G(e^jw)|^2 = A*|H(e^jw)|^2 for some real constant A>0 . so given the "ideal" FIR, h[n]. with spectrum H(e^jw), you want to design G(z) so that the above equation is as accurate as possible, then run your h[n] through the noise-shaped quantizer: .-------------. e1[n] .---| (z^-1)*G(z) |<----.----- e[n] = hq[n] - h1[n] | '-------------' | v - v h[n] ---->(+)-------------------->(+)-------> hq[n] + h1[n] or .--------. e1[n] .---| G(z) |<----- e[n-1] = hq[n-1] - h1[n-1] | '--------' v - .------. h[n] ---->(+)----------------->| Q{.} |------> hq[n] = Q{h1[n]} + h1[n] '------' and see what you get out: hq[n]. does that make sense. otherwise, all i can recommend is Google. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by June 9, 20062006-06-09
Rick,

ONEoverT digital filter designer will let you see the responses of
different coefficient wordlengths. you won't get any code output with
the demo version however, but you probably don't need the full version
anyway.

Bob



realimag wrote:
> I am also working on a cpld project where I need to see the frequency > responses of different coefficient wordlengths in order to obtain the > optimum result as space requirements on the device are very tight. Are > there any free utilities on the web to achieve this? > > Rick > > Mr. Ken wrote: > > I am quantizing an FIR filter's coefficients into 8-bit signed integers, > > which will be coded into hardware. How do I describe the errors in > > the quantization in my report? I only know of frequency response > > before and after quantization. > > > > TIA
Reply by NewLine June 9, 20062006-06-09


> > one way to do that is with noise shaping the impulse response as it is > input to the 8-bit quantizer. but we steer the noise from the stopband > (where the absolute error in the FIR gain is more of a problem) into > the passband where it is less of a problem. >
Sounds interesting...do you have any more details on how to perform this noise shaping, or a pointer to a paper/book?
Reply by Mr. Ken June 8, 20062006-06-08
"realimag" <realimag@hotmail.com> wrote in message
news:1149759795.627501.89100@h76g2000cwa.googlegroups.com...
> I am also working on a cpld project where I need to see the frequency > responses of different coefficient wordlengths in order to obtain the > optimum result as space requirements on the device are very tight. Are > there any free utilities on the web to achieve this? > > Rick >
If you use Xilinx FPGA in ISE, you may as well write some scripts to automate the entire procedure, then you can run fitting for all the wordlength. For Altera, I am not sure.
Reply by realimag June 8, 20062006-06-08
I am also working on a cpld project where I need to see the frequency
responses of different coefficient wordlengths in order to obtain the
optimum result as space requirements on the device are very tight. Are
there any free utilities on the web to achieve this?

Rick

Mr. Ken wrote:
> I am quantizing an FIR filter's coefficients into 8-bit signed integers, > which will be coded into hardware. How do I describe the errors in > the quantization in my report? I only know of frequency response > before and after quantization. > > TIA