---
# System prepended metadata

title: 'Ćwiczenia 1, grupa śr. 17-19, 9. marca 2022'
tags: [SYK21, pwit, ćwiczenia]

---

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

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

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

![](https://i.imgur.com/dhceOba.png)
Ścieżka krytyczna: 2


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

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

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

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

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

Alternatywna wersja:

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

![](https://i.imgur.com/xWmFuBu.jpg)


## Zadanie 4

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

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

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

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}$

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

Sumator RCA składa się z sumatorów pełnych
![](https://i.imgur.com/9bCAIMx.png)
W każdym sumatorze pełnym liczymy generację przeniesienia i propagację przeniesienia ($ab$ oraz $a\oplus b$).

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

## Zadanie 7

:::success
Autor: Jan Dalecki
:::

![](https://i.imgur.com/mkAOlZA.jpg)

![](https://i.imgur.com/XwquMTJ.jpg)

![](https://i.imgur.com/Qke4DJy.jpg)

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

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
:::
![](https://i.imgur.com/guUx11L.png)
Same mnożenie 4bit * 1bit
![](https://i.imgur.com/veT0Bc1.png)


