"Clay S. Turner" <Physics@Bellsouth.net> writes:> [...] > > I'm having trouble with this. Yes, I see that a Huffman code attempts to > > make > > (symbol length)*(symbol frequency) constant over all symbols. How does > > change > > anything about the underlying distribution, though? > > The idea is to try to make each symbol contribute equally to the overall > process. Imagine looking at your data after a huge number of symbols was > received. The idea is to make the info provided by each type of symbol > contribute equally.But this Huffman coding won't do that. Choosing a representation for a symbol doesn't change the probability of the symbol occurring. It does, however, minize the average symbol rate - I certainly see that. Perhaps I'm being blind? -- Randy Yates Sony Ericsson Mobile Communications Research Triangle Park, NC, USA randy.yates@sonyericsson.com, 919-472-1124
how to find the best ADC step size?
Started by ●December 21, 2004
Reply by ●December 22, 20042004-12-22
Reply by ●December 22, 20042004-12-22
Someone wrote:>>>I'm having trouble with this.>>>Yes, I see that a Huffman code attempts to make>>>(symbol length)*(symbol frequency) constant over>>>all symbols. How does change>>>anything about the underlying distribution, though?> "Clay S. Turner" <Physics@Bellsouth.net> writes: >>The idea is to try to make each symbol contribute equally to the overall >>process. Imagine looking at your data after a huge number of symbols was >>received. The idea is to make the info provided by each type of symbol >>contribute equally.Randy Yates wrote:> But this Huffman coding won't do that. Choosing a representation for a > symbol doesn't change the probability of the symbol occurring. It > does, however, minize the average symbol rate - I certainly see > that. Perhaps I'm being blind?The gaussian has infinite tails, so it isn't possible to cover the range with a linear scale ADC. One could then ask for what part of the distribution, when covered with the steps of a six bit ADC, are the symbol probabilities most equal. Without doing the math it isn't so obvious either way. For the case of a very large (lim --> infinity) most of the symbols will have almost no probability. In the limit of very small step size, and assuming that the lower and upper step get the tails, again most steps have almost no probability. So, it would seem that somewhere in between the probability would be more equal. One should then define the appropriate function of step size and find the minimum point. -- glen
Reply by ●December 22, 20042004-12-22
glen herrmannsfeldt <gah@ugcs.caltech.edu> wrote in news:cqceia$n9j$1 @gnus01.u.washington.edu:> The gaussian has infinite tails, so it isn't possible to cover > the range with a linear scale ADC. One could then ask for what > part of the distribution, when covered with the steps of a six > bit ADC, are the symbol probabilities most equal.I think the question is impossible to address in a vacuum. The theoretical handling, while possibly interesting, must take a back seat to the engineering concerns. Start with the questions "Why am I sampling the signal, and what will I be doing with the signal after I sample it?" Then, you can start talking about what happens when the signal falls outside your ADC range. You might even choose to investigate the possibility of a non-linear ADC. I've never heard of such a thing, but there's no reason why it can't be implemented. Scott
Reply by ●December 22, 20042004-12-22
glen herrmannsfeldt wrote:> > > > > Someone wrote: > >>>> I'm having trouble with this. > >>>>Yes, I see that a Huffman code attempts to make > >>>> (symbol length)*(symbol frequency) constant over > >>>>all symbols. How does change > >>>> anything about the underlying distribution, though? > > >> "Clay S. Turner" <Physics@Bellsouth.net> writes: >> >>> The idea is to try to make each symbol contribute equally to the >>> overall process. Imagine looking at your data after a huge number of >>> symbols was received. The idea is to make the info provided by each >>> type of symbol contribute equally. > > > Randy Yates wrote: > >> But this Huffman coding won't do that. Choosing a representation for a >> symbol doesn't change the probability of the symbol occurring. It >> does, however, minize the average symbol rate - I certainly see >> that. Perhaps I'm being blind? > > > The gaussian has infinite tails, so it isn't possible to cover > the range with a linear scale ADC. One could then ask for what > part of the distribution, when covered with the steps of a six > bit ADC, are the symbol probabilities most equal. >... For non-linear encoding, it actually is possible. One way is to divide the cumulative distribution into six parts equal (divide the density function into six equal areas), then have the ADC report the sextile* that the sample falls into. Infinite tails don't bother that scheme. Jerry _________________________ * Rarely the kitchen floor. -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●December 22, 20042004-12-22
"Scott Seidman" <namdiesttocs@mindspring.com> wrote in message news:Xns95C78A9EB3837scottseidmanmindspri@130.133.1.4...> > Then, you can start talking about what happens when the signal falls > outside your ADC range. You might even choose to investigate the > possibility of a non-linear ADC. I've never heard of such a thing, but > there's no reason why it can't be implemented.Hello Scott, Anytime you speak over a landline where the signal is carried digitally, the speech is quantized nonlinearly. Depending on the part of the world you are in, it will be either mu-law (North America) or A-law (pretty much the rest of the world save for a few place like a parts of the Philliphines). A lot of early work with nonlinear quantization was done using Laplacian and Gamma densities as models for the speech. Look up: Paez, M.D., and Glisson, T.H., "Minimum Mean Squared Error Quantization in Speech", IEEE Trans. Comm., Vol. Com-20, pp. 225-230, April 1972 and Max, J., "Quantizing for Minimum Distortion", IRE Trans. Inform. Theory, Vol IT-6, pp 7-12, March 1960 for more details. Clay> > Scott
Reply by ●December 22, 20042004-12-22
Jerry Avins wrote:> glen herrmannsfeldt wrote:(snip)>>The gaussian has infinite tails, so it isn't possible to cover >>the range with a linear scale ADC. One could then ask for what >>part of the distribution, when covered with the steps of a six >>bit ADC, are the symbol probabilities most equal.> For non-linear encoding, it actually is possible. One way is to divide > the cumulative distribution into six parts equal (divide the density > function into six equal areas), then have the ADC report the sextile* > that the sample falls into. Infinite tails don't bother that scheme.To me "step size" implies linear, but I could be convinced otherwise. I would have thought "step sizes", though, for the non-linear case. -- glen
Reply by ●December 22, 20042004-12-22
"Clay S. Turner" <Physics@Bellsouth.net> wrote in news:7%jyd.24$5y3.9@bignews5.bellsouth.net:> > "Scott Seidman" <namdiesttocs@mindspring.com> wrote in message > news:Xns95C78A9EB3837scottseidmanmindspri@130.133.1.4... >> >> Then, you can start talking about what happens when the signal falls >> outside your ADC range. You might even choose to investigate the >> possibility of a non-linear ADC. I've never heard of such a thing, >> but there's no reason why it can't be implemented. > > Hello Scott, > Anytime you speak over a landline where the signal is carried > digitally, the speech is quantized nonlinearly. Depending on the part > of the world you are in, it will be either mu-law (North America) or > A-law (pretty much the rest of the world save for a few place like a > parts of the Philliphines). > > A lot of early work with nonlinear quantization was done using > Laplacian and Gamma densities as models for the speech. > > Look up: > > Paez, M.D., and Glisson, T.H., "Minimum Mean Squared Error > Quantization in Speech", IEEE Trans. Comm., Vol. Com-20, pp. 225-230, > April 1972 > > and > > Max, J., "Quantizing for Minimum Distortion", IRE Trans. Inform. > Theory, Vol IT-6, pp 7-12, March 1960 > > for more details. > > Clay > > > > > > >> >> Scott > > >Learn something new every day! My impression, though, is that the ADC is high-bit linear, and then it's companded to a lower bit count. Is this how it's done, or do the ADC spirits do the whole thing in one step? Scott
Reply by ●December 22, 20042004-12-22
Scott Seidman wrote:>> > > Learn something new every day! My impression, though, is that the ADC is > high-bit linear, and then it's companded to a lower bit count. Is this > how it's done, or do the ADC spirits do the whole thing in one step? > > ScottIt could be done either way. In the old days it was probably done with 256 comparators and a long string of resistors -- today it's probably done with a 12-bit ADC and a look-up table. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●December 22, 20042004-12-22
"Randy Yates" <randy.yates@sonyericsson.com> wrote in message news:xxpllbqjpjf.fsf@usrts005.corpusers.net...> "Clay S. Turner" <Physics@Bellsouth.net> writes: >> [...] >> The idea is to try to make each symbol contribute equally to the overall >> process. Imagine looking at your data after a huge number of symbols was >> received. The idea is to make the info provided by each type of symbol >> contribute equally. > > But this Huffman coding won't do that. Choosing a representation for a > symbol doesn't change the probability of the symbol occurring. It > does, however, minize the average symbol rate - I certainly see > that. Perhaps I'm being blind? > --Hello Randy, The Huffman problem and the quantization problem are related in they both implement methods to effectively flatten out variations. True they are different in that the Huffman problem is trying to minimize the average number of bits per sample and the quantization problem is trying to maximize the information per sample. The differences arise from the constraints and what you are starting with. In one case we have a fixed amount of information, so how few total bits can we fit all of the info in. The theoretical answer is the entropy, but the practical answer (comes from requiring whole numbers of bits in a symbol is the Huffman entropy.) In the other case we have a fixed symbol size, so how can we get the most info per symbol. The connection is the entropy and its maximization requires a flat distribution. In Huffman coding we sort the symbol probabilities into descending order and then we make multiple passes throught the list each time combining the two lowest probilites together. So we are essentially trying to make each path's probability be the same or at leat similar. In the quantization we are just diving up the total probability into N equal regions. You are not being blind, you are just asking how two seemingly different things are related. And the relation is through a flattening out of the probabilty function. I hope this helps to clear some things up. Clay
Reply by ●December 22, 20042004-12-22
"Clay S. Turner" <Physics@Bellsouth.net> writes:> "Randy Yates" <randy.yates@sonyericsson.com> wrote in message > news:xxpllbqjpjf.fsf@usrts005.corpusers.net... > > "Clay S. Turner" <Physics@Bellsouth.net> writes: > >> [...] > >> The idea is to try to make each symbol contribute equally to the overall > >> process. Imagine looking at your data after a huge number of symbols was > >> received. The idea is to make the info provided by each type of symbol > >> contribute equally. > > > > But this Huffman coding won't do that. Choosing a representation for a > > symbol doesn't change the probability of the symbol occurring. It > > does, however, minize the average symbol rate - I certainly see > > that. Perhaps I'm being blind? > > -- > > Hello Randy, > > The Huffman problem and the quantization problem are related in they both > implement methods to effectively flatten out variations. True they are > different in that the Huffman problem is trying to minimize the average > number of bits per sample and the quantization problem is trying to maximize > the information per sample. The differences arise from the constraints and > what you are starting with. In one case we have a fixed amount of > information, so how few total bits can we fit all of the info in. The > theoretical answer is the entropy, but the practical answer (comes from > requiring whole numbers of bits in a symbol is the Huffman entropy.) In the > other case we have a fixed symbol size, so how can we get the most info per > symbol. The connection is the entropy and its maximization requires a flat > distribution. > > In Huffman coding we sort the symbol probabilities into descending order and > then we make multiple passes throught the list each time combining the two > lowest probilites together. So we are essentially trying to make each path's > probability be the same or at leat similar. In the quantization we are just > diving up the total probability into N equal regions. > > You are not being blind, you are just asking how two seemingly different > things are related. And the relation is through a flattening out of the > probabilty function. > > I hope this helps to clear some things up. > > ClayIntriguing stuff! I'm not sure I follow the sorting description, but that's OK. I need to go back and read fully and with undrstanding the seminal Shannon papers. -- Randy Yates Sony Ericsson Mobile Communications Research Triangle Park, NC, USA randy.yates@sonyericsson.com, 919-472-1124
