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.