МОДУЛЯРНЫЙ ВЫЧИСЛИТЕЛЬ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ Российский патент 2009 года по МПК G06F7/57 

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

Известно специализированное вычислительное устройство, включающее в себя сумматор, выход которого подключен к второму входу регистра результата, регистр для хранения булевых переменных, выход которого подключен к блоку конъюнкций, регистры для фиксации очередных строк матриц, описывающих структуру соответствующей конъюнкции, выходы которых подключены также к блоку конъюнкций, выход которого подключен к третьему входу регистра результата, выход которого является шиной выдачи результата вычислений (Малюгин В.Д. Параллельные логические вычисления посредством арифметических полиномов. - М.: Наука. Физматлит, 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 процентов. Получаемый выигрыш достигается за счет обеспечения замены вычисления всей СБФ вычислением только одной системы подфункций, выбранной из состава разложения.

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

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

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