Forney's Code For BSCp
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 .
Read more about this topic: Binary Symmetric Channel
Famous quotes containing the word code:
“Many people will say to working mothers, in effect, “I don’t think you can have it all.” The phrase for “have it all” is code for “have your cake and eat it too.” What these people really mean is that achievement in the workplace has always come at a price—usually a significant personal price; conversely, women who stayed home with their children were seen as having sacrificed a great deal of their own ambition for their families.”
—Anne C. Weisberg (20th century)