2010 | OriginalPaper | Buchkapitel
What Can Cryptography Do for Coding Theory?
verfasst von : Adam Smith
Erschienen in: Information Theoretic Security
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
By Shannon’s seminal work, we know that for the binary symmetric channel
bsc
p
which flips each transmitted bit independently with probability
p
, there exist binary codes of rate 1 −
H
(
p
) −
ε
that enable reliable information transmission with exponentially small probability of miscommunication. Here
ε
> 0 is arbitrary and
H
(·) is the binary entropy function. The quantity 1 −
H
(
p
) is called the (Shannon) capacity of the
bsc
p
channel. But what if the errors are
adversarial
and not randomly distributed? For the adversarial channel
Adv
p
where the channel can corrupt up to a fraction
p
of symbols in an arbitrary manner
after
seeing the codeword, it is known that for error-free communication to be possible, the rate has to be much smaller than the Shannon capacity 1 −
H
(
p
).