Теоретические основы информатики - Аветисян Р.Д.
Скачать (прямая ссылка):
оказывается меньше H[л:], т.е. значение выходного символа оказывается недостаточным для внесения полной ясности в вопрос о том, каким именно является входной символ. Это означает, что с просмотром каждого очередного выходного символа адресат получает о входном символе информацию, количественно равную не Н[х], как это имело место при идеальном канале (или идеальном инверторе), а /[л\ у] < H|х].
Значение Н[х] зависит только от параметра м - вероятностной характеристики входной последовательности. При заданном значении (u величина /[.v, у] зависит также от пары значений А, и X2 - вероятностных характеристик собственно канала. Так. из (3.29) следует, что
/[a, vl= /[.v. л],
т.е. с учетом (3.28) и (3.23) имеем:
/[л, у\ = -Х Iog2 X - (1 - X) Iog2 (1 - X) - Н[у / .Y1. (3.33)
Из (3.25) следует, что Н[у/х] зависит только от параметров A1A2 и (u, т.е. достаточно подставить в (3.33) значение X = 1 - X2 + OJiXl + + X2-I) (см. (3.18)), чтобы получить зависимость /|д, у] от параметров A1. X1 и <лг.
/LxjyJ = Z7(A11A2lM). (3.34)
Кроме двух идеальных случаев, когда имеют место (3.30) или (3.31) и поэтому /|.v, у] = Н[х], во всех остальных случаях значение /[л, у] оказывается меньше значения //[х].
Образно говоря, каждый двоичный символ, загруженный на входе канала Н[х] бит информации, доводит до конца канала лишь часть этой информации, а именно, /[х, >J бит. Остальная часть информации, т.е. Н[х/у\ бит, теряется в пути. Лишь в случае идеального канала (или
62 идеального инвертора) в пути ничего не теряется, Н[х/у] = 0, и каждый символ доводит до конца канала /[л, у] = Н[х] бит информации. Пусть теперь вероятностные характеристики Xt и X2 канала связи таковы, что имеет место
Таким образом, при соблюдении условия (3.35) каждый двоичный символ, независимо от того, каким количеством информации он был загружен на входе канала, весь свой "информационный груз" теряет в пути и к выходу канала приходит "с пустыми руками".
Пусть известно, что энтропия угадывания одной буквы передаваемого текста равна H бит. Тогда на входе канала, где информационная нагрузка каждого двоичного символа равна Н[х] бит, для распознавания каждой буквы в среднем необходимо Н/Н[х] символов. Столько же символов потребовалось бы на выходе канала, если бы канал был идеальным. Если же канал не идеальный, то среднее число символов на выходе, необходимое для распознавания одной буквы, оказывается равным Н/Цх, yj > Н/Н[х]. В частности, когда имеет место условие (3.35), т.е. когда /[л, у] = 0, число символов на выходе, необходимых для распознавания одной буквы, стремится к бесконечности. В рассматриваемом случае, независимо от того, сколько двоичных символов можно передавать через канал связи за единицу времени, количество информации, передаваемое через него за любой конечный отрезок времени, равно нулю. Далее этот случай исключим из рассмотрения, т.е. примем, что
Рассмотрим, например, случай, когда подлежит передаче оптимально закодированный текст, причем, прежде чем подать этот текст непосредственно на вход канала, его делят на блоки по т двоичных символов в каждом и каждый блок "снабжают" s дополнительно вводимыми (контрольными) символами, нацеленными на обнаружение и исправление возможных (одиночных) ошибок в канале связи. При этом значения т и л выбраны такими, что имеет место 2s - s - 1 = т. Иными словами, речь идет о передаче оптимально закодированного текста,
(3.39)
(3.36)
(3.37)
(3.38)
(3.35)
X, + X2 * 1.
63
ГЛАВА 5 снабженного кодом Р. Хэмминга, подробно рассмотренным во второй главе. Из схемы построения кода Р. Хэмминга и характера предполагаемых ошибок легко сделать вывод, что, как и для каждого информационного символа, для каждого контрольного символа при этом справедливо следующее: значения вероятностей того, что данный контрольный символ окажется нулем или единицей, равны между собой и не зависят от того, какие символы предшествовали данному символу.
Из вышеизложенного следует, что каждый двоичный символ входной последовательности несет информационную нагрузку, равную одному биту.
Оценим количество информации, которое доводится до конца канала связи очередным блоком из т + л двоичных символов (т информационных и контрольных).
Из (3.27) имеем
1[х,у]=Н[х]~Н[х/у], (3.27а)
где Н[х\ - количество неопределенности, соответствующее входному блоку из т + л двоичных символов; 7/[л/\] - количество остаточой неопределенности, соответствущее входному блоку из т + .v двоичных символов после того, как известен результат его приема на выходе канала.
Из оптимальности входной последовательности непосредственно следует, что Н[х] = (т + \)Т бит. Что же касается значения остаточной неопределенности Н\х/у], то для его вычисления мы руководствуемся следующими соображениями.
Поскольку речь идет лишь об одиночной ошибке, то после приема очередного блока из т + s двоичных символов, для внесения полной ясности в то, каким был этот блок на входе канала, необходимо ответить на два вопроса:
имела ли место ошибка вообще;
