---
# System prepended metadata

title: 'Ćwiczenia 2, grupa cz. 16-18, 7 marca 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ćwiczenia 2, grupa cz. 16-18, 7 marca 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   | 8   | 9   |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Marcin Banak             |    X  |   X  |   X  |     |     |     |     |     |     | 
Bartosz Borecki          |   X   |  X   |  ==X==   |     |  X   |     |  X   |     |  X   | 
Karol Burczyk            |   X  |   X | X   | X   | ==X==  |     |     |     |  X  | 
Yelyzaveta Ilman         |   X   | X    | X    |X     |  X   |     |    |  |     ==X==| 
Antoni Kamiński          |   X  |  X  |  X  |  X  |     |     |     |     |     | 
Jan Kamyk                |   X  |  X  |  X  |==X==|  X  |     |     |     |  X  | 
Bartosz Kruszewski       |   X  | X   | X   | X   |  X  |     |  X  |     |  X  | 
Hanna Laszkiewicz        |    X  |  ==X==   |   X  |   X  |     X|    |     |     |  X   | 
Kaja Matuszewska         |      |     |     |     |     |     |     |     |     | 
Dominik Muc              |      |     |     |     |     |     |     |     |     | 
Krzysztof Ostrowski      |  ==X==    |  X   |  X   | X    |  X   |     |     |     | X   | 
Franciszek Przeliorz     |    X  | X    |  X   |     |     |     |     |     |    X  |
Yaryna Rachkevych        |    X  |   X  |     |     |     |     |     |     |     | 
Piotr Thamm              |   X |     |     |     |   X  |     |   X  |     |     | 
Taras Tsehenko           |   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: Krzysztof Ostrowski	
:::

![image](https://hackmd.io/_uploads/rycBCRHp6.png)
Sumator liczący wynik liniowo, aby wyliczyć wynik na $_n$-tym bicie, musiał "poczekać" na ewentualne przeniesienie z $_{n-1}$-go bitu.
W tym rozwiązaniu przeniesienia liczone są równolegle i interpretowane w dalszych obliczeniach.

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

P i G są liczone według następującego wzoru:
![image](https://hackmd.io/_uploads/SkYmQeUTp.png)

ta zależnośc pozwala przyspieszyć znacząco obliczenia.

### Liczba bramek:

dla $n$ bitów:

kwadrat na początku: $2 \space bramki$
kwadrat zamalowany: $3 \space bramki$
kwadrat zaokrąglony: $2 \space bramki$

poziomów: $\log_2n$
bramek na jeden poziom: $\frac n2$

$$\Sigma =2n + 3 \cdot \frac 2n \cdot \log_2n + 2n =$$
$$ =4n + \frac {6 \cdot \log_2n}n$$

### Czas działania:

dla $n$ bitów:

bramki na "jednym poziomie" działają równoleglr

kwadrat na początku: $1$
kwadrat zamalowany: $2$
kwadrat zaokrąglony: $2$

poziomów: $\log_2n$
czas na jeden poziom: $2$ (kwadrat zamalowany)

$$\Sigma =1 + 2 \cdot \log_2n + 2 =$$
$$ = 2 \cdot \log_2n + 3$$

## Zadanie 2
:::success
Autor: Hanna Laszkiewicz	
![obraz](https://hackmd.io/_uploads/rkM-T8Pap.png)
![obraz](https://hackmd.io/_uploads/H1jk3LDp6.png)
![obraz](https://hackmd.io/_uploads/SyFxh8vTa.png)

:::

## Zadanie 3
:::success
Autor: Bartosz Borecki
![circuit](https://hackmd.io/_uploads/rywm28vTp.png)
czas: 2nlogn + 2nlogn - 1 + 2{xor} = 4nlogn + 1
:::

## Zadanie 4
:::success
Autor: Jan Kamyk	
:::
![4 tresc](https://hackmd.io/_uploads/BkX9yvwpp.png)

![zad4-2](https://hackmd.io/_uploads/rJKZ3UPap.png)
![zad4-4](https://hackmd.io/_uploads/B1Tt3LDTT.png)
![zad4-3](https://hackmd.io/_uploads/rkOBh8Dpp.png)

Niech:
n - liczba bitów
c - liczba bloków C
k - szerokość bloku C

c = n/k

Czas:
log(n/k) + log(n/k) + 3k

Rozmiar:
1. Adder - 5 bramek => 5n
2. Bloki C - 2 bramki na obliczenie małych p i g oraz 3 bramki na policzenie dużych P i G => 5n
3. Bloki B - każdy blok ma 5 bramek a jest ich około c (ponieważ c * (1/2 + 1/4 + 1/8 +...) = c) => 5c


## Zadanie 5
:::success
Autor: Karol Burczyk	
![IMG_0145](https://hackmd.io/_uploads/rJ6U3Ivpa.jpg)
![IMG_0146](https://hackmd.io/_uploads/SJADnUwap.jpg)
:::

## Zadanie 6
:::success
Autor: Taras Tsehenko	


Rozszerz układ(algorytm) mnożenia z poprzedniego zadania na liczby w kodzie uzupełnieniowym:
a) Załóż, że argument A jest liczbą bez znaku, a argument B jest liczbą w kodzie uzupełnieniowym. Czy w tym wypadku układ wymaga modyfikacji?
b) Teraz również argument A może być liczbą w kodzie uzupełnieniowym. Jakie modyfikacje w układzie(algorytmie) są konieczne?

6.a)  zasady działania układu się nie zmienają, jedyna rzecz, ktorą musimy zrobić, to zmienic przesunięcie
logiczne na przesunięcie arytmetyczne. Czyli przy przysuwaniu w prawo zamiast zer w P, ddodajemy jedynki.

6.b) 
A = a_n-1...a_0
1. if a_i = 0 and a_i-1 = 0, then add 0 to P
2. if a_i = 0 and a_i-1 = 1, then add B to P
3. if a_i = 1 and a_i-1 = 0, then substract B from P
4. if a_i = 1 and a_i-1 = 1 then add 0 to P


![aaa](https://hackmd.io/_uploads/HkrAvDv6a.png)
:::

$$A*B = (-2^{n-1}*a_{n-1} + \Sigma^{n-2}_{i=0} 2^{i}*a_{i}) * B = (-2^{n-1}*a_{n-1}) * B +  (\Sigma^{n-2}_{i=0} 2^{i}*a_{i}) * B  $$

Niech $A' = \Sigma^{n-2}_{i=0} 2^{i}*a_{i}$. Wtedy
$A*B = ((-2^{n-1}*a_{n-1}) * B) + A'*B$.

Mnożymy $A'*B$ algorytmem z punktu a) --- liczba kroków algorytmu to $n-1$. W n-tym kroku odejmujemy  od naszej sumy częśćiowej liczbę $a_{n-1}*B$.

Jak przekształcić sumator w układ odejmujący?

$C-D = C + (-D)$, zapis bitowy liczby $-D = \neg(D) + 1$ 
Czyli $C-D = C + \neg(D) + 1$.





## Zadanie 7
:::success
Autor: Bartosz Kruszewski
:::
![7.1](https://hackmd.io/_uploads/HJaDnUDT6.png)

![7.2](https://hackmd.io/_uploads/SJTwn8Dpa.png)

Działa jak układ z poprzedniej listy,\
ale dodatkowo zapamiętuje przeniesienia,\
oraz "zawraca" je do sumatora w kolejnym cyklu.

Jest to poprawne, poniewaz w kazdym cyklu\
robimy przesuniecie bitowe wyniku,\
a zapamietany bit wstawiamy na zwolnione miejsce.

Rozpoczynamy poprzez załadowanie sumy P i przeniesienia zerami.\
Wykonujemy pierwszą operację arytmetyczną.\
Przenosimy najmniej znaczący bit sumy P do A\
oraz przesuwamy rejestr A w celu zwolnienia miejsca na kolejny bit.\
Nie musimy przenosic n-1 pozostałych, ponieważ w kolejnej iteracji\
bity sumy są przeniesione do kolejnego addera.
Dodawanie działa niezależnie od siebie, ponieważ nie przenosimy\
między nimi reszty. Zwiększa to znacznie prędkość procesu.

Po wykonaniu mnożenia, P to suma i przeniesienie.\
W celu otrzymania wyniku, dodajemy je.

Dzięki zastosowaniu tego układu uzyskujemy dodawanie,
na każdym poziomie obliczania wyniku
(poza ostatnim dodawaniem wartości końcowych obu rejestrów) w czasie stałym,
przez co w rezultacie otrzymujemy możliwość mnożenia w czasie liniowym

## Zadanie 8
:::danger
Autor: do zadeklarowania na następnych ćwiczeniach
:::

## Zadanie 9
:::success
Autor: Yelyzaveta Ilman	
Najpierw piszemy algorytm:
![photo_2024-03-07_17-22-17](https://hackmd.io/_uploads/rkHq2Lvap.jpg)
Teraz mamy układ:
![photo_2024-03-07_17-23-47](https://hackmd.io/_uploads/HydNTUDTa.jpg)
I przykład (11\3 = 3 z resztą 2)
![photo_2024-03-07_17-26-19](https://hackmd.io/_uploads/SyM_pLwpa.jpg)
:::

$C/D = ??$

$D*w + r = C$ i $0<=  r < C$

Przed rozpoczęciem algorytmu mamy:

$C = M*A + Q$, gdzie $A = 0$, $Q = C$

A' <- 2A
Q' <- 2Q
A' <- 2A - M

Przypadki:

1. A' jest ujemne

A' = A' + M = 2A

Stan zmiennych:

A' = 2A
Q' = 2Q

$M*A' + Q'= M*2A + 2Q = 2C$

$C = M*A + Q$ ?

1. A' jest dodatnie

Stan zmiennych:

A' <- 2A - M
Q' = 2Q + 1

Było $C = M*A + Q$.

$M*A + Q = M*(A' + M)/2 + (Q' - 1)/2$











