8. Представление операций кодирования и декодирования

Нам нужно теперь представить математически операции, выполняемые передатчиком и приемником при кодировании и декодировании информации. И передатчик и приемник будем называть дискретными преобразователями. На вход преобразователя поступает последовательность входных символов, а на выходе получается последовательность выходных символов. Преобразователь может обладать внутренней памятью, так что выходной символ зависит не только от данного входного символа, но и от всех предыдущих. Предположим, что внутренняя память конечна, т. е. существует конечное число возможных состояний преобразователя и при этом очередной выходной символ является функцией от соответствующего входного символа и от состояния, в котором находится преобразователь. Следующее состояние преобразователя будет другой функцией от этих же аргументов. Таким образом, преобразователь может быть описан двумя функциями:

где - n-й входной символ,

— состояние преобразователя к моменту ввода входного символа.

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

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

Теорема 7. Выход преобразователя с конечным числом состояний, подключенного к статистическому источнику с конечным числом состояний, представляет из себя статистический источник с конечным числом состояний, причем энтропия этого источника (в единицу времени) меньше или равна энтропии источника на входе. Если преобразователь невырожденный, то энтропии равны.

Пусть а представляет собой состояние источника, который создает последовательность символов и пусть состояние преобразователя, который создает на выходе блоки символов Система, полученная в результате соединения источника с преобразователем, может быть представлена с помощью произведения «пространств состояний», состоящего из пар . Две точки в этом пространстве соединяются линией, если источник может изменить состояние на состояние создав при этом такой символ х, который изменит состояние преобразователя на Этой линии приписывается вероятность символа х, и она помечается блоком символов который был создан преобразователем при переходе из состояния в состояние Энтропия источника на выходе может быть вычислена как взвешенная сумма по всем состояниям. Если мы просуммируем сначала по то каждый получающийся в результате член будет не больше соответствующего члена для а, и, следовательно, энтропия не увеличивается. Если преобразователь невырожденный, то к его выходу можно присоединить второй преобразователь, обратный первому. Если при этом представляют соответственно энтропии источника и выходов первого и второго преобразователей, то , следовательно, .

Пусть на возможные последовательности наложена система ограничений того типа, который может быть представлен графически, как на рис. 2. Если бы различным линиям, соединяющим состояние с состоянием были приписаны вероятности то эта система стала бы источником. Имеется один частный способ приписывания вероятностей, при котором энтропия становится максимальной (см. приложение 4).

Теорема 8. Пусть система ограничений, рассматриваемая как канал, имеет пропускную способность Если положить

где — длительность символа, ведущего от состояния к состоянию а В, удовлетворяет условию

то энтропия максимальна и равна С.

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