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

ЗАСТАВНИЙ ОЛЕГ МИХАЙЛОВИЧ

УДК 681.325

МЕТОДИ ПОБУДОВИ СПЕЦПРОЦЕСОРІВ ТА АНАЛОГО-ЦИФРОВИХ

КОДЕРІВ В БАЗИСІ ГАЛУА

Спеціальність 05.13.05 – елементи та пристрої обчислювальної техніки та систем керування

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

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

Тернопіль – 2007

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

Робота виконана в Тернопільському національному економічному університеті

Міністерства освіти і науки України.

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

Николайчук Ярослав Миколайович,

Тернопільський національний економічний університет,

завідувач кафедри спеціалізованих комп’ютерних систем.

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

Черкаський Микола В’ячеславович,

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

професор кафедри електронних обчислювальних машин

кандидат технічних наук, доцент

Іщеряков Сергій Михайлович,

Івано-Франківський національний технічний університет

нафти і газу,

доцент кафедри комп’ютерних систем та мереж

Захист відбудеться “20” вересня 2007 р. о 1400 годині на засіданні

спеціалізованої вченої ради К 58.082.02 при Тернопільському національному економічному університеті за адресою: 46000, м. Тернопільвул. Львівська, 11,

(зал засідань вченої ради)

3 дисертацією можна ознайомитись у науково-технічній бібліотеці Тернопільського національного економічного університету за адресою:

46000, м. Тернопіль, вул. Львівська, 11.

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

Вчений секретар

спеціалізованої вченої ради,

к. т. н., доцент __________ Яцків В. В.

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

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

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

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

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

Зв’язок роботи з науковими програмами, планами, темами. Запропоновані методи побудови спецпроцесорів та аналого-цифрових кодерів (АЦК), а також їх використання в розподілених КС розроблялись в межах науково-дослідних робіт, що здійснюються на факультеті комп’ютерних інформаційних технологій Тернопільського національного економічного університету: - СКС–63–02”К” „Розробка теорії, методології побудови та технічних засобів спеціалізованих комп’ютерних систем”, державний реєстраційний номер 0102U005764 (2002-2006р.); “Методи, апаратні та програмні засоби для дослідження та моделювання нестаціонарних розподілених об’єктів на основі інтервальних даних” (номер державної реєстрації 0106U000529, 2006-2007р.). Вищеназвані роботи виконувались за безпосередньою участю автора.

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

У відповідності з поставленою метою дисертаційна робота включає розв’язання таких задач:

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

2) порівняльний аналіз характеристик кодових матриць різних ТЧБ та перспективи їх застосування для побудови спецпроцесорів;

3) дослідження характеристики низових рівнів зіркових архітектур розподілених КС оснащених асинхронними автономними сенсорами;

4) дослідження системних характеристик операційних пристроїв та спецпроцесорів в базисі Галуа;

5) розробка теоретичних основ формування та оброблення двовимірних шумоподібних кодових послідовностейШКП) та дослідження їх системних властивостей;

6) розробка операційних пристроїв багатоканального АЦП в базисі Галуа;

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

8) розробка спецпроцесорів та аналого-цифрових кодерів для низових широкосмугових мереж КС.

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

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

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

Наукова новизна одержаних результатів полягає в наступному:

1) запропоновано метод побудови конвеєрних спецпроцесорів на основі багатоканального АЦП в базисі Галуа та двовимірних ШКП, який забезпечує високий рівень паралелізму формування даних та їх одночасний захист від помилок та інтенсивних промислових завад;

2) отримав подальший розвиток метод формування даних на основі інтегрально-імпульсної технології (ІІТ) в базисі Галуа з застосуванням широкосмугових кодових послідовностей, що дозволило суттєво знизити вимоги до завадозахищеності каналів зв’язку низових рівнів КС;

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

4) вперше розроблені теоретичні засади методів цифрового формування та оброблення двовимірних широкосмугових кодових послідовностей (ДШКП), які характеризуються перевагами завадозахищеності по відношенню до одновимірних ШКП;

5) розроблений метод побудови спецпроцесора на основі конвеєрної архітектури, інтегрально-імпульсної технології та ДШКП, що дозволило суттєво розширити функціональні можливості автономних сенсорів та покращити їх системні характеристики;

6) вперше отримані нові моделі ДШКП, які в порівнянні з відомими одновимірними ШКП (коди Баркера, М-сигнали та ін.) забезпечують підвищення на 20-30% завадозахищеності та швидкості передавання даних в низових рівнях безпровідних КС.

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

1) розроблено структуру багатоканального АЦП скануючого типу в базисі Галуа, який в порівнянні з існуючими АЦП паралельного типу в кожному каналі містить 2k/2 замість 2k компараторів та забезпечує захист вихідних кодів від помилок в процесі зчитування даних;

2) розроблено архітектуру k розрядного паралельного суматора в базисі Галуа, швидкодія якого перевищує в 5-9 разів швидкодію паралельного суматора в базисі Радемахера в діапазоні розрядності процесорів 16-64;

3) розроблено функціональні схеми та принципові рішення аналого-цифрових кодерів в базисі Галуа з використанням інтегрально-імпульсної технології кодування даних та застосуванням ДШКП, які по відношенню до існуючих засобів характеризуються високими характеристиками завадостійкості та швидкості передавання даних;

4) на базі ПЛІС реалізовано компоненти спецпроцесорів, які побудовані на основі ТЧБ Галуа і характеризуються покращеними системними властивостями;

5) розроблений спецпроцесор в базисі Галуа, на основі БАЦП Галуа та ДШКП, що забезпечує високий рівень паралелізму цифрового перетворення даних, захист від помилок, який призначений для використання на низових рівнях комп’ютерних мереж з безпровідними каналами зв’язку в умовах інтенсивних промислових завад;

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

Теоретичні та практичні результати роботи використані та впровадженні при викладанні дисциплін "Проектування спеціалізованих комп’ютерних систем" та "Системи передавання даних" на кафедрі спеціалізованих комп’ютерних систем Тернопільського національного економічного університету, в науково дослідних роботах по темах: Тернопільського національного економічного університету: - СКС–63–02”К” „Розробка теорії, методології побудови та технічних засобів спеціалізованих комп’ютерних систем” державний реєстраційний номер 0102U005764, де запропоновані нові методи побудови спецпроцесорів на основі базису Галуа, по темі “Методи, апаратні та програмні засоби для дослідження та моделювання нестаціонарних розподілених об’єктів на основі інтервальних даних” номер державної реєстрації 0106U000529, де запропоновані програмно-апаратні засоби дистанційного екологічного моніторингу параметрів забруднення навколишнього середовища. ВАТ ТРЗ "Оріон" (м. Тернопіль) в рамках створення спецпроцесора дистанційного завадозахищеного обміну даними між рухомими та стаціонарними об’єктами залізничного транспорту.

Особистий внесок здобувача. Основні положення та результати дисертаційної роботи отримані автором особисто. У роботах опублікованих у співавторстві здобувачеві належить: в [1] принципи побудови автономного сенсора на основі запропонованого автором методу об’єднання ІІТ та ШКП, в [4] розробка теоретичних основ та дослідження характеристик двовимірних кодів з особливими кореляційними властивостями.

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

- 1-й міжнародній науково-практичній конференції „Автоматизація виробничих процесів” АВП – 2002, Хмельницький, 2002;

- 2-й міжнародній науково-практичній конференції „Мікропроцесорні пристрої та системи в автоматизації виробничих процесів” МППСАВП – 2003, Хмельницький, 2003;

- II міжнародній науково-практичній конференції International Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, IDAACS, Lviv, Ukraine, 2003

- 3-й міжнародній науково-практичній конференції „Мікропроцесорні пристрої та системи в автоматизації виробничих процесів” МППСАВП – 2004, Хмельницький, 2004;

- 8-й міжнародній конференції „The Experience of Designing and Application of CAD Systems in Microelectronics„ CADSM’2005, Lviv-Polyana, 2005;

- 4-й міжнародній науково-практичній конференції „Мікропроцесорні пристрої та системи в автоматизації виробничих процесів” МППСАВП – 2005, Хмельницький, 2005;

- 7-й міжнародній конференції “Modern problems of radio engineering, telecommunications and computer scienceTCSET 2006, Lviv-Slavsko, 2006, а також доповідалось та обговорювалось на наукових конференціях професорсько-викладацького складу та наукових семінарах кафедри спеціалізованих комп’ютерних систем Тернопільського національного економічного університету.

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

Структура дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, списку використаних джерел і 5 додатків. Загальний обсяг роботи становить 187 сторінок, з них 136 сторінок основного тексту, 74 рисунки та 24 таблиці. Список використаних джерел включає 151 найменування, додатки представлені на 22 сторінках.

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

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

У першому розділі проведено аналіз архітектур та області застосування спецпроцесорів, які використовуються в низових рівнях розподілених комп’ютерних систем (РКС), побудованих на різних інформаційних технологіях згідно класифікацій М. Фліна, Р. Хокні, Л. Шнайдера та Д. Скіллікорна. В результаті аналізу показано, що найбільш перспективними для побудови спецпроцесорів є конвеєрна архітектура. Виконаний аналіз функцій та структурних модулів широковживаних однокристальних спецпроцесорів фірм Micro-Devices типу RF2909 та RF3000, фірми Grand-Jansen типу GJRF400, Zilog типу Z87000 та Z87200, КД ЦІЗІТ НАН України типу ПАК та спецпроцесори фірм ABB та Crossbow, які використовують безпровідні автономні сенсори, що працюють в умовах інтенсивних промислових завад. Основним недоліком спецпроцесорів даного класу, що виготовляються зарубіжними фірмами є використання одновимірних шумоподібних кодових послідовностей та двійкової системи числення (базису Радемахера).

В результаті встановлено, що базовими компонентами досліджуваного класу спецпроцесорів є одноканальні та багатоканальні АЦП, DSP, енергонезалежна пам’ять та автономне джерело живлення, модулі формування та оброблення одновимірних широкосмугових кодових послідовностей. Відмічено, що відносно високі системні характеристики досягненні в спецпроцесорах (СП) вітчизняного виробництва типу ПАК, що використовується в КС ALFIYA, за рахунок використання рекурентних кодів базису Галуа, що забезпечує 20-30-ти кратне стиснення інформації вихідних потоків даних, і суттєво знижує вимоги до пропускної здатності каналів зв’язку низових рівнів КС. Вказаний основний недолік даного СП, в якому відсутні модулі формування широкосмугових шумоподібних кодових послідовностей, що обмежує його функціональні можливості та застосування на низових рівня безпровідних КС в умовах інтенсивних промислових завад.

Виконане порівняння характеристик кодових матриць різних ТЧБ та показано, що базис Галуа забезпечує максимальну упаковку кодових даних і мінімальну надлишковість представлення інформації.

Проведений аналіз характеристик емерджентності та продуктивності розподілених комп’ютерних систем оснащених периферійними СП та аналого-цифровими кодерами на основі оцінок:

, ,

де – число зв’язків; – число елементів в системі; Р – коефіцієнт продуктивності системи; Ki – кількість активних автономних сенсорів в і-й момент часу, H – загальна кількість автономних сенсорів системи, N – кількість відліків часу в дискретному просторі.

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

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

У другому розділі проведено аналіз системних характеристик різних типів АЦП, як компонентів СП. Системні характеристики АЦП розраховані на основі характеристичного функціонала запропонованого А.І. Кондалєвим:

SАЦП=F(m, V, k, M, H1, H2, S),

де m – число каналів; V – швидкодія; k – розрядність; M – буферна пам’ять; H1 – апаратна складність; H2 – алгоритмічна складність; S – функціональні та інтерфейсні характеристики.

Для оцінки системних характеристик різних типів АЦП використані принципи SH-моделі розробленої М. В. Черкаським, яка враховує часову, апаратну та структурну складність операційних пристроїв.

Оцінки системних характеристик проводилась для 16 типів відомих АЦП в базисі Радемахера та 3 типів АЦП в базисі Галуа. Розрахунок структурної складності проведений на основі адитивного критерію згідно виразу:

,

де вi – ваговий коефіцієнт який враховує апаратурну складність і-го компонента АЦП, що визначається методом експертної оцінки; Pij = 0, 1, 2, … - кількість даних компонентів в структурі j-го АЦП. Системні характеристики розраховані за допомогою виразу:

,

де i=1…19; – час затримки перетворення сигналу в і-му АЦП; – час перемикання базового мікроелектронного вентиля,4нс).

В результаті проведених розрахунків отримані наступні графіки структурної складності (рис.1 а) та системних характеристик (рис.1 б), на яких позначено наступні типи одноканальних АЦП: 1–Паралельний; 2–АЦП Монте-Карло базисі Радемахера; 3–Багатотактний послідовно-паралельний; 4–Конвеєрний; 5–Послідовно-паралельний багатоступінчатий; 6–АЦП порозрядного зрівноваження; 7–Розгортуючий; 8–Інтегруючий; 9–Сігма-дельта (слідкуючий); 10–Перетворювач напруга-частота з імпульсним виходом; 11–АЦП на основі ПНЧ, в базисі Радемахера; 12–Інтегрально-імпульсний АЦП з імпульсним вихідним кодом в базисі Крейга-Галуа; 13–АЦП розгортуючого типу в базисі Крестенсона; 14–АЦП розгортуючого типу в базисі Крейга; 15–АЦП розгортуючого типу в базисі Хаара; 16–АЦП розгортуючого типу в Унітарному базисі; 17–Паралельний в базисі Галуа з буферним регістром; 18–Скануючий в базисі Галуа; 29–Скануючий в базисі Галуа на імпульсних компараторах.

а) б)

Рис. . Гістограми структурної складності (а) та системних характеристик (б) АЦП

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

Аналіз існуючих розробок СП для низових рівнів КС показує, що вони містять багатоканальні АЦП (БАЦП) в якості базових модулів.

В роботі запропонована нова структура багатоканального АЦП в базисі Галуа (рис. ), з реалізацією захисного коду в процесі зчитування цифрових даних, що базується на рекурентних властивостях кодів Галуа.

Рис. . Структура БАЦП в базисі Галуа

В даному БАЦП використовуються пристрої вибірки і зберігання (ПВЗ); багатостабільний елемент (БС); суматори аналогових сигналів; блок прецизійних резисторів (БР) та блоки імпульсних компараторів число яких вдвічі менше (2k/2) в кожному каналі в порівнянні з БАЦП паралельного типу (2k). На рис. а показана відносна ефективність системних характеристик БАЦП в базисі Галуа в порівнянні з БАЦП паралельного типу (що має найвищі системні характеристики серед інших типів АЦП рис.2 б) в базисі Радемахера. З даного графіку видно, що БАЦП в базисі Галуа володіє кращими системними характеристиками в діапазоні розрядностей k=10-16 та при кількості каналів більше 4-х.

При необхідності використання гальванічної розв’язки між каналами АЦП доцільно використовувати АЦП з імпульсними виходами до класу яких належать: сігма-дельта АЦПрис.1 ), перетворювач напруга-частота (рис.1 ) та інтегрально-імпульсний АЦП з імпульсним вихідним кодом в базисі Галуарис.1 ). Графік відносних системних характеристик даних АЦП зображено на рис.  б.

а) б)

Рис. . Відносна ефективність системних характеристик БАЦП паралельного типу (а) та АЦП з імпульсним виходом (б) в залежності від розрядності та числа каналів

З графіку (рис.  б) видно, що інтегрально-імпульсний перетворювач в базисі Галуа має найвищі системні характеристики і на відміну від інших типів імпульсних АЦП дозволяє формувати біт орієнтовані потоки вихідних даних в кодах Галуа, які одночасно дозволяють визначити миттєві та інтегральні значення вхідного сигналу з захистом даних від помилок.

Проведений аналіз системних характеристик АЦП та БАЦП підтверджує ефективність та доцільність використання АЦП в базисі Галуа в якості компонента СП.

На основі побудованих таблиць істиності та систем логічних рівнянь виконаний синтез та мінімізація структур шифраторів та дешифраторів в базисі Галуа наступних типів: з десяткової системи числення в базис Галуа; з базису Галуа в базис Хаара десяткової системи числення, паралельного інкрементованого коду базису Радемахера в біт орієнтований код базису Галуа; конвертації паралельних кодів базису Радемахера в паралельні коди базису Галуа, послідовного коду Галуа в код базису Хаара. Аналіз систем логічних рівнянь для різної розрядності дешифраторів паралельних кодів базису Радемахера в паралельні коди базису Галуа показав, що при їх реалізації досягається значне зменшення структурної складності по відношенню до канонічної форми (40-60%), що при сучасному рівні розвитку мікроелектроніки та застосуванню ПЛМ даний тип дешифратора може бути ефективно реалізований в 16 та 32 розрядних процесорах.

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

,

де bk, bk-1, …, b1, біти коду Галуа першого з доданків; di,k, di,k-1, …, di,1 – коефіцієнти кодової матриці, які відповідають кодовій матриці другого доданку, що визначена згідно ключа коду Галуа для відповідної розрядності.

Вперше розроблені структурні схеми паралельних суматорів Галуа з використанням багаторозрядного (рис.  а) та однорозрядного (рис.  б) дешифраторів коефіцієнтів dij.

а) б) в)

Рис. 4. Структурні схеми паралельних суматорів Галуа: а) 4-х розрядного з багаторозрядним дешифратором; б) k – розрядного з однорозрядного дешифратором; в) структура одного розряду 4-х бітного суматора

Швидкодія суматорів в залежності від розрядності k в базисах Радемахера та Галуа розраховується за наступними аналітичними виразами:

, ,

де k – розрядність суматора; – час спрацювання логічного елемента.

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

Рис. . Графік відносної швидкодії суматора Галуа в порівнянні з суматором в базисі Радемахера

Важливим компонентом досліджуваного типу СП є кодові лічильники та генератори ШПК. З метою вибору даного компонента СП з найкращими характеристиками мінімальної структурної складності та максимальної швидкодії проведений аналіз архітектур та системних характеристик лічильників в різних ТЧБ: асинхронний та синхронний сумуючі та реверсивний двійкові лічильники в базисі Радемахера; лічильник Джонсона в базисі Крейга; багаторозрядний лічильник в базисі Крестенсона; повнорозрядний сумуючий та реверсивний лічильники в базисі Галуа; рекурсивний лічильник базису Галуа в якості генератора одновимірного ШКП з періодом 2k-1. Отримані аналітичні вирази швидкодії та структурної складності досліджуваних структур лічильників в базисах: Крейга; Радемахера; Крестенсона та Галуа, які представлені в табл.1.

Табл. – Характеристики швидкодії лічильників в різних ТЧБ

Рис. . Відносна системна ефективність лічильників в різних ТЧБ

Проведений аналіз системних характеристик лічильників в різних ТЧБ показує, що найкращі характеристики мають лічильники Джонсона в базисі Крейга, які реалізуються у вигляді регістрів зсуву на синхронних D-тригерах без додаткових елементів у зворотних зв’язках. В той же час, лічильники даного типу характеризуються кодовою надлишковістю, яка обумовлена використанням базису Крейга. Наступні високі системні характеристики мають лічильники в базисі Галуа, які реалізуються на основі аналогічної структури на синхронних D-тригерах і мають не менше одного логічного елемента "виключаюче АБО" у зворотному зв’язку. Перевагою лічильників у базисі Галуа є відсутність кодової надлишковості, а також унікальні можливості одночасного формування як паралельних так і біт орієнтованих кодів Галуа з захистом від помилок на основі рекурентних властивостей ТЧБ Галуа. Даний тип лічильників особливо ефективно можна використовувати в якості компонента досліджуваного класу СП.

Розроблені структури k-розрядного повнокодового лічильника Галуа та лічильника генератора одновимірних маніпульованих ШПК (М-послідовностей) приведені на рис. .

а)

б)

Рис. . Структури лічильників в базисі Галуа: а) повнокодового з періодом 2k; б) маніпульованих ШПК з періодом 2k-1

Робота лічильників Галуа даних типів базується на основі аналітичних виразів:

а) б)

В роботі приведена таблиця неприводимих поліномів, що визначають ключі кодів поля Галуа та відповідні номери тригерів у діапазоні k=4-32, виходи яких під’єднуються до логічних елементів зворотних зв’язків.

У третьому розділі проведено теоретичне обґрунтування моделювання та дослідження запропонованих двовимірних ШПК, що застосовуються в якості базових вихідних сигналів СП для низових рівнів безпровідних РКС. Викладені теоретичні основи кореляційних характеристик одновимірних кодових послідовностей, які характеризуються особливими кореляційними властивостями, що дозволяють приймати їх на фоні завад, потужність яких може перевищувати в багато разів потужність інформаційних сигналів. Показано, що в існуючих FHSS, DSSS системах, в якості шумоподібних сигналів використовуються одновимірні кодові послідовності: Баркера; Хафмена; Цірлера; Пелі-Плоткіна; Френка; ГалуаМ-сигнали); Голда, Касамі, Голея, коди побудовані на основі функцій Уолша, модифіковані дворівневі М-сигнали та багаторівневі ШПК.

Найбільшого поширення та популярності набули коди Баркера, які при невеликій довжині володіють хорошими кореляційними властивостями (практично найкращими серед всіх інших відомих ШПК) та дозволяють максимально ефективно використати канал зв’язку. Дані сигнали представляються двійковими компонентами в яких максимальний рівень бокових пелюсток не перевищує 1/n від основного піку, де n – кількість розрядів кодової послідовності. Незважаючи на хороші кореляційні властивості коди Баркера мають суттєвий недолік, а саме обмежене число та малу довжину кодової послідовності (n?13).

Сигнали з компонентами із символів Лежандра являють собою клас сигналів з трійковими компонентами Sj=[l;0;-l]. Кількість компонентів визначається із наступного виразу n=(pn -1)/(p-1), де р – просте число, n – ціле число.

Циклічні автокореляційні функції даних кодів мають бокові компоненти, що рівні нулю. Функції невизначеності при великих значеннях n мають бокові компоненти порядку n(1/2), а при невеликих значеннях n мають бокові пелюстки значно менші за n(1/2). Сигнали кодів Баркера з непарною кількістю компонентів входять в клас цих кодів. Розвиток теорії кодів Баркера науковою школою проф. Я.М. Николайчука дозволив виявити систему модифікованих кодів Баркера, які мають кореляційні функції з боковими пелюстками -1, -2 та 1, 2, але за рахунок більшої довжини n=14-33 забезпечують краще співвідношення сигнал/шум. Сигнали на основі багаторівневих ШПК, які характеризуються наявністю багатьох кореляційних піків мають вищі ентропійні властивості і дозволяють в значній мірі покращити співвідношення сигнал/шум при їх взаємокореляційному прийманні, але характеризуються більшою апаратною складністю засобів їх обробки. На основі оцінки S=100%Li/L0, де Li і L0 відповідно максимальний боковий та основний кореляційні піки, розраховані характеристики відомих дворівневих ШПС (рис. ).

Рис. – Залежність максимуму бокової пелюстки для кодів Баркера та інших ШПС

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

,

де ,- відповідно кількість нульових та кількість одиничних елементів в кодовій послідовності ШПС.

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

Рис. . Області існування відомих одновимірних та знайдених двовимірних ШПК з найкращими кореляційними властивостями та кодові матриці ШПК n?n.

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

; ;

; ,

де xij, yij – відповідно елементи інформаційного та еталонного двовимірних кодів Баркера.

Кореляційні характеристики n?n двовимірних ШПК розраховані на основі виразів (1) для n=2,4,5 показані на рис. .

а) б)

в) г)

Рис. . Кореляційні характеристики двовимірних ШПК

На основі визначеної області існування двомірних ШПК та аналітичних виразів (1) шляхом комп’ютерного моделювання знайдені двовимірні кодові послідовності з особливими кореляційними властивостями, які характеризуються покращеними на 20-30% характеристиками відношення висоти основного піку до максимального піку бокової пелюстки (рис. , рис. ) в порівнянні з відомими ШПС.

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

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

У четвертому розділі на основі проведених теоретичних, схемотехнічних та експериментальних досліджень виконаних в другому та третьому розділах розроблені структури конвеєрних СП у складі автономних сенсорів, які реалізують 2 запропонованих методи їх побудови: на основі багатоканального БАЦП в базисі Галуа в якості АЦК та модуля формування вихідних двовимірних ШПК (рис.  а) та на основі одноканального інтегрально-імпульсного АЦП в базисі Галуа та модуля формування двовимірних ШПК (рис.  б).

На мові VHDL описано структурні схеми запропонованих рішень компонентів СП в базисі Галуа та синтезовано та ПЛІС фірми Altera:

1) дешифратор паралельних кодів базису Радемахера в базис Галуа;

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

3) повнокодовий лічильник в базисі Галуа з періодом 2k;

4) лічильник-генератор маніпульованих М-сигналів з періодом 2k-1.

а) б)

Рис. . Структури СП з використанням: а) АЦК на основі БАЦП Галуа; б) АЦК на основі інтегрально-імпульсного АЦП Галуа та вихідних модулів формування двовимірних ШПК

Розроблена принципова схема та виготовлений дослідний взірець автономного сенсора оснащеного СП на основі інтегрально-імпульсного АЦП в базисі Галуа та формувача вихідних двовимірних ШПК.

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

В додатках подані документи, що підтверджують впровадження результатів наукових досліджень по темі дисертації, приведено програму пошуку та моделювання характеристик двовимірних ШПК та VHDL опис компонентів СП.

ВИСНОВКИ ТА ОСНОВНІ РЕЗУЛЬТАТИ РОБОТИ

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

1) в результаті аналізу архітектур та області застосування спецпроцесорів, які використовуються в низових рівнях розподілених комп’ютерних систем, встановлено, що найбільш ефективно даний клас спецпроцесорів реалізується на основі конвеєрної архітектури, а їх базовими компонентами є одноканальні та багатоканальні АЦП, DSP, енергонезалежна пам’ять та автономне джерело живлення, модулі формування та оброблення одновимірних широкосмугових кодових послідовностей. Обґрунтована ефективність застосування для побудови спецпроцесорів, крім широковживаного базису Радемахера, який породжує двійкову систему числення, інших теоретико-числових базисів, зокрема: унітарного, Хаара, Крейга, Крестенсона, Галуа. Виконане порівняння характеристик кодових матриць різних ТЧБ показано, що базис Галуа забезпечує максимальну упаковку кодових даних і мінімальну надлишковість представлення інформації;

2) запропоновано метод побудови конвеєрних спецпроцесорів на основі багатоканального АЦП в базисі Галуа та двовимірних ШКП, який забезпечує високий рівень паралелізму формування даних та їх одночасний захист від помилок та інтенсивних промислових завад;

3) отримав подальший розвиток метод формування даних на основі інтегрально-імпульсної технології (ІІТ) в базисі Галуа з застосуванням широкосмугових кодових послідовностей, що дозволило суттєво знизити вимоги до завадозахищеності каналів зв’язку низових рівнів КС;

4) розроблено метод, алгоритм операції сумування в базисі Галуа та архітектура k - розрядного паралельного суматора, швидкодія якого перевищує в 5-9 разів швидкодію паралельного суматора в базисі Радемахера в діапазоні розрядності процесорів 16-64, за рахунок виключення міжрозрядних переносів;

5) вперше розроблені теоретичні засади методів цифрового формування та оброблення двовимірних широкосмугових кодових послідовностей (ДШКП), які характеризуються перевагами завадозахищеності по відношенню до одновимірних ШКП;

6) розроблено метод побудови спецпроцесора на основі конвеєрної архітектури, інтегрально-імпульсної технології та ДШКП, що дозволило суттєво розширити функціональні можливості автономних сенсорів та покращити їх системні характеристики;

7) вперше отримані нові моделі ДШКП, які в порівнянні з відомими одновимірними ШКП (коди Баркера, М-сигнали та ін.) забезпечують підвищення на 20-30% завадозахищеності та швидкості передавання даних в низових рівнях безпровідних КС;

8) розроблено функціональні схеми та принципові рішення аналого-цифрових кодерів в базисі Галуа з використанням інтегрально-імпульсної технології кодування даних та застосуванням ДШКП, які по відношенню до існуючих засобів характеризуються покращеними системними характеристиками завадостійкості та швидкості передавання даних;

9) на базі ПЛІС реалізовано компоненти спецпроцесорів, які побудовані на основі ТЧБ Галуа і характеризуються покращеними системними властивостями;

10) розроблено спецпроцесор в базисі Галуа на основі БАЦП Галуа та ДШКП, що забезпечує високий рівень паралелізму цифрового перетворення даних, захист від помилок, який призначений для використання на низових рівнях комп’ютерних мереж з безпровідними каналами зв’язку в умовах інтенсивних промислових завад;

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

СПИСОК ПУБЛІКАЦІЙ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Николайчук Я.М., Заставний О.М. Методологія побудови автономних сенсорів для розподілених комп’ютерних мереж // Вісник Технологічного університету Поділля, -Хмельницький. -2002, - №3, -Т2 - С. 142-146.

2. Заставний О.М. Системні параметри автономних сенсорів з глибоким розпаралеленням інформаційних потоків // Вісник Технологічного університету Поділля, -Хмельницький, -2003, -№3, -Т1, -С. 128 – 131.

3. Заставний О.М. Дослідження теоретико–числових базисів як основи побудови двомірних шумоподібних сигналів // Вісник “Радіоелектроніка та телекомунікації” Національного університету ”Львівська політехніка”, Львів, 2004, №508, С. 33 – 37.

4. Николайчук Я.М., Заставний О.М. Дослідження системних характеристик двомірних кодів з особливими кореляційними властивостями // Вісник Технологічного університету Поділля, -Хмельницький, -2004,- №2, -Ч.1, Т2, -С. 107 – 110.

5. Заставний О.М. Аналіз системних характеристик спецпроцесорів формування вихідних даних аналого-цифрових кодерів // Вісник Хмельницького національного університету, -Хмельницький, -2005, -Ч.1, Т2, -С. 223-226.

6. Заставний О.М. Синтез та проектування аналого-цифрового кодера автономного сенсора з вихідними двомірними шумоподібними сигналами // Збірник наукових праць інституту проблем моделювання в енергетиці ім. Г.Є. Пухова.- Київ, -2006, – С.34 – 42.

7. O Y. Nykolaychuk, N. Krutskevych O. Zastavniy, T. Grinchyshyn, Perspective Architecture and Components of Computer Networks // Proc. Of the Second IEEE International Workshop on Intelligent Data Acquisition and Advanced Computing Systems: Technology and Applications, IDAACS, Lviv, Ukraine, 2003.

8. Zastavniy Analog-digital Coders in Galois Base // Proc. of the International Conf. CADSM 2005. - Lviv-Slavsko (Ukraine). – 2005, - P. 248

9. Заставний О.М. Методи підвищення регулярності архітектур багатоканальних аналого-цифрових кодерів//Proc. of the III International conference on optoelectronic information technologies “PHOTONICS-ODS 2005 ” Vinnytsia, VNTU, 2005.

10. Y.Nykolaychuk, N. Krutskevych Zastavniy O.М, .Architecture and System Characteristic of Distributed Computer Network with Autonomous Sensor Equipment// Proc. of the International Conf. TCSET 2006, – Lviv-Slavsko (Ukraine). – 2006. – P. 394 – 398.

АНОТАЦІЯ

Заставний О. М. Методи побудови спецпроцесорів та аналого-цифрових кодерів в базисі Галуа. – Рукопис.

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

Проведено аналіз архітектур та області застосування спецпроцесорів, які використовуються в низових рівнях розподілених комп’ютерних систем. Обґрунтована ефективність застосування для побудови спецпроцесорів, крім широковживаного базису Радемахера, який породжує двійкову систему числення, теоретико-числового базису Галуа. Запропоновано методи побудови конвеєрних спецпроцесорів на основі багатоканального АЦП, інтегрально-імпульсної технології в базисі Галуа та двовимірних шумоподібних кодових послідовностей. Розроблений метод, алгоритм операції сумування в базисі Галуа та архітектура паралельного суматора, швидкодія якого перевищує в 5-9 разів швидкодію паралельного суматора в базисі Радемахера.

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

Розроблено функціональні схеми та принципові рішення компонентів спецпроцесорів в базисі Галуа.

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

АННОТАЦИЯ

Заставный О. М. Методы построения спецпроцессоров и аналого-цифровых кодеров в базисе Галуа. – Рукопись.

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

Проведен анализ различных архитектур спецпроцессоров предназначенных для работы на низовых уровнях беспроводных распределённых компьютерных систем.

Обоснована эффективность применения для построения спецпроцессоров вместо базиса Радемахера, который порождает двоичную систему исчисления, других теоретико-числовых базисов: унитарного, Хаара, Крейга, Крестенсона, Галуа. Выполненное сравнение характеристик кодовых матриц различных теоретико-числовых базисов в результате которого показано что базис Галуа обеспечивает максимальную упаковку кодовых данных и минимальную излишность представления информации. Предложено методы построения конвейерных спецпроцессоров на базе многоканального АЦП, интегрально-импульсной технологии в базисе Галуа и двумерных шумоподобных кодовых последовательностей. Разработан метод, алгоритм операции суммирования в базисе Галуа и архитектура параллельного сумматора, быстродействие которого превышает в 5-9 раз быстродействие параллельного сумматора в базисе Радемахера за счет исключения сквозных междуразрядных переносов.

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

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

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

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

ABSTRACT

Zastavnyy O. M. Methods of constructions of the special processors and analog-digital coders in the Galois base. - Manuscript.

The thesis for a Ph.D. (candidate of science) degree on specialty 05.13.05 - Elements and Devices of Computing Engineering and Control Systems, Ternopil National Economic University, Ternopil, 2007.

The analysis of architectures and application of the special processors which are used in the low levels of the distributed computer systems domains is conducted. The efficiency of application of the construction of special processors, except for the wide use of Rademakher's basis, which generates the binary scale of notation, number-theoretical basis of Galois is being based. The methods of construction of the pipelining special processors are offered on the basis of multichannel ADC, integral-impulsive technology in the basis of Galois and two-dimensional spread spectrum sequences of codes. A method, an algorithm of operation of summing in the base of Galois and the architecture of parallel adder the fast-acting of which exceeds in 5-9 times the fast-acting of parallel adder in the basis of Rademakher are developed.

Theoretical principles of methods of the digital forming and treatment of two-dimensional spread spectrum sequences of codes, which are characterized advantages of noise immunity in relation to one-dimensional, are developed.

Functional diagrams and of principles decisions of components of the special processors are developed