期刊
IEEE TRANSACTIONS ON INFORMATION THEORY
卷 65, 期 7, 页码 4471-4485出版社
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TIT.2019.2896638
关键词
Source coding; algorithmic information theory; compression algorithms; Kolmogorov complexity; prefix-free codes
资金
- 1000 Talents Program for Young Scholars from the Chinese Government [D1101130]
- NSFC [11750110425]
- Institute of Software [ISCAS-2015-07]
- Royal Society University Research Fellowship
According to the Kolmogorov complexity, every finite binary string is compressible to a shortest code its information content from which it is effectively recoverable. We investigate the extent to which this holds for the infinite binary sequences (streams). We devise a new coding method that uniformly codes every stream X into an algorithmically random stream Y, in such a way that the first n bits of X are recoverable from the first 1(X vertical bar n) bits of Y, where I is any partial computable information content measure that is defined on all prefixes of X, and where X vertical bar n is the initial segment of X of length n. As a consequence, if g is any computable upper bound on the initial segment prefix-free complexity of X, then X is computable from an algorithmically random Y with oracle-use at most g. Alternatively (making no use of such a computable bound g), one can achieve an the oracle-use hounded above by K(X X vertical bar n)+ log n. This provides a strong analogue of Shannon's source coding theorem for the algorithmic information theory.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据