US4404674A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for weighted majority decoding of FEC codes using soft detection
Assignee: Comsat Corp
•
Filing: 1981-07-10
•
Granted: 1983-09-13
•
Expires: 2001-07-10
Abstract
Abstract New techniques are disclosed which utilize soft detection to improve the performance of FEC codes. For an FEC code with minimum Hamming distance, the decoder utilizes hard-detected code symbols to obtain d independent estimates of each information bit, including the detected information symbol itself and d-1 orthogonal parity checks on the information bit. Soft detection is employed for the purpose of computing reliability measures for the d estimates. The reliability numbers serve as weighting coefficients, with the bit decision determined on a weighted majority basis. In one preferred technique, Reliability Majority Decoding (RMD), the reliability of each estimate is determined from some number I of the least reliable of the m hard-detected code symbols contributing to the estimate. For I=1, a simplified logic circuit can be used to determine estimate reliability, while for I=m each symbol is assigned a number of demerits inversely proportional to reliability. The demerits are totalled for each estimate and inverse mapping yields an estimate reliability. In a second preferred technique, all detected symbols are assigned equal weights for purposes of computing parity symbols, but each detected code symbol is then itself assigned a reliability which is used to determine how many parity symbol mismatches are required to overrule the bit estimate. Cascaded feedback decoding techniques can be used to further improve decoding performance. Also disclosed is a technique for providing error protection of parity symbols.
Inventors
- 👤 Smith A. Rhodes
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 02:11
CPC Classifications
H; H03; H03M; H03M13/00; H03M13/37; H03M13/3776; H03M13/43; H03M13/45; H03M13/458
Claims Analysis
Total Claims: 33
Claim 1
Independent Claim
275 words
A method of weighted majority decoding of code symbol signals included in a forward error correcting (FEC) code, said code symbol signals including information symbol signals representing information symbols having at least first and second code values and parity symbol signals representing parity symbols generated from selected combinations of said information symbols, said method comprising the steps of: receiving information symbol signals representing the code values of said information symbols, receiving parity symbol signals representing the values of said parity symbols; soft detecting said information symbol signals to detect the voltage of each information symbol signal; generating a code value signal indicating the code value represented by each said information symbol signal; generating an information symbol reliability signal representing the reliability of each said code value signal; detecting said parity symbol signals and generating a parity value signal corresponding to the detected value of each parity symbol; generating a first estimate of the code value of a particular information symbol from the code value signal corresponding to that symbol; assigning to said first estimate a symbol weighting factor in accordance with the information symbol reliability signal corresponding to the detected information symbol signal for said particular information symbol; combining selected ones of said code and parity value signals to obtain at least one further estimate of the code value of said particular information symbol; assigning to said at least one further estimate a fixed symbol weighting factor; combining corresponding estimate weighting factors and code value estimates to obtain weighted estimates; combining said weighted estimates to obtain a combined weighted estimate; and providing a decoded symbol in accordance with the value of said combined weighted estimate.
Claim 2
Independent Claim
275 words
A method of weighted majority decoding of code symbol signals included in a forward error correcting (FEC) code, said code symbol signals including information symbol signals representing information symbols having at least first and second code values and parity symbol signals representing parity symbols generated from selected combinations of said information symbols, said method comprising the steps of: receiving information symbol signals representing the code values of said information symbols, receiving parity symbol signals representing the values of said parity symbols; soft detecting said information symbol signals to detect the voltage of each information symbol signal; generating a code value signal indicating the code value represented by each said information symbol signal; generating an information symbol reliability signal representing the reliability of each said code value signal; detecting said parity symbol signals and generating a parity value signal corresponding to the detected value of each parity symbol; generating a first estimate of the code value of a particular information symbol from the code value signal corresponding to that symbol; assigning to said first estimate a symbol weighting factor in accordance with the information symbol reliability signal corresponding to the detected information symbol signal for said particular information symbol; combining selected ones of said code and parity value signals to obtain at least one further estimate of the code value of said particular information symbol; assigning to said at least one further estimate a fixed symbol weighting factor; combining corresponding estimate weighting factors and code value estimates to obtain weighted estimates; combining said weighted estimates to obtain a combined weighted estimate; and providing a decoded symbol in accordance with the value of said combined weighted estimate.
Claim 3
Dependent Claim
69 words
A method as defined in claim 1, wherein the step of generating an information symbol reliability signal for each code value signal comprises the step of generating a selected one of a plurality of predetermined reliability signals indicating one of a corresponding plurality of reliability classifications, and the fixed symbol weighting factor assigned to said at least one further estimate corresponds to the lowest level of said reliability classifications.
Claim 4
Dependent Claim
31 words
A method as defined in claim 1 or 2, wherein said at least one further estimate comprises a plurality of estimates each of which is assigned a fixed estimate weighting factor.
Claim 5
Independent Claim
338 words
A method of weighted majority decoding of code symbol signals included in a forward error correcting (FEC) code, said code symbol signals including information symbol signals representing information symbols having at least first and second code values and parity symbol signals representing parity symbols generated from selected combinations of said information symbols, said method comprising the steps of: receiving information symbol signals representing the code values of said information symbols; receiving parity symbol signals representing the values of said parity symbols; soft detecting said information symbol signals to detect the voltage of each information symbol signal; generating a code value signal indicating the code value represented by each said information symbol signal; generating an information symbol reliability signal representing the reliability of each said code value signal; soft detecting said parity symbol signals to detect the voltage of each parity symbol signal; generating a parity value signal indicating the value represented by each said parity symbol signal; generating a parity symbol reliability signal representing the reliability of each said parity value signal; generating a first estimate of the code value of a particular information symbol from the code value signal corresponding to that symbol; combining m selected ones of said code and parity value signals to obtain at least one further estimate of the code value of said particular information symbol; assigning to said first estimate an estimate weighting factor in accordance with the information symbol reliability signal corresponding to the self-detected information symbol signal for said particular information symbol; determining for said at least one further estimate an estimate weighting factor derived from the reliability signals of the I least reliable code and parity value signals which were combined to obtain said at least one further estimate, where I is an integer greater than 1 and less than m; combining corresponding estimate weighting factors and code value estimates to obtain weighted estimates; combining said weighted estimates to obtain a combined weighted estimate; and providing a decoded symbol in accordance with the value of said combined weighted estimate.
Claim 6
Independent Claim
338 words
A method of weighted majority decoding of code symbol signals included in a forward error correcting (FEC) code, said code symbol signals including information symbol signals representing information symbols having at least first and second code values and parity symbol signals representing parity symbols generated from selected combinations of said information symbols, said method comprising the steps of: receiving information symbol signals representing the code values of said information symbols; receiving parity symbol signals representing the values of said parity symbols; soft detecting said information symbol signals to detect the voltage of each information symbol signal; generating a code value signal indicating the code value represented by each said information symbol signal; generating an information symbol reliability signal representing the reliability of each said code value signal; soft detecting said parity symbol signals to detect the voltage of each parity symbol signal; generating a parity value signal indicating the value represented by each said parity symbol signal; generating a parity symbol reliability signal representing the reliability of each said parity value signal; generating a first estimate of the code value of a particular information symbol from the code value signal corresponding to that symbol; combining m selected ones of said code and parity value signals to obtain at least one further estimate of the code value of said particular information symbol; assigning to said first estimate an estimate weighting factor in accordance with the information symbol reliability signal corresponding to the self-detected information symbol signal for said particular information symbol; determining for said at least one further estimate an estimate weighting factor derived from the reliability signals of the I least reliable code and parity value signals which were combined to obtain said at least one further estimate, where I is an integer greater than 1 and less than m; combining corresponding estimate weighting factors and code value estimates to obtain weighted estimates; combining said weighted estimates to obtain a combined weighted estimate; and providing a decoded symbol in accordance with the value of said combined weighted estimate.
Claim 7
Dependent Claim
19 words
A method as defined in claim 4, wherein said at least one further estimate comprises a plurality of estimates.
Claim 8
Dependent Claim
69 words
A method as defined in claim 4, wherein said step of generating a parity symbol reliability signal comprises the step of generating one of a plurality of predetermined reliability signals corresponding to one of a corresponding plurality of predetermined reliability classifications, and wherein said step of generating an information symbol reliability signal comprises the step of generating a fixed reliability signal corresponding to the highest of said reliability classifications.
Claim 9
Independent Claim
300 words
A method of weighted majority decoding of code symbol signals included in a forward error correcting (FEC) code, said code symbol signals including information symbol signals representing information symbols having at least first and second code values and parity symbol signals representing parity symbols generated from selected combinations of said information symbols, said method comprising the steps of: receiving information symbol signals representing the code values of said information symbols; receiving parity symbol signals representing the values of said parity symbols; soft detecting said information symbol signals to detect the voltage of each information symbol signal; generating a code value signal indicating the code value represented by each said information symbol signal; assigning to each code value signal a number of demerits corresponding to the reliability of the code value represented by each said code value signal; soft detecting said parity symbol signals to detect the voltage of each said parity symbol signal; generating a parity value signal corresponding to the value of each parity symbol signal; assigning to each parity symbol signal a number of demerits corresponding to the reliability of the parity value represented by said parity symbol signal; combining selected ones of said code and parity value signals to obtain a plurality of estimates of the code value of a particular information symbol; combining the demerits assigned to each of the code and parity value signals used to obtain each estimate in order to obtain a combined demerit value for each said estimate; assigning to each said estimate an estimate weighting factor in accordance with said combined demerit value; combining corresponding estimate weighting factors and code value estimates to obtain weighted estimates; combining said weighted estimates to obtain a combined weighted estimate; and providing a decoded symbol in accordance with the value of said combined weighted estimate.
Claim 10
Independent Claim
300 words
A method of weighted majority decoding of code symbol signals included in a forward error correcting (FEC) code, said code symbol signals including information symbol signals representing information symbols having at least first and second code values and parity symbol signals representing parity symbols generated from selected combinations of said information symbols, said method comprising the steps of: receiving information symbol signals representing the code values of said information symbols; receiving parity symbol signals representing the values of said parity symbols; soft detecting said information symbol signals to detect the voltage of each information symbol signal; generating a code value signal indicating the code value represented by each said information symbol signal; assigning to each code value signal a number of demerits corresponding to the reliability of the code value represented by each said code value signal; soft detecting said parity symbol signals to detect the voltage of each said parity symbol signal; generating a parity value signal corresponding to the value of each parity symbol signal; assigning to each parity symbol signal a number of demerits corresponding to the reliability of the parity value represented by said parity symbol signal; combining selected ones of said code and parity value signals to obtain a plurality of estimates of the code value of a particular information symbol; combining the demerits assigned to each of the code and parity value signals used to obtain each estimate in order to obtain a combined demerit value for each said estimate; assigning to each said estimate an estimate weighting factor in accordance with said combined demerit value; combining corresponding estimate weighting factors and code value estimates to obtain weighted estimates; combining said weighted estimates to obtain a combined weighted estimate; and providing a decoded symbol in accordance with the value of said combined weighted estimate.
Claim 11
Dependent Claim
28 words
A method as defined in claim 7, wherein the number of demerits assigned to each symbol value varies inversely with the reliability of the value of that symbol.
Claim 12
Dependent Claim
26 words
A method as defined in claim 8, wherein said plurality of terms in said determining step comprises all of the terms involved in each said estimate.
Claim 13
Dependent Claim
35 words
A method as defined in claim 9, wherein the maximum value of said combined demerit value is equal to the maximum value of demerits which can be assigned to a symbol signal of lowest reliability.
Claim 14
Independent Claim
253 words
A method of weighted majority decoding of a forward error correcting (FEC) code, said code comprising code symbol signals including information symbol signals representing information symbols having at least first and second code values and parity symbol signals representing parity symbols generated from selected combinations of said information symbols, said method comprising the steps of: soft-detecting said information and parity symbol signals and generating for each of said soft-detected signals a multi-bit signal having one bit representing the value of the detected symbol signal and a plurality of remaining bits representing the reliability of said symbol value; combining said one bits of selected ones of said multibit signals to obtain a plurality of estimates of the code value of a particular information symbol; determining an estimate weighting factor for each said estimate in accordance with the least reliable code value used in obtaining said estimate, said determining step comprising the steps of combining corresponding ones of said remaining bits for each symbol in respective AND gates, the combined outputs of said AND gates being the equivalent of the remaining bits of the least reliable term involved in said estimate, and assigning to each said estimate a weighting factor corresponding to the combined outputs of said AND gates; combining the estimate weighting factors and corresponding code value estimates to obtain a plurality of weighted estimates of said particular symbol; combining said weighted estimates to obtain a combined weighted estimate; and providing a decoded symbol in accordance with the value of said combined weighted estimate.
Claim 15
Independent Claim
253 words
A method of weighted majority decoding of a forward error correcting (FEC) code, said code comprising code symbol signals including information symbol signals representing information symbols having at least first and second code values and parity symbol signals representing parity symbols generated from selected combinations of said information symbols, said method comprising the steps of: soft-detecting said information and parity symbol signals and generating for each of said soft-detected signals a multi-bit signal having one bit representing the value of the detected symbol signal and a plurality of remaining bits representing the reliability of said symbol value; combining said one bits of selected ones of said multibit signals to obtain a plurality of estimates of the code value of a particular information symbol; determining an estimate weighting factor for each said estimate in accordance with the least reliable code value used in obtaining said estimate, said determining step comprising the steps of combining corresponding ones of said remaining bits for each symbol in respective AND gates, the combined outputs of said AND gates being the equivalent of the remaining bits of the least reliable term involved in said estimate, and assigning to each said estimate a weighting factor corresponding to the combined outputs of said AND gates; combining the estimate weighting factors and corresponding code value estimates to obtain a plurality of weighted estimates of said particular symbol; combining said weighted estimates to obtain a combined weighted estimate; and providing a decoded symbol in accordance with the value of said combined weighted estimate.
Claim 16
Dependent Claim
125 words
A method as defined in claim 11, wherein said code is a binary code having only first and second code values and wherein said step of combining selected ones of said information and parity symbols comprises the step of logically summing in a mod-2 adder the said one bit in each of said multi-bit signals representing the code value of said symbol and assigning a polarity of either +1 or -1 in accordance with the output of said mod-2 adder, said step of combining the estimate weighting factors and corresponding code value estimates comprising the multiplication of said assigned polarity value by said assigned estimate weighting and said providing step comprising the step of threshold detecting said combined weighted estimate with a zero threshold level.
Claim 17
Independent Claim
43 words
A method as defined in claims 1, 4 or 7, wherein said step of providing a decoded symbol comprises the step of threshold detecting said combined weighted estimate with a threshold substantially equal to the midpoint between said first and second code values.
Claim 18
Independent Claim
184 words
A method of generating a forward error correcting (FEC) majority logic decodable code from a series of information bits, said code comprising a series of output code symbol signal sets, said code being a rate ρ=k/n code wherein each output code symbol set includes k information symbols and (n-k) parity symbols where n and k are positive integers and n>k, said method comprising the steps of: providing said k information symbols to k respective information symbol shift registers; coupling selected stages of each of said k information symbol shift registers as a first set of inputs to each of (n-k) modulo-2 adders, each of which modulo-2 adders combine its respective first set of inputs with a second set of inputs and provides a parity symbol output; and providing the parity symbol output from each adder as an input to a corresponding one of (n-k) parity symbol shift registers, selected stages of said parity symbol shift registers being provided as said second set of inputs to corresponding modulo-2 adders, the inputs to said information and parity symbol shift registers constituting an output code symbol set.
Claim 19
Independent Claim
184 words
A method of generating a forward error correcting (FEC) majority logic decodable code from a series of information bits, said code comprising a series of output code symbol signal sets, said code being a rate ρ=k/n code wherein each output code symbol set includes k information symbols and (n-k) parity symbols where n and k are positive integers and n>k, said method comprising the steps of: providing said k information symbols to k respective information symbol shift registers; coupling selected stages of each of said k information symbol shift registers as a first set of inputs to each of (n-k) modulo-2 adders, each of which modulo-2 adders combine its respective first set of inputs with a second set of inputs and provides a parity symbol output; and providing the parity symbol output from each adder as an input to a corresponding one of (n-k) parity symbol shift registers, selected stages of said parity symbol shift registers being provided as said second set of inputs to corresponding modulo-2 adders, the inputs to said information and parity symbol shift registers constituting an output code symbol set.
Claim 20
Dependent Claim
260 words
A method of decoding a majority logic decodable code encoded according to the method of claim 14, said code being a rate ρ=k/n code including output code symbol sets each including k information symbols and (n-k) parity symbols, where n and k are positive integers and n>k, said decoding method comprising the steps of: receiving said k information symbols and (n-k) parity symbol signals in a first decoder; regenerating parity symbol estimates from said received signals in an encoder replica; comparing said received and regenerated parity symbols to generate (n-k) parity check syndromes each corresponding to successive comparisons between one of said n-k received parity symbols on a corresponding one of said n-k regenerated parity symbols; passing or correcting each of said k information symbols in accordance with a majority polling of said n-k parity check syndromes in order to provide k decoded information bits; passing or correcting each of said (n-k) received parity symbol signals in accordance with a majority polling of said parity check syndromes; correcting selected bits of said parity check syndromes in accordance with said majority pollings in order to obtain (n-k) updated syndromes; receiving said k decoded information symbols at a second decoder; obtaining said n-k updated syndromes at said second decoder; logically combining said k decoded information symbols with selected stages of said (n-k) updated parity syndromes to produce estimates of said information symbols; and producing k double decoded information symbols in accordance with weighted majority decisions on said detected information symbols and said plurality of estimates of each of said k information symbols.
Claim 21
Dependent Claim
23 words
A method as defined in claim 15, wherein said detected information symbol is assigned a weight in accordance with its soft-detected voltage level.
Claim 22
Dependent Claim
27 words
A method as defined in claim 15, wherein said reliability weight assigned to said detected information symbol is forwarded to said second decoder from said first decoder.
Claim 23
Dependent Claim
37 words
A method as defined in claim 15, wherein said plurality of estimates of said information symbol are assigned a fixed weight which is less than the maximum weight which may be assigned to said detected information symbol.
Claim 24
Independent Claim
15 words
A method according to either one of claims 14 or 15, wherein k=1 and n=2.
Claim 25
Dependent Claim
186 words
In a method of decoding a majority logic decodable code, said method being of the type including receiving at a first decoder information and parity symbol signals representing information and parity symbols in said code, regenerating parity symbol estimates from said received information symbol signals, comparing said received parity symbols and regenerated parity symbol estimates to generate a parity check syndrome, and passing or correcting said received information symbol in accordance with a majority logic decision on said parity check syndrome, the improvement comprising: receiving said detected information symbols at a second decoder; generating a second set of parity symbol estimates from said decoded information symbols in a second encoder replica; comparing said second set of parity symbol estimates to said received parity symbols in order to generate a second parity check syndrome; combining said decoded information symbols with selected stages of said second parity check syndrome in order to generate a plurality of estimates of each said information symbol; and passing or correcting said detected information symbol in accordance with a majority logic decision on said plurality of estimates and on said detected information symbol.
Claim 26
Dependent Claim
186 words
In a method of decoding a majority logic decodable code, said method being of the type including receiving at a first decoder information and parity symbol signals representing information and parity symbols in said code, regenerating parity symbol estimates from said received information symbol signals, comparing said received parity symbols and regenerated parity symbol estimates to generate a parity check syndrome, and passing or correcting said received information symbol in accordance with a majority logic decision on said parity check syndrome, the improvement comprising: receiving said detected information symbols at a second decoder; generating a second set of parity symbol estimates from said decoded information symbols in a second encoder replica; comparing said second set of parity symbol estimates to said received parity symbols in order to generate a second parity check syndrome; combining said decoded information symbols with selected stages of said second parity check syndrome in order to generate a plurality of estimates of each said information symbol; and passing or correcting said detected information symbol in accordance with a majority logic decision on said plurality of estimates and on said detected information symbol.
Claim 27
Dependent Claim
30 words
A method as defined in claim 20, wherein said detected information symbol is soft detected and is weighted in said majority logic decision in accordance with its soft-detected voltage level.
Claim 28
Dependent Claim
39 words
A method as defined in claim 20, wherein said received parity symbols are soft detected and said plurality of estimates of each said information symbol are weighted in accordance with the soft-detected voltage levels of said received parity symbols.
Claim 29
Dependent Claim
178 words
In a method of decoding majority logic decodable codes, said method being of the type including the steps of receiving and detecting at a first decoder information and parity symbol signals, regenerating parity symbol estimates from said received information symbol signals in an encoder replica, comparing said received parity symbol signals and regenerated parity symbol estimates to generate a parity check syndrome, correcting or passing said detected information symbol as a decoded value output in accordance with a majority polling of said parity check syndrome, and updating the contents of said parity check syndrome in accordance with said majority decision, the improvement comprising: receiving said detected information symbols at a second decoder; receiving said decoded information symbols at said second decoder; receiving said updated parity check syndrome at said second decoder; combining said decoded information symbols and said updated parity check syndrome in order to obtain a plurality of estimates of said information symbol; and passing or correcting said detected information symbol in accordance with a majority logic decision on said information symbol and said plurality of estimates.
Claim 30
Dependent Claim
178 words
In a method of decoding majority logic decodable codes, said method being of the type including the steps of receiving and detecting at a first decoder information and parity symbol signals, regenerating parity symbol estimates from said received information symbol signals in an encoder replica, comparing said received parity symbol signals and regenerated parity symbol estimates to generate a parity check syndrome, correcting or passing said detected information symbol as a decoded value output in accordance with a majority polling of said parity check syndrome, and updating the contents of said parity check syndrome in accordance with said majority decision, the improvement comprising: receiving said detected information symbols at a second decoder; receiving said decoded information symbols at said second decoder; receiving said updated parity check syndrome at said second decoder; combining said decoded information symbols and said updated parity check syndrome in order to obtain a plurality of estimates of said information symbol; and passing or correcting said detected information symbol in accordance with a majority logic decision on said information symbol and said plurality of estimates.
Claim 31
Dependent Claim
28 words
A method as defined in claim 23, wherein said information symbol is soft detected and is assigned a reliability weight in accordance with its soft detected voltage level.
Claim 32
Dependent Claim
39 words
A method as defined in claim 24, wherein said information symbol signal is soft detected at said first decoder and the reliability weight assigned to said detected information symbol is forwarded to said second decoder from said first decoder.
Claim 33
Dependent Claim
34 words
A method as defined in claim 24, wherein each of said plurality of estimates is assigned a fixed reliability weight which is less than the maximum permissible reliability weight for said soft-detected information symbol.
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) | 1986-09-12 | 1987-03-14 | 1987-09-13 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1990-09-12 | 1991-03-14 | 1991-09-13 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 1994-09-12 | 1995-03-14 | 1995-09-13 | $7700.00 | Window Closed / Lapsed |