FSM and Datapath for palindrome

Thread Starter

de1337ed

Joined Mar 6, 2011
23
Hey guys,

I have an assignment that requires me to construct a datapath and an fsm that will tell if a string in a given block of memory is a palindrome.
We are given the following inputs:
A StringAddress(memory address of first byte of palindrome string)
A StringLength(Length of the palindrome string, we are guarenteed that StringAddress + StringLength < 2^16)
Ready (indicates that memory bank has test string and that StringAddress and StringLength have good data), when asserted, do calculation.

2 outputs:
Done: when asserted, the check is complete
isPalindrome: asserted if string is a palindrome.
;;;;;;;;;;;;;;;

So this is what I was thinking,
I would have one part of the datapath that would count upwards from the StringAddress to StringAddress + StringLength.
And then another part of the datapath that would count from StringAddress+StringLength to StringAddress.
The registers for each of these would be connected to the address line for the memory bank, through a mux (whose selector I control).
I don't really know what to do now...
As a summary, i am basically trying to have a counter that starts from the beginning of the memory block, and one that starts at the end of a memory block and at each clock edge, they will be compared to one another using a comparator.
Can anyone guide me through this? I'm really bad at these things. Thank you.
 

Georacer

Joined Nov 25, 2009
5,182
So, if I read this right, you need to build a digital circuit that will collect a block from a given memory address and decide if it's palindrome or not.

Are you sure about the restriction StringAddress + StringLength < 2^16? It's not very helpful. The address and the string are two separate things. Moreover, the address length isn't more than some dozens of bits long, which leaves the data string 2^16 bits long at max. This is A LOT.

In what level of abstraction you need to build this? If you need to build an FSM for a 2^16 bit string using registers, the circuit will be chaotically big.

On the other hand, if you just examine the string bits in pairs (first-last, second-second to last, etc) that is much easier but isn't an fsm.

Please provide more info.
 

Thread Starter

de1337ed

Joined Mar 6, 2011
23
The problem itself is pretty badly worded, but from what I understand, its like this:

Say that you had a string "abcba", the letter "a" is stored in some memory location called StringAddress, lets assume that the address is the hex 0x0000. We also know the string length is 5, so we know that the block of letters we are looking at is 0x0000 to 0x0004.

Basically, I'm trying to make a datapath, and an FSM that controls this datapath to see if this block of memory holds a palindrome.

Let me know if you need more detail.
 

Georacer

Joined Nov 25, 2009
5,182
What exactly do you mean by datapath? I 'm not very familiar with the term.
Do you need to write a piece of code, controlled by a simulated FSM or do you actually need to build a circuit that will check the palindrome circuit.

For the first option you must choose a programming language.
For the second one, you must either specify a hardware description language or the kind of circuit you want to build (74XX digital logic, microcontroller, PLC, etc).

Posting the original exercise question would probably help too.
 

Thread Starter

de1337ed

Joined Mar 6, 2011
23
What exactly do you mean by datapath? I 'm not very familiar with the term.
Do you need to write a piece of code, controlled by a simulated FSM or do you actually need to build a circuit that will check the palindrome circuit.

For the first option you must choose a programming language.
For the second one, you must either specify a hardware description language or the kind of circuit you want to build (74XX digital logic, microcontroller, PLC, etc).

Posting the original exercise question would probably help too.
By datapath, I mean a circuit that uses any number of combinational or synchronous RTL components. So like arithmetic + logical operators. Comparators, counters, decoders, multiplexers, tri-state buffers, registers, etc. So we are not talking on the gate-level circuitry, we are talking at the level above that. (Components that use this gate-level circuitry)

Wikipedia: http://en.wikipedia.org/wiki/Datapath
 

Georacer

Joined Nov 25, 2009
5,182
Understood. However this approach requires a lot of building material. You didn't answer me about the validity of the 2^16 string length restriction. Nor did you clarify the string length. Is it up to a dozen? A hundred? 2^16? It makes all the difference for your circuit taking it from feasible to impossible.

Could you provide some example inputs for your circuit, to nail down what we are talking about?

Since you are going to work with ICs and memory chips, I 'd like to add that you will probably need to read from the memory in words. These have a set length. Can the data string exceed the word length? This will alter your design options.
 

Thread Starter

de1337ed

Joined Mar 6, 2011
23
Understood. However this approach requires a lot of building material. You didn't answer me about the validity of the 2^16 string length restriction. Nor did you clarify the string length. Is it up to a dozen? A hundred? 2^16? It makes all the difference for your circuit taking it from feasible to impossible.

Could you provide some example inputs for your circuit, to nail down what we are talking about?

Since you are going to work with ICs and memory chips, I 'd like to add that you will probably need to read from the memory in words. These have a set length. Can the data string exceed the word length? This will alter your design options.
From what I understand about the 2^16 restriction is that basically that the StringLength will not be large enough to go past the memory block (which has 2^16 spaces). So like if the start address is 0xFFFA. The StringLength has to be less than or equal to 6.
And our circuit will simply take in a StringAddress and StringLength, and a ready signal telling us that the StringAddress and StringLength is good data. It has to output "done" and isPalindrome.

I have this new thought about it: I know that each data coming out of the memory will be 8 bits (1 byte). So what I was thinking is that I would first traverse the memory block in one direction (from stringAddress to stringAddress+StringLength), and add the values up and store it as an 8 bit value in some register. I will then do the same except in the opposite direction (stringAddress+StringLength to StringAddress), and subtract the values from the 8bit register, and restore it inside that register. I will then compare this value with 0. If this value is 0, then its a palindrome, otherwise its not. Does this sound like a feasible plan? I'm sort of scared about overflow, but I don't think that this should make a difference. Thanks for the help.
 

Georacer

Joined Nov 25, 2009
5,182
I don't think your idea will work. In your approach, any string will show up as palindrome. Take FFAA for example F+F+A+A=A+A+F+F.

The only way I can think of this working without a bazillion hardware, is to compare the data in pairs, from the start and the end simultaneously.

For example: You have an two 8-bit accumulators. You fill the first with the first word and the second with the last word. Compare them and go on if equal.
Load the next inwards pair and do the same until you run out of pairs.

For each comparison you must access the memory twice. What kind of memory will be used? It may affect the implementation.

The necessary components in my approach will be:

  1. The arithmetic circuits that will resolve the data range, based on the StringAddress and StringLength.
  2. Two counters that will move the two cursors. The first counter will count from StringAddress to StringAddress+StringLength/2 and the second from StringAddress+StringLength to StringAddress+StringLength/2+1. If StringLength can be either even or odd, extra hardware will be needed. It is also affected by the format. Am I to assume that those numbers will be given in binary?
  3. The suitable clocking circuits that will referee the load transactions and the comparison action.
By now, you should place this project onto a real background. This is too big to be a homework assignment and too vague to be a real product. Please provide more background information.

If it is indeed a homework assignment, please post a photo of the exercise and/or the title of the book where it came from, or is used for that course.
 

mannycc

Joined Dec 11, 2010
17
One suggestion if my understanding with the problem is correct. You need to two sets of shift registers with serial outputs, the first with inputs configured to receive the data from msb to lsb and the other from lsb to msb. the the two outputs are then compared/detected by xor gate. When the xor gate is triggered (logical 1) indicates that the data bits are not palindrome.
Rgds.
 

Georacer

Joined Nov 25, 2009
5,182
That's it more or less. However the use of parallel in / parallel out registers would speed up the process significantly. These are a tad hard to find though.
 

Georacer

Joined Nov 25, 2009
5,182
Okay, but it will delay your system by 8. It's alright I guess for a educational circuit and it makes for much less hardware.
 

mannycc

Joined Dec 11, 2010
17
Oh yes got your point, most of the time i've got to look back not only twice to see the more logical (practical) solution.
Brgds.
 
Top