VHDL rollover of counter

[Jon Elson]

Hello, all,

I am trying to make a counter follow the value of a value sent from another
device. The value coming in is a bidirectional counter that can rollover
in either direction. The value is sampled so it is not necessarily
monotonic, but should not change greatly between samples.

I want to either increment or decrement the counter in my VHDL module
so it tracks the value coming in, and it always needs to go the "shortest"
way around the counter. I got it working on the rollover from -1 to 0
both ways, but then was confounded that it went the "wrong way" at the
half-rollover, from 011111 to 100000, for instance.

It seems like there must be a proper way to treat this so it can be done
with a simple less-than or greater-than comparison, without having to
compare the high two bits with a bunch of special case ors.

Anybody know what I'm mising here?

Thanks much,

Jon

 

[Tim]

On Sat, 09 Jul 2011 22:20:35 -0500, Jon Elson wrote:

Hello, all,

I am trying to make a counter follow the value of a value sent from
another device. The value coming in is a bidirectional counter that can
rollover in either direction. The value is sampled so it is not
necessarily monotonic, but should not change greatly between samples.

I want to either increment or decrement the counter in my VHDL module so
it tracks the value coming in, and it always needs to go the "shortest"
way around the counter. I got it working on the rollover from -1 to 0
both ways, but then was confounded that it went the "wrong way" at the
half-rollover, from 011111 to 100000, for instance.

It seems like there must be a proper way to treat this so it can be done
with a simple less-than or greater-than comparison, without having to
compare the high two bits with a bunch of special case ors.

Anybody know what I'm missing here?

Can you use up an adder? If so it's as simple as c = a - b. If you take
c as 2's compliment, then the magnitude of c is the amount that you need
to change a so that it matches b; the sign of c is the direction. It
will automagically be the shortest distance when interpreted in this
manner.

--
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

 

[Jim Granville]

On Jul 10, 3:20 pm, Jon Elson <el...@pico-systems.com> wrote:

It seems like there must be a proper way to treat this so it can be done
with a simple less-than or greater-than comparison, without having to
compare the high two bits with a bunch of special case ors.

I'm not sure a single comparison will do, as the subset if what you
want is
if A > B then inc(B) elseif A < B then dec(B)
but you are also asking for a 'shortest path' test, which adds another
test, to decide which way is closer : the maths way, or the wrap-way.
and I think that is 4 branches, no matter how you code it ?

 

[Jon Elson]

Jim Granville wrote:

On Jul 10, 3:20 pm, Jon Elson <el...@pico-systems.com> wrote:
It seems like there must be a proper way to treat this so it can be done
with a simple less-than or greater-than comparison, without having to
compare the high two bits with a bunch of special case ors.

I'm not sure a single comparison will do, as the subset if what you
want is
if A > B then inc(B) elseif A < B then dec(B)
but you are also asking for a 'shortest path' test, which adds another
test, to decide which way is closer : the maths way, or the wrap-way.
and I think that is 4 branches, no matter how you code it ?

Yes, of course, you need the count up test and the count down test,
so as to accommodate the case where the input did not change.

Right now I have 6 tests (a pair of 3-way ors depending on the state
of the upper two bits of input and counter) and I'm not sure this is
covering all cases.

I think my main problem was making the input and counter signed.
This takes care of the rollover between -1 and zero both ways work fine,
but totally messes up the overflow between largest negative number and
largest positive.

Changing to unsigned should help, but I still have to come up with a test
for when the < or > comparison give the wrong result.

Thanks, Tim and Jim!

Jon

 

[Jon Elson]

Jon Elson wrote:

Well, I changed it over to unsigned, but I still ended up with
more or clauses than I think should be needed. Anyway, it seems
to be working correctly now.

Thanks,

Jon

 

[Tim Wescott]

On 07/10/2011 03:22 PM, Jon Elson wrote:

Jon Elson wrote:

Well, I changed it over to unsigned, but I still ended up with
more or clauses than I think should be needed. Anyway, it seems
to be working correctly now.

2's compliment or unsigned binary is going to behave the same way as far
as finding the shortest path. Doing the c = a-b subtraction on the top
two (or three) bits will certainly use less logic -- I'm sort of a
permanent FPGA Rip Van Winkle, so I don't know if you could to the 3-bit
version in a pair of LUTs -- but you certainly could with the 2-bit
version, particularly since you only care about the sign bit and equality.

If your synthesizer is at all good with optimization, you should be able
to just do the c = a-b with two (or three) bit data, and have the right
answer pop out. If not, take the truth table below, and have fun with it.

a b up equal
--- --- --- ---
00 00 x 1
00 01 1 0
00 11 0 0
00 10 x x (indeterminate case)
01 10 1 0
01 11 x x " "
01 01 x 1
01 00 0 0
11 00 1 0
11 01 x x " "
11 11 x 1
11 10 0 0
10 10 x 1
10 11 1 0
10 01 0 0
10 00 x x " "

--

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

Do you need to implement control loops in software?
"Applied Control Theory for Embedded Systems" was written for you.
See details at http://www.wescottdesign.com/actfes/actfes.html

 

[Jim Granville]

On Jul 11, 10:22 am, Jon Elson <el...@pico-systems.com> wrote:

Jon Elson wrote:

Well, I changed it over to unsigned, but I still ended up with
more or clauses than I think should be needed.  Anyway, it seems
to be working correctly now.

A quadrant test can be efficient in Logic, but I'm not sure it meets
your condition of always taking the shortest path ?
If the quadrants are opposite, you could take over 128 clocks ?

So I quickly tried some unsigned maths algorithms, which leads to
firstly this in Basic Scripts (Vars are all Unsigned Bytes)
If uAp = uBp Then
exit Function
Else
Diff = uAp - uBp
if uAp > uBp Then
If Diff < 128 Then ' closer than 128, so INC uB
uBp = uBp+1
Else ' go the other way
uBp = uBp-1
End If
Else ' uAp < uBp , so Diff has wrapped
If Diff >= 128 Then ' Wrapped, closer than 128, so DEC uB
uBp = uBp-1
Else ' go the other way
uBp = uBp+1
End If
End If
End If

then I spotted that seems to be

If uAp = uBp Then
exit Function
Else
Diff = uAp - uBp
If Diff < 128 Then
uBp = uBp+1
Else
uBp = uBp-1
End If
End If

and tested this does seem to chose the 'right' direction, and
converge with never more than 128 calls.

So your instincts were right.

The magic of unsigned maths