Лекция 9. Анализ передачи сообщений по каналам с помехами
Курс “Теория информации и кодирования”

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

Анализ дискретного канала (передача кода)
Подходы к передаче кода по каналу с ошибками
Анализ непрерывного канала (передача сигналов)
Подходы к передаче сигналов по каналу с помехами

9.1 Анализ дискретного канала (передача кода)

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

Здесь мы рассмотрим случай передачи кода по условному каналу (в пространстве или во времени) с возможностью возникновения случайных ошибок. Модель передачи по такому дискретному каналу иллюстрирует рис.9.1:
  • источник вырабатывает поток сообщений, состоящих из знаков алфавита Z с безусловной энтропией Hz;
  • кодер преобразует передаваемые знаки zi в последовательность разрядов кода xj, которые характеризуются безусловной энтропией Hx. В связи с возможными ошибками передачи на вход декодера поступают значения разрядов уj с энтропией Hy;
  • канал обеспечивает передачу со средней скоростью Vx (разряд/с) при вероятности возникновения ошибок po. Эти ошибки обуславливают неопределенность, вносимую каналом (энтропию Hy/x или Hx/y). Рассматривается случай, когда вероятность ошибок не зависит от значений разрядов (канал “симметричен”). Вследствие этого справедливо Hx= Hy и Hx/y= Hy/x;
  • информативность разрядов, передаваемых через такой канал (бит/c), может быть определена как разность энтропии кодера и энтропии канала (Ixy = Hх - Hx/y). В силу симметричности канала справедливо также Ixy = Hy - Hy/x;
  • исходя из перечисленных параметров модели может быть рассчитана пропускная способность канала (максимальное количество информации, которое канал способен пропускать в среднем за единицу времени) С = Vx max{ Ixy}= Vx max{Hy - Hy/x} (бит/c).

Формула пропускной способности дискретного канала
Выше приведена общая формула определения пропускной способности канала. Однако, для практических нужд удобно привести ее к виду, где в качестве исходных данных используются только измеримые параметры передачи (в частности, скорость передачи и вероятность возникновения ошибок). Получение такой формулы иллюстрирует рис.9.2:
  • в качестве исходной принимается обоснованная выше формула С = Vx max{Hy - Hy/x};
  • 1) для дискретного канала можем использовать соответствующую формулу условной энтропии;
  • 2) учитывая, что канал двоичный, получим максимальное значение безусловной энтропии (1 бит/разряд), а также развернутую формулу для условной энтропии;
  • 3) для случая симметричного канала (ошибки для 0 и 1 происходят с одинаковой вероятностью) выразим условную энтропию через вероятность ошибок.

Таким образом, рассчетная формула для определения пропускной способности двоичного симметричного канала с ошибками будет иметь вид
С = Vx [1+po log2po + (1-po) log2(1-po)].
Пропускная способность канала без ошибок определяется из исходной формулы при допущении Hy/x=Hx/y=0. В этом случае С = Vx max{Нx}. Поскольку для двоичного канала max{Нx}=1 бит/разряд, пропускная способность численно равна скорости передачи С = Vx (бит/с).

Анализ пропускной способности и ее использования
Опираясь на полученную формулу, можно проанализировать зависимость пропускной способности дискретного канала от его параметров — рис.9.3:
  • максимум пропускной способности очевидно соответствует полному отсутствию ошибок (po=0). При этом, как мы уже знаем, величина пропускной способности (бит/с) численно равна скорости передачи разрядов Vx (разряд/с), поскольку каждый двоичный разряд кода без потерь доносит один бит информации. Интересно, что согласно формуле макисимум пропускной способности наблюдается также при вероятности ошибок po=1. Этот кажущийся парадокс легко объяснить: если заранее известно, что при передаче значение разряда поменяется на противоположное, то его всегда можно восстановить инвертированием;
  • минимум пропускной способности (ее полное отсутствие С=0) соответствует вероятности ошибок po=0,5. Это также легко объяснимо: если вероятности получения верного или ошибочного значения разряда одинаковы, то у нас нет никакого основания предпочесть один из этих вариантов. А следовательно, передача информации здесь невозможна;
  • промежуточные значения пропускной способности характеризуются выраженной нелинейностью. При этом наиболее значительные ее потери приходятся как раз не диапазон отнсительно небольших вероятностей ошибок. В частности: при вероятности po = 0,01 величина C снижается на 8%; при вероятности po = 0,05 - на 29%; при вероятности po = 0,10 - на 47%;
  • в целом влияние ошибок передачи можно уподобить влиянию отложений на стенках трубы: сечение, через которое может протекать жидкость, сокращается, а вместе с ним уменьшается и пропускная способность. Однако, жидкость все-таки способна протекать через трубу. Так же и с информацией — она принципиально может быть передана по каналу с ошибками, хоть и за большее время.

Контрольные вопросы
1) Опираясь на рис.9.1, охарактеризуйте информационную модель дискретного канала передачи.
2) Запишите формулы для удельной информативности разряда кода и пропускной способности канала. Что отражает в этих формулах условная энтропия Нy/x= Нx/y
3) Используя рис.9.2, расскажите об этапности вывода формулы для пропускной способности дискретного канала.
4) Запишите формулы для расчета пропускной способности дискретного канала с ошибками и без ошибок.
5) Опираясь на рис.9.3, поясните зависимость пропускной способности дискретного канала от вероятности ошибок передачи. Почему эта зависимость симметрична относительно значения вероятности ошибок 0,5
6) Поясните особенности пропускной способности дискретного канала. Каковы максимальное и минимальное значение пропускной способности и при каких условиях они проявляются. Назовите ориентировочную величину снижения пропускной способности при вероятности ошибок 1% и 10%.


9.2 Подходы к передаче кода по каналу с ошибками

Принципы кодирования для защиты от ошибок
Принципиальные особенности передачи сообщений по дискретному каналу с ошибками поясняет рис.9.4:
  • образно говоря, кодирование для передачи по каналу с ошибками создает “защитную оболочку” для передаваемого информационного кода. “Прочность” такой оболочки определяется избыточностью создаваемого кода. В минимальном варианте она позволяет фиксировать “повреждения”, а в максимальном — устранять их;
  • принято выделять два уровня кодирования: сжатие сообщений именуют кодированием источника, а защиту от ошибок — кодированием канала. На первом из уровней устраняется исходная избыточность. На втором, напротив, избыточность кода добавляется — но уже полезная, необходимая для устранения ошибок передачи;
  • для кодирования канала Клод Шеннон сформулировал и доказал теорему, подобную той, с которой мы знакомились для сжатия сообщений. Суть теоремы Шеннона в том, что всегда можно закодировать сообщения таким образом, что пропускная способность канала будет использована максимально полно (при этом преодолеть ограничение пропускной способности за счет кодирования невозможно);
  • при видимом сходстве формулировок с теоремой для кодирования источника, смыл теоремы для кодирования канала куда менее очевиден. Действительно, интуитивно не ясно, как именно можно достоверно передавать информацию по каналу с ошибками. Ориентир, который дает теорема Шеннона, состоит в том, что за счет избыточного кодирования можно обеспечить достоверную передачу ценой увеличения ее длительности. Снижение пропускной способности канала как раз и означает увеличение необходимой длительности передачи (подобно тому, как установленный объем жидкости может пройти через меньшее сечение трубы за большее время).

Примеры использования контрольных разрядов кода
Методы избыточного помехозащитного кодирования будут детально рассмотрены в следующих двух лекциях, а пока мы лишь проиллюстрируем на простых примерах приницип его действия — рис.9.5:
  • простейший способ такого кодирования заключается в использовании одного контрольного разряда, значение которого дополняет количество «1» в блоке кода до четного (пример А). Если при передаче происходит ошибка в одном из разрядов, то правило четности нарушается и тем самым ошибка обнаруживается. Разумеется, такой способ не позволяет определить позицию ошибочного разряда и это значит, что код не способен исправить обнаруженную ошибку. Более того, если при передаче “пострадают” одновременно два разряда кода, условие четности не нарушится и такая ошибка останется не обнаруженной;
  • усилить возможности кода (его корректирующую способность) можно, если использовать большее количество контрольных разрядов. В примере Б показано использование трех таких разрядов при передаче одного полубайта. Применение одновременно трех проверок позволяет локализовать позицию ошибочного разряда, а значит — исправить ошибку путем его инвертирования (в данном случае 3 проверки дают 8 различимых варианов кода, которые могут охватить 7 вариантов ошибки и 1 вариант безошибочной передачи). Подобные коды (они называются кодами Хэмминга) применяются для устранения результатов сбоев оперативной памяти серверов;
  • при одинаковом числе контрольных разрядов соотвествующая корректирующая способность кода может быть направлена не на исправление одиночных ошибок (которые характерны, в частности, для оперативной памяти компьютеров), а на обнаружение цепочек ошибок (которые нередко встречаются при передаче по линиям связи). В примере В показан вариант кода, который позволяет обнаруживать любые цепочки из двух или трех ошибок (такой код называется “циклическим”);
  • итак, на примерах видно, что использование дополнительных контрольных разрядов позволяет в принципе обнаруживать и даже исправлять ошибки передачи. При этом увеличение корректирующей способности кода требует роста его избыточности. Однако, нужно учитывать что вероятности возникновения ошибок могут значительно изменяться (как например, при передаче в эфире) и создавать коды, рассчитанные на самый худший случай, явно не рационально.

Исправление ошибок с использованием обратной связи
Более гибким и рациональным способом исправления ошибок является использование обратной связи для повторной передачи ошибочных блоков кода (рис.9.6):
  • здесь узлы А и Б (например, абоненты телефонной сети или узлы компьютерной сети) обмениваются сообщениями попеременно в роли Передатчика и Приемника. Передатчик кодирует блок сообщения, дополняя его контрольными разрядами, и отправляет по Прямому каналу. Приемник декодирует полученный блок и в зависимости от результата формирует Подтверждение правильности или Перезапрос на повторную передачу, которые отправляет по Обратному каналу. При получении перезапроса Передатчик повторяет соответствующий блок при этом повторение ошибки в канале маловероятно (в общем случае попытки передачи повторяются до достижения положительного результата);
  • избыточность кода, необходимая для обнаружения ошибок, значительно меньше требуемой для их исправления. при этом ухудшение условий передачи компенсируется ростом количества перезапросов, а значит — полного времени доставки сообщений. Таким образом способ обратной связи экономичен и к тому же автоматически отслеживает изменения пропускной способности канала. При этом наличие обратного канала при двусторонней передаче означает, что дополнительные затраты на оборудование не нужны;
  • показанная на рис.9.6 схема соответствует способу, который называют “решающей” обратной связью (РОС). Здесь решение о необходимости повторной передачи принимает Приемник и дополнительная нагрузка на обратный канал минимальна. Такой способ получил наибольшее распространение и применяется, в частности, в компьютерных сетях. В альтернативной схеме (с «информационной» обратной связью — ИОС) передаваемый информационный возвращается по обратному каналу и уже Передатчику принимает решение о его правильности. В этом случае нагрузка на обратный канал значительно выше. ИОС применяется, когда обратный канал мощнее прямого (например, в системах связи с летающими объектами).

Контрольные вопросы
1) Поясните понятия “кодирование источника” и “кодирование канала”. В чем смысл введения избыточности в код на втором из этих этапов, тогда как на первом избыточность напротив устранялась.
2) Сформулируйте теорему Шеннона о кодировании для канала с ошибками. В чем состоят ее особенности по сравнению с теоремой о кодировании источника.
3) Поясните принцип действия простейшего помехозащитного кода с контролем четности. Каковы его возможности и ограничения.
4) Опираясь на рис.9.5, поясните, каким образом за счет увеличения избыточности кодирования можно исправлять обнаруженные ошибки или обнаруживать цепочки ошибок.
5) Используя рис.9.6, поясните принцип исправления ошибок передачи с использованием обратной связи.
6) В чем состоит преимущество исправления ошибок с использованием обратной связи перед непосредственным исправлением с помощью кода.
7) Поясните различия способов исправления ошибок с помощью решающей и информационной обратной связи. Где применяются способы РОС и ИОС.


9.3 Анализ непрерывного канала (передача сигналов)

Модель передачи по непрерывному каналу
Модель передачи по непрерывному каналу используется в основном для анализа передачи сигналов в физической среде. Модель характеризует рис.9.7:
  • Преобразователь формирует непрерывный сигнал x(t) исходя из получаемой от Источника зависимости Z(t). Сигнал передается через Канал, где на него накладывается случайная непрерывная аддитивная помеха e(t). На стороне Получателя сигнал y(t) = x(t) + e(t);
  • параметрами модели являются значения средней мощности передаваемого cигнала x(t) и помехи e(t) – соответственно Px и Pe. Также к параметрам модели относится ширина полосы частот Fk, которую способен передавать канал. Для важного частного случая, когда энергия помех равномерно распределена по всей частотной полосе канала итоговая мощность помех определяется исходя из их удельной мощности px . Такие помехи называются “белым шумом”. Они наиболее непредсказуемы и сними сложнее всего бороться, поэтому пропускная способность определяется именно относительно таких помех;
  • передаваемый сигнал характеризуется величиной дифференциальной энтропии Нх, а принимаемый — энтропией Hy. Канал вслелствие влияния помех создает условную энтропию Нх/y = Hy/x. Пропускная способность канала как максимальное количество информации, которое канал способен передавать за единицу времени, может быть определена по общей формуле С = Vx max {Hy – Hy/x}. Модель позволяет преобразовать эту формулу таким образом, чтобы выразить величину С непосредственно через параметры сигналов, помех и канала.

Формула пропускной способности непрерывного канала
Вывод рабочей формулы для определения пропускной способности непрерывного канала поясняет рис.9.8:
  • 1) поскольку информативность непрерывного сигнала согласно теорем Котельникова ограничена удвоенной максимальной частотой спектра, максимальную скорость передачи можно определить исходя из предельной частоты, пропускаемой каналом;
  • 2) из допущения об аддитивности помех следует, что энтропия канала опредаеляется энтропией помех. Кроме того, дисперсия выходного сигнала (σy2) определяется как сумма дисперсии входного сигнала и помехи;
  • 3) условие максимума информативности досигается, если распределения сигнала и помехи будут гауссовыми. В обоих случаях может использоваться рассмотренная нами в лекции 3 формула дифференциальной энтропии гауссова распределения Н = log2√(2πe σy2);
  • 4) развернем теперь исходную формулу для пропускной способности с учетом описанных уточнений. Дополнительно учтем, что разность логарифмов преобразовывается в логарифм частного, а дисперсия выходного сигнала выражается через дисперсию входного и помех. Кроме того множитель 2 перед логарифмом эквивалентен возведению в квадрат выражения под логарифмом, что устраняет там корень квадратный. Наконец, учтем, что средняя мощность соотвествуют величине дисперсии.

Теперь мы располагаем рабочей формулой для расчета пропускной способности непрерывного канала C=Fk log2[1+Px/Pe] (бит/с). Ее развернутая форма учитывает связь мощности помех с шириной частотной полосы - C=Fk log2[1+Px/(pe Fk )]. В различных случаях оказывается более удобным использование одного из этих двух вариантов.

Анализ пропускной способности непрерывного канала
В полученной выше формуле удобно выделить два сомножителя:
- величина Fk (ширина полосы частот канала) пропорционален максимально допустимой скорости передачи (сигналов/c);
- смысл второго сомножителя — удельная информативность сигнала (бит/сигнал).
На рис.9.9 показаны примеры зависимостей пропускной способности канала и удельной информативности сигналов от ширины частотной полосы канала. Здесь наглядно проявляются следующие особенности:
  • увеличение ширины полосы канала позволяет наращивать его пропускную способность благодаря увеличению возможной скорости передачи. Однако, такой рост постепенно замедляется в связи с тем, что параллельно увеличивается суммарная мощность помех (рис.9.9а);
  • описанный эффект поясняет рис.9.9б, где показано уменьшение информативности отдельных значений сигналов с ростом полосы канала. Принцип заключается в том, что значительное превышение полезного сигнала над помехой позволяет уверенно различать больше его значений (например, при использовании 4 различимых значений сигнала можно передавать одновременно 2 бита информации). Увеличение мощности помех приводит к тому, что такие возможности исчерпываются;
  • пример наглядно иллюстрирует возможность принципиальную возможность передачи информации с помощью сигналов более слабых, чем помехи (это непосредственно следует из формулы пропускной способности, где слагаемое 1 под знаком логарифма делает величину информативности положительной даже для малых отношений сигнал/помеха). На практике это означает, что для передачи одного бита информации может быть использовано несколько сигналов. Такой подход действительно используется в современных системах связи.

В дальнейшем мы рассмотрим практические подходы к реализации пропускной способности непрерывного канала.

Контрольные вопросы
1) Опираясь на рис.9.7, охарактеризуйте информационную модель непрерывного канала передачи.
2) Охарактеризуйте основные параметры модели. В чем состоит особенность помех типа “белый шум” и как она отображается в модели.
3) Используя рис.9.8, расскажите об этапности вывода формулы для пропускной способности непрерывного канала.
4) Запишите варианты формулы для расчета пропускной способности дискретного канала и поясните их.
5) Опираясь на рис.9.9, поясните зависимость пропускной способности непрерывного и информативности отдельных значений сигналов от ширины полосы частот канала.
6) Почему из полученных формул следует возможность передачи информации с помощью сигналов, более слабых, чем помехи. Как эта возможность может быть реализована на практике.


9.4 Подходы к передаче сигналов по каналу с помехами

Примеры использования ресурсов пропускной способности
Основные практические направления использования пропускной способности канала связаны с ростом скорости передачи, а также увеличением их информационной нагрузки. Соответствующие примеры показаны на рис.9.10:
  • увеличение скорости передачи сигналов является наиболее очевидным и простым подходом. Однако, как видно на рис.9.10а, при этом закономерно возникают искажения формы сигналов, растет их затухание, а вместе с тем — вероятность неправильного распознавания на фоне помех;
  • рост информационной нагрузки на отдельный сигнал возможен за счет использования увеличения числа распознаваемых значений. На рис.9.10б показан пример использования так называемой фазовой модуляции (ФМ) гармонических сигналов-носителей (это одна из разновидностей передачи сигналов в эфире). Здесь представление “0” и “1” двумя противоположными значениями фазы (ФМ-2) позволяет передавать с помощью одного сигнала 1 бит информации. Применение четырех и восьми фаз (ФМ-4 и ФМ-8 соответственно) обеспечивает передачу одним сигналом 2 и 3 битов. При сохранении скорости передачи сигналов (а вместе с ней и максимальной частоты передачи) битовая скорость возрастает соответственно в 2 и в 3 раза. Такой подход можно реализовать, если в канале существует запас превышения допустимой мощности сигналов над помехами. В противном случае будет расти вероятность возникновения ошибок.

Направления согласования канала и передаваемых сигналов
Выполненное определение пропускной способности канала позволяет использовать простую и наглядную модель согласования параметров канала и передаваемых по нему сигналов — рис.9.11:
  • вводится параметр “емкости канала”, используемой для передачи информации. Емкость Qk (бит) определяется как произведение ширины частотной полосы Fk на величину превышения Lk возможной мощности полезного сигнала над существующей в канале помехой (соответствует второму сомножителю в формуле пропускной способности) и на время Tk использования канала для передачи;
  • соответственно, сигналы, необходимые для передачи нужной информации характеризуются “объемом сигнала” Qx = Fx Lx Tx. Очевидно, что для успешной передачи необходимо выполнение условия Qk >= Qx. Однако, только его выполнение может оказаться недостаточным: нужно, чтобы сигнал “уложился” в ограничения по всем трем координатам объема;
  • решение состоит в “обмене” недостающих ресурсов по одним координатам на избыточные по другим. Например, очевидно, что расширение полосы частот Fx для роста скорости передачи при наличии резерва частотной полосы канала Fk позволит пропорционально сократить длительность Tx. С другой стороны, наличие избытка по параметру Lk позволяет увеличить отношение сигнал/помеха Lx, а вместе с ней — информационную нагрузку на сигнал. Это опять-таки позволит сократить время передачи или, при необходимости — сэкономить полосу частот канала за счет уменьшения скорости. Таким образом, существует набор базовых приемов, которые позволяют эффективно согласовывать характеристики передаваемых сигналов с параметрами канала. В дальнейшем мы будем детально рассматривать их реализацию.


Контрольные вопросы
1) Опираясь на рис.9.10а поясните, как проявляются ограничения в повышении скорости передачи сигналов.
2) Используя рис.9.10б, прокомментируйте пример увеличения информационной нагрузки сигналов. При каких условиях можно использовать такой способ реализации пропускной способности непрерывного канала.
3) Поясните понятия “емкость канала” и “объем сигнала”. Сформулируйте исходя из их применения условия передачи сигнала по каналу.
4) Расскажите о способах “обмена” недостащих ресурсов по одним координатам объема сигнала на избыточные по другим.
О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP