Μια μηχανή καταστάσεων είναι κάποιο αφηρημένο μοντέλο που περιέχει έναν πεπερασμένο αριθμό καταστάσεων κάποιου πράγματος. Χρησιμοποιείται για την αναπαράσταση και τον έλεγχο της ροής εκτέλεσης οποιωνδήποτε εντολών. Το μηχάνημα κατάστασης είναι ιδανικό για την εφαρμογή τεχνητής νοημοσύνης σε παιχνίδια, λαμβάνοντας μια τακτοποιημένη λύση χωρίς να γράφετε δυσκίνητο και περίπλοκο κώδικα. Σε αυτό το άρθρο, θα καλύψουμε τη θεωρία και θα μάθουμε επίσης πώς να χρησιμοποιούμε μια απλή μηχανή κατάστασης που βασίζεται σε στοίβα.

Έχουμε ήδη δημοσιεύσει μια σειρά άρθρων για τη συγγραφή τεχνητής νοημοσύνης με χρήση κρατικής μηχανής. Αν δεν έχετε διαβάσει ακόμα αυτή τη σειρά, μπορείτε να το κάνετε τώρα:

Τι είναι μια μηχανή πεπερασμένης κατάστασης;

Μια μηχανή πεπερασμένης κατάστασης (ή απλά FSM - μηχανή πεπερασμένης κατάστασης) είναι ένα υπολογιστικό μοντέλο που βασίζεται σε μια μηχανή υποθετικής κατάστασης. Μόνο μία κατάσταση μπορεί να είναι ενεργή κάθε φορά. Επομένως, για να εκτελέσετε οποιαδήποτε ενέργεια, το μηχάνημα πρέπει να αλλάξει την κατάστασή του.

Οι κρατικές μηχανές χρησιμοποιούνται συνήθως για να οργανώσουν και να αναπαραστήσουν τη ροή της εκτέλεσης κάτι. Αυτό είναι ιδιαίτερα χρήσιμο κατά την εφαρμογή AI σε παιχνίδια. Για παράδειγμα, για να γράψουμε τον «εγκέφαλο» του εχθρού: κάθε κράτος αντιπροσωπεύει κάποιο είδος δράσης (επίθεση, αποφυγή κ.λπ.).

Ένα πεπερασμένο αυτόματο μπορεί να αναπαρασταθεί ως γράφημα, οι κορυφές του οποίου είναι οι καταστάσεις και οι ακμές είναι οι μεταβάσεις μεταξύ τους. Κάθε άκρη έχει μια ετικέτα που υποδεικνύει πότε πρέπει να γίνει η μετάβαση. Για παράδειγμα, στην παραπάνω εικόνα, μπορείτε να δείτε ότι το αυτόματο θα αλλάξει την κατάσταση από "περιπλάνηση" σε κατάσταση "επίθεση", με την προϋπόθεση ότι ο παίκτης είναι κοντά.

Προγραμματισμός καταστάσεων και οι μεταβάσεις τους

Η υλοποίηση μιας μηχανής πεπερασμένης κατάστασης ξεκινά με την αναγνώριση των καταστάσεων και των μεταβάσεων μεταξύ τους. Φανταστείτε μια κρατική μηχανή που περιγράφει τις ενέργειες ενός μυρμηγκιού που μεταφέρει φύλλα σε μια μυρμηγκοφωλιά:

Το σημείο εκκίνησης είναι η κατάσταση «βρίσκω φύλλο», η οποία παραμένει ενεργή μέχρι το μυρμήγκι να βρει το φύλλο. Όταν συμβεί αυτό, το κράτος θα αλλάξει σε «πάω σπίτι». Η ίδια κατάσταση θα παραμείνει ενεργή μέχρι το μυρμήγκι μας να φτάσει στη μυρμηγκοφωλιά. Μετά από αυτό, η κατάσταση αλλάζει ξανά σε "βρες φύλλο".

Εάν η κατάσταση "εύρεση φύλλου" είναι ενεργή, αλλά ο δρομέας του ποντικιού βρίσκεται δίπλα στο μυρμήγκι, τότε η κατάσταση αλλάζει σε "τρέξτε μακριά". Μόλις το μυρμήγκι βρεθεί σε αρκετά ασφαλή απόσταση από τον κέρσορα του ποντικιού, η κατάσταση θα αλλάξει ξανά σε "εύρεση φύλλου".

Λάβετε υπόψη ότι όταν πηγαίνετε σπίτι ή βγαίνετε από το σπίτι, το μυρμήγκι δεν θα φοβάται τον δρομέα του ποντικιού. Γιατί; Και επειδή δεν υπάρχει αντίστοιχη μετάβαση.

Εφαρμογή μιας απλής κρατικής μηχανής

Μια μηχανή κατάστασης μπορεί να υλοποιηθεί χρησιμοποιώντας μια κλάση. Ας το ονομάσουμε FSM. Η ιδέα είναι να εφαρμοστεί κάθε κατάσταση ως μέθοδος ή συνάρτηση. Θα χρησιμοποιήσουμε επίσης την ιδιότητα activeState για να προσδιορίσουμε την ενεργή κατάσταση.

Δημόσια κλάση FSM ( private var activeState:Function; // δείκτης στην ενεργή κατάσταση της αυτόματης δημόσιας συνάρτησης FSM() ( ) δημόσια συνάρτηση setState(state:Function) :void (activState = κατάσταση; ) ενημέρωση δημόσιας συνάρτησης() :void ( if ( activeState != null) ( activeState(); ) ) )

Κάθε κράτος είναι μια λειτουργία. Επιπλέον, έτσι ώστε να καλείται κάθε φορά που ενημερώνεται το πλαίσιο του παιχνιδιού. Όπως ήδη αναφέρθηκε, το activeState θα αποθηκεύσει έναν δείκτη στη συνάρτηση ενεργής κατάστασης.

Η μέθοδος update() της κλάσης FSM πρέπει να ονομάζεται κάθε καρέ παιχνιδιού. Και αυτός, με τη σειρά του, θα καλέσει τη λειτουργία αυτού του κράτους, το οποίο στο αυτή τη στιγμήείναι ενεργό.

Η μέθοδος setState() θα ορίσει τη νέα ενεργή κατάσταση. Επιπλέον, κάθε συνάρτηση που ορίζει κάποια κατάσταση του αυτόματου δεν χρειάζεται να ανήκει στην κλάση FSM - αυτό κάνει την τάξη μας πιο καθολική.

Χρησιμοποιώντας κρατική μηχανή

Ας εφαρμόσουμε ant AI. Παραπάνω, έχουμε ήδη δείξει ένα σύνολο καταστάσεων και μεταβάσεων μεταξύ τους. Ας τα ξαναδείξουμε, αλλά αυτή τη φορά θα επικεντρωθούμε στον κώδικα.

Το μυρμήγκι μας αντιπροσωπεύεται από την κλάση Ant, η οποία έχει ένα εγκεφαλικό πεδίο. Αυτό είναι απλώς ένα παράδειγμα της κλάσης FSM.

Δημόσια κλάση Ant ( δημόσια θέση var:Vector3D; δημόσια ταχύτητα var:Vector3D; δημόσιο var εγκέφαλος:FSM; δημόσια συνάρτηση Ant(posX:Number, posY:Number) ( position = new Vector3D(posX, posY); velocity = new Vector3D( -1, -1); εγκέφαλος = νέο FSM(); // Ξεκινήστε ψάχνοντας για ένα φύλλο. εγκέφαλος. setState(findLeaf); ) /** * Κατάσταση "findLeaf". * Κάνει το μυρμήγκι να αναζητά φύλλα. */ δημόσια συνάρτηση findLeaf( ) :void ( ) /** * Η κατάσταση "goHome" * Αναγκάζει το μυρμήγκι να πάει στη μυρμηγκοφωλιά */ δημόσια συνάρτηση goHome() :void ( ) /** * Η κατάσταση "runAway" * Προκαλεί την μυρμήγκι να τρέξει μακριά από τον κέρσορα του ποντικιού * / δημόσια συνάρτηση runAway() :void ( ) δημόσια λειτουργία ενημέρωση():void ( // Ενημέρωση του μηχανήματος κατάστασης. Αυτή η συνάρτηση θα καλέσει // τη συνάρτηση ενεργής κατάστασης: findLeaf(), goHome () ή runAway(). brain.update(); // Εφαρμόστε ταχύτητα στην κίνηση του μυρμηγκιού. moveBasedOnVelocity(); ) (...) )

Η κλάση Ant περιέχει επίσης ιδιότητες ταχύτητας και θέσης. Αυτές οι μεταβλητές θα χρησιμοποιηθούν για τον υπολογισμό της κίνησης χρησιμοποιώντας τη μέθοδο Euler. Η συνάρτηση update() καλείται κάθε φορά που ενημερώνεται το πλαίσιο του παιχνιδιού.

Παρακάτω ακολουθεί η υλοποίηση καθεμιάς από τις μεθόδους, ξεκινώντας από την findLeaf(), την κατάσταση που είναι υπεύθυνη για την εύρεση φύλλων.

Δημόσια συνάρτηση findLeaf() :void ( // Μετακινεί το μυρμήγκι στο φύλλο. velocity = new Vector3D(Game.instance.leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance (Παιχνίδι .instance.leaf, αυτό)<= 10) { // Муравей только что подобрал листок, время // возвращаться домой! brain.setState(goHome); } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши находится рядом. Бежим! // Меняем состояние автомата на runAway() brain.setState(runAway); } }

Η κατάσταση goHome() χρησιμοποιείται για να κάνει το μυρμήγκι να πάει σπίτι.

Δημόσια συνάρτηση goHome() :void ( // Μετακινεί το μυρμήγκι στην αρχική ταχύτητα = νέο Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance( Παιχνίδι. instance.home, αυτό)<= 10) { // Муравей уже дома. Пора искать новый лист. brain.setState(findLeaf); } }

Και τέλος, η κατάσταση runAway() - χρησιμοποιείται κατά την αποφυγή του δρομέα του ποντικιού.

Δημόσια συνάρτηση runAway() :void ( // Μετακινεί το μυρμήγκι μακριά από την ταχύτητα του δρομέα = νέο Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Είναι ο κέρσορας ακόμα γύρω ? if ( distance(Game.mouse, this) > MOUSE_THREAT_RADIUS) ( // Όχι, είναι ήδη μακριά. Ήρθε η ώρα να επιστρέψουμε στην εύρεση των φύλλων. brain.setState(findLeaf); ) )

Βελτίωση FSM: Αυτοματοποίηση βάσει στοίβας

Φανταστείτε ότι το μυρμήγκι στο δρόμο για το σπίτι πρέπει επίσης να τρέξει μακριά από τον δρομέα του ποντικιού. Έτσι θα μοιάζουν οι καταστάσεις του FSM:

Φαίνεται σαν μια ασήμαντη αλλαγή. Όχι, μια τέτοια αλλαγή μας δημιουργεί πρόβλημα. Φανταστείτε ότι η σημερινή κατάσταση είναι «ξεφυγή». Εάν ο δρομέας του ποντικιού απομακρυνθεί από το μυρμήγκι, τι πρέπει να κάνει: να πάει σπίτι ή να ψάξει για ένα φύλλο;

Η λύση σε αυτό το πρόβλημα είναι μια μηχανή κατάστασης που βασίζεται σε στοίβα. Σε αντίθεση με το απλό FSM που εφαρμόσαμε παραπάνω, αυτό το είδος FSM χρησιμοποιεί μια στοίβα για τη διαχείριση καταστάσεων. Στην κορυφή της στοίβας βρίσκεται η ενεργή κατάσταση και οι μεταβάσεις συμβαίνουν όταν προστίθενται/αφαιρούνται καταστάσεις από τη στοίβα.

Και εδώ είναι μια οπτική επίδειξη της λειτουργίας μιας μηχανής κατάστασης που βασίζεται στη στοίβα:

Υλοποίηση ενός FSM που βασίζεται σε στοίβα

Μια τέτοια μηχανή πεπερασμένης κατάστασης μπορεί να υλοποιηθεί με τον ίδιο τρόπο όπως μια απλή. Η διαφορά θα είναι η χρήση μιας σειράς δεικτών στις απαιτούμενες καταστάσεις. Δεν θα χρειαζόμαστε πλέον την ιδιότητα activeState, γιατί η κορυφή της στοίβας θα δείχνει ήδη στην ενεργή κατάσταση.

Δημόσια κλάση StackFSM ( private var stack:Array; δημόσια συνάρτηση StackFSM() ( this.stack = new Array(); ) public function update() :void ( var currentStateFunction:Function = getCurrentState(); if (currentStateFunction != null) ( currentStateFunction(); ) ) δημόσια συνάρτηση popState() :Function ( return stack.pop(); ) δημόσια συνάρτηση pushState(state:Function) :void (if (getCurrentState() != κατάσταση) (stack.push(state) ; ) ) δημόσια συνάρτηση getCurrentState() :Function (επιστροφή stack.length > 0 ? stack : null; ) )

Σημειώστε ότι η μέθοδος setState() έχει αντικατασταθεί με pushState() (προσθήκη νέας κατάστασης στην κορυφή της στοίβας) και popState() (αφαίρεση κατάστασης από την κορυφή της στοίβας).

Χρησιμοποιώντας το FSM που βασίζεται σε στοίβα

Είναι σημαντικό να σημειωθεί ότι όταν χρησιμοποιείτε μια μηχανή κατάστασης που βασίζεται σε στοίβα, κάθε κατάσταση είναι υπεύθυνη για την αφαίρεση της από τη στοίβα όταν δεν χρειάζεται. Για παράδειγμα, η κατάσταση επίθεσης() θα πρέπει η ίδια να αφαιρεθεί από τη στοίβα εάν ο εχθρός έχει ήδη καταστραφεί.

Δημόσια κλάση Ant ( (...) public var brain:StackFSM; δημόσια συνάρτηση Ant(posX:Number, posY:Number) ( (...) brain = new StackFSM(); // Ξεκινήστε αναζητώντας εγκέφαλο φύλλου. pushState( findLeaf); (...) ) /** * Κατάσταση "findLeaf". * Κάνει το μυρμήγκι να αναζητά φύλλα. */ δημόσια συνάρτηση findLeaf() :void ( // Μετακινεί το μυρμήγκι στο φύλλο. ταχύτητα = νέο Vector3D(Game.instance. leaf.x - position.x, Game.instance.leaf.y - position.y); if (distance(Game.instance.leaf, this)<= 10) { //Муравей только что подобрал листок, время // возвращаться домой! brain.popState(); // removes "findLeaf" from the stack. brain.pushState(goHome); // push "goHome" state, making it the active state. } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "findLeaf", что означает, // что состояние "findLeaf" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "goHome". * Заставляет муравья идти в муравейник. */ public function goHome() :void { // Перемещает муравья к дому velocity = new Vector3D(Game.instance.home.x - position.x, Game.instance.home.y - position.y); if (distance(Game.instance.home, this) <= 10) { // Муравей уже дома. Пора искать новый лист. brain.popState(); // removes "goHome" from the stack. brain.pushState(findLeaf); // push "findLeaf" state, making it the active state } if (distance(Game.mouse, this) <= MOUSE_THREAT_RADIUS) { // Курсор мыши рядом. Надо бежать! // Состояние "runAway" добавляется перед "goHome", что означает, // что состояние "goHome" вновь будет активным при завершении состояния "runAway". brain.pushState(runAway); } } /** * Состояние "runAway". * Заставляет муравья убегать от курсора мыши. */ public function runAway() :void { // Перемещает муравья подальше от курсора velocity = new Vector3D(position.x - Game.mouse.x, position.y - Game.mouse.y); // Курсор все еще рядом? if (distance(Game.mouse, this) >MOUSE_THREAT_RADIUS) ( // Όχι, είναι ήδη μακριά. Ήρθε η ώρα να επιστρέψουμε στην αναζήτηση για φύλλα. brain.popState(); ) ) (...) )

συμπέρασμα

Οι κρατικές μηχανές είναι σίγουρα χρήσιμες για την εφαρμογή λογικής τεχνητής νοημοσύνης στα παιχνίδια. Μπορούν εύκολα να αναπαρασταθούν ως γράφημα, το οποίο επιτρέπει στον προγραμματιστή να δει όλες τις πιθανές επιλογές.

Η εφαρμογή μιας κρατικής μηχανής με συναρτήσεις κατάστασης είναι μια απλή αλλά ισχυρή τεχνική. Ακόμη πιο πολύπλοκες εμπλοκές καταστάσεων μπορούν να υλοποιηθούν χρησιμοποιώντας FSM.

Ένα από τα κριτήρια για την πολυπλοκότητα ενός πεπερασμένου αυτόματου είναι ο αριθμός των καταστάσεων του. Όσο μικρότερος είναι αυτός ο αριθμός, τόσο πιο απλή είναι η διακριτή συσκευή που υλοποιεί αυτό το αυτόματο. Επομένως, ένα από τα σημαντικά προβλήματα στη θεωρία των πεπερασμένων αυτόματα είναι η κατασκευή ενός αυτόματου με τον μικρότερο αριθμό καταστάσεων.

Δεδομένου ότι στους σύγχρονους υπολογιστές οποιαδήποτε πληροφορία αναπαρίσταται με τη μορφή δυαδικών κωδικών, τότε για να δημιουργήσετε ένα αυτόματο, μπορείτε να χρησιμοποιήσετε στοιχεία που έχουν μόνο δύο διαφορετικές σταθερές καταστάσεις, η μία από τις οποίες αντιστοιχεί στον αριθμό 0 και η άλλη στον αριθμό 1.

Ακολουθούν μερικά παραδείγματα πεπερασμένων αυτόματα.

Παράδειγμα 1. Στοιχείο καθυστέρησης (στοιχείο μνήμης).

Τα στοιχεία καθυστέρησης είναι μια συσκευή με μία είσοδο και μία έξοδο. Επιπλέον, η τιμή του σήματος εξόδου εκείνη τη στιγμή t συμπίπτει με την τιμή του σήματος την προηγούμενη στιγμή. Σχηματικά, το στοιχείο καθυστέρησης μπορεί να απεικονιστεί ως εξής (Εικ. 2).

Ας υποθέσουμε ότι το αλφάβητο εισόδου και άρα εξόδου είναι Χ ={0, 1}, Υ =(0, 1). Επειτα Q =(0, 1). Κάτω από την κατάσταση του στοιχείου καθυστέρησης εκείνη τη στιγμή t είναι κατανοητό το περιεχόμενο του στοιχείου μνήμης τη δεδομένη στιγμή. Με αυτόν τον τρόπο q (t )= Χ (t 1), α Υ (t )= q (t )=Χ (t 1).

Ας ορίσουμε το στοιχείο καθυστέρησης από τον πίνακα, όπου ένα 1 =0, ένα 2 =1, q 1 =0, q 2 =1,

(ένα 1 , q 1)= (0, 0)=0,  (ένα 1 , q 1)= (0, 0)=0;

(ένα 1 , q 2)= (0, 1)=0,  (ένα 1 , q 2)= (0, 1)=1;

(ένα 2 , q 1)= (1, 0)=1,  (ένα 2 , q 1)= (1, 0)=0;

(ένα 2 , q 2)= (1, 1)=1,  (ένα 2 , q 2)= (1, 1)=1;

q ένα
	=0,  =0	=0,  =1
	=1,  =0	=1,  =1

Το διάγραμμα Moore φαίνεται στην εικ. 3

Για να αναπαραστήσουμε αυτό το αυτόματο με ένα σύστημα Boolean συναρτήσεων, χρησιμοποιούμε τον πίνακα αυτόματα και τον παραπάνω αλγόριθμο. Σε αυτήν την περίπτωση, η κωδικοποίηση δεν είναι απαραίτητη, καθώς τα αλφάβητα και οι καταστάσεις εισόδου και εξόδου είναι ήδη κωδικοποιημένα.

Ας προσέξουμε το γεγονός ότι m=p=p =2. Επειτα κ =r =μικρό =1, και επομένως το στοιχείο καθυστέρησης δίνεται από δύο συναρτήσεις  και  . Ο πίνακας αλήθειας αυτών των συναρτήσεων περιέχει 2 κ + r =2 2 =4 σειρές και κ +r +r +μικρό =4 στήλες:

Χ	z

Παράδειγμα 2. Δυαδικός διαδοχικός αθροιστής.

Αυτός ο σειριακός αθροιστής είναι μια συσκευή που προσθέτει δύο αριθμούς στο δυαδικό σύστημα. Οι αριθμοί τροφοδοτούνται στις εισόδους του αθροιστή Χ 1 και Χ 2, ξεκινώντας με τα λιγότερο σημαντικά ψηφία. Στην έξοδο, σχηματίζεται μια ακολουθία που αντιστοιχεί στην καταχώρηση αριθμού Χ 1 +Χ 2 στο δυαδικό σύστημα υπολογισμού (Εικ. 4).

Τα αλφάβητα εισόδου και εξόδου ορίζονται μοναδικά: Χ ={00; 01; 10; 11}, Υ =(0,1). Το σύνολο των καταστάσεων καθορίζεται από την τιμή της μεταφοράς κατά την προσθήκη των αντίστοιχων bits αριθμών Χ 1 και Χ 2. Αν κατά την πρόσθεση κάποιων ψηφίων σχηματιστεί μεταφορά, τότε θα υποθέσουμε ότι ο αθροιστής έχει περάσει στην κατάσταση q ένας . Εάν δεν υπάρχει μεταφορά, θα υποθέσουμε ότι ο αθροιστής βρίσκεται στην κατάσταση q 0 .

Ο αθροιστής δίνεται από έναν πίνακα.

q ένα	q 0	q 1
	q 0 , 0	q 0 , 1
	q 0 , 1	q 1 , 0
	q 0 , 1	q 1 , 0
	q 1 , 0	q 1 , 1

Το διάγραμμα Moore ενός διαδοχικού αθροιστή φαίνεται στο σχ. 5.

Σημειώστε ότι οι χαρακτήρες εισόδου και εξόδου είναι ήδη κωδικοποιημένοι. Κωδικοποιούμε τις καταστάσεις ως εξής:  (q 0)=0,  (q 1)=1. Επομένως, ο διαδοχικός αθροιστής δίνεται από δύο συναρτήσεις Boolean, ο πίνακας αλήθειας των οποίων έχει ως εξής:

Χ 1	Χ 2	z

Παράδειγμα 3. Σχέδιο σύγκρισης ισότητας.

Ένα κύκλωμα σύγκρισης ισότητας είναι μια συσκευή που συγκρίνει δύο αριθμούς. Χ 1 και Χ 2 , που δίνεται στο δυαδικό σύστημα. Αυτή η συσκευή λειτουργεί ως εξής. Στην είσοδο της συσκευής διαδοχικά, ξεκινώντας από το υψηλότερο, τροφοδοτούνται τα ψηφία των αριθμών Χ 1 και Χ 2. Αυτές οι τάξεις συγκρίνονται. Εάν τα bit ταιριάζουν, το σήμα εξόδου 0 σχηματίζεται στην έξοδο του κυκλώματος, διαφορετικά το σήμα 1 εμφανίζεται στην έξοδο. Είναι σαφές ότι η εμφάνιση του 1 στην ακολουθία εξόδου σημαίνει ότι οι συγκριμένοι αριθμοί Χ 1 και Χ 2 διαφορετικός. Εάν η ακολουθία εξόδου είναι μηδέν και το μήκος της ταιριάζει με τον αριθμό των ψηφίων των συγκρίσιμων αριθμών, τότε Χ 1 και Χ 2 .

Για αυτό το μηχάνημα Χ ={00, 01, 10, 11}; Υ ={0,1}.

Η λειτουργία του κυκλώματος καθορίζεται από δύο καταστάσεις. κατάσταση q 0 αντιστοιχεί στην ισότητα των δυαδικών ψηφίων που συγκρίνονται αυτήν τη στιγμή. Σε αυτή την περίπτωση, το μηχάνημα παραμένει στην ίδια κατάσταση. Εάν την επόμενη στιγμή τα συγκριτικά ψηφία είναι διαφορετικά, τότε το αυτόματο θα μεταβεί σε νέα κατάσταση q 1 και παραμένει σε αυτό, αφού σημαίνει ότι οι αριθμοί είναι διαφορετικοί. Έτσι, το σχήμα σύγκρισης μπορεί να καθοριστεί από τον πίνακα:

q Χ	q 0	q 1
	q 0 , 0	q 1 , 1
	q 1 , 1	q 1 , 1
	q 1 , 1	q 1 , 1
	q 0 , 0	q 1 , 1

Το διάγραμμα Moore του σχήματος σύγκρισης για την ισότητα φαίνεται στο σχήμα. 6.

Θα κωδικοποιήσουμε τις καταστάσεις ως εξής:  (q 0)=0,  (q 1)=1. Το αυτόματο θα έχει δύο λειτουργίες.

Χ 1	Χ 2	z

Παράδειγμα 4. Σχήμα σύγκρισης ανισότητας.

Το κύκλωμα σύγκρισης ανισότητας είναι μια συσκευή που σας επιτρέπει να μάθετε εάν η σύγκριση Χ 1 και Χ 2, και αν δεν είναι ίσα, βρείτε ποιο είναι μεγαλύτερο από το άλλο. Αυτή η συσκευή έχει δύο εισόδους και δύο εξόδους. Σήματα εξόδου y 1 (t ) και y 2 (t ) καθορίζονται σύμφωνα με τους ακόλουθους κανόνες:

y 1 (t )=y 2 (t )=0 αν Χ 1 (t )=Χ 2 (t );

y 1 (t )=1, y 2 (t )=0 αν Χ 1 (t )>Χ 2 (t ), αυτό είναι Χ 1 (t )=1, Χ 2 (t )=0;

y 1 (t )=0, y 2 (t )=1 αν Χ 1 (t )<Χ 2 (t ), αυτό είναι Χ 1 (t )=0, Χ 2 (t )=1.

Έτσι, όταν εφαρμόζεται στην είσοδο του κυκλώματος σύγκρισης για ανισότητα αριθμών Χ 1 =Χ 1(l)… Χ 1 (t ) και Χ 2 =Χ 2(l)… Χ 2 (t ) τα ψηφία αυτών των αριθμών συγκρίνονται διαδοχικά, ξεκινώντας από τα υψηλότερα. Τα σήματα εξόδου διαμορφώνονται σύμφωνα με τους παραπάνω κανόνες. Επιπλέον, εάν η ακολουθία εξόδου αποτελείται από μηδενικά ζεύγη, τότε Χ 1 =Χ 2. Εάν το πρώτο είναι διαφορετικό από το μηδέν, το ζεύγος έχει τη μορφή , () έπειτα Χ 1 >Χ 2 (Χ 1 <Χ 2).

Από την περιγραφή του κυκλώματος προκύπτει ότι

Χ ={00, 01, 10, 11}, Υ ={00, 01, 10}.

Η κατάσταση του σχήματος ορίζεται ως εξής. Υποθέτουμε ότι στον αρχικό χρόνο t =1 το μηχάνημα είναι σε κατάσταση q 1 . Αν τα συγκριτικά ψηφία των αριθμών Χ 1 και Χ 2 ταιριάζουν, τότε το μηχάνημα παραμένει σε αυτήν την κατάσταση. Σημειώστε ότι στην έξοδο θα εμφανιστεί το σήμα 00. Εάν το ψηφίο του αριθμού Χ 1 θα είναι μικρότερο (μεγαλύτερο) από το αντίστοιχο ψηφίο του αριθμού Χ 2, τότε το μηχάνημα θα μεταβεί στην κατάσταση q 2 (q 3). Σε αυτήν την περίπτωση, ένα σήμα 01 (10) θα εμφανιστεί στην έξοδο. Στο μέλλον, κατά την υποβολή των υπολοίπων ψηφίων των αριθμών Χ 1 και Χ 2 στις εισόδους του αυτόματου, το αυτόματο θα παραμείνει στην κατάσταση q 2 (q 3) και δημιουργήστε το σύμβολο εξόδου 10 (01). Από τα παραπάνω προκύπτει ότι το σχήμα σύγκρισης για την ανισότητα μπορεί να προσδιοριστεί από τον πίνακα:

q Χ	q 1	q 2	q 3
	q 1 , 00	q 2 , 01	q 3 , 10
	q 2 , 01	q 2 , 01	q 3 , 10
	q 3 , 10	q 2 , 01	q 3 , 10
	q 1 , 00	q 2 , 01	q 3 , 10

Το αντίστοιχο διάγραμμα Moore φαίνεται στο Σχ. 7.

Τα αλφάβητα εισόδου και εξόδου είναι ήδη κωδικοποιημένα εδώ. πολιτείες q 1 , q 2 και q 3 κωδικοποιούν:  1 (q 1)=00,  (q 2)=01,  (q 3)=10.

Επομένως, αυτό το κύκλωμα μπορεί να οριστεί από ένα σύστημα που αποτελείται από τέσσερις συναρτήσεις Boolean που εξαρτώνται από τέσσερις μεταβλητές. Αυτές οι συναρτήσεις ορίζονται εν μέρει και δίνονται από τον πίνακα αλήθειας

	Χ 1	Χ 2	z 1	z 2

Στον πίνακα, τα σύμβολα * επισημαίνουν σύνολα μεταβλητών Χ 1 , Χ 2 , z 1 , z 2 , στο οποίο οι συναρτήσεις  1 ,  2 ,  1 ,  2 δεν ορίζονται. Ας βάλουμε τιμές συνάρτησης  1 ,  2 ,  1 ,  2 σε αυτά τα σετ ίσο με 1.

Το άρθρο εξετάζει απλές μηχανές κατάστασης και την υλοποίησή τους στη C++ χρησιμοποιώντας κατασκευές μεταγωγέων, πίνακες χρόνου εκτέλεσης και τη βιβλιοθήκη Boost Statechart.

Εισαγωγή

Σε γενικές γραμμές, η μηχανή πεπερασμένης κατάστασης (Finite State Machine), στα μάτια του χρήστη, είναι ένα μαύρο κουτί στο οποίο μπορείτε να μεταφέρετε κάτι και να λάβετε κάτι από εκεί. Αυτή είναι μια πολύ βολική αφαίρεση που σας επιτρέπει να αποκρύψετε έναν πολύπλοκο αλγόριθμο, επιπλέον, οι μηχανές κατάστασης είναι πολύ αποτελεσματικές.

Τα πεπερασμένα αυτόματα απεικονίζονται ως διαγράμματα που αποτελούνται από καταστάσεις και μεταβάσεις. Επιτρέψτε μου να εξηγήσω με ένα απλό παράδειγμα:

Όπως πιθανώς μαντέψατε, αυτό είναι ένα διάγραμμα κατάστασης λαμπτήρα. Η αρχική κατάσταση υποδεικνύεται με μαύρο κύκλο, μεταβάσεις με βέλη, ορισμένα βέλη υπογράφονται - αυτά είναι συμβάντα μετά τα οποία το μηχάνημα μεταβαίνει σε άλλη κατάσταση. Έτσι, αμέσως από την αρχική κατάσταση, μπαίνουμε στην κατάσταση σβηστό φως- η λάμπα δεν είναι αναμμένη. Εάν πατήσετε το κουμπί, το μηχάνημα θα αλλάξει την κατάστασή του και θα ακολουθήσει το βέλος που επισημαίνεται πιέστε το κουμπί, στο κράτος φως αναμμένο- η λάμπα είναι αναμμένη. Μπορείτε να μεταβείτε από αυτήν την κατάσταση ξανά με το βέλος, αφού πατήσετε το κουμπί, στην κατάσταση σβηστό φως.

Τα τραπέζια άλματος χρησιμοποιούνται επίσης ευρέως:

Πρακτική εφαρμογή μηχανών

Οι μηχανές κατάστασης χρησιμοποιούνται ευρέως στον προγραμματισμό. Για παράδειγμα, είναι πολύ βολικό να φανταστείτε τη λειτουργία της συσκευής με τη μορφή ενός αυτόματου. Αυτό θα κάνει τον κώδικα απλούστερο και ευκολότερο στον πειραματισμό και τη συντήρηση.

Επίσης, τα πεπερασμένα αυτόματα χρησιμοποιούνται για τη σύνταξη όλων των ειδών αναλυτών και αναλυτών κειμένου, με τη βοήθεια τους μπορείτε να αναζητήσετε αποτελεσματικά υποσυμβολοσειρές, οι κανονικές εκφράσεις μεταφράζονται επίσης σε ένα πεπερασμένο αυτόματο.

Για παράδειγμα, θα εφαρμόσουμε ένα αυτόματο για την καταμέτρηση αριθμών και λέξεων σε ένα κείμενο. Αρχικά, ας συμφωνήσουμε ότι ένας αριθμός θα είναι μια ακολουθία ψηφίων από το 0 έως το 9 αυθαίρετου μήκους, που περιβάλλεται από χαρακτήρες κενού διαστήματος (κενό, καρτέλα, τροφοδοσία γραμμής). Μια λέξη θα θεωρείται μια ακολουθία αυθαίρετου μήκους που αποτελείται από γράμματα και περιβάλλεται επίσης από χαρακτήρες κενού διαστήματος.

Σκεφτείτε ένα διάγραμμα:

Από την αρχική κατάσταση φτάνουμε στην κατάσταση Αρχή. Ελέγχουμε τον τρέχοντα χαρακτήρα και αν είναι γράμμα, τότε πηγαίνουμε στην κατάσταση Λέξηκατά μήκος του βέλους που σημειώνεται ως Γράμμα. Αυτή η κατάσταση προϋποθέτει ότι τη στιγμή που εξετάζουμε μια λέξη, η ανάλυση περαιτέρω συμβόλων είτε θα επιβεβαιώσει αυτήν την υπόθεση είτε θα τη διαψεύσει. Επομένως, σκεφτείτε τον επόμενο χαρακτήρα, εάν είναι γράμμα, τότε η κατάσταση δεν αλλάζει (σημειώστε το κυκλικό βέλος που επισημαίνεται ως Γράμμα). Εάν ο χαρακτήρας δεν είναι γράμμα, αλλά αντιστοιχεί σε χαρακτήρα διαστήματος, τότε αυτό σημαίνει ότι η υπόθεση ήταν σωστή και βρήκαμε τη λέξη (κινούμε κατά μήκος του βέλους Χώροςσε κατάσταση Αρχή). Εάν το σύμβολο δεν είναι ούτε γράμμα ούτε κενό, τότε κάναμε λάθος στην υπόθεση και η ακολουθία που εξετάζουμε δεν είναι λέξη (ακολουθούμε το βέλος άγνωστοςσε κατάσταση Παραλείπω).

Ικανός Παραλείπωμένουμε μέχρι να συναντήσουμε έναν χαρακτήρα διαστήματος. Αφού βρεθεί το κενό, ακολουθούμε το βέλος Χώροςσε κατάσταση Αρχή. Αυτό είναι απαραίτητο για να παραλείψουμε εντελώς τη γραμμή που δεν ταιριάζει με το μοτίβο αναζήτησής μας.

Μετά τη μετάβαση στο κράτος Αρχή, ο κύκλος αναζήτησης επαναλαμβάνεται από την αρχή. Ο κλάδος αναγνώρισης αριθμών είναι παρόμοιος με τον κλάδο αναγνώρισης λέξεων.

Αυτόματη χρήση οδηγιών διακόπτη

Το πρώτο είναι οι πιθανές καταστάσεις:

Μετά από αυτό, επαναλαμβάνουμε τη συμβολοσειρά, ολισθώντας τον τρέχοντα χαρακτήρα στο αυτόματο. Το ίδιο το αυτόματο είναι μια δήλωση διακόπτη που εκτελεί πρώτα μια μετάβαση στην ενότητα τρέχουσας κατάστασης. Μέσα στην ενότητα υπάρχει μια κατασκευή if-else, η οποία, ανάλογα με το συμβάν (εισερχόμενος χαρακτήρας), αλλάζει την τρέχουσα κατάσταση:

const size_t μήκος = text.length () ; για (size_t i = 0 ; i != μήκος; ++ i) ( const char ρεύμα = κείμενο[ i] ; switch (κατάσταση) ( case State_Start: if (std:: isdigit (current) ) ( state = State_Number; ) αλλιώς εάν (std:: isalpha (τρέχον) ) ( κατάσταση = Κατάσταση_Λέξη; ) διάλειμμα ; περίπτωση Κατάσταση_Αριθμός: αν (std:: ισοδιάστημα (τρέχουσα) ) (

Εδώ βλέπουμε το διάγραμμα - την τρέχουσα κατάσταση αριθμός, Εκδήλωση Χώρος(συναντήθηκε ένας χαρακτήρας διαστήματος), που σημαίνει ότι βρέθηκε ένας αριθμός:

FoundNumber() ; κατάσταση = State_Start; ) else if (! std:: isdigit (current) ) ( state = State_Skip; ) break ; case State_Word: if (std:: isspace (current) ) ( FoundWord() ; state = State_Start; ) other if (! std:: isalpha (current) ) ( state = State_Skip; ) break ; case State_Skip: if (std::isspace (current) ) ( state = State_Start; ) break ; ) )

Αποτέλεσμα:

Υψηλής απόδοσης

Ευκολία υλοποίησης για απλούς αλγόριθμους

- δύσκολο να διατηρηθεί

Ερμηνεία χρόνου εκτέλεσης

Η ιδέα αυτής της προσέγγισης είναι απλή - πρέπει να δημιουργήσετε έναν πίνακα μετάβασης, να τον συμπληρώσετε και, στη συνέχεια, όταν συμβεί ένα συμβάν, να βρείτε την ακόλουθη κατάσταση στον πίνακα και να κάνετε τη μετάβαση:

enum Συμβάντα( Event_Space, Event_Digit, Event_Letter, Event_Unknown ); void ProcessEvent(Συμβάν Γεγονότων) ; ... struct Transition ( State BaseState_; Events Event_; State TargetState_;); void AddTransition (Πολιτεία από Πολιτεία, Συμβάντα Εκδηλώσεις, Πολιτεία σε Πολιτεία) ; ... typedef std::vector< transition>TransitionTable; TransitionTable Transitions_; Πολιτεία Τρέχουσα κατάσταση_;

Συμπληρώνοντας τον πίνακα:

AddTransition(State_Start, Event_Digit, State_Number) ; AddTransition(State_Start, Event_Letter, State_Word) ; AddTransition(State_Number, Event_Space, State_Start) ; AddTransition(State_Number, Event_Letter, State_Skip) ; Προσθήκη Μετάβασης(Κατάσταση_Αριθμός, Συμβάν_Άγνωστο, Κατάσταση_Παράλειψη) ; AddTransition(State_Word, Event_Space, State_Start) ; AddTransition(State_Word, Event_Digit, State_Skip) ; AddTransition(State_Word, Event_Unknown, State_Skip) ; AddTransition(State_Skip, Event_Space, State_Start) ;

Αποδείχθηκε αρκετά ξεκάθαρο. Η πληρωμή για σαφήνεια θα είναι πιο αργή λειτουργία του μηχανήματος, η οποία, παρεμπιπτόντως, συχνά δεν έχει σημασία.

Για να μπορεί το αυτόματο, με την εμφάνιση ορισμένων γεγονότων, να ειδοποιήσει κάποιον κώδικα, μπορείτε να προσθέσετε στη δομή πληροφορίες σχετικά με τη μετάβαση ( μετάβαση) δείκτης συνάρτησης ( δράση) που θα ονομάζεται:

typedef void (DynamicMachine:: * Action) () ; struct Transition ( State BaseState_; Events Event_; State TargetState_; Action Action_;) ; ... void AddTransition(Κατάσταση απόΠολιτεία, Συμβάν Γεγονότων, Πολιτεία σε Πολιτεία, Δράση δράσης) ; ... AddTransition (State_Number, Event_Space, State_Start, & DynamicMachine:: FoundNumber ) ;

Αποτέλεσμα:

Ευελιξία και ορατότητα

Πιο εύκολο στη συντήρηση

- Λιγότερη απόδοση σε σύγκριση με τα μπλοκ διακόπτη

Ερμηνεία χρόνου εκτέλεσης. Βελτιστοποίηση ταχύτητας

Μπορεί η ορατότητα να συνδυαστεί με την ταχύτητα; Είναι απίθανο ένα αυτόματο να είναι εξίσου αποτελεσματικό με ένα αυτόματο που βασίζεται σε μπλοκ διακόπτη, αλλά είναι δυνατό να κλείσει το κενό. Για να γίνει αυτό, είναι απαραίτητο να δημιουργηθεί ένας πίνακας από τον πίνακα, έτσι ώστε για να λάβετε πληροφορίες σχετικά με τη μετάβαση, να μην κάνετε αναζήτηση, αλλά να κάνετε μια επιλογή με βάση τον αριθμό της κατάστασης και του συμβάντος:

Το αποτέλεσμα επιτυγχάνεται σε βάρος της κατανάλωσης μνήμης.

Αποτέλεσμα:

Ευελιξία, ορατότητα

Αποτελεσματικός

- Κατανάλωση μνήμης (πιθανώς ασήμαντη)

Boost Statechart

Συζητήσαμε διάφορους τρόπους για να εφαρμόσετε μόνοι σας μια κρατική μηχανή. Για μια αλλαγή, προτείνω να σκεφτείτε μια βιβλιοθήκη για την κατασκευή αυτόματα από το Boost. Αυτή η βιβλιοθήκη είναι πολύ ισχυρή, τα προτεινόμενα χαρακτηριστικά σάς επιτρέπουν να δημιουργήσετε πολύ περίπλοκες μηχανές πεπερασμένης κατάστασης. Θα το δούμε μάλλον εν συντομία.

Ας ορίσουμε λοιπόν πρώτα τα γεγονότα:

namespace Events( struct Digit : boost::statechart::event< Digit>( ) ; struct Επιστολή : boost::statechart::event< Letter>( ) ; struct Space : boost::statechart::event< Space>( ) ; structUnknown : boost::statechart::event< Unknown> { } ; }

Το ίδιο το μηχάνημα (σημειώστε ότι η δεύτερη παράμετρος του προτύπου είναι η αρχική κατάσταση):

struct Machine : boost::statechart::state_machine< Machine, States:: Start > { } ;

Και τα ίδια τα κράτη. Μέσα σε καταστάσεις, απαιτείται να οριστεί ένας τύπος που περιγράφει μεταβάσεις ( αντιδράσεις), και αν υπάρχουν πολλές μεταβάσεις, τότε καταχωρίστε τις στη λίστα τύπων boost::mpl::list. Δεύτερη παράμετρος προτύπου απλή_κατάσταση– τύπος που περιγράφει το αυτοκίνητο. Οι μεταβάσεις περιγράφονται από τις παραμέτρους του προτύπου μετάβασης, το ζεύγος Εκδήλωση - Επόμενη Πολιτεία:

Καταστάσεις χώρου ονομάτων ( struct Start : boost::statechart::simple_state< Start, Machine> < boost:: statechart :: transition < Events:: Digit , States:: Number >< Events:: Letter , States:: Word >> αντίδραση; ) ; struct Number : boost::statechart::simple_state< Number, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statechart::transition< Events:: Letter , States:: Skip >, boost::statechart::transition< Events:: Unknown , States:: Skip >> αντίδραση; ) ; struct Word : boost::statechart::simple_state< Word, Machine>( typedef boost::mpl::list< boost:: statechart :: transition < Events:: Space , States:: Start >, boost::statechart::transition< Events:: Digit , States:: Skip >, boost::statechart::transition< Events:: Unknown , States:: Skip >> αντίδραση; ) ; struct Skip : boost::statechart::simple_state< Skip, Machine>( typedef boost::statechart::transition< Events:: Space , States:: Start >αντιδράσεις? ) ; )

Το μηχάνημα είναι κατασκευασμένο, μένει μόνο να το αρχικοποιήσετε και μπορείτε να χρησιμοποιήσετε:

Μηχανή μηχανής? machine.initiate(); ...machine .process_event(Events::Space() );

Αποτέλεσμα:

Ευελιξία, επεκτασιμότητα

- Αποτελεσματικότητα

Εκτέλεση

Έγραψα ένα δοκιμαστικό πρόγραμμα για να ελέγξω την ταχύτητα των κατασκευασμένων αυτόματα. Μέσα από τα μηχανήματα, οδήγησα το κείμενο μεγέθους ~ 17 MB. Ιδού τα αποτελέσματα του τρεξίματος:

Φόρτωση κειμένου Μήκος κειμένου: 17605548 BYTES 0.19 S Τρέξιμο Λέξεις boostmachine: 998002, Αριθμοί: 6816 0.73 S Λέξεις DynamicMachine: 998002, Αριθμοί: 6816 0.56 S Τρέχουσα FastDynamicmachine Λέξεις: 998002, Αριθμοί: 6816 0. μικρό

Τι μένει ακριτικό

Αρκετές ακόμη υλοποιήσεις πεπερασμένων αυτόματων παρέμειναν ακάλυπτες (συνιστώ http://www.rsdn.ru/article/alg/Static_Finite_State_Machine.xml και http://www.rsdn.ru/article/alg/FiniteStateMachine.xml), γεννήτριες που build αυτόματα από περιγραφές, τη βιβλιοθήκη Meta State Machine από την έκδοση Boost 1.44.0, καθώς και επίσημες περιγραφές καταστάσεων μηχανών. Ο περίεργος αναγνώστης μπορεί να εξοικειωθεί με όλα τα παραπάνω.

Η θεωρία των αυτομάτων είναι ένα τμήμα διακριτών μαθηματικών που μελετά μοντέλα διακριτών μετατροπέων πληροφοριών. Τέτοιοι μετατροπείς είναι τόσο πραγματικές συσκευές (υπολογιστές, ζωντανοί οργανισμοί) όσο και φανταστικές συσκευές (αξιωματικές θεωρίες, μαθηματικές μηχανές). Στην ουσία, μια μηχανή πεπερασμένης κατάστασης μπορεί να περιγραφεί ως συσκευή Μ , που έχει κανάλια εισόδου και εξόδου, ενώ σε κάθε μία από τις διακριτές χρονικές στιγμές, που ονομάζονται ρολογιακές στιγμές, βρίσκεται σε μία από τις τελικές καταστάσεις.

Στο κανάλι εισόδου ανά πάσα στιγμή t =1, 2, ... στη συσκευή Μ φτάνουν σήματα εισόδου (από κάποιο πεπερασμένο σύνολο σημάτων). Ο νόμος της αλλαγής κατάστασης στην επόμενη χρονική στιγμή ρυθμίζεται ανάλογα με το σήμα εισόδου και την κατάσταση της συσκευής την τρέχουσα χρονική στιγμή. Το σήμα εξόδου εξαρτάται από την κατάσταση και το σήμα εισόδου την τρέχουσα ώρα (Εικ. 1).

Η μηχανή κατάστασης είναι ένα μαθηματικό μοντέλο πραγματικών διακριτών συσκευών επεξεργασίας πληροφοριών.

κρατική μηχανή ονομάζεται το σύστημα Α= (Χ , Q , Υ ,  ,  ), όπου Χ , Q , Υ είναι αυθαίρετα μη-κενά πεπερασμένα σύνολα, και  και  - λειτουργίες, εκ των οποίων:

πολλά Χ ={ένα 1 , ..., ένα Μ ) λέγεται αλφάβητο εισαγωγής , και τα στοιχεία του είναι σήματα εισόδου , οι ακολουθίες τους είναι μέσα συνθηματικές φράσεις ;

πολλά Q ={q 1 , ..., q n ) λέγεται πολλά κράτη αυτόματο και τα στοιχεία του - πολιτείες ;

πολλά Υ ={σι 1 , ..., σι Π ) λέγεται αλφάβητο εξόδου , τα στοιχεία του είναι σήματα εξόδου , οι ακολουθίες τους είναι λέξεις εξόδου ;

λειτουργία  : Χ  Q Q που ονομάζεται λειτουργία μετάβασης ;

λειτουργία  :Χ  Q Υ που ονομάζεται λειτουργία εξόδου .

Με αυτόν τον τρόπο,  (Χ , q )Q ,  (Χ , q )Υ για  Χ Χ , q Q .

Μια φανταστική συσκευή συνδέεται με τη μηχανή κατάστασης, η οποία λειτουργεί ως εξής. Μπορεί να είναι σε κατάσταση από το σετ Q , λάβετε σήματα από το σετ Χ και εκδίδουν σήματα από ένα σετ Υ .

2. Μέθοδοι για τον ορισμό ενός πεπερασμένου αυτόματου

Υπάρχουν αρκετοί ισοδύναμοι τρόποι για τον ορισμό των αφηρημένων αυτόματα, τρεις από τους οποίους είναι: πινακοειδής , γεωμετρικός και λειτουργικός .

2.1 Αντιστοίχιση πίνακα του μηχανήματος

Από τον ορισμό του αυτόματου προκύπτει ότι μπορεί πάντα να οριστεί από έναν πίνακα με δύο εισόδους που περιέχει t γραμμές και Π στήλες, όπου στη διασταύρωση της στήλης q και γραμμές ένα αξίζουν οι τιμές συνάρτησης  (ένα Εγώ , q ι ),  (ένα Εγώ , q ι ).

q ένα	q 1		q ι		q n
ένα 1	(ένα 1 , q 1),  (ένα 1 , q 1)		(ένα 1 , q ι ),  (ένα 1 , q ι )		(ένα 1 , q n ),  (ένα 1 , q n )
ένα Εγώ	(ένα Εγώ , q 1),  (ένα Εγώ , q 1)		(ένα Εγώ , q ι ),  (ένα Εγώ , q ι )		(ένα Εγώ , q n ),  (ένα Εγώ , q n )
ένα Μ	(ένα Μ , q 1),  (ένα Μ , q 1)		(ένα Μ , q ι ),  (ένα Μ , q ι )		(ένα Μ , q n ),  (ένα Μ , q n )

2.2. Ορισμός αυτόματου με διάγραμμα Moore

Ένας άλλος τρόπος καθορισμού μιας μηχανής πεπερασμένης κατάστασης είναι ο γραφικός, δηλαδή η χρήση γραφήματος. Το αυτόματο αναπαρίσταται ως ένα επισημασμένο κατευθυνόμενο γράφημα σολ(Q , ρε ) με πολλές κορυφές Q και πολλά τόξα ρε ={(q ι ,  (ένα Εγώ , q ι ))| q ι Q , ένα Εγώ Χ ), ενώ το τόξο ( q ι ,  (ένα Εγώ , q ι )) επισημαίνεται με ένα ζευγάρι ( ένα Εγώ ,  (ένα Εγώ , q ι )). Έτσι, με αυτή τη μέθοδο, οι καταστάσεις του αυτόματου απεικονίζονται με κύκλους, στους οποίους εισάγονται τα σύμβολα των καταστάσεων q ι (ι = 1, …, n ). Από κάθε κύκλο πραγματοποιείται t βέλη (κατευθυνόμενες άκρες) ένα προς ένα που αντιστοιχούν στους χαρακτήρες του αλφαβήτου εισόδου Χ ={ένα 1 , ..., ένα Μ ). Βέλος που αντιστοιχεί στο γράμμα ένα Εγώ Χ και φεύγοντας από τον κύκλο q ι Q , το ζεύγος ( ένα Εγώ ,  (ένα Εγώ , q ι )), και αυτό το βέλος οδηγεί σε έναν κύκλο που αντιστοιχεί σε  (ένα Εγώ , q ι ).

Το σχέδιο που προκύπτει ονομάζεται αυτόματο γράφημα ή, Διάγραμμα Moore . Για όχι πολύ περίπλοκα αυτόματα, αυτή η μέθοδος είναι πιο ενδεικτική από ό πινακοειδής.

Σήμερα θα μιλήσουμε για πολυβόλα, αλλά σε καμία περίπτωση για αυτά που κρατούν οι στρατιώτες στα χέρια τους Ρωσικός στρατός. Θα μιλήσουμε για ένα τόσο ενδιαφέρον στυλ προγραμματισμού μικροελεγκτών όπως ο αυτόματος προγραμματισμός. Πιο συγκεκριμένα, αυτό δεν είναι καν ένα στυλ προγραμματισμού, αλλά μια ολόκληρη ιδέα, χάρη στην οποία ένας προγραμματιστής μικροελεγκτή μπορεί να κάνει τη ζωή του πολύ πιο εύκολη. Εξαιτίας του οποίου πολλές εργασίες που παρουσιάζονται στον προγραμματιστή επιλύονται πολύ πιο εύκολα και απλούστερα, απαλλάσσοντας τον προγραμματιστή από πονοκέφαλο. Παρεμπιπτόντως, ο αυτόματος προγραμματισμός ονομάζεται συχνά Τεχνολογία SWITCH.

Θέλω να σημειώσω ότι το ερέθισμα για τη συγγραφή αυτής της ανάρτησης ήταν σειρά άρθρων για την τεχνολογία SWITCH Βλαντιμίρ Ταταρτσέφσκι. Η σειρά άρθρων ονομάζεται «Εφαρμογή της τεχνολογίας SWITCH στην ανάπτυξη εφαρμοσμένων λογισμικόγια μικροελεγκτές "Έτσι σε αυτό το άρθρο θα προσπαθήσω ως επί το πλείστον να δώσω ένα παράδειγμα ενός κώδικα εργασίας και την περιγραφή του.

Παρεμπιπτόντως, έχω προγραμματίσει μια σειρά άρθρων για τον προγραμματισμό, στα οποία θα εξετάσω λεπτομερώς τις τεχνικές προγραμματισμού για μικροελεγκτές ABP, μην χάσετε…. Λοιπόν πάμε!

Το πρόγραμμα εκτελεί διαδοχικά τις εντολές που έχει ορίσει ο προγραμματιστής. Για τακτικά πρόγραμμα υπολογιστήείναι απολύτως φυσιολογικό όταν το πρόγραμμα έχει ολοκληρώσει και έχει σταματήσει την εκτέλεσή του, ενώ εμφανίζει τα αποτελέσματα της εργασίας του στην οθόνη.

Ένα πρόγραμμα μικροελεγκτή δεν μπορεί απλώς να τερματίσει την εκτέλεσή του. Φανταστείτε ότι έχετε ενεργοποιήσει τη συσκευή αναπαραγωγής ή το μαγνητόφωνο. Έχετε πατήσει το κουμπί λειτουργίας, επιλέξατε το τραγούδι που θέλετε και απολαύσατε τη μουσική. Ωστόσο, όταν η μουσική σταμάτησε να αναστατώνει το τύμπανο του αυτιού σας, η συσκευή αναπαραγωγής παγώνει και δεν αντιδρά με κανέναν τρόπο στο πάτημα των κουμπιών, και ακόμη περισσότερο στο χορό σας με ένα ντέφι.

Και τι είναι αυτό; Όλα είναι καλά - το χειριστήριο, αυτό στο βάθος της συσκευής σας, μόλις ολοκλήρωσε την εκτέλεση του προγράμματός του. Εδώ μπορείτε να δείτε πόσο άβολο αποδεικνύεται.

Από εδώ λοιπόν συμπεραίνουμε ότι το πρόγραμμα για τον μικροελεγκτή απλά δεν πρέπει να σταματήσει. Στην ουσία, θα έπρεπε να είναι ένας άπειρος βρόχος - μόνο σε αυτήν την περίπτωση ο παίκτης μας θα λειτουργούσε σωστά. Στη συνέχεια, θα σας δείξω ποια είναι τα σχέδια κώδικα προγράμματοςγια μικροελεγκτές, αυτά δεν είναι καν σχέδια, αλλά κάποια στυλ προγραμματισμού.

Στυλ προγραμματισμού.

Το "Προγραμματισμός στυλ" ακούγεται κάπως ακατανόητο, αλλά οκ. Τι θέλω να πω με αυτό;Ας φανταστούμε ότι ένας άνθρωπος δεν έχει ξανακάνει προγραμματισμό, δηλαδή γενικά ένα πλήρες ομοίωμα.

Αυτό το άτομο έχει διαβάσει πολλά βιβλία σχετικά με τον προγραμματισμό, έχει μάθει όλες τις βασικές δομές της γλώσσας.Συλλέγει πληροφορίες σπιθαμή προς σπιθαμή, αφού πλέον η πρόσβαση στις πληροφορίες είναι απεριόριστη. Καλά όλα αυτά, αλλά πώς θα είναι τα πρώτα του προγράμματα; Μου φαίνεται ότι δεν θα φιλοσοφήσει, αλλά θα ακολουθήσει το μονοπάτι από το απλό στο σύνθετο.

Αυτά τα στυλ λοιπόν είναι βήματα που οδηγούν από ένα απλό επίπεδο σε ένα πιο σύνθετο, αλλά ταυτόχρονα πιο αποτελεσματικό.

Στην αρχή δεν σκέφτηκα κανένα χαρακτηριστικά σχεδίουπρογράμματα. Μόλις σχημάτισα τη λογική του προγράμματος - σχεδίασα ένα διάγραμμα ροής και έγραψα τον κώδικα. Από αυτό που συναντούσε συνεχώς μια τσουγκράνα. Αλλά αυτή ήταν η πρώτη φορά που δεν έκανα ατμόλουτρο και χρησιμοποίησα το στυλ "απλού βρόχου", μετά άρχισα να χρησιμοποιώ διακοπές, μετά υπήρχαν αυτόματα και φύγαμε ...

1. Απλό looping. Το πρόγραμμα σε αυτήν την περίπτωση κάνει βρόχους χωρίς περιπλοκές και αυτό έχει τα θετικά και τα αρνητικά του. Επιπλέον, μόνο στην απλότητα της προσέγγισης, δεν χρειάζεται να εφεύρετε πονηρά σχέδια, γράφετε όπως νομίζετε (σκάβοντας σταδιακά τον δικό σας τάφο).

Void main(void) ( initial_AL(); //αρχικοποίηση της περιφέρειας while(1) ( Leds_BLINK(); //λειτουργία του φλας LED signal_on(); //λειτουργία ενεργοποίησης του σήματος signal_off(); // λειτουργία απενεργοποίησης του σήματος l=button( ); //μεταβλητή που είναι υπεύθυνη για το πάτημα των κουμπιών διακόπτης(l) //Ανάλογα με την τιμή της μεταβλητής, εκτελείται μία ή άλλη ενέργεια (περίπτωση 1: ( Deistvie1(); / /Αντί για συνάρτηση, μπορεί να υπάρχει υπό όρους χειριστή deistvie2(); //ή μερικές ακόμη διακλαδώσεις μεταγωγέα Deistvie3(); deistvie4(); deistvie5(); ) περίπτωση 2: ( Deistvie6(); Deistvie7(); Deistvie8(); Deistvie9(); Deistvie10(); ); . . . . . . . . ) ))

Το σημείο εργασίας του προγράμματος κινείται με τη σειρά. Σε αυτήν την περίπτωση, όλες οι ενέργειες, οι συνθήκες και οι κύκλοι εκτελούνται διαδοχικά. Ο κώδικας αρχίζει να επιβραδύνεται, πρέπει να εισαγάγετε πολλές επιπλέον συνθήκες, περιπλέκοντας έτσι την αντίληψη.

Όλα αυτά μπερδεύουν πολύ το πρόγραμμα, δημιουργώντας ένα κουβάρι συνθηκών από τον κώδικα. Ως αποτέλεσμα, αυτός ο κωδικός δεν μπορεί να προστεθεί ή να αφαιρεθεί, γίνεται σαν ένα μονολιθικό κομμάτι. Φυσικά, όταν ο όγκος δεν είναι μεγάλος, ο κωδικός μπορεί να τροποποιηθεί, αλλά όσο πιο μακριά τόσο πιο δύσκολο.

Με αυτήν την προσέγγιση, έγραψα πολλά προγράμματα, δεν ήταν μεγάλα και λειτουργούσαν αρκετά, αλλά η ορατότητα άφηνε πολλά να είναι επιθυμητά. Για να προσθέσω κάποια νέα συνθήκη, έπρεπε να φτυαρίσω ολόκληρο τον κωδικό, γιατί όλα ήταν δεμένα. Αυτό προκάλεσε πολλά λάθη και πονοκεφάλους. Ο μεταγλωττιστής ορκίστηκε το συντομότερο δυνατό, ο εντοπισμός σφαλμάτων ενός τέτοιου προγράμματος μετατράπηκε σε κόλαση.

2. Κύκλος + διακοπές.

Μπορείτε να επιλύσετε εν μέρει τον άπειρο κύκλο πέδησης χρησιμοποιώντας διακοπές. Οι διακοπές βοηθούν να σπάσετε τον φαύλο κύκλο, σας βοηθούν να μην χάσετε ένα σημαντικό γεγονός, προσθέστε επιπλέον λειτουργίες (διακοπές από χρονόμετρα, εξωτερικές διακοπές).

Ας υποθέσουμε ότι μπορείτε να κλείσετε την επεξεργασία των κουμπιών ή να παρακολουθήσετε ένα σημαντικό συμβάν σε μια διακοπή. Ως αποτέλεσμα, το πρόγραμμα γίνεται πιο οπτικό αλλά όχι λιγότερο μπερδεμένο.

Δυστυχώς, η διακοπή δεν θα σας σώσει από το χάος στο οποίο μετατρέπεται το πρόγραμμα. Δεν θα είναι δυνατό να χωριστεί σε μέρη αυτό που είναι ένα ενιαίο σύνολο.

3. Αυτόματος προγραμματισμός.

Φτάνουμε λοιπόν στο κύριο θέμα αυτού του άρθρου. Ο προγραμματισμός σε μηχανές πεπερασμένης κατάστασης σώζει το πρόγραμμα από τις ελλείψεις που είναι εγγενείς στα δύο πρώτα παραδείγματα. Το πρόγραμμα γίνεται πιο απλό, είναι εύκολο να τροποποιηθεί.

Ένα πρόγραμμα γραμμένο σε στυλ αυτόματου είναι σαν ένα διακόπτη που, ανάλογα με τις συνθήκες, μεταβαίνει στη μία ή την άλλη κατάσταση. Ο αριθμός των καταστάσεων είναι αρχικά γνωστός στον προγραμματιστή.

Χονδρικά, είναι σαν διακόπτης φώτων. Υπάρχουν δύο καταστάσεις ενεργοποίησης και απενεργοποίησης και δύο συνθήκες ενεργοποίησης και απενεργοποίησης. Λοιπόν, πρώτα πρώτα.

Εφαρμογή multitasking στην τεχνολογία μεταγωγής.

Ο μικροελεγκτής μπορεί να ελέγχει το φορτίο, να αναβοσβήνει τα LED, να παρακολουθεί τα πλήκτρα και πολλά άλλα. Πώς όμως να τα κάνεις όλα αυτά ταυτόχρονα; Υπάρχουν πολλές λύσεις σε αυτό το ζήτημα. Το απλούστερο από αυτά που ήδη ανέφερα είναι η χρήση των διακοπών.

Κατά τη διάρκεια του προγράμματος, όταν εμφανίζεται μια διακοπή, ο ελεγκτής αποσπάται από την εκτέλεση του κώδικα προγράμματος και εκτελεί για λίγο ένα άλλο κομμάτι του προγράμματος για το οποίο είναι υπεύθυνη η διακοπή. Η διακοπή θα λειτουργήσει, τότε το σημείο εργασίας του προγράμματος θα συνεχίσει από το σημείο από το οποίο ο ελεγκτής διακόπηκε από τη διακοπή (η ίδια η λέξη υποδηλώνει ότι ο ελεγκτής έχει διακοπεί).

Ένας άλλος τρόπος για να εφαρμόσετε το multitasking είναι να χρησιμοποιήσετε λειτουργικά συστήματα. Ναι, έχουν ήδη αρχίσει να εμφανίζονται μικρά λειτουργικά συστήματα, τα οποία μπορούν να χρησιμοποιηθούν σε ελεγκτή χαμηλής κατανάλωσης. Αλλά συχνά αυτή η μέθοδος αποδεικνύεται κάπως περιττή. Εξάλλου, γιατί να σπαταλάτε τους πόρους των ελεγκτών με περιττή εργασία, όταν είναι πολύ πιθανό να τα βγάλετε πέρα ​​με λίγη αιματοχυσία.

Σε προγράμματα που γράφτηκαν με χρήση τεχνολογίας μεταγωγής, μια τέτοια «ψευδαίσθηση» πολλαπλών εργασιών επιτυγχάνεται χάρη στο σύστημα ανταλλαγής μηνυμάτων. Έγραψα "ψευδαίσθηση" γιατί πραγματικά είναι, επειδή το πρόγραμμα φυσικά δεν μπορεί να εκτελέσει διαφορετικά μέρη του κώδικα ταυτόχρονα. Θα μιλήσω για το σύστημα ανταλλαγής μηνυμάτων λίγο παρακάτω.

Σύστημα ανταλλαγής μηνυμάτων.

Μπορείτε να καταστρέψετε πολλές διεργασίες και να δημιουργήσετε την ψευδαίσθηση του multitasking χρησιμοποιώντας το σύστημα ανταλλαγής μηνυμάτων.

Ας υποθέσουμε ότι χρειαζόμαστε ένα πρόγραμμα στο οποίο ενεργοποιείται το LED. Εδώ έχουμε δύο μηχανήματα, ας τα ονομάσουμε LEDON - το μηχάνημα που είναι υπεύθυνο για την ενεργοποίηση του LED και το μηχάνημα LEDOFF - το μηχάνημα που είναι υπεύθυνο για το σβήσιμο του LED.

Κάθε ένα από τα αυτόματα έχει δύο καταστάσεις, δηλαδή, το αυτόματο μπορεί να είναι σε ενεργή ή ανενεργή κατάσταση, όπως ένας διακόπτης μαχαιριού είναι είτε ενεργοποιημένος είτε απενεργοποιημένος.

Όταν ενεργοποιείται το ένα μηχάνημα, το LED ανάβει, όταν το άλλο μηχάνημα ενεργοποιείται, το LED σβήνει. Εξετάστε ένα μικρό παράδειγμα:

Int main(void) ( INIT_PEREF(); //αρχικοποίηση περιφερειακών (LED) InitGTimers(); //αρχικοποίηση χρονοδιακόπτων InitMessages(); //αρχικοποίηση του μηχανισμού επεξεργασίας μηνυμάτων InitLEDON(); //αρχικοποίηση του αυτόματου LEDON InitLEDOFF(); // προετοιμασία του αυτόματου LEDOFF SendMessage(MSG_LEDON_ACTIVATE); //ενεργοποίηση του αυτόματου LEDON sei(); //Ενεργοποίηση διακοπών //Κύριος βρόχος προγράμματος while(1) ( ProcessLEDON(); //Επανάληψη του LEDON automaton ProcessLEDOFF(); //επανάληψη του αυτόματου LEDOFF ProcessMessages (); //επεξεργασία μηνυμάτων);

Στις γραμμές 3-7, συμβαίνουν διάφορες αρχικοποιήσεις, επομένως δεν μας ενδιαφέρει ιδιαίτερα αυτό τώρα. Αλλά τότε συμβαίνει το εξής: πριν ξεκινήσουμε τον κύριο βρόχο (ενώ (1)), στέλνουμε ένα μήνυμα στο αυτόματο

Αποστολή μηνύματος(MSG_LEDON_ACTIVATE)

υπεύθυνος για το φωτισμό του LED. Χωρίς αυτό το μικρό βήμα, το hurdy-gurdy μας δεν θα λειτουργήσει. Στη συνέχεια, ο κύριος βρόχος infinite while κάνει το μεγαλύτερο μέρος της δουλειάς.

Μικρή παρέκκλιση:

Το μήνυμα έχει τρεις καταστάσεις. Δηλαδή, η κατάσταση του μηνύματος μπορεί να είναι ανενεργή, ρυθμισμένη αλλά ανενεργή και ενεργή.

Αποδεικνύεται ότι το μήνυμα ήταν αρχικά ανενεργό, όταν στείλαμε το μήνυμα, έλαβε την κατάσταση "εγκατεστημένο αλλά ανενεργό". Και αυτό μας δίνει το εξής. Όταν το πρόγραμμα εκτελείται διαδοχικά, το αυτόματο LEDON δεν λαμβάνει μήνυμα. Παρουσιάζεται μια επανάληψη σε αδράνεια του αυτόματου LEDON, στην οποία το μήνυμα απλά δεν μπορεί να ληφθεί. Εφόσον το μήνυμα έχει την κατάσταση "εγκατεστημένο αλλά ανενεργό", το πρόγραμμα συνεχίζει την εκτέλεσή του.

Αφού όλα τα αυτόματα είναι σε αδράνεια, η ουρά φτάνει στη συνάρτηση ProcessMessages(). Αυτή η συνάρτηση τοποθετείται πάντα στο τέλος του βρόχου, αφού έχουν ολοκληρωθεί όλες οι επαναλήψεις των αυτόματων. Η συνάρτηση ProcessMessages() απλώς αλλάζει το μήνυμα από την κατάσταση "set but inactive" σε "active".

Όταν ο άπειρος βρόχος ολοκληρώσει τον δεύτερο γύρο, η εικόνα είναι ήδη εντελώς διαφορετική. Η επανάληψη του αυτόματου ProcessLEDON δεν θα είναι πλέον αδρανής. Το μηχάνημα θα μπορεί να λάβει το μήνυμα, να μεταβεί στην κατάσταση αναμμένης και επίσης να στείλει το μήνυμα με τη σειρά του. Θα απευθύνεται στο μηχάνημα LEDOFF και κύκλος ζωήςτα μηνύματα θα επαναληφθούν.

Θέλω να σημειώσω ότι τα μηνύματα που έχουν την "ενεργή" κατάσταση καταστρέφονται όταν συναντηθούν με τη συνάρτηση ProcessMessages. Επομένως, ένα μήνυμα μπορεί να ληφθεί μόνο από ένα αυτόματο. Υπάρχει ένας άλλος τύπος μηνυμάτων - αυτά είναι μηνύματα εκπομπής, αλλά δεν θα τα λάβω υπόψη μου, καλύπτονται επίσης καλά στα άρθρα του Tatarchevskiy.

Χρονοδιακόπτες

Με την κατάλληλη ανταλλαγή μηνυμάτων, μπορούμε να ελέγξουμε τη σειρά με την οποία λειτουργούν οι μηχανές κατάστασης, αλλά δεν μπορούμε να κάνουμε χωρίς μηνύματα μόνο.

Ίσως έχετε παρατηρήσει ότι το προηγούμενο παράδειγμα απόσπασμα κώδικα δεν θα λειτουργήσει όπως έπρεπε. Τα μηχανήματα θα ανταλλάξουν μηνύματα, τα LED θα αλλάξουν, αλλά αυτό δεν θα το δούμε. Θα δούμε μόνο ένα αμυδρά φωτισμένο LED.

Κι αυτό γιατί δεν σκεφτήκαμε την αρμόδια επεξεργασία των καθυστερήσεων. Εξάλλου, δεν αρκεί να ανάβουμε και να σβήνουμε εναλλάξ τα LED, το LED πρέπει να παραμένει σε κάθε κατάσταση, για παράδειγμα, για ένα δευτερόλεπτο.

Ο αλγόριθμος θα είναι ο εξής:

Μπορείτε να κάνετε κλικ για μεγέθυνση

Ξέχασα να προσθέσω σε αυτό το μπλοκ διάγραμμα ότι όταν χτυπά ο χρονοδιακόπτης, φυσικά, εκτελείται μια ενέργεια - ανάβει το LED ή σβήνει.

1. Μπαίνουμε στην κατάσταση λαμβάνοντας ένα μήνυμα.

2. Ελέγχουμε τις ενδείξεις του χρονοδιακόπτη/μετρητή, αν χτυπάει, τότε εκτελούμε την ενέργεια, αλλιώς απλώς στέλνουμε ένα μήνυμα στον εαυτό μας.

3. Στέλνουμε μήνυμα στο επόμενο αυτόματο.

4. Έξοδος

Στην επόμενη καταχώρηση, όλα επαναλαμβάνονται.

Πρόγραμμα τεχνολογίας SWITCH. Τρία βήματα.

Και ας γράψουμε ένα πρόγραμμα σε πεπερασμένα αυτόματα και για αυτό θα χρειαστεί να κάνουμε μόνο τρία απλά βήματα. Το πρόγραμμα θα είναι απλό, αλλά αξίζει να ξεκινήσετε με απλά πράγματα. Μας κατάλληλο πρόγραμμαμε εναλλαγή LED. Αυτό είναι πολύ Καλό παράδειγμαας μην εφεύρουμε λοιπόν τίποτα καινούργιο.

Θα γράψω το πρόγραμμα στη γλώσσα C, αλλά αυτό δεν σημαίνει καθόλου ότι σε πεπερασμένα αυτόματα πρέπει να γράφετε μόνο σε C, είναι πολύ πιθανό να χρησιμοποιήσετε οποιαδήποτε άλλη γλώσσα προγραμματισμού.

Το πρόγραμμα θα είναι αρθρωτό και επομένως θα χωρίζεται σε πολλά αρχεία. Οι ενότητες μας θα είναι:

• Η κύρια μονάδα βρόχου του προγράμματος περιέχει τα αρχεία leds_blink.c, HAL.c, HAL.h
• Μονάδα χρονοδιακόπτη περιέχει αρχεία timers.c, timers.h
• Μονάδα επεξεργασίας μηνυμάτων περιέχει αρχεία messages.c, messages.h
  
• Μονάδα μηχανής 1 περιέχει αρχεία ledon.c, ledon.h
• Μονάδα μηχανής 2 περιέχει αρχεία ledoff.c, ledoff .h

Βήμα 1.

Δημιουργούμε ένα έργο και συνδέουμε αμέσως τα αρχεία των στατικών μας μονάδων σε αυτό: timers.c, timers.h, messages.c, messages.h.

Το αρχείο leds_blink.c της ενότητας του κύριου κύκλου του προγράμματος.

#include "hal.h" #include "messages.h" //μονάδα επεξεργασίας μηνυμάτων #include "timers.h" //μονάδα timers //Timer interrupts //############# ################################################################## ############################# ISR(TIMER0_OVF_vect) // Διακοπή διανυσματικής μετάβασης (υπερχείλιση χρονοδιακόπτη μετρητή T0) ( ProcessTimers(); / /Χειριστής διακοπής χρονοδιακόπτη) //############################################################# ############################################## int main (κενό) ( INIT_PEREF(); //αρχικοποίηση της περιφέρειας (LED) InitGTimers(); //αρχικοποίηση των χρονόμετρων InitMessages(); //αρχικοποίηση του μηχανισμού επεξεργασίας μηνυμάτων InitLEDON(); //αρχικοποίηση του αυτόματου LEDON InitLEDOFF(); StartGTimer( TIMER_SEK); //Έναρξη του χρονοδιακόπτη SendMessage(MSG_LEDON_ACTIVATE); //ενεργοποίηση του αυτόματου FSM1 sei(); //Ενεργοποίηση διακοπών //Κύριος βρόχος προγράμματος while(1) ( ProcessLEDON(); //επαναγραφή το αυτόματο LEDON ProcessLEDOFF(); ProcessMessages( ); //επεξεργασία μηνυμάτων);

Στις πρώτες γραμμές, οι υπόλοιπες μονάδες συνδέονται με το κύριο πρόγραμμα. Εδώ βλέπουμε ότι η μονάδα χρονοδιακόπτη και η μονάδα επεξεργασίας μηνυμάτων είναι συνδεδεμένα. Επόμενο στο πρόγραμμα είναι το διάνυσμα διακοπής υπερχείλισης.

Από τη γραμμή int main (void) μπορούμε να πούμε ότι ξεκινά το κύριο πρόγραμμα. Και ξεκινά με την αρχικοποίηση των πάντων και των πάντων. Εδώ αρχικοποιούμε τα περιφερειακά, δηλαδή ορίζουμε τις αρχικές τιμές​​στις θύρες εισόδου/εξόδου του συγκριτή και όλα τα άλλα περιεχόμενα του ελεγκτή. Όλα αυτά γίνονται από τη συνάρτηση INIT_PEREF, την τρέχουμε εδώ, αν και το κύριο σώμα της βρίσκεται στο αρχείο hal.c.

Στη συνέχεια, βλέπουμε την προετοιμασία των χρονόμετρων, τη μονάδα επεξεργασίας μηνυμάτων και την αρχικοποίηση των αυτόματα. Εδώ, αυτές οι λειτουργίες εκκινούνται επίσης απλά, αν και οι ίδιες οι λειτουργίες είναι γραμμένες στα αρχεία των λειτουργικών μονάδων τους. Δείτε πόσο βολικό. Το κύριο κείμενο του προγράμματος παραμένει ευανάγνωστο και δεν είναι γεμάτο με περιττό κώδικα που σπάει το πόδι σας.

Οι κύριες αρχικοποιήσεις έχουν τελειώσει, τώρα πρέπει να ξεκινήσουμε τον κύριο βρόχο. Για να γίνει αυτό, στέλνουμε το μήνυμα έναρξης και, επιπλέον, ξεκινάμε το ρολόι μας - ξεκινάμε το χρονόμετρο.

StartGTimer(TIMER_SEK); //Έναρξη χρονοδιακόπτη SendMessage(MSG_LEDON_ACTIVATE); //ενεργοποίηση μηχανής FSM1

Και ο κύριος βρόχος, όπως είπα, φαίνεται πολύ απλός. Καταγράφουμε τις συναρτήσεις όλων των αυτόματα, απλώς τις γράφουμε σε μια στήλη, χωρίς να ακολουθήσουμε τη σειρά. Αυτές οι λειτουργίες είναι χειριστές αυτόματων και βρίσκονται σε μονάδες αυτόματων. Η λειτουργία της μονάδας επεξεργασίας μηνυμάτων ολοκληρώνει αυτήν την αυτόματη πυραμίδα. Φυσικά, το είπα ήδη νωρίτερα όταν ασχολήθηκα με το σύστημα ανταλλαγής μηνυμάτων. Τώρα μπορείτε να δείτε πώς μοιάζουν δύο ακόμη αρχεία της ενότητας του κύριου βρόχου προγράμματος

Hal.h είναι αρχείο κεφαλίδαςενότητα του κύριου βρόχου του προγράμματος.

#ifndef HAL_h #define HAL_h #include #περιλαμβάνω //Τυπική βιβλιοθήκη με διακοπές #define LED1 0 #define LED2 1 #define LED3 2 #define LED4 3 #define Komparator ACSR //comparator #define ViklKomparator 1<

Όπως μπορείτε να δείτε, αυτό το αρχείο δεν περιέχει εγγενώς ούτε μια γραμμή εκτελέσιμου κώδικα - όλες αυτές είναι αντικαταστάσεις μακροεντολών και συνδέσεις βιβλιοθήκης. Έχοντας αυτό το αρχείο απλώς κάνει τη ζωή πολύ καλή, βελτιώνει την ορατότητα.

Αλλά το αρχείο Hal.c είναι ήδη ένα εκτελέσιμο αρχείο και όπως ήδη ανέφερα, περιέχει διάφορες αρχικοποιήσεις περιφερειακών.

#include "hal.h" void INIT_PEREF(void) ( //Initialize ports I/O //########################## ################################################################## # ##### Komparator = ViklKomparator; //αρχικοποίηση σύγκρισης - απενεργοποίηση DDRD = 1<

Λοιπόν, έδειξα την ενότητα του κύριου κύκλου του προγράμματος, τώρα πρέπει να κάνουμε το τελευταίο βήμα, πρέπει να γράψουμε τις ίδιες τις ενότητες των αυτόματα.

Βήμα 3

Απομένει να γράψουμε τις ενότητες των πεπερασμένων αυτόματα, στην περίπτωσή μας, το αυτόματο LEDON και το αυτόματο LEDOFF. Αρχικά θα δώσω το κείμενο του προγράμματος για το μηχάνημα που ανάβει το LED, το αρχείο ledon.c.

//αρχείο ledon.c #include "ledon.h" #include "timers.h" #include "messages.h" ανυπόγραφο char ledon_state; //state μεταβλητή void InitLEDON(void) ( ledon_state=0; //εδώ μπορείτε να αρχικοποιήσετε άλλες μεταβλητές αυτόματου εάν υπάρχουν ) void ProcessLEDON(void) ( switch(ledon_state) ( case 0: //inactive state if(GetMessage (MSG_LEDON_ACTIVATE )) //αν υπάρχει μήνυμα, θα γίνει αποδεκτό ( //και ο χρονοδιακόπτης θα ελεγχθεί εάν(GetGTimer(TIMER_SEK)==one_sek) //αν ο χρονοδιακόπτης έχει ορίσει 1s, τότε εκτελέστε ( StopGTimer(TIMER_SEK); PORTD = 1<

Εδώ, στις πρώτες γραμμές, όπως πάντα, συνδέονται βιβλιοθήκες και δηλώνονται οι μεταβλητές. Στη συνέχεια, έχουμε ήδη πάει τις λειτουργίες με τις οποίες έχουμε ήδη συναντηθεί. Αυτή είναι η λειτουργία αρχικοποίησης του αυτόματου InitLEDON και η λειτουργία του ίδιου του χειριστή αυτόματου ProcessLEDON.

Στο σώμα του χειριστή, οι λειτουργίες από τη μονάδα χρονοδιακόπτη και τη μονάδα μηνυμάτων βρίσκονται ήδη υπό επεξεργασία. Και η λογική του ίδιου του αυτόματου βασίζεται στον σχεδιασμό του διακόπτη. Και εδώ μπορείτε να δείτε ότι ο χειριστής του αυτόματου μπορεί επίσης να είναι περίπλοκος προσθέτοντας μερικούς διακόπτες θήκης.

Το αρχείο κεφαλίδας για το αυτόματο θα ήταν ακόμα πιο απλό:

//fsm1 αρχείο #ifndef LEDON_h #define LEDON_h #include "hal.h" void InitLEDON(void); void ProcessLEDON(void); #τέλος εαν

Εδώ συνδέουμε το αρχείο συνδέσμου hal.h και καθορίζουμε επίσης τα πρωτότυπα των συναρτήσεων.

Το αρχείο που είναι υπεύθυνο για την απενεργοποίηση του LED θα φαίνεται σχεδόν το ίδιο μόνο στην κατοπτρική εικόνα, επομένως δεν θα το εμφανίσω εδώ - απροθυμία 🙂

Μπορείτε να κατεβάσετε όλα τα αρχεία του έργου εδώ σε αυτόν τον σύνδεσμο ====>>> ΣΥΝΔΕΣΜΟΣ.

Εδώ είναι μόνο τρία βήματα και το πρόγραμμά μας έχει αποκτήσει μια ολοκληρωμένη εμφάνιση, πράγμα που σημαίνει ότι η αποστολή μου για σήμερα τελείωσε και ήρθε η ώρα να ολοκληρώσω. Μου φαίνεται ότι οι πληροφορίες που δίνονται σε αυτό το άρθρο θα είναι πολύ χρήσιμες για εσάς. Αλλά θα φέρει πραγματικό όφελος μόνο όταν κάνετε πράξη αυτή τη γνώση.

Παρεμπιπτόντως, έχω προγραμματίσει μια σειρά από ενδιαφέροντα έργα που θα είναι ιδιαίτερα ενδιαφέροντα, οπότε φροντίστε να το κάνετε εγγραφείτε για νέα άρθρα . Σκοπεύω επίσης να στείλω επιπλέον υλικό, τόσοι πολλοί άνθρωποι έχουν ήδη εγγραφεί μέσω της κύριας σελίδας του ιστότοπου. Μπορείτε να εγγραφείτε και εδώ.

Λοιπόν, τώρα πραγματικά τα έχω όλα, οπότε σας εύχομαι καλή τύχη, καλή διάθεση και τα λέμε ξανά.

N/A Vladimir Vasiliev