Editing Binary symmetric channel (section)

== Codes ==
Very recently, a lot of work has been done and is also being done to design explicit error-correcting codes to achieve the capacities of several standard communication channels. The motivation behind designing such codes is to relate the rate of the code with the fraction of errors which it can correct.

The approach behind the design of codes which meet the channel capacities of <math>\text{BSC}</math> or the [[binary erasure channel]] <math>\text{BEC}</math> have been to correct a lesser number of errors with a high probability, and to achieve the highest possible rate. Shannon's theorem gives us the best rate which could be achieved over a <math>\text{BSC}_{p}</math>, but it does not give us an idea of any explicit codes which achieve that rate. In fact such codes are typically constructed to correct only a small fraction of errors with a high probability, but achieve a very good rate. The first such code was due to George D. Forney in 1966. The code is a concatenated code by concatenating two different kinds of codes.

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