Benvenuto!
Accedi
o
registrati
.
13-12-2019, 06:53:57
Home
CDL Informatica
UniCT
CEA
Prof
Help
Search
Calendar
Login
Register
Forum Informatica Unict
»
LAUREA TRIENNALE (D.M. 270/04)
»
III anno
»
Reti di Calcolatori, 9 CFU
(Moderator:
Salvatore Riccobene
) »
hamming cambio formula ridondanza
Pages: [
1
]
Go Down
« precedente
successivo »
Print
Author
Topic: hamming cambio formula ridondanza (Read 3048 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
thedog
Apprendista Forumista
Offline
Posts: 160
hamming cambio formula ridondanza
«
on:
05-07-2011, 13:56:57 »
salve colleghi il mio dubbio e il seguente nella formula relativo alla ridondanza, che se non erro e per distanza hamming=3 come devo cambiarla per una distanza maggiore tipo 5??? cioè
con hammin per corregere e errori bisogna avere d=2e+1 mentre per rilevarli d=e+1 e fino a qui ok
ora considerando che avendo m bit dati e r bit di ridondanza sappiamo che la lunghezza tot della codeword e n=m+r
quindi per
codeworck ne abbiamo solo
valide quindi, per creare una codifica con m bit messaggio e r di controllo che ci permette di corregere gli errori singoli , per
messaggi legali ho bisogno di n+1 combinazioni di bit dedicate quindi
che poi sostituendo a n=m+r viene modificata....
ora se non ricordo male tale formula è per d=3 ovvero la minima distanza per corregere 1 errore, ricordo che il prof aveva detto che nel caso in cui d fosse superiore si doveva cambiare la formula...
Qualcuno potrebbe darmi una mano a capire come???
Logged
cock86
Forumista Eroico
Offline
Posts: 2.014
OM
Re:hamming cambio formula ridondanza
«
Reply #1 on:
05-07-2011, 22:53:54 »
prima una piccola domanda. Ti è chiaro a cosa servono questi calcoli?(te lo chiedo così in caso potrei provare a spiegarti)
Tornando a noi (n+1)2
m
sono il numero di parole in un codice a distanza di hamming pari a 3 (come dici tu). Questo viene dalle codeword lecite e da tutte le parole che stanno a distanza uno da una parola lecita. Se invece per esempio dovremmo correggere due errori, utilizzeremo un codice a distanza 5. Le codeword lecite saranno ancora 2
m
mentre quelle che vi stanno intorno questa volta saranno di più, per la precisione ancora n saranno le parole ad un passo, a due passi (cioè ad un passo da ognuna di queste) saranno (n-1)n, quindi sommiamo la parola lecita, più quelle ad un passo, più quelle a due passi, e viene fuori 1+n+(n(n-1)), queste dobbiamo moltiplicarle per il numero di parole lecite (come detto prima) 2
m
. Verrà fuori una disequazione simile alla precedente (da risolvere), ma che sta volta serve per i codici a distanza uguale 5 per la rilevazione di due errori.
dove n=m+r.
I calcoli poi continuano come nella prima.
Ovviamente lo stesso vale per i codici a distanza maggiore.
Logged
Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Fantius
Apprendista Forumista
Offline
Gender:
Posts: 378
Re:hamming cambio formula ridondanza
«
Reply #2 on:
16-02-2012, 11:22:07 »
è passato un pò di tempo però mi sta sorgendo un grosso dubbio!!! perchè a due passi è n(n-1) ??
Logged
cock86
Forumista Eroico
Offline
Posts: 2.014
OM
Re:hamming cambio formula ridondanza
«
Reply #3 on:
16-02-2012, 11:59:11 »
Perché al primo passo ne abbiamo n a distanza 1, per ognuna di queste n ce n'è saranno altre n a distanza 1 da quest'ultima, ma una di queste n, una è quella da cui iniziamo, per cui è a distanza 0 (dalla parola iniziale) e non 2 quindi non si conta, da qui viene n-1, per cui consideriamo n-1 per ogni n. Viene quindi n(n-1) a distanza 2. Spero di essere stato chiaro. Anche perché è passato un pò di tempo e i ricordi nella mia testa non sono lucidissimi.
Logged
Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Fantius
Apprendista Forumista
Offline
Gender:
Posts: 378
Re:hamming cambio formula ridondanza
«
Reply #4 on:
16-02-2012, 12:21:27 »
si penso di aver capito
grazie
Logged
cock86
Forumista Eroico
Offline
Posts: 2.014
OM
Re:hamming cambio formula ridondanza
«
Reply #5 on:
16-02-2012, 12:33:42 »
ma figurati!
Logged
Un "buon informatico" trova una soluzione ad ogni tipo di problema. Un "ottimo informatico" trova la soluzione più efficiente ad ogni tipo di problema! Non stancatevi di migliorare la vostra soluzione!
Mirkesx
Matricola
Offline
Posts: 23
Re:hamming cambio formula ridondanza
«
Reply #6 on:
11-07-2019, 11:12:06 »
Lo so che faccio necroposting, ma prima che qualche collega (come il sottoscritto) si imbatta in questo topic e legga quello che c'è scritto volevo fare una precisazione.
La logica di risoluzione di cock86 mi ha aiutato a capire come rispondere allo stesso quesito che si poneva Fantius, però è errato dire che le codewords a distanza due sono n*(n-1) questo perchè si conterebbero diverse codewords errate già contate precedentemente (esattamente ne contiamo il doppio).
La formula più corretta sarebbe n*(n-1)/2 ovvero combinazioni semplici di n elementi di classe 2 (o n-2 se preferite). Ogni volta che si fa il conto bisogna ignorare le codewords già contate precedentemente e con le combinazioni andiamo sul sicuro.
Si potrebbe generalizzare dicendo che:
1 parola corretta (Cn,0) ha n parole con distanza hamming = 1 (Cn,1), n(n-1)/2 parole con distanza hamming = 2 (Cn,2) e cosi via. Nel caso di risoluzione del doppio errore, la formula per il calcolo dei bit di ridondanza diventerebbe:
(Cn,0 + Cn,1 + Cn,2) * 2^m <= 2^n -> [1 + n + n*(n-1)/2 ]*2^m <= 2^n
Si sostituisce n = m + r e si svolgono i conti se si vuole esplicitare m e r.
Potete provare con la codifica a d=5 (minimo per correggere 2 errori) che consta delle due sole codewords 00000 e 11111. Quindi m = 1 e r = 4, perchè avremo 2 sole parole corrette e la restante parte parole non corrette.
n = 5 ovviamente. Ma è corretto dire che r deve essere 4?
Se sostituiamo alla formula su menzionata risulterà 32 <= 32 che è vera, confermando il ragionamento.
Se si provasse a scrivere tutte le possibili combinazioni di codici errati partendo da una codeword corretta (fino a distanza 2) si constaterebbe che le parole a distanza 2 non ripetute sono 10 (esattamente C5,2).
«
Last Edit: 11-07-2019, 11:34:45 by Mirkesx
»
Logged
Pages: [
1
]
Go Up
Print
« precedente
successivo »
Jump to:
Please select a destination:
-----------------------------
Area Ufficiale
-----------------------------
=> Annunci Ufficiali
=> Segreteria Didattica
=> Aiuto, proposte e commenti
=> Stages e progetti finali
=> C.O.F. Centro Orientamento e Formazione
=> Messaggi (d)agli amministratori del forum
-----------------------------
LAUREA TRIENNALE (D.M. 270/04)
-----------------------------
=> I anno
===> Architettura degli Elaboratori, 9 CFU
===> Elementi di Analisi Matematica, 12 CFU
===> Fondamenti di Informatica, 9 CFU
===> Matematica Discreta, 12 CFU
===> Programmazione 1, 9 CFU
===> Programmazione 2, 9 CFU
=> II anno
===> Algoritmi, 9 CFU
===> Basi di Dati, 9 CFU
===> Fisica, 9 CFU
===> Ingegneria del Software, 9 CFU
===> Inglese, 3 e 6 CFU
===> Interazione e Multimedia, 9 CFU
===> Sistemi Operativi, 9 CFU
=> III anno
===> Calcolo Numerico, 6 CFU
===> Formazione Numerica, 6 CFU
===> Introduzione all'Analisi dei Dati, 9 CFU
===> Metodi Matematici e Statistici, 6 CFU
===> Reti di Calcolatori, 9 CFU
===> Tecniche di Programmazione Concorrente e Distribuita, 9 CFU
===> Teoria dell'Informazione e Crittografia, 9 CFU
=> III anno - Materie a scelta (crediti liberi)
===> Computer Forensics, 6 CFU
===> Computer Graphics, 9 CFU
===> Digital Game Development, 6 CFU
===> GPGPU/CUDA, 6 CFU
===> Informatica Musicale, 6 CFU
===> LAP 1: programmazione C/C++ 6 CFU
===> LAP 2: Programmazione Android, 6 CFU
===> Sistemi Centrali, 6 CFU
===> Startup d'impresa e Modelli di Business, 6 CFU
===> Internet Security 9 CFU
===> Social Media Management, 6 CFU
=> Corsi disattivati - Vecchio curriculum
===> E-Commerce, 6 CFU
===> Legislazione Informatica, 6 CFU
===> Teoria della Computabilità, 9 CFU
-----------------------------
LAUREA MAGISTRALE
-----------------------------
=> I ANNO
===> Intelligenza Artificiale e Lab, 9 CFU
===> Algoritmi e Complessità, 9 CFU
===> Computer Vision, 9 CFU
===> Crittografia, 9 CFU
===> Fondamenti e Linguaggi per la Programmazione Distribuita
===> Inglese Scientifico, 3 CFU
===> Metodi analitici per l'informatica, 6 CFU
===> Metodi Matematici per l'Ottimizzazione (Corso Integrato), 12 CFU
===> Multimedia, 9 CFU
===> Sicurezza dei Sistemi Informatici 9 CFU
===> Computer Security, 9 CFU
=> II ANNO
===> Machine Learning 6 CFU
===> Teoria della Computabilità, 9 CFU
===> Analisi e Gestione dei Dati, 9 CFU
===> Compilatori, 9 CFU
===> Computazione Naturale e BioIspirata, 6 CFU
===> Introduzione alla Bioinformatica, 9 CFU
===> Linguaggi Formali e Applicazioni, 9 CFU
===> Logica Computazionale, 9 CFU
===> P2P & Wireless Networks, 9 CFU
===> Pattern Recognition, 9 CFU
===> Sistemi Distribuiti, 9 CFU
===> Sistemi dedicati e laboratorio, 9 CFU
===> Web Reasoning
=> Corsi disattivati - Vecchio curriculum
===> Fisica moderna per l'informatica, 6 CFU
===> Linguaggi di Programmazione, 9 CFU
===> Protocolli di Rete
===> Teoria dei Codici, 6 CFU
-----------------------------
Vecchi ordinamenti ad esaurimento
-----------------------------
=> Laurea Triennale (D.M. 509/00)
===> Algoritmi 1
===> Algoritmi 2
===> Basi Teoriche dell'Informatica
===> Economia Aziendale
===> Fisica 1, 6 CFU
===> Fisica 2, 6 CFU
===> Fisica 3
===> Formazione Analitica 1
===> Formazione Analitica 2
===> Formazione Discreta 1
===> Formazione Discreta 2
===> J2ME
===> Lab. Amministrazione di Sistemi
===> Laboratorio di Interazione
===> Modelli Matematici
===> Multimedia per Dispositivi Mobile
===> Progetto Software
===> Reti 1, 6 CFU
===> Sicurezza dei Sistemi Informatici 1
===> Sistemi Distribuiti 1
===> Teoria dei Grafi
===> Usabilità ed Estetica del Web
===> Web Programming
=> Laurea Specialistica (D.M. 509/00)
===> Algoritmi 3
===> Analisi Numerica
===> Complessità
===> Computabilità
===> Data analysis e management
===> Ingegneria del software 2
===> Linguaggi Formali
===> Metodi algoritmici per l'ottimizzazione combinatoria
===> Programmazione Funzionale
===> Reti di Calcolatori 2
===> Ricerca Operativa
===> Sistemi Distribuiti 2
-----------------------------
Dottorandi
-----------------------------
=> Wall
=> Events
-----------------------------
Area Studenti
-----------------------------
=> Agorà
=> L'angolo del tecnico
=> Il Mercatino degli studenti
=> Software
===> -vecchia catalogazione [sarà rimossa a breve]-
=====> Proprietario
=====> Free Software
=====> Open Source
===> Approfondimenti
===> News
===> Studio
===> Videogiochi
===> Networking e telecomunicazioni
===> Sviluppo
===> Ufficio e produttività
===> Sistemi Operativi
=====> Microsoft Windows
=====> GNU/Linux, Unix e BSD
=====> Mac OS X
=====> Windows Phone
=====> Android
=====> iOS
=====> Altri
===> Eventi, conferenze, concorsi
=> Microsoft Student Partner - Avvisi e informazioni
=> ERASMUS/borse di studio internazionali
Caricamento in corso...