One reason Why, It is Difficult For Me to Guess, at the Variable-Length Encoding of numbers, Chosen By Other People

The problem can come up often in Computing, that instead of having a fixed-length encoding for numbers, we may want to encode a majority of integers which lie in a small range, but out of which a progressively smaller number have larger values. This can lead to variable-length encoding schemes, and MP3 sound compression, logically, is one place where this happens.

If one is trying to guess at what encoding was used, the fact that can stymie a person is, that many methods exist to accomplish exactly that. Huffman Encoding has as a problem, that although the higher-value integers are assigned longer bit-sequences, the relative frequency with which these higher integers will occur, is not the inverse, of their bit-length. This can also be why, a non-default arrangement can be made, that if the size of the integer reaches 15, a full-length value needs to follow.

I have now finally learned, that with MP3 compression, at least the integers smaller than 15, Huffman-Encoded, are intended to be the default case, and values at or above 15 are intended to be the exception. Thus, if the scaling factor is increased, for sure the bit-length of the stream will decrease, until the bit-rate is achieved, that the user set. I got that.

But Why, then, You May Ask, does Dirk choose a different way to accomplish the same thing, and so often?

My answer would be, that formal solutions are often good at compressing the size of integers when those lie in a certain range, but if one value appears in the stream which is much larger than the average, those variable-length encoding schemes can become monsters. ( :1 )

As an example, I read that ‘FLAC’ will record the Linear Predictive Encoding coefficients for a frame accurately, and that this scheme will then Rice Encode the residual each time.

Pure Rice Encoding means, that a remainder of fixed bit-length is encoded with each sample, but that it is given a (variable-length) prefix encoded in straight unary, which states what the multiple of the tunable parameter is (the quotient), that fits into the fixed-length remainder. This choice of a pure unary prefix is questionable, for the reason that I just stated above.

Now, I know that there is also Exponential-Golomb encoding, which like Huffman Coding has a bit-length that grows with the size of the integer to be encoded. But Exponential-Golomb generally produces a bit-length twice as long, as what it would take just to write out the integer on paper.

And so at least a slightly more sophisticated form of encoding exists, which is called Golomb-Rice Encoding, which is essentially Rice Encoding, but in which the prefix, which states the quotient, is prepended in Exponential-Golomb format. Why would they not use it?

And, since it is possible just to put a prefix before an integer in unary, that states its length, an approach which I would be tempted to use, would be just to assume that this unary prefix should be multiplied by a factor such as 3, to arrive at the true length of the integer.

But then a problem with that would be, the fact that this type of prefix would need to be at least 2 bits long, for non-zero values, followed by this multiple of bits belonging to the value, as a minimum. So it will not compress very small values well.

And the reason for this would be the fact, that it would no longer be certain then, that the first bit which actually belongs to the integer, will always be a (1), the way it is with Exponential-Golomb.

And, while I tend to view such encoding schemes as arbitrary, the fashion these days is, always to select a formally-defined one.

In general, my approaches will work well, if a substantial number of values are high.

Dirk

1: ) And what ‘FLAC’ will do in such a case, is just switch the type of the frame this happens in, to a type ‘VERBATIM’ frame. In other words, FLAC would just decide ‘This is one frame we cannot compress’.

FLAC also has a mode, in which each sample is stated as a delta, from the previous one. This corresponds to an ‘LPE’ with one predictor, the coefficient of which is just equal to (+1), relative to which the current value is just the residual…

(Edit 05/25/2016 : ) This is another posting of mine, in which I explain an additional detail about MP3 compression.

Further, ‘FLAC’ is able to encode some of its frames as using LPE, with a variable number of coefficients. I.e., When set to compress more, it will spend its CPU time trying encodings with (!) 6 or more predictors, and will store those in cases where doing so led to more-compact encoding.

While a set of 4 or more coefficients needs to be computed specifically for one frame, via a Statistical Regression Analysis, I have read that for 1, 2, or 3, FLAC just uses a standard set of them. For 1, that will be [ +1 ] . For 2, that will be [ -1, +2 ] . It might seem like a purely academic exercise, to know a standard set of coefficients, which will generally work well if there are only 3 of them. But in fact, having this available offers a non-trivial advantage, over having to store those in the compressed stream.

Since we would presumably be multiplying signed, 16-bit samples with signed, 16-bit coefficients, it will be helpful if the latter only need to fall into the fractional range of ( -1.0 … +1.0 ) . The reason for this is the fact that If we needed to store coefficients which are allowed to exceed ( + 1.0 ) , Then we are blowing another bit of precision just so that one coefficient could do so.

The most recent coefficient will still exceed ( +1.0 ) when there are 3. But as soon as there are 4, none of them would exceed ( +1.0 ) anymore. Therefore, all the coefficients which must be stored, when their number reaches 4 or more, can be made more precise, just because there is a standard set for when we have 3.

 

Print Friendly, PDF & Email

30 thoughts on “One reason Why, It is Difficult For Me to Guess, at the Variable-Length Encoding of numbers, Chosen By Other People”

  1. Great article! We are linking to this great post on our website.
    Keep up tthe great writing.I have a website iin persian language which is about SEO
    and linnk building and backlink exchange, if you were persian I would invite you to
    make a look at mmy website.

  2. Hey! I just wanted to ask if you ever have any issues with hackers?
    My last blog (wordpress) was hacked and I ended up losing several weeks of hard work due to no back up.
    Do you have any methods to protect against hackers?

    1. I have defenses, but find it odd that you were hacked after only a few weeks. I suspect that one way people get hacked, is due to hosted sites, on which their own login is also the only way to manage the files that make up WordPress. One advantage I have, is that I am sitting in front of the Linux computer, which is also hosting my site. That means I can also ‘chown’ and ‘chmod’ files and folders as I like, which will continue to work for me, as long as I don’t do anything dumb.

      My Web-server runs as another username, other than ‘root’, which means that there exists an abundance of files which the server, and thus the PHP scripts, cannot access. And there are core files that define WordPress for me, which the server cannot write to. If you’re using FTP to upload all your files, then all you have is one login.

      Dirk

    1. Unfortunately, I do not know how to get on Yahoo News. If you found my blog-posting there, this can only be, because Yahoo decided to spider me (as Yahoo is also a search engine), and to offer that posting as a search result for you.

      Cheers,
      Dirk

  3. Hi, I do believe this is an excellent blog. I stumbledupon it ;
    ) I’m going to return yet again since i have book marked it.
    Money and freedom is the best way to change, may you be
    rich and continue to help other people.authentic mlb jerseys China

  4. Usually I don’t learn post on blogs, however I
    wish to say that this write-up very pressured me to take a
    look at and do so! Your writing taste has been surprised me.
    Thank you, quite nice article.

  5. Wonderful site you have here but I was curious
    about if you knew of any forums that cover the same topics
    discussed in this article? I’d really like to be a part of community where
    I can get feed-back from other knowledgeable people that share the same interest.
    If you have any suggestions, please let me know. Bless you!

    wholesale jerseys

    1. I believe your question is justified, especially since I’m writing most of what you see here off the top of my head. There could be specific forums dedicated to each of my many topics, as well as University courses which people can take. BTW – I did study in Computing. But for the general case, I’d say “WiKi Is Your Friend – But Use With Caution.” I think the WiKi authors do their best, but sometimes make curious mistakes, which would also become noticeable as discrepancies, if you held my version up against their version point-for-point.

      Dirk

  6. Hey there! Someone in my Facebook group shared this site with
    us so I came to take a look. I’m definitely enjoying the information. I’m bookmarking and will be tweeting
    this to my followers! Exceptional blog and excellent design.

  7. Hello there I am so thrilled I found your web site, I really found you by error, while I was looking on Askjeeve for something else, Nonetheless I am here
    now and would just like to say cheers for a incredible post and a all round enjoyable blog (I also love the
    theme/design), I don’t have time to read it all at the moment but I have book-marked it
    and also included your RSS feeds, so when I have time I will be back to read much more, Please do keep up the fantastic jo.

  8. Wow that was unusual. I just wrote an extremely long comment but after I clicked submit
    my comment didn’t appear. Grrrr… well I’m not writing all
    that over again. Regardless, just wanted to say fantastic
    blog!

    Here is my web site; Seaside Residences – Josh -

    1. Maybe you had not guessed it, but when a new reader submits a comment, that comment must first be Approved by me, before it appears. After that, comments from the same reader will appear automatically.
      One reason I am leery to Approve comments, is the fact that my doing so gives the commenter license to post directly to the site, without requiring subsequent Approvals from me.
      What I do not understand however, is why your original comment did not appear in my Spam folder, next to this one. In any case, this comment has now been Approved by me, as has your email address. :)
      Dirk

  9. Greetings! This is my first comment here so I just wanted to give a quick shout out and tell you I
    truly enjoy reading your blog posts. Can you suggest any other blogs/websites/forums that deal
    with the same subjects? Thanks a lot!

    1. There should be. IMHO, this sort of subject is commonly not described well in Web-sites though, because a formal College or University class is better-apt to do so. I aim to provide context, more than an in-depth explanation, of subjects which should really be studied. What I have found though, is that many compatriots will have misconceptions about how Technology works. And I aim not to bother those friends with direct, lecturing emails. Instead, those friends are as welcome as others are, to read my blog, or to choose not to.
      Dirk

    1. I do not have such a suggestion. As far as my own calculations are concerned, this type of question has evolved into a closed topic, only to be decided by the big search engines and big-wigs. If you find somebody who knows the answer to that, you can let me know what that is. :)
      As for myself, WordPress.org has some mechanism built-in, to announce its content and site-map directly to Google, in XML Format. But again, this is something I leave up to the code of others to do, and Google etc., works with that at its own discretion. Nobody can force Google to accept my site-map, or to apply it in some specific way…
      Dirk

  10. Have you ever thought about adding a little bit more than just your articles?
    I mean, what you say is important and everything. But imagine
    if you added some great photos or video clips to give your
    posts more, “pop”! Your content is excellent but with pics and clips,
    this site could undeniably be one of the best in its niche.
    Great blog!

    1. Unfortunately, I do not have the Windows computer required to test this site in IE. I have tested it on Firefox and Chrome, as well as on Chrome for Android and Dolphin Browser for Android. Also, I have a friend who has no problems viewing it on iOS.

      I am sorry if it is not IE-compatible. This would be due to how the Theme is designed, which was not coded by me. Ditching this theme, would mean losing a lot of the compatibility with mobile devices I already have.

      Dirk

  11. You are so awesome! I do not believe I’ve read a single thing like that before.
    So nice to discover someone with some genuine thoughts on this subject.
    Really.. many thanks for starting this up. This site is something that’s needed on the internet,
    someone with a little originality!

    Here is my homepage DesJarlais affairs

Leave a Reply

Your email address will not be published. Required fields are marked *

Please Prove You Are Not A Robot *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>