# SYK

### Zadanie 1





### Zadanie 2
| C P | A | B | Komentarz |
| ---- | ---- | ---- | --- |
| 0 **0000** | 1001 | 1101 | |
|||| ↓ Dodanie B |
| 0 **1101** | 1001 | 1101 | |
|||| ↓ Shift w prawo (PA) |
| 0 **1110** | **1**100 | 1101 | |
|||| ↓ Dodanie 0 <BR>↓ Shift w prawo (PA) |
| 0 **1111** | **01**10 | 1101 | |
|||| ↓ Dodanie 0 <BR>↓ Shift w prawo (PA) |
| 0 **1111** | **101**1 | 1101 | |
|||| ↓ Dodanie B |
| 1 **1100** | **101**1 | 1101 | |
|||| ↓ Shift w prawo (PA) |
| 0 **1110** | **0101** | 1101 | |

Rejestr ( P ) przechowuje teraz liczbę w U2
Podczas przesuwania w prawo chcemy zachować wartość części rejestru (PA) odpowiadającą wynikowi.
Aby to uzyskać jedyna zmianą jest to, że, po przesunięciu najbardziej znaczący bit powinien być
aktualną wartością najbardziej znaczącego bitu.

### Zadanie 3
Pomysłem stojącym za metodą "shifting over zeros" jest pominięcie operacji dodawania, jeśli najmniej znaczącycy bit A ma wartość 0 (oczywiście nie pomijamy przesunięcia). Stąd nazwa "shifting over zeros". W praktyce jednak rzadko korzysta się z tej metody, ze względu na złożoność czasową zależną od argumentów oraz brak znaczącej przewagi w porównaniu do zwykłych algorytmów.
| P | A | B | Komentarz|
| ---- | ---- | -----| --- |
| 0000 | 1001 | 0011 | init |
||||standardowe dodanie + <br>przesunięcie|
| 0001 | 1100 | 0011 | |
|||| pomijamy dodawanie!<br>samo przesunięcie |
| 0000 | 1110 | 0011 | |
|||| pomijamy dodawanie!<br>samo przesunięcie|
| 0000 | 0111 | 0011 | |
|||| standardowe dodanie + <br>przesunięcie|
| 0001 | 1011 | 0011 | koniec, wynik = 27|

### Zadanie 4
Kodowanie Booth'a bazuje na następującej obserwacji:
Wykorzystując ją, możemy na podstawie dwóch kolejnych bitów liczby A (przyjmujemy a_-1=0) decydować, czy do wyniku dodajemy B, czy -B.
Najwyższy bit przechodzi z poprzedniego stanu (jest duplikowany)
Przykład mnożenia dla A=-9 B=3
| P | A | B | -B |Komentarz|
| ---- | ---- | ----- | --- | --- |
| 00000 | 10111 | 00011 |11101| init| |
||||| a₀=1, a_-1=0, odejmujemy B|
| 11110 | 11011 | 00011 | 11101| |
||||| a₁=1, a₀=1, dodajemy 0|
| 11111 | 01101 | 00011 | 11101| |
||||| a₂=1, a₁=1, dodajemy 0|
| 11111 | 10110 | 00011 | 11101 | |
||||| a₃=0, a₂=1, dodajemy B|
| 00001 | 01011 | 00011 |11101| |
||||| a₄=1, a₃=0, odejmujemy B|
| 11111 | 00101 | 00011 |11101| |
### Zadanie 5

Reguły wykonywania dodawania do rejestru P korzystając z kodowania Booth'a:

Powyższe rozważania można podsumować, że w każdym kroku mamy:
$P := P + B * (a_{i-1} - a_{i})$ -> wybór znaku został przedstawiony w niebieskiej "ramce" na rysunku powyżej.

Zatem rozwiązanie polega na niejawnej zamianie liczby A (ze znakiem) na postać Booth'a (1, 0 oraz -1 dla każdej pozycji bitowo). Zamiana ta odbywa się zgodnie ze wskazówkami z Appendix J - korzysta z obserwacji, że ciąg postaci k jedynek: `111...1` można zamienić na k+1 elementowy ciąg `100...0(-1)`.

Podczas kolejnych kroków (tj. po kolejnych przesunięciach rejestru liczby A) gdy wirtualny bit w reprezentacji Booth'a jest równy 1 -> następuje dodanie B do rejestru P, a gdy równy -1 -> odjęcie. Bity z reprezentacji Booth'a są liczone na bieżąco -> na bazie $a_{-1}$ oraz $a_{0}$, później $a_{0}$ oraz $a_{1}$ itd. rozważając kolejne shift'y.

Odpowiednie przesunięcie zostaje wykonane po każdym kroku algorytmu - wiemy więc że będziemy dodawać bity pochodzące z B na odpowiedniej pozycji.

Zgodnie z obserwacjami z Appendix J. uznajemy, że $a_{-1}=0$, co jest zgodne z naturalną intuicją.

Obliczanie wartości A*B dla A = -9 oraz B = -3.
A w systemie U2: 10111 (-16 + 4 + 2 + 1) -> w rejestrze dopiszę 0 na końcu
B w systemie U2: 11101 (-16 + 8 + 4 + 1)

(w rzeczywistości podział rejestru na P i A nie istnieje - wprowadzam dla czytelności)
|rejestr P|rejestr A| co się dzieje?|
|-|-|-|
| 00000 | 101110 | następuje wstępne wpisanie danych do rejestrów |
||| zauważmy, że B to 11101 |
||| zauważmy, że B to -B to 00010 + 00001 = 00011 - trzymamy to w pamięci |
||| rozpoczynamy obliczenia |
| 00011 | 101110 | różnica ostatnich bitów w A to 0 - 1 = -1 => dodajemy -B do P |
| 00001 | 1 \ 10111 | shift right |
| 00000 | 11 \ 1011 | różnica ostatnich bitów w A to 1 - 1 = 0 => shift indeksów |
| 00000 | 011 \ 101 | różnica ostatnich bitów w A to 1 - 1 = 0 => shift indeksów |
| 11101 | 011 \ 101 | różnica ostatnich bitów w A to 1 - 0 = 1 => dodajemy B do P |
| 11110 | 1011 \ 10 | shift right, na przodzie duplikuję 1 (własności U2)|
| 00001 | 1011 \ 10 | różnica ostatnich bitów w A to 0 - 1 = -1 => dodajemy -B do P 11110 + 00011 = 100001 carry out pomijamy|
| 00000 | 11011 \ 1 | shift right|

Uzyskaliśmy 0000011011 = 1 + 2 + 8 + 16 = 27, czyli poprawny wynik

Aby obsłużyć ujemne liczby w rejestrze B korzystamy z obserwacji z zadania 2: mianowicie "najbardziej znaczący bit powinien być alternatywą carry out, oraz aktualnej wartości najbardziej znaczącego bitu."

### Zadanie 6

Schemat:

Zwyczajowo stosuje się proporcję 3:2 dla IN:OUT. Wtedy na wejściu otrzymujemy 3 liczby, a na wyjściu zwracamy jak niżej:
Używając CSA, uzyskujemy proporcję 3:2 w liczbach wierszy na wejściu

OUT_1 można zdefiniować jako: $a \oplus b \oplus c$ (nie shiftujemy, ma tyle samo bitów)
OUT_2 można zdefiniować jako: $ab \vee ac \vee bc$ (OUT_2 przy wyjściu jest przesuwany o jeden bit w lewo)

### Zadanie 7

<!--  -->

Koncept tego algorytmu polega na sprawdzeniu czy od liczby (po kolejnych przesunięciach) można odjąc liczbę m (dzielnik). Wynik jest konstruowany od lewej strony (zgodnie z naturalną koncepcją dzielenia liczb "na kartce")

Chodzi o to, że (w przypadku liczb bez znaku) Q / m = B gdy B to największa liczba naturalna taka że Q - M*b >= 0.

Zatem dla każdego bitu dzielnika sprawdzamy, czy powinien być zapalony, czy też zgaszony.
Jeśli mamy po odjęciu liczby m od Q (przesuniętego odpowiednio) A[n] = 1 liczba stała się ujemna (U2), zatem próbowaliśmy "podzielić" przez zbyt dużą liczbę. Ustawiamy wtedy Q[0] na 0 (ten bit dzielnika musi być zgaszony). Należy również wykonać naprawę. Trzeba ustawić bity w A na takie, jakie były przed nieudaną próbą dzielenia/odejmowania (następuje zw. "restoring"). Jednak gdy A[n] = 0 nasz wynik wciąż jest nieujemy - zatem wiemy, że dana pozycja bitowa w dzielniku musi zawierać wartość 1.

Powyższe kroki wykonujemy dopóki nasza liczba jest niepusta, ostatecznie przez magazynowanie odpowiednich wartości w Q[0] na przemian wykonując shift left dostaniemy wynik dzielenia w rejestrze Q oraz wartość reszty z dzielenia w rejestrze A.

Wykonajmy następnie dzielenie przykładowych 2 liczb z treści zadania. Mamy dane:
Q = 9, M = 3

Bitowo:
Q = 1001 (8 + 1)

Bitowo w U2:
M = 00011 (2 + 1)
-M = 11100 + 00001 = 11101 (-16 + 8 + 4 + 1)

| n | A | Q | opis wykonywanych operacji
|-|-|-|-|
|4| 00000 | 1001 | wstępna inicjalizacja
|4| 00001 | 001? | shift left
|4| 00001 | 001? | próba odjęcia M (tj dodania -M)
|4| 11110 | 001? | próba okazała się nieudana
|4| 00001 | 0010 | przywróć A, na stan przed próbą, przypisz 0 do `?`
|3| 00001 | 0010 | n -= 1
|3| 00010 | 010? | shift left
|3| 00010 | 010? | próba odjęcia M (tj dodania -M)
|3| 11111 | 010? | próba okazała się nieudana
|3| 00010 | 0100 | przywróć A, na stan przed próbą, przypisz 0 do `?`
|2| 00010 | 0100 | n -= 1
|2| 00100 | 100? | shift left
|2| 00100 | 100? | próba odjęcia M (tj dodania -M), mamy 00100 + 11101 = 100001, ucinamy curry-out - mamy 00001
|2| 00001 | 1001 | próba okazała się udana, przypisz 1 do `?`
|1| 00001 | 1001 | n -= 1
|1| 00011 | 001? | shift left
|1| 00011 | 001? | próba odjęcia M (tj dodania -M) mamy 00011 + 11101 = 00001 + 11111 = 100000
|1| 00000 | 0011 | próba okazała się udana
|0| 00000 | 0011 | n -= 1, skoro n==0 kończymy

Wynik = 0011 => 3, reszta = 00000 => 0 (zgodnie z prawdą)

### Zadanie 8



<u>Algorytm:</u>

Powtórz n razy:

Jeśli P < 0:
a) Przesuń rejestr (PA) w lewo
b) Dodaj zawartość rejestru B do rejestru P.
W przeciwnym razie:
a) Przesuń rejestr (PA) w lewo
b) Odejmij zawartość rejestru B od P
Jeśli P < 0:
a) Ustaw najmniej znaczący bit A na 0
W przeciwnym razie:
a) Ustaw najmniej znaczący bit A na 1

Iloraz znajduje się w rejestrze A. Reszta znajduje się w rejestrze P.
Jeśli reszta jest ujemna, należy dodać do niej wartość B.

Różnica pomiędzy algorytmami restoring i nonrestoring polega na tym, że w wersji
nonrestoring jeśli po odjęciu wartości B wartość P stanie się ujemna, to nie przywracamy poprzedniej wartości poprzez dodanie wartości B.

| P | A | B | wykonana operacja|
| -------- | -------- | -------- | -------- |
| 00000 | 1001 | 00011 | inicjalizacja |
| 00001 | 001? | 00011 | Shift w lewo |
| 11110 | 001? | 00011 | odjęcie B od P |
| 11110 | 0010 | 00011 | ustawienie najmniej znaczącego bitu A na 0 |
| 11100 | 010? | 00011 | Shift w lewo |
| 11111 | 010? | 00011 | dodanie B do P |
| 11111 | 0100 | 00011 | ustawienie najmniej znaczącego bitu A na 0 |
| 11110 | 100? | 00011 | Shift w lewo |
| 00001 | 100? | 00011 | dodanie B do P |
| 00001 | 1001 | 00011 | ustawienie najmniej znaczącego bitu A na 1 |
| 00011 | 001? | 00011 | Shift w lewo |
| 00000 | 001? | 00011 | odjęcie B od P |
| 00000 | 0011 | 00011 | ustawienie najmniej znaczącego bitu A na 1 |

*Uzasadnienie poprawności*
Zauważmy, że działanie tego algorytmu jest podobne do działania algorytmu restoring division
Gdy P jest dodatnie, algorytm działa tak samo jak restoring division
Gdy P jest ujemne, to nie wykonujemy restore w rejestrze P, więc
wartość w rejestrze P jest mniejsza o B niż w sytuacji gdybyśmy zrobili restore
następnie po przesunięciu w lewo P w następnym kroku wartość w P jest mniejsza o 2B niż gdybyśmy zrobili restore,
ale skoro P jest ujemne to ten algorytm doda B do P
stąd otrzymamy odpowiednią wartość P, tak jak w algorytmie restoring division.

### Zadanie 9

**Przedstaw algorytm dzielenia metodą SRT (ang. SRT division).**
Dzielimy **a** przez **b** obie są liczbami n bitowymi
Zapisujemy a do rejestru A (długość n)
Zapisujemy b do rejestru B (długość n)
Rejestr P trzyma na początku 0 (długość n+1)

1. Jeśli rejestr B ma k zer wiodących w zapisie n bitowym przesuń rejestr B oraz rejestr (PA) w lewo o k bitów
2. For i=n-1 to 0:
+ a) Jeśli 3 najbardziej znaczące bity P są sobie równe:<BR>przesuń rejestr (PA) w lewo, ustaw najmniej znaczący bit A na 0

+ b) Jeśli 3 najbardziej znaczące bity P nie są sobie równe i P jest ujemne:<BR>przesuń rejestr (PA) w lewo, ustaw najmniej znaczący bit A na -1, dodaj B do P.
- c) w przeciwnym przypadku:<BR>przesuń rejestr (PA) w lewo, ustaw najmniej znaczący bit A na 1, odejmij B od P.
End loop
3. Jeśli reszta ( P ) jest ujemna popraw wynik (A) odejmując od niego 1, oraz dodając B do P
4. Rejestr P musi być przesunięty o k bitów w prawo (odwracając przesunięcie z kroku 1)
5. A to iloraz P to reszta

**Uzasadnij jego poprawność**
<!-- Dla uproszczenia
Część rejestru (PA) reprezentującą dzielnik będę oznaczał jako
X, że X = P,A (przecinek rozdiela część ułamkową)

Natomiast część rejestru A oznaczającą aktualną część wyniku jako Q
Po wprowadzeniu danych

Na początku
Dzielna = X*2ⁿ
Dzielnik = B

Uzasadnienie niezmiennika:
(X*2^c)/B + Q = wynik
podczas wykonywania algorytmu
**1. Po wykonaniu przesunięcia o k bitów**
(X\*2ⁿ\*2^k)/(B\*2^k) + Q = wynik
**2.a**
m<=n
(P\*2^m\*2^k)/(B\*2^k) + Q = wynik
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
(P\*2^m-1\*2^k)/(B\*2^k) + Q = wynik
Przesuwamy P w lewo, więc P jest 2 razy większe,ale
2^m → 2^m-1, więc jest wszystko ok
**2.b**
(P\*2^m\*2^k)/(B\*2^k) + Q = wynik
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
((P+B)\*2^m-1\*2^k)/(B\*2^k) + Q - 2^m-1 = wynik
Analogicznie przesunięcie P nic nie zmienia, a dodanie 2^m-1 wyrównane jest poprzez dodanie B do P
**2.c**
(P\*2^m\*2^k)/(B\*2^k) + Q = wynik
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
((P-B)\*2^m-1\*2^k)/(B\*2^k) + Q + 2^m-1 = wynik
**3**
Ten krok działa tak jak **2.b**
**4**
Sytuacja przed rozpoczęciem tego kroku wygląda następująco
((P*2^k)/(B\*2^k) + Q = wynik
Widać, że w celu uzyskania reszty z dzielenia przez B należy przesunąć
P o k bitów w prawo -->

x,y - liczby bez znaku
dzielimy $\frac{x}{y}$
Na początku rejestr
$A = x$
$B = y$
$P = 0$
Dla uproszczenia
Część rejestru ( PA ) reprezentującą resztę będę oznaczał jako X,
Część rejestru ( PA ) reprezentującą iloraz będę oznaczał jako Q,

---

**Fakt 1.**(pokazany poźniej)
Przed/po każdej iteracji pętli
$P \in <-B,B)$

**Dowód Faktu 1**
Przed/po każdej iteracji pętli
$P \in <-B,B)$

Przed pierwszą iteracją P=0, więc teza zachodzi
Jeśli dzielimy liczby n bitowe, to P
$P\in<-2^n,2^n-1>$,
w rejestrze B najbardziej znaczący bit jest równy 1
$B\in<2^{n-1},2^n-1>$

2.a Gdy 3 najbardziej znaczące bity są sobie równe, to po SL
2 najbardziej znaczące bity są sobie równe, więc
$P \in <-2^{n}+2^{n-1},2^{n-2}+2^{n-1}+...+1>$
$P \in <-2^{n-1},2^{n-1}-1>$
Skor B jest równe co najmniej $2^{n-1}$ , to
$P\subseteq<-B,B)$
2.b P jest ujemne, więc
$P \in <-2^n,-1>$
po dodaniu B do P
$P \in <-2^n+2^{n-1},-1+B>$,więc
$P \in <-2^{n-1},B-1>$
$P\subseteq<-B,B)$
3.c P jest dodanie/równe 0, więc
$P \in <0,2^n-1>$
po odjęciu B od P
$P \in <0-B,2^n-1-2^{n-1}>$
$P \in <-B,2^{n-1}-1>$
$P \in <-B,2^{n-1}-1>$
$P \in <-B,B)$

---

Na początku oczywiście
$Q = 0$
I poprawny jest niezmiennik, przed każdą iteracją zachodzi:
$\frac{X}{B} + Q*2^{i} = wynik$
gdzie i to zmienina i w pętli for danej iteracji
$wynik$ - matematyczna postać dzielenia $\frac{x}{y}$
**1. Wykonanie przesunięcia o k bitów**
Przesuwamy
$\frac{X*2^k}{B*2^k} + Q*2^k = wynik$
Nadal nierówność będzie zachodzić, bo
$\frac{X*1}{B*1} + 0*2^k = wynik$
$\frac{X}{B} + 0 = wynik$
$\frac{X}{B} + Q = wynik$
Nowe wartośći rejestrów to
$X = X*2^k$
$B = B*2^k$
$Q = Q*2^k = Q$ ,bo $Q=0$
**2.a**
$\frac{X-B}{B} + Q*2^i = wynik$
Przesunięcie rejestru (PA) w lewo nie zmienia wartości w X
Q jest teraz o 2 większe w związku z presunięciem, ale za to i się zmniejszy o 1, więc niezmiennik zostanie zachowany
$\frac{X-B}{B} + (Q*2)*2^{i-1} = wynik$
nowa wartość
$Q=Q*2$

**2.b**
Przesunięcie rejestru (PA) zachowuje niezmiennik,
natomiast odjęcie 1 do A i dodanie B od P, to
$\frac{X+B*2^{i-1}}{B} + (Q - 1)*2^{i-1} = wynik$
Działa, bo:
$\frac{X+B*2^{i-1}}{B} + Q*2^{i-1} - 1*2^{i-1} = wynik$
$\frac{X}{B}+\frac{B*2^{i-1}}{B} + Q - \frac{B*2^{i-1}}{B} = wynik$
$\frac{X}{B} + Q = wynik$

Nowe wartości rejestrów
$X = X+B$
$Q = Q-1$

**2.c**
Przesunięcie rejestru (PA) zachowuje niezmiennik,
natomiast dodanie 1 do A i odjęcie B od P, to
$\frac{X-B*2^{i-1}}{B} + (Q + 1)*2^{i-1} = wynik$
Działa, bo:
$\frac{X-B*2^{i-1}}{B} + Q*2^{i-1} + 1*2^{i-1} = wynik$
$\frac{X}{B}-\frac{B*2^{i-1}}{B} + Q + \frac{B*2^{i-1}}{B} = wynik$
$\frac{X}{B} + Q = wynik$

Nowe wartości rejestrów
$X = X-B$
$Q = Q+1$

**3.**
Niezmiennik zostaje zachowany analogicznie do 2.b
Po wykonaniu pewien stan:
$\frac{X}{B} + Q = wynik$
Teraz X to dokładnie rejestr P, a Q to dokładnie rejestr A, więc
$\frac{P}{B} + A = wynik$
Skoro przed wykonaniem tego kroku
$P \in <-B,B)$
to po wykonaniu
$P \in <0, B)$

**4.**
W tym kroku dzielimy $P$ przez $2^k$
wykonując przesunięcie o k bitów w prawo i wirtualnie dzielimy też $B$
$\frac{P}{2^k} \in <0, \frac{B}{2^k})$
$\frac{P}{2^k} \in <0, y)$
Nowa wartość rejestru $P=\frac{P}{2^k}$, więc
$P \in <0, y)$
i wirtualnie traktujemy
$B=\frac{B}{2^k}$, więc
$\frac{P}{B} + A = wynik$
$\frac{P}{y} + A = wynik$
$P \in <0, y)$, więc
A to iloraz, a P to reszta z dzielenia przez y

---

Rejestr P zawsze przechowuje taką liczbę, że gdy jest ujemny zawsze po dodaniu P otrzymamy liczbę nieujemną, co za tym idzie dodatnią resztę. Wynika to z tego, że B zostało przesunięte w lewo, tak że najbardziej znaczący dodatni bit w B jest równy jeden.

**Oraz zademonstruj działanie na wybranym przez siebie przykładzie.**
A=9₁₀
B=3₁₀
9₁₀/3₁₀
1001₂/0011₂
| P | A | B | -B | Komentarz|
| ----- | ---- | ----- | ---- | --- |
| 00000 | 1001 | 00011 | 11101 | Początkowy stan |
||||| 1. B ma 2 bity wiodące w zapisie 4-bitowym, SL(B) o 2 bity |
| 00010 | 0100 | 01100 | 10100 | |
||||| 2.a) SL(PA), nowy bit 0 |
| 00100 | 100**0** | 01100 | 10100 | |
||||| 2.c) SL(PA), nowy bit 1|
| 01001 | 00**01** | 01100 | 10100 | |
||||| 2.c) odejmowanie B od P|
| 11101 | 0001 | 01100 | 10100 | |
||||| 2.a) SL(PA), nowy bit 0|
| 11010 | 0010 | 01100 | 10100 | |
||||| 2.b) SL(PA), nowy bit $\overline{1}$|
| 10100 | $010\overline{1}$ | 01100 | 10100 | |
||||| 2.b) dodawanie B do P|
| 00000 | $010\overline{1}$ | 01100 | 10100 | |
||||| 4. Reszta ( P ) jest dodatnia wszystko wynik jest ok |
||||| 5. Bity reszty są przesunięte o 2 bity w prawo |
| 00000 | $010\overline{1}$| 01100 | 10100 | |

**Jaka motywacja stoi za wprowadzeniem tego algorytmu?**
We wcześniejszych implementacjach dzielenia nie pomijamy żadnej operacji dodawania/odejmowania, ale jeżeli iloraz zawiera jakieś bity równe zero,
to moglibyśmy odpowiadające tym bitom operacje dodawania/odejmowania pominąć.
Stąd algorytm SRT division w podstawowej wersji działa szybciej, od poprzednich