Analytic combinatorics in several variables is a powerful tool for deriving the asymptotic behavior of combinatorial quantities by analyzing multivariate generating functions. We study information-theoretic questions about sequences in a discrete noiseless channel under cost and forbidden substring constraints. Our main contributions involve the relationship between the graph structure of the channel and the singularities of the bivariate generating function whose coefficients are the number of sequences satisfying the constraints. We combine these new results with methods from multivariate analytic combinatorics to solve questions in many application areas. For example, we determine the optimal coded synthesis rate for DNA data storage when the synthesis supersequence is any periodic string. This follows from a precise characterization of the number of subsequences of an arbitrary periodic strings. Along the way, we provide a new proof of the equivalence of the combinatorial and probabilistic definitions of the cost-constrained capacity, and we show that the cost-constrained channel capacity is determined by a cost-dependent singularity, generalizing Shannon's classical result for unconstrained capacity.
翻译:若干变量的分析性组合分析器是分析多变量生成功能,得出组合数量无症状行为的有力工具。我们研究了关于一个离散无噪音频道在成本和被禁止的子字符串限制下序列的信息理论问题。我们的主要贡献涉及该频道的图形结构与双变量生成功能的奇异性之间的关系,其系数是满足制约的序列数。我们将这些新结果与多种变量解析组合器解决许多应用领域问题的方法结合起来。例如,当合成超级序列为任何定期字符串时,我们确定DNA数据存储的最佳编码合成率。这是根据对任意周期字符串子序列数量的精确描述。接着,我们提供了成本限制能力组合和概率定义等值的新证据,我们表明,成本限制的频道能力是由成本依赖的单一性、对香农的古典结果进行一般分析,以获得不受限制的能力。