Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.compression > #1523 > unrolled thread

Fixed-length coding trick

Back to article view | Back to comp.compression

Contents

  Fixed-length coding trick Casper Bang <casper.bang@gmail.com> - 2012-09-22 12:50 -0700
    Re: Fixed-length coding trick Thomas Richter <thor@math.tu-berlin.de> - 2012-09-23 11:20 +0200
    Re: Fixed-length coding trick JoeK <joek06@gmail.com> - 2012-12-04 11:02 -0800
      Re: Fixed-length coding trick Phil Carmody <thefatphil_demunged@yahoo.co.uk> - 2012-12-05 23:25 +0200
    Re: Fixed-length coding trick James Dow Allen <gmail@jamesdowallen.nospam> - 2012-12-06 10:25 +0000
      Re: Fixed-length coding trick James Dow Allen <jdallen2000@yahoo.com> - 2012-12-06 02:47 -0800
    Re: Fixed-length coding trick Ernst <Ernst_Berg@sbcglobal.net> - 2013-04-05 17:38 -0700

#1523 — Fixed-length coding trick

Reading up on some basic information theory, I came by some notes by David S.Touretzky, regarding fixed-length codes, where he hints of a certain trick when a few items are outside the upper-bound of the fixed length:
http://www.cs.cmu.edu/~dst/Tutorials/Info-Theory/

"We can use a special trick to handle the rare cases where heads are more than 4,000 flips apart, but we won't go into the details here.": 

I wonder what this trick is about. Does anyone here have any insight?

[toc] | [next] | [standalone]

#1524

Am 22.09.2012 21:50, schrieb Casper Bang:
> Reading up on some basic information theory, I came by some notes by David S.Touretzky, regarding fixed-length codes, where he hints of a certain trick when a few items are outside the upper-bound of the fixed length:
> http://www.cs.cmu.edu/~dst/Tutorials/Info-Theory/
>
> "We can use a special trick to handle the rare cases where heads are more than 4,000 flips apart, but we won't go into the details here.":
>
> I wonder what this trick is about. Does anyone here have any insight?

Hard to say. He's probably considering escape-codes, i.e. where you 
reserve a single symbol in the fixed length code to signal that another 
coding is to be used for signals that are beyond the coding range of the 
code itself.

HTHH,
	Thomas

[toc] | [prev] | [next] | [standalone]

#1641

On Saturday, September 22, 2012 3:50:00 PM UTC-4, Casper Bang wrote:
> Reading up on some basic information theory, I came by some notes by David S.Touretzky, regarding fixed-length codes, where he hints of a certain trick when a few items are outside the upper-bound of the fixed length

Probably he means expanding a few codes to one more bit.

Say you have the codes:

..00..
..01..
..10..
..11..

The "simple" method of expanding the number of codes is to just keep going lexicographically while extending the shortest codes:

adding one more symbol:

.000..
..01..
..10..
..11..
.100..


Note that you can read the first 2 (lowest) bits and determine if you need to read one more simply by knowing how many times you have "expanded" the set (call this the "water mark.") In this case you've expanded 1 times, and if the integer value of the first 2 bits you have read in is less than 1 (which 00 is) then you need to read in one more bit.

Since the system remains lexicographical, the final value read in can continue to be used as a symbol index into a compact table, or whatever else you are doing with it.

This methodology is best generalized, so that instead of treating the system as "fixed length codes + some extensions" you instead treat it as a "a lexicographical code of N symbols" where the water mark is the difference between N, and N rounded to the nearest power of 2 less than or equal to N. When N is a power of two, the system is precisely equal to using fixed length codes.

In cases where every symbol has equally probability, this system is optimal within the margin of rounding error of the final message length. Otherwise you would want the least probable symbols sorted to the front and back of your symbol table.

[toc] | [prev] | [next] | [standalone]

#1642

JoeK <joek06@gmail.com> writes:
> On Saturday, September 22, 2012 3:50:00 PM UTC-4, Casper Bang wrote:
> > Reading up on some basic information theory, I came by some notes by David S.Touretzky, regarding fixed-length codes, where he hints of a certain trick when a few items are outside the upper-bound of the fixed length
> 
> Probably he means expanding a few codes to one more bit.
> 
> Say you have the codes:
> 
> ..00..
> ..01..
> ..10..
> ..11..
> 
> The "simple" method of expanding the number of codes is to just keep going lexicographically while extending the shortest codes:
> 
> adding one more symbol:
> 
> .000..
> ..01..
> ..10..
> ..11..
> .100..

10 and 100 share the same prefix - you cannot know whether a '10' is the whole 
symbol or just part of it.

However, you could expand the symbols at the other end:

..000..
..001..
..01..
..10..
..11..

Phil
-- 
I'm not saying that google groups censors my posts, but there's a strong link
between me saying "google groups sucks" in articles, and them disappearing.

Oh - I guess I might be saying that google groups censors my posts.

[toc] | [prev] | [next] | [standalone]

#1643

Bit-coding can be fun!

Consider the Elias gamma code for representing positive integers:


         1                =   1
         010              =   2
         011              =   3
         00100            =   4
         00101            =   5
         00110            =   6
         00111            =   7
         000001xxxxx      =   32 to 63

In the above, each code token is prefixed with a length prefix,
which happens to be a string of zeros.

But an equivalent coding exists where termination is denoted by
a 1 in an odd-indexed position:

         1                =   1
         001              =   2
         011              =   3
         00001            =   4
         00011            =   5
         01001            =   6
         01011            =   7
         0x0x0x0x0x1      =   32 to 63

And yet another equivalent exists with BOTH prefix and suffix
termination conditions -- it can be decoded in EITHER direction:

         1                =   1
         000              =   2
         010              =   3
         00100            =   4
         00110            =   5
         01100            =   6
         01111            =   7
         0x1x1x1x1x0      =   32 to 63

James Dow Allen

[toc] | [prev] | [next] | [standalone]

#1644

On Dec 6, 5:25 pm, James Dow Allen <gm...@jamesdowallen.nospam> wrote:
> Bit-coding can be fun!
> ...
>          01111            =   7

s/b 01110

(Once upon a time, I did double- and triple-check my writing.)

[toc] | [prev] | [next] | [standalone]

#1843

On Saturday, September 22, 2012 12:50:00 PM UTC-7, Casper Bang wrote:
> Reading up on some basic information theory, I came by some notes by David S.Touretzky, regarding fixed-length codes, where he hints of a certain trick when a few items are outside the upper-bound of the fixed length:
> 
> http://www.cs.cmu.edu/~dst/Tutorials/Info-Theory/
> 
> 
> 
> "We can use a special trick to handle the rare cases where heads are more than 4,000 flips apart, but we won't go into the details here.": 
> 
> 
> 

 I love bit coding.

 I've used this one..

{0},{1x...,1x.....,} And so on.
Given the most frequent I assign a simple reset (you can use either parity}
So if I am coding a few symbols then 0 for most frequent and 10 110, 1110 - 1111 The width is externally defined. 
If the width is fixed then prefix 1+"xxxx" binary is alright too.

I think this relates to Huffman codes.

Gotta love Binary coders!


> I wonder what this trick is about. Does anyone here have any insight?

[toc] | [prev] | [standalone]

Back to top | Article view | comp.compression

csiph-web