The boolean (also known as combinatorial) elements enable the creation of logical constructs in an automaton network by combining activation values using bitwise boolean operations such as OR and AND.
Boolean elements do not receive or respond to input symbols in the input stream; instead, they are driven by STEs or counter elements. Boolean elements evaluate their logic functions instantaneously (in the same clock cycle within which they are driven).
In an actual hardware implementation, a finite amount of time is required for electrical signals to propagate through a boolean element. For this reason, cascaded boolean elements may have an effect on the speed at which an automata network operates. The most conservative approach is to never connect the output of one boolean element to the input of another boolean element; however, this approach is not practical for all network automata designs.
Activation signals that are actively driven by other network elements (for example, an activate-on-match signal from an STE) are treated as logic 1. Activation signals that are not actively driven are treated as logic 0.
ANML supports three types of boolean elements:
- Inverter (single input terminal accepting a single activation signal; also referred to as a single-tier gate)
- OR, AND, NAND, NOR (single input terminals accepting multiple activation signals; also referred to as single-tier gates)
- SOP, POS, NSOP, NPOS (multiple input terminals accepting multiple activation signals; also referred to as dual-tiered gates)
The boolean elements share a common structure of required and optional attributes, outputs, and input terminals:
The inverter, OR, AND, NAND, and NOR elements have a single, unnamed input terminal. The SOP, POS, NSOP, and NPOS elements have three named input terminals.
An inverter element inverts an activation signal. It inverts non-activation into activation even when the input STE is not testing input symbols against its symbol set.
ANML syntax does not prohibit multiple activations to an inverter; however, ANML tools and compilers may reject such a construct or convert the inverter to a NOR or have other or undefined behavior.
OR, AND, NAND, NOR Elements
The OR, AND, NAND, and NOR elements combine activation values, producing a high event when the boolean value computed by the element is equivalent to 1.
There is no limit in ANML to the number of activations that may be combined, although the implementation will likely have a limit. These elements also work on single input activation; however, the function they perform will be logically equivalent to either a pass-through gate or an inverter.
SOP, POS, NSOP, NPOS Elements
The sum-of-product (SOP), product-of-sums (POS), nsum-of-products (NSOP), and nproduct-of-sums (NPOS) are boolean elements with multiple input terminals.
An SOP is the sum (OR) of product (AND) terms. A POS is the product (AND) of sum (OR) terms. An NSOP is an SOP with its activation value inverted. An NPOS is POS with its activation value inverted.
The number of terms supported in this type of boolean element is specific to the implementation, as is the number of activations that can be input into each term.
These boolean elements can be used to implement SOP and POS expressions and, more generally, be useful in the implementation of complex logical operations involving the two-level combination of several separate boolean terms.
It may be helpful to visualize POS and SOP in their representation as combinations of OR and AND gates as shown below. In the image, three terms are shown for each element, and each term is shown as having two inputs. However, in actuality, the number of terms and activation input to each term is an implementation dependency.
Similar to the other boolean elements, SOP, POS, NSOP, and NPOS have an ID element; 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 ID attribute is a user-defined unique identifier (name) for the boolean element. The ID attribute must start with a character, but can then contain other characters, digits, or underscore symbols.
End of data (EOD) is a signal delivered in conjunction with the input data stream. The EOD signal configures boolean elements to be active only at specific points in the processing of input. The EOD signal is typically not asserted. At times, EOD can be set to true. A boolean element is configured to respond to EOD by setting the high-only-on-eod attribute to true.
If a boolean element is configured with EOD, it can only generate outputs on symbol cycles where the EOD signal is asserted.
EOD implementation must support a mechanism by which the designer may request that EOD is asserted, zero or more times, at specific symbol cycles. This feature may have implementation-specific limitations, such as requiring the EOD be associated with chunks of data in allocated buffers or the EOD is asserted only on at intervals of a multiple of a specific length. If a foundational element is configured with EOD, it can only activate other elements and report on symbol cycles where EOD is asserted.
Similar to STEs and counter elements, boolean elements can be configured to report on an event.
Up to one report-on-high element may be associated with a boolean element, while zero or more activate-on-high elements may be specified.
The boolean event is a high value, specified in ANML with the report-on-high subelement. A boolean element configured to report a high event will report on each symbol cycle in which its value is high.
In ANML coding, the report-on-high element must precede any activate-on-high elements.
An input terminal is the connection point where other network elements connect to the boolean element.
The single-tier gates (inverter, AND, OR, NAND, NOR) all have a single, unnamed input terminal. Any number of other network elements may connect an activation signal to this terminal, and the gate will perform its logic function on these signals.
In the current implementation, the dual-tier gates (SOP, POS, NSOP, NPOS) contain three different input terminals. Multiple network elements may connect to any of these input terminals, and the dual-tiered logic function of the gate will operate on these signals as specified. Examples of this behavior will be shown later in this chapter.