Dyskretyzacja, kodowanie i kwantowanie.

• dyskretyzacja:
  Twierdzenie Kotielnikowa-Shannona - Sygnał ciągły może być wiernie odtworzony z ciągu swoich próbek tworzących sygnał dyskretny, jeśli próbki te zostały pobrane z częstotliwością ponad dwa razy większą od granicznej częstotliwości swego widma (tak zwany warunek Nyquista).

Niech u : R → R będzie sygnałem wejściowym, T_s będzie okresem próbkowania. Wartość sygnału analogowego u w chwili t ∈ R wynosi więc u(t) ∈ R. Mówimy,

że sygnał ten jest ciągły w dziedzinie czasu, chodzi tu o ciągłość czasu t, którego

wartości należą do zbioru R o mocy kontinuum(ciągły, nieskończony, uporządkowany). Za Układem Próbkująco-Pamiętającym wartości sygnału u będą miały postać u(k T_s). Pamiętając w pamięci komputera wartość okresu T_s możemy teraz operować pewnym abstrakcyjnym sygnałem $\tilde{u}:\mathbf{Z \rightarrow R}$. Wartość sygnału $\tilde{u}$ dla próbki o numerze k ∈ Z wynosi więc $\ \tilde{u}$(k). Ponieważ jest to ciąg wartości sygnału u w chwilach k T_s, to będziemy go zapisywać w postaci ciągu:

$\left( {\tilde{u}}_{k} \right)_{Z}$≔ (… ,${\tilde{u}}_{- 2}$, ${\tilde{u}}_{- 1}$, ${\tilde{u}}_{0}$, ${\tilde{u}}_{1}$, ${\tilde{u}}_{2}$, … )

Proces ten nosi nazwę dyskretyzacji sygnału (w czasie).

• Kwantowanie
  Załóżmy dalej, że ∀t ∈ R wartości sygnału u(t) ∈ [u_min, u_max] ⊂ R. Z kolei, przedział [u_min, u_max] dzielimy na K podprzedziałów. Zwykle K = 2ⁿ − 1, gdzie n jest liczbą bitów Przetwornika A/C. A zatem K + 1 = 2ⁿ jest liczbą poziomów kwantowania, którą możemy zakodować za pomocą n bitów. Mamy więc, że kwant

$$q\ : = \ \frac{u_{\max} - u_{\min}}{2^{n} - 1}$$

Pamiętając w pamięci komputera wartość kwantu q możemy teraz operować pewnym

abstrakcyjnym sygnałem $\tilde{\tilde{u}}:\mathbf{Z \rightarrow Z}$. Wartość sygnału $\tilde{\tilde{u}}$ dla próbki o numerze k ∈ Z wynosi więc

round() – zaokrąglenie ${\tilde{\tilde{u}}}_{k}\ : = round\left( \frac{{\tilde{u}}_{k}}{q} \right)\ : = int\left( \frac{{\tilde{u}}_{k}}{q} + 0.5 \right)$

lub

$${\tilde{\tilde{u}}}_{k}\ : = \text{int}\left( \frac{{\tilde{u}}_{k}}{q} \right)$$

Wybór wzoru zależy od rodzaju przetwornika A/C. Proces ten nazywamy kwantowaniem

(amplitudy) sygnału i dokonywany jest wewnątrz przetwornika A/C.

• Kodowanie
  Poziomom kwantowania, których jest K + 1 możemy przypisać kody liczbowe. Proces ten nazywamy kodowaniem i dokonywany jest, podobnie jak kwantowanie, wewnątrz przetwornika A/C.

• Kody dwójkowe:

USB – wartości 0-15

BCD – wartości 0-9 dalej A-F

BOB – wartości (-8) - 7

BTC – wartości 0-7 dalej (-8) – (-1)

BOC – wartości 0-7 dalej (-7) – (-0)

SMB – wartości 0-7 dalej (-0) – (-7)

Przyjęta kolejność kodów: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111.

Minimalizacja funkcji logicznych. Tablice Karnaugha…

• Kod Gray’a

Załóżmy, że zaprojektowaliśmy układ cyfrowy bez zachowania zasady kodu Gray’a i korzysta on z 3-bitowych stanów, a każdy z nich określa inną czynność wykonywaną.
Następują w nim kolejne zmiany stanów 000 -> 001 -> 010 -> .. itd.
Choć przejście z 1 do 2 stanu odbywa się bezproblemowo to między 2, a 3 stanem wystąpi błąd. Jest to określone przez fakt, że zamian kolejnych wyrazów w danym słowie bitowym nie następuję jednocześnie.

W naszym przypadku oznacza to, że po stanie 2 wystąpi stan 011 lub 000, a dopiero po nim stan 3. W celu uniknięcia podobnych błedów został stworzony…

Kod Gray’a – jego cechą jest że dwa kolejne wyrazy różnią się od siebie stanem tylko jednego bitu. Jest on niezbędny przy projektowaniu układów elektronicznych w celu uniknięcia występowania błędów podczas zmiany kolejnych stanów.

• Metoda hipersześcianów

Na podstawie kodu Gray’a lub inaczej warunku poprawnego działania układu cyfrowego, można stworzyć graficzną metodę tworzeni układu/automatu kombinacyjnego.

Jeżeli każdy kolejny stan określimy przez wierzchołek, a każde dwa wierzchołki które spełniają zasadę kodu Gray’a połączymy odcinkiem, to powstaje nam graficzna interpretacja działania układu kombinacyjnego. Rzeczą oczywistą jest fakt, że zmieniając stan możemy „poruszać” się tylko po odcinkach.

Tak więc, jeżeli nasz układ przyjmuje wyłącznie 2 stany to jego działanie możemy przedstawić za pomocą dwóch wierzchołków (odpowiednio 1 i 0 ) i jednego odcinaka je łączącego.
Natomiast gdy przyjmuje 4 stany, powstanie nam kwadrat w którym kolejne dwa stany różniące się od siebie stanem jednego bitu są połączone odcinkiem, a w przypadku 8 stanów powstanie nam sześcian.
Natomiast kolejne 16, 32, 64… stanów przedstawiamy za pomocą kolejnych sześcianów. W celu przejścia na kolejny sześcian wykonujemy skok pamiętając o zasadzie kodu Gray’a.

• Metoda tablic Karnaugh’a.

Projektowanie układów kombinacyjnych za pomocą metod brył geometrycznych jest pracochłonne, a także jest niewygodna dla człowieka który woli myśleć przestrzeni dwu-wymiarowej niż trój-wymiarowej.

Mając to na uwadze Karnaugh, stworzył metodę w której nie poruszamy się po odcinkach brył geometrycznych lecz po kratkach tablicy.
Z tym że wiersze tablicy są opisane przez cześć zmiennych binarnych, a kolumny przez pozostałą cześć. Stan odpowiadający danej kratce powstałej poprzez sklejanie binarnego numeru wiersza z binarnym numerem kolumny.

Powstała w ten sposób tablica zawiera wszystkie stany układu.
Pamiętać jednak należy o tym, że tylko sąsiednie kratki z stanami spełniają zasadę kodu Gray’a. Tym samym w celu zmiany stanu należy poruszać się po sąsiednich kratkach (nie można poruszać się po skosie!)

Przykład tablicy dla stanów 4-bitowych

Jest to metoda znacznie skuteczniejsza niż jej odpowiedniki geometryczne, a także umożliwia skorzystania z minimalizacji funkcji logicznych.

• Minimalizacja funkcji logicznych metodą siatek Karnaugh’a.

Stworzenie tablicy Karaugh’a nie umożliwia nam jeszcze zbudowani układy logicznego, do określeni zadań wykonywanych przez układ niezbędne jest stworzenie funkcji logicznych będących w postaci odpowiednich równań.

W tym celu należy wewnątrz kratek tablicy wpisać stany (0 lub 1) jakie mają pojawić się na danym wyjściu przy odpowiedniej kombinacji sygnałów wejściowych, a następnie zakreślenie w danej tablicy jak najliczniejszych grup składających się 1 (implikanty) lub 0 (implicenty) pamiętając o zasadach:

• Ilość zakreślonych kratek w jednej grupie musi być zawsze 2^k ( k ∈N )

• Zakreślona grup musi być zawsze symetryczna względem z którejś z głównych osi tablicy

Następnie należy stworzyć równania opisujące sygnał na wyjściu. W zależności od tego czy zakreślone zostały grupy 1 lub 0 otrzymujemy funkcję w postaci sumy iloczynu lub iloczynu sum zmiennych. Z tym, że zmienne wchodzące do opisu danej grupy, są to zmienne które w obrębie swojej grupy nie zmieniają wartości na przeciwną.

Surjekcja, Injekcja, Bijekcja, a Zasada Szufladkowania Dirichleta.

• Surjekcją lub funkcją odwzorowującą X na Y nazywamy funkcję f : X ↦ Y spełniającą warunek:

$$\bigwedge_{y \in Y}^{}{\bigvee_{x \in X}^{}{f\left( x \right) = y}}$$

Funkcja jest suriekcją, jeśli jej cała przeciwdziedzina jest wykorzystana, tzn. każdy jej element jest wartością funkcji dla jakiegoś elementu dziedziny. Suriekcje często są nazywane funkcjami „na”.

• Iniekcją lub funkcją różnowartościową nazywamy funkcjęf : X ↦ Y spełniającą warunek:

$$\bigvee_{x_{1},x_{2} \in X}^{}{x_{1} \neq x_{2}} \Rightarrow f(x_{1}) \neq f(x_{2})$$

Funkcja jest iniekcją, jeżeli różnym elementom dziedziny funkcja przyporządkowuje różne elementy przeciwdziedziny. Iniekcje często są nazywane funkcjami różnowartościowymi.

• Bijekcja to funkcja, która jest jednocześnie suriekcją i iniekcją.

• Zliczanie zbiorów

Załóżmy, że na parkingu stoi n samochodów. Zliczając je wybieramy elementy Z_n i przypisujemy je do samochodów na parkingu. Określamy zatem w trakcie tego zliczania bijekcję f : Z_n → S, gdzie S jest zbiorem samochodów na parkingu. W istocie jest to bijekcja, bo dwa różne samochody mają różne numery (injektywność) i każdy samochód jest policzony (surjektywność).

(*) Obserwacja: Gdy m<n, to nie istnieje iniekcja z Z_n w Z_m.

• Zasada Szufladkowa Dirichleta

Wcześniejsza (*) obserwacja ma bardziej praktyczną interpretację. Jest to formalne ujęcie faktu powszechnie znanego jako Zasada Szufladkowa Dirichleta:

Jeśli n obiektów jest rozmieszczonych w m szufladach i n>m, to istnieje szuflada z przynajmniej dwoma obiektami.

Dowód. Zbiór obiektów jest bijektywny ze zbiorem Zn, zaś zbiór szuflad z Zm. Rozmieszczenie obiektów w szufladach to określenie funkcji z Zn w Zm. Ponieważ n>m, to (*) obserwacja mówi nam, że funkcja ta nie jest iniekcją, a zatem lokuje co najmniej dwa obiekty w tej samej szufladzie.

Przykłady:

1) Wśród mieszkańców Krakowa co najmniej 2 osoby mają tę samą liczbę włosów na głowie.

Dowód. Liczba włosów na głowie nie przekracza 500.000, natomiast liczba mieszkańców Krakowa przekracza 800.000. Weźmy 500.000 szufladek ponumerowanych kolejnymi liczbami naturalnymi od 0 do 499.999 i wkładajmy do szufladki o danym numerze osoby, które mają taką liczbę włosów na głowie, jaki numer szufladki. Ponieważ osób jest 800.000, a szufladek 500.000, z Zasady Szufladkowej wynika, ze w jednej szufladce muszą się znaleźć co najmniej dwie osoby.

2) W grupie 13 osób musza być co najmniej 2, które urodziły się w tym samym miesiącu.

Dowód. Weźmy 12 szufladek z nazwami miesięcy i wkładajmy do nich Dowody Osobiste tych osób, które urodziły się w danym miesiącu. Ponieważ osób jest 13, a szufladek 12, w jednej z nich muszą być co najmniej 2 osoby.

3) Problem witania się z gośćmi, strona 26 w pdf do ewentualnego doczytania.

• Uogólniona Zasada Szufladkowa

Jeśli m obiektów rozmieszczonych jest w n szufladach i m>n*r, dla pewnego naturalnego r, to istnieje szufladka z co najmniej r+1 obiektami.

13. Elementy Teorii Liczb, Generatory Liczb Pseudolosowych i Szum Biały

Generatory liczb (ciągów) pseudolosowych o rozkładzie jednostajnym oraz generatory pseudolosowych ciągów dwójkowych o rozkładzie dwupunktowym mogą być zrealizowane w sposób numeryczny, a generator pseudolosowych ciągów dwójkowych może być nawet zrealizowany sprzętowo.

Problem generacji liczb pseudolosowych związany jest z pojęciem ciała skończonego.

Rodzaje generatorów:

(1) Generator multiplikatywny jest to generator linowy zdefiniowany

$\bigwedge_{}^{}{n \in Z_{+}}$ w następujący sposób:

r₀ > 0

Oraz

r_n : = a r_n − 1(mod M).

(2) Generator mieszany jest generatorem liniowym, który $\bigwedge_{}^{}{n \in Z_{+}}$ ma postać:

r_n : = a r_n − 1 + b(mod M),

gdzie współczynnik b>0.

(3) Generator addytywny (uogólnionym generatorem Fibonacciego) nazywamy generator liniowy zdefiniowany $\bigwedge_{}^{}{n \in Z_{+}}$ za pomocą równań:

r₀ + b > 0

Oraz

$r_{n} : = \sum_{i = 0}^{k - 1}{a_{i}\ r_{n - k + 1} + \ b(mod\ M)},$

Gdzie współczynniki a₀, …,  a_k − 1, b ∈ {0,1}. A z kolei generator addytywny, który $\bigwedge_{}^{}{n \in Z_{+}}$ ma postać:

r₀ > 0

Oraz

r_n : = r_n − 1 +  r_n − 2(mod M),

Nazywamy generatorem Fibonacciego.

(4) Generatorem dwójkowym (binarnym) nazywamy generator liniowy zdefiniowany $\bigwedge_{}^{}{n \in Z_{+}}\ $za pomocą równań:

r₀ = 1

Oraz

$r_{n} : = \sum_{i = 0}^{k - 1}{a_{i}\ r_{n - k + 1}(mod\ 2)}\text{\ \ }$

Generatory tego rodzaju nazywane są też generatorami pseudolosowych ciągów dwójkowych, w skrócie generatorami PRBS (z ang. Pseudo-Random Binary Sequences).

(5) Wirówka mersenna’a (and. Mersenne Twister)

• Mersenne Twister to algorytm generatora liczb pseudolosowych opracowany w 1997 przez Makoto Matsumoto i Takuji Nishimura. Generator jest szybki i dostarcza wysokiej jakości liczby pseudolosowe. Został zaprojektowany specjalnie dla naprawienia wielu wad, które znajdują się w starszych algorytmach.

Nazwa generatora pochodzi od tego, że na długość okresu wybierana jest liczba pierwsza Mersenne'a. Istnieją co najmniej dwa warianty algorytmu, które różnią się jedynie wielkością użytych liczb pierwszych Mersenne'a.

• Twierdzenie o generatorze multiplikatywnym:
  Jeżeli dla generatora multiplikatywnego

r₀ > 0

Oraz

r_n : = a r_n − 1(mod M)

moduł

M = 2^m

Oraz m ≥ 3, to maksymalny jego okres

N_max = 2^m − 2

można osiągnąć dla nieparzystych wartości r₀, gdy

a ≡ 3(mod 8)

lub

a ≡ 5(mod 8)

• Twierdzenie o generatorze mieszanym:
  Jeżeli dla generatora mieszanego

r_n = r_n − 1 + b(mod M)

Liczby b i M są względnie pierwsze dla każdego czynnika pierwszego p modułu M

a ≡ 1(mod p)

Oraz

a ≡ 1(mod 4),

Gdy 4 jest dzielnikiem M, to ma on maksymalny okres

N_max = M.

• Twierdzenie o generatorze Fibonacciego:
  Jeżeli dla generatora Fibonacciego

r₀ > 0

oraz

r_n = r_n − 1 + r_n − 2(mod M),

moduł

M = 2^m,

to maksymalny jego okres

N_max = 3 * 2^m − 1

I nie zależy od wyboru r₀ i r₁.

W grach komputerowych czy algorytmach probabilistycznych (takich jak np.całkowanie Monte Carlo) potrzebne jest jedynie źródło wartości o cechach przybliżonych do liczb prawdziwie losowych, chociaż jakość losowości może być decydująca dla dokładności obliczeń. Dlatego przy zastosowaniu każdego nowego generatora do celów obliczeń numerycznych należy sprawdzić jego własności statystyczne.