1 Elementy cyfrowe i układy logicznewykład № 3 Dr Galina Cariowa

2 Legenda Wielomian Reed’a- Müllera. Wielomian arytmetyczny.Wielomian arytmetyczny dla wielu wejść.

3 Wielomian Reed’a- MülleraDowolną boolowską FAL: można przedstawić w postaci wielomianu R-M Współczynniki wielomianu R - M - binarna reprezentacja j

4 Wielomian Reed’a- MülleraIstnieje różnych zestawów wartości współczynników , czyli dla dwóch zmiennych istnieje wielomianów Reed’a- Müllera.

5 Wielomian Reed’a- MülleraPrzykład. Zapisać dowolne boolowskie FAL dwóch i trzech zmiennych w postaci wielomianu Reed’a- Müllera. n=2. -wielomian R-M n=3. Zadanie wyznaczenia wielomianu Reed’a- Müllera sprowadza się do określenia współczynników

6 Wielomian Reed’a- MülleraPoczątkową FAL zadano w formie FDCF lub FCCF. Relacja dla mintermów i pozwala przejść od FDCF do wielomianu Reed’a- Müllera: 1. W FDCF należy wymienić symbol dysjunkcji na symbol sumowania modulo 2; 2. Wykonać podstawienie dla zanegowanych zmiennych; 3. Dokonać podstawowych przekształceń logicznych.

7 Wielomian Reed’a- MülleraSposób algebraiczny przedstawienia funkcji boolowskiej w postaci wielomianu Reed’a- Müllera Wielomian Reed’a- Müllera

8 Wielomian Reed’a- MülleraZamień funkcję na wielomian Reed’a- Müllera. 1.Wyznaczamy wektor wartości: 2. Z wektora wartości mamy FDCF: 3.Zamieniamy symbole dysjunkcji na sumowanie modulo 2 i korzystamy z podstawienia

9 Wielomian Reed’a- Müllera

10 Wielomian Reed’a- Müllera

11 Wielomian Reed’a- Müllera

12 Wyznaczenie wielomianu Reed’a- MülleraPrawa De Morgana wielomianu Reed’a- Müllera

13 Wielomian Reed’a- MülleraWektor współczynników wielomianu R - M W wektorze F pozycja każdego współczynnika jest ściśle ustalona. - baza koniunkcyjna logiczna X – wektor prawdy

14 Wielomian Reed’a- MülleraBaza odwrotna Baza prosta Baza odwrotna Baza prosta - symbol mnożenia Kronekkera k

15 Wielomian Reed’a- MülleraKorzystają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:

16 Wielomian Reed’a- Müllera

17 Wielomian Reed’a- Müllera

18 Wielomian Reed’a- Müllera

19 Wielomian Reed’a- Müllera

20 Wielomian Reed’a- MülleraInterpretacja 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.

21 Wielomiany arytmetyczne

22 Wielomiany arytmetyczneDo 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:

23 Wielomian arytmetyczny

24 Wielomiany arytmetyczne

25 Wielomiany arytmetyczne

26 Wielomiany arytmetyczne c.d.

27 Wielomiany arytmetyczne c.d.

28 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).

29 Wielomiany arytmetyczne c.d.Reguły zamiany operacji logicznych na operacje arytmetyczne : jeśli ab=0

30 Wielomiany arytmetyczne c.d.Przykład wyznaczania wielomianu arytmetycznego. funkcja logiczna wielomian arytmetyczny

31 ARYTMETYCZNE PRZEDSTAWIENIE SYSTEMU FUNKCJI

32 Wielomiany arytmetyczne dla n-wejść i m-wyjść.

33 Wielomiany arytmetyczne

34 Wielomiany arytmetyczne c.d.Wyznaczamy wektor wartości systemu trzech funkcji logicznych dwóch zmiennych

35 Wielomiany arytmetyczne c.d.

36 Wielomiany arytmetyczne c.d.nnnnnn

37 Zamiana kodu binarnego na kod Gray’akkkkk

38

39 Zamiana kodu binarnego na kod Gray’a

40 Zamiana kodu binarnego na kod Gray’aAby zamienić liczbę binarną bnbn-1…b1 w liczbę zapisaną w kodzie Gray’a gngn-1…g1, należy stosować regułę: 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.

41 Zamiana kodu binarnego na kod Gray’aPrzykład. Przedstawić liczbę binarną w liczbę zapisaną w kodzie Gray’a. Najmniej znaczący bit odrzucamy 11012=1011g

42 Zamiana kodu binarnego na kod Gray’aZaprojektujemy 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.

43 Zamiana kodu binarnego na kod Gray’aStan każdego wyjścia sieci logicznej jest funkcją stanów na wejściach. Możemy więc zapisać:

44 Zamiana kodu binarnego na kod Gray’a

45 Zamiana kodu binarnego na kod Gray’aNa przykład, dla liczby 000 mamy: W kodzie Gray’a dana liczba jest przedstawiana jako 000.

46 Zamiana kodu binarnego na kod Gray’aDla liczby 0102 mamy: W kodzie Gray’a dana liczba jest przedstawiana jako 011.

47 Zamiana kodu binarnego na kod Gray’a

48 Zamiana kodu Gray’a na kod binarnyPrzykład g zamienić na liczbę binarną. 1) -najmniej znaczący bit liczby binarnej 2) -w drugiej pozycji 3) - w trzeciej pozycji 4) -w czwartej pozycji mamy 1 1011g = 11012

49 Zamiana kodu Gray’a na kod binarny

50 Zamiana kodu Gray’a na kod binarny

51 Zamiana kodu Graya na kod binarny

52 Zamiana kodu Gray’a na kod binarny

53 Dziękuję za uwagę