Walsh függvények. Walsh-kód sorozatok, kialakulásuk

Navigációs táblázatok tömörítése Walsh-alapú C.B. Pashentsev

MSTU Navigációs Kar, Navigációs Tanszék

Annotáció. A cikk megvizsgálja a Walsh-Paley funkcionális alap felhasználásának lehetőségét lineáris és téglalap alakú táblázatok tömörítésére. Az ehhez szükséges összes képletet megadjuk, és néhány példán keresztül bemutatjuk az információtömörítés valódi hatását. A módszer az információk előzetes tömörítésére és valós idejű feldolgozására egyaránt használható.

Absztrakt. A munka során figyelembe vették a Wolsh-Paly funkcionális alap felhasználásának lehetőségét a lineáris és négyszögletes tömörítési táblázatokhoz. Az ehhez szükséges összes képletet megadtuk, és néhány példán bemutattuk az információtömörítés tényleges hatását. A módszer felhasználható információk előzetes tömörítésére és valós idejű feldolgozására is.

1. Bemutatkozás

Számos, a navigációhoz kapcsolódó automata és automatizált eszköz a döntési eszközök memóriájában tárolt és azokból szükség szerint kiválasztott táblázatos adatokat használ. Ebben az esetben a legfontosabb erőforrást - a memóriát - fogyasztják el, a belőle való mintavételezés pedig még fontosabb erőforrást - időt -, kihat a teljes információfeldolgozó rendszer teljesítményére. Ezért minden olyan módszer fontos, amely csökkenti a tárolási mennyiséget. Az egyik ilyen módszer lehet a táblázatos információk tömörítésének módszere annak spektrális dekompozíciója miatt valamilyen funkcionális alapon. A fogyasztás pillanatában a függvény értékét inverz transzformációval állítjuk vissza. A Fourier-bővítéshez képest előnyösebb a Walsh-alapot használni a bővítéshez, mivel sima függvényeknél a Walsh-bővítés együtthatói gyorsabban nullázódnak. Ez nagyobb fokú információtömörítést tesz lehetővé a Walsh-bázisban. Ezenkívül a táblaértékek Walsh-alapú visszaállítása kevesebb időt igényel. Ennek oka a Walsh-függvények egyszerűbb számítása a trigonometrikus függvények kiszámításához képest. Ha ezeket a funkciókat hardverben generálják, akkor a Walsh-függvények használatából származó előny még nagyobb, mivel lehetséges +1 és -1 értékeik könnyen megvalósíthatók a számítástechnikai eszközökkel. A munka numerikus példákon keresztül mutatja be a Walsh-bázis használatának előnyeit bizonyos típusú sima függvények és táblázatos adatok esetében. A számítási folyamat a szerző által írt gyors Fourier- és Walsh-transzformációs programokon és a kapott spektrumok összehasonlításán alapul.

2. A tömörítés elméleti alapjai

Jól ismertek azok az általános elméleti alapelvek, amelyek alapján az átalakítás a kiválasztott funkcionális bázison történik (Gold, Ryder, 1993; Trakhtman A., Trakhtman V., 1978). A diszkrét transzformációkat akkor kell kiemelni, ha az eredeti számsor véges. Mivel táblatömörítésről beszélünk, i.e. alapvetően véges számsorról, akkor a továbbiakban csak diszkrét transzformációkról beszélünk. Ha adott egy N számból álló sorozat

X2, Xk, , XN (1)

akkor a funkcionális alapot N függvény véges halmazából kell kiválasztani

Fa(X), a= 1, 2,„., N, (2)

Xk ponthalmazon létező. Ekkor egy diszkrét transzformáció ezen az alapon pontosan N Ca, Koropbie együtthatót ad formális összegzéssel:

C„ = ЪкХк Fa(Хк), а= 1, 2,„„ N. (3)

A Ca N együttható halmaza számos szám (1) diszkrét reprezentációját képezi

funkcionális alapja (2). Gyakran ezt a Ca-számkészletet vonalspektrumnak nevezik a kiválasztott alapon. A (3) kiterjesztést egy másik értelmezés szerint az eredeti Xk koordinátarendszer lineáris transzformációjának tekintjük. A Ca együtthatók ezután az új 0JX koordinátarendszerben koordinátákká válnak. Ha a spektrum (Ca együttható halmaz) ismert, akkor az azt generáló számsor inverz diszkrét transzformációval számítási hibákig visszaállítható

Xk = (1/N) T.aCa0JXk), k = 1, 2,..., N. (4)

Az egyszerű és majdnem szimmetrikus (3) és (4) transzformációk érvényességéhez szükséges, hogy a bázisfüggvények halmaza rendelkezzen az ortogonalitás és egy bizonyos normalizáció tulajdonságával. Az ortogonalitási feltétel egyenlőségek halmazának tűnik

Zk Фр(Хк) Ф(Хк) = 0, р Ф q, (5)

a normalizálási feltételek pedig egyenlőségek halmazaként

Zk ФрХк) Фр(Хк) = Ек Фр\Хк) = 1. (6)

Ezenkívül egy bázisfüggvény-rendszert teljesnek nevezünk, ha nem lehet egyetlen olyan függvénynél többet megadni, amely a bázis összes függvényére ortogonális.

Nyilvánvaló, hogy a kérdés ilyen megfogalmazásával nem történik tömörítés, mivel az eredeti sorozat tagjainak száma és a spektrális együtthatók száma megegyezik. Az információ tömörítésének lehetősége akkor jelenik meg, ha a spektrumegyütthatók száma N-nél kisebbre tehető. Például, ha a spektrumegyütthatók egy része nullával egyenlő vagy ahhoz közeli. Ekkor ezek az együtthatók figyelmen kívül hagyhatók, és a kapott spektrum rövidebb lesz. Az első esetben, amikor csak a spektrum nulla együtthatóit hagyjuk figyelmen kívül, az eredeti számsor visszaáll a számítási hibákig. Ha figyelmen kívül hagyjuk a spektrum együtthatókat, amelyek a jelzett mértékig nullához közelítenek, akkor az eredeti sorozat rekonstruált értékei nemcsak számítási hibákat tartalmaznak, hanem a spektrum pontatlan ábrázolásából adódó hibákat is. Minél nagyobb a hiba az eredeti sorozat mi flonyœaeM, TeM elemeinek rekonstruálásakor, annál nagyobb számú spektrumegyüttható elhanyagolható.

Ha n-nel jelöljük az általunk figyelmen kívül hagyott spektrumegyütthatók számát, akkor az arányt százalékban

négyzet = (n/N) -100% (7)

nevezhetjük az eredeti információ tömörítési fokának. Valójában ebben az esetben N-n spektrum együtthatóval ábrázoljuk az eredeti sorozat N értéke helyett. Sq = 0-nál a kompresszió egyáltalán nem következik be, sq = 100%-nál pedig eléri a határértéket. A tényleges esetek 0%-tól 100%-ig terjednek.

Az ötlet megvalósításának gyakorlati oldala némileg bonyolultabb. Ha a véges (végső) spektrális együtthatók nullák vagy kicsik a jelzett mértékben, akkor nem nehéz n-et eldobni belőlük, és ezáltal elérni a négyzettömörítést.

Ha a spektrumegyütthatók között van egy adott mértékben nulla vagy nullához közeli, de ezek nem véglegesek, akkor az információtömörítés szempontjából nehézséget okoz egy ilyen spektrum ábrázolása. Ebben az esetben vagy meg kell adni az összes spektrum együtthatót, beleértve a nullát és a közeli értéket, és akkor nem történik tömörítés. Vagy adjon meg nulla spektrális együtthatójú csoportokat a csoport kezdeti elemének számával és a csoport elemeinek számával. Ez természetesen csökkenti az eredeti számsor tömörítési fokát. Ha a spektrum nulla elemei nem véglegesek, vagy nem alkotnak csoportokat, és számuk nem egyszerű mintázatot mutat, akkor az információtömörítés így nem valósul meg.

Tehát az információ tömörítésének lehetősége és tömörítésének mértéke magától a számsortól (1) és a Ca spektrális felbontásának alapját képező függvényhalmaztól (2) is függ. Mivel az Xk számsor adott nekünk, a tömörítés mértékét a spektrális felbontás alapjának megváltoztatásával tudjuk szabályozni. De a választott Ф(х) alapnál az adott információ természete hatással lesz mind a

a tömörítési képességek és a tömörítés mértéke. Meglehetősen sok funkcionális bázis létezik, amelyeket sikeresen alkalmaznak az információszolgáltatás különféle feladataihoz. A legismertebbek közé tartoznak a hatványfüggvények alapjai és polinomváltozatai a Csebisev és Legendre polinomok formájában, valamint Kravcsuk, Charlier és Meissner alapjai. De a legismertebb számunkra a trigonometrikus függvények alapja:

sin(2nax) és с s(2n«x), (7)

vagy a megfelelő exponenciális alap komplex formában:

exp(-j 2nax). (8)

Ebben az esetben a Ca-együtthatók spektruma a szokásos fizikai értelemben vett spektrum, mint egy meghatározott frekvenciakészlet amplitúdóinak halmaza egy korlátozott tartományban és egy bizonyos frekvenciafelbontásban. Mivel ebben az esetben a bázis már ki van választva, a tömörítési lehetőségek most már csak a forrásinformáció jellegéhez kapcsolódnak. Ha az jellegében megfelel a választott alapnak (8), pl. véges számú periodikus függvény lineáris kombinációjából áll, akkor a spektrum csak véges számú nullától eltérő együtthatót tartalmaz majd, és felmerül az információtömörítés lehetősége.

3. Walsh-Paley függvényrendszer

Ha a kiindulási információ más jellegű, például hatvány, exponenciális vagy logaritmikus törvény szerint változik, akkor a spektrumban nem minden együtthatója elég kicsi, és a tömörítés vagy lehetetlen, vagy kicsi a tömörítés mértéke. Ezekben az esetekben indokolt más funkcionális alapot használni. Mivel más bázisokra nincs egyértelmű fizikai ábrázolás a spektrumnak, ezért a (2)-t az Xk koordinátarendszerből egy másik Fa(X) koordinátarendszerbe való átmenet képleteként értelmezhetjük. Ha az együtthatók egy része nullával egyenlő, az azt jelenti, hogy az új koordinátarendszerben az eredeti számsor formájában koordinátákkal megadott vektor egy N-n méretű koordináta-hipersíkban helyezkedik el. A létező lehetőségek között számos a Rademacher-függvények által generált bázis található Z e-re (0,1):

R0(z) = 1, Rk(z) = előjel (sin (2k nz)), k = 1,2,..., (9)

amelyek a bennük szereplő jel() függvénynek megfelelően csak két értéket vesznek fel: +1 vagy -1.

A (9) függvényrendszer ortogonális és normalizált, de nem teljes. Hozzáadhatjuk az alakjel(cos2knz) függvényeket, amelyek szintén ortogonálisak a (9) rendszer függvényeire. Ezért a reprezentációk (9) alapján további teljes rendszereket alakítanak ki, Rademacher-függvények szorzatait felhasználva, és bizonyos sorrendet visznek be az így kapott új függvényekbe.

A navigációs alkalmazások számára az információtömörítés szempontjából a legérdekesebb a Walsh-Paley funkciórendszer. Ennek a rendszernek a kialakulása szorosan összefügg az alkotó függvényeinek bináris számaival. Pontosabban, az a számú Walsh-Paley függvény a Rademacher-függvények szorzata azon a bináris bitek számával, amelyekben 1-esek találhatók. Ha az a számot bináris reprezentációban írjuk fel n = log N bittel

a = Zk 2k-1 ak, (10)

akkor a Walsh-Paley rendszer függvényei a következőképpen ábrázolhatók:

Wa(z) = Pk M. Maga a szám a (12)-hez hasonlóan bináris formában is ábrázolható:

) = Ek 2k-1]k. (15)

Ezután a Walsh-Paley függvények rendszere végre formában kerül bemutatásra

YaGa)/Sh = WJ (a/K) = (-1)"as1""k + \ (16)

amelyet minden további számítás során használnak. Az alábbiakban bemutatjuk a Pascal nyelvű WolshPaly() szoftverfüggvényt, amely Walsh-Paley függvényeket generál a (16) képletekkel. N = 8 esetén a Walsh-Paley No(/) függvények értékeit a táblázat tartalmazza. 1.

1. táblázat Walsh-Paley függvény értékei N = 8-hoz

] 0 1 2 3 4 5 6 7

0 1 1 1 1 1 1 1 1

Anélkül, hogy a részleteket tárgyalnánk, egyszerűen csak megemlítjük a Hadamard- és Harmuth-függvényrendszerek létezését, amelyek csak abban különböznek a részletesen vizsgált Walsh-Paley függvényrendszertől, hogy ugyanazokat a funkciókat szervezik. A Walsh-Paley függvények sorrendje adja a legtöbb olyan végső spektrum együtthatót, amely adott fokig nulla vagy nullához közeli.

4. Walsh-Paley sorozatok konvergenciája

A Walsh-függvényeknek számos hasznos tulajdonsága van, amelyek között bemutatjuk a számításoknál használt szimmetriatulajdonságot:

Shch (a/Shch. (17)

A Walsh-függvényszámok n = logN bites bináris reprezentációja határozza meg a függvény p sorrendjét és r rangját. A sorrend a bináris számjegyek legnagyobb száma, amely egyenlő 1-gyel. Egy függvény rangja a nullától eltérő bináris számjegyek száma, például a Walsh-függvény a = 9 számmal, ha N = 16 és n = 4 bináris formában 1001-ként van ábrázolva, ezért a rangja g = 2 (kettő

nem nulla számjegy) és p = 3 sorrend (a legjelentősebb nem nulla számjegy a harmadik, mivel a számolás nulláról indul). Ha egy a számú függvénynek r rangja van, akkor a száma a következőképpen ábrázolható:

a (R = r) = 2M1 + 21"2 + ... + 2Mg, (18)

ahol tsk (k = 1, 2,..., r) az a szám bináris reprezentációjának nullától eltérő bitjeinek száma. Például a 9-es szám ábrázolható 23 + 20-ként, figyelembe véve az 1001 bináris ábrázolását. Közvetlenül az eredeti információ tömörítésének problémája esetén az a sebesség, amellyel a Ca tágulási együtthatók a Walsh-alapban csökken a szám növekedésével. a növekedés fontos. Ha az (1) sorozattal ábrázolt függvénynek e nagyságrendig folytonos deriváltja van, és az |A"(m)| derivált modulusának maximális értéke M, akkor az a számú spektrumegyütthatók, amelyek rangja nem kisebb, mint a derivált sorrendje (r > igen), kielégíti az egyenlőtlenséget (Design of specialized..., 1984):

| Ca(g>w) |< М/ 2ш(ш+3)/2. (19)

Ez a fontos egyenlőtlenség az, amely garantálja a Ca spektrális együtthatók gyors konvergenciáját az a szám növekedésével, és kilátásokat nyit a táblázatos információk tömörítésére. Valójában a Walsh-függvény r rangja növekszik az a függvényszámmal, így az r > w feltétel teljesül nagy a számokra. Ez azt jelenti, hogy a (19) becslés a végső tágulási együtthatókra vonatkozik.

2. táblázat: Hatványfüggvények spektrális tágulási együtthatói Walsh-bázisban

RENDELÉSI RANK A FUNKCIÓ FOKOZATA

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

Ha ezen kívül a függvénynek véges számú nullától eltérő deriváltja van (például hatványfüggvény), akkor minden olyan együttható, amelynek a sorszáma nagyobb, mint ez a hatvány, azonosan nullával egyenlő. Ehhez azonban az szükséges, hogy az N szám elég nagy legyen, és a rangot „sikerült” nagyobbá válni, mint a legmagasabb derivált száma. Példaként vegyük egy (1) sorozattal ábrázolt hatványfüggvény spektrális kiterjesztését, ahol a minták száma egyenlő 16 (^ = 16, n = 4). Kis számú mintát választottunk csak a példaeredmények érthetősége érdekében. Fent a táblázatban. A 2. ábra két számjegyre kerekítve mutatja a különböző hatványfüggvények spektrális tágulási együtthatóit: lineáris, másodfokú, köbös és ötödik fok - a spektrum a számának és r rangjának egyidejű jelzésével.

Ez a példa azt mutatja, hogy minél alacsonyabb foka a számsort (1) generáló függvénynek, annál nagyobb mértékben érhető el az ods-ok tömörítése a bővítés során. Ha a sorozat rövid és a fokszám nagy, akkor a tömörítés egyáltalán nem érhető el, ahogy az a függvény ötödik fokánál történik. Ha ugyanazon függvényfok mellett növeljük a sorozat tagok számát és ennek következtében a spektrumegyütthatók számát, akkor a fok

a tömörítés növekszik. Tehát N = 64 négyzetméteren = 7,8%, N = 128 négyzetméteren = 18,0%, N = 256 négyzetméteren = 23,8%.

Közben jegyezzük meg, hogy a Fourier-spektrum esetében a fenti esetek egyikében sem érhető el semmilyen tömörítés - nyilvánvaló a hatványfüggvények trigonometrikus bázisának elégtelensége.

4. Alapképletek a diszkrét Walsh-Paley transzformációhoz

Általában egy adott függvény reprezentációiról beszélünk egy kiválasztott bázison, de ha diszkrét spektrális transzformációval dolgozunk, annak diszkrét értékeinek halmazával van dolgunk. Ezeket a diszkrét értékeket számsorok (1) képviselik.

Tehát a Walsh-Paley függvények (16) rendszerét választjuk funkcionális alapnak, és bemutatjuk ennek a rendszernek a függvények ortogonalitási és normalizálási tulajdonságait kifejező alapképleteket, valamint a hozzá tartozó transzformációs képleteket:

Képlet a közvetlen diszkrét Walsh-transzformációhoz a spektrum előállításához

Ca = (1/N) ZkXkWa(k/N).

Az inverz diszkrét Walsh-transzformáció képlete az eredeti értéksorozat visszaállításához

Xk = EaCaWa(k/N).

A Walsh-függvények ortogonalitásának és normalizálásának feltétele egy diszkrét ponthalmazon

No = (1/N)Zk Wp(k/N) W(k/N) = 0, ha p Ф q és No = 1, ha p = q. Parseval egyenlősége

(1/N) ZkXk2= ЪаСа,

amely az eredeti Xk és új Ca koordinátarendszerekben a vektor négyzetes modulusának egyenlőségét reprezentálja.

5. A szoftver implementáció elemei

A szerző ezt a képletkészletet vette alapul, amikor Pascal-ban összeállított egy programot a diszkrét Fourier- és Walsh-transzformációk eredményeinek összehasonlító elemzéséhez (a ROSAPO szoftvertermék 950347 sz. tanúsítványa, 1995.10.02.). Ebben az esetben a diszkrét transzformációkat gyors Fourier-transzformációként (FFT) és Walsh-transzformációként (WTF) valósították meg 2-es bázissal és időtizedeléssel (Rabinder és Gold, 1978). A táblázatos információk tömörítésénél ennek nincs jelentősége, hiszen a transzformációt ebben az esetben egyszer hajtjuk végre, viszont nagyon fontos az információ valós idejű feldolgozásánál, hogy minél nagyobb számú különböző numerikus sorozatot (táblázatokat, függvényeket) lehessen futtatni. ) minimális idő alatt. Az IL18-DORR PINRO repülőlaboratórium fedélzetén egy hasonló, gyakorlatilag változtatás nélküli programot sikeresen alkalmaztak az operatív spektrális elemzésben. A program két fő része az alábbiakban látható. Ez egy gyors Walsh-transzformációs eljárás, és egy függvény a Walsh-függvény értékének kiszámítására számmal és argumentummal. A teljes program túl sok helyet foglal, ezért nem szerepel itt.

Függvény WolshPaly(Alf, l: integer) : integer; var J, K, x, y, w, maskl, mask2: egész szám; kezdődik

w:=l; maszk1:=l; maszk2:=N div 2; mert K:=0-tól N-l-ig kezdjük

ha (Alf és maszk2)<>0 és (én és maszk1)<>0, majd w:=-w; maszk1:=maszk1*2; maszk2:=maszk2 div 2; vége;

WolshPaly:=w; vége;

Ez a függvény két paramétert vesz fel - a Walsh-függvény Alf-számát és I argumentumát, és magának a Walsh-függvénynek az értékét adja vissza.

Eljárás FastWolshTrans(var ml, m2, m3, m4: masdat); var L, LE, LE1, I, J, IP: egész szám; T1,T2: valós;

beginLE:=1; ha L:=1-től M-ig kezdjük: LE1:=LE; LE:=LE*2;

ha J:=1-től LE1-ig kezdjük: I:=J; ismétlés IP:=I+LEl; T1:=m1; T2:=m2;

Ha L=M, akkor kezdjük

m3: = m1[I]-T1; m4:=m2[I]-T2; m3[I]:=m1[I]+T1; m4[I]:=m2[I]+T2;

m1:=m1[I]-T1; m2:=m2[I]-T2; m1[I]:= m1[I]+T1; m2[I]:=m2[I]+T2;

I:=I+LE; I>N-ig; vége; vége;

/* "D" - közvetlen konverziós jel */

ha TIP="D", akkor kezdődik L:=1-től N-ig kezdje m3[L]:=m3[L]/N; m4[L]:=m4[L]/N; vége;

Az eljárás gyors Walsh-transzformációt hajt végre az eljárásnak az ml és m2 tömbökben továbbított adatokon. A transzformáció eredményét - a Walsh-spektrumot - az eljárás m3 és m4 tömbökben adja vissza. Ha az adatokat normál sorrendben adjuk át egy eljárásnak, az eredmény binárisan fordított sorrendben kerül visszaadásra. Ha a spektrum együtthatók szokásos sorrendjét szeretnénk megkapni, akkor a feldolgozásra szánt eredeti adatokat binárisan invertáljuk. Egy szám bináris inverziója olyan szám, amelyben a bináris számjegyeinek sorrendje megfordul, például a 6 = 110 szám inverziója 3 = 011. Bármely szám megfordításához a Pascal nyelven egy eljárást javasolunk:

Eljárás MASINVERSION(sw: integer; var m1, m2: masdat); var I, J, K, NV2: egész szám; T: igazi; kezdődik NV2:=N div 2;

az I:=1-től az N-1-ig kezdje

ha én

különben kezdődik K:=NV2; míg K

6. Tömörítse a táblázatokat két argumentummal

Az egydimenziós, lineáris táblázatok átalakításait és tömörítését fentebb tárgyaltuk. De a navigációban használt táblázatok többsége kétdimenziós - téglalap alakú mátrix. A tömörítésük kérdése kétféleképpen oldható meg. Az első módszer a táblázat lineárissá alakítása, figyelembe véve, hogy a mátrixtábla sorainak egymás utáni elhelyezésével jön létre, az első sortól kezdve. Ez az út meglehetősen gyakori, mert így egy kétdimenziós tömb tárolódik egy lineárisan szervezett számítógép memóriájában. Ennek a módszernek az az előnye, hogy egy ilyen lineáris táblázat mérete elég nagy ahhoz, hogy a tömörítés hatékony legyen. De potenciális bajok is rejtőznek benne. A mátrix sorainak sorba rendezését követően minden bizonnyal ugrásokat kapunk a függvényben, amikor az egyik sor végéről a következő elejére haladunk. Ezt a nehézséget úgy lehet megkerülni, hogy minden páros sorban megváltoztatjuk az elemek sorrendjét – ezt a sort megfordítjuk. Ennek megfelelően a spektrális együtthatók sorrendje megváltozik. De ez nem bonyolítja, hanem csak a számsorrendet változtatja meg magának a függvénynek az értékeinek visszaállításakor. Tehát, ha a visszaállított függvény értékének száma Npq = (p - 1) M + q volt, ahol p annak a sornak a száma, amelyben M elemszámú, q pedig az oszlop számát, akkor páros soroknál megfordítva ez a szám egyenlő lesz (p - 1) M + (M- q + 1).

A második módszer az, hogy először spektrálisan transzformáljuk a táblázat sorait, majd az így kapott közbenső spektrumot az oszlopok mentén. Ennek a módszernek a hátránya az alacsony tömörítési arány a sorok és oszlopok rövid hossza miatt. Igaz, a tömörítési hatást fokozza a sorok és oszlopok dupla átalakítása. Például, ha a sorok és oszlopok csak 10%-kal vannak tömörítve, a teljes tömörítési hatás 1 - 0,9x0,9 = 0,19 = 19%. Ha például egy táblázat sorai másodfokú törvény szerint, az oszlopok pedig köbtörvény szerint változnak, akkor a teljes tömörítési hatás a táblázat adatai szerint. 2 egyenlő 1-(1-0,188)x(1-0,63) = 0,24 = 24%.

Konkrét példaként bemutatjuk a Laplace-féle integrálfüggvény (Kondrashikhin, 1969) táblázatának transzformációját, amelyet a navigációban a navigáció megbízhatóságának értékelése során használnak. Itt egy 30x10-es mátrix formájában mutatjuk be, azaz. 30 sorból és 10 oszlopból áll. Nincs értelme kétdimenzióssá alakítani: túl kevés (10) elem van a sorokban. Ezért 300 értékből álló lineáris táblázatként alakítjuk át. A példában feltételezzük, hogy 256 = 28 érték van, de kiegészíthetjük a táblázatot nullákkal, és tekinthetjük az értékek számát 512 = 29-nek. Mindkét esetben ugyanazt az eredményt kapjuk: a végső számot a maximum 0,01%-a nagyságrendű nulla-közeli fokú nullák esetén az együttható 46,5%. A függvény visszaállítása az 53,5%-ra tömörített spektrumegyütthatók halmazából hibákat eredményezett: négyzetes átlag 0,005 és maximum 0,057. A példa bemutatja a táblázat transzformáció hatékonyságát.

7. Következtetés

A Walsh-Paley funkcionális bázis kiválasztásával kapcsolatos vizsgálatok azt mutatják, hogy ez a funkcionális alap sikeresen alkalmazható különféle, nem kifejezetten periodikus jellegű információfeldolgozó rendszerekben. Ebben az esetben egy ilyen funkcionális alap előnyei nyilvánvalóak a Fourier-bázissal szemben. Ezenkívül a Walsh-Paley bázis jó hatást ad az információk tömörítésére. Ezt szemlélteti a navigációs megbízhatósági problémákra jellemző Laplace integrál függvénytábla példája, ahol a tömörítési hatás elérte az 53,5%-ot.

Irodalom

Gold B., Rader Ch. Digitális jelfeldolgozás. M., Sov.radio, 367 e., 1993. Kondrashikhin V.T. Hibaelmélet. M., Transport, 256 e., 1969.

Speciális információs és számítástechnikai rendszerek tervezése. Szerk.

Smirnova Yu.N. M., Higher School, 359 e., 1984. Rabinder L., Gold B. A digitális jelfeldolgozás elmélete és alkalmazásai. M., Mir, 528 e., 1978. Trakhtman A.N., Trakhtman V.A. Bevezetés a jelek általános spektrumelméletébe. M., Sov.radio, 312 e., 1978.

A Walsh-függvények függvénycsalád, amely ortogonális rendszert alkot, és csak 1 és -1 értéket vesz fel a teljes definíciós tartományban.

Elvileg a Walsh-függvények ábrázolhatók folyamatos formában, de gyakrabban diszkrét sorozatokként határozzák meg őket. $2^n$ elemeket. Csoportja $2^n$ A Walsh-függvények alkotják a Hadamard-mátrixot.

A Walsh-függvényeket széles körben használják a rádiókommunikációban, ahol a kódosztás MA (CDMA) megvalósítására használják, például olyan cellás szabványokban, mint az IS-95, CDMA2000 vagy UMTS.

A Walsh-függvények rendszere ortonormális alap, és ennek következtében lehetővé teszi, hogy tetszőleges alakú jeleket általánosított Fourier-sorokká bontsunk ki.

A Walsh-függvények kettőnél több értékre történő általánosítása a Vilenkin–Chrestenson függvény.

Kijelölés

Legyen a Walsh-függvény definiálva az intervallumon; ezen az intervallumon kívül a függvény periodikusan megismétlődik. Vezessük be a dimenzió nélküli időt $\theta = t / T$ . Ekkor a k számú Walsh-függvényt jelöljük $wal(k,\théta)$ . A függvények számozása a függvények sorrendjének módjától függ. Van Walsh-rendezés - ebben az esetben a funkciók a fent leírtak szerint vannak kijelölve. Gyakoriak a paley rendelések is ( $pal(p,\théta)$ ) és Hadamard ( $volt(h,\théta)$ ).

A pillanattal kapcsolatban $\théta = 0$ A Walsh-függvények feloszthatók párosra és páratlanra. Úgy vannak kijelölve $cal(k,\théta)$ És $sal(k,\théta)$ illetőleg. Ezek a függvények hasonlóak a trigonometrikus szinuszokhoz és koszinuszokhoz. A függvények közötti kapcsolat a következőképpen fejeződik ki:

$cal(k,\theta) = wal(2k,\theta)$ $sal(k,\theta) = wal(2k-1,\theta)$

Képződés

Számos formációs módszer létezik. Nézzük meg az egyiket, a legvizuálisabbat: A Hadamard-mátrixot rekurzív módszerrel, blokkmátrixok felépítésével a következő általános képlet alapján állíthatjuk elő:

$H_(2^n) = \begin(bmátrix)H_(2^(n-1)) & H_(2^(n-1)) \\ H_(2^(n-1)) & -H_(2^(n-1)) \end(bmátrix)$

Így alakítható ki egy hosszúságú Hadamard-mátrix $2^n$ :

$H_1 = \begin(bmátrix)1\end(bmátrix)$

$H_2 = \begin(bmátrix)1 & 1 \\ 1 & -1 \end(bmátrix)$

$H_4 = \begin(bmátrix)1 & 1 & 1 & 1 \\ 1 & -1 & 1 & -1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \end(bmátrix)$

A Hadamard Mátrix minden sora Walsh-függvény.

Ebben az esetben a függvényeket Hadamard rendeli meg. A Walsh-függvény számának kiszámítása a Hadamard-függvény számából történik úgy, hogy a biteket a szám bináris jelölésében fordított sorrendben átrendezzük, majd az eredményt a Gray-kódból konvertáljuk.

Példa

Az eredmény egy Walsh-mátrix, amelyben a függvények Walsh szerint vannak rendezve:

$W_4 = \begin(bmátrix)1 & 1 & 1 & 1 \\ 1 & 1 & -1 & -1 \\ 1 & -1 & -1 & 1 \\ 1 & -1 & 1 & -1 \end(bmátrix)$

Tulajdonságok

1. Ortogonalitás

Írjon véleményt a "Walsh-függvény" cikkről

Irodalom

Baskakov S. I. Rádiótechnikai áramkörök és jelek. - M.: Felsőiskola, 2005 - ISBN 5-06-003843-2
Golubov B. I., Efimov A. V., Skvortsov V. A. Walsh-sorozat és transzformációk: elmélet és alkalmazások. - M.: Tudomány, 1987
Zalmanzon L. A. Fourier, Walsh, Haar transzformációk és alkalmazása a vezérlésben, kommunikációban és egyéb területeken. - M.: Nauka, 1989 - ISBN 5-02-014094-5

Lásd még

Megjegyzések

A Walsh-függvényt jellemző részlet

– Úgy tűnik, még nem mindenki ment el, herceg – mondta Bagration. - Holnap reggelig, holnap mindent megtudunk.
– A hegyen őrjárat van, excellenciás uram, még mindig ugyanazon a helyen, ahol este volt – jelentette Rosztov, előrehajolva, kezét a szemellenzőhöz tartva, és képtelen volt visszatartani az utazás okozta mulatság mosolyát. és ami a legfontosabb, a golyók hangja által.
– Oké, oké – mondta Bagration –, köszönöm, tiszt úr.
– Excellenciás uram – mondta Rosztov –, engedje meg, hogy megkérdezzem.
- Mi történt?
„Holnap a mi századunkat a tartalékokhoz rendelik; Hadd kérjem, helyezzenek ki az 1. századba.
- Mi a vezetékneved?
- Rosztov gróf.
- Oh jó. Maradj velem, mint rendfőnök.
– Ilja Andreics fia? - mondta Dolgorukov.
De Rosztov nem válaszolt neki.
- Szóval remélem, excellenciás uram.
- Rendelni fogok.
„Holnap talán valamiféle parancsot küldenek az uralkodónak” – gondolta. - Isten áldjon".

A sikolyok és a tüzek az ellenséges hadseregben azért keletkeztek, mert miközben Napóleon parancsát olvasták a csapatok között, maga a császár lovagolt lóháton bivakjait. A katonák, látva a császárt, szalmacsomókat gyújtottak, és azt kiabálva: vive l "Empereur!" futottak utána. Napóleon parancsa a következő volt:
„Katonák! Az orosz hadsereg kiszáll ellened, hogy megbosszulja az osztrák, ulmi hadsereget. Ezek ugyanazok a zászlóaljak, amelyeket Ön legyőzött Gollabrunnnál, és amelyeket azóta folyamatosan üldöztek erre a helyre. Az általunk elfoglalt pozíciók erősek, és miközben a jobb oldalamra mozognak, felfedik a szárnyamat! Katonák! Én magam fogom vezetni a zászlóaljaitokat. Távol maradok a tűztől, ha szokásos bátorságoddal rendetlenséget és zűrzavart viszel az ellenség soraiba; de ha a győzelem csak egy percig is kétséges, akkor császárodat az ellenség első csapásainak kitéve láthatod, mert a győzelemhez nem fér kétség, különösen azon a napon, amelyen a francia gyalogság becsülete, nemzete becsületéhez szükséges.
A sebesültek eltávolításának ürügyén ne háborítsd fel a sorokat! Mindenkit áthat a gondolat, hogy le kell győzni Anglia zsoldosait, akiket a nemzetünk elleni gyűlölet ihletett. Ez a győzelem véget vet a hadjáratunknak, és visszatérhetünk a téli szállásra, ahol a Franciaországban alakuló új francia csapatok találnak bennünket; és akkor a béke, amelyet megkötök, méltó lesz népemhez, hozzád és hozzám.
Napóleon."

Reggel 5 órakor még teljesen sötét volt. A központ csapatai, a tartalékok és Bagration jobbszárnya még mindig mozdulatlanul álltak; de a balszárnyon a gyalogság, lovasság és tüzérség oszlopai, amelyeknek elsőként kellett volna leereszkedniük a magasból, hogy megtámadják a francia jobbszárnyat, és a beosztás szerint visszadobják a Cseh-hegységbe. kavarni kezdtek, és felemelkedtek éjszakai pozíciójukból. A tüzek füstje, amibe beledobtak mindent, ami felesleges, megette a szemem. Hideg volt és sötét. A tisztek sietve ittak teát és reggeliztek, a katonák kekszet rágcsáltak, lábukkal melegedve lövést vertek, a tüzek ellen sereglettek, a tűzifába dobálták a fülkék, székek, asztalok, kerekek, kádak maradványait, mindent, ami fölösleges. nem lehetett magukkal vinni. Az osztrák hadoszlopvezetők az orosz csapatok között suhantak, és a támadás előhírnökeiként szolgáltak. Amint egy osztrák tiszt megjelent az ezredparancsnoki tábor közelében, az ezred megmozdult: a katonák elfutottak a tüzek elől, csöveket rejtettek a csizmáikba, táskákat a szekereikbe, leszerelték fegyvereiket és felsorakoztak. A tisztek begombolták magukat, felvették kardjukat és hátizsákjukat, és kiabálva járták körbe a sorokat; A vagonvonatok és a rendõrök felszerelték, pakolták és megkötözték a szekereket. Adjutánsok, zászlóalj- és ezredparancsnokok lóháton ültek, keresztet vetettek, kiadták az utolsó parancsokat, utasításokat, utasításokat a megmaradt konvojoknak, és megszólalt az ezer láb monoton csavargása. Az oszlopok mozogtak, nem tudták, hová, és nem látták a körülöttük lévő emberektől, a füsttől és a növekvő ködtől sem azt a területet, ahonnan távoztak, sem azt, ahová belépnek.
A mozgásban lévő katonát éppúgy körülveszi, korlátozza és vonzza az ezred, mint egy tengerészt a hajó, amelyen tartózkodik. Bármilyen messzire megy is, bármilyen furcsa, ismeretlen és veszélyes szélességi körökbe lép be, körülötte - mint egy tengerésznél, mindig és mindenütt ugyanazok a fedélzetek, árbocok, a hajójának kötelei - mindig és mindenhol ugyanazok az elvtársak, ugyanazok a sorok, ugyanaz az őrmester, Ivan Mitrich, ugyanaz a társasági kutya Zhuchka, ugyanazok a felettesek. Egy katona ritkán akarja tudni azokat a szélességi fokokat, amelyeken az egész hajója található; de a csata napján, Isten tudja, hogyan és honnan, a hadsereg erkölcsi világában mindenki számára egy szigorú hang hallatszik, amely valami határozott és ünnepélyes közeledtének hangzik, és szokatlan kíváncsiságra ébreszti. A csata napjaiban a katonák izgatottan próbálnak kilépni ezredük érdekei közül, hallgatnak, alaposan szemügyre vesznek, és lelkesen kérdezik, mi történik körülöttük.
A köd olyan erős lett, hogy hiába hajnalodott, nem lehetett látni tíz lépést maga előtt. A bokrok hatalmas fáknak, a sík helyek szikláknak és lejtőknek tűntek. Mindenhol, minden oldalról tíz lépésnyire egy láthatatlan ellenséggel lehetett találkozni. De az oszlopok sokáig ugyanabban a ködben jártak, le-fel a hegyekre, kertek és kerítések mellett haladtak át, új, felfoghatatlan terepen, soha nem találkoztak az ellenséggel. Ellenkezőleg, most elöl, most hátul, minden oldalról megtudták a katonák, hogy orosz oszlopaink ugyanabba az irányba haladnak. Minden katona jól érezte magát a lelkében, mert tudta, hogy ugyanoda, ahová ő megy, vagyis ismeretlenül hova, még sok-sok a miénk jár.
– Nézze, a kurszki katonák elhaladtak – mondták a sorokban.
- Szenvedély, testvérem, hogy csapataink összegyűltek! Este megnéztem, hogyan vannak elhelyezve a lámpák, nem látszott a vége. Moszkva - egy szó!
Bár az oszlopparancsnokok egyike sem közeledett a sorokhoz és nem beszélt a katonákkal (az oszlopparancsnokok, mint a katonai tanácson láttuk, nem voltak jó hangulatban és elégedetlenek a vállalkozással, ezért csak parancsokat hajtottak végre, és nem törődtek a mulatsággal a katonák), annak ellenére A katonák azonban, mint mindig, vidáman lépkedtek, akcióba lendültek, különösen támadólag. De miután körülbelül egy órát gyalogolt sűrű ködben, a hadsereg nagy részének meg kellett állnia, és a folyamatos rendetlenség és zavarodottság kellemetlen tudata söpört végig a sorokon. Nagyon nehéz meghatározni, hogyan közvetítik ezt a tudatot; de az biztos, hogy szokatlanul hűségesen terjed, és gyorsan, észrevehetetlenül és ellenőrizhetetlenül terjed, mint a víz a szakadékban. Ha az orosz hadsereg egyedül lett volna, szövetségesek nélkül, akkor talán sok idő telt volna el, mire ez a rendetlenség tudata általános bizalommá vált volna; de most különös örömmel és természetességgel a nyugtalanság okát az ostoba németeknek tulajdonítva mindenki meg volt győződve arról, hogy a kolbászkészítők káros zűrzavart okoztak.

A mérnökök olyan jeleket választottak ki, amelyek használatának célja a rendszerek alapvető jellemzőinek (kommunikációs minőség, zajtűrés) javítása, kizárólag az intuíciójukra támaszkodva. A fordulópont a jelképzés, -feldolgozás és -átvitel elméletének megalkotása volt. Lehetővé teszi, hogy meghatározza a jelek egy adott együttese (készlete) használatának hatékonyságát, csak az auto- és interkorrelációs jellemzőik ismerete alapján.

Alapfogalmak

A CDMA rendszerekben jelátvitelre használt kódszekvenciák N elemi szimbólumból (chipből) állnak. A jel minden információs szimbóluma hozzáadódik egy N-szimbólum sorozathoz, amelyet „szórási szekvenciának” neveznek, mivel az „eredmény” jelet szándékosan szétszórt spektrummal bocsátják ki a levegőbe. A kommunikáció minőségének növekedése a sorozat szimbólumainak számától (hosszától), valamint a jelkészlet jellemzőitől, elsősorban azok keresztkorrelációs tulajdonságaitól és modulációs módszerétől függ.

Sorozat hossza. A hazai szakirodalomban komplexnek szokták nevezni azokat a jeleket, amelyek bázisa lényegesen nagyobb az egységnél (B=TF>>1, ahol T a jelelem időtartama, F a frekvenciasáv). Az eredeti (információs) jelhez képest komplex jel közel azonos spektrális teljesítménysűrűségű zaj.

Köztudott, hogy minél „nyújtottabb” egy jel spektruma a levegőben, annál kisebb a spektrális sűrűsége. Ennek a tulajdonságnak köszönhetően a nagy bázisú jelek „másodlagos jelleggel” „idegen” (már foglalt) frekvenciasávban használhatók, tetszőlegesen kis hatással az ott működő rendszerre.

Jellemzők. A CDMA-ban használt kódszekvenciák teljes készlete két fő osztályra oszlik: ortogonális (kvázi-ortogonális) és pszeudo-véletlenszerű szekvenciákra (PSR), alacsony szintű keresztkorrelációval (1. ábra).

Egy optimális CDMA-vevőben a bejövő jeleket, amelyek lényegében additív fehér Gauss-zaj, mindig korrelációs módszerekkel dolgozzák fel. Ezért a keresési eljárás egy olyan jel megtalálására redukálódik, amely maximálisan korrelál az egyéni előfizetői kóddal. A két sorozat (x(t)) és (y(t)) közötti korrelációt úgy végezzük, hogy az egyik sorozatot megszorozzuk a másik időeltolásos másolatával. A szekvencia típusától függően a CDMA rendszerek különböző korrelációs módszereket alkalmaznak:

autokorreláció, ha a szorzott pszeudo-véletlen sorozatok alakja azonos, de időben eltolódnak;
kölcsönös, ha a PSP-k különböző típusúak;
periodikus, ha két PSP közötti eltolódás ciklikus;
időszakos, ha az eltolódás nem ciklikus;
a periódus egy részén, ha a szorzás eredménye csak két meghatározott hosszúságú sorozat szegmensét tartalmazza.

Ahhoz, hogy bármely korrelációs feldolgozási módszerrel javuljon a kommunikáció minősége, szükséges, hogy a jelek együttese „jó” autokorrelációs tulajdonságokkal rendelkezzen. Kívánatos, hogy a jeleknek egyetlen autokorrelációs csúcsuk legyen, ellenkező esetben hamis szinkronizálás lehetséges az autokorrelációs függvény (ACF) oldallebenye mentén. Vegye figyelembe, hogy minél szélesebb a kibocsátott jelek spektruma, annál szűkebb az ACF központi csúcsa (főlebenye).

A kódsorozatok párjait úgy választja ki, hogy a keresztkorrelációs függvény (MCF) páronkénti korrelációjuk minimális értéke legyen. Ez garantálja a kölcsönös interferencia minimális szintjét.

Következésképpen a CDMA-ban a jelek optimális együttesének megválasztása a kódszekvenciák olyan struktúrájának a keresését jelenti, amelyben az ACF központi csúcsa a legmagasabb szintű, és az ACF oldalsó lebenyei és az ACF maximális tüskéi lehetőleg minimálisan.

Ortogonális kódok

Az ortogonális kódsorozatokat a képzés módjától és a statisztikai tulajdonságoktól függően ténylegesen ortogonálisra és kvázi-ortogonálisra osztják. A sorozat jellegzetessége a pij keresztkorrelációs együttható, amely általában -1 és +1 között változik.

A jelelméletben bebizonyosodott, hogy a keresztkorrelációs együttható maximális elérhető értékét a feltétel határozza meg.

A VCF minimális értéke olyan kódokat biztosít, amelyekben a korrelációs együtthatók bármely sorozatpárra negatívak ( transzortogonális kódok). Keresztkorrelációs együttható ortogonális szekvenciák definíció szerint egyenlő nullával, azaz. Ó? ij =0. Nagy N értékek esetén az ortogonális és transzortogonális kódok korrelációs együtthatói közötti különbség gyakorlatilag elhanyagolható.

Az ortogonális kódok létrehozásának többféle módja van. A legelterjedtebb a 2n hosszú Walsh-szekvenciák használata, amelyeket a Hadamard-mátrix sorai alapján alakítanak ki.

Az eljárás többszöri megismétlésével tetszőleges méretű mátrixot hozhat létre, amelyet az összes sor és oszlop kölcsönös ortogonalitása jellemez.

A jelek előállításának ezt a módszerét az IS-95 szabvány implementálja, ahol a Walsh-szekvenciák hosszát 64-re választják. Vegye figyelembe, hogy a Hadamard-mátrix és a Walsh-szekvenciák sorai között csak az a különbség, hogy az utóbbiak unipólusjeleket használnak. az (1,0) formából.

A Hadamard-mátrixot példaként használva könnyen szemléltethetjük a transzortogonális kódok felépítésének elvét. Így ellenőrizhetjük, hogy ha az első csak egyből álló oszlopot töröljük a mátrixból, akkor az ortogonális Walsh-kódok transzortogonálisakká alakulnak, amelyekben bármely két sorozat esetén a szimbólum eltérések száma pontosan eggyel meghaladja az egyezések számát, azaz Ó? ij = -1/(N-1).

Az ortogonális kódok másik fontos típusa az biortogonális egy ortogonális kódból és annak inverziójából kialakított kód. A biortogonális kódok fő előnye az ortogonális kódokhoz képest, hogy képesek a jelet a frekvenciasáv felében továbbítani. Például a WCDMA-ban használt biortogonális blokkkód (32,6) lehetővé teszi egy TFI átviteli formátumú jel átvitelét.

Vegye figyelembe, hogy az ortogonális kódoknak két alapvető hátránya van.

1. A lehetséges kódok maximális számát a hosszúságuk korlátozza (az IS-95 szabványban a kódok száma 64), ennek megfelelően korlátozott címterűek.

A jelek együttesének bővítése az ortogonális jelekkel együtt kvázi-ortogonális sorozatok. Így a cdma2000 szabvány tervezete eljárást javasol kvázi-ortogonális kódok generálására Walsh-szekvenciák egy speciális maszkolási függvénnyel való megszorzásával. Ez a módszer lehetővé teszi kvázi-ortogonális sorozatok kvázi-ortogonális függvénykészletének (QOFS) előállítását egy ilyen függvény használatával. M maszkoló függvény és egy 2n hosszú Walsh-kód együttes használatával (m+1) 2n QOF sorozatot hozhatunk létre.

2. Az ortogonális kódok másik hátránya (és az IS-95 szabványban használtak sem kivételek), hogy a keresztkorrelációs függvény csak „egy ponton” egyenlő nullával, azaz. kódok közötti időeltolás hiányában. Ezért az ilyen jeleket csak szinkron rendszerekben és főként közvetlen csatornákon (a bázisállomástól az előfizetőig) használják.

A CDMA rendszer különböző átviteli sebességekhez való adaptálása speciális, változó szórási tényezőjű ortogonális sorozatok (OVSF, Orthogonal Variable Spreading Factor) használatával érhető el, ún. változó hosszúságú kódok. Az ilyen szekvenciával létrehozott CDMA jel továbbításakor a chip sebessége állandó marad, de az információ sebessége kétszeresére változik. A 3. generációs szabványok több átviteli sebességű (többsebességű) ortogonális Gold kódok használatát javasolják OVSF kódként. Kialakításuk elve meglehetősen egyszerű; ábra elmagyarázza. 3, amely egy kódfát mutat, amely lehetővé teszi különböző hosszúságú kódok felépítését.

A kódfa minden szintje meghatározza a kódszavak hosszát (szórási tényező, SF), minden következő szint megduplázza a lehetséges kódok számát. Tehát, ha a 2. szinten csak két kód generálható (SF=2), akkor a 3. szinten négy kódszó (SF=4) generálódik stb. A teljes kódfa nyolc szintet tartalmaz, ami SF=256-nak felel meg (az ábrán csak az alsó három szint látható).

Így az OVSF kódok együttese nem fix: az SF szórási tényezőtől függ, pl. valójában a csatorna sebességétől függ.

Meg kell jegyezni, hogy nem minden kódfa-kombináció valósítható meg egyidejűleg ugyanabban a CDMA-cellában. A kombináció kiválasztásának fő feltétele az ortogonalitásuk megsértésének elfogadhatatlansága.

Pszeudo-véletlen sorozatok

Az ortogonális kódok mellett a CDMA rendszerekben kulcsszerepet játszik a PRP, amely bár determinisztikus módon generálódik, a véletlen jelek összes tulajdonságával rendelkezik. Azonban előnyösen különböznek az ortogonális sorozatoktól, mivel invariánsak az időeltolódásokra. Számos PSP-típus létezik, amelyek eltérő tulajdonságokkal rendelkeznek. Egyszerűen fogalmazva, napjainkra olyan technikai eszközök jelentek meg, amelyek adott tulajdonságú sorozatok tetszőleges együttesét képesek „levezetni”.

m-szekvenciák

A bináris determinisztikus sorozatok előállításának egyik legegyszerűbb és rendkívül hatékony módja a shift regiszter (RS) használata. A visszacsatolással rendelkező n-bites PC kimenetén a sorrend mindig periodikus, és az n periódusa (azon ciklusok száma, amelyek után az áramkör visszatér eredeti állapotába) nem haladja meg a 2n-t.

Elméletileg egy n-bites regiszter és megfelelően megválasztott visszacsatolási logika használatával tetszőleges N hosszúságú sorozatot kaphatunk az 1-2 n tartományban. A maximális hosszúságú sorozat vagy m-sorozat periódusa 2 n -1.

Az m-szekvencia autokorrelációs függvény periodikus és kétértékű:

Az autokorrelációs függvény oldalmaximumainak szintje (4. ábra) nem haladja meg az értéket

Kódok Golda két m-sorozat karakterenkénti összeadása modulo 2-vel jönnek létre (5. ábra). A WCDMA-tervezet háromféle Gold kódot határoz meg: elsődleges és másodlagos ortogonális Gold kódot (mindkettő 256 bit hosszú) és hosszú kódot.

Az ortogonális Gold kódok 255 bites m-sorozat alapján jönnek létre, egy redundáns szimbólum hozzáadásával. Az elsődleges szinkronizációs kód időszakos autokorrelációs funkcióval rendelkezik, és a kezdeti szinkronizáláshoz használatos. A másodlagos szinkronkód egy modulálatlan ortogonális Gold kód, amelyet az elsődleges szinkronkóddal párhuzamosan továbbítanak. Minden másodlagos szinkronkód 17 különböző Gold kódból van kiválasztva (C1,...,C17).

Az előremenő csatorna hosszú kódja 40 960 chip hosszú Gold kódrészlet. A WCDMA-alapú kommunikációs rendszer aszinkron, és a szomszédos bázisállomások különböző Gold kódokat (összesen 512-t) használnak, 10 ms-onként ismétlődően. A bázisállomások aszinkron működési elve függetlenné teszi őket a külső szinkronizációs forrásoktól. Célja, hogy hosszú kódot használjon a visszirányú csatornában, de csak azokban a cellákban, ahol a többfelhasználós észlelési mód nincs engedélyezve.

Kódcsalád Kasami 2 k szekvenciát tartalmaz 2 n-1 periódussal. Optimálisnak tekinthetők abban az értelemben, hogy bármely „preferált” pár esetében biztosított az autokorrelációs függvény maximális értéke, amely egyenlő (1 + 2 k).

A Kasami kódsorozatokat három, sorba kapcsolt (u, v és w) eltolási regiszter segítségével valósítják meg különféle visszacsatolásokkal (6. ábra), amelyek mindegyike saját m-sorozatot alkot. Ahhoz, hogy adott tulajdonságokkal rendelkező Kasami kódsorozatokat kapjunk, a v és w szekvenciáknak különböző eltolódásokkal kell rendelkezniük.

A 256 bites Kasami kódok rövid sorozatként használatosak a visszatérési csatornában (WCDMA projekt) azokban a cellákban, amelyek többfelhasználós észlelést használnak.

Barker szekvenciák

A kis aperiodikus ACF értékű pszeudovéletlen sorozatok képesek biztosítani a továbbított és vett jelek szinkronizálását meglehetősen rövid időn belül, általában magának a sorozatnak a hosszával. A Barker-szekvenciák a leghíresebbek (lásd a táblázatot).

Az aperiodikus ACF-vel rendelkező sorozatok hatékonyságát általában az F minőségjelzővel mérik, amelyet a jel fázison belüli összetevőinek négyzeteinek és a fázison kívüli összetevőinek négyzetösszegének arányaként határoznak meg. Így egy bináris sorozat aperiodikus korrelációjának hatékonyságának mérőszáma a minőségi mutató.

A Walsh-függvények függvénycsalád, amely ortogonális rendszert alkot, és csak 1 és -1 értéket vesz fel a teljes definíciós tartományban.

Elvileg a Walsh-függvények ábrázolhatók folytonos formában, de gyakrabban 2^n (\displaystyle 2^(n))22 elemből álló diszkrét sorozatokként határozzák meg őket. A (\displaystyle 2^(n))2^n Walsh-függvény egy csoportja alkotja a Hadamard-mátrixot.

A Walsh-függvények rendszere ortonormális alap, és ennek következtében lehetővé teszi, hogy tetszőleges alakú jeleket általánosított Fourier-sorokká bontsunk ki.

A Walsh-függvények kettőnél több értékre történő általánosítása a Vilenkin-Chrestenson függvény.

M-szekvenciák. M-sorozatok kialakításának módja és tulajdonságai. M-szekvenciák alkalmazása kommunikációs rendszerekben

Jelenleg a hosszú hosszúságú bináris kódszekvenciák közül a legszélesebb körben használtak az M-szekvenciák, a Legendre-szekvenciák, a Gold és a Cassami kódszekvenciák, a Walsh-kódszekvenciák és a nemlineáris kódszekvenciák.

A hosszú M-szekvenciák előnye, hogy az M-szekvencia bizonytalansági függvény periodikus oldallebenyeinek szintje hosszának növekedésével csökken. L. Egy M-sorozat TCF periódusos oldallebenyének maximális szintje fordítottan arányos a szekvencia hosszával (1/L).

M-szekvenciák

Fentebb már említettük, hogy a maximális hosszúságú vagy M-szekvenciák optimálisak a jelspektrum bővítésére. Az ilyen szekvenciákat digitális gépek segítségével alakítják ki, amelyek fő eleme egy memóriacellákkal ellátott váltóregiszter T1, T2, …, T k(2. ábra).

2. ábra – Digitális automata M-sorozat kialakításához

Az óraimpulzusok egyidejűleg érkeznek minden cellába egy periódussal, az ezekben a cellákban tárolt szimbólumokat egy óraciklus alatt a jobb oldali cellákba mozgatják. Jelöljük betűkkel a ciklusban a megfelelő cellákban tárolt szimbólumokat. - szimbólum az első cella bemenetén; ennek a szimbólumnak az értéke lineáris ismétlődési reláció segítségével kerül kialakításra

A számot tartalmazó cellában lévő szimbólum értékének megfelelően megszorozzuk egy együtthatóval, és hozzáadjuk más hasonló termékekhez. Mind a szimbólumok, mind az együtthatók értéke 0 vagy 1 lehet; összegzési műveleteket hajtunk végre modulo 2. Ha az együttható , akkor a cella szimbólum nem vesz részt az összeg érték kialakításában.

Ha a shift regiszter cellák tartalmát vesszük kiindulási állapotnak, akkor órajelciklusok után ismét ez az állapot áll elő. Ha egyidejűleg regisztráljuk a -edik cella szimbólumsorozatát, akkor ennek a sorozatnak a hossza egyenlő lesz. A következő intézkedéseknél ez a sorrend ismét megismétlődik stb. A számot a sorozat periódusának nevezzük. A rögzített műszakregiszter hosszának értéke a leágazások számától és helyétől függ. Minden egyes értéknél megadhatja az érintések számát és azok pozícióit, amelyeknél az eredményül kapott sorozat periódusa maximális. Az eltolási regiszter bármely állapota (a nulla kombináció kivételével) kezdő állapotnak tekinthető; a kezdeti állapot megváltoztatása csak sorozateltolódást okoz. Azokat a szekvenciákat, amelyeknél a fix regiszterhosszúságnál a lehető legnagyobb időtartam van, M-sorozatoknak nevezzük. Időszakuk (hosszuk).

Az M-sorozatokat generáló automata blokkdiagramját általában egy karakterisztikus polinom adja meg:

amelyben mindig , . táblázatban 1 ennek a polinomnak az együtthatóinak értékkészleteihez, amelyek a maximális hosszúságú sorozatokat határozzák meg. Vektor tudás lehetővé teszi egy digitális automata szerkezetének egyértelmű jelzését, amely a megfelelő polinom (1.16) M-sorozatot alkotja:

– ha , akkor a shift regiszterszámú cella kimenete a modulo 2 összeadóhoz csatlakozik;

– ha , akkor a shift regiszterszámú cella kimenete nincs csatlakoztatva a modulo 2 összeadóhoz.(hosszú kód a kódoláshoz és a mobilállomások azonosításához)

Számos elemzési feladat megoldása során célszerű egy komplex jelet elemi jelek halmazaként ábrázolni. A gyakorlatban a jelábrázolás találta a legnagyobb alkalmazást utca), intervallumon megadva, néhány elemi függvény lineáris kombinációja formájában (p t (t), / = 0,1,2,..., alapnak nevezzük

- az alapfüggvény normája.

A jel ilyen formában történő ábrázolását általánosított Fourier-sornak nevezzük. Gyakran trigonometrikus függvényrendszert használnak alapfüggvényként.

vagy összetett exponenciális függvények rendszere

Az utóbbi években azonban a jelátvitel és -feldolgozás digitális módszereinek fejlődésével a diszkrét ortogonális sorozatokat Rademacher, Walsh, Haar stb. függvények formájában kezdik bázisfüggvényként használni.

Vezessük be a dimenzió nélküli időt 0 = t / T . Rademacher függvények reláció segítségével szinuszos függvényekből képezzük

Más szóval, a ±1 értékeket felvevő Rademacher-függvények „téglalap szinusz” függvényekként értelmezhetők. Az első négy Rademacher-függvény grafikonja úgy néz ki, mint a 4.12. ábra.

Rademacher funkciórendszer r k(0) ortonormális a 0 intervallumon

Walsh függvényrendszer a Rademacher-függvények rendszerének kiterjesztése egy teljes rendszerre, és a következőképpen definiálható

Ahol kf- jelentése j számjegy a számrekordban Nak nek szürke kódban. Például,

mivel 5=>101 2 =>111 g Az első négy Walsh-függvény grafikonja a 4.13.

Rizs. 4.13.

A Walsh-függvények a következő tulajdonságokkal rendelkeznek:

1. séta(®) = ± 1.
2. | wal k (0)| = 1, 2 = 1.

5. A Walsh-függvények szorzata Walsh-függvényt ad, de más sorrendben wal k (0) wal n (0) = walj (0), j = k ® n,

wal k (0 2) wal k (0 2) = wal k(0 3), 0 3 = 0j ® 0 2, ahol © a modulo kettes összeadás.

Egyes esetekben az űrlap Walsh-függvényeit használják

Ha Walsh-függvények rendszerét használjuk bázisfüggvényként, akkor a jel alakban ábrázolható

Walsh-Fourier együtthatók halmaza (q) ill (a k f k)és a függvények sorszámainak halmaza alkotja a jel spektrumát a Walsh-bázisban, amelyet a rövidség kedvéért néha S-spektrumnak is neveznek.

Például egy jel, amely négyszögletes impulzusok periodikus sorozata (4.14. ábra), a (4.39) kifejezés által meghatározott S-spektrummal rendelkezik.

Rizs. 4.14.

téglalap alakú impulzusok

Hadd n= 3, akkor erre az esetre megkapjuk a 4.15. ábrán látható S-spektrumot.

Rizs. 4.15.

Így a szokásos frekvenciaspektrummal ellentétben egy téglalap alakú impulzussorozat S-spektruma végesnek bizonyul. Meg kell jegyezni, hogy az impulzusok időbeni eltolódása az S-spektrum szerkezetének megváltozásához vezet. Különösen új alkatrészek jelennek meg. Például egy sorozathoz n= 3 impulzus 0=1/16-kal eltolva az S-spektrum úgy néz ki, mint a 4.16. ábrán, míg a trigonometrikus függvényrendszer használatakor az időeltolás csak a fázisspektrumot változtatja meg.

A Walsh-függvényekre logikai műveletek alkalmazásának lehetősége miatt mikroprocesszoros technológián alapuló jelgeneráló és -átalakító eszközök fejlesztésében használják őket. A Walsh-függvényeken alapuló jeleket digitális többcsatornás információátviteli rendszerekben használják.

Rizs. 4.16.

0=1/16-kal eltolva

Haar funkciós rendszer darabonként állandó függvényekből áll har k(0), a 0 intervallumon megadva

Ahol T- a legjelentősebb nem nulla számjegy száma egy szám bináris ábrázolásában

Nak nek mod2 w - érték Nak nek modulo 2 t, a legkisebb maradék egy szám osztásakor Nak nek tovább 2 t. Számos Haar-függvény grafikonja látható a 4.17. ábrán.

Rizs. 4.17.

Ha a jel spektrumát a Haar bázisban vesszük figyelembe, akkor az S-spektrumhoz hasonlóan, amikor a jel időben eltolódik, a spektrum szerkezete megváltozik.

A Haar-funkciókat vezérlő- és kommunikációs rendszerekben, digitális szűrők fejlesztésében, információtömörítésben használják – ezek például a fekete-fehér fényképek Haar-funkciókon alapuló különféle tömörítési módszerei a tömörített képek későbbi továbbítására kommunikációs csatornákon, ill. archiválásukat.

Walsh-kód sorozatok, kialakulásuk

Hogyan gratuláljunk a böjt végéhez a ramadán hónapban?