US5323402A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Programmable systolic BCH decoder
Assignee: MITRE BEDFORD MA A CORP OF
•
Filing: 1991-02-14
•
Granted: 1994-06-21
•
Expires: 2011-02-14
Abstract
Abstract A programmable decoder that provides both error and erasure decoding for all Reed-Solomon, primitive BCH, non-primitive BCH, and binary BCH codes of any rate over any field is disclosed. The user can specify decoding parameters including the code block-length, the code-generator polynomial, and the field-generator polynomial. The basic architecture, less the small overhead for programmability, is also recommended for fixed-code applications. The decoding processor of the decoder includes systolic arrays implementing a syndrome calculator, a key equation solver, a Chien search, a recursive extender, and an inverse transform. The number of cells required for each of the five functions is on order of the error correction capability t. The systolic arrays can be fabricated on a single VLSI microchip that is itself systolic. Each of the individual systolic arrays can extended by arraying microchips together, so that any desired error correction capability can be attained by using multiple systolic microchips with a single controller.
Inventors
- 👤 John J. Vaccaro
- 👤 Willard L. Eastman
- 👤 Thomas M. Hopkinson
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 18:27
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/60; G06F7/72; G06F7/724; H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
147 words
A programmable BCH decoder comprising: a systolic decoder processor including a first systolic array implementing a syndrome calculator, a second systolic array implementing a key equation solver, a third systolic array implementing a zero locator, a fourth systolic array implementing a recursive extender, and a fifth systolic array implementing an inverse transform, a control processor with input means for receiving decoding parameters of a BCH code and input means for receiving a coded sequence and output means for outputting a decoded sequence, and communication means between said control processor and each of the systolic arrays of said systolic decoder processor for communication of systolic inputs from said control processor to each said array and for communication of systolic outputs from each said array to said control processor, and further communication means between said control processor and said systolic decoder processor for communication of timing and control data.
Claim 2
Dependent Claim
147 words
A programmable BCH decoder comprising: a systolic decoder processor including a first systolic array implementing a syndrome calculator, a second systolic array implementing a key equation solver, a third systolic array implementing a zero locator, a fourth systolic array implementing a recursive extender, and a fifth systolic array implementing an inverse transform, a control processor with input means for receiving decoding parameters of a BCH code and input means for receiving a coded sequence and output means for outputting a decoded sequence, and communication means between said control processor and each of the systolic arrays of said systolic decoder processor for communication of systolic inputs from said control processor to each said array and for communication of systolic outputs from each said array to said control processor, and further communication means between said control processor and said systolic decoder processor for communication of timing and control data.
Claim 3
Dependent Claim
13 words
The decoder of claim 1 wherein said zero locator implements a Chien search.
Claim 4
Dependent Claim
15 words
The decoder of claim 1 wherein said key equation solver is mapped from Eastman's algorithm.
Claim 5
Dependent Claim
21 words
The decoder of claim 1 wherein the decoding parameters include the field of the BCH code, whereby said decoder is field-programmable.
Claim 6
Dependent Claim
40 words
The decoder of claim 1 wherein the decoding parameters include the field of the BCH code over the Galois field GF(2 m ) where m is an integer, whereby said decoder is field-programmable over the Galois field GF(2 m ).
Claim 7
Dependent Claim
25 words
The decoder of claim 1 wherein the decoding parameters include the code generator polynomial of the BCH code, whereby said decoder is code generator polynomial-programmable.
Claim 8
Dependent Claim
23 words
The decoder of claim 1 wherein the decoding parameters include the block length of the BCH code, whereby said decoder is block length-programmable.
Claim 9
Dependent Claim
14 words
The decoder of claim 1 wherein each said systolic array is a bit-serial processor.
Claim 10
Dependent Claim
44 words
The decoder of claim 1 wherein each said systolic array comprises cells, each cell having at least M bit-slices, and wherein said programmable decoder is field-programmable over the Galois fields GF(2 m ) where m is an integer less than or equal to M.
Claim 11
Dependent Claim
11 words
The decoder of claim 9 wherein M is equal to 8.
Claim 12
Dependent Claim
15 words
The decoder of claim 1 wherein the BCH code has a rate greater than 1/2.
Claim 13
Dependent Claim
13 words
The decoder of claim 1 wherein said decoder is optimized for error-only decoding.
Claim 14
Dependent Claim
52 words
The decoder of claim 12 wherein said first systolic array comprises 2t cells, said second systolic array comprises t+1 cells, said third systolic array comprises t+1 cells, said fourth systolic array comprises t cells, and said fifth systolic array comprises t cells, where t is the error-correcting capability of the programmable decoder.
Claim 15
Dependent Claim
15 words
The decoder of claim 1 wherein said decoder is optimized for error and erasure decoding.
Claim 16
Dependent Claim
53 words
The decoder of claim 14 wherein said first systolic array comprises 2t cells, said second systolic array comprises t+1 cells, said third systolic array comprises 2t+1 cells, said fourth systolic array comprises 2t cells, and said fifth systolic array comprises 2t cells, where ν errors and μ erasures can be corrected provided μ+2ν≦2t.
Claim 17
Dependent Claim
19 words
The decoder of claim 1 wherein said control processor implements a systolic cell associated with the key equation solver.
Claim 18
Dependent Claim
18 words
The decoder of claim 1 wherein said control processor implements a systolic cell associated with the recursive extender.
Claim 19
Dependent Claim
18 words
The decoder of claim 1 wherein the systolic arrays are resident on a single systolic decoder processor microchip.
Claim 20
Dependent Claim
128 words
The decoder of claim 1 wherein said systolic decoder processor comprises an array of M microchips, each microchip including a first systolic array implementing a syndrome calculator with n1 cells, a second systolic array implementing a key equation solver with n2 cells, a third systolic array implementing a zero locator with n3 cells, a fourth systolic array implementing a recursive extender with n4 cells, and a fifth systolic array implementing an inverse transform with n5 cells, and further comprises communication means between said microchips whereby said array of M microchips implements a systolic syndrome calculator with M×n1 cells, a systolic key equation solver with M×n2 cells, a systolic zero locator with M×n3 cells, a systolic recursive extender with M×n4 cells, and a systolic inverse transform with M×n5 cells.
References Cited (Backward Citations)
US4360916A
Cited
US4719628A
Cited
US4665523A
Cited
US4694455A
Cited
US4866716A
Cited
US5107503A
Cited
US4856004A
Cited
US4873688A
Cited
US4890286A
Cited
US4958349A
Cited
US5099482A
Cited
US5130990A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1997-06-20 | 1997-12-20 | 1998-06-21 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2001-06-20 | 2001-12-20 | 2002-06-21 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2005-06-20 | 2005-12-20 | 2006-06-21 | $7700.00 | Window Closed / Lapsed |