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 |

henk.hollmann@ut.ee |