The shannon capacity on C(n,k)

Bachelor thesis (2022)

Authors

T.A. den Dulk Electrical Engineering, Mathematics and Computer Science

Contributors

Dion Gijswijt Discrete Mathematics and Optimization - EEMCS (mentor)
R.J. Fokkink Applied Probability - EEMCS (graduation committee member)
Faculty
Electrical Engineering, Mathematics and Computer Science, Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Timo den Dulk
More Info
expand_more

Published Date

12-07-2022

Language

English

Reuse Rights

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.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

This thesis focuses on a problem formulated by Claude Shannon named the Shannon capacity. This problem is about information rate per time unit over a noisy channel. The noisy channel is here represented by a graph. We specifically focus on a class of circulant graphs that are denoted by C(n,k) with vertex set z/nz, where all vertices are connected with the k-1 vertices before and after it. We will discuss upper bounds that were found for the Shannon capacity and how C(n,k) behaves with these upper bounds. After that we will focus on multiple ways to calculate lower bounds for the Shannon capacity of $C(n,k)$. For these three search methods will be used. These are exhaustive searching for optimal values, optimal ways to make packagings and solutions created by using a special form. As last the answers will be discussed by combining the upper and lower bounds for C(n,k). From this conclusions are drawn after which some possibilities will be given for further research.