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

Реферат: Пристрій для впорядкування чисел містить перший та другий лічильники, перший і другий блоки пам'яті, блок порівняння, перший і другий елементи АБО та комутатор. Введено: перший, другий та третій регістри і блок вирахування. UA 114262 U (54) ПРИСТРІЙ ДЛЯ ВПОРЯДКУВАННЯ ЧИСЕЛ UA 114262 U UA 114262 U 5 10 15 20 25 30 35 40 45 50 55 Корисна модель, що пропонується, належить до обчислювальної техніки, а саме до цифрових пристроїв, і може бути використана в машинобудівних технологіях. Відомий пристрій для вибору чисел, який містить процесори, блоки пам'яті, блок керування та компаратор, при цьому виходи блоків пам'яті підключено до інформаційних входів компаратора, виходи якого підключено до перших входів процесорів, другі входи яких підключено до виходу блока керування [1]. Недоліки аналогу: вибір чисел не забезпечує їх впорядкування та представлення у компактній формі, що відповідно обмежує функціональні можливості пристрою та потребує значних обсягів пам'яті для їх збереження. Найбільш близьким до запропонованої корисної моделі по технічній суті та результату, що досягається, є пристрій для впорядкування чисел, який містить перший і другий лічильники, перший і другий блоки пам'яті, блок порівняння, перший і другий елементи АБО та комутатор, при цьому тактовий вхід та вхід скидання підключено відповідно до синхровходів та входів скидання першого та другого лічильників, виходи переповнення яких підключено до перших входів відповідно першого та другого елементів АБО, виходи яких підключено до входів блокування рахування відповідно першого та другого лічильників, інформаційні виходи яких підключено відповідно до адресних входів першого та другого блоків пам'яті, виходи яких підключено відповідно до першого та другого інформаційних входів комутатора та відповідно до першого та другого входів блока порівняння, вихід якого підключено до другого інверсного входу першого елемента АБО, другого входу другого елемента АБО та управляючого входу комутатора, вихід якого підключено до виходу (послідовності) пристрою [2]. Недоліки прототипу: впорядкована послідовність потребує значних обсягів пам'яті для її збереження. Задача корисної моделі - створення пристрою для впорядкування чисел, в якому шляхом введення першого, другого та третього регістрів і блока вирахування забезпечено компактне представлення впорядкованої послідовності чисел, що суттєво зменшує обсяг пам'яті для її збереження в умовах обмеженої малим значенням максимальної різності сусідніх чисел. Поставлена задача вирішується тим, що у пристрій для впорядкування чисел, що містить перший та другий лічильники, перший і другий блоки пам'яті, блок порівняння, перший і другий елементи АБО та комутатор, при цьому вхід скидання пристрою підключено до входів скидання першого та другого лічильників, тактовий вхід пристрою підключено до синхровходів першого та другого лічильників, інформаційні виходи яких підключено до адресних входів відповідно першого та другого блоків пам'яті, а виходи переповнення підключено до перших входів відповідно першого та другого елементів АБО, виходи яких підключено до входів блокування рахування відповідно першого та другого лічильників, виходи першого та другого блоків пам'яті підключено відповідно до першого та другого інформаційних входів комутатора та підключено відповідно до першого та другого входів блока порівняння, вихід якого підключено до другого інверсного входу першого елемента АБО, другого входу другого елемента АБО та управляючого входу комутатора, вихід якого підключено до виходу послідовності пристрою, згідно з корисною моделлю, введено: перший, другий та третій регістри і блок вирахування, при цьому вхід скидання пристрою підключено до синхровходу першого регістра та входу скидання третього регістра, тактовий вхід пристрою підключено до синхровходу другого та третього регістра, вихід комутатора підключено до інформаційних входів першого та другого регістрів і першого входу блока вирахування, вихід першого регістра підключено до виходу базового значення пристрою, вихід другого регістра підключено до другого входу блока вирахування, вихід якого підключено до інформаційного входу третього регістра, вихід якого підключено до виходу компактної форми послідовності пристрою. Технічний ефект від запропонованого рішення полягає в тому, що шляхом введення першого, другого та третього регістрів і блока вирахування забезпечено компактну форму представлення впорядкованої послідовності, що суттєво зменшує обсяг пам'яті для її збереження при обмеженні малим значенням максимальної різності сусідніх чисел. Зменшення обсягу пам'яті можна оцінити наступним чином. Обсяг пам'яті, необхідний для збереження послідовності двійкових чисел, впорядкованої в прототипі, визначається як V П = LМ1, де L - кількість чисел впорядкованої послідовності, М1 - довжина найбільшого з чисел, враховуючи розряд коду знаку. У запропонованому рішенні компактна форма представлення потребує обсяг пам'яті VЗ = L М2, де М2 - довжина найбільшої різниці сусідніх чисел (без знаку). Таким чином, обсяг пам'яті зменшується у М1/ М2 разів. Наприклад, для чисел з розрядністю М1=8 та різницею між сусідніми числами, що не перевищує 15, тобто М2=4, обсяг пам'яті зменшується в 2 рази. 1 UA 114262 U 5 10 15 20 25 30 35 40 45 50 55 Суть корисної моделі пояснюється кресленням на фіг. 1, де зображено пристрій для впорядкування чисел, що містить перший 1 і другий 2 лічильники, перший 3 і другий 4 блоки пам'яті, блок 5 порівняння, перший 6 і другий 7 елементи АБО, комутатор 8, перший 9, другий 10 та третій 12 регістри, блок 11 вирахування, вхід R скидання, тактовий вхід С, вихід S послідовності пристрою, вихід В базового значення пристрою та вихід G компактної форми послідовності пристрою, при цьому вхід R пристрою підключено до входів R скидання лічильників 1 та 2, синхровходу С регістра 9 та входу R скидання регістра 12, вхід С пристрою підключено до синхровходів С лічильників 1 і 2 та синхровходів регістрів 10 і 12, інформаційні виходи І лічильників 1 і 2 підключено відповідно до адресних входів блоків 3 і 4, а виходи переповнення Р підключено відповідно до перших входів елементів АБО 6 та 7, виходи яких підключено відповідно до входів V блокування рахування лічильників 1 і 2, вихід блока 3 підключено до першого входу блока 5 та першого інформаційного входу комутатора 8, вихід блока 4 підключено до другого входу блока 5 та другого інформаційного входу комутатора 8, вихід блока 5 підключено до другого інверсного входу елемента АБО 6, другого входу елемента АБО 7 та управляючого входу Y комутатора 8, вихід якого підключено до виходу S пристрою, інформаційних входів І регістрів 9 і 10 та першого входу блока 11, вихід регістра 9 підключено до виходу В пристрою, вихід регістра 10 підключено до другого входу блока 11, вихід якого підключено до інформаційного входу І регістра 12, вихід якого підключено до виходу G пристрою. На фіг. 2 показано часові діаграми роботи блоків пристрою, а саме для входів R, С пристрою, виходів І та Р лічильників 1 і 2, що позначені як "СЧ 1 І", "СЧ 1 Р", "СЧ 2 І", "СЧ 2 Р", блоків 3, 4 та 5, що позначені як "БП З", "БП 4" та "БС 5", виходу S пристрою, виходу регістра 10, що позначений як "РГ 10", виходу В пристрою, виходу блока 11, що позначений як "БВ 11" та виходу G пристрою. Числа, що зчитуються з блоків 3 і 4 пронумеровано 1, 2,…,N та 1*, 2*,…, N*, відповідно, де N тa N* - кількість чисел в блоках 3 і 4. Для прикладу числа приймають значення відповідно 3, 7,…, 17 та 5, 6, 9,…,19,…, 23 що впорядковані за зростанням їх величини. Пристрій працює у такий спосіб. На вхід R пристрою та відповідно на входи R скидання лічильників 1 та 2, регістра 12 та синхровхід С регістра 9 подається сигнал скидання. Він встановлює виходи лічильників 1 і 2 та регістра 12 у нульове значення. На вхід С пристрою та відповідно на синхровходи С лічильників 1 та 2, регістрів 10 та 12 подаються синхроімпульси, що тактують їх роботу. В блоках 3 та 4 розміщено числа, що впорядковані за величиною значень у напрямку збільшення відповідно до зростання номера адреси. Лічильники 1 та 2 формують послідовність кодів адрес 1, 2,…, N та 1*, 2*,…, N*, за якими з виходів блоків 3 та 4 зчитуються підряд впорядковані числа. Вони подаються на перший та другий входи блока 5 і перший та другий інформаційні входи комутатора 8. На виходах Р переповнення лічильників 1 та 2 формується нульове значення, що переходить у одиничне значення на останньому коді N та N*, відповідно. Ці значення подаються на перші входи елементів АБО 6 та 7, відповідно. Блок 5 формує одиничне значення, якщо з блока 3 зчитується менше число, ніж з блока 4, і нульове значення у противному випадку. Одиничне значення інвертується, проходячи елемент АБО 6 за інверсним другим входом при нульовому значенні на першому вході, та нульовим значенням на вході V блокування рахування дозволяє лічильнику 1 збільшувати код адреси на одиницю. При цьому другий вхід елемента АБО 7 та його вихід приймають одиничне значення, що приходить на вхід V блокування рахування лічильника 2 та забороняє йому змінювати код на інформаційному виході І. На останньому коді N-1 одиничне значення на виході Р переповнення лічильника 1 встановлює елемент АБО 6 у одиничне значення, що блокує подальше рахування, фіксуючи на інформаційному виході І лічильника 1 останній код N-1, а на виході блока 3 - останнє число. Нульове значення з виходу блока 5 приходить на другий вхід елемента АБО 7 і встановлює нульове значення на його виході (при нульовому значенні на першому вході) та вході V блокування рахування лічильника 2, дозволяючи йому збільшувати код адреси на одиницю. При цьому другий інверсний вхід елемента АБО 6 та його вихід приймають одиничне значення, що приходить на вхід V блокування рахування лічильника 1 та забороняє йому змінювати код на виході І. На останньому коді N* - 1 одиничне значення на виході Р переповнення лічильника 2 встановить елемент АБО 7 у одиничне значення, що заблокує подальше рахування, фіксуючи на інформаційному виході І лічильника 2 останній код N* - 1, а на виході блока 4 - останнє число. 2 UA 114262 U 5 10 15 20 Комутатор 8 приймає значення з виходу блока 5 на вхід Y управління, вибирає з виходів блоків 3 і 4 найменше число та видає його на вихід S пристрою, формуючи таким чином послідовність, впорядковану за зростанням значень чисел. Крім того, впорядкована послідовність чисел подається з виходу комутатора 8 на інформаційні входи І регістрів 9 і 10 та перший вхід блока 11. Регістр 9 приймає перше число впорядкованої послідовності за заднім фронтом сигналу скидання та видає його на вихід В пристрою як базове значення впорядкованої послідовності. Регістр 10 приймає числа послідовності за переднім фронтом синхроімпульсів та видає їх на другий вхід блока 11. Блок 11 знаходить різницю кожного наступного і попереднього числа впорядкованої послідовності та видає її на інформаційний вхід І регістра 12. Регістр 12 після нульового значення приймає за задніми фронтами синхросигналів послідовність різниць сусідніх наступних та попередніх чисел та видає її на вихід G пристрою, утворюючи компактну форму представлення впорядкованої послідовності. Пристрій може бути використаний для побудови обчислювальних систем, що виконують сортування числових даних з компактним представленням впорядкованих послідовностей. Джерела інформації: 1. Мельник А.О. Архітектура комп'ютера. Наукове видання. - Луцьк: Волинська обласна друкарня, 2008. - 470 с, стор. 438, рис. 12.16; 2. Патент на корисну модель № 101606 Україна, МПК G 06 F 7/022 (2006.01) Пристрій для впорядкування чисел / О.В. Дрозд, С А. Нестеренко, Ю.В.Дрозд, Д.В.Щербак. № u 2015 02306; Заявлено 16.03.2015, Опубл. 25.09.2015. Бюл. № 18. ФОРМУЛА КОРИСНОЇ МОДЕЛІ 25 30 35 40 45 Пристрій для впорядкування чисел, що містить перший та другий лічильники, перший і другий блоки пам'яті, блок порівняння, перший і другий елементи АБО та комутатор, при цьому вхід скидання пристрою підключено до входів скидання першого та другого лічильників, тактовий вхід пристрою підключено до синхровходів першого та другого лічильників, інформаційні виходи яких підключено до адресних входів відповідно першого та другого блоків пам'яті, а виходи переповнення підключено до перших входів відповідно першого та другого елементів АБО, виходи яких підключено до входів блокування рахування відповідно першого та другого лічильників, виходи першого та другого блоків пам'яті підключено відповідно до першого та другого інформаційних входів комутатора та підключено відповідно до першого та другого входів блока порівняння, вихід якого підключено до другого інверсного входу першого елемента АБО, другого входу другого елемента АБО та управляючого входу комутатора, вихід якого підключено до виходу послідовності пристрою, який відрізняється тим, що введено: перший, другий та третій регістри і блок вирахування, при цьому вхід скидання пристрою підключено до синхровходу першого регістра та входу скидання третього регістра, тактовий вхід пристрою підключено до синхровходу другого та третього регістра, вихід комутатора підключено до інформаційних входів першого та другого регістрів і першого входу блока вирахування, вихід першого регістра підключено до виходу базового значення пристрою, вихід другого регістра підключено до другого входу блока вирахування, вихід якого підключено до інформаційного входу третього регістра, вихід якого підключено до виходу компактної форми послідовності пристрою. 3 UA 114262 U Комп’ютерна верстка М. Мацело Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4