[frs_bis]

Re: domande su alcuni esercizi


Cronologico Percorso di conversazione 
  • From: Giuseppe Bianchi < >
  • To: Mercanti Andrea < >,
  • Subject: Re: domande su alcuni esercizi
  • Date: Sat, 02 Jul 2011 02:39:40 +0200
Premesso che ho studiato queste cose 23-24 anni fa, che sui codici a blocchi non ci ho mai lavorato, e quindi prendete quando segue con il beneficio del dubbio, mi sembra che la condizione sui codici BCH riportata nella slide (slide che sono andato a vedere, a scanso di equivoci) sia quella relativa all'ESISTENZA del codice stesso. E quindi la disuguaglianza e' corretta.

Per convincervi, e convincerMI ;-), provo a fare un esempio. Prendiamo il codice [15,5,3] di cui state dubitando dell'esistenza (giusto! Sempre dubitare di qualsiasi cosa vi viene detto!). Se capisco la notazione che state usando, stiamo parlando di un codice con n=15, k=5 (ovvero 10 bit di ridondanza e 5 di informazione), e 3 errori correggibili.

Il MINIMO numero di bit di ridondanza (meno di cosi' non c'e' trippa per gatti) NON e' quello scritto nella slide del BCH (ed e' qui che mi sembra sia emersa la confusione), ma e' quello generale espresso dalla condizione di Hamming, che ovviamente vale per QUALUNQUE codice a blocchi a prescindere da come si chiami. La condizione dice che

n-k >= Log_2 (somma combinazioni n su i, da 0 fino a 3) = Log2[1 + n + n(n-1)/2 + n(n-1)(n-2)/6]

Per n=15 viene

n-k >= Log2 (576) = 9.17

E questo mi dice che quindi il codice [15,5,3], avendo n-k=10 bit di ridondanza, e' comunque non assurdo, ma e' tecnicamente fattibile in quanto PER LO MENO rispetta il vincolo minimo dato da Hamming.

Ora, Hamming vi dice il meglio che potete fare se foste in grado di progettare un codice perfetto. Quando passiamo a parlare di BCH stiamo parlando di un condice REALE, quindi non necessariamente perfetto, anzi. Per i codici reali, non interessa sapere quale e' il numero minimo di bit di ridondanza (questo me lo diceva il limite precedente), ma al contrario, interessa sapere il numero massimo di bit in piu' da aggiungere in un codice COSTRUIBILE, ovvero e' importante capire quanto siano buoni (con 1 milione di bit di ridondanza aggiunti a 5 bit di informazione, anche il mio gatto saprebbe correggere 3 errori).

Ora, nel caso specifico di BCH, quello riportato nella slide e' un teorema importante che QUANTIFICA quanto un codice reale BCH puo' fare. In particolare, la slide vi dice che, a prescindere da come poi lo costruirete (cosa che non penso vi sia stata spiegata in quanto serve un po' di algebra), COMUNQUE ESISTE almeno un codice per cui la ridondanza e' minore di un dato valore.

Nel caso specifico, n=15 = 2^m-1 --> m=4; t=3, pertanto la disuguaglianza BCH dice che esiste sicuramente almeno un codice con un numero di bit di ridondanza

n-k  MINORE O UGUALE A t*m = 12

Ed a questo punto abbiamo finalmente capito che il codice che stiamo cercando avra' un numero di bit di ridondanza compreso tra un minimo di 10 (per la condizione di hamming) ed un massimo di 12 (per la disuguaglianza BCH). Quale sia il codice migliore, e come questo venga costruito, non potete saperlo con quello che avete studiato finora (penso). Ma sicuramente potete accettare, a questo punto, che sia proprio il codice [15,5,3] perche' ha un valore n-k=10, peraltro il migliore possibile! (siamo fortunati, perche' avremmo potuto trovare che il codice BCH in questo caso aveva 11 o 12 bit di ridondanza, ed invece ci viene detto che ne ha solo 10!!).

Spero di aver chiarito l'arcano (e di non avere scritto sciocchezze visto che sono a digiuno di codici a blocco da parecchio, non penso ma... non si sa mai ;-) - voi comunque dubitate sempre!)

At 23:09 01/07/2011, Mercanti Andrea wrote:
Però, effettivamente, stavo pensando che con la disequazione

n-k<= t*h

si arriva a dire che k, ovvero i bit informativi, possono essere quanti volgiamo per correggere t errori, infatti verrebbe fuori

k>=n-t*h (come ha fatto notare anche luca)

e la cosa è alquanto improbabile. Quindi mi viene da pensare che l'esempio fatto da Giaconi a lezione del codice BCH 15,5,3 sia totalmente sbagliato. E quindi anche la formula proposta sulle slide.

Infatti prendendo la formula con il verso opposto, ossia

n-k>=t*h

si ha che

k<n-t*h

La cosa così ha molto più senso, innanzi tutto è limitata da n, come è normale che sia, e poi k, ossia i bit informativi, diminuiscono all'aumentare degli errori da correggere. Infatti è anche logico che si debba usare più ridondanza e quindi, a parità di n, meno bit di informazione per correggere più errori. Inoltre oggi Giaconi per gli esercizi ha usato questa seconda variante(purtroppo no, nessuno gli ha fatto notare che sulle sue slide e a lezione aveva affermato il contrario -.-').

Quindi, in definitiva, nel mio piccolo, sono arrivato alla conclusione che la formula giusta è

n-k>=t*h

e che, sia l'esempio del codice bch (15,5,3) che la formula scritta sulle slide siano sbagliate.

Mi rivolgo al Professore Bianchi, che legge questa mailing list, se può darci una mano per risolvere definitivamente questo dubbio o, in alternativa, far presente al Professore Giaconi questa mail in modo che ci possa rispondere.

Mercanti Andrea

On 01 Jul, 2011,at 09:59 PM, Mercanti Andrea 
< >
 wrote:

Nella lezione extra fatta oggi da Giaconi pare che si sia affermato il contrario. Io non c'ero, quindi invito gentilmente qualcuno che ha assisto alla lezione a fare chiarezza. Anche perché, se quel (15,5,3) è un BCH realmente esistente non ci dovrebbero essere dubbi sul verso della formula.

Mercanti Andrea

On 01 Jul, 2011,at 09:43 PM, Luca Antonucci 
< >
 wrote:


dovrebbe essere n-k <= t*h e quindi k>= n - t*h

anche perchè se consideri BCH (15,5,3) applicando tale formula avresti k >= 15 - 12 e cioè k>=3 (infatti in questo caso prendiamo 5 considerando t*h=10)!

in caso contrario avresti avuto k<=3

Il giorno 01 luglio 2011 21:04, Alessandro Giordano <<mailto: > > ha scritto:
Scusate ma quindi qual è quella giusta? k >= n - ht oppure k < = n - ht? :D



2011/7/1 Mercanti Andrea <<mailto: > >
Sull'ultima parte ho qualche dubbio, in particolare sul verso della disequazione:

n-k > t*h

Sui miei appunti mi sono ritrovato quella disequazione scritta prima con un verso e poi con l'altro ma pensavo che fosse solo una mia disattenzione a lezione. Per verificare il verso giusto sono andato a ricercare la formula tra le slide di Giaconi, in particolare la formula giusta si trova nella slide 54 delle slide "<http://www.uniroma2.it/didattica/frs_bis/deposito/Giaconi-Codici.pdf>Codifica a controllo di errore".

la formula giusta risulta essere

n-k <= t*h  (sulle slide m è h)

Effettivamente, facendosi due conti, con la formula così scritta tornano i conti. Per esempio prendo un codice fatto a lezione

n=15 e h=4

1Errore  h*1=4                                            (15,11,1)
2Errori   h*2=8                                            (15,7,2)
3Errori   h*3=12  ma in questo caso n-k=10  (15,5,3)

quindi nel caso dei 3 errori n-k< t*h

Come si calcoli il k in questo caso particolare non è scopo del corso, e se capiterà in un esercizio verrà dato. Almeno così dovrebbe aver detto Giaconi

Se trovate qualcosa di sbagliato non esitate a contraddirmi

Mercanti Andrea

<mailto: >
Begin forwarded message:

From: Gabriele 
<<mailto: > >
Date: 01 July 2011 3:43:30 PM
To: <mailto: > ,Antonucci Luca 0094210 <<mailto: > >
Subject: Re: domande su alcuni esercizi



Per il primo dipende dai dati. Se hai i valori fissati di Capacità e Banda,
allora devi prendere 4.
Infatti l'utilizzazione del canale è il rapporto C/B. Con un valore come 3,8
se prendi 3 bit otterresti una banda più alta di quella che hai disponibile.
Se invece i dati sono diversi, devi diminuire, ma dipende dai casi.

Per il secondo dipende invece dal caso in cui lavori. Nel caso ideale, devi
utilizzare 2^n / [1+n+bin(n, 2)+...(un binomiale per ogni anello)] >= 2^k
Altrimenti nel caso reale utilizzi n = 2^(h) -1,
trovato h, se è un codice a correzione di 1 solo errore, fai
n - k = h

altrimenti
n - k > t*h (se n non è un numero primo)
oppure
n - k = t*h (se n è un numero primo)

--------------------------------------------------
From: "Antonucci Luca 0094210" <<mailto: > >
Sent: Friday, July 01, 2011 12:57 PM
To: 
<<mailto: > >
Subject: domande su alcuni esercizi

> salve ragazzi,
>
> qualcuno di voi può chiarirmi alcuni concetti riguardo gli esercizi della
> collezione di esami passati?
>
> Tipo:
> 1) quando mi viene chiesto di trovare la modulazione corretta immaginando
> di
> lavora a banda minima (Nyquist), se trovo [bit/simbolo] non intero come
> approssimo?? ad esempio se trovo 3,8 bit/simbolo prendo il valore 4 e
> quindi
> avrò una modulazione 16 QAM oppure prendo 3 e avrò una modulazione 8PSK
> (secondo me è questa ma ho il dubbio :))???
>
> 2) nei codici a blocchi quando devo trovare il valore di K, a seconda se
> devo
> rilevare (Dmin-1) oppure correggere (t) applico una delle due formulette e
> mi
> trovo rispettivamente per valore K=>n e k=<n. ma se devo prendere un
> numero
> preciso di k quando posso applicare la k<= n - t*h ???
>
> Vi ringrazio...
>





Archivio con motore MhonArc 2.6.16.

§