Single track orthogonal error correction system

• US 4,791,643 A
• Filed: 12/29/1986
• Issued: 12/13/1988
• Est. Priority Date: 12/29/1986
• Status: Expired due to Fees

• Current Assignee: 3M Company
• Original Assignee: 3M Company
• Inventors: Molstad, Richard W., Youngquist, Robert J.
• Primary Examiner(s): Fleming, Michael R.
• Application Number:
  US06/947,409
• Time in Patent Office: 715 Days
• Field of Search: 371/37, 371/40, 371/38, 371/41, 371/39, 371/42, 371/43
• US Class Current: 714/762
• CPC Class Codes: G11B 20/1809 by interleaving
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/31 combining coding for error detection or correction and efficient use of the spectrum without error detection or correction H03M5/14 , H03M5/145

Abstract

An error correcting method for use with a continuous serialized stream of digital information, such as present with digitized stereo audio signals, in which data is formatted in frames containing a preselected number of data words, parity words which in combination with data words of other frames enable correction of data in yet other, spatially remote frames, error check words from which errors in any frame may be detected, and frame sync words, and wherein the parity words are encoded from three orthogonal data sets having in common a single data word so that that word can be reconstructed by operating on any of the three sets, thus enabling correction of that word even if one or two of the three sets also contains an error.

Claims

1. A system for correcting errors in a serialized stream of digital data, comprising

means for encoding an input digital signal into a succession of frames containing data words, parity words, cyclical redundancy error check code words corresponding to other words in each frame, and sync words defining the locations of successive frames;

means for moving said data having a said succession of frames through a data communication system in which errors in said words within said frames may result,

means for receiving said data having said succession of frames and responsive to a said error check code word for providing an error signal upon determining the presence of an erroneous data or parity word within a given frame,

means responsive to a said error signal for operating on other data and parity words for reconstructing a correct data word corresponding to an erroneous data word and for substituting said reconstructed correct data word in place of said erroneous data word,

wherein said encoding means further comprises

(a) memory means having successive locations for temporarily storing at least a minimum number of data words sequentially occurring in said input digital signal,

(b) means responsive to data words stored at locations selected according to a constant set algorithm for defining at least two sets of data words, each set having only one common data word, the sets thereby being orthogonal to each other and

(c) exclusive-OR logic means responsive to all data words within each of said sets for producing parity words each of which corresponds to one of the sets and which when processed by exclusive-OR logic together with all but one data word of that set can regenerate the remaining data word of that set, and

wherein said means for a reconstructing a correct data word comprises exclusive-OR logic means responsive to the data words and associated parity words of at least one of said orthogonal sets in which said erroneous data word was included.

2. A system according to claim 1, further comprising means for inserting a reconstructed corrected data word in an output stream of serialized digital data in place of an erroneous data word.

3. A system according to claim 1, wherein said reconstructing means comprises means for operating on all data words and associated parity words of all orthogonal sets containing a said erroneous data word for reconstructing said erroneous word.

4. A system according to claim 1, wherein said selecting means comprises means for selecting three independent sets of data words, each set being orthogonal with each other set, and wherein said reconstructing means comprises means for operating an all data words and parity words within all three sets containing a said erroneous data word for reconstructing said erroneous data word.

5. A system according to claim 1, wherein said encoding means comprises means for encoding said input signal into successive frames each of which contains a predetermined number of data words, and a predetermined number of parity words derived from data words of other frames.

6. A system according to claim 1, wherein said encoding means comprises means for formatting said data and parity words into record blocks containing a plurality of frames in which certain frames of a given block contain only data words and other frames contain only parity words.

7. A system according to claim 1, wherein said encoding means comprises means for formatting said frames to contain one fourth as many parity words as there are data words, thus providing 25% redundant information in the encoded frames.

8. A system according to claim 7, wherein said encoding means comprises means for formatting 48 data words and twelve parity words into each frame.

9. A system according to claim 1, wherein said encoding means comprises means for formatting each frame to contain forth-eight data words and twelve parity words and for deriving said twelve parity words of each frame N from data words in different positions within frames N-239, N-226, N-212, N-197, N-175, N-158, N-140, N-121, N-95, N-74, N-52 and N-29.

10. A system according to claim 1, wherein said means for defining at least two sets of data words comprises

(i) means for selecting twelve data words stored at any given time for each said set, each of the selected twelve data words of any given set being spatially separated in the incoming data stream from the closest other data word of that set by a predetermined spatial distance which is greater than the largest error anticipated during data movement and having a relationship with the other data words of the set which is defined by a matrix of four rows and three columns of data words, and

(ii) means for moving data words through a succession of positions along one of the three rows of the matrix such that any given data word is successively positioned in the three positions of one of the rows and never appears in any other row, thus assuring that each data word will appear in three data sets, and only in three data sets and will appear no more than once with any other data word in any given set, thus resulting in three said orthogonal data sets.

12. A system according to claim 10, wherein said means for selecting twelve data words for each set includes means responsive to a said constant set algorithm for

(i) selecting the data words consistent with the following matrix:

##STR3## where A through L are respective positions in the matrix at which said selected data words may be positioned at any given time,

a through i are the spatial offsets between said words selected to be in each row in each of the respective columns and

o through v are the spatial offsets between the words selected to be in each column in each of the respective rows,

(ii) selecting data words at positions A, D, G and J of said matrix at any given time such that the spatial offsets of the data words at those positions is given by the expression a=4w+1, d=4x+2 and g=4y+3, respectively, where w, x and y are integers, and

(iii) selecting data words at the successive positions in each successive column along each row of said matrix at any given time such that the spatial offsets o through v of the data words at each said successive position from the word in the same row and preceding column position are four times a given integer, each integer being different from all other integers and from one-fourth the spatial separation between data words positioned in the first and third columns of each row, and wherein said encoding means includes means for sequentially shifting and outputting said stored data words in a said succession of frames in which the data words are in the same spatial sequence as in the input digital signal, said parity words being formatted in frames spatially remote from the frames containing data words from which the parity words were formed.

13. A system according to claim 12, wherein means for selecting the data words at the respective positions comprises means for selecting data words such that the integers defining the spatial separations o and p between the positions of the first row are 16 and 20, respectively, the integers defining the spatial separations q and r between the positions of the second row are 17 and 21, respectively, the integers defining the spatial separations s and t between the positions of the third row are 18 and 22, respectively, and the integers defining the spatial separations u and v between the positions of the fourth row are 19 and 23 respectively.

14. A system according to claim 13, wherein said encoding means comprises means for selecting the integers w, x and y to all equal three.

15. A system according to claim 14, wherein said encoding means comprises means for selecting the data words in each position of the matrix at any given time from the following spatial positions:

space="preserve" listing-type="tabular">______________________________________ 0 64 144 13 81 165 27 99 187 42 118 210. ______________________________________

16. A system according to claim 12, comprising selecting twelve data words for each set by responding to a said constant set algorithm by

(i) selecting the data words consistent with the following matrix:

##STR4## where A through L are respective positions in the matrix at which said selected data words may be positioned at any given time,

a through i are the spatial offsets between said words selected to be in each row in each of the respective columns and

o through v are the spatial offsets between the words selected to be in each column in each of the respective rows,

(ii) selecting data words at positions A, D, G and J of said matrix at any given time such that the spatial offsets of the data words at those positions is given by the expression a=4w+1, d=4x+2 and g=4y+3, respectively, where w, x and y are integers, and

(iii) selecting data words at the successive positions in each successive column along each row of said matrix at any given time such that the spatial offsets o through v of the data words at each said successive position from the word in the same row and preceding column position are four times a given integer, each integer being different from all other integers and from one-fourth the spatial separation between data words positioned in the first and third columns of each row, and by sequentially shifting and outputting said stored data words in a said succession of frames in which the data words are in the same spatial sequence as in the input digital signal, said parity words being formatted in frames spatially remote from the frames containing data words from which the parity words were formed.

11. A system according to claim 23, wherein said encoding means comprises means for sequentially shifting stored data words through a delay system to cause each successive data word of a given set to be separated from the preceding data word by a number sequentially taken from the following progression 13, 14, 15, 22, 17, 18, 19, 26, 21, 22 and 23.

17. A method for correcting errors in a serialized stream of digital data, comprising

encoding an input digital signal into a succession of frames containing data words, parity words, cyclical redundancy error check code words corresponding to other words in each frame and sync words defining the locations of successive frames,

transpositioning said succession of frames through a data communication system in which errors in said words within said frames may result,

receiving said transpositioned succession of frames and responding to a said error check code word for providing an error signal upon determining the presence of an erroneous data or parity word within a given frame,

responding to a said error signal, operating on other data and parity words to reconstruct a correct data word corresponding to an erroneous data word and substituting said reconstructed correct data word in place of said erroneous data word, wherein said step of encoding further comprises

(a) temporarily storing at successive locations within a memory at least a minimum number of data words sequentially occurring in said input digital signal,

(b) responding to data words stored at locations selected according to a constant set algorithm and deriving at least two sets of data words, each set having only one common data word, the sets thereby being orthogonal to each other and

(c) responding by exclusive-OR logic to all data words within each of said sets and producing parity words each of which corresponds to one of the sets and which when processed by exclusive-OR logic together with all but one data word of that set can regenerate the remaining data word of that set, and

reconstructing a said correct data word via exclusive-OR logic in response to the data words and associated parity words of at least one of said orthogonal sets in which said erroneous data word was included.

18. A method according to claim 17, further comprising inserting a reconstructed corrected data word in an output stream of serialized digital data in place of an erroneous data word.

19. A method according to claim 17, comprising operating on all data words and associated parity words of all orthogonal sets containing a said erroneous data word for reconstructing said erroneous word.

20. A method according to claim 17, comprising selecting three independent sets of data words, each set being orthogonal with each set, and operating on all data words and parity words within all three sets containing a said erroneous data word for reconstructing said erroneous data word.

21. A method according to claim 17, comprising

(a) selecting twelve data words stored in any given time for each said set, each of the selected twelve data words of any given set being spatially separated in the incoming data stream from the closest other data word of that set by a predetermined spatial distance which is greater than the largest error anticipated during data movement and having a relationship with the other data words of the set which is defined by a matrix of four rows and three columns of data words, and

(b) moving data words through a succession of positions along one of the three rows of the matrix such that any given data word is successively positioned in the three positions of one of the rows and never appears in any other row, thus assuring that each data word will appear in three data sets, and only in three data sets and will appear no more than once with any other data word in any given set, thus resulting in three said orthogonal data sets.