Эту аппаратно реализованную схему часто строят в виде программы для микроконтроллера, поскольку вычислительные ресурсы современных процессоров позволяют добиться приемлемых результатов по быстродействию и качеству генерируемой последовательности псевдослучайных чисел.

От того, какие будут выбраны разряды для обратной связи (feedback tap position), зависит качество работы генератора LFSR. В таблице ниже показаны рекомендованные номера этих разрядов для генератора LFSR с разрядностью от 2 до 32.

число бит длина цикла разряды обратной связи (tap)
2 3* [0,1]
3 7* [0,2]
4 15 [0,3]
5 31* [1,4]
6 63 [0,5]
7 127* [0,6]
8 255 [1,2,3,7]
9 511 [3,8]
10 1023 [2,9]
11 2047 [1,10]
12 4095 [0,3,5,11]
13 8191* [0,2,3,12]
14 16,383 [0,2,4,13]
15 32,767 [0,14]
16 65,535 [1,2,4,15]
17 131,071* [2,16]
18 262,143 [6,17]
19 524,287* [0,1,4,18]
20 1,048,575 [2,19]
21 2,097,151 [1,20]
22 4,194,303 [0,21]
23 8,388,607 [4,22]
24 16,777,215 [0,2,3,23]
25 33,554,431 [7,24]
26 67,108,863 [0,1,5,25]
27 134,217,727 [0,1,4,26]
28 268,435,455 [2,27]
29 536,870,911 [1,28]
30 1,073,741,823 [0,3,5,29]
31 2,147,483,647* [2,30]
32 4,294,967,295 [1,5,6,31]
* Звездочкой помечены последовательности, длина которых - простое число. Выделенные зеленым строки относятся к рассматриваемым в данной статье примерам кода.

Имейте в виду, что есть несколько вариантов выбора для feedback tap position, чтобы произвести максимальные последовательности генерируемых псевдослучайных данных.

Имеется одна общая проблема с использованием LFSR: если все разряды регистра станут равны 0, то регистр перестанет менять свое значение и навсегда останется нулевым. При этом генерации случайных чисел не будет, все выходные байты будут нулевые. Так происходит потому, что операция XOR от всех '0' также будет равна '0', и при этом обратная связь через XOR не сможет произвести '1', чтобы продолжалось генерирование псевдослучайных чисел. Чтобы предотвратить такое событие, регистр сдвига предварительно перед началом генерации чисел должен быть обязательно загружен ненулевым значением старта (его называют значением seed, seed value). Это значение seed может быть любым числом, если оно ненулевое. Последовательность чисел, которую выдает генератор LFSR, напрямую зависит от значения seed. После каждой загрузки seed Вы всегда получите одну и ту же последовательность псевдослучайных чисел снова и снова, пока не загрузите в качестве seed другое значение. С другим значением seed последовательность генерируемых псевдослучайных чисел поменяется.

Откуда можно взять это начальное значение? Все зависит от Вашего конкретного приложения. Например, если в системе есть RTC (real-time clock, часы реального времени), то хорошее значение seed можно получить из текущего времени. Вы можете прочитать текущее время и/или дату, замаскировать порцию этих данных, и полученный результат использовать как seed. Другой пример - температура. Если Ваша система может прочитать температуру (подразумевается, что температура непостоянна), то это значение также может использоваться как seed. Значение seed также можно получить из текстового пароля, складывая по определенному закону его символы. Другой источник seed - аналого-цифровой преобразователь (ADC), который встроен во многие микроконтроллеры (к примеру, многоканальный ADC имеется почти во всех моделях AVR). С помощью ADC можно измерить напряжение питания, некоторое положение какого-нибудь сенсора, или даже усиленное напряжение шума Джонсона (тепловой шум) на диоде Зенера (стабилитрон). Получение из шума случайных чисел - общая практика в прикладной криптографии.

Однако иногда необходимо использовать в качестве seed строго определенное число, чтобы иметь возможность получить заранее спрогнозированную, однозначно воспроизводимую последовательность псевдослучайных данных. Например, это может потребоваться для получения ключа в XOR-шифровании [3].

[25-разрядный LFSR на ассемблере MCS51]

В приведенном ниже примере подпрограммы на языке ассемблера микроконтроллера MAX765x (система команд 8051) используется 25-битная последовательность, которая повторяется после вызова подпрограммы 33 миллиона раз. Даже если Вы не можете каждый раз сгенерировать уникальное значение seed, такая длина псевдослучайной последовательности подходит для большинства приложений, и "случайность" данных оказывается более чем достаточной.

Подпрограмма использует 4 8-битных ячейки памяти (байты данных), помеченных как RN1..RN4. Три младшие из них, RB1..RN3, используются для 24 бит, и старший 25-й бит размещается в RN4 (в ячейках RN1..RN4 хранится регистр сдвига LFSR). Алгоритм использует обратные связи XOR (операция XOR выполняется командой XRL ассемблера) от разряда 25 (бит переноса) и разряда 7 (старший бит RN1). Поскольку все биты регистра сдвига LFSR регистра размещены просто в памяти RAM, Вы можете сформировать случайные числа размером до 32 бит. Например, 8-битное число RANNUM сохраняется в RAM на выходе из подпрограммы.

Чтобы получить действительную функцию нормального распределения (функция распределения Гаусса, Gaussian distribution function) случайных чисел, Вы можете произвести дополнительную обработку. Добавление некоторого произвольного количество последовательных выборок (например от 4) и взятие среднего числа от них создадут распределение Гаусса.

Один из примененных в алгоритме программных трюков - перестановка байт "byte swaps", для симулирования "сдвига на 8 тактов". Это экономит такты CPU, и ускоряет работу подпрограммы. например, если оригинальный порядок байт был ABCD, то после перестановки байт он будет BCDA. Это предотвращает выполнение в коде бесполезной работы по сдвигу старшего байта в следующий младший байт. Не имеет значения, вычисляются ли случайные числа каждый такт или каждые 8 тактов: оно по-прежнему остаются случайными. Так как полная длина LFSR - продукт 3 простых чисел (31, 601 и 1801), последовательность все еще не будет повторена после 33554431 вызовов подпрограммы! Конечно же, поскольку мы берем по 8 бит в нашем примере, то значения данных ограничены в диапазоне от 00H до 0FFH, и одни и те же значения будут возвращены множество раз.

Другой сохраняющий циклы трюк используется, когда выполняется XOR от 2 интересующих битов, все содержимое RN1 изменяется (см. пояснения в комментариях к коду).

1
....
52
;
; Подпрограмма RANDOM
;
; Генерирует случайные числа с использованием 25-битного регистра сдвига
; с обратными связями XOR от 7 и 25 разрядов (что определяет максимальную
; длину цикла).
;
; Для корректного применения подпрограммы учитывайте следующее:
; A) Некоторое ненулевое стартовое значение (SEED) обязательно должно
; быть предварительно загружено в RN1.
; B) Последовательность генерируемых данных будет повторена после
; приблизительно 33 миллиона вызова подпрограммы.
;
; Требуемые для работы ресурсы CPU:
;
; 6 ячеек памяти RAM для следующий целей.
;
; RANNUM: вычисленное случайное число
; RN1-RN1: эти ячейки формируют регистр сдвига
; TEMP1: регистр для временного хранения данных.
;
; Подпрограмма разрушает содержимое регистра A (аккумулятор) и бита
; переноса (CARRY BIT).;
;
RANDOM: MOV     A,RN4     ; Бит 25 помещается в CARRY
        RRC     A
        MOV     RN4,RN3
        MOV     RN3,RN2
        MOV     RN2,RN1   ; Сдвиг влево всех байт
        MOV     A,RN4     ; был RN3
        RRC     A         ; получение бита 25 (в бите CARRY) в старом RN3
        MOV     TEMP1,A   ; сохранение для последующего использования
        MOV     A,RN1
        RLC     A         ; бит 1 в позицию 7
        MOV     RN1,A     ; вернуть обратно
        MOV     A,TEMP1   ; восстановление A
        XRL     A,RN1     ; сумма по модулю 2 всех битов в RN1 и бита CARRY
        MOV     TEMP1,A   ; сохранение A
        MOV     A,RN4
        RRC     A
        MOV     RN4,A     ; сдвиг RN4
        MOV     A,RN3
        RRC     A
        MOV     RN3,A     ; сдвиг RN3
        MOV     A,RN2
        RRC     A
        MOV     RN2,A     ; сдвиг RN2
        MOV     A,TEMP1   ; восстановление A
        RLC     A
        MOV     RN1,A     ; xor перезаписывает все 8 бит, но это не имеет значения
        MOV     RANNUM,A  ; случайное число!!
        RET
[32-разрядный LFSR, код для микроконтроллера AVR]

Этот пример кода взят из [4]. Обратная связь XOR взята от разрядов 1, 5, 6, 31. Особенность алгоритма в том, что для инициализации LFSR нельзя использовать числа 0 и 1, иначе код будет выдавать только нулевые байты. По умолчанию регистр LFSR инициализирован константой 0xDEADBEEF.

  1
...
171
// Макрос для генерации 32-разрядной битовой маски.
#define _BVD( x ) ((uint32_t)( 1 ) << ( x ))

/*
* Подпрограмма генерации случайного байта с использованием 32-bit LFSR
*/
uint8_t random_byte_lfsr32(void)
{
    // регистр сдвига
    static uint32_t lfsr = 0xDEADBEEF;
   
    // сдвиг через 8 состояний для получения совершенно нового байта
    uint8_t state;

    for (state = 0; state <= 8; state++)
    {
        uint8_t new_bit = 0;

#ifndef OPTIMIZED_LFSR32

/*
* Оригинальный код на C.
* В среднем 61175.8 циклов на update_output_arcing() с опцией -O2, max частота
* обновления ~250 Гц, на частоте обновления 60 Гц CPU загружен ~24%.
*/
        // xor всех разрядов tap в один бит
        if ( lfsr & _BVD(1) )
            new_bit ^= 1;
        if ( lfsr & _BVD(5) )
            new_bit ^= 1;
        if ( lfsr & _BVD(6) )
            new_bit ^= 1;
        if ( lfsr & _BVD(31) )
            new_bit ^= 1;
        // сдвиг в новый бит
        lfsr >>= 1 ;
        lfsr |= (uint32_t)( new_bit ) << 31;

#else

/*
* Оптимизированная вручную версия на ассемблере.
* В среднем 13697.0 циклов на update_output_arcing() с опцией -O2, max частота
* обновления ~1200 Гц, на частоте обновления 60 Гц загрузка CPU ~5%.
*/

/*
* Безвозмездно предоставлен подробный комментарий по работе этой версии.
*
* Мотивацией для разработки был тот факт, что для 32-битных операций
* сдвига на C компилятор GCC AVR текущих версий генерирует поистине
* ужасающий машинный код, с различными сдвигами и ненужными промежуточными
* операциями хранения, в то время как все можно было просто реализовать
* 4 инструкциями, передающими данные через бит переноса (carry flag.
*
* Вычисление нового бита GCC реализовывал из кода C не настолько плохо,
* но все равно лучше это было сделать на ассемблере вручную.
*/
        asm volatile(
/*
* Операция xor над разрядами tap, результат помещается в new_bit.
*
* "sbrc a b" означает пропуск следующей инструкции, если очищен бит b
* в регистре a. Такой условный переход сделан для каждого разряда
* обратной связи (tap) в регистре lfsr. Если бит tap установлен,
* ветвление не выполняется, и далее выполняется команда "eor",
* которая переключает младший бит в new_bit операцией xor с константой
* 0x01 в регистре 4.
*/
            "sbrc %a0, 1"                                  "\n\t"
            "eor %1, %4"                                   "\n\t"
            "sbrc %a0, 5"                                  "\n\t"
            "eor %1, %4"                                   "\n\t"
            "sbrc %a0, 6"                                  "\n\t"
            "eor %1, %4"                                   "\n\t"
            "sbrc %d0, 7"                                  "\n\t"
            "eor %1, %4"                                   "\n\t"

/*
* Сдвиг вправо значения lfsr.
*
* Сдвиг начинается операции правого сдвига младшего байта слова,
* которая выдвигает младший бит слова в бит переноса, и при этом
* очищает старший бит. Затем используется "ror" над остальными
* тремя байтами, которые сдвигают данные вправо через бит переноса.
* Отличие сдвига "ror" от сдвига "lsr" в том, что "ror" вдвигает
* флаг переноса в старший бит вместо очистки старшего бита. При сдвиге
* первого байта не нужно вдвигать бит переноса, поэтому используется
* команда "lsr". Далее флаг переноса используется для передачи
* младшего бита предыдущего байта в старший бит текущего байта.
*/
            "lsr %d0"                                      "\n\t"
            "ror %c0"                                      "\n\t"
            "ror %b0"                                      "\n\t"
            "ror %a0"                                      "\n\t"

/*
* Вставка нового бита.
*
* Младший бит ячейки new_bit хранит значение нового бита. Если он очищен,
* то следующая инструкция пропускается. В следующей инструкции старший
* бит в старшем байте регистра устанавливается путем операции OR с
* константой 0x80.
*/
            "sbrc %1, 0"                                   "\n\t"
            "ori %d0, %5"                                  "\n\t"

/****************************************************/

/*
* Выходные регистры.
*
* 0 = lfsr
* 1 = new_bit
*
* Компилятору gcc будет указано, что lfsr имеет тип uint32_t, что
* размещение этой переменной в четырех (вероятно расположенных в памяти
* последовательно друг за другом) регистрах общего назначения (General
* Purpose Register, GPR), к которым происходит обращение по именам
* от %d0 до %a0.
*/
            : "=r" ( lfsr ), "=d" ( new_bit )

/*
* Входные регистры.
*
* 0 = lfsr
* 1 = new_bit
* 4 = регистр для константы
* 5 = непосредственная константа (immediate constant)
*
* 4 является константой, которая появляется в коде загруженной в регистр.
* 5 является непосредственной константой, она встроена прямо в код, это
* не регистр. 2 и 3 пропущены, потому что "входной" lfsr и new_bit должны
* быть там, но они повторно переназначены на 0 и 1, поскольку означают
* то же самое. Это обычное неочевидное поведение gcc.
*/
            : "0" ( lfsr ), "1" ( new_bit ), "d" ( 0x01 ),
                "m" ( 0x80 )
            );
#endif
    }
    // возврат младшего байта
    return (uint8_t)( lfsr & 0xFF );
}

/*
* Генерация случайного байта x так, что min < = x < = max.
*/
int8_t random_byte_in(int8_t min, int8_t max)
{
    // Получение случайного байта из младшего байта слова.
    uint16_t a_random_byte = random_byte_lfsr32();
    // Масштабирование.
    a_random_byte *= (max - min + 1);
    // Транслирование и возврат.
    return (int8_t)( (a_random_byte >> 8) + min );
}

/*
* Генерация случайного байта x так, что min < = x < = max
*/
uint8_t random_ubyte_in(uint8_t min, uint8_t max)
{
    // Получение случайного байта из младшего байта слова.
    uint16_t a_random_byte = random_byte_lfsr32();
    // Масштабирование.
    a_random_byte *= (max - min + 1);
    // Транслирование и возврат.
    return (uint8_t)( (a_random_byte >> 8) + min );
}
[Ссылки]

1. Pseudo-Random Number Generation Routine for the MAX765x Microprocessor site:maximintegrated.com.
2. Генератор псевдослучайных чисел site:wikipedia.org.
3. Бутлоадер USBasp с XOR-шифрованием.
4. Fast AVR 32-bit LFSR site:gist.github.com.

http://microsin.net/programming/AVR/lfs … rator.html
Ссылка на статью