close

Вход

Забыли?

вход по аккаунту

?

Патент BY9994

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2007.12.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 9994
(13) C1
(19)
G 06F 7/38
G 06F 7/60
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА
ПО МОДУЛЮ СЕМЬ
(21) Номер заявки: a 20051162
(22) 2005.11.30
(43) 2006.04.30
(71) Заявитель: Белорусский государственный университет (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович; Супрун Валерий Павлович (BY)
(73) Патентообладатель: Белорусский государственный университет (BY)
(56) BY 3707 C1, 2000.
BY 2628 C1, 1999.
RU 2045770 C1, 1995.
RU 2045771 C1, 1995.
SU 1285481 A1, 1987.
SU 1695308 A2, 1991.
US 3816728, 1974.
JP 60144827 A, 1985.
BY 9994 C1 2007.12.30
(57)
Устройство для формирования остатка по модулю семь, содержащее трехоперандный
сумматор по модулю семь, выходы старшего, среднего и младшего разрядов которого соединены соответственно с выходами старшего, среднего и младшего разрядов устройства,
BY 9994 C1 2007.12.30
отличающееся тем, что содержит три многовходовых одноразрядных сумматора по модулю семь, i-й вход ( i = 1, k ; k = 4, 5, 6,…; n = 3k - разрядность входного слова) первого из
которых соединен с входом (3i-2)-го разряда входного слова, вход (3i-1)-го разряда которого соединен с i-м входом второго многовходового одноразрядного сумматора по модулю семь, вход 3i-го разряда соединен с i-м входом третьего многовходового одноразрядного сумматора по модулю семь, выход старшего разряда которого соединен с первым
входом группы входов средних разрядов трехоперандного сумматора по модулю семь,
второй вход которой соединен с выходом младшего разряда второго многовходового одноразрядного сумматора по модулю семь, третий вход соединен с выходом среднего разряда первого многовходового одноразрядного сумматора по модулю семь, выход старшего разряда которого соединен с первым входом группы входов старших разрядов
трехоперандного сумматора по модулю семь, второй вход которой соединен с выходом
среднего разряда второго многовходового одноразрядного сумматора по модулю семь,
третий вход соединен с выходом младшего разряда третьего многовходового одноразрядного сумматора по модулю семь, выход среднего разряда которого соединен с первым
входом группы входов младших разрядов трехоперандного сумматора по модулю семь,
второй вход которой соединен с выходом старшего разряда второго многовходового одноразрядного сумматора по модулю семь, третий вход соединен с выходом младшего разряда первого многовходового одноразрядного сумматора по модулю семь.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения систем аппаратурного контроля и вычислительных устройств, реализующих алгоритмы модулярной арифметики.
Известно устройство для формирования остатка по модулю 2n-1, которое при n = 3 содержит шесть блоков вычисления фундаментальных симметрических булевых функций,
девять элементов ИЛИ и сумматор унитарных кодов по модулю семь [1]. При n = 3 устройство вычисляет свертку по модулю семь n-разрядных двоичных чисел.
Недостатками устройства являются высокая конструктивная сложность и низкое быстродействие, определяемое глубиной схемы.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является устройство для сложения по модулю семь, содержащее шесть элементов сложения по модулю два, три мажоритарных элемента с порогом
два и двадцать четыре элемента И [2]. Устройство выполняет сложение трех трехразрядных двоичных чисел по модулю семь и может быть использовано для формирования остатка по модулю семь девятиразрядного двоичного числа.
Недостатком известного устройства является ограниченная разрядность сворачиваемых по модулю семь двоичных чисел.
Изобретение направлено на решение задачи расширения функциональных возможностей
устройства за счет формирования остатка по модулю семь n-разрядных двоичных чисел.
Названный технический результат достигается путем введения в состав устройства
трех многовходовых одноразрядных сумматоров по модулю семь.
Устройство для формирования остатка по модулю семь содержит трехоперандный
сумматор по модулю семь, выходы старшего, среднего и младшего разрядов которого соединены соответственно с выходами старшего, среднего и младшего разрядов устройства.
В отличие от прототипа, устройство содержит три многовходовых одноразрядных
сумматора по модулю семь, i-й вход ( i = 1, k; k = 4, 5, 6,...; n = 3k - разрядность входного
слова) первого из которых соединен с входом (3i-2)-го разряда входного слова. Вход
(3i-1)-го разряда входного слова соединен с i-м входом второго многовходового одноразрядного сумматора по модулю семь. Вход 3i-го разряда входного слова соединен с i-м
входом третьего многовходового одноразрядного сумматора по модулю семь.
Выход старшего разряда третьего многовходового одноразрядного сумматора по модулю семь соединен с первым входом группы входов средних разрядов трехоперандного
2
BY 9994 C1 2007.12.30
сумматора по модулю семь, второй вход которой соединен с выходом младшего разряда
второго многовходового одноразрядного сумматора по модулю семь, третий вход соединен с выходом среднего разряда первого многовходового одноразрядного сумматора по
модулю семь.
Выход старшего разряда первого многовходового одноразрядного сумматора по модулю семь соединен с первым входом группы входов старших разрядов трехоперандного
сумматора по модулю семь, второй вход которой соединен с выходом среднего разряда
второго многовходового одноразрядного сумматора по модулю семь, третий вход соединен с выходом младшего разряда третьего многовходового одноразрядного сумматора по
модулю семь.
Выход среднего разряда третьего многовходового одноразрядного сумматора по модулю семь соединен с первым входом группы входов младших разрядов трехоперандного
сумматора по модулю семь, второй вход которой соединен с выходом старшего разряда
второго многовходового одноразрядного сумматора по модулю семь, третий вход соединен с выходом младшего разряда первого многовходового одноразрядного сумматора по
модулю семь.
На фигуре представлена схема устройства для формирования остатка по модулю семь.
Устройство содержит три многовходовых одноразрядных сумматора по модулю семь
1, 2 и 3, трехоперандный сумматор по модулю семь 4, k входов 51-5k разрядов входного
слова с номерами 3i-2 ( i = 1, k; k = 4, 5, 6,...; n = 3k - разрядность входного слова), k входов
61-6k разрядов входного слова с номерами 3i-1, k входов 71-7k разрядов входного слова с
номерами 3i, выходы старшего, среднего и младшего разрядов соответственно 8, 9 и 10.
Поясним принцип работы устройства.
Устройство вычисляет остаток по модулю семь n-разрядного двоичного слова
X = 2n-1хn + 2n-2хn-1 + ... + 2х2 + х1, xj ∈ {0, 1}, j = 1, n :
R = 4r1 + 2r2 + r3 = Xmod7,
(1)
где r1, r2, r3 ∈ {0, 1}.
Без потери общности полагаем, что n = 3k, k = 4, 5, 6,...
Представим (1) в виде:
k
k
 k

R =  ∑ 23i − 3 x 3i − 2 + ∑ 23i − 2 x 3i −1 + ∑ 23i −1 x 3i  mod 7 =
 i =1

i =1
i =1
k
k
k







=   ∑ x 3i − 2  mod 7 +  2∑ x 3i −1  mod 7 +  4∑ x 3i  mod 7  mod 7 =

 i =1

 i =1 
  i =1


 k

 k

 k

=   ∑ x 3i − 2  mod 7 + 2 ∑ x 3i −1  mod 7 + 4 ∑ x 3i  mod 7  mod 7 =

 i =1

 i =1 
  i =1

= (S1 + 2S2 + 4S3 ) mod 7,
 k

S1 = 4s11 + 2s12 + s13 =  ∑ x 3i − 2  mod 7, s11 , s12 , s13 ∈ {0, 1};
 i =1

k


S2 = 4s12 + 2s 22 + s32 =  ∑ x 3i −1  mod 7, s12 , s 22 , s32 ∈ {0, 1};
 i =1

k


S3 = 4s13 + 2s32 + s33 =  ∑ x 3i  mod 7, s13 , s32 , s33 ∈ {0, 1}.
 i =1 
Принимая во внимание (3)-(5), преобразуем (2) к виду:
R = (4s11 + 2s12 + s13 + 8s12 + 4s 22 + 2s32 + 16s13 + 8s 32 + 4s33 )mod7 =
где
= (4s11 + 2s12 + s13 + s12 + 4s 22 + 2s32 + 2s13 + s 32 + 4s33 )mod7 =
= (C1 + C2 + C3 )mod7,
3
(2)
(3)
(4)
(5)
(6)
BY 9994 C1 2007.12.30
где
C1 = 4s11 + 2s12 + s12 ;
C2 = 4s 22 + 2s32 + s12 ;
C3 = 4s33 + 2s13 + s32 .
Устройство для формирования остатка по модулю семь работает в соответствии с соотношениями (3)-(6).
Многовходовые (k-входовые) одноразрядные сумматоры по модулю семь 1, 2 и 3 вычисляют соответственно модулярные суммы S1, S2 и S3. Трехоперандный сумматор по модулю семь 4 выполняет сложение по модулю семь трех трехразрядных двоичных чисел С1,
С2 и С3 согласно (6). При этом кортеж двоичных переменных (s11 , s 22 , s33 ) поступает на
входы старших разрядов сумматора 4, кортеж (s12 , s32 , s13 ) - на входы средних разрядов
сумматора 4, кортеж (s13 , s12 , s32 ) - на входы младших разрядов сумматора 4.
Устройство для формирования остатка по модулю семь работает следующим образом.
На входы 51, 52, ..., 5k подаются двоичные разряды х1, х4, ..., хn-2 входного слова
X = 2n-1хn + 2n-2хn-1 + ... + 2х2 + x1, на входы 61, 62, ..., 6k - разряды х2, х5, ..., хn-1, на входы
71, 72, ..., 7k - разряды х3, х6, ..., хn.
На выходах 8, 9 и 10 формируются соответственно старший r1, средний r2 и младший
r3 разряды результата R = 4r1 + 2r2 + r3 свертки по модулю семь входного слова X.
Проиллюстрируем работу устройства на примере свертки по модулю семь двоичного
слова X = х24х23...х2х1 = 111001011001011101101101 (n = 24, k = 8).
Очевидно, что на входы первого восьмивходового одноразрядного сумматора по модулю семь 1 поступает вектор переменных (х1, х4,..., х22) = (1,1,1,1,1,1,1,1); на входы второго сумматора 2 - вектор (х2, х5,...., х23) = (0,0,0,1,0,1,0,1); на входы третьего сумматора 3 вектор (х3, х6,..., х24) = (1,1,1,0,0,0,0,1). На выходах первого сумматора 1 формируется кортеж (s11 , s12 , s13 ) = (0,0,1); на выходах второго сумматора 2 - кортеж (s12 , s 22 , s 32 ) = (0,1,1); на
выходах третьего сумматора 3 - кортеж (s13 , s32 , s 33 ) = (1,0,0).
Тогда на входы старших разрядов трехоперандного сумматора по модулю семь 4 поступает кортеж (s11 , s32 , s33 ) = (0,1,0); на входы средних разрядов - кортеж (s12 , s 32 , s13 ) = (0,1,1),
на входы младших разрядов - кортеж (s13 , s12 , s32 ) = (1,0,0).
На выходах 8, 9 и 10 устройства (выходах сумматора 4) формируются разряды соответственно r1 = 0, r2 = 1 и r3 = 0, составляющие позиционный двоичный код результата
свертки по модулю семь входного слова X:
R = 4r1 + 2r2 + r3 = (4(s11 + s 22 + s33 ) + 2(s12 + s 32 + s13 ) + s13 + s12 + s32 )mod7 = 2.
В десятичной системе счисления X = 223х24 + 222х23 + ... + 2х2 + x1 = 15046509. Следовательно, Xmod7 = 15046509 mod7 = 2.
Достоинствами устройства для формирования остатка по модулю семь являются простая конструкция и высокое быстродействие.
Источники информации:
1. Патент РБ 2628, МПК G 06F 7/72, Н 03М 7/18, 1999.
2. Патент РБ 3707, МПК G 06F 7/49, 2000 (прототип).
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
4
Документ
Категория
Без категории
Просмотров
0
Размер файла
143 Кб
Теги
by9994, патент
1/--страниц
Пожаловаться на содержимое документа