2022/05/12 by Yutaka Jitsumatsu, Jitsumatsu, Yutaka, Yasutada Oohama +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.2205.06027
openalex publication_date 2022/05/12 · openalex created_date 2022/05/22 · openalex updated_date 2026/07/28
The error exponent of a discrete memoryless channel is expressed in two forms. One is Gallager's expression with a positive slope parameter and the other is Csiszar and Korner's information-theoretic representation expressed using the mutual information and the relative entropy. They differ in appearance, and existing methods to prove their agreement are not elementary, as they require an evaluation of the KKT conditions that the optimal distribution must satisfy. Similarly, there are two types of expressions for the strong converse exponent. They are Arimoto's expression with a negative slope parameter and Dueck and Korner's information-theoretic expression. The purpose of this paper is to clarify the relation between two ways of representing exponents, i.e., representations using slope parameters and those using information-theoretic quantities, from the viewpoint of algorithms for computing exponents. Arimoto's algorithm is based on expression using slope parameters, while the authors' and Tridenski and Zamir's algorithms are based on Dueck and Korner's information-theoretic expression. An algorithm family that includes the above two algorithms as special cases was recently proposed. This paper clarifies that the convergence of Tridenski and Zamir's algorithm proves the match of Arimoto's and Dueck and Korner's exponents. We discuss another family of algorithms and, using the surrogate objective function used therein, prove that the two expressions of the error exponent coincide. Evaluation of the KKT condition is not needed in this proof. We then discuss the computation of the error and correct decoding probability exponents in lossy source coding. A new algorithm family for computing the source coding strong converse exponent is defined. The convergence of a member of the algorithm family implies the match of the two expressions of the strong converse exponent.