High-speed error correcting apparatus with efficient data transfer

• US 6,332,206 B1
• Filed: 02/24/1999
• Issued: 12/18/2001
• Est. Priority Date: 02/25/1998
• Status: Expired

• Current Assignee: Panasonic Corporation (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Nakatsuji, Fumio, Hashimoto, Yuichi
• Primary Examiner(s): MOISE, EMMANUEL LIONEL
• Application Number:
  US09/256,740
• Time in Patent Office: 1,028 Days
• Field of Search: 714/752, 714/753, 714/754, 714/755, 714/756, 714/757, 714/758, 714/763, 714/766, 714/767, 714/768, 714/769, 714/781-785, 714/800-805
• US Class Current: 714/755
• CPC Class Codes: G11B 20/10527 Audio or video recording; Data buffering arrangements G11B20/12 - G11B20/18 take precedence
• CPC Class Codes: G11B 20/18 Error detection or correction; Testing , e.g. of drop-outs
• CPC Class Codes: G11B 20/1833 by adding special lists or symbols to the coded information G11B20/1806, G11B20/1866 take precedence
• CPC Class Codes: G11B 2020/1062 Data buffering arrangements, e.g. recording or playback buffers
• CPC Class Codes: G11B 2220/2537 Optical discs
• CPC Class Codes: G11B 2220/40 Combinations of multiple record carriers
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C

Abstract

An error correcting apparatus includes a storing means for storing product code with n₂ rows and n₁ columns, an error correcting unit 5 that performs error correction for four code sequences simultaneously in parallel, and a bus control unit 2 for reading codes on four rows from the buffer memory 1 and transferring the codes to the error correcting unit 5. The bus control unit 2 reads and transfers four consecutive codes on each of four rows in order before shifting the reading position by four codes in the row direction.

Claims

1. An error correcting apparatus that repeatedly performs calculations that are required for error correction on code sequences in a row direction and a column direction in block code of R rows and L columns, the error correcting apparatus comprising:

storing means for storing the block code;

calculating means for performing calculations for correcting errors in the block code in units of one of (a) one row and (b) one column; and

transfer means, including

a row direction transferring unit for repeatedly reading code sequences on R1 (where R1 is an integer such that 2≦

R1<

R) rows in the block code from the storing means and transferring the read code sequences to the calculating means until all R rows have been read and transferred,

the row direction transferring unit transferring the code sequences on the R1 rows from the storing means to the calculating means by repeatedly reading and transferring sections of L1 consecutive codes (where L1 is an integer such that 2≦

L1<

L) on the R1 rows in order, shifting a read position by L1 codes after reading L1 consecutive codes on each of the R1 rows,

wherein when codes have been transferred by the row direction transferring unit, the calculating means performs the calculations for the code sequences on the R1 rows in parallel, treating the received codes as L1-code-wide sections of the code sequences on different rows in the R1 rows.

2. The error correcting apparatus of claim 1,

wherein the block code is product code, and code sequences in the row direction and column direction that compose the block code include information codes and error correction codes,

the calculating means includes:

error detecting means for detecting whether errors are present in a code sequence on one of (a) a row and (b) a column in the block code; and

error code updating means for rewriting, when the error detecting means has detected at least one error in a code sequence, a code in the storing means that corresponds to the error using a corrected value,

the row direction transferring unit repeatedly transfers code sequences to the error detecting means, and

the error detecting means performs error detection for the code sequences on the R1 rows in parallel, treating the received codes as L1-code-wide sections of the code sequences on different rows in the R1 rows.

3. The error correcting apparatus of claim 2,

wherein the storing means stores the block code so that codes on a same row are stored in a storage area with consecutive addresses, and

the row direction transferring unit sequentially reads L1 codes from a storage area with consecutive addresses in the storing means.

4. The error correcting apparatus of claim 3,

wherein the storing means is a dynamic random access memory, and

the row direction transferring unit reads L1 codes from the storing means using page mode.

5. The error correcting apparatus of claim 4,

wherein the row direction transferring unit transfers codes by performing direct memory access to the storing means.

6. The error correcting apparatus of claim 2,

wherein the error detecting means includes:

R1 error detecting units that each perform error detection for a code sequence on one row in the R1 rows; and

a distributing unit for distributing codes, which are received from the row direction transferring unit, in L1-code-wide sections to the R1 error detecting units in order,

wherein the R1 error detecting units are independent of one another and each perform error detection in parallel with a transfer of codes by the row direction transferring unit.

7. The error correcting apparatus of claim 6,

wherein each of the R1 error detecting units completes the error detection for an L1-code-wide section in a time that is shorter than an interval at which L1-code-wide sections are distributed to the error correcting unit by the distributing unit.

8. The error correcting apparatus of claim 7,

wherein each of the R1 error detecting units has a product-sum calculating circuit that calculates a plurality of syndromes for one code sequence.

9. The error correcting apparatus of claim 2,

wherein when a division of L by L1 results in a quotient of D and a remainder of E, the row direction transferring unit repeats a transfer of L1-code-wide sections on R1 rows D times, before reading and transferring an E-code-wide section on each of the R1 rows in order to the error detecting means, and

the error detecting means performs error detection a predetermined number of times for L1-code-wide sections before performing error detection for E-code-wide sections.

10. The error correcting apparatus of claim 2,

wherein the transferring means further includes a column direction transfer unit for reading code sequences in L2 (where L2 is an integer such that 2≦

L2<

L) columns in the block code from the storing means and transferring the read code sequences to the error detecting means until all L columns have been processed,

the column direction transferring unit transfers all code in the L2 columns from the storing means to the calculating means by repeatedly reading and transferring sections of L2 consecutive codes in the row direction on the R rows in order, shifting a read position by L2 codes after reading all codes in the L2 columns,

and when codes have been transferred by the column direction transferring unit, the error detecting means performs error detection for the code sequences in the L2 columns in parallel, treating the received codes as a series where each code corresponds to a code sequence in a different column in the L2 columns.

11. The error correcting apparatus of claim 10,

wherein R1 and L2 are such that R1=L2=j, and the error detecting means includes:

j error detecting units that each perform error detection for one code sequence; and

a distributing unit for repeatedly distributing each L1-code-wide section of codes that is received from the row to one of the j error detecting units selected in order, and for repeatedly distributing each code that forms part of an L2 code-wide section received from the column to a different error detecting unit in the j error detecting units in order,

wherein the j error detecting units are independent of one another and each detect errors in parallel with transfer of codes by the row direction transferring unit and the column direction transferring unit.

12. The error correcting apparatus of claim 11,

wherein each of the j error detecting units completes an error detection for an L1-code-wide section in a time that is shorter than an interval at which L1-code-wide sections are distributed to the error correcting unit by the distributing unit, and completes an error detection for one code in an L2-code-wide section in a time that is shorter than an interval at which codes in L2-code-wide sections are distributed to the error correcting unit by the distributing unit.

13. The error correcting apparatus of claim 12,

wherein R1=L1=L2=j.

14. An error correcting apparatus that repeatedly performs calculations that are required for error correction on code sequences in a row direction and column direction in block code of R rows and L columns,

the error correcting apparatus comprising:

storing means for storing the block code;

calculating means for performing calculations for correcting errors in the block code in units of one of (a) one row and (b) one column; and

transfer means, including

a column direction transferring unit for repeatedly reading code sequences on L2 (where R1 is an integer such that 2≦

L2<

L) columns in the block code from the storing means and transferring the read code sequences to the calculating means until all L columns have been read and transferred,

the column direction transferring unit transferring the code sequences in the L2 columns from the storing means to the calculating means by repeatedly reading and transferring sections of L2 consecutive codes on the R rows in order, shifting a read position by L2 codes after reading all codes in the L2 columns,

wherein when codes have been transferred by the column direction transferring unit, the calculating means performs the calculations for the code sequences in the L2 columns in parallel, treating successive codes as belonging to code sequences in different columns in the L2 columns.

15. The error correcting apparatus of claim 14,

wherein the block code is product code, and code sequences in the row direction and column direction that compose the block code include information codes and error correction codes,

the calculating means includes:

error detecting means for performing error detection for a code sequence on one of (a) a row and (b) a column in the block code; and

error code updating means for rewriting, when the error detecting means has detected at least one error in a code sequence, a code in the storing means that corresponds to the error using a corrected value,

the column direction transferring unit repeatedly transfers code sequences to the error detecting means, and

the error detecting means performs error detection for the code sequences in the L2 columns in parallel, treating the received codes as a series where each code corresponds to a code sequence in a different column in the L2 columns.

16. The error correcting apparatus of claim 15,

wherein the storing means stores the block code so that codes on a same row are stored in a storage area with consecutive addresses, and

the column direction transferring unit sequentially reads L2 codes from a storage area with consecutive addresses in the storing means.

17. The error correcting apparatus of claim 16,

wherein the storing means is a dynamic random access memory, and

the column direction transferring unit reads L2 codes from the storing means using page mode.

18. The error correcting apparatus of claim 17,

wherein the column direction transferring unit transfers codes by performing direct memory access to the storing means.

19. The error correcting apparatus of claim 15,

wherein the error detecting means includes:

L2 error detecting units that each perform error detection for a code sequence in one column in the L2 columns; and

a distributing unit for distributing each code that forms part of an L2 code-wide section received from the column direction transferring unit to a different one of the L2 error detecting units in order,

wherein the L2 error detecting units are independent of one another and each perform error detection in parallel with a transfer of codes by the column direction transferring unit.

20. The error correcting apparatus of claim 19,

wherein each of the L2 error detecting units completes the error detection for one code in an L2-code-wide section in a time that is shorter than an interval at which the distributing unit distributes codes in L2-code-wide sections to the error correcting unit.

21. The error correcting apparatus of claim 20,

wherein each of the L2 error detecting units has a product-sum calculating circuit that calculates a plurality of syndromes for one code sequence.

22. The error correcting apparatus of claim 15,

wherein when a division of L by L2 results in a quotient of D and a remainder of E, the column direction transferring unit repeats a transfer of L2-code-wide sections on R rows D times, before reading and transferring an E-code-wide section on each of the R rows in order, and

the error detecting means performs error detection a predetermined number of times for L2-code-wide sections before performing error detection for E-code-wide sections.

23. An error correcting apparatus that performs error correction on codes received from a first external apparatus and outputs the corrected codes to a second external apparatus,

the error correcting apparatus comprising:

storing means including a storage area for storing the codes;

error detecting means for detecting errors in sections of a predetermined number of codes;

error correcting means for correcting sections, in which the error detecting means has detected an error, of a predetermined number of codes in the storing means;

first transfer means for transferring codes outputted by the first external apparatus in parallel to the storing means and to the error detecting means so that the outputted codes are stored in the storing means and simultaneously subjected to error detection by the error detecting means;

second transfer means for transferring a section of a predetermined number of codes, in which the error detecting means has detected an error, from the storing means to the error correcting means,

third transfer means for transferring a section of a predetermined number of codes that does not contain any uncorrected errors from the storing means to the second external apparatus; and

transfer control means for controlling transfers of codes so that transfer is exclusively performed by one of the first to third transfer means.

24. The error correcting apparatus of claim 23,

wherein the error detecting means includes a detection result recording unit that records detection results showing whether an error exists in a section of codes, and

the error correcting means refers to the detection results in the detection result recording unit and controls the second transfer means so that only sections of codes for which the error detecting means has detected an error are transferred from the storing means to the error correcting means.

25. The error correcting apparatus of claim 24,

wherein the first external apparatus repeatedly outputs code sequences that form rows in block code composed of R rows by L columns,

the block code is product code, and code sequences in the row direction and column direction that compose the block code include information codes and error correction codes, and

the error correcting means performs error correction for code sequences in one of (a) a row direction and (b) a column direction, and when performing error correction for code sequences in the row direction, refers to the detection results in the detection result recording unit and controls the second transfer means so that only code sequences in the row direction for which the error detecting means has detected errors are transferred from the storing means to the error correcting means.

26. The error correcting apparatus of claim 25,

wherein the error detecting means accumulatively stores detection results in the detection result recording unit for all code sequences in the row direction that compose one set of block code, and

when performing error correction for code sequences in the column direction, the error correcting means refers to the detection results in the detection result recording unit and controls the second transfer means so that the second transfer means transfers code sequences in the column direction in a block from the storing means to the error correcting means only if the error detecting means has detected at least one error in the block.

27. The error correcting apparatus of claim 23,

wherein the second transfer means includes a row direction transferring unit for repeatedly reading code sequences on R1 (where R1 is an integer such that 2≦

R1<

R) rows where errors have been detected from the storing means and transferring the read code sequences to the error correcting means, until no code sequences on rows that contain errors remain in the block code,

the row direction transferring unit transfers the code sequences on the R1 rows from the storing means to the calculating means by repeatedly reading and transferring sections of L1 consecutive codes (where L1 is an integer such that 2≦

L1<

L) on the R1 rows in order, shifting a read position by L1 codes after reading L1 consecutive codes on each of the R1 rows, and

when codes have been transferred by the row direction transferring unit, the error correcting means performs the calculations for the code sequences on the R1 rows in parallel, treating the received codes as L1-code-wide sections of the code sequences on different rows in the R1 rows.

28. The error correcting apparatus of claim 27,

wherein the second transfer means further include s a column direction transferring unit for repeatedly reading code sequences in L2 (where L is an integer such that 2≦

L2<

L) columns in a block where an error has been detected from the storing means and transferring the read code sequences to the error correcting means, until code sequences in all L columns have been transferred,

the column direction transferring unit transfers all code in the L2 columns from the storing means to the error correcting means by repeatedly reading and transferring sections of L2 consecutive codes in the row direction on the R rows in order, shifting a read position by L2 codes after reading all codes in the L2 columns, and

when codes have been transferred by the column direction transferring unit, the error correcting means performs error detection for the code sequences in the L2 columns in parallel, treating the received codes as a series where each code corresponds to a code sequence in a different column in the L2 columns.

29. The error correcting apparatus of claim 23,

wherein transfer of codes from the first external apparatus to the storing means by the first transfer means, transfer of codes from the storing means to the error correcting means by the second transfer means, and transfer of codes from the storing means to the second external apparatus by the third transfer means are all transfers that are accompanied by direct memory access (DMA) to the storing means,

the transfer control means has DMA transfer by the first transfer means performed with a highest priority out of DMA transfers by the first to third transfer means, and

when DMA transfer by the first transfer means becomes necessary, the transfer control means has DMA transfer performed by the first transfer means immediately if DMA transfer is not presently being performed by any of the first to third transfer means and, if DMA transfer is presently being performed by one of the first to third transfer means, allows a present DMA transfer to end before having DMA transfer performed by the first transfer means.

30. The error correcting apparatus of claim 29,

wherein the transfer control means has DMA transfer performed by the second transfer means with a lowest priority out of the first to third transfer means, so that when DMA transfer by the second transfer means becomes necessary, the transfer control means only has DMA transfer performed by the second transfer means if DMA transfer is not being performed by any of the first to third transfer means.

31. The error correcting apparatus of claim 30,

wherein the error correcting means specifies an error code in a code sequence transferred by the second transfer means and then rewrites a corresponding error code in the storing means under control by the transfer control means, the transfer control means only allowing the error correcting means to rewrite the corresponding error if DMA transfer is not being performed by any of the first to third transfer means.

32. An error correcting apparatus that performs error correction on codes received from a first external apparatus and outputs the corrected codes to a second external apparatus,

the error correcting apparatus comprising:

storing means including a storage area for storing the codes;

error correcting means for detecting error codes in sections of a predetermined number of codes and correcting the error codes in the storing means;

code selecting means for selecting one of codes sent from the first external apparatus and codes sent from the storing means and sending the selected codes to the error correcting means to have the error correcting means perform error detection and error correction on the selected codes;

first transfer means for transferring codes outputted by the first external apparatus in parallel to the storing means and the code selecting means so that the outputted codes are stored in the storing means and simultaneously selected by the code selecting means and sent to the error correcting means where error detection and error correction are performed on the transferred codes;

second transfer means for transferring a section of a predetermined number of codes from the storing means to the code selecting means so that the error correcting means performs error detection and error correction on the transferred codes;

third transfer means for transferring a section of a predetermined number of codes that do not contain any uncorrected errors from the storing means to the second external apparatus; and

transfer control means for controlling transfers of codes so that transfer is exclusively performed by one of the first to third transfer means.

33. The error correcting apparatus of claim 32,

wherein the first external apparatus repeatedly outputs code sequences that form rows in block code composed of R rows by L columns,

the block code is product code, and code sequences in the row direction and column direction that compose the block code include information codes and error correction codes,

the first transfer means transfers code sequences in a row direction that are repeatedly outputted by the first external apparatus in parallel to the storing means and the code selecting means to have the code sequences stored in the storing means and simultaneously selected by the code selecting means and sent to the error correcting means where error detection and error correction are performed on the transferred code sequences, and

the second transfer means transfers code sequences in the column direction in the block code to the code selecting means so that the code sequences are selected by the code selecting means and sent to the error correcting means where error detection and error correction are performed for the code sequences.

34. The error correcting apparatus of claim 33,

wherein the error correcting means includes:

an error detecting unit for detecting whether error codes are present in a code sequence on one of (a) one row and (b) one column; and

an error updating unit for updating, when the error detecting unit finds an error code, a code in the storing means that corresponds to the error code using a corrected value,

the error detecting unit includes;

a row direction detection result recording unit for recording results of error detection for code sequences in the row direction that are transferred by the first transfer means from the first external apparatus to the error detecting unit; and

a column direction detection result recording unit for recording results of error detection for code sequences in the column direction that are transferred by the second transfer means from the storing means to the error detecting unit, and

the error code updating unit uses the detection results in the row direction detection result recording unit and in the column direction detection result recording unit to update codes in the storing means.

35. The error correcting apparatus of claim 34,

wherein when performing error detection in the row direction, the error detecting unit accumulates detection results for all code sequences in the row direction that compose one set of block code in the row direction detection result recording unit, and when performing error detection in the column direction, the error detecting unit refers to the detection results recorded in the row direction detection result recording unit and controls the second transfer means so that only code sequences in the column direction that compose a set of block code that contains an error are sent from the storing means to the error correcting means.

36. The error correcting apparatus of claim 35,

wherein the transfer control means has

(a) a transfer of a code sequence of one row from the first external apparatus to the storing means by the first transfer means, and

(b) a transfer of a code sequence for one column from the storing means to the code selecting means by the second transfer means executed alternately in units of parts of the transferred code sequences,

the error detecting unit switches between

(i) error detection for a code sequence in the row direction sent from the first external apparatus by the first transfer means and

(ii) error detection for a code sequence in the column direction sent from the storing means by the second transfer means

in units of parts of the code sequences so as to perform error detection for code sequences in the row direction and code sequences in the column direction in parallel, the error detecting unit storing results of the error detection in the row direction in the row direction detection result recording unit and results of the error detection in the column direction in the column direction detection result recording unit, and

the error code updating unit sequentially refers to the detection results recorded in the row direction detection result recording unit and in the column direction detection result recording unit and successively updates error codes in the storing means in the row direction and error codes in the storing means in the column direction.

37. The error correcting apparatus of claim 32,

wherein the second transfer means includes a column direction transferring unit for repeatedly reading code sequences in L2 (where L2 is an integer such that 2≦

L2<

L) columns in a block and transferring the read code sequences to the error correcting means via the code selecting means until all L columns in the block code have been transferred,

the column direction transferring unit transfers the code sequences in the L2 columns from the storing means to the code correcting means by repeatedly reading and transferring sections of L2 consecutive codes in the row direction on the R rows in order, shifting a read position by L2 codes after reading all codes in the L2 columns, and

when codes have been transferred by the column direction transferring unit, the error correcting means performs error correction for the code sequences in the L2 columns in parallel, treating the received codes as a series where each code corresponds to a code sequence in a different column in the L2 columns.

38. The error correcting apparatus of claim 32,

wherein transfer of codes from the first external apparatus to the storing means by the first transfer means, transfer of codes from the storing means to the error correcting means via the code selecting means by the second transfer means, and transfer of codes from the storing means to the second external apparatus by the third transfer means are all transfers that are accompanied by direct memory access (DMA) to the storing means,

the transfer control means has DMA transfer by the first transfer means performed with a highest priority out of DMA transfers by the first to third transfer means, and

when DMA transfer by the first transfer means becomes necessary, the transfer control means has DMA transfer performed by the first transfer means immediately if DMA transfer is not presently being performed by any of the first to third transfer means and, if DMA transfer is presently being performed by one of the first to third transfer means, allows a present DMA transfer to end before having DMA transfer performed by the first transfer means.

39. The error correcting apparatus of claim 38,

wherein the transfer control means has DMA transfer performed by the second transfer means with a lowest priority out of the first to third transfer means, so that when DMA transfer by the second transfer means becomes necessary, the transfer control means only has DMA transfer performed by the second transfer means if DMA transfer is not being performed by one of the first transfer means the third transfer means.

40. The error correcting apparatus of claim 39,

wherein the transfer control means only allows the code updating unit to rewrite codes in the storing means if DMA transfer is not being performed by any of the first to third transfer means.