1. ДИСКРЕТНЫЕ СИСТЕМЫ БЕЗ ШУМОВ

1. Дискретный канал без шума

Телетайп и телеграф являются двумя простыми примерами использования дискретного канала для передачи информации. Вообще же под дискретным каналом будет подразумеваться система, с помощью которой можно передать из одного места в другое последовательность символов, выбранных из некоторого конечного множества элементарных символов Предполагается, что каждый из символов имеет определенную длительность во времени секунд (не обязательно ту же самую для разных например точки и тире в телеграфии). Не требуется, чтобы все возможные последовательности символов могли передаваться системой. Эти допустимые последовательности и будут возможными сигналами для канала. Так, например, в телеграфии такими сигналами являются: 1) точка, создаваемая замыканием линии на некоторое единичное время и последующим размыканием на такое же время; 2) тире, создаваемое замыканием на три единицы времени и размыканием на одну единицу; 3) пробел между буквами, создаваемый, скажем, размыканием на три единицы времени; 4) пробел между словами, создаваемый размыканием на шесть единиц времени. Мы могли бы наложить ограничение на допустимые последовательности, состоящее в том, чтобы пробелы не следовали один за другим (так как два последовательных пробела между буквами идентичны пробелу между словами). Рассмотрим теперь вопрос о том, как можно измерить пропускную способность такого канала.

В случае телетайпа, где все символы имеют одинаковую длительность и каждая последовательность из этих 32 символов допустима, ответ получить легко. Каждый символ несет пять битов информации. Если система передает символов в секунду, естественно сказать, что канал имеет пропускную способность битов в секунду. Это еще не означает, что канал телетайпа будет всегда передавать информацию с такой скоростью - это максимальная возможная скорость, и достигает ли или нет действительная скорость этого максимума, зависит, как будет показано ниже, от источника информации на входе этого канала.

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

где — число допустимых сигналов длительности Т

Легко видеть, что в случае телетайпа это определение сводится к предыдущему. Можно показать, что рассматриваемый предел существует и для большинства случаев, представляющих интерес, конечен. Предположим, что все последовательности символов допустимы и что эти символы имеют длительности Чему равна пропускная способность канала? Если представляет собой число последовательностей длительности то

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

и поэтому

Если имеются ограничения на допустимые последовательности, часто можно все же получить разностное уравнение такого же типа и найти С из характеристического уравнения. В упомянутом выше случае телеграфии

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

Решая это уравнение, находим, что

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

два состояния, зависящие от того, был ли последним переданным символом пробел или нет. Если это был пробел, то после него могут быть посланы только точка или тире и состояние всегда изменяется. Если нет, то может быть передан любой символ, и состояние изменяется, если посылается пробел, в противном случае оно остается неизменным. Эти условия могут быть представлены в виде схемы, как показано на рис. 2. Узловые точки соответствуют состояниям, а линии указывают символы, возможные в некотором состоянии, и результирующие состояния. В приложении 1 показано, что если ограничения на допустимые последовательности могут быть описаны в такой форме, то С существует и может быть вычислено согласно следующей теореме.

Теорема 1. Пусть означает длительность символа, который допустим в состоянии и приводит к состоянию

Рис. 2. Графическое представление телеграфных символов.

Тогда пропускная способность канала С равна где — наибольший действительный корень характеристического уравнения

здесь если и нуль в противном случае.

Например, в случае телеграфа (рис. 2) уравнение имеет вид —

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