US5040179A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High data rate BCH encoder
Assignee: Lockheed Martin Corp
•
Filing: 1989-08-18
•
Granted: 1991-08-13
•
Expires: 2009-08-18
Abstract
Abstract An encoder for selected linear error correcting codes, such as a BCH code, uses relatively low-speed circuitry to generate parities for correcting the code. A parity matrix derived from the BCH generator matrix is provided as data to a generator vector whereby the generator vector is used as a logical shift function generator. When the logical shift function is applied to the rows of the parity matrix, columns of parity are shifted into an EXCLUSIVE-OR tree to produce the parity bit of the column. The parity bit of the column is then injected into a data stream forming the encoded symbol for transmission, attaching the parity word following the data word. The apparatus may be constructed making maximum use of the standard, commerically available, relatively low-cost integrated circuits, but it is nevertheless capable of operating at speeds in excess 1 GBPS.
Inventors
- 👤 Carson Chen
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 10:44
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15
Claims Analysis
Total Claims: 14
Claim 1
Independent Claim
173 words
An apparatus for encoding information according to a linear error correcting code having a generator matrix comprising an identity matrix and as associated parity matrix, said apparatus comprising: first means coupled to an input channel for storing an input data word of said linear error correcting code; matrix means for permanently storing a binary representation of the parity matrix for said linear error correcting code for use in computing parity of said input code word; means for controlling digital value output of said matrix means as a function of content of said first storing means; means for exclusive-OR combining content of said first storing means with said digital value output of said matrix means to generate a parity word for said input data word; and second means coupled to said input channel for storing said input data word of said linear error correcting code and said parity word, said second storing means being coupled to an output data channel for supplying said input data word and said parity word to said output channel.
Claim 2
Independent Claim
173 words
An apparatus for encoding information according to a linear error correcting code having a generator matrix comprising an identity matrix and as associated parity matrix, said apparatus comprising: first means coupled to an input channel for storing an input data word of said linear error correcting code; matrix means for permanently storing a binary representation of the parity matrix for said linear error correcting code for use in computing parity of said input code word; means for controlling digital value output of said matrix means as a function of content of said first storing means; means for exclusive-OR combining content of said first storing means with said digital value output of said matrix means to generate a parity word for said input data word; and second means coupled to said input channel for storing said input data word of said linear error correcting code and said parity word, said second storing means being coupled to an output data channel for supplying said input data word and said parity word to said output channel.
Claim 3
Dependent Claim
56 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 matrix means comprises a first Read Only Memory means storing only parity bits of the generator matrix of a code word in order to minimize storage of information.
Claim 4
Dependent Claim
80 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 matrix means comprises an array of dual-input AND gates, each first input of said AND gates being tied to a fixed value storing parity bits corresponding to the parity matrix and each second input being coupled to one parallel output of said first storage means in order to minimize storage of information.
Claim 5
Dependent Claim
84 words
The apparatus according to claim 3 further including: means for converting serial data to parallel data of a code word not divisible by Y, said converting means comprising a first array of Y means for storing parallel data divisible by X, where X is a common factor to said code word, and a second array of X means for storing data divisible by Y, said second array being coupled to receive Y by X data from said first array as X by Y data.
Claim 6
Dependent Claim
42 words
The apparatus according to claim 1, wherein said parity matrix is a means for determining at least one syndrome, said apparatus further comprising means for modulo-2 adding partial parities of said at least one syndrome to obtain said at least one syndrome.
Claim 7
Dependent Claim
53 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 parity matrix which is a syndrome determining means.
Claim 8
Independent Claim
161 words
A method for encoding information according to a linear error correcting code having a generator matrix comprising an identity matrix and an associated parity matrix, said method comprising: storing an input data word of said linear error correcting code in a first storage means, said input data word being received through an input data channel; shifting selected bits of said input data word through a parallel shift register means as a function of parity of the parity matrix for said linear error correcting code to compute parity of said input code word in order to generate a digital value output; exclusive-OR combining content of said first storing means with said digital value output to generate a parity word for said input data word; appending said parity word for said input data word to said input data word of said linear error correcting code; and supplying said input data word and said parity word as a bit stream to an output channel.
Claim 9
Independent Claim
161 words
A method for encoding information according to a linear error correcting code having a generator matrix comprising an identity matrix and an associated parity matrix, said method comprising: storing an input data word of said linear error correcting code in a first storage means, said input data word being received through an input data channel; shifting selected bits of said input data word through a parallel shift register means as a function of parity of the parity matrix for said linear error correcting code to compute parity of said input code word in order to generate a digital value output; exclusive-OR combining content of said first storing means with said digital value output to generate a parity word for said input data word; appending said parity word for said input data word to said input data word of said linear error correcting code; and supplying said input data word and said parity word as a bit stream to an output channel.
Claim 10
Dependent Claim
62 words
The method according to claim 7 wherein the error correcting code is selected from linear cyclic invariant error correcting codes whose generator polynomials can be factored, wherein said shifting step comprises applying said input data word to a first Read Only Memory means storing only parity bits of the generator matrix of a code word in order to minimize storage of information.
Claim 11
Dependent Claim
86 words
The method according to claim 7 wherein the error correcting code is selected from linear cyclic invariant error correcting codes whose generator polynomials can be factored, wherein said shifting step comprises applying said input data word to an array of dual-input AND gates, each first input of said AND gates being tied to a fixed value storing parity bits corresponding to the parity matrix and each second input being coupled to one parallel output of said first storage means in order to minimize storage of information.
Claim 12
Dependent Claim
85 words
The method according to claim 9 further including the steps of: converting serial data to parallel data of a code word not divisible by Y, said converting means comprising a first array of Y means for storing parallel data divisible by X, where X is a common factor to said code word, and a second array of X means for storing data divisible by Y, said second array being coupled to receive Y by X data from said first array as X by Y data.
Claim 13
Dependent Claim
25 words
The method according to claim 7 further comprising the step of: modulo-2 adding partial parities of said at least one syndrome to obtain said syndrome.
Claim 14
Dependent Claim
48 words
The method according to claim 7 further comprising: converting high-speed input data into parallel data to be processed at lower data speeds with a serial-to-parallel converter means, said serial-to-parallel converter means being coupled to provide said parallel data to said parity matrix which is a syndrome determining means.
References Cited (Backward Citations)
US4064483A
Cited
US4030067A
Cited
US4162480A
Cited
US4142174A
Cited
US4312069A
Cited
US4468769A
Cited
US4502141A
Cited
US4556977A
Cited
US4719628A
Cited
US4623999A
Cited
US4694455A
Cited
US4958349A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1994-08-12 | 1995-02-11 | 1995-08-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1998-08-12 | 1999-02-11 | 1999-08-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2002-08-12 | 2003-02-11 | 2003-08-13 | $7700.00 | Window Closed / Lapsed |