6.897 Algorithmic Introduction to Coding Theory October 9, 2002Lecture 10Lecturer: Madhu Sudan Scribe: Fu Liu1 Overview• Algorithmic issues• Algorithm for decoding Reed-Solomon codes2 Algorithmic tasksBroadly, it’s relatively easier to give an encoding function and construction of a code than to find adecoding algorithm.2.1 EncodingIf given a family of encoding functions {En|En: {0, 1}k→ {0, 1}n}n, we would like to ask that howefficiently they can be computed.It turns out that it is pretty hard when code is specified as part of the input. Fortunately, it works wellfor linear codes in polytime. Also, if the encoding problem is given as ”given an circuit E, for the ithmember of a family of a code, and a message m, compute its encoding.” The this problem is trivial tosolve in linear time in the size of E.2.2 Construction of Code• Code C ⊆ {0, 1}n• |C| = 2k• Encoding circuit E : {0, 1}k→ C.Circuit for E maybe specifictation of C.•Decide(x) =1, if x ∈ C0, otherwiseCircuit for Decide is specification of C.2.3 DecodingNow we come to the hard part. The problem can be stated informally as ”if message c is sent, howcan we compute c from the received message r? Also, we we consider the specification of the encodingfunction E, when/how is it specified” and ”how much time it takes to design the decoding algorithm”...Unfortunately, these problems are so hard that we do not know any efficient algorithm. So we will haveto focus on some specific codes.10-12.3.1 Popular definitions in decoding1. Maximum Likelihood Decoding (MLD)If we are given the channel, the code C, and a received vector r ∈ Γn, find a codeword c ∈ C, whichmaximizes Prchannel[r seen | c sent].2. Nearest Codeword Problem (NCP)Given channel and the code C, and received vector r ∈ Σn, find a codeword c ∈ C, whichminimizes ∆(c, r).If we look back the MLD problem and give the channel as a q-ary symmetric channel, i.e. ifΣ = {x1, x2, . . . , xq}, for ∀i : 1 ≤ i ≤ q, the probability of xiseen when xisent is 1 − p, and theprobablity of xj(j 6= i) seen when xisent isp1−q,where 1 − p >1qand |Σ| = q. Then this problemis just a NCP. This is a connection between MLD and NCP.3. Soft-decision Decoding ProblemGiven the channel, the code C and a Σ by n matrix M, whose entries are nonnegative reals, find ac ∈ C, thatminimizesΣni=1Mci,iIf M is given as a 0/1 matrix with one 1 in each column. Then it is the NCP problem.If Assume the given channel is i.i.d.. ThenPr[r seen | c sent]= Πni=1Pr[riseen | cisent]= EXP(Πni=1−log Pr[riseen|cisent]| {z }Mci,i)By the equation above, soft-decision decoding solves MLD for i.i.d. channel.2.3.2 Reasonable decoding problemsFor a decoding problem, we should consider both the number of errors we’re trying to correct and numberof errors the code designed to handle. Let’s look at the following three questions:1. Unambiguous/unique decoding Given a code C with minimum distance d, and r ∈ Σn, find code-word c such that ∆(r, c) <d2if it exists. Sometimes it is also called Bounded Distance Decoding.2. Relatively Near Codeword (RNC) This is a parameterize problem with parameter γ > 0. Given acode C with minimum distance d, and r ∈ Σn, e < γd, find c ∈ C, such that ∆(r, c) ≤ e.Note when pick γ =12, RNC is Unambiguous Decoding Problem.When pick γ = ∞, RNC becomes NCP.And the problem is reasonable up to when γ < 1.10-23. List-decoding problem The definition of this problem is similar to RNC except that here we wanta list of all codewords c such that ∆(r, c) < γd.Therefore, Unambiguous decoding is List-decoding also, for γ =12.For each γ, RNC reduces to List-decoding Problem. And the List-decoding can be very hard ifthe list size is (potentialy) super polynomial. Hence, we should only attempt to solve this up tothe list-decoding radius of a code, which is the radius of a ball with guarantee that the number ofcodewords in the ball is polynomial.2.3.3 Easy problems for linear codesFor a linear code, because a generator matrix is given, the following three problem is ”easy”. Here”easy” means that it takes poly time.• Encoding Clearly, code can be easily generated by the generator matrix.• Error-detection We can get the parity matrix from the given generator matrix, and use it to detectwhether errors occur.• Erasure correction– Erasure-decoding problem: Given an k by n generator matrix G, the code C generated by Gand vector r ⊆ (Σ ∪ {?})n, find c ∈ C, such that ci= ri, for i : 1 ≤ i ≤ n with ri 6=?.– Decoding Algorithm: If there’re s symbols of r are ?0s, i.e. erased, let r0be a vector obtainedby removing the s?0s from r. And let G0obtained by removing the corresponding columns.Then solving the linear system mG0= r0will give the solution c = mG.If mG0= r0has no solution, they our problem does not have solution; if it has one solution,our problem have one solution; if it has more than one solution, they our problem has asolution space in the form of Ax + b.– Another fact about the erasure-decoding problem is that when the number of erasures, s, issmaller than d, the minimum distance of the code, then the solution is unique.2.3.4 Syndrome Decoding• Definition: Given a linear code C with parity check matrix H and e ∈ Fnq, e · H is the syndromeof e.• Note that if given a vector r = c + e, where c ∈ C and e is the error, the r · H = e · H depends onlyon the error e but not on the codeword c.• Syndrome decoding can be interpreted in two ways:– Given e · H, compute e.– Build up a table of map e · H → e, and look up the table by index e · H to compute e. Thisis a brute-force algorithm.10-33 Unambiguous Decoding of Reed-Solomon Codes3.1 Problem statementIf given n distinct elements α1, α2, . . . , αn∈ Fq, r1, r2, . . . , rn∈ Fqand a parameter k, find a polynomialp ∈ Fq[x] of degree no more than k, such that p(αi) = rifor many values| {z }>n+k2of i.3.2 Convoluted historyAt first glance, this problem is not trivial. Let’s look at the history of this problem first.• In 1958, BC + H discovered binary BCH¿• Peterson 60’ gave polytime decoding algorithm for binary BCH in 1960.• Reed-Solomon found RS code, but did not notice the connection between it and BCH.• In 1963, Gorenstein-Zierler discovered q-ary BCH codes and noticed that RS codes are specialcases of q-ary BCH codes and that Peterson’s algorithm generalizes to q-ary BCH