Doble incursión - Double dabble

En informática , el algoritmo de doble incursión se utiliza para convertir números binarios en notación decimal codificada en binario (BCD). También se conoce como el 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 .

Algoritmo

El algoritmo funciona de la siguiente manera:

Supongamos que el número original para ser convertido se almacena en un registro que es n  bits de ancho. Reserve un espacio de borrador lo suficientemente amplio para contener tanto el número original como su representación 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, divida el espacio temporal 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 un ancho de ocho bits, el espacio temporal se dividirá de la siguiente manera: 

100s Tens Ones   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 temporal se inicializa a 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 temporal se desplaza un poco hacia la izquierda. El incremento asegura que un valor de 5, incrementado y desplazado a la izquierda, se convierta en 16 (10000), por lo que se "transporta" correctamente al siguiente dígito BCD.

Esencialmente, el algoritmo opera duplicando el valor BCD a la izquierda en cada iteración y agregando uno o cero de acuerdo con el patrón de bits original. Si se desplaza a la izquierda, se logran ambas tareas simultáneamente. Si cualquier dígito es cinco o más, se agrega tres para asegurar que el valor "se lleve" en base 10.

El algoritmo de doble incursión, realizado en el valor 243 10 , se ve así: 

0000 0000 0000   11110011   Initialization
0000 0000 0001   11100110   Shift
0000 0000 0011   11001100   Shift
0000 0000 0111   10011000   Shift
0000 0000 1010   10011000   Add 3 to ONES, since it was 7
0000 0001 0101   00110000   Shift
0000 0001 1000   00110000   Add 3 to ONES, since it was 5
0000 0011 0000   01100000   Shift
0000 0110 0000   11000000   Shift
0000 1001 0000   11000000   Add 3 to TENS, since it was 6
0001 0010 0001   10000000   Shift
0010 0100 0011   00000000   Shift
   2    4    3
       BCD

Ahora se han realizado ocho turnos, por lo que el algoritmo termina. Los dígitos BCD a la izquierda del espacio del "registro original" muestran la codificación BCD del valor original 243.

Otro ejemplo para el algoritmo de doble incursión: valor 65244 10 . 

 104  103  102   101  100    Original binary
0000 0000 0000 0000 0000   1111111011011100   Initialization
0000 0000 0000 0000 0001   1111110110111000   Shift left (1st)
0000 0000 0000 0000 0011   1111101101110000   Shift left (2nd)
0000 0000 0000 0000 0111   1111011011100000   Shift left (3rd)
0000 0000 0000 0000 1010   1111011011100000   Add 3 to 100, since it was 7
0000 0000 0000 0001 0101   1110110111000000   Shift left (4th)
0000 0000 0000 0001 1000   1110110111000000   Add 3 to 100, since it was 5
0000 0000 0000 0011 0001   1101101110000000   Shift left (5th)
0000 0000 0000 0110 0011   1011011100000000   Shift left (6th)
0000 0000 0000 1001 0011   1011011100000000   Add 3 to 101, since it was 6
0000 0000 0001 0010 0111   0110111000000000   Shift left (7th)
0000 0000 0001 0010 1010   0110111000000000   Add 3 to 100, since it was 7
0000 0000 0010 0101 0100   1101110000000000   Shift left (8th)
0000 0000 0010 1000 0100   1101110000000000   Add 3 to 101, since it was 5
0000 0000 0101 0000 1001   1011100000000000   Shift left (9th)
0000 0000 1000 0000 1001   1011100000000000   Add 3 to 102, since it was 5
0000 0000 1000 0000 1100   1011100000000000   Add 3 to 100, since it was 9
0000 0001 0000 0001 1001   0111000000000000   Shift left (10th)
0000 0001 0000 0001 1100   0111000000000000   Add 3 to 100, since it was 9
0000 0010 0000 0011 1000   1110000000000000   Shift left (11th)
0000 0010 0000 0011 1011   1110000000000000   Add 3 to 100, since it was 8
0000 0100 0000 0111 0111   1100000000000000   Shift left (12th)
0000 0100 0000 1010 0111   1100000000000000   Add 3 to 101, since it was 7
0000 0100 0000 1010 1010   1100000000000000   Add 3 to 100, since it was 7
0000 1000 0001 0101 0101   1000000000000000   Shift left (13th)
0000 1011 0001 0101 0101   1000000000000000   Add 3 to 103, since it was 8
0000 1011 0001 1000 0101   1000000000000000   Add 3 to 101, since it was 5
0000 1011 0001 1000 1000   1000000000000000   Add 3 to 100, since it was 5
0001 0110 0011 0001 0001   0000000000000000   Shift left (14th)
0001 1001 0011 0001 0001   0000000000000000   Add 3 to 103, since it was 6
0011 0010 0110 0010 0010   0000000000000000   Shift left (15th)
0011 0010 1001 0010 0010   0000000000000000   Add 3 to 102, since it was 6
0110 0101 0010 0100 0100   0000000000000000   Shift left (16th)
   6    5    2    4    4
            BCD

Se han realizado dieciséis turnos, 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 paramétrica de Verilog del convertidor binario a BCD de doble incursión 

// parametric Verilog implementation of the double dabble binary to BCD converter
// for the complete project, see
// https://github.com/AmeerAbdelhadi/Binary-to-BCD-Converter

module bin2bcd
 #( parameter                W = 18)  // input width
  ( input      [W-1      :0] bin   ,  // binary
    output reg [W+(W-4)/3:0] bcd   ); // bcd {...,thousands,hundreds,tens,ones}

  integer i,j;

  always @(bin) begin
    for(i = 0; i <= W+(W-4)/3; i = i+1) bcd[i] = 0;     // initialize with zeros
    bcd[W-1:0] = bin;                                   // initialize with input vector
    for(i = 0; i <= W-4; i = i+1)                       // iterate on structure depth
      for(j = 0; j <= i/3; j = j+1)                     // iterate on structure width
        if (bcd[W-i+4*j -: 4] > 4)                      // if > 4
          bcd[W-i+4*j -: 4] = bcd[W-i+4*j -: 4] + 4'd3; // add 3
  end

endmodule
Implementación paramétrica de Verilog del binario de doble incursión a BCD converte, ejemplo de 18 bits.
Implementación paramétrica de Verilog del convertidor binario a BCD de doble incursión, ejemplo de 18 bits.


Invertir doble incursión

El algoritmo es completamente reversible. Al aplicar el algoritmo de doble penetración inverso, un número BCD se puede convertir a binario. La inversión del algoritmo se realiza invirtiendo los pasos principales del algoritmo:

Los pasos principales de los algoritmos
Doble incursión
(binario a BCD) 		Invertir doble incursión
(BCD a binario)
Para cada grupo de entrada de cuatro bits:
   Si grupo> = 5 sume 3 al grupo
Cambio a la izquierda en los dígitos de salida 		Cambio a la derecha en el binario de salida
Para cada grupo de cuatro bits de entrada:
   Si grupo> = 8 reste 3 del grupo

Ejemplo de doble incursión inversa

El algoritmo de doble incursión inversa, realizado en los tres dígitos BCD 2-4-3, se ve así: 

    BCD Input      Binary 
                   Output
   2    4    3
 0010 0100 0011   00000000   Initialization
 0001 0010 0001   10000000   Shifted right
 0000 1001 0000   11000000   Shifted right
 0000 0110 0000   11000000   Subtracted 3 from 2nd group, because it was 9
 0000 0011 0000   01100000   Shifted right
 0000 0001 1000   00110000   Shifted right
 0000 0001 0101   00110000   Subtracted 3 from 3rd group, because it was 8
 0000 0000 1010   10011000   Shifted right
 0000 0000 0111   10011000   Subtracted 3 from 3rd group, because it was 10
 0000 0000 0011   11001100   Shifted right
 0000 0000 0001   11100110   Shifted right
 0000 0000 0000   11110011   Shifted right
==========================
                       24310

Histórico

En la década de 1960, el término doble incursión 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. 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.

Ver también

Referencias

Otras lecturas