Browse Prior Art Database

Method for Generating Constrained Subspaces in 0/1 Valued N Dimensional Space

IP.com Disclosure Number: IPCOM000089571D
Original Publication Date: 1977-Nov-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Goel, P: AUTHOR

Abstract

The problem to be solved can be stated as follows: Given an n-bit binary string of 0's, 1's, and X's (where X indicates that either a 1 or a 0 may be possible), provide an efficient method of sequentially generating all the n-bit binary numbers which may be generated by substituting either a 0 or 1 for each X in the original binary string. For example, given the 6-bit binary string 01X0X1, the required 6-bit numbers are obtained by using all possible combinations of 0's and 1's in the X positions of the string. The required numbers are 010001, 010011, 011001, and 011011.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 52% of the total text.

Page 1 of 2

Method for Generating Constrained Subspaces in 0/1 Valued N Dimensional Space

The problem to be solved can be stated as follows: Given an n-bit binary string of 0's, 1's, and X's (where X indicates that either a 1 or a 0 may be possible), provide an efficient method of sequentially generating all the n-bit binary numbers which may be generated by substituting either a 0 or 1 for each X in the original binary string. For example, given the 6-bit binary string 01X0X1, the required 6-bit numbers are obtained by using all possible combinations of 0's and 1's in the X positions of the string. The required numbers are 010001, 010011, 011001, and 011011.

The problem occurs in implementing search methods that are of the enumeration type.

A practical situation where the above problem is encountered is in test generation for stuck faults (in logic surrounding an embedded ROS (read-only storage) array) where there is a need to search the address space of a ROS array for an address (word) that contains a desired bit pattern (personalization). However, in general, the address space to be searched is not the entire 2/n/ addresses for the array with n address inputs. The address inputs can be at logic levels 0, 1, or X (where X indicates that the logic level is not yet known to be either a 1 or a 0). Those address inputs which are known to be either logic 0 or logic 1 are termed the fixed inputs. The remaining address inputs (i.e., those at
X) are termed the variable inputs.

The need then is to search the address space generated by allowing all possible combinations of 0's and 1's on the variable address inputs of the ROS. Thus, if m (m </= n) is the number of variable address inputs, a search of a subspace, consisting of 2/m/ words or addresses, would be needed. The 2/m/ addresses would have the same logic levels on the fixed inputs and have all possible combinations of 0's and 1's on the variable inputs. The requirement was to provide an efficient method that would sequentially generate the 2/m/ addresses one at a time on a demand basis. The demand for the next sequential address would continue until an address containing the desired bit pattern (personalization) was encountered.

The solution is obtained using...