Многие наверно хотели сделать качественный генератор случайных чисел но задавались
вопросом "как?". Постараюсь описать вкратце как сделать генератор псевдослучайной битовой М-последовательности на мелкой логике или (самое главное) программно без особых аппаратных затрат. Именно М-последовательности (или как их еще называют - последовательности максимальной длины) могут быть использованы как часть системы шифрования или к примеру системы с расширением спектра или как часть генератора шума для глушилки и много где еще.
Что внутри? Генераторы М-последовательности делаются на двоичном регистре сдвига, определенные биты регистра выводятся и суммируются ( чтобы сделать это на мелкой логике - аппаратно применяют элементы XOR).Длина последовательности бит которую создает конкретный регистр напрямую зависит
от длины регистра и равна (2^m-1), ^ - значек возведения в степень, м- количество бит в регистре. После прохождения (2^m-1) бит последовательность начинается сначала, поэтому для систем связи на шпс используют последовательности с относительно маленьким регистром и тогда можно дождаться синхронизации тк период повторения последовательности мал, а для шифрования можно сделать регистр к примеру в 40 бит и уже мало кто сможет подобрать байтики за свою жизнь тк повторения ждать очень
долго.
Любая М-последовательность задается полиномом (выглядит как функция, улавливаете? ) следующего вида:
ссылкаXm это соответствующие биты регистра, коэффициенты gm равны либо 0 либо 1, фактически означают используется ли тот или иной бит регистра при вычислении следующего числа в последовательности, при аппаратной реализации их еще называют отводами (и к тем выходам регистра где gm равен 1 подключают элементы XOR). Покопавшись в интернете можно найти два варианта описания М-последовательности - Фибоначи и Галуа, вот они:
ссылкаФибоначи
ссылкаГалуа
Треугольниками обозначено умножение на коэффициенты, на практике в зависимости от коэффициента там либо есть соединение с последующей логикой либо его нету. Плюсы в кружках это операция XOR
(считается так 0+0=0, 0+1=1, 1+1=0). Вот примерно так:
ссылкаВидно что реализация фибоначи это практически схема псп генератора
собранного на мелкой логике, и не требует никакой переделки для реализации в железе, просто квадраты заменяются на последовательный сдвиговый регистр и делаются отводы на XOR элементах. Вот пример такой схемы 8битного генератора:
ссылкаОднако если попробовать реализовать такую схему на микроконтроллере то потребуется куча тактов на вычисление следующего числа в последовательность тк. необходимо проделать минимум три логические операции над содержимым регистра на каждый отвод. В такой ситуации очень кстати приходится схема Галуа которая как видно из картинки гораздо трудней делается на рассыпухе но зато реализуется в виде программы вообще одной строкой.
Итак у нас есть задача создать М-последовательность, не важно в каком варианте. Для этого требуется выбрать длину сдвигового регистра и коэффициенты полинома, те биты которые будут сделаны отводами. Надо
сказать что не всякое сочетание коэффициентов даст М-последовательность, таких сочетаний немного и они определены для каждой длины сдвигового регистра начиная с 3битного. Поэтому коэффициенты определяются
по таблице.Я сделал два архива - файл для последовательностей от 3 до 20 бит
1-20.zip 120кил и для остальных от 21 до 32 бит
21-32.zip 1,5мега. В архивах находятся текстовые файлики содержащие возможные коэффициенты для регистра определенной длины при реализации Галуа, к примеру 5stages.txt содержит такое:
5 stages, 2 taps: (1 set)
[5, 3]
5 stages, 4 taps: (2 sets)
[5, 4, 3, 2]
[5, 4, 3, 1]
это значит что на 5 битном регистре (5 stages) возможно сделать генератор с 2 отводами (2 taps) и с 4мя отводами (4 taps). В квадратных скобках указаны номера битов с которых делать отводы. Важно что в этих таблицах приведены коэффициенты для реализации Галуа и если надо получить такую же последовательность в аппаратном виде (те по схеме Фибоначи) коэффициенты перессчитываются таким образом - первый коэфф в скобках не трогается а остальные получаются вычитанием из длины регистра текущего значения, те 5 битный генератор с 4 отводами для Галуа [5, 4, 3, 2], для фибоначи тот же самый будет [5 , 5 - 4, 5 - 3, 5 - 2] или [5, 1, 2, 3].
Итак длина регистра и определяющий полином были выбраны,как все это сделать программно? Во 1х надо перевести полином в числовой вид, для нашего случая - [5, 4, 3, 2], берем цифры из скобок и считаем что это номера битов считая с 1 (те байт содержит такие биты в таком порядке 87654321), и считаем их битами выставлеными в единицу а остальные - нули, те в бинарном виде получим 00011110, биты номер 5,4,3,2 выставлены в один. Далее переводим это число в десятичную форму и запоминаем - 30, это наш полином. Наш генератор потребует хранения двух переменных - полинома и текущего значения регистра, на С это к примеру будет unsigned int polynom=30,rand=0;
Для получения в rand следующего числа из последовательности на С делаем так
if(rand&1){rand=(rand>>1)^polynom;} else {rand=(rand>>1);}
При повторении данной команды (2^m-1) раз , где м в нашем случае 5 и считая по формуле 2^5-1 = 32 - 1 = 31 .Те через 31 число таже последовательность начнется снова. Как сделать тоже самое на ассемблере АВР (мой любимый вариант):
lsr sequ
brcc next
eor sequ,poly
next:
<команды дальше>
sequ это регистр содержащий случайное число, poly это регистр содержащий наш полином, те к примеру 30 как в предыдущем примере. Понятно что данный пример будет работать только для генераторов короче 8 бит, для последовательностей большей длины надо брать больше регистров для текущего числа и полинома, так для 24 бит надо чтобы случайное число было из 3х байт и полином тоже будет 3хбайтный.
Примечание, сама последовательность битовая, чтобы получить именно одиночные биты надо на каждом шаге генерации числа просто брать первый бит и использовать.
Это сообщение отредактировал Neekeetos - Apr 5 2009, 03:59 PM Because they are afraid that there is more to reality than they have ever confronted
Главная страница -> VRTP -> Texнологии -> Микропроцессоры. -> AVR фирмы Atmel.
M-последовательности и с чем их едят, Как сгенерировать случайные числа на AVR
Новые книги
Статистика
Группы:
Сейчас на сайте
Всего: 562
Гостей: 552
Анонимных: 1
Пользователей: 9
Зарегистрированные:
