Error correcting decoder and error correction decoding method

Claim 2

An error-correcting decoder for decoding a code signal composed of n2 rows×n1 columns of symbols including error-correction codes for one of error-correction and erasure-and-error correction, and for correcting errors in the code signal based on the error-correction codes, comprising; (A) a first decoder for correcting errors of each row, and for detecting an uncorrectable-error of each row; (B) a flag memory, connected to the first decoder, for setting a burst-error flag on when a number of detected consecutive uncorrectable-errors of a row exceeds a first predetermined value; (C) a location memory, connected to the first decoder, for memorizing locations of rows having uncorrectable-errors detected by the first decoder; (D) a counter, connected to the first decoder, for counting a number of rows having uncorrectable-errors detected by the first decoder; and (E) a second decoder, connected to the first decoder, for correcting errors of each column, for decoding a column based on erasure-and-error correction using the locations in the location memory in the case that the burst-error flag is set on, and that the number in the counter is between second and third predetermined values, and for decoding the column based on error-correction in the case that the number in the counter is between the second and third predetermined values, and that the burst-error flag is off.

Claim 3

An error-correcting decoder for decoding a code signal composed of n2 rows×n1 columns of symbols including error-correction codes for one of error-correction and erasure-and-error correction, and for correcting errors in the code signal based on the error-correction codes, comprising; (A) a first decoder for correcting errors of each row, and for detecting an uncorrectable-error of each row; (B) a location memory, connected to the first decoder, for memorizing locations of rows having uncorrectable-errors detected by the first decoder; (C) a first counter, connected to the first decoder, for counting a number of rows having uncorrectable errors detected by the first decoder; (D) a second counter, connected to the first decoder, for counting a number of maximum error-correction flags, a maximum error-correction flag being set for a row when a number of detected errors of the symbols in the row is equal to a maximum-correctable-error value; and (E) a second decoder, connected to the first decoder, for correcting errors of each column, for decoding a column based on erasure-and-error correction using the locations in the location memory if the number in the first counter is between second and third predetermined values, and a sum of the number in the first counter plus the number in the second counter is less than a first predetermined value, and for decoding a column based on error-correction if the number in the first counter is between the second and third predetermined values, and the number of the first counter plus the number of the second counter is more than the first predetermined value.

Claim 4

An error-correcting decoder for decoding a code signal composed of n2 rows×n1 columns of symbols including error-correction codes for one of error-correction and erasure-and-error correction, and for correcting errors in the code signal based on the error-correction codes, comprising; (A) a first decoder for correcting errors of each row, and for detecting an uncorrectable-error of each row; (B) a location memory, connected to the first decoder, for memorizing locations of rows having uncorrectable-errors detected by the first decoder; (C) a first counter, connected to the first decoder, for counting a number of rows having uncorrectable errors detected by the first decoder; (D) a second counter, connected to the first decoder, for counting a number of maximum error-correction flags, a maximum error-correction flag being set for a row when a number of detected errors of the symbols in the row is equal to a maximum-correctable-error value; and (E) a second decoder, connected to the first decoder, for correcting errors of each column, for decoding a column based on erasure-and-error correction using the locations in the location memory if the number in the first counter is between second and third predetermined values, and a sum of the number in the first counter plus the number in the second counter is less than a first predetermined value, and for decoding a column based on error-correction if the number in the first counter is between the second and third predetermined values, and the number of the first counter plus the number of the second counter is more than the first predetermined value.

Claim 5

The error-correcting decoder according to claim 2, wherein the second decoder decodes a column based on erasure-and-error correction using the locations in the location memory if the number in the first counter is between the second and third predetermined values, and the number in the second counter is less than a fourth predetermined value, and decodes a column based on error-correction if the number in the first counter is between the second and the third predetermined values, and the number of the second counter is more than the fourth predetermined value.

Claim 6

The error-correcting decoder according to claim 1 or claim 2, further comprising a degree calculator for calculating a degree of a Euclid algorithm, wherein the degree calculator sets a row as an uncorrectable error row when the degree in the degree calculator is different from a number of error-locations detected in the Chien-Search circuit in a row.

Claim 7

An error-correcting decoder for decoding a code signal composed of n2 rows×n1 columns of symbols including error-correction codes for one of error-correction and erasure-and-error correction, and for correcting errors in the code signal based on the error-correction codes, comprising; (A) a first decoder for correcting errors of each row, and for detecting an uncorrectable-error of each row; (B) a location memory, connected to the first decoder, for memorizing locations of rows having uncorrectable-errors detected by the first decoder; (C) a counter, connected to the first decoder, for counting a number of rows having uncorrectable-errors detected by the first decoder; (D) a Chien-Search circuit, connected to the first decoder, for calculating error-locations and error-magnitudes of a Euclid algorithm, and for setting a number of the error-locations, wherein the number of uncorrectable-error rows is initially zero; and (E) a second decoder, connected to the first decoder, for correcting errors of each column, for decoding a column based on erasure-and-error correction using the locations in the location memory if the number in the counter is less than a first predetermined value and the number of the error-locations detected in the Chien-Search circuit is initially less than a second predetermined value, and for decoding the column based on error-correction if the number in the counter is more than the first predetermined value, and the number of the error-locations detected in the Chien-Search circuit is initially more than the second predetermined value.

Claim 8

An error-correcting decoder for decoding a code signal composed of n2 rows×n1 columns of symbols including error-correction codes for one of error-correction and erasure-and-error correction, and for correcting errors in the code signal based on the error-correction codes, comprising; (A) a first decoder for correcting errors of each row, and for detecting an uncorrectable-error of each row; (B) a location memory, connected to the first decoder, for memorizing locations of rows having uncorrectable-errors detected by the first decoder; (C) a counter, connected to the first decoder, for counting a number of rows having uncorrectable-errors detected by the first decoder; (D) a Chien-Search circuit, connected to the first decoder, for calculating error-locations and error-magnitudes of a Euclid algorithm, and for setting a number of the error-locations, wherein the number of uncorrectable-error rows is initially zero; and (E) a second decoder, connected to the first decoder, for correcting errors of each column, for decoding a column based on erasure-and-error correction using the locations in the location memory if the number in the counter is less than a first predetermined value and the number of the error-locations detected in the Chien-Search circuit is initially less than a second predetermined value, and for decoding the column based on error-correction if the number in the counter is more than the first predetermined value, and the number of the error-locations detected in the Chien-Search circuit is initially more than the second predetermined value.

Claim 9

The error-correcting decoder according to claim 1 or claim 2 or claim 5, wherein the first decoder corrects only the uncorrectable-errors in each row after the second decoder corrects errors in each column.

Claim 10

The error-correcting decoder according to claim 5, further comprising a degree calculator for calculating a degree of a Euclid algorithm, and for detecting an uncorrectable-error if the degree in the degree calculator is different from the number of the error-locations detected in the Chien-Search circuit.

Claim 11

The error-correcting decoder according to claim 5, further comprising a flag memory, connected to the first decoder, for setting a burst-error flag on if a number of detected consecutive uncorrectable-errors in each row exceeds a third predetermined value, wherein the second decoder decodes a column based on erasure-and-error correction using the locations in the location memory if the burst-error flag is on, and the number of the error-locations detected in the Chien-Search circuit is initially more than a second predetermined value, and decodes a column based on error-correction if the burst-error flag is set off, and the number of the error-locations detected in the Chien-Search circuit is initially more than the second predetermined value.

Claim 12

The error-correcting decoder according to claim 5, further comprising a second counter, connected to the first decoder, for counting a number of maximum error-correction flags, a maximum error-correction flag being set for a row if the number of detected errors of the symbols in each row is equal to a maximum-correctable-error value, wherein the second decoder decodes a column based on erasure-and-error correction using the locations in the location memory if the number in the second counter is less than a third predetermined value, and the number of the error-locations detected in the Chien Search circuit is initially less than the second predetermined value, and decodes a column based on error-correction if the number in the second counter is more than the third predetermined value, and the number of the error-locations detected in the Chien Search circuit is initially more than the second predetermined value.

Claim 15

A decoding method for decoding a code signal composed of n1 rows×n2 columns of symbols including error-correction codes, and for correcting errors of the code signal, comprising the steps of; (A) generating location polynomials based on syndromes of the code signal; (B) for each row, analyzing error-locations and error-magnitudes of the row based on the location polynomial; (C) for each row, correcting the row based on error-correction when an error has occurred, and a number of the error-locations is less than a first predetermined value in the row; (D) for each row, storing an element of the row in a Galois field as a uncorrectable-error element when the number of the error-locations is more than the first predetermined value in the row; (E) for each row, setting a maximum error-correction flag on if a number of detected errors of each row is equal to a maximum-correctable-error value; (F) for each column, analyzing error-locations and error-magnitudes of the column based on the location polynomial; (G) for each column, correcting the column based on erasure-and-error correction when an error has occurred, when a number of uncorrectable-error elements is less than a second predetermined value, and when a number of the maximum error-correction flags is less than a third predetermined value; and (H) for each column, correcting the column based on error correction when an error has occurred, a number of the uncorrectable-error elements is less than the second predetermined value, and the number of the maximum error-correction flags is more than the third predetermined value.

Claim 16

A decoding method for decoding a code signal composed of n1 rows×n2 columns of symbols including error-correction codes, and for correcting errors of the code signal, comprising the steps of; (A) generating location polynomials based on syndromes of the code signal; (B) for each row, analyzing error-locations and error-magnitudes of the row based on the location polynomial; (C) for each row, correcting the row based on error-correction when an error has occurred, and a number of the error-locations is less than a first predetermined value in the row; (D) for each row, storing an element of the row in a Galois field as a uncorrectable-error element when the number of the error-locations is more than the first predetermined value in the row; (E) for each row, setting a maximum error-correction flag on if a number of detected errors of each row is equal to a maximum-correctable-error value; (F) for each column, analyzing error-locations and error-magnitudes of the column based on the location polynomial; (G) for each column, correcting the column based on erasure-and-error correction when an error has occurred, when a number of uncorrectable-error elements is less than a second predetermined value, and when a number of the maximum error-correction flags is less than a third predetermined value; and (H) for each column, correcting the column based on error correction when an error has occurred, a number of the uncorrectable-error elements is less than the second predetermined value, and the number of the maximum error-correction flags is more than the third predetermined value.

Claim 17

The decoding method according to claim 10 or claim 11, further comprising the steps of, for each row, comparing the value of the degree in the location polynomial with the number of the error-locations, and of, for each row, setting an element as a uncorrectable-error element when the degree in the location polynomial is different from the number of the error-locations.

Claim 18

The decoding method according to claim 10 or claim 11, further comprising the steps, between steps (F) and (G), of, for each row, comparing the value of the degree in the location polynomial with the number of the error-locations, and of, for each row, leaving an error as it is when the degree in the location polynomial is different from the number of the error locations.

Claim 19

A decoding method for decoding a code signal composed of n2 rows×n1 columns of symbols including error-correction codes, and for correcting errors of the code signal, comprising the steps of: (A) generating location polynomials based on syndromes of the code signal; (B) for each row, analyzing error-locations and error-magnitudes of the row based on the location polynomial; (C) for each row, correcting the row based on the error-correction codes when an error has occurred, and when a number of the error-locations is less than a first predetermined value in the row; (D) for each row, storing an element of the row in a Galois field as an uncorrectable-error element when the number of the error-locations is more than the first predetermined value in the row; (E) for each column, analyzing error-locations and error-magnitudes of the column based on the location polynomial assuming that every element has a correctable-error; (F) for each column, analyzing error-locations and error-magnitudes of the column based on the location polynomial when a number of the error locations analyzed in the step (E) is more than a second predetermined value; (G) for each column, correcting the column based on erasure-and-error-correction when a number of the uncorrectable-error elements is less than a third predetermined value; and (H) for each column, correcting the column based on error-correction when the number of the uncorrectable-error elements is more than the third predetermined value.

Claim 20

A decoding method for decoding a code signal composed of n2 rows×n1 columns of symbols including error-correction codes, and for correcting errors of the code signal, comprising the steps of: (A) generating location polynomials based on syndromes of the code signal; (B) for each row, analyzing error-locations and error-magnitudes of the row based on the location polynomial; (C) for each row, correcting the row based on the error-correction codes when an error has occurred, and when a number of the error-locations is less than a first predetermined value in the row; (D) for each row, storing an element of the row in a Galois field as an uncorrectable-error element when the number of the error-locations is more than the first predetermined value in the row; (E) for each column, analyzing error-locations and error-magnitudes of the column based on the location polynomial assuming that every element has a correctable-error; (F) for each column, analyzing error-locations and error-magnitudes of the column based on the location polynomial when a number of the error locations analyzed in the step (E) is more than a second predetermined value; (G) for each column, correcting the column based on erasure-and-error-correction when a number of the uncorrectable-error elements is less than a third predetermined value; and (H) for each column, correcting the column based on error-correction when the number of the uncorrectable-error elements is more than the third predetermined value.

Claim 21

The method according to claim 10 or claim 11 or claim 14, further comprising the steps, following the last step, of filling in the uncorrectable-error elements of the rows using the correcting step for each column, and of correcting the code data again based on the filling step.

Claim 22

The decoding method according to claim 14, further comprising the steps of, for each row, comparing the degree in the location polynomial with the number of the error-locations, and of setting the element as an uncorrectable-error element when the degree in the location polynomial is different from the number of the error locations.

Claim 23

The method according to claim 14, further comprising the steps, between step (F) and (G), of, for each row, comparing the value of the degree in the location polynomial with the number of the error-locations, and of, for each column, leaving an error as it is when the degree in the location polynomial in the column is different from the number of the error-locations.

Claim 24

A receiver comprising: (A) a receiving interface for receiving a code signal from a transmission line; (B) an error-correcting decoder having a first decoder for correcting errors in each row of the code signal, a location memory for storing locations of rows including uncorrectable-errors, a flag memory for setting a burst-error flag on when a number of detected consecutive uncorrectable-errors exceeds a first predetermined value, a counter for counting a number of rows including uncorrectable-error, and a second decoder for correcting errors in each column, for decoding a column based on erasure-and-error correction using the locations in the location memory when the number in the counter is between a second and third predetermined values, and the burst-error flag is set on, and for decoding a column based on error correction when the number in the counter is between the second and third predetermined values and the burst-error flag is off; and (C) a receiving circuit.

Claim 25

A receiver comprising: (A) a receiving interface for receiving a code signal from a transmission line; (B) an error-correcting decoder having a first decoder for correcting errors in each row of the code signal, a location memory for storing locations of rows including uncorrectable-errors, a flag memory for setting a burst-error flag on when a number of detected consecutive uncorrectable-errors exceeds a first predetermined value, a counter for counting a number of rows including uncorrectable-error, and a second decoder for correcting errors in each column, for decoding a column based on erasure-and-error correction using the locations in the location memory when the number in the counter is between a second and third predetermined values, and the burst-error flag is set on, and for decoding a column based on error correction when the number in the counter is between the second and third predetermined values and the burst-error flag is off; and (C) a receiving circuit.

Claim 26

A player comprising: (A) a playback interface for receiving a recorded code signal; (B) an error-correcting decoder having a first decoder for correcting errors in each row of the code signal, a location memory for storing locations of rows including uncorrectable-errors, a flag memory for setting a burst-error flag on when a number of detected consecutive uncorrectable-errors of a row exceeds a first predetermined value, a counter for counting a number of rows including an uncorrectable-error, and a second decoder for correcting errors in each column, for decoding a column based on erasure-and-error correction using the locations in the location memory when the number in the counter is between a second and third predetermined value, and the burst-error flag is set on, and for decoding a column based on error-correction when the number in the counter is between the second and third predetermined values, and the burst-error flag is off; and (C) a playback circuit.

Claim 27

A player comprising: (A) a playback interface for receiving a recorded code signal; (B) an error-correcting decoder having a first decoder for correcting errors in each row of the code signal, a location memory for storing locations of rows including uncorrectable-errors, a flag memory for setting a burst-error flag on when a number of detected consecutive uncorrectable-errors of a row exceeds a first predetermined value, a counter for counting a number of rows including an uncorrectable-error, and a second decoder for correcting errors in each column, for decoding a column based on erasure-and-error correction using the locations in the location memory when the number in the counter is between a second and third predetermined value, and the burst-error flag is set on, and for decoding a column based on error-correction when the number in the counter is between the second and third predetermined values, and the burst-error flag is off; and (C) a playback circuit.

Claim 30

The method of claim 20, wherein the method of determining when a burst error has occurred includes: determining a second number representing a largest number of consecutive data sets along the first dimension which have errors; and determining that a burst error has occurred when the second number exceeds a second value.

Claim 31

The method of claim 20, further including the step of: after completion of error correction for data sets along the second dimension, repeating the step of performing error correction for data sets along the first dimension where previously error correction was not possible from the error correction coding in the first dimension.

Claim 32

The method of claim 20, further including the step of: calculating an error polynomial after performing error correction for data sets along the first dimension, wherein the error polynomial represents locations of errors and number of errors.

Claim 33

The method of claim 23, wherein a Euclid algorithm generates the location polynomial, and the polynomial is solved using a Chien Search to obtain error locations and error magnitudes.

Claim 34

The method of claim 24, wherein the error locations are stored in memory elements corresponding to locations within a Galois field.

Claim 37

The method of claim 26, further including the step of: after completion of error correction for data sets along the second dimension, repeating the step of performing error correction for data sets along the first dimension where previously error correction was not possible from the error correction coding in the first dimension.

Claim 38

The method of claim 26, further including the step of: calculating an error polynomial after performing error correction for data sets along the first dimension, wherein the error polynomial represents locations of errors and number of errors.

Claim 39

The method of claim 28, wherein a Euclid algorithm generates the location polynomial, and the polynomial is solved using a Chien Search to obtain error locations and error magnitudes.

Claim 40

The method of claim 29, wherein the error locations are stored in memory elements corresponding to locations within a Galois field.

Claim 43

The apparatus of claim 31, wherein the means for determining when a burst error has occurred includes: means for determining a second number representing a largest number of consecutive data sets along the first dimension which have errors; and means for determining that a burst error has occurred when the second number exceeds a second value.

Claim 44

The apparatus of claim 31, further including: means for performing error correction for data sets along the first dimension where previously error correction was not possible from the error correction coding in the first dimension after completion of error correction for data sets along the second dimension.

Claim 45

The apparatus of claim 31, further including means for calculating an error polynomial after performing error correction for data sets along the first dimension, wherein the error polynomial represents locations of errors and number of errors.

Claim 46

The apparatus of claim 34, wherein the means for calculating an error polynomial includes a Euclid algorithm, and the means for solving the error polynomial includes means for using a Chien Search to obtain error locations and error magnitudes.

Claim 47

The apparatus of claim 35, wherein the error locations are stored in memory elements corresponding to locations within a Galois field.

Claim 50

The apparatus of claim 37, further including: means for performing error correction for data sets along the first dimension where previously error correction was not possible from the error correction coding in the first dimension after completion of error correction for data sets along the second dimension.

Claim 51

The apparatus of claim 37, further including; means for calculating an error polynomial after performing error correction for data sets along the first dimension, wherein the error polynomial represents locations of errors and number of errors.

Claim 52

The apparatus of claim 39, wherein the means for calculating an error polynomial includes a Euclid algorithm, and the means for solving the error polynomial includes means for using a Chien Search to obtain error locations and error magnitudes.

Claim 53

The apparatus of claim 40, wherein the error locations are stored in memory elements corresponding to locations within a Galois field.