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

Пристрій для сортування з ранжуванням чисел, який містить групу елементів І, вхідний елемент І, лічильники, вихідний лічильник, елемент АБО, першу групу забороняючих елементів І, причому вихід елемента АБО з'єднаний з першими входами елементів І групи, виходи яких є виходами пристрою, другий вхід вхідного елемента І з'єднаний з входом тактових імпульсів пристрою, вихід вхідного елемента І з'єднаний з другими входами забороняючих елементів І першої групи і входом додавання вихідного лічильника, виходи забороняючих елементів І першої групи з'єднані з входами віднімання відповідних лічильників, виходи вихідного лічильника порозрядно з'єднані з другими входами елементів І групи, який відрізняється тим, що в нього введено групу дозволяючих еле U 2 (19) 1 3 44929 4 Недоліком даного пристрою є обмежені функвходами елементів І групи, виходи яких є виходаціональні можливості через відсутність ранжуванми пристрою, вихід першого елемента АБО з'єдня чисел вхідного масиву. наний з першим входом вхідного елемента І, друВідомий пристрій для ранжування чисел [а.с. гий вхід якого з'єднаний з входом тактових СРСР №1363184, кл. G06F7/06, 1987р., Бюл. імпульсів пристрою, вихід вхідного елемента І №48], який містить розподілювач імпульсів, n регіз'єднаний з другими входами забороняючих елестрів, n схем порівняння, де n - кількість сортуючих ментів І першої групи і входом додавання вихідночисел, групи елементів І перепису чисел, вузел го лічильника, виходи забороняючих елементів І підрахунку кількості одиниць, проміжковий регістр, першої групи з'єднані з входами віднімання відпоn тригерів, n елементів І аналізу першої групи, відних лічильників, виходи вихідного лічильника причому виходи розрядів І-го регістра, де і=1, 2,..., порозрядно з'єднані з другими входами елементів n, з'єднані з входами першої групи і-ої схеми поріІ групи. вняння, входи другої групи якої з'єднані з виходаНедоліком даного пристрою є обмежені функми розрядів проміжкового регістра, перший вихід ціональні можливості через відсутність ранжування чисел вхідного масиву. підключений до першого входу і-го елемента І В основу корисної моделі поставлено задачу аналізу першої групи, другий вхід якого з'єднаний з створення пристрою для сортування з ранжуванпрямим виходом і-го тригера, вхід встановлення в ням чисел, в якому за рахунок введення нових одиничний стан якого з'єднаний з і-м виходом розелементів та зв'язків між ними розширюються фуподілювача імпульсів і керуючими входами елеменкціональні можливості за рахунок суміщення сорнтів І перепису чисел і-ої групи, тактовий вхід розтування з ранжуванням чисел вхідного масиву. поділювача імпульсів підключений до тактового Поставлена задача вирішується тим, що у входу пристрою, крім того пристрій містить n елепристрій для сортування з ранжуванням чисел, ментів І аналізу другої групи, n груп елементів І який містить групу елементів І, вхідний елемент І, перепису рангу і n лічильників, причому інформалічильники, вихідний лічильник, елемент АБО, ційні входи пристрою з'єднані з інформаційними першу групу забороняючих елементів І, причому входами відповідних елементів І перепису чисел вихід елемента АБО з'єднаний з першими входами (n+1)-ої групи, керуючі входи яких підключені до елементів І групи, виходи яких є виходами притактового входу пристрою, а виходи з'єднані з інстрою, другий вхід вхідного елемента І з'єднаний з формаційними входами проміжкового регістра, входом тактових імпульсів пристрою, вихід вхідновиходи розрядів якого з'єднані додатково з відпого елемента І з'єднаний з другими входами забовідними інформаційними входами елементів І пероняючих елементів І першої групи і входом додарепису чисел і-х груп, виходи елементів І перепису вання вихідного лічильника, виходи забороняючих чисел і-ої групи з'єднані з інформаційними входаелементів І першої групи з'єднані з входами відніми і-го регістра, другий вихід і-ої схеми порівняння мання відповідних лічильників, виходи вихідного підключений до першого входу І-го елемента І лічильника порозрядно з'єднані з другими входами аналізу другої групи, другий вхід якого з'єднаний з прямим виходом і-го тригера, а вихід з'єднаний з елементів І групи, введено групу дозволяючих елементів І, групу елементів затримки, другу групу лічильним входом і-го лічильника, виходи розрядів забороняючих елементів І, лічильники рангів, елеякого є виходами рангу і-го числа пристрою, а інмент АБО-Ш, входи якого з'єднані з інверсними формаційні входи з'єднаю з виходами відповідних виходами ознаки нуля лічильників, а його вихід елементів І перепису рангу і-ої групи, керуючі вхоз'єднаний з інверсним входом вхідного елемента І і ди яких підключені до і-го виходу розподілювача є виходом сигналу „Кінець" пристрою, інверсний імпульсів, виходи елементів І аналізу першої групи вихід ознаки нуля кожного лічильника з'єднаний з з'єднані з входами вузла підрахунку кількості одипершим входом відповідного забороняючого елениць, виходи якого з'єднані з інформаційними вхомента І першої і другої груп, інверсним входом дами відповідних елементів І перепису рангу всіх відповідного дозволяючого елемента І групи і чегруп. рез відповідний елемент затримки групи з другим Недоліком даного пристрою є обмежені функвходом відповідного дозволяючого елемента І ціональні можливості, оскільки він виконує ранжугрупи, виходи всіх дозволяючих елементів І групи вання чисел, які подаються послідовно, без їхньоз'єднані з входами елемента АБО, вихід якого го сортування. з'єднаний також з другими входами забороняючих Найбільш близьким за технічною суттю є приелементів І другої групи, вхід скиду пристрою з'єдстрій для сортування чисел [а.с. СРСР №993251, наний з входами скиду лічильників, вихідного лічикл. G06F7/08, 1983р., Бюл. №4], який містить групу льника і лічильників рангів, входи лічильників піделементів І, вхідний елемент І, лічильники, вихідключені до інформаційних входів пристрою ний лічильник, елементи АБО, диференціюючі відповідно, виходи забороняючих елементів І друелементи, забороняючі елементи І, в подальшому перша група забороняючих елементів І, причому гої групи з'єднані з входами додавання відповідних виходи лічильників порозрядно з'єднані з входами лічильників рангів, їх інформаційний вхід підклювідповідних елементів АБО, виходи яких з'єднані з чений до установного входу пристрою, а виходи входами відповідних диференціюючих елементів, лічильників рангів є відповідними виходами рангів першими входами відповідних забороняючих елепристрою. На кресленні зображено структурну схему ментів І першої групи і відповідними входами першого елемента АБО, виходи диференціюючих пристрою для сортування з ранжуванням чисел. елементів з'єднані з відповідними входами другого Пристрій для сортування містить лічильники елемента АБО, вихід якого з'єднаний з першими 11,...,1m (де m - кількість елементів у масиві чисел), 5 44929 6 Таким чином вхідний елемент І 7 і забороняючі вихідний лічильник 2, елемент АБО 3, елемент елементи І 61,...,6m першої групи відкриті, елемент АБО-HI 4, дозволяючі елементи І 51...,5m, першу групу забороняючи елементів І 61,...,6m, вхідний АБО 3 і забороняючі елементи І 111,...,11m другої елемент І 7, елементи І 81,...,8n (де n-розрядність групи закриті. На вхід 16 пристрою подають тактові імпульси, які через відкритий вхідний елемент І 7 чисел масиву), елементи затримки 91,...,9m, лічипоступають на вхід додавання вихідного лічильнильники рангів 101,...,10m, другу групу забороняючих ка 2 і через відкриті забороняючі елементи елементів І 111,...,11m, вхід 12 скиду пристрою, 161,...,6m першої групи на входи віднімання лічильінформаційні входи 131,...,13m пристрою, вихід 14 сигналу „Кінець" пристрою, виходи 151,...,15m ознаників 11,...,1m. При цьому вміст лічильників 11,...,1m ки нуля відповідних лічильників 11,...,1m, вхід 16 зменшується, а вміст вихідного лічильника 2 збільшується одночасно на одиницю з надходженням тактових імпульсів пристрою, виходи 17 пристрою, кожного тактового імпульсу. виходи 181,...,18m рангів пристрою, установний вхід Коли на вхід 16 пристрою буде подано кіль19 пристрою. кість тактових імпульсів, що відповідає значенню Інверсний вхід вхідного елемента І 7 з'єднаний мінімального і-го числа серед чисел, що були заз виходом елемента АБО-HI 4, його другий вхід писані в лічильниках 11,...,1m 9 а тепер сформоваз'єднаний з входом 16 тактових імпульсів прине у вихідному лічильнику 2, вміст лічильника 1i, строю, а його вихід з'єднаний з другими входами де і=1, 2, ..., m, в якому записане мінімальне чисзабороняючих елементів 161,...,6m першої групи і ло, стане дорівнювати нулю, на його інверсному входом додавання вихідного лічильника 2, виходи виході 15і ознаки нуля заявляється нульовий сигякого порозрядно з'єднані з другими входами еленал, що закриває забороняючий елемент І 6і перментів І 81,...,8m. Виходи забороняючих елементів І 61,...,6m шої групи і відповідно вхід віднімання лічильника 1i, а також забороняючий елемент 1 11i другої групершої групи з'єднані з входами віднімання відпопи і відповідно вхід додавання лічильника рангів відних лічильників 11,...,1m, інверсні виходи 10i. Одночасно нульовий сигнал з інверсного ви151,...,15m ознаки нуля яких з'єднані з входами елемента АБО-HI 4, вихід якого є виходом 14 сигходу 15і ознаки нуля лічильника 1i подається на налу „Кінець" пристрою. Інверсні виходи 151,...,15m відповідний вхід елемента АБО-HI 4, нульовий ознаки нуля лічильників 11...,1m з'єднані також відсигнал на виході якого при цьому не змінюється, і повідно з першими входами забороняючих елемена інверсний вхід дозволяючого елемента І 5і, на другий вхід якого ще надходить одиничний сигнал нтів І 61,...,6m першої групи, з інверсними входами з виходу елемента затримки 9і. дозволяючих елементів 51,...,5m та входами елеОтже, нульовий сигнал з інверсного виходу 15і ментів затримки 91,...,9m. Виходи елементів затримки 91,...,9m з'єднані з другими входами дозволяюознаки нуля лічильника 1i подається на відповідчих елементів І 51,...,5m відповідно, виходи яких ний вхід забороняючого елемента І 11i другої груз'єднані з входами елемента АБО 3, вихід якого пи, який при цьому закривається. З виходу забоз'єднаний з першими входами елементів І 81,...,8m, роняючого елемента I 11i другої групи нульовий виходи яких є виходами 17 пристрою. Вхід 12 скисигнал подається на вхід додавання лічильника ду пристрою підключений до входів скиду лічильрангів 10і і не змінює його стану. Таким чином, на ників 11,...,1m, вихідного лічильника 2 та лічильнивиході лічильника рангів 10, залишається раніше сформований ранг, що дорівнює 1. Тобто на вихоків рангів 101,...,10m, а входи 131,...,13m лічильників ді лічильника рангів 10і, в якого відповідний забо11,...,1m підключені до інформаційних входів пристрою відповідно. роняючий елемент I 11i другої групи закривається першим, ранг буде рівний одиниці, а на виході одІнверсні виходи 151,...,15m ознаки нуля лічильного з лічильників рангів 101...,10m, в якого відповіників 11,...,1m з'єднані також відповідно з першими входами забороняючих елементів І 111,...,11m друдний забороняючий елемент І 111,...,11m другої гої групи, а вихід елемента АБО 3 з'єднаний також групи закривається наступний - ранг буде на одиз другими входами забороняючих елементів І ницю більший і так далі. Отже, на виході елемента АБО 3 формується 111,...,11m другої групи, виходи яких з'єднані з входами додавання відповідно лічильників рангів одиничний сигнал за одиничним сигналом на ви101,...,10m. Інформаційний вхід лічильників рангів ході відкритого дозволяючого елемента І 5i який, 101,...,10m підключений до установного входу 19 будучи поданий на один з входів елементів 81,...,8n пристрою, а їх інформаційні виходи є відповідними групи, дозволяє проходження через них на виходи виходами 181,...,18m рангів пристрою. 17 пристрою інформації з виходів вихідного лічиПристрій працює таким чином. льника 2. Тривалість одиничного сигналу на виході Спочатку лічильники 11,...,1m, лічильники рандозволяючого елемента І 5і дорівнює часу затримгів 101,...,10m і вихідний лічильник 2 встановлюють ки елемента 9i і є достатньою для зчитування дау початковий (нульовий) стан за одиничним сигнаних з вихідного лічильника 2 через елементи І лом на вході 12 скиду пристрою, який подають на 81,...,8n групи. Одночасно одиничний сигнал на виході елемента АБО 3 дозволяє проходження їх входи скиду. Потім у лічильники 11,...,1m по їх через відкриті забороняючі елементи І 111,…,11m входах 131,...,13m записують елементи масиву чисел, а лічильники рангів 101,...,10m встановлюють в другої групи одиничних сигналів з виходів ознаки нуля всіх лічильників 1і,...,1m, крім лічильника 1i. В одиничний стан за сигналом на установному вході результаті вміст лічильників рангів 101,...,10m збі19 пристрою. На виході елемента АБО-HI 4 присульшується на одиницю, крім лічильника 10i, вміст тній нульовий сигнал, так як вміст лічильників якого залишається незмінним. 11,...,1m не дорівнює нулю і на їх інверсних виходах 151,...,15m ознаки нуля присутні одиничні сигнали. 7 44929 8 Після цього на виході дозволяючого елемента додавання вихідного лічильника 2 не поступають. І 5і встановлюється нульовий сигнал з виходу При цьому у вихідному лічильнику 2 зафіксовано елемента затримки 9i, який закриває елемент АБО значення максимального числа серед чисел маси3. Одночасно нульовий сигнал з виходу елемента ву, а з виходів 181,...,18m рангів пристрою можна АБО 3 закриває всі забороняючі елементи І зчитати відповідні ранги елементів масиву чисел, 111,...,11m другої групи відповідних лічильників що зафіксовані у лічильниках рангів 101,...,10m. рангів 101,...,10m і елементи І 81,...,8n. Аналогічний Отже, якщо робота пристрою для сортування чипроцес відбувається при обнуленні кожного з лічисел закінчена, на виході 14 сигналу „Кінець” прильників 11,...,1m у певній послідовності. строю присутній одиничний сигнал. Коли всі лічильники 11,...,1m обнуляться, на виЗапропонований пристрій для сортування з ході елемента АБО-НI 4 сформується одиничний ранжуванням чисел має розширені функціональні сигнал, який припинить надходження тактових можливості за рахунок суміщення процесу сортуімпульсів через вхідний елемент І 7. Тактові імпування за зростанням з формуванням рангів чисел льси на входи віднімання лічильників 11,...,1m і вхід вхідного масиву. Комп’ютерна верстка В. Мацело Підписне Тираж 28 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601