kiev-security.org.ua-Криптография.Общий подход к генерации естественных случайных переменных

IEEE Transactions on Computers, C-19, 1970, pp.1210-1213, H.F.Murry. A General Approach for Generating Natural Random Variables. Аннотация. Моделирование, метод Монте-Карло и др. виды стохастических вычислений используют большое количество случайных чисел (СЧ) на высокой скорости. Могут использоваться псевдослучайные числа (ПСЧ) и числа, генерируемые в естественных случайных процессах - дробовом и тепловом шуме, радиоактивном распаде и др. Обсуждаются преимущества и недостатки обоих методов; делается вывод о том, что естественные СЧ предпочтительны по скорости и универсальности. Предлагается обобщгнный генератор естественных СЧ и схемные решения; рассматривается максимальная средняя скорость выборки; даны рекомендации по обеспечению некогерентной работы. Ключевые слова: метод Монте-Карло, шум, ГСЧ, стохастические вычисления. Введение Хотя СЧ используются не в каждой компьютерной программе, они получили широкое применение в разных научных областях [2]. Например, системное моделирование использует случайные переменные для представления помехового искажения входных сигналов, отклонения параметров, а также для ряда применений в системах связи, питания, транспорта и т.п. Помимо представления таких вероятностных событий многие узловые проблемы (например, решение уравнения Лапласа с произвольными несогласованными границами [5]) могут быть решены путгм рандомизации проблемы для решения методом Монте-Карло; простые схемы могут быть приспособлены для выполнения сложных вычислений [3] и др. Псевдослучайные последовательности, генерируемые программно при помощи детерминированных методов, удовлетворяют потребность в СЧ, но в серьгзных стохастических вычислениях требуется более быстрый, дешгвый и универсальный метод получения случайных переменных ([3]). Эту потребность могут удовлетворить числа, генерируемые в естественных флуктуационных процессах, которые однако обладают рядом недостатков. Для такого подхода также отсутствует литература с описанием способов реализации генераторов. Статья призвана восполнить этот пробел. Сравнение ПСЧ и естественных СЧ Основные преимущества ПСЧ: 1) удобство благодаря простому вызову программы; отсутствие специальной схемы. Это особенно удобно при коротких прогонах программ. Это преимущество сохранит свог значение и в дальнейшем; 2) повторимость числовых последовательностей при отладке программ; 3) предопределгнная статистика. Хотя это вполне нормальный момент, многие пользователи были удивлены, когда им случалось столкнуться с задачей, некоторым образом разгадывающей детерминированную псевдослучайную программу, или с задачей, когда размерности непостоянны в конечной длине цикла. Основные недостатки ПСЧ: 1) отсутствие универсальности. Как упоминалось выше, нет полной уверенности в успехе при решении всех проблем. Хотя это в некоторой степени верно для всех случайных последовательностей, естественные СЧ предоставляют, по крайней мере, шанс получить полностью универсальные и несмещгнные переменные; 2) сложные вычисления требуют времени и памяти. Вычисления в ПСЧ-программах часто более сложны, чем сама задача. Большинство ПСЧ-методов используют умножение, тогда как , например, при решении уравнения Лапласа путгм случайных блужданий требуется только простое увеличение или уменьшение счгтчиков; 3) отношение скорость/стоимость очень низкое. Всегда требуется более 1 машинного цикла, и стоимость растгт пропорционально количеству используемых случайных переменных. СЧ, генерируемые при помощи естественных флуктуационных процессов, устраняют эти недостатки, но их статистика должна контролироваться, и для генерации требуется специальная схема. Другая проблема, часто упоминаемая в литературе, неактуальна благодаря ПСЧ - это проблема повторяемости. Когда же задача готова для серьгзного прогона, можно использовать более эффективные, быстрые и универсальные естественные СЧ. Проблема контроля статистики достаточно насущна, особенно когда используются стабильные источники шума с полосой частот до нескольких десятков ГГц [4]. Разработаны быстрые статистические тесты, о которых рассказано в [6]. Двоичные СЧ и равномерное распределение Хотя это и может быть первой мыслью, прямое аналого-цифровое преобразование шумовых сигналов обречено на провал по двум причинам: 1) ГСЧ ограничен выработкой распределения СЧ, соответствующего амплитудному распределению определгнного используемого источника шума; 2) распределение зависит от долговременной стабильности источника шума. Уделим основное внимание не источнику СЧ, а самим СЧ. Это допустимо, если мы имеем соответствующие статистические тесты для чисел [6] и для базового источника шума используем такую простую характеристику как пересечения нулевого уровня. Для простоты можно работать только с двоичными числами, поскольку основание числа не влияет на случайность. Любое распределение СЧ можно получить из группы источников независимых битов, причгм для каждого источника p(1)=p(0)=1/2. В статистике хорошо известно, что из такого равномерного распределения можно получить любое вероятностное рспределение. Для таких преобразований существует аппаратное [10] и программное обеспечение (ПО может привести к потере выигрыша по скорости, достигаемого при использовании естественных СЧ). Универсальный ГСЧ Из вышесказанного можно заключить, что если имеется массив независимых случайных битов, то любая другая операция над этими переменными для удовлетворения требований конкретного применения является полностью детерминированной. Это обобщение и ослабление недетерминированных факторов очень важно при создании ГСЧ. Если мы можем создать простую группу аналоговых источников шума и однобитных кодеров (в действительности, простых квантователей уровня) (рис.1), то основная часть задачи выполнена. здддддј зддддддддддддддј ° шум цдд>° квантователь цдд> случайный бит - 1 юддддды юдддддддддддддды здддддј зддддддддддддддј ° шум цдд>° квантователь цдд> случайный бит - 2 юддддды юдддддддддддддды ............................................... здддддј зддддддддддддддј ° шум цдд>° квантователь цдд> случайный бит - n юддддды юдддддддддддддды Рис.1. Массив случайных битов. В сущности необходимо рассмотреть один элемент группы, так как все элементы (шум/квантователь) идентичны. Каждый источник шума/квантователь независим от других, и квантователь просто выдагт "1", если шум превышает некоторый уровень, и "0" - в противном случае. В общем случае проблема "источник шума/квантователь" трудна. Однако для очень важного специального случая - гауссова белого шума (ГБШ) - многие аспекты проблемы решены. Вполне допустимо ограничить рамки статьи рассмотрением только ГБШ ввиду его широкой распространгнности в природе. Мы получим возможность использовать ГСЧ как инструмент исследований других типов случайных процессов, основываясь на опыте генерации СЧ из гауссовых процессов. Для создания элемента "источник шума/квантователь" необходимо знать: 1) среднюю амплитуду/точку смещения квантователя; 2) граничные частоты энергетического спектра белого шума/ максимальную скорость выборки (полагаем, что энергетический спектр предварительно выравнивается, или "выбеливается" [1] в полосе пропускания); 3) среднеквадратический шум/ гистерезис квантователя. Средняя амплитуда/ точка смещения квантователя Все 3 параметра источника шума - среднее, среднеквадратическое и полоса частот - легко определяются при помощи лабораторного оборудования ([1] - хороший пример), и после завершения разработки их не принимают во внимание, поскольку статистика контролируется. Это согласуется с нашей политикой - не рассматривать СЧ относительно схемы, если используются статистические тесты. Если же статистические тесты не дают удовлетворительных результатов, они, тем не менее, предоставляют полезную информацию для исправления схем "источник шума/квантователь" [6,7]. Единственное ограничение состоит в том, что шум должен быть стационарным в среднем и в автокоррекции, иначе требуется регулировка схемы. Простое вычисление показывает, что точка смещения квантователя может быть установлена по среднему значению распределения амплитуды шума для выполнения условия p(1)=p(0)=1/2. Это можно получить, решая относительно Vt соотношение p(V)dV = 1/2, (1) где p(V) - функция плотности вероятности шума, а Vt - точка смещения. Хотя для гауссова случая решение простое, для произвольных p(V) решить (1) весьма сложно. Кроме того, Vt необязательно удовлетворяет условию Vt = среднее = V p(V)dV для произвольных p(V). Граничные частоты/ максимальная скорость выборки Хотя о белом шуме можно сказать, что он имеет равномерную среднюю мощность на всех частотах, от 0 до бесконечности, любой реальный источник шума ограничен по частоте. Возникает вопрос: как быстро мы можем делать выборку из белого шума с ограниченной полосой, чтобы последовательные числа были некоррелированными. Так как мы планируем установить точку смещения по среднему значению шума, то в отношении уровня срабатывания квантователя, или точки смещения, мы сталкиваемся со знаменитой проблемой пересечения нулевого уровня. Эта проблема - цель многих исследований, и, к счастью, Райс [8,9] решил касающуюся нас часть этой задачио выборке случайного бита, квантуемого из шумового сигнала. Райс получил отношение для среднего числа пересечений нулевого уровня в секунду, No, для гауссова случайного процесса. __ No = 2 [ f G(f)df G(f)df] , (2) где G(f) - функция спектральной плотности мощности шума. В нашем случае G(f)=К - константа, а пределы интеграла - это нижняя и верхняя граничные частоты полосы шума fa и fb соответственно; G(f)=0 для ffb (т.е. белый шум пропускается через идеальный полосовой фильтр - рис.2). G(f)° ° ° К °д д д д д здддддддддддддддддддддддј ° ° ° ° ° ° ° ° ° юддддддддддадддддддддддддддддддддддаддддддддд fa fb f Рис.2. Идеальный белый шум с ограниченной полосой частот (3) Для широкополосного шума fb>>fa и (3) сводится к: No = (2/ 3)*fb = 1.155*fb (4) Поскольку (4) включает пересечения в обоих направлениях, то можно разделить на 2 для получения среднего числа импульсов Np в секунду из квантователя. Np = (1/ 3)*fb = 0,577*fb. Для реальной полосы шума мощность не срезается резко на fb. Частоты, превышающие fb, хотя и ослабленные по амплитуде, дают вклад в число пересечений уровня, поэтому наша оценка Np приблизительна. Для того, чтобы связать Np со скоростью, на которой могут выбираться случайные биты, рассмотрим битовые переходные вероятности p(1/1)=p(1/0)=p(0/1)=p(0/0), которые эквивалентны на квантуемой выборке автокорреляции на аналоговом сигнале. Условие случайности предполагает нулевую автокорреляцию по всем временным интервалам или равные переходные вероятности между дискретными битовыми выборками, разделенными произвольным временным интервалом. При интенсивном использовании верхних частотных границ источника шума для получения максимальной скорости выборки надо рассматривать соседние битовые выборки. Слишком быстрая выборка означает, что произойдет перевес переходов (1/1) и (0/0), так как будет сделано слишком много выборок прежде, чем выход квантователя сделает переход (1/0) или (0/1). Это означает максимум 4 выборки из одного (1/0) или (0/1) перехода за один случайный цикл с возвратом в этот переход. Поскольку имеются два перехода за случайный импульс (два пересечения нуля), то должно быть не более двух выборок за импульс. Следовательно, максимальная средняя скорость выборки fs равна __ ___ fs = 2Np = 1,155*fb, где fb>>fa. Среднеквадратический шум/ гистерезис квантователя Условия стабильности требуют, чтобы триггер Шмидта, компаратор или любой реальный квантователь имел небольшой гистерезис возле точки смещения (рис.3). вых. напряжение ° ° ° "1"°д д д д д здддддбддддддддддд ° ° ° ° v ^ ° ° ° "0"цддддддддддаддддды юдддддддддддддддддддддддддддддддддддддддддддд Vd Vu вх.напряжение Рис.3. Гистерезис квантователя Гистерезис вызывает два вопроса: 1) где выбирается точка смещения квантователя; 2) что влияет на скорость выборки. Аналитически ответить на эти вопросы очень сложно. Была проделана работа для пересечений произвольных уровней гауссовым процессом, но не для двух уровней, особенно когда два уровня пересекаются особым образом, вызывая изменение выхода квантователя. Например, один уровень может пересекаться несколько раз без пересечения второго уровня и изменения выхода, либо один уровень может пересекаться, после чего сигнал некоторое время изменяется до пересечения второго уровня и изменения выхода. Хотя проблема гистерезиса остается академически опасной, ее можно обойти на практике. Прстой способ увеличения среднеквадратического шума (т.е. простое усиление шумового сигнала) значительно уменьшает проблему гистерезиса, если он невелик. Для симметричного распределения типа гауссова положение среднего полупути между Vu и Vd обеспечивает p(1)=p(0)=1/2. Vd и Vu пересекаются на равном основании, и флуктуации, которые изменяются в разных направлениях между Vu и Vd без пересечения уровней и формирования выходного импульса, полагаются одинаково распределенными. При сочетании высокого среднекадратического значения и малого гистерезиса лишь некоторые флуктуации не пересекут и Vu и Vd. На рис.4 показаны результаты лабораторных испытаний, доказывающие это положение. средняя ° частота ° выходных ° __ импульсов°д д д д д д д д д д д д д д д Np для идеальной полосы квантова-° шума теля ° ° ° гистерезис Н3>Н2>Н1 юдддддддддддддддддддддддддддддддддддддддддддд среднеквадратический шум Рис.4. Типичная зависимость частоты импульсов квантователя от среднеквадратического шума с гистерезисом в качестве параметра В заключение ответим на вопросы о смещении квантователя, среднем значении шума и скорости выборки: 1) гистерезис квантователя должен быть настолько мал, насколько позволяют условия стабильности; 2) среднеквадратический шум длжен быть высоким. Нужное значение можно определить так: уровень Np падает при возрастании среднеквадратического значения; 3) среднее значение шума находится для напряжения смещения Vb, где Vb=(Vu+Vd)/2; 4) максимальная средняя скорость выборки уменьшается очень мало или совсем не уменьшается при малом гистерезисе и высоком среднеквадратическом значении шума. Логические схемы На каждом выходе квантователя требуется вентиль AND и триггер (рис.5). выборка ддддддддддј здддддј зддддддддддддј ° зддддд здддддј ° шум ° °квантователь° цдѓ °тр 1° ° цдддѓ цдедѓ ° 0° случайный бит 1 юддддды юдддддддддддды ° юддддд юддддды здддддј зддддддддддддј ° зддддд здддддј ° шум ° °квантователь° цдѓ °тр 1° ° цдддѓ цдедѓ ° 0° случайный бит 2 юддддды юдддддддддддды ° юддддд юддддды .......................... ..... ........................ здддддј зддддддддддддј ° зддддд здддддј ° шум ° °квантователь° юдѓ °тр 1° ° цдддѓ цдддѓ ° 0° случайный бит n юддддды юдддддддддддды юддддд юддддды Рис.5. Вентиль AND предотвращает переходы битов в момент выборки, а триггер хранит значение бита в момент выборки. Функционирование элемента AND (или другого элемента запрета) не вызывает сложности, но выбор триггера требует внимания. Для обеспечения скорости выборки fs=1,155*fb можно использовать JK- или D-триггер, а Ттриггер обеспечит p(0)=p(1)=1/2, проигрывая в скорости выборки. JK- и D-триггеры обеспчивают высокую скорость выборки, потому что они сохраняют случайный бит, действуя как ступень сдвигового регистра, сдвигая состояние случайного бита. Таким образом, используется запомненный образ случайного бита. Т-триггер обеспчивает p(0)=p(1)=1/2, потому что он действует как одноступенчатый двоичный счетчик, переключаемый одним из переходов (0/1) или (1/0). В качестве счетчика переходов Т-триггер только регистрирует, было ли число изменений состояния между выборками четным или нечетным, и не показывает ошибочную вероятность "1" или "0" на выходе квантователя. В этом качестве Т-триггер изменяет состояние в 2 раза реже, чем случайный бит, поэтому максимальная скорость выборки делится на 2: fs = 1,155*fb/2 = 0,577*fb. Рекомендации по обеспечению некогерентной работы Даже без внезапного выхода из строя одного из схемных элементов ГСЧ может отказать в трех случаях: - в случае позиционной зависимости между битовыми датчиками; - в случае зависимости от предыстории бита (битов); - при генерации смещенных битовых вероятностей. Все три типа неблагоприятных исходов могут быть вызваны разными видами взаимного влияния. Перекрестные помехи или вляние по излучению между источниками битов или между выбираемыми импульсами может вызвать позиционную зависимость. Если влияние когерентно (например, несущие радиопередатчика или фон переменного тока 60 Гц), то биты могут быть зависимы по предыстории. Каждый из этих факторов может влиять и на вероятности битов. Для предотвращения взаимного влияния рекомендуется: 1) развязывать по питанию датчик битов и устройство выборки; 2) использовать хорошо фильтрованные источники питания, мощные и короткие провода питания; 3) использовать электромагнитное экранирование; 4) обеспечить развязку источника шума и триггеров, устанавливая импедансные схемы между источником шума и квантователем и на выходах триггеров (типа эмиттерного повторителя)(рис.6). выборка ддддддддддј здддддј зддддддддддддј ° зддддд здддддј ° шум ° °квантователь° юдѓ °тр 1° ° цдд ° цдддѓ ° 0° юддддды юдддддддддддды юддддд юддддды Рис.6. Развязка при помощи эмиттерных повторителей Для источника шума это решит проблему нагрузки и ослабит обратную связь от квантователя и импульса выборки. Для триггера это ослабит обратную связь от компьютера выборки и других датчиков битов через компьютерные схемы. Сдвиг характеристик компонент также может вызывать неблагоприятные исходы в статистике СЧ. Изменение точки смещения квантователя может вызвать сдвиг битовых вероятностей, однако смещение можно регулировать автоматически по результатам статистических тестов или путем использования Т-триггера. Зависимость от предыстории может возникнуть при очень высокой скорости выборки. Скорость выборки также можно автоматически регулировать по результатам тестирования вероятностей перехода. Заключение СЧ, генерируемые при помощи естественных флуктуационных процессов, выигрывают по скорости и универсальности. Обобщенный ГСЧ можно построить на основе группы идентичных независимых источников шума/квантователей, при этом аналоговым источникам шума уделяется незначительное внимание. Среднеквадратическое значение шума должно быть высоким; должна обеспечиваться широкая полоса частот fb-fa. Гистерезис квантователя должен минимизироваться, и для ГБШ он долженг быть смещен на среднее значение шума; выборка производится со скоростью не более 1,155*fb. Необходим вентиль AND для блокировки битовых переходов в момент выборки и триггер для запоминания бита на момент выборки. Т-триггер поможет уменьшить смещение битовой вероятности, но вдвое уменьшает скорость выборки. Литература: 1. Bendat J.S., Piersol A.G. Measurement & Analysis of Random Data. N-Y, Wiley, 1966. 2. Chambers R.P. Random-number generation on digital computers// IEEE Spectrum, v.4, pp.48-56, Feb 1967. 3. Gaines B.R. Stochastic computer thrives on noise//Electronics, v.40, Э14, p.72, July 10, 1967. 4. Johnson H., DeRemer K.R. Gaseous discharge superhigh frequency noise sources//Proc. IRE, v.39, pp.908-914, Aug 1951. 5. Lansdown W.D. Random walk solution of Laplace's equation. Ph. D. diss., 1964. 6. Murry H.F. High speed probability tests on random number sequences//Proc. Region III IEEE Conf., 1968. 7. Murry H.F. Generation of random numbers from natural fluctuation phenomena. Ph.D. diss., 1966. 8. Rice S.O. Mathematical analysis of random noise, P.I & II// BSTJ, v.23, pp.282, 1944 July. 9. Rice S.O. Mathematical analysis of random noise, P.III & IV// BSTJ, v.24, pp.46, 1945 Jan. 10. Warfield J.N. Synthesis of switching circuits to yield prescribed probability relations//Proc. 6th Ann. IEEE Symp. on Switching Theory & Logic, 1956. quences//Proc. Region III IEEE Conf., 1968.