Technische Universiteit Delft
Slangcode
21 december 2006 door M&C
Promotie van dhr. L. Haryanto: "Constructing Snake-in-the-box Codes
and Families of such Codes Covering the Hypercube"
15 januari 2007 | 10:00 uur
plaats: Aula TU Delft
De heer L. Haryanto | Master of Science in Mathematics, V.S. van
Amerika
promotor | Prof.dr. A.J. van Zanten (U-Maastricht)
Constructing Snake-in-the-box Codes and Families of such Codes
Covering the Hypercube
Een slangcode is een lijst van binaire woorden van lengte n, zodanig
dat elk woord in precies één bitpositie verschilt van zijn opvolger in
de lijst. Bovendien verschillen elke twee woorden in de lijst in
tenminste twee bitposities, tenzij ze buren van elkaar zijn in de
lijst. De lijst wordt beschouwd als een cyclische lijst, hetgeen
impliceert dat het `eerste woord' de opvolger is van het `laatste
woord'. De twee hierboven genoemde definitieregels moeten in cyclische
zin geïnterpreteerd worden. Er is een aantal methoden bekend om zulke
codes te construeren.
Deze zijn alle van recursieve aard, dat wil zeggen dat slangen van een
zekere woordlengte n geconstrueerd worden uit slangen met woordlengte
m
In dit proefschrift wordt zo'n recursieve methode besproken en
enigszins gegeneraliseerd. In het resterende deel van het proefschrift
wordt een nieuwe methode ontwikkeld om slangen te construeren op een
rechtstreekse, dat wil zeggen niet-recursieve, manier. Omdat in deze
methode een lineaire algebraïsche code wordt gebruikt, hebben de
geconstrueerde slangen een extra soort structuur bovenop hun
eigenlijke `slangstructuur'. Iets preciezer gezegd, elk vierde woord
van de slang is een woord van de gebruikte lineaire code en dus heeft
een gedeelte van de slang (de `ruggengraat') de structuur van een
lineaire ruimte. Dank zij deze lineariteit zijn we in staat om een
gedeeltelijk antwoord te geven op een oud probleem van Erdös: Hoeveel
disjuncte slangen van dezelfde lengte zijn voldoende om alle binaire
woorden van lengte n te bevatten (`een overdekking van de hyperkubus
Qn')? Voor n = 2 is dit aantal gelijk aan 1 en voor 2
Bovendien levert deze methode, voor alle n > 2, concrete overdekkingen
van Qn met een grote symmetrie groep.
Meer informatie?
Voor inzage in proefschriften van de promovendi kunt kijken in de TU
Delft Repository op: repository.tudelft.nl. TU Delft Repository is de
digitale vindplaats van openbare publicaties van de TU Delft.
Proefschriften zullen binnen een paar weken na de desbetreffende
promotie in de Repository te vinden zijn.
Laatst gewijzigd: 21 december 2006