Sekwencje uzupełniające

Aby zapoznać się z komplementarnymi sekwencjami w biologii, zobacz komplementarność (biologia molekularna) . Sekwencje liczb całkowitych z komplementarnymi zbiorami elementów można znaleźć w twierdzeniu Lambeka-Mosera .

W matematyce stosowanej sekwencje komplementarne ( CS ) to pary sekwencji z użyteczną właściwością, że ich współczynniki aperiodycznej autokorelacji poza fazą sumują się do zera. Binarne sekwencje komplementarne zostały po raz pierwszy wprowadzone przez Marcela JE Golaya w 1949 r. W latach 1961–1962 Golay podał kilka metod konstruowania sekwencji o długości 2 ^N i podał przykłady sekwencji komplementarnych o długości 10 i 26. W 1974 r. RJ Turyn podał metodę konstruowania sekwencji o długości mn z ciągów o długości m i n , co pozwala na konstruowanie ciągów o dowolnej długości postaci 2 ^N 10 ^K 26 ^M .

Później inni autorzy uogólnili teorię sekwencji komplementarnych na polifazowe sekwencje komplementarne, wielopoziomowe sekwencje komplementarne i dowolne złożone sekwencje komplementarne. Rozważono również zestawy uzupełniające ; mogą one zawierać więcej niż dwie sekwencje.

Definicja

₀₀ Niech ( a , a ₁ , ..., a _{N − 1} ) i ( b , b ₁ , ..., b _{N − 1} ) będą parą ciągów dwubiegunowych, co oznacza, że ​​a ( k ) i b ( k ) mają wartości +1 lub −1. Niech aperiodyczna funkcja autokorelacji ciągu x będzie zdefiniowana przez

${\ Displaystyle R_ {x} (k) = \ suma _ {j = 0} ^ {Nk-1} x_ {j} x_ {j + k}. \,}$

Wtedy para ciągów a i b jest komplementarna, jeśli:

${\ Displaystyle R_ {a} (k) + R_ {b} (k) = 2N, \,}$

dla k = 0 i

${\ Displaystyle R_ {a} (k) + R_ {b} (k) = 0, \,}$

dla k = 1, ..., N - 1.

Lub używając delty Kroneckera możemy napisać:

${\ Displaystyle R_ {a} (k) + R_ {b} (k) = 2N \ delta (k), \,}$

Możemy więc powiedzieć, że suma funkcji autokorelacji sekwencji komplementarnych jest funkcją delta, która jest idealną autokorelacją dla wielu zastosowań, takich jak kompresja impulsów radarowych i telekomunikacja z rozproszonym widmem .

Przykłady

• Jako najprostszy przykład mamy ciągi o długości 2: (+1, +1) i (+1, −1). Ich funkcjami autokorelacji są (2, 1) i (2, −1), które sumują się do (4, 0).
• W następnym przykładzie (ciągi o długości 4) mamy (+1, +1, +1, −1) i (+1, +1, −1, +1). Ich funkcjami autokorelacji są (4, 1, 0, −1) i (4, −1, 0, 1), które sumują się do (8, 0, 0, 0).
• Przykładem długości 8 jest (+1, +1, +1, −1, +1, +1, −1, +1) i (+1, +1, +1, −1, −1, −1 , +1, −1). Ich funkcje autokorelacji to (8, −1, 0, 3, 0, 1, 0, 1) i (8, 1, 0, −3, 0, −1, 0, −1).
• Przykład długości 10 podany przez Golaya to (+1, +1, −1, +1, −1, +1, −1, −1, +1, +1) i (+1, +1, −1 , +1, +1, +1, +1, +1, −1, −1). Ich funkcje autokorelacji to (10, −3, 0, −1, 0, 1, −2, −1, 2, 1) i (10, 3, 0, 1, 0, −1, 2, 1, −2 , −1).

Własności komplementarnych par sekwencji

• Sekwencje komplementarne możemy

• mają komplementarne widma. Ponieważ funkcja autokorelacji i widma mocy tworzą parę Fouriera, sekwencje komplementarne mają również widma komplementarne.

$CS$

transformata

gdzie _stałą stałą .

Sa _i Sb są _zdefiniowane jako kwadrat wielkości transformaty Fouriera sekwencji. Transformata Fouriera może Z = ej ^{ω być} bezpośrednią DFT sekwencji, może być DFT sekwencji wypełnionych zerami lub może być ciągłą transformatą Fouriera sekwencji, która jest równoważna transformacji Z dla .

• Widma CS mają górną granicę. Ponieważ S _a i S _b są wartościami nieujemnymi, możemy napisać

$\ Displaystyle S_ {a} = C_ {S} -S_ {b}<C_ {S},}$

także

${\ Displaystyle S_ {b} <C_ {S}.}$

• Jeśli którakolwiek z sekwencji pary CS zostanie odwrócona (pomnożona przez -1), pozostają one komplementarne. Mówiąc bardziej ogólnie, jeśli którykolwiek z ciągów zostanie pomnożony przez e ^{j φ} , pozostają one komplementarne;
• Jeśli którakolwiek z sekwencji zostanie odwrócona, pozostają one komplementarne;
• Jeśli którakolwiek z sekwencji jest opóźniona, pozostają one komplementarne;
• Jeśli sekwencje są zamienione, pozostają komplementarne;
• Jeśli oba ciągi są pomnożone przez tę samą stałą (rzeczywistą lub zespoloną), pozostają one komplementarne;
• Jeśli obie sekwencje zostaną zdziesiątkowane w czasie przez K, pozostają komplementarne. Dokładniej, jeśli z komplementarnej pary ( a ( k ), b ( k )) utworzymy nową parę ( a ( Nk ), b ( Nk )) z odrzuconymi pominiętymi próbkami, to nowe sekwencje są komplementarne.
• Jeśli naprzemienne bity obu sekwencji są odwrócone, pozostają one komplementarne. Ogólnie rzecz biorąc, dla dowolnych sekwencji złożonych, jeśli obie sekwencje są pomnożone przez e ^{j π kn / N} (gdzie k jest stałą, a n jest indeksem czasu), pozostają one komplementarne;
• Nową parę komplementarnych sekwencji można utworzyć jako [ a b ] i [ a - b ], gdzie [..] oznacza konkatenację, a aib są parą CS;
• Nową parę sekwencji można utworzyć jako { a b } i { a − b }, gdzie {..} oznacza przeplatanie się sekwencji.
• Nową parę ciągów można utworzyć jako a + b i a − b .

Para Golaya

Komplementarną parę a , b można zapisać jako wielomiany A ( z ) = a (0) + a (1) z + ... + a ( N − 1) z ^{N −1} i podobnie dla B ( z ). Właściwość komplementarności sekwencji jest równoważna z warunkiem

${\ Displaystyle \ vert A (z) \ vert ^ {2} + \ vert B (z) \ vert ^ {2} = 2N \,}$

dla wszystkich z na okręgu jednostkowym, czyli | z | = 1. Jeśli tak, A i B tworzą parę wielomianów Golaya . Przykłady obejmują wielomiany Shapiro , które dają początek komplementarnym ciągom o długości potęgi dwójki .

Zastosowania sekwencji komplementarnych

• Spektrometria wieloszczelinowa
• Pomiary ultradźwiękowe
• Pomiary akustyczne
• kompresja impulsu radarowego
• Wi-Fi ,
• Sieci bezprzewodowe 3G CDMA
• Systemy komunikacji OFDM
• Systemy wykrywania kół pociągu
• Badania nieniszczące (NDT)
• Komunikacja
• kodowane maski aperturowe są projektowane przy użyciu dwuwymiarowego uogólnienia komplementarnych sekwencji.

Zobacz też

• Kod binarny Golay ( kod korygujący błędy )
• Złote sekwencje
• Sekwencje Kasami
• Sekwencja polifazowa
• Pseudolosowe sekwencje binarne (zwane także sekwencjami o maksymalnej długości lub sekwencjami M)
• Trójskładnikowy kod Golaya ( kod korygujący błędy )
• Sekwencje Walsha-Hadamarda
• Sekwencja Zadoffa-Chu

•   Golay, Marcel JE (1949). „Spektroskopia multilitowa”. J. opt. soc. jestem . 39 (6): 437–444. doi : 10.1364/JOSA.39.000437 . PMID 18152021 .
• Golay, Marcel JE (kwiecień 1961). „Seria uzupełniająca”. IRE Trans. Inf. Teoria . 7 (2): 82–87. doi : 10.1109/TIT.1961.1057620 .
• Golay, Marcel JE (1962). „Uwaga na temat„ serii uzupełniającej ” ”. proc. IRE . 50 : 84. doi : 10.1109/JRPROC.1962.288278 .
• Turyn, RJ (1974). „Macierze Hadamarda, jednostki Baumerta-Halla, sekwencje czterech symboli, kompresja impulsów i kodowanie fal powierzchniowych” . J. Grzebień. Teoria A. 16 (3): 313–333. doi : 10.1016/0097-3165(74)90056-9 .
•   Borwein, Peter (2002). Wycieczki obliczeniowe w analizie i teorii liczb . Skoczek. s. 110–9. ISBN 978-0-387-95444-8 .
• Donato, PG; Ureña, J.; Mazo, M.; De Marziani, C.; Ochoa, A. (2006). „Projektowanie i przetwarzanie sygnału magnetycznego układu czujników do wykrywania kół pociągu”. Czujniki i siłowniki A: Fizyczne . 132 (2): 516–525. doi : 10.1016/j.sna.2006.02.043 .