Kodowanie informacji

Kodowanie informacji dotyczy środków formalizowania informacji w celu ich obsługi, przechowywania lub przesyłania. Nie interesuje go treść, a jedynie kształt i rozmiar zakodowanych informacji.

Alfabet, słowo, języki

Definicje

Alfabet definiujemy jako niepusty zestaw symboli, na przykład:

• A = {a, b, c,…, z}, alfabet łaciński  ;
• A = {0,1,2,…, 9}, tak zwane cyfry arabskie
• A = {0,1,…, 9, A, B,…, F}, cyfry szesnastkowe .
• A = {0,1}, alfabet logiki Boole'a .
• A = {A, T, G, C}, czyli zasady DNA , które kodują nasz genom (ten alfabet jest głównym przedmiotem bioinformatyki ).

Wzywamy do nas elementem z alfabetu . Słowo
nazywane jest skończoną serią liter . Ciąg 0 liter nazywany jest pustym słowem , oznaczonym ε. Język nazywamy zbiorem słów związanych z pewnymi regułami interpretacji (bez tego ostatniego ograniczenia dowolną tabelę wartości losowych można by nazwać językiem ). W przypadku DNA reguły te zawarte są w rybosomie , w językach naturalnych zawarte są w ich leksykonie , w komputerze są obecne w obwodach jednostki centralnej .

Operacje

Niech będzie alfabetem i liczbą naturalną . Oznaczamy zbiór wszystkich słów o długości ponad i zbioru wszystkich słów . Mamy: ( zamknięcie Kleene ). Definiujemy operację konkatenacji , która wiąże słowo, które składa się z sekwencji liter z tego okresu . Przykład  : "marc" "et sophie" = "marc et sophie" (znaki cudzysłowu służą do oddzielania symboli, nie są elementami ). W{\ displaystyle A}nie{\ displaystyle n}
Wnie{\ displaystyle A ^ {n}}nie{\ displaystyle n}W{\ displaystyle A}W∗{\ displaystyle A ^ {*}}W{\ displaystyle A}
W∗=⋃nie≥0∞Wnie{\ Displaystyle A ^ {*} = \ bigcup _ {n \ geq 0} ^ {\ infty} A ^ {n}}
⋅:W∗×W∗→W∗{\ Displaystyle \ cdot: A ^ {*} \ razy A ^ {*} \ rightarrow A ^ {*}}(u,v){\ displaystyle (u, v)}w{\ displaystyle w}u{\ displaystyle u}v{\ displaystyle v}
⋅{\ displaystyle \ cdot}W{\ displaystyle A}

• Właściwości  :
  • ⋅{\ displaystyle \ cdot}jest asocjacyjny  :∀u,v,w∈W∗,(u⋅v)⋅w=u⋅(v⋅w){\ Displaystyle \ forall u, v, w \ w A ^ {*}, (u \ cdot v) \ cdot w = u \ cdot (v \ cdot w)}
  • ⋅{\ displaystyle \ cdot}dopuszcza ε jako element neutralny  :∀u∈W∗,u⋅ϵ=ϵ⋅u=u{\ Displaystyle \ forall u \ w A ^ {*}, u \ cdot \ epsilon = \ epsilon \ cdot u = u}
  • ⋅{\ displaystyle \ cdot}nie jest przemienna .

Kody i kody

Kodowanie

Niech L i M będą dwoma językami. C kodujący L wm to za pomocą wstrzyknięć (do pracy ) morfizmu . Innymi słowy, jest to zgodność między słowami L i M, gdzie każdemu słowu L jest przypisane unikalne słowo M i takie, że kodowanie połączonego jest równe połączonemu kodowaniu. ( ).
⋅{\ displaystyle \ cdot}∀u,v∈L,vs(u.v)=vs(u).vs(v){\ Displaystyle \ forall u, v \ w L, c (UV) = c (u). c (v)}

Kody

Język L nad alfabetem A jest kodem wtedy i tylko wtedy, gdy nie ma dwóch różnych rozkładów słów na słowa ze słowami L. W∗{\ displaystyle A ^ {*}}

Zastosowania, przykłady

• Kodowanie Manchester
• Kodowanie NRZ
• Kodowanie Millera
• Kod Baudota

Powiązane artykuły

• Wyciek informacji

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