Method and Apparatus for Low Complexity Combinatorial Coding of Signals

• US 20090234642A1
• Filed: 03/13/2008
• Published: 09/17/2009
• Est. Priority Date: 03/13/2008
• Status: Abandoned Application

• Current Assignee: Motorola Mobility LLC (Lenovo Group Ltd.)
• Original Assignee: Motorola, Inc. (Motorola Solutions, Inc.)
• Inventors: Ashley, James P., Mittal, Udar
• Application Number:
  US12/047,632
• Publication Number:
  US 20090234642A1
• Time in Patent Office: Days
• US Class Current: 704/201
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction

Abstract

To reduce the complexity of the encoding/decoding of pulse positions and/or pulse magnitudes associated with complex combinatorial computations, a method and structure for encoding and decoding of pulse position and/or pulse magnitudes requires fewer computations of these combinatorial functions. Approximation of such functions is acceptable as long as certain sufficient properties are maintained. Computational complexity of certain coding and decoding operations may be reduced by two orders of magnitude or more for a given signal vector input.

Claims

1. A method for combinatorial encoding or decoding, the method comprising:

receiving a value n based on positions or magnitudes of a vector;

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

generating F′

(n, d) based on n and d, wherein F′

(n, d) is an approximation of F(n, d) such that F′

(n, d)>

F(n, d) and wherein

2. A method of claim 1, wherein an arithmetic mean is used as the approximation of the geometric mean of the plurality of numbers.

3. A method of claim 2, wherein the plurality of numbers comprises of n, n−

1, n−

2, n−

d+1, the arithmetic mean is given by

4. A method of claim 1, wherein F′

(n, d) is based on an estimate of a logarithm of the approximation of the geometric mean of the plurality of numbers.

5. A method of claim 4, wherein the estimate of the logarithm of the approximation of the geometric mean is based on P′

(2·

n−

d+1).

6. The method of claim 1, wherein generating F′

(n, d) further comprises generating

7. The method of claim 6, wherein generating F′

(n, d) comprises generating F′

(n, d) such that F′

(n, d)≧

F(n, d) and F′

(n, d)≧

F′

(n−

1, d)+F′

(n−

1, d−

1).

8. A method of decoding a vector from a codeword comprising:

receiving a codeword (C);

generating a residual codeword C_k based on the received codeword;

decoding a position p_k or a magnitude derived from p_k based on a non iterative estimate {circumflex over (p)}_k, wherein the non iterative estimate is based on a ratio of log₂(C_k) and k.

9. The method of claim 8, wherein the non iterative estimate {circumflex over (p)}_k is given by an expression

10. A method of claim 8, further comprising:

setting p_k equal to one of {circumflex over (p)}_k−

1, {circumflex over (p)}_k, and {circumflex over (p)}_k+1.

11. A method of claim 8, wherein the expression

12. An apparatus comprising:

a combinatorial function generator that generates function F′

(n, d) having properties F′

(n, d)>

F(n, d) and F′

(n,d)≧

F′

(n−

1,d)+F′

(n−

1,d−

1), wherein F′

(n, d) is used encode/decode a vector X_cc based on an approximation of a geometric mean of a plurality of numbers.

13. The apparatus of claim 12, wherein an arithmetic mean is used as the approximation of the geometric mean of the plurality of numbers.

14. The apparatus of claim 13, wherein the plurality of numbers comprises n, n−

1, n−

2, n−

d+1, the arithmetic mean is given by

15. The apparatus of claim 12, wherein F′

(n, d) is based on an estimate of a logarithm of the approximation of the geometric mean of the plurality of numbers.

16. The apparatus of claim 15, wherein the estimate of the logarithm of the approximation of the geometric mean is based on P′

(2·

n−

d+1).

17. The apparatus of claim 12, wherein function F′

(n, d) is given as;

18. The apparatus of claim 17, further comprising a memory, wherein at least a portion of P′

(2n−

d+1) is fetched from the memory.

19. The apparatus of claim 17, further comprising a memory, wherein k is based on one or more terms stored in the memory.

20. The apparatus of claim 12, further comprising:

a coder that receives F′

(n, d) and vector X_cc and generates a codeword based on the vector X_cc and F′

(n, d).

21. The apparatus of claim 12, further comprising:

a decoder that receives a codeword and generates vector X_cc based on the codeword and F′

(n, d).

22. The apparatus of claim 21, wherein the decoder decodes a position p_k or a magnitude based on p_k based on a non iterative estimate {circumflex over (p)}_k wherein the non iterative estimate is based on a ratio of log₂(C_k) and k.

23. The apparatus of claim 22, wherein the non iterative estimate {circumflex over (p)}_k is given by an expression

24. The apparatus of claim 22, wherein p_k is one of {circumflex over (p)}_k−

1, {circumflex over (p)}_k, and {circumflex over (p)}_k+1.

25. The apparatus of claim 22, wherein the expression