Re: Barcodes & error detection

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: <[email protected]>    WorkEmail: <[email protected]>
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-----