книги / Основы дальней связи

(11.2.3)

Т. е. средняя длина кодограмм не может быть меньше ее сред­

ней энтропии. Знак равенства достигается, если Р(Ци) = 2 " т<* так как в данном случае

ном выше обычном посимвольном способе кодирования нижняя граница минимальной длины кодограмм не достига­

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

Равенство Н(Ч) — т ср говорит о том, что среднее на 1 кодограмму количество информации, действительно, пере­ носится двоичными посылками. Другими словами, одна двоичная посылка,- способная переносить 1 дв. ед. информа­

может сколь угодно приближаться к пропускной способно­ сти канала. Для этого, например, необходимо, чтобы алфа­ вит входных сигналов имел равномерное распределение символов, как это_ следует из выражения (II.5.7). Поэтому оптимальные в указанном смысле коды получили название эффективных.

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

где //,(;) учитывает корреляцию символов. Если имеем про­ извольный источник с коррелированным алфавитом, то оп­ тимальный код может быть построен с использованием крупноблочного кодирования, если известны условные и безусловные вероятности символов.

Предположим теперь, что для передачи непрерывных сиг­ налов используется гауссов канал с пропускной способно­ стью, определяемой выражением (1.5.15). Это выражение по­ лучено при условии, что как полезный сигнал, так и помеха имеют нормальную плотность распределения. Отсюда следует,

что, если осуществить такое непрерывное кодирование исход­ ных низкочастотных сигналов (т|), при котором линейные сигналы [U] будут нормально распределены и будут иметь равномерный спектр в полосе A/*, то можно вести пере­ дачу со скоростью, сколь угодно близкой к пропускной способности канала.

§II. 3. ПЕРВАЯ ТЕОРЕМА ШЕННОНА

ОКОДИРОВАНИИ В КАНАЛАХ

С ПОМЕХАМИ

Пусть по двоичному каналу передается бинарная последо­ вательность из п элементарных посылок £Д7) длительно­ стью т0 каждая. Будем считать, что все элементы последо­ вательности независимы, а сама она является эргодическим

то за время, равное длительности одной элементарной посыл­ ки, будет передано

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

Выражение (II.3.10) справедливо для любой, даже очень малой величины Д, т. е. при любом приближении vnM к С.

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

Так формулируется первая теорема Шеннона о кодиро­ вании в присутствии помех.

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

$ II. 4 ВТОРАЯ ТЕОРЕМА ШЕННОНА О КОДИРОВАНИИ В ПРИСУТСТВИИ ПОМЕХ

Первая теорема Шеннона указывает на существование ко­ да, обеспечивающего произвольную малость вероятности ошибки, но не дает никаких рекомендаций относительно ал­

вания относительно минимально допустимой величины веро­ ятности ошибки действительная скорость передачи инфор­ мации. казалось бы, должна стремиться к 0, так как при этом фактически все п элементов должны выполнять функ­ ции корректирования ошибок. Тогда вывод первой теоремы теряет какой-либо практический смысл. Однако это не так.

Пусть получатель наблюдает элемент ; (£), гдеу= 1,2,3,...,А.

Д ля того, чтобы установить, какая именно посылка была передана, необходимо сначала определить, была ли вообще совершена ошибка при передаче данного элемента. Вели вероятность ошибки есть Р 0, то количество информации, необходимое для ее обнаружения, составит

/(Р 0; ( 1 - Р 0)|= Л /[Р 0; ( 1 - Р 0) ] -

Если обнаружилось, что ошибка совершена, то нужно устано­

Т. е. для того, чтобы установить, какой именно элемент ;Д 0 был передан, если наблюдается элемент (t ), необходимо в среднем

H [P 0( \ - P n)} + P tH ( L - D = - P n log2P „ -

дв. ед. информации. Это количество информации должно быть достаточным, чтобы убрать оставшуюся неопределенность после наблюдения \} (t). Поэтому является справедливым неравенство

M - f ) < Яо 1о& Р » ~ ( 1~ R )lo g 2( l - P 0) + P 0log2( Z .- 1 ), (И.4.4)

называемое неравенством Фэно.

Оно может быть отнесено, конечно, не только к отдельным

L —количество реализаций, высоковероятной группы N e. Если теперь принять во внимание условия первой теоремы Шеннона, из которой следует, что Р,,<4, где е—сколь угодно малое положительное число, то справедливыми будут следующие неравенства:

e lo g îS ^ - ^ O g îO - e H - s lo g a O V e - l) - 1 Ь

поскольку для определения того, какая из (N , — 1) после* довательностей была передана, нужно иметь па приеме эту последовательность, которая несет примерно пЛ/(Ь) дв. ед. информации. Разделив обе части выражения (И.4.5) на я, по­ лучим

(П.4.7)

Таким образом, при п -*■оо апостериорная энтропия на сим-

ответствии с выражением (1.2.11), равна

(II.4.8)

поэтому при п со

(II.4.9)

Полученный результат позволяет сформулировать вторую теорему Шеннона для кодирования в условиях воздействия помех; при условии v„.u< С среди кодов, обеспечивающих

Обе теоремы пЬсле этого можно объединить в одну общую, сформулировав ее следующим образом: если скорость переда­ чи информации в шумящем канале без памяти не превышает его пропускной способности, то существует код, при котором вероятность ошибки на приеме будет сколь угодно малой.

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

Вторая теорема, как и первая, не дает никаких рекоменда­ ций относительно алгоритма построения, оптимального в ука­ занном смысле кода, за исключением того, что с увеличени­ ем п ее утверждение становится все более справедливым. Практически еще не найден алгоритм кода, реализующего тео­ ретические пределы величин е и Uu. Более того, использо­ вание очень длинных кодограмм сопряжено со значитель­ ным усложнением кодирующих устройств и увеличением

задержки получения информации на приемном конце систе­ мы связи. Поэтому важное значение приобретает вопрос о граничных значениях вероятности ошибки при кодировании блоками не очень большой длины. Эди оценки приведены в ряде исследований и хорошо согласуются с теоремами.

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

С увеличением vn u они уменьшаются, что вполне соответ­

ствует интуитивным представлениям: вероятность ошибки при увеличении производительности источника должна воз­ растать. При я - * о о е - * 0 , что согласуется с первой и вто­ рой теоремами Шеннона о кодировании в присутствии помех.

§ 11.5. ОБРАТНАЯ ТЕОРЕМА ШЕННОНА ДЛЯ КАНАЛОВ С ПОМЕХАМИ

Предположим, что к входу канала с пропускной способно­ стью С подключен источник с производительностью vn u > С. Возникает вопрос: что при этом произойдет с ве­

В силу фундаментального свойства Е для эргодических диск­