ФЭНДОМ


Linear feedback shift registers (LFSR, Линейный сдвиговый регистр с обратной связью) — один из методов генерации псевдослучайных чисел.

Сдвиговый регистр с обратной связью состоит из двух частей: сдвигового регистра и функции обратной связи. Сдвиговый регистр — последовательность битов. Длина сдвигового регистра — количество битов. Когда нужно извлечь бит, все биты сдвигового регистра сдвигаются вправо на одну позицию. Новый крайний слева бит определяется функцией остальных битов регистра. На выходе сдвигового регистра оказывается один, обычно младший значащий, бит. Период сдвигового регистра — длина получаемой последовательности до начала ее повторения. Для LFSR функция обратной связи представляет собой xor некоторых битов регистра (эти биты называются отводной последовательностью).

LFSR может находиться в 2^n-1 внутренних состояниях, где n - длина сдвигового регистра. Если сдвиговый регистр заполнен нулями, то такое состояние будет порождать на выходе только нули, так как в качестве функции обратной связи используется xor, поэтому такое состояние бесполезно. Теоретически LFSR может генерировать последовательность с длиной 2^n-1 бит, так как длина последовательности совпадает с количеством внутренних состояний. LFSR будет проходить все внутренние состояние (иметь максимальный период) только при определенных отводных последовательностях, если многочлен, образованный из отводной последовательности и константой 1 является примитивным по модулю 2. Степень многочлена - длина сдвигового регистра. Примитивный многочлен степени n - это неприводимый многочлен, который является делителем x^{2^n-1}+1, но не является делителем x^d+1 для всех d, делящих 2^n-1.

Например чтобы проверить будет ли LFSR с отводной последовательностью, состоящей из первого и четвертого битов, генерировать последовательность максимальной длины (15 для четырехбитного регистра) нужно проверить будет ли многочлен x^4+x+1 примитивным.de:Linear rückgekoppeltes Schieberegister en:Linear feedback shift register es:LFSR it:Registro a scorrimento a retroazione lineare ja:線形帰還シフトレジスタ ko:선형 되먹임 시프트 레지스터 nl:Linear Feedback Shift Register

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики