Сортувальна нейромережа

1. Сортувальна нейромережа, яка містить обчислювальну частину, що складається з двох блоків, причому другі входи першого блока обчислювальної частини з'єднані з входами початкових установчих значень пристрою, виходи першого блока обчислювальної частини з'єднані з входами її другого блока, які є входами вектора підстановки, інформаційні входи другого блока обчислювальної частини з'єднані з входами початкового вектора даних пристрою, яка відрізняється тим, що містить настроювану частину, яка складається з селектора кодів і аналізатора реакцій, інформаційні входи селектора кодів з'єднані з входами початкового вектора даних пристрою, а його виходи з'єднані з інформаційними входами аналізатора реакцій, виходи якого з'єднані з першими входами першого блока обчислювальної частини, який містить комутатор та пам'ять рангів, причому виходи матриці ваги першого блока обчислювальної частини підключені до адресних входів його комутатора та адресних входів селектора кодів настроюваної частини, інформаційні входи комутатора та пам'яті рангів є відповідно першими і другими входами першого блока обчислювальної частини, а виходи комутатора з'єднані попарно з входами інкремента/декремента пам'яті рангів, вхід скиду пристрою підключений до відповідних входів пам'яті рангів першого блока обчислювальної частини і аналізатора реакцій настроюваної частини, який також підключений до шини тактових імпульсів та входів керування відповідно непарними і парними циклами сортування пристрою, останні з'єднані також з відповідними входами комутатора першого блока обчислювальної частини, аналіза 2 (19) 1 3 20360 Корисна модель відноситься до обчислювальної техніки і може бути використана для сортування великих масивів даних. Відома систолічна матриця розміром n´n [Зарубежная радиоэлектроника, 1987, №7, с.16, рис.86], де n - кількість елементів сортування, яка складається з простих комірок порівняння, обміну та затримки і реалізує алгоритм сортування послідовності n чисел за n кроків, причому на кожному непарному кроці всі непарні елементи послідовності порівнюють зі своїми сусідніми парними елементами і міняють місцями, якщо попередній непарний елемент більше наступного парного елемента, а на кожному парному кроці всі парні елементи послідовності порівнюють зі своїми сусідніми непарними елементами і міняють місцями, якщо попередній парний елемент більше наступного непарного елемента. Недоліком даної систолічної матриці є апаратні витрати, оскільки використовується матриця розміром n´n комірок. Відома систолічна матриця розміром n´(n/2) [Вишенчук Й.М., Черкасский Н.В. Алгоритмические операционные устройства и суперЭВМ. - К.: Техника, 1990, с.129, рис.3.43д], де n - кількість елементів сортування, кожна комірка якої містить по два регістри на вході та виході елемента, схему порівняння двох багаторозрядних чисел і дві схеми І-АБО, причому кожні дві сусідні комірки ряду з'єднані між собою і зміщені відносно пари комірок сусіднього нижчого ряду. Недоліком даної систолічної матриці є апаратні витрати, оскільки використовується матриця розміром n´(n/2) комірок. Найбільш близькою за технічною суттю є сортувальна нейромережа [Автометрия, 1993, №3, с.30, рис.3], що містить навчальну частину, входи якої з'єднані з входами початкового вектора даних, та обчислювальну частину, що складається з двох блоків, причому ви ходи навчальної частини з'єднані з першими входами першого блока обчислювальної частини, другі входи першого блока якої з'єднані з входами початкових установчи х значень пристрою, виходи першого блока обчислювальної частини з'єднані з входами її другого блока, які є входами вектора підстановки, а також підключені до други х входів першого блока, інформаційні входи другого блока обчислювальної частини з'єднані з входами початкового вектора даних, а його інформаційні виходи є ви ходами відсортованого вектора даних пристрою. Недоліком даної сортувальної нейромережі є значні апаратні витрати, які складають O(n2) елементів, де n - розмірність вхідного вектора даних. В основу корисної моделі поставлена задача створення сортувальної нейромережі, в якій за рахунок введення нових вузлів та нових зв'язків між ними досягається можливість зменшення апаратних витрат. Поставлена задача вирішується тим, що у сортувальну нейромережу, яка містить обчислювальну частину, що складається з двох блоків, причому другі входи першого блока обчислювальної частини з'єднані з входами початкових установчих значень пристрою, виходи першого блока обчис 4 лювальної частини з'єднані з входами її другого блока, які є входами вектора підстановки, інформаційні входи друго го блока обчислювальної частини з'єднані з входами початкового вектора даних пристрою, введена налаштовувальна частина, яка складається з селектора кодів і аналізатора реакцій, інформаційні входи селектора кодів з'єднані з входами початкового вектора даних пристрою, а його виходи з'єднані з інформаційними входами аналізатора реакцій, виходи якого з'єднані з першими входами першого блока обчислювальної частини, який містить комутатор та пам'ять рангів, причому виходи матриці ваги першого блока обчислювальної частини підключені до адресних входів його комутатора та адресних входів селектора кодів налаштовувальної частини, інформаційні входи комутатора та пам'яті рангів є відповідно першими і другими входами першого блока обчислювальної частини, а виходи комутатора з'єднані попарно з входами інкремента/декремента пам'яті рангів, вхід скиду пристрою підключений до відповідних входів пам'яті рангів першого блока обчислювальної частини і аналізатора реакцій налаштовувальної частини, який також підключений до шини тактових імпульсів та входів керування відповідно непарними і парними циклами сортування пристрою, останні з'єднані також з відповідними входами комутатора першого блока обчислювальної частини, аналізатор реакцій налаштовувальної частини має вихід сигналу "Кінець" пристрою, який підключений до входу дозволу зчитування другого блока обчислювальної частини, інформаційні виходи якого є виходами елемента відсортованого вектора даних пристрою. На Фіг.1 представлена структурна схема сортувальної нейромережі, на Фіг.2 - функціональна схема аналізатора реакцій, на Фіг.3 - функціональна схема селектора кодів, на Фіг.4 - функціональна схема другого блока обчислювальної частини, на Фіг.5 - приклад сортування послідовності чисел (19 35 12 0 49 27) з ранжуванням. Сортувальна нейромережа (Фіг.1) містить налаштовувальну частину 1, яка складається з селектора кодів 2 та аналізатора реакцій 3, та обчислювальну частину 4, яка складається з блоків 5 і 6. Інформаційні входи 71,... ,7 n селектора кодів 2, де n - розмірність вхідного вектора даних, з'єднані з входами 81,...,8n початкового вектора даних пристрою, виходи селектора кодів 2 з'єднані з інформаційними входами 9і,...,9п аналізатора реакцій З, виходи 101,...,10K якого, де К=]n/2[ - кількість пар елементів, які порівнюють, з'єднані з входами 111,...,11K блока 5 обчислювальної частини 4, який містить комутатор 12 та пам'ять рангів 13. Вихід аналізатора реакцій 3, який підключений до входу дозволу зчитування блока 6 обчислювальної частини 4, є виходом 14 сигналу "Кінець" пристрою, а інформаційні входи пам'яті рангів 13 блока 5 обчислювальної частини 4 з'єднані з входами 1511,...,15nn початкових установчи х значень пристрою, інформаційні входи 161,...,16n блока 6 обчислювальної частини 4 з'єднані з входами 8 1,...,8n початкового вектора даних пристрою, а його інформаційні виходи є ви ходами 171,...,17m елемента 5 20360 6 відсортованого вектора даних пристрою, де m версного виходу D-тригера 43. Перший вхід елерозрядність елементів вхідного вектора даних. ментів АБО 41 і 42 підключений відповідно до Виходи 1811,...,18 nn матриці ваги пам'яті рангів прямого виходу D-тригерів 43 і 44, а другий вхід 13 блока 5 обчислювальної частини 4 підключені підключений до виходу елементів І 39 і 40 відповідо адресних входів 1911,...,19 nn блока 5, які є адредно, R-вхід D-тригерів 43, 44 і 45 підключений до сними входами його комутатора 12, і до адресних входу 23 скиду пристрою, С-вхід D-тригерів 43 і 44 входів 2011,..., 20 nn селектора кодів 2 налаштовупідключений до шини 24 тактових імпульсів. D-вхід вальної частини 1, а виходи 211,..., 21n підключені D-тригерів 43 і 44 з'єднаний відповідно з виходом до входів вектора підстановки блока 6 обчислюваелемента АБО 41 і 42, D-вхід D-тригера 45 підклюльної частини 4. Крім того, виходи комутатора 12 чений до прямого виходу D-тригера 44, прямий з'єднані попарно з входами 221,...,222n інкременвихід D-тригера 45 з'єднаний з виходом 10k k-гo та/декремента пам'яті рангів 13 блока 5 обчислюблока порівняння 27k. Крім того, вхід елемента вальної частини 4, вхід скиду якого підключений затримки 46 підключений до шини 24 тактових до відповідного входу аналізатора реакцій 3 наімпульсів, а вихід підключений до С-входу Dлаштовувальної частини 1 і до входу 23 скиду притригера 45 елемента порівняння 30 всіх блоків строю, шина 24 тактових імпульсів та входи 25, 26 порівняння 271, ..., 27k, входи елемента АБО-НІ 47 керування відповідно непарними і парними циклаз'єднані з виходами 10k всіх блоків порівняння 27 1, ми сортування пристрою підключені до відповідних ..., 27 k, а ви хід є ви ходом аналізатора реакцій 3 входів аналізатора реакцій 3 налаштовувальної налаштовувальної частини 1, який з'єднаний з частини 1, крім того, входи 25, 26 керування відповиходом 14 сигналу "Кінець" пристрою. відно непарними і парними циклами сортування Селектор кодів 2 налаштовувальної частини 1 пристрою з'єднані також з відповідними входами сортувальної нейромережі (Фіг.3) містить n шифкомутатора 12 блока 5 обчислювальної частини 4. раторів 481,..., 48n, n демультиплексорів 491, ..., 49 n Аналізатор реакцій 3 налаштовувальної часта n елементів АБО 501, .... 50n, причому mтини 1 сортувальної нейромережі (Фіг.2) містить К , розрядний інформаційний вхід 7і, i = 1 n , m - розблоків порівняння 271,..., 27 K, де K=]n/2[ - кількість рядність елементів вхідного вектора даних, селекпар елементів, які порівнюють, причому k-й блок тора кодів 2 налаштовувальної частини 1 підклю, чений до m-розрядного інформаційного входу порівняння 27k, де k = 1 K , складається з двох мультиплексорів 28, 29, елемента порівняння 30, демультиплексора 49і, його n-розрядний адресний трьох інформаційних входів 92k-1 , 92k, 92k+1 та ви ховхід 20і як рядок матриці ваги підключений до nду 10k. Мультиплексор 28 містить два елементи І розрядного інформаційного входу ши фратора 48i, 31 і 32, елемент АБО 33. Мультиплексор 29 міср-розрядний вихід якого підключений до адресного тить два елементи І 34 і 35, елемент АБО 36. Елевходу демультиплексора 49і, p=log2n. Крім того, j-й мент порівняння 30 містить два елементи НІ 37 і m-розрядний вихід демультиплексора 49і з'єдна38, два елементи І 39 і 40, два елементи АБО 41 і ний з відповідним входом елемента АБО 50j, 42, три D-тригера 43, 44 і 45. Крім того, аналізатоj = 1 n , m-розрядний вихід якого з'єднаний з інфо, ра реакцій 3 містить елемент затримки 46 і елермаційним входом 9, аналізатора реакцій 3 наламент АБО-НІ 47, вихід якого є виходом, який з'єдштовувальної частини 1. наний з виходом 14 сигналу "Кінець" пристрою. Блок 6 обчислювальної частини 4 (Фіг.4) місУ мультиплексорі 28 перший вхід елементів І тить n мультиплексорів 511, ...,51n та m елементів 31 і 32 з'єднаний відповідно з входом 92k-1 і 92k k-ro АБО 521, ..., 52m, де m - розрядність елементів блока порівняння 27k, другий вхід елемента І 31 вхідного вектора даних, причому т-розрядний інз'єднаний з входом 25 керування непарними циклами сортування пристрою, другий вхід елемента І формаційний вхід 16і, i = 1 n , блока 6 обчислюва, 32 з'єднаний з входом 26 керування парними цикльної частини 4 підключений до т-розрядного інлами сортування пристрою, виходи елементів I 31 формаційного входу мультиплексора 51i, його вхід і 32 з'єднані з входами елемента АБО 33, ви хід 21i і-го розряду вектора підстановки vj підключений якого є виходом мультиплексора 28. У мультипледо адресного входу м ультиплексора 51i, j = 1 n . , ксорі 29 перший вхід елементів І 34 і 35 з'єднаний Вхід дозволу м ультиплексорів 511, ..., 51n підклювідповідно з входом 92k і 92k+1 k-гo блока порівнянчений до виходу 14 сигналу "Кінець" пристрою, ня 27k, другий вхід елемента І 34 з'єднаний з вхоякий є входом дозволу зчитування блока 6 обчисдом 25 керування непарними циклами сортування лювальної частини 4, його (l+1)-й вихід підключепристрою, другий вхід елемента І 35 з'єднаний з ний до відповідного входу елемента АБО 52l+1, входом 26 керування парними циклами сортування пристрою, виходи елементів І 34 і 35 з'єднані з l = 0, m - 1 ви хід якого є виходом 17l+1 l-го розряду , входами елемента АБО 36, вихід якого є виходом j-го елемента XNj (l) відсортованого вектора даних мультиплексора 29. У елемента порівняння 30 пристрою. вихід мультиплексора 28 з'єднаний з входом елеСортувальна нейромережа (Фіг.1) функціонує мента НІ 37 і третім входом елемента І 40, вихід в такий спосіб. мультиплексора 29 з'єднаний з входом елемента На початку роботи на вхід 23 скиду пристрою НІ 38 і першим входом елемента І 39, вихід елеподається одиничний сигнал, який встановлює у ментів НІ 37 і 38 з'єднаний відповідно з другим початковий (нульовий) стан елементи пам'яті анавходом елементів І 39 і 40, третій вхід елемента І лізатора реакцій 3 налаштовувальної частини 1 і 39 підключений до інверсного виходу D-тригера пам'яті рангів 13 блока 5 обчислювальної частини 44, перший вхід елемента І 40 підключений до ін4. Перед сортуванням на інформаційні входи па 7 20360 8 м'яті рангів 13 блока 5 обчислювальної частини 4 сигналу "Кінець" пристрою. Якщо ця умова виконується і це не перший цикл, то процес сортування подається матриця розмірністю n´n, де n - розмірність вхідного вектора даних, з входів 1511 ,...,15nn закінчується; якщо ця умова не виконується, а також якщо це перший цикл, токомутатор 12 формує початкових установчих значень пристрою, яка явдва вектори: qt+={q1t+, ..., qnt+} і qt-={q1t-, ..., qnt-} виляє собою початкову матрицю ваги G0={g011, ..., 0 гляду: g nn}, виду 100... 0 ì qt + = q × G t - 1 p ï (4) 010... 0 í t0= t -1 , G , (1) ïq = q × Gp+ 1 ... î де Gt-1 - матриця ваги, яка формується у (t-1)-мy 000... 1 циклі сортування, крім початкової матриці ваги G0; тобто всім елементам вхідного вектора даних приqt+, qt- - вихідні вектори, які призводять відповідно строю присвоюються ранги, які відповідають нодо збільшення/зменшення на одиницю (або відпомерам їх позицій у векторі, наприклад, представвідно до інкремента/декремента) рангів елементів ляють натуральний ряд чисел, записаних в поточного вектора даних; р, р+1 - відповідно парні 0 одиничному позиційному коді (1). Вектор-рядки g i, та непарні стовпці матриці ваги. i = 1 n , матриці ваги G0 подаються на адресні вхо, Вихідні вектори qt+ і qt- комутатора 12 блока 5 обчислювальної частини 4 подаються на входи ди 2011,...,20nn селектора кодів 2 налаштовуваль221,...,222n інкремента/декремента пам'яті рангів 13 ної частини 1 і на адресні входи 1911,...,19 nn блока блока 5 обчислювальної частини 4, де за резуль5 обчислювальної частини 4 з виходів 18 11,...,18nn татом порівняння (3) у кожній парі елементів викоматриці ваги пам'яті рангів 13 блока 5 обчислюванують такі дії: льної частини 4. Одночасно на інформаційні входи а) якщо елемент молодшої позиції менший за 71,...,7n налаштовувальної частини 1 з входів значенням, ніж елемент старшої позиції у парі, то 81,...,8n початкового вектора даних пристрою подаранги елементів не змінюють; ється вхідний вектор даних виду х={х1, ..., xі, ..., xn}, б) якщо елемент молодшої позиції більший за i = 1 n . На вихода х селектора кодів 2 налаштову, значенням, ніж елемент старшої позиції у парі, то вальної частини 1 у t-му циклі оброблення формуранги змінюють таким чином: ранг елемента моється вихідний (поточний) вектор хt вигляду: лодшої позиції збільшують на одиницю, ранг елеt -1 t G (2) мента старшої позиції зменшують на одиницю. x ¬¾ ¾ x, t = 1 N, ¾ , Отже, на виходах 1811,...,18nn матриці ваги паде N - кількість циклів сортування. Формула (2) є м'яті рангів 13 блока обчислювальної частини 4 в аналітичною формою подання операції формурезультаті ітераційного процесу у t-му циклі форвання (вибірки) елементів хti поточного вектора хt з муються вектор-рядки матриці ваги Gt які знов поелементів вхідного вектора х за адресою, яку даються на адресні входи 2011,...,20nn селектора представляють вектор-рядки gіt-1 матриці ваги Gt-1 кодів 2 налаштовувальної частини 1 і адресні вхоу t-му циклі сортування. В аналізаторі реакцій 3 ди 1911,...,19nn комутатора 12 блока 5 обчислюваналаштовувальної частини 1 формується група льної частини 4 у всіх (t+1)-x циклах оброблення, t пар із сусідніх елементів поточного вектора х дакрім першого, оскільки тоді на цих входах були них незалежно від кількості n елементів вектора за зафіксовані вектор-рядки початкової матриці таким правилом: ваги G0 . а) у всіх непарних циклах кожна пара елеменПо закінченні процесу сортування (t=N), тобто тів складається з елементів (2k-1)-x і 2k-x позицій при наявності одиничного сигналу на виході 14 , пристрою з виходів 211,...,21n пам'яті рангів 13 на поточного вектора даних, де k = 1 K ; К=]n/2[ - кільвходи блока 6 обчислювальної частини 2 подаєтькість пар елементів, які порівнюють; б) у всіх парних циклах кожна пара елементів ся вектор підстановки vj={v1j, ...., vnj}, який є j-м вектор-стовпцем матриці ваги GN, значення одиниці складається з елементів 2k-x і (2k+1)-x позицій елемента vij якого відповідає адресі j-го елемента поточного вектора даних. у відсортованому векторі даних. На інформаційні Отже, вихідний вектор хt селектора кодів 2 навходи 161,...,16 n блока 6 обчислювальної частини лаштовувальної частини 1 подається на інформаційні входи 91,...,9 n аналізатора реакцій 3 налаш4, який є вихідним селектором кодів, подається вхідний вектор х даних, а на його інформаційному товувальної частини 1, який являє собою групу К виході 17 послідовно формуються т-розрядні елебінарних нейронів з пороговою функцією вигляду: ì 1, якщо x t менти вектора хN={x1N,...,хjN,..., хnN}. Отже, у блоці 6 > xt у непарних циклах i x t > x t у парних циклах , ï 2k -1 2k 2k 2k +1 qk = í (3) реалізується вибірка (формування) елементів хjN ï 0, якщо x t £ xt у непарних циклах i x t £ x t у парних циклах , î 2k -1 2k 2k 2k +1 результуючого вектора хN з елементів вхідного k = 1 K ; К=]n/2[ - кількість пар елементів, які , вектора х за адресою вектора підстановки vj, яку де представляють вектор-стовпці матриці ваги GN vij порівнюють. В результаті на виходах 101,...,10K аналізатора реакцій 3 налаштовувальної частини =gNij, виду 1 формується вектор зв'язків qt={q1t, ..., qKt}, який v (5) xN ¬¾j ¾ x, подається на інформаційні входи 111,..., 11K комуj татора 12 блока 5 обчислювальної частини 4. Одде vj=gNj; i, j = 1 n , i ¹ j. Таким чином виконується , ночасно, перевіряється умова відсутності будьякої зміни рангів у всіх парах елементів, про що зчитування елементів відсортованого вектора дасвідчить поява одиничного сигналу на виході 14 9 20360 10 них за зростанням числових значень його елеменІ 39 і 40 отримують відповідні добутки тів. x 2k - 1 l x2k,l bl + 1 та x 2k - 1l x 2k,l al+ 1 , які пода, , Аналізатор реакції 3 налаштовувальної частиються на вхід елементів АБО 41 і 42, на виході ни 1 сортувальної мережі (Фіг.2) функціонує в таяких отримують відповідні змінні а l (6) та bl (7). Ці кий спосіб. змінні записують у D-тригери 43 і 44 відповідно з На початку роботи одиничним сигналом з вхокожним тактовим імпульсом, що надходить з шини ду 23 скиду пристрою встановлюються у початко24 тактових імпульсів. вий (нульовий) стан D-тригери 43, 44 і 45 елеменАналогічні дії виконують у парних циклах сорта порівняння 30 кожного k-го блока порівняння тування для формування змінних аl (8) та bl (9). , 27k аналізатора реакцій 3, де k = 1 K , K=]n/2[ - кіПри наявності тактового імпульсу на виході лькість пар елементів, які порівнюють. Кожний елемента затримки 46, який подається на С-вхід блок порівняння 27k є бінарним нейроном, який D-тригера 45 елемента порівняння 30, на його випрацює за правилом (3). Порівняння починають зі ході отримують значення порогової функції qk (3) t старших розрядів кожного елемента хi поточного після порівняння останнього 0-го розряду відповівектора хt даних, які розглядають як відповідні дних елементів вектора х даних. операнди. Оскільки у кожному циклі в аналізаторі В якості початкових значень одиничним сигнареакцій 3 виконують однотипні операції, то в подалом на вході 23 скиду пристрою задають а m=bm=0, льшому в аналітичних формулах в цьому випадку оскільки встановлюють у нульовий стан D-тригери доцільно відмовитись від індексу t. 43 і 44 елементів порівняння 30. Нехай x2k-1,m-1=1, Мультиплексори 28 і 29 блока порівняння 27k x2k,m-1=0. В цьому випадку з формул (6), (7) для формують пару операндів, які порівнюють. В ненепарних циклів сортування випливає, що для всіх парному циклі, тобто при наявності одиничного l £ m - 1 аl=0, bl=1 і на виході 10k блока порівняння сигналу на вході 25 керування непарними циклами 27k отримують значення порогової функції qk=1 за сортування пристрою, однойменні l-ті розряди виразом (3). Якщо, навпаки, x2k-1,m-1=0, x2k,m-1=1, то елементів x2k- 1,l та x2k,l вектора х даних подаються для всіх l £ m - 1 виконується умова al=1, bl=0, і на на входи відповідно елементів I 31 і 34 та з'являвиході 10k блока порівняння 27k отримують знаються на виходах елементів АБО 33 і 36 мультичення порогової функції qk=0 за виразом (3). Може плексорів 28 і 29 відповідно. У парному циклі, тобвиявитись, що x2k-1,m-1=x2k,m-1=0 або x2k-1,m-1=x2k,mто при наявності одиничного сигналу на вході 26 1=1, тоді а l=b l=0 і порівняння операндів потрібно керування парними циклами сортування пристрою, подовжити, аналізуючи молодші розряди. Аналогіоднойменні l-ті розряди елементів x2k,l та x2k+1,l векчні дії повторюють з розрядами x2k-1,m-2 i x2k,m-2 і тора х даних подаються на входи відповідно елет.д., поки в результаті порівняння наймолодших ментів І 32 і 35 та з'являються на виходах відповірозрядів не будуть обчислені значення а 0 і b0. Якдно елементів АБО 33 і 36 мультиплексорів 28 і 29 що а0=1, b0=0, то x2k-1 >x2k, і на виході 10k блока відповідно. порівняння 27k отримують значення порогової фуКрім l-тих розрядів операндів х2k-1,l, x2k,l та нкції qk=1, при а0=0, b0=1, a0=b0=1 або а0=b0=0 на x2k+ 1,l, які подаються на інформаційні входи 92k-1, виході 10k отримують значення порогової функції 92k та 92k+1 блока 27k, в порівнянні операндів приqk=0 з урахуванням виразу (3). ймають участь дві допоміжні змінні аl та bl відповіАналогічні дії виконують у парних циклах сордно, значення яких обчислюються за допомогою тування. рекурентних співвідношень: Елемент АБО-НІ 47 аналізатора реакцій 3 наа) для непарних циклів сортування лаштовувальної частини 1, вихід якого є виходом (6) a l = al + 1 Ú x2 k -1,l x2k,l bl + 1 , 14 сигналу "Кінець" пристрою, формує одиничний сигнал, якщо значення всіх порогових функцій (7) b l = b l+1 Ú (x 2k -1,l x 2k ,l al+1 ), qk=0, що є ознакою закінчення процесу сортуванб) для парних циклів сортування ня. Селектор кодів 2 налаштовувальної частини 1 (8) a l = al + 1 Ú x2k,l x2k + 1 l bl + 1 , , сортувальної мережі (Фіг.3) функціонує в такий спосіб. (9) bl = bl+ 1 Ú x2k,l x 2k + 1l al+ 1 , , На m-розрядні інформаційні входи 71, ..., 7n де l = m - 10 , m - кількість розрядів операндів; аl+1 , селектора кодів 2 налаштовувальної частини 1, які значення змінної з порівняння попереднього (l+1)підключені відповідно до т-розрядних інформаційго розряду, що зберігається в D-тригері 43 елемених входів демультиплексорів 491, ..., 49n, поданта порівняння 30; bl+1 - значення змінної з порівється вхідний вектор х даних. На адресні входи няння попереднього (l+1)-го розряду, що зберіга2011, ..., 20nn селектора кодів 2, які підключені відповідно до n-розрядних інформаційних входів шиється в D-тригері 44 елемента порівняння 30 кожного блока порівняння 27k. фраторів 481, ..., 48n, подаються вектор-рядки git-1, t-1 У непарному циклі на входи елементів НІ 37 і i = 1, n , матриці ваги G , яка формується у (t-1)-мy 38 елемента порівняння 30 кожного блока порівциклі сортування, крім початкової матриці ваги G0. няння 27k подаються відповідно l-ті однойменні Кожен шифратор 48i, i = 1 n , перетворює вектор, розряди елементів x2k-1,l та x2k,l вектора х даних, на рядок git-1 матриці ваги Gt-1, який представлено в виходах яких отримують відповідно їхні інверсні одиничному позиційному коді, в його р-розрядний значення x2k -1,l та x2k,l , які подаються на вхід двійковий код, p=log 2n, і подає його значення на відповідно елементів І 39 і 40. На виході елементів адресний вхід демультиплексора 49і. Демульти ( ( ) ( ( ) ) ) ( ) 11 20360 12 плексор 49і комутує на свій j-й вихід значення і-го порівнюють, - ознака збільшення/зменшення елемента вхідного вектора х даних, ранг git-1 якого (інкремента/декремента) відповідних рангів еледорівнює величині j, j = 1 n , яке потім подається , ментів. Масив рангів елементів складається з діана вхід елемента АБО 50j. Таким чином, на вихопазону цілих додатних чисел від 1 до 6 (вони помідах 91, .... 9n селектора кодів 2 налаштовувальної чені в дужках біля кожного елемента вектора частини 1, які є виходами елементів АБО 501, ..., даних). В процесі сортування виконується один t t t t 50n, формується вектор x = {x1 ,...,xj ,..., xn }, тобто контрольний (п'ятий) цикл. Отже, кількість N циклів виконується зчитування елементів вхідного вектосортування складає N=O(n), оскільки N=n-1. ра х даних відповідно до їх рангів. Доведемо можливість застосування одного Блок 6 обчислювальної частини 4 сортувальконтрольного циклу. ної нейромережі (Фіг.4) функціонує в такий спосіб. Нехай s-й цикл був останній, в якому виконуНа m-розрядні інформаційні входи 161,...,16n вались зміни рангів елементів у парах. Але, якщо у блока 6 обчислювальної частини 4, які підключені (s+1)-му циклі не відбувається жодної зміни рангів відповідно до інформаційних входів мультиплекелементів у парах, то можна стверджувати, що у сорів 511, ..., 51 n, подається вхідний вектор х да(s+2)-му циклі також не буде зміни рангів елеменних. На входи 211,...,21n вектора підстановки блока тів, оскільки будуть порівнюватись елементи в 6 обчислювальної частини 4, які підключені відпопарах, які вже впорядковані у s-му циклі. Ці міркувідно до адресних входів мультиплексорів 511, .... вання стосуються всіх циклів, окрім першого. При N 51n, подається вектор підстановки vj=gj . При навідсутності зміни рангів елементів у першому циклі явності одиничного сигналу на вході 21 і вектора необхідно виконати ще один цикл для контролю. підстановки та на виході 14 сигналу "Кінець" приЗапропонована сортувальна нейромережа дострою, який є сигналом дозволу зчитування блока зволяє зменшити апаратні витрати на сортування 6 і підключений до входу дозволу мультиплексора чисел як елементів вхідного вектора даних за ра51і, l-й розряд елемента хі вхідного вектора х дахунок ранжування елементів послідовності, що приводить в процесі попарного перегляду до зміни них подається з (l+1)-го виходу, l = 0, m - 1 де m , значень рангів елементів на одиницю замість перозрядність елементів вхідного вектора даних, реміщення (транспозиції) елементів у парах, яке мультиплексора 51i на вхід елемента АБО 52l+1, потребує додаткової комірки пам'яті для кожної вихід якого є виходом 17l+1 l-го розряду j-го елемепари елементів, що переміщують. Крім того, апанта відсортованого вектора даних пристрою. Таратна складність налаштовувальної та обчислюким чином, елемент хі вхідного вектора х даних, в N вальної частин сортувальної нейромережі дорівмолодшому розряді рангу gij якого присутня одинює O(n) елементів, де п - кількість елементів ниця, тобто ранг якого giN є найменшим за значенвхідного вектора даних пристрою, в той час як ням, найпершим з'явиться на виходах 171, ..., 17m апаратна складність блоків відомої сортувальної елемента відсортованого вектора даних пристрою. мережі - прототипу дорівнює O(n2) елементів. В Приклад сортування послідовності чисел (19 якості значень рангів елементів може використо35 12 0 49 27), які є елементами вхідного вектора вуватися не тільки послідовність чисел від 1 до n даних, показано на Фіг.5. Тут застосовано такі (натуральний ряд чисел), але й послідовність адумовні позначення: [ - ознака пари елементів, які реси цих елементів при їх записі у пам'ять. 13 Комп’ютерна в ерстка А. Рябко 20360 Підписне 14 Тираж 26 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601