# Ćwiczenia 2, grupa cz. 14-16, 17. marca 2022

###### tags: `SYK21` `ć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 |
| ----------------------:| ----- | --- | --- | --- | --- | --- | --- | --- | --- |
Kamil Banaś | | | | | | | | | |
Mateusz Burdyna | | | | | | | | | |
Dariusz Ciesielski | X | X | | X | X | | | | |
Dawid Dudek |==X== | X | X | X | X | | X | X | |
Mikołaj Dworszczak | | | | | | | | | |
Przemysław Grochal | | | | | | | | | |
Adam Jarząbek | X | X | ==x== | | x | | x | | |
Anna Karykowska | X | X | X | | | | X | | |
Oleś Kulczewicz | X | X | X | X | | | X | X | |
Pola Marciniak | X | X | X | X | X |==X==| | | |
Mikołaj Mroziuk | X | X | | X | | | X | | |
Marcelina Oset | X | X | X | X | | | X | X | |
Natalia Piasta | X | X | X | X | X | | X | ==X== | |
Krzysztof Piekarczyk | ==X== | X | X | X | X | | X | | |
Marcin Płaza | X | ==X== | X | X | X | | X | X | |
Paweł Richert | ==X== | X | X | X | X | | X | | |
Rafał Starypan | X | X | X | X | X | | X | X | |
Dawid Strojek | X | X | | | | | X | | |
Mateusz Suszek | X | X | X | | X | | X | X | |
Wojciech Śniady | X | X | X | | | | X | X | |
Volha Tsekalo | ==X== | X | X | | | | X | X | |
Yana Vashkevich | ==X== | X | X | | | | X | | |
Konrad Woźniak | X | X | X | | | | X | X | |
Natalia Czerep | | | | | | | | | |
:::

Tu można do-deklarować zad 8. z listy 1. (proszę wpisać imię i nazwisko):

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

## Zadanie 1

:::success
Autor: Yana Vashkevich
:::



A=9=1001
B=3=0011
P=0000

1) 0000 1001
2) 0011 1001
3) 0001 1100
4) 0000 1110
5) 0000 0111
6) 0011 0111
7) 0001 1011

Wynik: 0001 1011 = 27

## Zadanie 2

:::success
Autor: Marcin Płaza
:::
Zamiast shifta na P robimy shift arytmetyczny
(powielamy bit znaku)

## Zadanie 3

:::success
Autor: Adam Jarząbek
:::


W przypadku liczb n - bitowych bez znaku algorytm używający przesuwania przez zera jest następujący:

w A zapisz bity pierwszej liczby
w B zapisz bity drugiej liczby 
w P zapisz 0
powtarzaj n razy:
    1. jeżeli najmłodszy bit jest 1:
        dodaj do P liczbę B i zapisz w P
    wpp nic nie rób
    2. Wykonaj przesunięcie bitowe w prawo liczb P i A w następujący sposób:
        - bit przeniesienia z dodawania z punktu 1 staje się najstarszym bitem P
        - najmłodszy bit P staje się najstarszym bitem A
        - najmłodszy bit A przepada

wynikiem jest P A

Różnica polega na tym, że w przypadku algorytmu z zadania 1 w przypadku, gdy najmłodszy bit A jest 0 dodajemy do P 0, a tutaj w tym przypadku po prostu pomijamy krok dodawania.

**Przykład**:

P = 0000, A = 1001, B = 0011

krok 1:
lsb(A) = 1
P <- P + B = 0000 + 0011 = 0011 (c=0)
shift!
P = 0001, A = 1100

krok 2:
lsb(A) = 0 
shift!
P = 0000, A = 1110

krok 3:
lsb(A) = 0
shift!
P = 0000 A = 0111

krok 4:
lsb(A) = 1
P <- P + B = 0000 + 0011 (c = 0)
shift!
P = 0001 A = 1011

wynik = 00011011 = 1 + 2 + 8 + 16 = 27

$9 \cdot 3 = 27$. Zgadza się.

## Zadanie 4

:::success
Autor: Dariusz Ciesielski
:::
Schemat polega na zapisaniu P zainicjowanego zerami B i jednego dodatkowego bitu b=0.
Potem wykonujemy tyle kroków ile bitów maja mnożone liczby.
W każdym kroku:
1) patrzymy na ostatnie dwa bity bloku PBb.
a) Jeśli są równe 00 lub 11 nie robimy nic
b) Jeśli są równe 01 do P dodajemy A
c) Jeśli są równe 10 do P dodajemy -A
2) Przesuwamy cały blok PBb z zachowaniem znaku

Po wykonaniu ostatniego kroku usuwamy dodatkowy bit, nasze rozwiązanie jest zapisane w PB.

Idea rozumowania:
natrafienie na 10 oznacza że wchodzimy do bloku jedynek
natrafienie na 11 oznacza że trwamy w bloku jedynek
natrafienie na 01 oznacza wyjście z bloku jedynek
dlatego mnożąc np. 7 * B = 0111 * B możemy zapisać to jako (8-1) * B. Zatem wchodząc w blok jedynek odejmujemy B a wychodząc z bloku jedynek dodajemy B (ale jako że przesuneliśmy blok 3 krotnie B jest na pozycji gdzie jest warte 8-krotnie więcej czyli tak naprawdę dodajemy 8B) w efekcie dostajemy 8B - 1B = 7B

## Zadanie 5

:::success
Autor: Mateusz Suszek
:::



## Zadanie 6

::: success
Autor: Pola Marciniak
:::

Przedstaw zasadę działania układu mnożącego opartego na drzewie Wallace'a. W szczególności podaj regułę łączenia wejść sumatorów CSA danej warstwy z wejściami sumatorów następnej warstwy.

Mnożenie liczb $A=[a_{n-1}, a_{n-2},..., a_0]_2$ i $B=[b_{n-1}, b_{n-2},..., b_0]_2$ jest równoważne $n$ dodawaniom liczb postaci $C_i=A\cdot b_i\cdot 2^i$ ($0\leq i \leq n$)

W strukturze drzewa wykorzystane są sumatory trójargumentowe z pamiętaniem przeniesień (CSA - Carry Save Adder), które pozostawiają wynik dodawania w postaci dwóch słów: słowa bitów sumy i słowa bitów przeniesień. Takie sumatory działają bardzo szybko, gdyż całkowicie wyeliminowane jest w nich propagowanie przeniesień a bity słowa przeniesień są generowane bardzo szybko na podstawie jedynie trójek bitówargumentów na kolejnych pozycjach. Dopiero na końcu serii dodawań, gdzie chcemy wynik sprowadzić do postaci jednego słowa, stosowany jest sumator z przeniesieniami jednoczesnymi (CLA - Carry Look-Ahead Adder).

Drzewo ma strukturę warstwową - w każdej warstwie znajdują się sumatory CSA. W każdej warstwie sumatory przyjmują jako wejście wyjście sumatorów z poprzedniej warstwy.
Ponieważ sumator przyjmuje 3 kanały wejścia może zdarzyć się sytuacja wyjątkowa - jeśli liczba wejść nie jest podzielna przez 3, dodatkowe kanały pomijają warstwę i przechodzą do kolejnej.

Kanały wchodzą do sumatora CSA zaczynając od najmniej znaczącj trójki do bitu najbardziej znaczącego (czyli tak jak widać na schemacie do pierwszego sumatora $b_0A, b_1A, b_2A$, do drugiego $b_3A, b_4A, b_5A$ i tak dalej).

Struktura drzewa:

## Zadanie 7

:::success
Autor: Dawid Dudek
:::



## Zadanie 8

:::success
Autor: Konrad Woźniak
:::




Gdy P >= 0 algorytm działa tak samo jak z zadania 7 tylko bez IV kroku

Gdy P < 0 na końcu pętli mamy P - B, po przesunięciu w lewo mamy 2P - 2B a po dodaniu B mamy 2P - B, czyli to samo co w wersji restoring

## Zadanie 9

:::danger
Autor: do-deklarować
:::