Sekvence maximální délky - Maximum length sequence
A sekvence maximální délky (MLS) je typ pseudonáhodná binární sekvence.
Jsou to bitové sekvence generované pomocí maxima posuvné registry lineární zpětné vazby a jsou tak nazýváni, protože jsou periodicky a reprodukovat každý binární sekvence (kromě nulového vektoru), které mohou být reprezentovány posuvnými registry (tj.m registry produkují sekvenci délky 2m - 1). MLS se někdy také nazývá n-sekvence nebo m-sekvence. MLS jsou spektrálně plochý, s výjimkou téměř nulového stejnosměrného termínu.
Tyto sekvence mohou být reprezentovány jako koeficienty neredukovatelných polynomů v a polynomiální kruh přes Z / 2Z.
Mezi praktické aplikace pro MLS patří měření impulzní reakce (např. místnosti dozvuk ). Používají se také jako základ pro odvození pseudonáhodných sekvencí v digitálních komunikačních systémech, které používají přímé spektrum šíření spektra a frekvenční skokové rozprostřené spektrum přenosové systémy design optického dielektrického vícevrstvého reflektoru,[1] a v efektivním designu některých fMRI experimenty.[2]
Generace
MLS jsou generovány pomocí maximálních lineárních zpětnovazebních posuvných registrů. Systém generující MLS s posuvným registrem o délce 4 je zobrazen na obr. 1. Lze jej vyjádřit pomocí následujícího rekurzivního vztahu:
kde n je časový index a představuje modulo-2 přidání. Pro bitové hodnoty 0 = FALSE nebo 1 = TRUE je to ekvivalentní operaci XOR.
Jelikož MLS jsou periodické a posuvné registry procházejí každou možnou binární hodnotou (s výjimkou nulového vektoru), lze registry inicializovat do libovolného stavu, s výjimkou nulového vektoru.
Polynomiální interpretace
A polynomiální přes GF (2) lze spojit s posuvným registrem lineární zpětné vazby. Má stupeň délky posuvného registru a má koeficienty buď 0 nebo 1, odpovídající odbočkám registru, které napájejí xor brána. Například polynom odpovídající obrázku 1 je X4 + X1 + 1.
Nutnou a dostatečnou podmínkou pro to, aby sekvence generovaná LFSR měla maximální délku, je její odpovídající polynom primitivní.[3]
Implementace
MLS je levná implementace do hardwaru nebo softwaru a registry zpětné vazby s relativně nízkou objednávkou mohou generovat dlouhé sekvence; sekvence generovaná pomocí posuvného registru délky 20 je 220 - 1 vzorek dlouhý (1048 575 vzorků).
Vlastnosti sekvencí maximální délky
MLS mají následující vlastnosti, jak je formuloval Solomon Golomb.[4]
Zůstatek majetku
Výskyt 0 a 1 v sekvenci by měl být přibližně stejný. Přesněji, v maximální délce sekvence délky existují ty a nuly. Počet jednotek se rovná počtu nul plus jedna, protože stav obsahující pouze nuly nemůže nastat.
Spustit vlastnost
„Běh“ je dílčí sekvence po sobě jdoucích „1“ nebo po sobě jdoucích „0“ v příslušném MLS. Počet běhů je počet takových dílčích sekvencí.[vágní ]
Ze všech „běhů“ (skládajících se z „1“ nebo „0“) v pořadí:
- Jedna polovina běhů má délku 1.
- Jedna čtvrtina běhů má délku 2.
- Jedna osmina běhů má délku 3.
- ... atd. ...
Korelační vlastnost
Kruhový autokorelace MLS je Kroneckerova delta funkce[5][6] (s DC offsetem a časovým zpožděním, v závislosti na implementaci). Pro konvenci ± 1, tj. Je přiřazena bitová hodnota 1 a bitová hodnota 0 , mapování XOR na zápor produktu:
kde představuje komplexní konjugát a představuje a kruhový posun.
Lineární autokorelace MLS se blíží Kroneckerově deltě.
Extrakce impulzních odpovědí
Pokud lineární invariant času (LTI) impulsní odezva systému se měří pomocí MLS, odezvu lze extrahovat z výstupu měřeného systému y[n] pomocí kruhové vzájemné korelace s MLS. Je to proto, že autokorelace MLS je 1 pro nulové zpoždění a téměř nula (-1 /N kde N je délka sekvence) pro všechny ostatní zpoždění; jinými slovy lze říci, že autokorelace MLS se blíží jednotkové impulsní funkci s rostoucí délkou MLS.
Pokud je impulzní odezva systému h[n] a MLS je s[n], pak
Vzít vzájemnou korelaci s ohledem na s[n] obou stran,
a za předpokladu, že φss je impuls (platí pro dlouhé sekvence)
Pro tento účel lze použít jakýkoli signál s impulzivní autokorelací, ale signály s vysokou činitel výkyvu, jako je samotný impuls, vytvářejí impulzní reakce se špatnou odstup signálu od šumu. Obvykle se předpokládá, že MLS by pak byl ideálním signálem, protože se skládá pouze z hodnot v plném rozsahu a jeho faktor digitálního výkyvu je minimální, 0 dB.[7][8] Avšak poté analogová rekonstrukce, ostré diskontinuity v signálu produkují silné vrcholy intersample, degradují činitel výkyvu o 4-8 dB nebo více, zvyšují se s délkou signálu, což je horší než sinusový průběh.[9] Ostatní signály byly navrženy s minimálním činitelem výkyvu, i když není známo, zda je možné je zlepšit nad 3 dB.[10]
Vztah k Hadamardově transformaci
Cohn a Lempel[11] ukázal vztah MLS k Hadamardova transformace. Tento vztah umožňuje korelace MLS, který má být vypočítán rychlým algoritmem podobným FFT.
Viz také
- Barkerův kód
- Doplňkové sekvence
- Federální norma 1037C
- Frekvenční odezva
- Zlatý kód
- Impulzní reakce
- Polynomiální kruh
Reference
- Golomb, Solomon W .; Guang Gong (2005). Návrh signálu pro dobrou korelaci: Pro bezdrátovou komunikaci, kryptografii a radar. Cambridge University Press. ISBN 978-0-521-82104-9.
- ^ Poudel, Khem Narayan; Robertson, William M. (2018-10-15). Msgstr "Maximální délka dielektrického vícevrstvého reflektoru". Kontinuum OSA. 1 (2): 358–372. doi:10.1364 / OSAC.1.000358. ISSN 2578-7519.
- ^ Buracas GT, Boynton GM (červenec 2002). "Efektivní návrh experimentů fMRI souvisejících s událostmi pomocí M-sekvencí". NeuroImage. 16 (3 Pt 1): 801–13. doi:10.1006 / nimg.2002.1116. PMID 12169264.
- ^ "Lineární zpětnovazební posuvné registry - implementace, vlastnosti M-sekvence, tabulky zpětné vazby"[1], New Wave Instruments (NW), Citováno 2013.12.03.
- ^ Golomb, Solomon W. (1967). Sekvence posuvných registrů. Holden-Day. ISBN 0-89412-048-4.
- ^ Jacobsen, Finn; Juhl, Peter Moller (04.06.2013). Základy obecné lineární akustiky. John Wiley & Sons. ISBN 978-1118636176.
Sekvence maximální délky je binární sekvence, jejíž kruhová autokorelace (kromě malé chyby DC) je funkcí delta.
- ^ Sarwate, D. V .; Pursley, M. B. (01.05.1980). Msgstr "Křížové korelační vlastnosti pseudonáhodných a souvisejících sekvencí". Sborník IEEE. 68 (5): 593–619. doi:10.1109 / PROC.1980.11697. ISSN 0018-9219.
- ^ Výukový program „Malá MLS (sekvence maximální délky) | dspGuru.com“. dspguru.com. Citováno 2016-05-19.
jeho RMS a špičkové hodnoty jsou X, takže činitel výkyvu (peak / RMS) se rovná 1, což je nejnižší hodnota, kterou může získat.
- ^ „Další elektroakustické měřicí techniky“. www.clear.rice.edu. Citováno 2016-05-19.
Faktor výkyvu pro MLS je velmi blízký 1, takže má smysl použít tento druh vstupního signálu, když pro naše měření potřebujeme vysoký poměr signálu k šumu
- ^ Chan, Ian H. „Swept Sine Chirps for Measuring Impulse Response“ (PDF). thinkrs.com. Citováno 2016-05-19.
- ^ Friese, M. (01.10.1997). „Vícetónové signály s nízkým činitelem výkyvu“ (PDF). Transakce IEEE na komunikaci. 45 (10): 1338–1344. doi:10.1109/26.634697. ISSN 0090-6778.
- ^ Cohn, M .; Lempel, A. (leden 1977). „On Fast M-Sequence Transforms“. IEEE Trans. Inf. Teorie. 23 (1): 135–7. doi:10.1109 / TIT.1977.1055666.
externí odkazy
- Bristow-Johnson, Robert. „Malý výukový program MLS“. - Krátký online tutoriál popisující, jak se MLS používá k získání impulsní odezva a lineární časově invariantní systém. Také popisuje, jak se nelinearity v systému mohou projevit jako rušivé hroty ve zjevné impulzní odezvě.
- Hee, Jensi. „Měření impulzní odezvy pomocí MLS“ (PDF). - Příspěvek popisující generování MLS. Obsahuje C-kód pro generování MLS pomocí až 18-tap-LFSR a odpovídající Hadamardovu transformaci pro extrakci impulzní odezvy.
- Kerr, Wesley; Drucker, Daniel. „Vytvoření M-sekvencí“. Laboratoř Geoffrey Aguirre. University of Pennsylvania.
- "Lineární zpětnovazební posuvné registry". Nové vlnové nástroje. 2005. - Vlastnosti sekvencí maximální délky a komplexní tabulky zpětné vazby pro maximální délky od 7 do 16 777 215 (3 až 24 stupňů) a dílčí tabulky pro délky až 4 294 967 295 (25 až 32 stupňů).
- Schäfer, Magnus (říjen 2012). „Aachen Impulse Response Database“. Institute of Communication Systems and Data Processing, RWTH Aachen University. V1.4. Databáze (binaurální) impulzní odezvy místnosti generovaná pomocí sekvencí maximální délky]
- „Efektivní posuvné registry, čítače LFSR a generátory dlouhých pseudonáhodných sekvencí - zastaralé“ (PDF). Xilinx. Červenec 1996. XAPP052 v1.1. - Implementace lfsr v FPGA zahrnuje seznam odboček pro 3 až 168 bitů