Còdic unívocamente descodificable

Plantilla:Enmarañado Un còdic unívocamente descodificable és un tipo de còdic no-singular si qualsevol seqüència finita de signes de l'alfabet usat pel còdic és l'image de, com a molt, un mensage, és dir, la funció de codificació I és una funció inyectiva.

Definició formal

Còdic l'extensió del qual és no-singular. Siga A un alfabet font i B un alfabet còdic. Es diu funció codificadora a qualsevol funció. f: A+ -> B+. El còdic corresponent és Unívocamente Decodificable (UD) si f és inyectiva. Fa part de l'àrea de la matemàtica discreta i els algoritmes computacionals.

Una forma de calcular la millor llongitut mija és per mig de l'[[Inecuación de Kraft]]. L'idea bàsica és assignar llongituts majors a les paraules en menor provabilitat.

Per a aclarir tot açò, devem anar per passos:

1. Un còdic és una assignació de paraules còdic $w_i$, a una font d'informació ya siga de memòria nula o en memòria (font de Markov). Estes paraules còdic $w_i$, no són més que combinacions de símbols d'un alfabet $T$. Per eixemple: si tenim la següent font de memòria nula. $S=\{s_1,s_2,s_3\}$ i tenim el següent alfabet $T=\{0,1\}$, podem assignar el següent còdic a $S$, $C=\{0,10,11\}$. El còdic Del qual és U.D.
2. Pero que vol dir, en exactitut còdic Unívocamente Decodificable. Significa que qualsevol codificació que es realise en eixe còdic no deu ser ambigua és dir, un possible mensage de la font $0100\dots 11$ o qualsevol un atre, tinga una i solament una interpretació $s_1{s}_2{s}_1\dots s_3$, és dir carixca d'ambigüitat.
3. En efecte la Teorema de Patterson-Sardines nos ajuden a verificar si un còdic és U.D. o no, pero ací devem notar que per a demostrar que un còdic no és unívocamente decodificable, bastaria en trobar una cadena que siga ambigua.

Referències

Bibliografia

• Dominic Welsh (1988): Codes and Cryptography, Clarendon Press, Oxford, ISBN 0-19-853287-3

Enllaços externs

• Còdics Unívocamente Decodificables - Una aplicació en llínea que permet identificar un còdic unívocamente decodificable (UD) usant la teorema de Sardines-Patterson [1] archivat en Wayback Machine.