67406

Разработка алгоритмов и программ тестирования генераторов СЧ

Лабораторная работа

Информатика, кибернетика и программирование

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

Русский

2014-09-10

165 KB

1 чел.

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

Государственное образовательное учреждение высшего профессионального образования

Ижевский Государственный технический университет

Чайковский технологический институт (Филиал ИжГТУ)

Кафедра ИВТ

ЛАБОРАТОРНАЯ РАБОТА3,4

по курсу

« Моделирование систем »

Выполнил                                                                                                 студент гр. АСОИиУ-00

А. Л. Юрьев

Руководитель                                                                                доцент,  канд. техн.  наук

                                                                                                                             В. Г. Тарасов                                                                                     

Чайковский 2004

ЦЕЛЬ РАБОТЫ: изучение специализированных тестов для проверки генераторов равномерно распределенных случайных чисел; разработка алгоритмов и программ тестирования генераторов СЧ.

ПОСТАНОВКА ЗАДАЧИ

GRR10, m=2**9, k=3,4,5. Исследовать влияние параметра  k  на апериодичность, добиться значений апериодичности  >= 2**15.

Покер-тест (проверка комбинаций), d=6.

ОПИСАНИЕ ГЕНЕРАТОРА СЧ

Поскольку большая величина периода обеспечивает высокую степень случайности чисел в последовательности, то разработан ряд методов увеличения длин периода. Первый способ состоит в использовании нескольких предыдущих членов последовательности при вычислении числа Xn+1. Если Xn+1 зависит от Xn и Xn-1, то длину периода можно увеличить до m2, так как последовательность начнет повторятся не раньше, чем  будет выполнено равенство

   (xn+i, xn+i+1) = (xn, xn+1).

Простейший случай зависимости Xn+1 от более чем одного из предыдущих значений реализуется в последовательности Фибоначчи (обозначим GRR9):

  xn+1= (xn+xn-1) mod m.

Можно также применить датчики вида GRR10

  xn+1= (xn+xn-k) mod m,

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

ОПИСАНИЕ ПРОВЕРКИ ГСЧ

Покертест (проверка комбинаций) В этом случае величина d берется небольшой, поэтому и диапазон элементов последовательности <Jn>=<Rn>*d также невелик, и значения <Jn> называют цифрами. Например, при d=8 значения 0 Jn  7 являются восьмеричными цифрами, а при d=10 значения будут десятичными цифрами. В “классическом” покер-тесте рассматриваются N групп из пяти следующих друг за другом целых чисел (J5j, J5j+1,..., J5j+4), 0 j N. Выделяются следующие 7 типов комбинаций, отличающихся различным содержанием цифр. abcde (все разные) aabcd (одна пара) aabbc (две пары) aaabc (три одного вида) aaabb (полный сбор) aaaab (четыре одного вида) aaaaa (пять одного вида) Таким образом, количество классов категорий равно 7, и с помощью критерия 2 проверяется, соответствует ли эмпирические частоты комбинаций теоретическим вероятностям их появления. Предполагая, что каждая из цифр 0,1, ..., d-1 в последовательности J0, J1,... появляется с одинаковой вероятностью , и что отдельные члены этой последовательности независимы, можно определить распределение вероятностей различных пятерок с помощью следующих формул:

 

 

 

Значения этих вероятностей указаны в табл.1 для наиболее часто используемых d=2,4,6,8,10.

Покер-тест применяют для проверки не только равномерно распределенных, но и случайных чисел с произвольным законом распределения. Процедура формирования вспомогательной последовательности <Jn> при этом следующая. Пусть X1, X2, ... последовательность случайных чисел с функцией распределения F. Разделим область значений этой случайной величины на d равновероятных интервалов с помощью точек a0<a1<a2<...<ad-1<ad. Если случайные числа Xj действительно имеют функцию распределения F, то для каждого интервала [ai-1,ai) имеет место равенство  P{aj-1 xj < ai} = 1/d.

D=

2

4

6

8

10

abcde

0

0

0,092593

0,205078

0,3024

aabcd

0

0,234375

0,462963

0,512695

0,504

aabbc

0

0,117188

0,231481

0,153809

0,108

aaabc

0

0,234375

0,154321

0,102539

0,072

aaabb

0,625

0,117188

0,03858

0,01709

0,009

aaaab

0,3125

0,058594

0,01929

0,008545

0,0045

aaaaa

0,0625

0,003906

0,000772

0,000244

0,0001

Выполняя преобразование Jj=i для Xj[ai, ai+1), i=0, 1, 2, ... ,  d-1, как раз и получим вспомогательную последовательность случайных чисел <Jn>, каждое из которых принимает только равновероятные значения 0, 1, 2, ..., d-1.

Табл.1.


ТЕКСТ ПРОГРАММЫ

unit GRR10;

interface

uses

 Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

 Dialogs, StdCtrls, Spin, ExtCtrls;

type

 TForm1 = class(TForm)

   ListBox1: TListBox; L1: TLabel;    L3: TLabel;    L2: TLabel;

   Label1: TLabel;    Label2: TLabel;    Label3: TLabel;    Label4: TLabel;

   Edit1: TEdit;    Edit2: TEdit;    Edit3: TEdit;    Edit4: TEdit;

   Edit5: TEdit;    Edit6: TEdit;    Label5: TLabel;    Bevel1: TBevel;

   Label6: TLabel;    Label7: TLabel;    Label8: TLabel;    Label9: TLabel;

   Label91: TLabel;    Label81: TLabel;    Label71: TLabel;    element: TSpinEdit;

   m: TSpinEdit;    k: TSpinEdit;    Button1: TButton;    Button2: TButton;

   Button3: TButton;    Shape1: TShape;    Shape2: TShape;    Shape3: TShape;

   Shape4: TShape;    Label10: TLabel;

   procedure Button1Click(Sender: TObject);

   procedure Button2Click(Sender: TObject);

   procedure Button3Click(Sender: TObject);

 private

   { Private declarations }

 public

   { Public declarations }

 end;

const

 symb:array [1..5] of char=('a','b','c','d','e');

var

 Form1: TForm1;

 i,i1,i2,i3,n:longint;

 x:array [1..330010] of integer;

 y:array [1..330010] of byte;

 s1,s2:array [1..66002] of string[5];

implementation

{$R *.dfm}

PROCEDURE TForm1.Button1Click(Sender: TObject);

begin

for i:=1 to element.Value do x[i]:=0;

Label3.Caption:=timetostr(time); ListBox1.Clear;

 {начальные значения}

n:=k.Value+1;

 if n>=1 then x[1]:=strtoint(Edit1.Text){20{};

if n>=2 then x[2]:=strtoint(Edit2.Text){31{};

if n>=3 then x[3]:=strtoint(Edit3.Text){82{};

if n>=4 then x[4]:=strtoint(Edit4.Text){58{};

if n>=5 then x[5]:=strtoint(Edit5.Text){63{};

if n>=6 then x[6]:=strtoint(Edit6.Text){1{};

for i:=1 to n do

 ListBox1.Items.Add(inttostr(i)+'   '+inttostr(x[i]));

{***генератор случайных чисел***}

REPEAT

x[n+1]:=(x[n]+x[n-k.Value]) mod m.Value;

n:=n+1;

ListBox1.Items.Add(inttostr(n)+')   '+inttostr(x[n])+'   ');

UNTIL n>=element.Value;

{***^^^^^^***}

Label4.Caption:=timetostr(time);

end;

{*** Периодичность ***}

PROCEDURE TForm1.Button2Click(Sender: TObject);

var stroka1,stroka2:string;

label met1, met2, met3;

begin

Label3.Caption:=timetostr(time); i3:=0;

{вычисление периода и апериода}

REPEAT

  i3:=i3+1;

  stroka1:='';

  if (i3>=(element.Value-k.Value)) then goto met2;

  for i1:=i3 to i3+k.value do stroka1:=stroka1+' '+inttostr(x[i1]);

 FOR i:=i3 to element.Value do

 Begin

  stroka2:='';

  for i2:=i+1 to i+1+k.value do

   stroka2:=stroka2+' '+inttostr(x[i2]);

   if stroka1=stroka2 then

    begin

     label1.Caption:=stroka1+' / '+stroka2;

     goto met1;

    end;

 End;

UNTIL (i3>=(element.Value-k.Value));

met1: label2.Caption:='Длина Периода= '+inttostr(i-(i3-1))+',  Апериод= '+inttostr(i);

goto met3;

met2: label2.Caption:='Длина периода больше '+inttostr(element.Value);

met3: Label4.Caption:=timetostr(time);

end;

{*** Покер-тест ***}

PROCEDURE TForm1.Button3Click(Sender: TObject);

var d6:byte;

   a,b,c,d,e:byte;

   aaaaa,abcde,aaaab,aaabb,aaabc,aabbc,aabcd,kol,elem:longint;

   kl:array[1..7] of longint;

begin

for i:=1 to 66002 do begin s1[i]:='';s2[i]:=''; end;

 d6:=6; n:=0; ListBox1.Clear;

{получение вспомогательной последовательности с диапазоном <0,1,2,3,4,5>}

 for i:=1 to element.Value do

 begin

  y[i]:=trunc((x[i]/m.Value)*d6);

 end;

{получение последовательностей из цифр по пять в каждой

например, 01211; 12355; 33333 и т.п.}

for i:=1 to element.Value div 5 do

  for i1:=1 to 5 do

   begin

    n:=n+1;

    s1[i]:=s1[i]+inttostr(y[n]);

    s2[i]:=s2[i]+inttostr(y[n]);

   end;

{преобразование последовательностей из цифр в

последовательности abcde,aabcd,aaabcd,aabbc,aaabb,aaaab,aaaaa}

 for i2:=1 to element.Value div 5 do

for i:=1 to 5 do

 for i1:=1 to 5 do

  if s1[i2][i1]=s2[i2][i] then s1[i2][i1]:=symb[i];

{поиск классов (все разные, одна пара, две пары и т.д.)}

aaaaa:=0;abcde:=0;aaaab:=0;aaabb:=0;aaabc:=0;aabbc:=0;aabcd:=0;kol:=0;

 FOR i1:=1 to element.Value div 5 DO

Begin

 a:=0;b:=0;c:=0;d:=0;e:=0;

 for i2:=1 to 5 do

  for i3:=1 to 5 do

   if s1[i1][i3]=symb[i2] then

    begin

     if symb[i2]='a' then a:=a+1;

     if symb[i2]='b' then b:=b+1;

     if symb[i2]='c' then c:=c+1;

     if symb[i2]='d' then d:=d+1;

     if symb[i2]='e' then e:=e+1;

    end;

  {Распределение по классам}

  if (a=1)and(b=1)and(c=1)and(d=1)and(e=1) then abcde:=abcde+1 {Все разные} else

  if (a=5) then aaaaa:=aaaaa+1 {Пять одного вида} else

  if (a=4)or(b=4) then aaaab:=aaaab+1 {Четыре одного вида} else

  if ((a=2)and(b=3))or

     ((a=3)and(b=2))or

     ((a=3)and(c=2))or

     ((a=3)and(d=2))or

     ((a=2)and(c=3)) then aaabb:=aaabb+1 {Полный сбор} else

  if (a=3)or(b=3)or(c=3) then aaabc:=aaabc+1 {Три одного вида} else

  if ((a=2)and(b=2))or

     ((a=2)and(c=2))or

     ((b=2)and(c=2))or

     ((a=2)and(d=2))or

     ((b=2)and(d=2)) then aabbc:=aabbc+1 {Две пары} else aabcd:=aabcd+1 {Одна пара};

{^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^}

End;

kol:=aaaaa+abcde+aaaab+aaabb+aaabc+aabbc+aabcd;

 {сортировка классов от меньшего к большему}

  kl[1]:=aaaaa;kl[2]:=abcde;kl[3]:=aaaab;kl[4]:=aaabb;

  kl[5]:=aaabc;kl[6]:=aabbc;kl[7]:=aabcd;

 for i1:=1 to 7 do

  begin

   for i2:=i1 to 6 do

   begin

     elem:=kl[i1];

     if elem>kl[i2+1] then //по не убыванию - >

     begin

       kl[i1]:=kl[i2+1];

       kl[i2+1]:=elem;

     end;

   end;

  end;

{вывод результатов на экран (в Label)}

 label10.Caption:='N * P(min) = '+floattostr(element.Value*(kl[1]/kol));

 label7.Caption:=  'a= '+inttostr(a)+';  b= '+inttostr(b)+';  c= '+inttostr(c)+

                ';  d= '+inttostr(d)+';  e= '+inttostr(e)+';';

 label71.Caption:='Сумма P(1..7) = '+floattostr((abcde/kol)+(aabcd/kol)+

                  (aabbc/kol)+(aaabc/kol)+(aaabb/kol)+(aaaab/kol)+(aaaaa/kol));

 label8.Caption:=         'kol= '+inttostr(kol)+'; '

                 +'  (1) abcde= '+inttostr(abcde)

                +';  (2) aabcd= '+inttostr(aabcd)

                +';  (3) aabbc= '+inttostr(aabbc)

                +';  (4) aaabc= '+inttostr(aaabc)+';';

 label81.Caption:=  '(5) aaabb= '+inttostr(aaabb)

                +';  (6) aaaab= '+inttostr(aaaab)

                +';  (7) aaaaa= '+inttostr(aaaaa);

 label9.Caption:=   'P(1)= '+floattostr(abcde/kol)+

                 ';  P(2)= '+floattostr(aabcd/kol)+

                 ';  P(3)= '+floattostr(aabbc/kol)+

                 ';  P(4)= '+floattostr(aaabc/kol)+';';

 label91.Caption:=  'P(5)= '+floattostr(aaabb/kol)+

                 ';  P(6)= '+floattostr(aaaab/kol)+

                 ';  P(7)= '+floattostr(aaaaa/kol);

{вывод пятерок на экран (в LISTBOX)}

 ListBox1.Clear;

for i:=1 to element.Value div 5 do

ListBox1.Items.Add(inttostr(i)+')   '+s1[i]+'   ');

end;

end.

РЕЗУЛЬТАТЫ РАБОТЫ ПРОГРАММЫ


 

А также другие работы, которые могут Вас заинтересовать

42803. Электроиндуцированные упругие деформации в кристаллах ниобата лития 329.46 KB
  Точечная группа симметрии: 3m. Приложено электрическое поле В см под углом 600 к главной оси симметрии. Область науки в задачу которой входит описание и объяснение структуры кристаллов на основе законов симметрии и пространственных соотношений расстояний между атомами называется кристаллографией. Поскольку в данном кристалле имеется ось симметрии третьего порядка то использование метода прямой проверки в декартовых координатах невозможно.
42804. Разработка программного обеспечения, ведение базы данных “Прокат видеокассет” 2.21 MB
  Видеотека Имя поля Тип данных Названиеописание Длина поля Код кассеты Numeric Указывается код видеокассеты. 5 Жанр Numeric Указывается жанр фильма. 10 Наименование Chrcter Указывается название кассеты. 18 Режиссер Chrcter Указывается режиссер данной видеокассеты.
42805. Сравнительная характеристика автоматической двухшпиндельной вакуум-закаточной машины 2.16 MB
  1 СВЕДЕНИЯ ОБ ОБЬЕКТЕ ОБРАБОТКИ Для производства жестяных банок необходима жесть уплотняющие материалы. При производстве цельно штамповочных банок требуется жесть уплотняющие материалы и материал для смазки жести перед штамповкой банок. Кроме того для производства консервных банок используют белую лакированную жесть электролитического лужения она более экономична так как толщина оловянного покрытия составляет 061мКр. Жесть черная рулонная лакированная применяют для...
42806. Использование переходных металлов и их соединений в технологии сенсорных микро-наносистем 313.59 KB
  Настоятельная необходимость отслеживать все аспекты состояния окружающей среды в реальном времени постоянно растет, и это вызвано возрастающими связями загрязнения окружающей среды с нашим здоровьем и безопасностью. Необходимо также иметь возможность определять содержание основных компонентов и примесей в различных средах.
42807. Анализ конструкции мобильного телефона Samsung i8910 HD с использованием методик FMEA и FTA 7.54 MB
  Попытки научного подхода к оценке качества предпринимались давно. Так, еще в 1930 г. немецкий доктор-инженер К. Комментц установил для кораблей, предназначенных для мелководья, что всякое уменьшение осадки судов на 1 % приводит к повышению цены на 0,6%. Несколько более сложным у него оказалось влияние вместимости судна и других параметров качества.
42808. Технология швейного производства на примере РУП «БХПО» 2.6 MB
  Совершенствование швейного производства предусматривает внедрение высокопроизводительного оборудования поточных линий расширение ассортимента и улучшение качества одежды выпуск изделий пользующихся повышенным спросом. Технология современного швейного производства все более становится механической ее эффективность в первую очередь зависит от применяемого оборудования. Выбор швейного оборудования зависит от особенностей обрабатываемых изделий и материалов. Механизация и автоматизация производства приводит к расширению перечня используемого...
42809. Система управления перемещением механизма 1.74 MB
  Функциональная схема установки На функциональной схеме введены следующие обозначения: КВ КН контакторы движения: вперёд и назад; S1 S2 S3 сигнал с конечным выключателем положений 1 2 3; S4 сигнал с кнопки; S5 сигнал с кнопки “Стоп†в режиме автомат; S6 сигнал выбора режима автомат или наладка; S7 сигнал движения вперёд в режиме наладка; S8 сигнал движения назад в режиме наладка; ПУУ проектирующие управляющие устройство; УВВ устройство выдержки времени; Хв сигнал управления контактором движения вперёд; Хн сигнал...
42810. Расчет районной электрической сети 471.49 KB
  1 Расчет баланса мощности 6 1.1 Расчет баланса мощности 1 Определение полной мощности для каждого потребителя: Таблица 1: Сведения о потребителях N P МВт cosϕ Uн кВ 1 33 094 10 2 34 092 10 3 134 078 6 4 34 085 10 2 Определение реактивной мощности для каждого потребителя: 3 Определение потерь активной мощности: Принимаем что они равны 5 от активной мощности iго потребителя 4 Определение реактивных потерь: Зарядную мощность линий а также потери реактивной мощности в линии не учитываем. Принимаем что они составляют 6 от...
42811. Мораль: понятие, источники, значение для Современной России 56.98 KB
  Особая роль принадлежит морали в формировании сознания, внутреннего мира и мировоззрения, активной жизненной позиции, мораль является важнейшим социальным регулятором, который входит в систему общественных отношений. Мораль имеет серьезное воздействие на развитие совершенствование многих сфер человеческой жизнедеятельности, поскольку она присуща всем сферам, где есть контакт между людьми.