Karnaughen mapa

Karnaughen mapa (Karnaughen taula edo Veitchen diagrama bezala ere ezaguna, K-Mapa edo KV-Mapa moduan laburtua) aljebra Boolearraren funtzioak sinplifikatzeko erabiltzen den diagrama bat da. Karnaugh-en mapa 1953an asmatu zuen Maurice Karnaughek^[1], Bell laborategietako fisikari eta matematikariak.

Karnaughen mapek adierazpen boolearrak sinplifikatzeko egin beharreko kalkulo luzeen beharra murrizten dute; baldintza oso zailak identifikatu eta kentzeko, gizakien burmuinaren zenbait gaitasun erabilita (patroiak antzematea, eta beste hainbat adierazpen analitiko era, esaterako).

Prozesua ondokoa da: lortutako emaitza Boolearrak egia taula batetik bi dimentsioko sare batera pasatzen dira, non lerro eta zutabeen ordena Gray kodea^[2]^[3] jarraituz egiten den, eta gelaxka bakoitzak sarreren konbinazio bat adierazten duen, eta bertan idatzitako balioak dagokion irteerako balioa. Behin hau eginda, 0 edo 1 multzoak egiten dira, ahalik eta handienak, hasierako egia taularen forma kanonikoaren terminoak definituko dituztenak. Termino hauek adierazpen Boolearraren sinplifikaziorako beharrezkoak diren ate logikoen konbinazioak izango dira; izan ere, biderkaduren baturen adierazpenak, OR ate batera sartzen diren AND ateen irteera moduan diseina daitezke; eta, baturen biderkadurak, AND ate batera sartzen diren OR ateen irteera bezala. Beraz, behin sinplifikatuta, AND eta OR ate logikoen konbinazio bezala adieraz daiteke emaitza.

Mapari dagokionez, N aldagaiko funtzio baten egia taulak 2^N lerro dituenez, dagokion K-Mapak ere 2^N lauki izango ditu. Aldagaiak, Gray kodearen arabera, eta bakoitzaren pisuari erreparatuta ordenatzen dira, horrela, ondoz ondoko gelaxka batetik bestera aldagai bakarra aldatuko da. Egia taulako gai bakoitza Karnaughen mapara pasatzeko prozesua zuzenekoa da, 0 edo 1 jarriz, lerro bakoitzean funtzioak duen balioaren arabera. 6 aldagaira arteko Karnaughen mapak erraz egin daitezke eskuz, baina aldagai gehiagoko funtzioetarako, gomendagarria da software espezializatuen erabilera.

Maparen lerro eta zutabeen kopuruaren kalkulua aldatu

Normalean, Karnaughen maparen lerro eta zutabeak mapa karratu bezala irudikatzen dira (lerro kopurua = zutabe kopurua) aldagai kopurua bikoitia denean (2, 4, 6...); hala ere, aldagai kopurua bakoitia denean, lerro kopurua zutabe kopuruaren erdia da, ondoko formuletan ikus daitekeen bezala:

Aldagai kopurua bikoitia denean:

$lerroak=zutabeak={\sqrt {2^{aldagaiak}}}$

Aldagai kopurua bikoitia denean:

$zutabeak={\sqrt {2^{aldagaiak+1}}}$

$lerroak={zutabeak \over 2}$

Adibidea aldatu

Karnaughen mapak funtzio Boolear aljebraikoak sinplifikatzeko erabiltzen dira. Adibidez, $A,B,C,D$ aldagai boolearrak dituen funtzio baten egia taula ondokoa litzeteke:


#	A	B	C	D	f(A,B,C,D)
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
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	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

Ondokoak dira funtzio bera aljebra Boolear sinplifikatu gabean adierazteko bi era, A, B, C, D aldagai Boolearrak eta euren alderantzizkoak erabilita.

$f(A,B,C,D)=\sum m_{i},i\in \{6,8,9,10,11,12,13,14\}$ non $m_{i}$ mapeatzeko mintermak diren (egia taulan 1 irteera duten lerroak).
$f(A,B,C,D)=\prod M_{i},i\in \{0,1,2,3,4,5,7,15\}$ non $M_{i}$ mapeatzeko maxtermak diren (egia taulan 0 irteera duten lerroak).

Karnaughen mapa aldatu

K-mapa toroide eta plano batean irudikatuta. Puntuekin adierazitako gelaxkak ondoz ondokoak dira.

Karnaughen maparen eraikuntza. Irteerako balioak erakutsi beharrean (egia taulako eskuinaldekoak), diagrama honek ABCD sarreren irudikapen hamartarra egiten du (egia taulako ezkerraldekoak), beraz ez da Karnaughen mapa bat.

Sarrerako aldagaiak 16 era ezberdinetan konbina daitezke, horrela, Karnaughen mapak 16 gelaxka izango ditu, 4 x 4-ko lauki-sarean banatuta. Lerro eta zutabeen ordenari dagokienez, 4 aldagaiko tauletan, ondoz ondoko bi zutabe "01" eta "11" dira ("10" izan beharrean, hurrengo balio bitarra izango litzatekeena); honen arrazoia maparen eraikuntzarako baldintza da, hau da, taulara sartzen den zutabe bakoitzean (ezkerretik eskumara) aurrekoarekiko bit bakarra alda daiteke. Hau horrela izanik, "01" zutabearen ostean, "11" etorriko litzateke, bit bakarra aldatzen delarik, "01" zutabetik "10" zutabera gertatuko ez litzatekeena, bi bitak aldatuko bailirateke.

Hau esanda, maparen zutabe eta lerroak izendatzeko Gray kodea erabiltzen da, kode bitarra erabili beharrean. Gray kodeak ondoz ondoko gelaxka batetik bestera aldagai bakarra aldatuko dela ziurtatzen du.

Betetako mapako gelaxka bakoitzak digitu bitar bat dauka, sarrera konbinazio horrentzako funtzioak daukan emaitza adierazten duena.

Behin Karnaughen mapa eraikita, mapa bera egia taulako informazioa adierazteko era sinpleenetako bat (forma kanonikoa) bilatzeko erabiltzen da. Mapan agertzen diren ondoz ondoko 1ek sinplifikatzeko aukera ematen dute; izan ere, amaierako adierazpenerako mintermak ("minimal term") mapako 1 taldeak borobilduz aurki daitezke. Minterm taldeak laukiak izan behar dira, eta azalera biren berredura izan behar da (1, 2, 4, 8...). Minterm laukiak ahalik eta handienak izan behar dira, 0 bat ere ez eduki gabe. Multzoek bata bestea zapal dezakete handiagoak izan ahal izateko. Esaterako, geroagoko adibidean, talde gorria 2 x 2 dimentsioko karratu bat da, eta berdea 4 x 1 dimentsioko laukia; marroia, bien arteko zapalkuntza da.

Sarea era toroidalean konektatuta dago, beraz, laukiak ertzen inguruan borobildu daitezke. Hau da, eskuin muturreko gelaxkak ezker muturrekoen ondoz ondokoak dira, batetik bestera bit bakarra aldatzen delarik; gauza bera gertatzen da goiko eta beheko ertzekin.

Soluzioa aldatu

Bi K-mapadun diagrama. f(A, B, C, D) funtzioaren K-mapa koloredun laukietan ageri da, mintermei dagozkienak. Alde marroia gorriaren eta berdearen arteko zapalgunea da. Alderantzizkoaren K-mapa grisez agertzen da, maxtermei dagozkienak.

Behin Karnaughen mapa eraikita eta ondoz ondoko 1ak lauki eta karratuetan sartuta, minterm aljebraikoak eratutako kutxa bakoitzean berdin mantentzen diren aldagaiak aztertuz lortzen dira.

Karratu gorrirako:

A berdina da (1) kutxa osorako, beraz, minterm gorriaren adierazpen aljebraikoan agertu beharko da.
B ez da berdin mantentzen (1 eta 0 balioak hartzen ditu), beraz, ez da adierazpenean agertuko.
C ez da aldatzen, denbora osoan da 0, beraz NOT-C agertu beharko da adierazpenean ( ${\bar {C}}$ ).
D aldatu egiten da, ondorioz, ez da agertuko.

Hau horrela, produktuen baturako adierazpen Boolearrean, lehen minterma $A{\bar {C}}$ izango da.

Kutxa berdean, A eta B berdin mantentzen dira, eta C eta D aldatu egiten dira. B 0 da, beraz, ezeztatu egin behar da erabili baino lehen. Laburbilduz, bigarren batutzailea $A{\bar {B}}$ da.

Prozesu berdina jarraituz, lauki urdinetik $BC{\bar {D}}$ lor daiteke.

Emaitza guztiak batuz, zirkuituaren ekuazio normalizatua ondokoa dela lortuko litzateke: $A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}$ .

Ondorioz, Karnaughen mapak hurrengo sinplifikazioa egitea lortu du: ${\begin{aligned}f(A,B,C,D)={}&{\overline {A}}BC{\overline {D}}+A{\overline {B}}\,{\overline {C}}\,{\overline {D}}+A{\overline {B}}\,{\overline {C}}D+A{\overline {B}}C{\overline {D}}+{}\\&A{\overline {B}}CD+AB{\overline {C}}\,{\overline {D}}+AB{\overline {C}}D+ABC{\overline {D}}\\={}&A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}\end{aligned}}$

Alderantzizkoa aldatu

f(A,B,C,D)

funtzioaren balioa ABCD = 1111 kasurako, "ez du axola" batekin ordezkatu da. Honen ondorioz, termino berdea erabat desagertu da, eta gorria handiagoa izatea ahalbidetu du.

Funtzio baten alderantzizkoa, 1ak beharrean, 0ak multzokatuz lortzen da.

Adibidearen kasuan, alderantzizkoaren terminoak grisez, kolore ezberdinetako ertzekin, ageri dira:

Marroia: ${\bar {A}}{\bar {B}}$
Urrea: ${\bar {A}}{\bar {C}}$
Urdina: $BCD$

Alderantzizkoa horrela adierazten da:

${\overline {f(A,B,C,D)}}={\bar {A}}{\bar {B}}+{\bar {A}}{\bar {C}}+BCD$

Honez gain, De Morgan-en legeei esker, baturen produktua kalkula daiteke:

${\begin{aligned}f(A,B,C,D)&={\overline {\overline {f(A,B,C,D)}}}\\&={\overline {{\overline {A}}\,{\overline {B}}+{\overline {A}}\,{\overline {C}}+BCD}}\\&=\left({\overline {{\overline {A}}\,{\overline {B}}}}\right)\left({\overline {{\overline {A}}\,{\overline {C}}}}\right)\left({\overline {BCD}}\right)\\&=\left(A+B\right)\left(A+C\right)\left({\overline {B}}+{\overline {C}}+{\overline {D}}\right)\end{aligned}}$

"Ez du axola" aldatu

Karnaughen mapak egia taulan "ez du axola" baldintzak dituzten funtzioak sinplifikatzea ere ahalbidetzen du. "Ez du axola" baldintza sarrera multzo baten irteerak inongo garrantzirik ez duenean gertatzen da, ez duenean axola irteera 1 edo 0 den. Beraz, "ez du axola" baldintzak laukietan sartu daitezke, ala ez, laukia handiagoa egingo duen aukera hartuz. Normalean, X edo marratxoaz adierazten dira mapan.

Eskuinaldeko adibidean, f(1,1,1,1) gelaxkaren balioa "ez du axola" batez ordezkatu da. Horrela, lauki gorria beheraino luzatzea ahalbidetu da, eta berdea desagerrarazi du.

Honen ekuazio minimoa horrela geratuko litzateke:

$f(A,B,C,D)=A+BC{\bar {D}}$

Ikus daitekeenez, lehen minterma $A$ da, eta ez $A{\bar {C}}$ . Kasu honetan, axola ez duen irteerari esker, termino bat desagertu da (berdea) eta beste bat sinplifikatu da (gorria).

Oraingoan, alderantzizko funtzioa horrela sinplifika daiteke:

${\overline {f(A,B,C,D)}}={\bar {A}}{\bar {B}}+{\bar {A}}{\bar {C}}+{\bar {A}}D$

Erreferentziak aldatu

↑ Karnaugh, M.. (1953). «The map method for synthesis of combinational logic circuits» Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics 72 (5): 593–599. doi:10.1109/TCE.1953.6371932. ISSN 0097-2452. (Noiz kontsultatua: 2019-11-23).
↑ Wakerly, John F.. (1994). Digital design : principles and practices. (2nd ed. argitaraldia) Prentice Hall ISBN 0-13-211459-3. PMC 29386744. (Noiz kontsultatua: 2019-11-23).
↑ Brown, Frank Markham, 1930-. Boolean reasoning : the logic of Boolean equations. (Second edition. argitaraldia) ISBN 978-1-137-53493-4. PMC 867768749. (Noiz kontsultatua: 2019-11-23).

Ikus, gainera aldatu

Kanpo estekak aldatu

Detect Overlapping Rectangles, Herbert Glarner.
Using Karnaugh maps in practical applications, Circuit design project to control traffic lights.
K-Map Tutorial for 2,3,4 and 5 variables
Karnaugh Map Example
POCKET–PC BOOLEAN FUNCTION SIMPLIFICATION, Ledion Bitincka — George E. Antoniou

Datuak: Q461528
Multimedia: Karnaugh maps / Q461528

[1] Karnaugh, M.. (1953). «The map method for synthesis of combinational logic circuits» Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics 72 (5): 593–599. doi:10.1109/TCE.1953.6371932. ISSN 0097-2452. (Noiz kontsultatua: 2019-11-23).

[2] Wakerly, John F.. (1994). Digital design : principles and practices. (2nd ed. argitaraldia) Prentice Hall ISBN 0-13-211459-3. PMC 29386744. (Noiz kontsultatua: 2019-11-23).

[3] Brown, Frank Markham, 1930-. Boolean reasoning : the logic of Boolean equations. (Second edition. argitaraldia) ISBN 978-1-137-53493-4. PMC 867768749. (Noiz kontsultatua: 2019-11-23).

[1]

[2]

[3]

#	A	B	C	D	f(A,B,C,D)
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
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	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

#	A	B	C	D	f(A,B,C,D)
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
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	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0

#	A	B	C	D	f(A,B,C,D)
0	0	0	0	0	0
1	0	0	0	1	0
2	0	0	1	0	0
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	1
13	1	1	0	1	1
14	1	1	1	0	1
15	1	1	1	1	0