# Circuit for Conditional Substring Function

Original Publication Date: 1976-Feb-01

Included in the Prior Art Database: 2005-Mar-02

## Publishing Venue

IBM

## Related People

## Abstract

It can readily be seen that an ordered set of elements (information) may be represented by a binary string which consists of the concatenation of fixed-length substrings, where each substring carries distinct information. Thus, for example, a binary string can be used to represent a stack or list or vector of information.

**This text was extracted from a PDF file.**

**At least one non-text object (such as an image or picture) has been suppressed.**

**This is the abbreviated version, containing approximately 52% of the total text.**

__Page 1 of 6__**Circuit for Conditional Substring Function **

It can readily be seen that an ordered set of elements (information) may be represented by a binary string which consists of the concatenation of fixed-length substrings, where each substring carries distinct information. Thus, for example, a binary string can be used to represent a stack or list or vector of information.

The described circuitry determines which substring of a string satisfies a given condition. The circuitry is flexible enough to be implemented by using modules, so that totally sequential processing up to totally parallel processing can be achieved. The circuitry may be used, for example, to detect page fault or available least recently used (LRU) page(s) in Virtual Memory.

Let n be the number of fixed-length substrings in a string, and let m be the length (in bits) of a substring. Then the string, denoted by B, consists of mn bits, and it is represented by: B = B/m/(0) B/m/(1) ..... B/m/(s) ..... B/m/(n-1)

where; B/m/(s) = b/0/(s) b/1/(s) ... b/i/(s) ... b/m-1/(s) for 0 </- s </- n - 1. B/m/(s) is the s-th substring of the string B.

The function of the circuitry which will be discussed below is the following. Find the subscript s in B such that B/m/(s) = D, where D is the given condition. This can be described as: Do s=0 to n-1;

If B/m/(s) = D, then z <-- s and go to FOUND; (1)

End;

FOUND: Stop;.

To increase the parallelism in processing, let r = n/p, where p is the degree of parallelism, then: Do s=0 to r-1;

(Image Omitted)

p is an integer and a divisor of n. If p=1 then (2) is totally sequential processing, and if p=n then (2) is totally parallel processing. If 1<p<n then it is the mixture of sequential processing and parallel processing.

DESCRIPTION OF THE CIRCUITS. Sequential Processing.

Fig. 1 shows the circuit which performs the operation described in the formula

(1) or p=1 in the formula (2). The circuit consists of three subcircuits, each of
which are named Select-Substring circuit (SSC), Matching circuit (MC), and
Response circuit (RC). S denotes the counter (or index) which will start from s=0
and will be incremented by 1 up to s=n-1 by CONTROL. For each s=i, the
Select-Substring circuit outputs B/m/(i), i.e., C/m/ <-- B/m/(i).

Then the Matching circuit checks whether B/m/(i) = D or not. If yes, then r=1, otherwise r=0. When r=1, then the Response circuit outputs s(=i), i.e., z <-- s. If

1

__Page 2 of 6__r=0, then CONTROL sets s <-- s + 1 (i.e., s <-- i+1) and the above operation will be repeated.

Since the Response circuit is a collection of m AND gates, the circuits for Select-Substring and Matching are shown.

In Fig. 2, a Select-Substring circuit for n=4 and m=2 is illustrated. The following shows the truth table of this circuit.

(Image Omitted)

Because of the difficulty of showing an exact Select-Substring circuit for arbitrary large n and m, the simplified notation which is illustrated in Fig. 3 is developed to illustrate a Select-Substring circuit for any v...