Homophonic Sequence Substitucion

  • Valdemar C. da Rocha Jr.
  • Hélio M. de Oliveira
Keywords: source coding, homophonic substitution, Markov sources, Huffman coding


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.

How to Cite
da Rocha Jr., V., & de Oliveira, H. (2017). Homophonic Sequence Substitucion. Journal of Communication and Information Systems, 13(1). https://doi.org/10.14209/jcis.1998.12
Regular Papers