Моделювання на ЕОМ цифрового паралельного оптичного процесора за технікою символьних підстановок

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

Хід роботи

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

2. Скласти алгоритмічну модель процесу виконання символьної підстановки, згідно з яким вхідна бінарна матриця розмірністю 8´8 елементів пере­тво­рю­ється відповідно до правила, поданого на рис.3.1, у вихідну бінарну ма­т­рицю тієї ж розмірності.

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

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

5. Скласти блок-схему алгоритму та його програмну реалізацію операції до­да­вання L-роз­ря­д­них двійкових чисел за методом символьних підстановок

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

7. Зробити висновки по роботі стосовно ефективності роботи методу симво­ль­них підстановок.

8. Оформити звіт по роботі.

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

Таблиця 3.1.

№ вар	Перший доданок	Другий доданок	№ вар	Перший доданок	Другий доданок
1	01110	01100	9	00001	01111
2	00010	01110	10	00111	00101
3	00101	00001	11	01010	01011
4	01010	01101	12	01110	00111
5	01111	01111	13	00100	01000
6	01010	01110	14	01011	01111
7	00011	00101	15	01111	01011
8	00101	01101

Рис 3.1.

Теоретичні відомості

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

Символьні підстановки [1,2] це ще один засіб використання парале­лі­з­му, властивого оптичним пристроям. Йому дано чітке математичне визна­че­н­ня [3] як способу реалізації паралельних оптичних логічних операцій на при­с­тро­ях з обмеженою спроможністю навантаження за входом і виходом і із про­сторово-інваріантними зв’язками однакової довжини.

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

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

Приклад застосування символьної підстано­в­ки в операції додавання дві­й­кових чисел (1100; 1001) подано на рис.3.3. Як видно з рис.3.3а, одиниці і нулі є взаємними доповненнями. За допомогою чотирьох правил підстановки які показують суму S_i і перенос P_i наведених на рис.3.3б, додавання можна про­ве­с­ти зразу над всіма зображеннями чисел. Як видно із рис.3.3в, правила повинні використовуватись (L+1) раз, тобто стільки разів, скільки роз­ря­дів L в числі, вра­хову­ю­чи що при по­розрядному додаванні із-за можливо­сті виник­не­н­ня переносу із старшого L-го розряду необхідно виконати ще один раз пере­т­во­рення.

Загальна схема оп­ти­чного процесору, який виконує операцію додавання двійкових чисел за методом символьних підстановок на основі поляризації світла (рис.3.3) містить систему 1 мультипліціювання вхідного зображення І_вх на р=4 канали, систему 2 зведення зображення з зміщеними символами, по­­ля­ризаційно-чутливі кубики 3, чотири канали 4. В такому випадку не­об­хі­д­но розпізнавати символи, які задаються не темними із світлими клітками, а за допомогою стану поляризації світла (« “нуль”, ¯­ “одиниця”).

Таким чином цикл обробки одного процесору складає (L+1) тактів і еквівалентний за часом обробці на порозрядній схемі.

Використання модифікованого подання чисел зі знаковим розрядом {1,0,-1} замість двійкової системи приводить до алгоритмів символьної під­ста­новки, в яких необхідна для додавання кількість кроків не залежить від кількості розрядів [1]. В цьому випадку немає потреби в операціях переносу. Але для реалізації символьної підстановки на основі цього підходу треба ма­ти три набори правил підстановки. Оптичне множення та ділення можна виконати, використовуючи модифіковане подання зі знаковим розрядом за час пропорційний log₂N, де N – довжина співмножника чи дільника [1].

Обмеження і порівняння методів

Порівняємо три методи символьної підстановки [1]: послідовний в часі; з пара­ле­ль­ним використанням декількох правил; з використанням одного пра­­ви­­ла. При порівнянні допускається, що для фізичної реалізації відпові­д­них си­стем використовуються симе­т­ри­ч­ні самоелектрооптичні пристрої (S-SEED – symmetric self-electrooptic device). Проводиться порівняння числа циклів об­робки, числа пристроїв, а також часу, необхідного для викона­ння додава­н­ня.

В послідовному в часі методі для виконання операції додаваання N –ро­з­рядних чисел буде використовуватись чотири правила символьної підс­та­но­в­ки. Тоді необхідно N +1 циклів обробки для N розрядів ( по одному для ко­ж­ного із чотирьох правил) і, відповідно 4(N + 1) реалізацій правил розпі­зна­ва­ння символів і копіювання комбінацій. Для технічної реалізації необхідно 8(N + 1) S-SEED –пристроїв.

В випадку паралельного використання декількох правил необхідно N +1 цик­лів обробки, але всі операції для всіх чотирьох правил будуть вико­ну­ва­тись одночасно. З цією ціллю вхідна комбінація ділиться на чотири частини. Оскі­льки всі чотири правила виконуються одночасно, цей метод характе­ри­зу­ється найменшим часом обробки. Але він вимагає 4(N+1) S-SEED-прис­т­роїв і 12(N+1) SEED-пристроїв, що використовуються в якості вентелів АБО-НІ.

В більш загальному випадку з одним правилом є лише одне правило під­с­тановки, але для реалізації суматора необхідно керуючі комірки. Вико­ри­с­товуючи SEED-пристрої, можна скласти напівсуматор, але потім його не­обхі­дно просторово продублювати (N+1)(N+2)/2 і з’єднати в вигляді N+1 рі­внв, або каскадів. Цей метод має найбільший час обробки, оскільки одне пра­вило підстановки, що використовується, має обмежену обчислювальну по­ту­жність, і, таким чином, повинно використовуватись багаторазово.

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

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

Література

Кейти У.Е., Вагнер К., У.Дж.Майсен. Цифровые вычислительные ма­ши­ны с оптическими устройствами // ТИИЭР, Т.77, №10, 1989, с.121-136.

Н.Штрайбль, К.Х.Бреннер, А.Хуан и др. Цифровая оптика // ТИИЭР, Т.77, №12, 1989, с.179-194.

K.H.Brenner. Digital jptical computing with symbolic substitution // Optical Computing 88, Toulon, France, also in Proc.SPIE. vol. 963.

Федоров Б.В. Оптические логические элементы для высокопроизводите­ль­ных оптических процессов//

Контрольні запитання

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

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

Які вимоги висуваються до формування правил підстановок?

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

Порівняєйте методи символьної підстановки та оберіть найефектив­ні­ший: послідовний; з паралельним використанням декількох правил; з використанням одного правила.