Decoding of barcodes by preprocessing scan data.

Background of the Invention

The invention relates to a novel system for decoding high density barcode from a record medium at high rate of speed and more particularly to method and circuitry for special preprocessing of the high speed barcode data stream that is much too fast for a conventional microprocessor, and then completing decoding with such a microprocessor without loss of throughput speed.

As known, barcodes contain information encoded by the ratios of the widths and sequence of the black bars and intervening white spaces. The code may be read by rapidly sweeping a spot of light, with a rotating mirror, across the entire barcode pattern. Reflection of light from spaces and absorption at black bars are sensed by the scanner's photodetector causing a varying level signal to be inputted to the decoder. The relative signal level thus fluctuates with the bars and spaces and is representative of the coded bar pattern. Moving beam barcode scanning of high density barcodes can generate serial data streams containing pulses as short as 1 microsecond.

To decode such a high density barcode data stream, the time duration of all the bars and spaces (as represented by signal amplitudes) must be effectively measured and compared to valid code patterns. By contrast, in slow speed decoders, a conventional microprocessor is itself programmed to measure each bar and space, with its own relatively slow internal counters and store that digital representation of the bar/space width in memory. The ratios of adjacent bars and spaces are calculated by dividing one bar count by the other to obtain a series of ratios that comprise a valid coded character.

Using this technique, minimum bar times of about 12 microseconds are the approximate lower limit using a fairly fast 16 bit microprocessor. However, this is an order of magnitude too slow for high speed moving beam scanners. Faster processors are available in the form of bit slice systems and sophisticated Digital Signal Processing chips; however, the cost and component count is prohibitive for many applications. Prior art decoders have employed hardware counters and DMA (direct memory access) controllers to measure the bars and spaces and put them directly into the microprocessor memory thus allowing higher scanning speeds. The problem with these known decoders is the excessive amount of hardware required, lack of adequate count range (without doing 16 bit data manipulation which is slow), and the presence of large amounts of extraneous background data in memory.

As described below, one of the features of the invention is to compress the input bar and space counts in a unique manner using a special log conversion of raw count information. One prior barcoding technique disclosed in U.S. Patent No. 3,887,792 and also in U.S. Patent No. 3,866,024 employs a logarithmic time base. By this prior art logarithmic technique, a reader can use the same scanner to decode from a high speed laser beam or a manually operated hand held wand. The technique disclosed in the above mentioned U.S. patents is a logarithmic technique but has drawbacks in not smoothly changing the log relationship and the time generator developed limits the decoder to a logarithmic base of two. Another prior art patent, U.S. Patent No. 4,104,514 describes tailoring the logarithmic operation not limited to the base of 2 but does not effectively and optimally convert high density barcodes scanned by rapid beam scanners. Examples of other barcode decoders are disclosed in U.S. Patent Nos. 4,282,426; 4,354,101 and 4,438,327.

Summary of the Invention

The present invention provides an improved barcode decoder based on a preprocessor that embodies one or more of the following features: <ul id="ul0001" list-style="none"><li>1. Compression logic to compress an n′ bit primary count bar and space widths down to n bit counts compatible with a downstream n bit microprocessor using a log base that is ideally suited to the count range.</li><li>2. "Quiet Zone" determination logic employing subtraction of logs of successive counts (hence division) to find predetermined space-to-bar ratios called "margins".</li><li>3. Separation logic for bar and space count data that separates in memory addresses containing spaces and from addresses containing bars.</li><li>4. Flagging memory addresses that contain bar/space counts adjacent "Quiet Zone" margins.</li><li>5. Sequencing control logic comprising a Johnson counter that acts as the lower initial counts of the primary counter.</li><li>6. A digital filter circuit to exclude very narrow noise spikes in the barcode scan data by disregarding initial counts.</li></ul>

In a system for decoding data scanned at a relatively high rate from barcode symbols, the following combination is disclosed herein. A preprocessor for receiving and preprocessing a scanned space and bar signal information, and a microprocessor cooperating with the preprocessor for completing decoding of the signal information and having a word length n; the preprocessor comprising: edge detect logic means for detecting the occurrence of edges of the space and bar signal information; primary counter logic means for receiving clock pulses of a predetermined frequency and performing a binary count up to a predetermined maximum count of C where C = 2^n′, and n′ = the number of binary bits of the primary counter logic means; sequencing logic means connected to the edge detect logic means and to the primary counter logic means for causing the primary counter logic means to perform a binary count of the clock pulses to represent the widths of spaces and bars in the space and bar signal information; log conversion logic means for converting the binary counts of spaces and bars to log counts L represented by integers in a range from 0 to a maximum of 2ⁿ; ratio logic means for detecting quiet zone margins from consecutive log counts L developed by the log conversion logic means, and producing a margin flag signal in response to log counts L having ratios equal to or greater than a predetermined ratio of space to bar widths; and latch logic means for latching and transferring log counts L to the microprocessor; and wherein the microprocessor has RAM means for storing the log counts L of space and bar widths at predetermined address areas, and for storing margin location data in the form of addresses of the log counts L that point to the memory locations of those space and bar counts at or adjacent to the predetermiend quiet zone margins.

The preferred embodiment of the invention uses the following method of selecting a log base to match system requirements and to implement the hardware to accomplish the logarithmic compression operation.

To allow highspeed processing and keep hardware costs to a minimum, the preprocessing is performed by a programmed gate (logic) array, and an 8 bit integrated host microprocessor is used having an n = 8 bit word length. Maximum processing speed can only be achieved if each count is represented by a single 8 bit byte, giving a maximum count of 2 raised to the 8th power or 256. This count range is not nearly great enough to accommodate a high performance moving beam scanner with a large depth of field. The greater the working range (depth of field), the larger the permissible variation in the speed of the spot that traverses the bar. The capacity of the counters must be sufficient to accumulate the total count without overflow at the lowest anticipated reading speed. Conversely, at the highest anticipated reading speed the number of counts per element must be great enough that quantization errors will not cause decoding errors. While a count range of 256 can be used successfully in a number of applications, it limits the performance of scanners having a large depth of field.

Increasing the count range to 1024, for example, allows the decoder to be used with most high speed scanners over a wide variety of conditions without the need for any adjustments. To extend the range of the count from 256 to 1024 and eliminate the complexities associated with division operations to provide the desired ratio information, methods and devices employing logarithmic techniques have been developed. The use of logarithmic compression allows a division process to be reduced to a simple subtraction operation which can be performed much faster by a microprocessor.

In the preferred embodiment, the logarithmic conversion is performed with a lookup table residing in a Read Only Memory (ROM) associated with the PLA preprocessor. This technique saves a tremendous amount of processing time for the microprocessor and allows a wide dynamic count range using n = 8 bit counts resulting in additional time savings at no cost in performance. The efficiencies introduced by the present invention include using the same ROM to implement a hardware divider that is used to determine whether a predetermined bar/space ratio has occurred, allowing a much smaller, less expensive and lower cost decoder than heretofore thought possible by the use of prior art techniques.

Since only 2ⁿ = 256 log values are available, assuming only n = 8 bit representation of each count, it is important in the interest of achieving maximum resolution to choose the log base carefully. In systems employing only microprocessors, a base of 2 is a common choice. However, this results in reduced resolution, especially in the low count range. If base 2 were used as the log base to represent counts ranging from 8 to 1024, it would require manipulating fractional numbers, which is slow and cumbersome with a microprocessor.

Additionally, with one byte representing each count, the accuracy in the low counts degrades to as much as ±5%

Since each element in a barcode reader introduces some error, even ± 5% is worth reducing, especially if it can be obtained without additional hardware. Decoders employing logarithmic time base generators, such as the type disclosed in Patent No. 4,104,514, would require an excessive amount of hardware to implement in a high speed decoder such as the one described in the present invention.

Also, the preferred embodiment of the preprocessor as disclosed herein includes relatively high speed edge detection logic that produces edge markers for the control logic, and counting circuits that are coupled with a Johnson state counter to logically sequence the preprocessor. The above described logarithmic conversion compresses the counted time interval to a single data word that can most efficiently be processed by the host microprocessor. Control circuitry provided between the preprocessor and the microprocessor transfers digital representations of each bar and space to their respective areas in the microprocessor memory. Bar/space comparator means for performing a ratiometric comparison of each bar and space to determine every occurrence of predetermined ratios, e.g. 10:1, of both bar/space and space/bar. Pointer information is transferred to the host microprocessor indicating precisely where in data memory each 10:1 ratio is located. The preprocessor of the serial data stream includes an ^n′ bit binary counter of 2^n′ capacity and is operated to perform a digital filter function to ignore all counts below a given minimum thereby filtering out spurious input noise.

BRIEF DESCRIPTION OF THE DRAWINGS

These and other features of the present invention will be more fully appreciated when considered in the light of the following specification and drawings in which: <ul id="ul0002" list-style="none"><li><u style="single">Fig.1</u> is a block diagram of a barcode decoder in accordance with the preferred embodiment utilizing a programmable gate-array coupled with a relatively highly integrated host microprocessor;</li><li><u style="single">Fig. 2</u> is a detailed block diagram of the preprocessor used in the decoder of Fig. 1;</li><li><u style="single">Figs. 3A-3H</u> are graphical illustrations of the wave-forms appearing at various parts of the diagram of Fig. 2;</li><li><u style="single">Fig. 4</u> comprises a logic flow diagram of the operations performed by the microprocessor of Fig. 1;</li><li><u style="single">Fig. 5</u> is a block diagram of an alternate embodiment of a barcode decoder, similar to the one shown in Fig. 1, except for the provision of plural microprocessors operating in parallel to further enhance the decoding speed.</li><li><u style="single">Fig. 6</u> is a logic circuit diagram of one of the logic block elements of Fig. 5.</li></ul>

DETAILED DESCRIPTION OF THE INVENTION

The invention will now be disclosed in detail to show examples of how the above concepts may be implemented for reading barcodes.

It is one of the intents of the present invention to represent bar/space count data C, for example having a maximum of 1024 numbers, with one n = 8 bit byte for downstream decoding of barcode data while maintaining the highest possible accuracy and implemented with the least amount of hardware.

The log conversion is preferably done with a ROM lookup table and thus we are free to choose any log base desired. As was mentioned earlier, log base 2 seems an obvious choice when using a microprocessor; however, in our case, the resolution is not adequate. It would be more efficient to select a log base that was perfectly tailored to the log range and count range being used. The following expression will give the log base as a function of log values available and highest count desired.

Where the highest desired primary count = C and the number of values for the log = L Then: Log base b = 10^{(Log C)/L}      (1) Using, for example L = 256, as a nonfractional log number to represent C = 1024 count range, the resulting log base b = 1.02811 limits the conversion error to a maximum of 1.3%. Since 256 can be efficiently represented as a binary 8 bit word, the n = 8 bit logarithmic representations of bar/space widths are then passed on to the 8 bit microprocessor via direct memory access (DMA). Furthermore, the ratios for determining margins can then be determined by high speed subtraction of one value from the other using a ROM lookup table.

To further increase the throughput speed of decoding by the microprocessor, the locations of key areas in memory, such as bar/space counts next to margins, are flagged. Knowing exactly where in RAM memory the margins of 10:1 are located saves the microprocessor the time of scrolling through memory searching for these ratios. In addition, with a simple subtraction of memory address locations it can be ascertained whether enough counts are present between the two framing ratios to form a valid barcode field. Additionally, the preprocessor automatically places the bars in odd memory locations of RAM and the spaces in even memory locations thus passing on the absolute bar/space information that would normally require a larger data word to be transferred between the preprocessor and the host microprocessor.

The margins or "quiet zones" as they are more commonly referred to, are the specified areas, both preceding and following the coded bar pattern that are required to be white and free of any marks that could cause a change in the barcode input signal. This white space must be at least 10 times the width of the narrowest element found in the coded bar pattern for the label to be valid. This requirement helps prevent truncating labels and reading valid barcode from random patterns.

A key element in the logic control of the preprocessor is an 8 stage Johnson counter that is used to identify specific master clock cycles and initiate various actions. The primary advantage of a Johnson counter is that it doesn't require numerous decode gates to identify cycles thus saving more hardware.

With the above concepts in mind, the implementation of the concepts of the present invention can be examined with reference to the drawing. In Fig. 1, the general organization of a hardware embodiment for implementing a preprocessor 49 is shown. The input to such a barcode decoder is the black/white digital signal from a moving beam barcode scanner. The signal from the scanner is coupled to an edge detector circuit <u style="single">41</u> that is clocked by the master clock <u style="single">4</u> and can resolve the edge of the digital barcode signal to within one time period of the master clock <u style="single">4</u>. The edge detector <u style="single">41</u> generates a positive pulse at each rising or falling edge of the barcode signal <u style="single">3</u>. The output of the edge detector <u style="single">41</u> is coupled to the Johnson counter logic sequencers <u style="single">42</u> which control the starting and stopping of the n′ = 10 bit bar/space counter <u style="single">17</u> as well as numerous other functions that will be explained later.

A Johnson counter is a binary counter designed specifically to count states. Instead of a binary sequenced output it has multiple discrete outputs that become active in sequence as the input is toggled, thus indicating how many pulses have been received. With this general functional description of the Johnson counter logic sequencers <u style="single">42</u> in mind the relationship of the bar counter <u style="single">17</u> the 10 bit multiplexer <u style="single">11</u> and the log conversion and margin detecting can be explained in more detail. Each time a pulse is received the logic sequencers <u style="single">42</u> stops the bar/space counter <u style="single">17</u>, latches the count and starts the counter <u style="single">17</u> counting the next interval. At the same time a delay is initiated to allow time for the divider/log convert ROM <u style="single">12</u> to convert the latched count <u style="single">13</u> to an 8 bit log value L that will then be saved by latch R1 <u style="single">23</u> so it can be compared to the next count and determine if a 10:1 difference exists between the two counts. The logic sequencers <u style="single">42</u> then activate the log/diy select line <u style="single">10</u> which causes multiplexer (MUX) <u style="single">11</u> to select the most significant 5 bits of latch R1 <u style="single">23</u> and latch R2 <u style="single">24</u> and couple them to the divider/log convert ROM <u style="single">12</u> to calculate the ratio between the two. Latch R1 <u style="single">23</u> holds the most recent count while latch R2 <u style="single">24</u> holds the count previous to that. The log/div select signal <u style="single">10</u> also switches the divider/log convert ROM <u style="single">12</u> to the divide table section of the ROM. If a 10:1 or greater ratio exists between the two counts, a margin interrupt signal <u style="single">39</u> will be activated by the logic sequencers <u style="single">42</u> alerting the microprocessor <u style="single">44</u> that a margin has just been detected.

The microprocessor <u style="single">44</u> then builds a lookup table of all the addresses in RAM <u style="single">43b</u> where the 10:1 margin ratios reside. The logic sequencers <u style="single">42</u> then request the microprocessor <u style="single">44</u> to perform a direct memory access operation by activating the DMA request line <u style="single">27</u>. A direct memory access (DMA) is an extremely fast and efficient way to enter data into a microprocessors memory. The operation is transparent to the execution of the microprocessor program as the microprocessor is very briefly halted while a DMA circuit, resident on the microprocessor <u style="single">44</u> chip in a highly integrated micro-processor such as a Hitachi the HD64180, takes brief control of the address and data lines of the microprocessor and stores the data into RAM <u style="single">43b</u>.

The logic sequencers <u style="single">42</u> then reset and begin the sequence all over again until the microprocessor <u style="single">44</u> decodes a valid barcode label, at which time the microprocessor simply ignores any further DMA requests until it wishes to read another barcode.

From the above description the operation of the preprocessor can be examined in more detail. Fig. 2 is a detailed block diagram of the preprocessor <u style="single">49</u> and its interface to the microprocessor <u style="single">44</u> and the timing relationships of the preprocessor functions are shown in Fig. 3. Preprocessor <u style="single">49</u> is preferably implemented using a programmable logic array (PLA) <u style="single">49a</u> as shown. The Johnson counter logic sequencers <u style="single">42</u> shown in Fig. 1 are comprised essentially of an 8 state first Johnson counter <u style="single">15</u> and a 6 state second Johnson counter <u style="single">16</u> as depicted in Fig. 2. The Johnson counters <u style="single">15</u> and <u style="single">16</u> are clocked by the master clock <u style="single">4</u> and advance one state for each master clock cycle, thus, with the master clock <u style="single">4</u> being 10 MHZ each state of the Johnson counter equals 100ns. Johnson counter <u style="single">15</u> detects the rising edge of the edge detector pulse <u style="single">51</u> on line <u style="single">1</u> and sets the clock enable signal <u style="single">52</u> low on line <u style="single">2</u> stopping the bar/space counter <u style="single">17</u> at its current count. No other action occurs until the fourth state of Johnson counter <u style="single">15</u>.

If the level of the barcode input <u style="single">3</u> has not changed states since the last rising edge of the edge pulse <u style="single">51</u> on line <u style="single">1</u> the transition of the barcode input <u style="single">3</u> is declared valid. The Johnson counter sets the edge clock signal <u style="single">53</u> on line <u style="single">6</u> high which latches the edge pulse signal <u style="single">51</u> on line <u style="single">3</u> and also latches the barcount data on line <u style="single">7</u> in count latch R0 <u style="single">8</u>. The level data on line <u style="single">9</u> is also latched into count latch R0 <u style="single">8</u>.

The purpose of the 4 state delay, 400ns, of Johnson counter <u style="single">15</u> is to form a digital filter to exclude very short spurious pulses on the barcode signal that are caused by either specular light reflections or high frequency random noise. The log/div signal <u style="single">54</u> on line <u style="single">10</u> is at a low level at this time which causes the 10 bit multiplexer <u style="single">11</u> to couple the latched barcount data at count latch R0 <u style="single">8</u> to the margin divide/log convert ROM <u style="single">12</u> via line <u style="single">13</u>. Signal <u style="single">54</u> also selects the ROM <u style="single">12</u> to address the log conversion portion of it's memory. No other action occurs until the 6th state of Johnson counter <u style="single">15</u>, this delay is necessary to allow for the propagation delay time of the ROM <u style="single">12</u>.

The data ready signal <u style="single">55</u> on line <u style="single">18</u> then goes high flagging Johnson counter <u style="single">16</u> that a new count is ready. On the seventh state of Johnson counter <u style="single">15</u> the counter reset signal <u style="single">56</u> on line <u style="single">19</u> goes high presetting the barcounter <u style="single">17</u> to a count of 8. Since the barcounter <u style="single">17</u> was not being clocked during the 8 states of Johnson counter <u style="single">15</u> this is a necessary compensation or the next count would be in error by 8 counts.

The next master clock <u style="single">4</u> sets Johnson counter <u style="single">15</u> back to the first state and the barcounter <u style="single">17</u> begins counting again. The cycle then repeats itself. Johnson counter <u style="single">16</u> controls the signal <u style="single">54</u> on line <u style="single">10</u> which determines whether the primary count data on line <u style="single">20</u> will be converted to logarithmic form by the log conversion portion of ROM <u style="single">12</u>, or whether the R1 latched data on line <u style="single">21</u> and the R2 latched data on line <u style="single">22</u> will be divided (subtract logs) by ROM <u style="single">12</u> to find a margin ratio.

Johnson counter <u style="single">16</u> also controls the progression of the log count data through the latches R1 <u style="single">23</u> and R2 <u style="single">24</u> as well as the interface to the microprocessor <u style="single">44</u>. With the above in mind, we will examine the operation of the remainder of the preprocessor <u style="single">49</u> in more detail. When the data ready signal <u style="single">55</u> on line <u style="single">18</u> goes high Johnson counter <u style="single">16</u> begins to count master clock pulses. The first state activates the R2 clock line <u style="single">26</u> that causes the data currently in latch R1 <u style="single">23</u> to be latched into latch R2 <u style="single">26</u>. The DMA request signal <u style="single">57</u> on line <u style="single">27</u> goes high requesting the microprocessor to perform a DMA cycle which moves the data from the output buffer <u style="single">28</u> into the microprocessor RAM memory <u style="single">43b</u>. During the DMA cycle, the read line <u style="single">2</u>9 is activated by the microprocessor which tells the Johnson counter <u style="single">16</u> that the data has been received by the microprocessor <u style="single">44</u>. If the read line <u style="single">29</u> is never activated the preprocessor suspends all operations until the microprocessor reads the current data in the output buffer <u style="single">28</u>.

The microprocessor <u style="single">44</u> must activate the chip select line <u style="single">30</u> before it can read the data at the output buffer <u style="single">28</u>. Upon activation of the chip select line <u style="single">30</u> the Johnson counter <u style="single">16</u> logic activates the read line <u style="single">31</u> which activates the normally disabled outputs of the output buffer <u style="single">28</u> allowing the RAM <u style="single">43b</u> to load the data.

Bar and space counts are separated in RAM <u style="single">43b</u> with the bar counts residing in odd numbered RAM locations and the space counts residing in even numbered locations. This separation is accomplished by synchronizing the DMA address and the bar count data. On the very first DMA cycle the preprocessor checks line <u style="single">34</u> to see if the bar count data on line <u style="single">32</u> is a white level. If it isn't, the microprocessor increments the DMA address and reads the same data again putting it in the second memory address location in the barcount RAM memory area.

From this point on, a level data logic, such as a flip-­flop, associated with Johnson counter <u style="single">16</u> is toggled each time a DMA cycle occurs. If this flip-flop ever gets out of sync with the level data signal <u style="single">34</u>, an additional DMA cycle is forced thus causing the RAM address to be in sync with the level data once again. This procedure insures that white counts will always be in even address locations and black counts will be in odd locations of RAM. One consequence of doing this synchronization process is that the very first address of the RAM may contain a bogus count, however, it has no negative effect on the decoding algorithm. An additional advantage of this synchronization feature is accommodating overflows of the bar/space counter <u style="single">17</u>. Whenever the barcode input signal <u style="single">3</u> remains in one state for more than 1024 counts, the counter <u style="single">17</u> generates an overflow signal <u style="single">33</u> and the count is latched in count latch R0 <u style="single">8</u> just as if a normal edge pulse <u style="single">51</u> on line <u style="single">1</u> had occurred. The only difference between an overflow of the counter <u style="single">17</u> and an actual edge occurrence is that the edge clock signal <u style="single">53</u> on line <u style="single">6</u> does not change. This allows the microprocessor to keep track of how many overflows have occurred without losing the synchronization of the bars and spaces with memory addresses. If an odd number of overflows occurs it will cause a bar count to be put into a white memory location. When this situation occurs, the Johnson counter <u style="single">16</u> detects that the level data signal <u style="single">34</u> is out of sync with the level data flip-flop in Johnson counter <u style="single">16</u> logic and activates the DMA request signal <u style="single">57</u> on line <u style="single">27</u> that causes an additional read of the barcount data currently in the output buffer <u style="single">28</u> thus making the DMA address correct once more.

At state two of Johnson counter <u style="single">16</u>, the R1 clk signal on line <u style="single">25</u> is activated latching the pending count in log form on line <u style="single">14</u> into R1 latch <u style="single">23</u>. At state 3 of Johnson counter <u style="single">16</u> the signal <u style="single">54</u> on line <u style="single">10</u> is activated thus coupling the most significant 5 bits of R1 latch <u style="single">23</u> on line <u style="single">35</u> and the most significant 5 bits of R2 latch <u style="single">24</u> on line <u style="single">36</u> to the ROM <u style="single">12</u> which is now selected to the divide portion of its memory. The two successive log counts in R1 latch <u style="single">23</u> and R2 latch <u style="single">24</u>, respectively, will now be divided (subtract logs) one into the other to determine if the ratio between them is greater than or less than a predetermined margin such as 10:1. At state 5 of Johnson counter <u style="single">16</u> the result on D0 of line <u style="single">14</u> of ROM <u style="single">12</u> will be valid and the compare window signal <u style="single">8</u> on line <u style="single">40</u> is activated thus enabling the margin detect circuit <u style="single">38</u>. If it is greater than 10:1, a bit on line <u style="single">37</u> is activated flagging a 10:1 ratio to the margin detect logic <u style="single">38</u>. Margin interrupt signal on line <u style="single">39</u> is then activated causing the microprocessor to immediately mark the current DMA address in a lookup table in RAM <u style="single">43b</u> so margins can easily be located by the microprocessor <u style="single">44</u>. Johnson counter <u style="single">16</u> then returns to state zero until another data ready signal <u style="single">55</u> occurs.

With reference to Fig. 4, the counts in RAM memory are marked so each scan is delimited in memory as indicated at <u style="single">60</u> to prevent appending counts from one scan to the other thus causing erroneous decoding. Then, as shown in the program flow chart of Fig. 4, Later after locating both a leading and a trailing margin at <u style="single">61</u> and <u style="single">62</u>, the program of microprocessor <u style="single">44</u> checks to see if there are enough counts between the two margins for a minimum length barcode <u style="single">63</u>. Block <u style="single">64</u> simply tests to see if the margin located is a white to black margin and not a black to white margin which is invalid for a leading margin. The remainder of the flowchart is relatively self explanatory as to the sequence of events to decode the data. The program controlling microprocessor <u style="single">44</u> and set forth in Fig. 4 is stored in EPROM <u style="single">43a</u>.

In block <u style="single">65</u> two important things that were done by the preprocessor <u style="single">49</u> increase the decoding speed significantly. The first is having the counts in logarithmic form. Then any of well known character decode algorithms programmed in microprocessor <u style="single">44</u> cause each count to be ratiometrically compared with another count. To divide two numbers in logarithmic form, you simply subtract them saving the time of a divide which would take at least four times longer. Additionally, the log base that was chosen above allows all the logs to be expressed as integers so the processor does not have to do fractional arithmetic. The second feature is having the bars and spaces identified in memory by their addresses. Since the decode algorithm typically compares bars to bars and spaces to spaces to help reduce optical distortion effects, knowing exactly where all of the bar and space counts reside in memory RAM <u style="single">43b</u> further increases the decode speed.

To further appreciate the present invention, the relationship of the preprocessor <u style="single">49</u> and the microprocessor <u style="single">44</u> must be explained in more detail. Fig. 4 shown an overview of the program flow of the microprocessor <u style="single">44</u>. The first thing the program does is try to locate the areas in memory where there is a high probability that valid barcode data resides. Bear in mind the microprocessor, without a margin flag or vector, would be forced to search through up to several thousand 8 bit counts to find a valid label and hence slowing decoding speed. Here a margin vector table created as described above by preprocessor <u style="single">49</u> points out all of the locations in RAM where 10:1 ratios exist thereby simplifying and speeding up this task. The program first checks at <u style="single">61</u> to see if any margins were seen during a cycle. If any margins are found, the program then checks at <u style="single">62</u> to make sure it is from the scan currently being analyzed.

To further enhance the speed of the barcode decoder, another embodiment shown in Fig. 5 is disclosed. The preprocessor <u style="single">49</u> described earlier is modified as preprocessor <u style="single">60</u> to allow sending its barcount data <u style="single">32</u> to one of two parallel microprocessors <u style="single">70</u> and <u style="single">48</u>. While parallel processing is known per se, it traditionally raises the problem of how to efficiently divide the task between one or more processors. A barcode scanning system lends itself perfectly to a parallel system since the individual scans are totally independent of one another, thus giving unusually great efficiency in the division of the barcode decoding task. To accomplish the implementation, the preprocessor <u style="single">60</u> has two multiplexers added <u style="single">45</u> and <u style="single">47</u> whose function is to couple the interface line to either the master microprocessor <u style="single">70</u> or the slave processor <u style="single">48</u>. The preprocessor <u style="single">60</u> arbitration logic <u style="single">46</u> will transfer data to whichever processor is ready first. Otherwise, the preprocessor <u style="single">60</u> is essentially the same in operation as the previously described processor <u style="single">49</u> except for the above mentioned circuits.

Each microprocessor <u style="single">70</u> and <u style="single">48</u> evaluates data from different scans of the barcode scanner independently. Once either processor has completed a valid barcode read the master processor <u style="single">70</u> takes control, via the serial communication port <u style="single">71</u> linking the two microprocessors, and either halts further processing by the slave processor <u style="single">48</u> or instructs it to continue if more valid reads are required. Once a valid barcode has been decoded it is sent by the master processor <u style="single">70</u> to a host computer via serial link <u style="single">72</u>.

The arbitration circuit <u style="single">46</u> is a logic circuit that controls the two multiplexers <u style="single">45</u> and <u style="single">47</u> that couple the barcount data and the related interface lines margin and DMA request to either the master microprocessor <u style="single">70</u> or the slave microprocessor <u style="single">48</u>. The ready line from each microprocessor is monitored by the arbitration logic <u style="single">46</u>, and whichever one goes active first will receive the barcount from the next scan. The arbitration circuit will switch the multiplexers <u style="single">45 </u> and <u style="single">47</u> at the end of the scan to the other microprocessor. In the event that the microprocessor is still busy, wait signal activated, the arbitration circuit will wait for the active ready line and switch the data to that processor.

The arbitration circuit <u style="single">46</u> is shown in detail in Fig. 6 to include RS flip-flops <u style="single">80</u> and <u style="single">81</u> and output logic gate <u style="single">82</u> and inverter <u style="single">83</u> and functions as follows: when scan sync becomes active, the microprocessor currently selected will be deactivated by unasserting the microprocessor's ready line. Immediately after this, both wait lines are checked to see if one or both are unasserted. If both are unasserted, the slave processor <u style="single">48</u> will always be selected because the master processor has the host interface communications task, which can add overhead in some cases, so it makes sense to give the data to the slave whose only task is barcode reading. Otherwise, whichever wait line unasserts first, the arbitration circuit will select that processor to receive the next scan's data by asserting the appropriate ready line. When the other processor is ready, it will unassert its wait line and the arbitration circuit latches that information so at the end of the current scan the data will be switched to this processor.

As described herein the present invention advances the state of the art of decoding barcode information through the provision of a scan data preprocessor. The invention comprehends the measurement of elapsed time with a uniquely selected log conversion ROM and computing the ratios of the widths of barcoded segments by simple subtraction. When the implementation is in the terms of a preprocessor coupled to a microprocessor, the additional functions of the preprocessor consisting of separating bars and spaces in RAM and identifying the margin locations, permits decoding and reading of the barcoded data by an inexpensive microprocessor at very high throughput data rates with a minimum of hardware.

While only particular embodiments have been disclosed, it will be apparent to those skilled in this art that numerous changes can be made thereto without departing from the essence of the invention as set forth in the following claims.