Binary Symmetric Channel - Forney's Code For BSC_p

Forney's Code For BSC_p

Forney constructed a concatenated code to achieve the capacity of Theorem 1 for . In his code,

• The outer code is a code of block length and rate over the field, and . Additionally, we have a decoding algorithm for which can correct up to fraction of worst case errors and runs in time.
• The inner code is a code of block length, dimension, and a rate of . Additionally, we have a decoding algorithm for with a decoding error probability of at most over and runs in time.

For the outer code, 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 polynomial time. This is why a binary linear code is used for .

For the inner code we find a linear code by exhaustively searching from the linear code of block length and dimension, whose rate meets the capacity of, by Theorem 1.

The rate which almost meets the capacity. We further note that the encoding and decoding of can be done in polynomial time with respect to . As a matter of fact, encoding takes time . Further, the decoding algorithm described takes time as long as ; and .