AngoLinux

Calcolo di una codifica a distanza di hamming data, usando un array di interi per il codice

- A cura del Prof. Stefano Salvi -


Calcoliamo ora una codifica a distanza di Hamming data.

Il testo dell'esercizio è il seguente:

Scrivere un programma C che legga da tastiera un numero tra 1 ed 8 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.
Suggerimento
  • Inizialmente l'array 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.

Una possibile soluzione è la seguente:
// Tizio - Pinco - 3°AIN - 08/03/2002
// Calcola una codifica a distanza di hamming data, non usando una 'matrice di bit'


#include <stdio.h>

#define DIM2 256			/* Numero totale di codici ad 8 bit */
#define DIM 8				/* Dimensione del codice */

int disth(int r,int c,int hamm2);	// Indica se la distanza di Hamming tra i codici
					// 'r' e 'c' e' uguale o superiore alla distanza
					// hamm2 data
void numToBin(int n,int bin[]);		// Converte il numero 'n' nel 'vettore di bit' bin
void visVet(int vet[],int num);		// Viusualizza il vettore 'vet', 
					// che contiene 'num' elementi
void azzera(int vet[],int dim);		// Azzera il vettore 'vet' di dimensione 'dim'

main()
{
int k,i,j;
int hamm;		// Distanza di Hamming richiesta dall'utente
int vet[DIM2];		// Codifica (flags dei codici -> 0=accettato, 1=scartato

  // Riciede all'utente la distanza, controllando il dato inserito
  do {
    printf("Distanza di Hamming: "); scanf("%d",&hamm);
  } while ((hamm<1) || (hamm>8));

  /* Algoritmo:
   *  Uso un array che conterra' i soli codici accettati.
   *  Inizialmente l'array conterra' solo il codice di partenza (lo 0)
   *  Esaminero' poi uno ad uno tutti gli altri codici (da 1 a 255).
   *  Calcolero' 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.
   */
  vet [0] = 0;	// Inserisco il primo valore nell'array	
  k=1;		// Indico che l'array contiene il primo codice
  // Ora analizzo tutti gli altri codici (dall'1 al 255)		
  for(i=1;i<DIM2;i++)
  {
    // Confronto il codice da esaminare con tutti quelli gia' nell'array.
    // Se trovo un codice per il quale la distanza non va bene (disth == 0)
    // interrompo l'analisi perche' il codice e' da scartare
    for(j=0; j < k && disth(i,vet[j],hamm);j++)
        ;

    if(j == k)	// Se il confronto e' andato bene con tutti i codici
    {		// (sono arrivato in fondo al ciclo)
      vet[k]=i;	// Inserisco il codice appena controllato
      k++;	// e indico che nel vettore c'e' un codice in piu'
    }
  }

  // Visualizza il codice prodotto						
  visVet(vet,k);
}

/* Indica se la distanza di Hamming tra i codici
 * 'r' e 'c' e' uguale o superiore alla distanza
 * hamm2 data
 * Ritorna 'vero' se il codice e' buono (la distanza e' magiore o uguale)
 * 'falso' se il codice e' da scartare
 */
int disth(int r,int c,int hamm2)
{
int j;		// Indice del bit
int hamm=0;	// Distanza di hamming corrente

int a[DIM],b[DIM];	// Traduzione 'binaria' dei due parametri

  // Inizializza i due 'codici'
  azzera(a,DIM);
  azzera(b,DIM);

  // Converte in binario i due codici
  numToBin(r,a);
  numToBin(c,b);
	
  for(j=0;j<DIM;j++)	// Per ogni bit del codice
  {
    if(a[j]!=b[j])	// Se i bit nei due codici sono diversi
    {
      hamm++;		// Conta il bit dicerso
    }
  }
	
  return hamm >= hamm2;	// Ritorna la condizione imposta
} 

/* Converte il numero 'n' nel 'vettore di bit' bin
 * Mette il bit piu' signidicativo nel prmo elemento dell'array
 */
void numToBin(int n,int bin[])
{
int i = 0;	// Indice del bit (dal meno significativo)

  while(n!=0)		// Finche' in 'n' ci sono bit
  {
    bin[DIM-1-i]=n%2;	// Mette nell'elemnto il bit meno significativo
    n=n/2;		// Elimina il bit meno significativo
    i++;		// e passa al prossimo bit
  }
}

/* Viusualizza il vettore 'vet', che contiene 'num' elementi
 * sia in decimale che in esadecomale
 */
void visVet(int vet[],int num)
{
int j;	// Indice dell'elemento

  for(j=0;j < num;j++)	// Tutti gli element dati
  {
    printf("%4d [%3x]",vet[j],vet[j]);	// Formato di stampa (tutti in linea)
  }
  printf ("\n");	// Alla fine va' a capo
}

/* Azzera il vettore 'vet' di dimensione 'dim'
 */
void azzera(int vet[],int dim)
{
int i;
  for(i=0;i<dim;i++)	// Per ogni elemeto del vettore
  {
    vet[i]=0;		// Azzera l'elemento
  }
}

Per provare il programma, scaricare il sorgente, compilarlo con il comando cc disth3.c ed eseguirlo con il comando ./a.out.


[Home Page dell'ITIS "Fermi"] [Indice Terza] [Precedente] [Successivo]

© Ing. Stefano Salvi - Released under GPL licence