Coding a signal with a shuffled-Hadamard function

• US 20090185629A1
• Filed: 01/21/2009
• Published: 07/23/2009
• Est. Priority Date: 12/05/2000
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Gunter, Michial Allen, Gossett, Carroll Philip
• Granted Patent: US 8,385,470 B2
• Time in Patent Office: Days
• US Class Current: 375/259
• 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 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.

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 identifying the column of data bits comprises applying a logical function to two or more columns of bits from the matrix of data bits.

8. The method of claim 7, wherein each column in the two or more columns has a power-of-two column index.

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

10. The method of claim 7, wherein identifying the column of data bits comprises identifying the m^th column, 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.

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

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. 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 the 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 one 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.

15. The method of claim 14, 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.

16. The method of claim 15, 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.

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

18. The system of claim 17, 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.

19. The system of claim 17, 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.

20. The system of claim 17, 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.

21. The system of claim 20, 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.

22. A system comprising:

an electronic receiver; and

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

a means for transmitting from the transmitter data bits from a matrix having the form of a 2^N×

2^N Hadamard matrix whose rows have been randomly or pseudo-randomly shuffled, in place of the first data value.

23. The system of claim 22, further comprising a means for receiving data at the electronic receiver and for determining that the received data is correlated to the first data value.

24. 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 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 one of the plurality of predetermined data values, and 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.