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

Реферат: Пристрій визначення залишку багаторозрядного числа містить n-розрядний регістр зсуву, вхід якого підключений до шини запису кодового представлення числа. В нього додатково введено шину запису кодового представлення модуля Р, яка підключена до першого входу додатково введеного к+1-розрядного регістра зсуву, другий адресний вхід, якого підключений до першого виходу додатково введеного блока управління. UA 68872 U (54) ПРИСТРІЙ ВИЗНАЧЕННЯ ЗАЛИШКУ БАГАТОРОЗРЯДНОГО ЧИСЛА UA 68872 U UA 68872 U 5 10 15 20 25 30 35 40 45 50 55 60 Корисна модель належить до пристроїв опрацювання та перетворення даних, і може бути використана в системах передавання інформації, а також захисту даних від помилок та несанкціонованого доступу. n Відомий пристрій визначення залишку шляхом згортки по непарному модулю Р = 2 -1, який містить и-розрядний регістр і логічні схеми [1]. Недоліком такого пристрою є велика апаратна складність та функціональна обмеженість, що ускладнює його застосування при визначенні залишку багаторозрядних двійкових чисел з 10 30 числом розрядів 2 …2 , а також не забезпечує визначення залишку по довільному цілочисельному багаторозрядному модулю Р. Відомий також пристрій обчислення залишку шляхом згортки унітарного коду числа, який містить лічильник і логічні схеми [2]. Недоліком такого пристрою є низька швидкодія, що обмежує його функціональні можливості при визначенні залишку багаторозрядних чисел. Найбільш близьким за технічною суттю до корисної моделі, що заявляється, є пристрій визначення залишку шляхом згортки по непарному модулю, який містить лічильник, nрозрядний регістр зсуву і k-розрядний суматор, охоплений зворотнім зв'язком, шину запису кодового представлення числа [1]. Недоліком пристрою є велика апаратна складність обумовлена наявністю багаторозрядного двійкового суматора з числом розрядів рівним довжині коду k, багаторозрядного модуля Р та обмежені функціональні можливості визначення залишку тільки по непарному модулю. В основу корисної моделі поставлена задача зменшення апаратної складності та розширення функціональних можливостей пристрою обчислення залишку багаторозрядного двійкового по довільному цілочисельному багаторозрядному модулю р. Поставлена задача вирішується завдяки тому, що, згідно з корисною моделлю, пристрій, який містить n-розрядний регістр зсуву, вхід якого підключений до шини запису кодового представлення числа, додатково введено шину запису кодового представлення модуля Р, яка підключена до першого входу додатково введеного k+1-розрядного регістра зсуву, другий адресний вхід, якого підключений до першого виходу додатково введеного блока управління, другий і третій виходи якого відповідно підключені до перших входів додатково введених третього і четвертого k+1-розрядних регістрів зсуву, виходи, яких відповідно підключені до першого і другого входів додатково введеного мультиплексора, третій вхід якого підключений до четвертого виходу блока управління, а вихід підключений до першого входу додатково введеного накопичувального суматора, другий вхід якого підключений до виходу другого k+1розрядного регістра зсуву, а вихід з'єднаний з другим входом блока управління і додатково введеною вихідною шиною кодового представлення залишку. Суть корисної моделі пояснюється тим, що в основу роботи пристрою поставлено алгоритм обчислення залишку багаторозрядного двійкового числа Y по багаторозрядному цілочисельному модулю Р згідно з рекурсивним виразом: bі = [р]м + 2bi-1 + аi і = n, n-1,…,1, (1) де и - розрядність числа Y, з якого визначається залишок bi, аi - біти двійкового числа Y, починаючи зі старшого розряду аn, [Р]м - k +1 розрядна мантиса доповнюючого коду модуля Р, bі - текуче кодове значення залишку (bi-1 = 0). Корисна модель ілюструється кресленнями, де показано структурну схему пристрою, де, 1 перший n-розрядний регістр зсуву, 2 - шина запису кодового представлення числа Y, 3 - шина запису кодового представлення модуля Р, 4 - блок управління, 5 - другий k+1-розрядний регістр зсуву, 6 - третій k+1-розрядний регістр зсуву, 7 - четвертий k+1-розрядний регістр зсуву, 8 однорозрядний накопичувальний суматор, 9 - мультиплексор, 10 - вихідна шина кодового представлення залишку bi. Пристрій працює таким чином. На початку циклів визначення залишку числа Y у перший n-розрядний регістр зсуву 1 і другий k+1-розрядний регістр зсуву 5, згідно з адресними сигналами блока управління 4, відповідно записуються двійковий код числа Y та мантиса доповнюючого коду модуля Р, а в третій 6 і четвертий 7 k+1-розрядні регістри зсуву записуються нулі. На початку кожного наступного циклу роботи пристрою на четвертому виході блока управління 4 формується сигнал "1", що дозволяє зсув на один розряд в бік старших розрядів на коду залишку bi-1 у регістрі 6 та запис старшого біта числа Y аi у молодший розряд третього регістра 6, що відповідає запису в цей регістр 2 bi-1 + аi В кожному текучому циклі роботи пристрою одночасно через мультиплексор 9 на входи однорозрядного накопичувального суматора 8, порозрядно зчитується код мантиси модуля Р([Р]м) розрядністю k + 1 та код відповідного регістра 6 або 7. При цьому одночасно 1 UA 68872 U 5 10 15 20 25 відбувається запис нового залишку bi у відповідний регістр 7 або 6 згідно адресних входів блока управління 4. У результаті на протязі k + 1 такту у однорозрядному накопичувальному суматорі 8 порозрядно формується сума кодів згідно виразу (1), яка завершується формуванням на виході суматора 8 останнього біта "0" або "1", значення якого надходить на другий вхід блока управління 4. При цьому, якщо вказаний біт є "1", то це означає, що текучий залишок bi у регістрі 6 менший значення модуля р (bi < Р) і відбувається зсув інформації в регістрі 6 на один розряд в бік старших розрядів, а в молодший розряд записується наступний молодший біт числа Y. При формуванні на виході суматора сигналу "0", це означає, що bi  Р і на вхід мультиплексора 9 подається сигнал "0", який формується на четвертому виході блока управління 4 і починається новий цикл сумування у суматорі 8 кодів [Р] м другого регістра 5 та четвертого регістра 7, та запис інформації у регістр 6 до появи біта "0" в кінці k+1 такту на виході суматора 8. У результаті виконується попередній цикл. Після зчитування останнього молодшого біта числа Y аi в одному з регістрів 6 або 7 формується код залишку bi, який зчитується через мультиплексор 9 і суматор 8 на вихідну шину 10 пристрою, при цьому на виході другого регістра 5 формується сигнал "0". Приклад, визначення залишку по непарному модулю: Припустимо Y = 100(10) 1100100(2), Р = 11(10) = 1011. Тоді b1 = res100(mod11) = 1. Потрібно визначити b1 над двійковими кодами Y та Р: 1. У перший регістр 1 записуємо число Y = 1100100(2) 2. У другий регістр 5 записуємо k+1 розрядну мантису доповнюючого коду [Р]м = 10101, яку отримуємо наступним чином: код числа Р записуємо з нульовим бітом у старшому розряді: Р = 01011(2) інвертуємо цей код: Р = 10100 додаємо до цього коду "1": [P]м 30 35 10100  1.  10101 3. У третій регістр 6 і четвертій 7 регістри записуємо нулі, тобто bi = 00000 bi-1 = 00000; i = n, n-1,…1. 4. Блок управління 4 формує біт "0” на керуючий вхід мультиплексора 9, що дозволяє відповідно записувати та зчитувати інформацію з другого регістра 5 і третього регістра 6(bi) та четвертого регістра 7(bi-1) та записувати коди порозрядно вихідні коди суматора у четвертій регістр 7. 5. В кожному циклі роботи пристрою виконується сумування мантиси доповнюючого коду модуля Р з значенням текучого залишку bi-m. У нашому випадку має місце така операція [p]м 10101  2bi  ai 00001 [bi  m 1]м 11110 40 i  n 1 6. Отримуємо мантису доповнюючого коду цієї операції додавання. Код цієї мантиси записуємо у регістр 6(bi) або 7(bi-1). Отримане значення "1" в k + 1 такті сумування показує, що bi-1 < P. Тоді відбувається зсув інформації у відповідному регістрі 6 або 7 і запис у молодший розряд ai-1, біта числа Y, тобто 10101 P  bi  00011 i  n  2 11100 10101 P  bi  00010 i  n  3 11011 10101 P  bi 45  01100 i  n  4 00011 2 UA 68872 U 7. Отриманий біт "0" надходить в блок управління, який запам'ятовує його і переключає мультиплексор 9, що приводить до подвоєння коду залишку в регістрі 7(bi-1) та запису в молодший розряд текучого біта числа Y. 8. Після цього використовується операція сумування згідно з розрахунками: 10101  5 10101  00011 10100 10101  00110  01100 11011 00001 b1 Тобто bi = 00001(2) = 1(10), що відповідає bi = res100(mod11) = 1. Аналогічні розрахунки можна виконати при визначенні залишку по парному модулю: Припустимо Y = 25(10) = 11001(2), p = 6(10) = 110. [P] p 10 1010  0001  1011 1010  1  0110  1001 1010.  м Запишемо Виконаємо наступні операції: 1010 0011  1101  0110 0000 Оскільки в старшому розряді "0", то цей залишок зсувається на біт і додається новий біт числа: 1010  0000  1010 1010  0001  b1 1011 Оскільки використані всі біти числа Y i bi < Р, то b1 = 0001(2), що відповідає b1 = res25(mod6) 15 =1. При реалізації пристрою доцільно як регістри використати багаторозрядну флеш-пам'ять. 20 Джерела інформації: [1] Хетагуров Я.А., Руднев Ю.П. Повышение надежности цифровых устройств методами избыточного кодирования. - М.: Энергия, 1974. - 272с. [2] Новиков Л.Г., Шурыгин И.Т. Счѐтчики импульсов с коэффициентами счѐта, управляемыми с помощью двоичного кода. Журнал "Приборы и системы управления" № 6, 1972. - С. 30-31. 25 ФОРМУЛА КОРИСНОЇ МОДЕЛІ 30 35 Пристрій визначення залишку багаторозрядного числа, який містить n-розрядний регістр зсуву, вхід якого підключений до шини запису кодового представлення числа, який відрізняється тим, що додатково введено шину запису кодового представлення модуля Р, яка підключена до першого входу додатково введеного к+1-розрядного регістра зсуву, другий адресний вхід, якого підключений до першого виходу додатково введеного блоку управління, другий і третій виходи якого відповідно підключені до перших входів додатково введених третього і четвертого к+1розрядних регістрів зсуву, виходи, яких відповідно підключені до першого і другого входів додатково введеного мультиплексора, третій вхід якого підключений до четвертого виходу блока управління, а вихід підключений до першого входу додатково введеного накопичувального суматора, другий вхід якого підключений до виходу другого к+1-розрядного регістра зсуву, а вихід з'єднаний з другим входом блока управління і додатково введеною вихідною шиною кодового представлення залишку. 3 UA 68872 U Комп’ютерна верстка Д. Шеверун Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 4