Expression Of A Partial Shift With Digital Circuit, partial right/left register shifter

Dear members,

I programmed a tool with python and I would like to know if it is implementable on a mobile system with very reduced capacity calculations. This requires an expertise in electronic or digital circuits which is beyond my skills :/

Problem: Making a shift on an input vector from a specific address with a delta offset.
Example: Rot(@2, 3) : delta = 3 offset from the address @2 of the vector. All the other fields have to remain unchanged in the output.
Question: Can I express this type of partial right/left register shifter/rotator via a set of combinational logic gates? This should consume how many logic gates if I have 54 entries and the representation of data is = to 6 bits.

Reminder: in a classical design, a LFSR, performs a shift on a vector, but this will affect the entire output vector. (What I want to do is a partial shift or rotation.)

Thank you in advance for your help. Your help allows me to know if what I do is helpul for the scientific community, or if I have to move on
Looking forward to hear from you soon.

Wai

This post has been edited by wai-tn on February 16, 2012 11:03 pm

In future, do not post the same question three times across different
aspects of the board. We are very active here and most read new posts. I've deleted two of them.

Damien

I'm sorry for this
I didn't know in what topic my question matches the best!

something like that would be quite simple to implement on a mcu or a fpga/gate-based system, assuming we are dealing with integers.

if floaters are involved, it can be quite difficult.

thank you Millwood for your response. Only integers are involved in my design.

If you may, further explanation will be welcome, as I m not a specialist in the domain
mcu or fpga/gate-based system can consume only some hundred of gates with 6 bits output? because the environment of use is very constrained and I have to optimize as much as possible.

is this an example of circuit to implement?
http://en.wikipedia.org/wiki/File:FPGA_cell_example.png

thanks for your interest!
have a nice day!

i am not familiar with fpga enough to tell you if that's schematic is correct.

i can see that implementing in mcu is a piece of cake - simply adding a number to an axis of a vector. you can get simpler than that.

a fully hardware based solution might be the use of memory chips where the address line carries the incoming vector and the adder and the data line carries out the result.

Look up barrel shifter, eg
http://en.wikipedia.org/wiki/Barrel_shifter
Many more results available.
Not sure if this is what you want, since the overflow goes to the LSB.

thanks GPG,

In the example seen in wikipedia, the order of the entries remains the same : ABCD as DABC, CDAB, or BCDA

While I have to realize a shifter doing: ABCD --> ACDB -->ACBD
-> thus, in the output we see only B (or a sequel of entries) moving.
Do the barrel shifter make a partial shift like below or we have to add other calculations?

Why did you think that the overflow goas to the Least Significant Bit ?

Thank you for your reactivity.. any new idea makes the problem easier !

Have a nice day!

Was thinking shift up. Of course the underflow (shift down) will go to MSB, it's the nature of a barrel shifter. You don't shift the bits so much as 'rotate' them.

No a barrel shifter will not do this unless ACD are "don't care" values. But you have made the problem clearer.

that's different from what you described earlier but that's not difficult to do either.

Good news, if the problem is not difficult neither!
In my last message I described the problem using the same example cited in the link sent by GPG.. May be I had to use an expressive example from the beginning!

What I want to do is a rotation/shift for one entry without touching the other entries:

ABCDEFG --> Rot(@2,3) : means rotate (or shift) the content of the adress @2 which is equal to B with three steps at right.
ACDEBFG , is the expected output.

another example:

ABCDEFG --> Rot(@6,3): means rotate the content of the adress @6 which is equal to F with three steps at right.
ABFCDEG is the expected output.

Thank you for your understanding!

I am looking forward to know the solution!

assuming A,B,..G are bits.

rot_r1(dat, n) shifts the nth bit of dat right by 1.

for now, assume n <>0 - we will consider that later.

rot_ra(dat, n) {
tmp = dat & ~((1<<n) | (1<< (n-1)); //clear dat's nth and (n-1)th bits
tmp_n = dat & (1<<n); //nth bit
tmp_n1= dat & (1<<(n-1)); //n-1th bit

return tmp | (tmp_n >> 1) | (tmp_n1 << 1);
}

if n = 0 (the right most bit), you simply shift everything to the right by 1 and fill the msb with the then-lsb.

to right shift a bit multiple times, you simply call the above routine multiple times.

for example to shift the nth bit 5 times,

dat = rot_r1(dat, n); //shift the nth bit by 1. n>=5;
dat = rot_r1(dat, n-1); //shift the n-1th bit by 1.
dat = rot_r1(dat, n-2);
dat = rot_r1(dat, n-3);
dat = rot_r1(dat, n-4);

the above isn't optimized but it should get you started.

thank you.