Transcription of Introduction to Coding Theory Lecture Notes - BIU
1 Introduction to Coding TheoryLecture Notes Yehuda LindellDepartment of Computer ScienceBar-Ilan University, IsraelJanuary 25, 2010 AbstractThese are Lecture Notes for an advanced undergraduate (and beginning graduate) course in CodingTheory in the Computer Science Department at Bar-Ilan University. These Notes contain the technicalmaterial covered but do not include much of the motivation and discussion that is given in the is therefore not intended for self study, and is not a replacement for what we cover in class.
2 This is afirst draft of the Notes and they may therefore contain errors. These Lecture Notes are based on Notes taken by Alon Levy in 2008. We thank Alon for his Basic Definitions.. A Probabilistic Model.. 32 Linear Basic Definitions.. Code Weight and Code Distance.. Generator and Parity-Check Matrices.. Equivalence of Codes.. Encoding Messages in Linear Codes.. Decoding Linear Codes.. Summary.. 123 The Main Question of Coding Theory .. The Sphere-Covering Lower Bound.
3 The Hamming (Sphere Packing) Upper Bound.. Perfect Codes.. The Binary Hamming Code.. Decoding the Binary Hamming Code.. Extended Codes.. Golay Codes.. Summary - Perfect Codes.. The Singleton Bound and MDS Codes.. The Reed-Solomon Code.. A Digression Coding Theory and Communication Complexity.. The Gilbert-Varshamov Bound.. The Plotkin Bound.. The Hadamard Code.. The Walsh-Hadamard Code.. 274 Asymptotic Bounds and Shannon s Background: Information/Entropy.
4 Asymptotic Bounds on Codes.. Shannon s Theorem.. Channel Capacity (Shannon s Converse).. 385 Constructing Codes from Other General Rules for Construction.. The Reed-Muller Code.. 406 Generalized Reed-Solomon Codes (GRS) Definition.. Polynomial representation of GRS.. Decoding GRS Codes.. Step 1: Computing the Syndrome.. Step 2 The Key Equation of GRS Decoding.. Step III - Solving the Key Equations.. The Peterson-Gorenstein-Zierler GRS Decoding Algorithm.. 50ii7 Asymptotically Good Background.
5 Concatenation of Codes.. The Forney Code.. Efficient Decoding of the Forney Code.. A Probabilistic Decoding Algorithm.. A Deterministic Decoding Algorithn.. 568 Local Locally decoding Hadamard codes.. 579 List Decoding5910 Hard Problems in Coding The Nearest Codeword Problem and NP-Completeness.. Hardness of Approximation.. 6211 CIRC: Error Correction for the CD-ROM67iiiiv1 IntroductionThe basic problem of Coding Theory is that of communication over an unreliable channel that results in errorsin the transmitted message.
6 It is worthwhile noting that all communication channels have errors, and thuscodes are widely used. In fact, they are not just used for network communication, USB channels, satellitecommunication and so on, but also in disks and other physical media which are also prone to addition to their practical application, Coding Theory has many applications in the Theory of computerscience. As such it is a topic that is of interest to both practitionersand check:Consider the following code: For anyx=x1, .. , xndefineC(x) = ni=1xi.
7 This codecan detect a single error because any single change will result in the parity check bit being code cannot detect two errors because in such a case one codeword will be mapped to code:Letx=x1, .. , xnbe a message and letrbe the number of errors that we wish tocorrect. Then, defineC(x) =xkxk kx, where the number of times thatxis written in the outputis 2r+ 1. Decoding works by taking then-bit stringxthat appears a majority of the time. Note thatthis code correctsrerrors because anyrerrors can change at mostrof thexvalues, and thus ther+1values remain untouched.
8 Thus the originalxvalue is the repetition code demonstrates that the Coding problem can be solved in principal. However, theproblem with this code is that it is extremely main questions of Coding Theory :1. Construct codes that can correct a maximal number of errorswhile using a minimal amount of redun-dancy2. Construct codes (as above) with efficient encoding and Basic DefinitionsWe now proceed to the basic definitions of {a1, .. , aq}be analphabet; we call theaivaluessymbols. Ablock codeCof lengthnoverAis a subset ofAn.
9 A vectorc Cis called acodeword. The number of elements inC, denoted|C|,is called thesizeof the code. A code of lengthnand sizeMis called an(n, M) code overA={0,1}is called abinary codeand a code overA={0,1,2}is called aternary will almost exclusively talk about sending a codewordc and then finding the codewordcthat was originally sent given a vectorxobtained by introducing errors intoc. This may seem strange atfirst since we ignore the problem of mapping a messageminto a codewordcand then findingmagain fromc.
10 As we will see later, this is typically not a problem (especially for linear codes) and thus the mapping oforiginal messages to codewords and back is not a rate of a code is a measure of its efficiency. Formally:Definition an(n, M)-code over an alphabet of sizeq. Then, therateofCis defined byrate(C) = that it is possible to specifyMmessages using logqMsymbols when there is no , the longer thatnis, the more wasteful the code (in principal, logqMsymbols suffice and then logqMadditional symbols are redundancy).
