Usage of error-correcting codes for error detection and correction
Reference books for the course:
"Error Control Coding" by Lin and Costello (2nd edition)
"Block Codes" by Sloane and McWilliams
"Algebraic Codes for Data Transmission" by Blayhood
"Error Control Coding" by K. Moon
"Fundamentals of Error Control Codes" by Huffman and Pless
Communication Process
Three basic steps in communication:
Encoding: Convert and efficiently represent a message.
Transmission: Transmit the encoded message through a communication channel.
Decoding: The receiver decodes the message to retrieve the original information.
Information theory defines fundamental limits on compression and transmission rates.
Channel Models
Binary Symmetric Channel:
Binary inputs (0s and 1s) and binary outputs (0s and 1s)
With probability 1 - ε, transmitted bits are correctly received.
ε represents crossover probability of error.
Binary Erasure Channel:
Binary inputs (0s and 1s)
Outputs are either correctly received bits or erased bits (denoted by δ)
With probability 1 - δ, bits are correctly received; with probability δ, bits are erased.
Shannon's Theorem
Channel capacity: Maximum information that can be conveyed from input to output of a channel.
Asserts existence of channel coding schemes achieving very low error probability if transmission rate is below channel capacity.
Design of such codes not specified by Shannon; error control coding theory aims to create codes achieving low error rates close to channel capacity.
Error-Correcting Codes
Designed by adding redundant bits (parity bits) to original message bits (information bits).
Used for both error detection and correction.
Applications: Digital communication, storage systems, etc.
Example: Repetition Code
Rate: Ratio of number of information bits to number of coded bits.
Rate 1/2 Repetition Code:
Encodes 0 as 00 and 1 as 11.
Can detect single errors but cannot correct them.
Rate 1/3 Repetition Code:
Encodes 0 as 000 and 1 as 111.
Can detect and correct single errors, detect double errors but cannot correct double errors.
Summary
Rate 1/2 code can detect single error but cannot correct; cannot detect double errors.
Rate 1/3 code can detect and correct single errors, detect double errors; cannot correct double errors.
Error detecting and correcting capabilities depend on the distance properties of the codes.
Quotation
Solomon Golomb: "A message of content and clarity has got to be quite a rarity; to combat the terror of serious error, use bits of appropriate parity."