Block Codes, Weight, and Distance#
ECFF
1992
Pretzel, Oliver. Error-Correcting Codes and Finite Fields. Oxford University Press Applied Mathematics and Computing Science Series.
How to assess the performance of a code over a given channel? The basis for this assessment is the Hamming distance which is the number of places in which two words differ.
The worst-case error-processing performance of a code is determined by the minimum distance between code words. Then some elementary probability theory can be used to assess the performance of a code.
Block Codes#
+--------------------------+
| |
| Random error generator |
| |
+--------------------------+
| +-----------+
| | | Message
+----------------+ +-----------+ | +-------------------+---------------->| Decoder |----------->
Message | | Message | | Signal v Distorted signal | | code words u' | | words x'
---------->| Preprocessor |---------->| Encoder |--------------->|+|-------------------->| Error processor | +-----------+
string | | words x | | code words u received words v | |
+----------------+ +-----------+ +-------------------+----------------------------------------->
v + error signal
Definition: block#
Definition: block code#
Definition: encoder#
Definition: decoder#
In a binary symmetric channel the error-processing capabilities of the coding system do not depend on the encoder and decoder but only on the set of code words because these are all that the channel sees; the choice of encoder and decoder is thus only a matter of practical convenience.
Most of coding theory is concerned with (1) the construction of codes \(C\) and (2) efficient error processors.
Definition: received word#
Definition: error of weight \(k\)#
Definition: Hamming distance and weight#
Definition: distance function#
Definition: error processor (and error detector)#
Definition: minimum distance of a code#
Claim: condition for error detection#
Claim: condition for error correction#
The minimum distance \(d(C)\) of code \(C\) determines the worst-case error-detecting and -correcting
Shannon’s Theorem#
the theoretical optimum for average coding performance