Устройство для возведения чисел в степень четь[ре

Устройство для возведения чисел в степень четь[ре

Иллюстрации

Показать все

Реферат

 

290279

О П

Союз Советских

Социалистических

Республик

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Зависимое от авт. свидетельства №

Заявлено 14.Ч.1969 (№ 1331578/18-24) с присоединением заявки ¹

Приоритет

МПК 6 061 7/52

Комитет по делам тизобретеиий и открытий при Совете Министров

СССР

УДК 681.325.59(088.8 ) Опубликовано 22.Х11.1970. Бюллетень № 2 за 1971

Дата опубликования описания б.1 .1971

Автор изобретения

Э. А. Чернов

Государственный всесоюзный центральный научно-исследовательский институт комплексной автоматизации

Заявитель

УСТРОЙСТВО ДЛЯ ВОЗВЕДЕНИЯ ЧИСЕЛ В СТЕПЕНЬ ЧЕТЬ1РЕ

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных машинах и устройствах автоматики.

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

Целью изобретения является уменьшение количества арифметических операций, необхо- 10 димых для получения результата.

Предлагаемое устройство отличается тем, что содержит квадратор, умножитель на коэффициент три, умножитель на коэффициент четыре, умножитель на коэффициент шесть, ре- 15 гистр второго блока и регистр результата, причем выход младшего разряда регистра числа соединен с входом младшего разряда регистра результата, выход второго разряда регистра числа — с входом младшего разряда 20 регистра второго блока, выход третьего разряда регистра числа — с входами младших разрядов квадратора и ряда сумматоров второго блока. Выход каждого t-го из остальных разрядов регистра числа соединен с входом 25 (i — 1)-го разряда квадратора, выход каждого -го разряда квадратора (кроме второго)— с входом (i+1)-го разряда ряда сумматоров

pòîðîãî блока. Выходы разрядов ряда сумматоров второго блока соединены с входами со- 30 ответствующих разрядов умножителя на коэффициент три, выход каждого /-го разряда которого соединен с входом (i+ 1)-ro разряда регистра второго блока, выходы разрядов этого регистра — с входами соответствующих разрядов ряда сумматоров третьего блока, выходы разрядов этого ряда сумматоров соединены с соответствующими входамп разрядов умножптеля на коэффициент четыре, выход каждого i-го раязряда этого умножителя соединен с входом (i — 2)-го разряда другого ряда сумматора третьего блока, выход каждого i-го рязряда этого ряда сумматоров соединен с (i+3)-м разрядом регистра результата, выходы разрядов квадратора соединены с входами соответствующих разрядов умножптеля на коэффициент шесть, выходы которых соединены с соответствующими разрядами другого ряда сумматоров третьего блока.

Построение устройства основано на следующих соображениях.

Берется некоторое число, записанное в виде:

Ас = а„ . r" — -+- а„° r" — - +,..., + — асг- 4- а;г + apl, где а; — цифры числа, г — основание системы счисления.

Это можно представить в виде: (а„(г" + а„аг" +,..., -,-а г -+- Q>rp) г+а0, обозначив часть числа, заключенную в круг24)0279 а, ао аз и — 1 а л — 2 ао аз а, а л-1 а п — 2 а л — 2 ао о

М х аз а л — 1 а и — 2 а, аз а л — 1 а2 о (»

Ж о n — 1 л — 2 а а ж а л — 1 а п — 3

n — 2

) 3 лые скобки через А, (индекс при букве А указывает на самую младшую цифру части числа в скобках), получим следующую форму записи числа А0

4p = A1r + а0.

Числа в этой записи возводятся в степень q:

Ао = (А,r + аоУ: А у . r + С А у r< ао +

1 С2, фу — 2112 r>ó — 2 1 4.т . Ад — т am Гд — т

+ O 1 0 »"" q 1 0

+ + ч — A,.ap — .r+ap<

Степень q у части числа А1 здесь сохранилась только в первом члене, все остальные члены разложения содержат более низкие степени части числа без младшей цифры А1, но часть числа А содержит на одну цифру меньше, чем исходное число. Аналогичный прием повторяется к первому члену А у . rp (умножение íà гу равносильно сдвигу влево на q разрядов и, следовательно, все члены разложения достаточно сдвинуть на q разрядов влево). Очевидно, что степень q после этого будет содержать также только первый член (А24 r<), но число А2 будет уже без двух младших цифр. Продолжая этот процесс и раз, получим некоторую матрицу, сумма строк которой равна степени q исходного числа, но степени всех частей числа будут не выше, чем (q — 1), а в степень д будут возводиться только цифры исходного числа, а не его части. Аналогичным образом теперь можно поступить со всеми членами этого разложения и снизить степень каждого из них еще на единицу.

Пусть, например, необходимо возвести в квадрат некоторое число, записанное в виде: а 1.2"- -1-а„2 2" — -1-,-1- аз 2 -)- а2 2 +

+ а121+ а0.

Умножение на бином инальный коэффициент 2 в этой матрице выполнено за счет сдвига на разряд влево.

Нетрудно убедиться, что число слагаемых цифр в этой матрице:

1+(и — 1) + и +и

2 2 где и — разрядность числа, что почти в два раза меньше, чем при обычном способе умножения.

Пусть теперь необходимо возвести в куб некоторое число, записанное в регистре или

При возведении этого числа в квадрат каукдый из квадратов слагаемых а;2 преобразуют в а ; 22 . Так как преобразования осуществляются в двоичной системе счисления, то

5 азу=а;, а умножение на 2" равносильно сдвигу,влево на 2i разрядов, что соответствует сдвигу на 1 разрядов слагаемого а;.2 . Поскольку цифры исходного числа записываются подряд, то квадраты в силу указанного пре10 образования оказываются записанными через разряд.

После этого прибавляют к квадратам цифр исходного числа удвоенное произведение каж15 дой цифры на остальные, т. е. произведение вида 2а; 2 а;2>, нетрудно видет, что

2ау. 2 a; 21 = а,а; 24+у+

Последнее выражение означает, что эти уд20,военные произведения получаются сдвигом цифры ау влево на число разрядов, равное

j+ 1.

Берут самую младшую цифру а0 и умножа25 ют ее на остальные цифры числа. Очевидно, что при этом получится исходное число, сдвинутое на один разряд влево без младшей цифры. Затем берут следующую цифру и умножают на цифры исходного числа без двух

З0 младших цифр, что равносильно сдвинутому исходному числу на два разряда влево без двух младших цифр. Эту операцию продолжают до тех пор, пока не будет умножена предпоследняя цифра на самую старшую.

Складывают полученные произведения с квадратами цифр .исходного числа и получают следующую матрицу, сумма строк которой равна квадрату исходного числа.

40 другом запоминающем устройстве в двоичной системе счисления, например (для большей наглядности) пятиразрядное в виде: а424 + аз23 + a222 + a121 + а020

45 Для этого возведем в куб это число, которое представим в виде ((a42з + аз22 -1- a221 + а,) + ap)ç.

По известному разложению по биному Ньютона

50 получим (а4азаза ) 2 +- 3 (а4азаза1) ар 22 -1+3 (а4аза2а1) а02 2 -4- ар, но в двоичной системе счисления ау = a;; умножение на уу< не

290279 аз а2 а2

4 а х х

М

Я х

И а4

a4 as a2 а, а а4 аз аз (а, а, аз а,) а4 аз аз а<

gp ар

as а2 а4 а4 х

% о х

Я

Р» аоХа1 аз а а, Х а, ао Х аз аз а4 аз аз а1 ар аз а, аз ао а аз а, а X ао

as аз аз а4 а4 аз а2 аз аз а4 аз а4 аз аз X аз а4 а, а4 а4

Хо аЗ а4 го

М о а, И ао а, аз а, а4 аз а2 а, а, а4 аз а2 сдвигает выражения (а4азаза1), выражение (а4азаза1) сдвигается влево на разряд, так как степень двойки в самом младшем разряде этого числа равна единице и после возведения .в квадрат удвоится, что соответствует сдвигу на один разряд влево. Кроме того, из вышеприведенного примера, возведения числа в квадрат известно, что выражение (a1азаза1) равно сумме строк следующей матрицы:

Повторим вышеприведенный прием теперь к выражению (а4азаза1) . Поскольку степень двойки при коэффициенте а> равна единице, то (21)з = 2з, или самый младший разряд этого числа будет размещен на четвертом месте или через два разряда от ао. аз Х ао аз Х ао

CO а2 х а, 4 а. Х а, аз Х а, 2 аз а, Эта матрица построена для пятиразрядного числа (но таким же способом можно построить матрицу для числа произвольной разрядности), Аналогичным образом строятся матрицы более высоких степеней чисел.

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

Запишем теперь матрицу квадрата числа для сложения частей исходного числа, начиная со старших разрядов:

Перепишем полученный результат с учетом этих соображений и мест цифр в разрядной сетке:

N Таким образом, матрица для выражения (а,азаза,) не отличается от предыдущей, но смещена на три разряда, влево, при этом степень «три» оттанется у выражения (а аза2).

Продолжая этот процесс дальше, получим

15 окончательно следующую матрицу, сумма строк которой равна кубу числа (а4азаза1ао): г5 Очевидно, что для реализации этой матрицы в виде устройства достаточно иметь два регистра: один — исходного числа, а другой— накапливающий сумматор с цепями сдвига влево на два разряда за такт. Вдвигая со стоЗО роны старших младших разрядов исходное число по одному разряду в регистр, а содержимое накапливающего сумматора сдвигая

290279

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

Ha tepTc>tкит регистр 1 числа, квадратор (регистр 2 первого блока), первый ряд сумматоров 8 первой группы второго блока, умножитель 4 на коэффициент «три» второго блока, регистр 5,второго блока, первый ряд сумматоров б первой группы третьего блока, умножитель 7 на коэффициент «четыре» третьего блока, умно>китель 8 на коэффициент «шесть» третьего блока, первый ряд сумматоров 9 второй группы третьего блока и регистр 10 третьего блока (регистр результата).

Кроме того, на чертеже приведены следующие обозначения: а; — l; — разряды соответствующих блоков, причем меньшим цифрам соответствуют младшие разряды.

Стрелки на рисунке показывают направление передачи сигнала между разрядами блоков, цифры с буквами у свободных концов стрелок указывают: цифра на номер разряда, а буква на блок, к котором должен быть подсоединен этот разряд. Регистр 1 имеет семь разрядов, а регистр 2 — десять, разрядность исходных чисел — шесть.

Регистры 1, 2, 5 и 10 снабжены цепями сдвига, причем за один такт сдвиг в регистре

1 осуществляется на один разряд влево, в регистре 2 — на два разряда, в регистре 5 — на три разряда и в регистре 10 — на четыре разряда.

Вход разряда b регистра 2 соединен с выходом разряда а» регистра 1, а входы разрядов b, b», bs и b соединены с выходами разрядов а», а;„а и à .

Выходы разрядов сь C>, C> и с» ряда сумматоров 8 соединены с выходами разрядов а, а . а5 и а6 регистра 1. Вторые входы разрядов с и с» ряда сумматоров 8 соединены с выходами разрядов b» и b> регистра 2 (выход разряда b регистра никуда не подается, так как сигнал, выхода этого разряда всегда соответствует нулевому сигналу, для двоичной системы счисления). Выходы разрядов с-,. cr„ с, с и с> ряда сумматоров 8 соединены с выходами разрядов Ь», 4, bg, Ь и bg регистра 2, Выходы сумматоров 3 поразрядно соединены с входа ми умножителя 4, биноминальный коэффициент этого блока равен трем. Выходы умножителя 4 соединены с входом регистра 5, причем выход младшего разряда множителя

4соединен свходом второго разряда регистра

5. Остальные разряды также подсоединены со сдвигом на разряд влево.

Выход.. регистра 5 соединены с входами

15 го

ЗО

8 первого ряда сумматоров б первой группь третьего блока, причем младший разряд ei регистра 5 соединен с входом разряда f3 ряда сумматоров б. Остальные разряды подсоединены со сдвигом на два разряда влево. Входы разрядов fI, f, f3, f» и f5 соединены с выходами соответственно разрядов а2, аз, а>,

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

9 второй группы третьего блока со сдвигом на два разряда влево.

Выходы регистра 2 соединены непосредственно со входами умножителя 8 (биноминальный коэффициент этого умножителя равен шести).

Выходы ряда сумматоров 9 соединены с входами регистра 5, при этом формально необходимо было бы соединить младший разряд к с входом разряда е, но поскольку в качестве примера рассматривается устройство, работающее в двоичной системе счисления, то в связи с тем, что биноминальные коэффициенты для третьего блока — 4 и б, то первый значащий разряд ряда сумматоров 9 будет совпадать с четвертым разрядом регистра 10, таким образом, разряд к ряда сумматоров 9 соединен с разрядом е» регистра 10.

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

Исходное число последовательно вдвигают в регистр 1 старшими разрядами вперед. Прн сдвиге на один разряд влево в регистре 1 одновременно производят сдвиги,в регистре 2 на два разряда влево, в регистре 5 — на три разряда влево и в регистре 10 — «a четыре разряда влево. После каждого сдвига анализируют состояние разрядов аь а2 и аз регистра 1. Если содержимое разряда а соответствует сигналу единицы (໠— — 1), то производят сложение содержимого регистров 1 и 2; если а. = 1, то сложение кода с выхода ряда сумматоров и с содержимым регистра 5 и подают код с выхода ч множителя 8 на вход ряда сумматоров 9; если а — — 1, то подают код с выхода»множителя 7 на .вход ряда сумматоров 9. Если же содержимое какого-либо из этих разрядов равно нулю, то существующие операции в данном цикле запрещают.

Завершается операция после цикла, следующего за тем сдвигом, когда младший разряд исходного числа займет места разряда а .

Аналогичным образом мажино создать устройства более высоких степеней чисел.

Предмет изобретения

Устройство для возведения чисел в степень четыре, состоящее из регистра числа и накапливающих сумматоров, отличак>щееся тем, 290279 что, с целью повышения быстродействия, оно содержит квадратор, умножитель на коэффициент «три», умножитель на коэффициент

«четыре», умножитель на коэффициент

«шесть», регистр второго блока и регистр результата, причем выход младшего разряда регистра числа соединен с входом младшего разряда регистра результата, выход второго разряда регистра числа соединен с входом младшего разряда регистра второго блока, выход третьего разряда регистра числа соединен с входами младших разрядов квадратора и ряда сумматоров второго блока, выход каждого

i-го из остальных разрядов регистра числа соединен с .входом (i — 1) -го разряда квадратора, выход каждого i-го разряда квадратора (кроме второго) соединен с входом (i++ 1) -го разряда ряда сумматоров второго блока, выходы разрядов ряда сумматоров второго блока соединены с входами соответствующих разрядов умножителя,на коэффициент «три», выход каждого i-го разряда которого соединен с входом (i + 1)-ro разряда регистра второго блока, выходы разрядов этого регистра соединены с входами соответствующих разрядов ряда сумматоров третьего олока, выходы разрядов этого ряда сумматоров соединены с соответствующими входами разрядов умножителя на коэффициент четы10 ре, выход каждого i ãî разряда этого умноякитсля соединен с входом (i — 2) -го разряда другого ряда сумматоров третьего блока, выход каждого -го разряда этого ряда сумматоров соединен с (+ 3) -м разрядом ре15 гистра результата, выходы разрядов квадратора соединены с входами соответствующих разрядов умножителя на коэффициент

«шесть», выходы которых соединены с соответствующими разрядами другого ряда сумматоров третьего блока.

2902 79

Составитель И. В. Долгушева

Редактор E. В. Семанова Техред T. П. Курилко Корректор В. И. Жолудева

Заказ 153/18 Изд. № 83 Тираж 473 Подписное

ЦНИИПИ Комитета по делам изобретений и открытий при Совете Министров СССР

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

Тигографпя, пр. Сапунова, 2