Smallest pattern size in a Byte

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

  1. asi123

    asi123 Thread Starter New Member

    Joined:
    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.
     
    #1
  2. hgmjr

    hgmjr Moderator

    Joined:
    Jan 28, 2005
    9,030
    210
    Your description of the goal of your circuit is not clear.

    Can you provide more details?

    hgmjr
     
    #2
  3. asi123

    asi123 Thread Starter New Member

    Joined:
    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.
     
    #3
  4. MrChips

    MrChips Moderator

    Joined:
    Oct 2, 2009
    11,758
    3,013
    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.
     
    #4
  5. asi123

    asi123 Thread Starter New Member

    Joined:
    Apr 1, 2010
    14
    0
    Sorry, my mistake.

    I meant the smallest repeated pattern size.

    I can't edit after 60 minutes apparently.
     
    #5
  6. WBahn

    WBahn Moderator

    Joined:
    Mar 31, 2012
    12,858
    3,241
    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.
     
    #6
  7. panic mode

    panic mode Well-Known Member

    Joined:
    Oct 10, 2011
    1,207
    254
    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.
     
    #7
  8. Wendy

    Wendy Moderator

    Joined:
    Mar 24, 2008
    20,060
    2,057
    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.
     
    #8
  9. asi123

    asi123 Thread Starter New Member

    Joined:
    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.

    Very helpful.

    Assaf.
     
    #9
  10. WBahn

    WBahn Moderator

    Joined:
    Mar 31, 2012
    12,858
    3,241
    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.
     
    #10
Loading...