Minimalizacja automatów skończonych z uwzględnieniem ich kosztu realizacji w układach programowalnych o strukturze CPLD

W pracy opisano heurystyczną metodę minimalizacji nie w pełni określonych automatów skończonych, która pozwala już na etapie minimalizacji stanów wewnętrznych uwzględniać parametry bazy technologicznej, metodę kodowania stanów oraz optymalizować koszt realizacji automatu w strukturze programowalnej. Opisano kryteria minimalizacji liczby stanów automatu ze względu na koszt ich realizacji w strukturze CPLD, gdzie głównym parametrem wpływającym na realizację jest liczba termów podłączonych do makrokomórki. Dodatkowym efektem działania metody jest minimalizacja liczby przejść automatu.

---

In the paper a heuristic method of minimization of incompletely specified finite state machines is described. This method allows taking into account parameters of technological base, the method of state assignment and realization costs. The presented method is focused on realization of an FSM in the CPLD structure. The method is based on an operation of merging two states. In addition to reducing internal states, this method minimizes the number of FSM transitions and FSM input variables. In contrast to the previously developed methods, in each step of the algorithm there is considered not only one, but the entire set of all pairs of states for which it is permissible to merge. Then the pair of states which best matches the criteria of minimizing is selected from the set. Two FSM states can be merged if they are equivalent. FSM behavior does not change after the states are merged, if the transition conditions from these states that lead to different states are orthogonal. If there are transi-tions from the states that lead to the same states, the transition conditions for such transitions should be equal. Moreover, the output vectors generated in these states should not be orthogonal. It should be noted that wait states can be formed at the merging of FSM states. This paper describes the criteria for minimizing the number of states of the machine because of the cost of their implementation in the CPLD structure, where the main parameter influencing the implementation is a number of terms connected to one macrocell.