ANML Documentation

Simple Automata Using Boolean Elements

This section provides examples of simple automaton networks built with boolean elements.

Inverter Operation

Basic operation of the inverter element:

<state-transition-element id="u1" symbol-set="b" start="start-of-data"> <activate-on-match element="i1"/> </state-transition-element> <inverter id="i1"> <activate-on-high element="f"/> </inverter> <state-transition-element id="f" symbol-set="#"> <report-on-match/> </state-transition-element>
Figure 1. Inverter Element (AP Workbench)
Boolean sample inverter

In this example, STE u1 is only active on the very first symbol cycle. On this cycle, if a b is seen in the input data stream, u1 will drive an activation signal to the inverter, and the inverter will therefore not drive an activation signal to STE f. STE f will be inactive on the second symbol cycle.

If the first symbol in the input data stream is not a b, STE u1 will not drive an activation signal to the inverter, and therefore, the inverter will drive an activation signal to STE f. STE f will be active during the second symbol cycle.

On all subsequent symbol cycles, STE u1 is inactive, and therefore, is not driving an activation signal to the inverter. The inverter drives an activation signal to STE f, and STE f is active on all subsequent symbol cycles.

On the very first symbol cycle f is inactive; the activation from the inverter u1 does not cause it be activated until the second symbol cycle.

Note: Boolean elements do not drive out signals until the end of the first symbol cycle. Therefore, in this example, STE f is inactive on the very first symbol cycle; the activation from the inverter u1 (if any) does not cause STE f to be activated until the second symbol cycle.

Table 1. Inverter Behavior
Symbol Cycle Input Actions
Input stream: b#2#
0 b
  1. u1 is active; f is inactive
  2. u1 matches the b input symbol
  3. u1 drives an activation signal to i1
  4. i1 inverts the activation signal and does NOT drive an activation signal to f
1 #
  1. u1 is inactive; f is inactive
  2. Neither STE responds to the input symbol
  3. u1 does not drive an activation signal to i1
  4. i1 inverts the not-active signal and drives an activation signal to f
2 2
  1. u1 is inactive; f is active
  2. f does not match the input symbol (2)
  3. u1 does not drive an activation signal to i1
  4. i1 inverts the not-active signal and drives an activation signal to f
3 #
  1. u1 is inactive; f is active
  2. f matches the input symbol (#); f generates a report event
  3. u1 does not drive an activation signal to i1
  4. i1 inverts the not-active signal and drives an activation signal to f
Input stream: a#
0 a
  1. u1 is active; f is inactive
  2. u1 does not match the input symbol (a)
  3. u1 does not drive an activation signal to i1
  4. i1 inverts the non-activate signal and drives an activation signal to f
1 #
  1. u1 is inactive;' f is active
  2. f matches the input symbol (#); f generates a report event
  3. u1 does not drive an activation signal to i1
  4. i1 inverts the not-active signal and drives an activation signal to f
Input stream: b##
0 b
  1. u1 is active
  2. b causes u1 match
  3. i1 inverts to not activate f on next cycle
  4. f is inactive
1 #
  1. u1 is inactive
  2. i1 inverts to activate f on next cycle
  3. f is inactive
  4. no report
2 #
  1. u1 is inactive
  2. i1 inverts to activate f on next cycle
  3. f is active
  4. # causes f match
  5. f reports
Input stream: a##
0 a
  1. u1 is active
  2. a is not a match u1
  3. i1 inverts to activate f on next cycle
  4. f is inactive
1 #
  1. u1 is inactive
  2. i1 inverts to activate f on next cycle
  3. f is active
  4. # causes f match
  5. f reports
2 #
  1. u1 is inactive
  2. i1 inverts to activate f on next cycle
  3. f is active
  4. # causes f match
  5. f reports
Input stream: baba#
0 b
  1. u1 is active
  2. b causes u1 match
  3. i1 inverts to not activate f on next cycle
  4. f is inactive
1 a
  1. u1 is inactive
  2. i1 inverts to activate f on next cycle
  3. f is inactive
  4. no report
2 b
  1. u1 is active
  2. i1 inverts to activate f on next cycle
  3. f is active
  4. b is not a match for f
  5. no report
3 a
  1. u1 is active
  2. i1 inverts to activate f on next cycle
  3. f is active
  4. a is not a match for f
  5. no report
4 #
  1. u1 is inactive
  2. i1 inverts to activate f on next cycle
  3. f is active
  4. # causes f match
  5. f reports

OR, AND, NAND, NOR Operation

The basic operation of OR, AND, NAND, and NOR elements is illustrated below with automata that implement each of these boolean element types with two input STEs and one output reporting STE.

The input STEs recognize the symbols a and b. The symbols arrive serially, one after the other, so the automata each have two sequences of two STEs: the upper, which recognizes the a followed by a wildcard to propogate the result of the a STE into the second cycle, and the lower which recognizes the b, preceded by a wildcard STE to delay recognition of the b until the second cycle.

The second upper and lower STEs activate the boolean elements, which will compute the boolean results and either activate or not activate the final STEs which, if activated, report on seeing the termination symbol #.

<state-transition-element id="l1" symbol-set="*" start="start-of-data"> <activate-on-match element="u2"/> </state-transition-element> <state-transition-element id="l2" symbol-set="b"> <activate-on-match element="a1"/> </state-transition-element> <state-transition-element id="u1" symbol-set="a" start="start-of-data"> <activate-on-match element="l2"/> </state-transition-element> <state-transition-element id="u2" symbol-set="*"> <activate-on-match element="a1"/> </state-transition-element> <or id="o1"> <activate-on-high element="f1"/> </or> <and id="a1"> <activate-on-high element="f2"/> </and> <nor id="no1"> <activate-on-high element="f3"/> </nor> <nand id="na1"> <activate-on-high element="f4"/> </nand> <state-transition-element id="f1" symbol-set="#"> <report-on-match/> </state-transition-element> <state-transition-element id="f2" symbol-set="#"> <report-on-match/> </state-transition-element> <state-transition-element id="f3" symbol-set="#"> <report-on-match/> </state-transition-element>
Figure 2. OR, AND, NOR, NAND Elements (AP Workbench)
Boolean sample and or nand nor

Table 2. OR, AND, NOR, NAND Behavior
Input f reports
OR AND NOR NAND
Cycle Cycle Cycle Cycle
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
a     Y       Y         Y       Y
!ab##     Y                 Y     Y Y
a!b##     Y                 Y     Y Y
!a!b##                     Y Y     Y Y

The OR element is not necessary in the first example because all elements have an implicit OR. The activation of u1 and l1 in the example could have gone straight to the STE f and would produce the same output as the automaton with the OR boolean element.

SOP, POS, NSOP, NPOS Operation

The basic operation of SOP, POS, NSOP, and NPOS elements is illustrated below where a single activation connection has been made from six STEs to each of an SOP, POS, NSOP, and NPOS element.

Each of these boolean elements has three input terminals, with two activations going to each terminal. An activation signal goes from the boolean element to STE f which reports if it is activated by the boolean element and sees a termination symbol #.

<state-transition-element id="i1" symbol-set="[DEKR]" start="start-of-data"> <activate-on-match element="sop:t1"/> <activate-on-match element="nsop:t1"/> <activate-on-match element="pos:t1"/> <activate-on-match element="npos:t1"/> </state-transition-element> <state-transition-element id="i2" symbol-set="[KRST]" start="start-of-data"> <activate-on-match element="sop:t1"/> <activate-on-match element="nsop:t1"/> <activate-on-match element="pos:t1"/> <activate-on-match element="npos:t1"/> </state-transition-element> <state-transition-element id="j1" symbol-set="[KRFWY]" start="start-of-data"> <activate-on-match element="sop:t2"/> <activate-on-match element="nsop:t2"/> <activate-on-match element="pos:t2"/> <activate-on-match element="npos:t2"/> </state-transition-element> <state-transition-element id="j2" symbol-set="[RWGP]" start="start-of-data"> <activate-on-match element="sop:t2"/> <activate-on-match element="nsop:t2"/> <activate-on-match element="pos:t2"/> <activate-on-match element="npos:t2"/> </state-transition-element> <state-transition-element id="k1" symbol-set="[DK]" start="start-of-data"> <activate-on-match element="sop:t3"/> <activate-on-match element="nsop:t3"/> <activate-on-match element="pos:t3"/> <activate-on-match element="npos:t3"/> </state-transition-element> <state-transition-element id="k2" symbol-set="K" start="start-of-data"> <activate-on-match element="sop:t3"/> <activate-on-match element="nsop:t3"/> <activate-on-match element="pos:t3"/> <activate-on-match element="npos:t3"/> </state-transition-element> <sum-of-products id="sop"> <activate-on-high element="f1"/> </sum-of-products> <nsum-of-products id="nsop"> <activate-on-high element="f2"/> </nsum-of-products> <product-of-sums id="pos"> <activate-on-high element="f3"/> </product-of-sums> <nproduct-of-sums id="npos"> <activate-on-high element="f4"/> </nproduct-of-sums> <state-transition-element id="f1" symbol-set="#"> <report-on-match/> </state-transition-element> <state-transition-element id="f2" symbol-set="#"> <report-on-match/> </state-transition-element> <state-transition-element id="f3" symbol-set="#"> <report-on-match/> </state-transition-element> <state-transition-element id="f4" symbol-set="#"> <report-on-match/> </state-transition-element
Figure 3. SOP, POS, NSOP, NPOS Elements (AP Workbench)
Boolean pos sop

Similar to the other boolean elements, SOP, POS, NSOP, and NPOS have an ID attribute; however, unlike the other elements, they have multiple terminals which must be selected when activating the element. Activations are therefore made directly to the term ID and not to the element. Like other ANML IDs, the IDs must be unique in the current namescope.

The table below shows the result of inputting different symbol values followed by the termination symbol # to illustrate the operation of each of different types of combinatorial elements discussed in this section.

Table 3. SOP, POS, NSOP, NPOS Behavior
  Input Stream
  D# Y# K# R# L# S# W#
i1[DEKR] 1   1 1      
i2[KRST]     1 1   1  
j1[KRFWY]   1 1 1     1
j2[RWGP]       1     1
k1[DK] 1   1        
k1[K] 1   1        
               
SOP     Y Y     Y
POS     Y        
NSOP Y Y     Y Y  
NPOS Y Y   Y Y Y Y

As was the case with the inverter and NAND and NOR elements, the NSOP and NPOS elements will activate f on any symbol cycle following the second cycle, as the inactive input STEs drive a low input on a term connection causing a high output by the logic of the element. See the Inverter Element section for more information on this behavior.

End of Data Operation

EOD operation is illustrated below. The AND element is enabled for EOD, is reporting, and also activates an STE (which is also reporting). The starting STEs have been set to all-input so that the effect of asserting EOD several times in an input stream can be seen.

<state-transition-element id="l1" symbol-set="*" start="all-input"> <activate-on-match element="u2"/> </state-transition-element> <state-transition-element id="l2" symbol-set="b"> <activate-on-match element="a1"/> </state-transition-element> <state-transition-element id="u1" symbol-set="a" start="all-input"> <activate-on-match element="l2"/> </state-transition-element> <state-transition-element id="u2" symbol-set="*"> <activate-on-match element="a1"/> </state-transition-element> <and id="a1"> <report-on-high/> <activate-on-high element="f"/> </and> <state-transition-element id="f" symbol-set="#"> <report-on-match/> </state-transition-element>
Figure 4. EOD with Boolean Element (AP Workbench)
Boolean eod

Table 4. EOD Behavior
Cycle 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Symbol # # a b # # a b # # a b # # a b # # a b # # x y #
EOD asserted?               Y                               Y  
a1 reports?               Y                                  
f reports?                 Y                                

The boolean element a1 only reports and activates f at cycle 8 when EOD has been asserted; all other sequences of a b do not cause reporting or activation. EOD is enabled at cycle 24; however, because the input does not generate a high value, it has no effect and a1 does not report or activate f.

Enabling EOD on NAND, NOR, NPOS, and NSOP elements prevents them from generating a high value in the absence of activation inputs when EOD is not asserted.

Boolean Element Reporting

A reporting boolean element is illustrated below by modifying AND in the previous example. In this example, it was reported by adding an extra symbol cycle with a termination symbol, with using the AND to activate a final reporting STE. The additional cycle and the STE can be eliminated simply by making the AND element one that reports.

<state-transition-element id="l1" symbol-set="*" start="start-of-data"> <activate-on-match element="u2"/> </state-transition-element> <state-transition-element id="l2" symbol-set="b"> <activate-on-match element="a1"/> </state-transition-element> <state-transition-element id="u1" symbol-set="a" start="start-of-data"> <activate-on-match element="l2"/> </state-transition-element> <state-transition-element id="u2" symbol-set="*"> <activate-on-match element="a1"/> </state-transition-element> <and id="a1"> <report-on-high/> </and>
Figure 5. Boolean Element Reporting (AP Workbench)
Boolean and or nand nor reporting

The SOP, POS, NSOP, and NPOS elements have an element ID in addition to IDs associated with each terminal. Activations are made to the terminal ID, not to the element ID; however, when reporting the output is associated with the element ID.