[Βιβλία: προαιρετικά μπορείτε να διαβάσετε: Wakerly: "στα γρήγορα" τις §7.3 έως και §7.7 (σελ. 652-714), και ανάμεσά τους "κανονικά" τις σελ. 656-665, σελ. 667-673, σελ. 680-684, σελ. 689-702, και §7.7 (σελ. 706-714)· Mano: σελ. 197-201 (από § 5.5) και σελ. 224-229 (από § 5.7, 5.8).]

10.1   Ακολουθιακά Κυκλώματα:

Εδώ θα μελετήσουμε τις "Μηχανές Πεπερασμένων Καταστάσεων (Finite State Machines - FSM). Από μιάν άποψη, όλα τα ακολουθιακά κυκλώματα είναι μηχανές πεπερασμένων καταστάσεων, διότι, αν έχουν n bits μνήμης (κατάστασης), τότε βρίσκονται ανά πάσα στιγμή σε μιάν από τις 2ⁿ διαφορετικές καταστάσεις τις οποίες διαθέτουν --οι οποίες και είναι πάντα πεπερασμένες. Όμως, συνηθίζουμε να αναφερόμαστε με τον όρο "FSM" κυρίως σε εκείνα τα ακολουθιακά κυκλώματα τα οποία έχουν σχετικά λίγες καταστάσεις, και των οποίων τη λειτουργία μπορούμε να περιγράψουμε και να καταλάβουμε καλύτερα αν μιλήσουμε γιά το πώς η κάθε μιά κατάστασή τους, σε συνδυασμό με τις τιμές εισόδου, καθορίζει τις εξόδους και την επόμενη κατάσταση· συνήθως, η περιγραφή αυτή γίνεται με ένα "Διάγραμμα (Μετάβασης) Καταστάσεων" (State (Transition) Diagram), όπως θα δούμε αμέσως παρακάτω. Μεγαλύτερα ακολουθιακά κυκλώματα, με πολλά bits μνήμης, συνήθως τα μελετάμε και τα σχεδιάζουμε κόβοντάς τα σε υποκυκλώματα, μερικά από τα οποία τα περιγράφουμε σαν FSM's ενώ άλλα τα περιγράφουμε και τα μελετάμε με άλλους τρόπους (μνήμες RAM, datapaths --που θα πούμε αργότερα-- κλπ).

10.2   Μετρητές, και το Διάγραμμα Καταστάσεών τους:

Κάτω από το κύκλωμα φαίνεται το διάγραμμα καταστάσεων αυτού του μετρητή. Οι 8 κύκλοι παριστάνουν τις 8 διαφορετικές καταστάσεις στις οποίες αυτός μπορεί να βρίσκεται, αφού έχει 3 bits κατάστασης. Ονομάσαμε κάθε κατάσταση με το δεκαδικό ισοδύναμο του αριθμού που σχηματίζουν τα 3 bits κατάστασης. Τα βέλη παριστάνουν τις μεταβάσεις καταστάσεων: εάν σε δεδομένο κύκλο ρολογιού το κύκλωμα βρίσκεται σε δεδομένη κατάσταση, και είναι δεδομένες οι τιμές των εισόδων του, τότε το αντίστοιχο βέλος δείχνει σε ποιάν επόμενη κατάσταση θα πάει το κύκλωμα στον επόμενο κύκλο ρολογιού. Τα μπλέ βέλη, που σημειώνονται με u (από "up", δηλ. μέτρηση προς τα επάνω), αντιστοιχούν στην τιμή εισόδου ελέγχου του πολυπλέκτη που επιλέγει την είσοδο +1 (και ενώ ταυτόχρονα η είσοδος reset' είναι 1)· υπ' αυτές τις συνθήκες, η επόμενη κατάσταση είναι εκείνη με κωδικό κατά 1 μεγαλύτερο από την παρούσα. Τα κόκκινα βέλη, που σημειώνονται με d (down - κάτω), αντιστοιχούν στην είσοδο που επιλέγει το -1, και μας μεταφέρουν στην κατάσταση με κωδικό κατά 1 μικρότερο της παρούσας. Τα βέλη που σημειώνονται με n (noop - καμιά πράξη) αντιστοιχούν στην είσοδο που επιλέγει το 0, και γι' αυτό η επόμενη κατάσταση ταυτίζεται με την παρούσα.

Κάθε ακολουθιακό κύκλωμα πρέπει να έχει έναν τρόπο αρχικοποίησης (reset) όταν του πρωτοδίνουμε τάση τροφοδοσίας, ή σε περίπτωση (έκτακτης) "ανάγκης" --όταν "χάνουμε το λογαριασμό" σε ποιά κατάσταση βρίσκεται, ή όταν πάει και "κολλάει" σε μιά κατάσταση και δεν ξέρουμε πώς αλλοιώς να το βγάλουμε από εκεί. Όπως έχουμε πει, όταν πρωτοανάβουμε την τροφοδοσία ενός flip-flop, αυτό πηγαίνει τυχαία σε μιάν από τις δύο σταθερές καταστάσεις του, 0 ή 1, και δεν υπάρχει τρόπος να προβλεφθεί σε ποιάν από τις δυό θα πάει (σαν να ρίχνεις ένα κέρμα "κορώνα-γράμματα"). Έτσι, η κατάσταση εκκίνησης ενός ακολουθιακού κυκλώματος είναι τυχαία, και πρέπει να υπάρχει τρόπος, στη συνέχεια, αυτό να έλθει σε γνωστή και επιθυμητή αρχική κατάσταση. Στο παραπάνω κύκλωμα, η αρχικοποίηση γίνεται ενεργοποιώντας το σήμα "reset", δηλαδή reset'=0, οπότε η επόμενη κατάσταση είναι πάντα η 0, ανεξαρτήτως προηγούμενης κατάστασης και των άλλων εισόδων. Στο διάγραμμα καταστάσεων, αυτό παριστάνεται με τα μάυρα βέλη που σημειώνονται με "r'" (έχει παραληφθεί ένα ακόμα τέτοιο βέλος, από την κατάσταση 0 στον εαυτό της, που έπρεπε να υπάρχει αλλά δεν χωρούσε στο σχήμα).

10.3   Παράδειγμα FSM: Φώτα Κυκλοφορίας σε Διασταύρωση Οδών

10.3.1   Κλασσικά φανάρια, χωρίς ανιχνευτές, με αναλογία 1 προς 1:
Τα συνηθισμένα φώτα κυκλοφορίας δεν έχουν ανιχνευτές αυτοκινήτων, κι έτσι δεν μπορούν να προσαρμοστούν στις πραγματικές συνθήκες κυκλοφορίας --απλώς αναβοσβήνουν περιοδικά το κόκκινο και το πράσινο με συγκεκριμένη διάρκεια γιά τον κάθε δρόμο. Στην απλούστερη περίπτωση, στο παραπάνω παράδειγμα, το πράσινο θα ανάβει εναλλάξ στους δύο δρόμους, γιά διάστημα ενός κύκλου ρολογιού --δηλαδή επαρκές γιά ένα αυτοκίνητο-- κάθε φορά. Το κύκλωμα ελέγχου σε αυτή την περίπτωση θα είναι η απλούστατη FSM τύπου μετρητή με 2 καταστάσεις που φαίνεται στο σχήμα. Η FSM αυτή δεν έχει εισόδους, και οι μεταβάσεις καταστάσεων γίνονται πάντα με τον ίδιο τρόπο, χωρίς συνθήκη· γιά το λόγο αυτό, στα βέλη σημειώνουμε "1" (πάντα αληθές), δηλαδή η αντίστοιχη μετάβαση γίνεται πάντα. Προφανώς, η FSM αυτή εναλλάσει συνεχώς κατάσταση μεταξύ της "Ago" (πράσινο στον A) και της "Bgo" (πράσινο στον B). Το απλούστατο αυτό κύκλωμα ελέγχου έχει μιά σειρά από μειονεκτήματα:

• Περιττές καθυστερήσεις υπό ελαφρύ φορτίο: λέμε ότι το σύστημα λειτουργεί υπό ελαφρύ φορτίο όταν περνάνε πολύ λίγα αυτοκίνητα, "αραιά και πού". Υπ' αυτές τις συνθήκες, όταν ένα αυτοκίνητο φτάνει στη διασταύρωση, συνήθως δεν θα υπάρχει αυτοκίνητο στον άλλο δρόμο, άρα θα μπορούσε να περάσει αμέσως. Παρ' όλα αυτά, το φανάρι με το κύκλωμα ελέγχου που μόλις σχεδιάσαμε μπορεί να τύχει να είναι κόκκινο (με πιθανότητα 50%), οπότε αυτό προκαλεί καθυστέρηση χωρίς λόγο.
• Έλλειψη δικαιοσύνης υπό βαρύ φορτίο: λέμε ότι το σύστημα λειτουργεί υπό βαρύ φορτίο όταν υπάρχει πολλή κίνηση, άρα σχηματίζεται ουρά πίσω από τα φανάρια, και στους δύο δρόμους. Υπ' αυτές τις συνθήκες, το κύκλωμα ελέγχου που μόλις σχεδιάσαμε αφήνει να περνούν τα αυτοκίνητα A και τα αυτοκίνητα B με αναλογία 1 προς 1· όμως, δεδομένου ότι ο A είναι κεντρικός δρόμος ενώ ο B είναι πάροδος, η αναλογιά αυτή δεν είναι δίκαια.
• Ανεπαρκής αξιοποίηση πόρων υπό ασύμμετρο φορτίο: λέμε ότι το σύστημα λειτουργεί υπό ασύμμετρο φορτίο όταν ο ένας δρόμος έχει πολλή κίνηση και ο άλλος λίγη. Υπ' αυτές τις συνθήκες, το κύκλωμα ελέγχου που μόλις σχεδιάσαμε αφήνει να περνά μόνο ένα αυτοκίνητο κάθε 2 χρόνους από τον βεβαρυμένο δρόμο, δηλαδή ρυθμός ροής μόνο 50 % της μέγιστης εφικτής παροχής, ακόμα και όταν στον άλλο δρόμο δεν υπάρχει κανένα αυτοκίνητο.

10.3.2   Κλασσικά φανάρια, χωρίς ανιχνευτές, με αναλογία 2 προς 1:
Την αδικία προς τον κεντρικό δρόμο υπό βαρύ φορτίο, λόγω αναλογίας 1:1 στη διάρκεια του πράσινου στους δύο δρόμους, μπορούμε να την διορθώσουμε προσθέτονας καταστάσεις στον παραπάνω μετρητή, όπως φαίνεται στο διάγραμμα καταστάσεων της νέας FSM, δίπλα. Εδώ, το πράσινο στον δρομο A ανάβει σε δύο από τις τρείς καταστάσεις, ενώ στον δρόμο B μόνο σε μία· έτσι, υπό βαρύ φορτίο, η αναλογία παροχής A:B είναι 2:1, και η μέγιστη παροχή A έχει αυξηθεί στα 2/3 ενώ η μέγιστη παροχή B έχει μειωθεί στο 1/3. Φυσικά, συνεχίζουν να υπάρχουν περιττές καθυστερήσεις υπό ελαφρύ φορτίο και ανεπαρκής αξιοποίηση υπό ασύμμετρο φορτίο --τώρα μάλιστα οι καθυστερήσεις στο δρόμο B έχουν αυξηθεί και η μέγιστη παροχή του έχει μειωθεί.

10.3.3   Συνδυαστικό κύκλωμα σταθερής προτεραιότητας (απλό "STOP"):
Οι περιττές καθυστερήσεις υπό ελαφρύ φορτίο και η ανεπαρκής αξιοποίηση υπό ασύμμετρο φορτίο είναι αδύνατον να διορθωθούν χωρίς ανιχνευτές αυτοκινήτων, διότι χωρίς αυτούς το κύκλωμα ελέγχου είναι "τυφλό": δεν έχει τρόπο να ξέρει τις πραγματικές συνθήκες κυκλοφορίας. Έστω τώρα ότι έχουμε τις εισόδους Ad και Bd από τους ανιχνευτές. Ας προσπαθήσουμε κατ' αρχήν να φτιάξουμε το κύκλωμα ελέγχου σαν σκέτο συνδυαστικό κύκλωμα, χωρίς μνήμη. Φυσικά, όταν υπάρχει αυτοκίνητο μόνο σε έναν από τους δύο δρόμους, πρέπει να το αφήνουμε να περνάει, τώρα που ξέρουμε τι γίνεται σε κάθε δρόμο την κάθε στιγμή. Το πρόβλημα είναι όταν Ad=1 και Bd=1, δηλαδή υπάρχουν αυτοκίνητα και στους δύο δρόμους. Αφού δεν θυμόμαστε τίποτα από το παρελθόν (συνδυαστικό κύκλωμα), και αφού ο δρόμος A είναι κεντρικός ενώ ο B είναι πάροδος, λογικό είναι να δώσουμε προτεραιότητα στον A, άρα: Ago = Ad, και Bgo = (Ad')·(Bd) --δηλαδή αν υπάρχει αυτοκίνητο στον A του ανάβουμε πράσινο και το αφήνουμε να περάσει, ενώ αν δεν υπάρχει αυτοκίνητο στον A και υπάρχει στον B τότε ανάβουμε πράσινο στον B. Σαν συνδυαστικό που είναι το κύκλωμα αυτό αποφασίζει χρησιμοποιώντας μόνο τα δεδομένα της στιγμής --χωρίς καμία γνώση από το παρελθόν-- άρα στην πράξη υλοποιείται χωρίς φανάρια, με μιά σκέτη πινακίδα "STOP" στο δευτερεύοντα δρόμο B.

Το κύκλωμα ελέγχου αυτό δεν εισάγει περιττές καθυστερήσεις υπό ελαφρύ φορτίο, διότι κάθε αυτοκίνητο περνάει αμέσως μόλις έρθει αν δεν υπάρχει αυτοκίνητο στον άλλο δρόμο (ελαφρύ φορτίο). Επίσης, υπό ασύμμετρο φορτίο, προσφέρει πλήρη αξιοποίηση πόρων: όποτε υπάρχει αυτοκίνητο σε κάποιο δρόμο εισόδου, περνάει κάποιο από αυτά στην έξοδο, άρα η έξοδος ποτέ δεν μένει ανεκμετάλλευτη τη στιγμή που υπάρχουν αυτοκίνητα που θέλουν να περάσουν. Όμως, το κύκλωμα αυτό πάσχει από μεγάλη έλλειψη δικαιοσύνης προς τα αυτοκίνητα B: μόνο όποτε και εάν δεν υπάρχει κανένα αυτοκίνητο A μπορεί να περάσει ένα αυτοκίνητο B. Η αδικία αυτή δεν αποκλείεται να φτάσει στην ακραία μορφή του λεγόμενου φαινόμενου "λιμοκτονίας" (starvation): εάν συνεχώς υπάρχουν αυτοκίνητα A, ένα αυτοκίνητο B δεν θα εξυπηρετηθεί ποτέ.

10.3.4   Προσαρμοστικός Έλεγχος (με αναλογία 1 προς 1):
Η αδικία της τελευταίας λύσης προέρχεται από την έλλειψη μνήμης στο κύκλωμα: όσο πολλά αυτοκίνητα A και να έχουν περάσει πρόσφατα, ο ελεγκτής δεν το ξέρει, κι έτσι αφήνει ακόμα ένα να περάσει. Η έλλειψη αυτή διορθώνεται με την απλή FSM που φαίνεται στο σχήμα δίπλα. Εδώ έχουμε 1 bit μνήμης (μόνο), μέσω του οποίου θυμόμαστε από ποιόν δρόμο ήλθε το τελευταίο αυτοκίνητο που πέρασε. Εάν το τελευταίο ήταν από τον A και τώρα υπάρχει αυτοκίνητο στον B, το αφήνουμε να περάσει· αντίθετα, αν το τελευταίο ήταν από τον B, τώρα δίνουμε προτεραιότητα στον A: προτεραιότητα θα έχει ο άλλος δρόμος από αυτόν που εξυπηρετήθηκε την τελευταία φορά. Φυσικά, εάν δεν υπάρχει αυτοκίνητο στο δρόμο με την προτεραιότητα, αφήνουμε να περάσει το αυτοκίνητο από τον άλλο δρόμο, εάν υπάρχει. Η επόμενη κατάσταση είναι ανάλογη με το ποιός τελικά πέρασε, ενώ αν δεν πέρασε κανείς (διότι δεν υπήρχε κανείς) η κατάσταση παραμένει αμετάβλητη. Πάνω στα βέλη του διαγράμματος καταστάσεων σημειώνουμε τη συνθήκη μετάβασης (μαύρο), αλλά και την έξοδο που πρέπει να ενεργοποιηθεί (μπλέ).

Ας δούμε τώρα πώς συνθέτουμε το κύκλωμα μιάς FSM από το διάγραμμα καταστάσεών της. Πρώτα πρέπει να αποφασίσουμε πόσα bits κατάστασης θα χρειαστούμε, και με ποιό συνδυασμό τιμών τους θα παραστήσουμε την κάθε κατάσταση του διαγράμματος. Φυσικά, υπάρχουν πολλές δυνατές επιλογές· η επιλογή μας δεν θα επηρεάσει την εξωτερική συμπεριφορά της FSM, αλλά είναι πολύ πιθανό να επηρεάσει την πολυπλοκότητα του κυκλώματος υλοποίησης --εδώ, πάντως, δεν υπάρχει εύκολος κανόνας γιά τον τρόπο που συμφέρει να γίνει η κωδικοποίηση των καταστάσεων. Στο παρόν παράδειγμά μας, οι καταστάσεις είναι δύο, άρα αρκεί ένα bit γιά την κωδικοποίησή τους· ας το ονομάσουμε S, και ας θεωρήσουμε ότι S=0 σημαίνει ότι "το τελευταίο ήταν A", ενώ S=1 σημαίνει ότι "το τελευταίο ήταν B". Εάν ονομάσουμε nS την επόμενη κατάσταση, τότε ο πίνακας αληθείας του συνδυαστικού κυκλώματος μέσα στην FSM είναι ο παρακάτω (αριστερά), από τον οποίον προκύπτουν οι έξοδοι του κυκλώματος σαν συναρτήσεις των εισόδων του (δεξιά):

  S   Ad   Bd   |  Ago  Bgo  nS
  0    0    0   |   0    0    0
  0    0    1   |   0    1    1       Ago = Ad · [ S + (S')·(Bd') ]
  0    1    0   |   1    0    0
  0    1    1   |   0    1    1       Bgo = Bd · [ S' + (S)·(Ad') ]
  1    0    0   |   0    0    1
  1    0    1   |   0    1    1       nS  =  S · Ad'  +  S' · Bd
  1    1    0   |   1    0    0
  1    1    1   |   1    0    0 

10.3.5   Προσαρμοστικός έλεγχος με αναλογία 2 προς 1:
Η τελευταία FSM διατηρεί όλες τις καλές ιδιότητες του προσαρμοστικού ελέγχου (adaptive control), δηλαδή του ελέγχου που παρακολουθεί το φορτίο του συστήματος και προσαρμόζεται σε αυτό: υπό ελαφρύ φορτίο ποτέ δεν προκαλεί περιττές καθυστερήσεις, και υπό ασύμμετρο φορτίο προσφέρει πλήρη χρήση πόρων. Επίσης, αίρει την κατάφορη αδικία στο δρόμο B, δίνοντάς του ισότιμη μεταχείριση με τον δρόμο A. Μένει τώρα να διορθώσουμε την αναλογία παροχής υπό βαρύ φορτίο από 1:1 σε κάτι ορθότερο, δεδομένου ότι η A είναι κύρια οδός και η B είναι πάροδος· αυτό μπορεί να επιτευχθεί με την τροποποιημένη FSM που φαίνεται δίπλα. Εδώ, ξεχωρίζουμε την περίπτωση (κατάσταση) όπου το ένα τελευταίο αυτοκίνητο ήταν A ενώ το προηγούμενό του ήταν B από την περίπτωση που και τα δύο τελευταία αυτοκίνητα ήταν A· στην πρώτη περίπτωση αφήνουμε να περάσει και δεύτερο A κατά προτεραιότητα, ενώ στη δεύτερη περίπτωση δίνουμε προτεραιότητα στο B. Υπό βαρύ φορτίο η FSM αυτή εξυπηρετεί τους δρόμους A και B με αναλογία 2:1, ενώ επίσης διατηρεί και όλα τα άλλα πλεονεκτήματα των δύο τελευταίων λύσεων, δηλαδή τελικά λύνει όλα τα παραπάνω μειονεκτήματα της λύσης της §10.3.1.

Άσκηση 10.4:   Σχεδίαση της FSM (5) γιά τη Διασταύρωση των Οδών

Παρατηρήστε ότι οι γραμμές του πίνακα με S1-S0 = 11 δεν καλύπτονται από το διάγραμμα καταστάσεων, δεδομένου ότι η 11 είναι αχρησιμοποίητη κατάσταση. Αρχικά, αφήστε τις εξόδους, στις γραμμές αυτές, σαν συνθήκες αδιαφορίας (§4.4), γιά να διευκολυνθεί η απλοποίηση των συναρτήσεων των εξόδων. Στη συνέχεια όμως, ελέγξτε ποιά σας προέκυψε σαν επόμενη κατάσταση μετά την 11 γιά τις διάφορες τιμές των εισόδων: το κύκλωμα πρέπει να εγκαταλείπει αυτή την "παράνομη" κατάσταση όσο πιό γρήγορα γίνεται, αν τύχει να βρεθεί εκεί όταν πρωτοανάβει η τροφοδοσία. Γιά να είστε εντελώς εντάξει, πρέπει και να σιγουρευτείτε και ότι δεν θα ανάψουν ποτέ και τα δύο πράσινα μαζί (Ago=Bgo=1), ακόμα και όταν το κύκλωμα βρεθεί στην "παράνομη" κατάσταση 11.

10.5   Κώδικες Μεταβλητού Μήκους: Κωδικοποίηση Huffman

Γιά παράδειγμα, θεωρήστε ότι θέλουμε να στέλνουμε μηνύματα αποτελούμενα από μακρές ακολουθίες τεσσάρων (4) συμβόλων, των A, B, C, και D --δηλαδή το αλφάβητό μας έχει αυτά τα 4 γράμματα/σύμβολα. Ξέρουμε ότι αυτά μπορούμε να τα παραστήσουμε μ' ένα κώδικα σταθερού μήκους 2 bits ανά σύμβολο: 00, 01, 10, και 11. Έστω τώρα ότι στα μηνύματά μας η συχνότητα με την οποία εμφανίζονται τα διάφορα σύμβολα δεν είναι η ίδια: υπάρχουν σύμβολα πολύ συχνά και άλλα πολύ σπάνια. Σ' αυτή την περίπτωση, ένας κώδικας μεταβλητού μήκους μπορεί να μεταδώσει τα μηνύματά μας με λιγότερα bits συνολικά και κατά μέσον όρο. Ας πούμε, στο παραπάνω παράδειγμα, ότι στα μηνύματά μας το 50 % των εμφανιζομένων συμβόλων είναι A, το 25 % είναι B, το 12.5 % είναι C, και το 12.5 % είναι D, και ας θεωρήσουμε τον κώδικα μεταβλητού μήκους:

A: 0,   B: 10,   C: 110,   D: 111.

Ο παραπάνω κώδικας έχει φτιαχτεί προσεκτικά ούτως ώστε να είναι εφικτή η κατ' ευθείαν αναγνώριση του κάθε σύμβολου αμέσως μόλις φτάσει το τελευταίο bit της κωδικοποιημένης μορφής του, χωρίς διφορούμενα και χωρίς την ανάγκη να περιμένουμε πρώτα να δούμε τα επόμενα bits του μηνύματος. Η ιδιότητα αυτή υπάρχει επειδή ο κώδικας κάθε βραχύτερου σύμβολου δεν αποτελεί πρόθεμα του κώδικα κανενός από τα μακρύτερα σύμβολα. Παρόμοια ιδιότητα έχουν και οι αριθμοί τηλεφώνου, όπου τα πρώτα ψηφία (πρόθεμα) καθορίζουν μονοσήμαντα το συνολικό μήκος και το είδος του αριθμού. Την ιδιότητα αυτή δεν θα την είχε π.χ. ο κώδικας A=0, B=1, C=10, D=11: με αυτόν τον κώδικα, το μήνυμα 110 μπορεί να σημαίνει είτε BC είτε DA. Παρόμοιο "διφορούμενο" (ambiguous) κώδικα είχε χρησιμοποιήσει και το Μαντείο των Δελφών στον περίφημο εκείνο χρησμό του "ίξεις αφίξεις ουκ εν τω πολέμω θνήξεις", που μπορούσε να ερμηνευτεί είτε σαν "ίξεις, αφίξεις, ουκ εν τω πολέμω θνήξεις" (θα πας, θα γυρίσεις, δεν θα πεθάνεις στον πόλεμο), είτε σαν "ίξεις, αφίξεις ουκ, εν τω πολέμω θνήξεις" (θα πας, δεν θα γυρίσεις, στον πόλεμο θα πεθάνεις).

10.6   FSM Αποκωδικοποίησης Huffman:

Ο παραπάνω κώδικας μεταβλητού μήκους γιά τα 4 σύμβολα A, B, C, D αποκωδικοποιείται με την FSM που φαίνεται δεξιά. Υποθέτουμε ότι τα bits των κωδικοποιημένων συμβόλων έρχονται σειριακά, ένα-ένα, από μιάν είσοδο in, και ότι υπάρχει ένα ρολόϊ ck που σημαδεύει, με την ενεργή ακμή του, το τέλος του κάθε bit εισόδου in. Η FSM έχει 4 εξόδους, A, B, C, D· κάθε μιά τους ανάβει όποτε παραλαμβάνουμε ένα αντίστοιχο σύμβολο, γιά διάρκεια ακριβώς ενός κύκλου ρολογιού, και συγκεκριμένα κατά τον κύκλο ρολογιού παραλαβής του τελευταίου bit του αντίστοιχου συμβόλου.

Η κατάσταση εκκίνησης είναι η S0, οπότε και περιμένουμε να μας έλθει ένα νέο σύμβολο, με όλα του τα bits από την αρχή. Στην ίδια κατάσταση επιστρέφουμε κάθε φορά που τελειώνουν όλα τα bits του προηγούμενου σύμβολου, και επομένως περιμένουμε ένα νέο σύμβολο από την αρχή. Εάν είμαστε στην κατάσταση S0 και μας έλθει είσοδος 0 (in' αληθές), σημαίνει ότι βλέπουμε ένα σύμβολο A (το μοναδικό άρα και το τελευταίο του bit), επομένως πρέπει να ανάψει η έξοδος A και η επόμενη κατάσταση να είναι πάλι η S0, αφού στον επόμενο κύκλο περιμένουμε το πρώτο bit του επομένου συμβόλου. Εάν τώρα είμαστε στην S0 και έλθει είσοδος 1 (in αληθές), τότε ξέρουμε ότι βλέπουμε το πρώτο bit ενός συμβόλου B ή C ή D, αλλά δεν ξέρουμε ακόμα τίνος από τα τρία· έτσι, μεταβαίνουμε στην κατάσταση S1 που σημαίνει ότι έχουμε δεί μέχρι στιγμής ένα "1". Τον επόμενο κύκλο, όντας στην S1, αν δούμε είσοδο 0 σημαίνει ότι βλέπουμε το τέλος ενός συμβόλου B, άρα ανάβουμε την έξοδο B και μεταβαίνουμε στην S0. Αν αντιθέτως δούμε είσοδο 1 σημαίνει ότι βλέπουμε το δεύτερο bit ενός συμβόλου C ή D, αλλά δεν ξέρουμε ακόμα τίνος από τα δύο· έτσι, μεταβαίνουμε στην κατάσταση S2. Τον επόμενο κύκλο, όντας στην S2, είσοδος 0 σημαίνει ότι βλέπουμε το τέλος ενός συμβόλου C, ενώ είσοδος 1 υποδεικνύει το τέλος ενός συμβόλου D.

10.7   Κωδικοποίηση Καταστάσεων One-Hot:

A = (S0)·(in'),  B=(S1)·(in'),  C=(S2)·(in'),  D=(S2)·(in)

nS1 = (S0)·(in)·(reset'),  nS2 = (S1)·(in)·(reset'),
nS0 = (S0)·(in') + (S1)·(in') + (S2) + (reset) = in' + S2 + reset

Πείραμα 10.8:   Huffman FSM

Γιά να παρακολουθείτε την παρούσα κατάσταση της FSM, καθώς και την υπο προετοιμασία επόμενη κατάσταση, χρησιμοποιήστε αντίστοιχα τις 3 αριστερές και τις 3 δεξιές LED, όπως δείχνει στο σχήμα. Γιά να βλέπετε τις τέσσερεις εξόδους της FSM, χρησιμοποιήστε αντίστοιχα τα 4 ψηφία της οθόνης LCD (αρκεί π.χ. το LS bit κάθε ψηφίου, δηλαδή ένα κάθε 4 bits της καλωδιοταινίας). Παρατηρήστε ότι τα σήματα εξόδου της FSM παίρνουν τη σωστή τους τιμή μόνο αφού η είσοδος in πάρει τη δική της σωστή τιμή, μετά την προηγούμενη ακμή (πάτημα) ρολογιού και πριν την επόμενη: η σωστή τιμή εισόδων και εξόδων είναι αμέσως πριν την ακμή (πάτημα) ρολογιού, τότε δηλαδή που τα ακμοπυροδότητα flip-flops "κοιτάζουν" τις εισόδους τους.

Πριν φτάσετε στο εργαστήριο, κάντε ένα πλήρες σχεδιάγραμμα συνδεσμολογίας. Επίσης, γράψτε στο χαρτί σας την κωδικοποίηση του μηνύματος "ABACADACABADACAC" σύμφωνα με τον κώδικά μας μεταβλητού μήκους. Επίσης, αποκωδικοποιήστε το μήνυμα που περιέχουν τα bits "1001001110111011001100" σύμφωνα πάντα με τον ίδιο κώδικα. Στο εργαστήριο, κατασκευάστε το κύκλωμα, αρχικοποιήστε το σωστά (reset=1 και in=0 και ακμή ρολογιού), και στη συνέχεια ελέγξτε τη σωστή λειτουργία του στέλνοντάς του τα δύο παραπάνω μηνύματα και βλέποντας αν τα λαμβάνει σωστά, δηλαδή αν ανάβει η σωστή LED μία φορά γιά κάθε γράμμα-σύμβολο.