Инициализация псевдослучайной последовательности, как это сделать? Опции

[ARV]

Отправная точка: миниатюрное устройство, где каждый новый компонент - лишний. устройство формирует ряд "случайных" сигналов, используя rand(). в сущности, алгоритм генерации ПСПЧ не принципиален. но есть большая проблема: два одинаковых устройства, включенные одновременно, генерируют абсолютно одинаковые "случайные" последовательности, что очень плохо. более того, после подачи питания устройство всегда стартует с одного и того же "места", что тоже очень плохо.

есть, конечно, функция srand(), которая могла бы помочь, но для нужного результата эту функцию нужно передать случайное число... круг замкнулся.

вопрос знатокам: посоветуйте, какими простыми и дешевыми средствами реализовать получение хотя бы одного-единственного, но на самом деле случайного числа в программе?

сразу ограничу круг советов: надежда на то, что после включения питания ячейки ОЗУ содержат случайные данные, не срабатывает, в подавляющем большинстве у одного и того же контроллера при более-менее одинаковых условиях содержимое ОЗУ после подачи питания так же более-менее одинаковое, вариации крайне недостаточные для того, чтобы считать их действительно случайными - проверено на некотором количестве atmega32.

[ataradov]

У Атмела есть аппнот на эту тему, номер не помню правда.

В качестве источинков случайных событий в частности там предлагались: АЦП с висящим в воздухе выводом, время записи ячейки EEPROM и много чего еще.

[ARV]

пока что не нашел такого апноута... с АЦП я пробовал, но что-то не очень хорошо вышло... вроде поначалу показалось есть случайность, а потом она куда-то пропала... правда, я использовал "веру" в то, что младший бит АЦП шумит, и поэтому мерял 8 раз небольшой уровень и младший бит результата задвигал в байт... а вот время записи EEPROM - оно же может зависеть от питания, температуры, частоты встроенного генератора, но для одинаковых условий будет неизменным, как мне кажется... 2 девайса могут получиться с разными последовательностями, но каждое будет всегда стартавать однотипно...

[314]

Висящий в воздухе вывод АЦП лихо реагирует на влажность платы, можно просто дохнуть на это место платы и показания здорово меняются. Только по-моему это больше проблема, чем решение.

[ARV]

в том-то и дело, что висящий вход лихо на все реагирует... например, зарядится от статики и держит заряд минутами... т.е. будет выдавать одно и то же число... девайс будет корпусирован, т.е. сильно "дышать" на него никто не будет, условия вокруг МК будут более-менее стабильные, т.е. очень медленно меняющиеся... а включение выключение может происходить и несколько раз в минуту...

[Petka]

есть, конечно, функция srand(), которая могла бы помочь, но для нужного результата эту функцию нужно передать случайное число... круг замкнулся.

вопрос знатокам: посоветуйте, какими простыми и дешевыми средствами реализовать получение хотя бы одного-единственного, но на самом деле случайного числа в программе?

На самом деле "действительно случайное" число не нужно. Нужно всего-лишь навсего при каждом запуске в srand подсовывать ДРУГОЕ число. Получить его достаточно просто. При каждом запуске инкрементируйте какую-нибудь ячейку EEPROM и данным значением инициализируйте srand.

[ARV]

На самом деле "действительно случайное" число не нужно. Нужно всего-лишь навсего при каждом запуске в srand подсовывать ДРУГОЕ число. Получить его достаточно просто. При каждом запуске инкрементируйте какую-нибудь ячейку EEPROM и данным значением инициализируйте srand.

да, действительно спасибо, что натолкнули на эту мысль, хотя я уже получил аналогичный совет на телесиськах http://530.ru/wwwboards/mcontrol/2979/messages/1182899.shtml

если вдруг кому потребуется действительно случайный генератор чисел, то я нашел целый трактат по этой теме (может, это его посчитали за апноут атмеля?) http://www.avrfreaks.net/index.php?name=PN...pic&t=59417

[ataradov]

но для одинаковых условий будет неизменным, как мне кажется...

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

[DpInRock]

Согласен с предыдущим оратором.
Хуже того, набор 1 2 3 4 5 6.... тоже является частным случаем случайной последовательности. Которая может быть вполне (если числа действительно случайные).
Посему во многих случаях более полезной будет просто последовательность 1 2 3 4... . Её плюс состоит в том, что числа не повторяются с максимальным интервалом.
И при наличии епром реализуются просто.

[rx3apf]

вопрос знатокам: посоветуйте, какими простыми и дешевыми средствами реализовать получение хотя бы одного-единственного, но на самом деле случайного числа в программе?

Уникального серийника нет ? Ну, еще можно воспользоваться тем, что WDT тактируется от RC-генератора, и при основном тактировании от кварца можно измерить время срабатывания WDT и плясать от него. Думаю, достаточно случайное значение, при высокой дискретизации счета.

[ARV]

Уникального серийника нет ? Ну, еще можно воспользоваться тем, что WDT тактируется от RC-генератора, и при основном тактировании от кварца можно измерить время срабатывания WDT и плясать от него. Думаю, достаточно случайное значение, при высокой дискретизации счета.

да, этот метод рассматривался в числе прочих в вышеупомянутом мною трактате спасибо, я считаю, что на данном этапе я свою проблему решил.

P.S. на счет 1,2,3,4,5 и т.д. - я вообще молчу (звездавшоке)

[domowoj]

Если говорить о псевдослучвайной последовательности, то можно прогрмно реализовать
один из вариантов следующей схемы сдвигового регистра с ОС
http://www.qrz.ru/schemes/contribute/secur...generator1.shtm
Или вот так
http://algolist.manual.ru/maths/generator/

Или вот генератор случ. чисел
http://vx.netlux.org/lib/vsl04.html

Сообщение отредактировал domowoj - Mar 11 2011, 15:30

[rx3apf]

Если говорить о псевдослучвайной последовательности, то можно прогрмно реализовать
.....
Или вот генератор случ. чисел

Что толку с генератора ПСЕВДОслучайной последовательности, если нет возможности рандомизировать "затравку" ? У всех устройств при равном числе обращений к этому генератору "случайное" число будет строго одинаковым...

[domowoj]

Тогда усилить шумы стабилитрона
и оцифровать

[zombi]

Отправная точка: миниатюрное устройство, где каждый новый компонент - лишний. устройство формирует ряд "случайных" сигналов, используя rand(). в сущности, алгоритм генерации ПСПЧ не принципиален. но есть большая проблема: два одинаковых устройства, включенные одновременно

Интересно как это Вам удается их одновременно включать?

[muravei]

Тогда усилить шумы стабилитрона
и оцифровать

А если попробовать стабилитрон на уровне опоры компаратора?
Можно тогда обойтись и без ПСП.

[SKov]

А если попробовать стабилитрон на уровне опоры компаратора?
Можно тогда обойтись и без ПСП.

А может, обычный "аналоговый генератор" типа трехточки на одном транзисторе?
И спрашивать напряжение через АЦП?

[demiurg_spb]

Уважайте поиск! :-)
В ветке AVR по слову RAND куча всего уже понаписано, в том числе и по теме топикстартера:

http://electronix.ru/forum/index.php?act=S...ighlite=%2BRAND

А ведь ещё есть и ветка в помощь начинающему...

[forever_student]

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

В такой же ситуации при включении запускал таймер (на МАХ возможной частоте). В момент отпускания кнопки включения таймер считывал. Все.

[HALFer]

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

но если все же требуется "случайный старт", то на вход счетчика завести копку включения питания девайса. эту же кнопку сделать источником внешнего прерывания для вывода контроллера из сна. сам контроллер будет спать вместо полного обесточивания.
укладывать спать нужно для того, чтобы не тратить драгоценное время дребезга контакта на запуск генератора, на инициализацию программы и т д (дребезжание может и закончиться прежде чем счетчик начнет считать). кнопка без фиксации. засыпать после отработки цикла автоматически. для двух парных устройств - двойная кнопка.

LC-контур СЧ-диапазона на вход ADC тоже даст шум все зависит от особенностей конструкции и эксплуатации. мало данных по прибору. чем он включается, одновременно ли два прибора включаются (т е присутствует ли тут фактор человека). больше инфы - больше простора для фантазии

[ARV]

не смотря на то, что лично для меня тема исчерпана, обсуждение продолжается
поясню:
1. одновременно - не значит на самом деле одновременно, т.е. в абсолютно один и тот же момент. просто человек включает два девайса и они показывают ему одинаковое состояние. человек снова "передергивает" питание - и снова оба одно и то же... причем то же самое, что и в прошлый раз. именно от этого нужно было уйти.
2. самое простое решение было высказано: хранить в EEPROM число включений и использовать его для srand() - инициализации генератора ПСПЧ. это самое простое решение. не смотря на то, что два впервые изготовленных девайса будут вести себя точно так же, как описано в п.1, но стоит на "5 минут" унести один девайс в другую комнату и там его повключать, то вернувшись обратно синхронности уже не добиться. и угадать, на сколько включений произошло рассогласование внутренних счетчиков тоже будет сложно.
3. улучшение варианта п.3 элементрано: на стадии прошивки задается "случайное" первичное значение счетчика включений - это несложно сделать при помощи программатора с возможностью редактирования дампа EEPROM.
4. варианты внешнего усложенения схемы (генераторы шума на стабилитронах, транзисторах и т.п.) дадут лучшую случайность, но, во-первых, истинная случайность не требуется, а во-вторых, это усложняет схему, т.е. удорожает ее. кстати, эти варианты изначально были известны ... и отброшены.
5. кнопок, дребезг которых можно было бы использовать, или останавливать по ним таймер и т.п., в девайсе не предусмотрено

[=AK=]

1. одновременно - не значит на самом деле одновременно

У меня была аналогичная проблема: как по радиоканалу назначить уникальные серийные номера нескольким "свежезапрограммированным" устройствам? Понятно, что программы у них поначалу совершенно одинаковые, и откликаются на вызов одинаково, поэтому вроде бы невозможно их различить.

Чтобы устройства откликались по-разному, я назначаю им временные серийные номера. Причем этот серийный номер назначается не в момент включения, а в момент получения первого (широковещательного) вызова по радиоканалу. А в качестве случайного числа используется значение счетчика локального времени, который считает время от момента включения питания. Соответственно, каждое устройство в момент прихода вызова имеет свое собственное уникальное локальное время, отличное от остальных.

[rx3apf]

5. кнопок, дребезг которых можно было бы использовать, или останавливать по ним таймер и т.п., в девайсе не предусмотрено

Еще варианты - измерение напряжения встроенного опорного источника (отличается от экземпляра к экземпляру даже в одной партии кристаллов, хотя абсолютное число "вариантов" не так уж и велико). И измерение частоты встроенного калиброванного RC-генератора (если тактирование от внешнего кварца). Как вариант - измерение времени записи в ячейку(и) EEPROM данных.

3. улучшение варианта п.3 элементрано: на стадии прошивки задается "случайное" первичное значение счетчика включений - это несложно сделать при помощи программатора с возможностью редактирования дампа EEPROM.

Тогда уж правильнее "сериализация" (инкремент серийного номера) (avreal, например, это обеспечивает). А от серийника считать "затравку".

[demiurg_spb]

Еще варианты - измерение напряжения встроенного опорного источника

А относительно чего измерять? Внешний опорник ставить?
Предлагаю считать количество нейтрино, прошедших сквозь прибор, за какой-то интервал времени:-)

Кстати, что там с регистром OSCAL он вообще отличается среди образцов одной партии? Если да то ещё немного случайности добавит.

[rx3apf]

А относительно чего измерять? Внешний опорник ставить?

Встроенный опорник относительно питания.

Кстати, что там с регистром OSCAL он вообще отличается среди образцов одной партии? Если да то ещё немного случайности добавит.

Тоже варьируется.

[ARV]

снова у меня проблема rand() вместе с srand() не втискиваются в память микроконтроллера. уже несколько дней ищу более-менее адекватную замену - и не могу найти

задача очень проста: получить псевдослучайное число в пределах от 1 до 7. все мои попытки сделать генератор ПСПЧ с заданными параметрами дают чрезвычайно короткий цикл - буквально пару десятков чисел, после чего последовательность повторяется

я делаю на "регистре сдвига с XOR-обратными связями по простому полиному", после чего маскирую 3 младших бита, и если результат равен 0 - повторяю.

уже сделал открытие, что avr-gcc может с легкостью выбросить volatile register переменные из кода, если моя функция случайного числа объявлена как static... но вот качественной последовательности (мне хватило бы длины цикла хотя бы больше сотни) получить не могу то ли полиномы у меня не те, то ли что-то не то в алгоритме...

посодействуйте, пожалуйста...

[defunct]

посодействуйте, пожалуйста...

попробуйте такое, рожал для быстрого шифрования страниц флеш:

Код

#define RND_INITIALIZER (777)

typedef union tagU32xU16
{
    U32 full;
    struct
    {
        U16 low;
        U16 high;
    } words;
} TU32xU16;


U16 cpr_rand16( U16 num)
{
    TU32xU16 t32;
    U16 XorCode = 0xF7B2;

    num += RND_INITIALIZER;

    t32.full = (U32)num * XorCode;
    XorCode ^= t32.words.high;
    t32.full = (U32)t32.words.low * XorCode >> 1;

    return t32.words.low;
}

Input'ом для функции может быть любая последовательность неповторяющихся чисел, например 0, 1, 2, 3 .... 64K.
RND_INITIALIZER задает начальный сдвиг выходной последовательности.

Вот что имеем на выходе для входной последовательности 0, 1, 2, ..255:

Код

rnd initializer 777,  input sequence 0, 1, 2, ... 255:
007d e374 dbb9 6700 5f45 92b4 69c1 1640 ed4d bd14 72e9 40a0 f675 6294 f731 e620
7abd 1cf4 28b9 d140 dd05 1a34 04c1 ce80 b90d 1d7a 623e a76c 1ed8 6406 4522 6918
01bc 25b2 94c6 1c64 5b20 e2be 816a e7d0 47c4 ae2a e92e 2e5c af88 f4b6 cc12 f008
926c b662 69b6 f154 39d0 c16e 565a bcc0 9dbf 93e8 7627 12a8 d3af eb10 ac17 e4f0
84bf bd58 5d27 44d8 484f 2700 2a77 20e0 031f 0308 e547 7808 390f 5a30 1b37 4a50
ea1f 2c78 cc47 7638 662f 3b20 2b17 9660 dac6 255e a7fc f294 d352 fcb2 a088 c9e8
46fe 4f26 1434 1c5c 692a d4fa 4020 abf0 e696 312e bd8c 0824 df22 0882 b618 df78
52ce 5af6 29c4 31ec c2fa 2efc 16a5 1800 ffa9 9bcc 623d 84d0 4b41 83bc 28f5 6cc0
11f9 e6cc 6acd cfd0 53d1 193c 00e5 0c00 f3a9 860c 4c7d 78d0 3f41 6dfc 1335 60c0
05f9 d10c 550d c3d0 48bc 4896 dede 55e0 0ab0 81b2 8912 dedc b4e4 0aae ae66 e2f8
da38 0eca 4eda 6234 7aac 8e06 df8e 5690 1520 8c22 89c2 df8c bf54 151e af16 e3a8
e4a8 193a 4f8a 6488 f3bb a268 319b b780 aa5b ff20 f1fb 5118 22bb 98b8 6a5b 65d0
163b ad70 5ddb f5a8 84db 3d48 cc7b 96a0 897b e800 dadb 3038 01db 8198 533b 44f0
f55b 9650 4918 755c 6ea6 79b2 c854 d360 2e62 8996 6ad0 c604 695e a35a a5cc dfc8
1f7a 383e 5be8 74ac 50b6 4842 8d24 84b0 b3f2 0f26 fa20 5554 eeee 28ea 351c 6f18
a50a c0e4 5581 0f60 a3fd e184 54e9 3000 a365 0704 de11 5f40 364d 3164 e739 89a0

[forever_student]

...посодействуйте, пожалуйста...

У меня для однобайтного псевдослучайного сделано так: Х(n+1)=5*X(n)+5. Х(n) - unsigned char

[Warlockwolf]

Код

u32 iran;
u8 Radom(){
iran=(iran*(u32)4096+(u32)150889)%(u32)714025;
return iran/0xfff;
};

iran -только надо чем то забить первый раз. а потом можно в еппром сохранять.

[ARV]

У меня для однобайтного псевдослучайного сделано так: Х(n+1)=5*X(n)+5. Х(n) - unsigned char

не понял - это что за операция? (выделил)

спасибо всем откликнувшимся! но видимо я недостаточно четко изложил нюансы... у меня attiny13, поэтому оперирование 32-битными числами, да еще с умножением и делением - это заведомо неподходящий вариант - так работает стандартный rand() из avr-libc, и при этом в 1К кода моя программа не влезает. мне нужен вариант, требующий не более 200 байт кода.

[rx3apf]

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

У меня реализация xorshift (32-битный вариант) - 40 слов (80 байтов). asm, и, для экономии, без сохранения регистров (ускоренный вариант и с сохранением - вдвое толще). Нужно ? Избыточно, конечно (для озвученных требований), и не очень эффективная реализация (поскольку алгоритм плохо подходит для 8-битных контроллеров, и не умеющих сдвигать иначе как на один бит),зато просто исключительно хорошее распределение.

Сообщение отредактировал rx3apf - Mar 20 2011, 12:32

[ARV]

У меня реализация xorshift (32-битный вариант) - 40 слов (80 байтов). asm, и, для экономии, без сохранения регистров (ускоренный вариант и с сохранением - вдвое толще). Нужно ? Избыточно, конечно (для озвученных требований), и не очень эффективная реализация (поскольку алгоритм плохо подходит для 8-битных контроллеров, и не умеющих сдвигать иначе как на один бит),зато просто исключительно хорошее распределение.

по идее xor-shift довольно прост, все дело в "полиноме", не так ли? у меня сейчас так:

Код

static uint16_t prev_rand;
uint8_t rand(void){
   if(prev_rand & 1)
      prev_rand = (prev_rand >> 1) ^ POLYNOM;
   else
      prev_rand >>= 1;
   return prev_rand & 7; // мне нужно число от 0 до 7 (точнее, 0 не нужно, но это мелочи)
}

думаю, ваш вариант аналогичный, разве что не 16, а 32 бита "регистр". все упирается именно в POLYNOM... который я так и не смог подобрать...

или я что-то не так делаю?

так как я по сути использую только младшие 3 бита, меня интересует распределение именно этой части - все мои попытки дают крайне короткую последовательнсоть ИМЕННО этих битов... скажите мне свой полином - я протестирую, может. ваш вариант будет лучше...

[rx3apf]

скажите мне свой полином - я протестирую, может. ваш вариант будет лучше...

xorshift реализуется не так, как большинство простых алгоритмов реализации ПСП (обратная связь по нескольким "отводам" из регистра сдвига - полиномы для которых можно посмотреть, например, у Хоровица и Хилла), там сдвиг всего содержимого и xor всего этого добра.

CODE

;----------------------------------------------------------------------
; Генератор псевдослучайных чисел (алгоритм XorShift32)
; Используются и не сохраняются регистры r2...r9, Z и temp
;----------------------------------------------------------------------

XorShift32:
ldi ZH,high(Rnd32)
ldi ZL,low(Rnd32)
ldd r5,Z+0
ldd r4,Z+1
ldd r3,Z+2
ldd r2,Z+3
movw r9:r8,r5:r4
movw r7:r6,r3:r2
ldi temp,5
XS32_1:
lsl r6
rol r7
rol r8
dec temp
brne XS32_1
eor r5,r8
eor r4,r7
eor r3,r6

movw r7:r6,r5:r4 ; сдвиг вправо на 16
lsr r7
ror r6 ; и еще на 1
eor r3,r7
eor r2,r6

movw r9:r8,r5:r4
movw r7:r6,r3:r2 ; копия регистра
ldi temp,5
XS32_2:
lsl r6
rol r7
rol r8
rol r9
dec temp
brne XS32_2

eor r5,r9
eor r4,r8
eor r3,r7
eor r2,r6

std Z+0,r5
std Z+1,r4
std Z+2,r3
std Z+3,r2
ret

[defunct]

требующий не более 200 байт кода.

Тогда как насчет таблички. Если вам нужны только 3-х битные числа, то в 200 байт можно засунить последовательность из ~500 чисел. ну а затем просто последовательно их читать.

[ARV]

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

моя проблема была в том, что я не учел, что вышеприведенный мной код генерирует при каждом обращении ТОЛЬКО 1 СЛУЧАЙНЫЙ БИТ, а я использовал сразу три бита из "регистра"... сейчас я улучшил генератор ПСП, как мне кажется, до приемлемого уровня случайности, путем заполнения выходного числа тремя случайными битами.

в очередной раз проблема, похоже, решена раньше, например, всегда после числа 7 можно было ожидать число 3, причем однозначно, сейчас же с более менее равной вероятностью приходят другие числа.

[Метценгерштейн]

а не лучше ли использовать алгоритм ПСП, например ГОСТ, просто записывать последнее значение во флеш, и при запуске снова контроллера, брать последнее значение от туда, а не заново начинать считать?