metoda Karnaught'a



Masz problem? Zapytaj na forum elektroda.pl

Poprzedni Następny
Wiadomość
Spis treści
From: qqq <qqq_at_nospam_interia.pl>
Subject: metoda Karnaught'a
Date: Thu, 05 May 2005 14:32:13 +0200


Mam takie zadanie. Mam funkcje i musze ją zminimalizować 2-ma metodami
-> Karnaught'a i McKluskey'a. Zrobiłem je obie, ale wyniki się różnia
od siebie. Jestem na 100% przekonany, że robie błąd w metodzie tej, co w
temacie.Funkcja to:

y=y1+y2+y3+y4+y6+y7+y14+y15

Zrobiłem tabele Karnaught'a i wyszło mi coś takiego:

0 1 1 1
1 0 1 1
0 0 1 1
0 0 0 0

No i potrafie obliczyć wartości (na abcd) tylko dla dwóch jedynek koło
siebie, dla większej ilości już nie :/

Jakby komuś się chciało, to prosze o jakieś wskazówki, a jeszcze lepiej
całe rozwiązanie, abym mógł sobie ze swoimi wyliczeniami porównać ;-)
I bardzo prosze nie odsyłać mnie do googli...
A musze to oddać na jutro...

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_xnospamx_at_nospam_poczta.onet.pl>
Subject: Re: metoda Karnaught'a
Date: Thu, 05 May 2005 15:10:09 +0200


On Thu, 05 May 2005 14:32:13 +0200, qqq wrote:
Mam takie zadanie. Mam funkcje i musze ją zminimalizować 2-ma metodami
-> Karnaught'a i McKluskey'a. Zrobiłem je obie, ale wyniki się różnia
od siebie. Jestem na 100% przekonany, że robie błąd w metodzie tej, co w

Wbrew nazwie to sa bardzo podobne metody.
Tyle ze obie w drugiej czesci maja element niepewnosci - mozna
dobrac rozne grupy do pokrycia, mozna je dobrac nieoptymalnie.
Wyniki moga wyjsc rozne, mimo ze to ta sama funkcja.

temacie.Funkcja to:
y=y1+y2+y3+y4+y6+y7+y14+y15

Rozumiem ze y7 oznacza "ustawione bity b0,b1,b2, a b3=0"

Zrobiłem tabele Karnaught'a i wyszło mi coś takiego:

0 1 1 1
1 0 1 1
0 0 1 1
0 0 0 0

No i potrafie obliczyć wartości (na abcd) tylko dla dwóch jedynek koło
siebie, dla większej ilości już nie :/

Na oko to teraz trzeba zakreslic grupy
y1+y3 [~b3*~b2*b0]
y4+y6 [~b3*b2*~b0]
y3+y2+y7+y6
y7+y6+y14+y15

J.


Poprzedni Następny
Wiadomość
Spis treści
From: qqq <qqq_at_nospam_interia.pl>
Subject: Re: metoda Karnaught'a
Date: Thu, 05 May 2005 16:34:19 +0200



Rozumiem ze y7 oznacza "ustawione bity b0,b1,b2, a b3=0"


Na oko to teraz trzeba zakreslic grupy
y1+y3 [~b3*~b2*b0]
y4+y6 [~b3*b2*~b0]
y3+y2+y7+y6
y7+y6+y14+y15

Sorry, ale spędziłem dzisiaj i wczoraj z kumplami cały dzień w budzie
nad tym i już nie myśle :/ Dlatego może to opisze bardziej dokładnie ;)

y7 = 7 = a^bcd ( 0 1 1 1 )

^ - negacja

Ta tabelka wygląda dokładniej tak:

ab\cd 00 01 11 10
00 0 1 1 1
01 1 0 1 1
11 0 0 1 1
10 0 0 0 0

Mi teraz z tej tabelki wychodzi coś takiego:

y = a^b^d + cda^ + cd^a^ + abc^ + a^bd^

Jak już pisałem to są wyniki dla par po 2, a z tego co tu jest to można
niby zrobić 6. NA wikipedii jest to opisane, ale interpretacja mi nie
wychodzi :/

> Wbrew nazwie to sa bardzo podobne metody.
> Tyle ze obie w drugiej czesci maja element niepewnosci - mozna
> dobrac rozne grupy do pokrycia, mozna je dobrac nieoptymalnie.
> Wyniki moga wyjsc rozne, mimo ze to ta sama funkcja.

Czyli jeżeli z McKluskey'a wychodzi mi coś takiego:

a^b^ + a^bc + abc + a^

a z Karrnaught'a coś takiego :

a^ + abc + ca^

to jest to niby to samo?
Kumplom to normalnie po obu stronach (tj. w obu metodach) wychodziło to
samo ...

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_xnospamx_at_nospam_poczta.onet.pl>
Subject: Re: metoda Karnaught'a
Date: Thu, 05 May 2005 18:10:55 +0200


On Thu, 05 May 2005 16:34:19 +0200, qqq wrote:
Ta tabelka wygląda dokładniej tak:
ab\cd 00 01 11 10
00 0 1 1 1
01 1 0 1 1
11 0 0 1 1
10 0 0 0 0

Mi teraz z tej tabelki wychodzi coś takiego:

y = a^b^d + cda^ + cd^a^ + abc^ + a^bd^

Jak już pisałem to są wyniki dla par po 2, a z tego co tu jest to można
niby zrobić 6. NA wikipedii jest to opisane, ale interpretacja mi nie
wychodzi :/

Nie musisz sie ograniczac do "par po dwie". Im wieksze obszary
zaznaczysz, tym mniej wejsc beda mialy bramki [a to oznacza mniej
krzemu, w CMOS nawet duzo mniej] i jest szansa ze mniej bramek ci
wyjdzie.

W tym przykladzie to ja widze nawet 9 mozliwych "par po 2". Teraz
zaczyna sie czesc przykra - tzn ktore z tych par wybrac, zeby za
pomoca jak najmniejszej ilosci pokryc wszystkie jedynki.
A jesli sie uda czworkami to jeszcze lepiej.

To co proponowalem w poprzednim poscie, to najpierw sklejamy te
dwie 1 "samotne" po prawej stronie. Je mozna tylko na jeden sposob
skleic, wiec wyboru nie mamy [a^b^d+a^bd^]. Zostaje nam tabelka:

0 x x 1
x 0 1 x
0 0 1 1
0 0 0 0


Musimy teraz pokryc wszystkie pozostale 1, przy czym mozemy x
pokryc poraz drugi. Najprosciej to zrobic dwoma "kwadratami".


Czyli jeżeli z McKluskey'a wychodzi mi coś takiego:

a^b^ + a^bc + abc + a^ (1)

a z Karrnaught'a coś takiego :

a^ + abc + ca^ (2)

to jest to niby to samo?

Czy jest to samo .. zrob tabelke :-)

najpierw zauwaz ze a^ pokrywa tez a^b^ [a^b^+a^ = a^]
Pokrywa tez a^c, wiec mozemy obie skrocic do
a^ + abc (3)

W (1) latwo zauwazyc ze a^bc + abc = bc, wiec (3) mozemy skrocic do
a^ + bc (4)

Wyprowadzenie (4) bezposrednio z (2) lub (3) jest trudniejsze do
zauwazenia .. ale tak, jest prawdziwe a^ + abc = a^ + bc

Jak widac ta sama funkcje mozna zapisac na 4 sposoby [i wiecej],
i zadna z metod nie uzyskales dobrej minimalizacji :-)

Na oko to jednak to jest to inna funkcja niz z poczatkowej tabelki.

Kumplom to normalnie po obu stronach (tj. w obu metodach) wychodziło to
samo ...

No i generalnie powinno, choc np w takiej tabelce
0 1 1 1
0 1 0 1
0 1 1 1
0 0 0 0

sa dwa rownie dobre rozwiazania i co wyjdzie to od szczescia zalezy.

J.


Poprzedni Następny
Wiadomość
Spis treści
From: qqq <qqq_at_nospam_interia.pl>
Subject: Re: metoda Karnaught'a
Date: Thu, 05 May 2005 19:10:00 +0200



Na oko to teraz trzeba zakreslic grupy
y1+y3 [~b3*~b2*b0]
y4+y6 [~b3*b2*~b0]
y3+y2+y7+y6
y7+y6+y14+y15

A jeszcze takie pytanie. Ze tak można je zakreślić, to się domyśliłem,
ale jak teraz można obliczyć, ile wynoszą wartości tych grup po 4 ?
Właśnie tego nie wiem, jak je obliczyć. Potrafie obliczyć daną wartość
dla 2-ch jedynek (np. dla y1+y3 wartość ta wynosi a^b^d)
Z wikipedii wiem, że wartość y3+y2+y7+y6 wynosi a^c, ale skąd się to
wieło? Jak właśnie to odczytać z tabelki? I jaka będzie wartość dla
y7+y6+y14+y15 ??

Poprzedni Następny
Wiadomość
Spis treści
From: qqq <qqq_at_nospam_interia.pl>
Subject: Re: metoda Karnaught'a
Date: Thu, 05 May 2005 19:20:28 +0200


qqq napisał(a):

Na oko to teraz trzeba zakreslic grupy
y1+y3 [~b3*~b2*b0]
y4+y6 [~b3*b2*~b0]
y3+y2+y7+y6
y7+y6+y14+y15


A jeszcze takie pytanie. Ze tak można je zakreślić, to się domyśliłem,
ale jak teraz można obliczyć, ile wynoszą wartości tych grup po 4 ?
Właśnie tego nie wiem, jak je obliczyć. Potrafie obliczyć daną wartość
dla 2-ch jedynek (np. dla y1+y3 wartość ta wynosi a^b^d)
Z wikipedii wiem, że wartość y3+y2+y7+y6 wynosi a^c, ale skąd się to
wieło? Jak właśnie to odczytać z tabelki? I jaka będzie wartość dla
y7+y6+y14+y15 ??


Kurde, jak napisałem posta to załapałem, jak się odczytuje wartości dla
4-rech :-P
Ale jeszcze jeden szkopuł mnie niepokoi. Jak zrobie takie dwa kwadraty,
to wtedy przez y6 będą biegły 3 takie grupy, a jak dobrze pamiętam, to
nauczyciel mówił, że mogą przechodzić tylko dwie. To jak to w końcu jest?

Poprzedni Następny
Wiadomość
Spis treści
From: J.F. <jfox_xnospamx_at_nospam_poczta.onet.pl>
Subject: Re: metoda Karnaught'a
Date: Thu, 05 May 2005 20:47:50 +0200


On Thu, 05 May 2005 19:20:28 +0200, qqq wrote:
Ale jeszcze jeden szkopuł mnie niepokoi. Jak zrobie takie dwa kwadraty,
to wtedy przez y6 będą biegły 3 takie grupy, a jak dobrze pamiętam, to
nauczyciel mówił, że mogą przechodzić tylko dwie. To jak to w końcu jest?

moze "biec" dowolna ilosc.
W koncu to OR - wystarczy choc jedna jedynka, nie mowi sie na ilu
wejsciach.

J.

P.S. Troche inaczej jest gdybys wysylal plytke w kosmos - wtedy
moze to przeszkodzic porzadnemu przetestowaniu plytki ..


Poprzedni Następny
Wiadomość
Spis treści
From: qqq <qqq_at_nospam_interia.pl>
Subject: Re: metoda Karnaught'a
Date: Thu, 05 May 2005 22:21:27 +0200



Już mi się udało, wyszło wszystko :D
Dzieki serdeczne za pomoc, bez Ciebie by mi się nie udało - masz u mnie
piwo ;>

Pozdro i jeszcze raz thx ;]