Мета роботи: набуття практичних навичок з з моделювання матричних алгоритмів обробки оптичних сигналів за технікою символьних підстановок.
Хід роботи
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а, одиниці і нулі є взаємними доповненнями. За допомогою чотирьох правил підстановки які показують суму Si і перенос Pi наведених на рис.3.3б, додавання можна провести зразу над всіма зображеннями чисел. Як видно із рис.3.3в, правила повинні використовуватись (L+1) раз, тобто стільки разів, скільки розрядів L в числі, враховуючи що при порозрядному додаванні із-за можливості виникнення переносу із старшого L-го розряду необхідно виконати ще один раз перетворення.
Загальна схема оптичного процесору, який виконує операцію додавання двійкових чисел за методом символьних підстановок на основі поляризації світла (рис.3.3) містить систему 1 мультипліціювання вхідного зображення Івх на р=4 канали, систему 2 зведення зображення з зміщеними символами, поляризаційно-чутливі кубики 3, чотири канали 4. В такому випадку необхідно розпізнавати символи, які задаються не темними із світлими клітками, а за допомогою стану поляризації світла (« “нуль”, ¯ “одиниця”).
Таким чином цикл обробки одного процесору складає (L+1) тактів і еквівалентний за часом обробці на порозрядній схемі.
![]() |
Використання модифікованого подання чисел зі знаковим розрядом {1,0,-1} замість двійкової системи приводить до алгоритмів символьної підстановки, в яких необхідна для додавання кількість кроків не залежить від кількості розрядів [1]. В цьому випадку немає потреби в операціях переносу. Але для реалізації символьної підстановки на основі цього підходу треба мати три набори правил підстановки. Оптичне множення та ділення можна виконати, використовуючи модифіковане подання зі знаковим розрядом за час пропорційний log2N, де 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 розрядних чисел за технікою символьних підстановок.
Які вимоги висуваються до формування правил підстановок?
Назвіть область застосування методу символьних підстановок.
Порівняєйте методи символьної підстановки та оберіть найефективніший: послідовний; з паралельним використанням декількох правил; з використанням одного правила.