Cookbook

Finding an Ordered Sequence of a Fixed Size

Application

This automaton finds an ordered sequence of a fixed size.

For example, in a scenario with a fixed sequence of eight symbols consisting of a, b, and c, the automaton would search for a string of eight symbols that must start with a and end with c. Between these two symbols any number of a, b, and c symbols are allowed, as long as all c symbols are preceded by at least one, possibly more, b symbols, and all b symbols are preceded by at least one, possibly more, a symbols.

Stated as a regular expression, this automaton would search for the following string that is exactly eight characters long:

/a+b+c+/

Two designs can be used to construct this automaton in ANML: one that uses STEs only (c_finding_ordered_sequence_of_size_n.html#concept_83D854328C0848F5BDAE5D24F72A91CF__fig_0A786F188769464CA27DB9753D7DAC49) and another that uses STEs in conjunction with counter and boolean elements (c_finding_ordered_sequence_of_size_n.html#concept_83D854328C0848F5BDAE5D24F72A91CF__fig_222B7EBD7BDB46D59100208332792FDE).

Construction

AP Workbench: STEs Only


Finding ordered sequence size n ste only

AP Workbench: STEs with Counter and Boolean Elements


Finding ordered sequence size n ste counter boolean

C Code: STEs Only

#include <micron/ap/ap_defs.h>
#include <micron/ap/ap_anml.h>

int main(int argc, char* argv[]) {
    ap_anml_t anml = NULL;
    ap_anml_network_t anml_net;
    struct ap_anml_element element = {0};
    ap_anml_element_ref_t start, a2, a3, a4, a5, a6;
    ap_anml_element_ref_t b2, b3, b4, b5, b6, b7;
    ap_anml_element_ref_t c3, c4, c5, c6, c7, c8;

    // Initialize the automata network
    anml = AP_CreateAnml();
    AP_CreateAutomataNetwork(anml, &anml_net, "find_ordered_sequence_fixed_size_ste");

    // Build the network
    element.id = "start";
    element.res_type = RT_STE;
    element.start = ALL_INPUT;
    element.symbols = "a";
    AP_AddAnmlElement(anml_net, &start, &element);

    element.start = NO_START;
    element.id = "a2";
    AP_AddAnmlElement(anml_net, &a2, &element);
    element.id = "a3";
    AP_AddAnmlElement(anml_net, &a3, &element);
    element.id = "a4";
    AP_AddAnmlElement(anml_net, &a4, &element);
    element.id = "a5";
    AP_AddAnmlElement(anml_net, &a5, &element);
    element.id = "a6";
    AP_AddAnmlElement(anml_net, &a6, &element);

    element.symbols = "b";
    element.id = "b2";
    AP_AddAnmlElement(anml_net, &b2, &element);
    element.id = "b3";
    AP_AddAnmlElement(anml_net, &b3, &element);
    element.id = "b4";
    AP_AddAnmlElement(anml_net, &b4, &element);
    element.id = "b5";
    AP_AddAnmlElement(anml_net, &b5, &element);
    element.id = "b6";
    AP_AddAnmlElement(anml_net, &b6, &element);
    element.id = "b7";
    AP_AddAnmlElement(anml_net, &b7, &element);

    element.symbols = "c";
    element.id = "c3";
    AP_AddAnmlElement(anml_net, &c3, &element);
    element.id = "c4";
    AP_AddAnmlElement(anml_net, &c4, &element);
    element.id = "c5";
    AP_AddAnmlElement(anml_net, &c5, &element);
    element.id = "c6";
    AP_AddAnmlElement(anml_net, &c6, &element);
    element.id = "c7";
    AP_AddAnmlElement(anml_net, &c7, &element);
    element.id = "c8";
    element.match = 1;
    AP_AddAnmlElement(anml_net, &c8, &element);

    AP_AddAnmlEdge(anml_net, start, a2, 0);
    AP_AddAnmlEdge(anml_net, start, b2, 0);

    AP_AddAnmlEdge(anml_net, a2, a3, 0);
    AP_AddAnmlEdge(anml_net, a2, b3, 0);
    AP_AddAnmlEdge(anml_net, a3, a4, 0);
    AP_AddAnmlEdge(anml_net, a3, b4, 0);
    AP_AddAnmlEdge(anml_net, a4, a5, 0);
    AP_AddAnmlEdge(anml_net, a4, b5, 0);
    AP_AddAnmlEdge(anml_net, a5, a6, 0);
    AP_AddAnmlEdge(anml_net, a5, b6, 0);
    AP_AddAnmlEdge(anml_net, a6, b7, 0);

    AP_AddAnmlEdge(anml_net, b2, b3, 0);
    AP_AddAnmlEdge(anml_net, b2, c3, 0);
    AP_AddAnmlEdge(anml_net, b3, b4, 0);
    AP_AddAnmlEdge(anml_net, b3, c4, 0);
    AP_AddAnmlEdge(anml_net, b4, b5, 0);
    AP_AddAnmlEdge(anml_net, b4, c5, 0);
    AP_AddAnmlEdge(anml_net, b5, b6, 0);
    AP_AddAnmlEdge(anml_net, b5, c6, 0);
    AP_AddAnmlEdge(anml_net, b6, b7, 0);
    AP_AddAnmlEdge(anml_net, b6, c7, 0);
    AP_AddAnmlEdge(anml_net, b7, c8, 0);

    AP_AddAnmlEdge(anml_net, c3, c4, 0);
    AP_AddAnmlEdge(anml_net, c4, c5, 0);
    AP_AddAnmlEdge(anml_net, c5, c6, 0);
    AP_AddAnmlEdge(anml_net, c6, c7, 0);
    AP_AddAnmlEdge(anml_net, c7, c8, 0);

    // Export the network to an ANML file
    AP_ExportAnml(anml_net, "find_ordered_sequence_fixed_size_ste.anml", "");

    // Clean up 
    AP_DestroyAnml(anml);
    return 0;
}

C Code: STEs with Counter and Boolean Elements

#include <micron/ap/ap_defs.h>
#include <micron/ap/ap_anml.h>

int main(int argc, char* argv[]) {
    ap_anml_t anml = NULL;
    ap_anml_network_t anml_net;
    struct ap_anml_element element = {0};
    ap_anml_element_ref_t fna, fa, a, b, c, nab, nbc, nc, counter, lc, and_gate;

    // Initialize the automata network
    anml = AP_CreateAnml();
    AP_CreateAutomataNetwork(anml, &anml_net, "find_ordered_sequence_fixed_size_ste_counter_boolean");

    // Build the network
    element.id = "fna";
    element.res_type = RT_STE;
    element.start = ALL_INPUT;
    element.symbols = "[^a]";
    AP_AddAnmlElement(anml_net, &fna, &element);

    element.id = "fa";
    element.start = START_OF_DATA;
    element.symbols = "a";
    AP_AddAnmlElement(anml_net, &fa, &element);

    element.start = NO_START;
    element.id = "a";
    element.symbols = "a";
    AP_AddAnmlElement(anml_net, &a, &element);
    element.id = "b";
    element.symbols = "b";
    AP_AddAnmlElement(anml_net, &b, &element);
    element.id = "c";
    element.symbols = "c";
    AP_AddAnmlElement(anml_net, &c, &element);

    element.id = "nab";
    element.symbols = "[^ab]";
    AP_AddAnmlElement(anml_net, &nab, &element);
    element.id = "nbc";
    element.symbols = "[^bc]";
    AP_AddAnmlElement(anml_net, &nbc, &element);
    element.id = "nc";
    element.symbols = "[^c]";
    AP_AddAnmlElement(anml_net, &nc, &element);

    element.id = "lc";
    element.symbols = "c";
    AP_AddAnmlElement(anml_net, &lc, &element);

    element.id = "Counter";
    element.res_type = RT_COUNTER;
    element.cnt_mode = COUNT_STOP0_PULSE;
    element.target = 6;
    AP_AddAnmlElement(anml_net, &counter, &element);

    element.id = "and";
    element.res_type = RT_BOOLEAN;
    element.bool_mode = BOOL_AND;
    element.terminals = 1;
    element.match = 1;
    AP_AddAnmlElement(anml_net, &and_gate, &element);

    AP_AddAnmlEdge(anml_net, fna, fa, 0);
    AP_AddAnmlEdge(anml_net, fa, a, 0);
    AP_AddAnmlEdge(anml_net, fa, b, 0);
    AP_AddAnmlEdge(anml_net, fa, nab, 0);
    AP_AddAnmlEdge(anml_net, a, a, 0);
    AP_AddAnmlEdge(anml_net, a, b, 0);
    AP_AddAnmlEdge(anml_net, a, nab, 0);
    AP_AddAnmlEdge(anml_net, a, counter, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, b, b, 0);
    AP_AddAnmlEdge(anml_net, b, c, 0);
    AP_AddAnmlEdge(anml_net, b, nbc, 0);
    AP_AddAnmlEdge(anml_net, b, counter, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, c, c, 0);
    AP_AddAnmlEdge(anml_net, c, and_gate, 0);
    AP_AddAnmlEdge(anml_net, c, nc, 0);
    AP_AddAnmlEdge(anml_net, c, counter, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, nab, counter, RESET_PORT);
    AP_AddAnmlEdge(anml_net, nbc, counter, RESET_PORT);
    AP_AddAnmlEdge(anml_net, nc, counter, RESET_PORT);
    AP_AddAnmlEdge(anml_net, counter, lc, 0);
    AP_AddAnmlEdge(anml_net, lc, and_gate, 0);

    // Export the network to an ANML file
    AP_ExportAnml(anml_net, "find_ordered_sequence_fixed_size_ste_counter_boolean.anml", "");

    // Clean up 
    AP_DestroyAnml(anml);
    return 0;
}

Python Code: STEs Only

from micronap.sdk import *

def main():
    # Initialize the automata network
    A = Anml()
    AN = A.CreateAutomataNetwork(anmlId='find_ordered_sequence_fixed_size_ste')

    # Build the network
    start = AN.AddSTE('a', startType=AnmlDefs.ALL_INPUT, anmlId='start')

    a2 = AN.AddSTE('a', anmlId='a2')
    a3 = AN.AddSTE('a', anmlId='a3')
    a4 = AN.AddSTE('a', anmlId='a4')
    a5 = AN.AddSTE('a', anmlId='a5')
    a6 = AN.AddSTE('a', anmlId='a6')

    b2 = AN.AddSTE('b', anmlId='b2')
    b3 = AN.AddSTE('b', anmlId='b3')
    b4 = AN.AddSTE('b', anmlId='b4')
    b5 = AN.AddSTE('b', anmlId='b5')
    b6 = AN.AddSTE('b', anmlId='b6')
    b7 = AN.AddSTE('b', anmlId='b7')

    c3 = AN.AddSTE('c', anmlId='c3')
    c4 = AN.AddSTE('c', anmlId='c4')
    c5 = AN.AddSTE('c', anmlId='c5')
    c6 = AN.AddSTE('c', anmlId='c6')
    c7 = AN.AddSTE('c', anmlId='c7')
    c8 = AN.AddSTE('c', match=True, anmlId='c8')

    AN.AddAnmlEdge(start, a2, 0)
    AN.AddAnmlEdge(start, b2, 0)

    AN.AddAnmlEdge(a2, a3, 0)
    AN.AddAnmlEdge(a2, b3, 0)
    AN.AddAnmlEdge(a3, a4, 0)
    AN.AddAnmlEdge(a3, b4, 0)
    AN.AddAnmlEdge(a4, a5, 0)
    AN.AddAnmlEdge(a4, b5, 0)
    AN.AddAnmlEdge(a5, a6, 0)
    AN.AddAnmlEdge(a5, b6, 0)
    AN.AddAnmlEdge(a6, b7, 0)

    AN.AddAnmlEdge(b2, b3, 0)
    AN.AddAnmlEdge(b2, c3, 0)
    AN.AddAnmlEdge(b3, b4, 0)
    AN.AddAnmlEdge(b3, c4, 0)
    AN.AddAnmlEdge(b4, b5, 0)
    AN.AddAnmlEdge(b4, c5, 0)
    AN.AddAnmlEdge(b5, b6, 0)
    AN.AddAnmlEdge(b5, c6, 0)
    AN.AddAnmlEdge(b6, b7, 0)
    AN.AddAnmlEdge(b6, c7, 0)
    AN.AddAnmlEdge(b7, c8, 0)

    AN.AddAnmlEdge(c3, c4, 0)
    AN.AddAnmlEdge(c4, c5, 0)
    AN.AddAnmlEdge(c5, c6, 0)
    AN.AddAnmlEdge(c6, c7, 0)
    AN.AddAnmlEdge(c7, c8, 0)

    # Export the network to an ANML file
    AN.ExportAnml('find_ordered_sequence_fixed_size_ste.anml')

if __name__ == '__main__':
    main()

Python Code: STEs with Counter and Boolean Elements

from micronap.sdk import *

if __name__ == '__main__':
    # Initialize the automata network
    anml = Anml()
    network = anml.CreateAutomataNetwork(anmlId='find_ordered_sequence_fixed_size_ste_counter_boolean')

    # Build the network
    fna = network.AddSTE('[^a]', startType=AnmlDefs.ALL_INPUT, anmlId='fna')
    fa = network.AddSTE('a', startType=AnmlDefs.START_OF_DATA, anmlId='fa')

    a = network.AddSTE('a', anmlId='a')
    b = network.AddSTE('b', anmlId='b')
    c = network.AddSTE('c', anmlId='c')
    nab = network.AddSTE('[^ab]', anmlId='nab')
    nbc = network.AddSTE('[^bc]', anmlId='nbc')
    nc = network.AddSTE('[^c]', anmlId='nc')

    counter = network.AddCounter(6, mode=CounterMode.STOP_PULSE, anmlId='Counter')
    lc = network.AddSTE('c', anmlId='lc')
    and_gate = network.AddBoolean(mode=BooleanMode.AND, match=True, anmlId='and')

    network.AddAnmlEdge(fna, fa, 0)
    network.AddAnmlEdge(fa, a, 0)
    network.AddAnmlEdge(fa, b, 0)
    network.AddAnmlEdge(fa, nab, 0)
    network.AddAnmlEdge(a, a, 0)
    network.AddAnmlEdge(a, b, 0)
    network.AddAnmlEdge(a, nab, 0)
    network.AddAnmlEdge(a, counter, AnmlDefs.COUNT_ONE_PORT)
    network.AddAnmlEdge(b, b, 0)
    network.AddAnmlEdge(b, c, 0)
    network.AddAnmlEdge(b, nbc, 0)
    network.AddAnmlEdge(b, counter, AnmlDefs.COUNT_ONE_PORT)
    network.AddAnmlEdge(c, c, 0)
    network.AddAnmlEdge(c, and_gate, 0)
    network.AddAnmlEdge(c, nc, 0)
    network.AddAnmlEdge(c, counter, AnmlDefs.COUNT_ONE_PORT)
    network.AddAnmlEdge(nab, counter, AnmlDefs.RESET_PORT)
    network.AddAnmlEdge(nbc, counter, AnmlDefs.RESET_PORT)
    network.AddAnmlEdge(nc, counter, AnmlDefs.RESET_PORT)
    network.AddAnmlEdge(counter, lc, 0)
    network.AddAnmlEdge(lc, and_gate, 0)

    # Export the network to an ANML file
    network.ExportAnml('find_ordered_sequence_fixed_size_ste_counter_boolean.anml')

Operation

STEs Only

In the first design, STE start is always searching for an a symbol. After the initial a is detected, STEs a2 and b2 are activated, with each STE allowing for a subsequent a or b, respectively.

If a second a is detected by STE a2, STEs a3 and b3 are activated, allowing for another a or b. This same pattern continues, with STE a3 activating STEs a4 and b4, and so on until STE a6, at which point the only option is to receive a b symbol via STE b7, and then a c symbol via STE c8.

At any point on the a path (or right after the initial a), a b symbol could transfer flow to the middle b track.

While on the b track, subsequent b symbols are allowed, as are c symbols. a symbols will further progress down this track, until STE a6 is reached. At this point, a b followed by a c must be detected for the pattern match to be successful.

In summary, input that matches this automaton must first contain an a symbol, it must end with a c symbol, and it must be eight characters in length. Between the two endpoints, an a can only be followed by either an a or b, and b can only be followed by either a b or c.

STEs, Counter, Boolean Elements

The second design is more intricate than the first; however, this design can help lower STE space by using counter and boolean elements to reduce the number of STEs by half. This can be helpful In designs with 10, 20, 30 or more consecutive symbols.

This automaton contains STEs labeled a, b, and c as well as nab, nbc, and nc.

STEs a, b, and c are analogous to STEs a, b, and c in the first design; they ensure that a symbols are only followed by either a or b, and b symbols are only followed by either b or c. A c symbol is only allowed to be followed by another c symbol. Each time a legitimate symbol is seen, the counter increments by 1.

If an a is followed by anything other than an a or a b, STE nab will match. Similarly, if a b is followed by anything other than a b or a c, STE nbc will match. And if a c is followed by anything other than a c, STE nc will match. All three of these STEs (nab, nbc, nc) drive into the reset node of the counter, so they essentially reset the automaton when a non-pattern-matching symbol is seen in the input data stream.

STE fa and STE lc ensure that the pattern must start with an a and end with a c. These two STEs, in conjunction with the other STEs that increment the counter up to six, guarantee that a total of eight symbols match.

STEs fna and fa both find the start of the pattern wherever it may exist in the input data stream. Both STEs are active on the very first symbol cycle, and STE fna keeps STE fa active as long as non-a symbols exist in the input data stream. After STE fa matches, it enables both STE a and STE b, which is the equivalent of STE start enabling STEs a2 and b2 in the first design.

The counter counts up to six, meaning it has seen one initial symbol followed by six more symbols that match the target pattern. At this point, the counter activates STE lc. If a final c symbol is seen, STE lc will drive a positive signal into the AND boolean (gate). This action is not enough to cause the automaton to report because it could be that seven sequential a symbols could have caused the automaton to arrive at this state, and it is not the design for seven a symbols followed by a single c symbol to generate a report event. Therefore, STE lc and STE c are connected to the AND gate. STE c is only active if it has been activated by the STE b, meaning an a symbol followed by b followed by c must occur in the input data stream.