ANML Documentation

Counter Automata Networks

Counting Occurrences

The automaton in the following example uses a counter to recognize four bs in an input stream (the bs do not need to be in a consecutive sequence).

A counter does not examine the input symbols and does not match patterns; therefore, it must be used in conjunction with STEs. The first STE, a1, must recognize a b and cause the counter to count, and the final STE, a2, generates output.

<state-transition-element id="a1" symbol-set="b" start="all-input"> <activate-on-match-automaton="c1"/> </state-transition-element> <counter countone="c1" reset="r1" target="3" at_target="latch"> <activate-on-target element="a2"/> </counter> <state-transition-element id="a2" symbol-set="b"> <report-on-match/> </state-transition-element>
Figure 1. Counting Occurrences (AP Workbench)
Counter latch mode

The counter receives input from the elements connected to it, modifies its internal state, and has its output latched all within the same cycle used by the input STEs to evaluate the input against its symbol set. It may be helpful to think of a counter and all the STEs that input to it as a single device.

The operation of this automaton is provided in detail, cycle-per-cycle, in the table below. The input stream is bbbb. STE a1 is always activated, as indicated with the all-input start attribute.

Table 1. Counting Automata Network Behavior
Symbol Cycle Input Symbol Actions
Input stream: bbbb
1 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
2 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
3 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target, driving an activation signal to a2.
4 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count remains at target (no reset).
  4. a2 is reactivated because of c1 latch setting.
  5. c1 drives an activation signal to a2, causing output.

This example could also be constructed using STEs only. Given the low target value, an STE-only implementation would probably be a better use of resources on a semiconductor implementation. However, the equivalent STE-only design is more complicated. The figures below demonstrate a design that implements this example with STEs only: one follows very simple automaton (Figure 2) and one does not (Figure 3).

Figure 2. Sample ANML Counting Automata Network (Not Following Simple Automata)
Counter four consecutive b incorrect

Figure 3. Sample ANML Counting Automata Network (Following Simple Automata)
Counter four b not b latch

Figure 3 illustrates the operation of the example counter machine on a input stream with a mixture of bs and non-bs. This is another example of the original automaton, this time with input bxxbbbxb:

Figure 4. Sample Counting Automata Network
Counter latch mode

Table 2. Sample Counting Automata Network Behavior
Symbol Cycle Input Symbol Actions
Input stream: bxxbbbxb
1 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
2 x  
3 x  
4 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
5 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target, driving an activation signal to a2.
6 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count remains at target (no reset).
  4. a2 is reactivated because of c1 latch setting.
  5. c1 drives an activation signal to a2, causing output.
7 x
  1. c1 count remains at target (no reset).
  2. a2 is reactivated because of c1 latch setting.
8 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count remains at target (no reset).
  4. a2 is reactivated because of c1 latch setting.
  5. c1 drives an activation signal to a2, causing output.

Counter Reporting

The following is a simple automaton for a report that is generated on every 1024th input symbol. The report is associated with the counter countone id c1.

<state-transition-element id="a1" symbol-set="*" start="all-input"> <activate-on-match-element="c1"/> </state-transition-element> <counter countone="c1" reset="r1" target="1024" at_target="rollover"> <report-on-target/> </counter>
Figure 5. Counter Report (AP Workbench)
Counter count 1024 report

Counter Operating Modes

Latch Mode

In the example below, the following stream of input symbols is submitted against each STE:

bxxbbbxbbbbb

The automaton generates a match report from STE a2 on receipt of the fourth, fifth, sixth, seventh, eighth, and ninth b.

<state-transition-element id="a1" symbol-set="b" start="all-input"> <activate-on-match-element="c1"/> </state-transition-element> <counter countone="c1" reset="r1" target="3" at_target="latch"> <activate-on-target element="a2"/> </counter> <state-transition-element id="a2" symbol-set="b"> <report-on-match/> </state-transition-element>
Figure 6. Counter Latch Mode (AP Workbench)
Counter latch mode

Table 3. Cycle-by-Cycle Analysis: Counter Latch Mode
Symbol Cycle Input Symbol Actions
1 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
2 x  
3 x  
4 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
5 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target, driving an activation signal to a2.
6 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count remains at target (no reset).
  4. a2 is activated because of the latch setting.
7 x
  1. c1 count remains at target (no reset).
  2. a2 is activated because of the latch setting.
8 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. a2 causing output c1 count remains at target (no reset).
  4. a2 is activated because of the latch setting.
9 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. a2 causing output c1 count remains at target (no reset).
  4. a2 is activated because of the latch setting.
10 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. a2 causing output c1 count remains at target (no reset).
  4. a2 is activated because of the latch setting.
11 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. a2 causing output c1 count remains at target (no reset).
  4. a2 is activated because of the latch setting.
12 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. a2 causing output c1 count remains at target (no reset).
  4. a2 is activated because of the latch setting.

The figure below demonstrates a design that implements this example with STEs only.

Figure 7. STE-Only Equivalent: Counter Latch Mode (AP Workbench)
Counter four b not b latch

Pulse Mode

In the following example, the automaton generates a match report only on the fourth b, essentially shutting off after the first time the counter activates STE a2.

This automaton must use the start-of-data attribute instead of the all-input attribute because it will not recognize subsequent sequences after the counter reaches the target the first time, and additional input should not be propagated through the automaton after that occurs.

An STE with a [ˆb] character class with a start-of-data attribute must also be added to enable the automaton to work in the case where the first symbol is not b. This automaton is only language-equivalent instead of simply equivalent to the version using a counter because, in the counter version, the first STE is continually activated because of the all-input start while in the STE-only version, the STE (which recognizes the first b) can only be activated once. The two automata do, however, generate output on the same set of input sequences.

Input stream:

bxxbbbxbbbbb

<state-transition-element id="a1" symbol-set="b" start="all-input"> <activate-on-match-element="c1"/> </state-transition-element> <counter countone="c1" reset="r1" target="3" at_target="pulse"> <activate-on-target element="a2"/> </counter> <state-transition-element id="a2" symbol-set="b"> <report-on-match/> </state-transition-element>
Figure 8. Counter Pulse Mode (AP Workbench)
Counter pulse mode

Table 4. Cycle-by-Cycle Analysis: Pulse Mode
Cycle Input Symbol Actions
1 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
2 x  
3 x  
4 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
5 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target, driving an activation signal to a2.
6 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. a2 causing output c1 count remains at target (no reset).
  4. a2 is not activated because of the pulse setting.
7 x
  1. c1 count remains at target (no reset).
  2. a2 is not activated because of the pulse setting.
8 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count remains at target (no reset).
  4. No output from a2 because it was not activated.
9 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count remains at target (no reset).
  4. No output from a2 because it was not activated.
10 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count remains at target (no reset).
  4. No output from a2 because it was not activated.
11 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count remains at target (no reset).
  4. No output from a2 because it was not activated.
12 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count remains at target (no reset).
  4. No output from a2 because it was not activated.

The figure below demonstrates a design that implements this example with STEs only.

Figure 9. STE-Only Equivalent: Counter Pulse Mode
Counter pulse mode ste only

Roll Mode

In the following example, the automaton generates a match report from STE a2 on receipt of the fourth b and seventh b in the symbol cycle.

Four bs are needed to generate the first match report; however, only three are needed for the second report because the fourth b is both the last of the first sequence and the first of next sequence.

Similar to the pulse counter example, this automaton must use the start-of-data attribute instead of the all-input attribute to avoid having bs cascade into STE a2 after the first pass through the counter. However, because of the roll mode, the automaton should restart the count sequence after the first b is seen after the count reset.

An STE with a [ˆb] character class with the start-of-data attribute must also be added to enable the automaton to work in the case where the first symbol is not b. This automaton is language-equivalent only instead of simply equivalent to the version using a counter because in the counter version, the first STE is continually activated because of the all-input start. In the STE-only version, the STE that recognizes the first b can be activated only once. The two automata do, however, generate output on the same set of input sequences.

Input stream:

bxxbbbxbbbbb

<state-transition-element id="a1" symbol-set="b" start="all-input"> <activate-on-match-element="c1"/> </state-transition-element> <counter countone="c1" reset="r1" target="3" at_target="roll"> <activate-on-target element="a2"/> <state-transition-element id="a2" symbol-set="b"> <report-on-match/> </state-transition-element>
Figure 10. Counter Roll Mode (AP Workbench)
Counter roll mode

Table 5. Cycle-by-Cycle Analysis: Roll Mode
Cycle Input Symbol Actions
1 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
2 x  
3 x  
4 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
5 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target, driving an activation signal to a2.
  4. c1 count resets.
6 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target.
  4. a2 is not activated because of the roll mode.
  5. a2 causes output.
7 x  
8 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target.
  4. No output from a2 because it was not activated.
9 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target, driving an activation signal to a2.
  4. C1 count resets.
10 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target.
  4. a2 is not activated because of the roll mode.
  5. a2 causes output.
11 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
12 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target, driving an activation signal to a2.
  4. c1 count resets.

The figure below demonstrates a design that implements this example with STEs only.

Figure 11. STE-Only Equivalent: Roll Mode
Counter roll mode ste only

Reset and Counting in Sequence

In a previous example, an automaton was constructed to count four bs but allowed non-b symbols to be interspersed between bs.

The example below shows an automaton that counts only sequences of four consecutive bs using the counter reset.

STE a2 examines each input symbol and resets the counter if a symbol which is not a b is seen. Reset causes the counter value to be restored to the initial value, restarting the count. The equivalent STE-only implementation follows.

Input stream:

bbbbbxbbbbxb

<state-transition-element id="a1" symbol-set="b" start="all-input"> <activate-on-match element="c1"/> </state-transition-element> <state-transition-element id="a2" symbol-set="[^b]" start="all-input"> <activate-on-match element="r1"/> </state-transition-element> <counter countone="c1" reset="r1" target="3" at_target="latch"> <activate-on-target element="a3"/> </counter> <state-transition-element id="a3" symbol-set="b"> <report-on-match/> </state-transition-element>
Figure 12. Reset and Counting in Sequence (AP Workbench)
Counter four consecutive b

Table 6. Cycle-by-Cycle Analysis: Reset and Counting in Sequence
Cycle Input Symbol Actions
1 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
2 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
3 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target, driving an activation signal to a3.
  4. c1 count resets.
4 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. a3 causes output c1 count remains at target (no reset).
  4. a3 is activated.
5 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. a3 causes output c1 count remains at target (no reset).
  4. a3 is activated.
6 x
  1. a2 matches the x input symbol, driving an activation signal to r1.
  2. c1 count resets.
  3. a3 is deactivated.
7 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
8 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances.
9 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. c1 count advances to target, driving an activation signal to a3.
  4. c1 count remains at target (no reset).
10 b
  1. a1 is active.
  2. a1 matches the b input symbol, driving an activation signal to c1.
  3. a3 matches the b input symbol, causing output.
  4. c1 count remains at target (no reset).
  5. a3 is active.
11 x
  1. a2 matches the x input symbol, driving an activation signal to r1.
  2. c1 count resets.
  3. a3 is deactivated.
12 b
  1. a1 matches the b input symbol, driving an activation signal to c1.
  2. c1 count advances.

The figure below demonstrates a design that implements this example with STEs only.

Figure 13. STE-Only Equivalent: Reset and Counting Sequence
Counter four b