😦 🤶🏾 🤚🏻 The implementation of inertial algorithms on the example of logical modeling of digital circuits 🕓 🙊 👩🏽‍🏫

1. Introduction

We proceed to the second part of the topic devoted to nested automata. In the first, we examined recursive algorithms, which, having a model of nested automata and connecting OOP capabilities, it turned out to be not so difficult to implement. But the possibilities of nested automata are not limited to this. So, when describing the control model of automaton programs, inertial algorithms were determined, based on the idea of embedding automata. Inertial algorithms are difficult to imagine in the framework of the usual block diagram of the computational model, which does not provide for the return of control to the point preceding the subroutine call. But I must say that conventional automata also provide for the abolition of transitions "on the fly." Nevertheless, for automata this can not only be imagined, but also implemented.

Inertial algorithms and logical modeling of digital circuits related topics. And not so much because the inertial delay gave the name to the class of algorithms under consideration, but how much the meaning of the delayed actions of the inertial delay, which was transferred to the meaning of their work. Although, of course, it’s not the name. In UML, similar algorithms are implemented using the concept of history state. The analogy is straightforward, although modeling of digital circuits in UML, as a rule, is out of the question. It’s just that the situations when returning to the starting point, if something compels one to do so, seem to be the most natural. Examples include refusal to purchase tickets, cancellation of banking operations / transactions, disconnection of a network connection, etc. etc. In the end, as stated in UML,without the use of historical states, the implementation of such algorithms would not be so “beautiful” [1].

The topic of logical modeling of digital circuits is extensive and interesting in itself. And a new reading does not hurt her. As we will see, automatic programming technology can offer an even better way to describe, implement, and logically model digital circuits. We will get to know this all the same, pursuing the main goal - to consider an interesting, useful and, finally, just a beautiful class of algorithms that is natural for automata, but quite difficult to implement in other computational models.

2. Logical modeling of digital circuits

The literature usually considers two methods of modeling digital circuits - compilation and event. Compilation is limited in its capabilities, because does not take into account element delays, requires ranking elements and breaking feedback [2]. The event method does not have such restrictions and is based on tracking events associated with changes in signal values within the circuit. We will not consider compilation, but will focus on comparing the event with the method implemented within the framework of the possibilities of automatic programming, which we will call further, accordingly, in an automatic way.

As an example, take the circuit from [2], shown in Fig. 1. Diagrams of her work from the source are shown in Fig. 2. Two options are considered: with a single delay, when the logic elements of the circuit have the same delay, and with a distributed delay, when the elements B and E have a delay twice as much as the rest of the circuit elements.

Fig. 1. An example of a circuit.

Fig. 2. Examples of modeling: a - a single delay; b - distributed delay.

With the automatic simulation method, you don’t even have to invent something, because there is no need to create a sufficiently specific language for describing a circuit and structures that implement circuit relationships, and it does not need specific enough algorithms for detecting events in the process of modeling a circuit, which then serve as the basis for constructing diagrams of the circuit (for a description of both, see [2] )

In the case of automata, the logical element models that are usual for the automaton technology for program design are created, which are included in the logical element library (BLE). Then, on the basis of this library, a set of parallel automaton processes corresponding to the number of circuit elements is created, between which the connections are indicated using the input / output channels of logical element models (for this, in the VKPA environment, local process variables are often quite enough). In conclusion, the circuit model is supplemented by processes-generators of input signals and processes of displaying signal diagrams.

The simulation results of the considered example in the VKPa environment, which are shown in Fig. 3 completely coincide with the diagrams in Fig. 2. True, it was not immediately possible to achieve such a coincidence. And not because of problems with the models, but because in fact the “scientific selection method” had to calculate the duration of the input signals, which, as it turned out, has a significant impact. But in [2] not a word was said about this, nor about the parameters of the input signals. Full agreement was achieved by finding out that 1) the duration equal to three times the delay is necessary, and 2) the signal offset (b) relative to the signal (a) should be equal to the unit delay. To explain this problem, see fig. Figure 4 shows the signal diagrams for different durations of the input signals (and this without taking into account their displacement).

Fig. 3. The simulation results in VKPa: a - a single delay; b - distributed delay.

Fig. 4. Simulation results with different input signal durations

Consider another example of a circuit from the same source [2]. Its scheme and timing diagrams of work are shown in fig. 5. In the framework of the event method, to “calculate” the time diagram, 20 simulation steps were required (for more details see [2]). But, as it is stated there, an even more complex algorithm and, accordingly, an even greater number of steps are required if the inertial type of delays is chosen. In our case (the case of the automatic modeling method), having the previous model, we need “20 clicks” with the mouse to go to the diagram in Fig. 5, removing unnecessary elements of the original circuit. The results of the circuit simulation obtained in VKPa are shown in Fig. 6.

Fig. 5. An example of a circuit and its timing chart.

In addition, the diagram in Fig. 5 we added parallel to the element OR element I. Graph d in fig. 6 displays its operation for the case of a single delay. If we set a large delay and set the inertial type of delay, then the graph d will turn into a straight line. Therefore, the And element with an inertial delay greater than a single value will not miss the pulse generated at its inputs by a combination of these input signals a and b. Note that manipulating the type of delay makes sense only for elements that have a delay greater than one.

Fig. 6. Modeling the circuit in Fig. 5 and the element And (d).

3. Implementation of logic elements

In the general case, any logical element can be represented as a series connection of two blocks (see Fig. 7) - an ideal logical element without delay and a block, which can be considered as propagation delay (transport delay) or inertial delay [2].

Fig. 7. Delayed logic element model.

An ideal logical element is very easily implemented by a normal logical function, and the delay block model can be represented in the form of an automaton model - a universal model including transport and inertial delay. A model of such a universal delay is shown in Fig. 8, and models of nested automata for it are shown in Fig. 9. Their implementation in C ++ and as part of the automated programming technology is shown in Listing 1.

Fig. 8. The model of universal delay.

Fig. 9. Models of nested automata for universal delay.

The machines in Fig. 8 and fig. 9 are mixed Mili-Moore assault rifles. The operation of the main automaton in Fig. 8. begins by creating local variables and initializing the references in action y12 (the predicate x12 checks all this). The intermediate state “ss” is necessary for the predicate x3 to work correctly, which has a link to an input variable, which may not be initialized. From the “ss” state, the model goes into the state corresponding to the delay output, while causing a nested automaton. Note that actions under states of an automaton (actions of Moore automata) will be initiated only after the operation of a nested automaton is completed. They will ultimately set the current delay value and the state of the output variable.

Action y13, if a delay value is defined, creates the necessary nested automaton depending on the type of delay. The embedded transport delay automaton simply counts the set value of the discrete time clock cycles (the duration of the delay is determined by the number of discrete clock cycles), and the inertial delay additionally controls the input signal level. In this case, we note that the returned value of the predicate x3 depends on the current state of the top-level automaton.

The implementation of automata in Fig. 8, 9 reflects Listing 3. Considering the code, you should pay attention to the virtual method f (), which, on the one hand, implements one or another overlapping abstract logical function, and, on the other hand, performs, if specified, inversion. All this is necessary for the implementation of derived models of logical elements. Listing 2 demonstrates the implementation of such a NAND gate.

Listing 1. Implementing a universal delay logic element

#include "lfsaappl.h"

extern LArc TBL_DiscreteTime[];
class FDiscreteTime :											
	public LFsaAppl											
{													
public:													
    enum {cvarINE, cvarExlusiveOR, cvarOrNot};
    void MooreAction();
	bool	FCreationOfLinksForVariables();								
    LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF) return new FDiscreteTime(nameFsa); }
	bool FInit();											
    FDiscreteTime(string strNam, LArc* pTBL = TBL_DiscreteTime);
	~FDiscreteTime(void);										
	CVar *pVarType;		// delay type 0-transport; 1- inertial
	CVar *pVarX1;		// input variable
	CVar *pVarStrNameX1;	// input variable name
    	CVar *pVarIfNotX1;	// inverse of the first input variable
    	CVar *pVarY1;		// output variable
	CVar *pVarStrNameY1;	// output variable name
	CVar *pVarValue01;	// delay value from 0 to 1
	CVar *pVarValue10;	// delay value from 1 to 0
    	CVar *pVarNegationY;// output inversion 0 - no inversion; 1- inversion
    	virtual int x3();	// input analysis
	virtual int x12();	// link setup analysis
    	virtual bool f();
    	int nTypeElement;
protected:
// predicates												
    int x1();
// actions												
	void y1(); void y4(); void y5(); void y6(); void y7(); void y12(); void y13(); 
    bool bType{false};	// delay type: false - transport; true - inertial;
    bool bX1{false};
    int nCurrent{0};
    int nDelay{0};		// tech. delay counter value
    LFsaAppl	*pFCall{nullptr};
    friend class FCallTransport;
    friend class FCallInertial;
};		

class FCallTransport :
	public LFsaAppl
{
public:
	void MooreAction();
	FCallTransport(FDiscreteTime	*pFDiscreteTime);
	FDiscreteTime	*pFDiscreteTime;
protected:
	int x1();
};

class FCallInertial :
	public LFsaAppl
{
public:
	void MooreAction();
	FCallInertial(FDiscreteTime	*pFDiscreteTime);
	FDiscreteTime	*pFDiscreteTime;
protected:
    int x1(); int x3();
};

#include "stdafx.h"
#include "FDiscreteTime.h"											
#include "VARFSA/SetVarFsaLibrary.h"
//=====================================================================
//		Delay model at the upper structural level of the view
//=====================================================================
LArc TBL_DiscreteTime[] = {
    LArc("st",	"st","^x12","y12"),	//
    LArc("st",	"ss","x12", "--"),	//
    LArc("ss",	"s1","x3",  "y7y6y13"),// transition to a single state
    LArc("ss",	"s0","^x3", "y4y5y13"),// transition to zero state
// creation of a nested automaton at the transition to a single state
    LArc("s0",	"s1","x3",  "y13"),    
// creation of a nested automaton at the transition to the zero state
    LArc("s1",	"s0","^x3", "y13"),    
    LArc()
};
FDiscreteTime::FDiscreteTime(string strNam, LArc* pTBL):
    LFsaAppl(pTBL, strNam, nullptr, nullptr)
{ }
													
FDiscreteTime::~FDiscreteTime(void) { if (pFCall) delete pFCall; }

bool FDiscreteTime::FInit() {										
    FCreationOfLinksForVariables();
    return true;
}

bool FDiscreteTime::FCreationOfLinksForVariables()
{
// Local variables
    pVarNegationY = CreateLocVar("negation", CLocVar::vtBool, "output inversion: 0-without inversion / 1-inversion");
    pVarType = CreateLocVar("type", CLocVar::vtBool, "delay type: 0-transp / 1-inertia");
    pVarY1 = CreateLocVar("y", CLocVar::vtBool, "local output");
    pVarX1 = CreateLocVar("x1", CLocVar::vtBool, "local input");
    pVarValue01 = CreateLocVar("value to 1", CLocVar::vtInteger, "delay value from 0 to 1");
    pVarValue10 = CreateLocVar("value to 0", CLocVar::vtInteger, "delay value from 1 to 0");
    pVarStrNameX1 = CreateLocVar("strNameX1", CLocVar::vtString, "name of external input variable (x)");
    pVarStrNameY1 = CreateLocVar("strNameY", CLocVar::vtString, "name of external output variable (y)");
    pVarIfNotX1 = CreateLocVar("not(x1)", CLocVar::vtBool, "1st input inversion: 0-without inversion / 1-inversion");
    string str;
    str = pVarStrNameX1->strGetDataSrc();
    if (str != "") { pVarX1 = pTAppCore->GetAddressVar(pVarStrNameX1->strGetDataSrc().c_str(), this);	}
    str = pVarStrNameY1->strGetDataSrc();
    if (str != "") { pVarY1 = pTAppCore->GetAddressVar(pVarStrNameY1->strGetDataSrc().c_str(), this);	}
    return true;
}
// predicates
int FDiscreteTime::x1() { return nCurrent == nDelay; }
//  
int FDiscreteTime::x3() {
    if (bool(pVarNegationY->GetDataSrc())) return !f();
    return f();
}
//
int FDiscreteTime::x12() { return pVarX1 != nullptr; }
//
bool FDiscreteTime::f() {
    bX1 = bool(pVarX1->GetDataSrc());
    if (bool(pVarIfNotX1->GetDataSrc())) bX1 = !bX1;
    return bX1;
}
// actions
// +1 to the current delay value
void FDiscreteTime::y1() { nCurrent++; }
// setting the delay value when switching from 0 to 1
void FDiscreteTime::y4() { nDelay = int(pVarValue01->GetDataSrc()); }
// setting output to zero
void FDiscreteTime::y5() { pVarY1->SetDataSrc(nullptr, 0.0); }
// setting output to unit
void FDiscreteTime::y6() { pVarY1->SetDataSrc(nullptr, 1); }
// setting the delay value when switching from 1 to 0
void FDiscreteTime::y7() { nDelay = int(pVarValue10->GetDataSrc()); }
//
void FDiscreteTime::y12() { FInit(); }
// creation, if a delay is determined, of the necessary nested automaton
void FDiscreteTime::y13() {
	nCurrent = 0;
	if (pFCall) { delete pFCall; pFCall = nullptr; }
	if (x1()) return;
	bType = pVarType->GetDataSrc();		// set delay type
	if (bType) pFCall = new FCallInertial(this);
	else pFCall = new FCallTransport(this);
	if (pFCall) pFCall->FCall(this);
}

void FDiscreteTime::MooreAction()
{
	string strState = FGetState();
	if (strState=="s0")	{ 
        y4(); y5();		// y4) setting the delay value when switching from 0 to 1; y5) set the output to zero
    }
	else if (strState=="s1") { 
        y7(); y6();		// y7) setting the delay value when switching from 1 to 0; y6) setting the output to one
    }
}
//=====================================================================
//				Transport delay
//=====================================================================
static LArc TBL_CallTransport[] = {
	LArc("s5","s5","^x1",	"--"),		//
	LArc("s5","00","x1",	"--"),		// 
	LArc()
};

FCallTransport::FCallTransport(FDiscreteTime	*pFI):
    LFsaAppl(TBL_CallTransport, "FCallTransport", nullptr, nullptr)
{
	pFDiscreteTime = pFI;
}
// . == 
int FCallTransport::x1() { return pFDiscreteTime->x1(); }
//
void FCallTransport::MooreAction()
{
	string strState = FGetState();
	if (strState=="s5")	{ pFDiscreteTime->y1(); }
}
//=====================================================================
//				Inertial delay
//=====================================================================
static LArc TBL_CallInertial[] = {
	LArc("s5",	"s5","^x1x3",	"--"),		//
	LArc("s5",	"00","x1x3",	"--"),		//
	LArc("s5",	"XX","^x3",	"--"),		//
	LArc()
};

FCallInertial::FCallInertial(FDiscreteTime	*pFI):
    LFsaAppl(TBL_CallInertial, "FCallInertial", nullptr, nullptr)
{
	pFDiscreteTime = pFI;
}
// . == 
int FCallInertial::x1() { return pFDiscreteTime->x1(); }
// input value (depends on the name of the current state of the main automaton)
int FCallInertial::x3() {
	string strState = FGetStateUp();
	bool bX = pFDiscreteTime->x3();
    if (strState == "s0") return bX;
    if (strState == "s1") return !bX;
	if (strState == "st") {
		string str = pFDiscreteTime->FGetNextState();
		bX = pFDiscreteTime->x3();
		if (!bX) {
			if (x1()) {
                if (str == "s0") return !bX;
                if (str == "s1") return bX;
			}
            else return true;
		}
		return true;
	}
	else return bX; 
}
//
void FCallInertial::MooreAction()
{
	string strState = FGetState();
	if (strState=="s5")	{ pFDiscreteTime->y1(); }
}

Listing 2. Implementing a NAND gate

#include "lfsaappl.h"

#include "../FDiscreteTime.h"
extern LArc TBL_DiscreteTime[];
class FIne :
	public FDiscreteTime
{
public:
    bool	FCreationOfLinksForVariables() override;
    LFsaAppl* Create(CVarFSA *pCVF) override { Q_UNUSED(pCVF) return new FIne(nameFsa); }
    bool FInit() override;
    FIne(string strNam, LArc* TBL = TBL_DiscreteTime);
    ~FIne(void);
	CVar *pVarX2;		//  
	CVar *pVarStrNameX2;	//    
	CVar *pVarIfNotX2;	//    
	virtual bool f() override;
protected:
    	int x12() override;
    	bool bX2;
};

#include "stdafx.h"
#include <Ine/FIne.h>
#include "VARFSA/SetVarFsaLibrary.h"

FIne::FIne(string strNam, LArc* pTBL):
    FDiscreteTime(strNam, pTBL)
{
    nTypeElement = FDiscreteTime::cvarINE;
}

FIne::~FIne(void) { }

bool FIne::FInit() {										
// 	 		
	FCreationOfLinksForVariables();
//	 										
	return true;										
}

bool FIne::FCreationOfLinksForVariables() {
//  
	FDiscreteTime::FCreationOfLinksForVariables();
	//      x1, x2
    pVarIfNotX2 = CreateLocVar("not(x2)", CLocVar::vtBool, " 2- : 0- /1-");
	pVarX2 = CreateLocVar("x2", CLocVar::vtBool, " 2- ");
    //  ,         x2
	pVarStrNameX2 = CreateLocVar("strNameX2", CLocVar::vtString, "  2- .(x)");
	// :   ,     
    string str = pVarStrNameX2->strGetDataSrc();
    if (str != "") { pVarX2 = pTAppCore->GetAddressVar(pVarStrNameX2->strGetDataSrc().c_str(), this); }
//
	return true;
}
//
int FIne::x12() { return FDiscreteTime::x12() && pVarX2 != nullptr; }
//
bool FIne::f() {
    //  1- 
    FDiscreteTime::f();
    //   
    bX2 = bool(pVarX2->GetDataSrc());
    if (bool(pVarIfNotX2->GetDataSrc())) bX2 = !bX2;
    //   : 
    return bX1&&bX2;
}

Thanks to OOP, the code of the model of the logical element AND is NOT noticeably smaller than the code of the "parent" delay. Moreover, it is largely determined by the need to create an additional input for the model of the AND element. If, at the structural level, the models match the number of inputs / outputs, then the code will be even smaller. So, the implementation code for the XOR gate generated from a structurally similar model of the AND-NOT element is shown in Listing 3.

Listing 3. Exclusive OR gateway implementation

#include <Ine/FIne.h>

extern LArc TBL_DiscreteTime[];
class FExlusiveOR :
    public FIne
{
public:
    LFsaAppl* Create(CVarFSA *pCVF) { return new FExlusiveOR(nameFsa); }
    FExlusiveOR(string strNam, LArc* TBL = TBL_DiscreteTime);
    ~FExlusiveOR(void);
protected:												
    bool f();
};

#include "stdafx.h"
#include "FExlusiveOR.h"

FExlusiveOR::FExlusiveOR(string strNam, LArc* pTBL):
    FIne(strNam, pTBL)
{
    nTypeElement = FDiscreteTime::cvarExlusiveOR;
}

FExlusiveOR::~FExlusiveOR(void) { }
//
bool FExlusiveOR::f() {
    FIne::f();
    return (bX1&&bX2)||(!bX1&&!bX2);
}

Here, the f () method of the FExlusiveOR class calls the f () method of the FIne class only to read the values of the input variables, then overlapping the value of the NAND function with the value calculated in accordance with the logical function of the new class. In the image and likeness, models of any other two-input logic elements can be created.

3. Conclusions

To implement any digital circuit, the so-called functionally complete set of logic elements is sufficient. It can be, for example, a set of AND, OR, NOT elements. We examined the implementation of the following logical elements - delays, which can be an inverter, AND-NOT and EXCLUSIVE OR elements. They relate to the basic elements that are part of a functionally complete set. In order to implement and / or simulate any scheme, it remains to add to the library, for example, an OR-NOT element or implement a universal custom element that is configured to an element from a functionally complete set. And already this will be quite enough.

As a result, on the basis of the above models, we have in the face of the CPSU environment a full-fledged environment for the logical modeling of digital circuits, which allows you to generate any number of processes from any library element, configure them and establish connections between them. At the same time, the simulation will be more detailed (taking into account all types of delays), more flexible (you can configure the elements individually) than in the case of the two typical logical modeling methods mentioned above - compilation and event. And it will not be a specialized environment, as the model of software processes remains unchanged; it will remain as universal as any other object-oriented programming environment based on the use of the C ++ language.

And more about ... sore. Once upon a time, faced with what is wrong in the scientific literature or, more accurately, a description of such a key logical element as an RS trigger is actually illiterate, as well as the fact that even cool electronics engineers don’t know how it works in detail trigger, I spent a lot of time to figure this out. And I can report that at the moment in the trigger problem, at least for me there are no blank spots (see details [3]). And therefore it remains only to be amazed that, by and large, nothing is changing. As the tabular description of the trigger was given earlier, it is still given today, as there were the notorious forbidden states, and they remained the same as they complained about the unpredictable switching of the trigger when exiting the forbidden state, so they are still in the same ignorance. And this despitethat examples of a sufficiently accurate description of its behavior are already known (see, for example, [4]).

Truly, "Thy deeds are wonderful, Lord!" No, it seems, on the heads of such “RS-trigger descriptors” ... automatic programming and the considered method of modeling logic circuits in the VKPa environment. And if you return to the topic of the article, then, for example, using the above model of the NAND element, you can easily create a trigger model and simulate its operation in detail. Including taking into account the properties of real logic elements that have only an inertial type of delays. Well, if you need a formal proof of the properties of a trigger, then it is given in [5].

Literature

1. ., ., . UML. . . : , 2007. – 493 .
2. ., ., . : . . – .: , 1988. – 309 .
3. . [ ], : habr.com/ru/post/484588 . . . ( 07.01.2020).
4. . . 2- . – .: , 2004. – 432.
5. .. . [ ], : cloud.mail.ru/public/HwsK/T95PMM8Ed . . . ( 01.02.2020).

The implementation of inertial algorithms on the example of logical modeling of digital circuits

1. Introduction

2. Logical modeling of digital circuits

3. Implementation of logic elements

3. Conclusions

More articles: