Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: implikanty proste

Sortuj według:

Ogranicz wyniki do:

Novel method to simplify Boolean functions

Prasad V. C.

Automatyka / Automatics

2018

Vol. 22, no. 2

29--40

Most methods for determining the prime implicants of a Boolean function depend on the minterms of the function. Deviating from this philosophy, this paper presents a method that dependson maxterms (the minterms of the complement of the function) for this purpose. Normally, maxterms are used to get prime implicates and not prime implicants. It is shown that all prime implicants of a Boolean function can be obtained by expanding and simplifying any product of sums form of the function appropriately. No special form of the product of the sums is required. What is more, prime implicants can generally be generated from any form of the function by converting it into a POS using well-known techniques. The prime implicants of a product of Boolean functions can be obtained from the prime implicants of individual Boolean functions. This allows us to handle big functions by breaking them into the products of smaller functions. A simple method is presented to obtain one minimal set of prime implicants from all prime implicants without using minterms. Similar statements also hold for prime implicates. In particular, all prime implicates can be obtained from any sum of a products form.Twelve variable examples are solved to illustrate the methods.

Większość metod wyznaczania implikantów prostych funkcji boolowskiej wykorzystuje mintermy funkcji. Niniejszy artykuł prezentuje odmienną metodę, która stosuje do tego celu makstermy (mintermy dopełnienia funkcji). Jest to podejście niestandardowe, gdyż zazwyczaj na podstawie makstermów uzyskuje się implicenty proste, a nie implikanty proste. W artykule pokazano, że wszystkie implikanty proste funkcji boolowskiej mogą być otrzymane przez odpowiednie rozwinięcie i uproszczenie funkcji podanej w dowolnej postaci typu iloczyn sum. Nie jest przy tym wymagana żadna szczególna postać tego iloczynu. Co więcej, implikanty proste mogą być zwykle utworzone na podstawie funkcji w dowolnej postaci, przez przekształcenie jej do postaci typu iloczyn sum z wykorzystaniem znanych metod. Implikanty proste iloczynu funkcji boolowskich można uzyskać z implikantów prostych poszczególnych funkcji. To pozwala operować na dużych funkcjach przez rozbicie ich na iloczyn mniejszych. Artykuł pokazuje prostą metodę uzyskania jednego zbioru minimalnego implikantów prostych na podstawie zbioru wszystkich implikantów prostych bez korzystania z mintermów. Podobne stwierdzenia mają zastosowanie także w przypadku implicentów prostych. W szczególności, wszystkie implicenty proste mogą być otrzymane z dowolnej formy typu suma iloczynów. Zaproponowana w artykule metoda została zilustrowana licznymi przykładami.

Algorytm selekcji wykorzystujący teorię hipergrafów

Stefanowicz Ł., Wiśniewski R., Adamski M.

Pomiary Automatyka Kontrola

2014

R. 60, nr 7

516--518

Artykuł porusza kwestię selekcji określonych elementów zbioru z wykorzystaniem teorii hipergrafów. Przedstawiona została idea wspólnego algorytmu selekcji, w przypadku takich problemów, jak selekcja podsieci automatowych w dekompozycji sieci Petriego, a także selekcja implikantów prostych w procesie miminalizacji funkcji logicznych. Jako bazowy algorytm, wykorzystano metodę transwersal dokładnych, jednocześnie usprawniając ją o alternatywną scieżkę w przypadku, kiedy dany hipergraf selekcji nie należy do klasy hipergrafu transwersal dokładnych. Jak pokazują badania, metoda może być dobrą alternatywą obok wykorzystywanych metod tradycyjnych.

The paper deals with the selection problem based on the hypergraph theory. There is presented an idea of a common selection algorithm for selection of State Machine Components and Prime Implicants. The exact transversal method was used as a baseline algorithm. It was improved by supporting it with an optional path when a given selection hypergraph did not belong to the xt-class (class of the exact transversal hypergraph). In this case, the exact transversal was searched. When it was unsuccessful, the regular transversal was searched. The studies prove that the method allows obtaining the exact solution when the selection hypergraph does not belong to the xt-class, but has an exact transversal. The presented results show that a hypergraph which does not belong to the xt-class may have an exact transversal enabling obtaining a solution which would be as good as the one obtained with the backtracking method. The exact solution was also obtained with the use of an ordinary transversal, which de facto indicated that the regular transversals allowed, in certain cases, obtaining the exact solution. It seems to confirm the aptly determined class of solutions of the proposed improvements. In some cases, the solution contained one extra subnet, but in one tested case, the solution turned out to be much worse than the exact one.