Анализ псевдослучайных последовательностей по критерию энтропия цепей Маркова

25 Пример 2.6. Построение последовательности де Брейна по последовательности ПСП 1 1 . Последовательности (2.6) на основе (2.14) поставим в соот - ветствие ПСП де Брейна вида : (1111, 0111, 1011, 0101, 1010, 1101, 0110, 0011, 1001, 0100, 0010, 0001, 0000, 1000, 1100, 1110). Последовательности , получаемые на основе (2.14), являют - ся нелинейными , обозначим их как ПСП 3 2 . По структурным и ста - тистическим свойствам ПСП 3 2 отличаются от ПСП 1 1 [3,7]. От - метим следующие структурные особенности последовательности де Брейна [33]. Определение 2.1. Если n – положительное целое число и 2 n N = , то цикл 1 a , 2 a , …, N a , составленный из нулей и единиц , называет - ся полным циклом , при этом подпоследовательности i a , 1 i a + , …, 1 i n a + − , i = 1, N , состоят из всех возможных 2 n N = упорядоченных по c ледова - тельностей b 1 … b n из нулей и единиц . При n = 1, 2, 3 имеются следующие полные циклы : n = 1: 0, 1. n = 2: 00, 10, 11, 01 n = 3: 011, 101, 010, 001, 000, 100, 110, 111. 011, 001, 000, 100, 010, 101, 110, 111. При n = 4 существует точно 16 полных циклов . Существова - ние полных циклов длины 2 n N = и их число определяет теорема , принадлежащая де Брейну . По этой причине полные циклы назы - ваются также последовательностями де Брейна . Согласно работе [33] для ПСП де Брейна , представленных при использовании двоичных чисел , справедлива : (2.15)