Homophonic Sequence Substitucion - da Rocha Jr., Valdemar C.; de Oliveira, Hélio M. (Journal of Communication and Information Systems, 2017)
Homophonic sequence substitution is the name given in this paper to the technique which consists of substituting one-to-one a given finite (or semi-infinite) sequence of symbols by another finite (or semi-infinite) sequence over the same alphabet but having a higher entropy rate. The output sequence of a given discrete stationary and ergodic source is encoded with a binary lossless source code C. A concatenation of codewords of C is then conveniently parsed and reencoded with a binary lossless source code. By iterating the latter step a number of times, it is proved that the entropy rate of the binary sequence at the output of the last encoder approaches the value 1 asymptotically, therefore performing optimum homophonic sequence substitution. The remaining redundancy, after k consecutive encodings, is 1- H_k(S) bits per binary digit, where H_k(S) is the entropy rate of the binary sequence resulting after the k-th encoding. A Markov source model is presented to describe the binary encoded sequences and to compute their entropy rate.