Post by thread:Binary Chain Codes

Hi all, I am now looking for a new linear position sensor for my robotics PIC application. I decided to leave the infrared LED to sensor link alone because of the inherent calibration problems. It turns out that LEDs degrade with time to the point that constant recalibration would be required. I am now exploring linear encoding for a more digital solution. I have come across a type of absolute position linear encoding called binary chain code which is a _non-repeating_ pattern of ones and zeros of length 2^N. In an N-bit code _any_ N-bit sequence appears only once in the entire 2^N pattern so you always know where your are. My sensor is a Texas Instruments TSL213. It is a 64x1 pixel array with a simple 64-bit shift register output. I can supposedly print my pattern on a mylar strip and encode away. I am asking you guys if anyone has experience with this type of position encoding especially with a PIC. Maybe one if you has some code written to deal with this. Thanks, Martin Kirk Arizona State University spam_OUTmlkTakeThisOuTasu.edu (602) 263-9270

>array with a simple 64-bit shift register output. I can supposedly print my >pattern on a mylar strip and encode away. I am asking you guys if anyone has >experience with this type of position encoding especially with a PIC. Maybe >one if you has some code written to deal with this. I haven't used that type of encoder but it sounds similiar to a standard rotary encoder, you might want to look at the application notes related to the rotary encoders. Did you find the information about the binary chain code in the application note s for the device or from some other source? If its from another source could you site the reference? I would be interested in hearing more about this project and how it t urns out. Walter Anderson .....khadfwKILLspam@spam@onramp.net

On Tue, 23 May 1995, Walter Anderson, C.D.P. wrote: > >array with a simple 64-bit shift register output. I can supposedly print my > >pattern on a mylar strip and encode away. I am asking you guys if anyone has > >experience with this type of position encoding especially with a PIC. Maybe > >one if you has some code written to deal with this. > > I haven't used that type of encoder but it sounds similiar to a standard rotar y > > encoder, you might want to look at the application notes related to the rotary > encoders. > > Did you find the information about the binary chain code in the application no te > s for > the device or from some other source? If its from another source could you si te > the > reference? I would be interested in hearing more about this project and how it t > urns > out. > > Walter Anderson > khadfwKILLspamonramp.net > Walter, The source is Electronics Now, October 1994. It was faxed to me from TI as an app. note for their TSL213 64x1 pixel array product. Martin Kirk Arizona State University .....mlkKILLspam.....asu.edu (602) 263-9270

{Quote hidden}>Hi all, > I am now looking for a new linear position sensor for my robotics >PIC application. I decided to leave the infrared LED to sensor link >alone because of the inherent calibration problems. It turns out that >LEDs degrade with time to the point that constant recalibration would be >required. > > I am now exploring linear encoding for a more digital solution. >I have come across a type of absolute position linear encoding called >binary chain code which is a _non-repeating_ pattern of ones and zeros of >length 2^N. In an N-bit code _any_ N-bit sequence appears only once in >the entire 2^N pattern so you always know where your are. > > My sensor is a Texas Instruments TSL213. It is a 64x1 pixel >array with a simple 64-bit shift register output. I can supposedly print my >pattern on a mylar strip and encode away. I am asking you guys if anyone has >experience with this type of position encoding especially with a PIC. Maybe >one if you has some code written to deal with this. > >Thanks, > >Martin Kirk >Arizona State University >EraseMEmlkspam_OUTTakeThisOuTasu.edu >(602) 263-9270 HP PhotoOptics has a complete line of positioning sensors and strips for this purpose. Doug Sellner Beach Tech 4131 Vincent Avenue South Minneapolis MN 55410 Voice (612) 924-9193 x 521 Fax (612) 926-1145 Internet: dsellnerspam_OUTembay.com

Martin Kirk wrote: [...] I am now exploring linear encoding for a more digital solution. I have come across a type of absolute position linear encoding called binary chain code which is a _non-repeating_ pattern of ones and zeros of length 2^N. In an N-bit code _any_ N-bit sequence appears only once in the entire 2^N pattern so you always know where your are. My sensor is a Texas Instruments TSL213. It is a 64x1 pixel array with a simple 64-bit shift register output. I can supposedly print my pattern on a mylar strip and encode away. I am asking you guys if anyone has experience with this type of position encoding especially with a PIC. Maybe one if you has some code written to deal with this. --------------------------------------------------- Hi all, it seems, that the above problem has something to do with 'random bit generation'. an (electric) example: - take a shift register, length 8 bit (bit0..bit7), - the content of the shift register MUST not be b'00000000'! - exor proper bits, e. g. bit7 xor bit6 xor bit4 xor bit2 - shift left this result bit into the shift register with each shift you get a new 'random' byte. the principle can be expanded to the desired length. the byte sequence will repeat after 2^N-1 shifts (when xor-ing the correct bits), here it is after 255 shifts. your problem will be to read 8 following bits from the sensor and recalculate the order number in the range of 0..255. An unefficient way would be to initialize the shift reg. with b'00000001', and call the shifting procedure repeatedly until the result matches with the sensor byte. the number of calls is equal to the position. it is easy to calculate / compare with the following random number, but I do not know an algorithm to calculate the preceeding value. when using only 255 positions you could create a lookup-table, too :-) I use this shifting principle for PIC-based software generation of random numbers, it is also part of an application note. By the way, what exactly does the TSL213? Siggi Siegfried Grob, | student of electrical engineering, | university of ulm, germany | e-mail: @spam@siegfried.grobKILLspamstudent.uni-ulm.de | tel&fax: +49 731 25148 | --------------------------------------------------'

Hi all, in the meantime, I thought about my last mail and came to the conclusion that is as simple to calculate the preceeding random number as the following one. an example: 1 0 0 1 0 1 1 0 the actual random number ~ ~ ~ ~ 1*0 * 1 * 1 = 1 xor bit7,6,4,2 the next: 1 <- 0 0 1 0 1 1 0 1 shift left the new bit ~ ~ ~ ~ 0* 1 * 1 * 1 = 1 xor bit 7,5,3,0 the last: 1 0 0 1 0 1 1 0 -> 1 shift right this bit the xor-ing is like a parity-calculation, the 4 old bits and the new bit always have even parity. so it is always possible to calculate a missing bit from the other four. so if the last position code is known, calculate the following random numbers out of the last position code until matching to get the relative forward movement - or if not matching after a limited number of calculations, calculate the preceeding random numbers until matching to get the relative backward movement. This all is a theoretical consideration. I did not test/simulate that yet. Did everybody understand that? By the way, what exactly does the TSL213? Siggi Siegfried Grob, | student of electrical engineering, | university of ulm, germany | e-mail: KILLspamsiegfried.grobKILLspamstudent.uni-ulm.de | tel&fax: +49 731 25148 | --------------------------------------------------'

> > I am now exploring linear encoding for a more digital solution. > > I have come across a type of absolute position linear encoding called > > binary chain code which is a _non-repeating_ pattern of ones and zeros of > > length 2^N. In an N-bit code _any_ N-bit sequence appears only once in > > the entire 2^N pattern so you always know where your are. > > Is it better than standard way? I mean few parallel sensors and Gray coded > strip. Depends, the strip is only 1 bit wide and for a 16 bit resolution requires a sense head 16 bits LONG not wide so may be possible to fit into smaller spaces. The problem that is solved with gray codes (only one bit changes at a time) is not covered with the non repeating pattern code, you would need to either have one more index track to indicate the read position or over sample the code (16 x 4 = 64 ccd) and do edge detection and then read the center of the bit position on all the code bits, remembering that you can have a sequence of N (16) 1 bits which does make edge detection quite difficult. -- Kalle Pihlajasaari RemoveMEkalleTakeThisOuTdata.co.za Interface Products Box 15775, Doornfontein, 2028, South Africa +27 (11) 402-7750 Fax: +27 (11) 402-7751

Hi all, I have been off the air for a few days. First I will respond to S_GROB's question: > By the way, what exactly does the TSL213? The TSL213 is a 64x1 pixel sensing array. It comes in an 8-bit package with a long window exposing the 64 pixels. When given the SI (start integration?) signal it ends the previous integration and transfers the accumulated charge from pixel #1 to the output buffer. 65 successive clocks will step the output through all 64 pixels and get ready for the next sweep. The output is analog but when the integration time and light intensity are selected correctly the output meets digital 1/0 specifications. Now for Jaroslaw Lis' question: >Is it better than standard way? I mean few parallel sensors and Gray coded strip. Bear in mind that I have not used part yet. I am designing to it now. From my understanding the beauty of this approach is that it gives an absolute position at all times. There is no position count to keep track of because the non-repeating code always corresponds to an absolute position on the strip. Also the TSL213 costs about $5 where the encoders I have looked at are in excess of $20 each. I need 8 of these sensors per design so ... do the math. One thing to keep in mind. The 64x1 array will be used to oversample the coded strips. I figure I can use a 3-bit Binary Chain Code which gives 8 (2^3) bits in the code. Precisely the code I will use is: 00010111 ^^^ [ ] <-- first window There are exactly six 3-bit windows on to this pattern: 000 001 010 101 011 111 It works out that one gets 2^n - n + 1 distinct windows on any n bit code. If I oversample at 16 pixels per bit I can detect the starting position of the 3-bit code to within one of 16 positions. That give a total of 96 (6x16) positions I can resolve. I only need about 70. If my edge detection is a little too noisy I can go to a 4-bit code and get greater resolution. I welcome feedback here. I would rather spot a colossal boo boo before I have hardware, but I think this will do what I want it to do. Absolute position is all I need for this application. Thanks for all the discussion of this topic. Martin Kirk Arizona State University spamBeGonemlkspamBeGoneasu.edu (602) 263-9270

Martin Kirk wrote some days ago: > Hi all, > I have been off the air for a few days. First I will respond to > S_GROB's question: > > By the way, what exactly does the TSL213? > > The TSL213 is a 64x1 pixel sensing array. It comes in an 8-bit > package with a long window exposing the 64 pixels. When given the SI > (start integration?) signal it ends the previous integration and > transfers the accumulated charge from pixel #1 to the output buffer. 65 > successive clocks will step the output through all 64 pixels and get > ready for the next sweep. The output is analog but when the integration > time and light intensity are selected correctly the output meets digital > 1/0 specifications. > If I understand you right, the TSL213 is some sort of CCD array, or a kind of analog shift register of 64 pixels. You can shift out each pixel sequen- tially and convert its analogue value into a digital bit. So you get a sequence of 64 bits representing 64 (bright or dark) pixels? you continued: (...) {Quote hidden}> One thing to keep in mind. The 64x1 array will be used to > oversample the coded strips. I figure I can use a 3-bit Binary Chain > Code which gives 8 (2^3) bits in the code. Precisely the code I will use > is: > > 00010111 > ^^^ > [ ] <-- first window > > There are exactly six 3-bit windows on to this pattern: > > 000 > 001 > 010 > 101 > 011 > 111 > > It works out that one gets 2^n - n + 1 distinct windows on any n > bit code. and if you add '00' (or in general the first n-1 bits) you get a full range of 2^n patterns: 0001011100 ~~ 000,001,010,101,011,111,110,100 :-) continuing: > > If I oversample at 16 pixels per bit I can detect the starting > position of the 3-bit code to within one of 16 positions. That give a total > of 96 (6x16) positions I can resolve. I only need about 70. If my edge > detection is a little too noisy I can go to a 4-bit code and get greater > resolution. again, if I understand you right, one bit of the Binary-Chain-Code is represented by 16 pixels? I. e. the pattern '000' is equal to 3*16=48 zeroes in the pixel array. And as an 48-pixel-array can be positioned at 16 locations in a 64 full-array, you think to resolve these 16 locations? In your example you thought to find one of your six patterns in the pixel array to get a rough position, and to locate this pattern inside its 16-location-bandwith to get the exact position!? ------------------------ You said, that you need a resolution of about 70 positions. But what is the unit, in which you need your position? Do you need to know the position as exactly as one pixel width or is your position-unit a multiple of pixels? As I thought to read out of your lines, you want the maximum possible reso- lution, based on a single pixel. If yes, then it is a hard job to do! Theoretically, one bit of the binary- chain-code is represented by 16 pixels, but reality will not be as digital as you like it, it tends to be `fuzzy'. What I want to say is, that a bit can be read as 15 or 17 pixels, too, which must not confuse your position- calculation-routine! So I would suggest one of the two following methods, based on the calculation of random numbers I described earlier: the unit: 1 position unit = 8 pixels ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ resolution: 8 bit = 255 (or 256) positions. divide the 64 pixel array into 8 pieces of 8-pixel-groups. one 8-pixel-group represents one bit (8-times-oversampling). the 64 pixel array is declared valid, if the middle five pixels of an 8-pixel-group are the same. (the change between a 1- and a 0-bit occurs in the outer area of an 8-pixel-group, so no error will occur, if a bit is represented by 7 or 9 pixels instead of 8) if the 64 pixel array is valid, you get an 8-bit-position-code out of the 8 pieces. now calculate your position out of this position-code (trial-and-error or look-up-table) example: an 'x' as well as an 'o' represents a pixel. Just to show 8-pixel-groups. pixel array: xxxxxxxxooooooooxxxxxxxxooooooooxxxxxxxxooooooooxxxxxxxxoooooooo valid pattrn: ######## ################ ######### \______/\______/\______/\______/\______/\______/\______/\______/ read as: 1 0 1 1 0 0 1 0 inval. patt.: ######## ################ ######### \______/ ^^^^^ the middle four pixels are not the same the unit: 1 position unit = 1 pixel ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ this is max. resolution unit, resolution: 7 bit = 127*8 positions again, one 8-pixel-group represents one bit (8-times-oversampling). if pixel00..pixel04, pixel08..pixel12 and so on are equal each (no change inside a 5-pixel-group) then FineResolution:=0 else if pixel01..pixel05, pixel09..pixel13 and so on are equal each (no change inside a 5-pixel-group) then FineResolution:=1 else if pixel02..pixel06, pixel10..pixel14 and so on are equal each (no change inside a 5-pixel-group) then FineResolution:=2 ... else if pixel 07..pixel10 ... then FineResolution:=7 now build up a 7-bit-position-code out of the valid nibbles and calculate the RoughResolution out of it. ExactPosition:=RoughResolution*8 + FineResolution (same) example: pixel array: xxxxxxxxooooooooxxxxxxxxooooooooxxxxxxxxooooooooxxxxxxxxoooooooo valid pattrn: ######## ################ ######### 1. run: \______/\______/\______/\______/\______/\______/\______/ result: ^^^^^ pixel00..pixel04 are not the same => invalid 2. run: \______/\______/\______/\______/\______/\______/\______/ result: ^^^^^ pixel01..pixel05 are equal => FineResolution:=1 position-code: 1 0 1 1 0 0 1 exact position := RoughResolution (1011001)*8 + FineResolution Ist doch ganz einfach, oder? [really simple, isn't it?] I am sure that not everybody has understood this possible solution of a really fascinating problem, but it is sufficient if at least Martin has :-) I think, that my method elliminates all problems, which can occur due to errors at the edge from a 1-bit and a 0-bit. The solution is a question of resolution and algorithm and not really a problem of hardware, I think. But if you have a fast and "tough" PIC, this should not be a big problem, too. My 16C84 also survived after a rotated insertion into its socket. So it is almost unbelievable, that a fried of mine killed his 16C84. Maybe some 16C84 are tougher than others? Siggi Siegfried Grob, | student of electrical engineering, | university of ulm, germany | e-mail: TakeThisOuTsiegfried.grobEraseMEspam_OUTstudent.uni-ulm.de | tel&fax: +49 731 25148 | --------------------------------------------------'