Пристрій для ранжування чисел

Пристрій для ранжування чисел, що містить n регістрів, де n - кількість сортованих чисел, К схем порівняння, де К-]n/2[ - ціла частина числа n/2, n лічильників, виходи розрядів і-го лічильника є виходами рангу і-го числа пристрою, де і=1,...,n, який відрізняється тим, що в нього введено селектор кодів, комутатор, елемент АБО-НІ, елемент затримки, два елементи АБО, причому перша і друга групи n входів пристрою є відповідно входами елементів вхідного масиву чисел та їхніх початкових рангів, перша група n входів пристрою з'єднана з відповідними інформаційними входами n регістрів, інформаційні виходи яких підключені до інформаційних входів селектора кодів, інформаційні виходи якого попарно з'єднані з входами К схем порівняння, інформаційні входи комутатора з'єднані з виходами ознаки відповідних К схем порівняння, а інформаційні виходи з'єднані з входами інкременту і декременту відповідних n лічильників, інформаційні входи яких підключені до другої групи n входів пристрою, крім першого та nго лічильників, крім того, інформаційні виходи n лічильників з'єднані з відповідними входами керування селектора кодів і комутатора, а інформаційний вихід першого лічильника з'єднаний з входом елемента затримки, вихід якого з'єднаний з першим входом першого елемента АБО, другий вхід якого з'єднаний з n-м входом другої групи входів пристрою, а вихід з'єднаний з інформаційним входом n-го лічильника, інформаційний вихід якого U 2 UA 1 3 хронізації відповідно першого і другого блоків пам'яті, вихід ознаки порівняння блока порівняння з'єднаний з входом аналізу ознаки порівняння блока керування, виходи першої групи комутатора з'єднані з інформаційними входами другого блока пам'яті, блоки пам'яті містять n регістрів кожний, де n - кількість чисел у початковому масиві, перший і третій виходи блока керування з'єднані відповідно з першим і другим входами керування блока порівняння, і-й вихід рівності якого, де і= 1, 2, ..., n, з'єднаний з входом установлення у нульовий стан і-го регістра першого блока пам'яті, інформаційні входи n-го регістра якого підключені до виходів другої групи комутатора, перший і другий входи керування якого підключені відповідно до виходу ознаки порівняння блока порівняння і другого виходу блока керування, вхід запуску якого є входом запуску пристрою, виходи розрядів першого регістра другого блока пам'яті з'єднані з інформаційними входами комутатора, і-й інформаційний вхід пристрою з'єднаний з установлюючими входами і-х регістрів першого і другого блоків пам'яті, виходи розрядів яких з'єднані з і-ми інформаційними входами відповідно першої і другої груп блока порівняння, третій вхід керування якого підключений до входу логічної одиниці пристрою, входи синхронізації першого і другого блоків пам'яті є входами синхронізації всіх регістрів відповідно першого і другого блоків пам'яті, інформаційні входи j-х регістрів першого і другого блоків пам'яті, де j=1, 2, ..., (n-1), підключені до виходів розрядів (j+1)-х регістрів відповідно першого і другого блоків пам'яті. Недоліком даного пристрою є недостатня швидкодія через те, що в процесі сортування чисел виконується їхній перезапис у першому блоці пам'яті шляхом послідовного циклічного зсуву чисел у другому блоці пам'яті. Найбільш близьким за технічною суттю є пристрій для ранжування чисел (а.с. СРСР №1363184, кл. G 06 F 7/06, 1987р., Бюл. №48), який містить розподілювач імпульсів, n регістрів, n схем порівняння, в подальшому К схем порівняння, де n кількість сортованих чисел, К=]n/2[ - ціла частина числа n/2, групи елементів І перезапису чисел, вузол підрахунку кількості одиниць, проміжний регістр, n тригерів, n елементів І аналізу першої групи, причому виходи розрядів і-го регістра, де і=1,..., n, з'єднані з входами першої групи і-ої схеми порівняння, входи другої групи якої з'єднані з виходами розрядів проміжного регістра, перший вихід підключений до першого входу і-го елемента І аналізу першої групи, другий вхід якого з'єднаний з прямим виходом і-го тригера, вхід встановлення в одиничний стан якого з'єднаний з і-м виходом розподілювача імпульсів і входами керування елементів І перезапису чисел і-ої групи, тактовий вхід розподілювача імпульсів підключений до тактового входу пристрою, крім того пристрій містить n елементів І аналізу другої групи, n груп елементів І перезапису рангу і n лічильників, причому інформаційні входи пристрою з'єднані з інформаційними входами відповідних елементів І перезапису чисел (n+1)-ої групи, входи керування яких підключені до тактового входу пристрою, а виходи з'єднані з ін 43261 4 формаційними входами проміжного регістра, виходи розрядів якого з'єднані додатково з відповідними інформаційними входами елементів І перезапису чисел і-х груп, виходи елементів І перезапису чисел і-ої групи з'єднані з інформаційними входами і-го регістра, другий вихід і-ої схеми порівняння підключений до першого входу і-го елемента І аналізу другої групи, другий вхід якого з'єднаний з прямим виходом і-го тригера, а вихід з'єднаний з входом лічби і-го лічильника, виходи розрядів якого є виходами рангу і-го числа пристрою, а інформаційні входи з'єднані з виходами відповідних елементів І перезапису рангу і-ої групи, входи керування яких підключені до і-го виходу розподілювача імпульсів, виходи елементів І аналізу першої групи з'єднані з входами вузла підрахунку кількості одиниць, виходи якого з'єднані з інформаційними входами відповідних елементів І перезапису рангу всіх груп. Недоліком цього пристрою є недостатня швидкодія, оскільки він сортує числа з ранжуванням в процесі їхнього послідовного подання у пристрій. В основу корисної моделі поставлено задачу створення пристрою для ранжування чисел, в якому за рахунок введення нових вузлів та зв'язків між ними досягається зменшення часу сортування масиву чисел, що сприятиме підвищенню швидкодії пристрою для ранжування чисел. Поставлена задача вирішується тим, що у пристрій для ранжування чисел, який містить n регістрів, де n - кількість сортованих чисел, К схем порівняння, де К=]n/2[ - ціла частина числа n/2, n лічильників, виходи розрядів і-го лічильника є виходами рангу і-го числа пристрою, де і=1,...,n, введено селектор кодів, комутатор, елемент АБО-НІ, елемент затримки, два елементи АБО, причому перша і друга групи n входів пристрою є відповідно входами елементів вхідного масиву чисел та їхніх початкових рангів, перша група n входів пристрою з'єднана з відповідними інформаційними входами n регістрів, інформаційні виходи яких підключені до інформаційних входів селектора кодів, інформаційні виходи якого попарно з'єднані з входами К схем порівняння, інформаційні входи комутатора з'єднані з виходами ознаки відповідних К схем порівняння, а інформаційні виходи з'єднані з входами інкременту і декременту відповідних n лічильників, інформаційні входи яких підключені до другої групи n входів пристрою, крім першого та nго лічильників, крім того, інформаційні виходи n лічильників з'єднані з відповідними входами керування селектора кодів і комутатора, а інформаційний вихід першого лічильника з'єднаний з входом елемента затримки, вихід якого з'єднаний з першим входом першого елемента АБО, другий вхід якого з'єднаний з n-м входом другої групи входів пристрою, а вихід з'єднаний з інформаційним входом n-го лічильника, інформаційний вихід якого з'єднаний з першим входом другого елемента АБО, другий вхід якого з'єднаний з першим входом другої групи входів пристрою, а вихід з'єднаний з інформаційним входом першого лічильника, вхід керування пристрою з'єднаний з входом керування циклічністю роботи селектора кодів, а виходи 5 ознаки К схем порівняння з'єднані з відповідними входами елемента АБО-НІ, вихід якого є виходом сигналу "Кінець" пристрою, причому селектор кодів містить n демультиплексорів, першу і другу групи n елементів АБО, першу і другу групи n елементів І, причому і-й вхід селектора кодів з'єднаний з інформаційним входом і-го демультиплексора відповідно, адресний вхід якого з'єднаний з і-м входом керування селектора кодів, кожний і-й вихід з n виходів j-го демультиплексора (де j=1..., n) з'єднаний з j-м входом і-го елемента АБО першої групи, вихід якого з'єднаний з першими входами і-го елемента І першої групи та (і-1)-го елемента І другої групи, крім першого елемента АБО першої групи, вихід якого з'єднаний з першими входами першого елемента І першої групи та (n-1)-го елемента І другої групи, і крім n-го елемента АБО першої групи, вихід якого з'єднаний з першими входами n-х елементів І першої та другої груп, другий вхід кожного елемента І першої групи та інверсний вхід кожного елемента І другої групи з'єднаний з входом керування циклічністю роботи селектора кодів, виходи і-х елементів І першої та другої груп з'єднані відповідно з першими входами і-го та другими входами (і+1)-го елементів АБО другої групи, крім (n-1)-го елемента І другої групи, вихід якого з'єднаний з другим входом першого елемента АБО другої групи, а також n-го елемента І другої групи, вихід якого з'єднаний з другим входом n-го елемента АБО другої групи, вихід і-го елемента АБО другої групи є і-м виходом селектора кодів. На Фіг.1 представлено блок-схему пристрою для ранжування чисел; на Фіг.2 представлено топологію з'єднань елементів масиву чисел, яку реалізує селектор кодів для парної розмірності масиву п чисел; на Фіг.3 наведено функціональну схему селектора кодів. Пристрій для ранжування чисел (Фіг.1) містить n регістрів 11, ..., 1n, де n - кількість сортованих чисел (елементів у масиві чисел), К схем порівняння 21, ..., 2К, де К=]n/2[ - ціла частина числа n/2, n лічильників 31, ..., 3n, селектор кодів 4 і комутатор 5. Крім того, пристрій містить входи 61, ..., 6n, та 71, ..., 7n пристрою, які є відповідно входами елементів вхідного масиву чисел та їхніх початкових рангів, виходи 81, ..., 8n рангів пристрою. Входи 61, ..., 6n пристрою з'єднані з інформаційними входами регістрів 11, ..., 1n, виходи яких підключені до інформаційних входів 91, ..., 9n селектора кодів 4, інформаційні виходи 101, ..., 10n якого попарно з'єднані з входами схем порівняння 21, ..., 2К. Інформаційні входи комутатора 5 з'єднані з виходами ознаки відповідних схем порівняння 21, ..., 2К, а інформаційні виходи з'єднані з входами інкременту і декременту відповідних лічильників 31, ..., 3n, інформаційні входи яких, крім лічильників 31, 3n, підключені до входів 72, ..., 7n-1 пристрою. Крім того, інформаційні виходи лічильників 31 ..., 3n є виходами 81, ..., 8n рангів пристрою і з'єднані з входами 111, ..., 11n керування селектора кодів 4 і відповідними входами керування комутатора 5, вхід 12 керування пристрою з'єднаний з входом керування циклічністю роботи селектора кодів 4, а виходи ознаки схем порівняння 21, ..., 2К з'єднані також з відповідними входами елемента АБО-НІ 43261 6 13, вихід якого є виходом 14 сигналу "Кінець" пристрою. Крім того, інформаційний вихід 81 лічильника 31 з'єднаний з входом елемента затримки 15, вихід якого і вхід 7n з'єднані через елемент АБО 16 з інформаційним входом n-го лічильника 3n, інформаційний вихід 8n якого і вхід 71 пристрою з'єднані через елемент АБО 17 з інформаційним входом першого лічильника 31. Селектор кодів 4 (Фіг.3) містить інформаційні входи 91, ..., 9n, інформаційні виходи 101, ..., 10n, входи 111, ..., 11n керування, вхід 12 керування циклічністю роботи, n демультиплексорів 181, ..., 18n, n елементів АБО 191, ..., 19n, n елементів I 201, ..., 20n, n елементів І 211, ..., 21n, n елементів АБО 221, ..., 22n. Вхід 9i (де і=1, ..., n) з'єднаний з інформаційним входом і-го демультиплексора 18i відповідно, адресним входом якого є вхід 11i керування селектора кодів 4. Кожний і-й вихід Qi з n виходів демультиплексора 18, (j=1, ..., n) з'єднаний з j-м входом і-го елемента АБО 19i вихід якого з'єднаний з першим входом і-го елемента І 20i, а також з першим входом (і-1)-го елемента I 21i, крім першого елемента АБО 191, вихід якого з'єднаний з першими входами першого елемента І 201 і (n-і)-го елемента І 21n-1, і крім n-го елемента АБО 19n, вихід якого з'єднаний з першими входами n-х елементів І 20n та І 21n. Другий вхід кожного елемента І 20i та інверсний вхід кожного елемента І 21i з'єднаний з входом 12 керування циклічністю роботи селектора кодів 4. Виходи і-х елементів І 20i та І 21i з'єднані відповідно з першими входами і-го АБО 22i та другими входами (і+1)-го елемента АБО 22i+1, крім (n-1)-го елемента І 21n-1, вихід якого з'єднаний з другим входом першого елемента АБО 221, а також n-го елемента І 21n, вихід якого з'єднаний з другим входом n-го елемента АБО 22n, вихід і-го елемента АБО 22i є і-м виходом 10i селектора кодів 4. Сортування масиву чисел шляхом попарного обміну без використання рангів виконують в такий спосіб. У першому і всіх непарних циклах попарно порівнюють сусідні елементи масиву чисел у (2k1)-х і 2k-х позиціях і більший з них за значенням переміщують або залишають у 2k-й позиції, а менший переміщують або залишають у (2k-1)-й позиції, де k=1, ..., К. У другому і всіх парних циклах попарно порівнюють сусідні елементи масиву чисел у 2k-х і (2k+1)-х позиціях, а також перший і n-й елементи масиву, і більший з них за значенням переміщують або залишають у (2k+1)-й позиції, а менший переміщують або залишають у 2k-й позиції або першій позиції. Сортування шляхом попарного обміну з введенням рангів елементів масиву чисел має такий вигляд. 1. Перед сортуванням усім елементам масиву чисел присвоюють ранги, які відповідають номерам їхніх позицій у масиві. 2. Формують групу пар із сусідніх елементів масиву чисел незалежно від кількості n елементів масиву за таким правилом: а) у всіх непарних циклах кожна пара елементів складається з (2k-1)-х і 2k-х елементів (k=1, ..., К); б) у всіх парних циклах кожна пара елементів складається з 2k-х і (2k+1)-х 7 елементів, а також першого та n-го елементів масиву чисел. 3. У кожній парі елементів масиву чисел за результатом порівняння виконують такі дії: а) якщо елемент молодшої позиції менший за значенням, ніж елемент старшої позиції, то ранги елементів не змінюють; б) якщо елемент молодшої позиції більший за значенням, ніж елемент старшої позиції, то ранги змінюють таким чином: ранг елемента молодшої позиції збільшують на одиницю, ранг елемента старшої позиції зменшують на одиницю, а також ранги елементів першої і n-ої позицій міняються місцями. 4. Перевіряють умову відсутності будь-якої зміни рангів у всіх парах елементів масиву чисел. Якщо ця умова виконується і це не перший цикл, то виконують перехід до п. 5; якщо ця умова не 43261 8 виконується, а також якщо це перший цикл, то виконують перехід до п. 2. 5. Процес сортування закінчено. Приклади сортування масиву чисел без ранжування і з введенням рангів елементів масиву показано у табл. 1 і 2 відповідно. Тут застосовано такі умовні позначення: - ознака пари елементів, що порівнюють; - ознака переміщення (транспозиції) елементів у відповідній парі, - ознака зменшення або збільшення відповідних рангів елементів. Елементи масиву чисел взято з діапазону цілих додатних чисел (0, 9). Масив рангів елементів масиву чисел складається з діапазону цілих чисел від 1 до 6. Наприкінці сортування виконують один контрольний цикл. 9 Розглянемо сортування масиву чисел, який складається, наприклад, з шести чисел {7,9,1,5,4,2} (табл.2). Ці числа записують по входах 61, ..., 66 пристрою у відповідні регістри 11, ..., 16. Одночасно по входах 71, ..., 76 пристрою у лічильники 31, ..., 36 записують масив початкових рангів елементів масиву чисел у вигляді послідовності номерів позицій відповідних елементів у масиві, а саме {1,2,3,4,5,6}. Після цього з подачею зі входу 12 керування пристрою відповідного сигналу (наприклад, одиничного) на вхід керування циклічністю роботи селектора кодів 4 і з урахуванням початкових рангів елементів на його входах 111, ..., 116 керування виконують перший (непарний) цикл сортування, який починають з формування відповідних пар сусідніх елементів масиву чисел (п.2а) селектором кодів 4, які подають на його інформаційні входи 91, ..., 96. Сформовані пари чисел з виходів 101 ...,106 селектора кодів 4 подають на попарні входи відповідних схем порівняння 21, ..., 23, причому принцип формування пар елементів у 43261 10 непарних і парних циклах графічно подано на Фіг.2. За результатом попарного порівняння на виходах ознаки схем порівняння 21, ..., 23 одиниця формується у тих випадках, коли не виконується умова (п.3а), а виконується умова (п.3б). Ці одиничні сигнали, проходячи через комутатор 5, формують одиничні сигнали на входах інкременту і декременту відповідних лічильників 31, ..., 36, тобто збільшують або зменшують на одиницю їхній стан. Ці значення рангів з виходів лічильників 31, ..., 36 фіксують на входах 111, ..., 116 керування селектора кодів 4 і відповідних входах керування комутатора 5 перед початком наступного циклу сортування. Одночасно перевіряють виконання умови (п.4), тобто наявність одиничного сигналу на виході 14 елемента АБО-НІ 13, що можливо при відсутності одиничних сигналів на виходах ознаки всіх схем порівняння 21, ..., 23. Оскільки для першого циклу це не суттєво, тому змінюють сигнал на вході 12 керування пристрою на протилежний (нульо 11 вий), який подають на вхід керування циклічністю роботи селектора кодів 4, в результаті чого починають виконання другого (парного) циклу сортування. Він складається з формування відповідних пар сусідніх елементів масиву чисел (п.2б) селектором кодів 4, попарного порівняння у схемах порівняння 21, ..., 23, комутації сигналів ознаки з виходів ознаки схем порівняння 21, ..., 23 комутатором 5, формування рангів чисел масиву у лічильниках 31, ..., 36. Причому у лічильниках 32, ..., 35 формування рангів виконується в процесі збільшення або зменшення їхнього стану, а у лічильниках 31 і 36 виконується перезапис рангів між ними. Причому спочатку записується ранг з виходу лічильника 36 у лічильник 31 через елемент АБО 17, а потім у лічильник 36 через елемент затримки 15 і елемент АБО 16 записується ранг з виходу лічильника 31. Змінені значення рангів з виходів лічильників 31, ..., 36 знову подають на входи 111, ..., 116 керування селектора кодів 4 і на відповідні входи керування комутатора 5 перед початком наступного циклу сортування. Процес сортування з ранжуванням елементів масиву чисел по циклах представлено у табл.2. Після кожного циклу сортування перевіряють умову (п.4) у вигляді наявності чи відсутності одиничного сигналу на виході 14 елемента АБО-НІ 13. Якщо одиничний сигнал на виході 14 елемента АБО-НІ 13 відсутній, то змінюють сигнал на вході 12 керування пристрою на протилежний і починають виконання наступного парного/непарного циклу сортування. Так виконується процес сортування з ранжуванням. Він закінчується з появою одиничного сигналу на виході 14 сигналу "Кінець" пристрою. Отже, у лічильниках 31, ..., 36 сформовано відповідні ранги елементів відсортованого масиву чисел, а саме, найбільшому за значенням елементу масиву чисел відповідає максимальний ранг, а найменшому - мінімальний (одиничний) ранг. Сформовані ранги в подальшому використовують для зчитування чисел з регістрів 11, ..., 16 або за збільшенням, або за зменшенням їхніх значень, тобто формують відсортований масив чисел за зростанням/спаданням. Таким чином, для наведеного сортування чисел мінімальна кількість циклів сортування дорівнює двом, а максимальна - n, де n – кількість елементів у масиві чисел, тобто: Nmin=2, Nmax=n. При відсутності зміни рангів у першому циклі необхідно виконати ще один цикл для контролю. 43261 12 Селектор кодів 4 (Фіг.3) працює у такий спосіб. На інформаційний вхід 9i селектора кодів 4, а отже на інформаційний вхід і-го демультиплексора 18i спочатку подається відповідний і-й елемент масиву чисел, а на його адресний вхід, який з'єднаний з входом 11i керування селектора кодів 4, відповідний ранг і-го елемента в масиві чисел. Тобто на іму виході Qi, кожного j-го демультиплексора 18j (j=1, ..., n) з'явиться відповідне число масиву з і-м початковим рангом, яке подається на j-й вхід і-го елемента АБО 19i і далі з його виходу проходить на перший вхід і-го елемента І 20i, (де і=1, ..., n), a також на перший вхід (і-1)-го елемента І 21i, крім першого елемента АБО 191, з виходу якого відповідне число масиву подається на перший вхід першого елемента І 201 і на перший вхід (n-і)-го елемента І 21n-1 і крім n-го елемента АБО 19n, з виходу якого відповідне число масиву подається на перші входи n-х елементів І 20n та І 21n. При наявності одиничного сигналу на вході 12 керування циклічністю роботи селектора кодів 4, що відповідає виконанню непарних циклів сортування, число з виходу і-го елемента І 20i проходить на перший вхід елемента АБО 22i (де і=1, ..., n) і з'являється на відповідному виході 10i селектора кодів 4. Якщо на вході 12 керування циклічністю роботи селектора кодів 4 присутній нульовий сигнал, що відповідає виконанню парних циклів сортування, то відповідне число масиву з виходу іго елемента І 21i проходить на другий вхід елемента АБО 22i+1 (де і=1, ..., n-2) і з'являється на відповідному виході 10і+1 селектора кодів 4, крім числа з виходу (n-1)-го елемента І 21n-1, що приходить на другий вхід першого елемента АБО 221 і з'являється на відповідному виході 101 селектора кодів 4, і крім числа з виходу n-го елемента І 21n, що приходить на другий вхід елемента АБО 22n і з'являється на відповідному виході 10n селектора кодів 4. У запропонованому пристрої зменшення тривалості сортування масиву чисел досягається за рахунок їх ранжування, що приводить в процесі попарного перегляду елементів масиву чисел до зміни значень рангів на одиницю (інкремент/декремент) замість переміщення (транспозиції) елементів у парах, яке виконують як мінімум за три такти. В якості значень рангів елементів може використовуватися не тільки послідовність чисел від 1 до n, де n - кількість елементів у масиві чисел, але й послідовність адреси цих елементів при їхньому записі у пам'ять. 13 Комп’ютерна верстка М. Ломалова 43261 Підписне 14 Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601