НАКАПЛИВАЮЩИЙ СУММАТОР-ВЫЧИТАТЕЛЬ ПО МОДУЛЮ ПРОИЗВОЛЬНОГО НАТУРАЛЬНОГО ЧИСЛА Российский патент 2022 года по МПК G06F7/505 

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

Известны накапливающие сумматоры [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 устройства. Выходы младших разрядов суммы сумматора 2 поразрядно соединены с первым информационным входом мультиплексора 3. Выход переноса сумматора 2 соединен с управляющим входом мультиплексора 3, выход которого соединен с информационным входом регистра 4. Тактовый вход регистра 4 является тактовым входом 9 устройства, а его вход обнуления является входом обнуления 10 устройства.

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

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

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

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

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

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

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

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

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

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

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

7 – вход двоичного кода модуля;

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

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

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

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

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

13 – первый набор инверторов;

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

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

16 – второй набор инверторов;

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

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

19 – вход выбора режима сложения или вычитания.

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

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

Перед началом работы на вход 10 устройства подается импульс, который обнуляет содержимое регистров 4, 17 и 18. На вход 9 устройства поступают тактовые импульсы, которые синхронизируют работу устройства. С каждым тактовым импульсом на вход 5 подается двоичный код очередного n-разрядного числа A(k), удовлетворяющего условию 0 ≤ A(k) < P. Он поступает на вход (X₁…X_n) мультиплексора 14 и вход набора инверторов 13. Поразрядно проинвертированный двоичный код A(k) с выхода набора инверторов 13 поступает на вход (Y₁…Y_n) мультиплексора 15 и вход (A₁…A_n) сумматора 12. На вход (B₁…B_n) сумматора 12 подается двоичный код модуля P, по которому осуществляется суммирование или вычитание, а на его вход переноса подается логическая единица со входа 8 устройства. На выходе (S₁…S_n) сумматора 12 формируется двоичный код положительного числа P - A(k), который поступает на вход (Y₁…Y_n) мультиплексора 14 и вход набора инверторов 16. Поразрядно проинвертированный двоичный код числа P - A(k) с выхода набора инверторов 16 поступает на вход (X₁…X_n) мультиплексора 15.

В режиме суммирования чисел A(k) на вход 19 устройства подается сигнал V с уровнем логического нуля. Под его воздействием на выходы (Q₁…Q_n) мультиплексоров 14 и 15 коммутируются входы (X₁…X_n). При этом на вход (D₁…D_n) регистра 17 поступает код числа A(k), который записывается в него очередным тактовым импульсом и далее поступает на вход (B₁…B_n) сумматора 1. На вход (D₁…D_n) регистра 18 поступает поразрядно проинвертированный код числа P - A(k), который записывается в него в очередным тактовым импульсом и далее поступает на вход (A₁…A_n) сумматора 2. На вход A_n+1 сумматора 2 подается логическая единица, поэтому на входе (A₁…A_n+1) сумматора 2 формируется двоичный дополнительный код отрицательного числа A(k) - P - 1. На выходе суммы (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), который записывается в регистр очередным тактовым импульсом.

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

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

(1)

В режиме вычитания чисел A(k) на вход 19 устройства подается сигнал V с уровнем логической единицы. Под его воздействием на выходы (Q₁…Q_n) мультиплексоров 14 и 15 коммутируются входы (Y₁…Y_n). При этом на вход (D₁…D_n) регистра 17 поступает код положительного числа P - A(k), который записывается в него очередным тактовым импульсом и далее поступает на вход (B₁…B_n) сумматора 1. На вход (D₁…D_n) регистра 18 поступает поразрядно проинвертированный код числа A(k), который записывается в него очередным тактовым импульсом и далее поступает на вход (A₁…A_n) сумматора 2. На входе (A₁…A_n+1) сумматора 2 формируется двоичный дополнительный код отрицательного числа - A(k) - 1. На выходе суммы (S₁…S_n) сумматора 1 формируется код числа S(k) + P - A(k), где S(k) – число, записанное в регистре 4. На выходе суммы (S₁…S_n+1) сумматора 2 формируется двоичный дополнительный код числа S(k) - A(k), причем разряд S_n+1 определяет знак числа.

Если A(k) > S(k), то разность S(k) - A(k) отрицательна и на выходе старшего разряда S_n+1 суммы сумматора 2 формируется логическая единица, под воздействием которой на выход мультиплексора 3 коммутируется его второй вход (Y₁…Y_n) и на информационный вход регистра 4 поступает код числа S(k) + P - A(k), который записывается в регистр очередным тактовым импульсом.

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

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

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

(2)

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

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

Предположим, что S(k) < P, тогда с учетом того, что A(k) < P, справедливо неравенство A(k) + S(k) - P < P.

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

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

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

РЕАЛИЗАЦИЯ

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

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

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

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

1. Справочник по интегральным микросхемам / Б.В. Тарабрин, С.В. Якубовский, Н.А. Барканов и др.; Под ред. Б.В. Тарабрина. – 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 + 1)-разрядный сумматор, два n-разрядных сумматора, три n-разрядных мультиплексора, три n-разрядных регистра и два набора инверторов. 2 ил.

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