Check whether a BCD number is a palindrome or not

Thread Starter

TwistedFateX

Joined Oct 30, 2020
5
So i'm having trouble on a Digital Design assignment. I'm supposed to create a circuit in logisim that checks whether a BCD number is a palindrome or not. This is easy enough when the length of the number is given but apparently I'm supposed to do this without knowing the length of the number.
I'm honestly stumped so any help will be appreciated
 

WBahn

Joined Mar 31, 2012
26,398
How is the information presented to you? How do you know when you have seen all of the data? Can you access each end of the number, or only in a sequence from one end? Need more information.
 

Thread Starter

TwistedFateX

Joined Oct 30, 2020
5
Do you know the largest possible number they can give you?
/mike
Unfortunately not

How is the information presented to you? How do you know when you have seen all of the data? Can you access each end of the number, or only in a sequence from one end? Need more information.
We build the circuit connected to the input number, the input number is changed accordingly. We have to get the circuit to work with an input of any length which is what i can;t figure out
 

WBahn

Joined Mar 31, 2012
26,398
HOW is this circuit connected to the input number?

Can you access the digits in the number arbitrarily, or do you have to access them one at a time, starting at one end and not being able to go back once you've moved on to the next digit?
 

Lo_volt

Joined Apr 3, 2014
162
Your first step should be to find the size, in bits, of the number being input. You're saying it can be any size, but there has to be a limit. Perhaps you can design your circuit to a maximum number of bits, and determine how many bits the current input number is. In any case, knowing how many bits is crucial.

Once you've figured out the number of bits, you can move on to determining whether it's a palindrome. What are the characteristics of a palindrome that make it so? How do you think you can test for those characteristics? How would you do it in a logic circuit?
 

dl324

Joined Mar 30, 2015
12,792
We build the circuit connected to the input number, the input number is changed accordingly. We have to get the circuit to work with an input of any length which is what i can;t figure out
Post the entire text of the problem so we can understand what you're being asked to do; and not have to play 20 questions.
 

Thread Starter

TwistedFateX

Joined Oct 30, 2020
5
Post the entire text of the problem so we can understand what you're being asked to do; and not have to play 20 questions.
"Design a system that checks if a multi-digit BCD number input is a palindrome or not."

This is all we're given
 
Last edited:

Thread Starter

TwistedFateX

Joined Oct 30, 2020
5
Your first step should be to find the size, in bits, of the number being input. You're saying it can be any size, but there has to be a limit. Perhaps you can design your circuit to a maximum number of bits, and determine how many bits the current input number is. In any case, knowing how many bits is crucial.

Once you've figured out the number of bits, you can move on to determining whether it's a palindrome. What are the characteristics of a palindrome that make it so? How do you think you can test for those characteristics? How would you do it in a logic circuit?
So I guess I could use xor gates for each digit to check equality and then put that to an and gate to make sure they're all the same? I just can't figure out how to connect the xor gates to the input number when the input number can change, since surely you'd have to increase/decrease the number of gates accordingly with the input size?
 

Thread Starter

TwistedFateX

Joined Oct 30, 2020
5
HOW is this circuit connected to the input number?

Can you access the digits in the number arbitrarily, or do you have to access them one at a time, starting at one end and not being able to go back once you've moved on to the next digit?
It can be anything I guess. As long as it can be implemented in logisim
 

WBahn

Joined Mar 31, 2012
26,398
It can be anything I guess. As long as it can be implemented in logisim
Do YOU get to decide how you access the digits in the number? If not, then whoever is giving you the problem needs to specify how you interact with it. Otherwise it is meaningless.
 

Lo_volt

Joined Apr 3, 2014
162
How do you determine if a number is a palindrome? The most significant digit (MSD) is equal to the least significant digit (LSD) and each successively lesser MSD is equal to each successively greater LSD. So then how would you implement that in logic? I would start with a 3 digit design and scale that to larger numbers of digits.

Since the problem, as stated, is vague, I'd suggest an input that sets the digit count for the given input number.
 

djsfantasi

Joined Apr 11, 2010
7,628
First, @Lo_volt stated you need to know the length in bits. I disagree... I think you need to know the length in BCD digits. Subtle distinction, but more addressing the problem statement and less likely to run into irrelevant issues. But note, you don’t need to know this in advance of solving the problem. Think of a way that the length is an output of your algorithm; not an input.

Secondly, I am not familiar with Logisim. But before you start coding. can you break your problem into simpler sub-problems? Then, except for allocating memory for each new digit, you don’t need to know the number of digits.

Hint: Solve for two digits. Then, solve for three digits. Then, solve for four digits... How do you break a BCD number of unknown length into these simpler problems?
 

jpanhalt

Joined Jan 18, 2008
11,088
Isn't a palindrome in BCD also a palindrome in binary?

With an MCU, you can read the bytes big endian and compare with a little endian read or have a LIFO buffer, etc. Like you, I am not sure how any such thing is done with logisim.
 

djsfantasi

Joined Apr 11, 2010
7,628
Isn't a palindrome in BCD also a palindrome in binary?

With an MCU, you can read the bytes big endian and compare with a little endian read or have a LIFO buffer, etc. Like you, I am not sure how any such thing is done with logisim.
No... In a simple, three digit example, say 0xA0A, the MSB in binary is 1010b. For it to be a palindrome in binary, the LSB must be 0101b, or 0x5. 0xA05 is not a BCD palindrome.
 

WBahn

Joined Mar 31, 2012
26,398
Isn't a palindrome in BCD also a palindrome in binary?
No.

Any number consisting of a single BCD digit is a palindrome, yet the binary bit patterns for only three of the ten BCD digits, namely 0, 6, and 9, are palindromes.

Consequently, knowing that one is or is not a palindrome is not sufficient to know whether or not the other is. It goes both ways. For instance:

dec = binary; <BCD is palindrome, Binary is palindrome>
9 = 1001; <T,T>
4 = 0100; <T,F>
18 =00011000; <F,T>
12 = 00010010; <F,F>

With an MCU, you can read the bytes big endian and compare with a little endian read or have a LIFO buffer, etc. Like you, I am not sure how any such thing is done with logisim.
Your LIFO buffer has to be arbitrarily large if you don't have some upper limit on the length of the input number.

If he has unrestricted access to the data -- and if there is some means of identifying the length of the actual string -- then the problem is trivially easy.

If he had a maximum length of the string he could simply read the string into a RAM buffer and turn it into the former trivial case.

But as soon as the string is of unbounded length, this approach fails as you don't know how big to make the finite RAM buffer.
 
Top