Комірка однорідної структури

Комірка однорідної структури, яка містить перший мультиплексор, арифметично-логічний елемент, мініматор, перший і другий регістри, блок налаштування, який містить елемент АБО-НІ і елемент затримки, причому інформаційні входи першої групи комірки з'єднані з першими інформаційними входами першого мультиплексора, інформаційні входи третьої групи комірки з'єднані з другими входами мініматора, виходи другого регістра є інформаційними виходами третьої групи комірки, інформаційні входи другої групи комірки з'єднані з інформаційними виходами другої групи комірки, виходи арифметично-логічного елемента з'єднані з інформаційними входами блока налаштування та другими інформаційними входами першого мультиплексора, інформаційні виходи якого з'єднані з входами першого регістра, входи елемента АБО-НІ є ін формаційними входами блока налаштування, вихід елемента затримки блока U 2 36458 1 3 36458 виходом четвертого елемента І та першим входом третього елемента АБО, другий та третій входи якого з'єднані з виходами другого та п'ятого елементів І, виходи першого, другого та третього елементів АБО з'єднані з другим, третім та четвертим виходами комірки, шостий вихід якої з'єднаний з другими входами шостого та восьмого елементів І та п'ятим виходом комірки, третій вихід четвертого елемента І з'єднаний з виходом тригера, причому перший вхід комірки з'єднаний з першими входами дев'ятого, десятого та одинадцятого елементів І, другі входи яких з'єднані з виходом тригера, виходом третього елемента НІ та другим входом комірки відповідно, а треті входи дев'ятого, десятого та одинадцятого елементів І з'єднані з шостим входом комірки та входом четвертого елемента НІ, вихід якого з'єднаний з четвертим входом другого елемента І, вихід першого елемента НІ з'єднаний з третіми входами шостого та восьмого елементів І, виходи яких з'єднані з першими входами четвертого та п'ятого елементів АБО, другі входи яких з'єднані з виходами одинадцятого та десятого елементів І, а ви ходи четвертого та п'ятого елементів АБО з'єднані з одиничним і нульовим входами тригера, вхід третього елемента НІ з'єднаний з другим входом комірки, четвертий вхід третього елемента І з'єднаний з виходом дев'ятого елемента І. Відома комірка виконує: а) інформаційний пошук, який містить пошук максимального елемента, пошук мінімального елемента, розбиття масиву на три підмножини; б) перетворення структур, що містить розширення, стиснення, зваження; в) пересування даних, що містить запис інформації у стовпець, зсув даних. Але цей набір операцій є недостатнім для реалізації класифікації масивів даних на таких однорідних стр уктура х. Найбільш близькою за технічкою суттю є комірка однорідної структури [патент України №13107, кл. G06F7/00, 2006р. Бюл. №3], яка містить мультиплексор, в подальшому поіменований як перший мультиплексор, демультиплексор, арифметичнологічний елемент, мініматор, перший і другий регістри та блок налаштування, який містить RSтригер, елементи І, АБО-НІ, АБО і елемент затримки, причому інформаційні входи першої групи комірки з'єднані з інформаційними входами першого мультиплексора, керуючий вхід демультиплексора з'єднаний з однойменним входом першого мультиплексора, виходи демультиплексора з'єднані з інформаційними виходами першої групи комірки, інформаційні входи другої гр упи якої з'єднані з другим входом арифметично-логічного елемента, причому виходи першого регістра з'єднані з інформаційними входами демультиплексора, другі інформаційні виходи якого з'єднані з першими входами арифметично-логічного елемента і мініматора, інформаційні входи третьої групи комірки з'єднані з другими входами мініматора, виходи якого з'єднані з входами другого регістра, виходи якого є інформаційними виходами третьої групи комірки, інформаційні входи другої групи комірки з'єднані також з інформаційними виходами другої групи комірки, виходи арифметично-логічного елемента з'єднані з інформаційними входами блока налаштування та другими інформаційними вхо 4 дами першого мультиплексора, інформаційні виходи якого з'єднані з входами першого регістра, входи елемента АБО-НІ є інформаційними входами блока налаштування, а вихід елемента АБО-НІ з'єднаний з першими входами елементів АБО та І, другий вхід елемента АБО з'єднаний з входом початкового встановлення пристрою, а вихід з'єднаний з R- входом RS-тригера, S- вхід якого з'єднаний з входом дозволу пристрою, а інверсний вихід з'єднаний з другим входом елемента І та керуючим входом демультиплексора і першого мультиплексора, вихід елемента І з'єднаний з входом елемента затримки, вихід якого є виходом скиду комірки, вхід скиду якої з'єднаний з входом скиду першого регістра і входом ознаки нуля мініматора. Недоліком даної комірки однорідної структури є обмежені функціональні можливості через послідовний запис по стовпцях елементів початкової матриці. В основу корисної моделі поставлена задача створення комірки однорідної структури, в якій в результаті введення нових вузлів та зв'язків досягається можливість виконання в однорідній структурі операцій паралельного запису елементів матриці, визначення мінімального елемента у стовпцях матриці, формування невпорядкованої та впорядкованої матриць, що дозволяє реалізувати класифікацію масивів даних, тобто розширити функціональні можливості як комірки, так і однорідної структури на цих комірках. Поставлена задача вирішується тим, що в комірку однорідної структури, яка містить перший мультиплексор, арифметично-логічний елемент, мініматор, перший і другий регістри, блок налаштування, який містить елемент АБО-НІ і елемент затримки, причому інформаційні входи першої групи комірки з'єднані з першими інформаційними входами першого мультиплексора, інформаційні входи третьої групи комірки з'єднані з другими входами мініматора, виходи другого регістра є інформаційними виходами третьої групи комірки, інформаційні входи другої групи комірки з'єднані з інформаційними виходами другої групи комірки, виходи арифметично-логічного елемента з'єднані з інформаційними входами блока налаштування та другими інформаційними входами першого мультиплексора, інформаційні виходи якого з'єднані з входами першого регістра, входи елемента АБОНІ є інформаційними входами блока налаштування, вихід елемента затримки блока налаштування є виходом скиду комірки, вхід скиду якої з'єднаний з входом скиду першого регістра, введено другий мультиплексор і (q+1)- вхідний елемент І, де q розрядність даних, а блок налаштування містить D-тригер, перші входи арифметично-логічного елемента з'єднані з виходами першого регістра, які також з'єднані з першими входами мініматора та інформаційними виходами першої групи комірки, причому вхід заборони комірки з'єднаний з інверсним входом (q+1)- вхідного елемента І та керуючим входом другого мультиплексора, виходи (q+1)- вхідного елемента І з'єднані з другими входами арифметично-логічного елемента, виходи мініматора з'єднані з другими інформаційними входами другого мультиплексора, перші інформа 5 36458 ційні входи якого з'єднані з інформаційними входами третьої групи комірки, а виходи якого з'єднані з входами другого регістра, інформаційні входи другої гр упи комірки з'єднані з q входами (q+1)вхідного елемента І, інформаційні входи четвертої групи комірки з'єднані з третіми інформаційними входами першого мультиплексора, а вхід дозволу комірки з'єднаний з входом скиду D-тригера блока налаштування комірки, вихід елемента АБО-НІ якого з'єднаний з D-входом D-тригера, прямий вихід якого з'єднаний з другим керуючим входом першого мультиплексора і через елемент затримки з'єднаний з виходом блока налаштування. На Фіг.1 подано схему однорідної структури, на Фіг.2 показано структурну схему комірки однорідної структури. Однорідна структура (Фіг.1) містить m рядків по n комірок у кожному рядку, тобто має вигляд матриці комірок 1i. j розмірністю m ´ n , у кожному j ( ) 6 (q+1)-вхідний елемент І 19, де q - розрядність даних, мультиплексор 20, блок 21 налаштування, до якого входять D-тригер 22, q-вхідний елемент АБО-НІ 23 та елемент 24 затримки. Інформаційні входи 8 групи комірки 1i. j з'єднані з першими інформаційними входами мультиплексора 14, вхід скиду D-тригера 22 блока 21 налаштування з'єднаний з входом 12 дозволу пристрою, виходи регістра 17 з'єднані з входами 25 АЛЕ 15 і входами 26 мініматора 16, а також є інформаційними виходами 10 групи комірки 1i. j . Ін формаційні входи 4 групи комірки 1i. j з'єднані з інформаційними входами 27 мультиплексора 20 і з входами 28 мініматора 16, виходи якого з'єднані з інформаційними входами 29 мультиплексора 20, виходи якого з'єднані з входами регістра 18, виходи якого є інформаційними виходами 2 групи комірки 1i. j . Інформаційні Вхід 9i всіх комірок 1i. j і-го рядка i = 1, m є входом заборони і-го рядка однорідної структури. У кожному рядку однорідної структури інформаційні виходи 10 групи наступної комірки 1i. j , почи входи 5 групи комірки 1i. j з'єднані з q інформаційними входами 30 (q+1)- вхідного елемента І 19 та інформаційними виходами 3 групи комірки 1i. j , виходи (q+1)-вхідного елемента І 19 з'єднані з входами 31 АЛЕ 15, виходи якого з'єднані з входами q- вхідного елемента АБО-НІ 23 блока 21 налаштування та інформаційними входами 32 мультиплексора 14, з третіми інформаційними входами якого з'єднані інформаційні входи 11 групи комірки 1i. j . Вхід 13 керування пристрою з'єднаний з керуючим входом 33 мультиплексора 14, виходи якого з'єднані з входами 34 регістра 17. У блоці 21 налаштування вихід q- вхідного елемента АБО-НІ 23 з'єднаний з D-входом D-тригера 22, а його прямий вихід з'єднаний з керуючим входом 35 мультиплексора 14 і входом елемента 24 затримки, вихід якого є виходом блока 21 налаштування, який з'єднаний з виходом 6 скиду комірки 1i. j , вхід 7 скиду якої з'єднаний з входом скиду регістра 17. Вхід заборони 9i комірки 1i. j з'єднаний з (q+1)-м інверсним входом елемента І 19 та керуючим входом мультиплексора 20. Класифікація масивів даних в однорідній структурі (Фіг.1) виконується таким чином. Перед початком роботи за одиничним сигналом на вході 12 дозволу пристрою і при наявності нульового сиг наючи з останньої 1i.n , з'єднані з інформаційними налу на входах 9i заборони пристрою i = 1, m всі входами 11 групи попередньої комірки 1i. j-1 , крім комірки 1i. j однорідної структури встановлюються у початковий стан. Потім на інформаційні входи 8 групи комірок 1i. j подаються числа, які є елемен - му стовпці j = 1, n всі комірки 1i. j мають два інформаційні виходи 2 і 3 груп, крім останньої комірки 1m. j , яка має інформаційні виходи 2 групи, і два інформаційні входи 4 і 5 гр уп, крім першої комірки 11, j , яка має інформаційні входи 5 групи. У кожному стовпці однорідної структури інформаційні ви ( ) ходи 2 і 3 груп попередньої комірки 1i. j , i = 1,m - 1 з'єднані відповідно з інформаційними входами 4 і 5 груп наступної комірки 1i +1. j , а інформаційні виходи 2 групи останньої комірки 1m. j з'єднані з інформаційними входами 5 групи першої комірки 11, j . У кожному рядку однорідної структури вихід 6 скиду ( ) попередньої комірки 1i. j , j = 1, n - 1 , крім останньої комірки 1i.n , з'єднаний з входом скиду 7 наступної комірки 1i. j +1 . Інформаційні входи 8 групи кожної комірки 1i. j з'єднані з групою інформаційних входів пристрою. ( ) першої комірки 1i.1 кожного рядку, яка не має інформаційних виходів 10 групи, а також крім останньої комірки 1i.n кожного рядку, яка не має інформаційних входів 11 гр упи. На схемі однорідної структури (Фіг.1) не показано вхід 12 дозволу пристрою і вхід 13 керування пристрою, які є загальними і підключені до кожної комірки 1i. j . Комірка 1i. j однорідної структури (Фіг.2) містить мультиплексор 14, арифметично-логічний елемент (АЛЕ) 15, мініматор 16, регістри 17,18, ( ) тами a0i. j початкової матриці A 0 . Запис виконується паралельно за одиничним сигналом на вході 13 керування пристрою, в результаті чого в комірки 1i. j однорідної структури записано двовимірну матрицю A 0 розмірністю m ´ n вигляду 7 36458 8 é ù ê ú ê 0 ú 0 0 ê a1.1 K a1. j K a1. n ú ê ú 0 A0 = ê M M M ú = A1 ,K , A i0, K, A 0 n 0 0 0 ê ai. 1 K ai. j K ai.n ú ê M M M ú ê ú ê a0 . 1 K a0 . j K a0 .n ú m m m û ë ( де рядки представляють собою відповідні маA0 i сиви чисел = ( a01,K, a0j ,K, a0n i. i. i. ) , (i = 1,m) . Отже, у комірку 1i. j однорідної структури записано число a0i. j . Спочатку у кожному стовпці матриці A t -1 (= 1, N , де N - кількість етапів оброблення) t виконують визначення мінімального елемента, в подальшому поіменованого як мінелемент, вигляду mintj -1 a1, j = mina t, -1, j ij i = 1, n . (2) послідовно, починаючи з першого елемента кожного стовпця, але паралельно у всіх стов ( ) ) T , (1) ходи 2 гр упи та ін формаційні входи 4 групи відповідних комірок 1i. j однорідної структури. Остаточний результат формується на інформаційних виходах 2 групи останніх комірок 1m. j кожного ( ) j-го стовпця j = 1, n як вектор-рядок з n мінелементів вигляду: ( ) t t Mint -1 = min1-1, K, mintj -1, K, minn-1 . (3) Потім виконують паралельне віднімання кож ( ) ного мінелемента mint -1 j = 1, n вигляду (2) від j кожного і-го елемента відповідного j-гo стовпця матриці A t -1 і формують t-й різницевий зріз у вигляді невпорядкованої матриці A t вигляду: пцях j = 1, n . При цьому задіяно інформаційні ви æ ö ç ÷ ç ÷ ç at -1 - mint -1 K a t -1 - mint -1 K at -1 - mint -1 ÷ 1,1 1 1, j j 1,n n ÷ ç t A =ç M M M ÷ (4) t ç at,1 1 - min1-1 K ait,-1 - mintj -1 K at, -1 - mint -1 ÷ i j in n ç ÷ M M M ç ÷ ç at -1 - mint -1 K a t -1 - mint -1 K at -1 - mint -1 ÷ 1 m, j j m,n n ø è m,1 æ ö ç ÷ ç ÷ ç a t K a t K at ÷ 1,1 1, j 1,n ç ÷ t або A = ç M M M ÷ , (5) t t ÷ ç t ç ai,1 K ai, j K ai,n ÷ ç M M M ÷ ç t ÷ t t ç am,1 K am, j K am,n ÷ è ø t ai, j = ait,-1 j - mintj -1, t де = 1, N . (6) При цьому задіяно інформаційні входи 5 групи та інформаційні виходи 3 групи відповідних комірок 1i. j однорідної структури. Після виконання таких дій у кожному стовпці отриманої матриці A t (5) є хоча б один нульовий елемент. Відповідно, в кожному рядку може бути один, декілька, всі або не бути взагалі нульових елементів. Тому перевіряють умову наявності m-1 нульових рядків, тобто: t A1 = K = A t -1 = A lt+1 = K = A t = 0, A t ¹ 0, t = 1, N (7) l m l Якщо умова (7) виконується і формуються одиничні сигнали на виходах 6 скиду комірок 1i. j всіх рядків, крім l-го рядка однорідної структури, то оброблення закінчують, у протилежному випадку t виконують такі дії. Для всіх рядків матриці A (5) паралельно виконують транспозицію елементів з просуванням праворуч усі х н ульових елементів і формують впорядковану матрицю A t яка має вигляд: æ ö ç ÷ ç ÷ ç a t K a t K at ÷ 1. j 1 .n ÷ ç 1. 1 At = ç M M M ÷ (8) ç at. 1 K at. j K ait.n ÷ i ç i ÷ M M ÷ ç M ç at K at K a t ÷ m. j m.n ø è m. 1 При цьому задіяно вихід 6 скиду і вхід 7 скиду, а також інформаційні входи 11 групи та інформаційні виходи 10 групи двох суміжних комірок 1i. j та ( ) 1i, j +1 j = 1, n - 1 у всі х рядках однорідної структури. Для отриманої матриці A t (8) повторюють етапи оброблення, які складаються з вищезазначеної послідовності дій, починаючи з визначення 9 36458 мінелемента (2) у кожному стовпці матриці A t . На деякому t-му етапі оброблення у двовимірній матt риці A (5) з'являється деякий k-й рядок з усіма нульовими елементами, про що свідчить наявність одиничних сигналів на виходах 6 скиду всі х комірок 1k , j k-ro рядка однорідної структури. Цей рядок ( ) 0 вказує на k-й масив чисел Ak k = 1, m , який є мінімальним за сумою своїх елементів серед початко0 0 вих масивів A1 , K, Am . Цей k-й нульовий рядок в подальшому обробленні участі не приймає і значення його елементів в подальшому не беруть до уваги при визначенні мінелементів кожного стовпця матриці A t . Для цього призначений вхід 9k заборони пристрою, на який у цьому випадку подають одиничний сигнал. Кожний наступний нульовий рядок, який з'явиться у двовимірній матриці A t (5), вказує на масив чисел, який є мінімальним за сумою своїх елементів серед тих масивів (відповідних рядків), які ще приймають участь в обробленні. Оброблення двовимірної матриці A t (5) триває до тих пір, поки не виконається умова (7) наявності m-1 нульових рядків. Тобто, поки не залишиться один єдиний рядок, який буде містити хоча б один ненульовий елемент, а решта рядків будуть виключені з оброблення як нульові. Цей рядок вказує на деякий l-й масив, чисел ( ) Al0 l Î 1, m , який є максимальним за сумою своїх елементів серед початкових масивів чисел 0 0 A1 , K, Am . Величина N дорівнює кількості циклів оброблення, виконаних в процесі пошуку максимального за сумою його елементів масиву чисел 0 0 серед масивів A1 , K, Am . Комірка 1i, j однорідної структури (Фіг.2) працює таким чином. Вона виконує такі операції: а) паралельний запис даних в комірку 1i, j по її інформаційних входа х 8 групи; б) визначення мінімального значення серед двох операндів: першого, що подається у комірку 1i. j по інформаційних входах 4 групи, і другого, що знаходиться у комірці 1i. j , і передачу результату по інформаційних вихода х 2 групи комірки 1i, j ; в) формування різниці значень двох операндів: першого, що знаходиться у комірці 1i. j , і другого, що надходить по інформаційних входа х 5 групи комірки 1i, j , з тимчасовим збере1i, j женням отриманої різниці у комірці ; г) транзит 1i. j даних через комірку з інформаційних входів 5 групи на інформаційні виходи 3 групи комірки 1i. j ; д) транспозицію даних між комірками 1i. j ( ) та 1i. j +1 j = 1, n - 1 з просуванням праворуч на одну позицію нульових значень даних з використанням виходу 6 скиду попередньої та входу 7 скиду на 10 ступної комірок; е) виключення з оброблення комірки 1i. j з використанням входу 9i заборони пристрою. Для встановлення комірки 1i. j у початковий стан подається одиничний сигнал з входу 12 дозволу пристрою на вхід скиду D - тригера 22 блока 21 налаштування. В результаті на його прямому виході встановлюється нульовий сигнал. На керуючий вхід 33 мультиплексора 14 подається одиничний сигнал з входу 13 керування пристрою, що дозволяє проходження даних з інформаційних входів 8 групи комірки 1i. j через мультиплексор 14 на інформаційні входи 34 регістра 17. Так виконується запис даних у комірку 1i. j по її інформаційних входа х 8 гр упи. Для визначення мінімального значення серед двох операндів один з операндів подається з інформаційних виходів регістра 17 на інформаційні входи 26 мініматора 16, на інформаційні входи 28 якого подається інший операнд з інформаційних входів 4 групи комірки 1i. j . Результат, тобто мінімальне значення одного з двох операндів, з інформаційних виходів мініматора 16 подається на входи 29 мультиплексора 20, на керуючий вхід якого подається сигнал з входу 9i заборони пристрою. Якщо цей сигнал нульовий, то дані з інформаційних входів 29 мультиплексора 20 записуються в регістр 18, з інформаційних виходів якого подаються на інформаційнівиходи 2 групи комірки 1i. j . Для формування різниці двох операндів задіяно АЛЕ 15, на інформаційні входи 25 якого подається перший операнд, який знаходиться в регістрі 17 комірки 1i. j , а на його інформаційні входи 31 подається другий операнд з виходу (q+1)- вхідного елемента I 19. Другий операнд подається на q входи 30 (q+1)- вхідного елемента І 19 з інформаційних входів 5 групи комірки 1i. j за умови, що на (q+1)-й інверсний вхід елемента І 19 подається 9 нульовий сигнал з входу i заборони пристрою. Результат, тобто різниця двох операндів з інформаційних виходів АЛЕ 15 подається на інформаційні входи 32 мультиплексора 14 і записується по інформаційних входах 34 у регістр 17 за умови, якщо на обох керуючих входах 33 і 35 мультиплексора 14 присутні нульові сигнали. Транспозиція між сусідніми комірками 1i. j та ( ) 1i. j +1 j = 1, n - 1 відбувається тоді, коли у комірці 1i. j дані дорівнюють нулю, а у комірці 1i. j +1 - не дорівнюють нулю. У цьому випадку у блоці 21 налаштування на виході q-вхідного елемента АБО-НІ 23 1 комірки i. j формується одиничний сигнал, який подається на D- вхід D-тригера 22 і встановлює його в одиничний стан. В результаті одиничний сигнал з прямого виходу D-тригера 22 блока 21 налаштування, будучи поданий на керуючий вхід 35 мультиплексора 14, дозволяє проходження 11 36458 12 Розглянемо приклад реалізації класифікації nвимірного образу у вигляді векторних масивів чисел на однорідній структурі (Фіг.1). Нехай маємо через нього даних з комірки 1i. j +1 , що подаються на інформаційні входи 11 групи комірки 1i. j , на ( входи 34 регістра 17 комірки 1i. j . Після цього одиничний сигнал з прямого виходу D-тригера 22 проходить через елемент 24 затримки блока 21 налаштування, з'являється на вході 6 скиду комірки 1i. j і, будучи поданий з певною затримкою на вхід ) чотири i = 1,4 масиви чисел A 0 за кількістю класів i класифікації образів, кожний з яких містить по чо ( ) тири j = 1,4 числа a0j за кількістю елементів у i, вхідному векторному масиві даних, тобто 0 A1 = (25 16 12 8 ), 7 скиду комірки 1i. j +1 , викликає обнуління її регістра 17, оскільки подається на його вхід скиду. Для передачі даних з комірки 1i. j +1 використовуються інформаційні виходи 10 групи, які з'єднані з виходами регістра 17 цієї комірки. Таким чином виконується просування праворуч на одну позицію нульових значень даних, тобто обмін даними між сусідніми комірками 1i. j та 1i. j +1 у і-му рядку однорідної структури. Виключення з оброблення комірки 1i. j у і-му рядку однорідної структури виконується за наявністю одиничного сигналу на її вході 9i заборони пристрою, що приводить до заборони подання даних з інформаційних входів 5 групи комірки 1i. j через (q+1)- вхідний елемент І 19 на входи 31 АЛЕ 15, а також дозволяє проходження даних безпосередньо з інформаційних входів 4 групи комірки 1i. j через входи 27 мультиплексора 20 на входи регістра 18, а далі на інформаційні виходи 2 групи комірки 1i. j . A 0 = (14 9 6 20 ), 2 A 0 = (10 22 31 5), 3 A 0 = (13 7 21 29 ), 4 які складають початкову двовимірну матрицю вигляду æ 25 16 12 8 ö ç ÷ ç 14 9 6 20 ÷ 0 A =ç ÷ . (9) ç 10 22 31 5 ÷ ç 13 7 21 29 ÷ è ø Результати оброблення матриці A 0 (9) по циклах представлено у вигляді таблиці 1. Отже, максимальним за сумою своїх елементів є масив A 0 , тобто вхідний образ належить до 4 четвертого класу образів за даною класифікацією, а кількість циклів оброблення, виконаних в процесі пошуку цього максимуму, дорівнює 8. Таблиця 1 Цикл/Операції 1 1/1 1/2 1/3 2/1 2/2 Дія 2 Формування рядка мінелементів (пошук мінімального елемента стовпця). Формування різницевого зрізу у вигляді невпорядкованої матриці (віднімання мінелементів у кожному стовпці матриці). Формування впорядкованої матриці (транспозиція елементів у рядках з просуванням нульових елементів праворуч). Формування рядка мінелементів. Формування невпорядкованої матриці. Результат (числова матриця або вектор) і коментар 3 Min = (10 7 6 5) 0 æ 25 - 10 16 - 7 12 - 6 8 - 5 ö æ15 9 6 3 ö ç ÷ ç ÷ 1 ç 14 - 10 9 - 7 6 - 6 20 - 5 ÷ ç 4 2 0 15 ÷ A =ç =ç ÷ ÷ ç 10 - 10 22 - 7 31 - 6 5 - 5 ÷ ç 0 15 25 0 ÷ ç 13 - 10 7 - 7 21 - 6 29 - 5 ÷ ç 3 0 15 24÷ è ø è ø æ 15 9 6 ç ç 4 2 15 A1 = ç ç 15 25 0 ç 3 15 24 è Min = (3 2 1 3ö ÷ 0÷ 0÷ ÷ 0÷ ø 0 0) æ 15 - 3 9 - 2 6 3 ö æ 12 7 6 ç ÷ ç ç 4 - 3 2 - 2 15 0 ÷ ç 1 0 15 A =ç ÷ =ç ç 15 - 3 25 - 2 0 0 ÷ ç 12 23 0 ç 3 - 3 15 - 2 24 0 ÷ ç 0 13 24 è ø è 2 3ö ÷ 0÷ 0÷ ÷ 0÷ ø 13 36458 14 2/3 Формування впорядкованої матриці. æ 12 7 6 3ö ç ÷ ç 1 15 0 0÷ A2 = ç ÷ ç 12 23 0 0÷ ç 13 24 0 0÷ è ø 3/1 Формування рядка мінелементів. Min = (1 7 0 0 ) 3/2 Формування невпорядкованої матриці. 2 æ 12 - 1 7 - 7 ç ç 1 - 1 15 - 7 A =ç ç 12 - 1 23 - 7 ç 13 - 1 24 - 7 è 3 6 3 ö æ 11 0 6 ÷ ç 0 0÷ ç 0 8 0 = 0 0 ÷ ç 11 16 0 ÷ ç 0 0 ÷ ç 12 17 0 ø è 3/3 Формування впорядкованої матриці. æ 11 6 3 ç ç8 0 0 A3 = ç ç 11 16 0 ç 12 17 0 è 4/1 Формування рядка мінелементів. 3ö ÷ 0÷ 0÷ ÷ 0÷ ø Min = (8 0 0 0 ) 4/2 Формування невпорядкованої матриці. 0ö ÷ 0÷ 0÷ ÷ 0÷ ø 3 æ 11 - 8 6 3 0 ö æ 3 6 3 0ö ç ÷ ç ÷ ç 8 - 8 0 0 0 ÷ ç 0 0 0 0÷ A =ç = - мінімальний масив A 0 2 11 - 8 16 0 0 ÷ ç 3 16 0 0÷ ç ÷ ç ÷ ç 12 - 8 17 0 0 ÷ ç 4 17 0 0÷ è ø è ø Отримано перший нульовий рядок двовимірної матриці, який вказує на те, що масив чисел A 0 є мінімальним серед масивів 2 0 A1 , A 0 , A 0 , A 0 . Цей рядок виключають з подальшого оброблення. 2 3 4 4/3 Формування впорядкованої матриці. æ3 6 3 ç ç- - A4 = ç ç 3 16 0 ç 4 17 0 è 5/1 Формування рядка мінелементів. Min = (3 6 0 0) 5/2 Формування невпорядкованої матриці. 0ö ÷ -÷ 0÷ ÷ 0÷ ø 4 æ3-3 6 -6 ç ç A =ç ç 3 - 3 16 - 6 ç 4 - 3 17 - 6 è 5 3 0ö æ 0 0 3 ÷ ç - -÷ ç - - = 0 0 ÷ ç 0 10 0 ÷ ç 0 0 ÷ ç 1 11 0 ø è 5/3 Формування впорядкованої матриці. æ3 0 ç ç- A5 = ç ç10 0 ç 1 11 è 6/1 Формування рядка мінелементів. Min = (1 0 0 0 ) 6/2 Формування невпорядкованої матриці. 6/3 Формування впорядкованої матриці. 7/1 Формування рядка мінелементів. 0ö ÷ -÷ 0÷ ÷ 0÷ ø 0 0ö ÷ - -÷ 0 0÷ ÷ 0 0÷ ø 5 æ 3 -1 ç ç A =ç ç10 - 1 ç 1 -1 è 6 0 0ö æ 2 0 ÷ ç - - -÷ ç- = 0 0 0÷ ç 9 0 ÷ ç 11 0 0 ÷ ç 0 11 ø è æ 2 0 0 0ö ç ÷ ç - - - -÷ A6 = ç ÷ ç 9 0 0 0÷ ç11 0 0 0 ÷ è ø 0 Min = (2 0 0 0) 6 0 0ö ÷ - -÷ 0 0÷ ÷ 0 0÷ ø 15 7/2 36458 æ 2 - 2 0 0 0ö æ 0 0 0 0 ö ç ÷ ç ÷ 7 - - -÷ ç - - - - ÷ ç 0 A =ç =ç - наступний мінімум A1 9 - 2 0 0 0÷ ç 7 0 0 0 ÷ ç ÷ ÷ Формування невпоç 11 - 2 0 0 0 ÷ ç 9 0 0 0 ÷ è ø è ø рядкованої матриці. Отримано наступний нульовий рядок двовимірної матриці, який вказує 7/3 Формування впорядкованої матриці. 8/1 0 0 на те, що масив чисел A1 є мінімальним серед масивів A1 , A 0 , A 0 . 3 4 Цей рядок виключають з подальшого оброблення. æ- - - -ö ç ÷ ç- - - -÷ A7 = ç ÷ ç7 0 0 0÷ ç9 0 0 0÷ è ø Формування рядка мінелементів. 8/2 16 Формування невпорядкованої матриці. Min = (7 0 0 0 ) 7 - - -ö æ- - æ ç ÷ ç - - -÷ ç- - ç A =ç ÷=ç ç 7 - 7 0 0 0÷ ç 0 0 0 ç 9 - 7 0 0 0÷ ç 2 0 0 è ø è Отримано наступний нульовий рядок -ö ÷ -÷ - наступний мінімум A 0 . 3 0÷ ÷ 0÷ ø двовимірної матриці, який вказує на те, що масив чисел A 0 є мінімальним серед масивів A 0, A 0 . Цей 3 3 4 рядок виключають з подальшого оброблення. В подальшому вже немає необхідності виконувати зсув н ульових елементів праворуч, оскільки залишився лише один рядок з ненульовим елементом . Цей рядок вказує на те, що масив чисел A 0 є максимальним серед масивів 4 0 A1 , A 0 , A 0 , A 0 . 2 3 4 Для виконання наведеної класифікації n- вимірних образів за m класами комірки однорідної структури забезпечують реалізацію таких операцій, як паралельний запис даних у кожну комірку, транзит даних через комірки по стовпцях однорідної структури, визначення мінімального елемента та віднімання його у комірках у кожному стовпці однорідної структури, транспозиція даних з просуванням праворуч нульових значень даних між сусідніми комірками у кожному рядку однорідної структури. 17 Комп’ютерна в ерстка Д. Шев ерун 36458 Підписне 18 Тираж 28 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601