Powered by Invision Power Board


Forum Rules Forum Rules (Please read before posting)
  Reply to this topicStart new topicStart Poll

> Expression Of A Partial Shift With Digital Circuit, partial right/left register shifter
wai-tn
Posted: January 14, 2012 11:35 pm
Reply to this postQuote Post


Newbie
**

Group: Members+
Posts: 11
Member No.: 36,379
Joined: January 14, 2012




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 cool.gif
Looking forward to hear from you soon.

Wai

This post has been edited by wai-tn on February 16, 2012 11:03 pm
PMEmail Poster
Top
damien
Posted: January 14, 2012 11:54 pm
Reply to this postQuote Post


Forum Addict ++
Group Icon

Group: Moderators
Posts: 5,464
Member No.: 175
Joined: October 02, 2002




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


--------------------
Wow you look quite normal for a geek.

The statistics on sanity are that one out of every four persons is suffering from some sort of mental illness. Think of your three best friends -- if they're okay, then it's you.
PMEmail PosterUsers Website
Top
wai-tn
Posted: January 15, 2012 12:00 am
Reply to this postQuote Post


Newbie
**

Group: Members+
Posts: 11
Member No.: 36,379
Joined: January 14, 2012




I'm sorry for this
I didn't know in what topic my question matches the best!
PMEmail Poster
Top
millwood
Posted: January 15, 2012 02:35 am
Reply to this postQuote Post


Forum Addict ++
*******

Group: Trusted Members
Posts: 1,823
Member No.: 25,377
Joined: July 26, 2009




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.
PMEmail Poster
Top
wai-tn
Posted: January 15, 2012 09:59 am
Reply to this postQuote Post


Newbie
**

Group: Members+
Posts: 11
Member No.: 36,379
Joined: January 14, 2012




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 blush.gif
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!
PMEmail Poster
Top
millwood
Posted: January 15, 2012 02:14 pm
Reply to this postQuote Post


Forum Addict ++
*******

Group: Trusted Members
Posts: 1,823
Member No.: 25,377
Joined: July 26, 2009




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.
PMEmail Poster
Top
GPG
Posted: January 16, 2012 03:23 am
Reply to this postQuote Post


Forum Addict ++
*******

Group: Spamminator Taskforce
Posts: 6,219
Member No.: 792
Joined: April 25, 2004




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.
PMEmail Poster
Top
wai-tn
Posted: January 16, 2012 12:54 pm
Reply to this postQuote Post


Newbie
**

Group: Members+
Posts: 11
Member No.: 36,379
Joined: January 14, 2012




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!
PMEmail Poster
Top
GPG
Posted: January 16, 2012 01:20 pm
Reply to this postQuote Post


Forum Addict ++
*******

Group: Spamminator Taskforce
Posts: 6,219
Member No.: 792
Joined: April 25, 2004




QUOTE
Why did you think that the overflow goas to the Least Significant Bit ?
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.
QUOTE
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?
No a barrel shifter will not do this unless ACD are "don't care" values. But you have made the problem clearer.
PMEmail Poster
Top
millwood
Posted: January 16, 2012 10:53 pm
Reply to this postQuote Post


Forum Addict ++
*******

Group: Trusted Members
Posts: 1,823
Member No.: 25,377
Joined: July 26, 2009




QUOTE
While I have to realize a shifter doing: ABCD --> ACDB -->ACBD


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

PMEmail Poster
Top
wai-tn
Posted: January 16, 2012 11:20 pm
Reply to this postQuote Post


Newbie
**

Group: Members+
Posts: 11
Member No.: 36,379
Joined: January 14, 2012




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!
PMEmail Poster
Top
millwood
Posted: January 17, 2012 12:15 am
Reply to this postQuote Post


Forum Addict ++
*******

Group: Trusted Members
Posts: 1,823
Member No.: 25,377
Joined: July 26, 2009




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.

PMEmail Poster
Top
millwood
Posted: January 17, 2012 12:17 am
Reply to this postQuote Post


Forum Addict ++
*******

Group: Trusted Members
Posts: 1,823
Member No.: 25,377
Joined: July 26, 2009




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.
PMEmail Poster
Top
wai-tn
Posted: February 16, 2012 02:04 am
Reply to this postQuote Post


Newbie
**

Group: Members+
Posts: 11
Member No.: 36,379
Joined: January 14, 2012




thank you.
PMEmail Poster
Top
0 User(s) are reading this topic (0 Guests and 0 Anonymous Users)
0 Members:

Topic Options Reply to this topicStart new topicStart Poll

 


:: support us ::




ElectronicsSkin by DutchDork & The-Force