Files in this item
Files | Description | Format |
---|---|---|
application/pdf ![]() | (no description provided) |
Description
Title: | Combinatorial channels from partially ordered sets |
Author(s): | Cullina, Daniel Francis |
Director of Research: | Kiyavash, Negar |
Doctoral Committee Chair(s): | Kiyavash, Negar |
Doctoral Committee Member(s): | Barg, Alexander; Hajek, Bruce; Milenkovic, Olgica; Srikant, R. |
Department / Program: | Electrical & Computer Eng |
Discipline: | Electrical & Computer Engr |
Degree Granting Institution: | University of Illinois at Urbana-Champaign |
Degree: | Ph.D. |
Genre: | Dissertation |
Subject(s): | coding theory
combinatorics, partially ordered set deletion errors |
Abstract: | A central task of coding theory is the design of schemes to reliably transmit data though space, via communication systems, or through time, via storage systems. Our goal is to identify and exploit structural properties common to a wide variety of coding problems, classical and modern, using the framework of partially ordered sets. We represent adversarial error models as combinatorial channels, form combinatorial channels from posets, identify a structural property of posets that leads to families of channels with the same codes, and bound the size of codes by optimizing over a family of equivalent channels. A large number of previously studied coding problems that fit into this framework. This leads to a new upper bound on the size of s-deletion correcting codes. We use a linear programming framework to obtain sphere-packing upper bounds when there is little underlying symmetry in the coding problem. Finally, we introduce and investigate a strong notion of poset homomorphism: locally bijective cover preserving maps. We look for maps of this type to and from the subsequence partial order on q-ary strings. |
Issue Date: | 2016-11-28 |
Type: | Text |
URI: | http://hdl.handle.net/2142/95346 |
Rights Information: | Copyright 2016 Daniel Cullina |
Date Available in IDEALS: | 2017-03-01 |
Date Deposited: | 2016-12 |
This item appears in the following Collection(s)
-
Dissertations and Theses - Electrical and Computer Engineering
Dissertations and Theses in Electrical and Computer Engineering -
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois