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

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