Sieci wielodostępu z podziałem kodowym i sieci CDMA. Funkcje Walsha

System IS95c (CDMA-2000-1x) wykorzystuje technologię wielodostępu z podziałem kodowym (patrz PSP i charakterystyka), dzięki zastosowaniu tej technologii sposób adresowania kanałów, stacji mobilnych i bazowych w systemie realizowany jest również z wykorzystaniem kodów w specjalny sposób. Aby wyjaśnić zasady zaimplementowane w tym systemie, w tej sekcji najpierw zostaną wyjaśnione niektóre koncepcje techniczne, a następnie szczegółowo omówione zostaną problemy.

Konfiguracja kanału radiowego

Konfiguracja radiowa (RC) definiuje konfigurację kanałów fizycznych w oparciu o określoną szybkość transmisji danych. Każdy RC definiuje zestaw szybkości transmisji danych w oparciu o 9,6 lub 14,4 kbit/s. Są to dwie istniejące szybkości transmisji danych obsługiwane przez IS95c. Każdy RC definiuje również szerokość widmową (szybkość rozprzestrzeniania SR1) i typ kodowania. Obecnie w cdma2000-1x zdefiniowanych jest pięć konfiguracji łącza radiowego dla łącza nadawczego i trzy dla łącza zwrotnego.

Szybkość rozprowadzania: Prędkość chipa kanału do przodu lub do tyłu IS95c wykorzystuje SR1 (Szybkość rozprowadzania 1): Taka sama jak „1XRTT”. Kanały CDMA do przodu i do tyłu wykorzystują widmo rozproszone do przodu z sekwencją pseudolosową przy szybkości chipa 1,2288 MHz.

Konfiguracja RC2 oparta na prędkości 14,4 kbit/s obsługuje również prędkości 9,6, 4,8, 2,4 i 1,5 kbit/s dla głosu działającego w SR1 n=9 R=1/2.

Konfiguracja RC3 bazująca na 9,6 kbps obsługuje także dla głosu 4,8, 2,7 i 1,5 kbps, natomiast dla strumieni danych stosowane są konfiguracje z kodem kanału - obsługujące prędkości 19,2, 38,4, 76,8 i 153,6 kbps/s oraz działa w SR1 i wykorzystuje kodowanie kanałów z parametrami n=9 R=1/2.

Konfiguracja RC4 do transmisji danych wykorzystuje strumienie ze zmianą kodu kanału - obsługujące prędkości 9,6, 19,2, 38,4, 76,8, 153,6 i 307,2 kbit/s oraz działa w trybie SR1 i wykorzystuje kody turbo.

RC5 - używany tylko do transmisji danych, wykorzystywane są strumienie z konfiguracjami kodu kanałowego - obsługa prędkości 14,4, 28,8, 57,6, 115,2 i 230,4 działa w SR1 wykorzystuje specjalne. kodowania i dzięki ustandaryzowanemu zakresowi prędkości jest najbardziej preferowaną konfiguracją do transmisji danych.

Konfiguracja RC określa także tryb pracy toru transmisji radiowej, np. tryb RC3 wykorzystuje nową metodę modulacji, patrz rys. 1, a tryb RC1 jest w pełni kompatybilny z IS95a CCC, patrz. zdjęcie 1.

W tej sekcji rozważymy system w trybie RC1.

Kody stosowane w systemie IS-95c.

SSMS wykorzystuje trzy typy kodów: krótkie i długie m-sekwencje oraz kody Walsha.

Krótki PSP

Krótki PSP składa się z dwóch pseudolosowych sekwencji szyfrujących PSP - I i PSP - Q (symbole I i Q odpowiadają celowi fizycznemu i wskazują składowe w fazie i kwadraturę w modulatorze). Okres każdego z wymienionych PSP zawiera 215 żetonów, których częstotliwość powtarzania według normy wynosi 1,2288 Mchip/s. Bezpośrednie obliczenia pokazują, że dokładnie 75 okresów krótkiego PSP mieści się w jednym dwusekundowym segmencie. Strukturalnie krótkie PSP to M - sekwencje długości

N=2-1 z charakterystycznymi wielomianami

fa ja = x 15 + x 13 + x 9 + x 8 + x 7 + x 5 +1 i

f Pytanie = X 15 + X 12 + X 11 + X 10 + X 6 + X 5 + X 4 + X 3 +1,

przedłużony poprzez dodanie symbolu zera do łańcucha 14 kolejnych zer w każdym okresie.

Długie PSP

Długie symbole PSP mają częstotliwość powtarzania 1,2288 Mchip/s. Tworzenie długiego PSP odbywa się za pomocą wielomianu

F( X) = x 42 + x 35 + x 33 + x 31 + x 27 + x 26 + x 25 + x 22 + x 21 + x 19 + + X 18 + X 17 + X 16 + X 10 + X 7 + X 6 + X 5 + X 3 + X 2 + X + 1.

Kody Walsha

Kody Walsha stosowane w systemie oznaczane są jako: W n N , gdzie N to długość kodu, n to wiersz macierzy Walsha-Hadamarda. Macierz ta jest konstruowana za pomocą algorytmu iteracyjnego (patrz rys. 2). W każdej iteracji każde słowo kodowe uzyskane w poprzednim kroku jest konwertowane na dwa nowe poprzez podwojenie długości poprzez dwukrotne powtórzenie jednego słowa i powtórzenie ze zmianą znaku w drugim. Jeśli więc C k , określone słowo otrzymane w k-tym kroku, to jego „potomkami” w k+1-tym kroku będą słowa postaci (C k ,C k),(C k ,-C k) , wychodząc w ten sposób z trywialnych słów o długości 1 równej 1, w k iteracjach można otrzymać 2 k wektorów kodowych o długości N=2 k, których ortogonalność jest oczywista (patrz rys. 2.).

Za pomocą tej metody można utworzyć kod Walsha, którego wymiar jest równy 2 k X 2 k(k- Dodatnia liczba całkowita). Zbiór kodów Walsha charakteryzuje się macierzą 64 x 64 (RC1) lub 128 x 128 (RC3), gdzie każdy wiersz odpowiada osobnemu kodowi. Ponieważ elementy zbioru kodowego Walsha są wzajemnie ortogonalne, ich zastosowanie umożliwia podzielenie kanału komunikacyjnego nadawczego na 64 (RC1) lub 128 (RC3) sygnałów ortogonalnych.

Bezpośrednie adresowanie kanałów

Adresowanie kanałów.

Kanał nadawczy cdma2000-1x, zachowując kompatybilność z IS95a, wykorzystuje tę samą strukturę dla pilota kanału nadawczego (F-Pilot), kanału synchronizacji (F-Sync) i sygnalizacji (F-Paging).

Również w CDMA2000-1x każdemu użytkownikowi przypisany jest własny kanał ruchu bezpośredniego (F-Traffic), który może obejmować:

Osiem dodatkowych kanałów (F-SCCH) dla RC1 i RC2;

Trzy dodatkowe kanały (F-SCH) dla RC3 do RC9;

Dwa dedykowane kanały sterujące (F-DCCH);

Kanały F-FCH służą do transmisji głosu, kanały F-SCCH i F-SCH służą do transmisji danych. Bazowa stacja nadawczo-odbiorcza może również wysyłać zerowy lub pierwszy kanał F-DCCH. Kanał F-DCCH jest powiązany z kanałami ruchu (albo FCH i SCH, albo SCCH) i może zawierać dane sygnalizacyjne oraz dane sterujące mocą nadawania.

W tej instrukcji przyjrzymy się bliżej głównym kanałom:

kanał pilotażowy (kanał pilota f);

kanał synchronizacji (kanał f-synchronizacji);

osobisty kanał rozmów (f-stronicowanie kanał);

bezpośredni kanał ruchu (kanał ruchu do przodu).

W trybie RC1 mapowanie kanałów logicznych na kanały fizyczne w kierunku do przodu odbywa się za pomocą układu ortogonalnych funkcji Walsha o długości 64: w ja, ja= 0,1,..., 63, gdzie i jest numerem funkcji Walsha. Standard CDMA-2000 przewiduje organizację jednego kanału pilotażowego, jednego kanału synchronizacji, od jednego do siedmiu kanałów wywoławczych (w zależności od obciążenia abonentów na stacji bazowej) i od 55 do 62 kanałów ruchu bezpośredniego, ponieważ można wykorzystać niektóre kanały wywoławcze jako kanały ruchu. Zależność między kanałami logicznymi i fizycznymi pokazano na ryc. 4.

W trybie RC3 mapowanie kanałów logicznych na kanały fizyczne odbywa się analogicznie jak w trybie RC1, z tą tylko różnicą, że dzięki zastosowaniu kwadraturowej modulacji fazy zwiększa się liczbę wykorzystywanych kodów Walsha z 64 do 128 - odpowiednio liczba możliwych adresowalnych kanałów jest podwojona w porównaniu z trybem RC1.

1. Kanał pilotażowy

Według ryc. Kanałowi pilota 5 przypisano zerową funkcję Walsha w0 , czyli ciąg samych zer.

2. Kanał synchronizacja

Po przeplataniu bloków strumień danych jest bezpośrednio rozpraszany w widmie poprzez dodanie modulo 2 z funkcją Walsha przypisaną do kanału synchronizacji w 32.

3. Kanałosobista rozmowa

Po zaszyfrowaniu zdziesiątkowanego długiego PSP okresu 2 42-1 strumień danych poddawany jest rozszerzaniu widma w taki sam sposób, jak to miało miejsce dla rozważanych już kanałów: jest sumowany modulo dwa z funkcją Walsha przypisaną do kanału ze zbioru W 1 -W 7 . Następnie następuje kombinacja z pozostałymi kanałami (wejścia P 1 - P 7 na rys. 2), a następnie (w modulatorze) zwielokrotnienie ze złożonym krótkim pasmem i przesłanie na nośną.

4. Kanał ruchu bezpośredniego

Jedna z sekwencji Walsha w 8 + w 31 i t. 33 + t. 63 z szybkością chipa 1,2288 Mchip/s, z numerem sekwencyjnym Walsha jednoznacznie identyfikującym numer kanału ruchu nadawczego.

Adresowanie stacji bazowych.

Para PSP - I i PSP - Q lub równoważnie złożony PSP. Ta złożona krótka szerokość pasma jest taka sama dla wszystkich 64 kanałów CDMA i jest wykorzystywana przez wszystkie stacje BS systemu, ale z różnymi przesunięciami cyklicznymi. Różnica w przesunięciach cyklicznych umożliwia MS oddzielenie sygnałów emitowanych przez stacje BS różnych komórek lub sektorów, tj. pozwala na identyfikację stacji BS lub numeru sektora. Dla różnych BS przesunięcie zmienia się ze stałym krokiem równym 64 chip x PILOT_INC, gdzie parametr systemowy PILOT_INC przyjmuje wartości od 1 do 4. Zatem przy minimalnym kroku dostępnych jest 2 15 /2 6 =2 9 =512 krótkich przesunięć pasma, co oznacza, że ​​możliwe jest bezkonfliktowe istnienie sieci składającej się z 512 BS. Jeżeli konieczne jest, aby sieć składała się z większej liczby stacji BS, wówczas przy planowaniu terytorialnym sieci można łatwo osiągnąć to, że stacje BS z tymi samymi cyklicznymi przesunięciami krótkich PSP nie mogą jednocześnie znajdować się w strefie widoczności radiowej MS.

Z drugiej strony, etap przesunięcia PRP jednoznacznie określa rozmiar komórki (lub sektora), w którym MS może wiarygodnie rozróżnić PRP posiadające minimalne przesunięcie czasowe. Łatwo zauważyć, że przy minimalnym przesunięciu 64 żetonów promień komórki wyniesie około 15,5 km.

Adresowanie kanału zwrotnego

W kanale zwrotnym (uplinks)

Kanał dostępu (kanał dostępu);

Odwrotny kanał ruchu kanał komunikacyjny).

Asynchronia podziału kodu sprawia, że ​​irracjonalne jest używanie funkcji Walsha jako sekwencji tworzących kanał (sygnatur) kanałów fizycznych, ponieważ przy względnych przesunięciach czasowych nie mogą one zachować ortogonalności i mają bardzo nieatrakcyjne właściwości korelacji krzyżowej. Dlatego za separację kanałów w łączu zwrotnym odpowiadają różne przesunięcia cykliczne długiego PSP okresu 2 42 -1. Wykorzystywane są również funkcje Walsha w kanale zwrotnym, ale w innym charakterze: do zorganizowania kolejnego etapu kodowania odpornego na szumy danych przesyłanych przez MS.

Ogólną strukturę kanału komunikacji zwrotnej systemu IS-95c przedstawiono na rys. 6. Kanały dostępu i ruchu zwrotnego wykorzystywane przez państwo członkowskie są powiązane z określonymi kanałami przywoławczymi. W rezultacie jeden osobisty kanał wywoławczy może mieć do n = 32 kanałów dostępu i do t = 64 kanały ruchu zwrotnego.

Ryż. 6. Struktura kanału zwrotnego w standardzie SSMS IS-95c

1 kanał dostęp

Kanał dostęp zapewnia połączenie pomiędzy MS a stacją BS, dopóki MS nie dostroi się do przypisanego do niego kanału ruchu zwrotnego. Proces wyboru kanału dostępu jest losowy - MS losowo wybiera numer kanału z zakresu O...ACC_CHAN, gdzie ACC_CHAN jest parametrem transmitowanym przez stację bazową BS w komunikacie parametrów dostępu. Modulator ortogonalny odwzorowuje (koduje) grupy 6 symboli binarnych w funkcję Walsha o długości 64. Operacja ta polega na kodowaniu 6-bitowych bloków (64,6) kodem ortogonalnym. Przy dekodowaniu optymalnym („miękkim”) zysk energii przy zastosowaniu takiego kodu asymptotycznie dąży do 4,8 dB (45). Jednocześnie w wielu źródłach rozważana procedura nazywana jest modulacją ortogonalną lub modulacją Walsha. Grupa 6 symboli zostaje zastąpiony funkcją Walsha zgodnie z następującą zasadą: wartość dziesiętna 6-bitowej liczby binarnej odpowiadająca grupie 6 bitów jednoznacznie określa numer funkcji Walsha. Na przykład, jeśli grupa 6 symboli ma postać Na wejście modulatora ortogonalnego podawany jest sygnał (010110), wówczas odpowiada on wartości dziesiętnej 22, co oznacza, że ​​grupa ta jest zastępowana przez modulator z funkcją Walsha w 22, składający się z 64 znaków. W wyniku modulacji ortogonalnej szybkość transmisji danych wzrasta do

Strumień ortogonalnie modulowanych danych poddawany jest bezpośredniemu rozpraszaniu widma za pomocą długiego PSP z pewnym przesunięciem cyklicznym, które jednoznacznie identyfikuje dany MS, co pozwala na jego identyfikację na stacji bazowej BS, a co za tym idzie, realizację separacji kodowej abonentów. Przesunięcie cykliczne dużej przepustowości pamięci jest określane przez maskę generatora o długości 42 bitów, która jest zbudowana z identyfikatora BS, numerów kanałów wywoławczych i dostępu. Po rozszerzeniu widma (sumowanie modulo 2 z dużą przepustowością pamięci i konwersja symboli logicznych na dwubiegunowe jednostkowe), przepływ następuje z prędkością wiórów, tj. 1,2288 Mchip/s, wchodzi do kanałów kwadraturowych modulatora fazy, gdzie jest szyfrowany przez dwa krótkie PSP (PSP-I i PSP-Q) okresu 2 15. Wszystkie MS w danej komórce używają tego samego krótkiego przesunięcia PRP. Ponieważ kanał zwrotny wykorzystuje offset kwadraturowy PSK (OQPSK), w ramieniu Q modulatora wprowadza się element opóźniający na połowę czasu trwania chipa. Zastosowanie OQPSK zmniejsza głębokość niepożądanych spadków w obwiedni sygnału, a tym samym zmniejsza wymagany liniowy zakres dynamiki wzmacniacza mocy nadajnika MS.

Wykład 17. Funkcje Walsha i ich zastosowania

Funkcje Walsha. Podstawowe definicje. Sposoby porządkowania funkcji Walsha

Funkcje Walsha są naturalnym rozwinięciem systemu funkcji Rademachera, uzyskanego przez Walsha w 1923 roku i reprezentującego kompletny system ortonormalnych funkcji prostokątnych.

Zbiór funkcji Walsha uporządkowany według częstotliwości jest zwykle oznaczany w następujący sposób:

Funkcje Walsha, uporządkowane według częstotliwości, podobnie jak funkcje trygonometryczne, można podzielić na parzyste cal(i,t) i nieparzyste sal(i,t)

Rysunek 17.1 przedstawia pierwsze osiem funkcji wal w(To).

Rysunek 17.1

Oczywiste jest, że częstotliwość każdej kolejnej funkcji Walsha jest większa lub równa częstotliwości poprzedniej funkcji Walsha i ma jeszcze jedno przejście przez zero w otwartym przedziale t. Stąd wzięła się nazwa „porządkowanie częstotliwości”.

Dyskretyzacja funkcji Walsha pokazanych na rysunku 17.1a w ośmiu równomiernie rozmieszczonych punktach daje macierz (8x8) pokazaną na rysunku 17.1b. Macierz ta jest oznaczona przez H w(n) gdzie n=log 2 N i macierz będzie miała rozmiar NxN.

Funkcje Walsha, uporządkowane według częstotliwości, w ogólnym przypadku można otrzymać z funkcji Rademachera r k (x) korzystając ze wzoru:

gdzie w jest numerem funkcji Walsha; k – numer funkcji Rademachera;
wykładnik funkcji Rademachera, która w wyniku sumowania przyjmuje wartość 0 lub 1, tj. zgodnie z zasadą: 11=00=0; 10=01=1 bit liczby binarnej w. Na przykład dla szóstej funkcji Walsha ( w=6), zawartego w układzie wielkości N=2 3 =8, iloczyn (17,4) składa się z trzech współczynników postaci: dla k=1
przy k=2
przy k=3
. Liczby w systemie binarnym zapisuje się jako kombinację zer i jedynek. W naszym przypadku wartość w i jej kategorie przedstawiono w tabeli 17.1

Tabela 17.1

w 0 – najbardziej znacząca cyfra liczby, w 3 – najmniej znacząca cyfra liczby w.

Wykładniki funkcji Rademachera są równe:
;
;
i dlatego

wal(6,x)=r 1 1 (x)r 2 0 (x)r 3 1 (x)=r 1 (x)r 3 (x)

Regułę otrzymywania wykładników funkcji Rademachera przedstawiono schematycznie w tabeli 17.1, gdzie strzałki wskazują sumowalne cyfry liczby w oraz funkcje Rademachera, do których odnosi się otrzymany wykładnik. Z rysunku 17.1 widać, że parzyste liczby funkcji Walsha odnoszą się do funkcji parzystych, a liczby nieparzyste do funkcji nieparzystych. Innym sposobem zamawiania jest zamawianie Paley. Na zlecenie Paleya analityczny zapis funkcji Walsha ma postać:

p 1 jest najmniej znaczącą cyfrą liczby binarnej, p n jest najbardziej znaczącą cyfrą liczby binarnej. Przy porządkowaniu według Paleya, aby utworzyć funkcje Walsha, należy podnieść iloczyn funkcji Rademachera do potęgi, której liczby pokrywają się z liczbami odpowiednich cyfr podwójnej reprezentacji liczby p i wykładnikiem każdej funkcji jest równa zawartości odpowiedniej cyfry, tj. 0 lub 1. Co więcej, najmniej znacząca funkcja Rademachera odpowiada najmniej znaczącej cyfrze kombinacji binarnej liczby p. Zgodnie z tą zasadą w tabeli 17.2 przedstawiono wartości funkcji Walsha uporządkowanych według Paleya.

Tabela 17.2

Funkcje Rademachera w tabeli przedstawiono w postaci:
. Porównanie iloczynów i potęg funkcji Rademachera zapisanych w tabelach 17.1 i 17.2 pokazuje, że istnieje zgodność pomiędzy funkcjami Walsha uporządkowanymi przez Paleya i Walsha, co znajduje odzwierciedlenie w ostatniej kolumnie tabeli 17.2. Zgodnie z funkcjami Walsha uporządkowanymi przez Paleya można także skonstruować macierz próbek H p (n), podobną do pokazanej na rysunku 17.1b.

Kolejną popularną metodą porządkowania jest porządkowanie Hadamarda. Funkcje Hadamarda har(h,x) tworzy się przy użyciu macierzy Hadamarda. Macierz Hadamarda H N rzędu N=2 n jest macierzą kwadratową o wymiarach NxN i elementach 1, która ma właściwość

Na przykład zaczynając od H 1 = 1 znajdujemy:

Porównując otrzymaną macierz H 8 z macierzą próbek dla funkcji Walsha uporządkowaną przez Walsha (rysunek 17.1b), widzimy, że pomiędzy pierwszymi ośmioma funkcjami uporządkowanymi przez Walsha i Hadamarda istnieje następująca zgodność:

i może służyć jako podstawa do widmowej reprezentacji sygnałów. Każdą funkcję całkowalną w przedziale 0x1 i stanowiącą model matematyczny sygnału elektrycznego można przedstawić w postaci szeregu Fouriera za pomocą układu funkcji Walsha

Gdzie
- czas bezwymiarowy znormalizowany do dowolnego przedziału T.

Funkcje Walsha, podobnie jak funkcje Rademachera, przyjmują tylko dwie wartości: -1 i 1. Dla dowolnego m – wal 2 (m,x)=wal(0,x)=1.

Funkcje Walsha są funkcjami okresowymi z okresem równym 1.

Funkcje Walsha mają właściwość multiplikatywną; mnożenie dowolnych dwóch funkcji Walsha jest również funkcją Walsha:

Średnia wartość funkcji Walsha wal(i,x) dla i0 jest równa zeru.

System funkcyjny Walsha jest systemem złożonym i składa się z funkcji parzystych i nieparzystych, oznaczonych odpowiednio:

Błąd względny aproksymacji sygnału f(x) skończoną liczbą funkcji Walsha określa wzór

Gdzie
- energia sygnału w znormalizowanym przedziale jednostkowym.

Pytania do samodzielnej nauki

Znajdź wyrażenia dla funkcji Walsha w postaci funkcji Rademachera wal(7,x), wal(9,x), wal(13,x) w porządku Walsha, Paleya i Hadamarda.

Wymień i wyjaśnij podstawowe własności funkcji Walsha.

Rozwiń szereg Walsha, ograniczając się do pierwszych ośmiu funkcji Walsha funkcji sin X,sałata X i je zbudować.

Opisz zalety i wady każdego z rozważanych sposobów porządkowania funkcji Walsha.

Oblicz wartości pierwszych 8 współczynników rozwinięcia szeregu Fouriera-Walsha następujących sygnałów:

M. Yu. Vasilyeva, F. V. Konnov, I. I. Ismagilov

BADANIA NOWYCH PORZĄDKÓW DYSKRETNYCH FUNKCJI WALSHA

I ICH ZASTOSOWANIE W AUTOMATYCZNYCH SYSTEMACH STEROWANIA

Słowa kluczowe: dyskretne funkcje Walsha, system uporządkowany różnicowo, przetwarzanie i transmisja danych,

zautomatyzowane systemy sterowania.

Zaproponowano nową metodę porządkowania układów dyskretnych funkcji Walsha, przedstawiono właściwości nowych uporządkowań oraz rozważono możliwość wykorzystania syntetyzowanych uporządkowań dyskretnych funkcji Walsha w zautomatyzowanych systemach sterowania.

Słowa kluczowe: dyskretne funkcje Walsha, system uporządkowany różnicowo, przetwarzanie i przesyłanie danych, zautomatyzowane systemy sterowania.

Nowa metoda porządkowania układów dyskretnych funkcji Walsha, pokazuje właściwości nowych uporządkowań, możliwość zastosowania syntetyzowanych dyskretnych uporządkowań funkcji Walsha w układach automatycznego sterowania.

Wstęp

Powszechny rozwój sieci i systemów informatycznych, w tym zautomatyzowanych systemów sterowania (ACS) na różnych poziomach, sieci komputerowych, systemów projektowania wspomaganego komputerowo, gromadzenia i przetwarzania danych, automatyzacji eksperymentów, masowych

usług, kompleksów telemetrycznych, systemów informacyjnych i referencyjnych, sieci komunikacyjnych itp., doprowadziły do ​​znacznego wzrostu przepływów informacji pomiędzy rozproszonymi geograficznie źródłami a odbiorcami komunikatów oraz przechowywania w bazach danych coraz większej ilości informacji różnego typu. Aby zwiększyć efektywność wykorzystania zasobów komunikacyjnych i informacyjno-obliczeniowych tych systemów, stosuje się różne metody i środki.

Wśród nich bardzo ważną rolę odgrywają metody ograniczania redundancji danych, zapewniające kompresję wolumenu przesyłanych lub przechowywanych informacji. Pozwala to na znaczne odciążenie kanałów komunikacyjnych oraz systemów przetwarzania i przechowywania danych poprzez eliminację zbędnych lub zduplikowanych informacji, co jest równoznaczne ze zwiększeniem przepustowości systemów gromadzenia, przesyłania i przetwarzania danych lub zwiększeniem pojemności urządzeń przechowujących.

Wśród istniejących metod ograniczania redundancji danych szczególne miejsce zajmują metody kompresji wykorzystujące różne przekształcenia matematyczne. Do najczęściej stosowanych przy redukcji i transmisji danych w zautomatyzowanych systemach produkcji i sterowania procesami należą

Transformacje Fouriera, Walsha i Haara. Każde z nich ma szereg zalet, np. zastosowanie transformacji Walsha i Haara może znacznie uprościć i przyspieszyć przetwarzanie informacji.

Powszechne stosowanie szeregu transformacji w stosowanych problemach polega na możliwości ich obliczania przy użyciu szybkich algorytmów, które mają znacznie mniejsze

złożoność obliczeniowa w porównaniu z klasycznymi algorytmami transformacji.

W artykule poruszono szereg zagadnień związanych ze stosowaniem przekształceń Walsha: przedstawiono konstrukcję nowych porządków funkcji Walsha, przedstawiono badanie ich własności oraz rozważono wykorzystanie funkcji Walsha przy wykonywaniu przekształceń.

Krótki przegląd dyskretnych funkcji Walsha i ich uporządkowania

Ortonormalny, kompletny układ funkcji prostokątnych został wprowadzony przez Walsha. W przeciwieństwie do harmonicznych trygonometrycznych, w których funkcja jest rozwinięta do klasycznego szeregu Fouriera, funkcje Walsha są falami prostokątnymi, które są preferowane w wielu zadaniach przetwarzania sygnału

fale sinusoidalne. Wynika to w dużej mierze z prostej postaci funkcji Walsha, z których każda przyjmuje tylko dwie wartości (+1 i -1), co znacznie ułatwia ich implementację na komputerze.

Dyskretne transformaty Walsha (DWT) opierają się na dyskretnych funkcjach Walsha (DWF), które są utworzone przez jednolite próbki ciągłych funkcji Walsha. Całkowita liczba raportów w DFU musi wynosić N = 2n, gdzie n jest dowolną dodatnią liczbą całkowitą.

Cyfrowe przetwarzanie sygnału wykorzystuje transformacje w różnych obszarach

zamawianie systemów DFU. Do najbardziej znanych porządków w praktyce przetwarzania sygnałów DFU w systemie zalicza się: porządkowanie sekwencyjne (Walsha-Kaczmarza); diadyczny

porządkowanie (Walsh-Paley); zamawianie

zgodnie z układem wierszy w macierzy

Hadamard (Walsh-Hadamard).

Biorąc za podstawę układy ciągłych funkcji Walsha o różnym rzędzie funkcji, otrzymujemy odpowiednio macierze DPUC (dyskretne transformaty Walsha-Kaczmarza), DPUP (dyskretne transformaty Walsha-Paleya) i DPUA (dyskretne transformaty Walsha-Hadamarda).

DFU można opisać analitycznie, wyrażając je w postaci dyskretnych funkcji Rademachera. Pozwalać

j = £ ік2 - numer funkcji w systemie oraz і = £ ік2 к=0 к к=0 К

Numer referencyjny, wówczas wspomniane macierze transformacji mają postać:

Matryca DPUK

macierz DPUP

(- 1) tys. £ 0ік^к(і)

(- 1) tys. £ 0іkip-k

Matryca DPUA

(- 1)к£ 0ікік

gdzie -t= - współczynnik normalizacji; l/i

PoSH = b = ^n-k+1 f-!n-k’ k = 1,2 n,

gdzie ® jest znakiem dodawania modulo 2.

Należy pamiętać, że kombinacje binarne formularza

Ch0(-).Ch1S-)...Pp(-) lub Pp(-),Pp-1(-), -,P0(-)

nazywane są odpowiednio kodem Graya lub odwrotnym kodem Graya liczby -

Dla macierzy Walsha-Hadamarda obowiązuje następujący podział na podmacierze:

Powtarzający się wzór (4) można również wyrazić jako iloczyn Kroneckera macierzy:

NAR k = NAR 0 NAR k 1 . 2k 2 2k-1

Macierze (1-2) można otrzymać poprzez zmianę kolejności wierszy macierzy Walsha-Hadamarda, gdyż istnieją pewne zależności pomiędzy uporządkowaniami dyskretnego układu Walsha o wymiarze N, które w postaci macierzowej mają postać:

PAM = B^HAR^

WALN = B^PAI.

macierz binarnych permutacji odwrotnych;

Macierz permutacji wykorzystująca odwrotny binarny kod Graya.

Podsumujmy krótko główne właściwości DFU. Następujące właściwości nieodłącznie związane z ciągłymi funkcjami Walsha są ważne dla DFU:

1. Ortogonalność. Funkcje Walsha

są ortogonalne na przedziale i odwrotnie.

6. Multiplikatywność. Iloczyn dwóch funkcji Walsha jest równy nowej funkcji Walsha z tego samego systemu.

7. Porządek i ranga funkcji Walsha. Wygodnie jest scharakteryzować funkcje Walsha za pomocą dwóch parametrów związanych z binarną reprezentacją ich liczb. Pierwsza z nich określa maksymalną liczbę niezerowej cyfry binarnej liczby - i nazywa się ją rządem p; drugi - rząd funkcji Walsha r - pokazuje liczbę cyfr binarnych, w których liczba Ш ma jednostki. Liczbę funkcji Walsha i-tego stopnia umownie oznacza się jako -(r) i zapisuje w systemie dziesiętnym:

gdzie ^k (k = 1,2,...,r) jest numerem bitu kodu binarnego Ř, zawierającego jedynkę. Obszar zmiany wszystkich ^k w (8) musi spełniać następujący układ równości:

M1 = 0,1,..., n - r -1;

M 2 = ja + 1, . ., p_g;

Dla rangi i porządku funkcji Walsha obowiązuje następująca własność: ranga

iloczyn funkcji Walsha nie przekracza sumy ich rang; rząd iloczynu nie przekracza maksimum rzędów czynników. Ważność tej własności wynika z właściwości sumowania modulo 2.

W systemach DFU są one klasyfikowane jako jednoróżnicowe dyskretne bazy ortogonalne. Przy badaniu szeregu właściwości baz tej klasy bardzo przydatne są ich parametry i charakterystyki, szczegółowo omówione w tej pracy. Podejście do ich wprowadzenia opiera się na fakcie, że dowolny współczynnik transformacji w rozpatrywanej klasie zasad można przedstawić jako sumę ważoną skończonych różnic odpowiednich rzędów

wektor przekształcalny £

р(і)= £ і = 0,М -1,

gdzie P(I) jest współczynnikiem konwersji I-tego; Dk jest operatorem różnicy skończonej k-tego rzędu;

ы(|,-) = ы(|,Н-1 -^ -Ш) - 1. funkcja wagi; d| -

jakaś liczba całkowita.

W tym przypadku wektory bazowe dyskretnych podstaw monoróżnicowych tworzone są przez ciągi operatorów różnic skończonych odpowiednich rzędów. W dalszej części będziemy operować parametrem zwanym rządem różniczkowym funkcji bazowej d|,

przez co rozumiemy rząd operatorów różnic skończonych tworzących tę funkcję.

Należy zauważyć, że rząd różniczkowy konkretnej funkcji Walsha jest związany z jej właściwościami strukturalnymi i nie zależy od jej umiejscowienia w systemie, czyli od uporządkowania funkcji bazowych.

Ważne są również następujące właściwości:

8. Dla układów DFU zamówionych przez Hadamarda i Paleya rzędy różniczkowe funkcji są równe

Stąd,

ich szeregi: liczba

C = rki, i = 0,M-1.

(k = 0,p) chk

rząd różniczkowy jest równy wartości Cn – liczby kombinacji od n do k.

9. Dobrze znana właściwość rozwinięć dyskretnych wielomianów mocy w układzie Walsha-Paleya, którą można przeformułować w następujący sposób

sposób: widmo wielomianu dyskretnego stopnia k-tego (k = 0,n) zawiera składowe odpowiadające funkcjom bazowym nie wyższym niż k-ty

porządek różnicowy. Należy zauważyć, że podobne stwierdzenie będzie prawdziwe w przypadku rozwinięć w systemie Walsha-Hadamarda.

10. Współczynniki widmowe sygnałów dość dobrze opisanych dyskretnymi wielomianami mocy niskich rzędów, w obrębie grup odpowiadających funkcjom bazowym Walsha-Paleya jednego rzędu różniczkowego, zmniejszają wartość bezwzględną wraz ze wzrostem ich liczb porządkowych.

Synteza układu różnicowo-uporządkowanego dyskretnych funkcji Walsha

Proponowany sposób zamawiania systemów

DFU wymiaru N = 2n jest następujące. Konstruuje się podział zbioru liczb porządkowych funkcji Walsha pierwotnego układu I = (0,1 N -1)

na (n +1) podzbiory, z których każdy zawiera liczbę funkcji o tym samym rzędzie różniczkowym.

|(0) = (0), i = 0,

I(i) = (2M + 2M2 +... + 2M: m1 = 0,p - i,

^2 - +1,n - I +1,...^| - ^| 1 +1, p - 1), I - 1, p - 1,

1(p) – (2p – 1), I – str.

Następnie wygenerowane podzbiory układamy w kolejności rosnących rzędów różniczkowych odpowiednich funkcji, czyli w efekcie otrzymujemy zbiór A – TsL^.-Ln), dla którego

obowiązują zależności: L p oraz: - 0 i L - Sp,1 - 0, p.

Oczywiście zbiór wyznacza permutację funkcji Walsha w układzie |0 1 ... N - 1]

Otrzymany w wyniku tego przegrupowania system DFU będzie charakteryzował się tym, że znajdujące się w nim funkcje ułożone są w grupy w kolejności rosnącej ich różniczkowego rzędu. Z tego powodu nazywamy ten system DFU uporządkowanym różnicowo.

Dla wektora permutacji

będziemy trzymać się kolejności

zapis Рп = (Р0,Р1....Рм-1), gdzie

p| - w|,1 - 0^-1. Przegrupowanie za pomocą

Nazwijmy ten wektor permutacją ze względu na rzędy różniczkowe funkcji bazowych (w skrócie B-permutacja).

Rozważmy uporządkowanie układu Walsha-Paleya za pomocą proponowanej metody. Analiza rzędów różniczkowych funkcji Walsha-Paleya wykazała, że ​​wektor Pn można przedstawić jako sumę wielu podwektorów:

Рп - (рп0),рп1),рп2),.,рп)) , (13)

Рп,к = 1,п-1, - podwektory,

relacje powtarzalności: Рі(к)= |(2і -1), і=к,

Рі(і) = (2і - 1),і = 1, n;

zdefiniowany

^(P-k), 2i-1 + P,- 1)),i = k +1, n,

Wektory Рп wymiaru N - 2п,п -1,5, odpowiadające permutacjom

sekwencje przedstawiono w tabeli. 1.

Grupy są podkreślone u góry

współczynniki parzystych, a od dołu - nieparzystych rzędów różniczkowych.

Tabela 1 - Wektory wartości sekwencji permutacji

p Wektor Rp

3 {0,1,2,4,3,5,6,7}

4 {0,1,2,4,8,3,5,6,9,10,12,7,11,13,14,15}

5 {0,1,2,4,8,16,3,5,6,9,10,12,17,18,20,24, 7,11,13,14,19,21,22,25,26,28,15,23,27,29,30,31}

Uwzględnienie wprowadzonego wektora wartości ciągu permutacyjnego różnicy

uporządkowany system DFU (РЦ^0))(=о można opisać następująco:

pldN(i) = palN(pj), i = 0,N

gdzie pai^(i) jest i-tą funkcją Walsha-Paleya.

S^PAL^ , (І6)

macierz D-permutacji,

którego elementy są utworzone w następujący sposób:

[och, w innych przypadkach.

Należy zaznaczyć, że przedstawione powyżej uporządkowanie układu DFU uzyskano w oparciu o system Walsha-Paleya. Wybór systemu Walsha-Paleya jako systemu bazowego wynika z łatwości

uzyskanie opisu analitycznego sekwencji permutacji i relacji macierzowej tworzącej proponowane uporządkowanie systemu DFU.

Różne opcje różnicy

zamówione systemy można uzyskać wybierając jako podstawę inne systemy firmy Walsh. Analiza rzędów różniczkowych funkcji Walsha-Hadamarda i Walsha-Paleya wykazała, że ​​wektor wartości sekwencji permutacji Рр, wybierając Walsha-Hadamarda jako macierze nośne, można również przedstawić jako kombinację wielu podwektorów (13-14) - (Tabela 2).

Na podstawie otrzymanego wektora wartości sekwencji permutacji różnicy

opisz to tak:

zamówił systemy DFU

hddN ()= hadN (pj)i = 0,N -1

gdzie hadN (0 - odpowiednio pierwsza funkcja Walsha-Hadamarda.

Tabela 2 - Grupy rzędów różniczkowych systemów Walsha-Paleya i Walsha-Hadamarda z N=8

j had,j PALn,j di pj pldn,j di

O OOO OOO O O OOO O

I OOІ IOO I 4 IOO I

2 ОІО ОІО I 2 ОІО I

3 ОІІІІО 2 I ООІ I

4 IOO OOI I 6 IIIO 2

Z ІОІ ІОІ 2 З ІОІ 2

6 ІІО ОІІ 2 3 ОІІ 2

7 III III 3 7 III 3

Zapis macierzy dla wprowadzonego układu DFU ma następującą postać:

Na przykład jawna postać macierzy HDDN dla N = 2 jest następująca:

11 1 1 1 1 1 1 0

1 -1 1 -1 1 -1 1 -1 1

11 -1 -1 1 1 -1 1

1 1 1 1 -1 -1 -1 1

1 -1 -1 1 1 -1 1 2

1 -1 1 -1 -1 1 1 2

1 -1 -1 1 1 -1 1 2

1 -1 -1 1 -1 1 1 -1 3

rząd różniczkowy funkcji bazowej znajdującej się w odpowiednim wierszu macierzy.

Dokładne oszacowanie M całkowitej liczby układów DFU uporządkowanych różnicowo, pod warunkiem, że grupy funkcji bazowych zostaną uporządkowane w kolejności rosnącej ich rzędów różniczkowych, można wyznaczyć ze wzoru:

M = P (SP!). (18)

W artykule rozważono możliwość uzyskania zapisu macierzowego innej wersji systemu DFU uporządkowanego różnicowo. W tym przypadku stosowana jest metoda Kroneckera warstwa po warstwie

iloczyn macierzy.

Zastanówmy się nad kwestią numeracji DFU o kolejności różnicowej w systemie. Tutaj w niektórych przypadkach wygodniej jest operować dwucyfrowym indeksowaniem funkcji bazowych. Na przykład dla systemów DFU rozważanych w tej pracy wprowadza się go w następujący sposób:

pld2n(i) = pld2n(l,j), i = 0,N -1, i = bnl-1 + j, l є (0,1,..., n) j є(,1,... ,сП ​​​​-1).

Oczywiście indeks l jest równy porządkowi różniczkowemu wektora bazowego, a indeks j jest jego liczbą porządkową w odpowiedniej grupie. Zależność opisująca relację między dwoma typami indeksowania nie zależy od wersji systemu DFU uporządkowanego różnicowo.

Należy zauważyć, że macierze PAL^ i DOWN

pokrywają się dla N=2,4 i PLD^ = DOWN dla N=8.

Własności układów różnicowo-uporządkowanych dyskretnych funkcji Walsha

nieruchomości

oddzielnie wprowadzone zamówienia

Rozważmy transformacje według układów DFU.

1. Dla systemów DFU uporządkowanych różnicowo

właściwości DFU 1-7 są ważne.

2. Dobrze znana własność 8 (rozbudowa dyskretna

wielomiany mocy według układów Walsha-Paleya i Walsha-Hadamarda) w odniesieniu do rozpatrywanych układów DFU uporządkowanych różnicowo, można

sformułować następująco: widmo

dyskretnego wielomianu k-tego (k = 0,P) stopnia jest rozwijany w funkcjach bazowych nie wyższych niż k-ta grupa.

Nieruchomość rozpatrywana w sprawie

uporządkowanie funkcji Walsha-Paleya można zapisać jako następującą zależność:

p(|,|) = 0,1>k, (20)

gdzie P(u)= £ 10(,u)

3. Ważną właściwością jest 9, która

dotyczy to również systemów DFU uporządkowanych różnicowo: współczynniki widmowe sygnałów, które są dość dobrze opisane przez dyskretne

wielomiany potęgowe małych rzędów, w obrębie grup odpowiadających funkcjom bazowym tego samego rzędu różniczkowego, zmniejszają się wartości bezwzględnej wraz ze wzrostem ich liczb porządkowych.

Macierze funkcji Walsha uzyskane przy tych porządkach są asymetryczne,

Wyjątkiem są trywialne przypadki macierzy dla rzędów N = 2, 4.

4. Zwróć uwagę na następującą właściwość: widma

dyskretne wielomiany mocy niskich rzędów w bazach DFU uporządkowanych różnicowo

charakteryzują się większym stopniem lokalizacji niezerowych składowych w swoich przekrojach początkowych

Zilustrujmy naturę rozkładu niezerowych składowych widm dyskretnych wielomianów mocy 1(1) k-tego (k = 1,2) stopnia dla N=16 w

podstawy różnych systemów DFU.

Wprowadźmy najpierw wektor wskaźnika widma B = (zo^...^^-), definiując jego elementy w następujący sposób

B| = |0, р(|)=о, (21)

gdzie P(1) jest-tym współczynnikiem konwersji. Jednowymiarowe wielomiany mocy dyskietki 10) są określone przez funkcje postaci

f(j) = Е аі]”, ] = 0,Н-1, к є г,

1 = (0,1, ..., m -1).

Wybierając modele sygnałów, często ograniczamy się do modelu wielomianowego małych stopni (k є r 5). Wynika to z faktu, że

można skutecznie opisać szeroką klasę sygnałów rzeczywistych w skończonych odstępach czasu.

Wzory na obliczenie współczynników transformacji P(i) jednowymiarowego sygnału wielomianowego w postaci macierzowej będą miały następującą postać:

gdzie jest macierzą DPU w zastosowanej kolejności DFU;

1 = |g(|), | = oTy -1) - wektor danych początkowych;

P = p(1), I = 0^ -11 - wektor widmowy

współczynniki, T - znak transpozycji.

Wektory wskaźnikowe widm w oparciu o Walsha-Hadamarda, Walsha-Kaczmarza, Walsha-Paleya oraz DFU uporządkowane różnicowo dla wielomianów stopnia k=1 i k=2 mają postać:

(1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0) - dla bazy Walsha-Hadamarda;

(1,1,0,1,0,0,0,1,0,0,0,0,0,0,0,1) - dla bazy Walsha-Kaczmarza;

(1,1,1,0,1,0,0,0,1,0,0,0,0,0,0,0) - dla bazy Walsha-Paleya;

(1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0) - dla podstawy

DFU uporządkowane różnicowo.

(1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,0) - dla bazy Walsha-Hadamarda;

(1,1,1,1,1,0,1,1,1,0,0,0,1,0,1,1) - dla bazy Walsha-Kaczmarza;

(1,1,1,1,1,1,1,0,1,1,1,0,1,0,0,0) - dla bazy Walsha-Paleya;

(1,1,1,1,1,1,1,1,1,1,1,0,0,0,0,0) - dla podstawy

DFU uporządkowane różnicowo.

Zilustrujmy naturę rozkładu niezerowych składowych widm dyskretnych dwuwymiarowych wielomianów mocy stopnia 1(1, ] k-tego (k = 1,2) dla N1* N2=8x8 w podstawach DFU. Dwuwymiarowe dyskretne wielomiany mocy są określone przez funkcje postaci

Ш) = X X арір]а,

gdzie I = 0,^ -1,] = 0,^ -1, k e 2^1,

^ -1 = (o,1, ^ - 1) .

W tym przypadku ograniczymy się do dwuwymiarowych modeli wielomianowych niskich stopni, gdyż stanowią one podstawę szeregu algorytmów przetwarzania sygnałów cyfrowych.

Przedstawmy wzory na prostą

transformacja dwuwymiarowego sygnału wielomianowego do postaci wektorowo-macierzowej:

P = HNTfHN, (25)

gdzie 1 = (1(1,]), I = 0,^ -1,] = 0,^ -1) - macierz

dane źródłowe;

Р = "Р(И),1 = 0,^ -1, ] = 0^2 -1) - macierz

współczynniki widmowe.

Wektory wskaźnikowe widm dla rozpatrywanych przypadków przy k=1 przedstawiono na rys. 1,

1 ja 1 ja o ja 1 ja □ ja □ ja □ ja 1

00000000 1 0 0 0 0 0 0 0

00000000 1 0 0 0 0 0 0 0

Ryż. 1 - Wektory wskaźnikowe widm o k=1 w bazie: Walsh-Hadamard, Walsh-Kaczmarz

00000000 00000000 00000000 00000000

Ryż. 2 - Wektory wskaźnikowe widm o k=1 w bazie: Walsha-Paleya, uporządkowane różnicowo

Wektory wskaźnikowe widm dla rozpatrywanych przypadków przy k=2 przedstawiono na rys. 3,

11111110 1110 10 0 0 1110 10 0 0 1 0 0 0 0 0 0 0 1110 10 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 00000000

Ryż. 3 - Wektory wskaźnikowe widm przy k=2 w bazie: Walsh-Hadamard, Walsh-Kaczmarz

1 ja 1 ja 1 ja 1 ja 1 ja 1 ja 1 ja o

Ryż. 4 - Wektory wskaźnikowe widm dla k=2 w bazie: Walsha-Paleya, uporządkowane różnicowo

Z tych przykładów jasno wynika, że ​​widma dyskretnych wielomianów mocy niskich rzędów w podstawach DFU o kolejności różnicowej

charakteryzują się większym stopniem lokalizacji niezerowych składowych w swoich przekrojach początkowych. Uzyskane właściwości transformacji na układach DFU uporządkowanych różnicowo są ważne dla ich zastosowań w układach sterowania i systemach komunikacyjnych.

1 0 □ 0 0 0 0 0

1 0 0 □ 0 0 □ 0

□ 0 0 □ 0 0 □ 0

Zastosowanie syntetyzowanych uporządkowań dyskretnych funkcji Walsha w zautomatyzowanych układach sterowania

Pomyślne wykorzystanie transformacji Walsha w dziedzinie sterowania i komunikacji ułatwiło zbadanie następujących zagadnień: właściwości funkcji Walsha; właściwości widm Walsha; ogólne zagadnienia wykorzystania funkcji Walsha przy wykonywaniu przekształceń; algorytmy szybkiej transformacji Walsha; obliczanie funkcji korelacji i wykonywanie splotów na podstawie funkcji Walsha; zastosowanie funkcji Walsha do badania procesów losowych; wykorzystanie funkcji Walsha w konstrukcji filtrów cyfrowych.

Ze względu na wspólne właściwości 1-7 ze znanymi DFU (w porządkach Walsha-Kaczmarza, Walsha-Paleya, Walsha-Hadamarda), zsyntetyzowany uporządkowany różnicowo

Systemy DFU mogą znaleźć skuteczne zastosowanie w obszarze automatycznego sterowania procesami. Na przykład istotne jest wykorzystanie transformacji Walsha w analizie dynamiki układów liniowych i nieliniowych, opracowywaniu optymalnych układów sterowania, modelowaniu procesów, identyfikacji obiektów i opracowywaniu szeregu specjalnych urządzeń automatyki.

Praktycznie istotne dla zautomatyzowanych systemów sterowania jest wykorzystanie funkcji Walsha zaproponowanych przez X. Harmuta do generowania sygnałów przesyłanych liniami radiokomunikacyjnymi. Funkcje Walsha są wykorzystywane przy opracowywaniu wielokanałowych systemów komunikacyjnych, w których różne sygnały są jednocześnie przesyłane w każdym kanale komunikacyjnym. Zastosowanie systemów DFU uporządkowanych różnicowo (właściwość 2) umożliwi wielowątkowe przetwarzanie danych, przy czym każdy wątek będzie zawierał elementy grupy transformantów odpowiedniego

porządek różnicowy, co znacznie przyspiesza przetwarzanie danych.

Obecnie technologia falkowa wykorzystywana jest do rozwiązywania wielu problemów w zautomatyzowanych systemach sterowania procesami technologicznymi i produkcją.

transformacja. Na przykład w OAO Tatneft transformacja falkowa jest wykorzystywana do tłumienia szumów i kompresji tablic danych z manometrów głębokości lub podczas przesyłania dynamogramów uzyskanych z czujników hamowni do sterowni. W wielu przypadkach niewystarczający stopień kompresji danych przy wykonywaniu DPD utrudnia powszechne stosowanie tych przekształceń. Właściwość 2 uzyskana dla systemów DFU uporządkowanych różnicowo znacznie zwiększy stopień kompresji danych i ułatwi zastosowanie w wymienionych powyżej zadaniach.

Jednym z ważnych zadań w zautomatyzowanym systemie sterowania jest zadanie przesyłania danych kanałami komunikacyjnymi. W tym samym czasie 8SLEL-

systemy. Znane są również rozwiązania, w których funkcje systemu 8SLEL realizowane są z wykorzystaniem oprogramowania internetowego; w OJSC Gas-Service (Republika Baszkortostanu) uruchomiono kilka zautomatyzowanych systemów zdalnego monitorowania urządzeń sieci dystrybucyjnej gazu. Do transmisji danych w sieci można efektywnie wykorzystać systemy DFU uporządkowane różnicowo (właściwość 4).

W pracy autorzy zaproponowali algorytmy wykorzystujące transformacje Walsha oraz analizę porównawczą ich efektywności. Zastosowanie w prezentowanych algorytmach transmisji danych układów DFU uporządkowanych różnicowo zapewni sekwencyjną transmisję wyjściowych strumieni danych z dużą szybkością przetwarzania i transmisji danych w sieci.

Uzyskane właściwości nowych uporządkowań dyskretnych funkcji Walsha są ważne dla ich zastosowań w układach sterowania i systemach komunikacyjnych. Syntetyzowane uporządkowanie różnicowe

Przy rozwiązywaniu wielu problemów analitycznych wygodnie jest przedstawić złożony sygnał jako zbiór sygnałów elementarnych. W praktyce największe zastosowanie znalazła reprezentacja sygnału s(t), podane na przedziale w postaci kombinacji liniowej niektórych funkcji elementarnych (pkt (t), / = 0,1,2,..., zwane podstawowym

- norma funkcji bazowej.

Reprezentację sygnału w tej postaci nazywa się uogólnionym szeregiem Fouriera. Często jako funkcje bazowe używany jest układ funkcji trygonometrycznych.

lub układ złożonych funkcji wykładniczych

Jednakże wraz z rozwojem cyfrowych metod transmisji i przetwarzania sygnałów w ostatnich latach, jako funkcje bazowe zaczęto stosować dyskretne ciągi ortogonalne w postaci funkcji Rademachera, Walsha, Haara itp.

Wprowadźmy czas bezwymiarowy 0 = T / T . Funkcje Rademachera powstają z funkcji sinusoidalnych przy użyciu zależności

Inaczej mówiąc, funkcje Rademachera przyjmujące wartości ±1 można interpretować jako funkcje „sinusa prostokątnego”. Wykresy pierwszych czterech funkcji Rademachera wyglądają jak na rysunku 4.12.

Układ funkcyjny Rademachera r k(0) jest ortonormalny w przedziale 0

Układ funkcyjny Walsha jest rozszerzeniem systemu funkcji Rademachera na kompletny system i jest zdefiniowany jako

Gdzie kf- oznaczający J cyfra w zapisie numeru Do w kodzie Graya. Na przykład,

ponieważ 5=>101 2 =>111 g. Wykresy pierwszych czterech funkcji Walsha pokazano na rysunku 4.13.

Ryż. 4.13.

Funkcje Walsha mają następujące właściwości:

• 1. spacer(®) = ​​± 1.
• 2. | chodzić (0)| = 1, 2 = 1.
• 3. Funkcje Walsha są okresowe chodzić (©) = chodzić (0 +1).
• 4. Funkcje Walsha są ortogonalne

5. Mnożenie funkcji Walsha daje funkcję Walsha, ale innego rzędu chodzić (0) wal n (0) = Walj (0), j = k ® N,

chodzić (0 2) chodzić (0 2) = chodzić(0 3), 0 3 = 0j ® 0 2, gdzie © to dodawanie modulo dwa.

W niektórych przypadkach używane są funkcje Walsha w postaci

Używając układu funkcji Walsha jako funkcji bazowych, sygnał można przedstawić w postaci

Zbiór współczynników Walsha-Fouriera (q) lub (ak, k, k) a zbiór liczb porządkowych funkcji tworzy widmo sygnału w bazie Walsha, które dla zwięzłości nazywa się czasami widmem S.

Na przykład sygnał będący okresową sekwencją prostokątnych impulsów (rys. 4.14) ma widmo S określone wzorem (4.39).

Ryż. 4.14.

impulsy prostokątne

Pozwalać n= 3, wówczas otrzymujemy widmo S dla tego przypadku, pokazane na rysunku 4.15.

Ryż. 4.15.

Zatem w przeciwieństwie do zwykłego widma częstotliwości, widmo S sekwencji prostokątnych impulsów okazuje się skończone. Należy zauważyć, że przesunięcie impulsów w czasie prowadzi do zmiany struktury widma S. W szczególności pojawiają się nowe komponenty. Na przykład dla sekwencji n= Przy 3 impulsach przesuniętych o 0=1/16 widmo S wygląda jak na rysunku 4.16, natomiast przy zastosowaniu układu funkcji trygonometrycznych przesunięcie czasowe zmienia jedynie widmo fazowe.

Ze względu na możliwość zastosowania operacji logicznych do funkcji Walsha, wykorzystuje się je przy opracowywaniu urządzeń do generowania i konwersji sygnałów opartych na technologii mikroprocesorowej. Sygnały oparte na funkcjach Walsha stosowane są w cyfrowych wielokanałowych systemach transmisji informacji.

Ryż. 4.16.

przesunięty o 0=1/16

System funkcji Haara składa się z fragmentarycznie stałych funkcji har k(0), określone w przedziale 0

Gdzie T- liczba najbardziej znaczącej niezerowej cyfry w binarnej reprezentacji liczby

Do mod2 w - wartość Do modulo 2 t, jest najmniejszą resztą z dzielenia liczby Do NA 2 t. Wykresy kilku funkcji Haara przedstawiono na rysunku 4.17.

Ryż. 4.17.

Jeśli rozpatrzymy widmo sygnału w bazie Haara, to podobnie jak w przypadku widma S, gdy sygnał przesuwa się w czasie, zmienia się struktura jego widma.

Funkcje Haara wykorzystywane są w systemach sterowania i komunikacji, przy opracowywaniu filtrów cyfrowych, przy kompresji informacji – są to na przykład różne metody kompresji zdjęć czarno-białych w oparciu o funkcje Haara w celu późniejszej transmisji skompresowanych obrazów kanałami komunikacyjnymi lub ich archiwizacja.

Kompresja tablic nawigacyjnych w bazie Walsha C.B. Paszencew

Wydział Nawigacji MSTU, Katedra Nawigacji

Adnotacja. W artykule rozważono możliwość wykorzystania podstawy funkcjonalnej Walsha-Paleya do kompresji tabel liniowych i prostokątnych. Podano wszystkie niezbędne do tego wzory i zaprezentowano rzeczywisty efekt kompresji informacji na przykładach. Metodę można stosować zarówno do wstępnej kompresji informacji, jak i do ich przetwarzania w czasie rzeczywistym.

Abstrakcyjny. W pracy rozważono możliwość wykorzystania bazy funkcjonalnej Wolsha-Paly'ego dla liniowych i prostokątnych tabel kompresji. Podano wszystkie niezbędne do tego wzory oraz pokazano na przykładach rzeczywisty efekt kompresji informacji. Metodę można zastosować zarówno do wstępnej kompresji informacji, jak i do jej przetwarzania w skali czasu rzeczywistego.

1. Wstęp

Wiele automatycznych i zautomatyzowanych urządzeń związanych z nawigacją wykorzystuje dane tabelaryczne przechowywane w pamięci urządzeń decyzyjnych i wybierane z nich w miarę potrzeb. W tym przypadku zużywany jest najważniejszy zasób - pamięć, a pobieranie z niego próbek pochłania jeszcze ważniejszy zasób - czas, wpływając na wydajność całego systemu przetwarzania informacji. Dlatego ważne są wszelkie metody zmniejszające objętość pamięci. Jedną z takich metod może być metoda kompresji informacji tabelarycznej ze względu na jej rozkład widmowy w jakiejś bazie funkcjonalnej. W momencie zużycia wartość funkcji przywracana jest poprzez transformację odwrotną. W porównaniu z rozwinięciem Fouriera, do rozwinięcia bardziej korzystne jest wykorzystanie bazy Walsha, ponieważ w przypadku funkcji gładkich współczynniki rozwinięcia Walsha dążą do zera szybciej. Pozwala to na większy stopień kompresji informacji w bazie Walsha. Ponadto przywrócenie wartości tabeli w bazie Walsha wymaga mniej czasu. Wynika to z prostszego obliczania funkcji Walsha w porównaniu z obliczaniem funkcji trygonometrycznych. Jeśli te funkcje są generowane sprzętowo, korzyść z korzystania z funkcji Walsha jest jeszcze większa, ponieważ ich możliwe wartości +1 i -1 są łatwo implementowane przez urządzenia komputerowe. W pracy wykorzystano przykłady numeryczne, aby pokazać zalety stosowania bazy Walsha dla niektórych typów funkcji gładkich i danych tabelarycznych. Proces obliczeniowy opiera się na opracowanych przez autora programach do szybkich transformat Fouriera i Walsha oraz porównaniu uzyskanych widm.

2. Teoretyczne podstawy kompresji

Ogólne zasady teoretyczne, na podstawie których przeprowadza się transformację w wybranej bazie funkcjonalnej, są dobrze znane (Gold, Ryder, 1993; Trakhtman A., Trakhtman V., 1978). Należy podkreślić dyskretne przekształcenia, gdy pierwotny szereg liczbowy jest skończony. Ponieważ mówimy o kompresji tabeli, tj. o zasadniczo skończonej serii liczb, to dalej będziemy mówić tylko o dyskretnych transformacjach. Jeśli podano serię N liczb

X2, Xk, , XN (1)

wówczas bazę funkcjonalną należy wybrać ze skończonego zbioru N funkcji

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

istniejący na zbiorze punktów Xk. Wtedy dyskretna transformacja w tej podstawie da dokładnie N współczynników Ca, Koropbiego znajdziemy stosując sumowanie formalne:

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

Zbiór N współczynników Ca stanowi dyskretną reprezentację liczby liczb (1) w

podstawa funkcjonalna (2). Często ten zestaw liczb Ca nazywany jest widmem liniowym w wybranej podstawie. Inną interpretacją rozwinięcia (3) jest uznanie go za transformację liniową pierwotnego układu współrzędnych Xk. Współczynniki Ca stają się wówczas współrzędnymi w nowym układzie współrzędnych 0JX). Jeżeli znane jest widmo (zestaw współczynników Ca), to ciąg liczb, który je wygenerował, można odtworzyć aż do błędów obliczeniowych, stosując odwrotną transformację dyskretną

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

Dla poprawności prostych i prawie symetrycznych przekształceń (3) i (4) konieczne jest, aby zbiór funkcji bazowych miał własności ortogonalności i pewną normalizację. Warunek ortogonalności wygląda jak zbiór równości

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

a warunki normalizacji są zbiorem równości

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

Ponadto system funkcji bazowych nazywa się kompletnym, jeśli nie można określić więcej niż jednej funkcji, która jest ortogonalna do wszystkich funkcji bazy.

Oczywiście przy takim sformułowaniu pytania nie zachodzi żadna kompresja, ponieważ liczba wyrazów pierwotnego szeregu i liczba współczynników widmowych są takie same. Możliwość kompresji informacji pojawia się, jeśli liczbę współczynników widma można zmniejszyć od N. Na przykład, gdy niektóre współczynniki widma są równe zeru lub bliskie niego. Wtedy współczynniki te można pominąć, a otrzymane widmo będzie krótsze. W pierwszym przypadku, gdy pominiemy tylko zerowe współczynniki widma, zostanie przywrócony pierwotny ciąg liczb aż do błędów obliczeniowych. Jeśli pominiemy współczynniki widma, które we wskazanym stopniu są bliskie zeru, to odtworzone wartości pierwotnego szeregu będą zawierały nie tylko błędy obliczeniowe, ale także błędy wynikające z niedokładnego przedstawienia widma. Im większy błąd w rekonstrukcji wyrazów szeregu pierwotnego flonyœaeM, TeM, tym większą liczbę współczynników widmowych można pominąć.

Jeśli oznaczymy przez n liczbę zaniedbanych współczynników widma, wówczas stosunek będzie procentowy

kwadrat = (n/N) -100% (7)

można nazwać stopniem kompresji oryginalnej informacji. Rzeczywiście, w tym przypadku reprezentujemy to za pomocą współczynników widma N-n zamiast wartości N oryginalnej serii. Przy sq = 0 kompresja w ogóle nie występuje, a przy sq = 100% osiąga hipotetyczną wartość graniczną. Rzeczywiste przypadki wahają się od 0% do 100%.

Praktyczna strona wdrożenia tego pomysłu jest nieco bardziej skomplikowana. Jeśli skończone (końcowe) współczynniki widmowe są zerowe lub małe we wskazanym stopniu, wówczas nie jest trudno odrzucić n z nich i osiągnąć w ten sposób kompresję kwadratową.

Jeżeli wśród współczynników widma w danym stopniu są zerowe lub bliskie zeru, lecz nie są one ostateczne, wówczas pojawia się trudność w przedstawieniu takiego widma z punktu widzenia kompresji informacji. W takim przypadku należy albo podać wszystkie współczynniki widma, w tym zerowe i zbliżone do nich, a wtedy kompresja nie nastąpi. Lub określ grupy o zerowych współczynnikach widmowych według numeru początkowego elementu w grupie i liczby elementów grupy. To w naturalny sposób zmniejsza stopień kompresji oryginalnej serii liczb. Jeżeli zerowe elementy widma nie są ostateczne lub nie tworzą grup, a ich numeracja nie układa się w prosty wzór, to w ten sposób nie uzyskuje się kompresji informacji.

Zatem możliwość kompresji informacji i stopień jej kompresji zależą zarówno od samego ciągu liczb (1), jak i od zbioru funkcji (2), które stanowią podstawę rozkładu widmowego Ca. Ponieważ dany jest nam ciąg liczb Xk, możemy kontrolować stopień kompresji, zmieniając podstawę rozkładu widmowego. Ale przy wybranej podstawie Ф(х) charakter podanych informacji będzie miał wpływ zarówno na

możliwości kompresji i stopień kompresji. Baz funkcjonalnych, które z powodzeniem można wykorzystać do różnorodnych zadań prezentowania informacji, jest naprawdę sporo. Do najbardziej znanych należą podstawy funkcji potęgowych i ich warianty wielomianowe w postaci wielomianów Czebyszewa i Legendre'a, a także podstawy Krawczuka, Charliera i Meissnera. Ale najbardziej znana nam jest podstawa funkcji trygonometrycznych:

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

lub odpowiednia podstawa wykładnicza w postaci zespolonej:

exp(-j 2nax). (8)

W tym przypadku widmo współczynników Ca jest widmem w jego zwykłym sensie fizycznym, jako zbiór amplitud pewnego zestawu częstotliwości o ograniczonym zakresie i określonej rozdzielczości częstotliwości. Ponieważ w tym przypadku podstawa została już wybrana, możliwości kompresji są obecnie kojarzone jedynie z charakterem informacji źródłowej. Jeżeli ma ona charakter adekwatny do wybranej podstawy (8), tj. składa się z liniowej kombinacji skończonej liczby funkcji okresowych, wówczas widmo będzie zawierać tylko skończoną liczbę niezerowych współczynników i powstaje możliwość kompresji informacji.

3. Układ funkcyjny Walsha-Paleya

Jeśli początkowa informacja ma inny charakter, na przykład zmienia się zgodnie z prawem potęgowym, wykładniczym lub logarytmicznym, wówczas w widmie wszystkie jej współczynniki nie są wystarczająco małe, a kompresja jest albo niemożliwa, albo stopień kompresji jest niewielki. W takich przypadkach rozsądne jest zastosowanie innej podstawy funkcjonalnej. Ponieważ dla innych baz nie ma jasnej fizycznej reprezentacji widma, możemy zinterpretować (2) jako wzory na przejście z układu współrzędnych Xk do innego układu współrzędnych Fa(X). Jeżeli część współczynników jest równa zeru, oznacza to, że wektor określony przez współrzędne w postaci pierwotnego ciągu liczb, w nowym układzie współrzędnych znajduje się w hiperpłaszczyźnie współrzędnych o wymiarze N-n. Wśród istniejących możliwości istnieje kilka baz generowanych przez funkcje Rademachera dla Z e (0,1):

R0(z) = 1, Rk(z) = znak (sin (2k nz)), k = 1,2,..., (9)

które zgodnie z zawartą w nich funkcją znak() przyjmują tylko dwie wartości: +1 lub -1.

Układ funkcji (9) jest ortogonalny i znormalizowany, ale nie jest kompletny. Można do tego dodać funkcje postaci znaku (cos2knz), które są również ortogonalne do funkcji układu (9). Zatem na podstawie przedstawień (9) buduje się inne kompletne układy, wykorzystując iloczyny funkcji Rademachera i wprowadzając pewne uporządkowanie do uzyskanych w ten sposób nowych funkcji.

Najbardziej interesujący w zastosowaniach nawigacyjnych pod względem kompresji informacji jest układ funkcyjny Walsha-Paleya. Tworzenie tego systemu jest ściśle związane z liczbami binarnymi jego funkcji składowych. W szczególności funkcja Walsha-Paleya z liczbą a jest iloczynem funkcji Rademachera z liczbami tych bitów binarnych a, w których znajdują się jedynki. Jeśli zapiszemy liczbę a w reprezentacji binarnej z n = log N bitów

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

wówczas funkcje systemu Walsha-Paleya można przedstawić w następujący sposób:

Wa(z) = Pk M. Sama liczba może być przedstawiona podobnie jak (12) w postaci binarnej:

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

Następnie układ funkcji Walsha-Paleya zostanie ostatecznie przedstawiony w postaci

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

który jest używany we wszystkich kolejnych obliczeniach. Poniżej podano funkcję programową WolshPaly() w języku Pascal służącą do generowania funkcji Walsha-Paleya za pomocą wzorów (16). Dla N = 8 wartości funkcji Walsha-Paleya No(/) podano w tabeli. 1.

Tabela 1. Wartości funkcji Walsha-Paleya dla N = 8

] 0 1 2 3 4 5 6 7

0 1 1 1 1 1 1 1 1

Nie wchodząc w szczegóły, wspomnimy po prostu o istnieniu systemów funkcji Hadamarda i Harmutha, które od szczegółowo rozpatrywanego systemu funkcji Walsha-Paleya różnią się jedynie sposobem organizacji tych samych funkcji. To rząd funkcji Walsha-Paleya zapewnia największą liczbę końcowych współczynników widma, które w danym stopniu są zerowe lub bliskie zeru.

4. Zbieżność szeregu Walsha-Paleya

Funkcje Walsha posiadają szereg przydatnych właściwości, wśród których prezentujemy właściwość symetrii wykorzystywaną w obliczeniach:

Szch (a/Szch. (17)

Binarna reprezentacja numerów funkcji Walsha z n = logN bitów określa rząd p i rangę r funkcji. Rząd to największa liczba cyfry binarnej, która jest równa 1. Rangą funkcji jest liczba niezerowych cyfr binarnych, np. funkcja Walsha o liczbie a = 9 dla N = 16 i n = 4 jest reprezentowane w postaci binarnej jako 1001, a zatem jego ranga g = 2 (dwa

cyfry niezerowe) i kolejność p = 3 (najbardziej znacząca cyfra niezerowa to trzecia, gdyż liczenie zaczyna się od zera). Jeśli funkcja o numerze a ma rangę r, to jej liczbę można przedstawić jako:

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

gdzie tsk (k = 1, 2,..., r) to liczba niezerowych bitów binarnej reprezentacji liczby a. Na przykład liczbę 9 można przedstawić jako 23 + 20, biorąc pod uwagę binarną reprezentację liczby 1001. Bezpośrednio w przypadku problemu kompresji oryginalnej informacji, tempo, w jakim współczynniki rozszerzalności Ca w bazie Walsha maleje wraz ze wzrostem liczby podwyżki są ważne. Jeżeli funkcja reprezentowana przez szereg (1) ma pochodną ciągłą aż do tego rzędu, a maksymalna wartość modułu pochodnej |A"(m)| wynosi M, to współczynniki widma o liczbach a, których stopień jest nie mniejszy niż rząd pochodnej (r > tak), spełnia nierówność (Design of special..., 1984):

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

To właśnie ta ważna nierówność gwarantuje szybką zbieżność współczynników widmowych Ca w miarę wzrostu liczby a i otwiera perspektywy kompresji informacji tabelarycznych. Rzeczywiście, rząd r funkcji Walsha wzrasta wraz z numerem funkcji a, tak że warunek r > w jest spełniony dla dużych liczb a. Oznacza to, że oszacowanie (19) dotyczy końcowych współczynników rozszerzalności.

Tabela 2. Współczynniki ekspansji widmowej funkcji potęgowych w bazie Walsha

RANGA ZAMÓWIENIA STOPIEŃ FUNKCJI

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

Jeśli dodatkowo funkcja ma skończoną liczbę niezerowych pochodnych (na przykład funkcja potęgowa), to wszystkie współczynniki o liczbach, których rangi są większe od tej potęgi, są identycznie równe zeru. Ale w tym celu konieczne jest, aby liczba N była wystarczająco duża, a ranga „udała się” stać się większa niż liczba najwyższej pochodnej. Jako przykład rozważmy ekspansję widmową funkcji potęgi reprezentowanej przez szereg (1) z liczbą próbek równą 16 (^ = 16, n = 4). Niewielką liczbę próbek wybrano jedynie dla przejrzystości przykładowych wyników. Powyżej w tabeli. 2 przedstawia, w zaokrągleniu do dwóch cyfr, współczynniki rozszerzalności widmowej dla różnych funkcji potęgowych: liniowej, kwadratowej, sześciennej i piątego stopnia – z jednoczesnym wskazaniem liczby a widma i jego rangi r.

Przykład ten pokazuje, że im niższy stopień funkcji generującej ciąg liczb (1), tym większy stopień kompresji szans, jaki można osiągnąć podczas rozwijania. Jeśli szereg jest krótki, a stopień duży, to w ogóle nie uzyskuje się kompresji, jak to ma miejsce w przypadku piątego stopnia funkcji. Jeśli dla tego samego stopnia funkcji zwiększymy liczbę wyrazów szeregu, a co za tym idzie, liczbę współczynników widma, to stopień

kompresja rośnie. Zatem przy N = 64 mkw. = 7,8%, przy N = 128 mkw. = 18,0%, przy N = 256 mkw. = 23,8%.

Zauważmy na marginesie, że w przypadku widma Fouriera w żadnym z powyższych przypadków nie dochodzi do kompresji – oczywista jest nieadekwatność podstawy trygonometrycznej dla funkcji potęgowych.

4. Podstawowe wzory na dyskretną transformatę Walsha-Paleya

Zwykle mówimy o przedstawieniach danej funkcji w wybranej bazie, jednak pracując z dyskretną transformacją widmową mamy do czynienia ze zbiorem jej dyskretnych wartości. Te dyskretne wartości są reprezentowane przez serię liczb (1).

Jako podstawę funkcjonalną wybierzemy zatem układ funkcji Walsha-Paleya (16) i przedstawimy dla tego układu podstawowe wzory wyrażające własności ortogonalności i normalizacji funkcji w tym układzie oraz wzory transformacji dla niego:

Wzór na bezpośrednią dyskretną transformację Walsha w celu uzyskania widma

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

Wzór na odwrotną dyskretną transformację Walsha w celu przywrócenia pierwotnego szeregu wartości

Xk = EaCaWa(k/N).

Warunek ortogonalności i normalizacji funkcji Walsha na dyskretnym zbiorze punktów

Nie = (1/N)Zk Wp(k/N) W(k/N) = 0 jeśli p Ф q i Nie = 1 jeśli p = q. Równość Parsevala

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

co reprezentuje równość kwadratowego modułu wektora w pierwotnych układach współrzędnych Xk i nowych Ca.

5. Elementy realizacji oprogramowania

To właśnie ten zestaw formuł autor wykorzystał jako podstawę podczas kompilacji programu w języku Pascal do analizy porównawczej wyników dyskretnych transformat Fouriera i Walsha (certyfikat oprogramowania ROSAPO nr 950347 z dnia 10.02.1995). W tym przypadku transformacje dyskretne zostały zaimplementowane jako szybkie transformaty Fouriera (FFT) i transformaty Walsha (WTF) z decymacją o podstawie 2 i czasie (Rabinder i Gold, 1978). Nie ma to znaczenia przy kompresji informacji tabelarycznych, gdyż transformacja w tym przypadku jest wykonywana jednorazowo, jednak jest to bardzo istotne przy przetwarzaniu informacji w czasie rzeczywistym, aby móc uruchomić większą liczbę różnych szeregów liczbowych (tabele, funkcje ) w minimalnym czasie. Podobny program, praktycznie bez zmian, z powodzeniem zastosowano w operacyjnej analizie widmowej na pokładzie latającego laboratorium IL18-DORR PINRO. Poniżej przedstawiono dwie główne części tego programu. Jest to procedura szybkiej transformacji Walsha i funkcja obliczania wartości funkcji Walsha na podstawie liczby i argumentu. Cały program zajmuje zbyt dużo miejsca i dlatego nie jest tutaj uwzględniony.

Funkcja WolshPaly(Alf, l: liczba całkowita): liczba całkowita; var J, K, x, y, w, maskl, mask2: liczba całkowita; zaczynać

w:=l; maska1:=l; maska2:=N dział 2; dla K:=0 do N-l zaczynamy

jeśli (Alf i maska2)<>0 i (I i maska1)<>0 następnie w:=-w; maska1:=maska1*2; maska2:=maska2 dział 2; koniec;

WolshPaly:=w; koniec;

Funkcja ta przyjmuje dwa parametry — liczbę Alf i argument I funkcji Walsha i zwraca wartość samej funkcji Walsha.

Procedura FastWolshTrans(var ml, m2, m3, m4: masdat); var L, LE, LE1, I, J, IP: liczba całkowita; T1, T2: rzeczywiste;

początekLE:=1; dla L:=1 do M rozpocznij LE1:=LE; LE:=LE*2;

dla J:=1 do LE1 zacznij I:=J; powtórz IP:=I+LEl; T1:=m1; T2:=m2;

Jeśli L=M to zacznij

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;

Ja:=Ja+LE; do I>N; koniec; koniec;

/* "D" - znak bezpośredniej konwersji */

jeśli TIP="D" to zacznij od L:=1 do N zacznij m3[L]:=m3[L]/N; m4[L]:=m4[L]/N; koniec;

Procedura wykonuje szybką transformację Walsha danych przekazywanych do procedury w tablicach ml i m2. Wynik transformacji – widmo Walsha – procedura zwraca w tablicach m3 i m4. Jeśli dane są przekazywane do procedury w normalnej kolejności, wynik jest zwracany w odwróconej kolejności binarnej. Jeśli chcemy uzyskać zwykły porządek współczynników widma, to pierwotne dane do przetwarzania powinny być binarnie odwrócone. Binarna inwersja liczby to liczba, w której odwrócona jest kolejność jej cyfr binarnych, na przykład inwersja liczby 6 = 110 to 3 = 011. Aby odwrócić dowolną liczbę, proponowana jest procedura w języku Pascal:

Procedura MASINVERSION(sw: liczba całkowita; var m1, m2: masdat); var I, J, K, NV2: liczba całkowita; T: prawdziwy; rozpocznij NV2:=N dział 2;

dla I:=1 do N-1 zaczynamy

Jeśli ja

w przeciwnym razie rozpocznij K:=NV2; podczas gdy K

6. Kompresuj tabele z dwoma argumentami

Transformacje i kompresję jednowymiarowych tabel liniowych omówiono powyżej. Jednak większość tablic używanych w nawigacji to macierze dwuwymiarowe - prostokątne. Kwestię ich kompresji można rozwiązać na dwa sposoby. Pierwszy sposób polega na przekształceniu tabeli na liniową, biorąc pod uwagę, że powstaje ona poprzez ułożenie kolejnych wierszy tabeli macierzowej, zaczynając od pierwszego wiersza. Ta ścieżka jest dość powszechna, ponieważ w ten sposób przechowywana jest dwuwymiarowa tablica w liniowo zorganizowanej pamięci komputera. Zaletą tej metody jest to, że rozmiar takiej tabeli liniowej będzie na tyle duży, że można oczekiwać, że kompresja będzie wydajna. Ale kryją się w tym także potencjalne kłopoty. Po ułożeniu wierszy macierzy z pewnością uzyskamy skoki funkcji przy przejściu od końca jednego wiersza do początku następnego. Trudność tę można ominąć, zmieniając kolejność elementów w każdym parzystym rzędzie – odwracając ten rząd. Odpowiednio zmieni się kolejność współczynników widmowych. Ale to nie skomplikuje, a jedynie zmieni kolejność liczb podczas przywracania wartości samej funkcji. Jeśli więc numer wartości przywróconej funkcji wynosił Npq = (p - 1) M + q, gdzie p jest numerem wiersza zawierającego liczbę M elementów, a q jest numerem kolumny, to po odwracając dla parzystych wierszy liczba ta będzie równa (p - 1) M + (M- q + 1).

Drugi sposób polega na pierwszym przekształceniu widmowym wierszy tabeli, a następnie przekształceniu wynikowego widma pośredniego wzdłuż kolumn. Wadą tej metody jest niski stopień kompresji wynikający z małej długości wierszy i kolumn. To prawda, że ​​efekt kompresji jest wzmocniony przez podwójną konwersję zarówno wierszy, jak i kolumn. Na przykład, jeśli wiersze i kolumny zostaną skompresowane tylko o 10%, całkowity efekt kompresji wyniesie 1 - 0,9x0,9 = 0,19 = 19%. Jeśli na przykład wiersze tabeli zmieniają się zgodnie z prawem kwadratowym, a kolumny zgodnie z prawem sześciennym, wówczas ogólny efekt kompresji zgodnie z danymi tabeli. 2 równa się 1-(1-0,188)x(1-0,63) = 0,24 = 24%.

Jako konkretny przykład przedstawiamy wyniki przekształcenia tablicy funkcji całkowej Laplace’a (Kondrashikhin, 1969), która jest wykorzystywana w nawigacji przy ocenie niezawodności nawigacji. Tutaj jest to przedstawione w postaci matrycy 30x10, tj. składa się z 30 wierszy i 10 kolumn. Nie ma sensu konwertować go na dwuwymiarowy: w liniach jest za mało (10) elementów. Dlatego przekształcamy go jako tabelę liniową zawierającą 300 wartości. W przykładzie założymy, że jest 256 = 28 wartości, ale moglibyśmy uzupełnić tabelę zerami i przyjąć, że liczba wartości wynosi 512 = 29. W obu przypadkach uzyskuje się ten sam wynik: liczbę końcową. zer o stopniu zbliżenia do zera rzędu 0,01% wartości maksymalnej współczynnik wynosi 46,5%. Przywrócenie funkcji ze zbioru współczynników widma skompresowanego do 53,5% dało błędy: średnia kwadratowa 0,005 i maksymalnie 0,057. Przykład pokazuje skuteczność transformacji tabeli.

7. Wnioski

Przeprowadzone badania związane z wyborem bazy funkcjonalnej Walsha-Paleya pokazują, że ta baza funkcjonalna może być z powodzeniem stosowana w różnych systemach przetwarzania informacji, które nie mają wyraźnie okresowego charakteru. W tym przypadku przewaga takiej bazy funkcjonalnej nad bazą Fouriera jest oczywista. Ponadto baza Walsha-Paleya daje dobry efekt w kompresji informacji. Ilustruje to przykład tablicy funkcji całkowych Laplace’a, typowej dla problemów niezawodności nawigacji, gdzie efekt kompresji sięgał 53,5%.

Literatura

Gold B., Rader Ch. Cyfrowe przetwarzanie sygnału. M., Sov.radio, 367 e., 1993. Kondrashikhin V.T. Teoria błędu. M., Transport, 256 e., 1969.

Projektowanie specjalistycznych systemów informatycznych i obliczeniowych. wyd.

Smirnova Yu.N. M., Szkoła Wyższa, 359 e., 1984. Rabinder L., Gold B. Teoria i zastosowania cyfrowego przetwarzania sygnałów. M., Mir, 528 e., 1978. Trakhtman A.N., Trakhtman V.A. Wprowadzenie do ogólnej teorii spektralnej sygnałów. M., Radio Sow., 312 e., 1978.