---
# System prepended metadata

title: Ćwiczenia 2
tags: [Sieci Komputerowe]

---

###### tags: `Sieci Komputerowe`

# Ćwiczenia 2

## Zadanie 1
:::info
W kablu koncentrycznym używanym w standardowym $10$-Mbitowym Ethernecie (Można założyć, że $10\space Mbit = 10^7\space bit$) sygnał rozchodzi się z prędkością $10^8\space m/s$. Standard ustala, że maksymalna odległość między dwoma komputerami może wynosić co najwyżej $2,5 km$. Oblicz, jaka jest minimalna długość ramki.(Wraz z nagłówkami, w rzeczywistości sygnał rozchodzi się ok. $2$ razy szybciej, ale opóźnienia występują nie tylko w kablu.).
:::

Wiemy, że:
1. Czas transmisji pakietu $T_t\geq 2T_p$, gdzie $T_p$ jest czasem propagacji
2. Czas transmisji wyraża się wzorem $T_t=\frac LR$ Gdzie $L$ jest rozmiarem pakietu, a $R$ przepustowością łącza
3. $T_p=\frac sv$ gdzie $s$ to odległość między dwoma komputerami, a $v$ prędkością sygnału

Po podstawieniach:

$\frac LR \geq \frac{2s}{v}$ / $*R$
$L \geq \frac{2sR}{v}=\frac{2*2500m*10^7\space bit/s}{10^8\space m/s}=\frac{5000*10^7}{10^8}\space bit=\frac{500*10^8\space bit}{10^8}\space bit=500\space bit$

Czyli minimalna długość ramki wraz z nagłówkami wynosi $500$ bitów.

## Zadanie 2 X
:::info
Rozważmy rundowy protokół Aloha we współdzielonym kanale, tj. w każdej rundzie każdy z n uczestników usiłuje wysłać ramkę z prawdopodobieństwem $p$. Jakie jest prawdopodobieństwo $P(p, n)$, że jednej stacji uda się nadać (tj. że nie wystąpi kolizja)? Pokaż, że $P(p, n)$ jest maksymalizowane dla $p = 1/n$. Ile wynosi $\displaystyle\lim_{n→∞} P(1/n, n)$?
:::

## Zadanie 3 X
:::info
Wyszukaj w sieci informację na temat zjawiska Ethernet capture i wytłumacz w jaki sposób ono powstaje. (Tym mianem określa się sytuację, w której jedna ze stacji nadaje znacznie częściej, choć wszystkie stacje używają algorytmu CSMA/CD.)
:::

## Zadanie 4
:::info
Jaka suma kontrolna $CRC$ zostanie dołączona do wiadomości $1010$ przy założeniu że $CRC$ używa wielomianu $x^2 + x + 1$? A jaka jeśli używa wielomianu $x^7 + 1$?
:::

Musimy znaleźć taki wielomian $S(x)$, że $G(x)\space |\space x^r*M(x)+S(x)$

Wiemy, że $S(x)=R(x)$, gdzie $x^r*M(x) : G(x)=Q(x)*G(x)+R(x)$

### a)
:::info
$x^2 + x + 1$
:::

$G(x)=x^2+x+1$
$r=st(G)=2$
Skoro $m = 1010$ to $M(x)=x^3+x$

$x^r*M(x) : G(x)=x^2*(x^3+x):(x^2+x+1)=\frac{x^5+x^3}{x^2+x+1}=\frac{x^5+x^4+x^3-x^4}{x^2+x+1}=\frac{x^3(x^2+x+1)}{x^2+x+1} + \frac{-x^4}{x^2+x+1}=\\=x^3+\frac{-(x^4+x^3+x^2)+x^3+x^2}{x^2+x+1}=x^3+\frac{-x^2(x^2+x+1)}{x^2+x+1} + \frac{x^3+x^2}{x^2+x+1}=x^3-x^2 + \frac{x^3+x^2}{x^2+x+1}=\\=x^3-x^2 + \frac{x^3+x^2+x-x}{x^2+x+1}=x^3-x^2 + \frac{x(x^2+x+1)}{x^2+x+1} + \frac{-x}{x^2+x+1}=x^3-x^2 + x + \frac{-x}{x^2+x+1}=\\=x^3-x^2 + x + R(x)$

Gdzie $R(x)=\frac{-x}{x^2+x+1}$, czyli $S(x)=-x=10$

### b)
:::info
$x^7 + 1$
:::

$G(x)=x^7+1$
$r=st(G)=7$
Skoro $m = 1010$ to $M(x)=x^3+x$

$x^r*M(x) : G(x)=x^7*(x^3+x):(x^7+1)=\frac{x^{10}+x^8}{x^7+1}=\frac{x^3(x^7+1)+x^8-x^3}{x^8+1}=x^3+\frac{x^8-x^3}{x^7+1}=\\=x^3+\frac{x(x^7+1)-x^3-x}{x^7+1}=x^3+x+\frac{-x^3-x}{x^7+1}=x^3+x+R(x)$

Gdzie $R(x)=\frac{-x^3-x}{x^7+1}$, czyli $S(x)=-x^3-x=0001010$

## Zadanie 5
:::info
Pokaż, że $CRC-1$, czyli $1-bitowa$ suma obliczana na podstawie wielomianu $G (x) = x + 1$, działa identycznie jak bit parzystości.
:::

$G(x) = x+1$
$r=st(G)=1$
$M(x) = m$

$x^r*M(x) : G(x)=x*M(x):(x+1)$

Z twierdzenia Bézouta wiemy, że jeśli $(x+1)\space |\space x*M(x)$, to $(-1)*M(-1)=0$

Czyli w arytmetyce $F_2$: $\space S(x) = 0 \leftrightarrow M(1)=0$

$M(1)=\displaystyle\sum_{i=1}^{St(M)} m_i$, gdzie $m_i$ jest $i$-tym bitem liczby binarnej $m$
W arytmetyce $F_2$ suma ta jest równa $1$ jeżeli liczba zapalonych bitów jest nieparzysta, a równa $0$ jeżeli ta suma jest parzysta. Czyli ta 1-bitowa suma działa identycznie jak bit parzystości.
$\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\blacksquare$
 
## Zadanie 6 X
:::info
Załóżmy, że wielomian $G(x)$ stopnia n stosowany w $CRC$ zawiera składnik $x^0$. Pokaż, że jeśli wybierzemy dowolny odcinek długości $n$ z wiadomości i dowolnie go zmodyfikujemy (zmienimy dowoln niezerową liczbę bitów w nim), to zostanie to wykryte. Czy taka własność zachodzi, jeśli $G(x)$ nie zawiera składnika równego $x^0$?
:::

## Zadanie 7 X
:::info
Pokaż, że kodowanie $Hamming(7,4)$ umożliwia skorygowanie jednego przekłamanego bitu. Wskazówka: wystarczy pokazać, że odległość Hamminga między dwoma kodami wynosi co najmniej $3$.
:::

## Zadanie 8 X
:::info
Pokaż, że suma $CRC$ stosująca wielomian $G (x) = x^3 + x + 1$ wykryje wszystkie podwójne błędy (zmianę wartości dwóch bitów), które są oddalone od siebie o nie więcej niż $6$ bitów (tj. pomiędzy dwoma zmienianymi bitami jest nie więcej niż $5$ innych bitów)
:::

## Zadanie 9 X
:::info
Załóżmy, że wyliczamy sumę $CRC$ dla $4$-bitowej wiadomości używając wielomianu $G (x) = x^3 + x + 1$; wtedy wiadomość wraz z sumą ma długość $7$ bitów. Załóżmy, że co najwyżej jeden z tych $7$ bitów został przekłamany. Pokaż, jak odbiorca takiego komunikatu może wykryć i skorygować takie przekłamanie.
:::

## Zadanie 10 X
:::info
Dana jest deterministyczna funkcja skrótu $h$ zwracająca na podstawie tekstu liczbę $m$-bitową. Losujemy $2^{m/2}$ tekstów i obliczamy na nich funkcję $h$. Zakładamy tutaj, że przy takim losowaniu tekstu $x$, $h(x)$ jest losową (wybraną z rozkładem jednostajnym) liczbą $m$-bitową. Pokaż, że prawdopodobieństwo, że wsród wylosowanych tekstów istnieją dwa o takiej samej wartości funkcji $h$ jest $Ω(1)$.
:::

<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>