Dr Galina

Cariowa

Legenda

Wielomian

arytmetyczny.

Wielomian arytmetyczny

dla wielu wejść.

Wielomian Reed’a-

Müllera.

Wielomian Reed’a-

Müllera











1

2

0

)

(

)

(

2

)

(

1

)

(

...

)

(

2

1

n

n

j

j

n

j

j

j

x

x

x

f

X

F













0

,

1

1

,

)

(

i

i

i

j

i

j

j

x

x

i









1

0

)

(X

f

Współczynniki wielomianu R -

M

n

j

j

j

...

2

1

- binarna
reprezentacja

j

)

,...,

,

(

2

1

n

x

x

x

f

Dowolną boolowską
FAL:

można przedstawić

w postaci

wielomianu R-M

Wielomian Reed’a-

Müllera

Istnieje różnych zestawów

wartości współczynników , czyli

dla dwóch zmiennych istnieje

wielomianów Reed’a- Müllera.

4

2

)

( j

f

4

2

Wielomian Reed’a-

Müllera

Przykład

. Zapisać dowolne boolowskie FAL dwóch i

trzech

zmiennych w postaci wielomianu

Reed’a- Müllera.

n=

2.

1

2

1

1

)

3

(

0

2

1

1

)

2

(

1

2

0

1

)

1

(

0

2

0

1

)

0

(

)

(

x

x

f

x

x

f

x

x

f

x

x

f

X

F









2

1

)

3

(

1

)

2

(

2

)

1

(

)

0

(

)

(

x

x

f

x

f

x

f

f

X

F









-

wielomia

n R-M

n=

3.

3

2

1

)

7

(

2

1

)

6

(

3

1

)

5

(

1

)

4

(

3

2

)

3

(

2

)

2

(

3

)

1

(

)

0

(

)

(

x

x

x

f

x

x

f

x

x

f

x

f

x

x

f

x

f

x

f

f

X

F

















Zadanie wyznaczenia wielomianu Reed’a- Müllera

sprowadza się do określenia współczynników .

)

( j

f

Wielomian Reed’a-

Müllera

Początkową FAL zadano w formie FDCF lub

FCCF.
Relacja dla mintermów

i pozwala przejść od FDCF do wielomianu

Reed’a- Müllera:

2

1

2

1

m

m

m

m







1. W FDCF należy wymienić symbol

dysjunkcji na symbol sumowania modulo 2;

2. Wykonać podstawienie dla

zanegowanych zmiennych;

1



x

x

3. Dokonać podstawowych przekształceń

logicznych.

1

m

2

m

Sposób algebraiczny

przedstawienia funkcji

boolowskiej w postaci

wielomianu Reed’a- Müllera

)

1

(

)

1

)(

1

(

)

1

(

)

1

)(

1

)(

1

(

)

(

3

2

1

3

2

1

3

2

1

3

2

1























x

x

x

x

x

x

x

x

x

x

x

x

x

f

3

2

1

3

2

1

3

2

1

3

2

1

)

(

x

x

x

x

x

x

x

x

x

x

x

x

x

f











3

2

1

1

3

1

3

2

3

2

3

2

1

3

1

2

1

3

2

1

1

)

(

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

f

























3

2

1

2

1

)

(

x

x

x

x

x

f















1



x

x

Wielomian Reed’a-

Müllera

3

2

1

3

2

1

3

2

1

3

2

1

)

(

x

x

x

x

x

x

x

x

x

x

x

x

x

f











Wielomian Reed’a-

Müllera

Zamień funkcję

na

wielomian

Reed’a-

Müllera.

3

2

1

)

(

x

x

x

x

f





1.Wyznaczamy wektor wartości

:





T

X

1

,

1

,

1

,

1

,

0

,

0

,

0

,

1



2. Z wektora wartości mamy

FDCF:

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

)

(

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

f











3.Zamieniamy symbole dysjunkcji na

sumowanie modulo 2 i korzystamy z
podstawienia

x

x



1

Wielomian Reed’a-

Müllera





































3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

)

1

(

)

1

(

)

1

)(

1

(

)

1

)(

1

)(

1

(

)

(

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

F

Wielomian Reed’a-

Müllera

.

1

3

2

1

3

2

1

2

1

3

2

1

3

1

3

2

1

2

1

3

1

1

3

2

1

2

1

3

1

1

3

2

2

3

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x











































0



 x

x

Wielomian Reed’a-

Müllera

.

3

2

1

2

1

3

1

3

2

2

3

1

)

(

x

x

x

x

x

x

x

x

x

x

x

x

F















Wyznaczenie

wielomianu

Reed’a- Müllera

3

2

1

2

1

)

(

x

x

x

x

x

x

f













3

2

1

2

1

)

(

)

(

x

x

x

x

x

x

f

x

f







3

2

1

2

1

x

x

x

x

x















1

))

1

)

1

)(

1

)

1

(

(

3

2

1

2

1

x

x

x

x

x

2

1

1

3

2

3

2

1

x

x

x

x

x

x

x

x









Prawa De

Morgana

1



x

x

wielomianu

Reed’a- Müllera























1

1

3

2

3

2

1

1

3

2

1

3

2

1

2

1

3

2

1

3

2

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

Wielomian Reed’a-

Müllera

)

2

(mod

2

X

K

F

n





T

n

f

f

f

F

]

,...,

,

[

)

(

)

1

(

)

0

(



Wektor

współczynnikó

w wielomianu

R - M

X – wektor

prawdy

n

K

2

- baza koniunkcyjna

logiczna

W wektorze

F

pozycja każdego

współczynnika jest ściśle
ustalona.

Wielomian Reed’a-

Müllera

Baza

odwrotna

Baza

prosta

k

Baza

odwrotna

Baza

prosta



- symbol

mnożenia

Kronekkera

Wielomian Reed’a-

Müllera

)

2

(mod

1

2

F

K

X

n







Korzystając z własności, że

macierze

K

są własnymi

odwrotnościami, te same macierze

służą do transformacji odwrotnej, tj

z postaci wielomianu Reed’a-

Müllera do wektora prawdy

X

:

K

K





)

2

(mod

1

Wielomian Reed’a-

Müllera



Wielomian Reed’a-

Müllera

Wielomian Reed’a-

Müllera

Wielomian Reed’a-

Müllera

Wielomian Reed’a-

Müllera

Interpretacja

wektora F.

Czytamy tylko wiersze, dla których wektor

R-M przyjmuje wartość 1.

Każdy wiersz to iloczyn kolejnych

kolumn, przy czym :
Wartość „0” w kolumnie odpowiada

wartości „1”w iloczynie;

Wartość „1” w kolumnie odpowiada

zmiennej w nagłówku kolumny.

Wielomiany

arytmetyczne

Wielomiany arytmetyczne

Do rozwiązywania zadań techniki

obliczeniowej stosuje się logikę

arytmetyczną czyli postać

arytmetyczną przedstawienia

funkcji boolowskich.

Wielomianowa postać

arytmetyczna

(postać P) funkcji

logicznej f(X) określana jest

następująco:

Wielomian arytmetyczny



Wielomiany arytmetyczne

Wielomiany arytmetyczne

Wielomiany arytmetyczne

c.d.

Wielomiany arytmetyczne

c.d.

Wielomiany arytmetyczne

c.d.

Jeśli w pewnym wyrażeniu funkcji

boolowskiej f(x)

wymienić operacje

logiczne na operacje arytmetyczne

wg odpowiednich reguł, to otrzymane

wyrażenie będzie

wielomianem

arytmetycznym

boolowskiej funkcji,

P(x).

Wielomiany arytmetyczne

c.d.

ab

b

a

b

a

ab

b

a

ab

a

b

a

b

a

b

a

ab

b

a

b

a

b

a

b

a

ab

b

a

b

a

ab

ab

a

a

























































1

1

1

2

1

jeśli

ab=0

jeśli

ab=0

Reguły

zamiany

operacji

logicznych na

operacje
arytmetyczne

:

Wielomiany arytmetyczne

c.d.

3

2

1

3

2

3

1

3

2

1

2

1

3

2

1

3

2

1

3

1

3

2

1

3

2

3

1

3

2

1

2

1

3

2

1

3

2

1

3

1

3

2

1

1

2

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

2

1

2

1

1

)

1

)(

1

(

)

1

(

)

1

)(

1

)(

1

(

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

F



















































































3

2

1

3

2

3

1

3

2

1

2

1

3

2

1

3

2

1

3

1

3

2

1

3

2

3

1

3

2

1

2

1

3

2

1

3

2

1

3

1

3

2

1

1

2

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

3

2

1

2

1

1

)

1

)(

1

(

)

1

(

)

1

)(

1

)(

1

(

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

F



















































































wielomian

arytmetyczn

y

funkcja

logiczna

Przykład wyznaczania wielomianu

arytmetycznego.

ARYTMETYCZNE

PRZEDSTAWIENIE

SYSTEMU FUNKCJI

Wielomiany arytmetyczne

dla

n-wejść i m-wyjść.

Wielomiany arytmetyczne

Wielomiany arytmetyczne

c.d.

Wyznaczamy wektor wartości systemu

trzech funkcji logicznych dwóch

zmiennych

D

X

2

1

0

,

,

f

f

f

2

1

,x

x

Wielomiany arytmetyczne

c.d.

Wielomiany arytmetyczne

c.d.

2

0

)

(

x

x

f



2

1

1

)

(

x

x

x

f



2

1

2

)

(

x

x

x

f





Zamiana kodu binarnego

na kod Gray’a

Zamiana kodu binarnego

na kod Gray’a

Zamiana kodu binarnego

na kod Gray’a

Aby zamienić liczbę binarną

b

n

b

n-1

…b

1

w

liczbę zapisaną w kodzie Gray’a

g

n

g

n-1

…g

1

,

należy stosować regułę:

1







i

i

i

b

b

g

n

n

b

g



Kod binarny przetwarzamy w kod Gray’a

sumowaniem modulo 2 danej liczby binarnej z

taką samą liczbą, ale przesuniętej w prawo na

jeden bit.

Zamiana kodu binarnego na

kod Gray’a

Przykład

. Przedstawić liczbę binarną

1101

2

w

liczbę zapisaną w kodzie

Gray’a.

1101

2

=10

11

g

1

1

0

1

1

0

1

1

1

0

1

1



Najmniej

znaczący

bit

odrzucamy

Zamiana kodu binarnego

na kod Gray’a

Zaprojektujemy sieć logiczną

zmieniającą 3-bitowy naturalny kod

binarny NBC na wyrazy w kodzie Gray'a.

Sieć będzie posiadała 3 wejścia danych

, na

które należy podać wartość binarną. Na

trzech wyjściach sieci pojawi

się wtedy odpowiedni wyraz kodu

Gray'a.

0

1

2

,

,

x

x

x

0

1

2

,

,

g

g

g

Zamiana kodu binarnego

na kod Gray’a

Stan każdego wyjścia sieci logicznej jest

funkcją stanów na wejściach. Możemy

więc zapisać:

)

,

,

(

)

,

,

(

)

,

,

(

0

1

2

0

0

0

1

2

1

1

0

1

2

2

2

x

x

x

g

g

x

x

x

g

g

x

x

x

g

g







Zamiana kodu binarnego

na kod Gray’a

Zamiana kodu binarnego

na kod Gray’a

Na przykład, dla
liczby 000 mamy

:

0

,

0

,

0

2

1

0







x

x

x

0

2

2



x

g

0

0

0

1

2

1











x

x

g

0

0

0

0

1

0











x

x

g

W kodzie Gray’a dana liczba

jest przedstawiana jako

000

.

Zamiana kodu binarnego

na kod Gray’a

Dla liczby

010

2

mamy:

0

,

1

,

0

2

1

0







x

x

x

0

2

2



x

g

1

1

0

1

2

1











x

x

g

1

0

1

0

1

0











x

x

g

W kodzie Gray’a dana

liczba jest

przedstawiana jako

011

.

Zamiana kodu binarnego

na kod Gray’a

g

b

010

011 

Zamiana kodu Gray’a na kod

binarny

Przykład.

1011

g

zamienić

na

liczbę

binarną.

1

)

1

1

1

0

1









-najmniej znaczący bit liczby

binarnej

2

)

0

1

0

1







-w drugiej

pozycji

3

)

1

0

1





- w trzeciej

pozycji

4

)

-w czwartej pozycji

mamy 1

1011g =

1101

2

Zamiana kodu Gray’a na

kod binarny

Zamiana kodu Gray’a na

kod binarny

b

g

010

011 

Zamiana kodu Graya na

kod binarny

b

g

001

001 

Zamiana kodu

Gray’a na kod

binarny

b

g

011

010 

Dziękuję za uwagę

Dziękuję za uwagę