Project topics and materials
Get Complete Project Material File(s) Now! »
The Classical List Decoding Framework for Finite Rings
Context
In this part we extend the Guruswami-Sudan algorithm to generalized Reed-Solomon codes over nite rings with identity and we study its complexity. Let A be a nite ring with identity, A need not be commutative. We let A denote the units of A and Z(A) denote the center of A, all the a 2 A such that for all b 2 A, ab = ba. The construction of generalized Reed-Solomon codes over nite rings is a bit di erent than generalized Reed-Solomon codes over elds, in order to obtain maximum distance separable codes we must add two conditions on their support.
Definition. Let k < n be two positive integers and x = (x1; : : : ; xn) 2 An be such that for all i 6= j, xi xj 2 A (y) and xixj = xjxi (yy). The left submodule generated by the (f(x1); : : : ; f(xn)) 2 An; f 2 A[X] and deg f < k is called a Reed-Solomon code of parameters [n; k]A and denoted by RSA(x; n) or simply RS(n; k) when there is no confusion. The vector x is called the support of RSA(x; k).
Thanks to conditions (y) and (yy) the Reed-Solomon code of parameters [n; k]A has minimum distance n k + 1. When A is commutative condition (yy) is useless and when A is a nite eld we nd the classical de nition of Reed-Solomon codes (De nition 8).
Definition. Let k < n be two positive integers, v = (v1; : : : ; vn) be such that vi 2 Z(A) for all i and x = (x1; : : : ; xn) 2 An be such that for all i 6= j, xi xj 2 A and xixj = xjxi. The left submodule generated by the (v1f(x1); : : : ; vnf(xn)) 2 An; f 2 A[X] and deg f < k is called a generalized Reed-Solomon code of parameters [n; k]A and denoted by GRSA(v; x; n) or simply GRS(n; k) when there is no confusion. The vector x is called the support while v is called the weight of GRSA(v; x; k).
As for Reed-Solomon codes the minimum distance of GRS(n; k) is n k + 1. Gen-eralized Reed-Solomon and Reed-Solomon codes over the ring of matrices over a nite eld are considered for example in [BCQ12]. They have been studied when the base ring is commutative in [Arm04, Arm05b]. In this PhD thesis we focus on a particular family of rings called Galois rings.
Proposition. Let p be a prime and r; s two positive integers. Let ’(X); (X) 2 Z=prZ[X] be two degree-s monic polynomials irreducible modulo p. Then there is a ring isomorphism Z=prZ[X] = Z=prZ[X]:
(’(X)) ( (X))
The proof can be found in [Rag69, Statements I and II, page 207].
Definition (Galois rings). The ring Z=prZ[X] from the previous proposition is denoted (’(X)) by GR(pr; s) and called a Galois ring.
The name for Galois rings comes from the following fact whose proof can also be found in [Rag69, Proposition 2, page 213].
Proposition. Taking the same notation as the above de nition, the ring automorphisms of GR(pr; s) form a cyclic group of order s. (It is isomorphic to Gal(Fprs jFpr ).)
The decoding of generalized Reed-Solomon codes over Galois rings have been widely studied. The unique decoding is treated in [IPE97, Nor99, NSM00, BF01, BF02, Arm02, Arm05c] while the list decoding is investigated in [Arm04, Arm05b, Arm05a, AdT05]. Algebraic geometric over local Artinian rings have also been studied [Wal99a, VW99, WB08] as well as their list decoding [Bar06, WB08].
In fact, when working with nite rings with identity as alphabets for generalized Reed-Solomon codes, their niteness implies the following lemma which allows one to apply the Guruswami-Sudan algorithm over any nite ring as soon as one dispose of practical linear algebra algorithms over the latter.
Lemma. Let n < m be two positive integers and M 2 Mn m(A). Then there exists a nonzero v 2 Am such that M v = 0.
Proof. The matrix M induces a group homomorphism of Am ! An. Its kernel H is a subgroup of Am of cardinality at least jAjm n > 0.
When A is commutative, the previous lemma can also be proven with linear alge-bra techniques, see for example [Bro93, Chapter 5 and Corollary 5.9, page 39]. The Guruswami-Sudan algorithm for generalized Reed-Solomon codes over elds is consti-tuted of two parts. Thanks to the previous lemma it can be applied as is to generalized Reed-Solomon codes over nite rings and commutative rings.
Algorithm 2 Overview of the Guruswami-Sudan algorithm.
Input: A received word y 2 An and a decoding radius .
Output: All codewords c 2 An such that d(c; y) .
With linear algebra, nd a bivariate polynomial Q(X; Y ) 2 A[X; Y ] satisfying certain properties.
Find all the roots of Q(X; Y ) seen as a univariate polynomial of (A[X])[Y ].
The maximum decoding radius of the Algorithm can be computed in exactly the same way as in the case of nite elds. It will be shown in this thesis that n n(k 1) 1 is the maximum possible value for the Guruswami-Sudan algorithm, thus reaching the Johnson bound (De nition 15).
Contributions
Although there have been several papers concerning the unique decoding of generalized Reed-Solomon codes, and more generally other families of codes over rings, no detailed complexities is given. The situation is the same for list decoding. Only one interpolation algorithm is given in [Arm05b] with no complexity. Moreover no root nding algorithm is given. First, in Chapter 1 we give an interpolation algorithm for generalized Reed-Solomon codes over Galois rings and its complexity. It follows the same idea as the interpolation algorithm of [Ale05]. Then in Chapter 2 we give the rst root nding algorithm for the second step of the Guruswami-Sudan algorithm for generalized Reed-Solomon codes over Galois rings and its complexity. We rst give the rst algorithm for root nding of polynomials with coe cients in a local nite commutative ring. We then give an algorithm to nd the roots of bivariate polynomials with coe cients in a Galois ring.
Shortest Vectors in Polynomial Lattices Over Galois Rings and Application to List Decoding
This chapter contains the most recent results I obtained. It has not been submitted. It concerns the interpolation step of the Guruswami-Sudan algorithm and is included here for the completeness of this part of the PhD thesis.
Introduction
In this chapter we adapt the algorithm of [Ale05], which works over nite elds, over discrete valuation rings. Given a nite eld Fq and a lattice in Fq[X]n, the algorithm in [Ale05] gives in polynomial time the shortest vector of . The \norm » used here is the degree of the polynomial of greatest degree among all the components of a vector of . It is interesting to note that the nding of the shortest vector of a lattice in Fq[X]m can be done in polynomial time whereas, a priori, no polynomial time algorithm is known to nd the shortest vector of a lattice in Zm.
We follow the presentation given in Alekhnovich’s paper [Ale05]. We rst recall the de nition and properties of discrete valuation rings. Then we give a naive algorithm which computes the shortest vector of a lattice (A=( r))n where A is a DVR with uniformizing parameter . Finally we apply this algorithm to the Sudan list decoding algorithm for Reed-Solomon codes over A=( r).
Related work
Given a lattice in 0 Rm it is NP-hard [Ajt98] to nd a shortest vector. However in the early 1980s a polynomial time algorithm for nding a short vector in 0 was given in [LLL82]. The situation for polynomial lattices is much simpler. Let [X]m be a polynomial lattice over the eld . One can compute a shortest vector of in polynomial time [MS03]. In [Ale05] the author applies a shortest vector nding algorithm to the Guruswami-Sudan problem. Related work of shortest vector in polynomial lattices includes [GJV03, JV05, SV05, JV06].
Prerequisites
Complexity model
The \soft-Oh » notation f(n) 2 ~ O(1) (3 + g(n)). It O(g(n)) means that f(n) 2 g(n) log is well known [Fur07] that the time needed to multiply two integers of bit-size at most ~ n in binary representation is O(n). The cost of multiplying two polynomials of degree ~ at most n over a ring A is O(n) in terms of the number of arithmetic operations in A. ~
Thus the bit-cost of multiplying two elements of the nite eld Fpn is O(n log p).
Discrete valuation rings
Definition 51. A discrete valuation ring (DVR) is a principal ideal domain which has one and only one prime ideal m. Any element 2 A such that ( ) = m is called a uniformizing parameter of A. Let a 2 A be a nonzero element. The greatest integer i 2 N such that a 2 mi n mi+1 is called the valuation of a and denoted by v(a). We let v(0) = +1.
Definition 52. Let Zps be an unrami ed extension of Zp of degree s. Then Zps is a DVR with uniformizing parameter p [Ser62, Chapter 1]. Let r be a positive integer. Then the quotient ring GR(pr; s) := Zps (pr) is called a Galois ring.
Proposition 53. Let a; b 2 GR(pr; s). Then the product ab 2 GR(pr; s) can be computed with a number of O (s log s log log sr log p log(r log p) log log(r log p)) ~ or O(rs log p) bit-operations.
Proposition 54. Let Fq[[t]] be the power series ring over Fq. It is a DVR with uni-formizing parameter t. Let a; b 2 Fq[[t]]=(tr). Then the product ab 2 Fq[[t]]=(tr) can be ~ computed with a number of O(r log r log log r) or O(r) arithmetic operations in Fq.
Proof. Proposition 52 and 53 are in [GG03, Chapter 8].
Reed-Solomon codes over valuation rings
Let A be a DVR. Reed-Solomon codes over rings are de ned in a slightly di erent way than their eld counterparts. We let A[X]<k denote the submodule of A[X] consisting of all the polynomials of degree at most k 1 of A[X].
Definition 55. Let x1; : : : ; xn be elements of A such that xi xj 2 A 6 r i = j (where A is the group of units of A). The submodule of An generated by the vectors (f(x1); : : : ; f(xn)) 2 A n where f 2 A[X]<k is called a Reed-Solomon code over A. The n-tuple (x1; : : : ; xn) is called the support of the RS code.
Proposition 56. Let C be a RS code over A. Then C has parameters [n; k; d = n k+1]A.
Proposition 57. Let C be a RS code with parameters [n; k; d = n k + 1]A over a discrete valuation ring A with uniformizing parameter . Then C= rC is a RS code with parameters [n; k; d]A=( r) over A=( r). Moreover of (x1; : : : ; xn) is the support of C then (x1 mod r; : : : ; xn mod r) is the support of C= rC.
The decoding of Reed-Solomon codes over Galois rings have been widely studied. The unique decoding is treated in [IPE97, Nor99, NSM00, BF01, BF02, Arm02, Arm05c] while the list decoding is investigated in [Arm04, Arm05b, Arm05a, AdT05].
Proposition 58. Algorithm 3 and 4 work correctly as expected.
The proof of Proposition 58 follows exactly the same proof as in the nite eld case. See for example [Sud97b] and [GS98]. The only point that di ers concerns the existence of the polynomial Q(X; Y ) of step 3. But the following lemma allows us to use the same property as the one for matrices over commutative elds.
Lemma 59. Let n < m be two positive integers and M 2 Mn m(A). Then there exists a nonzero v 2 Am such that M v = 0.
Proof. The matrix M induces a group homomorphism of Am ! An. Its kernel H is a subgroup of Am of cardinality at least jAjm n > 0. It can also be proven with linear algebra techniques, see for example [Bro93, Chapter 5 and Corollary 5.9, page 39].
Informally speaking, note that the nding of Q (step 2 of Algorithm 3 and step 3 of Algorithm 4) can be seen as nding a vector of univariate polynomials with bounded degrees in a certain ideal.
Computing the shortest vector
Preliminaries
Until the end of this chapter, we let A be a DVR with uniformizing parameter be such that A=( ) is a nite eld and B = A=( r) for a positive integer r.
In Subsection 1.4.1 we will present how to reduce the interpolation step of the Guruswami-Sudan algorithm to Problem 60 by a suitable choice of the matrix M.
The naive algorithm
We let M be the B[X]-module (B[X])m for a xed integer m.
Definition 61. Let b 2 B. Then there exists a unique unit u 2 B and a non negative integer such that b = u . The integer is called the ltration of b. The ltration of 0 2 B is de ned to be +1. For an element ’ 2 B[X] we de ne the ltration of ’ to be the least ltration of the nonzero coe cients of ’. For an element f = (f1; : : : ; fm) 2 M the ltration of f is de ned to be the least ltration of the components of f.
Definition 62. For any element f = (f1(X); : : : ; fm(X)) 2 M, we de ne its degree deg f to be maxfdeg fi : i 2 f1; : : : ; mgg, its leading index LI(f) to be maxfi : i 2 f1; : : : ; mg and deg fi = deg fg and its leading coe cient LC(f) to be fLI(f).
The degree of 0 2 M is . If E is any subset of M non reduced to zero, we call a vector of minimal degree or shortest vector of E any nonzero vector a0 satisfying 8b 2 E; b 6= 0; deg b deg a0.
Definition 68. Let a 2 M. We say that a is -reduced if for any non negative integer we have either va = 0 or, LI( va) = LI(a) and deg( va) = deg a. Let E be a nite set of vectors of M. We say that E is X-reduced if for all a; b 2 E, a 6= b, we have LI(a) 6= LI(b). Finally, we say that E is reduced if E is X-reduced and each element of E is -reduced.
Example 69. Let B be the ring Z=22Z = Z2=(22). The vector (1; X) is 2-reduced while the vector (1; 2X) is not as we have 2 (1; 2X) = (2; 0).
Table of contents :
Introduction
I The Classical List Decoding Framework for Finite Rings
1 Shortest Vectors in Polynomial Lattices Over Galois Rings and Application to List Decoding
1.1 Introduction
1.1.1 Related work
1.2 Prerequisites
1.2.1 Complexity model
1.2.2 Discrete valuation rings
1.2.3 Reed-Solomon codes over valuation rings
1.3 Computing the shortest vector
1.3.1 Preliminaries
1.3.2 The naive algorithm
1.4 Application to list decoding of Reed-Solomon codes
1.4.1 Preliminaries
1.4.2 Application to the Sudan algorithm
1.5 Conclusion
2 Polynomial root nding over local rings and application to error correcting codes
2.1 Introduction
2.1.1 Application to list decoding
2.1.2 Complexity model
2.1.3 Our contributions
2.1.4 Related works
2.2 Algorithm with linear convergence
2.2.1 Local multiplicities
2.2.2 Representation of the set of roots
2.2.3 Naive local solver
2.2.4 Cumulative cost of steps 1
2.2.5 Cumulative cost of steps 2
2.2.6 Cumulative cost of steps 3
2.2.7 Cumulative cost of steps 4
2.2.8 Total cost of Algorithm 9
2.3 Faster algorithm with splitting
2.3.1 Quasi-homogeneous Hensel lifting
2.3.2 Quasi-homogeneous multifactor Hensel lifting
2.3.3 Local solver with splitting
2.3.4 Total cost of Algorithm 13
2.3.5 Implementation and timings
2.3.6 Cost analysis in higher dimension
2.4 Application to error correcting codes
2.4.1 Algorithm
2.4.2 Experiments
II A Lifting Framework for List Decoding over some Finite Rings
3 On Generalized Reed-Solomon Codes Over Commutative and Non-commutative Rings
3.1 Introduction
3.1.1 Our contributions
3.1.2 Related work
3.2 Prerequisites
3.2.1 Error correcting codes
3.2.2 Galois rings
3.2.3 Complexity model
3.3 Generalized Reed-Solomon codes
3.4 Unique decoding of generalized Reed-Solomon codes
3.4.1 Unique decoding over certain valuation rings
3.4.2 The Welch-Berlekamp algorithm
3.5 List decoding of generalized Reed-Solomon codes
3.5.1 List-decoding over certain valuation rings
3.5.2 The Guruswami-Sudan algorithm
3.5.3 Complexities for list decoding algorithms
3.6 Conclusion
4 A Lifting Decoding Scheme and its Application to Interleaved Linear Codes
4.1 Introduction
4.1.1 Our contributions
4.1.2 Related work
4.2 Prerequisites
4.2.1 Complexity model
4.2.2 Error correcting codes
4.2.3 Reed-Solomon codes over rings
4.3 Improved -adic lifting
4.4 Application to interleaved linear codes
4.5 Conclusion
III Related work on error correcting codes
5 On Quasi-Cyclic Codes as a Generalization of Cyclic Codes
5.1 Introduction
5.1.1 Context
5.1.2 First denitions
5.2 Properties of quasi-cyclic codes
5.2.1 The one-to-one correspondence
5.2.2 The generator polynomial of an `-quasi-cyclic code
5.2.3 A property of generator polynomials
5.3 Quasi-BCH
5.3.1 Denition
5.4 Decoding scheme for quasi-BCH codes
5.4.1 The key equation
5.5 Evaluation codes
5.5.1 Denition and parameters
5.5.2 New good codes
5.6 Conclusion
6 An algorithm for list decoding number eld codes
6.1 Introduction
6.2 Generalities on number elds
6.3 Decoding with Coppersmith’s theorem
6.4 Johnson-type bound for number elds codes
6.5 General description of the algorithm
6.6 Existence of the decoding polynomial
6.7 Computation of the decoding polynomial
6.8 Good weight settings
6.9 Conclusion
IV Implementation
7 Implementation within Mathemagix
7.1 Introduction
7.2 Overview of the C++ side of Mathemagix
7.2.1 The directory tree of Mathemagix
7.2.2 C++ classes and variants
7.3 The mgf2x package
7.4 The finitefieldz package
7.4.1 Prime elds
7.4.2 Extensions of nite elds
7.4.3 Variants available for ffe
7.4.4 Finite elds of characteristic 2
7.5 The quintix package
7.5.1 Prime Galois rings
7.5.2 Extensions of Galois rings
7.5.3 Galois rings of characteristic 2r
7.5.4 Implementation of univariate root nding over Galois rings
8 The decoding Library for List Decoding
8.1 Overview of decoding
8.1.1 Introduction and motivation
8.1.2 The implementation
8.1.3 Presentation
8.2 More details on decoding
8.2.1 The directory tree of decoding
8.2.2 The internals of the library
8.2.3 Customization of the library
8.2.4 Rings provided by default with the library
8.2.5 Implemented algorithms
8.2.6 Timings
Bibliography
