 |
Partendo dal programma precedente, introduciamo ora le maschere e le operazioni bit a bit,
facendo riscrivere la funzione che calcola la distanza di Hamming.
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.
Usare operazioni bit a bit invece che convertire i codici in vettori di interi per calcoare
la distanza di Hamming.
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.
- Per calcolare la distanza di Hamming, possiamo prima di tutto utilizzare l'operazione
EXCLUSIVE OR (operatore ^) per individuare i bit diversi (l'exclusive or tra due
bir vale 1 se i bit sono diversi, 0 se sono uguali). A questo punto si può usare una
versione modificata della conversione in binario, per calcolare i bit a 1. Per isolare il bit
meno significativo è possibile utilizzare l'operazione AND bit a bit ed una
maschera (1 per il bit meno significativo).
Una possibile soluzione è la seguente:
// Tizio - Pinco - 3°AIN - 05/04/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 */
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);
}
}
}
/* calcola la distanza di Hamming tra due codici usando le operazioni binarie
* Ritorna la distanza calcolata
*/
int disth(int a,int b)
{
int i; // Codice contenete i bit diversi tra a e b
int dist; // Distanza calcoalta
dist=0; // Distanza inizialmente 0
i = (a ^ b); // Usando l'exclusive or, discrimina i bit diversi
if (i < 0) exit ();
while (i != 0)// Finche' ci sono bit a 1 (bit diversi)
{
if(i & 1) // Se il bit meno significativo e' diverso da 0 (bit diversi)
{
dist++; // Conta la differenza
}
i = i >> 1; // Scarta il bit meno significativo
}
return dist; // Restituisce la distanza
}
/* 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;j<n && disth(i,hamm[j])>=dist ; 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 disth5.c ed eseguirlo con il comando ./a.out.
[Home Page dell'ITIS "Fermi"]
[Indice Terza]
[Precedente]
[Successivo]
© Ing. Stefano Salvi - Released under GPL licence
|
