Decoding Gabidulin Codes Using Module Minimization

Master's Thesis, 2015

83 Pages, Grade: 1,0



1 Introduction.. 3

2 Mathematical Fundamentals.. 5

2.1 Finite Fields.. 5

2.1.1 Prime Fields.. 5

2.1.2 Extension Fields.. 5

2.2 Linearised Polynomials.. 7

2.2.1 Operations on Linearised Polynomials.. 8

2.2.2 Properties of Linearised Polynomials.. 9

2.2.3 Modulo Minimal Subspace Polynomial.. 10

2.3 Ore Extension.. 11

2.3.1 Isomorphism of Linearised Polynomials and some Ore Extension.. 12

2.4 Modules and Module Minimisation.. 15

2.4.1 Modules.. 15

2.4.2 Module Minimisation.. 16

2.5 Determinant and Orthogonality Defect.. 17

2.5.1 Existence of a Determinant.. 18

2.5.2 Orthogonality Defect.. 19

3 Coding Theory Fundamentals.. 21

3.1 Reed–Solomon Codes.. 21

3.1.1 Hamming Metric.. 21

3.1.2 Encoding of Reed–Solomon Codes.. 22

3.1.3 Decoding of Reed–Solomon Codes.. 23

3.1.4 Interleaved Reed–Solomon Codes.. 25

3.1.5 Application of Interleaved Reed–Solomon Codes.. 27

3.2 Gabidulin Codes.. 29

3.2.1 Rank Metric.. 29

3.2.2 Encoding of Gabidulin Codes.. 29

3.2.3 Decoding of Gabidulin Codes.. 30

3.2.4 Interleaved Gabidulin Codes.. 34

3.2.5 Application of Interleaved Gabidulin Codes.. 38

3.3 Summary.. 39

4 Known Algorithms.. 41

4.1 Preliminaries.. 41

4.1.1 Complexity of Multiplication.. 41

4.1.2 Simple Transformation.. 42

4.2 Mulders–Storjohann Algorithm.. 46

4.2.1 Algorithm.. 47

4.2.2 Complexity.. 48

4.3 Demand–Driven Algorithm.. 49

4.3.1 Algorithm.. 50

4.3.2 Complexity.. 52

4.4 Summary.. 54

5 Alekhnovich’s Algorithm.. 55

5.1 Basic Algorithm.. 55

5.1.1 Correctness.. 57

5.1.2 Complexity.. 59

5.2 Accuracy Approximation of Polynomials.. 61

5.3 Improvement.. 63

5.3.1 Correctness.. 64

5.3.2 Complexity.. 66

5.4 Post–Computation.. 68

5.5 Summary.. 69

6 Regular Decoding Using Alekhnovich’s Algorithm.. 71

6.1 Sub–Quadratic Decoding.. 71

6.2 Importance.. 74

7 Conclusion.. 75

Notations.. 77

1 Introduction

Gabidulin codes are the rank-metric equivalent of the widely used Reed–Solomon codes. Gabidulin codes are considered for random linear network coding, as in [KK08], and public key cryptography systems, as in [BL05]. Especially the applica- tion of random linear network coding inspires the use of interleaving in this thesis.

While there are different decoding schemes for Gabidulin codes, module minimi- sation brings a more straight forward approach, allowing easier proofs and under- standing of the decoding process, and a generalised approach over a multitude of codes.

The goal of this thesis is to give an overview of the concept and add to it over gener- alised non–commutative polynomials and give a complexity estimate for the special case of Gabidulin codes. This is done by adding an algorithm to perform module minimisation over non–commutative polynomials and analysing its performance on decoding of (interleaved) Gabidulin codes.

Overview of the thesis

Chapter 2 introduces the necessary mathematical fundamentals used throughout the thesis. This includes an introduction to finite fields, linearised polynomials, Ore extensions and modules.

Chapter 3 gives a brief overview over the coding theory fundamentals of Reed– Solomon codes and, the main application of this thesis, Gabidulin codes.

In Chapter 4 two known algorithms for non–commutative polynomials are exam- ined: A review of the Mulders–Storjohann algorithm and the improved demand driven variant for decoding. This chapter also introduces the restrictions for the complexity analysis of the algorithms and common factors.

Based on the results of the previous chapter, inChapter 5 a divide and con- quer variant of Mulders–Storjohann, Alekhnovich’s algorithm, is converted to non– commutative polynomials. Alekhnovich’s algorithm is then analysed under the restrictions for decoding resulting in a much more detailed complexity for this problem.

Chapter 6 examines the implication of a sub–quadratic decoding algorithm for non–interleaved Gabidulin codes, based on the analysis done in Chapter 4.

Chapter 7 summarizes the analysis of Chapter 4 and its implications in Chapter 6.

2 Mathematical Fundamentals

This chapter consists of two parts. In the first part,Section 2.1 toSection 2.4 necessary mathematical tools for this thesis are introduced, starting with finite fields in Section 2.1. ThenSection 2.2 introduces linearised polynomials, a special ring of polynomials, which are further generalised to Ore extensions in Section 2.3. In Section 2.4 the concepts of modules and module minimisation are examined.


Excerpt out of 83 pages


Decoding Gabidulin Codes Using Module Minimization
University of Ulm  (Institut für Nachrichtentechnik)
Catalog Number
ISBN (eBook)
ISBN (Book)
File size
1992 KB
Coding Theory, Decoding, Encoding, Mathmatics, Algorithm, Alekhnovichs Algorithm, Gabidulin Codes, Reed-Solomon Codes
Quote paper
David Mödinger (Author), 2015, Decoding Gabidulin Codes Using Module Minimization, Munich, GRIN Verlag,


  • No comments yet.
Read the ebook
Title: Decoding Gabidulin Codes Using Module Minimization

Upload papers

Your term paper / thesis:

- Publication as eBook and book
- High royalties for the sales
- Completely free - with ISBN
- It only takes five minutes
- Every paper finds readers

Publish now - it's free