Appunti Matematica discreta e codici

PRIMA PARTE

INTRO 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

(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

e dire in che modo migliora la situazione di udd

Potrei fare d(C) (minima distanza tra le parole del codice)

d(C) = 3

Aumentando la dim di codifica e scegliendo le parole di cod. distanziate migliora la situazione di decodifica.

Quindi: ci vuole un compromesso tra n grande (e C ⊆ F₂ⁿ) e velocità di trasmissione nel canale e di decodifica. Di tale compromesso si occupa la teoria dei codici

con le proprietà di compatibilità tra (✖) e (+) data dalla prop. DISTRIBUTIVA:

Distribuzione:

• (x+y)∙z = x∙z + y∙z
• x∙(y+z) = x∙y + x∙z
• ∀ x,y,z ∈ ℝ

Se ∙: ℝ×ℝ → ℝ (prodotto) è commutativo ⇒

l’anello (ℝ, +, 0_ℝ, ∙, 1_ℝ) si dice commutativo.

Esempi

1. (ℝ, +, 0, ∙, 1) è un anello commutativo
2. (ℂ, +, 0, ∙, 1) " " "
3. (ℚ, " " " " " )
4. (ℤ, " " " " " )

(_n,n(ℂ), +, \ , ∙, )

• Matrice quadrate a coeff complesse
• prodotto matriciale

Questo è un anello NON COMMUTATIVO (perché il prodotto matriciale, con n≥1, non è commutativo)

4. (ℤ₂=ℤ/2={0,1}, +, 0, ∙, 1) è un anello commutativo

somme mod 2

prod mod 2

• TRANSITIVA

(x, y) ∈ R

(y, z) ∈ R

⇒ (x, z) ∈ R, cioè

x ~_R y

y ~_R z

⇒ x ~_R z

Esempio S ⊂ ℤ, definiamo R come x ~_R y sse x - y è pari, x, y ∈ ℤ oppure sse x - y è multiplo di n ∈ ℤ.

Tali relazioni sono di equivalenza

Def. [Insieme quoziente per una rel. di equiv.]

Sia S insieme, R rel. di eq. su S.

Definisco INSIEME QUOZIENTE S/R (S/_R) :=

{Classi di R-equivalenza di elementi in S}

dove una CLASSE DI EQUIVALENZA di x ∈ S è

[x]_R := {y ∈ S | x ~_R y} ⊂ S

Quindi: S/R è un insieme i cui elementi sono particolari sottoinsiemi di S (le classi di equiv. in S)

Esercizio (1) Se x, y ∈ S e [x]_R = [y]_R

x ~_R y (usare prop. trans.)

DIM Se x ~_R y => ∀ z ∈ [x]_R y ~_R z => [y]_R = [x]_R

= [r⋅r'⋅r'']_I

Buona definizione di: r₁/I e ⋅R/I:

Supponiamo che r₂, r₂' ∈ R t.c. [r₂]_I = [r₂']_Ir₂', r₂'' ∈ R t.c. [r₂']_I = [r₂'']_I

devo mostrare che [r₂ + r₂']_I = [r₂ + r₂']_Icioè che (r₂ + r₂') - (r₂ + r₂') ∈ I =>

(r₂ + r₂') - (r₂ + r₂') = (r₂ - r₂') + (r₂' - r₂') ∈ I

Per esercizio verificare la moltiplicazione cioè che se cambio il rapp. della classe⋅R/I vale sempre

Contali: operazioni (R/I, +_R/I, ⋅_R/I, [0₂]_I, [1₂]_I) è un anello commutativo detto anello quoziente di R modulo I

ES: R = ℂ[x], I = (x) = {f⋅x⋅p(x) | p(x) ∈ ℂ[x]}

→ ℂ[x] → ℂ[x]/(x) è nella forma R/I

→ morfismo quoziente modulo I R/I → R/I è un morf di anelli

t.c. x ⋅ x^-1 = 1_R

Esempi Q, R, C sono campi.

F₂ = Z/2 = Z/(2) è un campo.

Z non è un campo: l'inverso moltiplicativo di 2 ad es. non c'è

R[x] non è un campo. Il suo inverso moltiplicativo non è un polinomio ma una funzione razionale

Z/(4) non è un campo. [2]₄⋅[2]₄ = 0_Z/4

[2]₄ ≠ [0]₄

=> no campo

• Nella biezione della lezione scorsa:

Ideali (R/I) { Ideali J ⊂ R Con J ⊇ I }

π^-1(-)

π (-)

π(I) = { [x]_I | x ∈ I } = (0_R/I) ideale nullo modulo R/I

Torniamo a F_p. #(F_p)=p. Abbiamo appena visto che esistono campi finiti con p elementi se p è primo.

Domanda: Esistono campi finiti con un numero non primo di elementi?

Teorema: [Esistenza e unicità dei campi finiti]

Sia q ∈ ℕ. Esiste un campo con q elementi sse q è una potenza di un primo: ∃ r ≥ 1 p primo t.c. q=p^r. Inoltre, se F_q e F_q sono campi finiti con q elementi (quindi q=p^r), esiste un isomorfismo d’anelli F_q ≅ F_q

□ Costruzione Sia q=p^r. Voglio costruire un campo F_q con q elementi. Considero l’anello dei polinomi F_p[x] (F_p è un campo)

(Proposizione: Se K è un campo (qualsiasi) allora l’anello K[x] è un anello ad ideali principali:

ideali principali:

Dim⇔: Sia I ⊆ K[x], I ≠ {0_K}.

☆ Scelgo in I\{0_K} un polinomio di grado minimo, lo chiamo f

CLAIM: I=(f)

Ovviamente I ⊃ (f) (f ∈ I e I ideale)

(es. g(x) = h₁(x) h₂(x) con h₁(x) = 1)

Esempio: K = ℂ x² = x × x (riducibile)

x²+1 = (x+i)(x−i) (riducibile)

con K = ℝ x²+1 (irriducibile)

Es: K = 𝔽₂: Lista polinomi di grado 2 in 𝔽₂

x², x²+1, x²+x+1, x²+x

riduc. riduc. irriducib.? riduc.

(x+1)² = x² + 1 + 2x

Vado a vedere se ha zeri: non ce n’ha!

Prop.: K campo, g ∈K[x], K[x]/(g) campo ⇔g è irriducibile, g ≠1 (g non costante)

Dim.: K[x]/(g) campo ⊃ (g) ideale max.

⇒ dimostro che g irrid. ⇔ (g) id. max

(1) g irriducibile ⇒ (g) ℑ K[x] è max.

(g) + K[x] ✓ (g non costante)

origina _GB = ^{( V₁ )} righe è una^{( V_k )} matrice k x n a coeff in K

Rango (_GB) = k (rango massimo)

Come ottengo tutte le basi di V ? (a partiredalla conoscenza della matrice G_B)

GL_{(K, K)} = {matrici k x k a coeff in Kgruppo lineare con det ≠ 0, cioè A^-1}

G L (k, K) : _GB = { A ∙ G | A ε GL (k, K) }^{k ⋅ n}

Rango(A ∙ _GB) = k (max)

Queste matrici (o meglio le loro righe) formanotutte le basi possibili di V.

Oss.

Sia C ⊆ ⁿ_q lineare, k := dim_q C, G unamatrice generatrice di C, H una una tricecp di C

1. Se x ∈ ⁿ_q allora : x ∈ C^⊥ <=> G ∙ x = 0x = (x₁, ..., x_n)[ Dfiniz è G = ^{( V₁ )} => G ∙ x^t = ^{( V₁ )} ](V_k) ^{( x_k )}

2. x ∈ C ⟺ H ∙ x^t = 0