Apparatus for rapidly accessing a large data base employing an optical disc reading system with multiple heads and track position compensation

What is claimed is:

1. Apparatus for rapidly accessing data elements on a serially encoded optically readable disc, said elements comprising a plurality of radially spaced tracks of a given number and spacing along a reference radial line, said tracks surrounding the disc center and partitioned into a plurality of contiguous files, each file having a certain angular and radial position on the disc relative to a reference position, said file angular and radial position tending to periodically differ from disc to disc and within a disc at different times in an unknown way in response to thermal contraction and expansion due to changes in the ambient temperatures and due to manufacturing tolerances, the data elements on the different tracks tending to have different read data rates when said disc is rotated at a constant angular velocity, said apparatus comprising:

disc drive means for receiving and rotatably driving a disc at a constant angular velocity;

a plurality of optical disc read means associated with said disc drive means for reading said data elements from the disc then being driven by that drive means at respective ones of angular spaced locations at a constant data rate, each said read means including a respective actuator means responsive to an applied control signal representing a given file position for independently reading the data elements from the file corresponding to that given file position; and

control means for generating said control signal and for selectively applying said control signal to currently selected one of said read means, said control means including means for correlating each said radially spaced track to each said certain file position to provide in memory said certain file position and means for periodically updating in said memory the correlation of said tracks to said certain file position to provide a periodically corrected certain file position.

2. The apparatus of claim 1 wherein said track spirals and said disc drive means includes means for rotating the disc at a constant angular velocity such that the reading of data from said files changes in frequency in proportion with the radial position of the read file on the track, said read means including means for corresponding the frequency response characteristics of the read file to the radial position of the read data so as to read the data from anywhere on the spiral track at substantially constant frequency.

3. The apparatus of claim 1 including a plurality of said drive means, each for receiving and driving a separate, different disc, each drive means including said plurality of read means, said control means including means for causing said signal to select one of said drive means and one of said read means of that selected drive means.

4. The apparatus of claim 1 wherein said means for generating a signal includes data read means for reading a data element from each of a plurality of objects and means for deriving a code from each said read data elements, said code having a unique value corresponding to each different data element, said means for deriving including means for correlating said derived unique code for each read data element to a corresponding file position wherein said signal manifests the file position of a read data element.

5. The apparatus of claim 1 wherein each said read means includes a laser read head for reading encoded information on said received, rotating disc.

6. The apparatus of claim 5 wherein said displacement means includes digital position encoding means for generating a position signal representing an approximate position of said read head relative to said spiral disc track and means for applying said position signal to said actuator control for moving the read head adjacent to said file position.

7. Apparatus for rapidly accessing data from a compact disc read only memory (CD-ROM) containing a digitally encoded data storage track impressed upon a light reflective surface, said track containing a plurality of contiguous data files, the location of said files on said track tending to change in response to temperature excursions causing said disc to expand and contract, said apparatus comprising:

disc drive means for receiving and rotating said disc about an axis;

a plurality of laser disc read means located at angular spaced positions about said axis, each read means including means for reading said data from anywhere on said spiral track, each read means including means for reading data from said disc independent of the reading of data by remaining read means, each read means including a read head and read head positioning means, said read head positioning means including means responsive to a read head positioning signal applied as an input thereto for aligning the head relative to a given file track; and

control means responsive to an applied input signal for generating said read head positioning signal and for applying said positioning signal to said read means, said control means including memory means for storing the position of said given file track and means for periodically determining the current position of said given file track and for periodically updating said stored position of said given file track in said memory means with said determined current position.

8. The apparatus of claim 7 wherein said control means includes means for reading data items from an object, means for deriving a file location code corresponding to each different data item from the read data items, and means responsive to said derived file location code for generating said read head positioning signal.

9. The apparatus of claim 8 wherein said data items include street name, city, state and five-digit zip code of a mailing address, said means for deriving including means for deriving from said mailing address a unique number corresponding to that mailing address, said means for generating said read head positioning signal including means for storing in memory the approximate file location on said disc of the file containing that mailing address for each said unique number.

10. A zip code enhancement system for adding an x digit zip code to a five digit zip code on an object containing a mailing address comprising a street, city, state and five digit zip code address, x being a positive integer, said system comprising:

a plurality of CD-ROM disc drive means, each for receiving and rotating a CD-ROM disc having a spirally encoded track containing a plurality of contiguous files, each file comprising a data block containing synchronization data, file address data, zip code address plus x for a plurality of zip code addresses, and error detection and error correction data;

means for reading the five digit zip code address on said object and for deriving a unique number for each different read address;

means for correlating each said derived number to a given disc containing that read zip code and to a given angular position on that given disc from a reference angular position and to a given radial distance from the center of that given disc to the file containing that zip code address and for generating an output signal representing said correlated angular position, radial distance and given disc in response to the reading of said address on said object; and

a plurality of disc read means responsive to said output signal applied thereto for reading that file located at that angular position and radial distance on that given disc.

11. The apparatus of claim 10 wherein said system further comprises zip plus x digit print means responsive to the reading of a disc by said disc read means for printing information representing the five-plus-x-digit zip code on the corresponding object containing the five-digit zip code.

12. The apparatus of claim 10 further including angular reference indicia on each second discs, said disc read means including means responsive to said indicia for generating a signal representing said reference angular position and for determining said given angular position from said reference position.

13. The apparatus of claim 10 wherein each said disc read means includes a read head and read position means, said read position means including means for moving said head to an approximate location relative to said given radial distance and track counting means coupled to said head for counting tracks from said approximate location in a given direction to place the head at that track containing the desired file.

14. The apparatus of claim 10 wherein said drive means includes means for rotating a received disc at a constant angular velocity causing the frequency of the read data along said track to differ as a function of the radial position of the read track to the center of the drive means, said read means including frequency compensation means for reading data at substantially the same data rate regardless the position of the data on the track.

15. A CD-ROM disc read system for reading data recorded at a constant linear rate on a disc track comprising:

CD-ROM disc drive means for driving a received disc at a constant angular velocity resulting in different playback rates for different radius portions of the track;

a plurality of read head means for independently accessing and reading data at a plurality of disc locations from anywhere on a given disc at substantially the same constant data rate regardless the difference in actual rates occurring on the different track portions being read; and

control means for selecting and operating the selected read head means, said control means including means for generating a signal representing the radial and angular positions of said track portions relative to a reference position at a plurality of locations on a disc, each read head means including a read head and means responsive to said signal applied as an input thereto for positioning the read heat at that radial position relative to the received disc for reading target data from a given track portion, said means responsive to said signal including means for updating in memory said radial and angular positions of said target data track portion and means for reading said updated radial and angular positions from said memory for positioning each said read head.

16. A system for updating change of address information on a letter comprising:

means for reading the name and address on the letter;

means including first CD-ROMS for deriving and generating a standard eleven-digit-zip code from said read name and address;

means including second CD-ROMs for determining if a given read name and address has a corresponding change of address and for storing in memory the new eleven-digit zip code for such change of address;

means for printing the sotred new zip code, if any, on said read letter; or, if not new, the old zip code, and

means for printing an address label containing the new, changed complete address, if any, for said letter in response to said determining.

17. The system of claim 16 wherein said first CD-ROMS includes a first set of CD-ROM systems for providing a standard eleven-digit zip code for a given name and address and a second set of CD-ROM systems including means cooperating with said means for reading for supplying said complete name and address to said means for printing.

18. The system of claim 16 wherein said means for printing includes means for printing a bar code on said letter representing the standard generated eleven-digit zip code or the new eleven-digit zip code of a changed address.

Description Submit all comments and votes

This invention relates to an apparatus for accessing a relatively large data base in one seek.

The United States Postal Service (USPS) presently intends to provide several hundred letter sorting machines at spaced locations around the United States equipped with optical character reading (OCR) systems which will be able to read the entire address block for a given addressee. The purpose of this is to permit the USPS to print nine or eleven digit zip codes on pieces of mail which will in turn enable advance sorting strategies to thereby affect significant reductions in postal operation costs.

The USPS employs two types of automatic sorting equipment. In this first type, the characters of the address block are read by optical character reader (OCR) systems. In existing sorters, the bottom line containing the cite, state and zip code is read. From this data a barcode is marked on the envelope by an ink jet printer. This barcode can be read by automatic sorters of the second type, which are less expensive since they are not equipped with the OCR system. The USPS system contains many more sorters of the second type than of the first type.

Each such letter sorter requires a data base which contains the destination addresses corresponding to the nine digit (zip+4) or eleven digit (zip+6) zip codes. The nine digit zip code defines the ranges of addresses, such as a side of a street, or a floor of an office building. The USPS maintains a file of standard address ranges for the zip+4 codes, which consists of about 29 million records requiring approximately 3 gigabytes for storage. A standard address is that assigned by the USPS. Individual postal patrons may inscribe mailpieces with variations on or additions to the standard address. These variations are a problem in the design of OCR systems for USPS. The present inventor recognises a need to provide rapid access to the file of standard addresses.

The eleven digit zip code defines all the specific mail destinations in the country, and consists of some 86 million records. An additional factor is that there are approximately 40 million changes of addresses each year; the change of address file is kept for eighteen months. Thus, there are an average of about 110 thousand changes of address per day. The data base to retain these addresses for eighteen months contains 60 million records.

It is required by the USPS that the letter sorters process twelve letters per second (80 millisec per letter). Further, the data base containing all of the addresses must be accessed at this rate on a continued sustained basis. It is intended that there be 650 letter sorters on a nation wide basis. Such sorters will be located at 250 sectional centers. Letters entering the center are to be marked with a bar code containing the nine or eleven zip digits; thereafter, simple sorters will read the code. Each of the 650 data bases is a duplicate containing the addresses for the entire country.

Conventional data base technology is believed unable to provide the required performance at a reasonable cost. Magnetic disc recording systems of requisite capacity are standard features of large computer systems. These are controlled by data base software which enable continuous incremental updates of the records by many users. The consequence of this procedure is that the distribution of data on a disc becomes progressively more complex and multiple seeks are necessary to find specific items. Thus, even though the access time for a high performance disc may be as low as 18 milliseconds (ms), so many accesses are required that the 80 ms (12 per second) goal cannot be met.

The present inventor recognizes that the bulk of such a data base is static. Such a data base can be updated periodically at a central site and copies distributed to local cites where it can be read but not revised. Such data bases can be updated, published and distributed as wholes and local updating may be by complete replacement of the entire data base. Because any specific issue of the data base is static, it can be organized in a simple manner such that one seek to a track and scan of that track will find any record.

The most useful means of current data base distribution are CD-ROM (compact disc read only memory) and digital video tape (D-1 format). CD-ROM refers to the use of compact audio disc technology for the distribution and reproduction of digital data. A single such disc contains in excess of 0.5 gigibytes (GB) of user data, after system overhead and error correction are included. Digital video tape refers to the use of helical scan video recording technology to record digital signals. The recording density is significantly greater than on conventional computer tapes.

CD-ROM's are conventionally recorded with a spiral tape at constant linear velocity. The recorded data rate is constant and the disc speed must change with the radial position of the recording or read head. The read head contains a semiconductor laser and sensors which provide signals for focus and tracking servos, as well as data readout. Commercial CD-ROM players are intended for personal computers and feature access times of the order of one second, which is impractical for the USPS applications.

According to the present invention a CD-ROM disc read system for reading data recorded at a constant linear rate on a disc track comprises a CD-ROM disc drive means for driving a received disc at a constant angular velocity. This results in different playback data rates for different radius portions of the track. A plurality of read head means are coupled to the drive means for independently accessing and reading data at a plurality of disc locations from anywhere on a given disc at substantially the same constant data rate regardless the difference in actual data rates occurring on the different track portions being read. Control means select and operate the selected read head means.

In the Drawing:

FIG. 1 is a diagramatic representation of a system in accordance with one embodiment of a present invention;

FIG. 2 is a plan view partially diagrammatic of one disc drive system according to the embodiment of FIG. 1;

FIG. 3 is a block diagram of one actuator controller system used to read data from a given disc according to the embodiment of FIG. 1; and

FIG. 4 is a block diagram of a system for updating the data in a system having a significant number of changes of data.

In FIG. 1, a conveyor 11 conveys a serial stream of letters L1-LN or other types of mail for reading by an optical character reader (OCR) 12. OCR 12 reads the name, street, city, state and five digit zip code appearing on the face of the letters L1-LN. The name, street, city, state and five digit zip code read by the OCR 12 is supplied to system controller and multiplexer 14. Multiplexer 14 has a plurality of parallel channel outputs 1A-D, 2A-D-10A-D. These outputs are applied via multiple lines to CD-ROM controllers for reading data from an array 15 of CD-ROM read systems.

For example, outputs 1A are applied to controller 16A, outputs 1B are applied to controller 16B, and so forth. Outputs 2A-D of multiplexer 14 are respectively applied to a second set of identical controllers 17A-17D wherein outputs 2A are applied to controller 17A, outputs 2B are applied to controller 17B and so on. The remaining outputs 3A-D-10A-D are applied respectively to the remaining sets of controllers 18, 20, 22, 24, 26, 28, 30 and 32 of the system. Each of the sets 18-32 comprise four identical controllers which are also identical to controller sets 16A-16D and 17A-17D for receiving inputs from the system control and multiplexer 14.

Controller 16A operates an actuator 34, controller 16B operates an actuator 36, controller 16C operates an actuator 38 and controller 16D operates an actuator 40. Actuators 34-40 are mechanical devices for radially displacing respective laser read heads 44-50 secured thereto. Actuators 34, 36, 38 and 40 are represented by radial lines relative to CD-ROM drive 42. Actuator 34 is radially aligned with actuator 38 on diametrical opposite sides of the drive 42. Similarly, actuators 36 and 40 are radially aligned normal to actuators 34 and 38. Actuator 34 is coupled to a read head 44, actuator 36 is coupled to read head 46, actuator 38 is coupled to read head 48 and actuator 40 is coupled to read head 50. Read heads 44-50 are identical and comprise a laser read mechanism as available in commercially available CD-ROM drive systems. Each controller 16A-16D independently drives and controls the position of its respective corresponding read head 44-50 via the respective actuators 34-40. The use of plural read heads with independent actuators and controllers allows overlapping of periods of time to adjust the radial position of the heads as part of a seek operation. This permits the plural heads to be read consecutively without having to allow intervening time periods to adjust read head radial positions.

In similar fashion, a CD-ROM read head and actuator system is associated with each controller 17A-17D and the remaining controller sets 18-32. The laser read drive subsystems are identical.

System control and multiplexer 14 responds to the scanof the address on a given letter L1-LN and activates a selected one of the controllers to access a portion of a disc known a priori to contain the standard address and five+four zip code corresponding to the read letter. A CR-ROM disc is on each of the CD-ROM drives. Each disc is part of a data base containing the standard address including the city, state and five+four zip code. As known, the five-digit zip code refers to a destination locality whereas the additional four digit zip code narrows the destination to a given street or carrier route. The United States Postal System desires to bar code print the nine-digit zip code (five+four) onto each letter so that the letter may be automatically sorted by the bar code imprinted address by a sorter 52. Sorter 52 may be of the first or second types as described above. To do this the controllers for each of the CD-ROM drive systems supply the additional four digit specific zip code in response to the reading of the normal five digit zip code appearing on each letter.

This requires the system to read the street address and five-digit zip code appearing on each letter. The system then extracts from a data base containing the standard street addresses and the nine-digit zip code for every such address range in the United States. System control and multiplexer 14 generates from the read address and five-digit zip code an appropriate signal which identifies a particular controller of a particular disc drive system corresponding to that read data. That signal causes the read head of a given system to access the standard address and nine-digit zip code information from a given CD-ROM disc driven by that drive system. To perform this access the read head radial position is slewed to the approximate track location using a digital position encoder. The read head is then positioned to the desired track portion by counting tracks. Because conventional CD-ROMs have access times of about 1 to 2 seconds and because the postal system requires accessing of the data base at a rate of 12 items per second, normal CD-ROMs are too slow for this purpose.

By providing 10 drive systems 42, 43, 45, 47, 49, 51, 53, 57, and 59 each receiving a CD-ROM disc containing a different portion of the standard address and nine-digit zip code data base and by providing each drive system with four read heads it is possible to access the selected addresses and zip codes at an average rate of 12 units/second. The number of read heads and thus access channels is a function of the required access time in relation to the required read rate. Access time is the time required to radially position the head plus the time to rotate the disc about one revolution under the head. Four channels corresponding to the four read heads permit 4.times.80 =320 ms access time for each channel and still maintain the required average read rate of 12 units per second. The access time for a disc is a function of the disc rotation speed and head seek time. For example, the time available to radially position the head may be 3.times.80=240 ms; and the time to rotate the disc one revolution may be 80 ms. CD-ROMs normally have about 18,000 spirally connected tracks.

In a commercially available player, the head is moved radially to the approximate track location and the data is read to determine the actual location of the desired data. The read head is then radially displaced a smaller incremental distance and the data read again until the target data is located. This process, thus, is time consuming. By providing the four channels per disc, a 320 ms access time can be allowed. Such performance is reasonable for the actuator and controllers as will be described below in more detail. If better performance is achieved by a specific actuator design, the number of channels can be reduced, still conforming to the principles of the embodiment described herein. Ten discs are illustrated in FIG. 1 since it is believed that the nine-digit zip code defines a range of addresses which consists of about 29 million records requiring 3 gigabytes of data storage. Since a conventional CD-ROM disc contains about 0.5 gigabytes of data, it is believed that 10 discs are adequate to contain the 29 million records. Well understood techniques of data compression can be used to reduce the number of discs required.

In response to the read address from OCR 12 the system control and multiplexer 14 determines which one of the systems 42-59 and which one of the controllers 16A-16D through 32 contains the desired address and generates an appropriate signal. That signal selects the specific read head and given drive system for accessing the data at that selected drive system. How the controllers operate and select the information and how the system controller derives the signal for selecting a given controller is described below in more detail in connection with FIG. 3.

Once a signal is applied to a given controller and that controller read head accesses the data on its corresponding CD-ROM disc, the information is applied via line 54 to system control and multiplexer 14. The information accessed on a given CD-ROM disc is the standard street address range and corresponding nine-digit zip code. Once the information applied to the multiplexer 14, multiplexer 14 causes bar code printer 56, which may be a jet ink printer, to print the bar code representing the nine digit zip code on the individual letters such as letter L3.

In FIG. 2 representative system 42 includes a disc drive 58 and a CD-ROM disc 60. One controller 16A and its corresponding actuator 36 are shown in solid, the remaining controllers and actuators are represented by the broken radial lines 62, 64 and 66.

Disc 60 contains data which are recorded in a continuous inside out spiral track. As is known, CD-ROM discs contain data in a series of user data blocks of fixed size alternating with headers containing serial numbers and error detection codes. User data files may contain any number of data blocks. There are no sectors of fixed angular extent or discrete concentric tracks as is the common practice in magnetic disk recording. As a result, the length of a file depends on the amount of data in that file and the angular location of the beginning of that file may vary from track to track along the spiral. The header information as employed on the disc of the present data base is conventional.

The method of providing rapid access to data will now be described. The access time in a disc recording system has two components, conventionally named seek time and latency time. Seek time is that required for the read head to find a specific track, commonly by a generally radial movement (which may be in a straight line or arc). Latency time is that required for the disc to rotate to bring the desired data past the read head. In a CD-ROM, the latency time is determined by the rotation speed of the disc which in turn is a function of the data density of the track and the data bandwidth of the processing circuits. For conventional CD ROMS, latency time may be over 200 ms. Seek time must be reduced to tens of milliseconds to achieve the performance goal of 320 ms access time. A CD-ROM player utilizes a pre-recorded plastic whose tracks are spaced about 1.6 micrometers apart. Because of thermal expansion and manufacturing variations, the exact radial position of a track is initially unknown to the system. In conventional CD-ROM players, specific tracks must be located by a method of successive approximation as described above. The present system provides a means for accessing the disc by each head in 320 milliseconds in one seek.

Each disc of the data base, for example disc 60, is marked with reference indicia 68 and 70. Indicium 68 represents an angular reference mark by which the angular position of data from that reference mark is measured by the value of angle .theta.. Indicia 70 divide the disc into small angular increments to provide precise angular location of any point on the disc with reference to the indicia 68. Two sensors 72 and 74 are coupled to controller 16A for supplying information relative to the angular position of the reference indicium 68 and for providing information via indicia 70 of the exact angular position of any point on the disc 60. Each controller 16A through 16D through controllers 32 (FIG. 1) include sensors such as sensors 72 and 74 for sensing the reference indicia on the corresponding rotating disc.

Drive 58 rotates disc 60 at a constant angular speed. However, the data on the disc is recorded in its spiral format at a constant linear rate. Therefore, in reading the data along the spiral track as the distance r from the center of a disc changes in value, the frequency of the read data will also change. Since the data on the disc are binary in an encoded format, the interpretation of the signals frm the optical read head will be performed by digital logic circuits and microprocessors which conventionally operate in a synchronously organized fashion driven by a central clock oscillator. In a conventional CD-ROM player, the disc speed is adjusted as a function of playback head radius to give a constant playback data rate. Because the disc 60 is driven at a constant angular rate, it would be impossible to read the data from the four read heads 44-50, which may be positioned at different radii, at a given constant data rate unless otherwise provided for. Means is provided as will be described below for reading the data from each of the tracks regardless the track radial distance r from the center of the disc at a constant data rate. In FIG. 3, the radial line r is a measure of the distance from the axis 76 about which disc 60 rotates. The disc drive 58 of system 42 includes a turntable 78 which receives the disc 60 and further includes a drive motor 80 for rotating the table 78 at a constant angular rate.

Each of the discs 60 as is known comprises static data impressed upon an optically reflective surface and coated with a transparent protective coating. The data comprise impressions formed in the reflective coating surface so that the transitions at the beginning and end of each depression form a binary signal representing the data. The binary one, for example may represent the transition from the bottom of the depression to the disc surface or vice versa whereas a binary zero may represent the bottom of the depression or the disc surface between depressions. These depressions are formed in a spiral track. The disc may be premastered and pressed in a conventional manner and then distributed to a wide number of local postal sorting stations located throughout the United States.

The data base comprises a set of ten discs. Each disc is associated with a separate drive system 42. Encoded at the end of the data track of each disc is an indexing table. The indexing table comprises a hash index number and the r-.theta. coordinates of the file headers expressed in radial and angular dimensions. The table of coordinates is recorded last