Устройство для преобразования двоичного кода в код системы остаточных классов (сок)



Устройство для преобразования двоичного кода в код системы остаточных классов (сок)

 


Владельцы патента RU 2413279:

Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Национальный исследовательский ядерный университет "МИФИ" (НИЯУ МИФИ) (RU)

Изобретение относится к области вычислительной техники и может быть использовано в вычислительных системах для преобразования двоичных кодов в коды системы остаточных классов (СОК). Техническим результатом является увеличение разрядности преобразуемых в СОК двоичных кодов. Устройство содержит входной регистр, коммутатор, мультиплексор, схему коррекции, два сумматора по модулю, два регистра для фиксации промежуточных результатов суммирования по модулям, три выходных регистра. 1 ил.

 

Устройство относится к области вычислительной техники и может быть использовано в вычислительных системах для преобразования чисел, представленных в позиционной двоичной системе счисления, в систему счисления в остаточных классах (СОК) по основаниям (модулям) p1=2k, p2=2k-1, p3=2k+1 (k=3, 4, 5).

Известны устройства для преобразования чисел из позиционных систем счисления в систему остаточных классов, содержащие элементы задержки, элементы запрета, регистры, блоки элементов «И», комбинационный сумматор по модулю, группу преобразователей кода группы двоичных разрядов числа в модульный остаток [1] или содержащие входной регистр, генератор гармонического сигнала, управляемые фазовращатели, измеритель фазы гармонического сигнала, шифратор [2]. Однако в этих устройствах не учитываются величины оснований СОК, что снижает функциональные возможности устройств.

Наиболее близким по техническому решению к предлагаемому изобретению является преобразователь двоичного кода в код системы остаточных классов [3], одно из оснований СОК при использовании которого имеет величину p1=2k и которое содержит входной регистр, сумматоры по модулю, матрицу преобразования двоичного кода в промежуточный непозиционный код, входы которой соединены с первой группой выходов входного регистра, а выходы подключены к первым входам сумматоров по модулю, вторые входы которых соединены соответственно со второй группой выходов входного регистра и первой группой выходных шин, а выходы сумматоров по модулю подключены ко второй группе выходных шин.

Этот преобразователь принят в качестве прототипа.

Недостатком прототипа являются низкие функциональные возможности, которые проявляются в том, что это устройство ориентировано на преобразование в СОК двоичных кодов относительно малой разрядности. Относительно малая разрядность двоичных кодов, пребразуемых в коды СОК, обусловлена наличием в устройстве матрицы преобразования двоичного кода в промежуточный непозиционный код, предназначенной для хранения в постоянной памяти промежуточных результатов преобразования для всех исходных двоичных кодов. Аппаратные затраты для построения этой матрицы пропорциональны величине 2n, т.е. являются быстрорастущей функцией от разрядности исходных двоичных кодов n, что и накладывает естественные ограничения на построение устройства.

Технический результат предлагаемого изобретения направлен на расширение функциональных возможностей устройства за счет снятия ограничений на разрядность двоичных кодов, преобразуемых в коды СОК, что достигается тем, что в известное устройство для преобразования двоичного кода в код системы остаточных классов, содержащее входной и выходные регистры, сумматоры по модулю, шины управления, подключенные к входам управления узлов устройства, входные и выходные шины, подключенные, соответственно, к входам входного и к выходам выходных регистров, в котором к выходов входного регистра, соответствующих к младшим разрядам исходного двоичного кода, подключены к входам одного из выходных регистров, согласно изобретению введены коммутатор, имеющий n входов и k выходов, где n - разрядность исходного двоичного кода, а k=2, 3, 4… - целое положительное число, определяющее величины оснований (модулей) p1=2k, p2=2k-1 и p3=2k+1 системы остаточных классов, мультиплексор, имеющий k входов и две группы по k выходов, схема коррекции и два регистра фиксации промежуточных результатов суммирования по модулям p2=2k-1 и p3=2k+1, причем выходы входного регистра подключены к входам коммутатора, выходы которого подключены к первой группе входов сумматора по модулю p2=2k-1 и подключены к входам мультиплексора, первая группа из k выходов которого подключена к первой группе входов сумматора по модулю p3=2k+1, а вторая группа из k выходов которого подключена к входам схемы коррекции, выходы которой также подключены к первой группе входов сумматора по модулю p3=2k+1, причем выходы сумматоров по модулю подключены к входам соответствующих регистров фиксации промежуточных результатов суммирования, выходы которых подключены ко вторым группам входов сумматоров по модулю и к входам соответствующих выходных регистров. Это позволяет расширить функциональные возможности устройства за счет снятия ограничений на разрядность двоичных кодов, преобразуемых в коды СОК.

В устройстве используется следующий способ преобразования чисел из позиционной двоичной системы счисления в коды СОК.

Исходное число A=a1a2 an, где ai - двоичные цифры числа A (i=1, 2, …, n), рассматривается как число, представленное в позиционной системе счисления с основанием p=2k, записанное, соответственно, в следующих трех эквивалентных видах:

где bj - цифры числа A (j=1, 2,…, m) при его записи в позиционной системе счисления с основанием p=2k. При таком подходе цифры bj в записях (1)-(3) представляются, в свою очередь, группами из k двоичных разрядов числа A в его исходной двоичной записи.

Из записи (1) следует, что α1=restA(mod2k)=bm, т.е. искомый вычет α1 числа А по основанию p1=2k совпадает с цифрой bm, которая представлена k младшими двоичными разрядами числа A в его исходной двоичной записи.

Из записи (2), с учетом представления содержимого каждой из внешних круглых скобок в виде бинома Ньютона, следует, что α2=restA(mod2k-1)=restb1(mod2k-1)+restb2(mod2k-1)+…+restbm(mod2k-1), т.е. для нахождения искомого вычета α2 числа A по основанию p2=2k-1 достаточно просуммировать цифры bj числа А по этому модулю, которые, как отмечалось выше, представлены группами из k двоичных разрядов в исходной двоичной записи числа А.

Из записи (3), с учетом представления содержимого каждой из внешних круглых скобок в виде бинома Ньютона, следует, что α3=restA(mod2k+1)=restb1(mod2k+1)-restb2(mod2k+1)+…-…+restb1(mod2k+1), т.е. для нахождения искомого вычета α3 числа А по основанию p3=2k+1 достаточно знакопеременно просуммировать цифры bj числа А по этому модулю. Для замены операции вычитания при знакопеременном суммировании операцией сложения достаточно цифры bj, вычеты от которых подлежат вычитанию, заменить, как известно, их дополнениями до величины основания p3=2k+1. Этот прием является основой при вычитании через сложение с использованием обратных кодов.

Структурная схема устройства изображена на чертеже.

Устройство содержит входной регистр 1, к входам которого подключены входные шины 2, а к управляющим входам которого подключены шины управления 3, содержит коммутатор 4, к управляющим входам которого подключены шины управления 5, сумматоры по модулям p2=2k-1 и p3=2k+16 и 7, регистры фиксации промежуточных результатов суммирования 8 и 9, к управляющим входам которых подключены, соответственно, шины управления 10 и 11, мультиплексор 12, к управляющему входу которого подключена шина управления 13, схему коррекции 14, выходные регистры 15, к управляющим входам которых подключены шины управления 16, а к выходам подключены выходные шины 17.

Входной регистр 1 предназначен для фиксации числа A, где A=a1a2…an - число, имеющее n двоичных разрядов, которое требуется преобразовать в СОК по основаниям p1=2k, p2=2k-1 и p3=2k+1, т.е. представить в виде вектора A=(α1, α2, α3), где αr=restA(modpr), r=1, 2, 3. К информационным входам входного регистра 1 подключены входные шины 2, предназначенные для подачи двоичных разрядов числа А на регистр, а к управляющим входам подключены шины управления 3, предназначенные для подачи сигналов сброса и, соответственно, записи на этот регистр.

Коммутатор сигналов 4 предназначен для считывания с входного регистра 1 двоичных разрядов числа А группами, содержащими по k двоичных разрядов в каждой группе, с последующей передачей этих групп, начиная с младших разрядов, на сумматор по модулю 6 и на мультиплексор 12. Коммутатор реализуется по одной из известных схем на основе логических элементов и имеет n входов, подключенных, соответственно, к n выходам регистра 1, и имеет k выходов, подключенных, соответственно, к первой группе из k входов сумматора по модулю 6 и к к входам мультиплексора 12, а также имеет управляющие входы, к которым подключены шины управления 5.

Сумматоры по модулю 6 и 7 предназначены, соответственно, для непосредственного и знакопеременного суммирования по модулям 2k-1 и 2k+1 цифр bj числа А, представляемых группами из k двоичных разрядов и считываемых с входного регистра 1. Сумматоры по модулю 6 и 7 имеют по две группы входов и по одной группе выходов. Разрядность первой и второй группы входов, а также выходная разрядность сумматора по модулю 6 имеют величины, равные к. Разрядность первой и второй групп входов, а также выходная разрядность сумматора по модулю 7 имеют величины, равные к+1. Первая группа входов сумматора по модулю 6 подключена к выходам коммутатора 4, а вторая группа входов сумматора по модулю 6 подключена к выходам регистра фиксации промежуточных результатов суммирования 8. Первая группа входов сумматора по модулю 7 подключена к первой группе выходов мультиплексора 12 и к выходам схемы коррекции 14, а вторая группа входов сумматора по модулю 7 подключена к выходам регистра фиксации промежуточных результатов суммирования 9. Сумматоры по модулю 6 и 7 реализуются на основе логических элементов по одной из известных схем.

Мультиплексор 12 предназначен для передачи двоичных кодов цифр bj или на сумматор по модулю 7, если цифра bj должна поступать на этот сумматор со знаком плюс, или на схему коррекции 14, если цифра bj должна поступать на сумматор по модулю 7 со знаком минус. Мультиплексор 10 реализуется по одной из известных схем на основе логических элементов и имеет k входов, подключенных, как отмечалось выше, к выходам коммутатора 4, и две группы по k выходов, подключенных, соответственно, к первой группе входов сумматора по модулю 7 и к входам схемы коррекции 14. Управление работой мультиплексора 12 осуществляется посредством подачи управляющих сигналов на шину управления 13, которая подключена к управляющему входу мультиплексора.

Схема коррекции14 предназначена для преобразования цифр bj в их дополнение до величины p3 посредством выполнения операции - bj+p3, где bj являются цифрами числа А в позиционной системе счисления с основанием p=2k и в силу соотношения p=2k<p3=2k+1 совпадают по величине с α3=restbj (mod2k+1). Выполнение этого преобразования позволяет заменить операции вычитания при знакопеременном суммировании цифр bj на сумматоре по модулю 7 выполнением операций сложения. Схема коррекции 14 может быть реализована, например, на основе схемы постоянной памяти, содержащей в памяти N=2k k+1-разрядных двоичных слов, которые являются результатами выполнения этой операции. Эта схема имеет k входов, подключаемых к второй группе выходов мультиплексора 12, и имеет k+1 выходов, подключаемых к первой группе входов сумматора по модулю 7. Адресами при обращении к схеме коррекции 14 при этом являются k-разрядные двоичные коды цифр bj

Регистры фиксации промежуточных результатов суммирования 8 и 9 предназначены для фиксации результатов суммирования, поступающих с сумматоров по модулю 6 и 7. Входы этих регистров подключены, соответственно, как отмечалось выше, к выходам сумматоров по модулю 6 и 7, а выходы подключены к первым группам входов сумматоров по модулю 6 и 7, а также к входам соответствующих выходных регистров 15. К управляющим входам регистров 8 и 9 подключены, соответственно, шины управления 10 и 11. По этим шинам на регистры подаются сигналы сброса и сигналы записи.

Выходные регистры 15 предназначены для фиксации результатов преобразования двоичных кодов чисел А в коды СОК по основаниям p1=2k, p2=2k-1 и p3=2k+1, т.е. предназначены для фиксации α1=restA(mod2k), α2=restA(mod2k-1) и α3=restA(mod2k+1). Входы выходных регистров 15 подключены, соответственно, к k выходам входного регистра 1, соответствующим k младшим разрядам исходного двоичного кода числа А, а также к выходам регистров фиксации промежуточных результатов суммирования 8 и 9. К управляющим входам выходных регистров 15 подключены шины управления 16 для подачи на эти регистры сигналов сброса и сигналов записи. К выходам выходных регистров 15 подключены выходные шины 17 для передачи результатов преобразования на дальнейшую обработку в вычислительные устройства, функционирующие в СОК.

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

Производится сброс всех регистров устройства в ноль, что обеспечивается подачей управляющих сигналов на соответствующие из шин управления 3, 10, 11, 16.

Далее двоичный код числа A=a1a2…an, подлежащий преобразованию в коды СОК по основаниям p1=2k, p2=2k-1 и p3=2k+1, поступает по входным шинам 2 и фиксируется на входном регистре 1, что осуществляется посредством подачи сигнала записи на соответствующую из шин управления 3.

После фиксации числа А на регистре 1 с использованием коммутатора 4 производится считывание двоичных разрядов числа А с входного регистра 1. Двоичные разряды числа А считываются с регистра 1 группами, по k двоичных разрядов в каждой группе, начиная с младших разрядов. При этом каждая группа из k разрядов представляет собой цифру bj, т.е. цифру в записи числа А в позиционной системе счисления с основанием p=2k. Считывание обеспечивается последовательной подачей управляющих импульсов на шины управления 5. При подаче одного управляющего импульса на соответствующую из шин управления 5 производится считывание одной цифры bj.

Считываемые группы из k двоичных разрядов, представляющие собой цифры bj, поступают последовательно на сумматор по модулю 6, на котором, с целью получения вычета α2=restA(mod2k-1), они суммируются по модулю p2=2k-1. Для выполнения упомянутого суммирования цифр bj, цифры bj поступают последовательно на первую группу входов сумматора по модулю 6, а на вторую группу входов сумматора по модулю 6 с выходов регистра фиксации промежуточных результатов суммирования 8 поступают величины промежуточных сумм цифр bj. Управление записью промежуточных величин сумм на регистр фиксации промежуточных результатов 8 осуществляется посредством подачи управляющих импульсов на соответствующую из шин управления 10. Этим реализуется последовательное суммирование цифр bj и формирование искомого вычета α2=restA(mod2k-1). Одновременно эти же группы из k двоичных разрядов, представляющие собой цифры bj, последовательно поступают на вход мультиплексора 12, с выходов которого они попеременно поступают на первую группу входов сумматора по модулю 7 и на входы схемы коррекции 14. На схеме коррекции 14 выполняется операция - bj+p3, где p3=2k+1. Результаты выполнения операции - bj+p3 опять же поступают на первую группу входов сумматора по модулю 7. На вторую группу входов сумматора по модулю 7 с выходов регистра фиксации промежуточных результатов суммирования 9 поступают величины промежуточных сумм результатов знакопеременного суммирования цифр bj. Управление записью промежуточных величин сумм на регистр фиксации промежуточных результатов 9 осуществляется посредством подачи управляющих импульсов на соответствующую из шин управления 11. Управление работой мультиплексора осуществляется посредством подачи управляющих сигналов на шину управления 13. Этим реализуется знакопеременное суммирование цифр bj и формирование искомого вычета α3=restA(mod2k+1).

Далее вычет α1=restA(mod2k), представляемый k младшими двоичными разрядами исходного числа А на входном регистре 1, и вычеты α2=restA(mod2k-1) и α3=restA(mod2k+1), сформированные на сумматорах по модулю 6 и 7, посредством подачи сигналов записи на соответствующие из управляющих шин 16 записываются на выходные регистры 15.

Эффективность предлагаемого устройства можно проиллюстрировать на следующем конкретном примере. Так, например, при значительных величинах оснований p1=28=256, p2=28-1=255 и p3=28+1=257, т.е. при k=8, и при значительной величине разрядности преобразуемых в СОК двоичных кодов n=24 устройство содержит восьмиразрядный мультиплексор, восьмиразрядную схему коррекции, восьми- и, соответственно, девятиразрядные сумматоры и регистры. Коммутатор в составе устройства, который имеет 24 входа и 8 выходов, опять же реализуется на основе трех групп из восьми двухвходовых элементов И и одной группы из восьми трехвходовых элементов ИЛИ. При подобных аппаратных затратах реализация всех составляющих устройства, а следовательно и устройства в целом, не вызывает затруднений и удобна в интегральном исполнении.

Список литературы

1. Патент РФ № 2157589.

2. Патент РФ № 2242035.

3. Авт.св. СССР № 525947.

Устройство для преобразования двоичного кода в код системы остаточных классов, содержащее входной и выходные регистры, сумматоры по модулю, шины управления, подключенные к входам управления узлов устройства, входные и выходные шины, подключенные, соответственно, к входам входного и к выходам выходных регистров, в котором к выходов входного регистра, соответствующих к младшим разрядам исходного двоичного кода, подключены к входам одного из выходных регистров, отличающееся тем, что в состав устройства введены коммутатор, имеющий n входов и k выходов, где n - разрядность исходного двоичного кода, а k=2, 3, 4… целое положительное число, определяющие величины оснований (модулей) p1=2k, p2=2k-1 и р3=2k+1 системы остаточных классов, мультиплексор, имеющий к входов и две группы по k выходов, схема коррекции и два регистра фиксации промежуточных результатов суммирования по модулям р2=2k-1 и р3=2k+1, причем выходы входного регистра подключены к входам коммутатора, выходы которого подключены к первой группе входов сумматора по модулю p2=2k-1 и подключены к входам мультиплексора, первая группа из k выходов которого подключена к первой группе входов сумматора по модулю p3=2k+1, а вторая группа из k выходов которого подключена к входам схемы коррекции, выходы которой также подключены к первой группе входов сумматора по модулю р3=2k+1, причем выходы сумматоров по модулю подключены к входам соответствующих регистров фиксации промежуточных результатов суммирования, выходы которых подключены ко вторым группам входов сумматоров по модулю и к входам соответствующих выходных регистров.



 

Похожие патенты:

Изобретение относится к вычислительной технике, в частности к модулярным спецпроцессорам (СП), функционирующим в полиномиальной системе классов вычетов (ПСКВ) и способным сохранять работоспособное состояние при возникновении ошибки за счет реконфигурации структуры.

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

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей и в криптографических приложениях.

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей и в криптографических приложениях.

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

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

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

Изобретение относится к вычислительной технике и, в частности, к модулярным спецпроцессорам (СП), функционирующим в полиномиальной системе классов вычетов (ПСКВ) и способным сохранять работоспособное состояние при возникновении ошибки за счет реконфигурации структуры.

Изобретение относится к вычислительной технике и предназначено для использования в вычислительных устройствах, функционирующих в системе остаточных классов (СОК), а также технике связи для передачи информации кодами СОК.

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

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

Изобретение относится к вычислительной технике и, в частности, к модулярным нейрокомпьютерным средствам и предназначено для определения ошибок в кодовых конструкциях непозиционного кода полиномиальной системы классов вычетов (ПСКВ), представленных в расширенных полях Галуа GF(2v).

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей и в криптографических приложениях.

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

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах для формирования элементов конечных полей и в криптографических приложениях.

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

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

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

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

Изобретение относится к вычислительным модулярным нейрокомпьютерным системам. .

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах для формирования кодовых последовательностей
Наверх