Finite BSC-Decomposition of Binary-Input Symmetric-Output Channels and Applications to Channel Simulation

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 $\mathrm{\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 $({\pi }^2\log e)\mathrm{/}(48{\mathrm{\ell }}^2)+O({\mathrm{\ell }}^{-5\mathrm{/}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\mathrm{/}n{)}^{2\mathrm{/}3})$ redundancy over the capacity for simulating $n$ copies of a BISOC.