Kommafri kode

I teoretisk informatikk , og spesielt i kodeteori , og også i bioinformatikk og spesielt i genetikk , er en kommafri kode (et begrep som kan oversettes som "kode uten komma") en blokkode eller ensartet kode. som ingen ord i koden er en intern faktor i produktet av to ord i koden.

Kommafrie koder er også kjent som “selvsynkroniserende blokkoder” fordi det ikke kreves synkronisering for å finne starten på et kodeord.

Historisk motivasjon

Den genetiske koden består av kodoner . Hvert kodon er en sekvens av tre nukleotider hentet fra et " alfabet " med fire bokstaver A, U, G, C ( adenin , uracil , guanin og cytosin ). Settet med 64 mulige kodoner danner en enhetlig kode. Hver av de mulige kodonene kan syntetisere en av de 20 naturlig forekommende aminosyrene . Ved begynnelsen av genetikk ble spørsmålet stilt om settet med kodoner til de 20 aminosyrene var en kommafri kode ; faktisk er det maksimale antall elementer i en kommafri kode med lengde 3 med 4 bokstaver nøyaktig 20. Hvis det var sammenheng mellom aminosyrer og kodoner, kunne dekodingen gjøres uten synkronisering. Det er det faktisk ikke.

Definisjoner

En kode på et alfabet er et sett med ord uten ord på slik at ethvert produkt av ord fra blir unikt beregnet som et produkt: formelt, hvis $PÅ$ $VS$ $PÅ$ $VS$

{\ displaystyle c_ {1} c_ {2} \ cdots c_ {n} = d_ {1} d_ {2} \ cdots d_ {m}}

for og , da ${\ displaystyle n, m \ geq 1}$ ${\ displaystyle c_ {i}, d_ {j} \ in C}$

n = m

og for alt .

{\ displaystyle c_ {i} = d_ {i}}

Jeg

En annen formulering av eiendommen er at submonoid generert av fritt genereres av , derfor er det et grunnlag for submonoid . Ordene som komponerer en kode kalles "kodenes ord", et produkt av kodenes ord er en "melding". Hvis er et alfabet i Bijeksjon med en bijective funksjon strekker seg naturlig inn i en morphism av på som, med noen ord om kollegaer meldingen $C ^ *$ $VS$ $VS$ $VS$ $C ^ *$ $VS$ $B$ $VS$ ${\ displaystyle f: B \ til C}$ $B ^ {*}$ $C ^ *$ ${\ displaystyle w = b_ {1} \ cdots b_ {n}}$ $B$

{\ displaystyle f (b_ {1} \ cdots b_ {n}) f (b_ {1}) \ cdots f (b_ {n}}

Søknaden er en "kodende morfisme", den omvendte applikasjonen er "dekoding". $f$ $f ^ {- 1}$

En ensartet kode eller blokkode er en kode hvis alle ord har samme lengde, kalt lengden på koden. En kode med kommafri er en ensartet kode slik at intet kodeord er en intern faktor for produktet av to kodeord: Hvis det er for kodeord , er eller er det tomme ordet. Golomb og. al. gi eksplisitt følgende formulering: hvis og er elementer i koden , så er ordene , ..., i . ${\ displaystyle pcs = c_ {1} c_ {2}}$ ${\ displaystyle c, c_ {1}, c_ {2}}$ $s$ $s$ $a_ {1} a_ {2} \ cdots a_ {n}$ ${\ displaystyle b_ {1} b_ {2} \ cdots b_ {n}}$ $VS$ ${\ displaystyle a_ {2} \ cdots a_ {n} b_ {1}}$ ${\ displaystyle a_ {3} \ cdots a_ {n} b_ {1} b_ {2}}$ ${\ displaystyle a_ {n} b_ {1} b_ {2} \ cdots b_ {n-1}}$ $VS$

Størrelsen på en kommafri kode

Alle ordene i en kommafri kode er primitive . Den størrelse , det vil si antallet av elementer i en komma-fri kode av lengde blir derfor øket med antall primitive ord av lengde , som også er antallet periodiske krager i lengde ; dette tallet er lik $ikke$ $ikke$ $ikke$

M_k (n) = {1 \ over n} \ sum_ {d \ mid n} \ mu (d) k ^ {n / d}

for et alfabet med k bokstaver. Her er Möbius-funksjonen . Hvis vi noterer den maksimale størrelsen på en kommafri lengdekode på et bokstavalfabet , har vi det . Golomb et al. har vist at det er likhet hvis lengden på ordene i koden er merkelig og mindre enn 15; den generelle saken er bevist av Willard L. Eastman. Så vi har: $\ mu$ ${\ displaystyle W_ {k} (n)}$ $ikke$ $k$ ${\ displaystyle W_ {k} (n) \ leq M_ {k} (n)}$ $ikke$

{\ displaystyle W_ {k} (n) = M_ {k} (n) = {1 \ over n} \ sum _ {d \ mid n} \ mu (d) k ^ {n / d}}

hvis er rart.

ikke

Willard L. Eastman gir også en algoritme for å bygge disse kodene. En annen algoritme er gitt av Robert A. Scholtz. For bokstaver og ord med lengde finner vi verdien 20, i samsvar med antagelsen til Crick et. al. $k = 4$ $n = 3$

Knuth snakker om den første algoritmen i julepraten sin. Eastmans algoritme er utviklet av Knuth som et eksempel på backtracking . Det er koblinger mellom kommafrie koder og Hall-sett og Lazard-sett. Resultatet på maksimalitet er falskt for ord med jevn lengde, og ingen formel antas for kardinaliteten til en kommafri kode med jevn lengde n over k bokstaver.

Merknader og referanser

Et ord er en indre faktor i et ord hvis det er for to ord som ikke er imøtekommende og . $x$ $y$ ${\ displaystyle y = sxy}$ $s$ $t$
Golomb og Gordon Welch .
(no) Universal Codes Commafree Donald Knuth (11. desember 2015) Universitetet i Stanford.
Knuth 2017 , s. 9-10.
Francis HC Crick , John Stanley Griffith og Leslie Orgel , " Koder uten komma ", Proceedings of the National Academy of Sciences i USA , vol. 43,1957, s. 416–421 ( les online , åpnet 16. desember 2017 ).
De vakreste gale ideene innen vitenskap på Chemistry Blog
Eastman 1965 .
Scholtz 1969 .
Perrin og Reutenauer 2018 .

Bibliografi

Solomon W. Golomb , Basil Gordon og Lloyd R. Welch , “ Kommafrie koder ”, Canadian Journal of Mathematics , vol. 10,1958, s. 202–209 ( ISSN 1496-4279 , DOI 10.4153 / CJM-1958-023-9 , les online ).
Willard L. Eastman, " Om konstruksjon av kommafrie koder ", IEEE Trans. Informere. Teori , vol. IT-11,1965, s. 263–267.
Robert A. Scholtz, “ Maksimal og variabel lengde med kommafri koder ”, IEEE Trans. Informere. Teori , vol. IT-15,1969, s. 300–306.
Donald E. Knuth, “Introduksjon til backtracking. ” , In The Art of Computer Programming , vol. 4. pre-fascicle 5b, Addison-Wesley,september 2017( les online )

Relaterte artikler

Ekstern lenke

(en) Universal Commafree Codes , Donald Knuth (11. desember 2015) Universitetet i Stanford.