Ideas how to do this?

[Tobias Weingartner]

Hello all,

Thank you all for the help and direction you guys have given me
over the last few weeks. This newsgroup is turning out to be like
the days of old, usefull, and of a very decent SNR.

Anyways, I've been trying to figure out a circuit/program in verilog
that coorelates two serial bit streams to a in-memory representation
of the two bit-streams, and outputs the current "location". I'm
not even sure what to call this type of circuit, but bit-stream
correlator seems about right.

The input streams would be asynchronous to the system clock, but
are relative to each other. In other words, I'm looking for synch
up with a particular position in the two bit-streams (they are
recurring) by looking at the relationship they have with each other
over time. Each waveform (on a 1 degree interval) is described
using some memory like storage (such that the user of the module
can describe/input arbitrary waveforms). The output should be a
clock, and data bus describing the position we are currently tracking,
and a valid pin describing if we have synchronized up or not.


On this vein, does anyone know of a good book on such "advanced"
things in logic design? Seems every logic book out there is of a
the introduction type...


Thank you for any pointers/help,

--
[100~Plax]sb16i0A2172656B63616820636420726568746F6E61207473754A[dZ1!=b]salax

 

[glen herrmannsfeldt]

Tobias Weingartner wrote:

(snip)

Anyways, I've been trying to figure out a circuit/program in verilog
that coorelates two serial bit streams to a in-memory representation
of the two bit-streams, and outputs the current "location". I'm
not even sure what to call this type of circuit, but bit-stream
correlator seems about right.

(snip)

I am a little unsure what you are asking, but for aligning
character strings, possibly including insertions and deletions,
dynamic programming algorithms, and systolic array
implementations of such algorithms work very well.

If you don't need insertions and deletions, finite state
automatons are pretty good if you can preprocess the pattern
(is that what you mean by in-memory representation) into a
state table.

There are books on dynamic programming, systolic arrays,
and finite state automatons, but maybe not all in one book.

-- glen

 

Perhaps a content addressable memory, with entries holding
one of the patterns shifted different amounts. This would be
pretty expensive in terms of hardware, compared to taking
advantage of your greater knowledge of the relationship
between the entries. On the other hand, it might use an
off-the-shelf design for the CAM.

This sounds like a rather hard thing to do. And if you are
dealing with asynchronous inputs, that is an entire mess
of its own.

 

At those speeds, you might be able to use an embedded
microcontroller and a software solution.

This kind of reminds me of locking onto GPS signals,
which requires synching up to a pseudorandom
number sequence. We used to do that in software,
though it took a while to lock on. Then again, we
were having to deal with bit rates around 1Mb/s,
phase shift keying on a sinusoidal carrier, doppler
shift (which would correspond to a variation in the
speed of your encoder wheels), and input with a
noise level higher than the signal level.

 

[Tobias Weingartner]

sharp@cadence.com wrote:

At those speeds, you might be able to use an embedded
microcontroller and a software solution.

Yes and no. The resolution required is pretty tough, and
would require custom programming of a separate cpu just to
keep track of these events. I'm already using a cpu to do
lots of other things.

Basically, once I have synced up, and interprolated the
position, I need to fire off various sequences of pulses at
certain rotational positions, and these pulses have to be
as accurate as I can make them. In order to use a MCU, I'd
have to dedicate at least 1 single MCU to these timing events.

--
[100~Plax]sb16i0A2172656B63616820636420726568746F6E61207473754A[dZ1!=b]salax

 

[Tobias Weingartner]

In article <cue4dj$9fs$1@gnus01.u.washington.edu>, glen herrmannsfeldt wrote:

Tobias Weingartner wrote:

Anyways, I've been trying to figure out a circuit/program in verilog
that coorelates two serial bit streams to a in-memory representation
of the two bit-streams, and outputs the current "location". I'm
not even sure what to call this type of circuit, but bit-stream
correlator seems about right.

I am a little unsure what you are asking, but for aligning
character strings, possibly including insertions and deletions,
dynamic programming algorithms, and systolic array
implementations of such algorithms work very well.

Not really. Basically, think of it as two signals off of an encoding
wheel. At each position we have eithr a high or a low on either
of the two lines. The simplest would be to have an encoder where
one line is always low, and the other line would be high from 0 deg
to 1 deg.

The in-memory representation is based on a per-degree basis. It
would basically be:

000000....010...0000 (360 positions)
000000....000...0000 (360 positions)


This would take 360/2 degrees on average to sync up. Using some
heuristics or variables, we could likely stay synched to a signal
such as this as long as the variance between sync points is not too
great. Of course, the above is not the best waveform to have wrt
synching up quickly, and staying synched up.

A better one may be to have one signal alternating on a per-degree
basis (01010101...0101), and the other having 6 high positions,
with the 0 degree being 1 long, the 60,300 degree being 2 long, the
180 being 3 long, and the 120,300 being 5 long. We can now synch
up to our signals a lot quicker, on average less than 80 degrees
of a rotation.

If you don't need insertions and deletions, finite state
automatons are pretty good if you can preprocess the pattern
(is that what you mean by in-memory representation) into a
state table.

There are books on dynamic programming, systolic arrays,
and finite state automatons, but maybe not all in one book.

This might be possible, at the current time I'm not sure. I have
a circuit that gives me a high at each rotational position when
they match (360 bits wide, bit-wise XNOR, pushed through a 360
bit-wise AND), but I'd then need to figure out how to shift/rotate
these matches such that I get a longest consecutive string of 1's
in any one position of the bit-string. (Not sure if I'm describing
this well)

I'm going to try and describe what I mean. Assume you have 2 inputs
from an rotary encoder. We're going to try and use a memory
representation that covers 10 degrees for each position (36 characters
so they dont need to wrap here). We'll assume that one waveform is
10 degrees high, 10 degrees low, with the 0 mark being 30 degrees low.
The second waveform will be something a little different.

Wave 1: 000101010101010101010101010101010101
Wave 2: 010000011100001111000000011111000000

Now assume that we have 2 inputs of the waveform. If we take the XNOR
of each waveform at a point in time, with every location of the memory
and then AND each of these, we get all possible matching points of the
input to the waveform stored in memory. If there is only 1 point, we
have synch. If not, we need to wait until consecutive matchings give a
strings of 1's (matches) offset by one in the direction of rotation.

Input 1: high, Input 2: low

Wave 1: 000101010101010101010101010101010101
Wave 2: 010000011100001111000000011111000000
XNOR 1: 000101010101010101010101010101010101
XNOR 2: 101111100011110000111111100000111111
AND 12: 000101000000010000000101000000010101

As you can see, with the inputs being (1: high, 2: low), we have really
only 8 rotational positions we could be in. The next time either input
changes, we do another matchup, and we again have a number of positions
we can be in.

Input 1: high, Input 2: high

Wave 1: 000101010101010101010101010101010101
Wave 2: 010000011100001111000000011111000000
XNOR 1: 000101010101010101010101010101010101
XNOR 2: 010000011100001111000000011111000000
AND 12: 000000010100000101000000010101000000

This time we have 7 matches, 7 rotational positions we could be in. Now
we take the first and the second, and we get:

#1 AND 12: 000101000000010000000101000000010101
#2 AND 12: 000000010100000101000000010101000000

We know that the second one is a rotation of the first, in other words,
there are 1 ones above that match up. In our case, it's shifted between
1 to 3 positions. Anyways, what I was thinking was that after certain
number of matchings, you would get a strings on "1's" that would follow
the positions in the memory array just like the current position of the
rotary encoder.


Not sure if this helps any? Am I going about this the wrong way?

--
[100~Plax]sb16i0A2172656B63616820636420726568746F6E61207473754A[dZ1!=b]salax

 

[glen herrmannsfeldt]

Tobias Weingartner wrote:
(snip)

Not really. Basically, think of it as two signals off of an encoding
wheel. At each position we have eithr a high or a low on either
of the two lines. The simplest would be to have an encoder where
one line is always low, and the other line would be high from 0 deg
to 1 deg.

The in-memory representation is based on a per-degree basis. It
would basically be:

000000....010...0000 (360 positions)
000000....000...0000 (360 positions)

This would take 360/2 degrees on average to sync up. Using some
heuristics or variables, we could likely stay synched to a signal
such as this as long as the variance between sync points is not too
great. Of course, the above is not the best waveform to have wrt
synching up quickly, and staying synched up.

A better one may be to have one signal alternating on a per-degree
basis (01010101...0101), and the other having 6 high positions,
with the 0 degree being 1 long, the 60,300 degree being 2 long, the
180 being 3 long, and the 120,300 being 5 long. We can now synch
up to our signals a lot quicker, on average less than 80 degrees
of a rotation.

If you don't need insertions and deletions, finite state
automatons are pretty good if you can preprocess the pattern
(is that what you mean by in-memory representation) into a
state table.

There are books on dynamic programming, systolic arrays,
and finite state automatons, but maybe not all in one book.

This might be possible, at the current time I'm not sure. I have
a circuit that gives me a high at each rotational position when
they match (360 bits wide, bit-wise XNOR, pushed through a 360
bit-wise AND), but I'd then need to figure out how to shift/rotate
these matches such that I get a longest consecutive string of 1's
in any one position of the bit-string. (Not sure if I'm describing
this well)

I'm going to try and describe what I mean. Assume you have 2 inputs
from an rotary encoder. We're going to try and use a memory
representation that covers 10 degrees for each position (36 characters
so they dont need to wrap here). We'll assume that one waveform is
10 degrees high, 10 degrees low, with the 0 mark being 30 degrees low.
The second waveform will be something a little different.

Wave 1: 000101010101010101010101010101010101
Wave 2: 010000011100001111000000011111000000

(snip)

OK, I think the FSA will do it. It won't determine the
best code, though, but it will do the match once you have found
it, using a fairly small look-up table and register.

log4(360) rounds up to 5, so you need at least five base four
digits to represent a position. You then need the 360 unique 5
digit base four numbers that overlap by four digits. The state
table will have slightly less than 360*5 states, each state
represented by an 11 bit binary number. It might be that such a
set of base 4 numbers doesn't exist and you have to go to six
digits, but I think five will work. The lookup table is then
7200 by 13 bits, not so big for FPGA's with block RAMs.
Each step you index the table with the current state and the
input from the encoder.

I think then you can arrange the state table such that the
state value indicates directly the position.

That assumes you know the position of each code, separately from
the code itself, which you might not. For a two bit gray code
only two possible values are available at each position, in
which case you need log2(360), rounds to 9 digits, so you need
at least 9, and I will guess that 9 is enough.

The state table will be close to 3600*9*2 entries of 16 bits
each. Maybe a little big for an FPGA, but small for an external
ROM.

-- glen

 

[glen herrmannsfeldt]

glen herrmannsfeldt wrote:
(snip)

I'm going to try and describe what I mean. Assume you have 2 inputs
from an rotary encoder. We're going to try and use a memory
representation that covers 10 degrees for each position (36 characters
so they dont need to wrap here). We'll assume that one waveform is
10 degrees high, 10 degrees low, with the 0 mark being 30 degrees low.
The second waveform will be something a little different.

Wave 1: 000101010101010101010101010101010101
Wave 2: 010000011100001111000000011111000000

(snip)

OK, I think the FSA will do it. It won't determine the
best code, though, but it will do the match once you have found it,
using a fairly small look-up table and register.

log4(360) rounds up to 5, so you need at least five base four digits to
represent a position. You then need the 360 unique 5 digit base four
numbers that overlap by four digits.

For the complete set of n digit base b numbers, it seems that the
math is well understood.

http://mathworld.wolfram.com/deBruijnGraph.html

is one explanation, and a google search for deBruijn or "de Bruijn"
should find them.

For 360, which is less than the full set, I believe it can also
be done. If you want n-1, though, it might not be possible.

deBruijn will give you a 512 digit or 1024 digit circular base 2
or base 4 number, and you need to splice it together at 360 digits.

-- glen

 

[Jonathan Bromley]

On Thu, 10 Feb 2005 00:29:50 +0000 (UTC),
weingart@cs.ualberta.ca (Tobias Weingartner) wrote:

Anyways, I've been trying to figure out a circuit/program in verilog
that coorelates two serial bit streams to a in-memory representation
of the two bit-streams, and outputs the current "location". I'm
not even sure what to call this type of circuit, but bit-stream
correlator seems about right.

I didn't understand this at all, but...

Not really. Basically, think of it as two signals off of an encoding
wheel. At each position we have eithr a high or a low on either
of the two lines. The simplest would be to have an encoder where
one line is always low, and the other line would be high from 0 deg
to 1 deg.
[snip]

Is this *really* a mechanical encoder, and therefore fairly slow?
If so, I may have some good ideas for you. If the pulses from
the "code wheel" are at a rate comparable with the system clock,
then it's harder.

This might be possible, at the current time I'm not sure. I have
a circuit that gives me a high at each rotational position when
they match (360 bits wide, bit-wise XNOR, pushed through a 360
bit-wise AND), but I'd then need to figure out how to shift/rotate
these matches such that I get a longest consecutive string of 1's
in any one position of the bit-string. (Not sure if I'm describing
this well)

That's clear enough. I'm not quite sure why you are locked to
only 360 points, though - more resolution is usually better!

[snip description of ingenious technique]

That sounds fairly sensible, although there's quite a bit of
implementation detail to sort out. As I hinted above, the
killer question is the maximum speed of your "encoder" pulses
relative to the available system clock frequency.

~~~~~~

About fifteen years ago I independently "invented" a variant on
this theme that, I think, works a little better than yours.
I suspect it wasn't original at all, although I have found
no references to the idea (except for one partial implementation,
used on Unimation's Puma robots in the mid 1980s for index
seeking). In "my" scheme, the encoder has two tracks: a
clock track of the traditional kind (probably picked up using
a quadrature detector, so that you can also sense direction)
and an index track. Most existing encoders have such an
index track giving just one pulse per rotation, so it's
easy to modify them to have a rather different index track
carrying a pseudo-random binary sequence. If the clock
track has at most (2^N)-1 pulses, then you can build an
index sequence that allows you to locate the absolute
position of the encoder after a movement of only N pulses.

The implementation is straightforward enough:
a) using transitions of the encoder's clock track as
shift-enable for an N-bit shift register, clock in
N pulses from the index track - these are now stored
in the N-bit shift register ready for comparison
b) Using the fast system clock, run an N-bit pseudo-
random counter and an N-bit binary counter in parallel
c) When the P-R counter matches the index-track shift
register, copy the binary counter into a "current
position" register
Now you're in sync, and staying that way goes like this:
d) On every transition of the encoder's clock track...
* increment/decrement both the binary counter and
the PRBS counter
* shift the index shift register appropriately
* check you're still in sync by comparing the index
shift register with the P-R counter
* if in sync, update "current position" from the
binary counter; if not, go back to (b) and/or
flag an error

Lots of details missing here, of course - in particular,
if your encoder is to be bidirectional, then the index-
track shift register is not quite so simple, and you
also have to work out how to make your P-R counter
go backwards.
--
Jonathan Bromley, Consultant

DOULOS - Developing Design Know-how
VHDL, Verilog, SystemC, Perl, Tcl/Tk, Verification, Project Services

Doulos Ltd. Church Hatch, 22 Market Place, Ringwood, BH24 1AW, UK
Tel: +44 (0)1425 471223 mail:jonathan.bromley@doulos.com
Fax: +44 (0)1425 471573 Web: http://www.doulos.com

The contents of this message may contain personal views which
are not the views of Doulos Ltd., unless specifically stated.

 

[Tobias Weingartner]

Jonathan Bromley wrote:

On Thu, 10 Feb 2005 00:29:50 +0000 (UTC),
weingart@cs.ualberta.ca (Tobias Weingartner) wrote:

Anyways, I've been trying to figure out a circuit/program in verilog
that coorelates two serial bit streams to a in-memory representation
of the two bit-streams, and outputs the current "location". I'm
not even sure what to call this type of circuit, but bit-stream
correlator seems about right.

I didn't understand this at all, but...

What I mean, is that you put a representation of the waveform/bitstream
that the encoders output into the memory, and then have the logic sync
up the incoming stream of bits (level transitions) to a point in the in
memory representation.

In other words, we support arbitrary waveforms (ok, all 1's or 0's are
not really going to do it, as do other waveforms that do not have at
least 1 point in the cycle where they differ in their input), and have
the logic to sync up with them.

Is this *really* a mechanical encoder, and therefore fairly slow?
If so, I may have some good ideas for you. If the pulses from
the "code wheel" are at a rate comparable with the system clock,
then it's harder.

It is mechanical, and significantly slower than the system clock.

That's clear enough. I'm not quite sure why you are locked to
only 360 points, though - more resolution is usually better!

That is the resolution (maximum) for the encoders I'm working with.
The resolution I need is about 1/16th of a degree, and I'm working
to achieve this by using the system clock to slice up the "pulses"
of the incoming signal. Then using a rough 2nd order interpolation
I can try to minimize the jitter/error of the interpolated signal.

That sounds fairly sensible, although there's quite a bit of
implementation detail to sort out. As I hinted above, the
killer question is the maximum speed of your "encoder" pulses
relative to the available system clock frequency.

At the current time I doubt it will top 120KHz. Given I'm trying
to design for roughly xc2s50 (or possibly xc3s200 later), with a
clock of some 20MHz, it would seem I have loads of overhead.

About fifteen years ago I independently "invented" a variant on
this theme that, I think, works a little better than yours.
Most existing encoders have such an
index track giving just one pulse per rotation, so it's
easy to modify them...

If I allow modification of the input signal (encoder wheels) to
suit my wants, this excersize would be *very* simple. But
unfortunately, I needs to be "user" programmable...

--Toby.

 

[Tobias Weingartner]

glen herrmannsfeldt wrote:

glen herrmannsfeldt wrote:

OK, I think the FSA will do it. It won't determine the
best code, though, but it will do the match once you have found it,
using a fairly small look-up table and register.

log4(360) rounds up to 5, so you need at least five base four digits to
represent a position. You then need the 360 unique 5 digit base four
numbers that overlap by four digits.

For the complete set of n digit base b numbers, it seems that the
math is well understood.

http://mathworld.wolfram.com/deBruijnGraph.html

is one explanation, and a google search for deBruijn or "de Bruijn"
should find them.

-- glen

I've been trying to follow this, but whenever I think I get it, it
get's rather grey and fuzzy around the edges. Can you help me out
by telling what you are doing with the overlaping 4 digits?


Thank you,

Toby.

--
[100~Plax]sb16i0A2172656B63616820636420726568746F6E61207473754A[dZ1!=b]salax

 

[glen herrmannsfeldt]

Tobias Weingartner wrote:

(snip)

I've been trying to follow this, but whenever I think I get it, it
get's rather grey and fuzzy around the edges. Can you help me out
by telling what you are doing with the overlaping 4 digits?

Consider the following 100 digit decimal string.

00112233445566778899024680357913692581470482605937
15061627283849407395174185296308642097531987654321

If you consider the end wrapping to the beginning (as if you
write it on a cylinder) two character substrings represent
numbers from 00 to 99.

Any two consecutive digits represent a unique position.

If I understand it right, for any base b and number of digits n
it is possible to generate a b**n digit series containing all
possible n digit numbers in base b.

For fewer than b**n positions in many cases it is possible to
generate such a sequence, but maybe not in all cases. In the
sequence above, if you remove the first 0 you remove 00, and the
trailing one still forms 10.

However, it can be decoded somewhat simpler than the FSA I wrote
about, all you need is a shift register to store n consecutive
digits and a lookup table to find the position of that n digit
number. (The FSA is useful when many fewer than b**n codes are
in use, such as text string searching.)

I am not sure how many photodetectors you have on each track.
In the usual quadrature encoder there is one track alternating
zero and one, and two detectors shifted one half a bit spacing.
If you have those, I think you can decode base four reliably.

If you have one detector on each track they should be gray coded
such that one track or the other changes at each position but
not both. Only two possible codes are available at each
position, so it need to be base two. The same result as using
one for a clock (alternating zero and one) and one for data bits.

-- glen

 

[Tobias Weingartner]

glen herrmannsfeldt wrote:

However, it can be decoded somewhat simpler than the FSA I wrote
about, all you need is a shift register to store n consecutive
digits and a lookup table to find the position of that n digit
number. (The FSA is useful when many fewer than b**n codes are
in use, such as text string searching.)

Hmm... thank you. I'm going to have to digest and draw this idea
out a bit. It does look usefull, and possibly solves one of the
problems.

I am not sure how many photodetectors you have on each track.
In the usual quadrature encoder there is one track alternating
zero and one, and two detectors shifted one half a bit spacing.
If you have those, I think you can decode base four reliably.

Well, the detectors are not something I have control over. The
user of the module will program the ram bits telling us what the
waveforms look like.

If you have one detector on each track they should be gray coded
such that one track or the other changes at each position but
not both. Only two possible codes are available at each
position, so it need to be base two. The same result as using
one for a clock (alternating zero and one) and one for data bits.

Hmm... the edges of the signals are important because they determine
precisely the rotational position of the shaft. I'm going for 1/16th
of a degree resolution, with as much precision as I can get out of a
20MHz system clock. So on a 120KHz signal, that would be roughly 166
counts of the system clock (on the high end of rotation) per count of
the rotational input pulses. This gives me a precision of +/- 1/10th
of 1/16th of a degree (roughly) at steady state.

--
[100~Plax]sb16i0A2172656B63616820636420726568746F6E61207473754A[dZ1!=b]salax