US6263087B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of encoding bits in a signal
Assignee: NEC Corp
•
Filing: 1998-06-26
•
Granted: 2001-07-17
•
Expires: 2018-06-26
Abstract
Abstract A message in the form of a sequence of bits is encoded into relatively short, non-binary signals. The message (or vector) is divided into two halves. The encoder first determines an encoding of the message into a vector half the length of the eventual encoded vector. The half-length vector forms the first half of the encoded, and is negated to form the second half of the encoded vector. An identical synchronization signal is added to both halves of the encoded vector. The synchronization signal is used to compensate for the possibility that the received vector (or message) is cyclically rotated from the original vector. During decoding, the decoder first obtains the synchronization signal by adding the two halves of the vector together, canceling the encoded message. The synchronization signal is used to find the original cyclical shift of the vector. The decoder obtains the half-length encoded message vector by taking the difference between the two halves of the aligned full-length encoded vector. After decoding the vector into a bit sequence, the encoder re-encodes that bit sequence and compares the resulting vector with the original vector to determine whether the original vector truly encoded a message or was simply a noise signal.
Inventors
- 👤 Matthew L. Miller
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 19:56
CPC Classifications
H; H04; H04L; H04L7/00; H04L7/04; H04L7/041; H04L7/042; H03; H03M; H03M13/00; H03M13/03; H03M13/05; H03M13/13; H03M13/15; H03M13/151; H03M13/1515; H03M13/152; H03M13/19; H03M13/23
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
150 words
A method of decoding a received vector of two half vectors into a sequence of bits comprising the steps of: a) receiving a received vector of two half vectors, including a first half vector containing a synchronization signal and a first modulation vector, and a second half vector containing the synchronization signal and a second modulation vector which is the negation of the first modulation vector, where the received vector is a signal extracted from media according to a watermark extraction method; b) averaging the first half vector with the second half vector to obtain a received synchronization vector; c) determining an amount by which the received synchronization vector must be shifted to obtain the best match with a reference synchronization vector; d) shifting the received vector by the determined amount to obtain an aligned received vector, and e) demodulating the aligned received vector to obtain the sequence of bits.
Claim 2
Independent Claim
150 words
A method of decoding a received vector of two half vectors into a sequence of bits comprising the steps of: a) receiving a received vector of two half vectors, including a first half vector containing a synchronization signal and a first modulation vector, and a second half vector containing the synchronization signal and a second modulation vector which is the negation of the first modulation vector, where the received vector is a signal extracted from media according to a watermark extraction method; b) averaging the first half vector with the second half vector to obtain a received synchronization vector; c) determining an amount by which the received synchronization vector must be shifted to obtain the best match with a reference synchronization vector; d) shifting the received vector by the determined amount to obtain an aligned received vector, and e) demodulating the aligned received vector to obtain the sequence of bits.
Claim 3
Independent Claim
224 words
A method of decoding a received vector of two half vectors into a sequence of bits comprising the steps of: a) receiving a received vector of two half vectors, including a first half vector containing a synchronization signal and a first modulation vector, and a second half vector containing the synchronization signal and a second modulation vector which is the negation of the first modulation vector, where the received vector is a signal extracted from media according to a watermark extraction method; b) averaging the first half vector with the second half vector to obtaining a received synchronization vector, c) determining an amount by which the received synchronization vector must be shifted to obtain the best match with a reference synchronization vector; d) shifting the received vector by the determined amount to obtain an aligned received vector; and e) demodulating the aligned received vector to obtain the sequence of bits comprising averaging a first half of the aligned received vector with the negation of a second half of the aligned received vector to obtain a received modulated vector, demodulating the received modulated vector to obtain an extended sequence of bits, including at least one redundant bit, and correcting errors in the extended sequence of bits using the at least one redundant bit in the extended sequence of bits to obtain the sequence of bits.
Claim 4
Independent Claim
224 words
A method of decoding a received vector of two half vectors into a sequence of bits comprising the steps of: a) receiving a received vector of two half vectors, including a first half vector containing a synchronization signal and a first modulation vector, and a second half vector containing the synchronization signal and a second modulation vector which is the negation of the first modulation vector, where the received vector is a signal extracted from media according to a watermark extraction method; b) averaging the first half vector with the second half vector to obtaining a received synchronization vector, c) determining an amount by which the received synchronization vector must be shifted to obtain the best match with a reference synchronization vector; d) shifting the received vector by the determined amount to obtain an aligned received vector; and e) demodulating the aligned received vector to obtain the sequence of bits comprising averaging a first half of the aligned received vector with the negation of a second half of the aligned received vector to obtain a received modulated vector, demodulating the received modulated vector to obtain an extended sequence of bits, including at least one redundant bit, and correcting errors in the extended sequence of bits using the at least one redundant bit in the extended sequence of bits to obtain the sequence of bits.
Claim 5
Independent Claim
78 words
A method of determining whether a received vector encodes a message in the form of a sequence of bits comprising the steps of: a) decoding a received vector where the received vector is a signal extracted from media according to a watermark extraction method to obtain a received message; b) encoding the received message to obtain an encoded vector, and c) comparing the received vector with the encoded vector to determine whether the received vector encodes a message.
Claim 6
Independent Claim
78 words
A method of determining whether a received vector encodes a message in the form of a sequence of bits comprising the steps of: a) decoding a received vector where the received vector is a signal extracted from media according to a watermark extraction method to obtain a received message; b) encoding the received message to obtain an encoded vector, and c) comparing the received vector with the encoded vector to determine whether the received vector encodes a message.
Claim 7
Dependent Claim
80 words
The method of claim 3 , where said decoding comprises averaging a first half of the received vector with a second half of the received vector to obtain a received synchronization vector; determining an amount by which the received synchronization vector must be shifted to obtain the best match with a reference synchronization vector; shifting the received vector by the determined amount to obtain an aligned received vector, and decoding the aligned received vector to obtain the sequence of bits.
Claim 8
Dependent Claim
16 words
The method of claim 4 , where the determined amount is an amount of cyclical shifting.
Claim 9
Dependent Claim
29 words
The method of claim 4 , where the match between the received synchronization vector and the reference synchronization vector is measured by computing the correlation between both synchronization vectors.
Claim 10
Dependent Claim
15 words
The method of claim 4 , where said shifting the received vector is cyclical shifting.
Claim 11
Dependent Claim
82 words
The method of claim 4 , where said decoding comprises averaging a first half of the aligned received vector with the negation of a second half of the aligned received vector to obtain a received modulated vector; demodulating the received modulated vector to obtain an extended sequence of bits, including at least one redundant bit; correcting errors in the extended sequence of bits using the at least one redundant bit in the extended sequence of bits to obtain the sequence of bits.
Claim 12
Dependent Claim
57 words
The method of claim 8 , where said demodulating comprises multiplying the received modulated vector by the inverse of a modulation matrix to obtain a demodulated vector, and comparing each element of the demodulated vector with a predetermined threshold to determine whether the corresponding bit in the sequence of bits should be a 0 or a 1.
Claim 13
Dependent Claim
19 words
The method of claim 9 , where the columns of the modulation matrix have zero correlation with one another.
Claim 14
Dependent Claim
12 words
The method of claim 9 , where the predetermined threshold is zero.
Claim 15
Dependent Claim
18 words
The method of claim 8 , where said correcting errors is performed according to an error-correction decoding method.
Claim 16
Dependent Claim
27 words
The method of claim 12 , where the error-correction decoding method is selected from the group consisting of Hamming decoding, BCH decoding, Reed-Solomon decoding, or Convolutional decoding.
Claim 17
Dependent Claim
32 words
The method of claim 13 , where said correcting errors comprises comparing the at least one redundant bit with a constant value to determine whether all of the bits must be flipped.
Claim 18
Dependent Claim
32 words
The method of claim 12 , where said correcting errors comprises comparing the at least one redundant bit with a constant value to determine whether all of the bits must be flipped.
Claim 19
Dependent Claim
32 words
The method of claim 8 , where said correcting errors comprises comparing the at least one redundant bit with a constant value to determine whether all of the bits must be flipped.
Claim 20
Dependent Claim
77 words
The method of claim 3 , where said encoding comprises appending at least one redundant bit to the received message to obtain an expanded sequence of bits; modulating the expanded sequence of bits to obtain a modulated vector; appending the negation of the modulated vector to the modulated vector to obtain a double-length modulated vector; and adding a synchronization vector to both the modulated vector and the negation of the modulated vector to obtain the encoded vector.
Claim 21
Dependent Claim
23 words
The method of claim 17 , where one or more redundant bits of constant value are appended to the expanded sequence of bits.
Claim 22
Dependent Claim
24 words
The method of claim 18 , where further redundant bits are appended to the expanded sequence of bits according to an error-correction encoding method.
Claim 23
Dependent Claim
27 words
The method of claim 19 , where the error-correction encoding method is selected from the group consisting of Hamming encoding, BCH encoding, Reed-Solomon encoding, or Convolutional encoding.
Claim 24
Dependent Claim
24 words
The method of claim 17 , further comprising appending additional redundant bits to the expanded sequence of bits according to an error-correction encoding method.
Claim 25
Dependent Claim
27 words
The method of claim 21 , where the error-correction encoding method is selected from the group consisting of Hamming encoding, BCH encoding, Reed-Solomon encoding, or Convolutional encoding.
Claim 26
Dependent Claim
34 words
The method of claim 17 , where said modulating comprises converting the extended sequence of bits into a bit vector and multiplying the bit vector by a modulation matrix to obtain the modulated vector.
Claim 27
Dependent Claim
41 words
The method of claim 23 , where the bit vector contains a first value corresponding to each 0 bit of the extended sequence of bits and contains a second value corresponding to each 1 bit of the extended sequence of bits.
Claim 28
Dependent Claim
19 words
The method of claim 23 , where the columns of the modulation matrix have zero correlation with one another.
Claim 29
Dependent Claim
29 words
The method of claim 3 , where said comparing comprises computing the correlation between the received vector and the encoded vector, and comparing the correlation with a predetermined threshold.
Claim 30
Dependent Claim
34 words
The method of claim 3 , where said comparing comprises the steps of computing the correlation coefficient between the received vector and the encoded vector, and comparing the correlation coefficient with a predetermined threshold.
Claim 31
Dependent Claim
34 words
The method of claim 3 , where said comparing comprises the steps of computing the normalized correlation between the received vector and the encoded vector, and comparing the normalized correlation with a predetermined threshold.
Claim 32
Independent Claim
81 words
A method of determining whether a received vector encodes a message in the form of a sequence of bits comprising the steps of: a) decoding a received vector to obtain a received message; b) encoding the received message to obtain an encoded vector; and c) comparing the received vector with the encoded vector to determine whether the received vector encodes a message, where said comparing determines whether the received vector is inside or outside a hyperboloid centered on the encoded vector.
Claim 33
Independent Claim
81 words
A method of determining whether a received vector encodes a message in the form of a sequence of bits comprising the steps of: a) decoding a received vector to obtain a received message; b) encoding the received message to obtain an encoded vector; and c) comparing the received vector with the encoded vector to determine whether the received vector encodes a message, where said comparing determines whether the received vector is inside or outside a hyperboloid centered on the encoded vector.
Claim 34
Dependent Claim
22 words
The method of claim 29 , where the received vector is a signal extracted from media according to a watermark extraction method.
References Cited (Backward Citations)
US3810019A
Cited
US4777635A
Cited
US5870405A
Cited
US5450443A
Cited
US5828676A
Cited
US5907565A
Cited
US5883929A
Cited
US5909645A
Cited
US5889868A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-07-16 | 2005-01-15 | 2005-07-17 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-07-16 | 2009-01-15 | 2009-07-17 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-07-16 | 2013-01-15 | 2013-07-17 | $7700.00 | Window Closed / Lapsed |