Re: domande su alcuni esercizi

[Andrea Mercanti < >]

Ringrazio il Prof Bianchi per la risposta completa ed esaustiva, e per di più 
a tempo di record. Adesso ho un quadro più chiaro sui codici a blocco. Grazie 
Professore

Andrea Mercanti

 
Inviato da iPhone

Il giorno 02/lug/2011, alle ore 02:39, Giuseppe Bianchi 
<
 >
 ha scritto:

> 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...
>>>>> >
>>>> 
>>>> 
>