Kód bez čárky

V teoretické informatiky , a zejména v teorii kódů a také v bioinformatice a zejména v genetice , je čárka bez kódu (termín, který by se dalo přeložit jako „kód bez čárkou“) je blokový kód nebo jednotný kód. V které žádné slovo kódu není vnitřním faktorem součinu dvou slov kódu.

Kódy bez čárky jsou také známé jako „samosynchronizující blokové kódy“, protože k nalezení začátku kódového slova není nutná žádná synchronizace.

Historická motivace

Genetický kód se skládá z kodonů . Každý kodon je sekvence tří nukleotidů převzatých z „ abecedy “ čtyř písmen A, U, G, C ( adenin , uracil , guanin a cytosin ). Sada 64 možných kodonů tvoří jednotný kód. Každý z možných kodonů může syntetizovat jednu z 20 přirozeně se vyskytujících aminokyselin . Na začátku genetiky byla položena otázka, zda sada kodonů 20 aminokyselin je kód bez čárek ; ve skutečnosti je maximální počet prvků kódu bez čárek o délce 3 o 4 písmena přesně 20. Pokud by existovala bijekce mezi aminokyselinami a kodony, dekódování by bylo možné provést bez synchronizace. Ve skutečnosti tomu tak není.

Definice

Kód na abecedě je sada z neprázdných slov na taková, že jakýkoli produkt slov je jednoznačně započítat jako součin: formálně, pokud $NA$ $VS$ $NA$ $VS$

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

pro a poté ${\ displaystyle n, m \ geq 1}$ ${\ displaystyle c_ {i}, d_ {j} \ v C}$

n = m

a na všechno .

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

i

Další formulace vlastnosti spočívá v tom, že submonoid generovaný pomocí je volně generován pomocí , což je tedy základem submonoidu . Slova, která tvoří kód, se nazývají „slova kódu“, produktem slov kódu je „zpráva“. Pokud je abeceda v bijekci s , bijektivní funkce přirozeně zasahuje do morfismu, na kterém s jakýmkoli slovem na spojuje zprávu $C ^ *$ $VS$ $VS$ $VS$ $C ^ *$ $VS$ $B$ $VS$ ${\ displaystyle f: B \ až 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}}

Aplikace je „kódovací morfismus“, opačnou aplikací je „dekódování“. $F$ $f ^ {- 1}$

Jednotný kód nebo hromadné kód je kód, jehož všechna slova mají stejnou délku, která se nazývá délka kódu. Kód čárka bez je jednotný kód tak, aby žádný kódové slovo je vnitřní faktor produktu ze dvou kódových slov: Je-li na kódová slova , potom nebo je prázdné slovo. Golomb a. al. uveďte výslovně následující formulaci: pokud a jsou prvky kódu , pak jsou slova , ..., obsažena . ${\ displaystyle pcs = c_ {1} c_ {2}}$ ${\ displaystyle c, c_ {1}, c_ {2}}$ $p$ $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$

Velikost kódu bez čárek

Všechna slova v kódu bez čárek jsou primitivní . Velikost , to znamená, že počet prvků čárkami bez kódu délky se proto zvyšuje o počtu primitivních slov o délce , která je také počet neperiodických límce délky ; toto číslo se rovná $ne$ $ne$ $ne$

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

pro abecedu s písmeny k . Tady je funkce Möbius . Pokud si všimneme maximální velikosti kódu bez čárky o délce nad písmenovou abecedou , máme . Golomb a kol. prokázali, že existuje rovnost, pokud je délka slov kódu lichá a menší než 15; obecný případ prokázal Willard L. Eastman. Takže máme: $\ mu$ ${\ displaystyle W_ {k} (n)}$ $ne$ $k$ ${\ displaystyle W_ {k} (n) \ leq M_ {k} (n)}$ $ne$

{\ displaystyle W_ {k} (n) = M_ {k} (n) = {1 \ nad n} \ součet _ {d \ mid n} \ mu (d) k ^ {n / d}}

pokud je liché.

ne

Willard L. Eastman také dává algoritmus pro sestavení těchto kódů. Další algoritmus uvádí Robert A. Scholtz. Pro písmena a slova délky najdeme hodnotu 20, v souladu s domněnkou Cricka et. al. $k = 4$ $n = 3$

Knuth hovoří o prvním algoritmu ve své vánoční řeči. Eastmanův algoritmus vyvinul Knuth jako příklad ústupu . Existují odkazy mezi kódy bez čárek a sadami Hall a Lazard. Výsledek na maximum je falešný pro slova sudé délky a pro mohutnost kódu bez čárky sudé délky n nad k písmeny se nepředpokládá žádný vzorec .

Poznámky a odkazy

Slovo je vnitřním faktorem slova, pokud pro dvě neprázdná slova a . $X$ $y$ ${\ displaystyle y = sxy}$ $s$ $t$
Golomb a Gordon Welch .
(en) Univerzální kódy Commafree Donald Knuth (11. prosince 2015) Stanfordská Univerzita.
Knuth 2017 , s. 9-10.
Francis HC Crick , John Stanley Griffith a Leslie Orgel , „ Kódy bez čárek “, Sborník Národní akademie věd USA , sv. 43,1957, str. 416–421 ( číst online , přístup k 16. prosinci 2017 ).
Nejkrásnější nesprávné nápady ve vědě na Chemistry Blog
Eastman 1965 .
Scholtz 1969 .
Perrin a Reutenauer 2018 .

Bibliografie

Solomon W. Golomb , Basil Gordon a Lloyd R. Welch , „ Comma-free codes “, Canadian Journal of Mathematics , sv. 10,1958, str. 202–209 ( ISSN 1496-4279 , DOI 10.4153 / CJM-1958-023-9 , číst online ).
Willard L. Eastman, „ O konstrukci kódů bez čárek “, IEEE Trans. Informovat. Theory , sv. IT-11,1965, str. 263–267.
Robert A. Scholtz, „ Kódy bez čárek maximální a proměnné délky “, IEEE Trans. Informovat. Theory , sv. IT-15,1969, str. 300–306.
Donald E. Knuth, „Úvod do ústupu. ” , In The Art of Computer Programming , roč. 4. pre-fascicle 5b, Addison-Wesley,září 2017( číst online )

Související články

Externí odkaz

(en) Universal Commafree Codes , Donald Knuth (11. prosince 2015) Stanfordská Univerzita.