Устройство для деления Советский патент 1990 года по МПК G06F7/49 

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

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

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

ром нуль соответствует нулевому разряду р-кода Фибоначчи мастного и является делителем, a L-e число последовательности, соответствующее i-му разряду р-кода Фибоначчи частного, образуется путем сложения в р-коде Фибоначчи (1-1)-гои (i-p-1)-го чисел последовательности обобщенных чисел Фибоначчи. Число последовательно сравнивают в р-кодах Фибоначчи с делимым до тех пор, пока не определится 1-е число, которое является первым числом в полученной последовательности, большим делимого. После этого в (1-1)-й разряд р-кода Фибоначчи частного записывают единицу, а (1-1)-е число последовательности обобщенных чисел Фибоначчи вычитают в р-коде Фибоначчи из делимого. Полученный остаток сравнивают в р-коде Фибоначчи с числами полученной последовательности и выделяют п-е число последовательности, которое является наибольшим числом последовательности меньшим, чем остаток. После этого в п-й разряд р-кода Фибоначчи частного записывается единица, а ш-е число последовательности вычитают в р-коде Ф

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

На фиг. 1 приведена структурная схема устройства для деления; на фиг. 2 - схема блока управления; на фиг. 3 временная диаграмма работы блока управления.

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

0

5

мого, сумматор 2, осуществляющий сложение р-кодов Фибоначчи, поступающих на его входы, регистр 3 остатка, в котором хранится р-код.Фибоначчи разности делимого (остатка) и числа из последовательности обобщенных чисел Фибоначчи, преобразователь 4 прямого кода в обратный,осуществляющий преобразование прямого р-кода Фибоначчи делителя в обратный р-код Фибоначчи, который является исходным в последовательности кодов, формируемой генератором 5 последовательности 5 обобщенных чисел Фибоначчи блок б управления, регистр 7 частного, в котором формируется результат деления в р-коде Фибоначчи, блок 8 памяти, в котором хранится последовательность обобщенных чисел Фибоначчи, счетчик 9, который формирует адрес записи и выборки кодов последовательности обобщенных чисел Фибоначчи блока 8 памяти, первый коммутатор 10, второй коммутатор 11, вход 12 делимого устройства, вход 13-делителя устройства, вход 14 начальной установки устройства, вход 15 пуска устройства, выход 16 частного устройства, входы блока 6 управления, выходы 21- 27 блока 6 управления.

В состав блока 6 управления (фиг. ) входят триггеры 28-31 элемент И-ИЛИ 32, элементы , генератор ЗУ синхроимпульсов и элементы ИЛИ 40 и 41 .

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

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

На первом такте работы устройства генератор 5 формирует обратный 1-код Фибоначчи нулевого числа последовательности, приведенной в таблице.

0

5

0

5

0

5

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

Нулевой сигнал, поступающий с выхода 22 блока 6 управления на управляющий вход коммутатора 10, разрешает подачу кода с выхода генератора 5 на второй вход сумматора 2, который осуществляет сложение этого кода с кодом делимого. При этом на вход переноса младшего разряда сумматора 2 постоянно подается единица, т.е. сложение выполняется как бы с дополнительным кодом. Если на выходе пе- реноса старшего разряда сумматора 2 отсутствует сигнал переноса, то это означает, что код, поступающий из регистра 1, меньше кода, поступающе55217 6

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

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

Ю разности, но теперь это разность между первым остатком и очередным (предыдущим) числом последовательности обобщенных чисел Фибоначчи, подаваемым на второй вход сумматора 2 с

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

Изобретение относится к вычислительной технике и предназначено для деления многоразрядных чисел в 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 табл.

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

ления на выходе 2k единичного сигнала. При этом код с выхода генератора 5 записывается в блок 8 памяти по адресу, формируемому счетчиком 9,

увеличивающим свое состояние на еди- -5 ряда сумматора 2 формируется нуленицу

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

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

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

45 рее очередного числа последовательности, уменьшая свое состояние на единицу.

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

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

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

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

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

рее очередного числа последовательности, уменьшая свое состояние на единицу.

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

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

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

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

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

При сложении кодов нулевого числа последовательности, являющегося Делителем, и третьего остатка оказы-- Е|ается, что остаток меньше делителя. О выхода переноса старшего разряда Сумматора на вход 17 блока 6 управления поступает единичный сигнал. блок 6 на выходах 22. 25 и 27 Формирует управляющие сигна лы, под действием которых код;, записанный в регисре 7 частного, сдвигается на один разряд, а счетчик Э, уменьшая свое 0 состояние на единицу, становится равным нулю, что является признаком окончания операции деления. С второго выхода счетчика 9 поступает единичный сигнал на вход 18 блока 6 управления, который прекращает формирование управляющих сигналов. При этом в регистре 7 частного находится код частного, а в регистре 3 остатка находится код остатка деления. Формула изобретения

Устройство для деления, содержащее регистры делимого остатка и часного, преобразователь прямого кода

5

0

5 o

55

5

40

45

50

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

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

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

affiLJTJTJTJTnJTJn

n-----lr 1J-L

z/ ПJT П

22 -I

r JOCXIX XIXDCD

cr

иnJTJTJTJ J T --

27 „ -J UnjnJHJ JTJl

25П П П П П П

-

Фиг.Э