Генератори імпульсних послідовностей з пуассонівським законом розподілу

Размещено на http://www.allbest.ru/

Національний університет “Львівська політехніка”

УДК 681.3

ГЕНЕРАТОРИ ІМПУЛЬСНИХ ПОСЛІДОВНОСТЕЙ З ПУАССОНІВСЬКИМ ЗАКОНОМ РОЗПОДІЛУ

05.13.05 - елементи та пристрої обчислювальної техніки

та систем керування

Автореферат

дисертації на здобуття наукового ступеня

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

Гарасимчук Олег Ігорович

Львів 2007

Дисертацією є рукопис

Робота виконана у Національному університеті “Львівська політехніка” Міністерства освіти і науки України

Науковий керівник - кандидат технічних наук, доцент Максимович Володимир Миколайович, доцент кафедри “Захист інформації” Національного університету “Львівська політехніка”, м. Львів.

Офіційні опоненти - доктор технічних наук, професор Самотий Володимир Васильович, професор кафедри “Комп'ютеризовані системи автоматики” Національного університету “Львівська політехніка”, м. Львів.

кандидат технічних наук, доцент Паламар Михайло Іванович, завідувач кафедри “Прилади і контрольно-вимірювальні системи” Державного технічного університету ім. І. Пулюя, м. Тернопіль.

Захист дисертації відбудеться 21 вересня 2007 року о 11 годині на засіданні спеціалізованої вченої ради Д 35.052.08 у Національному університеті “Львівська політехніка” (79013, Львів-13, вул. С.Бандери, 12, ауд 226 головного корпусу).

З дисертацією можна ознайомитись у бібліотеці Національного університету “Львівська політехніка”, (79013, Львів, вул. Професорська, 1).

Автореферат розісланий 20 серпня 2007 р.

Вчений секретар спеціалізованої

вченої ради, д.т.н., проф. Луцик Я.Т.

Загальна характеристика роботи

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

На даний час, генератори випадкових і псевдовипадкових імпульсних послідовностей широко використовуються:

в криптографії - для шифрування, розшифрування та генерації ключів;

в імітаційному моделюванні - для математичних, економічних, медичних і фізичних досліджень, а також в моделюванні у військовій справі;

у вимірювальній техніці - як складові блоки вимірювальних приладів або для їхнього тестування;

при розробці комп'ютерних ігор.

Важливе місце серед таких генераторів займають генератори пуассонівських імпульсних послідовностей (ГПІП). Вони широко застосовуються в різних галузях науки і техніки, в системах зв'язку, а також в багатьох фізичних і біологічних системах. ГПІП, в залежності від мети і сфери застосування, можуть бути реалізовані апаратними та програмними засобами.

Основними вимогами, що стоять перед розробниками ГПІП є наступні:

простота апаратної або програмної реалізації;

максимальна швидкодія;

максимальна наближеність до теоретичного закону розподілу;

можливість керування вихідними параметрами;

можливість роботи в широкому діапазоні частот;

можливість переналагодження.

Незважаючи на велику кількість публікацій, що стосуються побудови і дослідження характеристик генераторів випадкових чисел (ГВЧ) та генераторів псевдовипадкових чисел (ГПВЧ), що входять до складу ГПІП, практично відсутні роботи, в яких наведений порівняльний аналіз характеристик ГПІП і сформульовані чіткі рекомендації стосовно їхнього проектування і використання. Отже, на даний час, існує ряд невирішених задач, пов'язаних з розробкою ГПІП.

ГПІП можуть бути ефективно реалізовані за допомогою сучасних досягнень в галузі обчислювальної техніки ? з використанням мікропроцесорної техніки або на основі програмованих логічних інтегральних схем (ПЛІС).

Однією з важливих задач дослідження якості ГПІП є вибір групи тестів, на основі яких можна з певною ймовірністю вважати, що згенерована псевдовипадкова послідовність буде мати розподіл наближений до пуассонівського.

Зв'язок роботи з науковими програмами, планами, темами. Основний зміст дисертаційної роботи складають результати теоретичних і практичних розробок, проведених автором під час виконання держбюджетних робіт згідно з галузевим тематичним планом впровадження дослідно-конструкторських робіт Міністерства освіти і науки України, розділ “Заряд”, за 2004 р, № державної реєстрації - 0104U002297.

Мета і задача дослідження. Метою роботи є розроблення нових методів і засобів побудови ГПІП, порівняльний аналіз їхніх характеристик, вибір групи тестів для оцінки їхньої якості.

Згідно з поставленою метою задачами дослідження є:

пошук алгоритмів для генерування пуассонівського імпульсного потоку, їх аналіз і класифікація;

створення універсальних ГПІП з простою апаратною реалізацією, великими швидкодією і періодом повторення, можливістю керування вихідними параметрами;

вибір групи тестів для оцінки якості псевдовипадкових імпульсних послідовностей з пуассонівським законом розподілу;

аналіз основних характеристик розроблених генераторів;

програмна і апаратна реалізація ГПІП.

Об'єкт дослідження - процес генерування пуассонівських імпульсних послідовностей. генератор пуассонівський імпульсний послідовність

Предмет дослідження - алгоритми та апаратні засоби для реалізації ГПІП, методи оцінки їхньої якості;

Методи дослідження - теоретичні дослідження базуються на використанні основних положень теорії цифрових автоматів, теорії ймовірності, теорії похибок. Для підтвердження правильності теоретичних досліджень і розробок використані методи комп'ютерного моделювання.

Наукова новизна одержаних результатів:

· проведено аналіз алгоритмів функціонування та принципів побудови ГПІП на основі ГПВЧ, що дало можливість визначити підходи до побудови останніх з точки зору забезпечення кращих статичних і статистичних характеристик пуассонівських імпульсних послідовностей;

· проведений аналіз принципів побудови ГПВЧ, реалізованих на базі лінійного конгруентного методу, дозволив визначити параметри конгруентних рівнянь, що забезпечують кращі характеристики вихідної імпульсної послідовності і запропонувати нові число-імпульсні структури ГПІП;

· в результаті проведеного аналізу твірних поліномів та матричних рівнянь, що описують роботу ГПВЧ на базі генераторів М-послідовностей, обґрунтовано вибір типу і степеня матриць та вперше запропоновані нові швидкодіючі структури ГПІП реалізовані на їх основі;

· розроблено і досліджено новий математичний алгоритм формування пуассонівської імпульсної послідовності, призначений для програмної реалізації;

· запропоновано удосконалений набір тестів для оцінки якості ГПІП, що включає в себе тестування ГПВЧ і визначення статистичних характеристик вихідної імпульсної послідовності з пуассонівським законом розподілу.

Практичне значення одержаних результатів:

· розроблені алгоритми формування ГПІП дозволяють створювати моделі джерел псевдовипадкових імпульсних сигналів, що можуть бути використані в процесі проектуванні вимірювальних (зокрема дозиметричних) пристроїв;

· розроблені апаратні засоби можуть бути використані під час створення нестандартного обладнання для забезпечення налагодження і метрологічної атестації вимірювальних пристроїв;

· запропонований набір тестів дозволяє виконувати аналіз статичних і статистичних характеристик ГПІП з урахуванням можливої зміни параметрів конгруентних і матричних рівнянь, що описують роботу ГПВЧ;

· запропоновані базові генератори та ряд рекомендацій дисертаційної роботи успішно використовуються для побудови імітаторів радіаційного випромінювання, під час налагоджування і випробування дозиметричних пристроїв у ПП “НВПП “Спаринг-Віст Центр” (м. Львів), що дозволяє уникнути роботи з фізичними джерелами випромінювання;

· розроблений пакет прикладних програм та рекомендації, наведені в дисертаційній роботі, використовуються в Національному університеті “Львівська політехніка”, на кафедрі “Захист інформації” в курсі “Захист інформації від несанкціонованого доступу в автоматизованих системах обробки даних”.

Особистий внесок здобувача:

Основні положення та результати дисертаційної роботи отримані автором самостійно. У друкованих працях, опублікованих у співавторстві, автору належать: [1] - класифікація і сфери застосування генераторів випадкових та псевдовипадкових чисел; [2,8] - алгоритм формування пуассонівського імпульсного потоку; [3] - метод оцінки якості псевдовипадкових імпульсних послідовностей з пуассонівським законом розподілу за допомогою відносної похибки; [4] - структурна схема формування імпульсного потоку; [5] - структурні схеми генераторів М-послідовностей і вибір тестів для оцінки їхньої якості; [6] - оцінка якості базового конгруентного генератора та визначення характеристик вихідного сигналу ГПІП на основі статистичного критерію ; [7] - оцінка якості базового генератора М-послідовностей та визначення характеристик вихідної імпульсної послідовності ГПІП на основі статистичного критерію .

Апробація результатів дисертації:

Основні результати роботи доповідались на:

1. VII Міжнародній конференції “Контроль і управління в складних системах (КУСС-2003)”, присвяченій 75-річному ювілею професора Іваненка В.І., у м.Вінниця 8-12 жовтня 2003 року.

2. ІІІ Всеукраинской научно-практической конференции “Информационные технологии и безопасность в управлении”. Крым, г. Ялта, пгт. Ливадия, 18-22 сентября 2006 г.

3. Міжвідомчих міжрегіональних семінарах Наукової Ради НАН України “Технічні засоби захисту інформації”, Львівське відділення: 14.02.02 р., 07.11.02 р., 26.02.04 р., 04.11.04 р., 09.03.06 р.

Публікації:

За тематикою дисертаційної роботи опубліковано 9 наукових праць, серед яких 7 статей у фахових виданнях, 1 - у тезах міжнародної конференції, 1 - у тезах всеукраїнської конференції.

Структура та обсяг дисертації. Дисертаційна робота складається із вступу, чотирьох розділів і висновків, викладених на 114 сторінках друкованого тексту, містить 36 рисунків, 37 таблиць, список використаних джерел з 101 найменування і додатків. Загальний обсяг дисертації становить 157 сторінок.

Основний зміст роботи

У вступі обґрунтовано актуальність теми дисертаційної роботи, зазначено зв'язок з держбюджетним галузевим тематичним планом впровадження дослідно-конструкторських робіт. Сформульовано мету та задачі дослідження, висвітлена наукова новизна та практична цінність роботи. Наведено відомості про впровадження результатів роботи, їх апробацію та публікації.

У першому розділі наведені характеристики імпульсних послідовностей з пуассонівським законом розподілу, результати аналізу принципів побудови ГПВЧ та ГПІП на їх основі. Запропонована класифікація ГПВЧ наведена на рис. 1.

Розглянуто різні способи побудови ГПВЧ:

- лінійні конгруентні генератори, що функціонують у відповідності з виразом

; (1)

- поліноміальні конгруентні генератори -

; (2)

- адитивні генератори Фібоначі -

, (3)

(де X_n-1, X_n, X_n+1 - значення псевдовипадкових чисел на тактах n-1, n, n+1 роботи пристрою; a, b, a_і - коефіцієнти конгруентних рівнянь; m - модуль рівнянь);

- стандартні генератори алгоритмічних мов програмування;

- генератори М-послідовностей.

Проведено аналіз матричних рівнянь генераторів М-послідовностей:

, (4)

де і - стани регістра генератора в моменти часу t і t+1 відповідно (до і після приходу синхроімпульсу), T - квадратна матриця порядку N вигляду

або , (5)

N - степінь примітивного полінома

, (6)

а r - натуральне число.

Проаналізовано основні області застосування ГПІП.

Розглянуто методи оцінки якості псевдовипадкових послідовностей, а саме дві групи тестів:

1. Графічні тести - за допомогою яких користувач отримує певні графічні залежності і робить висновки про властивості псевдовипадкової послідовності, що тестується.

2. Оціночні тести - тести, в яких на основі певних критеріїв, отримують кількісні дані і робиться висновок про степінь близькості статистичних властивостей псевдовипадкової послідовності, що тестується, до заданих параметрів.

У другому розділі запропонована загальна структурна схема ГПІП, в якій середня частота вихідних імпульсів є керованою.

Структура ГПІП, зображенена на рис.2, складається з ГПВЧ, схеми порівняння СП і логічного елементу І.

З кожним вхідним імпульсом, частота повторення яких дорівнює f_t, на виході ГПВЧ формуються псевдовипадкові числа D з рівномірним законом розподілу. У випадку, коли виконується умова D<G, на виході СП формується сигнал, який дозволяє черговому вхідному імпульсу пройти на вихід генератора.

Середню частоту повторення вихідних імпульсів ГПІП визначають за формулою

, (7)

де А - максимально можливе значення числа на виході ГПВЧ.

Перевагою такого ГПІП є те, що середньою частотою слідування вихідних імпульсів можна керувати змінюючи: значення G; тактову частоту генератора f_t; кількість розрядів ГПВЧ.

В результаті імітаційного моделювання були знайдені оптимальні параметри базових генераторів рівномірно розподілених псевдовипадкових чисел та досліджені їхні характеристики.

Запропоновані структурні схеми ГПІП з використанням, як базового, лінійного конгруентного генератора, одна з яких наведена на рис. 3.

В склад ГПІП входять два комбінаційні суматори КС1 і КС2, регістри РГ1 і РГ2, схема множення СМ, схема порівняння СП і логічний елемент І. Робота пристрою полягає в реалізації лінійного конгруентного методу формування псевдовипадкових чисел згідно рівняння (1).

Кожен вхідний імпульс генератора викликає формування на виході СМ серії з a імпульсів. На виході нагромаджувального суматора, побудованого на комбінаційному суматорі КС1 і регістрі РГ1, формується добуток a•X_n. Число a•X_n+b формується на виходах КС2, а поточні значення X_n зберігаються в s молодших розрядах регістра РГ2. Поновлення чисел в РГ2 та обнулення вмісту РГ1 проводиться вхідними імпульсами пристрою. При умові X_n+1<G, на виході СП формується логічний рівень, який пропускає вхідний імпульс через логічний елемент І на вихід генератора.

Для лінійного конгруентного генератора знайдено ряд оптимальних параметрів, зокрема, значення a=105, b=12345, m=2³⁰ для рівняння (1). В процесі дослідження, спочатку були протестовані псевдовипадкові послідовності вихідних чисел ГПВЧ на рівномірність і випадковість розподілу, у тому числі за допомогою тесту “розподіл на площині” (рис.4), де X_n, X_n-1 ? чергове та попереднє значення псевдовипадкового числа відповідно. Площина заповнена повністю і безсистемно, що дає підстави зробити попередній висновок про придатність даного варіанту для подальших досліджень ГПІП.

В результаті проведеного аналізу було додатково вибрано сім оціночних тестів, за допомогою яких можна оцінити якість псевдовипадкової послідовності чисел. Результати тестування лінійного конгруентного генератора наведено в табл. 1.

В таблиці “+” означає, що тест пройдено. Отже, при правильному виборі параметрів лінійного конгруентного генератора, він проходить всі тести на випадковість і рівномірність розподілу, що свідчить про його високу якість.

Таблиця 1

Результати оціночного тестування лінійного конгруентного генератора

Вид оціночного тесту	imaxnmax
	5000000	50000000
Перевірка кореляції	+	+
Перевірка перестановок, що пересікаються	+	+
Перевірка на монотонність	+	+
Перевірка перестановок	+	+
Тест дірок	+	+
Перевірка незціплених серій	+	+
Частотний монобітний тест	+	+

Для оцінки якості ГПІП отримана за допомогою базового генератора псевдовипадкова рівномірно розподілена послідовність розбивається на інтервали i_max. Кількість чисел в інтервалі i_max може бути довільною, але достатньо великою. Кількість таких інтервалів n також є довільною і змінюється в межах 0<n<n_max. При цьому необхідно, щоб виконувалась умова

, (8)

де T ? період повторення значень чисел.

При дослідженні вихідної імпульсної послідовності на відповідність пуассонівському закону розподілу був використаний наступний аналітичний підхід.

Середня кількість імпульсів, що може бути зафіксована на виході ГПІП за час вимірювання T_B, обчислюється за формулою

. (9)

Кількість імпульсів пуассонівського імпульсного потоку, зафіксована за час T_B:

а) з надійною ймовірністю p=0,68 знаходиться в межах

; (10)

б) з надійною ймовірністю p=0,95 ? в межах

; (11)

в) з надійною ймовірністю p=0,997 ? в межах

. (12)

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

Статистичні характеристики ГПІП наведено на рис. 5 і в табл. 2. Тут k -кількість імпульсів на виході ГПІП за час T_B, а n - кількість інтервалів часу T_B. Межі вказані згідно формули (11), де

і . (13)

Таблиця 2

Результати оцінювання ГПІП, побудованого на основі лінійного конгруентного генератора, згідно формул (10) - (12)

Значення і	Діапазон дослідження (значення )	Кількість значень , що виходить за межі згідно формул (10) - (12)
		для =0,95	для =0,68	для =0,997
=1000 Гц, =0,01 с	0 - 100	5	26	0
	100 - 200	3	24	0
	200 - 300	4	28	1
	300 - 400	5	30	1
	400 - 500	1	26	0
=100 Гц, =0,1 с	0 - 100	4	27	1
	100 - 200	2	26	0
	200 - 300	5	21	0
	300 - 400	5	27	1
	400 - 500	4	31	1

Як видно з таблиці, псевдовипадкові послідовності на виході ГПІП володіють статистичними властивостями, наближеними до теоретично визначених, що становлять для p=0,95 - 5, для p=0,68 - 32, для p=0,997 - 0,3.

Також виконано оцінку якості вихідної послідовності ГПІП за допомогою оціночного критерію . Результат такого оцінювання наведено в табл. 3.

Таблиця 3

Кількісна оцінка ГПІП на основі статистичного критерію

	при =1000 Гц і =0,01 с;	при =100 Гц і =0,1 с;
Результат тестування	тест пройдено	тест пройдено

Аналогічні дослідження були виконані для ГПІП реалізованих на основі поліноміального конгруентного генератора, адитивного генератора Фібоначі та стандартного генератора random алгоритмічної мови Delphi.

Для поліноміального конгруентного генератора були, зокрема, знайдені наступні оптимальні параметри: a₂=2, a₁=115, b=12345, m=2³⁰ (2); для адитивного генератора Фібоначі: Х_n-1=0; Х_n=1234567, m=2³⁰ (3).

Оцінювання з допомогою тесту “розподіл на площині” показало, що всі вище згадані генератори, при правильно підібраних параметрах, мають рівномірний та випадковий розподіл. Кількісне оцінювання цих ГПВЧ і ГПІП, реалізованих на їх основі, довело, що вони, за винятком поліноміальних конгруентних генераторів, володіють властивостями наближеними до теоретично визначених, оскільки успішно проходять переважну більшість тестів.

Поліноміальний конгруентний генератор пройшов лише частину тестів і в загальному, ГПІП реалізований на його основі, не володіє характеристиками наближеними до теоретичних. На цьому прикладі видно, що використання лише одного тесту (а не групи тестів) може бути помилковим при побудові ГПІП.

Також був запропонований наступний математичний алгоритм генерування псевдовипадкових чисел з законом розподілу наближеним до рівномірного

, (14)

де i=1... i_max, n=1...n_max; j=10^s, де k і s - цілі числа.

Генератор на основі системи (14), може бути використаний як базовий для побудови ГПІП, в-першу чергу в тих випадках, коли реалізація ГПІП виконується програмно. До переваг цього алгоритму можна віднести простоту програмної реалізації, можливість швидкого переналагодження і високу швидкодію, а до недоліків - відносну складність апаратної реалізації.

В результаті імітаційного моделювання були визначені оптимальні значення параметрів, зокрема: j=10⁹, k=10⁸. Результати розподілу на площині та результати тестування за допомогою групи з семи запропонованих вище оціночних тестів дають підстави зробити попередній висновок про придатність даного варіанту для подальших досліджень ГПІП. Кількісні оцінки ГПІП, побудованого на основі запропонованого математичного алгоритму (14), за допомогою формул (10) - (12) і статистичного критерію , також були позитивними.

У третьому розділі запропоновано принципи вибору базового генератора М-послідовностей і ГПІП реалізованих на його основі.

Досліджені різні способи побудови генераторів М-послідовностей в залежності від вибору матриці (T₁ чи T₂), з допомогою яких описується робота цих генераторів, та в залежності від вибору твірного поліному і для різних значень r ? степеня матриці. В результаті імітаційного моделювання ГПІП на основі генераторів М-послідовностей для різних степеней r, запропоновано використовувати значення r=10. Це зумовлено тим, що результати моделювання та оцінка якості доводять, що для значень r>6, псевдовипадкова послідовність згенерована за допомогою генератора М-послідовностей має розподіл близький до рівномірного і є випадково розподілена. Побудовані на основі такого генератора ГПІП мають розподіл більш наближений до теоретичного пуассонівського в порівнянні з ГПІП побудованими для менших значень r. Також не варто будувати ГПІП для дуже великих значень r, оскільки тоді ускладнюється апаратна реалізація такого генератора, а якість ГПІП, побудованого на основі генератора М-послідовностей для значення r=10, мало відрізняється від ГПІП, побудованого на основі генератора М-послідовностей для значень r >10.

В результаті імітаційного моделювання були проаналізовані генератори М-послідовностей реалізовані на основі різних твірних поліномів, зокрема, для твірного поліному (рис. 6).

До складу схеми входять: 31 тригер (відповідно до степеня полінома), на виходах яких зберігається чергове значення псевдовипадкової послідовності і 10 суматорів за модулем 2.

За допомогою групи тестів була виконана оцінка якості даного ГПВЧ. Отримані результати свідчать, що він проходить більшість тестів. Кількісні оцінки ГПІП, побудованого на основі такого генератора, за допомогою формул (10) - (12) і статистичного критерію також були позитивними.

Аналогічні дослідження, виконані для ГПІП на основі генераторів М-послідовностей реалізованих на матриці T₂, у тому числі, для твірного поліному , при r =10.

Генератор, зображений на рис. 7, як і генератор, зображений на рис. 6, складається з 31 тригера і 10 суматорів за модулем 2.

Для даного генератора М-послідовностей також була виконана оцінка якості за допомогою групи тестів, більшість з яких він пройшов. Кількісні оцінки ГПІП, побудованого на основі такого генератора М-послідовностей, за допомогою формул (10) - (12) і статистичного критерію , також були позитивними.

Отже, було ще раз отримане підтвердження того, що ГПІП, які реалізовані на генераторах М-послідовностей (згідно матриць T₁ та T₂), при правильному виборі твірного поліному і степенів матриць r, володіють статистичними властивостями наближеними до теоретичних.

У четвертому розділі розглянуто реалізацію ГПІП на базі ПЛІС.

Були проведені дослідження швидкодії лінійних конгруентних генераторів та ГПІП, в залежності від способу побудови і кількості розрядів їх складових частин (секцій).

За допомогою імітаційного моделювання у системі моделювання Foundation фірми Xilinx та програмування на алгоритмічній мові Delphi проведено оцінювання основних технічних характеристик ГПІП на базі лінійного конгруентного генератора. Результати такого моделювання представлені в табл. 4.

Таблиця 4

Зведена таблиця основних технічних характеристик ГПІП на базі лінійного конгруентного генератора

Кількість розрядів ГПІП	24 розряди	28 розрядів	31 розряд
Кількість розрядів секцій нагромаджувального суматора	4	8	16
Період повторення псевдо-випадкових чисел T	33554432	268435456	1073741824
Мінімальний період тактових імпульсів	40,304 нс	56,116 нс	52,540 нс	40,744 нс	28,866 нс
Максимальна частота тактових імпульсів fмакс	24,811 MГц	17,820 MГц	19,033 MГц	24,543 MГц	34,643 MГц
Максимальна затримка зв'язків	9,065 нс	12,690 нс	11,551 нс	9,777 нс	9,608 нс
Діапазон вихідних частот fв_мінчfв_макс	1,479 Гц - 24,811 MГц	0,066 Гц - 17,820 MГц	0,018 Гц -19,033 MГц	0,023 Гц - 24,543 MГц	0,032 Гц - 34,643 MГц
Надійна ймовірність	Показники якості
p =0,68	28,74%	28,09%	24,10%
p=0,95	4,79%	3,28%	3,20%
p =0,997	0,60%	0,07%	0,02%

В табл. 4 наведено дані для тактової частоти f_t = 1 МГц. Показники якості визначались на відповідність виразам (10) - (12), а діапазон вихідних частот f_{в_мін}чf_{в_макс} обчислювався за формулами

(15)

(16)

де m- розрядність чисел на виході ГПВЧ.

В роботі проаналізовано характеристики вихідного сигналу ГПІП при імітації вихідного сигналу дозиметричних детекторів.

Якщо не враховувати "мертвий час" детекторів, то середню частоту імпульсів на виході блоку детектування, яка залежить від величини потужності експозиційної дози ПЕД іонізуючого випромінювання л і чутливості детектора г, можна обчислити за формулою

Z=л•г. (17)

Таблиця 5

Кількість розрядів ГПІП	24 розряди	28 розрядів	30 розрядів
Кількість розрядів секцій нагромаджувального суматора	4	8	16
Період повторення ТП	1,352 сек	15,064 сек	56,415 сек	43,749 сек	30,994 сек
Діапазон значень ПЕД	73,95 мкР/год - 1240,55 Р/год	3,3 мкР/год - 891 Р/год	0,9 мкР/год - 949,45 Р/год	1,15 мкР/год - 1227,15 Р/год	1,6 мкР/год - 1732,15 Р/год

В табл. 5 наведено характеристики ГПІП, реалізованого на базі лінійного конгруентного генератора, при імітації вихідного сигналу дозиметричних детекторів. Характеристики були обчислені для типової чутливості дозиметричних детекторів Гейгера - Мюллера - г=0.02Гц/(мкР/год).

Період повторення ГПІП Т_П та діапазон значень ПЕД л визначалися за формулами

. (18)

. (19)

Аналогічне імітаційне моделювання виконано для ГПІП на базі генераторів М-послідовностей. Крім цього в дисертаційній роботі наведені принципові схеми цих генераторів (для матриць Т₁ та Т₂). Результати оцінювання основних технічних характеристик моделювання наведені в табл. 6 ? 8, зокрема, в табл. 8 - при імітації вихідного сигналу дозиметричного детектора.

Таблиця 6

Зведена таблиця основних технічних характеристик ГПІП, реалізованого на основі генератора М-послідовностей (матриця T₁)

Кількість розрядів ГПІП	17 розрядів	31 розряд
Твірний поліном
Період повторення псевдовипадкових чисел T	131072	2147483648
Мінімальний період тактових імпульсів	4.349 нс	4,585 нс
Максимальна частота тактових імпульсів fмакс	229,938 МГц	218,103 MГц
Максимальна затримка зв'язків	4,056 нс	6,894 нс
Діапазон вихідних частот fв_мінчfв_макс	1754,288 Гц - 229,938 МГц	0,102 Гц - 218,103 MГц
Надійна ймовірність	Показники якості
p =0,68	38,45%	28,89%
p=0,95	0	3,91%
p =0,997	0	0,11%

Таблиця 7

Зведена таблиця основних технічних характеристик ГПІП, реалізованого на основі генератора М-послідовностей (матриця T₂)

Кількість розрядів ГПІП	17 розрядів	31 розряд
Твірний поліном
Період повторення псевдовипадкових чисел T	131072	2147483648
Мінімальний період тактових імпульсів	4,623 нс	5,166 нс
Максимальна частота тактових імпульсів fмакс	216,310 МГц	193,573 МГц
Максимальна затримка зв'язків	3,591 нс	9,584 нс
Діапазон вихідних частот fв_мінчfв_макс	1650,314 Гц - 216,310 МГц	0,09 Гц - 193,573 МГц
Надійна ймовірність	Показники якості
p =0,68	36,42%	24,75%
p=0,95	4,5%	3,25%
p =0,997	0,0%	0,07%

Таблиця 8

Кількість розрядів ГПІП	17 розрядів	31 розряд
Вид матриці	матриця T1	матриця T2	матриця T1	матриця T2
Період повторення ТП	0,57 мсек	0,606 мсек	9,846 сек	11,094 сек
Діапазон значень ПЕД	87,714 мР/год - 11469,9 Р/год	82,516 мР/год - 10815,5 Р/год	5,1 мкР/год - 10905,15 Р/год	4,5 мкР/год - 9678,65 Р/год

В розділі також розглянуті можливості програмної реалізації ГПІП, можливості створення універсального ГПІП з попереднім вибором одного з наперед визначених ГПВЧ. В розроблених програмах поряд з генеруванням пуассонівської імпульсної послідовності є можливість виконувати оцінку її якості.

Основні висновки роботи

1. У дисертаційній роботі наведено теоретичне узагальнення та нове вирішення наукового завдання, що виявляється в створенні нових алгоритмів та засобів для реалізації ГПІП і оцінки їх якості, що дозволяє створювати генератори з покращеними статистичними характеристиками.

2. Проведений аналіз принципів побудови генераторів рівномірно розподілених псевдовипадкових чисел, які є базовими при побудові ГПІП, показав, що не існує універсальних методів оцінки їх якості. Отже, існує необхідність в пошуку групи тестів, на основі яких можна робити висновки про ефективність базових генераторів та ГПІП і удосконалювати їх структури з метою покращення метрологічних характеристик вихідних імпульсних послідовностей.

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

4. Показано, що при правильно вибраних параметрах лінійні конгруентні генератори та адитивні генератори Фібоначі можуть ефективно використовуватись як базові генератори при побудові ГПІП. Поліноміальні конгруентні генератори, хоч і проходять тест “розподіл на площині”, який показує рівномірність розподілу чисел, при подальшому дослідженні виявили свою неефективність. Це ще раз підтверджує тезу про те, що одного чи двох тестів для оцінки якості генераторів недостатньо. Потрібна група тестів, яка і була запропонована в даній дисертаційній роботі.

5. Розроблено математичний алгоритм генерування псевдовипадкових чисел з законом розподілу, наближеним до рівномірного. Дослідження якості цього алгоритму показало, що він може ефективно використовуватись при побудові ГПІП, особливо в тих випадках, коли достатньо лише програмної реалізації.

6. Запропоновані принципи вибору параметрів генераторів М-послідовностей, а саме твірного поліному та степенів матриць Т₁ чи Т₂ (з допомогою яких описується робота цих генераторів), дозволили створити швидкодіючі ГПІП з характеристиками наближеними до теоретично визначених.

7. При аналізі різних способів побудови комбінаційних суматорів, які є складовою частиною лінійних конгруентних генераторів, зроблено рекомендації стосовно їх побудови в залежності від конкретного способу використання.

8. Дослідження генераторів М-послідовностей, реалізованих на основі матриці Т₁ та Т₂ для різних твірних поліномів показали, що при меншому степені твірного полінома апаратна реалізація є простішою, але діапазон вихідних частот є вужчим при приблизно однаковій граничній вихідній частоті.

9. Дослідження вихідних сигналів ГПІП, побудованих на основі лінійного конгруентного методу і генераторів М-послідовностей, показали можливість їх використання для імітації вихідних сигналів дозиметричних детекторів в діапазоні від 1мкР/год до 10000 Р/год.

10. Результати досліджень використано при виконанні науково-дослідних робіт на кафедрах “Автоматика та телемеханіка” та “Захист інформації” Національного університету “Львівська політехніка”.

Список наукових праць опублікованих за темою дисертації

1. Гарасимчук О.І., Максимович В.М., Генератори псевдовипадкових чисел, їх застосування, класифікація, основні методи побудови і оцінка якості // Захист інформації, м.Київ, №3, 2003. с. 29-36.

2. Гарасимчук О.І., Максимович В.М., Алгоритм формування пуассонівського імпульсного потоку // Вісник Національного університету “Львівська політехніка” “Автоматика, вимірювання та керування”, №475, 2003. с. 21-25.

3. Гарасимчук О.І., Максимович В.М., Оцінка якості алгоритмів формування пуассонівського імпульсного потоку // Вісник Національного університету “Львівська політехніка” “Комп'ютерна інженерія та інформаційні технології”, №496, 2003. с. 162-167.

4. Гарасимчук О.І., Дудикевич В.Б., Максимович В.М., Смук Р.Т. Генератори тестових імпульсних послідовностей для дозиметричних пристроїв // Вісник Національного університету “Львівська політехніка” “Теплоенергетика. Інженерія довкілля. Автоматизація”, №506, 2004. с. 186-192.

5. Гарасимчук О.І., Максимович В.М., Генератори пуассонівського імпульсного потоку на основі генераторів М-послідовностей // Вісник Національного університету “Львівська політехніка” “Комп'ютерні науки та інформаційні технології”, №521, 2004. с. 17-23.

6. Гарасимчук О.І., Дудикевич В.Б., Максимович В.М. Кількісне оцінювання генератора пуассонівської імпульсної послідовності побудованого на основі конгруентного генератора // Вісник Східно-Українського національного університету ім. Даля. №9 (103). Науковий журнал. Частина І. Луганськ, 2006 с. 53-56.

7. Гарасимчук О.І., Дудикевич В.Б., Максимович В.М. Кількісне оцінювання генератора пуассонівської імпульсної послідовності на основі генератора М-послідовності // Вісник ДУІКТ - №4, том 4, 2006. с. 251-258.

8. Гарасимчук О.І., Максимович В.М., Дослідження алгоритмів формування пуассонівського імпульсного потоку // Наукові праці VII Міжнародної конференції “Контроль і управління в складних системах (КУСС-2003)” присвяченої 75-річному ювілею професора Іваненка В.І., у м.Вінниця 8-12 жовтня 2003 року.

Анотація

Гарасимчук О.І. Генератори імпульсних послідовностей з пуассонівським законом розподілу. Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.05 ? елементи та пристрої обчислювальної техніки та систем керування. ? Національний університет “Львівська політехніка”, Львів, 2007.

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

Проведене імітаційне моделювання різних методів побудови генераторів псевдовипадкових чисел з рівномірним законом розподілу, які є базовими при реалізації ГПІП, на основі чого для цих генераторів вибрані оптимальні початкові параметри. Запропонована нова структура ГПІП, основною перевагою якої є можливість керування вихідною частотою слідування імпульсів. Вперше запропоновано набір тестів для оцінки якості ГПІП і базових генераторів рівномірно розподілених чисел. Розроблені нові число-імпульсні структури ГПІП, що забезпечують реалізацію конгруентних методів та нові швидкодіючі структури ГПІП, побудовані з використанням генераторів М-послідовностей. Запропонований математичний алгоритм генерування псевдовипадкових чисел з законом розподілу наближеним до рівномірного, який ефективно може використовуватись при програмній реалізації ГПІП. Проаналізовано характеристики вихідного сигналу ГПІП при імітації вихідного сигналу дозиметричних пристроїв.

Ключові слова: генератори псевдовипадкових імпульсних послідовностей, генератори псевдовипадкових чисел, пуассонівський закон розподілу, статистичні характеристики.

Аннотация

Гарасимчук О.И. Генераторы импульсных последовательностей с пуассоновским законом распределения. Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 ? элементы и устройства вычислительной техники и систем управления. ? Национальный университет “Львівська політехніка”, Львов, 2007.

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

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

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

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

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

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

Разработаны новые структуры ГПИП, что обеспечивают реализацию конгруэнтных методов и новые быстродействующие структуры ГПИП, построенные с использованием генераторов М-последовательностей, синтезированные на основе преобразования матриц разного типа, что описывают их работу.

Реализация ГПИП на базе линейных конгруэнтных методов и генераторов М-последовательностей выполнена на программируемых интегральных схемах (ПЛИС). Выполнен анализ временных и частотных характеристик ГПИП на основе ПЛИС.

Проанализированы характеристики выходного сигнала ГПИП при имитации выходного сигнала дозиметрических приборов.

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

Abstract

O. I. Garasymchuk. The pulse sequence generators with Poisson Law of Distribution. Manuscript.

The theses submitted in fulfillment of the requirements for the degree of Candidate of Technical Sciences in specialty 05. 13. 05 “Elements and Devices of Computer Engineering and System Control”. National University “Lvivska Politechnica”, Lviv 2007.

Theses dedicated to the development of new methods and means of pulse sequence generators with Poisson Law of Distribution (PSPG), as well as comparative analysis of their characteristics and selection of tests set for quality evaluation of such generators.

Imitational modeling of different methods, aiming at construction of generators of pseudo-random numbers with the uniform law of distribution has been conducted, which appear to be basic by realization generators of pseudo-random pulse sequences and provide the ground for selection of optimal initial parameters for such generators. A new structure of PSPG, the main advantage of which is the possibility to control the outgoing frequency of impact sequence, has been suggested. A set of tests for evaluation PSPG quality and basic generators of equally distributed numbers has been proposed for the fist time. New fast-acting structures of PSPG being constructed using M-sequence generators and new number-pulse structures of PSPG which provides the realization of congruous methods have been developed. The mathematical algorithm of pseudo-random numbers generation with the law of distribution, being approximated to the uniform, which can be effectively used by program realization of PSPG has been proposed. Characteristics of outgoing signal of PSPG by imitation of outgoing signal of dosimeter devices have been analyzed.

Key words: generators of pseudo-random pulse sequences, generators, of pseudo-random numbers, Poisson Law of Distribution, statistic characteristics.

Размещено на Allbest.ru

...