Násobičky, Boothovo překódování INP Demonstrační cvičení 7
Obsah Princip násobení Sekvenční a kombinační násobička Kombinační násobičky ve VHDL Násobení se znaménkem (FX) Boothovo překódování, VHDL
Násobení s pevnou řádovou čárkou
Sekvenční násobička
– (Postupně) dodáme bity operandů A a B, přivedeme hodinový signál CLK a po k taktech získáme součin C – Zpoždění je dáno max. možnou frekvencí CLK a počtem taktů nutných k výpočtu – Výhoda: plocha na čipu, Nevýhoda: rychlost
Kombinační násobička • Dodáme operandy A a B a čekáme na součin C • Zpoždění je obvykle dáno zpožděním logiky na cestě k nejvyššímu bitu součinu • Výhoda: rychlost, Nevýhoda: plocha 12 na čipu
6
16
2
1
1 7 7
6
10
12
Výsledné zpoždění 16x zpoždění logického členu
4
8
10
4
5
8
14
12
9
16
14
12
9
5
2
1
Násobička s uchováním přenosu ve VHDL entity MULT is port ( A, B : in std_logic_vector(3 downto 0); PROD : out std_logic_vector(7 downto 0)); end MULT; architecture RTL1 of MULT is constant N : integer := 4; subtype p1ary is std_logic_vector(N-1 downto 0); type pary is array(0 to N) of p1ary; signal PP, PC, PS : pary; component FA -– full adder port ( A, B, CI : in std_logic; S, COUT : out std_logic); end component; component ANDG –- and gate port ( A, B : in std_logic; C : out std_logic); end component;
subtype = omezená podmnožina typu
PP-partial product PC-partial carry PS-partial sum j-row number k-column number
begin pgen : for j in 0 to N-1 generate pgen1 : for k in 0 to N-1 generate and0 : ANDG port map ( A => A(k), B => B(j), C => PP(j)(k)); end generate; PC(0)(j) <= '0'; end generate; PS(0) <= PP(0); PROD(0) <= PP(0)(0); -- nultý bit výsledku
vytvoříme částečné součiny
addr : for j in 1 to N-1 generate addc : for k in 0 to N-2 generate fa0 : FA port map ( A => PP(j)(k), B => PS(j-1)(k+1), CI => PC(j-1)(k), S => PS(j)(k), COUT => PC(j)(k)); end generate; PROD(j) <= PS(j)(0); PS(j)(N-1) <= PP(j)(N-1); end generate; PC(N)(0) <= '0';
begin pgen : for j in 0 to N-1 generate pgen1 : for k in 0 to N-1 generate and0 : ANDG port map ( A => A(k), B => B(j), C => PP(j)(k)); end generate; PC(0)(j) <= '0'; end generate; PS(0) <= PP(0); PROD(0) <= PP(0)(0); -- nultý bit výsledku addr : for j in 1 to N-1 generate Sčítačky řádků addc : for k in 0 to N-2 generate 1..N-1 fa0 : FA port map ( A => PP(j)(k), B => PS(j-1)(k+1), CI => PC(j-1)(k), S => PS(j)(k), COUT => PC(j)(k)); PP-partial product end generate; PC-partial carry PROD(j) <= PS(j)(0); PS(j)(N-1) <= PP(j)(N-1); PS-partial sum end generate; j-row number PC(N)(0) <= '0';
k-column number
Sčítačky v posledním řádku addlast : for k in 1 to N-1 generate fa1 : FA port map ( A => PS(N-1)(k), B => PC(N-1)(k-1), CI => PC(N)(k-1), S => PS(N)(k), COUT => PC(N)(k)); end generate; PROD(2*N-1) <= PC(N)(N-1); PROD(2*N-2 downto N) <= PS(N)(N-1 downto 1); end RTL1;
PP-partial product PC-partial carry PS-partial sum j-row number k-column number
Plocha a doba výpočtu • Předpokládejme násobení N-bitů x M-bitů • Potřebujeme (N-1)*M sčítaček (některé mohou být poloviční) • Zpoždění (předpokládejme, že zpoždění 1 FA odpovídá zpoždění 2 hradel) + 1 x hradlo AND (první částečný součin) + M-1 řádků sčítaček + N-1 sčítaček v posledním řádku
+ Celkem 2*(M-1 + N-1) + 1 [zpoždění hradla]
Násobení čísel se znaménkem -4*-14 na 4b+1b na znaménko => 2x5b => zn. až do 10b !!! (-4) (-14)
1111111100 1111110010 00000 1111111100 00000 00000 1111111100 1111111100 Nutnost šířit znaménko dílčích 1111111100 součinů a sčítat dílčí součiny 1111111100 i pro bity rozšířeného 1111111100 znaménka násobitele. 1111111100 0 0000111000b (+56d)
Možné řešení: použití Boothova překódování
Boothovo překódování po 1 bitu (radix 2) • Překódujeme násobitel podle tabulky: překódovávaný bit bit vpravo kód 0 0 0 0 1 1 1 0 -1 1 1 0
• Příklad (4b+1b zn.): -4 x –14 -4 = 11100, +4 = 00100, -14 = 10010
Překódování -14: 100100 -> -1 0 1 -1 0 111 00 (-4) -101-10 (-7) 0 (0) 00100 (+4) 1111100 (-4) 0 (0) 00100 (+4) 1000111000(=56)
=> 5 součtů namísto deseti
Boothovo překódování po 2 bitech (radix 4) překódovávané bity bit vpravo kód 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 2 1 0 0 -2 1 0 1 -1 1 1 0 -1 1 1 1 0
Musíme přejít na sudý počet bitů (6) umožňující zobrazit též dvojnásobky násobence.
Př. 7 x –10: 7=000111, -10=110110
Překódujeme násobitel: -1 2-2 -7=111001 14=001110 -14=110010
000111 (7) -1 2-2 (-10) 11111110010 (-14) posun o 2 bity 000001110 (+14) 1111001 (-7) 111110111010(-70)
Vroubení znaménka 000111 1-1 2-2 10110010 11001110 10111001 111110111010
(7) (-10) (-14) (+14) (-7) (-70)
Boothovo překódování s radixem 4 ve VHDL library IEEE; use IEEE.std_logic_1164.all; use IEEE.std_logic_unsigned.all; entity RECODER is port ( DIN : in std_logic_vector(15 downto 0); BIT3 : in std_logic_vector( 2 downto 0); DOUT : out std_logic_vector(16 downto 0)); end RECODER; architecture RTL of RECODER is constant N : integer := 16; subtype bitn1 is std_logic_vector(N downto 0); function COMP2 (D : in bitn1) return bitn1 is variable Dn : bitn1; begin Dn := not D; return(Dn+1); Příklad funkce ve end COMP2;
VHDL (vrací dvojkový doplněk D)
Boothovo překódování s radixem 4 ve VHDL (2) begin process (DIN, BIT3) begin case BIT3 is when "001" | "010" => DOUT <= DIN(N-1) & DIN; when "101" | "110" => DOUT <= COMP2(DIN(N-1) & DIN); when "100" => DOUT <= COMP2(DIN & '0'); when "011" => DOUT <= DIN & '0'; překódovávané bity bit vpravo kód when others => 0 0 DOUT <= (DOUT'range => '0'); 0 0 0 0 1 1 end case; 0 1 0 1 end process; 0 1 1 2 end RTL; 1 0 0 -2 1 0 1 -1 1 1 0 -1 1 1 1 0
Boothovo překódování: radix 16 Postup podle obecného Boothova algoritmu: 1. Zopakujeme nejvyšší bit skupiny 2. K takto získané hodnotě přičteme hodnotu nejvyššího bitu skupiny vpravo od překódovávané skupiny 3. Výsledná hodnota je binárním vyjádřením relativní číslice Úloha: překódujte číslo -600 na 12 bitech -600 = 1 1 0 1 1 0 1 0 1 0 0 0
Literatura • Drábek, V.: Výstavba počítačů, skriptum VUT v Brně, 1995. • Chang, K. C.: Digital Design and Modeling with VHDL and Synthesis. • Chang, K. C.: Digital Systems Design with VHDL and Synthesis.
