# Ć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:
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.
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:
Liczba bramek: rzędu n * log n

Sumator:

## Zadanie 2
:::success
Autor: Maria Hreniak
:::
Definicje generacji i propagacji (z wykładu):
Ogólne wzory na wyliczanie generacji i propagacji (z wykładu):

## Zadanie 3
:::success
Autor: Maciej Szałasz
:::

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

## A

## B

## Analiza czasowa

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

## Zadanie 5
:::success

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

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