PL104832B1 - Uklad cyfrowy cyklicznego sumo-mnozenia liczb binarnych - Google Patents

Description

Przedmiotem wynalazku jest uklad cyfrowy cyklicznego sumo-mnozenia liczb binarnych do obliczania wartosci wyrazenia ((...(ai +^ )d +dt )c2 +d2 )...)cn+d„, gdzie symbole a,, b, ,c,, d, ,c2, d2 ,c„ dn, oznaczaja liczby binarne, a n jest liczba cykli dzialania ukladu. W szczególnosci, jesli a, +t>! = dG, ct = c2 = ..=c„--x uklad ten sluzy do obliczania wartosci wielomianu d0xn+d, xn -1 + ...+dn_ix+dn, zatem sluzy równiez do obliczania wartosci dowolnej funkcji rozwinietej w szereg zbiezny. Uklad jest przeznaczony do zastosowania w duzych elektronicznych maszynach i systemach cyfrowych i wchodzacych w ich sklad bardzo szybkich procesorach przystosowanych specjalnie do zlozonych obliczen naukowo-technicznych. Ponadto w takich systemach sterowania obiektami, które wymagaja bardzo szybkich obliczen numerycznych.

Znany jest elektroniczny uklad cyfrowy do bardzo szybkiego mnozenia dwóch liczb binarnych, w którym sa do siebie równolegle dodawane równoczesnie wszystkie, przyporzadkowane kolejnym grupom bitów mnoznika, iloczyny, czesciowe potrzebne do wyznaczenia iloczynu koncowego. W ukladzie mnozenia liczb 48-bitowych, w którym pojedyncze iloczyny czesciowe przyporzadkowane sa parom kolejnych bitów mnoznika, dodawane jest równoczesnie 24 takich iloczynów. Zespól cyfrowy wykonujacy to dodawanie zlozony jest z 22 sumatorów z zachowaniem przeniesien (carry save adders) i sumatora z propagacja przeniesien (carry propagating adder). Sumatory te sa polaczone w wielowarstwowa kaskade zawierajaca w 7 warstwach kolejno 8, 5, 3, 2, 2, 1, 1 sumatorów z zachowaniem przeniesien i ósmej warstwie 1 sumator z propagacja przeniesien. Wszystkie te sumatory tworza zespól cyfrowy stanowiacy jedna laczna kombinacyjna siec przelaczajaca bez elementów pamietajacych. Czas wykonania dodawania 24 iloczynów czesciowych w takim zespole sumatorów jest suma maksymalnego czasu propagacji sygnalów przez 7 polaczonych w szereg sumatorów jednopozycyjnych i propagacji przeniesien przez 1 sumator okolo 90 pozycyjny. Ten ostatni sumator posiada rozbudowane obwody przeskoków przeniesien (carry skips) dla zminimalizowania maksymalnego czasu propagacji przeniesien. Iloczyny czesciowe dodawane w omówionym zespole sumatorów, stanowia wzajemnie przesuniete wielokrotnosci mnoznej, przyporzadkowane parom bitów mnoznika, reprezentujacych liczby calkowite z zakresu od 0 do 3.

Ola unikniecia czasochlonnego wyznaczania 3-krotnej mnoznej wymagajacego dodatkowego dodawania wzajemnie przesunietych mnoznych, omawiany uklad mnozenia zawiera siec przelaczajaca, przeksztalcajaca2 104 832 równolegle mnoznik. Sygnaly wyjsciowe tej sieci przyporzadkowane kolejnym grupom bitów mnoznika, reprezentuja, zamiast liczb 0, 1,2, 3, liczby —2, —1,0, 1,2. Dwukrotna mnozna otrzymuje sie w omawianym ukladzie mnozenia przez przesuniecie mnoznej o jeden bit w lewo, a wielokrotnosci ujemne - przez zanegowanie bitów wielokrotnosci dodatnich i uwzglednienie korekcyjnej jedynki na najmniej znaczacej pozycji binarnej.

Uklad mnozenia zawierajacy omówiony zespól sumatorów opisany zostal w pracach: CS. Wallace „A.

Suggestion for a Fast Multiplier", The Institute of Electrical and Electronics Engineers, Transactions on Electronic Computers, tom EC-13, strony 14-17, luty 1964; T.G. Hallin, MJ. Flynn „Pipelining of arithmetic functions", The Institute of Electrical and Electronics Engineers, Transactions on Electronic Computers, tom EC—21, strony 880-886, sierpien 1972, J.W. Gawrilow, A.N. Puczko „Arifmeticzeskije ustroistwa bystrodiejstwujuszczich elektronnych cifrowych wyczislitielnych maszin", Izdatielstwo: Sowietskoje radio, Moskwa 1970, strony 133-180, a obwody przeskoków przeniesien w pracy: O.L. MacSorley: High Speed Arithmetic in Binary Computers, Proceedings of Institute of Radio Engineers, tom 49, numer 1, 1961, strony 67-91.

Uzupelniajac omówiony uklad mnozenia o dodatkowy jeden sumator z zachowaniem przeniesien, dolaczony w trzeciej lub czwartej warstwie zespolu sumatorów, otrzymuje sie uklad wykonujacy dodatkowo dodawanie liczby binarnej do iloczynu, bez zwiekszania czasu jego dzialania.

Zastosowanie takiego ukladu do wystepujacego czesto w obliczeniach numerycznych wielokrotnego wykonywania na przemian dodawania i mnozenia, wymaga jednak pewnego czasu na propagacje przeniesien po kazdym cyklu obliczen obejmujacym mnozenie i dodawanie. Laczna procentowa strata czasu na propagacje przeniesien jest wówczas jednak dosc znaczna. Stanowi to istotna wade znanych dotychczas rozwiazan bardzo szybkich ukladów realizujacych na przemian dodawanie i mnozen L liczb binarnych. Wady tej mozna wprawdzie uniknac stosujac redundancyjne zapisy liczb. Mozna wówczas wykonywac dzialania dodawania i mnozenia bez propagacji przeniesien. Wykonywanie dzialan na zapisach redundancyjnych ma jednak z kolei te wade, ze wymaga wiecej srodków technicznych na pamietanie i przetwarzanie informacji, a równiez dodatkowego czasu na odpowiednie przekodowanie informacji.

Zgodnie z wynalazkiem, uklad cyklicznego sumo-mnozenia do obliczania wartosci wyrazenia ((...(a1+bi)c1+d1)c2+d2 )cn+dn, gdzie symbole ai bi, Ci dt c2,d2...cn, dn oznaczaja liczby przedstawione w zapisie binarnym, a n jest liczba cykli dzialania ukladu, zawiera dwa rejestry, pamietajace skladniki mnoznika, rejestr pamietajacy mnozna, rejestr pamietajacy liczbe dodawana do iloczynu zespól cyfrowy sluzy do przygotowania iloczynów czesciowych w postaci wzajemnie przesunietych wielokrotnosci mnoznej, stanowiacych skladniki pelnego iloczynu, oraz zespól cyfrowy sluzacy do redukowania liczby k skladników dodawania do 2 skladników o takiej samej sumie, gdzie k^> 2.

Pojecie rejestru obejmuje dowolny zespól cyfrowy, na którego wyjsciach utrzymywane sa, przez wystarczajaco dlugi czas, sygnaly reprezentujace bity pamietanej liczby. Korzystne jest stosowanie rejestrów równoleglych dostarczajacych równoczesnie sygnaly reprezentujace wiele bitów pamietanych liczb. Korzystne jest równiez wyposazenie rejestrów pamietajacych skladniki mnoznika, w srodki umozliwiajace utrzymanie na ich wyjsciach niezaklóconych sygnalów poprzednich, az do momentu zapamietania nowej zawartosci rejestrów (np. „master-slave registers").

Skladowe elementy logiczne zespolu przygotowania iloczynów czesciowych jak równiez skladowe elementy logiczne zespolu redukowania skladników, tworza warstwowa strukture równolegla. Liczba warstw skladowych elementów logicznych w tych zespolach i odpowiadajaca jej maksymalna liczba polaczonych ze soba szeregowo elementów logicznych nie zalezy od ilosci bitów mnoznej i ilosci bitów liczby dodawanej do iloczynu, o ile nie brac pod uwage elementów sluzacych do wzmocnienia lub powielenia sygnalów.

Korzystne jest stosowanie takiej struktury logicznej zespolu przygotowania iloczynów czesciowych, w której liczba warstw elementów logicznych jest bardzo mala i nie zalezy od liczby bitów mnoznika wprowadzanych równolegle do tego zespolu. Korzystne jest równiez stosowanie takiej struktury logicznej zespolu redukowania skladników, w której liczba warstw elementów logicznych jest mozliwie najmniejsza.

Wszystkie cztery wymienione rejestry posiadaja wejscia wyprowadzone na zewnatrz ukladu sumo-mnozenia. Wyjscia rejestrów pamietajacych skladniki mnoznika i mnozna stanowia wejscia ze polu przygotowania iloczynów czesciowych. Zespól ten posiada k-1 wyjsc, odpowiadajacych k—1 iloczynom czesciowym, stanowiacym równoczesnie wejscia zespolu redukowania skladników. Pozostale wejscie tego ostatniego zespolu polaczone jest z wyjsciem rejestru pamietajacego liczbe dodawana do iloczynu. Zespól redukowania skladników posiada dwa wyjscia polaczone z wejsciami obu rejestrów pamietajacych skladniki mnoznika. Rejestry pamietajace skladniki mnoznika, zespól przygotowania iloczynów czesciowych oraz zespól redukowania skladników tworza zatem petle zamknieta. Poza petla pozostaje rejestr pamietajacy mnozna i rejestr pamietajacy liczbe dodawana do iloczynu. Z petli tej wyprowadzone sa na zewnatrz ukladu104 832 3 sumomnozenia oba wyjscia zespolu redukowania skladników, i/lub wyjscia obu rejestrów pamietajacych skladniki mnoznika.

Kazde z wymienionych polaczen i wyprowadzen zewnetrznych dostosowane jest do równoleglego przesylania sygnalów reprezentujacych wiele bitów jednej liczby.

Pod pojeciem objetego niniejszym zgloszeniem ukladu sumo-mnozenia rozumie sie nie oddzielna jednostke konstrukcyjna, ale zestaw wspólpracujacych z soba elementów logicznych, które moga obejmowac jeden lub wiecej modulów konstrukcyjnych, albo stanowic czesc jednego modulu konstrukcyjnego.

Korzystne jest, jesli uklad wedlug wynalazku zawiera dodatnkowo równolegly sumator do dodawania dwóch liczb, którego dwa wejscia polaczone sa z dwoma wyjsciami zespolu redukowania skladników i/lub z wyjsciami obu rejestrów pamietajacych skladniki mnoznika. Wyjscie sumatora jest jednoczesnie wyjsciem zewnetrznym ukladu sumo-mnozenia. Celowe jest stosowanie równoleglego sumatora o jak najkrótszym czasie propagacji przeniesien i jak najwiekszej szybkosci dzialania.

W szczególnosci uklad wedlug wynalazku zawiera jeden lub kilka dodatkowych rejestrów, pamietajacych kolejne nieparzyste wielokrotnosci mnoznej, których polaczone sa z dodatkowymi wejsciami zespolu przygotowania iloczynów czesciowych.

Dla uzyskania maksymalnych szybkosci dzialania ukladu wedlug wynalazku zespól przygotowania iloczynów czesciowych i zespól redukowania skladników laczy sie w jedna kombinacyjna siec przelaczajaca, nie zawierajaca elementów pamietajacych i w której elementy skladowe nie tworza petli zamknietych.

Zgodnie z wynalazkiem dla uzyskania maksymalnych szybkosci dzialania ukladu zawierajacego wyjsciowy sumator do dodawania dwóch liczb, laczy sie zespól przygotowania iloczynów czesciowych, zespól redukowania skladników i sumator w jedna kombinacyjna siec przelaczajaca nie zawierajaca elementów pamietajacych i w której elementy skladowe nie tworza petli zamknietych. Dwa wyjscia tej sieci polaczone sa z wejsciami rejestrów pamietajacych skladniki mnoznika, a trzecie wyjscie jest wyjsciem zewnetrznym ukladu cyklicznego sumo-mnozenia.

Dla zmniejszenia liczby elementów stosuje sie uklad, w którym zespól redukowania skladników zawiera siec przelaczajaca oraz rejestry lub inne elementy pamietajace polaczone w zamknieta petle o cyklu pracy co najmniej dwukrotnie krótszym niz pojedynczy cykl pracy calego ukladu. Liczba k-1 wejsc tego zespolu przeznaczonych do wprowadzania iloczynów czesciowych jest wtedy znacznie mniejsza od liczby iloczynów czesciowych koniecznych do otrzymania pelnego iloczynu.

Uklad cyfrowy cyklicznego sumo-mnozenia liczb binarnych, wedlug niniejszego zgloszenia, dziala w sposób nizej opisany.Pierwszy cykl pracy ukladu sumomnozenia rozpoczyna sie od wprowadzenia skladników mnoznika ai, bx mnoznej Ci i liczby dodawanej do iloczynu di do rejestrów pamietajacych te liczby.W wyniku dzialania zespolu przygotowania iloczynów czesciowych i zespolu redukowania skladników, otrzymuje sie na wyjsciach tego ostatniego liczby a2, b2, których suma a2 + b2 równa jest wartosci wyrazenia (ai+bi)ci+dj.

Otrzymane liczby a2, b2 wprowadzone zostaja do rejestrów pamietajacych skladniki mnoznika, co przy równoczesnym wprowadzeniu nowych liczb c2, d2 do rejestrów, pamietajacych mnozna i liczbe dodawana do iloczynu konczy pierwszy cykl dzialania ukladu sumo-mnozenia i rozpoczyna drugi. Drugi i dalsze cykle dzialania ukladu sumo-mnozenia przebiegaja identycznie jak pierwszy.

Wynik dzialania kolejnych n cykli mozna zapisac nastepujaco: (ai+bi^i+di =a2+b2 (a2+b2)c2+d2 =a3+b3 (an+bn)cn+dn =an+i+bn+i z czego wynika, ze suma skladników a n+1, bn+1 otrzymanych w n-tym cyklu dzialania ukladu sumo-mnozenia na wyjsciach zespolu redukowania skladników i ewentualnie na wyjsciach rejestrów pamietajacych skladniki mnoznika, równa jest wartosci wyrazenia ((...(ai lb^ci +di)c2 +d2)...)cn+dn.

Wprzypadku obliczania wartosci wielomianu d0xn+d1xI1"1+ ...dn -ix+dn dzialanie ukladu sumo-mnozenia rózni sie tym, ze na poczatku pierwszego cyklu dzialania wyprowadza sie liczbe dQ tylko do jednego z rejestrów pamietajacych skladniki mnoznika, a liczbe x do rejestru pamietajacego mnozna, przy czym liczba x pozostaje w tym rejestrze az do konca n-tego cyklu pracy ukladu sumo-mnozenia.

Redukowanie liczby skladników odbywa sie calkowicie równolegle, z wyeliminowaniem procesu propagacji przeniesien wzdluz liczb, to znaczy w czasie praktycznie niezaleznym, od ilosci bitów mnoznej i ilosci bitów liczby dodawanej do iloczynu.

Otrzymanie wyniku obliczenia w postaci jednej liczby binarnej, bez bitów z nadmiarem informacji, wymaga dodania liczb a n t>n po ostatnim n-tym cyklu dzialania ukladu sumo-mnozenia. Moze to byc przeprowadzone albo poza ukladem sumomnozenia, albo w ukladzie samo-mnozenia uzupelnionym w równolegly sumator do4 104 812 dodawania dwóch liczb. - Dolaczenie do ukladu sumo-mnozenia dodatkowych rejestrów pamietajacych kolejne nieparzyste wielokrotnosci mnoznej ma na celu zwiekszenie liczby róznych wielokrotnosci mnoznej, co umozliwia zmniejszenie liczby iloczynów czesciowych stanowiacych skladniki pelnego iloczynu, a w konsekwencji zmniejszenie liczby elementów skladowych zespolu redukowania skladników. Rozwiazanie zespolów przygotowania iloczynów czesciowych i redukowania skladników w postaci jednej lacznej kombinacyjnej sieci przelaczajacej, oraz bezposrednie polaczenie wejsc tej sieci z wyjsciami wymienionych poprzednio czterech rejestrów powoduje, ze bezposrednio po wprowadzeniu do nich, w i-tym cyklu dzialania ukladu, liczb aj, bi,q, di a zatem po pojawieniu sie na wejsciach sieci sygnalów reprezentujacych bity tych liczb, nastepuje propagacja sygnalów przez siec, w wyniku której ustalaja sie na wyjsciach sieci sygnaly reprezentujace bity liczb aj+ \ y bj+1 spelniajacych równanie (ai+bi)ci+di=an. i J)i+1.

Dolaczajac bezposrednio do wyjsc omawianej kombinacyjnej sieci przelaczajacej sumator do dodawania dwóch liczb zrealizowany równiez w postaci kombinacyjnej sieci przelaczajacej, otrzymuje sie w n-tym cyklu na wyjsciu tej ostatniej sieci sygnaly reprezentujace bity liczby an+ i+bn+1 stanowiacej koncowy wynik dzialania calego ukladu. Sygnaly te ustalaja sie po wprowadzeniu liczb an, bn, cn, dn do wspomnianych czterech rejestrów, oraz po propagacji sygnalów przez cala kombinacyjna siec przelaczajaca zlozona z wymienionych wyzej sieci skladowych.

Rozwiazanie ukladu, w którym zespól redukowania skladników zawiera siec przelaczajaca oraz rejestry lub inne elementy pamietajace polaczone w zamknieta petle pozwala na kilkakrotne zmniejszenie ilosci jego elementów skladowych. Zespól redukowania skladników wykonuje wówczas kilka cykli pracy w jednym cyklu dzialania calego ukladu cyklicznego sumo-mnozenia, redukujac w kazdym z tych cykli kilkakrotnie mniejsza liczbe iloczynów czesciowych.

Podstawowa zaleta cyfrowego ukladu cyklicznego sumo-mnozenia jest prawie calkowite unikniecie czasochlonnego procesu propagacji przeniesien i uzyskanie przez to znacznie wiekszej szybkosci obliczen niz w innych ukladach cyfrowych, wykonujacych analogiczne obliczenia równiez na liczbach binarnych w zapisie nieredundancyjnym, to znaczy w zapisie wymagajacym minimalnej liczby bitów. Obliczenie wyrazenia wymagajacego n-krotnego wykonania na przemian dodawania i mnozenia odbywa sie mianowicie w omawianym ukladzie albo w ogóle bez procesu propagacji przeniesien wzdluz przetwarzanych liczb, jesli koncowy wynik obliczenia moze byc przedstawiony w formie dwóch skladników dodawania, albo wymaga jednokrotnego procesu propagacji przeniesien, gdy wymagany jest wynik w postaci jednej liczby w binarnym zapisie nieredundancyjnym.

Wynalazek zostanie blizej wyjasniony w przykladzie wykonania, pokazanym na rysunku przedstawiajacym uklad w schemacie blokowym.

Zgodnie z/ysunkiem uklad zawiera cztery rejestry równolegle A, B, C, D pamietajace dwa skladniki mnoznika, mnozna i liczbe dodawana do iloczynu. Zawiera równiez zespól cyfrowy IM" pr/vjWinvania iloczynów czesciowych zespól cyfrowy R do redukowania liczby skladników ora/ szybki sumator sownolee.ly S do dodawania dwóch liczb binarnych. Kazde z wejsc i wyjsc wymienionych rejestrów i zespolów yhowych umozliwia równolegle wprowadzenie lub wyprowadzenie równoczesnie wszystkich bilów jeilnci he/hy binarnej.

Pokazane na rysunku wejscia WiA, W|B, wC,wD rejestrów A, B, C, D wyprowadzone sa su zewnatrz ukladu sumomnozenia. Wyjscia zA,zB,zC rejestrów A, B, C polaczone sa z wejsciami w, l\ w, l\ w ,1* zespolu P, którego wyjscia ZiP, z^P,..., Zk.|P stanowia wejscia w lR, w2R, ...,Wk-iR zespolu R. Pozostale wejsue w^R tego zespolu jest polaczone z wyjsciem zD rejestru D. Wyjscia zt R, z2R zespolu R stanowia wejscia \\{ S, w>S sumatora S i niezaleznie od tego polaczone sa z wejsciami w2 A, w2B rejestrów A, B. Wyjscie /S sumatora S wyprowadzone jest na zewnatrz ukladu sumo-mnozenia.

Rejestry A, B, pamietajace skladniki mnoznika sa podwójnymi równoleglymi rejestrami (master-slave registers). Rejestr C pamietajacy mnozna i rejestr D pamietajacy liczbe dodawana do iloczynu sa pojedynczymi równoleglymi rejestrami. Zespoly cyfrowe P, R i sumator S zrealizowane sa w postaci kombinacyjnych sieci przelaczajacych i nie zawieraja elementów pamietajacych.

Zespól cyfrowy P sluzy do przygotowania iloczynów czesciowych, z których kazdy przyporzadkowany jest jednej parze odpowiadajacych sobie grup dwubitowych z obu skladników mnoznika. Iloczyny te stanowia wzajemnie przesuniete wielokrotnosci mnoznej o krotnosciach calkowitych -2, -1,0, 1,2. Zespól P sklada sie z dwóch czesci. Wieksza z nich zlozona jest z wielu jednakowych dwuwarstwowych sieci przelaczajacych uporzadkowanych w wiersze i kolumny. Na wejscia kazdego wiersza takiej dwuwymiarowej macierzy sieci przelaczajacych wprowadzane sa z rejestru C sygnaly reprezentujace bity mnoznej i bity negacji mnoznej, a na wejscia kazdej kolumny wprowadzane sa z drugiej czesci zespolu P sygnaly reprezentujace calkowite krotnosci mnoznej z zakresu od —2 do +2. Ta druga czesc zespolu P zawiera inne, równiez jednakowe sieci przelaczajace,104 832 5 z których kazda przyporzadkowana jest dwom pozycjom binarnym obu rejestrów A i B.

W wyniku wprowadzenia na wejsciach kazdej z tych sieci sygnalów reprezentujacych bity z trzech kolejnych odpowiadajacych sobie par dwubitowych obu skladników mnoznika z rejestrów A i B, otrzymuje sie na jej wyjsciu sygnaly reprezentujace jedna z liczb calkowitych od —2 do +2. Na wyjsciach sieci przelaczajacych z pierwszej omawianej czesci zespolu P, stanowiacych poszczególne wiersze macierzy, otrzymuje sie bity poszczególnych iloczynów czesciowych. Wszystkie wyjscia bitowe jednego iloczynu czesciowego stanowia jedno wyjscie zespolu P.

Analogicznie wszystkie wejscia bitowe tego zespolu polaczone z wyjsciami bitowymi jednego rejestru stanowia jedno wejscie zespolu P. Otrzymywane na wyjsciach zespolu P iloczyny czesciowe wprowadzane sa na wejscia zespolu R. Na pozostale jedno wejscie tego zespolu wprowadzana jest równolegle z rejestru D liczba dodawana do iloczynu.

Zespól R,sluzy do redukowania liczby skladników i zlozony jest z wielu warstw jednopozycyjnych sumatorów binarnych, nie polaczonych, ze soba wewnatrz poszczególnych warstw. Sumatory te sa kombinacyjnymi sieciami przelaczajacymi posiadajacymi po 3 jednobitowe wejscia i po 2 jednobitowe wyjscia.

Sa one uporzadkowane w kazdej warstwie w wiersze i kolumny dwuwymiarowej macierzy sumatorów. Jeden wiersz pierszej warstwy sumatorów redukuje trzy iloczyny czesciowe do dwóch skladników o takiej samej sumie.

W kazdej nastepnej warstwie pojedynczy wiersz sumatorów redukuje równiez trzy skladniki wejsciowe do dwóch skladników o takiej samej sumie. W ten sposób, w 8-warstwowej kaskadzie jednopozycyjnych sumatorów, redukuje sie, bez propagacji przeniesien wzdluz wierszy sumatorów w poszczególnych warstwach, 32 iloczyny czesciowe i 1 liczbe dodawana do iloczynu do 2 skladników o takiej samej sumie. Liczby wierszy sumatorów w kolejnych warstwach zespolu R przedstawiaja w tym przypadku wyrazy ciagu 11,7,5,3, 2, 1,1, 1, a liczby odpowiadajacych im skladników wejsciowych w tych warstwach wyrazy ciagu 33,22,15,10,7,5,4,3.

Otrzymane na wyjsciach ZiR, z2R zespolu Rdwa skladniki wprowadzane sa nastepnie na wejscia WiS, w2 S sumatora S, oraz na wejscia w2 A, w2 B rejestrów A, B, gdzie stanowia one skladniki mnoznika w nastepnym cyklu dzialania ukladu sumomnozenia. Skladniki wprowadzone w ostatnim cyklu dzialania ukladu sumomnozenia, na wejscia wj S, w2S sumatora S, sa w nim dodawane, dajac na jego wyjsciu zS koncowy wynik obliczenia.

Claims (6)

Zastrzezenia patentowe

1. Uklad cyfrowy cyklicznego sumo-mnozenia liczb binarnych do obliczenia wartosci wyrazenia ((...(ai +bi)ci +dx)c2 +d2)...)cn+dn, gdzie symbole ai, bi, ct, di, c2, d2 ,...,cn, dn oznaczaja liczby przedstawione w zapisie binarnym, a n jest liczba cykli dzialania ukladu, znamienny tym, ze zawiera dwa rejestry (A, B) pamietajace skladniki mnoznika, rejestr (C) pamietajacy mnozna, rejestr (D) pamietajacy liczbe dodawana do iloczynu, zespól cyfrowy (?) do przygotowania iloczynów czesciowych w postaci wzajemnie przesunietych wielokrotnosci mnoznej, stanowiacych skladniki pelnego iloczynu, oraz zespól cyfrowy (R) do redukowania liczby k skladników dodawania do 2 skladników o takiej samej sumie, gdzie k>2, przy czym zarówno skladowe elementy logiczne zespolu (P) przygotowania iloczynów czesciowych jak i zespolu (R) redukowania skladników tworza warstwowa strukture równolegla, taka, ze liczba warstw skladowych elementów logicznych kazdego z tych zespolów (P, R) i odpowiadajaca jej maksymalna liczba polaczonych z soba szeregowo elementów logicznych, nie zalezy bezposrednio od ilosci bitów mnoznej i ilosci bitów liczby dodawanej do iloczynu, a wszystkie wymienione rejestry (A, B, C, D) posiadaja wejscia (wiA, WiB, wC, wD) z zewnatrz ukladu sumomnozenia, podczas gdy wyjscia (zA, zB) rejestrów (A, B) pamietajacych skladniki mnoznika i wyjscie (zC) rejestru (C) pamietajacego mnozna stanowia wejscia (wiP, w2P, w3P) zespolu (P) przygotowania iloczynów czesciowych, a wyjscie (zD) rejestru (D) pamietajacego liczbe dodawana do iloczynu polaczone jest z wejsciem (wfcP) zespolu (R) redukowania skladników, którego pozostale k-1 wejsc (wiR, w2R,...., Wk-iR) stanowia wyjscia (ZiP, z2P,...., Zk_iP) zespolu (P) przygotowania iloczynów czesciowych, oraz którego dwa wyjscia cfciR, z2R) polaczone sa z wejsciami (w2A, w2B) obu rejestrów (A, B) pamietajacych skladniki mnoznika, tworzac petle zamknieta obejmujaca rejestry (A, B) pamietajace skladniki mnoznika oraz zespoly (P, R) przygotowania iloczynów czesciowych i redukowania skladników, poza która pozostaja rejestry (C„D) pamietajace mnozna i liczbe dodawana do iloczynu oraz z której wyprowadzone sa na zewnatrz ukladu sumomnozenia oba wyjscia (ziR, z2R) zespolu (R) redukowania skladników i/lub wyjscia (zA, zB) obu rejestrów (A, B) pamietajacych skladniki mnoznika, gdzie kazde z wymienionych polaczen i wyprowadzen zewnetrznych dostosowane jest do równoleglego przesylania sygnalów reprezentujacych wiele bitów jednej liczby.

2. Uklad wedlug zastrz. 1, znamienny tym, ze zawiera dodatkowo sumator (S) do dodawania dwóch liczb, którego dwa wejscia (wiS, w2S) polaczone sa z dwoma wyjsciami (ZiR, z2R) zespolu (R)6 104 832 redukowania skladników, i/lub z wyjsciami (zA, zB) obu rejestrów (A, B) pamietajacych skladniki mnoznika i którego wyjscie (zS) stanowi wyjscie zewnetrzne ukladu sumomnozenia.

3. Uklad wedlug zastrz. 1, znamienny tym, ze zawiera jeden lub kilka dodatkowych rejestrów pamietajacych kolejne nieparzyste wielokrotnosci mnoznej, których wyjscia polaczone sa z dodatkowymi wejsciami zespolu (?) przygotowania iloczynów czesciowych.

4. Uklad wedlug zastrz. 1, znamienny tym, ze zespól (?) przygotowania iloczynów czesciowych i zespól (R) redukowania liczby skladników tworza lacznie jedna kombinacyjna siec przelaczajaca, nie zawierajaca elementów pamietajacych i w której elementy skladowe nie tworza petli zamknietych.

5. Uklad wedlug zastrz.2, znamienny t ym, ze zespól (?) przygotowania iloczynów czesciowych, zespól (R) redukowania skladników i sumator (S) tworza lacznie jedna kombinacyjna siec przelaczajaca, nie zawierajaca elementów pamietajacych i w której elementy skladowe nie tworza petli zamknietych.

6. Uklad wedlug zastrz. 1, znamienny tym, ze zespól (R) redukowania skladników zawiera siec przelaczajaca i rejestry lub inne elementy pamietajace, tworzace razem zamknieta petle o cyklu pracy co najmniej dwukrotnie krótszym niz pojedynczy cykl pracy calego ukladu sumomnozenia, a liczba k-1 wejsc (wi R, w2R,..MWk-iR) tego zespolu, przeznaczonych do wprowadzania iloczynów czesciowych jest mniejsza od liczby iloczynów czesciowych koniecznych do otrzymania pelnego iloczynu. »D zD »t Q #C zC zS *,P\ •4*1 >P zB M *tP zA "H '#>» *,S 1 ^^A Prac. Poligraf. UP PRL naklsd 120+18 Cena 45 zl