- Tytuł:
-
Zastosowanie hipergrafów w procesie selekcji implikantów prostych
Application of hypergraphs to the prime implicant selection process - Autorzy:
-
Wiśniewski, R.
Stefanowicz, Ł. - Powiązania:
- https://bibliotekanauki.pl/articles/155992.pdf
- Data publikacji:
- 2013
- Wydawca:
- Stowarzyszenie Inżynierów i Techników Mechaników Polskich
- Tematy:
-
minimalizacja funkcji logicznych
selekcja implikantów prostych
hipergraf
transwersala dokładna
minimization of Boolean functions
selection of prime implicants
hypergraph
exact transversal - Opis:
-
W referacie przedstawiona została nowa koncepcja selekcji implikantów prostych w procesie dwupoziomowej minimalizacji funkcji logicznych. Aktualnie znane metody selekcji bazują na połączeniu metod dokładnych z przybliżonymi. W artykule zaproponowana została nowatorska metoda selekcji, która w całości opiera się na algorytmach dokładnych, poprzez zastosowanie teorii hipergrafów. Najbardziej istotną zaletą proponowanego rozwiązania jest wielomianowa złożoność obliczeniowa całej operacji selekcji, która w przypadku ogólnym ma złożoność wykładniczą.
: In the paper a new idea for the selection of prime implicants is proposed. The method is based on the two-level minimization process of the Boolean functions, according to the Quine-McCluskey approach. Initially, the set of prime implicants for the logic function ought to be calculated. Next, the selection process is applied to achieve the minimal formula. Such an operation is a typical covering problem and in general case it has exponential computational complexity. In the paper we propose a new prime implicants selection method. An idea is based on the hypergraph theory. The prime implicants table is formed as a selection hypergraph. If the selection hypergraph belongs to the Exact Transversal Hypergraph class (xt-class), the solution may be obtained in a polynomial time, which is not possible in a general case. The proposed method is illustrated by an example. All necessary steps are shown in order to apply the proposed selection algorithm to minimize an exemplary Boolean function. - Źródło:
-
Pomiary Automatyka Kontrola; 2013, R. 59, nr 11, 11; 1195-1197
0032-4140 - Pojawia się w:
- Pomiary Automatyka Kontrola
- Dostawca treści:
- Biblioteka Nauki
Artykuł