Index Coding and Error Correction Son Hoang Dau, Vitaly Skachek, and Yeow Meng Chee Division of Mathematical Sciences, School of Physical and Mathematical Sciences Nanyang Technological University, 21 Nanyang Link, Singapore 637371 Emails: { DauS0002, Vitaly.Skachek, YMChee } @ntu.edu.sg Abstract—Aproblemofindexcodingwithsideinformationwas B. Our contribution firstconsideredbyY.BirkandT.Kol(IEEEINFOCOM,1998).In In this work, we generalize the ICSI problem towards a thepresentwork,ageneralizationofindexcodingscheme,where setup with error correction. We extend some known results 1 transmitted symbols are subject to errors, is studied. Error- 1 correctingmethodsforsuchascheme,andtheirparameters,are on index coding to a case where any receiver can correct up 0 investigated. In particular, the following question is discussed: to a certain number of errors. The problem of designing such 2 given the side information hypergraph of index coding scheme error-correctingindexcodes(ECIC’s)naturallygeneralizesthe and the maximal number of erroneous symbols δ, what is the n problem of constructing classical error-correcting codes. We shortest length of a linear index code, such that every receiver a establish an upper bound (the κ-bound) and a lower bound is able to recover the required information? This question turns J out to be a generalization of the problem of finding a shortest- (the α-bound) on the shortest length of a linear ECIC, which 4 length error-correcting code with a prescribed error-correcting is able to correct any error pattern of size up to δ. We also 1 capability in the classical coding theory. derive an analog of the Singleton bound, and show that this The Singleton bound and two other bounds, referred to as boundistightforcodesoverlargealphabets.Wealsoconsider ] the α-bound and the κ-bound, for the optimal length of a T random ECIC’s. By analyzing their parameters, we obtain an linear error-correcting index code (ECIC) are established. For I large alphabets, a construction based on concatenation of an upperboundon their length. Finally, we discuss the decoding . s optimal index code with an MDS classical code, is shown to oflinearECIC’s.Weshowthatthesyndromedecodingresults c attain the Singleton bound. For smaller alphabets, however, this inacorrectresult,providedthatthenumberoferrorsdoesnot [ construction may not be optimal. A random construction is also exceed the error-correctingcapability of the code. 1 analyzed. It yields another inexplicit bound on the length of an The problem of error correction for NC was studied in v optimal linear ECIC. Finally, the decoding of linear ECIC’s is 8 discussed. The syndrome decoding is shown to output the exact several previous works. However, these results are not di- 2 message if the weight of the error vector is less or equal to the rectly applicable for the ICSI problem. First, the existing 7 error-correcting capability of the corresponding ECIC. works only consider the multicast scenario, while the ICSI 2 problem, however, is a special case of the non-multicast NC 1. I. INTRODUCTION problem. Second, the ICSI problem can be modeled by the 0 NCscenario[8],yet,thisrequiresthattherearedirectededges A. Background 1 from particular sources to each sink, which provide the side 1 TheproblemofIndexCodingwithSide Information(ICSI) information. The symbols transmitted on these special edges, v: was introducedby Birk and Kol [1]. During the transmission, unlikeforerror-correctingNC,arenotallowedtobecorrupted. i each client might miss a certain part of the data, due to X intermittent reception, limited storage capacity or any other II. PRELIMINARIES ar reasons.Viaaslowbackwardchannel,theclientslettheserver Let Fq be the finite field of q elements, where q is a power know which messages they already have in their possession, of prime, and F∗ = F \{0}. Let [n] = {1,2,...,n}. For the q q and which messages they are interested to receive.The server vectorsu,v ∈Fn,weused(u,v)todenotethetheHamming q has to find a way to deliver to each client all the messages he distance between u and v. If u ∈ Fn and M ⊆ Fn is a set q q requested, yet spending a minimum number of transmissions. of vectors (or a vector subspace), then this notation can be Asit wasshownin [1], theservercan significantlyreducethe extended to number of transmissions by coding the messages. d(u,M)= min d(u,v). Possible applications of index coding include communica- v∈M tionsscenarios,inwhichasatelliteoraserverbroadcastsaset Givenq,k,andd,letNq[k,d]denotethelengthoftheshortest of messages to a set clients, such as daily newspaperdelivery linear code over Fq which has dimension k and minimum or video-on-demand. Index coding with side information can distance d. The support of a vector u ∈ Fnq is defined by also be used in opportunistic wireless networks [2]. supp(u) =△ {i ∈ [n]: u 6= 0}. The Hamming weight of u is i The ICSI problem has been a subject of several recent defined by wt(u) =△ |supp(u)|. Suppose E ⊆ [n]. We write studies [3]–[8]. This problem can be viewed as a special case u⊳E whenever supp(u)⊆E. of the Network Coding (NC) problem [9], [10]. In particular, We use e = (0,...,0,1,0,...,0) ∈ Fn to denote the i q as it was shown in [7], every instance of the NC problem can i−1 n−i be reduced to an instance of the ICSI problem. unit vector, which has a one at the ith position, and zeros | {z } | {z } 2 elsewhere. For a vector y = (y ,y ,...,y ) and a subset by R , i ∈ [m]. Then R actually receives the vector y = 1 2 n i i i B ={i ,i ,...,i } of [n], where i <i < ···<i , let y y+ǫ ∈FN, instead of y. 1 2 b 1 2 b B i q denote the vector (y ,y ,...,y ). i1 i2 ib Definition 3.2: Consider an instance of the ICSI problem For an n×N matrix L, let L denote its ith row. For a i described by H=H(m,n,X,f). A δ-error-correcting index set E ⊆[n], let LE denote the |E|×N matrix obtained from code ((δ,H)-ECIC) over F for this instance is an encoding q L by deleting all the rows of L which are not indexed by function the elements of E. For a set of vectors M, we use notation span(M) to denote the linear space spanned by the vectors E : Fnq →FNq , in M. We also use notation colspan(L) for the linear space suchthatforeachreceiverR ,i∈[m],thereexistsadecoding i spanned by the columns of the matrix L. function Let G =(V,E) be a graph with a vertex set V and an edge D : FN ×F|Xi| →F , i q q q set E. A directed graph G is called symmetric if satisfying (u,v)∈E ⇔ (v,u)∈E . ∀x,ǫ ∈Fn, wt(ǫ )6δ : D (E(x)+ǫ ,x )=x . i q i i i Xi f(i) The independence number of an undirected graph G is de- Ifδ =0,werefertosuchEasanon-error-correctingindex noted by α(G). There is a natural correspondence between code, or just H-IC. The parameter N is called the length of undirected graphs and directed symmetric graphs. By using the indexcode.Inthe scheme correspondingto the codeE, S thiscorrespondence,the definitionofindependencenumberis broadcasts a vector E(x) of length N over F . q naturally extended to directed symmetric graphs. Definition 3.3: A linear index code is an index code, for III. ERROR-CORRECTING INDEX CODING WITH SIDE which the encodingfunctionE is a linear transformationover INFORMATION Fq. Such a code can be described as Index Coding with Side Information problem considers ∀x∈Fn : E(x)=xL, q the following communications scenario. There is a unique whereLisann×N matrixoverF .ThematrixLiscalledthe q sender (or source) S, who has a vector of messages x = matrix correspondingto the index code E, while E is referred (x ,x ,...,x ) in his possession. There are also m receivers 1 2 n to as the linear index code based on L. R ,R ,...,R ,receivinginformationfromS viaabroadcast 1 2 m channel. For each i ∈ [m], Ri has side information, i.e. Ri Definition 3.4: An optimal linear (δ,H)-ECIC over Fq is owns a subset of messages {xj}j∈Xi, where Xi ⊆ [n]. Each a linear (δ,H)-ECIC over Fq of the smallest possible length Ri, i ∈ [m], is interested in receiving the message xf(i) (we Nq(H,δ). say that R requires x ), where the mapping f :[m]→[n] i f(i) satisfies f(i) ∈/ X for all i ∈ [m]. Hereafter, we use the Hereafter, we assume that X = (X ) is known to S. i i i∈[m] notation X = (X ,X ,...,X ). An instance of the ICSI We alsoassume thatthecodeE isknowntoeachreceiverR , 1 2 m i problem is given by a quadruple (m,n,X,f). An instance i∈[m]. of the ICSI problem can also be conveniently described by Definition 3.5: Suppose H = H(m,n,X,f) corresponds the following directed hypergraph[8]. to an instance of the ICSI problem. Then the min-rank of H over F is defined as Definition 3.1: Let (m,n,X,f) be an instance of the ICSI q pgrroabplhemH.=ThHec(morr,ens,pXon,dfi)ngissdideefininefdorbmyatthieonve(drtierxecsteetdV)h=yp[enr-] κq(H)=△ min{rankFq({vi+ef(i)}i∈[m]) : v ∈Fn , v ⊳X }. and the edge set E , where i q i i H Observe that κ (H) generalizes the min-rank over F of the E ={(f(i),X ) : i∈[n]}. q q H i sideinformationgraph,whichwasdefinedin[3].Morespecif- We often refer to (m,n,X,f) as an instance of the ICSI ically,whenm=n andf(i)=i foralli∈[m], GH becomes problem described by the hypergraphH. thesideinformationgraph,andκq(H)=min-rankq(GH).The min-rank was shown in [3], [4] to be the smallest number of Each side information hypergraph H = (V,E ) can be transmissions in a linear index code. H associated with the directed graph G = (V,E) in the H following way. For each directed edge (f(i),X ) ∈ E there Lemma 3.1: ( [3], [11]) Consider an instance of the ICSI i H will be |X | directed edges (f(i),v) ∈ E, for v ∈ X . When problem described by H=H(m,n,X,f) . i i m=n and f(i)=i for all i∈[m], the graph GH is, in fact, 1) The matrix L corresponds to a linear H-IC over Fq if the side information graph, defined in [3]. and only if for each i ∈ [m] there exists vi ∈ Fnq such Due to noise, the symbolsreceived by Ri, i∈[m], may be that vi⊳Xi and vi+ef(i) ∈colspan(L). subject to errors. Assume that S broadcasts a vector y ∈FN. 2) The smallest possible length of a linear H-IC over Fq is q Let ǫi ∈ FNq be the error affecting the information received κq(H). 3 IV. BASIC PROPERTIES Then, the matrix L corresponds to a (δ,H)-ECIC over Fq if and only if We define the set of vectors ∀i∈[m] : d(L ,M )>2δ+1. (6) I(q,H)=△ z ∈Fn : ∃i∈[m] s.t. z =0, z 6=0 . f(i) i q Xi f(i) For alli∈[m(cid:8)], we also defineY =△ [n]\ {f(i)}∪X . Th(cid:9)en i i Example 4.1: Let q = 2, m = n = 3, and f(i) = i for thecollectionofsupportsofallvectorsin(cid:16)I(q,H) isg(cid:17)ivenby i∈[3]. Suppose X ={2,3}, X ={1,3}, and X ={1,2}. 1 2 3 Let J(H)=△ {f(i)}∪Yi : Yi ⊆Yi . (1) 1 1 1 0 i∈[[m]n o L= 1 1 0 1 .   1 0 1 1 Lemma 4.1: The matrix L corresponds to a (δ,H)-ECIC over Fq if and only if Note that L generates a[4,3,1] code, which has minimum 2 distance one. However, the index code based on L can still wt(zL)≥2δ+1 for all z ∈I(q,H). (2) correct one error. Indeed, let H=H(3,3,X,f), we have Equivalently, L corresponds to a (δ,H)-ECIC over F if and q I(2,H)={100,010,001}. only if Since each row of L has weight at least three, it follows wt z L ≥2δ+1, (3) i i ! that wt(zL) ≥ 3 for all z ∈ I(2,H). By Lemma 4.1, L iX∈K corresponds to a (1,H)-ECIC over F . for all K ∈J(H) and for all choices of z ∈F∗, i∈K. 2 i q Proof: For each x∈Fn, we define Example 4.2: Assume that m = n and f(i) = i for all q i ∈ [m]. Furthermore, suppose that X = ∅ for all i ∈ [m] B(x,δ)={y ∈FN : y =xL+ǫ, ǫ∈FN, wt(ǫ)≤δ}, i q q (i.e. there is no side information available to the receivers). the set of all vectors resulting from at most δ errors in the LetH=H(m,n,X,f).Then,I(q,H)=Fnq\{0}.Hence,by transmitted vector associated with the information vector x. Lemma 4.1, the n×N matrix L corresponding to a (δ,H)- Then the receiver Ri can recover xf(i) correctly if and only ECIC overFq (for some integer δ >0) is a generatingmatrix if of an [N,n,> 2δ + 1]q linear code. Thus, the problem of B(x,δ)∩B(x′,δ)=∅, designing an ECIC is reduced to the problem of constructing a classical linear error-correcting code. for every pair x,x′ ∈Fn satisfying: q x =x′ and x 6=x′ . V. THEα-BOUND ANDTHEκ-BOUND Xi Xi f(i) f(i) Let (m,n,X,f) be an instance of the ICSI problem, and (Observe that R is interested only in the bit x , not in the i f(i) letHbethecorrespondingsideinformationhypergraph.Next, whole vector x.) we introduce the following definitions for the hypergraphH. Therefore, L corresponds to a (δ,H)-ECIC if and only if the following condition is satisfied: for all i∈[m] and for all Definition 5.1: A subset H of [n] is called a generalized x,x′ ∈Fn such that x =x′ and x 6=x′ , it holds q Xi Xi f(i) f(i) independent set in H if every nonempty subset K of H belongs to J(H). ∀ǫ,ǫ′ ∈FN, wt(ǫ)6δ, wt(ǫ′)6δ : q xL+ǫ6=x′L+ǫ′ . (4) Definition 5.2: Ageneralizedindependentsetofthelargest size in H is called a maximum generalized independent set. Denote z = x′ − x. Then, the condition in (4) can be The size of a maximum generalized independent set in H is reformulated as follows: for all i ∈ [n] and for all z ∈ Fn q called the generalized independence number, and denoted by such that z =0 and z 6=0, it holds Xi f(i) α(H). ∀ǫ,ǫ′ ∈FN, wt(ǫ)6δ, wt(ǫ′)6δ : zL6=ǫ−ǫ′ . (5) q When m = n and f(i) = i for all i ∈ [n], the generalized independence number of H is equal to the maximum size of The equivalent condition is that for all z ∈I(q,H), an acyclic induced subgraph of G , which was introduced H wt(zL)>2δ+1. in [3]. In particular, when G is symmetric, α(H) is the H independence number of G . We omit the proof. Inequality(3)followsfromthisconditioninastraight-forward H manner. Theorem 5.1 (α-bound): The length of an optimal linear Corollary 4.1: For all i∈[m], let (δ,H)-ECIC over Fq satisfies Mi =△ span({Lj : j ∈Yi}) . Nq(H,δ)>Nq[α(H),2δ+1]. 4 Proof: Consider an n×N matrix L, which corresponds VI. THESINGLETONBOUND to a (δ,H)-ECIC.LetH ={i1,i2,...,iα(H)} bea maximum Theorem 6.1 (Singleton bound): The length of an optimal generalizedindependentset in H. Then, everysubset K ⊆H linear (δ,H)-ECIC over F satisfies q satisfies K ∈J(H). Therefore, N (H,δ)≥κ (H)+2δ . q q wt ziLi ≥2δ+1 Proof: Let L be the n×Nq(H,δ) matrix corresponding iX∈K ! to some optimal (δ,H)-ECIC. Let L′ be the matrix obtained forallK ⊆H,K 6=∅,andforallchoicesofzi ∈F∗q,i∈K. by deleting any 2δ columns from L. Hence, the α(H) rows of L, namely Li1,Li2,...,Liα(H), By Lemma 4.1, L satisfies for all z ∈I(q,H), form a generator matrix of an [N,α(H),2δ + 1] code. q wt(zL)>2δ+1. Therefore, N ≥Nq[α(H),2δ+1]. We deduce that the rows of L′ also satisfy that for all z ∈ I(q,H), Thefollowingpropositionis basedonthefactthatconcate- wt(zL′)>1. nationofaδ-error-correctingcodewithanoptimal(non-error- By Lemma 4.1, L′ corresponds to a linear H-IC. Therefore, correcting) H-IC yields a (δ,H)-ECIC. by Lemma 3.1, part 2, L′ has at least κ (H) columns. We q Proposition 5.2 (κ-bound): The length of an optimal deduce that (δ,H)-ECIC over Fq satisfies Nq(H,δ)−2δ ≥κq(H), N (H,δ)≤N [κ (H),2δ+1]. which concludes the proof. q q q The proof of this proposition is omitted due to lack of space. The corollary below shows that for sufficiently large al- Corollary 5.1: Thelengthofanoptimallinear(δ,H)-ECIC phabets, a concatenation of a classical MDS error-correcting over Fq satisfies code with an optimal (non-error-correcting)index code yields an optimal linear ECIC. N [α(H),2δ+1]≤N (H,δ)≤N [κ (H),2δ+1]. q q q q Example 5.1: Let q =2, m =n = 5, δ =2, and f(i)= i Corollary 6.1 (MDS error-correcting index code): Forq ≥ for all i∈[m]. Assume κq(H)+2δ−1, X1 ={2,5}, X2 ={1,3}, X3 ={2,4}, Nq(H,δ)=κq(H)+2δ . (7) X4 ={3,5}, X5 ={1,4}. Proof:FollowsfromTheorem6.1andProposition5.2. Let H = H(5,5,X,f). The side information graph GH of Remark 6.1: ThereexisthypergraphH,suchthatGH isthe this instance is a pentagon. It is easy to verify that α(H) = (symmetric) odd cycle of length n, for which the α-bound is α(G) = 2. It follows from Theorem 9 in [4] that κ2(H) = at least as good as the Singleton bound. min-rank (G )= 3. Thus, from [12] we have 2 H VII. RANDOM CODES N [2,5]=8 and N [3,5]=10. 2 2 Theorem 7.1: Let H=H(m,n,X,f) describe an instance Due to Corollary 5.1, we have oftheICSI problem.Thenthereexistsa (δ,H)-ECICoverF q of length N if 8≤N (H,2)≤10. 2 qN Using a computer search, we obtain that N2(H,2) = 9, and qn−|Xi|−1 < , (8) the corresponding optimal scheme is based on Vq(N,2δ) iX∈[m] 1 1 1 1 1 0 0 0 0 where 0 1 0 1 1 0 1 1 0 2δ N L=1 1 0 0 0 1 1 1 0 . Vq(N,2δ)= (q−1)ℓ ℓ 0 1 1 0 0 1 0 1 1 Xℓ=0(cid:18) (cid:19)   1 0 1 0 1 0 0 1 1 is the volume of the q-ary sphere in FN.   q It is technical to verify that by Lemma 4.1, L corresponds to Idea of proof: We construct a random n×N matrix L over F , row by row. Each row is selected independently of other (2,H)-ECIC.ThelengthofthisECICliesstrictlybetweenthe q rows, uniformlyover FN. The result is obtained by bounding α-bound and the κ-bound. q from above the probability of the event Remark 5.1: Example 5.1 illustrates that over small al- phabets, the concatenation of an optimal linear (non-error- Ei , where Ei =△ d(Lf(i),Mi)<2δ+1 , correcting) index code and an optimal linear error-correcting i∈[[m] (cid:8) (cid:9) code may fail to produce an optimal linear ECIC. and by making this probability less than 1. 5 Remark 7.1: The bound in Theorem 7.1 implies a bound on κ (H), which is tightfor some H. Indeed,fix δ =0. Take • Input: yi, xXi, L. q m = n = 2ℓ+1 (ℓ ≥ 2), and f(i) = i for all i ∈ [n]. Let • Step 1: Compute the syndrome X1 = [n]\{1,2,n} and Xn = [n]\{1,n−1,n}. For 2 ≤ i ≤ β =H(i)(y −x L )T . n−1, let X =[n]\{i−1,i,i+1}. Take H=H(n,n,X,f). i i Xi Xi i Then G is the complement of the (symmetric directed) odd • Step 2: Find the lowest Hamming weight solution ˆǫ of H cycle of length n. We have |X | = 2ℓ− 2 for all i ∈ [n]. the system i Then (8) becomes H(i)ˆǫT =βi . N >2+logq(2ℓ+1). • Step3:GiventhatxˆXi =xXi,solvethesystemforxˆf(i): If q >2ℓ+1thenwe obtainN >3. Observethatin thiscase yi =xˆL+ˆǫ. κ (H) = min-rank (G ) = 3 (see [8, Claim A.1]), and thus thqe bound is tight.q H • Output: xˆf(i). VIII. SYNDROME DECODING Fig. 1: Syndrome decoding procedure. Consider the (δ,H)-ECIC based on a matrix L. Suppose that the receiver R , i∈[m], receives the vector i Figure 1 is applied to (y ,x ,L). Then, its output satisfies yi =xL+ǫi , (9) xˆ =x . i Xi f(i) f(i) where xL is the codeword transmitted by S, and ǫ is the Remark 8.1: It is not impossible that ˆǫ 6= ǫ . However, i i error pattern affecting this codeword. if wt(ǫ ) ≤ δ, it can be shown that ˆǫ ∈ L (ǫ ). Hence, by i i i In the classical coding theory, the transmitted vector c, the Lemma 8.1, we have xˆ =x . f(i) f(i) received vector y, and the error pattern e are related by y = IX. ACKNOWLEDGEMENTS c+e. For index coding, however, this is no longer the case. The following theorem shows that, in order to recover the The authors would like to thank the authors of [4] for message x from y using (9), it is sufficient to find just providing a preprint of their paper. This work is supported f(i) i one vector from a set of possible error patterns. This set is by the National Research Foundation of Singapore (Research defined as follows: Grant NRF-CRP2-2007-03). L (ǫ )={ǫ +z : z ∈span({L } )} . REFERENCES i i i j j∈Yi [1] Y. Birk and T. Kol, “Informed-source coding-on-demand (ISCOD) We henceforth refer to the set L (ǫ ) as the set of relevant i i over broadcast channels,” in Proc. IEEE Conf. on Comput. Commun. error patterns. (INFOCOM),SanFrancisco, CA,1998,pp.1257–1264. [2] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Me´dard, and J. Crowcroft, Lemma 8.1: Assume that the receiver R receives y . “Xors in the air: Practical wireless network coding,” in Proc. ACM i i SIGCOMM,2006,pp.243–254. 1) IfRi knowsthemessagexf(i) thenitisabletodetermine [3] Z. Bar-Yossef, Z. Birk, T. S. Jayram, and T. Kol, “Index coding with the set L (ǫ ). sideinformation,”inProc.47thAnnu.IEEESymp.onFound.ofComput. i i Sci.(FOCS),2006,pp.197–206. 2) If R knows some vector ˆǫ ∈ L (ǫ ) then it is able to i i i [4] ——, “Index coding with sideinformation,” IEEETrans.Inform. The- determine x . ory,toappear. f(i) [5] E. Lubetzky and U. Stav, “Non-linear index coding outperforming the linear optimum,” Proc. 48th Annu. IEEESymp. on Found. of Comput. We now describea syndromedecodingalgorithmforlinear Sci.(FOCS),pp.161–168, 2007. error-correcting index codes. We have [6] S.ElRouayheb,M.A.R.Chaudhry,andA.Sprintson,“Ontheminimum number of transmissions in single-hop wireless coding networks,” in y −x L −ǫ ∈span {L }∪{L } . Proc.IEEEInform.TheoryWorkshop(ITW),2007,pp.120–125. i Xi Xi i f(i) j j∈Yi [7] S. El Rouayheb, A. Sprintson, and C. Georghiades, “On the relation Let C =span({L }∪{L } (cid:0) ), and let H(i) be(cid:1)a parity between the index coding and the network coding problems,” in Proc. i f(i) j j∈Yi IEEESymp.onInform.Theory(ISIT),Toronto,Canada,2008,pp.1823– check matrix of C . We obtain that i 1827. [8] N.Alon,A.Hassidim,E.Lubetzky,U.Stav,andA.Weinstein,“Broad- H(i)ǫTi =H(i)(yi−xXiLXi)T . casting with side information,” in Proc. 49th Annu. IEEE Symp. on Found.ofComput.Sci.(FOCS),2008,pp.823–832. Let β be a column vector defined by [9] R. Ahlswede, N. Cai, S. Y. R. Li, and R. W. Yeung, “Network i informationflow,”IEEETrans.Inform.Theory,vol.46,pp.1204–1216, β =H(i)(y −x L )T . 2000. i i Xi Xi [10] R.KoetterandM.Me´dard,“Analgebraicapproachtonetworkcoding,” ObservethateachR iscapableofdeterminingβ .Thisleads IEEE/ACMTrans.Netw.,vol.11,pp.782–795,2003. i i [11] S. H. Dau, V. Skachek, and Y. M. Chee, “Secure us to the formulation of the decoding procedure for R in i index coding with side information,” available online at Figure 1. http://arxiv.org/abs/1011.5566. Theorem 8.2: Let y = xL + ǫ be the vector received [12] M. Grassl, “Bounds on the minimum distance of linear codes and i i by R , and let wt(ǫ ) 6 δ. Assume that the procedure in quantumcodes,”availableonlineathttp://www.codetables.de. i i