Hispanopedia WikiEn informática , el algoritmo double dabble se utiliza para convertir números binarios en notación decimal codificada en binario (BCD). [1] [2] También se lo conoce como algoritmo shift-and-add -3 , y se puede implementar utilizando una pequeña cantidad de puertas en el hardware de la computadora, pero a expensas de una alta latencia . [3]
Algoritmo
El algoritmo funciona de la siguiente manera:
Supongamos que el número original que se va a convertir se almacena en un registro de n bits de ancho. Reserve un espacio de trabajo lo suficientemente amplio como para contener tanto el número original como su representación en BCD; n + 4× ceil ( n /3) bits serán suficientes. Se necesitan un máximo de 4 bits en binario para almacenar cada dígito decimal.
Luego, se divide el espacio de trabajo en dígitos BCD (a la izquierda) y el registro original (a la derecha). Por ejemplo, si el número original que se va a convertir tiene ocho bits de ancho, el espacio de trabajo se dividiría de la siguiente manera:
Centenas Decenas Unidades Original 0010 0100 0011 11110011
El diagrama de arriba muestra la representación binaria de 243 10 en el registro original y la representación BCD de 243 a la izquierda.
El espacio de trabajo se inicializa con todos los ceros y luego el valor que se va a convertir se copia en el espacio del "registro original" a la derecha.
0000 0000 0000 11110011
El algoritmo luego itera n veces. En cada iteración, cualquier dígito BCD que sea al menos 5 (0101 en binario) se incrementa en 3 (0011); luego, todo el espacio de trabajo se desplaza a la izquierda un bit. El incremento garantiza que un valor de 5, incrementado y desplazado a la izquierda, se convierta en 16 (10000), "llevándose" así correctamente al siguiente dígito BCD.
Básicamente, el algoritmo funciona duplicando el valor BCD de la izquierda en cada iteración y agregando uno o cero según el patrón de bits original. Al desplazarse hacia la izquierda se logran ambas tareas simultáneamente. Si algún dígito es cinco o más, se agregan tres para garantizar que el valor "se mantenga" en base 10.
El algoritmo de doble dabble, ejecutado sobre el valor 243 10 , se ve así:
0000 0000 0000 11110011 Inicialización
0000 0000 0001 11100110 Turno
0000 0000 0011 11001100 Turno
0000 0000 0111 10011000 Turno
0000 0000 1010 10011000 Suma 3 a UNIDADES, ya que era 7
0000 0001 0101 00110000 Turno
0000 0001 1000 00110000 Suma 3 a UNIDADES, ya que eran 5
0000 0011 0000 01100000 Turno
0000 0110 0000 11000000 Turno
0000 1001 0000 11000000 Suma 3 a DECENAS, ya que eran 6
0001 0010 0001 10000000 Turno
0010 0100 0011 00000000 Turno
2 4 3
BCD
Ahora se han realizado ocho cambios, por lo que el algoritmo finaliza. Los dígitos BCD a la izquierda del espacio del "registro original" muestran la codificación BCD del valor original 243.
Otro ejemplo del algoritmo double dabble: valor 65244 10 .
10 4 10 3 10 2 10 1 10 0 Binario original
0000 0000 0000 0000 0000 1111111011011100 Inicialización
0000 0000 0000 0000 0001 1111110110111000 Desplazamiento a la izquierda (1.º)
0000 0000 0000 0000 0011 1111101101110000 Desplazamiento a la izquierda (2.º)
0000 0000 0000 0000 0111 1111011011100000 Desplazamiento a la izquierda (3.º)
0000 0000 0000 0000 1010 1111011011100000 Suma 3 a 10 0 , ya que era 7
0000 0000 0000 0001 0101 1110110111000000 Desplazamiento a la izquierda (4.º)
0000 0000 0000 0001 1000 1110110111000000 Suma 3 a 10 0 , ya que era 5
0000 0000 0000 0011 0001 1101101110000000 Desplazamiento a la izquierda (5.º)
0000 0000 0000 0110 0011 1011011100000000 Desplazamiento a la izquierda (6.º)
0000 0000 0000 1001 0011 1011011100000000 Suma 3 a 10 1 , ya que era 6
0000 0000 0001 0010 0111 0110111000000000 Desplazamiento a la izquierda (7.º)
0000 0000 0001 0010 1010 01101110000000000 Suma 3 a 10 0 , ya que era 7
0000 0000 0010 0101 0100 1101110000000000 Desplazamiento a la izquierda (8.º)
0000 0000 0010 1000 0100 1101110000000000 Suma 3 a 10 1 , ya que era 5
0000 0000 0101 0000 1001 1011100000000000 Desplazamiento a la izquierda (9.º)
0000 0000 1000 0000 1001 1011100000000000 Suma 3 a 10 2 , ya que eran 5
0000 0000 1000 0000 1100 10111000000000000 Suma 3 a 10 0 , ya que era 9
0000 0001 0000 0001 1001 0111000000000000 Desplazamiento a la izquierda (10.º)
0000 0001 0000 0001 1100 01110000000000000 Suma 3 a 10 0 , ya que era 9
0000 0010 0000 0011 1000 1110000000000000 Desplazamiento a la izquierda (11.º)
0000 0010 0000 0011 1011 1110000000000000 Suma 3 a 10 0 , ya que era 8
0000 0100 0000 0111 0111 1100000000000000 Desplazamiento a la izquierda (12.º)
0000 0100 0000 1010 0111 11000000000000000 Suma 3 a 10 1 , ya que era 7
0000 0100 0000 1010 1010 11000000000000000 Suma 3 a 10 0 , ya que era 7
0000 1000 0001 0101 0101 1000000000000000 Desplazamiento a la izquierda (13.º)
0000 1011 0001 0101 0101 1000000000000000 Suma 3 a 10 3 , ya que eran 8
0000 1011 0001 1000 0101 100000000000000000 Suma 3 a 10 1 , ya que era 5
0000 1011 0001 1000 1000 10000000000000000 Suma 3 a 10 0 , ya que era 5
0001 0110 0011 0001 0001 00000000000000000 Desplazamiento a la izquierda (14.º)
0001 1001 0011 0001 0001 00000000000000000 Suma 3 a 10 3 , ya que eran 6
0011 0010 0110 0010 0010 00000000000000000 Desplazamiento a la izquierda (15.º)
0011 0010 1001 0010 0010 00000000000000000 Suma 3 a 10 2 , ya que eran 6
0110 0101 0010 0100 0100 00000000000000000 Desplazamiento a la izquierda (16.º)
6 5 2 4 4
BCD
Se han realizado dieciséis cambios, por lo que el algoritmo finaliza. El valor decimal de los dígitos BCD es: 6*10 4 + 5*10 3 + 2*10 2 + 4*10 1 + 4*10 0 = 65244.
Implementación de Verilog paramétrico
// Implementación paramétrica de Verilog del convertidor binario a BCD de doble dabble
. // Para ver el proyecto completo, consulte
// https://github.com/AmeerAbdelhadi/Binary-to-BCD-Converter
módulo bin2bcd #( parámetro W = 18 ) // ancho de entrada ( entrada [ W - 1 : 0 ] bin , // salida binaria reg [ W + ( W - 4 ) / 3 : 0 ] bcd ); // bcd {...,millares,centenas,decenas,unidades}
entero i , j ;
siempre @( bin ) begin for ( i = 0 ; i <= W + ( W - 4 ) / 3 ; i = i + 1 ) bcd [ i ] = 0 ; // inicializar con ceros bcd [ W - 1 : 0 ] = bin ; // inicializar con vector de entrada for ( i = 0 ; i <= W - 4 ; i = i + 1 ) // iterar sobre la profundidad de la estructura for ( j = 0 ; j <= i / 3 ; j = j + 1 ) // iterar sobre el ancho de la estructura if ( bcd [ W - i + 4 * j -: 4 ] > 4 ) // if > 4 bcd [ W - i + 4 * j -: 4 ] = bcd [ W - i + 4 * j -: 4 ] + 4 'd3 ; // sumar 3 end
módulo final
[4]
Doble toque inverso
El algoritmo es completamente reversible. Aplicando el algoritmo de doble dabble inverso, se puede convertir un número BCD a binario. Para invertir el algoritmo, se invierten los pasos principales del algoritmo:
Ejemplo de doble toque inverso
El algoritmo de doble dabble inverso, realizado en los tres dígitos BCD 2-4-3, se ve así:
Entrada binaria BCD
Producción
2 4 3
0010 0100 0011 00000000 Inicialización
0001 0010 0001 10000000 Desplazado a la derecha
0000 1001 0000 11000000 Desplazado a la derecha
0000 0110 0000 11000000 Le resté 3 al 2do grupo, porque eran 9
0000 0011 0000 01100000 Desplazado a la derecha
0000 0001 1000 00110000 Desplazado a la derecha
0000 0001 0101 00110000 Le resté 3 al 3er grupo, porque eran 8
0000 0000 1010 10011000 Desplazado a la derecha
0000 0000 0111 10011000 Le resté 3 al 3er grupo, porque eran 10
0000 0000 0011 11001100 Desplazado a la derecha
0000 0000 0001 11100110 Desplazado a la derecha
0000 0000 0000 11110011 Desplazado a la derecha
==========================
243 10
Histórico
En la década de 1960, el término double dabble también se utilizó para un algoritmo mental diferente, utilizado por los programadores para convertir un número binario en decimal. Se realiza leyendo el número binario de izquierda a derecha, duplicando si el siguiente bit es cero y duplicando y sumando uno si el siguiente bit es uno. [5] En el ejemplo anterior, 11110011, el proceso de pensamiento sería: "uno, tres, siete, quince, treinta, sesenta, ciento veintiuno, doscientos cuarenta y tres", el mismo resultado que el obtenido anteriormente.
Véase también
- Tabla de búsqueda : un enfoque alternativo para realizar la conversión
Referencias
- ^ Gao, Shuli; Al-Khalili, D.; Chabini, N. (junio de 2012), "Un sumador BCD mejorado que utiliza FPGAs de 6 LUT", IEEE 10th International New Circuits and Systems Conference (NEWCAS 2012) , págs. 13– 16, doi :10.1109/NEWCAS.2012.6328944, ISBN 978-1-4673-0859-5, Número de identificación del sujeto 36909518
- ^ "Convertidor de binario a BCD: "Algoritmo de conversión de binario a BCD Double-Dabble"" (PDF) . Archivado desde el original (PDF) el 2012-01-31.
- ^ Véstias, Mario P.; Neto, Horatio C. (marzo de 2010), "Multiplicadores decimales paralelos utilizando multiplicadores binarios", VI Southern Programmable Logic Conference (SPL 2010) , pp. 73– 78, doi :10.1109/SPL.2010.5483001, ISBN 978-1-4244-6309-1, Número de identificación del sujeto 28360570
- ^ ab Abdelhadi, Ameer (7 de julio de 2019), AmeerAbdelhadi / Binary-to-BCD-Converter , consultado el 3 de marzo de 2020
- ^ Dios, Deepali A.; Godse, Atul P. (2008). Técnicas digitales. Pune, India: Publicaciones técnicas. pag. 4.ISBN 978-8-18431401-4.
Lectura adicional
- Falconer, Charles "Chuck" B. (16 de abril de 2004). "Una explicación del algoritmo de conversión bin-BCD de Double-Dabble". Archivado desde el original el 25 de marzo de 2009.