ГлавнаяАрхивПОСТРОЕНИЕ НОРМАЛЬНЫХ ПЕРИОДИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИЗ ЦИКЛИЧЕСКИ МИНИМАЛЬНЫХ ЧИСЕЛ

ПОСТРОЕНИЕ НОРМАЛЬНЫХ ПЕРИОДИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИЗ ЦИКЛИЧЕСКИ МИНИМАЛЬНЫХ ЧИСЕЛ | Прикладная дискретная математика. 2008. № 2(2).

Предлагается алгоритм с вычислительной сложностью 0(2n/п), позволяющий по задаваемым значениям параметра путем склеивания циклов, порожденных циклически минимальными числами, строить двоичные нормальные периодические последовательности порядка и так, что при разных значениях параметра с равной вероятностью строятся попарно неэквивалентные последовательности из множества большой мощности. В случае простого и указываются выражения для вычисления последней и размера параметра.
  • Title ПОСТРОЕНИЕ НОРМАЛЬНЫХ ПЕРИОДИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИЗ ЦИКЛИЧЕСКИ МИНИМАЛЬНЫХ ЧИСЕЛ
  • Headline ПОСТРОЕНИЕ НОРМАЛЬНЫХ ПЕРИОДИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИЗ ЦИКЛИЧЕСКИ МИНИМАЛЬНЫХ ЧИСЕЛ
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 2(2)
  • Date:
  • DOI
Ключевые слова
циклически минимальные числа , последовательности де Брейна , нормальные периодические последовательности
Авторы
Ссылки
Games R.A. A generalized recursive construction for de Bruijn sequences // IEEE Trans. Inform. Theory. 1983. V. IT-29. No. 6. P. 843-850.
Annexstein F.S. Generating De Bruijn Sequences: An Efficient Implementation// IEEE Trans. Computers. 1997. V. C-46. No. 2. P. 198-200.
Siu M.K., Tong P. Generation of some de Bruijn sequences //Discrete Mathematics. 1980. V. 31. P. 97 - 100.
Mykkeltveit J., Siu M.K., TongP. On the cycle structure of some nonlinear shift register sequence // Information and Control. 1979. V. 43. P. 202-215.
Радченко А.Н. Методы синтеза кодовых колец //Радиотехника и электроника. 1959. № 11. С. 1782 - 1795.
Lempel A. On a Homomorphism of the De Bruijn Graph and Its Applications to the Design of Feedback Shift Registers // IEEE Trans. Computers. 1970. V. C-19. No. 12. P. 1204 - 1209.
Агибалов Г.П. Нормальные рекуррентные последовательности//Вестник ТГУ. Приложение. 2007. № 23. С. 4 - 11.
ПОСТРОЕНИЕ НОРМАЛЬНЫХ ПЕРИОДИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИЗ ЦИКЛИЧЕСКИ МИНИМАЛЬНЫХ ЧИСЕЛ | Прикладная дискретная математика. 2008. № 2(2).
ПОСТРОЕНИЕ НОРМАЛЬНЫХ ПЕРИОДИЧЕСКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИЗ ЦИКЛИЧЕСКИ МИНИМАЛЬНЫХ ЧИСЕЛ | Прикладная дискретная математика. 2008. № 2(2).
Полнотекстовая версия