 Library Home /
 Search Collections /
 Open Collections /
 Browse Collections /
 UBC Theses and Dissertations /
 Capacity of multidimensional constrained channels :...
Open Collections
UBC Theses and Dissertations
UBC Theses and Dissertations
Capacity of multidimensional constrained channels : estimates and exact computations Louidor, Erez
Abstract
This work considers channels for which the input is constrained to be from a given set of Ddimensional 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 2dimensional constraints, and improve the best known bounds for a few constraints of this class. Given a binary Ddimensional constraint, a Ddimensional 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 1dimensional constraints. Given a 1dimensional constraint, one can consider the Ddimensional constraint formed by collecting all the Ddimensional arrays for which the original 1dimensional constraint is satisfied on every "row" in every "direction". The sequence of capacities of these Ddimensional generalizations has a limit as D approaches infinity, sometimes called the infinitedimensional capacity. We partially answer a question of [37], by proving that for a large class of 1dimensional constraints with maximum insertion rate 0, the infinite dimensional capacity equals 0 as well.
Item Metadata
Title 
Capacity of multidimensional constrained channels : estimates and exact computations

Creator  
Publisher 
University of British Columbia

Date Issued 
2010

Description 
This work considers channels for which the input is constrained to be from a given set of Ddimensional 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 2dimensional constraints, and improve the best known bounds for a few constraints of this class.
Given a binary Ddimensional constraint, a Ddimensional 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 1dimensional constraints.
Given a 1dimensional constraint, one can consider the Ddimensional constraint formed by collecting all the Ddimensional arrays for which the original 1dimensional constraint is satisfied on every "row" in every "direction". The sequence of capacities of these Ddimensional generalizations has a limit as D approaches infinity, sometimes called the infinitedimensional capacity. We partially answer a question of [37], by proving that for a large class of 1dimensional constraints with maximum insertion rate 0, the infinite dimensional capacity equals 0 as well.

Genre  
Type  
Language 
eng

Date Available 
20100521

Provider 
Vancouver : University of British Columbia Library

Rights 
AttributionNonCommercialNoDerivs 3.0 Unported

DOI 
10.14288/1.0069991

URI  
Degree  
Program  
Affiliation  
Degree Grantor 
University of British Columbia

Graduation Date 
201011

Campus  
Scholarly Level 
Graduate

Rights URI  
Aggregated Source Repository 
DSpace

Item Media
Item Citations and Data
Rights
AttributionNonCommercialNoDerivs 3.0 Unported