US3818442A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Error-correcting decoder for group codes
Assignee: Northrop Grumman Space and Mission Systems Corp
•
Filing: 1972-11-08
•
Granted: 1974-06-18
•
Expires: 1992-11-08
Abstract
Abstract A multiple error-correcting decoder for group codes. The decoder does not attempt to determine error positions in the transmitted group code word, instead the transmitted code word or vector is operated on by a multiplier or mask so as to blank out or obliterate possible error positions. Subsequently, the code word is reconstituted by a recursion relation. Finally the Hamming distance between all the newly generated code vectors and the received code word is calculated, and the new vector with the least Hamming distance is selected as the most likely original code word. The decoder can be realized either by a simultaneous decoder or by a cyclic decoder. It can be shown that such a multiplier exists for group codes over an algebraic finite field and a procedure is disclosed for realizing such a multiplier. The recursion relation may be built into the multiplier so that in a single step the received vector can be multiplied and reconstituted. The new decoder has the advantage of great flexibility. It requires a minimum of hardware and decoding can be effected at the rate of 300 megabits per second.
Inventors
- 👤 G Solomon
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-04 15:12
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; G; G06; G06F; G06F11/00; G06F11/07; G06F11/08; G06F11/10; G06F7/00; G06F7/60; G06F7/72; G06F7/724; H04; H04L; H04L1/00; H04L1/004; H04L1/0056; H04L1/0057
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
117 words
The method of decoding and correcting errors in a received code word subject to errors of a group code over a finite, algebraic field, said method comprising the steps of: a. multiplying the received code word represented by electrical signals with each one of a predetermined set of multiplier vectors represented by electrical signals, thereby to obliterate certain positions of the received code word and to generate a set of code vectors; b. reconstituting the obliterated positions of each code vector by a predetermined linear recursion relation; and c. determining which of the newly reconstituted code vectors has the closest Hamming distance to the received code word, whereby the closest reconstituted vector is the decoded code word.
Claim 2
Independent Claim
117 words
The method of decoding and correcting errors in a received code word subject to errors of a group code over a finite, algebraic field, said method comprising the steps of: a. multiplying the received code word represented by electrical signals with each one of a predetermined set of multiplier vectors represented by electrical signals, thereby to obliterate certain positions of the received code word and to generate a set of code vectors; b. reconstituting the obliterated positions of each code vector by a predetermined linear recursion relation; and c. determining which of the newly reconstituted code vectors has the closest Hamming distance to the received code word, whereby the closest reconstituted vector is the decoded code word.
Claim 3
Dependent Claim
25 words
The method defined in claim 1 wherein the code is a cyclic code and the set of multiplier vectors is a cyclic set of vectors.
Claim 4
Dependent Claim
22 words
The method defined in claim 2 wherein the received code word is multiplied simultaneously with the entire set of the multiplier vectors.
Claim 5
Dependent Claim
20 words
The method defined in claim 2 wherein the received code word is multiplied sequentially with the set of multiplier vectors.
Claim 6
Dependent Claim
25 words
The method defined in claim 1 wherein the received code word is multiplied with a vector of the set of multipliers and is simultaneously reconstituted.
Claim 7
Independent Claim
129 words
The method of decoding and correcting errors in a received code word subject to errors and of a cyclic group code over a finite, algebraic field, said method comprising the steps of: a. masking predetermined positions of the received code word represented by electrical signals by means of each one of a predetermined set of multiplier vectors represented by electrical signals to obliterate Predetermined positions of the received code word and to generate a set of code vectors; b. reconstituting the obliterated positions of each code vector by an independent set of coordinates determined by a linear recursion relation; and c. determining which of the newly reconstructed code vectors has the closest Hamming distance to the received code word, whereby the closest reconstituted vector is the decocded code word.
Claim 8
Independent Claim
129 words
The method of decoding and correcting errors in a received code word subject to errors and of a cyclic group code over a finite, algebraic field, said method comprising the steps of: a. masking predetermined positions of the received code word represented by electrical signals by means of each one of a predetermined set of multiplier vectors represented by electrical signals to obliterate Predetermined positions of the received code word and to generate a set of code vectors; b. reconstituting the obliterated positions of each code vector by an independent set of coordinates determined by a linear recursion relation; and c. determining which of the newly reconstructed code vectors has the closest Hamming distance to the received code word, whereby the closest reconstituted vector is the decocded code word.
Claim 9
Independent Claim
143 words
The method of decoding and correcting errors in a received code word forming a vector of a cyclic group code over a finite algebraic field, said method comprising the steps of: a. cyclically shifting the received code word represented by electrical signals subject to errors to generate a set of code word vectors; b. multiplying each of the code word vectors cyclically with at least one multiplier represented by electrical signals, said multiplier belonging to a cyclic set, thereby to obliterate certain positions of the received code word and to generate a set of multiplied code vectors; c. reconstituting the obliterated positions of each multiplied code vector by a predetermined linear recursion relation; and d. determining which of the newly reconstituted code vectors has the closest Hamming distance to the received code word, whereby the closest reconstituted vector is the decoded code word.
Claim 10
Independent Claim
143 words
The method of decoding and correcting errors in a received code word forming a vector of a cyclic group code over a finite algebraic field, said method comprising the steps of: a. cyclically shifting the received code word represented by electrical signals subject to errors to generate a set of code word vectors; b. multiplying each of the code word vectors cyclically with at least one multiplier represented by electrical signals, said multiplier belonging to a cyclic set, thereby to obliterate certain positions of the received code word and to generate a set of multiplied code vectors; c. reconstituting the obliterated positions of each multiplied code vector by a predetermined linear recursion relation; and d. determining which of the newly reconstituted code vectors has the closest Hamming distance to the received code word, whereby the closest reconstituted vector is the decoded code word.
Claim 11
Dependent Claim
18 words
The method defined in claim 7 wherein each of the code word vectors is simultaneously multiplied and reconstituted.
Claim 12
Dependent Claim
139 words
Apparatus for decoding and for correcting the errors of a received code word, said code word existing in a group code over an algebraic finite field, said apparatus comprising: a. a register for holding the received code word; b. a multiplier matrix coupled to said register for multiplying the code word with a set of multiplier vectors to generate a set of multiplied code vectors, thereby to obliterate predetermined positions of the received code word; c. a recursion matrix coupled to said multiplier matrix for reconstituting the obliterated positions of each of the multiplied code vectors; d. a minimum distance comparator coupled to said recursion matrix for determining that multiplied and reconstituted code vector having the minimum Hamming distance with respect to the received code word; and e. means coupled to said comparator for developing the decoded code word.
Claim 13
Dependent Claim
139 words
Apparatus for decoding and for correcting the errors of a received code word, said code word existing in a group code over an algebraic finite field, said apparatus comprising: a. a register for holding the received code word; b. a multiplier matrix coupled to said register for multiplying the code word with a set of multiplier vectors to generate a set of multiplied code vectors, thereby to obliterate predetermined positions of the received code word; c. a recursion matrix coupled to said multiplier matrix for reconstituting the obliterated positions of each of the multiplied code vectors; d. a minimum distance comparator coupled to said recursion matrix for determining that multiplied and reconstituted code vector having the minimum Hamming distance with respect to the received code word; and e. means coupled to said comparator for developing the decoded code word.
Claim 14
Dependent Claim
151 words
Apparatus for decoding and for correcting the errors of a received code word, said code word existing in a group code which is a cyclic code over an algebraic finite field, said apparatus comprising: a. a cycling register for holding and for cyclically shifting the received code word; b. a multiplier coupled to said cycling register for multiplying each of the cyclically shifted code vectors with at least one multiplier vector to generate a set of multiplied code vectors, thereby to obliterate predetermined positions of the received code word; c. recursion means coupled to said multiplier for reconstituting the obliterated positions of each of the multiplied code vectors; d. minimum distance comparator means coupled to said recursion means for determining that multiplied and reconstituted code vector having the minimum Hamming distance with respect to the received code word; and e. means coupled to said comparator for developing the decoded code word.
Claim 15
Dependent Claim
151 words
Apparatus for decoding and for correcting the errors of a received code word, said code word existing in a group code which is a cyclic code over an algebraic finite field, said apparatus comprising: a. a cycling register for holding and for cyclically shifting the received code word; b. a multiplier coupled to said cycling register for multiplying each of the cyclically shifted code vectors with at least one multiplier vector to generate a set of multiplied code vectors, thereby to obliterate predetermined positions of the received code word; c. recursion means coupled to said multiplier for reconstituting the obliterated positions of each of the multiplied code vectors; d. minimum distance comparator means coupled to said recursion means for determining that multiplied and reconstituted code vector having the minimum Hamming distance with respect to the received code word; and e. means coupled to said comparator for developing the decoded code word.
Claim 16
Dependent Claim
21 words
Apparatus as defined in claim 10 wherein each of the cyclically shifted code vectors is multiplied in sequence by said multiplier.
Claim 17
Dependent Claim
170 words
Apparatus for decoding and for correcting the errors of a received code word, said code word existing in a cyclic group code over an algebraic finite field, said apparatus comprising: a. a register for holding the received code word; b. a plurality of multipliers, each coupled to said register, each multiplier multiplying the received code word with a particular one of a set of multiplier vectors to generate a set of multiplied code vectors, thereby to obliterate predEtermined positions of the received code word, each multiplier being so arranged in accordance with a predetermined recursion relation to reconstitute the obliterated positions of each of the multiplied code vectors, thereby to generate a set of reconstituted code vectors; c. minimum distance comparator means coupled to each of said multipliers for determining the one reconstituted code vector from the set of reconstituted code vectors having the minimum Hamming distance with respect to the received code word; and d. output means coupled to said distance comparator means for generating the decoded code word.
Claim 18
Dependent Claim
170 words
Apparatus for decoding and for correcting the errors of a received code word, said code word existing in a cyclic group code over an algebraic finite field, said apparatus comprising: a. a register for holding the received code word; b. a plurality of multipliers, each coupled to said register, each multiplier multiplying the received code word with a particular one of a set of multiplier vectors to generate a set of multiplied code vectors, thereby to obliterate predEtermined positions of the received code word, each multiplier being so arranged in accordance with a predetermined recursion relation to reconstitute the obliterated positions of each of the multiplied code vectors, thereby to generate a set of reconstituted code vectors; c. minimum distance comparator means coupled to each of said multipliers for determining the one reconstituted code vector from the set of reconstituted code vectors having the minimum Hamming distance with respect to the received code word; and d. output means coupled to said distance comparator means for generating the decoded code word.
Claim 19
Dependent Claim
149 words
Apparatus for decoding and for correcting the errors of a received code word, said code word existing in a cyclic group code over an algebraic finite field, said apparatus comprising: a. a cycling register for holding the received code word and cyclically shifting it to generate a plurality of code vectors; b. two multipliers coupled to said cyclic register, one for multiplying each code vector with a multiplier and the other one for multiplying the same code vector with the complementary multiplier, each multiplier being arranged to reconstitute the obliterated positions of each multiplied code vector in accordance with a predetermined recursion relation; c. minimum distance calculator and comparator means coupled to said multipliers for successively determining the reconstituted code vector having the minimum Hamming distance with respect to the received code word; and d. means coupled to said calculator and comparator means for generating the decoded code word.
Claim 20
Dependent Claim
149 words
Apparatus for decoding and for correcting the errors of a received code word, said code word existing in a cyclic group code over an algebraic finite field, said apparatus comprising: a. a cycling register for holding the received code word and cyclically shifting it to generate a plurality of code vectors; b. two multipliers coupled to said cyclic register, one for multiplying each code vector with a multiplier and the other one for multiplying the same code vector with the complementary multiplier, each multiplier being arranged to reconstitute the obliterated positions of each multiplied code vector in accordance with a predetermined recursion relation; c. minimum distance calculator and comparator means coupled to said multipliers for successively determining the reconstituted code vector having the minimum Hamming distance with respect to the received code word; and d. means coupled to said calculator and comparator means for generating the decoded code word.
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) | 1977-06-17 | 1977-12-17 | 1978-06-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1981-06-17 | 1981-12-17 | 1982-06-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1985-06-17 | 1985-12-17 | 1986-06-18 | $7700.00 | Window Closed / Lapsed |