Budowa komputera w Logisim cz. 2: Systemy liczbowe oraz układy dodające i odejmujące

Wstęp

W tym artykulę opiszę system liczbowe:

  • szesnastkowy,
  • dziesiętny,
  • ósemkowy,
  • dwójkowy,

oraz sposoby:

  • dodawania binarnego,
  • zapisu liczby ujemnych w systemie:
    • Znak-Modul (ZM),
    • Uzupełnień do 1 (U1),
    • Uzupełnień do 2 (U2).

Następnie pokażę jak zbudować:

  • półsumator jednobitowy,
  • pełny sumator jednobitowy,
  • 8-bitowy sumator,
  • 8-bitowy układ umożliwiający odejmowanie 8-bitowych liczb.

Systemy liczbowe

 

System dziesiętny

Na co dzień posługujemy się dziesiętnym systemem liczbowym, w którym podstawą jest liczba 10. Przy zapisie liczb mamy więc możliwość korzystania z 10 cyfr: od 0 do 9.
Pozycja cyfry określa przez jaką wagę trzeba ją pomnozyć by obliczyć wartość całej liczby.

Wagi dla przykładowej, 7-cyfrowej, liczby:

Numer cyfry 7 6 5 4 3 2 1 0
Waga 107 106 105 104 103 102 101 100

Przykładowo, liczbę 46 możemy zapisać w taki sposób:
46 = 4 * 101 + 6 * 100

 

System dwójkowy

W systemie dwójkowym jest podobnie jak w dziesietnym. Pozycja cyfry także oznacza jej wielkość w liczbie, jednak cyfr do dyspozycji mamy tylko dwie: 0 i 1.

Wagi dla przykładowej, 7-cyfrowej, liczby:y:

Numer cyfry 7 6 5 4 3 2 1 0
Waga 27 26 25 24 23 22 21 20

Przykładowo, liczbę 46 możemy zapisać w taki sposób:
4610 = 32 + 8 + 6 = 0 * 27 + 0 * 26 + 1 * 25 + 0 * 24 + 1 * 23 + 1 * 22 + 1 * 21 + 0 * 20 = 00101110(2)

 

System ósemkowy

System ósemkowy umożliwia zapis liczby za pomocą 8 cyfr: od 0 do 7.

Wagi dla przykładowej, 7-cyfrowej, liczby:

Numer cyfry 7 6 5 4 3 2 1 0
Waga 87 86 85 84 83 82 81 80

Przykładowo, liczbę 46 możemy zapisać w taki sposób:

4610 = 40 + 6 = 5 * 81 + 6 * 80 = 0568

 

System szesnastkowy

System szesnastkowy umożliwia zapisanie w jednej cyfrze aż 16 wartości: od 0 do F (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F). Wykorzystano kolejne litery alfabetu do uzupełnienia brakujących 6 cyfr.

Dziesiętnie Szesnastkowo Ósemkowo Dwójkowo
0 0x0 00 0000
1 0x1 01 0001
2 0x2 02 0010
3 0x3 03 0011
4 0x4 04 0100
5 0x5 05 0101
6 0x6 06 0110
7 0x7 07 0111
8 0x8 010 1000
9 0x9 011 1001
10 0xA 012 1010
11 0xB 013 1011
12 0xC 014 1100
13 0xD 015 1101
14 0xE 016 1110
15 0xF 017 1111

Tab. 1. Liczby od 0 do 15 w systemie dziesiętnym, szesnastkowym i dwójkowym

 

Często dodaje się literkę “h” na końcu lub “0x” na początku liczby, by określić, że liczba jest zapisana w systemie szesnastkowym.

 

Wagi dla przykładowej, 7-cyfrowej, liczby:

Numer cyfry 7 6 5 4 3 2 1 0
Waga 167 166 165 164 163 162 161 160

Przykładowo, liczbę 46 możemy w systemie szesnastkowym zapisać tak:

4610 = 2 * 161 + 14 * 160 = 2E16 = 2Eh = 0x2E

 

Dodawanie liczb w systemie dziesiętnym i dwójkowym

Dodawanie pisemne każdy z nas miał w szkole, ale dla przypomnienia.

Załóżmy, że chcemy zsumować dwie liczby 15 i 8:

  1
  13
+  8
-----
  21

Przy dodawaniu jednostek 3 i 8 otrzymujemy wartość 11, jednak nie możemy jej całej zapisać w pozycji jednostek (gdyż dosępne wartości są od 0 do 9). Dlatego zapisujemy wartość 1 a ilość dziesiątek, czyli 1, “przenosimy” na pozycję wyżej (ilość dziesiątek).
Potem sumujemy dziesiątki, wynik 2 zapisujemy. Suma dwóch liczb to 21.

Podobnie jest podczas dodawania liczb binarnych, tylko w tym przypadku maksymalną wartością jaką mozemy zapisać na jednej pozycji w wyniku jest 1.

Zróbmy przykład z liczbami takimi jak wyżej. Najpierw zamieńmy liczby na liczby binarne:

1310 = 16 + 4 + 1 = 1 * 2+ 1 * 22 + 0 * 2+ 1 * 20 = 11012

810 = 8 =1 * 23 + 0 * 2+ 0 * 21 + 0 * 210002

I wykonajmy dodawanie

     1     | przeniesienie
      1101 | 13
+     1000 | 8
-----------
     10101 | 21

Podobnie jak w liczbach dziesietnych tak i w przypadku liczb dwójkowych może być wymagane przeniesienie wartości na pozycję wyżej. W tym przypadu wystepuje ono w pierwszej cyfrze od lewej – sumowanie daje wartość 2, którą trzeba przenieść na pozycję wyżej.

Zamieńmy wynik z powrotem na liczbę w systemie dziesiętnym:

101012 = 1 * 24 + 1 * 22 + 1 * 20 = 16 + 4 + 1 = 2110

Wygląda na to, że wyniki są takie same i wszystko się zgadza.

Pierwszy układ logiczny – półsumator 1-bitowy

Trochę definicji

Półsumator 1-bitowy jest układem z dwoma wejściami i dwoma wyjściami, dokonujący sumowania dwóch liczb 1-bitowych.

Wejscia:

  • A – pierwsza liczba 1-bitowa
  • B – druga liczba 1-bitowa

Wyjścia:

  • Y – wynik sumy liczb A i B
  • C -carry, czyli przeniesienie na następną pozycję. Stan wysoki występuje w przypadku, gdy wynik sumy liczb 1-bitowych A i B nie mieści się w jednym bicie.

 

Tak prezentuje się tabela prawdy dla półsumatora:

Wejscie Wyjście
A B Y C
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

Możemy zauważyć, że wartości Y przypominają wartości wyjście z bramki XOR, a wartości wyjścia C przypominają wartości wyjścia bramki AND. Na tej podstawie użyjemy tych bramek podczas budowy układu.

Przechodzimy do budowy półsumatora w Logisim

Po uruchomieniu Logisim pojawi się nam pusty ekran. Po lewej mamy menu z różnymi elementami (od prostych logicznych po bardziej złożone jak np ekran, klawiatura).

Na początku stworzymy sobie nowy układ. W tym celu należy kliknąć zielony plus lub w górnym menu wybrać “Project” -> “Add Circuit”.

Pojawi się okno z polem tekstowym pytające o nazwę układu. Wpisujemy “1-bit Half Adder”.

Z menu Wiring wybieramy Pin (lub użyjmy skrótu Ctrl + 4) i wstawiamy dwa po lewej stronie obszaru. Bedą to piny wejściowe. Nazwijmy je A i B.

Dodajmy też dwa piny wyjsciowe. Nazwijmy je Y i C. (Do obracania pinów można użyć strzałek). Żeby stały się pinami wyjsciowymi należy w parametrach wybranego pinu wybrać “Output?: Yes”.
Możemy też wybrać od razu piny jako wyjściowe uzywając skrótu Ctrl + 5

Żeby zbudować półsumator musimy wybrać dwie bramki logiczne XOR i AND. Tak jak wspomnialem wcześniej wyjście Y jest wynikiem A XOR B, a wyjscie C jest wyjściem A AND B.

Po połączeniu układ prezentuje się następująco:

Rys. 1. Półsumator 1-bitowy

Tak stworzony układ zostaje zamknięty w kostce, której wygląd można edytować po wybraniu ostatniej opcji w tym menu:

Rys. 2. Menu – ostatni przycisk pokazuje wygląd zewnetrzny układu

Rys. 3. Kostka, w której znajduje się półsumator 1-bitowy

Przy edycji wyglądu zewnętrznego naszego układu widzimy dwa wejscia po lewej i dwa wyjścia po prawej. Tak będzie prezentować się nasz układ w przypadku, gdy użyjemy go gdzieś w innym układzie.

Ja dodałem do niego napis i etykiety wejść i wyjść, by nie musieć się zastanawiać, do czego służą poszczególne piny:

 

Rys. 4. Półsumator z etykietami wyjśc

Pierwszy układ logiczny wykorzystujący układ półsumatora – Pełny sumator 1-bitowy

Zbudowaliśmy półsumator, mozemy dodawać dwie 1-bitowe liczby!

Co jednak w przypadku, gdy chcielibyśmy zsumować wieksze liczby, składające się z wiekszej ilości bitów?

Czy wystarczy użyć wiekszej ilości półsumatorów? Nie do końca.

Moglibyśmy użyć 8 półsumatorów by zsumować dwie liczby 8-bitowe, jednak pamiętajmy o tym, że pin wyjściowy Cout informuje nas o tym czy wystapiło przeniesienie i czy do nastepnego bitu nie trzeba dodać dodatkowej jedynki.

Problem w tym, że nie mamy gdzie go podłączyć! Nasz półsumator ma tylko wejscia A i B, nie posiada trzeciego na informację o przeniesieniu.

Dlatego trzeba zbudować układ, który będzie sumował dwie liczby 1-bitowe jednocześnie posiadając wejście na dodatkową informację, czy z dodawania poprzednich bitów nie wynika konieczność przeniesienia jedynki do aktualnego bitu.

Tabela prawdy

Wejscie Wyjście
A B Cin Y Cout
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

Budowa układu pełnego sumatora 1-bitowego

Półsumator otrzymuje dwie liczby 1-bitowe i zwraca na wyjściach sumę oraz informację o przeniesieniu.

Pełny sumator oprócz dwóch liczb będzie otrzymywał także informację o przeniesieniu, czyli uogólniając można powiedzieć, że sumujemy 3 liczby 1-bitowe.

Możemy napisać takie równianie:

Y = A + B + Cin

W zasadzie mamy tutaj dwa dodawania 1-bitowych liczb.

  1. A + B
  2. Wynik z dodawania nr 1.  + Cin

Takie pojedyncze dodawanie bez problemów możemy wykonać półsumatorem, który stworzyliśmy wcześniej.

Budowę pełnego sumatora zaczniemy podobnie, jak pół sumatora poprzez opcję “Add Circuit” lub zielonego plusa. Nazywamy nowy układ “1-bit Full Adder”.

Używamy pierwszego półsumatora do zsumowania liczb A i B.  (Pierwsze dodawanie)
Wynik (Y) z pierwszego półsumatora przekazujemy na wejscie drugiego półsumatora pod pin B. Pod pin A podpinamy wejscie Cin. (Drugie dodawanie).
Wynik z drugiego półsumatora jest naszą sumą liczb A, B i Cin. Przeniesienie mamy wtedy, gdy pierwszy lub drugi półsumator zwrócił przeniesienie – dlatego używamy dodatkowo bramki OR:

Rys. 5. Pełny sumator 1-bitowy

Rys. 6. Pełny sumator 1-bitowy wygląd zewnętrzny

 

Sumator 8-bitowy

Do zsumowania liczby 1 bajtowej (czyli 8 bitowej), potrzebować będziemy osiem 1-bitowych sumatorów (po jednym na każdy bit 8-bitowej liczby). Wartości liczby A i B oraz dodatkowego przeniesienia.
Tworzymy układ z 8 wejsciami bitów liczby A, 8 wejsciami bitów liczby B, jedno wejscie Cin (na przeniesienie, np z poprzedniego 8-bitowego sumatora). Bedzie także 8 wyjść na bity sumy Q oraz wyjscie Cout z informacją o przeniesieniu:

Rys. 7. Wstępny układ 8-bitowego sumatora

Łączymy wszystko ze sobą:

  • wejścia liczby A0…A7 do wejść A w sumatorach,
  • wejscia liczby B0..B7 do wejść B w sumatorach,
  • wyniki Y łaczymy z odpowiednimi wyjściami Q0…Q7
  • wejście Cin łączymy do sumatora sumującego bity nr 0 liczb A i B
  • każde wyjście Cout łączymy z wejsciem Cin kolejnego sumatora – w ten sposób przekazujemy przeniesienie z poprzedniej pozycji
  • wyjscie Cout ostatniego sumatora łączymy z pinem wyjściowym Cout

Rys. 8. Sumator 8-bitowy po podłączeniu wejść i wyjść

Rys. 8. Wygląd 8-bitowego sumatora z zewnątrz

Odejmowanie to dodawanie

Odejmowanie przedstawione poniżej:

5 - 3 = 2

Możemy zapisać również w postaci sumy liczby dodatniej i ujemnej:

5 + (-3) = 2

W podobny sposób zrealizujemy odejmowanie – poprzez dodawanie liczb dodatniej i ujemnej w naszym 8-bitowym subtraktorze, wykorzystując przy tym nasz 8-bitowy sumator. Najpierw jednak trzeba wiedzieć jak liczby ujemne zapisywać.

Sposoby zapisu liczb ujemnych

Istnieje kilka sposobów zapisów liczb ujemnych w systemie binarnym.

Znak – moduł (ZM)

Zapis znak-moduł polega na tym, że pierwszy bit liczby określa czy liczba jest ujemna czy dodatnia. Liczby dodatnie i 0 mają pierwszy bit równy 0, liczby ujemne mają pierwszy bit równy 1.
Pozostałe bity oznaczają wartość absolutną liczby nazywaną modułem.

Numer cyfry 7 6 5 4 3 2 1 0
Waga -1 26 25 24 23 22 21 20
Przykład zapisu:

Liczba 3 to 00000011
Liczbę (-3) natomiast zapiszemy tak 10000011

Zapis jest banalny. W przypadku operacji arytmetycznych na liczbach zapisanych w ten sposób już nie jest tak łatwo.

W przypadku:

  1. gdy obie liczby są dodatnie – wynik jest także dodatni (bit znaku = 0)
    5 + 2 = 7 <=>0101 + 0010 = 0111
  2. gdy obie liczby są ujemne – wynik także jest ujemny (bit znaku = 1)
    -5 + -2 = -7 <=>1101 + 1010 = 1111
  3. gdy dodawane liczby są z różnymi znakami to sprawa się komplikuje:
    • zamiast dodawania należy dokonać odejmowania
    • odejmujemy liczbę z wiekszym modułem od liczby z mniejszym modułem
    • bit znaku będzie równy bitowi znaku liczby z wiekszą wartością modułu
      5 + -2 = 3 <=> 0101 - 1010 = 0011
      -5 + 2 = -3 <=> 1101 - 0010 =
      1011

Z powodu przypadku nr 3 nie jest wygodne wykorzystanie tej formy zapisu w układzie odejmującym.

 

Zapis w systemie uzupełnień do 1 – U1

Zapis w systemie uzupełnień do 1 dla najstarszego bitu w liczbie 8 bitowej waga przyjmuje wartość -(2)7 + 1

Numer cyfry 7 6 5 4 3 2 1 0
Waga -(2)7 + 1 26 25 24 23 22 21 20
Przykład zapisu:

Liczba 3 to00000011
Liczbę (-3) natomiast zapiszemy tak 11111100
Można wyciągnąć wniosek, że, aby zamienić liczbę dodatnią na ujemną w U1 wystarczy zamienić wszystkie jej bity na przeciwne.

I ponownie zapis jest w miare prosty, jednak dodawanie wymaga dodatkowej logiki:

  1. Jezeli przy dodawaniu nie nastepuje przeniesienie, to liczby są dodawane zwyczajnie:
    2 + -3 = -1 <=> 0010 + 1100 = 1110

       0010 | 2
     + 1100 | -3
     ------
       1110 | -1
  2. Jednak w przypadku, gdy wystepuje przeniesienie to do wyniku należy dodać dodatkową jedynkę:
    2 - 1 = 1 <=> 0010 + 1110 = 0000 + 1 = 0001

      111
       0010 | 2
    +  1110 | -1
    -------
       0000 | 0
    +     1 | 1
    -------
       0001 | 1

Dodatkowa logika przy dodawaniu, podobnie jak w znak-modul, wyklucza użycie takiego sposobu zapisu liczby do prostego wykorzystania w naszym subtraktorze.

Ciekawostka:

Liczbę 0 w systemie U2 można zapisać pod dwiema postaciami (na przykładzie liczb 4 bitowych):
1. 0000 = 0 * (-23 + 1) + 0 * 22 + 0 * 21 + 0 * 20 = 0 + 0 + 0 + 0 = 0
2. 1111 = 1 * (-23 + 1) + 1 * 22 + 1 * 21 + 1 * 20 =  -7 + 4 + 2 + 1 = 0

Tracimy więc możliwość zapisania dodatkowej liczby dla możliwości zapisania zera w dwóch formach.

 

Zapis w systemie uzupełnień do 2 – U2

System zapisu w systemie uzupełnień do dwóch jest podobny do U1. Wyjątkiem jest waga najstarszego bitu (w przypadku liczby 8-bitowej), która wynosi teraz-(2)7  zamiast-(2)7 + 1

Numer cyfry 7 6 5 4 3 2 1 0
Waga -(2)7 26 25 24 23 22 21 20
Przykład zapisu:

Liczba 3 to00000011
Liczbę (-3) natomiast zapiszemy tak 11111101

Sposób zamiany liczby dodatniej na ujemną:
  1. Wybieramy liczbę, np 5 = 0101
  2. Negujemy wszystkie bity (zamieniamy 1 na 0 i 0 na 1): NOT 0101 = 1010
  3. Dodajemy 1 do wyniku z pkt 2: 1010 + 0001 = 1011

Przykłady odejmowania liczb w systemie U2

2 - 3 = 2 + (-3) = -1

  0010 | (2)
  1101 | (-3)
--------
+ 1111 | -1

2 - 1 = 2 + (-1) = 1

    11   | przeniesienia
    0010 | (2)
    1111 | (-1)
--------
+ 1 0001 | 1 z przeniesieniem

Tak więc widzimy, że nie mamy problemów z sumowaniem różnych liczb i możemy bez wiekszych problemów skorzystać z tego sposobu zapisu liczby ujemnej w naszym układzie subtraktora.

Układ realizujacy dodawanie i odejmowanie liczb

Układ dodający 8-bitowe liczby mamy już zbudowany. Wykorzystamy go do stworzenia układu odejmującego 8-bitowe liczby zwyczajnie sumując pierwszą liczbę z drugą liczbą, wczesniej zamieniając drugą liczbę na ujemną.

Utwórzmy nowy zintegrowany układ “8-bit Subtractor”. Na początku stwórzmy wejscia dla dwóch liczb i zanegujmy wszystkie wejscia B bramkami NOT. (Zgodnie  z punktem 2 ze schematu zamiany liczby dodatniej na ujemną w U2)

Rys. 9. Wejscia A i B w układzie “8-bit Subtractor”

Nastepnie dodajmy nasz zbudowany sumator.
Połączmy wejscia A do wejść A sumatora, wyjścia bramek NOT podłączmy do wejscia B sumatora i wyjścia sumatora Q do wyjść Q.
Pozostała jeszcze jedna rzecz w związku z zamianą liczby B na przeciwną. Bramki NOT zamieniły nam liczbę B na liczbę ujemną, ale w systemie U1. By powstała nam liczba w systemie U2 musimy dodać ekstra-jedynkę (Zgodnie  z punktem 3 ze schematu zamiany liczby dodatniej na ujemną w U2) – robimy to przez ustawienie wartości 1 na wejściu Cin w sumatorze (poprzez element Constant z menu Wiring), udając, że mamy przeniesienie z innego sumowania – de facto zwiekszając w ten sposób wartość o 1.
Dodatkowo z racji, że liczba B jest zanegowana, pin Cin także jest zanegowany to by dostać prawidłową informację o “zapożyczeniu” (czyli przeciwieństwie “przeniesienia”) musimy także zanegować wyjście Cout oznaczające przeniesienie:

 

Rys. 10. Układ odejmujący dwie 8-bitowe liczby A i B

Rys. 11. Wygląd zewnetrzny układu odejmującego

 

Zakończenie

W ten o to sposób dotarliśmy do końca artykułu. Zbudowalismy prosty układ sumatora 1-bitowego, z którego skorzystalismy przy budowie sumatora 8-bitowego, a z którego z kolei skorzystaliśmy budująć 8-bitowy subtraktor.
Możemy już dodawać i odejmować liczby, ale przydałoby się ich nie zapominać, dlatego w następnym wpisie zbudujemy proste jednostki pamięci – przerzutniki i rejestry.

W plikach do pobrania udostępniam aktualną wersję projektu Logisim z sumatorem i subtraktorem.

Pliki do pobrania

  1. Aktualna wersja projektu