УСТРОЙСТВО ДЛЯ ПРЕОБРАЗОВАНИЯ ДВОИЧНОГО КОДА В КОД СИСТЕМЫ ОСТАТОЧНЫХ КЛАССОВ (СОК) Российский патент 2011 года по МПК G06F7/72 H03M7/18 

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

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

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

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

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

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

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

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

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

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

Из записи (2), с учетом представления содержимого каждой из внешних круглых скобок в виде бинома Ньютона, следует, что α₂=restA(mod2^k-1)=restb₁(mod2^k-1)+restb₂(mod2^k-1)+…+restb_m(mod2^k-1), т.е. для нахождения искомого вычета α₂ числа A по основанию p₂=2^k-1 достаточно просуммировать цифры b_j числа А по этому модулю, которые, как отмечалось выше, представлены группами из k двоичных разрядов в исходной двоичной записи числа А.

Из записи (3), с учетом представления содержимого каждой из внешних круглых скобок в виде бинома Ньютона, следует, что α₃=restA(mod2^k+1)=restb₁(mod2^k+1)-restb₂(mod2^k+1)+…-…+restb₁(mod2^k+1), т.е. для нахождения искомого вычета α₃ числа А по основанию p₃=2^k+1 достаточно знакопеременно просуммировать цифры b_j числа А по этому модулю. Для замены операции вычитания при знакопеременном суммировании операцией сложения достаточно цифры b_j, вычеты от которых подлежат вычитанию, заменить, как известно, их дополнениями до величины основания p₃=2^k+1. Этот прием является основой при вычитании через сложение с использованием обратных кодов.

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

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

Входной регистр 1 предназначен для фиксации числа A, где A=a₁a_2…a_n - число, имеющее n двоичных разрядов, которое требуется преобразовать в СОК по основаниям p₁=2^k, p₂=2^k-1 и p₃=2^k+1, т.е. представить в виде вектора A=(α₁, α₂, α₃), где α_r=restA(modp_r), r=1, 2, 3. К информационным входам входного регистра 1 подключены входные шины 2, предназначенные для подачи двоичных разрядов числа А на регистр, а к управляющим входам подключены шины управления 3, предназначенные для подачи сигналов сброса и, соответственно, записи на этот регистр.

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

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

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

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

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

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

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

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

Далее двоичный код числа A=a₁a₂…a_n, подлежащий преобразованию в коды СОК по основаниям p₁=2^k, p₂=2^k-1 и p₃=2^k+1, поступает по входным шинам 2 и фиксируется на входном регистре 1, что осуществляется посредством подачи сигнала записи на соответствующую из шин управления 3.

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

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

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

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

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

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

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

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

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

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