Числоімпульсний пристрій для множення

Реферат: Числоімпульсний пристрій для множення належить до засобів обчислювальної техніки і систем статистичної обробки інформації, цифрових взаємокореляторів та засобів паралельного розпізнавання образів на основі матриць великого числа пікселів оцифрованих зображень. Пристрій ґрунтується на обчисленні добутку двох чисел шляхом додаткового введення модульних лічильників у базисі Хаара-Крестенсона, входи яких з'єднані з вхідними шинами додатково введених матричних модульних перемножувачів та цифрового шифратора. Пристрій забезпечує отримання на виході двійкового цифрового значення добутку двох чисел, представлених унітарними кодами, та за допомогою запропонованого пристрою досягається підвищення швидкодії та регулярності структури для обчислення добутку двох чисел. UA 115182 C2 (12) UA 115182 C2 UA 115182 C2 5 10 15 20 25 30 35 40 45 50 55 60 Числоімпульсний пристрій для множення належить до засобів обчислювальної техніки і може бути використаний для множення чисел, представлених унітарним кодом у пристроях статистичної обробки інформації, цифрових взаємокореляторах та засобах паралельного розпізнавання образів шляхом опрацювання матриці великого числа пікселів оцифрованих зображень. Відомий аналог - пристрій множення [Грибок Н.И. Обуханич Р.-А.В. Квадратор, // А.С. СССР № 475619. - Бюллетень № 24. - 1975], який містить вхідну шину, лічильник, накопичувач, який дозволяє шляхом перемноження однакових чисел отримувати код їх квадрата. Недоліком такого пристрою є обмежені функціональні можливості та низька швидкодія, обумовлені тим, що даний пристрій визначає тільки квадрат одного числа, заданого унітарним 2 кодом, що дозволяє у взаємокореляторах вичислити тільки одну точку хіхі+0=х . Недоліком відомого пристрою також є низька швидкодія, обумовлена тим, що представлення інформації у лічильнику та накопичуючому суматорі відбувається у двійковій системі числення теоретикочислового базису Радемахера, що передбачає наявність наскрізних переносів у накопичуючому суматорі, які відбуваються після кожного імпульсу вхідного унітарного коду. Відомий прототип - числоімпульсний пристрій для множення [Николайчук Я.М. Числоимпульсное множительное устройство // А.С. СССР № 754414. - Бюллетень № 29). 1980], який містить лічильник, логічні елементи, перемножувач, накопичувач, який дозволяє тримати двійковий код добутку у базисі Радемахера шляхом перемноження двох нерівних чисел заданих унітарним кодом. Недоліком числоімпульсного множильного пристрою є низька швидкодія та значна структурна складність, які обумовлені тим, що даний пристрій містить двійковий лічильник та двійковий накопичуючий суматор, причому швидкодіюча реалізація двійкового синхронного лічильника з вхідними логічними елементами прискорення переносів та реалізація накопичувача на основі повних однорозрядних двійкових суматорів, які містять від 4 до 6 послідовно включених логічних елементів, характеризується низькою швидкодією та значною структурною складністю, що обмежує можливість реалізації їх великого числа в мікроелектронному кристалі матриці пікселів цифрової відеокамери. В основу винаходу поставлена задача вдосконалення числоімпульсного множильного пристрою шляхом додаткового введення модульних лічильників теоретико-числового базису Хаара-Крестенсона, входи яких з'єднані з вхідними шинами додатково введених матричних модульних перемножувачів та цифрового шифратора, що дозволяє отримати підвищення на 12 порядки швидкодії, по відношенню до відомого прототипу, а також більш високу регулярність структури за рахунок реалізації модульних лічильників на регістрах зсуву та матричних модульних перемножувачів на елементах І-НІ. Поставлена задача вирішується завдяки тому, що числоімпульсний пристрій для множення містить першу і другу вхідні шини, лічильник і помножувач, згідно з винаходом, додатково введені перша і друга групи К модульних лічильників у базисі Хаара-Крестенсона, група К модульних матричних перемножувачів, перша вхідна шина з'єднана з входами першої групи модульних лічильників, друга шина з'єднана з входами другої групи модульних лічильників, виходи яких підключені до відповідних входів додатково введених матричних перемножувачів, другі входи яких підключені до виходів відповідних модульних лічильників першої групи, а виходи підключені до входів додатково введеного шифратора, виходи якого є виходами пристрою. Винахід ілюструється кресленням, де на фіг. 1 показана структурна схема пристрою: 1 перша вхідна шина; 2 - перша група модульних лічильників; 3 - друга вихідна шина; 4 - друга група модульних лічильників; 5 - група матричних модульних перемножувачів; 6 - шифратор. На фіг. 2 показана структурна схема модульного лічильника, на фіг. 3 - структурна схема модульного матричного перемножувача у базисі Хаара-Крестенсона по модулю Р, а на фіг. 4 приклад реалізації модульного матричного перемножувача для Р=7. Пристрій працює наступним чином: Перед початком кожного циклу множення всі Д-тригери модульних лічильників пристрою окремою мікрокомандою скидаються в "0", крім нульового тригера, який встановлюється в стан "1" (на структурній схемі не показано). При синхронному надходженні кожної пари імпульсів унітарних кодів чисел, що перемножуються, на вхідні шини (1, 3) у модульних лічильниках першої (2) і другої (4) групи накопичуються коди залишків системи залишкових класів базису Хаара-Крестенсона, які одночасно надходять на входи відповідних модульних матричних перемножувачів (5), на виходах яких формуються добутки у вигляді кодів Хаара-Крестенсона, згідно з виразом ai  bi mod Pi  di ; i  1, k , де ai та bi поточні залишки чисел X та Y згідно з виразами ai  resXmod Pi  ; bi  resYmod Pi  . 1 UA 115182 C2 5 10 15 20 Після закінчення циклу перемноження на виході матричних модульних перемножувачів (5) формується код добутку d1, d2 ,...di ,...dk у системі числення залишкових класів базису Крестенсона, який шифратором (6) перетворюється у двійковий код базису Радемахера, Принцип роботи пристрою полягає у тому, що в числоімпульсному множильному пристрої унітарні коди паралельно записуються у модульні лічильники системи залишкових класів теоретико-числового базису Хаара-Крестенсона, паралельно перемножуються у матричних модульних перемножувачах, а результати дешифруються з системи залишкових класів в двійкову систему числення. При цьому, як показано на фіг. 2 модульний лічильник базису Хаара-Крестенсона реалізується на основі регістра зсуву на Д-тригерах зі зворотним зв'язком TP1  T0 . На початку циклу перемноження макрокомандою y 0 всі Д-тригери T1  TP1 по R-входах встановлені в стан "0", а тригер T0 по S-входу в стан "1". У процесі надходження імпульсів унітарного коду на вхідну шину, яка з'єднана з С-входами синхронізації всіх Д-тригерів, на прямих виходах тригерів формуються модульні коди залишків ai , bi Хаара-Крестенсона з розрядністю Pi . Таким чином у процесі надходження вхідних імпульсів унітарного коду на модульні лічильники на їх виходах з часовою затримкою 2 , де  - тактова частота переключення логічних елементів кристала, на якому реалізується пристрій. Структура модульного матричного перемножувача, на входи якого надходять коди ХаараКрестенсона з першої і другої груп модульних лічильників, забезпечує виконання операції модульного множення також за інтервал часу 2 згідно з таблицею та структурою, показаної на фіг. 4 для P  7 . P7 ai bi 0 1 2 3 4 5 6 25 30 35 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 2 3 4 5 6 0 2 4 6 1 3 5 0 3 6 2 5 1 4 0 4 1 5 2 6 3 0 5 3 1 6 4 2 0 6 5 4 3 2 1 Приклад реалізації модульного матричного перемножувача для P  7 , показаний на фіг. 4, швидкодія якого визначається двома послідовно включеними логічними інвенторами, що складає 2 . Таким чином швидкодія числоімпульсного множильного пристрою згідно з винаходу визначається затримкою сигналів внаслідок переключення елементів матричного модульного лічильника    л , модульного матричного перемножувача п та шифратора    л  п     2  2  2  6 . Швидкодія відомого пристрою прототипу визначається сумарною швидкодією переключення JK-тригерів двійкового лічильника, мультиплексора та накопичуючого суматора, який складається з двійкового багаторозрядного суматора на основі повних тривходових однорозрядних суматорів з часом переключення 4  6 [Круліковський Б.Б. Архітектура високопродуктивних матричних прискорювачів операції множення у базисах Радемахера та Хаара / Б.Б. Круліковський, А.Я. Давлетова, В.Л. Кімак, І.Б. Албанський / Праці міжнародної наукової школи-семінару "Питання оптимізації обчислень (ПОО-XLII)" Київ: Інститут кібернетики імені В.М. Глушкова HАH України. 2015. - С. 47-49], а такоє 2 n , наскрізних переносів при 2 n розрядних унітарних кодів перемножуваних чисел. Тобто    л   м   р  2n c . 40 45 Наприклад, при діапазоні кодування вхідних чисел унітарним кодом 2 8 швидкодія відомого пристрою буде визначатися наступним чином   4  2  2  2  8  4  72 , в той час як у пристрої згідно з винаходом швидкодія складає 6 , не залежно від розрядності вхідних унітарних кодів перемножуваних чисел. Розрахунок системи взаємно простих модулів P , P2,..., Pi,..., Pk для числоімпульсного 1 множильного пристрою при k  8 виконується, виходячи з умови, що добуток модулів 2 UA 115182 C2 P , P2,..., Pi,..., Pk повинен перевищувати числове значення 216 . Цій умові відповідає наступний 1 набір модулів системи залишкових класів базису Крестенсона 5 7, 8, 9, 11, 13  72072  216  65536 . Таким чином на виходах матричних модульних перемножувачів, після завершения процесу множення, формується код Хаара-Крестенсона d1, d2,..., d5 , який дешифрується у 16-розрядний двійковий код базису Радемахера, Приклад: Нехай перемножуються числа X  100 , Y  200 ; X  Y  20000. Числа X тa Y представляться у базисі Хаара-Крестенсона наступним кодом: 10 Сформовані таким чином коди надходять на входи і-тих матричних модульних перемножувачів, на виходах яких формується код Хаара-Крестенсона результатів перемноження d1, d2,..., dk згідно з виразом: aibi mod Pi  di . 15 що відповідає дешифрованому значенню 20 000 у двійковій системі числення базису Радемахера 100111000100000. 20 25 30 Для спрощення структури шифратора (6) він реалізується по двокаскадній схемі, де в першому каскаді коди Хаара-Крестенсона по кожному модулю перетворюються в двійкові коди Радемахера, які в другому каскаді перетворюються в позиційний код двійкової системи числення, тобто 48-бітний код Хаара-Крестенсона дешифрується у 18-бітний код РадемахераКрестенсона та 16-бітний код Радемахера. При цьому в шифраторі (6) затримка сигналів складає 4 і загальна швидкодія пристрою буде складати 6  2  8 . Технічний результат: пристрій згідно з винаходом характеризується підвищеною на 1-2 порядки швидкодією по відношенню до відомого прототипу, а також більш високою регулярністю структури за рахунок реалізації модульних лічильників на регістрах зсуву, та матричних модульних перемножувачів на елементах І-НІ. ФОРМУЛА ВИНАХОДУ 35 Числоімпульсний пристрій для множення, що містить першу і другу вхідні шини, першу і другу групи К модульних лічильників у базисі Хаара-Крестенсона, групу К модульних матричних помножувачів, перша вхідна шина з'єднана з входами першої групи модульних лічильників, друга вхідна шина з'єднана з входами другої групи модульних лічильників, виходи яких 3 UA 115182 C2 підключені до відповідних перших входів матричних помножувачів, другі входи яких підключені до виходів відповідних модульних лічильників першої групи, а виходи підключені до входів шифратора, виходи якого є виходами пристрою. UA 115182 C2 Комп’ютерна верстка Г. Паяльніков Міністерство економічного розвитку і торгівлі України, вул. М. Грушевського, 12/2, м. Київ, 01008, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 5