Coding a signal with a shuffled-Hadamard function

• US 8,385,470 B2
• Filed: 01/21/2009
• Issued: 02/26/2013
• Est. Priority Date: 12/05/2000
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gossett, Carroll Philip, Gunter, Michial Allen
• Primary Examiner(s): Liu, Shuwang
• Assistant Examiner(s): Bolourchi, Nader
• Application Number:
  US12/356,791
• Publication Number:
  US 20090185629A1
• Time in Patent Office: 1,497 Days
• Field of Search: 375/316, 375/141, 375/145, 375/146, 375/149, 370/209
• US Class Current: 375/316
• CPC Class Codes: H04B 1/707 using direct sequence modulation
• CPC Class Codes: H04B 1/7093 Matched filter type
• CPC Class Codes: H04L 1/0059 Convolutional codes
• CPC Class Codes: H04L 23/02 adapted for orthogonal signalling

Abstract

A method can include receiving, at an electronic transmitter device, for communication to an electronic receiver device, a first data value corresponding to one of a plurality of predetermined data values; identifying, from a matrix of data bits having the form of a 2^N×2^N Hadamard matrix whose rows have been randomly or pseudo-randomly shuffled, a column of data bits that is associated with the first data value; and transmitting to the electronic receiver device, in place of the first data value, the identified column of data bits. The method can further include receiving data at the electronic receiver; correlating the received data to the identified column of data bits; and providing the first data value for further processing by the electronic receiver.

Claims

1. A method comprising:

receiving, at an electronic transmitter device, for communication to an electronic receiver device, a first data value corresponding to one of a plurality of predetermined data values;

identifying, from a matrix of data bits in a form of a 2^N×

2^N Hadamard matrix whose rows have been randomly or pseudo-randomly shuffled, a column of data bits that is associated with the first data value;

generating the identified column of data bits based on a proper subset of the columns of the matrix of data bits, each of the columns in the proper subset having a power-of-two column index in the matrix of data bits, the proper subset comprising two or more columns of the matrix of data bits, the proper subset not comprising the identified column of data bits; and

transmitting to the electronic receiver device, in place of the first data value, the identified column of data bits.

2. The method of claim 1, further comprising:

receiving data at the electronic receiver;

correlating the received data to the identified column of data bits; and

providing the first data value for further processing by the electronic receiver.

3. The method of claim 2, wherein correlating the received data to the identified column of data bits comprises:

calculating a correlation between the received data and each column in the matrix of data bits to which is associated one of the predetermined data values; and

determining that the received data is most strongly correlated to the identified column of data bits.

4. The method of claim 3, wherein calculating comprises calculating a sign of the correlation, and determining comprises determining based on the calculated sign.

5. The method of claim 2, wherein correlating the received data to the identified column of data bits comprises calculating a Hadamard transform or fast Hadamard transform.

6. The method of claim 1, further comprising associating the first data value to the column of data bits in a manner that the first data value can be determined by the electronic receiver, from the transmitted column of data bits, in discrimination to other data transmitted by the electronic transmitter device.

7. The method of claim 1, wherein generating the identified column of data bits comprises applying a logical function to the two or more columns of bits from the matrix of data bits.

8. The method of claim 7, wherein applying the logical function comprises applying, bit-wise, an exclusive-OR function to the two or more columns.

9. The method of claim 7, wherein generating the identified column of data bits comprises generating the m^th column of the matrix of data bits, and applying the logical function comprises applying, bit-wise, an exclusive-OR function to each power-of-two column in the matrix of bits whose m^th row has a value equal to a first predetermined value.

10. The method of claim 7, further comprising storing in a memory device included in each of the electronic transmitter device and the electronic receiver device, a 2^N×

N matrix corresponding to columns of the matrix of data bits having power-of-two indices, wherein all of the columns of the matrix of data bits stored by the memory device are columns having power-of-two column indices in the matrix of data bits.

11. The method of claim 10, wherein storing the 2^N×

N matrix corresponding to columns of the matrix of data bits having power-of-two indices comprises storing a 2^N×

N matrix that includes only columns from the matrix of data bits having power-of-two indices in the matrix of data bits, the stored columns having already been randomly or pseudo-randomly shuffled.

12. The method of claim 1, wherein transmitting the identified column of data bits comprises transmitting, in order and one bit at a time, each bit contained in the identified column.

13. The method of claim 1, wherein each of the predetermined data values has a fixed number of one or more data bits.

14. The method of claim 1, wherein generating the identified column of data bits based on a proper subset of the columns of the matrix of data bits comprises:

without using any columns of the matrix of data bits that do not have power-of-two columns, generating the identified column of data bits based on a proper subset of the columns of the matrix of data bits that includes only columns having power-of-two column indices.

15. The method of claim 1, wherein generating the identified column of data bits based on a proper subset of the columns of the matrix of data bits comprises:

generating a particular column from the matrix of data bits that does not have a power-of-two column index, the proper subset comprising (i) a first column of data bits that is already shuffled relative to the corresponding column in a standard Hadamard matrix, the first column of data bits having a first power-of-two column index in the matrix of data bits, and (ii) a second column of data bits that is already shuffled relative to the corresponding column in a standard Hadamard matrix, the second column of data bits having a second power-of-two column index different from the first power-of-two column index.

16. The method of claim 1, generating the identified column of data bits based on a proper subset of the columns of the matrix of data bits comprises:

identifying a first column index for a particular column of the matrix of data bits to be generated;

selecting, from among the columns of data bits that have power-of-two column indices in the matrix of data bits, each column of data bits that has a particular predetermined value in a row having a row index equal to the first column index; and

applying, bit-wise, an exclusive-OR function to each of the selected columns of data bits.

17. A method comprising:

receiving, at an electronic transmitter device, for communication to an electronic receiver device, a first data value corresponding to one of a plurality of predetermined data values;

identifying, from a matrix of data bits in a form of a 2^N×

2^N Hadamard matrix whose rows have been randomly or pseudo-randomly shuffled, an m^th column of data bits that is associated with the first data value;

generating the m^th column of bits, including applying, bitwise, an exclusive-OR function to two or more power-of-two columns from the matrix of bits whose m^th row has a value equal to a first predetermined value; and

transmitting to the electronic receiver device, in place of the first data value, the dynamically generated m^th column of data bits.

18. The method of claim 17, further comprising storing the 2^N×

2^N Hadamard matrix of data bits in a compressed 2^N×

N matrix in which only columns of the matrix of data bits having power-of-two column indices are stored in the electronic transmitter device.

19. The method of claim 18, wherein generating the m^th column of bits comprises determining one or more columns in the compressed 2^N×

N matrix whose m^th row has a value equal to the first value, and applying, bitwise, an exclusive-OR function to the one or more columns.

20. The method of claim 17, wherein generating the m^th column of bits, including applying, bitwise, an exclusive-OR function to two or more power-of-two columns from the matrix of bits whose m^th row has a value equal to a first predetermined value comprises generating the m^th column of bits by applying, bitwise, the exclusive-OR function to a set of operands that includes only power-of-two columns from the matrix of bits whose m^th row has a value equal to a first predetermined value.

21. A system comprising:

an electronic receiver; and

an electronic transmitter that receives for communication to the electronic receiver a first data value corresponding to one of a plurality of predetermined data values;

wherein the electronic transmitter;

identifies, from a matrix of data bits in a form of a 2^N×

2^N Hadamard matrix whose rows have been randomly or pseudo-randomly shuffled, a column of data bits that is associated with the first data value,

generates the identified column of data bits based on a proper subset of the columns of the matrix, each of the columns in the proper subset having a power-of-two column index in the matrix of data bits, the proper subset comprising two or more columns of the matrix, the proper subset not comprising the identified column of data bits, and

transmits to the electronic receiver device, in place of the first data value, the identified column of data bits; and

wherein the electronic receiver receives data, correlates the received data to the identified column of data bits, and provides to circuitry within the electronic receiver the first data value for further processing.

22. The system of claim 21, wherein the electronic transmitter comprises a memory device that stores the 2^N×

2^N Hadamard matrix of data bits in a compressed 2^N×

N matrix in which only columns of the matrix of data bits having power-of-two column indices are stored.

23. The system of claim 21, wherein:

the identified column of data bits comprises the m^th column of the matrix of data bits; and

the electronic transmitter further comprises circuitry for generating the m^th column from the compressed 2^N×

N matrix by applying, bitwise, an exclusive-OR function to one or more columns in the compressed 2^N×

N matrix whose m^th row has a first value.

24. The system of claim 21, wherein the electronic receiver comprises a plurality of correlators that calculate correlations between the received data and each of a corresponding plurality of columns of the matrix of data bits to which data values in the plurality of predetermined data values are associated.

25. The system of claim 24, wherein the electronic receiver further comprises circuitry that (a) determines which of the corresponding columns from the matrix of data bits has the strongest calculated correlation to the received data and (b) outputs a data value from the plurality of predetermined data values that is associated with the determined corresponding column.

26. A system comprising:

an electronic receiver; and

an electronic transmitter that receives for communication to the electronic receiver a first data value corresponding to one of a plurality of predetermined data values;

wherein the transmitter identifies, from a matrix of data bits having a form of a 2^N×

2^N Hadamard matrix whose rows have been randomly or pseudo-randomly shuffled, a column of data bits that is associated with one of the plurality of predetermined data values, the identified column of data bits being an m^th column of the 2^N×

2^N Hadamard matrix,

wherein the transmitter generates the m^th column by applying, bitwise, an exclusive-OR function to two or more input columns from the matrix of data bits, each of the two or more input columns having (i) a power-of-two column index in the matrix of bits and (ii) a value in the m^th row that is equal to a first predetermined value; and

wherein the transmitter transmits to the electronic receiver device, in place of and based on the first data value, the identified column of data bits or a complement of the identified column of data bits; and

wherein the electronic receiver receives data, correlates the received data to the identified column of data bits or the complement, and provides to circuitry within the electronic receiver the first data value for further processing.