Decoder, data storage device and data error correction method

Background The field of invention The present application generally applies error correction of data using error correction codes (for example, Bose-Chaudhuri-Hocquenghem (BCH) code, Reed-Solomon code, etc.). More specifically, it relates to an error correction decoder using a cell with partial syndrome occurrence.

Related Technology Data error correction is used in various fields such as data storage devices and telecommunications systems. For example, in a data storage device, data is stored by writing the data to the storage medium of the storage device. The stored data can be later retrieved from the storage device by reading the data from the storage medium. However, for many reasons, there may be errors in the data retrieved from the storage device. That is, the stored data may not be searchable or may differ from the data originally stored on the storage medium. For example, a part of the data stored in the storage medium may deteriorate over time, and the part of the stored data cannot be read out accurately later.

<p> Traditional error correction techniques include generating or coding one or more redundant blocks of data, which can be used in the decoding process to correct data errors. Typically, the decryption process is performed using special hardware and tends to be complex and difficult to modify.</p>

<p> Summary In one exemplary embodiment, a decoder that corrects data errors includes multiple cells. Each cell produces a partial syndrome based on a block of data and one or more redundant blocks. Each cell generates a partial error value based on the inverse matrix portion of the error position matrix that identifies the location of the erroneous data block. Additive logic connected to a plurality of cells generates an erroneous value based on a partial erroneous value generated by the plurality of cells. The error value corrects the error of the data block having the error.</p>

Detailed Description The following description specifies a number of specific configurations, parameters, etc. However, it is recognized that such description is not intended to limit the scope of the invention and is provided to provide a better description of the exemplary embodiments.

As an example, error correction of data in a storage device will be described below. However, it is recognized that error correction can be used in a variety of fields, including telecommunications.

Referring to FIG. 1, a host terminal 102 connected to the storage device 104 is shown. The host computer 102 can be any kind of computer, such as a personal computer, workstation, server, and the like. The storage device 104 can be any type of storage drive, such as a tape drive, a hard drive, and the like. It is recognized that the host terminal 102 can be connected to any number of storage devices 104 and any number of host terminals 102 can be connected to one or more storage devices 104.

Continuing with reference to FIG. 1, in one exemplary embodiment, the storage device 104 is configured to detect and correct errors in the data stored in the storage device 104. More specifically, when the data stored in the storage device 104 is searched, for example, if the searched data is different from the data originally stored in the storage device 104, or the stored data cannot be searched. In some cases, the storage device 104 is configured to use redundant blocks, also called error correction code (ECC) redundant blocks, to correct errors in the retrieved data. In addition, internal codes such as Cyclic Redundancy Check (CRC) codes can be used to detect errors in the retrieved data. However, it is recognized that error correction codes such as the Reed-Solomon code can be used to correct and detect errors.

In the embodiment shown in FIG. 1, the storage device 104 includes a storage medium 106, a channel and read / write head 108, a processor 110, and an error detection / correction unit 112. In the storage device 104, the data is stored in the storage medium 106. The read / write head 108 reads and / or writes data to the storage medium 106. Processor 110 controls the operation of storage device 104, including the operation of channels and read / write heads 108. As described in more detail below, the error detection / correction unit 112 detects and corrects an error in the data stored in the storage medium 106.

In this exemplary embodiment, the error detection / correction unit 112 includes a data buffer 114, a redundant block coder / decoder 116, and an internal code coder / decoder 118. When the data should be stored in the storage medium 106, the data is received from the host terminal 102 and written to the data buffer 114. The redundant block encoder / decoder 116 generates redundant blocks for the data in the data buffer 114. The internal code encoder / decoder 118 generates an internal code (for example, CRC code, Reed-Solomon code, etc.) for the data in the data buffer 114. Next, the read / write head 108 writes the data and the generated redundant block and internal code to the storage medium 106.

If the data should be read from the storage medium 106, the read / write head 108 reads the data, redundant blocks, and internal code from the storage medium 106 into the data buffer 114. Any errors in the data read from the storage medium 106 will be detected and corrected using internal codes and redundant blocks, as described in more detail below. This data can then be transferred to the host terminal 102.

In this exemplary embodiment, the data is transferred between the host terminal 102 and the storage device 104 as a data record, which is stored in a buffer. The data record is divided into data blocks of a predetermined length, for example 2 kbytes, 4 kbytes, 6 kbytes, and so on. However, it is recognized that data blocks of various lengths can be used.

After the data block is searched from the storage medium 106, the searched data block having an error is detected, and the error of the searched data block is that the data of the searched data block cannot be read or the data block. Indicates that is different from the data in the data block when it was first stored in the storage medium 106. For example, if the data in the retrieved data block is different from the data in the data block when the data block was first stored in storage medium 106, a CRC code may be used for detection. More specifically, before storing the data block in the storage medium 106, a CRC code is generated for the data block and stored together with the data block in the storage medium 106. When a data block is later retrieved, a new CRC code is generated for the retrieved data block. The new CRC code is then compared to the CRC code retrieved from the storage medium 106. This CRC code retrieved from the storage medium 106 corresponds to the retrieved data block and is first generated for this retrieved data block before storing the retrieved data block in the storage medium 106. It was done. If the new CRC code and the retrieved CRC code are different, an error is detected in the data block. However, it is recognized that various types of error correction codes can be used, including Reed-Solomon codes.

In this exemplary embodiment, the error location matrix identifies the location of the erroneous data retrieved from the storage medium. For example, an exemplary error position matrix is represented as follows.

<maths num="1"><img file="JP2005293557A_D0001.tif" /></maths>

Where X is the location of the error and ρ is the total number of erroneous data blocks and redundant blocks.

In this exemplary embodiment, the inverse matrix of the error position matrix is generated. For example, the inverse matrix of the exemplary error position matrix in the above example is represented as follows.

<maths num="2"><img file="JP2005293557A_D0002.tif" /></maths>

The error position matrix is the Vandermonde matrix, which is O (ρ).³) In general, O (ρ) for reciprocal operations when compared to general inverse matrices that require operations.²Note that it requires an operation. Rows in the Vandermonde matrix start at zero and consist of rising rising constant values. The inverse matrix of the error position matrix can be generated by firmware or hardware using a variety of matrix inversion techniques.

In this exemplary embodiment, redundant blocks are used to correct errors in the retrieved data blocks. More specifically, before storing the data block in the storage medium 106, a redundant block is generated based on the data block and stored together with the data block in the storage medium 106. When the data block is later retrieved, the data block identified as having an error is corrected with a redundant block.

In this exemplary embodiment, the redundant block is a Bose-Chowdury-Ockangam (BCH) code, more specifically a Reed-Solomon code. A more detailed description of the Reed-Solomon code is incorporated herein by reference in its entirety by 1972, "Error Correction Code" by MIT Press, Peterson and Weldon. (Error Correcting Codes) 2nd edition is referenced. However, it is recognized that different types of error correction codes can be used.

In this exemplary embodiment, a set of data blocks, a set of redundant blocks, and a set of redundant symbols of internal codes can be read and written together as a group called an "entity". For example, with reference to FIG. 2, entity 202 is shown to have 20 redundant symbols with 16 data blocks 204, 4 redundant blocks 206, and internal code 208. However, it is recognized that entity 202 can contain various numbers of data blocks 204, redundant blocks 206, and redundant symbols of internal code 208. For example, entity 202 may include 32 data blocks 204 and 8 redundant blocks 206, 112 data blocks 204 and 16 redundant blocks 206, and so on. In addition, the redundant symbol of internal code 208 can detect and correct errors in the data block 204 or the redundant block 206.

FIG. 2 shows the entity 202 stored in the data buffer 114 (FIG. 1). However, it is recognized that entity 202 does not have to physically exist as shown in FIG. It is also recognized that the data of entity 202, more specifically the data of data block 204, does not have to correspond to a single file. Rather, in this exemplary embodiment, the data retrieved from the host terminal 102 (FIG. 1) is interleaved. Therefore, the data in a particular data block 204 may correspond to a portion of each of the separate files received from the host terminal 102 (FIG. 1).

FIG. 2 also shows the logical relationship between the redundant symbols of entity 202, data block 204, redundant block 206, and internal code 208. With reference to FIG. 3, the portion of entity 202 is shown in more detail to more clearly show the logical relationship between the redundant symbols of data block 204, redundant block 206, and internal code 208.

In FIG. 3, the redundant symbol of internal code 208 is shown as a CRC code. However, it is recognized that various types of error detection or error correction codes, such as Reed-Solomon codes, can be used.

In this exemplary embodiment, the redundant symbol of internal code 208 corresponds to data block 204 or redundant block 206 and is used to detect errors in data block 204 or redundant block 206. For example, CRC with CRC code₁₉Is the data block D of entity 202₁₉Corresponds to. Therefore, data block D₁₉Data block D from storage medium 106 (Fig. 1) to detect errors in₁₉After searching for, the searched data block D₁₉CRC, which is a new CRC code for₁₉ ́ is generated. Next, the new CRC code, CRC₁₉ ́ and the data block D searched from the storage medium 106 (Fig. 1)₁₉The CRC code corresponding to (ie, the CRC code, CRC)₁₉) Is compared. CRC which is a new CRC code₁₉ CRC which is the CRC code searched for ́₁₉If different from, data block D₁₉An error is detected in.

In this exemplary embodiment, the number of redundant blocks determines the maximum number of data blocks that can be corrected. Therefore, in the example shown in FIG. 2, a total of four redundant blocks 206 can be used to correct up to four erroneous data blocks 204.

In this exemplary embodiment, each redundant block 206 is generated based on the data in all the data blocks of entity 202. For example, redundant block E₀, E₁, E₂, And E₃Each of the data blocks D₄, ..., D₁₈, And D₁₉It is generated based on the data of. As mentioned above, with reference to FIG. 1, the redundant block is generated by the redundant block encoder / decoder 116. Also, as described above, the redundant block is first generated for the data received from the host terminal 102. Next, the generated redundant block and the received data are stored in the storage medium 106.

Seeing Figure 3 again, redundant block E₀, E₁, E₂, And E₃Is generated based on the same set of data (ie, data block 204 of entity 202), and each redundant block 206 is unique to each other. More specifically, in this embodiment, the redundant block E₀, E₁, E₂, And E₃Is the Bose-Chaudory-Ockangam (BCH) code, more specifically the Reed-Solomon code.

Referring to FIG. 1, in this exemplary embodiment, the redundant block encoder / decoder 116 operates as a encoder for generating redundant blocks that are stored with the data blocks in the storage medium 106. The redundant block encoder / decoder 116 operates as a decoder for correcting errors in the data block retrieved from the storage medium 106. However, it is recognized that the redundant block encoder / decoder 116 can be implemented as separate components within the storage device 104 (ie, the encoder component and the decoder component).

Referring to FIG. 4, an exemplary encoder 400 for correcting an error in a data block retrieved from a storage medium is shown. As mentioned above, the encoder 400 is implemented as an integrated part of the redundant block encoder / decoder 116 (FIG. 1) or as a separate component within storage 104 (FIG. 1). You may.

As shown in FIG. 4, the encoder 400 includes a plurality of cells 402 and an additive logic 404 connected to the plurality of cells 402. Each cell 402 generates a partial syndrome based on redundant blocks and data blocks retrieved from the storage medium. Each cell 402 further generates a partial error value based on the inverse matrix portion of the error position matrix that identifies the position of the erroneous data block retrieved from the storage medium. As mentioned above, the inverse matrix of the error position matrix can be generated by firmware or hardware. The additive logic 404 generates an error value that corrects an error in a data block retrieved from the storage medium based on the partial error values generated by the plurality of cells 402.

Referring to FIG. 1, as described above, the data blocks and redundant blocks retrieved from the storage medium 106 are held in the data buffer 114. More specifically, with reference to FIG. 2, in one exemplary embodiment, the data block 204 and the redundant block 206 may be stored in the data buffer 114 (FIG. 1) in the form of entities 202.

Referring again to FIG. 4, in this exemplary embodiment, the plurality of cells 402 are connected to the data buffer 114 (FIG. 1) via line 406. Each cell 402 receives a portion of entity 202 (FIG. 2) stored in data buffer 114 (FIG. 1) as input. More specifically, each cell 402 reads a portion of entity 202 (FIG. 2) in a cache burst.

Referring to FIG. 2, in this exemplary embodiment, each cache burst is part of a single data block 204 or redundant block 206. In addition, in this exemplary embodiment, the parts of the data block 204 and the redundant block 206 are read in a raster pattern.

For example, suppose each cache burst is 32 bytes long. The first 32 bytes of the first data block 204 are read in the first cache burst. The first 32 bytes of each of the next 15 data blocks 204 and 4 redundant blocks 206 of entity 202 are then read in the next 19 cache bursts. After the first 32 bytes of the last redundant block 206 are read, the second 32 bytes next to the first data block 204 are read, then the next 15 data blocks 204 and 4 of entity 202. The next second 32 bytes of each of the redundant blocks 206 are read. In this embodiment, the data block 204 and the redundant block 206 of the entity 202 are read in a cache burst in a raster pattern with 32 byte portions at a time. However, it is recognized that the size of the cache burst may vary and the data block 204 and the redundant block 206 can be read in a variety of patterns. For example, each cache burst may be 64 bytes instead of 32 bytes.

In this exemplary embodiment, each part of the data block 204 and the redundant block 206 of entity 202 can be logically grouped as codeword 210. For example, the first part of each of the data block 204 and the redundant block 206 can be logically grouped as the first codeword 210, which corresponds to the first column in FIG. The second byte of each of the data block 204 and the redundant block 206 can be logically grouped as a second codeword 210, which corresponds to the second column in FIG.

In this exemplary embodiment, the codeword 210 is 1 byte wide. Thus, if data block 204 and redundant block 206 are 2 kbytes long, then data block 204 and redundant block 206 of entity 202 can be logically grouped into 2000 separate and independent codewords 210. In addition, if data block 204 and redundant block 206 are read using a 32-byte cache burst corresponding to 16 long words, each of which is 32 bits, then each part of the 32 codewords 210 is read once. Is read to.

Referring again to FIG. 4, in this exemplary embodiment, the number of cells 402 in the decoder 400 corresponds to the number of redundant blocks 206 (FIG. 2) in entity 202, which in turn corresponds to the number of data blocks 204 that can be corrected. Corresponds to the maximum number. Therefore, the decoder 400 is modified based on the maximum number of data blocks 204 to be corrected. For example, if up to four data blocks 204 are corrected, the decoder 400 is transformed to include four cells 402. Similarly, if a maximum of 16 or 32 data blocks 204 are corrected, the decoder 400 is transformed to include 16 or 32 cells 402.

With reference to FIG. 5, exemplary cell 402 is shown. In this exemplary embodiment, each cell 402 includes an input logic 502, a queue 504, a multiplier 506, a multiplexer 508, a queue 510 and a queue 512.

As mentioned above, each cell 402 generates a partial syndrome based on the data blocks retrieved from the storage medium and one or more redundant blocks. Referring to FIG. 6, an exemplary read process 600 is shown which produces a partial syndrome in cell 402 (FIG. 4).

At 602, cell 402 (FIG. 4) is set to read mode. Referring to FIG. 5, in this exemplary embodiment, input logic 502 receives input from line 406 connected to data buffer 114 (FIG. 1) and from feedback line 514 connected to the output of multiplier 506. Is set. More specifically, referring to FIG. 7, the multiplexer 702 is configured to receive input from the XOR gate 704 connected to line 406 and feedback line 514. Referring to FIG. 5, multiplier 506 is configured to receive input from queue 504, which holds the intermediate results produced by input logic 502, and from queue 510, which holds the roots of the generated polynomial. More specifically, the multiplexer 508 whose inputs are connected to queue 510 and queue 512 is configured to receive input from queue 510.

Referring to FIG. 6, at 604, cell 402 (FIG. 4) reads data from data buffer 114 (FIG. 1). In this exemplary embodiment, cell 402 (FIG. 4) reads a portion of a data block or redundant block from entity 202 (FIG. 2) stored in data buffer 114 (FIG. 1) as a cache burst.

For example, data can be read from the data buffer 114 (Figure 1) in a 32-byte cache burst corresponding to 16 long words. Referring to FIG. 5, line 406 and feedback line 514 are 32 bits wide, so cell 402 can process 32 bits (one long word) at a time. However, it is recognized that line 406 and feedback line 514 can be of any size and cell 402 can process any number of bits at a time.

At 606, the data read from data buffer 114 (FIG. 1) is summed with the output from multiplier 506 (FIG. 5). Referring to FIG. 5, in this exemplary embodiment, the input OR 502 is the cache burst read from entity 202 (FIG. 2) via line 406 and the output of multiplier 506 via feedback line 514. Performs an exclusive OR (XOR) operation on the. As mentioned above, with reference to FIG. 7, the input logic 502 includes an XOR gate 704 capable of performing an XOR operation. However, the input logic 502 includes various components for summing the data read from the data buffer 114 (FIG. 1) with the output of the multiplier 506 (FIG. 5), including various types and numbers of logic gates. It is recognized to get.

Referring to FIG. 6, in 608, the sum of the data read from the data buffer 114 (FIG. 1) and the output of the multiplier 506 (FIG. 5) is stored as an intermediate result. Referring to FIG. 5, in this exemplary embodiment, the intermediate result produced by input logic 502 is stored in queue 504.

In this exemplary embodiment, the size and number of entries in queue 504 is the size of the cache burst used to read data from data buffer 114 (FIG. 1) and the size of line 406 and feedback line 514. Determined based on. For example, if data is read from data buffer 114 (Figure 1) in a 32-byte cache burst corresponding to 16 long words, and line 516 and feedback line 514 are 32 bits wide, then each long word in the cache burst is Summed with the output of multiplier 506 and stored as an entry in queue 504. Therefore, according to this example, queue 504 contains eight entries, each entry being 32 bits long. As the cache burst is resized, the queue 504 can be resized further. For example, if the cache burst is 64 bytes long, queue 504 can contain 16 entries, each 32 bits long.

Referring to FIG. 6, at 610, the intermediate result is multiplied by the root of the generated polynomial. In this exemplary embodiment with reference to FIG. 5, the multiplier 506 performs a Galois field multiplication between the intermediate result stored in the queue 504 and the root of the generated polynomial stored in the queue 510. It is a vessel (Galois Field Multiplier).

In this exemplary embodiment, multiplier 506 performs multiple parallel Galois field multiplications. For example, if each entry in queue 504 is 32 bits long, the 32-bit data in the entry in queue 504 can be formatted as four parallel 8-bit Galois elements. The multiplier 506 can then perform four parallel 8x8 Galois field multiplications between the 32-bit length entry of queue 504 and the 8-bit root of the generated polynomial of queue 510.

In 612, if all the data blocks and redundant blocks of entity 202 (FIG. 2) have not been processed, loops 604 through 612 are repeated to process the next data block or redundant block. Ru. In this exemplary embodiment, when it is determined that the next data block to be processed has an error, at 604, instead of reading the cache burst from the data buffer 114 (FIG. 1), all zeros are read. Will be done. When all the data blocks and redundant blocks have been processed, the read process 600 ends at 614.

In this exemplary embodiment, the number of iterations from loop 604 to loop 612 corresponds to the number of data blocks and redundant blocks of entity 202 (FIG. 2). For example, refer to Figure 3, suppose that part of entity 202 is read in a 32-byte long cache burst. In the first iteration of loops 604 to 612 (Figure 6), data block D₁₉The first cache burst containing the first 32 bytes of is read and processed. In the second iteration of loops 604 to 612 (Figure 6), data block D₁₈A second cache burst containing the first 32 bytes of is read and processed. Data block D₄Is identified as having an error. Then, in the 16th iteration of loops 604 to 612 (FIG. 6), data block D₄Instead of reading the cache burst from, all zeros are read and processed. In this example, loops 604 to 612 (Figure 6) are iterated 20 times to handle all 16 data blocks and all 4 redundant blocks.

Referring to FIG. 5, in the first iteration of loops 604 to 612 (FIG. 6), the sum of the first cache burst and the output of multiplier 506 is the data read in the first cache burst. Please note that. This is because the queue 504 is empty and the output of the multiplier 506 is zero. In the second iteration, queue 504 holds the data read in the first cache burst, and the output of multiplier 506 is the data read in the first cache burst multiplied by the root of the generating polynomial. is there. Therefore, the sum of the results of the second cache burst and the output of multiplier 506 is the data read in the second cache burst multiplied by the root of the generated polynomial. It is the total with the result. This result is then stored in queue 504 as a new intermediate result. When all data and redundant blocks have been processed and the read process 600 ends at 614 (Figure 6), the final result stored in queue 504 of each cell 402 is the partial syndrome of each cell 402. Is.

Seeing FIG. 4 again, in this exemplary embodiment, each cell 402 uses a different root of the generated polynomial. Therefore, different partial syndromes are generated in each of the plurality of cells 402.

<maths num="3"><img file="JP2005293557A_D0003.tif" /></maths>

The sequence may start from any number, while the roots of the generated polynomials of multiple cells 402 must be sequential. For example, each cell 402 is α, which is the root of the generated polynomial.^{n + l}Where n is the sequence number of the cell and l is the fixed constant of each cell 402.

<maths num="4"><img file="JP2005293557A_D0004.tif" /></maths>

After the read process 600 (FIG. 6) is complete, each cell 402 generates a partial error value based on the generated partial syndrome and the inverse matrix portion of the error position matrix. Reference to FIG. 8 shows an exemplary write process 800 that produces partial error values in cell 402 (FIG. 4).

In 802, cell 402 (FIG. 4) is set to write mode. Referring to FIG. 5, in this exemplary embodiment, the input logic 502 is configured to receive input from the feedback line 516, which retains the partial syndrome generated in cell 402 in the previous read process. Connected to queue 504. More specifically, referring to FIG. 7, the multiplexer 702 is configured to receive input from the feedback line 516. With reference to FIG. 5, the multiplier 506 is configured to receive input from queue 504 and queue 512, which holds the inverse matrix portion of the error position matrix. More specifically, the multiplexer 508 with inputs connected to queue 510 and queue 512 is configured to receive input from queue 512.

As described above, the error position matrix identifies the position of the erroneous data block retrieved from the storage medium. For example, an exemplary error position matrix is represented as follows.

<maths num="5"><img file="JP2005293557A_D0005.tif" /></maths>

Where X is the location of the error and ρ is the total number of erroneous data blocks and redundant blocks. The inverse matrix of the error position matrix is expressed as follows.

<maths num="6"><img file="JP2005293557A_D0006.tif" /></maths>

Further, as described above, in this exemplary embodiment, the inverse matrix of the error position matrix can be generated by firmware or hardware.

<maths num="7"><img file="JP2005293557A_D0007.tif" /></maths>

<maths num="8"><img file="JP2005293557A_D0008.tif" /></maths>

Referring to FIG. 8, in 806, the partial error value generated by cell 402 (FIG. 4) is sent to the additive logic 404 (FIG. 4). Referring to FIG. 4, in the above example, the partial error value y generated by cell 402 (0), cell 402 (1), ..., cell 402 (ρ-1).₀(0), y₀(1), ..., and y₀(ρ-1) is sent to the additive logic 404.

The additive logic 404 sums the partial erroneous values generated by cell 402 to generate erroneous values. In the above example, the first error value Y₀Is a partial error value y generated by cell 402 (0), cell 402 (1), ..., cell 402 (ρ-1).₀(0), y₀(1), ..., and y₀It is generated by summing (ρ-1).

Referring to FIG. 9, in this exemplary embodiment, the addition logic 404 can include an array of XOR gates 902 that computes the Galois sum of the outputs of cell 402 (FIG. 4). However, it is recognized that the additive logic 404 can include a variety of components that compute the Galois sum of the outputs of cell 402 (FIG. 4), including a variety of types and numbers of logic components.

<maths num="9"><img file="JP2005293557A_D0009.tif" /></maths>

<maths num="10"><img file="JP2005293557A_D0010.tif" /></maths>

<maths num="11"><img file="JP2005293557A_D0011.tif" /></maths>

With reference to Figure 5, the write process 800 (Figure 8) can then be repeated to generate another set of partial erroneous values, which can be summed up to produce another erroneous value. The other error values generated can then be used to correct parts of the other erroneous data block. For example, in the second iteration, a second set of partial error values is generated and summed to produce a second error value.

<maths num="12"><img file="JP2005293557A_D0012.tif" /></maths>

In the second iteration of 806 (FIG. 8), the partial error value y generated by cell 402 (0), cell 402 (1), ..., and cell 402 (ρ-1).₁(0), y₁(1), ..., and y₁A second set of (ρ-1) is sent to the additive logic 404. Then partial error value y₁(0), y₁(1), ..., and y₁Second error value Y by summing (ρ-1)₁Is generated.

By repeating the write process 800 (FIG. 8) and summing the set of generated partial error values, an error value can be generated to correct a portion of the data block that is identified as having an error. The number of times the write process 800 (FIG. 8) is repeated and the number of error values generated can be determined based on the number of data blocks identified as having errors (ie, ρ). Alternatively, the number of times write process 800 (Figure 8) is repeated and the number of erroneous values generated can be set to the maximum number of data blocks that can be corrected, which is that of entity 202 (Figure 2). Corresponds to the number of redundant blocks.

After the write process 800 (FIG. 8) is complete, the read process 600 (FIG. 6) is repeated again to process the data blocks stored in the data buffer 114 (FIG. 1) and the rest of the redundant blocks. The write process 800 (FIG. 8) can then be repeated again to correct the error in other parts of the erroneous data block. In this exemplary embodiment, queue 504 (FIG. 5) is cleared before the read process 600 (FIG. 6) is repeated again.

For example, refer to Figure 3 and suppose that part of entity 202 is read in a cache burst 32 bytes long. The read process 600 (FIG. 6) is repeated to read and process the first 32 bytes of each data block 204 and each redundant block 206 to generate a partial syndrome. The write process 800 (FIG. 8) then iterates to generate an erroneous value and corrects the erroneous data block 204 in the first 32 bytes. Queue 504 (Figure 5) is cleared, then read process 600 (Figure 6) is repeated again to read and process the second 32 bytes of each data block 204 and each redundant block 206 to create a partial syndrome. Generate another set. The write process 800 (FIG. 8) is then repeated again to generate an erroneous value and correct the erroneous data block 204 in the second 32 bytes. In this embodiment, all parts of each data block 204 and each redundant block 206 are read and processed using read process 600 (FIG. 6), and all parts of the erroneous data block are written process 800 (FIG. 6). It is corrected using Fig. 8).

Although exemplary embodiments have been described, various modifications can be made without departing from the spirit and / or scope of the invention. For example, with reference to FIG. 4, although the decoder 400 is described in connection with a storage device, the decoder 400 can be used in connection with a variety of devices and can also be used, for example, as part of an electrical communication system. It should be recognized that it can be used in a variety of fields, where data is received via error-causing channels. Therefore, the present invention should not be construed as being limited to the specific embodiments described above and shown in the drawings.

<figref num="1">It is a figure which shows the exemplary host terminal connected to the exemplary storage device.</figref><figref num="2">FIG. 5 illustrates an exemplary entity with a set of data blocks, redundant blocks, and cyclic redundancy check codes.</figref><figref num="3">It is a figure which shows the part of the exemplary entity of FIG.</figref><figref num="4">It is a figure which shows an exemplary decoder.</figref><figref num="5">It is a figure which shows the exemplary cell of the exemplary decoder shown in FIG.</figref><figref num="6">FIG. 5 illustrates an exemplary reading process performed by the exemplary cell shown in FIG.</figref><figref num="7">It is a figure which shows the part of the exemplary cell shown in FIG.</figref><figref num="8">FIG. 5 illustrates an exemplary writing process performed by the exemplary cell shown in FIG.</figref><figref num="9">It is a figure which shows the other part of the exemplary cell shown in FIG.</figref>

Code description

102 Host Terminal, 104 Storage Device, 106 Storage Medium, 108 Channel and Read / Write Head, 110 Processor, 112 Error Detection / Correction Unit, 114 Data Buffer, 116 Redundant Block Coder / Decoder, 118 Internal Code Coder / Decoder, 400 decoder, 402 cells, 404 additive logic