US3568148A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Decoder for error correcting codes
Assignee: Radiation Inc
•
Filing: 1969-04-02
•
Granted: 1971-03-02
•
Expires: 1989-04-02
Abstract
Abstract A decoder for error correcting binary cyclic group codes consisting of code words to be transmitted in blocks of n bits including k information bits and n-k check bits, includes a syndrome calculator for computing the matrix product of each received word, which may have a maximum of t correctable transmission errors, with a modified form of the original parity check matrix defined by the check digits in the original code. The parity check matrix used in the computation is effectively modified by the syndrome calculator by development within the calculator of a syndrome or pattern of parity check failures corresponding to that which would be produced by multiplication of the received word with the desired modified parity check matrix. This operation spreads out the columns of the identity matrix into which the original parity check matrix is partitionable, from their original locations in consecutive columns in the original parity check matrix to spaced columns in the modified matrix, to permit examination of a larger set of error patterns than can ordinarily be contained in the syndrome. Decoding may then proceed in a conventional manner.
Inventors
- 👤 George C Clark Jr
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 20:30
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0056; H04L1/0057; H03; H03M; H03M13/00; H03M13/37; H03M13/43
Claims Analysis
Total Claims: 13
Claim 1
Independent Claim
364 words
A decoder for an error correcting digital group code transmitted from an encoder in the form of consecutive code words of block length n including k information digits and n-k check digits, and having associated therewith a known parity check matrix containing an identity matrix as consecutive columns of the parity check matrix, said decoder being capable of correcting a maximum number of t transmission errors in a received word, said decoder comprising: a syndrome calculator responsive to each word received from said encoder for computing the matrix product of said received word with a modified form of said parity check matrix in which said columns forming said identity matrix are separated from one another in the modified parity check matrix, said matrix product constituting a syndrome defining the pattern of transmission errors in said received word; an n-position storage means responsive simultaneously with said syndrome calculator to said received word for storage of said received word, and means for selectively coupling predetermined positions in said storage means to selectively circulate the contents of said storage means; said selective coupling means being responsive to completion of entry of the entire received word into said syndrome calculator and into said storage means for circulating said received word in said storage means one digit at a time; said syndrome calculator including a n-k position storage means for storing said computed syndrome in the form of a series of n-k digits, said syndrome being advanced in position synchronously in said calculator storage means with the digitby-digit circulation of said received word in said n-position storage means and being thereby subjected to continued recalculation; means responsive to the digits stored in said calculator storage means at each single digit advancement thereof for detecting the existence of t or fewer errors in said received word and thereby identifying a correctable error pattern in said received word; and means for selectively adding the digits in the n-k positions of said calculator storage means to positions of said recieved word in said n-positions storage means predetermined to produce correction of the errors in said received word, when the existence of t or fewer errors in detected by said error detecting means.
Claim 2
Dependent Claim
364 words
A decoder for an error correcting digital group code transmitted from an encoder in the form of consecutive code words of block length n including k information digits and n-k check digits, and having associated therewith a known parity check matrix containing an identity matrix as consecutive columns of the parity check matrix, said decoder being capable of correcting a maximum number of t transmission errors in a received word, said decoder comprising: a syndrome calculator responsive to each word received from said encoder for computing the matrix product of said received word with a modified form of said parity check matrix in which said columns forming said identity matrix are separated from one another in the modified parity check matrix, said matrix product constituting a syndrome defining the pattern of transmission errors in said received word; an n-position storage means responsive simultaneously with said syndrome calculator to said received word for storage of said received word, and means for selectively coupling predetermined positions in said storage means to selectively circulate the contents of said storage means; said selective coupling means being responsive to completion of entry of the entire received word into said syndrome calculator and into said storage means for circulating said received word in said storage means one digit at a time; said syndrome calculator including a n-k position storage means for storing said computed syndrome in the form of a series of n-k digits, said syndrome being advanced in position synchronously in said calculator storage means with the digitby-digit circulation of said received word in said n-position storage means and being thereby subjected to continued recalculation; means responsive to the digits stored in said calculator storage means at each single digit advancement thereof for detecting the existence of t or fewer errors in said received word and thereby identifying a correctable error pattern in said received word; and means for selectively adding the digits in the n-k positions of said calculator storage means to positions of said recieved word in said n-positions storage means predetermined to produce correction of the errors in said received word, when the existence of t or fewer errors in detected by said error detecting means.
Claim 3
Dependent Claim
48 words
The decoder according to claim 1 wherein said syndrome calculator provides said modification of the parity check matrix normally associated with said code by effective formation of a new parity check matrix whose rows are a linear combination of the rows of said normally associated parity check matrix.
Claim 4
Dependent Claim
74 words
The decoDer according to claim 2 wherein said syndrome calculator provides said parity check matrix modification by computing the syndrome as the product of said received word and said normally associated parity check matrix, followed by linearly transforming the contents of said n-k position storage means to a new set of contents constituting the syndrome that would be derived by computing the matrix product of said received word with said modified parity check matrix.
Claim 5
Dependent Claim
58 words
The decoder according to claim 2 wherein said syndrome calculator provides said parity check matrix modification by feeding backward and feeding forward between multiple points in said n-k position storage means to compute a syndrome corresponding to that syndrome that would be derived by computing the matrix product of said received word with said modified parity check matrix.
Claim 6
Dependent Claim
52 words
The decoder according to claim 1 wherein said selective adding means comprises means for correcting the error pattern in said received word by parallel addition of said digits in the n-k positions of said calculator storage means to the respective selected n-k positions of the received word in said n-position storage means.
Claim 7
Dependent Claim
56 words
The decoder according to claim 1 wherein said selective adding means comprises means for correcting the error pattern in said received word by serial addition of said digits in the n-k positions of said calculator storage means to the digits in the respective n-k positions of the received word upon readout from said n-position storage means.
Claim 8
Dependent Claim
368 words
A decoder for an error correcting binary cyclic group code consisting of code words to be transmitted in blocks of n bits including k information bits and n-k check bits, said check bits being a linear combination of the k information bits specified by a parity check matrix used at the decoder in determining the pattern of errors in each received word, said received words having a maximum of t correctable transmission errors, said decoder comprising: a syndrome calculator including an n-k stage shift register and logic means coupled to predetermined stages of said register for computing the product of each received word with the parity check matrix, as a pattern of the parity check failures in the received word, and further including means coupled to said logic means and to said register for developing a modified pattern of parity check failures in the form of bits in said n-k stages conforming to the product of said received word with a modified parity check matrix whose rows are a linear combination of the rows of the original parity check matrix; an n-stage shift register responsive to the incoming bits in said received word simultaneously with entry thereof in said calculator shift register for complete storage of said received word in the received sequence of bits, and including means for selectively coupling the input and output terminals of said n-stage register to circulate the stored word upon completion of entry into said n-stage shift register; said syndrome calculator responsive to said circulation of said received word in said n-stage shift register to synchronously advance said modified pattern of parity check failures in said calculator storage register one bit at a time; means responsive to the modified pattern of parity check failures currently existing in said calculator register with each one bit advance, for detecting the existence of t or fewer errors within said pattern; and means for selectively adding the bits in the n-k stages of said calculator storage register to bits in respective positions of the received word as currently stored in said n-stage storage register to correct the errors in said received word, when the existence of t of fewer errors is sensed by said detecting means.
Claim 9
Dependent Claim
368 words
A decoder for an error correcting binary cyclic group code consisting of code words to be transmitted in blocks of n bits including k information bits and n-k check bits, said check bits being a linear combination of the k information bits specified by a parity check matrix used at the decoder in determining the pattern of errors in each received word, said received words having a maximum of t correctable transmission errors, said decoder comprising: a syndrome calculator including an n-k stage shift register and logic means coupled to predetermined stages of said register for computing the product of each received word with the parity check matrix, as a pattern of the parity check failures in the received word, and further including means coupled to said logic means and to said register for developing a modified pattern of parity check failures in the form of bits in said n-k stages conforming to the product of said received word with a modified parity check matrix whose rows are a linear combination of the rows of the original parity check matrix; an n-stage shift register responsive to the incoming bits in said received word simultaneously with entry thereof in said calculator shift register for complete storage of said received word in the received sequence of bits, and including means for selectively coupling the input and output terminals of said n-stage register to circulate the stored word upon completion of entry into said n-stage shift register; said syndrome calculator responsive to said circulation of said received word in said n-stage shift register to synchronously advance said modified pattern of parity check failures in said calculator storage register one bit at a time; means responsive to the modified pattern of parity check failures currently existing in said calculator register with each one bit advance, for detecting the existence of t or fewer errors within said pattern; and means for selectively adding the bits in the n-k stages of said calculator storage register to bits in respective positions of the received word as currently stored in said n-stage storage register to correct the errors in said received word, when the existence of t of fewer errors is sensed by said detecting means.
Claim 10
Dependent Claim
226 words
In a decoder for error correcting digital group codes transmitted as consecutive code words of block length n including k information digits and n-k check digits, said check digits being a linear combination of said k information digits as specified by a known parity check matrix for the code, said matrix containing an identity matrix as consecutive columns thereof and utilized in the decoder to determine the pattern of errors in each received word, a syndrome calculator comprising: means for storing a sequence of n-k digits and for selectively advancing the sequence of stored digits in accordance with successive digits in n-k positions of a code word entered therein; means for entering received code words into said storing means; logic means connecting predetermined storage positions in said storing means to modify the sequence of stored digits by a modulo addition operation during selective advancement of the sequence; and means coupled to said logic means and to said storing means for forming from the modified sequence of digits a syndrome constituting the matrix product of the entered code word and of a modification of said known parity check matrix in which the rows of the modified parity check matrix are a linear combination of the rows of the original known parity check matrix, and the identity matrix is in nonconsecutive columns of the modified parity check matrix.
Claim 11
Dependent Claim
226 words
In a decoder for error correcting digital group codes transmitted as consecutive code words of block length n including k information digits and n-k check digits, said check digits being a linear combination of said k information digits as specified by a known parity check matrix for the code, said matrix containing an identity matrix as consecutive columns thereof and utilized in the decoder to determine the pattern of errors in each received word, a syndrome calculator comprising: means for storing a sequence of n-k digits and for selectively advancing the sequence of stored digits in accordance with successive digits in n-k positions of a code word entered therein; means for entering received code words into said storing means; logic means connecting predetermined storage positions in said storing means to modify the sequence of stored digits by a modulo addition operation during selective advancement of the sequence; and means coupled to said logic means and to said storing means for forming from the modified sequence of digits a syndrome constituting the matrix product of the entered code word and of a modification of said known parity check matrix in which the rows of the modified parity check matrix are a linear combination of the rows of the original known parity check matrix, and the identity matrix is in nonconsecutive columns of the modified parity check matrix.
Claim 12
Dependent Claim
55 words
The invention according to claim 8 wherein said syndrome is formed by calculating the matrix product of the entered word and the original known parity check matrix, followed by linearly transforming the calculated matrix product to the matrix product of the entered word and the modified parity check matrix, using said modified sequence of digits.
Claim 13
Dependent Claim
44 words
The invention according to claim 8 wherein said logic means connects storage positions in said storage means to feed forward digits from one storage position to another and to feed back digits from one storage position to another, during selective advancement of the sequence.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1974-03-01 | 1974-08-31 | 1975-03-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1978-03-01 | 1978-08-31 | 1979-03-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1982-03-01 | 1982-08-31 | 1983-03-02 | $7700.00 | Window Closed / Lapsed |