PŘENOS PŘENOS DAT DAT Doc. Ing. Aleš Prokeš, Ph.D
[email protected],
Tel.: 541 149 149,
Obsah 1. Základní stavební bloky digitálního komunikačního systému 2. Přenos dat v telekomunikačních sítích 3. Přenos dat v počítačových sítích 4. Bezdrátové prostředky přenosu dat
1. Základní stavební bloky digitálního komunikačního systému
•
Format (digitalizace signálu): vzorkování, lineární a nelineární kvantování, pulsní kódová modulace (PCM)
•
Source encode (zdrojové kódování): kódování řeči, hudby a obrazu pro odstranění redundance. Ztrátové kódování (MPEG, JPEG) a bezeztrátové kódování (Huffmanův kód, LZH, ARJ, …).
•
Encrypt (kryptografie): zabezpečení informace proti zneužití. Veřejné a neveřejné klíče.
•
Channel encode (kanálové kódování): zabezpečení dat proti chybám pomocí detekčních nebo opravných kódů. Blokové kódy, konvoluční kódy a turbokódy.
•
Multiplex (multiplex): sloučení více datových toků (od několika uživatelů) do jednoho.
•
Pulse modulate (tvarování pulsů, ekvalizace): tvarování pulsů za účelem snížení šířky jejich pásma a potlačení mezisymbolových interferencí. Případně vytvoření linkového kódu pro komunikaci v základním pásmu.
•
Bandpass modulate (modulace): převod signálu ze základního pásma do přeneseného modulací nosné vlny. Modulace MQAM, MPSK, MFSK, GMSK, …
•
•
• • • • • • • •
Frequency spread (kmitočtové rozprostření): rozšíření kmitočtového spektra pro širokopásmové přenosy (eliminace úniků, utajení…). Přímá modulace pseudonáhodnou posloupností (DS), kmitočtové nebo časové skákání (FH, TH), hybridní systémy. Multiple access (mnohonásobný přístup): přidělení kanálu jednotlivým uživatelům časovým dělením (TDMA), kmitočtovým dělením (FDMA), kódovým dělením (CDMA) Prostorovým dělením (SDMA), polarizačním dělením (PDMA)…. XMT (vysílač). Synchronization (synchronizace): zajištění přenosu nebo získání informace o časování symbolů, kmitočtu a fázi nosné vlny, časování rámců (multiplexu), … Channel (přenosový kanál): zavádí zpoždění, rušení, disperzi … RCV (přijímač). ……. Inverzní operace…… Demodulate & sample (demodulace a vzorkování): převod signálu demodulátorem do základního pásma, ekvalizace a vzorkování ve vhodných okamžicích daných obvodem synchronizace. Detect (vyhodnocení symbolů): detekce symbolů v závislosti na typu modulace (např. vyhodnocením amplitud pro MPSK nebo MQAM) ……. Inverzní operace……
1.1 Metody zdrojového kódování Redundance: množství znaků, symbolů nebo bitů které je možné eliminovat, aniž by došlo ke ztrátě užitečné informace. Odstranění redundance = bezeztrátové kódování (komprese). Irelevance: nepodstatná (zbytečná) složka informace, kterou je možné ve zdrojovém kodéru zcela potlačit aby byla zachována potřebná kvalita signálu. Odstranění irelevance = ztrátové kódování (komprese).
1.1.1 1.1.1Kódování Kódovánířečových řečovýchsignálů signálů(300 (300Hz Hzaž až3.4 3.4KHz) KHz) PCM (Pulse Code Modulation): analogově digitální (A/D) převodník. Počet bitů = 3
Hodnoty vzorků 8bitů
Datový tok při kvantování řeči Kmitočet vzorkování 8 kHz, (vzorkovací teorém: fvz ≥ 2fmax) Kvantování 8 bitů ⇒ R = 64 kbit/s
PCM (Pulse Code Modulation): s nelineární charakteristikou.
Praktické využití: A/D převod v telefonních ústřednách. A-law v Evropě, μ-law v USA.
Logaritmické charakteristiky kodeků s nelineárním kvantováním A law a μ law 8 bitů (1+3+4) aproximované lomenou přímkou
úsek (chord)
Zn
x
x
x
krok (step)
x
x
x
x
x
Parametrické zdrojové kódování: vokodéry
Hláska S
Kvaziperiodický průběh
Pseudonáhodný průběh
Blokové schéma vokodéru
Kanálem se nepřenáší hovorový signál ale pouze jeho parametry získané na základě analýzy. Segmentování: vytváření úseků 10-30 ms (parametry hlasového traktu jsou konstantní) Z-N: znělá-neznělá hláska T0: perioda budících pulsů (perioda základního tónu) Modernější systémy používají multiimpulsní buzení
Zjednodušený model vokodéru a multiimpulzního systému
1.1.2 Kódování akustických signálů (20 Hz – 20 kHz) Využití maskovacího jevu lidského sluchu 70 práh současné slyšitelnosti
60 50
slyšitelný zvuk
40 30
L = 20 log
P 20 μPa
20
neslyšitelný zvuk
10 0
práh slyšitelnosti
20 Pa 0.25
1
4
[kHz]
Křivky současné slyšitelnosti při maskování jednotlivých kmitočtů úzkopásmovým šumem s šířkou pásma 160 Hz, konstantní hladinou a třemi středními kmitočty (závisí na kmitočtu a amplitudě).
Subpásmové kódování 1. pásmo
2. pásmo
3.
4.
5. 6. 7. 8. 10. 11. až 32. pásmo
dílčí pásma [1 až 32]
70 LT = 60 dB
60
11. až 26. pásmo
0.25
1
4
0
-10
40
-20
30
-30
20
-40
10
-50
0
-60
0.02
0.05
0.1
0.2
0.3
0.4 0.5
1 0.75 [kHz]
2 1.5
3
4
2.25 3
5 4.5
3.75
10 6
7.5
5.25 6.75
20
[dB]
L[dB]
50
•
MPEG 1 – úroveň 1 (Audio Layer 1) – nejjednodušší, malá redukce přenosové rychlosti pro nejkvalitnější signál (vstup: (32, 44.1) a 48 kS/s ⋅16 bitů = 768 kbit/s, dělení na skupiny (rámce) po 384 vzorcích ⋅ [48 kS/s]-1 = 8ms. Transformace. Dělení do 32 kanálů (750 Hz) po 12 vzorcích, podvzorkování 1.5 kS/s, kvantování 2-15 bitů v každém kanálu podle měřítka a psychoakustického modelu, výstup: 448 kbit/s – 32 kbit/s)
•
MPEG 1 – úroveň 2 (Audio Layer 2) vychází ze systému MUSICAM (Masking pattern adapted Universal Subband Integrated Coding And Multiplexing) určený pro DAB (Digital Audio Broadcasting). Nižší přenosová rychlost signálu ve srovnání s úrovní 1 při zvýšení jakosti zvuku na nízkých kmitočtech (vstup: (32, 44.1) a 48 kS/s ⋅16 bitů = 768 kbit/s, dělení na skupiny (rámce) po 1152 vzorcích ⋅ [48 kS/s]-1 = 24ms. Dělení do 32 kanálů (750 Hz) po 36 bitech (3 činitelé měřítka), kvantování 215 bitů u nízkých kmitočtů, výstup: 384 kbit/s – 32 kbit/s).
MPEG 1 – úroveň 1.
1.1.3 Kódování obrazu 1. Kompozitní: kódování signálu PAL, NTSC,….. 2. Složkové: Y, R-Y, B-Y: 4:4:4 (3×13.5 MS/s), 4:2:2 (1×13.5 MS/s+2× 6.75 Ms/s = 216 Mb/s při 8 bit A/D (ITU-R 601). •
transformační kódování (DFT, FFT, DCT, WHT (Walsh-Hadamar) – pro statické obrazy,
•
prediktivní kódování (využití prostorová korelace) – pro pohyblivé obrazy,
•
hybridní kódování (pohybová kompenzace) – pro pohyblivé obrazy.
Transformační kódování JPEG: Diskrétní kosinová transformace DCT Kvantování pomocí matice (dělení a zaokrouhlování )
⎡ G (u, v ) ⎤ Y (u , v ) = round ⎢ ⎥ ⎣ Q(u , v ) ⎦
Kodér, dekodér JPEG
Prediktivní kódování MPEG: Metody zpracování: •
Zpracování v makroblocích 16 × 16.
•
Dělení do skupin snímků opakující se po 12 snímcích.
•
Transformace v prostorové oblasti – DCT.
•
DPCM, Predikce ze snímků předchozích, nebo předchozích a následných (nutná reorganizace snímků).
Hybridní kódování: Stejné jako prediktivní, navíc využití pohybové estimace BMA (Block Matching Algorithm). Určení a přenos vektorů pohybu dvou bloků a hodnoty míry podobnosti.
Přenosové rychlosti typických aplikací
APLIKACE
Přenosová rychlost Přenosová rychlost před kompresí po kompresi
Video s pomalým pohybem (10 snímků/s, 176×120, 8bitů/pixel)
5.07 Mbit/s
8 - 16 kbit/s
Videokonference (15 snímků/s, 352×240, 8bitů/pixel)
30.41 Mbit/s
64 - 768 kbit/s
Video na CD-ROM (30 snímků/s, 352×240, 8bitů/pixel)
60.83 Mbit/s
1.5 - 4 Mbit/s
Digitální TV vysílání (30 snímků/s, 720×480, 8bitů/pixel)
248.83 Mbit/s
3 - 8 Mbit/s
1330 Mbit/s
20 Mbit/s
HDTV vysílání (59.94 snímků/s, 1280×720, 8bitů/pixel)
1.1.4 Kódování dat Smyslem je zakódovat posloupnost symbolů zdrojové abecedy tak aby délka symbolů kódové abecedy byla co nejnižší a posloupnost byla jednoznačně dekódovatelná. Neadaptivní kódování: používá předdefinované pevné slovníky Huffmanův kód: kód proměnné délky (VLC).
Adaptivní kódování: používá dynamicky vytvářené slovníky (LZW (Lempel – Ziv – Welch), ZIP, GIF, TIFF, ARJ). Knihovna značek se vytváří postupně. Určitý úsek dat je kódován srovnáním s předchozími značkami knihovny. Pokud dojde ke shodě, použije se identifikace (adresa) shodné značky a přidá se další symbol. Příklady Lempel – Ziv algoritmu: Posloupnost symbolů pro kódování: [a b a a b a b b b b b b b a b b b bba] Kóduje se ve tvaru: 〈adresa knihovny, další symbol〉. kódový paket adresa obsah buňky
〈0,a〉 1 a
〈0,b〉 2 b
〈1,a〉 3 aa
〈2,a〉 4 ba
〈2,b〉 5 bb
〈5,b〉 6 bbb
〈5,a〉 7 bba
〈6,b〉 8 bbbb
〈4,-〉
1.2 Kryptografie Převedení srozumitelné zprávy do nesrozumitelné podoby a zpět (šifrování a dešifrování).
1.2.1 Symetrická (konvenční) kryptografie Šifrování s privátním klíčem. Stejný klíč pro šifrování i dešifrování. Účastníci musí klíč znát, nebo se musí přenést (obvykle jiným kanálem).
Substituce: Vzájemná záměna symbolů (písmen abecedy): Př.: M1↔M4, M2↔M8, …. Nový symbol ŠZ je vytvořen kombinací několika jiných. C1=M1 XOR M2 XOR M6, C2=… Permutace: reorganizace uspořádání posloupnosti prvků. Př.: Cézarova šifra: E = 1,3,5,7,9,2,4,6,8,10, E(3) = 5,… Transpozice: zápis
čtení
1.2.2 Nesymetrická kryptografie Používají se dva různé klíče: veřejný Ek a privátní (soukromý) Dk. Odesílatel šifruje vždy veřejným klíčem (dostupným každému uživateli). Konkrétní příjemce dešifruje privátním klíčem (jedinečným pro každého uživatele). • • • •
• •
Lze zveřejnit šifrovací metodu, algoritmus i veřejný šifrovací klíč. Privátní klíč musí být utajen !!! Klíče Ek a Dk jsou inverzní transformace otevřeného textu M, resp. šifrovaného textu C, C=Ek(M) a M=Dk(C). Výpočet Dk z Ek pro daný klíč K je obtížný (prakticky nemožný) Trapdoor One-way Functions: př.: y = x5+12x3+107x+123, výpočet y = f(x) je snadný snadné ale výpočet x = f(y) obtížný. Teoretický základ šifrování komplikovaný, vlastní výpočet snadný. Nejznámější šifry: RSA, El Gamal, bezpečnost založena na obtížnosti výpočtu diskrétních logaritmů (nalezení x ve vztahu
y = gx mod p, p je prvočíslo).
Příklad: za x se dosadí privátní klíč Dk. y pak tvoří veřejný klíč Ek nebo jeho část (zveřejní se). Provede se výpočet C = Ek(M). Pro prolomení šifry nebo její dešifrování je třeba určit M = Dk(C). Výpočet Dk = f(Ek) je obtížný, avšak příjemce šifry Dk zná. Šifrovací a dešifrovací mechanizmus A→B
Autorizace: A vytvoří zprávu: S=DA(M) ⇒ C=EB(S)=EB[DA(M)] B: DB{EB[DA(M)]}= DA(M); ověření: EA[DA(M)]=M.
1.3 Kanálové kódování Zabezpečení signálu proti chybám vznikajícím při přenosu v komunikačním kanálu (vlivem aditivního rušení, mezisymbolových přeslechů, úniku,..) pomocí zabezpečovacích (bezpečnostních) kódů.
FEC (Forward Error Correction)
ARQ (Automatic Request Repetition)
Kódy FEC opravují: nezávislé chyby (rádiové kanály bez úniku). shluky chyb (telefonní datové spoje, rádiové kanály s únikem). Hammingova vzdálenost dmin dvou značek složených z binárních prvků je počet míst, ve kterých se dvě značky liší.
010 110
010
011
110
111
000 100
001 101
dmin = 1 Lmax
kz
011 111
000 100
010 110
111
001 101
dmin = 1 L < Lmax
011
000 100
001 101
dmin = 2
010 110
011 111
000 100
001 101
dmin = 3
1.3.1 Blokové lineární kódy Využívá se pravidel lineární algebry (maticový a vektorový počet) Hammingovy kódy: typický kód (7,4) (počet všech bitů, počet informačních bitů).
0 0 0 1 1 1 1 H= 0 1 1 0 0 1 1 1 0 1 0 1 0 1
Kóduje se pomocí vHT=0.
0 0 1
c1 c2
a3
c4
a5
a6
vektor značky v a – informační bity c – kontrolní bity
0 0 a7 1 1
1 1 0 0
kontrolní matice transponovaná
0 kontrolní matice HT 1 0 = 0 0 0 1
1 1 0 1 1 1
Příklad: a3 = a5 = a6 = 0, a7 = 1 ⇒ c1 = c2 = c4 = 1 ⇒ značka: 1101001,
Při přenosu vznikne chyba např. na 3. pozici: 1111001.
0 0 1 0 1 0 0 1 1 1 1 1 1 0 0 1 1 0 0 = 0 1 1 1 0 1 1 1 0 1 1 1
Oprava: změní se bit na 3. pozici.
(011)2 = (3)10
1.3.2 Cyklické kódy Využívá se popis pomocí mnohočlenů. Je dána m −1 m−2 1 0 • značka am −1 , am − 2 , K , a1 , a0 → m( x ) = am −1 x + am − 2 x + K + a1 x + a0 x (je-li m(x) značkou kódu je i cyklicky posunutá posl. m´(x) značkou kódu) •
a generující mnohočlen g(x).
Kódování:
z (x ) = x n−m m( x )
1.
Vytvoří se pomocný mnohočlen
2.
Značka kódu c(x), která vznikne z mnohočlenu
(doplnění n - m nul)
z(x) musí být dělitelná
bezezbytku generujícím mnohočlenem g(x).
r (x ) z (x ) (x ) = q{ (x )g (x ) = c(x ) = q(x ) + ⇒ z (x ) + r{ g (x ) g (x ) zbytek podil
Příklad: Kód (7,4) volíme:
g ( x ) = x 3 + x 2 + 1 (1101)
Dána informační posloupnost:
m( x ) = x 2 + 1 ⇒ m = (0101) (a3 = 0, a2 = 1, a1 = 0, a0 = 1)
Vypočte se:
z ( x ) = m( x )x
n−m
} , n − m = 3, z = (0101000)
0101000 : 1101 = 0101 110100 011100 11010 00110 = r(x)
c( x ) = z ( x ) + r (x ) = x 5 + x 3 + x 2 + x, c = z + r = (0101110) Při přenosu vznikne chyba např. na 5. pozici: 0101010.
c( x ) = z ( x ) + r ( x ) = x 5 + x 3 + x (0101010) 0101010 : 1101 = 0101 110100 011110 11010 00100 = r(x) Oprava: přičte se zbytek ke značce: 0101010 + 100 = 0101110.
2.2.5 BCH kódy (Bose, Chaudhuri, Hocquencgham) Cyklické kódy (binární i nebinární) vhodné pro korekci skupinových chyb. použití: v celulárních paketových systémech.
2.2.6 Reedovy – Solomonovy kódy RS Nebinární cyklické BCH kódy. Kódování se neprovádí nad jednotlivými bity, ale nad byty (symboly).
1.3.3 Konvoluční kódy Kodéry konvolučních kódů zpracovávají vstupní posloupnost kontinuálně nikoli blokově.
Vstupní bity Výstupní bity
Kodér konvolučního kódu, k0 = 1, m = 2, n0 = 3 Vstupní posloupnost
1011
c1
c2
c3
Bα
Bβ
Bγ
0
0
0
0
-
-
-
1
1
0
0
1
1
1
2
0
1
0
1
1
0
3
1
0
1
0
0
0
4
1
1
0
0
0
1
000 000 111 000 110 111 001
0
Pro vstupní posloupnost L znaků je na L-té úrovni stromu 2L rozvětvení, ale jen 2m různých stavů, tj. v uvedeném případě 22 = 4 různých stavů ⇒ mřížový diagram.
111
1
110 000 111 001 001 110
Kódový strom
000 111 110 001 111 000 001 110 000 111 110 001 111 000 001 110
Viterbiho dekódování Optimální dekódování: porovnávání přijaté, obecně chybami narušené, posloupnosti prvků se všemi posloupnostmi, které mohly být vyslány. Porovnání je založeno na stanovení věrohodnostního poměru a jeho maximalizaci (maximum likelihood decoding). αβγ 00
000 111
000
000
111
000
111
111
111
10
000 111
111 000 110
110
000 111
111 000 110
000 111
111 000 110
111 000 110
000 110
001
001
01 001 11
c2c3
001
001 001 110
001 110
001 001 110
Mřížový diagram
001 110
001 110
1.4 Přenos v základním pásmu Kódování pro přenos dat v základním pásmu. Základní typy- NRZ (Non Return to Zero), RZ (Return to Zero), fázově kódované, binární dvojúrovňové/víceúrovňové. L=Level, M=Mark, S=Space.
Linkový kód 2B1Q (použití v DSL)
Předchozí úroveň +1 nebo +3
-1 nebo -3
1
Příchozí dibit
Nová úroveň
00
+1
01
+3
2B1Q
10
-1
3
11
-3
00
-1
01
-3
10
+1
11
+3
1
1. dibit
0
1
2. dibit
0
0
3. dibit
1
1
4. dibit
1
0
t
1 t -1
-3
Proč tolik kódů? Různé kódy mají různé specifické vlastnosti: 1. Stejnosměrná složka. Její odstranění umožní střídavou vazbu (AC) mezi obvody (kapacitní, transformátorovou) ⇒ snadnější realizace obvodů. 2. Vlastní synchronizace. Symbolová nebo bitová synchronizace je potřebná pro všechny digitální systémy. Některé kódy tuto informaci přenášejí v každém bitu (Bi-φ-L = Manchester). 3. Šířka pásma. Vhodným kódováním je možné lépe využít použitelné kmitočtové pásmo – přenést více informace v dané šířce pásma. 4. Diferenciální kódování. Tato technologie umožní inverzi kódu (záměna +V a –V) aniž by došlo k chybnému dekódování. 5. Šumová imunita. Některé kódy mají větší odolnost vůči chybám. Vyšší BER (Bit Error Ratio) při daném poměru výkonu signálu k šumu S/N, SNR (Signal to Noise Ratio).
1.5 Modulace Analogové (přenos analogových signálů) AM, FM, PM, QAM Digitální (přenos číslicových signálů) ASK, FSK, PSK, QAM Lineární (s proměnnou modulační obálkou) AM, QAM, ASK Nelineární (s konstantní modulační obálkou) FM, PM, FSK, PSK Harmonický signál: s0(t) = S0cos
Modulovaný signál:
(2πf0t + φ0)
⎤ ⎡t s(t ) = S (t ) cos ⎢ ∫ 2πf (α )dα + ϕ (t )⎥ 0 ⎣1 4442444 3⎦ fázový úhel
Analogové modulace • V praxi používané modulace AM, FM, PM, QAM • Potřebují velký poměr S/N
Digitální modulace (dvoustavové)
•
modulace ASK (Amplitude Shift Keying) - modulace s klíčováním amplitudy nemá S0 ve své základní podobě výhodné vlastnosti
•
modulace FSK (Frequency Shift Keying) - modulace s klíčováním kmitočtu
•
modulace PSK (Phase Shift Keying) - modulace s klíčováním fáze
Tb
Digitální modulace (vícestavové) Počet bitů n, počet stavů M = 2n Zobrazení modulací v rovině IQ (In-phase – synfázní složka, Quadrature – kvadraturní složka) konstelačním diagramem
Zobrazení modulace 16QAM v rovině IQ vektorovým diagramem, časový průběh a spektrum modulačního signálu I(t) a) bez filtru, b) s filtrací symbolů