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:
“Wise Draco comes, deep in the midnight roll
Of black artillery; he comes, though late;
In code corroborating Calvin’s creed
And cynic tyrannies of honest kings;
He comes, nor parlies; and the Town, redeemed,
Gives thanks devout; nor, being thankful, heeds
The grimy slur on the Republic’s faith implied,
Which holds that Man is naturally good,
And—more—is Nature’s Roman, never to be
scourged.”
—Herman Melville (1819–1891)