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, 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 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 2N lerro dituenez, dagokion K-Mapak ere 2N 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 
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:

 Aldagai kopurua bikoitia denean:

Adibidea 
Karnaughen mapak funtzio Boolear aljebraikoak sinplifikatzeko erabiltzen dira. Adibidez,  aldagai boolearrak dituen funtzio baten egia taula ondokoa litzeteke:

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

  non  mapeatzeko mintermak diren (egia taulan 1 irteera duten lerroak).
  non  mapeatzeko maxtermak diren (egia taulan 0 irteera duten lerroak).

Karnaughen mapa 

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 

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 ().
 D aldatu egiten da, ondorioz, ez da agertuko.

Hau horrela, produktuen baturako adierazpen Boolearrean, lehen minterma  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  da.

Prozesu berdina jarraituz, lauki urdinetik  lor daiteke.

Emaitza guztiak batuz, zirkuituaren ekuazio normalizatua ondokoa dela lortuko litzateke: .

Ondorioz, Karnaughen mapak hurrengo sinplifikazioa egitea lortu du:

Alderantzizkoa 

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

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

 Marroia: 
 Urrea: 
 Urdina: 

Alderantzizkoa horrela adierazten da:

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

"Ez du axola" 
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:

Ikus daitekeenez, lehen minterma  da, eta ez . Kasu honetan, axola ez duen irteerari esker, termino bat desagertu da (berdea) eta beste bat sinplifikatu da (gorria).

Oraingoan, alderantzizko funtzioa horrela sinplifika daiteke:

Erreferentziak

Ikus, gainera 
 Zirkuitu minimizazio
 Venn diagrama
 Forma algebraiko normala

Kanpo estekak 
 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

Ingeniaritza
Diagramak