The Capacity of Multidimensional Permutations with Restricted Movement

We study the multidimensional constrained systems of Z^d-permutations with restricted movement. We show a correspondence between these restricted permutations and perfect matchings. We use the theory of perfect matchings to investigate several two-dimensional cases, for which we compute the exact capacity of the constrained system, and prove the existence of a polynomial-time algorithm for counting admissible patterns. We prove that the capacity of Z^d-permutations restricted by a set with full affine dimension depends only on the size of the set. We use this result in order to compute the exact capacity for a class of two-dimensional constrained systems.

I. Introduction

While appearing as early as the works [2], [33], in the last decade the interest in permutations has been reignited in the field of communication [5], [8], [9], [17]–[21], [21], [23], [28], [30], [31], [34], [35], [37]–[41]. This is mainly due to their recent applications in coding for flash memories, and their relevance in various channels.