Back to search

McMaster University

Sequential Scalar Quantization of Two Dimensional Vectors in Polar and Cartesian Coordinates

Abstract

dc:description.abstract

This thesis addresses the design of quantizers for two-dimensional vectors, where the scalar components are quantized sequentially. Specifically, design algorithms for unrestricted polar quantizers (UPQ) and successively refinable UPQs (SRUPQ) for vectors in polar coordinates are proposed. Additionally, algorithms for the design of sequential scalar quantizers (SSQ) for vectors with correlated components in Cartesian coordinates are devised. Both the entropy-constrained (EC) and fixed-rate (FR) cases are investigated. The proposed UPQ and SRUPQ design algorithms are developed for continuous bivariate sources with circularly symmetric densities. They are globally optimal for the class of UPQs/SRUPQs with magnitude thresholds confined to a finite set. The time complexity for the UPQ design is O(K2 + KPmax) in the EC case, respectively O(KN2) in the FR case, where $K$ is the size of the set from which the magnitude thresholds are selected, Pmax is an upper bound for the number of phase levels corresponding to a magnitude bin, and $N$ is the total number of quantization bins. The time complexity of the SRUPQ design is O(K3Pmax) in the EC case, respectively O(K2N'2Pmax) in the FR case, where $N'$ denotes the ratio between the number of bins of the fine UPQ and the coarse UPQ. The SSQ design is considered for finite-alphabet correlated sources. The proposed algorithms are globally optimal for the class of SSQs with convex cells, i.e, where each quantizer cell is the intersection of the source alphabet with an interval of the real line. The time complexity for both EC and FR cases amounts to O(K12K22), where K1 and K2 are the respective sizes of the two source alphabets. It is also proved that, by applying the proposed SSQ algorithms to finite, uniform discretizations of correlated sources with continuous joint probability density function, the performance approaches that of the optimal SSQs with convex cells for the original sources as the accuracy of the discretization increases. The proposed algorithms generally rely on solving the minimum-weight path (MWP) problem in the EC case, respectively the length-constrained MWP problem or a related problem in the FR case, in a weighted directed acyclic graph (WDAG) specific to each problem. Additional computations are needed in order to evaluate the edge weights in this WDAG. In particular, in the EC-SRUPQ case, this additional work includes solving the MWP problem between multiple node pairs in some other WDAG. In the EC-SSQ (respectively, FR-SSQ) case, the additional computations consist of solving the MWP (respectively, length-constrained MWP) problem for a series of other WDAGs.

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
  • WU, HUIHUI
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

WU, HUIHUI. Sequential Scalar Quantization of Two Dimensional Vectors in Polar and Cartesian Coordinates. 2018. http://hdl.handle.net/11375/23428