Subject:
|
Re: Barcodes & error detection
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Thu, 8 Sep 2005 02:31:06 GMT
|
Original-From:
|
Rob Roschewsk <[pabutusa@gmail.]Spamless[com]>
|
Viewed:
|
935 times
|
| |
|
|
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" <brdavis@iusb.edu>
To: <lego-robotics@crynwr.com>
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
|
|
Message is in Reply To:
 | | 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 (...) (19 years ago, 7-Sep-05, to lugnet.robotics)
|
16 Messages in This Thread:
 
- Entire Thread on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
