Calculating Hamming Distance


Hamming distance is a measure of the difference between two strings of symbols. It is the number of changes that would need to be made to one of the strings to convert it into the other string. For example, the hamming distance between mice and nice is one, because only a single character change needs to be applied to one of the strings to convert it into the other string.

This automaton accepts a string of symbols. The ! symbol starts the automaton. After the ! symbol is seen, the automaton computes the hamming distance of the next five symbols with the word cable. The comparison is case-sensitive. After five symbols are received, the automaton expects to receive four more # symbols, which are used as part of the reporting process.

If the hamming distance between the word cable and the five symbols is zero, the counter generates a report on the fifth symbol. If the hamming distance is one, the report generates on the first # symbol. If the hamming distance is two, the report generates on the second # symbol, and so on. The automaton does not generate a report for a hamming distance of five (that is, when five symbols and the word cable have zero characters in common).


AP Workbench

Hamming distance

C Code

#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, cable_cnt, c, a, b, l, e;
    ap_anml_element_ref_t p1, p2, p3, p4, p5, p6, p7, p8, p9;

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

    // Build the network = "cable_cnt";
    element.res_type = RT_COUNTER;
    element.cnt_mode = COUNT_STOP0_PULSE; = 5;
    element.match = 1;
    AP_AddAnmlElement(anml_net, &cable_cnt, &element); = "start";
    element.res_type = RT_STE;
    element.start = ALL_INPUT;
    element.symbols = "!";
    element.match = 0;
    AP_AddAnmlElement(anml_net, &start, &element);

    element.match = 0;
    element.symbols = "*"; = "p1";
    AP_AddAnmlElement(anml_net, &p1, &element); = "p2";
    AP_AddAnmlElement(anml_net, &p2, &element); = "p3";
    AP_AddAnmlElement(anml_net, &p3, &element); = "p4";
    AP_AddAnmlElement(anml_net, &p4, &element); = "p5";
    AP_AddAnmlElement(anml_net, &p5, &element);

    element.symbols = "#"; = "p6";
    AP_AddAnmlElement(anml_net, &p6, &element); = "p7";
    AP_AddAnmlElement(anml_net, &p7, &element); = "p8";
    AP_AddAnmlElement(anml_net, &p8, &element); = "p9";
    AP_AddAnmlElement(anml_net, &p9, &element); = "c";
    element.symbols = "c";
    AP_AddAnmlElement(anml_net, &c, &element); = "a";
    element.symbols = "a";
    AP_AddAnmlElement(anml_net, &a, &element); = "b";
    element.symbols = "b";
    AP_AddAnmlElement(anml_net, &b, &element); = "l";
    element.symbols = "l";
    AP_AddAnmlElement(anml_net, &l, &element); = "e";
    element.symbols = "e";
    AP_AddAnmlElement(anml_net, &e, &element);

    AP_AddAnmlEdge(anml_net, start, cable_cnt, RESET_PORT);
    AP_AddAnmlEdge(anml_net, start, p1, 0);
    AP_AddAnmlEdge(anml_net, start, c, 0);

    AP_AddAnmlEdge(anml_net, p1, p2, 0);
    AP_AddAnmlEdge(anml_net, p2, p3, 0);
    AP_AddAnmlEdge(anml_net, p3, p4, 0);
    AP_AddAnmlEdge(anml_net, p4, p5, 0);
    AP_AddAnmlEdge(anml_net, p5, p6, 0);
    AP_AddAnmlEdge(anml_net, p6, p7, 0);
    AP_AddAnmlEdge(anml_net, p7, p8, 0);
    AP_AddAnmlEdge(anml_net, p8, p9, 0);

    AP_AddAnmlEdge(anml_net, p1, a, 0);
    AP_AddAnmlEdge(anml_net, p2, b, 0);
    AP_AddAnmlEdge(anml_net, p3, l, 0);
    AP_AddAnmlEdge(anml_net, p4, e, 0);

    AP_AddAnmlEdge(anml_net, c, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, a, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, b, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, l, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, e, cable_cnt, COUNT_ONE_PORT);

    AP_AddAnmlEdge(anml_net, p6, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p7, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p8, cable_cnt, COUNT_ONE_PORT);
    AP_AddAnmlEdge(anml_net, p9, cable_cnt, COUNT_ONE_PORT);

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

    // Clean up 
    return 0;

Python Code

from micronap.sdk import *

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

    # Build the network
    start = AN.AddSTE('!', startType=AnmlDefs.ALL_INPUT, anmlId='start')
    cable_cnt = AN.AddCounter(5, mode=CounterMode.STOP_PULSE, match=True, anmlId='cable_cnt')

    p1 = AN.AddSTE('*', anmlId='p1')
    p2 = AN.AddSTE('*', anmlId='p2')
    p3 = AN.AddSTE('*', anmlId='p3')
    p4 = AN.AddSTE('*', anmlId='p4')
    p5 = AN.AddSTE('*', anmlId='p5')

    c = AN.AddSTE('c', anmlId='c')
    a = AN.AddSTE('a', anmlId='a')
    b = AN.AddSTE('b', anmlId='b')
    l = AN.AddSTE('l', anmlId='l')
    e = AN.AddSTE('e', anmlId='e')

    p6 = AN.AddSTE('#', anmlId='p6')
    p7 = AN.AddSTE('#', anmlId='p7')
    p8 = AN.AddSTE('#', anmlId='p8')
    p9 = AN.AddSTE('#', anmlId='p9')

    AN.AddAnmlEdge(start, cable_cnt, AnmlDefs.RESET_PORT)
    AN.AddAnmlEdge(start, p1, 0)
    AN.AddAnmlEdge(start, c, 0)

    AN.AddAnmlEdge(p1, p2, 0)
    AN.AddAnmlEdge(p2, p3, 0)
    AN.AddAnmlEdge(p3, p4, 0)
    AN.AddAnmlEdge(p4, p5, 0)
    AN.AddAnmlEdge(p5, p6, 0)
    AN.AddAnmlEdge(p6, p7, 0)
    AN.AddAnmlEdge(p7, p8, 0)
    AN.AddAnmlEdge(p8, p9, 0)

    AN.AddAnmlEdge(p1, a, 0)
    AN.AddAnmlEdge(p2, b, 0)
    AN.AddAnmlEdge(p3, l, 0)
    AN.AddAnmlEdge(p4, e, 0)

    AN.AddAnmlEdge(c, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(a, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(b, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(l, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(e, cable_cnt, AnmlDefs.COUNT_ONE_PORT)

    AN.AddAnmlEdge(p6, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p7, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p8, cable_cnt, AnmlDefs.COUNT_ONE_PORT)
    AN.AddAnmlEdge(p9, cable_cnt, AnmlDefs.COUNT_ONE_PORT)

    # Export the network to an ANML file

if __name__ == '__main__':


In this automaton, STE start is always active and looking for the ! symbol. When this symbol is seen, STE p1 and STE 11 are both activated. STEs p1–p5 are designed to look for the target symbols cable, each one incrementing the counter when a target symbol matches.

STEs p1–p4 each match on any symbol, and therefore, will be activated in sequence regardless of the input symbol. These STEs are used to ensure that the symbols able are checked in sequence with the second, third, fourth, and fifth input symbols.

Each symbol that matches the five input symbols will cause the corresponding STE (11–15) to activate, thus causing the counter to increment. If all five symbols match, the counter will have incremented to its target count of five by the time the fifth character is seen in the input data stream.

If less than five symbols have matched, the counter will be at a number lower than five. According to the automaton design specification, four # symbols should now be presented to the automaton. STEs p6–p9 will match these # symbols, each one causing the counter to increment. These # symbols each compensate for one of the mismatched symbols between the five input symbols and the symbols in the word cable. The counter will generate a report when it reaches a count of five, which will be earlier for words with lower hamming distance to cable and later for words with higher hamming distance to cable. The symbol cycle in which the counter reports indicates the exact hamming distance.