close

Вход

Забыли?

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

?

Патент BY11753

код для вставкиСкачать
ОПИСАНИЕ
ИЗОБРЕТЕНИЯ
К ПАТЕНТУ
РЕСПУБЛИКА БЕЛАРУСЬ
(46) 2009.04.30
(12)
(51) МПК (2006)
НАЦИОНАЛЬНЫЙ ЦЕНТР
ИНТЕЛЛЕКТУАЛЬНОЙ
СОБСТВЕННОСТИ
(54)
BY (11) 11753
(13) C1
(19)
G 06F 7/00
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ n ЧЕТВЕРИЧНЫХ ЦИФР
ПО МОДУЛЮ ТРИ
(21) Номер заявки: a 20060809
(22) 2006.07.31
(43) 2007.10.30
(71) Заявитель: Общество с ограниченной ответственностью "Научно-технический центр "ДЭЛС" (BY)
(72) Авторы: Авгуль Леонид Болеславович; Булаш Юрий Леонидович;
Курносенко Сергей Васильевич;
Терешко Сергей Михайлович (BY)
(73) Патентообладатель: Общество с ограниченной ответственностью "Научнотехнический центр "ДЭЛС" (BY)
(56) BY 5352 C1, 2003.
BY 7000 C1, 2005.
BY 7002 C1, 2005.
SU 1827672 A1, 1993.
BY 11753 C1 2009.04.30
(57)
1. Устройство для сложения n четверичных цифр по модулю три, где n = 2k + 2;
k = 1, 2, 3,…, характеризующееся тем, что содержит три элемента 3-2И-3ИЛИ и два блока
вычисления веса двоичных кодовых комбинаций по модулю три, j-й, где j = 1, n , вход первого из которых соединен с входом старшего разряда j-й четверичной цифры, вход младшего разряда которой соединен с j-м входом второго блока вычисления веса двоичных
кодовых комбинаций по модулю три, выход "равно i - 1", где i = 1, 2, 3, первого блока вычисления веса двоичных кодовых комбинаций по модулю три соединен с i-м входом первого элемента 3-2И-3ИЛИ, i-м входом второго элемента 3-2И-3ИЛИ и i-м входом третьего
Фиг. 1
BY 11753 C1 2009.04.30
элемента 3-2И-3ИЛИ, выход "равно нулю" второго блока вычисления веса двоичных кодовых комбинаций по модулю три соединен с четвертым входом первого элемента 3-2И3ИЛИ, шестым входом второго элемента 3-2И-3ИЛИ и пятым входом третьего элемента
3-2И-3ИЛИ, выход "равно единице" второго блока вычисления веса двоичных кодовых
комбинаций по модулю три соединен с пятым входом первого элемента 3-2И-3ИЛИ, четвертым входом второго элемента 3-2И-3ИЛИ и шестым входом третьего элемента 3-2И3ИЛИ, выход "равно двум" второго блока вычисления веса двоичных кодовых комбинаций по модулю три соединен с шестым входом первого элемента 3-2И-3ИЛИ, пятым входом второго элемента 3-2И-3ИЛИ и четвертым входом третьего элемента 3-2И-3ИЛИ,
выход i-го элемента 3-2И-3ИЛИ соединен с выходом "равно i - 1" устройства.
2. Устройство по п. 1, отличающееся тем, что блок вычисления веса двоичных кодовых комбинаций по модулю три содержит k групп элементов 3-2И-3ИЛИ по три элемента
в каждой, k + 1 элементов И, k + 1 элементов сложения по модулю два и k + 1 элементов
ИЛИ-НЕ, l-й вход t-го из которых, где l = 1, 2; t = 1, k + 1 , соединен с l-м входом t-го элемента И, l-м входом t-го элемента сложения по модулю два и (2t + l - 2)-м входом блока,
выход (s + 1)-го, где s = 1, k , элемента ИЛИ-НЕ соединен с первым входом i-го элемента
3-2И-3ИЛИ s-й группы; второй вход которого соединен с выходом (s + 1)-го элемента сложения по модулю два, третий вход соединен с выходом (s + 1)-го элемента И, выход первого элемента ИЛИ-НЕ соединен с четвертым входом первого элемента 3-2И-3ИЛИ
первой группы, пятым входом второго элемента 3-2И-3ИЛИ первой группы и шестым
входом третьего элемента 3-2И-3ИЛИ первой группы, выход первого элемента сложения
по модулю два соединен с шестым входом первого элемента 3-2И-3ИЛИ первой группы,
четвертым входом второго элемента 3-2И-3ИЛИ первой группы и пятым входом третьего
элемента 3-2И-3ИЛИ первой группы, выход первого элемента И соединен с пятым входом
первого элемента 3-2И-3ИЛИ первой группы, шестым входом второго элемента 3-2И3ИЛИ первой группы и четвертым входом третьего элемента 3-2И-3ИЛИ первой группы,
выход первого элемента 3-2И-3ИЛИ r-й группы, где r = 1, k − 1 , соединен с четвертым входом первого элемента 3-2И-3ИЛИ (r + 1)-й группы, пятым входом второго элемента 3-2И3ИЛИ (r + 1)-й группы и шестым входом третьего элемента 3-2И-3ИЛИ (r + 1)-й группы,
выход второго элемента 3-2И-3ИЛИ r-й группы соединен с шестым входом первого элемента 3-2И-3ИЛИ (r + 1)-й группы, четвертым входом второго элемента 3-2И-3ИЛИ
(r + 1)-й группы и пятым входом третьего элемента 3-2И-3ИЛИ (r + 1)-й группы, выход
третьего элемента 3-2И-3ИЛИ r-й группы соединен с пятым входом первого элемента 32И-3ИЛИ (r + 1)-й группы, шестым входом второго элемента 3-2И-3ИЛИ (r + 1)-й группы
и четвертым входом третьего элемента 3-2И-3ИЛИ (r + 1)-й группы, выход r-го элемента
3-2И-3ИЛИ k-й группы соединен с выходом "равно i - 1" блока.
Изобретение относится к вычислительной технике и микроэлектронике и может быть
использовано для построения систем аппаратурного контроля и вычислительных устройств, реализующих алгоритмы модулярной арифметики.
Известен многовходовый логический модуль, содержащий n элементов НЕ, 2n-2 элементов И и n-1 группу элементов 2-2И-2ИЛИ [1]. Модуль формирует унитарный двоичный код числа единиц, содержащихся во входном n-разрядном двоичном слове (модуль
является устройством для вычисления веса двоичных кодовых комбинаций).
Недостатком устройства является невозможность вычисления веса двоичных кодовых
комбинаций по модулю три.
Наиболее близким по конструкции и функциональным возможностям техническим
решением к предлагаемому является многовходовый одноразрядный сумматор по модулю
три, содержащий элементы сложения по модулю два, элементы ЗАПРЕТ и мажоритарные
2
BY 11753 C1 2009.04.30
элементы с четными порогами [2]. Сумматор формирует позиционный двоичный код
суммы по модулю три числа единиц, содержащихся во входном слове (сумматор выполняет сложение n одноразрядных двоичных чисел по модулю три).
Недостатком известного устройства является невозможность сложения по модулю три
двухразрядных двоичных чисел (четверичных цифр).
Изобретение направлено на решение задачи расширения функциональных возможностей устройства за счет выполнения сложения по модулю три n четверичных цифр.
Названный технический результат достигается путем введения в состав устройства
двух блоков вычисления веса двоичных кодовых комбинаций по модулю три и трех элементов 3-2И-3ИЛИ.
Устройство для сложения n четверичных цифр по модулю три, где n = 2k + 2; k = 1, 2,
3,…, содержит три элемента 3-2И-3ИЛИ и два блока вычисления веса двоичных кодовых
комбинаций по модулю три. При этом j-й вход, где j = 1, n , первого блока вычисления веса двоичных кодовых комбинаций по модулю три соединен с входом старшего разряда j-й
четверичной цифры, вход младшего разряда которой соединен с j-м входом второго блока
вычисления веса двоичных кодовых комбинаций по модулю три. Выход "равно i - 1", где
i = 1, 2, 3, первого блока вычисления веса двоичных кодовых комбинаций по модулю три
соединен с i-м входом первого элемента 3-2И-3ИЛИ, i-м входом второго элемента 3-2И3ИЛИ и i-м входом третьего элемента 3-2И-3ИЛИ. Выход "равно нулю" второго блока
вычисления веса двоичных кодовых комбинаций по модулю три соединен с четвертым
входом первого элемента 3-2И-3ИЛИ, шестым входом второго элемента 3-2И-3ИЛИ и пятым входом третьего элемента 3-2И-3ИЛИ. Выход "равно единице" второго блока вычисления веса двоичных кодовых комбинаций по модулю три соединен с пятым входом
первого элемента 3-2И-3ИЛИ, четвертым входом второго элемента 3-2И-3ИЛИ и шестым
входом третьего элемента 3-2И-3ИЛИ. Выход "равно двум" второго блока вычисления веса двоичных кодовых комбинаций по модулю три соединен с шестым входом первого
элемента 3-2И-3ИЛИ, пятым входом второго элемента 3-2И-3ИЛИ и четвертым входом
третьего элемента 3-2И-3ИЛИ. Выход i-го элемента 3-2И-3ИЛИ соединен с выходом
"равно i - 1" устройства.
В устройстве каждый блок вычисления веса двоичных кодовых комбинаций по модулю три содержит k групп элементов 3-2И-3ИЛИ по три элемента в каждой, k + 1 элементов И, k + 1 элементов сложения по модулю два и k + 1 элементов ИЛИ-НЕ, l-й вход t-го
из которых, где l = 1, 2; t = 1, k + 1, соединен с l-м входом t-го элемента И, l-й входом t-го
элемента сложения по модулю два и (2t + l - 2)-м входом блока. Выход (s + 1)-го, где
s = 1, k , элемента ИЛИ-НЕ соединен с первым входом i-го элемента 3-2И-3ИЛИ s-й группы; второй вход которого соединен с выходом (s + 1)-го элемента сложения по модулю
два, третий вход соединен с выходом (s + 1)-го элемента И. Выход первого элемента ИЛИНЕ соединен с четвертым входом первого элемента 3-2И-3ИЛИ первой группы, пятым
входом второго элемента 3-2И-3ИЛИ первой группы и шестым входом третьего элемента
3-2И-3ИЛИ первой группы. Выход первого элемента сложения по модулю два соединен с
шестым входом первого элемента 3-2И-3ИЛИ первой группы, четвертым входом второго
элемента 3-2И-3ИЛИ первой группы и пятым входом третьего элемента 3-2И-3ИЛИ первой группы. Выход первого элемента И соединен с пятым входом первого элемента 3-2И3ИЛИ первой группы, шестым входом второго элемента 3-2И-3ИЛИ первой группы и четвертым входом третьего элемента 3-2И-3ИЛИ первой группы. Выход первого элемента 32И-3ИЛИ r-й группы, где r = 1, k − 1, соединен с четвертым входом первого элемента 32И-3ИЛИ (r + 1)-й группы, пятым входом второго элемента 3-2И-3ИЛИ (r + 1)-й группы и
шестым входом третьего элемента 3-2И-3ИЛИ (r + 1)-й группы. Выход второго элемента
3-2И-3ИЛИ r-й группы соединен с шестым входом первого элемента 3-2И-3ИЛИ (r + 1)-й
группы, четвертым входом второго элемента 3-2И-3ИЛИ (r + 1)-й группы и пятым входом
3
BY 11753 C1 2009.04.30
третьего элемента 3-2И-3ИЛИ (r + 1)-й группы. Выход третьего элемента 3-2И-3ИЛИ r-й
группы соединен с пятым входом первого элемента 3-2И-3ИЛИ (r + 1)-й группы, шестым
входом второго элемента 3-2И-3ИЛИ (r + 1)-й группы и четвертым входом третьего элемента 3-2И-3ИЛИ (r + 1)-й группы. Выход i-го элемента 3-2И-3ИЛИ k-й группы соединен
с выходом "равно i -1" блока.
На чертеже (фиг. 1) представлена схема устройства для сложения n четверичных цифр
по модулю три (n = 2k + 2; k = 1, 2, 3,…), на фиг. 2 - схема блока вычисления веса двоичных кодовых комбинаций по модулю три при n = 10 (k = 4).
Устройство (фиг. 1) содержит первый 1 и второй 2 блоки вычисления веса двоичных
кодовых комбинаций по модулю три, первый 3, второй 4 и третий 5 элементы 3-2И-3ИЛИ,
n входов 61-6n старших разрядов четверичных цифр, n входов 71-7n младших разрядов четверичных цифр, выход "равно нулю" 8, выход "равно единице" 9, выход "равно двум" 10.
Блок вычисления веса двоичных кодовых комбинаций по модулю три (фиг. 2) содержит k + 1 = 5 элементов ИЛИ-НЕ 11-15, k + 1 = 5 элементов сложения по модулю два 1620, k + 1 = 5 элементов И 21-25, k = 4 группы элементов 3-2И-3ИЛИ (три элемента первой
группы 26, 27 и 28; три элемента второй группы 29, 30 и 31; три элемента третьей группы
32, 33 и 34; три элемента четвертой группы 35, 36 и 37), n = 10 входов 38-47, выход "равно
нулю" 48, выход "равно единице" 49, выход "равно двум" 50.
Поясним принцип работы устройства для сложения n четверичных цифр по модулю
три.
Устройство выполняет сложение n двухразрядных двоичных чисел (четверичных
цифр) X j = 2 x1 j + x 2 j j = 1, n по модулю три:
(
)
 n
 n


S = (s 0 , s1 , s 2 ) =  ∑ X j  mod 3 =  ∑ 2 x1 j + x 2 j  mod 3,
(1)
 j=1 
 j=1





где si-1 ∈ {0, 1} - сигнал, формируемый на выходе "равно i - 1" устройства (i = 1, 2, 3).
 n

При этом si-1 = 1 тогда и только тогда, когда  ∑ X j  mod 3 = i − 1.
 j=1 


Преобразуем (1) к виду:
 n

 n
 n



 ∑ 2 x1 j + x 2 j  mod 3 =   ∑ 2x1 j  mod 3 +  ∑ x 2 j  mod 3  mod 3 =
 j=1
 j=1 


  j=1








(2)

  n

 n

=  2 ∑ x1 j  mod 3 +  ∑ x 2 j  mod 3  mod 3 = (2R1 + R 2 ) mod 3,
 j=1 

  j=1 




 
 n

где R1 = r01 , r11 , r21 =  ∑ x1 j  mod 3 - унитарный двоичный код, формируемый на выходе
 j=1 


первого блока вычисления веса двоичных кодовых комбинаций по модулю три 1;
 n

R 2 = r02 , r12 , r22 =  ∑ x 2 j  mod 3 - унитарный двоичный код, формируемый на выходе
 j=1



второго блока вычисления веса двоичных кодовых комбинаций по модулю три 2.
Здесь rim−1 ∈ {0, 1} - сигнал, формируемый на выходе "равно i - 1" m-го блока вычисления веса двоичных кодовых комбинаций по модулю три (i = 1, 2, 3; m = 1, 2).
 n

При этом rim−1 ∈ {0, 1} тогда и только тогда, когда  ∑ x mj  mod 3 = i − 1.
 j=1



(
(
)
)
4
BY 11753 C1 2009.04.30
Унитарный код результата S = (s0, s1, s2) формируется элементами 3-2И-3ИЛИ 8, 9 и
10 путем сложения по модулю три унитарных кодов R1 = r01 , r11 , r21 и R 2 = r02 , r12 , r22 с
учетом их весов согласно (2):
s 0 = r01r02 ∨ r11r12 ∨ r21r22 ;
(
)
(
)
s1 = r01r12 ∨ r11r22 ∨ r21r02 ;
s 2 = r01r22 ∨ r11r02 ∨ r21r12 .
Устройство для сложения n четверичных цифр по модулю три работает следующим
образом.
На входы 61 - 6n подаются старшие разряды х11 - х1n (в произвольном порядке), а на
входы 71 - 7n - младшие разряды х21 - х2n (в произвольном порядке) четверичных цифр Х1 Хn. На выходах 8, 9 и 10 формируются соответственно сигналы s0, s1 и s2, составляющие
 n

унитарный двоичный код S = (s 0 , s1 , s 2 ) =  ∑ X j  mod 3 суммы по модулю три n четве j=1 


ричных цифр Х1 - Хn.
Поясним принцип построения блоков вычисления веса двоичных кодовых комбинаций по модулю три, используемых в предлагаемом устройстве.
В общем случае такие блоки формирует унитарный двоичный код (y0, y1, y2) суммы по
модулю три числа единиц V(X), содержащихся во входном n-разрядном двоичном слове
X = (х1, х2,…, хn):
Y = V(X)mod3 = (х1 + х2 + … + xn)mod3 = (y0, y1, y2),
где yi-1 = 1 тогда и только тогда, когда V(X)mod3 = i - 1; i = 1, 2, 3.
Положим, что n = 2k + 2 и k = 1, 2, 3,…
Пусть ysi −1 - булева функция, реализуемая на выходе i-го элемента 3-2И-3ИЛИ s-й
(
)
группы s = 1, k; l = 1, 7 .
Тогда работа блока может быть описана следующими рекуррентными соотношениями:
ys0 = x 2s +1 ∨ x 2s + 2 ⋅ ys0−1 ∨ (x 2s +1 ⊕ x 2s + 2 ) ⋅ ys3−1 ∨ x 2s +1x 2s + 2 ⋅ ys2−1;
y1s = x 2s +1 ∨ x 2s + 2 ⋅ y1s −1 ∨ (x 2s +1 ⊕ x 2s + 2 ) ⋅ ys0−1 ∨ x 2s +1x 2s + 2 ⋅ ys2−1;
ys2 = x 2s +1 ∨ x 2s + 2 ⋅ ys2−1 ∨ (x 2s +1 ⊕ x 2s + 2 ) ⋅ y1s −1 ∨ x 2s +1x 2s + 2 ⋅ ys0−1 ,
где y 00 = x1 ∨ x 2 , y10 = x1 ⊕ x 2 , y 02 = x1x 2 .
(
)
Очевидно, что (y 0 , y1 , y 2 ) = y 0k , y1k , y k2 .
Работа блока вычисления веса двоичных кодовых комбинаций по модулю три при
n = 10 поясняется таблицей (фиг. 3).
Достоинствами устройства для сложения n четверичных цифр по модулю три являются простая конструкция и регулярная однородная структура.
Источники информации:
1. А.с. СССР 1793547, МПК H 03M 7/22, 1993.
2. Патент РБ 5352, МПК G 06F 7/49, 7/50, 2003 (прототип).
5
BY 11753 C1 2009.04.30
Фиг. 2
Фиг. 3
Национальный центр интеллектуальной собственности.
220034, г. Минск, ул. Козлова, 20.
6
Документ
Категория
Без категории
Просмотров
0
Размер файла
517 Кб
Теги
патент, by11753
1/--страниц
Пожаловаться на содержимое документа