96890

Разработка сумматора–умножителя

Курсовая

Информатика, кибернетика и программирование

Арифметические операции сложения двоично-четверичных чисел с разными знаками в дополнительных кодах и умножения на 2 разряда множителя в прямых кодах должны выполняться одним цифровым устройством, именуемым сумматор-умножитель. Учитывая то, что суммирующие узлы обязательно входят в состав умножителя...

Русский

2015-10-11

3.86 MB

8 чел.

Министерство образования Республики Беларусь

Учреждение образования

Белорусский государственный университет информатики и радиоэлектроники

Кафедра электронных вычислительных машин

Пояснительная записка к типовому расчету по дисциплине «Арифметические и логические основы вычислительной техники»

Тема: Разработка сумматора-умножителя

Выполнил: Германенко И.И.                                                                                         

Студент гр. 480562                                                              

MRY

Проверила:

                                                                                                       Лукьянова  И.В.

Минск 2015

Исходные данные:

Исходные сомножители:  = 81,92;  = 44,35;

Алгоритм умножения: Г;

Метод умножения: умножение закодированного двоично-четверичного множимого на 2 разряда двоичного множителя одновременно в прямых кодах;

Варианты кодирования четверичных цифр двоичными кодами:

= 10;  = 01;  = 11;  = 00;

Тип синтезируемого умножителя: структурные схемы приведены для  умножителя 2-го типа (ОЧС, ОЧУС, аккумулятор).

Метод минимизации ОЧС: карты Карно-Вейча.

Метод минимизации ОЧУС: Алгоритм Квайна-МакКласке, карты Карно-Вейча.

Функционально полный логический базис для схемы ОЧС (А4):

Логический базис для реализации ОЧС:

Функционально полный логический базис для схемы ОЧУС (А7):

Логический базис для реализации ОЧУС:

Арифметические операции сложения двоично-четверичных чисел с разными знаками в дополнительных кодах и умножения на 2 разряда множителя в прямых кодах должны выполняться одним цифровым устройством, именуемым сумматор-умножитель. Учитывая то, что суммирующие узлы обязательно входят в состав умножителя, начнем синтез с разработки алгоритма умножения.


Разработка алгоритма умножения

Перевод сомножителей из десятичной системы счисления в четверичную:

Множимое:

*

0,92

    4

*

3,68

    4

*

2,72

    4

2,88

=1101,322

=01011001,001111

Множитель:

*

0,35

    4

*

1,40

    4

*

1,60

    4

2,40

=230,112

=110010,010111

Запишем сомножители в форме с плавающей запятой в прямом коде:

Мн = 0,010110010011   = 0.0110   (закодирован по заданию)

Мт = 0,01010001111010   = 0.0011   (закодирован традиционно)

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

= 0.0100   

+4

= 0.0011   

+3

P   = 0.0111

+7

Результат закодирован в соответствии с заданием на кодировку множимого.

Знак произведения определяется суммой по модулю двух знаков сомножителей: зн Мн  зн Мт = 0 + 0 = 0

Для умножения мантисс необходимо предварительно преобразовать множитель, чтобы исключить диаду 11 (34), заменив ее на триаду 1 и диаду 10 (24).

Преобразованный множитель имеет вид:

=1,

Мн = 0,110132   2Мн = 0,220330

= 3,223202  = 3,113010

Умножение по алгоритму Г

Четверичная с/с

Двоично-четверичная с/с

Комментарии

0

000000

0

10 10 10 10 10 10

0

110132

0

01 01 10 01 00 11

=Мн*

0

110132

0

01 01 10 01 00 11

3

322320

2

1

00 11 11 00 11 10

11

=*

0

033112

2

0

10 00 00 01 01 11

11

3

332232

02

1

00 00 11 11 00 11

10 11

=*

0

032010

22

0

10 00 11 10 01 10

11 11

0

000000

000

0

10 10 10 10 10 10

10 10 10

=0*Мн*

0

032010

220

0

10 00 11 10 01 10

11 11 10

0

000011

0132

0

10 10 10 10 01 01

10 01 00 11

=*

0

032021

2332

0

10 00 11 10 11 01

11 00 00 11

0

000002

20330

0

10 10 10 10 10 11

11 10 00 00 10

=*

0

032030

10310

0

10 00 11 10 00 10

01 10 00 01 10

3

333333

113010

1

00 00 00 00 00 00

01 01 00 10 01 00

=*

0

032023

222110

0

10 00 11 10 11 00

11 11 11 01 01 10

После окончания умножения необходимо оценить погрешность вычислений. Для этого полученное произведение = 0,032023222110 приводится к нулевому порядку (* 7), а затем переводится в десятичную систему счисления:

= 320232,22110

= 3630,64453125

Результат прямого перемножения операндов дает следующее значение:

= 3633,15185547

Абсолютная погрешность:

Δ = 3633,15185547 - 3630,64453125 = 2,50732422

δ; δ =

Эта погрешность получена за счет приближенного перевода из десятичной системы счисления в четверичную обоих сомножителей, а также за счет округления полученного результата произведения.

Синтез структуры сумматора-умножителя 2го типа

Структурная схема сумматора-умножителя 2го типа для алгоритма умножения “Г” приведена на рис.2.

Если устройство работает как сумматор, то оба слагаемых последовательно (за 2 такта) заносятся в регистр множимого, а на управляющий вход формирователя дополнительного кода F2 поступает «1». Необходимо обеспечить выполнение алгоритма сложения чисел, представленных в форме с плавающей запятой, базируясь на схеме умножителя, реализующего заданный алгоритм умножения. Первое слагаемое переписывается в регистр результата под действием управляющих сигналов, поступающих на входы «h» всех ОЧУС (рис. 5). Если на вход «h» поступает «0», то ОЧУС перемножает разряды Мн и Мт и добавляет к полученному результату перенос из предыдущего ОЧУС.

В ОЧС первое слагаемое складывается с нулем, записанным в регистре результата, и переписывается без изменений в регистр результата. На втором такте второе слагаемое из регистра множимого через цепочку ОЧУС попадает на входы ОЧС и складывается с первым слагаемым, хранящимся в регистре результата. Сумма хранится в регистре результата. Разрядность регистра результата должна быть на единицу больше, чем разрядность исходных слагаемых, чтобы предусмотреть возможность возникновения при суммировании переноса.

Если устройство работает как умножитель, то множимое и множитель помещаются в соответствующие регистры, а на управляющий вход ФДК F2 поступает «0». Диада множителя поступает на входы преобразователя множителя. Единица переноса в следующую диаду, если она возникает, должна быть добавлена к следующей диаде множителя (выход 1 ПМ). В регистре множителя после каждого такта умножения содержимое сдвигается на 2 двоичных разряда, и в конце умножения регистр обнуляется. Это позволяет использовать регистр множителя для хранения младших разрядов произведения при умножении по алгоритму «Г». Выход 2 ПМ переходит в единичное состояние, если текущая диада содержит отрицание (). В этом случае инициализируется управляющий вход F1 формирователя дополнительного кода, и на выходах ФДК формируется дополнительный код множимого с обратным знаком (умножение на -1). Принцип работы ФДК в зависимости от управляющих сигналов отражен в табл.2.

На выходах 3,4 ПМ формируются диады преобразованного множителя, которые поступают на входы ОЧУС вместе с диадами множимого (см. рис.2). На трех выходах ОЧУС формируется результат умножения диад Мн ∙ Мт + перенос из предыдущего ОЧУС. Максимальной цифрой в диаде преобразованного множителя является двойка, поэтому перенос, формируемый ОЧУС, может быть только двоичным:

  3     ∙     2    =   1 2.

max      maх       max

Мн       Мт     перенос

Так как на входы ОЧУС из регистра Мт не могут поступить коды «3», в таблице истинности работы ОЧУС будут содержаться 16 безразличных входных наборов.

Частичные произведения, получаемые на выходах ОЧУС, складываются с накапливаемой частичной суммой из регистра результата с помощью цепочки ОЧС (на первом такте выполняется сложение с нулем).

Частичные суммы хранятся в регистре результата и регистре множителя, так как алгоритм умножения «Г» предполагает возможность синхронного сдвига этих регистров. Количество тактов умножения определяется разрядностью Мт.


Разработка функциональных схем основных узлов сумматора-умножителя

Логический синтез одноразрядного четверичного сумматора

ОЧС - это комбинационное устройство, имеющее 5 входов и 3 выхода:

  •  2 разряда одного слагаемого (множимого);
  •  2 разряда второго слагаемого (регистр результата);
  •  вход переноса из младшего ОЧС.

Принцип работы ОЧС описывается с помощью таблицы истинности

Разряды обоих слагаемых закодированы: 0 - 11; 1 - 00; 2 - 01; 3 -10.

Таблица истинности ОЧС.

p

П

Пример

1

1

1

1

0

1

1

1

3+3+0=12

1

1

1

1

1

1

0

0

3+3+1=13

1

1

0

0

0

1

1

0

3+1+0=10

1

1

0

0

1

1

0

1

3+1+1=11

1

1

0

1

0

0

0

0

3+0+0=03

1

1

0

1

1

1

1

0

3+0+1=10

1

1

1

0

0

1

0

1

3+2+0=11

1

1

1

0

1

1

1

1

3+2+1=12

0

0

1

1

0

1

1

0

1+3+0=10

0

0

1

1

1

1

0

1

1+3+1=11

0

0

0

0

0

0

1

1

1+1+0=02

0

0

0

0

1

0

0

0

1+1+1=03

0

0

0

1

0

0

0

1

1+0+0=01

0

0

0

1

1

0

1

1

1+0+1=02

0

0

1

0

0

0

0

0

1+2+0=03

0

0

1

0

1

1

1

0

1+2+1=11

0

1

1

1

0

0

0

0

0+3+0=03

0

1

1

1

1

1

1

0

0+3+1=10

0

1

0

0

0

0

0

1

0+1+0=01

0

1

0

0

1

0

1

1

0+1+1=02

0

1

0

1

0

0

1

0

0+0+0=00

0

1

0

1

1

0

0

1

0+0+1=01

0

1

1

0

0

0

1

1

0+2+0=02

0

1

1

0

1

0

0

0

0+2+1=03

1

0

1

1

0

1

0

1

2+3+0=11

1

0

1

1

1

1

1

1

2+3+1=12

1

0

0

0

0

0

0

0

2+1+0=03

1

0

0

0

1

1

1

0

2+1+1=10

1

0

0

1

0

0

1

1

2+0+0=02

1

0

0

1

1

0

0

0

2+0+1=03

1

0

1

0

0

1

1

0

2+2+0=10

1

0

1

0

1

1

0

1

2+2+1=11

Минимизацию выходов ОЧС П и S1 проведем с помощью карт Вейча, минимизацию  проведем с помощью карт Карно.

Минимизация функции П картами Вейча:

a2

a2

a1

1

1

1

1

1

1

b1

1

1

1

1

1

1

1

1

1

1

b2

b2

p

Минимизировав функцию, получим: 

Минимизация функции  картами Вейча:

a2

a2

a1

1

1

1

1

1

1

1

b1

1

1

1

1

1

1

1

1

b2

b2

p

 

Минимизация функции  картами Карно:

000

001

011

010

110

111

101

100

00

1

1

1

1

01

1

1

1

1

11

1

1

1

1

10

1

1

1

1

Минимизировав функцию, получим:

 

          

 

Логический синтез одноразрядного четверичного умножителя-сумматора

ОЧУС  это комбинационное устройство, имеющее шесть входов (два разряда из регистра множимого, два разряда из регистра множителя, вход переноса и управляющий вход h) и три выхода. Принцип работы ОЧУС представлен с помощью таблицы истинности (табл. 13).

Разряды множителя закодированы: 0 = 00; 1 = 01; 2 = 10; 3 = 11.

Разряды множимого закодированы: 0 = 00; 1 = 11; 2 = 10; 3 = 01.

Управляющий вход h определяет тип операции: 0  умножение закодированных цифр, поступивших на информационные входы, и добавление переноса; 1  вывод на выходы без изменения значения разрядов, поступивших из регистра множимого. В табл. 13 выделено 36 безразличных наборов, так как на входы ОЧУС из разрядов множителя не может поступить код 11, при работе ОЧУС как сумматора на вход переноса не может поступить единица, а при умножении на ноль или единицу на вход переноса также не может поступить единица.

Таблица истинности ОЧУС.

Пер.

Мн.

Мт.

Упр.

Перенос

Результат

Результат операций  в четверичной с/с

h

P

0

0

0

0

0

0

0

1

0

3*0+0=00

0

0

0

0

0

1

0

0

0

Выход-код«03»

0

0

0

0

1

0

0

0

0

3*1+0=03

0

0

0

0

1

1

0

0

0

Выход-код«03»

0

0

0

1

0

0

1

1

1

3*2+0=12

0

0

0

1

0

1

0

0

0

Выход-код«03»

0

0

0

1

1

0

x

x

x

3*3+0=21

0

0

0

1

1

1

x

x

x

Выход-код«03»

0

0

1

0

0

0

0

1

0

1*0+0=00

h

P

Результат

0

0

1

0

0

1

0

0

1

Выход-код«01»

0

0

1

0

1

0

0

0

1

1*1+0=01

0

0

1

0

1

1

0

0

1

Выход-код«01»

0

0

1

1

0

0

0

1

1

1*2+0=02

0

0

1

1

0

1

0

0

1

Выход-код«01»

0

0

1

1

1

0

x

x

x

1*3+0=03

0

0

1

1

1

1

x

x

x

Выход-код«01»

0

1

0

0

0

0

0

1

0

0*0+0=00

0

1

0

0

0

1

0

1

0

Выход-код«00»

0

1

0

0

1

0

0

1

0

0*1+0=00

0

1

0

0

1

1

0

1

0

Выход-код«00»

0

1

0

1

0

0

0

1

0

0*2+0=00

0

1

0

1

0

1

0

1

0

Выход-код«00»

0

1

0

1

1

0

x

x

x

0*3+0=00

0

1

0

1

1

1

x

x

x

Выход-код«00»

0

1

1

0

0

0

0

1

0

2*0+0=00

0

1

1

0

0

1

0

1

1

Выход-код«02»

0

1

1

0

1

0

0

1

1

2*1+0=02

0

1

1

0

1

1

0

1

1

Выход-код«02»

0

1

1

1

0

0

1

1

0

2*2+0=10

0

1

1

1

0

1

0

1

1

Выход-код«02»

0

1

1

1

1

0

x

x

x

2*3+0=12

0

1

1

1

1

1

x

x

x

Выход-код«02»

1

0

0

0

0

0

x

x

x

3*0+1=01

1

0

0

0

0

1

x

x

x

Выход-код«03»

1

0

0

0

1

0

x

x

x

3*1+1=10

1

0

0

0

1

1

x

x

x

Выход-код«03»

1

0

0

1

0

0

1

1

1

3*2+1=13

1

0

0

1

0

1

x

x

x

Выход-код«03»

1

0

0

1

1

0

x

x

x

3*3+1=22

1

0

0

1

1

1

x

x

x

Выход-код«03»

1

0

1

0

0

0

x

x

x

1*0+1=01

1

0

1

0

0

1

x

x

x

Выход-код«01»

1

0

1

0

1

0

x

x

x

1*1+1=02

1

0

1

0

1

1

x

x

x

Выход-код«01»

1

0

1

1

0

0

0

0

0

1*2+1=03

1

0

1

1

0

1

x

x

x

Выход-код«01»

1

0

1

1

1

0

x

x

x

1*3+1=10

1

0

1

1

1

1

x

x

x

Выход-код«01»

1

1

0

0

0

0

x

x

x

0*0+1=01

1

1

0

0

0

1

x

x

x

Выход-код«00»

1

1

0

0

1

0

x

x

x

0*1+1=01

h

P

Результат

1

1

0

0

1

1

x

x

x

Выход-код«00»

1

1

0

1

0

0

0

0

1

0*2+1=01

1

1

0

1

0

1

x

x

x

Выход-код«00»

1

1

0

1

1

0

x

x

x

0*3+1=01

1

1

0

1

1

1

x

x

x

Выход-код«00»

1

1

1

0

0

0

x

x

x

2*0+1=01

1

1

1

0

0

1

x

x

x

Выход-код«02»

1

1

1

0

1

0

x

x

x

2*1+1=03

1

1

1

0

1

1

x

x

x

Выход-код«02»

1

1

1

1

0

0

1

0

1

2*2+1=11

1

1

1

1

0

1

x

x

x

Выход-код«02»

1

1

1

1

1

0

x

x

x

2*3+1=13

1

1

1

1

1

1

x

x

x

Выход-код«02»

Минимизацию выхода ОЧУС P проведем алгоритмом Квайна-МакКласке, минимизацию Q1 проведем с помощью карт Вейча, минимизацию  проведем с помощью карт Карно.

Минимизация функции  алгоритмом Квайна-МакКласке:

001001; 111001; 000001; 000011; 000101; 000111; 001011; 001101; 001111; 010001; 010001; 010101; 010111; 011011; 0111101; 011101; 011111; 100001; 100011; 100101; 100111; 101011; 101101; 101111; 110001; 110011; 110101; 110111; 111011; 111101; 111111.

C1

000001

1)─

C3

110001

19) ─

    

C5   

111011

37) ─

001000

2) ─

111000

20) ─

111101

38) ─

C2

000011

3) ─

C4

001111

21) ─

111110

39) ─

000101

4) ─

010111

22) ─

   C6

111111

40) ─

001001

5) ─

011011

23) ─

001100

6) ─

011101

24) ─

010001

7) ─

011110

25) ─

100001

8) ─

100111

26) ─

C3

000111

9) ─

101011

27) ─

001011

10) ─

101101

28) ─

001101

11) ─

101110

29) ─

001110

12) ─

110011

30) ─

010011

13) ─

110101

31) ─

010101

14) ─

111001

32) ─

011100

15) ─

111100

33) ─

100011

16) ─

C5

011111

34) ─

100101

17) ─

101111

35) ─

101100

18) ─

110111

36) ─

C1

0000X1

1)─

X10011

42) ─

11X101

83) ─

000X01

2) ─

C3

0101X1

43) ─

C4

1110X1

84) ─

00X001

3) ─

01X101

44) ─

111X01

85) ─

0X0001

4) ─

X10101

45) ─

11110X

86) ─

X00001

5) ─

01110X

46) ─

1111X0

87) ─

00100X

6) ─

0111X0

47) ─

X11111

88) ─

001X00

7) ─

X11100

48) ─

C5

1X1111

89) ─

C2

000X11

8) ─

100X11

49) ─

11X111

90) ─

00X011

9) ─

10X011

50) ─

111X11

91) ─

0X0011

10) ─

1X0011

51) ─

1111X1

92) ─

X00011

11) ─

1001X1

52) ─

11111X

93) ─

00X101

12) ─

10X101

53) ─

0001X1

13) ─

1X0101

54) ─

0X0101

14) ─

10110X

55) ─

X00101

15) ─

1011X0

56) ─

0010X1

16) ─

1100X1

57) ─

001X01

17) ─

110X01

58) ─

00110X

18) ─

11X001

59) ─

0011X0

19) ─

11100X

60) ─

0X1100

20) ─

111X00

61) ─

X01100

21) ─

0X1111

62) ─

0100X1

22) ─

C4

X01111

63) ─

010X01

23) ─

01X111

64) ─

X10001

24) ─

X10111

65) ─

1000X1

25) ─

011X11

66) ─

100X01

26) ─

X11011

67) ─

1X0001

27) ─

0111X1

68) ─

C2

00X111

28) ─

X11101

69) ─

0X0111

29) ─

01111X

70) ─

X00111

30) ─

X11110

71) ─

001X11

31) ─

10X111

72) ─

0X1011

32) ─

1X0111

73) ─

X01011

33) ─

101X11

74) ─

0011X1

34) ─

1X1011

75) ─

0X1101

35) ─

1011X1

76) ─

X01101

36) ─

1X1101

77) ─

00111X

37) ─

10111X

78) ─

0X1110

38) ─

1X1110

79) ─

X01110

39) ─

110X11

80) ─

010X11

40) ─

11X011

81) ─

01X011

41) ─

1101X1

82) ─

1)─

44) ─

87) ─

2) ─

45) ─

88) ─

3) ─

46) ─

89) ─

4) ─

47) ─

90) ─

5) ─

48) ─

91) ─

6) ─

49) ─

92) ─

7) ─

50) ─

93) ─

8) ─

51) ─

94) ─

9) ─

52) ─

95) ─

10) ─

53) ─

96) ─

11) ─

54) ─

97) ─

12) ─

55) ─

98) ─

13) ─

56) ─

99) ─

14) ─

57) ─

100) ─

15) ─

58) ─

101) ─

16) ─

59) ─

102) ─

17) ─

60) ─

103) ─

18) ─

61) ─

104) ─

19) ─

62) ─

105) ─

20) ─

63) ─

106) ─

21) ─

64) ─

107) ─

22) ─

65) ─

108) ─

23) ─

66) ─

109) ─

24) ─

67) ─

110) ─

25) ─

68) ─

111) ─

26) ─

69) ─

112) ─

27) ─

70) ─

113) ─

28) ─

71) ─

114) ─

29) ─

72) ─

115) ─

30) ─

73) ─

116) ─

31) ─

74) ─

117) ─

32) ─

75) ─

118) ─

33) ─

76) ─

119) ─

34) ─

77) ─

120) ─

35) ─

78) ─

121) ─

36) ─

79) ─

122) ─

37) ─

80) ─

123) ─

38) ─

81) ─

124) ─

39) ─

82) ─

125) ─

40) ─

83) ─

126) ─

41) ─

84) ─

127) ─

42) ─

85) ─

128) ─

43) ─

86) ─

129) ─

129) ─

130) ─

131) ─

132) ─

133) ─

134) ─

135) ─

136) ─

137) ─

138) ─

139) ─

140) ─

141) ─

142) ─

143) ─

144) ─

145) ─

146) ─

147) ─

148) ─

149) ─

150) ─

151) ─

152) ─

153) ─

Минимизация функции  картами Вейча:

x2

x2

x1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

y1

p1

x

x

x

x

1

x

x

x

x

x

x

x

x

x

x

1

1

x

x

1

x

x

1

y1

x1

1

x

x

1

1

x

x

1

1

1

1

1

1

1

1

1

y2

y2

h


Минимизация функции  картами Карно:

000

001

011

010

110

111

101

100

000

x

x

x

x

001

1

1

x

x

x

x

x

011

1

x

1

x

x

x

x

010

x

x

1

1

x

x

1

110

x

x

1

1

x

x

1

111

1

x

1

x

x

x

x

101

1

x

x

x

x

x

100

x

x

x

x

Минимизировав функцию, получим:

 =

          

Оценка эффективности минимизации переключательных функций

Для проведения оценки эффективности минимизации переключательных функций необходимо посчитать цену схемы до минимизации и цену схемы после минимизации. Эффективность минимизации k определяется как:

 

Все рассчитанные данные сведены в таблицу 3 и 4

Табл 3 Эффективность минимизации ОЧС

Вых.

схемы

Рассчитанная цена схемы

Эфф.

мин. k

До минимизации

После минимизации

P1

с=2*5++=15

с=2*4+++1=13

1,15

P2

с=2*5+++1=14

с=2*4+++1=13

1,15

P3

с=14*5++14+=99

с=10++ 4 +=19

5,21

P4

с=16*5++16+=113

c=3++ 2 +=6

18,3

Табл 4 Эффективность минимизации ОЧУ

Вых.

схемы

Рассчитанная цена схемы

Эфф.

мин. k

До минимизации

После минимизации

c=4*5++1+4++4+

+=38

с=11++3++3+

+=24

1,58

с=8*5++1+8++8+=73

с=22++6++6+

+=47

1,55

с=8*5++1+8++8+

+=73

с=13++4++4+

+=30

2,43

 


Синтез ОЧС на основе мультиплексора

Мультиплексор – это логическая схема, имеющая n входов,m управляющих входов и один выход. При этом должно выполняться равенство .На выход мультиплексора может быть пропущен без изменений любой (один) логический сигнал, поступающий на информационные входы. Порядковый номер информационного входа, значение с которого в данный момент должно быть передано на выход, должно быть передано на выход, определяется двоичным кодам на управляющих входах. Для синтеза ОЧС будем использовать мультиплексор “один из восьми” (1 из 8-ми). Входы  – это информационные входы мультиплексора. Входы  – управляющие входы

Мультиплексор “один из восьми”

Используя таблицу истинности ОЧС, составим таблицу истинности для построения ОЧС на мультиплексорах

p

П

П

1

1

1

1

0

0

1

1

1

1

1

1

1

0

0

0

1

1

1

0

0

x

x

x

1

1

1

0

1

x

x

x

1

1

0

0

0

0

0

0

p

1

1

0

0

1

0

0

1

1

1

0

1

0

x

x

x

1

1

0

1

1

x

x

x

0

0

1

1

0

0

0

0

p

0

0

1

1

1

0

0

1

0

0

1

0

0

x

x

x

0

0

1

0

1

x

x

x

0

0

0

0

0

0

0

p

1

0

0

0

0

1

0

1

0

0

0

0

1

0

x

x

x

0

0

0

1

1

x

x

x

0

1

1

1

0

0

0

p

1

0

1

1

1

1

0

1

0

0

1

1

0

0

x

x

x

0

1

1

0

1

x

x

x

0

1

0

0

0

0

p

1

0

p

0

1