Wiesz co się liczy?

Daniel Chmielowiec

Liczby się liczy. A jak się liczy liczby? Można użyć komputera lub kalkulatora. Ale dlaczego prąd przepływający przez jakiś kawałek metalu czy innego materiału powoduje, że maszyna wykonuje jakiekolwiek obliczenia?

Wszystko co potrafi komputer to porównać ze sobą dwie wartości, oraz dodać do siebie dwie liczby.
~ J. Sobień (nauczyciel programowania)

Jeśli maszyna potrafi dodawać, to będzie w stanie wykonać inne obliczenia - w końcu odejmowanie to tak naprawdę tylko dodawanie liczb ujemnych, a mnożenie to nic innego niż wielokrotne dodawanie itd.

Jak zatem to się dzieje, że komputer potrafi dodawać? Jest to wynikiem przyjętej notacji oraz cech przewodnictwa prądu. Toczy się nawet ogólna debata na temat tego czy matematyka jest czymś co ludzie wynajdują, czy odkrywają[1].

Odpowiednio połączone tranzystory[2] przekazują sygnał dalej lub go blokują w zależności od sygnału wejściowego (ang. input), w wyniku czego otrzymywany jest sygnał wyjściowy (ang. output). Przekazując te sygnały do urządzeń elektronicznych możemy nimi sterować, np. wyświetlać piksele lub "przeczytać", które klawisze klawiatury są aktualnie wciśnięte. Aby zrozumieć jak dodaje maszyna, potrzebne będzie przyswojenie kilku podstawowych zagadnień:

  1. Jak liczyć w systemie binarnym
  2. Jak działa tranzystor
  3. Jak działają bramki logiczne

Jeśli czujesz się komfortowo z tymi zagadnieniami, możesz pominąć te sekcje i przejść od razu do Dodawania.

He-ska-me-cyda... co? Systemy liczenia

Odrobina matematyki

Na co dzień do wyrażania liczb używamy cyfr arabskich w systemie dziesiętnym. Ten system nazywa się dziesiętnym dlatego, że posiada on dziesięć symboli do zapisu wartości od 0 do 9. Co jednak, kiedy chcemy zapisać wartość większą niż 9? W takim momencie zmuszeni jesteśmy do zapisania liczby przez więcej niż jeden znak. Kiedy napiszę 14 nie oznacza to, że mam na myśli 1 + 4, czyli 5. Oznacza to, że moja liczba składa się z jednej dziesiątki oraz czterech jedności co można by zapisać jako:

14 = 1 * 10 + 4 * 1

Analogicznie w przypadku większych liczb moglibyśmy na przykład zapisać 16352 jako:

16352 = 1 * 10000 + 6 * 1000 + 3 * 100 + 5 * 10 + 2 * 1

Zauważyłeś takie dziwne, regularne zmiany w mnożniku kolejnych cyfr? Każda kolejna jest 10 razy większa od poprzedniej. Cóż za zbieg okoliczności! To akurat tyle ile mamy cyfr w przyjętym systemie liczenia. Używając tej regularności moglibyśmy zgeneralizować ten mnożnik do postaci 10^n, gdzie n oznacza pozycję cyfry licząc od 0. W powyższym przykładzie wyglądałoby tak:

pozycja cyfry (n) 4 3 2 1 0
mnożnik
10^4
10^3
10^2
10^1
10^0
cyfra 1 6 3 5 2

Zapnij pasy

System dziesiętny to nie jedyny pozycyjny system liczbowy.

mindblown.gif

W rzeczywistości sam fakt, że nazywa się pozycyjny podpowiada, że to nawet nie jedyny system liczbowy [3]. Komputer do pracy używa tzw. systemu binarnego inaczej nazywanego dwójkowym lub zerojedynkowym.

W systemie binarnym, aby zapisać liczbę, mamy do dyspozycji dwie cyfry: 0 i 1 [4]. Kiedy chcemy zapisać liczbę większą niż 1, musimy użyć większej liczby miejsc. Stąd też, aby zapisać liczbę 2, musimy napisać: 10. Taka liczba oznacza, że mamy jedną dwójkę i zero jedynek 10 = 1 * 2 + 0 * 1. Gdyby natomiast chcieć zapisać binarnie 5, musielibyśmy napisać: 101, co można rozbić na: 101 = 1 * 4 + 0 * 2 + 1 * 1. Mnożnik w tym systemie ma więc postać: 2^n.

Używając liczby 10110, tabela poniżej może wyglądać znajomo:

pozycja cyfry (n) 4 3 2 1 0
mnożnik
2^4
2^3
2^2
2^1
2^0
cyfra 1 0 1 1 0

Sprawdźmy jaka to liczba w systemie dziesiętnym.

1 * 2^4 + 0 * 2^3 + 1 * 2^2 + 1 * 2 ^ 1 + 0 * 2^0 = 16 + 0 + 4 + 2 + 0 = 22

Bin 10110 = Dec 22

Nic nie stoi na przeszkodzie, aby jako podstawę liczenia przyjąć jakąkolwiek inną liczbę naturalną np. 16 lub 9. Należałoby tylko ustalić wspólny system jak oznaczać kolejne symbole. Przyjęło się oznaczać je kolejnymi literami alfabetu łacińskiego, tak jak np. w systemie szesnastkowym, nazywanym także heksadecymalnym (hex - sześć, decy - dziesięć). Wtedy:

A = 10
B = 11
C = 12
1A = 26
itd.

Tutaj[5] możesz znaleźć więcej o systemach liczenia. Mając już pojęcie o tym jak działa system binarny, możemy zająć się kolejnym zagadnieniem.

Tranzystory

Tranzystor to taki niewielki element elektroniczny, który jest zbudowany głównie z krzemu i działa podobnie jak włącznik[6] światła. Włącznik ma dwa stany, tak jak tranzystor. Kiedy jest włączony, prąd może swobodnie przez niego przepływać. Kiedy natomiast jest wyłączony, prąd nie może przepłynąć. Podobnie tranzystor, będzie potrafił przewodzić prąd lub nie, w zależności od tego jaki sygnał dostaje. Poniżej znajduje się symbol tranzystora:

Transistor

Litera B oznacza Base, litera C - Collector, natomiast litera E - Emitter. Jeśli na base podamy logiczne 1, nasz tranzystor umożliwi przepływ prądu pomiędzy collector'em a emitter'em. Jeśli na base podamy logiczne 0, tranzystor będzie zachowywał się jak rezystor o ogromnym oporze, co uniemożliwi przepływ prądu. Możesz więc na ten moment myśleć o tranzystorze jak o włączniku światła, ale bez ruchomego przycisku powodującego przewodzenie prądu, tylko sterowanego podaniem sygnału 1, lub 0.

Transistor

Tutaj[7] znajduje się film, który wyjaśnia jak działają one na poziomie chemiczno-fizycznym.

Mając do dyspozycji takie tranzystory możemy zacząć budować coś bardziej złożonego. A konkretniej...

Bramki logiczne

Bramka logiczna[8] to taki układ elektroniczny, który posiada jedno lub więcej wejść oraz wyjście. Istotnym elementem budowy bramek logicznych są tranzystory. To właśnie one odpowiadają za "zależność" stanu takiej bramki. W zależności od stanu wejść "przepuszcza prąd dalej" do wyjścia lub nie (przekazując 1 lub 0). Istnieją trzy podstawowe bramki logiczne plus ich różne połączenia:

1. OR

Jeśli co najmniej jedno wejście znajduje się w stanie 1, bramka przekazuje 1 na wyjście. Jeśli wszystkie wejścia znajdują się w stanie 0, bramka przekazuje 0.

2. AND

Jeśli wszystkie wejścia są w stanie 1, bramka przekazuje 1 na wyjście. Jeśli co najmniej jedno wejście jest w stanie 0, bramka przekazuje 0.

3. NOT

To wyjątkowa bramka, ponieważ ma tylko jedno wejście i jest dokładną negacją tego wejścia.

Mieszanki

Istnieją także różne mieszanki powyższych. Jeśli na przykład połączyć wyjście bramki OR do wejścia bramki NOT, otrzymamy tzw NOR. Jeśli zrobimy to samo z bramką AND, otrzymamy NAND.

Jest jeszcze jeden rodzaj bramki, która nazywa się EX-OR, lub krócej XOR. Pochodzi od angielskiego Exclusive OR i różni się od podstawowego OR w taki sposób, że wyjście jest w stanie 1 tylko wtedy gdy dokładnie jedno wejście również jest w stanie 1. Poniżej znajduje się podsumowanie i porównanie bramek.

gates

Kiedy już mamy bramki logiczne, możemy przejść do sedna sprawy.

Dodawanie

Przyjmując pozycyjny system liczbowy, moglibyśmy dodawać cyfry w kolejnych pozycjach. Być może spotkałeś się już z tą metodą podczas dodawania pisemnego.

Załóżmy, że chcielibyśmy dodać takie dwie ładne liczby 10 oraz 12. Pierwszą rzeczą, którą musimy zrobić, to zamienić je na zapis binarny.

Robimy to dzieląc wielokrotnie przez 2, która jest podstawą binarnego systemu liczenia aż do momentu, kiedy dzielna będzie równa 0.

krok liczba reszta z dzielenia przez 2
0 10 0
1 5 1
2 2 0
3 1 1
4 0

Wyniki tych operacji czytamy w kolejności od dołu, co oznacza, że:

Dec 10 = Bin 1010

Robiąc to samo z 12[9] otrzymujemy 1100.

W dodawaniu pisemnym, kiedy wynikowa wartość jest większa lub równa podstawie systemu liczenia, przenosimy ją do następnej kolumny i dodajemy ją tam. W naszym wypadku, jeśli ustawimy sobie te dwie liczby do dodawania pisemnego, wygląda to tak:

| 0       | 1       | 2       | 3       | 4       | 5       |
|---------|---------|---------|---------|---------|---------|
|         |         |         |         |         |   1     |
|    1010 |    1010 |    1010 |    1010 |    1010 |    1010 |
| +  1100 | +  1100 | +  1100 | +  1100 | +  1100 | +  1100 |
| ------- | ------- | ------- | ------- | ------- | ------- |
|         |       0 |      10 |     110 |    0110 |   10110 |

Z powyższego przykładu wynika, że wynik to 10110. Zamieniając to na liczbę dziesiętną otrzymamy:

1 * 2 ^ 4 + 0 * 2^3 + 1 * 2^2 + 1 * 2^1 + 0 * 2^0 = 16 + 4 + 2 = 22

Wszystko się zgadza. 10 + 12 = 22. Wystarczy więc połączyć ze sobą dodawane cyfry w taki sposób, aby wynik z danej pozycji się zgadzał. Jeśli zrobimy to z jedną pozycją, to samo należy zrobić z pozostałymi i będziemy mogli dodawać.

Spójrzmy jeszcze raz na wynik dodawania binarnego i tym razem skupmy się na ostatnich miejscach. Mamy tam:

1. 0 + 0 = 0
2. 1 + 0 = 1
3. 0 + 1 = 1
4. 1 + 1 = 0
5. 1 + 0 = 1

Ok, czy któraś z bramek logicznych nie spełnia takiego zachowania? Dokładnie w taki sposób zachowuje się bramka XOR. Jedyny problem to ta jedynka, która idzie "dalej". Jest tak wtedy, kiedy oba wejścia są włączone. Takie zachowanie z kolei prezentuje bramka AND. Zobacz taką demonstrację:

half-adder.gif

Tak jak widzisz, kiedy podłączymy dwie cyfry obok siebie bramką XOR oraz jednocześnie bramką AND, będziemy w stanie dodać do siebie dwie jednocyfrowe (w systemie binarnym można powiedzieć jednobitowe) liczby. Taki układ nazywany jest half-adder, ponieważ aby dodawać wielobitowe liczby, musimy w następnym kroku być w stanie dodać do siebie 3 bity naraz - dwa pochodzące z liczb, i jeden z poprzedniego dodawania.

Jeśli więc chcielibyśmy dodać wynik dodawania, musimy powtórzyć kombinację XOR z AND, a jako rezultat ponownie będziemy mieli dwa bity, co w połączeniu z bitem z poprzedniej operacji daje nam trzy. To nie jest dobrze, bo chcemy mieć ponownie dwa. Jeden oznaczający wynik, a drugi, który "przejdzie dalej". Tutaj można zastosować trick w postaci bramki OR. Ta bramka zbierze oba "przechodzące" bity, bo nie robi nam różnicy, która z nich się tam znajdzie. Takie zachowanie obrazuje poniższa demonstracja:

full-adder.gif

W tym przykładzie bit znajdujący się na samej górze oznacza bit z poprzedniego działania. Taki układ nazywa się full-adder. Jeśli będziemy powtarzać te struktury, będziemy w stanie dodawać liczby składające się z większej ilości bitów.

W taki oto sposób komputer dodaje. Można więc powiedzieć, że ta umiejętność dodawania jest kombinacją dwóch czynników: demonstracji przepływu prądu przez różne materiały, oraz wymyślonego przez człowieka systemu zapisywania liczb.


  1. https://youtu.be/X_xR5Kes4Rs ↩︎

  2. https://pl.wikipedia.org/wiki/Tranzystor" ↩︎

  3. https://pl.wikipedia.org/wiki/System_liczbowy ↩︎

  4. Takie założenie pozwala w prosty sposób reprezentować liczby używając prądu. Napięcie powyżej określonego poziomu (np. 5v) oznacza 1, a poniżej - 0. ↩︎

  5. https://www.youtube.com/watch?v=Xpk67YzOn5w ↩︎

  6. Formalnie łącznik ↩︎

  7. https://www.youtube.com/watch?v=IcrBqCFLHIY ↩︎

  8. https://pl.wikipedia.org/wiki/Bramka_logiczna ↩︎

  9. Polecam wykonać takie ćwiczenie samodzielnie ↩︎

Udostępnij twitter/ facebook/ skopiuj link
Twój link wygasł
Sukces! Sprawdź swój e-mail i kliknij link, aby zakończyć logowanie.