Back to search

University of British Columbia

Capacity of multidimensional constrained channels : estimates and exact computations

Abstract

dc:description

This work considers channels for which the input is constrained to be from a given set of D-dimensional arrays over a finite alphabet. Such a set is called a constraint. An encoder for such a channel transforms arbitrary arrays over the alphabet into constrained arrays in a decipherable manner. The rate of the encoder is the ratio of the size of its input to the size of its output. The capacity of the channel or constraint is the highest achievable rate of any encoder for the channel. We compute the exact capacity of two families of multidimensional constraints. We also generalize a known method for obtaining lower bounds on the capacity, for a certain class of 2-dimensional constraints, and improve the best known bounds for a few constraints of this class. Given a binary D-dimensional constraint, a D-dimensional array with entries in {0,1,⃞} is called "valid", for the purpose of this abstract, if any "filling" of the '⃞'s in the array with '0's and '1's, independently, results in an array that belongs to the constraint. The density of '*'s in the array is called the insertion rate. The largest achievable insertion rate in arbitrary large arrays is called the maximum insertion rate. An unconstrained encoder for a given insertion rate transforms arbitrary binary arrays into valid arrays having the specified insertion rate. The tradeoff function essentially specifies for a given insertion rate the maximum rate of an unconstrained encoder for that insertion rate. We determine the tradeoff function for a certain family of 1-dimensional constraints. Given a 1-dimensional constraint, one can consider the D-dimensional constraint formed by collecting all the D-dimensional arrays for which the original 1-dimensional constraint is satisfied on every "row" in every "direction". The sequence of capacities of these D-dimensional generalizations has a limit as D approaches infinity, sometimes called the infinite-dimensional capacity. We partially answer a question of [37], by proving that for a large class of 1-dimensional constraints with maximum insertion rate 0, the infinite dimensional capacity equals 0 as well.

Degree

thesis:*
Name thesis:degree_name
Doctor of Philosophy - PhD
Level thesis:degree_level
doctoral
Discipline thesis:degree_discipline
Mathematics
Grantor dc:publisher
University of British Columbia
Year dc:date
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Louidor, Erez

Rights

dc:rights
Statement dc:rights
  • Attribution-NonCommercial-NoDerivs 3.0 Unported
Language dc:language
eng

Identifiers

dc:identifier.*
Handle dc:identifier
http://hdl.handle.net/2429/24888

Chain of custody

source
Harvested from
University of British Columbia
Base URL
circle.library.ubc.ca/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
related terms
citation

Louidor, Erez. Capacity of multidimensional constrained channels : estimates and exact computations. doctoral thesis, University of British Columbia, 2010. http://hdl.handle.net/2429/24888