Palindrome detection circuit -Need help designing

Discussion in 'General Electronics Chat' started by JohnGeorge, Jul 1, 2008.

1. JohnGeorge Thread Starter New Member

Nov 20, 2007
6
0
Hi,

First, I would like to design a two level circuit that accepts a 4bit input string and determines if it is a palindrome.

Second, I would also like to implement this 4bit detection system using a 8x1 multiplexer with 3 control lines and 8 input lines.

I have not been able to find much information on the internet. Can you help me draw the two circuits? Thanks in advance.

2. jpanhalt AAC Fanatic!

Jan 18, 2008
5,699
909
I must be missing something, so let me re-phrase the first part of the question. If the four bits are binary, i.e., 0-15, and you exclude the trivial answers, there is only one palindrome in that sequence, namely 11. Now, if you look at the binary, eleven is not a palindrome, but six, nine, and 15 (and zero) are.

So, in what base do you want the palindrome to be defined? Are you referring to numbers or words?

The simplest circuit I can think of right now would involve microcontroller, such as as PIC 16F628A, but there are many other possibilities. Are you willing to use software or do you want a hardware solution?

John

3. JohnGeorge Thread Starter New Member

Nov 20, 2007
6
0
Sorry I did not make my question clear enough. I would like to check for a palindrome in base 2 using logic gates. I would prefer not to use xor gates in the circuit.

Example of what I would like to do:

Input: 1101 Output: 0 (not a palindrome)
Input: 1001 Output: 1 (palindrome)
Input: 1111 Ouptut: 1 (palindrome)
Input: 1010 Output: 0 (not a palindrome)

4. blocco a spirale AAC Fanatic!

Jun 18, 2008
1,460
370
For 4-bit binary palindrome detection, you could XNOR bits 1&4, XNOR bits 2&3 then AND the two results.

5. JohnGeorge Thread Starter New Member

Nov 20, 2007
6
0
I got the truth table:

Input Output
0000 1
0001 0
0010 0
0011 0
0100 0
0101 0
0110 1
0111 0
1000 0
1001 0
1010 0
1011 0
1100 0
1101 0
1110 0
1111 1

I dont have any Xnor or Xor gates so I would need a solution that does not use them.

6. blocco a spirale AAC Fanatic!

Jun 18, 2008
1,460
370
You could make XNOR from NAND gates.

7. hgmjr Moderator

Jan 28, 2005
9,030
214
Shouldn't you include 1001 as one of the palindromes?

hgmjr

8. hgmjr Moderator

Jan 28, 2005
9,030
214
You can construct and XOR function using inverters and OR gates.

hgmjr

Jan 18, 2008
5,699
909
10. JohnGeorge Thread Starter New Member

Nov 20, 2007
6
0
I made a mistake typing. From the truth table I get the boolean equation
F=A'B'C'D'+A'BCD'+AB'C'D+ABCD

I got the circuit figure out. I am not sure how to solve the problem with the 8-1 mux and ideas on how I should set it up?

11. JohnGeorge Thread Starter New Member

Nov 20, 2007
6
0
Still having problems with how to implement this 4bit detection system using a 8x1 multiplexer with 3 control lines and 8 input lines. Any help with that or resources that can help me? Thanks.

12. thingmaker3 Retired Moderator

May 16, 2005
5,072
6
You could easily do it with a 16x1 mux (four address lines) or two each 1x8 muxes (with some unused lines in one mux). I really don't think it can be done with a single 8x1 mux. You can't represent a four digit number with three digits.