2025/06/10 by Jianguo Zhao, Li, Cheuk Ting, Cheuk Ting Li +1
Computer Science · Engineering · #Advanced Wireless Communication Techniques #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Wireless Communication Security Techniques
paper · pdf · doi:10.48550/arxiv.2506.09239
openalex publication_date 2025/06/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We show that linear codes combined with rejection sampling can yield a capacity-achieving scheme for simulating additive exchangeable noise channels. Specifically, our scheme achieves an amount of communication within log e + 1 bits from the excess functional information lower bound. Hence, it can be used in lossy source coding to achieve the rate-distortion function. We discuss practical implementations based on BCH codes and polar codes. For the simulation of binary symmetric channels, the BCH-based construction with a blocklength of n = 63 attains a rate comparable to the PolarSim with n = 4096, while significantly reducing the latency. The polar-based construction asymptotically achieves the channel capacity with polynomial average complexity. Furthermore, using the idea from greedy rejection sampling, we propose an algorithm to construct capacity-achieving schemes based on any linear codes. Experiments reveal that our construction can outperform conventional covering codes for lossy source coding with Hamming distortion for a certain range of distortion levels, and performs well even when the blocklength is small (e.g., n = 24).