# US 8,543,528 B2 · Exploitation of transition rule sharing based on short state tags to improve the storage efficiency

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 8,543,528 B2
- Document ID: US8543528B2
- Status: Granted
- Kind: B2
- Application number: 12/888,740
- Filed: 2010-09-23
- Published: 2012-03-29
- Granted: 2013-09-24
- Earliest claimed: 2010-09-23
- Assignees: International Business Machines Corporation
- Applicants: Jan van Lunteren
- Inventors: Jan van Lunteren
- Web page: https://patentgrep.com/patent/US8543528B2

## CPC

- G06N 5/02: Knowledge representation; Symbolic representation
- G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS

## Abstract

A mechanism is provided with an address generator that is operative to receive a current state vector and a current input value, and the address generator is operative to generate a memory address corresponding to a transition rule in response to the current state vector and the current input value. A transition rule memory includes a memory addresses, and the memory address is a location in the transition rule memory. The transition rule is a transition rule vector that includes a short state tag field. The short state tag field includes fewer bits than the current state vector.

## Claims

### Claim 1

An apparatus, comprising:
an address generator operative to receive a current state vector and a current input value, wherein the address generator is operative to generate a memory address corresponding to a transition rule in response to the current state vector and the current input value;
a transition rule memory comprising a plurality of memory addresses, wherein the memory address is a location in the transition rule memory; and
a rule selector;
wherein the transition rule is a transition rule vector comprising a short state tag field;
wherein the short state tag field comprises fewer bits than the current state vector;
wherein the rule selector is operative to ensure that the short state tag field is not an error by correlating the memory address to the short state tag field since the memory address is derived from the current state vector; and
wherein when the rule selector determines that there is no correlation between the memory address and the short state tag field, the rule selector is operative to recognize the error.

### Claim 2 (depends on 1)

The apparatus of claim 1, wherein the short state tag field comprises two bits.

### Claim 3 (depends on 1)

The apparatus of claim 1, wherein the short state tag field comprises three bits.

### Claim 4 (depends on 1)

The apparatus of claim 1, wherein the short state tag field is configured to identify a current state of the transition vector.

### Claim 5 (depends on 1)

The apparatus of claim 1, wherein the current state vector is configured to identify a current state of a state register.

### Claim 6 (depends on 1)

The apparatus of claim 1,
wherein the rule selector is operative to determine if a first current state of the current state vector matches a second current state of the short state tag field.

### Claim 7 (depends on 6)

The apparatus of claim 6, wherein the rule selector is operative to determine if the current input value matches a test input value of the transition rule vector.

### Claim 8 (depends on 7)

The apparatus of claim 7, wherein if the first current state of the current state vector matches the second current state of the short state tag field and if the current input value matches the test input value of the transition rule vector, the rule selector is operative to select the transition rule vector.

### Claim 9 (depends on 6)

The apparatus of claim 6, wherein the rule selector is operative to determine if the first current state of the current state vector matches the second current state of the short state tag field by checking the upper bits of the current state vector against the bits of the short state tag field; and
wherein when the upper bits match the bits of the short state tag field, the transition rule vector is selected.

### Claim 10 (depends on 1)

The apparatus of claim 1, wherein the short state tags are configured to designate an “any state” condition based on a value of the bits.

### Claim 11

An apparatus, comprising:
a transition rule memory comprising a plurality of memory addresses which are locations in the transition rule memory;
a pattern compiler operative to:
determine input values for states;
determine next states for the states;
for the states that have matching input values and matching next states, determine that the states have a shared rule; and
for the states that have the shared rule, store the share rule in the transition rule memory at a same memory address to be utilized by the states that have the shared rule;
wherein for the states that have the shared rule, the pattern compiler is operative to assign unique current state vectors each differing in three significant bits; and
wherein the pattern compiler is operative to assign mask vectors for the states that have the shared rule.

### Claim 12 (depends on 11)

The apparatus of claim 11, further comprising an address generator;
wherein the address generator is operative to generate the same memory address for the states that have the shared rule based on the mask vectors and the unique current state vectors.

### Claim 13 (depends on 11)

The apparatus of claim 11, wherein the three significant bits that differ for the unique current state vectors are provided as short tags that correspond to the shared rule.

### Claim 14 (depends on 11)

The apparatus of claim 11, wherein the states that have the shared rule comprise a first state and a second state;
for the first state and second state, the pattern compiler is operative to:
map the shared rule only once for the first and second states to reduce storage requirements in the transition rule memory;
place the first and second states having the shared rule at a beginning of a list for processing all states.

### Claim 15 (depends on 14)

The apparatus of claim 14, wherein the pattern compiler is operative to:
compile the first and second states together such that the first and second states are mapped as being a single state, with the shared rule of the first and second states only handled once; and
assign the first and second states the same hash function.

### Claim 16

A method for transition rule sharing, comprising:
receiving by an address generator a current state vector and a current input value,
generating a memory address corresponding to a transition rule in response to the current state vector and the current input value;
wherein the memory address is a location in the transition rule memory; and
wherein the transition rule is a transition rule vector comprising a short state tag field;
providing the short state tag field with fewer bits than the current state vector;
wherein a rule selector is operative to ensure that the short state tag field is not an error by correlating the memory address to the short state tag field since the memory address is derived from the current state vector; and
wherein when the rule selector determines that there is no correlation between the memory address and the short state tag field, the rule selector is operative to recognize the error.

### Claim 17

A method for transition rule sharing, comprising:
determining input values for states;
determining next states for the states;
for the states that have matching input values and matching next states, determining that the states have a shared rule;
for the states that have the shared rule, storing the share rule in a transition rule memory at a same memory address to be utilized by the states that have the shared rule;
wherein for the states that have the shared rule, the pattern compiler is operative to assign unique current state vectors each differing in three significant bits; and
wherein the pattern compiler is operative to assign mask vectors for the states that have the shared rule.