 |
Scriviamo ora un programma che, calcolata una codifica di Hammng, verifiche ed eventualmente
corregga un codice.
Il testo dell'esercizio è il seguente:
Scrivere un programma C che legga da tastiera un numero tra 1 ed 8 (controllare l'input) e
calcoli una codifica ad 8 bit che rispetti la distanza di Hamming data (qualunque codice abbia
distanza di Hamming uguale o superiore a quella data con qualunque altro).
Costruire il codice in un array di interi, che contenga solo i codici validi della codifica.
Leggere poi un codice ad 8 bit (controllare l'input) e verificare se appartiene alla codifica.
In caso contrario verificare se e' correggibile e, nel caso proporre la correzione.
Suggerimenti
- Inizialmente l'array dei codici conterra' solo il codice di partenza (lo 0)
Esamineremo poi uno ad uno tutti gli altri codici (da 1 a 255).
Calcoleremo la distanza di Hamming con tutti i codici gia' accettati,
vale a dite tutti i codici presenti nel vettore.
Se la distanza e' maggiore o uguale alla data in tutti i casi, il
codice esaminato e' buono e lo inseriremo nell'array.
- Per individuare se il codice e' correggibile, occorre verificare che ci sia un solo codice
valido con la distanza minima. Per fare questo si può modificare l'algoritmo di ricerca
del minimo. Useremo una variabile contatore che conterrà il numero di codici con distanza
minima. Prima del confronto per minore, confrontare se la distanza del codice corrente
è uguale al minimo. Nel qual caso incrementeremo il contatore. Nel successivo confronto,
se la nuova distanza e' inferiore al minimo corrente, imposteremo ad uno il contatore, ad
indicare che si e' trovato per ora non più di un valore minimo
Una possibile soluzione è la seguente:
// Tizio - Pinco - 3°AIN - 22/03/2002
// Calcola la distanza di Hamming tra due char con correzione
#include<stdio.h>
#define DIM 8 /* serve la conversione in binario */
#define DIM1 256 /* vettore in cui memorizzo i valori aventi distanza di H. */
/* desiderata */
void ntob2(int n,int vet[]); // converte un numero da int a binario
int disth(int n1,int n2); // calcola la distanza di Hamming tra due vettori bit a bit
int codici(int hamm[],int dist);// genera i numeri aventi la distanza di Hamming passata
// in ingresso
main()
{
int i; // Indice per i cicli
int n; // Numero di codici nella codifica
int hamm; // Distanza di Hamming richiesto dall'utente
int flag; // Flag per interrompere il ciclo
int c; // Codice inserito
int d=10; // Distanza di hamming minima
int corr; // Codice con distanza di Hamming minima
int l; // Quanti codici hanno distanza uguale al minimo
int vet[DIM1]; // Codice di riferimento calcolato
// prende in input la distanza di Hamming
do {
printf("Distanza di Hamming = ");
scanf("%d",&hamm);
} while (hamm<1 || hamm>DIM);
n = codici(vet,hamm); // Calcola la codifica
// Stampa il codice prodotto
for(i=0;i<n;i++)
{
printf("%4d",vet[i]);
}
printf ("\n");
// prende in input il numero da controllare ed eventualmente da correggere
do {
printf("\nCodice: ");
scanf("%d",&c);
}while (c<0 || c>255);
// controllla che il numero non si già presente tra quelli generati
for(i=0, flag=0; i<n && flag==0;i++)
{
if(vet[i]==c)
{
printf("%d appartiene alla codifica\n",c);
flag=1;
}
}
// nel caso in cui il numero sia diverso controlla se lo si può correggere
if(flag==0)
{
printf("%d non appartiene alla codifica\n",c);
for (i=0;i < n;i++) // Analizza tutti i codici della codifica
{
if(d==disth(c,vet[i])) // Se la distanza e' uguale al minimo calcolato
{
l++; // Conta quanti codici hanno la stessa distanza
}
if(d>disth(c,vet[i])) // Se la distanza e' inferiore al vecchio minimo
{
d=disth(c,vet[i]); // La distanza corrente e' il nuovo minimo
corr=vet[i]; // Il codice corrispondente e' il relativo minimo
l = 1; // E ne ho trovato uno solo
}
}
if(l > 1) // Se ho piu' di un minimo
{
printf("Non e' possibile correggere %d\n",c);
} else { // Se invece il minimo e' uno solo
printf("Correzione di %d: %d\n",c,corr);
}
}
}
/* converte un numero da int a binario
* Un bit per ogni elemento dell'array, il piu' significativo nel primo elemento
*/
void ntob2(int n,int vet[])
{
int i; // Indice del bit nel vettore
for (i = DIM; i-- > 0;) // Scandisce gli elementi dall'ultimo al primo
{
vet[i]=n%2; // Immagazzina il bit meno significativo nell'elemento corrente
n=n/2; // Poi scarta questo bit
}
}
/* calcola la distanza di Hamming tra due codici bit a bit
* Prima di tutto converte i due codici in 'vettori di bit'
* quindi calcola la distanza
*/
int disth(int n1,int n2)// genera i numeri aventi la distanza di Hamming passata in ingresso
{
int vet1[DIM],vet2[DIM]; // I due 'vettori di bit
int i; // L'indice del bit
int dist=0; // La distanza calcolata
// Converte i codici in 'vettori di bit'
ntob2(n1,vet1);
ntob2(n2,vet2);
for(i=0;i<DIM;i++) // Per ogni bit del codice
{
if(vet1[i]!=vet2[i]) // Se i bit sono diversi
{
dist++; // Li conta
}
}
return dist; // Restituisce la distanza calcolata
}
/* genera i numeri aventi la distanza di Hamming passata in ingresso
* Usa l'algoritmo del precedente esercizio.
* Ritorna il numero di codici che appartengono alla codifica
*/
int codici(int hamm[],int dist)
{
int i; // Codice corrente
int cont;
int j;
int n; // Numero di codici inseriti nella codifica
hamm[0]=0; // Inizializza il primo codice (lo 0)
n=1; // e conta i codici introdotti (per ora uno)
// Per ogni codice possibile oltre il primo
for(i=1;i<DIM1;i++)
{
// Per ogni codice gia' inserito, se la distanza sbaglia, termina
for (j=0; disth(i,hamm[j])>=dist && j<n; j++)
;
if(j==n) // Se ha passato tutti i test (e' arrivato in fondo)
{
hamm[n]=i; // Inserisce il codice
n++; // E lo conta
}
}
return n; // Ritorna il numero di codici trovati
}
|
Per provare il programma, scaricare il sorgente, compilarlo
con il comando cc disth4.c ed eseguirlo con il comando ./a.out.
[Home Page dell'ITIS "Fermi"]
[Indice Terza]
[Precedente]
[Successivo]
© Ing. Stefano Salvi - Released under GPL licence
|
