APPARATUS AND METHOD FOR LOW COMPLEXITY COMBINATORIAL CODING OF SIGNALS

• US 20090024398A1
• Filed: 08/22/2008
• Published: 01/22/2009
• Est. Priority Date: 09/12/2006
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Ashley, James P., Mittal, Udar, Cruz-Zeno, Edgardo M.
• Granted Patent: US 8,495,115 B2
• Time in Patent Office: Days
• US Class Current: 704/500
• CPC Class Codes: G06F 17/17 Function evaluation by approximation methods, e.g. inter- or extrapolation, smoothing, least mean square method G06F17/18 takes precedence ; interpolation for numerical control G05B19/18
• CPC Class Codes: G10L 19/0212 using orthogonal transformation
• CPC Class Codes: G10L 19/035 Scalar quantisation
• CPC Class Codes: H03M 7/14 Conversion to or from non-weighted codes

Abstract

The invention utilizes low complexity estimates of complex functions to perform combinatorial coding of signal vectors. The invention disregards the accuracy of such functions as long as certain sufficient properties are maintained. The invention in turn may reduce computational complexity of certain coding and decoding operations by two orders of magnitude or more for a given signal vector input.

Claims

1. (canceled)

2. (canceled)

3. (canceled)

4. (canceled)

5. (canceled)

6. (canceled)

7. (canceled)

8. (canceled)

9. (canceled)

10. (canceled)

11. (canceled)

12. A method for combinatorial coding and decoding, the method comprising the steps of:

receiving a vector comprising speech, audio, image, or video;

receiving a value n based on a number of positions in the vector;

receiving a value d based on a number of occupied positions within the vector;

generating a value based on a logarithmic approximation of a combinatorial function of n and d;

generating a value F′

(n, d) based on the logarithmic approximation of the combinatorial function of n and d, such that

13. The method of claim 12 wherein the step of generating the value based on the logarithmic approximation of the combinatorial function of n and d further comprises the step of generating a value Q′

(d), wherein Q′

(d) is an approximation of the function

14. The method of claim 12 wherein the step of generating the value based on the logarithmic approximation of the combinatorial function of n and d further comprises the step of generating a value Q′

(d), wherein

15. The method of claim 12 wherein the step generating of the value F′

(n, d) comprises the step of generating a value F′

(n,d)=R′

(k), where R′

(k) is an approximation of the function a^k, and where a is a logarithm base.

16. The method of claim 15 wherein the step of generating a value F′

(n,d)=R′

(k) further comprises the steps of;

generating an integer component k_i and a fractional component k_f, based on a value k such that k=k_i+k_f;

generating a value K_f, wherein K_f is based on a low resolution Talyor series expansion of 2^kf.

producing the value R′

(k) based on K_f.

17. The method of claim 16 wherein the step of producing the value R′

(k) based on K_f further comprises generating;

R′

(k)=└

2^ki-lK_f┘

┘

.

18. An apparatus comprising:

a vector generator receiving a vector comprising speech, audio, image, or video;

a combinatorial function generator receiving a value n based on a number of positions in the vector, receiving a value d based on a number of occupied positions within the vector, generating a value based on a logarithmic approximation of a combinatorial function of n and d, and generating a value F′

(n, d) based on the logarithmic approximation of the combinatorial function of n and d, such that

19. The apparatus of claim 18 wherein the combinatorial function generator generates the value based on Q′

(d), wherein Q′

(d) is an approximation of the function

20. The apparatus of claim 18 wherein the combinatorial function generator generates the value based on Q′

(d), wherein

21. The apparatus of claim 18 wherein F′

(n,d)=R′

(k), where R′

(k) is an approximation of the function a^k, and where a is a logarithm base.