Модулярный вычислитель систем булевых функций

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

2^n-k мультиплексоров, сумматор. 2 ил.

 

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

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

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

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

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

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

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

Структурная схема предлагаемого СУЛВ представлена на фиг.1. Пусть дана система булевых функций (СБФ): f₁(x), f₂(х), …, f_d(х) от n булевых переменных x=x₁,x₂,…,x_n (x_i∈{0,1}, i=1,2,…,n):

где F(х) - значение, принимаемое d-выходной БФ.

Известно, что СБФ (1) можно однозначно представить в числовой нормальной форме (ЧНФ):

где α₀,α₁,α₂,…α_n∈Z, Z - множество целых чисел, F(x) при представлении в двоичной системе счисления интерпретируется как результат вычисления СБФ.

Пример 1. Пусть СБФ (1) задана формулами:

тогда ЧНФ (2) будет иметь вид:

присвоив булевым переменным значения x₁=1, x₂=1, x₃=1, x₄=1, получим

результат вычисления СБФ (3)

Так как число 9 в двоичной системе счисления запишется как (01001)₂, то f₁(x)=1, f₂(x)=0, f₃(x)=0, f₄(x)=1, f₅(x)=0 (значения f₁(x) находится в младшем разряде (справа), а f₅(x) -в старшем разряде слева)).

Известно, что СБФ (1) может быть единственным образом представлена на основе модулярной ЧНФ (2) в виде:

где d - количество реализуемых булевых функций, ,

(mod 2^d) - указывает на то, что вычисление (5) выполняется в конечном кольце

- получение наименьшего неотрицательного вычета от x по модулю 2^d.

Пример 2. Пусть дана ЧНФ (4) СБФ (3), тогда модулярная форма (5) будет иметь вид:

присвоив булевым переменным значения: x₁=1, x₂=1, x₃=1, x₄=1, получим:

- результат вычисления СБФ (3).

Известно, что любую СБФ, зависящую от n аргументов, можно разложить по переменным и представить в виде:

где

Обобщим (7) для произвольного количества переменных разложения, получим:

где - степень аргументов x_k, p_k - двоичная переменная величина такая, что

Придав фиксированные значения переменным разложения: 0…0; 0…1; …; 1…1, разложение (9) можно записать в виде

Пример 3. Пусть дана СБФ (3). Разложим каждую функцию по переменным x₁, x₃. Тогда СБФ будет иметь вид:

Объединим подфункции, полученные в результате разложения, в системы и присвоим булевым переменным значения x₂=1, x₄=1, представим каждую систему подфункций в ЧНФ:

а затем в модулярной ЧНФ:

Результат вычисления соответствует результату вычисления F(x).

Таким образом, для нахождения искомого результата достаточно вычислить только одну систему подфункций, представленную модулярной ЧНФ в соответствии с координатами, определяемыми значениями переменных разложения. В данном примере координатами системы подфункций являются значения переменных разложения x₁=1, x₃=1.

Предлагаемое устройство СУЛВ включает: входы 6.1,…,6.n подачи значений булевых переменных, коммутатор 1, блок 2 конъюнкций, блоки 3.1,…,3.2^k памяти, мультиплексоры 4.1,…,4.2^n-k, сумматор 5, выходы 7.1,…,7d выдачи значений булевых функций: f_d(x),…,f₁(x).

Входы 6.1,…,6.n подачи значений булевых переменных x₁,x₂,…,x_n, которые являются входами устройства, являются и входами коммутатора 1, выходы (k+1)…n которого подключены ко входам блока 2 конъюнкций, выходы которого подключены ко входам блоков 3.1,…,3.2^k памяти соответственно, первые выходы блоков 3.1,…,3.2^k памяти подключены к информационным входам мультиплексора 4.1, вторые выходы блоков 3.1,…,3.2^k памяти подключены к информационным входам мультиплексора 4.2 и так далее, (n-k)-e выходы блоков 3.1,…,3.2^k памяти подключены к информационным входам мультиплексора 4.2^n-k соответственно, выходы мультиплексоров 4.1,…,4.2^n-k подключены ко входам многоместного сумматора 5, а первый, второй и так далее, k-й адресные входы мультиплексоров 4.1,…,4.2^n-k соединены соответственно с первым, вторым и так далее, k-м выходами коммутатора 1. Выходы 7.1,…,7.d многоместного сумматора 5 являются выходами устройства выдачи значений булевых функций: f_d(x),…,f₁(x). Предлагаемое устройство работает следующим образом.

В исходном состоянии в блоки 3.1,…,3.2^k памяти занесены группы коэффициентов: модулярных ЧНФ (11.1), (11.2),…,(11.2^k) соответственно, полученных в результате разложения (9). В момент времени, соответствующий началу преобразования, на входы 6.1,…,6.n коммутатора 1 поступают значения булевых переменных x₁,x₂,…,x_n. В коммутаторе 1 под воздействием внешних сигналов управления, в соответствии с заранее выполненным разложением (9) из состава поступивших переменных x₁,x₂,…,x_n выделяются переменные разложения x_i1,…,x_ik, которые поступают на адресные входы мультиплексоров 4.1,…,4.2^n-k, а остальные - информационные переменные x_ik+1,…,x_in - подаются далее на входы блока 2 конъюнкций. Блок 2 конъюнкций предназначен для вычисления конъюнкций: x_ik+1; x_ik+2; x_ik+1·x_ik+2;…; x_ik+1·x_ik+2·…·x_in, которые поступают на входы блоков 3.1,…,3.2^k памяти, с первых выходов которых коэффициенты поступают на информационные входы мультиплексора 4.1, со вторых выходов блоков 3.1,…,3.2^k памяти коэффициенты , значения соответствующих конъюнкций которых равны 1, поступают на информационные входы мультиплексора 4.2 и так далее, с (n-k)-x выходов блоков 3.1,…,3,2^k памяти коэффициенты значения соответствующих конъюнкций которых равны 1, поступают на информационные входы мультиплексора 4.2^n-k. Общая задача мультиплексоров 4.1,…,4.2^n-k заключается в том, чтобы в соответствии со значениями булевых переменных x_i1…,x_ik, поступивших на адресные входы и определяющих параметр разложения, подать на входы многоместного сумматора 5 значения коэффициентов одной из подсистем БФ, представленной в модулярной ЧНФ. После преобразований в многоместном сумматоре 5 на выходы устройства поступают вычисленные значения СБФ в следующем порядке: f_d(x), f_d-1(x), …, f₁(x).

Длительность функционирования СВУ - прототипа определяется как:

где T_к - длительность функционирования коммутатора,

T_бк - длительность функционирования блока конъюнкций,

Т_∑прот - длительность функционирования многоместного сумматора прототипа,

T_∑прот=Δτ_ЛЭ4dlog₂2ⁿ = Δτ_ЛЭ4dn, где Δτ_ЛЭ - время задержки одного двухвходового логического элемента (ЛЭ), n - количество булевых переменных, d - количество реализуемых булевых функций.

Длительность функционирования предлагаемого СУЛВ определяется как:

T_{∑заявл} - длительность функционирования многоместного сумматора предлагаемого СУЛВ,

T_{∑заявл}=Δτ_ЛЭ4dlog₂2^n-k=Δτ_ЛЭ4d(n-k), где k - количество булевых переменных разложения,

T_MS - длительность функционирования мультиплексора,

T_MS=Δτ_ЛЭ(k+log₂(k+1)).

Из (11) и (12) видно, что общей и у прототипа, и у предлагаемого СУЛВ является сумма длительностей T_к+T_бк=T_к,бк. Длительность функционирования предлагаемого устройства отличается от длительности функционирования прототипа уменьшенной длительностью функционирования T_{∑заявл} сумматора 5. При допущении, что коммутатор 1 конструктивно представляет схему последовательно соединенных мультиплексора и демультиплексора, а блок 2 конъюнкций построен по принципу, представленному на фиг.2, коэффициент выигрыша в уменьшении длительности вычислений предлагаемого СУЛВ по отношению к прототипу с учетом длительности функционирования T_MS мультиплексора будет определяться выражением:

Например, при значениях: d=10, n=16, k=1 минимальный выигрыш в уменьшении длительности вычислений предлагаемого СУЛВ по отношению к прототипу составит 6 процентов, при значениях: d=10, n=16, k=4 выигрыш составит 24 процента, при значениях: d=10, n=16, k=8 выигрыш составит 48 процентов. Получаемый выигрыш достигается за счет обеспечения замены вычисления всей СБФ вычислением только одной системы подфункций, выбранной из состава разложения.

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