// Tizio - Pinco - 3°AIN - 08/03/2002
// Calcola un codice a distanza di hamming data
#include <stdio.h>
#define DIM3 8 /* Dimensione di un codice */
#define SCARTATO 8 /* Elemento che contiene il flag */
#define DIM (DIM3+1)/* Dimensione del dato (8 bit piu' un flag) */
#define DIM2 256 /* Numero totale di codici diversi (a 8 bit) */
void disth(int r,int c,int chx[][DIM],int hamm1); // Calcola la distanza di hamming
// tra gli elementi r e c di chx
void numToBin(int n,int bin[][DIM]); // Converte un numero in binario, lasciando il risultato
// nell'elemento n di bin
void visMat(int mat[][DIM]); // Visualizza gli elementi attivi della matrice
// (quelli con bin [x][8] != 0)
void azzera(int chx[][DIM]); // Azzera tutti gli elementi della matrice
main()
{
int chx[DIM2][DIM]; // Vettore nel quale si immagazzina il codice
// In ogni riga, gli elementi da 0 a 7 contengono i bit del
// codice, l'elemento 8 contiene un flag:
// Se l'elemento 8 vale 0, la riga e' da accettare
// Se l'elemento 8 vale 0, la riga e' da scartare
int i,j; // Indici per i cicli
int hamm1; // Distanza di Hamminh introdotta dall'utente
azzera(chx); // Inizalizza il vettore dei codici - inizialmente tutti accettati
// Richiede la distanza di hamming, controlla che sia tra 1 ed 8
do {
printf("Distanza di Hamming: ");
scanf("%d",&hamm1);
} while(hamm1<1 || hamm1>8);
// Inizializza il vettore con tutti i codici da 000000000 (0) ad 11111111 (255)
for(i=0;i<DIM2;i++)
{
numToBin(i,chx);
}
/* Algoritmo:
* All'inizio tutti i codici sono validi
* Per ogni codice valido:
* Confronta ogni codice che lo segue con questo, scartando tutti quelli
* che sono troppo 'vicini'
*/
for(j=0;j<DIM2-1;j++) // Esamina tutti i codici
{
if(chx[j][SCARTATO] != 1) // Se il codice corrente e' 'buono'
{
for(i=j+1;i<DIM2;i++) // Confronta con lui tutti i codici successivi
{
if(chx[i][SCARTATO] != 1)// Se il secondo codice e' ancora 'buono'
{
disth(j,i,chx,hamm1); // Lo confronta con il primo e, se e' troppo 'vicino',
// lo scarta
}
}
}
}
visMat(chx); // Visualizza il risultato
}
/* Confronta i codici di indice 'r' e 'c' della matrice chx.
* Se i due codici distano almendo 'hamm1' bit, il codice
* di indice 'c' viene accettato (chx [c][8] = 0), altirmenti
* viene scartato (chx [c][8] = 1)
*/
void disth(int r,int c,int chx[][DIM],int hamm1)
{
int j; // Indice del bit
int hamm=0; // Distanza tra i due codici esaminati
for(j = 0; j < DIM3; j++) // Per ogni bit del codice
{
if(chx[r][j]!=chx[c][j]) // Se i bit sono diversi
{
hamm++; // Li conta
}
}
if(hamm < hamm1) // Se il numero di bit diversi e' troppo basso
{
chx[c][SCARTATO] = 1; // Scarta il secondo codice
}
}
/* Converte il numero 'n' in binario, lasciando il risultato alla riga 'n',
* un bit per ogni elemento, a partire dal piu' significativo
*/
void numToBin(int n,int bin[][DIM])
{
int j=0; // Indice del bit
int i=n; // Riga del codice (n viene 'distrutto')
while(n!=0) // Finche' 'n' contiene bit ad 1
{
bin[i][DIM3-1-j]=n%2; // Lascia nel bit corrente il bit meno significativo
n=n/2; // Elimina il bit meno significativo
++j; // e passa al prossimo bit
}
}
/* Viusalizza i codici validi della matrice (quelli con l'ultimo elemento a 0)
*/
void visMat(int mat[][DIM])
{
int i,j; // Indici di colonna (bit) e riga (codice)
for(j=0;j<DIM2;j++) // Analizza tutti i codici
{
if(mat[j][SCARTATO]==0) // Se il codice e' attivo
{
for(i=0;i<DIM3;i++) // Per ogni bit
{
printf("%2d",mat[j][i]); // Stampa il bit
}
printf(" %d\n",j); // Alla fine stampa anche il codice in decimale
// (l'indice corrisponde al codice stesso)
}
}
}
/* Azzera tutti gli elementi della matrice */
void azzera(int chx[][DIM])
{
int i,j; // In dicie di riga e clonna
for(i=0;i<DIM2;i++) // Per ogni riga
{
for(j=0;j<DIM;j++) // Per ogni colonna
{
chx[i][j]=0; // Azzera l'elemento
}
}
}
|
