отождествления принятых комбинаций с действительно переданными. Если же vKlog2m < vH#(A), то такого способа нет.

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

N(B) = mTv2n. (7.11)

Число типичных последовательностей длительностью Т с числом символов п = 7vH согласно (7.7) равно

NTm(A) = 2TvMA). (7.12)

Условие (7.10) можно записать в виде vKlog2m = vKH (А) + е, где е - сколь угодно малая величина, откуда N (BNA) - 2№. Если принять е = log2e/WTMI(A), то

W (A)~e 1 AU(A) 2\[Nmn(A)f

или

ЛКВ)>ЛГтап(А) + 1.

Таким образом, при выполнении условия (7.10) число различных кодовых комбинаций Впо крайней мере на единицу больше числа типичных последовательностей источника. Эту избыточную кодовую комбинацию поставим в соответствие всем нетипичным последовательностям, предопределив их недостоверную передачу. Поскольку при Г-> < и соответственно п -> °° вероятность появления нетипичной последовательности стремится к нулю, а величина е, определяющая требуемое превышение пропускной способности канала над производительностью источника, бесконечно малая, первую часть теоремы можно считать доказанной.

В случае нарушения условия (7.10), когда vKlog2m>vKH (А) используя тот же подход, получаем неравенство Л^А) >N(B)+l.

Таким образом, в этом случае даже при описанном способе кодирования, обеспечивающем равную вероятность использования всех символов алфавита канала и, следовательно, предельную скорость передачи информации по каналу, мы уже не сможем закодировать и передать все

типичные последовательности Л^А). Поэтому и вторую часть теоремы можно считать доказанной.

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

Кодирование способом, изложенным при доказательстве теоремы, связано с задержкой передачи сообщения на время

Тзад = 27ЧГ0, (7.13)

где время 2Т определяется тем, что кодирование может начаться, когда уже известна вся последовательность символов источника длительностью Г, а декодирование - когда уже принята кодовая комбинация той же длительности; Г0 - время, затрачиваемое на технические операции кодирования, декодирования и на прохождение сигнала по каналу.

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

7.2. Скорость передачи информации и пропускная способность дискретного канала при наличии помех

Если в канале без помех среднее количество информации, получаемой с выхода канала в единицу времени, соответствует среднему количеству информации, содержащемуся во входном сообщении той же длительности, то в канале с помехами это соответствие нарушается. При наличии помех скорость передачи информации по каналу будет меньше среднего количества информации, поступающего в единицу времени на вход канала, ибо часть информации, поступившей на вход канала, разрушается помехами. Помехи нарушают взаимно-однозначное соответствие между символами bj на выходе канала и символами bt на его входе. Принятый символ Ь) определяет при этом не конкретный входной символ bjy а некоторый закон распределения апостериорных вероятностей P(b\bj)

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

= P(b\bj)\og2P{b\bj). (7.14)

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

н дао=-X 2 рф]> рф№ iog2p W)=

j=i /=i

= ~Х X Р (h bj) log2P(b,]bj), (7-15)

j=l i-l

где Р (bh bj) - совместная вероятность появления входного символа Ь-х и выходного bj.

Используя формулы (2.3) и (2.9), выражение (7.15) можно переписать в виде:

Н (В\В') = -X X Р (Ьд Р (Ь%) х

Р(ЬдРф%) xlog2 mv . (7.16)

XpcmpW

Величина Я (£#0 по терминологии, введенной К. Шенноном, называется ненадежностью канала. Из (7.16) видно, что она зависит как от статистических характеристик входного сообщения канала В (распределения вероятностей Р (ft,)), так и от вероятностных характеристик искажений символов, вносимых действующими в канале помехами.

Последние могут быть заданы матрицей условных переходов [р,у], где Pi/, обозначает условную вероятность P(bj\bi) трансформации входного символа bi в выходной символ bj.

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

#(BiB) = H(B)-H{B\B) =

= Я(В)+ХХ P{bhbj)\og2P(b\bj). (7.17)

j=i i=i

Наличие двойного аргумента в левой части (7.17) связано с тем, что осреднение информации, приходящейся на один символ, должно производиться по всем сочетаниям символов входного и выходного алфавита.

Преобразуем (7.17), воспользовавшись формулами (2.8) и (2.3):

W В') = - X Р Фд log2/>(*>/) + X X р &ь bj) х

i=l ;=1 /=1

х log2P(b,]bj) = - X £р{Ь>, bj) 1оё2Р(Ьд +

В силу симметрии (7.18) относительно символов входного и выходного алфавитов можно заключить, что

J(B, Bf)-H{B)-H (Я|#0 = Я (В') - Я (В*\В) = (2Г, В), (7.19)

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

Средняя скорость передачи информации по каналу с помехами равна

MSMl = VkJ(b> Ю = Vb [н (В) + £ > ф bj) х

ai ;=1 /=1

xlog2P(fc,Z>,)]. (7.20)

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

на один символ на входе канала, т.е. условию безызбыточности входных сообщений:

Ск = vK JiJLB, Ю = vK [log2m - Я (В|В01 С7-21)

В данном случае пропускная способность определяется нами как предельное количество информации, которое достигает выхода канала в единицу времени, если на вход в единицу времени поступает максимальное количество информации vKlog2m, которое только может быть воспринято каналом с данным алфавитом и скоростью формирования символов.

Пропускная способность дискретного канала с помехами, как следует из (7.21), зависит от ненадежности канала H(B\Bf), характеризующей средние потери информации, приходящейся на один символ, из-за действия помех. При отсутствии помех Я (В\В') = 0, так как

при/*/ Р№,)=/>да)=о.

при i = , P(bhbj) = l. Пропускная способность канала, определяемая формулой (7.21), в этом случае равна

CKmax = vK log2m,

что совпадает с приведенной ранее формулой (7.4) для пропускной способности канала без помех. При полном забитии канала помехами, когда независимо от принятого символа равновероятен любой символ на входе канала, т.е. Я (В^) - log2m, как следует из (7.21), пропускная способность

Ск min ~~ О

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

0CKvKlog2m. (7.22)

7.3. Основная теорема Шеннона для дискретного канала с помехами

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

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

vK [log2 т-Н (Bp)] > v Я (А). (7.23)

Докажем эту теорему. Число типичных последовательностей достаточно большой длительности Г, которое может давать источник А производительностью у„Я (А), равно

Ли(А) = 2ГУнЯ(А). (7.24)

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

N (В) = mv r = 2VK71og2m . (7.25)

Поскольку Я (#]#) > 0, неравенство (7.23) только усилится, если его записать в виде:

vK\og2m>vKH(A), (7.26)

тогда

N (В) = 2Tv>2TvMA) = AU(A), (7.27)

т.е. множество цифровых кодов N (В), которые могут быть использованы для кодирования, много больше числа типичных последовательностей Л^тнп(А), подлежащих кодированию. Таким образом, при кодировании входных типичных последовательностей используется лишь небольшая часть множества N (В), что предопределяет большой выбор возможных способов кодирования (число таких способов М, очевидно, равно числу размещения из N (В) по Nnn(A) элементов). Требуется доказать, что среди этих М способов кодирования имеется по крайней мере один, обеспечивающий однозначную идентификацию любой принятой кодовой комбинации с одной из комбинаций, используемых при кодировании, что является условием достоверного приема. Для доказательства найдем

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

число типичных входных кодовых последовательностей, которые могут трансформироваться в данное выходное сообщение длительностью Г, по аналогии с (7.12) равно

() = 27V (. (7.28)

Правильный прием (однозначная идентификация переданной кодовой комбинации) обеспечивается в том случае, когда среди #ТИП(2?В') входных последовательнрстей, которые могли дать данную выходную последовательность, лишь одна была использована при кодировании, а остальные N-тЛЩВ?) -1 последовательностей вообще не могли передаваться.

Найдем осредненную по всем возможным способам кодирования вероятность Рцрав того, что ни одна из этих [NrvniBlB) -1] последовательностей не была использована при кодировании. Средняя [для всех возможных способов кодирования множества Nma(A) поступающих от источника типичных последовательностей] вероятность использования конкретной кодовой комбинации из N (В) возможных комбинаций равна

Ртип = ЛГтап(А)/АКЯ),

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

l-P =l-NUAW(B). (7.29)

Средняя же вероятность того, что не использовались конкретные [NjB]?) -1] кодовые комбинации, определяющие среднюю вероятность правильного приема, равна

р -Л - Р \M WO-l] 1 nW (7 30ч

прав-U гът) ~\ N(B)\

Так как основание степени в правой части (7.30) меньше единицы, то, увеличивая показатель степени до значения NjJLB\p)f из (7.30) получаем неравенство

а после разложения в ряд правой части этого неравенства имеем:

P>\-Nrm{B\Br)- +

N(B) J К }

Г w 1 1 тип

В силу (7.27) NvmiAyN (В)<1 и правая часть (7.31), представляющая знакопеременный ряд с убывающими по абсолютной величине членами, только уменьшится, если отбросить все остальные члены, начиная с положительного члена 2-го порядка. Поэтому можем записать

AU.(gBQAU(A) N(B)

Используя (7.24), (7.25), (7.28), из (7.32) получаем: Лно= 1 -Л^<ЛГ (Я|Я0 =

2~7Tv log2m-vrH(5le>-VH (A)] 2-7ICK-v tf(A)] 33

Помимо ошибки при приеме типичных последовательностей, вероятность которой Рош определяется формулой (7.33), может также иметь место нарушение достоверности передачи информации при кодировании всякий раз, когда потребуется передача нетипичных последовательностей, кодирование которых вообще не предусматривается. При вероятностях появления нетипичной последовательности 8 и типичной последовательности 1 - 5 суммарная вероятность ошибочной передачи информации равна

Pz = 5 + (l-S)P . (7.34)

При Г-> оо в соответствии с (7.33) Рош-> 0 [по условию теоремы Ск>уиЯ (А)] и в соответствии с теоремой асимптотической равновероятности 5 -> 0 следовательно, и р£->0. Итак, при любом заданном е>0 можно выбрать такое Т9 что будет обеспечиваться Рх < е.

Поскольку среди всех М вариантов кодирования обязательно существует хотя бы один, для которого вероятность ошибки не превышает среднего по всем вариантам кодирования значения Р^, теорему Шеннона можно считать доказанной. Заметим, что здесь, как и в канале без помех [см. (7.31)], кодирование связано с задержкой передачи сообщения на время

Тзад = 27Ч Го.

Теорема Шеннона для канала с шумами не указывает конкретного способа кодирования, обеспечивающего достоверную передачу информации

со скоростью, сколь угодно близкой к пропускной способности канала, а лишь доказывает принципиальное существование такого кода. Однако из формулы (7.33) вытекает крайне важный практический вывод: достоверность связи тем выше, чем больше длительность кодированной последовательности (при этом соответственно увеличивается задержка в приеме информации) и чем менее эффективно используется пропускная способность канала [больше запас по пропускной способности Ск - v # (А)]. Таким образом, существует возможность размена эффективности использования канала на достоверность передачи информации, что и делается на практике.

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

HiB)=v=vm--&K{og2m.HiBW)

и, следовательно, избыточность входного сообщения

р ai,Ma дсв|У) (735)

ри 1 log2m - log2m

Таким образом, для обеспечения достоверной передачи информации достаточно ввести во входное сообщение избыточность, превышающую потерею информации в канале из-за действия помех, характеризуемую ненадежностью канала Н(В\В'). Удлинение же кодируемых последовательностей при использовании кодов Шеннона вызывает не снижение пропускной способности, а лишь увеличение задержки в приеме информации.

Основной смысл теоремы Шеннона сводится к следующему. Пропускную способность дискретного канала мы определяли как максимальную скорость передачи информации по каналу, соответствующую безызбыточности входных сообщений, т.е. условию поступления на вход канала в каждую единицу времени предельного количества информации, которое только способен воспринять канал. При отсутствии помех CKmax = vKlog2m, а при наличии помех - меньше на величину vKH(B\B,)f характеризующую

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

Для наглядного пояснения роли теорем Щеннона прибегнем к следующему сравнению. Пусть имеется трубопровод для доставки некоторого жидкого продукта, поступающего от источника. Технические возможности трубопровода определяются количество жидкости, которое можно передать по нему в единицу времени. Скорость передачи продукта по трубопроводу будем определять количеством чистого продукта, доставляемого потребителю в единицу времени, а производительность источника - количество чистого продукта, поступающего от него в единицу времени. Пропускную способность трубопровода определим как максимально возможную скорость передачи чистого продукта, соответствующую условию, что от источника поступает чистый продукт без примесей (без избыточности ). Аналогом радиоканала с помехами может служить трубопровод с утечкой. Пропускная его способность, отвечающая скорости доставки продукта потребителю при поступлении на вход трубопровода чистого продукта, будет меньше, чем в трубопроводе без утечки, на величину утечки продукта за единицу времени. Можно теперь представить, какой эффект вызвало бы утверждение, что существует такой способ введения примеси ( избыточности ) в продукт, при котором, введя количество примеси, равное утечке в трубопроводе, можно по нему доставить чистый продукт без потерь со скоростью, отвечающей пропускной способности трубопровода с утечкой. Именно такой смысл применительно к задаче передачи информации имеет теорема Шеннона для радиоканала с помехами.

7.4. Пропускная способность непрерывного канала при наличии аддитивного шума

Под пропускной способностью непрерывного канала будем понимать максимально возможную скорость передачи информации по каналу при заданных технических характеристиках канала: полосе пропускания и отношении сигнал/шум. Так же, как и в случае дискретных каналов, скорость передачи информации по непрерывному каналу зависит от выбора ансамбля входных сигналов. Максимальная скорость передачи информации реализуется при максимальной скорости поступления информации на вход канала, которая соответствует случаю выбора ансамбля входных сигналов с максимальной энтропией. Для дискретных каналов, когда заданным для ансамбля сигналов является объем алфавита канала, максимальная скорость поступления информации обеспечивается при равномерном использовании символов алфавита. Для непрерывных сигналов, когда заданной следует считать среднюю мощность сигнала, максимальная скорость поступления информации соответствует использованию нормальных центрированных случайных сигналов. Условие центрированности обеспечивает при этом максимум дисперсии при данной средней мощности сигнала, а его нормальность - наибольшую априорную энтропию каждого отсчета при данном значении дисперсии (см. § 6.3). Поэтому при определении пропускной способности непрерывного канала входные сигналы будем считать стационарными случайными центрированными нормальными.

Шум будем считать нормальным белым, что соответствует максимальной энтропии, вносимой шумом в полученное непрерывное сообщение, т.е. максимальной ненадежности канала по Шеннону при заданном отношении сигнал/шум. Принимаемый сигнал имеет вид

ti(0 = + (7.36)

где £ (0 - передаваемый сигнал, несущий полезную информацию; п (t) - шумы в канале.

Ширина спектра сигнала ограничивается верхней частотой определяемой полосой пропускания канала. Поэтому согласно теореме Котельникова сигнал полностью определится дискретными отсчетами Г| следующими с частотой 29. Значения белого шума при такой частоте отсчетов будут некоррелированными (см. § 2.8). Дискретные отсчеты передаваемого сигнала будем также считать некоррелированными, что соответствует условию максимума его энтропии (для нормальных сигналов, как было показано в § 2.6, некоррелированность отсчетов означает и их

независимость). Тогда и дискретные отсчеты принимаемого сигнала будут некоррелированными (а значит, и независимыми), и количество информации, содержащейся в принимаемом сигнале, будет равно сумме количеств информации, содержащихся в независимых его отсчетах, следующих с частотой 29*. Количество информации о текущем значении передаваемого сигнала вносимое дискретным отсчетом принимаемого сигнала Т| может быть представлено в виде разности априорной энтропии этого отсчета и апостериорной его энтропии при известном отсчете передаваемого сигнала (см. § 7.2). Заменяя разность энтропии разностью соответствующих дифференциальных энтропии по аналогии с (7.19), получаем

(Л ) = А(т1/)-Л(т1). (737)

Отсчеты принимаемого сигнала, представляющего сумму двух нормальных случайных сигналов £ (г) и п (г), распределены по нормальному закону с дисперсией о\ = а\ + а2ш (входной сигнал и шум считаем независимыми). Апостериорная неопределенность принимаемого сигнала при известных значениях отсчетов передаваемого сигнала определяется значением шума, имеющего нормальное распределение с дисперсией а2ш. Поэтому разность дифференциальных энтропии в правой части (7.37) в соответствии с (6.24) равняется log2 (аг/аш) и информация, вносимая одним дискретным отсчетом сигнала,

(Ць £/) = log2 (ол/аш) =

= \оё2(о\ + о2ш)/о2ш = log2Vl+а24/а2ш. (7.38)

Величина а\/о2ш = 9J9m характеризует отношение сигнал/шум в канале.

Пропускная способность канала, определяемая количеством информации, передаваемой по каналу в единицу времени при рассмотренных условиях, равна информации, содержащейся в 2,% независимых дискретных отсчетах сигнала:

Ск = 2.Klog2Vl= #dog2(l + 9J9m) . (7.39)

Формула (7.39) называется формулой Шеннона.

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

Нетрудно видеть, что при &J&m - О, Ск - 0. Формулу (7.39) можно трактовать следующим образом. Величина (1 + ЗУш) характеризует количество уровней непрерывного сигнала, различимых на фоне шума при данном отношении SPJ&n. Поэтому количество информации, приходящееся на один отсчет, будет в данном случае таким же, как для дискретного источника с числом состояний (1 + 9УЗ.

Преобразуем (7.39), приняв 9>ш = где N0 - спектральная плотность белого шума (для одностороннего спектра):

Ск = log2(l + (7.40)

Раскрывая по правилу Лопиталя неопределенность при 3 - °°, в правой части (7.40) получаем Ск = (9>CIN0) log2e, т.е. пропускная способность стремится к фиксированной величине, определяемой отношением средней мощности сигнала к спектральной плотности шума. Таким образом, обмен мощности сигнала на полосу пропускания для обеспечения заданной пропускной способности непрерывного канала возможен лишь в некоторых границах, за которыми дальнейшее расширение полосы пропускания дает уже малый эффект.

Можно показать, что и в случае непрерывного канала его пропускная способность Ск является одновременно и верхней границей скорости достоверной передачи информации. Примем следующую модель кодирования и декодирования непрерывных сигналов. Из всего множества реализация случайного сигнала £ (/) будем использовать для передачи счетное подмножество реализаций {xt{t}}. Кодирование заключается в отождествлении данной реализации х (0 случайного сигнала £, (/) с ближайшим к ней сигналом подмножества {xt(t)}y а декодирование - в выделении сигнала подмножества {*,<*)}, ближайшего к принятой реализации выходного сигнала т| (г). Оптимальное кодирование должно обеспечивать достоверный прием переданных сигналов x,{t) при максимально возможном числе реализаций xt{t\ используемых при кодировании. Правильный прием переданного сигнала x&t) будет обеспечиваться в случае,если из всего подмножества {х,{0} ближайшим к принятой реализации случайного сигнала Г] (0 - х,{0 + п (г) останется сигнал xt{t). Это накладывает ограничения на минимально допустимое расстояние между реализациями x,(t) [при данном уровне шума п (0] и, следовательно, на максимальное число сигналов, используемых для передачи информации, и на максимальную скорость достоверной передачи информации.

-(l0g2AUx)/7\

где Т- длительность сигналов.

В [18, 23] доказывается, что скорость достоверной передачи информации по непрерывному каналу при рассмотренном способе кодирования ограничивается пропускной способностью непрерывного канала, определяемой формулой (7.39). При этом так же,как в дискретных каналах, достоверная передача информации со скоростью, приближающейся к пропускной способности непрерывного канала, возможна лишь при кодировании сигналов очень большой (строго говоря, бесконечной) длительности.

Ш

ОСНОВЫ ТЕОРИИ КОДИРОВАНИЯ

Глава 8

ОБЩИЕ СВЕДЕНИЯ О КОДИРОВАНИИ

8.1. Функциональная схема радиолинии передачи дискретных сообщений

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

Рис 8.1

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

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

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

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

Декодирующее устройство осуществляет обратное преобразование кодовых комбинаций в сообщения. Из-за действия помех возможно нарушение однозначного соответствия между переданным и принятым сообщением (ошибочный прием). Достоверность передачи информации зависит от формы сигнала и характеристик радиолинии. Форма сигнала определяется кодом и видом модуляции. От вида модуляции зависит вероятность искажения элементарных символов (признаков) кодовой комбинации. От выбора кода зависит вероятность правильного приема сообщения при данной вероятности искажения элементарных символов. Таким образом, помехозащищенность радиолинии передачи сообщений зависит от выбора как способа кодирования (кода), так и вида модуляции.

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

Глава 8. Общие сведения о кодировании

8.2. Цифровые коды

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

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

Увеличение основания цифрового кода приводит к повышению пропускной способности радиолинии (уменьшается требуемое число разрядов кода), но зато требует большего числа различных элементарных символов, что приводит к усложнению радиолинии. При отсутствии помех пропускная способность канала увеличивалась бы пропорционально увеличению основания кода. Наличие помех ослабляет этот эффект: увеличение числа различных символов, если энергия их остается фиксированной, т.е. сохраняется скорость их формирования, ухудшает их различимость на фоне помех и повышает вероятность их искажений. Это приводит к увеличению ненадежности канала и снижает его пропускную способность (см. § 7.2). Эффект повышения пропускной способности канала в результате увеличения основания кода будет тем меньшим, чем большим будет уровень помех.

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

8.3. Основные задачи теории кодирования

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

1. Реальные сообщения имеют конечную длительность.

2. Число различных кодовых комбинаций с увеличением их длительности, как следует из (7.11) и (7.25), растет по экспоненте. Поэтому приближение к условиям идеального кодирования по Шеннону в результате

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

3. Кодирование и декодирование по Шеннону может осуществляться только после накопления в памяти всей последовательности символов длительностью Г, что требует дополнительной задержки в передаче информации на время 2 Г. Это также ограничивает приемлемую длительность кодов и возможность приближения к условиям идеального кодирования.

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

Исследованием свойств кодов ограниченной длительности и поиском оптимальных структур технически реализуемых кодов занимается теория кодирования. Теория кодирования развивается в двух главных направления: 1) поиски кодов, позволяющих в каналах без помех максимально устранить избыточность источника и тем самым повысить эффективность передачи информации (теория экономного кодирования); 2) поиски кодов, повышающих достоверность передачи информации в каналах с помехами (теория помехоустойчивого кодирования).

Рассмотрим коротко пути решения этих основных задач теории кодирования.

8.4. Понятие об экономном кодировании

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

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

tj = -(\og2Pj)/CK, (8.1)

где Ск - пропускная способность канала.

Кодирование, при котором обеспечивается распределение времени на передачу отдельных символов алфавита в зависимости от априорных вероятностей их появления по закону (8.1), называется оптимальным ста-тистическим кодированием.

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

= 1Р/; = -£Ру1оё2Р;= , (8.2)

j = \ Ск ) = \ *

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

Необходимой предпосылкой применения оптимального статистического кодирования является независимость символов алфавита, обеспечивающая априорное (независимое от контекста) знание вероятностей Pj появления отдельных символов. Реальные сообщения, подлежащие передаче, обычно не удовлетворяют условию независимости символов. Поэтому статистическому кодированию должны предшествовать меры по устранению или, по крайней мере, по ослаблению корреляционных связей между символами алфавита канала. Этого можно достигнуть, используя укрупнение алфавита канала, которое сводится к тому,что блок из L символов источника сообщений объединяется в один символ алфавита канала. При этом практически устраняются статистические связи между символами укрупненного алфавита канала. При объеме алфавита источника, равном jw, объем укрупненного алфавита ту при любых возможных сочетаниях

символов источника в блоке длины L равен ту = т . Уменьшения избыточности при этом практически не происходит, поскольку при кодировании относительно коротких последовательностей еще не происходит выделения существенной группы нетипичных последовательностей, вероятностью появления которых можно было бы пренебречь, исключив их из укрупненного алфавита. А без этого, как легко убедиться, изменить избыточность алфавита нельзя. При энтропии источника сообщений Н(А) среднее количество информации на символ укрупненного фильтра равно Ну - LH(A) и избыточность передаваемого сообщения

Ну ГД(А) = 1 LH(A) =1 Н(А)

Руи log2my Llog2m \о&т Ри

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

Распределение длительностей символов, близкое к закону (8.1), можно реализовать, используя для их передачи неравномерное цифровые коды, т.е. цифровые коды, содержащие различное число разрядов. При этом строгое удовлетворение условия (8.1) не обеспечивается из-за дискретного закона изменения длительности цифрового кода. Однако, чем больше длина L кодируемых блоков и соответственно объем укрупненного алфавита /Яу, тем большей будет максимальная длительность цифрового кода и меньшим влияние дискретности ее изменения.

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

Рассмотрим в качестве конкретного примера статистического кодирования двоичный код Шеннона-Фано. Для его формирования расположим все /Яу независимых символов укрупненного алфавита канала в порядке возрастания априорных вероятностей их появления Ру. На рис. 8.2 показан случай использования восьми символов, обозначенных первыми восемью буквами латинского алфавита; в скобках указаны вероятности появления этих символов. Найдем сечение, разбивающее все символы на две группы

с суммарной вероятностью каждой примерно равной 0,5. На рис. 8.3 это сечение проходит между символами/и g. Присвоим для всех символов, входящих в первую группу, единицу в передаваемом первым разряде отображающих их двоичных кодов, а для символов второй группы - соответственно нуль. Разобьем снова каждую из этих групп на две подгруппы с суммарными вероятностями примерно равными 0,25 и присвоим следующим разрядам двоичных кодов, отображающих символы первых подгрупп каждой группы, единицы, а вторых подгрупп - нули. Кодирование

d(0,03) в(0,07)

с(0,08)

d(0,09)

е(0,10)

8(0,23)

h(0,25)

Рис. 8.2

каждого символа заканчивается, как только он остается единственным символом в подгруппе после соответствующего этапа разбиений. Очевидно, что чем меньше вероятность появления символа, тем в большем числе разбиений он будет участвовать и тем длиннее будет отображающий его двоичный код. Процедуру кодирования удобно осуществлять, используя построение кодового дерева , как показано на рис. 8.3. Полученные двоичные коды, отображающие каждый из символов, записаны на рисунке у соответствующих вершин кодового дерева. Это неравномерные двоичные коды, обладающие тем свойством, что ни одна из используемых кодовых комбинаций меньшей длины не совпадает с началом кодовой комбинации большей длины. Такие неравномерные коды называются неприводимыми. В отсутствие искажений символов в канале неприводимость кодов обеспечивает однозначность декодирования неравномерных кодов без использования специальных символов для разделения кодовых комбинаций: конец каждой кодовой комбинации и начало следующей в этом случае опре деляются единственным образом. Заметим, что для обеспечения этого свойства кодовые комбинации обязательно должны записываться, начиная от корня кодового дерева.