| abstract
| - Linear feedback shift registers (LFSR, Линейный сдвиговый регистр с обратной связью) — один из методов генерации псевдослучайных чисел. Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи. Сдвиговый регистр — последовательность битов. Длина сдвигового регистра — количество битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на одну позицию. Новый крайний слева бит определяется функцией остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Период сдвигового регистра — длина получаемой последовательности до начала ее повторения. Для LFSR функция обратной связи представляет собой xor некоторых битов регистра (эти биты называются отводной последовательностью). LFSR может находиться в внутренних состояниях, где n - длина сдвигового регистра. Если сдвиговый регистр заполнен нулями, то такое состояние будет порождать на выходе только нули, так как в качестве функции обратной связи используется xor, поэтому такое состояние бесполезно. Теоретически LFSR может генерировать последовательность с длиной бит, так как длина последовательности совпадает с количеством внутренних состояний. LFSR будет проходить все внутренние состояние (иметь максимальный период) только при определенных отводных последовательностях, если многочлен, образованный из отводной последовательности и константой 1 является примитивным по модулю 2. Степень многочлена - длина сдвигового регистра. Примитивный многочлен степени n - это неприводимый многочлен, который является делителем , но не является делителем для всех d, делящих . Например чтобы проверить будет ли LFSR с отводной последовательностью, состоящей из первого и четвертого битов, генерировать последовательность максимальной длины (15 для четырехбитного регистра) нужно проверить будет ли многочлен примитивным.
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)