< Previous | Contents | Next >
rл. 1. ДИСI<РЕТНЫЕ СИСТЕМЫ БЕЗ ШУМОВ 29
Теорема 9
Пусть источник имеет «энтропию» Н (двоичных единиц на сим вол), а канал обладает пропускной способностью С (двоичных единиц в 1 сек.). Тогда можно закодировать сообщения на выхо де источника таким образом, чтобы передавать символы по ка-
налу со среднемu скоростьюНс - е символов в I сек., где е - сколь
угодно мало. Передавать со средней скоростью, большей чем
Нс' невозможно.
Обратная часть теоремы, утверж ающая, что нельзя прев- зоиu ти скорости Нс' может б ыть доказана, если заметить, что «энт-
ропию> на входе канала за 1 сек. ра·вна «энтропии» источника, так как передатчик должен быть несингулярным четырех полюсником, и что эта <<энтропия>> не может превзойти пропускной способнасти канала. Отсюда Н' <.С и число символов в 1 сек.
равнН' _<С-.
н н
Первая часть теоремы будет доказана двумя различными спо собами. Первый способ состоит в рассмотрении совокупности всех последовательностей из N символов, создаваемых источником. При большом N можно разделить их на две группы, одна из
.которых содержит меньше чем 2<н+'f/)N членов, а вторая меньше чем 2R.V членов (где R. - логарифм числа различных символов) и имеет полную вероятность, меньшую µ.. Если N возрастает, "1/ и µ. приближаются к нулю. Число сигналов в канале, каждый длительностью Т, больше чем 2<с-в1т, причем 6 мало, когда Т велико. Если-выбрать
то найдется достаточное число последовательностей канальных символов для группы, обладающей высокой вероятностью, когда N и Т достаточно велики (как бы ни было мало л), а также несколько добавочных .последовательностей символов. Группа последовательностей с высокой вероятностью произвольным, взаимно однозначным образом, кодируется в эту совокупность. Остающиеся последовательности представляются более длинны ми, начинающимися и заканчивающимися одной из последова тельностей, не использованных для группы с высокой вероят ностью. Эта особая последовательность играет роль стартстопного сигнала другой кодовой комбинации.
Между ними сохраняется временной интервал, необходимый для образования достаточного числа различных последователь-