,

VYJÁDŘENÍ ČÍSEL V PEVNÉ DESETINNÉ ČÁRCE Jakou hodnotu vyjadřuje následující zápis čísla

101 1001 0101,1000 0011 To nejsme schopni říci, dokud nebudeme vědět zda: Je to číslo se znaménkem?

NE - V jakém je kódu?

- Binárním - BCD - Grayově - jiném (Johansonův, Aikenův, atd.)

0 1

5 7 8

1 7 1 1 5 , 9 2 4 1

ANO - V jjakém formátu? - ± absolutní hodnota - dvojkový doplněk - s posunutou nulou (+ ½ intervalu) - jednotkový doplněk 10 9 8 7 6 5 4 3 2 1 0 Binární vyjádření = 1.2 + 0.2 + 1.2 + 1.2 + 0.2 + 0.2 + 1.2 + 0.2 + 1.2 + 0.2 + 1.2 + 1.2-1+ 0.2- 2 +0.2- 3+ 0.2- 4 + 0.2-5+ 0.2- 6 + 1.2- 7 + 1.2-8 = BCD komprimované vyjádření (každá cifra od 0 do 9 je od desetinné tečky vyjádřena 4 bity) odtud = 595,83 U čísel se znaménkem budeme předpokládat, že nejvyšší bit značí znaménko 1 01 1001 0101,1000 0011 ± absolutní hodnota = - 405,5117187510

FEL ČVUT

Petr Skalický, katedra radioelektroniky

1

VYJÁDŘENÍ ČÍSEL V PEVNÉ DESETINNÉ ČÁRCE n −1

Dvojkový doplněk

2

A = 2 - A = 2 − ∑ a i .2 n

n

n −1

A = 2 - A = 2 − ∑~ ai .2i

i

n 2

i=− b

n

i=− b

Naše číslo je záporné a tudíž vyjádřené ve dvojkovém doplňku A = 211 - 101 1001 0101 0101,1000 1000 0011 = 010 0110 1010 ,0111 0111 1101 = - 618,48828125 618 4882812510 Sériový algoritmus převodu A ↔2A: Kopírujeme bity převáděného čísla od nejnižší váhy k nejvyšší (zprava doleva) dokud se nedostaneme k první jedničce, kterou též zkopírujeme. Po první jedničce všechny bity invertujeme. Dvojkový doplněk je s jednotkovým svázán vztahem Dvojkový doplněk = Jednotkový doplněk + 2-bb. Plus ½ intervalu

1/2

A=2

n -1

+A=2

n −2

n -1

− ∑ a i .2i i=− b

Čí l je Číslo j kladné kl d é a představuje ř d t j hodnotu h d t

405 5117187510 405,51171875

Jednotkový doplněk n −1

1

n −1

n −1

A = 2 − A − 2 = 2 − ∑ a i .2 − 2 = (2 − 2 ) − ∑ a i .2 = 1111K1111 − ∑ a i .2i n

-b

n

i

-b

n

-b

i=− b

i

i=− b

i=− b

Naše číslo je záporné a tudíž vyjádřené v jednotkovém doplňku A = 111 1111 1111, 1111 1111 - 101 1001 0101,1000 0011 = 010 0110 1010 ,0111 1100 = = - 618,48437510 Převod A ↔1A spočívá v inverzi bitů převáděného čísla. FEL ČVUT


2

INSTRUKCE SČÍTÁNÍ A JEJICH POUŽITÍ Potřebujeme-li sčítat operandy, operandy které mají více bitů než je šířka datové sběrnice, sběrnice musíme operandy rozdělit na části odpovídající šířce datové sběrnice do jednotlivých registrů nebo datové paměti. Nejnižší byty sečteme pomocí instrukce ADD, vyšší pomocí sčítání s přenosem ADDC. Například pro součet dvou čísel 16-bitových čísel můžeme psát

1

1 1

0 1

1 1

0 1

0 0

0 1

0 0

0 1

1 0

0 0

0 1

1 1

0 0

1 1

0 1

1 1

1

0

0

1

0

1

0

1

1

1

0

0

1

1

0

0

V procesoru budou čísla uložena ve dvou registrech např. R6,R7 a R4,R5 R6 = 1 0 1 0 0 0 0 0 R7 = 1 0 0 1 0 1 0 1 R4 = 1 1 1 1 0 1 0 1 R5 = 0 0 1 1 0 1 1 1 Program v asembleru pro součet dvou 16-ti bitových čísel bude vypadat následovně

S č t16 MOV A,R5 Součet16: A R5 ADD A,R7 MOV R7,A MOV A,R4 ADDC A,R6 MOV

R6, A

; ; ; ; ; ; ; ; ;

Nižší byte b t druhého d héh čísla čí l do d střadače tř d č Přičtení nižšího bytu prvého čísla Uložení nižší bytu součtu do registru R7 Vyšší byte druhého čísla do střadače Přičtení vyššího bytu prvého čísla včetně příznaku přenosu C případně nastaveného v součtu nižších bytů Uložení vyšší bytu součtu do registru R7 Je-li součet > 16 bitů příznak přenosu C=1

Pokud k d jsou j čí l v jiném čísla ji é formátu f á nežž binárním bi á í např. ř Gray, G Johansonův h ů atd. d je j potřeba ř b jejich j ji h konverze do binárního tvaru, pokud není znám algoritmus výpočtu jejich součtu. FEL ČVUT


3

SČÍTÁNÍ ČÍSEL V JAZYCE C Program v jazyce C pro součet dvou 16 16-ti ti bitových čísel bude vypadat následovně

unsigned int oper1,oper2; main() { oper1=oper1+oper2; } Překlad programu v jazyce C do asembleru a následně do strojového kódu pro součet dvou 16-ti bitových čísel bude vypadat následovně (překladač uplatňuje princip Big-endian)

0000 0002 0004 0006 0008 000A

E500 2500 F500 E500 3500 F500

R R R R R R

; SOURCE MOV ADD MOV MOV ADDC MOV

LINE # 3 A,oper2+01H , p A,oper1+01H oper1+01H,A A,oper2 A,oper1 oper1 A oper1,A

Bude-li součet > 16 bitů, bude C=1, ale jeho testování musí proběhnout bezprostředně po součtu. Program pro součet více bitových čísel v asembleru je prostým rozšířením uvedeného programu. V jjazyce y C narazíme na p problém v okamžiku, kdy y sčítané operandy p y budou mít více bitů, než jje maximální velikost proměnné v pevné desetinné čárce v daném implementaci jazyka (long – 32bitů nebo double long – 64bitů). Operandy musíme rozdělit do více proměnných a požadovaný součet vyřešit buď vloženým asemblerem do jazyka C nebo součtem dílčích operandů v jazyce C s vyřešením přenosů mezi dílčími součty. Jako příklad uveďme součet dvou 64-bitových čísel.

FEL ČVUT


4

SČÍTÁNÍ ČÍSEL V JAZYCE C unsigned int oper1_H,oper1_L,oper2_H,oper2_L; oper1 H,oper1 L,oper2 H,oper2 L; main() { oper1_H=oper1_H+oper2_H; oper1_L=oper1_L+oper2_L; if (C==1) oper1_H++;} Uvedený příklad je sice možný, ale podmínka na příznak přenosu C není příliš bezpečná. Program bude správně fungovat tehdy, jestliže mezi implementací druhého a třetího řádku nedojde ke zničená stavu příznaku přenosu. Bezpečnější variantou je následující příklad (který by se dal napsat efektivněji)

unsigned int oper1_H,oper1_L,oper2_H,oper2_L,vysled_H,vysled_L; main() { vysled_L=oper1_L+oper2_L; vysled_H=oper1_H+oper2_H; if ((oper1_L & oper2_L & 0x8000)!=0)| (((oper1_L | oper2_L)& 0x8000)!=(vysled_L & 0x8000))) vysled_H|=1; V případě odečítání je situace analogická s operací sčítání. Jediným rozdíl spočívá v tom, že instrukce odečítání je pouze ve variantě s přenosem. Před rozdílem nejnižších bytů je třeba nulovat příznak přenosu. I když instrukce odečítání je dnes na každém procesoru, principielně by v instrukčním souboru být nemusí, protože může být nahrazena součtem s jednotkovým nebo dvojkovým doplňkem.

FEL ČVUT


5

SČÍTÁNÍ ČÍSEL SE ZNAMÉNKEM Máme-li Máme li čísla se znaménkem, znaménkem potom musíme v první řadě zjistit v jakém ze čtyř formátů jsou vyjádřena str.7-8 [1]. V procesorové technice se nejčastěji setkáváme s vyjádřením ± absolutní hodnota, vyjádření s posunem (plus polovina intervalu) a s vyjádřením záporných čísel dvojkovým doplňkem. První dva formáty souvisí spíše s vyjádřením čísel v pohyblivé čárce, poslední se používá pro součet/rozdíl čísel v pevné desetinné tečce. Jak vyplývá ze str.60-62 [1], může součet dvou čísel s rozdílným znaménkem kladný nebo záporný, ale vždy správný. Součet čísel se stejným znaménkem může vést ke správnému výsledku nebo výsledek má opačné znaménko než sčítaná čísla - dochází k přetečení, které je indikováno příznakem OV =1 (overflow). K přetečení tedy dochází tehdy, když součtem dvou kladných čísel získáváme číslo záporné nebo součtem záporných čísel kladný výsledek. výsledek Znaménkový bit u sčítaných nebo odčítaných čísel je uložen v nejvyšším bytu sčítaných čísel. Je-li šířka ALU a do ní vstupujících operandů stejná, potom součet provádíme stejně jako u čísel bez znaménka s tím, že na konci součtu budeme kontrolovat zda nedošlo k přetečení tj. není nastaven příznak OV=1. 1 1

0 1

0 1

0 1

0 0

0 1

0 0

0 1

1 0

0 0

0 1

1 1

0 0

1 1

0 1

1 1

1 0 1 1 1 0 1 0 1 1 1 0 0 1 1 0 0 V případě procesorů 8051 budou čísla například uložena ve dvou registrech např. R6,R7 a R4,R5 R6 = 1 0 0 0 0 0 0 0 R7 = 1 0 0 1 0 1 0 R4 = 1 1 1 1 0 1 0 1 R5 = 0 0 1 1 0 1 1

1 1

Budou-li sčítaná čísla ve formátu plus ½ intervalu, je potřeba od součtu odečíst ½ intervalu. potřeba zjistit j velikost a znaménko operandů p a Budou-li čísla ve formátu ± absolutní hodnota,, jje p následně rozhodnout o jejich rozdílu nebo součtu. Výhodnější bude převod na dvojkový doplněk. [1] Podlešák.J., Skalický.P.: Spínací a číslicová technika, ČVUT Praha 1994, str.235. FEL ČVUT


6

SČÍTÁNÍ ČÍSEL SE ZNAMÉNKEM Budou-li operandy v jednotkovém doplňku můžeme realizovat převod na doplněk dvojkový nebo realizovat kruhový přenos potřebný pro správný součet čísel v jednotkovém doplňku viz. [1]. Program pro součet dvou 16-ti bitových čísel se znaménkem ve vyjádření dvojkovým doplňkem bude vypadat následovně

Součet16z: MOV A,R5 ADD A,R7 MOV R7,A MOV A,R4 ADDC A,R6 ,

; ; ; ; ; ; ; MOV R6, A ; ;Příznak OV=1

Nižší byte druhého čísla do střadače Přičtení nižšího bytu prvého čísla Uložení nižší bytu součtu do registru R7 Vyšší byte druhého čísla do střadače Přičtení vyššího y bytu y prvého čísla včetně p příznaku přenosu C případně nastaveného v součtu nižších bytů Uložení vyššího bytu součtu do registru R7 indikuje, že při součtu došlo k přetečení

V jazyce C budeme muset přetečení testovat okamžitě po operaci součtu nebo rozdílu dříve, než kompilátor zrealizuje operaci, která tento příznak ovlivní. Dojde-li k přetečení, potom výsledek představuje dvojkový doplněk správného výsledku viz. následující blána.

FEL ČVUT


7

SČÍTÁNÍ SOUČTU SOUČINŮ SČÍTÁNÍ SOUČTU SOUČINŮ –– NAPŘ. PROBLÉM FILTRACE Tato skutečnost nejvíce vadí při realizaci číslicového zpracování signálu (součty součinů), součinů) kdy nemůžeme po každém součtu realizovat kontrolu přetečení (dvojnásobná doba výpočtu). Na obrázku je zobrazen dopad přetečení do zpracovávaného signálu. U signálových procesorů je z tohoto důvodu implementovaná tzv. saturační aritmetika. Dojde-li při operaci k překročení maximální kladné nebo záporné hodnoty je výsledek omezen na maximální hodnotu viz. obrázek. U některých procesorů je aritmetická jednotka o 8 bitů širší, než součin datového vzorku s koeficientem. Součet součinů se tak může dynamicky pohybovat na větším počtu bitů a teprve na konci výpočtu je zjištěno, zda výsledek překračuje maximální hodnotu určenou součtem bitů obou operandů. Při překročení rozsahu pro součet součinů je výsledná hodnota saturována Má-li procesor aritmeticko-logickou jednotku (ALU) s větším počtem bitů než do saturována. ní vstupující operandy, potom musí být informována o to, zda operandy jsou čísla bez znaménka nebo se znaménkem. Vstupuje-li do střadače nebo ALU operand se znaménkem, musí být znaménkový bit zkopírován i na bity před znaménkem až do plné šířky střadače nebo ALU. Číslo se zvětšeným počtem bitů musí představovat stejnou hodnotu, kterou chceme do střadače uložit. l ži xp

xmax

0

t

2-b

x 2-b

x min

FEL ČVUT


8

SČÍTÁNÍ DEKADICKÝCH ČÍSEL V PACKED BCD KÓDU Máme Máme-li li operandy v komprimovaném BCD (packed BCD) kódu a potřebujeme realizovat jednodušší operace (sčítání, odečítání, snadno vytvořitelný součin), je lepší operaci realizovat v BCD kódu. Realizace převodu z dekadické do binární soustavy, provedení výpočtu a návrat z binární do dekadické soustavy je zbytečně složitý a tudíž zdlouhavý a neefektivní. Aritmeticko logické jednotky ALU pracují skoro vždy v dvojkové soustavě a tudíž součet BCD čísel nemusí být správný á ý viz. i Příklady. Příkl d 0 0

1 0

1 0

0 1

0 0

1 0

0 1

1 1

= 65 = 13

0

1

1

1

1

0

0

0

= 78

7

Korekce mezi 10 a 16 soustavou

8

0 0

1 0

1 0

0 1

0 0

1 1

0 1

1 1

= 65 = 17

0

1

1

1

1

1

0

0

= 7d

0

0

0

0

0

1

1

0

1

0

0

0

0

0

1

0

= 82

8

Korekce mezi 10 a 16 soustavou

FEL ČVUT

2 AC=1

0 0

1 0

1 0

0 1

1 1

0 0

0 0

1 0

= 69 = 18

1

0

0

0

0

0

0

1

= 81

0

0

0

0

0

1

1

0

1

0

0

0

0

1

1

1

8

výsledek není BCD

7

= 87

Korekci mezi součtu BCD čísel (a u některých procesorů i rozdílu) realizuje tzv. dekadická korekce, která musí být uplatněna bezprostředně po součtu nebo rozdílu dvou BCD čísel. Korekce je uplatněna na spodní 4 bity jestliže představují číslo >9 nebo příznak částečného přenosu AC AC=11 (je přičtena hodnota 6) a na horní 4 bity jestliže představují číslo >9 nebo pří-znak přenosu C=1 (je přičtena hodnota 60h). Program bude vypadat takto SoučetBCD:

výsledek je BCD ale špatný

MOV A,#69h MOV R7,#18h ADD A,R7 DA A Výsledek bude ve střadači a bude roven A=87h


9

SČÍTÁNÍ A ODEČÍTÁNÍ DEKADICKÝCH ČÍSEL V PACKED BCD KÓDU U procesorů, které nemají dekadickou korekci např. AVR, se při součtu dvou BCD čísel musí postupovat podle funkce dekadické korekce popsané na předcházející bláně. Korekce je realizována programem testujícím zda spodní nebo horní 4 bity jsou >9 nebo je nastaven příznak C a AC. Podle výsledku testování je k součtu přičtena hodnota 00h, 06h, 60h nebo 66h. R li Realizace rozdílu díl BCD čísel čí l u procesorů, ů u kterých kt ý h dekadická d k di ká korekce k k f g j jenom funguje j po součtu, se problém dá obejít přes součet. Zaveďme dekadický doplněk (analogie dvojkového doplňku) výrazem D n

B = 10 − B

D

A= 0045 B= 9984

A= 9955 A= 0016

D

99C9 + 0060

996B + 0006

10029

09971

Výsledek kladný

Výsledek záporný

Dekadický doplněk čísla získáme n

10 -11 = 9 9 9 9 -A = - 0 0 4 5 9954 + 0001

V případě, případě že A>B potom můžeme pro rozdíl psát

A − B = A+ DB − 10n Hodnotu rozdílu A-B získáme součtem A+DB od kterého odečteme hodnotu 10n, která představuje 1 vlevo od nejvyššího bitu a v dalším zpracování ji neuvažujeme. V případě, že A
A − B = 10 n + A − B = 10 n − R = DR Je-li rozdíl záporný, pak získáváme přímo jeho dekadický doplněk. Jako příklad jsou ukázány oba případy při rozdílu dvou BCD čísel A=45 a B=16.

D

A= 9955

FEL ČVUT


10

PŘEVOD BINÁRNĚ DEKADICKÝ S DEKADICKOU KOREKCÍ Vypočtenou hodnotu potřebujeme převést do dekadické soustavy a zobrazit na displeji. V jazyce C můžeme použít funkci printf, ale strojový kód se nám zvětší o více jak 1kB, což při aplikacích do malých procesorů může být problém. Ukažme si převod čísla s pevnou desetinnou čárkou do dekadické soustavy, který zahájíme rozdělením na celou a desetinnou část. Celou část můžeme převést pomocí metody postupného dělení základem nebo metodou postupného odečítání mocnin základu. Oba algoritmy nepatří mezi nejefektivnější a proto si ukážeme jiný založený l ž ý na dekadické d k di ké korekci, k k i jehož j h ž doba d b převodu ř d je j nezávislá á i lá na velikosti lik i převáděného ř ádě éh čísla. Číslo ve dvojkové soustavě můžeme vyjádřit tzv. Hornerovým schématem

N = ((a n .2 + a n -1 ).2 + a n -2 ).2 + ........ + a 0 Každá závorka představuje součet dvou stejných čísel (.2) s hodnotou 0 nebo 1 (an-i ∈(0 1)) Bude-li ∈(0,1)). Bude li závorka číslo v BCD formátu (např.0), (např 0) potom na jejich součet s přičtením hodnoty 0 nebo 1 může být aplikována instrukce dekadické korekce. Na obrázku je zobrazen převod binární hodnoty 01101002 na dekadické číslo. 0 0 0 0 0 1 1 0

(...........).2 + a3

0 0 0 0 0 0 0 0

Počáteční stav

0 0 0 0 0 1 1 0

dekadická korekce

0 0 0 0 0 0 0 0

a6

0 0 0 0 1 1 0 1

(...........).2 + a2

0 0 0 1 0 0 1 1

dekadická korekce

0 0 1 0 0 1 1 0

(...........).2 + a1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

dekadická korekce a6.2 + a5

0 0 0 0 0 0 0 1

dekadická korekce

0 0 1 0 0 1 1 0

dekadická korekce

0 0 0 0 0 0 1 1

((a6.2 + a5).2 ) + a4

0 1 0 0 1 1 0 0

((...........).2 ) + a0

0 0 0 0 0 0 1 1

dekadická korekce

0 1 0 1 0 0 1 0

dekadická korekce

5 FEL ČVUT


2

Výsledek

11

PŘEVOD BINÁRNĚ DEKADICKÝ BEZ DEKADICKÉ KOREKCE Existují procesory (AVR, (AVR PIC), PIC) které v instrukčním souboru nemají instrukci dekadické korekce. Pro vytvářený algoritmus je důležité zda procesor je vybaven příznakem částečného přenosu AC nebo H (half carry flag). Jsou-li k dispozici příznaky, můžeme dekadickou korekci implementovat na základě testování příznaku přenosu, částečného přenosu a toho, zda horní a dolní 4 bity jsou > nebo < než číslo 9 viz tři blány zpět. Druhou možností, u které nepotřebujeme ř b j čá č ý přenos, částečný ř j realizace je li předstihu d h dekadické d k d k korekce. k k Před ř d operacíí dvojnásobku mezivýsledku a přičtení dalšího bitu provedeme testování spodních i horních 4 bitů a zjistíme, zda po realizaci dvojnásobku dojde k potřebě korekce či nikoliv. Pokud by po dvojnásobku došlo k potřebě korekce přičteme k příslušné čtveřici bitů hodnotu 3. Podmínkou pro korekci po dvojnásobku je velikost 4 bitů. Budou Budou-li li představovat hodnotu 0 0÷4 4 korekce potřeba nebude. Bude Budeli na čtyřech bitech hodnota 5÷9, potom realizujeme předstih korekce přičtením hodnoty 3. Viz. příklad 10111112 = 9510. 0 0 0 0 1 0 0 0 předkorekce 0 0 0 0 0 0 0 0

Počáteční stav

0 0 0 1 0 0 0 1

0 0 0 0 0 0 0 0

předkorekce

0 0 0 1 0 0 0 1

0 0 0 0 0 0 0 1

a6

0 0 1 0 0 0 1 1

0 0 0 0 0 0 0 1

předkorekce

0 0 1 0 0 0 1 1

0 0 0 0 0 0 1 0

a6.2 + a5

0 1 0 0 0 1 1 1

0 0 0 0 0 0 1 0

předkorekce

0 1 0 0 1 0 1 0

0 0 0 0 0 1 0 1

(a6.2 + a5).2 + a4

1 0 0 1 0 1 0 1 9

FEL ČVUT


5

(...........).2 + a3 předkorekce (...........).2 + a2 předkorekce (...........).2 + a1 předkorekce (...........).2 + a0 Výsledek 12

PŘEVOD BINÁRNĚ DEKADICKÝ DESETINNÉHO ČÍSLA Převod desetinné části převáděného čísla vychází z vyjádření čísla N N<1 1 v základu B takto

N B = b−1B −1 + b−2 B −2 + ... + b−n+1B − n+1 + bn B − n které bude na displeji zobrazeno

,

N = 0, b−1b−2b−3 ...b−n

kde b-n je koeficient s nejmenší váhou. Převod čísla lze provést obdobně jako u čísel přirozených metodou postupného odečítání základu nebo metodou postupného násobení, při kterém postupným násobením čísla N a jeho zbytků základem B získáváme jednotlivé koeficienty čísla N v základu B takto

N .B = b−1 + b−2 B −1 + ... + b−n+1B − n+ 2 + b−n B − n+1 = b−1 + Z1 Z1.B = b−2 + b−3 B −1 + ... + b−n+1B − n+3 + b−n B − n+ 2 = b−2 + Z 2 Koeficienty hledaného čísla N získáváme v pořadí jak jdou za sebou jako celou část součinu N.B pro i = 1 a Zi.B pro i >= 2. V našem případě se jedná o násobení hodnotou B=10. Bude-li procesor vybaven instrukcí násobení, pak bude výhodnější k realizaci algoritmu využít tuto instrukci. Pokud procesor pak násobení hodnotou 10 bude vycházet y ze součtů p posunutých ý nemá instrukci násobení p hodnot 10=(23+21). Desetinné číslo posuneme o jeden bit doleva (dvojnásobek) a uschováme. Následně jej posuneme ještě o dva bity doleva (osminásobek) a sečteme je s uloženým dvojnásobkem. Získaná celá část je hledaná cifra čísla v desítkové soustavě a zbývající desetinou část zase násobíme 10, až získáme požadovaný počet cifer. Stejný algoritmus využijeme při zadávání čísel z klávesnice do mikropočítače. mikropočítače

FEL ČVUT


13

INSTRUKCE NÁSOBENÍ A JEJÍ POUŽITÍ IInstrukce t k násobení á b í neníí instrukcí, i t k í která kt á by b musela l být součástí čá tí instrukčního i t kč íh souboru b procesoru. Není-li procesor vybaven násobičkou, potom musíme násobení realizovat jako součet vzájemně posunutých hodnot násobence v závislosti na jednotlivých bitech násobitele (klasický algoritmus násobení v dvojkové soustavě). Chceme-li snížit počet součtů můžeme použít ý Boothův algoritmus, g , p při kterém násobenec jje násoben více bity y Boothův nebo modifikovaný násobitele. I když se tyto algoritmy využívají hlavně pro obvodová řešení násobičky, lze je využít i pro procesorové řešení. Je-li procesor vybaven násobičkou a operandy nepřesahující její možnosti, potom součin O1(MSB) ( ) O1(LSB) ( ) zrealizujeme jedinou instrukcí. instrukcí Mají-li * operandy větší počet bitů, potom násobená O2(MSB) O2(LSB) čísla X a Y, rozdělíme na dvě nebo více částí, které svoji délkou vyhovují možnostem O1(LSB)*O2(LSB) násobičky procesoru. Na obrázku je příklad O1(LSB)*O2(MSB) 00000000 součinu dvou 16-bitových čísel na procesoru s násobičkou 8x8 bitů. V jazyce C jsou O1(MSB)*O2(LSB) 00000000 funkce obvykle realizovány tak, že výsledek O1(MSB)*O2(MSB) 00000000 00000000 operace násobení má stejný počet bitů jako vstupní operandy. Tato konstrukce VYSL4 VYSL3 VYSL2 VYSL1 má svoje úskalí, ale i výhody. Oproti uvedenému obrázku jsou v jazyce C realizovány pouze tři součiny (chybí součin vyšších bytů). Trvá-li instrukce násobení na procesoru dlouho, jsou popsány algoritmy, u kterých za cenu více součtů redukujeme počet součinů ze čtyř na tři. FEL ČVUT


14

NÁSOBENÍ ČÍSEL SE ZNAMÉNKEM b ~ ~ X = (−1).x z + ∑ ~ x − i .2 − i i =1

b ~ ~ Y = ( −1). y z + ∑ ~ y − j .2 − j j =1

b b ⎤ ⎡ ~~ ⎡ −i ⎤ ~ ~ ~ X .Y = ⎢(−1).x z + ∑ x−i .2 ⎥.⎢(−1). y z + ∑ ~ y− j .2 − j ⎥ = i =1 j =1 ⎦⎣ ⎣ ⎦ b b ⎡ ⎤ b ~ ⎡ ⎤ −j ~ ~ ~ ~ = (−1). ) x z .⎢(−1). ) y z + ∑ y− j .2 ⎥ + ∑ x−i .⎢(−1). ) yz + ∑ ~ y− j .2 − j ⎥ . 2 − i j =1 j =1 ⎣ ⎦ i =1 ⎣ ⎦

A 10011 B 01001 111110011 00000000 0000000 110011 1110001011

= - 13 = 9

= -117

A 01101 B 10111 000001101 00001101 0001101 000000 00001011011 - 01101 11110001011

= 13 = -9

= -117

A 10011 B 10111 111110011 11110011 1110011 000000 10110100101 - 10011 10001110101

= - 13 = -9

= 117

Algoritmus je vhodný pro sériovou realizaci násobení. FEL ČVUT


15

MODIFIKOVANÝ BOOTHŮV MODIFIKOVANÝ BOOTHŮV ALGORITMUS ALGORITMUS ‐‐ RADIX4 n−2 ~~ ⎡ ~ ~ 0 n −1 i⎤ ~ ~ ~ A.B = ⎢− an−1.2 + ∑ ai .2 ⎥.B + a−1.B.2 = i =0 ⎣ ⎦ ~ ~ ~ ~ ~ − a~n −1.B.2n−1 + a~n−2 .B.2n−2 + K + a~1.B.21 + a~0 .B.20 + a~−1.B.20 = ~ ~ = (a~n −2 − a~n−1 ).B.2n−1 + (a~n−3 − a~n−2 ).B.2n−2 + K ~ 3 ~ ~ ~ 2 ~ ~ ~ 1 ~ ~ 0 ~ ~ ~ K + (a2 − a3 ).B.2 + (a1 − a2 ).B.2 + (a0 − a1 ).B.2 + (a−1 − a0 ).B.2 = ~ = (a~n − 2 .2 − a~n −1.2 + a~n −3 − a~n − 2 ).B.2 n − 2 + K ~ ~ K + (− a~2 .2 − a~3 .2 + a~1 − a~2 ).B.2 2 + (a~0 .2 − a~1.2 + a~−1 − a~0 ).B.2 0 = ~ = (− a~n −1.2 + a~n − 2 + a~n −3 ).B.2 n − 2 + K ~ ~ K + (− a~3 .2 + a~2 + a~1 ).B.2 2 + (− a~1.2 + a~0 + a~−1 ).B.20 =

Pokud bude koeficient a-1=0, pak výpočet součinu z trojic bitů násobitele bude roven součinu čísel A a B se znaménkem. Kombinace tří bitů pak ovlivňuje násobence podle následující tabulky. Posun trojce bitů je po dvou bitech. Při zpracování bitů nevzniká potřeba kaskádního přenosu jako u nemodifikovaného Boothova algoritmu.

FEL ČVUT


16

MODIFIKOVANÝ BOOTHŮV MODIFIKOVANÝ BOOTHŮV ALGORITMUS ALGORITMUS ‐‐ RADIX4 an-k+1 0 0 0 0 1 1 1 1

an-k 0 0 1 1 0 0 1 1

an-k-1 0 1 0 1 0 1 0 1

(hodnota v závorce).B 0 B B 2.B -2.B -B -B 0

Příklad na sériově realizovaný součin čtyřbitových čísel 1110 (-2) a 1101 (-3) (Výsledek = 0000 0110 (+6)) modifikovaným Boothovým algoritmem-Radix4. Součin vzniká v ALU a pomocném é registru i t i s pomocným ý bitem bit pro počáteční čát č í hodnotu h d t a-1 1

Iterace

A

0 1

1110 1110 1110 1110 1110

2

FEL ČVUT

Modifikovaný Boothův algoritmus – Radix4 Krok Součin Inicializace 0000 1101 0 010 ⇒ výsl=výsl+B 1110 1101 0 2x posun doprava 1111 1011 0 ý ý 0001 1011 0 110 ⇒ výsl=výsl-B 2x posun doprava 0000 0110 1 Petr Skalický, katedra radioelektroniky

17

VYJÁDŘENÍ ČÍSEL V POHYBLIVÉ DESETINNÉ ČÁRCE Chceme-li p pracovat s čísly y v p pohyblivé y desetinné čárce, musíme jje rozšířit o číslo vyjadřující hodnotu exponentu včetně jeho znaménka. Číslo s pohyblivou čárkou pak bývá vyjádřeno ve tvaru (standard IEEE 754-1985)

A = 0,

A = ∞,

A = (− 1) .(1 + m ).2e+127 z

kde z představuje znaménko čísla, čísla e jeho exponent a m mantisu (hodnotu na desetinných místech ), kterou můžeme vyjádřit výrazem

m = a−1 2 −1 + a− 2 2−2 + ... + a−n+1 2− n+1 + a−n 2− n Hodnota závorky (1+m) v první rovnici se může pohybovat v intervalu <1,0;2,0) (tzv. normovaná mantisa, která zajišťuje požadovanou přesnost mantisy a která je vyjádřena ve formátu ±absolutní hodnota). Přesnost čísla na desetinných místech je dána hodnotou 2-n. Hodnotu exponentu vyjádříme celým číslem se znaménkem ve formátu čísla s posunutou nulou (nebo +1/2 intervalu zmenšeném o hodnotu 1)

exponent = e + 127 = am−1am−2 am−3 ...a a0 kde e se pohybuje v intervalu <-126;127> pro dvojnásobnou přesnost <-1022;1023>). Krajní hodnoty exponentu e+127=0 a e+127=255 se využívají k vyjádření čísel, která nelze ve formátu daném první rovnicí vyjádřit (tzn. 0 a ±∝). Standardizovaný formát čísla v jednoduché přesnosti je vyjádřen 32 bity, které jsou rozděleny do 4 bytů takto: MSB = ze7e6e5e4e3e2e1 e0m-1m-2m-3m-4m-5m-6m-7 m-8m-9m-10m-11m-12m-13m-14m-15 LSB = m-16m-17m-18m-19m-20m-21m-22m-23 Číslo v dvojnásobné přesnosti je vyjádřeno 64 bity, z nichž 11bitů je exponent a 52 bitů je mantisa. Jednička z výrazu (1+m) je tzv. skrytá jednička (ve vyjádření se neobjevuje). FEL ČVUT


18

VYJÁDŘENÍ ČÍSEL V POHYBLIVÉ DESETINNÉ ČÁRCE Příklad na vyjádření některých čísel v pohyblivé čárce je uveden v následující tabulce Číslo

Vyjádření z

exponent

mantisa

1,000.10 1 000 100

1,000000.2 1 000000 20

0

0111111

0000000000

8,000.100

1,000000.23

0

1000010

0000000000

0,000.100

0,000000.20

0

0000000

0000000000

-1,750.100

1,750000.20

1

0111111

1100000000

1,250.102

1,953125.26

0

1000101

1111010000

-1,250.102

-1,953125.26

1

1000101

1111010000

-7,812.10-2

-1,249920.2-4

1

0111011

0011111111

Při realizaci atypického vyjádření čísel s pohyblivou čárkou určíme nezbytný počet bitů mantisy n ze vztahů :

2−n ≤ 10− pocet desetinných míst Počet bitů exponentu bude dán vztahy m−1

22 ≥ 10rozsah exp onentu FEL ČVUT

n≥

pocet desetinných míst log 2

⎛ rozsah exponentu ⎞ log⎜⎜ ⎟⎟ log 2 ⎝ ⎠ m ≥1+ log 2


19

OPERACE V POHYBLIVÉ OPERACE V POHYBLIVÉ DESETINNÉ ČÁRCE DESETINNÉ ČÁRCE Násobení čísel A a B v p pohyblivé y čárce můžeme vyjádřit yj takto

A.B = ((−1) z . MA. 2 e ). ((−1) z . MB . 2 e A

A

B

B

)

kde MA MB - jsou normované mantisy představující závorku (1+m). Součin MA.MB představuje součin čísel v pevné desetinné čárce s tím, že výsledek součinu bude mít dvojnásobný počet bitů a jeho velikost bude ležet v intervalu <1;4). <1;4) Pokud součin mantis je ≥2 musí být výsledek posunut o jednu pozici doprava, abychom získali normovanou mantisu, a hodnota exponentu bude zvětšena o hodnotu 1. Na konci normování dojde k omezení nebo zaokrouhlení součinu mantis na standardní počet bitů ⇒ operace není lineární a výsledek je zatížen chybou

A B = (-11) z ⊕ z . MA. MB. 2 e +e = (−1) z .mV .2 e +e = A.B A

B

A

V

B

= normování = (−1) z .MV .2 e V

A

B

V

V případě podílu je situace stejná, jen násobení s pevnou desetinnou čárkou je nahrazeno dělením a součet exponentů je nahrazen rozdílem. Při sčítání a odečítání je situace následující

A ± B = (−1) z . MA. 2 e ± (−1) z . MB . 2 e = (−1) z . MA. 2 e ± (−1) z . mB . 2 e = A

[

A

B

]

B

A

A

B

A

= (−1) z . MA ± (−1) z . mB .2 e = (−1) z . mV . 2 e = normování = (−1) z . MV . 2 e A

B

A

V

A

V

V

Mantisa čísla s menším exponentem je posouvána doprava tak dlouho, dokud nedojde ke srovnání exponentů obou čísel. Následně jsou mantisy obou čísel sečteny (součet čísel v pevné desetinné čárce) a podle výsledku musí být mantisa upravena tak, aby ležela v intervalu <1;2). V případě součtu se bude jednat o případný jeden posun doprava a inkrementaci exponentu, v případě rozdílu i o několik posunů doleva a zmenšení exponentu. Nakonec rozšířenou mantisu opět omezíme nebo zaokrouhlíme na standardní počet bitů ⇒ operace není lineární a výsledek je zatížen chybou. Součet nebo rozdíl řádově velkého a malého čísla se nemusí neprojevit ve výsledku. FEL ČVUT


20

,

Recommend Documents