Основна бинарна дивизија: алгоритам и ВХДЛ код

Week 3, continued (Јули 2019).

$config[ads_text] not found
Anonim

Основна бинарна дивизија: алгоритам и ВХДЛ код


Овај чланак ће прегледати основни алгоритам за бинарну подјелу.

На основу основног алгоритма за бинарну поделу ћемо размотрити у овом чланку, изводићемо блок дијаграм за имплементацију кола бинарне подјеле. Затим ћемо погледати графикон АСМД (алгоритамска државна машина са путањом података) и ВХДЛ код овог бинарног разделника.

Ресурси

Узмите у обзир провјеру чланака који сам објавио у прошлости, што вам могу помоћи да боље разумете ову тему:

  • Како написати ВХДЛ Опис једноставног алгоритма: Контролна стаза

  • Како написати ВХДЛ опис једноставног алгоритма: Путања података

Приступ папира и оловке за бинарну дивизију

Да почнемо, размотрите поделу 11000101 на 1010.

Као у децималној подели, можемо упоредити четири најзначајнија бита дивиденде (тј. 1100) са делитељем да пронађемо прву цифру количника. Радимо са бинарним бројевима, тако да цифре количника могу бити нула или једна.

Од 1100 је веће од 1010, прва цифра количника ће бити једна. Добијену цифру мора бити подељен од стране делитеља и резултат мора бити одузет од дивиденде. Дакле, имамо

Сада, требало би да напишемо следећи део дивиденде (приказан црвеном бојом) десно од разлике и наставимо процедуру баш као што радимо у децималној подели. Дакле, добијамо

Горе наведени пример показује децимални еквивалент параметара, као и слова која их представљају. Можемо проверити калкулације вредновањем $$ з = к \ тимес д + с $$ и то $$ с <д $$.

Да бисмо добили бољи увид у имплементацију алгоритма поделе, преписали смо горњи пример као:

Прво, делилац се одузима од четири најзначајнија бита дивиденде. Резултат овог одузимања, тј. 0010, приказан је плавом бојом.

Ми можемо замијенити четири МСБ-а дивиденде са 0010 и добити $$ с ^ {(0)} = 0010 0101 $$. Четири ЛСБс $$ с ^ {(0)} $$, које су исте као и четири ЛСБ-а дивиденде, приказане су црвеном бојом. Имајте на уму да више не требамо првобитну дивиденду и можемо је замијенити са $$ с ^ {(0)} $$. Са становишта имплементације то значи да можемо користити регистар који је изворно чувао вредност дивиденде да би се чувао $$ с ^ {(0)} $$.

За друго одузимање, делилац се помера десно за један бит. Након одузимања добијамо $$ с ^ {(1)} = 0010 0101 $$. Опет, битови добијени од одузимања су приказани плавом бојом, а неизмењени битови $$ с ^ {(0)} $$ су приказани црвеном бојом. Сада можемо да ажурирамо регистар дивиденде са $$ с ^ {(1)} $$.

Ова процедура се наставља до коначног одузимања у којој је ЛСБ помјереног дивисор усклађен са ЛСБ дивиденде. Након овог коначног одузимања, остатак ће бити мањи од делитеља.

Имајте на уму да, како настављамо са алгоритмом, битови великог реда с $$ с ^ {(.)} $$ терминима постају нули (у овом чланку користићемо $$ с ^ {(.)} $$ да се позивају на $$ с ^ {(и)} $$ термине где $$ и = 0, 1, 3, $$ и $$ 4 $$). Ово указује на то да неке битне позиције регистра дивиденде више неће бити потребне. У следећем одељку ћемо видети које битне позиције су редундантне. У горњим примјерима, битне позиције које се могу одбацити су подвучене.

Како имплементирати алгоритам дивизије "" срц = "// ввв.аллабоутцирцуитс.цом/уплоадс/артицлес/Фиг1м532018.пнг" />

Слика 1

На слици 1, резултат одузимања је приказан плавом бојом и битови разлике који су исти као и $$ с ^ {(.)} $$ појам су приказани црвеном бојом. Слично децималној подели, разлика ($$ р_3р_2р_1р_0 $$) је мања од делитеља ($$ р_3р_2р_1р_0 <д_3д_2д_1д_0 $$). Дакле, имамо

$$ с_ {МСБ} \ дотс с_ {м + 4} с_ {м + 3} м_2

То значи да $$ с_ {м + 4} $$ може бити нула, али сви битови лево од $$ с_ {м + 4} $$ су нули. Због тога, у сваком одузимању, потребан је само један додатни бит с $$ с ^ {(.)} $$ појмом лево од МСБ-а делитеља. У примеру претходног одељка, битне позиције које се могу одбацити су подвучене. Ово сугерише да, како наставимо са алгоритмом, можемо користити мањи и мањи регистар за чување $$ с ^ {(.)} $$ термина. Обично су празне локације овог регистра кориштене за чување квоциентних битова. Ово ће се размотрити за минут.

Поједностављени блок дијаграм за поделу осам бита броја четворо-битним бројем приказан је на слици 2. Деветобитни регистар, $$ з_8, \ дотс, з_0 $$, чува вредност дивиденде и четвероструки број, битни регистар, $$ д_3, \ дотс, д_0 $$, се користи за чување делитеља. $$ з_8 $$ је додатни бит који ће се користити за чување бита $$ с ^ {(.)} $$ појам лево од МСБ-а делитеља. На почетку алгоритма, овај бит је подешен на нулу.

Слика 2

У наставку са алгоритмом, садржај З регистра ће бити ажуриран (са резултатом одузимања) и пребачен на лево. После сваке смене, ЛСБ З регистра ће бити празан. Овај празан меморијски елемент ће се користити за чување количника који је управо добио.

Као и приступ папиру и оловком, можемо да упоредимо $$ з_8з_7з_6з_5з_4 $$ са $$ д_3д_2д_1д_0 $$ и одлучимо да ли квоциентни бит мора бити нула или један. То се ради помоћу блока "субтрактор и компаратор" на слици 2. Када $$ з_8з_7з_6з_5з_4 \ гек д_3д_2д_1д_0 $$, сигнал "цомп" ће бити логичан и јединица "контроле" ће сачувати квоциентни бит, што је један, у ЛСБ регистра З. Када $$ з_8з_7з_6з_5з_4 <д_3д_2д_1д_0 $$, добијени количник бит ће бити нула, а ЛСБ З регистра ће бити нула.

Осим тога, јединица "контроле" мора одлучити да ли је пет МСБ-ова регистра З потребно ажурирати или не. Сигнал "комп" може се користити и за доношење ове одлуке. На основу нашег нумеричког примера, знамо да, када $$ з_8з_7з_6з_5з_4 \ гек д_3д_2д_1д_0 $$, пет МСБс регистра З мора бити ажурирано са разликом $$ з_8з_7з_6з_5з_4 - д_3д_2д_1д_0 $$. Када $$ з_8з_7з_6з_5з_4 <д_3д_2д_1д_0 $$, није потребно ажурирање.

Као што је раније речено, пребацимо садржај З регистра у лево, а не померити делилац с десне стране.

Избегавање преоптерећења

Током последње одузимања алгоритма, ЛСБ дивиденде ће бити изнад ЛСБ-а делитеља (погледајте 5. одузимање нумеричког примера). То значи да ће вриједност која је напуњена на $$ з_0 $$ на почетку алгоритма бити на $$ з_4 $$ на крају алгоритма. Другим ријечима, примјеном слике 2, алгоритам подјеле ће обухватити укупно четири смјене. Знамо да ће меморијске локације које су напуштене из ових смјена користити за чување квоциентних битова. Дакле, квоциент мора бити мањи или једнак $$ 1111_2 = 15_ {10} $$. С обзиром на једначину $$ з = к \ тимес д + с $$, имамо

$$ з = к \ тимес д + с <(2 ^ 4-1) \ тимес д + с = 2 ^ 4 \ тимес д + с - д $$

Отуда, $$ з + (дс) <2 ^ 4 \ тимес д $$. Пошто је $$ дс $$ позитиван број, $$ 2 ^ 4 \ тимес д $$ мора бити већи од $$ з $$. Другим речима, на почетку алгоритма, морамо имати $$ з_8з_7з_6з_5з_4 <д_3д_2д_1д_0 $$, у супротном, коефицијент ће бити већи од $$ 1111_2 = 15_ {10} $$ и не можемо га представити на исправљеним локацијама З регистар.

Као што је горе речено, укупан број смена је познат по алгоритму поделе. Стога можемо користити бројач да бројимо број смена и утврдимо када је алгоритам завршен. Овај број ће се ресетовати на нулу на почетку алгоритма.

Алгоритам дивизије

Са блок дијаграмом на слици 2, морамо више пута обављати сљедеће радње:

  1. Учините дивиденду и делилац у З и Д регистре, респективно. Поништите $$ з_8 $$ на нулу. Осим тога, вредност бројача итерације подесите на нулу.
  2. Ако $$ з_8з_7з_6з_5з_4 <д_3д_2д_1д_0 $$, идите на корак 3 иначе поставите заставицу која означава стање преоптерећења и заврши алгоритам.
  3. Померите З регистар на лево од једног бита. Операција измене ће напустити ЛСБ регистра З. Ова празна локација меморије ће се користити за чување битног бројача добијеног у наредном кораку.
  4. Сравнить $$ з_8з_7з_6з_5з_4 $$ с $$ д_3д_2д_1д_0 $$:

    (а) Ако $$ з_8з_7з_6з_5з_4 \ гек д_3д_2д_1д_0 $$, подесите ЛСБ регистра З на један и ажурирајте пет МСБс регистра З са разликом $$ з_8з_7з_6з_5з_4 - д_3д_2д_1д_0 $$.

    (б) Ако $$ з_8з_7з_6з_5з_4 <д_3д_2д_1д_0 $$, подесите ЛСБ регистра З на нулу и не задржите пет МСБ-ова З регистра.

  5. Повећајте вредност бројача за један. Ако је бројач једнак четири, завршите алгоритам у супротном идите на корак 3.

АСМД графикон и ВХДЛ код

На основу ових корака, АСМД графикон од 16 бита може бити изведен 8-битним подјељењем као што је приказано на слици 3.

Слика 3

На овом дијаграму, "старт" је улаз који говори систему да покрене алгоритам. Када се прорачуни заврше, "реади" излаз ће бити постављен на високу логику како би означио крај алгоритма. Када се суочи са преливом, излаз "овфл" ће ићи на висок.

Стање "идле" учитава з_рег и д_рег регистре са дивидендом (м) и уносима дивисор (н), респективно. У овом стању иницијализује се иутер бројач (и_рег). Стање преоптерећења ће се проверити, а следеће стање ће бити изабрано.

Стање "схифт" помера садржај з_рег регистра лево од једног бита. Ово ће убацити нулу десно од садржаја з_рег. Међутим, вредност овог бита може се променити током следеће фазе алгоритма.

Стање "оп" упоређује регистре. Ако су девет МСБ з_рег веће или једнаке садржају д_рег, ЛСБ з_рег ће бити постављен на један, а девет МСБ з_рег ће се ажурирати са резултатом одузимања који је представљен са "суб". Ако је девет МСБ з_рег-а мање од садржаја д_реф, не морамо мијењати з_рег. Затим ће се бројач итера повећати за један и проверићемо број смена. Ако имамо осам смена, алгоритам је завршен, а следеће стање је "идле". Ако је број итерација мањи од осам, требало би да се вратимо у стање "схифт" и наставимо са осталим алгоритмом.

Да бисте прочитали више о изради АСМД графикона, погледајте ова два чланка: Како написати ВХДЛ опис једноставног алгоритма: Путања података и како написати ВХДЛ опис једноставног алгоритма: Контролна стаза.

Сада, имајући АСМД графикон, можемо написати ВХДЛ код алгоритма:

 1 library IEEE; 2 use IEEE.STD_LOGIC_1164.ALL; 3 use IEEE. NUMERIC_STD.ALL; 4 entity Divider is 5 Port (clk, reset : in STD_LOGIC; 6 start : in STD_LOGIC; 7 m : in STD_LOGIC_VECTOR (15 downto 0); -- Input for dividend 8 n : in STD_LOGIC_VECTOR (7 downto 0); -- Input for divisor 9 quotient : out STD_LOGIC_VECTOR (7 downto 0); -- Output for quotient 10 remainder : out STD_LOGIC_VECTOR (7 downto 0); -- Output for remainder 11 ready, ovfl : out STD_LOGIC); -- Indicates end of algorithm and overflow condition 12 end Divider; 13 architecture Behavioral of Divider is 14 -- Type for the FSM states 15 type state_type is (idle, shift, op); 16 -- Inputs/outputs of the state register and the z, d, and i registers 17 signal state_reg, state_next : state_type; 18 signal z_reg, z_next : unsigned(16 downto 0); 19 signal d_reg, d_next : unsigned(7 downto 0); 20 signal i_reg, i_next : unsigned(3 downto 0); 21 -- The subtraction output 22 signal sub : unsigned(8 downto 0); 23 begin 24 --control path: registers of the FSM 25 process(clk, reset) 26 begin 27 if (reset='1') then 28 state_reg <= idle; 29 elsif (clk'event and clk="1") then 30 state_reg <= state_next; 31 end if; 32 end process; 33 --control path: the logic that determines the next state of the FSM (this part of 34 --the code is written based on the green hexagons of Figure 3) 35 process(state_reg, start, m, n, i_next) 36 begin 37 case state_reg is 38 when idle => 39 if ( start="1" ) then 40 if ( m(15 downto 8) < n ) then 41 state_next <= shift; 42 else 43 state_next <= idle; 44 end if; 45 else 46 state_next49 state_next51 if ( i_next = "1000" ) then 52 state_next <= idle; 53 else 54 state_next <= shift; 55 end if; 56 end case; 57 end process; 58 --control path: output logic 59 ready <= '1' when state_reg=idle else 60 '0'; 61 ovfl = n ) ) else 62 '0'; 63 --control path: registers of the counter used to count the iterations 64 process(clk, reset) 65 begin 66 if (reset='1') then 67 i_reg '0' ); 68 elsif (clk'event and clk="1") then 69 i_reg77 i_next'0'); 78 79 when shift => 80 i_next83 i_next <= i_reg + 1; 84 end case; 85 end process; 86 --data path: the registers used in the data path 87 process(clk, reset) 88 begin 89 if ( reset="1" ) then 90 z_reg'0'); 91 d_reg'0'); 92 elsif ( clk'event and clk="1" ) then 93 z_reg <= z_next; 94 d_reg <= d_next; 95 end if; 96 end process; 97 --data path: the multiplexers of the data path (written based on the register 98 --assignments that take place in different states of the ASMD) 99 process( state_reg, m, n, z_reg, d_reg, sub) 100 begin 101 d_next104 z_next107 z_next109 if ( z_reg(16 downto 8) < ('0' & d_reg ) ) then 110 z_next <= z_reg; 111 else 112 z_next <= sub(8 downto 0) & z_reg(7 downto 1) & '1'; 113 end if; 114 end case; 115 end process; 116 --data path: functional units 117 sub <= ( z_reg(16 downto 8) - unsigned('0' & n) ); 118 --data path: output 119 quotient <= std_logic_vector( z_reg(7 downto 0) ); 120 remainder <= std_logic_vector( z_reg(15 downto 8) ); 121 end Behavioral; 

Симулација ИСЕ за горе наведени код је приказана на слици 4.

Слика 4

Можете проверити да када "реади" излаз иде до логике, имамо $$ м = н \ тимес куотиент + ремаиндер $$.

Закључак

Овај чланак испитао је основни алгоритам за бинарну поделу. Изводили смо блок дијаграм за имплементацију кола бинарне подјеле. Такође смо испитали АСМД графикон и ВХДЛ код овог бинарног разделника.