Method and apparatus for low complexity combinatorial coding of signals

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 1 , p 2 , . . . , p v and the unoccupied u 1 , u 2 , . . . , u n−v , 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 n−v ,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 n−v ;

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 1 , m 2 , . . . , m v of the plurality of occupied positions;

determining the occupied positions p′ 1 , p′ 2 , . . . , p′ v−1 and the unoccupied positions u′ 1 , u′ 2 , . . . , u′ m−v of the n positions of the vector (x) based upon the plurality of pulse magnitudes m 1 , m 2 , . . . , 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′ m−v ,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′ m−v ;

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 1 , m 2 , . . . , 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

C

μ

=

∑

k

=

1

m

-

v

⁢

F

′

⁡

(

u

k

′

,

k

)

⁢

⁢

0

≤

u

k

′

<

m

-

1

,

where μ′ k belongs to a set U′ defined as U′={0, 1, . . . , m−2}−{p′ 1 , p′ 2 , . . . , p′ v−1 } and

p

k

′

=

∑

j

=

1

k

⁢

m

j

-

1

8. The method of claim 7 , wherein the code C π for the plurality of unoccupied positions is generated in accordance with

C

π

=

∑

k

=

1

n

-

v

⁢

F

′

⁡

(

u

k

,

k

)

⁢

⁢

0

≤

u

k

<

n

9. The method of claim 5 , wherein determining a plurality of non-zero pulse positions p 1 , p 2 , . . . , 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

C

π

=

∑

k

=

1

n

-

v

⁢

F

′

⁡

(

u

k

,

k

)

⁢

⁢

0

≤

u

k

<

n

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 1 , m 2 , . . . , 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

C

μ

=

∑

k

=

1

v

-

1

⁢

F

′

⁡

(

∑

j

=

1

k

⁢

m

j

-

1

,

k

)

⁢

⁢

1

≤

∑

j

=

1

k

⁢

m

j

,

m

k

<

m

;

and

generating the codeword C from at least the code C μ .

11. The method of claim 10 , further comprising:

encoding a plurality of pulse positions p 1 , p 2 , . . . , p v of the plurality of occupied positions to generate code C π in accordance with

C

π

=

∑

k

=

1

v

⁢

F

′

⁡

(

p

k

,

k

)

⁢

⁢

0

≤

p

k

<

n

.

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 1 , p 2 , . . . , p v of the plurality of occupied positions to generate code C π in accordance with

C

π

=

∑

k

=

1

v

⁢

F

′

⁡

(

p

k

,

k

)

⁢

⁢

0

≤

p

k

<

n

.

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 n−v ,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 n−v ;

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 1 , m 2 , . . . , m v of the plurality of occupied positions;

determining the occupied positions p′ 1 , p′ 2 , . . . , p′ v−1 and the unoccupied u′ 1 , u′ 2 , . . . , u′ m−v , of the n positions of the vector (x) based upon the plurality of pulse magnitudes m 1 , m 2 , . . . , 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′ m−v ,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′ m−v ;

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 1 , m 2 , . . . , 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 1 , m 2 , . . . , m v of the plurality of occupied positions to generate the vector (x) in accordance with x p k =m k s 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).