Учебное пособие 800647

табл. 7 подставить значения компонент fi и произвести в каждом столбце сложение по модулю 2 всех перечисленных в нем значений fi.

Для функции F(a,b,c)=(10100110) имеем следующий полином Жегалкина: P(a,b,c) 1 c a ab

Для построения табл. 7 существенно следующее. Все монотонные конъюнкции полинома Жегалкина общего вида пронумерованы возрастающими двоичными кодами, совпадающими с двоичными наборами переменных. При этом за каждым двоичным разрядом кодов монотонных конъюнкций закрепляются те же переменные, что и в двоичных наборах

переменных. Например, набору переменных 101 (a b c) соот-

ветствует монотонная конъюнкция 101 (ac), состоящая только из тех переменных, которые равны единичным значениям в соответствующем наборе переменных. Двоичный код монотонной конъюнкции однозначно определяет так же и соответствующую компоненту gi, где i – десятичный номер компоненты, представляемый в двоичном коде и равный двоичному коду монотонной конъюнкции.

Анализ табл. 7 позволяет выявить следующую алгоритмическую закономерность: в определении значения компоненты g с определенным номером i, представленным двоичным кодом m(gi), участвуют только те компоненты f, номера которых j, представленные двоичными кодами s(fj), содержат те же нулевые значения, что и двоичный код m(gi). Формализуем данную алгоритмическую закономерность алгоритмом А1.

Алгоритм А1:

1.Ввод количества (n) переменных xk функции F;

2.Ввод вектора F(x0 , x1,...,xn-1 ) (f0 , f1,...,f2n 1 );

3.Формирование вектора

G(x0, x1,...,xn-1) (g0,g1,...,gi ,...,g2n 1) и обнуление его компо-

нент;

19

4.Подготовка текущих переменных i=0, j=0, s=0, r=0 (i, j, s, r – целые неотрицательные n-разрядные двоичные числа);

5.s: i; j:=i ;

6.r := j&s;

7.Если r = 0, то gi gi fj ;

8.gi gi 0; j=j-1;

9.Если j ≥0, то перейти на пункт 6;

10.i=i+1;

11.Если i <2n, то перейти на пункт 5;

12.Конец алгоритма, вектор

G(x0, x1,...,xn-1) (g0,g1,...,gi ,...,g2n 1) сформирован.

Врезультате выполнения алгоритма А1 каждый компо-

нент вектора G может быть равен 0 или 1 и однозначно соответствует некоторой монотонной конъюнкции Kiм, являющейся членом полинома Жегалкина общего вида.

Валгоритме А1 учитывается следующая логическая закономерность: в определении значения компоненты g с определенным номером i, представленным двоичным кодом m(gi), участвуют только те компоненты f, номера которых j, представленные двоичными кодами s(fj), содержат те же нулевые значения, что и двоичный код m(gi).

Вычислительная сложность алгоритма А1 преобразования принципиально может быть уменьшена, если удастся найти такое логико-арифметическое преобразование кода индекса j, которое бы позволяло непосредственно вычислять двоичный код номера следующего компонента вектора F, участвующего в определении компонента gi. Рассмотрим алгоритм А2.

Алгоритм А2:

1.Ввод количества (n) переменных xk функции F;

2.Ввод вектора F(x0, x1,...,xn-1) (f0,f1,...,f2n 1);

20

3. Формирование вектора

G(x0, x1,...,xn-1) (g0,g1,...,gi ,...,g2n 1) и обнуление его компо-

нент;

4.Подготовка текущих переменных i=0, j=0, s=0, r=0 (i, j, s, r – целые неотрицательные n-разрядные двоичные числа);

5.s: i; j:=i;

6.r := s;

7.gi gi fj ;

8.Если r =2n-1, то перейти на пункт 12;

9.r:=r+1;

10. r:=r v s; j r;

11.Если j ≥0, то перейти на пункт 7;

12.i=i+1;

13.Если i <2n, то перейти на пункт 5;

14.Конец алгоритма, вектор

G(x0 , x1,...,xn-1) (g0,g1,..., gi ,..., g2n 1) сформирован.

В предложенном алгоритме А2 с помощью операций

r:=r+1, r:=r s, j r выполняется найденное логико-

арифметическое преобразование, обеспечивающее непосредственное вычисление индекса следующего компонента fj, значение которого должно суммироваться для нахождения значения компонента gi.

Возможно ли дальнейшее снижение вычислительной сложности алгоритмов преобразования на основе метода неопределенных коэффициентов? Преобразуем систему уравнений (29) – (36) к следующему виду:

21

2.Ввод вектора F(x0, x1,...,xn-1) (f0 ,f1,..., f2n 1);

3.Формирование вектора G(x0, x1,...,xn-1) (g0,g1,...,gi ,...,g2n 1)

иобнуление его компонент;

4.Подготовка текущих переменных i=0, j=0, s=0, r=0, m=0 (i, j, s, r, m – целые неотрицательные n-разрядные двоичные числа);

5.s: i; j:=i ;

6.r := s;

7.gi gi fj ;

8.если r=2n-1, то п. 14

9.r:=r+1; r:=r s; j r;

10.Если i =0, то перейти на пункт 14;

11.Если j <2m, то перейти на пункт 13;

12.Перейти на пункт 7;

13.j:=i - 2m; gi = gi gj;

14.i:=i+1; m = int(log2(i))

15.Если i <2n, то перейти на пункт 5;

ЗАДАНИЕ: изучить представленные в лабораторной работе алгоритмы А1-А3 и представить их в виде схем алгоритмов. Оценить возможность распараллеливания алгоритмов А1-А3 и предложить вариант программно-аппаратных средств, необходимых для их параллельной реализации. Дать оценку параллельной и последовательной реализации алгоритмов.

Лабораторная работа №3

АЛГОРИТМ ПОЛИНОМИАЛЬНОГО ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ НА ОСНОВЕ ЧПНФ

23

ЦЕЛЬ: изучение метода ЧПНФ и алгоритма полиномиального преобразования n – аргументных булевых функций на его основе.

Существо метода полиномиального преобразования булевых функций, носящего название метод частных полиномиальных форм (ЧПНФ), подробно изложено в [10].

При осуществлении преобразований данным методом формирование ПНФ функции осуществляется путем последовательного преобразования каждого минтерма СДНФ БФ в частные ПНФ (ЧПНФ) и на основе их последующей суперпозиции – формировании окончательной ПНФ БФ – полинома Жегалкина. Рассмотрим данный метод на примере.

Пусть логическая функция f(p, q, r) задана таблицей истинности, представленной в табл. 9, индексом i обозначен номер набора значений логических переменных.

f0 (0,0,0) pqr (1 p)(1 q)(1 r)

1 p q r pq qr pr pqr B0

24

f1(0,0,1) pqr (1 p)(1 q)r

r qr pr pqr B1

f2 (0,1,0) pqr (1 p)q(1 r)

q pq qr pqr B2

f3 (0,1,1) pqr (1 p)qr qr pqr B3 f4 (1,0,0) pqr p(1 q)(1 r)

p pq pr pqr B4

f5 (1,0,1) pqr p(1 q)r pr pqr B5

f6 (1,1,0) pqr pq(1 r) pq pqr B6 f7 (1,1,1) pqr B7

Сведем полученные данные в табл. 10.

Таблица 10

В табл. 10 в первом столбце перечислены все возможные минтермы функции f(p, q, r) – Ki, а в первой строке указаны все возможные члены ПНФ той же функции. В остальных строках метками «1» отмечены те члены ПНФ, которые входят в частные ПНФ в соответствии с перечисленными выше ЧПНФ. Жирным шрифтом выделены те Bj, которые соответствуют единичным значениям функции f(p, q, r).

25

Просуммируем по модулю 2 в символьном виде те ЧПНФ, которые соответствуют выделенным в табл. 10 минтермам логической функции. В результате, после раскрытия скобок и приведения подобных членов, получим:

(1 r q qr p pr pq pqr)

(r qr pr pqr)

(45)

(q qr pq pqr) (qr pqr)

(1 qr p pq)

Тождественный (45) результат с использованием данных табл. 10 может быть получен путем суммирования по модулю 2 двоичных векторов Вj, соответствующих выделенным минтермам, что иллюстрируется табл. 11.

Таблица 11

26

хранения всей таблицы истинности логической функции, для формирования ПНФ достаточно иметь только таблицу минтермов данной функции.

На рис. 2 представлен алгоритм А4 полиномиального преобразования БФ на основе ЧПНФ. Исходными данными для алгоритма А4 являются: n – число аргументов БФ, вектор E размерности 2n, содержащий значения таблицы истинности БФ.

28