System and Method for Encoding and Storing Digital Information on Magnetic Tape

The present invention relates to systems and methods for writing digital information on magnetic tapes, and more particularly to such systems and methods for generating and storing redundant information with the digital information on the tape.

A wide variety of storage devices has been developed for storing digital data or information generated by, and utilized in conjunction with, a digital computer. The selection of an appropriate storage device for a particular application is dictated by several factors including the cost per byte of information stored and the read/write response time. CMOS random access memory (RAM) provides the fastest response time, but has the highest cost per byte. At the other end of the spectrum, magnetic tape has the slowest response time, but the lowest cost per byte stored. In between these two extremes are a variety of disks, which provide response time and cost per byte in between those for RAM and tape. Such disks include hard disks, "Winchester" disks, and floppy disks.

All of these storage devices are subject to information loss or garbling, which often can be catastrophic. CMOS RAM can lose its information if a circuit malfunctions or if "noise" exists on a communication bus. Information can be lost on disks, tapes, and other magnetic surfaces by a magnetic field, physical damage to the magnetic surface, or noise on the communication bus. Other causes of information loss include software which "goes haywire" or programmer/operator error. This lost information is generally referred to as "erasures". It is therefore desirable and commonly accepted within the computer industry to provide cost effective "backup" for the various memory devices. "Backup" involves periodically storing the contents of a first storage device on a second storage device, so that the contents of the first storage device can be restored or recovered in the event of damage to, or information loss from, the first storage device.

Over the evolution of memory devices, disks have acquired the largest acceptance as striking an appropriate compromise between response time and cost per byte for the large volumes of information used in conjunction with a digital computer. A variety of magnetic tape "backup" systems have been developed on which the digital information on the disk can be periodically stored or backed up. Several particularly effective tape backups are those sold as Models 110 and 310 by Irwin Magnetic Systems, Inc., of Ann Arbor, Mich., the assignee of the present application. The structure and operation of some of these systems are illustrated in U.S. patent application Ser. No. 589,007, filed Mar. 13, 1984, by Chambors et al, entitled Method and Apparatus for Pre-Recording Tracking Information on Magnetic Media; U.S. Pat. No. 4,472,750, issued Sept. 18, 1984, to Klumpp et al., entitled Data Record with Pre-Recorded Transducer Positioning Signals, and System for Utilizing Same; and U.S. Pat. No. 4,468,712, issued Aug. 28, 1984, to Mueller et al., entitled Positioner Apparatus for Tape Recorder Heads. Although these systems constitute a significant advance and enjoy wide-spread commercial success today, the assignee of the present application has continually sought to improve the performance and efficiency of these backup systems.

In recording the backup information on the magnetic tape, it is desirable to provide redundant information to guard against loss of information on the magnetic tape. If a portion of the backup data information is lost for one reason or another, the lost information (or erasure) may be recoverable from the redundant information. One approach is to record two complete copies of the disk contents on the tape. Consequently, if one copy of the information is lost, the other copy can be consulted to complete the information restoration. This approach is wasteful of tape space and requires excessive time during backup. Typically, the computer cannot be utilized while the backup process is occurring; and therefore this approach is undesirably wasteful of time. A second approach is to calculate redundant information using an error-correction code. Redundant information calculated using this method typically requires less space than a complete second copy of the data information, while still enabling recovery from at least some loss of information. Typically, redundant information is stored in blocks physically separate from the data blocks; and a look-up table is provided on the tape to provide a mapping between the data blocks and the corresponding redundant blocks. This approach also has its drawbacks. If the look-up table is erased or otherwise lost, it is impossible to determine the correspondence between the data blocks and the redundant blocks required to read the redundant information and restore the data information to the disk. Additionally, both the writing and reading are undesirably slow because the mapping table must be repeatedly consulted and the various data and redundant blocks accessed at separate locations on the tape.

The aforementioned problems are overcome in the present invention wherein a system and method are provided for efficiently and rapidly calculating and storing redundant information in a magnetic tape backup unit.

In a first aspect of the invention, (1) the data information is formatted into data sectors, (2) redundant information is calculated for a group of data sectors and stored in one or more redundant sectors, and (3) the group of data sectors and the corresponding redundant sectors are written sequentially to the tape as a block of information. Preferably, the redundant sectors are written sequentially at the beginning or end of each block. This method and system have significant advantages over known backup units. First, the redundant information is interleaved with the data information in a known pattern at known locations, eliminating the need for mapping tables to correlate the data information and the redundant information. Second, the present invention operates faster than known systems because the redundant information is stored physically adjacent the data information to which it relates. It is not necessary to physically transport the tape between separate physical locations to access related data and error-correction information. This aspect of the invention greatly enhances the speed and reliability of the resultant backup system.

In a second aspect of the invention, the method includes the steps of (1) formatting the data information into groups of data words, (2) calculating one or more redundant words for each group using a Reed-Solomon code, and (3) writing the related data and redundant words to the tape as a block of backup information. Utilizing a Reed-Solomon code improves both the efficiency and the speed at which the backup system operates. First, the chosen Reed-Solomon code is a "high rate" code meaning that relatively little redundant information is required to correct a relatively large number of erasures. Second, the code is a "systematic" code meaning that the original data is unchanged during storage, so that decoding is unnecessary if erasures do not occur. Third, the redundant information can be readily encoded with a relatively fast algorithm and/or a relatively simple hardware configuration.

These and other objects, advantages, and features of the invention will be more readily understood and appreciated by reference to the detailed description of the preferred embodiment of the drawings.

FIG. 1 shows a conceptual block of backup information including data and redundant sectors as generated by the present invention;

FIG. 2 shows the physical tape format of the backup blocks; and

FIGS. 3-7 are flow charts showing the progam flow of the encoding and decoding software.

The data information written to the tape from the disk will hereinafter be referred to as data words and/or data bytes. The redundant information calculated and written to the tape will hereinafter be referred to as redundant words, redundant bytes, error-correction code (ECC) words, and/or error-correction code (ECC) bytes. In the preferred embodiment, each data word or redundant word includes a single byte. The present invention is applicable to and encompasses multibyte words also. The data bytes are arranged or formatted into sectors, each of which contains 1024 (1k) bytes. For every 16 data sectors, two sectors of redundant bytes are created. Each byte in each redundant sector is a function of the corresponding bytes in the sixteen data sectors. A total of 18 sectors--sixteen data sectors and two redundant sectors--comprise a block. The format of the tape and the encoding of the redundant information comprise two aspects of the present invention.

As currently implemented, the backup system of the present invention is capable of storing 20 megabytes (20 M) of data information on a single data cartridge. The construction of the backup unit is generally well-known to those having ordinary skill in the art, for example as illustrated in the above-noted U.S. patent application No. 589,007 and U.S. Pat. Nos. 4,472,750 and 4,468,712. Such data tape drives have been manufactured and sold by the assignee of the present application as Models 110 and 310. The data cartridges are those sold as Models TC200 and TC400 by Irwin Magnetic Systems, Inc. of Ann Arbor, Mich.; those manufactured and sold as Models DC1000 and DC2000 by Minnesota Mining and Manufacturing Company of Minneapolis, Minn.; and those manufactured and sold as Models Microtape 1000 and Microtape 2000 by Data Electronics, Incorporated of San Diego, Calif.

A. Conceptual Format

The conceptual format of a tape encoded utilizing the system and method of the present invention is illustrated in FIG. 1. The data information received from the disk is formatted into sectors, each of which includes 1024 8-bit bytes. Sixteen data sectors are included within each block 10 and are denoted DATA 1 through DATA 16. Consequently, each block 10 includes sixteen kilobytes of data information. The words within each sector are sequentially ordered and denominated 0-1023. As conceptually illustrated in FIG. 1, the sectors are arranged in table format with corresponding words in each sector (e.g. word 0 of each sector) arranged side by side. The bytes within each corresponding sector at a given location are hereinafter referred to as corresponding data bytes.

For each group of sixteen corresponding bytes (one byte from each of the sixteen data sectors), two redundant bytes are generated. These bytes are sequentially ordered in two sectors denoted ECC 1 and ECC 2. One byte in each of the ECC sectors corresponds to one byte in each of the sixteen data sectors and therefore to a group of sixteen corresponding data bytes.

As will be more fully described below, the two ECC sectors are generated from the sixteen data sectors utilizing a Reed-Solomon encoding scheme. Two ECC bytes are generated for each group of corresponding data bytes by "folding" the sixteen data bytes and the two ECC bytes together. Suffice it to say at this point that the two redundant bytes are of such a nature, quality, and/or quantity to enable the unique reconstruction or restoration of any two erased bytes (either data or ECC) based on the remaining sixteen bytes in the group.

B. Physical Format

The conceptual block 10 as illustrated in FIG. 1 is generated within RAM and subsequently written to the tape 12 as illustrated in FIG. 2. All 18 sectors of the physical block are written sequentially on one track of the tape 12. Physically, the sixteen data sectors are written first followed by the two ECC sectors. The ECC sectors have the same physical location in every block. Consequently, a map is not required between the data sectors and/or the ECC sectors in order to locate and correlate this information. The 1024 bytes within each sector are written sequentially to the tape. As is routine to those having skill in the art, appropriate header information is included at the beginning of each sector; and appropriate header information is written at the beginning of each block, for example at point 26 (FIG. 2).

The tape preferably includes 12 tracks denoted track 0 through track 11 identified by designating numerals 28, 30, 32, and 34. The blocks 10 are written to the tape 12 in serpentine format. Specifically, track 0 is first filled from a first end of the tape to second end of the tape; track one is then filled from the second end of the tape to the first end of the tape; and so forth. The physical length of each sector of 1024 bytes is approximately 1 inch.

As briefly mentioned above, the error-correction information is generated using a Reed-Solomon code. The implementation of a Reed-Solomon code is generally well-known to those having ordinary skill in the data transmission art. The symbols or bytes of a codeword in a Reed-Solomon code are elements in a finite field known as a Galois field. In the present application, the Galois field is selected to have 256 elements because the 8-bit data bytes are capable of defining 256 different bytes. The 256-element Galois field is denoted GF(256). A Galois field is a finite set of elements with two operations, addition and multiplication, such that each element has an additive inverse and each nonzero element has a multiplicative inverse. Both operations are closed, meaning that the result of an operation performed on any two elements in the field results in a third element also in the field. All Galois fields with 256 elements are isomorphic, meaning that a one-to-one mapping exists between elements in any two such fields that preserves addition and multiplication.

The concept of a primitive root must also be mentioned at this point. A primitive root q is an element within the field such that the powers of the primitive element generate all nonzero elements in the filed. At least one primitive element exists for each Galois field.

Reed-Solomon codewords can be viewed as polynomials of degree n-1 with coefficients in GF(256), where n is the total number of symbols or bytes, both information and redundant. All Reed-Solomon codewords within a given field are multiples of a polynomial g(x) over GF(256), where g(x) is the codeword generating polynomial.

The minimum distance of a code is the minimum number of symbols in which any two codewords differ. As a general rule, if j erasures are to be corrected, the distance must be at least j+1. If two errors are to be corrected, the distance is three. The polynomial g(x) generates a Reed-Solomon code with minimum distance d if g(x) has roots q.sup.k, q.sup.k+1, . . . , q.sup.k+d-2 for any k. The polynomial g(x) generating a code with minimum distance d is defined as follows: ##EQU1##

Based upon the information supplied by the tape manufacturer, it was decided that a reliable level of performance was to be able to correct up to two erasures in every sixteen data bytes. The probability of three erasures is too small to be dealt with on a routine basis. Indeed, in all tests conducted since the present invention was implemented, no more than two erasures has ever occurred in a single codeword. Accordingly, d in the above equation is selected to be three providing for correction of two erasures. The generator polynomial then becomes: ##EQU2## To facilitate encoding calculations, it is desirable to have as many coefficients as possible in the above equation to be equal to one. Accordingly, the following selection is made in view of the fact that k can be arbitrary:

Therefore, the coefficient of x is the only coefficient not equal to one. In GF(256), q.sup.255 =1 since q.sup.256 must equal itself. Therefore, k=127. In view of this selection, the code generating polynomial is given as follows: ##EQU3## Within GF(256), q.sup.127 +q.sup.128 equals q.sup.69 ; and, as stated above, q.sup.255 equals 1. Therefore:

In GF(256) addition and subtraction are identical to one another--namely both being exclusive ORs when elements are represented as bytes--and the above equation finally becomes:

The software implementing the backup and restoration functions utilizing the present invention are illustrated in FIGS. 3-7. The flow chart for performing disk backup, or tape write, is illustrated in FIG. 3. Within a loop, data bytes are read 302 from the disk into the random access memory (RAM) buffer and arranged or formatted into sixteen sectors of 1024 bytes each. The ENCODE subroutine is called 304 to generate or create the two error-correction code (ECC) sectors related to or corresponding to the sixteen data sectors and placed in sectors 17 and 18 of the RAM buffer. All 18 sectors, including the sixteen data sectors and the two ECC sectors, are then written 306 from the RAM buffer onto the tape as a block 10 of information. A decision 308 is then made to determine whether all disk data has been written to the tape. If so, the backup or write function is complete 310; if not, program flow returns to block 302 wherein additional disk information is backed up onto the tape.

FIG. 4 illustrates the ENCODE subroutine utilized to generate the two ECC sectors based on the sixteen data sectors. Upon commencement, the next byte is selected 402 from each of the data sectors and designated c.sub.2 through c.sub.17. For example, on the first pass through the loop, the first byte is selected from each of the 16 sectors; on the second pass, the second byte is selected from each sector; and so forth. The equation: ##EQU4## is then divided 404 by g(x) to produce a remainder c.sub.1 x+c.sub.0. The coefficient c.sub.1 and c.sub.0 are the ECC bytes and are placed in order in the two ECC sectors to correspond with the sixteen data bytes. For example, on the first pass through the loop, the two ECC bytes will be placed in the first locations in the ECC sectors; on the second pass, the bytes will be placed in the second locations; and so forth. A decision 406 is made based on whether all 1024 data bytes in the sectors have been encoded. If so, control returns 408 to the WRITE routine; if not, flow returns to block 402 wherein the next bytes in each of the sectors are encoded.

FIGS. 5-7 illustrate the program flow wherein the information is reread from the tape and restored to the disk. FIG. 5 illustrates the main control during the restoration or READ function and begins by reading 502 the next block of information, including sixteen data sectors and two ECC sectors, from the tape 12. A decision 504 is made to determine whether all eighteen sectors were read. If so, flow continues to block 506 wherein the data sectors are written to the disk; if not, an attempt is made to reread 508 all unread sectors. The attempt to reread can be made "in a gulp" or using an odd/even scheme to sequentially access the odd and even sectors. After the reread attempt is made, a decision 510 is made to again query whether all eighteen sectors have now been read. If so, the data sectors are written 506 to the disk; if not, a decision 512 is made to determine whether 16 or 17 sectors have been read. If so, the unread sectors can be restored using the Reed-Solomon code, which as disclosed herein will restore up to two erasures. In such a case, erasure correction is performed 514 by calling the appropriate restoration subroutine, and the data sectors are written 506 to the disk.

If sixteen or seventeen sectors are not read, a decision 516 is made to determine whether twelve attempts to reread have been made. If not, another attempt to reread 508 is made; if so, a decision 518 is made to determine whether this is the first twelve tries at a reread. If so, the tape is retensioned 520 and the reread loop beginning with block 508 is reinitiated. The tape is retensioned by transporting it first to one end of the tape, then to the opposite end of the tape, and finally returning the tape to the problem block. Frequently, this retensioning of the tape will enable the sectors to be read. If retensioning of the tape does not enable the sectors to be reread, the subroutine indicates that a failure 520 has occurred and that the data from the tape cannot be recovered. As indicated above, this failure mode has not yet been encountered in rather extensive testing of the present invention. However, if such failure were encountered, extraordinary measures could be taken to read the tape; or the backup information could possibly be recovered from yet another backup media.

The program flow to recover from a single erasure is illustrated in FIG. 6 and denominated RECOVER 1. Processing begins by selecting 602 the next byte from each sector read. One of the parameters passed to the RECOVER 1 subroutine is the location of the erasure, which is in the jth position. Processing continues by solving the following equation which has a single unknown--namely c.sub.j : ##EQU5##

The polynomial g(x) has roots at q.sup.127 and q.sup.128 in GF(256). Because the polynomial on the left side of the above equation is a multiple of g(x), this polynomial also has roots at q.sup.127 and q.sup.128. The summation term in the above equation is known because all of the c.sub.i 's are bytes which can be read. Additionally, since q is a known primitive root, the expression (q.sup.127).sup.i is also known. In the second term of the equation, the factor (q.sup.127).sup.j is also known. Consequently, the single equation can be solved for the single unknown c.sub.j to derive the erased coefficient or missing data byte. After the byte has been recovered, a decision 606 is made to determine whether all 1024 bytes in the unreadable sector have been restored. If so, the subroutine returns 608 to block 514 in FIG. 5; if not, program flow returns to block 602 to continue the data restoration or erasure recovery.

The RECOVER 2 subroutine for restoring two unreadable or erased sectors is illustrated in FIG. 7. The subroutine begins by selecting 702 the next byte from each of the sixteen sectors which were read. The READ routine (FIG. 5) advises the RECOVER 2 subroutine of the location of the erasures, which are in the jth and kth positions. Program flow passes to block 704 wherein the following two equations are solved for the two unknowns c.sub.j and c.sub.k : ##EQU6## The first summation term of each equation can be calculated because c.sub.i is known (i.e. has been successfully read) for all i not equal to j or k. Also, q.sup.127 and q.sup.128 are known. With regard to the second two terms of each equation, (q.sup.127).sup.j, (q.sup.127).sup.k, (q.sup.128).sup.j, and (q.sup.128).sup.k are known. Consequently, the two equations include only two unknowns--namely c.sub.j and c.sub.k --which is solved to produce the two erasures. After the two erased bytes are restored, a decision 706 is made to determine whether all 1024 bytes in each of the unrecovered sectors have been restored. If so, control returns 708 to block 514 in FIG. 5; if not, program flow returns to block 702 wherein the next two erasures are recovered.

Source code for implementing the flow charts illustrated in FIGS. 3-7 is attached hereto as appendix A. The source code is written in C language and will be readily understood and appreciated by those having ordinary skill in the programming art. This implementation is for GF(256) generated by the polynomial:

The disclosed look-up table "log f[ ]" contains the primitive root logs of the ordered entries. For example, the log of the second entry, or 1, is 255; the log for the third entry, or 2, is 1; and so forth. The first entry is never accessed and therefore is arbitrarily given the value zero. The primitive root q of this field is binary 00000010. The look-up table "exp f[ ]" includes entries which are the powers of the primitive root q. For example, q.sup.0 is 00000001; q.sup.1 is 00000010; q.sup.2 is 00000100; and so forth.

The described system and method for encoding and storing digital information on tape, and the resulting tape, comprise a significant enhancement of the reliability and recoverability of the stored information. The present invention also results in significant efficiencies, both in speed and physical tape space. A Reed-Solomon code utilizes relatively little tape space while providing full recoverability from up to two erasures in the sixteen corresponding data bytes. The tape format, wherein the error-correction sectors within a given block are stored adjacent the data sectors, eliminates the need for a mapping table and improves the efficiency and speed at which the back up and restoration functions can be performed.

The above description is that of a preferred embodiment of the invention. Various alterations and changes can be made without departing from the spirit and broader aspects of the invention as set forth in the appended claims, which are to be interpreted in accordance with the principles of patent law including the doctrine of equivalents.