N-dimensional iterative ECC method and apparatus with combined erasure - error information and re-read

BACKGROUND OF THE INVENTION

00011. Field of the Invention

0002The present invention concerns a method and an apparatus for improved re-try error recovery for tape storage drives. The method and apparatus are based on an n-dimensional array of symbols (typically bytes) that are ECC coded with a symbol correcting code (typically an RS code) in each dimension (product code scheme).

00032. Description of the Prior Art

0004When a storage system, such as a tape storage system, reads data from a storage medium, such as tape, erroneous data will be received occasionally because of defects in the medium, tape debris, etc. When erroneous data are detected by an error detection system, an attempt is made to correct the data, or to test the data to determine if the data can be corrected. If the correction process is not successful, the tape must be rewound, and data have to be read again. This is referred to as a re-read. After the re-read is performed, the error detection and error correction process is repeated. The re-read process and the ECC process are performed a predetermined number of times. If the error cannot be corrected after the predetermined number of tries, the data cannot be recovered and the error is referred to as a “fatal” error. The re-read and ECC processes have conventionally been performed as two separate processes for tape storage systems.

0005U.S. Pat. No. 6,920,005, however, discloses combining the re-read process for a storage apparatus with the error correction process. In the procedure disclosed in the U.S. Pat. No. 6,920,005, the performance of a current error recovery operation is compared with the performance of a previous error recovery operation. This is accomplished by applying parameters to the recovery process, and comparing the performance, such as channel statistics, of the recovery operation with those of a previous recovery operation, and then adding parameters.

SUMMARY OF THE INVENTION

0006An object of the present invention is to improve combined re-read and ECC processes by introducing more than one dimension for a dataset into the ECC process. The use of one than more dimension for a dataset in the ECC process provides the opportunity for more sophisticated error decoding procedures, such as iterative ECC decoding, wherein decoding is performed in each dimension iteratively until no new errors can be recovered, or until some other stop criterion is satisfied or reached. Introducing n-dimensional code layout, wherein n is an integer greater than one, also provides the opportunity to merge the re-read process and the ECC process into a single process in a more sophisticated manner with better data recovery probability.

0007Instead of comparing the performance of a current error recovery operation with a previous error recovery operation, the system and method in accordance with the invention compare the result of the correction process, namely an error map. An error map is a map encompassing erroneous symbols in the dataset. The result for the current correction process, namely the error map, may be different from the result of a previous correction process because of randomly-distributed errors or variations in debris for each re-read pass. The performance of the process itself is not measured, and the parameters in the process are not modified or added.

0008In accordance with the inventive method and apparatus, correctable symbol error positions are monitored in each re-read pass. In each re-read pass, the number of symbol errors and symbol error positions may vary depending on the SNR level in the channel, and the amount of debris on the tape. The parameters in the channels, such as off-track values, MR bias values, AGC parameters, etc., are not adjusted for each re-read pass. Instead, the inventive method and apparatus are based on natural variations in error positions for the symbols protected by the ECC code. The aforementioned error map with variable error positions is constructed, and the iterative correction process is performed. In the inventive method and apparatus, parameters are not applied or added in the recovery process. Instead, after each comparison, the error map is updated by deducting symbol errors from the error map, and overriding the corresponding erroneous data symbols with correct data symbols.

DESCRIPTION OF THE DRAWINGS

0009<figref idref="DRAWINGS">FIGS. 1A</figref>, <b>1</b>B, <b>1</b>C, <b>1</b>D, <b>2</b>A and <b>2</b>B illustrate respective examples of error maps for explaining the method in accordance with the present invention.

0010<figref idref="DRAWINGS">FIG. 3</figref> illustrates a C2 sub-dataset with C2 and C1 code words.

0011<figref idref="DRAWINGS">FIGS. 4A and 4B</figref> illustrate a C3 sub-dataset with a C3 code word.

0012<figref idref="DRAWINGS">FIG. 5</figref> is a flowchart for an embodiment of the main process in the iterative algorithm in accordance with the present invention.

0013<figref idref="DRAWINGS">FIG. 6</figref> is a flowchart of an embodiment of the error decoding sub-process in the inventive iterative algorithm.

0014<figref idref="DRAWINGS">FIG. 7</figref> is a flowchart of an embodiment of the erasure decoding sub-process in the inventive iterative algorithm.

0015<figref idref="DRAWINGS">FIG. 8</figref> is a block diagram of an apparatus in accordance with the invention, operating in accordance with the inventive iterative algorithm.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

0016Errors received when reading data from a storage medium typically include two different error types, namely random errors related to SNR in the channel and tape debris, and media defect errors. The media defect will be constant for a given dataset, but the random errors will vary each time the dataset is read.

0017As track width and bit length decrease, and more channels are introduced in tape storage products, the amount of SNR-related errors will increase compared to the number of errors caused by media defects. The SNR-related errors are randomly distributed. This means that when reading the same dataset twice, the amount of errors caused by SNR will be approximately the same, but it can be expected that there will be a variation in the error positions. The errors caused by media defects will have the same error positions from one read to another. The probability of successfully re-reading an uncorrectable dataset and obtaining a better sample of the dataset, which can be corrected, will be smaller as the percentage of randomly distributed SNR-related errors increases in the system.

0018To compensate for this problem and improve the data recovery success, re-reads can be combined with the ECC process into a single error recovery process. Additionally, using an iterative product code, such as an n-dimensional Reed-Solomon code, for error correction in combination with the re-read process, improved correction capabilities can be obtained, compared to conventional methods employing a separate re-read process and error correction process. Although Reed-Solomon (RS) codes are used as an example, the improvement achieved by the method described herein can be obtained using other symbol-correcting product codes other than n-dimensional RS codes, such as LPDC codes.

0019In accordance with the invention, an n-dimensional code, such as a Reed-Solomon code, is combined with an iterative decoding algorithm suitable for “cross probing” and correcting erroneous symbols in the n dimensions. The method and device according to the invention are based on the concept of reducing symbols in an erasure map, meaning that a conventional erasure map is initially generated, and non-erroneous (OK) symbols are deducted from the map as the symbols are corrected by the ECC system.

0020An overview of the inventive method is as follows:

0021An uncorrectable dataset is read from a storage medium. Optionally, an initial error map is constructed from a CRC check or a quick syndrome check. The dataset and the corresponding initial error map are stored in a memory structure S<b>1</b>. An example of such initial error map in that S<b>1</b> is shown in <figref idref="DRAWINGS">FIG. 1A</figref>.

0022The iterative decoding and correction algorithm is performed on S<b>1</b> in all dimensions, designated below as dimensions C<b>1</b>, C<b>2</b> and C<b>3</b>, until a predetermined stop criterion is satisfied. An error map of the remaining errors in S<b>1</b> is constructed. An example of such an error map is shown in <figref idref="DRAWINGS">FIG. 1B</figref>. The dataset is re-read from the medium and stored as a second data structure S<b>2</b>. An initial error map in S<b>2</b> after the re-read is shown in <figref idref="DRAWINGS">FIG. 1C</figref>. The iterative decoding algorithm is performed on S<b>2</b>, and an error map of the remaining errors in S<b>2</b> is constructed. Such an error map in S<b>2</b> is shown in <figref idref="DRAWINGS">FIG. 1D</figref>. The error maps in S<b>1</b> and S<b>2</b> are compared. OK data from S<b>2</b> which are marked as bad in S<b>1</b>, are transferred from S<b>2</b> to S<b>1</b>, and the S1 error map is updated by deducting the errors corrected in this manner. Such an updated error map is shown in <figref idref="DRAWINGS">FIG. 2A</figref>.

0023The iterative decoding algorithm is again performed on S<b>1</b>. If there are new successful corrections, the S1 error map is again updated. Such a further updated error map is shown in <figref idref="DRAWINGS">FIG. 2B</figref>.

0024The method then loops back to another re-read and the process is again repeated a predetermined number of times, or the process is exited if no errors are left in S<b>1</b>.

0025The inventive method is explained as an iterative algorithm in three dimensions C<b>1</b>, C<b>2</b> and C<b>3</b>. The algorithm can be expended, however, to more than three dimensions. The three-dimensional dataset used in the example is formed for ECC code words in each dimension, and thus forms a three-dimensional cube with encoded data. This cube is referred to herein as the dataset.

0026A code word is defined as the smallest amount of data that can be encoded or decoded by the ECC that is selected for use. A code word consists of data and parity symbols.

0027A C1 code word is formed by symbols in the x-dimension in the cube. A C2 code word is formed by symbols in the y-dimension in the cube, and a C3 code word is formed by symbols in the z dimension in the cube.

0028A “slice” through the cube is shown in <figref idref="DRAWINGS">FIG. 3</figref>, representing a C2 sub-dataset. The C2 sub-dataset is defined as a dataset formed by C2 and C1 code words and represents and square area in the x-y plane. The number of C2 datasets equals the number of symbols in a C3 code word.

0029A C3 sub-dataset is defined as a dataset formed by C3 and C2 code words, and equals a square in the y-z plane. The number of C3 sub-datasets equals the number of symbols in a C1 code word, as illustrated in <figref idref="DRAWINGS">FIGS. 4A and 4B</figref>.

0030A syndrome check (or additional CRC check) in the C1 dimension for the C1 code words is used as erasure information for the C2 dimension. The information is used to construct the initial erasure map.

0031As used herein, “erasure” means symbol faults in a code word where the positions of the faulty symbols are known. The faulty positions are used as error positions from code words in another dimension in the cube. The term “symbol error” as used herein means an error in a code word that requires the decoding algorithm to decode the faulty positions in the code word with the use of the symbol information in the code word itself.

0032The algorithm begins with an initial erasure map. The code words in the different dimensions are then decoded with error detection and correction, and an error map is generated by removing symbol error positions from the erasure map. The new error map is used as an input to an erasure decoding algorithm, and a correction process, in the different dimensions.

0033The algorithm makes use of one map for both error and erasure information. It is the use of the map in the decoding method and error or erasure decoding that allows a determination to be made whether the information omitted from the map is erasure information or error information.

0034<figref idref="DRAWINGS">FIG. 5</figref> shows further details of the main iterative algorithm. After starting the algorithm, an erasure map is constructed in all dimensions based on CRC or a syndrome check from the read channels. In the next step, error decoding is performed and the correction process is undertaken for all C2 sub-datasets. The erasure map is updated by deducting errors from the map. Details of the deduction procedure are set forth in <figref idref="DRAWINGS">FIG. 6</figref>.

0035Next, error decoding and correcting is performed for all C3 sub-datasets, and the erasure map is updated by deducting errors from the map.

0036The erasure decoding and correcting are performed for all code words in all remaining directions, and the erasure map is updated.

0037If there are any symbol errors corrected by the aforementioned error and erasure decoding process, a check is made as to whether any symbol errors are left in the erasure map. If the answer to this inquiry is “yes,” then the algorithm loops back to the error decoding and correcting for all C2 sub-datasets, and the algorithm is again iterated.

0038Optionally, before beginning the error decoding and correcting process for all C2 sub-datasets in this next iteration, the error decoding and correcting can be performed for all C1 code words, and the erasure map can be updated by deducting errors there from.

0039If there are no symbol errors left in the erasure map, the iterative algorithm is ended, and the main recovery process is continued. This is also the result if the answer to the preceding inquiry regarding symbol errors corrected by the error or erasure decoding processes is “no.”

0040A flowchart for the error decoding process is set forth in <figref idref="DRAWINGS">FIG. 6</figref>, which applies to all dimensions and is therefore described generically for sub-datasets Cx. A Cx sub-dataset to be processed is selected, and the next code word in the selected sub-dataset is selected, and the number of errors in that code word is calculated. An inquiry is made as to whether there are any errors in this code word. If the answer is “yes,” another inquiry is made as to whether the code word is correctible, If the answer is “no,” then an inquiry is made as to whether there are more code words in the sub-dataset to be processed.

0041If the answer to the inquiry of whether there are any errors in the code word is “no,” then the symbol errors are deducted from the erasure map which are currently marked as erroneous symbols, and the algorithm also proceeds to the aforementioned inquiry as to whether there are more code words in the sub-dataset to be processed. If the answer to that inquiry is “yes,” the algorithm loops back to select the next code word, and the aforementioned procedure is repeated. If the answer to that inquiry is “no,” then an inquiry is made as to whether there are more Cx datasets to be processed. If the answer is “yes,” the algorithm loops back to make a selection of the next Cx sub-dataset to be processed. If the answer to that inquiry is “no,” then the error decoding is finished for all sub-datasets Cx, and the main process is continued.

0042As noted above, in the aforementioned iteration, there is an inquiry as to whether the code word is correctable. If the answer to that inquiry is “yes,” then the algorithm proceeds to calculate the symbol error positions and check whether the calculated error positions are valid positions in the erasure map. If the error positions are not valid, a decoding error has occurred, and this decoding step is ignored and no corrections are made and no error deductions from the erasure map occur. The algorithm then proceeds to the aforementioned inquiry as to whether there are more code words in the sub-dataset to be processed.

0043If the error position is valid, the errors in the code word are corrected, and the erasure map is updated by deducting the corrected errors from the map. The algorithm then again proceeds to the inquiry as to whether there are more code words in the sub-dataset to be processed.

0044The erasure-decoding algorithm is illustrated in a flowchart in <figref idref="DRAWINGS">FIG. 7</figref>. The erasure decoding algorithm is started with the code words in the C1 dimension, and a code word in that dimension is selected for processing. The error information for the selected code word is fetched from the deducted erasure map, and this information is used as erasure information since the erroneous positions in the code word are known.

0045An inquiry is then made as to whether the code word is correctable. If the code word is correctable, the erasures in the code word are corrected, and the erasure map is updated by deducting the corrected erasures from the erasure map. The algorithm then proceeds to inquire whether there are more code words in the dimension to be processed.

0046If the code word is not correctable, the algorithm again proceeds to this same inquiry as to whether there are more code words to be processed. If the answer is “yes,” the algorithm loops back to select the next code word in the selected dimension and the aforementioned process is iterated again.

0047If there are no more code words in the dimension to be processed, an inquiry is made as to whether there are more dimensions to be processed. If so, the next dimension to be processed is selected, and the algorithm loops back to select the first code word in the selected dimension to be processed, and the aforementioned iteration is again done.

0048If there are no more dimensions to be processed, an inquiry is made as to whether any successive erasure correction occurred in the iteration that was just performed. If the answer is “no,” the erasure decoding process in concluded, and the main process continues.

0049If a successful erasure correction in the iteration occurred, then a new iteration is started. If the erasure map is empty, this iteration will be the last iteration. The ECC decoding algorithm runs in a check mode, rather than an erasure correct mode. The new iteration begins with the code words in the C1 dimension at the beginning of the algorithm shown in <figref idref="DRAWINGS">FIG. 7</figref>.

0050A basic block diagram of an apparatus for implementing the aforementioned procedure is shown in <figref idref="DRAWINGS">FIG. 8</figref>. The apparatus includes a write/read head <b>1</b> that interacts with a data storage medium <b>2</b> in a known manner to write digital data on and read digital data from the data storage medium <b>2</b>. For this purpose, the write/read head <b>1</b> is in communication with a control unit <b>3</b> via a write amplifier for that is operational in a write mode, and a read amplifier <b>5</b> that is operational in a read mode. The control unit <b>3</b> is in communication with an ECC unit <b>6</b>, wherein the method described above is performed.

0051Although modifications and changes may be suggested by those skilled in the art, it is the intention of the inventor to embody within the patent warranted hereon all changes and modifications as reasonably and properly come within the scope of his contribution to the art.