Apparatus and method for encoding using signal fragments for redundant transmission of data

• US 8,477,050 B1
• Filed: 09/15/2011
• Issued: 07/02/2013
• Est. Priority Date: 09/16/2010
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Massimino, Pascal
• Primary Examiner(s): Mai, Lam T
• Application Number:
  US13/233,640
• Time in Patent Office: 656 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 system and method for redundant transmission is provided. In one embodiment, an input signal S is encoded as a list of fragments. Each fragment includes an index value and a projection value. The index points to an entry in a dictionary of signal elements. A repetition factor is assigned to each fragment based on its importance. After a fragment is added, a reconstructed signal is generated by decoding the list of fragments. Encoding terminates once the reconstructed signal is sufficiently close to the original signal S.

Claims

1. A method for encoding a data signal, comprising:

accessing a set of signal elements stored in a memory; and

generating a plurality of signal fragments, wherein each of at least some of the plurality of signal fragments are associated with (i) at least one signal element selected from the set of signal elements, and (ii) a transform value that is calculated as a function of at least a portion of the data signal and the at least one signal element.

2. The method of claim 1, wherein the set of signal elements is configured such that the data signal can be approximated from a weighted sum of a subset of the set of signal elements.

3. The method of claim 1, wherein generating the plurality of signal fragments further comprises successively adding new signal fragments to the plurality of signal fragments until the plurality of signal fragments is of a number to permit reconstruction of the data signal with a level of fidelity that exceeds a threshold.

4. The method of claim 1, further comprising:

determining a repetition factor for at least some of the plurality of signal fragments, wherein the repetition factor for each such signal fragment is based at least in part on the signal element associated with that signal fragment.

5. The method of claim 4, wherein determining the repetition factor for a specific signal fragment further comprises determining a transfer energy value associated with the specific signal fragment;

and determining the repetition factor as a function of the transfer energy value.

6. The method of claim 4, further comprising:

transmitting the plurality of signal fragments, including duplicate copies of at least one of the signal fragments based on the repetition factor.

7. The method of claim 1, wherein generating the plurality of signal fragments further comprises generating the plurality of signal fragments sequentially and, after each signal fragment is generated, generating a reconstructed signal using the plurality of signal fragments and determining the fidelity of the reconstructed signal.

8. The method of claim 1, further comprising:

determining a plurality of amplitudes (A_k) using the signal fragments; and

determining a reconstructed signal (REC) using the plurality of amplitudes (A_k) and the signal elements associated with each of the plurality of signal fragments.

9. The method of claim 8, wherein determining the plurality of amplitudes (A_k) further comprises solving a linear system.

10. The method of claim 8, wherein the linear system is expressed as follows:

11. The method of claim 8, wherein the amplitude (A_k) for each k^th signal fragment U_i,k in the plurality of signal elements is determined based upon the transform value associated in the k_th signal fragment.

12. The method of claim 8, wherein determining the reconstructed signal further comprises setting the reconstructed signal (REC) equal to:

13. The method of claim 8, further comprising:

determining a residual signal based on differences between the data signal and the reconstructed signal (REC);

determining the scalar product of the residual signal (R) and at least one of the signal elements in the set of signal elements; and

selecting at least one of the signal elements from the set of signal elements based on the determined scalar product.

14. The method of claim 1, further comprising:

transmitting the plurality of signal fragments to a decoder that has access to a copy of the set of signal elements used to encode the data signal.

15. The method of claim 1, wherein the data signal includes signal elements that are at least one of audio data or video data.

16. A method for encoding a data signal, comprising:

accepting as input the data signal to be encoded;

storing in memory a set of signal elements that includes elements not found in the data signal; and

generating a list of fragments from which can be derived an approximation of the data signal, at least some of the fragments referencing at least one of the signal elements selected from the set of signal elements;

wherein the list of fragments is generated by an iterative process of adding at least one new fragment to the list of fragments, using the list of fragments to generate a reconstructed signal, and using a processor to determine the fidelity of the reconstructed signal.

17. The method of claim 16, wherein the iterative process is repeated until the determined fidelity reaches a threshold.

18. The method of claim 16, wherein the set of signal elements is configured such that the data signal can be approximated from a weighted sum of a subset of the signal elements.

19. The method of claim 16, further comprising:

determining a repetition factor for at least one signal fragment in the list of signal fragments, based at least in part on the signal element referenced by that fragment; and

transmitting the list of signal fragments including a number of duplicate copies of the at least one fragment;

wherein the number of duplicate copies is determined using the repetition factor.

20. The method of claim 16, further comprising:

determining a category into which the data signal falls; and

selecting the set of signal elements from a plurality of dictionaries based upon the determined category.

21. An apparatus for encoding a data signal, comprising:

a memory;

a processor coupled to the memory and configured to execute instructions stored in memory to;

select a plurality of signal elements from a set of signal elements;

for at least one of the selected plurality of signal elements, calculate a projection value as a function of the selected signal element and at least a portion of the data signal; and

generate a plurality of signal fragments, at least one signal fragment including the projection value and a value associating the at least one signal fragment with that one of the plurality of selected signal elements used to generated the projection value.

22. The apparatus of claim 21, wherein the set of signal elements is configured such that the data signal can be approximated from a weighted sum of a subset of the set of signal elements.

23. The apparatus of claim 21, wherein the processor is further configured to calculate the projection value as a scalar product of data signal and the newly selected signal element.

24. The apparatus of claim 21, wherein the processor is further configured to successively generate newly added fragments until the plurality of signal fragments is sufficient to permit reconstruction of the data signal with a level of fidelity that exceeds a threshold.

25. The apparatus of claim 21, wherein at least some of the set of signal elements are derived from a source other than the data signal.