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

Харківський національний університет радіоелектроніки

СТРУКТУРНИЙ СИНТЕЗ КОМПОНЕНТІВ ЦИФРОВИХ СИСТЕМ НА ОСНОВІ БІНОМІАЛЬНИХ ЧИСЕЛ

05.13.05 - комп'ютерні системи та компоненти

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

Гриненко Віталій Вікторович

УДК 004.312.43

Харків - 2010

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

Робота виконана на кафедрі електроніки і комп'ютерної техніки Сумського державного університету Міністерства освіти і науки України.

Науковий керівник: доктор технічних наук, професор Борисенко Олексій Андрійович, Сумський державний університет, завідувач кафедри електроніки і комп'ютерної техніки

Офіційні опоненти: доктор технічних наук, професор

Кривуля Геннадій Федорович

Харківський національний

університет радіоелектроніки,

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

доктор технічних наук, професор

Краснобаєв Віктор Анатолійович,

Харківський національний технічний університет сільського господарства ім. Петра Василенка, професор кафедри автоматизації та комп'ютерно-інтегрованих технологій

Захист відбудеться “17” листопада 2010 р. о 15-00 год. на засіданні спеціалізованої вченої ради Д 64.052.01 у Харківському національному університеті радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна,14, тел. (057)-7021-451.

З дисертацією можна ознайомитися в бібліотеці Харківського національного університету радіоелектроніки за адресою: 61166, м. Харків, пр. Леніна, 14.

Автореферат розісланий “15” жовтня 2010 р.

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

вченої ради Д 64.052.01

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми.

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

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

Вперше питання про синтез надійних систем з ненадійних компонентів було поставлене Дж. фон Нейманом. Ним був запропонований метод, заснований на введенні структурної надлишковості. Методи поелементного резервування розглядаються також в роботах І. Мура і К. Шеннона. У роботах
М. А. Гаврилова і А. Д. Закревського були запропоновані і отримали подальший розвиток методи, засновані на уведенні інформаційної надлишковості. Питанням спільного використання інформаційної та апаратної надлишковостей при побудові цифрових пристроїв присвячені роботи Хєтагурова Я.А., Согомоняна Є.С., Харченко В.С., Рудницького В.М. Перспективним напрямом дослідження є створення пристроїв, завадостійкість яких базується на природній надлишковості.

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

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

Зв'язок роботи з науковими програмами, планами, темами.

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

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

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

Для досягнення цієї мети потрібно вирішити такі завдання:

1. Розробити метод аналізу завадостійкості біноміальних кодів за ймовірностями помилок.

2. Удосконалити метод синтезу послідовних біноміальних лічильників для підвищення їх швидкодії та спрощення механізму зміни параметрів біноміальної системи числення.

3. Розробити метод побудови модифікованих біноміальних кодів на основі біноміальних чисел з підвищеними рівнем завадостійкості.

4. Розробити методи кодування, декодування і лічби комбінацій модифікованого біноміального коду.

5. Розробити методики оцінки завадостійкості цифрових пристроїв з резервуванням на основі біноміальних чисел.

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

Предмет дослідження - методи структурного синтезу і оцінки компонентів цифрових систем на основі біноміальних чисел.

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

Наукова новизна одержаних результатів. У ході вирішення поставлених завдань автором особисто були отримані такі результати:

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

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

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

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

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

Результати дисертаційної роботи використані в науково-виробничому колективному підприємстві «Преобразователь» (м. Суми) у проекті системи передачі даних в автоматизованій системі керування технологічним процесом розподілення електроенергії в електричних мережах ВАТ «Сумиобленерго» Сумської групи підстанцій (довідка про впровадження від 09.11.2009). Методи побудови і оцінки завадостійкості цифрових пристроїв на основі модифікованих біноміальних кодів, а також пакети програм для дослідження імовірнісних характеристик біноміальних кодів використані в Сумському державному університеті в навчальному процесі в дисциплінах «Інформаційні основи електронної техніки», «Основи теорії кодування», «Цифрова схемотехніка», «Цифрові автомати», а також при виконанні дипломних проектів і випускних робіт магістрів (акт впровадження від 05.11.2009).

Особистий внесок здобувача. Всі основні результати дисертаційної роботи одержані автором самостійно. У роботах, виконаних у співавторстві, автору належать такі результати: у роботі [7] - розглянуті питання виявлення помилок в роботі біноміальних лічильних пристроїв; у роботі [8] - удосконалено метод синтезу послідовних біноміальних лічильників та запропоновано спосіб побудови біноміальних лічильників зі змінними параметрами і генераторів рівноважних кодів; у роботі [9] - запропоновано методику оцінки завадостійкості для обчислення імовірнісних показників завадостійкості при використанні мажоритарного принципу кодування; у роботі [10] - запропонована метод лічби та структура лічильників на основі модифікованих біноміальних кодів; у роботі [13] - запропонована модель для оцінки завадостійкості біноміальних кодів; у роботі [14] - запропонований метод побудови та оцінки завадостійкості модифікованих біноміальних кодів.

Апробація результатів дисертації. Основні результати дисертації доповідалися та обговорювалися на конференціях: Міжнародній науковій конференції ”Сучасні методи кодування в електронних системах ” СМКЕС-2002 (Суми, СумДУ, 2002 р.); другій міжнародній науковій конференції ”Сучасні методи кодування в електронних системах” СМКЕС-2004 (Суми, СумДУ, 2004 р.); першій міжнародній науковій конференції «Теорія та методи обробки сигналів» (Київ, НАУ, 2005 р.); Міждержавній науково-методичній конференції «Проблеми математичного моделювання» (Дніпродзержинськ, ДДТУ, 2006 р.); першій Міжнародній науково-практичній конференції «Методи та засоби кодування, захисту й ущільнення інформації» (Вінниця, ВНТУ, 2007 р.); другій міжнародній науковій конференції «Теорія та методи обробки сигналів» (Київ, НАУ, 2008 р.); Гарантоздатні (надійні та безпечні) системи, сервіси та технології DESSERT 2009 (Кіровоград, 2009 р.) та на наукових семінарах Сумського державного університету.

Публікації. За результатами виконаних досліджень опубліковано 16 робіт, у тому числі 9 статей у наукових фахових виданнях, що входять до переліків, затверджених ВАК України, 6 статей у збірниках праць науково-технічних конференцій та 1 патент України на корисну модель.

Структура та обсяг дисертації. Робота складається із вступу, 5 розділів, загальних висновків, додатків. Загальний обсяг дисертації - 177 сторінок, у тому числі 140 сторінок основного тексту. Кількість додатків - 4. Дисертація містить 23 рисунки, 29 таблиць та список використаних джерел із 116 назв на 12 сторінках.

ОСНОВНИЙ ЗМІСТ РОБОТИ

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

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

На основі аналізу шляхів підвищення завадостійкості цифрових пристроїв було обґрунтоване застосування інформаційної надлишковості з використанням біноміальних двійкових чисел. Компоненти цифрових систем на основі біноміальних чисел можуть бути використані при побудові систем передачі та стиску даних, захисту інформації від несанкціонованого доступу. Зокрема біноміальні лічильники можуть бути використані при розробці датчиків систем автоматизованого керування. Ще однією корисною властивістю біноміальних кодів є можливість побудови на їх основі рівноважних кодів та сполучень.

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

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

Як показники завадостійкості біноміальних пристроїв обрані ймовірності відповідно правильних переходів, помилкових переходів, помилкових переходів, що виявляються і не виявляються.

Процес появи помилок на виходах цифрового пристрою характеризується ймовірностями та спотворення значень відповідно одиничних і нульових станів (переходів та ).

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

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

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

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

,

при дотриманні обмежень:

,

,

де - максимальне число одиниць у біноміальному числі;

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

- кількість розрядів біноміального числа (довжина);

- порядковий номер розряду;

- сума одиничних значень цифр біноміального числа від ()-го розряду до ()-го включно:

,

,

.

Другим співмножником -го доданку є вага -го розряду біноміального числа яка дорівнює

.

Діапазон біноміальних чисел визначається виразом

.

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

Таблиця 1

Рівномірний біноміальний код з параметрами і

Пор. номер	Біноміальний код	Біноміальний рівномірний код	Пор. номер	Біноміальний код	Біноміальний рівномірний код
0	00	00000	8	10111	10111
1	010	01000	9	1100	11000
2	0110	01100	10	11010	11010
3	01110	01110	11	11011	11011
4	01111	01111	12	11100	11100
5	100	10000	13	11101	11101
6	1010	10100	14	1111	11110
7	10110	10110

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

Рис 1. Біноміальний лічильник з підвищеною швидкодією

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

.

Максимальні значення апаратурних витрат спостерігаються для лічильників, побудованих на основі біноміальних кодів з . При порівнянні лічильників з близькими за значенням модулями лічби (діапазоном ), але різною кількістю розрядів апаратурні витрати більші в лічильниках, побудованих на основі кодів з більшим значенням параметра . Таким чином було зроблено висновок, що апаратурні витрати на одиницю модуля лічби збільшуються зі збільшенням параметра , тобто кількості розрядів біноміальної кодової комбінації.

Недоліком лічильника, наведеного на рис.1, є неможливість зміни параметрів та . Для побудови лічильника зі змінними та розглянуті біноміальні коди з різними параметрами, і встановлено, що в кодах з різними та однаковими в перших біноміальних комбінаціях коду з молодші розряди відповідають біноміальному коду з .

Таким чином, для перенастроювання лічильника, що працює в біноміальному коді з на код з , при незмінному необхідно блокувати установку в одиницю -го розряду при скиданні в нуль -го розряду. Для цього в лічильник з параметром необхідно увести сигнали блокування переносу , які дозволяють установку в одиницю тригера -го розряду при скиданні в нуль тригера -го розряду. Сигнал визначається наступним виразом:

.

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

Особливості побудови біноміальних кодів дозволяють будувати на їх основі рівноважні коди. Із комбінацій рівноважного коду можна отримати сполучення. Так комбінації 010111 відповідає сполучення 5321, а комбінації 110110 - 6532 і т. д.

Формування комбінації рівноважного коду на основі біноміального коду починається з додаткового розряду, що стоїть праворуч від молодшого розряду. У даний розряд записується одиниця, якщо кодова комбінація біноміального коду містить менш ніж одиниць. Далі записуються одиниці в усі подальші розряди кодової комбінації до тих пір, поки їх загальне число не стане рівним . Якщо в біноміальній комбінації вже є одиниць, то в додатковий розряд записується нуль, а решта всіх розрядів залишається без змін. Наприклад, на основі біноміального числа 01110 буде сформована комбінація 011101 рівноважного коду довжиною та кількістю одиниць .

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

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

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

,

і ймовірність невиявлення помилок



де

,

,

,

.

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

Проведене дослідження імовірнісних характеристик біноміальних кодів, за результатами яких були зроблені наступні висновки:

- при симетричному характері помилок () ймовірність невиявлення помилки в біноміальних кодах збільшується зі збільшенням , і при малих значеннях ймовірності помилки характер даної залежності близький до лінійного;

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

- ймовірність невиявлення помилки у кодів з рівним , але різним змінюється за нелінійним законом з екстремумом при , збільшується із збільшенням до , і зменшується із збільшенням після , якщо - парне. У разі, коли - непарне, ймовірність невиявлення помилки збільшується до і зменшується після .

На підставі досліджень імовірнісних характеристик біноміальних кодів, а також у зв'язку з тим, що апаратурні витрати при побудові біноміальних лічильних пристроїв збільшуються зі збільшенням , поставлене завдання забезпечення модуля лічби біноміальним лічильним пристроєм, з метою мінімізації довжини біноміальної комбінації, при обмеженнях

,

,

де - максимально допустима довжина кодової комбінації;

- максимальне значення ймовірності невиявлення помилки.

Завдання полягає у виборі параметрів та біноміального коду, що задовольняє обмеженням ,, для заданих ймовірностей помилок при дотриманні умови здійсненності кодування

.

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

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

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

Крок 3. Перевірити вирішуваность завдання . Якщо , то завдання визнається нерозв'язним.

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

Крок 5. Вивести значення і , якщо завдання оптимізації визнане вирішуваним.

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

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

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

.

Кількість різних модифікованих біноміальних кодів, отриманих шляхом об'єднання підмножин з різною кількістю одиниць , визначається співвідношенням:

.

Отже, на основі біноміальної системи числення з параметрами та можна побудувати:

,

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

Розглянемо модифікований біноміальний код з параметрами , і , який побудований на основі біноміального коду з параметрами і (табл. 2). Комбінація модифікованого біноміального коду з числом одиниць може бути побудована на основі комбінації рівноважного коду довжиною з кількістю одиниць з додатковими нульовими розрядами до довжини . Комбінацію рівноважного коду з числом одиниць можна отримати на основі комбінації проміжного біноміального коду з параметрами і .

Таблиця 2

Модифікований біноміальний код з параметрами , і

Пор. номер	Параметри і проміжного біноміального коду	Комбінація проміжного біноміального коду	Комбінація рівноважного коді з параметрами і	Модифікований біноміальний код
0		0	00	000000
1 2 3		00 01 10	001 010 100	001000 010000 100000
4 5 6 7 8 9 10 11 12 13		0000 0100 0110 0111 1000 1010 1011 1100 1101 1100	00111 01011 01101 01110 10011 10101 10110 11001 11010 11100	001110 010110 011010 011100 100110 101010 101100 110010 110100 111000

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

Метод кодування модифікованим біноміальним кодом містить у собі такі кроки:

Крок 1. Обчислити кількісний еквівалент початкової кодової комбінації . Параметру надати значення першого елементу впорядкованої множини (). Перейти на крок 2.

Крок 2. Визначити параметри і проміжного біноміального коду. За формулою обчислити потужність даного коду. Провести порівняння потужності з кількісним еквівалентом . Перейти на крок 3.

Крок 3. Якщо , то кількісний еквівалент зменшити
на . Параметру надати значення наступного елемента множини (). Перейти до кроку 2. Якщо , то кількісному еквіваленту надати значення . Перейти на крок 4.

Крок 4. За кількісним еквівалентом і параметрами проміжного біноміального коду і отримати біноміальну кодову комбінацію. Перейти на крок 5.

Крок 5. На основі комбінації біноміального коду сформувати рівноважну кодову комбінацію довжиною розрядів з числом одиниць . Шляхом дописування нульових розрядів до довжини отримати комбінацію у модифікованому біноміальному коді.

Метод лічби комбінацій модифікованого біноміального коду містить наступні кроки:

Крок 1. Установити параметри і , що відповідають першому значенню (). Перейти до кроку 2.

Крок 2. Виконати перебір комбінацій біноміального коду з параметрами і до формування сигналу «останов». При цьому на основі біноміальної комбінації сформувати комбінацію модифікованого біноміального коду. При формуванні сигналу «останов» перейти до кроку 3.

Крок 3. Якщо не є максимальним для даного коду, то встановити наступне значення , і перейти до кроку 2. Продовжити перебір комбінацій біноміального коду з новими параметрами і . Якщо дорівнює максимальному значенню, то цикл перебору комбінацій закінчений.

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

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

Проведено дослідження завадостійкості модифікованих біноміальних кодів. За результатами досліджень був зроблений висновок, що застосування модифікованих біноміальних кодів з певними параметрами дозволяє значно зменшити ймовірність невиявлення помилок у порівнянні з пристроями на основі біноміальних кодів.

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

Для підвищення завадостійкості цифрових пристроїв пропонується використовувати структурну надлишковість із застосуванням дублювання та мажоритарних структур. Запропоновано методику оцінки завадостійкості біноміальних пристроїв з дублюванням і апаратним контролем у кожному каналі.

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

Порівняльний аналіз способів контролю виявив значно менше значення ймовірності невиявлення помилки при використанні дублювання з рівнозначними каналами порівняно з дублюванням і організацією роботи з провідним каналом.

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

Для наведених способів контролю отримано співвідношення для визначення імовірнісних характеристик завадостійкості.

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

ВИСНОВКИ

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

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

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

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

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

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

6. На основі аналізу алгоритмів побудови біноміальних кодів була запропонована методика синтезу біноміальних лічильників зі змінними параметрами, що дозволило спростити їх структуру, а також структуру генераторів рівноважних кодів та сполучень.

7. Запропонований метод аналізу завадостійкості та вибору параметрів біноміальних кодів був використаний в науково-виробничому колективному підприємстві «Преобразователь» (м. Суми) у проекті системи передачі даних в автоматизованій системі керування технологічним процесом розподілення електроенергії в електричних мережах ВАТ «Сумиобленерго» Сумської групи підстанцій.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Гриненко В.В. Оценка помехоустойчивости систем передачи данных на основе биномиальных двоичных чисел. / В.В. Гриненко // Вісник Сумського державного університету.- 2002. -№ 12(45).- С. 131-138.

2. Гриненко В.В. Моделирование систем хранения и передачи данных на основе биномиальных кодов / В.В. Гриненко // Вісник Сумського державного університету.- 2003. -№ 11(57).- С. 100-105.

3. Гриненко В.В. Оценка помехоустойчивости биномиальных модифицированных кодов / В.В. Гриненко // Вісник Сумського державного університету. - 2004. -№ 12(71).- С. 131-138.

4. Гриненко В.В. Алгоритм и устройство перебора комбинаций биномиального модифицированного кода / В.В. Гриненко // Вісник Сумського державного університету.- 2008. -№ 2.- С. 35-44.

5. Гриненко В.В. Устройство декодирования комбинаций биномиального модифицированного кода / В.В. Гриненко // Електроніка та системи управління. - 2008. -№ 3 (17).- С. 27-34.

6. Гриненко В.В. Алгоритм и устройство преобразования двоичных чисел в биномиальный модифицированный код / В.В. Гриненко // Радіоелектронні і комп'ютерні системи.- 2009. - №6(40).- С. 193-197.

7. Борисенко А.А. Биномиальные счетные устройства /А.А. Борисенко, В.В. Гриненко, А.Е. Горячев, С.В. Костель, В.В. Петров // Вісник Сумського державного університету.- 2008. -№ 1.- С. 147-157.

8. Борисенко А.А. Синтез устройств на основе биномиальных чисел /
А.А. Борисенко, В.В. Гриненко // Східно-Європейський журнал передових технологій. - 2010.- №1/7 (43). - С. 55-56.

9. Борисенко А.А. Моделирование систем передачи данных с мажоритарным принципом кодирования на основе биномиальных кодов /
А.А. Борисенко, И.А. Кулик, В.В. Гриненко // Автоматизированные системы управления и приборы автоматики.- 2004. - № 128.- С. 9-16.

10. Пат. на корисну модель 48328 Україна, МПК (2009) Н03К 23/00. Лічильник імпульсів / О.А. Борисенко, В.В. Гриненко; заявн. Сумський державний університет. - № u200910488; заявл. 16.10.2009; опубл. 10.03.2010; Бюл. №5.

11. Гриненко В.В. Формула оценки помехоустойчивости биномиальных чисел / В.В. Гриненко // Тезисы докладов Международной научной конференции «Современные методы кодирования в электронных системах». - Сумы: СумГУ. - 2002.- С. 52.

12. Гриненко В.В. Дублирование в системах передачи данных на основе биномиальных кодов / В.В. Гриненко // Тези доповідей Першої міжнародної наукової конференції «Теорія та методи обробки сигналів». - Киев: КНАУ. - 2005. С. 86-87.

13. Гриненко В.В., Моделирование процессов передачи данных в инфорационных системах на основе биномиальных кодов / В.В. Гриненко, Т.А. Протасова // Тези доповідей Міждержавної науково-методичної конференції «Проблеми математичного моделювання». - Дніпродзержинськ: ДДТУ. - 2006.- С. 56-57.

14. Гриненко В.В. Самопроверяемые устройства на основе биномиальных модифицированных кодов / В.В. Гриненко, И.В. Голофост // Тезисы докладов Второй Международной научной конференции «Современные методы кодирования в электронных системах». - Сумы: СумГУ. - 2004.- С. 69-70.

15. Гриненко В.В. Оценка эффективности контроля ошибок в биномиальных цифровых устройствах / В.В. Гриненко // Тези доповідей Першої Міжнародної науково-практичної конференції «Методи та засоби кодуваня, захисту й ущільнення інформації». - Вінниця: ВНТУ. - 2007. - С. 24.

16. Гриненко В.В. Алгоритм декодирования комбинаций биномиального модифицированного кода / В.В. Гриненко // Тези доповідей Другої міжнародної наукової конференції «Теорія та методи обробки сигналів». - Киев: КНАУ. - 2008. - С. 33-34.

АНОТАЦІЯ

біноміальний лічильник дублювання канал

Гриненко В.В. Структурний синтез компонентів цифрових систем на основі біноміальних чисел - Рукопис.

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

У дисертації вирішено науково-прикладну задачу розробки методів синтезу завадостійких компонентів цифрових систем на основі біноміальних чисел.

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

Розроблено метод аналізу завадостійкості та вибору параметрів біноміальних кодів, що дало можливість обирати параметри біноміального коду в залежності від рівня помилок.

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

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

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

АННОТАЦИЯ

Гриненко Виталий Викторович Структурный синтез компонентов цифровых систем на основе биномиальных чисел - Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 - компьютерные системы и компоненты. - Харьковский национальный университет радиоэлектроники, Харьков, 2010.

В диссертации решена научно прикладная задача синтеза помехоустойчивых компонентов цифровых систем на основе биномиальных чисел.

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

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

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

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

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

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

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

ABSTRACT

Grinenko V.V. Structural synthesis of components of the digital systems on the basis of binomial numbers. - Manuscript.

Thesis for a Ph.D. science degree by specialty 05.13.05 - computer systems and components, Kharkiv National University of Radioelectronics, Kharkiv, 2010.

In dissertation the applied task of synthesis of antijamming components of the digital systems is decided scientifically on the basis of binomial numbers.

The new variants of construction of binomial counters which are characterized a large fast-acting and possibility of change of parameters are offered.

The method of estimation of noise stability of binomial codes is developed, that enabled to choose the parameters of binomial code depending on the level of errors.

The method of construction of the noise stability modified binomial codes is developed, on the basis of binomial numbers, the change of parameters of which allows to adapt oneself to the noise level. The methods of the adaptive encoding, decoding and account of combinations of the modified code, which the structures of devices of encoding, decoding and account are offered on the basis of, are offered.

The methods of estimation of noise stability of devices are offered on the basis of the binomial numbers with duplication and decision-making on a leading channel or on ductings equivalent on meaningfulness. The questions of estimation of noise stability of majority structures were considered on the basis of the binomial numbers.

Key words: components of the digital systems, counter, noise stability of digital devices, binomial number system, modified binomial code, backuping.

Відповідальний випусковий Руденко О. Г.

Підписано до друку 07.10.2010 р. Формат 60х48/16. Папір ксероксний Обл. вид. арк. 0,9. Наклад 100 прим. Гарнітура Times New Roman Cyr. Умовн.-друк. арк. 1,1. Замовлення № 1197.

Вид-во СумДУ. Свідотство ДК №3062 від 17.12.2007.

40007, м. Суми, вул. Римського-Корсакова, 2.

Друкарня СумДУ. 40007, м. Суми, вул. Римського-Корсакова, 2.

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

...