Створення універсальних генераторів пуассонівських імпульсних послідовностей з простою апаратною реалізацією, великими швидкодією і періодом повторення, можливістю керування вихідними параметрами. Аналіз основних характеристик розроблених генераторів.
Аннотация к работе
У звязку з бурхливим розвитком обчислювальної і вимірювальної техніки, а також із впровадженням новітніх технологій значно розширилась сфера застосування генераторів випадкових і псевдовипадкових імпульсних послідовностей, що ставить нові вимоги до їх проектування та методів оцінки якості. Важливе місце серед таких генераторів займають генератори пуассонівських імпульсних послідовностей (ГПІП). Незважаючи на велику кількість публікацій, що стосуються побудови і дослідження характеристик генераторів випадкових чисел (ГВЧ) та генераторів псевдовипадкових чисел (ГПВЧ), що входять до складу ГПІП, практично відсутні роботи, в яких наведений порівняльний аналіз характеристик ГПІП і сформульовані чіткі рекомендації стосовно їхнього проектування і використання. Однією з важливих задач дослідження якості ГПІП є вибір групи тестів, на основі яких можна з певною ймовірністю вважати, що згенерована псевдовипадкова послідовність буде мати розподіл наближений до пуассонівського. Основний зміст дисертаційної роботи складають результати теоретичних і практичних розробок, проведених автором під час виконання держбюджетних робіт згідно з галузевим тематичним планом впровадження дослідно-конструкторських робіт Міністерства освіти і науки України, розділ “Заряд”, за 2004 р, № державної реєстрації - 0104U002297.
Список литературы
За тематикою дисертаційної роботи опубліковано 9 наукових праць, серед яких 7 статей у фахових виданнях, 1 - у тезах міжнародної конференції, 1 - у тезах всеукраїнської конференції.
Структура та обсяг дисертації. Дисертаційна робота складається із вступу, чотирьох розділів і висновків, викладених на 114 сторінках друкованого тексту, містить 36 рисунків, 37 таблиць, список використаних джерел з 101 найменування і додатків. Загальний обсяг дисертації становить 157 сторінок.
Основний зміст роботи
У вступі обґрунтовано актуальність теми дисертаційної роботи, зазначено звязок з держбюджетним галузевим тематичним планом впровадження дослідно-конструкторських робіт. Сформульовано мету та задачі дослідження, висвітлена наукова новизна та практична цінність роботи. Наведено відомості про впровадження результатів роботи, їх апробацію та публікації.
У першому розділі наведені характеристики імпульсних послідовностей з пуассонівським законом розподілу, результати аналізу принципів побудови ГПВЧ та ГПІП на їх основі. Запропонована класифікація ГПВЧ наведена на рис. 1.
Розглянуто різні способи побудови ГПВЧ: - лінійні конгруентні генератори, що функціонують у відповідності з виразом
; (1)
- поліноміальні конгруентні генератори -
; (2)
- адитивні генератори Фібоначі -
, (3)
(де Xn-1, Xn, Xn 1 - значення псевдовипадкових чисел на тактах n-1, n, n 1 роботи пристрою; a, b, ai - коефіцієнти конгруентних рівнянь; m - модуль рівнянь);
- стандартні генератори алгоритмічних мов програмування;
- генератори М-послідовностей.
Проведено аналіз матричних рівнянь генераторів М-послідовностей: , (4) де і - стани регістра генератора в моменти часу t і t 1 відповідно (до і після приходу синхроімпульсу), T - квадратна матриця порядку N вигляду або , (5)
N - степінь примітивного полінома
, (6) а r - натуральне число.
Проаналізовано основні області застосування ГПІП.
Розглянуто методи оцінки якості псевдовипадкових послідовностей, а саме дві групи тестів: 1. Графічні тести - за допомогою яких користувач отримує певні графічні залежності і робить висновки про властивості псевдовипадкової послідовності, що тестується.
2. Оціночні тести - тести, в яких на основі певних критеріїв, отримують кількісні дані і робиться висновок про степінь близькості статистичних властивостей псевдовипадкової послідовності, що тестується, до заданих параметрів.
У другому розділі запропонована загальна структурна схема ГПІП, в якій середня частота вихідних імпульсів є керованою.
Структура ГПІП, зображенена на рис.2, складається з ГПВЧ, схеми порівняння СП і логічного елементу І.
З кожним вхідним імпульсом, частота повторення яких дорівнює ft, на виході ГПВЧ формуються псевдовипадкові числа D з рівномірним законом розподілу. У випадку, коли виконується умова D<G, на виході СП формується сигнал, який дозволяє черговому вхідному імпульсу пройти на вихід генератора.
Середню частоту повторення вихідних імпульсів ГПІП визначають за формулою
, (7) де А - максимально можливе значення числа на виході ГПВЧ.
Перевагою такого ГПІП є те, що середньою частотою слідування вихідних імпульсів можна керувати змінюючи: значення G; тактову частоту генератора ft; кількість розрядів ГПВЧ.
В результаті імітаційного моделювання були знайдені оптимальні параметри базових генераторів рівномірно розподілених псевдовипадкових чисел та досліджені їхні характеристики.
Запропоновані структурні схеми ГПІП з використанням, як базового, лінійного конгруентного генератора, одна з яких наведена на рис. 3.
В склад ГПІП входять два комбінаційні суматори КС1 і КС2, регістри РГ1 і РГ2, схема множення СМ, схема порівняння СП і логічний елемент І. Робота пристрою полягає в реалізації лінійного конгруентного методу формування псевдовипадкових чисел згідно рівняння (1).
Кожен вхідний імпульс генератора викликає формування на виході СМ серії з a імпульсів. На виході нагромаджувального суматора, побудованого на комбінаційному суматорі КС1 і регістрі РГ1, формується добуток a•Xn. Число a•Xn b формується на виходах КС2, а поточні значення Xn зберігаються в s молодших розрядах регістра РГ2. Поновлення чисел в РГ2 та обнулення вмісту РГ1 проводиться вхідними імпульсами пристрою. При умові Xn 1<G, на виході СП формується логічний рівень, який пропускає вхідний імпульс через логічний елемент І на вихід генератора.
Для лінійного конгруентного генератора знайдено ряд оптимальних параметрів, зокрема, значення a=105, b=12345, m=230 для рівняння (1). В процесі дослідження, спочатку були протестовані псевдовипадкові послідовності вихідних чисел ГПВЧ на рівномірність і випадковість розподілу, у тому числі за допомогою тесту “розподіл на площині” (рис.4), де Xn, Xn-1 ? чергове та попереднє значення псевдовипадкового числа відповідно. Площина заповнена повністю і безсистемно, що дає підстави зробити попередній висновок про придатність даного варіанту для подальших досліджень ГПІП.
В результаті проведеного аналізу було додатково вибрано сім оціночних тестів, за допомогою яких можна оцінити якість псевдовипадкової послідовності чисел. Результати тестування лінійного конгруентного генератора наведено в табл. 1.
В таблиці “ ” означає, що тест пройдено. Отже, при правильному виборі параметрів лінійного конгруентного генератора, він проходить всі тести на випадковість і рівномірність розподілу, що свідчить про його високу якість.
Таблиця 1
Результати оціночного тестування лінійного конгруентного генератора
Вид оціночного тесту imax?nmax
5000000 50000000
Перевірка кореляції
Перевірка перестановок, що пересікаються
Перевірка на монотонність
Перевірка перестановок
Тест дірок
Перевірка незціплених серій
Частотний монобітний тест
Для оцінки якості ГПІП отримана за допомогою базового генератора псевдовипадкова рівномірно розподілена послідовність розбивається на інтервали imax. Кількість чисел в інтервалі imax може бути довільною, але достатньо великою. Кількість таких інтервалів n також є довільною і змінюється в межах 0<n<nmax. При цьому необхідно, щоб виконувалась умова
, (8) де T ? період повторення значень чисел.
При дослідженні вихідної імпульсної послідовності на відповідність пуассонівському закону розподілу був використаний наступний аналітичний підхід.
Середня кількість імпульсів, що може бути зафіксована на виході ГПІП за час вимірювання TB, обчислюється за формулою
. (9)
Кількість імпульсів пуассонівського імпульсного потоку, зафіксована за час TB: а) з надійною ймовірністю p=0,68 знаходиться в межах
; (10) б) з надійною ймовірністю p=0,95 ? в межах
; (11) в) з надійною ймовірністю p=0,997 ? в межах
. (12)
Під час дослідження ГПІП, на основі лінійного конгруентного методу з вище наведеними параметрами, за допомогою оціночних та графічних тестів, для різних значень добутку imax?nmax, були отримані наступні результати.
Статистичні характеристики ГПІП наведено на рис. 5 і в табл. 2. Тут k -кількість імпульсів на виході ГПІП за час TB, а n - кількість інтервалів часу TB. Межі вказані згідно формули (11), де і . (13)
Таблиця 2
Результати оцінювання ГПІП, побудованого на основі лінійного конгруентного генератора, згідно формул (10) - (12)
Значення і Діапазон дослідження (значення )Кількість значень , що виходить за межі згідно формул (10) - (12) для =0,95для =0,68для =0,997
=1000 Гц, =0,01 с0 - 1005260
100 - 200 3 24 0
200 - 300 4 28 1
300 - 400 5 30 1
400 - 500 1 26 0
=100 Гц, =0,1 с0 - 1004271
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.
Для поліноміального конгруентного генератора були, зокрема, знайдені наступні оптимальні параметри: a2=2, a1=115, b=12345, m=230 (2); для адитивного генератора Фібоначі: Xn-1=0; Xn=1234567, m=230 (3).
Оцінювання з допомогою тесту “розподіл на площині” показало, що всі вище згадані генератори, при правильно підібраних параметрах, мають рівномірний та випадковий розподіл. Кількісне оцінювання цих ГПВЧ і ГПІП, реалізованих на їх основі, довело, що вони, за винятком поліноміальних конгруентних генераторів, володіють властивостями наближеними до теоретично визначених, оскільки успішно проходять переважну більшість тестів.
Поліноміальний конгруентний генератор пройшов лише частину тестів і в загальному, ГПІП реалізований на його основі, не володіє характеристиками наближеними до теоретичних. На цьому прикладі видно, що використання лише одного тесту (а не групи тестів) може бути помилковим при побудові ГПІП.
Також був запропонований наступний математичний алгоритм генерування псевдовипадкових чисел з законом розподілу наближеним до рівномірного
, (14) де i=1... imax, n=1...nmax; j=10s, де k і s - цілі числа.
Генератор на основі системи (14), може бути використаний як базовий для побудови ГПІП, в-першу чергу в тих випадках, коли реалізація ГПІП виконується програмно. До переваг цього алгоритму можна віднести простоту програмної реалізації, можливість швидкого переналагодження і високу швидкодію, а до недоліків - відносну складність апаратної реалізації.
В результаті імітаційного моделювання були визначені оптимальні значення параметрів, зокрема: j=109, k=108. Результати розподілу на площині та результати тестування за допомогою групи з семи запропонованих вище оціночних тестів дають підстави зробити попередній висновок про придатність даного варіанту для подальших досліджень ГПІП. Кількісні оцінки ГПІП, побудованого на основі запропонованого математичного алгоритму (14), за допомогою формул (10) - (12) і статистичного критерію , також були позитивними.
У третьому розділі запропоновано принципи вибору базового генератора М-послідовностей і ГПІП реалізованих на його основі.
Досліджені різні способи побудови генераторів М-послідовностей в залежності від вибору матриці (T1 чи T2), з допомогою яких описується робота цих генераторів, та в залежності від вибору твірного поліному і для різних значень r ? степеня матриці. В результаті імітаційного моделювання ГПІП на основі генераторів М-послідовностей для різних степеней r, запропоновано використовувати значення r=10. Це зумовлено тим, що результати моделювання та оцінка якості доводять, що для значень r>6, псевдовипадкова послідовність згенерована за допомогою генератора М-послідовностей має розподіл близький до рівномірного і є випадково розподілена. Побудовані на основі такого генератора ГПІП мають розподіл більш наближений до теоретичного пуассонівського в порівнянні з ГПІП побудованими для менших значень r. Також не варто будувати ГПІП для дуже великих значень r, оскільки тоді ускладнюється апаратна реалізація такого генератора, а якість ГПІП, побудованого на основі генератора М-послідовностей для значення r=10, мало відрізняється від ГПІП, побудованого на основі генератора М-послідовностей для значень r >10.
В результаті імітаційного моделювання були проаналізовані генератори М-послідовностей реалізовані на основі різних твірних поліномів, зокрема, для твірного поліному (рис. 6).
До складу схеми входять: 31 тригер (відповідно до степеня полінома), на виходах яких зберігається чергове значення псевдовипадкової послідовності і 10 суматорів за модулем 2.
За допомогою групи тестів була виконана оцінка якості даного ГПВЧ. Отримані результати свідчать, що він проходить більшість тестів. Кількісні оцінки ГПІП, побудованого на основі такого генератора, за допомогою формул (10) - (12) і статистичного критерію також були позитивними.
Аналогічні дослідження, виконані для ГПІП на основі генераторів М-послідовностей реалізованих на матриці T2, у тому числі, для твірного поліному , при r =10.
Генератор, зображений на рис. 7, як і генератор, зображений на рис. 6, складається з 31 тригера і 10 суматорів за модулем 2.
Для даного генератора М-послідовностей також була виконана оцінка якості за допомогою групи тестів, більшість з яких він пройшов. Кількісні оцінки ГПІП, побудованого на основі такого генератора М-послідовностей, за допомогою формул (10) - (12) і статистичного критерію , також були позитивними.
Отже, було ще раз отримане підтвердження того, що ГПІП, які реалізовані на генераторах М-послідовностей (згідно матриць T1 та T2), при правильному виборі твірного поліному і степенів матриць r, володіють статистичними властивостями наближеними до теоретичних.
У четвертому розділі розглянуто реалізацію ГПІП на базі ПЛІС.
Були проведені дослідження швидкодії лінійних конгруентних генераторів та ГПІП, в залежності від способу побудови і кількості розрядів їх складових частин (секцій).
За допомогою імітаційного моделювання у системі моделювання Foundation фірми Xilinx та програмування на алгоритмічній мові Delphi проведено оцінювання основних технічних характеристик ГПІП на базі лінійного конгруентного генератора. Результати такого моделювання представлені в табл. 4.
Таблиця 4
Зведена таблиця основних технічних характеристик ГПІП на базі лінійного конгруентного генератора
Кількість розрядів ГПІП 24 розряди 28 розрядів 31 розряд
Кількість розрядів секцій нагромаджувального суматора 4 8 16
Період повторення псевдовипадкових чисел T 33554432 268435456 1073741824
Надійна ймовірність Показники якості 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 наведено дані для тактової частоти ft = 1 МГЦ. Показники якості визначались на відповідність виразам (10) - (12), а діапазон вихідних частот fв_мінчfв_макс обчислювався за формулами
(15)
(16) де m- розрядність чисел на виході ГПВЧ.
В роботі проаналізовано характеристики вихідного сигналу ГПІП при імітації вихідного сигналу дозиметричних детекторів.
Якщо не враховувати "мертвий час" детекторів, то середню частоту імпульсів на виході блоку детектування, яка залежить від величини потужності експозиційної дози ПЕД іонізуючого випромінювання л і чутливості детектора г, можна обчислити за формулою
Z=л•г. (17)
Таблиця 5
Кількість розрядів ГПІП 24 розряди 28 розрядів 30 розрядів
Кількість розрядів секцій нагромаджувального суматора 4 8 16
В табл. 5 наведено характеристики ГПІП, реалізованого на базі лінійного конгруентного генератора, при імітації вихідного сигналу дозиметричних детекторів. Характеристики були обчислені для типової чутливості дозиметричних детекторів Гейгера - Мюллера - г=0.02Гц/(МКР/год).
Період повторення ГПІП ТП та діапазон значень ПЕД л визначалися за формулами
. (18)
. (19)
Аналогічне імітаційне моделювання виконано для ГПІП на базі генераторів М-послідовностей. Крім цього в дисертаційній роботі наведені принципові схеми цих генераторів (для матриць Т1 та Т2). Результати оцінювання основних технічних характеристик моделювання наведені в табл. 6 ? 8, зокрема, в табл. 8 - при імітації вихідного сигналу дозиметричного детектора.
Таблиця 6
Зведена таблиця основних технічних характеристик ГПІП, реалізованого на основі генератора М-послідовностей (матриця T1)
Кількість розрядів ГПІП 17 розрядів 31 розряд
Твірний поліном
Період повторення псевдовипадкових чисел T 131072 2147483648
Мінімальний період тактових імпульсів 4.349 нс 4,585 нс
В розділі також розглянуті можливості програмної реалізації ГПІП, можливості створення універсального ГПІП з попереднім вибором одного з наперед визначених ГПВЧ. В розроблених програмах поряд з генеруванням пуассонівської імпульсної послідовності є можливість виконувати оцінку її якості.
Основні висновки роботи
1. У дисертаційній роботі наведено теоретичне узагальнення та нове вирішення наукового завдання, що виявляється в створенні нових алгоритмів та засобів для реалізації ГПІП і оцінки їх якості, що дозволяє створювати генератори з покращеними статистичними характеристиками.
2. Проведений аналіз принципів побудови генераторів рівномірно розподілених псевдовипадкових чисел, які є базовими при побудові ГПІП, показав, що не існує універсальних методів оцінки їх якості. Отже, існує необхідність в пошуку групи тестів, на основі яких можна робити висновки про ефективність базових генераторів та ГПІП і удосконалювати їх структури з метою покращення метрологічних характеристик вихідних імпульсних послідовностей.
3. На основі аналізу загальних принципів отримання послідовностей з законом розподілу, що відрізняється від рівномірного, запропоновано нову структуру ГПІП, в якій можна керувати вихідною частотою слідування імпульсів.
4. Показано, що при правильно вибраних параметрах лінійні конгруентні генератори та адитивні генератори Фібоначі можуть ефективно використовуватись як базові генератори при побудові ГПІП. Поліноміальні конгруентні генератори, хоч і проходять тест “розподіл на площині”, який показує рівномірність розподілу чисел, при подальшому дослідженні виявили свою неефективність. Це ще раз підтверджує тезу про те, що одного чи двох тестів для оцінки якості генераторів недостатньо. Потрібна група тестів, яка і була запропонована в даній дисертаційній роботі.
5. Розроблено математичний алгоритм генерування псевдовипадкових чисел з законом розподілу, наближеним до рівномірного. Дослідження якості цього алгоритму показало, що він може ефективно використовуватись при побудові ГПІП, особливо в тих випадках, коли достатньо лише програмної реалізації.
6. Запропоновані принципи вибору параметрів генераторів М-послідовностей, а саме твірного поліному та степенів матриць Т1 чи Т2 (з допомогою яких описується робота цих генераторів), дозволили створити швидкодіючі ГПІП з характеристиками наближеними до теоретично визначених.
7. При аналізі різних способів побудови комбінаційних суматорів, які є складовою частиною лінійних конгруентних генераторів, зроблено рекомендації стосовно їх побудови в залежності від конкретного способу використання.
8. Дослідження генераторів М-послідовностей, реалізованих на основі матриці Т1 та Т2 для різних твірних поліномів показали, що при меншому степені твірного полінома апаратна реалізація є простішою, але діапазон вихідних частот є вужчим при приблизно однаковій граничній вихідній частоті.
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 року.