Re: Barcodes & error detection

Thanks, you actually made me pull out one of my old comp sci texts :-)

I remembered studying this stuff many moons ago ....

Error detecting requires a "distance" between codes of at least TWO ... what 
this means is to detect a single bit error each code must be different from 
the other code by TWO Bits .... simple example a code set that consists of 
just "00" and "11" ... we know if we receive "01" or "10" we must have 
received an error but we don't know what the intended code was.

For error correcting codes the "distance" must be raised to 3 bits, so for 
our simple example our two codes are now "000" and "111" so if we encounter 
a single bit error we could receive "001", "010", "011", ... "110" the 
difference now is if we assume only a single bit error we can derive from 
say "001" that the last "1" is the error bit and the intended code was "000"

It is also said that a code with a distance of three is "single error 
correctable" and "double error detectable" however you can't distinguish 
from the two!

The most popular error correcting code is  "The Hamming Code" 
http://en.wikipedia.org/wiki/Hamming_code basically you add 3 check bits to 
4 data bits for a total of 7 bits per symbol.

--> Rob


----- Original Message ----- 
From: "Brian Davis" <[email protected]>
To: <[email protected]>
Sent: Wednesday, September 07, 2005 1:38 PM
Subject: Barcodes & error detection


   Some of you at BrickFest may have seen Gus, a small robotic forklift that 
was
one of my GBC modules. Gus had two problems at BrickFest. First, while the
codereading task was 98% accurate, that still means on average once every 16
circuits of the course Gus would mis-read a barcode, resulting in it doing..
something inappropriate (leaving a crate on the table, pushing over or
destroying a structure, or in at least one instance making inappropriate
advances on a member of the audience). Second, after a while the 
line-following
got rough, resulting in 180 degree turns on the line.
   To increase reliability I wanted to add error-detection. Suggestions? 
Right
now the codes are made of bits (black=1 white=0) with each bit preceeded by 
a
highly reflective strip (reflective thin tape used to repair flexible 
ducts -
great stuff, especially if they'd ever produce it without printing). Since 
each
bit is preceeded by a reflective flag, I can use variable length 'words' 
(i.e. -
'0' is distinguishable from '00').
   It turns out the errors seem to only be of the form of a '1' (black)
mistakenly read as a '0' (white). Currently I can check by making sure any 
code
read has "even parity" (an even number of '1's), and not using the odd 
parity
codes. But that means of the 30 codes it can currently read (up to 4 bits 
long)
I can only use 15 (the even parity ones).
   Question (finally): given the unique nature of the errors (only mistakes 
'1's
for '0's, never the converse) is there any better error-detecting (or, even
better yet, error-*correcting*) coding system I can use? There's plenty of
options, but I want something that minimizes the number of complexity of the
barcodes (I've got to make them by hand... no, I've not made them from LEGO
tiles *yet*, it's just tape on cardboard).

   And hey, while we're on the subject... any suggestion for tasks Gus 
should
try to accomplish? Loading/unloading crates on a conveyor and wharehousing
crates, as well as detecting when it has a full or empty crate, are either
implemented or planned. When I can figure out how to position the train
accurately enough I'll work on loading crates on the train.

-- 
Brian Davis