  The vast existing wireless infrastructure features a variety of systems and
standards. It is of significant practical value to introduce new features and
devices without changing the physical layer/hardware infrastructure, but
upgrade it only in software. A way to achieve it is to apply protocol coding:
encode information in the actions taken by a certain (existing) communication
protocol. In this work we investigate strategies for protocol coding via
combinatorial ordering of the labelled user resources (packets, channels) in an
existing, primary system. Such a protocol coding introduces a new secondary
communication channel in the existing system, which has been considered in the
prior work exclusively in a steganographic context. Instead, we focus on the
use of secondary channel for reliable communication with newly introduced
secondary devices, that are low-complexity versions of the primary devices,
capable only to decode the robustly encoded header information in the primary
signals. We introduce a suitable communication model, capable to capture the
constraints that the primary system operation puts on protocol coding. We have
derived the capacity of the secondary channel under arbitrary error models. The
insights from the information-theoretic analysis are used in Part II of this
work to design practical error-correcting mechanisms for secondary channels
with protocol coding.
