Finite BSC-Decomposition of Binary-Input Symmetric-Output Channels and Applications to Channel Simulation
In the authors' words
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 distinct crossover probabilities. We show that the weighted average capacity of the component BSCs exceeds the capacity of the original BISOC by at most 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 redundancy over the capacity for simulating copies of a BISOC.
Appeared: Tuesday, October 20. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 15pages,5 figures