Re: Efficient unbiased prefix-free encodings

On 11 Dec, 23:46, "joeship...@xxxxxxx" <JoeShip...@xxxxxxx> wrote:
I am looking for an efficient way to encode an n-letter alphabet so
that a stream of random bits will produce an unbiased stream of random
elements of {0,...,n-1}. An easy way to do this is to encode modulo
the next power of 2 greater than (a multiple of) n, then reduce modulo
n, but in the event of an "overflow" (>= the last multiple of n
available) shift left, add the next bit, and take modulo the next
power of 2 and iterate.

For example, suppose n=23 and the bit stream goes 1 1 1 0 0 1 0 ....
Proceed as follows: The successively longer binary numbers this stream
gives, in decimal, are 1, 3, 7, 14, 28, 57, 114. The first of these
which has a multiple of 23 between it and the next higher power of 2
is 114, so take 114 mod 23 and return 22. Start over with the next bit
to get the next letter. It's easy to show that the resulting stream of
letters is random and unbiased.

This requires, on average, 5.702 bits per letter in a 23-letter
alphabet, and 5.711 bits per letter in a 17-letter alphabet, etc. Can
this be done more efficiently while preserving both the "unbiased" and
"prefix-free decodable" properties? (For example, 23^21 ~
0.996*(2^95), so using 95 bits at a time to get 21 successive letters
would be close to the information-theoretic bound of log(23)/
log(2)=4.52 bits, but it doesn't work "online" and turn a stream of
bits into a stream of letters by using a prefix-free encoding).

Best way is the Huffmann codes. The general principles of which are
given in.

http://www.data-compression.com/theory.html

You take sequences of letters and encode wrt. frequency.


- Ian Parker

.

Relevant Pages

  • Re: Efficient unbiased prefix-free encodings
    ... that a stream of random bits will produce an unbiased stream of random ... An easy way to do this is to encode modulo ... letters is random and unbiased. ... Best way is the Huffmann codes. ...
    (sci.math.research)
  • Re: Post on Hols
    ... Are they on holiday this week ?? ... No but your letters are floating down some stream somewhere or at the bottom of some ditch. ...
    (uk.media.tv.misc)
  • Re: Can A Parking Fine Ever Lead to a CCJ?
    ... found a stream of letters regarding about unpaid parking fines going ... find warrants amongst all the love letters. ...
    (uk.legal)
  • Re: Can A Parking Fine Ever Lead to a CCJ?
    ... found a stream of letters regarding about unpaid parking fines going ... letters go to the point of Warrants for seizure of goods etc. ... is there a risk of getting a CCJ for these? ...
    (uk.legal)
  • Re: Efficient unbiased prefix-free encodings
    ... that a stream of random bits will produce an unbiased stream of random ... An easy way to do this is to encode modulo ... power of 2 and iterate. ...
    (sci.math.research)
Loading