2) Дискретный канал с помехами

Дискретный канал с помехами характеризуется условными вероятностями P(y_j/x_i) того, что будет принят сигнал y_j, если передан x_i, т.е. матрицей

(6.12)

при отсутствии помех все P(y_j/x_i) при j # i равны 0 и при j = i равны 1.

Среднее количество информации на символ, получаемое при приёме одного элементарного сигнала равно: I(Y,X) = H(Y) – H(Y/X). (6.13)

В случае независимости отдельных символов сигнала энтропия на выходе линии

(6.14)

предполагается, что число букв алфавита Y = (y₁, y₂, …, y_m) равно числу букв алфавита X = (x₁, x₂, …, x_m) и равно, следовательно, m.

Средняя условная энтропия:

. (6.15)

Пропускная способность канала высчитывается по формуле

C = V_ max I(Y,X) , (6.16)

где максимум определяется по всем возможным распределениям вероятностей, характеризующим источник сигналов

В этом случае алфавит X и алфавит Y состоит из двух символов:

X = (x₁, x₂), Y = (y₁, y₂).

Диаграмма (рис. 6.4) показывает возможные варианты передачи и соответствующие им вероятности.

Канал такого типа носит название симметричного

Средняя условная энтропия:

(6.18)

Отсюда видно, что не зависит от характеристик

источника, т.е. от P(x₁) и P(x₂), и определяется только

помехами в канале передачи.

Максимальное количество информации на один символ

получается при таком распределении вероятностей P(x_i), при котором оказывается максимальным член H(Y). Но H(Y) не может превосходить величины что достигается при P(x₁) = P(x₂) 1/2. Поэтому имеем max (I(Y,X)) = 1 + PlogP + (1-P) log(1-P)

и, следовательно, пропускная способность: C = V_ max(I(Y,X)) = V_ [1+ PlogP + (1-P) log(1-P)]. (6.19)

Отсюда следует: в частности, что при Р = 0, т.е. при отсутствии шумов в канале связи, имеем

Cmax =V_.

При P = 1 также имеем детерминированный случай, когда сигналы x₁ превращаются в сигналы x₂ и наоборот с вероятностью, равной единице. При этом пропускная способность канала также максимальная:Cmax = V_.

Минимальное значение пропускная способность имеет при P1/2.

В этом случае независимо от полученных сигналов ничего нельзя сказать о том, какой сигнал был послан: имеет место такая ситуация, как если бы в линию связи вообще не посылались сигналы. Тогда, естественно, пропускная способность Cmin = 0.

Дискретный канал без помех

В любом реальном канале всегда присутствуют помехи. Однако если их уровень настолько мал, что вероятность искажения практически равна нулю, можно считать, что все сигналы передаются не искажёнными. В этом случае среднее количество информации, переносимое одним символом, определяется по формуле I(Y,X) = I(X,Y) = H(X), (6.6)

а максимальное значение (6.7)

где H_m(X) – максимальная энтропия источника сигналов, получающаяся при равномерном распределении вероятностей символов алфавита источника P(X₁)=P(X₂)=… = P(X_m) = 1/m. (6.8)

Но максимальная энтропия выражается в единицах информации на символ сигнала, как

. (6.9)

Следовательно, пропускная способность дискретного канала без помех в единицах информации за единицу времени равна (6.10)

Шенноном сформулирована основная теорема о кодировании, которая утверждает, что если источник информации имеет энтропию H(Z) единиц информации на символ сообщения, а канал связи обладает пропускной способностью С единиц информации в единицу времени, то:

1) сообщения, вырабатываемые источником, всегда можно закодировать так, чтобы скорость Vz их передачи была сколь угодно близкой к (6.11)

где измеряется в символах сообщения за единицу времени;

2) не существует метода кодирования, позволяющего сделать эту скорость больше чем

Согласно сформулированной теореме существует метод кодирования, позволяющий при и передавать всю информацию, вырабатываемую источником, а при такого метода не существует, где – поток информации.

3) 1) Определим энтропию ансамбля X и У

точные количества условных энтропий H(yj/xi)

и

объединенные

2) Условные энтропии ансамблей и

4) Полиграммная замена формируется из одного алфавита с помощью специальных правил. В качестве примера рассмотрим шифр Плэйфера [12].

В этом шифре алфавит располагается в матрице. Открытый текст разбивается на пары символов Каждая пара символов открытого текста заменяется на пару символов из матрицы следующим образом:

• если символы находятся в одной строке, то каждый из символов пары заменяется на стоящий правее его (за последним символом в строке следует первый);

• если символы находятся в одном столбце, то каждый символ пары заменяется на символ расположенный ниже его в столбце (за последним нижним символом следует верхний);

• если символы пары находятся в разных строках и столбцах, то они считаются противоположными углами прямоугольника. Символ, находящийся в левом углу заменяется на символ, стоящий в другом левом углу. Замена символа, находящегося в правом углу осуществляется аналогично;

• если в открытом тексте встречаются два одинаковых символа подряд, то перед шифрованием между ними вставляется специальный символ (например, тире).

Пример 9.8. Открытый текст «ШИФР ПЛЭЙФЕРА» Матрица алфавита представлена в таблице 9.6

Таблица 9.8 - Матрица алфавита шифра Плэйфера

А	Ж	Б	м	ц	в
Ч	Г	Н	ш	Д	0
Е	Щ	,	X	У	п
.	3	ъ	р	и	й
С	ь	к	э	т	л
Ю	я	□	ы	ф	–

Шифртекст «РДЫИ,-СТ-И. ХЧС».

Технология шифрования с помощью подстановки, например использование шифра Цезаря и прогрессивного ключа шифрования Тритемиуса, широко используется в головоломках. Такие простые подстановочные шифры дают малую защищенность. Чтобы к подстановочной технологии можно было применить концепцию смещения, требуется более сложное соотношение. Смещение – это подстановки, которые делают взаимосвязь между ключом и шифрованным текстом как можно более сложной. На рисунке 9.4 изображен пример создания большей подстановочной сложности с помощью использования нелинейного преобразования. В общем случае n входных битов сначала представляются как один из 2ⁿ различных символов (на приведенном рисунке n=3). Затем множество из 2ⁿ символов перемешивается так, чтобы каждый символ заменялся другим символом множества. После этого символ снова превращается в n-битовый.

Можно легко показать, что существует (2ⁿ)! Различные подстановки или связанные с ними возможные модели. Задача криптоаналитика становится вычислительно невозможной для больших n. Пусть n=128, тогда 2ⁿ=10³⁸ и (2ⁿ)! представляет собой астрономическое число. Видим, что для n=128 это преобразование с помощью блока подстановки (substitution block, S-блок) является сложным (запутывающим). Впрочем, хотя S-блок с n=128 можно считать идеальным, его реализация является невозможной, поскольку она потребует блока с 2ⁿ = 10³⁸ контактами.

Вход	000	001	010	011	100	101	110	111
Выход	011	111	000	110	010	100	101	001

Рисунок 9.4 – Блок подстановки

Чтобы убедиться, что S-блок, приведенный на рисунке 9.4, представляет собой нелинейное преобразование, достаточно использовать теорему о суперпозиции, которая формулируется ниже. Предположим, что

(9.1)

где a и b – входные элементы, С и С’ – выходные элементы, а Т - преобразование. Тогда если T линейно, С=С’ для всех входных элементов, а если Т нелинейно,

Предположим, а=001 и b=010; тогда, используя преобразование Т, показанное на рисунке 9.4, получим следующее:

Здесь символ обозначает сложение по модулю 2. Поскольку , S – блок является нелинейным.