Event
PhD Dissertation Defense: Woomyoung Park
Friday, November 9, 2012
3:00 p.m.
Room 2328, AV Williams Bldg
Maria Hoo
301 405 3681
mch@umd.edu
ANNOUNCEMENT: PhD Dissertation Defense
Name: Woomyoung Park
Committee:
Professor Alexander Barg, Chair/Advisor
Professor Prakash Narayan
Professor Adrian Papamarcou
Professor Sennur Ulukus
Professor Leonid Koralov, Dean's Representative
Date/Time: Friday, November 9, 2012 at 3 PM
Location: Room 2328, AV Williams Building
Title: Applications of ordered weights in information transmission
This dissertation is devoted to a study of a class of linear codes related to a particular metric space that generalizes the Hamming space in that the metric function is defined by a partial order on the set of coordinates of the vector.
We begin with developing combinatorial and linear-algebraic aspects of linear ordered codes. In particular, we define multivariate rank enumerators for linear codes and show that they form a natural set of invariants in the study of the duality of linear codes. The rank enumerators are further shown to be connected to the shape distributions of linear codes, and enable us to give a simple proof of a MacWilliams-like theorem for the ordered case. We also pursue the connection between linear codes and matroids in the ordered case and show that the rank enumerator can be thought of as an
instance of the classical matroid invariant called the Tutte polynomial. Finally, we consider the distribution of support weights of ordered codes and its expression via the rank enumerator. Altogether, these results generalize a group of well-known results for codes in the Hamming space to the ordered case.
Extending the research in the first part, we define simple probabilistic channel models that are in a certain sense matched to the ordered distance, and prove several results related to performance of linear codes on such channels. In particular, we define ordered wire-tap channels and establish several results related to the use of linear codes for reliable and secure transmission in such channel models.
In the third part of this dissertation we study polar coding schemes for channels with nonbinary input alphabets. We construct a family of linear codes that achieve the capacity of a nonbinary symmetric discrete memoryless channel with input alphabet of size q=2^r, r=2,3,.... A new feature of the coding scheme that arises in the nonbinary case is related to the emergence of several extremal configurations for the polarized data symbols. We establish monotonicity properties of the configurations and use them to show that total transmission rate approaches the symmetric capacity of the channel. We develop these results to include the case of ``controlled polarization'' under which the data symbols polarize to any pre-defined set of extremal configurations. We also outline an application of this construction to data encoding in video sequences of the MPEG-2 and H.264/MPEG-4 standards.
