Encoder-Decoder Codi Binari – Codi Gray

Reprenc el bloc després d’una aturada d’un any!

He dedicat bona part del temps que dedicava al bloc a estudiar. Des de fa un any i mig estic matriculat als estudis de Màster d’Enginyeria Informàtica de la UOC. He tornat a la Universitat gairebé trenta anys després de posar-hi el peu per primer cop!

Fa poc més d’un parell d’anys les circumstàncies professionals em van empènyer a canviar de feina. Una de les conseqüències d’aquell canvi va ser que em va semblar que era un bon moment per capitalitzar l’experiència professional acumulada després de… gairebé vint-i-cinc anys al sector TIC, dels quals més de setze específicament a la consultoria.

He de dir que em va molt bé, per ara, i que duri. També cal dir que m’ho estic prenent amb calma: només faig dues assignatures per semestre.

Tanmateix, la quantitat de temps que cal dedicar als treballs i pràctiques, només amb dues assignatures, és prou important. Tant que en tot un any no m’he vist amb cor de dedicar temps al bloc d’apunts de tecnologia.

idealment, a meva intenció és que bloc i estudis siguin activitats sinèrgiques. No és el cas d’avui, però alguns dels treball que ja he fet per a la UOC donen per a un post interessant, i potser els adaptaré i els acabaré publicant aquí. En aquest sentit, a diferència dels polítics del PP, el meu màster me l’estic currant…  i puc aportar proves.

Fetes aquestes explicacions, anem al gra. Avui presento un exercici senzill per reprendre el bloc : es tracta d’un decoder/encoder de codi Binari a codi Gray. El codi Gray és una d’aquelles coses que vaig aprendre a l’Enginyeria Tècnica de Telecos, quan estudiava electrònica digital allà pels finals dels vuitanta. Hi havia alguna cosa gairebé màgica en les simplificacions de circuits combinacionals fent servir mapes de Karnaugh. La màgia és que als mapes  de Karnaugh els minterms es distribueixen per la taula seguint el codi de gray, aleshores, elements adjacents difereixen només en un bit, i això vol dir que es pot simplificar la variable binària corresponent al bit que canvia en aquells termes adjacents.

Però té més usos. Notablement, es fa servir per minimitzar els errors en les modulacions digitals QAM i Gray Coded M-PSK.

De Viquipèdia (https://ca.wikipedia.org/wiki/Codi_Gray) : « El codi binari reflectit o codi Gray, nomenat així en honor de l’investigador Frank Gray, és un sistema de numeració binari en què dos valors successius difereixen només en un dels seus dígits.

El codi Gray va ser dissenyat originalment per prevenir senyals espuris dels switches electromecànics. Actualment és utilitzat per a facilitar la correcció d’errors en els sistemes de comunicacions, com ara alguns sistemes de televisió per cable i la televisió digital terrestre. »

Vet aquí un vídeo que explica perquè el codi gray és tan útil en els codificadors de posició rotatoris (elimina els valors espuris que podria introduir la codificació binària directa) :

De fet, la idea original d’aquest post era implementar un control rotatori basat en el codi Gray amb Arduino . Queda per a més endavant.

Anem per feina, el que vull fer és un codificador / decodificador de binari a gray, és dir, vull un mètode al que li passo un número enter de n bits, i vull que em torni un array amb els bits del codi gray corresponent al número rebut.

també vull el mètode que faci el camí de tornada, és dir, vull el mètode al que li passi un array de bits amb el codi gray d’un número de n bits, i vull que em torni un array amb els bits de la codificació binària directa d’aquell número.

L’algoritme per a calcular el codi gray / codi binari és, en realitat, molt senzill. Està ben explicat a la wiki. La gràcia de tot això és que abans de consultar-ho a la wiki he dedicat un temps a veure si me’n recordava com es feia aquesta codificació i descodificació. Després d’algunes proves (de les que en trobareu rastre al meu GitHub), finalment me n’he sortit. Vet aquí el resultat :

Vet aquí el codi Python

Coder

def calculate_gray(number, n):
    bits = []
    gray = []
    
    remainder = number
    for nn in range(0, n):
        [quotient, remainder] = divmod(remainder, 2 ** (n - 1 - nn))
        bits.append(quotient)
        if nn == 0:
            gray.append(bits[0])
        else:
            gray.append(bits[nn - 1] ^ bits[nn])      
            
            
    return [bits, gray]

i decoder

def calculate_binary(gray, n):  # gray is an array of bits
    bits = []

    for pos in range(0, n):
        if pos == 0:
            bits.append(gray[0])
        else:
            bits.append(bits[pos - 1] ^ gray[pos])      
            
    return bits

i una taula de prova

if __name__ == '__main__':
    print "print a Gray table for n bits"
    n = raw_input('Number of bits? ')
    n = int(n)
    print "number of bits : %d" % n   
    
    bits = []
    gray = []
    grayTable = []

    for i in range(0, 2 ** n):
        [bits, gray] = calculate_gray(i, n)
        grayTable.append(gray)
        strBits = ''.join(map(lambda (x) : chr(ord('0') + x), bits))
        strGray = ''.join(map(lambda (x) : chr(ord('0') + x), gray))
        
        print "%5d --> %s --> %s" % (i, strBits, strGray)
    
    print "-------------------------------------------"
    
    bits = []

    for i in range(0, 2 ** n):
        bits = calculate_binary(grayTable[i], n)
        strBits = ''.join(map(lambda (x) : chr(ord('0') + x), bits))
        strGray = ''.join(map(lambda (x) : chr(ord('0') + x), grayTable[i]))
        
        print "%5d --> %s --> %s" % (i, strGray, strBits)

    print "Done!"

Com a cosa molt bonica, indicaria l’us de lambdes i join per a passar l’array de bits a cadena de caràcters; i també la funció divmod, que utilitzada en cascada em permet obtenir els bits corresponents a l’enter que vull codificar.

El repositori Github és :

https://github.com/abaranguer/gray-code-py-version.git

Bé, tot plegat queda una mica curt, oi? el que he fet és escriure una segona versió del codi, però aquest cop amb llenguatge C. Així, de pas, l’he refrescat una mica.

Python és un llenguatge de molt alt nivell d’abstracció i m’ha permès implementar l’algoritme en un obrir i tancar d’ulls. La versió C, en canvi, ha estat més interessant. Vet aquí el codi :

#include 
#include 
#include 

#define BUF_SIZE 3

/* typedef */
typedef struct typeRetDivMod {
	int quotient;
	int remainder;
} RetDivMod;

typedef struct typeRetCalculateGray {
	int *bits;
	int *gray;
} RetCalculateGray;

/* prototypes */
int main(void);
RetCalculateGray calculate_gray(int number, int n);
int *calculate_binary(int *gray, int n);
RetDivMod divmod(int number, int divisor);
char *bitsToString(int *bits, int numBits);

/* functions */
int main() {
	char buf[BUF_SIZE];
	int n;
	int i;
	RetCalculateGray retValue;
	int *bitsFromGray;
	char *bits;
	char *bits2;
	char *gray;

	printf("Print a Gray table for n bits\n\n");
	printf("Number of bits? ");
	fgets(buf, BUF_SIZE, stdin);
	n = atoi(buf);
	printf("number of bits : %d\n", n);

	int range = pow(2, n);

	for (i = 0; i  %s --> %s --> %s\n", i, bits, gray, bits2);
		free(bits);
		free(gray);
		free(bits2);
		free(retValue.bits);
		free(retValue.gray);
		free(bitsFromGray);
	}

	printf("Done!\n");
	return 0;
}

RetCalculateGray calculate_gray(int number, int n) {
	int remainder;
	int nn;
	RetDivMod retDivMod;
	RetCalculateGray retValue;

	retValue.bits = (int *) malloc(n * sizeof(int));
	retValue.gray = (int *) malloc(n * sizeof(int));

	remainder = number;

	for (nn = 0; nn < n; nn++) {
		retDivMod = divmod(remainder, pow(2, n - 1 - nn));
		retValue.bits[nn] = retDivMod.quotient;
		remainder = retDivMod.remainder;
		if (nn == 0) {
			retValue.gray[nn] = retValue.bits[0];
		} else {
			retValue.gray[nn] = retValue.bits[nn - 1] ^ retValue.bits[nn];
		}
	}

	return (retValue);
}

int *calculate_binary(int *gray, int n) {
	int nn;
	int *bits;

	bits = (int *) malloc(n * sizeof(int));

	for (nn = 0; nn < n; nn++) {
		if (nn == 0) {
			bits[nn] = gray[0];
		} else {
			bits[nn] = bits[nn - 1] ^ gray[nn];
		}
	}

	return (bits);
}

RetDivMod divmod(int number, int divisor) {
	RetDivMod retDivMod;

	retDivMod.quotient = number / divisor;
	retDivMod.remainder = number % divisor;

	return retDivMod;
}

char *bitsToString(int *bits, int numBits) {
	int i;
	char *charBits;

	charBits = (char *) malloc(numBits * sizeof(char) + 1);
	for (i = 0; i < numBits; i++) {
		charBits[i] = '0' + bits[i];
	}
	charBits[numBits] = '\0';

	return charBits;
}

El repositori Github de la versió C :

https://github.com/abaranguer/gray-code-c-version.git

Per acabar, doncs, a la versió C hi han més coses a comentar. En destaco :

  • L’us de typedef i struct per a definir estructures que faig servir per moure arguments entre  main  i les funcions de coding i encoding.
  • Us de malloc i free per reservar / alliberar dinàmicament l’espai de memòria per als arrays dels bits.
  • La versió C de la funció divmod de Python.
  • L’ús de fgets per a prendre entrada per consola de forma segura aprofitant que fgets fa automàticament el control de desbordament del buffer d’entrada.