Editing Binary symmetric channel (section)

=== Forney's code ===

Forney constructed a [[concatenated code]] <math>C^{*} = C_\text{out} \circ C_\text{in}</math> to achieve the capacity of the noisy-channel coding theorem for <math>\text{BSC}_p</math>. In his code,

* The outer code <math>C_\text{out}</math> is a code of block length <math>N</math> and rate <math>1-\frac{\epsilon}{2}</math> over the field <math>F_{2^k}</math>, and <math>k = O(\log N)</math>. Additionally, we have a [[Code|decoding]] algorithm <math>D_\text{out}</math> for <math>C_\text{out}</math> which can correct up to <math>\gamma</math> fraction of worst case errors and runs in <math>t_\text{out}(N)</math> time.
* The inner code <math>C_\text{in}</math> is a code of block length <math>n</math>, dimension <math>k</math>, and a rate of <math>1 - H(p) - \frac{\epsilon}{2}</math>. Additionally, we have a decoding algorithm <math>D_\text{in}</math> for <math>C_\text{in}</math> with a [[Code|decoding]] error probability of at most <math>\frac{\gamma}{2}</math> over <math>\text{BSC}_p</math> and runs in <math>t_\text{in}(N)</math> time. 
 
For the outer code <math>C_\text{out}</math>, a Reed-Solomon code would have been the first code to have come in mind. However, we would see that the construction of such a code cannot be done in [[Time complexity|polynomial time]]. This is why a [[binary linear code]] is used for <math>C_\text{out}</math>.

For the inner code <math>C_\text{in}</math> we find a [[linear code]] by exhaustively searching from the [[linear code]]  of block length <math>n</math> and dimension <math>k</math>, whose rate meets the capacity of <math>\text{BSC}_p</math>, by the noisy-channel coding theorem.

The rate <math>R(C^{*}) = R(C_\text{in}) \times R(C_\text{out}) = (1-\frac{\epsilon}{2}) ( 1 - H(p) - \frac{\epsilon}{2} ) \geq 1 - H(p)-\epsilon</math> which almost meets the <math>\text{BSC}_p</math> capacity. We further note that the encoding and decoding of  <math>C^{*}</math> can be done in polynomial time with respect to <math>N</math>. As a matter of fact,  encoding <math>C^{*}</math> takes time <math>O(N^{2})+O(Nk^{2}) = O(N^{2})</math>. Further, the decoding algorithm described takes time <math>Nt_\text{in}(k) + t_\text{out}(N) = N^{O(1)} </math> as long as <math>t_\text{out}(N) = N^{O(1)}</math>; and <math>t_\text{in}(k) = 2^{O(k)}</math>.

==== 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>