Lossless and near-lossless source coding for multiple access networks

• US 20020176494A1
• Filed: 01/30/2002
• Published: 11/28/2002
• Est. Priority Date: 01/30/2001
• Status: Active Grant

• Current Assignee: California Institute of Technology
• Original Assignee: California Institute of Technology
• Inventors: Zhao, Qian, Effros, Michelle
• Granted Patent: US 7,187,804 B2
• Time in Patent Office: Days
• US Class Current: 375/240
• 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/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

Embodiments of the invention present implementations for multiple access source coding (MASC). One embodiment presents an implementation directed at the lossless side-information case of MASC. Another embodiment gives an implementation of the general case MASC. One embodiment is a near-lossless implementation of MASC. In a two dimensional example, the invention provides a way to decode data pairs (x,y) from encoded individual data streams x and y. The present invention provides a solution that partitions the source code into optimal partitions and then finds a matched code that is optimal for the given partition. Embodiments of the present invention use Optimal Shannon, Huffman and Arithmetic Codes for the matched codes. Another embodiment of the present invention gives a method of finding near-lossless multiple access source coding.

Claims

1. A method for encoding and decoding first and second data streams comprising:

encoding said first data stream using a first encoder to produce a first encoded data stream;

encoding said second data stream using a second encoder to produce a second encoded data stream;

providing said first and second encoded data streams to a receiver;

decoding said first and second encoded data streams using a single decoder.

2. The method of claim 1 wherein said encoding and decoding are lossless.

3. The method of claim 1 wherein said encoding and decoding are near-lossless.

4. The method of claim 1 wherein said receiver is provided one of said first and second data stream;

s as side-information.

5. The method of claim 4 wherein encoding of said second stream satisfies a prefix condition and said prefix condition is satisfied for a code γ

_Y for Y given X when for each x∈

X, and each y, y′

∈

A_x, the description of y is not a prefix of the description of y′

.

6. The method of claim 5 wherein said code γ

_Y is a matched code.

7. The method of claim 6 wherein said code γ

_Y is an instantaneous, side-information matched code for p(x, y) when γ

_Y is a matched code for some partition P(Y) for p(x, y) .

8. A method of generating code comprising:

obtaining an alphabet of symbols generated by a data source;

identifying combinable symbols of said alphabet and generating subsets of combinable symbols;

identifying optimal partitions of said subsets of symbols to generate a list of groups;

using said list of groups to generate partitions of the full alphabet.

9. The method of claim 8 further comprising determining a matched code for each partition.

10. The method of claim 8 further comprising selecting a partition whose matched code has a best rate.

11. The method of claim 8 wherein said matched code comprises a Huffman code.

12. The method of claim 8 wherein said matched code comprises an arithmetic code.

13. The method of claim 8 wherein symbols y₁, y₂∈

Y can be combined under p(x, y) if p(x, y₁)p(x, y₂)=0 for each x∈

X.

14. The method of claim 13 wherein for each symbol a set C_y is generated.

15. The method of claim 13 further including the step of identifying all non-empty subsets for each set C_y.

16. The method of claim 8 wherein a partition is complete and nonoverlapping if P(Y)={G₁,G₂, . . . , G_m} satisfies _i=^mG_i=and G_j,G_k=φ

for any j≠

k, where each G_i∈

P(Y) is a group for p(x,y), and G_j∪

G_k and G_j∩

G_k refer to the union and intersection respectively of the members of G_j and G_k.

17. The method of claim 8 wherein said coding scheme is a lossless coding scheme.

18. The method of claim 8 wherein said coding scheme is a near-lossless coding scheme.

19. The method of claim 8 wherein said coding scheme is a side-information, lossless coding scheme.

20. The method of claim 8 wherein said coding scheme is a side-information, near-lossless coding scheme.

21. A method of code for X and Y comprising:

generating a partition pair P(X) and P(Y) such that each partition is a legitimate partition for a side-information, lossless decoding scheme;

identifying said partition pair as a legitimate partition for general lossless decoding if the two descriptions together give enough information to decode X and Y uniquely.

22. The method of claim 21 wherein said partition pair is a legitimate partition pair when for any x, x′

∈

X such that {γ

_X(x), γ

_X(x′

)} does not satisfy the prefix condition, {γ

_Y(y);

y ∈

A_x∪

A_x′

} satisfies the prefix condition.

23. The method of claim 21 wherein said partition pair is a legitimate partition pair when for any y, y′

∈

Y such that {γ

_Y(y), γ

_Y(y′

)} does not satisfy the prefix condition, {γ

_X(x);

x ∈

B_y∪

B_y′

} satisfies the prefix condition.

25. The method of claim 24 further comprising satisfying one of the following conditions;

(A) X∈

T_x or n_y is a leaf implies that Y∈

n_y, and Y∈

T_y or n_x is a leaf implies that X∈

n_x;

(B) X∈

T_x implies that Y∉

n_y;

(C) Y∈

T_y implies that X∉

n_x.

26. The method of claim 25 wherein said instantaneous code is lossless when:

generating code such that for any(x,y)∈

X×

Y with p(x, y)>

0, final nodes (n_x, n_y) are generated that satisfy;

(D)(x,y)∈

n_y×

n_y and for any other x′

∈

n_x and y′

∈

n_y, p(x,y′

)=p(x′

,y)=p(x′

,y′

)=0

28. The method of claim 27 further including determining which of said symbols can have code descriptions for which one symbols'"'"'s code description is a prefix of another symbol'"'"'s code description.

30. The method of claim 29 wherein λ

∈

[0,1].

24. A method for generating a MASC code comprising:

generating instantaneous code by;

generating subtrees T_x and T_y descending from nodes n_x and n_y (including n_x and n_y respectively).

27. A method of generating code comprising:

obtaining an alphabet of symbols generated by a data source

determining which of said symbols can have identical code descriptions and which symbols cannot have identical code descriptions;

29. A method of generating code for data sources X and Y having data rates Rx and Ry respectively, comprising:

generating a code that minimizes λ

R_x+(1−

λ

)R_y for an arbitrary value of λ

.

31. A method for encoding and decoding a plurality of data streams comprising:

encoding said plurality of data streams using a plurality of encoders to produce a plurality of encoded data streams;

providing said plurality of encoded data streams to a receiver;

decoding said plurality of encoded data streams using a single decoder.

32. The method of claim 31 wherein said encoding and decoding are lossless.

33. The method of claim 31 wherein said encoding and decoding are near-lossless.

34. The method of claim 31 wherein said decoding is accomplished using side-information.

36. The method of claim 35 wherein said restrictions include a requirement that symbols be adjacent symbols.

37. The method of claim 35 further including the step of selecting an ordering of said alphabet based on generating code for a plurality of orderings.

38. The method of claim 37 wherein an ordering is selected based on a best rate resulting from one of said orderings.

35. A method of designing codes comprising:

obtaining an alphabet of symbols generated by a data source;

ordering said alphabet of symbols;

identifying restrictions of a class of codes based on said ordering of said alphabet;

designing code for said restricted class for said ordering of said alphabet.