Browse Prior Art Database

Serial Logic for Generating Arbitrarily Weighted Bit Strings

IP.com Disclosure Number: IPCOM000105681D
Original Publication Date: 1993-Aug-01
Included in the Prior Art Database: 2005-Mar-20
Document File: 2 page(s) / 67K

Publishing Venue

IBM

Related People

Linsker, R: AUTHOR

Abstract

Disclosed is a method and apparatus for generating a set of random bit values each of which equals 1 with a specified probability P, where P is of the form m/2 sup K for arbitrary K ge 1 and 1 le m lt 2 sup K. Applications of the method include weighted random pattern test generation for fault determination.

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

Serial Logic for Generating Arbitrarily Weighted Bit Strings

      Disclosed is a method and apparatus for generating a set of
random bit values each of which equals 1 with a specified probability
P, where P is of the form m/2 sup K for arbitrary K ge 1 and 1 le m
lt 2 sup K.  Applications of the method include weighted random
pattern test generation for fault determination.

The method comprises the steps of:

1.  pre-determining a sequence of control bits (CON sub 1 , ..., CON
    sub K-1 ) as a given function of the values (p sub 1 , ..., p sub
    K ), and defining the integer L such that p sub L = 1 and p sub i
    = 0 for all L lt i le K;

2.  generating a set of unweighted independent pseudorandom bit
    values A sub 1 , ..., A sub K (i.e., each A sub i is equal to 1
    with probability 1/2);

3.  generating a first intermediate output bit B sub 1 that is equal
    to A sub 1;

4.  serially for each i=1, ..., K-1, providing B sub i and A sub i+1
    as inputs to an i'th Boolean-function unit that computes an
    intermediate output bit B sub i+1 as a selectable Boolean
    function of the two inputs, the selection being controlled by the
    value of the control bit CON sub i (this step is omitted if K=1);

5.  providing as the final output bit the L'th intermediate output
    bit value B sub L;

6.  repeating steps 2 through 5 for each final output bit desired.

(Note that for a single given P, it is efficient to choose K such
that p sub K = 1.  Then L=K and no unnecessary computations of B sub
i are wasted, as they would be if K gt L.  On the other hand, since
the same circuitry will in general be used for different specified
values of P at different times, the option of allowing K gt L is
provided here.)

      Apparatus that implements the method described above is shown
in the Figure.  The box at left provides independent unweighted
pseudorandom bit values A sub 1 , ..., A sub K.  A linear feedback
shift register (LFSR) may be used t...