Comparing bounds on binary error-correcting codes

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.