Smallest pattern size in a Byte

[asi123]

Hey guys.

I need to build a circuit that its input is a Byte and its output is the smallest pattern size.

For example

Input: 00000000 Output: 1
Input: 01010101 Output: 2
Input: 11011101 Output: 4
Input: 11111110 Output: 8

Any ideas guys?

Thanks a lot.

Assaf.

[hgmjr]

Your description of the goal of your circuit is not clear.

Can you provide more details?

hgmjr

[asi123]

Originally Posted by hgmjr

Your description of the goal of your circuit is not clear.

Can you provide more details?

hgmjr

Hey, this is how we got the question...

I agree with you, it's not the most clear one.

I wonder if I can build it with a FSM.

I think they want some kind of a combinational circuit but If I wont find a solution, I guess I'll use some kind of memory with 256 memory units.

[MrChips]

Originally Posted by asi123

I need to build a circuit that its input is a Byte and its output is the smallest pattern size.

There is a breakdown in communication here.
Forget about building any kind of circuit.
Firstly you have to define what you mean by "smallest pattern size."

The description makes absolutely no sense.
I would take it back to the teacher and ask him/her to restate the assignment.

[asi123]

Sorry, my mistake.

I meant the smallest repeated pattern size.

I can't edit after 60 minutes apparently.

[WBahn]

Originally Posted by asi123

Input: 00000000 Output: 1
Input: 01010101 Output: 2
Input: 11011101 Output: 4
Input: 11111110 Output: 8

What pattern do you get if you rotate the first input by 1, the second by 2, the third by 4, and the fourth by 8?

Can you have a pattern that repeats with a shortest pattern length of 3? If not, why not and, consequently, which lengths are possible?

Once you understand the answers to these questions, there are a couple of obvious ways to implement a circuit that answers the question. You can do it using nothing but combinatorial logic and it isn't that bad. You can also do it with a sequential circuit and it would be very simple to implement.

[panic mode]

there are only few possible answers, instead of writing pattern recognition algorithm, why not just encode all possible outcomes?
output 1 is either for 00000000 or 11111111
output 2 is either for 10101010 or 01010101
etc.

[Bill_Marsden]

FYI, after 10 posts you will be able to edit to your hearts content, this option was limited due to people erasing their homework questions. If it get abused the number count could be bumped up, or the feature eliminated entirely.

[asi123]

Originally Posted by panic mode

there are only few possible answers, instead of writing pattern recognition algorithm, why not just encode all possible outcomes?
output 1 is either for 00000000 or 11111111
output 2 is either for 10101010 or 01010101
etc.

That's my last option if I wouldn't have found a solution, obviously best solution if you have enough memory (and if memory is allowed solution).

However WBahn had a great idea and I think I'll use.

Thanks a lot.

Very helpful.

Assaf.

[WBahn]

Originally Posted by asi123

That's my last option if I wouldn't have found a solution, obviously best solution if you have enough memory (and if memory is allowed solution).

I would argue that using a lookup table is, in most instances, not the best solution. There are places in which that is not the case and it is, arguable, the ideal approach.

But the table you were talking about implementing and the table panic mode was leading you toward are two very different approaches.

You were talking about encoding all 256 possible patterns. Since, by brute force, each byte could have a pattern length between 1 and 8, you would need a minimum of 3 bits for each byte (encode the patterns as 0 to 7 and always add 1), you would need 86 bytes of memory.

The approach panic mode was taking (I may be going a bit further than he was thinking) was to see that there are only 2 bytes with a minimum pattern length of 1 and 2 bytes with a minimum pattern length of 2. As it turns out, there are only 12 bytes with a minimum pattern length of 4 and all the rest have a pattern length of 8. Thus you could use just 16 bytes of memory. You then search down the table to see if you find the input byte and, if you find it, based on the address of the entry in the table, you know what the minimum pattern length is.

In my approach, which doesn't require any memory, you are actually doing something conceptually similar.