Binario a BCD por codigo algoritmo 16-bit

Hola Compañeros
Recuerdo una vez en el que tuve que hacer un proyecto en que tenía que pasar un número decimal a uno o más displays de 7 segmentos (más sencillo de decir; separar decimal en dígitos).
Siempre usé la forma clásica (La primera que se nos viene a la cabeza) y es la de usar divisiones y multiplicaciones.

Código:
number = 15623
_d1 = number / 10000
_d2 = number / 1000 - 10 * _d1
_d3 = number / 100 - 100 * _d1 - 10 * _d2
_d4 = number / 10 - 1000 * _d1 - 100 * _d2 - 10 * _d3
_d5 = number / 1 - 10000 * _d1 - 1000 * _d2 - 100 * _d3 - 10 * _d4
Si bien este "algoritmo" funciona a la perfección, me vi obligado a saber sus debilidades, cómo la cantidad excesiva de tiempo que tardaba un micro en hacerlo (alrededor de 300 instrucciones).

Hace unos meses en la facultad, oh sorpresa! nos tocó una teoría muy interesante en informática que trataba la conversión de un Binario a un BCD que hasta su momento desconocía.
Y bueno, resumiendo logré hacer lo mismo pero casi 7 veces más eficiente.
Lo que me liberó un montón de preciados tiempos en el micro, incluso lograr mucho más que un barrido aceptable en 5 displays!

El programita está hecho en basic, pero considero que es extremadamente fácil su conversión a otro lenguaje como el C.

El algoritmo es Doble Dabble (Desplazar y sumar 3):

ALGORITMO (numero de 4bits en adelante)
(consider 8-bit binary)
1. Shift the binary number left one bit.


1. Desplazar nuestro número 1 bit a la izquierda
2. si en cualquiera de los cajones nibble el número es mayor igual a 5, se le sumará 3 al nibble donde se encontró
3. Repetimos hasta haber desplazado la misma cantidad de veces que cantidades de bits tenia nuestro número

Siguiendo esto y la foto como guía, creé un algoritmo en que mi número inicial (Long de 4 bytes) "number" se cargaba en otro long llamado "binario".
El porqué hice esto, es fácil de responder:
El BASIC me permite un máximo de variables de 4 bytes o mejor dicho 32 bits.
Si desplazaba y hacia todo sobre mi número inicial 32 bits no sería suficiente para un número de 16 bits, si bien se desplazaría 16 veces hay que tener en cuenta que un número en BDC es mayor a uno binario.

Algoritmo dentro de un for que se repetirá las mismas veces que la cantidad de bits de mi número inicial

Código:
Dim number As Long
Dim i As Byte
Dim binario As Long
binario = 0
number =15623

For i = 0 To 15
    binario = mayor_que_cinco(binario)  \'-----Busco 1 o mas nibble en binario y les sumo 3 solo a los que resultaron mayores igual a 5
    binario = ShiftLeft(binario, 1)  \'--------Desplazo Binario 1 paso a la izquierda
    binario.0 = number.15  \'------------------Cargo en el bit 0 de binario el bit 15 de number
    number = ShiftLeft(number, 1)  \'----------Desplazo number 1 paso a la izquierda
Next i
Función que calcula cuando se suma 3 y cuando no:

Código:
Function mayor_que_cinco(lng As Long) As Long
    Dim bt As Byte
    
    Dim nl As Long
    nl = lng
    bt = 0
    
    
    bt.0 = nl.0
    bt.1 = nl.1
    bt.2 = nl.2
    bt.3 = nl.3
    If bt >= 5 Then bt = bt + 3
    nl.0 = bt.0
    nl.1 = bt.1
    nl.2 = bt.2
    nl.3 = bt.3
    
    
    bt.0 = nl.4
    bt.1 = nl.5
    bt.2 = nl.6
    bt.3 = nl.7
    If bt >= 5 Then bt = bt + 3
    nl.4 = bt.0
    nl.5 = bt.1
    nl.6 = bt.2
    nl.7 = bt.3
    
    
    bt.0 = nl.8
    bt.1 = nl.9
    bt.2 = nl.10
    bt.3 = nl.11
    If bt >= 5 Then bt = bt + 3
    nl.8 = bt.0
    nl.9 = bt.1
    nl.10 = bt.2
    nl.11 = bt.3
    
    
    bt.0 = nl.12
    bt.1 = nl.13
    bt.2 = nl.14
    bt.3 = nl.15
    If bt >= 5 Then bt = bt + 3
    nl.12 = bt.0
    nl.13 = bt.1
    nl.14 = bt.2
    nl.15 = bt.3
    
    
    bt.0 = nl.16
    bt.1 = nl.17
    bt.2 = nl.18
    bt.3 = nl.19
    If bt >= 5 Then bt = bt + 3
    nl.16 = bt.0
    nl.17 = bt.1
    nl.18 = bt.2
    nl.19 = bt.3
    
    mayor_que_cinco = nl
End Function
Bueno, esto es todo, creo que es algo muy útil de implementar en cualquier sistema en el que los tiempos y la eficiencia es una prioridad. (Siempre debería serlo). Saludos!

P.D.: Adjunto las fotos ...
 

Adjuntos

  • db.jpg
    db.jpg
    2.1 KB · Visitas: 108
Última edición por un moderador:
Es muy interesante ese algoritmo; no lo conocía.

Pero haciendo memoria, solo es interesante si el micro 'no sabe' dividir. Si sabe para 8 bits son dos divisiones mas mover los resultados. Para 16 bits no recuerdo pero empleando la instrucción de dividir de 8 bits creo que eran 24 instrucciones, en este caso 16 rotaciones x 2 ya son 32 mas las comprobaciones y las sumas...la fiesta sale entre 48 y 64 mas el bucle etc.
 
El método yo lo conozco por conversión de códigos por exceso a 3 y es muy eficaz para ahorrar tiempo como dice PHElectrónica. De hecho es con el método que me he casado cuando implemento la conversión de códigos binarios a BCD

;)
 
Normalmente cuando hago este tipo de conversión, no suelo tener el tiempo en contra, para lo cual suelo usar la función de resto del C y una división:

Código:
void convertir_digitos_byte(u8 digitos[],u8 dato)
{
	u8 aux;
	
	for(aux=2;aux>0;aux--)
		{
		digitos[aux]=(dato%10)+0x30;
		dato=(int)(dato/10);
		}
		
	digitos[0]=dato+0x30;
}

void convertir_digitos_int(u8 digitos[],u16 dato)
{
	u8 aux;
	
	for(aux=4;aux>0;aux--)
		{
		digitos[aux]=(dato%10)+0x30;
		dato=(int)(dato/10);
		}
		
	digitos[0]=dato+0x30;
}

Al usar esa función de resto, es muy probable que la cantidad de instrucción sean varias, me imagino que al menos una división, multiplicación y una resta necesita.

De todas formas, después le voy a dar una repasada al código.
 
Pues el Double Dabble es uno de mis algoritmos favoritos (bueno, es que tengo muchos favoritos, jejeje) pero hay que saber cómo sacarle toda la potencia que tiene y mucha.

En general la conversión de binarios a BCD/ASCII se suele hacer en bibliotecas que ya implementan este algoritmo entre otros.

La mayoría de los que conocen este algoritmo saben que se usa para pasar un binario (en forma de cadena de bits o bitstream) a BCD. Lo que no muchos saben es que este algoritmo funciona igualmente bien en base arbitraria (al menos cuando ésta es par), bases extrañas, como por ejemplo la conversión directa de un binario a caracteres ASCII, y lo mejor de todo, funciona en base mixta.

¿Qué es base mixta? cuando tenemos un número cuyos dígitos no son todos de la misma base. Quizá ahora no venga a la cabeza un ejemplo, pero sólo tienes que mirar el reloj digital del ordenador o el móvil para darse cuenta de que el formato horario (la marca horaria o timestamp) es un número con base mixta, porque las horas tienen base 24, los minutos y segundos base 60, y las centésimas de segundo tienen base 100 (las décimas tienen base 10).

Otro ejemplo puede ser las cordenadas geográficas de un mapa expresadas en grados, minutos y segundos. Muy útil en la convesión de coordendas en un GPS.

El double dabble permite estas conversiones de un tirón sin tener que hacer ni siquiera una división u operación de resto. De hecho este algoritmo permite calcular congruencias (módulos) sin necesidad de dividir. Todo lo que hay que hacer es ir arrastrando bit a bit e ir ajustando las cantidades a las bases correspondientes sumando el valor adecuado para completar el dígito.

Es un algoritmo tan simple, y a la vez tan bonito, que la gente sabe que funciona pero pocos sabrían decir exáctamente el por qué funciona (de hecho yo mismo dudo sobre cómo modificarlo para que funcione en base impar, aunque creo que es posible hacerlo). Me gusta pensar que es como si tuvieramos una cadena de bolas (cadena de bits) que conforme se desplaza va rellenando una serie de cajas (dígitos) bien todas de igual tamaño (base uniforme) o de distinto tamaño (base mixta) de manera que cuando la última bola entra en la tira de cajas, cada caja contiene la cantidad de bolas que el corresponde.

Aquí una demostración en ANSI C sobre el double dabble de base mixta. El algoritmo en sí es el bucle for. El resto sirve para hacer funcionar el programa en una consola (por lo que necesitais abrir una consola si se quiere ejecutar bajo windows o linux).

Código:
#include <stdio.h>

char *B2A(char *str,unsigned char byte){ 	// Esta funcion devuelve un ASCII de dos dígitos a partir de un
	str[1]=(byte&0x0F)+0x30;				// Byte en BCD. Se usa para salida en pantalla.
	str[0]=((byte>>4)&0x0F)+0x30;
	return(str);
}

void main(){

	unsigned char buffer[9]={0,0,0,0,0,0,0,0,0},*asc="00",*ts=buffer+4; //El buffer contiene el binario de 32bits a transformar y el timestamp.
	unsigned long *tics=buffer;  // los punteros tics y ts (timestamp) apuntan a zonas distintas del mismo buffer.
	int i,j;

	printf("\nIntroduce tics transcurridos (cada tic es una centesim de segundo): ");
	scanf("%d",tics);

	for(i=0;i<32;i++){					// El proceso completo son 32 desplazamientos hacia la izquierda.

		for(j=4;j>=0;j--) switch(j){	// En cada desplazamiento se realizan ajustes correspondientes según la base de cada campo de tiempo.

		case 3:							// Byte de la horas, ajusta la conversion a base 24 (al no caber en un nibble, se toma el byte entero).
			if (ts[j]>=12) ts[j]+=116;
			break;
		case 2:							// Byte de los minutos y los segundos, a base 60.
		case 1:
			if ((ts[j]&0xf0)>=0x30) ts[j]+=0x50; // Ajuste a base 6
			if ((ts[j]&0x0f)>=0x05) ts[j]+=0x03; // Ajuste a base 10
			break;
		default:								 // Resto de bytes (dias y centésimas de segundo) a base 100.
			if ((ts[j]&0xf0)>=0x50) ts[j]+=0x30; // Ajuste a base 10
			if ((ts[j]&0x0f)>=0x05) ts[j]+=0x03; // Ajuste a base 10
		}
		for(j=8;j>=1;j--) buffer[j]=(buffer[j]<<1)|(buffer[j-1]>>7); //Se desplaza completamente bit a bit los 9 bytes del buffer hacia la izda.
		buffer[0]<<=1;
	}
	if(ts[3]>=20) ts[3]+=12; else if(ts[3]>=10) ts[3]+=6; // Ajuste a BCD del campo de las horas en base 24.

	printf("\nLa TimeStamp son %s dias, ",B2A(asc,ts[4]));  // Se imprime resultado.
	printf("%s horas, ",B2A(asc,ts[3]));
	printf("%s minutos y ",B2A(asc,ts[2]));
	printf("%s,",B2A(asc,ts[1]));
	printf("%s segundos.\n",B2A(asc,ts[0]));
}

Os adjunto el archivo con el programa ya compilado para la consola de windows.
 

Adjuntos

  • ddbmixta.rar
    18.5 KB · Visitas: 6
//En proceso hasta que logre poner bien las tablas --> no pude, sin tablas de paso ocupo menos espacio. No queda otra que abrir el adjunto.

Si tienen un multiplicador por hardware en el micro y quieren aprovecharlo, se pueden ahorrar algunos ciclos. Pongamos que hay un pic18fxxx (multiplicador que toma 2 operandos de 8 bits y da resultado de 16 bits en PRODH y PRODL).

Queremos dividir /10 pero en el micro solo puedo multiplicar.
No hay problema, el resultado de la multiplicación es de 16 bits, así que tomando el byte alto estamos dividiendo por 256.
Por lo tanto mul x 10 = 256 -> mul = 25.6

Multiplicar x 25.6 equivale a dividir /10.
Podemos empezar redondeando a 26.

Va una tabla de valores de 8 bits multiplicando x 26, mostrando que queda en byte alto y byte bajo:
{Ver primeras 3 columnas adjunto}

Y que son esos numeros feos en la columna byte bajo?.
Hasta acá hicimos:
N * 26 = byte alto * 256 + byte bajo
dividimos ambos lados /26:
N = byte alto * 256/26 + byte bajo/26
Nuestra aproximación es que 256/26 ~ 10, asi que:

N ~ byte alto * 10 + byte bajo/26

Byte alto por lo tanto es una aproximación al cociente de dividir /10:
cociente ~ byte alto
y el resto es = byte bajo / 26

Otra división... y como hacemos división?, multiplicando!!!! :p
Quiero dividir /26 -> multiplico por 256/26 ~ 10

Entonces ahora nos queda la tabla (leer operaciones de izquierda a derecha):

{Ver columnas 3 en adelante adjunto}

Como se ve el último residuo es el resto de dividir el numero original.
O casi.... que pasó a partir de 64?. Hay un 5 donde debería haber un 4 en el resto (n)
Divisor da bien hasta setenta y pico, pero no importa, porque precisamos usar el resto para terminar de convertir a BCD.
Así que hasta ahora tenemos algo que da divisor y resto bien hasta N = 64. Algo es algo...

Y si sirve solo hasta 64 entonces ya no hace falta más, 2 multiplicaciones y tenemos decenas y unidades separados cada uno por su lado:

PHP:
typedef struct{
    uin8t_t q;
    uint8_t r;
}qr;

//Calculates N div 10 and N mod 10.
//Only good results for N<64 :(
void udivmod(uint8_t N; qr *result);
{
    uint8_t temp;

    #asm
    movf    N,    W    ;
    mullw    26    ;    //multiplicar x 26 ~=~ /10 
                ;     //Ahora tenemos Byte alto = PRODH, byte bajo = PRODL    
    movff    PRODH,    temp    ;    //divisor

    movf    PRODL,    W    ;    //Ahora el resto
    mullw    10    ;    //Dividiendo por 26 ~ multiplicar x10 y tomar PRODH
    #endasm


    qr->r = PRODH;
    qr->q = temp;
    
}
No ví como usar el multiplicador en los pic sin recurrir al assembler, de todas formas no importa, es un ejercicio para entretenerse.

Suficiente!!! ... por ahora. Ya tenemos un conversor a bcd de 2 dígitos, o 1 dígito y 1/2, o era 1 dígito y 3/4... no se, que le pregunten a los de medidas eléctricas de la facultad. Digamos que tenemos 6 bits.
Por lo menos nos sirve para fecha: segundo (hasta 60), minuto (hasta 60), hora (hasta 24), día del mes (hasta 31), mes (hasta 12). Y año hasta el 2063 :p; vamos a generar un nuevo efecto 2000.

A pensar para la casa, como podemos hacer que funcione para N > 64?
De pura generosidad adjunto una planilla odt para el que quiere numerear un poco.

La 1 de la mañana... será hasta hoy entonces :D.
 

Adjuntos

  • bin_bcd_8b_mul.ods.zip
    56.5 KB · Visitas: 4
Última edición:
Atrás
Arriba