---
# System prepended metadata

title: 'Ćwiczenia 1, grupa cz. 14-16, 10. marca 2022'
tags: [SYK21, pwit, ćwiczenia]

---

# Ć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
:::

![](https://i.imgur.com/4SuQRmk.png)

![](https://i.imgur.com/Sl2EY8u.png)

![](https://i.imgur.com/dG4OP1Z.png)

### 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
:::
![](https://i.imgur.com/6wmn8WS.png)
![](https://i.imgur.com/Sg3Sy7U.png)

![](https://i.imgur.com/iRELyNz.png)
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
:::

![](https://i.imgur.com/ObXJjEy.png)

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.

![](https://i.imgur.com/88IC93G.png)


## 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.

![](https://i.imgur.com/S3vVDyq.png)

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
![](https://i.imgur.com/rRbFXBw.png)

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$
![](https://i.imgur.com/lgVePtq.png)

## Zadanie 5

:::success
Autor: Wojciech Śniady
:::
![](https://i.imgur.com/WmLXsDS.png)

![](https://i.imgur.com/sU8gSo9.png)
![](https://i.imgur.com/suwNsrC.png)



## Zadanie 6

:::success
Autor: Natalia Czerep
:::
![](https://i.imgur.com/GmpWhco.png)

![](https://i.imgur.com/UkHrlBf.png)
![](https://i.imgur.com/gF1HcpH.png)
![](https://i.imgur.com/WjrGl1b.png)

![](https://i.imgur.com/DgCYpDR.png)


Sumator rca ma w sobie sumatory pełne:
![](https://i.imgur.com/9bCAIMx.png)
i możemy dzięki temu wyliczyć 
$g= ab$ generację przeniesienia
$p=a + b$ propagację przeniesienia

![](https://i.imgur.com/IMgxKob.png)

## Zadanie 7

:::success
Autor: Rafał Starypan

![](https://i.imgur.com/imoGYiq.png)

![](https://i.imgur.com/Glf0p8B.png)

![](https://i.imgur.com/te20L9L.png)

![](https://i.imgur.com/05RUjS7.png)


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 
:::
![](https://i.imgur.com/7ezdJDx.png)
![](https://i.imgur.com/EWBcU0t.png)
