Optimal Redundancy in Exact Channel Synthesis

2024/01/30 by Sharang M. Sriramu, Sriramu, Sharang M., Aaron B. Wagner +1 · 2 citations
Biochemistry, Genetics and Molecular Biology · Computer Science · #Cellular Automata and Applications #DNA and Biological Computing #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.2401.16707

openalex publication_date 2024/01/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the redundancy of the exact channel synthesis problem under an i.i.d. assumption. Existing results provide an upper bound on the unnormalized redundancy that is logarithmic in the block length. We show, via an improved scheme, that the logarithmic term can be halved for most channels and eliminated for all others. For full-support discrete memoryless channels, we show that this is the best possible.

Cited by

• Rejection-Sampled Linear Codes for Lossy Compression and Channel Simulation
• Communication Complexity of Exact Sampling under Rényi Information

Related

• Optimal coding for the deletion channel with small deletion probability
• Strong Converse and Second-Order Asymptotics of Channel Resolvability
• Quantization of Binary-Input Discrete Memoryless Channels
• Exact Channel Synthesis
• Single Letter Expression of Capacity for a Class of Channels with Memory