# Ćwiczenia 1, grupa śr. 17-19, 9. 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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Grzegorz Bielecki | | | | | | | | | |
Kamila Brzozowska | X | X | X | X | | X | X | | X |
Adam Ciężkowski | X | X | X | X | X | | | | X |
Natalia Czerep | | | | | | | | | |
Jan Dalecki | x | | x | x | x | x | x | | x |
Marko Golovko | X | X | X | X | X | | X | | |
Adam Górkiewicz | X | X | X | X | X | X | X | X | X |
Piotr Gunia | ==X== | | X | X | X | X | | | X |
Krzysztof Jadłowski | X | X | X | ==X== | X | X | X | | X |
Magdalena Jarecka | X | | | | | | | | X |
Mikołaj Jaszcza | X | X | X | X | X | X | X | X | X |
Monika Jędrzejkowska | X | | X | | | | | | X |
Michał Kierul | X | X | X | X | X | | X | X | X |
Damian Lukas | | | | | | | | | |
Karol Ochman-Milarski | | | | | | | | | |
Piotr Piesiak | | | | | | | | | |
Damian Ratajski | | | | | | | | | |
Aleksandra Rozkrut | X | | | | | X | | | |
Marcin Sarnecki | X | X | X | X | X | X | X | X | X |
Maria Szlasa | X | X | X | X | X | X | X | | |
Yana Vashkevich | X | X | | | | | | | |
Nikola Wrona | X | | X | | | | | | X |
Marcin Wróbel | X | X | ==X== | X | X | X | X | X | X |
:::

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

## Zadanie 1

:::success
Autor: Piotr Gunia
:::



Ścieżka krytyczna: 2

Ścieżka krytyczna: 3

### Zakładając, że każda bramka działa w czasie jednostkowym, jaki jest czas działania tego sumatora (tzn. ile jednostek czasu potrzeba by na wyjściach sumatora pojawił się poprawny wynik dodawania)?

Ścieżka krytyczna: 2*n, (3*n)

### W jaki sposób wykryć, że wynik sumowania nie mieści się w n bitach (przepełnienie)?
$C_{out} = 1$

## Zadanie 2

:::success
Autor: Marko Golovko
:::

:::spoiler Pierwsza wersja rozwiązania zadania
* Dla liczb, które nie zmieniają znaku działa tak samo
* Jeżeli jedna liczba jest ujemna: a dodatnia, b ujemna
* abs(a) > abs(b): musi musi nastąpić zmiana znaku
$abs(b)=\bar{b}+1$
$\bar{b}+b+1$ wystąpenie nadmiary
$\bar{b}+b+1\leq a+b$
$\bar{b}+1\leq a$
$a > b$
* abs(a) = abs(b): liczba musi wyzerować się
W tym przypadku jest to najmniejsza możliwa wartość a do występowania nadmiaru
$\bar{b}+b+1 = a+b$
$\bar{b}+1 = a$
$abs(a) = abs(b)$

-1 + 1 = ?

(111) + (001) = (000) i przeniesienie 1 z najstarszego bitu

Co się stało w tym przykładzie:
* wzięliśmy dwie liczby, policzyliśmy ich reprezentację w kodzie uzupełnień do dwóch
* dodaliśmy te reprezentacje sumatorem traktując je jako liczby bez znaku
* wynik sumowania potraktowaliśmy jako liczbę ze znakiem i stwierdziliśmy, że jest to poprawny wynik sumowania liczb ze znakiem.

(a)_n + (-a)_n = (0)_n, ale tak naprawdę to powinno być 2^n

* abs(a) < abs(b): odwrotnie do perwszego, nadmiar nie wystepuje
:::

:::spoiler Poprawione zadanie
Sumator sumuje liczby traktując je jako liczby bez znaku. Zakładając, że nie będziemy mieć przepełnień, wyjdzie u nas summa dla liczby ze znakiem.
Pokażemy na przykładzie dwóch liczb, a i b
Niech $a'$ bedzie liczba $a$ bez wiodącego bitu
Niech $b'$ bedzie liczba $b$ bez wiodącego bitu
* Dla liczb dodatnich korzystając z założenia, wiemy, że suma zmieści się na n-1 bitach, n-ty bit jak i było oczekiwane będzie 0.
* Dla liczb ujemnych z założenia wiemy, że traktując ja jako liczby bez znaku długości n-1, $a' + b' > 2^{n-1}$, wieć n-ty bit będzie równy 1 (sumator zrobimy przeniesienie na n-ty bit)
$a = 2^{n-1}+a'$
$b = 2^{n-1}+b'$
i $a+b = 2^n+a'+b'$
I widzimy, że sumując, a i b sumator zrobi przeniesienie na n+1 bit i z rozumowania powyżej widzimy, że n-ty bit też będzie jeden
* Jeżeli jedna liczba ujemna a druga dodatnia. Niech a będzie dodatnia i b ujemna
$a' = a$
$b = b' - 2^{n-1}$
Dodając $a'$ i $b'$ jeżeli otrzymujemy przeniesienie, wtedy otrzymamy liczbę dodatnią, bo n bit jest ustawiony na jedynkę przez liczbę b
Jeżeli wystąpiło przeniesienie, przy dodawaniu sumatora to znaczy, że $a' + b' > 2^{n-1}$ i przez to że bit n-ty był jedynką to po przeniesieniu zerujemy go i wychodzi liczba równa $a' + b'- 2^{n-1}$ co i oczekiwaliśmy
$a + b = a' + b' - 2^{n-1}$
Jeżeli nie otrzymamy przeniesienia to wyjdzie jak i oczekiwaliśmy liczbę ujemną, bo n-ty bit zostanie jedynka i $a'+b' < 2^{n-1}$
:::


## Zadanie 3

:::success
Autor: Michał Kierul

$sa,sb,sw$ - wartości najstarszych bitów w składnikach oraz sumie

| $out$| $sa$| $sb$| $sw$|
|------|-----|-----|-----|
| 00 | 1 | 1 | 1 |
| 10 | 1 | 1 | 0 |
| 00 | 0 | 1 | 1 |
| 00 | 1 | 0 | 1 |
| 00 | 0 | 1 | 0 |
| 00 | 1 | 0 | 0 |
| 00 | 0 | 0 | 0 |
| 01 | 0 | 0 | 1 |

:::

Alternatywna wersja:

Overflow (underflow) wystąpi kiedy bity przeniesienia dwóch ostatnich sumatorów są różne $c_{n} \neq c_{n-1}$


## Zadanie 4

:::success
Autor: Krzysztof Jadłowski
:::

Mamy 19 bitowy sumator, 7 sumatorów RCA oraz multipleksery. Zauważmy że każdy z sumatorów może działać równolegle (do wyliczenia odpowiednich outputów nie potrzebujemy znać C_in ponieważ liczymy oba możliwe przypadki jego wartości). Jako że RCA działają równolegle a później już tylko za pomocą odpowiednich bramek i multiplekserów(do wyboru wariantu RCA z C_in =0 albo C_in = 1) możemy wyliczyć ostateczny wynik czas działania możemy oszacować jako:
maksymalny czas działania RCA + czas działania multiplekserów+ czas działania bramek. Wyliczmy teraz wartość k z treści zadania
Przyjmijmy teraz że każdy blok będzie miał ten sam rozmiar. Załóżmy że każdy blok ma długość k oraz mamy d poziomów(na każdym mamy 2 równoległe bloki), mamy $n\approx k*d$, zauważmy że gdy $k> \sqrt{n}$ wtedy etap przejścia równoległego staje się droższy od pierwiastka w przeciwnym przypadku etap przejścia sekwencyjnego. ostateczny czas działania też jest pierwiastkowy

## Zadanie 5

:::success
Autor: Adam Ciężkowski
:::


a) Wylicz jego czas działania:

Czas działania: 4 (pierwszy sumator) + 3 * 2 (ścieżka między sumatorami) + 4 (ostatni sumator)
Koszt full adder = 1 (założenie)

b) Następnie załóż, że mamy zaprojektować $n$-bitowy sumator według tego schematu, przyczym 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?

Liczba sumatorów RCA: $\frac{n}{k}$
Najdłuższa ścieżka: $O(n)$
ALE przechodzimy przez tylko pierwszy i ostatni sumator, resztę ścieżkami "dolnymi", korekcja dzieje się podczas przechodzenia przez ostatni sumator. Koszt wynosi: $k + (\frac{n}{k} - 2) * 2 + k$, czyli $O(k + \frac{n}{k})$
By zminimalizować tę wartość, $k$ powinno być równe $\sqrt{n}$.

## Zadanie 6

:::success
Autor: Kamila Brzozowska
:::
Opracuj sumator złożony z bloków (podobnie jak w poprzednim zadaniu), w którym każdy blok jest sumatorem RCA z dodatkowym układem obliczającym przeniesienie z tego bloku. Ten dodatkowy układ może korzystać jedynie z przeniesienia wejściowego danego bloku oraz bitów argumentów do zsumowania w danym bloku. Ideę tego układu oprzyj na liczeniu propagacji przeniesienia i generowania przeniesienia przez dany blok. Będzie to tzw. blokowy sumator z przeniesieniem równoległym (ang. carry-lookahead adder, CLA). Narysuj swój n-bitowy sumator dla n=16 i rozmiaru bloku k=4.

|a|b|$c_{in}$|$c_{out}$|
|-|-|--------|---------|
|0|0| 0 | 0 |
|0|0| 1 | 0 |
|0|1| 0 | 0 |
|0|1| 1 | 1 |
|1|0| 0 | 0 |
|1|0| 1 | 1 |
|1|1| 0 | 1 |
|1|1| 1 | 1 |

$c_{out}= ab+ (a\oplus b)c_{in}$
$g= ab$ generacja przeniesienia
$p=(a\oplus b)$ propagacja przeniesienia (bo zależy od poprzedniego przeniesienia)

$c_{1}= g_0+ p_0 c_{0}$
$c_{2}= g_1+ p_1 c_{1}= g_1+ p_1(g_0+ p_0 c_{in}) = g_1 + p_1g_0 +p_1p_0c_{in}$
$c_{3}= g_2+ p_2 c_{2}= g_2+ p_2(g_1 + p_1g_0 +p_1p_0c_{in})=g_2+ p_2g_1 + p_2p_1g_0 + p_2p_1p_0c_{in}$
$c_{4}= g_3+ p_3c_{3}= g_3+ p_3 (g_2+ p_2g_1 + p_2p_1g_0 + p_2p_1p_0c_{in})=g_3+ p_3g_2+ p_3p_2g_1 + p_3p_2p_1g_0 + p_3p_2p_1p_0c_{in}$


Sumator RCA składa się z sumatorów pełnych
W każdym sumatorze pełnym liczymy generację przeniesienia i propagację przeniesienia ($ab$ oraz $a\oplus b$).


## Zadanie 7

:::success
Autor: Jan Dalecki
:::




Czas obliczenia przeniesienia dla ostatnich bitów $a$ i $b$ wymaga najdłuższego oczekiwania. Sygnał musi przejść do spodu drzewa. Pokonujemy w ten sposób $log(n)$ bloków z których każdy wykonuje się w pewnym stałym czasie $O(1)$. Zatem czas działania układu to $log(n)$.

## Zadanie 8

:::success
Autor: Mikołaj Jaszcza
:::
Białe bloki na górze reprezentują sumatory 1 bitowe (tworzą razem sumator RCA), które także obliczają propagację dla każdego bitu.
Blok C oblicza propagację dla danego przedziału bitów, i przekazuje dalej generację przez cały przedział bitów obliczoną przez sumator.

Propagacja przedziału jest iloczem (AND - tj. p0 AND p1 AND p2 AND p3) propagacji pojedynczych pozycji. Natomiast generacja w trywialny sposób jest równoważna z wartością carry-out sumatora RCA przy carryin=0 (zauważmy, że jej wartość jest znana już po 2k+1 jednostkach czasu, niezależnie od "wejściowych" c0, gdzie k to liczba bitów w bloczku RCA).

Sygnał jest propagowany w "dół" drzewa (zgodnie ze schematem u góry)
poprawne są kolejne wartości Pij, Gij
dla coraz większych przedziałów (niżej w drzewie), wyznaczone dzięki wzorom
=> P(i, k) = P(i, j) * P(j+1,k)
=> G(i, k) = (Gj+1, k)+ (Pj+1, k) * G(i, j).

Następnie mając poprawne powyższe wartości
obliczane są wartości carry-out "ck" (chodzi tu o działania mające miejsce w "bloczku" B) bloczku przy otrzymanym carry in (indeksy poniżej na bazie indeksów bloczku B)
c(k + 1) = G(i,k) + P(i,k)c(i). Więc następnie każdy sumator poprawnie oblicza odpowiednie bity sumy.

n=b*k
k-rozmiar bloku
b-liczba bloków

Pełny sumator jednobitowy ma 5 bramek, więc cały sumator k-bitowy będzie miał 5k bramek (i będzie działał w czasie 2k+1).

Schemat bloczku B:

CZAS DZIAŁANIA:
(2k+1)+(2*log(b))+(2*log(b))+(2k+1) - 2

2k+1 sumatory rca na początku
2*log(b) przejście drzewa w dół
2*log(b) przejście drzewa w góre
2k+1 sumator rca na końcu
-2 -> ponieważ w korzeniu drzewa nie ma potrzeby wyznaczania generacji oraz propagacji (o ile nie sprawdzamy potencjalnego overflow)

obliczenie liczby bramek w przedstawionym rozwiązaniu (z podziałem na czynniki):
5*n -> sumatory pełne 1 bitowe (po 5 bramek, n bitów)
n -> liczenie propagacji dla każdego pojedynczego bitu, każdy z nich musi przekazać odpowiednią wartość do bloku C aby wyliczyć propagację całego bloczku - łącznie jest ich n
b -> skoro jest b bloczków typu C, a każdy blok ma po jednym "wielkim" AND (tj obliczanie propagacji)
5*(b-1) - każdy blok typu B ma 5 bramek (patrz. schemat wklejony powyżej), a bloczków typu B jest b-1 (własności bitowe).

Zatem podsumowując -> 5*n+n+b+5*(b-1)

## Zadanie 9

:::success
Autor: Marcin Wróbel
:::
Same mnożenie 4bit * 1bit