in
A hardware and device driver project for Linux.
Parity Patterns

Whether the bar pattern for any given digit of the ISBN is taken from bar pattern group A, group B or group C, depends on the so-called parity pattern. The parity pattern used for the left group of six ISBN digits is always ``ABBABA''. The parity pattern used for the right group of six ISBN digits is always ``CCCCCC''. The parity pattern used for the price code extension is selected by a single-digit hash value computed using the price digits themselves.

Price Extension Hash Value

For the five-digit price code extension, the parity pattern always includes three odd (O) digits from group A and two even (E) digits from group B, in some combination selected from the array:

UPC5PARITY =["EEOOO","EOEOO","EOOEO","EOOOE","OEEOO",
<@cont_arrow>å<@\$p>"OOEEO","OOOEE","OEOEO","OEOOE","OOEOE"]

The parity pattern used depends on the price digits being encoded. To encode the price \$24.95 US, for example, the hash value is calculated like this:

5  2  4  9  5
5  +  4  +  5  =  14
2  +  9     =  11
3  *  14    =  42
9  *  11    =  99
42 + 99 = 141
141 modulo 10 = 1
The ordinal 1 would be used for picking the parity pattern out of the array:
UPC5PARITY = ["EEOOO","EOEOO","EOOEO","EOOOE","OEEOO",
<@cont_arrow>å<@\$p>"OOEEO","OOOEE","OEOEO","OEOOE","OOEOE"]
The parity pattern at ordinal 1 is ``EOEOO'' and so the price code digits ``52495'' would be encoded by selecting bar patterns from groups A and B in the order ``BABAA'', taking even digits from group B, odd from group A. The four interdigit delineators--inserted between each two adjacent digits of the price code extension--possibly provide additional clocking information or possibly achieve that certain complexity agreeable to the bureaucratic mind.

Data Collection

Our user-side program stores bar-width readings in the array bartime[ ]. The width reading for the first bar of the ISBN left guard bars will be at bartime[0]. The width reading for the last bar of the last digit of the price extension will be at bartime[90]. Using an array index we can access bar-time data for whatever digit we are interested in.

Preview of the Algorithm

For the digit we wish to decode, we begin by summing the four measured bar times. Since we know that the total width of a four-bar digit pattern must be seven units, we divide the sum by seven to obtain the value of the local unit-bar-width for this four-bar digit. We calculate this local unit-bar-width as a floating-point value. Using this local unit-bar-width, we determine the size, as an integer value, of each of the four bars that make up this digit. If the four integer bar sizes thus calculated do not sum to seven, then we fiddle with the rounding threshold, reducing or increasing it a little, until the bar sizes do sum to seven. How much fiddling we have to do to make the bar sizes sum to seven gives us some idea of the quality of the bar code; assuming, of course, that while data was being gathered, the wand moved with fairly uniform speed across the bar pattern, and the software clock was not erratically interrupted.

Bar Code Wand Device Driver

To keep things simple, the kernel module portion of our bar code reader system implements only the module initialize, module remove, device open, device close and device read functions. We need no data buffer because our read( ) function returns just one bit of information each time it is called: the state of DCD. In place of the character count that is normally returned by the read function, our read function simply returns the state of DCD, the wand's output line, at the instant the read function was called. Using this device read function, our user-side program repeatedly samples the state of the wand output while advancing a software clock that measures the time duration of its high and low states. These measured bar-time durations are saved in a linear list that becomes the input data for the algorithm described above.

Create the Device

In a UNIX-type system, such as Linux, attached peripheral devices preferably are accessed through the filesystem. A directory entry that points to a peripheral device is said to point to a special file, also called a device file. Such an entry can be placed in any directory, but it is conventional to gather the special device file directory entries into the directory called /dev. To access the line printer, for example, there will be a device file in this directory. The command

ls -l /dev/lp*

may display entries such as these

crw-rw----  1 root  daemon  6, 0 Apr 27  1995 /dev/lp0
crw-rw----  1 root  daemon  6, 1 Apr 27  1995 /dev/lp1
crw-rw----  1 root  daemon  6, 2 Apr 27  1995 /dev/lp2
The ``c'' in the string crw-rw--- means that the device named /dev/lp0, in this case, is a character device, and the rest of this string shows that root and members of the dæmon group have read and write access to this device. The line printer driver in this system has been assigned major number six and is intended to handle up to three attached printers that are to be selected via minor numbers 0, 1 and 2.

The kernel takes notice only of the device type ``c'' and the major number. The minor numbers are used only by the device driver. The major number is the ordinal into a kernel table of pointers to device drivers. The kernel reserves location 42 in this table for device-driver testing purposes, so that is the major number we use here to create a device file directory entry. Promote yourself to superuser with the command su and type in root's password. Create the device called ``wand'' with the command mknod /dev/wand c 42 0. Use the command exit to restore your normal user state. The command ls -l /dev/w* should now create a display including a line such as

crw-r--r-- 1 root  root  42,  0 Nov 22 16:43 /dev/wand

showing that you have a character type special device file named /dev/wand that has major number 42 and minor number 0.

______________________