Length of the longest consecutive 1's in a binary number

Question

I need to implement a digital logic circuit with logic gates such as AND, OR, NOT, ADDER (and so on..), that gets an 8 bits binary number and return the number of the longest consecutive 1's in the input.

For example:

11110011 - will return 4

10101111 - will also return 4

01111111 - will return 7

I would really appreciate some help, as I'm struggling for days to find solution to this problem.

Thanks!

Possible duplicate of [Finding consecutive bit string of 1 or 0](https://stackoverflow.com/questions/3304705/finding-consecutive-bit-string-of-1-or-0) — JJJ, Dec 09 '18 at 19:33

Axel Kemper · Answer 1 · 2018-12-11T09:57:21.480

I generated a truth table with 256 terms and reduced it to 47 terms using the Espresso minimizer:

Then, I converted the compressed table into a multi-level circuit (too big to be displayed here as image). For this, I used Logic Friday 1.

It might be possible to derive a simpler circuit by mapping my C# routine into gates:

private static int countConsecutiveBits(int i)
{
    int bMax = 0;
    int b = 0;

    for (int j = 0; j < 8; j++)
    {
        if (((i >> j) & 1) == 1)
        {
            b++;
            if (bMax < b)
            {
                bMax = b;
            }
        }
        else
        {
            b = 0;
        }
    }

    return bMax;
}

This would involve adders and comparators as indicated in your question.

The following circuit - hand crafted and not verified - is a bit-slice which takes as inputs the so-far maximum bit count, the current bit count and the respective bit. The outputs are the new maximum bit count and the current bit count. All counts are 4-bit wide. This could be optimized for the first slices, where the count is smaller.

Length of the longest consecutive 1's in a binary number

1 Answers1