Appunti Matematica discreta e codici

Problema della decodifica

Introduzione al problema della decodifica

Notazioni

• Def: definizione
• Oss: osservazione
• Dim: dimostrazione
• CLAIM: sta per "affermo che" all'interno di una dimostrazione
• Es: esempio
• ★, *, (.) usati come etichette

Messaggio sorgente
Rumore
Messaggio ricevuto
Codifica di sorgente
Trasmissione canale di comunicazione
Decodifica di ricezione

* codifica primaria
** decodifica secondaria

Esempio:
SUD <-> 00
NORD <-> 10
EST <-> 01
OVEST <-> 11
In questo caso supponiamo che Codifica = Decodifica.

Questo canale implicitamente è un'applicazione F₂² -> F₂² con F₂ = Z/2. Per ridurre il Rumore, bisogna agire su cod. e dec.

Esempio di trasmissione

Trasmetto SUD = 00. Se il rumore altera < 1 bit, non ci sono errori. Se il rumore altera < 2 bit, ci sono possibili messaggi ricevuti. Quindi con tale codifica e decodifica:

• a) Non riesco a segnalare possibili errori in trascrizione [NO ERROR DETECTION]
• b) Non riesco nemmeno a correggerli [NO ERROR CORRECTION]

Soluzione

Aggiungo una codifica/decodifica

Codifica (-):
Posso enumerare i bit:
00 ↔ 000
10 ↔ 101
01 ↔ 011
11 ↔ 110
Aggiungo un terzo bit di ridondanza, somma dei precedenti. Questa è un'applicazione da F₂² a F₂³.

Decodifica (⋅⋅)
L'unica decodifica valida in generale (per tutti i canali) senza ulteriori info sul canale + rumore è la DECODIFICA A MINIMA DISTANZA (mdd).

Distanza di Hamming
d((x₁, x₂, x₃), (y₁, y₂, y₃)) = # i | x_i ≠ y_i
x_i, y_i ϵ F₂

Esempio: d((100), (011)) = 3, d((100), (110)) = 1

A questo punto, mdd: Se ricevo y ϵ F₂³, decodifico y ⟶ x dove x ϵ C ⊆ F₂³ + Cd (y, x) = min d (y, x') x' ϵ C Codice, insieme di parole, C ϵ F₂³.

Esempio: NORD ⟶ (101) ⟶ CANALE ⟶ y = 101 ϵ C 100 ➔ (C 111 001⟶ min ((101, x') x' ϵ C)

Ora mi accorgo che 3 dei risultati non stanno nel codice (che abbiamo definito prima)

• (1) Mi accorgo che c'è stato almeno 1 errore
• (2) Non posso però correggere univocamente l'errore, poiché esistono più elementi del codice che realizzano la moda fra y e gli elementi del codice (per es. 000, 101 ∈ C)

Esercizio

Che succede se l'errore è ≤ 2 bits? Idea: usare

• 00 ↔ 00000
• 01 ↔ 01111
• 10 ↔ 10110
• 11 ↔ 11001

C ⊆ ℱ₂⁵ e dire in che modo migliora la situazione di decodifica. Potrei fare d(C) (minima distanza tra le parole del codice): d(C) = 3. Aumentando la dimensione di codifica e scegliendo le parole di cod. distanziate, migliora la situazione di decodifica. Quindi: ci vuole un compromesso tra n grande (e C ⊆ ℱ₂ⁿ) e velocità di trasmissione nel canale e di decodifica. Di tale compromesso si occupa la teoria dei codici.

Definizioni

(1) Un alfabeto A è un insieme finito A = {a₁, ..., a_q} q = # (A) si dice TAGLIA dell'alfabeto.
Notazione: A_q è un alfabeto con #(A) = q. Gli elementi di A si dicono lettere dell'alfabeto.

(2) Un codice di lunghezza n è un sottoinsieme C ⊂ A_qⁿ = A_q × A_q × ... × A_q (n volte) e #(C) si dice TAGLIA DEL CODICE: #(C) ≤ qⁿ.

(3) Distanza di Hamming (in A_qⁿ)
d(x, y) = # { i ∈ {1, ..., n} | x_i ≠ y_i }
x = (x₁, ..., x_n) ∈ A_q^h y = (y₁, ..., y_n) ∈ A_qⁿ

Proprietà

1. 0 ≤ d(x, y) ≤ n
2. d(x, y) ≤ d(x, x') + d(x', y) disuguaglianza triangolare
3. d(x, y) = d(y, x)
4. d(x, y) ≥ 0 ∀ x, y e d(x, y) = 0 s.s. se x = y

Def. Se C ⊂ A_qⁿ ⇒ si dice distanza del codice d(C) = min { d(x, x') | x, x' ∈ C, x ≠ x' } (minima distanza fra 2 elementi del codice).

Def. Se y ∈ A_qⁿ ⇒ d(y, C) = min { d(y, x) }