Linear ordered codes, shape enumarators and parallel channels
Woomyoung Park, Alexander Barg · 2010
We consider linear codes in Hamming-like metric spaces with the metric derived from a partial order of coordinates of codewords. In the first part of the paper we examine a matroid-theoretic perspective of linear ordered codes. We define the (multivariate) Tutte polynomial of a linear code and prove an extension of the Greene theorem for an ordered metric. We further relate the Tutte polynomial to the distribution of higher weights (shapes) of linear ordered codes, and find this distribution for ordered MDS codes. We also observe that ordered MDS codes represent uniform poset matroids. The ordered metric is known to describe the noise process in a wireless fading system studied by S. Tavildar and P. Viswanath (2006). We define a probabilistic model of the channel in the system which can be represented by a set of dependent parallel symmetric channels. We show that linear ordered codes achieve capacity of this channel. As an application of these results, we show that linear ordered codes attain secrecy capacity of parallel wiretap channels that extend Wyner's wire-tap channel I model. Likewise, the Ozarow-Wyner wire-tap channel II is naturally linked to generalized poset weights of linear codes.