Minimalizacja funkcji przelaczajacej ?!?!?!?!?



Masz problem? Zapytaj na forum elektroda.pl z bramką pl.misc.elektronika!

Poprzedni Następny
Wiadomoœć
spis treści
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



Poprzedni Następny
Wiadomoœć
spis treści
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ę...

Poprzedni Następny
Wiadomoœć
spis treści
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.


Poprzedni Następny
Wiadomoœć
spis treści
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 | | | | |
> -------------------------------------
>