Run-Length and Dictionary Coding: Information Theory Results (III)
This chapter focuses on run-length coding and dictionary-based coding techniques. It introduces Markov models as a type of dependent source model in contrast to memoryless source model. The Markov source discussed earlier represents a kind of dependence between source symbols in terms of the transition probability. Concretely, in determining the transition probability of a present source symbol given all the previous symbols, only the set of finitely many immediately preceding symbols matters. Many documents such as letters, forms, and drawings can be transmitted using facsimile machines over the general switched telephone network. In digital facsimile techniques, these documents are quantized into binary levels: black and white. 1-D Run-Length Coding technique, each scan line is encoded independently. Each scan line can be considered as a sequence of alternating, independent white and black runs. As an agreement between encoder and decoder, the first run in each scan line is assumed to be a white run.