Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

Background: 3 of 9 Barcode Alphabet

A simple syntax for 3 of 9 bar codes

What is the formula behind the alphabet and digits in a 3 of 9 bar code?

For example, ASCII has a relatively clear arrangement. Numbers start at 33, capitals at 65, lowercase at 97. From these starting points you can infer the ASCII code for any number or letter. The start point for each range is also a multiple of 32 + 1.

Bar codes seem random and lacking sequence. If we use the syntax from the second link, this is the first six characters in 3 of 9:

A 100-01
B 010-01
C 110-00
D 001-01
E 101-00
F 011-00

I see no pattern here; what is it? I'm as much interested in the designer's intended pattern behind these as I am in someone devising an algorithm of their own that can give you the above code for a given character based on its sequence.

I struggled with where to put this question; is it history, computer science, information science? I chose Programmers because a StackExchange search had the most barcode hits here, and because I wanted to specifically relate it to ASCII to explain what sort of formula/explanation I'm looking for.


Update

For the curious, here's the full list of all basic characters in Code 39: http://jsfiddle.net/b9chris/LnX2e/2/

(the source lines are taken from my C# barcode lib)

You'll notice that the simplified syntax proposed can confuse the issue a bit, because it might imply that every character is a 5-bit number with a dash position. The final 4 characters have numerous dashes (wide gaps). Really, these codes are best thought of as 9-bit numbers that happen to have most odd bits set to 0 for the majority of symbols. Here they are as 9-bit numbers: http://jsfiddle.net/b9chris/LnX2e/1/

share|improve this question
    
I didn't read the wiki but after seeing your example I'd say the next would be G 111-01 –  Pieter B Apr 8 '13 at 10:19
    
Sadly it is G 000-11. –  Chris Moschini Apr 8 '13 at 16:40

3 Answers 3

up vote 8 down vote accepted

I don't know if this is the correct explanation, but based on what you posted: The first 3 bits are 1 to 6 in reverse binary. The last digit is 1 when there are an odd number of 1s in the first 3(4?) bits, so this is probably a parity bit.

share|improve this answer

The Wikipedia page you link to mentions that

Their original design included two wide bars and one wide space in each character, resulting in 40 possible characters.

As a reference it cites David Allais' memoirs:

I proceeded to illustrate a symbol character using the side of the chalk to draw the wide bars. The structure of five bars and four spaces including two wide bars and one wide space came to me in flash. The two of five coding in the bars afforded ten combinations and the wide space provided for four separate groups.

So with that in mind we can identify the marked bars and spaces and a pattern does emerge:

  BSBSBSBSB     BB S
  001122334

0 000110100     23 1
1 100100001     04 1
2 001100001     14 1
3 101100000     01 1
4 000110001     24 1
5 100110000     02 1
6 001110000     12 1
7 000100101     34 1
8 100100100     03 1
9 001100100     13 1

A 100001001     04 2
B 001001001     14 2
C 101001000     01 2
D 000011001     24 2
E 100011000     02 2
F 001011000     12 2
G 000001101     34 2
H 100001100     03 2
I 001001100     13 2
J 000011100     23 2

K 100000011     04 3
L 001000011     14 3
M 101000010     01 3
N 000010011     24 3
O 100010010     02 3
P 001010010     12 3
Q 000000111     34 3
R 100000110     03 3
S 001000110     13 3
T 000010110     23 3

U 110000001     04 0
V 011000001     14 0
W 111000000     01 0
X 010010001     24 0
Y 110010000     02 0
Z 011010000     12 0
- 010000101     34 0
. 110000100     03 0
  011000100     13 0
* 010010100     23 0

Note that the bars for 0 in the first section correspond instead to 10 in the other three sections. If we rotate the bars to be ordered 40123 then the pattern we see is

    40123
04  xx...
14  x.x..
01  .xx..
24  x..x.
02  .x.x.
12  ..xx.
34  x...x
03  .x..x
13  ..x.x
23  ...xx

which is one of the obvious ways of enumerating pairs of 5 elements.

Equivalently, if you name the bits B1-S3-B2-S0-B3-S1-B4-S2-B0 from left to right in your representation and instead represent each code as SBB indices then the sequence 12..90AB..YZ-. * becomes 010 020 021 030 031 032 040 041 042 043 110 120 ... 342 343.

share|improve this answer

The right pattern to think how this encoding works is that 1) you find a set of "safe bit sequences", then 2) map your characters to these sequences.

End result feels like a random order, but each of these steps is quite logical per se.

"Safe" bit sequences are such that if you invert a single bit in any of it, result will be "outside" of your set. This is a form of error checking - basically a major "selling point" of Code 39.

  • Say, if you want to "encode" that way two characters, you'll need two bits at least. 00 and 11 make a set of two safe bit sequences - break (invert) one bit in any of these and you will get invalid code. Note that set of 01 and 10 is safe, too.
     
    To encode three characters, one needs more than two bits.
    Example of safe set for three characters is 000, 110 and 011.

Now, you need to encode 39 characters.

First, find how much bits you need for that, then find a set of "safe bit sequences".

And only after that, map your characters, like first char -> first safe bit sequence, second char -> second sequence etc.

You see, it's easier to think in terms of "steps" here, not in terms of "formula".


Algorithm to find safe bit sequences for given number of bits N could be about as follows,

  1. allocate boolean array of length 2 power N, initialize its elements with true
  2. start with 0 - its boolean representation is N bits, each zero
  3. do N times: invert one of the bits in 0 - that will be "unsafe bit sequence",
    mark array element at resulting index false
    array[1000], array[0100], array[0010], etc
  4. find next after 0index in array where element is true,
    for bit representation of that index, repeat same loop as above:
    invert one of the bits and mark respective ("unsafe") element of array false
  5. find next true index and so on and so on until array ends

In the end, elements of array marked true will represent "safe bit sequences".

To transform these sequences to bar code, one would just map pairs of bits appropriately, like 00 - narrow black, 01 - narrow white, 10 - wide black, 11 - wide white.

share|improve this answer

protected by World Engineer Sep 29 '13 at 19:10

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.