## Arithmetic channel coding

Arithmetic coding is a source coding algorithm which encodes the output
of any discrete stationary source into a sequence of independent and uniformly
distributed random variables. The code is specified by the probabilities
and cumulative probabilities of the source. By shrinking the source probabilities
by a given factor, redundancy is added into the code sequence with only
minor deviations from the code statistics. This enables us to use arithmetic
coding for noisy channels. Though this may seem like an unusual channel
coding algorithm, we show that every block code and every convolutional
code can also be implemented by an arithmetic encoder. Beyond these special
cases, the algorithm can be used to generate code sequences which cannot
be generated using a block or convolutional encoder.

The decoder used in arithmetic source coding is based on the noiseless
assumption and it cannot be used to decode the output of a noisy channel.
However, sequential decoding can be used. We develop a MAP metric for arithmetic
channel coding similar to Fano's metric for sequential decoding of convolutional
codes. Finally, we show simulation results for a simple arithmetic encoder
of rate 1/2 which is neither a block nor a convolutional code. The encoder
is used to encode a binary symmetric source to be transmitted over a binary
symmetric channel. The results shown are promising, though they suffer
from the known limitations of sequential decoding. Both the encoder and
the metric developed apply to any discrete stationary source. Therefore,
they are inherently capable of joint source-channel coding.