Doplňkové sekvence - Complementary sequences

Doplňkové sekvence v biologii viz komplementarita (molekulární biologie).

V aplikované matematice komplementární sekvence (CS) jsou páry sekvence s užitečnou vlastností, že jejich mimo-fáze neperiodické autokorelace součty koeficientů na nulu. Binární komplementární sekvence byly poprvé zavedeny Marcel J. E. Golay v roce 1949. V letech 1961–1962 dal Golay několik metod pro konstrukci sekvencí délky 2^N a uvedl příklady komplementárních sekvencí o délkách 10 a 26. V roce 1974 R. J. Turyn poskytl metodu pro konstrukci sekvencí o délce mn ze sekvencí délek m a n což umožňuje konstrukci sekvencí libovolné délky formy 2^N10^K.26^M.

Teorie dalších komplementárních sekvencí byla později zobecněna jinými autory na polyfázové komplementární sekvence, víceúrovňové komplementární sekvence a libovolné komplexní komplementární sekvence. Doplňkové sady byly rovněž zváženy; mohou obsahovat více než dvě sekvence.

Definice

Nechť (A₀, A₁, ..., A_N − 1) a (b₀, b₁, ..., b_N − 1) být dvojicí bipolárních sekvencí, což znamená A(k) a b(k) mají hodnoty +1 nebo -1. Nechť neperiodické funkce autokorelace sekvence X být definován

${displaystyle R_ {x} (k) = součet _ {j = 0} ^ {N-k-1} x_ {j} x_ {j + k}.,}$

Pak dvojice sekvencí A a b je komplementární, pokud:

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

pro k = 0 a

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

pro k = 1, ..., N − 1.

Nebo pomocí Kroneckerova delta můžeme psát:

${displaystyle R_ {a} (k) + R_ {b} (k) = 2Ndelta (k) ,,}$

Můžeme tedy říci, že součet funkcí autokorelace komplementárních sekvencí je funkce delta, což je ideální autokorelace pro mnoho aplikací, jako je radar pulzní komprese a rozprostřené spektrum telekomunikace.

Příklady

• Jako nejjednodušší příklad máme sekvence délky 2: (+1, +1) a (+1, −1). Jejich autokorelační funkce jsou (2, 1) a (2, -1), které přidávají až (4, 0).
• Jako další příklad (sekvence délky 4) máme (+1, +1, +1, −1) a (+1, +1, −1, +1). Jejich autokorelační funkce jsou (4, 1, 0, -1) a (4, -1, 0, 1), které sčítají až (8, 0, 0, 0).
• Jedním z příkladů délky 8 je (+1, +1, +1, −1, +1, +1, −1, +1) a (+1, +1, +1, −1, −1, −1 , +1, -1). Jejich autokorelační funkce jsou (8, -1, 0, 3, 0, 1, 0, 1) a (8, 1, 0, -3, 0, -1, 0, -1).
• Příklad délky 10 dané Golayem je (+1, +1, -1, +1, -1, +1, -1, -1, +1, +1) a (+1, +1, -1 , +1, +1, +1, +1, +1, -1, -1, -1). Jejich autokorelační funkce jsou (10, -3, 0, -1, 0, 1, -2, -1, 2, 1) a (10, 3, 0, 1, 0, -1, 2, 1, -2 , -1).

Vlastnosti komplementárních párů sekvencí

• Komplementární sekvence mít doplňková spektra. Protože autokorelační funkce a výkonová spektra tvoří Fourierův pár, mají komplementární sekvence také komplementární spektra. Ale protože Fourierova transformace delta funkce je konstanta, můžeme psát

${displaystyle S_ {a} + S_ {b} = C_ {S},}$

kde C_S je konstanta.

S_A a S_b jsou definovány jako druhá mocnina velikosti Fourierova transformace sekvencí. Fourierova transformace může být přímá DFT sekvencí, může to být DFT nulových polstrovaných sekvencí nebo to může být kontinuální Fourierova transformace sekvencí, která je ekvivalentní Z transformace pro Z = E^jω.

• CS spektra jsou horní hranice. Tak jako S_A a S_b jsou nezáporné hodnoty, které můžeme zapsat

${displaystyle S_ {a} = C_ {S} -S_ {b}$

taky

${displaystyle S_ {b}$

• Pokud je některá ze sekvencí páru CS obrácená (vynásobená -1), zůstává komplementární. Obecněji, pokud je některá ze sekvencí vynásobena E^jφ zůstávají doplňkové;
• Pokud je některá ze sekvencí obrácena, zůstávají komplementární;
• Pokud je některá ze sekvencí zpožděna, zůstává komplementární;
• Pokud jsou sekvence zaměňovány, zůstávají komplementární;
• Pokud jsou obě sekvence vynásobeny stejnou konstantou (skutečnou nebo komplexní), zůstávají komplementární;
• Pokud jsou obě sekvence časově zdecimovány K. zůstávají doplňkové. Přesněji, pokud z doplňkového páru (A(k), b(k)) vytvoříme nový pár (A(Nk), b(Nk)) s vynechanými vzorky se nové sekvence doplňují.
• Pokud jsou střídavé bity obou sekvencí invertovány, zůstávají komplementární. Obecně pro libovolné složité posloupnosti, pokud jsou obě posloupnosti vynásobeny E^jπkn/N (kde k je konstanta a n je časový index) zůstávají doplňkové;
• Nová dvojice komplementárních sekvencí může být vytvořena jako [A b] a [A −b] kde [..] označuje zřetězení a A a b jsou dvojice CS;
• Nová dvojice sekvencí může být vytvořena jako {A b} a {A −b} kde {..} označuje prokládání sekvencí.
• Nová dvojice sekvencí může být vytvořena jako A + b a A − b.

Golay pár

Doplňkový pár A, b mohou být kódovány jako polynomy A(z) = A(0) + A(1)z + ... + A(N − 1)z^N−1 a podobně pro B(z). Vlastnost komplementarity sekvencí je ekvivalentní podmínce

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

pro všechny z na jednotkovém kruhu, tj. |z| = 1. Pokud ano, A a B formulář a Golay pár polynomů. Mezi příklady patří Shapiro polynomy, které dávají vzniknout komplementárním sekvencím délky a síla dvou.

Aplikace doplňkových sekvencí

• Víceosvitová spektrometrie
• Ultrazvuková měření
• Akustická měření
• radar pulzní komprese
• Wi-Fi sítě,
• 3G CDMA bezdrátové sítě
• OFDM komunikační systémy
• Detekční systémy vlakových kol^[1][2]
• Nedestruktivní zkoušky (NDT)
• komunikace
• kódovaná clona masky jsou navrženy pomocí 2-dimenzionálního zobecnění komplementárních sekvencí.

Viz také

• Binární Golay kód (Kód pro opravu chyb )
• Zlaté sekvence
• Kasami sekvence
• Polyfázová sekvence
• Pseudonáhodné binární sekvence (také zvaný sekvence maximální délky nebo M-sekvence)
• Ternary Golay kód (Kód pro opravu chyb )
• Walsh-Hadamardovy sekvence
• Sekvence Zadoff – Chu

Reference