---
# System prepended metadata

title: 'Ćwiczenia 1, grupa cz. 10-12, 29 luty 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ć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	
:::
![IMG_0278](https://hackmd.io/_uploads/BkNUZ0ah6.jpg)







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

![z3](https://hackmd.io/_uploads/SkFBhJR3a.png)


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
:::
![image](https://hackmd.io/_uploads/SJ3rc233T.png)
![image](https://hackmd.io/_uploads/rklD92nna.png)

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

![obraz_2024-02-29_120022283](https://hackmd.io/_uploads/rypaXyC2a.png)


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$

![zad_6_zalacznik](https://hackmd.io/_uploads/BkG32p6na.png)

![zad_6](https://hackmd.io/_uploads/B1ohh6Th6.png)



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	
:::
![image](https://hackmd.io/_uploads/Bky1p663p.png)

![image](https://hackmd.io/_uploads/S1nNSRa3T.png)


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.

