Patent US3225987A successfully refreshed from Google Patents.
Patent US2067153A successfully refreshed from Google Patents.
Patent US5577053A successfully refreshed from Google Patents.
US5577053A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for decoder optimization
Assignee: Unwired Planet LLC
•
Filing: 1994-09-14
•
Granted: 1996-11-19
•
Expires: 2014-09-14
Abstract
Abstract In a communications system, a message to be transmitted is used to generate an error detection checkword. Both the message and checkword are encoded into a communication traffic signal using an error correction code. An error correction decoder decodes a received traffic signal, generating a plurality of candidate decoded signals and quantitative measurements of the reliability of the candidates. An error detection calculator tests the most reliable candidate for compliance between its decoded message and checkword. If there is compliance, that candidate and its decoded message are selected. If there is no compliance, the next most reliable candidate is tested for compliance, the selection process continuing until compliance is found. If no compliance is found among all the candidates, an error corrector scrutinizes the most reliable candidate for the presence of a correctable error, and the corrected candidate is re-tested for compliance. If there is still no compliance, the next most reliable candidate is scrutinized for the presence of a correctable error, and the corrected candidate is retested for compliance, the process continuing until compliance is found, up to the limits of the error correction capability of the error corrector.
Inventors
- 👤 Paul W. Dent
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-26 08:27
CPC Classifications
H; H04; H04L; H04L1/00; H04L1/004; H04L1/0056; H04L1/0057; H03; H03M; H03M13/00; H03M13/03; H03M13/23
Claims Analysis
Total Claims: 29
Claim 1
Independent Claim
118 words
A communications system providing for reduction of errors in transmission of communication traffic signals, comprising: an error detection signal generator for generating an error detection checkword corresponding to a data message to be transmitted, an error correction encoder for encoding said data message and said error detection checkword, an error correction decoder for decoding an encoded data message and an encoded error detection checkword, said decoder including: means for comparing encoded data message postulates with said encoded data message and for comparing encoded error detection checkword postulates with said encoded error detection checkword, and means for generating confidence factors based on said comparisons, and selection means for selecting a candidate decoded data message based on said confidence factors.
Claim 2
Dependent Claim
118 words
A communications system providing for reduction of errors in transmission of communication traffic signals, comprising: an error detection signal generator for generating an error detection checkword corresponding to a data message to be transmitted, an error correction encoder for encoding said data message and said error detection checkword, an error correction decoder for decoding an encoded data message and an encoded error detection checkword, said decoder including: means for comparing encoded data message postulates with said encoded data message and for comparing encoded error detection checkword postulates with said encoded error detection checkword, and means for generating confidence factors based on said comparisons, and selection means for selecting a candidate decoded data message based on said confidence factors.
Claim 3
Dependent Claim
20 words
The system according to claim 1, wherein said data message and said error detection checkword are encoded using convolutional codes.
Claim 4
Dependent Claim
30 words
The system according to claim 1, wherein said decoder uses a sequential maximum likelihood sequence estimation technique to optimally decode said encoded data message and said encoded error detection checkword.
Claim 5
Dependent Claim
39 words
The system according to claim 1, wherein said decoder includes memory for storing postulate bit states, a history of selected bits for each of said postulate bit states, and a confidence factor for each of said postulate bit states.
Claim 6
Dependent Claim
57 words
The system according to claim 1, further comprising: a transmitter having a convolutional encoder including: an L-bit shift register for storing L bits of data message information and error detection checkword information; a logic circuit for logically combining particular ones of said L bits in order to generate parity bits; and means for transmitting said parity bits.
Claim 7
Dependent Claim
20 words
The system according to claim 1, wherein said encoded data message and said encoded error detection checkword are parity bits.
Claim 8
Dependent Claim
22 words
The system according to claim 1, wherein said error correction encoder is initialized and terminated by encoding bits unknown to said decoder.
Claim 9
Dependent Claim
22 words
The system according to claim 1, wherein said error correction encoder is initialized and terminated by encoding bits known to said decoder.
Claim 10
Dependent Claim
26 words
The system according to claim 1, wherein said data message is N 1 message bits and said error detection checkword is N 2 error detection bits.
Claim 11
Dependent Claim
31 words
The system according to claim 9, wherein said N 2 error detection bits are the remainder on polynomial division of said N 1 message bits by a cyclic redundancy check polynomial.
Claim 12
Independent Claim
249 words
A method of communicating data adapted for reducing the incidence of data bit errors arising from transmission, comprising the steps of: assembling a number of data bits into a message to be transmitted; calculating a number of first error detection bits as a function of said message data bits; appending said error detection bits to said message; encoding said message and said appended error detection bits in an error correction encoder; producing a larger number of bits from said encoder for transmission; modulating said larger number of bits; transmitting said modulated bits over a communications medium; receiving estimates of said transmitted bits; demodulating said received estimates; decoding said demodulated estimates in an error correction decoder; generating a plurality of candidate bit sequences corresponding to the N most likely candidate message data and candidate first error detection bit sequences to have been transmitted; calculating a number of second error detection bits as a function of decoded message data bits for each of said candidate bit sequences; for each candidate bit sequence, comparing its calculated second error detection bits with its candidate first error detection bits to form an error detection syndrome, an error detection syndrome having a value of zero indicating that a candidate message data is error-free; and selecting a candidate message having a highest likelihood and an error detection syndrome having a value of zero, or if no zero value syndrome is found, selecting a candidate message having a highest likelihood and an acceptable non-zero error detection syndrome.
Claim 13
Independent Claim
249 words
A method of communicating data adapted for reducing the incidence of data bit errors arising from transmission, comprising the steps of: assembling a number of data bits into a message to be transmitted; calculating a number of first error detection bits as a function of said message data bits; appending said error detection bits to said message; encoding said message and said appended error detection bits in an error correction encoder; producing a larger number of bits from said encoder for transmission; modulating said larger number of bits; transmitting said modulated bits over a communications medium; receiving estimates of said transmitted bits; demodulating said received estimates; decoding said demodulated estimates in an error correction decoder; generating a plurality of candidate bit sequences corresponding to the N most likely candidate message data and candidate first error detection bit sequences to have been transmitted; calculating a number of second error detection bits as a function of decoded message data bits for each of said candidate bit sequences; for each candidate bit sequence, comparing its calculated second error detection bits with its candidate first error detection bits to form an error detection syndrome, an error detection syndrome having a value of zero indicating that a candidate message data is error-free; and selecting a candidate message having a highest likelihood and an error detection syndrome having a value of zero, or if no zero value syndrome is found, selecting a candidate message having a highest likelihood and an acceptable non-zero error detection syndrome.
Claim 14
Dependent Claim
31 words
A method of communicating data according to claim 11 wherein said error detection bits are the remainder on polynomial division of said message data bits by a cyclic redundancy check polynomial.
Claim 15
Dependent Claim
18 words
A method of communicating data according to claim 11 wherein said error correction encoding is a convolutional encoding.
Claim 16
Dependent Claim
53 words
A method of communicating data according to claim 11 wherein said error correction encoding is a convolutional encoding using tail-biting, further comprising the steps of: initializing said encoder by feeding in data bits unknown to said receiving decoder prior to said transmission; and terminating said encoder by feeding in said data bits again.
Claim 17
Dependent Claim
52 words
A method of communicating data according to claim 11 wherein said error correction encoding is a convolutional encoding, further comprising the steps of: initializing said encoder by feeding in a bit pattern known to said receiving decoder prior to said transmission; and terminating said encoder by feeding in said bit pattern again.
Claim 18
Dependent Claim
23 words
A method of communicating data according to claim 11 wherein said error correction decoding uses a sequential maximum likelihood sequence estimation Viterbi algorithm.
Claim 19
Dependent Claim
50 words
A method of communicating data according to claim 11, further comprising the step of: sorting final states of said decoder in ascending order of respective path metrics of said final states following the decoding of a complete input signal sequence for determining the order of said error detection bit comparisons.
Claim 20
Independent Claim
255 words
A method of communicating data adapted for reducing the incidence of data bit errors arising from transmission, comprising the steps of: assembling a number of data bits into a message to be transmitted; calculating a number of first error detection bits as a function of said message data bits; appending said error detection bits to said message; encoding said message and said appended error detection bits in an error correction encoder; producing a larger number of bits from said encoder for transmission; modulating said larger number of bits; transmitting said modulated bits over a communications medium; receiving estimates of said transmitted bits; demodulating said received estimates; decoding said demodulated estimates in an error correction decoder; generating a plurality of candidate bit sequences corresponding to the N most likely candidate message data and candidate first error detection bit sequences to have been transmitted; calculating a number of second error detection bits as a function of message data bits for each of said candidate bit sequences; for each candidate bit sequence, comparing its calculated second error detection bits with its candidate first error detection bits to produce a syndrome indicative of the number of errors; selecting a first candidate message from the candidate bit sequence having a highest likelihood and a syndrome indicative of no errors, or when no such candidate exists, selecting a second candidate message from the candidate bit sequence having the highest likelihood and a syndrome indicative of a correctable number of errors; and correcting said bit error in said second selected candidate message.
Claim 21
Independent Claim
255 words
A method of communicating data adapted for reducing the incidence of data bit errors arising from transmission, comprising the steps of: assembling a number of data bits into a message to be transmitted; calculating a number of first error detection bits as a function of said message data bits; appending said error detection bits to said message; encoding said message and said appended error detection bits in an error correction encoder; producing a larger number of bits from said encoder for transmission; modulating said larger number of bits; transmitting said modulated bits over a communications medium; receiving estimates of said transmitted bits; demodulating said received estimates; decoding said demodulated estimates in an error correction decoder; generating a plurality of candidate bit sequences corresponding to the N most likely candidate message data and candidate first error detection bit sequences to have been transmitted; calculating a number of second error detection bits as a function of message data bits for each of said candidate bit sequences; for each candidate bit sequence, comparing its calculated second error detection bits with its candidate first error detection bits to produce a syndrome indicative of the number of errors; selecting a first candidate message from the candidate bit sequence having a highest likelihood and a syndrome indicative of no errors, or when no such candidate exists, selecting a second candidate message from the candidate bit sequence having the highest likelihood and a syndrome indicative of a correctable number of errors; and correcting said bit error in said second selected candidate message.
Claim 22
Dependent Claim
31 words
A method of communicating data according to claim 18 wherein said error detection bits are the remainder on polynomial division of said message data bits by a cyclic redundancy check polynomial.
Claim 23
Dependent Claim
18 words
A method of communicating data according to claim 18 wherein said error correction encoding is a convolutional encoding.
Claim 24
Dependent Claim
53 words
A method of communicating data according to claim 18 wherein said error correction encoding is a convolutional encoding using tail-biting, further comprising the steps of: initializing said encoder by feeding in data bits unknown to said receiving decoder prior to said transmission; and terminating said encoder by feeding in said data bits again.
Claim 25
Dependent Claim
52 words
A method of communicating data according to claim 18 wherein said error correction encoding is a convolutional encoding, further comprising the steps of: initializing said encoder by feeding in a bit pattern known to said receiving decoder prior to said transmission; and terminating said encoder by feeding in said bit pattern again.
Claim 26
Dependent Claim
23 words
A method of communicating data according to claim 18 wherein said error correction decoding uses a sequential maximum likelihood sequence estimation Viterbi algorithm.
Claim 27
Dependent Claim
50 words
A method of communicating data according to claim 18, further comprising the step of: sorting final states of said decoder in ascending order of respective path metrics of said final states following the decoding of a complete input signal sequence for determining the order of said error detection bit comparisons.
Claim 28
Dependent Claim
124 words
A decoder apparatus comprising: logic circuitry for receiving a transmitted data message with an appended error check code; logic circuitry for generating a plurality of candidate data messages and an associated plurality of appended candidate error check codes, each of said plurality of candidate data messages having associated therewith a confidence measure indicative of a likelihood that said candidate data message matches said transmitted data message; logic circuitry for identifying, using said candidate error check codes, an error-free candidate data message having a highest confidence measure, and in absence thereof, for correcting a least-erroneous data message having a highest confidence measure; output circuitry for outputting said identified error-free candidate data message having a highest confidence measure, or in absence thereof, said corrected data message.
Claim 29
Dependent Claim
124 words
A decoder apparatus comprising: logic circuitry for receiving a transmitted data message with an appended error check code; logic circuitry for generating a plurality of candidate data messages and an associated plurality of appended candidate error check codes, each of said plurality of candidate data messages having associated therewith a confidence measure indicative of a likelihood that said candidate data message matches said transmitted data message; logic circuitry for identifying, using said candidate error check codes, an error-free candidate data message having a highest confidence measure, and in absence thereof, for correcting a least-erroneous data message having a highest confidence measure; output circuitry for outputting said identified error-free candidate data message having a highest confidence measure, or in absence thereof, said corrected data message.
References Cited (Backward Citations)
US4134071A
Cited
US4108359A
Cited
GB2033699A
Cited
US4368534A
Cited
US4307463A
Cited
US4497058A
Cited
US4949273A
Cited
US5208816A
Cited
US5327439A
Cited
US5230003A
Cited
US5349589A
Cited
EP0552781A2
Cited
EP0609934A2
Cited
US5355376A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-11-19 | 2000-05-20 | 2000-11-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-11-19 | 2004-05-20 | 2004-11-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-11-19 | 2008-05-20 | 2008-11-19 | $7700.00 | Window Closed / Lapsed |