Notes 1: Introduction, linear codes

← Back to document page

Introduction to Coding TheoryCMU: Spring 2010Notes 1: Introduction, linear codesJanuary 2010Lecturer: Venkatesan GuruswamiScribe: Venkatesan GuruswamiThe theory of error-correcting codes and more broadly, information theory, originated in ClaudeShannon s monumental work A mathematical theory of communication, published over 60 yearsago in 1948. Shannon s work gave a precise measure of the information content in the output of arandom source in terms of itsentropy. Thenoiseless coding theoremor the source coding theoreminformally states random variables each with entropyH(X) can be compressed inton(H(X) + ) bits with negligible probability of information loss, and conversely compression inton(H(X) ) bits would entail almost certain information directly relevant to this course is Shannon snoisy coding theoremwhich considered com-munication of a message (say consisting ofkbits that are output by a source coder) on a noisycommunication channel whose behavior is given by a stochastic channel law.

The fractional Hamming distance or relative distance between x;y2 n is given by (x;y) = ( x;y) n. It is trivial to check that the Hamming distance de nes a metric on n. De nition 2 (Hamming weight) The Hamming weight of a string xover alphabet is de ned as the number of non-zero symbols in the string. More formally, the Hamming weight of a string

  Distance