Арифметический вычислитель систем булевых функций

Иллюстрации

Показать все

Изобретение относится к вычислительной технике и может быть использовано как специализированный вычислитель универсальный в классе логических вычислений. Техническим результатом является уменьшение длительности вычислений. Устройство содержит коммутатор, 2k блоков памяти хранения коэффициентов, где k - количество булевых переменных разложения, (n-k+1) мультиплексоров выделения группы коэффициентов, сумматор, d мультиплексоров выделения информационного разряда, 2k блоков памяти хранения значений адресов информационных разрядов, многоканальный мультиплексор. 2 ил., 1 табл., 6 пр.

Реферат

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

Известен арифметический вычислитель систем булевых функций, содержащий блок конъюнкций, входы которого являются шиной подачи значений булевых переменных, выходы которого подключены к блоку памяти, выходы которого подключены к входам коммутатора, выходы которого подключены к многоместному сумматору, выходы которого являются выходами устройства выдачи результата вычислений (Малюгин В.Д. Параллельные логические вычисления посредством арифметических полиномов / [Текст] - М.: Наука. Физматлит, 1997. - С.154-155).

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

Наиболее близким по сущности технического решения заявленному устройству является модулярный вычислитель систем булевых функций, содержащий коммутатор, входы которого являются входами устройства для подачи n булевых переменных, а выходы с (k+1) по n подключены к входам блока конъюнкций, выходы которого подключены к входам каждого из 2k блоков памяти, выходы которых подключены к входам 2n-k мультиплексоров, где i-й выход j-го блока памяти подключен к j-му входу i-го мультиплексора (i=1, 2, …,2n-k; j=1, 2, …,2k), управляющие входы каждого из которых соединены с k первыми выходами коммутатора, а выходы подключены к входам многоместного сумматора, выходы которого являются выходами устройства выдачи результата вычисления булевых функций (Пат. 2373564 Российская Федерация, МПК8 G06F 7/57. Модулярный вычислитель систем булевых функций [Текст] / Щербаков А.В.; заявитель и патентообладатель Щербаков А.В. - №2007141074/09; заявл. 06.11.2007; опубл. 20.05.2009, Бюл. №32. - 9 с.: ил.).

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

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

Поставленная цель достигается тем, что в арифметический вычислитель систем булевых функций, содержащий n входов подачи булевых переменных, коммутатор, 2k блоков памяти хранения групп коэффициентов, (n-k+1) мультиплексоров выделения группы коэффициентов, многоместный сумматор, d выходов выдачи значений булевых функций, где информационные входы коммутатора являются входами подачи булевых переменных устройства, а выходы с (k+1)-го по n-й подключены к информационным входам каждого из 2k блоков памяти хранения коэффициентов, выходы которых подключены к информационным входам каждого из (n-k+1) мультиплексоров выбора группы коэффициентов, где i-й выход j-го блока памяти подключен к j-му входу j-го мультиплексора (i=1, 2, …, n-k+1; j=1, 2, …, 2k), адресные входы каждого из которых соединены с k первыми выходами коммутатора, а выходы подключены к многоместному сумматору, с целью уменьшения длительности вычислений введены d мультиплексоров выделения информационного разряда, многоканальный мультиплексор, 2k блоков памяти хранения значений адресов информационных разрядов, управляющий вход подачи сигнала выбора реализуемой системы булевых функций и управляющий вход подачи сигнала выбора булевых переменных разложения, который является управляющим входом коммутатора, а управляющий вход подачи сигнала выбора реализуемой булевой функции устройства является управляющим входом каждого из 2k блоков памяти хранения коэффициентов и каждого из 2k блоков памяти хранения значений адресов информационных разрядов, выходы каждого из которых подключены к информационным входам многоканального мультиплексора, адресные входы которого соединены с первыми k выходами коммутатора, а выходы с 1-го по d-й подключены к адресным входам d мультиплексоров выделения информационного разряда соответственно, информационные входы каждого из которых соединены с выходами многоместного сумматора, а выходы являются выходами выдачи значений булевых функций устройства.

Структурная схема предлагаемого устройства дана на фиг.1.

Предлагаемое устройство содержит: коммутатор 1, блоки 2.1, …, 2.2k памяти, блоки 3.1, …, 3.2k памяти, многоканальный мультиплексор 4, мультиплексоры 5.1, …, 5.(n-k+1), многоместный сумматор 6, мультиплексоры 7.1, …, 7.d, входы 8.1, …, 8.n подачи значений булевых переменных х1, х2, …, xn, управляющий вход 9 подачи сигнала выбора переменных разложения, управляющий вход 10 подачи сигнала выбора реализуемой СБФ, выходы 11.1, …, 11.d выдачи значений булевых функций ƒ1(x), …, ƒd(x) соответственно.

Выходы 8.1, …, 8.n устройства подачи значений булевых переменных x1, х2, …, xn являются входами коммутатора 1, управляющий вход которого является управляющим входом 9 устройства подачи сигнала выбора переменных разложения, а выходы k+1, …, n подключены к блокам 3.1, …, 3.2k памяти соответственно. Управляющие входы блоков 3.1, …, 3.2k памяти соединены с управляющим входом 10 устройства подачи сигнала выбора реализуемой системы булевых функций, а первые выходы каждого подключены к информационным входам мультиплексора 5.1, вторые выходы каждого подключены к информационным входам мультиплексора 5.2 и так далее, (n-k+1)-е выходы каждого подключены к информационным входам мультиплексора 5.(n-k+1). Адресные входы мультиплексоров 5.1, …, 5.(n-k+1) соединены с k первыми выходами коммутатора 1, а выходы подключены к многоместному сумматору 6, двоичные выходы которого подключены к информационным входам каждого мультиплексора 7.1, …, 7.d, выходы которых являются выходами 11.1, …, 11.d устройства выдачи значений БФ ƒ1(х), …, ƒd(x). Адресные входы мультиплексоров 7.1, …, 7.d соединены с выходами многоканального мультиплексора 4, соответственно первый выход многоканального мультиплексора 4 подключен к адресному входу мультиплексора 7.1, второй выход многоканального мультиплексора 4 подключен к адресному входу мультиплексора 7.2 и так далее, d-й выход многоканального мультиплексора 4 подключен к адресному входу мультиплексора 7.d. Адресные входы многоканального мультиплексора 4 соединены с k первыми выходами коммутатора 1, а информационные входы соединены с выходами блоков 2.1, …, 2.2k памяти, управляющие входы которых соединены с управляющим входом 10 устройства подачи сигнала выбора реализуемой СБФ.

При этом блоки 2.1, …, 2.2k памяти предназначены для хранения значений адресов информационных разрядов, соответствующих значениям БФ ƒd(x), …, ƒ1(x), блоки 3.1, …, 3.2k памяти предназначены для хранения групп коэффициентов системы (14), многоканальный мультиплексор предназначен для выделения группы значений адресов информационных разрядов, мультиплексоры 5.1, …, 5.(n-k+1) предназначены для выделения группы коэффициентов, в соответствии с заданным значением переменных разложения, мультиплексоры 7.1, …, 7.d предназначены для выделения информационных разрядов. Многоместный сумматор, как в случае прототипа, так и в случае предлагаемого устройства имеет наиболее типичную - пирамидальную структуру, представленную на фиг.2.

В исходном состоянии с помощью управляющего сигнала, поступающего с управляющего входа 10 подачи сигнала выбора реализуемой СБФ на управляющие входы блоков 2.1, …, 2.2k памяти, производится запись групп значений адресов информационных разрядов, соответствующих БФ ƒ1(x), …, ƒd(x) и с помощью того же сигнала в блоки 3.1, …, 3.2k памяти записываются значения групп коэффициентов , которые соответствуют реализуемой СБФ (9). В момент времени, соответствующий началу преобразования, на входы 8.1, …, 8.n коммутатора 1 поступают значения булевых переменных х1, х2, …, xn. В коммутаторе 1 под воздействием управляющего сигнала, поступающего на его управляющий вход с управляющего входа устройства 9 подачи сигнала выбора переменных разложения, выделяются переменные разложения xi1, xi2, …, xik, которые поступают на адресные входы многоканального мультиплексора 4 и адресные входы мультиплексоров 5.1, …, 5.(n-k+1), а остальные информационные переменные поступают на входы блоков 3.1, …3.2k памяти, с первых выходов которых коэффициенты поступают на информационные входы мультиплексора 5.1, со вторых выходов коэффициенты поступают на информационные входы мультиплексора 5.2 и так далее, с (n-k+1)-х выходов коэффициенты поступают на информационные входы мультиплексора 5.(n-k+1). Мультиплексоры 5.1, …, 5.(n-k+1) выделяют первый, второй и так далее, (n-k+1)-й коэффициенты соответственно, в соответствии со значениями переменных разложения, поступающих на их адресные входы. Выделенная группа коэффициентов с выходов мультиплексоров 5.1, …, 5.(n-k+1) поступает на входы многоместного сумматора 6. После преобразований в многоместном сумматоре полученное значение с двоичных выходов многоместного сумматора 6 поступает на двоичные входы каждого мультиплексора 7.1, …, 7.d, которые в соответствии с управляющим сигналом, поступившим на их адресные входы, выделяют на выходы 11.1, …, 11.d устройства значения булевых функций в следующем порядке ƒ1(х), …, ƒd(х), где управляющий сигнал формируется в результате подачи групп значений адресов информационных разрядов с выходов блоков 2.1, …. 2.2k памяти на информационные входы многоканального мультиплексора 4, где с выходов блока 2.1 подаются значения адресов информационных разрядов для разложения на первый вход многоканального мультиплексора 4, с выходов блока 2.2 подаются значения адресов информационных разрядов для разложения на второй вход многоканального мультиплексора 4 и так далее, с выходов блока 2.2k подаются коэффициенты для разложения на 2k-й вход многоканального мультиплексора 4, который в свою очередь в соответствии со значениями переменных разложения, подаваемыми на его адресные входы с k первых выходов коммутатора 1, выбирает группу значений адресов информационных разрядов и передает на адресные входы мультиплексоров 7.1, …, 7.d.

Предлагаемое устройство имеет глубину в 5 ступеней преобразования: 1-я ступень - коммутатор, 2-я ступень - 2k блоков памяти хранения групп коэффициентов и 2k блоков памяти хранения адресов информационных разрядов, 3-я ступень - (n-k+1) мультиплексоров выделения информационного разряда и многоканальный мультиплексор, 4-я ступень - многоместный сумматор, 5-я ступень - d мультиплексоров выделения информационного разряда, прототип имеет такую же глубину: 1-я ступень - коммутатор, 2-я ступень - блок конъюнкций, 3-я ступень - 2k блоков памяти, 4-я ступень - 2n-k мультиплексоров, 5-я ступень - многоместный сумматор, однако наиболее существенный вклад в длительность преобразования как предлагаемого устройства, так и прототипа вносит многоместный арифметический сумматор, длительность его вторых выходов коэффициенты поступают на информационные входы мультиплексора 5.2 и так далее, с (n-k+1)-х выходов коэффициенты поступают на информационные входы мультиплексора 5.(n-k+1). Мультиплексоры 5.1, …, 5.(n-k+1) выделяют первый, второй и так далее, (n-k+1)-й коэффициенты соответственно, в соответствии со значениями переменных разложения, поступающих на их адресные входы. Выделенная группа коэффициентов с выходов мультиплексоров 5.1, …, 5.(n-k+1) поступает на входы многоместного сумматора 6. После преобразований в многоместном сумматоре полученное значение с двоичных выходов многоместного сумматора 6 поступает на двоичные входы каждого мультиплексора 7.1, …,7.d, которые в соответствии с управляющим сигналом, поступившим на их адресные входы, выделяют на выходы 11.1, …, 11.d устройства значения булевых функций в следующем порядке ƒ1(x), …, ƒd(х), где управляющий сигнал формируется в результате подачи групп значений адресов информационных разрядов с выходов блоков 2.1, …, 2.2k памяти на информационные входы многоканального мультиплексора 4, где с выходов блока 2.1 подаются значения адресов информационных разрядов для разложения на первый вход многоканального мультиплексора 4, с выходов блока 2.2 подаются значения адресов информационных разрядов для разложения на второй вход многоканального мультиплексора 4 и так далее, с выходов блока 2.2k подаются коэффициенты для разложения на 2k-й вход многоканального мультиплексора 4, который в свою очередь в соответствии со значениями переменных разложения, подаваемыми на его адресные входы с k первых выходов коммутатора 1, выбирает группу значений адресов информационных разрядов и передает на адресные входы мультиплексоров 7.1, …, 7.d.

Предлагаемое устройство имеет глубину в 5 ступеней преобразования: 1-я ступень - коммутатор, 2-я ступень - 2k блоков памяти хранения групп коэффициентов и 2k блоков памяти хранения адресов информационных разрядов, 3-я ступень - (n-k+1) мультиплексоров выделения информационного разряда и многоканальный мультиплексор, 4-я ступень - многоместный сумматор, 5-я ступень - d мультиплексоров выделения информационного разряда, прототип имеет такую же глубину: 1-я ступень - коммутатор, 2-я ступень - блок конъюнкций, 3-я ступень - 2k блоков памяти, 4-я ступень - 2n-k мультиплексоров, 5-я ступень - многоместный сумматор, однако наиболее существенный вклад в длительность преобразования как предлагаемого устройства, так и прототипа вносит многоместный арифметический сумматор, длительность его функционирования определяется глубиной его функционирования, которая определяется формулой:

где t - количество входов сумматора. Учитывая то, что в устройстве-прототипе сумматор содержит 2n-k входов, а в предлагаемом устройстве (n-k+1) входов, то соответственно глубина схемы в первом и во втором случаях составит: n-k ступеней и ступеней. Таким образом глубина сумматора, используемого в предлагаемом устройстве в

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

Таблица 1
Значения выигрыша по сравнению с сумматором прототипа
n-k 2 3 4 5 6 7 8 9 10 11
Квыигр 1 1.5 1.333 1.667 2 2.333 2 2.25 2.5 2.75

В целом выигрыш в быстродействии предлагаемого устройства составит:

учитывая, что , формула (17) примет вид:

Более высокое быстродействие предлагаемого устройства выгодно отличает его от прототипа.

Источники информации

1. Малюгин В.Д. Параллельные логические вычисления посредством арифметических полиномов / [Текст] - М.: Наука. Физматлит, 1997. - С.154-155 (аналог).

2. Пат. 2373564 Российская Федерация, МПК8 G06F 7/57. Модулярный вычислитель систем булевых функций [Текст] / Щербаков А.В.; заявитель и патентообладатель Щербаков А.В. - №2007141074/09; заявл. 06.11.2007; опубл. 20.05.2009, Бюл. №32. - 9 с.: ил. (прототип).

3. Малюгин В.Д. Реализация булевых функций арифметическими полиномами / [Текст]. Автоматика и телемеханика. - 1982. - №4 (мат. аппарат).

Арифметический вычислитель систем булевых функций, содержащий n входов подачи булевых переменных, коммутатор, 2k блоков памяти хранения групп коэффициентов, (n-k+1) мультиплексоров выделения группы коэффициентов, многоместный сумматор, d выходов выдачи значений булевых функций, причем информационные входы коммутатора являются входами подачи булевых переменных устройства, а выходы с (k+1)-го по n-й подключены к информационным входам каждого из 2k блоков памяти хранения коэффициентов, выходы которых подключены к информационным входам каждого из (n-k+1) мультиплексоров выбора группы коэффициентов, где i-й выход j-го блока памяти подключен к j-му входу i-го мультиплексора (i=1, 2, …, n-k+1; j=1, 2, …, 2k), управляющие входы каждого из которых соединены с k первыми выходами коммутатора, а выходы подключены к многоместному сумматору, отличающийся тем, что для уменьшения длительности вычислений введены d мультиплексоров выделения информационного разряда, многоканальный мультиплексор, 2k блоков памяти хранения адресов информационных разрядов, управляющий вход подачи сигнала выбора реализуемой системы булевых функций и управляющий вход подачи сигнала выбора булевых переменных разложения, который является управляющим входом коммутатора, а управляющий вход подачи сигнала выбора реализуемой булевой функции устройства является управляющим входом каждого из 2k блоков памяти хранения коэффициентов и каждого из 2k блоков памяти хранения адресов информационных разрядов, выходы каждого из которых подключены к информационным входам многоканального мультиплексора, управляющие входы которого соединены с первыми k выходами коммутатора, а выходы с 1-го по d-й подключены к адресным входам d мультиплексоров выделения информационного разряда соответственно, информационные входы каждого из которых соединены с выходами многоместного сумматора, а выходы являются выходами выдачи значений булевых функций устройства.