Кіріспе

Псевдорандомды екілік тізбектің түрі

Максималды ұзындығы бар тізбек (MLS) – псевдорандомды екілік тізбектің бір түрі. Олар максималды сызықтық кері байланыс тізбектік регистрлерін пайдаланып жасалған биттік тізбектер болып табылады және олар периодтық болғандықтан, тізбектік регистрлермен бейнеленетін барлық екілік тізбектерді (нөлдік вектордан басқа) қайталайды (яғни, ұзындығы m тізбектік регистрлер үшін олар ұзындығы 2m–1 тізбектерді шығарады). MLS кейде n немесе m тізбегі деп те аталады. MLS-тер нөлге жуық тұрақты ток компонентін қоспағанда, спектрлік тұрғыдан тегіс. Бұл тізбектер Z/2Z-ге бөлінген полиномдық сақинадағы иррационалды полиномдардың коэффициенттері ретінде көрсетілуі мүмкін. MLS-тің практикалық қолданылуы импульстік жауаптарды өлшеуді қамтиды (мысалы, бөлмедегі дыбыс қайталануын немесе мұхитта сүйретілетін көздерден келу уақыттарын). Олар сондай-ақ тікелей тізбектік таралым спектрін және жиіліктік секіруді таралым спектрін қолданатын цифрлық байланыс жүйелерінде псевдорандомды тізбектерді тудыру үшін негіз ретінде, сондай-ақ кейбір fMRI эксперименттерін тиімді жобалау үшін қолданылады.

Ұрпақ

МЛС максималды сызықтық кері байланыс тізбектік тіркегіштері арқылы жасалады. 4 ұзындығындағы тізбектік тіркегішті қолданатын МЛС жасау жүйесі 1-суретте көрсетілген. Оны келесі рекурсивті қатынас арқылы өрнектеуге болады:

мұнда n – уақыт индексі, ал – 2-модульді қосуды білдіреді. Биттік мәндер үшін 0 = FALSE немесе 1 = TRUE, бұл XOR операциясына баламалы. МЛС периодтық болғандықтан және тізбектік тіркегіштер барлық мүмкін екілік мәндерді (нөлдік вектордан басқа) аралап өтеді, тіркегіштерді нөлдік вектордан басқа кез келген күйге бастамалауға болады.

Көптамалық интерпретация

GF(2) бойынша полином сызықтық кері байланыс тізбектік регистрімен байланыстырылады. Оның дәрежесі тізбектік регистрдің ұзындығымен анықталады, ал коэффициенттері 0 немесе 1 болып табылады, бұл XOR қақпасын қоректендіретін регистрдің тармақтарына сәйкес келеді. Мысалы, 1-суретте көрсетілген полином – LFSR арқылы туындайтын тізбектің максималды ұзындығы үшін қажетті және жеткілікті шарт, оның сәйкес полиномы примитивті болуы керек.

Іске асыру

MLS аппараттық немесе бағдарламалық түрде жүзеге асыруға арзан, және салыстырмалы түрде төмен реттік кері байланыс тізбектік регистрлер ұзақ тізбектерді жасай алады; 20 ұзындықтағы тізбектік регистрді пайдалану арқылы жасалған тізбек 220 - 1 үлгіден (1 048 575 үлгі) тұрады.

Ең үлкен ұзындығы реттіліктердің қасиеттері

MLS Соломон Голомбтың айтуынша, келесі қасиеттерге ие.

Сальдолық мүлік

0 және 1 сандары тізбекте шамамен бірдей жиілікте кездесуі керек. Нақтырақ айтқанда, ең ұзын тізбекте бірліктер саны нөлдер санынан бірге артық болады, себебі тек нөлдерден тұратын күй пайда бола алмайды.

Корреляция қасиеті

МЛС-тің дөңгелек автокорреляциясы Кронекер дельта функциясы болып табылады (жұмыс істеуіне қарай DC смещениесі және уақыт кешіктірілуімен). ±1 конвенциясы үшін, яғни, 1 биттік мәніне және 0 биттік мәніне сәйкес мән берілгенде, XOR көбейтіндінің теріс мәніне шамалас келеді:

мұнда – күрделі түйіндес және – дөңгелек жылжуды білдіреді. МЛС-тің сызықтық автокорреляциясы Кронекер дельтасына жуықтайды.

Хадамард трансформациясына қатынасы

Кохн мен Лемпель МЛС-тің Хадамард трансформациясымен байланысын көрсетті. Бұл байланыс МЛС-тің корреляциясын FFT сияқты жылдам алгоритм арқылы есептеуге мүмкіндік береді.