Patent US2356896A successfully refreshed from Google Patents.
EP0273676A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Single track orthogonal error correction system
Assignee: 3M Co
•
Filing: 1987-12-22
•
Granted: —
•
Expires: 2007-12-22
Abstract
Abstract An error correcting system and method for use with a continuous serialized stream of digital information, such as present with digitized stereo audio signals, in which data is formatted (16) 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 (14) 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.
Inventors
- 👤 Richard W. C/O Minnesota Mining And Molstad
- 👤 Robert J. C/O Minnesota Mining And Youngquist
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-23 20:45
CPC Classifications
G; G11; G11B; G11B20/00; G11B20/10; G11B20/18; H; H03; H03M; H03M13/00; H03M13/31; G11B20/1806; G11B20/1809; H03M13/03; H03M13/05
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
280 words
A system for correcting errors in a serialized stream of digital data; comprising means (14, 16) 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 frames and sync words defining the locations of successive frames; means (18, 20, 22) for transpositioning said succession of frames through a data communication system in which errors in said words within said frames may result, means (24) for receiving said transpositioned succession of frames and responsive to a said error check code word for providing an error signal upon determining an erroneously received data or parity word within a given frame, means (26) responsive to a said error signal for operating on other data and parity words for reconstructing an erroneous data word and for substituting a reconstructed data word in place of said erroneous data word, wherein said encoding means (14) further comprises a) means (52, 62, 64) for selecting from said input digital signal at least two sets of data words, each set of which is orthogonal to each other set, having only one common data word, and b) means (72) for operating on each of said sets to produce corresponding parity words which when processed together with all but one data word of each set can regenerate the remaining data word of that set, and wherein said means (26) for a reconstructing erroneous data word comprises means (146, 148, 168, 170) 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 for reconstructing said erroneous data word.
Claim 2
Independent Claim
280 words
A system for correcting errors in a serialized stream of digital data; comprising means (14, 16) 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 frames and sync words defining the locations of successive frames; means (18, 20, 22) for transpositioning said succession of frames through a data communication system in which errors in said words within said frames may result, means (24) for receiving said transpositioned succession of frames and responsive to a said error check code word for providing an error signal upon determining an erroneously received data or parity word within a given frame, means (26) responsive to a said error signal for operating on other data and parity words for reconstructing an erroneous data word and for substituting a reconstructed data word in place of said erroneous data word, wherein said encoding means (14) further comprises a) means (52, 62, 64) for selecting from said input digital signal at least two sets of data words, each set of which is orthogonal to each other set, having only one common data word, and b) means (72) for operating on each of said sets to produce corresponding parity words which when processed together with all but one data word of each set can regenerate the remaining data word of that set, and wherein said means (26) for a reconstructing erroneous data word comprises means (146, 148, 168, 170) 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 for reconstructing said erroneous data word.
Claim 3
Dependent Claim
45 words
A system according to claim 1, wherein said encoding means (14) further comprises means (52) for temporarily storing at least a minimum number of data words of a said input digital signal and for selecting from said stored data words said sets of data words.
Claim 4
Dependent Claim
31 words
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.
Claim 5
Dependent Claim
37 words
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.
Claim 6
Dependent Claim
60 words
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 on all data words and parity words within all three sets containing a said erroneous data word for reconstructing said erroneous data word.
Claim 7
Dependent Claim
44 words
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.
Claim 8
Dependent Claim
46 words
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.
Claim 9
Dependent Claim
38 words
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.
Claim 10
Dependent Claim
24 words
A system according to claim 8, wherein said encoding means comprises means for formatting 48 data words and twelve parity words into each frame.
Claim 11
Dependent Claim
126 words
A system according to claim 1, wherein said encoding means comprises means for generating each parity word from a set of twelve stored data words, each word being selected so as to be spatially separated in the incoming data stream a distance greater than the largest error anticipated during transposition, according to a matrix of four rows and three columns in which each data word appears three times in each row and never appears in any other row, thus assuring that each data word will only appear in three data sets, and in which data successively moves along that row in a fashion such that it appears no more than one with any other data word in any set, thus resulting in said orthogonal data sets.
Claim 12
Dependent Claim
266 words
A system according to claim 10, wherein said encoding means comprises means for selecting the data words consistent with the following matrix: A through L being respective positions in the matrix at which selected data words are positioned at any given time, a through i being the spatial offsets between words in each row in each of the respective columns and o through v being the spatial offsets between words in each column in each of the respective rows, wherein when a data word of the incoming data stream to be formatted in frame N is at position A, the data words at positions D, G and J will be words selected from the incoming data stream to be formatted in frames spatially separated from the frame in which the word in the immediately preceding row of the matrix will be placed by a distance a=4w+1, d=4x+2, and g=4y+3, respectively, where W, X and Y are integers, thus ensuring that the data words in each row will be formatted in frames which are spatially remote from each other, and wherein the data words in each successive column along each row will be words selected from the incoming data stream which are spatially separated from the word in the same row and preceding column position by a distance o through v respectively, each spatial separation being four times a given integer, each unit integer being equal to the spatial length of each frame, and each integer being different from all other integers and from the separation between data words in the respective rows of the first column.
Claim 13
Dependent Claim
111 words
A system according to claim 11, wherein said encoding means comprises means for selecting the data words at the respective positions in said matrix such that the integers o and p defining the spatial separation between the positions of the first row are 16 and 20, respectively, the integers q and r defining the spatial separation between the positions of the second row are 17 and 21, respectively, the integers s and t defining the spatial separation between the positions of the third row are 18 and 22, respectively, and the integers u and v defining the spatial separation between the positions of the fourth row are 19 and 23 respectively.
Claim 14
Dependent Claim
24 words
A system according to claim 12, wherein said encoding means comprises means for selecting the integers w, x and y to all equal three.
Claim 15
Dependent Claim
37 words
A system according to claim 13, 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 in the incoming data stream:
Claim 16
Dependent Claim
61 words
A system according to claim 10, 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.
Claim 17
Dependent Claim
57 words
A system according to claim 1, wherein said encoding means comprises means for formatting each frame to contain forty-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.
Claim 18
Independent Claim
252 words
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 each 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 an erroneously received data or parity word within a given frame, responding to a said frame error signal, operating on other data and parity words to reconstruct an erroneous data word and substituting a reconstructed data word in place of said erroneous data word, wherein said step of encoding further comprises selecting from said input digital signal at least two sets of data words, each set of which is orthogonal to each other set, having only one common data word, operating on each of said sets to produce corresponding parity words which when processed together with all but one data word of each set can regenerate the remaining data word of that set, and reconstructing erroneous data word by responding to the data words and associated parity word by responding to the data words and associated parity words of least one of said orthogonal sets in which said erroneous data word was included for reconstructing said erroneous data word.
Claim 19
Independent Claim
252 words
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 each 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 an erroneously received data or parity word within a given frame, responding to a said frame error signal, operating on other data and parity words to reconstruct an erroneous data word and substituting a reconstructed data word in place of said erroneous data word, wherein said step of encoding further comprises selecting from said input digital signal at least two sets of data words, each set of which is orthogonal to each other set, having only one common data word, operating on each of said sets to produce corresponding parity words which when processed together with all but one data word of each set can regenerate the remaining data word of that set, and reconstructing erroneous data word by responding to the data words and associated parity word by responding to the data words and associated parity words of least one of said orthogonal sets in which said erroneous data word was included for reconstructing said erroneous data word.
Claim 20
Dependent Claim
29 words
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.
Claim 21
Dependent Claim
31 words
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.
Claim 22
Dependent Claim
45 words
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 within all three sets containing a said erroneous data word for reconstructing said erroneous data word.
Claim 23
Dependent Claim
119 words
A method according to claim 17, comprising generating each parity word from a set of twelve stored data words, each word being selected so as to be spatially separated in the incoming data stream a distance greater than the largest error anticipated during transposition, according to a matrix of four rows and three columns in which each data word appears three times in each row and never appears in any other row, thus assuring that each data word will only appear in three data sets, and by successively moving data along that row in a fashion such that it appears no more than once with any other data word in any set, thus resulting in said orthogonal data sets.
Claim 24
Dependent Claim
251 words
A method according to claim 21, wherein said encoding means comprises a) selecting the data words consistent with the following: A through L being respective position in the matrix at which selected data words are positioned at any given time, a through i being the spatial offsets between words in each row in each of the respective columns and o through v being the spatial offsets between words in each column in each of the respective rows, b) selecting a data word of the incoming data stream to be formatted in frame N is at position A, selecting corresponding data words at positions D, G and J from the incoming data stream which are spatially separated from the frame in which the word in the immediately preceding row of the matrix will be placed by a distance a=4w+1, d=4X+2, and q=4y+3, respectively, wherein W, X and Y are integers, thus ensuring that the data words in each row will be formatted in frames which are spatially remote from each other, and c) selecting the data words in each successive column along each row so as to be separated from the word in the same row and preceding column position by a distance o through v respectively, each spatial separation being four times a given integer, each unit integer being equal to the spatial length of each frame, and each integer being different from all other integers and from the separation between data words in the respective rows of the first column.
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.