Задачи и упражнения

• 8.1. Образует ли векторное пространство множество всех последовательностей над полем Р, длина периода которых (при t > 2):
  • а) не больше t;
  • б) не меньше t>
  • в) равна ?;
  • г) кратна t?
• 8.2. <1 если последовательность {х,} над Z_m периодическая, то v ({x,}) = v ({ax,}) и ?({х,}) = ?({ах,}), где а е Z_m, (т_у а) = 1.
• 8.3. = Х_{• … • Х_пи t (X_J = 2¹⁰, то имеется i е {1, …, п) такое, что t (Xj^) = 2¹⁰.
• 8.4. Пусть последовательности {х,} и {г/,} над Z_m периодические с длинами периодов t_{ и t₂ соответственно, где t₂)= 1.
• а) <] длина периода t последовательности {(х, — + у_{) modm} равна t_{t₂. Каково наименьшее из возможных значений t, если (t_[y t₂) = d> 1?
• б) При каких a, b е Z_m длина периода последовательности {(ах, + by,) modw} равна tfo?
• 8.5. Пусть {х,} — периодическая последовательность над X и t (X_J = t. Какова при натуральном г длина периода т подпоследовательности:
  • а) {*"•};
  • б) полученной из {х,} изъятием подпоследовательности {х"}, если г делит t?

• 8.6. Преобразование# множества V" имеет длины предпериодов и периодов нулевого вектора, равные соответственно 25 и 17. При каких натуральных п это возможно?
• 8.7. Пусть т> 2⁸ и {*,?}, {г/,}, {z,} — периодические последовательности над Z_m с дли

нами периодов 255,96 и 34 соответственно. Может ли быть равной 60 длина периода последовательности {х) + - z,}?

• 8.8. Постройте граф преобразования#регистра левого сдвига длины п с обратной связью /, определите длины предпериодов и периодов нулевого вектора и преобразования #:
  • а) n = A_Jf (x_{,…, x₄)=x_l®x₂x_4f
  • б) п = 4,/(х_{,…, х₄) = х_хх₃ 0 х^х₄ 0 1;
  • в) п = 5, f (x_[y …, ДГ₅) = © *3*4 © *2*4 © *2 © *1 © ^
  • г) п = 5, /(*!, …, ДГ₅) = Х2*3*4*Г) © * 1*3*4 © *2*4 © *3 © *2 © *1 © 1 •
• 8.9. Какова цикловая структура и длина периода аффинного преобразования h множества V_n, гдеh (x) = х0 а при а* 0?
• 8.10. Является ли п.ц. подстановкой преобразование g (.r) = (ах+ b) mod2″, если:
  • а) п = 10, а = 10, Ь-1
  • б) п = 10, а = 9, b = 6;
  • в) п — 10, а = 9, b = 9?
• 8.11. Является ли п.ц. преобразование # множества V_n:
  • а) n = 3,g={x_x 0 _ух_х 0дг₂, *! ^v*₂(c)*3};
  • б) n = 3, g= {х_ь х_{ 0*2 Ф 1, *i v х₂ v лг₃};
  • в) Я = 4, g = {*_t, 0 ЛГ₂> *1*2 © *3' *1*2 © *2*3 © *4}-
• 8.12. Какова цикловая структура и длина периода преобразования g^k, если g — преобразование Л PCmax-w над GF (2)?
• 8.13. <1 регистр с функцией обратной связи f (x_{,…, х_п) 0 х₂…х_п является п.ц., где f (x_t, …,*") — функция обратной связи ЛРСтах-я над GF (2).
• 8.14. Пусть /(jtj, x_w) = Xj 0 а^х₉ 0…0 а^с_п — функция обратной связи левого ЛРС над GF (2).
• 1? <1 преобразование регистра сдвига с обратной связью/(*_{…, i")0i2.In не имеет неподвижных элементов ая0…0 а2 = 1.}
• 8.15. Пусть# — преобразование двоичного ЛРСтах-я, /г=х®а — аффинное преобразование множества V". Определите неподвижные элементы преобразования hgh.
• 8.16. <] t_g = t/jg/j для преобразований #, h е П (Х), если h — инволюция.
• 8.17. Какова длина периода аффинного преобразования h = #0 а множества V_n, где# — линейная инволюция и а — ненулевой вектор?
• 8.18. <] многочлен над GF (2) не примитивный, если не содержит мономов нечетных степеней.
• 8.19. Является ли примитивным многочлен /(Я) над полем GF (2):
  • а) ДЯ) = Я5(c)Я²0Я;
  • б) /(А.) = Я,⁵ 0 Я² 0 Л 0 1;
  • в) /(Я) = А.⁶ 0 X⁴ 0 1;
  • г) /(Я) = Я¹¹ 0 Я¹⁰ 0 Я⁹ 0 Я⁷ 0 Я⁶ 0 Я⁵ 0 Я² 0 Я 0 1.
• 8.20. <1 для линейного преобразования # пространства Р^п:
  • а) множество циклических вершин графа Г (#) образует подпространство;
  • б) в Г (#) длина одного из циклов кратна длине каждого цикла.
• 8.21. Определите или оцените длину периода последовательности, полученной как сумма:
  • а) ЛРСтах-13, ЛРСтах-17, ЛРСтах-19;
  • б) ЛРСтах-15, ЛРСтах-18, ЛРСтах-21.
• 8.22. Определите или оцените длину периода последовательности, полученной как сумма трех последовательностей с длинами периодов т, 0, р, где р — простое, (т, 0) = d и т, 0 не кратны р.

• 8.23. Пусть Х_+ = {;*:₀,…, Xi__x) — отличная от {м,и) последовательность длины / над Р^т, I > 1. Оцените Л (Х__>), если / > 1 и вектор Xj__x линейно выражается через векторы Х₀, …, Xf_2>
• 8.24. Оцените линейный размах последовательности (а, …, а) длины /, а е Р^т_у при а Ф и.
• 8.25. Является ли минимальный многочлен последовательностиХ_>над Р^п неприводимым? Обоснуйте примерами.
• 8.26. Оцените линейную сложность последовательности#^, где# — полноцикловая подстановка множества У₄₀.
• 8.27. Постройте чисто периодическую двоичную последовательность Х_>, имеющую длину периода t и линейную сложность Л, укажите се минимальный многочлен т (к)
• а) t = 2, Л = 2;
• б)? = 3, Л = 2;
• в) t- 5, Л = 3.
• 8.28. Постройте линейный профиль двоичной последовательности:
  • а) {0, 1,0, 1,1,1,0,1};
  • б) {0, 0, 0, 0, 0,1, 1,1, 1,1, 0, 0, 0, 0, 0, 1, 1,1, 1, 1}.
• 8.29. Как разместить п нулей и т единиц, чтобы слово длины п + т имело наибольшую (наименьшую) линейную сложность:
  • а) п = 5, т=10;
  • б) п= 10, т= 14;
  • в) п=, т = 16?

Укажите наибольшее и наименьшее значения линейной сложности.

• 8.30. <1 линейная сложность Л суммы ЛРПшах-гс и ЛРПтах-w (над полем Р) с характеристическими многочленами Р (к) и F₂(k) равна п + т при (F_t(X), F₂(X)) = 1. Определите, А при F_x(k) = F₂() и п = т.
• 8.31. Пусть Х_> = {jtJ есть двоичная ЛРПтах-и и Y_> получена из Х_> с помощью б.ф./от г переменных, где r< п: Y_> = {f (x_it x_i+x,…, x_i+r__{)}_} i = 1, 2,… Сколько единиц имеется на периоде последовательности У_>, если вес функции /равен т?
• 8.32. Период последовательности Xнад 6 Т (31) имеет длину 31 и состоит из четырех «4», четырех «11», восьми «8» и пятнадцати «0». Верно ли, что А (Х_>) = 31?
• 8.33. Как соотносятся линейные сложности последовательности {я*₀, длины / над Р^т и периодической последовательности У_>, период которой совпадает с (х₀,…, *м),/> 1?
• 8.34. Пусть = {.г,} — последовательность, генерируемая «счетчиком» по модулю 2^й, и Y_>= {г/ф где г/_у есть двоичное представление числа x_if /=1,2,… Докажите, что для j-й координатной последовательности Yj^, je {1,…, п}, верны утверждения:
  • а) длина периода tj равна 2J;
  • б) минимальный многочлен ш_;(Х) равен (А ® 1)^г, где г= 2Н + 1.
• 8.35. Составьте список многочленов, минимальных хотя бы для одной чисто периодической двоичной последовательности с длиной периода 6.
• 8.36. Пусть Х_> — двоичная компенсированная последовательность с длиной периода 2″, У— ее циклический сдвиг на d битов. Докажите, что при некотором ненулевом d линейная сложность суммы последовательностей X+ Y_> меньше 2^й-1.