Background
The field of channel coding is concerned with sending a stream of data at the highest possible rate over a given communications channel, and then decoding the original data reliably at the receiver, using encoding and decoding algorithms that are feasible to implement in a given technology.
Shannon's channel coding theorem shows that over many common channels there exist channel coding schemes that are able to transmit data reliably at all rates less than a certain threshold, called the channel capacity of the given channel. In fact, the probability of decoding error can be made to decrease exponentially as the block length of the coding scheme goes to infinity. However, the complexity of a naive optimum decoding scheme that simply computes the likelihood of every possible transmitted codeword increases exponentially with, so such an optimum decoder rapidly becomes infeasible.
In his doctoral thesis, Dave Forney showed that concatenated codes could be used to achieve exponentially decreasing error probabilities at all data rates less than capacity, with decoding complexity that increases only polynomially with the code block length.
Read more about this topic: Concatenated Error Correction Code
Famous quotes containing the word background:
“Silence is the universal refuge, the sequel to all dull discourses and all foolish acts, a balm to our every chagrin, as welcome after satiety as after disappointment; that background which the painter may not daub, be he master or bungler, and which, however awkward a figure we may have made in the foreground, remains ever our inviolable asylum, where no indignity can assail, no personality can disturb us.”
—Henry David Thoreau (1817–1862)
“I had many problems in my conduct of the office being contrasted with President Kennedy’s conduct in the office, with my manner of dealing with things and his manner, with my accent and his accent, with my background and his background. He was a great public hero, and anything I did that someone didn’t approve of, they would always feel that President Kennedy wouldn’t have done that.”
—Lyndon Baines Johnson (1908–1973)
“Pilate with his question “What is truth?” is gladly trotted out these days as an advocate of Christ, so as to arouse the suspicion that everything known and knowable is an illusion and to erect the cross upon that gruesome background of the impossibility of knowledge.”
—Friedrich Nietzsche (1844–1900)