Some simple and elegant models for evaluating error correcting codes:
Binary Symmetric Channel.
Binary Erasure Channel.
A channel with which has both bit flips and erasures, at (possibly different) specified probabilities.
The following one doesn't have a name, as far as I know: a channel with an adversary who knows what error correcting code you are using, and always induces worst case errors (within the specified error rates). This is probably equivalent to characterizing the worst case performance of a given error correcting code. I suspect LDPC and turbo codes don't do well against an adversary, in contrast to codes based on sphere packing or Hamming distances.
A channel whose alphabet is larger than binary.
12 possibilities total.
For each of the possibilities, what is the current state of the art? I haven't found a reference which organizes things according to these possibilities. I suspect some might be practically solved while others are open research topics with likely considerable room for improvement.
Practically solved means having low-degree polynomial running time, and operating close enough to the information-theoretic maximum efficiency for that channel.
https://en.wikipedia.org/wiki/Category:Capacity-approaching_codes
What is the information-theoretic capacity of a channel with an adversary?
No comments :
Post a Comment