Browse Prior Art Database

Compressed Translator

IP.com Disclosure Number: IPCOM000075543D
Original Publication Date: 1971-Oct-01
Included in the Prior Art Database: 2005-Feb-24
Document File: 3 page(s) / 56K

Publishing Venue

IBM

Related People

Gurski, CS: AUTHOR [+2]

Abstract

This method provides an efficient way (utilizing a functional memory) to implement a very common translator requirement in which the number of input variables is very large, while the number of input combinations utilized for outputs is small. Fig. 1 depicts a typical associative or functional memory 1 having third "don't-care" states. The basic elements are an I/O Register 2, Mask Register 3, Array 4, and Match Register 5.

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 53% of the total text.

Page 1 of 3

Compressed Translator

This method provides an efficient way (utilizing a functional memory) to implement a very common translator requirement in which the number of input variables is very large, while the number of input combinations utilized for outputs is small. Fig. 1 depicts a typical associative or functional memory 1 having third "don't-care" states. The basic elements are an I/O Register 2, Mask Register 3, Array 4, and Match Register 5.

The type of problem solved by this method occurs often; notable examples are in implementing pattern recognition and memory hierarchy directories. Straightforward implementation in associative or functional memories is often impossible, since the length of the input vectors may be larger than the width of the memory array. Fig. 2 depicts a conventional implementation of a 190-input, 6-output translator in an associative memory requiring a 196-bit wide associative memory.

The improved solution utilizes the NEXT operation and certain "flags" to be described. Because of the Memory width restrictions, each valid input combination, C, must be partitioned into parts, Cj, such that: 1) C = (C1 : C2 : .... : Cn) where : is the concatenate symbol. 2) The length of each part, Cj, is less than the width of the available memory.

The partitions along with the output vector (likewise partitioned if necessary) are stored sequentially in the Array. In order to search the Memory, the input vectors, V, must be correspondingly partitioned into subvectors, Vj. The resulting search arguments are presented sequentially to the Memory. Then, a given imposed input vector, V, matches a stored input combination, C, if and only if Cj = Vj for all valid j, where = means compares in the associative or functional memory sense. The match must be resolved only when all of the partitions have matched.

This is accomplished as follows:

The input combinations and the output vectors are stored sequentially. The first partition of each stored input combination is flagged f1. The last input partition is flagged f2. A temporary flag, f3, is provided. 1) The first input partition along with flag f1 is presented as the first search argument. Each first word, C1, which matches the first subvector, V1, is selected. 2) The Next function is performed. This moves each select to the following word. 3) The flag f3 is written in each now-selected word. 4) If the subsequent partition is not the last partition, then it and flag f3 are utilized as the search argument, and the procedure returns to step 2. 5) If the partition is the last one, that...