Устройство для преобразования чисел из системы остаточных классов в позиционную систему счисления

Изобретение относится к области вычислительной техники и может быть использовано в системах связи и обработки информации, функционирующих в системе остаточных классов. Технический результат заключается в снижении аппаратурных затрат преобразователя чисел из системы остаточных классов в позиционную двоичную систему счисления. Поставленная цель достигается за счет последовательного вычисления всех цифр искомого представления числа, что позволяет сократить общий объем ПЗУ устройства и исключить сумматор большой разрядности. 3 ил., 1 табл.

 

Заявляемое изобретение относится к области вычислительной техники и может быть использовано в системах связи и обработки информации, функционирующих в системе остаточных классов.

Известны преобразователи чисел из системы остаточных классов (СОК) в позиционную двоичную систему счисления на основе промежуточного перехода через полиадический код (Модулярные параллельные вычислительные структуры нейропроцессорных систем /Н.И.Червяков, П.А.Сахнюк, А.В.Шапошников, С.А.Ряднов; Под ред. Н.И.Червякова. - М.: ФИЗМАТЛИТ, 2003. - 288 с.), (Патент США №4281391), (Патент США №5008668), использования ортогональных базисов (Модулярные параллельные вычислительные структуры нейропроцессорных систем /Н.И.Червяков, П.А.Сахнюк, А.В.Шапошников, С.А.Ряднов; Под ред. Н.И.Червякова. - М.: ФИЗМАТЛИТ, 2003. - 288 с.), позиционных характеристик числа в классах вычетов (Модулярные параллельные вычислительные структуры нейропроцессорных систем /Н.И.Червяков, П.А.Сахнюк, А.В.Шапошников, С.А.Ряднов; Под ред. Н.И.Червякова. - М.: ФИЗМАТЛИТ, 2003. - 288 с.), (А.С. СССР №1267625). Недостатком известных схемных решений являются большие аппаратурные затраты, вследствие использования сумматора разрядности (во всех трех типах устройства), где [·] - оператор извлечения целой части числа, (N-1) умножителей (при использовании полиадической системы счисления) разрядности , j=1÷N-1, которые необходимы для вычисления за один такт работы устройства всех цифр числа. Вычисление за один такт работы устройства всех цифр числа лежит в основе функционирования обозначенных аналогов.

Наиболее близким аналогом, принятым за прототип, является устройство (Патент США № 5008668), содержащее пять постоянных запоминающих устройств (ПЗУ) организации j=1÷4, для преобразования числа из системы остаточных классов S=(s₁,s ₂, s₃, s₄) в полиадическую систему счисления , где ,, , ПЗУ с организацией для вычисления суммы B₁=b₁+b₂p₁, ПЗУ с организацией для вычисления суммы , сумматор для вычисления S=B₁+B₂, где , десять - разрядных регистров-«защелок», два - разрядных регистра-«защелки», один - разрядный регистр-«защелка».

Основными недостатками прототипа являются большие аппаратурные затраты вследствие использования позиционного сумматора, рассчитанного на сложение операндов разрядности и , двух ПЗУ увеличенной емкости для вычисления операндов В₁ и В₂, неоднородности структуры (в схемном решении присутствуют табличные вычислители различной емкости, регистры, комбинационный сумматор).

Основной задачей, на которую направлено изобретение, является снижение аппаратурных затрат преобразователя чисел из системы остаточных классов в позиционную двоичную систему счисления.

Техническим результатом, достигаемым при осуществлении изобретения, являются снижение аппаратурных затрат вследствие сокращения общего объема ПЗУ, отсутствие сумматора разрядности структуры (в устройстве присутствуют табличные вычислители и регистры).

Указанный технический результат достигается тем, что добавлены четыре ПЗУ для операций взвешенного вычитания по каждому основанию, адресные входы которых связаны с выходами входных регистров и добавленного выходного регистра устройства, причем выходы подключены к добавленным четырем регистрам, данные с которых поступают на входные регистры, емкость двух ПЗУ сокращены за счет хранения редуцированных по модулю 2ⁿ данных, выходы которых соединены с ПЗУ организации 2²ⁿ×n. Согласно изобретению ПЗУ, предназначенное для вычисления В₁, и выходной сумматор заменяются на два 2²ⁿ×n ПЗУ, а ПЗУ, предназначенное для вычисления B₂, заменяется на ПЗУ организации , где , для вычисления , , , а также добавляются четыре ПЗУ с организацией для вычисления , j=1÷4, где i - номер цикла преобразования, а число 2ⁿ является взаимно простым с основаниями системы остаточных классов. Получаемая экономия аппаратурных затрат представлена на фиг.1 в виде зависимости отношения объема памяти заявляемого устройства к объему памяти прототипа от разрядности оснований (при основаниях равной разрядности) без учета затрат на выходной сумматор аналога:

. На фиг.2 представлена зависимость отношения аппаратурных затрат (логических элементов) на дополнительные регистры заявляемого устройства к затратам на комбинационный сумматор прототипа от разрядности оснований (с учетом того, что на один D-триггер затрачивается десять логических элементов, а на один комбинационный одноразрядный сумматор на три входа затрачивается восемь логических элементов): , где Е₁=4·10·n, E₂=10·n+n, Е₃=4·10·(n+1)+4·(n+1) - затраты на дополнительные регистры заявляемого устройства, Е₄=4·10·(n+1), Е₅=4·10·(n+1) - затраты на регистры прототипа повышенной разрядности, Е₆=4·8·(n+1) - затраты на комбинационный сумматор прототипа. Преобразование основано на переводе числа из системы остаточных классов в полиадическую систему счисления с последовательным вычислением цифр позиционного двоичного представления числа S (Ноден П., Ките К. Алгебраическая алгоритмика (с упражнениями и решениями): Пер. с франц. - М.: Мир, 1999. - 720 с.): на первом шаге i-го цикла вычисляются , , , где , , ; на втором шаге i-го цикла вычисляются , , , где , ; на третьем шаге i-го цикла вычисляется , где ; на четвертом шаге i-го цикла вычисляются i-ые n разрядов искомого двоичного представления числа ; на пятом шаге i-го цикла вычисляются , , , ; номер цикла , если кратно n (на цикле пятый шаг отсутствует), и , если не кратно n (на цикле пятый шаг отсутствует).

На фиг.3 представлена блок-схема заявляемого устройства для преобразования чисел из системы остаточных классов в позиционную двоичную систему счисления.

Устройство содержит - разрядные регистры-«защелки» 5, 6, 7, 8 для j=1-4, соответственно, 25, 26, 27 для j=2-4, соответственно, 40, 41 для j=3, j=4, соответственно; - разрядные синхронные регистры хранения информации 66, 67, 68, 69, j=1-4; n-разрядные регистры-«защелки» 24, 39, 48, 49 и синхронный регистр 56; ПЗУ 17, 18, 19, 33, 34 организации для вычисления , , где f=1-3 при m=1, и f=1-2 при m=2; ПЗУ 45 организации и 32, 52 организации 2²ⁿxn для вычисления , k=1-4; ПЗУ 58, 59, 60, 61 организации для вычисления , j=1-4; блок управления 9.

Устройство работает следующим образом.

Первоначальное состояние устройства: на регистры 66, 67, 68, 69 подан с блока управления 9 сигнал 11, запрещающий передачу сохраненных данных; на регистр 56 подан запрещающий передачу сигнал 55. Первый и последний циклы функционирования устройства отличаются от внутренних циклов. Первый цикл заключается в следующем. По шинам 1, 2, 3, 4 на вход устройства подаются остатки искомого числа ,,, по основаниям p₁,p₂,p₃,p₄ соответственно. На регистры 5, 6, 7, 8 подается сигнал 10, переводящий регистры в режим хранения. С шин 1, 2, 3, 4 сигналы снимаются. Записанная в регистрах 5, 6, 7, 8 информация по шинам 13, 14, 15, 16, соответственно, поступает на адресные входы ПЗУ 17, 18, 19. В ПЗУ 17, 18, 19 по адресам , , , соответственно, где || - оператор конкатенации, записаны константы , , соответственно. На информационные входы регистра 24 заводятся младшие n разрядов шины 13. Через время, равное времени выборки одного ПЗУ на регистры 24, 25, 26, 27, подается сигнал «защелкивания» 20 передаваемой информации по шинам 13, 21, 22, 23, соответственно. Сохраненная в регистрах 24, 25, 26, 27 информация поступает на адресные входы ПЗУ 32, 33, 34. На адресные входы ПЗУ 32 заводятся младшие n разрядов шины 29. В ПЗУ 32 по адресам записаны константы . В ПЗУ 33, 34 по адресам , записаны константы , соответственно. Информация с ПЗУ 32, 33, 34 по шинам 36, 37, 38 поступает на информационные входы регистров 39, 40, 41, соответственно. На регистры 39, 40, 41 подается стробирующий сигнал 35, переводящий регистры в режим хранения. Сохраненная в регистре 39 информация по шине 42 поступает на входы регистра 48. Сохраненная в регистрах 40, 41 информация 43, 44, соответственно, поступает на адресные входы ПЗУ 45. В ПЗУ 45 по адресам записаны константы . С выхода ПЗУ 45 поступает информация 47 на входы регистра 49. На регистры 48 и 49 поступает сигнал записи информации 46. С регистров 48, 49 по шинам 50, 51, соответственно, поступает сохраненная в данных регистрах информация на адресные входы ПЗУ 52. В ПЗУ 52 по адресам , хранятся константы . С выхода ПЗУ 52 данные 53 поступают на входы регистра 56. На регистр 56 с блока управления 9 поступает сигнал сохранения информации 54 и снимается сигнал запрета передачи данных 55. С выхода регистра 56 считываются первые (младшие) n бит искомого двоичного представления числа S по шине 57. Сигнал 57 поступает на адресные входы ПЗУ 58, 59, 60, 61. На свободные адресные входы ПЗУ 58, 59, 60, 61 поступают сигналы 13, 14, 15, 16, соответственно. В ПЗУ 58, 59, 60, 61 по адресам , , , , соответственно, хранятся константы , , , , соответственно. Данные 62, 63, 64, 65 с ПЗУ 58. 59, 60, 61 поступают на информационные входы регистров 66, 67, 68, 69, соответственно. На регистры 66, 67, 68, 69 с блока управления 9 поступает сигнал сохранения информации 12. На регистр 56 подается сигнал 55, запрещающий передачу данных, и снимается сигнал запрета передачи данных 11 с регистров 66, 67, 68, 69. С регистров 5, 6, 7, 8, 24, 25, 26, 27, 39, 40, 41, 48, 49, 56 снимаются сигналы сохранения данных. Первый цикл завершен. Действия в циклах со второго по предпоследний одинаковы. Работа устройства во втором цикле заключается в следующем. На регистры 5, 6, 7, 8 подается сигнал 10 записи информации , , , поступающей с регистров 66, 67, 68, 69 по шинам 70, 71, 72, 73, соответственно. С регистров 66, 67, 68, 69 снимается сигнал-«защелка» 12. Записанная в регистрах 5, 6, 7, 8 информация поступает на адресные входы ПЗУ 17, 18, 19 по шинам 13. 14, 15, 16. С выходов регистра 5 и ПЗУ 17, 18, 19 информация поступает на информационные входы регистров 24, 25, 26, 27 по шинам 13, 21, 22, 23, соответственно. На регистры 24, 25, 26, 27 подается сигнал «защелкивания» информации 20. С выходов регистров 24, 25, 26, 27 записанная информация поступает на адресные входы ПЗУ 32, 33, 34 по шинам 28, 29, 30, 31. Записанные в ПЗУ 32, 33, 34 константы поступают на информационные входы регистров 39, 40, 41 по шинам 36, 37, 38, соответственно. На регистры 39, 40, 41 подается сигнал сохранения информации 35. Информация 43, 44 с регистров 40, 41 поступает на адресные входы ПЗУ 45. С выхода регистра 39 по шине 42 и выхода ПЗУ 45 по шине 47 информация поступает на информационные входы регистров 48, 49, соответственно. На регистры 48, 49 с блока управления 9 подается сигнал записи 46. С регистров 48, 49 по шинам 50, 51, соответственно, информация поступает на адресные входы ПЗУ 52. С выхода ПЗУ 52 по шине 53 поступают данные на информационные входы регистра 56. На регистр 56 поступает сигнал сохранения информации 54 и снимается сигнал запрета передачи данных 55. С выхода регистра 56 считываются вторые n бит искомого двоичного представления числа S по шине 57. Сигнал 57 поступает на адресные входы ПЗУ 58, 59, 60. 61. На свободные адресные входы ПЗУ 58, 59, 60, 61 поступают сигналы 13, 14, 15, 16, соответственно. Данные 62, 63, 64, 65 с ПЗУ 58, 59, 60, 61 поступают на информационные входы регистров 66, 67, 68, 69, соответственно. На регистры 66, 67, 68, 69 с блока управления 9 поступает сигнал сохранения информации 12. На регистр 56 подается сигнал 55, запрещающий передачу данных. С регистров 5, 6, 7, 8, 24, 25, 26, 27, 39, 40, 41, 48, 49, 56 снимаются сигналы сохранения данных. Второй цикл завершен. Последний цикл под номером или заключается в следующем. На регистры 5, 6, 7, 8 подается сигнал 10 записи информации , , , поступающей с регистров 66, 67, 68, 69 по шинам 70, 71, 72, 73 соответственно. С регистров 66, 67, 68, 69 снимается сигнал-«защелка» 12 и подается сигнал 11, запрещающий передачу данных. Записанная в регистрах 5, 6, 7, 8 информация поступает на адресные входы ПЗУ 17, 18, 19 по шинам 13, 14, 15, 16. С выходов регистра 5 и ПЗУ 17, 18, 19 информация поступает на информационные входы регистров 24, 25, 26, 27 по шинам 13, 21, 22, 23, соответственно. На регистры 24, 25, 26, 27 подается сигнал «защелкивания» информации 20. С выходов регистров 24, 25, 26, 27 записанная информация поступает на адресные входы ПЗУ 32, 33, 34 по шинам 28, 29, 30, 31. Записанные в ПЗУ 32, 33, 34 константы поступают на информационные входы регистров 39, 40, 41 по шинам 36, 37, 38, соответственно. На регистры 39, 40, 41 подается сигнал сохранения информации 35. Информация 43, 44 с регистров 40, 41 поступает на адресные входы ПЗУ 45. С выхода регистра 39 по шине 42 и выхода ПЗУ 45 по шине 47 информация поступает на информационные входы регистров 48, 49, соответственно. На регистры 48, 49 с блока управления 9 подается сигнал записи 46. С регистров 48, 49 по шинам 50, 51, соответственно, информация поступает на адресные входы ПЗУ 52. С выхода ПЗУ 52 по шине 53 поступают данные на информационные входы регистра 56. На регистр 56 поступает сигнал сохранения информации 54 и снимается сигнал запрета передачи данных 55. С выхода регистра 56 считываются последние (старшие) n бит искомого двоичного представления числа S по шине 57. На регистр 56 подается сигнал запрета передачи данных. С регистров 5, 6, 7, 8, 24, 25, 26, 27, 39, 40, 41, 48, 49, 56 снимаются сигналы сохранения данных. Последний цикл завершен.

Рассмотрим численный пример. Пусть задана система остаточных классов с основаниями р₁=17, р₂=19, р₃=23, p₄=29. Тогда, , 2ⁿ=16, Т=5. Константы L¹ ₂=9, L¹ ₃=19, L¹ ₄=12, L² ₃=17, L² ₄=26, L³ ₄=24, , , , . Следовательно, устройство содержит пятиразрядные регистры-«защелки» 5, 6, 7, 8, 25, 26, 27, 40, 41; пятиразрядные синхронные регистры хранения информации 66, 67, 68, 69; четырехразрядные регистры-«защелки» 24, 39, 48, 49 и синхронный регистр 56; ПЗУ 17, 18, 19, 33, 34 организации 2¹⁰×5; ПЗУ 45 организации 2¹⁰×4; ПЗУ 32, 52 организации 2⁸×4; ПЗУ 58, 59, 60, 61 организации 2⁹×5. Рассмотрим процесс преобразования числа A=(214441)₁₀=(3,7,12,15)_СОК= =(110100010110101001)₂ из СОК в двоичную систему счисления. Рассмотрим первый цикл. Через регистры 5, 6, 7, 8 на адресные входы ПЗУ 17, 18, 19 поступают адреса 0001100111, 0001101100, 0001101111, соответственно, полученные в результате конкатенации остатков в двоичном представлении: 3||7, 3||12, 3||15, соответственно. С выходов ПЗУ 17, 18, 19 по шинам 21, 22, 23 на информационные входы регистров 25, 26, 27 поступают константы , , , соответственно. На вход регистра 24 поступают 4 младших разряда шины 13, по которым передается число 0011. На адресные входы ПЗУ 32, 33, 34 поступают числа 00110001, 1000101010, 1000111100, соответственно. С выходов ПЗУ 32, 33, 34 константы , , , соответственно, поступают на информационные входы регистров 39, 40, 41. С регистров 40, 41 на адресные входы ПЗУ 45 поступает по шинам 43, 44 число 1001111001. С выхода ПЗУ 45 по шине 47 на вход регистра 49 поступает число . С регистров 48, 49 по шинам 50, 51 на адресные входы ПЗУ 52 поступает адрес 01000101. С выхода ПЗУ 52 по шине 53 на вход регистра 56 поступает число . После подачи сигнала записи 54 и снятия сигнала запрета передачи сохраненной информации с шины 57 считываются первые (младшие) 4 бита искомого двоичного представления числа А. На адресные входы ПЗУ 58, 59, 60, 61 поступают адреса 000111001, 001111001, 011001001, 011111001, соответственно. С выходов ПЗУ 58, 59, 60, 61 на входы регистров 66, 67, 68, 69 по шинам 62, 63, 64, 65 соответственно, поступают константы , , , В таблице 1 представлены пять циклов функционирования заявляемого устройства, через сигналы на соответствующих шинах. Объединяя числа из последнего столбца таблицы 1 («Выходной сигнал») получим искомое представление числа А=(3,7,12,15)_СОК=(110100010110101001)₂.

Устройство для преобразования чисел из системы остаточных классов в позиционную систему счисления, содержащее четыре входных регистра, выход s₁ первого из которых соединен с адресными входами четырех ПЗУ, выход s₂ второго регистра присоединен к свободным адресным входам первого из четырех ПЗУ, в котором по адресу s₁||s₂ записаны константы , где || - оператор конкатенации, a , данные с которого поступают на свободные адресные входы четвертого, пятого и шестого ПЗУ, выход s₃ третьего регистра подключен к свободным адресным входам второго ПЗУ, в котором по адресу s₁||s₃ записаны константы , где , выход которого связан со свободными адресными входами пятого ПЗУ, в котором по адресу записаны константы , где , а выход s₄ четвертого регистра соединен со свободными адресными входами третьего ПЗУ, в котором по адресу s₁||s₄ записаны константы , где , данные с которого поступают на свободные адресные входы шестого ПЗУ, в котором по адресу записаны константы , где , а p₁, p₂, p₃, р₄ - основания системы остаточных классов, данные с выхода которого и выхода пятого ПЗУ поступают на вход седьмого ПЗУ, отличающееся тем, что добавлены четыре ПЗУ для операций взвешенного вычитания по каждому основанию, необходимого для реализации округления в остаточном представлении на каждом цикле работы устройства по числу 2ⁿ, адресные входы которых связаны соответственно с выходами четырех входных регистров и с выходом добавленного выходного регистра, причем выходы подключены соответственно к добавленным четырем регистрам, данные с которых поступают соответственно на четыре входных регистра, емкость четвертого и седьмого ПЗУ сокращены за счет хранения по адресам и , соответственно, редуцированных по модулю 2ⁿ данных и , выходы которых соединены с адресными входами восьмого ПЗУ организации 2²ⁿ×n для вычисления за один цикл работы устройства n цифр числа в двоичном счислении, где n=[log₂(p₁-1)], p₁ - младшее основание, [] -оператор извлечения целой части, причем выход восьмого ПЗУ соединен с входом выходного регистра.