автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.05, диссертация на тему:Вычислительные средства для статистического моделирования

Р Г Б ОД

- 8 МАЙ 1995

На правах рукописи

ГЛОВА ВИКТОР ИВАНОВИЧ

ВЫЧИСЛИТЕЛЬНЫЕ СРЕДСТВА ДЛЯ СТАТИСТИЧЕСКОГО МОДЕЛИРОВАНИЯ

Специальность 05.13.05 - элементы и устройства вычислительной техники и систем управления

Автореферат диссертации на соискание ученой степени доктора технических наук

Казань 1995

Работа выполнена в Казанском государственном техническом университете им. А. Н. Туполева

Официальные оппоненты :

академик международной академии информатизации, доктор технических наук Ю Н. МЕЛЬНИКОВ доктор технических наук В.П. ДАНЧЕЕВ доктор технических наук Г.И- ИЛЬИН

Ведущая организация :

Казанский научно - исследовательский институт радиоэлектроники.

Завита состоится " /л&> Ъ_1Ж г. в ^ часов

на заседании диссертационного совета Д 063.09.02 Казанского государственного технического университета по адресу : 4200111,

г. Казань, ул. К. Маркса, 10, МТУ.

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан ". и " ^и^ш_ 1ддд г

Ученый секретарь специализированного совета

кандидат технических наук

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. В наше время практически нет отраслей науки и техники, гле не применялись бы методы , связанные со статистическим моделированием или испытанием . Это методы имитационного моделирования, Монте-Карло, зашиты информации, формирования случайных и псевдослучайных сигналов и т.п. Все более широкое применение они находят и в нетехнической сфере: в медицине, демографии , социологии , биологии и др.

Сложность решаемых задач этими методами быстро растет и существенно опережает рост производительности вычислительных систем СВС) Сувеличивается размерность, повышается требуемая точность и т.п.). Эти же причины ведут к росту стоимости решения задач детерминированными методами. Статистические же методы довольно просты для реализации.

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

Именно поэтому во многих отраслях науки разрабатываются проблемно ориентированные системы СПОС) на основе функционально ориентированных СФОС): процессоров, сопроцессоров, транспьютерных систем и других аппаратных средств . В системах статистического моделирования СССМ) имеется множество фундаментальных работ как по методам, так и по средствам. Решению таких задач посвящены работы отечественных, и зарубежных ученых: Аманна H.A., Бакановича Э.А., Бусленко Н.П.. Бухараева Р.Г., Володина 'Л.Н. .Гавела Я., Гладкого B.C., Голенко Д.И., Гондарева В.П., Да-зильченко И. А., Данчеева В. П., Добриса Г. В., Доценко В. И., Ермакова С.М., Живетиной Т.М., Захарова В.М.. Карасова А.С.-Б., Ки-эьянова Б. Ф., Кнута Д., Корна Г., Кузнецова В. М., Левина В. К..

I

Леусенко А. Е.. Лоренца А. А., Марчука Г. И. , Мельникова Ю. Н. , Михайлова Г. А. , Мороза IT. А., Морозова А. М., Орлова М. А., Песо-иина В.А., Растригина Л.А., Рудоманова В.И., Романкевича A.M., Свердлшса А. Н., Сергеева' Н. Н., Соболя И. М., Столова Е. Л., Таус-ворта Р., Тетерича Н.М.. Урецкого Я.С., Фараджева Р.Г., Федорова Р. Ф., Хамитова Г. П., Чабдарова I. М., Четверикова В. Н., трейдера Ю. А., Яковлева В. В. и др.

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

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

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

Указанные недостатки приводили к тому, что имелись лишь отдельные блоки для специальных систем: приставки,блоки и элементы к ЭВМ. Практически не разрабатывались вопросы архитектур и их элементов высокопроизводительных аппаратно программных ФОС, не осуществлялась проработка системных, методологических,методических вопросов, теории и методов построения модулей всего технологического процесса статистического моделирования. В связи с этим возникает актуальная проблема, решаемая в диссертации.

Цель работы. Разработка методов и создание средств высокопроизводительных функционально ориентированных вычислительных систем статистического моделирования, включающие теоретическое обобщение и' разработку элементной базы, новых аппаратно реализуемых методов и алгоритмов, доведение их до инженерных методик проектирования и создания серийно способных устройств.

Для достижения цели необходимо провести исследования и решить следующие задачи :

- исследовать современные методы , структуры и блоки ССМ , а также определить критерии- их построения ;

- произвести обобщение методов и структур и разработку генераторов с равномерным и заданным распределением случайных чисел и представлением информации , совместимым с ВС ;

- разработать методы построения технолотачных ГРРСЧ на современной элементной базе ВТ ;

- разработать методы и алгоритмы преобразователей стохастических потоков ;

- исследовать архитектурные элементы ССМ ;

-.исследовать возможные направления развития методов , блоков и архитектур ССМ .

Научная новизна .

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

В процессе исследований получены следующие новые научные результаты . выносимые на защиту .

1. Проведен системотехнический анализ ССМ с точки зрения ФОС , на основе которого определены систематизированный набор задач и архитектурные требования к структурным элементам и предложены критерии их построения .

2. Проведено обобщение и систематическое исследование методов генерирования равномерно и произвольно распределенных случайных и псевдослучайных чисел на основе нелинейных динамических систем со стохастическим аттрактором и различным представлением информации, предложена их логическая структура. Предложены, исследованы и разработаны методы и устройства ГРРСЧ с использованием распределенных источников шума: микрошумов переключательных элементов ИС С ГСЧ разрабатывались двух типов: со стохаским аттрактором и с квазидетерминнрованными процессами).

3. Проведена систематизация аппроксимационных методов ГПЗ и предложен метод сплайн-аппроксимации с суперпозицией порядковых статистик и наименьшим количеством узлов. Предлагается обобщение метода условных вероятностей непрерывных, сингулярных и дискретными распределений. Впервые предлагается как перспективное направление разработка ГШ на основе нелинейных систем. Предложены

3

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

4. Впервые предлагается использовать методы оптимального хранения и поиска информации в базах данных для организации информации в газ и гсч .

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

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

7. Предложена и проведена архитектурная увязка блоков для построения ФОС С сопроцессоров и процессоров ).

ПРАКТИЧЕСКАЯ ценность состоит в создании, на основе предложенных математических моделей, методов, методик, алгоритмов, аппаратных, программных и микропрограммных средств для высокопроизводительных ФОС, архитектурно совместимых с ВС; впервые проведена полная разработка всех блоков и системных вопросов, сопроцессоров, процессоров и внешних устройств; разработаны методики практического проектирования ГРРСЧ на интегральных схемах (матричных кристаллах, микропроцессорах, ПЛИСах FGLA и т.д.), также БИС и аппаратуры контроля; разработана, предложена в качестве проекта ГОСТа и апробирована система тестирования ГСЧ и ГПСЧ; разработана программная поддержка статистической обработки информации нетрадиционными методами (с использованием генерации случайных чисел) для экспертной медицинской системы .

РЕАЛИЗАЦИЯ результатов. Разработанные методы , алгоритмы и устройства использовались: в Казанском НИИ радиоэлектроники в серийном устройстве ГСЧ для защиты информации, а также БИС ГСЧ и БИС его контроля аа базовых матричных кристаллах для тех же целей; в серийном "Устройстве ввода случайных чисел" ЕС 6903 (устройство фактически являлось терминальным функционально ориентированным процессором) и сопроцессоре статистического моделирования для терминальной ЭВМ ЕС 1007 (архитектура, структура, блоки, программная и микропрограммная поддержка, языковой интерфейс),

выпускавшимися Казанским НПО ВС; в сопроцессоре для ПЭВМ типа PC XT/AT Сс аппаратной и программной поддержкой в.языковым :интер-. фейсоы), разработанном в Казанском филиале института проблем информатики РАН по конкурсной теме РАН; в проекте ГОСТа ло системе тестирования генераторов ГСЧ и ГПСЧ); в пакете программ для ста- .тнстаческой обработки информации, использующимся в учебном про-мцессе в Казанском государственном техническом университете по кафедре ЭВМ;. в- программной системе статистической обработки информации нетрадиционным методом Сс использованием генерации случайных- чисел) для экспертной медицинской системы, работающей в .ряде медицинских учреждений г. Кдоаяи .

, чТехнические решения защищены 10 авторскими свидетельствами.

Работы проводились по госбюджетным и хоздоговорным темам, по темам и- договорам с Казанским НИИ радиоэлектроники, по комплексным договорам с.НИИ ВС Казанского НПО ВС по теме: "Исследование и разработка специализированных процессоров ЭВМ С Ряд 2 и /Ряд 3) для .сети ЭВМ"; по теме, утвержденной Минвузом СССР на 1981 - 1985 годы, приказ >N 1236 от 29-12.81; по конкурсным те-_ мам РАН РФ:. "Сопроцессорные средства ПЭВМ для статистического . моделирования и обработки информации" и "Методы и средства криптографической заашты информации от несанкционированного использования в ПЭВМ и ЛВС".

АПРОБАЦИЯ работы . Основные положения и результаты докладывались и обсуждались, на Всесоюзной школе-семинаре "Генерирование случайных функций" Сг. Иркутск, 1973г.); II Поволжской конферен-. ции по автоматическое управлению. С г. Казань. 1974 г.); Республиканской научно-практической-конференции "Пути повышения эффек-. тивности АСУ Сг. Казань, 1976 г.); V Всесоюзной конференции "Дальнейшее развитие аналоговой и:аналого-цифровой техники" Сг. Москва,. 1977 т-); VII Всесоюзном симпозиуме по проблеме избыточности в информационных системах Сг. Ленинград. 1977г.); .1 Всесоюзном симпозиуме "Вероятностные вычислительные методы и средства" Сг.Москва, 1978 г.); Всесоюзной школе-семинаре по-вероятностным . автоматам Сг.: Славск, 1978 г.); на II и III Всесоюзных симпозиумах по вероятностным автоматам Сг. Тбилиси, 1975 г., г. Казань, 1983 г.); IV Всесоюзном симпозиуме "Проблемы создания преобразователей формы информации" Сг. Киев, 1980 г.); Всесоюзной научно-технической конференции "Вероятностные методы и средства" Сг. Новгород, 1983 г.); VII Всесоюзной школе-семинаре "Вероятностные автоматы и их приложения" Сг.Киев. 1984 г.); на Всесоюзных школах-семинарах по вероятностным автоматам С1972-1980г.г.); Респу-

5

бликанской научно-практической конференции Сг. Казань, 1983г.); Межреспубликанской научно-технической конференции "Вероятностные автоматы и их приложения" Сг. Тбилиси, 1986 г.); XIV Научно-технической конференции молодых ученых и специалистов ЕрНИИММ Сг. Ереван, 1986 г.); на VI Всесоюзном межотраслевом симпозиуме Сг. Новосибирск, 1986 г.); Республиканской конференции "Повышение эффективности использования мини- и микро-ЭВМ в автоматизированных системах" Сг. Казань, 1988 г.); Всесоюзной научно-технической конференции "Компьтерные методы исследования проблем теории и техники передачи дискретных сигналов по радиоканалам "Сг.Москва, 1990г.); научно-технической конференции "Проблемы разработки и внедрения микромодульных систем в ЭВМ" Сг. Казань, 1990 г.); научно-техническом семинаре "Программное обеспечение ЕС ЭВМ.ГОВМ и комплексов АРМ" Сг. Минск, 1990 г.); научно-технической конференции "Научный потенциал вузов-программе, "Конверсия" КГТУ" Сг. Казань, 1992 г.); на VIII Всесоюзном совещании по методам Монте-Карло в вычислительной математике и математической физике Сг. Новосибирск, 1991 г.); на межреспубликанской конференции "Современные проблемы алгоритмизации" Сг. Ташкент, 1991 г.); на ежегодных конференциях Казанского авацяонного института; на конференциях Казанского научного центра РАН и на научно-технических советах ИЛИ РАН и Казанского филиала ИЛИ РАН С1990- .1992 гг.).

ПУБЛИКАЦИИ по работе. Результаты опубликованы в 80 печатных работах, 20 отчетах по научно-исследовательским темам , получены 10 авторских свидетельства на изобретения .

СТРУКТУРА и объем работы. Диссертация состоит из введения, 7 глав, заключения, приложений, списка использованной литературы. Объем работы : 365 с. основного машинописного текста, 27 рисунков , и 6 - таблиц .

СОДЕРЖАНИЕ РАБОТЫ

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

Первая глава "Проблемы построения аппаратно-программных средств статистического моделирования" посвящена анализу технологического процесса решения задач ССМ на основе функционального графа. Проводится классификация этих систем и определяются критерии их разработки. Для каждой выделенной классифи-6

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

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

В качестве критериев предлагается , как и принята в ВС, среднее время решениия задач

= Бчл

1=1

или производительность Л = Т-1, где т( - среднее время выполнения 1-ой операции моделирования, р.-вероятность обращения к ней, I =1 ч- п. Необходимость создания специальных средств повышения производительности тем более рациональна , чем больше р.т..

МКС и ИС характерны использованием случайной величины £ с требуемой функцией распределения, получение которой осутцествляет-' ся преобразованием « = рСх) конструктивно заданных равномерно распределенных случайных величин а, а е (0,1). После этого вычисляются некоторые параметрические или непараметрические оценки. В результате выделяются этапы: подготовка исходных данных; генерирование равномерно распределенных случайных чисел; преобразования для получения заданного закона распределения; выполнение дополнительных преобразований в соответствии с проблемной областью; статистическая обработка.

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

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

Системотехнический аспект проблем приводит к необходимости

7

исследования архитектурных особенностей и методов построения ФОС ССМ : определить системы функций , команд и адресации ; способы связи Синтерфейсы) между компонентам!! ; систему представления информации Счисла с фиксированной и плавающей точками, целые короткие и длинные форматы и т. п.); способы и систему управления (жесткое, микропрограммное и пр.) ; способы взаимодействия с универсальными ВС и степень универсализации.

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

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

Вторая глава 2 "Генерирование равномерно распределенных случайных чисел " посвящена разработке ГРРСЧ, архитектурно и информационно увязанных с ВС и имеющих современную цифровую элементную базу .

Отсутствие методологического единства ГРРСЧ привело к появлению множества теоретически равноценных методов, например, пересчет детерминированной последовательности импульсов за случайный интервал времени или их случайного количества за детерминированный интервал и т.п. При этом источниками шумов в большинстве случаев являлись специальные генераторы (шумовые диоды) и лишь иногда внутренние шумы транзисторов. Для ССМ это не перспективно, т.к. компоненты системы не имеют методическую, архитектурную, конструктивную, технологическую и элементную совместимость с ВС. Действительно, например, практически все аппаратные генераторы формируют числа с фиксированной точкой .

Более единую методологическую основу стохастических генераторов (СГ) может дать теория нелинейных динамических систем (НДС) со "странным" аттрактором. Различие ГПСЧ и ГСЧ заключается в использовании последними физических источников шумов (плохо предсказуемых или случайных процессов) и преобразованием их в дискретную величину. Статистические характеристики таких ГСЧ неустойчивы по отношению к внешним воздействиям и поэтому применяют дополнительные средства для их "улучшения" (усиления стохас-тичности), т.е. строят комбинированные схемы. Таковыми являются все известные физические СГ и ряд ГПСЧ. В качестве выравнивающих используются симметрические булевы функции. (Автор исследовал .8

такие функции).

Известные линейные ГПСЧ имеют модели :

уС1+1) = 2-уШ * РСуС«) Стоё 1)

или

уС1+1) =0.3-уС» * РСуШ) Стоё 1),

где ГСуШ) - стохастгсшрующая функция. Для ускорения затухания корреляционной характеристики до 0 используют точечное отображение вида :

уС1+1)=2куСО Сшос1 1) к = 2,3.4,-.. , что соответствует многотактному сдвигу . Б этом случае также получается марковская цепь с переходными вероятностями, определяемая! длинами интервалов у = 2~( к+1>. Модель позволяет генерировать числа с фиксированной точкой . Равноценной является модель со счетчиком I

+ V«*! и)

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

Р1/' •= -¿г «ФС" "чЬ^ .

где р С]) - характеристическая функция решетчатой величины .

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

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

Предлагается набор критериев для оценки выбираемых решений: конструктивные, технологические, по модели и временные. Так, например, исполнение может быть в виде: функциональных ячеек Сих блоков) на многослойной печатной плате; гибридной БИС; микросборки или ИС, БИС. Проектирование ГСЧ на основе интегральных и программируемых логических схем СБМК, ПЛИС или помимо общих накладывает специфические ограничения: реализуемость в цифровой схемотехнике; возможность применения существующих САПР; реализуемость на элементах из ограниченного состава библиотеки элементов БМК, ПЛИС или ГИ.А; использование одинакового номинала источника питания; возможность контроля и диагностики неисправностей ИС соответствующими методами ВС.

Выделяются ГСЧ с локальными и распределенными источниками шума СЛШ и РИШ ). ГСЧ с ЯШ наиболее традиционны, они проектируются как многоканальные схемы с выравнивающими функциями или мультиплексорами. В работе проводится их анализ.

ГСЧ с РЩ рассматривались двух типов; со стохастическим аттрактором и с квазидетерминированными процессами. В первом типе используется структура, подобная линейным ГПСЧ, но в обратной связи используются переключательные элементы со случайными временами задержки Синверторы , сумматоры по mod 2). Математическая модель для выходной последовательности имеет вид

где |ЗС1-т,) - значение 1-го элемента задержки , величины т. -случайны и определяются параметрами схем. Выбор вида математической модели осуществлялся из соображений соответствия структуры простому стохастизатору ГГОЧ . Стохастический автогенератор и его разновидности полностью реализуемы на цифровой элементной базе и использованы в ряде промышленных разработок (разрабатывались на отдельных ИС и на микропроцессорных секциях). Поскольку отображение имеет два устойчивых состояния, то иногда наблюдается срыв колебаний и для его компенсации требуются дополнительные средства.

Более устойчивы схемы с квазидерминированными процессами 7)Ш=1Л1.,£. ^ШЗ, где 11-некоторая детерминированная функция; ГШ - векторы случайных параметров и флюктуационных воздействий соответсвенно. В качестве генераторов квазидерминированных процессов (ГКДГО используются цепочки асинхронных элементов задержки, в которых происходит нарастание ("накапливание") дисперсии: Б tQj)=vJ -о^, где и о^ - соответственно число элементов и их дисперсии в ^цепочке. комбинируя количество цепочек и стохастизаторы синтезируем ГСЧ на цифровой элементной базе.

Впервые предложено и проведено исследование ГРРСЧ с плавающей точкой. Будем считать , что случайная величина 7) в форме с плавающей точкой нормализована и п € (0,1) .

Теорема 2.1. Для того, чтобы тз имела равномерное распределение, необходимо и достаточно удовлетворение следующих услог

ВИЙ :

1.Случайная величина у, формирующая порядок, должна иметь распределение РСу)=0.5 Оу(О-1) , у € <-(2к-1)-=- 0 ), к - разрядность, а 0 - основание порядка.

л

(mod 2),

2. Случайная величина х, формирующая мантиссу, должна иметь равномерное распределение в (0.5ч 1-2-т).

3. Случайные величины х и у должны быть независимы .

При 0 = 2 распределение порядка имеет вид Р(у) = 2У~' или , если у е (0 + 2к -1) , то Р(у) = 2-у"4.

Реализующая схема распадается на две: ГРРСЧ с фиксированной точкой, генерирующей мантиссу, и генератор случайных целых чисел для формирования порядка. Формирование порядка может быть параллельным и последовательным.

Теорема 2.2. Система минимальных булевых функций преобразователя вероятностного автомата для генерирования порядка имеет . вид: а

Г (2 2 2 )=2 и о ' а*' • • "V '

Г, (г, .2.....2.) = 2.и • 2. • • • г.1-1 • 2. ,

I 1 а' к I I I I

причем сложность этой функции для максимального значения порядка 1 равна = 2(1 - 2)+ 1 , здесь Ссг1,ая.... .о,,) значения кодов

переменных г1 ,гг.....\

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

7 - а _ Д1*1 _ I о**1 (1- а)2 (1-а)г 1- а

а = 0.5 , г - пах порядок или для больших г Т = 2. Аналогично для дисперсии для больших I О > 16) ^ = 2 .

Теорема 2.3. Для всякой решетчатой случайной величины ^ можно найти стохастическую бинарную последовательность, параметры которой однозначно определяются распределением Р(?г). Условная вероятность определится следужим образом-.

У Р1С,(г(_____г, .1)

ГГ.2 Д)е V

РССгСг )=1|г .....2 )]=-' ^ --

1 1 1-4 У .....г, )

"М -4-1

В работе исследуются методы генерирования равномерно распределенной случайной величины в заданном интервале .

Изучаются также погрешности получения заданного распределения, которые возникают из-за: ограничения количества разрядов порядка; отклонения от равновероятости знаков "0" и "1" и корреляции в потоке; зависимости порядка и мантиссы. Определяется абсолютная погрешность функции плотности вследствии ограничения порядка Д4=|*СхЗ-«*Сх)|. где и(х) - точная, а «*Сх) - реальная плотности, тогда погрешность математического ожидания составит

Д,п= /х «Сх)с1х = 2 а для г-го центрального момента

^ = 2_(г+4>С-1) Г+1 [ а-г-1-')^1-! ]

Третья глава "Генераторы случайных чисел с заданным распределением" посвящена разработке методов и устройств, архитектурно совместимых с ВС.

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

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

В широко распространенных аппроксимационных методах моделирования используются либо суперпозиции простых распределений, либо полиномиальные сплайны, либо смешанные методы. Один из таких методов - аппроксимация функции плотности **Сх) по оси х. Причем, если выбрать VI. Дх^= Дх = то метод заключается в формировании щ-к старших разрядов, а оставшиеся к разрядов получают конкатенацией с равномерно распределенным кодом. Общий метод формирования старших разрядов разработчиками аппаратурных средств не исследовался Спредлагаются использовать методы, разработанные автором.

Второй метод: используется аппроксимация »Г1Су) С по оси "у"). Из соображений простоты аппаратной реализации наиболее рационально равномерное разбиение щ, Ду. = Ду = 2тогда поиск коэффициентов осуществляется по к-разрядному адресу, получаемому с ГРРСЧ. Существенный недостаток в значительном усложнении блока подготовки информации.

12

В предлагаемом способе закон распределения FCx) С FCx) e

€ ССа.Ы) приближенно представляется через

п

SCx) = У Р- F. СхЗ . ift 1 1

где р. = рСХ = О - вероятности появления несовместных событий ; X - случайная величина; F.Cx) - функция распределения . Соответственно плотность WCx) , будет иметь вид ¡

R Сх) = Д р. W. Сх) . ( Др. = 1 ) Для реализации выбраны порядковые статистики второго порядка !

п

RCx) = У р. С2С. Cl-x) + 2С1-С. )х] ,

т.е. используется аппроксимация сплайнами, и возникают следующие задачи .

Задача 1 . Для заданной функции FCx) или WCx) и заданной точностГГ Ü^TI^ S) или QoCWtR) в выбранной метрике найти S*Cx) СRCx)) такую , что n* - min п среди натуральных чисел минимальным объемом оперативной памяти СОШ ГСЧ. Из критерия времени подготовки информации tnCmin ,tn) задача разделяется на две.

Задача 1.1. Найти rain n = п# при условиях задачи 1 Сдля оп-ределенйя^достаточности объема ЗУ 3. Даже для линейных сплайнов в Чебышевской норме эта задача аналитически не решается, поэтому необходимо решать сразу задачу 1 ;

Задача 1.2. Если n* < V , то определить S*Cx)CR*Cx)), где Г^Зс5ъем"ОП ГСЧ .

Задача 2 . Найти наилучшее приближение при п = п*. Задачи характерны и при разработке программного обеспечения . В качестве нормы выберем абсолютное отклонение с Сх)- |WCx)-RCx)|. Алгоритм определения C¡,fl)-ra участка сплайна :

1. Определяются корни уравнения

df I

fCx) - -gg Сх - х.) - у.

где 6- заданная"ошибка приближения ; fCx) - исходная функция ; х. ,у. - координаты конца i,-го участка сплайна.

2. Отбрасываются лишние корни, оставшиеся луч - касательные продолжаются до пересечения с кривыми fCx) i 6. и за очередную точку сплайна берется правая конечная точка. Решением задачи

у. +• у. у.

Для уменьшения времени формирования СЧ впервые предлагается

13

информацию организовать как оптимальную базу данных (оптимальный поиск).

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

Теорема 3.1. Всякую случайную величину, имеющую функцию распределения Р(х) заданную на множестве конечной меры и предста-вимую в ЭВМ, можно определить в виде конечной бинарной стохастической цепи.

Условная вероятность I - знака разряда определится при известной комбинации •1

f

pt/^n^/VA-J =

d Fix)

-1

V ."«I-1» J d Fix)

Интегрирование подразумевается в смысле Лебега - Стильтьеса . При необходимости разрядность формируемых случайных чисел может быть увеличена равномерно распределенным кодом в младших разрядах. Если lj$?lf3.=l/(3l,... .(3 ) = const* 0.5, то распределение является либо дискретным, либо сингулярным. Погрешность найдется из разложения в ряд W (х) и условия | W (х) - с | < е . Предложена схема для данного метода и оценка времени формирования . Уменьшение можно достичь усовершенствованием алгоритма :

1. Разложим W(x) по ортогональным полиномам Лаггера .

2. Найдем длину отрезка 2~1 с заданной погрешностью отклонения от W(x) .

3. По полученному экспоненциальному распределению определим вероятности появления бита .

4. На каждом дальнейшем шаге опрделяется погрешность отклонения от равномерного распределения. При достижении заданной погрешности процесс останавливается, и остальные разряды дополняются равновероятной последовательностью. Достоинством метода является возможность конвейеризации и параллелизации процесса. Предлагается вариант схемы.

ГШ с плавающей точкой. Для непрерывной или сингулярной фу-

нкции распределения FCx) вероятность порядка г

а-< r-t>

Р If) = гз = / d FCx)

o.s-a"r

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

1. Интервал С0.1) рабивается на 1 участков, где 1- максимально принятое значение порядка, причем значения границ интервалов записывается в ЗУ в виде значений последовательных сумм :

= I Рг •

2- Генерируется равномерно распределенное СЧ а . 3. Находится i, для которого а. _1 < а < at и присваивается г = t. Значения а образуют базу данных, поэтому необходимо организовать их оптимальное хранение С более подробно в работах автора ).

Порядок можно формироваться и последовательно, поразрядно у ...), например, начиная с младших разрядов, тогда для вероятности У:

m/a s-<r-i>

Р Су, = 1) = I J d F Сх)

r = i о. s 'a-1"

где г - все нечетные числа (с единичным первым разрядом). Аналогично для произвольной конкретной комбинации Су% ,... .у. ^

1 Рг Г^иУ.....У. ..............>?1 > >

Ply. =1/у......у. = -S-^-«¿1-

I к

.....^.j'^i,.....V

Разряды мантиссы выбираются при условии появления значения величины порядка г. Количество разрядов порядка определится, как и ранее. При той же WCx) скорость сходимости вероятности знака для мантиссы будет выше, чем в аналогичном методе для "фиксированной точки". Время формирования равно t^ = t^-t-t^, где t^ - время формирования, соответственно, порядка и мантиссы. Производится оценка этих величин и приводится схема ГПЗ с пар? х-лельным формированием порядков.

ГПЗ на основе бинарных последовательностей. Случай с фиксированной точкой. Основной недостаток предыдущих последовательных методов заключается в необходимости хранения большого количества коэффициентов. Общая схема представляет преобразование входной и

15

выходной последовательностей булевыми функциями. В работе предложены "линейные" схемы, описывающиеся разностным уравнением

к г

уС1+к)= |а.С1)уСик-1) +■ | Ь.СОха+к-.)),

где а. СО, Ь. Ш - вероятностные коэффициенты, а хС^к-р и уС1+к-1) - вероятности входных и выходных знаков, причем , £ а^и + Е Ь. СО =1. Привлекательность этого способа в возможности исследования достаточно хорошо развитого математического аппарата разностных уравнений для формирователей с булевыми функциями. Реально число формируемых разрядов га % Юч-12. В отличие от общего последовательного метода в этом используется гораздо меньше коэффициентов, а схемная реализация очень проста и может реализоваться на ПЛМ или РСЬА.

Точные параллельные методы Сстандартный, Неймана и т.п.). Реализация их на существовавшей элементной базе сложна,и поэтому разработчиками они не использовались.Метод исключения может быть реализован на современной элементной базе Смикропроцессорах) и стать особенна эффективным для многомерного случая. Исследование его ранее не проводилось. В диссертации предлагаются параллельные и конвейерные схемы и производится временной анализ. Повышение производительности метода может достигаться использованием операций с сокращенным форматом Сне более 2-х байт), что следует из выявленных свойств функций распределения.

ГПЗ по методам НДС. С точки зрения эргодической теории: если отображение фазового пространства в себя не изменяет начального распределения и является эргодическим, то распределение вероятностей движений системы с вероятностью 1 совпадает с исходным. Определяются условия возникновения псевдостохастических колебаний. Проведены исследования некоторых отображений.

Четвертая глава "Преобразователи стохастических бинарных последовательностей" посвящены вопросам синтеза преобразователей, имеющих большое самостоятельное значение и применяющихся в ГСЧ . В качестве математического аппарата исследований автор стремился использовать развитый классический анализ. Со схемотехнической точки зрения выбирались способы наиболее простой-реализации на современной элементной базе Смикропроцессоры, ПЛМ, ПЛИС, РР6А и д.р.).

Генератор бинарных марковских последовательностей. В главе 3 было введено понятие преобразователя, работа которого описывается разностным уравнением. В этой главе и приложении, проводится 16

углубленный анализ математической модели.

Как известно, общее решение уравнения выражается через корни рг его характеристического полинома, vi. Рг € R . Задачей является исследование корней и их границ, результаты которого сформулированы в следующей теореме Сполное доказательство в приложении 2).

Теорема 4.1.

1. vi, Ргб С-1,1) , l = 0 -f m ;

2. В R+ существует всегда только один корень р+, р+ =1 если ][а = 1 и р+< 1, если ^ а. < 1

3. уг (р^Э j i I 0 ]

Находятся частные и общие решения для однородного уравнения . Исследуются варианты автоматов с памятью и по выходу и по входу:

yCt + к) - £ yCt + к - О а = *>Ct + к) -d ,

где d = const несовиестеный с а. , находится общее решение. В работах автора исследовались и уравнения для переменного входного сигнала (приложение 2 ), в частности, для синусоидального x(t)■= А + В-sin wt. В работе предлагается алгоритм синтеза преобразователей и приводится пример синтеза по значениям Fit). Таким образом, преобразователи позволяют получать широкий класс нестационарных последовательностей с довольно простой реализацией на цифровой элементной базе.

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

Входная случайная бинарная последовательность ССБП) ?Ctfc), следующая с периодом Т (в дальнейшем считаем Т = 1 ) и вероятностью PtfCtfc) = 1] , tfc = kT преобразуется в новую СБП 7? (к)

так, что вероятность появления знака "1" в ней равна :

к

P[j)Ck) = 13 =c m Ck) = c-Mtx(k) =cJ?Cj)] ,

J = o

где с - коэффициент пропорциональности,с < 1 , юхСк) = MtxCk)]-- математическое ожидание последовательных сумм хСк). В работе изучается отображение vxCk): хСк)-*Нхк, Нхкс Y = С к)>, s зави-

17

симости от которого выделяются типы интеграторов. При этих условиях вероятности выходных знаков СИ определятся

Р[т}Ск) = 1] = У Р1хСк)3 У РЕуСкЗЗ *( кгех у( к)

Соответственно, условные вероятности равны :

РЕтгСкЭ = 1|хСк)3 = У Р1у(к)] = РСН ) у(кГ€Нх *

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

Сопоставим вероятности знаков соответственно входной последовательности £Ск) - *(к), а выходной ^Ск - уСк). тогда модель СИ определится разностным уравнением

*Ск) + а^кЗ-хСк - 1) +... + агСк)*Ск - г) = уСк) Находятся необходимые решения для значений параметров интеграла и выходной последовательности. Доказывается, что если знаки эталонного кода распределены не равномерно, то РСх(к)3 имеет сингулярное распределение, которое приближенно представляется через В-распределение.

Интегральные преобразователи с обратной связью. Предлагаются обобщения этих схем. В частности когда обратная связь воздействует на п-1-ый разряд ожидание М[х(к+131 описывается неоднородным разностным уравнением:

МЕхСк + 1)3 = МЕхСк)] * 2~(п_г><2Ск) - РС?)Ск) = 13>

Вводя в рассмотрение характеристическую функцию (.&) и решая дифференциально - разностное уравнение, получим

п-1 г -<п-1)

| = е£2 к«'^! - е^»2 ]

Наиболее распространенный и чаще используемый случай интеграторов - с обратной связью, сравнением и равным числом разрядов в регистрах. Детально исследован автором (выводы в приложении 3).

Преобразователи с постоянным эталонным кодом С"с").

Работа СИ определится следующим рекуррентным уравнением : Рк+1Сх > с] = Рк[х > с] + р Рк[с -1] - ъ Р^СсЗ, где Рк1с] - вероятность появления в к-й момент в сумматоре значения "с". Для получения т)СкЗ с "хорошими" вероятностными характеристиками следует использовать сложные эталонные последовательностями.

..Нелинейные преобразователи стохастических бинарных последо-довательностей. Здесь ставится задача синтеза преобразователей 18

на основе НДС, исследования которых в настоящее время исключительно актульно. Однако, теория их недостаточно развита для решения задач синтеза.

Предлагается разработка "многоустойчивых" преобразователей, под которыми понимаются устройства с точечными отбражениями рСх), имеющими несколько точек устойчивости вероятности выходного знака С"1"). Если такая точка одна и равна р = ? , то 7)Ш "асимптотически устойчива", т.е. независимо от входной вероятности <р * 0 и р * 13, выходная сходится к При £о = 0.5- это "выравнивающее" устройство. Подобной же задачей является, напри- ^ мер , разработка устройств контроля выходных вероятностных характеристик. Доказана следующая теорема.

Теорема 4.2. Функция отображения ^р) = + (-1)п+'с^-н +■ с2 является функцией вероятности при ? =0.5, где б = р- 0.5.

Рассмотрен синтез функций рСр) с одной точкой устойчивости ? ^ 0.5 о соответствующей функцией вероятности, обозначенной через Го1Ср), которая существует для р =к/и , где к и и - целые числа ,2-<"-*>< ^ <1 ст < < 2П_1). В этом случае класс функций имеет следующий вид а

Го4Ср) = р - рчйД с^ р^ .

где коэффициенты полинома. Скорость сходимости оценивается из выражения АЬ*У, где Ь = Го1'С?о), А - некоторая постоянная, и -номер шага. Приведен пример для ? = 1/3 и п = 5.

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

Случайное напряжение ?си с источника шума СИЮ квантуется по времени в моменты действия тактовых импульсов СТГО на квантователе СКВ). Полученные выборки сравниваются на схеме сравнения СССГО с напряжением иСО на выходе интегратора. Если в момент сравнения £Ш< иси, то на выходе т)СО=1,а функция обрат-

19

ной связи С ФОС) вырабатывает сигнал - Ц^. При ?Ct) > UCt), т>Ш = О и Uoc = О. Uoc и управляющий сигнал Uz поступают на входы интегратора Соперационный усилитель).

Вероятность выходного знака на выходе АСП определится из ш и< t>

PlTjCt) = 13 = J f [UCt)3dU J f«C?)d? r -00 -00 ^ где Гц[ЦСО I - плотность распределения UCt) на выходе интегратора; fcCx) - плотность распределения ?Ct). Математическое ожидание Mi UCt +■ 1)] описывается следующим разностным уравнением, в общем случае нелинейным :

MEUCt + 1)] = MCUCt)] ехрС-Т/ти) - yí^Ct.t + 1)3 + * к,иосР[7>ш = 1КехрС-СТ - tüc)/ru) - ехрС-Т/ти)) .

где Т - период ТИ; тц-постоянная времени интегратора; ку-коэффи-циент усиления усилителя;toc-длительность импульсов U,y[UCt,t^l)3 -величина, зависящая от характера изменения Uz в интервале Ct,t+-1

Теорема 5.1. Если v ? . f?Cf) к 0 , { « [0 , -И н U2Ct) = = const = U2, то tДц PC7)Ct) =11 = k-Uz , где k - некоторый коэффициент пропорциональности.

Точное значение вероятности Pl7)Ct) = 13 в переходном режиме удается получить не для всех плотностей f^Cx). Для решения в общем случае нелинейного разностного уравнения используется кусочно-линейная аппроксимация F^íUCt)3.

Длительность N переходного процесса определится из выражения

- lnCl - PM /U )

м - уст кап z

И Пй " '

где £ - отклонение от установившегося значения. Для получения

JrCT

распределения UCt) проводилось статистическое моделирование. Исследовались динамические свойства схемы при управляющем сигнале UCt)=A+B sin wt СА > В, А + В < 1), при этом анализировались не только вероятности знаков, но и корреляционный момент.

Возможности существенно расширяются введением сложной логической ФОС. Действительно, введение коныонктора дает возможность управления Сопределения) корреляционным моментом. ФОС в общем случае представляет, собой конечный автомат, содержащий элементы памяти, на вход которого поступает последовательность j)Ct). Анализируются также схемы, в которых осуществляется одновременное управление выходной вероятностью и корреляционным моментом.

Шестая глава "Архитектурные элементы ФОС ССМ" призвана несколько обобщить полученные результаты и носит концептуальный характер. Разработка архитектур ССМ является большим самос-20

тоятеяьным исследованием и не является основной целью этой работы (хотя исследования продолжаются и работ такой ориентации практически нет). Производительность ФОС определяется как и выше.

Наиболее сбалансированной является система из базовой ЭВМ и ФОС. Аппаратная поддержка в первую очередь таких систем и является целью работы. Архитектурный аспект включает информационный, функциональный и структурный направления исследований. Для систем специального назначения эти проблемы могут выродиться в разработку отдельных блоков СГСЧ, ГПРСЧ и т.п.).

Информационный аспект требует соблюдения принципов представления данных в ЭВМ, для чего в диссертации ряд новых методов и алгоритмов.

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

Анализ ФОС ССМ показывает на необходимость введения системы команд, причем обязательными являются: генерирования СЧ и ПСЧ с равномерным и произвольными распределениями-, статистической обработки. Предпочтительный формат команд - типа Р.Н. В сопроцессор-ном варианте они должны быть расширением базовой системы. Модификации команд должны содержать возможность применения их для различных форматов данных с фиксированной и плавающей точками и целых чисел. Необходимо также учитывать возможность генерирования многомерных величин.

Структурный аспект имеет основные задачи: определить набор блоков" и функций Ссуть данной работы), т.е. найти оптимальное функционально структурное отображение

Б : , 6 > —♦ {Сс1. , Э.)).

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

Устройство ввода случайных чисел ЕС-6903 проектировалось как внешнее устройство ЕС ЭВМ (специализированный терминальный процессор), подключаемое к селекторному или мультиплексному каналу. Серийное производство его начато в 1983 году на предприятии п/я А-3886. Экономический эффект от внедрения одного устройства составляет 20.8 тыс.руб. (по ценам 1982 г.), а от выпущенных в 1983 году - 208 тыс. руб. Быстродействие устройства -800 Кбайт/сек (пропускная способность селекторного канала). Максимальный объем однократного массива 64 Кбайта.

Устройство может работать в 2-х режимах: генерирование СЧ и

21

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

Статистическая погрешность генерирования не хуже 10"4 .

Сопроцессор терминальной ЭВМ ЕС1007 предназначен для статистического моделирования и защиты информации в терминальной ЭВМ СТЭВМ) и вычислительной сета криптографическими методами Сем. рис). Скорость обмена по интерфейсу расширения конфигурации: при кодировании/декодировании информации и формировании равномерно распределенных чисел - не менее 300 Кбайт/с; при формировании чисел с произвольным законом распределения - не менее 100 Кбайт/с; при формировании случайного процесса - не менее 50 Кбайт/с. Форма представления чисел - 32-разрядное слово с плавающей точкой.

Система команд использует код ЕА 60-65 ЕС ЭВМ и имеет аппаратную и микропрограммную поддержку. Назначение команд: генерирование СЧ и ПСЧ с равномерным, дискретным и непрерывным распределениями; генерирование случайного процесса с заданным корреляционным моментом; шифрование/дешифрование информации криптографическими методами. Возможны различные формы задания функции распределения (функцией, гистограммой, точками). В сопроцессоре использованы методы, описанные в предыдущих главах.

Основу ГСЧ и ГПСЧ составляют две 4-разрядные микропроцессорные секции К1804ВС2, образующие 8-разрядную микропроцессорную систему. В регистровом запоминающем устройстве СРЭУ) МПС эмулируется 103-разрядный кольцевой RG, формирующий М -последовательность с образующим полиномом fCx) = xto1 ® Xs18 1. На них же строится и ГСЧ. Елок защиты использует таблицу подстановок и операции гаммирования.

Сопроцессор СМ для ПЭВМ типа IBM PC/AT разрабатывался как аппаратно программный комплекс ГСЧ, ГПСЧ и защиты информации. Наиболее массовые процедуры - приведение к заданному формату, интервалу, связь с языками высокого уровня - выполнены на ассемблере. Программы статистического контроля выполнены на языках высокого уровня.

Быстродействие ГСЧ при тактовой частоте PC/AT 6/12 МГц при формировании: ПСЧ - 1,32/2,64 Мбайт/с, СЧ - 0,86/1,72 Мбайт/с. ГСЧ формирует 32-разрядные коды, интерпретируемые программными : средствами как числа целые или с плавающей точкой. Конструктивно 22

БТК

нала ГСЧ; БУ ГСЧ - блок местного управления; БНО - буферный регистр; БЗ - блок зашиты; ФРЗ - формирователь равномерного закона; КСА - регистр адреса; ФПЗ - формирователь произвольного закона; ОЛ ГСЧ - оперативная память ГСЧ; ФИ - формирователь процесса; БС - блок сопряжения с СЕ1Р

ГСЧ выполнен в виде одной платы на основе интегральных микросхем серий К155, К531, К555, К580 и КМ1804. ГСЧ построен как стохастический генератор.

В приложениях приведены результаты испытаний в режимах формирования СЧ и ПСЧ для выборок объемом 104 и 10® чисел.

При тактовой частоте PC/AT 12 МГц, ГСЧ формирует псевдослучайный код за 1,5 мкс, случайный - за 2,33 мкс. На получение целого СЧ или ПСЧ из TurboPascal затрачивается 14 мкс, а с плавающей точкой - 23 мкс. Встроенная функция TurboPascal RANDOM формирует только псевдослучайные числа за 75 мкс.

Интерфейс ГСЧ с языками FORTRAN, TurboPascal, TurboC осуществляется специально разработанными функциями. Программное обеспечение осуществляет подготовку исходных данных, преобразование кодов в числа с различным представлением и статистическую обработку. Алгоритм формирования СЧ и ПСЧ с произвольным законом распределения реализован модульным программным комплексом.

Сопроцессор использовался для решения сеточных уравнений вероятностными методами.

ГСЧ для защиты информации в специальных системах. Автор был разработчиком серийного устройства. Ввиду повышенных требований к надежности , быстродействию и статистическим характеристикам, была принята концепция многоканального генератора с функциональным дублированием. В качестве источника шума использовался шумовой диод типа КГ 401.

БИС ГСЧ на базовых матричных кристаллах разрабатывался как замена предыдущего, на основе методов с квазидетерминированными процессами. Схема защищена авторскими свидетельствами. БИС ГСЧ типа 4.601BJ2-0105 формирует последовательность непредсказуемых равномерно распределенных чисел, реализован на цифровом базовом матричном кристалле КМОП - структуры.

Комплекс программных средств для генерирования и исследова-вания статистической информации предназначен имитации работы аппаратных блоков и обработки статистической информации. В настоящее время он используется ъ учебном процессе КГТУ.

Выделяется два этапа работы системы: подготовка неходкой информации; обработка статистической информации. На первом происходит выбор одного из трех видов источников статистической информации: ГПСЧ; готового файла с информацией; клавиатуры ПЭВМ.

Первым источником является модель ГПСЧ, построенного на основе регистра: сдвига, в которой пользователь может изменять параметры и начальное состояние. Модуль обработки статистики: вы-24

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

Система тестирования генераторов равномерно распределенных случайных и псевдослучайных чисел. Для стандартизации тестов и создания возможности сравнения различных устройств и программных средств ГРРСЧ и ГПСЧ был предложен проект ГОСТ: "ПРАВИЛА ПРОВЕРКИ ГЕНЕРАТОРОВ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ И ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ ", который включает'базовый набор критериев. Проект был принят к рассмотрению ГОССТАНДАРТОМ, разослан в ведущие организации страны, получены отзывы и замечания, которые были устранены, материалы переданы на утверждение. С помощью этих тестов проводилась проверка разработанных средств.

Настоящий стандарт устанавливает правила проверки качества конечных последовательностей независимых, равномерно распределенных чисел на интервале С0,1) СЧ и ПСЧ по тестам: комбинаций, пар, монотонности, серий, "наибольшее из I", М - мерной равномерности, корреляции, апериодичности.

Проверку согласия распределения по критериям Колмогорова, X*. шг следует проводить в соответствии с СТ СЭВ 1190-78 .

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

ЗАКЛЮЧЕНИЕ

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

На основе системотехнического анализа ССМ как ФОС определены архитектурные требования и проблемы разработки. Проведено теоретическое обобщение и систематическое исследование методов генерирования равномерно и произвольно распределенных СЧ и ПСЧ

на основе нелинейных динамических систем со стохастическим аттрактором и квазидетерминированных процессов и с различной формой представления информации. Предложена логическая структура ГРРСЧ.

В работе предложены, разработаны и исследованы методы и устройства ГРРСЧ с использованием распределенных источников шума: микрошумов переключательных элементов ИС С ГСЧ разрабатывались двух типов: со стохастическим аттрактором и с квазидетерми-нированными процессами). Это впервые позволило создать БИС ГСЧ и контроля.

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

Впервые предлагается использовать методы оптимального хранения и поиска информации в базах данных для организации информации в ССМ.

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

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

Предложена и проведена архитектурная увязка блоков для построения ФОС С сопроцессоров и процессоров ) .

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

комплексах.

Содержание диссертации изложено в следующих основных работах .

1. ГловаВ. И., РякинО. М. О синтезе симметрических базовых многополюсников //Труды семинара "Вопросы теории ЭЦВМ" научный совет по кибернетике АН УССР. - Киев, 1965, - Вып. 8, Савторский оттиск) - 14 с.

2. ГловаВ. И. О синтезе устройств многоустойчивых по вероятности появления бинарных знаков //Тезисы докладов на 1 Всесоюзном симпозиуме'по вероятностным автоматам. - Казань, 1969, - С. 21-22

3. ГловаВ. И. 0 синтезе устройств, многоустойчивых по вероятности появления бинарных знаков // В сб. Вероятностные автоматы и их применение. - Зинатне, 1971, - С. 77-96.

4. Г л о в а В. И., С к р е б н е в А. А. Вопросы анализа и синтеза стохастических потоков бинарных символов методом разностных уравнений //Тезисы докладов научно-технической конференции городов Поволжья по статистической радиофизике и радио-электронике. - Казань: Изд-во КГУ, 1971,- С. 11-12.

5-Глова В. И. .Жамагорцян К. М. .Кирьянов Б. Ф. О корреляции в стохастических интеграторах //Труды ГНИПИ-ВТ. -Казань, 1971. Вып. 6, - С. 124-130

6. ГловаВ. И. Определение моментов распределения напряжения линейной цепи, коммутируемыми стохастическим потоком бинарных символов //Труды ГНИПИ-ВТ.- Казань, 1971.- Вып 6, - С. 22-28.

7. A.c. 447707 СССР . Генератор случайной последовательности /В. И. Г л о в а, Б. Ф. К и р ь я н о в, В. А. П е с о ш и н //Б.И., 1974, N 39.

8. A.c. 458821 СССР . Генератор случайной последовательности импульсов /В. И. Г л о в а. В. А. П е с о ш и н // Б. И. . 1975, N4.

9. Глова В. И. .Кирьянов Б. Ф., С к р е б н е в A.A. Стохастический принцип построения аналого-цифровых вычислительных систем. //Тезисы докладов IV Всесюзной конференции по аналоговой и аналого-цифровой вычислительной технике. -Москва, 1973.-С.14.

10. ГловаВ. И. , П е с о ш и н В. А. Аналого-стохастические преобразователи //Автоматика и вычислительная техника.-Рига: Зинатне, 1974. - И 1. - С.52-58.

11. Г л о в а В. И., К и р ь я н о в Б. Ф. Стохастические вычислительные машины Собзор и проблемы) //Труды Иркутского

политехнического института. - Иркутск, 1974. - С.33-69. 1^ГгЯ.4Э'В а В. И., Лесов и' н В. А. Аналого-стохастические преобразователи с управляемыми корреляционными свойствами //Труды Иркутского политехнического института. - Иркутск, 1974с - С. 93-104.

13. Г л" о в а В. И., Кирьянов Б. Ф. 0 сходимости итерационных процессов в стохастических интеграторах //Сб. Прием

обработка инфорШши в структурно - сложных информационных системах . - Казань: Ш-во КГУ, 1974. - Вып. 4. С. 15-21.

14. Г л. о в а В. И., ПесошинВ. А. Аналого-стохастические преобразователи с обратной связью //Сб. Прием и обработка

г информации в структурно-сложных информационных системах. -Казань: Из-во КГУ, 1974. Вып. 4. - С.53-67. . 45. К и р ь я н о в Б. Ф., Г л о в а В. И., Я е о н т ь е ;в' А. Г7, * - Р и з а е в- И. С. Формирование случайных последовательностей - при физичёском моделировании дискретных каналов связи //В кн.: Кодирование и передача дискретных сообщеий в системах - "'СВЯЗИ, - м.: Наука, 1976. с. 141 ^151- " "

16 Г ло в а В. И., М о с у н о в В. Е. Вопросы создания адаптивной СУБД в АСУ //Тезисы докладов научно-практической кбн-

.......ференции "Автоматизация оперативного управления 'основным

производством". - Казань, 1977. - С.36-35. ■17. Г л о в а В. И., 0 ж и г а н о в \Я. И., Р и :з -а е в И. С., • М о с у н о в В. Е., С у з д а л ь ц-е в В. А., Я х "й н а 3. Т. Вопросы оценки качества и повышения эффективности ис-- ~ пользования памяти Информационной базы АСУП // Научно - технический отчет N 77039432.- Казань, КАИ, "1977. Часть 1- 71с. 1-8. Г я о в а В. И., М о с у н о в В. Е. , Р и з а е в И/ С. Вопросы сокращенийизбыточности при проектировании информаци-■ онной базы АСУ. //Труды седьмого^ Всесоюзного симпозиума по "^-■"проблеме избыточности в информационных системах. - Я.", 1977.-ттоЧ;з. -' С. 14-17.

19. Г л о в'~а В. И. ,' П в с "о ш и н В. А., Ж и в е т и н а Т. М. Исследование и разработка специализированных процессоров для ЕС ЭВМ Сряд 2 и ряд 33 для сети ЭВМ- Анализ архитектуры системного математического обеспечения процессора статистического моделирования.- Казань: Изд-во КАИ,1981,рег.N811036626.

- 27 с.

20. Г л о в а В. И., П е с о ш и н В. А., Кузнецов В. М., БурнашевМ. И., С о ф р о н о в В. В. Исследование и разработка спецпроцессоров ЕС ЭВМ (ряд 2 и 33 для сети ЭВМ.

Разработка процессора статистического моделирования //Научно

- технический отчет Гос. per. N Б953670. 1981. - 160 с.

21. Г л о в а В. И., П е с о ш и н В. А., С о ф р о н о в В. В., Тахавова Э. Г. Исследование и разработка специализированных процессоров для ЕС ЭВМ (РЯД 2 и РЯД 3) для сети ЭВМ. Разработка транслятора языка описания дифференциальных уравнений в частных производных. -Казань: Изд-во КАИ, 1982. per. N81103626. - 40 с.

22. Г л о в а В. И., П е с о ш и н В. А., К у з н е ц о в В. М., Живет и на Т. М. ,СофроновВ. В., Тарасов В.М., М а н с у р о в Р. М. Модернизация устройства ЕС 6903. Аппаратурно - программные методы генерирования псевдослучайных чисел и последовательностей. Вероятностные методы и средства //Тезисы Всесоюзной научно-технической конференции.

- Новгород, 1983. - С.13S

!3. Г л о в а В. И., П е с о ш и н В. А., С о ф р о н о в В. В. Алгоритмы и аппаратура для вероятностного решения краевых задач. Вероятностные методы и средства //Тезисы Всесоюзной научно-технической конференции.- Новгород, 1983, - С. 50-51.

¡4. Г л о в а В. И., П е с о ш и н В. А., Кузнецов В. М., Ж цвет и на Т. М., СофроновВ. В., Тарасов В. М. .Мансуров Р. М. .Сергеев Н. Н., Д а п и н О. И. Исследование и разработка специализированных процессов для ЕС ЭВМ С РЯД 2 и РЯД 3) для сети ЭВМ. Разработка процессора статистического моделирования. - Казань: Изд-во КАИ, 1983. per Н 81103626. - 98 с.

5. Г л о в а В. И., Л е с о ш и н В. А. , Б у р н а ш е в М. И. , Кузнецов В. М., СкребневА. А., Тахаут-д и н о в а С. Л., Разработка генератора случайных чисел для ТЭВМ ЕС1007 //Научно-технический отчет Гос. per. Н 81103626. 1985. - 120 с.

6. ГловаВ. И., И е с о ш и н В. А. .Кузнецов В. М., Сергеев Н. Н. Исследование и разработка методов математических моделей нетрадиционных генераторов случайных чисел и процессов защиты информации в сетях ЭВМ // Отчет о НИР Гос. per. 018600056154. 1985. - 77 с.

7. ГловаВ. И. Методы и средства моделирования случайных величин с произвольной функцией распределения для мини - ЭВМ //Тезисы докладов научно-технической конференции. - Казань, 1985. - С.33-34

3. ГловаВ. И., БикмухаметовР. Р., Бурна-

ш е в М- И., П е с о ш и н В. А. Моделирование случайных процессов на мини - ЭВМ. Автоматизация управления производством и технологическими процессами с применением мини -ЭВМ //Тезисы докладов республиканской научно-практической конференции. - Казань, 1985. - С.54-55.

29. ГловаВ. И., Песошин В. А., Тахаутдинова С. Я., Я х и н а 3. Т. Математическое обеспечение аппаратных средств статистического моделирования //Межвузовский сборник "Управление в сложных системах". - Уфа : Изд-во УАИ, 1985.

- С. 43-45.

30. A.c. N 1249512 ССССР), МКИ G 06 F 7/58. Генератор случайной последовательности //В. А. П е с о ш и н, В. М. Кузнецов, Н. Н. С е р г е е в, С. Г. Г р и ш к и н, 0. И. Д а-п и н, В. И. Г л о в а, Е. К. I а р о н о в а // Б. И. 1986.

- N 29.

31. A.c. N 1272482 ССССР). Устройство для формирования псевдослучайных чисел / ГалеевИ. К., ГловаВ, И., Д а -пинО. И. .Вострокнутов А. Г., Песошин В. А., IT и у л ь с к а я Г. И. // Б. И., 1986. 11 48.

32. A.c. N1302274 ССССР). Устройство для контроля генератора случайных чисел /ГловаВ. И., Сергеевы. Н., Д а -п и н 0. И., К у з н е ц о в В. М., М о и с е е в В. В., П ес о ш и н В. А., Ш а р о н о в а Е. К. //Б. И. 1987, N 13.

33. A.c. 1280612 ССССР). Генератор случайных чисел /Г л о в а В. И., Песошин В. А., Тахаутдинова С. Л. //Б.И., 1986, N48.

34. ГловаВ. И., Б у р н а ш е в М. И. Песошин В. А., Тахаутдинова С. Л., ЯхинаЗ. Т. Принципы построения средств статистического моделирования мини ЕС ЭВМ //Тезисы межреспубликанской научно-технической конференции "Вероятностные автоматы и их приложения".- Тбилиси: Мецние-реба, 1986. - С.33-34.

35. ГловаВ. И., БурнашевМ. И., Песошин В. А. Микропрограммные средства ГСЧ терминальной ЕС ЭВМ //Тезисы межреспубликанской научно-технической конференции "Вероятностные автоматы и их приложения". - Тбилиси: Мецниереба, 1986. - С.35-37.

36. ГловаВ. И., Песошин А. А., Тахаутдинова С. Л. Моделирование случайных величин с произвольным распределением //Тезисы межреспубликанской научно-технической конференции "Вероятностные автоматы и их приложения".

- Тбилиси: Мецниереба, 1986. - С .37-39

37. ГловаВ. И. .Бикмухаметов Р. Р., Песо-шин В. А. Моделирование случайных процессов // Тезисы Межреспубликанской научно-технической конференции "Вероятностные автоматы и их приложения". - Тбилиси: Мецниереба",

1986. - С. 43-44.

38. ГловаВ. И., Р о м а н о в В. 0. Вероятностный автомат для получения оценок характеристик случайных процессов //Тезисы межреспубликанской научно - технической конференции "Вероятностные автоматы и их приложения". - Тбилиси: Мецниереба, 1986. - С. 67

39. ГловаВ. И., Р о м а н о в С. В. Методы и средства воспроизведения нагрузок со случайными амплитудами //VI Всесоюзный межотраслевой симпозиум. - Новосибирск, 1986- - С.23.

40. Г л о в а В. И., П и у л ь с к а я Г. И., П е с о ш и н В. А., Я н и ц к и й В. Е- Процессор для решения задач динамики разреженного газа // Сб. "Методы и средства статистического моделирования". - Казань, 1987. - С.19-25.

41. ГловаВ, И. К у з н е ц о в В. М., Я х и н а 3. Т. Имитационные модели генератора случайного процесса //Сб. "Методы и средства статистического моделирования". - Казань,

1987. - С. 71-76.

42. A.c. Н 1413706 ССССР), МКИ H 03 К 3/84 Генератор случайной последовательности /ГловаВ. И-. Д а п и н 0. И.. К у з-нецовВ. М. .Песошин В. А. .Сергеев H. Н., Ермолаева Л. С., Сафонов В. Л., Яр м уха-мет о в А. У. //Б. И. 1988. - К 28.

43. ГловаВ. И., M а в р и н а Л. Н., Я х и н а 3. Т. Диалоговая система статистической обработки данных //Сб. "Повышение эффективности использования мини- и микро-ЭВМ в автоматизированных системах". Тезисы докладов. - Казань, 1988.

- С. 7-8

44. А.с. 1509883 СССР, МКИ С 06 Г 7/58. Генератор случайных чисел с проивольным законом распределения /В. И. Г л о в а , Р. Р. Бикмухаметов, С.Л. Тахаутдинова, В. А. Песошин, Ю. В. Горбунов, А. У. Ярму-х а м е т о в, В. Л. С а ф о к о в // Б. И. 1989. - H 35.

45. A.c. N 1513446, МКИ1 G06 F 7/58. Генератор псевдослучайных чисел /ГловаВ. И., Мансуров Р. М., Столов Б. Л.

46. ГловаВ. И., П е с о ш и н В. А., Ж и в е т и н а Т. М.

Проверка генераторов равномерно-распределенных случайных и псевдослучайных чисел //Сб. "Проблемы разработки и внедрения микромодульных систем в ЭВМ". Тезисы докладов научно - технической конференции. - Казань, 1990. - С.7-8

47. Г л о в а В. ■ И., Несения В. А. Вычислительные средства статистического моделирования //Сб. "Проблемы разработки и внедрения микромодульных систем в ЭВМ". Тезисы докладов научно-технической конференции. - Казань, 1990. - С. 5-6.

48. ГловаВ. И., БурнашевМ. И.. Т а, х а у т д и н о-в а С. Л., Я х и н а 3. Т. Пакет программ для генерации случайных последовательностей и исследования статистической информации для ПЭВМ //Сб. Программное обеспечение ЕС ЭВМ, ПЭВМ и комплексов АРМ". Тезисы докладов научно - технического семинара. - Минск, 1990. - С.17-18.

49. Г л о в а В. И., Т а х а у т д и н о в а С. Л., Я х и н а - 3.Т. Программное обеспечение ' сопроцессоров статистического

моделирования в ЕС ЭВМ и ПЭВМ //Сб. "Програмное обеспечение ЕС, ПЭВМ и комплексов АРМ". Тезисы докладов научно - технического семинара. - Минск, 1990.- С.19-20.

50. Глова В.И., ПесошинВ. А. Система моделирования и обработки случайных" сигналов ЕС ПЭВМ //Тезисы докладов Всесоюзной научно - технической конференции "Компьютерные методы исследования проблем теории и техники передачи дискретных сигналов по радиоканалам. М: Радиосвязь, 1990. -С. 33-35.

51. ГловаВ. И., ПесошинВ. А., СофроновВ. В., Г р и ш к и н С. Г. Сопроцессорные средства ПЭВМ для статистического моделирования и обработки информации //Научно -исследовательский отчет. М: ИЛИ АН СССР, 1990. - 22 с.

52. ГловаВ. И. , П е с о ш и н В. А. Вычислительные средства для статистического моделирования //Тезисы докладов на VIII Всесоюзном совещании "Методы Монте-Карло в вычислительной математике и математической физике. - Новосибирск, ВЦ СО АН СССР, 1991. - С.17-21.

53. ГловаВ. И. .БикмухаметовР. Р., Бурна-шев М. И. .Песошин В. А., Тахаутдинова С. Л., Я х и н а 3. Т. Сопроцессорные средства формирования случайных чисел и защиты информации //Сб. "Вопросы ра-диоэлектрникн. 1991. - Сер. ЭВТ. - Вып. 6. - С. 63-69.

54. Глова В. И. .Тахаутдинова С. Л., Яхина З.Т. Методы аппаратурного формирования случайных чисел с

произвольным распределением //Сб. "Вопросы радиоэлектроники". 1991. - Сер. ЭВТ. - Вып. 6. - С. 70-76.

53. Глова В. И., Мавр и на Л. Н. , Тахаутдино-ва С. Л. Программные средства формирования случайных чисел с произвольным распределением на персональных ЭВМ //Тезисы докладов "Современные проблемы алгоритмизации". - Ташкент, АН Узбекской ССР, 1991. - С.36.

56. ГловаВ. И., Ж и в е т и н а Т. М., Песошин В. А. Система тестирования генераторов равномерно распределенных чисел //Тезисы докладов "Современные проблемы алгоритмизации". - Ташкент, АН Узбекской ССР, 1991. - С.37.

57. ГловаВ. И., П е с о ш и н В. А. Проблемы алгоритмизации задач статистического моделирования //Тезисы докладов "Современные проблемы алгоритмизации".- Ташкент, АН Узбекской ССР, 1991. - С. 7.

58. Г л о в а В. И., П е с о ш и н В. А. Проблемы разработки вычислительных средств статистического моделирования //Математическое моделирование и обработка изображений. - Новгород, НПИ, 1991. - С. 22-28.

59. Глова В. И., Песошин В. А., Софронов В. В., Г р и ш к и н С. Г. Сопроцессорные средства ПЭВМ для статистического моделирования и обрабтки информации //Исследовательский отчет. - Казань, Институт проблем информатики РАН, 1991. - 50 с.

60. Глова В. И., СуздальцевВ. А., Тахавова Э.Г. Экспертная медицинская система для акушерства и генико-логии //Тезисы докладов научно - технической конференции "Научный потенциал ВУЗов - программе, "Конверсия" КГТУ".-

Казань, 1992. - С. 12.

61. Г л о в а В. И., БалоевМ. А. .Богатова Н.М., Подольская М. А. Экспертная система диагностики и лечения вертеброгенных заболеваний //Тезисы докладов научно-технической конференции "Научный потенциал ВУЗов- программе, "Конверсия" КГТУ. - Казань, 1992. - С. 13.

Формат 60x84 1/16. Бумага офсетная Печать офсетная.

Печ. л. 2.о. Усл. печ. л. /.<36. Усл. кр. -отт. i. 9/, Уч.-изд. л.2.О.

Тира* 100. Заказ Р293

Казанский государственный технический университет им.А. Н. Туполева.

Ротапринт Казанского государственного технического университета им. А. Н. Туполева. 420111, Казань. К. Маркса, 10