# Ćwiczenia 1, grupa cz. 14-16, 10. marca 2022

###### tags: `SYK21` `ćwiczenia` `pwit`

## Deklaracje

Gotowość rozwiązania zadania należy wyrazić poprzez postawienie X w odpowiedniej kolumnie! Jeśli pożądasz zreferować dane zadanie (co najwyżej jedno!) w trakcie dyskusji oznacz je znakiem ==X== na żółtym tle.

**UWAGA: Tabelkę wolno edytować tylko wtedy, gdy jest na zielonym tle!**

:::danger
| | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Kamil Banaś | | | | | | | | | |
Mateusz Burdyna | X | |==X==| X | X | | | | X |
Dariusz Ciesielski | | | | | | | | | |
Dawid Dudek | ==X== | X | X | X | | X | X | | X |
Mikołaj Dworszczak | | | | | | | | | |
Przemysław Grochal | | | | | | | | | |
Adam Jarząbek | X | | X | | | | | | |
Anna Karykowska | X | | X | X | | | | | X |
Oleś Kulczewicz | X | | X | | | | | | |
Pola Marciniak | | | | | | | | | |
Mikołaj Mroziuk | x | x | x | x | | x | | | |
Marcelina Oset | X | | X | | | | | | |
Natalia Piasta | X | X | X | X | | | | | ==X== |
Krzysztof Piekarczyk | X | | | | | | | | |
Marcin Płaza | X | | X | X | | | | | X |
Paweł Richert | X | X | X | X | X | X | | | |
Rafał Starypan | X | X | X | X | X | X | X | | X |
Dawid Strojek | | | | | | | | | |
Mateusz Suszek | X | | X | X | | | | | X |
Wojciech Śniady | X | | X | X | X | X | | | |
Volha Tsekalo | X | | X | X | | | | | ==X== |
Konrad Woźniak | X | | X | X | X | X | | | |
Natalia Czerep | X | X | X | X | | ==X== | | | X |
:::

Paweł Richert (spóźnione): 1,2,3,4,5,6

:::info
**Uwaga:** Po rozwiązaniu zadania należy zmienić kolor nagłówka na zielony.
:::

## Zadanie 1

:::success
Autor: Dawid Dudek
:::




### Ile czasu potrzeba?

Widzimy zatem, że głębokość wynosi 2n (3n jeśli chcemy skorzystać z implementacji sumatora który ma bramki rozmiaru 2)

### Jak wykryć przepełnienie?

Wykryjemy je obserwując bit $c_n$ - jeśli będzie on zapalony to znaczy, że wystąpiło przeniesienie.

## Zadanie 2

:::success
Autor: Mikołaj Mroziuk
:::

liczby, które chcemy dodać - A, B
ciąg bitów w kodzie uzupełnień do dwóch - $a_{n-1}a_{n-2}...a_{0}$, $b_{n-1}b_{n-2}...b_{0}$
niech
$$A' = (a_{n-2}...a_0)_2$$
$$B' = (b_{n-2}...b_0)_2$$
zatem
$$A = A' - a_{n-1}2^{n-1} $$
$$B = B' - b_{n-1}2^{n-1} $$
dodajemy liczby A i B za pomocą RCA. otrzymujemy $S = s_{n-1}s_{n-2}...s_0$.
Pokażmy, że $S =(A + B )mod 2^n$

$$ S = S' - s_{n-1}2^{n-1} $$
$$ s_{n-1} = (a_{n-1} + b_{n-1} + c_{n-1} - 2c_n)$$
$$ S = A' + B' - c_{n-1}2^{n-1} - (a_{n-1} + b_{n-1} + c_{n-1} - 2c_n)*2^{n-1}$$
$$= A' + B' - a_{n-1}2^{n-1} - b_{n-1}2^{n-1} - c_{n-1}2^n + c_n2^n$$
$$= A' + B' - a_{n-1}2^{n-1} - b_{n-1}2^{n-1}$$
$$= A + B$$

Rozumowanie:

* a, b - liczby ze znakiem

* (a)_2, (b)_2 --- zapis bitowy liczb a i b

* patrzymy na zapis bitowy liczby (a)_2 +_2 (b)_2, gdzie +_2 jest operatorem dodawania pisemnego (działającego poprawnie dla liczb bez znaku)

* musimy pokazać, że to jest poprawny zapis bitowy liczby a + b

## Zadanie 3

:::success
Autor: Mateusz Burdyna
:::


W przypadku dodawania liczb bez znaku sprawdzaliśmy wartość przeniesienia w ostatnim adderze - $c_{\text{out}}$. W tym przypadku będzie podobnie, ale przepełnienie będzie dodatkowo zależeć od przeniesienia wejściowego - $c_{\text{in}}$

Będziemy oznaczać $x_k$, $y_k$ - wartości bitów znaków mnożonych liczb
Idea:

Jeśli suma dwóch liczb dodatnich daje liczbę ujemną to mamy przepełnienie ujemne ($c_\text{out}$ traktujemy jako wynikowy bit znaku).
Jeśli suma dwóch liczb dodatnich daje liczbę ujemną to mamy przepełnienie dodatnie.

| c_in | c_out| overflow |
| -------- | -------- | -------- |
| 0 | 0 | 00 |
| 1 | 1 | 00 |
| 0 | 1 | 10 |
| 1 | 0 | 01 |

Gdy $c_\text{out} = c_\text{in} = 0$ to wynikowa liczba jest dodatnia (i nie ma przeniesienia). Ale żeby $c_\text{out} = 0$ musi zachodzić albo $x_k = y_k = 0$ albo $x_k \neq y_k$, w pierwszym przypadku sumujemy dwie liczby dodatnie i nie dostajemy przepełnienia, w drugim przypadku sumujemy dwie liczby o różnych znakach, więc przepełnienia nie ma.

Gdy $c_\text{out} = c_\text{in} = 1$ to wynikowa liczba jest liczbą ujemną. Ale żeby $c_{\text{out}} = 1$ to musi zachodzić $x_k = y_k = 1$ albo $x_k \neq y_k$, czyli albo sumowaliśmy dwie liczby ujemne, albo liczby o różnych znakach, czyli przepełnienia nie ma.

Gdy $c_\text{in} = 0$ i $c_\text{out} = 1$ to liczba wynikowa jest dodatnia, ale żeby $c_\text{out} = 1$ musi zachodzić $x_k = y_k = 1$ czyli zsumowaliśmy dwie liczby ujemne i dostaliśmy liczbe dodatnia - przepełnienie.

Gdy $c_\text{in} = 1$ i $c_\text{out} = 0$ to liczba wynikowa jest ujemna oraz musi zachodzić $x_k = y_k = 0$, czyli otrzymujemy przepełnienie dodatnie.


## Zadanie 4

:::success
Autor: Anna Karykowska
:::

Na rysunku poniżej przedstawiono 19-bitowy sumator z wyborem przeniesień (ang. carry-select adder). Sumator ten składa się z siedmiu sumatorów RCA (szare bloki), multiplekserów (trójkąty) oraz bramek. Każdy sumator RCA przyjmuje, oprócz bitów do zsumowania, pewne przeniesienie wejściowe. Produkuje natomiast, oprócz bitów sumy, przeniesienie wyjściowe. Każdy z trzech par sumatorów RCA liczy swój fragment sumy, przy założeniu, że przeniesienie wejściowe jest równe odpowiednio 0 lub 1. Następnie, po ustaleniu faktycznej wartości tego przeniesienia, multipleksery wybierają odpowiednie bity do wyprowadzenia na wyjście jako bity sumy. Produkowane jest też przeniesienie dla następnej pary sumatorów RCA.


Przeanalizuj działanie tego układu i upewnij się, że dobrze je rozumiesz.

* Wylicz jego czas działania.

Na początku zauważmy, że każdy z sumatorów RCA będzie działać równolegle. Do wyliczenia ich nie potrzebujemy żadnych dodatkowych danych, później tylko wybierzemy odpowiedni wynik za pomocą multipleksera. Możemy w takim razie wziąć do wyliczenia czasu pierwszy sumator. Do wyniku musimy dodać jeszcze czas dla ostatniego multipleksera i pozostałych bramek.

multipleksery - ścieżka krytyczna: 3

Czas:
$4*2$ (pierwszy sumator) $+ 2*2$ (bramki) + $3$ (ostatni rząd multiplekserów) $= 15$
* Następnie załóż, że mamy zaprojektować n-bitowy sumator według tego schematu, przy czym wszystkie sumatory RCA mają mieć tą samą liczbę wyjść k. Jaka powinna być wartość k, by czas działania zaprojektowanego układu był możliwie najmniejszy?

$k = \sqrt{n}$
Jeżeli k byłoby większe niż wybrana wartość, to zwiększyłby się czas wyliczania sumatorów. Natomiast jeżeli byłoby mniejsze, to zwiększyłby się czas wyliczania multiplekserów i bramek.

Możemy to określić formalnie licząc ekstrema funkcji:
$f(k) = \frac{n}{k} + k + c$

## Zadanie 5

:::success
Autor: Wojciech Śniady
:::


## Zadanie 6

:::success
Autor: Natalia Czerep
:::



Sumator rca ma w sobie sumatory pełne:
i możemy dzięki temu wyliczyć
$g= ab$ generację przeniesienia
$p=a + b$ propagację przeniesienia


## Zadanie 7

:::success
Autor: Rafał Starypan





Na początku wykonujemy preprocessing, w którym dla każdego spójnego
przedziału bitów o długości będącej potęgą dwójki obliczamy wartości
propagacji i generacji. Sygnał jest propagowany w dół, wyliczane są kolejne
wartości Pij, Gij dla coraz większych przedziałów niżej w drzewie.

P(i, k) = P(i, j) AND P(j+1, k)
G(i, k) = G(j+1, k) OR (P(j+1, k) AND G(i, j))

Czas działania
w czasie 1 obliczone w każdej bramce A wartości generacji oraz propagacji pojedynczej pozycji (trywialnie -> generacja AND, propagacja XOR)

Następnie w czasie 2 obliczone w każdej bramce typu B liczone jest G i P
1+(log(n))*2 na bazie ilości poziomów drzewa (z własności drzew binarnych)

następnie obliczane carry-out
dla bramki B w czasie 2 (zgodnie ze schematem bloczku B)

mamy teraz łącznie
1+(log(n))*2+log(n)*2
i jeszcze jeden dla obliczenia s(i)
1+(log(n))*2+log(n)*2+1

Liczba bramek:
n*4+(n-1)*5=9n-5

Wyjaśnienie: Mamy n bloczków typu A (każdy po 4 bramki) oraz (n-1)
bloczków typu B (każdy po 5 bramek). Podsumowując wynik wychodzi jak wyżej.

:::

## Zadanie 8

:::danger
Autor: do-deklarować
:::

## Zadanie 9

:::success
Autor: Volha Tsekalo
:::