Wyniki wyszukiwania - BazTech

1

An Efficient Two-phase Clocked Sequential Multiply : Accumulator Unit for Image Blurring

Samanth Rashmi, Nayak Subramanya G.

International Journal of Electronics and Telecommunications

|

2022

|

Vol. 68, No. 2

307--313

EN

The multiply-accumulator (MAC) unit is the basic integral computational block in every digital image and digital signal processor. As the demand grows, it is essential to design these units in an efficient manner to build a successful processor. By considering this into account, a power-efficient, high-speed MAC unit is presented in this paper. The proposed MAC unit is a combination of a two-phase clocked modified sequential multiplier and a carry-save adder (CSA) followed by an accumulator register. A novel two-phase clocked modified sequential multiplier is introduced in the multiplication stage to reduce the power and computation time. For image blurring, these multiplier and adder blocks are subsequently incorporated into the MAC unit. The experimental results demonstrated that the proposed design reduced the power consumption by 𝟓𝟐% and improved the computation time by 𝟒% than the conventional architectures. The developed MAC unit is implemented using 𝟏𝟖𝟎𝒏𝒎 standard CMOS technology using CADENCE RTL compiler, synthesized using XILINX ISE and the image blurring effect is analyzed using MATLAB.

2

A hierarchy of finite state machines as a scenario player in interactive training of pilots in flight simulators

Bach Małgorzata, Werner Aleksandra, Mrozik Magda, Cyran Krzysztof A.

International Journal of Applied Mathematics and Computer Science

|

2021

|

Vol. 31, no. 4

713--727

EN

The paper presents the concept of a control unit, i.e., a scenario player, for interactive training pilots in flight simulators. This scenario player is modelled as a hierarchy of finite state machines. Such an approach makes it possible to separate the details of an augmented reality display device which is used in training, from the core module of the system, responsible for contextual organization of the content. Therefore, the first contribution of this paper is the mathematical model of the scenario player as a universal formulation of the self-trained control unit for interactive learning systems, which is applicable in a variety of situations not limited solely to flight simulator related procedures. The second contribution is an experimental verification achieved by extensive simulations of the model, which proves that the proposed approach is capable to properly self-organize details of the context information by tracing preferences of the end users. For that latter purpose, the original algorithm is derived from statistical analysis, including Bayesian inference. The whole approach is illustrated by a real application of training the preflight procedure for the captain of the Boeing 737 aircraft in a flight simulator.

3

Roots and Powers in Regular Languages : Recognizing Nonregular Properties by Finite Automata

Frei Fabian, Hromkovič Juraj, Karhumäki Juhani

Fundamenta Informaticae

|

2020

|

Vol. 175, nr 1-4

173--185

EN

It is well known that the set of powers of any given order, for example squares, in a regular language need not be regular. Nevertheless, finite automata can identify them via their roots. More precisely, we recall that, given a regular language L , the set of square roots of L is regular. The same holds true for the nth roots for any n and for the set of all nontrivial roots; we give a concrete construction for all of them. Using the above result, we obtain decision algorithms for many natural problems on powers. For example, it is decidable, given two regular languages, whether they contain the same number of squares at each length. Finally, we give an exponential lower bound on the size of automata identifying powers in regular languages. Moreover, we highlight interesting behavior differences between taking fractional powers of regular languages and taking prefixes of a fractional length. Indeed, fractional roots in a regular language can typically not be identified by finite automata.

4

A Common Framework to Recognize Two-dimensional Languages

Anselmo Marcella, Giammarresi Dora, Madonia Maria

Fundamenta Informaticae

|

2020

|

Vol. 171, nr 1-4

1--17

EN

We introduce the two-dimensional rational automata (RA) to recognize languages of pictures, as an extension of the finite automata for strings. A RA processes a picture column by column changing its state. The states are columns of symbols, too. The transition function is realized by a transducer. We prove that RA recognize the family REC of languages recognized by tiling systems. Moreover, RA provide a uniform setting for a lot of important notions, techniques and results presented in the last decades for recognizable two-dimensional languages. The model is also very flexible. In fact, there can be imposed restrictions or added features to easily interesting new classes and examples or to capture known families of languages.

5

Research on driving behavior decision making system of autonomous driving vehicle based on benefit evaluation model

Wang Pengwei, Gao Song, Li Liang, Cheng Shuo, Zhao Hailan

Archives of Transport

|

2020

|

Vol. 53, iss. 1

21--36

EN

Autonomous driving vehicle could increase driving efficiency, reduce traffic congestion and improve driving safety, it is considered as the solution of current traffic problems. Decision making systems for autonomous driving vehicles have significant effects on driving performance. The performance of decision making system is affected by its framework and decision making model. In real traffic scenarios, the driving condition of autonomous driving vehicle faced is random and time-varying, the performance of current decision making system is unable to meet the full scene autonomous driving requirements. For autonomous driving vehicle, the division between different driving behaviors needs clear boundary conditions. Typically, in lane change scenario, multiple reasonable driving behavior choices cause conflict of driving state. The fundamental cause of conflict lies in overlapping boundary conditions. To design a decision making system for autonomous driving vehicles, firstly, based on the decomposition of human driver operation process, five basic driving behavior modes are constructed, a driving behavior decision making framework for autonomous driving vehicle based on finite state machine is proposed. Then, to achieve lane change decision making for autonomous driving vehicle, lane change behavior characteristics of human driver lane change maneuver are analyzed and extracted. Based on the analysis, multiple attributes such as driving efficiency and safety are considered, all attributes benefits are quantified and the driving behavior benefit evaluation model is established. By evaluating the benefits of all alternative driving behaviors, the optimal driving behavior for current driving scenario is output. Finally, to verify the performances of the proposed decision making model, a series of real vehicle tests are implemented in different scenarios, the real time performance, effectiveness, and feasibility performance of the proposed method is accessed. The results show that the proposed driving behavior decision making model has good feasibility, real-time performance and multi-choice filtering performance in dynamic traffic scenarios.

6

Simple SubTypes of Intersection Types

Statman Rick

Fundamenta Informaticae

|

2019

|

Vol. 170, nr 1-3

307--324

EN

Solving the Entscheidungsproblem was a challenge first posed by David Hilbert in 1928, and solutions to decision problems are perhaps the most prized posessions in logic. Pawel Urzyczyn has a number of these, one of which I will discuss below. However, let me remind you of Michael Rabin describing his time with Dana Scott at IBM prior to their Turing award winning paper Finite automata and their decision problems “So we both went, in 1957 to IBM and the location was the so-called Lamb Estate [Robert S. Lamb estate], a wonderful place, while the Princeton Laboratory, designed by Sarason, the Watson Laboratory was in stages of construction. The Lamb Estate, very appropriately, used to be, before that, an Insane Asylum. All those buildings were building where kooks were housed...” [1]. This is what IBM thought of decision problems. In this note we give a new proof of the undecidability of the inhabitation problem for intersection types.

7

Speed Targeted Minimization of Finite State Machines for CPLDs

Klimowicz A.

Measurement Automation Monitoring

|

2018

|

Vol. 64, No. 1

5--7

EN

A method of the minimization finite state machines (FSM) is proposed. In this method, such optimization criterion as the critical delay path is taken into account already at the stage of minimizing internal states. The method is based on sequential merging of two internal states including the optimization criteria. The critical path is estimated for CPLD devices. In addition, the proposed method allows one to minimize the number of transitions and input variables of the FSM. Experimental results shows, that the maximum clock frequency of minimized FSMs is higher by 17% comparing to initial FSM.

8

Modelling of Parameterized Discrete Control Algorithms With Use of Finite State Machines in TIA Portal Environment

Andrzejewski G., Zając W.

International Journal of Electronics and Telecommunications

|

2018

|

Vol. 64, No. 2

249--254

EN

There exist numerous modelling techniques and representation methods for digital control algorithms, aimed to achieve required system or process parameters, e.g. precision of process modelling, control quality, fulfilling the time constrains, optimisation of consumption of system resources, or achieving a trade-off between number of parameters. This work illustrates usage of Finite State Machines (FSM) modelling technique to solve a control problem with parameterized external variables. The structure of this work comprises six elements. The FSM is presented in brief and discrete control algorithm modelling is discussed. The modelled object and control problem is described and variables are identified. The FSM model is presented and control algorithm is described. The parameterization problem is identified and addressed, and the implementation in PLC programming LAD language is presented. Finally, the conclusion is given and future work areas are identified.

9

Tinput-Driven Pushdown, Counter, and Stack Automata

Kutrib M., Malcher A., Wendlandt M.

Fundamenta Informaticae

|

2017

|

Vol. 155, nr 1/2

59--88

EN

In input-driven automata the input alphabet is divided into distinct classes and different actions on the storage medium are solely governed by the input symbols. For example, in inputdriven pushdown automata (IDPDA) there are three distinct classes of input symbols determining the action of pushing, popping, or doing nothing on the pushdown store. Here, input-driven automata are extended in such a way that the input is preprocessed by a deterministic sequential transducer. IDPDAs extended in this way are called tinput-driven pushdown automata (TDPDA) and it turns out that TDPDAs are more powerful than IDPDAs but still not as powerful as real-time deterministic pushdown automata. Nevertheless, even this stronger model has still good closure and decidability properties. In detail, it is shown that TDPDAs are closed under the Boolean operations union, intersection, and complementation. Furthermore, decidability procedures for the inclusion problem as well as for the questions of whether a given automaton is a TDPDA or an IDPDA are developed. Additionally, representation theorems for the context-free languages using IDPDAs and TDPDAs are established. Two other classes investigated are on the one hand TDPDAs restricted to tinput-driven counter automata and on the other hand TDPDAs generalized to tinput-driven stack automata. In both cases, it is possible to preserve the good closure and decidability properties of TDPDAs, namely, the closure under the Boolean operations as well as the decidability of the inclusion problem.

10

Reversible Limited Automata

Kutrib M., Wendlandt M.

Fundamenta Informaticae

|

2017

|

Vol. 155, nr 1/2

31--58

EN

A k-limited automaton is a linear bounded automaton that may rewrite each tape square only in the first k visits, where k≥ 0 is a fixed constant. It is known that these automata accept context-free languages only. We investigate deterministic k-limited automata towards their ability to perform reversible computations, that is, computations in which every configuration has at most one predecessor. A first result is that, for all k≥ 0, sweeping k-limited automata accept regular languages only. In contrast to reversible finite automata, all regular languages are accepted by sweeping 0-limited automata. Then we study the computational power gained in the number k of possible rewrite operations. It is shown that the reversible 2-limited automata accept regular languages only and, thus, are strictly weaker than general 2-limited automata. Furthermore, a proper inclusion between reversible 3-limited and 4-limited automata languages is obtained. The next levels of the hierarchy are separated between every k and k + 3 rewrite operations. We investigate closure properties of the family of languages accepted by reversible k-limited automata. It turns out that these families are not closed under intersection, but are closed under complementation. They are closed under intersection with regular languages, which leads to the non-closure under concatenation, iteration, and homomorphisms. Finally, it turns out that all k-limited automata accept Church-Rosser languages only, that is, the intersection between context-free and Church-Rosser languages contains an infinite hierarchy of language families beyond the deterministic context-free languages.

11

Minimization of finite state machines by states merging

Salauyou V.

Measurement Automation Monitoring

|

2016

|

Vol. 62, No. 5

179--181

EN

The paper presents a method for minimization of finite state machines (FSMs) with unspecified values of output variables. The proposed method is based on merging of two states. In addition to reduction of the FSM states, the method also allows reducing the number of FSM transitions and FSM input variables. This method enables reducing the number of internal states of the initial FSM by 1.22 times on the average, and by 2.75 times on occasion. An average reduction of the number of FSM transitions makes up 1.32 times, and on occasion may amount to 2.27 times. The comparison of the method with the program STAMINA shows that the offered method allows decreasing the number of FSM transitions by 1.55 times on the average, and by 3.92 times on occasion.

12

Kodowanie stanów energooszczędnych automatów sekwencyjnych wykorzystujące algorytm Kernighana-Lina

Kajstura K., Kania D.

Przegląd Elektrotechniczny

|

2015

|

R. 91, nr 5

155-158

PL

W artykule przedstawiono oryginalny dekompozycyjny algorytm kodowania stanów wewnętrznych automatów skończonych, który ukierunkowany jest na minimalizację poboru mocy. W kolejnych krokach następuje podział grafu stanowiącego probabilistyczny opis automatu realizowany za pomocą zmodyfikowanego algorytmu Kernighana-Lina. Wyniki eksperymentów wskazują, że opracowana metoda kodowania prowadzi do redukcji poboru mocy oraz zmniejszenia powierzchni układu.

13

FSM state merging for low power

Salauyou V.

Measurement Automation Monitoring

|

2015

|

Vol. 61, No. 7

337--339

EN

A method of finite state machine (FSM) minimization for low power by merging FSM internal states is considered. The general algorithm for the minimization of FSM power consumption by means of merging two states is presented. The algorithm of the merging possibility of two states and the actual algorithm merging of two states for incompletely specified Mealy FSMs are given. In the conclusions, the possible directions of development of this approach are specified.

14

Iterating Transducers

Sutner K.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

259--272

EN

We discuss simple functional transductions defined by invertible Mealy automata under iteration and in particular the question when the orbit relation defined by iteration is rational. We identify a class of these automata that has relatively complicated orbits, yet some of them are still orbit rational and discuss a number of decision problems associated with these devices.

15

Asynchronous Systems of Parallel Communicating Finite Automata

Vollweiler M.

Fundamenta Informaticae

|

2015

|

Vol. 136, nr 1/2

177--197

EN

Synchronous systems of parallel communicating one-way finite automata have already been investigated. There, all components work stepwise in parallel, and the communication between the components is realized by requesting states in a one-directional manner. This means that one component can request information in form of the current state from another component, where the latter one sends its current state without realizing that a communication takes place. Here, we introduce asynchronous systems of parallel communicating one-way and two-way finite automata with a bidirectional communication protocol. A communication only takes place, when both components - the requesting and the responding component - are ready to communicate. It is shown that almost all language classes that are characterized by these systems coincide with the language classes that are characterized by multi-head finite automata. Moreover, our communication protocol uses blocking point-to-point communications, i.e. a communication takes place between two components, and a communicating component is blocked until the communication has been finished. There have also been studied asynchronous systems of finite automata with non-blocking communication in the literature. Thus, we compare synchronous and asynchronous systems on the one hand and asynchronous systems with blocking and non-blocking communication on the other hand. Finally, we give some results on the communication complexity of our systems, where the amount of communication is measured by counting each message which is sent from one component to another during a computation of a system. Particularly, we show that with constantly many communications our systems can only accept regular languages, and at most linearly (polynomially) many communications are needed for systems of one-way (two-way) components depending on the length of the input. Further, there exists no system that executes more than constantly many and less than linearly many communications.

16

Projektowanie procesora sekwencyjnego i symulacja w środowisku MATLAB/Simulink

Szostek K.

Przegląd Elektrotechniczny

|

2014

|

R. 90, nr 1

119--121

PL

W artykule omówiono projekt procesora dedykowanego do realizacji tabeli przejść i wyjść dowolnego automatu sekwencyjnego. Celem budowy było skonstruowanie procesora o jak najprostszej budowie reprezentującego podstawowe cechy procesora oraz zaprojektowanie takiego procesora i uruchomienie w środowisku matlab simulink. Do budowy automatów kombinacyjnych zostały wykorzystane bloki State-Space programu simulink.

EN

This paper discusses the design of processor dedicated to the implementation of the state and output tables of finite-state machines. The aim was to construct and a building of a CPU represents the simplest construction of the basic features of the processor and run it in the Matlab Simulink environment. To build the combinational logic of the machine were used blocks State-Space of Simulink.

17

Konstruowanie automatów sekwencyjnych w środowisku Matlab Simulink

Szostek K.

Przegląd Elektrotechniczny

|

2014

|

R. 90, nr 1

179--181

PL

W artykule omówiono algorytmy, pozwalające wyznaczać funkcje logiczne automatów sekwencyjnych. Algorytmy zostały zaimplementowane w programie Matlab. Zaimplementowany algorytm został wykorzystany do wyznaczenia funkcji logicznych przykładowego automatu. Zostały wyznaczone stany wewnętrzne oraz funkcje logiczne automatu. Wyznaczone funkcje logiczne zostały wykorzystane do symulacji pracy automatu w programie Fluidsim.

EN

The article discusses the algorithms that allow, to find, logic functions for finite state machines The algorithms were implemented in MATLAB program. The implemented algorithm was used to determine the internal states and logic functions for finite state machine. Determined logic has been used to simulate of automata in FluidSIM program.

18

Koszt implementacji w strukturach CPLD i FPGA jako kryterium wyboru stanów przy minimalizacji automatu skończonego

Klimowicz A.

Pomiary Automatyka Kontrola

|

2014

|

R. 60, nr 7

480--482

PL

W pracy opisano heurystyczną metodę minimalizacji automatów skończonych, która pozwala na etapie minimalizacji stanów uwzględniać parametry bazy technologicznej oraz metodę kodowania stanów. Opisano kryteria minimalizacji liczby stanów ze względu na koszt ich realizacji w strukturze CPLD, gdzie głównym parametrem wpływającym na realizację jest liczba termów podłączonych do jednej makrokomórki i liczba elementarnych koniunkcji w opisie SOP (Sum of Products) funkcji logicznej oraz FPGA, gdzie głównym parametrem jest liczba wejść elementu logicznego i liczba argumentów realizowanej funkcji logicznej. Przedstawiono także wyniki badań opracowanych algorytmów i porównanie ich z innymi metodami minimalizacji stanów.

EN

In the paper a heuristic method of minimization of incompletely specified finite state machines is described. This method allows taking into account the parameters of technological base, the method of state assignment and realization costs. The presented method is focused on realization of FSM in CPLD and FPGA structures. The method is based on operation of merging two states. In addition to reducing internal states this method minimizes the number of FSM transitions and FSM input variables. In contrast to the previously developed methods, in each step of the algorithm there is considered not only one, but the entire set of all pairs of states for which it is permissible to merge. Then from the set there is selected the pair of states which best matches the criteria of minimizing. The paper describes the criteria for minimizing the number of states of the machine because of the cost of their implementation in the CPLD. The main parameter influencing the implementation is a number of terms connected to one macrocell and FPGA structures, where the main parameter is the number of LUT inputs and the number of logic function arguments. The results of implementation of the minimized FSMs in programmable devices showed that the proposed method allowed building FSMs at lower cost and higher speed than STAMINA program for CPLD and FPGA devices.

19

The Incremental Maintenance of Transition Tour

Németh G. A., Pap Z.

Fundamenta Informaticae

|

2014

|

Vol. 129, nr 3

279--300

EN

While evolutionary developmentmethodologies have become increasingly prevalent, incremental testing methods are lagging behind. Most traditional test generation algorithms – including the Transition Tour method – rebuild test sequences from scratch even if minimal changes to the system have been made. In the current paper we propose two incremental algorithms to update a Transition Tour test sequence after changes in a deterministic finite state machine model. Our solution uses existing information – the Eulerian graph of a previous version of the system and an Euler tour in it – to update the test cases of the system in response to modification. The first algorithm keeps an Eulerian graph up to date, while the second algorithm maintains an Euler tour in the augmented graph. Analytical and practical analyses show that our algorithms are very efficient in the case of changing specifications. We also demonstrate our methods through an example.

20

Deciding Whether or Not a Synchronous Relation is Regular Prefix

Choffrut C.

Fundamenta Informaticae

|

2014

|

Vol. 132, nr 4

439--459

EN

Eilenberg and al. introduced and studied in the late sixties the family of n-ary relations over the free monoid recognized by finite n-tape automata where the where the n reading heads tapes move simultaneously from left to right. We call these relations synchronous. In the eighties Angluin and Hoover and then L¨auchli and Savioz introduced a proper subfamily which the first authors called regular prefix. Our main result shows that given a synchronous relation it is decidable whether or not it is regular prefix. Incidentallywe also show that the family of regular prefix relations is uniformizable in the sense that all such relations contain a partial function with the same domain whose graph is a regular prefix relation.