Форум ОНИОО «Космопоиск»

Направления => Технический форум. (Приборный). => Тема начата: Starling от 04 сентября 2009 г., 15:19:56

Название: TG-RND7: Принцип генерации случайных чисел.
Отправлено: Starling от 04 сентября 2009 г., 15:19:56
TG-RND7: Принцип генерации случайных чисел.

Принцип работы прибора основан на подсчете длительности нажатия на клавишу с очень высокой точностью.

В зависимости от режима ГСЧ оперирует с первичными алфавитами разной длины.
Все режимы подобны друг другу и построены по одинаковой схеме.
Для примера будет подробно рассмотрен режим генерации случайных чисел 1 из 10 (0-9).

---
В промежутке между нажатиями на кнопку "А" выполнчются различные служебные подпрограммы: динамическая индикация (вывод на индикатор соответствующего символа), проверка нажатия на кнопки и т.д.

При нажатии на кнопку генерации случайного числа "А" программа запускает соответствующий блок генерации числа.

Тактовая частота работы микроконтроллера составляет 20 000 000 Гц (20МГц), что указано на задающем частоту кварцевом генераторе.
То есть, длительность такта составляет 0,00000005 секунды, или 5*10^-8 сек.

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

Таким образом, длительность 1 машинного такта (времени выполнения команды) составляет 0,0000002 секунды, или 2*10^-7 сек.

Ассемблерный код (MPASM) блока генерации 1 из 10.

Этот блок программа выполняет в том случае, если нажата кнопка "А" и выбра режим генерации 1 из 10 (0-9).
Переменная rand при этом уже равна нулю.

----------
; старт перебора
mDec_go
 incf   rand, f
 movlw  d'10'
 subwf   rand, w
 btfsc   STATUS, Z
 clrf   rand
 btfss   PORTB, 0
 goto   mDec_go
; конец перебора
----------

Для знающих ассемблер MPASM уже можно ничего не комментировать, для остальных - постараемся разобрать это настолько просто, насколько возможно.


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


Переведем ассемблерный код на русский:
----------
; старт перебора (комментарий, не является командой, игнорируется микроконтроллером).
Метка строки (не является командой, указывает на номер строки начала цикла в памяти микроконтроллера)

-  Увеличить переменную rand на 1
-  Поместить в аккумулятор десятичное значение "10"
-  Вычесть из аккумулятора значение переменной rand
-  Если результат выполнения предыдущей команды не равен нулю (то есть значение переменной rand НЕ равно 10), то пропустить следующую команду (два такта: сама команда, и переход на следующую команду или пропускание ее)
-  Обнулить переменную rand (пропускается если rand не равно 10)
-  Если на выводе контроллера логическая единца (кнопка не нажата), то пропустить следующую команду (два такта)
-  Перейти на метку, на начало цикла (пропускается, если кнопка "А" отпущена) (два такта)

; конец перебора (комментарий, не является командой, игнорируется микроконтроллером).
-------

Таким образом, основной цикл состоит из 6 команд длительностью в 1 такт, и команды перехода на метку начала цикла длительностью 2 такта.
То есть, длительность основного цикла составляет 8 тактов, или 8*2*10^-7=0,0000016 секунд, или 1,6*10^-6 сек, или 1,6 микросекунд.

В этом цикле программа перебирает значения от 0 до 9 до тех пор, пока не будет обнаружено, что кнопка отпущена.
На этом генерация случайного числа заканчивается, далее следуют служебные подпрограммы.

То есть, каждое значение "существует" всего  1,6 мкС, и чтобы "специально" сгенерировать  не случайное число, мы должны уложиться в промежуток времени 1,6/1000000 секунды.

Для приведенного случая (1 из 10) вся длительность полного перебора составляет 16 мкс секунд, или 1,6*10^-5 сек., или 1,6/100000 сек., за это время программа перебирает значения от 0 до 9 и начинает перебор снова.

По различным оценкам время, с которым обычный человек может нажимать кнопку "в такт", составляет порядка 1/10 сек, у специально тренированных людей отдельных профессий - не более 1/100 секунды.

То есть за 1/10 секунды, пока человек пытается "попасть в такт", программа переберет полный цикл 62500 раз и в момент отпускания кнопки остановится на каком-то случайном значении.

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

Несколько других факторов так же увеличивают "случайность", но рассмотрение их выходит за рамки данного материала и в целом не принципиально.


Фактически сгенерированное число/символ - это результат ОЧЕНЬ многих процессов.
Часть из которых строго детерминизирована (но далеко за пределами человеческих способностей по восприятию или управлению).
А часть - совершенно хаотична.
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: Aleеks от 04 сентября 2009 г., 19:05:58
Весьма остроумно .   
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: Олень от 04 сентября 2009 г., 21:56:50
Мне это напоминает(в детстве) процесс, подключения питания эл.реле переменным током - от кнопки. По моему этот ГСЧ (релейный) может быть даже более эффективным. Т.е сколько импульсов он даст - в зависимости от раствора контактов, напряжения на данный момент, влажности, температуры воздуха, времени срабатывания самого реле, которое всегда разное, и состояния окружающей среды, а также состояния человека, нажимающего на кнопку ( а оно не может быть одинаковым в разные промежутки времени), - вот это и будет неопределённый ипмульс.
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: Starling от 05 сентября 2009 г., 11:06:39
Конечно.
Любая механика, измеренная с высокой точностью электроникой - даст чистый случайный ряд.
Очень жаль, что реле (особено с мощными, достаточно шероховатыми контактами) требуют много электропитаиня.
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: Кай от 02 февраля 2012 г., 16:52:43
Есть другой вариант генератора, который также является электронным, и он именно ГСЧ а не ПГСЧ. Сам  шум генерируется с помощью стабилитрона включенного в "неправильном" режиме работы. Если через стабилитрон задать постоянный ток(например с помощью токового зеркала), и напряжение на нем будет ниже напряжения стабилизации, то на его выводах начинается случайный шумовой процесс. Далее, с помощью конденсатора отсекается постоянная составляющая и сигнал подается на предусилитель. Выход усилителя через развязывающий конденстор подается на вход быстродействующего компаратора(тут следует с помощью внешних элементов задать нужный порог и гистерезис). С компаратора на выходе мы будем получать цифровую случайную последовательность импульсов. Далее эту последовательность можно просто считывать портом микроконтроллера, и заполнять ей регистр. Ну, а когда у вас есть регистр со случайным числом, то дальнейшая разработка прибора зависит уже от конкретных нужд и реализации.
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: Sagittarius от 26 февраля 2012 г., 18:09:37
Устройство предложенное Starling` ом,  по моему глубокому ИМХО, есть не что иное как игрушка - вариант "Генератора случайных чисел" из книги Л.Д Пономарёв и А.Н. Евсеев "Конструкции юных радиолюбителей", из серии Массовая радио-библиотека, Выпуск 1090, 1985 год, стр.22. Правда, выполненная на другой элементной базе, но от этого ее смысл и принцип действия не изменится. Кто ее сделает получит этакое электронное плацебо, позволяющее почувствовать свою сопричастность с нетрадиционной "науке". Источник (книга) это то что есть у меня. На самом деле схема ещё более ранняя. Посмотрите на элементную базу 155 серия!
Кай, то что предлагаете Вы, тоже "с бородой" — почти полное описание устройства, называемого "Костёр...без пламени" из книги Б.С. Иванова "Самоделки юного радиолюбителя", издательство ДОСААФ СССР, 1988 год, стр 40. (И это, точно не первая публикация). Берём выходной сигнал этой схемы, формируем из пары выходных импульсов прямоугольные импульсы случайной длительности (старт-стоп), подаём на вход упомянутого выше "Генератора случайных чисел" и получаем предложенную вами схему.
Сравниваем со схемой  Принстонской лаборатории,  упомянутой Uncle Mike http://forum.kosmopoisk.ru/index.php?topic=2227.msg39370#msg39370 (http://forum.kosmopoisk.ru/index.php?topic=2227.msg39370#msg39370), удивляемся.... Но всё равно получаем игрушку.
Кстати, энтузиасты неизведанного, скачайте и внимательно просмотрите упомянутые книги. Сколько там "велосипедов" придуманных до вас. Может и почерпнёте ценные идеи.
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: Samcrew от 01 октября 2012 г., 21:28:30
Легкий способ генерации чисел - операции с битами потока данных с микрофона..
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: radioman от 16 декабря 2012 г., 19:07:17
А еще есть один прикольный вариант - приставка к дозиметру! Вы нажимаете кнопку пуск. Срабатывает триггер - устройство с двумя устойчивыми состояниями. После отпускания кнопки триггер остается в переключенном положении и разрешает работу счетчика импульсов, который получает импульсы от генератора и так же считает по кругу, от 0 до 9 (как захотите, решается легко). Через некоторое время дозиметр регистрирует очередную гамма - частицу и *опрокидывает* триггер. Процесс останавливается и на индикаторе - некое число. Достоинство данного варианта - результат от человека вообще не зависит! Частицы -то летят неравномерно.
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: Grey от 16 декабря 2012 г., 23:16:37
radioman, интересная идея. Но я бы предложил использовать её совместно с вариантом Starling'a.
ЦитироватьДостоинство данного варианта - результат от человека вообще не зависит!
Я бы не относил это к достоинствам или недостаткам. Полагаю нельзя полностью отстранять человека.
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: radioman от 17 декабря 2012 г., 00:10:44
Ну дело как говорится хозяйское. Тут я исходил из принципа наличия пусть и с точки зрения статистики не совсем правильной, идеи о хаотичном во времени распределении радиоактивных частиц, попадающих в датчик дозиметра. А вообще хочу заметить, что даже использование счетчика, считающего по кругу и получающего импульсы от дребезга кнопок  - не совсем правильно. Я как-то паял один приборчик. Надо было подсчитать количество срабатываний импульсов от ИФК - датчика за некоторое время. Подключил к микросхеме 10 светодиодов и для испытания узла решил пустить *бегущий * огонек по кругу. А подключать генератор поленился. Просто касаюсь пальцем входа микросхемы. В сети как известно 50 герц и от наводки микросхема *крутится*. Сплошная дорожка горящих светодиодов. Но все вроде горят. Убираю палец - горит один. Сбрасываю микросхему на ноль и опять касаюсь. Так несколько раз. И вот что замечаю - второй ну никак не остается. И шестой редко. А вот восьмой чаще других. Парадокс!  В секунду от пальца поступает 50 импульсов. Палец я держу разное время. Так что должна быть равновероятность остановки в любом положении. Потом понял - есть какая-то паразитная обратная связь - зависимость между номером выхода микросхемы и чувствительностью самого входа. В момент прекращения контакта с пальцем как-то она проявляется, типа когда на некотором определенном выходе появляется сигнал, вход *тупеет* и перестает реагировать. Вот такие пироги с котятами. Так что просто дребезг контактов использовать нельзя. Кнопкой надо  управлять запуском высокочастотного генератора, который будет выдавать на счетчик сигналы строго определенной амплитуды.  В принципе, в схеме Старлинга так и происходит. Но вот если кто-то захочет собрать другие, предложенные сдесь более простые варианты - то должен учесть. Правда, я использовал К176 ие8, а вот как на ТТЛ - логике будет - не знаю.
Кстати, а зачем кварц ставить -то? Я вообще бы на конденсаторе генератор собрал и еще терморезисторы всунул. Для хаотичности.
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: Grey от 17 декабря 2012 г., 00:49:17
А если с другой стороны подойти.
В лозоходцев веришь? 100% результатов конечно не бывает, но всё же.
Перед поиском лозоходец настраивается.
А что ты делаеш со схемой Старлинга. Нажимаеш кнопку, смотриш результат, записываеш, нажимаеш...
И так медитируешь до достижения нирваны :)
Это я отношу к достоинствам его схемы.
Название: Re: TG-RND7: Принцип генерации случайных чисел.
Отправлено: radioman от 17 декабря 2012 г., 19:29:32
По поводу лозоходцев - не знаю. Как и по поводу экстрасенсов. Возможно, настоящие есть. Но на одного 10000 шарлатанов. Сам работу лозоходцев не видел непосредственно, а что там по ТВ - ну сам понимаешь. Очень давно был интересный случай - ушиб внешнюю сторону ладони об угол стола. Вроде мелочь, чертыхнулся... Но потом одну неделю как-то не так ладонью шевельнешь - побаливает. Вторая неделя пошла. Как-то в  компании познакомился с познакомился с одной девушкой. И она заметила, что я при неком движении рукой поморщился. Спросила, в чем дело. Я расказал Она предложила *прогреть*. Ну, почему бы и не попробывать? Сказала держать ладонь горизонтально пнред собой. Одну свою ладонь поместила примерно в 10 см над моей, а другую - под И что самое интересное, от нижней почувствовал легкий холодок, а от верхней на мою ладонь пошло тепло! И через минуту стало даже жарко! Я в шутку напомнил, что моя ладонь не котлета. Она засмеялась и все кончилось. Ладонь больше не болела. Вот именно она действительно обладала способностями!
По поводу приборов Старлинга - ну не знаю. Я вообще - то сомневаюсь в полезности этой схемы. Как-то все *за уши притянуто*. Сам я таким не занимаюсь и такие приборы не делал, не пользовался, не состоял. Ну а если кому-то нравится - ну не самое страшное увлечение.