OBSAH WEBU
ČTĚTE!
Rozdíly
Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.
|
temata:09-reprezentace_cisel:main [2011/04/27 16:00] jasho [Násobenie] |
temata:09-reprezentace_cisel:main [2011/06/02 09:46] (aktuální) george [Zobrazenie čísel v pohyblivej rádovej čiarke] |
||
|---|---|---|---|
| Řádek 1: | Řádek 1: | ||
| + | ~~ODT~~ | ||
| + | |||
| ====== 09 - Reprezentácia čísiel a základné dvojkové aritmetické operácie v počítači ====== | ====== 09 - Reprezentácia čísiel a základné dvojkové aritmetické operácie v počítači ====== | ||
| Řádek 134: | Řádek 136: | ||
| ---- | ---- | ||
| - | 17<sub>10</sub> = 10001<sub>2</sub> = 10001 * 2<sup>5</sup> | + | 17<sub>10</sub> = 10001<sub>2</sub> = 0,10001 * 2<sup>5</sup> |
| {{:temata:09-reprezentace_cisel:fp_17.jpeg?400|FP - 17}} | {{:temata:09-reprezentace_cisel:fp_17.jpeg?400|FP - 17}} | ||
| Řádek 180: | Řádek 182: | ||
| * robí sa s kladnými operandmi, keď je jeden záporný tak sa výsledok nakoniec prevedie | * robí sa s kladnými operandmi, keď je jeden záporný tak sa výsledok nakoniec prevedie | ||
| {{:temata:09-reprezentace_cisel:04_cele_cisla_aritmetika_delenie_01.png|}} | {{:temata:09-reprezentace_cisel:04_cele_cisla_aritmetika_delenie_01.png|}} | ||
| + | |||
| {{:temata:09-reprezentace_cisel:04_cele_cisla_aritmetika_delenie_02.png|}} | {{:temata:09-reprezentace_cisel:04_cele_cisla_aritmetika_delenie_02.png|}} | ||
| + | |||
| + | * zavedieme skratky: | ||
| + | * D - delenec | ||
| + | * d - deliteľ | ||
| + | * Q - podiel | ||
| + | * <m>q_i</m> - i-ty bit podielu | ||
| + | * <m>R_i</m> - i-ty zbytok | ||
| + | |||
| + | * v praxi sa posúva dielčí zbytok vľavo a deliteľ je v pevnej polohe | ||
| + | * keď je deliteľ väčší ako <m>2R_i</m> | ||
| + | * potom <m>q_(n-i) = 0</m> | ||
| + | * inak <m>q_(n-i) = 1</m> | ||
| + | |||
| + | {{:temata:09-reprezentace_cisel:delenie_posun_zbytku.png|}} | ||
| + | |||
| + | === Reštaurácia nezáporného zbytku === | ||
| + | |||
| + | * v praxi sa porovnávanie založené na komparátoroch nepoužíva | ||
| + | * odčítanie sa prevedie skúšobne, teda keď <m>2R_i - d</m> je menšie ako: | ||
| + | * potom <m>q_(n-i) = 0</m> | ||
| + | * inak <m>q_(n-i) = 1</m> | ||
| + | * ak je <m>q_(n-i) = 0</m> výsledok skúšobného odčítania nie je správny, treba pričítať d - reštaurácia nezáporného zvyšku | ||
| + | * postup bez reštaurácie: | ||
| + | * v každom kroku prevádzame len jednu operáciu: | ||
| + | * keď je <m>q_(n-i) = 1</m>, použijeme: <m>R_(i+1) = 2R_i - d</m> | ||
| + | * keď je <m>q_(n-1) = 0</m>, použijeme: <m>R_(i+1) = 2R_i + d</m> | ||
| + | * v každom kroku teda len pričítame alebo odćítame, nemusíme robiť zbytočne 2 operácie | ||
| + | |||
| + | {{:temata:09-reprezentace_cisel:delenie_bez_restauracie.png|}} | ||
| + | |||
| + | === Delenie SRT === | ||
| + | |||
| + | * algoritmus pre delenie znamienkových čísel | ||
| + | * vykonávané operácie sa pre každý krok určujú podľa najvyšších bitov priebežného zbytku | ||
| + | * pre demonštráciu - odhad podľa 3 bitov, ale pre niektoré hodnoty D a d postup zlyháva | ||
| + | |||
| + | {{:temata:09-reprezentace_cisel:delenie_srt_priklad.png|}} | ||
| + | |||
| + | * v praxi sa odhaduje podľa viacerých bitov - napr. Pentium - podľa 7 bitov priebežného zbytku a 5 bitov deliteľa | ||
| + | * obvodová realizácia - sekvenčná delička, odhad podľa 3 bitov priebežného zbytku: | ||
| + | * ak má delenec aj deliteľ k ľavostranných núl, posunú sa obsahy registrov PA aj B o k bitov vľavo | ||
| + | * ak je <m>p_n = p_(n-1) = p_(n - 2)</m>, potom <m>q_(n-i) = 0</m> - posun registra PA o 1 bit vľavo | ||
| + | * ak je <m>p_n = 0</m>, potom <m>q_(n-i) = 1</m>, odčítanie PA - B, posun registra PA o 1 bit vľavo | ||
| + | * ak je <m>p_n = 1</m>, potom <m>q_(n-i) = -1</m>, pričítanie PA + B, posun registra PA o 1 bit vľavo | ||
| + | * ak je koncový zbytok menší ako nula, pričítame P + B a odčítame Q - 1 | ||
| ==== Násobenie ==== | ==== Násobenie ==== | ||
| Řádek 192: | Řádek 240: | ||
| * v plávajúcej rádovej čiarke | * v plávajúcej rádovej čiarke | ||
| - | === Princíp násobenia === | + | === Princíp násobenia (bez znamienka) === |
| * majme 2 čísla: N-bitový násobiteľ <m>x_(N-1)x_(N-2)...x_0</m> a M-bitový násobenec <m>y_(M-1)y_(M-2)...y_y_0</m> | * majme 2 čísla: N-bitový násobiteľ <m>x_(N-1)x_(N-2)...x_0</m> a M-bitový násobenec <m>y_(M-1)y_(M-2)...y_y_0</m> | ||
| * súčin bude: | * súčin bude: | ||
| * <m>P = (\sum{j=0}{M-1}{y_j 2^i})(\sum{i=0}{N-1}{x_i 2^i}) = \sum{i=0}{N-1}{\sum{j=0}{M-1}{x_i y_j 2^(i+j)}}</m> | * <m>P = (\sum{j=0}{M-1}{y_j 2^i})(\sum{i=0}{N-1}{x_i 2^i}) = \sum{i=0}{N-1}{\sum{j=0}{M-1}{x_i y_j 2^(i+j)}}</m> | ||
| - | {{:temata:09-reprezentace_cisel:nasobenie_princip.png|}} | + | {{:temata:09-reprez__Podtržení__entace_cisel:nasobenie_princip.png|}} |
| === Sekvenčná násobička === | === Sekvenčná násobička === | ||
| Řádek 209: | Řádek 257: | ||
| * nevýhoda - nízka rýchlosť, n taktov na násobenie | * nevýhoda - nízka rýchlosť, n taktov na násobenie | ||
| {{:temata:09-reprezentace_cisel:sekvencna_nasobicka.png|}} | {{:temata:09-reprezentace_cisel:sekvencna_nasobicka.png|}} | ||
| + | |||
| + | === Kombinačná násobička === | ||
| + | |||
| + | * jednotlivé dielčie súčiny sa tvoria radom hradiel a sčítajú sa na 4-bitových sčítačkách s postupným prenosom | ||
| + | * celkový opčet hradiel pre násobičku n*n bitov je O(n^2) | ||
| + | * celkový počet jednobitových sčítačiek je (n-1)*n | ||
| + | * oneskorenie sčítačky je dané najdlhšou cestou v kombinačnej sieti - ak je prenosové oneskorenie hradla T a sčítačky 2T, má najdhlšia cesta oneskorenie 16T - s rastúcou dĺžkou operandov sa zväčšuje | ||
| + | {{:temata:09-reprezentace_cisel:kombinacna_nasobicka.png|}} | ||
| + | |||
| + | === Násobenie čísel so znamienkom v doplnkovom kóde === | ||
| + | |||
| + | * výsledok je na M + N bitoch | ||
| + | * dôslední práca so znamienkom: | ||
| + | * výsledok násobenia dvoch čísel na n bitoch bude na 2n bitoch - aj vstupné operandy musia byť zakódované na 2n bitoch | ||
| + | * princíp šírenia hodnoty znamienkového bitu doľava - 2 problémy: | ||
| + | - u dielčích súčinov sa objavia ľavostranné jednotky | ||
| + | - objavia sa ďalšie dielčie súčiny | ||
| + | * počet čiastočných súčinov s šírenie znamienkového bitu sa dá redukovať pomocou Boothovho algoritmu | ||
| + | * počet úrovní nutných na sčítanie čiastočných súčinov sa dá redukovať pomocou Wallaceovho stromu | ||
| + | |||
| + | === Princíp Boothovho prekódovania === | ||
| + | * Překódováním násobitele potenciálně velmi usnadníme násobení, protože zredukujeme počet částečných součinů a zbavíme se levostranných jedniček. | ||
| + | |||
| + | == Boothovo prekódovanie s radixom 2 == | ||
| + | * Základem Boothova algoritmu je překódování násobitele do soustavy relativních číslic. Máme-li násobit číslem 31, tedy 00011111, dostaneme stejný výsledek, vynásobíme-li číslem (32 - 1), což zapíšeme v soustavě relativních číslic, která používá číslice 0, +1, -1, jako: | ||
| + | * 0 0 0 1 1 1 1 1 | ||
| + | * 0 0 1 0 0 0 0-1 | ||
| + | * Tento princip aplikujeme na dvojkové číslo opakovaně pro všechny skupiny jedniček, přičemž za skupinu jedniček považujeme i jedinou jedničku. | ||
| + | * 0 1 1 0 0 0 1 0 1 1 0 1 1 1 1 0 1 1 1 1 | ||
| + | * 1 0-1 0 0 1-1 1 0-1 1 0 0 0-1 1 0 0 0-1 | ||
| + | * Odtud můžeme sestavit překódovaci tabulku. Kromě překódovaného bitu se řídíme ještě hodnotou sousedního bitu vpravo. Dostáváme tak základní Boothovo překódování, zvané též překódování s radixem 2. | ||
| + | {{:temata:09-reprezentace_cisel:booth_01.png|}} | ||
| + | * vznikají nulové částečné součiny, které usnadňují výsledný součet | ||
| + | * zůstává však nutnost šíření znaménka u záporných dílčích součinů. | ||
| + | |||
| + | == Boothovo prekódovanie s radixom 4 == | ||
| + | * Dalším požadavkem pro urychlení násobení je snížení počtu dílčích součinů | ||
| + | * překódování "2 bity najednou" | ||
| + | <code> | ||
| + | 1 1 0 1 0 1 1 0 0 1 původní číslo rozdělené do dvojic | ||
| + | 2 1 2 1 2 1 2 1 2 1 váhy | ||
| + | 0-1 1-1 1 0 -1 0 1-1 Boothovo překódování po jednom bitu | ||
| + | -1 1 2 -2 1 překódování "2 bity najednou" | ||
| + | </code> | ||
| + | {{:temata:09-reprezentace_cisel:boothovo_prekodovanie_4.png|}} | ||
| + | |||
| + | == Boothovo prekódovanie - všeobecný počet bitov == | ||
| + | * Obecný postup je takový: V každé skupině zopakujeme nejvyšší bit, a přičteme k nejnižšímu bitu nejvyšší bit ze skupiny vpravo. Výsledné číslo pak považujeme za relativní číslici v doplňkovém kódu. | ||
| + | <code> | ||
| + | Radix 4: | ||
| + | 00 00 11 01 11 10 01 00 10 10 původní číslo | ||
| + | 000 000 111 001 111 110 001 000 110 110 rozšíření znam. bitu | ||
| + | 0 1 0 1 1 0 0 1 1 0 přičtení bitu zprava | ||
| + | -------------------------------------------------------------------------- | ||
| + | 000 001 111 010 000 110 001 001 111 110 doplňkový. kód rel. číslice | ||
| + | 0 +1 -1 2 0 -2 +1 1 -1 -2 překódování s radixem 4 | ||
| + | </code> | ||
| + | {{:temata:09-reprezentace_cisel:boothovo_prekodovanie_8.png|}} | ||
| + | |||
| + | == Násobička s uchovaním prenosov == | ||
| + | |||
| + | * Urychlení sečtení částečných součinů | ||
| + | * Sčítá se bez uvážení přenosů (tj. rychle). | ||
| + | * Avšak přenosy se uchovávají v registru a přičítají (pomocí úplných sčítaček) k průběžnému součtu a dalšímu operandu v následujícím kroku (opět bez přenosu). | ||
| + | * Přičtení posledního operandu se provede pomocí sčítačky s postupným přenosem. | ||
| + | * Ze tří řad sčítacího stromu jsme odstranili sčítačky s postupným přenosem. | ||
| + | * Sčítačky v jedné řadě se označují jako sčítačka s uchováním přenosu (SUP, angl. CSA - Carry-Save Adder). | ||
| + | * V každém stupni se sčítačka v nejvyšším řádu redukovala na hradlo. | ||
| + | * Museli jsme však nakonec jednu řadu sčítaček s postupným přenosem (SPP) přidat. | ||
| + | * Základem n-bitové násobičky s uchováním přenosu je n-bitová SUP: | ||
| + | {{:temata:09-reprezentace_cisel:nasobicka_s_uchovanim_prenosu.png|}} | ||
| + | {{:temata:09-reprezentace_cisel:blokova_schema_nasobicka_6x6.png|}} | ||
| + | {{:temata:09-reprezentace_cisel:blokova_schema_nasobicka_8x8.png|}} | ||
| + | |||
| + | == Príklad na násobenie s uchovaním prenosu == | ||
| + | - Nejdříve jsou sečteny částečné součiny A, B a C, výsledek je v S1 a C1. | ||
| + | - Potom jsou sečteny částečné součiny D, E a F, výsledek je v S2 a C2. | ||
| + | - Následuje součet S1, C1 a S2, výsledek je v S3 a C3. | ||
| + | - Nakonec jsou sečteny S3, C3 a C2, výsledek je v S4 a C4. | ||
| + | - Sčítačkou s postupným přenosem jsou nakonec sečteny S4 a C4. | ||
| + | - Kromě posledního sčítaní jsou všechna ostatní sčítání s uchováním přenosu. | ||
| + | {{:temata:09-reprezentace_cisel:nasobicka_s_uchovanim_prenosu_priklad.png|}} | ||
| + | |||
| + | == Wallaceov strom == | ||
| + | * Zrychlené sčítání částečných součinů | ||
| + | * 6x6 bitov: | ||
| + | {{:temata:09-reprezentace_cisel:wallaceov_strom_6x6.png|}} | ||
| + | * 8x8 bitov: | ||
| + | {{:temata:09-reprezentace_cisel:wallaceov_strom_8x8.png|}} | ||
| ===== Zdroj ===== | ===== Zdroj ===== | ||
| + | <note> | ||
| + | Čerpal som zo slidov k IAS: | ||
| + | https://wis.fit.vutbr.cz/FIT/st/course-files-st.php/course/IAS-IT/lectures/10ias_1.pdf | ||
| + | |||
| + | a zo slidov k INP: | ||
| + | https://wis.fit.vutbr.cz/FIT/st/course-files-st.php/course/INP-IT/lectures/inp2010_08mult.pdf | ||
| + | https://wis.fit.vutbr.cz/FIT/st/course-files-st.php/course/INP-IT/lectures/inp2010_09div.pdf | ||
| + | </note> | ||
| ===== Potvrzení ===== | ===== Potvrzení ===== | ||
