Minimalizacja funkcji przelaczajacej ?!?!?!?!?
Masz problem? Zapytaj na forum elektroda.pl z bramką pl.misc.elektronika!
From: "Marek###" <mkmkmk_at_nospam_polbox.com>
Subject: Minimalizacja funkcji przelaczajacej ?!?!?!?!?
Date: 30 Sep 1997 19:17:16 GMT
Czy ktos spotkal sie juz z tym problemem.
Mam np. funkcje y=E(0,1,2,6,8,9,,10,11,14)x4,x3,x2,x1
Nalezy przeprowadzic minimalizacje tej funkcji
A wiec najpierw rysujemy siatke Karnaugtha, ktora niby ma przedtsawiac
przestrzen wielowymiarowa na plaszczyznie.
I tak przestrzen 3 wymiarowa to:
x1
/ \
/ ---------------------
x3 |4 |6 |7 |5 |
\ ---------------------
|0 |2 |3 |4 |
---------------------
\ /
x2
Czy ktos wie dlaczego tak?
Ale w przypadku mojej funcji to funckja 4 wymiarowa wiec tabela ponoc
wyglada tak
/ x2 \
/ x1 \
-----------------------------
| 0 | 2 | 3 | 1 |
/-----------------------------
/ | 4 | 6 | 7 | 5 |
/ x3-----------------------------
/ \ | 12 | 14 | 15 | 13 |
x4 \----------------------------
\ | 8 | 10 | 11 | 9 |
\ ----------------------------
Czy ktos wie skad sie to wzielo i dlaczego,
skad te zakresy dla x1 ,x2 itd
I tearaz skad sie bierze dalej
minimalizacja
i w koncy wychodzi
"""""" x4 razy negacja x3 """"""
i to ma byc wynik, czy ktos wie z kad sie to wzielo
Czy jest moze jakas ksiazka ktora to opisuje?
Prosze o pomoc, mam sie z tego przygotowac ! ! !
Minimalizacja funcji to ponoc podstawowy problem w elektronice
Zalamany Marek
From: "Sylwester Łazar" <zsee_at_nospam_ids.poznan.pl>
Subject: Re: Minimalizacja funkcji przelaczajacej ?!?!?!?!?
Date: 30 Sep 1997 21:19:47 GMT
Marek### <mkmkmk_at_nospam_polbox.com> napisał(a) w artykule
Mam np. funkcje y=E(0,1,2,6,8,9,,10,11,14)x4,x3,x2,x1
I tak przestrzen 3 wymiarowa to:
x1
/ \
/ ---------------------
x3 |4 |6 |7 |5 |
\ ---------------------
|0 |2 |3 |4 |
---------------------
\ /
x2
Powinno być raczej tak:
x1
/ \
/ ---------------------
x3 |4 |6 |7 |5 |
\ ---------------------
|0 |2 |3 |1 |
---------------------
\ /
x2
Czy ktos wie dlaczego tak?
o tym za chwilę..
Ale w przypadku mojej funcji to funckja 4 wymiarowa wiec tabela ponoc
wyglada tak
/ x2 \
/ x1 \
-----------------------------
| 0 | 2 | 3 | 1 |
/-----------------------------
/ | 4 | 6 | 7 | 5 |
/ x3-----------------------------
/ \ | 12 | 14 | 15 | 13 |
x4 \----------------------------
\ | 8 | 10 | 11 | 9 |
\ ----------------------------
tu jest o.k.
i w koncy wychodzi
"""""" x4 razy negacja x3 """"""
Mi wychodzi raczej:
y= /x2/x3+/x1x2+x4/x3
legenda:
/x2 czytaj nie x2
A teraz wykład:
Są książki, ale bym musiał poszukać tytułów.
W ogóle to tabelka jest rysowana w kodzie Graya, więc przyjmuje się, że
sąsiednie kolumny i wiersze mogą mieć "współrzędne" różniące się tylko i
wyłącznie na
jednym bicie.
Czyli opis kolumn od lewej do prawej musi wyglądać tak:
| 00 | 01 | 11 | 10 |
Teraz jeszcze opis wierszy:
00
--
01
--
11
--
10
teraz przyporządkujemy, (dowolnie zresztą)danym współrzędnym określone
zmienne:
i dla Twojego przykładu zrobiono tak
kolumny są opisywane przez parę: x1,x2 czyli:
| x1x2 | x1x2 | x1x2 | x1x2 |
| 00 | 01 | 11 | 10 |
a dla wierszy:
x3x4
00
--
01
--
11
--
10
Powstała więc siatka 4x4
| x1x2 | x1x2 | x1x2 | x1x2 |
x3x4 | 00 | 01 | 11 | 10 |
-------------------------------------
00 | | | | |
-------------------------------------
01 | | | | |
-------------------------------------
11 | | | | |
-------------------------------------
10 | | | | |
-------------------------------------
Jeżeli teraz przyjmiesz że dla kolejnych liczb dziesiętnych (lp) numery
komórek odpowiadają następującym kodom binarnym (x4,x3,x2,x1):
lp. x4 x3 x2 x1 y
0 0 0 0 0 1
1 0 0 0 1 1
2 0 0 1 0 1
3 0 0 1 1 0
4 0 1 0 0 0
5 0 1 0 1 0
6 0 1 1 0 1
7 0 1 1 1 0
8 1 0 0 0 1
9 1 0 0 1 1
10 1 0 1 0 1
11 1 0 1 1 1
12 1 1 0 0 0
13 1 1 0 1 0
14 1 1 1 0 1
15 1 1 1 1 0
*Legenda:
*y-jest to wartość funkcji dla danej liczby (lp).Bierzemy ją z treści
zadania.
*Zdaje się, że zapis
*> y=E(0,1,2,6,8,9,,10,11,14)x4,x3,x2,x1
*określa dla jakich liczb y=1, więc stąd te dane w kolumnie y.
To możesz oznaczyć-ponumerować kratki- jaki mają numer dziesiętny:
| x1x2 | x1x2 | x1x2 | x1x2 |
x4x3 | 00 | 01 | 11 | 10 |
-------------------------------------
00 | | | | |
| 0| 2| 3| 1|
-------------------------------------
01 | | | | |
| 4| 6| 7| 5|
-------------------------------------
11 | | | | |
| 12| 14| 15| 13|
-------------------------------------
10 | | | | |
| 8| 10| 11| 9|
-------------------------------------
teraz uzupełniamy kratki wartością funkcji (y- z tabelki, nr kratki - lp)
| x1x2 | x1x2 | x1x2 | x1x2 |
x4x3 | 00 | 01 | 11 | 10 |
-------------------------------------
00 |1 |1 |0 |1 |
| 0| 2| 3| 1|
-------------------------------------
01 |0 |1 |0 |0 |
| 4| 6| 7| 5|
-------------------------------------
11 |0 |1 |0 |0 |
| 12| 14| 15| 13|
-------------------------------------
10 |1 |1 |1 |1 |
| 8| 10| 11| 9|
-------------------------------------
Teraz wyślę ten fragment na listę, a potem jak nie zasnę dodam resztę...
From: "Sylwester Łazar" <zsee_at_nospam_ids.poznan.pl>
Subject: Re: Minimalizacja funkcji przelaczajacej ?!?!?!?!?
Date: 30 Sep 1997 22:02:27 GMT
Teraz zaczyna się wielka zabawa!
Co zrobić:
Pokryć wszystkie jedynki prostokątami o następujących parametrach:
1)prostokąty powinny być jak największe
2)prostokąty mogą mieć powierzchnię 1,2,4,8 lub 16 kratek - nie inną
3)prostokąty mogą się pokrywać wzajemnie (z pewnych względów nawet lepiej)
4)prostokąty mogą zaczynać się przy prawej krawędzi i kończyć na lewej
To samo dotyczy góry i dołu.Inaczej mówiąc prawa krawędź łączy się jakby
z lewą, górna z dolną.
W naszym przykładzie jest nawet kwadrat(szczególny przypadek prostokąta),
który składa się z 4 narożników!- i to jest o.k.
5)prostokątów powinno być jak najmniej.
6)w skład prostokątów nie mogą wchodzić zera
Stosując się do tych zasad naszą łamigłówkę najlepiej jest pokryć trzema
prostokątami o powierzchni 4 (gwiazdki oznaczają pola jakie wchodzą
w skład prostokąta)
1)prostokąt A:
| x1x2 | x1x2 | x1x2 | x1x2 |
x4x3 | 00 | 01 | 11 | 10 |
-------------------------------------
00 |1 * |1 |0 |1 * |
| 0| 2| 3| 1|
-------------------------------------
01 |0 |1 |0 |0 |
| 4| 6| 7| 5|
-------------------------------------
11 |0 |1 |0 |0 |
| 12| 14| 15| 13|
-------------------------------------
10 |1 * |1 |1 |1 * |
| 8| 10| 11| 9|
-------------------------------------
2)prostokąt B:
| x1x2 | x1x2 | x1x2 | x1x2 |
x4x3 | 00 | 01 | 11 | 10 |
-------------------------------------
00 |1 |1 * |0 |1 |
| 0| 2| 3| 1|
-------------------------------------
01 |0 |1 * |0 |0 |
| 4| 6| 7| 5|
-------------------------------------
11 |0 |1 * |0 |0 |
| 12| 14| 15| 13|
-------------------------------------
10 |1 |1 * |1 |1 |
| 8| 10| 11| 9|
-------------------------------------
3)prostokąt C:
| x1x2 | x1x2 | x1x2 | x1x2 |
x4x3 | 00 | 01 | 11 | 10 |
-------------------------------------
00 |1 |1 |0 |1 |
| 0| 2| 3| 1|
-------------------------------------
01 |0 |1 |0 |0 |
| 4| 6| 7| 5|
-------------------------------------
11 |0 |1 |0 |0 |
| 12| 14| 15| 13|
-------------------------------------
10 |1 * |1 * |1 * |1 * |
| 8| 10| 11| 9|
-------------------------------------
Wynik jest sumą logiczną iloczynów dla poszczególnych prostokątów.
Dla prostokąta wyznacza się zmienne które go określają na następujących
zasadach:
-jeśli prostokąt zajmuje tylko 1 wiersz/kolumnę to do iloczynu wchodzą
tylko zmienne
leżące na jego krótszym boku.
-jeśli prostokąt zajmuje 2 wiersze/kolumny to do iloczynu wchodzą tylko te
zmienne, które
dla tych dwóch wierszy/kolumn nie zmieniają swojego stanu logicznego- np.
są równe 1 lub 0
w obu wierszach/kolumnach.
-czy zmienna będzie zanegowana czy nie to zależy od jej wartości dla
poszczególnych
wierszy czy kolumn.
negacja jeśli 0
nie zanegowana zmienna gdy 1
I tak mamy dla naszych prostokącików:
1)prostokąt A:
| x1x2 | x1x2 | x1x2 | x1x2 |
x4x3 | 00 | 01 | 11 | 10 |
-------------------------------------
00 |1 * |1 |0 |1 * |
| 0| 2| 3| 1|
-------------------------------------
01 |0 |1 |0 |0 |
| 4| 6| 7| 5|
-------------------------------------
11 |0 |1 |0 |0 |
| 12| 14| 15| 13|
-------------------------------------
10 |1 * |1 |1 |1 * |
| 8| 10| 11| 9|
-------------------------------------
/x2/x3
2)prostokąt B:
| x1x2 | x1x2 | x1x2 | x1x2 |
x4x3 | 00 | 01 | 11 | 10 |
-------------------------------------
00 |1 |1 * |0 |1 |
| 0| 2| 3| 1|
-------------------------------------
01 |0 |1 * |0 |0 |
| 4| 6| 7| 5|
-------------------------------------
11 |0 |1 * |0 |0 |
| 12| 14| 15| 13|
-------------------------------------
10 |1 |1 * |1 |1 |
| 8| 10| 11| 9|
-------------------------------------
/x1x2
3)prostokąt C:
| x1x2 | x1x2 | x1x2 | x1x2 |
x4x3 | 00 | 01 | 11 | 10 |
-------------------------------------
00 |1 |1 |0 |1 |
| 0| 2| 3| 1|
-------------------------------------
01 |0 |1 |0 |0 |
| 4| 6| 7| 5|
-------------------------------------
11 |0 |1 |0 |0 |
| 12| 14| 15| 13|
-------------------------------------
10 |1 * |1 * |1 * |1 * |
| 8| 10| 11| 9|
-------------------------------------
x4/x3
teraz już tylko dodać:
y=/x2/x3 + /x1x2 + x4/x3
i sprawdzić (najlepiej 3 razy)!!!
Mam nadzieję, że dość jasno to zobrazowałem.
Wszystkich przepraszam, za przydługawy post, ale może komuś jeszcze się to
przyda.
--
Sylwester Łazar
electronics engineer
zsee_at_nospam_ids.poznan.pl
aktiv_at_nospam_sylaba.poznan.pl
p.s.
BTW.
Przypuszczam, że już nikt w praktyce tego nie robi za pomocą tabelek
Karnaugh,
bo po prostu pisze się program z danymi jak w zadaniu, kompiluje i w
wyniku mamy już gotową funkcję oraz mapę przepaleń do GAL'a.
Osobiście tego nie robiłem ale wydaje się to dość proste.
From: "Sylwester Łazar" <zsee_at_nospam_ids.poznan.pl>
Subject: Re: Minimalizacja funkcji przelaczajacej ?!?!?!?!?
Date: 30 Sep 1997 22:14:25 GMT
Ojej, a nie mówiłem: 3x sprawdzić!
Są tutaj byki:
a dla wierszy:
x3x4
00
--
> 01
> --
> 11
> --
> 10
>
Tu się pomyliłem:
Powinno być:
> x4x3
>
> 00
> --
> 01
> --
> 11
> --
> 10
Tu też zamieniłem x4 z x3:
> Powstała więc siatka 4x4
>
> zamień!| x1x2 | x1x2 | x1x2 | x1x2 |
>!x3x4! | 00 | 01 | 11 | 10 |
> -------------------------------------
> 00 | | | | |
> -------------------------------------
> 01 | | | | |
> -------------------------------------
> 11 | | | | |
> -------------------------------------
> 10 | | | | |
> -------------------------------------
>