Mnozenie w ukladzie kombinacyjnym ?
From: Wojt <rwxrwx_at_nospam_poczta.onet.pl>
Subject: Mnozenie w ukladzie kombinacyjnym ?
Date: Wed, 24 Oct 2001 01:59:37 +0200
Witam
Czy jest możliwe zrobienie cyfrowego kombinacyjnego układu mnożącego ?
Wojt
From: <mstanisz_at_nospam_poczta.onet.pl>
Subject: Re: Mnozenie w ukladzie kombinacyjnym ?
Date: 24 Oct 2001 10:26:56 +0200
Witam
Czy jest możliwe zrobienie cyfrowego kombinacyjnego układu mnożącego ?
Przez 2, 4, 8, itd. - bez problemu :-)
bp, nmsp
Marcin
--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl
From: "Piotr Wyderski" <Piotr.Wyderski_at_nospam_student.ii.uni.wroc.pl>
Subject: Re: Mnozenie w ukladzie kombinacyjnym ?
Date: Wed, 24 Oct 2001 13:07:35 +0200
Przez 2, 4, 8, itd. - bez problemu :-)
bp, nmsp
Wcale nie jest to odpowiedz klasy nmsp, bo to wlasnie jest juz prawie gotowe
rozwiazanie -- dodaj do tego rownolegle sumatory z AND-ami, a bedzie mozna
mnozyc przez dowolna liczbe. :-)
Pozdrawiam
Piotr Wyderski
From: "Piotr Wyderski" <Piotr.Wyderski_at_nospam_student.ii.uni.wroc.pl>
Subject: Re: Mnozenie w ukladzie kombinacyjnym ?
Date: Wed, 24 Oct 2001 13:38:43 +0200
W uzupelnieniu prosty multiplikator oparty o algorytm rosyjskich wiesniakow.
Chcemy pomnozyc n-bitowe liczby x i y. Pomysl polega na tym, ze bierzemy
ich reprezentacje dwojkowe x=[x_{n-1},...,x_0] i y=[y_{n-1},...,y_0] i
patrzymy,
co to jest mnozenie. Na przyklad 13*5 = (1*8+1*4+0*2+1*1)*5 =
1*8*5 + 1*4*5 + 0*2*5 + 1*1*5. Przez potegi 2. mnozy sie bardzo szybko,
po prostu przeindeksowujac numery bitow i uzupelniajac pozostale zerami.
No to tworzymy sobie n iloczynow przez kolejne potegi dwojki:
x*2^0
x*2^1
...
x^2^{n-1}
i odpowiednio sumujemy je z wagami. Jesli i-ty bit y =1, to
do wyniku dodajemy obliczony poprzednio iloczyn 1 x2^i.
Jesli zas bit ten jest rowny 0, to do wyniku dodajemy
0 x2^i, czyli 0. Jak pisalem, najprosciej zalatwic sprawe
bramkami AND. Po zsumowaniu po wszystkich bitach
y-ka wynikiem bedzie x*y. A jak zbudowac wykorzystywane
tu n sumatorow rownoleglych, (najprostszych, bez wymyslnych
dopalaczy w rodzaju ukladu przewidywania przeniesien) to
wiadomo. Po co kombinowac z EPROMami, chyba lepiej
to wypalic w jakims PLD.
Pozdrawiam
Piotr Wyderski
From: jfox_at_nospam_friko6.onet.pl (J.F.)
Subject: Re: Mnozenie w ukladzie kombinacyjnym ?
Date: Thu, 25 Oct 2001 20:52:42 GMT
On Wed, 24 Oct 2001 13:38:43 +0200, Piotr Wyderski wrote:
[...] A jak zbudowac wykorzystywane
tu n sumatorow rownoleglych, (najprostszych, bez wymyslnych
dopalaczy w rodzaju ukladu przewidywania przeniesien) to
wiadomo. Po co kombinowac z EPROMami, chyba lepiej
to wypalic w jakims PLD.
Sumatory sa bardzo wredne jesli chodzi o PLD - wymagaja wielu
produkt term, i czesto przekraczaja mozliwosci danego PLD.
A taki niewymyslny uklad bedzie dzialal dosc wolno - sporo
tam propagacji ..
J.
From: "Piotr Wyderski" <Piotr.Wyderski_at_nospam_student.ii.uni.wroc.pl>
Subject: Re: Mnozenie w ukladzie kombinacyjnym ?
Date: Fri, 26 Oct 2001 12:04:25 +0200
A taki niewymyslny uklad bedzie dzialal dosc wolno - sporo
tam propagacji ..
Oczywiscie, ze przedstawiony uklad bedzie bardzo wolny -- tylko
mi chodzilo o jak najbardziej intuicyjne wyjasnienie zasady dzialania
takiego mnoznika. Mozna go bardzo przyspieszyc, np. zmieniajac
sumowanie otrzymanego N-elementowego zbioru iloczynow
czesciowych przez caly lancuch sumatorow na rekurencyjna sume:
Sum(N) = Sum(N_1) + Sum(N_2), gdzie N_1 i N_2 maja
odpowiednio po floor(N/2) i ceil(N/2) elementow. Zmniejsza to
glebokosc ukladu z O(N) do O(log(N)). Mozna tez zamiast
"naiwnych" sumatorow zastosowac uklad z przyspieszona
propagacja przeniesien, co da kolejne przyspieszenie sumowania
do O(log(N)). Jak widac, algorytm sie wcale nie zmienil, jego koszt
czasowy spadl z O(N^2) do O(log^2(N)), ale za to jest tak zaciemnony,
ze na jego podstawie trudno sie domyslic zasady dzialania. Skoro
z zalozenia miala to byc wersja edukacyjna, to po co kombinowac? :-)
Pozdrawiam
Piotr Wyderski
PS. Tak sie zastanawiam... skoro sprzetowe mnozenie jest
tak proste, tj. uklad do mnozenia 32*32 bity to tylko najwyzej
kilka tysiecy bramek, to dlaczego na IA-32 takie mnozenie
trwa 10 cykli? Chyba nie chodzi tu o czas propagacji ukladu,
bo to samo mnozenie, ale przez jednostke MMX, trwa 2 cykle.
A dlaczego trwalo to tak dlugo w dawniejszych procesorach?
Czy dolozenie powiedzmy 4 tysiecy bramek do procesora
klasy MC68000 to jest duzy problem od strony technologicznej?
From: "Radek" <radecek_at_nospam_kki.net.pl>
Subject: Re: Mnozenie w ukladzie kombinacyjnym ?
Date: Wed, 24 Oct 2001 12:28:38 +0200
Tak jak kolega Marcin powiedział, mnożenie przez 2,4,8,16....jest sprawą
prostą i polega na przesunięciu liczby binarnej o n-pozycji w prawo, gdzie n
jest potęgą liczby 2, czyli żeby pomnożyć liczbę przez osiem wystarczy
przesunąć o 3 pozycje w prawo. Z dzieleniem jest odwrotnie, z tym że jest
gubiony bit najmniej znaczący.
Mnożyć liczby można na zasadzie wielokrotnego sumowania. Można wykorzystać 2
rejestry , licznik.
Mnożną wpisujesz do rejestru nr 1 i 2, a mnożnik do licznika. Sprawdzasz
czy w liczniku jest zero, jeżeli nie ma to sumujesz zawartość rej. 1 i 2, po
zsumowaniu zmniejszasz licznik o 1, sprawdzasz czy jest zero i tak dalej...
Może jest to prymitywna i wolna metoda ale prosta.
Pozdrawiam:
Radek
Wojt napisał(a) w wiadomości: <3BD60469.87DA6E71_at_nospam_poczta.onet.pl>...
Witam
Czy jest możliwe zrobienie cyfrowego kombinacyjnego układu mnoż?cego ?
Wojt
From: "Marcin Stanisz" <mstanisz_at_nospam_SPAM.poczta.onet.pl>
Subject: Re: Mnozenie w ukladzie kombinacyjnym ?
Date: Wed, 24 Oct 2001 12:51:31 +0200
"Radek" <radecek_at_nospam_kki.net.pl> wrote in message
news:9r653l$s2t$1_at_nospam_news.tpi.pl...
Mnożyć liczby można na zasadzie wielokrotnego sumowania. Można wykorzystać
2
rejestry , licznik.
Mnożną wpisujesz do rejestru nr 1 i 2, a mnożnik do licznika. Sprawdzasz
czy w liczniku jest zero, jeżeli nie ma to sumujesz zawartość rej. 1 i 2,
po
zsumowaniu zmniejszasz licznik o 1, sprawdzasz czy jest zero i tak
dalej...
Może jest to prymitywna i wolna metoda ale prosta.
Radek - jeden problem. To chyba nie będzie układ kombinacyjny :-)
Pozdrawiam
Marcin Stanisz
From: "Piotr Wyderski" <Piotr.Wyderski_at_nospam_student.ii.uni.wroc.pl>
Subject: Re: Mnozenie w ukladzie kombinacyjnym ?
Date: Wed, 24 Oct 2001 13:01:58 +0200
Czy jest możliwe zrobienie cyfrowego kombinacyjnego układu mnożącego ?
Tak, i to nawet na kilka ciekawych sposobow. Najprosciej to chyba zrobic
jako rownolegla wersje "algorytmu rosyjskich wiesniakow". Zobacz: Cormen,
Rivest, Leiserson, "Wprowadzenie do algorytmow i struktur danych". Jest tam
rozdzial wlasnie o ukladach rownoleglych: sumatory, multiplikatory, sieci
permutacyjne i tym podobne.
Pozdrawiam
Piotr Wyderski
From: "Serwis ADO-MED" <serwis_at_nospam_adomed.com.pl>
Subject: Odp: Mnozenie w ukladzie kombinacyjnym ?
Date: Wed, 24 Oct 2001 13:14:01 +0200
Jesli to uznasz za uklad kombinacyjny? to mozna to wykonac na pamieci EPROM
odpowiednio zaprogramowanej. Na połowe wejsc adresowych podajesz czynnik
pierwszy na drugą polowe drugi czynnik, na wyjściu danych pamieci otrzymasz
statyczny wynik - o ile sobie odpowiednie liczby tam wczesniej wpiszesz
(zaprogramujesz). Jesli brak ci bitów wyjsciowych mozna uzyc 2,3 EPROM-y.
Wtedy wejscia chipow bedą podlaczone tak samo (rownolegle), a wyjscia bedą
stanowily po koleji np mlodszą (środkową) i starszą część wyniku. Np 2
chipy typu 27512 mające 16 wejsc adresowych mogą "mnozyc" dwie liczby
8-bitowe, wynik jest 16-o bitowy - jeden chip da mlodszy bajt wyniku drugi
starszy bajt. 3 chipy 272048 mogą mnozyc liczby 10-o bitowe, wynik 20 bitow.
Zaleta takiego samodzielnego robienia tabliczek mnozenia jest takze to, ze
moze to byc tabliczka niekwadratowa (w takim samym układzie mozna mnozyc
zamiast dwoch liczb 8-o bitowych np liczbe 10-o bitową przez 6-o bitową),
mozna utworzyc tablicę do mnożeń liczb ze znakiem lub z jaimiś
zaokrągleniami, poprawkami czy jakiekolwiek inne funkcje przeliczające
kilkanaście bitów wejsciowych na kilkanaście wyjściowych.