następny punkt »


1. Sumatory równoległe

Jedną z najczęściej wykonywanych operacji w systemach cyfrowych jest dodawanie dwóch słów dwójkowych. W wykładzie I poznaliśmy układ sumatora jednobitowego (jednopozycyjnego). Symbol tego sumatora oraz równania opisujące działanie sumatora jednobitowego przypominamy na rysunku VI.1.

Rys. VI.1. Sumator jednobitowy

Teraz pokażemy jak można zbudować sumator wielobitowy, korzystając z układów sumatorów jednobitowych. Można to zrealizować łącząc szeregowo odpowiednią liczbę sumatorów jednobitowych, tak jak na rysunku VI.2. Uzyskuje się w ten sposób tak zwany sumator kaskadowy.

Rys. VI.2. Schemat kaskadowego sumatora n-bitowego

Każda para bitów dodawanych słów jest sumowana przez odpowiedni sumator jednobitowy z uwzględnieniem przeniesienia. Przeniesienie wchodzące na pierwszy sumator na ogół jest równe 0. Wynikiem dodawania jest n-bitowe słowo S oraz przeniesienie cn wychodzące z ostatniego sumatora.

Struktura układu n-bitowego sumatora pokazana na rysunku VI.2 jest typową strukturą iteracyjną. Istotą struktur iteracyjnych jest to, że budowane są one z identycznych komórek połączonych ze sobą szeregowo: wyjście jednej komórki jest połączone z wejściem sąsiedniej komórki. Na wejście pierwszej komórki podawana jest z reguły stała wartość. W dalszej części wykładu poznamy jeszcze jeden układ o strukturze iteracyjnej.

Teoretycznie w sumatorze z rysunku VI.2 wszystkie pary bitów są dodawane równocześnie. Jeżeli jednak uwzględnimy czasy propagacji, to okaże się, że czas dodawania dwóch słów jest wielokrotnie dłuższy niż czas propagacji przez pojedynczy sumator. Zauważmy bowiem, że drugi sumator jednobitowy (licząc od prawej strony) ma poprawne dane wejściowe dopiero wtedy, gdy otrzyma przeniesienie z pierwszego stopnia. Podobnie, każdy z pozostałych sumatorów ma poprawne dane wejściowe dopiero wtedy, gdy otrzyma przeniesienie z poprzedniego stopnia.

W najgorszym przypadku, dane na wejściu ostatniego sumatora ustalą się po przepropagowaniu przeniesień przez wszystkie poprzednie sumatory. Wynik dodawania pojawi się po czasie propagacji przez ostatni stopień. Załóżmy dla ustalenia uwagi, że czasy propagacji przez sumator jednobitowy (od wejść do wyjścia sumy i od wejść do wyjścia przeniesienia) są sobie równe i wynoszą tp. Wtedy wyniku sumowania przez sumator z rysunku VI.2, w najgorszym przypadku możemy spodziewać się dopiero po czasie .

Pojawia się pytanie, czy nie można przyśpieszyć działania sumatora z rysunku VI.2. Odpowiedź jest twierdząca. Można to zrobić, jeżeli uda się znaleźć wszystkie przeniesienia generowane w układzie szybciej niż w wyniku propagacji przez poszczególne stopnie sumatora.

Pamiętamy, że funkcja przeniesienia w jednobitowym sumatorze wygląda następująco

Wprowadźmy oznaczenia

Teraz funkcję przeniesienia możemy zapisać w skróconej postaci

Wypiszmy teraz funkcje dla kolejnych przeniesień

itd.

Można zauważyć, że każde przeniesienie można zrealizować za pomocą niezależnego układu sumy iloczynów, przy czym argumentami są tylko bity dodawanych słów oraz przeniesienie początkowe . Oznacza to, że można zbudować układ, który będzie generował poszczególne przeniesienia tylko na podstawie znajomości słów wejściowych. Układ taki określany jest jako układ generacji przeniesień. Wszystkie przeniesienia uzyskuje się po czasie propagacji przez dwa poziomy bramek.

Na rysunku VI.3 pokazano układ sumatora, określanego jako sumator równoległy, w którym wykorzystano układ generacji przeniesień (układ ten pokazano w postaci symbolu graficznego). Jeżeli przyjmiemy dla uproszczenia, że czas generacji przeniesień jest równy tp, to czas uzyskania wyniku w sumatorze wynosi teraz 2tp.

Rys. VI.3. Sumator z układem generacji przeniesień (sumator równoległy)


 następny punkt »