Method and apparatus for encoding low redundancy check words from source data

• US 4,375,100 A
• Filed: 10/23/1980
• Issued: 02/22/1983
• Est. Priority Date: 10/24/1979
• Status: Expired due to Term

• Current Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Matsushima, Hiroshi, Shimeki, Yasuharu, Tsuji, Shiro, Kihara, Nobuyoshi, Kato, Misao
• Primary Examiner(s): Atkinson, Charles E.
• Application Number:
  US06/199,703
• Time in Patent Office: 852 Days
• Field of Search: 371/38, 371/37, 371/40, 371/50, 371/51
• US Class Current: 714/755
• CPC Class Codes: G11B 20/1809 by interleaving
• CPC Class Codes: G11B 20/1876 Interpolating methods
• CPC Class Codes: H03M 13/29 combining two or more codes or code structures, e.g. product codes, generalised product codes, concatenated codes, inner and outer codes

Abstract

Source data is organized by a time compression memory (4) into a plurality of successive groups of data words arranged in a pattern of rows and columns with the rows corresponding to respective recording tracks. A plurality of successive groups of parity check words is provided in the same pattern of rows and columns as the data words subsequent to the data word groups. Each parity check word is derived in a parity generator (6) by modulo-2 summations from the data words selected from different data word groups. The data and check words of each row of each respective group are (a) preceded by a synchronization code provided by a sync generator (10) to allow differentiation between data and parity groups, and (b) followed by a cyclic redundancy check, (CRC) code provided by a CRCC generator (9) to allow detection of an error in that data row or check words. The parity check word is used to correct an error specified by the CRC code upon detection of an error.

Claims

1. A method of processing data words comprising the steps of organizing the data words into successive patterns of rows and columns, deriving a plurality of first parity words from columnwise data words of each pattern, arranging the first parity words in a row parallel to the rows of data words, deriving a plurality of second parity words from diagonally arranged data words of each pattern, arranging the second parity words in a pattern of rows and columns in succession to the pattern of data words, generating a check code word, and appending the check code word to each row of said data and first and second parity words for enabling detection of errors in each row.

2. A method as claimed in claim 1, further comprising the step of generating a synchronization word and appending it to the beginning of words of each row of each pattern.

3. A method as claimed in claim 1 or 2, wherein the words of each row are recorded on separate tracks of a recording medium.

4. Apparatus for processing data words comprising means for organizing the data words into successive patterns of rows and columns, means for deriving a plurality of first parity words from columnwise data words of each pattern and arranging the first parity words in a row parallel to the rows of data words, means for deriving a plurality of second parity words from diagonally arranged data words of each pattern and arranging the second parity words in a pattern of rows and columns in succession to each pattern of data words, and means for generating a check code word and appending it to each row of said data and first and second parity words for enabling detection of errors in each row.

5. Apparatus as claimed in claim 4, further comprising means for generating a synchronization word and appending it to the beginning of each row of words of each pattern.

6. Apparatus as claimed in claim 4 or 5, further comprising means for recording the words of each row on separate tracks of a recording medium.

7. A method of processing data blocks so that clustered errors in data bits derived from parallel data tracks can be detected, wherein the bits from different locations along the length of the tracks are sequentially derived, comprising arranging the sequentially derived data bits in a storage matrix of rows and columns so that data bits derived at like times from the parallel tracks are aligned in the same columns and sequential data bits derived from the same track are arranged sequentially in different columns in the same row, data bits derived at different times and from the different tracks being respectively arranged in different columns and rows, deriving a first parity bit field, each parity bit of the first parity bit field being formed by combining data bits from a plurality of the rows and a plurality of the columns such that each parity bit is responsive to a data bit in only one of said columns, the number of rows in the first field being equal to the number of rows in the matrix, the parity bits of the first parity field being formed such that every one of said data bits contributes to one and only one parity bit of the first field and the same number of data bits contributes to each parity bit of the first field.

8. The method of claim 7 wherein the first parity field includes N columns and M rows derived from the data bits and the matrix includes P columns and M rows of data bits, where each of M, N and P is an integer greater than one, the parity bit at column j, row i of the first parity field being derived by combining one data bit from each of columns N-M+j, N-2M+j, N-3M+j . . . j, such that lines drawn through entries in the matrix of the data bits forming the parity bit at column j, row i are parallel to each other and terminate at the parity bit at column j, row i, where k is selectively every column in the first parity field and i is selectively every one of the M rows.

9. The method of claim 8 wherein a second parity field having N columns is included, the bit at column r, row s of the second parity field being derived by combining the parity bit at column r, row t of the first parity field and the data bits combined to form the parity bit at column r, row t being such that a line drawn from the entry at column r, row s of the first parity field to the entry at column r, row t of the second parity field is parallel to the lines in the matrix of the data bits forming the parity bit at column r, row t of the first parity field, where r is selectively every one of the N columns;

and s and t are selectively every one of the M rows.

10. The method of claim 7 or 8 wherein column u of the matrix includes a parity bit derived by combining the data bits from all of the rows containing data bits of column u, and column v of the first parity field includes a parity bit derived by combining the data bits from all of the rows containing parity bits of column v, where u is selectively every row of the block containing data bits and v is selectively every row of the first parity field.

11. Apparatus for processing data blocks so that clustered errors in data bits derived from parallel data tracks can be detected comprising means for reading the parallel data tracks so the bits from different locations along the length of the tracks are sequentially derived and bits from the same locations of the different tracks are simultaneously derived in parallel, a storage matrix responsive to the bits of the read data tracks, means for arranging the sequentially derived data bits in rows and columns of the storage matrix so that data bits derived at like times from the parallel tracks are aligned in the same columns and sequential data bits derived from the same track are arranged sequentially in different columns in the same row, data bits derived at different times and from the different tracks being respectively arranged in different columns and rows, means responsive to the data bits stored in the matrix for deriving a first parity bit field, said last named means including means for combining data bits from a plurality of the rows and a plurality of the columns such that each parity bit of the first parity bit field is responsive to a data bit in only one of said columns, the number of rows in the first field being equal to the number of rows in the matrix, the parity bits of the first parity field being formed such that every one of said data bits contributes to one and only one parity bit of the first field, and the same number of data bits contributes to each parity bit of the first field.

12. The apparatus of claim 11 wherein the first parity field includes N columns and M rows derived from the data bits and the matrix includes P columns and M rows of data bits, where each of M, N and P is an integer greater than one, the combining means including means for deriving the parity bit at column j, row i of the first parity field by combining one data bit from each of columns N-M+j, N-2M+j, N-3M+j . . . j, such that lines drawn through entries in the matrix of the data bits forming the parity bit at column j, row i are parallel to each other and terminate at the parity bit at column j, row i, where k is selectively every column in the first parity field and i is selectively every one of the M rows.

13. The apparatus of claim 12 wherein the matrix includes a second parity field having N columns, the combining means including means for combining the parity bit at column r, row t of the first parity field and means for combining selected ones of the data bits to form the parity bit at column r, row t, the selected data bits being selected such that a line drawn from the entry at column r, row s of the first parity field is parallel to the lines in the matrix of the data bits forming the parity bit at column r, row t of the first parity field, where r is selectively every one of the N columns;

and s and t are selectively every one of the M rows.

14. The apparatus of claim 11 or 12 wherein each of columns u and v of the matrix includes a parity bit, the combining means including:

means for combining the data bits from all of the rows containing data bits of column u to form the parity bit of column u, and means for combining the data bits from all of the rows containing parity bits of column v to form the parity bit of column v, where u is selectively every row of the block containing data bits and v is selectively every row of the first parity field.