Digital data storage in video format

• US 4,495,623 A
• Filed: 09/02/1982
• Issued: 01/22/1985
• Est. Priority Date: 09/02/1982
• Status: Expired due to Fees

• Current Assignee: Discovision Associates (Pioneer Corporation)
• Original Assignee: Discovision Associates (Pioneer Corporation)
• Inventors: Yardy, Raymond, George, David J., Nguyen, Hue V.
• Primary Examiner(s): ATKINSON, CHARLES
• Application Number:
  US06/414,094
• Time in Patent Office: 873 Days
• Field of Search: 371/38, 371/40
• US Class Current: 714/755
• CPC Class Codes: G11B 20/1809 by interleaving

Abstract

A method and apparatus for encoding a plurality of bytes of digital data into a further plurality of bits suitable for storage in a storage medium, and for recovery therefrom, and for decoding the stored bits retrieved from the storage medium, for the recovery of the encoded bytes. The digital data bytes are arranged into a plurality of code blocks, each having a first predetermined number of columns and a second predetermined number of rows of bytes. A parity block of bytes of data is generated having a number of columns and a number of rows of bytes corresponding to the first predetermined number of columns and to the second predetermined number of rows of bytes, respectively, of the code blocks, the bits of data in the parity block corresponding to the computed parity of the combined corresponding bits in each of the code blocks. Secondly, a parity row of bytes of data are generated for each of the data blocks such that each bit in each byte in the parity row corresponds to the computed parity of the combined corresponding bits in each byte in the column of the associated data block of that parity row. Each such row of parity bytes is added to its associated block. Thirdly, a correction control word is generated for each 8 bit byte of data blocks, parity rows and parity blocks, and is added to its associated byte to form a composite word. The bits of data of all such composite words for all of the blocks are interleaved according to a matrix having a third predetermined number of rows and a fourth predetermined number of columns, and the interleaved data is provided in serial arrangement for storage.

Claims

1. Apparatus for correcting errors in digital data stored on a storage medium and recovered therefrom, said apparatus comprising:

means for arranging the bytes of data to be stored on the storage medium into a plurality of code blocks each having a first predetermined number of columns and a second predetermined number of rows of bytes;

first order means for generating a parity block of first order parity bytes, said parity block having a number of columns and a number of rows of bytes corresponding to said first predetermined number and said second predetermined number, respectively, such that the first order parity bits in said parity block correspond to the computed parity of the combined corresponding bits in each of said code blocks;

second order means for generating a parity row of second order parity bytes for each of said data blocks and said parity block, such that each bit of each said second order parity byte corresponds to the computed parity of the combined corresponding bits in each byte in the column of the block associated with that parity row, said second order means adding each said row to its associated block; and

means for generating a correction control word for each byte of all of said blocks, and for adding each said correction control word to each said byte for which said correction control word is generated, to form a composite word.

2. The apparatus as claimed in claim 1, further comprising:

means for interleaving the bits of said composite words for each of said blocks according to a matrix having a third predetermined number of rows and a fourth predetermined number of columns, and for providing said interleaved bits in serial arrangement for storage on the storage medium.

3. The apparatus as claimed in claim 2, further comprising:

means for disinterleaving the bits recovered from said storage medium according to the reverse of said matrix to reform said composite words.

4. The apparatus as claimed in claims 1 or 3, further comprising:

composite word error correction means for applying a first correction step to the composite words recovered from the storage medium using said correction control word to correct any single erroneous bits in each data byte or parity byte;

double error detection means for determining if more than one bit error exists in at least one of said composite words and for bypassing said composite word error correction means;

second order parity correction means responsive to said double error detection means for applying a second correction step using said row of second order parity bytes to correct said erroneous bits; and

compound error detection means for determining if said more than one bit errors cannot be corrected using said second order parity correction means and for bypassing said second order parity correction means.

5. The apparatus as claimed in claim 4, further including first order correction means responsive to said compound error detection means for correcting compound errors using the first order parity bits.

6. The apparatus as claimed in claim 1, wherein said first order means includes:

a shift register for temporarily storing as many bytes as contained in one of said blocks; and

eight Exclusive OR circuits each having one input connected to receive the data to be stored on the storage medium and the second input connected to the output of said shift register, the output of said Exclusive OR circuits being connected to the input of said shift register,

whereby when the bytes of data of a particular block are clocked through said Exclusive OR circuits, they are combined with the parity of the respective bytes of the previous blocks clocked through said Exclusive OR circuits to generate parity bytes of the particular block and the previous blocks, thereby generating the parity block.

7. The apparatus as claimed in claim 1, wherein said second order means includes:

a shift register for temporarily storing as many bytes as contained in one of said rows in said blocks; and

eight Exclusive OR circuits each having one input connected to receive data and parity bytes from said first order means and having the second input connected to the output of said shift register, the output of said Exclusive OR circuits being connected to the input of said shift register, whereby when the bytes of a particular row of a particular block are clocked through said Exclusive OR circuits, they are combined with the parity of the respective bytes of the previous rows of the particular block clocked through said Exclusive OR circuits to generate parity bytes of the particular row and the previous rows of the particular block, thereby generating the parity row for the particular block.

8. The apparatus as claimed in claim 1, wherein said means for generating a correction control word includes:

programmed permanent memory means having a plurality of addressable storage locations, each of said locations containing the correction control word for a byte of a particular value; and

addressing means for accessing the storage location containing the correction control word corresponding to the value of an input byte.

9. The apparatus as claimed in claim 2, wherein said means for interleaving includes:

addressable temporary storage means for storing a plurality of composite words equal to said third predetermined number multiplied by said fourth predetermined number, said temporary storage means having a corresponding plurality of bit storage locations, each said location having a unique address;

sequential read-in addressing means for selecting a unique one of said storage locations in which to store each one of a corresponding plurality of bits in accordance with a first predetermined sequence;

sequential read-out addressing means for sequentially selecting each of the addresses of said storage locations in a second predetermined sequence in order to read-out each of the stored bits in an order different from the storing order.

10. The apparatus as claimed in claim 9, wherein said second predetermined sequence is related to said first predetermined sequence in such a way that the bits of a composite word are separated from each other by more than the number of bits in the word.

11. The apparatus as claimed in claim 9 or 10, wherein said read-in addressing means and said read-out addressing means include programmed permanent storage means each having a corresponding plurality of sequentially selectable storage locations, the storage locations of said read-in addressing means containing the addresses of said temporary storage locations in said first predetermined sequence, the storage locations of said read-out addressing means containing the addresses of said temporary storage locations in said second predetermined sequence.

12. The apparatus as claimed in claim 9, further including:

a second addressable temporary storage means;

a second read-in addressing means connected to said second addressable temporary storage means;

a second read-out addressing means connected to said second addressable temporary storage means; and

switch means selectable between a first state activating the first-named read-in addressing means for reading bits into the first-named temporary storage means and simultaneously activating said second readout addressing means for reading bits out of said second temporary storage means, and a second state in which the first-named read-out addressing means and said second read-in addressing means are activated.

13. The apparatus as claimed in claim 4, wherein said second order parity correction means includes:

means for generating a series of column parity error bits by computing the parity of all of the bits in each column of bits of a block of data and the previously-computed parity bit for each row;

means for combining the erroneous bits in a byte indicated by said double error detection means as having more than one error with the parity error bits for the columns of bits containing the erroneous bits of that byte.

14. The apparatus as claimed in claim 13, wherein said means for generating a series of column parity error bits includes an Exclusive OR circuit;

and a shift register.

15. The apparatus as claimed in claim 13, wherein said means for combining includes an Exclusive OR circuit.

16. An error correction apparatus for detecting and correcting errors in digital information recovered from a storage medium, said apparatus comprising:

means for arranging the information to be stored on the storage medium in blocks of a selected number of bits b;

means for generating a group of n first order parity bits by computing parity for each sequence of every nth bit of the b bits of the block, where b is an integer multiple of n;

means for generating b/n+1 further groups of m second order parity bits by computing parity for each sequence of every mth bit in each sub-block of n bits of the b bits of the block and the n first order parity bits, where n is an integer multiple of m;

means for generating error correction bits for each group of c bits of the b bits of the block and the n first order parity bits and the (b/n+1)m second order parity bits, each group of c bits and its associated error correction bits, forming a composite word;

means for sequentially feeding to the storage media each composite word formed from the bits of each sub-block of n data bits and its associated second order parity bits, followed by each composite word formed from the parity bits of the n first order parity bits and their associated second order parity bits.

17. The apparatus as claimed in claim 16, wherein said means for sequentially feeding includes means for interleaving the bits such that each bit of a composite word is separated from the other bits of that composite word by more than the number of bits in the word.

18. The apparatus as claimed in claim 16, further comprising:

bit correction means receiving information recovered from the storage medium and utilizing the error correction bits in a word to correct the other bits in the word; and

second order correction means for correcting errors in the bits of each sub-block and the first order parity bits using the second order parity bits.

19. The apparatus as claimed in claim 18, further comprising:

parity error detection means including means for checking the parity of each sequence of every mth bit recovered from the storage medium with the associated second order parity bits;

error correction bit validity detection means for comparing the error correction bits of a composite word recovered from the storage medium with the remaining bits of that word;

switching means responsive to said parity error detection means and said error correction bit validity detection means to route the recovered composite word through said bit correction means if neither or both of said parity error detection means and said error correction bit validity detection means indicate the presence of an error in the recovered composite word, and to route the recovered composite word directly to said second order correction means if one or the other but not both of said parity error detection means and said error correction bit validity detection means indicates an error in a composite word.

20. The apparatus as claimed in claim 18 or 19, further comprising first order error correction means utilizing the first order parity bits to correct errors in the data bits.

21. The apparatus as claimed in claim 20, further comprising:

compound error detecting means for indicating the presence of a compound error including two or more errors in a given sequence of every mth bit in a subblock requiring the use of said first order error correction means; and

switching means for bypassing said second order error correction means when said compound error detection means indicates the presence of a compound error.

22. Apparatus for encoding a plurality of bytes of digital data into further plurality of bits suitable for storage in a storage medium and for recovery therefrom, comprising;

(a) means for arranging said bytes of data into a plurality of data blocks each having a first predetermined number of columns and a second predetermined number of rows of bytes;

(b) means for generating a parity block of bytes of data having a number of columns and a number of rows of bytes corresponding to said first predetermined number and said second predetermined number, respectively, such that the bits of data in said parity block correspond to the computed parity of the combined corresponding bits in each of said data blocks;

(c) means for generating a parity row of bytes of data for each of said data blocks and said parity block such that each bit of said parity bytes in said parity rows corresponds to the computed parity of the combined corresponding bits in each byte in the respective column of the associated block of that parity row, and for adding each said row to its associated block;

(d) means for generating a correction control word for each byte of all said data blocks and said parity block for adding each said correction control word to each said byte for which said correction control word is generated, to form a composite word; and

(e) means for interleaving the bits of said composite words of data for each of said blocks according to a matrix having a third predetermined number of rows and a fourth predetermined number of columns, and for providing said interleaved bits in serial arrangement.

23. Apparatus for decoding into recovered data bytes a plurality of bits, wherein said bits are generated from said data bytes by the steps of arranging said bytes of data into a plurality of data blocks each having a first predetermined number of columns and a second predetermined number of rows of bytes;

generating a parity block of bytes of data having a number of columns and of rows of bytes corresponding to said first predetermined number and said second predetermined number, respectively, the bits of data in said parity block corresponding to the computed parity of the combined corresponding bits in each of said data blocks;

generating a parity row of bytes of data for each of said data blocks and said parity block such that each bit of each of said parity bytes in said parity rows corresponds to the computed parity of the combined corresponding bits in each byte in the respective column of the associated block of that parity row, and adding each said row to its associated block;

generating a correction control word for each byte of all of said data blocks and said parity block, and adding said correction control word to said bytes for each said correction control word was generated, to form a composite word;

interleaving the bits of said composite words of data for each of said blocks according to a matrix having a third predetermined number of rows and a fourth predetermined number of columns, and providing said interleaved bits in serial arrangement;

comprising;

(a) means for disinterleaving said bits of data according to the reverse of said matrix into said composite words;

(b) means for determining if a bit error exists in one of said composite words and for applying a first correction step using said correction control word to correct said erroneous bit;

(c) means for determing if more than one bit error exists in at least one of said composite words and for applying a second correction step using said row of parity bytes of data to correct said erroneous bits; and

(d) means for determining if said more than one bit errors cannot be corrected using said first determining means and for applying a third correction step using said parity block of bytes to correct said errors.

24. Method for encoding a plurality of bytes of digital data into a further plurality of bits suitable for storage in a storage medium and for recovery therefrom, comprising the steps of:

(a) arranging said bytes of data into a plurality of data blocks each having a first predetermined number of columns and a second predetermined number of rows of bytes;

(b) generating a parity block of bytes of data having a number of columns and a number of rows of bytes corresponding to said first predetermined number and said second predetermined number, respectively, such that the bits of data in said parity block correspond to the computed parity of the combined corresponding bits in each of said data blocks;

(c) generating a parity row of bytes of data for each of said data blocks and said parity block such that each bit of each of said parity bytes in said parity rows corresponds to the computed parity of the combined corresponding bits in each byte in the respective column of the associated block of that parity row, and for adding each said row to its associated block;

(d) generating a correction control word for each byte of all said data blocks and said parity block, and for adding each said correction control word to each said byte for which said correction control word is generated, to form a composite word; and

(e) interleaving the bits of said composite words of data for each of said blocks according to a matrix having a third predetermined number of rows and a fourth predetermined number of columns, and for providing said interleaved bits in serial arrangement.

25. Method for decoding into recovered data bytes a plurality of bits, wherein said bits are generated from said data bytes by the steps of arranging said bytes of data into a plurality of data blocks each having a first predetermined number of columns and a second predetermined number of rows of bytes;

generating a parity block of bytes of data having a number of columns and of rows of bytes corresponding to said first predetermined number and said second predetermined number, respectively, the bits of data in said parity block corresponding to the computed parity of the combined corresponding bits in each of said data blocks;

generating a parity row of bytes of data for each of said data blocks and said parity block such that each bit of each of said parity bytes in said parity rows corresponds to the computed parity of the combined corresponding bits in each byte in the respective column of the associated block of that parity row, and adding each said row to its associated block;

generating a correction control word for each byte of all of said data blocks and said parity block, and adding said correction control word to said bytes for which said correction control word was generated, to form a composite word;

interleaving the bits of said composite words of data for each of said blocks according to a matrix having a third predetermined number of rows and a fourth predetermined number of columns, and providing said interleaved bits in serial arrangement;

said method comprising the steps of;

(a) disinterleaving said bits of data according to the reverse of said matrix into said composite words;

(b) determining if a bit error exists in one of said composite words and for applying a first correction step using said correction control word to correct said erroneous bit;

(c) determining if more than one bit error exists in at least one of said composite words and for applying a second correction step using said row of parity bytes of data to correct said erroneous bits; and

(d) determining if said more than one bit errors cannot be corrected using said first determining means and for applying a third correction step using said parity block of bytes to correct said errors.