文档介绍：ERROR-CORRECTING CODES
John Stone
9/21/04
Overview
Quick Definitions
Error Generation
Real World Example
Reed-Muller Code
Hadamard Matrices
Hamming Distance
Encoding Example
Decoding Example
Summary
References
Error-Correcting Codes
Quick Definitions
Error-Correcting Code
Code that can detect and fix its own errors
Error (Binary)
0 changed to 1
1 changed to 0
Example
1000**********
1010**********
Error-Correcting Codes
Error Generation
Noise
Other signals
Other devices
Distance
Reduced signal strength
Greater chance of interference
Examples
A space probe that collects and transmits data back to earth
Downloading from a FTP site in China
Error-Correcting Codes
Real World Example
Mariner series of Mars reconnaissance vehicles
32 possible gray levels
5 bits / pixel
(32, 5) Reed-Muller Code
32 bits / pixel
Error-Correcting Codes
Reed-Muller Code
Code produced that contains extra information so that a limited amount of errors can be corrected if needed
Uses Hadamard matrices for encoding and decoding error-correcting codes.
Error-Correcting Codes
Hadamard Matrices
Each row is a possible code
Each matrix has a Hamming distance
Error-Correcting Codes
Hamming Distance
The number of places that two binary words differ from one another
Can fix (d – 1) / 2⌡errors
Error-Correcting Codes
Encoding Example
Hamming Distance = 4
(4 – 1) / 2⌡= 1 (fixable error)
Example:
110 01001101
Error-Correcting Codes
Decoding Example
Example:
0101 1101 ?
Result:
0101 1101 0100 1101 110
Error-Correcting Codes