Informazione, Trasmissione e Codici a Protezione d'Errore - Formulario completo

spazio degli esiti:

Ω = un insieme i cui elementi si interpretano come possibili esiti di un esperimento

spazio degli eventi:

A(Ω) = un insieme di sottoinsiemi di Ω. A(Ω) = P(Ω), A(Ω) ha le seguenti proprietá:

1. Ω ∈ A(Ω)
2. Se A ⊆ A(Ω) allora A' = Ω \ A ∈ A(Ω)
3. ∀A_i ∈ A(Ω), ∪A_i ∈ A(Ω) e ⋂A_i ∈ A(Ω)

processo di Bernoulli:

p(B) = un triplo (Ω, A(Ω), ρ: A(Ω) → ℝ) dove

• A una numerabilitá di intersezione numerabili di T_i: 0:T_i
• T: t ≠ 0, s ∈ ai : ai ∈ β
• p(A(Ω) → ℝ)

eventi elementari di Bernoulli:

T₁ = {x ∈ Ω | x = 1} = "al lancio è uscita testa"

T₂ = {x ∈ Ω | x = 0} = "al lancio è uscita croce"

probabilitá:

P: A(Ω) → ℝ t.c. ∀P ∈ 1 e che

1. p(Ω) = 1
2. p(A) ≥ 0 ∀A ∈ A(Ω)
3. p(∪A_i) = p(A_i) + p(A_j) − ⋃ p(A_i) se A_i e A_j sono eventi disgiunti (i ≠ j) (A_i ⋀ A_j = ∅)

eventi indipendenti:

A e B si dicono indipendenti se p(A ⋀ B) = p(A) ⋅ p(B)

Se A e B sono disgiunti, A e B sono indipendenti se p(A) = 0 o se p(B) = 0

processo probabilistico Finito:

è un Teorema (Ω, A(Ω), ρ) dove

• Ω è un insieme finito di esiti possibili di un esperimento
• A(Ω) = P(Ω)
• Gli eventi sono tutti i sottoinsiemi di Ω
• p: P(Ω) → ℝ è una misura di prob.

probabilitá uniforme:

p: P(x) = → ℝ c. uniforme se p è l'unica misura di prob.

• p({x}) = 1/ ∀ x ∈ Ω Quindi, per un generico evento A ∈ P(Ω), si ha t.c. che p(A) = 1/n^{mod n}

Principio di inclusione/esclusione

ρ(A₁ ∪ ... ∪ A_h) = ∑_i=1^h (-1)^i-1 ∑_j=1 ρ(A_j₁ ∩ ... ∩ A_jm)

(Asu insiemi):

ρ(A₁ ∪ A₂) = ρ(A₁) + ρ(A₂) - ρ(A₁ ∩ A₂)

ρ(A₁ ∪ A₂ ∪ A₃) = ρ(A₁) + ρ(A₂) + ρ(A₃) - ρ(A₁ ∩ A₂) - ρ(A₁ ∩ A₃) - ρ(A₂ ∩ A₃) + ρ(A₁ ∩ A₂ ∩ A₃)

(Per esteso ρ(A₁ ∪ ... ∪ A_k) = ρ(A₁) + ... + ρ(A_k) - ∑_i≠j ρ(A_i ∩ A_j)

numero esiti di 6 lanci data. 6ⁿ

• #k-uple con ripetizioni con numeri da 1 a n: n^k
• #k-uple senza ripetizioni con num da 1 a n: (n)_k = ∏_i=0^k-1 (n-i)
• #sottomultimi di k elemtiti da un insieme di n elementi: (k)_n = (n!)/(k!(n-k)!) = (n_n)/k!

Formula di Stirling:

n! ≈ nⁿ e^-n √2πn è la formula approssimativa

n molto bene già per n>10

Formula di Stirling logaritmica: log(n!) ≈ log(nⁿ e^-n √2πn) = nlog(n) - n + 1/2 log(2πn)

da cui segue che log(n!) ≈ 1 + 1/2 log(2πn) ≈ 1 per h→+∞

• #di disposizioni di k palle indistinguibili in n cindrici: { n } = ( n )^k = (n+k-1)! / k! = (n-1)! / k!(n-k)! = [n-helper_k]

coefficiente multinomiale ( n ) = n / k₁! ... k_m-1!

dove k₁+...+k_m=n

proprietà coefficienti binomiali e di multinomiale:

• ( n ) = ( n-1 ) + ( n-1 )
• ( n ) = n / ( i )² = n
• { n } = { ( n ) }²
• = k_i+1 [ { ( n ) } ]
• = k { ( n ) } = Σ { ( n ) }
• { ( n ) }ⁿ ~ n + 1

partizione condizionata: Sia π una partizione e A un evento, allora π|A = {π_i ∩ A | π_i ∈ π} limitav. p(π_i|A) = p(π_i ∩ A) / p(A)

entropia condizionata di partizioni: Siano π e σ due partizioni. Allora H(π|σ) = Σ_σ p(σ_j) H(π|σ_j)

entropia condizionata di eventi: Sia π una partizione e A un evento. Allora H(π|A) = Σ_i p(π_i|A) ln [1 / p(π_i|A)]

entropia condizionata: H(X,Y|Y) = H(π|σ) = Σ_j p(y) p(x|y) ln [1 / p(x|y)]

entropia congiunta: H(X, Y) = H(π ∧ σ) = Σ_{i j} ρ(x = x_i ∧ y = y_j) ln 1 / p(x = i, y = j)

H(X, Y) = Σ_{x y} p(x) p(y) ln 1 / [p(x) p(y)] sse X e Y sono indip. = H(X) + H(Y)

proprietà dell’entropia: 1) H(p₁, ..., p_n) = H(p₁, ..., p_n + 0)

2) H(p₁, ..., p_n) con Σ p_i = 1 non dipende dell’ordine delle p_i.

3) H(p₁, ..., p_n) è continua

4) H(π|σ) = H(π) - H(σ) sse π è più fine di σ

teorema di unicità di H: H(p₁, ..., p_n) = Σp_i ln 1 / p_i

è l’unica funzione a meno di costanti moltiplicative, che soddisfa le n proprietà dell’entropia.

c.a. sufficiente con confidenza: S₁ ... S_m congiunzione di v.a. è sufficiente per X

per X = (X ... X_n) congiunzione di v.a. con confidenza 1 - ε sse ∃ A ⊆ Ω t.c.:

1) p(A) = 1 - ε

2) S₁ | A, ..., S_m | A è sufficiente per (X₁ | A, ..., X_n | A)

decodifica per sindromi. Sia y ∈ F₂^m, e palla: z = (y₀)

inducono di y abbiamo a disposizione un DB di parole

di Fⁿ: {x₂, x₂ ∈ F₂} t.c. ∀x∈Fⁿ, d(x₂, 0) = peso

min{d(x,ρ)∣ H(x, z) = 1} Allora y_dec = y + xz ∈ C

distanza minima = d(C) = min{d(x, x¹) ∣ x ≠ 0 e x ∈ C} ovvero

è minima distanza di 2 parole tra il codice C.

peso minimo = w(C) = peso minimo di C

• w(C) = min{d(x,ρ) ∣ x ≠ 0 e x ∈ C}
• se C è lineare allora d(C) = w(C)

massima numero di errori corretti con certezza: un dec.

corregge al massimo └──────────────┘ errori

distanza minima nel cubo di Hamming: d(C)_(4,7,2)≥3, quindi

corregge al massimo 1 errore.

entropia condizionata (formule nuove): H(X∣Y) = H(X, Y) - H(Y)

H(Y∣X) = H(Y, X) - H(X)

da cui si ricava che H(X^Y) = H(Y) + H(X∣Y)

= H(X) + H(Y∣X)

interferenze di mutua informazione: I(X∣Y) = H(X) - H(X∣Y) =

H(Y) - H(Y∣X)

che è la misura di indecisione di

incertezza da X ad Y sapendo Y