ВЫЧИСЛИТЕЛЬНЫЙ ЭЛЕМЕНТ ДЛЯ ОСУЩЕСТВЛЕНИЯ БЫСТРОЙ СВЕРТКИ Российский патент 1995 года по МПК G06F17/17 G06F17/14 

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

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

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

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

Наиболее близким техническим решением к предлагаемому изобретению является вычислительный элемент для осуществления быстрой свертки (3), содержащий сумматор по модулю чисел Ферма, первое и второе устройство вычитания по модулю чисел Ферма, первый и второй входные буферные регистры, первый, второй и третий регистры повторного тактирования, выходной регистр, регистр хранения экспоненты вращения, умножители на 2¹² и на 2⁴, первый и второй мультиплексоры 2:1 и мультиплексор 16:1, причем входом устройства является первый вход второго буферного регистра, выход которого подключен к первым входам сумматора по модулю чисел Ферма, первого устройства вычитания по модулю чисел Ферма и первого входного буферного регистра, выход которого подключен ко вторым входам сумматора по модулю чисел Ферма и первого устройства вычитания по модулю чисел Ферма, выходы которых соответственно через первый и второй регистры повторного тактирования подключены к первым входам соответственно первого и второго мультиплексоров 2:1, выход второго регистра повторного тактирования через умножители 2¹² и 2⁴ подключены к входам второго устройства вычитания по модулю чисел Ферма, выход которого соединен со вторым входом второго мультиплексора 2:1, выход которого через третий регистр повторного тактирования, мультиплексор 16:1 подключен ко второму входу первого мультиплексора 2:1, выход которого подключен к первому входу выходного регистра, к третьему входу соответственно втоpого мультиплексора 2: 1 и второму входу мультиплексора 16:1 подключены соответственно первый и второй выходы регистра хранения экспоненты вращения, выход выходного регистра является выходом устройства, на вторые входы входных буферных регистров, регистров повторного тактирования, выходного регистра и третий вход первого мультиплексора 2:1 подаются тактовые импульсы.

Устройство работает следующим образом.

Теоретико-числовое преобразование Ферма (ТЧПФ) последовательности { X(k)} определяется (3, с.187) как
X_n= x(k)α^-<n·k>mod F_t где F_t = 2^2t+1, t-oе-число Ферма;
N - степень числа 2;
α- такое число, что N является наименьшим положительным целым числом, для которого справедливо α^N≡ 1 mod Ft;
<n˙k> - произведение n˙k по модулю N.

Вычислительный элемент реализует базовую операцию быстрого алгоритма ТЧПФ по основанию два при прореживании по частоте и формирует на выходе величины
A+b и (A+B) применительно в 64-точечному ТЧПФ в конечном поле чисел по модулю 2¹⁶+1.

Особенностью реализации быстрого алгоритма ТЧПФ с помощью такого вычислительного элемента является предварительное кодирование данных, позволяющее упростить выполнение операций по модулю чисел Ферма. Схема кодирования данных и описание ее работы приведены в (3, с.188...191).

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

Цикл работы устройства состоит из 6 интервалов t₀, t₁,...,t₅. В течение временных интервалов t₀ и t₁ происходит запись кодов чисел А и В соответственно в первый и второй входные буферные регистры.

В течение временных интервалов t₂, t₃, t₄ осуществляется выполнение базовой операции "бабочка".

Выполнение операции сложения в процессе выполнения базовой операции ТЧПФ двух не равных нулю 16-разрядных чисел при принятой схеме кодирования данных производится за два шага. Возможные структурные схемы сумматора по модулю чисел Ферма приведены в (3, с.194, 195). Вычитание чисел А-В может быть реализовано получением дополнением числа В и его последующим сложением с А.

Результат суммирования по модулю чисел Ферма А+В запоминается в первом регистре повторного тактирования и через первый мультиплексор 2:1 записывается в выходной регистр.

С выхода первого устройства вычитания по модулю чисел Ферма величина разности А-В записывается во второй регистр повторного тактирования. Умножение разности А-В на степень осуществляется через операцию вычитания. Как показано в (4, с.205)
≡ 2^v/4·(2^v/2-1)mod (2^v+1) где v= 2^t=16 для рассматриваемого устройства. Отсюда легко видеть, что
≡ (2- 2^v/4)mod(2^v+ 1) = (2¹²- 2⁴) mod (2¹⁶+1) Таким образом, нужно сформировать величины (А-В) 2¹² и (А-В) 2⁴, а затем получить их разность по модулю чисел Ферма. Умножение на 2¹² и 2⁴реализуется простой коммутацией проводов (эквивалентно сдвигу величины А-В в сторону старших разрядов на соответствующее число разрядов).

Поскольку при четном k умножение на не требуется, второй мультиплексор 2:1 селектирует на выход (в третий регистр повторного тактирования) либо число А-В, либо (А-В).

Управление осуществляется подачей на третий вход второго мультиплексора 2:1 наименьшего значащего разряда числа k.

На втором этапе осуществляется умножение на степень 2, а именно на степень с показателем [k/2] ( [˙] - означает наибольшую целую часть). Это умножение реализуется с помощью мультиплексора 16:1, управляемого четырьмя старшими разрядами двоичного представления степени 2.

Выдача информации с выходного регистра вычислительного элемента для осуществления быстрой свертки производится в интервалы времени t₄ и t₅.

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

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

Поставленная цель достигается тем, что в вычислительный элемент для осуществления быстрой свертки, содержащей первый и второй входные буферные регистры, первый, второй и третий регистры повторного тактирования, первый выходной регистр, регистр хранения экспоненты вращения, первые умножители 2^3v/4 и 2^v/4, где v = 2^t, первый и второй мультиплексоры 2:1 и первый мультиплексор N: 1, (N-разрядность данных), причем первым входом устройства является первый вход второго входного буферного регистра, прямой выход которого соединен с первым входом первого входного буферного регистра, выход первого регистра повторного тактирования через первый мультиплексор 2: 1 подключен к первому входу первого выходного регистра, выход которого является первым выходом устройства, выход второго регистра повторного тактирования через последовательно соединенные второй мультиплексор 2:1, третий регистр повторного тактирования, первый мультиплексор N:1 подключен ко второму входу первого мультиплексора 2:1, входы первых умножителей 2^3v/4 и 2^v/4соединены с выходом второго регистра повторного тактирования, к третьему входу второго мультиплексора 2:1 и второму входу первого мультиплексора N: 1 подключены соответственно первый и второй выходы регистра хранения экспоненты вращения, введены третий и четвертый выходные буферные регистры, четвертый, пятый и шестой регистры повторного тактирования, второй выходной регистр, третий и четвертый мультиплексоры 2:1, второй мультиплексор N:1, вторые умножители 2^3v/4 и 2^v/4, первый, второй и третий блоки суммирования по модулю чисел Ферма, счетчик и элемент задержки, причем прямой выход второго входного буферного регистра соединен с первым входом первого блока суммирования по модулю чисел Ферма, первый выход которого через последовательно соединенные четвертый регистр повторного тактирования и третий мультиплексор 2: 1 подключен к второму выходному регистру, выход которого является вторым выходом устройства, ко вторым входам первого и второго блоков суммирования по модулю чисел Ферма подключен соответственно прямой и инверсный выходы третьего входного буферного регистра, выход первого входного буферного регистра соединен с третьими входами первого и второго блоков суммирования по модулю чисел Ферма, четвертые входы которых подключены к выходу четвертого входного буферного регистра, вход которого соединен с прямым выходом третьего входного буферного регистра, инверсный выход второго входного буферного регистра подключен к первому входу второго блока суммирования по модулю чисел Ферма, первый выход которого через последовательно соединенные пятый регистр повторного тактирования, четвертый мультиплексор 2: 1, шестой регистр повторного тактирования и второй мультиплексор N: 1 соединен со вторым входом третьего мультиплексора 2:1, выходы первого умножителя 2^3v/4 и первого умножителя 2^v/4 подключены соответственно к первому и второму входам третьего блока суммирования по модулю чисел Ферма, первый и второй выходы которого соединены со вторыми входами соответственно второго и четвертого мультиплексоров 2:1, к третьему и четвертому входам третьего блока суммирования по модулю чисел Ферма подключены инверсные выходы соответственно второго умножителя 2^3v/4 и второго умножителя 2^v/4, входы которых соединены с выходом пятого регистра повторного тактирования, первый и второй выходы регистра хранения экспоненты вращения подключены соответственно к третьему входу четвертого мультиплексора 2:1 и ко второму входу второго мультиплексора N:1, вторые выходы первого и второго блоков суммирования по модулю чисел Ферма соединены с первыми входами соответственно первого и второго регистров повторного тактирования, вторые входы второго и третьего входных буферных регистров, первого и второго выходных регистров и вход счетчика соединены между собой и являются тактовым входом устройства, выход счетчика подключен ко вторым входам первого и четвертого входных буферных регистров, третьего и шестого регистpов повторного тактирования, третьим входом первого и третьего мультиплексоров 2:1 и через элемент задержки ко вторым входам первого, второго, четвертого и пятого регистров повторного тактирования, второму входу регистра хранения экспоненты вращения, первый вход которого является входом кода экспоненты вращения устройства.

Блок суммирования по модулю чисел Ферма содержит две группы сумматоров по N (N - количество разрядов) трехвходовых одноразрядных сумматоров, причем первые, вторые и третьи входы трехвходовых одноразрядных сумматоров первой группы сумматоров и третьи входы трехвходовых одноразрядных сумматоров второй группы сумматоров являются соответственно первым, вторым, третьим и четвертым входами блока суммирования по модулю чисел Ферма, выход суммы j-го трехвходового одноразрядного сумматора первой группы сумматоров (j= 1,2, ...,N) подключен к первому входу j-го трехвходового одноразрядного сумматора второй группы сумматоров, выход переноса N-го трехвходового одноразрядного сумматора первой группы сумматоров подключен ко второму входу первого трехвходового одноразрядного сумматора второй группы сумматоров, а выход переноса i-го трехвходового одноразрядного сумматора (i=1,2,...,N-1) первой группы сумматоров подключен ко второму входу (i+1)-го трехвходового одноразрядного сумматора второй группы сумматоров, шина сумм и шина переносов трехвходовых одноразрядных сумматоров второй группы сумматоров являются соответственно первым и вторым выходом блока суммирования по модулю чисел Ферма.

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

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

На фиг. 1 представлена структурная схема вычислительного элемента для осуществления быстрой свертки; на фиг. 2 - структурная схема блока суммирования по модулю чисел Ферма для разрядности данных N = 16; на фиг. 3 - вид управляющих сигналов, обеспечивающих функционирование устройства; на фиг. 4 - работа блока суммирования по модулю чисел Ферма.

Вычислительный элемент для осуществления быстрой свертки (фиг.1) содержит входные буферные регистры 1₁...1₄, регистры повторного тактирования 2₁. ..2₆, выходного регистра 3₁,3₂, регистр хранения экспоненты вращения 4, мультиплексоры 2:1, 5₁...5₄, мультиплексоры N:1 6₁...6₂, умножители на 2^3v/4 7₁, 7₂, умножители на 2^v/4, 8₁, 8₂, блоки суммирования по модулю чисел Ферма 9₁. . .9₃, входные 10 и выходные 11 шины, тактовый вход устройства 12, вход кода экспоненты вращения устройства 13, счетчик 14, элемент задержки 15.

Блок суммирования по модулю чисел Ферма 9 (фиг.2) содержит первую 16₁ и вторую 16₂ группы сумматоров, содержащие трехвходовые одноразрядные сумматоры 17.

Элементы вычислительного элемента для осуществления быстрой свертки соединены следующим образом.

Первым входом 10₁ вычислительного элемента является первый вход второго 1₂ входного буферного регистра, прямой выход которого соединен с первым входом первого 1₁ входного буферного регистра; выход первого регистра 2₁ повторного тактирования через первый 5₁ мультиплексор 2:1 подключен к первому входу первого выходного регистра 3₁, выход которого является первым выходом 11₁ устройства, выход второго регистра 2₂повторного тактирования через последовательно соединенные второй 5₂мультиплексор 2:1, третий регистр 2₃ повторного тактирования, первый 6₁мультиплексор N:1 подключен ко второму входу первого 5₁ мультиплексора 2:1, входы первых умножителей 2^3v/4 (7₁) и 2^v/4 (8₁) соединены с выходом второго регистра 2₂ повторного тактирования, к третьему входу второго 5₂мультиплексора 2:1 и второму входу первого 6₁ мультиплексора подключены соответственно первый и второй выходы регистра хранения экспоненты вращения 4, прямой выход второго 1₂ входного буферного регистра соединен с первым входом первого блока 9₁ суммирования по модулю чисел Ферма, первый выход которого через последовательно соединенные четвертый регистр 2₄, повторного тактирования и третий 5₃ мультиплексор 2:1 подключен к второму выходному регистру 3₂, выход которого является вторым выходом 11₂ вычислительного элемента для осуществления быстрой свертки, ко вторым входам первого 9₁ и второго 9₂ блоков суммирования по модулю чисел Ферма подключены соответственно прямой и инверсный выходы третьего 1₃ входного буферного регистра, выход первого 1₁ входного буферного регистра соединен с третьими входами первого 9₁ и второго 9₂ блоков суммирования по модулю чисел Ферма, четвертые входы которых подключены к выходу четвертого 1₄ входного буферного регистра, вход которого соединен с прямым выходом третьего 1₃ входного буферного регистра, инверсный выход второго входного 1₂ буферного регистра подключен к первому входу второго 9₂ блока суммирования по модулю чисел Ферма, первый выход которого через последовательно соединенные пятый регистр 2₅ повторного тактирования, четвертый 5₄ мультиплексор 2: 1, шестой регистр 2₆повторного тактирования и второй 6₂ мультиплексор N:1 соединен со вторым входом третьего 5₃ мультиплексора 2:1, выходы первого 7₁ умножителя 2^3v/4 и первого 8₁ умножителя 2^v/4 подключены соответственно к первому и второму входам третьего 9₃ блока суммирования по модулю чисел Ферма, первый и второй выходы которого соединены со вторыми входами соответственно второго 5₄ и четвертого 5₄ мультиплексоров 2:1, к третьему и четвертому входам третьего блока суммирования по модулю чисел Ферма 9₃ подключены выходы соответственно второго 7₂ умножителя 2^3v/4 и второго 8₂ умножителя 2^v/4, входы которых соединены с выходом пятого регистра 2₅ повторного тактирования, первый и второй выходы регистра хранения экспоненты вращения 4 подключены соответственно к третьему входу четвертого 5₄ мультиплексора 2:1 и ко второму входу второго 6₂ мультиплексора N:1, вторые выходы первого 9₁ и второго 9₂ блоков суммирования по модулю чисел Ферма соединены с первыми входами соответственно первого 2₁ и второго 2₂ регистров повторного тактирования, вторые входы второго 1₂ и третьего 1₃ входных буферных регистров, первого 3₁ и второго 3₂ выходных регистров и вход счетчика 14 соединены между собой и являются тактовым входом устройства 12, выход счетчика 14 подключен ко вторым входам первого 1₁ и четвертого 1₄входных буферных регистров, третьего 2₃ и шестого 2₆, регистров повторного тактирования, третьим входам первого 5₁ и третьего 5₃мультиплексоров 2:1 и через элемент задержки 15 ко вторым входам первого 2₁, второго 2₂, четвертого 2₄ и пятого 2₅ регистров повторного тактирования, второму входу регистра хранения экспоненты вращения 4, первый вход которого является входом 13 кода экспоненты вращения устройства.

В блоке суммирования по модулю чисел Ферма 9 объединенные шины первые, вторые и третьи входы трехвходовых одноразрядных сумматоров 17 первой группы сумматоров 16₁ и объединенные в шину третьи входы трехвходовых одноразрядных сумматоров 17 второй группы сумматоров 16₂являются соответственно первым, вторым, третьим и четвертым входом блока суммирования по модулю чисел Ферма 9. Выход суммы j-го (j=) трехвходового одноразрядного сумматора 17 первой группы сумматоров 16₁подключен к первому входу j-го трехвходового одноразрядного сумматора 17 второй группы сумматоров 16₂, выход переноса N-го трехвходового одноразрядного сумматора 17 первой группы сумматоров 16₁ подключен ко второму входу первого трехвходового одноразрядного сумматора 17 второй группы сумматоров 16₂, а выход переноса i-го (i= ) трехвходового одноразрядного сумматора 17 первой группы сумматоров 16₁подключен ко второму входу (i+1)-го трехвходового одноразрядного сумматора 17 втоpой группы сумматоров 16₂, объединенные в шины выхода сумм и выходы переносов трехвходовых одноразрядных сумматоров 17 второй группы сумматоров 16₂ являются соответственно первым и вторым выходом блока суммирования по модулю чисел Ферма.

Устройство работает следующим образом.

Рассмотрим ТЧПФ по основанию 2 применительно к 64-точечному преобразованию по модулю 2¹⁶+1 для 16-разрядных данных.

Предварительное кодирование данных осуществляется аналогично прототипу, однако отпадает необходимость в дополнительном разряде, кодирующем нулевой результат, поскольку он может быть представлен кодом любого числа и его дополнением. Например при t=4 и 2^t+1 = 17 нулевое число может быть представлено в виде
1 ряд 0101 (-8+4-2+1)=5
2 ряд 1010 (8-4+2-1)=-5
В исходном состоянии все регистры вычислительного элемента обнулены.

С поступлением первого тактового импульса на тактовый вход 12 (фиг. 3(а)) составляющие двухрядного кода числа А₁ со входов 10₁ и 10₂записываются во второй 1₂ и третий 1₃ входные буферные регистры. Счетчик 14 выделяет из последовательности входных тактовых импульсов каждый второй импульс (фиг. 3(б)).

С поступлением второго тактового импульса на вход 12 вычислительного элемента производится перезапись двухрядного кода числа А₁ из входных буферных регистров 1₂ и 1₃ соответственно в регистры 1₁ и 1₄, а двухрядный код числа В₁ записывается в регистры 1₂ и 1₃. (фиг. 3 интервал t₂).

Блоки суммирования по модулю чисел Ферма 9₁ и 9₂ производят соответственно сложение и вычитание двухрядных кодов чисел А и В. Процесс сложения иллюстрируют фиг. 4, где каждой точке соответствует двоичная цифра, сверху проставлены номера разрядов. Сплошной линией обведены числа, подаваемые на вход трехвходового одноразрядного сумматора 17. Результат работы сумматора 17 (цифра суммы и цифра переноса) изображены в виде двух связанных точек на следующей по порядку диаграмме, где буквами S и Р обозначены код суммы и код переноса, а цифрами 1,2,3,4 - коды, поступающие на соответствующие входы блока суммирования по модулю чисел Ферма 9. Особенности организации суммирования двухрядных кодов по модулю чисел Ферма в блоке 9 поясним следующим примером.

Пусть t = 4 (2^t+1=17), числа А и В представлены в виде двухрядных кодов
A = и B = ,
т.е. A = 13; B = - 2.

Операция сложения в блоке 9 выполняется в два этапа
I этап:
II этап: Последний результат соответствует числу -9+3=-6=11mod17, что и требовалось, так как (А+В)mod17 = 11 mod17.

Разность А-В вычисляется аналогично вышерассмотренному, только число -В подается на второй блок суммирования по модулю чисел Ферма 9₂ с инверсных выходов второго 1₂ и третьего 1₃ входных буферных регистров.

Второй тактовый импульс с выхода счетчика 14 проходит через элемент задержки на период следования тактовых импульсов (фиг.3(в)) и действует одновременно с третьим тактовым импульсов на входе 12. Он разрешает запись двухрядного кода результата сложения (А₁+В₁) в регистры повторного тактирования 2₁ и 2₄ двухрядного кода результата вычитания (А₁-В₁) в регистры повторного тактирования 2₂ и 2₅ и запись кода первой экспоненты вращения со входа 13 в регистр 4. Третьим тактовым импульсов на входе 12 двухрядный код числа А₂ записывается в регистры 1₂ и 1₃.

Двухрядный код результата вычитания по модулю чисел Ферма запоминается в регистрах повторного тактирования 2₂ и 2₅ для последующего умножения на степень 2. Умножение двухрядного кода, представленного составляющими S и Р, на 2 производится следующим образом. Поскольку
≡ (2¹²- 2⁴) mod (2¹⁶+1), то
(2¹⁶+1) =
Умножение составляющих S и Р на 12¹² и 2⁴ может производиться соответствующим соединением входов блока 9₃ с выходами регистров повторного тактирования 2₂, 2₅.

В зависимости от значения младшего разряда экспоненты вращения, которое определяет необходимость умножения (А-В) на , мультиплексоры 2:1 5₂ и 5₄ коммутируют двухрядный код (А-В), либо (А-В) для записи в регистры повторного тактирования 2₃ и 2₆. Запись в регистры повторного тактирования 2₃ и 2₆ осуществляется с поступлением второго тактового импульса с выхода счетчика 14 (фиг. 3(б)). Он действует одновременно с поступлением четвертого тактового импульса на вход 12 (фиг.3(а), t₄) и переводит мультиплексоры 5₁ и 5₃ в состояние, разрешающее запись двухрядного кода суммы (А+В) в выходные регистры 3₁ и 3₂. При этом двухрядный код числа А₂ записывается в регистры 1₁ и 1₄, двухрядный код В₂ - в регистры 1₂ и 1₃, а двухрядный код (А+В) - в регистры 3₁ и 3₂ и выдается на выходы вычислительного элемента 11₁ и 11₂.

Умножение на степень 2 каждой из составляющих S и Р двухрядного кода записанных в регистрах 2₃ и 2₆, производится в независимых цепях, первая из которых содержит регистр повторного тактирования 2₃, мультиплексор 16:16₁, а вторая - регистр повторного тактирования 2₆, мультиплексор 16:16₂.

В отсутствии тактового импульса на входе мультиплексоры 2:1 5₁ и 5₃находятся в состоянии, когда к их выходам подключены вторые входы.

В следующий временной интервал (фиг. 3, t₅) производится запись двухрядного кода (А₁-В₁) в выходные регистры 3₁ и 3₂ и выдача его на выходы 11₁ и 11₂ вычислительного элемента, запись двухрядных кодов (А₂+В₂) в регистры повторного тактирования 2₁ и 2₄, (А₂-В₂) - в регистры 2₂ и 2₅ и нового значения в регистр 4 хранения экспоненты вращения.

Далее процессы циклически повторяются.

При необходимости получения результата преобразования в традиционном однорядном коде к выходам вычислительного элемента последнего яруса может быть подключен сумматор по модулю чисел Ферма, выполненный по любой из известных схем, например по схеме (3), с.195, рис.7 или (3), с.194, рис. 6.

Для технико-экономического обоснования преимуществ предлагаемого устройства по быстродействию, произведем его сравнение с базовым объектом, в качестве которого выберем прототип, так как он является наиболее быстродействующим из известных устройств.

Из анализа структурной схемы базового объекта следует, что наиболее длительной операцией является операция суммирования по модулю чисел Ферма. Время выполнения сложения по модулю чисел Ферма определяется соотношением (3), с.194, рис. 5).

Т_б = 2m T_s + 2τ_э , где T_s - задержка в одноразрядном сумматоре;
m - разрядность данных;
τ_э- задержка в логическом элементе.

Полагая Т_s = 2τ_э(5), с.139, рис. 3.37,б), получим T_б = 66τ_э.

В предлагаемом устройстве время сложения двухрядных чисел, согласно фиг. 2 и фиг. 4, определяется как
Т₃ = 2 T_s = 4τ_э , откуда выигрыш в быстродействии составляет 66:4 = 16,5 раз при m = 16.

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

Изобретение относится к вычислительной технике, в частности к средствам цифровой обработки сигналов в реальном масштабе времени, и может быть применено в радиолокации, навигации и связи для построения быстродействующих цифровых процессоров. Цель изобретения - повышение быстродействия за счет предоставления дискретно преобразуемого сигнала двухстрочными кодами. Поставленная цель достигается путем организации вычисления операции "бабочка" с помощью теоретико-числовых преобразований по модулю чисел Ферма, причем промежуточные и окончательные результаты представляются двухрядными кодами, для чего в вычислительный элемент для осуществления быстрой свертки, содержащий первый и второй входные буферные регистры, первые умножители на 2^3v/4 и на 2^v/4 , три регистра повторного трактирования, первый выходной регистр, регистр хранения экспоненты вращения, три мультиплексора, введены три блока суммирования по модулю чисел Ферма, третий и четвертый входные буферные регистры, четвертый, пятый и шестой регистры повторного трактирования, второй выходной регистр, третий, четвертый, пятый и шестой мультиплексоры, вторые умножители на 2^3v/4 и на 2^v/4 , счетчик и элемент задержки, обеспечивающие сложение /вычитание/ двух чисел, представленных двухрядными кодами, и формирование кода результата также в виде двухрядного кода. 1 з.п. ф-лы, 4 ил.

1. ВЫЧИСЛИТЕЛЬНЫЙ ЭЛЕМЕНТ ДЛЯ ОСУЩЕСТВЛЕНИЯ БЫСТРОЙ СВЕРТКИ, содержащий первый и второй входные буферные регистры, первый, второй и третий регистры повторного тактирования, первый выходной регистр, регистр хранения экспоненты вращения, первые умножители на 2^3v/4 и 2^v/4 (v=2^t, где t - целые числа), первый, второй и третий мультиплексоры, причем первым информационным входом устройства является информационный вход первого буферного регистра, прямой выход которого соединен с информационным входом второго входного буферного регистра, выход первого регистра повторного тактирования соединен с первым информационным входом первого мультиплексора, выход которого подключен к информационному входу первого выходного регистра, выход которого является первым выходом устройства, выход второго регистра повторного тактирования соединен с первым информационным входом второго мультиплексора, выход которого соединен с информационным входом третьего регистра повторного тактирования, выход которого соединен с первым информационным входом третьего мультиплексора, выход которого соединен с вторым информационным входом первого мультиплексора, входы первых умножителей на 2^3v/4 и 2^v/4, соединены с выходом второго регистра повторного тактирования, управляющие входы второго и третьего мультиплексоров подключены соответственно к первому и второму выходам регистра хранения экспоненты вращения, отличающийся тем, что, с целью повышения быстродействия за счет представления дискрет преобразуемого сигнала двухрядными кодами, в него введены третий и четвертый входные буферные регистры, четвертый, пятый и шестой регистры повторного тактирования, второй выходной регистр, с четвертого по шестой мультиплексоры, вторые умножители на 2^3v/4 и 2^v/4 первый, второй и третий блоки суммирования по модулю чисел Ферма, счетчик и элемент задержки, причем прямой выход первого входного буферного регистра соединен с первым входом первого блока суммирования по модулю чисел Ферма, первый выход которого соединен с информационным входом четвертого регистра повторного тактирования, выход которого соединен с первым информационным входом четвертого мультиплексора, выход которого соединен с информационным входом второго выходного регистра, выход которого является вторым выходом устройства, вторые выходы первого и второго блоков суммирования по модулю чисел Ферма подключены соответственно к прямому и инверсному выходам третьего входного буферного регистра, информационный вход которого является вторым информационным входом устройства, выход второго входного буферного регистра соединен с третьими входами первого и второго блоков суммирования по модулю чисел Ферма, четвертые входы которых подключены к выходу четвертого входного буферного регистра, информационный вход которого соединен с прямым выходом третьего входного буферного регистра, инверсный выход второго входного буферного регистра подключен к первому входу второго блока суммирования по модулю чисел Ферма, первый выход которого соединен с информационным входом пятого регистра повторного тактирования, выход которого соединен с информационным входом пятого мультиплексора и входами вторых умножителей на 2^3v/4 и 2^v/4 выходы первого умножителя на 2^3v/4 и первого умножителя 2^v/4 подключены соответственно к первому и второму входам третьего блока суммирования по модулю чисел Ферма, первый и второй выходы которого соединены с вторыми информационными входами соответственно второго и пятого мультиплексоров, третий и четвертый входы третьего блока суммирования по модулю чисел Ферма подключены к инверсным выходам соответственно второго умножителя на 2^3v/4 и второго умножителя на 2^v/4, первый и второй выходы регистра хранения экспоненты вращения подключены соответственно к управляющим входам пятого и шестого мультиплексоров, вторые выходы первого и второго блоков суммирования по модулю чисел Ферма соединены с информационными входами соответственно первого и второго регистров повторного тактирования, тактовые входы первого и третьего входных буферных регистров, первого и второго выходных регистров и счетный вход счетчика соединены между собой и являются тактовым входом устройства, выход счетчика подключен к тактовым входам второго и четвертого входных буферных регистров, третьего и шестого регистров повторного тактирования, управляющим входам первого и четвертого мультиплексоров и через элемент задержки к тактовым входам первого, второго, четвертого и пятого регистров повторного тактирования, регистра хранения экспоненты вращения, информационный вход которого является входом экспоненты вращения устройства, выход пятого мультиплексора соединен информационным входом шестого регистра повторного тактирования, выход которого соединен с информационным входом шестого мультиплексора, выход которого соединен с вторым информационным входом четвертого мультиплексора. 2. Элемент по п. 1, отличающийся тем, что блок суммирования по модулю чисел Ферма содержит две группы сумматоров по N (N - количество разрядов) трехвходовых одноразрядных сумматоров, причем первые, вторые и третьи входы трехвходовых одноразрядных сумматоров первой группы сумматоров и третьи входы трехвходовых одноразрядных сумматоров второй группы сумматоров являются соответственно первым, вторым, третьим и четвертым входами блока суммирования по модулю чисел Ферма, выход суммы j-го трехвходового одноразрядного сумматора (j = 1,2..., N) первой группы сумматоров подключен к первому входу j-го трехвходового одноразрядного сумматора второй группы сумматоров, выход переноса N-го трехвходового одноразрядного сумматора первой группы сумматоров подключен к второму входу первого трехвходового одноразрядного сумматора второй группы сумматоров, выход переноса i-го трехвходового одноразрядного сумматора (i= 1,2, . .., N-1) первой группы сумматоров подключен к второму входу (i + 1)-го трехвходового одноразрядного сумматора второй группы сумматоров, объединенные в шину сумм и шину переносов выходы трехвходовых одноразрядных сумматоров второй группы сумматоров являются соответственно первым и вторым выходами блока суммирования по модулю чисел Ферма.