Быстродействующий накапливающий сумматор по модулю произвольного натурального числа

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

 

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

Известны накапливающие сумматоры [1], [2], [3], содержащие двоичные сумматоры и регистры.

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

Наиболее близким по технической сущности к заявленному изобретению является накапливающий сумматор по модулю [4], схема которого представлена на фиг. 1, где обозначено:

1 – n-разрядный сумматор;

2 – (n + 1)-разрядный сумматор;

3 – мультиплексор;

4 – n-разрядный регистр;

5 – n-разрядный информационный вход устройства;

6 – вход логического нуля;

7 – вход поразрядно проинвертированного двоичного кода модуля;

8 – вход логической единицы;

9 – тактовый вход устройства;

10 – вход обнуления устройства;

11 – n-разрядный информационный выход устройства.

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

Устройство-прототип содержит сумматор 1, вход первого слагаемого которого соединен с выходом регистра 4 и является выходом 11 устройства, а вход второго слагаемого является информационным входом 5 устройства. На вход переноса сумматора 1 подается логический ноль со входа 6 устройства, а выход суммы сумматора 1 поразрядно соединен со вторым информационным входом мультиплексора 3 и n младшими разрядами первого слагаемого сумматора 2. Старший разряд первого слагаемого сумматора 2 соединен с выходом переноса сумматора 1, а на вход второго слагаемого сумматора 2 со входа 7 устройства подается поразрядно проинвертированный двоичный код модуля, по которому осуществляется суммирование. На вход переноса сумматора 2 подается логическая единица со входа 8 устройства. Выходы n младших разрядов суммы сумматора 2 поразрядно соединены с первым информационным входом мультиплексора 3. Выход переноса сумматора 2 соединен с управляющим входом мультиплексора 3, выход которого соединен с информационным входом регистра 4. Тактовый вход регистра 4 является тактовым входом 9 устройства, а его вход обнуления является входом обнуления 10 устройства.

Данное устройство осуществляет суммирование входной последовательности {A(k); k = 1, 2, …} n-разрядных чисел по модулю произвольного натурального числа P, лежащего в интервале [2, 2ⁿ - 1]. При этом сами числа принимают значения из интервала [0, P - 1].

Недостатком устройства является низкое быстродействие по сравнению с накапливающим сумматором [3], содержащим только n-разрядные сумматор и регистр. Это объясняется тем, что задержка распространения сигналов увеличивается на величину задержки в (n + 1)-разрядном сумматоре и мультиплексоре.

Задачей изобретения является повышение быстродействия.

Для решения поставленной задачи в быстродействующем накапливающем сумматоре по модулю произвольного натурального числа, содержащем n-разрядные сумматор, мультиплексор и регистр, а также (n + 1)-разрядный сумматор n младших разрядов выхода суммы которого поразрядно соединены с первым информационным входом мультиплексора, второй информационный вход которого соединен с выходом суммы n-разрядного сумматора, а выход мультиплексора соединен с информационным входом регистра, выход которого соединен со входом первого слагаемого n-разрядного сумматора и является информационным n-разрядным выходом устройства, тактовый вход регистра является тактовым входом устройства, а вход обнуления регистра является входом обнуления устройства, при этом на вход переноса n-разрядного сумматора подается логический ноль, согласно изобретению введены дополнительный n-разрядный сумматор, а также второй и третий n-разрядные регистры, причем тактовые входы регистров соединены с тактовым входом устройства, в входы обнуления регистров соединены со входом обнуления устройства, выход второго n-разрядного регистра соединен со входом второго слагаемого n-разрядного сумматора, а информационный вход второго n-разрядного регистра является n-разрядным информационным входом устройства и объединен со входом первого слагаемого дополнительногосумматора, при этом на вход второго слагаемого дополнительного сумматора подается поразрядно проинвертированный двоичный код модуля, по которому осуществляется суммирование, на вход переноса дополнительного сумматора подается логическая единица, а его выход суммы соединен с информационным входом третьего регистра, выход которого поразрядно соединен с n младшими разрядами входа первого слагаемого (n + 1)-разрядного сумматора, младшие n разрядов входа второго слагаемого (n + 1)-разрядного сумматора поразрядно соединены с выходом регистра, при этом на вход переноса (n + 1)-разрядного сумматора, а также на старший разряд входа его второго слагаемого подается логический ноль, на старший разряд входа первого слагаемого(n + 1)-разрядного сумматора подается логическая единица, а старший разряд его выхода суммы соединен с управляющим входом мультиплексора.

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

1 – n-разрядный сумматор;

2 – (n + 1)-разрядный сумматор;

3 – мультиплексор;

4 – n-разрядный регистр;

5 – n-разрядный информационный вход устройства;

6 – вход логического нуля;

7 – вход поразрядно проинвертированного двоичного кода модуля;

8 – вход логической единицы;

9 – тактовый вход устройства;

10 – вход обнуления устройства;

11 – n-разрядный информационный выход устройства;

12 – дополнительный n-разрядный сумматор;

13 – второй n-разрядный регистр;

14 – третий n-разрядный регистр.

На вход 5 последовательно, синхронно с тактовыми импульсами, подаваемыми на вход 9, подается последовательность чисел {A(k); k = 1, 2, …}, подлежащих накоплению. Далее она поступает на информационный вход регистра 13 и вход первого слагаемого сумматора 12. На вход второго слагаемого сумматора 12 подается поразрядно проинвертированный двоичный код модуля, по которому осуществляется суммирование. На вход переноса сумматора 12 подается логическая единица со входа 8 устройства, выход суммы сумматора 12 соединен с информационным входом регистра 14, выход которого соединен с n младшими разрядами входа первого слагаемого сумматора 2. Младшие n разрядов входа второго слагаемого сумматора 2 соединены с выходом регистра 4, на вход переноса сумматора 2, а также на старший разряд входа его второго слагаемого подается логический ноль со входа 6 устройства. Выход регистра 13 соединен со входом второго слагаемого сумматора 1, вход первого слагаемого которого соединен с выходом регистра 4 и выходом 11 устройства. На вход переноса сумматора 1 подается логический ноль со входа 6 устройства. Выход суммы сумматора 1 соединен со вторым информационным входом мультиплексора 3, первый информационный вход которого соединен с n младшими разрядами выхода суммы сумматора 2. Выход мультиплексора 3 соединен с информационным входом регистра 4, а его вход управления соединен с выходом старшего разряда суммы сумматора 2. На вход старшего разряда первого слагаемого сумматора 2 подается логическая единица со входа 8 устройства. Тактовые входы регистров 4, 13, 14 соединены с тактовым входом 9 устройства, а входы обнуления регистров 4, 13, 14 соединены со входом 10 обнуления устройства.

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

Перед началом работы на вход 10 устройства подается импульс, который обнуляет содержимое регистров 4, 13, 14. На вход 9 устройства поступают тактовые импульсы, которые синхронизируют работу устройства. С каждым тактовым импульсом на вход 5 поступает код очередного n-разрядного числа A(k), удовлетворяющего условию 0 ≤ A(k) < P. Он поступает на вход (D₁…D_n) регистра 13 и вход (A₁…A_n) сумматора 12. На вход (B₁…B_n) сумматора 12 подается поразрядно проинвертированный код модуля P, а на вход переноса – логическая единица. На выходе суммы (S₁…S_n) сумматора 12 формируется двоичный дополнительный код разности A(k) - P без знакового разряда. Так как A(k) < P, разность A(k) - P всегда отрицательна, поэтому ее знаковый разряд равен единице. По приходу очередного тактового импульса в регистр 13 записывается код числа A(k), а в регистр 14 – код числа A(k) - P без знакового разряда. На выходе суммы (S₁…S_n) сумматора 1 формируется код числа A(k)+S(k), где S(k) – число, записанное в регистре 4. На выходе суммы (S₁…S_n+1) сумматора 2 формируется двоичный дополнительный код числа A(k)+ S(k) - P, причем разряд S_n+1 определяет знак числа. Если A(k) + S(k) < P, то разность A(k)+ S(k) - P отрицательна и на выходе старшего разряда S_n+1 суммы сумматора 2 формируется логическая единица, под воздействием которой на выход мультиплексора 3 коммутируется второй вход (Y₁…Y_n), и на информационный вход регистра 4 поступает код числа A(k) + S(k), который записывается в регистр 4 очередным тактовым импульсом.

Если A(k) + S(k) ≥ P, то разность A(k) + S(k) - P больше или равна нулю, поэтому на выходе старшего разряда S_n+1 суммы сумматора 2 формируется логический ноль, и на выход мультиплексора коммутируется его первый вход (X₁…X_n).

На информационный вход регистра 4 поступает код неотрицательного числа A(k) + S(k) - P, который записывается в регистр 4 очередным тактовым импульсом.

Таким образом, на выходе регистра 4 и соответственно выходе 11 устройства формируется код следующего элемента выходной последовательности {S(k); k = 1, 2, …}

(1)

Покажем, что значения элементов последовательности {A(k); k = 1, 2, …} меньше P.

После прихода обнуляющего импульса на выходах регистров 4, 13, 14 устанавливаются коды нулевых чисел. На входах и выходе мультиплексора 3 также устанавливаются коды нулевых чисел, поэтому по приходу первого тактового импульса в регистр 4 записывается число S(1) = 0.

Если предположить, что S(k) < P, то с учетом того, что A(k) < P, справедливо неравенство A(k) + S(k) - P < P. Поэтому в соответствии с формулой (1) S(k + 1) < P. Согласно методу математической индукции все элементы последовательности {S(k); k = 1, 2, …} меньше P.

В соответствии с определением суммы по модулю P

Это означает, что заявляемое устройство реализует функцию накапливающего сумматора по модулю P, где P произвольное натуральное число из интервала [2, 2ⁿ - 1].

Повышение быстродействия осуществляется за счет одновременного вычисления чисел A(k) + S(k) и A(k) + S(k) - P, в то время как в устройстве-прототипе вначале вычисляется число A(k) + S(k), а затем число A(k) + S(k) - P.

РЕАЛИЗАЦИЯ

Для оценки на практике выигрыша в быстродействии было проведено моделирование в системе автоматического проектирования Quartus II при использовании программируемой логической интегральной схемы (ПЛИС) EP2C8F256I8 семейства Altera Cyclon II (аналог отечественной ПЛИС 5578ТС024).

В качестве модуля, по которому осуществляется суммирование, было выбрано число P = 30000, что соответствует n = 15.

Результат моделирования показал, что максимально возможная тактовая частота устройства-прототипа равна 135 МГц, а заявляемого устройства – 190 МГц. Таким образом, выигрыш в быстродействии составляет 1,4 раза.

ИСТОЧНИКИ ИНФОМАЦИИ

1. Справочник по интегральным микросхемам /n Б.В. Тарабрин, С.В.Якубовский, Н.А. Барканов и др.; Под ред. Б.В. Тарабрина. – 2-е изд., перераб. и доп. – М: Энергия, 1981. – 816 c., ил., Рис. 5-250, стр. 741.

2. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. – М.: Радио и связь, 1990. – 304 с.: ил., Рис. 4.80, стр. 268.

3. Наумкина Л.Г. Цифровая схемотехника. Конспект лекций по дисциплине «Схемотехника» – М.: «Горная книга». Издательство Московского государственного горного университета, 2008, Рис. 6.9, стр. 228.

4. Патент RU 2 500 017 С1. Накапливающий сумматор по модулю. Опубликован 17.11.2013. Бюл. № 33.

Быстродействующий накапливающий сумматор по модулю произвольного натурального числа, содержащий n-разрядные сумматор, мультиплексор и регистр, а также (n + 1)-разрядный сумматор, n младших разрядов выхода суммы которого поразрядно соединены с первым информационным входом мультиплексора, второй информационный вход которого соединен с выходом суммы n-разрядного сумматора, а выход мультиплексора соединен с информационным входом регистра, выход которого соединен со входом первого слагаемого n-разрядного сумматора и является информационным n-разрядным выходом устройства, тактовый вход регистра является тактовым входом устройства, а вход обнуления регистра является входом обнуления устройства, при этом на вход переноса n-разрядного сумматора подается логический ноль, отличающийся тем, что в него введены дополнительный n-разрядный сумматор, а также второй и третий n-разрядные регистры, причем тактовые входы регистров соединены с тактовым входом устройства, а входы обнуления регистров соединены со входом обнуления устройства, выход второго n-разрядного регистра соединен со входом второго слагаемого n-разрядного сумматора, а информационный вход второго n-разрядного регистра является n-разрядным информационным входом устройства и объединен со входом первого слагаемого дополнительного сумматора, при этом на вход второго слагаемого дополнительного сумматора подается поразрядно проинвертированный двоичный код модуля, по которому осуществляется суммирование, на вход переноса дополнительного сумматора подается логическая единица, а его выход суммы соединен с информационным входом третьего регистра, выход которого поразрядно соединен с n младшими разрядами первого слагаемого (n + 1)-разрядного сумматора, младшие n разрядов входа второго слагаемого (n + 1)-разрядного сумматора поразрядно соединены с выходом регистра, при этом на вход переноса (n + 1)-разрядного сумматора, а также на старший разряд входа его второго слагаемого подается логический ноль, на старший разряд входа первого слагаемого (n + 1)-разрядного сумматора подается логическая единица, а старший разряд его выхода суммы соединен с управляющим входом мультиплексора.