Approximately counting the number of constrained arrays via the sum-product algorithm

摘要

Very often, constrained coding schemes impose nonlinear constraints on arrays and therefore it is usually nontrivial to determine how many arrays satisfy the given constraints. In this paper we show that there are non-trivial constrained coding scenarios where the number of constrained arrays can be estimated to a surprisingly high accuracy with the help of the sum-product algorithm, despite the fact that the underlying factor graphs have many short cycles, and we investigate the reasons why this is the case. These findings open up interesting possibilities for determining the number of constrained arrays also for scenarios where other counting and bounding techniques are not readily available.