Apparatus and method for low complexity combinatorial coding of signals

• US 8,495,115 B2
• Filed: 08/22/2008
• Issued: 07/23/2013
• Est. Priority Date: 09/12/2006
• Status: Expired due to Fees

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola Mobility LLC (Lenovo Group Ltd.)
• Inventors: Mittal, Udar, Ashley, James P., Cruz-Zeno, Edgardo M.
• Primary Examiner(s): Yaary, Michael D
• Application Number:
  US12/196,414
• Publication Number:
  US 20090024398A1
• Time in Patent Office: 1,796 Days
• Field of Search: None
• US Class Current: 708/200
• 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. 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 logarithmic approximation of a combinatorial function based on n and d;

generating a value F′

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

2. The method of claim 1 wherein Q′

(d) is an approximation of the function

3. The method of claim 1 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), is generated by a summation wherein each quantity in the summation is less than logarithm of numbers from 1 to d.

4. The method of claim 1 wherein the step of producing the value R′

(k) based on K_f further comprises generating;

R′

(k)=└

2<sup>ki−

l</sup>└

2^lK_f┘

┘

.

5. The method of claim 3 wherein the summation is generated as

6. The method of claim 1 wherein the approximation of the function a^k is obtained using a Taylor series expansion method.

7. An apparatus comprising:

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

combinatorial function generator circuitry 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 logarithmic approximation of a combinatorial function based on 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

8. The apparatus of claim 7 wherein Q′

(d) is an approximation of the function

9. The apparatus of claim 7 wherein the combinatorial function generator circuitry generates the value based on Q′

(d), wherein

10. The apparatus of claim 7 wherein F′

(n,d)=R′

(k), where R′

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