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

1. Сортувальна нейромережа, яка містить обчислювальну частину, що складається з двох блоків, причому другі входи першого блока обчислювальної частини з'єднані з входами початкових установчих значень пристрою, виходи першого блока обчислювальної частини з'єднані з входами її другого блока, які є входами вектора підстановки, інформаційні входи другого блока обчислювальної частини з'єднані з входами початкового вектора даних пристрою, а його інформаційні виходи є ви ходами відсортованого вектора даних пристрою, яка відрізняється тим, що містить налаштовувальну частину, яка складається з селектора кодів і аналізатора реакцій, інформаційні входи селектора кодів з'єднані з входами початкового вектора даних пристрою, а його виходи з'єднані з інформаційними входами аналізатора реакцій, виходи якого з'єднані з першими входами першого блока обчислювальної частини, який містить комутатор та пам'ять рангів, причому ви ходи першого блока обчислювальної частини підключені до адресних входів його комутатора та адресних входів селектора кодів налаштовувальної частини, інформаційні входи комутатора та пам'яті рангів є відповідно першими і другими входами першого блока обчислювальної частини, а виходи комутатора з'єднані попарно з входами інкремента/декремента пам'яті рангів, вхід скидання пристрою підключений до відповідних входів пам'яті рангів першого блока обчислювальної частини і аналізатора реакцій налаштовувальної частини, який також підключений до шини тактових імпульсів та входів керування відповідно непарними і парними циклами сортування пристрою, останні з'єднані також з відповідними входами комутатора першого блока обчислювальної частини, аналізатор реакцій налаштовувальної частини має вихід сигналу "Кінець" пристрою, який підключений до входу дозволу зчитування другого блока обчислювальної частини. 2 (19) 1 3 19907 4 також підключений до відповідного входу елемені-й вхід вектора підстановки підключений до адрета АБО-НІ аналізатора реакцій, вихід якого є вихосного входу і-го демультиплексора, у якого j-й видом сигналу "Кінець" пристрою. хід з'єднаний з відповідним і-м входом j-го елемен3. Сортувальна нейромережа за п. 1, яка відрізта АБО, де j = 1 n , ви хід якого є j-м виходом , няється тим, що другий блок обчислювальної чавідсортованого вектора даних пристрою, а вхід стини містить n демультиплексорів та n елементів дозволу зчитування другого блока обчислювальної АБО, і-й інформаційний вхід, де i = 1 n , другого , частини підключений до входу дозволу всі х його блока обчислювальної частини підключений до демультиплексорів. інформаційного входу і-го демультиплексора, його Корисна модель відноситься до обчислювальної техніки і може бути використана для сортування великих масивів даних. Відома систолічна матриця розміром 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], що містить навчальну частину, входи якої з'єднані з входами початкового вектора даних пристрою, та обчислювальну частину, що складається з двох блоків, причому виходи навчальної частини з'єднані з першими входами першого блока обчислювальної частини, другі входи першого блока якої з'єднані з входами початкових установчих значень пристрою, виходи першого блока обчислювальної частини з'єднані з входами її другого блока, які є входами вектора підстановки, а також підключені до други х входів першого блока, інформаційні входи другого блока обчислювальної частини з'єднані з входами початкового вектора даних пристрою, а його інформаційні виходи є виходами відсортованого вектора даних пристрою. Недоліком даної сортувальної нейромережі є значні апаратні витрати, які складають n2 компараторів, n2 фотоприймачів, n електронних порогових елементів і два шари, що містять n2 комірок (каналів) і n2 фотоприймачів відповідно. В основу корисної моделі поставлена задача створення сортувальної нейромережі, в якій за рахунок введення нових вузлів та нових зв'язків між ними досягається можливість зменшення апаратних витрат. Поставлена задача вирішується тим, що у сортувальну нейромережу, яка містить обчислювальну частину, що складається з двох блоків, причому, другі входи першого блока обчислювальної частини з'єднані з входами початкових установчих значень пристрою, виходи першого блока обчислювальної частини з'єднані з входами її другого блока, які є входами вектора підстановки, інформаційні входи друго го блока обчислювальної частини з'єднані з входами початкового вектора даних пристрою, а його інформаційні виходи є ви ходами відсортованого вектора даних пристрою, введена налаштовувальна частина, яка складається з селектора кодів і аналізатора реакцій, інформаційні входи селектора кодів з'єднані з входами початкового вектора даних пристрою, а його виходи з'єднані з інформаційними входами аналізатора реакцій, виходи якого з'єднані з першими входами першого блока обчислювальної частини, який містить комутатор та пам'ять рангів, причому виходи першого блока обчислювальної частини підключені до адресних входів його комутатора та адресних входів селектора кодів налаштовувальної частини, інформаційні входи комутатора та пам'яті рангів є відповідно першими і другими входами першого блока обчислювальної частини, а виходи комутатора з'єднані попарно з входами інкремента/декремента пам'яті рангів, вхід скидування пристрою підключений до відповідних входів пам'яті рангів першого блока обчислювальної частини і аналізатора реакцій налаштовувальної частини, який також підключений до шини тактових імпульсів та входів керування відповідно непарними і парними циклами сортування пристрою, останні з'єднані також з відповідними входами комутатора першого блока обчислювальної частини, аналізатор реакцій налаштовувальної частини має вихід сигналу "Кінець" пристрою, який підключений до входу дозволу зчитування другого блока обчислювальної частини. На фіг.1 представлено структурну схему сор 5 19907 6 тувальної нейромережі, на фіг.2 - функціональну АБО 33, ви хід якого є виходом мультиплексора 28. схему аналізатора реакцій, на фіг.3 - функціональМультиплексор 29 містить два елементи І 34 і ну схему др угого блока обчислювальної частини, 35, елемент АБО 36, причому перший вхід елемена фіг.4 наведено приклад сортування послідовнтів І 34 і 35 з'єднаний відповідно з входом 9 2k і ності чисел (19 35 12 0 49 27) з ранжуванням. 92k+1 k-гo блока порівняння 27k, другий вхід елемеСортувальна нейромережа (фіг.1) містить нанта І 34 з'єднаний з входом 25 керування непарлаштовувальну частину 1, яка складається з селеними циклами сортування пристрою, другий вхід ктора кодів 2 та аналізатора реакцій 3, та обчиселемента І 35 з'єднаний з входом 26 керування лювальну частину 4, яка складається з блоків 5 і 6. парними циклами сортування пристрою, виходи Інформаційні входи 71,...,7n селектора кодів 2 з'єделементів І 34 і 35 з'єднані з входами елемента нані з входами 81,...,8n початкового вектора даних АБО 36, вихід якого є виходом мультиплексора 29. пристрою, виходи селектора кодів 2 з'єднані з інЕлемент порівняння 30 містить два елементи НІ формаційними входами 91,...,9n аналізатора реак37 і 38, два елементи І 39 і 40, два елементи АБО цій 3, виходи 101,...,10K якого, де K=]n/2[ - кількість 41 і 42, три D-тригера 43, 44 і 45, причому ви хід пар елементів, які порівнюють, з'єднані з входами мультиплексора 28 з'єднаний з входом елемента 111,...,11K блока 5 обчислювальної частини 4, який НІ 37 і третім входом елемента І 40, вихід мультимістить комутатор 12 та пам'ять рангів 13. Вихід плексора 29 з'єднаний з входом елемента НІ 38 і аналізатора реакцій 3, який підключений до входу першим входом елемента І 39. дозволу зчитування блока 6 обчислювальної часВихід елементів НІ 37 і 38 з'єднаний відповідно тини 4, є виходом 14 сигналу "Кінець" пристрою, а з другим входом елементів І 39 і 40, третій вхід інформаційні входи пам'яті рангів 13 блока 5 обчиелемента І 39 підключений до інверсного виходу слювальної частини 4 з'єднані з входами 151,...,15n D-тригера 44, перший вхід елемента І 40 підклюпочаткових установчих значень пристрою, інфорчений до інверсного виходу D-тригера 43. Перший маційні входи 161,...,16 n блока 6 обчислювальної вхід елементів АБО 41 і 42 підключений відповідно частини 4 з'єднані з входами 81,...,8n початкового до прямого виходу D-тригерів 43 і 44, а другий вхід вектора даних пристрою, а його інформаційні випідключений до виходу елементів І 39 і 40 відповіходи є виходами 171,...,171 відсортованого вектора дно, R-вхід D-тригерів 43, 44 і 45 підключений до даних пристрою. входу 23 скидування пристрою, С-вхід D-тригерів Виходи 181,...,18 n пам'яті рангів 13 блока 5 об43 і 44 підключений до шини 24 тактових імпульсів. числювальної частини 4 підключені до адресних D-вхід D-тригерів 43 і 44 з'єднаний відповідно з входів 191,...,19 n блока 5, які є адресними входами виходом елемента АБО 41 і 42, D-вхід D-тригера його комутатора 12, до адресних входів 201,...,20n 45 підключений до прямого виходу D-тригера 44, селектора кодів 2 налаштовувальної частини 1 і до прямий вихід D-тригера 45 з'єднаний з виходом входів 211,...,21 n вектора підстановки блока 6 об10k k-гo блока порівняння 27k. Крім того, аналізачислювальної частини 4. Крім того, виходи комутатор реакцій 3 містить елемент затримки 46, вхід тора 12 з'єднані попарно з входами 221,...,222n інякого підключений до шини 24 тактових імпульсів, кремента/декремента пам'яті рангів 13 блока 5 а вихід підключений до С-входу D-тригера 45 елеобчислювальної частини 4, вхід скидування якого мента порівняння 30 всіх блоків порівняння підключений до відповідного входу аналізатора 271,...,27K , та елемент АБО-НІ 47, входи якого з'єдреакцій 3 налаштовувальної частини 1 і до входу нані з виходами 10k всіх блоків порівняння 23 скидування пристрою, шина 24 тактових імпу271,...,27K , а вихід є виходом аналізатора реакцій 3 льсів та входи 25, 26 керування відповідно непарналаштовувальної частини 1, який з'єднаний з ними і парними циклами сортування пристрою виходом 14 сигналу "Кінець" пристрою. підключені до відповідних входів аналізатора реаБлок 6 обчислювальної частини 4 (фіг.3) міскцій 3 налаштовувальної частини 1, крім того, вхотить n демультиплексорів 481,...,48n та n елеменди 25, 26 керування відповідно непарними і партів АБО 491,...,49n. Ін формаційний вхід 16i, i = 1 n , , ними циклами сортування пристрою з'єднані також блока 6 обчислювальної частини 4 підключений до з відповідними входами комутатора 12 блока 5 інформаційного входу демультиплексора 48і, його обчислювальної частини 4. вхід 2 її вектора підстановки підключений до адреАналізатор реакцій 3 налаштовувальної чассного входу демультиплексора 48j, у якого j-й вихід тини 1 сортувальної нейромережі (фіг.2) містить К з'єднаний з відповідним входом елемента АБО 49j, блоків порівняння 271,...,27 K, де K=]n/2[ - кількість j = 1 n , вихід якого є виходом 17j відсортованого , пар елементів, які порівнюють, причому k-й блок вектора даних пристрою, а вхід дозволу кожного порівняння 27k, де k = 1 K , складається з двох , демультиплексора 48і з'єднаний з входом дозволу мультиплексорів 28, 29, елемента порівняння 30, зчитування блока 6, а отже, з виходом 14 сигналу трьох інформаційних входів 92k-1 , 92k, 92k+1 та ви хо"Кінець" пристрою. ду 10k. Мультиплексор 28 містить два елементи І Сортувальна нейромережа (фіг.1) функціонує 31 і 32, елемент АБО 33, причому перший вхід в такий спосіб. елементів І 31 і 32 з'єднаний відповідно з входом На початку роботи на вхід 23 скидування при92k-1 і 92k k-гo блока порівняння 27k, другий вхід строю подається одиничний сигнал, який встановелемента 131 з'єднаний з входом 25 керування лює у початковий (нульовий) стан елементи пам'я непарними циклами сортування пристрою, другий ті аналізатора реакцій 3 налаштовувальної вхід елемента І 32 з'єднаний з входом 26 керуванчастини 1 і пам'яті рангів 13 блока 5 обчислювальня парними циклами сортування пристрою, виходи ної частини 4. Перед сортуванням на інформаційні елементів 131 і 32 з'єднані з входами елемента входи пам'яті рангів 13 блока 5 обчислювальної 7 19907 8 частини 4 подається вектор розмірністю n з входів закінчується; якщо ця умова не виконується, а та151,...,15n початкових установчих значень прикож якщо це перший цикл, то комутатор 12 формує строю, який являє собою початковий вектор ваги два вектори: qt+={qt+1,…,qt+n} і qt-={qt-1,…,qt-n} вигля0 0 0 0 g ={g 1, ..., g i, ..., g n} виду ду: gt-1 t 1 (4) q (qt+, qt-) 2 t-1 де g - вектор ваги, який формується у t-му ... 0 циклі сортування; qt+, qt- - вихідні вектори, які при(1) g = ,i = 1 n , зводять відповідно до збільшення/зменшення на i одиницю (або відповідно до інкремен... та/декремента) рангів елементів поточного вектоn ра даних. тобто всім елементам вхідного вектора даних Вихідні вектори qt+ і qt- комутатора 12 блока 5 пристрою присвоюються ранги, які відповідають обчислювальної частини 4 подаються на входи номерам їх позицій у векторі, наприклад, предста221,...,222n інкремента/декремента пам'яті рангів 13 вляють натуральний ряд чисел (1). Вектор ваги g0 блока 5 обчислювальної частини 4, де за резульподається на адресні входи 201,...,20 n селектора татом порівняння (3) у кожній парі елементів викокодів 2 налаштовувальної частини 1 і на адресні нують такі дії: входи 191,...,19 n блока 5 обчислювальної частини 4 а) якщо елемент молодшої позиції менший за з виходів 181,...,18 n пам'яті рангів 13 блока 5 обчизначенням, ніж елемент старшої позиції у парі, то слювальної частини 4. Одночасно на інформаційні ранги елементів не змінюють; входи 71 ,...,7n налаштовувальної частини 1 з вхоб) якщо елемент молодшої позиції більший за дів 81,...,8n початкового вектора даних пристрою значенням, ніж елемент старшої позиції у парі, то подається вхідний вектор даних виду х={х1, ..., xi, ранги змінюють таким чином: ранг елемента мо..., xn}. На ви ходах селектора кодів 2 налаштовулодшої позиції збільшують на одиницю, ранг елевальної частини 1 у t-му циклі оброблення формумента старшої позиції зменшують на одиницю. t ється вихідний (поточний) вектор х вигляду: Отже, на виходах 181,...,18n пам'яті рангів 13 блока обчислювальної частини 4 в результаті ітеgt-1 (2) x раційного процесу у t-му циклі формується вектор xt , t = 1,N , ваги gt, який знов подається на адресні входи 201,...,20n селектора кодів 2 налаштовувальної де N - кількість циклів сортування; i = 1 N . Фо, частини 1 і адресні входи 191,...,19n комутатора 12 рмула (2) є аналітичною формою подання операції блока 5 обчислювальної частини 4 у всіх (t+l)-x формування (вибірки) елементів хti поточного векциклах оброблення, крім першого, оскільки тоді на тора хt з елементів вхідного вектора х за адресою цих входах був зафіксований початковий вектор gіt-1 вектора ваги gt-1 у t-му циклі сортування. В ваги g0. аналізаторі реакцій 3 налаштовувальної частини 1 По закінченні процесу сортування (t=N), тобто формується група пар із сусідніх елементів поточпри наявності одиничного сигналу на виході 14 ного вектора хt даних незалежно від кількості n пристрою на входи 211,...,21n блока 6 обчислюваелементів вектора за таким правилом: льної частини 2 подається вектор підстановки а) у всіх непарних циклах кожна пара елеменv={v1N ,...,vjN,...,vnN}, який є вектором ваги gN, знатів складається з елементів (2k-l)-x і 2k-x позицій чення j і-го елемента якого відповідає адресі j-го поточного вектора даних, де k = 1 K , K=]n/2[ - кіль, компонента у відсортованому векторі даних. На кість пар елементів, які порівнюють; інформаційні входи 161,...,16n блока 6 обчислюваб) у всіх парних циклах кожна пара елементів льної частини 4, який є вихідним селектором кодів, складається з елементів 2k-x і (2k+l)-x позицій поподається вхідний вектор х даних, а на його інфоточного вектора даних. рмаційних виходах 171,...,17 n формується вектор t Отже, вихідний вектор х селектора кодів 2 нахN={x1N,…,xjN,…xnN}. Отже, у блоці 6 реалізується лаштовувальної частини 1 подається на інформавибірка (формування) елементів хNj результуючого ційні входи 91,...,9 n аналізатора реакцій 3 налашвектора xN з елементів вхідного вектора х за адретовувальної частини 1, який являє собою групу К сою vi=gNi вектора підстановки v виду бінарних нейронів з пороговою функцією вигляду: V t t t (5) ì1, якщо x t xN ï x 2k -1 > x 2k у непарних циклах і x2k > x2 k +1 у парних циклах, qk = í (3) , t t t t ï2, якщо x2k -1 £ x2 k у непарних циклах і x 2k £ x 2k +1 у парних циклах, î де k = 1 K ; К=]n/2[ - кількість пар елементів, які , порівнюють. В результаті на виходах 101,...,10K аналізатора реакцій 3 налаштовувальної частини 1 формується вектор зв'язків q={q1t,...,qK t}, який подається на інформаційні входи 11і,...,11K комутатора 12 блока 5 обчислювальної частини 4. Одночасно, перевіряється умова відсутності будьякої зміни рангів у всіх парах елементів, про що свідчить поява одиничного сигналу на виході 14 сигналу "Кінець" пристрою. Якщо ця умова виконується і це не перший цикл, то процес сортування де v=gN; i, j = 1, n , i¹j. Таким чином виконується зчитування елементів відсортованого вектора даних за зростанням числових значень його елементів. Аналізатор реакцій 3 налаштовувальної частини 1 сортувальної нейромережі (фіг.2) функціонує в такий спосіб. На початку роботи одиничним сигналом з входу 23 скидування пристрою встановлюються у початковий (нульовий) стан D-тригери 43, 44 і 45 елемента порівняння 30 кожного k-го блока порів 9 19907 няння 27k аналізатора реакцій 3, де k = 1 K , , K=]n/2[ - кількість пар елементів, які порівнюють. Кожний блок порівняння 27k є бінарним нейроном, який працює за правилом (3). Порівняння починають зі старших розрядів кожного елемента xit поточного вектора хt даних, які розглядають як відповідні операнди. Оскільки у кожному циклі в аналізаторі реакцій 3 виконують однотипні операції, то в аналітичних формулах в цьому випадку доцільно відмовитись від індексу t. Мультиплексори 28 і 29 блока порівняння 27k формують пару операндів, які порівнюють. В непарному циклі, тобто при наявності одиничного сигналу на вході 25 керування непарними циклами сортування пристрою, однойменні l-ті розряди елементів x2k- 1,l та x2k,l вектора х даних подаються на входи відповідно елементів І 31 і 34 та з'являються на виходах елементів АБО 33 і 36 мультиплексорів 28 і 29 відповідно. У парному циклі, тобто при наявності одиничного сигналу на вході 26 керування парними циклами сортування пристрою, однойменні l-ті розряди елементів x2k,l та x2k+1,l вектора х даних подаються на входи відповідно елементів І 32 і 35 та з'являються на виходах відповідно елементів АБО 33 і 36 мультиплексорів 28 і 29 відповідно. Крім l-тих розрядів операндів x2k-1,l, x2k,l та x2k+ 1,l, які подаються на інформаційні входи 92k-1, 92k та 92k+1 блока 27k, в порівнянні операндів приймають участь дві допоміжні змінні аl та bl відповідно, значення яких обчислюються за допомогою рекурентних співвідношень: а) для непарних циклів сортування al = al +1 Ú ( x2k -1,l x 2k,l bl+1) , (6) bl = bl+1 Ú (x 2k-1,l x2k,l al +1) , б) для парних циклів сортування (7) al = al +1 Ú ( x 2k, l x2k +1,l bl +1) , (8) bl = al +1 Ú ( x2k,l x 2k +1,l al +1) , (9) де l = m - 1 0 , m - кількість розрядів операндів, , аl+1 - значення змінної з порівняння попереднього (l+1)-го розряду, що зберігається в D-тригері 43 елемента порівняння 30, bl+1 - значення змінної з порівняння попереднього (l+1)-го розряду, що зберігається в D-тригері 44 елемента порівняння 30кожного блока порівняння 27k. У непарному циклі на входи елементів НІ 37 і 38 елемента порівняння 30 кожного блока порівняння 27k подаються відповідно l-ті однойменні розряди елементів x2k-1,l та x2k,l вектора х даних, на виходах яких отримують відповідно їхні інверсні значення x2k -1, l та x2 k, l , які подаються на вхід відповідно елементів І 39 і 40. На виході елементів І 39 і 40 отримують відповідні добутки ( x2k -1,lx 2k,lbl+1 ) та ( x2k -1,l x2k,l al+1 ), які подаються на вхід елементів АБО 41 і 42, на виході яких отримують відповідні змінні al (6) та bl (7). Ці змінні записують у D-тригери 43 і 44 відповідно з кожним тактовим імпульсом, що надходить з шини 24 тактових імпульсів. 10 Аналогічні дії виконують у парних циклах сортування для формування змінних аl (8) та bl (9). При наявності тактового імпульсу на виході елемента затримки 46, який подається на С-вхід D-тригера 45 елемента порівняння 30, на його виході отримують значення порогової функції qk (3) після порівняння останнього 0-го розряду відповідних елементів вектора х даних. В якості початкових значень одиничним сигналом на вході 23 скидування пристрою задають аm=bm=0, оскільки встановлюють у нульовий стан D-тригери 43 і 44 елементів порівняння 30. Нехай x2k- 1,m- 1=1, x2k,m-1=0. В цьому випадку з формул (6), (7) для непарних циклів сортування випливає, що для всіх l£m-l al=0, bl=l і на виході 10k блока порівняння 27k отримують значення порогової функції qk=1 за виразом (3). Якщо, навпаки, x2k-1,m-1=0, x2k,m-1=1, то для всі х l£m-1 виконується умова аl=1, bl=0, і на виході 10k блока порівняння 27k отримують значення порогової функції qk=0 за виразом (3). Може виявитись, що x2k-1,m-1=x2k,m-1=0 або x2k1,m-1=x2k,m-1=l, тоді а l=b l=0 і порівняння операндів потрібно подовжити, аналізуючи молодші розряди. Аналогічні дії повторюють з розрядами x2k-1,m-2 і x2k,m-2 і т.д., поки в результаті порівняння наймолодших розрядів не будуть обчислені значення а 0 і b0. Якщо а0=1, b0=0, то x2k-1>x2k, і на виході 10k блока порівняння 27k отримують значення порогової функції qk=l, при а0=0, b0=l, a0=b0=1 або а0=b0=0 на виході 10k отримують значення порогової функції qk=0 з урахуванням виразу (3). Аналогічні дії виконують у парних циклах сортування. Елемент АБО-НІ 47 аналізатора реакцій 3 налаштовувальної частини 1, вихід якого є виходом 14 сигналу "Кінець" пристрою, формує одиничний сигнал, якщо значення всіх порогових функцій qk=0, що є ознакою закінчення процесу сортування. Блок 6 обчислювальної частини 4 сортувальної нейромережі (фіг.3) функціонує в такий спосіб. На інформаційні входи 161,...,16n блока 6 обчислювальної частини 4, які підключені відповідно до інформаційних входів демультиплексорів 481,...,48n блока 6, подається вхідний вектор х даних. На входи 211,...,21n вектора підстановки блока 6 обчислювальної частини 4, які підключені відповідно до адресних входів демультиплексорів 481,...,48n блока 6, подається вектор підстановки v=gN. При наявності на виході 14 пристрою одиничного сигналу, який є сигналом закінчення процесу сортування і підключений до входів дозволу зчитування блока 6, кожен демультиплексор 48i, де i = 1 n , комутує на свій j-й вихід, де j = 1 n , зна, , чення і-го елемента вхідного вектора х даних, ранг vі якого дорівнює величині j, тобто j=vi=gN, яке потім подається на вхід елемента АБО 49j. Таким чином, на інформаційних виходах 171,...,17n блока 6 обчислювальної частини 4, які є виходами елементів АБО 491,...,49n , формується вектор xN={x1N,...,xjN,...,xnN}, тобто виконується зчитування елементів відсортованого вектора даних за зростанням числових значень його елементів. Приклад сортування послідовності чисел (19 35 12 0 49 27), які є елементами вхідного вектора 11 19907 12 даних, показано на фіг.4. Тут застосовано такі S Запропонована сортувальна нейромережа доумовні позначення: [ - ознака пари елементів, які зволяє зменшити апаратні витрати на сортування чисел як елементів вхідного вектора даних за рахунок ранжування елементів послідовності, що порівнюють, - ознака збільшення/зменшення приводить в процесі попарного перегляду до зміни (інкремента/декремента) відповідних рангів елезначень рангів елементів на одиницю замість пементів. Масив рангів елементів складається з діареміщення (транспозиції) елементів у парах, яке пазону цілих додатних чисел від 1 до 6 (вони поміпотребує додаткової комірки пам'яті для кожної чені в дужках біля кожного елемента вектора пари елементів, що переміщують. Крім того, аналіданих). В процесі сортування виконується один затор реакцій 3 налаштовувальної частини 1 сорконтрольний (п'ятий) цикл. Отже, кількість N циклів тувальної нейромережі містить 3-k елементів пасортування складає N=O(n), оскільки N=n-l. Доведемо можливість застосування одного м'яті (тригерів), де k = 1 K , K=]n/2[ - кількість пар , контрольного циклу. елементів, які порівнюють, тобто його апаратна Нехай р-й цикл був останній, в якому виконускладність дорівнює O(n) елементів, де n - кільвались зміни рангів елементів у парах. Але, якщо у кість елементів вхідного вектора даних пристрою, (р+1)-му циклі не відбувається жодної зміни рангів в той час як апаратна складність відомої сортуваелементів у парах, то можна стверджувати, що у льної мережі - прототипу дорівнює O(n2) елемен(р+2)-му циклі також не буде зміни рангів елементів. В якості значень рангів елементів може викотів, оскільки будуть порівнюватись елементи в ристовуватися не тільки послідовність чисел від 1 парах, які вже впорядковані у р-му циклі. Ці міркудо n (натуральний ряд чисел), але й послідовність вання стосуються всіх циклів, окрім першого. При адреси цих елементів при їх записі у пам'ять. відсутності зміни рангів елементів у першому циклі необхідно виконати ще один цикл для контролю. 13 19907 14 15 Комп’ютерна в ерстка Г. Паяльніков 19907 Підписне 16 Тираж 26 прим. Міністерство осв іт и і науки України Держав ний департамент інтелектуальної в ласності, вул. Урицького, 45, м. Київ , МСП, 03680, Україна ДП “Український інститут промислов ої в ласності”, вул. Глазунова, 1, м. Київ – 42, 01601