Comparing bounds on binary error-correcting codes

Comparing bounds on binary error-correcting codes

van Alebeek, Sanne (TU Delft Electrical Engineering, Mathematics and Computer Science; TU Delft Delft Institute of Applied Mathematics)

Weber, Jos (mentor)
Kurowicka, Dorota (graduation committee)
Gijswijt, Dion (graduation committee)
van Elderen, Emiel (graduation committee)

Delft University of Technology

2017-03-24

This bachelor thesis is about binary error-correcting codes. A binary code is a collection words with the same length n that consists only of zeroes and ones. The error-correcting quality of a code is determined by the Hamming distance d of a code. A classical question in coding theory is: What is the maximum number of codewords in a code with length n and Hamming distance d? This maximum is denoted with A(n,d). Determining A(n,d) is quite difficult and often we have to make due with lower and upper bounds on A(n,d). In this thesis we compare six different bounds for finding an upper bound on A(n,d), give a detailed description of each bound, a proof and a clarifying example. The main focus of this thesis lies on the linear programming bound (with extra constraints). For d=4 we dive deeper into the linear programming bound and the Krawtchouck polynomials it uses. Finally we draw some conclusions from the comparisons of the different types of bounds.

error-correcting
linear codes
bounds
binary codes
linear programming bound
hamming
plotkin
singleton
johnson
delsarte

http://resolver.tudelft.nl/uuid:4659424f-ee9c-482d-8799-064a60686459

Student theses

bachelor thesis

© 2017 Sanne van Alebeek