МОДУЛЯРНЫЙ ВЫЧИСЛИТЕЛЬ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ
MODULAR CALCULATOR OF BOOLEAN FUNCTION SYSTEMS

Предлагаемое устройство относится к вычислительной технике и может быть использовано как специализированный вычислитель - универсальный в классе логических вычислений.
Известно специализированное вычислительное устройство, включающее в себя сумматор, выход которого подключен к второму входу регистра результата, регистр для хранения булевых переменных, выход которого подключен к блоку конъюнкций, регистры для фиксации очередных строк матриц, описывающих структуру соответствующей конъюнкции, выходы которых подключены также к блоку конъюнкций, выход которого подключен к третьему входу регистра результата, выход которого является шиной выдачи результата вычислений (Малюгин В.Д. Параллельные логические вычисления посредством арифметических полиномов. - М.: Наука. Физматлит, 1997. - С.156-157).
Недостаток известного устройства - большая длительность вычислений.
Наиболее близким по сущности технического решения к заявляемому устройству является специализированное вычислительное устройство, содержащее блок конъюнкций, входы которого являются шиной подачи значений булевых переменных, выходы которого подключены к блоку памяти, выходы которого подключены к входам коммутатора, выходы которого подключены к многоместному сумматору, выходы которого являются выходами устройства выдачи результата вычислений (Малюгин В.Д. Параллельные логические вычисления посредством арифметических полиномов. - М.: Наука. Физматлит, 1997. - С.154-155).
Недостаток известного устройства - большая длительность вычислений.
Цель изобретения - уменьшение длительности вычислений.
k
n-k
k
n-k
Поставленная цель достигается тем, что в специализированное устройство для логических вычислений (СУЛВ), содержащее коммутатор, входы которого являются входами устройства подачи n булевых переменных, блок конъюнкций, выходы которого подключены к первому блоку памяти, многоместный сумматор, выходы которого являются выходами устройства выдачи значений булевых функций, с целью уменьшения длительности вычислений введены 2-1 блоков памяти, где k - количество булевых переменных разложения, 2 мультиплексоров, при этом входы (k+1)…n коммутатора подключены ко входам блока конъюнкций, выходы которого подключены ко входам второго, третьего и так далее, 2-го блоков памяти соответственно, первые выходы блоков памяти подключены к информационным входам первого мультиплексора, вторые выходы блоков памяти подключены к информационным входам второго мультиплексора и так далее, (n-k)-е выходы блоков памяти подключены к информационным входам 2-го мультиплексора соответственно, выходы мультиплексоров подключены ко входам многоместного сумматора, а первый, второй и так далее, k-й адресные входы мультиплексоров соединены соответственно с первым, вторым и так далее, k-м выходами коммутатора.
1
2
d
1
2
n
i
Структурная схема предлагаемого СУЛВ представлена на фиг.1. Пусть дана система булевых функций (СБФ): f(x), f(х), …, f(х) от n булевых переменных x=x,x,…,x (x∈{0,1}, i=1,2,…,n):
где F(х) - значение, принимаемое d-выходной БФ.
Известно, что СБФ (1) можно однозначно представить в числовой нормальной форме (ЧНФ):
0
1
2
n
где α,α,α,…α∈Z, Z - множество целых чисел, F(x) при представлении в двоичной системе счисления интерпретируется как результат вычисления СБФ.
Пример 1. Пусть СБФ (1) задана формулами:
тогда ЧНФ (2) будет иметь вид:
1
2
3
4
присвоив булевым переменным значения x=1, x=1, x=1, x=1, получим
результат вычисления СБФ (3)
2
1
2
3
4
5
1
5
Так как число 9 в двоичной системе счисления запишется как (01001), то f(x)=1, f(x)=0, f(x)=0, f(x)=1, f(x)=0 (значения f(x) находится в младшем разряде (справа), а f(x) -в старшем разряде слева)).
Известно, что СБФ (1) может быть единственным образом представлена на основе модулярной ЧНФ (2) в виде:
где d - количество реализуемых булевых функций, ,
d
(mod 2) - указывает на то, что вычисление (5) выполняется в конечном кольце
d
- получение наименьшего неотрицательного вычета от x по модулю 2.
Пример 2. Пусть дана ЧНФ (4) СБФ (3), тогда модулярная форма (5) будет иметь вид:
1
2
3
4
присвоив булевым переменным значения: x=1, x=1, x=1, x=1, получим:
- результат вычисления СБФ (3).
Известно, что любую СБФ, зависящую от n аргументов, можно разложить по переменным и представить в виде:
где
Обобщим (7) для произвольного количества переменных разложения, получим:
k
k
где  - степень аргументов x, p - двоичная  переменная величина такая, что
Придав фиксированные значения переменным разложения: 0…0; 0…1; …; 1…1, разложение (9) можно записать в виде
1
3
Пример 3. Пусть дана СБФ (3). Разложим каждую функцию по переменным x, x. Тогда СБФ будет иметь вид:
2
4
Объединим подфункции, полученные в результате разложения, в системы  и присвоим булевым переменным значения x=1, x=1, представим каждую систему подфункций в ЧНФ:
а затем в модулярной ЧНФ:
Результат вычисления  соответствует результату вычисления F(x).
1
3
Таким образом, для нахождения искомого результата достаточно вычислить только одну систему подфункций, представленную модулярной ЧНФ в соответствии с координатами, определяемыми значениями переменных разложения. В данном примере координатами системы подфункций являются значения переменных разложения x=1, x=1.
k
n-k
d
1
Предлагаемое устройство СУЛВ включает: входы 6.1,…,6.n подачи значений булевых переменных, коммутатор 1, блок 2 конъюнкций, блоки 3.1,…,3.2 памяти, мультиплексоры 4.1,…,4.2, сумматор 5, выходы 7.1,…,7d выдачи значений булевых функций: f(x),…,f(x).
1
2
n
d
1
k
k
k
k
n-k
n-k
n-k
Входы 6.1,…,6.n подачи значений булевых переменных x,x,…,x, которые являются входами устройства, являются и входами коммутатора 1, выходы (k+1)…n которого подключены ко входам блока 2 конъюнкций, выходы которого подключены ко входам блоков 3.1,…,3.2 памяти соответственно, первые выходы блоков 3.1,…,3.2 памяти подключены к информационным входам мультиплексора 4.1, вторые выходы блоков 3.1,…,3.2 памяти подключены к информационным входам мультиплексора 4.2 и так далее, (n-k)-e выходы блоков 3.1,…,3.2 памяти подключены к информационным входам мультиплексора 4.2 соответственно, выходы мультиплексоров 4.1,…,4.2 подключены ко входам многоместного сумматора 5, а первый, второй и так далее, k-й адресные входы мультиплексоров 4.1,…,4.2 соединены соответственно с первым, вторым и так далее, k-м выходами коммутатора 1. Выходы 7.1,…,7.d многоместного сумматора 5 являются выходами устройства выдачи значений булевых функций: f(x),…,f(x). Предлагаемое устройство работает следующим образом.
k
k
n-k
k
k
k
n-k
n-k
1
2
n
1
2
n
i1
ik
ik+1
in
ik+1
ik+2
ik+1
ik+2
ik+1
ik+2
in
i1
ik
d
d-1
1
В исходном состоянии в блоки 3.1,…,3.2 памяти занесены группы коэффициентов:  модулярных ЧНФ (11.1), (11.2),…,(11.2) соответственно, полученных в результате разложения (9). В момент времени, соответствующий началу преобразования, на входы 6.1,…,6.n коммутатора 1 поступают значения булевых переменных x,x,…,x. В коммутаторе 1 под воздействием внешних сигналов управления, в соответствии с заранее выполненным разложением (9) из состава поступивших переменных x,x,…,x выделяются переменные разложения x,…,x, которые поступают на адресные входы мультиплексоров 4.1,…,4.2, а остальные - информационные переменные x,…,x - подаются далее на входы блока 2 конъюнкций. Блок 2 конъюнкций предназначен для вычисления конъюнкций: x; x; x·x;…; x·x·…·x, которые поступают на входы блоков 3.1,…,3.2 памяти, с первых выходов которых коэффициенты  поступают на информационные входы мультиплексора 4.1, со вторых выходов блоков 3.1,…,3.2 памяти коэффициенты , значения соответствующих конъюнкций которых равны 1, поступают на информационные входы мультиплексора 4.2 и так далее, с (n-k)-x выходов блоков 3.1,…,3,2 памяти коэффициенты  значения соответствующих конъюнкций которых равны 1, поступают на информационные входы мультиплексора 4.2. Общая задача мультиплексоров 4.1,…,4.2 заключается в том, чтобы в соответствии со значениями булевых переменных x…,x, поступивших на адресные входы и определяющих параметр разложения, подать на входы многоместного сумматора 5 значения коэффициентов  одной из подсистем БФ, представленной в модулярной ЧНФ. После преобразований в многоместном сумматоре 5 на выходы устройства поступают вычисленные значения СБФ в следующем порядке: f(x), f(x), …, f(x).
Длительность функционирования СВУ - прототипа определяется как:
к
где T - длительность функционирования коммутатора,
бк
T - длительность функционирования блока конъюнкций,
∑прот
Т - длительность функционирования многоместного сумматора прототипа,
∑прот
ЛЭ
2
ЛЭ
ЛЭ
n
T=Δτ4dlog2= Δτ4dn, где Δτ - время задержки одного двухвходового логического элемента (ЛЭ), n - количество булевых переменных, d - количество реализуемых булевых функций.
Длительность функционирования предлагаемого СУЛВ определяется как:
∑заявл
T - длительность функционирования многоместного сумматора предлагаемого СУЛВ,
∑заявл
ЛЭ
2
ЛЭ
n-k
T=Δτ4dlog2=Δτ4d(n-k), где k - количество булевых переменных разложения,
MS
T - длительность функционирования мультиплексора,
MS
ЛЭ
2
T=Δτ(k+log(k+1)).
к
бк
к,бк
∑заявл
MS
Из (11) и (12) видно, что общей и у прототипа, и у предлагаемого СУЛВ является сумма длительностей T+T=T. Длительность функционирования предлагаемого устройства отличается от длительности функционирования прототипа уменьшенной длительностью функционирования T сумматора 5. При допущении, что коммутатор 1 конструктивно представляет схему последовательно соединенных мультиплексора и демультиплексора, а блок 2 конъюнкций построен по принципу, представленному на фиг.2, коэффициент выигрыша в уменьшении длительности вычислений предлагаемого СУЛВ по отношению к прототипу с учетом длительности функционирования T мультиплексора будет определяться выражением:
Например, при значениях: d=10, n=16, k=1 минимальный выигрыш в уменьшении длительности вычислений предлагаемого СУЛВ по отношению к прототипу составит 6 процентов, при значениях: d=10, n=16, k=4 выигрыш составит 24 процента, при значениях: d=10, n=16, k=8 выигрыш составит 48 процентов. Получаемый выигрыш достигается за счет обеспечения замены вычисления всей СБФ вычислением только одной системы подфункций, выбранной из состава разложения.