Application to the Sudan algorithm

For more info about our services contact : help@bestpfe.com

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