Method and apparatus for low complexity combinatorial coding of signals

• US 7,889,103 B2
• Filed: 03/13/2008
• Issued: 02/15/2011
• Est. Priority Date: 03/13/2008
• Status: Active Grant

• Current Assignee: Google Technology Holdings LLC (Alphabet Inc.)
• Original Assignee: Motorola Mobility, Inc. (Lenovo Group Ltd.)
• Inventors: Ashley, James P., Mittal, Udar
• Primary Examiner(s): Nguyen; Linh V
• Application Number:
  US12/047,586
• Publication Number:
  US 20090231169A1
• Time in Patent Office: 1,069 Days
• Field of Search: 341/51, 341/58, 341/59, 341/65, 341/67, 341/106, 341/107, 375/240.12, 375/240.22, 375/240.24, 375/262, 375/295, 382/104, 382/236, 382/253
• US Class Current: 341/107
• 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
• CPC Class Codes: H03M 7/3082 Vector coding for television signals, see H04N19/94

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. Adaptive switching between coding or encoding is performed in accordance with the estimated density of the plurality of occupied positions.

Claims

1. A method for operating an encoder that encodes a codeword (C) from a vector (x), the method comprising:

receiving the vector (x) having n positions to be encoded;

determining an estimated density of a plurality of occupied positions of the n positions of the vector (x); and

adaptively switching between coding of the plurality of occupied positions and coding of a plurality of unoccupied positions of the n positions in accordance with the estimated density of the plurality of occupied positions to generate a coded value.

2. The method of claim 1, wherein determining the estimated density and adaptively switching between coding of the plurality of occupied positions and coding of the plurality of unoccupied positions based upon the estimated density is dynamically performed at a plurality of positions of the n positions of vector (x).

3. The method of claim 2, further comprising:

determining the occupied positions p₁, p₂, . . . , p_v and the unoccupied u₁, u₂, . . . , u<sub>n−

v</sub>, of the n positions of the vector (x);

for the positions p_k of the n positions;

a. if 2·

v>

n encoding a highest unoccupied position as F′

(u<sub>n−

v</sub>,v) but if 2·

v≦

n then encoding the highest unoccupied position as F′

(p_v,v), wherein a last encoded position (ρ

) is set to p_v or u<sub>n−

v</sub>;

b. calculating a number of occupied positions (η

) and a number of unoccupied positions (ε

) which are less than the last encoded position (ρ

);

c. if 2·

η

≦

ρ

then obtaining a maximum occupied position p_k less than ρ and

coding the position as F′

(p_k,η

), wherein the last encoded position is ρ

=p_k;

d. if 2·

η

>

ρ

then obtaining a maximum unoccupied position u_k less than ρ and

coding the position as F′

(u_k,ε

), wherein the last encoded position is ρ

=u_k.

e. repeating b, c, and d until η

or ε

is equal to 0;

summing up the position codes generated in d and e to generate position code C_π

.

4. The method of claim 2, further comprising:

determining a plurality of pulse magnitudes m₁, m₂, . . . , m_v of the plurality of occupied positions;

determining the occupied positions p′

₁, p′

₂, . . . , p′

<sub>v−

1</sub> and the unoccupied positions u′

₁, u′

₂, . . . , u′

<sub>m−

v</sub> of the n positions of the vector (x) based upon the plurality of pulse magnitudes m₁, m₂, . . . , m_v; and

for the positions p′

_k of the n positions;

a. if 2·

(v−

1)>

m−

1 encoding a highest unoccupied position as F′

(u′

<sub>m−

v</sub>,v−

1) but if 2·

(v−

1)≦

m−

1 then encoding the highest unoccupied position as F′

(p′

_v,v−

1), wherein a last encoded position (ρ

′

) is set to p′

_v or u′

<sub>m−

v</sub>;

b. calculating a number of occupied positions (η

′

) and a number of unoccupied positions (ε

′

) which are less than the last encoded position (ρ

′

);

c. if 2·

η

′

≦

ρ

′

then obtaining a maximum occupied position p′

_k less than ρ

′ and

coding the position as F′

(p′

_k,η

′

), wherein the last encoded position is ρ

′

=p′

_k;

d. if 2·

η

′

>

ρ

′

then obtaining a maximum unoccupied position u′

_k less than ρ

′ and

coding the position as F′

(u′

_k,ε

′

), wherein the last encoded position is ρ

′

=u′

_k.

e. repeating b, c, and d until η

′

or ε

′

is equal to 0;

summing up the position codes generated in d and e to generate position code C_μ

.

5. The method of claim 1, wherein the estimated density of a position is determined by a number of the plurality of unoccupied positions vis-à

-vis a number of the plurality of occupied positions and adaptively switching between coding of the plurality of occupied positions and coding of the plurality of unoccupied positions further comprises;

if the number of the plurality of unoccupied positions of the n positions of the vector (x) is less than a threshold, determining values of the plurality of unoccupied positions of the n positions of the vector (x) and generating codeword (c) from the values of the plurality of unoccupied positions, and

otherwise, if the number of the plurality of unoccupied positions of the vector (x) is not less than the threshold, determining values of the plurality of occupied positions and generating codeword (C) from the values of the plurality of occupied positions.

6. The method of claim 5, wherein if the number of the plurality of unoccupied positions of the n positions of the vector (x) is less than the threshold, equal to (m−

1)/2, determining values of the plurality of unoccupied positions further comprises;

determining a plurality of pulse magnitudes m₁, m₂, . . . , m_v of the plurality of occupied positions;

generating a plurality of unoccupied pulse positions u′

_k based on the plurality of pulse magnitudes; and

encoding the plurality of magnitudes when 2·

(v−

1)>

(m−

1) by position encoding of m−

v unoccupied pulse positions located at m−

1 locations to generate a code C_μ

for the plurality of pulse magnitudes.

7. The method of claim 6, wherein encoding the plurality of pulse magnitudes of the plurality of unoccupied positions further comprises:

generating a code C_μ

for the plurality of magnitudes in accordance with

8. The method of claim 7, wherein the code C_π

for the plurality of unoccupied positions is generated in accordance with

9. The method of claim 5, wherein determining a plurality of non-zero pulse positions p₁, p₂, . . . , p_v within the vector x comprises:

selectively encoding the plurality of unoccupied positions to generate a code C_π

for the plurality of unoccupied positions in accordance with

10. The method of claim 5, wherein if the number of the plurality of unoccupied positions of the n positions of the vector (x) is not less than the threshold, equal to (m−

1)/2, determining values of the plurality of occupied positions and generating codeword (C) from the values of the plurality of occupied positions further comprises;

determining a plurality of pulse magnitudes m₁, m₂, . . . , m_v of the plurality of occupied positions when 2·

(v−

1)≦

m−

1 to generate code C_μ

for the pulse magnitudes in accordance with

11. The method of claim 10, further comprising:

encoding a plurality of pulse positions p₁, p₂, . . . , p_v of the plurality of occupied positions to generate code C_π

in accordance with

12. The method of claim 5, wherein if the number of the plurality of unoccupied positions of the n positions of the vector (x) is not less than the threshold, determining values of the plurality of occupied positions and generating codeword (C) from the values of the plurality of occupied positions further comprises:

encoding a plurality of pulse positions p₁, p₂, . . . , p_v of the plurality of occupied positions to generate code C_π

in accordance with

13. An encoder, comprising:

combinatorial coding circuitry operable to perform;

receiving a vector (x) having n positions to be encoded;

determining an estimated density of a plurality of occupied positions of the n positions of the vector (x);

adaptively switching between coding of the plurality of occupied positions and coding of a plurality of unoccupied positions of the n positions in accordance with the estimated density of the plurality of occupied positions to generate a coded value.

14. The encoder of claim 13, wherein the estimated density of a position is determined by a number of the plurality of unoccupied positions vis-à

-vis a number of the plurality of occupied positions and adaptively switching between coding of the plurality of occupied positions and coding of the plurality of unoccupied positions performed by the combinatorial coding circuitry further comprises;

coding the plurality of unoccupied positions when a number of the plurality of unoccupied positions is less than a threshold value; and

coding the plurality of occupied positions when a number of the plurality of unoccupied positions is not less than the threshold.

15. The encoder of claim 13, wherein determining the estimated density and adaptively switching between coding of the plurality of occupied positions and coding of the plurality of unoccupied positions based upon the estimated density is dynamically performed at a plurality of positions of the n positions of vector (x).

16. A method for operating a decoder that generates a vector (x) from a codeword (C), the method comprising:

receiving the codeword (C) representing a signal coded using a sequence of pulses;

determining an estimated density of a plurality of occupied positions of n positions of the vector (x) based on the codeword C; and

adaptively switching between decoding of the plurality of occupied positions and decoding of a plurality of unoccupied positions of the vector x in accordance with the estimated density of the plurality of occupied positions to generate a decoded value.

17. The method of claim 16, wherein determining the estimated density and adaptively switching between decoding of the plurality of occupied positions and decoding of the plurality of unoccupied positions based upon the estimated density is dynamically performed at a plurality of positions of the n positions of vector (x).

18. The method of claim 17, further comprising:

for the positions p_k of the n positions;

a. if 2·

v>

n decoding a highest unoccupied position as F′

(u<sub>n−

v</sub>,v) from code C_π

but if 2·

v≦

n then decoding the highest occupied position as F′

(p_v,v), wherein a last decoded position (ρ

) is set to p_v or u<sub>n−

v</sub>;

b. calculating a number of occupied positions (η

) and a number of unoccupied positions (ε

) which are less than the last decoded position (ρ

);

c. if 2·

η

≦

ρ

then obtaining a maximum occupied position p_k less than ρ and

decoding the position as F′

(p_k,η

), wherein the last decoded position is ρ

=p_k;

d. if 2·

η

>

ρ

then obtaining a maximum unoccupied position u_k less than ρ and

decoding the position as F′

(u_k,ε

), wherein the last decoded position is ρ

=u_k.

e. repeating b, c, and d until η

or ε

is equal to 0;

decoding the plurality of occupied positions from the maximum occupied positions p_k and the maximum unoccupied positions u_k generated in a, b, c, d and e.

19. The method of claim 17, further comprising:

determining a plurality of pulse magnitudes m₁, m₂, . . . , m_v of the plurality of occupied positions;

determining the occupied positions p′

₁, p′

₂, . . . , p′

<sub>v−

1</sub> and the unoccupied u′

₁, u′

₂, . . . , u′

<sub>m−

v</sub>, of the n positions of the vector (x) based upon the plurality of pulse magnitudes m₁, m₂, . . . , m_v; and

for the positions p′

_k of the n positions;

a. if 2·

(v−

1)>

m−

1 decoding a highest unoccupied position as F′

(u′

<sub>m−

v</sub>,v−

1) code C_μ

but if 2·

(v−

1)≦

m−

1 then decoding the highest occupied position as F′

(p′

_v,v−

1), wherein a last decoded position (ρ

′

) is set to p′

_v or u′

<sub>m−

v</sub>;

b. calculating a number of occupied positions (η

′

) and a number of unoccupied positions (ε

′

) which are less than the last decoded position (ρ

′

);

c. if 2·

η

′

≦

ρ

′

then obtaining a maximum occupied position p′

_k less than ρ

′ and

decoding the position as F′

(p′

_k,η

′

), wherein the last decoded position is ρ

′

=p′

_k;

d. if 2·

η

′

>

ρ

′

then obtaining a maximum unoccupied position u′

_k less than ρ

′ and

decoding the position as F′

(u′

_k,ε

′

), wherein the last decoded position is ρ

′

=u′

_k.

e. repeating b, c, and d until η

′

or ε

′

is equal to 0;

decoding the plurality of occupied positions from the maximum occupied positions p_k and the maximum unoccupied positions u_k generated in a, b, c, d and e.

20. The method of claim 16, wherein the estimated density of a position is determined by a number of the plurality of unoccupied positions vis-à

-vis the number of the plurality of occupied positions and adaptively switching between decoding of the plurality of occupied positions and decoding of the plurality of unoccupied positions further comprises;

if the number of the plurality of unoccupied positions of the n positions of the vector (x) is less than a threshold, decoding the plurality of unoccupied positions of the n positions of the vector (x) and decoding the plurality of occupied positions based upon the decoded plurality of unoccupied positions;

generating a plurality of decoded occupied position values from the plurality of unoccupied positions and generating vector (x) from the plurality of decoded unoccupied and decoded occupied position values, and

otherwise, if the number of the plurality of unoccupied positions of the vector (x) is not less than the threshold, decoding the plurality of occupied positions.

21. The method of claim 20, wherein if the number of the plurality of unoccupied positions of the n positions of the vector (x) is less than the threshold, further comprising:

decoding a plurality of unoccupied pulse positions u′

_k;

decoding a plurality of pulse magnitudes m₁, m₂, . . . , m_v of the plurality of occupied positions from the extracted code C_μ

and the plurality of decoded unoccupied pulse positions u′

_k; and

decoding the codeword (C) using the decoded plurality of pulse magnitudes m₁, m₂, . . . , m_v of the plurality of occupied positions to generate the vector (x) in accordance with x_pk=m_ks_k.

22. The method of claim 20, wherein if the number of the plurality of unoccupied positions of the n positions of the vector (x) is less than the threshold, further comprising:

decoding a plurality of unoccupied pulse positions u_k;

generating a plurality of decoded occupied pulse positions from the plurality of decoded unoccupied pulse positions u_k;

decoding the codeword (C) using the decoded unoccupied pulse positions and the decoded occupied pulse positions to generate the vector (x).

23. A decoder comprising:

combinatorial decoding circuitry operable to perform;

receiving the codeword (C) representing a signal coded using a sequence of pulses;

determining an estimated density of a plurality of occupied positions of n positions of the vector (x) based on the codeword C; and

adaptively switching between decoding of the plurality of occupied positions and decoding of a plurality of unoccupied positions of the vector x in accordance with the estimated density of the plurality of occupied positions to generate a decoded value.

24. The decoder of claim 23, wherein the estimated density of a position is determined by a number of the plurality of unoccupied positions vis-à

-vis the number of the plurality of occupied positions and adaptively switching between decoding of the plurality of occupied positions and decoding of the plurality of unoccupied positions performed by the combinatorial decoding circuitry further comprises;

decoding the plurality of unoccupied positions to generate a plurality of decoded unoccupied positions and generating a plurality of decoded occupied positions from the plurality of decoded unoccupied positions when the number of the plurality of unoccupied positions is less than a threshold value; and

decoding the plurality of occupied positions when the number of the plurality of unoccupied positions is not less than the threshold.

25. The decoder of claim 23, wherein determining the estimated density and adaptively switching between decoding of the plurality of occupied positions and decoding of the plurality of unoccupied positions based upon the estimated density is dynamically performed at a plurality of positions of the n positions of vector (x).