Informacja

Drogi użytkowniku, aplikacja do prawidłowego działania wymaga obsługi JavaScript. Proszę włącz obsługę JavaScript w Twojej przeglądarce.

Tytuł pozycji:

Zastosowanie hipergrafów w procesie selekcji implikantów prostych

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
Źródło:
Pomiary Automatyka Kontrola; 2013, R. 59, nr 11, 11; 1195-1197
0032-4140
Język:
polski
Prawa:
CC BY: Creative Commons Uznanie autorstwa 3.0 Unported
Dostawca treści:
Biblioteka Nauki
Artykuł
  Przejdź do źródła  Link otwiera się w nowym oknie
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.

Ta witryna wykorzystuje pliki cookies do przechowywania informacji na Twoim komputerze. Pliki cookies stosujemy w celu świadczenia usług na najwyższym poziomie, w tym w sposób dostosowany do indywidualnych potrzeb. Korzystanie z witryny bez zmiany ustawień dotyczących cookies oznacza, że będą one zamieszczane w Twoim komputerze. W każdym momencie możesz dokonać zmiany ustawień dotyczących cookies