we study algorithmic approaches for rate-fidelity optimal packetization of a single and multiple scalable source code streams with uneven erasure protection (UEP). A new algorithm is developed to obtain the globally optimal solution for scalable source codes of convex rate-fidelity function and for a wide class of erasure channels, including channels for which the probability of losing packets is monotonically nonincreasing in , and independent erasure channels with packet erasure rate smaller than 0.5. This is achieved at linear space complexity and near-linear time complexity in the transmission budget, representing significant improvement over the known globally optimal algorithm. When applied to SPIHT compressed images, the results of the proposed algorithm are virtually the same as the global optima. The above success is also extended to UEP packetization of multiple scalable code streams. We improve the existing algorithms in both speed and performance.

A new algorithm is presented for rate-fidelity optimal packetization of scalable source bit streams with uneven erasure protection. It provides the globally optimal solution for input sources of convex rate-fidelity function and for a wide class of erasure channels, including channels for which the probability of losing n packets is monotonically decreasing in n, and independent erasure channels with packet erasure rate smaller than 0.5. The time and space complexities of the new algorithm are both O(NL), where N is the number of packets and L is the packet payload size, comparing to the O(NL2) time and space complexities of the existing globally optimal solution. When applied to SPIHT compressed images, the results of the proposed algorithm are virtually the same as the globally optima

In this paper, we consider the problem of length-constrained maximum a posteriori decoding of a Markov sequence that is variable-length encoded and transmitted over a binary symmetric channel. We convert this problem into one of a maximum-weight k-link path in a weighted directed acyclic graph. The induced graph-optimization problem can be solved by a fast parameterized search algorithm that finds either the optimal solution with high probability, or a good approximate solution otherwise. The proposed algorithm has lower complexity and superior performance than the previous approximation algorithms

The problem of maximum a posterior probability (MAP) decoding of a Markov sequence that is variable length coded and transmitted over a binary symmetric channel (BSC) is considered. The number of source symbols in the sequence, if made known to the decoder, can improve MAP decoding performance. But adding a sequence length constraint to MAP decoding problem increases its complexity and also converts the length-constrained MAP decoding problem into one of maximum-weight k-link path in a weighted directed acyclic graph. The corresponding graph optimization problem can be solved by a fast parameterized search algorithm that finds either the exact solution with high probability or a good approximate solution otherwise. The proposed algorithm has lower complexity and superior performance than the previous heuristic algorithms.

We consider the problem of length-constrained maximum a posteriori (MAP) decoding of a Markov sequence that is variable length encoded and transmitted over a binary symmetric channel. We convert this problem into one of maximum-weight k-link path in a weighted directed acyclic graph. The induced graph optimization problem can be solved by a fast parameterized search algorithm that finds either the optimal solution with high probability or a good approximate solution otherwise. The proposed algorithm has lower complexity and superior performance than previous heuristic algorithms.

In this correspondence, we study algorithmic approach to solving the problem of maximum a posteriori (MAP) estimation of Markov sequences transmitted over noisy channels, which is also known as the MAP decoding problem. For the class of memoryless binary channels that produce independent substitution and erasure errors, the MAP sequence estimation problem can be formulated and solved as one of the longest path in a weighted directed acyclic graph. But for algorithm efficiency, we transform the graph problem to one of matrix search. If the underlying matrix is totally monotone, then the complexity of MAP sequence estimation can be greatly reduced. We give a sufficient condition for the matrix induced by MAP sequence estimation to be totally monotone, which is indeed the case if the input sequence is Gaussian Markov. Under this condition, the complexity of MAP decoding can be reduced from O(N/sup 2/M) to O(NM), where N is the size of source alphabet and M is the length of input sequence. Furthermore, for Markov sequences of fixed-length code we propose a block parsing strategy to reduce the complexity of MAP sequence estimation to O(M+N/sup 2/M/logM) or to O(M+NM/logM), depending on if the total monotonicity holds. Another significance of this correspondence lies in the applicability of the presented algorithmic approach, which has been thoroughly studied in computer science literature, to many other discrete optimization problems encountered in both source and channel coding, ranging from optimal multiresolution and multiple-description quantizer design, to context quantization for minimum conditional entropy, and to optimal packetization with uneven error protection.

In this paper, we present a family of new algorithms for rate-fidelity optimal packetization of scalable source bit streams 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 obtained O(N/sup 3/L/sup 2/) complexity, where N is the number of packets and L is the packet payload size. If the rate-fidelity function of the input is convex, the time complexity can be reduced to O(NL/sup 2/) for a class of erasure channels, including channels for which the probability function of losing n packets is monotonically decreasing in n and independent erasure channels with packet erasure rate no larger than N/2(N + 1). Furthermore, our O(NL/sup 2/) algorithm for the convex case can be modified to rind an approximation solution for the general case. All of our algorithms do away with the expediency of fractional bit allocation, a limitation of some existing algorithms.

We propose a soft decision decoding algorithm for a variable-length encoded Markov source transmitted via a noisy channel that has all three types of errors - substitution, deletion, and insertion. The decoder aims to find a sequence, X, that maximizes the posterior probability, given a received sequence, Y. First, we assume the channel is a binary symmetric channel (BSC), and the input of the channel is a first order Markov source. We convert the MAP (maximum a posteriori) problem to one of finding a single-source longest path in a directed acyclic graph, which can be solved by dynamic programming. We also present a generalization of the BSC to include both insertion and deletion errors, and the development of a soft decision MAP decoding algorithm for this more challenging case, which is our main contribution.

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.