Binary symmetric channels simplify simulating complex communication links
Finite BSC-Decomposition of Binary-Input Symmetric-Output Channels and Applications to Channel Simulation
Information Theory
Summary
Communicating over noisy channels is a common problem in digital communication. This paper shows how any binary channel that behaves the same way forwards and backwards can be closely represented by mixing a small number of simpler, well-understood channels called binary symmetric channels (BSCs). The authors also use this representation to design ways to simulate complex channels efficiently with only small extra communication needed. This might help improve methods for testing and designing communication systems where exact channel behavior is complicated.
What this means in practice
- •For telecommunication engineers: Construct precise simulated communication links using limited simple channel models to test network protocols.
- •For digital system designers: Design efficient coding schemes by approximating complex channels as a weighted combination of binary symmetric channels.
Authors
Jianguo Zhao, Cheuk Ting Li
Abstract
We propose a finite BSC-decomposition method for representing an arbitrary binary-input symmetric-output channel (BISOC) as a mixture of binary symmetric channels (BSCs) with at most $\ell+1$ distinct crossover probabilities. We show that the weighted average capacity of the component BSCs exceeds the capacity of the original BISOC by at most $(π^2\log e)/(48\ell^2)+O(\ell^{-5/2})$ bits, and the leading term is asymptotically optimal in the worst case. Based on the finite BSC-decomposition, we design a channel simulation scheme for arbitrary BISOCs. Combined with efficient channel simulation algorithms for BSCs, our scheme achieves a communication rate with $O((\log n / n)^{2/3})$ redundancy over the capacity for simulating $n$ copies of a BISOC.