extracting D from 1 / D*D

Uwe Bonnes <bon@elektron.ikp.physik.tu-darmstadt.de> wrote:

(snip, I wrote)
>> Usually this would be done with a barrel shifter, but they are
>> not very LUT efficient in many FPGAs.  If you aren't so restricted
>> in cycles, though, you can use an ordinary shift register.

> You can use a Multiplier as barrel shifter too (Xilinx xapp195)

Usually the barrel shifter problem comes up doing floating point
in an FPGA.  If you use the hardware multipliers for multiplying,
you might not have them avaialble.  But it takes two or three for 
floating point add, which usually makes add bigger than multiply!

For IEEE double, 53 bits is a big shifter!

-- glen

On Aug 18, 11:43=A0am, Steve <theec...@gmail.com> wrote:
> >> Usually this would be done with a barrel shifter, but they are
> >> not very LUT efficient in many FPGAs. =A0If you aren't so restricted
> >> in cycles, though, you can use an ordinary shift register.
>
> > You can use a Multiplier as barrel shifter too (Xilinx xapp195)
>
> Given that there are plenty of clock cycles available and not much HW,
> I'd spend the first 8 clock cycles looking at the two MSBs and left
> shifting two positions when those MSBs are 00. =A0The detection of the
> zero input special case can also be folded into this part very efficientl=
y.

How much clock cycles is plenty?

You can:

a) start with some value for D
b) compute T1=3DD*D
c) compute T2=3DY*T1
d) check whether T2 > K
e) use nested intervals to find the exact value of D in 16 iterations.

Using 16 bit iterative multipliers you are in the range of 80 luts for
the datapath and 16*32 clock cycles.
Using bit serial implementation you will be using even less luts for
the data path and about 16*16*32 clock cycles.

An even simpler solution is not to use nested intervals but making use
of the fact that:
Y*(D+1)*(D+1) - Y*D*D =3D 2*Y*D + 1
and
2*Y*(D+1) - 2*Y*D =3D 2*Y

This means that you can scan all values of D using two additions per
try:
YDD_next =3D YDD + 2YD
2YD_next =3D 2YD + 2Y

Note that this version uses no multipliers.

resulting in
48 LUTs and 64k clock cycles (parallel)
or
6 LUTs and 2M clock cycles (bit serial)

10 bit accuracy is 64 times faster at identical hardware cost.

Kolja
cronologic.de

On Thu, 18 Aug 2011 17:21:39 -0700 (PDT), Kolja Sulimma wrote:

>Y*(D+1)*(D+1) - Y*D*D = 2*Y*D + 1
>and
>2*Y*(D+1) - 2*Y*D = 2*Y
>
>This means that you can scan all values of D using two additions per
>try:
>YDD_next = YDD + 2YD
>2YD_next = 2YD + 2Y
>
>Note that this version uses no multipliers.
>
>resulting in
>48 LUTs and 64k clock cycles (parallel)
>or
>6 LUTs and 2M clock cycles (bit serial)

Very nice use of second differences.

I believe there is a successive-approximation variant of this
which will calculate an N-bit result in N cycles without
multipliers.  But it requires some ingenious juggling with
shifts, and the margin of this post, etc, etc (meaning:
I'm not smart enough to write down the algorithm nicely).
I haven't yet done a LUT count.  It will be a little larger
than Kolja's numbers, but not massively bigger (I think).
Bert, we can discuss offline if you wish.

cheers
-- 
Jonathan
replace spam with jonathan in the published email address.

Hello all !

Sorry, I had to stay away from the forum for a few days.
*Thanks* a lot to all contributors for all their ideas.

I haven't made my mind yet since the sensor still
needs some validation, but there is a lot of food
for thougt here :-)

For the record, "many" means 100 clock cycles would
be fast enough, more (1000 !) clock cycles would still
be possible. That's why in theory, very compact
implementations are possible.
Large accumulators are possible since they can be
pipelined / multi-cycled in this context.
The "best" implementation is a compact enough one
that is easy enough to code :-)

I'll let you know if the project is going to use
this sensor, and which implementation I used.

Bert.