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
    Messages:
    14
    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

    hgmjr Moderator Staff Member

    Joined:
    Jan 28, 2005
    Messages:
    9,030
    Location:
    Tennessee, USA (GMT-6)
    Your description of the goal of your circuit is not clear.

    Can you provide more details?

    hgmjr
  3. asi123

    asi123 Thread Starter New Member

    Joined:
    Apr 1, 2010
    Messages:
    14
    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

    MrChips Moderator Staff Member

    Joined:
    Oct 2, 2009
    Messages:
    9,806
    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

    asi123 Thread Starter New Member

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

    I meant the smallest repeated pattern size.

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

    WBahn AAC Fanatic!

    Joined:
    Mar 31, 2012
    Messages:
    8,129
    Location:
    Larkspur, Colorado
    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

    panic mode Well-Known Member

    Joined:
    Oct 10, 2011
    Messages:
    1,103
    Location:
    Mississauga, Ontario
    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. Bill_Marsden

    Bill_Marsden Moderator Staff Member

    Joined:
    Mar 24, 2008
    Messages:
    19,233
    Location:
    Dallas, TX (GMT-5 w/ DST)
    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

    asi123 Thread Starter New Member

    Joined:
    Apr 1, 2010
    Messages:
    14
    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.
  10. WBahn

    WBahn AAC Fanatic!

    Joined:
    Mar 31, 2012
    Messages:
    8,129
    Location:
    Larkspur, Colorado
    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.
Similar Threads
Forum Title Date
Homework Help clocked sequential circuit to detect the serial input pattern 1110 Nov 14, 2010
Homework Help Pattern detector Oct 27, 2010
Homework Help LEED pattern Dec 4, 2009
Homework Help string pattern recognizer Sep 30, 2009
Homework Help MultiSim HW - Shifting Input Pattern-Shift Registers, Tristates, JK Flip-Flops Nov 7, 2008

Related Site Pages

Section Title
Worksheet Analog-to-Digital conversion
Worksheet Binary math

Share This Page