Материалы что дал Мухачев / Материалы что дал Мухачев / Білети_коротки_відповіді / Білети_відпові_УБДМ / Sp_Otvet17
.doc№ 17. Лінійна складність послідовності. Формулювання теореми про лінійну складність нелінійного комбінуючого генератора.
Лінійна складність періодичної послідовності – це нійменша довжина регістру звуву з лінійним зворотним зв’язком, що породжує цю послідовність.
У комбінуючих генераторів в кожному такті роботи чергові елементи послідовностей, що виробляються кожним з декількох регістрів зсуву, надходять на вхід деякої функції. Значення цієї функції є виходом генератора (елементом гами).
гама
Регістр
2
Регістр
k F
Регістр
1 . .. .
Комбінуюючий
генератор
Теорема про лінійну складність нелінійного комбінуючого генератора.
Нехай
комбінуючий генератор складається з
РЗЛЗЗ
над
максимального періоду і різної довжини
.
Нехай булєва функція
є сумою в полі
мономів виду
.
Тоді
лінійна складність генератора дорівнює
сумі в полі дійсних чисел всіх мономів
виду
.