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

ОДЕСЬКИЙ ДЕРЖАВНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

АВТОРЕФЕРАТ

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

МЕТОДИ ФУНКЦІОНАЛЬНО-ЛОГІЧНОГО ПРОЕКТУВАННЯ ШВИДКОДІЮЧИХ АРИФМЕТИЧНИХ ПРИСТРОЇВ НА ОСНОВІ СИМЕТРИЧНИХ БУЛЕВИХ ФУНКЦІЙ

ЛЯХОВЕЦЬКИЙ ОЛЕКСАНДР МИХАЙЛОВИЧ

УДК 681.325.5

05.13.05 “Елементи та пристрої

обчислювальної техніки та систем керування”

Одеса - 1999

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

Робота виконана на кафедрі “Системне програмне забезпечення”

Одеського державного політехнічного університету міністерства освіти України.

Науковий керівник

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

Паулін Олег Миколайович, Одеський державний політехнічний університет, доцент кафедри

“Системне програмне забезпечення”

Офіційні опоненти:

доктор технічних наук, професор Ящук Леонід Омелянович, Одеська державна академія зв'язку, завідувач кафедрою мереж і систем поштового зв'язку

кандидат технічних наук, доцент Мещеряков Володимир Іванович, Одеська державна академія холоду, завідувач кафедрою САПР

Провідна установа

Інститут проблем математичних машин та систем НАН України, м. Київ

Захист відбудеться 23. 09. 1999 року о 13 годині 30 хвилин на засіданні спеціалізованої вченої ради Д 41.052.01 Одеського державного політехнічного університету за адресою: 270044, м. Одеса, проспект Шевченка, 1.

З дисертацією можна ознайомитись в бібліотеці Одеського державного політехнічного університету за адресою: 270044, м. Одеса, пр. Шевченко, 1.

Автореферат розісланий 20.08.1999 р.

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

спеціалізованої вченої ради Ямпольский Ю.С.

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

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

алгебра арифметичний функція

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

Сучасні засоби побудови обчислювальних пристроїв орієнтуються на спеціалізацію як самих пристроїв, так і методів їх проектування. При цьому засобом підвищення продуктивності обчислювальних пристроїв є використання спеціалізованих апаратно реалізованих обчислювачів. Наприклад, навіть у сучасних процесорах загального призначення запроваджуються раніше властиві лише для супер-ЕОМ спеціальні команди для виконання операцій над матрицями і масивами чисел, що реалізуються спеціалізованими АП. Таким чином, спостерігається тенденція відмови від універсальних апаратних обчислювачів на користь спеціалізованих.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дослідні роботи, зокрема, розробка пакета прикладних програм для автоматизації проектування арифметичних пристроїв, зв'язані з темою планової науково-дослідної роботи кафедри системного програмного забезпечення ОДПУ № 329-73 “Програмні засоби автоматизованих систем. Розробка та дослідження методів та засобів автоматизованих систем”.

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

Для досягнення поставленої мети вирішуються такі задачі:

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

2. Розвиток і адаптація алгебри симетричних функцій (СФ) і частково симетричних булевих функцій (ЧСФ) для проектування АП.

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

4. Розроблення методу опису структури АП у базису СФ і ЧСФ та процедур, придатних для автоматизованого синтезу структури АП на основі цього методу.

5. Розроблення пакету підпрограм функціонально-логічного проектування АП, що включає в себе:

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

програму розрахунку розрядних індексів для проектування суматорів із довільною кількістю доданків у розрядах.

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

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

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

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

3. Вперше запропоновано узагальнену структуру і метод проектування схеми визначення знака результату підсумовування N чисел у додатковому коді для довільного N, що забезпечують збільшення швидкодії в 1,3 рази і більш та зменшення складності схеми в 1,4 рази і більш.

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

Розроблений в дисертаційній роботі пакет прикладних програм для функціонально-логічного проектування спеціалізованих багатооперандних суматорів із довільною кількістю доданків у розрядах прийнято до використання у виробничо-комерційній фірмі "ТЕЛЕКАРТ" і застосовується при проектуванні блоку кодування пристрою ініціалізації та запису телефонних чіп-карт "ТЕЛЕКАРТ-5СК" для швидкодіючої апаратної реалізації криптографічного алгоритму.

Наукові результати роботи впроваджені в навчальний процес ОДПУ на кафедрах "Системне програмне забезпечення" і "Комп'ютерні та інтелектуальні системи та мережі". Метод представлення і мінімізації частково-симетричних булевих функцій і метод довизначення неповністю заданої булевої функції до симетричної викладаються в темі "Булева алгебра" дисципліни "Дискретна математика" для студентів спеціальності 7.080403. Методи проектування багатооперандних багаторозрядних суматорів, схеми прискореного переносу для таких суматорів і схеми визначення знака результату підсумовування кількох чисел викладаються в темі "Арифметичні пристрої ЕОМ" дисципліни "Комп'ютерна електроніка" для студентів спеціальності 7.091501.

Особистий внесок здобувача полягає в:

1. Аналізу методів побудови та структур швидкодіючих помножувачів [1].

2. Узагальненні алгебри частково-симетричних булевих функцій на випадок кількох комплектів симетричних аргументів [9].

3. Розробленні методу та алгоритму довизначення неповністю визначеної довільної булевої функції до симетричної функції [5].

4. Розвитку методу проектування суматорів із довільною кількістю доданків у розрядах [8] і розробленні методу проектування схем прискореного переносу [4] в термінах алгебри СФ, а також створенні алгоритму і модулів програми автоматичної генерації розрядних індексів для проектування таких суматорів [3].

5. Створенні програми виявлення симетричної частини в довільній функції [3].

6. Розробленні узагальненої структури і методу проектування схеми визначення знаку результату підсумовування N чисел у додатковому коді [2].

7. Розробленні таблично-алгоритмічного помножувача на основі триоперандного суматора [6] та розвитку швидкодіючого таблично-алгоритмічного методу множення на базі багатооперандних обчислювальних структур [7].

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

Апробація результатів дисертації. Результати роботи докладалися та обговорювались на щорічних наукових конференціях студентів і молодих дослідників (1996-1998 р.) та на міжнародній науково-технічній конференції "Приладобудування-98" у м. Євпаторія.

Публікації. За темою дисертаційної роботи опубліковано 9 наукових робіт, серед них патент України, подані 2 заяви на одержання патенту в Держпатент України і отримані пріоритетні довідки та опубліковані рішення щодо прийняття заяв до розгляду (Бюлетень “Промислова власність”, 1998, № 3/1. С. 333-334).

Структура та обсяг дисертації. Дисертаційна робота складається з вступу, чотирьох розділів, висновків, додатків. Робота викладена на 209 сторінках, містить 31 рисунок на 17 сторінках, 55 таблиць на 13 сторінках і 4 додатки, що займають 34 сторінки. Список використаних джерел займає 7 сторінок і складається з 80 найменувань.

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

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

Симетричними аргументами (СА) називаються такі аргументи xi і xj булевої функції y=f(xn--1, ..., x1, x0), перестановка котрих місцями не змінює значення функції y на всіх наборах значень аргументів xn--1, ..., x1, x0. Симетричність аргументів xi і xj позначається xi~xj і називається прямою симетрією. Коли xi~ , то цей вид симетрії позначається xi xj і називається змішаною симетрією. Якщо і xi~xj, і xixj, то говорять про поліморфну симетрію і пишуть xixj. Запис xixj означає, що xi і xj являються СА: xi ~xj, xi xj або xi xj.

Симетричною функцією (СФ) називається булева функція y=f(xn--1,..., x1, x0), усі аргументи xi (i=0, ..., n-1) якої являються СА. Число a називається індексом СФ f, якщо f дорівнює одиниці на будь-якому наборі, що має a одиниць. Всяка СФ цілком визначається набором своїх індексів. СФ від n аргументів з індексами a1, a2,..., ak позначають, або Sn(a1, a2, ... , ak). Довільна СФ y=f(xn--1, ..., x1, x0) однозначно представляється характеристичним (n+1)-розрядним двійковим кодом (f)=(0, 1,..., n), де s значення f на будь-якому наборі значень аргументів xn--1, ..., x1, x0, що містить рівно s одиниць (0 s n). Таким чином, СФ визначається локальним кодом, довжина котрого лінійно залежить від n. Кількість нетривіальних СФ дорівнює 2n-1. СФ з одним індексом називається елементарною СФ (ЕСФ).

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

Поряд із симетричними функціями, існує клас частково симетричних булевих функцій (ЧСФ), у яких тільки частина аргументів m (2 m n-2) є СА. Для ЧСФ важливим є поняття симетричного комплекту аргументів (СК). Множина аргументів X ={xi1, xi2, ... , xim} утворює СК, якщо xik , xij : xikxij (1 k, j m ). СК бувають прості і поліморфні. У простих СК аргументи зв'язані тільки відношеннями прямої і змішаної симетрії. Простий СК задається набором k аргументів і k-розрядним вектором поляризації, що задає інверсовані аргументи. У поліморфних СК аргументи зв'язані тільки відношенням поліморфної симетрії. Поліморфний СК задається набором m аргументів без урахування їх інверсій.

ЧСФ у загальному випадку складається з кількох СК, що не перетинаються. ЧСФ із числом СК більш одного і без несиметричних аргументів (НСА) зветься квазісиметричною функцією (КСФ). КСФ грають важливу роль при описі багаторозрядних багатооперандних суматорів.

Найбільш потужні методи виявлення симетрії засновані на властивості транзитивності СА і на розкладанні Шенона функції y=f(xn-1,..., x1, x0).

Ефективним засобом аналізу залишкових функцій являються декомпозиційні карти. Декомпозиційна карта (ДК) Dij(y) функції y=f(X) по аргументах xi і xj це таблиця з 4 рядками та 2n-2 стовпчиками. У таблицю записуються десяткові еквіваленти наборів значень n аргументів, при цьому рядкові 0 відповідають набори, у котрих xi=0 і xj=0, тобто залишкова функція R0(X), рядкові 1 xi=0 і xj=1 і R1 (X), рядкові 2 xi=1 і xj=0 і R2 (X), рядкові 3 xi=1 і xj=1 і R3(X). Визначення рівності залишкових функцій зводиться до поелементного порівняння рядків ДК.

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

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

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

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

В результаті критичного аналізу виявлені такі недоліки існуючих традиційних методів проектування АП: 1) існують ефективні методи проектування тільки бінарних АП, а багатооперандні структури, зокрема помножувачі, будуються на основі бінарних структур; 2) задача проектування швидкодіючих N-розрядних багатооперандних суматорів має розмірність 2MN, де M кількість операндів, що обмежує можливість її вирішення традиційними методами булевої алгебри при великих M, N; 3) не існують схеми прискореного переносу для багатооперандних суматорів.

Виявлено такі недоліки існуючих методів проектування АП на базі СФ: 1) існуючі методи дозволяють проектувати АП лише в обмеженому базисі СФ, зокрема, порогових функцій; 2) існуючий математичний апарат СФ і ЧСФ дозволяє використовувати лише один комплект симетричних аргументів, що дає можливість проектувати багатооперандні структури лише з ланцюгом поширення міжрозрядного внутрішнього переносу; 3) відомі засоби побудови і структури багатооперандних суматорів обмежуються дворозрядними структурами; 4) не існують методи довизначення неповністю заданої булевої функції до СФ, що не дозволяє використувати для таких функцій математичний апарат СФ і ЧСФ.

На підставі проведеного аналізу поставлено такі задачі: 1) доробити алгебру ЧСФ для представлення і мінімізації ЧСФ із множиною незалежних комплектів симетричних аргументів; 2) розробити метод довизначення неповністю заданої булевої функції до СФ або ЧСФ; 3) розробити метод проектування багатооперандного багаторозрядного суматора із довільною кількістю доданків у розрядах і схеми прискорених переносів для нього; 4) вивчити закономірності обчислення розрядів переповнення і значення знакового розряду при підсумовуванні N операндів і розробити метод проектування схеми визначення знаку результату підсумовування N знакових операндів; 5) розробити метод проектування помножувача на основі багатооперандних обчислювальних структур і алгебри СФ; 6) розробити пакет підпрограм функціонально-логічного проектування АП, зокрема: а) програму виявлення симетричної частини в довільній булевій функції; б) програму розрахунку розрядних індексів для проектування суматорів із довільною кількістю доданків у розрядах.

В другому розділі теорія СФ розвивається та узагальнюється з метою адаптації до вирішення задачі проектування деяких класів АП. Поняття часткової симетрії узагальнюється на випадок декількох СК, що розширює клас СФ. Запропоновано засоби представлення і мінімізації ЧСФ, що складають основу методів синтезу схем на основі ЧСФ. Розроблено метод довизначення неповністю заданої функції до СФ, що розширює галузь застосування математичного апарату СФ і ЧСФ для синтезу схем, які описуються такими функціями.

Представлення ЧСФ засноване на використанні таблиці наборів груп (ТНГ) і на властивостях частково симетричних наборів (ЧСН). Розглянемо процедуру одержання ТНГ. Після визначення симетричних аргументів (СА) перегрупуємо змінні в таблиці, щоб розділити симетричну (СЧ) і несиметричну частину (НСЧ), і згрупуємо наявні сукупності СА. Потім заміняємо отримані сукупності СА групами і визначаємо значення груп. При цьому таблиця істинності перетворюється в ТНГ, якій властиві звичайні двійкові змінні і їхні значення. Якщо ЧСФ має кілька СК, то змінні, що складають кожний СК, є аргументами відповідної групи.

Мінімізація ЧСФ заснована на розкладанні ЧСФ на СЧ і НСЧ і операціях групового і бінарного склеєння. Розглядаються два способи представлення ЧСФ.

1. Бінарно-групова мінімізація. Спочатку здійснюється бінарне склеєння в ТНГ скрізь, де це можливо, а потім групове склеєння. Розглядаючи НСЧ окремо від СЧ кожного елемента ТНГ, проводимо всілякі склеєння НСА класичними методами. Після цього проводимо групове склеєння між тими елементами таблиці, у яких НСЧ рівні.

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

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

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

У третьому розділі розглядаються питання проектування багатооперандних структур швидкодіючих суматорів та їх застосування в матричних помножувачах. Отримано методику проектування каскаду багатооперандного суматора з довільною кількістю доданків у розрядах, що заснована на моделі з вертикальною обробкою інформації та на ітераційному обчислювальному алгоритмі, який моделює поширення переносу уздовж розрядної сітки. Отримані за допомогою описаної методики суматори відрізняються від традиційних суматорів із паралельним переносом відсутністю ланцюга внутрішнього переносу. За рахунок використання непозиційного переносу з бітами однакової ваги і розробленого в даній роботі математичного апарату представлення і мінімізації ЧСФ ця методика дозволила отримати чотирибітний каскад триоперандного суматора, що збільшує швидкодію в 1,3 рази в порівнянні з традиційним засобом підсумовування трьох операндів, хоча і має на 30% більшу приведену складність. Через те, що ітераційний алгоритм легко реалізується на ЕОМ, методика застосовується для автоматизації проектування швидкодіючих суматорів із можливістю варіювання характеристиками складності та швидкодії.

З метою підвищення швидкодії багаторозрядних багатооперандних суматорів, які складаються з декількох каскадів (можливо, різнотипних), розроблено метод проектування схеми прискореного переносу, яка генерує вхідні переноси кожного каскаду. Ця методика заснована на модифікації ітераційного алгоритму і дозволяє одержати схеми, що забезпечують збільшення швидкодії в 1,5-2 рази при збільшенні складності пристрою на 5-13% у порівнянні з послідовним з'єднанням каскадів.

Розроблено матричний таблично-алгоритмічний помножувач, у якому тетради часткових добутків підсумовуються триоперандним суматором. Використання багатооперандних структур на основі СФ дозволяє збільшити швидкодію на 30%.

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

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

Багаторядний код із змінним числом доданків у розрядах позначимо MN MN-1 ... M2M1, де Mi кількість доданків в i-му розрядному зрізі. Конкретний набір значень доданків при поразрядному представленні позначаємо N-розрядним кодом AN=aN aN-1... a2 a1. Кожний такий набір представляє множину наборів доданків із числом одиниць в i-му розрядному зрізі ai, що відрізняються лише порядком розташування одиниць у кожному розрядному зрізі. Таким чином, використання індексів, рівних кількості одиниць у кожному розрядному зрізі, дозволяє значно скоротити обсяг вихідних даних для опису функціонування суматора і надалі спростити його проектування.

Нехай S=РkРk-1...Р1 SN... .S2S1 результат підсумовування, наданий у двійковій системі числення, S = CвихSN... S2S1 результат підсумовування з вихідним переносом із бітами однакової ваги, де SN.…S2S1 біти суми S, РkРk-1...Р1 біти переносу. Вихідні функції АП задаються КСФ.

Кожному значенню ПВД Q відповідає множина наборів AN=aN aN-1 ... a2 a1. Кожний набір AN відповідає конкретному значенню набору груп G1, G2, ...GN і може бути поданий у вигляді кон'юнкції ЕСФ, що відповідають індексам набору AN = aN, aN-1...a2a1. Таким чином, кожна з вихідних КСФ Si і Cвых j представляється диз'юнкцією наборів значень груп G1, G2, ...GN , що відповідають тим AN і ПВД Q, які задовольняють формулам (10-11). Отже, ці функції можуть бути задані у вигляді ДГФ, заданої в табличному вигляді. Будемо записувати в таблицю лише множини індексів СФ і називати її таблицею розрядних індексів (ТРІ).

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

Метод розрахунку ТРІ полягає в наступному.

Фіксуємо вхідний перенос Cвх=С0 і розглядаємо усі комбінації наборів AN=aN, aN-1...a2a1. Для кожного набору AN розраховуємо вихідну функцію F=Si+1 чи F=C(N+1)j. Ті набори AN, для котрих F=1, заносимо в ТРІ. Таким чином, для кожної вихідної функції маємо по одній ТРІ для кожного значення вхідного переносу Cвх=C0. Наступним етапом є мінімізація отриманих ТРІ на основі операцій групового склеєння.

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

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

При реалізації багатооперандних структур виникає задача визначення знаку результату підсумовування N чисел у додатковому коді для N-операндного суматора. Традиційно ця задача вирішується шляхом розширення розрядної сітки операндів на k=[log2(N-1)]+1 розрядів шляхом дублювання знакового розряду, щоб результат підсумовування укладався цілком у розрядну сітку операндів. Це призводить до ускладнення схеми підсумовування за рахунок додаткових розрядів багатооперандних суматорів.

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

Схема пристрою визначення знаку в загальному випадку містить вертикальний суматор для одержання суми в оберненому коді, і k-розрядний двооперандний суматор для підсумовування оберненого коду з переносами Qk …Q2Q1 за формулою (15). Швидкодія пристрою залежить лише від двооперандного суматора. Отримано формули і схема для N=3 (рис. 3):

При проектуванні багаторозрядних суматорів виникає задача розбивки операндів на сегменти, що підсумовуються кожний своїм каскадом. З метою збільшення швидкодії пристрою, що складається з кількох каскадів, розроблено метод проектування схеми прискореного переносу, що обчислює та одночасно видає на входи переносів всіх каскадів значення вхідних переносів Свх(i) на основі вхідних переносів пристрою Свх(1) і деяких допоміжних функцій ВФi, що залежать від операндів і генеруються БДФ кожного каскаду. Цей метод заснований на інтерпретації каскаду як одного розрядного зрізу з кількістю одиниць на вході Mi від 0 до Qmax(i)= M1(i)+ 2M2(i)+...+2k-1Mk(i), і на тому, що k-розрядний каскад суматора виконує функцію ділення кількості одиниць на 2k. У результаті застосування модифікованого методу утворюються ТРІ, термами яких є ВФi , що залежать від Q(i). Застосування схеми прискореного переносу забезпечує збільшення швидкодії пристрою в 1,5-2 рази в порівнянні з послідовним з'єднанням каскадів при збільшенні складності пристрою на 5-15%. Перевагою цього методу є можливість проектування блока прискореного переносу для різнотипних каскадів.

Таблиця 1

Фрагменти ТРІ чотирибітного каскаду триоперандного суматора

Вхідні переноси Cвх2C вх1	Вхідні переноси Cвх2C вх1
0 0	0 1	1 1	0 0	0 1	1 1
Розрядні індекси для S3	Розрядні індекси для S2
3	2	1	3	2	1	3	2	1	2	1	2	1	2	1
0,2	1,2	2,3	0,2	1,2	1,2	0,2	0,1	2,3	0,2	2,3	0,2	1,2	0,2	0,1
0,2	2,3	0,1	1,3	0,3	1,2	0,2	1,2	0,1	1,3	0,1	1,3	0,3	1,3	2,3
1,3	0,1	0,1	0,2	2,3	0	1,3	0,3	0,1
1,3	0,3	2,3	1,3	0,1	0	1,3	2,3	2,3
			0,2	0,1	3
			1,3	2,3	3

За допомогою запропонованого методу розроблено триоперандний 16-розрядний чотирикаскадний суматор із схемою прискореного переносу, який швидше прототипу на 30%. Фрагмент ТРІ, що описує його функціонування, приведено в табл. 1.

На основі триоперандного суматора розроблено таблично-алгоритмічний помножувач 4n*4n, що у 1,3 рази швидше прототипу, який використовує для підсумовування часткових додатків двооперандні суматори (рис. 4).

На підставі отриманих якісних характеристик багатооперандних суматорів запропоновано модифікований метод згортки багаторядного коду, що дозволяє зменшити витрати устаткування. Швидкий комбінований вертикально-секційний триетапний спосіб згортки припускає на першому етапі стиск m-рядного коду в m'-рядний код за допомогою БОС, на другому етапі секціонування m'-рядного коду з метою згортки в дворядний, причому кожна секція обробляється m'-операндним k-розрядним суматором, де m'=k=[log2(m'-1)]+1. З урахуванням можливості проектування ефективних швидкодіючих багатооперандних суматорів запропоновано модифікацію методу секціонування, при якому секціонований m-рядний код стискується не в дворядний код, а в t-рядний (t>2) і отриманий код на третьому етапі підсумовується t-операндним паралельним суматором. При цьому розрядність секції k зменшується в t разів (k=[(1/t)log2(m-1)]+1), та апаратурні витрати переносяться з блоку обробки секцій у блок згортки t-рядного коду. Дослідження ефективності цієї модифікації показує, що перехід до трирядного коду дає зменшення устаткування при рядності коду m>4.

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

Створено VHDL-модель чотирибітного каскаду триоперандного суматора, отриманого за допомогою розробленого в дисертації методу проектування багатооперандних структур, і проведено функціонально-логічне моделювання пристрою для перевірки правильності функціонування суматора. В результаті проведеного моделювання доведена правильність функціонування моделі і показана вірогідність вищевказаного методу. Фрагменти діаграм роботи суматора наведені на рис. 5, де Aop, Bop, Cop операнди, sExpectedSum очікувана сума, sGotSum отримана сума.

За допомогою програми Orcad Express 7.0 проведено логічний синтез моделі суматора на елементній базі масиву логічних вентилів (FPGA) фірми Xilinx і функціонально-логічне моделювання суматора. Логічний синтез надав можливість вивести евристичну формулу вентильної складності синтезованих по запропонованому в цій роботі методу схем багатооперандних суматорів при довільних значеннях параметрів суматора і розрахувати величину похибки цієї формули. Аналітичне співвідношення для чисельного значення складності схеми, вираженої у вентилях.

Деякі розроблені методи доведені до програмної реалізації на ЕОМ та приведені рекомендації щодо їх використання. Програма виділення симетричної частини з довільної функції дає вичерпну інформацію з приводу симетрії булевої функції і може бути основою підсистеми функціонально-логічного проектування ЦП на основі ЧСФ. Програма розрахунку ТРІ, яка відповідає розробленому методу проектування багатооперандних суматорів, дозволяє в автоматичному режимі одержувати множину варіантів, що відрізняються характеристиками складності та швидкодії і використується для аналізу властивостей зазначеного методу, зокрема складності одержаних схем.

Проведений аналітичний і експериментальний аналіз характеристик методу проектування багатооперандних суматорів дозволив розробити рекомендації для його використання. Для вибору оптимальних параметрів каскаду, як от кількості операндів N і розрядності M, а також типу переносу, здійснюється дослідження функцій складності Zобщ(N, M) та приведеної до одного біта складності Zбит(N, M) N-операндного M-розрядного суматора (NM). Аналіз графіків на рис. 6 показує, що починаючи з деякої величини M0, йде різке експоненціальне зростання складності. Аналогічно зроблено висновок, що використання вихідних переносів з бітами однакової ваги більш ефективно, ніж позиційний двійковий перенос, при кількості операндів N<9.

ВИСНОВКИ

1. Використання СФ і ЧСФ для опису АП при синтезі N-розрядних швидкодіючих структур зменшує розмірність задачі синтезу в порівнянні з використанням традиційної булевої алгебри від 2MN до (M+1)N, де M кількість операндів суматора. Це дозволяє розширити застосування методів синтезу на багаторозрядні структури.

2. Опис функціонування АП у термінах алгебри СФ і ЧСФ дозволяє значно звузити зону пошуку оптимального рішення задачі синтезу АП, відкинувши велику кількість некорисних варіантів синтезу, і наблизити пристрій до оптимального.

3. Застосування апарату СФ забезпечує одноманітність опису функціонування АП та можливість формалізації процесу проектування АП, що дало можливість створити ефективні методи автоматизованого проектування суматорів.

4. Основні результати роботи: 1) запропоновано метод представлення і мінімізації ЧСФ із декількома комплектами СА, що дозволяє застосувати ЧСФ для ефективного синтезу багаторозрядних суматорів; 2) розроблено метод і алгоритм довизначення неповністю заданої довільної булевої функції до СФ, що дозволяє розширити клас СФ; 3) розроблено метод і програма логічного проектування N-операндного суматора із довільною кількістю операндів у розрядах та автоматизованої генерації його опису в термінах алгебри СФ, а також метод проектування схеми прискореного переносу для багатооперандного суматора; 4) на основі запропонованого методу синтезовано суматор трьох операндів на базі чотирибітного каскаду і схеми прискореного переносу; 5) розроблено метод проектування схеми визначення знаку результату підсумовування N чисел у додатковому коді на базі універсальної аналітичної залежності, що забезпечує підвищення швидкодії в 1,3 рази і більш і зменшення складності схеми в 1,4 рази і більш; 6) розроблено метод побудови таблично-алгоритмічного помножувача на основі триоперандного суматора, що дає підвищення швидкодії пристрою в 1,3 рази; 7) запропоновано модифікований метод згортки багаторядного коду на основі багатооперандних суматорів, що дає зменшення складності схеми в 1,2 рази і більш.

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

1. Паулин О.Н., Ляховецкий А.М., Синегуб Н.И. Повышение быстродействия комбинационных умножителей // Труды Одесского политехнического университета. Одесса. 1996. № 2. С. 17-18.

2. Паулин О.Н., Ляховецкий А.М. Определение значения знакового разряда результата суммирования N чисел // Труды Одесского политехнического университета. Одесса. 1997. № 2. С. 37-40.

3. Паулин О.Н., Ляховецкий А.М. Автоматизация функционально-логического проектирования некоторых классов цифровых устройств // Труды Одесского политехнического университета. Одесса. 1998. № 2(6). С. 31-33.

4. Ляховецкий А.М. Автоматизация проектирования блока ускоренного переноса многословного сумматора на базе симметрических булевых функций // Приднiпровський науковий вiсник. Технiчнi науки. Днепропетровск. 1998. № 90 (157). С. 43-48.

5. Паулин О.Н., Ляховецкий А.М. Синтез симметрической булевой функции на базе неполностью заданной булевой функции // Приднiпровський науковий вiсник. Технiчнi науки. Днепропетровск. 1998. № 108 (175). С. 49-55.

6. Паулин О.Н., Ляховецкий А.М. Таблично-алгоритмический умножитель 4n*4n на основе сумматора трех операндов // Научные труды молодых ученых. Одесса: Одесский государственный политехнический университет. 1997. С. 97 - 101.

7. Паулин О.Н., Ляховецкий А.М. Таблично-алгоритмический метод умножения // Ученые записки Симферопольского государственного университета. Сборник трудов международной научно-технической конференции “Приборостроение-98”. Винница-Симферополь. 1998. С. 156-159.

8. Патент 94023276 Украины, МКИ G06F 7/50. Пристрiй для пiдсумовування трьох n-розрядних операндiв / Паулин О.Н., Ляховецкий А.М., Синегуб Н.И.; Одесский политехнический университет. -- № 23235А; Заявл. 14.02.1994; Опубл. 19.05.1998; Бюл. “Промислова власність”, 1998, № 4/2. -- С. 272.

9. Синтез комбинационных схем, описываемых частично симметрическими булевыми функциями / Паулин О.Н., Ляховецкий А.М.; Одесский государственный политехнический университет. Одесса, 1995. 23 с. Рус. Деп. в ГНТБ Украины 13.02.95, № 350 Ук95 // Анот. в ж. ВИНИТИ РАН “Депонированные научные работы”, № 5 (282), 1995, б/о № 238.

Ляховецький О.М. Методи функціонально-логічного проектування швидкодіючих арифметичних пристроїв на основі симетричних булевих функцій. Рукопис.

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

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

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

Lyakhovetsky A.M. Methods of functional-logical design of fast arithmetical devices based on symmetric boolean functions. Manuscript.

The thesis for Master of technical Science degree by speciality 05.13.05 “Elements and devices of computers equipment and control systems”. Odessa State Politechnical University, Odessa, 1999.

A new approach to fast arithmetical devices (AD) design has been developed, that is based on using of specific particularities of data input symmetry, and can provide considerable speedup, hardware abundunce reduction of developed devices due to considering of some specific properties of performed operations, simplification of design procedures, unification of design process and possibility of automation of some design procedures. Methods of functional-logical design of fast multi-operand adders and multipliers are suggested, that are based on usage of symmetric boolean functions with partial symmetry for defining functionality of these devices. The results of research work are recommended to use for design of arithmetical-logical units, contained in special processing devices, intended for digital signal processing, parallel data flow real time processing, coding and decoding devices and other tasks, that are critical to system response time.

Key words: arithmetical device, symmetric boolean functions, partial and total symmetry, automation, design, speed.

Ляховецкий А.М. Методы функционально-логического проектирования быстродействующих арифметических устройств на основе симметрических булевых функций. Рукопись.

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.05 “Элементы и устройства вычислительной техники и систем управления”. Одесский государственный политехнический университет, Одесса, 1999.

В работе разрабатывается новый подход к проектированию быстродействующих арифметических устройств (АУ), основывающийся на использовании свойства симметрии входов АУ и обеспечивающий повышение быстродействия и устранение избыточности АУ, упрощение, единообразие и возможность формализации и автоматизации процесса проектирования. Предложены методы функционально-логического проектирования многооперандных сумматоров и умножителей, основанные на использовании частично-симметрических булевых функций (ЧСФ).

Выявлены недостатки известных методов проектирования быстродействующих АУ: а) системы булевых функций, описывающие многооперандные одноразрядные сумматоры (МОС), слабо минимизируются в классах нормальных форм, поэтому синтез МОС традиционными методами затруднителен; б) применение существующих методик многоразрядных сумматоров на основе ЧСФ при большом числе разрядов усложнено, так как требует многократной аналитической декомпозиции функций, что приводит к ухудшению быстродействия схем; в) существуют эффективные методы проектирования только бинарных арифметических структур, а многооперандные структуры строятся на основе бинарных; г) задача синтеза N-разрядных сумматоров имеет размерность 2MN, где M количество операндов, что ограничивает возможность ее решения традиционными методами булевой алгебры; д) существующий аппарат СФ позволяет использовать только один симметрический комплект аргументов (СК), что дает возможность строить многооперандные структуры только с цепью распространения межразрядного переноса.

В диссертационной работе теория СФ развивается и обобщается с целью адаптации к проектированию многоразрядных сумматоров. Понятие частичной симметрии обобщается на случай нескольких СК. Предложены способы представления и минимизации ЧСФ, составляющие основу методов синтеза схем на основе ЧСФ. Разработан метод доопределения неполностью заданной функции до СФ, способный находить все варианты доопределения с учетом инверсий и частичной симметрии. Его использование сокращает сложность задачи от экспоненциальной до линейной. Метод обладает высокой степенью формализации, что позволяет реализовать его на ЭВМ.

Получена методика проектирования многооперандного быстродействующего сумматора с произвольным количеством слагаемых в разрядах, основанная на вертикальной обработке информации и на итерационном алгоритме, моделирующем распространение переноса. Полученные сумматоры отличаются от традиционных отсутствием цепи внутреннего переноса. За счет использования метода представления и минимизации ЧСФ данная методика позволила получить трехоперандный сумматор, который быстрее в 1,3 раза по сравнению с традиционным способом суммирования трех операндов.

С целью повышения быстродействия многооперандных сумматоров разработан метод проектирования схемы ускоренного переноса, увеличивающий быстродействие в 1,5-2 раза по сравнению с последовательным соединением каскадов.

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

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

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

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

Создана VHDL-модель разработанного трехоперандного сумматора, и проведено ее функционально-логическое моделирование. Произведен логический синтез модели на базе программируемого массива логических вентилей (FPGA) и функционально-логическое моделирования модели на логическом уровне, приведены аналитические оценки вентильной сложности сумматоров.

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

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

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

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