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:
“Hollywood keeps before its child audiences a string of glorified young heroes, everyone of whom is an unhesitating and violent Anarchist. His one answer to everything that annoys him or disparages his country or his parents or his young lady or his personal code of manly conduct is to give the offender a “sock” in the jaw.... My observation leads me to believe that it is not the virtuous people who are good at socking jaws.”
—George Bernard Shaw (1856–1950)