КОМБИНАЦИОННЫЙ РЕКУРРЕНТНЫЙ ФОРМИРОВАТЕЛЬ ОСТАТКОВ Российский патент 1995 года по МПК H03M7/18 

Описание патента на изобретение RU2029435C1

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

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

Недостатком известного устройства является низкая надежность, так как для его реализации требуется большой объем оборудования.

Целью изобретения является повышение надежности функционирования за счет уменьшения объема оборудования.

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

Известно, что позиционные системы счисления строятся следующим образом. Выбирается некоторое число m - основание системы счисления и каждое число А представляется в виде комбинации его степеней с коэффициентами ai, i = , принимающими значения от 0 до m-1. Для случая двоичной системы счисления (m = 2) всякое число А можно представить в виде
A = ak2k + ak-12k-1 + ... + a121 + a0, (1) где ai,i = 0,k, принимают значения "0" или "1".

Для вычисления остатка от числа А по модулю Р достаточно в выражении (1) просуммировать частичные остатки по модулю Р от чисел 2iдля тех i, для которых коэффициент ai = 1. Способ вычисления частичных остатков состоит в следующем. Частичный остаток от 2о для любого модуля (Р ≥2) всегда равен единице. Частичный остаток от 21 в два раза превышает (с учетом операции приведения по модулю) частичный остаток от 2о и т.д., т.е. частичный остаток от 2i в два раза превышает частичный остаток от 2i-1. Таким образом, вычисление частичного остатка от 2i заключается в умножении на два частичного остатка от 2i-1 и приведении результата по модулю Р. Операция умножения на два (как видно из выражения (1)) может быть реализована сдвигом всех разрядов умножаемого числа на один влево либо подачей разрядов множимого на выход результата в такой последовательности: 2i разряд множимого на 2i+1 разряд произведения, i = . Операция приведения по модулю Р для чисел, не превышающих величину 2Р-1, реализуется следующим образом. Если число не превышает величину Р, то оно остается без изменения, если же число лежит в интервале от Р до 2Р-1, то из него вычитается модуль Р, а результат является остатком.

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

Формирователь содержит (фиг.1) последовательно соединенные комбинационный формирователь 1 частичных остатков, блок 2 ключей и блок 3 сумматоров по модулю. Вход 4 служит для подачи инверсного кода модуля, а вход 5 - для подачи кода числа. Выход 6 является выходом остатка формирователя.

Комбинационный формирователь 1 частичных остатков содержит N-1 узлов 7 формирования частичных остатков, соединенных последовательно по рекуррентному принципу, причем на вход первого узла формирования подан код единицы, выходы разрядов предыдущего узла формирования подаются на входы последующего узла формирования со сдвигом на один в сторону старших (реализация процедуры умножения), выходы каждого узла формирования, а также код единицы, защитный на входе первого узла, являются информационными выходами формирователя. Блок 2 ключей содержит N ключей 8, на информационные входы которых подаются коды с выходов узлов 7 формирования, причем управляющие входы являются входами подачи кода числа блока, а информационные выходы - информационными выходами блока.

Блок 3 сумматоров по модулю содержит сумматоры 9 по произвольному модулю. Каждый сумматор 9 содержит (фиг.2) последовательно соединенные комбинационный сумматор 10 и узел 11 формирования частичных остатков. В состав узла формирования частичных остатков (фиг.3) входят сумматор 12 и мультиплексор 13.

Комбинированный рекуррентный формирователь остатков работает следующим образом.

В исходном состоянии (фиг.1) на вход 4 модуля подается инверсный код модуля Рj, по которому необходимо формировать остатки. Так как на вход первого узла 7 формирования частичных остатков подается код единицы, а выходы разрядов предыдущего узла формирования подключены к входам последующего узла формирования со сдвигом на один разряд в сторону старших, то на выходах формирователя 1 формируются частичные остатки по модулю Рj от числа 2i, i = .

Число Аk через вход 5 поступает на управляющие входы блока 2 ключей. В зависимости от того на управляющий вход какого из ключей 8 поступает логическая "1", тот из ключей 8 оказывается открытым и коммутирует на свои выходы значения с информационных входов, на которые с информационных выходов формирователя 1 поступают частичные остатки по модулю Рj. В результате на соответствующие входы блока 3 сумматоров по модулю поступают остатки от чисел 2i для тех i, для которых коэффициент аi = 1 в представлении (1) числа Ak, записанного в формирователь 1. Блок 3 сумматоров по модулю суммирует по модулю Рj частичные остатки, и результат суммирования выдается на информационные выходы 6 формирователя.

При следующем цикле формирования остатка задается любое другое число А, которое поступает на вход 5, и работа всех элементов и блоков формирователя повторяется.

Для смены модуля на вход 4 формирователя подается очередной модуль Рх, узлы 7 формирования формирователя 1 формируют частичные остатки от чисел 2i, а с подачи очередного числа Аm работа элементов и блоков формирователя повторяется.

Блок 3 сумматоров по модулю работает следующим образом. На управляющие входы каждого сумматора 9 поступает значение модуля в инверсном виде, а на информационные входы первого сумматора 9 поступают остатки от чисел 20 и 21, если коэффициенты а0 и а1 при представлении (1) числа А равны единице. Результат суммирования поступает на вторые информационные входы второго сумматора, на первые информационные входы которого поступает остаток от числа 22 по модулю, если коэффициент а2 = 1, и т.д. до тех пор, пока результат суммирования по модулю частичных остатков не появится на выходе последнего сумматора 9 по произвольному модулю. Этот результат и поступает на выход 6 формирователя. Время формирования остатка равно времени распространения сигнала с первого по последний сумматор 9 по произвольному модулю.

Сумматор 9 по произвольному модулю (фиг.2) работает следующим образом. Комбинационный сумматор 10 осуществляет суммирование остатков, поступающих на его информационные входы, а узел 11 формирования частичных остатков в зависимости от значения инверсного кода модуля, поступающего на его вход 4, приводит по модулю значение суммы.

Узел 7 (11) формирования остатков (фиг.3) работает следующим образом. Сумматор 12, на разряд переноса которого постоянно подан уровень логической "1", за счет подачи на его вход 4 кода модуля в инверсном виде выполняет функцию вычитания модуля из числа. Если поступившее на информационный вход сумматора 12 число меньше кода модуля, то на управляющем выходе (выходе переноса) остается нулевой потенциал и вторые информационные входы мультиплексора 13 остаются скоммутированными на его информационные выходы, и код числа поступает на выход формирователя без изменений. Если код числа меньше или равен коду модуля, то на выходе переноса сумматора 12 появляется единичный потенциал, который коммутирует первые входы мультиплексора 13 с его информационными выходами, и код разности поступает на выход мультиплексора 13.

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

название год авторы номер документа
РЕКУРРЕНТНЫЙ ФОРМИРОВАТЕЛЬ ОСТАТКОВ ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ 1991
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2007037C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 1992
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2012137C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 1990
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2029434C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 1991
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2007033C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ЭЛЕМЕНТОВ МУЛЬТИПЛИКАТИВНЫХ ГРУПП ПОЛЕЙ ГАЛУА GF (P) 1991
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2007036C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ИНДЕКСОВ ЭЛЕМЕНТОВ МУЛЬТИПЛИКАТИВНЫХ ГРУПП ПОЛЕЙ ГАЛУА GF (P) 1991
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2007034C1
ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО 1992
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2025897C1
СУММАТОР ПО МОДУЛЮ P 1992
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2032934C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 1991
  • Петренко В.И.
  • Чипига А.Ф.
RU2023346C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 1991
  • Петренко В.И.
  • Чипига А.Ф.
RU2020759C1

Иллюстрации к изобретению RU 2 029 435 C1

Реферат патента 1995 года КОМБИНАЦИОННЫЙ РЕКУРРЕНТНЫЙ ФОРМИРОВАТЕЛЬ ОСТАТКОВ

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

Формула изобретения RU 2 029 435 C1

1. КОМБИНАЦИОННЫЙ РЕКУРРЕНТНЫЙ ФОРМИРОВАТЕЛЬ ОСТАТКОВ, содержащий блок из N ключей и блок из N-1 сумматоров по модулю (где N - разрядность входного числа), причем первый информационный вход i-го сумматора по модулю блока (i= 1, .. N-1) соединен с выходом (i+1)-го ключа блока, отличающийся тем, что в него введен блок формирования частичных остатков, состоящий из N-1 узлов формирования частичных остатков, причем вход блока формирования частичных остатков соединен с входом инверсного кода модуля формирователя и вторым информационным входом каждого из N-1 сумматоров по модулю блока, выход (N-1)-го сумматора по модулю блока соединен с выходом остатка формирователя, вход j-го разряда числа которого соединен с управляющим входом j-го ключа блока (j=1, ..., N), третий вход первого сумматора по модулю блока соединен с выходом первого ключа блока, третий вход (i+1)-го сумматора по модулю блока соединен с выходом i-го сумматора по модулю блока, N выходов блока формирования частичных остатков соединены соответственно с информационными входами N ключей блока, а в блоке формирования частичных остатков вход блока соединен с первым входом каждого из N-1 узлов формирования частичных остатков, второй вход первого узла формирования частичных остатков соединен с шиной логической единицы и первым выходом блока, (i+1)-й выход которого соединен с выходом i-го узла формирования частичных остатков и вторым входом (i+1)-го узла формирования частичных остатков. 2. Формирователь по п.1, отличающийся тем, что каждый из N-1 сумматоров по модулю блока содержит комбинационный сумматор и узел формирования частичных остатков, выход которого соединен с выходом сумматора по модулю, первый и третий информационные входы которого соединены соответственно с первым и вторым входами комбинационного сумматора, выход которого соединен с вторым входом узла формирования частичных остатков, первый вход которого соединен с вторым информационным входом сумматора по модулю. 3. Формирователь по пп.1 и 2, отличающийся тем, что узел формирования частичных остатков содержит сумматор и мультиплексор, выход которого соединен с выходом узла, первый вход которого соединен с входом первого слагаемого сумматора, выход суммы которого соединен с первым информационным входом мультиплексора, второй информационный вход которого соединен с вторым входом узла и входом второго слагаемого сумматора, вход переноса и выход переноса которого соединены соответственно с шиной логической единицы и управляющим входом мультиплексора.

Документы, цитированные в отчете о поиске Патент 1995 года RU2029435C1

Устройство для формирования остатка по произвольному модулю от числа 1989
  • Горбенко Иван Дмитриевич
  • Сныткин Иван Илларионович
  • Петренко Вячеслав Иванович
SU1633495A1
Переносная печь для варки пищи и отопления в окопах, походных помещениях и т.п. 1921
  • Богач Б.И.
SU3A1

RU 2 029 435 C1

Авторы

Петренко Вячеслав Иванович

Чипига Александр Федорович

Даты

1995-02-20Публикация

1992-03-16Подача