ПАРАЛЛЕЛЬНЫЙ СУММАТОР КОДОВ ФИБОНАЧЧИ Российский патент 1995 года по МПК G06F7/49 

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

Известен параллельный сумматор кодов Фибоначчи [1] содержащий первый и второй регистры, параллельный полусумматор, блок определения окончания суммирования, блок коммутации, блок контроля и блок нормализации.

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

Наиболее близким к предлагаемому является накапливающий сумматор [2] каждый 1-й разряд которого содержит триггер со счетным входом, элементы И, ИЛИ и элемент задержки, причем входные шины соответствующих разрядов первого и второго слагаемых соединены с первым и вторым входами первого элемента ИЛИ данного разряда, выход которого подключен к счетному входу триггера, нулевой вход которого подключен к шине сброса, а единичный выход к первому входу первого элемента И, выход которого подключен к первому входу второго элемента ИЛИ, второй вход которого подключен к выходу второго элемента И, причем в каждый разряд введен элемент сложения по модулю 2, выход которого подключен к третьему входу первого элемента ИЛИ, выход которого соединен с вторым входам первого элемента И, первый и второй входы элемента сложения по модулю 2 соединены соответственно с первым и вторым входами переноса в данный разряд сумматора и с первым и вторым входами элемента И, выход второго элемента ИЛИ подключен к входу элемента задержки, выход которого, являющийся выходом переноса в (1+1)-й разряд сумматора, подключен к первому входу третьего элемента И, второй выход которого соединен с управляющей шиной, а выход является выходом переноса в (1-2)-й разряд сумматора, единичный выход триггера со счетным входом является выходом суммы данного 1-го разряда.

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

Целью изобретения является увеличение быстродействия за счет возможности одновременного суммирования n-разрядных N-чисел, представленных в любой форме фибоначчиевой системы счисления.

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

Предлагаемое устройство соответствует критерию изобретения "новизна".

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

На чертеже представлена структурная схема предлагаемого устройства.

Устройство содержит ПЗБ1, ПЗБ2, ПЗБ3, ПЗБ4, входные регистры 8.1-8.4, регистр управления 6, триггер управления 7, блок задержки 5.1, элементы задержки 5.2-5.Р, элементы ИЛИ 9.1-9.К1, 12.1-12.К2, 13, 18.1, 18.2, элементы И 10.1-10.N, 11.1-11.К2, 16, 17.1-17.К2, 19.1-19.3, элементы НЕ 14, 20, трехвходовый элемент ИЛИ-НЕ 15, входы синхронизации 1, информационные входы 2 и информационные выходы 1-(n+m).

В табл. 1 и 2 представлены адреса и записанные по этим адресам слова для ПЗБ1 при сложении четырех n-разрядных фибоначчиевых чисел в удобной для рассмотрения последовательности.

В табл. 3, 4 и 5 показаны адреса и записанные по этим адресам слова соответственно для ПЗБ2, ПЗБ3 и ПЗБ4 при сложении четырех n-разрядных фибоначчиевых чисел.

ПЗБ2 располагает единицы входного слова подряд в младших разрядах.

Работа устройства осуществляется следующим образом. Во входные регистры 8.1-8. N записываются слагаемые. По приходу первого импульса на входы синхронизации 1, на вход ПЗБ2 поступают первые разряды слагаемых, преобразованный в ПЗБ2 код поступает на входы Х ПЗБ1. По этому же такту на первые входы элементов И 10.1-10.N поступает логическая единица с первого выхода регистра управления (РУ) 6, в результате чего код с выхода ПЗБ2 поступает на вход ПЗБ3, преобразованный в нем код поступает на первые входы элементов ИЛИ 9.1-9. К1, на кторые входы которых по этому же такту поступают нули с входа блока задержки (БЗ) 5.1. По адресу, указанному на входах XYZ, код с выхода ПЗБ1 поступает на вход Б3 5.1.

По приходу второго импульса на входы синхронизации 1 на вход ПЗБ2 поступают вторые разряды слагаемых, код с выхода ПЗБ2 поступает на входы Х ПЗБ1, код с входа Б35.1 поступает на входы Y и Z ПЗБ1, код с выхода ПЗБ1 поступает на вход Б35.1. По этому же такту логическая единица с первого выхода РУ 6 переходит на его второй выход и поступает на вход разрешения записи триггера управления (ТУ)7. Если на 1-3 выходах ПЗБ1 имеются логические нули, в него записываются единицы.

По третьему импульсу на вход ПЗБ2 поступают третьи разряды слагаемых, код, преобразованный в ПЗБ2, поступает на входы Х ПЗБ1, код с входа БЗ 5.1 поступает на вторые входы элементов ИЛИ 9.1-9.К1. Логическая единица с второго выхода РУ6 переходит на его третий выход, в результате чего сигнал с выхода ТУ7 поступает на третий вход элемента ИЛИ 9.1. Код по адресу, указанному на входах XYZ ПЗБ1, поступает на вход БЗ 5.1.

При последующих тактах на выходах РУ6 будут логические нули. Трехвходовый элемент ИЛИ 1.3 и элемент НЕ 14 поддерживают первые три такта на выходе 4 БЗ 5.1 логический нуль.

Начиная с четвертого импульса, по каждому импульсу синхронизации на вход ПЗБ2 поочередно поступают остальные разряды слагаемых, преобразованный в ПЗБ2 код поступает на входы Х ПЗБ1, код с входа БЗ 5.1 поступает на входы Y и Z ПЗБ1, код указанный по адресу XYZ, с выхода ПЗБ1 поступает на вход БЗ 5.1, сигнал с 4-го выхода которого поступает на элементы задержки (ЗЗ) 5.2-5.Р.

Если в процессе сложения на выходах 5 ПЗБ1 и 4 БЗ 5.1 появятся логические единицы, то на выходе элемента НЕ 20 будет логический нуль, в результате чего код с выхода ПЗБ1 поступает на вход ПЗБ4, код с выхода которого поступает на вход БЗ 5.1, сигнал с выхода 5, ПЗБ4 поступает на вход 33 5.2, а нулевой сигнал с выхода элемента НЕ 20 на вход 33 5.3.

По истечении n-тактов, где n-разрядность слагаемых, на выходах 1-n появятся младшие n разрядов, а на выходах (n+1)-(n+m) старшие m разрядов результата сложения n-разрядных N-чисел.

Число элементов задержки определяется по формуле
z-n-5
Число слов ПЗБ1 определяется по формуле
M-(10+5(N-Р2))(N+1)
П р и м е р 1. Пусть необходимо сложить следующие числа, представленные в фибоначчиевой системе счисления: 100100, 111100, 000100, 001100 n-6, N-4. Число 33 Z-n-5-6-5-1, следовательно, первый разряд результате снимается с выхода элемента И 19.3.

После прихода 1-го импульса на входы синхронизации 1 на вход ПЗБ2 поступают 1-е разряды слагаемых 0000, на выходе получают код 0000. РУ6 выдает сигнал разрешения на прохождение кода 0000 на вход ПЗБ3, на выходе ПЗБ3 получают код 000 000, который поступает на входы Y и Z ПЗБ1, в результате на входе ПЗБ1 будет код 0000 000 000, на выходе 000 00000.

После прихода 2-го импульса на вход ПЗБ 2 поступают вторые разряды слагаемых 0000, на выходе получают код 0000. На входы Y и Z ПЗБ1 с входа БЗ 5.1 поступает код 000 000. На входе ПЗБ1 получают код 0000 000 000, на выходе 000 00000. РУ 6 выдает сигнал разрешения записи на ТУ 7, по этому сигналу в ТУ 7 записывается единица.

После прихода 3-го импульса на вход ПЗБ2 поступают 1111, на выходе получают 1111. С входа БЗ 5.1 на входы Y и Z поступает код 000 000. С выхода ТУ 7 единица поступает на 3-й вход элемента ИЛИ 9.1. На входе ПЗБ1 получают код 1111 00 001, на выходе код 010 11000.

После прихода 4-го импульса на вход ПЗБ2 поступает 0101, на выходе получают 0011. На входы Y и Z ПЗБ1 С входа БЗ 5.1 поступает код 010 110. На входе ПЗБ1 получают код 0011 010 110, на выходе 010 11100.

После прихода 5-го импульса на вход ПЗБ2 поступает 0100, на выходе получают 0001.

На выходе БЗ 5.1 получают код 010 1110. Нуль с 4-го выхода БЗ 5.1 поступает на вход 33 5.2.

На входе ПЗБ1 получают код 0001 010 111, на выходе 001 11110.

После прихода 6-го импульса на вход ПЗБ2 поступает 1100, на выходе получают 0011. На выходе Б35.1 получают 001 1111. Нуль с входа 33-5.2 перемещается на выход элемента И 19.3. Единица с 4-го выхода Б35.1 поступает на вход Э35.2. На входе ПЗБ1 получают код 0011 001 111, на выходе 010 11000.

На информационные выходы n+3, n+2, n+1, n, n-1, n-2, n-3 с выхода ПЗБ1 поступает кодовая комбинация 010 1100, на выходах n-4 и n-3 получают 10, следовательно результат сложения 010 110010.

П р и м е р 2. Рассмотрим сложение чисел 11100001, 01010001, 01100001, 01000000 n-4, N-4, Z-n-5-8-5-3, следовательно, первый разряд снимается с выхода Э3 5.4.

После прихода 1-го импульса на вход Х П2Б1 поступает через ПЗБ2 0111. На вход ПЗБ3 поступает 0111, на выходе получают 000 111. На входе ПБЗ1 0111 000 111, на выходе 010 11000.

После прихода 2-го импульса на вход ПЗБ1 поступает 000 010 110, на выходе получают 001 01100.

После прихода 3-го импульса на вход ПЗБ1 поступает 0000 001 011, на выходе 000 11000.

После прихода 4-го импульса на вход ПЗБ1 поступает 0000 000 110, на выходе 000 01100. На вход 4 БЗ 5.1 поступает нуль.

После прихода 5-го импульса на вход ПЗБ1 поступает 0001 000 011, на выходе 000 11000. На выходе 4 БЗ 5.1 получают нуль. На вход 4 БЗ 5.1 поступает нуль.

После прихода 6-го импульса нуль с 4-го выхода БЗ5.1 поступает на выход Э35.2, на выход 4 Б35.1 поступает нуль. На вход ПЗБ1 поступает код 0011 000 110, на выходе получают 001 01111. Единица с выхода 5 ПЗБ1 поступает на вход Э35.2.

После прихода 7-го импульса нуль с выхода Э3 5.2 поступает на выход Э3 5.3, единица с входа Э3 5.2. поступает на его вход, единица с выхода 4 ПЗБ1, поступает на выход 4 БЗ 5.1. На входе ПЗБ1 получают 1111 001 011, на выходе 011 01111.

Единица на выходе 5 ПЗБ1 вместе с единицей на выходе 4 БЗ 5.1 дает на выходе элемента И 19.1 единицу, а на выходе элемента НЕ 20 нуль, в результате чего на вход ПЗБ4 поступает код с выхода ПЗБ1 011 0111, на выходе ПЗБ4 получают код 011 11000, который поступает на вход БЗ 5.1. Нуль с выхода 5 ПЗБ4 поступает на вход ЭЗ 5.2, нуль с выхода элемента НЕ 20 поступает на вход ЭЗ 5.3.

После прихода 8-го импульса нуль с выхода ЭЗ 5.3 поступает на выход ЭЗ 5.4, нуль с входа ЭЗ 5.3 поступает на его выход, нуль с входа ЭЗ 5.2 на его выход, нуль с выхода 4 ПЗБ4 на выход 4 БЗ 5.1. На входе ПЗБ1 получают код 0001 011 110, на выходе 010 11100. На информационных выходах получают код 010 1110 0000, который и является результатом сложения.

Изобретение относится к вычислительной технике и может быть использовано для сопряжения с вычислительными устройствами, функционирующими в кодах Фибоначчи, а также в технике связи для передачи информации кодами Фибоначчи. Цель изобретения увеличение быстродействия за счет возможности одновременного суммирования n разрядных N чисел, представленных в любой форме фибоначчиевой системы счисления. Устройство содержит постоянные запоминающие блоки 1 4, входные регистры 8.1 8.N, регистр 6 управления, триггер 7 управления, блок 5.1 задержки, элементы задержки 5,2 5.Р, элементы ИЛИ 9.1 9.К1, 12.1 12. К2, 13, 18.1, 18.2, элементы И 10.1 10.N, 11.1 11.К2, 16, 17.1 - 17.К2, 19.1 19.3, элементы НЕ 14,20, трехвходовый элемент ИЛИ НЕ 15, входы синхронизации 1, информационные входы 2 и информационные выходы 1 /n+m/. 1 ил.

ПАРАЛЛЕЛЬНЫЙ СУММАТОР КОДОВ ФИБОНАЧЧИ, содержащий группу элементов задержки, первые группы элементов И и элементов ИЛИ, отличающийся тем, что сумматор содержит вторую и третьи группы элементов И и ИЛИ, четыре постоянных запоминающих блока, регистр управления и триггер управления, три элемента НЕ, три элемента ИЛИ, три элемента И, элемент ИЛИ НЕ, группу входных регистров, информационные входы которых являются информационными входами сумматора, а выходы соединены с адресным входом второго постоянного запоминающего блока, выходы которого соединены с первыми входами элементов И первой группы, вторые входы которых соединены с первыми выходами регистра управления, а выходы с адресным входом третьего постоянного запоминающего блока, выходы которого соединены с первыми входами элементов ИЛИ первой группы, выходы которых соединены с адресным входом младших разрядов первого постоянного запоминающего блока, адресный вход старших разрядов которого соединен с выходами второго постоянного запоминающего блока, третий вход первого элемента ИЛИ первой группы элементов ИЛИ соединен с выходом первого элемента И, первый вход которого соединен с третьим выходом регистра управления, а второй вход с выходом триггера управления, вход разрешения записи которого соединен с вторым выходом регистра управления, информационный вход триггера управления соединен с выходом элемента ИЛИ НЕ, входы которого соединены с выходами младших разрядов первого постоянного запоминающего блока, которые совместно с выходами старших разрядов первого постоянного запоминающего блока соединены с первыми входами элементов И второй группы, выходы первого постоянного запоминающего блока также соединены с первыми входами элементов И третьей группы, выходы которых соединены с адресными входами четвертого постоянного запоминающего блока, выходы которого соединены с первыми входами элементов ИЛИ второй группы, вторые входы которых соединены с выходами элементов И второй группы, а выходы с информационными выходами старших разрядов устройства и с входами блока задержки, выходы которого соединены с вторыми входами элементов ИЛИ первой группы, первый выход блока задержки соединен с первыми входами первого элемента ИЛИ и второго элемента И, вторые входы которых соединены с первым выходом первого постоянного запоминающего блока, выход первого элемента ИЛИ соединен с первым входом третьего элемента И, выход которого соединен с первым входом второго элемента ИЛИ, второй вход которого соединен с первым выходом четвертого постоянного запоминающего блока, а выход соединен с информационным выходом сумматора и с входом первого элемента задержки, выход которого соединен с первым выходом четвертого элемента И, выход которого является информационным выходом сумматора и входом второго элемента задержки, а второй вход соединен с вторым входом третьего элемента И и с выходом первого элемента НЕ, вход которого соединен с выходом второго элемента И и с вторыми входами элементов И третьей группы, выход первого элемента НЕ также соединен с вторыми входами элементов И второй группы, третий вход первого элемента И которой соединен с выходом второго элемента НЕ, вход которого соединен с выходом элемента ИЛИ, входы которого соединены с выходами регистра управления, вход синхронизации которого соединен с входами синхронизации входных регистров группы, с входом синхронизации задержки и с входами синхронизации элементов задержки группы, выходы которых, начиная с второго элемента задержки, соединены с входом последующего элемента задержки и являются информационными выходами сумматора.