Double fušovat - Double dabble

v počítačová věda, dvojité fušování algoritmus slouží k převodu binární čísla do binárně kódované desetinné místo (BCD) notace.[1][2] To je také známé jako shift-and-add -3 algoritmus, a lze je implementovat pomocí malého počtu bran v počítačovém hardwaru, ale na úkor vysokých latence.[3]

Algoritmus

Algoritmus funguje následovně:

Předpokládejme, že původní číslo, které má být převedeno, je uloženo v a Registrovat to je n bity široké. Vyhraďte si dostatečně široký stírací prostor, který udrží původní číslo i jeho BCD zastoupení; n + 4×strop(n/3) bitů bude dost. Uložení každé desítkové číslice trvá binárně maximálně 4 bity.

Potom 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 Desítky Originální 0010 0100 0011 11110011

Výše uvedený diagram ukazuje binární reprezentaci 24310 v původním registru a BCD reprezentace 243 nalevo.

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 n krá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řenáší“ 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 více, přidají se tři, aby se zajistilo, že hodnota „nese“ v základu 10.

Algoritmus double-dabble, provedený na hodnotě 24310, vypadá takto:

0000 0000 0000 11110011 Inicializace 0000 0000 0001 11100110 Shift0000 0000 0011 11001100 Shift0000 0000 0111 10011000 Shift0000 0000 1010 10011000 Přidat 3 k ONES, protože to bylo 70000 0001 0101 00110000 Shift0000 0001 1000 00110000 Přidat 3 k ONES, protože 00 bylo 0 0000 11000000 Shift0000 1001 0000 11000000 Přidejte 3 k TENS, protože to bylo 60001 0010 0001 10000000 Shift0010 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 6524410.

 104  103  102   101  100    Původní binární 0000 0000 0000 0000 0000 1111111011011100 Inicializace 0000 0000 0000 0000 0001 1111110110111000 Posun doleva (1.) 0000 0000 0000 0000 0011 1111101101110000 Posun doleva (2.) 0000 0000 0000 0000 0111 1111011011100000 Posun vlevo (3.)0, protože to bylo 70000 0000 0000 0001 0101 1110110111000000 Posun vlevo (4.) 0000 0000 0000 0001 1000 1110110111000000 Přidat 3 až 100, protože to bylo 50000 0000 0000 0011 0001 1101101110000000 Posun vlevo (5.) 0000 0000 0000 0110 0011 1011011100000000 Posun vlevo (6.) 0000 0000 0000 1001 0011 1011011100000000 Přidat 3 až 101, protože to bylo 60000 0000 0001 0010 0111 0110111000000000 Posun doleva (sedmý) 0000 0000 0001 0010 1010 0110111000000000 Přidat 3 až 100, protože to bylo 70000 0000 0010 0101 0100 1101110000000000 Posun vlevo (8.) 0000 0000 0010 1000 0100 1101110000000000 Přidat 3 až 101, protože to bylo 50000 0000 0101 0000 1001 1011100000000000 Posun doleva (9.) 0000 0000 1000 0000 1001 1011100000000000 Přidat 3 až 102, protože to bylo 50000 0000 1000 0000 1100 1011100000000000 Přidejte 3 k 100, protože to bylo 90000 0001 0000 0001 1001 0111000000000000 Posun doleva (10.) 0000 0001 0000 0001 1100 0111000000000000 Přidat 3 k 100, protože to bylo 90000 0010 0000 0011 1000 1110000000000000 Posun doleva (11.) 0000 0010 0000 0011 1011 1110000000000000 Přidat 3 k 100, protože to bylo 80000 0100 0000 0111 0111 1100000000000000 Posunout doleva (12.) 0000 0100 0000 1010 0111 1100000000000000 Přidat 3 k 101, protože to bylo 70000 0100 0000 1010 1010 1100000000000000 Přidejte 3 k 100, protože to bylo 70000 1000 0001 0101 0101 1000000000000000 Posun doleva (13.) 0000 1011 0001 0101 0101 1000000000000000 Přidat 3 k 103, protože to bylo 80000 1011 0001 1000 0101 1000000000000000 Přidejte 3 k 101, protože to bylo 50000 1011 0001 1000 1000 1000000000000000 Přidejte 3 až 100, protože to bylo 50001 0110 0011 0001 0001 0000000000000000 Posun doleva (14.) 0001 1001 0011 0001 0001 0000000000000000 Přidat 3 k 103, protože to bylo 60011 0010 0110 0010 0010 0000000000000000 Posun doleva (15.) 0011 0010 1001 0010 0010 0000000000000000 Přidat 3 k 102, protože to bylo 60110 0101 0010 0100 0100 0000000000000000 Posun doleva (16.) 6 5 2 4 4 BCD

Bylo provedeno šestnáct směn, takže algoritmus končí. Desetinná hodnota číslic BCD je: 6 * 104 + 5*103 + 2*102 + 4*101 + 4*100 = 65244.

Parametrická implementace Verilogu převaděče binárních dvojitých signálů na BCD[4]

// parametrická implementace Verilogu převaděče binárních dvojitých dat na BCD// celý projekt viz// https://github.com/AmeerAbdelhadi/Binary-to-BCD-Convertermodul bin2bcd #( parametr                Ž = 18)  // vstupní šířka  ( vstup      [Ž-1      :0] zásobník   ,  // binární    výstup reg [Ž+(Ž-4)/3:0] bcd   ); // bcd {..., tisíce, stovky, desítky, jedny}  celé číslo i,j;  vždy @(zásobník) začít    pro(i = 0; i <= Ž+(Ž-4)/3; i = i+1) bcd[i] = 0;     // inicializovat s nulami    bcd[Ž-1:0] = zásobník;                                   // inicializace pomocí vstupního vektoru    pro(i = 0; i <= Ž-4; i = i+1)                       // iterace o hloubce struktury      pro(j = 0; j <= i/3; j = j+1)                     // iterace na šířku struktury        -li (bcd[Ž-i+4*j -: 4] > 4)                      // pokud> 4          bcd[Ž-i+4*j -: 4] = bcd[Ž-i+4*j -: 4] + 4„d3; // přidat 3  konecendmodul
Parametrická implementace Verilogu dvojitého binárního binárního převodu na BCD, 18bitový příklad.
Parametrická implementace verilogu převaděče binárních dvojitých signálů na BCD, příklad 18 bitů.[5]


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:

Základní kroky algoritmů
Double fušovat
(Binární na BCD)		Reverzní dvojité fušování
(BCD na binární)
Pro každou skupinu vstupu čtyři bity:
Pokud skupina> = 5, přidejte 3 do skupiny
Posun doleva do výstupních číslic		Posun doprava do binárního výstupu
Pro každou skupinu čtyř vstupních bitů:
Pokud skupina> = 8 odečtěte 3 ze skupiny

Příklad obráceného dvojitého fušování

Algoritmus reverzního dvojitého dablování, prováděný na třech číslech BCD 2-4-3, vypadá takto:

    Vstup BCD Binární výstup 2 4 3 0010 0100 0011 00000000 Inicializace 0001 0010 0001 10000000 Posun doprava 0000 1001 0000 11000000 Posunuto vpravo 0000 0110 0000 11000000 Odečteno 3 od 2. skupiny, protože to bylo 9 0000 0011 0000 01100000 Posun doprava 0000 0001 1000   00110000 Posunuto vpravo 0000 0001 0101   00110000 Odečteno 3 od 3. skupiny, protože to bylo 8 0000 0000 1010   10011000 Posun doprava 0000 0000 0111   10011000 Odečteno 3 od 3. skupiny, protože to bylo 10 0000 0000 0011 11001100 Posun doprava 0000 0000 0001 11100110 Posun doprava 0000 0000 0000 11110011 Posun doprava ====================== ===== 24310

C implementace

Algoritmus double dabble může při implementaci vypadat takto C. Všimněte si, že tato implementace je navržena k převodu "vstupního registru" jakékoli šířky tím, že jako parametr vezmeme pole a vrátíme a dynamicky přiděleno tětiva. Všimněte si také, že tato implementace neukládá explicitní kopii vstupního registru v jeho pomocném prostoru, jak to popisoval algoritmus; kopírování vstupního registru do nulového prostoru bylo jen a pedagogický přístroj.

#zahrnout <stdio.h>#zahrnout <stdlib.h>#zahrnout <string.h>/*   Tato funkce přebírá pole n celých čísel bez znaménka,   každý drží hodnotu v rozsahu [0, 65535],   představující číslo v rozsahu [0, 2 ** (16n) -1].   arr [0] je nejvýznamnější „číslice“.   Tato funkce vrací nové pole obsahující dané   číslo jako řetězec desetinných číslic.   Z důvodu stručnosti tento příklad předpokládá, že   calloc a realloc nikdy nezklame.*/prázdnota double_dabble(int n, konst nepodepsaný int *přílet, char **výsledek){    int nbits = 16*n;         / * délka příchodu v bitech * /    int nscratch = nbits/3;   / * délka škrábání v bajtech * /    char *poškrábat = calloc(1 + nscratch, velikost *poškrábat);    int i, j, k;    int úsměv = nscratch-2;    / * optimalizace rychlosti * /    pro (i=0; i < n; ++i) {        pro (j=0; j < 16; ++j) {            / * Tento bit bude posunut vpravo. * /            int shifted_in = (přílet[i] & (1 << (15-j)))? 1: 0;            / * Přidejte 3 všude, kde jsou škrábance [k]> = 5. * /            pro (k=úsměv; k < nscratch; ++k)              poškrábat[k] += (poškrábat[k] >= 5)? 3: 0;            / * Posuňte škrábání doleva o jednu pozici. * /            -li (poškrábat[úsměv] >= 8)              úsměv -= 1;            pro (k=úsměv; k < nscratch-1; ++k) {                poškrábat[k] <<= 1;                poškrábat[k] &= 0xF;                poškrábat[k] |= (poškrábat[k+1] >= 8);            }            / * Posunutí nového bitu od arr. * /            poškrábat[nscratch-1] <<= 1;            poškrábat[nscratch-1] &= 0xF;            poškrábat[nscratch-1] |= shifted_in;        }    }    / * Odstraňte úvodní nuly z nuly. * /    pro (k=0; k < nscratch-1; ++k)      -li (poškrábat[k] != 0) přestávka;    nscratch -= k;    memmove(poškrábat, poškrábat+k, nscratch+1);    / * Převede stírací prostor z číslic BCD na ASCII. * /    pro (k=0; k < nscratch; ++k)      poškrábat[k] += '0';    / * Změnit velikost a vrátit výsledný řetězec. * /    *výsledek = realloc(poškrábat, nscratch+1);    vrátit se;}/*   Tento testovací ovladač by měl tisknout následující desetinná čísla:   246   16170604   1059756703745*/int hlavní(prázdnota){    nepodepsaný int přílet[] = { 246, 48748, 1 };    char *text = NULA;    int i;    pro (i=0; i < 3; ++i) {        double_dabble(i+1, přílet, &text);        printf("% s", text);        volný, uvolnit(text);    }    vrátit se 0;}

Implementace VHDL

knihovna IEEE;použití IEEE.STD_LOGIC_1164.VŠECHNO;použití IEEE.numeric_std.Všechno;subjekt bin2bcd_12bit je    Přístav ( binIN : v  STD_LOGIC_VECTOR (11 dolů 0);           ty : ven  STD_LOGIC_VECTOR (3 dolů 0);           desítky : ven  STD_LOGIC_VECTOR (3 dolů 0);           stovky : ven  STD_LOGIC_VECTOR (3 dolů 0);           tisíce : ven  STD_LOGIC_VECTOR (3 dolů 0)          );konec bin2bcd_12bit;architektura Behaviorální z bin2bcd_12bit jezačítbcd1: proces(binIN)  - dočasná proměnná  proměnná tepl : STD_LOGIC_VECTOR (11 dolů 0);    - proměnná pro uložení výstupního BCD čísla  - organizováno následovně  - tisíce = BCD (15 až 12)  - stovky = bcd (11 až 8)  - desítky = bcd (7 až 4)  - jednotky = bcd (3 až 0)  proměnná bcd : NEPODEPSANÝ (15 dolů 0) := (ostatní => '0');  - od  - https://en.wikipedia.org/wiki/Double_dabble    začít    - vynulujte proměnnou bcd    bcd := (ostatní => '0');        - načíst vstup do dočasné proměnné    tepl(11 dolů 0) := binIN;        - cyklus 12krát, protože máme 12 vstupních bitů    - to by mohlo být optimalizováno, nemusíme kontrolovat a přidávat 3 pro     - první 3 iterace, protože počet nikdy nemůže být> 4    pro i v 0 na 11 smyčka          -li bcd(3 dolů 0) > 4 pak         bcd(3 dolů 0) := bcd(3 dolů 0) + 3;      konec -li;            -li bcd(7 dolů 4) > 4 pak         bcd(7 dolů 4) := bcd(7 dolů 4) + 3;      konec -li;          -li bcd(11 dolů 8) > 4 pak          bcd(11 dolů 8) := bcd(11 dolů 8) + 3;      konec -li;          - tisíce nemohou být> 4 pro 12bitové vstupní číslo      - takže nemusíte dělat nic do horních 4 bitů bcd          - posunout bcd doleva o 1 bit, zkopírovat MSB teploty do LSB bcd      bcd := bcd(14 dolů 0) & tepl(11);          - teplota posunu doleva o 1 bit      tepl := tepl(10 dolů 0) & '0';        konec smyčka;     - nastavit výstupy    ty <= STD_LOGIC_VECTOR(bcd(3 dolů 0));    desítky <= STD_LOGIC_VECTOR(bcd(7 dolů 4));    stovky <= STD_LOGIC_VECTOR(bcd(11 dolů 8));    tisíce <= STD_LOGIC_VECTOR(bcd(15 dolů 12));    konec proces bcd1;              konec Behaviorální;

Testovací stůl VHDL

KNIHOVNA tj;POUŽITÍ tjee.std_logic_1164.VŠECHNO; ENTITY bin2bcd_12bit_test_file JEKONEC bin2bcd_12bit_test_file; ARCHITEKTURA chování Z bin2bcd_12bit_test_file JE      - Deklarace komponent pro testovanou jednotku (UUT)     SOUČÁSTKA bin2bcd_12bit    PŘÍSTAV(         binIN : V  std_logic_vector(11 dolů 0);         ty : VEN  std_logic_vector(3 dolů 0);         desítky : VEN  std_logic_vector(3 dolů 0);         stovky : VEN  std_logic_vector(3 dolů 0);	 tisíce : VEN  std_logic_vector(3 dolů 0)        );    KONEC SOUČÁSTKA;      - UPOZORNĚNÍ: Vezměte prosím na vědomí, že ve zkušebním stolku není potřeba hodinový signál, protože design je přísný  - kombinační (nebo souběžný, na rozdíl od implementace C, která je sekvenční).  - Tyto hodiny jsou zde pouze pro simulaci; můžete vynechat všechny reference a procesy hodin a použít "počkat na ... ns"  - prohlášení místo.   --Vstupy   signál binIN : std_logic_vector(11 dolů 0) := (ostatní => '0');   signál clk : std_logic := '0';  - lze vynechat 	--Výstupy   signál ty : std_logic_vector(3 dolů 0);   signál desetiny : std_logic_vector(3 dolů 0);   signál stovky : std_logic_vector(3 dolů 0);   signál tisíce : std_logic_vector(3 dolů 0);   - Definice periody hodin   konstantní clk_period : čas := 10 ns;  - lze vynechat   - Různé   signál full_number : std_logic_vector(15 dolů 0);ZAČÍT 	- Vytvoření instance testované jednotky (UUT)   uut: bin2bcd_12bit PŘÍSTAV MAPA (          binIN => binIN,          ty => ty,          desítky => desetiny,          stovky => stovky,	  tisíce => tisíce        );   - Definice hodinového procesu - celý proces lze vynechat   clk_process :proces   začít		clk <= '0';		Počkejte pro clk_period/2;		clk <= '1';		Počkejte pro clk_period/2;   konec proces;    - Spojte signály pro plný počet   full_number <= tisíce & stovky & desetiny & ty;   - Stimulační proces   stim_proc: proces   začít		      - podržte resetovací stav po dobu 100 ns.      Počkejte pro 100 ns;	      Počkejte pro clk_period*10;      - zde vložte podnět 		- měl by vrátit 4095		binIN <= X „FFF“;		Počkejte pro clk_period*10;  tvrdit full_number = x "4095" vážnost chyba;  - použijte "počkat na ... ns;"		- by měl vrátit 0		binIN <= X "000";		Počkejte pro clk_period*10;  tvrdit full_number = x "0000" vážnost chyba;		- měl by se vrátit 2748		binIN <= X „ABC“;		Počkejte pro clk_period*10;  tvrdit full_number = x "2748" vážnost chyba;				      Počkejte;   konec proces;KONEC;

Optimalizovaný úryvek Bin2BCD pro SBA (VHDL)

[6]

- / SBA: Podrobnosti o programu - ========================================== ========== -- Snippet: 16bitový binární převodník BCD- Autor: Miguel A. Risco-Castillo- Popis: Převodník 16 bitů na BCD pomocí algoritmu „Double Dabble“.- Před zavoláním musíte vyplnit „bin_in“ příslušnou hodnotou, po zavolání,- úryvek vložený do proměnné „bcd_out“ je výsledkem převodu BCD.- Umístěte úryvek do části rutiny uživatelského programu.- / SBA: Podrobnosti o ukončení programu ------------------------------------------ ---------- / SBA: Uživatelské registry a konstanty - ====================================== - -  proměnná bin_in  : nepodepsaný(15 dolů 0);      - 16bitový vstupní registr  proměnná bcd_out : nepodepsaný(19 dolů 0);      - 20bitový výstupní registr- / SBA: Registry a konstanty koncových uživatelů --------------------------------------- / SBA: User Program - ========================================== ============== -- / L: Bin2BCD=> bcd_out := (ostatní=>'0');   -li bin_in=0 pak SBARet; konec -li; - pokud je nula, pak se vraťte=> bcd_out(2 dolů 0) := bin_in(15 dolů 13); - shl 3   bin_in := bin_in(12 dolů 0) & "000";=> pro j v 0 na 12 smyčka     pro i v 0 na 3 smyčka - pro nibble 0 až 3, poslední nibble není třeba upravovat       -li bcd_out(3+4*i dolů 4*i)>4 pak - je okusovat> 4?         bcd_out(3+4*i dolů 4*i):=bcd_out(3+4*i dolů 4*i)+3; - přidejte 3 k okusování       konec -li;     konec smyčka;     bcd_out := bcd_out(18 dolů 0) & bin_in(15); --shl     bin_in := bin_in(14 dolů 0) & '0';   konec smyčka;   SBARet; - návrat do hlavního programu- / SBA: Program pro koncového uživatele ------------------------------------------ ------------

Historický

V roce 1960, termín dvojité fušování byl také použit pro jiný mentální algoritmus, používaný programátory 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.[7] 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é

Reference

  1. ^ Gao, Shuli; Al-Khalili, D .; Chabini, N. (červen 2012), „Vylepšený sčítač BCD s využitím FPGA 6-LUT“, 10. mezinárodní konference nových obvodů a systémů IEEE (NEWCAS 2012), s. 13–16, doi:10.1109 / NEWCAS.2012.6328944
  2. ^ "Převodník z binárního na BCD:" Algoritmus převodu dvojitého binárního převodu z binárního na BCD"" (PDF). Archivovány od originál (PDF) dne 31.01.2012.
  3. ^ Véstias, Mario P .; Neto, Horatio C. (březen 2010), „Paralelní desítkové multiplikátory využívající binární multiplikátory“, VI Southern Programmable Logic Conference (SPL 2010), str. 73–78, doi:10.1109 / SPL.2010.5483001
  4. ^ Abdelhadi, Ameer (07.07.2019), Převaděč AmeerAbdelhadi / Binary-to-BCD, vyvoláno 2020-03-03
  5. ^ Abdelhadi, Ameer (07.07.2019), Převaděč AmeerAbdelhadi / Binary-to-BCD, vyvoláno 2020-03-03
  6. ^ „SBA“. sba.accesus.com. Citováno 2016-12-31. Jednoduchá architektura autobusů
  7. ^ Godse, Deepali A .; Godse, Atul P. (2008). Digitální techniky. Pune, Indie: Technické publikace. str. 4. ISBN  978-8-18431401-4.

Další čtení