Back to search

McMaster University

Graph-Based Solution for Two Scalar Quantization Problems in Network Systems

Abstract

dc:description.abstract

This thesis addresses the optimal scalar quantizer design for two problems, i.e. the two-stage Wyner-Ziv coding problem and the multiple description coding problem for finite-alphabet sources. The optimization problems are formulated as the minimization of a weighted sum of distortions and rates. The proposed solutions are globally optimal when the cells in each partition are contiguous. The solution algorithms are both based on solving the single-source or the all-pairs minimum-weight path (MWP) problems in certain weighted directed acyclic graphs (WDAG). When the conventional dynamic programming technique is used to solve the underlying MWP problems the time complexity achieved is O(N3) for both problems, where $N$ is the size of the source alphabet. We first present the optimal design of a two-stage Wyner-Ziv scalar quantizer with forwardly or reversely degraded side information (SI) {for finite-alphabet sources and SI}. We assume that binning is performed optimally and address the design of the quantizer partitions. A solution based on dynamic programming is proposed with O(N3) time complexity. %The solution relies on finding the single-source or the all-pairs MWP in several one dimensional WDAGs. Further, a so-called {\it partial Monge property} is additionally introduced and a faster solution algorithm exploiting this property is proposed. Experimental results assess the practical performance of the proposed scheme. Then we present the optimal design of an improved modified multiple-description scalar quantizer (MMDSQ). The improvement is achieved by optimizing all the scalar quantizers. %are optimized under the assumption that all the central and side quantizers have contiguous codecells. The optimization is based on solving the single-source MWP problem in a coupled quantizer graph and the all-pairs MWP problem in a WDAG. Another variant design with the same optimization but enhanced with a better decoding process is also presented to decrease the gap to theoretical bounds. Both designs for the second problem have close or even better performances than the literature as shown in experiments.

Degree

thesis:*
Department dc:contributor.department
Electrical and Computer Engineering
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Zheng, Qixue
Advisor dc:contributor.advisor
  • Dumitrescu, Sorina

Subjects

dc:subject × 2

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Zheng, Qixue. Graph-Based Solution for Two Scalar Quantization Problems in Network Systems. 2018. http://hdl.handle.net/11375/23972