РЕКОНФИГУРИРУЕМЫЙ АСИНХРОННЫЙ СУММАТОР-УМНОЖИТЕЛЬ Российский патент 2000 года по МПК G06F7/50 G06F7/52 

Изобретение относится к техническим средствам информатики и вычислительной техники и может быть использовано в высокоскоростных арифметико-логических устройствах, в том числе в арифметико-логических устройствах для вычисления быстрого преобразования Фурье (БПФ) и сверток по методу Винограда.

Известны различные схемы сумматоров, а также умножителей, построенных на основе последовательно включенных сумматоров [1].

В качестве прототипа выбран "Параллельный асинхронный сумматор" (патент РФ N 2097826, 1997 г. Бюл. N 33), содержащий n блоков параллельной обработки разрядных срезов, n-1 формирователей импульсов, запускающий формирователь импульсов, элемент 8 ИЛИ-НЕ. Его отличительной особенностью является организация процесса сложения операндов по разрядным срезам. С помощью обратной связи выхода суммы арифметического полусумматора на его вход через один из ключей осуществляется пространственное разделение ситуаций возникновения переносов и их одновременная коррекция в разных позициях параллельного асинхронного сумматора, что повышает его быстродействие.

Вычисление дискретного преобразования Фурье и сверток широко применяется в области цифровой обработки сигналов. Известны методы, позволяющие уменьшить их вычислительную сложность. Один из них - алгоритм Винограда [2]. Особенностями алгоритмов Винограда вычисления сверток и дискретного преобразования Фурье являются значительное превышение числа сложений над числом умножений, попеременное вычисление больших групп сложений и умножений. В связи с этим возможно построение реконфигурируемого арифметико-логического устройства для выполнения сложений и умножений, составным элементом которой является устройство на основе параллельного асинхронного сумматора. Недостатком параллельного асинхронного сумматора является отсутствие аппаратной поддержки выполнения операции умножения.

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

Технически задача решается тем, что к блоку асинхронного суммирования, который состоит из 2m блоков параллельной обработки разрядных срезов, 2m-1 формирователей импульсов и запускающего формирователя импульсов, первые выходы которых соединены с соответствующими входами элемента ИЛИ-НЕ, выход которого является выходом готовности суммы, а вторые выходы блоков параллельной обработки разрядных рядных срезов являются выходами результата, с целью возможности объединения m блоков асинхронного суммирования в реконфигурируемую матрицу и осуществления подачи слагаемых на соответствующие блоки асинхронного суммирования дополнительно введены: коммутатор-сдвигатель первого слагаемого, блок мультиплексоров первого слагаемого, состоящий из 2m мультиплексоров 3 в 1, блок мультиплексоров второго слагаемого, состоящий из 2m мультиплексоров 2 в 1, мультиплексор готовности суммы, инвертор, 2m шинных мультиплексора слагаемых, каждый из которых содержит 2m мультиплексоров n в 1, блок управления устройством, шинный мультиплексор множителя, состоящий из m мультиплексоров n в 1. Информационные входы шинных мультиплексоров слагаемых соединены с n 2m-разрядными входами данных, информационные входы шинного мультиплексора множителя соединены с n m-разрядными входами, которые являются младшими разрядами входов данных. Выход шинного мультиплексора множителя, а также вход команд подключены к блоку управления. Выходы шинных мультиплексоров слагаемых соединены с соответствующими входами блоков асинхронного суммирования. Выходы блока управления соединены с управляющими входами шинного мультиплексора множителя, шинных мультиплексоров слагаемых, а также с блоками мультиплексоров первого слагаемого, блоками мультиплексоров второго слагаемого, мультиплексорами готовности суммы блоков асинхронного суммирования, выход начала суммирования блока управления соединен со вторым входом мультиплексора готовности суммы блоков асинхронного суммирования. Вход первого слагаемого блока асинхронного суммирования соединен с коммутатором-сдвигателем первого слагаемого и вторым входом блока мультиплексоров первого слагаемого. Выход коммутатора-сдвигателя соединен с первым входом блока мультиплексоров первого слагаемого, третий вход блока мультиплексоров первого слагаемого подключен ко входу логического нуля. Вход второго слагаемого блока асинхронного суммирования соединен со вторым входом блока мультиплексоров второго слагаемого. Первый вход блока мультиплексоров второго слагаемого, исключая первый блок асинхронного суммирования, соединен с выходом результата предыдущего блока асинхронного суммирования, первый вход блока мультиплексоров второго слагаемого первого блока асинхронного суммирования соединен с логическим нулем. Выходы блоков мультиплексоров первого и второго слагаемого соединены с соответствующими входами блоков параллельной обработки разрядных срезов. Вход готовности суммы является выходом готовности суммы предыдущего блока асинхронного суммирования, исключая первый блок асинхронного суммирования, и соединен через инвертор с первым входом мультиплексора готовности суммы. Выход мультиплексора готовности суммы соединен с блоками параллельной обработки разрядных срезов и запускающим формирователем импульсов. В первом блоке асинхронного суммирования вход готовности суммы, мультиплексор готовности суммы и инвертор отсутствуют, сигнал начала суммирования блока управления соединен непосредственно с блоками параллельной обработки разрядных срезов и запускающим формирователем импульсов.

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

Реконфигурируемый асинхронный сумматор-умножитель состоит из 2m шинных мультиплексоров слагаемых 1, которые объединены в блок шинных мультиплексоров слагаемых 2, шинного мультиплексора множителя 3, блока управления 4, m блоков асинхронного суммирования 5, которые объединены в реконфигурируемую матрицу 6. В блок асинхронного суммирования входят коммутатор-сдвигатель 7, блок мультиплексоров первого слагаемого 8, блок мультиплексоров второго слагаемого 9, мультиплексор готовности суммы 10, асинхронный сумматор 11, со стоящий из 2m блоков параллельной обработки разрядных срезов 12, 2m-1 формирователей импульсов 13₁...13_2m-1, запускающего формирователя импульсов 13₀, инвертора 14, элемента ИЛИ-НЕ 15.

Устройство работает следующим образом. Известно, что произведение двух k-разрядных чисел есть 2k-paзрядное число, которое является суммой k сдвигов одного из множителей, сдвинутых согласно значениям разрядов другого множителя, то есть, к примеру, произведение чисел 11 (двоичное представление 1011) и 7 (двоичное представление 0111) есть сумма сдвигов числа 1011 согласно значениям разрядов числа 0111 (проиллюстрировано на фиг. 3). Таким образом, возможно построение устройства, выполняющего в определенный промежуток времени либо одно умножение двух k-разрядных чисел, либо k сложений чисел разрядностью 2k-l. Предлагаемое устройство реализует данную возможность с помощью матрицы параллельных асинхронных сумматоров, выполняемая операция (умножение либо группа сложений) определяется с помощью изменения конфигурации связей блоков асинхронного суммирования и подачей на блоки асинхронного суммирования требуемых входных значений. Программоуправляемый блок управления 4 управляет работой следующих блоков устройства: шинных мультиплексоров слагаемых 1₁...1_2m с помощью соответствующих сигналов управления шинными мультиплексорами слагаемых УМ₁...УМ_2m шинного мультиплексора множителя 3 с помощью сигнала управления шинным мультиплексором множителя УММ; блоками мультиплексоров первого слагаемого 8, блоками мультиплексоров второго слагаемого 9, мультиплексорами готовности суммы 10 блоков асинхронного суммирования 5₁...5_m с помощью сигналов управления блоками асинхронного суммирования УС₁...УС_m, кроме того, блок управления выдает на блоки асинхронного суммирования сигнал C начала суммирования. Возможны два типа операций, исполняемых устройством в определенный момент времени: выполнение одного умножения двух m-разрядных чисел, либо m сложений чисел разрядностью 2m. В зависимости от кода операции, определяемого программой, подаваемой на вход команд ПРОГ, блок управления 4 выдает следующие значения сигналов управления, сведенные в таблицу на фиг. 4. Если выполняемая операция - умножение, на сигнал управления шинным мультиплексором множителя УММ выдается число от 1 до n требуемого входного значения множителя, определяемое программой, которое затем подается на блок управления для выполнения операции умножения. На четные номера сигналов управления шинными мультиплексорами слагаемых УМ₂, УМ₄,...,УМ_2m выдается число от 1 до n требуемого входного значения множимого, определяемое программой, которое затем через соответствующие шинные мультиплексоры слагаемых подается на входы первого слагаемого СЛ₁...СЛ_1m блоков асинхронного суммирования. На нечетные номера сигналов управления шинными мультиплексорами слагаемых УM₁, УМ₃,...,УМ_2m-1 выдается комбинация, сигнализирующая о том, что соответствующие шинные мультиплексоры слагаемых необходимо перевести в третье состояние, значения входов второго слагаемого СЛ2₁...СЛ2_m блоков асинхронного суммирования не используются. Если выполняемые операции - группа сложений, на сигнал управления шинным мультиплексором множителя УММ выдается комбинация, сигнализирующая о том, что шинный мультиплексор множителя необходимо перевести в третье состояние, значение его выхода не используется. На сигналы управления шинными мультиплексорами слагаемых УМ₁...УМ_2m выдаются числа от 1 до n требуемых входных значений слагаемых, определяемые программой, которые затем через соответствующие шинные мультиплексоры слагаемых подаются на входы первого слагаемого СЛ1₁...СЛ1_m и входы второго слагаемого СЛ2₁. . . СЛ2_m блоков асинхронного суммирования. Сигналы управления блоками асинхронного суммирования УС₁...УС_m управляют блоками мультиплексоров первого слагаемого, блоками мультиплексоров второго слагаемого и мультиплексорами готовности суммы соответствующих блоков асинхронного суммирования. Каждый из сигналов управления блоком асинхронного суммирования УС является двухразрядным. Младший разряд является признаком выполняемой операции и устанавливается блоком управления в "0", если выполняемая операция - умножение, и в "1", если выполняемая операция - сложение. Старший разряд при выполнении сложения всегда принимает значение "0", а при выполнении умножения является инверсией соответствующего разряда множителя, подаваемого с шинного мультиплексора множителя на блок управления. К примеру, если i-й разряд множителя имеет значение "1", то старший разряд сигнала управления i-м блоком асинхронного суммирования УС_i принимает значение "0". Таким образом, на первый вход асинхронного сумматора через блок мультиплексоров первого слагаемого при значении сигнала УС_i "00" подается множимое со входа первого слагаемого СЛ_i, сдвинутое влево с помощью коммутатора-сдвигателя на i разрядов, при значении "01" подается первое слагаемое со входа первого слагаемого СЛ_i, при значении "10" на первый вход асинхронного сумматора подаются логические нули. На блок мультиплексоров второго слагаемого и мультиплексор готовности суммы подается только младший разряд сигнала управления блоком асинхронного суммирования УС_i, таким образом, при значении младшего разряда сигнала УС_i "0", на второй вход асинхронного сумматора подается выход результата предыдущего блока асинхронного суммирования, на блоки параллельной обработки разрядных срезов и запускающий формирователь импульсов - инверсия значения выхода готовности суммы предыдущего блока асинхронного суммирования, а при значении младшего разряда сигнала УС_i "1" на второй вход асинхронного сумматора подается значение со входа второго слагаемого СЛ₂, на блоки параллельной обработки разрядных срезов и запускающий формирователь импульсов - сигнал C начала суммирования. Процесс выполнения группы операций сложения состоит из двух стадий. Первая стадия начинается поступлением сигнала начала суммирования C = 1. К этому времени на входы асинхронного сумматора 11 уже поданы значения операндов. При поступлении сигнала C = 1 запускающий формирователь импульсов 13₀ вырабатывает сигнал, инициирующий начало суммирования. В результате сложения операндов по разрядам формируется текущая сумма на выходах 12 и значения переносов, которые анализируются элементом ИЛИ-НЕ 15. Если не было переносов, то текущая сумма становится окончательной, о чем сигнализирует "1" на выходе готовности суммы ГС_i. Затем следует вторая стадия сложения, которая заключается в параллельной коррекции текущей суммы путем ее сложения по разрядным срезам с полученными значениями переносов. Параллельная коррекция текущей суммы осуществляется по сигналу C = 0. На время коррекции возбужденные формирователи импульсов 13₁...13_2m-1 выдают сигналы на элемент ИЛИ-НЕ 15, так что на выходе готовности суммы ГС_i формируется сигнал "0", сигнализирующий о том, что сумма еще не готова. Выполнение операции умножения начинается поступлением сигнала начала суммирования C = 1 на блок асинхронного суммирования 5₁. Суммирование на этом блоке происходит соответственно описанному выше процессу выполнения операции сложения. После того как сумма готова, она подается с выхода результата PE3₁ на вход следующего блока асинхронного суммирования 5₂, на выходе готовности суммы сформировался сигнал ГС₁ = 1, свидетельствующий о готовности суммы, одновременно разрешающий начало второй стадии сложения на блоке асинхронного суммирования 5₂. Корректное завершение первой стадии суммирования гарантируется более длинной цепью прохождения сигнала готовности результата через блоки 13-15-14-10, чем сигнала результата через блок 9. После завершения суммирования на блоке 5₂ процесс переходит на блок 5₃, и так далее, пока на выходе РЕЗ_m блока асинхронного суммирования 5_m не появится результат умножения, а на выходе готовности суммы ГС_m "1", свидетельствующая о готовности результата умножения.

Список использованной литературы
1. Карцев М.А. Арифметика цифровых машин. - М.: Наука.

2. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. - М.: Мир, 1989.

3. Патент РФ N 2097826, 1997. Титенко Е.А., Титов B.C., Довгаль В.М.

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

Реконфигурируемый асинхронный сумматор-умножитель, содержащий блок асинхронного суммирования, состоящий из 2m блоков параллельной обработки разрядных срезов, 2m-1 формирователей импульсов и запускающего формирователя импульсов, первые выходы формирователей импульсов и запускающего формирователя импульсов соединены с соответствующими входами элемента ИЛИ-НЕ, выход которого является выходом готовности суммы блока асинхронного суммирования, а вторые выходы блоков параллельной обработки разрядных срезов являются выходами результата блока асинхронного суммирования, отличающийся тем, что в него введены 2m шинных мультиплексоров слагаемых, каждый из которых содержит m мультиплексоров n в 1, блок управления устройством, шинный мультиплексор множителя, состоящий из m мультиплексоров n в 1, m-1 блоков асинхронного суммирования, а в каждый блок асинхронного суммирования дополнительно введены коммутатор-сдвигатель первого слагаемого, блок мультиплексоров первого слагаемого, состоящий из 2m мультиплексоров 3 в 1, блок мультиплексоров второго слагаемого, состоящий из 2m мультиплексоров 2 в 1, мультиплексор готовности суммы, инвертор, причем информационные входы шинных мультиплексоров слагаемых соединены с n 2m-разрядными входами данных сумматора-умножителя, информационные входы шинного мультиплексора множителя соединены с n m-разрядными входами данных, являющимися младшими разрядами входов данных сумматора-умножителя, выход шинного мультиплексора множителя и вход команд сумматора-умножителя подключены к блоку управления, управляющие выходы которого соединены с соответствующими шинными мультиплексорами слагаемых, шинным мультиплексором множителя, выходы шинных мультиплексоров слагаемых соединены с соответствующими входами слагаемых блоков асинхронного суммирования, выход результата и выход готовности суммы каждого блока асинхронного суммирования являются выходами сумматора-умножителя и одновременно служат входами результата и готовности суммы для соответствующего следующего блока асинхронного суммирования, в каждом блоке асинхронного суммирования вход первого слагаемого соединен с вторым входом блока мультиплексоров первого слагаемого и коммутатором-сдвигателем первого слагаемого, выход которого соединен с первым входом блока мультиплексоров первого слагаемого, третий вход блока мультиплексоров первого слагаемого соединен с логическим нулем, вход второго слагаемого и выход результата предыдущего блока асинхронного суммирования - соответственно с вторым и первым входами блока мультиплексоров второго слагаемого, выходы блока мультиплексоров первого слагаемого и блока мультиплексоров второго слагаемого - с соответствующими первыми и вторыми входами блоков параллельной обработки разрядных срезов, вход готовности суммы блока асинхронного суммирования через инвертор соединен с первым входом мультиплексора готовности суммы, выход мультиплексора готовности суммы - с соответствующими входами блоков параллельной обработки разрядных срезов и запускающим формирователем импульсов, блок управления предназначен для подачи на блоки мультиплексоров первого и второго слагаемых, мультиплексор готовности суммы каждого блока асинхронного суммирования соответствующих управляющих сигналов.