# Smallest pattern size in a Byte

Discussion in 'Homework Help' started by asi123, Apr 13, 2012.

1. ### asi123 Thread Starter New Member

Apr 1, 2010
14
0
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.

2. ### hgmjr Moderator

Jan 28, 2005
9,030
214

Can you provide more details?

hgmjr

3. ### asi123 Thread Starter New Member

Apr 1, 2010
14
0
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.

4. ### MrChips Moderator

Oct 2, 2009
12,440
3,361
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.

5. ### asi123 Thread Starter New Member

Apr 1, 2010
14
0
Sorry, my mistake.

I meant the smallest repeated pattern size.

I can't edit after 60 minutes apparently.

6. ### WBahn Moderator

Mar 31, 2012
17,743
4,792
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.

7. ### panic mode Senior Member

Oct 10, 2011
1,320
304
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.

8. ### Wendy Moderator

Mar 24, 2008
20,765
2,536
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.

9. ### asi123 Thread Starter New Member

Apr 1, 2010
14
0
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.

Assaf.

10. ### WBahn Moderator

Mar 31, 2012
17,743
4,792
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.