Interleaved redundancy sector for correcting an unrecoverable sector in a disc storage device

A disc drive storage system is disclosed that employs sector level and track level error correction systems (ECS), wherein the track level error correction capability is increased by interleaving the track level redundancy. In the preferred embodiment, each sector on the disc is divided into three interleaves or codewords with sector level redundancy generated for each interleaved codeword. The track level redundancy is then generated by combining the interleaved codewords separately according to a predetermined error correction operation (e.g., byte XOR) to form an interleaved redundancy sector. During readback, the sector level ECS generates an erasure pointer corresponding to an uncorrectable codeword within a sector for use by the track level ECS. In this manner, the track level ECS can correct up to three uncorrectable sectors when three sectors contain a single uncorrectable codeword in separate interleaves.

FIELD OF INVENTION 
The present invention relates to disc storage systems (such as magnetic and 
optical), particularly to an error detection and correction system that 
employs sector level redundancy for detecting and correcting errors within 
a data sector, and track level redundancy for correcting a data sector 
unrecoverable at the sector level. 
CROSS REFERENCE TO RELATED APPLICATIONS AND PATENTS 
This application is related to co-pending U.S. patent application Ser. No. 
08/326,126 entitled "Error Correction Method and Apparatus." This 
application is also related to U.S. Pat. No. 5,446,743 entitled 
"Coefficient Updating Method and Apparatus for Reed-Solomon Decoder." The 
above referenced U.S. patent application and U.S. patent are assigned to 
the same entity and are hereby incorporated by reference. 
BACKGROUND OF THE INVENTION 
Disc drive storage devices typically store binary data onto the surface of 
a rotating disc in divisible units referred to as tracks, where each track 
is divided into a number of data units referred to as sectors. In magnetic 
storage devices, for example, the digital data serves to modulate a write 
current in a inductive recording head in order to write a series of 
magnetic flux transitions onto the surface of a magnetizable disc in a 
series of concentric, radially spaced tracks. And in optical recording 
systems, the digital data may modulate the intensity of a laser beam in 
order to record a series of "pits" onto the surface of an optical disk in 
spiral tracks. 
The host system connected to the storage device accesses the disc drive by 
writing and reading data to and from a particular sector. The disc drive 
positions a recording head (or transducer) over the track containing the 
requested sector, waits for the disc to rotate until the recording head is 
over the requested sector within the track, and then performs a write or 
read operation on the sector. The latency associated with spinning the 
disc to the requested sector is a significant factor in the overall 
operation speed (access time) of the disc drive. Once the transducer 
reaches the target track, the storage system must wait for the disc to 
complete one-half a revolution on average to reach the target sector for 
every read and write operation requested. 
The sectors on a track typically include user data and appended sector 
level redundancy symbols for detecting and correcting errors in the user 
data when reading the sector from the disc. During a read operation, a 
sector level error correction system (ECS) uses the sector level 
redundancy symbols to detect and correct errors in the user data that 
occur due, for example, to noise or defects in the recording/reproduction 
process. If the number of errors detected exceeds the error correction 
capability of the sector level ECS, then depending on the nature of the 
errors, the entire sector may be unrecoverable. Random errors caused by 
noise in the reproduction process (e.g., electronic noise induced in the 
read signal) are referred to as "soft errors" because they may not 
necessarily render the sector permanently unrecoverable. That is, the 
storage system can "retry" the read operation until the number of soft 
errors is within the error correction capability of the sector level ECS. 
Permanent errors, or "hard errors", are typically associated with defects 
(drop-outs, aberrations, etc.) on the surface of the disc which render the 
medium permanently unrecoverable if the number of hard errors exceeds the 
error correction capability of the sector level ECS. Further, every sector 
typically includes a preamble field and a sync mark for use by timing 
recovery in synchronizing to the data in the sector. If a hard error 
corrupts this timing information, then the entire sector may become 
completely unreadable due to the inability to synchronize to the data. 
In the context of this application, an unrecoverable sector refers either 
to a readable but uncorrectable sector at the sector level, or an 
unreadable sector due, for example, to an inability to synchronize to the 
sector data. 
There are prior art disc storage systems which attempt to protect against 
losing an entire sector that has become unrecoverable at the sector level. 
For example, U.S. Pat. No. 5,392,290 entitled "System and Method for 
Preventing Direct Access Data Storage System Data Loss from Mechanical 
Shock During Write Operation," suggests using a parity sector within each 
track, wherein the parity sector comprises the XOR (parity) of all of the 
data sectors for that track. In this manner, if any one of the data 
sectors becomes unrecoverable, it can be completely reconstructed using 
the parity sector. 
The parity sector in the above scheme is updated during each write 
operation by first reading the sector that is to be over written and 
"backing out" its contribution to the parity sector (by XORing it with the 
parity sector). Then, the new sector is written to the disc and added 
(XORed) into the parity sector. The updated parity sector is then written 
back to the disc. If a particular sector is determined unrecoverable 
during a read operation, then to recover that sector the storage system 
reads and XORs the other sectors in the track (including the parity 
sector), and the result of the XOR operation is the unrecoverable sector. 
This track level parity sector scheme for recovering an unrecoverable 
sector has not been widely employed in disc storage systems due to the 
intolerable increase in latency associated with updating the parity sector 
during each write operation. That is, the storage system must seek to the 
sector to be over written, read that sector (or sectors), and "back out" 
its contribution to the parity sector. Then, it must wait for a complete 
revolution in order to write the new sector (or sectors). Finally, the 
storage system must wait for the disc to spin to the parity sector so that 
it can over write it with the updated parity sector. Further, the 
revolution of latency associated with backing out the contribution of the 
target data sectors from the redundancy sector applies even if the write 
range spans one less sector than the entire track. 
Another problem inherent in the prior art track level parity sector scheme 
is that it can correct only one unrecoverable sector per track. Thus, if 
two or more sectors on a track become unrecoverable, the prior art parity 
sector scheme is rendered useless. 
Yet another problem not addressed by the prior art parity sector scheme is 
that a sector can become unrecoverable due to errors associated with a 
write operation on that sector. For example, a defect on the medium may 
result in a hard error depending on how the sector data is written to the 
disc. That is, a corrupted write operation may result in excessive hard 
errors which render the sector uncorrectable, whereas another write 
operation may not. For example, a phenomena that can result in an 
unrecoverable sector, known as "high write", occurs when an anomaly on the 
medium causes the fly height of the recording head to increase, thereby 
decreasing the magnetization strength of the inductive write signal. Thus, 
if a first sector on a track becomes unrecoverable due to a corrupted 
write operation, and no attempt is made to read that first sector before a 
second sector becomes unrecoverable due to a subsequent corrupted write 
operation, then the prior art parity sector scheme will be unable to 
recover either sector. 
Consequently, most disc storage systems do not employ a track level parity 
sector; instead, they take other precautions to protect against influences 
which may render a sector unrecoverable. Namely, to protect against hard 
errors which may render a sector unreadable due to defects in the medium 
at the preamble or sync mark fields, the entire disc is tested during 
manufacturing. If it is determined that the preamble or sync mark field 
cannot be read due to defects in the medium, then that sector is mapped to 
a spare sector. A similar "defect scan" and "defect mapping" can be 
performed for the entire sector to determine if the number of resulting 
hard errors will exceed the error correction capability of the sector 
level ECS. Alternatively, a system designer may increase the error 
correction capability of the sector level ECS to decrease the probability 
that a sector will become uncorrectable. 
The problem with scanning the medium for defects during the manufacturing 
process and mapping bad sectors to spare sectors is that it does not 
account for "grown defects", defects that arise during the lifetime of the 
storage system. Grown defects include, for example, invading foreign 
particles which become embedded onto the surface of the disc, or external 
shocks to the storage system which can cause the transducer to nick the 
surface of the disc. Furthermore, there are problems associated with 
increasing the error correction capability of the sector level ECS to 
overcome grown defects. Namely, it becomes prohibitively complex and 
expensive to implement, and it reduces the capacity of the storage system 
due to the increase in the sector level redundancy bytes. 
There is, therefore, a need for a disc storage system that can protect 
against read errors rendering a sector unrecoverable, without increasing 
the cost and complexity of the sector level ECS, and without the above 
mentioned problems associated with the prior art track level ECC scheme. 
SUMMARY OF THE INVENTION 
A disc storage system is disclosed which comprises a sector level ECS for 
correcting errors within a sector during readback, and a track level ECS 
for correcting a sector that becomes unrecoverable at the sector level 
either because the number of hard errors exceeds the error correction 
capability of the sector redundancy, or because the sector is unreadable 
due, for instance, to an inability to synchronize to the sector data. The 
sector level ECS is preferably implemented using a high order Reed-Solomon 
code capable of correcting multiple random burst errors, and the track 
level ECS is preferably implemented using a less complex error correction 
code such as byte XOR or a first order Reed-Solomon code. 
The track level error correction capability is increased by interleaving 
the track level redundancy. In the preferred embodiment, each sector is 
divided into three interleaves or codewords with sector level redundancy 
generated for each interleaved codeword. The track level redundancy is 
then generated by combining the interleaved codewords separately according 
to a predetermined error correction operation (e.g., byte XOR) to form an 
interleaved redundancy sector. During readback, the sector level ECS 
generates an erasure pointer corresponding to an uncorrectable codeword 
within a sector for use by the track level ECS. In this manner, the track 
level ECS can correct up to three uncorrectable sectors (as opposed to one 
uncorrectable sector in the above prior art implementation) when three 
sectors contain a single uncorrectable codeword in separate interleaves.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT OVERVIEW 
FIG. 1A shows the general format of a disc 2 comprising a number of data 
tracks where each track comprises a number of data sectors and a 
redundancy sector. The redundancy sector has the same format as the data 
sectors except it may optionally contain a few extra bytes for storing 
status as described below. The redundancy sector is generated according to 
a predetermined error correction operation (e.g., byte XOR) over the data 
sectors for use in correcting a data sector that has become unrecoverable 
at the sector level. 
An example track 1 on the disc 2 comprises five sectors, where each sector 
4 (as shown in FIG. 1B) comprises a preamble 6 for use in synchronizing 
timing recovery, a sync mark 8 for use in synchronizing to the user data 
12, and ECC redundancy bytes 14 for use in detecting and correcting errors 
in the user data 12 at the sector level. Each sector may optionally 
comprise an ID field for storing the sector number, but most disc storage 
systems have moved to an ID-less format wherein the sector numbers are 
derived from information stored in embedded servo wedges (not shown). If 
the preamble 6 or sync mark 8 become unreadable due, for example, to a 
defect in the medium, then the storage system may be unable to synchronize 
to the user data 12 and the entire sector may become unreadable. The 
sector may also become uncorrectable at the sector level if the number of 
hard errors exceeds the error detection and correction capabilities of the 
sector ECC redundancy bytes 14. 
Referring again to FIG. 1A, the operation and drawbacks of prior art 
attempts to incorporate a track level parity sector for recovering a 
sector, as compared to the method of the present invention, will now be 
described. Consider, for example, that the host system directs the storage 
device to write new data to SECTOR 0. If the recording head arrives at the 
target track 4 just after the beginning of SECTOR 0, then the storage 
system must wait for the disc to complete a full revolution in order to 
read the current content of SECTOR 0. Then, the disc must make another 
revolution so that the storage system can read the parity sector 
(redundancy sector), back out the current content of SECTOR 0 from the 
parity sector (by XORing it with the parity sector), XOR the new 
information into the parity sector and over write SECTOR 0 with the new 
information. Then, the storage system must wait for the disc to make yet 
another revolution so that it can write the updated parity sector to the 
disc. In the worst case, then, a write operation in the prior art 
implementations of a parity sector requires three revolutions of latency, 
and over two revolutions on average to write a single sector. Further, the 
revolution of latency associated with backing out the old contribution of 
the target data sectors from the redundancy sector applies even if the 
write range spans one less sector than the entire track. 
In addition to the above described latency problem, the prior art 
implementations are capable of correcting only one unrecoverable data 
sector per track. Furthermore, the prior art makes no attempt to verify 
the validity of the data sectors before writing new information to the 
track. Thus, if there is already an unrecoverable data sector on a track 
and a corrupted write operation renders another sector unrecoverable, then 
both sectors are lost permanently. The present invention addresses these 
problems, and provides other unexpected benefits and advantages over the 
prior art. 
ERROR CORRECTION SYSTEM 
FIG. 1C schematically illustrates the error correction system (ECS) 
according to an embodiment of the present invention, including a sector 
level ECS and a track level ECS. The sector level ECS comprises a 
redundancy/syndrome generator 20, a Reed-Solomon decoder 22 an erasure 
location value generator 24, a root search and error/erasure magnitude 
generator 26, and a register 28 and an XOR gate 30 for correcting data 
symbols in a codeword stored in data buffer 32. The track level error 
correction system comprises a redundancy buffer 34 for storing the 
redundancy sector as it is generated, and a combining circuit 36 for 
combining the data sectors and redundancy sector according to a 
predetermined error correction operation, such as byte XOR. A 
timer/controller 38 controls the overall operation of the system by 
executing the sector level and track level error correction operations 
described below. 
During a write operation, the storage system receives user data from a host 
system over a system bus 40 and stores the data in a data buffer 32 with a 
capacity to hold several sectors of data. When the system is ready to 
write a sector of data to the disc 42, the timer/controller 38 clears the 
redundancy buffer and reads a sector of user data from the data buffer 32. 
As the sector is read from the buffer, a the redundancy/syndrome generator 
20 generates sector level redundancy bytes 14 (shown in FIG. 1B) which are 
appended to the sector as it is written to the disc 42. Concurrently, the 
redundancy sector stored in the redundancy buffer 34 is updated by 
combining it (e.g., XORing) 36 with the user data. This is accomplished by 
reading an appropriate byte from the redundancy buffer 34 and combining 36 
it with the corresponding user data byte applied over the system bus 40. 
The result is then written back to the redundancy buffer 34 over line 44. 
Depending on whether the storage system is configured into a "immediate 
redundancy regeneration" write mode or "deferred redundancy regeneration" 
write mode, as described below, the contents of the redundancy buffer 
after processing all of the user data to be written to the disc will be 
either the redundancy for the entire track, or the redundancy for the 
sectors written. In either case, the redundancy sector itself is applied 
to the system bus 40 over line 46 and processed by the syndrome/redundancy 
generator 20 to generate sector level redundancy bytes which are appended 
to the redundancy sector as it is written to the disc. 
During a read operation a sector of data is read from the disc 42 and 
applied over line 48 to the system bus 40. A sector reset signal on line 
50 resets the redundancy/syndrome generator 20, the erasure location value 
generator 24 and the timer/controller 38 every time a new sector is about 
to be read from the disc 42. Then, as the next sector is read, the 
redundancy/syndrome generator 20 generates error syndromes for use by the 
decoder circuit 22 and the sector is stored in the data buffer 32 for 
subsequent correction in the event that errors are detected (i.e., 
non-zero syndromes are generated). As described below, the decoder circuit 
22 processes the error syndromes to generate an error location polynomial 
which is processed by the root search and error/erasure magnitude 
generator 26 to determine the location and correction values for the 
errors in the sector. In addition, the decoder circuit 22 may utilize 
erasure pointer information generated by the erasure location value 
generator 24. For instance, a read channel may generate a thermal asperity 
erasure pointer applied over line 52. 
To correct a sector using the sector level ECS, a codeword symbol in error 
is read from the data buffer 32 into register 28 and XORed 30 with the 
error correction value. The corrected symbol is then restored to the data 
buffer 32 and the corrected sector transferred to the host system. The 
sector level error correction operations described above are carried out 
in asynchronous and overlapping steps in order to facilitate 
un-interrupted, or "on-the-fly", transfer of data from the disc 42. 
As mentioned above, there are two situations where a data sector on the 
disc may become unrecoverable. First, the sector may become entirely 
unreadable due to an inability to synchronize to the sector data (because, 
for example, the preamble 6 or sync mark 8 have been corrupted by a defect 
on the medium). The other possibility is that the sector becomes 
uncorrectable; that is, the number of hard errors exceeds the error 
correction capability of the sector level ECS. In these situations, the 
storage system pauses the data transfer and executes the track level error 
correction steps to recover the lost sector using the redundancy sector. 
The track level sector recovery steps are disclosed in detail below, but 
the general operation is as follows. First, the recording head is oriented 
over the first sector on the disc (SECTOR 0). Then the storage system 
attempts to read all of the sectors on the disc including the 
unrecoverable sector and the redundancy sector. As each sector is read, 
the sector data is combined 36 according to a predetermined error 
correction operation (e.g., byte XOR) and the result stored in the 
redundancy buffer 34. The sector data can be combined 36 into the 
redundancy buffer 34 after it has been corrected by the sector level ECS, 
but in the preferred embodiment, the sector data is combined 36 with the 
redundancy buffer 34 as the sector is read from the disc 42 (i.e., the 
uncorrected sector data is combined with the redundancy buffer). In the 
latter embodiment, the error correction values generated by the sector 
level ECS are combined 36 "on-the-fly" with the redundancy buffer 34 so 
that the track level redundancy data accounts for corrections made at the 
sector level. After reading the sectors on the disc, the redundancy buffer 
34 contains either error syndromes for correcting a data sector 
uncorrectable at the sector level, or it contains a reconstructed image of 
an unreadable data sector. 
If the data sector is uncorrectable at the sector level, then it is 
corrected by combining it with the error syndromes in the redundancy 
buffer 34. This is accomplished by reading each symbol of the 
uncorrectable sector from the data buffer 32 and combining it 36 with the 
corresponding syndrome stored in the redundancy buffer 34. The corrected 
symbol is then restored to the data buffer 32. If the data sector is 
unreadable, then it is simply replaced by transferring the contents of the 
redundancy buffer 34 to the data buffer 32. 
WRITE OPERATION 
FIG. 2 is a flow chart illustrating the general steps executed by the 
present invention when writing user data to the disc. When the storage 
system receives a write command from the host 60, which includes the user 
data and the target sectors to write the data, the storage system seeks to 
the corresponding target track 62 that contains the target sectors. As the 
recording head traverses radially across the disc surface, it reads 
information typically contained in embedded servo wedges (not shown in 
FIG. 1A) to determine if the recording head has reached the target track. 
Once at the target track, the redundancy buffer 34 of FIG. 1C is cleared 
64 and the user data is written to the disc according to a pre-selected 
write mode 66. 
The write modes provided by the present invention include "immediate 
redundancy regeneration" 68, "pre-read immediate redundancy regeneration" 
70, "deferred redundancy regeneration" 72, "pre-read deferred redundancy 
regeneration" 74 and "cache deferred redundancy regeneration" 76. Each of 
the above write operations will now be described seriatim--the preferred 
operating mode depends on system dynamics such as the desired performance 
level or whether the recording head is capable of switching between a read 
and write operation between sectors. 
IMMEDIATE REDUNDANCY REGENERATION 
A method for performing a write operation according to the present 
invention will now be described with reference again to FIG. 1A and with 
reference to FIG. 3A. As compared to the above described prior art 
implementation which requires over two revolutions of latency on average, 
the following method requires only 1.5 revolutions of latency on average 
to write a single data sector and update the redundancy sector. Further, 
as the write range approaches the entire track, the overhead associated 
with updating the redundancy sector approaches zero; that is, it requires 
no more latency than a storage system that does not employ a redundancy 
sector. This is a significant advantage over the prior art backing out 
technique which requires an additional revolution of latency even if the 
write range is one sector less than the entire track. 
In short, the present invention decreases the write latency by regenerating 
the redundancy sector for the entire track during each write operation 
rather than backing out the old information in the over written sectors. 
For example, if SECTOR 1 is to be over written and the recording head 
arrives at the target track just after the beginning of SECTOR 0, then the 
storage system waits one revolution to reach the beginning of the track 
(i.e., SECTOR 0). The storage system then reads SECTOR 0 and begins to 
combine the data sectors into a regenerated redundancy sector (stored in 
the redundancy buffer 34) according to a predetermined error correction 
operation, such as byte XOR. After reading SECTOR 0, the storage system 
switches to a write operation, writes the user data to SECTOR 1, and 
combines the user data into the regenerated redundancy sector. Then, the 
storage system switches back to a read operation, reads the rest of the 
sectors on the track (sectors 2-4) and combines their contents into the 
regenerated redundancy sector. Finally, the storage system switches to a 
write operation and over writes the redundancy sector with the regenerated 
redundancy sector stored in the redundancy buffer 34. 
The above described write operation requires a half a revolution on average 
to reach the beginning of the track (i.e., SECTOR 0), and one revolution 
to read the data sectors on the track and write the user data to the 
target sector(s). Thus, the present invention requires only 1.5 
revolutions of latency on average to complete a write operation. 
Furthermore, if a data sector preceding the target sector (e.g., SECTOR 0) 
was determined to be unrecoverable during the write operation, it could be 
corrected using the redundancy sector before writing the user data to the 
disc. That is, the data sectors on the track can be at least partially 
verified before over writing the target sector, thereby protecting against 
a the catastrophic error event due to a write operation rendering a newly 
written data sector unrecoverable when the track already contains an 
unrecoverable data sector. 
FIG. 3A shows a flow chart of the write operation of the present invention 
wherein the redundancy sector is regenerated immediately as the user data 
is written to the disc without "backing out" the overwritten information 
as in the prior art. A variable, REDUND. STATUS, is associated with each 
track which indicates the status of the redundancy sector for the track. 
For the "immediate" write mode of FIG. 3A, the REDUND. STATUS can be 
either READ VALID or NOT VALID, where READ VALID means that the redundancy 
sector is valid for recovering a data sector on the track, and NOT VALID 
means that the redundancy sector cannot be used to recover a data sector. 
As described below, the redundancy status is set to NOT VALID if an 
unrecoverable sector is detected after writing the user data to the target 
sectors. 
After setting the REDUND. STATUS=READ VALID 78, the storage system orients 
in front of the first sector on the track (i.e., sector 0) 80. Then, a 
loop is executed to read all of the data sectors on the track except for 
the target sector(s). The storage system determines whether the next 
sector is in the write range 82--if not, the storage system orients to the 
next sector 90 and attempts to read the sync mark 92. If the sync mark is 
successfully detected 94, then the storage system reads the current sector 
112 and simultaneously combines the data read with the redundancy buffer 
to regenerate the track level redundancy data. Also while reading the 
sector data, the sector level ECS detects and corrects errors in the 
sector data. If the sector is correctable at the sector level 114, then 
the data sector correction values generated by the sector level ECS are 
combined with the redundancy buffer 116 so that the regenerated track 
level redundancy data accounts for the corrections at the sector level. 
After processing the current sector, the storage system checks whether the 
next sector is in the write range 82--if so, the storage system orients to 
the next sector 84 and switches to a write operation to write the user 
data to the disc by over writing the target data sectors 86. While writing 
the user data to the target sectors, the write data is combined with the 
redundancy buffer 88 to further generate the new track level redundancy 
data. 
If the sync mark is not successfully detected 94 or if the sector is 
uncorrectable 114, then the storage system determines whether the 
unrecoverable sector was detected prior to over writing the target data 
sectors 96. If so, then the storage system executes a track level 
reconstruction operation 98 described below in an attempt to recover the 
data sector using the redundancy sector. If the track level sector 
reconstruction is successful 100, then the write operation is restarted 
(i.e., starting at FIG. 2). If the sector reconstruction operation is not 
successful, then the write cooperation continues because the unrecoverable 
sector may be over rewritten before the host system attempts to read it. 
However, the REDUND. STATUS is set to NOT VALID to indicate that the 
redundancy sector could not be successfully regenerated for the track. 
Also, the storage system immediately orients to the first sector in the 
write range 106 since the redundancy sector can no longer be regenerated. 
If an unrecoverable data sector is detected subsequent to over writing the 
target data sectors 96, then again the REDUND. STATUS is set to NOT VALID 
since the redundancy sector cannot be regenerated. 
Once the storage system has processed the last data sector in the track 
118, the REDUND. STATUS for the track is stored in non-volatile memory. 
Preferably, the status is stored on the disc as an extra byte appended to 
the redundancy sector, but it could also be stored in semiconductor memory 
and written to a table on the disc periodically or during a power down 
procedure, for example. The redundancy data stored in the redundancy 
buffer is then written to the redundancy sector for the track after 
appending sector level ECC bytes (and the REDUND. STATUS), thus concluding 
the "immediate redundancy regeneration" write operation. 
It should be noted that in order to achieve minimum latency for the above 
"immediate" write operation, a recording device is required that can 
switch between reading and writing within the gap between sectors. For 
example, many systems employing thin-film recording heads are capable of 
switching operations within the sector gap, whereas many systems employing 
magnetoresistive (MR) recording heads are not. 
The "immediate" write operation can still be implemented in a storage 
system that cannot switch between a read and write operation within the 
sector gap, but it requires up to an additional revolution of latency. 
That is, in a first revolution the storage system reads the data sectors 
outside the write range and develops the track level redundancy. Then in a 
second revolution, the storage system writes the target data sectors and 
combines the write data with the track level redundancy data which is then 
written to the redundancy sector. 
A flow chart of this alternative embodiment of the "immediate" write 
operation is shown in FIG. 3B. After the recording head reaches the target 
track, the storage system sets the REDUND. STATUS to READ VALID 79 and 
immediately orients to the next sector 81 rather than orient to sector 0 
80 as in FIG. 3A. If the current sector is in the write range or is the 
redundancy sector 83, then the storage system skips the sector and orients 
to the next sector 81. If the current sector is outside the write range, 
then the storage system attempts to detect the sync mark 85 and, if 
successful 87, read the sector data 89 and combine it with the redundancy 
buffer 91. If the current sector is correctable at the sector level 93, 
then the sector level correction values are used to correct the redundancy 
buffer 95. 
If the sync mark was not successfully detected 87 or if the current sector 
cannot be corrected at the sector level 93, then the storage system 
performs a track level reconstruction procedure 99 to recover the sector 
using the redundancy sector. If the reconstruction is successful 101, then 
the write operation is restarted (i.e., starting at FIG. 2). Otherwise, 
the REDUND. STATUS is set to NOT VALID 105 and the storage system orients 
to the start of the write range 107; an error event is not sent to the 
host since the unrecoverable data sector may be over written before the 
host requests it. 
Once all of the data sectors outside the write range have been successfully 
read 97, the storage system orients to the first sector in the write range 
107 and writes the new data to the target sector while simultaneously 
combining the write data with the redundancy buffer 109. Then the 
redundancy status is stored 111 (e.g., appended to the track level 
redundancy data as it is written to the disc) and the redundancy buffer is 
written to the redundancy sector 113. 
PRE-READ IMMEDIATE REDUNDANCY REGENERATION 
In the above-described "immediate redundancy regeneration" write operation 
of FIG. 3A, there is a possibility that an unrecoverable data sector on 
the track will be lost permanently due to over writing a data sector 
without first backing-out its contribution to the redundancy sector as in 
the prior art implementation. That is, an unrecoverable data sector 
detected after over writing a target data sector on the track will be lost 
permanently because the redundancy sector is invalid. 
The present invention provides an option to protect against losing an 
unrecoverable data sector: read the data sectors in the track after the 
write range to verify they are recoverable before over writing any of the 
target data sectors. Although when writing a single sector this method 
results in as much write latency as the above-described prior art 
implementation (unless the pre-read is deemed unnecessary as described 
below), the protection provided against losing an unrecoverable data 
sector outside the write range is not provided by the prior art "backing 
out" technique. The "pre-read" method of the present invention could be 
used to modify the prior art such that all the data sectors in the track 
were read in addition to backing out the target sectors from the 
redundancy sector. This modification to the prior art "backing out" 
technique, however, should be considered a novel, non-obvious aspect of 
the present invention. 
The flow chart description for the "pre-read immediate redundancy 
regeneration" method of the present invention is shown in FIG. 3C. First, 
the storage system checks whether the write range spans the entire track 
124. If so, then a pre-read is unnecessary since all of the data sectors 
are about to be over written with new user data. If not over writing the 
entire track, then there is an option to force a pre-read 126 or, if not, 
to determine whether a pre-read is necessary. For example, the storage 
system may inquire into the time elapsed since the last write to the track 
128; if too much time has elapsed, then a pre-read may be forced. 
Otherwise, the storage system checks whether the last sector written to 
the track precedes the write range for the current write operation 130. If 
so, then a pre-read is unnecessary since the sectors over written in the 
previous write operation will be read before over writing the current 
target data sectors, and the data sectors following the write range will 
have been pre-read during the recent, previous write operation. 
If a pre-read is deemed necessary, then the storage system orients to the 
end of the write range 132 since the sectors preceding the write range 
will be read as part of the write operation described with reference to 
FIG. 3A above. The storage system orients to the next data sector 134 and 
attempts to detect the sync mark 136. If the sync mark is successfully 
detected 138, then the storage system reads the current sector and 
determines if it is correctable at the sector level. If the sync mark 
cannot be detected or if the data sector is uncorrectable, then a track 
level reconstruction procedure is executed 140 in an attempt to recover 
the sector using the redundancy sector. If the sector reconstruction 
procedure is successful, then it means all of the data sectors on the 
track have been read successfully and the "pre-read" is complete. If the 
sector reconstruction was not successful, then the "pre-read" is futile 
since there is an unrecoverable sector on the disk. If an unrecoverable 
data sector is not encountered, the "pre-read" operation returns normally 
to the "immediate redundancy regeneration" operation of FIG. 3A after 
reaching the end of the track 146. 
DEFERRED REDUNDANCY REGENERATION 
An alternative method provided by the present invention for writing data 
sectors to the disc, referred to as "deferred redundancy regeneration", 
generates a redundancy sector over the write data. Then, during idle time, 
the storage system regenerates the redundancy sector over the entire 
track. If the write operation results in an unrecoverable sector, then the 
write redundancy sector is used to recover the sector. Again, this method 
reduces the write latency because the over written data sectors are not 
"backed out" of the redundancy sector as in the above-described prior art 
implementation. In fact, this method requires only one revolution on 
average to write a single target data sector and the write redundancy 
sector. Further, as the write range approaches the entire track, the 
overhead associated with updating the redundancy sector approaches zero; 
that is, it requires no more latency than a storage system that does not 
employ a redundancy sector. This is a significant advantages over the 
prior art backing out technique which requires an additional revolution of 
latency even if the write range is one sector less than the entire track. 
A drawback of the present invention, however, is that if an unrecoverable 
data sector exists outside the range of data sectors written, then it will 
be permanently lost after the write operation. As described in more detail 
below, the present invention provides an option to protect against losing 
a data sector outside of the write range by verifying (reading) all of the 
data sectors in the track outside the write range before performing the 
write operation. 
To illustrate the write verify method with reference to FIG. 1A, consider 
that sectors 3 and 4 are to be over written and the recording head reaches 
the target track in the middle of SECTOR 2. When the recording head 
reaches SECTOR 3, it over writes SECTOR 3 and SECTOR 4 with the new user 
data and simultaneously combines the write data into the redundancy buffer 
34 according to a predetermined error correction operation, such as byte 
XOR. Then, when the recording head reaches the redundancy sector, it over 
writes it with the contents of the redundancy buffer 34. During idle time, 
the storage system reads all of the data sectors on the track and 
regenerates the redundancy sector in the redundancy buffer 34 for the 
entire track. If SECTOR 3 or SECTOR 4 is determined to be unrecoverable 
while regenerating the redundancy sector for the entire track, then the 
operation is aborted and the redundancy sector on the disc (write 
redundancy) is used to recover the sector. In this manner, the storage 
system can verify the validity of a write operation which may render a 
sector unrecoverable due, for example, to a "high write". That is, the 
storage system can rectify the situation before another corrupted write 
operation renders yet another sector unrecoverable, thereby losing both 
sectors permanently. 
Turning now to FIG. 4A which is a flow chart description of the deferred 
redundancy regeneration method of the present invention, the storage 
system initializes a status variable, REDUND. STATUS, to WRITE VALID 150. 
The REDUND. STATUS indicates whether the redundancy sector contains 
redundancy data associated with the over written data sectors (i.e., WRITE 
VALID), or for the entire track (i.e., READ VALID). As explained below, 
the REDUND. STATUS may also be set to NOT VALID if the redundancy sector 
is cached in the data buffer 32. The state of the REDUND. STATUS for each 
track must be preserved in order to ensure the integrity of the track 
level ECS. Thus, these variables must be stored in non-volatile memory 
such as on the disc. In the preferred embodiment, the redundancy sector 
contains an extra byte for storing the REDUND. STATUS, and the status is 
updated whenever the redundancy sector is updated. 
Continuing with FIG. 4A, the storage system orients to the first sector in 
the write range 152, writes the user data to the target data sectors and 
simultaneously combines the user data with the redundancy buffer 34 to 
generate the write redundancy 154. If after writing the target data 
sectors there is another write command pending for the track 156, then the 
storage system checks whether the write range for the next command is 
contiguous with the current command 158. If so, then the storage system 
processes the next write command by writing the user data to the 
contiguous target data sectors and updating the write redundancy stored in 
the redundancy buffer 34. If the next write range is not contiguous, then 
the storage system optionally queues an immediate write verify command 160 
which is processed 170 at the conclusion of the current write command. 
As explained below, the immediate write verify 170 verifies the current 
write operation before processing the next write command. If the immediate 
write command is not queued 160, then the current write is not verified 
since the write verify is otherwise performed during idle time of the 
storage system; however, the latency associated with the immediate write 
verify 170 is also avoided. Thus, queuing an immediate write verify is 
optional as configured by the system designer according to the desired 
level of performance. 
Continuing now with FIG. 4A, after writing the user data to the target data 
sectors and generating the write redundancy in the redundancy buffer 34, 
the redundancy status is stored in non-volatile memory 162 (e.g., stored 
in a byte appended to the redundancy sector when it is written to the 
disc). The storage system then writes the redundancy buffer (write 
redundancy) to the redundancy sector 164 and places the track number and 
the sector write range for the entire write operation in a write log 166. 
The "entire write range" includes all write commands processed having 
contiguous write ranges 158. 
The write log, which is preferably stored in the data buffer 32, is 
preferably implemented as a circular list or buffer of data structures. 
The write log stores the track number and sector range for every write 
operation, and as explained below, it is used during idle time to verify 
that the sectors written are recoverable. Since the write log is stored in 
the data buffer 32, it is not protected against a power failure. Thus, if 
the write log is erased, the ability to verify the write operations is 
lost. This is not a fatal error, however, since the redundancy sector for 
the entire track can still be regenerated as long as all the sectors are 
recoverable. In another words, losing the write log is only a fatal error 
if a logged write operation rendered a written sector unrecoverable. In an 
alternative embodiment, the write log is stored in non-volatile memory 
such as on the disc. For example, the sector write range for a track is 
stored in the redundancy sector so that if the write log is lost due to a 
power failure, the sector write range can still be determined. 
The capacity of the write log is finite meaning that it will eventually 
overflow if the pending entries are not processed in time. If the write 
log is a circular buffer, then the oldest entries in the log will be over 
written first. If an entry is over written, the corresponding write 
command cannot be verified but the redundancy for the entire track can 
still be regenerated during idle time. Also, if there are consecutive 
write commands to the same track such that a previous write command has 
not been verified before processing a current write command, then the 
previous write command cannot be verified unless it is processed before 
processing the current write command. Thus, an option not shown in the 
flow charts is to force an immediate write verify operation (see FIG. 4E) 
on any entry in the write log matching the current track number before 
executing the current write command. Also, as explained above, an 
immediate write verify can be queued 160 if a new, consecutive write 
command is detected during a current write operation. Thus, after 
processing the current write command, the storage system immediately 
verifies the write operation 170 before processing the next write command 
172. 
If an immediate write verify has not been queued 168, then the "deferred" 
write operation exits 174 and returns control to the storage system's 
operational firmware. Then, as described below, during idle time the 
storage system processes the entries in the write log to verify the write 
operations, and it simultaneously regenerates the redundancy sector for 
the entire track. 
PRE-READ DEFERRED REDUNDANCY REGENERATION 
Similar to the "immediate redundancy regeneration" write method described 
above, the "deferred" write method is subject to the catastrophic error 
event of a write command rendering a written sector unrecoverable when the 
target track already contains an unrecoverable data sector outside the 
write range. To protect against this situation, the "deferred" write 
method of the present invention optionally pre-reads all of the data 
sectors in the target track outside the write range. Pre-reading the 
target track results in as much latency as the above-described prior art 
"backing out" technique (unless the pre-read is deemed unnecessary as 
described below), but unlike the prior art the present invention protects 
against the above catastrophic error event. 
A flow chart for the "pre-read" operation performed before a "deferred" 
write operation is shown in FIG. 4B. First the storage system checks 
whether the write range is the entire track 176--if so, then the pre-read 
is unnecessary since all of the data sectors are about to be over written. 
Otherwise, the storage system checks whether the pre-read should be forced 
178 as configured by the system designer. If not, then the storage system 
optionally checks whether the last write command to the current track was 
recent 180 since the pre-read is optionally forced if a considerable 
length of time has elapsed since the last write command to the track. If 
the last write to the track was recent, then the storage system checks 
whether a write verify is pending for the track 182 (i.e., whether there 
is a write log entry for the track). If so, then an immediate write verify 
184 is performed for the previous write; otherwise, the pre-read is 
unnecessary since the previous write command has already been verified 
during idle time which means the entire track was already successfully 
read. 
If the pre-read is deemed necessary, then the storage system orients to the 
next sector in the track 186 and checks whether the sector is within the 
write range 188. If so, the storage system skips the sector and continues 
to the next sector until the first sector beyond the write range is 
reached. Then, the storage system attempts to detect the sync mark 190 for 
the current sector and if successful 192, it attempts to read the current 
sector 194. If the sync detection fails 192 or if the current sector is 
uncorrectable at the sector level 196, then the storage system executes 
the track level reconstruction method 198, as described below, in an 
attempt to reconstruct the unrecoverable data sector. If the track level 
reconstruction routine is executed, then the pre-read is complete because 
all of the sectors in the track will have been read. Otherwise, the 
pre-read continues until all of the sectors outside of the write range 
have been read 200. 
CACHE DEFERRED REDUNDANCY REGENERATION 
The performance of the above-described "deferred redundancy regeneration" 
write method can be improved by caching the redundancy sectors in the data 
buffer 32. In fact, after a redundancy sector has been cached for a 
particular track, the latency for subsequent write operations is not 
increased over methods that do not employ a redundancy sector. The flow 
charts for the "cached deferred" method of the present invention are shown 
in FIGS. 4C and 4D. The method can be executed directly from FIG. 2, or it 
can be executed after performing the pre-read operation of FIG. 4B. 
Starting at FIG. 4C, the REDUND. STATUS is initialized to WRITE VALID 202. 
Then the storage system checks whether the redundancy sector for the 
target track is already in the cache 204. If it is, then a status 
variable, CACHE CODE, is set to 2 to indicate that the redundancy sector 
was cached during a previous write operation. Then the storage system 
checks whether the current write range is contiguous with the previous 
write operation 208. If not, then an immediate write verify 210 is 
optionally executed to verify the previous write; otherwise, the storage 
system initializes the redundancy buffer 34 with the cached redundancy 
sector 212. An alternative embodiment to executing an immediate write 
verify 210 is to reserve another redundancy sector for the target track in 
the cache corresponding to the non-contiguous write operation. In yet 
another embodiment, both the cached redundancy sector and the redundancy 
sector on the disc are used to account for a non-contiguous write to the 
same track. 
If the redundancy sector is not already cached 204, then the storage system 
checks whether there is space available in the cache 214. If so, then 
space is reserved in the cache for the redundancy sector and the CACHE 
CODE is set to 1 to indicate that redundancy sector was cached during the 
current write operation. If there is not space available in the cache 214, 
then the storage system sets the CACHE CODE to 0 to indicate that the 
redundancy sector is not cached. 
The final step shown in FIG. 4C is to orient to the first sector in the 
write range 222 so that the user data can be written to the track. 
Continuing now to FIG. 4D, when the recording head reaches the target 
sectors, the storage device writes all of the sectors in the write range 
and simultaneously combines the write data with the redundancy buffer 224. 
Then the storage system checks whether a subsequent write command is 
pending for the current track 226. If so, then the storage system checks 
whether the write range of the pending write command is contiguous with 
the current write operation 228. If the write range is contiguous, then 
the storage system processes the pending write command by writing the 
additional sectors and updating the write range 224. If the write range is 
not contiguous, then the storage system optionally queues an immediate 
write verify 230 as described with reference to FIG. 4A above. 
Once the user data has been written to the target sectors, then the track 
number and write range for the entire write operation is stored in the 
write log 232. Then a branch is executed depending on the state of the 
CACHE CODE as set above. If the CACHE CODE is 0, indicating that the 
redundancy sector is not cached, then the storage system stores the 
REDUND. STATUS 236 (e.g., appends it to the redundancy sector) and then 
writes the redundancy sector to the target track 238. If the CACHE CODE is 
1, indicating that the redundancy sector should now be cached, then the 
REDUND. STATUS is set to NOT VALID 240 and stored in non-volatile memory 
242 (e.g., on the disc at the end of the redundancy sector). The NOT VALID 
status indicates that the redundancy sector stored on the disc is no 
longer valid since it is cached in the data buffer 32. If the CACHE CODE 
is 2, indicating that the redundancy sector was cached during a previous 
write operation to the target track, or if the CACHE CODE is 1 as describe 
above, then the redundancy buffer 34 is transferred to the cache in the 
data buffer 244. 
After updating the cached redundancy sector, the storage system checks 
whether an immediate write verify was queued 246 as described above and, 
if so, executes an immediate write verify operation 248 described below 
with reference to FIG. 4E. If an immediate write verify was not queued 
246, then the "cached deferred" write operation exits 250 and returns 
control over to the storage system's operational firmware. 
IMMEDIATE WRITE VERIFY 
There are instances during the "deferred" and "cached deferred" write 
methods of the present invention as described above with reference to FIG. 
4A, 4C and 4D where a consecutive write to a target track is requested 
before a previous write to the same track has been verified during idle 
time. For instance, in the flow chart of FIG. 4A an immediate write verify 
may be queued 160 if a pending write command to the same track 156 having 
a non-contiguous write range 158 is detected. And in FIG. 4C, there may be 
consecutive write to a track with a cached redundancy sector wherein the 
write range is not contiguous 208 and an optional immediate write verify 
210 is performed for the previous write operation. And in FIG. 4D, an 
immediate write verify may be queued 230 if a subsequent write command is 
pending 226 similar to FIG. 4A. In these situations, the immediate write 
verify operation verifies the recoverability of the previously written 
data sectors without regenerating the redundancy sector for the entire 
track as in the idle time write verify method of FIG. 4F. 
Referring now to FIG. 4E, which is a flow chart description of the 
immediate write verify operation, the storage system orients and attempts 
to read the target data sectors within the write range of the previous 
write operation (the write range is passed as a parameter retrieved from 
the write log or from a current write operation). If an unrecoverable 
sector is encountered 256 while reading the sectors in the write range, 
then the storage system attempts to reconstruct the unrecoverable sector 
258 using the redundancy sector. Finally, before returning from the 
immediate write verify operation, all entries in the write log for the 
current track are cleared 260. 
IDLE TIME WRITE VERIFY 
In the "deferred" write method of FIG. 4A and the "cached deferred" method 
of FIG. 4B, the redundancy sector covers the write data after performing a 
write operation on a track. During idle time, the storage system executes 
a "write verify" operation intended to regenerate the redundancy sector 
for the entire track and, and the same time, verify the validity of the 
previous write operation. That is, if while regenerating the redundancy 
sector for the entire track an unrecoverable data sector is encountered 
within the write range of the previous write operation, then the storage 
system uses the redundancy sector to reconstruct the unrecoverable data 
sector. If the data sectors in the write range are recoverable, then the 
storage system over writes the redundancy sector with the regenerated a 
redundancy sector. 
The flow chart executed by the storage system during the idle time write 
verify operation is shown in FIG. 4F. First the storage system seeks to 
the track to be write verified 266. Then the redundancy sector is cleared 
268 and the storage system orients to the first sector in the track 270 
(i.e., sector 0). Once at sector 0, the storage system reads all of the 
data sectors in the track and combines the sector data and sector 
correction values with the redundancy buffer 272. Also while reading the 
entire track, all unrecoverable data sectors encountered are logged 272. 
Thus, if an unrecoverable data sector is encountered before reaching the 
write range of the previous write operation, which is potentially a 
catastrophic error since the redundancy sector at this time covers only 
the write range, the write verify operation is not aborted because an 
unrecoverable data sector in the write range can still be corrected. 
Further, an unrecoverable data sector encountered outside the write range 
may be over written before read by the host system; i.e., the catastrophic 
error event may be avoided. 
After reading the entire track, the storage system checks whether there 
were any unrecoverable data sectors encountered within the write range 
274. If so, the storage system executes a track level reconstruction 
operation 276 in an attempt to recover the data sector using the 
redundancy sector. If the sector reconstruction was successful 278, then 
the write verify operation is re-executed and the redundancy sector 
regenerated for the entire track. If the sector reconstruction was not 
successful 278, then the write verify operation is aborted after clearing 
the write log and relinquishing the cached redundancy sector 288. 
If there are no unrecoverable sectors within the write range 274, the 
storage system checks if there were any unrecoverable sectors encountered 
outside the write range 280. If not, then the REDUND. STATUS is set to 
READ VALID 282 and then stored 284 (e.g., appended to the redundancy 
sector as it is written to the disc). The redundancy buffer is then 
written to the redundancy sector 286, thereby updating the redundancy 
sector to cover the entire track. If unrecoverable data sectors are 
encountered outside the write range 280, then the redundancy status is not 
changed (i.e., left WRITE VALID) so that an unrecoverable sector in the 
write range can be corrected in the future, if necessary. Finally, the 
write log is cleared for all entries matching the current track and the 
cached redundancy sector 288. 
TRACK LEVEL SECTOR RECONSTRUCTION 
The method for reconstructing an unrecoverable data sector is set forth in 
the flow charts at FIGS. 5A-5C. Starting with FIG. 5A, the storage system 
retrieves the redundancy status for the track containing the unrecoverable 
data sector 294 (e.g., reads the redundancy status byte appended to the 
redundancy sector). If the REDUND. STATUS is READ VALID 296, then the 
reconstruction range is set to the entire track 308. If the REDUND. STATUS 
is WRITE VALID 296 or if it is NOT VALID and the redundancy sector is 
cached 298, then if the current track is in the write log 302 the most 
recent write log entry for the track is retrieved 304 and the 
reconstruction range set to the write range in the write log entry 306. If 
the current track is not in the write log 302, it means the write log 
entry was lost for the current track (e.g., over written) so the operation 
is aborted 300. If the REDUND. STATUS is NOT VALID 294 and the redundancy 
sector is not cached 298, then the operation is aborted 300 because there 
is no valid redundancy sector to perform the reconstruction operation. 
If the redundancy sector is cached 310, then the redundancy buffer is 
initialized with the cached redundancy sector 314; otherwise, the 
redundancy buffer is cleared 312. Then the storage system orients to the 
first sector on the track (i.e., sector 0) 316. Once at sector 0, the 
storage system reads the data sectors in the reconstruction range and 
combines the read data and the sector level error correction values with 
the redundancy buffer 318. 
Continuing now to FIG. 5B, if the redundancy sector is not cached 320, then 
the storage system reads the redundancy sector and combines it with the 
redundancy buffer 322. At this point, the redundancy buffer either 
contains syndromes for correcting a data sector uncorrectable at the 
sector level, or it contains an unreadable data sector. 
If the number of unrecoverable sectors encountered after reading the 
reconstruction range is zero 324, then the operation is aborted 326 since 
sector reconstruction is unnecessary. If the number of unrecoverable data 
sectors is greater than one 324, then the storage system makes a list of 
the unrecoverable data sectors 328 and, for each entry in the list, sets 
up 330 to perform a sector level error recovery operation 332 (see FIG. 
7). When finished with the unrecoverable entries in the list 334, if the 
number of unrecoverable data sectors after the sector level recovery 332 
is not one, then the operation is aborted 338 because the sectors cannot 
be reconstructed. 
If after attempting the sector level recovery 336 the number of 
unrecoverable data sectors is one, then the sector recovery procedure 
restarts at FIG. 5A. If after reading the data sectors in the write range 
324 the number of unrecoverable data sectors is one, then continuing to 
FIG. 5C the contents of the redundancy buffer is used to reconstruct the 
sector. If the unrecoverable data sector is uncorrectable at the sector 
level 340, then the redundancy buffer contains error syndromes which are 
combined with the uncorrectable data sector stored in the data buffer 344 
to correct the sector. If the unrecoverable data sector is unreadable 340, 
then the redundancy buffer contains the reconstructed data sector and the 
storage system merely replaces the unreadable sector in the data buffer 
with the contents of the redundancy buffer. After correcting the 
unrecoverable data sector in the data buffer, the storage system executes 
a dynamic defect management operation described below with reference to 
FIG. 8. 
IDLE TIME FUNCTIONS 
When the storage system is idle (i.e., not reading or writing), it either 
processes entries in the write log, if any are pending, to verify previous 
write operations, or it scans the entire disc looking to correct data 
sectors that have become unrecoverable at the sector level due, for 
example, to grown defects in the medium. The flow charts describing the 
idle time operations are set for at FIGS. 6A-6C. 
Starting with FIG. 6A, if the storage system detects a pending host command 
352 (e.g., read or write request), it exits the idle mode and returns 
control to the operational firmware 354. If no host commands are pending, 
then the storage system checks whether there are any entries in the write 
log (i.e., if there is a previous write command that needs to be write 
verified). If there are, then the track number for the oldest write log 
entry is retrieved 358 and the storage system prepares to perform a write 
verify on the sector range for the most recent write log entry for that 
track 360. The storage system processes the most recent write log entry 
since it corresponds to the most recent write operation (i.e., it 
corresponds to the redundancy sector currently stored on the track). The 
storage system then performs an idle time write verify 362 for the write 
log entry, the operation of which is described above with reference to 
FIG. 4F. After the write verify, the storage system continues the idle 
time operation for the next entry in the write log. 
Once all of the write log entries have been processed, then continuing to 
FIG. 6B, the storage system prepares to scan the entire disc looking for 
data sectors that have become unrecoverable. Since this scan will be 
periodically interrupted by a host command 370 and return to the 
operational firmware 372, the storage system saves a "place holder" so 
that the scan will continue where it left off. The flow charts show that 
the data integrity scan will continue indefinitely, but the storage system 
may alternatively be configured to perform the scan of the entire disc 
periodically. 
If no host commands are pending 370, then the storage system sets up to 
scan the next track 374 by retrieving the redundancy status for the track 
(e.g., reading the redundancy status byte stored at the end of the 
redundancy sector). If the REDUND. STATUS is READ VALID 371, indicating 
that the redundancy sector covers the entire track, then the storage 
system clears the redundancy buffer 376 and reads all of the sectors on 
the track (data sectors and redundancy sector) and combines the read data 
and sector level error correction values with the redundancy buffer 378. 
If an unrecoverable data sector is encountered 380, then the storage 
system executes the above track level reconstruction operation (FIG. 5A) 
382 in attempt to recover the sector. If the reconstruction is successful 
383, then the scan continues with the next track; otherwise, the REDUND. 
STATUS is set to NOT VALID 385 and stored 387 (e.g., written to the 
redundancy sector) to indicate the redundancy sector is no longer valid. 
After reading all of the data sectors on the track 378, the redundancy 
buffer should contain all zeros 384 if there were no unrecoverable data 
sectors encountered 380. If the redundancy buffer is not all zeros, it is 
tantamount to a catastrophic problem with the operation of the hardware or 
firmware 386 that requires appropriate action by the manufacturer 388. 
If the REDUND. STATUS for a track is not READ VALID 371, then continuing to 
FIG. 6C, the storage system clears the redundancy buffer 387 and reads all 
of the data sectors and combines the read data and the sector level error 
correction values with the redundancy buffer 389. If an unrecoverable data 
sector is encountered, then the storage system executes the above track 
level reconstruction operation (FIG. 5A) 391 in attempt to recover the 
sector. If the sector reconstruction operation 391 is successful 392, then 
the storage system again attempts to regenerate the redundancy sector for 
the entire track; otherwise, the scan continues at FIG. 6B. If no 
unrecoverable sectors are encountered 390, the REDUND. STATUS is set to 
READ VALID 393, the REDUND. STATUS is stored 395 (e.g., written to the 
redundancy sector) and the redundancy buffer is written to the redundancy 
sector 397 before continuing the scan at FIG. 6B. 
SECTOR LEVEL ERROR RECOVERY 
In the track level reconstruction procedure of FIG. 5B described above, if 
a track contains more than one unrecoverable data sector (thereby 
exceeding the correction capability of the track level redundancy) the 
storage system performs a sector level error recovery procedure 332 on the 
unrecoverable data sectors. If after this procedure there is only one 
remaining unrecoverable data sector, it can be recovered using the track 
level reconstruction procedure. 
A flow chart of the sector level error recovery procedure 332 is shown in 
FIG. 7, wherein the storage system attempts to recover a sector using 
drive specific "retry" techniques 396. For example, the storage system may 
repeatedly reread an uncorrectable sector until the number of errors is 
within the error correction capability of the sector level redundancy. In 
addition, varying certain system dynamics may aid the sector recovery 
process; for example, offsetting the centerline servo tracking system or 
adjusting parameters in the read channel's gain control or timing recovery 
may increase the SNR enough to recover the sector. And a method for 
recovering an unreadable sector caused by an obliterated sync mark is to 
repeatedly reread the sector and time when the sync mark should occur 
relative to a particular point on the track, such as an embedded servo 
wedge. 
If the sector level retry techniques are successful 397, then the storage 
system maps the unrecoverable data sector to a spare sector according to a 
dynamic defect management procedure 398 described below with reference to 
FIG. 8. Ideally, there will remain at most one unrecoverable data sector 
after the drive specific retry techniques, so that when control is 
returned 400 to the track level reconstruction procedure (FIG. 5B), the 
last remaining unrecoverable data sector can be recovered using the 
redundancy sector. 
DYNAMIC DEFECT MANAGEMENT 
If a data sector is recovered using the track level reconstruction 
procedure of FIG. 5A or using the sector level error recovery procedure of 
FIG. 7, the storage system will execute a dynamic defect management 
procedure shown in FIG. 8. Before mapping to a spare sector, the storage 
system first rewrites the corrected or reconstructed data to the 
unrecoverable data sector 404. Then, the storage system attempts to read 
the unrecoverable data sector 406 to determine if the unrecoverability 
persists 408. If it does persist, the unrecoverable data sector is mapped 
to a spare sector on the disc 410, and preferably to a spare sector on the 
same track. 
Once the unrecoverable data sector has been mapped to a spare sector on the 
track, the track is queued for "in the field" sector slipping 412. Sector 
slipping is a technique employed to maintain performance after defect 
mapping by, for example, "slipping" the logical sector numbers past a 
mapped sector (defective sector) so that the sector sequence remains 
contiguous around the track. Any well known technique of sector slipping 
after defect mapping may be employed, but an important aspect of the 
present invention is that the sector slipping is performed "in the field" 
during idle time of the storage system, as opposed to when the disc is 
formatted as in the prior art. 
Sector slipping addresses the following problem: after a defective sector 
has been mapped to a spare sector on a track, the logical sector sequence 
will no longer be contiguous. Consider, for example, that SECTOR 4 in FIG. 
1A is a spare sector and SECTOR 2 becomes unrecoverable. After mapping 
SECTOR 2 to SECTOR 4, the logical sector numbers are no longer contiguous 
and it is not possible to consecutively read or write the sectors in one 
revolution. 
To implement "in the field" sector slipping, the storage system reserves a 
spare track preferably in the outer zone of the disc. The disc is normally 
partitioned into a number of zones where each zone comprises a 
predetermined group of adjacent tracks. This "zoning" technique allows the 
storage density to be increased at the outer zones due to the increase in 
the circumferential recording area. Thus, the number of sectors per track 
can be increased from the inner zone to the outer zone. 
In the present invention, if an unrecoverable sector is mapped to a spare 
sector on a given track, then the storage system performs sector slipping 
on that track using the spare track. This is accomplished during idle time 
by transferring the sectors of the non-contiguous track to the spare 
track, and then copying in a contiguous order the sectors from the spare 
track back to the target track (i.e., slipping the defective sector). 
The process of copying the sectors to the spare track can be interrupted by 
a host command to the track being slipped. If the host command is not a 
write command, then the state of the track copy is saved and restored when 
the operation is re-initiated. If the host command is a write command, the 
copying operation is simply restarted. Once all of the sectors have been 
successfully copied to the spare track, all host commands are mapped to 
the spare track until the sectors are successfully copied back to the 
target track in a contiguous order. Again, the process of copying the 
sectors from the spare track back to the target track can be interrupted 
by a host command wherein the state of the copy operation is saved unless 
it is a write command to the spare sector, in which case the copying 
operation is simply restarted. 
INTERLEAVED REDUNDANCY SECTOR 
The prior art track level error correction systems are limited to 
correcting only one unrecoverable data sector per track because the 
redundancy sector is generated as the byte XOR of the respective data 
bytes in the data sectors. This severely limits the benefit of using a 
redundancy sector, especially in cases where a burst error spans two 
sectors, thereby rendering both sectors unrecoverable at the sector level 
and at the track level. The present invention improves the error 
correction capability of the track level ECS by dividing a sector into 
three interleaved codewords and generating the redundancy sector by 
combining the respective symbols in each codeword according to a 
predetermined error correction operation (e.g., byte XOR). 
This aspect of the present invention is understood with reference to FIG. 9 
which shows each data sector divided into three codewords, and the 
codewords being combined (XORed) across three interleaves (designated 
INTLV 0, INTLV 1 and INTLV 2) to generate an interleaved redundancy 
sector. The data sector itself is interleaved to generate the three 
codewords; that is, symbol 0 is placed in the first codeword, symbol 1 is 
placed in the second codeword, symbol 2 is placed in the third codeword, 
symbol 3 is placed in the first codeword, etc.. Then, sector level 
redundancy is generated for each of the three codewords and stored in the 
data sector. Upon read back, the data symbols read from the disc are 
de-interleaved into the three codewords and each codeword is processed by 
the sector level ECS separately. In this manner, the sector level ECS can 
generate an erasure pointer corresponding to an unrecoverable codeword 
within a sector (i.e., an unrecoverable codeword in INTLV0, INTLV1 or 
INTLV2). Using the erasure pointers, the track level ECS is capable of 
correcting a single unrecoverable codeword in each interleave, and the 
unrecoverable codewords can occur in different sectors. Thus, using the 
interleave technique of the present invention, the track level ECS is 
capable of correcting up to three unrecoverable data sectors containing a 
single uncorrectable codeword in separate interleaves. 
Preferably, the redundancy sector is generated according to: 2.sup.m --the 
sum modulo 2.sup.m of the respective codeword symbols in an interleave 
(i.e., INTLV0, INTLV1 or INTLV2), where m is the size in bits of a 
codeword symbol. Then, the track level error syndromes for correcting a 
codeword are generated as the sum modulo 2.sup.m of the respective 
codeword symbols in an interleave, including the redundancy sector 
codeword. The error syndromes are then used to correct a data codeword 
uncorrectable at the sector level that corresponds to the erasure pointer 
generated by the sector level ECS. That is, the erasure pointer identifies 
the sector and interleave location of the uncorrectable codeword, and the 
track level ECS uses the erasure pointers to correct up to three codewords 
in separate interleaves which can occur in three different sectors. 
MULTIPLE REDUNDANCY SECTORS 
The above aspects of the present invention are extendable to a storage 
system that employs two or more redundancy sectors geographically 
distributed over a track in order to further improve performance and 
reduce the write latency. 
In one embodiment, each of the redundancy sectors covers the entire track; 
that is, after the redundancy is regenerated for an entire track, the 
redundancy data is stored in the nearest redundancy sector in order to 
minimize the revolution latency. The storage system maintains a variable 
to indicate which of the plurality of redundancy sectors per track is 
valid, that is, which redundancy sector was updated last. 
In an alternative embodiment, each of the plurality of redundancy sectors 
covers a subset of the data sectors on a track. Again, this reduces the 
latency in the present invention write operations described above because 
the storage system can regenerate the redundancy sector and write the 
target data sectors in one pass. This is not true in the above described 
prior art "backing out" technique because it requires an extra revolution 
of latency to back out the old contribution of the target sectors from the 
redundancy sector. 
The objects of the invention have been fully realized through the 
embodiments disclosed herein. Those skilled in the art will appreciate 
that the various aspects of the invention can be achieved through 
different embodiments without departing from the essential function. The 
particular embodiments disclosed are illustrative and not meant to limit 
the scope of the invention as appropriately construed from the following 
claims.