Apparatus and method for decoding data

• US 8,907,821 B1
• Filed: 06/05/2012
• Issued: 12/09/2014
• Est. Priority Date: 09/16/2010
• Status: Expired due to Fees

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Massimino, Pascal
• Primary Examiner(s): Mai, Lam T
• Application Number:
  US13/489,025
• Time in Patent Office: 917 Days
• Field of Search: 713/168, 713/303, 713/340, 707/693, 707/698, 707/827, 382/100, 382/245, 382/253, 704/201, 704/203, 704/205, 704/207, 704/212, 704/267, 704/275, 341 50- 90, 375/147, 375/150, 375/377, 375/E1.002, 375/240.22, 375/240.16
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3088 employing the use of a dictionary, e.g. LZ78

Abstract

A computer-implemented method and apparatus are disclosed for decoding an encoded data signal. In one embodiment, the method includes accessing, in a memory, a set of signal elements. The encoded data signal is received at a computing device. The signal includes signal fragments each having a projection value and an index value. The projection value has been calculated as a function of at least one signal element of the set of signal elements and at least a portion of the data signal. The index value associates its respective signal fragment with the at least one signal element used to calculate the projection value. The computing device determines amplitude values based on the projection values in the signal fragments. The decoded signal is determined using the amplitude values and the signal elements associated with the at least some of the signal fragments.

Claims

1. A computer-implemented method for decoding an encoded data signal, comprising:

accessing in a memory a set of signal elements;

receiving, at a computing device, the encoded data signal including a plurality of signal fragments each having;

(i) a projection value that has been calculated as a function of at least one signal element of the set of signal elements and at least a portion of the encoded data signal; and

(ii) a value associating each respective signal fragment with the at least one signal element used to calculate the projection value;

determining, by the computing device, a plurality of amplitude values wherein at least one of the plurality of amplitude values is based on the projection value in at least one of the plurality of signal fragments; and

determining a decoded signal using the plurality of amplitude values and signal elements associated with the at least one of the plurality of signal fragments.

2. The method of claim 1, further comprising:

de-duplicating the plurality of signal fragments.

3. The method of claim 1, wherein determining the plurality of amplitudes further comprises solving a linear system.

4. The method of claim 1, wherein the set of signal elements is a dictionary of signal elements having a plurality of records each including an index (i) and a signal element (U_i).

5. The method of claim 4, wherein a k^th amplitude value (A_k) of the plurality of amplitude values is based on the projection value of a k^th signal fragment and is determined by solving the following linear system:

6. The method of claim 5, wherein determining the decoded signal using the plurality of amplitude values and the signal elements associated with the at least one of the plurality of signal fragments further comprises determining at least a portion of the decoded signal REC based on a result of the following summation:

7. The method of claim 1, wherein determining the decoded signal using the plurality of amplitude values and the signal elements associated with the at least one of the plurality of signal fragments further comprises:

determining a weighted sum of the signal elements, wherein a weight of each signal element is based on at least one of the plurality of amplitude values.

8. The method of claim 1, further comprising:

periodically receiving, in the memory, at least an updated portion of the set of signal elements.

9. A computer-implemented method for decoding an encoded data signal, comprising:

accessing in a memory a set of signal elements;

receiving, at a computing device, the encoded data signal including a plurality of signal fragments each having a projection value and an index value;

identifying, from the set of signal elements stored in the memory, a plurality of selected signal elements, at least one of which corresponds to the index value in at least one of the plurality of signal fragments; and

determining, by the computing device, a decoded data signal based on the plurality of selected signal elements and at least one projection value included in the plurality of signal fragments.

10. The method of claim 9, wherein the at least one projection value is calculated as a function of at least one signal element of the set of signal elements and at least a portion of the encoded data signal.

11. The method of claim 9, wherein the index value in the at least one of the plurality of signal fragments associates its respective signal fragment with at least one signal element used to calculate the projection value.

12. The method of claim 9, wherein determining, by the computing device, the decoded data signal based on the plurality of selected signal elements and the at least one projection value, further comprises:

determining, by the computing device, a plurality of amplitude values based at least in part on the projection value in at least one of the plurality of signal fragments; and

determining the decoded data signal using the plurality of amplitude values and the plurality of selected signal elements.

13. The method of claim 12, wherein determining the plurality of amplitude values further comprises solving a linear system.

14. The method of claim 12, wherein determining the decoded signal using the plurality of amplitude values and the plurality of selected signal elements further comprises:

determining a weighted sum of the plurality of selected signal elements, wherein a weight of each of the plurality of selected signal elements is based on at least one of the plurality of amplitude values.

15. The method of claim 9, further comprising:

de-duplicating the plurality of signal fragments from the encoded data signal.

16. An apparatus for decoding an encoded data signal, comprising:

a memory including a set of signal elements; and

a processor in communication with the memory and configured to execute instructions to;

receive the encoded data signal including a plurality of signal fragments each having a projection value and an index value;

identifying, using at least one index value included in the plurality of signal fragments, a plurality of selected signal elements in the set of signal elements; and

determining a decoded data signal based on the plurality of selected signal elements and at least one projection value included in the plurality of signal fragments.

17. The apparatus of claim 16, further comprising:

a receiver adapted to receive a satellite signal that includes the encoded data signal.

18. The apparatus of claim 16, wherein the projection value of at least one of the plurality of signal fragments is calculated as a function of at least one signal element of the set of signal elements and at least a portion of the encoded data signal.

19. The apparatus of claim 16, wherein at least one index value points to one of the plurality of signal fragments that was used to calculate the at least one projection value.

20. The apparatus of claim 16, wherein the processor is further configured to execute instructions to:

determine a plurality of amplitude values based at least in part on the projection value in at least one of the plurality of signal fragments; and

determine the decoded data signal using the plurality of amplitude values and the plurality of selected signal elements.