Conception of partial specification of logic controller deterministic state machine

• Autorzy: Łabiak G.

Warianty tytułu

PL

Koncepcja niepełnej specyfikacji deterministycznej maszyny stanów sterownika logicznego

• Języki publikacji: EN

Abstrakty

EN

The issue of creating a deterministic behaviour description (without conflicts between transitions) of a logic controller is an issue of computational complexity equal to a classic satisfiability problem. Its solution through by-hand transition predicates construction can be very painstaking and tedious, if possible at all. The paper focuses on automatic transition predicates construction where transition predicates are partially specified by a designer giving only the most essential information necessary to comprehend the controller behaviour. This partial specification causes that a state machine (statechart diagram) is nondeterministic (and hence cannot be technically implemented) and the CAD system task is to transform automatically this partial specification into a corresponding deterministic form.

PL

Zagadnienie stworzenia deterministycznego opisu zachowania sterownika logicznego (bez konfliktów między tranzycjami) opisanego diagramami statecharts [2, 9] jest zagadnieniem o złożoności problemu spełnialności i jego rozwiązanie poprzez "ręczne" konstrukcje predykatów tranzycji może być dla projektanta bardzo trudne o ile w ogóle możliwe. Referat skupia się na problemie automatycznego doboru predykatów tranzycji w warunkach niepełnej specyfikacji, tak aby maszyna stanów [2, 9] (diagram statechart, rys. 3a) modelowała zachowanie w sposób deterministyczny. W proponowanej metodzie projektant podaje najistotniejsze zdarzenia warunkujące przejścia, a system CAD automatycznie rozwiązuje konflikty tranzycji niepełnej specyfikacji. Podstawową koncepcją automatycznego rozwiązywania konfliktów tranzycji jest utworzenie własnego zestawu wszystkich zmiennych dla każdej tranzycji osobno (podrozdz. 4.1). Nowo utworzone zmienne wyznaczają bazę symbolicznej przestrzeni wektorowej, w której można przestawić wszystkie możliwe predykaty (podrozdz. 4.2). W przestrzeni symbolicznej w łatwy sposób można opisać wyrażeniem logicznym zbiór wszystkich predykatów ortogonalnych oraz zbiory odpaleń wynikające z niepełnej specyfikacji (podrozdz. 4.3). Iloczyn w przestrzeni symbolicznej zbiorów predykatów ortogonalnych i zbiorów odpaleń wyznacza zbiór zestawów ortogonalnych predykatów wynikających z częściowej specyfikacji (podrozdz. 4.4). Wszystkie operacja na zbiorach wykonywane są jako logiczne przekształcenia odpowiednich funkcji charakterystycznych, które efektywnie mogą być implementowane za pomocą binarnych diagramów decyzyjnych [7].

Słowa kluczowe

EN

deterministic state machine; statechart diagrams; logic controller; transition conflicts; predicates; Boolean algebra; symbolic methods; metody symboliczne

PL

deterministyczna maszyna stanów; diagramy statechart; sterownik logiczny; konflikty tranzycji; predykaty; algebra Boole'a

• Wydawca: Wydawnictwo PAK
• Czasopismo: Pomiary Automatyka Kontrola
• Rocznik: 2012
• Tom: R. 58, nr 1
• Strony: 76--79
• Opis fizyczny: Bibliogr. 9 poz., rys., wzory

Twórcy

autor

Łabiak G.

• Uniwersytet Zielonogórski, Instytut Informatyki i Elektroniki, ul. Licealna 9, 65-417 Zielona Góra, Poland,

Bibliografia

• [1] Graham R. L., Knuth D. E., Patashnik O.: Concrete Mathematics: A Foundation for Computer Science, 2nd Edition, Addison-Wesley Professional, 1994.
• [2] Harel D.: Statecharts. A Visual Formalism for Complex Systems, Science of Computer Programming 8, 231-274, 1987.
• [3] Harel D. and Naamad A.: The STATEMATE Semantics of Statecharts, ACM Trans. Soft. Eng. Method, 1996.
• [4] Lipski W.: Kombinatoryka dla programistów, WNT, Warszawa, 1989.
• [5] Łabiak G.: Transition Conflicts Detection in Binary Modular Statechart Diagrams, PDS, s. 192-197, Kraków 2004.
• [6] Łabiak G.: Wykorzystanie hierarchicznego modelu współbieżnego automatu w projektowaniu układów cyfrowych, Oficyna Wydawnicza Uniwersytetu Zielonogórskiego 2005.
• [7] Minato S.: Binary Decision Diagrams and Applications for VLSI CAD, Kluwer Academic Publishers, Nov. 1996.
• [8] Moon J. W. and Moser L.: On cliques in graphs, Israel Journal of Mathematics, 3(1):23-28, 1965.
• [9] UML: OMG Unified Modeling Language TM (OMG UML), Superstructure, Version 2.3, Object Management Group, OMG, 2010.