Browse Prior Art Database

Adaptive Means for Generating Random Bit Vectors with Specified Inter-Bit Correlations

IP.com Disclosure Number: IPCOM000108772D
Original Publication Date: 1992-Jun-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 2 page(s) / 94K

Publishing Venue

IBM

Related People

Linsker, R: AUTHOR

Abstract

Disclosed is a method for generating an ensemble of random bit vectors that approximately satisfies specified desired statistical properties. These properties may include single-bit probabilities (the probability with which a bit in a given position is a '1'), pairwise probabilities (for bits in two given positions having the values '00', '01', etc.), and joint probabilities involving more than two bits. Applications include improved means for weighted random pattern test generation.

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

Adaptive Means for Generating Random Bit Vectors with Specified Inter-Bit Correlations

       Disclosed is a method for generating an ensemble of
random bit vectors that approximately satisfies specified desired
statistical properties.  These properties may include single-bit
probabilities (the probability with which a bit in a given position
is a '1'), pairwise probabilities (for bits in two given positions
having the values '00', '01', etc.), and joint probabilities
involving more than two bits. Applications include improved means for
weighted random pattern test generation.

      To generate each such bit vector B, a vector A of independent
pseudo-random values is generated.  A may be a bit vector or a
continuous-valued vector.  If A is a bit vector, a linear feedback
shift register may be used to generate A.  The vector A is processed
according to a specified function F that depends upon a set of
parameters W, to yield the output vector B.  [That is, B = F(A,W).]
The process is repeated for each new vector A, keeping W unchanged.

      The set of parameter values W are determined as follows.  an
objective function E(W,Q) is defined, in which Q denotes the set of
specified desired single- and multiple-bit probabilities.  The values
W are iteratively optimized so as to minimize the value of E(W,Q).
The functional form of E(W,Q) includes terms that penalize deviations
between (i) the actual single- and multiple-bit probabilities amongst
the vectors B = F(A,W) and (ii) the specified desired values Q of
these probabilities.

      In one embodiment of the invention, the vectors A are
continuous-valued, and are randomly drawn from a specified (e.g.,
Gaussian) distribution.  The components of A and B are denoted by
subscripts.  The function F computes Bk X STEP X(Siwk,iAi + wk,o),
where STEP(z) X 1 if z>0 and 0 otherwise.  This computation generates
the bit vector B.  Here, W is the set of weights {wk,i, wk,o}.

      In this illustrative embodiment, the objective function E(W,P)
is the sum of various terms, one term for each specified single- or
multiple-bit probability.  For example, suppose one of these
specified values is the desired joint probability for bits #2, 5, and
7 having values 1, 0, and 1, respectively.  ...