Статистика
Время:
Зарегистрированных: 77605
Последним зарегистрирован: cedric69
Рекорд посещаемости: 12585
Групп пользователей: 4
 Группы:
[Admin] [Cоучастник] [Автор] [Модератор]
 Сейчас на сайте
 Всего: 245
 Гостей: 214
 Анонимных: 0
 Пользователей: 31
 Зарегистрированные:
Sergey393 UUV indman srg320 redzub gradient CAHEK Aries yaris shanta oleg3360 azgard2745 Terkins ifa amidi MishaSinica020909 алексус Andrew007 uryd Zlodey Ykrop feliks master90 megavoltus elektronshik manliz GEX13 куко FPV Geo78 ra3tmo
  Ответить Новая тема Новый опрос

> 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оучастник
Сообщений: 749
Пользователь №: 22294
Регистрация: 14-July 07
Место жительства: Спб



lsr sequ
brcc next
eor sequ,poly
next:

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

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

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


 




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