Decoding Reed-Muller codes over product sets

1 Error-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesDecoding Reed-Muller codes over product setsJohn Kim, Swastik KoppartyRutgers UniversityMay 30, 2016 John Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesOverview1 Error-correcting codesMotivation2 Polynomial-based codesReed-Solomon codesReed- muller codes3 Efficient Decoding of Reed-Muller codesPolynomial time decoderNear-linear time decoderJohn Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesMotivationError-correcting codesGoal:Send a message Don t shoot the boy.

2 Through a :Don t shoot the Don t shoot the fix:boyencode bbboooyyynoise bbboooyxydecode 2:boyencode bbboooyyynoise bbboooxxydecode repetition code corrects up to 1 correct more errors by repeating more takes up a lot of Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesMotivationDistanceQuestion:What gave the repetition code its error-correctingpowers?Codewords are far many errors to confuse one codeword with distanceDis the closest distance between twodistinct correct up toD/2 :Given a received wordrsuch that there is a codewordcwith (r,c)<D/2, Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesReed-Solomon codesReed- muller codesPolynomial-based codesReed-Solomon codeView characters as coefficients of a low-degree this polynomial at many (Reed-Solomon code )LetS Fq,|S|=n.

3 Then theReed-Solomon codeCofpolynomials of degree at mostdis given by:C={(p(x))x S|p Fq[X],deg(p) d}.baaview as 2X2+X+ 1encode (1,4,11,22,37,56,79,106,137).aaaview as X2+X+ 1encode (1,3,7,13,21,31,43,57,73).Distinct polynomials of degreedagree in at of this code isn Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesReed-Solomon codesReed- muller codesDecoding Reed-Solomon codesReed-Solomon codes are central to coding theory and applications in coding, complexity extensively Reed-Solomon codes , the Decoding problem becomes thefollowing basic noisy polynomial interpolation problem:Given:Received wordr.

4 S Fqsuch that there exists somepolynomialf(X) of degree at mostdwith (r,f)<n :f(X).Efficient algorithms known since the 1960 s (Solomon,Berlekamp, Massey, Berlekamp-Welsh).Even near-linear time algorithm Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesReed-Solomon codesReed- muller codesMultivariate polynomial codesDefinition ( Reed-Muller code )LetS Fq,|S|=n. Then theReed- muller codeCofm-variatepolynomials of degree at mostdis given by:C={(p(x1,..,xm))(x1,..,xm) Sm|p Fq[X1.]}

5 ,Xm],deg(p) d}.Lemma (Schwartz-Zippel Lemma)Letp(X1,..,Xm) F[X1,..,Xm]be a polynomial of total degreeat mostd. LetS Fhave size|S|=n. ThenPrx Sm[p(x) = 0] of Reed-Muller code isnm(1 dn).John Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesPolynomial time decoderNear-linear time decoderDecoding bivariate Reed-Muller codesReed- muller codes are also extensively in many coding, complexity theory problem is also a nice algebraic :Received wordr:S S Fqsuch that there exists somepolynomialf(X,Y) of degree at mostdwith (r,f)<n22(1 dn)=n n :f(X,Y).

6 However, no known efficient algorithm in known ford<<nand algebraically special evaluationsetsS( ).We give an efficient algorithm for this Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesPolynomial time decoderNear-linear time decoderDecoding bivariate Reed-Muller codesGiven:Received wordr:S S Fqsuch that there exists somepolynomialf(X,Y) of degree at mostdwith (r,f)<n22(1 dn)=n n :f(X,Y).Strategy:Writef(X,Y) =d i=0Pi(X)Yd i, deg(Pi(X)) (X) (X,Y) P0(X)Ydstill close tof(X,Y) P0(X) polynomialf(X,Y) P0(X)Ydis simpler (has smallerY-degree).

7 Will help find the more complex linear coefficientP1(X).John Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesPolynomial time decoderNear-linear time decoderFinding the coefficient ofYd x Sr(x,Y)decode gx(Y)guess P0(x).Try:For eachx S, decoder(x,Y) to polynomial of degreedwithin distance (n d)/2 (hopefullyf(x,Y)).Extract coefficient ofYdto get a guess forP0(x).Decode guesses forP0(x),x Sto polynomial of degree 0within :Can distribute errors to force many wrong Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesPolynomial time decoderNear-linear time decoderFinding the coefficient ofYd x Sr(x,Y)decode gx(Y)guess P0(x).

8 Problem:Can distribute errors to force many wrong :Also pass along uncertainty in our guessP0(x).The closerr(x,Y) is togx(Y), the more certain we are in (r(x,Y),gx(Y))(n d) a Reed-Solomon decoder that handles uncertainties(Forney -O(n2polylogn) time).John Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesPolynomial time decoderNear-linear time decoderFinding the coefficient ofYd iAssume:We have successfully found the higher order the received word:ri(X,Y) =r(X,Y) i 1 j=0Pj(X)Yd is close to the polynomialfi(X,Y) =d j=iPj(X)Yd decoder for degreed ipolynomialsri(x,Y)can handle more to more accurate guesses forPi(x),x , as degree ofPi(X) isi.

9 (Decoder to findPi(X)handles fewer errors.)John Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesPolynomial time decoderNear-linear time decoderEfficiency of Reed-Muller decoderQuestion:What is the runtime of our Reed-Muller decoder?For bivariate codes , runtime isO(n3polylogn).Form-variate codes , runtime isO(nm+2polylogn).Gap in runtime because decodingm-variate codes requiresdecoding (m 1)-variate codes with :Can our algorithm be improved to near-linear time?

10 (nmpolylogn).John Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesPolynomial time decoderNear-linear time decoderImproving the Reed-Muller decoder x Sri(x,Y)decode gi,x(Y)guess Pi(x),ui, hasd+ 1 iterations, one to find eachPi(X).Each iteration doesnReed-Solomon decodings and oneReed-Solomon Decoding with :Reduce the number of Reed-Solomon Forney s algorithm for Reed-Solomon Decoding Kim, Swastik KoppartyDecoding Reed-Muller codes over product setsError-correcting codesPolynomial-based codesEfficient Decoding of Reed-Muller codesPolynomial time decoderNear-linear time decoderReduce the number of Reed-Solomon decodingsEach row decoded many times to successively larger decodeto Johnson contains relevant polynomials for (n) iterations providedd= (1 )