Browse Prior Art Database

Detection of a Leading Zero of a Leading Sequence of Zeros

IP.com Disclosure Number: IPCOM000099916D
Original Publication Date: 1990-Mar-01
Included in the Prior Art Database: 2005-Mar-15
Document File: 7 page(s) / 198K

Publishing Venue

IBM

Related People

Weinberger, A: AUTHOR

Abstract

A method is described that detects a leading zero of a leading sequence of zeros in a string of bits. A 256-bit string is illustrated. Let A(A0,...,A255) = a 256-bit string identifying data units (DUs) available for assignment. Ai=0 means DUi is available and Ai=1 not available; C(C0,...,C7) = an 8-bit count specifying the number of consecutive unassigned DUs desired, 1-256 (C=0 means 1, C=1 means 2, etc.); B(B0,...,B8) = a 9-bit number identifying the location (suf fix of A) of the first zero of the first sequence of zeros in A of length equal to or greater than C. For example, if A = 110111000010001...

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

Detection of a Leading Zero of a Leading Sequence of Zeros

       A method is described that detects a leading zero of a
leading sequence of zeros in a string of bits.  A 256-bit string is
illustrated.
Let A(A0,...,A255)  =    a 256-bit string identifying data units
(DUs) available for assignment.  Ai=0 means DUi is available and Ai=1
not available;
C(C0,...,C7)    =    an 8-bit count specifying the number of
consecutive unassigned DUs desired, 1-256
                          (C=0 means 1, C=1 means 2, etc.);
     B(B0,...,B8)    =    a 9-bit number identifying the location
(suf                         fix of A) of the first zero of the first
sequence of zeros in A of length equal to or greater than C.
For example, if A   =    110111000010001...
             and C   =    00000010 representing 3 DUs,
            then B   =    00000110 = 6, namely, A6 is the leading
zero of the leading string of zeros of length 3 or greater.

      The implementation transforms A to a string to which a known
leading zero detect method is applied to achieve the desired result.
Reference (1) describes a most significant bit detector that can
easily be modified to detect the leading zero instead of the leading
one.

      A is transformed by replacing trailing zeros with ones in every
sequence of zeros of size specified by the binary value of C.  In the
example, the binary value of C=2 (a desired sequence of 3 or more
zeros).  A zero in A will be forced to a one if one or more
of the two bits to the right are ones.  (Bits to the right of A255
are assumed to be ones.)  As a result, all sequences of 2 or fewer
zeros will be filled with ones and those with 3 or more zeros will be
diminished by 2, namely,

      Transformed A = 111111001110111... When the leading zero of the
transformed A is detected, it identifies the leading zero of the
leading sequence of 3 or more zeros of A.  (Note that when C =
00000000, representing a desired sequence of one, no transformation
is needed.) Figure 1 shows the block diagram of the combined
function, and Figure 2 the primitive equation of the string
transformer.

      When A is of substantial size, such as 256 bits of this
example, the string transformer is implemented in steps.  Figure 3
shows a 3-step string.  In step 1, the high order 3 bits of C (C0,
C1 and C2) transform A into string AX, the next 2 bits of C (C3
and C4) transform AX into AY, and the final 3 bits of C (C5, C6,
and C7) transform AY into the final string T.  The choice of these
steps is a trade-off between stages of logic and number of logic
gates.  A saving of a logic stage by using fewer steps would
significantly increase the number of logic gates.  On the other hand,
only a modest saving of gates results from increasing the number of
steps and hence the number of logic stages.

      Figure 4 shows the equations for...