---
# System prepended metadata

title: 'Ćwiczenia 2, grupa śr. 12-14, 6 marca 2024'
tags: [pwit, ćwiczenia, SYK24]

---

# Ćwiczenia 2, grupa śr. 12-14, 6 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   |
| ----------------------:| -----| --- | --- | --- | --- | --- | --- | --- | --- |
Mikołaj Balwicki         |      |     |     |     |     |     |     |     |     | 
Małgorzata Galińska      |   ==X==   |   X  |  X   |     |   X  |     |     |     |  X   |
Maria Hreniak            |  X    | ==X==    |  X   |     |  X   |     |     |     |  X   |
Jakub Jankowski          |  X    | X    |  X   |     | X    |     | X    |     |  X   |
Mikołaj Kalitka          |    X  |  X   |  X   |     |  X   |     |     |     |  X   |
Julia Konefał            |   X   | X    |  X   |     |  X   |     |     |     |     |
Julia Kulczycka          |   X  |  X  |  X  |     |  X  |     |     |     |  X  |
Cecylia Łyjak            |  X    |  X   |     |     |     |     |     |     |     |
Adam Majchrowski         |  X    |  X   |  X   | ==X==    |     |     |     |     |  X   |
Piotr Mańkowski          |      |     |     |     |     |     |     |     |     |
Piotr Salamon            |      |     |     |     | ==X==    |     |     |     |   X  |
Maciej Szałasz           |   X   |  X   |  ==X==   |     |  X   |     |     |     |   X  |
:::

Tutaj można zadeklarować zaległe **zadanie 6 z listy 1**:

:::danger
| Imię i nazwisko        | 1.6  |
| ----------------------:| -----|
                         |      | 
                         |      | 
:::



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



## Zadanie 1
:::success
Autor: Małgorzata Galińska	
:::
Sumator prefiksowy, to układ służący do szybkiego i efektywnego dodawania wielu bitów. Zasada jego działania opiera się na wykorzystaniu dwóch operacji logicznych: 
•	generacji przeniesienia – na podstawie bitu a_i i b_i określamy, czy wygenerujemy przeniesienie w dodawaniu i-tego bitu (niezależne od przeniesienia wejściowego). Generujemy przeniesienie tylko, gdy a_i = b_i = 1, więc g_i = AND(a_i, b_i).
•	propagacji przeniesienia – sprawdza, czy w przy dodawaniu i-tego bitu przeniesienie c_in zostanie przeniesione do kolejnego dodawania i+1-szego bitu (zależne od przeniesienia wejściowego). Propagujemy przeniesienie, gdy a_i = 1 lub b_i = 1, więc p_i = OR(a_i, b_i).
Wtedy c_out = g_i + p_i * c_in
Zauważmy, że możemy to uogólnić na bloki:
![ZAD1](https://hackmd.io/_uploads/SJpCWCr6T.png)
Czyli uogólniając dla dowolnej liczby bloków: c_out = 1, jeśli c_in = 1 i zostało przeniesione przez wszystkie bloki lub zostało wygenerowane ostatnie lub zostało wygenerowane przedostatnie i przeniesione przez ostatni blok lub zostało wygenerowanie przed-przedostatnie i przeniesione przez 2 ostatnie bloki lub … lub wygenerowane przez pierwszy i przeniesione przez wszystkie bloki.
![ZAD1_2](https://hackmd.io/_uploads/B1deGArpT.png)
Pomysł: mając wzór ogólny dla bloków możemy tworzyć mniejsze bloki w blokach: najpierw wyliczymy pojedyncze wartości p_i, g_i, c_i, następnie połączymy je w bloki 2-elementowe, następnie te bloki 2-elementowe połączymy w 4-elementowe itd… Dzięki temu przyspieszymy proces dodawania, będziemy liczyć log n generacji i propagacji. Czas działania:
![ZAD1_3](https://hackmd.io/_uploads/BJtGM0rTa.png)
Liczba bramek: rzędu n * log n

Sumator:
![ZAD1_4](https://hackmd.io/_uploads/BJt4GRSTT.png)


## Zadanie 2
:::success
Autor: Maria Hreniak	
:::
![2a](https://hackmd.io/_uploads/HJs2ZCSTa.png)
Definicje generacji i propagacji (z wykładu):
![image](https://hackmd.io/_uploads/r1SSMRraa.png)
Ogólne wzory na wyliczanie generacji i propagacji (z wykładu):
![image](https://hackmd.io/_uploads/rkxOMCrpp.png)
![2b](https://hackmd.io/_uploads/BJmpWABT6.png)
![image](https://hackmd.io/_uploads/H12G5CrT6.png)
![2d](https://hackmd.io/_uploads/r1XAbRBpa.png)



## Zadanie 3
:::success
Autor: Maciej Szałasz
:::
![image](https://hackmd.io/_uploads/rkiVcjSpT.png)


Sumator był już w materiałach, więc zaprojektujemy tylko bloki A i B:


## A
![image](https://hackmd.io/_uploads/rkTaTcVpa.png)

## B
![image](https://hackmd.io/_uploads/SkvCacETa.png)


## Analiza czasowa
![image](https://hackmd.io/_uploads/B1VCtoEp6.png)

Zakładamy że C_0 jest wczytywane wszędzie od razu (brak bramki/bramka buforowa). Przy takim założeniu zaczynamy obliczenia od prawej strony rysunku i idziemy w lewy dolny róg w czasie **2logn - 1**. Następnie liczymy czas idąc w lewy górny róg, bo sumowanie ostatniego bitu wykona się najpóźniej. Schodzimy więc o **2logn** poziomów i dodajemy 2 jako czas wyliczenia wartości Sn-1.
Stąd łączny czas to **4logn + 1**

## Rozmiar
**4n + 6logn**

## Zadanie 4
:::success
Autor: Adam Majchrowski
![image](https://hackmd.io/_uploads/rJTSzRrpa.png)
![image](https://hackmd.io/_uploads/Hk9PG0Sp6.png)
:::

## Zadanie 5
:::success
![image](https://hackmd.io/_uploads/BkjkfAHaa.png)

Autor: Piotr Salamon	
Algorytm:
P <- n-bitowa tablica samych 0
A <- n-bitowa tablica zawierająca liczbę A
B <- n-bitowa tablica zawierająca liczbę B
C <- [0] (jednobitowa tablica do przechowywania przeniesienia)
K <- pomocnicza tablica o n+1 bitach, początkowo same 0

n razy wykonaj:
  jeżeli A[0] == 1:
  K <- B + P (binarne dodawanie)
  C <- K[n+1] (jeżeli na n+1 miejcu była 1 to nastąpiło przeniesienie)
  P <- K[n:] (kopiuję bity od n do 0)
  A >> 1
  A[n] = P[0]
  P >> 1
  P[n] = C[0]
  C >> 1
Wypisz P, Wypisz A

Przykład dla A = 9 [1001] oraz B = 3 [0011]

Iteracja 1:
  Wchodzimy do if'a:
  K = [00011]
  C = [0]
  P = [0011]
A = [1100]
P = [0001]
C = [0]

Iteracja 2:
Nie wchodzimy do if'a bo A[0] == 0

A = [1110]
P = [0000]
C = [0]

Iteracja 3:
Nie wchodzimy do if'a bo A[0] == 0

A = [0111]
P = [0000]
C = [0]

Iteracja 4:
  Wchodzimy do if'a:
  K = [00011]
  C = [0]
  P = [0011]
A = [1011]
P = [0001]
C = [0]

Wynik - [00011011] = 1 + 2 + 8 + 16 = 27 (zgadza się :heart:)
:::

## Zadanie 6
:::danger
Autor: do zadeklarowania na nastęþnych ćwiczeniach
:::


$$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$. **i przesunąc w prawo o 1 bit (tak samo jak w poprzednich n-1 krokach)**

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: Jakub Jankowski
Układ ten jest równoważny nast. algorytmowi
![image](https://hackmd.io/_uploads/ByyJNCrp6.png)


gdzie P_s[n+1] jest dodany ze stałą wartością =0 tylko ze względu na wygodę pisania algorytmu.


:::

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

## Zadanie 9
:::success
Autor: Mikołaj Kalitka
#### Kroki działania
Zaczynamy z parą registrów (P[n]=[0..0], A) oraz registrem B podobnie, jak poprzednio. Następnie wykonujemy w pętli kroki n razy:

1.  Przesuwamy parę registrów (P, A) o jeden bit w lewo.
2.  "Próbujemy" od P odjąć B (tzn. wykonujemy odejmowanie obarczone ryzykiem, że wyjdzie liczba ujemna)
3.  Jeżeli wynik wyszedł ujemny, ustawiamy bit a0 na 0, w przeciwnym wypadku - na 1.
4.  Jeżeli wynik wyszedł nieujemny, to zostaje on nową wartością P.

**Wynik**: A - wynik dzielenia, P - reszta z dzielenia.

**Przykład:**
![430423703_387112230737551_2869404298433788752_n](https://hackmd.io/_uploads/rk4hBABpa.jpg)
:::
