Dr Galina
Cariowa
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ę