Dekompozycja funkcji logicznych metodą rozwojowego programowania genetycznego

Praca przedstawia metodę wyszukiwania strategii dekompozycji funkcji logicznych za pomocą rozwojowego programowania genetycznego. Strategia dekompozycji jest reprezentowana w formie drzewa decyzyjnego, w którym węzły określają jeden krok dekompozycji. Drzewo podlega ewolucji, której celem jest uzyskanie jak najlepszego rozwiązania. Otrzymane wyniki wykonanych eksperymentów wskazują na wysoką skuteczność przedstawionej metody w porównaniu z dotychczas stosowanym podejściem deterministycznym.

Functional decomposition splits logical function into two simpler functions. For complex functions the decomposition should be repeated iteratively for the result functions. It was observed that types of decomposition applied during each step have strong influence on the final result. Thus, a proper decomposition strategy should be used to find optimal FPGA implementation for a given function. This paper presents the method for searching the decomposition strategy for logical functions specified by cubes. The strategy is represented using the decision diagram, in which each node corresponds to a single decomposition step. In this way the multistage decomposition of a complex logical function can be specified. The diagram is evolved using the developmental genetic programming. In opposite to classical genetic methods, in our approach the methods producing solutions, instead of the solutions, are evolved. The goal of the evolution is to find the decomposition strategy for which the cost of FPGA implementation of a given function is minimal. The experimental results show that our approach gives significantly better solutions than other known methods.