Дискретные каналы связи; модели дискретных каналов связи

Лекция 6 Дискретные каналы связи 6.1 Дискретные каналы связи 6.1.1 Модели дискретных каналов связи В общем виде информационная модель канала с помехами задается множеством символов на его входе и выходе и описанием вероятностных свойств передачи отдельных символов. В общем случае канал может иметь множество состояний и переходить из одного состояния в другое как с течением времени, так и в зависимости от последовательности передаваемых символов. В каждом своем состоянии канал характеризуется матрицей условных вероятностей P (Ui |Zj ) того, что переданный символ Ui будет воспринят на выходе кака символ Zj . Таким образом, нестационарный канал связи имеет зависимость матрицы P от времени, но при этом может быть представлен рядом стационарных каналов, соответствующим различным временным интервалам. Информационная модель канала без помех является частным случаем с определением однозначных соответствий между множествами символов на входе и выходе канала (матрица условных вероятностей заполняется единицами). В общем случае M -ичным каналом (с помехами, либо без помех) называется такой канал связи, в котором размеры ансамблей U и Z совпадают. Важной частной моделью, широко использующейся при анализе и построении систем и сетей телекоммуникаций является стационарный дискретный двоичный канал без памяти. Данная модель однозначно определяется четырьмя условными вероятностями: p(0|0), p(1|0), p(0|1), p(1|1). 73 Рис. 6.1: Дискретный двоичный канал без памяти На указанном рис. 6.1 p(0|0) и p(1|1) - вероятности неискаженной передачи символов, а p(0|1) и p(1|0) - вероятности искажения (трансформации) символов 0 и 1 соответственно. Если вероятности искажения символов приблизительно равны: p(0|1) ≈ p(1|0) = q, то такой канал называют двоичным симметричным каналом, иначе несимметричным. Достаточно интересной также является мат. модель т.н. двоичного дискретного канала со стиранием. На выходе такого канала возможен символ неопределенности состояния (когда символ с равным основанием может быть отнесен к нулю, либо единице) - символ стирания, обозначающийся S: Рис. 6.2: Дискретный двоичный канал со стиранием При декодировании символы стирания существенно проще исправить, чем ошибочно определенные. 6.2 Теоремы Шеннона для дискретных каналов связи 6.2.1 Теорема Шеннона для дискретного канала без помех Определим понятие пропускной способности канала связи: 74 Пропускной способностью канала связи называется величина C, характеризующая максимально возможную скорость передачи информации по каналу с данными техническими характеристиками. Исходя из указанного определения, возможно записать выражение для пропускной способности канала связи: = max I(U, Z) = max v · I(U, Z). (6.1) Для случая канала без помех имеет место взаимно-однозначного соответствия между множествами символов U и Z на входе и выходе канала, соответственно. Таким образом, для канала без помех: I(U, Z) = I(Z, U ) = H(U ). При этом максимум возможного количества информации на символ равен log M , где M - объем алфавита символов; таким образом, пропускная способность дискретного канала без помех определяется следующим образом: C = vchannel log M. (6.2) Исходя из свойства асимптотической сходимости становится возможно доказать теорему Шеннона для дискретного канала без помех: Теорема 1 (Теорема Шеннона для дискретного канала без помех). Если пропускная способность дискретного канала без помех превышает производительность источника сообщений, т.е. удовлетворяется условие: vchannel log M > vsource H(U ), (6.3) то существует способ кодирования и декодирования сообщений источника с энтропией H(A), обеспечивающий сколь угодно высокую однозначного и верного декодирования. В противном случае такого способа не существует. Доказательство.Для доказательства теоремы пронумеруем все типичN ные последовательности достаточно большой временной длины T = vsource цифровыми комбинациями B с основанием M , равным объему алфавиту канала. Таким образом, число различных кодовых комбинаций равно: N (B) = M N = 2T ·vsource log M . 75 (6.4) Число типичных последовательностей длительностью N в соответствии с (5.9) Ntyp (U ) = 2T ·vsource ·H(U ) . Условие теоремы Шеннона 6.3 возможно записать в виде vchannel log M = vsource H(A) + , где  - сколь угодно малая величина и, следовательно: N (B) = 2T · . Ntyp (U ) Примем  = log e T Ntyp (U ) (6.5) . (6.6) В этом случае: N (B) 1 1 = e1/Ntyp (U ) = 1 + + + ... Ntyp (U ) Ntyp (U ) 2![Ntyp (U )]2 или N (B) > Ntyp (U ) + 1. Таким образом, при выполнении базового условия теоремы Шеннона число различных комбинаций по крайней мере на единицу больше числа типичных последовательностей источника. Эту избыточную кодовую комбинацию поставим в соответствие всем нетипичным последовательностям, предопределив их недостоверную передачу. Поскольку при T −→ ∞ и N −→ ∞, то вероятность появления нетипичной последовательности стремится к нулю, а величина  бесконечно мала, то первую часть теоремы возможно считать доказанной. Докажем теперь вторую часть теоремы - в случае нарушения условия 6.3, когда vchannel log M > vsource H(U ), используя аналогичный подход при доказательстве, получаем неравенство Ntyp (U ) > N (B) + 1. Из полученного неравенства следует, что даже при равновероятном сопособе кодирования (соответствующем предельной скорости передачи информации по каналу связи) невозможно закодировать и передать все типичные последовательности Ntyp , что и требовалось доказать. Оптимальное кодирование, использованное при доказательстве теоремы Шеннона для дискретного канала без помех, сводится к предельному укрупнению 76 алфавита канала, когда каждый укрупненный символ (кодовая комбинация) отвечает бесконечно длинной последовательности символов источника сообщений. При этом одновременно устраняется корреляция между символами укрупненного алфавита канала и благодаря сохранению лишь типичных последовательностей обеспечивается равная вероятность их появления. В результате полностью устраняется избыточноть сообщения, передаваемого по каналу. Кодирование данным способом связано с задержкой передачи сообщения (латентностью передачи) на время: τlatency = 2T + T0 , (6.7) где время 2T определяется тем, что кодирование может начаться, лишь когда известна уже вся последовательность символов источника длительностью T , а декодирование - когда уже принята кодовая комбинация той же длительности; T0 - время, затрачиваемое на технические операции кодирования, декодирования и на прохождение сигнала по каналу1 . 6.2.2 Теорема Шеннона для дискретного канала с помехами При наличии помех соответствие между множествами символов на входе и выходе канала связи перестает быть однозначным. Среднее количество информации I(U, Z), передаваемое по каналу одним символом, определяется в этом случае соотношением: I(V U ) = H(U ) − HZ (U ) = H(Z) − HU (Z). (6.8) Если статистические связи между символами отсутствуют, энтропия на выходе канала связи равна: H(U ) = − M X p(um ) log p(um ). (6.9) m=1 При наличии статистической связи энтропию определяют с использованием цепей Маркова. Для простоты рассуждений ограничимся здесь случаем отсутствия корреляции между отдельными символами. 1 Необходимо отметить, что в канале без помех источником ненадежности отождествления передаваемых сообщений может быть только операция кодирования, т.к. нарушение соответствия при передаче сообщений по каналу исключено. 77 Итак, если объем алфавита входных символов U равен M , а выходных символов Z - L, то апостериорная энтропия2 входного сообщения U после приема конкретного символа может быть вычислена по следующей формуле: M X L X HZ (U ) = − p(um , zl ) log p(um |zl ). (6.10) m=1 l=1 Величина HZ (U ) по терминологии, введенной Клодом Шенноном, называется ненадежностью канала. Таким образом, получаем скорость передачи информации по каналу с помехами: I(U, Z) = vsymbol M X L X p(um , zl ) log m=1 l=1 p(um , zl ) , p(um )p(zl ) (6.11) где vsymbol - символьная скорость передачи по каналу связи. Согласно своему определению, пропускная способность канала с помехами является пределом функции I(U, Z): C = max vsymbol I(U, Z). p(U ) Для двоичного симметричного канала с помехами пропускная способность определяется по формуле C = F [1 + (1 − β) · ln(1 − β) + β · ln β], (6.12) где β - вероятность ошибочного приема; F = 1/τ - символьная частота передачи данных (τ - длительность канального символа). C учетом вышеизложенного, реальная степень загрузки канала характеризуется коэффициентом использования канала: λ = I(U )/C, (6.13) где I(U ) - производительность источника сообщений, а C - пропускная способность канала связи. 6.2.3 Теорема Шеннона для дискретного канала с помехами Шенноном было доказано, что и в случае канала с помехами его пропускная способность определяет верхнюю достижимую границу скорости 2В случае канала без помех значение апостериорной энтропии равно нулю. 78 достоверной передачи информации по каналу. Таким образом, для дискретного канала с помехами теорему Шеннона возможно сформулировать следующим образом: Теорема 2 (Теорема Шеннона для дискретного канала с помехами). Для дискретного канала с помехами существует такой способ кодирования, при котором может быть обеспечена безошибочная передача всей информации, поступающей от источника сообщений, если только пропускная способность канала превышает производительность источника сообщений, т.е. выполняется условие: vchannel [log M − H(U |Z)] > vsource H(U ). (6.14) Доказательство данной теоремы приводится, например, [Липкин] и может быть детально рассмотрено читателем. Отметим лишь основные следствия данной теоремы: 1 Теорема Шеннона для дискретного канала с помехами под оптимальным понимает кодирование, связанное с увеличием задержки передачи сообщения3 на время τlatency = 2T + T0 . 2 Теорема Шеннона для канала с шумами не указыает конкретного способа кодирования, обеспечивающего достоверную передачу информации, а лишь доказывает принципиальное существование такого кода. 3 Чем выше длительность кодированной последовательности (и, соответственно, латентность) и чем меньше коэффициент использования канала, тем больше помехоустойчивость сообщений. Теорема Шеннона для канала с помехами имела огромное значение для становления правильных воззрений на принципиальные возможности техники связи. До Шеннона считалось, что сколь угодно малую вероятность ошибки можно получить лишь при стремлении скорости передачи информации к нулю. Введя в рассмотрение кодирование последовательностей бесконечной длительности, Шеннон впервые показал, что принципиально существуют коды, которые обеспечивают сколь угодно малую вероятность ошибки при конечной скорости передачи информации, причем эти коды обладают сравнительно небольшой избыточностью, необходимой для компенсации вредного действия помех в канале связи. 3 Латентности сообщения. 79