Finite-length analyses for source and channel coding on markov chains

Hayashi，Masahito1,2,3,4; Watanabe，Shun5

2020-04-01

10.3390/E22040460

Entropy   影响因子和分区

1099-4300

1099-4300

We derive finite-length bounds for two problems with Markov chains: source coding with side-information where the source and side-information are a joint Markov chain and channel coding for channels with Markovian conditional additive noise. For this purpose, we point out two important aspects of finite-length analysis that must be argued when finite-length bounds are proposed. The first is the asymptotic tightness, and the other is the efficient computability of the bound. Then, we derive finite-length upper and lower bounds for the coding length in both settings such that their computational complexity is low. We argue the first of the above-mentioned aspects by deriving the large deviation bounds, the moderate deviation bounds, and second-order bounds for these two topics and show that these finite-length bounds achieve the asymptotic optimality in these senses. Several kinds of information measures for transition matrices are introduced for the purpose of this discussion.

Channel coding Finite-length analysis Markov chain Source coding

SCI

英语

第一 ; 通讯

Japan Society of the Promotion of Science (JSPS)[16H06091][23246071][17H01280][16KT0017]

Physics

Physics, Multidisciplinary

WOS:000537222600090

MDPI

2-s2.0-85084677039

Scopus

1.Shenzhen Institute for Quantum Science and Engineering,Southern University of Science and Technology,Shenzhen,518055,China
2.Graduate School of Mathematics,Nagoya University,Nagoya,464-8602,Japan
3.Center for Quantum Computing,Peng Cheng Laboratory,Shenzhen,518000,China
4.Centre for Quantum Technologies,National University of Singapore,Singapore,3 Science Drive 2,117542,Singapore
5.Department of Computer and Information Sciences,Tokyo University of Agriculture and Technology,Koganei-shi,Tokyo,184-8588,Japan

Hayashi，Masahito,Watanabe，Shun. Finite-length analyses for source and channel coding on markov chains[J]. Entropy,2020,22(4).

Hayashi，Masahito,&Watanabe，Shun.(2020).Finite-length analyses for source and channel coding on markov chains.Entropy,22(4).

Hayashi，Masahito,et al."Finite-length analyses for source and channel coding on markov chains".Entropy 22.4(2020).