Definition
Coding Theory
Coding Theory refers to the theory of error-correcting and -detecting codes.
Goals
- Data Compression: Reduction of data volume
- Coding Theory: Protection against transmission errors (through increased redundancy)
- Cryptography: Protection against unwanted receivers and transmitters
Redundancy
Redundancy
Redundancy means including information that can be removed without losing the original data.
Multilevel Coding
- Source Coding: Original data is encoded using binary numbers (e.g. compression or encryption)
- Channel Coding: Re-coding of the binary data (e.g. compression or encryption)
- Line Coding: Re-coding of data to optimise it for the transmission medium
Error Detection and Correction
Errors always occur when information is transmitted, e.g. when calling someone on the phone. To reduce errors, redundancies are introduced.
Types of Transmission Errors
There are two major types of transmission errors:
- Single Bit Errors: A single bit or multiple unrelated bits are disturbed.
- Bursts: Multiple consecutive bits are disturbed.
Shannon Information
Relative Frequency
The relative frequency of a symbol
where
Information Content
The information content is given by:
where
Entropy (Average Information Content)
Let
Example: Compute the entropy of the following alphabet:
Then
Average Word Length
Let
Redundancy
The redundancy is the difference between average word length and entropy (average information content):
To get the dimensionless relative redundancy
Types of Codes
Block Codes
Block code means that all codes have equal length, e.g.:
0101010
1000101
1101111
0000000
Linear Codes
Linear code means that you can choose a pair of two codes and their XOR result is again a valid code, e.g.:
0101010
1000101
1101111
0000000
Cyclical Codes
Cyclical code means that you can choose one possible code and shift it by 1 (to left or right) and the result is again a valid code, e.g.:
0101010
1010100
0010101