High speed leading or trailing bit value detection

A trailing bit detector configured to locate and output a binary encoded position of a trailing bit of a desired value in an input string of bits, comprising:

• a plurality of input encoders, each accepting as input equal length sub-strings of the original input string, and each generating a binary encoded position of a trailing bit of a desired value within the sub-string;
• a plurality of bit value detectors, each also accepting as input the equal length sub-strings of the original input string, each detector indicating if the desired bit value exists within the sub-string;
• an encoder arbitrator accepting as input the outputs of the bit value detectors and the binary encoded position from each of the input encoders, said arbitrator forwarding the binary encoded position of the trailing bit of a desired value within the least significant sub-string;
• and
• a least significant sub-string encoder accepting as input the outputs from the bit value detectors, said sub-string encoder generating a binary encoded representation of the least significant sub-string comprising the desired bit value;
• wherein the output of the encoder arbitrator and the output of the least significant sub-string encoder are concatenated to form the binary encoded representation of the position of the trailing bit of a desired value in the input string of bits.

A method of locating and indicating the position of a leading binary bit value in a string of bits, comprising:

• a) dividing the string of bits into shorter length segments, each segment represented by a unique binary value;
• b) setting a bit flag for each of the shorter length segments that contain the bit value;
• c) generating a binary location of the leading binary bit value for each of the shorter length segments;
• d) selecting the unique binary value of the most significant shorter length segment that contains the bit value;
• e) selecting the binary location generated in step c) for the most significant shorter length segment that contains the bit value;
• and
• f) concatenating the unique binary value selected in step d) with the binary location selected in step e) to output a final binary representation of the location of the leading binary bit value in the original string of bits.

A method of locating and indicating the position of a trailing binary bit value in a string of bits, comprising:

• a) dividing the string of bits into shorter length segments, each segment represented by a unique binary value;
• b) setting a bit flag for each of the shorter length segments that contain the bit value;
• c) generating a binary location of the trailing binary bit value for each of the shorter length segments;
• d) selecting the unique binary value of the least significant shorter length segment that contains the bit value;
• e) selecting the binary location generated in step c) for the least significant shorter length segment that contains the bit value;
• and
• f) concatenating the unique binary value selected in step d) with the binary location selected in step e) to output a final binary representation of the location of the trailing binary bit value in the original string of bits.

A method of locating and indicating the position of a leading binary bit value in an input string of bits, comprising:

• sub-dividing the input string into sub-strings;
• locating the position of the leading binary bit value in each substring and generating a first binary representation of this position for each substring;
• identifying a most significant substring that includes the most significant bit value in the input string and generating a second binary representation of this substring;
• and
• combining the first binary representation corresponding to the most significant substring and the second binary representation to form a single output binary representation of the position of a leading binary bit value in the input string.

A method of locating and indicating the position of a trailing binary bit value in an input string of bits, comprising:

• sub-dividing the input string into substrings;
• locating the position of the trailing binary bit value in each substring and generating a first binary representation of this position for each substring;
• identifying a least significant substring that includes the least significant bit value in the input string and generating a second binary representation of this substring;
• and
• combining the first binary representation corresponding to the least significant substring and the second binary representation to form a single output binary representation of the position of a trailing binary bit value in the input string.

A digital circuit for generating a binary encoded position of a leading bit value in an input string of bits, comprising:

• a sub-dividing means for dividing the input string of bits into equal length sub-strings;
• an input encoder means corresponding to each sub-string for generating a binary encoded position of a leading bit value in each sub-string;
• a bit value detection means corresponding to each sub-string to indicate whether the bit value exists in each sub-string;
• an output encoder means for selecting the most significant sub-string containing the bit value and generating a unique binary representation of this sub-string;
• and
• an arbitrator means for selecting the most significant sub-string containing the bit value and forwarding the binary encoded position from the input encoder means corresponding to that sub-string;
• wherein the output of the output encoder means and the output of the arbitrator means are combined to form a single binary representation of the position of the leading bit value in the input string of bits.

A digital circuit for generating a binary encoded position of a trailing bit value in an input string of bits, comprising:

• a sub-dividing means for dividing the input string of bits into equal length sub-strings;
• an input encoder means corresponding to each sub-string for generating a binary encoded position of a trailing bit value in each sub-string;
• a bit value detection means corresponding to each sub-string to indicate whether the bit value exists in each sub-string;
• an output encoder means for selecting the least significant sub-string containing the bit value and generating a unique binary representation of this sub-string;
• and
• an arbitrator means for selecting the least significant sub-string containing the bit value and forwarding the binary encoded position from the input encoder means corresponding to that sub-string;
• wherein the output of the output encoder means and the output of the arbitrator means are combined to form a single binary representation of the position of the trailing bit value in the input string of bits.