# Ćwiczenia 1, grupa cz. 10-12, 29 luty 2024

###### tags: `SYK24` `ć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 |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- |
Borys Adamiak | X | X | X | ==X== | | | X |
Michał Chawar | X | | X | X | X | X | X |
Julia Cygan | X | | X | X | | | X |
Maciej Dengusiak | X | X | X | X | | | X |
Patryk Flama | X | X | X | X | | | X |
Szymon Fluder | X | | X | X | | X | X |
Aleksandra Jędrzejak | X | | X | X | | | |
Mikołaj Karapka | X | | X | X | | | X |
Viktoriia Kashpruk | X | X | X | X | X | | ==X== |
Wiktor Małek | X | | X | X | | X | X |
Błażej Molik | X | X | X | X | | | X |
Andrzej Morawski | | | | | | | |
Konrad Oleksy | | | | | | | |
Lucjan Pucelak | X | | X | X | | | X |
Aleksandra Sęk | X | | | | | | X |
Radosław Śliwiński | X | X | ==X== | X | | | X |
Piotr Traczyński | X | X | X | X | | | X |
Katarzyna Trzos | ==X== | | X | X | | | X |
Piotr Warząchowski | | | | | | | |
Olga Zaborska | X | X | X | X | | | X |
:::

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

## Zadanie 1
:::success

Autor: Katarzyna Trzos
:::

## Zadanie 2
:::success
Autor: Maciej Dengusiak
:::
n-bitowy sumator $\Leftrightarrow$ możemy dodawać n-bitowe liczby
z systemu zapisu U2 wiemy że
$$A = \sum_{k=0}^{n-2}a_{k}2^k - a_{n-1}2^{n-1} = A' - a_{n-1}2^{n-1}$$
teraz sumujemy A z B, S' to wartość sumy, ignorując jej znak $\Leftrightarrow$ suma A' z B' bez przepełnienia (:exclamation: $cout_{k}$ to przepełnienie wychodzące z k-1 i wchodzące do k)
$$S'=A'+B'-cout_{n-1}2^{n-1}$$$$cout_{n} = \lfloor ( a_{n-1}+b_{n-1}+cout_{n-1} )/2 \rfloor$$

z definicji operacji dodawania liczymy $s_{n-1}$:
$$a_{n-1}+b_{n-1}+cout_{n-1}$$
ale generuje to przepełnienie, którego się pozbywamy przenosząc wartość 2 do kolejnej komórki (która już nie istnieje, ale to nie prolem przy modulo $2^n$)
$$s_{n-1} = a_{n-1}+b_{n-1}+cout_{n-1} - 2cout_n$$
więc na koniec otrzymujemy
$$S = S' - s_{n-1}2^{n-1} =$$$$A'+B'-cout_{n-1}2^{n-1} - (a_{n-1}+b_{n-1}+cout_{n-1} - 2cout_n) 2^{n-1}$$$$=A+B - 2cout_n2^{n-1} \equiv_{2^n} A+B$$
czyli nasza operacja dodawania poprawnie dodaje liczby w systemie U2
:::

## Zadanie 3
:::success
Autor: Radosław Śliwiński
:::


Rozwiązanie opiera się na obserwacji, że przy dodawaniu w systemie U2 przepełnienie następuje, gdy na ostatnim dodawanym bicie Carry_in jest różne od Carry_out.

## Zadanie 4
:::success
Autor: Borys Adamiak
:::

a) 4 na pierwszy sumator + 2 na pierwsze bramki + 2 na kolejne bramki + 1 multipleksery = 9
b)
k - liczba wyjsc n
i - liczba sumatorow RCA
$$n=k*i => i = \frac{n}{k}$$
szukamy minimum z k+i
$$f(k)=k+\frac{n}{k}$$ $$\frac{d}{dk}f(k)=1-\frac{n}{k^2}$$ $$\frac{df(k)}{dk}=0\iff1=\frac{n}{k^2}$$ $$k=\sqrt{n}$$

## Zadanie 5
:::success
Autor: Michał Chawar
:::


Zakładamy, że $n|k$. $T_{FA}$ to czas działania pełnego sumatora (których jest $k$ w $k$-bitowym *RCA*), $T_{P}$ to czas wyliczenia propagacji z sumatora.

Mamy $\frac{n}{k}$ sumatorów *RCA* po $k$ wyjść. Pierwszy i ostatni obliczą się po standardowych czasach - $kT_{FA}$. Dalej, wszystkie środkowe zostaną pominięte (w górnym sygnale bramki OR jest informacja, czy blok generuje przesunięcie $c_i$, policzona po $kT_{FA}$ - zaczyna się liczyć w $t=0$ przy $c_{i-4} = 0$, a gdy istnieje, to będzie istnieć i gdy $c_{i-4} = 0$) i będą się wyliczać w tle, podczas gdy my pójdziemy dalej - każdy z $\frac{n}{k}-2$ sumatorów pomijamy w czasie $2$.

Stąd mamy
$t(k)=2kT_{FA} + T_{P} + 2(\frac{n}{k}-2)$

Przy $T_{FA}=1$ i $T_{P}=c$
$t(k)=2k + c + 2nk^{-1}-4$ i analogicznie do `zad. 4` wychodzi $k=\sqrt{n}$

*Dodatkowe spostrzeżenie:*
Jeśli na początku i na końcu weźmiemy mało bitów, a do środkowych *RCA* wepchniemy pozostałe, to pierwsze i ostatnie *RCA* obliczą się szybciej, a w najlepszym wypadku środkowe i tak zostaną pominięte i spadnie $t$.

## Zadanie 6
:::success
Autor: Wiktor Małek
:::

Korzystając z `appendix j str.37`

$G_i=A_iB_i$
$P_i=A_i+B_i$



narysowany tylko jeden blok bo więcej się nie zmieściło - podłączamy $c_{out}$ danego bloku jako $c_{in}$ następnego bloku za wyjątkiem pierwszego i ostatniego bloku. Pierwszy blok przyjmuje $c_0$, a ostatni blok zwraca $C_{out}$ (całej sumy, całego sumatora 16-bitowego)

## Zadanie 7
:::success
Autor: Viktoriia Kashpruk
:::


Stosując analogię do mnożenia pisemnego, chcemy pomnożyć 2 liczby binarne 4-bitowe **a** i **b**. Żeby to osiągnąć wystarczy pomnożyć **a** przez każdy bit b.
**Przemnożenie przez bity b** jest równoważne z zastosowaniem bramki *and* na każdym bicie z a.
Póżniej za pomocą sumatorów dodajemy wyniki przesunięte w lewo.