Устройство для приведения 1-кода фибоначчи к минимальной форме

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИРЕСПУБЛИК 65515 51)ю Н 03 М КОМИТЕТИ ОТКРЫТИЯМ ГОСУДАРСТВЕННЫПО ИЗОБРЕТЕНИЯМПРИ ГКНТ СССР ИЕ ИЗОБРЕТЕ ОП ВТОРСКОМУ СВИДЕТЕЛЬСТВУ(71) Научно-производственное объединение космических исследований(56) Авторское свидетельство СССР М 1418910, кл. Н 03 М 7/30, 1987.Авторское свидетельство СССР М 842782, кл. Н 03 М 7/30, 1979,(54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ 1- КОДА ФИБОНАЧЧИ К МИНИМАЛЬНОЙ ФОРМЕ(57) Изобретение относится к вычислительной технике и позволяет повысить быстродействие устройства, Последнее содержит уппу блоков 1 - 4 свертки, элементы И 5 и 6 и имеет группы информационных входов 7 и выходов 8, Каждый блок свертки содержит два триггера, два элемента И, элемент И - НЕ и одноразрядный сумматор. В каждом блоке свертки на соответствующем элементе И проверяется выполнение условия свертки. Поскольку свертка может выполняться только для двух разрядов, одновременно в бло-. ках 1 - 4 свертки на элементах И - НЕ вырабатываются сигналы, запрещающие свертку в предыдущих блоках свертки. При помощи элементов И осуществляется коррекЦия младшего разряда исходного кода. Быстродействие устройства достигается, кроме того, за счет использования конвейерного способа преобразования, 1 з,п. ф-лы, 2 ил.Изобретение относится к вычислительной технике и предназначено для приведения 1-кода Фибоначчи к минимальной форме.Целью изобретения является повышение быстродействия.На фиг. 1 приведена схема устройства для приведения 1-кода Фибоначчи к минимальной форме (для 8-ми разрядного кода); на фиг, 2 - схема блока свертки,Устройство содержит первую группу ,блоков 1.1-1,8 свертки, вторую группу блоков 2.1 - 2.9 свертки, третью группу блоков 3.1 свертки, четвертую группу блоков 4,1- 4.9 свертки, первый 5 и второй 6 элементы И, группу информационных входов 7,1 - 7.8 устройства, группу выходов 8,1-8.9 устройства,На фиг, 1 группа тактовых входов устройства не показана.Каждый блок 1 (2 - 4) свертки (фиг, 2) со, держит первый 9 и второй 10 триггеры, первый элемент И 11, элемент И-НЕ 12, второй элемент И 13 и одноразрядный сумматор 14,Устройство работает следующим образом,Необходимость выполнения операции свертки над кодовым изображением определяется проверкой соответствия признаку минимальной формы исходного кода, Соответствие признаку минимальной формы 1- кода Фибоначчи описывается логическимуравнением5=д дд,ь-"1где аь 1, - значение 1-го разряда кода, полученного путем сдвига исходного кода а на разряд вправо, Это уравнение задает алгоритм последовательного контроля по признаку минимальной формы.В каждом блоке 1 - 4 свертки групп на элементе И 11 проверяется 1 выполнение условия свертки по логическому уравнению. Для этою в каждом такте в триггеры 9 и 10 соответственно записываются исходный код и сдвинутое на разряд вправо значение этого же кода, После окончания переходных процессов на выходах элементов И 11 имеем результаты проверок условия свертки.Поскольку свертка может выполняться только для двух разрядов, то для этого одновременно в блоках 1 - 4.свертки на элементе И - НЕ 12 вырабатывается сигнал, запрещающий свертку в предыдущих блоках свертки. Например, при свертке кода типа 1111, согласно вышеописанному, свертка будет выполняться для первой и третьей групп (каждая группа содержит два разряда)начиная со старших разрядов. Так как в двух старших разрядах выполняется условие40 тки. На первом входе одноразрядногосумматора 14 присутствует нулевой сигнал, так как на выходе элемента И 11 нулевой сигнал, а на втором входе - единичный сигнал, равный значению младшего разрядаисходного кода с выхода триггера 9. На одноразрядном сумматоре 14 блока 1.1 осуществляется суммирование младшего разряда с единицей, поступающей на вход переноса с выхода элемента И 5, После окончанияпереходных процессов на выходах блоков 1 свертки имеем первый промежуточный результат 1010110, который также является изображением числа 21 в 1-коде Фибоначчи. Таким образом, в первом такте осущест 55 вляется толькокоррекция младшего разрядаисходнбго кода.Второй тактовый сигнал этот код(1010110)заносит в триггеры 9 блоков 2 свертки и аналогичным образом в триггеры 10 блоков 2 свертки. Во втором такте происходят ана 5 10 15 20 25 30 35 свертки, то на выходе элемента И - НЕ 12появится нулевой сигнал, который поступа- ет на первый вход предыдущего блокасверткина первый вход элемента И 13 изапрещает выполнение, свертки, В старших группах указанного кода выполняется свертка, при этом сигнал переноса с выхода сумматора 14 (в нашем случае с блока 1.8 свертки) поступает на второй и на пятый входы соответственно блоков 2,9 и 2,8 свертки следующей группы, Допустим, что необходимо приведение к минимальной форме кода 1010101 - изображения числа 21 в 1-коде Фибоначчи, представляющего собой наихудший случай в смысле времени выполнения свертки,Этот код в младшем разряде содержит единицу и поэтому не соответствует и ризна-ку нормальной формы. По первому тактовому сигналу, поступающему на четвертый вход блоков свертки, исходный код заносится в триггеры 9 блоков 1,1 - 1.8 свертки. В триггеры 10 блоков свертки одновременно заносятся сдвинутые вправо значения исходного кода. На элементах И 11 проверяется условие свертки. Поскольку исходный код не содержитдва смежных единичных разряда, то на выходах элементов И 11 всех блоков свертки присутствует нулевой сигнал, а на входах элементов И - НЕ 12 - единичный, Следовательно, свертка разрешена во всех блоках свертки, Поскольку второй разряд кода содержит нуль, то содержимое триггера 10 блока 1,1 также равно нулю и единичный сигнал с его инверсного выхода (четвертого выхода блока 1.1 свертки) поступает на первый вход элемента И 5, на второй вход которого единичный сигнал поступает с выхода триггера 9 блока 1.1 свер 1665515В четвертом такте происходят процессы 35 40 45 50 55 логичные первому такту процессы с той лищь разницей, что в блоке 2,2 будет выполняться условие свертки, а в остальных нет. Поскольку в блоке 2,3 также не выполняется условие свертки, то согласно вышеописанному единичный сигнал с выхода элемента И - НЕ 12 блока 2,3 поступает на первый вход блока 2,2 - на первый вход элемента И 13, Результат проверки условия свертки на элементе И 11 блока 2,2 свертки поступает . на первый вход одноразрядного сумматора14, на второй вход которого с выхода триггера 9 поступает значение второго разряда кода промежуточного результата. Таким об; разом, свертка в группе из двух разрядов осуществляется путем суммирования младшего из них с результатом свертки для дан, ной группы разрядов, После окончания переходныХ процессов в одноразрядных сумматорах 14 на выходах блоков 2 свертки появляется код второго промежуточного результата 1011000, который также является изображением числа 21 в 1-коде Фибоначчи.Третий тактовый сигнал этот код описанным выше образом заносит в триггеры 9 и 10 блоков 3 свертки, Как видно, свертка будет выполняться в блоке 3.4 свертки, соответствующего четвертому разряду, Аналогично предыдущим тактам после окончания переходных процессов на выходах блоков 3 свертки имеем третий промежуточный результат 1100000, являющийся также изображением числа 21 в 1-коде Фибоначчи. аналогичные первым трем тактам, и после окончания процесса суммирования в одноразрядных сумматорах 14 блоков 4 свертки на выходах последних имеем окончательный результат кода числа 21, представленный в минимальной форме 1-кода Фибойаччи, т,е, 10000000.При приведении кода типа ,111 к минимальной форме в блоке 1,1 свертки коррекция младшего разряда не осуществляется, поскольку на четвертом выходе блока 1,1 свертки имеем нулевой сигнал с инверсного выхода триггера 10, Следовательно, на выходе элемента И 5 присутствует нулевой сигнал, поступающий на вход переноса одноразрядного сумматора 14, Поскольку в двух старших разрядах указанного кода будет выполняться свертка, то нулевой сигнал с первого выхода блока 1,2 свертки запрещает свертку в блоке 1,1 свертки. Следовательно, на выходе элемента И 13 блока 1,1 свертки также присутствует нулевой сигнал, Таким образом, значение младшего разряда с выхода триггера 10 без изменения переносится на третий выход блока 1,1 10 15 20 25 30 свертки, После выполнения свертки указанный код примет вид 1001, В следующем такте код .1001 переносится в блоки 2,4, 2.3, 2,2 и 2,1 свертки, при этом в блоке 2,1 свертки будет осуществляться коррекция младшего разряда кода при помощи элемента И 6, Далее устройство работает вышеописанным способомдо получения окончательного результата свертки.Таким образом, в устройстве за четыре (в общем случае за и/2) такта возможно одновременное приведение к минимальной форме и/2 кодов, причем максимальная частота поступления преобразуемых данных ограничена в конвейерном режиме временем переходных процессов трех (в общем случае р+2) блоков свертки и от разрядности кода не зависит.Формула изобретения1, Устройство для приведения 1-кода Фибоначчи к минимальной форме, содержащее первую группу блоков свертки, причем первый выход (Н 1)-го (1=1 - и, и - разрядность кода) блока свертки первой группы соединен с первым входом 1-го блока сверт-, ки первой группы, группа информационных входов устройства соединена с вторыми входами соответствующих блоков свертки первой группы, второй выход 1-го блока свертки первой группы соединен с третьим входом (+1)-го блока свертки первой группы, первый тактовый вход группы устройства соединен с четвертыми входами блоков свертки первой группы, о т л и ч а ю щ е е - с я тем, что, с целью повышения быстродействия, оно содержит с второй по и/2-ю группы блоков свертки, первый и второй элементы И, причем пятый вход 1-го блока свертки первой группы соединен с вторыивходом (1+1)-го блока свертки первой гругРкпы, первый выход 0+1)-го О=1 - и) блока свертки 1-й (1=2 - и/2) группы соединен с первым входом )-го блока свертки М-й группы, второй выход )-го блока свертки К-й группы соединен с третьим входом О+ 1)-го блока свертки М-й группы, третий выход)-го блока свертки (1 - 1)-й группы соединен с вторым входом)-го блока свертки К-й группы, третьи выходы блоков свертки и/2-й группы являются группой выходов устройства, с второго по и/2-й тактовые входы группы которого соединены с четвертыми входами блоков свертки соответствующих групп, второй выход и-го блока свертки первой группы соединен с вторым входом (и+ 1)-го блока свертки второй группы, третий выход (и+1)- го блока свертки м-й(м=2 - и/2 - 1) группы соединен с вторым входом (и+ 1)-го блока свертки (м+1)-й группы, пятый вход)-го блока свертки 1-й группы соединен с вторым1665515 Составитель А,Клюеведактор Г.Гербер Техред М,Моргентал Корректор Э.Лончаков аказ 2399 Тираж 459 Подписное ВНИИПИ Государственного комитета по изобретениям и открцтиям при ГКНТ СССР 113035, Москва, Ж, Раушская наб 4/5 изводственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 входом О+1)-го блока свертки к-й группы, четвертый и пятый выходы, третий вход первого блока свертки первой группы соединены соответственно с первым и вторым входами, с выходом первого элемента И, четвертый и пятый выходы, третий вход перВого блока свертки второй группы соединены соответственно с первым и вторым Входами, с выходом второго элемента И, Вход нулевого потенциала устройства соединен с пятыми входами и-го блока свертки первой группы и с пятым входом (и+1)-го блока свертки 1-й группы. 2. Устройство по и. 1, о т л и ч а ю щ е ес я тем, что блок свертки содержит первыйвторой триггеры, первый и второй элементы И, элемент И-НЕ и одноразрядный сум)чатор, причем первый вход блока свертки соединен с первым входом второго элемента И, выход которого соединен с входом Первого слагаемого одноразрядного сумматора, выход суммы, выход переноса и вход переноса которого являются соответственно третьим выходом, вторым выходом и третьим входом блока свертки, второй и пя тый входы которого соединены с информационными входами соответственно первого и второго триггеров, входы разрешения записи которых соединены с четвертым входом блока свертки, прямой выход второго 10 триггера соединен с первым входом первого элемента И, выход которого соединен с вторым входом второго элемента И, выход первого триггера соединен с вторым входом первого элемента И, с первым входом эле мента И-НЕ, с входом второго слагаемогоодноразрядного сумматора и является пятым выходом блока свертки, четвертый выход которого соединен с инверсным выходом второго триггера, прямой выход кото рого соединен с вторым входом элементаИ-НЕ, выход которого является первым выходом блока свертки,