Kompresia navigačných tabuliek vo Walshovom základe C.B. Pašencov
Plavebná fakulta MSTU, Katedra navigácie
Anotácia. Príspevok uvažuje o možnosti využitia funkčnej bázy Walsh-Paley pre kompresiu lineárnych a pravouhlých tabuliek. Všetky vzorce potrebné na to sú uvedené a skutočný účinok kompresie informácií je demonštrovaný na niekoľkých príkladoch. Metódu je možné použiť ako na predbežnú kompresiu informácií, tak aj na ich spracovanie v reálnom čase.
Abstraktné. V práci bola zvážená možnosť použitia funkčnej základne Wolsh-Paly pre lineárne a pravouhlé lisovacie stoly. Všetky vzorce, ktoré sú na to potrebné, sú uvedené a skutočný efekt kompresie informácií bol ukázaný na niekoľkých príkladoch. Metódu je možné použiť ako na predbežnú kompresiu informácií, tak aj na ich spracovanie v reálnom čase.
1. Úvod
Mnohé automatické a automatizované zariadenia súvisiace s navigáciou využívajú tabuľkové údaje uložené v pamäti rozhodovacích zariadení a podľa potreby sa z nej vyberajú. V tomto prípade sa spotrebúva najdôležitejší zdroj – pamäť a vzorkovanie z nej spotrebúva ešte dôležitejší zdroj – čas, ovplyvňujúci výkon celého systému spracovania informácií. Preto sú dôležité akékoľvek metódy, ktoré znižujú objem úložiska. Jednou z takýchto metód môže byť metóda kompresie tabuľkovej informácie v dôsledku jej spektrálneho rozkladu v nejakej funkčnej báze. V momente spotreby sa hodnota funkcie obnoví inverznou transformáciou. V porovnaní s Fourierovou expanziou je výhodnejšie použiť na expanziu Walshovu bázu, keďže pre plynulé funkcie majú koeficienty Walshovej expanzie tendenciu rýchlejšie nulovať. To umožňuje väčší stupeň kompresie informácií na Walshovom základe. Okrem toho obnovenie hodnôt tabuľky na základe Walsh vyžaduje menej času. Je to spôsobené jednoduchším výpočtom Walshových funkcií v porovnaní s výpočtom goniometrických funkcií. Ak sú tieto funkcie generované v hardvéri, potom je prínos z používania funkcií Walsh ešte väčší, pretože ich možné hodnoty +1 a -1 sú ľahko implementované výpočtovými zariadeniami. Práca na numerických príkladoch ukazuje výhody použitia Walshovej bázy pre určité typy hladkých funkcií a tabuľkových údajov. Výpočtový proces je založený na programoch pre rýchle Fourierove a Walshove transformácie napísaných autorom a porovnaní výsledných spektier.
2. Teoretické základy kompresie
Všeobecné teoretické princípy, na základe ktorých sa transformácia uskutočňuje vo vybranom funkčnom základe, sú dobre známe (Gold, Ryder, 1993; Trakhtman A., Trakhtman V., 1978). Je potrebné zvýrazniť diskrétne transformácie, keď je pôvodný číselný rad konečný. Keďže hovoríme o kompresii tabuľky, t.j. o fundamentálne konečný rad čísel, ďalej budeme hovoriť len o diskrétnych transformáciách. Ak je daný rad N čísel
X2, Xk, , XN (1)
potom by mal byť funkčný základ vybraný z konečnej množiny N funkcií
Fa(X), a= 1, 2,„., N, (2)
existujúce na množine bodov Xk. Potom diskrétna transformácia v tomto základe poskytne presne N koeficienty Ca, Koropbie sa zistí pomocou formálneho súčtu:
C„ = ЪкХк Fa(Хк), а= 1, 2,„„ N. (3)
Súbor N koeficientov Ca predstavuje diskrétnu reprezentáciu množstva čísel (1) v
funkčný základ (2). Často sa táto množina Ca čísel nazýva čiarové spektrum vo vybranom základe. Iná interpretácia expanzie (3) je považovať ju za lineárnu transformáciu pôvodného súradnicového systému Xk. Koeficienty Ca sa potom stanú súradnicami v novom súradnicovom systéme 0JX). Ak je spektrum (množina koeficientov Ca) známe, sériu čísel, ktoré ho vygenerovali, možno obnoviť až po chyby vo výpočte pomocou inverznej diskrétnej transformácie.
Xk = (1/N) T.aCa0JXk), k = 1, 2,..., N. (4)
Pre platnosť jednoduchých a takmer symetrických transformácií (3) a (4) je potrebné, aby množina bázových funkcií mala vlastnosti ortogonality a určitej normalizácie. Podmienka ortogonality vyzerá ako množina rovnosti
Zk Фр(Хк) Ф(Хк) = 0, р Ф q, (5)
a normalizačné podmienky sú ako súbor rovnosti
Zk ФрХк) Фр(Хк) = Ек Фр\Хк) = 1. (6)
Okrem toho sa systém základných funkcií nazýva úplný, ak nie je možné špecifikovať viac ako jednu funkciu, ktorá je ortogonálna ku všetkým funkciám bázy.
Je zrejmé, že pri tejto formulácii otázky nedochádza ku kompresii, pretože počet členov pôvodného radu a počet spektrálnych koeficientov sú rovnaké. Možnosť komprimácie informácií sa objaví, ak počet spektrálnych koeficientov môže byť menší ako N. Napríklad, keď sa niektoré spektrálne koeficienty rovnajú nule alebo sú jej blízke. Potom môžu byť tieto koeficienty zanedbané a výsledné spektrum bude kratšie. V prvom prípade, keď zanedbáme len nulové koeficienty spektra, sa obnoví pôvodný rad čísel až po chyby výpočtu. Ak zanedbáme spektrálne koeficienty, ktoré sa k uvedenému stupňu blížia k nule, tak rekonštruované hodnoty pôvodnej série budú zahŕňať nielen chyby vo výpočtoch, ale aj chyby z nepresného znázornenia spektra. Čím väčšia je chyba pri rekonštrukcii členov pôvodnej série we flonyœaeM, TeM, tým väčší počet spektrálnych koeficientov možno zanedbať.
Ak n označíme počet spektrálnych koeficientov, ktoré sme zanedbali, tak pomer v percentách
sq = (n/N) -100 % (7)
možno nazvať mierou kompresie pôvodnej informácie. V tomto prípade to skutočne reprezentujeme s N-n koeficientmi spektra namiesto N hodnôt pôvodnej série. Pri sq = 0 sa kompresia vôbec nevyskytuje a pri sq = 100 % dosahuje hraničnú hypotetickú hodnotu. Skutočné prípady sa pohybujú od 0 % do 100 %.
Praktická stránka realizácie tejto myšlienky je o niečo zložitejšia. Ak sú konečné (konečné) spektrálne koeficienty nulové alebo malé na uvedený stupeň, potom nie je ťažké ich n vyradiť a tým dosiahnuť kompresiu sq.
Ak medzi koeficientmi spektra existuje nula alebo blízko k nule v danom stupni, ale nie sú konečné, potom vzniká problém pri reprezentácii takéhoto spektra z hľadiska kompresie informácií. V tomto prípade je potrebné buď uviesť všetky koeficienty spektra, vrátane nuly a blízko nich, a potom nenastane kompresia. Alebo špecifikujte skupiny nulových spektrálnych koeficientov číslom počiatočného prvku v skupine a počtom prvkov skupiny. To prirodzene znižuje stupeň kompresie pôvodného radu čísel. Ak nulové prvky spektra nie sú konečné alebo netvoria skupiny a ich počet neodhaľuje jednoduchý vzor, potom sa kompresia informácií týmto spôsobom nedosiahne.
Takže možnosť kompresie informácie a stupeň jej kompresie závisí tak od samotného číselného radu (1), ako aj od súboru funkcií (2), ktoré tvoria základ spektrálneho rozkladu Ca. Keďže je nám daný rad čísel Xk, môžeme ovládať stupeň kompresie zmenou základu spektrálneho rozkladu. Ale so zvoleným základom Ф(х) povaha danej informácie ovplyvní obe
možnosti kompresie a stupeň kompresie. Existuje pomerne veľa funkčných základov, ktoré sa úspešne používajú na rôzne úlohy prezentácie informácií. Medzi najznámejšie patria bázy mocninných funkcií a ich polynómové varianty v podobe Čebyševových a Legendreových polynómov, ako aj bázy Kravčuka, Charliera a Meissnera. Najznámejší je však základ goniometrických funkcií:
sin(2nax) a с s(2n«x), (7)
alebo zodpovedajúca exponenciálna báza v komplexnej forme:
exp(-j 2nax). (8)
V tomto prípade je spektrum Ca koeficientov spektrom v jeho obvyklom fyzikálnom zmysle ako súbor amplitúd určitého súboru frekvencií obmedzeného rozsahu a určitého frekvenčného rozlíšenia. Keďže v tomto prípade už bol základ vybraný, možnosti kompresie sú teraz spojené len s povahou zdrojovej informácie. Ak je svojou povahou adekvátna zvolenému základu (8), t.j. pozostáva z lineárnej kombinácie konečného počtu periodických funkcií, potom bude spektrum obsahovať len konečný počet nenulových koeficientov a vzniká možnosť kompresie informácií.
3. Funkčný systém Walsh-Paley
Ak je počiatočná informácia inej povahy, napríklad sa mení podľa mocniny, exponenciálneho alebo logaritmického zákona, potom v spektre nie sú všetky jej koeficienty dostatočne malé a kompresia je buď nemožná, alebo je stupeň kompresie malý. V týchto prípadoch je rozumné použiť iný funkčný základ. Keďže pre iné bázy neexistuje jasné fyzikálne znázornenie spektra, môžeme (2) interpretovať ako vzorce na prechod zo súradnicového systému Xk do iného súradnicového systému Fa(X). Ak sa niektorý z koeficientov rovná nule, znamená to, že vektor určený súradnicami v tvare pôvodného radu čísel sa v novom súradnicovom systéme nachádza v nadrovine súradníc rozmeru N-n. Medzi existujúcimi možnosťami existuje niekoľko báz generovaných funkciami Rademacher pre Z e (0,1):
R0(z) = 1, Rk(z) = znamienko (sin (2k nz)), k = 1,2,..., (9)
ktoré v súlade s funkciou sign() v nich obsiahnutou nadobúdajú iba dve hodnoty: +1 alebo -1.
Systém funkcií (9) je ortogonálny a normalizovaný, ale nie je úplný. K nemu môžeme pridať funkcie tvaru znak(cos2knz), ktoré sú tiež ortogonálne k funkciám systému (9). Preto sa na základe reprezentácií (9) tvoria ďalšie ucelené systémy využívajúce produkty Rademacherových funkcií a zavádzajúce do takto získaných nových funkcií určité usporiadanie.
Najzaujímavejší pre navigačné aplikácie z hľadiska kompresie informácií je funkčný systém Walsh-Paley. Vznik tohto systému úzko súvisí s binárnymi číslami jeho základných funkcií. Konkrétne Walshova-Paleyova funkcia s číslom a je súčinom Rademacherových funkcií s číslami tých binárnych bitov a, v ktorých sa nachádza 1. Ak číslo a zapíšeme v binárnej reprezentácii s n = log N bitov
a = Zk 2k-1 ak, (10)
potom môžu byť funkcie systému Walsh-Paley reprezentované takto:
Wa(z) = Pk M. Samotné číslo môže byť reprezentované podobne ako (12) v binárnom tvare:
) = Ek2k-l]k. (15)
Potom bude systém funkcií Walsh-Paley konečne predstavený vo forme
YaGa)/Sh = WJ (a/K) = (-1)"as1""k + \ (16)
ktorý sa používa vo všetkých nasledujúcich výpočtoch. Softvérová funkcia WolshPaly() v jazyku Pascal na generovanie Walsh-Paleyho funkcií pomocou vzorcov (16) je uvedená nižšie. Pre N = 8 sú hodnoty Walsh-Paleyových funkcií No (/) uvedené v tabuľke. 1.
Tabuľka 1. Hodnoty funkcie Walsh-Paley pre N = 8
] 0 1 2 3 4 5 6 7
0 1 1 1 1 1 1 1 1
Bez rozoberania detailov jednoducho spomenieme existenciu systémov Hadamardových a Harmuthových funkcií, ktoré sa od podrobne uvažovaného Walsh-Paleyho systému funkcií líšia len spôsobom, akým organizujú rovnaké funkcie. Je to poradie Walsh-Paleyových funkcií, ktoré poskytuje najväčší počet konečných koeficientov spektra, ktoré sú v danom stupni nulové alebo blízke nule.
4. Konvergencia Walsh-Paleyovho radu
Walshove funkcie majú množstvo užitočných vlastností, medzi ktorými uvádzame vlastnosť symetrie používanú pri výpočtoch:
Shch (a/Shch. (17)
Binárna reprezentácia čísel Walshových funkcií s n = logN bitov určuje poradie p a poradie r funkcie. Poradie je najväčšie číslo dvojkovej číslice, ktoré sa rovná 1. Hodnosť funkcie je počet nenulových dvojkových číslic, napríklad Walshova funkcia s číslom a = 9 pre N = 16 an n = 4 je reprezentované v binárnom tvare ako 1001, a preto jeho poradie g = 2 (dva
nenulové číslice) a poradie p = 3 (najvýznamnejšia nenulová číslica je tretia, keďže počítanie začína od nuly). Ak funkcia s číslom a má hodnosť r, potom jej číslo môže byť reprezentované ako:
a (R = r) = 2M1 + 21"2 + ... + 2Mg, (18)
kde tsk (k = 1, 2,..., r) sú počty nenulových bitov binárnej reprezentácie čísla a. Napríklad číslo 9 môže byť reprezentované ako 23 + 20, berúc do úvahy binárnu reprezentáciu 1001. Priamo pre problém kompresie pôvodnej informácie, rýchlosť, akou expanzné koeficienty Ca vo Walshovej báze klesá, ako číslo zvýšenie je dôležité. Ak má funkcia reprezentovaná radom (1) spojitú deriváciu až do tohto rádu a maximálna hodnota modulu derivácie |A"(m)| je M, potom koeficienty spektra s číslami a, ktorých poradie nie je menší ako rád derivácie (r > áno), spĺňa nerovnosť (Design of special..., 1984):
| Ca(g>w) |< М/ 2ш(ш+3)/2. (19)
Práve táto dôležitá nerovnosť zaručuje rýchlu konvergenciu spektrálnych koeficientov Ca so zvyšujúcim sa číslom a a otvára vyhliadky na kompresiu tabuľkových informácií. V skutočnosti sa poradie r Walshovej funkcie zvyšuje s číslom funkcie a, takže podmienka r > w je splnená pre veľké čísla a. To znamená, že odhad (19) sa vzťahuje na konečné koeficienty expanzie.
Tabuľka 2. Koeficienty spektrálnej expanzie mocninových funkcií na Walshovej báze
STUPEŇ FUNKCIE PORADIA
0 0 4.68 3.03 2.20 1.37
1 0 -2.50 -2.34 -1.96 -1.34
2 1 -1.25 -1.17 -1.10 -0.95
3 1 0 0.63 0.88 0.92
4 2 -0.63 -0.59 -0.56 -0.52
5 2 0 0.31 0.44 0.49
6 2 0 0.16 0.22 0.31
7 3 0 0 -0.12 -0.29
8 3 -0.31 -0.29 -0.28 -0.26
9 3 0 0.16 0.22 0.25
10 3 0 0.08 0.11 0.15
11 3 0 0 -0.06 -0.15
12 3 0 0.04 0.05 0.08
13 3 0 0 -0.03 -0.07
14 3 0 0 -0.01 -0.04
15 3 0 0 0 -0.03
od % 43,8 18,8 6,3 0
Ak má funkcia navyše konečný počet nenulových derivácií (napríklad mocninová funkcia), potom sú všetky koeficienty s číslami, ktorých poradie je väčšie ako táto mocnina, zhodne rovné nule. Na to je však potrebné, aby číslo N bolo dostatočne veľké a poradie sa „podarilo“ zvýšiť ako číslo najvyššej derivácie. Ako príklad uvažujme spektrálne rozšírenie mocninovej funkcie reprezentovanej sériou (1), s počtom vzoriek rovným 16 (^ = 16, n = 4). Malý počet vzoriek bol vybraný len kvôli prehľadnosti výsledkov príkladov. Vyššie v tabuľke. 2 sú zaokrúhlené na dve číslice koeficienty spektrálnej expanzie pre rôzne mocninné funkcie: lineárny, kvadratický, kubický a piaty stupeň - so súčasným uvedením čísla a spektra a jeho poradia r.
Tento príklad ukazuje, že čím nižší je stupeň funkcie, ktorá generuje sériu čísel (1), tým väčší stupeň kompresie ods možno dosiahnuť počas expanzie. Ak je rad krátky a stupeň je veľký, kompresia sa vôbec nedosiahne, ako sa to stáva pri piatom stupni funkcie. Ak pre rovnaký stupeň funkcie zvýšime počet členov radu a následne počet spektrálnych koeficientov, potom stupeň
kompresia rastie. Takže pri N = 64 sq = 7,8 %, pri N = 128 sq = 18,0 %, pri N = 256 sq = 23,8 %.
Len mimochodom poznamenajme, že v prípade Fourierovho spektra sa ani v jednom z uvedených prípadov nedosiahne kompresia - nevhodnosť trigonometrickej bázy pre mocninné funkcie je zrejmá.
4. Základné vzorce pre diskrétnu Walsh-Paleyovu transformáciu
Väčšinou hovoríme o reprezentáciách danej funkcie vo vybranej báze, ale pri práci s diskrétnou spektrálnou transformáciou máme do činenia s množinou jej diskrétnych hodnôt. Tieto diskrétne hodnoty sú reprezentované sériou čísel (1).
Ako funkčný základ teda zvolíme systém Walsh-Paleyových funkcií (16) a predstavíme pre tento systém základné vzorce vyjadrujúce vlastnosti ortogonality a normalizácie funkcií v tomto systéme a transformačné vzorce preň:
Vzorec pre priamu diskrétnu Walshovu transformáciu na získanie spektra
Ca = (1/N) ZkXkWa(k/N).
Vzorec pre inverznú diskrétnu Walshovu transformáciu na obnovenie pôvodného radu hodnôt
Xk = EaCaWa(k/N).
Podmienka ortogonality a normalizácie Walshových funkcií na diskrétnej množine bodov
Nie = (1/N)Zk Wp(k/N) W(k/N) = 0, ak p Ф q a Nie = 1, ak p = q. Parsevalova rovnosť
(1/N) ZkXk2= ЪаСа,
čo predstavuje rovnosť štvorcového modulu vektora v pôvodnom Xk a novom Ca súradnicovom systéme.
5. Prvky implementácie softvéru
Práve tento súbor vzorcov použil autor ako základ pri zostavovaní programu v jazyku Pascal na porovnávaciu analýzu výsledkov diskrétnych Fourierových a Walshových transformácií (certifikát pre softvérový produkt ROSAPO č. 950347 zo dňa 10.02.1995). V tomto prípade boli diskrétne transformácie implementované ako rýchle Fourierove transformácie (FFT) a Walshove transformácie (WTF) so základom 2 a časovou decimáciou (Rabinder a Gold, 1978). Pri kompresii tabuľkových informácií to nevadí, keďže transformácia sa v tomto prípade vykonáva jednorazovo, ale je to veľmi dôležité pri spracovaní informácií v reálnom čase, aby bolo možné spustiť väčší počet rôznych číselných radov (tabuľky, funkcie ) v minimálnom čase. Podobný program, prakticky bez zmien, bol úspešne použitý pri prevádzkovej spektrálnej analýze na palube lietajúceho laboratória IL18-DORR PINRO. Dve hlavné časti tohto programu sú uvedené nižšie. Toto je rýchly postup Walshovej transformácie a funkcia na výpočet hodnoty Walshovej funkcie s číslom a argumentom. Celý program zaberá príliš veľa miesta, a preto tu nie je zahrnutý.
Funkcia WolshPaly(Alf, l: integer) : integer; var J, K, x, y, w, maskl, mask2: celé číslo; začať
w:=l; maska1:=l; maska2:=N div 2; pre K:=0 až N-l začať
if (Alf a maska2)<>0 a (ja a maska1)<>0 potom w:=-w; maska1:=maska1*2; maska2:=maska2 div 2; koniec;
WolshPaly:=w; koniec;
Táto funkcia má dva parametre – číslo Alf a argument I Walshovej funkcie a vracia hodnotu samotnej Walshovej funkcie.
Postup FastWolshTrans(var ml, m2, m3, m4: masdat); var L, LE, LE1, I, J, IP: celé číslo; T1,T2: skutočné;
beginLE:=1; pre L:=1 až M začnite LE1:=LE; LE:=LE*2;
pre J:=1 až LE1 začínajú I:=J; opakuj IP:=I+LEl; T1:=m1; T2:=m2;
Ak L=M, tak začnite
m3:=ml[I]-T1; m4:=m2[I]-T2; m3[I]:=m1[I]+T1; m4[I]:=m2[I]+T2;
m1:=ml[I]-T1; m2:=m2[I]-T2; m1[I]:= m1[I]+T1; m2[I]:=m2[I]+T2;
I:=I+LE; až do I>N; koniec; koniec;
/* "D" - znamienko priamej konverzie */
ak TIP="D" then begin for L:=1 až N do begin m3[L]:=m3[L]/N; m4[L]:=m4[L]/N; koniec;
Procedúra vykonáva rýchlu Walshovu transformáciu údajov, ktoré sa odovzdávajú procedúre v poliach ml a m2. Výsledok transformácie - Walshovo spektrum - je vrátený procedúrou v poliach m3 a m4. Ak sa údaje prenesú do procedúry v normálnom poradí, výsledok sa vráti v binárnom invertovanom poradí. Ak chceme získať obvyklé poradie spektrálnych koeficientov, potom by pôvodné dáta na spracovanie mali byť binárne invertované. Binárna inverzia čísla je číslo, v ktorom je obrátené poradie jeho dvojkových číslic, napríklad inverzia čísla 6 = 110 je 3 = 011. Na invertovanie ľubovoľných čísel je navrhnutý postup v jazyku Pascal:
Procedure MASINVERSION(sw: integer; var m1, m2: masdat); var I, J, K, NV2: celé číslo; T: skutočný; begin NV2:=N div 2;
pretože I:=1 až N-1 začínajú
Ak ja inak začať K:=NV2; zatiaľ čo K 6. Komprimujte tabuľky s dvoma argumentmi Transformácie a kompresie jednorozmerných lineárnych tabuliek boli diskutované vyššie. Ale väčšina tabuliek používaných v navigácii sú dvojrozmerné – obdĺžnikové matice. Otázku ich kompresie je možné riešiť dvoma spôsobmi. Prvým spôsobom je transformovať tabuľku ako lineárnu, berúc do úvahy, že je tvorená postupným umiestňovaním riadkov maticovej tabuľky, začínajúc prvým riadkom. Táto cesta je celkom bežná, pretože takto sa ukladá dvojrozmerné pole v lineárne organizovanej pamäti počítača. Výhodou tejto metódy je, že veľkosť takejto lineárnej tabuľky bude dostatočne veľká, aby bolo možné očakávať efektívnu kompresiu. No skrývajú sa v nej aj potenciálne úskalia. Po zoradení riadkov matice určite dostaneme skoky vo funkcii pri prechode z konca jedného riadku na začiatok nasledujúceho. Tento problém sa dá obísť zmenou poradia prvkov v každom párnom riadku – invertovaním tohto radu. V súlade s tým sa zmení poradie spektrálnych koeficientov. To to však neskomplikuje, ale zmení iba poradie čísel pri obnove hodnôt samotnej funkcie. Ak teda číslo hodnoty obnovenej funkcie bolo Npq = (p - 1) M + q, kde p je číslo riadku s počtom M prvkov v ňom a q je číslo stĺpca, potom po prevrátením pre párne riadky sa toto číslo bude rovnať (p - 1) M + (M- q + 1). Druhým spôsobom je najprv spektrálna transformácia riadkov tabuľky a potom transformácia výsledného stredného spektra pozdĺž stĺpcov. Nevýhodou tejto metódy je nízky kompresný pomer v dôsledku krátkej dĺžky riadkov a stĺpcov. Pravda, efekt kompresie je posilnený dvojitou konverziou riadkov aj stĺpcov. Ak sú napríklad riadky a stĺpce stlačené iba o 10 %, celkový efekt kompresie bude 1 – 0,9 x 0,9 = 0,19 = 19 %. Ak sa napríklad riadky tabuľky menia podľa kvadratického zákona a stĺpce podľa kubického zákona, potom celkový efekt kompresie podľa údajov tabuľky. 2 sa rovná 1-(1-0,188)x(1-0,63) = 0,24 = 24 %. Ako konkrétny príklad uvádzame výsledky transformácie tabuľky Laplaceovej integrálnej funkcie (Kondrashikhin, 1969), ktorá sa používa v navigácii pri hodnotení spoľahlivosti navigácie. Tu je prezentovaný vo forme matice 30x10, t.j. pozostáva z 30 riadkov a 10 stĺpcov. Nemá zmysel previesť ho ako dvojrozmerný: v riadkoch je príliš málo (10) prvkov. Preto ju transformujeme ako lineárnu tabuľku 300 hodnôt. V príklade budeme predpokladať, že existuje 256 = 28 hodnôt. Tabuľku by sme však mohli doplniť nulami a považovať počet hodnôt za 512 = 29. V oboch prípadoch dostaneme rovnaký výsledok: konečné číslo núl so stupňom blízkosti k nule rádovo 0,01 % z maxima je koeficient 46,5 %. Obnovenie funkcie zo sady spektrálnych koeficientov komprimovaných na 53,5 % poskytlo chyby: stredná kvadratúra 0,005 a maximum 0,057. Príklad ukazuje efektívnosť transformácie tabuľky. 7. Záver Vykonané štúdie súvisiace s výberom Walsh-Paleyho funkčnej bázy ukazujú, že túto funkčnú bázu možno úspešne použiť v rôznych systémoch spracovania informácií, ktoré nemajú výrazne periodický charakter. V tomto prípade sú výhody takejto funkčnej bázy oproti Fourierovej báze zrejmé. Okrem toho základ Walsh-Paley poskytuje dobrý účinok pri komprimácii informácií. Ilustruje to príklad Laplaceovej integrálnej tabuľky funkcií, ktorá je typická pre problémy so spoľahlivosťou navigácie, kde efekt kompresie dosiahol 53,5 %. Literatúra Gold B., Rader Ch. Digitálne spracovanie signálu. M., Sov.radio, 367 e., 1993. Kondrashikhin V.T. Teória chýb. M., Transport, 256 e., 1969. Návrh špecializovaných informačných a výpočtových systémov. Ed. Smirnova Yu.N. M., Higher School, 359 e., 1984. Rabinder L., Gold B. Teória a aplikácie číslicového spracovania signálov. M., Mir, 528 e., 1978. Trakhtman A.N., Trakhtman V.A. Úvod do všeobecnej spektrálnej teórie signálov. M., Sov.radio, 312 e., 1978. Walshove funkcie sú rodinou funkcií, ktoré tvoria ortogonálny systém s hodnotami iba 1 a -1 v celej doméne definície. V princípe môžu byť Walshove funkcie reprezentované v spojitej forme, ale častejšie sú definované ako diskrétne postupnosti prvkov. Skupina Walshove funkcie tvoria Hadamardovu maticu. Walshove funkcie sú široko používané v rádiovej komunikácii, kde sa používajú na implementáciu kódového delenia MA (CDMA), napríklad v celulárnych štandardoch ako IS-95, CDMA2000 alebo UMTS. Systém Walshových funkcií je ortonormálny základ a v dôsledku toho umožňuje rozšíriť signály ľubovoľného tvaru do zovšeobecneného Fourierovho radu. Zovšeobecnením Walshových funkcií na prípad viac ako dvoch hodnôt sú Vilenkin-Chrestensonove funkcie. Nech je Walshova funkcia definovaná na intervale ; mimo tohto intervalu sa funkcia periodicky opakuje. Predstavme si bezrozmerný čas . Potom Walshova funkcia očíslovaná k je označená ako . Číslovanie funkcií závisí od spôsobu zoradenia funkcií. Existuje Walshovo usporiadanie - v tomto prípade sú funkcie označené tak, ako je opísané vyššie. Paleyho objednávky sú tiež bežné ( ) a Hadamard ( ). Čo sa týka momentu Walshove funkcie možno rozdeliť na párne a nepárne. Sú označené ako A resp. Tieto funkcie sú podobné ako trigonometrické sínusy a kosínusy. Vzťah medzi týmito funkciami je vyjadrený takto:
Existuje niekoľko spôsobov formovania. Zoberme si jednu z nich, najnázornejšiu: Hadamardovu maticu možno vytvoriť rekurzívnou metódou zostrojením blokových matíc pomocou nasledujúceho všeobecného vzorca:
H_(2^(n-1)) & H_(2^(n-1)) \\ H_(2^(n-1)) & -H_(2^(n-1)) \end(bmatica) Takto možno vytvoriť Hadamardovu maticu dĺžky :
1\end(bmatica)
1 & 1 \\ 1 & -1 \end (bmatica)
1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end(bmatica) Každý riadok Hadamardovej matice je Walshova funkcia. V tomto prípade funkcie objednáva Hadamard. Číslo Walshovej funkcie sa vypočíta z čísla Hadamardovej funkcie preusporiadaním bitov v binárnom zápise čísla v opačnom poradí, po čom nasleduje konverzia výsledku z Grayovho kódu. Výsledkom je Walshova matica, v ktorej sú funkcie usporiadané podľa Walsha:
1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \\ 1 & -1 & 1 & -1 \end(bmatica) Výkriky a paľby v nepriateľskej armáde nastali preto, že kým sa medzi vojakmi čítal Napoleonov rozkaz, sám cisár jazdil okolo svojich bivakov na koni. Vojaci, ktorí videli cisára, zapálili trsy slamy a s výkrikom: vive l "empereur! bežali za ním. Napoleonov rozkaz znel: O 5. hodine ráno bola ešte úplná tma. Jednotky v strede, zálohy a Bagrationov pravý bok stále nehybne stáli; ale na ľavom boku kolóny pechoty, jazdy a delostrelectva, ktoré mali ako prvé zostúpiť z výšin, aby zaútočili na pravé francúzske krídlo a vrhli ho späť, podľa dispozície, do Českých hôr. sa začali miešať a začali vstávať zo svojich nočných pozícií. Dym z ohňov, do ktorých hádzali všetko nepotrebné, mi žral oči. Bola zima a tma. Dôstojníci narýchlo popíjali čaj a raňajkovali, vojaci žuvali sušienky, bili panáka nohami, zohrievali sa a hrnuli sa proti ohňom, hádzali do palivového dreva zvyšky búdok, stoličiek, stolov, kolies, vaní, všetkého nepotrebného, čo nebolo možné vziať so sebou. Rakúski vodcovia kolón prebehli medzi ruskými jednotkami a slúžili ako predzvesť útoku. Akonáhle sa v blízkosti tábora veliteľa pluku objavil rakúsky dôstojník, pluk sa dal do pohybu: vojaci utekali pred požiarmi, schovali rúrky do topánok, tašky do vozíkov, demontovali zbrane a zoradili sa. Dôstojníci si zapli gombíky, nasadili si meče a batohy a kričali po radoch; Vagónové vlaky a sanitári zapriahli, zbalili a zviazali vozíky. Pobočníci, velitelia práporov a plukov sedeli na koňoch, krížili sa, vydávali posledné rozkazy, pokyny a pokyny zvyšným konvojom a ozýval sa monotónny prešľap tisíc stôp. Kolóny sa hýbali, nevediac kam a nevideli z ľudí okolo seba, z dymu a z pribúdajúcej hmly buď oblasť, z ktorej odchádzali, alebo tú, do ktorej vchádzali. Inžinieri vybrali signály, ktorých použitie by malo zlepšiť základné charakteristiky systémov (kvalita komunikácie, odolnosť voči šumu), pričom sa spoliehali len na svoju intuíciu. Prelomom bolo vytvorenie teórie vzniku, spracovania a prenosu signálu. Umožňuje určiť efektívnosť použitia konkrétneho súboru (množiny) signálov len na základe znalosti ich auto- a interkorelačných charakteristík. Kódové sekvencie používané v CDMA systémoch na prenos signálu pozostávajú z N elementárnych symbolov (čipov). Každý informačný symbol signálu je pridaný k jednej N-symbolovej sekvencii, ktorá sa nazýva „rozširujúca sa sekvencia“, keďže „výsledný“ signál je vysielaný do vzduchu so zámerne rozprestretým spektrom. Zisk v kvalite komunikácie závisí jednak od počtu symbolov (dĺžky) sekvencie a jednak od charakteristík množiny signálov, predovšetkým od ich krížových korelačných vlastností a spôsobu modulácie. Dĺžka sekvencie. V domácej literatúre sa signály, ktorých báza je výrazne väčšia ako jednota (B=TF>>1, kde T je trvanie signálneho prvku, F je frekvenčné pásmo), zvyčajne nazývajú komplexné. Vo vzťahu k pôvodnému (informačnému) signálu je komplexný signál šum s takmer rovnakou spektrálnou hustotou výkonu. Je známe, že čím viac je spektrum signálu „natiahnuté“ na vzduch, tým nižšia je jeho spektrálna hustota. Vďaka tejto vlastnosti môžu byť signály s veľkou bázou využívané v „cudzom“ (už obsadenom) frekvenčnom pásme „sekundárne“ s ľubovoľne malým dopadom na tam fungujúci systém. Charakteristika. Celý súbor kódových sekvencií používaných v CDMA je rozdelený do dvoch hlavných tried: ortogonálne (kvázi ortogonálne) a pseudonáhodné sekvencie (PSR) s nízkou úrovňou vzájomnej korelácie (obr. 1). V optimálnom CDMA prijímači sú prichádzajúce signály, ktoré sú v podstate aditívnym bielym gaussovským šumom, vždy spracované pomocou korelačných metód. Preto sa postup vyhľadávania redukuje na nájdenie signálu, ktorý maximálne koreluje s individuálnym účastníckym kódom. Korelácia medzi dvoma sekvenciami (x(t)) a (y(t)) sa robí vynásobením jednej sekvencie časovo posunutou kópiou druhej. V závislosti od typu sekvencie používajú systémy CDMA rôzne korelačné metódy: Na dosiahnutie zvýšenia kvality komunikácie pri použití ktorejkoľvek z metód korelačného spracovania je potrebné, aby súbor signálov mal „dobré“ autokorelačné vlastnosti. Je žiaduce, aby signály mali jeden autokorelačný vrchol, inak je možná falošná synchronizácia pozdĺž bočného laloku autokorelačnej funkcie (ACF). Všimnite si, že čím širšie je spektrum emitovaných signálov, tým užší je centrálny vrchol (hlavný lalok) ACF. Páry kódových sekvencií sa vyberú tak, aby funkcia krížovej korelácie (MCF) mala minimálnu hodnotu pre ich párovú koreláciu. To zaručuje minimálnu úroveň vzájomného rušenia. V dôsledku toho sa výber optimálneho súboru signálov v CDMA obmedzuje na hľadanie štruktúry kódových sekvencií, v ktorých centrálny vrchol ACF má najvyššiu úroveň a bočné laloky ACF a maximálne špičky ACF sú čo najmenšia. V závislosti od spôsobu tvorby a štatistických vlastností sa ortogonálne kódové sekvencie delia na skutočne ortogonálne a kvázi ortogonálne. Charakteristickým znakom postupnosti je koeficient krížovej korelácie pij, ktorý sa vo všeobecnosti pohybuje od -1 do +1. V teórii signálov sa dokázalo, že maximálna dosiahnuteľná hodnota koeficientu vzájomnej korelácie je určená z podmienky Minimálna hodnota VCF poskytuje kódy, v ktorých sú korelačné koeficienty pre akékoľvek páry sekvencií záporné ( transortogonálne kódy). Koeficient krížovej korelácie ortogonálne sekvencií sa podľa definície rovná nule, t.j. O? ij = 0. Pre veľké hodnoty N možno rozdiel medzi korelačnými koeficientmi ortogonálnych a transortogonálnych kódov prakticky zanedbať. Existuje niekoľko spôsobov, ako generovať ortogonálne kódy. Najbežnejšie je použitie Walshových sekvencií dĺžky 2n, ktoré sú tvorené na základe riadkov Hadamardovej matice Viacnásobné opakovanie postupu umožňuje vytvoriť maticu ľubovoľnej veľkosti, ktorá sa vyznačuje vzájomnou ortogonalitou všetkých riadkov a stĺpcov. Tento spôsob generovania signálov je implementovaný v štandarde IS-95, kde je dĺžka Walshových sekvencií zvolená na 64. Všimnite si, že rozdiel medzi riadkami Hadamardovej matice a Walshovými sekvenciami je len v tom, že tieto sekvencie používajú unipólové signály. formulára (1,0). Pomocou Hadamardovej matice ako príkladu je ľahké ilustrovať princíp konštrukcie transortogonálnych kódov. Môžeme teda overiť, že ak sa z matice vymaže prvý stĺpec pozostávajúci iba z jednotiek, ortogonálne Walshove kódy sa transformujú na transortogonálne, v ktorých pre ľubovoľné dve sekvencie počet nezhôd symbolov prevyšuje počet zhôd presne o jednu, t.j. O? ij = -1/(N-1). Ďalším dôležitým typom ortogonálnych kódov je bioortogonálny kód, ktorý je vytvorený z ortogonálneho kódu a jeho inverzie. Hlavnou výhodou biortogonálnych kódov v porovnaní s ortogonálnymi je schopnosť prenášať signál v polovičnom frekvenčnom pásme. Napríklad biortogonálny blokový kód (32,6) používaný vo WCDMA umožňuje prenos signálu transportného formátu TFI. Všimnite si, že ortogonálne kódy majú dve základné nevýhody. 1. Maximálny počet možných kódov je obmedzený ich dĺžkou (v norme IS-95 je počet kódov 64), a teda majú obmedzený adresný priestor. Na rozšírenie súboru signálov spolu s ortogonálnymi signálmi kvázi ortogonálne sekvencie. Návrh normy cdma2000 teda navrhuje metódu na generovanie kvázi ortogonálnych kódov vynásobením Walshových sekvencií špeciálnou maskovacou funkciou. Táto metóda umožňuje získať súbor kvázi-ortogonálnych sekvencií Quasi-ortogonal Function Set (QOFS) pomocou jednej takejto funkcie. Použitím m maskovacích funkcií a súboru Walshových kódov dĺžky 2n je možné vytvoriť (m+1) 2n QOF sekvencií. 2. Ďalšou nevýhodou ortogonálnych kódov (a tie, ktoré sa používajú v štandarde IS-95 nie sú výnimkou) je, že funkcia krížovej korelácie sa rovná nule iba „v bode“, t.j. pri absencii časového posunu medzi kódmi. Preto sa takéto signály používajú iba v synchrónnych systémoch a hlavne v priamych kanáloch (od základnej stanice k účastníkovi). Schopnosť prispôsobiť systém CDMA rôznym prenosovým rýchlostiam sa dosahuje použitím špeciálnych ortogonálnych sekvencií s variabilným faktorom šírenia (OVSF, Orthogonal Variable Spreading Factor), tzv. kódy s premenlivou dĺžkou. Pri prenose signálu CDMA, ktorý bol vytvorený pomocou takejto sekvencie, zostáva rýchlosť čipu konštantná, ale rýchlosť informácie sa mení dvakrát. Štandardy 3. generácie navrhujú ako OVSF kódy používať ortogonálne zlaté kódy s viacerými prenosovými rýchlosťami (multirate). Princíp ich formovania je pomerne jednoduchý; Vysvetľuje to obr. 3, ktorý zobrazuje kódový strom, ktorý vám umožňuje vytvárať kódy rôznych dĺžok. Každá úroveň kódového stromu určuje dĺžku kódových slov (spreading factor, SF), pričom každá ďalšia úroveň zdvojnásobuje možný počet kódov. Takže ak na úrovni 2 možno vygenerovať iba dva kódy (SF=2), potom na úrovni 3 sa vygenerujú štyri kódové slová (SF=4) atď. Kompletný kódový strom obsahuje osem úrovní, čo zodpovedá SF=256 (na obrázku sú zobrazené iba spodné tri úrovne). Súbor kódov OVSF teda nie je pevný: závisí od faktora šírenia SF, t.j. v skutočnosti to závisí od rýchlosti kanála. Treba poznamenať, že nie všetky kombinácie kódového stromu môžu byť súčasne implementované v rovnakej bunke CDMA. Hlavnou podmienkou pre výber kombinácie je neprípustnosť porušenia ich ortogonality. Spolu s ortogonálnymi kódmi zohráva kľúčovú úlohu v systémoch CDMA PRP, ktoré, aj keď sú generované deterministickým spôsobom, majú všetky vlastnosti náhodných signálov. Priaznivo sa však líšia od ortogonálnych sekvencií tým, že sú invariantné voči časovým posunom. Existuje niekoľko typov PSP s rôznymi vlastnosťami. Jednoducho povedané, dnes sa objavili technické nástroje, ktoré dokážu „odvodiť“ akýkoľvek súbor sekvencií s danými vlastnosťami. Jedným z najjednoduchších a mimoriadne účinných prostriedkov na generovanie binárnych deterministických sekvencií je použitie posuvného registra (RS). Sekvencia na výstupe n-bitového PC so spätnou väzbou je vždy periodická a jej perióda n (počet cyklov, po ktorých sa obvod vráti do pôvodného stavu) nepresahuje 2n. Teoreticky je možné pomocou n-bitového registra a vhodne zvolenej spätnoväzbovej logiky získať sekvenciu ľubovoľnej dĺžky N v rozsahu od 1 do 2 n vrátane. Sekvencia maximálnej dĺžky alebo m-sekvencia bude mať periódu 2 n -1. Autokorelačná funkcia m-sekvencie je periodická a má dve hodnoty: Úroveň bočných maxím autokorelačnej funkcie (obr. 4) nepresahuje hodnotu Kódy Golda sú tvorené znak po znaku sčítaním modulo 2 dvoch m-sekvencií (obr. 5). Návrh WCDMA špecifikuje tri typy zlatých kódov: primárne a sekundárne ortogonálne zlaté kódy (oba majú dĺžku 256 bitov) a dlhý kód. Ortogonálne zlaté kódy sú vytvorené na základe 255-bitovej m-sekvencie s pridaním jedného redundantného symbolu. Primárny synchronizačný kód má funkciu aperiodickej autokorelácie a používa sa na počiatočnú synchronizáciu. Sekundárny synchronizačný kód je nemodulovaný ortogonálny zlatý kód, ktorý sa prenáša paralelne s primárnym synchronizačným kódom. Každý sekundárny synchronizačný kód je vybraný zo 17 rôznych zlatých kódov (C1,...,C17). Dlhý kód pre dopredný kanál je 40 960 čipových fragmentov zlatého kódu. Komunikačný systém založený na WCDMA je asynchrónny a susedné základňové stanice používajú rôzne zlaté kódy (spolu 512), ktoré sa opakujú každých 10 ms. Asynchrónny princíp činnosti základňových staníc ich robí nezávislými od externých zdrojov synchronizácie. Je určený na použitie dlhého kódu v spätnom kanáli, ale iba v tých bunkách, kde nie je povolený režim detekcie viacerých používateľov. Rodina kódov Kasami obsahuje 2 k sekvencií s periódou 2 n-1. Za optimálne sa považujú v tom zmysle, že pre každý „preferovaný“ pár je zabezpečená maximálna hodnota autokorelačnej funkcie, ktorá sa rovná (1 + 2 k). Kasami kódové sekvencie sú implementované pomocou troch posuvných registrov zapojených do série (u, v a w) s rôznymi spätnými väzbami (obr. 6), z ktorých každá tvorí svoju m-sekvenciu. Na získanie sekvencií kódu Kasami s danými vlastnosťami musia mať sekvencie v a w rôzne posuny. Kasami kódy s dĺžkou 256 bitov sa používajú ako krátke sekvencie v návratovom kanáli (projekt WCDMA) v tých bunkách, ktoré využívajú detekciu viacerých používateľov. Pseudonáhodné sekvencie s malou aperiodickou hodnotou ACF sú schopné zabezpečiť synchronizáciu vysielaných a prijímaných signálov v pomerne krátkom časovom úseku, ktorý sa zvyčajne rovná dĺžke samotnej sekvencie. Najznámejšie sú Barkerove sekvencie (pozri tabuľku). Účinnosť sekvencií s aperiodickým ACF sa zvyčajne hodnotí indikátorom kvality F, ktorý je definovaný ako pomer druhých mocnín súfázových zložiek signálu k súčtu druhých mocnín jeho mimofázových zložiek. Meradlom účinnosti aperiodickej korelácie binárnej sekvencie je teda indikátor kvality. Walshove funkcie sú rodinou funkcií, ktoré tvoria ortogonálny systém s hodnotami iba 1 a -1 v celej doméne definície. V princípe môžu byť Walshove funkcie reprezentované v spojitej forme, ale častejšie sú definované ako diskrétne postupnosti 2^n (\displaystyle 2^(n))22 prvkov. Skupina (\displaystyle 2^(n))2^n Walshových funkcií tvorí Hadamardovu maticu. Walshove funkcie sú široko používané v rádiovej komunikácii, kde sa používajú na implementáciu kódového delenia MA (CDMA), napríklad v celulárnych štandardoch ako IS-95, CDMA2000 alebo UMTS. Systém Walshových funkcií je ortonormálny základ a v dôsledku toho umožňuje rozšíriť signály ľubovoľného tvaru do zovšeobecneného Fourierovho radu. Zovšeobecnením Walshových funkcií na prípad viac ako dvoch hodnôt sú Vilenkin-Chrestensonove funkcie. M-sekvencie. Spôsob vzniku a vlastnosti M-sekvencií. Aplikácia M-sekvencií v komunikačných systémoch V súčasnosti sú spomedzi dlhých binárnych kódových sekvencií najpoužívanejšie M-sekvencie, Legendreove sekvencie, Gold a Cassamiho kódové sekvencie, Walshove kódové sekvencie a nelineárne kódové sekvencie. Výhodou dlhých M-sekvencií je, že úroveň periodických postranných lalokov funkcie neistoty M-sekvencie klesá s rastúcou dĺžkou. L. Maximálna úroveň periodického postranného laloku TCF M-sekvencie je nepriamo úmerná dĺžke sekvencie (1/L). M-sekvencie Vyššie bolo spomenuté, že sekvencie maximálnej dĺžky alebo M-sekvencie sú optimálne na rozšírenie spektra signálu. Takéto sekvencie sa tvoria pomocou digitálnych strojov, ktorých hlavným prvkom je posuvný register s pamäťovými bunkami T1, T2, …, T k(Obrázok 2). Hodinové impulzy prichádzajú do všetkých buniek súčasne s periódou , čím sa symboly uložené v týchto bunkách presúvajú do buniek susediacich vpravo v jednom hodinovom cykle. Označme písmenami symboly uložené v zodpovedajúcich bunkách v tom cykle. - symbol na vstupe prvej bunky; hodnota tohto symbolu je tvorená pomocou lineárneho rekurentného vzťahu V súlade s hodnotou symbolu v bunke s číslom sa vynásobí koeficientom a pridá sa k iným podobným produktom. Symboly aj koeficienty môžu mať hodnoty 0 alebo 1; sčítacie operácie sa vykonávajú modulo 2. Ak je koeficient , potom sa symbol bunky nezúčastňuje na tvorbe hodnoty súčtu. Ak zoberieme obsah buniek posuvného registra ako počiatočný stav, potom po taktovacích cykloch tento stav opäť nastane. Ak zároveň zaregistrujeme postupnosť symbolov -tej bunky, potom bude dĺžka tejto postupnosti rovná . Pri nasledujúcich opatreniach sa táto sekvencia znova zopakuje atď. Číslo sa nazýva perióda postupnosti. Hodnota pre pevnú dĺžku posuvného registra závisí od počtu a umiestnenia odbočiek. Pre každú hodnotu môžete určiť počet ťuknutí a ich pozície, pri ktorých je perióda výslednej sekvencie maximálna. Akýkoľvek stav posuvného registra (okrem nulovej kombinácie) možno považovať za počiatočný; zmena počiatočného stavu spôsobí iba posun sekvencie. Sekvencie s maximálnou možnou periódou pre pevnú dĺžku registra sa nazývajú M-sekvencie. Ich obdobie (dĺžka). Bloková schéma automatu, ktorý generuje M-sekvencie, je zvyčajne špecifikovaná charakteristickým polynómom: v ktorom vždy , . V tabuľke 1 pre množiny hodnôt koeficientov tohto polynómu, ktoré definujú sekvencie maximálnej dĺžky. Vektorové znalosti – ak , potom je výstup bunky s číslom posuvného registra pripojený k sčítačke modulo 2; – ak , tak výstup bunky s číslom posuvného registra nie je pripojený k sčítačke modulo 2. (dlhý kód pre kódovanie a identifikáciu mobilných staníc) Pri riešení mnohých analytických problémov je vhodné reprezentovať komplexný signál ako súbor elementárnych signálov. V praxi našla najväčšie uplatnenie reprezentácia signálu s(t), daný na intervale, vo forme lineárnej kombinácie niektorých elementárnych funkcií (p t (t), / = 0,1,2,..., nazývané základné -
norma základnej funkcie. Reprezentácia signálu v tejto forme sa nazýva zovšeobecnený Fourierov rad. Často sa ako základné funkcie používa systém goniometrických funkcií. alebo systém zložitých exponenciálnych funkcií S rozvojom digitálnych metód prenosu a spracovania signálov v posledných rokoch sa však ako základné funkcie začínajú používať diskrétne ortogonálne postupnosti v podobe Rademacherových, Walshových, Haarových funkcií atď. Zaveďme bezrozmerný čas 0 = t / T . Funkcie Rademacher sú tvorené zo sínusových funkcií pomocou vzťahu Inými slovami, funkcie Rademacher nadobúdajúce hodnoty ±1 možno interpretovať ako funkcie „obdĺžnikového sínusu“. Grafy prvých štyroch funkcií Rademacher vyzerajú ako na obrázku 4.12. Funkčný systém Rademacher r k(0) je ortonormálny na intervale 0 Walshov funkčný systém je rozšírením systému funkcií Rademacher na kompletný systém a je definovaný ako Kde kf- význam jčíslica v číselnom zázname Komu v sivom kóde. Napríklad, keďže 5=>101 2 =>111 g. Grafy prvých štyroch Walshových funkcií sú znázornené na obrázku 4.13. Ryža. 4.13. Walshove funkcie majú nasledujúce vlastnosti: 5. Násobením Walshových funkcií získame Walshovu funkciu, ale v inom poradí chôdza k (0) wal n (0) = walj (0), j = k ® n, chôdza k (0 2) chôdza k (0 2) = chôdza k(0 3), 0 3 = 0j ® 0 2, kde © je sčítanie modulo dva. V niektorých prípadoch sa používajú Walshove funkcie formulára Pri použití systému Walshových funkcií ako základných funkcií môže byť signál reprezentovaný vo forme Súbor Walsh-Fourierových koeficientov (q) resp (a k f k) a množina radových čísel funkcií tvorí spektrum signálu vo Walshovej báze, ktorá sa pre stručnosť niekedy nazýva S-spektrum. Napríklad signál, ktorý je periodickou sekvenciou pravouhlých impulzov (obr. 4.14), má S-spektrum určené výrazom (4.39). Ryža. 4.14. pravouhlé impulzy Nechaj n= 3, potom získame S-spektrum pre tento prípad, znázornené na obrázku 4.15. Ryža. 4.15. Na rozdiel od bežného frekvenčného spektra sa teda S-spektrum sekvencie pravouhlých impulzov ukazuje ako konečné. Treba si uvedomiť, že posun impulzov v čase vedie k zmene štruktúry S-spektra. Objavujú sa najmä nové komponenty. Napríklad pre sekvenciu n= 3 impulzy posunuté o 0=1/16, S-spektrum vyzerá ako na obrázku 4.16, pričom pri použití trigonometrickej sústavy funkcií sa časovým posunom mení len fázové spektrum. Vzhľadom na možnosť aplikácie logických operácií na Walshove funkcie sa používajú pri vývoji zariadení na generovanie a konverziu signálu na báze mikroprocesorovej technológie. Signály založené na Walshových funkciách sa používajú v digitálnych viackanálových systémoch prenosu informácií. Ryža. 4.16. posunuté o 0=1/16 Systém Haarovej funkcie pozostáva z po častiach konštantných funkcií har k(0), špecifikované na intervale 0 Kde T- číslo najvýznamnejšej nenulovej číslice v binárnom vyjadrení čísla Komu mod2 w - hodnota Komu modulo 2 t, je najmenší zvyšok pri delení čísla Komu na 2 t. Grafy niekoľkých Haarových funkcií sú uvedené na obrázku 4.17. Ryža. 4.17. Ak uvažujeme spektrum signálu na Haarovej báze, tak ako v prípade S-spektra, keď sa signál v čase posúva, mení sa štruktúra jeho spektra. Haarove funkcie sa využívajú v riadiacich a komunikačných systémoch, pri vývoji digitálnych filtrov a pri kompresii informácií - sú to napr. rôzne spôsoby kompresie čiernobielych fotografií na báze Haarových funkcií pre následný prenos komprimovaných obrazov cez komunikačné kanály resp. ich archivácia.Označenie
Tvorenie
Príklad
Vlastnosti
1. Ortogonalita
Napíšte recenziu na článok "Funkcia Walsh"
Literatúra
pozri tiež
Poznámky
Výňatok charakterizujúci Walshovu funkciu
"Zdá sa, že ešte všetci neodišli, princ," povedal Bagration. – Do zajtra rána, zajtra sa všetko dozvieme.
"Na hore je hliadka, Vaša Excelencia, stále na tom istom mieste, kde bola večer," oznámil Rostov, predklonil sa, držal si ruku na priezore a nedokázal potlačiť úsmev pobavenia, ktorý v ňom vyvolal jeho výlet. a hlavne zvukmi guliek.
"Dobre, dobre," povedal Bagration, "ďakujem, pán dôstojník."
"Vaša Excelencia," povedal Rostov, "dovoľte mi, aby som sa vás spýtal."
- Čo sa stalo?
„Zajtra je naša letka pridelená do záloh; Dovoľte mi požiadať vás, aby ste mi sekundovali k 1. letke.
- Aké je tvoje priezvisko?
- Gróf Rostov.
- OH dobre. Zostaň so mnou ako sanitár.
– Syn Ilju Andreja? - povedal Dolgorukov.
Ale Rostov mu neodpovedal.
- Takže budem dúfať, Vaša Excelencia.
- Budem objednávať.
„Zajtra možno pošlú nejaký rozkaz panovníkovi,“ pomyslel si. - Boh žehnaj".
„Vojaci! Ruská armáda vystupuje proti vám, aby pomstila rakúsku, ulmskú armádu. Sú to tie isté prápory, ktoré ste porazili pri Gollabrunne a ktoré odvtedy neustále prenasledujete na toto miesto. Pozície, ktoré zastávame, sú silné, a kým sa budú pohybovať, aby ma obkľúčili napravo, odhalia môj bok! Vojaci! Ja sám povediem vaše prápory. Budem ďaleko od ohňa, ak svojou obvyklou odvahou vnesiete do nepriateľských radov neporiadok a zmätok; ale ak je víťazstvo na pochybách čo i len na jednu minútu, uvidíš svojho cisára vystaveného prvým úderom nepriateľa, pretože o víťazstve nemôže byť pochýb, najmä v deň, keď česť francúzskej pechoty, ktorá je tzv. potrebné pre česť jeho národa, je v stávke.
Pod zámienkou odstránenia ranených neznepokojujte rady! Nech je každý plne presiaknutý myšlienkou, že je potrebné poraziť týchto anglických žoldnierov, inšpirovaných takouto nenávisťou voči nášmu národu. Toto víťazstvo ukončí našu kampaň a môžeme sa vrátiť do zimných priestorov, kde nás nájdu nové francúzske jednotky, ktoré sa formujú vo Francúzsku; a potom pokoj, ktorý urobím, bude hodný môjho ľudu, teba i mňa.
Napoleon."
Vojak v pohybe je rovnako obkľúčený, obmedzený a ťahaný svojim plukom ako námorník loďou, na ktorej sa nachádza. Bez ohľadu na to, ako ďaleko sa dostane, bez ohľadu na to, do akých zvláštnych, neznámych a nebezpečných zemepisných šírok sa dostane, okolo neho - ako pre námorníka, sú vždy a všade tie isté paluby, stožiare, laná jeho lode - vždy a všade tí istí súdruhovia, ktorí sú na ceste k námorníkom. tie isté rady, ten istý nadrotmajster Ivan Mitrich, ten istý rotný pes Zhuchka, tí istí nadriadení. Vojak málokedy chce poznať zemepisné šírky, v ktorých sa nachádza celá jeho loď; ale v deň boja, bohvie ako a odkiaľ, v morálnom svete armády zaznie pre každého jeden prísny tón, ktorý vyznieva ako priblíženie sa čohosi rozhodného a slávnostného a vzbudzuje ich k neobyčajnej zvedavosti. Počas dní bojov sa vojaci vzrušene snažia vymaniť sa zo záujmov svojho pluku, počúvajú, pozorne pozerajú a dychtivo sa pýtajú na to, čo sa okolo nich deje.
Hmla zosilnela tak, že napriek tomu, že svitalo, nebolo vidieť ani na desať krokov pred seba. Kríky vyzerali ako obrovské stromy, ploché miesta vyzerali ako útesy a svahy. Všade, zo všetkých strán bolo možné na desať krokov naraziť na nepriateľa neviditeľného. Ale kolóny dlho kráčali v tej istej hmle, klesali a stúpali po horách, míňali záhrady a ploty, novým, nezrozumiteľným terénom, nikdy nestretli nepriateľa. Naopak, teraz vpredu, teraz vzadu, zo všetkých strán sa vojaci dozvedeli, že naše ruské kolóny idú rovnakým smerom. Každý vojak sa cítil dobre na duši, lebo vedel, že na to isté miesto, kam ide on, teda neznáme, kam ide oveľa, oveľa viac našich.
"Pozrite, kurskí vojaci prešli," povedali v radoch.
- Vášeň, brat môj, že sa naše vojská zhromaždili! Večer som sa pozrel ako sú rozmiestnené svetlá, koniec v nedohľadne. Moskva - jedno slovo!
Hoci sa nikto z veliteľov kolón nepriblížil k radom, ani sa s vojakmi nerozprával (velitelia kolón, ako sme videli na vojenskej rade, nemali dobrú náladu a boli nespokojní s podnikaním a preto iba plnili rozkazy a nestarali sa o to, pobavenie vojakov), napriek Vojaci však kráčali veselo, ako vždy, išli do akcie, najmä útočne. Po asi hodinovej chôdzi v hustej hmle sa však väčšina armády musela zastaviť a v radoch sa prehnalo nepríjemné vedomie pokračujúceho neporiadku a zmätku. Ako sa toto vedomie prenáša, je veľmi ťažké určiť; isté však je, že sa prenáša neobyčajne verne a šíri sa rýchlo, nebadane a nekontrolovateľne ako voda cez roklinu. Keby bola ruská armáda sama, bez spojencov, potom by možno prešlo veľa času, kým by sa toto vedomie neporiadku stalo všeobecným sebavedomím; ale teraz, so zvláštnym potešením a prirodzenosťou pripisujúc príčinu nepokoja hlúpym Nemcom, všetci boli presvedčení, že je tu škodlivý zmätok spôsobený klobáskami.Základné pojmy
Ortogonálne kódy
Pseudonáhodné sekvencie
m-sekvencie
Barkerove sekvencie
Obrázok 2 – Digitálny automat na vytváranie M-sekvencií
umožňuje jednoznačne naznačiť štruktúru digitálneho automatu, ktorý tvorí zodpovedajúcu polynómovú (1.16) M-sekvenciu:
