Статистика
Время:
Зарегистрированных: 77048
Последним зарегистрирован: Gadjet
Рекорд посещаемости: 12585
Групп пользователей: 4
 Группы:
[Admin] [Cоучастник] [Автор] [Модератор]
 Сейчас на сайте
 Всего: 136
 Гостей: 132
 Анонимных: 0
 Пользователей: 4
 Зарегистрированные:
Virtuz bulat NIK-2101 sarzha
  Ответить Новая тема Новый опрос

> M-последовательности и с чем их едят, Как сгенерировать случайные числа на AVR
Neekeetos
Сообщение: # 151705   Sep 4 2008, 10:56 AM
Quote Post


Соучастник
***

Группа: Cоучастник
Сообщений: 482
Пользователь №: 20292
Регистрация: 23-April 07
Место жительства: Тула



Многие наверно хотели сделать качественный генератор случайных чисел но задавались
вопросом "как?". Постараюсь описать вкратце как сделать генератор псевдослучайной битовой М-последовательности на мелкой логике или (самое главное) программно без особых аппаратных затрат. Именно М-последовательности (или как их еще называют - последовательности максимальной длины) могут быть использованы как часть системы шифрования или к примеру системы с расширением спектра или как часть генератора шума для глушилки и много где еще.
Что внутри? Генераторы М-последовательности делаются на двоичном регистре сдвига, определенные биты регистра выводятся и суммируются ( чтобы сделать это на мелкой логике - аппаратно применяют элементы XOR).Длина последовательности бит которую создает конкретный регистр напрямую зависит
от длины регистра и равна (2^m-1), ^ - значек возведения в степень, м- количество бит в регистре. После прохождения (2^m-1) бит последовательность начинается сначала, поэтому для систем связи на шпс используют последовательности с относительно маленьким регистром и тогда можно дождаться синхронизации тк период повторения последовательности мал, а для шифрования можно сделать регистр к примеру в 40 бит и уже мало кто сможет подобрать байтики за свою жизнь тк повторения ждать очень
долго.
Любая М-последовательность задается полиномом (выглядит как функция, улавливаете? ) следующего вида:
image
ссылка
Xm это соответствующие биты регистра, коэффициенты gm равны либо 0 либо 1, фактически означают используется ли тот или иной бит регистра при вычислении следующего числа в последовательности, при аппаратной реализации их еще называют отводами (и к тем выходам регистра где gm равен 1 подключают элементы XOR). Покопавшись в интернете можно найти два варианта описания М-последовательности - Фибоначи и Галуа, вот они:
image
ссылка
Фибоначи
image
ссылка
Галуа
Треугольниками обозначено умножение на коэффициенты, на практике в зависимости от коэффициента там либо есть соединение с последующей логикой либо его нету. Плюсы в кружках это операция XOR
(считается так 0+0=0, 0+1=1, 1+1=0). Вот примерно так:
image
ссылка
Видно что реализация фибоначи это практически схема псп генератора
собранного на мелкой логике, и не требует никакой переделки для реализации в железе, просто квадраты заменяются на последовательный сдвиговый регистр и делаются отводы на XOR элементах. Вот пример такой схемы 8битного генератора:
image
ссылка
Однако если попробовать реализовать такую схему на микроконтроллере то потребуется куча тактов на вычисление следующего числа в последовательность тк. необходимо проделать минимум три логические операции над содержимым регистра на каждый отвод. В такой ситуации очень кстати приходится схема Галуа которая как видно из картинки гораздо трудней делается на рассыпухе но зато реализуется в виде программы вообще одной строкой.
Итак у нас есть задача создать М-последовательность, не важно в каком варианте. Для этого требуется выбрать длину сдвигового регистра и коэффициенты полинома, те биты которые будут сделаны отводами. Надо
сказать что не всякое сочетание коэффициентов даст М-последовательность, таких сочетаний немного и они определены для каждой длины сдвигового регистра начиная с 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
PMEmail PosterUsers WebsiteICQ
Top
majorPAE
Сообщение: # 155152   Sep 23 2008, 05:58 PM
Quote Post


Соучастник
*****

Группа: Cоучастник
Сообщений: 1144
Пользователь №: 17903
Регистрация: 16-February 07
Место жительства: Москва



Че то архив для 21-32 не открывается... Не обновишь его по ссылке, плз?


--------------------
"Очередной шаг вперед, как правило, результат хорошего пинка в зад!"(С)
PMEmail PosterICQ
Top
Neekeetos
Сообщение: # 155159   Sep 23 2008, 06:20 PM
Quote Post


Соучастник
***

Группа: Cоучастник
Сообщений: 482
Пользователь №: 20292
Регистрация: 23-April 07
Место жительства: Тула



QUOTE (majorPAE @ Sep 23 2008, 07:18 PM)
Че то архив для 21-32 не открывается... Не обновишь его по ссылке, плз?

Обновил, и правда файл недозалился smile.gif


--------------------
Because they are afraid that there is more to reality than they have ever confronted
PMEmail PosterUsers WebsiteICQ
Top
majorPAE
Сообщение: # 155161   Sep 23 2008, 06:26 PM
Quote Post


Соучастник
*****

Группа: Cоучастник
Сообщений: 1144
Пользователь №: 17903
Регистрация: 16-February 07
Место жительства: Москва



QUOTE (Neekeetos @ Sep 23 2008, 07:40 PM)
Обновил, и правда файл недозалился smile.gif

ОК! Огромный фенкс! За давностью лет многое забылось... Оченно пользительный материал! vo.gif drinks_cheers.gif


--------------------
"Очередной шаг вперед, как правило, результат хорошего пинка в зад!"(С)
PMEmail PosterICQ
Top
ysmat
Сообщение: # 212789   Jul 7 2009, 01:19 PM
Quote Post


Посетитель
**

Группа: Cоучастник
Сообщений: 259
Пользователь №: 620
Регистрация: 29-June 05




имееться такой crc полином
x4 + 1 = 21 (oct)
вопрос
соответствует ли он этой схеме


это модуль вычисления crc то есть
исходные последовательные данные 320 бит
проталкиваються через эту цепочку тригеров
чтобы получить на выходе 4 битный crc


Присоединённое изображение (Нажмите для увеличения)
Присоединённое изображение


--------------------
долой шифрование
PMICQ
Top
dimab
Сообщение: # 212792   Jul 7 2009, 01:49 PM
Quote Post


Соучастник
*****

Группа: Cоучастник
Сообщений: 1213
Пользователь №: 14289
Регистрация: 4-December 06




на википедии кусок кода лежит, работающий...

а лучше всего этого - стабилитрон и АЦП smile.gif
PMEmail Poster
Top
ведущий специалист
Сообщение: # 212940   Jul 8 2009, 12:01 PM
Quote Post


Соучастник
****

Группа: Cоучастник
Сообщений: 745
Пользователь №: 22294
Регистрация: 14-July 07
Место жительства: Спб



lsr sequ
brcc next
eor sequ,poly
next:

мне кажется повторяемость будет.Надо проверить.
А вообще XOR вещь хорошая, в давние времена спектрумисты ксорили свой код так что хрен угадаешь куда по ссылке после ксора пошел. Взломщики вешались. Выручал только отладчик в реальном времени, какие появились в нормальном виде только у скорпиона.

Почему так в начале написал. Побитовое исключающее или действует все равно по своему закону. Повторяемость будет всегда, тем более что сдвигаем на один бит в строгой последовательности, а полином - константа.
PMEmail PosterICQ
Top

Настройки темы Ответить Шустрый ответ Новая тема Новый опрос


 




    РадиоКОТ - популярно об электронике. Авторские схемы, новые разработки. Обучение по электронике, микроконтроллерам, ПЛИС. Форум  phreakerclub.com  banner DIPTRACE - САМЫЙ ЛУЧШИЙ ТАКСИРОВЩИК ПЕЧАТНЫХ ПЛАТ
Portal-X