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

Реферат: Винахід належить до області автоматики та обчислювальної техніки та може бути застосовано в комп'ютерних системах та компонентах, що функціонують у системі залишкових класів (СЗК). Пристрій для визначення лишків дійсних та комплексних чисел у системі залишкових класів містить перший вхідний регістр, перший суматор, лічильник, перший блок пам'яті констант (БПК), блок порівняння. Додатково до пристрою введені перша, друга та третя групи елементів АБО, другий БПК, перша, друга та третя групи елементів І, друга і третя вхідні регістри, блок множення, другий суматор, перший та другий елементи І, вентильний елемент. Технічним UA 114063 C2 (12) UA 114063 C2 результатом винаходу є розширення функціональних можливостей пристрою-прототипу за рахунок додаткового визначення лишків чисел, що представлені у комплексній області, за комплексним модулем ṁ=p+qi. UA 114063 C2 5 10 15 20 25 30 35 40 45 50 55 60 Винахід належить до області автоматики та обчислювальної техніки та може бути застосовано в комп'ютерних системах та компонентах, що функціонують у системі залишкових класів (СЗК). Відомий пристрій (аналог), що застосовується для перетворення позиційного двійкового коду А у лишок за довільним модулем mі КЛ [а.с. СРСР № 864278, МПК G06F 5/02, 1978]. Пристрій містить блок множення, блок порівняння, регістри, комбінаційний суматор, елементи І та АБО. Недолік аналога - низькі функціональні можливості пристрою. Це обумовлено неможливістю визначення лишків комплексних чисел. Відомий пристрій (аналог), що застосовується для перетворення позиційного двійкового коду А у лишок за довільним модулем mi, КЛ [а.с. СРСР № 1185339, МПК G06F 5/02, 1985]. Даний пристрій містить блок порівняння, вхідний та вихідний регістри, суматор, елементи І та АБО. Недолік аналога - низькі функціональні можливості пристрою. Це обумовлено неможливістю визначення лишків комплексних чисел. Відомий пристрій (аналог), що застосовується для перетворення позиційного двійкового коду А у лишок за довільним модулем mі КЛ [а.с. СРСР № 1105895, МПК G06F 11/08, 1983]. Пристрій для перетворення позиційного двійкового коду у лишок за довільним модулем mі, містить лічильник, до першого входу якого підключено перший (установчий) вхід пристрою, блок порівняння та перший елемент І, причому перший вхід першого елемента І є другим (тактовим) входом пристрою, вихід першого елемента І підключено до другого (рахункового) входу лічильника, перший вхід блока порівняння є входом подачі значення модуля mі. Недолік аналога - низькі функціональні можливості пристрою. Це обумовлено неможливістю визначення лишків комплексних чисел. Найбільш близьким за технічною сутністю до запропонованого винаходу є пристрій для перетворення позиційного двійкового коду у лишок за довільним модулем m [патент України № 92155, МПК G06F 11/08, 2014 р]. Пристрій для перетворення позиційного двійкового коду у лишок за довільним модулем mi, що містить: лічильник, до першого входу якого підключено перший установчий вхід пристрою, блок порівняння та перший елемент І, при цьому перший вхід першого елемента І є другим тактовим входом пристрою, вихід першого елемента І підключено до другого (рахункового) входу лічильника, перший вхід блока порівняння є входом подачі значення модуля mі, другий елемент І, блок пам'яті констант, блок множення, суматор і регістр, при цьому вихід суматора підключено до першого інформаційного входу регістра, вихід якого є виходом пристрою, який підключено до першого входу суматора та до другого входу блока порівняння, вихід якого є виходом ознаки кінця перетворення позиційного двійкового коду у лишок за довільним модулем mі, вихід лічильника підключено до входу блока пам'яті констант, вихід якого підключено до першого входу блока множення, до другого якого підключена шина подачі значення модуля mі, вихід блока множення підключено до другого входу суматора, другий вихід якого підключено до другого входу першого елемента І і до першого входу другого елемента І, вихід якого підключено до другого входу регістра, другий вхід другого елемента I підключено до другого входу пристрою, шина подачі числа, що перетворюється, підключена до третього входу регістра. Недолік прототипу - низькі функціональні можливості пристрою. Це обумовлено неможливістю визначення лишків комплексних чисел. В основу винаходу поставлена задача розширення функціональних можливостей пристроюпрототипу за рахунок додаткового визначення лишків чисел, що представлені у комплексній  області, за комплексним модулем m  p  qi . Поставлена задача вирішується тим, що містить перший вхідний регістр, перший суматор, лічильник, перший блок пам'яті констант (БПК), блок порівняння (БП), при цьому перший (тактовий) вхід пристрою підключено до входу лічильника, а вихід першого регістру підключено до перших входів першого суматора. В пристрій додатково введено першу, другу та третю групи елементів АБО, другий БПК, першу, другу та третю групи елементів І, другий і третій вхідні регістри, блок множення, другий суматор, перший та другий елементи І, вентильний. елемент, при цьому, вихід лічильника підключено до першого входу вентильного елемента, вихід якого підключено до перших входів першого та другого елементів І, до других входів яких підключено відповідно перша та друга керуючі шини пристрою (шини подачі сигналів ознак відповідно першого та другого режимів роботи пристрою). Виходи першого та другого елементів І підключено до входів відповідно першого та другого БПК, виходи яких через елементи АБО першої групи підключено до других входів першого суматора, вихід якого підключено до перших входів БП і до перших входів елементів І першої групи, виходи яких є виходом пристрою. Другий 1 UA 114063 C2 5 10 15 20 (інформаційний) вхід пристрою через елементи АБО другої групи підключено до входу першого регістру. Третій і четвертий (інформаційні) входи пристрою підключено до входів відповідно другого та третього вхідних регістрів, вихід третього вхідного регістру підключено до першого входу блока множення, до другого входу якого підключена шина подачі значення константи ρ множення, виходи другого регістру та блока множення підключено до входів другого суматора вихід якого підключено до входів елементів АБО другої групи. До перших входів елементів І другої та третьої груп підключено шини подачі значень відповідно першого та другого модулів пристрою, до других (відкриваючих) входів елементів І другої та третьої груп підключено відповідно перша та друга керуючі шини пристрою, виходи елементів І другої та третьої груп через елементи АБО третьої групи підключено до других входів БП, перший вихід якого підключено до других (відкриваючих) входів елементів І першої групи, а другий вихід БП підключено до другого (забороненого) входу вентильного елементу. Введення вказаних ознак дозволяє додатково, до операції визначення лишків αA(mod mi) дійсних чисел А за довільним модулем mі СЗК, здійснювати операцію визначення дійсних  лишків h комплексних чисел A  a  bi за довільним комплексним модулем m  p  qi СЗК, що  задана у комплексній числовій області. Відповідно до наслідків першої фундаментальної теореми. Гауса, за заданим комплексним 2 2 модулем m  p  qi , норма N якого дорівнює N=p +q , та при найбільшому загальному дільнику   (НЗД) чисел р і q (p, q)=1, комплексне число A  a  bi порівняно з одним і лише одним лишком   з ряду 0,1,2,…,N-2,N-1 чисел. Тобто, A  hmod m , де h - дійсне ціле число. Ізоморфізм між комплексними числами та їх дійсними лишками дає можливість реалізувати процес визначення лишків комплексних чисел за допомогою алгоритму визначення лишків числа у дійсній області. З теорії чисел відомо, що для двох чисел р і q таких, що НЗД (р, q)=1, знайдуться два цілих числа u та ν, такі, що виконується умова 25 u·p+ν·q=1. (1) Крім цього відомо, що існує таке число h, що визначається з наступного порівняння [а+(u·q-ν·р)·b]h(mod N) 30 (2) або (a+b·ρ)h(mod N), (3) де вираз ρ=u·q-ν-p (4) 35 за допомогою якого установлюється відповідність між комплексними та дійсними лишками чисел, називають коефіцієнтом ізоморфізму. В цьому випадку дійсний лишок h комплексного  числа A визначається за алгоритмом визначення дійсного лишку α дійсного числа А, тобто (5) hZ(mod N), 40 де 2 2 Z=a+b·ρ; N=p +q . 45 50 (6) Суть винаходу пояснює креслення. На (фіг.) представлена блок-схема винаходу, де: 1 - перший (тактовий) вхід пристрою; 2 лічильник імпульсів; 3 - перший регістр; 4 - перший суматор; 5 - вентильний елемент; 6, 7 перший та другий елементи І; 8, 9 - перша та друга керуючі шини пристрою (шини подачі сигналів ознак відповідно першого та другого режимів роботи пристрою); 10, 11 - перший та другий БПК; 12 - перша група елементів АБО; 13 - БП; 14 - перша група елементів І; 15 - вихід пристрою; 16 - другий (інформаційний) вхід пристрою (шина подачі дійсного числа); 17 - перша група елементів І; 18, 19 - третій (шина подачі дійсної частині комплексного числа) та четвертий (шина подачі уявної частині комплексного числа) входи пристрою; 20, 21 - другий і третій вхідні регістри; 22 - блок множення двох чисел b і ρ; 23 - шина подачі значення константи ρ=u·q-ν·p 2 UA 114063 C2 5 10 15 20 25 30 35 40 45 50 55 множення; 24 - другий суматор; 25, 26 - друга та третя групи елементів І; 27, 28 - шини подачі значень відповідно першого та другого модулів пристрою; 29 - третя група елементів АБО. Перший (тактовий) 1 вхід пристрою підключено до входу лічильника 2, а вихід першого 3 регістру підключено до перших входів першого 4 суматора. Вихід лічильника 2 підключено до першого входу вентильного елемента 5, вихід якого підключено до перших входів першого 6 та другого 7 елементів І, до других входів яких підключено відповідно перша 8 та друга 9 керуючі шини пристрою (шини подачі сигналів ознак відповідно першого та другого режимів роботи пристрою). Виходи першого 6 та другого 7 елементів І підключено до входів відповідно першого 10 та другого 11 БПК, виходи яких через елементи АБО першої 12 групи підключено до других входів першого 4 суматора, вихід якого підключено до перших входів БП 13 і до перших входів елементів І першої 14 групи, виходи яких є виходом 15 пристрою. Другий (інформаційний) 16 вхід пристрою через елементи АБО другої 17 групи підключено до входу першого 3 регістру. Третій 18 і четвертий (інформаційні) 19 входи пристрою підключено до входів відповідно другого 20 та третього 21 вхідних регістрів. Вихід третього 21 вхідного регістру підключено до першого входу блока множення 22, до другого входу якого підключена шина 23 подачі значення константи р множення. Виходи другого 20 регістру та блока множення 22 підключено до входів другого 24 суматора вихід якого підключено до входів елементів АБО другої 17 групи. До перших входів елементів І другої 25 та третьої 26 груп підключено шини подачі значень відповідно першого 27 та другого 28 модулів пристрою, до других (відкриваючих) входів елементів І другої 25 та третьої 26 груп підключено відповідно перша 8 та друга 9 керуючі шини пристрою. Виходи елементів І другої 25 та третьої 26 через елементи АБО третьої 29 групи підключено до других входів БП 13, перший вихід якого підключено до других (відкриваючих) входів елементів І першої 14 групи, а другий вихід БП 13 підключено до другого (забороненого) входу вентильного елементу 5. Пристрій для визначення лишків дійсних та комплексних чисел у системі залишкових класів функціонує у двох режимах. Перший режим. Визначення лишку αА(mоd mi) дійсного числа А за першим модулем mi (присутній керуючий сигнал шини 8). За другим 16 входом пристрою через другу 17 групу елементів АБО до першого 3 регістру надходить дійсне число А, де воно постійно знаходиться. За першим (тактовим) 1 входом лічильник 2 встановлює початкову (нульову) адресу першого 10 БПК (вентильний елемент 5 і перший 6 елемент І відкрито). Перший БПК 10 містить константи виду 0·mі, 1·mі, …, k·mі. З подачею імпульсів на тактовий вхід 1, з виходу першого 10 БПК константи послідовно (починаючи з нульової константи, тобто k=0) через елементи АБО першої 12 групи поступають до другого входу першого 4 суматора, до другого входу якого з виходу першого 3 регістру поступає значення дійсного числа А. Перший 4 суматор визначає результат операції (у загальному випадку А-k·mі (k=0,1,2,…), а для нульової (k=0) константи маємо А0·mі=А), який поступає до першого входу БП 13, до другого входу якого за шиною 27 через відкриті елементи І другої 25 групи, елементи АБО третьої групи поступає значення модуля mі за яким працює пристрій. Якщо А-k·mi > mі (А-0·mi > mi), тоді одночасно присутній сигнал першої вихідної шини БП 13 і відсутній сигнал другої вихідної шини БП 13. В даному випадку елементи І першої 14 групи закриті, а вентильний елемент 5 відкрито. Далі, за першим (тактовим) 1 входом, лічильник 2 встановлює наступну (першу) адресу БПК 10 (вентильний елемент 5 і перший 6 елемент І відкрито). Перший 4 суматор визначає наступний (k=1) результат операції А-k·mi=А-mi (k=1), який поступає до першого входу БП 13, до другого входу якого за шиною 27 поступає значення першого модуля mi, за яким у першому режимі працює пристрій. Якщо А-k·mi=А-mi>mi, тоді одночасно присутній сигнал першої вихідної шини БП 13 і відсутній сигнал другої вихідної шини БП 13. Цей процес буде продовжуватися до тих пір, поки α=A-k·mi≤mi. В цьому випадку одночасно відсутній сигнал першої вихідної шини БП 13, що закриває вентильний елемент 5, і присутній сигнал другої вихідної шини БП 13, який відкриває елементи першої 14 І групи через які з виходу першого 4 суматора значення лишку αА(mоd mi) поступає на вихід 15 пристрою.    Другий режим. Визначення дійсного лишку h  Amod m комплексного числа A  a  bi за комплексним модулем m  p  qi (присутній керуючий сигнал шини 9). За третім 18 та четвертим  19 входами відповідно до другого 20 (дійсна а частина комплексного числа) і третього 21 (уявна  в частина комплексного числа) регістрів поступає значення комплексного числа A  a  bi . На перші та другі входи другого 24 суматора відповідно поступають значення а і b·ρ (див. співвідношення (4) та (6)). З виходу суматора 24 значення Z (див. співвідношення (6)) через елементи АБО другої 17 групи поступає до входу першого 3 регістру. У подальшому алгоритм 2 2 знаходження лишку h числа за модулем N (тобто hZ(mod N), де N=р +q ) ідентично першому режиму роботи пристрою. При другому режимі роботи пристрою другий 11 БПК містить наступні 3 UA 114063 C2 5 10 15 20 25 константи 0-N, 1·N, 2·N, при цьому, за шиною 28 через відкриті елементи І третьої 26 групи, елементи АБО третьої 29 групи до других входів БП 13 поступає значення другого модуля N, а перший 4 суматор реалізує операцію Z-k·N. Розглянемо процес функціонування винаходу для двох режимів роботи пристрою при конкретних значеннях модулів СЗК. Пертий режим. Визначення лишку А(mоd mi) дійсного числа А за першим модулем mі (присутній керуючий сигнал шини 8). Нехай mі=3. Для першого режиму функціонування пристрою розглянемо три варіанти значень числа А: А=20, А=2 і А=6. Варіант 1. А=20 і m i=3. У таблиці 1 представлено деякі пояснення, щодо процесу функціонування пристрою для першого варіанту. За другим 16 входом пристрою через другу 17 групу елементів АБО до першого 3 регістру надходить дійсне число А=20, де воно постійно знаходиться. За першим 1 входом лічильник 2 встановлює початкову (нульову) адресу (табл. 1) першого 10 БПК (вентильний елемент 5 і перший 6 елемент І відкрито). Перший БПК 10 містить константи виду 0·mі, 1·mі, 2·mі, …, k·mі (табл. 1). З подачею імпульсів на тактовий вхід 1, з виходу першого 10 БПК константи послідовно (починаючи з нульової константи, тобто k=0) через елементи АБО першої 12 групи поступають до першого входу першого 4 суматора, до другого входу якого з виходу першого 3 регістру поступає значення дійсного числа А=20. Перший 4 суматор визначає результат операції A-k·mi=А-0·mi=А (табл. 1), який поступає до першого входу БП 13, до другого входу якого за шиною 27 через відкриті елементи І другої 25 групи, елементи АБО третьої групи поступає значення модуля mі=3 за яким працює пристрій. Якщо А-k·mі>mі тоді одночасно присутній сигнал першої вихідної шини БП 13 і відсутній сигнал другої вихідної шини БП 13. В даному випадку елементи І першої 14 групи закриті, а вентильний елемент 5 відкрито. Далі, за першим (тактовим) 1 входом, лічильник 2 встановлює наступну (першу) адресу БПК 10 (вентильний елемент 5 і перший 6 елемент І відкрито). Перший 4 суматор визначає наступний (k=1) результат операції A-1·mi=20-3=17 (табл. 1), який поступає до першого входу БП 13, до другого входу якого за шиною 27 поступає значення модуля mі=3 за яким у першому режимі працює пристрій. Так як 17>mi=3, тоді одночасно присутній сигнал першої вихідної шини БП 13 і відсутній сигнал другої вихідної шини БП 13. Цей процес буде продовжуватися до тих пір, поки А-k·mі≤mі (k=6). В цьому 30 Таблиця 1 Дані першого варіанту при А=20, mі=3 Адреса констант k 0 1 2 3 4 5 6 35 Значення констант k·mі БПК 10 0 3 6 9 12 15 18 Вихід першого 4 суматора А-k·mі 20-0=20 20-3=17 20-6=14 20-9=11 20-12=8 20-15=5 20-18=2 Результат порівняння БП 13 20>3 17>3 14>3 11>3 8>3 5>3 2