Editing Binary symmetric channel (section)

==== Decoding error probability ====

A natural decoding algorithm for <math>C^{*}</math> is to:

* Assume <math>y_{i}^{\prime} = D_\text{in}(y_i), \quad i \in (0, N)</math> 
* Execute <math>D_\text{out}</math> on <math>y^{\prime} = (y_1^{\prime} \ldots y_N^{\prime})</math>

Note that each block of code for <math>C_\text{in}</math> is considered a symbol for <math>C_\text{out}</math>. Now since the probability of error at any index <math>i</math> for <math>D_\text{in}</math> is at most <math>\tfrac{\gamma}{2}</math> and the errors in <math>\text{BSC}_p</math> are independent, the expected number of errors for <math>D_\text{in}</math> is at most <math>\tfrac{\gamma N}{2}</math> by linearity of expectation. Now applying [[Chernoff bound]], we have bound error probability of more than <math>\gamma N</math> errors occurring to be <math>e^\frac{-\gamma N}{6}</math>. Since the outer code <math>C_\text{out}</math> can correct at most <math>\gamma N</math> errors, this is the [[Code|decoding]] error probability of <math>C^{*}</math>. This when expressed in asymptotic terms, gives us an error probability of <math>2^{-\Omega(\gamma N)}</math>. Thus the achieved decoding error probability of <math>C^{*}</math>  is exponentially small as the noisy-channel coding theorem.

We have given a general technique to construct <math>C^{*}</math>. For more detailed descriptions on <math>C_\text{in}</math> and <math>C_\text{out}</math> please read the following references. Recently a few other codes have also been constructed for achieving the capacities. [[LDPC]] codes have been considered for this purpose for their faster decoding time.<ref>Richardson and Urbanke</ref>