Общая постановка задачи

Лабораторная работа №2. Исследование способов формирования случайной величины на основе генератора псевдослучайных последовательностей.

Требования к содержанию, оформлению и порядку выполнения

 

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

1. Схема генератора ПСП на регистрах сдвига.

2. Листинг программы (или файл в электронном виде) и результаты генерации ПСП в последовательном и параллельном кодах.

3. Анализ сгенерированной ПСП по трем критериям случайности.

4. Выводы по работе.

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

 

Теоретическая часть

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

В настоящее время наиболее широко применяются два подхода.

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

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

 Рассмотрим подробнее метод формирования псевдослучайных последовательностей единиц и нулей на основе регистров сдвига (или сдвигающего регистра).

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

Общая функциональная схема такого сдвигающего регистра с обратной связью приведена на рис.1. Например, если n = 3, функция обратной связи имеет вид  (на элемент обратной связи, являющийся сумматором по модулю 2, по­даны выходы с первого и третьего разрядов регистра) и начальное состояние регистра 001, то он по­следовательно принимает состояния 001, 100, 110, 111, 011, 101, 010, 001... В этом случае восьмое состояние совпадает с первым, т. е. пе­риодичность работы схемы равна 7. С выхода снимается псевдослучайная последователь­ность 1001110, повторяющаяся с периодом, равным 7 элементам. При этом состояния регистра представляют собой не что иное, как последовательность чисел от 0 до 7 представленных в двоичном коде, то есть последовательность чисел: 1,4,6,7,3,5,2 и затем снова 1. Легко видеть, что период повторения определяется максимальным значением числа из полученной последовательности чисел. Таким образом, на выходе генератора ПСП формируется двоичная последовательность, а в параллельном коде с выходов регистров можно получать значения псевдослучайных чисел в двоичной системе счисления.

 

 

Рис. 1. Схема n-разрядного сдвигающего ре­гистра с внутренней обратной связью

 

Последовательности, образуемые с помощью схемы, изображенной на рисунке 1, применимы для широкого класса задач, а некоторые из них обладают хорошими корреляционными свойствами. Фак­тически таким способом при соответствующем выборе n, f и начального состояния сдвигающего регистра может быть получена любаянапе­ред заданная двоичная последовательность.

Однако для многих целей к схеме, изображенной на рис.1, удобнее добавить «выходную логи­ку» g(x₁, x₂,…, x_n), как показано на рис. 2.

Основным преимуществом последней схемы является то, что «внут­ренняя логика» f (x₁, x₂,…, x_n) и сдвигающий регистр могут быть ис­пользованы для формирования некоторой последовательности с требуе­мым периодом р, а внешняя, или вы­ходная, логика может видоизменить ее в любую другую последователь­ность с тем же периодом.

 

Рис. 2. Схема n -разрядного сдвигающего ре­гистра с внешней обратной связью

 

Наиболее распространены и хорошо изучены регистры с обратной связью, в которых f (x₁, x₂,…, x_n) (см. рис. 1.) представляет собой функцию проверки на четность нескольких или всех nее аргу­ментов. В вышеприведенном примере функция   линейна, так как она является функцией проверки на четность x₁ и x₃. Функция равна 1, когда их сумма нечетна, и 0, когда четна.

Последовательность на выходе n-разрядного сдвигающего регистра с обратной связью в конечном счете всегда периодична, причем ее пе­риод р не превышает 2ⁿ. В случае линейного сдвигающего регистра наи­больший период будет р = (2ⁿ – 1) и любая выходная последовательность, имеющая такой период, называется линейной последовательностью мак­симальной длины. Именно таковой является последовательность 1001110 с периодом p = 7 = 2³ – 1.

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

критерий 1 (свойство уравновешенности): в каждом периоде после­довательности число «1» отличается от числа «0» не более чем на единицу;

критерий 2 (свойство серий (серией называется последовательность одинаковых цифр)): в течение периода последовательно­сти половина серий единиц и нулей имеет длину 1, одна четверть - 2, одна восьмая - 3 и т. д. до тех пор, пока это продолжение имеет смысл;

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

При подбрасывании «идеальной монеты» критерий 1 означает, что орел или решка выпадают приблизительно одинаково часто. Критерий 2 соответствует утверждению, что после выпадения орла (или решки) n раз подряд вероятность того, что при следующем подбрасывании вы­падет орел (или решка), равна половине. И, наконец, критерий 3 озна­чает независимость испытаний: значение результатов предыдущих под­брасываний не дает никакой информации относительно результатов те­кущих подбрасываний.

Пример. На рис. 3 последовательность генерируется четырехразрядным сдвигаю­щим регистром и логическая обратная связь представляет собой функцию проверки на четность содержимого третьего и четвертого разрядов: х ₃и х ₄. Учитывая обозначения предыдущего примера: .

  Здесь функция проверки на четность обозначена  и известна также под названиями «исключенное ИЛИ», «сумма по модулю 2», «функция полусумматора». (В матлабе это оператор xor!) Если начальное состояние сдвигающего регистра 1000 (счи­тая на рис. 1.3 слева направо), то он последовательно примет следующие состояния: 1000, 1100, 0010, ф001, 1100, 0110, 1011, 0101, 1010, 1401, 1110, 1111, 0111, 0011, 0001, 1000. Выходная последовательность (последние цифры каждого состояния) имеет вид 000100110101111 и ее период равен 15.

Рис.3 Схема генератора линейной ПСП максимальной длины на основе 4-х разрядного регистра сдвига с обратной связью

 

Критерий 1 удовлетворяется, так как число единиц в последовательности равно 8, а число нулей равно 7 и «неуравновешенность» не превышает допустимой величины.

Критерий 2 удовлетворяется, так как среди восьми серий (необходимо, чтобы по­ловину всех серий составляли серии единиц и половину — серии нулей, так как се­рии обоих видов должны чередоваться) половина имеет длину 1 (две серии единиц и две серии нулей), четверть — длину 2 (одна серия единиц и одна серия нулей), од­на восьмая — длину 3 (одна серия из трех нулей).

Справедливость критерия 3 можно проверить следующим образом. Если сдвинуть псевдослучайную последо­вательность (пример для n= 4) на один элемент (такт) и затем произвести поразрядное сравнение полученной последовательности и исходной

000100110101111

001001101011110,

то можно увидеть, что в этих двух строках элементы совпадают между собой 7 раз и не совпадают 8 раз, т. е. критерий 3 удовлетворяется. Более того, если сдвигать последовательность на любое число элемен­тов от одного до четырнадцати (так как период последовательности для n = 4 равен p = 2⁴-1 = 15) включительно и затем производить по­разрядное сравнение, то всегда получится семь совпадений и восемь несов­падений.

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

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

Таким образом, все линейные последовательности максимальной длины хотя и являются детерминированными, однако проходят некоторые из основных тестов на случайность. Действительно, почти полная уравнове­шенность единиц и нулей в последова­тельностях, характер распределения длин серий в них, их кажущаяся статистиче­ская независимость служат серьезным основанием для того, чтобы рассматри­вать эти последовательности как истинно случайные. Другими словами, можно с оди­наковой уверенностью утверждать, что последовательность 000100110101111 получена либо при подбрасывании монеты, либо с помощью сдвигающего регистра, изображенного на рис. 1.3.

 

Общая постановка задачи

Для выполнения лабораторной работы необходимо:

· Изучить теоретический материал и ответить на контрольные вопросы.

· Самостоятельно в любой доступной программной среде (Matlab, Any Logic, Excel и т.д.) разработать программные модули, реализующие рассмотренные выше генераторы ПСП в соответствии с исходными данными в приведенной ниже таблице.

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

· Оформить бланк отчета установленным выше образом.