US4355391A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method of error detection and/or correction in a data set
Assignee: Texas Instruments Inc
•
Filing: 1980-03-31
•
Granted: 1982-10-19
•
Expires: 2000-03-31
Abstract
Abstract Matrix multiplication is used to generate error detection and/or correction binary code bits from a binary input word. A matrix made up of columns and rows of bits set to binary "1"s and "0"s in a pattern conforming to the mathematical expression of a predetermined error detection and/or correction code algorithm is set into a read only memory. The input binary word is 512 bits (64 bytes), one matrix being provided for each of the bytes. The first byte of the 512 bit word is multiplied by its respective matrix providing a ten bit binary code word. Simple odd parity is computed on the first byte and the odd parity bit is appended to the binary code word, which are stored in an accumulator. The next byte is multiplied by its respective matrix to provide another ten bit binary code word, and a simple parity bit is also generated. The second code word and parity bit combination is exclusively ORed in the accumulator with the first binary code word and first parity bit, thereby accumulating the correction and/or detection code. This procedure is continued until all 64 bytes have been handled. The 64 bytes and accompanying eleven error correction and/or detection bits are stored. When recalled from storage, the 64 bytes have the error detection and/or correction bits generated in exactly the same fashion. Means are provided for comparing the new code with the previously computed code. A read-only memory table is provided to locate any erroneous byte to identify the erroneous bit within that byte. Correction circuitry is provided to correct any error within a byte.
Inventors
- 👤 John H. Alsop, IV
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 09:54
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/19
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
87 words
Apparatus for generating a binary code word in response to an input binary word, comprising: (a) matrix generating means comprising a memory for storing and for supplying a matrix of columns and rows of bits set to binary "1"s and "0"s in a pattern conforming to the mathematical expression of a predetermined error detection and/or correction code algorithm; and (b) matrix multiplying means connected to multiply the matrix by the input binary word to yield the binary code word indicative of an error detection and/or correction code.
Claim 2
Dependent Claim
87 words
Apparatus for generating a binary code word in response to an input binary word, comprising: (a) matrix generating means comprising a memory for storing and for supplying a matrix of columns and rows of bits set to binary "1"s and "0"s in a pattern conforming to the mathematical expression of a predetermined error detection and/or correction code algorithm; and (b) matrix multiplying means connected to multiply the matrix by the input binary word to yield the binary code word indicative of an error detection and/or correction code.
Claim 3
Dependent Claim
62 words
The apparatus of claim 1 wherein the matrix multiplying means comprises: (b) (i) at least one AND gate for each bit of the input binary word and a corresponding bit of the matrix; and (ii) exclusive OR circuitry for combining the products from the AND gates in exclusive OR logic in conformance with the mathematical expression to provide the binary code word.
Claim 4
Dependent Claim
14 words
The apparatus of claim 2 wherein the exclusive OR circuitry comprises a parity generator.
Claim 5
Dependent Claim
33 words
The apparatus of claim 3 further comprising unmasked parity generating means for receiving the input binary word, generating at least one parity bit therefrom and appending the bit to the binary code word.
Claim 6
Dependent Claim
12 words
The apparatus of claim 4 wherein the memory is a read-only memory.
Claim 7
Dependent Claim
27 words
The apparatus of claim 5 wherein the number of bits in each column in the matrix corresponds to the number of bits in the input binary word.
Claim 8
Dependent Claim
136 words
Apparatus for generating a binary code word in response to an input binary word that is presented to the apparatus in not less than two sequential sections, comprising: (a) matrix generating means for supplying a matrix for each of the sequential sections, each matrix being made up of columns and rows of bits set to binary "1"s and "0"s in a pattern conforming to the mathematical expression of a predetermined error detection and/or correction code algorithm; (b) matrix multiplying means connected to multiply each matrix by the corresponding input binary word section to yield the binary code word indicative of an error detection and/or correction code for the particular section; and (c) accumulator means for accumulating the code output of the matrix multiplying means until all sections have been received and multiplied by their respective matrices.
Claim 9
Dependent Claim
136 words
Apparatus for generating a binary code word in response to an input binary word that is presented to the apparatus in not less than two sequential sections, comprising: (a) matrix generating means for supplying a matrix for each of the sequential sections, each matrix being made up of columns and rows of bits set to binary "1"s and "0"s in a pattern conforming to the mathematical expression of a predetermined error detection and/or correction code algorithm; (b) matrix multiplying means connected to multiply each matrix by the corresponding input binary word section to yield the binary code word indicative of an error detection and/or correction code for the particular section; and (c) accumulator means for accumulating the code output of the matrix multiplying means until all sections have been received and multiplied by their respective matrices.
Claim 10
Dependent Claim
39 words
The apparatus of claim 7 wherein the matrix generating means includes an addressable memory in which the matrices are stored and an address register for indexing the memory to read out the matrix that corresponds to the appropriate section.
Claim 11
Dependent Claim
62 words
The apparatus of claim 8 wherein the matrix multiplying means comprises: (b) (i) at least one AND gate for each bit of the input binary word and the corresponding bit of the matrix; and (ii) exclusive OR circuitry for combining the products from the AND gates in exclusive OR logic in conformance with the mathematic expression to provide the binary code word.
Claim 12
Dependent Claim
14 words
The apparatus of claim 9 wherein the exclusive OR circuitry comprises a parity generator.
Claim 13
Dependent Claim
34 words
The apparatus of claim 10 further comprising unmasked parity generating means for receiving the input binary word section, generating at least one parity bit therefrom and appending the bit to the binary code word.
Claim 14
Dependent Claim
45 words
The apparatus of claim 11 wherein the accumulator means is a flip-flop register for temporarily storing the binary code word and the parity bit, each position providing an input to the parity generator to cause accumulation of the binary code word and the parity bit.
Claim 15
Dependent Claim
28 words
The apparatus of claim 12 further comprising total parity bit generator means, connected to receive the outputs of the flip-flop register and to generate a parity signal therefrom.
Claim 16
Dependent Claim
256 words
Apparatus for detecting and/or correcting errors in a block of sequentially presented input binary words comprising: (a) matrix generating means for supplying a matrix for each of the input binary words, each matrix being made up of columns and rows of bits set to binary "1"s and "0"s in a pattern conforming to the mathematical expression of a predetermined error detection and/or correction code algorithm; (b) matrix multiplying means connected to multiply each matrix by the corresponding input binary word to yield a binary code word indicative of an error detection and/or correction code for the particular input binary word; (c) accumulator means for accumulating the code output of the matrix multiplying means until all the binary words have been received and multiplied by their respective matrices; (d) means connected to receive and store the block of sequentially presented input binary words; (e) means for transferring the block of sequentially presented input binary words and the associated binary code words from the accumulator into the apparatus to permit, upon input, sequentially presenting the input binary words to the matrix multiplying means to yield new binary code words; (f) comparison means for comparing each new binary code word with the corresponding binary code word transferred in; (g) error locating means, responsive to a signal from the comparison means for locating the erroneous word and the error within the word; and (h) error correcting means for receiving the located erroneous word, masking with the correct word, and toggling the contents where the mask and the erroneous word differ.
Claim 17
Dependent Claim
256 words
Apparatus for detecting and/or correcting errors in a block of sequentially presented input binary words comprising: (a) matrix generating means for supplying a matrix for each of the input binary words, each matrix being made up of columns and rows of bits set to binary "1"s and "0"s in a pattern conforming to the mathematical expression of a predetermined error detection and/or correction code algorithm; (b) matrix multiplying means connected to multiply each matrix by the corresponding input binary word to yield a binary code word indicative of an error detection and/or correction code for the particular input binary word; (c) accumulator means for accumulating the code output of the matrix multiplying means until all the binary words have been received and multiplied by their respective matrices; (d) means connected to receive and store the block of sequentially presented input binary words; (e) means for transferring the block of sequentially presented input binary words and the associated binary code words from the accumulator into the apparatus to permit, upon input, sequentially presenting the input binary words to the matrix multiplying means to yield new binary code words; (f) comparison means for comparing each new binary code word with the corresponding binary code word transferred in; (g) error locating means, responsive to a signal from the comparison means for locating the erroneous word and the error within the word; and (h) error correcting means for receiving the located erroneous word, masking with the correct word, and toggling the contents where the mask and the erroneous word differ.
Claim 18
Dependent Claim
39 words
The apparatus of claim 14 wherein the matrix generating means includes an addressable memory in which the matrices are stored and an address register for indexing the memory to read out the matrix that corresponds to the appropriate word.
Claim 19
Dependent Claim
62 words
The apparatus of claim 15 wherein the matrix multiplying means comprises: (b) (i) at least one AND gate for each bit of the input binary word and the corresponding bit of the matrix; and (ii) exclusive OR circuitry for combining the products from the AND gates in exclusive OR logic in conformance with the mathematic expression to provide the binary code word.
Claim 20
Dependent Claim
14 words
The apparatus of claim 16 wherein the exclusive OR circuitry comprises a parity generator.
Claim 21
Dependent Claim
33 words
The apparatus of claim 17 further comprising unmasked parity generating means for receiving the input binary word, generating at least one parity bit therefrom and appending the bit to the binary code word.
Claim 22
Dependent Claim
45 words
The apparatus of claim 18 wherein the accumulator means is a flip-flop register for temporarily storing the binary code word and the parity bit, each position providing an input to the parity generator to cause accumulation of the binary code word and the parity bit.
Claim 23
Dependent Claim
28 words
The apparatus of claim 20 further comprising total parity bit generator means, connected to receive the outputs of the flip-flop register and to generate a parity signal therefrom.
Claim 24
Dependent Claim
35 words
The apparatus of claim 20 wherein the means for transferring comprises a buffer memory for temporarily storing the block and contents of the accumulator, and a bus for transmission to and from the buffer memory.
Claim 25
Dependent Claim
26 words
The apparatus of claim 21 wherein the comparison means comprises an exclusive OR gate for each bit of the original and the new binary code word.
Claim 26
Dependent Claim
22 words
The apparatus of claim 22 wherein the error locating means comprises a read-only memory, addressable by the output of the comparison means.
Claim 27
Dependent Claim
40 words
The apparatus of claim 23 wherein the error correcting means comprises an exclusive NOR gate for receiving each bit of the erroneous word and each mask bit, to provide a toggled output at positions where the bits do not match.
Claim 28
Independent Claim
81 words
A method of generating a binary code word in response to an input binary word comprising the steps of: (a) forming a matrix in a memory, the matrix comprising columns and rows of bits set to binary "1"s and "0"s in a pattern conforming to the mathematical expression of a predetermined error detection and/or correction code algorithms; and (b) multiplying the matrix by the input binary word to yield the binary code word indicative of an error detection and/or correction code.
Claim 29
Independent Claim
81 words
A method of generating a binary code word in response to an input binary word comprising the steps of: (a) forming a matrix in a memory, the matrix comprising columns and rows of bits set to binary "1"s and "0"s in a pattern conforming to the mathematical expression of a predetermined error detection and/or correction code algorithms; and (b) multiplying the matrix by the input binary word to yield the binary code word indicative of an error detection and/or correction code.
Claim 30
Dependent Claim
33 words
The method of claim 25 further comprising the steps of: (c) generating at least one parity bit from the input binary word; and (d) appending the parity bit to the binary code word.
Claim 31
Dependent Claim
38 words
The method of claim 26 further comprising the steps of: (e) sectioning the input binary word into a plurality of sections; and (f) accumulating the code output together with the parity bit until all sections have been received.
Claim 32
Dependent Claim
22 words
The method of claim 27 further comprising the step of: (g) transferring the binary word and the code word out to storage.
Claim 33
Dependent Claim
80 words
The method of claim 28 further comprising the steps of: (h) transferring in the binary word and code word from storage; (i) generating a new code word by repeating steps (a) and (b) on the binary word section transferred in; (k) comparing the newly generated code word with the code word transferred in; (l) in the event of no comparison, locating the erroneous section and error within the section; and (m) correcting the erroneous section by toggling the erroneous bits.
References Cited (Backward Citations)
US3413599A
Cited
US3568148A
Cited
US4030067A
Cited
US4077028A
Cited
US4214228A
Cited
US4242752A
Cited
US4168486A
Cited
US4201337A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1985-10-18 | 1986-04-19 | 1986-10-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1989-10-18 | 1990-04-19 | 1990-10-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1993-10-18 | 1994-04-19 | 1994-10-19 | $7700.00 | Window Closed / Lapsed |