Two-step encoding for finite sources

Abstract

Any finite information source is given a graph structure, in which two vertices are adjacent whenever the two corresponding source letters are distinguishable by the coder-decoder pair. Usual sources correspond, therefore, to complete graphs. If the associated graph is not complete, however, anvarepsilon-code for the source can be constructed in two steps: in the first, distinct codewords are given to distinguishable letters only; in the second step, a similar encoding is carried out for the complementary graph, in which distinguishable letters become indistinguishable and the converse. A particularly simple case shows up when nonadjacency is an equivalence relation among the vertices of the graph: each class of nondistinguishable letters can then be considered as a letter in a coarser source alphabet. The two-step procedure is then particularly intuitive. A problem arises when this procedure does not destroy optimality of the resultingvarepsilon-code; some partial results are given in this direction. The results obtained are largely based on some graph-theoretical ideas and tools.