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

Реферат: Винахід належить до обчислювальної техніки і може бути використаний у спеціалізованих комп'ютерних системах з вертикальною обробкою даних. Пристрій для визначення максимального числа з групи чисел містить тактових вхід, вхід початкової установки, m однорозрядних інформаційних входів, m блоків порівняння, кожен з яких містить перший Dтригер, перший елемент І-НІ з відкритим колектором, перший елемент АБО, перший елемент I, другий D-тригер. Згідно з винаходом в пристрій додатково введені: n-розрядний зсувний регістр з інвертованим виходом, n-розрядний зсувний регістр, вихід результату обчислення максимального числа, вихід результату обчислення мінімального числа, два блоки порівняння; у кожному блоці порівняння додатково введений третій D-тригер, другий елемент І-НІ з відкритим колектором, другий елемент АБО, другий елемент I. Введення у пристрій нових елементів і зв'язків між ними забезпечило розширення функціональних можливостей шляхом одночасного визначення максимального та мінімального чисел як з одновимірного масиву із m чисел, так і з двовимірного масиву із (mр) чисел, та при цьому забезпечило підвищення швидкодії. UA 110187 C2 (12) UA 110187 C2 UA 110187 C2 5 10 15 20 25 30 35 40 45 50 55 60 Винахід належить до обчислювальної техніки і може бути використаний у спеціалізованих комп'ютерних системах з вертикальним опрацюванням даних для підвищення швидкодії та зменшення затрат обладнання при визначенні максимального та мінімального чисел як з одновимірного, так і з двовимірного масивів чисел, які надходять послідовним кодом. Відомий пристрій для визначення екстремальних значень послідовності чисел [А.с. СССР № 1462291, кл. G06F 7/00, 1989], який містить сім регістрів, два комутатори, три схеми порівняння, два елементи НІ, два елементи I та три елементи затримки. Однак даний пристрій має малу швидкодію. Відомий пристрій для визначення максимального числа з групи чисел [Деклараційний патент на винахід № 29630, кл. G06F 7/04, 2000], який містить тактовий вхід, вхід початкової установки, m інформаційних входів, де m - кількість чисел, які порівнюються, вихід результату, mn блоків порівняння, де n - розрядність чисел, які порівнюються, кожен з яких містить Dтригер, елемент І-НІ з відкритим колектором, елемент АБО, елемент I. Однак даний пристрій для своєї реалізації вимагає великої кількості входів-виходів та великих затрат обладнання. Найбільш близьким до запропонованого пристрою є пристрій для визначення максимального числа з групи чисел [Патент України на винахід № 103106, кл. G06F 7/04, 2013], який містить тактовий вхід, вхід початкової установки, m однорозрядних інформаційних входів, де m - кількість чисел, які порівнюються, вихід результату обчислення максимального числа, m блоків порівняння, кожен з яких містить перший D-тригер, елемент І-НІ з відкритим колектором, елемент АБО, елемент I, другий D-тригер. Однак даний пристрій має обмежені функціональні можливості, оскільки визначає тільки максимальне число з групи чисел (одновимірного масиву). В основу винаходу поставлено задачу створити пристрій для одночасного визначення максимального та мінімального чисел як з одновимірного масиву із m чисел, так і з двовимірного масиву із (mp) чисел, у якому введення нових елементів і зв'язків між ними дозволило б збільшити функціональні можливості. Поставлена задача вирішується тим, що пристрій для визначення максимального числа з групи чисел, що містить тактовий вхід, вхід початкової установки, m однорозрядних інформаційних входів, де m - кількість чисел, які одночасно опрацьовуються, вихід результату обчислення максимального числа, m блоків порівняння, кожен з яких містить перший D-тригер, елемент І-НІ з відкритим колектором, елемент АБО, елемент I, другий D-тригер, при цьому тактові входи першого та другого D-тригера всіх блоків порівняння з'єднані з тактовим входом, входи встановлення в одиницю першого та другого D-тригера всіх блоків порівняння з'єднані з входом початкової установки, у кожному j-у (j=1, …, m) блоці порівняння інформаційний вхід першого D-тригера з'єднаний з j-м однорозрядним інформаційним входом, прямий вихід першого D-тригера з'єднаний з першим входом елемента І-НІ з відкритим колектором та першим входом елемента АБО, вихід якого з'єднаний з першим входом елемента I, вихід якого з'єднаний з інформаційним входом другого D-тригера, вихід якого з'єднаний з другим входом елемента I та другим входом елемента І-НІ з відкритим колектором, згідно з винаходом додатково містить n-розрядний зсувний регістр з інвертованим виходом, де n - розрядність чисел, що порівнюються, n-розрядний зсувний регістр, вихід результату обчислення мінімального числа, вхід скиду регістрів, два блоки порівняння, а у кожному блоці порівняння третій D-тригер, другий елемент І-НІ з відкритим колектором, другий елемент АБО, другий елемент I, причому у кожному блоці порівняння тактовий вхід третього D-тригера з'єднаний з тактовим входом, вхід встановлення в одиницю третього D-тригера з'єднаний з входом початкової установки, інвертований вихід першого D-тригера з'єднаний з першим входом другого елемента І-НІ з відкритим колектором та першим входом другого елемента АБО, вихід якого з'єднаний з першим входом другого елемента I, вихід якого з'єднаний з інформаційним входом третього D-тригера, вихід якого з'єднаних з другим входом другого елемента I та другим входом другого елемента І-НІ з відкритим колектором, вхід n-розрядного зсувного регістра з інвертованим виходом з'єднаний з виходом елемента І-НІ з відкритим колектором всіх блоків порівняння та другим входом елемента АБО всіх блоків порівняння, вхід n-розрядного зсувного регістра з'єднаний з виходом другого елемента І-НІ з відкритим колектором всіх блоків порівняння та другим входом другого елемента АБО всіх блоків порівняння, тактові входи nрозрядного зсувного регістра з інвертованим виходом та n-розрядного зсувного регістра з'єднані з тактовим входом, входи скиду n-розрядного зсувного регістра з інвертованим виходом та nрозрядного зсувного регістра з'єднані з входом скиду регістрів, паралельний вихід n-розрядного зсувного регістра з інвертованим виходом з'єднаний з виходом результату обчислення максимального числа, послідовний вихід n-розрядного зсувного регістра з інвертованим 1 UA 110187 C2 5 10 15 20 25 30 35 40 45 50 55 виходом з'єднаний з інформаційним входом першого D-тригера (m+1)-го блока порівняння, паралельний вихід n-розрядного зсувного регістра з'єднаний з виходом результату обчислення мінімального числа, послідовний вихід n-розрядного зсувного регістра з'єднаний з інформаційним входом першого D-тригера (m+2)-го блока порівняння. Введення у пристрій двох додаткових блоків порівняння, (m+2) D-тригерів, (m+2) елементів I, (m+2) елементів І-НІ з відкритим колектором, (m+2) елементів АБО, n-розрядного зсувного регістра з інвертованим виходом, n-розрядного зсувного регістра, входу скиду регістрів та виходу результату обчислення мінімального числа забезпечило розширення функціональних можливостей шляхом одночасного визначення максимального та мінімального чисел як з одновимірного масиву із m чисел, так і з двовимірного масиву із (mр) чисел. На кресленні представлена схема пристрою для визначення максимального числа з групи чисел, де: 1 - тактовий вхід, 2 - вхід початкової установки, 31, …, 3m - однорозрядні інформаційні входи, 4 - n-розрядний зсувний регістр з інвертованим виходом, 5 - n-розрядний зсувний регістр, 6 вихід результату обчислення максимального числа, 7 - вихід результату обчислення мінімального числа, 81, …, 8m+2 - блоки порівняння; у кожному блоці порівняння 9 - перший Dтригер, 10 - другий D-тригер, 11 - перший елемент I-HI з відкритим колектором, 12 - перший елемент АБО, 13 - перший елемент I, 14 - третій D-тригер, 15 - другий елемент І-НІ з відкритим колектором, 16 - другий елемент АБО, 17 - другий елемент I, 18 - вхід скиду регістрів. Пристрій для визначення максимального числа з групи чисел містить тактових вхід 1, вхід початкової установки 2, однорозрядні інформаційні входи 31, …, 3m, n-розрядний зсувний регістр з інвертованим виходом 4, n-розрядний зсувний регістр 5, вихід результату обчислення максимального числа 6, вихід результату обчислення мінімального числа 7, блоки порівняння 81, …, 8m+2; у кожному блоці порівняння перший D-тригер 9, другий D-тригер 10, перший елемент І-НІ з відкритим колектором 11, перший елемент АБО 12, перший елемент I 13, третій D-тригер 14, другий елемент І-НІ з відкритим колектором 15, другий елемент АБО 16, другий елемент I 17, вхід скиду регістрів 18. Тактові входи D-тригерів 9, 10 та 14 всіх блоків порівняння з'єднані з тактовим входом 1, входи встановлення в одиницю D-тригерів 9, 10 та 14 всіх блоків порівняння з'єднані з входом початкової установки 2, у кожному k-у (k=1, …, m+2) блоці порівняння 8k прямий вихід першого D-тригера 9 з'єднаний з першим входом першого елемента І-НІ з відкритим колектором 11 та першим входом першого елемента АБО 12, вихід якого з'єднаний з першим входом першого елемента I 13, вихід якого з'єднаний з інформаційним входом другого D-тригера 10, вихід якого з'єднаний з другим входом першого елемента I 13 та другим входом першого елемента І-НІз відкритим колектором 11, інвертований вихід першого D-тригера 9 з'єднаний з першим входом другого елемента І-НІ з відкритим колектором 15 та першим входом другого елемента АБО 16, вихід якого з'єднаний з першим входом другого елемента I 17, вихід якого з'єднаний з інформаційним входом третього D-тригера 14, вихід якого з'єднаних з другим входом другого елемента I 17 та другим входом другого елемента І-НІ з відкритим колектором 15, у кожному j-у (j=1, …, m) блоці порівняння 8j інформаційний вхід першого D-тригера 9 з'єднаний з j-м однорозрядним інформаційним входом 3j, вхід n-розрядного зсувного регістра з інвертованим виходом 4 з'єднаний з виходом першого елемента І-НІ з відкритим колектором 11 всіх блоків порівняння та другим входом другого елемента АБО 13 всіх блоків порівняння, вхід nрозрядного зсувного регістра 5 з'єднаний з виходом другого елемента І-НІ з відкритим колектором 15 всіх блоків порівняння та другим входом другого елемента АБО 17 всіх блоків порівняння, тактові входи n-розрядного зсувного регістра з інвертованим виходом 4 та nрозрядного зсувного регістра 5 з'єднані з тактовим входом 1, входи скиду n-розрядного зсувного регістра з інвертованим виходом 4 та n-розрядного зсувного регістра 5 з'єднані з входом скиду регістрів 18, паралельний вихід n-розрядного зсувного регістра з інвертованим виходом 4 з'єднаний з виходом результату обчислення максимального числа 6, послідовний вихід nрозрядного зсувного регістра з інвертованим виходом 4 з'єднаний з інформаційним входом першого D-тригера 9 (m+1)-o блока порівняння 8m+1, паралельний вихід n-розрядного зсувного регістра 5 з'єднаний з виходом результату обчислення мінімального числа 7, послідовний вихід n-розрядного зсувного регістра 5 з'єднаний з інформаційним входом першого D-тригера 9 (m+2)о блока порівняння 8m+2. Пристрій для визначення максимального числа з групи чисел працює наступним чином. Перед початком роботи імпульсом початкової установки, який надходить із входу початкової установки 2, тригери 9, 10 і 14 у кожному блоці порівняння 8 k, встановлюються у лог. 1, а імпульсом скиду, який надходить з входу скиду регістрів 18, всі розряди регістрів 4 і 5 2 UA 110187 C2 5 10 15 20 25 30 35 40 45 50 55 60 встановлюються у лог. 1. У кожному блоці порівняння 8k інформація з виходів тригерів 7, 8 і 14 (лог. 1) встановлює на виходах елементів I 13 і 17 сигнал лог. 1. При одночасному визначенні максимального та мінімального чисел в одновимірному масиві із m чисел дані на інформаційні входи 31, …, 3m надходять порозрядно старшими розрядами вперед. У першому такті роботи пристрою у кожному блоці порівняння 8 k дані з інформаційних входів тригерів 9, 10 і 14 записуються у ці тригери. При цьому у тригер 9 j-го блока порівняння 8j записується старший розряд j-го числа, у тригер 9 (m+1)-го блока порівняння 8(m+1) - лог. 0, а у тригер 9 (m+2)-го блока порівняння 8(m+2) - лог. 1. У тригери 10 і 14 всіх блоків порівняння 8k записуються лог. 1, які дозволяють участь j-го числа у визначенні відповідно максимального та мінімального значень. У кожному блоці порівняння 8k дані з виходу тригера 9 надходять на перший вхід елемента І-НІ з відкритим колектором 11 та перший вхід елемента АБО 12. Лог. 1 з виходу тригера 10 (сигнал управління) надходить на другий вхід елемента І-НІ з відкритим колектором 11 та другий вхід елемента I 13. Дані з виходів елементів І-НІ з відкритим колектором 11 всіх блоків порівняння 8 об'єднуються по монтажному I. Аналогічно, дані з виходів елементів І-НІ з відкритим колектором 15 всіх блоків порівняння 8 також об'єднуються по монтажному I. У випадку, коли старші розряди чисел, що порівнюються, рівні нулю, то на виході елементів І-НІ з відкритим колектором 11 формується лог. 1, у інших випадках - лог. 0, а на виходах елементів I-HI з відкритим колектором 15 формується лог. 0, у інших випадках - лог. 1. Інформація з виходів елементів І-НІ з відкритим колектором 11 (старший розряд максимального числа) надходить на вхід n-розрядного зсувного регістра з інвертованим виходом 4, а інформація з виходів елементів І-НІ з відкритим колектором 15 (старший розряд мінімального числа) надходить на вхід n-розрядного зсувного регістра 5. При лог. 1 на других входах елементів АБО 12 блоків порівняння 81, …, 8(m+2) на їхніх виходах встановлюється сигнал лог. 1, а при лог. 0 - інформація з прямих виходів тригерів 9. У випадку, коли на другі входи елементів АБО 16 блоків порівняння 81, …, 8(m+2) надходить лог. 1, то на їхніх виходах встановлюється сигнал лог. 1, а при лог. 0 - інформація з інверсних виходів тригерів 9. Інформація з виходів елементів АБО 12 формує на виходах елементів I 13 сигнали управління, які надходять на інформаційні входи тригерів 10, а інформація з виходів елементів АБО 16 формує на виходах елементів I 17 сигнали управління, які надходять на інформаційні входи тригерів 14. Другим тактовим імпульсом у кожному блоці порівняння 8 виконується запис інформації у тригери 9, 10 і 14. При цьому дані із виходів елементів I-HI з відкритим колектором 11 та 15 запишуться, відповідно, у n-розрядний зсувний регістр з інвертованим виходом 4 і n-розрядний зсувний регістр 5. У тригерах 9 отримуємо значення наступних розрядів чисел, які порівнюються, а у тригерах 10 і 14 - значення, які дозволяють (лог. 1) або забороняють (лог. 0) участь даних блоків порівняння у подальшому формуванні максимального (тригер 10) та мінімального (тригер 14) чисел. На виходах елементів І-НІ з відкритим колектором 11 та 15 формуються відповідно наступні розряди максимального (інвертоване значення) та мінімального чисел. Формування наступних розрядів результату та сигналів управління виконуються аналогічно. За (n+1) тактів, де n - розрядність чисел, у n-розрядному зсувному з інвертованим виходом 4 отримаємо інвертоване значення максимального числа, а в n-розрядному зсувному 5 мінімальне значення числа із одновимірного масиву з m чисел. Інформація з виходів регістрів 4 і 5 використовується для одночасного визначення максимального та мінімального чисел з наступного масиву з m чисел. Таке визначення здійснюється шляхом її порозрядного порівняння з наступними m числами. При одночасному визначенні максимального та мінімального чисел у двовимірному масиві із (mр) чисел, які надходять порозрядно старшими розрядами вперед, робота пристрою здійснюється аналогічно до роботи при визначені максимального та мінімального чисел в одновимірному масиві із m чисел з тією різницею, що в (n+1)-му такті відбувається скид в нуль тригерів 9, 10 і 14 у всіх блоках порівняння 8. Кількість тактів для одночасного визначення максимального та мінімального чисел у двовимірному масиві із (mp) чисел дорівнює (n+1)р. Тривалість такту роботи в даному пристрої рівна: T=tTг+3tI, де tTг - час запису інформації у тригер, tI - час затримки інформації при проходженні через логічні елементи типу АБО, І, І-НІ. Час обчислення максимального та мінімального чисел у цьому пристрої для масиву із m чисел рівний: tm=(tTг+3tI)(n+1), а для масиву із (mр) чисел: 3 UA 110187 C2 5 tmр=(tTг+3tI)(n+1)р, де р - кількість рядків масиву чисел, n - розрядність чисел. Затрати обладнання на реалізацію даного пристрою рівні: W Пp=(m+2)(3W Tг+6W I)+2W Pг, де m - кількість чисел, що опрацьовуються одночасно (кількість стовпців масиву чисел), W Tг затрати обладнання на реалізацію D-тригера, W I - затрати обладнання на реалізацію логічних елементів типу АБО, І, І-НІ, W Pг - затрати на реалізацію n-розрядного зсувного регістра. ФОРМУЛА ВИНАХОДУ 10 15 20 25 30 35 40 45 Пристрій для визначення максимального числа з групи чисел, який містить тактовий вхід, вхід початкової установки, m однорозрядних інформаційних входів, де m - кількість чисел, які одночасно опрацьовуються, вихід результату обчислення максимального числа, m блоків порівняння, кожен з яких містить перший D-тригер, елемент І-НІ з відкритим колектором, елемент АБО, елемент I, другий D-тригер, при цьому тактові входи першого та другого Dтригерів всіх блоків порівняння з'єднані з тактовим входом, входи встановлення в одиницю першого та другого D-тригерів всіх блоків порівняння з'єднані з входом початкової установки, у кожному j-у (j=1, …, m) блоці порівняння інформаційний вхід першого D-тригера з'єднаний з j-м однорозрядним інформаційним входом, прямий вихід першого D-тригера з'єднаний з першим входом елемента І-НІ з відкритим колектором та першим входом елемента АБО, вихід якого з'єднаний з першим входом елемента I, вихід якого з'єднаний з інформаційним входом другого D-тригера, вихід якого з'єднаний з другим входом елемента I та другим входом елемента I-HI з відкритим колектором, який відрізняється тим, що додатково містить n-розрядний зсувний регістр з інвертованим виходом, де n - розрядність чисел, що порівнюються, n-розрядний зсувний регістр, вихід результату обчислення мінімального числа, вхід скиду регістрів, два блоки порівняння, а у кожному блоці порівняння додатково включені третій D-тригер, другий елемент І-НІ з відкритим колектором, другий елемент АБО, другий елемент I, причому у кожному блоці порівняння тактовий вхід третього D-тригера з'єднаний з тактовим входом, вхід встановлення в одиницю третього D-тригера з'єднаний з входом початкової установки, інвертований вихід першого D-тригера з'єднаний з першим входом другого елемента І-НІз відкритим колектором та першим входом другого елемента АБО, вихід якого з'єднаний з першим входом другого елемента I, вихід якого з'єднаний з інформаційним входом третього Dтригера, вихід якого з'єднаних з другим входом другого елемента I та другим входом другого елемента І-НІ з відкритим колектором, вхід n-розрядного зсувного регістра з інвертованим виходом з'єднаний з виходом елемента І-НІ з відкритим колектором всіх блоків порівняння та другим входом елемента АБО всіх блоків порівняння, вхід n-розрядного зсувного регістра з'єднаний з виходом другого елемента І-НІ з відкритим колектором всіх блоків порівняння та другим входом другого елемента АБО всіх блоків порівняння, тактові входи n-розрядного зсувного регістра з інвертованим виходом та n-розрядного зсувного регістра з'єднані з тактовим входом, входи скиду n-розрядного зсувного регістра з інвертованим виходом та n-розрядного зсувного регістра з'єднані з входом скиду регістрів, паралельний вихід n-розрядного зсувного регістра з інвертованим виходом з'єднаний з виходом результату обчислення максимального числа, послідовний вихід n-розрядного зсувного регістра з інвертованим виходом з'єднаний з інформаційним входом першого D-тригера (m+1)-го блока порівняння, паралельний вихід nрозрядного зсувного регістра з'єднаний з виходом результату обчислення мінімального числа, послідовний вихід n-розрядного зсувного регістра з'єднаний з інформаційним входом першого D-тригера (m+2)-го блока порівняння. 4 UA 110187 C2 Комп’ютерна верстка Д. Шеверун Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5