Устройство для деления

 

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

„,SU„, 1552174

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

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИН

Р1) С 06 F 7/49

>

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

К Д BTGPCHGMV СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРИТИЙМ

ПРИ ГННТ СССР (21) 4465855/24-24 (22) 26.07,88 (46) 23.03.90.„ Бюл. > 11 (71) Специальное конструкторско-технологическое бюро "Модуль" Винницкоо

ro политехнического института (72) А.П.Стахов, В.А.Лужецкий, . И.M.Ïoïoâè÷ и В.В.Коротин (53) 681.325(088.8) (56) Карцев М.А. Арифметика цифровых машин. - М.:Наука, 1969, с. 494.

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

>r 744564, кл. С 06 F 7/49, 1978. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ (57) Изобретение относится к вычислительной технике и предназначено для деления многоразрядных чисел в р-кодах Фибоначчи. Цель изобретения — повышение быстродействия деления чисел, представленных в р-кодах Фибоначчи. Устройство для деле" ния содержит регистр 1 делимого, предназначенный для хранения р-кода

Фибоначчи делимого, сумматор 2, ре- . гистр 3 остатка, в котором хранится р-êoä Фибоначчи разности делимого (остатка) и числа из последовательно обобщенных чисел. Фибаначчи, преобразователь 4 прямого кода делителя в обратный. генератор 5 последовательности обобщенных чисел Фибоначчи, блок 6 управления, регистр 7 частного, в котором формируется результат деления в р-коде Фибоначчи, блок 8 памяти, в котором хранится последовательность обобщенных чисел Фибоначчи, счетчик 9, предназначенный для Формирования адреса записи и выборки кодов из блока 8 памяти, первый коммутатор 10, обеспечивающий подачу на второй вход суммаТора 2 кода с выхода генератора 5 или с выхода блока

8 памяти, второй коммутатор 1 I.îáåñпечивающий подачу на второй вход регистра 1 кода с выхода регистра 3 или с второго выхода сумматора 2.

3 ил., 1 табл.

1552 17ч

Изобретение относится к вычислительной технике и предназначено для деления многоразрядных чисел в.р-кодах Фибоначчи.

Целью изобретения является повышение быстродействия устройства.

При делении чисел в р-кодах Фибоначчи образуют последовательность обобценных чисел Фибоначчи. Начальное число последовательности с номе1 ром нуль соответствует нулевому разряду р-кода Фибоначчи частного и является делителем, а :i-е число последовательности, соответствующее i-му разряду р-кода Фибоначчи частного, образуется путем сложения е р-коде

Фибоначчи (i — 1)-го и (i-р-1)-го чисел последовательности обобщенных чисел

Фибоначчи. Число последовательно 20 сравнивают в р-кодах Фибоначчи с делимым до тех пор, пока не опредег ится 1-е число, которое является перBblM числом в полученной последова-! тельности, большим делимого. После 25 этого в (1-1)-й разряд р-кода Фибоначчи частного записывают единицу, а (1-1)-е число последовательности обобщенных чисел Фибоначчи вычитают в р-коде Фибоначчи из делимого. По- gp лученный остаток сравнивают в р-коде

Фибоначчи с числами полученной последовательности и выделяют m- е число последовательности, которое является наибольшим числом последовательности, меньшим, чем остаток. После этого в

m-й разряд р-кода Фибоначчи частного записывается единица, а ш-t. число последовательности вычитают в р-коде Фи— боначчи из остатка, получая при этом 40 очередной остаток. Процесс сравнения чисел последовательности с очередным остатком и вычитание повторяют до тех пор,пока остаток не станетменьше делителя. При этом контролируют, чтобы в р-коде Фибоначчи частного в каждой группе из (р+1) подряд идущих разрядов кода встречалось не более одной единицы. Нарушение этого условия является признаком неправильного выполнения операции деления.

На фиг. 1 приведена структурная схема устройства для деления, на

Фиг. 2 - схема блока управления; на

Фиг..3 — временная диаграмма работы блока управления.

Устройство для деления содержит регистр 1 делимого, предназначенный для хранения р-кода Фибоначчи дели—

1 мого, сумматор 2, осуществляющий сложение р-кодов Фибоначчи, поступающих на его входы, регистр 3 остатка, в котором хранится р-код Фибоначчи разности делимого (остатка) и числа из последовательности обобщенных чисел Фибоначчи, преобразователь

4 прямого кода в обратный, осуществляющий преобразование прямого р-кода Фибоначчи делителя в обратный р-код Фибоначчи, который является исходным . в последовательности кодов, Формируемой генератором 5 последовательности обобщенных чисел Фибоначчи, блок б управления, регистр 7 частного, в котором формируется результат деления в р-коде Фибоначчи, блок 8 памяти, в котором хранится последователь1 ность обобщенных чисел Фибоначчи, счетчик 9, который формирует адрес записи и выборки кодов последовательности обобщенных чисел Фибоначчи блока 8 памяти, первый коммутатор 10, второй коммутатор 11, вход 12 делимого устройства, вход 13,делителя уст4 ройства, вход 1Ч начальной установки устройства, вход 15 пуска устройства, выход 16 частного устройства, входы

17-20 блока б управления, выходы 21—

27 блока 6 управления.

В состав блока 6 управления (Фиг. 2) входят триггеры 28-31, элемент И-ИЛИ 32, элементы 33-38., генератор 39 синхроимпульсов и элементы

ИЛИ ч0 и 41.

Работу устройства для деления рассмотрим ча примере р-кода Фибоначчи при р = 1.

Пусть делимое равно 102, а дели" тег1ь 5. Единичный сигнал, поступающий на вход 14 начальной установки устройства, приводит к тому„ что содержимое регистра 1 делимого, генератора 5 последовательности обобщенных чисел Фибоначчи и триггеров блока 6 управления становится равным нулю, а счетчик 9 равен единице. В регистр 1 с входа 12 устройства записывается l-код Фибоначчи числа 102, в преобразователь ч прямого кода в обратный с входа 13 устройства подается I-код Фибоначчи числа 5 и обратный код числа 5 записывается в генератор 5, На первом такте работы устройства генератор 5 Формирует обратный I-код

Фибоначчи нулевого числа последовательности, приведенной в таблице.

1552

Нулевое число последовательности обобщенных чисел Фибоначчи равно обратному I-коду Фибоначчи делителя.

Нулевой сигнал, поступающий с выхода 22 блока 6 управления на управляющий вход коммутатора 10, разрешает подачу кода с выхода генератора

5 на второй вход сумматора 2, который осуществляет сложение этого кода 10 с кодом делимого. При этом на вход переноса младшего разряда сумматора

2 постоянно подается единица, т.е. сложение выполняется как бы с дополнительным кодом. Если на выходе пе- 15 реноса старшего разряда сумматора 2 отсутствует сигнал перекоса, то это означает, что код, поступающий иэ регистра 1, меньше кода, поступающего с выхода генератора 5. Если на вы- 20 ходе переноса старшего разряда сумматора 2 Формируется единичный сигнал, то это значит, что код, поступающий из регистра 1, больше кода, поступающего с выхода генератора 5. 25

Каждый код, Формируемый на выходе. сумматора. 2 и являющийся положительной разностью входных кодов, записывается в регистр,3 остатка под действием сформированного блоком 6 управ-3о ления на выходе 24 единичного сигнала. При этом код с выхода генератора

5 записывается в блок 8 памяти по адресу, Формируемому счетчиком 9, увеличивающим свое состояние на единицу.

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

Отсутствие на входе 17 блока 6 управления единичного сигнала, поступающего с выхода переноса .старшего разряда сумматора 2, приводит к сле" дующему. Блок 6 управления Формирует на выходе 24 нулевой сигнал, запрещающий запись очередного кода с выхода сумматора 2 в регистр 3 остатка, на выходе 21 - единичный сигнал, разрешающий запись в регистр f кода остатка, а на выходе 22 блока 6 присутствует нулевой сигнал, который разрешает подачу кода остатка из регистра 3 через коммутатор 11 на второй вход регистра 1. Таким образом, в ре0

174 6 гистр 1 записывается код остатка, полученного на предыдущем (пятом} такте сложения кодов в сумматоре 2.

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

Сумматор 2 вновь формирует код разности, но теперь это разность меж,ду первым остатком и очередным (предыдущим) числом последовательности обобщенных чисел Фибоначчи, подаваемым на второй вход сумматора 2 с блока 8 памяти через коммутатор 10 .под действием единичного управляющего сигнала, сформированного блоком 6 управления на выходе 22. На выходе переноса -старшего. разряда сумматора 2

Формируется нулевой сигнал, свидетельствующий о том, что число последовательности . больше первого остака. При этом на выходах 25-27 блока 6 управления присутствуют единичные управляющие сигналы, под действием которых в регистр 7 частного записывается единица и сдвигается на один разряд в сторону старших разрядов, а счетик 9 выбирает адрес очередного числа последовательности, уменьшая свое состояние на единицу.

Код четвертого числа последовательности больше кода первого остат,,ка. На выходе переноса старшего раэ1 ряда сумматора 2 формируется нулевой сигнал. Блок 6 управления на выходах 22, 25 и 27 Формирует единичные управляющие сигналы, под действием которых с блока 8 памяти через коммутатор 10 на второй вход сумматора 2 подается код очередного числа последовательности, код, записанный в регистре 7 частного, сдвигается на один разряд, а счетчик 9 выбирает ад рес очередного числа последовательности, уменьшая свое состояние на единицу.

Код третьего числа последовательности меньше кода первого остатка.

На выходе переноса старшего разряда сумматора 2 формируется единичный сигнал. Блок 6 управления на выходах

21, 22 и 25-27 Формирует единичные управляющие сигналы, под действием которых код разности между первым остатком и третьим числом последовательности записывается в регистр 1. в регистр 7 частного записывается единица и код, :записанный в этом

1552174 регистре, сдвигается на один разряд в сторону старших разрядов, счетчик

9 выбирает адрес очередного числа последовательности, уменьшая свое с стояние на единицу. Код второго ! числа последовательности оказывается большим кода второго остатка.

Блок 6 формирует на выходах 22, 2 и 27 управляющие сигналы, под д йствием которых счетчик 9 выбирает а рес числа последовательности, под ваемого с блока 8 памяти, уменьшая с ое состояние на единицу, а код, э писанный в регистре 7 частного, сдвигается на один разряд. Код первог числа последовательности меньше к да второго остатка. На входе 16 б ока б присутствует единичный сигн л, под действием которого на выхо- щ д х 21. 22 и ?5-?7 этого блока форм руются управляющие сигналы, которые и иводят к тому, что код положитепьн и разности между вторым остатком и первым числом последовательности записывается в регистр 1 делимого, счетчик 9 выбирает адрес кода очередного (нулевого) числа последовательности,. состояние счетчика уменьшается на единицу, в регистр 7 частного записывается единица и код, записанный в этом регистре, сдвига тся на один разряд, 1

При сложении кодов нулевого числа последовательности, являющегося

Делителем, и третьего остатка оказывается, что остаток меньше делителя. выхода переноса старшего разряда сумматора на вход 17 блока .6 управления поступает единичный сигнал.

Блок 6 на выходах 22. 25 и 27 формирует управляющие сигналы, под дейстВием которых код, записанный в регист.ре 7 частного, сдвигается на один разряд, а счетчик 9, уменьшая свое о состояние на единицу, становится равным нулю, что является признаксм окончания операции деления. С второго выхода счетчика 9 поступает единичный сигнал на вход 18 блока 6 управления, который прекращает форми рование управляющих сигналов. При этом в регистре 7 частного находится код частного, а в регистре 3 остатка находится код остатка деления.

Формула и э о б р е т е н и я

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

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

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

Разряд .Вес разряда Последовательность чисел

Код частного

i

3

Ц

6

Ц

2

2

5

13

21

13

Я.

3

4 102

10 с 102

15 (102

25 102

40 - 102

65 102

105 > 102

65 >37

40 >37

25 37

15.> 12.

1О -с 12

5)2

1 0 l

1

1552174 гз я п / 1 ГШ.

Корректор З.Лончакова

Редактор В. Петран

Заказ 330

Тираж 561

Подписное

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

113035, Иосква, Ж-35, Рауиская наб., д. 4/5

Производственно-издательский комбинат "Патент", г.ужгород, ул.Гагарина, 101 г

Составитель Е.Иурзина

Техред JI.Олийнык