Repeat-free codes

Organisatsiooni nimi
Coding and Information Transmission Group
Kokkuvõte
In this thesis topic we are going to investigate repeat-free codes. A word c of length n over a finite alphabet A is called (n,k) repeat-free if every word of length k occurs at most once as a subword of c. Here a word w=w_1w_2...w_k occurs in c at location i if c_{i+j-1}=w_j for j=1, ..., k. A collection C of words of length n over A is called an (n,k) repeat-free code over A if every word c in C is (n,k)-repeat-free. More general, a code C is called (n,k) (t+1)-repeat-free if in each code word, every word of length k occurs at most t times.
Some important questions are the following.

1. What is the number N_{n,k} of (n,k) repeat-free words of length n? And what is
the number N_{n,k,t} of (n; k) (t + 1)-repeat-free words?

2. How should we encode into repeat-free words?

Already the notion of a (t + 1)-repeat-free code seems new here.
The aim is to read some papers on this subject and then to investigate the above questions.
Lõputöö kaitsmise aasta
2022-2023
Juhendaja
Henk D.L. Hollmann, Vitaly Skachek, Ago-Erik Riet
Suhtlemiskeel(ed)
inglise keel
Nõuded kandideerijale
The topic is suitable both for a bachelor thesis and for a master thesis.
Some background in combinatorics would be helpful but is not required.
Tase
Bakalaureus, Magister
Märksõnad
#combinatorics, #graph theory

Kandideerimise kontakt

 
Nimi
Henk D.L. Hollmann
Tel
+31 619489142
E-mail
henk.hollmann@ut.ee