Authors: Zakrevskij, Arkadij

Abstract: The task of simple decomposition of a Boolean function, generally non-disjunctive, is considered, its solution is reduced in main to search for appropriate weak partitions on the set of arguments. A special attention is paid to the case of presence of a good solution for the given Boolean function, in remaining random. To find it, a twostage heuristic combinatorial algorithm is offered, optimized on speed. At the first stage the randomized search for "traces" of the decomposition is fulfilled. These traces are represented by some "triads" - the simplest weak partitions corresponding to non-trivial decompositions. At the second stage the whole sought-for partition is restored from the discovered trace. The results of computer experiments confirming practical efficiency of the algorithm are quoted.

Keywords: boolean functions,decomposition methods,logic design

Identifier: 10.3182/20060926-3-PL-4904.00003

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Pottosin, Yuri; Shestakov, Eugeny

Abstract: The concept of generalized compact table as a form of specification of a Boolean function is introduced. This form is a further generalization of the decomposition chart and uses the concept of ternary matrix cover. A method for decomposition of a Boolean function using its representation in the form of generalized compact table is given.

Keywords: decomposition of Boolean functions,disjunctive normal form,ternary matrix

Identifier: 10.3182/20060926-3-PL-4904.00009

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Szpyrka, Marcin; Matyasik, Piotr; Piwowarczyk, Jacek

Abstract: The paper presents an RTCP-net approach to the verification of embedded systems implemented in Ada programming language. We focus on the verification of software implemented in accordance with Ada Ravenscar Profile. An RTCP-net model is constructed with the use of the Ada source code, and utilised for the formal verification of the software. An example of a driver for a home heating furnace is used to demonstrate the most important features of this approach.

Keywords: ADA 2005,Ravenscar profile,RTCP-nets,embedded systems,verification

Identifier: 10.3182/20060926-3-PL-4904.00034

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Pereira, Miguel; Soto, Enrique; Rodríguez-Andina, Juan J.

Abstract: High-speed telecommunications routers are very important systems in today's networked environments. In order to improve their quality of service, it is important to provide them with means to detect errors that affect their behaviour. If such detection is performed concurrently with normal operation, the negative effects of errors could be mitigated or even avoided, leading to fault-tolerant operation. This work concentrates on the scheduler part of the system and, in particular, on concurrent error detection in circuits implementing the well-known iSLIP scheduling algorithm. The faulty behaviour of complex digital processing systems is usually better described at the algorithmic level, particularly when the operation of the system relies on complex mathematical principles. Therefore, the issues related to concurrent error detection are addressed from a mathematical model of the target system. Results are presented that point to the ability of the proposed solution to detect errors at a high abstraction level.

Keywords: VOQ switch,iSLIP scheduling algorithm,concurrent error detection,statistical detector,behavioural fault modelling

Identifier: 10.3182/20060926-3-PL-4904.00013

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Komenda, Jan; Marchand, Hervé; Pinchinat, Sophie

Abstract: We plunge decentralized control problems into modular ones to benefit from the know-how of modular control theory: any decentralized control problem is associated to a natural modular control problem, which over-approximates it. Then, we discuss how a solution of the latter problem delivers a solution of the former.

Keywords: decentralized supervisory control,modular discrete-event systems,separability,controllability,coobservability

Identifier: 10.3182/20060926-3-PL-4904.00019

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Rohee, B.; Riera, B.; Carré-Ménétrier, V.; Roussel, J-M.

Abstract: Applications on manufacturing systems (diagnosis, control, supervision...) often require a plant model. Obtaining the plant model is a difficult task because of systems complexity and deepth knowledge of physical materials. A necessary condition that must be verified by the plant model is its capability to respond to all the requests of the specification model. This paper ends by two complementary approaches a mathematical property is proposed to check formally and this capability and a methodology to design the plant model is proposed in order to guarantee the model capability according to the most permissive control model.

Keywords: discrete event systems,finite automata,formal specification,formal verification

Identifier: 10.3182/20060926-3-PL-4904.00041

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Luba, Tadeusz; Rawski, Mariusz; Tomaszewicz, Pawel

Abstract: In this paper, using FIR filters as an example, the discussion on efficiency of different implementation methodologies used in DSP application targeted modern FPGA architectures is presented. Nowadays programmable technology provides possibility to implement digital system with use of specialized embedded DSP blocks. On the first place, however, this technology gives the designer the possibility to increase efficiency of designed system by exploitation of parallelisms of implemented algorithms. Moreover, it is possible to apply special techniques, such as distributed arithmetic (DA). Since in this approach general purpose multipliers are replaced by combinational LUT blocks, it allows constructing digital filters of very high performance. Additionally, application of the functional decomposition based method to LUT blocks optimisation and mapping has been investigated. The paper presents results of comparison of different design approaches.

Keywords: digital signal processors,FPGA,logic synthesis,functional decomposition

Identifier: 10.3182/20060926-3-PL-4904.00004

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Rosado-Muñoz, A.; DeJuan-Esteban, C. A.; Soria-Olivas, E.; Bataller-Mompeán, M.; Guerrero-Martínez, J.

Abstract: This work proposes a new approximation to design and program Complex Adaptive Systems (CAS), these systems comprise neural network, intelligent agents, genetic algorithms, support vector machines and artificial intelligence systems in general. Due to the complexity of such systems, it is necessary to build a design environment able to ease the design work, allowing reusability and easy migration to hardware and/or software. Ptolemy II is used as the base system to simulate and evaluate the designs with different Models of Computation so that an optimum decision about the hardware or software implementation platform can be taken.

Keywords: signal processing,hardware,embedded systems,hardware programming,circuit design

Identifier: 10.3182/20060926-3-PL-4904.00006

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Miczulski, Piotr; Adamski, Marian

Abstract: In the paper a new method of analysis of safeness, liveness and persistence properties of Petri nets is presented. This method is based on hierarchical representation of the state space of a Petri net by means of a collection of monotone logical functions and with related set of binary decision diagrams. The algorithm of symbolic analysis of a Petri net based behavioural specification of logic controllers is given, together with conditions, which allow analysing the properties mentioned above. One of the advantages of the proposed method is a possibility of detail analysis of selected local parts of a Petri net, as well as hierarchical approach for constructing the total state space.

Keywords: Petri nets,logic controllers,boolean functions,computer aided control system design,concurrency

Identifier: 10.3182/20060926-3-PL-4904.00023

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Wegrzyn, Agnieszka

Abstract: In the paper application of databases for management of the distributed control system is discussed. The proposed system consists of three levels. A considered part of the system corresponds to manage of data. The data transfer between levels of the system is managing using Oracle database. A data management part is responsible for storing information about control system and data flow between levels of the system. The considered control system is specified by Petri net, FSM and HDLs.

Keywords: database,distributed computer control systems,Petri nets,HDLs,verification

Identifier: 10.3182/20060926-3-PL-4904.00044

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Taborek, Krzysztof; Hrynkiewicz, Edward

Abstract: The paper presents the arbitration circuit that was designed for a classical multiprocessor system with a common memory and a time-sharing bus. The arbitration algorithm called "with cyclically shifted priorities" was implemented in this arbiter. The arbitration circuit was designed as modular and expandable. Thanks to proper hardware solutions the arbiter has a simply logic structure. This logic structure was implemented in FPGA. Operation of the arbiter in the real multiprocessor system was described. Block diagrams of all parts of this arbitration circuit were shown. A queueing model of the multiprocessor system with the arbiter was presented. Thanks to this, it was possible to predict performance of this system. The method of performance calculation of the multiprocessor system with the presented arbitration circuit was described. The analytic results were compared with the corresponding measured results that were obtained in the real multiprocessor system. The analytic and measured results were shown in a graphic form in figures.

Keywords: arbiter,arbitration circuit,multiprocessor system,priority,queueing model

Identifier: 10.3182/20060926-3-PL-4904.00029

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Hasdemir, I. Tolga; Kurtulan, Salman

Abstract: Automata formalism has been used extensively in control design of Discrete Event Systems (DES) and, realization methodologies to implement automata that are synthesized using formal methods are needed. In this study, we present a methodology that can be used to express a given automaton in logical domain. Using this methodology, a Matlab program which automatically generates Programmable Logic Controller (PLC) codes that realize the given automaton has been developed.

Keywords: discrete event systems,programmable logic controllers,automata theory,implementation

Identifier: 10.3182/20060926-3-PL-4904.00022

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Chmiel, Miroslaw; Hrynkiewicz, Edward; Milik, Adam

Abstract: The paper presents modified idea of program execution in the Programmable Logic Controllers (PLCs). Instead of serial cyclic execution is proposed event sensitive cyclic execution. Proposed approach to program execution allow for selective execution of program blocks or tasks provided calculation condition for this part has changed since last time. Proposed method can be implemented as software modification or as hardware accelerated solution. The most important part of the idea is task or subprogram triggering condition computation. Different method of program optimization are discussed. Finally hardware implementation of event triggered system is presented.

Keywords: programmable logic controller,central processing unit,control program,scan time,throughput time

Identifier: 10.3182/20060926-3-PL-4904.00017

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Pyka, Maciej; Sakowski, Wojciech

Abstract: This paper explains why the 8-bit microcontroller IP cores are still popular in system on chip designs. It presents R8051XC configurable microcontroller core (developed at Evatronix SA) with a focus on the implemented enhancements of this popular instruction set architecture and on the configurability of the core. For microcontrollers embedded in ASIC or ASSP circuits effective support for software development is very important. Therefore on chip debug support (OCDS) solutions developed for R8051XC are presented along with prototyping environment and real time operating system port available for R8051XC follows. Finally application specific solutions based on R8051XC and oriented towards USB-interfaced and Ethernet-interfaced systems have been presented.

Keywords: IP cores,electronic virtual components,design reuse,hardware description languages,8051 compliant ISA (instruction set architecture),microcontrollers,microcontroller applications

Identifier: 10.3182/20060926-3-PL-4904.00028

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Wisniewski, Remigiusz

Abstract: A method of designing of Compositional Microprogram Control Units with Elementary Operational Linear Chains is proposed. The method is based on the special encoding of the Operational Linear Chains. Such an approach permits to decrease the number of logic blocks of the destination FPGA device. An exemplary application of the proposed method is discussed. The investigations conducted by the author have shown that the proposed method permits to decrease the usage of the logic blocks of destination device up to 20%.

Keywords: compositional microprogram control unit,elementary operational linear chain,logic devices,field programmable gate arrays

Identifier: 10.3182/20060926-3-PL-4904.00032

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Król, Václav; Pokorny, Jan

Abstract: It is very difficult to achieve guaranteed real time database services when putting a database into a real-time environment because various components can compete for system resources. Previous research in real-time databases has focused primarily on evolution of transaction processing algorithms, priority assignment strategies and concurrency control techniques. But for the most part the research efforts are based only on simulation studies with many parameters defined. Our objective is to design and implement an experimental real-time database system suitable for study of real time transaction processing. The experimental system is implemented as an integrated set of the most important functional parts upon the real-time operating system VxWorks. It serves as a support platform for performance evaluation of known and new algorithms of the particular processing components to understand their effect on system performance and to identify the most influencing factors.

Keywords: real-time database,transaction processing,CPU scheduling,concurrency control,real-time operating system

Identifier: 10.3182/20060926-3-PL-4904.00048

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Kraft, Marek; Kasinski, Andrzej; Ponulak, Filip

Abstract: Hardware real-time implementations of Spiking Neuron Networks (SNN) are wanted for multiple applications. Introduction of the supervised learning mechanism for SNNs is a hot topic. A model of a single spiking neuron having that property is proposed. This is based on LIF simplified model. A number of design issues has been solved in order to enable the correct work of such a neuron during learning phase. The proposed extensions and modifications are described and illustrated with corresponding timing diagrams.

Keywords: neural networks,learning algorithms,VLSI design,biocybernetics

Identifier: 10.3182/20060926-3-PL-4904.00050

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Biernat, Janusz; Czapski, Mariusz; Nikodem, Maciej

Abstract: The Advanced Encryption Standard algorithm itself does not guarantee error free operation or detection of arising errors. Contemporary research has shown that even single bit errors strongly affect the output of the algorithm. Moreover an attacker may maliciously induct errors during the run of the AES in order to perform cryptanalysis and recover the encryption secret key. In this paper we propose an extension of error detection code for AES, known from an open literature. The implementation of our idea leads to the improvement of error detection ability and reduces of the probability of successful fault analysis below 2-7.

Keywords: AES,fault detection,fault tolerance,parity code

Identifier: 10.3182/20060926-3-PL-4904.00051

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Trawczynski, Dawid M.; Sosnowski, Janusz; Zalewski, Janusz

Abstract: The general objective of this project is to create an environment for discrete event simulation to assess safety properties of databuses used in real-time applications, especially in automotive and avionics industries. In this paper, we describe several extensions of the TrueTime simulator, beginning with the development of the fault injection model and incorporating it into the simulator using Matlab S-functions in C++. We also discuss an interface to TrueTime to simulate hardware faults via Matlab/Simulink with the use of HDL/Spice tools and high-level object-oriented programming models, which simulate software and hardware faults. Finally, we are suggesting graphical user interface extensions to TrueTime using LabVIEW that prove necessary for efficient experimental data generation, gathering and analysis.

Keywords: fault tolerance,real-time simulation,safety critical systems,databus

Identifier: 10.3182/20060926-3-PL-4904.00014

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Zwolinski, Mark

Abstract: The principle of reconfiguring digital hardware for testing is now widely accepted. Built-in self-test is also now established technology. Self-testability can be thought of as a design objective, in a similar manner to speed, area and power. Thus high-level synthesis tools can be designed to explore a design space that includes testability and to search for optimal implementations. In this context, self-test would normally be performed off-line, but on-line test structures can also be created. Using high-level synthesis allows efficient reuse of resources for self-checking. A further design objective might be dynamic reconfiguration. By combining self-checking and selfreconfiguration, it is possible to create a fault-tolerant computing fabric. This paper describes our recent research in synthesis for self-test, self-checking, reconfiguration and self-repair.

Keywords: testability,fault tolerance,self-adjusting systems

Identifier: 10.3182/20060926-3-PL-4904.00011

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Labiak, Grzegorz

Abstract: Statechart diagrams are very convenient way in specifying behavior of reactive systems and controllers in particular. The system modelled as a statechart can be directly implemented in reprogrammable devices. Mathematical model of statechars gives an opportunity to verify symbolically some properties and to transform into FSM-description. Having statechart in FSM-description allow to implement controllers in embedded array blocks.

Keywords: statechart diagrams,FSM,BDDs,symbolic techniques,state space

Identifier: 10.3182/20060926-3-PL-4904.00027

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: None

Abstract:

Keywords:

Identifier: 10.3182/20060926-3-PL-4904.90001

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Tkacz, Jacek

Abstract: The paper presents a practical application of Gentzen theorem proving system by means of an experimental computer tool, for the purpose of logic expressions normalization into the form similar to the Horn clauses. The initial expressions are described as complicated nested condition rules in general rule-based form "IF THEN". Additionally the paper describes a particular kind of logic algorithms optimization and some possibilities of increasing of efficiency of the presented application, for the normalizing a great number of symbolic expressions.

Keywords: Gentzen,sequent,minimalization,symbolic deduction,Espresso

Identifier: 10.3182/20060926-3-PL-4904.00010

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Hahanov, Vladimir; Kteaman, Hassan; Ghribi, Wade; Fomina, Elena

Abstract: Hardware Embedded DEductive Fault Simulation (HEDEFS) is a hardware-software realization of a deductively-parallel topological method of faults modeling. The method uses ad hoc technology of the analysis of converging branching, back-word modeling of faults simulation, and transformation of testable circuits; and is oriented on handling of digital circuits with big dimension represented on gate or RT description levels. Structural hardware solutions for realization of the method are presented at an estimation of quality of generated tests.

Keywords: digital system,hardware and software realization,testing,verification deductive-parallel and deductive-topological faults modelling

Identifier: 10.3182/20060926-3-PL-4904.00005

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006

Authors: Kothe, R.; Galke, C.; Schultke, S.; Fröschke, H.; Vierhaus, H. T.

Abstract: Systems on a Chip (SoCs) typically consist of several processor devices, embedded memory blocks, application-specific logic blocks and complex interconnects. While embedded memory blocks are mostly equipped with built-in self test (BIST) capabilities, test methods for processors, logic blocks and interconnects are still topics of intensive research. Beyond production testing, SoCs in safety-critical applications also need built-in self test capabilities, which work independently from external control hardware. A HW / SW -based self test scheme can facilitate self test in the field of application making efficient use of structures for production test and can even supplement production test, e.g. for internal interconnects. The paper describes the architecture, cost and limitations.

Keywords: test data compression,hierarchical systems methodology

Identifier: 10.3182/20060926-3-PL-4904.00015

Conference: 3rd IFAC Workshop on Discrete-Event System Design (2006)

Location: University of Zielona Gora, Poland

Start Date: Wed Sep 13 2006 - End Date: Fri Sep 15 2006