Minimalizacja - metoda tablic Karnaugha :: Ekspansja :: Redukcja argumentów :: Dekompozycja :: Rodzaje automatów :: Moor'a :: Mealy'ego :: (a)synchroniczne :: Synteza automatów :: Minimalizacja automatów (liczby stanów) - synchroniczne :: Minimalizacja automatów (liczby stanów) - asynchroniczne

Elementy teorii układów logicznych

Podstawowym podziałem jest podział na układy kombinacyjne (stan ich zależy tylko od aktualnego wejścia) oraz sekwencyjne (stan ich zależy od aktualnego wejścia oraz historii układu). Na potrzeby teoretycznej analizy układów kombinacyjnych często stosuje się ich opis z wykorzystaniem tabeli gdzie kolejne wiersze odpowiadają różnym wektorom pobudzającym (kodowanym w NKB) a kolumny pokazują sygnały na wyjściach układu.

Minimalizacja - metoda tablic Karnaugha

Aby uzyskać wyrażenie na opisywaną przez tablicę funkcję wypisujemy w oparciu o zakreślenia:

  1. jedynek - sumę ilorazów zadanych przez zmienne niezmieniające się w ramach pętelki,
  2. zer - iloraz sum zadanych przez zanegowane zmienne niezmieniające się w ramach pętelki.

Możemy także wypisać funkcję zaprzeczoną - w tym celu dla obejmowania pętelkami jedynek postępujemy jak w pkt. 2 a dla zer jak w pkt. 1 (zamieniamy rolami zera z jedynkami w wartościach funkcji podanych w tablicy).

Warto także zapoznać się z komputerowym systemem minimalizacji funkcji logicznych espresso. Zamieszam także skrypt do generowania plików PLA na podstawie wyrażenia boolowskiego - expr2pla.sh

Ekspansja

macierz blokująca

Macierz blokująca dla kostki ki (i funkcji f) jest to macierz utworzona z macierzy wektorów ri dla których f ma wartość 0, poprzez zanegowanie kolumn o indeksach j dla których kij=1.

pokrycie kolumnowe

Jest to zbiór kolumn Lj takich że w każdym wierszu co najmniej jedna z kolumn ma wartość 1. Minimalnym pokryciem nazywamy takie pokrycie, dla którego usunięcie z niego jakiejkolwiek kolumny sprawiłoby że przestaje być ono pokryciem. Możemy także wprowadzić relację mniejszości pokrycia równoważną relacji mniejszości ilości kolumn składających się na pokrycie.

Minimalne pokrycia obliczamy poprzez minimalizację wyrażenia: $$\bigcap_i \left( \bigcup_{j: b_{ij}=1} L_j \right)$$. Wyrażenie doprowadzamy do postaci sumy iloczynów, reprezentującej wszystkie minimalne pokrycia kolumnowe zadanej macierzy B.

implikanty proste

Implikanty uzyskujemy poprzez wybór z wektora ki wartości kij dla kolumn wchodzących w skład minimalnego pokrycia kolumnowego, gdy kij = 1 to do implikantu wchodzi xj w przeciwnym wypadku (kij = 0) wchodzi wartość zanegowana $$\bar x_j$$.

selekcja najlepszych implikantów

Najpierw ustalamy które kostki ki pokrywają dany implikant Ij (kostka pokrywa implikant gdy dla każdej wartości z kostki implikant ma wartość z nią zgodną lub dowolną). Następnie tworzymy macierz P o kolumnach zawierającą informację o tym pokrywaniu (gdy kj pokrywa Ij to pij = 1, w przeciwnym wypadku jest 0) i obliczamy minimalne pokrycie kolumnowe. Suma implikantów z minimalnego pokrycia kolumnowego stanowi minimalną formułę dla funkcji początkowych.

Redukcja argumentów

podział

Podziałem nazywamy system zbiorów o rozłącznych blokach, których suma daje cały zbiór. Podział A jest nie większy od B gdy każdy blok A zawiera się w jakimś bloku B.

Iloczyn podziałów (największy podział nie większy od każdego z wchodzących w skład iloczynu) obliczamy grupując elementy w bloki tak aby każdy z bloków zawierał się w jakimś bloku każdego z składników oraz aby były to bloki możliwie największe.
$$A=\{\overline{1,2,3}, \overline{4}\}$$
$$B=\{\overline{1,2}, \overline{3,4}\}$$
$$A \cdot B = \{\overline{1,2}, \overline{3}, \overline{4}\}$$

Ilorazem podziałów nazywamy podział (dzielony) z blokami złożonymi z powiększonych elementów (stanowiących bloki podziału przez który dzielimy).
$$A=\{\overline{1,2,3}, \overline{4}\}$$
$$B=\{\overline{1,2}, \overline{3}, \overline{4}\}$$
$$A / B = \{\overline{(1,2),(3)}, \overline{(4)}\}$$

procedura redukcji

Obliczamy iloczyn podziałów względem zmiennych niezbędnych (zmiennych na których różnią się dwa wektory dla których funkcja ma różne wartości i nie mają one innych różnych pozycji) i dzielimy go przez podział względem wyniku zwracanego przez funkcję. Następnie znajdujemy pozycje na których różnią się wektory o numerach należących do różnych elementów składających się na obliczony podział. (dla powyższego przykładu będą to różnice pomiędzy wektorem 3 a 1 i 3 a 2). Ostatecznie obliczamy iloczyn sum tych zmiennych (na którym różnią się wektory). Po przekształceniu go na sumę iloczynów każdy składnik tej sumy wraz z zmiennymi niezbędnymi stanowi zestaw argumentów, oczywiście wybieramy ten najmniejszy ... .

Dekompozycja

Czyli (rozsądny) podział na podfunkcje (tak aby każda z nich zależała od mniejszej liczby zmiennych niż wejściowa)

Tworzymy macierz gdzie kolumny odpowiadają pewnemu podzbiorowi argumentów wejściowych, a wiersze reszcie zbioru argumentów wejściowych. Wyszukujemy w niej kolumny zgodne (o takich samych wartościach lub akceptujące takie same wartości). Dokonujemy optymalnego sklejenia kolumn zgodnych otrzymując w ten sposób funkcję g o ilości argumentów nie większej niż wielkość podzbioru przeznaczonego na opis kolumn oraz ilości wyjść odpowiadającej logarytmowi ilości kolumn po sklejeniu przybliżonemu w górę.

Obliczanie maksymalnych klas zgodnych metodą par zgodnych

Para zgodna = dwie kolumny zgodne ze sobą.

W oparciu o indeksy elementów wchodzących w skład par zgodnych tworzymy zbiory Ri. Ri jest zbiorem takich j że (i,j) jest parą zgodną oraz i>j.

Mając obliczone RJ generujemy rodzinę maksymalnych klas zgodnych wg następujących reguł:

  1. jeżeli Rk jest zbiorem pustym to rodzinę MKZ powiększamy o KZ k
  2. jeżeli Rk przecięty z KZ jest pusty to bez zmian
  3. jeżeli Rk przecięty z KZ jest nie pusty to to przecięcie powiększamy o k i zastępujemy nim daną KZ

Punkty 2 i 3 powtarzamy dla każdej klasy zgodnej w rodzinie. Jeżeli jakaś KZ zawiera się w innej to o niej zapominamy.

Obliczanie maksymalnych klas zgodnych metodą par sprzecznych

Pary sprzeczne to wszystkie pary które nie są zgodne. Poprzez zbudowanie wyrażenia boolowskiego typu iloczyn sum (gdzie każda suma jest zbudowana z jednej pary sprzecznej) i przekształcenie go do postaci sumy iloczynów, uzyskujemy rodzinę MKZ (każdy iloczyn wchodzący do tej sumy reprezentuje MKZ).

Rodzaje automatów

Automat jest opisem matematycznym dużej liczby układów cyfrowych, ułatwiających ich konstruowanie. Opiera się na wyróżnieniu dyskretnych stanów i czynników powodujących zmianę stanu. Zobacz też: Automat skończony, Deterministyczny automat skończony.

Moor'a

Automat Moore'a charakteryzuje się powiązaniem wyjść wyłącznie z stanem wewnętrznym automatu, czyli automat będący w określonym stanie zawsze ma takie samo wyjście. Automat możemy opisać przy pomocy grafu, gdzie wierzchołkami są stany z powiązanymi z nimi wyjściami, a krawędziami są przejścia pomiędzy stanami (wraz z powodującym je sygnałem). Inną formą prezentacji jest tabela przejść/wyjść, gdzie dla każdego stanu podane są stany następne do których automat przechodzi pod wpływem danego wektora oraz wyjście związane z aktualnym stanem:

stan obecnywektor wejściowy 1wektor wejściowy 2...wyjście
ABA...10
BCD...11
...

Mealy'ego

Automat Mealy'ego charakteryzuje się powiązaniem wyjść z stanem wewnętrznym automatu i jego wejściami. Automat możemy opisać przy pomocy grafu, gdzie wierzchołkami są stany, a krawędziami są przejścia pomiędzy stanami (wraz z powodującym je sygnałem i związanym z tym wyjściem automatu). Inną formą prezentacji jest tabela przejść/wyjść, gdzie dla każdego stanu podane są stany następne do których automat przechodzi pod wpływem danego wektora oraz wyjścia związane z aktualnym stanem i podanym wektorem wejściowym:

stan obecnywektor wejściowy 1wektor wejściowy 2...
AB/10A/11...
BC/01D/11...
...

(a)synchroniczne

Automatem synchronicznym nazywa się automat który działa zgodnie z zewnętrznym sygnałem taktującym, którego zbocze powoduje dokonanie przejścia stanu w automacie. Automat asynchroniczny stan swój zmienia natychmiast po zmianie wektora wejściowego (dowolnego z jego bitów). W tym wypadku należy mieć na szczególnej uwadze problemy związane z tym że nigdy nie możemy oczekiwać równoczesnej zmiany dwóch sygnałów co prowadzi do tego że np. przejście ze stanu kodowanego jako 11 na 00 będzie przez stan 10 albo 01. Prowadzi to do tak zwanych wyścigów. jeżeli automat może utknąć w którymś z tych stanów są to tzw. wyścigi krytyczne i należy je eliminować.

Synteza automatów

Synteza automatu sprowadza się do następujących kroków:

  • opis w postaci grafu
  • konwersja grafu na tablicę przejść/wyjść
  • kodowanie (numeracja stanów)
  • zapisanie tablicy przejść/wyjść w postaci tablicy Karnaugha
  • podział na tyle tablic ile bitów ma kod stanu (na każdy przerzutnik trzymający jeden bit numeru stanu automatu jedna tablica) - każda tablica jako wejścia przyjmuje poprzedni wektor stanu i aktualny wektor wejść
  • jeżeli używamy przerzutników innych niż D to należy dokonać konwersji tych tablic poprzez tablice dla poszczególnych typów przerzutników
  • minimalizacja tablic opisujących logikę podłączoną do danego przerzutnika
  • zdefiniowanie logi przekształcającej wektor stanu (i ew. wektor wejściowy jeżeli automat typu Mealy'ego) na wektor wyjściowy

Automat można zrealizować także w postaci układu mikro-programowalnego:
POWIĘKSZPrzykład projektu układu mikro-programowalnego

Minimalizacja automatów (liczby stanów) - synchroniczne

  • tworzymy tablicę trójkątną (kolumny 1 -> N-1, wiersze 2-> N) w której zaznaczamy dla każdej pary stanów czy jest ona:
    • zgodna (dla każdego wejścia stany mają niesprzeczne wyjścia i niesprzeczne stany następne)
    • warunkowo zgodna (dla każdego wejścia stany mają niesprzeczne wyjścia i niesprzeczne stany następne, pod warunkiem zgodności innych stanów) - wtedy zapisujemy warunki zgodności (jest to iloczyn logiczny)
    • sprzeczna (dla jakiegoś wektora wejściowego wyjścia są sprzeczne)
  • po wypełnieniu sprawdzamy dla każdej pary sprzecznej czy nie jest warunkiem w innej parze - jeżeli jest to tamta para też sprzeczna, powtarzamy to dla nowo powstałych par sprzecznych, aż dojdziemy do sytuacji że nie ma już nowo powstałych par sprzecznych
  • pozostałe pary (zgodne lub zgodne warunkowo) są parami zgodnymi
  • obliczamy MKZ (można jak opisano powyżej, ale najprościej poprzez grupowanie 3 par w trójkę, 4 trójek w czwórkę itd)
  • wybieramy takie MKZ aby spełnić warunek pokrycia (wszystkie stany muszą być w zbiorze wynikowym) i sprawdzamy czy jakiś stan z jednej grupy nie prowadzi do stanów z innej grupy
  • w tym celu sporządzamy tabelkę gdzie w kolumnach mamy kolejne MKZ, a w wierszach mamy ich reakcję na kolejne wektory wejściowe

Minimalizacja automatów (liczby stanów) - asynchroniczne

  • łączymy stany pseudo równoważne (mające stany stabilne w jednej kolumnie, niesprzeczne wyjścia oraz niesprzeczne stany następne), w tym etapie rozważamy zgodność warunkową
  • tworzymy graf zgodności (warunkiem jest niesprzeczność stanów następnych), stany o sprzecznych wyjściach umieszczamy, ale łączymy je linią przerywaną
  • przy automacie Mealy'ego możemy grupować stany o sprzecznych wyjściach (połączone linią przerywaną), robimy wtedy także tablicę wyjść:
    • przepisujemy wyjścia stanów stabilnych
    • przepisujemy wyjścia stanów niestabilnych (gdy dane wyjście nie jest wyjściem stabilnego z bieżącego wejścia to kreska)
    • uzupełniamy kreski
  • kodujemy tak aby uniknąć wyścigów krytycznych - przejścia przez stany niestabilne i/lub dodajemy dodatkowe stany


Copyright (c) 1999-2015, Robert Paciorek (http://www.opcode.eu.org/), BSD/MIT-type license


Redystrybucja wersji źródłowych i wynikowych, po lub bez dokonywania modyfikacji JEST DOZWOLONA, pod warunkiem zachowania niniejszej informacji o prawach autorskich. Autor NIE ponosi JAKIEJKOLWIEK odpowiedzialności za skutki użytkowania tego dokumentu/programu oraz za wykorzystanie zawartych tu informacji.

This text/program is free document/software. Redistribution and use in source and binary forms, with or without modification, ARE PERMITTED provided save this copyright notice. This document/program is distributed WITHOUT any warranty, use at YOUR own risk.

Valid XHTML 1.1 Dokument ten (URL: http://www.opcode.eu.org/digital/theory_of_systems) należy do serwisu OpCode. Autorem tej strony jest Robert Paciorek, wszelkie uwagi proszę kierować na adres e-mail serwisu: webmaster@opcode.eu.org.
Data ostatniej modyfikacji artykulu: '2015-10-10 11:33:43 (UTC)' (data ta może być zafałszowana niemerytorycznymi modyfikacjami artykułu).