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

 

Изобретение относится к вычислительной технике и позволяет повысить быстродействие устройства. Последнее содержит группу блоков 1 - 4 свертки, элементы И 5, 6 и имеет группы информационных входов 7 и выходов 8. Каждый блок свертки содержит два триггера, два элемента И, элемент И - НЕ и одноразрядный сумматор. В каждом блоке свертки на соответствующем элементе И проверяется выполнение условия свертки. Поскольку свертка может выполняться только для двух разрядов, одновременно в блоках 1 - 4 свертки на элементах И - НЕ вырабатываются сигналы, запрещающие свертку в предыдущих блоках свертки. При помощи элементов И 5 и 6 осуществляется коррекция младшего разряда исходного кода. Быстродействие устройства достигается, кроме того, за счет использования конвейерного способа преобразования. 1 з.п. ф-лы, 2 ил.

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

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

РЕСПУБЛИК (51)5 Н 03 M 7/30

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4724744/24 (22) 19.07.89 (46) 23,07;91. Бюл, М 27 (71) Научно-производственное объединение космических исследований (72) К, Х. Исмаилов, Я. А, Мамедов, Ф. А.

Мамедов и И. 3. Животовский (53) 681,3(088,8) (56) Авторское свидетельство СССР

М 1418910, кл. Н 03 M 7/30, 1987.

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

N 842782, кл. Н 03 M 7/30, 1979. (54) УСТРОЙСТВО ДЛЯ ПРИВЕДЕНИЯ 1КОДА ФИБОНАЧЧИ К МИНИМАЛЬНОЙ

ФОРМЕ (57) Изобретение относится к вычислительной технике и позволяет повысить быстродействие устройства, Последнее содержит,, Ж,, 1665515 А1 группу блоков 1 — 4 свертки, элементы И 5 и

6 и имеет группы информационных входов 7 и выходов 8. Каждый блок свертки содержит два триггера, два элемента И, элемент И вЂ” НЕ и одноразрядный сумматор. В каждом блоке свертки на соответствующем элементе И проверяется выполнение условия свертки.

Поскольку свертка может выполняться только для двух разрядов, одновременно в бло-. ках 1 — 4 свертки на элементах И вЂ” НЕ вырабатываются сигналы, запрещающие свертку в предыдущих блоках свертки.

При помощи элементов И осуществляется коррекЦия младшего разряда исходного кода. Быстродействие устройства достигается, кроме того,- за счет использования конвейерного способа преобразования, 1 з,п. ф-лы, 2 ил.

1665515

Изобретение относится к вычислительной технике и предназначено для приведения 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= U n„. „h haa„, i-" 1 где а -p. — значение 1-го разряда кода, полученного путем сдвига исходного кода ai на разряд вправо, Это уравнение задает алгоритм последовательного контроля по признаку минимальной формы.

В каждом блоке 1 — 4 свертки групп на элементе И 11 проверяется выполнение условия свертки по логическому уравнению.

Для этого в каждом такте в триггеры 9 и 10 соответственно записываются исходный код и сдвинутое на разряд вправо значение этого же кода, После окончания переходных процессов на выходах элементов И 11 имеем результаты проверок условия свертки.

Поскольку свертка может выполняться только для двух разрядов, то для этого одновременно в блоках 1 — 4-свертки на элементе

И вЂ” HF 12 вырабатывается сигнал, запрещающий свертку в предыдущих блоках свертки. Например, при свертке кода типа 1111... согласно вышеописанному, свертка будет выполняться для первой и третьей групп (каждая группа содержит два разряда)., начиная со старших разрядов. Так как в двух старших разрядах выполняется условие

40 свертки, то на выходе элемента И вЂ” НЕ 12 появится нулевой сигнал, который поступает на первый вход предыдущего блока свертки -- на первый вход элемента И 13 v. запрещает выполнение: свертки, В старших группах указанного кода выполняется свертка, при этом сигнал переноса с выхода сумматора 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 свертки. На первом входе одноразрядного сумматора 14 присутствует нулевой сигнал, так как на выходе элемента И 11 нулевой сигнал, а на втором входе — единичный сигнал, равный значению младшего разряда исходного кода с выхода триггера 9. На одноразрядном сумматоре 14 блока 1.1 осуществляется суммирование младшего разряда с единицей, поступающей на вход переноса с выхода элемента И 5, После окончания

50 переходных процессов на выходах блоков 1 свертки имеем первый промежуточный результат 1010110, который также является изображением числа 21 в 1-коде Фибоначчи. Таким образом, в первом такте осущест55 вляется толькокоррекция младшего разряда исходного кода.

Второй тактовый сигнал этот код (1010110) заносит в триггеры 9 блоков 2 свертки и аналогичным образом в триггеры 10 блоков

2 свертки. Во втором такте происходят ана1665515

В четвертом такте происходят процессы35

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

30 свертки. После выполнения свертки указанный код примет вид ...1001. B следующем такте код .„1001 переносится в блоки 2,4, 2.3. 2,2 и 2,1 свертки, при этом в блоке 2,1 свертки будет осуществляться коррекция младшего разряда кода при помощи элемента И 6. Далее устройство работает вышеописанным способом до получения окончательного результата свертки.

Таким образом, в устройстве за четыре (в общем случае за n/2) такта возможно одновременное приведение к минимальной форме и/2 кодов, причем максимальная частота поступления преобразуемых данных ограничена в конвейерном режиме временем переходных процессов трех (в общем случае р+2) блоков свертки и от разрядности кода не зависит.

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

1. Устройство для приведения 1-кода

Фибоначчи к минимальной форме, содержащее первую группу блоков свертки, причем первый выход (Н1)-го (i=1 — n — 1, и — разрядность кода) блока свертки первой группы соединен с первым входом i-го блока сверт- . ки первой группы, группа информационных. входов устройства соединена с вторыми входами соответствующих блоков свертки первой группы, второй выход i-го блока свертки первой группы соединен с третьим входом (i+1)-го блока свертки первой группы, первый тактовый вход группы устройст- . ва соединен с четвертыми входами блоков свертки первой группы, о т л и ч а ю щ е е— с я тем, что, с целью повышения быстродействия, оно содержит с второй по и/2-ю группы блоков свертки, первый и второй элементы И, причем пятый вход I-го блока свертки первой группы соединен с вторыи входом(1+1)-го блока свертки первой rpyrl кпы, первый выход()+1)-ro О=1 — и) блока свертки k-й (k=2 — п/2) группы соединен с первым входом j-го блока свертки k-й группы, второй выход j-ro блока свертки k-й группы соединен с третьим входом (j+ 1)-го блока свертки k-й группы, третий выход j-fo блока свертки (k — 1)-й группы соединен с вторым входом j-ro блока свертки k-й группы, третьи выходы блоков свертки п/2-й группы являются группой выходов устройства, с второго по n/2-й тактовые входы группы которого соединены с четвертыми входами блоков свертки соответствующих групп, второй выход п-го блока свертки первой группы соединен с вторым входом (и+ 1)-ro блока свертки второй группы, третий выход (и+1)го блока свертки м-й(м=2 — n/2 — 1) группы соединен с вторым входом (и+ 1)-ro блока свертки (м+1)-й группы, пятый вход j-го блока свертки k-й группы соединен с вторым

1665515

2. Устройство по и. 1, о т л и ч а ю щ е ес я тем, что блок свертки содержит первый второй триггеры, первый и второй элемен ты И, элемент И-НЕ и одноразрядный сум)чатор, причем первый вход блока свертки соединен с первым входом второго элеменга И, выход которого соединен с входом

Первого слагаемого одноразрядного суммаi

Составитель А,Клюев

Техред M,Ìîðãåíòàë Корректор Э.Лончакова

Редактор Г.Гербер

Заказ 2399 Тираж 459 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул,Гагарина, 101 входом ()+1)-го блока свертки k-й группы, четвертый и пятый выходы, третий вход первого блока свертки первой группы соединены соответственно с первым и вторым входами, с выходом первого элемента И, четвертый и пятый выходы, третий вход пер ого блока свертки второй группы соединены соответственно с первым и вторым

Входами, с выходом второго элемента И, Вход нулевого потенциала устройства соединен с пятыми входами и-ro блока свертки

inepaoA группы и с пятым входом (и+1)-ro блока свертки k-й группы. тора, выход суммы, выход переноса и вход переноса которого являются соответственно третьим выходом, вторым выходом и третьим входом блока свертки, второй и пя5 тый входы которого соединены с информационными входами соответственно первого и второго триггеров, входы разрешения записи которых соединены с четвертым входом блока свертки, прямой выход второго

10 триггера соединен с первым входом первого элемента И, выход которого соединен с вторым входом второго элемента И, выход первого триггера соединен с вторым входом первого элемента И, с первым входом эле15 мента И-НЕ, с входом второго слагаемого одноразрядного сумматора и является пятым выходом блока свертки, четвертый выход которого соединен с инверсным выходом второго триггера, прямой выход кото20 рого соединен с вторым входом элемента

И-НЕ, выход которого является первым выходом блока свертки,