Comparing bounds on binary error-correcting codes
S.L.F. van Alebeek (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Jos Weber – Mentor
Dorota Kurowicka – Graduation committee member
DC Gijswijt – Graduation committee member
E.M. van Elderen – Graduation committee member
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
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.