Informasjonskoding

Informasjon koding bekymringer hjelp av formal informasjon for å kunne håndtere, lagre eller sende det. Han er ikke interessert i innholdet, men bare i formen og størrelsen på informasjonen som skal kodes.

Alfabet, ord, språk

Definisjoner

Vi definerer et alfabet som et ikke-tomt sett med symboler, for eksempel:

• A = {a, b, c,…, z}, det latinske alfabetet  ;
• A = {0,1,2,…, 9}, de såkalte arabiske tallene
• A = {0,1,…, 9, A, B,…, F}, heksadesimale sifre .
• A = {0,1}, alfabetet til den boolske logikken .
• A = {A, T, G, C}, DNA- basene som koder genomet vårt (dette alfabetet er hovedfaget for bioinformatikk ).

Vi kaller et brev et element i et alfabet .
Et ord kalles en endelig bokstavserie .
Sekvensen på 0 bokstaver kalles det tomme ordet , bemerket ε.
Vi kaller språk et sett med ord som er knyttet til visse tolkningsregler (uten denne siste begrensningen kan en hvilken som helst tabell med tilfeldige verdier kalles språk ). Når det gjelder DNA, er disse reglene inneholdt i ribosomet , på naturlige språk, de er inneholdt i leksikonet , i en datamaskin , de er til stede i kretsene til den sentrale enheten .

Operasjoner

La være et alfabet og et naturlig tall . Vi betegner mengden av alle ordene i lengde i løpet av og settet av alle ord . Vi har: ( Kleene nedleggelse ). Vi definerer sammenkoblingsoperasjonen som knytter et ord som består av bokstavsekvensen fra den av . Eksempel  : "marc" "et sophie" = "marc et sophie" (anførselstegnene brukes til å avgrense symbolene, de er ikke deler av ). PÅ{\ displaystyle A}ikke{\ displaystyle n}
PÅikke{\ displaystyle A ^ {n}}ikke{\ displaystyle n}PÅ{\ displaystyle A}PÅ∗{\ displaystyle A ^ {*}}PÅ{\ displaystyle A}
PÅ∗=⋃ikke≥0∞PÅikke{\ displaystyle A ^ {*} = \ bigcup _ {n \ geq 0} ^ {\ infty} A ^ {n}}
⋅:PÅ∗×PÅ∗→PÅ∗{\ displaystyle \ cdot: A ^ {*} \ times A ^ {*} \ rightarrow A ^ {*}}(u,v){\ displaystyle (u, v)}w{\ displaystyle w}u{\ displaystyle u}v{\ displaystyle v}
⋅{\ displaystyle \ cdot}PÅ{\ displaystyle A}

• Egenskaper  :
  • ⋅{\ displaystyle \ cdot}er assosiativ  :∀u,v,w∈PÅ∗,(u⋅v)⋅w=u⋅(v⋅w){\ displaystyle \ for all u, v, w \ i A ^ {*}, (u \ cdot v) \ cdot w = u \ cdot (v \ cdot w)}
  • ⋅{\ displaystyle \ cdot}innrømmer ε som et nøytralt element  :∀u∈PÅ∗,u⋅ϵ=ϵ⋅u=u{\ displaystyle \ forall u \ i A ^ {*}, u \ cdot \ epsilon = \ epsilon \ cdot u = u}
  • ⋅{\ displaystyle \ cdot}er ikke kommutativ .

Koder og koder

Koding

La L og M være to språk.
A c- koding av L i M er en injiserende (for operasjonen ) morfisme . Med andre ord er det en samsvar mellom ordene til L og de til M, hvor hvert ord av L er assosiert med et enkelt ord av M og slik at kodingen av det sammenkoblede er lik det sammenkoblede av kodingene. ( ). ⋅{\ displaystyle \ cdot}∀u,v∈L,vs.(u.v)=vs.(u).vs.(v){\ displaystyle \ for all u, v \ in L, c (uv) = c (u) .c (v)}

Koder

Et språk L over et alfabet A er en kode hvis og bare hvis det ikke er to forskjellige faktoriseringer av ord med ord av L. PÅ∗{\ displaystyle A ^ {*}}

Søknader, eksempler

• Manchester koding
• NRZ-koding
• Miller koding
• Baudot-kode

Relaterte artikler

• Informasjonslekkasje

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">