Patent US4958349A successfully refreshed from Google Patents.
US4958349A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High data rate BCH decoder
Assignee: Lockheed Martin Corp
•
Filing: 1988-11-01
•
Granted: 1990-09-18
•
Expires: 2008-11-01
Abstract
Abstract A decoder for selected linear error correcting codes, such as a BCH code, uses relatively low-speed circuitry to determine syndromes and corresponding error locations for correcting the code. In a specific embodiment of a BCH linear cyclic invariant error correcting code, only cyclic invariants are stored in Read Only Memory such that the storage requirements of the Read Only Memory are minimized, and table look-up techniques are employed to speed apparent computation. In another specific embodiment of a linear error correcting codes, a Read Only Memory is used to store precomputed indicia of possible errors in the code word, and table look-up techniques are employed to determine one or more syndromes. The table look-up method avoids the complexity of error locating polynomials, algebraic root finders and real-time computation while reducing computation time. The apparatus may be constructed making maximum use of the standard, commercially available, relatively low-cost integrated circuits, but it is nevertheless capable of operating at speeds in excess 1 GBPS.
Inventors
- 👤 Robert M. Tanner
- 👤 Richard Koralek
- 👤 Frank Chethik
- 👤 Stephen B. Lengel
- 👤 David H. Miller
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 10:25
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
148 words
An apparatus for decoding in linear error correcting code, said decoding being at data speeds greater than direct computation capabilities of error computation circuitry, said apparatus comprising: first register means for temporarily storing a complete representation of an input code word; means for determining at least one syndrome to identify errors in said input code word; means coupled to said syndrome determining means for identifying from said at least one syndrome a corresponding error location in said input code word by table lock-up to maximize processing speed, said error location identifying means including a first memory means storing a cyclic invariant representation of error patterns for each syndrome to minimize the size of said memory means for use by table lock-up; and means coupled to said error location identifying means and to said first register means for correcting said input code word from said at least one syndrome.
Claim 2
Independent Claim
148 words
An apparatus for decoding in linear error correcting code, said decoding being at data speeds greater than direct computation capabilities of error computation circuitry, said apparatus comprising: first register means for temporarily storing a complete representation of an input code word; means for determining at least one syndrome to identify errors in said input code word; means coupled to said syndrome determining means for identifying from said at least one syndrome a corresponding error location in said input code word by table lock-up to maximize processing speed, said error location identifying means including a first memory means storing a cyclic invariant representation of error patterns for each syndrome to minimize the size of said memory means for use by table lock-up; and means coupled to said error location identifying means and to said first register means for correcting said input code word from said at least one syndrome.
Claim 3
Dependent Claim
60 words
The apparatus according to claim 1 wherein the error correcting code is selected from linear cyclic invariant error correcting codes whose generator polynomials can be factored, wherein said first memory means further comprises a first Read Only Memory means storing a cyclic invariant representation of said error patterns in order to minimize storage of information in said first memory means.
Claim 4
Dependent Claim
39 words
The apparatus according to claim 2 wherein said location identifying means further includes means for correlating bit position between actual error patterns and stored representations of said error patterns based on said cyclic invariant representation of said error pattern.
Claim 5
Dependent Claim
48 words
The apparatus according to claim 3 further including: a serial-to-parallel converter coupled to receive input data in order to convert high-speed input data into parallel data to be processed at lower data speeds, said serial-to-parallel converter being coupled to provide said parallel data to said syndrome determining means.
Claim 6
Dependent Claim
27 words
The apparatus according to claim 1 wherein said syndrome determining means further comprises a second memory means storing indicia of possible errors in said input code word.
Claim 7
Dependent Claim
61 words
The apparatus according to claim 5 wherein said second memory further comprises a second Read Only Memory means storing at least partials of the parity of the bit-by-bit product of a received code word and rows of an H matrix representing a parity check characteristic of said code, said product corresponding to a corresponding bit of said at least one syndrome.
Claim 8
Dependent Claim
24 words
The apparatus according to claim 6 further comprising means for modulo-2 adding partial parities of said at least one syndrome to obtain said syndrome.
Claim 9
Dependent Claim
48 words
The apparatus according to claim 1 further comprising: a serial-to-parallel converter coupled to receive input data in order to convert high-speed input data into parallel data to be processed at lower data speeds, said serial-to-parallel converter being coupled to provide said parallel data to said syndrome determining means.
Claim 10
Dependent Claim
60 words
The apparatus according to claim 1 wherein said second memory comprises a second Read Only Memory means storing at least partials of the parity of the bit-by-bit product of a received code word and rows of an H matrix representing a parity check characteristic of said code, said product corresponding to a corresponding bit of said at least one syndrome.
Claim 11
Dependent Claim
24 words
The apparatus according to claim 9 further comprising means for modulo-2 adding partial parities of said at least one syndrome to obtain said syndrome.
Claim 12
Independent Claim
183 words
An apparatus for decoding a triple error correcting binary BCH code at data speeds greater than direct computation capabilities of error computation circuitry, said apparatus comprising: first register means for temporarily storing a complete representation of an input code word; means for determining a first syndrome, a second syndrome and a third syndrome to identify errors in said input code word, said syndrome determining means including a first memory means storing indicia of possible errors in said input code word; means coupled to said syndrome determining means for identifying from said first syndrome, from said second syndrome and from said third syndrome error locations in said input code word by table look-up to maximize processing speed, said error location identifying means including a second memory means storing a cyclic invariant representation of error patterns for each said syndrome to minimize the size of said memory means for use by table look-up; and means coupled to said error location identifying means and to said first register means for correcting said input code word from said first syndrome, said second syndrome and said third syndrome.
Claim 13
Independent Claim
183 words
An apparatus for decoding a triple error correcting binary BCH code at data speeds greater than direct computation capabilities of error computation circuitry, said apparatus comprising: first register means for temporarily storing a complete representation of an input code word; means for determining a first syndrome, a second syndrome and a third syndrome to identify errors in said input code word, said syndrome determining means including a first memory means storing indicia of possible errors in said input code word; means coupled to said syndrome determining means for identifying from said first syndrome, from said second syndrome and from said third syndrome error locations in said input code word by table look-up to maximize processing speed, said error location identifying means including a second memory means storing a cyclic invariant representation of error patterns for each said syndrome to minimize the size of said memory means for use by table look-up; and means coupled to said error location identifying means and to said first register means for correcting said input code word from said first syndrome, said second syndrome and said third syndrome.
Claim 14
Dependent Claim
39 words
The apparatus according to claim 11 wherein said second memory means comprises a first Read Only Memory means storing a cyclic invariant representation of said error patterns in order to minimize storage of information in said second memory means.
Claim 15
Dependent Claim
39 words
The apparatus according to claim 12 wherein said location identifying means further comprises means for correlating bit position between actual error patterns and stored representations of said error patterns based on said cyclic invariant representation of said error pattern.
Claim 16
Dependent Claim
48 words
The apparatus according to claim 13 further comprising: a serial-to-parallel converter coupled to receive input data in order to convert high-speed input data into parallel data to be processed at lower data speeds, said serial-to-parallel converter being coupled to provide said parallel data to said syndrome determining means.
Claim 17
Dependent Claim
60 words
The apparatus according to claim 14 wherein said second memory comprises a second Read Only Memory means storing at least partials of the parity of the bit-by-bit product of a received code word and rows of an H matrix representing a parity check characteristic of said code, said produce corresponding to a corresponding bit of said at least one syndrome.
Claim 18
Dependent Claim
24 words
The apparatus according to claim 15 further comprising means for modulo-2 adding partial parities of said at least one syndrome to obtain said syndrome.
Claim 19
Independent Claim
123 words
A method for decoding a linear error correcting code, said decoding being at data speeds greater than direct computation capabilities of error computation circuitry, said method comprising the steps of: temporarily storing a complete representation of an input code word; determining at least one syndrome to identify errors in said input code word; identifying from said at least one syndrome a corresponding error location in said input code word by table lock-up in a first memory means to maximize processing speed, said first memory means storing a cyclic invariant representation of error patterns for each syndrome to minimize the size of said memory means for use by table look-up; and correcting said temporarily stored input code word using said error locations so identified.
Claim 20
Independent Claim
123 words
A method for decoding a linear error correcting code, said decoding being at data speeds greater than direct computation capabilities of error computation circuitry, said method comprising the steps of: temporarily storing a complete representation of an input code word; determining at least one syndrome to identify errors in said input code word; identifying from said at least one syndrome a corresponding error location in said input code word by table lock-up in a first memory means to maximize processing speed, said first memory means storing a cyclic invariant representation of error patterns for each syndrome to minimize the size of said memory means for use by table look-up; and correcting said temporarily stored input code word using said error locations so identified.
Claim 21
Dependent Claim
59 words
The method according to claim 17 wherein said code is selected selected from linear cyclic invariant error correcting codes whose generator polynomials can be factored, and wherein said identifying step comprising comparing said at least one syndrome with a stored cyclic invariant representation of said error patterns in order to minimize storage of information in said first memory means.
Claim 22
Dependent Claim
35 words
The method according to claim 18 further including the step of correlating bit position between actual error patterns and stored representations of said error patterns based on said cyclic invariant representation of said error pattern.
Claim 23
Independent Claim
117 words
A method for decoding a linear error correcting code, said decoding being at data speeds greater than direct computation capabilities of error computation circuitry, said method comprising the steps of: temporarily storing a complete representation of an input code word; determining at least one syndrome to identify errors in said input code word by comparing said input code word with precomputed indicia of possible errors in said input code word stored in a first memory means; identifying from said at least one syndrome a corresponding error location by look-up in a table containing cyclic invariants of error locations in said input code word; and correcting said temporarily stored input code word using said error locations so identified.
Claim 24
Independent Claim
117 words
A method for decoding a linear error correcting code, said decoding being at data speeds greater than direct computation capabilities of error computation circuitry, said method comprising the steps of: temporarily storing a complete representation of an input code word; determining at least one syndrome to identify errors in said input code word by comparing said input code word with precomputed indicia of possible errors in said input code word stored in a first memory means; identifying from said at least one syndrome a corresponding error location by look-up in a table containing cyclic invariants of error locations in said input code word; and correcting said temporarily stored input code word using said error locations so identified.
Claim 25
Independent Claim
163 words
A method for decoding a linear error correcting code, said decoding being at data speeds greater than direct computation capabilities of error computation circuitry, said method comprising the steps of: temporarily storing a complete representation of an input code word; determining at least one syndrome to identify errors in said input code word by comparing said input code word with precomputed indicia of possible errors in said input code word stored in a first memory means; wherein said determining step comprises comparing said input code word precomputed indicia including at least partials of the parity of the bit-by-bit product of a received code word and rows of an H matrix representing a parity check which is characteristic of said code, said product corresponding to a corresponding bit of said at least one syndrome; identifying from said at least one syndrome a corresponding error location in said input code word; and correcting said temporarily stored input code word using said error locations so identified.
Claim 26
Independent Claim
163 words
A method for decoding a linear error correcting code, said decoding being at data speeds greater than direct computation capabilities of error computation circuitry, said method comprising the steps of: temporarily storing a complete representation of an input code word; determining at least one syndrome to identify errors in said input code word by comparing said input code word with precomputed indicia of possible errors in said input code word stored in a first memory means; wherein said determining step comprises comparing said input code word precomputed indicia including at least partials of the parity of the bit-by-bit product of a received code word and rows of an H matrix representing a parity check which is characteristic of said code, said product corresponding to a corresponding bit of said at least one syndrome; identifying from said at least one syndrome a corresponding error location in said input code word; and correcting said temporarily stored input code word using said error locations so identified.
Claim 27
Dependent Claim
26 words
The method according to claim 21 wherein said determining step further comprises modulo-2 adding partial parities of said at least one syndrome to obtain said syndrome.
References Cited (Backward Citations)
US4162480A
Cited
US4410989A
Cited
US4509172A
Cited
US4564944A
Cited
US4665523A
Cited
US4597083A
Cited
US4683571A
Cited
US4623999A
Cited
US4694455A
Cited
US4649541A
Cited
US4747103A
Cited
US4644343A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1993-09-17 | 1994-03-19 | 1994-09-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1997-09-17 | 1998-03-19 | 1998-09-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2001-09-17 | 2002-03-19 | 2002-09-18 | $7700.00 | Window Closed / Lapsed |