Kodowanie informacji i transmisja w paśmie podstawowym

Wprowadzenie do kodowania informacji i transmisji w paśmie podstawowym

• Podział tematyczny wykładu:

  • Kodowanie źródłowe: dotyczy efektywnej reprezentacji danych, czyli kompresji.

  • Kodowanie kanałowe: koncentruje się na ochronie danych przed błędami w celu zapewnienia niezawodności.

  • Kodowanie liniowe: odnosi się do nadawania bitom fizycznej postaci przebiegów falowych.

  • Integralność sygnału: obejmuje zagadnienia pasma, interferencji międzysymbolowej (ISI) oraz analizę wykresów oczkowych.

Kodowanie źródłowe: Definicja, Cele i Korzyści

• Definicja: Jest to proces zamiany informacji pochodzącej ze źródła na możliwie najkrótszy ciąg binarny.

• Miejsce w torze komunikacyjnym: Proces ten zachodzi na samym początku toru (Koder źródła), przed koderem kanału i modulatorem.

• Mechanizm działania: Polega na redukcji nadmiarowości (redundancji) poprzez usuwanie treści powtarzalnych lub przewidywalnych, przy jednoczesnym zachowaniu pierwotnego znaczenia lub akceptowalnej jakości.

• Główne korzyści wynikające z kodowania źródłowego:

  • Oszczędność pasma: Możliwość przesłania większej ilości informacji w tym samym czasie przez dany kanał transmisyjny.

  • Mniejszy rozmiar danych: Dane zajmują mniej miejsca na nośnikach (np. przewaga formatu JPG nad BMP).

  • Szybsza transmisja: Przesyłanie mniejszej liczby bitów skraca czas oczekiwania na odbiór.

  • Redukcja kosztów: Mniejsza ilość danych to mniejsze zużycie energii i niższe koszty infrastruktury sieciowej.

Rodzaje kodowania źródłowego: Stratne vs Bezstratne

• Kodowanie Stratne (Lossy):

  • Zasada: Trwałe usuwanie informacji, których ludzkie zmysły (wzrok, słuch) nie są w stanie zarejestrować.

  • Zastosowania: Multimedia, streaming wideo, telefonia cyfrowa.

  • Formaty: JPEG, MP3, MP4, H.264.

  • Przykład: W filmach na YouTube oko nie zauważa braku ok. $90\%$ danych, co pozwala na płynną transmisję.

• Kodowanie Bezstratne (Lossless):

  • Zasada: Możliwość odzyskania danych „bit po bicie” – otrzymujemy idealną kopię oryginału.

  • Zastosowania: Dokumenty tekstowe, bazy danych, obrazy medyczne (RTG, MRI).

  • Formaty: ZIP, PNG, FLAC, PDF.

  • Przykład w medycynie: Stosuje się wyłącznie metody bezstratne, ponieważ utrata nawet jednego bitu mogłaby zmienić diagnozę lekarską.

Przykłady efektywności kodowania źródłowego

• Porównanie ASCII i Flagi Binarnej (Płeć użytkownika):

  • Podejście ASCII: Przechowywanie napisu "female" (48 bitów) lub "male" (32 bity) – każda litera to 8 bitów.

  • Podejście binarne: Użycie 1 bitu (0 = male, 1 = female).

  • Wynik: Redukcja rozmiaru o ponad $95\%$ bez straty jakiejkolwiek informacji.

• Słowo „HELLO”:

  • Standard ASCII: $5 \text{ liter} \times 8 \text{ bitów} = 40 \text{ bitów}$.

  • Kodowanie VLC: Wykorzystując kody o zmiennej długości, to samo słowo można zapisać za pomocą zaledwie $10 \text{ bitów}$, co daje $75\%$ oszczędności.

Automatyczne kodowanie o zmiennej długości (VLC)

• Zasada Variable Length Coding (VLC): Algorytmy analizują statystykę występowania symboli. Symbole częste otrzymują krótkie kody, a symbole rzadkie – długie kody.

• Algorytm Shannon-Fano (Top-Down):

  1. Sortowanie symboli według prawdopodobieństwa.

  2. Podział listy na dwie grupy o zbliżonej sumie prawdopodobieństw.

  3. Przypisanie bity (0 dla jednej grupy, 1 dla drugiej).

  4. Rekurencyjne powtarzanie procesu dla podgrup aż do uzyskania pojedynczych liści.

  • Przykład dla „HELLO”: L = 0, H = 10, E = 110, O = 111.

• Algorytm Huffmana (Bottom-Up):

  • Gwarantuje uzyskanie optymalnego kodu o najkrótszej średniej długości.

  1. Każdy symbol jest traktowany jako oddzielny „liść”.

  2. Łączenie dwóch elementów o najmniejszym prawdopodobieństwie w jeden węzeł (sumowanie wartości).

  3. Budowa drzewa aż do osiągnięcia korzenia o wartości $1.0$.

  4. Kodowanie krawędzi drzewa (0 i 1); kod symbolu to ścieżka od korzenia do liścia.

• Właściwości kodu Huffmana:

  • Kod przedrostkowy (prefiksowy): Żaden kod nie jest początkiem innego, co pozwala na dekodowanie bez separatorów (spacji).

  • Praktyczne użycie: Składnik standardów JPEG, MP3, ZIP, GZIP.

Matematyczne miary w kodowaniu

• Prawdopodobieństwo ($p_i$): Częstotliwość występowania symbolu (np. dla „L” w „HELLO” wynosi $0.4$).

• Ilość informacji/Miara zaskoczenia ($I$): Wyrażona w bitach jako $\log_2(1/p_i)$. Im rzadszy symbol, tym więcej informacji niesie.

• Entropia Shannona ($H$): Średnia ilość informacji na symbol:     $H = -\sum_{i=1}^{n} p_i \log_2 p_i$

Studium przypadku: Numer PESEL jako kod hybrydowy

• Struktura PESEL (kod blokowy o stałej długości - 11 cyfr):

  • 6 cyfr (YYMMDD): Data urodzenia (kodowanie źródłowe).

  • 4 cyfry: Numer serii i płci (nieparzysta = mężczyzna, parzysta = kobieta).

  • 1 cyfra (K): Suma kontrolna (kodowanie kanałowe).

• Rozwiązywanie kolizji stuleci (manipulacja miesiącem):

  • Aby odróżnić lata, dodaje się stałe do miesiąca:

    • 1800 – 1899: $+80$

    • 1900 – 1999: $+0$ (standard)

    • 2000 – 2099: $+20$

    • 2100 – 2199: $+40$

    • 2200 – 2299: $+60$

• Obliczanie sumy kontrolnej ($S$):     $S = (1 \times d_1 + 3 \times d_2 + 7 \times d_3 + 9 \times d_4 + 1 \times d_5 + 3 \times d_6 + 7 \times d_7 + 9 \times d_8 + 1 \times d_9 + 3 \times d_{10})$     $K = 10 - (S \pmod{10})$ (jeśli wynik to 10, $K = 0$).

Kodowanie kanałowe: Ochrona przed błędami

• Cel: Niezawodne dostarczenie danych mimo szumu w kanale (kable, powietrze, światłowód).

• Metoda: Celowe dodawanie kontrolowanej nadmiarowości matematycznej („tarcza”).

• Parametry kodu blokowego (n, k):

  • $k$: Liczba bitów informacji faktycznej.

  • $r$: Liczba bitów nadmiarowych/parzystości.

  • $n$: Całkowita długość słowa kodowego ($n = k + r$).

  • Sprawność kodu (Code Rate): $R = \frac{k}{n}$. Im bliżej $1$, tym wyższa wydajność, ale słabsza ochrona.

Techniki kodowania kanałowgo

• Bit parzystości:

  • Najprostsza metoda wykrywania błędów ($r=1$).

  • Parzystość parzysta (Even Parity): Suma jedynek musi być parzysta.

  • Wada: Nie wykrywa parzystej liczby błędów, nie koryguje ich.

• Kod Hamminga (7, 4):

  • Dla każde $4 \text{ bitów}$ danych dodaje $3 \text{ bity}$ parzystości.

  • Możliwości: Wykrywa do dwóch błędów, naprawia jeden błąd (FEC – Forward Error Correction).

  • Syndrom: 3-bitowy wynik testów parzystości. Jeśli $\neq 000$, wskazuje adres uszkodzonego bitu.

• Kody Reed-Solomon (RS):

  • Operują na symbolach (np. blokach 8-bitowych), a nie pojedynczych bitach.

  • Specjalizacja: Błędy seryjne (Burst Errors), np. rysy na płycie CD.

  • Zastosowania: Kody QR, CD/DVD/Blu-ray, komunikacja satelitarna (Voyager).

  • Kody QR: Poziomy korekcji L ($7\%$), M ($15\%$), Q ($25\%$), H ($30\%$ odzysku danych).

• Przeplot (Interleaving) na płytach CD: Rozpraszanie symboli wzdłuż ścieżki, aby duża rysa (błąd seryjny) po de-interleavingu stała się serią pojedynczych błędów, które RS łatwo naprawi.

• Inne: CRC (Ethernet/Wi-Fi), LDPC/Turbo (4G/5G).

Transmisja w paśmie podstawowym (Baseband)

• Definicja: Przesyłanie sygnału cyfrowego w oryginalnym zakresie częstotliwości zaczynającym się od $0 \text{ Hz}$.

• Cechy: Brak fali nośnej, impulsy wysyłane bezpośrednio do medium (miedź, światłowód).

• Współdzielenie medium: Wykorzystuje TDM (Time Division Multiplexing) – podział czasu.

• Zastosowania: Ethernet (LAN), USB, HDMI, magistrale PCIe/SATA, sterowanie przemysłowe (RS-232, RS-485).

Kodowanie liniowe

• Definicja: Konwersja danych binarnych na fizyczny przebieg napięcia lub prądu.

• Wymagania wobec kodów liniowych:

  • Samotaktowanie (Synchronizacja): Umożliwia odtworzenie zegara z sygnału.

  • Eliminacja składowej stałej (DC): Kluczowa dla transformatorów (Ethernet).

  • Efektywność widmowa: Minimalizacja wymaganego pasma.

• Rodzaje kodów liniowych:

  • Unipolar NRZ-L: $1 = +V$, $0 = 0V$. Słaba synchronizacja, występuje składowa stała.

  • Polar NRZ: $1 = +V$, $0 = -V$. Lepsza odporność na szum niż unipolar.

  • Bipolar AMI: $0 = 0V$, $1 =$ naprzemiennie $+V$ i $-V$. Brak DC, detekcja błędów, ale gubi zegar przy ciągu zer.

  • Manchester: Informacja zawarta w kierunku przejścia (zboczu) w środku bitu ($1 =$ Low-to-High, $0 =$ High-to-Low). Idealna synchronizacja, brak DC, ale wymaga dwa razy szerszego pasma.

Interferencja międzysymbolowa (ISI) i Integralność Sygnału

• Przyczyna: Kable działają jak filtry dolnoprzepustowe (obwód RC o stałej $\tau = R \times C$). Ostre impulsy ulegają zaokrągleniu i rozszerzeniu w czasie.

• Definicja ISI: Przenikanie energii („ogonów” impulsów) na sąsiednie bity, co utrudnia poprawne próbkowanie.

• Kryterium Nyquista (Teoretyczna granica):

  • Szybkość symbolowa: $R_s \le 2B \text{ [Baud/s]}$

  • Szybkość bitowa: $R_b \le 2B \log_2 M \text{ [bps]}$, gdzie $M$ to liczba poziomów sygnału.

  • Przy $B = 1 \text{ MHz}$ i $M = 2$, maksymalne $R_b = 2 \text{ Mbps}$.

• Kształtowanie impulsu (Pulse Shaping):

  • Funkcja Sinc: Teoretycznie idealna (zerowe ISI w punktach próbkowania), ale niemożliwa do realizacji (nieprzyczynowa, nieskończona).

  • Filtr Raised Cosine (Podniesiony Cosinus): Praktyczne rozwiązanie. Parametr roll-off ($\alpha$) reguluje kompromis między pasmem a stabilnością:         $B_{req} = \frac{R_s}{2} (1 + \alpha)$

Stopa błędów (BER) i Twierdzenie Shannona-Hartleya

• Bit Error Rate (BER): Stosunek bitów błędnych do wszystkich przesłanych.

  • Standardy: Głos ($10^{-3}$), Światłowody ($10^{-12}$).

  • Wartość $0.5$ oznacza całkowity brak komunikacji (zgadywanie).

• Twierdzenie Shannona-Hartleya: Określa maksymalną przepustowość kanału ($C$) w obecności szumu:     $C = B \log_2 (1 + SNR)$

  • Aby zwiększyć szybkość, należy zwiększyć pasmo ($B$) lub moc sygnału (poprawa $SNR$).

Wykres oczkowy (Eye Diagram)

• Definicja: Wizualne narzędzie oceny jakości sygnału powstałe przez nałożenie na siebie segmentów strumienia danych.

• Kluczowe parametry wykresu:

  • Wysokość oka: Margines szumu. Im większa, tym lepiej.

  • Szerokość oka: Margines czasu. Szersze oko = mniejsza wrażliwość na błędy zegara.

  • Jitter: Poziome rozmycie punktów przecięcia, oznacza niestabilność czasową.

  • Grubość linii: Świadczy o poziomie szumu losowego i resztkowego ISI.

  • Zamknięte oko: Oznacza bardzo niską jakość sygnału i wysoki BER ($\approx 50\%$).", "title": "Kodowanie informacji i transmisja w paśmie podstawowym"}