Ćwiczenie VIII

 

1. Pojęcia

            Algorytm dodawania liczb binarnych

            Algorytm operacji arytmetycznych dla liczb w kodzie U2

            Kod BCD

            Kod Graya

2. Wiadomości

2.1 Dodawanie liczb binarnych (NKB)

 

Dodawanie liczb binarnych jest operacją arytmetyczną podobnie jak odejmowanie, mnożenie i dzielenie. Cechą charakterystyczną tej operacji jest szeregowa propagacja przeniesień. Dodawanie jest operacją dwuargumentową (argumenty oznaczono literami „a” i „b”), w której wyniku generowany jest wynik (oznaczany przez „w”) równy, co do długości dłuższemu z argumentów oraz jednobitowe tzw. przeniesienie globalne „c”. W przypadku, gdy nie rozważa się wyniku operacji ograniczonego do długości dłuższego z argumentów, to przeniesienie globalne powinno być umieszczone przed wynikiem, stając się jego najbardziej znaczącą cyfrą. W praktyce zwykle wszelkie rozważania dotyczące działań na ciągach zerojedynkowych w komputerach prowadzone są dla pewnych z góry ustalonych długości zarówno argumentów, jak i wyników.

 

Dla pojedynczego bitu wykorzystywana jest następująca tabliczka dodawania

 

ai bi ci-1 ci wi

 

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 0 1

1 0 1 1 0

1 1 0 1 0

1 1 1 1 1

 

gdzie:

ai – bit o numerze „i” pierwszego argumentu;

bi – bit o numerze „i” drugiego argumentu;

ci – przeniesienie z pozycji „i”;

ci-1 – przeniesienie na pozycję „i”;

wi – bit o numerze „i” wyniku.

 

 

 

2.2 Znajdowanie reprezentacji liczby w kodzie U2

            Mamy wartość dziesiętną W i chcemy zapisać ją w n-bitowym kodzie U2. Najpierw musimy sprawdzić, czy zakres liczb U2 obejmuje wartość W. Jeśli tak, to:

·                     Dla W nieujemnego obliczamy liczbę dwójkową o tej wartości, a następnie dopełniamy ją zerami do formatu n-bitowego.

·                     Dla W ujemnego obliczamy uzupełnienie do podstawy 2 o wartości 2n + W. Wynik kodujemy binarnie i otrzymujemy liczbę ujemną w kodzie U2.

Przykład

 

Znaleźć zapis liczby 92 w 8 bitowym kodzie U2.

Liczba jest dodatnia, więc znajdujemy jej zapis binarny:

 

 

92 : 2 = 

46

 i reszta c0 = 0

 

46 : 2 = 

23

i reszta c1 = 0

 

23 : 2 = 

11

i reszta c2 = 1

 

11 : 2 = 

5

i reszta c3 = 1

 

5 : 2 = 

2

i reszta c4 = 1

 

2 : 2 = 

1

i reszta c5 = 0

 

1 : 2 = 

0

i reszta c6 = 1

, koniec

92 = 01011100(U2)

 

Znaleźć zapis liczby -107 w 8 bitowym kodzie U2:

Liczba jest ujemna, więc najpierw obliczamy jej dopełnienie do podstawy:

Najpierw obliczamy uzupełnienie do podstawy:

U = 2n + W = 28 - 107 = 256 - 107 = 149

Wyrażamy 149 binarnie

 

 

149 : 2 = 

74

 i reszta c0 = 1

 

74 : 2 = 

37

i reszta c1 = 0

 

37 : 2 = 

18

i reszta c2 = 1

 

18 : 2 = 

9

i reszta c3 = 0

 

9 : 2 = 

4

i reszta c4 = 1

 

4 : 2 = 

2

i reszta c5 = 0

 

2 : 2 = 

1

i reszta c6 = 0

 

1 : 2 = 

0

i reszta c7 = 1

, koniec

-107 = 10010101(U2)

 

2.3 Obliczanie wartości przeciwnej w kodzie U2

            Wartość przeciwna ma tą samą wartość bezwzględną, lecz znak przeciwny. W kodzie U2 obliczamy ją następująco:

      1. Zmień wszystkie bity liczby na przeciwne (możesz wykorzystać do tego celu operację logiczną NOT).

            2. Do tak uzyskanej liczby dodaj 1

 

Wartość przeciwną do liczby  0011(U2) = 3:

NOT  0011

1100
+   0001

1101

Sprawdzenie:

1101(U2) = 1 x (-23) + 1 x 22 + 0 x 21 + 1 x 20
1101(U2) = 1 x (-8) + 1 x 4 + 0 x 2 + 1 x 1
1101(U2) = -8 + 4 + 1
1101(U2) = -3

Drugi sposób jest jeszcze prostszy

  1. Idąc od końca zapisu liczby przepisuj wszystkie zera, aż do napotkania jedynki, którą również przepisz.

Pozostałe cyfry przepisz jako przeciwne, tzn. zera zamień na jedynki i na odwrót.

Obliczmy tym sposobem liczbę przeciwną do 00110100(U2) = 52(10):

00110100
11001100

Sprawdzenie otrzymanego wyniku:

11001100(U2) = 1 x (-27) + 1 x 26 + 1 x 23 + 1 x 22
11001100(U2) = -128 + 64 +8 + 4
11001100(U2) = -52

Poprawny wynik.

 

2.4 Dodawanie i odejmowanie w kodzie U2

 

Zasady dodawania i odejmowania liczb w kodzie U2 nie różnią się od zasad wykonywania tych działań arytmetycznych w zwykłym systemie binarnym, co jest niewątpliwą zaletą kodu U2. Sprawdzenie:

 

5 + (-3)
  
0101
+ 1101

     

2-(-3)
  0010
- 1101

1 0010
Wynik 2

 

1 0101
Wynik 5

 

Otrzymaliśmy poprawne wyniki operacji bez sprawdzania znaków przetwarzanych liczb. Jest to bardzo dużą zaletą kodu U2, dzięki której obliczenia są szybkie i sprawne.

 

 

W systemie U2 dodawanie i odejmowanie wykonujemy wg poznanych zasad dla naturalnego kodu dwójkowego. Przeniesienia i pożyczki poza bit znaku ignorujemy.

 

2.5 Mnożenie w kodzie U2

 

            Mnożenie liczb w kodzie U2 różni się nieco od standardowego mnożenia liczb binarnych. Przed wykonaniem tej operacji arytmetycznej musimy rozszerzyć znakowo obie mnożone liczby tak, aby ich długość (liczba bitów) wzrosła dwukrotnie (jeśli są różnej długości, to rozszerzamy znakowo względem dłuższej liczby). Rozszerzenie znakowe polega na powielaniu bitu znaku na wszystkie dodane bity.

 

Np.:

0111(U2) = 0000 0111(U2) - rozszerzenie znakowe liczby 4 bitowej do 8 bitowej
1011(U2) = 1111 1011(U2) - to samo dla liczby ujemnej.

 

Rozszerzenie znakowe nie zmienia wartości liczby w kodzie U2. Po wykonaniu rozszerzenia znakowego liczby mnożymy wg poznanych już zasad. Dla przykładu pomnóżmy (-2) x 3:

 

-2 = 1110(U2) - 1111 1110(U2)
3 = 0011(U2) = 0000 0011(U2)

(-2) x 3
11111110
x  00000011

 11111110
+ 11111110
 

1011111010
Wynik = -6

 

Wynik mnożenia może być liczbą o długości równej sumie długości mnożonych liczb. Dlatego bity wykraczające w naszym przykładzie poza 8 bitów ignorujemy. Pozostałe 8 bitów określa w kodzie U2 liczbę -6. Zatem rachunek zgadza się.

2.6 Dzielenie w kodzie U2

 

            Najprostszym rozwiązaniem jest zapamiętanie znaków dzielonych liczb, zamiana ich na liczby dodatnie, dokonanie dzielenia dla liczb naturalnych, a następnie zmiana znaku wyniku, jeśli znaki dzielnej i dzielnika różnią się.

 

Podzielmy 6 przez -3:

 

6 = 0110(U2)
-3= 1101(U2)
- zmieniamy na 3 = 0011(U2)

 

Dzielimy liczbę 0110 przez 0011

    10
  0110 : 0011
- 011
  0000
  0011

 

Otrzymaliśmy wynik 0010  (liczba 2). Ponieważ znaki dzielnej i dzielnika są różne, zmieniamy znak wyniku na przeciwny:

 

 

NOT  0010

1101
+   0001

1110

 

I ostatecznie otrzymujemy wynik 1110(U2) = -2.

 

Jeśli w trakcie dzielenia otrzymamy resztę, to musi ona mieą ten sam znak, co dzielna. Zbierzmy i podsumujmy  reguły określania znaków wyniku i reszty z dzielenia w poniższej tabelce.

 

 

Reguły znaków przy dzieleniu
liczb całkowitych

Dzielna

Dzielnik

Wynik

Reszta

plus

plus

plus

plus

plus

minus

minus

plus

minus

plus

minus

minus

minus

minus

plus

minus

 

 

2.7 Nadmiar i niedomiar w kodzie U2

 

            W trakcie wykonywania działań arytmetycznych wynik operacji może przekroczyć dozwolony zakres liczb zarówno powyżej górnej granicy (nadmiar) jak i poniżej dolnej (niedomiar). Cechą charakterystyczną nadmiaru/niedomiaru jest zmiana znaku wyniku w sytuacji, gdy nie powinna ona nastąpią. Załóżmy, iż operujemy na 4 bitowych liczbach w kodzie U2 i chcemy wykonać proste dodawanie:

 

0 111
+   0 001

     

7
+ 1

1 000

 

-8

 

 

Otrzymany wynik jest niepoprawny w tym kodzie. Spowodowane to jest tym, iż liczba 8 będąca sumą 7 i 1 wykracza poza górny kres wartości 4 bitowego kodu U2 (równy 7) i nie można jej poprawnie przedstawią - musielibyśmy przeznaczyć na zapis liczby więcej bitów.

Podobną sytuację zastaniemy przy próbie dodania dwóch liczb ujemnych, np. -6 i -3:

 

 

1 010
+   1 101

     

-6
+ -3

10 111

 

7

 

 

Liczba -9 jest mniejsza od dolnego krańca 4 bitowych liczb w kodzie U2 (równego -8) i z tego powodu nie może być poprawnie przedstawiona w tym kodzie.

 

 

Wystąpienie nadmiaru lub niedomiaru jest wskazówką, iż liczby są reprezentowane zbyt małą ilością bitów i nie można poprawnie zapisywać wyniku operacji. Najprostszym rozwiązaniem będzie zwiększenie liczby bitów dla liczb w kodzie U2 (np. z 16 na 32).

 

2.8 Kod ASCII

 

      Przechowywanie i przetwarzanie danych przez układy elektroniczne komputera ma miejsce z wykorzystaniem systemu binarnego. Należy więc przedstawić tekst za pomocą liczb czyli jednoznacznie przyporządkować  literom i innym znakom alfanumerycznym - liczb (numerów). W ten sposób powstał w 1965 r. kod ASCII (American Standard Code for Information Interchange). Oczywiście kod ten jest jawny i używany przez wszystkich użytkowników i twórców oprogramowania. Jest to kod 7 bitowy, a więc możemy za jego pomocą przedstawią 2^7 czyli 128 znaków. W 1981 r. IBM wprowadził rozszerzony do 8 bitów kod, co pozwala  na przedstawienie 256 znaków (w tym znaki specjalne, graficzne, matematyczne i diakrytyczne znaki narodowe)

 

 

Znak

Kod dzies.

Kod binarny

Znak

Kod dzies.

Kod binarny

A

65

01000001

a

97

00110001

B

66

01000010

b

98

00110010

C

67

01000011

c

99

00110011

K

75

01001011

k

107

01101011

L

76

01001100

l

108

01101100

ź

171

10101011

Ż

189

10111101

¦

179

10110011

Ă

198

11000110

+

188

10111100

-

196

11000100

 

 

            W kodzie ASCII znaki o kodach od 0 do 31 reprezentują kody sterujące wykorzystywane do komunikacji z terminalami oraz innymi urządzeniami I/O. Znaki o kodach powyżej 31 reprezentują drukowalne symbole alfanumeryczne. Rozszerzony kod ASCII umożliwia zapis symboli na ośmiu bitach, a więc pozwala zakodować 256 symboli. Znaki o kodach od 128 do 255 są pewnymi symbolami graficznymi, których postać zależy od zainstalowanego zestawu symboli alfanumerycznych.

 

 

Przykładowy zestaw znaków o kodach od 32 do 255 może mieć następującą postać:

 

 

 

 

 

Extended ASCII

256 możliwych kombinacji bitów w jednym bajcie to jednak za mało, by zapisać znaki specyficzne dla różnych języków świata, jak polskie „ąćęłńóśżź” czy niemieckie „umlauty” (nie mówiąc już o zupełnie innych alfabetach, jak cyrylica czy znaki chińskie).

 

Dlatego dodatkowe 128 znaków powstałe po użyciu ósmego bitu nie jest ujednolicone. Stworzonych zostało wiele tzw. stron kodowych (ang. codepage) używających tych dodatkowych znaków do kodowania liter alfabetów narodowych, a przy tym różnych symboli graficznych i innych bardziej lub mniej przydatnych.

 

Jest z tym niestety dużo problemów. Nawet dla samego języka polskiego powstało kilka kodów. Obecnie używane są dwa:

 

1.      ISO-8859-2 (Latin-2)

2.      Windows-1250

 

Ten drugi jest przez wielu krytykowany za to, że został wylansowany przez Microsoft. W praktyce jednak to właśnie jego używa system Windows, a wielu miejscach Internetu jest on nie mniej popularny, niż ten pierwszy.

 W wielu zastosowaniach, szczególnie w Internecie (WWW, e-mail) w nagłówku zapisywana jest nazwa standardu kodowania użytego w danym dokumencie. Pozwala to zminimalizować problemy wynikające z róznych form zapisu.

 

Unikod

Rozwój Internetu stworzył konieczność wynalezienia lepszego sposobu kodowania znaków, niż wysłużony już kod ASCII. Nawet ze swoimi stronami kodowymi ten ostatni ma wiele ograniczeń i sprawia wiele problemów. Nie można chociażby zapisać tekstu w kilku różnych językach w jednym dokumencie.

 

W ten sposób zwiększono liczbę bajtów kodujących pojedynczy znak. Tak powstał Unikod (ang. Unicode, w skrócie UCS). Warto zdać sobie sprawę z faktu, że już za pomocą 2 bajtów można zakodować 216 = 65536 różnych znaków! Dlatego w unikodzie znalazło się miejsce dla wszelkich użytecznych i używanych na świecie liter, symboli i znaków, a po upowszechnieniu się tego standardu nasze dzieci będą już tylko od nas słyszały historie, jakie to kiedyś były problemy w komputerze z kodowaniem znaków :)

 

Najpopularniejszymi odmianami unikodu są UTF-8 i UTF-16. W tej pierwszej znak może mieć różną długość. Pierwsze 128 znaków pokrywa się z tablicą ASCII i jest zapisywana za pomocą jednego bajta, natomiast znaki dodatkowe (np. polskie literki) są zapisywane za pomocą specjalnych kilkubajtowych sekwencji. Z kolei UTF-16 określa standard, w którym każdy znak zajmuje 2 bajty.

 

2.9 Kod BCD (8421)

 

            Podstawowym wagowym kodem BCD jest kod BCD 8421 (w skrócie kod BCD), w którym kolejne cyfry dziesiętne są kodowane za pomocą pierwszych dziesięciu słów naturalnego kodu binarnego (NKB).

 

Wagi: 8 4 2 1

 

            Cyfry

                        0 0 0 0 0

                        1 0 0 0 1

                        2 0 0 1 0

                        3 0 0 1 1

                        4 0 1 0 0

                        5 0 1 0 1

                        6 0 1 1 0

                        7 0 1 1 1

                        8 1 0 0 0

                        9 1 0 0 1

 

Przykład 2.1. Przedstawić liczbę dziesiętną 347 w kodzie BCD 8421.

 

Kodując każdą cyfrę dziesiętną na czterech bitach otrzymujemy reprezentację liczby 347 w kodzie BCD 8421.

 

3 4 7

0011 0100 0111.

 

            Można zauważyć, że dla przedstawienia liczby dziesiętnej w kodzie BCD zwykle trzeba więcej bitów niż do zakodowania tej liczby w kodzie NKB. Liczba 34710 może być zapisana w kodzie NKB na dziewięciu bitach w postaci 1 0101 1011, natomiast w kodzie BCD wymaganych jest dwanaście bitów

 

 

2.10 Kod Aikena (2421)

 

            Kod ten jest kodem wagowym BCD o wagach 2, 4, 2, 1. Sposób kodowania cyfr w kodzie Aikena przedstawiono poniżej.

 

Wagi: 2 4 2 1

 

Cyfry

            0 0 0 0 0

            1 0 0 0 1

            2 0 0 1 0

            3 0 0 1 1

            4 0 1 0 0

            5 1 0 1 1

            6 1 1 0 0

            7 1 1 0 1

            8 1 1 1 0

            9 1 1 1 1

 

            W kodzie tym cyfry od 0 do 4 koduje się z wyzerowanym najstarszym bitem, natomiast cyfry od 5 do 9 z ustawionym najstarszym bitem. Liczba dziesiętna 347 ma w kodzie Aikena następującą postać:

 

3 4 7

0011 0100 1101.

 

2.11 Kod Graya

 

            Przykładem niewagowego kodu binarnego jest kod Graya, w którym sąsiednie słowa różnią się wartością tylko jednego bitu. Ponadto wartości słów różnią się o możliwie małą wielkość, a słowa kodowe są unikalne. Poniżej przedstawiono sposób kodowania danych z wykorzystaniem 3-bitowego kodu Graya.

 

 

0 – 0 0 0

1 – 0 0 1

2 – 0 1 1

3 – 0 1 0

4 – 1 1 0

5 – 1 1 1

6 – 1 0 1

7 – 1 0 0

 

 

 

Kod binarny

XOR

Kod Gray'a

000(2)

000
 00
0
000(Gray)

000(Gray)

001(2)

001
 00
1
001(Gray)

001(Gray)

010(2)

010
 01
0
011(Gray)

011(Gray)

011(2)

011
 01
1
010(Gray)

010(Gray)

100(2)

100
 10
0
110(Gray)

110(Gray)

101(2)

101
 10
1
111(Gray)

111(Gray)

110(2)

110
 11
0
101(Gray)

101(Gray)

111(2)

111
 11
1
100(Gray)

100(Gray)

 

Taki kod Gray'a nosi nazwę kodu odzwierciedlonego binarnie (binary reflected Gray Code). Otrzymanie wartości binarnej z wyrazu w kodzie Gray'a jest dla tych kodów równie proste. W tym celu kopiujemy najstarszy bit wyrazu w kodzie Gray'a do najstarszego bitu wyrazu binarnego. Resztę bitów binarnych otrzymamy wykonując operację XOR na i-tym bicie kodu Gray'a i (i+1) bicie wyrazu binarnego. Oto przykład.

Najpierw utwórzmy ze słowa binarnego 1101 wyraz w kodzie Gray'a:

1101(2)
 1101
1011(Gray)

Teraz dokonamy konwersji odwrotnej:

1011
    
1
xxx

Przepisujemy do wyniku najstarszy bit.

1011
 1
  
11xx

Bit ten zapisujemy pod spodem na pozycji przesuniętej w prawo i obliczamy funkcję XOR z bitem kodu Gray'a

1011
 11  
110x

Otrzymany w wyniku operacji XOR bit umieszczamy pod spodem obok poprzedniego bitu

1011
 110
1101

Operację tą wykonujemy ponownie i otrzymujemy słowo binarne.

 

 

 

Zadania i ćwiczenia

 

Zadanie 1

Oblicz wartość następujących liczb w kodzie Z-M:

 

(1 0011101)(ZM), (0 1101100)(ZM), (1 1110110)(ZM)

 

Zadanie 2

Przedstaw w 8 bitowym kodzie Z-M liczby dziesiętne:

 

                                    -45, 126, -99

 

Czy kod Z-M jest całkiem efektywny?

 

Ile bitów jest potrzebne na zapis w kodzie Z-M liczb z zakresu od <-26, 45> ?

 

Zadanie 3

Wykonaj następujące operacje arytmetyczne na liczbach w kodzie Z-M:

 

 

 

 0110111
+ 1101110

  

10001011
+ 10111010

 

11101110
- 01011100

 

00001101
- 10011011

 

 

 

 

 

 

Zadanie 4

Zamienić na system 10

 

(11011)NKB

 

(11011)U2

 

(11011)8

 

(AF)16

 

 

Zadanie 5

 

Obliczyć wartość podanych liczb w kodzie uzupełnień do dwu

 

(-42)10

(-38)10

(-128)10

(FF)16

(77)8

 

 

Następnie policzyć dla tych liczb ich wartości przeciwne w kodzie U2

 

 

 

Zadanie 6

 

Wykonać działania

 

(77)U2 + (100)U2

(77)U2 – (100)U2

(150)U2 +- (244)U2

 

Sprawdzić poprawność

 

Zadanie 7

 

Mamy ciąg a[] n elementów oraz tablicę b[] również n-elementową (wyzerować)

Sprawdzić jakie liczby znajdują się w tablicy a[], jeżeli w tej tablicy a[] znajduje się wartość k, to na pozycji b[k] powinna znajdować się 1, w przeciwnym przypadku 0.

 

 

Zadanie 8

 

Napisać program w pseudokodzie (Pascalu) pobierający od użytkownika podstawę systemu liczbowego oraz liczbę w tym systemie i następnie wyświetlający wartość wprowadzonej liczby w systemie 10.

           

Zadanie 9

 

Napisać program w pseudokodzie (Pascalu):

-           pobierający od użytkownika liczbę (-128, 127) i zamieniający na postać U2

-           zmieniający znak liczby zapisanej w U2

-           dodający dwie liczby w U2

 

 

Zadanie dodatkowe (1 pkt)

 

Napisać program pobierający liczbę w systemie dziesiętnym i zamieniający na kod Graya – ciąg znaków oraz pobierający liczbę w postaci kodu Graya i zamieniający na postać dziesiętną.

 

 

Projekt

 

1)     Operacje dodawania, odejmowania, mnożenia oraz dzielenia ze znakiem.

2)     Zamiana liczby z jednego systemu liczenia na drugi (zadany).

 

 

Przykłady

 

(00000000)U2 = 0

(01010101)U2 = 64 + 16 + 4 + 1 = 85

(11110000)U2 = -128 + 64 + 32 + 16 = -16

(11000011)U2 = -128 + 64 + 2 + 1 = -61

(11000000)U2 = -128 + 64 = -64

(10101010)U2 = -128 + 32 + 8 + 2 = -86

(150)U2 = (10010110)U2 = -128 + 16 + 4 + 2 = -126

(188)U2 = (10111100)U2 = -128 + 32 + 16 + 8 + 4 = -68

(200)U2 = (11001000)U2 = -128 + 64 + 8 = -56

(255)U2 = (11111111)U2 = -128 + 64 + 32 + 16 + 8 + 4 +2 + 1 = -1