Устройство для приведения 1-кода Фибоначчи к минимальной форме Советский патент 1991 года по МПК H03M7/30 

Г0 f88 lf87 86 f83 f84 r83 82 81

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

S-U а- Л а i--i l 1 7

где аи - значение 1-го разряда кода, полученного путем сдвига исходного кода ai на разряд вправо. Это уравнение задает алгоритм последовательного контроля по признаку минимальной формы.

В каждом блоке 1-4 свертки групп на элементе И 11 проверяется выполнение условия свертки по логическому уравнению. Для этого в каждом такте в триггеры 9 и 10 соответственно записываются исходный код и сдвинутое на разряд вправо значение этого же кода. После окончания переходных процессов на выходах элементов И 11 имеем результаты проверок условия свертки. Поскольку свертка может выполняться только для двух разрядов, то для этого одновременно в блоках 1-4 свертки на элементе И-НЕ 12 вырабатывается сигнал, запрещающий свертку в предыдущих блоках свертки. Например, при свертке кода типа 1111... согласно вышеописанному, свертка будет выполняться для первой и третьей групп (каждая группа содержит два разряда) начиная со старших разрядов, Так как в двух старших разрядах выполняется условие

свертки, то на выходе элемента И-НЕ 12 появится нулевой сигнал, который поступает на первый вход предыдущего блока свертки - на первый вход элемента И 13 и

запрещает выполнение свертки, В старших группах указанного кода выполняется свертка, при этом сигнал переноса с выхода сумматора 14 (в нашем случае с блока 1.8 свертки) поступает на второй и на пятый

0 входы соответственно блоков 2.9 и 2.8 свертки следующей группы. Допустим, что необходимо приведение к минимальной форме кода 1010101 -изображения числа 21 в 1-ко- де Фибоначчи, представляющего собой на5 ихудший случай в смысле времени выполнения свертки.

Этот код в младшем разряде содержит единицу и поэтому не соответствует признаку нормальной формы. По первому тактово0 му сигналу, поступающему на четвертый вход блоков свертки, исходный код заносится в триггеры 9 блоков 1.1-1.8 свертки. В триггеры 10 блоков свертки одновременно заносятся сдвинутые вправо значения ис5 ходного кода. На элементах И 11 проверяется условие свертки. Поскольку исходный код не содержит два смежных единичных разряда, то на выходах элементов И 11 всех блоков свертки присутствует нулевой сигнал, а

0 на входах элементов И-НЕ 1Z- единичный, Следовательно, свертка разрешена во всех блоках свертки. Поскольку второй разряд кода содержит нуль, то содержимое триггера 10 блока 1.1 также равно нулю и единич5 ный сигнал с его инверсного выхода (четвертого выхода блока 1.1 свертки) поступает на первый вход элемента И 5, на второй вход которого единичный сигнал поступает с выхода триггера 9 блока 1.1 свер0 тки. На первом входе одноразрядного сумматора 14 присутствует нулевой сигнал, так как на выходе элемента И 11 нулевой сигнал, а на втором входе - единичный сигнал, равный значению младшего разряда

5 исходного кода с выхода триггера 9. На одноразрядном сумматоре 14 блока 1.1 осуществляется суммирование младшего разряда с единицей, поступающей на вход переноса с выхода элемента И 5. После окончания

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

Второй тактовый сигнал этот код (1010110) заносит в триггеры 9 блоков 2 свертки и аналогичным образом в триггеры 10 блоков 2 свертки. Во втором такте происходят аналогичные первому такту процессы с той лишь разницей, что в блоке 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.1 свертки. Следова- тельно, на выходе элемента И 13 блока 1,1 свертки также присутствует нулевой сигнал. Таким образом, значение младшего разряда с выхода триггера 10 без изменения переносится на третий выход блока 1.1

свертки. После выполнения свертки указанный код примет вид ...1001. В следующем такте код .,,1001 переносится в блоки 2.4, 2.3, 2.2 и 2.1 свертки, при этом в блоке 2.1 свертки будет осуществляться коррекция младшего разряда кода при помощи элемента И 6, Далее устройство работает вышеописанным способом до получения окончательного результата свертки.

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

Формула изобретения 1. Устройство для приведения 1-кода Фибоначчи к минимальной форме, содержащее первую группу блоков свертки, причем первый выход (i+1)-ro (l 1-n-1, п - разрядность кода) блока свертки первой группы соединен с первым входом i-ro блока свертки первой группы, группа информационных входов устройства соединена с вторыми входами соответствующих блоков свертки первой группы, второй выход 1-го блока свертки первой группы соединен с третьим входом (i+1)-ro блока свертки первой группы, первый тактовый вход группы устройства соединен с четвертыми входами блоков свертки первой группы, отличающее- с я тем, что, с целью повышения быстродействия, оно содержит с второй по n/2-ю группы блоков свертки, первый и второй элементы И, причем пятый вход 1-го блока свертки первой группы соединен с вторым входом (i+1)-ro блока свертки первой rpyrlIf пы, первый выход 0+1 )-ro() блока свертки k-й (k 2-n/2) группы соединен с первым входом j-ro блока свертки k-й группы, второй выход j-ro блока свертки k-й группы соединен с третьим входом (j+ 1)-го блока свертки k-й группы, третий выход j-ro блока свертки (k-1)-H группы соединен с вторым входом j-ro блока свертки k-й группы.третьи выходы блоков свертки n/2-й группы являются группой выходов устройства, с второго по n/2-й тактовые входы группы которого соединены с четвертыми входами блоков свертки соответствующих групп, второй выход n-го блока свертки первой группы соединен с вторым входом (п+ 1)-го блока свертки второй группы, третий выход (п+1)- го блока свертки м-й(м 2-п/2-1) группы соединен с вторым входом (п+ 1)-го блока свертки (м+1)-й группы, пятый вход j-ro блока свертки k-й группы соединен с вторым

входом (j+1)-ro блока k-й группы, четвертый и пятый выходы, третий вход первого блока свертки первой группы соединены соответственно с первым и вторым входами, с выходом первого элемента И, четвертый и пятый выходы, третий вход первого блока свертки второй группы соедине- ны соответственно с первым и вторым Входами, с выходом второго элемента И, вход нулевого потенциала устройства сое динен с пятыми входами n-го блока свертки первой группы и с пятым входом (п+1)-го блока свертки k-й группы.

2. Устройство по п. 1,отличающее- с я тем, что блок свертки содержит первый 1 второй триггеры, первый и второй элементы И, элемент Й-НЕ и одноразрядный сум- {матор, причем первый вход блока свертки Ьоединен с первым входом второго элемен- Jra И, выход которого соединен с входом Первого слагаемого одноразрядного сумматора, выход суммы, выход переноса и вход переноса которого являются соответственно третьим выходом, вторым выходом и третьим входом блока свертки, второй и пятый входы которого соединены с информационными входами соответственно первого и второго триггеров, входы разрешения записи которых соединены с четвертым входом блока свертки, прямой выход второго - 10 триггера соединен с первым входом первого элемента И, выход которого соединен с вторым входом второго элемента И, выход первого триггера соединен с вторым входом первого элемента И, с первым входом эле- 15 мента И-НЕ, с входом второго слагаемого одноразрядного сумматора и является пятым выходом блока свертки, четвертый выход которого соединен с инверсным выходом второго триггера, прямой выход кото- 20 рого соединен с вторым входом элемента И-НЕ, выход которого является первым выходом блока свертки.

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

Фиг. 2