2*2500/10^8 * 10Mb = 500 bit
2. Aloha
Mamy rundowy protokół ALOHA we współdzielonym kanale (w każdej rundzie jeden z n uczestników próbuje wysłać ramkę z prawdopodobieństwem p). Jakie jest P(p, n), że jednej stacji uda się nadać (nie wystąpi kolizja)? + Pokazać że P maksymalne dla p=1/n. + Ile wynosi P(1/n, n) dla n->∞ ?
Po pierwsze - ALOHA działa tak, że stacje wysyłają bez uprzedniego sprawdzania czy ktoś nadaje i sprawdzania czy będzie kolizja (np. stacje naziemne transmitujące do satelity + stacje się nawzajem nie widzą). Czas dzielimy na rundy(sloty) Założenie jest takie, że mamy dużo senderów nadajacych rzadko + pakiety mają takie same długości. Niech T to czas potrzebny na wysłania jednego pakietu (czyli też jeden slot czasowy). Wysyłamy pakiet/ slot czasowy z prawdopodobieństwem p.
Skoro per runda każdy chce wysłać z prawdopodobieństwem p, to szansa, że jeden wyśle a pozostałe nie wyślą jest P=np(1-p)⁽ⁿ⁻¹⁾. To teraz da p=1/n mamy P=(1-1/n)⁽ⁿ⁻¹⁾=(1-1/n)ⁿ*(1-1/n)⁻¹ → e dla n → ∞. Żeby pokazać, że w p=1/n jest maximum, wystarczy sprawdzić, że δ/δx P(p=1/n)=0, a druga pochodna to już na wiarę że to maksimum. Ogólnie to łatwe.
Po pierwsze - jest sobie algorytm Exponential Backoff w CSMA/CD. Po i kolizjach losowana jest liczba z przedziału 0->(2ⁱ-1) tzw. slot time, która oznacza, jaki czas stacja będzie musiala odczekać, zanim powtórnie rozpocznie nadawanie. Dostosowuje się to więc do natężenia w sieci - wraz ze wzrostem liczby kolizji liczba losowana jest na szerszym przedziale. i jest ograniczone zazwyczaj do jakiś 10-16.
I teraz powracając do naszego problemu: wyobraźmy sobie że stacje A i B mają do wysłania pakiety, więc biją się o łącze. A wygrywa pierwszy pakiet. A skończyło nadawać, więc B próbuje wysłać ponownie, ale A ma do wysłania drugi pakiet, więc wybiera opóźnienie na przedziale <2, ale jednocześnie B musi losować na przedziale <4, co oznacza, że A ma większe szanse na wygranie ( i załóżmy, że tak się dzieje). Po zakończeniu transmisji, A i B próbują znowu, A jest znów na pierwszym podejściu dla 3-go pakietu, a B na 3-cim podejściu do 1-go pakietu, dlatego A losuje na <2, a B ma <8. Za każdym razem gdy B przegyrwa, jego prawdopodobieństwo wygrania kolejnego maleje dwukrotnie. Taka sytuacja jest prawdopodobna i w praktyce często zdaża się, że B przegrywa wszystkie swoje próby zanim dojdzie do maxa (16). Prawdopodobieństwo tego jest bardzo duże już po 3-4 nieudanych próbach. Wtedy to B wywala pakiet do śmieci i próbuje dla następnego z licznikiem zresetowanym do początkowej wartości (<2).
wiadomość 1010 (m=x^3+x), CRC ma G1=x^2+x+1, albo G2=x^7 +1.
- r=2 => xʳM=x⁵+x³=G(x³-x²+x)+x => S=
0b10 - r=7 => xʳM=x¹⁰+x⁸=G(x³+x)+x³+x => S=
0b0001010
gdzie r to stpień wielomianu G, S to suma kontrolna.
gdzie M to wiadomość, G to nasz wielomian a S to suma kontrolna (małymi oznaczam bitowe repr.)
CRC-1, G=x+1 indukcja:
- podstawa dla m=1 ⇒ s=0 i m=0 ⇒ s=1
- załóżmy, że dla m i g działa gdzie m conajwyżej stopnia jakiegoś
- teraz przedłużamy m:
- 0..m ⇒ nic się nie zmienia więc OK
- 1..m ⇒ chcemy pokazać CRC(11..m) = CRC(m) i CRC(10..m) = !CRC(m). patrzymy na pierwszy bit m:
- m = 1..m' (11..m) => CRC(11..m) = !CRC(1..m) = CRC(m)
- m = 0..m' (10..m) => CRC(10..m) = !CRC(0..m) = CRC(1..m) = !CRC(m)
G st. n zawiera x⁰. Pokazać, że jeśli wybierzemy dowolny odcinek długości n z wiadomości i dowolnie go zmodyfikujemy, to zostanie to wykryte. Czy będzie działać, jeśli G nie ma x⁰ ?
- G = xⁿ+...+1, E(rror) = xⁱ(αₙxⁿ + ... + α₁x) = xⁱ⁺¹(αₙxⁿ⁻¹ + ... + α₁). Mamy G ⟂ xⁱ⁺¹ AND G ∤ (αₙxⁿ⁻¹ + ... + α₁) bo ma mniejszy stopień.
- G = xⁿ+...+0 = x(xⁿ⁻¹+...). G ∣ E jeśli E = xⁱ(xⁿ⁻¹+...), co może nastąpić.
mamy kodowanie bitów danych d na d i p(arzystości). Kodowanie jest jak poniżej:
0->00 --
1->70 --
2->4C ++
3->3C ++
4->2A
5->5A
6->66
7->16
8->69
9->19
A->25
B->55
C->43
D->33
E->0F
F->7F
Patrząc na sufiksy widać, że jeśli się różnią zawsze o 2 i dodatkowo w tych grupach różniących się o 2 prefiksy też są zawsze inne (grupy ++ i --). wewnątrz grup natomiast można zauważyć, że różnią się zawsze o ≥3. W Związku z tym przekłamanie jednego bitu zawsze można prześledzić do dobrego kodu.
G = x^3+x+1
E = x^i(x^[6|5|4]+1), dla mniejszych stopni jest prosto bo stopnie są ≤.
x^i ⟂ G
W=x⁶+1 = (x^3+x+1)^2 + x^2 => G ∤ W
W=x⁵+1 = (x^2+1)(x^3+x+1)+(x^2+x)=> G ∤ W
W=x^4+1 = x(x^3+x+1) + (x^2+x+1) => G ∤ W
Dla 2^(m/2) funkcja h(x) zwraca m-bitową liczbę (losową z ppd jednostajnym). Zacznijmy od tego, że mamy paradoks dnia urodzin. ppd mapowania na różne liczby jest 1*(1-1/2ᵐ)(1-2/2ᵐ)...*(1-(2^(m/2)-1)/2ᵐ) co się upraszcza do 𝚷 P' = i=0→2^(m/2)-1 (1-i/2ᵐ). Prawdopodobieństwo tego, że będzie kolizja jest więc P=1-P'. trzeba tylko pokazać, że to jest P>0, aka P'<1. no i można to ograniczać z faktu, że 1-x<e^-x dla dowonego x∈R. wtedy szereg sumuje się do e^-n(n-1)/2k, gdzie n=2^(m/2) a k = 2^m. Można z tego wyciągnąć, że lim m->∞ jest wtedy 1/sqrt(e) a dla m=1 to jest jakieś 0.8... więc nice. + funkcja monotoniczna.