All About Circuits Forum  

Go Back   All About Circuits Forum > Electronics Forums > Homework Help

Notices

Homework Help Stuck on a textbook question or coursework? Cramming for a test and need help understanding something? Post your questions and attempts here and let others help.

Reply   Post New Thread
 
Thread Tools Display Modes
  #1  
Old 04-13-2012, 06:43 PM
asi123 asi123 is offline
Junior Member
 
Join Date: Apr 2010
Posts: 14
Default Smallest pattern size in a Byte

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.
Reply With Quote
  #2  
Old 04-13-2012, 06:49 PM
hgmjr's Avatar
hgmjr hgmjr is offline
Super Moderator
 
Join Date: Jan 2005
Location: Tennessee, USA (GMT-6)
Posts: 9,030
Blog Entries: 11
Default

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

Can you provide more details?

hgmjr
Reply With Quote
  #3  
Old 04-13-2012, 07:15 PM
asi123 asi123 is offline
Junior Member
 
Join Date: Apr 2010
Posts: 14
Default

Quote:
Originally Posted by hgmjr View Post
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.
Reply With Quote
  #4  
Old 04-13-2012, 07:41 PM
MrChips's Avatar
MrChips MrChips is online now
Super Moderator
 
Join Date: Oct 2009
Posts: 8,994
Blog Entries: 23
Default

Quote:
Originally Posted by asi123 View Post
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.
__________________
Most computer problems can be attributed to a simple problem - a loosewire behind the keyboard.

Reply With Quote
  #5  
Old 04-13-2012, 07:47 PM
asi123 asi123 is offline
Junior Member
 
Join Date: Apr 2010
Posts: 14
Default

Sorry, my mistake.

I meant the smallest repeated pattern size.

I can't edit after 60 minutes apparently.
Reply With Quote
  #6  
Old 04-13-2012, 08:45 PM
WBahn WBahn is offline
Senior Member
 
Join Date: Apr 2012
Location: Larkspur, Colorado
Posts: 8,068
Blog Entries: 9
Default

Quote:
Originally Posted by asi123 View Post

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.
Reply With Quote
  #7  
Old 04-13-2012, 09:36 PM
panic mode's Avatar
panic mode panic mode is offline
Senior Member
 
Join Date: Oct 2011
Location: Mississauga, Ontario
Posts: 1,091
Default

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.
Reply With Quote
  #8  
Old 04-13-2012, 10:04 PM
Bill_Marsden's Avatar
Bill_Marsden Bill_Marsden is offline
Super Moderator
 
Join Date: Mar 2008
Location: Dallas, TX (GMT-5 w/ DST)
Posts: 19,022
Blog Entries: 5
Default

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.
__________________
..
"Good enough is enemy of the best." An old engineering saying, Author unknown.

General info:
If you have a question, please start a thread/topic. I do not provide gratis assistance via PM nor E-mail, as that would violate the intent of this Board, which is sharing knowledge ... and deprives you of other knowledgeable input. Thanks for the verbage Wookie.
Reply With Quote
  #9  
Old 04-14-2012, 07:52 AM
asi123 asi123 is offline
Junior Member
 
Join Date: Apr 2010
Posts: 14
Default

Quote:
Originally Posted by panic mode View Post
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.
Reply With Quote
  #10  
Old 04-14-2012, 08:28 PM
WBahn WBahn is offline
Senior Member
 
Join Date: Apr 2012
Location: Larkspur, Colorado
Posts: 8,068
Blog Entries: 9
Default

Quote:
Originally Posted by asi123 View Post
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.
Reply With Quote
Reply   Post New Thread

Tags
, , ,


Related Site Pages
Section Title
Worksheet Analog-to-Digital conversion
Worksheet Memory devices
Worksheet Binary math


Similar Threads
Thread Thread Starter Forum Replies Last Post
PIC Division (multiplication of inverse) Pencil Embedded Systems and Microcontrollers 43 Yesterday 04:22 PM
USB Keyboard with PIC18F4550 Dalaran Embedded Systems and Microcontrollers 4 09-01-2012 10:39 AM
i wanna USB HID mikroC Open source code buffon2009 Embedded Systems and Microcontrollers 4 02-20-2012 09:49 AM
PIC code help skuzzie Homework Help 3 03-02-2009 05:08 PM
keypad question conanav Embedded Systems and Microcontrollers 9 06-28-2008 10:26 PM

Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump


All times are GMT. The time now is 04:32 PM.


User-posted content, unless source quoted, is licensed under a Creative Commons Public Domain License.
Powered by vBulletin
Copyright ©2000 - 2014, vBulletin Solutions, Inc.