Method for encoding bits in a signal

• US 20010016052A1
• Filed: 03/26/2001
• Published: 08/23/2001
• Est. Priority Date: 06/26/1998
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Research Institute, Inc. (NEC Corporation)
• Inventors: Miller, Matthew L.
• Granted Patent: US 6,438,252 B2
• Time in Patent Office: Days
• US Class Current: 382/100
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/152 Bose-Chaudhuri-Hocquenghem [BCH] codes
• CPC Class Codes: H03M 13/19 Single error correction without using particular properties of the cyclic codes, e.g. Hamming codes, extended or generalised Hamming codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H04L 7/042 Detectors therefor, e.g. correlators, state machines digital correlators in general G06F17/15

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.

Claims

1. A method of encoding a message in the form of a sequence of bits to form an encoded vector comprising the steps of:

a) expanding the sequence of bits to obtain an expanded sequence of bits;

b) modulating the expanded sequence of bits to obtain a modulated vector;

c) appending the negation of the modulated vector to the modulated vector to obtain a double-length modulated vector, and

d) adding a synchronization signal to both the modulated vector and the negation of the modulated vector of the double-length modulated vector to obtain an encoded vector.

2. The method of

claim 1

, further comprising inserting the encoded vector into media as a watermark.

3. The method of

claim 1

, where said expanding comprises appending at least one redundant bit of constant value to the sequence of bits.

4. The method of

claim 3

, further comprising appending at least one additional redundant bit to the sequence of bits according to an error-correction encoding method.

5. The method of

claim 4

, further comprising inserting the encoded vector into media as a watermark.

6. The method of

claim 4

, where the error-correction encoding method is selected from the group consisting of Hamming encoding, BCH encoding, Reed-Solomon encoding, and Convolutional encoding.

7. The method of

claim 1

, where said expanding comprises appending at least one redundant bit to the sequence of bits according to an error-correction encoding method.

8. The method of

claim 7

, further comprising inserting the encoded vector into media as a watermark.

9. The method of

claim 7

, where the error-correction encoding method is selected from the group consisting of Hamming encoding, BCH encoding, Reed-Solomon encoding, or Convolutional encoding.

10. The method of

claim 1

, where said modulating comprises converting the expanded sequence of bits into a bit vector and multiplying the bit vector by a modulation matrix to obtain the modulated vector.

11. The method of

claim 10

, where the bit vector contains a first value corresponding to each 0 bit of the expanded sequence of bits and contains a second value corresponding to each 1 bit of the expanded sequence of bits.

12. The method of

claim 10

, where the columns of the modulation matrix have zero correlation with one another.

13. A method of decoding a received vector of two half vectors into a sequence of bits comprising the steps of:

a) averaging the first half of the received vector with the second half of the received vector to obtain a received synchronization vector;

b) determining an amount by which the received synchronization vector must be shifted to obtain the best match with a reference synchronization vector;

c) shifting the received vector by the determined amount to obtain an aligned received vector, and

d) demodulating the aligned received vector to obtain the sequence of bits.

14. The method of

claim 13

, where the received vector is a signal extracted from media according to a watermark extraction method.

15. The method of

claim 13

, where the determined amount is an amount of cyclical shifting.

16. The method of

claim 13

, where the match between the received synchronization vector and the reference synchronization vector is measured by computing the correlation between both synchronization vectors.

17. The method of

claim 13

, where said shifting the received vector is cyclical shifting.

18. The method of

claim 13

, where said demodulating 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; 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.

19. The method of

claim 18

, where the received vector is a signal extracted from media according to a watermark extraction method.

20. The method of

claim 18

, where said demodulating the received modulated vector 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.

21. The method of

claim 20

, where the columns of the modulation matrix have zero correlation with one another.

22. The method of

claim 20

, where the predetermined threshold is zero.

23. The method of

claim 18

, where said correcting errors is performed according to an error-correction decoding method.

24. The method of

claim 23

, where the error-correction decoding method is selected from the group consisting of Hamming decoding, BCH decoding, Reed-Solomon decoding, and Convolutional decoding.

25. The method of

claim 24

, where said correcting errors comprises comparing one or more redundant bits with constant values to determine whether all of the bits must be flipped.

26. The method of

claim 23

, where said correcting errors comprises comparing one or more redundant bits with constant values to determine whether all the bits must be flipped.

27. The method of

claim 18

, where said correcting errors comprises comparing one or more redundant bits with constant values to determine whether all the bits must be flipped.

28. 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.

29. The method of

claim 28

, where the received vector is a signal extracted from media according to a watermark extraction method.

30. The method of

claim 28

, 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.

31. The method of

claim 30

, where the received vector is a signal extracted from media according to a watermark extraction method.

32. The method of

claim 30

, where the determined amount is an amount of cyclical shifting.

33. The method of

claim 30

, where the match between the received synchronization vector and the reference synchronization vector is measured by computing the correlation between both synchronization vectors.

34. The method of

claim 30

, where said shifting the received vector is cyclical shifting.

35. The method of

claim 30

, 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.

36. The method of

claim 35

, where the received vector is a signal extracted from media according to a watermark extraction method.

37. The method of

claim 35

, 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.

38. The method of

claim 37

, where the columns of the modulation matrix have zero correlation with one another.

39. The method of

claim 37

, where the predetermined threshold is zero.

40. The method of

claim 35

, where said correcting errors is performed according to an error-correction decoding method.

41. The method of

claim 40

, where the error-correction decoding method is selected from the group consisting of Hamming decoding, BCH decoding, Reed-Solomon decoding, or Convolutional decoding.

42. The method of

claim 41

, 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.

43. The method of

claim 42

, where the received vector is a signal extracted from media according to a watermark extraction method.

44. The method of

claim 40

, 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.

45. The method of

claim 35

, where said correcting errors comprises comparing the at least one redundant bit with constant a value to determine whether all of the bits must be flipped.

46. The method of

claim 45

, where the received vector is a signal extracted from media according to a watermark extraction method.

47. The method of

claim 28

, 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.

48. The method of

claim 47

, where the received vector is a signal extracted from media according to a watermark extraction method.

49. The method of

claim 47

, where one or more redundant bits of constant value are appended to the expanded sequence of bits.

50. The method of

claim 49

, where further redundant bits are appended to the expanded sequence of bits according to an error-correction encoding method.

51. The method of

claim 50

, where the error-correction encoding method is selected from the group consisting of Hamming encoding, BCH encoding, Reed-Solomon encoding, or Convolutional encoding.

52. The method of

claim 47

, further comprising appending additional redundant bits to the expanded sequence of bits according to an error-correction encoding method.

53. The method of

claim 52

, where the error-correction encoding method is selected from the group consisting of Hamming encoding, BCH encoding, Reed-Solomon encoding, or Convolutional encoding.

54. The method of

claim 47

, 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.

55. The method of

claim 54

, 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.

56. The method of

claim 54

, where the columns of the modulation matrix have zero correlation with one another.

57. The method of

claim 28

, where said comparing comprises computing the correlation between the received vector and the encoded vector, and comparing the correlation with a predetermined threshold.

58. The method of

claim 28

, 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.

59. The method of

claim 58

, where the received vector is a signal extracted from media according to a watermark extraction method.

60. The method of

claim 28

, 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.

61. The method of

claim 60

, where the received vector is a signal extracted from media according to a watermark extraction method.

62. The method of

claim 28

, where said comparing determines whether the received vector is inside or outside a hyperboloid centered on the encoded vector.

63. The method of

claim 62

, where the received vector is a signal extracted from media according to a watermark extraction method.

64. A method of encoding a message in the form of a sequence of bits to form an encoded vector comprising the steps of:

a) modulating the sequence of bits to obtain a modulated vector;

b) appending the negation of the modulated vector to the modulated vector to obtain a double-length modulated vector, and

c) adding a synchronization signal to both the modulated vector and the negation of the modulated vector of the double-length modulated vector to obtain an encoded vector.

65. The method of

claim 64

, where the received vector is a signal extracted from media according to a watermark extraction method.

66. The method of

claim 64

, where said modulating comprises converting the sequence of bits into a bit vector and multiplying the bit vector by a modulation matrix to obtain the modulated vector.

67. The method of

claim 66

, where the bit vector contains a first value corresponding to each 0 bit of the expanded sequence of bitsand contains a second value corresponding to each 1 bit of the expanded sequence of bits.

68. The method of

claim 66

, where the columns of the modulation matrix have zero correlation with one another.