Пользователь
0,0
рейтинг
24 ноября 2011 в 17:04

Разработка → Создаём аппаратный генератор случайных чисел

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





Магия случайных чисел меня привлекала с раннего детства. Дата рождения, смерти, одарённость, выигрыш в лотерею, билет на экзамене и т. д. — всё это случайные события. С другой стороны, глядя на наш мир, понимаешь, что случайностей не бывает. Или как говорят учёные: Случайность – это не исследованная закономерность. Мне всегда было интересно, почему вот наступает именно это случайное событие, а не другое? Почему монетка, брошенная сейчас, выпала решкой, и может ли что-то повлиять на это событие? Какие взаимовлияния случайностей друг на друга, можем ли мы влиять на эти случайные величины? Все эти вопросы находятся пока за гранью науки, но интересно на них найти ответ. К сожалению, в институте, я не достаточно хорошо оценил предмет «Теорию вероятности» и просто прошёл его, за что и получил минус жизненной кармы. По сему сегодня я всячески стараюсь наверстать упущенное.

Постановка задачи



Для различных инженерных и вычислительных задач требуется поиск случайных чисел. Причём, чем выше энтропия числа, чем ниже его закономерность и предсказуемость, тем лучше. Все мы пользовались в программировании функцией генератора случайных чисел. На самом деле, все эти числа псевдослучайны. Они могут вычисляться по очень сложному алгоритму, или вообще представлять собой «слепок» случайных шумов системы (как например /dev/random и /dev/urandom ). Но всё же, как ни странно, эти случайные числа предсказуемы. Самый очевидный способ получения случайных чисел, это брать их извне. Ведь наш реальный мир — это громадный генератор случайных величин. Конечно же все эти величины тоже псевдослучайны, но их закономерности и взаимозависимости проследить невозможно, из-за бесконечного количества вариантов происходящих событий. Надо так же понимать, что нельзя рассматривать случайные числа, как числа появляющиеся в замкнутой системе, поскольку на них идёт влияние бесконечного множества внешних факторов. Тогда, если разобраться, каждое событие совершенно не случайно и имеет свою закономерность. Просто учесть все взаимовлияния (а их бесконечно много), невозможно, по сему для простоты принимают многие события случайными.

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

+ + Sound card = Random generator

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

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

Гистограмма частоты числа наблюдений случайной величины



Случайные величины колеблются возле какого-то одного значения (математического ожидания этой величины). Положим, мы снимем несколько тысяч случайных точек, найдём максимальное и минимальное значение, которое принимает случайная величина. Возьмем интервал от минимального значения, которое принимает случайная величина, до максимального значения, которое может принимать случайная величина. Разобьём этот интервал на равные интервалы, например на пятьдесят. Ололо пыщ-пыщ, никто же не читает. И посчитаем, сколько случайных величин попадёт в каждый интервал, то мы получим диаграмму распределения случайной величины. Надо сказать, величина рассеяния случайного события определяется, и измеряется она дисперсией. Данный способ построения диаграммы рассеяния случайной величины называется интервальным. Он основан на разбиении исходных численных значений на интервалы.
Если на пальцах представить, что такое распределение, то это будто мы сыпем из ладони песок, в соответствии с изменением сигнала по вертикальной оси.
Проиллюстрирую примером. Колебания маятника. Если его развернуть во времени, то получится синусоида f(x)=sin(x) – это исходный график, распределение которого мы ищем. Если к этому маятнику приделать солонку, которая сыпет песок, то она и будет рисовать диаграмму распределения. Продемонстрируем как это выглядит

Пример куска кода для построения:


do
{
	y=512*sin(x)+512;
	count=0;
	for (i=0;i<n;i++)
	{
		if ( y<count+deltay && y >=count) 
		{
			a[i]=a[i]+1;
			break;
		}
		count=count+deltay;
	}
	 x=x+deltax;
}
while  (x<200*3.14159265);


И график f(i)=a[i]


График «распределения» синуса.

Если говорить о солонке на маятнике, то становится понятно, почему получился такой график. В высшей точке колебания маятника, которая соответствует пикам синусоиды, движение замедляется и там песочек должен образовывать «горки», а в точке нуля должно быть минимальное количество песка, т.к. это место маятник проходит с максимальной скоростью.

Распределение Гаусса или нормальное


Наилучшим образом это демонстрируется на этом видео, с использованием доски Гальтона ru.wikipedia.org/wiki/Доска_Гальтона, взятым из курса лекций МИФИ



В моём институте тоже был аналогичный опыт, и преподаватель произнёс сакральную фразу, которая произвела на меня большое впечатление: Я пятьдесят лет провожу этот опыт, и всегда получаю одну и ту же картину. Формально, ничего не мешает частицам лечь равномерно, однако всегда мы получаем распределение Гаусса.

Распределению Гаусса подчиняются различные величины. Например, стрельба по мишени – пули будут ложится в мишень по распределению Гаусса. Наиболее кучно в десятки и наименее по краям. Разумеется, электрический шум (если он не вызван наводкой электрической сети), тоже будет подчиняться этому распределению.

Распределение Пуассона


Существуют и другие виды распределения случайной величины. Например, существует распределение Пуассона. Одна из особенностей распределения Пуассона является то, что случайная величина является дискретной. Самой лучшей иллюстрацией событий распределения Пуассона могут быть звонки в какой-нибудь call-центр. Количество звонков поступивших за единицу времени будет случайной величиной. Или вот, пока я отлаживал программу, о которой скажу ниже, я измерял интервалы нажатия на клавишу. Интервалы измерял микроконтроллер, считая прошедшее количество тактов между каждым нажатиями. Я сделал несколько тысяч нажатий и получил вот такую диаграмму.


Диаграмма распределения частоты нажатий на кнопку.

Кстати говоря, я не зря сказал, что случайных величин не бывает. Здесь я нажимаю пальцем на кнопку. Случайность интервалов нажатия обусловлена тем, что мой мозг занимается обработкой различных сигналов, мечтами о «вечном», мысли о программе и т.д. Плюс так же, сигналы от мозга достигают конечностей тоже не со скоростью света, т.к. ионный обмен при передаче сигналов обусловлен химическими процессами в моём организме и т.д. и т.п. В результате мы имеем совершенно случайную интенсивность нажатий.

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

Равномерное распределение


Самое ценное распределение, с точки зрения программиста – это равномерное распределение. Когда случайные числа любой длинны, встречаются одинаково часто на всём заданном диапазоне. Пример из жизни такого распределения, это время ожидания транспорта на остановке, при учёте того, что транспорт ходит с одинаковыми интервалами времени. Вы можете придти и тут же сесть в маршрутку, тогда время вашего ожидания будет равно нулю, или прямо из под носа уйдёт эта маршрутка. Тогда время вашего ожидания будет равно интервалу следования маршруток. Но, как правило, приходится ждать. И если мы разобьём время ожидания на интервалы dt и построим гистограмму частот попадания на маршрутку, допустим на несколько лет, то она будет линией.


Гистограмма частот попадания на свою маршрутку.

По вертикали отложено количество попаданий на маршрутку, а по горизонтали время ожидания маршрутки.

Например, гистограмма распределения данных, получаемых /dev/random


Гистограмма системного генератора случайных чисел

Вы можете сами получить данную гистограмму, заменив в моей программе, о которой будем говорить ниже, /dev/audio (/dev/dsp) на /dev/random (инициализация звуковой карты никак не влияет на генератор случайных чисел).
Надо заметить, что я раз 15 перезапускал программу, чтобы получить гистограмму наиболее близкую к теоретической. Это говорит о несовершенстве этого генератора случайных чисел. Синяя линия показывает, как эта гистограмма должна выглядеть в идеале.

Другие типы распределений можно посмотреть на этом рисунке


Основные типы распределения случайных величин.

Взятым с www.ievbras.ru/ecostat/Kiril/Library/Book1/Content350/Content351.htm.

Меньше слов и больше дела



Наверное, я уже успел надоесть своим любительским тервером. По сему, от теории переходим к практике. Моя программа написана под Linux, и тестировалась на Ubuntu 10.10. Для построения диаграмм в системе должен быть установлен пакет gnuplot, без него программа работать не будет.
К слову сказать, я всячески рекомендую всем инженерам разобраться с кроссплатформенным программным пакетом gnuplot. Это идеальный пакет для построения любых графиков. После работы с ним, я забыл, что такое построение графиков в MS Excel как страшный сон. День-два разобраться, и потом на лабораторках в институте или на работе вы будете радовать себя и других оригинальными графиками высокого качества. Несомненный плюс, что данный пакет можно использовать в в программах, для быстрого и простого построения графиков.
На этом о гнуплоте всё, я не буду подробно останавливаться, как же я строил графики. Лучше как-нибудь отдельно напишу пост, посвящённый этому замечательному пакету.

Итак, что же делает моя программа. Она в течении трёх секунд

#define LENGTH 		3    /* how many seconds of speech to store */


С частотой дискретизации 96000 Гц

#define RATE 		96000   /* the sampling rate */


Записывает данные типа signed short

#define SIZE 		16      /* sample size: 8 or 16 bits */


С одного входного канала звуковой карты

#define CHANNELS 	1  /* 1 = mono 2 = stereo */


Данные записываются сохраняются в массив

short buf[LENGTH*RATE*SIZE*CHANNELS/16];


После чего инициализируется звуковая карта, и в течении трёх секунд считываются данные. Я честно признаюсь, что полностью всех особенностей работы со звуковой картой я не исследовал. Не пробовал читать в стереорежиме, принимать 24-х разрядные данные. Я пробовал менять только частоту дискретизации. Так же хочу сказать, что получение данных со звуковой карты выходит не всегда стабильным. После перезагрузки системы я перезапускаю эту программу несколько раз, чтобы получить гистограмму. Иногда она выдаёт совершенно непонятные значения. С чем это связанно, я так же не знаю.
После инициализации звука и чтения всех данных в массив buf, мы находим минимальное и максимальное значение массива. После чего сохраняется не отсортированный массив в array.dat (из которого можно потом построить осциллограмму снимаемых данных). Далее массив сортируется функцией


quickSortR(buf, lbuf);


Для отладки сохраняется отсортированный массив в файл error.log.

Дальше мы находим дельту – интервал ячейки, в который мы будем складывать наши значения:
deltay=(unsigned short)((max-min)/n_rasp+1);

Выделяем память для массива распределения. Выделение память сделано для универсальности, чтобы можно было динамически менять размер распределения.

rasp = (unsigned int *)(malloc(n_rasp*sizeof(unsigned int)));


После чего начинаем считать, какие же значения попали в какой интервал, или проще говоря строить распределение случайных величин:

 
for (i=0;i<n;i++)
 {
	count=min;
	for (j=0;j<n_rasp;j++)
	{
		if ((buf[i] >=count) && (buf[i]<=count+deltay))
		{
			rasp[j]++;
			break;
		}
	count=count+deltay;
	}
}

Уже по этому графику можно построить диаграмму распределения случайной величины. Но я хочу сравнить практическое распределение с теоретическим графиком Нормального распределения, который строится по формуле взятой из википедии ru.wikipedia.org/wiki/Нормальное_распределение:



Для построения по этой формуле нам необходимо найти два параметра: Математическое ожидание и дисперсию. Как я говорил, математическое ожидание – это величина, вокруг которой колеблется случайные числа. Дисперсия – это мера рассеяния. Есть два пути нахождения этих величин – из исходного массива и из получившейся диаграммы. Математическое ожидание я нахожу двумя способами, но использую последний, дисперсию нахожу только последним способом.
Математическое ожидание в нашем случае – это просто среднее значение всех случайных величин. Находим его так

 
for (i=0;i<n_rasp;i++)
{
	summall=rasp[i]+summall;
	math_f+=rasp[i]*i;
}
printf("math_f = %3.5f sumall=%d\n",math_f,summall);
math_f=math_f/summall;
printf("Математическое ожидание 2 = %3.5f\n",math_f);


Дисперсия определяется как квадратичное отклонение случайной величины от математического ожидания. Мы его находим следующим образом:


 
for (i=0;i<n_rasp;i++)
{
	dispers+=((long double)(i)-math_f)*((long double)(i)-math_f)*(rasp[i]);
}
dispers=dispers/summall;
printf("Дисперсия равна = %4.5Lf\n",dispers);
...
//После чего сохраняем полученные данные в файл 
for (i=0;i<n_rasp;i++)
{
	gausse=(long double)summall*exp(-((i-math_f)*(i-math_f))/(2*dispers))/(sqrt(2*3.14159265*dispers));
	fprintf(logf, "%3ld  %5d  %+07.5Lf (%10d;%10d]\n",i,rasp[i], gausse ,dat, dat+deltay); //write to file		
}
....
//И строим по полученным данным гистограмму и осциллограмму снимаемого сигнала:

gnuplot(outputfile, 0, 0);
gnuplot("dat/array.dat", 1, 0);


Здесь:

gausse=(long double)summall*exp(-((i-math_f)*(i-math_f))/(2*dispers))/(sqrt(2*3.14159265*dispers));

Это и есть рассчёт распределения Гаусса, с использованием математического ожидания и дисперсии.

Полученную программу можно скачать тут: narod.ru/disk/32347266001/sound_distribution.tar.gz.html
Опосля компилируем программу командой make.

Для правильной работы программы нужно настроить звуковую карту. В Убунте это делается так: Система-> Параметры-> Звук. Выбираем микрофонный вход, выставляем громкость на максимум и снимаем галку «Выключить». Опционально, можно подключить к линейному входу звуковой карты радиоприёмник, тогда вместо микрофонного входа можно использовать линейный вход.
Одно замечание — микрофон должен быть отключен от входа звуковой карты. Говорят, что бросать микрофонный вход не стоит, так что в принципе можно зашунтировать (для желающих) его сопротивлением равным сопротивлению микрофона.

Итак, запускаем программу «./sound_distribution» и любуемся спустя 3-4 секунды результатом.


Гистограмма полученных значений


Осциллограмма получаемых значений с микрофонного входа.

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

Применение на практике



Как я уже описал, для программиста нужны числа, имеющие равномерное распределение. В данном случае у нас распределение нормальное, где число колеблется вокруг математического ожидания. Чтобы получать числа, необходимые нам, надо брать младшие четыре бита числа. Эти четыре бита будут принимать совершенно случайное значение. И эти четыре бита укладывать в число необходимой длинны. Например, для того чтобы заполнить число типа short (2 байта), нам понадобится 4 числа снятых со звуковой карты, а точнее их младшие разряды. Вот пример кода:

 
short random_num=0;
for (i=n; i<n+4; i++)
{
	random_num<<= 4;
	random_num+=buf[i]&0x0F;	
}


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

Планы на будущее



На будущее я хотел сделать программу на GTK+, чтобы можно было ползунками изменять ширину интервалов, частоту дискретизации, количество получаемых данных, входные данные и т. п. Но увы, обломал пока зубы. Сделал только график осциллограммы получаемого сигнала, склепав его из нескольких программ. В этом вопросе я буду очень признателен за посильную помощь.
Как вариант, можно поставить стационарный приёмник, поставить вторую звуковую карту, чисто для генератора случайных чисел. Написать демон или драйвер, которые бы имели некий файл случайных данных, наподобии /dev/random, из которого можно читать данные. В общем, применений масса.

Примечания и выводы



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

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

Моя программа сохраняет три файла:
array.dat – Это просто сырые данные снятого массива
error.log – этот файл предполагался (как видно из названия) для сохранения ошибок, но пока используется для сохранения упорядоченного массива. Который в общем-то и служил мне для отладки.
sounddist.dat – Сам файл выходных данных. В первом столбце порядковый номер столба диаграммы, второй столбец– значение относительных частот, третий – распределение Гаусса, рассчитанное по стандартной формуле, четвёртый – диапазон значений, которые попадают в данный столбец диаграммы.

Я не знаю почему, но в этой программе перестали работать #define. Попытка инициализировать переменную с помощью define приводят к ошибке. Как, например, если заменить: «arg = 16;» (строка 83) на «arg = SIZE;» (закоменнтировать строку 83 и раскомментрировать строку 79), то компилятор выдаст ошибку:

sound_distribution.c: In function ‘main’:
sound_distribution.c:81: error: stray ‘\321’ in program
sound_distribution.c:81: error: stray ‘\216’ in program
make: *** [sound_distribution] Ошибка 1


Самое забавное, что в оригинальной программе инициализация переменных идёт именно через дефайны. Отсутствие дефайнов делает код не очень удобным для правки, но беглое гугление не дало ответ на эту проблему.


Ошибка найдена и исправлена, спасибо galaxy

В качестве вывода хочу сказать, что аппаратный генератор случайных чисел получить очень просто, достаточно только оглянуться вокруг :).

Я буду признателен любой конструктивной критикие, начиная от стилистики написания программ, заканчивая алгоритмами. Так же буду признателен за любую посильную помощь в продлжении проекта на GTK+.

Так же хочу сказать, что данный пост не последний по этой теме.

Список используемой литературы



1. ru.wikipedia.org/wiki/Нормальное_распределение
2. ru.wikipedia.org/wiki/Распределение_Пуассона
3. tegir.ru/ml/k66.html аппаратный генератор случайных чисел.
4. www.mtu-net.ru/aborovsky/articles/linsnd1.htm Программирование звука в Линукс (рус)
5. www.oreilly.de/catalog/multilinux/excerpt/ch14-05.htm пример программы работы со звуком в Линукс, который используется в моей программе.

Добавляются:
6. Н.С. Маркин «Основы теории обработки результатов измерения»
7. habrahabr.ru/blogs/python/62237 Случайные числа из звуковой карты

Список литературы будет ещё дополняться и расширяться, поскольку сейчас под рукой нет всех тех книг, которые я использовал при написании программы, понимании тервера и написании этого поста.
Сергей @dlinyj
карма
452,5
рейтинг 0,0
Пользователь
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (104)

  • +11
    В криптографии хорошим тоном является пропускать сырые данные с выхода аппаратного ГСЧ через любую криптостойкую хеш-функцию.

    Кстати, умело подбирая объем хешируемого блока данных, можно добиться, чтобы объем появляющихся на выходе хеш-функции данных был практически равен их энтропии (т.е. в Вашем случае отпадет этап «берем только младшие 4 бита», тем более, что у них тоже может обнаружиться определенная неочевидная корреляция).
    • +1
      тем более, что у них тоже может обнаружиться определенная неочевидная корреляция)

      Я больше, чем уверен, что там есть некоторая корреляция. И считаю, что разумеется сырцом данные использовать нельзя.
      • +2
        50 герц там полюбому есть.
        • +1
          Если бы она была, то распределение было бы, как в картинке про распределение синуса. У меня есть такие гистограммы: 50 Гц + шум. Вечером постараюсь показать.
          • +1
            Может быть не 50 герц+шум, а что-то более хитрое, но с периодом 50 герц. Спектр получаемого сигнала какой? Это было бы интересно глянуть
            • +1
              Вот интересный график. Я «бубучу» в микрофон, и смотрим получаемую гистограмму:


              Осциллограмма


              Полученная гистограмма

              Пропавший столбик вызван небольшой ошибкой в программе, сути явления он не меняет. И вот второй вариант для примера:


              Осциллограмма


              Полученная гистограмма

              По крайне мере любопытно ;).
              • +1
                Ненене, интересна именно спектрограмма у шума) Я почти уверен что там будет несколько пиковых частот, где один будет на 50 герцах.
                А если спектрограмма будет иметь отличное от равномерного распределение, то, по сути, уже появляется большая корреляция получаемых данных.
                • 0
                  Если мне будет не лень, то я попробую это сделать
              • 0
                хотя это тоже забавно) Если говорить вслух около звуковухи, то она уже перестаёт быть генератором шума;)
  • +50
    В тексте есть прикольный момент:)

    «Ололо пыщ-пыщ, никто же не читает.»

    Чем-то напомнило, из анекдота «А сердечник мы сделаем из дерева, все равно дипломную работу никто не читает»
    • +4
      Приятно, что внимательно читаете :).
      • +7
        Сначала читал внимательно… После этого сломался и начал листать до комментов, проверить я ли первый это увидел! :)
      • НЛО прилетело и опубликовало эту надпись здесь
      • +3
        Рановато вставили :)
    • +7
      Мы со знакомым на сайте, где контент 50/50 — бесплатный и платный, платный покупается за поинты, которые можно оплатить платежной системой, либо комментируя статьи, и т.д., в правилах регистрации в середине написали, — «Если вы это видите, отправьте письмо администратору и получите 50000 поинтов бесплатно». До сих пор никто не написал.
    • 0
      Странно, я этот блок читал вдумчиво и эту надпись вообще не заметил :/
      • 0
        Я её раза четыре прочитал, стараясь понять, как она относится к теме.
  • +7
    Из всего текста лучше всего я понял только «Ололо пыщ пыщ».
    • 0
      Что же, лекция профессора не дала наглядности?
      • 0
        Вечером из дома посмотрю и прочитаю повнимательнее.
      • 0
        Лично я вообще на этих видео-лекциях застрял (опять) и не осилил статью дальше.
  • +3
    И действительно, интересная стилистика написания самого поста. Этакое «академическое графоманство». Но не всем же стопроцентно прикладные посты писать.

    Респект, очень интересно!
    • +3
      Я искренне старался максимально упростить и сделать максимально доступнее, но увы есть некий предел, когда простота превращается в бред :).
      • +1
        А мне как раз наоборот показалось что вы замечательно объяснили разные типы распределения.
        • 0
          Лучше изложено в учебниках :). Я вечером добавлю в список литературы одну книженцию, где всё отлично разжованно.
  • +1
    Надеюсь, скоро это проблема будет навсегда решена как была решена с дискретными сетевыми и звуковыми картами, дело только за AMD:

    www.gcsec.org/blog/intel%C2%AE-include-pseudo-random-number-generator-future-cpus
    • 0
      Непонятно почему это не сдллали ещё на заре, так же как и проверка деления на ноль.
      • +1
        Сделали в 1999, вот тут интересная статья про это: habrahabr.ru/blogs/crypto/128666/
        • 0
          Спасибо за ссылку!
  • +4
    Матчасть приятно описана.
    А формулы в коде легче читаются, если хотя бы использовать пробелы вокруг операторов.
    В целом понравилось, продолжайте пожалуйста =)
    • +2
      Спасибо.
  • +3
    А вы не пробовали прогонять полученные данные через тесты Die hard? Сами тесты в исходниках есть тут
    • 0
      Нет, не пробовал.
      • +2
        Было бы крайне интересно прогнать
        • +1
          У нас лабораторная именно такая была — ввод со звуковухи — на DieHard
  • 0
    Программа это хорошо, а вот наскоро написанный реферат по терверу кажется несколько лишним.
    • 0
      Не понял про реферат? :)
      • +1
        Да весь этот вводный курс. Кому надо, в учебнике лучше прочитают, а кому не надо, можно было в двух словах объяснить. К тому же, в тексте много логических нестыковок, отсюда и мнение, что наскоро.
        • +1
          Если мне укажут на нестыковки, я с готовностью их поправлю. Данный «реферат» писался около трёх-четырёх дней, с полным обдумыванием каждой детали, чтобы не осложнять понимание.

          В учебниках без сомнения лучше описано, в особенности в тех, где есть примеры. Я не ставил цель переписать учебник своими словами. Однако для понимания картины, привёл здесь некоторое моё понимание тервера :).
          • 0
            Да не вопрос, отписал в личку.
  • +3
    Да, кстати, а почему вы системному генератору случайных чисел дали десятки проб, а своему десятки тысяч??
    • 0
    • 0
      Системный и мой генератор стоят полностью в одинаковых условиях. Просто вместо /dev/sound в массив поступают данные из /dev/random. Вы можете сами попробовать.
  • +7
    «Конечно же все эти величины тоже псевдослучайны» — некоторые физические величины стоит все же полагать реально случайными, а-то квантовая механика сломается.
  • +2
    За статью, конечно, спасибо, но самая главная благодарность уходит за видеолекцию.
    Пару лет назад на дерти.ру уже выкладывали саамый первый ролик (этакую демо-версию) и тогда еще материал только подготавливался и я не мог дождаться когда доделают, проверял сайт. А потом забыл. -(
    Теперь буду сидеть, смотреть вечерами.

    Рассказывает и показывает очень уж хорошо!
  • –1
    «Сегодня атеисты бьют тревогу,
    И я не знаю, кто бы им помог.
    Ведь если Бога нет, то слава Богу,
    А ежели он есть, то не дай Бог!»
    ©

    Это не только в ваш адрес, конечно, ничего личного. Просто удивляет воинствующая тенденция хабровчан всё и вся перепроверять и ставить под сомнение ;)
    • 0
      Упс! Адресовано было на каммент sanix
      • 0
        а, ок :)
    • 0
      Я не перепроверяю и не ставлю под сомнение. В тексте описано, что данный пост является побочным продуктом другого исследования. Полагаю, что программа и подход могут быть полезны.
    • +3
      Вы предпочитаете нам людей, которые безоговорочно соглашаются со всем сказанным?
      • 0
        Да нет, я и сам отчасти такой:) Но тенденция опасная.
        • 0
          Такие воинствующие ещё и коллайдер построили. Чтоб всё и вся проверять и перепроверять. Короче, хорошо что мы есть :-)
  • –1
    Графики распределений, нарисованные вручную в пэинте жгут)
    Вы бы их лучше в википедии взяли, а то тут у них какие-то горбы лишние…
    • +3
      Не пойму, почему этот комментарий минусуют. Ведь он в общем-то по делу.
      • 0
        Думают что придрался) Но я это, любя, из перфекционизма только) Статья хорошая))
  • +2
    Вместо ололо пыщ пыщ можно применять и более интересные приёмы. Я, например, вставил в середину одного из текстов песен строки о том, что даю всем добравшимся до сюда мороженое. Пока только одна подруга заявила своё право на пломбир.
  • +1
    Идея не нова, но использовать ее в таком виде нельзя, слишком уж подвержена система внешним воздействиям. Таки да, коэффициент автокорреляции будет стремиться к нулю, но вот атакующий специально сформированными наводками сможет сместить распределение в нужную ему сторону.
    Кстати, интересные генераторы случайных чисел получаются из весьма необычных вещей — например, транзистор МП26 со спиленной крышкой, направленный на солнышко, дает почти гауссово распределение. В светлое время суток :)
  • +1
    Из всех теорем тевера, наиболее люблю Central Limit Theorem. Она прекрасна.
    Суть ее в том, что какое бы странное и кривое у нас бы не было изначальное разложение вероятностей, то если брать пробы и суммировать результаты, все равно получится чистый Гаусс (:
  • 0
    Зная частоту приемника, можно передавать на этой частоте заведомо известный сигнал, чем сильно сузить распределение генерируемых чисел: вместо равномерного будет нормальное.
  • +7
    «Случайности не случайны, мой друг...»

    image
    • +4
      На месте этой картинки пару минут назад я увидел «интенсивность запросов превышена...», мне кажется это было не случайно.
      • +2
        картинка

  • 0
    Вы столько раз повторили тезис про детерминированность событий внешнего мира, что мне просто стало интересно — вы квантовую физику хоть как-то учили? Хотя бы на школьном уровне?
    • 0
      Когда-то учил, лет 6-7 назад. Даже экзамен по ней сдавал. Но я её прошёл :). А что?
      • 0
        М… Я полагал, что после некоторого рода неравенств, которые изучаются в оном курсе, вопросы о детерминированности явлений больше не поднимаются.
        • 0
          Быть может вы конкретизируете, что вы имете в виду?

          На меня квантовая физика в институте произвела впечатление полностью нелогичной области. такое ощущение, что процессы которые протекают в ней не понимает никто. Да, математически описанно, явления все используются, но почему вот так не понимает никто.
          • 0
            Конкретизирую: неравенство Гейзенберга.

            Как можно говорить про детерминированность распада атома?
            • 0
              То, что мы не можем точно измерить или предсказать некое событие, плюс мы не знаем досконально все процессы, протекающие в мире (в т.ч. и квантовой механике), да и никогда знать не будем, то утверждать, что все процессы там недетерминированны нельзя.
        • +1
          Я хочу ещё сказать, что статья писалась для людей, которые могут ничего не понимать ни в квантовой физике, ни в программировании, ни в теории вероятности. По этому я хотел особо подчеркнуть, что «ничто не случайно» (с) Ричард Бах.

          Для меня, то что всё имеет свои закономерности стало ясно ещё лет в 7-10.
          • 0
            Для меня, то что всё имеет свои закономерности стало ясно ещё лет в 7-10.

            … включая то, что случайно. Полностью согласен!
            • 0
              Случайностей нет
              • 0
                Как и ложки.
  • +2
    Спасибо за статью, напомнило проект LavaRnd, где использовали «баночку» внешней энтропии (закрытую веб-камеру) для генерации чисел.

    Кстати, кроме гистограммы распределения было бы еще интересно взглянуть на корреляцию между соседними значениями, или спектр полученного шума, чтобы выбрать оптимальную частоту дискретизации. Так как не думаю, что все звуковые карты оцифровывают микрофон с частотой 96кГц.
    • 0
      Я тоже об этом думал, но мне уже было лениво реализовывать БПФ и функцию корреляции.
  • 0
    Кто первый сделает и разместит на Amazon Cloud JSON-генератор? :)
  • +2
    > Я не знаю почему, но в этой программе перестали работать #define. Попытка инициализировать переменную с помощью define приводят к ошибке

    Потому что в конце строки 13 пара неведомых символов притаилась (D1 и 8E, что как раз stray \321 и stray \216 в восьмеричной системе счисления)
    • +1
      Бью челом поклоны!
  • +2
    Недавно в одном из топиков я заикнулся о идее получения случайных чисел с белого шума и мне ответили, что такая идея уже реализована в сервисе рандом.орг
  • –1
    Готов инструмент для исследования EVP?
  • НЛО прилетело и опубликовало эту надпись здесь
    • 0
      Спасибо.
      • НЛО прилетело и опубликовало эту надпись здесь
  • 0
    «При помощи совпадений Бог сохраняет анонимность.» — Альберт Эйнштейн.
  • +1
    В качестве доп. литературы habrahabr.ru/blogs/python/62237/ )
    Там заодно написано как получить равномерное распределение.
    • 0
      добавил
  • +1
    В силу того, что знаком с автором лично, комментировать в духе «ура-ура» и «превосходно» было бы небольшим лицемерием))
    Но при ее устной озвучке сама идея показалась классной и напомнила что-то из фантастики.
    Круто, короче, что есть такая партия такие люди)
    Предлагаю посильную таки помощь.

  • +1
    «ничего не мешает частицам лечь равномерно...»
    Мешает то, что частицы высыпают по центру отностительно ряда каналов, соответственно вероятность того, что частица допрыгает до края самая маленькая, а то, что останется по центру — самая большая…
    • 0
      Тут важное слово «вероятность», т.е. значит существует сверх-малая вероятность, что все частицы лягут равномерно?
      • 0
        Существует, но эта вероятность на столько «сверх-малая», что для того, чтобы увидеть равномерное распределение, вашему преподователю явно нужно ждать этого не 50 лет.
        • –1
          Боюсь, как раз, что частицы никогда не лягут равномерно, их достаточно большое количество чтобы теория вероятностей, так сказать, сработала. То что подвержено закону распределения, будет ему подчиняться, будь тому 50 лет, 500 или 500млн лет.
          • 0
            Всё это не факт. Раз есть вероятность, значит это возможно.
            • 0
              Вероятность здесь относится к попаданию зерна в тот или иной канал, распределение вероятностей обусловлено схемой самого стенда
              • +1
                спасибо КЭП. Я говорю вот о чём, бросив монету 10 раз, она может все десять раз выпасть решкой.
                • 0
                  Применительно к данной схеме это то же самое если в конусе будет 10 зерен и если каждое из них попадет в отдельный канал, то мы будем говорить что они легли равномерно, тут вы абсолютно правы.
                  Я пытаюсь заострить внимание на том, что в данном случае вероятностное событие не распределение всех запущенных зерен, а запуск одного зерна.
                  Зерно с какой-то вероятностью попадает в тот или иной канал, а вот характер распределения этих вероятностей подчиняется известному закону.
                  • 0
                    Я согласен. Тут речь идёт о том, что могут ли зёрна упасть в виде равномерного распределения. Утверждаю, что могут. Вопрос в другом, сколько для этого потребуется опытов.
                    • 0
                      Тут я только говорю что как бы зерна не упали, распределение вероятностей гауссовское, вне зависимости от числа опытов, зерен или того как они легли. Вероятность того, что, в результате эксперимента, в каждый канал упадет одинаковое число зерен — не одно и то же что их распределение равномерно. Конечно есть вероятность такого события, однозначно зависящая от числа зерен.
  • 0
    Раз уж есть возможность снять данные с микроконтроллера, может попробуете в каком-нибудь виде построить график плотности распределения случайных чисел, собирая их с младшего разряда АЦП микроконтроллера? Уж очень интересно посмотреть «случайность» таких данных.
    • +1
      Там в списке литературы есть такая ссылочка tegir.ru/ml/k66.html. Там есть этот график. Можете ознакомиться.
      • 0
        Ой спасибо, а распределение то похоже очень даже неплохое
        • +1
          В общем, есть простой алгоритм, чтобы убирать наклон в сторону единиц или нулей, если такой вдруг возникает в твоем физическом процессе.
          Из последовательности выбираешь два бита. Если там 01, в выход ставишь 0, если 10, в выход ставишь 1, если 00 или 11, выкидываешь их и берешь следующие два бита.
          Есть улучшенный вариант алгоритма, у которого лучше выход, но он немного сложнее.
          Берется четыре бита и из них получаем от нуля до двух бит.
          0000 выкидываем
          0001 00
          0010 10
          0011 0
          0100 01
          0101 00
          0110 01
          0111 01
          1000 11
          1001 10
          1010 11
          1011 11
          1100 1
          1101 00
          1110 10
          1111 выкидываем

          via dlinyj.livejournal.com/560925.html?replyto=6789405 (типа комментарии к этому посту у меня в ЖЖ)
          • 0
            Еще раз спасибо, уже попробовал внедрить.
            Немного смущает недетерминированность времени генерации конечной последовательности бит. Зато приведенный в статье метод взлома SMART-карт тут неприменим :)
            • 0
              А можете рассказать, что вы делаете?
              • 0
                Вкратце, я занимаюсь изделием, к которому подключается плата расширения, плата простая, её легко повторить, поэтому я использую протокол идентификации для платы расширения. Ну а генератор случайных последовательностей делает всю соль.
                По большому счету, конечно, здесь нет никакой необходимости так сильно заморачиваться с генератором случайных чисел, но, с другой стороны, почему бы и не сделать хороший генератор :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.