Introduction to Coding Theory

Jul 21, 2024

Introduction to Coding Theory

Lecturer: Adrish Banerjee, IIT Kanpur

Overview

  • 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

Communication Process

  • Three basic steps in communication:
    1. Encoding: Convert and efficiently represent a message.
    2. Transmission: Transmit the encoded message through a communication channel.
    3. 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."