Finite-Length Analyses for Source and Channel Coding on Markov Chains

Abstract

We study finite-length bounds for source coding with side information for Markov sources and channel coding for channels with conditional Markovian additive noise. For this purpose, we propose two criteria for finite-length bounds. One is the asymptotic optimality and the other is the efficient computability of the bound. Then, we derive finite-length upper and lower bounds for coding length in both settings so that their computational complexity is efficient. To discuss the first criterion, we derive the large deviation bounds, the moderate deviation bounds, and second order bounds for these two topics, and show that these finite-length bounds achieves the asymptotic optimality in these senses. For this discussion, we introduce several kinds of information measure for transition matrices.

51 pages; 2 figures; presented at Allerton 2013 and ITA 2014; v2 fixed a gap in Remark 5; v3 changed the organization and presentation of the paper; Sections 2 and 3 in v2 were removed in v3, and extended version of them are in separate papers (cf. arXiv:1401.3801 and arXiv:1401.3814); in v4, results on random number generation are removed, and will appear in a separate paper

References in corpus (7)

• Error Exponent in Asymmetric Quantum Hypothesis Testing and Its Application to Classical-Quantum Channel coding
• Finite blocklength converse bounds for quantum channels
• Relating different quantum generalizations of the conditional Renyi entropy
• Finite-length Analysis on Tail probability for Markov Chain and Application to Simple Hypothesis Testing
• A uniform Berry--Esseen theorem on $M$-estimators for geometrically ergodic Markov chains
• Non-Asymptotic Analysis of Privacy Amplification via Renyi Entropy and Inf-Spectral Entropy
• The Saddlepoint Approximation: Unified Random Coding Asymptotics for Fixed and Varying Rates

Cited by in corpus (7)

• More Efficient Privacy Amplification with Less Random Seeds via Dual Universal Hash Function
• Uniform Random Number Generation from Markov Chains: Non-Asymptotic and Asymptotic Analyses
• Second Order Analysis for Joint Source-Channel Coding with Markovian Source
• Semi-Finite Length Analysis for Information Theoretic Tasks
• Asymptotically Secure Network Code for Active Attacks and its Application to Network Quantum Key Distribution
• Secrecy and Robustness for Active Attack in Secure Network Coding and its Application to Network Quantum Key Distribution
• Finite-Length Bounds for Joint Source-Channel Coding with Markovian Source and Additive Channel Noise to Achieve Large and Moderate Deviation Bounds