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

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

УДК 681.325.5

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

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

АВТОРЕФЕРАТ
дисертації на здобуття наукового ступеня
кандидата технічних наук

Одеса - 1999

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

Робота виконана на кафедрі “Системне програмне забезпечення”
Одесь-ко-го державного політехнічного університету міністерства освіти України.

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

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

Паулін Олег Миколайович, Одеський державний політехнічний університет, доцент кафедри
“Системне програмне забезпечення”

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Зв'язок роботи з науковими програмами, планами, темами. Дослідні роботи, зок--ре-ма, розробка пакета прикладних програм для автоматизації проектування ариф-ме---тич-них пристроїв, зв'язані з темою планової науково-дослідної роботи кафедри сис--темного програмного забезпечення ОДПУ № 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. Симетричним набором (СН) називається кон’юнкція всіх груп СФ. ДГФ має вигляд:

(1)

де ai індекси СФ y; G1, ... , Gp групи j-го набору груп; li кількість СН ваги ai.

Поряд із симетричними функціями, існує клас частково симетричних булевих функцій (ЧСФ), у яких тільки частина аргументів 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) по двом аргументам, яке виглядає так:

(2)

де залишкові функції R(X) залежать від аргументів xn-1,..., xi+1,xi-1,..., xj+1, xj-1,..., x0. З рівняння (2) виплива-ють правила визначення відношення симетрії xixj.

(3)

(4)

(5)

Ефективним засобом аналізу залишкових функцій являються декомпозиційні кар-ти. Де-ком-позиційна карта (ДК) 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) розробити пакет підпрограм функці-ональ-но-ло-гіч-ного проектування АП, зокрема: а) програму виявлення симетричної час-тини в довіль-ній булевій функ-ції; б) програму розрахунку розрядних індексів для проек-тування суматорів із довільною кількістю доданків у розрядах.

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

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

Розглянемо властивості частково симетричних наборів. Сукупність ЧСН порядку r із ступенями комплектів mi (1 i r) таких, що кількість одиниць в i-м комплекті СЧ дорівнює ai, покривається сукупністю ЧСФ-конституєнт виду

(6)

де усі можливі НСЧ-конституєнти, при яких виконується умова властивості. Таким чином, функція, що відповідає цій сукупності ЧСН

(7)

де y(x1, x2 , ... , xk ) деяка функція від несиметричних аргументів x1 , x2, ... xk. .

Теорема 1. Будь-яку ЧСФ можна представити у вигляді логічної суми членів (7).

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

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

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

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

Оцінка складності запропонованого нами алгоритму дається формулою

(8)

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

(9)

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

У третьому розділі розглядаються питання проектування багатооперандних струк--тур швидкодіючих суматорів та їх застосування в матричних помножувачах. От-ри--мано методику проектування каскаду багатооперандного суматора з довіль-ною кіль-кістю до-дан-ків у розрядах, що заснована на моделі з вертикальною обробкою ін-фор--мації та на ітераційному обчислювальному алгоритмі, який моделює поширення пе--ре-носу уздовж розрядної сітки. Отримані за допомогою описаної методики су-ма-то-ри від-різ-няються від тра-диційних суматорів із паралельним переносом від-сут-ніс-тю лан--цю-га внутрішнього переносу. За рахунок використання непозиційного пере-но-су з бі-тами од-на-кової ваги і роз-робленого в даній роботі математичного апарату пред-став-лен-ня і мі-ні-мізації ЧСФ ця ме-тодика дозволила отримати чотирибітний кас-кад три-опе-ранд-ного суматора, що збіль-шує швидкодію в 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, що відрізняються лише порядком розташування одиниць у кож--ному розрядному зрізі. Таким чином, використання індексів, рівних кількості оди--ниць у кожному розрядному зрізі, дозволяє значно скоротити обсяг вихідних даних для опи-су функціонування суматора і надалі спростити його проектування.

Назвемо підсумковою вагою доданків (ПВД) величину Q, надану у формі, а підсумковою вагою входів (ПВВ) величину Q', що визначається співвідношенням

де С числовий еквівалент вхідного переносу.

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

(10)

. (11)

Кожному значенню ПВД 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). Отже, ці функції можуть бути задані у вигляді ДГФ, заданої в таб-лич-ному виг-ляді. Будемо записувати в таблицю лише множини індексів СФ і називати її таблицею розрядних індексів (ТРІ).

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

(12)

де Ci+1 перенос у (i+1)-й розряд з i-го розряду, С0 вхідний перенос. Ця формула моделює процес поширення переносу уздовж розрядної сітки і випливає з того, що кожний розряд суматора є подільником кількості одиниць на 2.

Формула для обчислення вихідних функцій суми:

(13)

Формула для обчислення вихідних функцій переносу:

(14)

де C(i+1) j j-й розряд переносу з i-го в (i+1)-й розряд.

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

Фіксуємо вхідний перенос 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 чисел у додатковому коді від значень зна---ко-вих розрядів операндів і переносів з основної розрядної сітки операндів, та от-ри--мана за-лежність, що дозволяє реалізувати ефективні схеми для будь-якого числа операн-дів:

(15)

де Rk…R2R1 — двійковий еквівалент суми знакових розрядів операндів, тобто
Rk...R2R1 = Zi (підсумовування здійснюється по всім операндам); Qk...Q1 - позиційні пере-носи з урахуванням N знакових розрядів, тобто Qk...Q1Q0 = Rk...R2R1 + Pk...P2P1;
Z - дійсний знаковий розряд результату; U1... Uk - дійсні розряди переповнення;

обернений код числа Rk…R2R1.

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

Рис. 1. N-розрядний Рис. 2. Структура Рис. 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%. Перевагою цього ме-то-ду є можливість про-ектування блока прискореного переносу для різнотипних каскадів.

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

Таблиця 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

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

Рис. 4. Таблично-алгоритмічний помножувач 12*12.

На підставі отриманих якісних характеристик багатооперандних суматорів за--про--по-новано модифікований метод згортки багаторядного коду, що дозволяє змен-ши--ти витрати устаткування. Швидкий комбінований верти-кально-сек-ційний три--етап----ний спо--сіб згортки припускає на першому етапі стиск 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 отримана сума.

Рис. 5. Діаграми роботи каскаду трьохоперандного суматора

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

(16)

де Z(БДФ) вентильний коефіцієнт складності БДФ, що розраховується методом Квайна, N кількість операндів суматора, М кількість його розрядів.

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

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

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

Рис. 6. Параметричні графіки складності суматора Рис. 7. Визначення знаку

ВИСНОВКИ

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 на основе сумма-тора трех операндов