Druhy rušení v komunikačních kanálech. Hlavní typy rušení a zkreslení v komunikačních systémech. Metody řešení interference

Tento algoritmus(algoritmus LZ77 4 Pojmenováno podle autorů Abrahama Lempela a Jacoba Ziva. Publikováno v roce 1977.) byl jedním z prvních, kdo použil slovník. Posledních N již zakódovaných prvků sekvence je použito jako slovník. Během procesu komprese se slovník podsekvencí posouvá („snímá“) podél vstupní sekvence. Řetězec prvků na výstupu je zakódován následovně: pozice odpovídající části zpracovávaného řetězce prvků ve slovníku - offset (vzhledem k aktuální pozici), délka, první prvek následující za spárovanou částí řetězce. Délka párovacího řetězce je výše omezena číslem n. Úkolem je tedy najít největší řetězec ze slovníku, který odpovídá zpracovávané sekvenci. Pokud nejsou žádné shody, zaznamená se nulový posun, délka jednotky a pouze první prvek nekódované sekvence - (0, 1, e) .

Výše popsané schéma kódování vede ke konceptu posuvné okno (anglicky posuvné okno), skládající se ze dvou částí:

1. podsekvence již zakódovaných prvků délky N - slovník - vyhledávací vyrovnávací paměť(anglický vyhledávací buffer);
2. podposloupnost délky n z řetězce prvků, pro které bude učiněn pokus najít shodu - vyrovnávací paměť náhled (anglicky look-ahead buffer).

V termínech posuvné okno Kompresní algoritmus je popsán následovně: jestliže e 1, . . . , e i je již zakódovaná podsekvence, pak e i-N+1 , . . . , e i je slovník nebo vyrovnávací paměť a e i+1 , . . . , e i+n - vyrovnávací paměť náhledu. Podobně je úkolem najít největší řetězec prvků z náhledového bufferu počínaje prvkem e i+1, který odpovídá řetězci z vyhledávacího bufferu - tento řetězec může začínat od libovolného prvku a končit libovolným prvkem, tzn. překročit vyrovnávací paměť vyhledávání a napadnout vyrovnávací paměť náhledu. Je přirozené jít dál posuvné okno je to zakázáno. Nechť je v posuvném okně nalezena maximální délka odpovídající řetězci prvků ei-p , . . . , e i+q , pak bude zakódováno následovně: (p+1, q+p+1, e i+p+q+2 ) - offset vzhledem k začátku vyrovnávací paměti náhledu (e i+1) , délka shodného řetězce, prvek následující po shodném řetězci z vyrovnávací paměti náhledu. Pokud jsou výsledkem hledání dvě shody stejné délky, vybere se ta, která je nejblíže začátku vyrovnávací paměti náhledu. Poté se posuvné okno posune o p + q + 2 prvky dopředu a postup vyhledávání se opakuje.

Volba čísel N a n je samostatný důležitý problém, protože čím větší N a n, tím více prostoru potřebné k uložení hodnot offsetu a délky. S rostoucím N an n se přirozeně také zvyšuje doba běhu algoritmu. Všimněte si, že N a n se obvykle liší o řád.

Uveďme příklad komprese pomocí tohoto algoritmu. Zkomprimujme řetězec "TOBEORNOTTOBE" s parametry N = 10 an = 3:

Pokud alokujeme 4 bity pro uložení offsetu, 2 bity pro délku a 8 bitů pro prvky, pak bude délka kódované sekvence (bez zohlednění konce označení sekvence) 4 x 8 + 2 x 8 + 8 x 8 = 112 bitů a délka původního bitu bude 102 bat. V v tomto případě sekvenci jsme nezkomprimovali, ale naopak zvýšili redundanci reprezentace. Je to proto, že délka sekvence je pro takový algoritmus příliš malá. Ale například kresba stromu Huffmanova kódu na Obr. 13.1, zabírá 420 kB místo na disku, po kompresi má velikost asi 310 kilobajtů.

Níže je pseudokód pro kompresní algoritmus.

// M - pevná hranice // čtení znaků postupně ze vstupního proudu // in - vstup - komprimovaná sekvence // n - maximální délka chains // pos - pozice ve slovníku, len - délka řetězce // nelem - prvek za řetězcem, str - nalezený řetězec // in - vstup, výstup - výstup // SlideWindow - vyhledávací buffer while(!in.EOF() ) / /když jsou data ( // hledá maximální shodu a její parametry SlideWindow.FindBestMatch(in, n, pos, len, nelem); // zapište výstup: offset, délka, prvek out.Write(pos) ; out.Write(len );Write(nelem // posunutí posuvného okna o délku + 1 prvky SlideWindow.Move(in, len + 1); Výpis 13.2.

kompresní algoritmus LZ77

Dekódování komprimované sekvence je přímé dekódování zaznamenaných kódů: každý záznam je porovnán s řetězcem ze slovníku a explicitně zapsaným prvkem, po kterém je slovník posunut. Je zřejmé, že slovník je znovu vytvořen, když běží dekódovací algoritmus.

Je vidět, že proces dekódování je z výpočetního hlediska mnohem jednodušší. // n - maximální délka řetězce // pos - pozice ve slovníku, len - délka řetězce // nelem - prvek za řetězem, str - nalezený řetězec // in - vstup, výstup - výstup // Dict - slovník while(!in. EOF()) //když jsou data ( in.Read(pos); in.Read(len); in.Read(nelem); if(pos == 0) ( //nové samostatné znak //odstranit ze slovníku (daleko) jeden prvek Dict.Remove(1) //přidat prvek do slovníku Dict.Add(nelem out.Write(nelem); odpovídající řádek ze slovníku str = Dict.Get(pos, len //odstranit len ​​+ 1 prvky ze slovníku Dict.Remove(len + 1) //Přidat řetězec do slovníku Dict.Add(str + nelem); ); napiš.

Výpis 13.3. Algoritmus Tento algoritmus je zakladatelem celé rodiny algoritmů a sám se ve své původní podobě prakticky nepoužívá. Mezi jeho výhody patří slušný stupeň komprese na poměrně velkých sekvencích, rychlá dekomprese a absence patentu 5 dokument poskytující výhradní právo využívat vynález po určitou dobu (obvykle 15-20 let) k algoritmu. Mezi nevýhody patří pomalá rychlost komprese a také nižší kompresní poměr než u alternativních algoritmů (úpravy algoritmu tuto nevýhodu řeší). Kombinace algoritmů Huffman („Algorithms bezztrátové komprese obrazu“) a LZ77 se nazývá metoda DEFLATE 6. Toto se nazývá komprese a dekomprese se nazývá INFLATE (anglicky: DEFLATE - vyfouknout, INFLATE - nafouknout).. Metoda DEFLATE se používá v grafický formát PNG, stejně jako

univerzální formát

Aby se ujistil, že je nutný opakovaný přenos dat, odesílatel očísluje odesílané rámce a pro každý rámec očekává od přijímače tzv. pozitivní potvrzení (ACK) - servisní rámec oznamující, že byl přijat původní rámec a data v něm obsažená. je správné. Aby bylo možné takové číslování organizovat, je zapotřebí logický postup spojení - poskytuje výchozí bod, od kterého číslování začíná. Čekací doba na příjem je omezená - při odesílání každého rámce vysílač spustí časovač, a pokud po stanovené době není přijat kladný příjem, je rámec považován za ztracený. Pokud přijímač obdrží rámec s poškozenými daty, může poslat negativní potvrzení (NACK) - explicitní označeníže tento rám je třeba znovu odeslat.

Existují dva způsoby organizace procesu výměny účtenek: metoda nečinného zdroje a metoda posuvného okna.

Metoda nečinnosti zdroje vyžaduje, aby zdroj, který odeslal rámec, čekal na potvrzení (kladné nebo záporné) od přijímače, než odešle další rámec (nebo zopakuje poškozený). Pokud účtenka do časového limitu nedorazí, je rámec (nebo účtenka) považován za ztracený a jeho přenos se opakuje. Na Obr. 6.6, ale je zřejmé, že v tomto případě je výkon výměny dat nižší, než je potenciálně možné, ačkoliv vysílač mohl odeslat další rámec ihned po odeslání předchozího.

Nejprve musí počkat na příchod kladného potvrzení. (Dále, pokud to nezkresluje podstatu uvažovaného problému, budou pozitivní příjmy pro stručnost nazývány jednoduše „účtenky“.)

Nevýhody této korekční metody jsou patrné zejména na nízkorychlostních komunikačních kanálech, tedy v teritoriálních sítích.

Druhá metoda se nazývá metoda posuvného okna. V tomto způsobu, aby se zvýšila rychlost přenosu dat, je zdroji dovoleno vysílat určitý počet rámců v nepřetržitém režimu, to znamená maximální možnou rychlostí pro zdroj, aniž by přijímal potvrzení pro tyto pakety. Počet paketů, které je povoleno přenášet tímto způsobem, se nazývá velikost okna. Obrázek 6.6b znázorňuje aplikaci tato metoda pro okno o velikosti W paketů.

V počátečním okamžiku, kdy ještě nebyly odeslány žádné pakety, okno určí rozsah paketů s čísly od 1 do W včetně. Zdroj začne vysílat pakety a přijímat potvrzení jako odpověď. Pro zjednodušení předpokládejme, že stvrzenky přicházejí ve stejném pořadí jako pakety, na které jsou odesílány.

korespondovat. V čase t t, kdy je přijata první účtenka Kj, se okno posune o jednu pozici a definuje nový rozsah od 2 do (W + 1).

Procesy odesílání balíků a přijímání účtenek jsou na sobě zcela nezávislé. Uvažujme libovolný okamžik v čase t n, kdy zdroj obdrží potvrzení o paketu s číslem n. Okno se přesune doprava a určí rozsah paketů povolených k přenosu od (n + 1) do (W + n). Celou sadu paketů opouštějících zdroj lze rozdělit do skupin uvedených níže (viz obr. 6.6, b).

Pakety s čísly od 1 do η již byly odeslány a stvrzenky pro ně byly přijaty, to znamená, že jsou mimo okno vlevo.

Pakety začínající číslem (η + 1) a končící číslem (W + n) jsou uvnitř okna a lze je tedy odesílat bez čekání na příchod jakékoli účtenky. Tento rozsah lze rozdělit do dvou dalších podrozsahů:

O paketů s čísly od (η + 1) až m již bylo odesláno, ale potvrzení pro ně ještě nebylo přijato;

O pakety s čísly od m do (W + n) ještě nebyly odeslány, ačkoli to není zakázáno.

Všechny pakety s čísly větším nebo rovným (W + η + 1) jsou mimo okno vpravo, a proto je zatím nelze odeslat.

Posouvání okna po sekvenci čísel paketů je znázorněno na Obr. 6,6, c. Zde t〇 je počáteční okamžik, tļ a t n jsou okamžiky příchodu potvrzení pro první a η-tý paket. Pokaždé, když přijde účtenka, okno se posune doleva, ale jeho velikost se nezmění a zůstane rovna W.

Při odeslání paketu je u zdroje nastaven časový limit. Pokud během této doby účtenka k odeslanému balíku nedorazí, je balík (resp. účtenka k němu) považován za ztracený a balík je odeslán znovu.

Pokud tok příjmů přichází pravidelně v toleranci W paketů, pak směnný kurz dosahuje maximální možné hodnoty pro daný kanál a přijatý protokol.

V některých implementacích posuvných oken se od přijímače nevyžaduje, aby posílal potvrzení pro každý přijatý platný paket. Pokud mezi přijatými pakety nejsou žádné „zúčtování“, pak příjemce potřebuje poslat potvrzení pouze poslednímu přijatý balíček a tato účtenka bude odesílateli indikovat, že všechny předchozí balíčky také dorazily v pořádku.

Jiné metody používají záporné příjmy. Existují dva typy negativních příjmů – skupinové a výběrové. Skupinový příjem obsahuje číslo paketu, od kterého je nutné opakovat přenos všech paketů odeslaných vysílačem do sítě. Selektivní negativní potvrzení vyžaduje opětovné odeslání pouze jednoho paketu.

Metoda posuvného okna má dva parametry, které mohou výrazně ovlivnit efektivitu přenosu dat mezi vysílačem a přijímačem – velikost okna a hodnotu časového limitu příjmu. Volba časového limitu nezávisí na spolehlivosti sítě, ale na zpožděních při přenosu paketů sítí.

Ve spolehlivých sítích, ve kterých jsou pakety zřídka zkresleny a ztraceny, musí být pro zvýšení rychlosti výměny dat zvětšena velikost okna, protože v tomto případě bude vysílač odesílat pakety s menšími pauzami. V nespolehlivých sítích by se měla velikost okna zmenšit, protože při častých ztrátách a zkreslení paketů se objem paketů znovu přenášených sítí prudce zvyšuje, což znamená propustnost Síť je z velké části plýtvána a užitečná propustnost sítě klesá.

Velikost okna může být konstantní parametr algoritmus posuvného okna. V tomto případě se vybere při navázání spojení a během relace se nemění. Existují také adaptivní verze algoritmu, kde se velikost okna během relace mění v souladu s aktuálním stavem sítě a cílového uzlu.

Spolehlivost sítě v takových algoritmech je určena takovými známkami ztráty paketů, jako je vypršení časového limitu pro pozitivní příjem nebo příchod duplicitního příjmu pro určitý paket. Duplikát označuje, že cílový uzel vypršel při čekání na další paket a uzel požaduje, aby byl tento paket odeslán podruhé. Když k takovým událostem dojde, uzel odesílatele zmenší velikost okna a pokusí se najít optimální režim přenos dat.

Velikost okna lze také změnit podle cílového uzlu. Důvodem zmenšení velikosti okna je přetížení cílového uzlu, který nestíhá zpracovávat příchozí pakety. K této problematice se vrátíme později v části Zpětná vazba„Kapitola 7, kde budeme studovat metody řešení přetížení.

Existují také implementace metody posuvného okna, které jako velikost okna používají spíše počet bajtů než počet paketů. Většina slavný příklad Tento přístup je protokol TCP.

V obecný případ Metoda posuvného okna je složitější na implementaci než metoda nečinného zdroje, protože vysílač musí uložit do vyrovnávací paměti všechny pakety, pro které ještě nebyla přijata kladná potvrzení. Při použití této metody je navíc nutné sledovat několik parametrů algoritmu: velikost okna W, číslo paketu, pro který byla přijata účtenka, počet paketů, které lze ještě odeslat před přijetím nové účtenky .

Více k tématu Retransmise a posuvné okno:

1. § 29 Přechod a přechod práv ze závazků. – Římská konstrukce práva převodu. – Usnadnění převodu podle nejnovějších právních předpisů. – Přenosový nápis. – Přenosová omezení. – Přenosová akce. – Odpovědnost převodce a práva nabyvatele. – Vstup do práva nebo subrogace věřitele. – Ruské právo přenosu. – Převod zápůjčních dopisů. – Převod pohledávek na věřitele.

Jednou z nejpřirozenějších technik používaných k organizaci spolehlivého přenosu je potvrzení. Odesílatel odešle data a čeká, až obdrží potvrzení o tom, že jeho data bezpečně dorazila k příjemci. V TCP protokol použitý speciální případ handshake - algoritmus posuvného okna. Než přistoupíme k podrobnému zvažování implementačních vlastností tohoto algoritmu v protokolu TCP, je velmi užitečné o něm diskutovat z obecné perspektivy.

Existují tedy dvě metody pro organizaci procesu výměny účtenek: metoda nečinného zdroje a metoda posuvného okna.

Metoda výpadek zdroje vyžaduje, aby zdroj odesílající rámec (v tomto případě nezáleží na tom, jaké jméno je použito pro jednotku přenášených dat) čekal na příjem od přijímače, který uvádí, že původní rámec byl přijat a data v něm jsou správná, a teprve poté odešle další snímek (nebo opakovaný zkreslený). Pokud účtenka do časového limitu nedorazí, je rámec (nebo účtenka) považován za ztracený a jeho přenos se opakuje. Na Obr. Obrázek 17.10 ukazuje, že druhý rámec je odeslán až po obdržení potvrzení o doručení prvního rámce.

Rýže. 17.10. Metoda nečinnosti zdroje

Poté však nastala dlouhá pauza ve vysílání dalšího třetího framu. Během této pauzy byl zdroj nucen opakovat přenos snímku 2, protože potvrzení o jeho první kopii bylo ztraceno. Je jasné, že s takovým algoritmem pro zdrojovou operaci musí být přijímající strana schopna rozpoznat duplicitní snímky a zbavit se jich.

Je zcela zřejmé, že při použití této metody je výkon výměny dat nižší, než je potenciálně možné - vysílač by mohl vyslat další rámec ihned po odeslání předchozího, ale musí počkat, až dorazí příjemka.

Druhá metoda se nazývá metoda posuvné okno(posuvné okno). V tomto způsobu, aby se zvýšila rychlost přenosu dat, je zdroji povoleno vysílat určitý počet rámců v nepřetržitém režimu, to znamená při maximální možné rychlosti pro zdroj. dokud nebudou obdrženy účtenky za tyto rámy. Je volán počet rámců, které je povoleno přenášet tímto způsobem velikost okna.

Obrázek 17.11 ukazuje použití této metody pro okno s 5 snímky.

Rýže. 17.11. Metoda posuvného okna

V počátečním okamžiku, kdy ještě nebyly odeslány žádné snímky, okno definuje rozsah čísel snímků od 1 do 5 včetně. Zdroj začne vysílat rámce a po nějaké době obdrží jako odpověď potvrzení. Pro jednoduchost předpokládejme, že účtenky přicházejí ve stejném pořadí (ale ne nutně stejným tempem), jako snímky, kterým odpovídají. V okamžiku, kdy odesílatel obdrží potvrzení 1, okno se posune o jednu pozici nahoru a definuje nový rozsah rámců povolených k odeslání (od 2 do 6).

Procesy odesílání balíků a přijímání účtenek jsou na sobě zcela nezávislé. V našem příkladu odesílatel pokračuje v přenosu rámců, ale nějakou dobu za ně nedostane potvrzení. Po přenosu snímku 6 je okno vyčerpáno a zdroj pozastaví vysílání.

Po obdržení příjmu 2 (pro snímek 2) se okno posune o jeden nahoru a definuje rozsah snímků povolených pro přenos od 3 do 7. Dojde k podobnému „posunutí“ okna nahoru po obdržení každé účtenky: okno se posune o 1 nahoru, ale jeho velikost se nezmění a zůstane rovno 5. Po obdržení účtenky 8 se okno objeví v rozsahu od 9 do 13 a zůstane tak poměrně dlouho, protože z nějakého důvodu zdroj přestane dostávat rámce potvrzení doručení. Po odeslání posledního povoleného rámce 13 vysílač opět zastaví vysílání, aby jej obnovil po přijetí příjmu 9.

Při odeslání rámce je u zdroje nastaven časový limit. Pokud pro nastavit čas Pokud potvrzení pro odeslaný rámec nedorazí, pak je rámec (nebo jeho potvrzení) považován za ztracený a rámec je přenesen znovu. Pokud tok příjmů přichází pravidelně v toleranci 5 snímků, pak směnný kurz dosahuje maximální možné hodnoty pro daný kanál a přijatý protokol.

Obecně je implementace metody posuvného okna složitější než metoda nečinného zdroje, protože vysílač musí ukládat do vyrovnávací paměti kopie všech rámců, pro které ještě nebyly přijaty příjmy. Kromě toho je při použití této metody nutné sledovat několik parametrů algoritmu, jako je velikost okna, číslo rámce, pro který byla přijata účtenka, a číslo rámce, které lze před přijetím nové účtenky ještě odeslat.