Non repeating binary string for encoder?

[Mr RB]

Hi, I'm trying to make a low resolution linear encoder with one sensor. The sensor reads 1 "bit" either 0 or 1, for every 10mm of movement. So when the machine is moving it outputs a continuous string of reliable bits.

The goal is to know absolute position after reading N number of bits. Here are the two simplest examples;

N=2, determines position from ANY 2 bits;
00110     (encoder string)
00
 01
  11
   10
=4 positions 

N=3, determines position from any 3 bits;
0001110100    (encoder string)
000
 001
  011
   111
    110
     101
      010
       100
=8 positions

So it looks simple enough, the length, ie amount of bits is; (2^N)+(N-1);
2bits tested; 2^2 +1 = 4+1 = length 5
3bits tested; 2^3 +2 = 8+2 = length 10

So an 8bit system would allow 256+7 = length263 which should be long enough.

So, does anyone know the best way to generate the string, or if this is a commonly used system do you know the name for it? I found some grey encoders and other systems on google but none of them seem to be what I want.

I can write some software to brute force it, but it would be easier if there was a simple process or rules etc to generate the bit string.

Thanks!

 

[ericgibbs]

hi Roman,
I guess you are aware of the Gray Code.?

 

[crutschow]

It's not clear to me what you are trying to do. If it's a simple string of serial bits why can't you just do a binary add of the bits? Obviously I'm missing something.

 

[Mr RB]

Hi Eric, yes I know the grey code, but that is based on only 1 bit changing in the sample. As far as I can see that won't work here as the encoder moves linearly one new bit enters at one side and the previous bits from the last sample shift right or left to make room for the new bit.

Example;

0001110100    (encoder string)
     101
      010

In those 2 consecutive samples, all 3 bits have changed. Or is there some particular variation of grey code that works like this?

Hi Crutschow, the goal is to read each new bit as the machine moves, which is shifted into a shift register. So there are always 8bits in the shift register and the machine always knows where it is as that *particular* 8bit sample only exists in ONE place along the linear encoder. And int he event of a crash, the machine only needs to move 8bits (80mm) to recover and know absolute position again.

 

[crutschow]

OK, the light came on and I see what you are trying to do. The trick is to make a linear string of code such that the 8-bit register always has a unique code for anywhere on the string. That's an interesting concept. It's not apparent if there's a way to calculate the code string needed for that.

What about starting the string with eight 0's and a 1. Then add six 0's and 11, five 0's and 101, five 0's and 111, four 0's and 1001, four 0's and 1011, four 0's and 1101, four 0's and 1111, etc. ending with eight 1's. Not sure if that unambiguously gives all codes or avoids duplication.

 

[Mr RB]

Interesting! And thanks for the fast response.

I think with a very slight variation on your system it looks like a winner. Which is to increase the number of 1 bits each block;

On a smaller scale of N=4 that would be;
0001 0011 0111 0000 1111
which is logical, but unfortunately still has repeats?

N=4, seems to have repeats;
00010011011100001111
0001                
             0001    
        0111    
               0111
     
N=4, but ending after 16bits total;
0001001101110000
0001                
             000
        0111    
               0
(no repeats!)

That looks pretty good! It has a beautiful simplicity that should be easy to design for any amount of bits) and easy to decode as well. I like the fact that the number of 1 bits inthe 4bit sample tells you roughly how far left the sample is on the strip... Cool.

I just had a nightmarish hour of wading through Wiki pages on binary sequence algorithms, looking at every one and finally found the one I originally thought of using;
https://en.wikipedia.org/wiki/De_Bruijn_sequence (1946)

It gives the same sequences as I posted in post#1, (so my system was DeBruijn) and the DeBruijn's N=4 solution looks like this;
0000 1111 0110 0101
which can be repeated circularly, so will give all possible 16 samples along the machine travel.
so max samples is (2^N) = 2^4 = 16

Your sequence (which I did not find on Wiki by the way!) is;
0001001101110000
0000 (last possible sample)
which only gives 13 samples as; max samples = (2^N)-(N-1)

But even with the limitation that your system has a few less samples total for N, so yours would give 249 positions for an 8bit encoder rather than DeBruijn's 256 positions for an 8bit encoder, I still like the bulletproof ease of generating the encoder data for your system.

Also I like the fact that the number of 1's in your system tells the rough left/right position, that is nice and might be good for error detecting. With DeBruijn as it goes left->right the bits just get more random looking which would not be easy to detect and won't help much for error checking... And DeBruijn is a bit of a pain to generate the data for...

Anyway thanks Crutschow, it looks like you hit the nail on the head! I can live with a few less counts on the encoder and go with the ease of generating the 8bit data like this;
00000001
00000010
00000100 (etc)
which suits me fine as it will go in a lookup table in C code.

(edit) Whoops! Darn it I just realised your system will only give 57 positions for 8bits, as I just tested and it gives; max samples = Nsquared-(N-1) = 8*8 -7 = 57

That hurts! To get the 200+ samples I need will require 15bits to get me 211 samples...

 

[crutschow]

Well, after some thought I did realize that it was likely my scheme would have a problem with duplicate codes.

The best I can think of is to do a sequence with two zeros as a separator and 6 bits of code. Avoiding all 6-bit codes with two zeros in a row leaves 52 unique 6-bit codes. This 6-bit code can appear in three different positions in the 8-bit shift-register giving, I think, a total of 156 unique positions.

So you may have to go with DeBruijn's sequence after all, if you want to get a full 256 positions for an 8-bit code.

 

[Mr RB]

Hmm, I'm not sure I get your math?
OK, (assuming it is aligned to the boundary) so each 8bit sample must have 00cccccc where cccccc is a 6bit code with 52 permutations? So the maximum length of encoder data is 52 segments, each 8bit long; = 416 bits... maximum perfect (Debruijn) is 256 bits?

I think to accurately detect the 00 means it must have a 1 on both sides, as if there is a 0 on either side it can't be detected as you don't know if the zero is part of 00 or part of the 6digit code...

So doesn't the pattern become 001cccc1 (or 1001cccc)? That only gives 16 codes and 6 are illegal as they contain 00 pairs so there are 10 valid codes. So I get the maximum length is now 10*8 = 80 bits.

I looked at implementing DeBruijn and it's less attractive than its "perfect" nature implies. There is a hassle of writing code to generate the 256 bytes of ugly data, then copy it into the C code with no errors and no visible way to check it, then try to create artwork for 256 stripes in a drawing program with no errors, then if it's printed out in segments they have to be assembled with no errors to make the 2metre long strip etc etc. Real world implementation is all a total pain!

I'm now thinking it's better to stick with a system where each small segment is easy to understand, easy to check and easy to draw and print out, then live with the fact the machine needs to read a few more bits to get an absolute position!

Also it would be good if the code could be decoded by logic (by analysing its content structure), rather than needed a lookup table for every possible bit combination.

It looks like you could be onto something by using a symbol to signify and align each data segment, then data contents that can hopefully be decoded logically by looking at the incomplete start of one segment and the incomplete end of the previous segment...

As an example;
1001 (symbol, which is 00 that cannot appear anywhere else)
____cccccccc (data, can be any combinations with no 00, so is 256-27 I think = 229 combinations, but still needs a lookup table?)

I'm still not sure of a good way to logically decode a segment when it is misaligned;
ccc1001ccccc etc?

 

[crutschow]

Hmm, I'm not sure I get your math?

Yes, after a second look my math was off. Your's looks correct.

It looks like a real dilemma between efficient code and code that's easy to decode.

Perhaps three zeros as a break with 7 or 8 data bits (leaving out the ones with 000) would give you sufficient points.

 

[Mr RB]

Thanks Crutschow I appreciate your input.

Currently I'm leaning towards something like your first idea, with data segments which are a bit like "PWM";

00 0000 0001 (first 10bit data segment)
00 0000 0011 (next segment)
00 0000 0111 (etc)...
00 1111 1111 (last segment, you can see the similarity to an edge-aligned PWM signal)
That gives 8 segments of 10 bits, 80bits of travel, and easy to decode as each segment boundary is decimal which is good for positioning as each segment boundary is now equal to 10cm travel on the machine.

In any read of 10 consecutive bits the boundary can be found logically as the point to the left of the (2 or more) zeros. And simple logic can be used to count the 1 bits, so no lookup table is needed.

Then (again based on your first idea) additional coding can be added by including a redundant bit on the next set of 8 segments;
00 0000 0101
00 0000 1011
00 0001 0111
00 0010 1111
00 0001 1101
00 0011 1101
00 0111 1101
00 1111 1101

I'm not sure if that's perfect but it does allow another 80 bits and still relatively easy decoding.

You can see common similarities there where it should be easy enough to detect the 00 boundary, then the "PWM length" and finally the "group" bit which tells which of the three groups it is.