Формулировка:
Пусть задано количество бит скремблера \(n \in \mathbb{N}\). Тогда существует \(2^n \cdot \left( 2^n – 1 \right)\) скремблеров длины \(n\).
Доказательство:
Ключ скремблера – некоторая последовательность бит длины \(n\). Рассмотрев ключ как вектор из множества \(\{ 0, 1 \} ^n\), можно сделать вывод, что всего существует \(2^n\) ключей длины \(n\). (Это также можно доказать, используя обычное комбинаторное правило произведения: на первую позицию ключа можно поставить два возможных элемента – \(0\) и \(1\), на вторую, \(\ldots\), n-тую – аналогично. По правилу произведения, имеем: \(2 \cdot 2 \cdots 2 = 2^n\))
Регистры сдвига скремблера задают выборку бит из ключа, по которой будет формироваться XOR-сумма. По теореме “О количестве XOR-сумм над заданной последовательностью бит”, таких выборок существует \(2^n-1\).
Далее, по комбинаторному правилу произведения имеем, что количество всевозможных состояний скремблера (которое определяется состояниями ключа и регистров сдвига) равно \(2^n \cdot \left( 2^n – 1 \right)\). Теорема доказана.