Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
13
УДК 681.324
МЕТОДИ І ЗАСОБИ ФОРМУВАННЯ СПЕЦІАЛІЗОВАНИХ ПСЕВДОВИПАДКОВИХ КЕРОВАНИХ ДВІЙКОВИХ ПОСЛІДОВНОСТЕЙ
Спеціальність - 05.13.05 –Елементи та пристрої обчис-
лювальної техніки та систем
керування
АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук
Дисертацією є рукопис.
Робота виконана в Національному технічному університеті України “Київський політехнічний інститут” (НТУУ “КПІ”) на кафедрі спеціалізованих комп’ютерних систем.
Науковий керівник: доктор технічних наук, професор
Романкевич Олексій Михайлович,
НТУУ “КПІ”, професор кафедри СКС
Офіційні опоненти: доктор технічних наук, професор
Дрозд Олександр Валентинович,
Одеський національний політехнічний
університет, професор кафедри комп’ютер-
них інтелектуальних систем та мереж
кандидат технічних наук
Селігей Олександр Минович,
Кременчуцький державний політехнічний університет, доцент кафедри комп’ютерних та інформаційних систем
Захист відбудеться “ 15 ” жовтня 2007 р. о 16:00 на засіданні спеціалізованої вченої ради Д 26.002.02 у НТУУ “КПІ” (м. Київ, пр. Перемоги, 37, корп. 18, ауд. 306)
Відзиви на автореферат в двох примірниках, завірені печаткою установи, просимо надсилати за адресою: 03056, м. Київ, пр. Перемоги, 37, вченому секретарю НТУУ “КПІ”
З дисертацією можна ознайомитись в бібліотеці Національного технічного університету України “Київський політехнічний інститут”
Автореферат розісланий “”вересня 2007 р.
Вчений секретар
спеціалізованої вченої ради Орлова М.М.
ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ
Актуальність теми
Псевдовипадкове тестування цифрових схем є одним з перспективних напрямків в галузі технічної діагностики. Основним аргументом на користь його широкого застосування є спрощення всієї процедури тестування, що пов'язано з відсутністю найбільш трудомісткого етапу - синтезу тесту для заданого класу несправностей. Додатковий стимул використання псевдовипадкового тестування дістало останнім часом у зв'язку з успішним розвитком методів синтезу тестопридатних схем, що враховують особливості такого методу іспитів.
Основою комплексу апаратних засобів, необхідних для організації псевдовипадкового тестування, є пристрої, що формують псевдовипадкові послідовності іспитових сигналів - генератори псевдовипадкових послідовностей. Структурні і функціональні особливості генераторів іспитових послідовностей у великому ступені впливають на такі найважливіші характеристики системи діагностування, як продуктивність, ефективність, вірогідність і повнота контролю, ступінь автоматизації, динаміка іспитів, габарити апаратури і т.ін. Як показує аналіз, вимоги, що пред'являються до генераторів псевдовипадкових іспитових сигналів, ускладнюються в зв'язку з необхідністю реалізації заданого комплексу функціональних можливостей.
Як показує аналіз, існуючі способи і відповідні засоби генерації тестових послідовностей часто залишають дослідженими в недостатньому ступені такі цікаві і перспективні можливості, як, наприклад, генерація іспитових псевдовипадкових послідовностей з керуванням по декільком параметрам. Дійсно, практично всі існуючі підходи до побудови апаратних засобів генерації послідовностей псевдовипадкових наборів супроводжуються або фіксованою (наприклад, на рівні 1/2) або змінюваною лише в процесі налагоджування імовірністю елементів двійкових послідовностей на виходах генератора, причому вихідні двійкові сигнали з заданою імовірністю формуються, за звичай, на повній множині виходів багатоканальних структур таких генераторів. У випадку ж необхідності одержання, наприклад, різних імовірностей сигналів по різних каналах, то традиційно даний режим технічно реалізується шляхом використання множини незалежно налагоджуваних і керованих одноканальних схем генерації. Крім того, необхідно відзначити відсутність комплексного підходу, що враховує специфіку й особливості методів псевдовипадкового тестування при організації складних систем діагностування цифрових об'єктів. Таким чином, виникають задачі організації програмно–апаратних діагностичних комплексів, що дозволяють врахувати в більш високому ступені особливості імовірнісного тестування і забезпечити набір необхідних сервісних засобів для підвищення ефективності контролю складних дискретних об'єктів.
Окремою важливою галуззю використання спеціалізованих генераторів є дослідження, пов‘язані з розрахунком надійності відмово стійких багатопроцесорних систем (ВБС), а саме –проведення статистичних експериментів з моделями, які відображають реакцію ВБС на появу відмов. Використання традиційних генераторів псевдовипадкових чисел (або їх програмних моделей) у даному випадку доцільно для однорівневих ВБС, які включають невелику кількість модулів. У випадку, коли модель поведінки ВБС у потоці відмов має багаторівневий характер, а, значить, необхідно моделювати поведінку одразу декількох підсистем, у тому числі з загальними елементами, задача формування двійкових послідовностей векторів стану системи приймає нетривіальний характер, який потребує побудови нових спеціалізованих псевдовипадкових керованих двійкових генераторів.
Отже, розробка і дослідження нових, більш ефективних методів і структурних засобів синтезу псевдовипадкових керованих іспитових послідовностей визначає науково-практичну значимість тематики дисертаційної роботи і здається досить актуальною, тому що рішення задач, що відносяться до предметної області дисертації, дозволяє, наприклад, істотно розширити номенклатуру об'єктів контролю, іспити яких можуть бути проведені в автоматичному режимі, забезпечити підвищену продуктивність процедур діагностування складних цифрових пристроїв або збільшити ефективність етапу моделювання при верифікації проектних рішень, запропонованих у ході розробки та створення дискретних приладів, пристроїв чи систем.
Зв'язок роботи з науковими програмами, планами, темами. Основні наукові результати, отримані в ході виконання дисертаційної роботи, відповідають області наукових досліджень, які проводяться на кафедрі спеціалізованих комп'ютерних систем НТУУ “Київський політехнічний інститут”, а саме: “Методи та засоби побудови тестопридатних цифрових об‘єктів”(№ держреєстрації 0104U000686), а також “Підвищення ефективності засобів генерації псевдовипадкових іспитових послідовностей і схем сигнатурного аналізу”.
Мета і завдання дослідження - створення та дослідження структурних методів і засобів побудови спеціалізованих цифрових схем, що дозволяють з високою продуктивністю формувати псевдовипадкові послідовності двійкових векторів з можливістю керування їх імовірнісними параметрами.
Для досягнення поставленої мети в роботі вирішені наступні задачі:
- проведено порівняльний аналіз відомих методів формування псевдовипвдкових послідовностей, сформульовані рекомендації щодо вибору структур керуючих генераторів псевдовипвдкових наборів відповідно до вимоги зменшення ступеня корельованості вихідних однорозрядних послідовностей;
- розроблено і досліджено структурні методи і відповідні апаратурні засоби формування послідовностей псевдовипадкових наборів із заданою вагою, запропоновано методики вибору структури формувача відповідно до критеріїв структурної складності або імовірнісних показників якості вихідних послідовностей;
- розроблено структурний підхід, який припускає використання типових цифрових схем для реалізації спеціалізованої частини генератора, а також застосування класичного джерела рівноімовірних наборів для формування послідовностей з керуванням по двох параметрах вихідної послідовності;
- обґрунтовано вибір критеріїв, відповідно до яких на етапі проектування можна забезпечити необхідні значення основних параметрів формувача послідовностей з керуванням по двох параметрах;
- розроблено алгоритмічне й апаратурне забезпечення процедур формування псевдовипадкових послідовностей рівновагових наборів, у тому числі, із заданим законом розподілу вихідних імовірностей двійкових сигналів, тобто з можливістю незалежного програмування вихідних імовірностей по усіх вихідних каналах генератора;
- обґрунтовано вибір показників якості імовірнісних послідовностей, що генеруються, на основі яких розроблено методики моделювання роботи запропонованих формувачів, наприклад, на етапі верифікації різних варіантів проектних рішень;
- сформульовано вимоги до функціонального призначення основних програмних модулів системи моделювання спеціалізованих структурних засобів генерації керованих псевдовипвдкових послідовностей, розроблено алгоритми виконання найбільш важливих системних і сервісних процедур, а також досліджено взаємодію програмних модулів у складі моделюючого комплексу.
Об'єкт дослідження - спеціалізовані структурні методи і засоби генерації керованих псевдовипадкових послідовностей двійкових векторів.
Предмет дослідження - структурні методи побудови формувачів спеціалізованих керованих послідовностей двійкових сигналів та векторів, зокрема з використанням генераторів рівноімовірних псевдовипадкових наборів.
Методи дослідження базуються на теорії послідовносних керуючих пристроїв і цифрових лінійних структур, основних положеннях теорії імовірностей, булевій алгебрі, елементах теорії множин, теоретичних питаннях технічної діагностики, алгоритмічних засадах логічного моделювання цифрових структур.
Наукова новизна одержаних результатів полягає у створенні і дослідженні методів структурного синтезу спеціалізованих цифрових пристроїв, основним призначенням яких є реалізація ефективних процедур формування послідовностей псевдовипадкових векторів з можливістю керування різними параметрами таких послідовностей.
Розроблено нові способи та алгоритми генерації послідовностей псевдовипадкових наборів визначеної ваги, що передбачають спільне використання властивостей зсувної регістрової структури з схемою лінійного зворотного зв'язку і спеціальної логічної структури. На базі цих способів запропоновано і досліджено конкретні структурні і схемотехнічні вирішення реалізації формувачів, а також розроблено рекомендації, що дозволяють на етапі проектування вибрати оптимальний варіант формувача зі зменшеною апаратурною складністю або з поліпшеними якісними показниками послідовності, що генерується.
Розроблено новий структурний метод побудови генератора послідовності спеціального виду, у якому сполучається можливість керування як імовірністю стану вихідних елементів, так і імовірністю переключення в двійковій послідовності, що генерується, причому відмінною рисою методу є орієнтація на використання типових цифрових вузлів і джерел рівноімовірних двійкових наборів.
Розроблено методику вибору основних структурних параметрів генератора з керуванням по двох параметрах, отримано аналітичні співвідношення, що дозволяють змінюючи визначені структурні параметри формувача, такі, як розрядність вихідного слова і число комірок схеми пам'яті, поліпшити статистичні властивості вихідної послідовності або зменшити структурну складність спеціалізованої апаратури; отримано аналітичні співвідношення для оцінки погрішності, що виникає в процесі формування ПВП із можливістю керування імовірносними параметрами, причому особливістю даної методики є урахування трьох складових погрішності, а саме: погрішності, обумовленої представленням необхідних значень імовірностей у форматі двійкових чисел, погрішності формування опорних ПВП, що визначають вихідні параметри генератора, і погрішності, зв'язаної з логічним об'єднанням опорних ПВП на виході генератора .
Вперше розроблено алгоритм роботи спеціалізованої структури керованого генератора послідовностей рівновагових наборів, характерною рисою якого є можливість задавати (програмувати) імовірності вихідних каналів незалежно один від іншого, а також запропонована методика одержання заданих значень основних імовірносних характеристик генератора, що дозволяє на етапах його налагоджування і системного функціонування забезпечити підвищення продуктивності моделюючих процедур, реалізованих з використанням нових структурних засобів формування керованих послідовностей зі змінюваним законом розподілу.
Розглянуто різні способи визначення показників якості імовірносних послідовностей, що генеруються, і розроблені методики адаптації цих підходів для оцінки запропонованих структур формувачів таких послідовностей, наприклад, за критеріями статистичної незалежності елементів послідовностей, значенням коефіцієнтів кореляції й автокореляції, величини математичного очікування інтервалу дискретного часу, на якому з заданою імовірністю формується повна множина вихідних наборів фіксованої ваги, частоти появи у вихідних послідовностях серій однакових елементів.
Практичне значення одержаних результатів дисертаційної роботи.
Розроблені в дисертації методи та засоби побудови спеціалізованих цифрових структур, які призначені для формування двійкових псевдовипадкових послідовностей з можливістю управління основними імовірносними параметрами вихідних сигналів, можуть бути засосовані, наприклад, при проектуванні діагностичних комплексів, за допомогою яких, зокрема, можна виконувати процедури випробувань складних цифрових об’єктів з покращеними показниками тестопридатності. Джерелом одержання економічного ефекту при цьому є скорочення витрат на визначення технічного стану таких пристроїв як у процесі виробництва, так і в ході їх експлуатації. Запропоновані і розроблені достатньо детально в дисертаційній роботі алгоритмічні та структурні засоби одержання керованих послідовностей рівновагових наборів можуть виступати ефектвними інструментальними засобами для підвищення продуктивності процедур виконання статистичних експериментів над моделями поведінки відмовостійких багатопроцесорних систем у потоці відмов з метою одержання основних надійносних показників таких систем.
Найбільш суттєві наукові результати дисертаційної роботи знайшли використання в навчальному процесі НТУУ "КПІ" на кафедрі спеціалізованих комп’ютерних систем, зокрема, при складанні курсів лекцій по навчальним дисціплінам "Моделювання", "Тестування, надійність, контроль та діагностика комп’ютерних систем", "Архітектура комп’ютерів", ряд положень і рекомердацій науково-прикладного характеру використовуються студентами спеціальностей "Спеціалізовані комп’ютерні системи" та "Системне програмування" під час написання курсових, бакалаврських і дипломних проектів, а також випускних магістерських робіт.
Особистий внесок здобувача. Всі наукові результати одержані дисертантом самостійно. У наукових працях, що опубліковані в соавторстві, їм виконано наступне.
В роботах [1,6,7,8] –дослідження методики формування двійкових послідовностей з керуванням по двох параметрах, та обчислення похибки. В роботі [2] - логічна структура схеми об'єднання розрядів керованого генератора. В роботі [3] сформульовано вимоги до параметрів генеруючої структури та розроблено алгоритм процедури програмування імовірності вихідних двійкових сигналів. В роботі [4] - методика оцінки впливу на результуючу похибку використання перетворювачів “код-ймовірність”. В роботі [5] сформульовано вимоги до структури формувача послідовностей псевдовипадкових рівновагових наборів та запропоновано схемотехнічну реалізацію комбінаційної частини генератора.
Апробація результатів дисертації
Основні результати дисертаційної роботи обговорювалися на наступних міжнародних конференціях і школах-семінарах:
-й, вересень 2005, і 19-й, вересень 2006, міжнародних науково-практичних конференціях “Перспективні системи управління на залізничному, промисловому і міському транспорті” (ХарГАЖТ –УЗ –НТО), м. Алушта; науково-практичній конференції “Комп’ютерні системи в автоматизації виробничих процесів”, м. Хмельницький, травень 2007р.; на 7-й, травень 2006, та 8-й, травень 2007, міжнародних науково-практичних конференціях “Сучасні інформаційні та електронні технології” у м. Одеса; а також на IEEE East-West Design & Test Workshop, Russia, Sochi, September 2006.
Публікації. За результатами проведених досліджень опубліковано 8 наукових робіт, з них 4 статті у фахових виданнях, які входять до списку затверджених ВАК України, 1 стаття у фаховому виданні Росії та 3 тези доповідей.
Структура й обсяг роботи. Дисертаційна робота включає вступ, чотири глави, висновок, список літератури та додатки. Основний матеріал викладений на 150 сторінках машинописного тексту, містить 99 рисунків, 14 таблиць, у списку використаної літератури перелічено 57 найменування джерел.
ОСНОВНИЙ ЗМІСТ РОБОТИ
У вступі до дисертаційної роботи визначена актуальність проблеми створення і дослідження нових ефективних методів побудови спеціалізованих структурних засобів формування псевдовипадкових послідовностей з можливістю керування імовірносними параметрами. Сформульована мета роботи, основні задачі досліджень, наведені головні нові наукові результати, що одержані в ході досліджень, та їх практичне значення, пов’язане з суттєвим підвищенням ефективності тестування цифрових об’єктів, іспити яких можуть бути проведені в автоматичному режимі, забезпеченням більшої продуктивності процедур діагностування (зокрема, зменшення часу) складних цифрових пристроїв, підвищенням ефективності етапів моделювання при верифікації проектних рішень, запропонованих у ході проектування дискретних приладів, пристроїв або систем, зокрема, відмовостійких багатопроцесорних структур.
У першому розділі проведено порівняльний аналіз відомих методів і засобів формування псевдовипадкових (ПВ) послідовностей. В основі цих методів лежить використання як джерела рівноімовірних двійкових псевдовипадкових послідовностей класичної схеми зсувного регістра з лінійним зворотним зв'язком (ЗРЛЗЗ), що формує М–послідовність, тобто послідовність максимального періоду. Виявлено, що для одержання ПВ - послідовностей рівноімовірних двійкових векторів (ПВ - чисел) найбільш доцільно використовувати регістрову структуру на тригерах Т- типу (рис.1), що має кращі статистичні властивості, ніж класична схема ЗРЛЗЗ. При обранні варіанта побудови ГПВЧ перевіряється виконання умови
Н.О.К. (m, 2n-1) = m(2n-1),
де: m –кількість тактів зміщення при організації виборки вихідних станів, n - ступінь характеристичного багаточлена.
В процесі аналізу відомих структур керованих формувачів показано, що одноканальні перетворювачі “код - імовірність”, які побудовані по послідовному принципу, характеризуються невеликою складністю апаратури і використовують тільки однобітну ПВ –послідовність рівноімовірних двійкових сигналів. Паралельна структура одноканальних перетворювачів відрізняється тим, що в якості опорної використовується ПВ –послідовність рівноімовірних двійкових наборів, що призводить до збільшення складності каналу перетворення і висуває підвищені вимоги до розрядності опорного (керуючого) генератора псевдовипадкових чисел (ГПВЧ). Багатоканальні формувачі керованих ПВ –послідовностей достатньо просто програмуються на задані значення вихідних імовірностей. При цьому з'являється можливість за рахунок використання спеціальних схемотехнічних вирішень зменшити складність апаратури і розрядність ГПВЧ, що припадає на один вихідний канал перетворювача “вага набору - імовірність”.
Матеріали другого розділу дисертаційної роботи пов'язані з питаннями розробки і дослідження спеціальних структурних методів і засобів формування послідовностей ПВ-наборів зі змінюваною вагою. Загальний принцип побудови таких формувачів заснований на використанні класичного ГПВЧ в якості керуючого пристрою у сполученні зі спеціальною регістровою структурою, схемотехнічні особливості якої визначають основні параметри послідовності рівновагових векторів, що генеруються. Розроблено методику, яка використовує організацію переключення елементів пам'яті регістра при випадковому (точніше, псевдовипадковому) виборі пари сусідніх елементів пам'яті, що знаходяться в різних станах, і здійсненні зміни станів тригерів цієї пари. Процедура функціонування генератора може бути визначена у відповідності до умови:
i, t [Ti (t+1) = i [Ti(t) Ti+1(t)],
де: I –допоміжна функція такого вигляду (аргумент t умовно не показано), така, що:
i = [T(i-1) mod N Ti ] (DCi P(i-1) mod N),
DCi - стан i-го виходу дешифратора керуючого псевдовипадкового logN–розрядного набору, Pi- вихід схеми послідовного переносу, - функція збудження елемента пам’яті Ті:
Ti=i (i+1) mod N ,
Pi = [P(i-1) mod N DCi] [T(i-1) mod N Ti 1].
Показано, що імовірності станів вихідного регістра генератора P(Sj) пропорційні відповідним алгебраічним доповненням, які одержані з імовірносної матриці, що описує поведінку генератора, тобто:
,
причому значення компонентів вектора імовірностей станів (наборів) обчислюються на основі співвідношення:
.
Додаткова умова має такий вигляд:
.
Відповідно, коефіцієнт пропорційності С можна одержати таким чином:
.
Досліджено розподіл ймовірностей для всіх можливих двійкових вихідних наборів різної ваги, а також запропонована методика оцінки апаратурних витрат на реалізацію формувача.
У цьому ж розділі розроблена методика побудови формувачів рівновагових кодів, коли на кожнім такті роботи доступ здійснюється у відповідності з розподілом усіх біт вихідного регістра за принципом парності номера біта (рис.2), оцінено складність технічної реалізації цього методу формування послідовностей, розглянуто два варіанти структурної реалізації, причому показано, що модифікації відрізняються ступенем мінливості (імовірністю зміни стану) сусідніх генерованих наборів, тобто ентропійними показниками вихідної ПВ-послідовності.
Для збільшення ентропії вихідної послідовності генератора за рахунок можливості псевдовипадкового доступу до більшого числа біт вихідного регістра запропоновано виконати декомпозицію цього регістра на кілька груп, тобто N бітів вихідного регістру RN розбиваються на підмножини , i=1,2,…,n таким чином, що:
Критерієм оптимальності вибору числа груп визначено або математичне очікування часу перебування довільного біта в групі, або складність апаратурної реалізації генератора, при цьому показано, що відзначальною рисою даного методу є рівномірний характер закону розподілу імовірностей вихідних наборів.
Рис.3 ілюструє структурні особливості запропонованого методу побудови генератора послідовності спеціального виду, що поєднує можливість керування як імовірністю стану виходу, так і імовірністю переключення вихідного сигналу. Метод орієнтований на використання стандартних цифрових вузлів і джерела рівноімовірних керуючих наборів.
Імовірність P(1) одиничного стану на виході такої генеруючої структури:
Точність визначення величини P(1) (наприклад, 0.1, 0.01, 0.001,……) дорівнює 1/R, при чому
.
Імовірність P(S)W зміни станів суміжних бітів (без урахування конкатенації вихідних наборів схеми пам’яті):
Якщо b(1) –число слів, для котрих , b(0) –число слів, для котрих , e(1) –число слів, для котрих , e(0) –число слів, для котрих , тоді:
,
тобто:
Розроблено методику вибору основних структурних параметрів генератора, показано, що зменшення розрядності вихідного слова схеми пам'яті і відповідне збільшення числа комірок пам’яті призводить до росту ентропії вихідної послідовності, у той же час альтернативний спосіб визначення даних параметрів приводить до зменшення структурної складності. Складено досить детальний алгоритм процедури програмування вихідного стану схем пам'яті, використання цього алгоритму дозволяє на практиці оптимізувати вихідні імовірносні параметри генератора послідовностей спеціального виду. Розроблено методику оцінки похибки, що виникає в процесі формування ПВП із можливістю керування декількома вихідними параметрами. Суть і особливості даної методики полягають у врахуванні трьох головних складових результуючої похибки, а саме: а) похибка δ(r), обумовлена представленням необхідних значень імовірностей у форматі двійкових чисел, δ(r) 2-(n+1), n –розрядність коду імовірності, б) похибка формування опорних ПВП, що визначають вихідні параметри генератора (одержано аналітичну оцінку верхньої межі погрішності на вихаді перетворювачів "код-імовірність" |δ(z)| ≤ 1/2n) і в) похибки, пов'язана з логічним об'єднанням опорних ПВП на виході генератора.
В третьому розділі дисертаційної роботи досліджується досить широкий клас спеціалізованих структурних засобів, який має практичне використання, і який включає формувачі послідовностей рівновагових наборів, що мають властивості визначати (програмувати) імовірності для вихідних каналів (тобто, імовірності станів каналів вихідного регістра) незалежно один від іншого. Як приклад області можливого застосування таких структурних засобів можна назвати задачу підвищення ефективності процедур моделювання несправностей різної кратності в неоднорідних відмовостійких багатопроцесорних обчислювальних системах. Проведений аналіз програмного методу формування таких послідовностей для моделювання відмовних ситуацій багатопроцесорної системи показав низьку продуктивність процедури моделювання в цілому.
Розроблено спеціалізовану структуру апаратурного керованого генератора (вона показана на рис. 4), що є альтернативою відносно чисто програмних методів і алгоритмів формування послідовностей рівновагових наборів з урахуванням розподілу імовірностей сигналів на виходах формувача.
Нижче наведені логічні умови роботи основних вузлів формувача. Зокрема, для вузла LO:
Умови роботи вузла R1:
Вузол комбінаційної керуючої логіки CL:
Комутатор CF кіл зворотного зв’язку :
У дисертації наведено алгоритм роботи запропонованої спеціалізованої структури керованого генератора.
Розроблено методику одержання заданих значень основних імовірносних характеристик генератора, що дозволяє забезпечити підвищення продуктивності моделюючих процедур на етапі їх налагоджування і виконання, реалізованих з використанням запропонованих структурних засобів формування керованих послідовностей рівновагових наборів.
Умови співвідношення імовірностей:
P1 ≥ P2 ≥ P3 ≥ … ≥ PN, а також j (1 Pj 0)),
Залежність між імовірностями Pj і Pj
rP1 = P1 ½ k 1/N + P2 ½ k 2/N+…+PN-1 ½ k (N-1)/N + PN ½ k (N/N),
rP2 = P2 ½ k 2/N + …PN-1 ½ k (N-1)/N + PN ½ k (N/N),
……………………………………………………………………….…………….…….
rPN-1 = PN-1 ½ k (N-1)/N + PN ½ k (N/N),
rPN = PN ½ k (N/N),
,
причому Pj – імовірність одиничного стану j-го виходу генератора (тобто імовірність одиничного значення j-го біта регістра REG), Pj – імовірність вибору з блоку пам'яті MEM ідентифікатора j-го каналу генератора, r - нормувальний коефіцієнт). Таки чином,
r = k / (2N) 1 / [(P1 – P2) / 1 + (P2 – P3) / 2 + (P3 – P4) / 3 + …
…..+ (PN – 0) / N] = k / 2N .
Для ілюстрації ефективності розробленої методики розрахунку нормувальних коефіцієнтів і визначення основних налагоджувальних імовірносних характеристик керованого формувача псевдовипадкових сигналів зі змінюваним законом розподілу розглянуто числові приклади, що конкретизують особливості вибору параметрів генератора відмовних ситуацій багатопроцесорних неоднорідних систем.
До найбільш істотних результатів, отриманих у четвертому розділі дисертації, можна віднести положення, пов'язані з організацією моделюючих процедур для оцінки основних параметрів проектованих спеціалізованих структурних засобів формування керованих двійкових псевдовипадкових послідовностей.
Розглянуто відомі підходи до оцінки показників якості стохастичних послідовностей і розроблено методики адаптації цих підходів для оцінки ефективності структур формувачів таких послідовностей. Зокрема, найбільш простим критерієм виявляється критерій статистичної незалежності елементів послідовностей псевдовипадкових станів:
P() = ,
де: P(σi) – імовірність настання події σi, P() – імовірність одночасного настання n подій σi.
У той же час значно складніше обчислюються такі показники якості псевдовипадкових послідовностей, якими є коефіцієнти кореляції
й автокореляції
,
причому стандартні відхилення
, ,
і, відповідно, коваріація змінних
.
Отримано оцінки кількісних значень такого важливого параметра, що визначає якість роботи формувача, як величина математичного очікування інтервалу дискретного часу, на якому з заданою імовірністю формується повна множина вихідних наборів визначеної ваги. Розроблено алгоритм оцінки частоти появи у вихідних послідовностях серій однакових елементів, запропоновано методику знаходження довжини інтервалу моделювання у відповідності до виконання умови, пов'язаної з забезпеченням ситуації, коли на даному інтервалі частота появи довільного набору відрізнялася б від значення відповідної імовірності не більш, ніж на задану величину.
Розроблено алгоритм оцінки величини інтервалу моделювання при наявності певних обмежень зверху, наприклад, внаслідок надмірної тривалості і/чи вартості процедур моделювання.
У цьому ж розділі дисертації розглянуто загальний склад програмного комплексу моделювання керованих генераторів ПВ–послідовностей і сформульовано вимоги до функціонального призначення основних програмних модулів системи моделювання а також наведено алгоритми роботи основних програмних модулів.
Сформульовано конкретні вимоги щодо особливостей вихідної інформації, тобто визначена структура файлів і формати вихідних даних моделювання, причому ці вимоги дозволяють врахувати структурні і функціональні особливості комплексу сервісних програмних засобів, спрямованих на підвищення продуктивності і полегшення роботи оператора в процесі моделювання керованих формувачів ПВ - послідовностей, а також у ході аналізу й оцінки основних стохастичних параметрів таких пристроїв.
У додатках представлені деякі результати моделювання розроблених структур генераторів. На основі аналізу цих даних можна зробити обґрунтований висновок про досить високу якість формованих псевдовипадкових послідовностей, зокрема, про близькість отриманих реальних характеристик генераторів до обчислених аналітично імовірносних показників.
ВИСНОВКИ
В дисертаційній роботі приведені результати наукових досліджень, спрямованих на вирішення складної науково-технічної проблеми розробки ефективних структурних методів синтезу спеціалізованих апаратних засобів генерації керованих псевдовипадкових двійкових послідовностей і послідовностей двійкових векторів. До основних результатів роботи можна віднести наступне.
1. Гроль В.В., Романкевич А.М., Фаллаги Али. Генерация ПС-последовательностей с управлением по двум параметрам // Вісник НТУУ “КПІ”.- Інформатика, управління та ОТ.-2006.- №45.-С.85-92 (розроблено методику заповнення схем пам’яті генератора з метою одержання необхідних статистичних характеристик керованої вихідної послідовності).
2. Гроль В.В., Лупанова Р.И., Фаллаги Али. О генерации псевдослучайных последовательностей двоичных равновесных наборов // Вісник НТУУ “КПІ”.- Інформатика, управління та ОТ.-2004.- Вип.42.-С. 11-19 (розроблено логічну структуру схеми об'єднання розрядів керованого генератора псевдовипадкових послідовностей, а також методика оцінки розрядності зсувної регістрової групи).
3. Гроль В.В., Хедаятоллах Бахтари, Фаллаги Али. Структурный метод формирования последовательностей двоичных псевдослучайных (n,k)-векторов при моделировании ОМС // Теоретические проблемы информатики и ее приложения: Сб.науч.тр., Под ред. проф. А.А.Сытника.-Изд-во Сарат. ун-та, 2007.- Вып. 7.-С.36-43 (сформульовано вимоги до параметрів генеруючої структури та розроблено алгоритм процедури програмування імовірності вихідних двійкових сигналів).
4. Гроль В.В., Романкевич В.А., Фаллаги Али, Фесенюк А.П. Оценка погрешности формирования управляемых псевдослучайных последовательностей // Вісник Хмельницького Національного університету, Хмельницький, 2007.-т.1.- с. 149-153 (складено методику оцінки впливу на результуючу похибку генерованої послідовності способу завдання ймовірностей за допомогою двійкових наборів перетворювачів “код-ймовірність”).
5. Romankevych A., Grol V., Fallahi Ali Structural Method of Pseudorandom Fixed Weight Binary Pattern Sequences Generation // Proceedings of IEEE East-West Design & Test Workshop,- Russia, Sochi, September 2006.- p. 217-221 (сформульовано вимоги до структури формувача послідовностей псевдовипадкових рівновагових наборів та запропоновано схемотехнічну реалізацію комбінаційну частину генератора).
6. Романкевич А.М., Гроль В.В., Фаллаги Али. Генерация ПС-последовательностей двоичных наборов с управляемым законом распределения // Інформаційно-керуючі системи на залізничному транспорті. Тези доповідей.- 2005.- №5.- С. 97 (розроблено алгоритм настроювання схеми оперативної пам’яті з урахуванням закону розподілу ймовірностей вихідних сигналів).
7. Романкевич А.М., Фаллаги Али, Фесенюк А.П., Скрицкий А.В. О погрешности генератора псевдослучайных последовательностей, управляемого по двум параметрам // Інформаційно-керуючі системи на залізничному транспорті. Тези доповідей.- 2006.- №5.- С. 103-104 (одержано аналітичні співвідношення для оцінки складової частини похибки вихідної послідовності, яка обумовлена особливостями побудови перетворювачів “код-ймовірність”).
8. Романкевич А.М., Фаллаги Али, Лупанова Р.И., Фесенюк А.П. О формировании псевдослучайных последовательностей с управляемыми параметрами // Труды 7-й МНПК СИЭТ-2006 Одесса.- 2006.- С. 152 (розроблено метод та алгоритм формування вихідної керованої послідовності на основі конкатенації двійкових багаторозрядних векторів).
АНОТАЦІЇ
Фаллагі Алі. Методи і засоби формування спеціалізованих псевдовипадкових керованих двійкових послідовностей. – Рукопис.
Дисертація на здобуття ученого ступеня кандидата технічних наук за спеціальністю 05.13.05 – Елементи і пристрої обчислювальної техніки та систем управління. - Національний технічний університет України “Київський політехнічний інститут”. – Київ, 2007.
Дисертаційна робота присвячена питанням розробки методів і засобів формування послідовності керованих псевдовипадкових двійкових сигналів і векторів, створено структурні методи і відповідні апаратурні засоби формування послідовностей псевдовипадкових наборів із заданою вагою, обґрунтовано вибір критеріїв, відповідно до яких на етапі проектування можна забезпечити необхідні значення основних параметрів формувачів послідовностей з одночасним керуванням по двох залежних параметрах (імовірність появи одиничного сигналу та імовірність переключення), розроблено систему критеріїв оцінки показників якості імовірносних послідовностей, що генеруються, на основі яких запропоновані методики моделювання генеруючих структур, сформульовано вимоги до функціонального призначення основних програмних модулів системи моделювання спеціалізованих структурних засобів генерації керованих псевдовипадкових послідовностей.
Ключові слова: двійкові послідовності, генератори псевдовипадкових наборів, лінійні послідовносні пристрої, нелінійний зворотній зв’язок.
Фаллаги Али. Методы и средства формирования специализированных псевдослучайных управляемых двоичных последовательностей. – Рукопись.
Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 – Элементы и устройства вычислительной техники и систем управления. - Национальный технический университет Украины “Киевский политехнический институт”. – Киев, 2007.
Диссертационная работа посвящена вопросам разработки и исследования методов и средств построения специализированных цифровых схем, позволяющих с высокой производительностью формировать псевдослучайные последовательности двоичных сигналов и векторов с возможностью управления разными вероятностными параметрами таких последовательностей, проведен сравнительный анализ известных методов формирования псевдослучайных последовательностей, сформулированы рекомендации по выбору структур управляющих генераторов псевдослучайных наборов.
Разработаны структурные методы и соответствующие аппаратурные средства формирования последовательностей псевдослучайных наборов с заданным весом, разработана методика выбора основных структурных параметров генератора с одновременным управлением по двум зависимым параметрам, а именно: вероятность появления единичного сигнала и вероятность переключения.
Для решения задач формирования подобных управляемых двоичных последовательностей разработан структурный подход, ориентированный на сочетание использования типовых цифровых узлов и классического источника равновероятных управляющих наборов.
Получены аналитические соотношения, позволяющие при соответствующем задании некоторых структурных параметров формирователя, таких, как разрядность выходного слова и число ячеек схемы памяти, улучшить статистические свойства выходной последовательности либо уменьшить структурную сложность специализированной аппаратуры.
Предложен оригинальный структурный метод формирования двоичных последовательностей, обеспечивающий возможность управления одновременно по двум параметрам: вероятность появления единичного сигнала и вероятность переключения. Основной идеей метода является конкатенация векторов, которые псевдослучайно выбираются из типовой схемы памяти, благодаря чему может быть значительно повышена эффективность процедур тестирования специализированных цифровых объектов или расширены функциональные возможности контрольно-диагностического оборудования.
Также получены аналитические соотношения для оценки погрешности, возникающей в процессе формирования последовательностей с возможностью управления вероятностными параметрами, при этом данная методика учитывает такие составляющие, как погрешность, обусловленная представлением требуемых значений вероятностей в формате двоичных чисел, погрешность формирования опорных псевдослучайных последовательностей, определяющих выходные параметры генератора, и погрешность, связанная с логическим объединением на выходе генератора опорных последовательностей.
Исследован широкий и имеющий прикладное значение класс структурных средств, включающий формирователи последовательностей равновесных наборов, позволяющие получить вероятности появления двоичных сигналов на выходных каналах независимо друг от друга.
Обоснован выбор критериев, в соответствии с которыми на этапе проектирования можно обеспечить необходимые значения основных параметров формирователей последовательностей с управлением по двум параметрам.
Разработана система критериев оценки показателей качества вероятностных генерируемых последовательностей, на основе которых предложены методики моделирования генерирующих структур, сформулированы требования к функциональному назначению основных программных модулей системы моделирования специализированных структурных средств генерации управляемых псевдослучайных последовательностей и разработаны алгоритмы выполнения наиболее важных системных и сервисных процедур для этих модулей, а также рассмотрен процесс взаимодействия программных модулей в составе моделирующего комплекса.
Основное назначение предложенных методов, алгоритмов и технических средств – повышение эффективности диагностирования цифровой аппаратуры, а также, и это касается в первую очередь генераторов равновесных векторов, – формирование последовательности векторов состояния системы при проведении статистических экспериментов с моделями поведения отказоустойчивых многопроцессорных систем в потоке отказов.
Ключевые слова: псевдослучайные последовательности, генераторы псевдослучайных наборов, управляемые вероятностные параметры, линейные последовательностные машины, схемы с нелинейной обратной связью, моделирование цифровых устройств.
Fallahi Ali. Methods and means for specialized pseudorandom controlled binary sequences' implementation. - Manuscript.
Thesis for a PhD degree by specialty of 05.13.05 – Elements and units for computers and control systems. – National Technical University of Ukraine "Kiev Polytechnic Institute". – Kiev, 2007.
Thesis deals with questions of designing and studying of the methods and means to build a specialized digital circuits which allow a high efficiency generation of a pseudorandom binary vectors" sequences with the feature of being controlled by some probabilistic parameters, a comparative analysis of known methods to form the pseudorandom sequences had been implemented, some recommendations on choice of pseudorandom patterns generators' controlling structures had been formulated, a set of criterions on evaluation of quality characteristics of the generated probabilistic sequences had been proposed and on the basis of which some methodic for modeling of the generating structures had been designed, a demands on functional destination of main program modules to simulate a specialized structural means for generation of controlled pseudorandom sequences had been formulated and an algorithms for most important system and service functions" implementation had been constructed, furthermore a process of interaction of those modules as parts of a modeling complex had been reviewed.
Key words: pseudorandom sequences, pseudorandom pattern generators, controlled probabilistic parameters, linear sequential units, circuits with nonlinear feedback, modeling of digital circuits.