Decoding algorithms for Reed-Solomon Codes.

(1)

Dipartimento di Matematica

Corso di Laurea Magistrale in Matematica

Tesi di Laurea Magistrale

Decoding algorithms

for Reed-Solomon codes

Candidato:

Relatori:

Isabella Panaccione

Dott. Alain Couvreur

Prof.ssa Ilaria Del Corso

Controrelatore:

Dott. Massimo Caboara

(2)

Introduction

Reed-Solomon codes are interesting in Coding Theory because they dispose of several decod-ing algorithms. This property allows to work with them easily and to solve many different decoding problems.

Given a code C, one of the best known decoding problems is the unambiguous decoding problem: if C ⊆ Fn

q has minimum distance d and y ∈ Fnq, we look for an element c ∈ C such

that

δ(y, c) = |{i ∈ {1, . . . , n} | yi 6= ci}| ≤

d − 1 2 .

The reason why it is called “unambiguous”, is that we will have at most one solution (it is entailed by the definition of minimum distance). By solving this kind of problem we are then able to correct up to d−1

2 errors. We remind in particular two algorithms which can be

applied to Reed-Solomon codes in order to solve the unambiguous decoding problem: • Berlekamp-Welch algorithm (see [5]);

• Error Correcting Pairs algorithm (see [10]).

Another important decoding problem is the list decoding problem: given a code C ⊆ Fn q,

y ∈ Fn

q and t ∈ N with t ≤ n, we want to find the set

{x ∈ C | δ(x, y) ≤ t}.

The important property of this problem is that we can choose even t > d−1

2 . In this case

though we may not have uniqueness of the solution. This is why we are looking for a list. Even this case, we can find an algorithm for Reed-Solomon codes: Sudan algorithm (see [7]), which can be regarded as a generalisation of Berlekamp-Welch algorithm. However, even if we talked about a list, if we do not choose a too big t, the situations where the list contains more than one solution are very rare. That is why Power Decoding algorithm is also very useful ([1]). That is another generalisation of Berlekamp-Welch algorithm for Reed-Solomon codes which can correct more than d−1

2 errors. Though it does not solve the list decoding

problem, since it gives only one solution or zero.

In the first two chapters of this thesis we will give the first notions of Coding Theory and an overview on these Reed-Solomon codes decoding algorithms, while in the last three chapters we will present some personal results and considerations:

• in Chapter 4 we will study the solution space S of a subproblem of Power Decoding algorithm. In particular we will focus on the relation between Sudan solutions and S;

(4)

• Experimentation: in Chapter 5 we will define a particular error typology, the homoge-neous error vector, which allows to produce examples where the Sudan solutions list is longer than two. We will be able then to study the behaviour of this algorithm in sev-eral situations. Moreover we will present a failure case for Power Decoding algorithm and give some considerations about it;

• Power Error Correcting Pairs: we have seen that Berlekamp-Welch algorithm can be then generalised by two algorithms which correct more than the unambiguous amount of errors. In Chapter 3 we will present a generalisation of Error correcting pairs algorithm too. In particular we will use the key relations of Power Decoding algorithm in order to find an alternative definition of error correcting pairs, which will take the name of power error correcting pairs. An interesting property is that this algorithm, as the main one, can be applied to any code which disposes of a power error correcting pair. Moreover, if we apply this new algorithm to Reed-Solomon codes, we obtain the same decoding radius as Power Decoding algorithm but with a smaller cost.

(5)

Chapter 1

Coding Theory

1.1 Error correcting codes

In order to understand the following chapters we will give some notions of Coding Theory. Definition 1.1.1. Given a finite field Fq and n ∈ N we define a linear error correcting code

as a subspace C of Fn

q. We will indicate with k its dimension as a Fq−vector space and we

will call the integer n the length of C.

For convenience, we will just write “linear code”.

Definition 1.1.2. Let K be a field. Given two elements x = (x1, . . . , xn), y = (y1. . . , yn)

of Kn_{, the Hamming distance between x and y is}

δ(x, y) = |{i ∈ {1, . . . , n} | xi6= yi}|.

It is easy to verify that δ is a distance over Kn_{. In particular we can define the weight of an}

element x ∈ Kn _{as w(x) = δ(x, 0).}

Definition 1.1.3. Let C ⊆ Fn

q be a linear code. We define the (minimum) distance of C as

d = min

x6=y∈Cδ(x, y).

Remark 1.1.4. It is also possible to give a more general definition of error correcting code, by removing the condition of linearity. In this case, our code will be only a subset of Fn

q,

which means that we could not even define the dimension and, moreover, we could not use the following result.

Theorem 1.1.5. Let C ⊆ Fn

q a linear code. Then

d = min

06=x∈Cw(x).

(6)

n, dimension k and minimum distance d. Depending on the context we may use also other parameters for a code: the rate R = k

n and the relative distance D = d n.

It is now quite natural to wonder about a link between these three integers we presented. Theorem 1.1.6. Let C be a code [n, k, d]. Then the following bound (called Singleton bound) holds

d ≤ n − k + 1.

Proof. Let us suppose that d > n − k + 1. Then we have k > n − d + 1, that means that there are at least n − d + 2 linearly independent vectors in C. Let us call these vectors v1, . . . , vn−d+2 and consider the matrix M ∈ M(Fq, n − d + 2, n)such that Mi= vi for all

i = 1, . . . , n − d + 2. Since C is a linear code, by operating with Gaussian reduction on the rows of M, we obtain elements of C. After this reduction we have in the last row a nonzero vector ˜v with at least n − d + 1 zero coefficients. So we have w(˜v) ≤ d − 1.

Definition 1.1.7. A code [n, k, d] is a Maximum Distance Separable code (MDS) if it fulfills d = n − k + 1.

Notation: We will work with row vectors and, given M ∈ M(Fnq, m, n), we will write

kerr(M ) = {x ∈ Fnq | M xt= 0}, Imr(M ) = {M xt| x ∈ Fnq}, kerl(M ) = {x ∈ Fmq | xM = 0}

and Iml(M ) = {xM | x ∈ Fmq }. Where not specified, by ker and Im, we will mean kerr and

Imr.

We would like now to explain how to represent a code. In the last proof we already gave an idea of what we could use:

Definition 1.1.8. If C is a code [n, k, d], a generator matrix for C is a matrix G whose rows generate C as Fq-vector space. Since dimFqC = k, then G ∈ M(Fq, m, n) with m ≥ k and

we can write

C = {xG | x ∈ Fmq } = Iml(G).

Definition 1.1.9. Given C a code [n, k, d], a parity-check matrix for C is a matrix H ∈ M(Fq, n − l, n)such that kerr(H) = C. Again, for dimension reasons, we have l ≤ k.

The following statement relates the notion of minimum distance with that of generator and parity check matrix.

Proposition 1.1.10. Given C a code with distance d and a parity-check matrix H for C, then every (d − 1)-tuple of columns of H is linearly independent while there exists at least one d-tuple of columns of H linearly dependent.

Proof. We know that C = ker(H). Suppose there is a (d − 1)-tuple (wlog {H1_{, . . . , H}d−1_}₎

of linearly dependent columns of H, then there exist c1, . . . cd−1 such that PiciHi = 0

and c1, . . . , cd−1 ar not all zero. Then we could take the vector y such that yi = ci for

i = 1, . . . , d − 1 and yi = 0 for i = d, . . . n. It is easy to see that y ∈ C since Hyt =

Pd−1

i=1H i_c

(7)

of H which is linearly dependent. Since there is x ∈ C such that w(x) = d, that means that we have a linear combination of d columns of H which gives 0.

Theorem 1.1.11. Let C be an [n, k, d] code and let G ∈ M(Fq, k, n) and H ∈ M(Fq, n−k, n)

be respectively its generator matrix and its parity-check matrix. Then C is MDS if and only if one of the following statements is satisfied:

(i) every k × k minor of G is non zero;

(ii) every (n − k) × (n − k) minor of H is non zero.

Proof. Thanks to Proposition 1.1.10, it is easy to see that a code is MDS if and only if (ii) holds. In fact we have that every (n − k) × (n − k) minor of H is non zero if and only if every (n − k)-tuple of columns of H are linearly independent. This is equivalent to say that d ≥ n − k + 1that means, because of the Singleton bound, the code is MDS.

Let us now prove that a code is MDS if and only if it satisfies (i). Let us suppose that there is x ∈ C such that w(x) ≤ n − k. Then there is m ∈ Fk

q such that mG = x. In particular we

can find k columns Gi1_{, . . . , G}ik of G such that mGij _{= 0}. Therefore the matrix R whose

columns are the Gijs, has ker

l6= 0, that means there is a k × k zero minor of G. To prove

(MDS⇒ (i)) it is possible to follow the same path in the other way. In this work we will need the notion of dual of a code.

Definition 1.1.12. Given a [n, k, d] code C, the dual code of C is D = C⊥, where the symbol ⊥refers to the standard inner product hx, yi = Pn_i=1xiyi.

Remark 1.1.13. Since we are working with finite fields, the standard inner product may have less good properties than in the case of R or C. For instance it is not always true that A ∩ A⊥_{= 0}_{. Though it is easy to see that dim(A}⊥_{) = n − dim(A)}_{, since the standard inner}

product is not degenerate.

Remark 1.1.14. Even if the name is the same, it is important to distinguish the dual of C from the the space C∨_{of linear forms of C. In fact they do not even have the same dimension,}

since dim(C⊥_{) = n − dim(C)}_{, while dim(C}∨_{) = dim(C)}_.

The codes C and C⊥ _{are related by the following statements:}

Proposition 1.1.15. Let C be a [n, k, d] code and let G and H be respectively a generator matrix and a parity-check matrix for C. Then,

(i) G is a parity-check matrix for C⊥_;

(ii) H is a generator matrix for C⊥_.

Proof. We already know that dim_F_q(C⊥) = n − dim_F_q(C) = n − k. For any row Hiof H we

have

(8)

that is, any row of H belongs to C⊥_{. Therefore we have}

S := span_F

q(H1, . . . , Hn−m) ⊆ C

⊥_.

Moreover, since dim(ker(H)) = dim(C) = k, we have rk(H) = n − k, hence dim(S) = dim(Iml(H)) = n − k. Thus, we proved that Im(H) = C⊥, i.e. H is a generator matrix of

C⊥_{. We want now to show that ker(G) = C}⊥_{. We have}

HGt= 0 ⇐⇒ GHt= 0,

therefore C⊥ _{⊆ ker(G)}_{. But dim(ker(G)) = n − rk(G) = n − k = dim(C}⊥₎_.

Remark 1.1.16. An important consequence of this result is that if C is an MDS code, then C⊥ _{is an MDS code too. In fact, let us consider a parity check matrix H ∈ M(F}

q, n − k, n)

of C. Then, from Proposition 1.1.15, H is a generator matrix for C⊥_{, whose dimension is}

n − k. Therefore from Theorem 1.1.11, C⊥ is MDS.

Another structure we will be interested in, is the star product of a finite number of codes. Definition 1.1.17. Given two vectors v = (v1, . . . , vn) and w = (w1, . . . , wn) of Fnq we

define

v ∗ w = (v1w1, . . . , vnwn)

as the star product between v and w. Moreover, given n ∈ N, we will denote v∗n= v ∗ v ∗ · · · ∗ v

| {z }

n

.

Definition 1.1.18. Given two codes C, D ⊆ Fnq, we define

C ∗ D = span_F_q{v ∗ w | v ∈ C, w ∈ D} and call it the star product between C and D.

Remark 1.1.19. We have the following properties:

• C∗D is a linear code of length n whose dimension satisfies dim(C∗D) ≤ dim(C) dim(D); • Given three vectors u, v, w ∈ Fn

q, we have hu ∗ v, wi = hu, v ∗ wi;

• Given u, w ∈ Fn

q and a linear code A ⊆ Fnq, we have

u ∗ w ∈ A⊥⇐⇒ u ∈ (w ∗ A)⊥⇐⇒ w ∈ (u ∗ A)⊥.

The proofs, which are quite easy, are left to the reader.

1.2 Reed-Solomon codes

We can now introduce a particular family of linear codes. Reed-Solomon codes are inter-esting in Coding Theory for several reasons. First of all, as we will see, they are MDS.

(9)

Moreover, they have many efficient decoding algorithms to correct up to bd−1

2 cerrors and

some algorithms who go even beyond this bound (we will present some of them in Chapter 2). Let us consider a finite field Fq, an integer k and introduce the space

Fq[x]<k:= {p(x) ∈ Fq[x] | deg(p(x)) < k}.

Definition 1.2.1. Given x = (x1, . . . , xn) ∈ Fnq with xi 6= xj for any pair (i, j) such that

i 6= j, and an integer k ≤ n, we define the Reed-Solomon code given by x as RSk(x) := {(p(x1), . . . , p(xn)) | p(x) ∈ Fq[x]<k}.

Remark 1.2.2. Since x is in Fn_q, we have length(RSk(x)) = n. Moreover we can observe

that G :=       1 . . . 1 x1 . . . xn ... ... xk−1₁ · · · xk−1 n      

is a generator matrix for RSk(x)and it is a truncated Vandermonde matrix. Since xi6= xj

for i 6= j, we have dim(RSk(x)) = rk(G) = k. Finally, Reed-Solomon codes are MDS. Infact,

every k × k minor of G is non zero, since it is the determinant of a Vandermonde matrix and xi6= xj for any pair (i, j) such that i 6= j. Hence, from Theorem 1.1.11, RSk(x)is MDS.

We will then use the notation RS[n, k](x) or even RS[n, k] if it is clear what is the x we are talking about. In order to present some decoding algorithms for Reed-Solomon codes, we need to prove some results. In particular we will see how the dual and the star product behave with Reed-Solomon codes.

Duality for Reed-Solomon codes

Since we know that, for any linear code C, we have dim(C⊥) = n − dim(C),

the naive intuition would be that (RS[n, k])⊥ _{= RS[n, n − k]}_{. Unfortunately that is true}

only in a particular case:

Theorem 1.2.3. Let x = (x1, . . . , xn) with {x1, . . . , xn} = {x1, . . . , xq} = Fq. Then

(RS[n, k](x))⊥= RS[n, n − k](x).

In order to prove this theorem we will need the following lemma. Lemma 1.2.4. Let 0 ≤ t ≤ q − 1. Then

X α∈Fq αt=    0 0 ≤ t < q − 1 −1 t = q − 1.

(10)

Proof. We observe that, since we are working in characteristic dividing q, for t = 0 it is obvious. Let us now consider a generator γ of F∗

q. Then our sum becomes

X α∈Fq αt= q−1 X i=1 γit.

If 0 6= t < q − 1, then γt_{6= 1}_{and we can write}

X α∈Fq αt=1 − γ t(q−1) 1 − γt = 0. If t = q − 1, then P_α∈F_qαt_{= −1}_.

Now we are ready to prove Theorem 1.2.3.

Proof. Let us prove that every row of a generator matrix for RS[n, k](x) is orthogonal to every row of a generator matrix for RS[n, n − k](x). From remark 1.2.2, we know we can take as generator matrices two truncated Vandermonde matrices respectively with k and n − krows. The inner product between two generic rows will be

h(xi1, . . . , x i n), (x j 1, . . . , x j n)i = n X s=1 xi+j_s = X α∈Fq αi+j = 0

from Lemma 1.2.4, since i + j ≤ q − 2.

We wonder what can happen if {x1, . . . , xn} ( Fq. In order to study this more general case

we have to introduce a broader family of codes.

Definition 1.2.5. Given y = (y1, . . . , yn) ∈ Fnq with yi 6= 0 for all i ∈ {1, . . . , n} and

x = (x1, . . . , xn) with xi 6= xj for all i 6= j, we define the generalised Reed-Solomon code

given by x and y as

GRSk(x, y) = {(y1p(x1), . . . , ynp(xn)) | p(x) ∈ Fq[x]<k}.

Remark 1.2.6. As for a Reed-Solomon code, also a generalised Reed-Solomon code has dimension k and length n. In fact let

Y =     y1

₀

...

0

_y_n     , G =       1 . . . 1 x1 . . . xn ... ... xk−1₁ · · · xk−1 n       .

Then, a generator matrix for GRSk(x, y) is given by the product Y G and since yi 6= 0for

all i,

(11)

Moreover, the generalised Reed-Solomon codes are MDS too. In fact, Y induces an isometry of Fn

q with respect to the distance δ, hence d(GRSk(x, y)) = d(RSk(x)).

Let us now see what happens to the dual of a Reed-Solomon code in the most general case. Theorem 1.2.7. If x = (x1, . . . , xn) ∈ Fnq with xi 6= xj for any pair (i, j) such that i 6= j,

and y = (y1, . . . , yn) ∈ Fnq with yi6= 0 for all i, then

(GRS[n, k](x, y))⊥= GRS[n, n − k](x, y’),

where for all i ∈ {1, . . . , n}

y0_i= − 1 yiQj6=i(xj− xi)

·

For the proof we refer to [3], [4] or the lectures notes [2].

Thanks to this theorem, we can conclude that the dual code of a Reed-Solomon code RS[n, k](x)is the generalised Reed-Solomon code GRS[n, n − k](x, y), where

yi= −

1 Q

j6=i(xj− xi)

·

Reed-Solomon codes and star product

Let now us study the behavior of Reed-Solomon codes with the star product. Proposition 1.2.8. If (k1+ k2− 1) ≤ n, then

RS[n, k1](x) ∗ RS[n, k2](x) = RS[n, k1+ k2− 1](x).

Proof. First of all let us show that

RS[n, k1+ k2− 1] ⊆ RS[n, k1] ∗ RS[n, k2].

We know that RS[n, k1+k2−1]is generated by the evaluations of the monomials 1, x, . . . , xk1+k2−2

in x1. . . , xn. So it is equivalent to show that all these evaluations belong to the star product,

which is simple.

Conversely, we know that by definition it is enough to prove v ∗ w ∈ RS[n, k1+ k2− 1]

for any v ∈ RS[n, k1], w ∈ RS[n, k2]. If v = (p(x1), . . . , p(xn)) with deg(p) < k1 and

w = (q(x1), . . . , q(xn))with deg(q) < k2, then we can see v ∗ w as (r(x1), . . . , r(xn))where

(12)

Chapter 2

Known decoding algorithms

The reason why we are interested in Coding Theory, is the exchange of messages. In partic-ular let us imagine two people who want to communicate by using a channel. The problem is that the channel may have some noise and the message may then arrive on the other side with some alterations. Then, what we want to do by using error correcting codes, is to give a way to recover the original message even if it has been affected in some way.

An important instrument we have, is the minimum distance. In fact, if we know the min-imum distance of a code, then we know how much two codewords can be close to each other. In particular, given a vector y ∈ Fn

q, we cannot have two codewords c1, c2 such that

δ(y, c1) ≤ d−1₂ and δ(y, c2) ≤ d−1₂ (otherwise δ(c1, c2) < d). Figure 2.1 gives a clearer idea

of that: we take two codewords c1, c2 such that δ(c1, c2) = d and h < d−1₂ . Then, the ball

Bδ(y, h)can include at most one element of the code.

Figure 2.1: Example We will focus in particular on the two decoding problems:

• Unambiguous decoding problem: given a code C ⊆ Fn

q and y ∈ Fnq, find a codeword

c ∈ C such that δ(y, c) ≤ d−1

2 . This problem cannot have more than one solution and

it may even have no solution1_;

1_{That depends in fact on the code. There are some codes, called “perfect”, for which a solution is always}

(13)

• List decoding problem: given a code C ⊆ Fn

q, y ∈ Fnq and r ∈ Z+, find the list of all

codewords {c1 . . . , cs} ⊆ C such that δ(y, ci) < r for all i = 1, . . . , r. This problem

may have more than one solution or even no one.

We now present two algorithms solving the unambiguous decoding problem for Reed-Solomon codes in polynomial time.

2.1 Context

Let C = RS[n, k](x), where x = (x1, . . . , xn) ∈ Fnq and let c = (f(x1), . . . , f (xn)) ∈ C with

deg f < k. Let us suppose that during the transmission, the codeword c is affected by an error e = (e1, . . . , en) ∈ Fnq such that t = w(e) ≤ d−12 . We will obtain then a new vector

y = c + e. What we want to do, is to recover c with the very knowledge of y. Definition 2.1.1. Given a vector x ∈ Fn

q, we define its support as

supp(x) := {i ∈ {1, . . . , n} | xi6= 0}.

In the following section we will call I = supp(e), hence we have |I| = w(e) = t.

2.2 Berlekamp-Welch algorithm

We will refer to [5] for more informations. Let us set Λ(x) :=Y

i∈I

(x − xi).

Of course, polynomial Λ(x) is unknown. Since Λ(xi)ei= 0 for all i = 1, . . . , n, this

polyno-mial fullfills

Λ(xi)yi= Λ(xi)f (xi) ∀i = 1, . . . , n. (2.1)

We would like now to use these equations to find the coefficients of f and Λ. The problem is that we know only the yi’s, so this is a non linear system, that is difficult to solve. We

can though linearise it by defining a polynomial N(x) = Λ(x)f(x) (so deg(N(x)) < t + k). This way, (2.1) becomes

Λ(xi)yi = N (xi) ∀i = 1, . . . , n. (2.2)

Therefore we can solve the easier problem: find ˜Λ with deg(˜Λ) = t and Ñ with deg( Ñ ) < t+k such that (2.2) holds for all i = 1, . . . , n. Once we have a solution (˜Λ, Ñ ), we recover f = N_˜˜

Λ.

A priori there is no reason why, given a general solution (˜Λ, ˜N ), then N_˜˜

Λ has to be

ex-actly our f (we may not even have ˜Λ| ˜N). Actually we have the following result:

Theorem 2.2.1. Let t ≤ n−k₂ . If ( ˜Λ, ˜N ) is a non zero solution to Problem (2.2), then ˜

Λ 6= 0. Furthermore if (Λ1, N1), (Λ2, N2) are two non zero solutions to this problem, then

N1

Λ1

=N2 Λ2

(14)

Proof. Let us consider (˜Λ, ˜N )a non zero solution to the problem. If ˜Λ = 0, then ˜N (xi) = 0

for all i = 1, . . . , n. Therefore Ñ has at least n different roots, but deg( Ñ ) < t + k and t ≤ n−k₂ . So Ñ = 0, while for hypothesis (˜Λ, Ñ ) 6= (0, 0).

Let now (Λ1, N1), (Λ2, N2)be two non zero solution to the problem. We want to show that

0 = N1 Λ1 −N2 Λ2 = N1Λ2− N2Λ1 Λ1Λ2 ,

so let us prove that R = N1Λ2− N2Λ1 is 0. For all i = 1, . . . , n, we have

R(xi) = N1(xi)Λ2(xi) − N2(xi)Λ1(xi)

= yiΛ1(xi)Λ2(xi) − yiΛ2(xi)Λ1(xi)

= 0.

Therefore R has at least n different roots, while deg(R) ≤ 2t+k −1 and from the hypothesis t ≤ n−k₂ , we get R = 0.

Remark 2.2.2. From (2.1) we observe that (Λ, Λf) is a solution to Problem (2.2), hence we have at least one solution.

We can now write the algorithm. As we said, given a generic y ∈ Fn

q, there may not exist a

codeword c such that δ(y, c) ≤ d−1

2 . That is why this algorithm can give also the result “?”.

Algorithm 1:Berlekamp-Welch algorithm Data: y ∈ Fnq.

Result: c ∈ RS[n, k] such that y = c + e with w(e) ≤ d−1₂ , if it exists. Otherwise it returns “?”.

1 Compute a non zero solution to Problem (2.2); 2 if (Λ|N ) then 3 f := N Λ; 4 if deg(f ) < k and δ((f (x₁), . . . , f (x_n)), y) ≤d−1 2 then 5 c = (f (x₁), . . . , f (x_n)); 6 return c; 7 end 8 end 9 return“?”; Complexity

In this algorithm we have to:

• solve a linear system with n equations and 2t + k + 1 unknowns. From the bound on t, we get 2t + k + 1 ≤ n, hence the computational cost is O(n3₎_;

• do an Euclidian division of N, which has degree t+k, by Λ, which has degree t. Hence the cost is O(tk) ≈ O(k(n − k));

(15)

• evaluate f in the xi’s, hence this cost is O(nk), that is O(n2).

Therefore, the complexity of the Berlekamp-Welch algorithm is O(n3₎_{. Actually it is possible}

to reduce the cost to O(n2₎_{by replacing the linear algebra’s step with Euclid algorithm [6].}

2.3 Error Correcting Pairs algorithm

Let us now present another algorithm for the unambiguous decoding problem. Error Cor-recting Pairs algorithm has been developped in order to give decoding algorithms also for more general geometric codes, in fact it can be applied to any code with certain proper-ties we will present later. Another peculiarity is given by the output. In fact, while the Berlekamp-Welch algorithm returns a codeword c such that y = c+e and w(e) ≤ d−1

2 , Error

Correcting Pairs algorithm returns only the support of e. It is then natural to wonder if the support of the error e can give enough informations to find c. We have the following general result.

Proposition 2.3.1. Let C be a [n, k, d] code and y = c + e ∈ Fnq with c ∈ C.

Let I ⊆ {1, . . . , n} such that I ⊇ supp(e). If |I| ≤ d − 1, then it is possible to find c. In order to prove this proposition and to make the notation easier we give some definitions first.

Definition 2.3.2. Let us consider I ⊂ {1, . . . , n} and a set A ⊂ Fnq. We define

A(I) := {a ∈ A | ai= 0, ∀i ∈ I}.

Let us consider now a linear code B ⊂ Fn

q, I ⊂ {1, . . . , n} with | I |= t and the map:

πI : Fnq −→F t q

x 7−→(xi)i∈I.

We will call BI = πI(B).

Remark 2.3.3. B(I)is a linear code. Moreover, if we consider the restriction of πI to B

˜

πI : B −→ Ftq,

then we have that ker(˜πI) = B(I)and Im(˜πI) = BI.

Let us now prove Proposition 2.3.1.

Proof. We can write I = {i1, . . . , ir}with r ≤ d − 1. Let us consider a parity check matrix

H for C. Then we have

sT := HyT = HeT = r X j=1 Hij_e ij,

(16)

where e is unknown. That is, we can consider the n × r matrix HI

h

Hi1_|Hi2_{| . . . |H}ir

i

and we have that the system HIeTI = s T

I has only one solution, since HI has rank r ≤

d − 1 ≤ n − k.

Proposition 2.3.1 tells us that even if we have a y = c+e much closer to a “wrong” codeword c1, if we know the positions of the errors and w(e) < d, we can still recover c (see Figure 2.2).

Hence, since we want to solve the unambiguous decoding problem, we have w(e) ≤ d−1 2 , and

Figure 2.2: Example

by knowing the support of e, we can find c. Now, we can focus on error correcting pairs. In [10], Pellikaan gives the following definition.

Definition 2.3.4. Given A, B, C linear codes in Fn

q, the couple (A, B) is a t-error correcting

pair for C if (i) dim(A) > t; (ii) d(B⊥_{) > t}_;

(iii) A ∗ B ⊆ C⊥_;

(iv) d(A) + d(C) > n.

In [10] it is presented an algorithm which does not go through Proposition 2.3.1 and gives as output the solution c. In particular the last hypothesis is needed to entail the solution and the uniqueness of it. Though, since we want to solve the non ambiguous decoding problem and we are looking only for the support of e (hence, we will not use the final part of Pellikaan algorithm), we will give a different definition and talk about almost-t-error correcting pairs. In this case, the solution is not entailed, but the probability to have that is very small. Definition 2.3.5. Given A, B, C linear codes in Fnq, the couple (A, B) is an almost-t-error

correcting pair for C if it fulfills (i), (ii) and (iii).

(17)

code C then, given y = c+e with c ∈ C and w(e) ≤d−1

2 , we are able to detect I ⊆ {1, . . . , n}

such that I contains the support of e. We will need some lemmas.

Definition 2.3.6. Let A and B be linear codes on Fn_q. Given a codeword y ∈ Fn_q, we define the map Ey by

Ey : A −→ B∨

a 7−→ (b 7→ hy, a ∗ bi).

where we recall that B∨_{denotes Hom}

Fq(B, Fq).

Remark 2.3.7. We have:

(i) If A ∗ B ⊆ C⊥ _{and y = c + e with c ∈ C, then E}

y = Ee. Indeed, for all a ∈ A and b ∈ B

hy, a ∗ bi = hc, a ∗ bi + he, a ∗ bi = he, a ∗ bi,

since hc, a ∗ bi = 0.

(ii) If y = c + e with c ∈ C and supp(e) = I, then ker(Ey) ⊇ A(I). Indeed, if a ∈ A(I),

then for any b ∈ B we get

hy, a ∗ bi = he, a ∗ bi = heI, aI ∗ bIi = 0,

since aI = 0.

Lemma 2.3.8. The following statements are equivalent: (i) d(B⊥_{) > t}_.

(ii) codimB(B(I)) = tfor every subset I of {1, . . . , n} with | I |= t.

(iii) BI = Ftq for every subset I of {1, . . . , n} with | I |= t.

Proof. From Remark 2.3.3, we have the equivalence between (ii) and (iii). Let us now prove (i)⇔(iii):

(⇐) Suppose there is x ∈ B⊥such that w(x) ≤ t. Let us consider I = {i1, . . . , it} ⊆ {1, . . . , n}

such that |I| = t and I ⊇ supp(x). Since BI = Ftq, there exists c ∈ B such that

cI = (1, 0, . . . , 0) ∈ Ftq. Then we have

0 = hc, xi = hcI, xIi = xi1.

If we do the same for any ij ∈ I, we obtain x = 0. Hence d(B⊥) > t.

(⇒) First, let us observe that dim(B) ≥ t. Indeed, since d(B⊥) > t, we get dim(B) = n − dim(B⊥) ≥ n − n + d(B⊥) − 1 > t − 1.

Let us now consider G a full rank generator matrix for B and let G1_{, . . . G}n _{be the}

(18)

columns are Gi1_{, . . . , G}it. We observe that G

I is a generator matrix for BI. If we

prove that rk(GI) = t, then we get BI = Ftq. If rk(GI) < t, it means that these

columns are linearly dependent. Hence, there exists x ∈ Ft

q such that GIxT = 0. We

define the vector c ∈ Fn

q such that    ch= xij h = ij ch= 0 h /∈ I. (2.3) Therefore, we get c ∈ B⊥ _{because Gc}T _{= G}

IxT = 0. But w(c) ≤ t, while d(B⊥) > t.

Hence, for any I ⊆ {1, . . . , n} such that |I| = t, BI = Ftq.

Lemma 2.3.9. Let A, B, C be linear codes in Fn

q such that A ∗ B ⊆ C⊥, y = c + e with c ∈ C

and supp(e) = I ⊂ {1, . . . , n}. Then2

ker(Ey)

A(I)∼= πI(e ∗ A) ∩ (BI)⊥.

Proof. Let us define

Φ : ker(Ey) −→ πI(e ∗ A) ∩ (BI)⊥

a 7−→ πI(e ∗ a)

The map Φ is well defined: given a ∈ ker(Ey), let us prove that πI(e ∗ a) ∈ (BI)⊥. In order

to do that, we take b ∈ B and we show that hπI(e ∗ a), bIi = 0. We have

hπI(e ∗ a), bIi = he ∗ a, bi (2.4)

= he, a ∗ bi

= hy, a ∗ bi, (2.5) where in (2.4) and (2.5) we used respectively that supp(e) = I and a ∈ ker(Ey).

By definition we have that the map is surjective. Indeed, let us consider x ∈ πI(e∗A)∩(BI)⊥.

Then there exists a ∈ A such that πI(e ∗ a) = x. We want to prove that a ∈ ker(Ey). For

any b ∈ B, then we get

hy, a ∗ bi = he, a ∗ bi = h(e ∗ a)I, bIi = 0,

because supp(e) = I and a ∈ (BI)⊥. Now, it is straightforward to see that ker(Φ) = A(I).

Hence Φ induces an isomorphism.

Now we are ready to prove the following theorem.

Theorem 2.3.10. Let (A, B) be an almost-t-error correcting pair for a linear code C in Fn q

and let y = c + e with c ∈ C, I = supp(e) and t =| I |. Then ker(Ey) = A(I).

2_{We can speak about ker(E}y)

(19)

Proof. We already know that A(I) ⊆ ker(Ey). From Lemma 2.3.9 we have

ker(Ey)

A(I)∼= πI(e ∗ A) ∩ B⊥I.

From Lemma 2.3.8 we have that dim(BI) = t, so dim(BI⊥) = 0. Hence ker(Ey) = A(I).

2.3.1 The Reed-Solomon codes case

We want now to show that it is possible to use Error Correcting Pairs algorithm to solve the unambiguous decoding problem for Reed-Solomon codes. Let us consider the situation described at the beginning of the chapter. What we have to do, is to find an almost-t-error correcting pair for C = RS[n, k].

Since dim(A) has to be bigger than t, we take A = RS[n, t + 1]. Moreover we need to have

A ∗ B ⊆ C⊥,

that is equivalent to A ∗ C ⊆ B⊥ _{from Remark 1.1.19. Since A and C are Reed-Solomon}

codes, their star product is the Reed-Solomon code RS[n, t + k] from Proposition 1.2.8. We take then B⊥ _{= RS[n, t + k]}_{. In order to prove that (A, B) is an almost-t-error correcting}

pair for C, let us verify that d(B⊥_{) > t}_{. We have}

d(B⊥) = n − t − k + 1 > t ⇐⇒ t ≤ d − 1 2 .

In other words, (A, B) is an almost-t-error correcting pair for C if and only if t ≤ d−1 2 , that

is our case.

Remark 2.3.11. Let us consider the key equations of Berlekamp-Welch algorithm: Λ(xi)yi= N (xi) ∀i ∈ {1, . . . , n}, (2.6)

where deg(N) = deg(Λ) + deg(f) ≤ t + k − 1. We wonder if there is a link between these equations and what we do in Error Correcting Pairs algorithm. Actually, if we consider the almost-t-error correcting pair we have found above, the codeword given by Λ(x) belongs to A(I). Furthermore we have

(Λ(x1), . . . , Λ(xn)) ∗ (c1, . . . , cn) = (N (x1), . . . , N (xn)),

where deg(N(x)) ≤ t + k − 1, hence (N(x1), . . . , N (xn)) ∈ B⊥. In other words, by the

almost-t-error correcting pair we have chosen, we give two codes A, B such that Λ(x) and N (x)give a codeword respectively of A and B⊥. This Remark will be useful in Chapter 3. Once we have I, if |I| < d − 1, then we can complete the algorithm by solving the linear system we talked about in the beginning of the section and we can find c. In fact, if |I| < d − 1, then this system will have an unique solution.

(20)

Algorithm 2:Error Correcting Pairs algorithm Data: y ∈ Fnq.

Result: I ⊆ {1, . . . , n}. If there exists c ∈ C and e ∈ Fnq such that y = c + e and

w(e) ≤ d−1₂ , then I is such that I ⊇ supp(e).

1 Compute ker(Ey);

2 I := {i ∈ {1, . . . , n} | ai= 0 ∀a ∈ ker(Ey)}; 3 return I;

is why we get as output I ⊇ supp(e). Theoretically, we may also have |I| > d − 1 (and that is why the algorithm can fail), but actually the probability to get that is very small. Complexity:

In this algorithm we have to

• find ker(Ey). We can do this by solving a linear homogeneous system of t+k equations

in t + 1 unknowns. We know that the cost to solve a linear system of m equations in nunknowns is O(nm min{n, m}). Hence, in our case the cost will be

O((t + 1)2(t + k)) = O((n − k))2(n + k),

roughly speaking, O(n3₎₎_;

• recover I. It is enough to find the zero columns of the matrix whose rows generate ker(Ey), which gives a cost O(n2);

• solve the system to find c as in Proposition 2.3.1. Again this is a system of at most n − k equations in at most n unknowns. Hence, we get O(n3₎_.

Roughly speaking, the complexity of the decoding algorithm which goes through Error Correcting Pairs algorithm, is O(n3₎_.

2.4 Beyond half the minimum distance

Until now, we have just considered algorithms for the unambiguous decoding problem. The uniqueness of the solution was entailed by the condition

t ≤ d − 1 2 .

Let us now consider C a code [n, k, d] and y = c+e where c ∈ C and e ∈ Fn

q with w(e) ≥ d−1

2 .

As before we want to find c again, but, seen this hypothesis on the weight of e (i.e. the radius of the problem), this time we want to do that by correcting more errors than we were used to do by Berlekamp-Welch and Error Correcting Pairs algorithms. By an algorithm which solves the list decoding problem, we are able to do it. Though we know that we may not have a unique solution. That is why the algorithms which solve the list decoding problem, may return a list of solutions. But, if we can increase the radius beyond the half of the minimum distance, is there a value better then another for it? Of course we would

(21)

like to correct as best as we can, but if we increase the radius too much we could find too many codewords. For example, if we set the radius r = n, our list would be equal to the whole code, that means that its cardinality would be exponential in n. The following result, known as Johnson bound, gives a condition to have a list of solutions with polynomial size in n.

Theorem 2.4.1. Let C ⊆ Fn

q be a code [n, k, d] with d = δn. We define the Johnson radius

as ρ := 1 −1 q 1 − s 1 − qδ q − 1 ! . For any y ∈ Fn q, we have |{c ∈ C | δ(c, y) ≤ ρn}| ≤ qdn.

Remark 2.4.2. Through this result we obtain lists of size O(qn2).

For the proof we refer to [11]. From now on then, we will try to correct up to ρn errors, and we will work with a Reed-Solomon code C = RS[n, k]. In this case ρn, for q → +∞, is

n(√1 − δ) = n −pn(n − d) = n −√nk − n. (2.7)

2.4.1 Sudan algorithm

Sudan has been the first one who tried to formulate an algorithm to correct more than d−1 2

errors (see [7]). First, we will present a different formulation of Berlekamp-Welch algorithm that will then lead to this generalisation naturally. Let h =d−1

2 and let us consider the key

equation

Λ(xi)yi= N (xi),

where deg(Λ) ≤ t and deg(N) ≤ t + k − 1. That means that the polynomial Q(x, y) := −N (x) + Λ(x)y

is such that Q(xi, yi) = 0 for all i ∈ {1, . . . , n}. Let us look at the degrees of N and Λ. We

know that this algorithm works whenever t < h, that means • deg(N) < k + t ≤ n − t;

• deg(Λ) ≤ t ≤ h = n − k − t < n − t − (k − 1).

An idea to generalise this algorithm would be then to consider a polynomial Q(x, y) = Q0(x) + Q1(x)y + · · · + Q`(x)y`

with ` ≥ 1 and such that

(i) deg(Qj(x)) < n − t − j(k − 1)for all j ∈ {1, . . . , `};

(22)

It is easy to verify that we obtain the Berlekamp-Welch case bounds for ` = 1.

Let us come back again to Berlekamp-Welch algorithm. Once we found N and Λ, we computed f = N

Λ. We want to do the same in the more general case, so we will focus on the

factors of Q(x, y) with degree 1 in y. Given `, our new algorithm becomes then: 1) find Q(x, y) satisfying (i) and (ii);

2) find linear factors (Aj(x)y − Bj(x))of Q(x, y);

3) for any j, if Aj|Bj, compute gj = Bj

Aj.

The following result proves that this algorithm works.

Proposition 2.4.3. Let Q(x, y) be a polynomial which satisfies (i) and (ii). If f ∈ Fq[x]<k

is such that δ(y, (f(x1), . . . , f (xn))) ≤ t, then

Q(x, f (x)) ≡ 0.

Proof. Let us study the polynomial Q(x, f(x)) = P`_i=0Qi(x)(f (x))i. Since Q fulfills (i),

then deg(Q(x, f(x))) < n − t. We want to prove that Q(x, f(x)) has at least n − t roots, that is, Q(x, f(x)) = 0. We know that Q(xi, yi)for all i = 1, . . . , n. Moreover we can define

J = {i ∈ {1, . . . , n} | f (xi) = yi}and we have |J| ≥ n − t. Therefore

yi= f (xi) ∀i ∈ J,

that means

Q(xi, f (xi)) = 0 ∀i ∈ J.

From this proposition, we have that whenever c ∈ RS[n, k] is such that δ(y, c) ≤ t and we have a polynomial Q(x, y) with the right properties, we can find our solutions by looking for the y-roots of Q (i.e. the roots of Px(y) = Q(x, y)where Px(y) ∈ Fq(x)[y]).

(23)

Algorithm 3:Sudan algorithm Data: y ∈ Fn

q, t ∈ Z+.

Result: {f1, . . . , fs} ⊆ Fq[x]<k such that δ((fj(x1), . . . , fj(xn)), y) < t for all

j ∈ {1, . . . , s}.

1 Compute Q(x, y);

2 f actors := [y-roots of Q(x, y)]; 3 list := [];

4 while p(x) ∈ f actors do

5 if p(x) ∈ Fq[x] and deg(p) < k then 6 f (x) := p(x); 7 c := (f (x1), . . . , f (xn)); 8 if δ(c, y) ≤ t then 9 list append (f); 10 end 11 end 12 end 13 return list; Decoding radius

We would like now to understand for which parameters this algorithm can work. First, let us study the possible values for `. Since we have deg(Qj) < n − t − j(k − 1), in particular

we get

n − t − `(k − 1) > 0, that is ` ≤ bn−t−1

k−1 c. Let us compute the amount of errors we can correct once we fix `. We

know that this algorithm works if and only if it is possible to find a Q(x, y) with the good properties. That is, we want the system to find Q(x, y) to have at least one solution. Since the key equations are

Q(xi, yi) = Q0(xi) + Q1(xi)yi+ · · · + Q`(xi)y`i = 0 ∀i = 1, . . . , n,

and deg(Qj) < n − j(k − 1) − t, we will have an homogenous system of n equations in `

X

j=0

n − t − j(k − 1) = (n − t)(` + 1) − (k − 1)`(` + 1) 2

unknowns. So a sufficient condition to have more than the zero solution, is to have more unknowns than equations, which gives

n < (n − t)(` + 1) − (k − 1)`(` + 1) 2 , (2.8) that is t < n` ` + 1− (k − 1)` 2 . (2.9)

(24)

Let us now do an asymptotic analysis, that is, let us look what happens if we consider a succession of codes with constant rate R but with length which tends to infinity.

Remark 2.4.4. Since we need x = (x1, . . . , xn) with xi 6= xj for any pair (i, j) such that

i 6= j, then n ≤ q. Hence, If we consider n → +∞, then also q → +∞. We will call τ = t

n. Now, we would like to obtain the longest possible list of solutions and

in order to do that we want to fix `. We observe that, once we fix `, our list will be at most `long, since we will have at most one solution for any factor of Q with nonzero degree in y. Since we have seen that ` ≤ bn−t−1

k−1 c, we take ` = b n−t−1

k−1 c. Hence, asymptotically

` ≈1 − τ R .

Therefore, if we divide (2.8) by n and we put n → ∞, we obtain τ . 1 −√2R, while we know that the Johnson bound (2.7) for Reed-Solomon codes is, dividing by n,

1 − √

R.

That means that we have not reached the optimal radius yet. Complexity

The algorithm is made by two main steps and a last check step:

• interpolation to find Q(x, y): as we have seen, this step can be computed my solving a linear system of n equations in

(n − t)(` + 1) − (k − 1)`(` + 1) 2

unknowns. If we take the biggest possible value for ` and we suppose that n−t−1 k−1 is an

integer, we have then

(n − t)2_{− 1}

2(k − 1) +

n − t + 1 2

unknowns, that gives, in the case we have more unknowns than equation, O n2 (n − t) 2_{− 1} 2(k − 1) + n − t + 1 2 = = O n2 _n2 2(k − 1)+ n 2 = = O n2 n 2_{+ kn} 2(k − 1) .

We have3 _{then O(n}3₎_;

• “factorisation” of Q(x, y): in fact what we do, it is to look for the factors of Q which are linear in y. That means that it is not necessary to compute a complete factorisation. This is possible by Newton method (see [8]) with a cost smaller than O(n3₎_.

3_{The result is not different if} n−t−1

(25)

• evaluation of the fi’s: since the list of polynomials is bounded by `, it gives a cost of

O(`nk).

Then the cost of the Sudan algorithm is O(n3₎_.

2.4.2 Guruswami-Sudan algorithm

Guruswami-Sudan algorithm is a generalisation of Sudan’s one and it is important in Coding Theory because, while Sudan algorithm just gets close to the Johnson bound, this new algorithm finally reaches it (see [9]). We remind the concept of multiplicity for a polynomial zero. Given a, b ∈ Fq, let us denote

Ia,b:= (x − a, y − b) ⊆ Fq[x, y].

This is a maximal ideal for Fq[x, y].

Definition 2.4.5. Given Q(x, y) ∈ Fq[x, y], we say that Q vanishes in (a, b) with multiplicity

m, if Q(x, y) ∈ Im a,b.

What we do to generalise Sudan algorithm, is to construct a polynomial Q(x, y) whose properties are a generalisation of the Sudan case ones. In fact we take

Q(x, y) = Q0(x) + Q1(x)y + · · · + Q`(x)y`

such that

(i’) deg(Qj) + j(k − 1) < m(n − t)for any j = 1, . . . , n;

(ii’) Q(xi, yi) = 0with multiplicity m for any i = 1, . . . , n.

As in Sudan case our algorithm will then follow the Berlekamp-Welch path. In other words, given ` and m, it will be made by the three steps:

1) find Q(x, y) which fulfills (i’), (ii’);

2) find linear factors (Ai(x)y − Bi(x))of Q(x, y);

3) for any j, if Aj|Bj, compute gj = Bj

Aj.

As for the Sudan case, we have a result which entails that this algorithm works and returns all the “good” solutions.

Proposition 2.4.6. Let Q(x, y) be a polynomial which satisfies (i’) and (ii’). If f ∈ Fq[x]<k

is such that δ(y, (f(x1), . . . , f (xn))) ≤ t, then

Q(x, f (x)) ≡ 0.

(26)

Decoding radius

Let us now show that Guruswami-Sudan algorithm reaches the Johnson bound. First we should fix m and `. From condition (ii’), given m, we have

m(n − t) − `(k − 1) > 0,

that is, ` ≤ bmn−t

k−1− 1c. Then, as in Sudan case in order to have the longest list of solutions,

we will set this value for `. Let us now see when our algorithm can work. We need the system to find Q to have a solution. Since we can write, for every i ∈ {1, . . . , n},

Q(x, y) =X

h,j

qhj(x − xi)h(y − yi)j,

and Q(x, y) vanishes in (xi, yi)with multiplicity m, we have to put qhj = 0for all h + j <

m. That means we have Pm−1_j=0 j = m(m−1)₂ conditions on the coefficients of Q. For the unknowns, since deg(Qi(x)) < m(n − t) − i(k − 1), we get

mn−t_k−1−1 X i=0 m(n − t) − i(k − 1) =m2(n − t)n − t k − 1− (k − 1) 2 mn − t k − 1− 1 mn − t k − 1 =m 2_{(n − t)}2 k − 1 − (m(n − t) − k + 1)m(n − t) 2(k − 1) =m 2_{(n − t)}2 2(k − 1) + m(n − t) 2 .

In order to have a solution, a sufficient condition is to have the number of equations smaller then the number of unknowns, that is

m(m − 1) <m 2_{(n − t)}2 (k − 1) + m(n − t) m(m − 1) /m 2_{(n − t)}2 (k − 1) (m − 1)(k − 1) m /(n − t) 2_. Let us call τ = t

n and divide both the sides by n 2_: 1 + m m /(1 − τ 2₎ R , that is, since τ ≤ 1,

τ / 1 − r

m + 1 m R.

Hence, when m tends to infinity we get τ < 1 −√R, that is the Johnson Bound. Complexity

Even if the algorithm is the same of the Sudan case, the new properties we need for Q give a bigger cost for its construction. Indeed, as we have seen, we have to solve a linear system

(27)

of O(m2₎ _{equations in O}m2_(n−t)2

2(k−1)

= O(m2_n) _{unknowns. So our system can be solved}

in O(m6_n)_{. Since we would like to reach the Johnson bound asintotically, we have to take}

a big m (m has to tend to infinity like nk). So if m = O(n2₎_{, then we have a final cost}

O(n13). Hence, even if theoretically this algorithm is very interesting for the properties of its decoding radius, from the practical point of view, it is not possible to push this radius to its maximum with a good time result.

2.4.3 The Power Decoding algorithm

Through Sudan and Guruswami-Sudan algorithms, we have studied the list decoding prob-lem. What happens though in most of the cases, is that the codes are not that “dense” in Fnq. That is, given y = c + e with c ∈ C, if w(e) is not very big, these algorithms return a list

not longer than one. We will now present the Power Decoding algorithm, which gives either one solution, or zero. As for the Sudan case, we can think at Power Decoding algorithm as a generalisation of Berlekamp-Welch algorithm. We will give a slightly different construc-tion from the one in [1], since we will talk about Reed-Solomon codes with a support not necessarily full (i.e. {x1, . . . , xn} ( Fq). Because of that, there will be a small difference

between the key system we obtain and the one of [1], but the results and the costs will be equivalent.

Let e(1)_{:= e = (e}

1, . . . , en)with w(e) = t and c = (f(x1), . . . , f (xn))with deg f < k. Let us

start by a remark. In Berlekamp-Welch algorithm we have worked with the key equations Λ(xi)yi= N (xi) ∀i = 1, . . . , n

and we got the bound

t ≤ n − k 2

from the sufficient condition n ≥ |var| − 1 (where |var| is the number of coefficients of Λ and N). It is reasonable then to think that we could have a larger bound by having more conditions on the coefficients of Λ and N.

Remark 2.4.7. Let us consider m such that m(k − 1) + 1 ≤ n: (i) if we denote

e(m):= y∗m− c∗m,

then we can see c∗m _{as an element of RS[n, m(k − 1) + 1] (see Proposition 1.2.8), and}

y∗mas a perturbation of c∗m with error e(m); (ii) we have supp(e(m+1)_{) ⊆ supp(e}(m)₎_{for any m ∈ N.}

Let us then take m such that m(k − 1) + 1 ≤ n, J = {j ∈ {1, . . . , n} | f(xj) 6= yj} and

Λ(x) =Q

j∈J(x − xj). Then, the star product between y∗mand (Λ(x1), . . . , Λ(xn))gives for

all i = 1, . . . n,

Λ(xi)yim=Λ(xi)(cmi + (e (m)₎

i)

(28)

where we used the (i) of Remark 2.4.7. Therefore our Λ has to fulfills this relation for any mand for any i ∈ {1, . . . , n}. Since, as for the Berlekamp-Welch case, these relations would not give a linear system, we linearise them and we get the weaker conditions for any m

Λ(xi)yim= Nm(xi) ∀i = 1, . . . , n, (2.10)

where Nm(xi) = Λ(xi)f (xi). Hence, our new problem is to find (˜Λ, ˜N1(x), . . . , ˜N`(x))such

that

• they fulfill 2.10 for any m ≤ `, for a certain ` such that `(k − 1) + 1 ≤ n; • deg(˜Λ) ≤ t;

• deg( ˜Ni) ≤ t + i(k − 1).

Algorithm 4:Power Decoding Algorithm Data: y ∈ Fn

q, t, ` ∈ Z+.

Result: f ∈ Fq[x]<k such that δ((f(x1), . . . , f (xn)), y) < t or “?”. 1 Compute the solution space S of 2.10;

2 if dim(S) = 1 then

3 ( ˜Λ, ˜N1, . . . , ˜N`) =non zero element of S; 4 f = N˜_˜1

Λ ; 5 return f;

6 end

7 return“?”

Remark 2.4.8. While in Berlekamp-Welch algorithm we had a result which ensured that any non zero solution would have given the right f, the Power Decoding case is unfortunately different. For sure, since (Λ = Qj∈J(x − xj), Λf, . . . , Λf`)fulfills the equations 2.10, it will

belong to the solution space S. Hence,

• if dimFq(S) = 1, we can recover our solution;

• if there exist c16= c2∈ C such that δ(ci, y) ≤ tfor i = 1, 2, then dimFq(S) ≥ 2and the

algorithm will not give any solution;

• a priori the algorithm may fail even if we have only one c ∈ C such that δ(y, c) ≤ t. We will focus on this problem in the next chapter.

Decoding Radius

Since we need deg( ˜Ni(x)) ≤ t + i(k − 1), we have to solve a homogeneous system of n`

equations in ` X i=0 t + i(k − 1) + 1 =(t + 1)(` + 1) + (k − 1)`(` + 1) 2 =t(` + 1) + (k + 1)`(` + 1) 2

(29)

unknowns. A necessary condition in order to have dim(S) ≤ 1, is to have |var| ≤ |eq| + 1, that is

t ≤ 2n` − `(` + 1)k + `(` − 1)

2(` + 1) . (2.11)

We will call this bound t[`] max.

Remark 2.4.9. Power Decoding algorithm gives some restrictions on the rate R of the code C:

• the larger the `, the smaller the rate. In fact, from the condition n > `(k − 1) − 1, we have

R < n + 1 n` +

1 n,

which is a quantity decreasing in `. Asymptotically we get R < 1 `;

• if we want t[1]

max< t[2]max, then we have to have

R < 1 3− 1 n, so the R < 1 3 is a necessary condition. The bound1

3 also comes from another remark. In fact, since we have the necessary condition

|eq| ≥ |var| + 1, then by taking ` = 2, we would like this condition to be fulfilled also for t ≥ n−k₂ . Therefore we put: 2n ≥ 3t + 3k − 1 ≥ 3n − 3k 2 + 3k − 1 and we obtain R ≤ 1 3+ 2 n. Asymptotically we get R ≤ 1 3.

Let us do now an asymptotic study for the decoding radius. From the condition of Remark 2.4.7, we get ` ≤ n−1

k−1, hence we fix ` to this bound. Condition 2.11 becomes

τ ≤ 1 − R 2(1 + R),

while for ` = 2 we obtain τ ≤ 2 3− R.

Complexity

The advantage of this algorithm is that we do not have to solve two steps, like we did instead in Sudan and Guruswami-Sudan algorithms. This case in fact, we just have to solve a linear system of ln equations in

t(` + 1) + (k + 1)`(` + 1)

2 = O(n`

2₎

(30)

0 0.2 0.4 0.6 0.8 1 0 0.2 0.4 0.6 0.8 1 R τ B-W S G-S PD l=2 PD l max Figure 2.3: comparison.

2.4.4 Comparison

Let us compare the Berlekamp-Welch (and Error Correcting Pairs), Sudan, Guruswami-Sudan and Power Decoding (with ` = 2 and ` = n−1

k−1) algorithms. In Figure 2.3 it is shown

the maximum value for τ, given R.

• We can see that it is not possible to apply Sudan algorithm for codes with rate R >

1

2. Though, as expected, for small rates

4 _{this algorithm corrects more errors than}

Berlekamp-Welch algorithm;

• As we have seen, the best algorithm in terms of decoding radius, is Guruswami-Sudan algorithm, even if it is the one with the biggest complexity among the algorithm we have presented;

• Power Decoding algorithm with ` = 2 can be applied only for R < 2

3, but it improves

Berlekamp-Welch algorithm5 _{for R <} 1 3;

• The R bound for Power Decoding algorithm with ` = 2 is bigger than the one of Sudan algorithm, hence it can be applied in more situations. Moreover it corrects more errors for big rates6_{. Though, the bounds for Berlekamp-Welch, Sudan and}

Guruswuami-Sudan algorithms come from sufficient conditions, while the one of Power Decoding algorithm comes from a necessary one. Hence, even if the decoding radius of Power Decoding algorithm is bigger than the one of Sudan algorithm, the solution is not guaranteed.

• We have that Power Decoding algorithm applied with the maximum value of ` does not improve Berlekamp-Welch algorithm for any vaule of R.

4_{For R < 3 − 2}√_2.

5_{As we have found previously.} 6_{For R >}4

3−

q

5 3.

(31)

Remark 2.4.10. We may then make a strategy in order to use the best algorithm (among the ones we have seen) for any situation

         Sudan 0 < R ≤ 4 3− q 5 3 Power Decoding ` = 2 4 3− q 5 3 ≤ R ≤ 1 3 Berlekamp-Welch 1 3 ≤ R < 1.

We get that it is possible to correct more than the unambiguous amount of errors (i.e. d−1 2 )

through the algorithms we have presented only for R < 1 3.

(32)

Chapter 3

Power error correcting pairs

In the previous chapter, we have presented two algorithms to solve the unambiguous decoding problem: the Berlekamp-Welch and the error correcting pairs. Moreover we presented some extensions for Berlekamp-Welch algorithm in order to correct more than half the minimum distance. What we want to do now, is to present this kind of extension for error correcting pairs algorithm too. In particular, in Remark 2.3.11 we have seen that, for Reed-Solomon codes, there is a link between the key equation of Berlekamp-Welch algorithm and the choice we made for the almost-t-error correcting pairs. For this reason, we have made this generalisation by focusing on Reed-Solomon codes and Power Decoding algorithm.

3.1 Small powers case

In order to present this structure, we will follow a constructive path. First, we will present the cases for power 2 and 3.

Power 2

Let us focus on the key equations of Power Decoding for l = 2: 

 

Λ(xi)yi = Λ(xi)f (xi) ∀i ∈ {1, . . . , n}

Λ(xi)yi2= Λ(xi)f2(xi) ∀i ∈ {1, . . . , n}.

As before, we replace these conditions by    Λ(xi)yi= N1(xi) ∀i ∈ {1, . . . , n} Λ(xi)y2i = N2(xi) ∀i ∈ {1, . . . , n}, (3.1) where deg(N1) ≤ t + k − 1 and deg(N2) ≤ t + 2k − 2. Now, since Λ(xi)ei = 0, (3.1) is

equivalent to:    Λ(xi)ci= N1(xi) ∀i ∈ {1, . . . , n} Λ(xi)c2i = N2(xi) ∀i ∈ {1, . . . , n}. (3.2)

(33)

By looking at this new system, we can now try to fix a new definition of “error correct-ing pair”. As for the base case, by an error correctcorrect-ing pair, we want to give two codes A, B such that Λ(x) and N1(x) give respectively two codewords of A and B⊥. Since

N2(xi) = N1(xi)f (xi)for all i ∈ {1, . . . , n}, then N2(x)has to give a codeword of B⊥∗ C.

So, for the moment we will use the hypothesis: (i) A ∗ C ⊆ B⊥ _{(⇐⇒ A ∗ B ⊆ C}⊥_);

(ii) A ∗ C∗2_{⊆ B}⊥_{∗ C} _{(but this condition follows from the first one);}

(iii) dim(A) > t.

Let us now consider a general linear code C and let us see which results we can reach with this new definition. We consider y = c + e(1)_{, where c ∈ C, supp(e}(1)_{) = I}

1and t1= |I1|. In

the first case, we studied the set

ker(Ey) = {a ∈ A | a ∗ y ∈ B⊥}.

We proved that, if d(B⊥_{) > t}

1, then ker(Ey) = A(I1). Now we do not want the same

hypothesis, since in the case of Reed Solomon codes the conclusion would be t1 < n−k₂ ,

while our aim is to correct more than this amount. However without d(B⊥_{) > t} 1, it is

difficult to have the property ker(Ey) = A(I1)again. That is why we define

M1={a ∈ A | a ∗ y ∈ B⊥},

M2={a ∈ A | a ∗ y∗2∈ B⊥∗ C}

and we consider a new set Ky = M1∩ M2. Given y = c + e(1) as above, we can define as we

did for the Power Decoding case

e(2)= (2e₁₁c1+ e121, . . . , 2e1ncn+ e12n) = y∗2− c∗2

and I2= supp(e(2)). Then we have y∗2= c∗2+ e(2). Let us consider a ∈ A and study the

two conditions in Ky, that is the sets M1and M2.

(a) For M1, we have the following equivalences

a ∗ y ∈ B⊥⇐⇒ ha ∗ y, bi = 0 ∀b ∈ B ⇐⇒ ha ∗ e(1)_{, bi = 0 ∀b ∈ B} ⇐⇒ ha, e(1)_{∗ bi = 0 ∀b ∈ B} ⇐⇒ haI1, e (1) I1 ∗ bI1i = 0 ∀b ∈ B ⇐⇒ aI1 ∈ (e (1) I1 ∗ BI1) ⊥

where we used that A ∗ C ⊆ B⊥ _{and supp(e}(1)_{) = I}

1. In other words, we have

M1= {a ∈ A | aI1 ∈ (e

(1) I1 ∗ BI1)

(34)

(b) For M2 we have a ∗ y∗2∈ B⊥_{∗ C ⇐⇒ ha ∗ y}∗2_{, γi = 0 ∀γ ∈ (B}⊥_{∗ C)}⊥ ⇐⇒ ha ∗ e(2)_{, γi = 0 ∀γ ∈ (B}⊥_{∗ C)}⊥ ⇐⇒ ha, e(2)_{∗ γi = 0 ∀γ ∈ (B}⊥_{∗ C)}⊥ ⇐⇒ haI1, e (2) I1 ∗ γI1i = 0 ∀γ ∈ (B ⊥_{∗ C)}⊥ I1 ⇐⇒ aI1 ∈ (e (2) I1 ∗ (B ⊥_{∗ C)}⊥ I1) ⊥

where we used that A ∗ C∗2_{⊆ B}⊥_{∗ C} _{and supp(e}(2)_{) ⊆ supp(e}(1)_{) = I}

1. That is, M2= {a ∈ A | aI1 ∈ (e (2) I1 ∗ (B ⊥_{∗ C)}⊥ I1) ⊥_}. If we call W = (e(1) I1 ∗ BI1) ⊥_{∩ (e}(2) I1 ∗ (B ⊥_{∗ C)}⊥ I1) ⊥_{, then we get} Ky = {a ∈ A | aI1∈ W }.

Remark 3.1.1. We have (Ky)I1⊆ W. Therefore, if W = 0, then (Ky)I1 = 0. That means

that we can have informations on I1 just by looking at the elements of Ky. Then, now our

aim is to find a condition to have W = 0, for istance we take the necessary condition dim((e(1)_I 1 ∗ BI1) ⊥_{) + dim((e}(2) I1 ∗ (B ⊥_{∗ C)}⊥ I1) ⊥_{) ≤ t} 1. (3.3)

Let us see what we can get from (3.3) in the Reed-Solomon case. We consider C = RS[n, k], c = (f (x1), . . . , f (xn))with deg(f) < k and y = c + e(1) with I1 and I2as before. As A and

B⊥ _{we take respectively RS[n, t}

1+ 1]and RS[n, t1+ k].

Remark 3.1.2. If t1>n−k₂ , then dim(B) = dim(e(1)∗ B)I1.

Indeed, let us consider the followings homomorphisms:

0 K B Ft1 q b (e(1)_{∗ b)} I1 ι (e(1)∗ ·)I1 where K = {b ∈ B | (e(1)_{∗ b)}

I1= 0}and ι is the immersion of K in B. We have that b ∈ K

if and only if bi = 0for all i ∈ I1but, since d(B) = t1+ k + 1, we have that this is possible if

d(B) ≤ n − t1, in other words if t1<n−k₂ . Since we want to correct more than n−k₂ errors,

we have K = 0 and hence dim(B) = dim(e ∗ B)I1.

We can finally see that

dim((e(1)_I 1 ∗ BI1) ⊥_{) = dim((e}(1)_{∗ B)}⊥ I1) = dim(((e(1)∗ B)I1) ⊥₎ =t1− dim(B) =2t1− n + k.

(35)

Let us now focus on dim((e(2) I1 ∗ (B

⊥_{∗ C)}⊥ I1)

⊥₎_{: if we consider again the homomorphism}

0 K (B⊥∗ C)⊥ Ft1 q γ _(e(2)_{∗ γ)} I1 ι (e(2)∗ ·)I1

we notice that the situation is different from the one in the previous case. In fact, we have K = {γ ∈ (B⊥∗ C)⊥| γi= 0 ∀i ∈ I2},

so if γ is an element of K, then w(γ) ≤ n − t2. Therefore we have that a necessary condition

for K to not be 0, is

d((B⊥∗ C)⊥) ≤ n − t2. (3.4)

Since we took B⊥ _{= RS[n, k + t}

1] and C = RS[n, k], from Proposition 1.2.7 we have

(B⊥∗ C)⊥ _{= GRS[n, n − 2k − t}

1+ 1], so d((B⊥∗ C)⊥) = 2k + t1 and the condition (3.4)

becomes

2k + t1≤ n − t2. (3.5)

Since I2= supp(e(2)) ⊆ supp(e(1)) = I1 we can study different cases:

(i) If I2= I1, then the condition (3.5) becomes

t1≤

n − 2k 2 .

Since, as before, we are supposing t1 > n−k₂ errors, we have that the condition (3.5)

can not hold and K = 0. That means that dim(e(2)_{∗ (B}⊥_{∗ C)}⊥_{) = dim((B}⊥_{∗ C)}⊥₎ I1.

We can conclude then dim((e(2)_I 1 ∗ (B ⊥_{∗ C)}⊥ I1) ⊥_{) = dim((e}(2)_{∗ (B}⊥_{∗ C)}⊥₎⊥ I1) = t1− dim((e(2)∗ (B⊥∗ C)⊥)I1) = t1− dim((B⊥∗ C)⊥I1) = 2t1+ 2k − n − 1. Finally, (3.3) becomes t1≤ 2n − 3k + 1 3

which is exactly the necessary condition to have solution for the Power Decoding with l = 2.

(ii) If t1> t2> n−2k+1₂ , then Condition (3.5) becomes

t1<

n − 2k − 1 2

but we have t1> n−k₂ > n−2k+1₂ by hypothesis, so we have the same result as in (i).

(iii) If t2≤ n−2k+12 , we come back to the first approach. In other words, we can consider

(36)

B1= B⊥∗ C. In fact we have that

d(B₁⊥) = 2k + t1>

n − 2k + 1 2 ≥ t2,

so we can find the support of e(2)_{, that is we can find f}2_(x)_{. Once we have that, we}

can look for f by factorisation for degrees or others (see Newton method [8]).

Remark 3.1.3. The third case tells us that if the support of e(2) decreases very much, we can just avoid a part of the problem, because the informations we have through the power 2, are enough. Moreover, if we are in the same situation with Power Decoding algorithm, we can notice that the bound t2≤ n−2k+1₂ is exactly the bound to correct in an unique way

a word in C∗2_{, since}

d(C∗2) − 1

2 =

n − 2k + 1 2 .

So, again, we can solve the problem by focusing on the derived problem with l = 2. This remark gives us a way to face a decoding problem:

1) Try to solve the problem for c∗2_{and find f(x) from f(x)}2_;

2) If (1) does not work, consider the whole problem. Power 3

Given C a linear [n, k, d] code, we will consider the same hypothesis we used in the Power 2 case:

(i) A ∗ B ⊆ C⊥_;

(ii) dim(A) > t.

We can observe that (i) implies A ∗ C∗2 _{⊆ B}⊥_{∗ C} _{and A ∗ C}∗3 _{⊆ B}⊥_{∗ C}∗2_{. We want to}

see if, also this case, we can find an interesting necessary condition for the error detecting problem. Let us consider y = c + e(1)_{, e}(2) _{as before, and}

e(3)= y∗3− c∗3

with I3= supp(e(3))and t3= |I3|. Let us define the sets:

M1={a ∈ A | ha ∗ y, bi = 0 ∀b ∈ B}

M2={a ∈ A | ha ∗ y∗2, αi = 0 ∀α ∈ (B⊥∗ C)⊥}

M3={a ∈ A | ha ∗ y∗3, γi = 0 ∀γ ∈ (B⊥∗ C∗2)⊥}

This time we are going to study the set:

(37)

In particular we would like that (Ky)I1= 0, as before. We have already seen that M1= {a ∈ A | aI1∈ (e (1)_{∗ B)}⊥ I1}, M2= {a ∈ A | aI1∈ (e (2)_{∗ (B}⊥_{∗ C)}⊥₎⊥ I1}.

Let us now study (M3)I1:

ha ∗ y∗3_{, γi = 0 ∀γ ∈ (B}⊥_{∗ C}∗2₎⊥_{⇐⇒ ha ∗ e}(3)_{, γi = 0 ∀γ ∈ (B}⊥_{∗ C}∗2₎⊥ ⇐⇒ ha, e(3)_{∗ γi = 0 ∀γ ∈ (B}⊥_{∗ C}∗2₎⊥ ⇐⇒ haI1, e (3) I1 ∗ γI1i = 0 ∀γ ∈ (B ⊥_{∗ C}∗2₎⊥ I1 ⇐⇒ aI1 ∈ (e (3) I1 ∗ (B ⊥_{∗ C)}⊥ I1) ⊥ We have then1 M3= {a ∈ A | aI1 ∈ (e (3) ∗ (B⊥∗ C∗2)⊥)⊥I1}.

Remark 3.1.4. As before we call W = (e1∗ B)⊥I1∩ (e

(2)_{∗ (B}⊥_{∗ C)}⊥₎⊥ I1∩ (e

(3)_{∗ (B}⊥_{∗ C}∗2₎⊥₎⊥ I1,

and we have that Ky = {a ∈ A | aI1 ∈ W }. In other words, Ky I₁ ⊆ W, so it is enough

to find a necessary condition in order to have W = 0. Now, this case we will consider the necessary condition

dim((e(1)∗ B)⊥_I₁∩ (e(2)_{∗ (B}⊥_{∗ C)}⊥₎⊥

I1) + dim((e

(3)_{∗ (B}⊥_{∗ C}∗2₎⊥₎⊥

I1) ≤ t1. (3.6)

Let us see what we can say in Reed-Solomon case. We take again C = RS[n, k], A = RS[n, t1+ 1]and B⊥ = RS[n, t1+ k]. However, it is difficult to recover all the dimensions

in (3.6). But we know that, given three vector space A, B ⊆ V with dim(V ) = t, then dim(A⊥∩ B⊥) ≥ t − dim(A) − dim(B).Hence, a necessary condition in order to have (3.6), is

t1− dim(e(1)∗ B) − dim(e(2)∗ (B⊥∗ C)⊥) + dim((e(3)∗ (B⊥∗ C∗2)⊥)⊥I1) ≤ t1. (3.7)

In order to compute this bound, we want to see if dim(e(3)_∗(B⊥_∗C∗2₎⊥_{) = dim((B}⊥_∗C∗2₎⊥₎_.

Let us suppose that t1> n−k₂ and t2> n−2k+1₂ (that is, we cannot use the base algorithm

case on c and neither on c∗2_{) and let us consider}

0 K (B⊥∗ C∗2₎⊥ Ft1 q γ _(e(3)_{∗ γ)} I1. ι (e(3)∗ ·)I1 1_{Since I} 3⊆ I1, we have ((e(3)∗ (B⊥∗ C∗2)⊥)I1) ⊥_{= ((e}(3)_{∗ (B}⊥_{∗ C}∗2₎⊥₎⊥₎ I1

(38)

We have that

dim(K) = dim((B⊥∗ C∗2₎⊥_{) − dim(Im((e}(3)_{∗ ·)} I1))

≥n − (3k + t1− 2) − t1,

so a sufficient condition to have dim(K) > 0, is to have t1<

n − 3k + 2 2 .

In our case, since t1>n−k2 we are never in this case, but we can see what happens when we

consider this bound for t3. In fact let us suppose that t3 > n−3k+2₂ . Then we observe that

x ∈ K if and only if w(x) ≤ n − t3, so a necessary condition for K 6= 0 is

n − t3≥ d((B⊥∗ C∗2)⊥) = t1+ 3k − 1. (3.8)

Then, if we suppose that K 6= 0, we have from (3.8) and the bound on t3:

t1≤

n − 3k 2

which is impossible. So K = 0 and dim(e(3)_{∗ (B}⊥_{∗ C}∗2₎⊥_{) = dim((B}⊥_{∗ C}∗2₎⊥₎_{. Therefore}

if t3>n−3k+2₂ , dim((e(3)∗ (B⊥∗ C∗2)⊥)⊥I1) = t1− n + (3k + t1− 2).

Condition (5.3.1) becomes finally

t1≤

3n − 6k + 3 4 ,

which is the bound for the Power Decoding with l = 3. Moreover, if t3 < n−3k+2₂ , we can

easily solve the problem, by applying the base algorithm to C∗3 _{and y}∗3_.

3.2 General case

Let us consider C a generic [n, k, d] code.

Definition 3.2.1. A couple (A, B) is a power t-error correcting pair, if • A ∗ B ⊆ C;

• dim(A) > t.

As in the previous case, given ` > 1 we can define Mi for i = 1, . . . , ` in the natural way,

and obtain    M1= {a ∈ A | aI1∈ (e (1)_{∗ B)}⊥ I1} Mi= {a ∈ A | aI1 ∈ (e (i)_{∗ (B}⊥_{∗ C}∗i−1₎⊥₎⊥ I1} i = 2, . . . , `. (3.9)

Decoding algorithms for Reed-Solomon Codes.

Dipartimento di Matematica

Corso di Laurea Magistrale in Matematica

Tesi di Laurea Magistrale

Decoding algorithms

for Reed-Solomon codes

Candidato:

Relatori:

Isabella Panaccione

Dott. Alain Couvreur

Prof.ssa Ilaria Del Corso

Controrelatore:

Dott. Massimo Caboara

Contents

Introduction

Chapter 1

Coding Theory

1.1

Error correcting codes

1.2

Reed-Solomon codes

0

0

Chapter 2

Known decoding algorithms

2.1

Context

2.2

Berlekamp-Welch algorithm

2.3

Error Correcting Pairs algorithm

2.3.1

The Reed-Solomon codes case

2.4

Beyond half the minimum distance

2.4.1

Sudan algorithm

2.4.2

Guruswami-Sudan algorithm

2.4.3

The Power Decoding algorithm

2.4.4

Comparison

Chapter 3

Power error correcting pairs

3.1

Small powers case

3.2

General case

₀