I seek a scheme to send data thru a biased channel like arithmetic coding. I suppose it costs more to send 1’s than 0’s.

If you have a stream of random bits that you can consume, and these bits are 50% ones, and independent of each other then several cute tricks can be used to employ them “economically”.

If routine b() produces the next random bit then

• if r() returns successive bits of the binary representation of a real number R between 0 and 1 then
```int cut(){int B = b(), R = r();
if(B && ~R) return 1;
if(R && ~B) return 0;
return cut();}
```
more obscurely:
`int cut(){int B = b(), R = !r(); return B && R || (B || R) && cut();}`
returns a 1 with probability R
• and thus routine
int third() {while(1){if(b()) return 0; if(b()) return 1;}}
or
int third() {return b() && (b() || third());}
or even
int third() {return b() && !third();}
returns 1 with probability 1/3.
This can be simply explained as the comparison of a randomly selected real B, uniformly between 0 and 1, and comparing its binary representation with the bits of R (or 1/3) until a difference is found. The expected number of random bits consumed is exactly 2.

Alas this is not good enough. I use 2 bits of entropy to produce −((1/3)log2(1/3) + (2/3)log2(2/3)) = .918296 bits of entropy conveyed by a bit in a 2:1 channel. The discrepancy indicates that this does not achieve the efficiency of arithmetic coding. I think there is an idea lurking here but I can’t find it just now. Its still a useful trick for when entropy is scarce.

The original notion of arithmetic coding is most cleanly expressed in Scheme. The message is a real number m between 0 and 1. Given a channel with cost of 1 is R and cost of 0 is 1−R, a channel coder is yielded by

```(define ((cc R) m) (let ((m m)) (lambda ()
(let ((v (- m R))(r (> m R))) (set! m
(if r (/ (- m R) (- 1 R)) (/ m R))) (if r 1 0)))))```
Invoking cc creates a procedure whose successive invocations produce the bits to be transmitted.
```(define (Do n p) (let Do ((n n)) (if (> n 0) (let ((u (- n 1))) (p u) (Do u)))))
(let ((w ((cc 1/3) 0.2540226510663))) (Do 60 (lambda (j) (write (w)))))```
yields: 011101100111001001110101001110111111111011101001101111111110