Patent Publication Number: US-11049520-B1

Title: Data storage device employing multi-tier coding for magnetic tape

Description:
BACKGROUND 
     Conventional tape drive storage systems comprise a magnetic tape wound around a dual reel (reel-to-reel cartridge) or a single reel (endless tape cartridge), wherein the reel(s) are rotated in order to move the magnetic tape over one or more transducer heads during write/read operations. The format of the magnetic tape may be single track or multiple tracks that are defined linearly, diagonally, or arcuate with respect to the longitudinal dimension along the length of the tape. With a linear track format, the heads may remain stationary relative to the longitudinal dimension of the tape, but may be actuated in a lateral dimension across the width of the tape as the tape moves past the heads. With a diagonal or arcuate track format, the heads may be mounted on a rotating drum such that during access operations both the heads and tape are moved relative to one another (typically in opposite directions along the longitudinal dimension of the tape). 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1A  shows a data storage device according to an embodiment comprising at least one head configured to access a magnetic tape. 
         FIG. 1B  is a flow diagram according to an embodiment wherein data read from the magnetic tape is decoded in three tiers, including a low density parity check (LDPC) type decoder for decoding LDPC type codewords, a parity block, and an erasure code. 
         FIGS. 2A-2C  shows an embodiment wherein each LDPC type codeword spans a diagonal of an array of detected symbols. 
         FIG. 3A  shows an embodiment wherein data written to the magnetic tape is encoded into M blocks of LDPC type codewords, each of the M blocks is covered by a M-blocks parity, and the erasure code covers a plurality of the M blocks of LDPC type codewords and a plurality of the M-blocks parity. 
         FIG. 3B  shows a segment of the magnetic tape according to an embodiment comprising a plurality of M blocks LDPC codewords each having an M-blocks parity, and redundancy of an erasure code that covers the plurality of M blocks and M-blocks parity. 
         FIG. 4  shows an embodiment wherein an M-blocks parity is generated over the M-blocks of LDPC type codewords. 
         FIG. 5  shows control circuitry according to an embodiment for decoding the LDPC type codewords, wherein un-converged codewords are decoded as erased codewords using the erasure code. 
         FIG. 6A  shows an embodiment wherein random errors in the data written to the magnetic tape may be corrected by the LDPC type decoder. 
         FIG. 6B  shows an embodiment wherein burst errors in the data written to the magnetic tape may be corrected by the LDPC type decoder enhanced by hard erasures. 
         FIG. 6C  shows an embodiment wherein a large block of errors in the data written to the magnetic tape may be corrected by the erasure code. 
     
    
    
     DETAILED DESCRIPTION 
       FIGS. 1A and 1B  show a data storage device according to an embodiment comprising a magnetic tape  2  and at least one head  4  configured to access the magnetic tape  2 . The data storage device further comprises control circuitry  6  configured to execute the flow diagram of  FIG. 1B , wherein data is read from the magnetic tape to generate a read signal (block  8 ) which is processed to decode a first M blocks of low density parity check (LDPC) type codewords using a LDPC type decoder (block  10 ). First un-converged codewords out of the first M blocks are decoded using a first M-blocks parity (block  12 ), and second un-converged codewords out of the first M blocks are decoded using an erasure code (block  14 ). It is noted that while  FIG. 1A  shows the magnetic tape as being embedded within the data storage device as an example, in other embodiments the tape may be inserted via a mechanism such as a cartridge. 
       FIG. 2A  shows an embodiment wherein the data storage device comprises a plurality of heads  4   1 - 4   16  that are configured to write/read a plurality of longitudinal data tracks along the length of the magnetic tape  2 . In the example of  FIG. 2A , there are 16 heads that write  16  LDPC type codewords as an array of symbols, wherein each LDPC type codeword spans a diagonal of the of the array. For example, in one embodiment each row of the array consists of 4 kilobytes (4 kB) of data, wherein each cell of a row consists of 4 kB/16=256 bytes. In one embodiment in order to average the signal-to-noise (SNR) across the array, the symbols of each LDPC type codeword are distributed along a diagonal of the array. In the example of  FIG. 2A , a first LDPC type codeword is distributed along a first diagonal of the array as represented by the first shaded cells. In the example of  FIG. 2B , a second LDPC type codeword is distributed along a second diagonal of the array as represented by the second shaded cells. In the example of  FIG. 2C , a third LDPC type codeword is distributed along a third diagonal of the array as represented by the third shaded cells, and so on. Accordingly in the example of  FIGS. 2A-2C , there is a block of 16 LDPC type codewords each consisting of 4 kB and each distributed along a diagonal of the array of symbols written to 16 data tracks. 
       FIG. 3A  shows an embodiment wherein M blocks of LDPC type codewords are written to the magnetic tape, wherein each block comprises a predetermined number of LDPC type codewords (e.g., 16 4 kB codewords as shown in  FIGS. 2A-2C ). An M blocks parity is generated over the M blocks of LDPC codewords, wherein the M blocks parity may comprise one or more parities generated over a predetermined number of the LDPC type codewords.  FIG. 4  shows an example parity (P) generated over a predetermined number of the LDPC type codewords (CW) by XORing the symbols of each codeword. In one embodiment, the resulting parity (P) becomes an additional parity equation enabling a separate iteration of LDPC decoding. In the example of  FIG. 3A , there may be 6 blocks of LDPC type codewords (i.e., M=6) and 6 corresponding parities (P) per parity block, where each of the 6 parities (P) may be generated over a corresponding interleave of the LDPC type codewords in the M blocks of LDPC type codewords. In other embodiments, there may be more or less parities (P) generated over the M blocks of LDPC type codewords, including an embodiment wherein when a lower correction power is acceptable, a single parity (P) may be generated over the M blocks in order to achieve a higher code rate. 
     When the LDPC type decoder is unable to decode all of the LDPC type codewords in the M blocks, the M blocks parity may be used to facilitate the decoding of the un-converged codewords. In the embodiment of  FIG. 3A , there is a third tier of coding in the form of an erasure code that may be generated over a plurality of the M blocks of LDPC type codewords and a plurality of the M-blocks parity. In one embodiment M=6 and the erasure code is generated over 34 of the parity level sub-blocks (i.e., the erasure code is generated over 34×6=204 LDPC blocks or 204×16=3264 4 kB LDPC type codewords). When there are still un-converged codewords remaining after processing with the M blocks parity, the erasure code is used to decode these remaining un-converged codewords.  FIG. 3B  shows a segment of the magnetic tape  2  according to an embodiment comprising a plurality of M blocks LDPC codewords  16   1 - 16   N  each having an M-blocks parity  18   1 - 18   N  such as shown in  FIG. 3A , and redundancy  20  of an erasure code that covers the plurality of M blocks  16   1 - 16   N  and M-blocks parity  18   1 - 18   N . 
       FIG. 5  shows control circuitry according to an embodiment wherein a Viterbi type detector  22  processes the signal samples of a read signal  24  generated by reading a data track on the magnetic tape  2 . The Viterbi type detector  22  generates a reliability metric  26  (e.g., a log-likelihood ratio (LLR)) for each symbol of a LDPC type codeword. The LLRs of each LDPC type codeword are then iteratively processed using an LDPC type decoder  28 . When the LDPC type decoding fails due to at least one of the codewords failing to converge, the LLRs for at least one of the un-converged codewords are updated using the Viterbi type detector  22 , and the updated LLRs are processed again by the LDPC type decoder  28 . The process of updating the LLRs of an un-converged codeword using the Viterbi-type detector  22  and reprocessing the updated LLRs by the LDPC type decoder  28  may be repeated N1 number of times. In one embodiment, the Viterbi type detector  22  and the LDPC type decoder  28  are replicated a number of times equal to the number of heads and corresponding read signals (e.g., 16 heads in the embodiment of  FIG. 2A ) such that a block of LDPC type codewords are decoded in parallel. 
     After processing the current block of LDPC type codewords over N1 iterations, the LLRs of the un-converged codewords for the current block are stored in a buffer at element  30 . The next block of LDPC type codewords (e.g., as shown in  FIG. 3A ) are then processed by the Viterbi type detector  22  and the LDPC type decoder  28  over N1 iterations. After processing the current block of LDPC type codewords over N1 iterations, the LLRs of the un-converged codewords for the current block are stored in the buffer at element  30 . After processing M blocks of LDPC type codewords such as shown in  FIG. 3A , the corresponding M blocks parity is read from the magnetic tape and used to update the stored LLRs of the un-converged codewords at element  32 . The updated LLRs are again processed by the LDPC type decoder  28 , wherein the LLRs of any remaining un-converged codewords are again processed by the Viterbi type detector  22  and LDPC type decoder  28  over N2 iterations. After the N2 iterations, the LLRs of any remaining un-converged codewords are updated using the M blocks parity at block  32  and the process repeated over N3 global iterations. If after the N3 global iterations there are still un-converged codewords remaining, the un-converged codewords are stored as erased codewords at element  34 . In one embodiment, an erased codeword may be stored as an identifier (e.g., an address) that identifies the codeword within the M blocks of LDPC codewords as being an erased (un-converged) codeword. After converting the un-converged codewords to erased codewords, in one embodiment the LLRs of the current M blocks of codewords stored at element  30  may be “deleted” so that the memory may be reused for a subsequent M blocks of codewords. This process is repeated for N of the M blocks of LDPC type codewords such as shown in  FIG. 3A , wherein after processing N of the M blocks the redundancy of the erasure code is read from the magnetic tape as shown in  FIG. 3B , and the erased codewords stored at element  34  of  FIG. 5  are decoded using the erasure code decoder  36 . 
     Any suitable technique may be employed to update the LLRs of a codeword using the M blocks parity. In one embodiment when processing the LLRs of the codewords corresponding to one of the M blocks parity bits, at least one of the LLRs across the un-converged codewords is modified so that the likelihood of a codeword bit flips its binary state, thereby satisfying the parity. When at least one of the LLRs is updated correctly, it improves the likelihood the corresponding codeword will converge during the subsequent processing by the LDPC type decoder  22 . As each un-converged codeword converges, there is a corresponding improvement in the update accuracy of the M blocks parity, further improving the likelihood of recovering all of the un-converged codewords. A suitable technique for updating the LLRs of un-converged codewords using the M blocks parity is disclosed in U.S. Pat. No. 9,632,863 entitled “TRACK ERROR-CORRECTION CODE EXTENSION,” the disclosure of which is incorporated herein by reference. 
     In one embodiment, an inline parity may be generated over each of the M blocks of LDPC type codewords shown in  FIG. 3A , wherein the inline parity may be used to update the reliability metrics during the Viterbi type detection and LDPC type decoding iterations. That is, in one embodiment the M blocks parity shown in  FIG. 3A  may be augmented by an inline parity generated over each block of codewords. In yet another embodiment, the M blocks parity may be generated over interleaves of symbols in each LDPC type codeword, such as by generating a first parity over a first interleave (e.g., even interleave) of symbols of the LDPC type codewords, and generating a second parity over a second interleave (e.g., odd interleave) of symbols of the LDPC type codewords. In still another embodiment, multiple parities may be generated over different symbol resolutions (e.g., every ½ and every ¼ symbols) and the reliability metrics updated in a cascading manner starting with the lowest resolution parity. Examples of this embodiment are disclosed in U.S. Pat. No. 10,373,645 entitled “DATA STORAGE DEVICE DYNAMICALLY GENERATING EXTENDED REDUNDANCY OVER INTERLEAVES OF A DATA TRACK,” the disclosure of which is incorporated herein by reference. 
     The processing order shown in the embodiment of  FIG. 5  is to perform the M blocks parity update, followed by LDPC type decoding, followed by Viterbi type detection, followed by another LDPC type decoding, and so on. In other embodiments, there may be a different processing order, such as M blocks parity update, followed by LDPC type decoding, followed by another M blocks parity update, followed by a number of Viterbi/LDPC iterations. Various examples of different processing orders are disclosed in U.S. Pat. No. 10,592,334 entitled “DATA STORAGE DEVICE EMPHASIZING PARITY SECTOR PROCESSING OF UN-CONVERGED CODEWORDS,” the disclosure of which is incorporated herein by reference. 
     Any suitable erasure code may be employed in the embodiment of  FIG. 3A . In general, an erasure code generates redundancy by combining J of the LDPC type codewords, such as by XORing the LDPC type codewords, to generate K redundancy blocks. The K redundancy blocks are then capable of recovering K unrecoverable (erased) codewords by combining the K redundancy blocks with the recovered codewords. Referring to the embodiment shown in  FIG. 3A , the redundancy of the erasure code may be generated in any suitable manner, such as by using a 24-way 8-bit symbol deep-interleave erasure code. 
     In one embodiment, the three tier coding scheme shown in the embodiment of  FIG. 3A  enables the control circuitry to correct various types of random and burst errors that may be typically seen in a magnetic tape storage system.  FIG. 6A  shows a segment of a magnetic tape  2  wherein the black dots represent random errors in the recorded data that are corrected using the first and second tiers of the coding scheme of  FIG. 3A  (i.e., the Viterbi/LDPC decoding augmented by the M blocks parity update).  FIG. 6B  shows a segment of the magnetic tape  2  wherein a long burst error  38  along the length of the tape segment may be caused by a defective read head, or a short burst error  40  may be caused by failing to acquire a sync mark. Both of these types of burst errors may be corrected using the first and second tiers of the coding scheme of  FIG. 3A , wherein in one embodiment the LDPC type decoder may be further augmented by generating hard erasures when a burst error is detected from the read signal. An example of augmenting a LDPC type decoder using hard erasures is disclosed in U.S. Pat. No. 10,417,089 entitled “DATA STORAGE DEVICE EXTENDING ERASURES FOR LDPC-TYPE DECODING,” the disclosure of which is incorporated herein by reference.  FIG. 6C  shows a segment of the magnetic tape  2  wherein a large block  42  of codewords are effectively erased due, for example, to the heads lifting off the magnetic tape during a read operation. The first and second tiers of the coding scheme (Viterbi/LDPC decoding and M blocks parity update) may be unable to correct a large block of erased codewords, whereas the third tier of the coding scheme of  FIG. 3A  (erasure code) is well suited for correcting this type of large block error. In one embodiment, a large block error  42  shown in  FIG. 6C  occurs infrequently as compared to the random errors of  FIG. 6A  or the burst errors of  FIG. 6B . Accordingly in one embodiment, the first and second tiers of the coding scheme are typically sufficient to correct a majority of the errors, whereas the third tier erasure code may be needed occasionally to recover an infrequently occurring large block error. 
     Any suitable control circuitry may be employed to implement the flow diagrams in the above embodiments, such as any suitable integrated circuit or circuits. For example, the control circuitry may be implemented within a read channel integrated circuit, or in a component separate from the read channel, such as a data storage controller, or certain operations described above may be performed by a read channel and others by a data storage controller. In one embodiment, the read channel and data storage controller are implemented as separate integrated circuits, and in an alternative embodiment they are fabricated into a single integrated circuit or system on a chip (SOC). In addition, the control circuitry may include a suitable preamp circuit implemented as a separate integrated circuit, integrated into the read channel or data storage controller circuit, or integrated into a SOC. 
     In one embodiment, the control circuitry comprises a microprocessor executing instructions, the instructions being operable to cause the microprocessor to perform the flow diagrams described herein. The instructions may be stored in any computer-readable medium. In one embodiment, they may be stored on a non-volatile semiconductor memory external to the microprocessor, or integrated with the microprocessor in a SOC. In yet another embodiment, the control circuitry comprises suitable logic circuitry, such as state machine circuitry. In some embodiments, at least some of the flow diagram blocks may be implemented using analog circuitry (e.g., analog comparators, timers, etc.), and in other embodiments at least some of the blocks may be implemented using digital circuitry or a combination of analog/digital circuitry. 
     In addition, any suitable electronic device, such as computing devices, data server devices, media content storage devices, etc. may comprise the storage media and/or control circuitry as described above. 
     The various features and processes described above may be used independently of one another, or may be combined in various ways. All possible combinations and subcombinations are intended to fall within the scope of this disclosure. In addition, certain method, event or process blocks may be omitted in some implementations. The methods and processes described herein are also not limited to any particular sequence, and the blocks or states relating thereto can be performed in other sequences that are appropriate. For example, described tasks or events may be performed in an order other than that specifically disclosed, or multiple may be combined in a single block or state. The example tasks or events may be performed in serial, in parallel, or in some other manner. Tasks or events may be added to or removed from the disclosed example embodiments. The example systems and components described herein may be configured differently than described. For example, elements may be added to, removed from, or rearranged compared to the disclosed example embodiments. 
     While certain example embodiments have been described, these embodiments have been presented by way of example only, and are not intended to limit the scope of the inventions disclosed herein. Thus, nothing in the foregoing description is intended to imply that any particular feature, characteristic, step, module, or block is necessary or indispensable. Indeed, the novel methods and systems described herein may be embodied in a variety of other forms; furthermore, various omissions, substitutions and changes in the form of the methods and systems described herein may be made without departing from the spirit of the embodiments disclosed herein.