Globally optimal uneven error-protected packetization of scalable code streams

Abstract

In this extended abstract we present a family of new algorithms for rate-fidelity optimal packetization of scalable source bit stream with uneven error protection. In the most general setting where no assumption is made on the probability function of packet loss or on the rate-fidelity function of the scalable code stream, one of our algorithms can find the globally optimal solution to the problem in O(N/sup 2/L/sup 2/) time, compared to a previously claimed O(N/sup 3/L/sup 2/) complexity, where N is the number of packets and L is the packet payload size. The time complexity can be reduced to O(NL/sup 2/) if the rate-fidelity function of the input is convex and under the reasonable assumption that the probability function of packet loss is monotonically decreasing. In the convex case the algorithm of Mohr et al. (2000) has complexity O(N/sup 2/L log N). Furthermore, our O(NL/sup 2/) algorithm for the convex case can be modified to find an approximation solution for the general case that is better than the results of other algorithms in the prior literature. All of our algorithms do away with the expediency of fractional redundancy allocation, a limitation of some existing algorithms. To our best knowledge this work offers for the first time globally optimal solutions to the important problem of optimal UEP packetization.