Maximizing the Shannon Capacity of Constrained Systems with Two Constraints
Navin Kashyap · SIAM Journal on Discrete Mathematics · 2003
In this paper, we consider the problem of finding the set $\{A,B\} \subset {0,1} m that maximizes, among all 2-subsets of ${\{0,1\}}^m$, the Shannon capacity, H(A,B), of a constrained system of binary sequences that do not contain A or B as a contiguous subsequence. This problem is motivated by the problem of finding a pair of length-m binary sequences, called markers, that achieves the maximum rate, R(2,m,n), of a (2,m,n) periodic prefix-synchronized (PPS) code. A (2,m,n) PPS code is a binary block code with two length-m markers, A,B, and codewords of length n that inserts A and B alternately at regular intervals in the encoded bitstream, with the additional constraint that A and B may not appear anywhere in the encoded bitstream other than where inserted. We show that for any $m \geq 2$, $\lim_{n \rightarrow \infty} R(2,m,n) = \max\{H(A,B): \{A,B\} \subset {\{0,1\}}^m\} = \log_2\rho_{m-1}$, where $\rho_{m-1}$ is the largest-magnitude zero of the polynomial $z^{m-1} - z^{m-2} - \cdots - 1$. Moreover, we completely characterize the sequences A and B that achieve $\max H(A,B), as well as those that achieve R(2,m,n) for all sufficiently large n.