Subject:
|
Re: Barcodes & error detection
|
Newsgroups:
|
lugnet.robotics
|
Date:
|
Thu, 8 Sep 2005 03:11:53 GMT
|
Original-From:
|
Steve Baker <sjbaker1@airmail{AntiSpam}.net>
|
Viewed:
|
1023 times
|
| |
|
|
Brian Davis wrote:
> 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').
Well, there is a sharp distinction between error DETECTION and error CORRECTION.
It's also important to characterize the errors you are getting.
Are you getting single bit errors or multi-bit errors?
You will certainly need to use more bits in order to correct or even detect
errors.
Generally - if you need to only DETECT an error - you'll need to add one
extra bit. If you want to CORRECT an error - you'll need more than one
extra bit.
For single bit error detection, your parity scheme is pretty much the best
you can do.
> 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).
Yep. That's the best you can do.
> 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?
Not without using more error bits.
To correct an error is difficult for very small code words...for large
blocks of bits, there are simple and cheap ways to do it.
Suppose your useful data is a 5 bit code (32 possibilities). There
are five ways this can go wrong. So you know that it's going to take
more than two bits to correct the error because two bits could only
identify an error in four ways. It's actually worse than that because
the error could be in the check bit - so 5 data bits needs a MINIMUM
of three check bits - making a total of 8 bits.
There are fancy mathematical ways to think about this - but in the end,
the simplest way to understand it is to make 32 codes - each of which
is different from all the other codes by MORE than one bit. With 256
different binary numbers available, you can do this...although it may
take you a while to figure it out. (Read up on 'Huffman Coding' for
the theoretical background). When you read a code, you can compare
it to a list of correct codes and if it doesn't match any of them,
find the code that differs from the one you read by only one bit.
Since all the codes differ from each other by MORE than one bit,
you can be sure to know which one you should have read.
But this is something of a mixed blessing.
If there was a probability of X% of getting a single bit error in
5 bits, you'll have an (X * 8/5)% chance of getting a single bit
error in the new system. That's OK because you can correct any
single bit error. But the 3 bit error correction scheme can't
correct two-bit errors. So whilst you may have had a very remote
chance of getting a 2 bit error, you've now dramatically increased
that chance by increasing the number of bits you have to read.
Sometimes, adding single bit error correction can actually worsen
your overall error rate.
Knowing as you do that errors are always of the form 1==>0 and
never 0==>1, you can possibly get by with fewer than three error
bits - but I kinda doubt it.
So, for example, suppose you have the code for decimal '20' with
32 possible codes and 3 error bits (8 bits total).
That's 00010100. So to ensure that you don't have any codes that
differ by just one '1' bit, you'll have to avoid using these bit
patterns for other codes:
00010101
00010110
00010000
00011100
00000100
00110100
01010100
10010100
...because if you used one of those - and there was a single
1==>0 error, you wouldn't be able to tell whether you had a
'20' with a bad bit - or the other number (possibly with a
bad bit).
As it is, if you see any of those eight codes (or the original
20 code) - then you'll be able to say that you definitely have
a 20 because you know the results of all possible 1 bit errors.
---------------------------- Steve Baker -------------------------
HomeEmail: <sjbaker1@airmail.net> WorkEmail: <sjbaker@link.com>
HomePage : http://www.sjbaker.org
Projects : http://plib.sf.net http://tuxaqfh.sf.net
http://tuxkart.sf.net http://prettypoly.sf.net
-----BEGIN GEEK CODE BLOCK-----
GCS d-- s:+ a+ C++++$ UL+++$ P--- L++++$ E--- W+++ N o+ K? w--- !O M-
V-- PS++ PE- Y-- PGP-- t+ 5 X R+++ tv b++ DI++ D G+ e++ h--(-) r+++ y++++
-----END GEEK CODE BLOCK-----
|
|
Message has 1 Reply:
 | | Re: Barcodes & error detection
|
| (...) Agreed, and, for this application, the bit overhead to allow on-board correction is probably just not worth it. After all, if an error is detected, the forklift can always back up and try to read the barcode again. (...) Almost exclusively (...) (19 years ago, 8-Sep-05, to lugnet.robotics)
|
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
This Message and its Replies on One Page:
- Nested:
All | Brief | Compact | Dots
Linear:
All | Brief | Compact
|
|
|
|
