Устройство для возведения в квадрат м-разрядных двоичных чисел

 

Изобретение относится к вычислительной и информационной технике и может быть использовано в информационно-преобразовательных устройствах, в частности в аналого-цифровом преобразователе , с извлечением квадратного корня,реализующем принцип последовательных приближений. Цель изобретения - расширение функциональных возможностей за счет вычисления квадратов последовательных приближений исходного числа. Устройство содержит распределитель импульсов I, регистр сдвига 2, накапливающий сумматор 3, элемент задержки 4, элемент импликации 5, элемент И 6. Устройство имеет синхровход 7, информационный вход 8, вход Сброс 9, выходы 10; регистр сдвига 2 содержит D-триггеры, элементы ИЛИ, 1 з.п.ф-лы, 2 ил. (Л

СОЮЗ СОВЕТСКИХ

СО1.1ИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (19) (И> (511 4 G 06 F 7/552

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

r10 ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

1(3 .„

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 1

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ й7 (21) 4164468/24-24 (22) 18.12.86 (46) 30 05.88.Бюл. 1(20 (71) Одесский политехнический институт

{72) А.E.Амдуров, Ю.М.Бастриков, Л.И.Протасова, Т.Г.Трофименко и А.В.Фрид (53) 681.325 (088.8) (56) Авторское свидетельство СССР

Ф 4?5619, кл. G 06 F 7/38, 1973.

Авторское свидетельство СССР

Ф 290279, кл. G 06 F 7/552, 1969. (54) УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ В

КВАДРАТ M-РАЗРЯДНЫХ ДВОИЧНЫХ ЧИСЕЛ (57) Изобретение относится к вычислительной и информационной технике и мажет быть использовано в информационно-преобразовательных устройствах, в частности в аналого-цифровом преобразователе.с извлечением квадратного корня, реализующем принцип последовательных приближений. Цель изобретения — расширение функциональных возможностей за счет вычисления квадратов последовательных приближений исходного числа. Устройство содержит распределитель импульсов 1, регистр сдвига 2, накапливающий сумматор 3, элемент задержки 4, элемент импликации 5, элемент И 6. Устройство имеет синхровход 7, информационный вход 8, вход и и

1 ф

Сброс 9, выходы 10 регистр сдвига

2 содержит D-триггеры, элементы ИЛИ, 1 з.п.ф-лы, 2 ил.

1399733 разом.

Исходное число в последовательйом коде старшими разрядами вперед поступает на информационный вход устройства, каждый k-й разряд (k= l,2,3,...,N} сопровождается синхро импульсом на синхровходе устройства. До прихода 1-го разряда подачей единичного сигнала на вход "Сброс" устройства обеспечивается установка распределителя 1 в первое состояние ,и установка в нуль регистра 2 и на-, 40 капливающего сумматора 3. Таким образом, имеют место; (1) ) ()

$ =0

Zä oэ где S, — содержимое накапливающего сумматора на нулевом такте;

Z - содержимое регистра сдвига на нулевом такте.

Рассмотрим работу устройства HG

k-м такте. Пусть як О. Тогда на выходе элемента И 6 имеет место сигнал уровня логического нуля, который и поступает H& синхровход накапливающего сумматора 3. Поэтому содержи- 5

> мое накапливающего сумматора 3 не изменяется, т.е выполняется (3) 1

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

Цель изобретения — расширение 1(! класса решаемых задач за счет обеспечения возможности вычисления квадратов последовательных приближений исходного числа.

На фиг.I представлена схема уст- 15 ройства; на фиг.2 - схема регистра, сдвига.

Устройство содержит М"разрядный распределитель 1 импульсов, регистр 2 сдвига, накапливающий сумматор 3, 2О элемент 4 задержки, элемент 5 импликации, элемент И 6, устройство имеет синхровход 7, информационный вход, 8, вход 9 "Сброс" и выходы !Î, Регистр сдвига образуют D-триггеры 11 и элементы ИЛИ 12. с

Устройство работает следующим обгде S — содержимое накапливающего сумматора на k-м такте. На выходе элемента 5 импликации имеет место сигнал логического нуля, который поступает на вход "Разрешение" распределителя 1 . На всех выходах распределителя 1 устанавливаются сигналы логического нуля, которые поступают на вторые входы элементов ИЛИ регистра 2, Поэтому информация без искажения передается с выхода любого предыдущего D-триггера регистра сдвига на вход последующего, Тогда по переднему фронту синхроимпульса через время, определяемое элементом 4 задержки происходит сдвиг информации в регистре 2 вправо на один разряд, т,. е. (4) где Е к - содержимое регистра сдвина на k-м такте.

Ло заднему фронту синхроимпульса распределитель 1 переходит в следующее, (k+I)-е состояние.

Пусть oC< = 1, Тогда синхровход накапливающего сумматора 3 через элемент И 6 поступает синхроимпульс, по переднему фронту которого изменяется содержимое накапливающего сумматора

3, а именно к содержимому накапливающего сумматора прибавляется число, установленное на выходах регистра 2, 1 сдвига. Это число отличается от содержимого регистра 2 (Z„,) на величину 2 ("1. Действительно, на вход

"Разрешение" распределителя 1 поступает сигнал логической единицы с выхода элемента 5 импликации, на

k-м выходе распределителя 1 присутствует сигнал логической единицы, который попадает на вторые входы (2k-l)-го и 2k-ro элементов ИЛИ, вследствие чего .2k-й выход регистра сдвига принудительно устанавливается в единицу, что соответствует появлению на 2k-м входе накапливающего сумматора сигнала с весом 2 (. Та2(М- k) ким образом, на выходах регистра 2 устанавливается число Е„, +

2(М-Ц

+ 2 . Поэтому по переднему фронту синхроимпульса содержимое накапливающего сумматора становится равным

Через время, определяемое элементом 4 задержки, по переднему фронту!

399733

Z А 2

Я = А„ (12) (13) Z = А 2

k-1 7 (14) 7

Я = А„, (15) 2

А,, всего М разрядов синхроимпульса в регистре 2 сдвига аналогично описанному происходит сдвиг вправо на один разряд, т.е. осуществляется операция Е„, /2.

При этом одновременно происходит принудительная установка в единицу выхода (2k-1)-го элемента ИЛИ, подключенного к входу 2k-ro D-триггера. В результате к содержимому регистра

2(М-k сдвига добавляется 2, т.е. имеет место

Z = Z, /2 + 2 1 (6) По заднему фронту синхроимпульса распределитель 1 переходит в следующее, (k+1) -е состояние, Объединив (3),(4) и (5),(6), можно записать в общем виде зависимости, которые реализуют устройство для любого

Е „- Z„, /2 +М „2"" ", (8) причем Я = 0; (9)

Z О (! 0)

Пример. Пусть требуется возвести в квадрат число 7 (lll в двоичном коде).

Согласно (7) и (8) получим

S, О + 1/О + 2 16;

Е, m mО/2+! 2 г(З -1)

° 16;

Ф

S = 16 + 1/16 + 2 36;

2 г(з-г)

Ег* 16/2 + 1 ° 2 12;

Я 36+.1/12 + 2 49;

2<Э-S) а )2/2 + !е 2

3 зв 7, Итак, в этом примере в отличие от прототипа действительно на проме- жуточных этапах получены значения

S = 16, Я 36 — квадраты последовательных приближений исходного числа

Проведем доказательство в общем виде. Обозначим через А„ последовательное приближение исходного числа на

k-м такте, его можно представить а виде

s- c

А1, *о(,о,, ° ° a„000. ° .0 А„, + о „2

Докажем методом математической ин индукции, что для любого

При k О согласно (11) А„= О, 10 а в силу (9) и (10) Я "- 0; Е О, о о т.е ° в исходном состоянии соотношения (12) и (13) выполняются.

Пусть на некотором (k-!)-м такте имеют место

20 Тогда на следующем, k-м такте используя (8), (11) и (14), получим

Zk = Е, /2 +о к2 =(А1,, 2 )/ г(м-k) М(11-1) что доказывает справедливость соотношения (! 2), используя (7), (! 1) и (15) и учитывая, что о(,< Ы,, получим

2(м-t)

Я1, ЯМ 1+ (1 (Zk 1+ 2 ) 35 А2 + (А 2 + 2 ) м

k-1+ k !с-1

- А „, + 2А„, ((., г ) + г м-

М-1 м-k

+ („° 2 ) - (A„,+ы 2 ) что доказывает справедливость соотношения (1 3), Формула изобретения! .Устройство для возведения в квадрат М-разрядных двоичных чисел, содержащее регистр сдвига, 2И-разрядные выходы которого соединены с информационными входами 2М-разрядного накапливающего сумматора, выходы ко торого являются выходами устройства, а т л и ч à ю щ е е с я тем, что, с целью расширения .класса решаемых задач эа счет обеспечения возможности вычисления квадратов последовательСоставитель Д. Сингх

Редактор А. Orap Техред Л.Сердюкова Корректор М, Пожо

Заказ 2666/48 Тираж 704 Поцписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

1 13035, Москва, Ж-35, Раушская наб., д. 4/5

«

Произнодственно"полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

5 13 ных приближений исходного числа, в него введены М-разрядный распределитель импульсов, элемент задержки, эЛементы И и импликации, причем вхо" ды "Сброс" распределителя импульсов, регистра сдвига и накапливающего сумматора объединены и являются входом сброса устройства, синхровход которого объединен с одноименным входом распределителя импульсов, с первыми входами элементов И и импликации и подключен через элемент задержки к синхровходу регистра сдвига, синхровход накапливающего сумматора соединен с выходом элемента И, второй вход которого соединен с информационным входом устройства и вторым входом элемента импликации, выХОд которого подключен к входу "Разрйщение" распределителя импульсов, выходы которого соединены с информационными входами регистра сдвига.

2. Устройство по п.1, о т л ич а ю щ е е с. я тем, что регистр

99733 6 сдвига содержит по 2N D-триггеров и элементов ИЛИ, причем выход каждого

D-триггера соединен с перным входом соответствующего элемента ИЛИ, вторые входы (2k-1)-го и 21-го элементов ИЛИ объединены и являются k-м (1с-1,2,ь ° а,М) инфОрмационным входом регистра сдвига, информационный вход первого D-триггера подключен к входу логического нуля устройства, информационный вход (2k-1) -ro D-триггера регистра сдвига соединен с выходом

1 (2k-2)-го Р-триггера (k 2,3,4,...,N), информационный вход 2k-ro D-триггера соединен с выходом (2k-1)-го элемента

ИЛИ (k=1,2,3,...,М), Б.-входы и синхровходы всех П-триггеров объединеНЫ И ПОДКЛЮЧЕНЫ СоотаатСтВЕННО K входу "Сброс" и синхровходу регист1 ра сдвига, выходы {2k-1) -го В-триггера и 2k-го элемента ИЛИ (k=1,2,3, °, М) являются соответственно (2k-1)-и

26 и 2k-и выходами регистра сдвига.