Последовательность де Брюина
Материал из Википедии — свободной энциклопедии
Цикл де Брюина или последовательность де Брюина B(k,n), любая подпоследовательность длины n встречается один раз.
циклическая последовательность де Брюина с периодом 16
s = 0000100110101111
Условно открыты де Брюином (de Bruijn) в 1946, но реально Flye-Sainte Marie ещё в 1894.
число циклических последовательностей де Брюина с периодом n в алфавите из k символов
пример для k=2, n=2,4,8,…
01 0011 00010111
существуют для любых n,k.
На основе этих циклов, задаваемых линейными рекуррентными формулами, построен CRC32 (с примитивным полиномом EDB88320)