Patent US5160282A successfully refreshed from Google Patents.
Patent US5926488A successfully refreshed from Google Patents.
US5926488A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for decoding second order reed-muller codes
Assignee: Ericsson Inc
•
Filing: 1997-08-14
•
Granted: 1999-07-20
•
Expires: 2017-08-14
Abstract
Abstract The Conway-Sloane decoding method presents a general premise that for any given highly complex block code, an attempt should be made to find a subcode of that given block code that is less complex to decode. The given complex block code may then be maximum likelihood decoded with reduced complexity by cycling over the subcode and its cosets. Extending this general premise to Reed-Muller codes, and in particular to a second order Reed-Muller (or Kerdock) code, reduced maximum likelihood decoding complexity is obtained by cycling over a found subcode (and its cosets) of the second order Reed-Muller (or Kerdock) code. A first order Reed-Muller code comprises just such a suitable subcode which, like the parity check for the Golay codes analyzed by Conway and Sloane, has a known less complex maximum likelihood decoding solution utilizing a fast Hadamard Transform.
Inventors
- 👤 Ali S. Khayrallah
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-01 17:36
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
89 words
A method for maximum likelihood decoding of a received vector comprising second order Reed-Muller code encoded information bits, comprising the steps of: cycling over cosets of a subcode of a second order Reed-Muller code used to encode the information bits; performing a Hadamard Transformation on the received vector compared to each coset to obtain an intermediate codeword guess for each cycle; and recovering, following cycling through each of the cosets, the originally encoded information bits from a final codeword guess comprising a best one of the intermediate codeword guesses.
Claim 2
Independent Claim
89 words
A method for maximum likelihood decoding of a received vector comprising second order Reed-Muller code encoded information bits, comprising the steps of: cycling over cosets of a subcode of a second order Reed-Muller code used to encode the information bits; performing a Hadamard Transformation on the received vector compared to each coset to obtain an intermediate codeword guess for each cycle; and recovering, following cycling through each of the cosets, the originally encoded information bits from a final codeword guess comprising a best one of the intermediate codeword guesses.
Claim 3
Dependent Claim
15 words
The method as in claim 1 wherein the Hadamard Transformation comprises a Fast Hadamard Transformation.
Claim 4
Dependent Claim
27 words
The method as in claim 1 further including the step of precomputing and saving a plurality of intermediate values for the Hadamard Transformation of the received vector.
Claim 5
Dependent Claim
60 words
The method as in claim 3 wherein the step of performing a Hadamard Transformation on the received vector further comprises the steps of: recalling necessary ones of the precomputed intermediate values at each cycle; and completing the Hadamard Transformation of the received vector using the recalled precomputed intermediate values to obtain the intermediate codeword guess with respect to each coset.
Claim 6
Dependent Claim
16 words
The method as in claim 1 wherein the second order Reed-Muller code comprises a Kerdock code.
Claim 7
Dependent Claim
22 words
The method as in claim 1 wherein the second order Reed-Muller code comprises a shortened form of the second order Reed-Muller code.
Claim 8
Dependent Claim
15 words
The method as in claim 1 wherein the subcode is a first order Reed-Muller code.
Claim 9
Independent Claim
90 words
A method for maximum likelihood decoding of a received vector comprising encoded information bits, comprising the steps of: cycling over cosets of a subcode of a code used to encode the information bits, the subcode comprising a first order Reed-Muller code; performing a Hadamard Transformation on the received vector compared to each coset to obtain an intermediate codeword guess for each cycle; and recovering, following cycling through each of the cosets, the originally encoded information bits from a final codeword guess comprising a best one of the intermediate codeword guesses.
Claim 10
Independent Claim
90 words
A method for maximum likelihood decoding of a received vector comprising encoded information bits, comprising the steps of: cycling over cosets of a subcode of a code used to encode the information bits, the subcode comprising a first order Reed-Muller code; performing a Hadamard Transformation on the received vector compared to each coset to obtain an intermediate codeword guess for each cycle; and recovering, following cycling through each of the cosets, the originally encoded information bits from a final codeword guess comprising a best one of the intermediate codeword guesses.
Claim 11
Dependent Claim
15 words
The method as in claim 8 wherein the Hadamard Transformation comprises a Fast Hadamard Transformation.
Claim 12
Dependent Claim
27 words
The method as in claim 8 further including the step of precomputing and saving a plurality of intermediate values for the Hadamard Transformation of the received vector.
Claim 13
Dependent Claim
60 words
The method as in claim 10 wherein the step of performing a Hadamard Transformation on the received vector further comprises the steps of: recalling necessary ones of the precomputed intermediate values at each cycle; and completing the Hadamard Transformation of the received vector using the recalled precomputed intermediate values to obtain the intermediate codeword guess with respect to each coset.
Claim 14
Dependent Claim
15 words
The method as in claim 8 wherein the code comprises a second order Reed-Muller code.
Claim 15
Dependent Claim
13 words
The method as in claim 8 wherein the code comprises a Kerdock code.
Claim 16
Dependent Claim
19 words
The method as in claim 8 wherein the code comprises a shortened form of a second order Reed-Muller code.
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) | 2002-07-19 | 2003-01-18 | 2003-07-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-19 | 2007-01-18 | 2007-07-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-19 | 2011-01-18 | 2011-07-20 | $7700.00 | Window Closed / Lapsed |