Jul 21, 2024

- Introduction to coding theory
- 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

- 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.

**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.

- 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.

- 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.

**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.

- 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.

- 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."