2018/08/16 by Chou, Remi A., Bloch, Matthieu R., Yener, Aylin · 1 citation
#FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1808.05612
Consider a sequence Xn of length n emitted by a Discrete Memoryless Source (DMS) with unknown distribution pX. The objective is to construct a lossless source code that maps Xn to a sequence \widehatYm of length m that is indistinguishable, in terms of Kullback-Leibler divergence, from a sequence emitted by another DMS with known distribution pY. The main result is the existence of a coding scheme that performs this task with an optimal ratio m/n equal to H(X)/H(Y), the ratio of the Shannon entropies of the two distributions, as n goes to infinity. The coding scheme overcomes the challenges created by the lack of knowledge about pX by a type-based universal lossless source coding scheme that produces as output an almost uniformly distributed sequence, followed by another type-based coding scheme that jointly performs source resolvability and universal lossless source coding. The result recovers and extends previous results that either assume pX or pY uniform, or pX known. The price paid for these generalizations is the use of common randomness with vanishing rate, whose length scales as the logarithm of n. By allowing common randomness larger than the logarithm of n but still negligible compared to n, a constructive low-complexity encoding and decoding counterpart to the main result is also provided for binary sources by means of polar codes.