Double dabble - Double dabble
Ve vědě o počítačích je dvojitý Dabble algoritmus se používá pro převod binárních čísel na BCD (BCD) notace. Je také známý jako algoritmus shift-and-add -3 a lze jej implementovat pomocí malého počtu bran v počítačovém hardwaru, ale na úkor vysoké latence .
Algoritmus
Algoritmus funguje následovně:
Předpokládejme, že původní počet má být převedena je uložena v registru , který je n bitů široká. Vyhraďte si dostatečně široký stírací prostor, který udrží původní číslo i jeho BCD zastoupení; n + 4 × ceil ( n / 3) bitů bude stačit. Uložení každé desítkové číslice trvá binárně maximálně 4 bity.
Poté rozdělte stírací prostor na BCD číslice (vlevo) a původní registr (vpravo). Například pokud je původní číslo, které má být převedeno, široké osm bitů, stírací prostor by byl rozdělen takto:
100s Tens Ones Original 0010 0100 0011 11110011
Výše uvedený diagram ukazuje binární reprezentaci 243 10 v původním registru a BCD reprezentaci 243 vlevo.
Zápisný prostor je inicializován na všechny nuly a poté je hodnota, která má být převedena, zkopírována do prostoru „původního registru“ vpravo.
0000 0000 0000 11110011
Algoritmus pak iteruje nkrát . Při každé iteraci se jakákoli číslice BCD, která je alespoň 5 (0101 v binární podobě), zvýší o 3 (0011); pak je celý stírací prostor posunut o jeden bit doleva. Přírůstek zajišťuje, že hodnota 5, inkrementovaná a posunutá doleva, se stane 16 (10 000), čímž se správně „přenese“ na další číslici BCD.
Algoritmus v podstatě funguje tak, že zdvojnásobuje hodnotu BCD na levé straně každé iterace a přidává buď jednu, nebo nulu podle původního bitového vzoru. Řazení doleva splňuje oba úkoly současně. Pokud je některá číslice pět nebo vyšší, přidají se tři, aby se zajistilo, že hodnota „nese“ v základně 10.
Algoritmus double-dabble, provedený na hodnotě 243 10 , vypadá takto:
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
Nyní bylo provedeno osm směn, takže algoritmus končí. Číslice BCD nalevo od prostoru „původního registru“ zobrazují BCD kódování původní hodnoty 243.
Další příklad algoritmu double dabble - hodnota 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
Bylo provedeno šestnáct směn, takže algoritmus končí. Desetinná hodnota číslic BCD je: 6 * 10 4 + 5 * 10 3 + 2 * 10 2 + 4 * 10 1 + 4 * 10 0 = 65244.
Parametrická implementace Verilogu převaděče binárních dvojitých signálů na BCD
// 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
Reverzní dvojité fušování
Algoritmus je plně reverzibilní. Použitím algoritmu reverzního dvojitého dablování lze číslo BCD převést na binární. Obrácení algoritmu se provádí obrácením základních kroků algoritmu:
| Double dabble (binární na BCD) |
Reverzní dvojitý dabble (BCD na binární) |
|---|---|
| Pro každou skupinu vstupu čtyři bity: Pokud skupina> = 5, přidejte 3 do skupiny Levý posun do výstupních číslic |
Posun doprava do výstupního binárního souboru Pro každou skupinu čtyř vstupních bitů: Pokud skupina> = 8 odečtěte 3 od skupiny |
Příklad obráceného dvojitého fušování
Algoritmus reverzního dvojitého dablování, provedený na třech číslech BCD 2-4-3, vypadá takto:
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
Historický
V šedesátých letech se termín double dabble používal také pro jiný mentální algoritmus, který programátoři používali k převodu binárního čísla na desítkové. Provádí se čtením binárního čísla zleva doprava, zdvojnásobením, pokud je další bit nula, a zdvojnásobením a přidáním jednoho, pokud je další bit jedna. Ve výše uvedeném příkladu 11110011 by myšlenkový proces byl: „jedna, tři, sedm, patnáct, třicet, šedesát, sto dvacet jedna, dvě stě čtyřicet tři“, stejný výsledek jako výše.
Viz také
- Vyhledávací tabulka - alternativní přístup k provedení převodu
Reference
Další čtení
- Falconer, Charles "Chuck" B. (2004-04-16). "Vysvětlení konverzního algoritmu Double-Dabble Bin-BCD" . Archivovány od originálu na 2009-03-25.