Проблема помехоустойчивого кодирования

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

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

Мы помним, что нас окружают со всех сторон шумы, помехи. Когда я говорю, где-то на фоне — там где вы меня слушаете — может работать перфоратор, где-то что-то может стучать или может играть какая-то музыка, и вы будете слышать меня всё хуже и хуже в зависимости от того, какой шумовой фон окружает вас или какой шумовой фон окружает меня. Но всё-таки мы снимаем в условиях тишины, чтобы обеспечить как можно большую устойчивую передачу информации.

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

Рисунок 1. График функции шума

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

 
Рисунок 2. Помехи на графике функции нормального шума

А что с сигналом? Допустим, есть спутник, который излучает сигнал, или вышка сотовой связи, или когда вы с кем-то общаетесь на каком-то расстоянии, ваш сигнал, несмотря на то, что вы стараетесь говорить с одним и тем же уровнем сигнала, и передатчик на спутнике старается поддерживать определенный уровень, но тем не менее всё-равно настройки передатчика немного меняются. Это может быть связано с какими-то температурными влияниями или ещё с чем-то, на пути распространения сигнала может возникнуть какая-то поглощающая среда, характеристики которой меняются от времени. Тоже самое связано относится и к приёмнику. 

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

Рисунок 3. График функции полезного сигнала (справа)

Обратите внимание, что есть некоторая точка (точка пересечения графиков функции нормального шума и функции полезного сигнала), при которой всё-таки есть вероятность того, что уровень сигнала, который мы принимаем, окажется меньше уровня шумов. 

Проведём некоторую вертикальную линию через эту точку. И если мы выберем настройки приёмника, который регистрирует сигнал, например, в точке - правее точки пересечения графиков, то таким образом мы попытаемся как можно дальше уйти от шумов. То есть интервал AB (вертикальный отрезок на графике, выделен на рис. 4) показывает, что вероятность того, что шум «выпрыгнет» выше сигнала, уже намного меньше. И поэтому может показаться, что порог приёма сигнала нужно повышать.

Рисунок 4

Но, с другой стороны, обратите внимание, что и полезный сигнал, который находится слева от этой линии, мы будем пропускать — площадь S1 (заштрихована на рис. 4). То есть получается, что сильно завышать порог регистрации принятого сигнала на приёмнике тоже не выгодно, потому что мы будем пропускать и часть полезного сигнала.

Тогда может нужно решать задачу как можно более полного приёма сигнала? И порог срабатывания выбрать так, чтобы практически весь сигнал, который вы ожидаете, принимать. 

Рисунок 5

Но тогда окажется, что шум, который умело прикинулся сигналом, тоже будет чаще возникать. То есть случаи, соответствующие площади S₂ под кусочком кривой шума (рисунок 5), тоже будут чаще. 

Эта площадь показывает общую вероятность того, что шум преодолеет порог срабатывания и вы будете на самом деле регистрировать не сигнал, а шум. Поэтому, когда мы принимаем сигнал и принимаем решение о том, какой порог срабатывания нам установить, то мы должны решить в каком-то смысле противоречивую задачу: с одной стороны, мы бы хотели вероятность ошибки (называется вероятность ложной тревоги) уменьшить, это означает — перенести порог срабатывания правее, тогда площадь S₂ будет уменьшаться, но, с другой стороны, мы будем часто пропускать сигналы, то есть вероятность потери — площадь S₁ будет расти.

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

p_л.т. + p_п.с. → min

Вам всегда в любом случае нужно принимать решение: что считать сигналом, а что — шумом.

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

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

Вот такая картина наблюдается, когда мы работаем с какими-то реальными системами.

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

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

Попробуем разобраться с этой задачей на примере знакомого нам кода Хэмминга (7, 4), где 7 — это общее количество бит, которое мы хотим передать, 4 — это количество информационных битов, и соответственно 7 – 4 = 3 дополнительных проверочных бита. Если бы мы передавали сигнал, не используя помехоустойчивый код Хэмминга, то вероятность успешной передачи без искажений P₄=p₀⁴, где p₀ — это вероятность успешной передачи одного бита.

Если будем использовать код Хэмминга, то есть будем передавать 7 бит, то мы помним, что этот код исправляет однократную ошибку, то есть если среди принятых семи бит есть одна ошибка, то код Хэмминга сможет её благополучно исправить и сообщение будет восстановлено и принято без ошибки. И естественно, если среди семи бит вообще нет ошибок, то это тоже успешная передача данных. Вероятность того, что в принятом сообщении вообще нет ошибок равно p₀⁷. Вероятность того, что в сообщении из 7 бит будет одна ошибка — это 7p₀⁶(1-p₀), где (1-p₀) — это вероятность, того что в данном бите будет ошибка, а так как всего их семь, то при их сложении получается коэффициент 7.

Тогда получаем вероятность успешной передачи:

P₇ = p₀⁷ + 7p₀⁶(1-p₀)

Обратите внимание на эти два выражения (P₄ и P₇). И спросим себя: начиная с какой вероятности p₀, использование кода Хэмминга уже оправдано. То есть необходимо сравнить два числа (P₄ и P₇). На рисунке 8 вы видите эти две функции: функция, которая отвечает за код Хэмминга, представляет собой чёрную линию, функция, которая представляет просто передачу четырёх бит без всяких контрольных, — синюю линию. 

Рисунок 8

И обратите внимание, что если p₀ < 1/2, то использовать код Хэмминга уже не перспективно, то есть передать сообщение без ошибки, не используя код Хэмминга, всё-таки эффективнее, чем использовать кодирование. Это связано с тем, что в код Хэмминга добавляется ещё три проверочных символа, то есть удлиняете сообщение и следовательно вероятность двукратной ошибки в этом случае возрастает.

Но начиная с вероятности p_{0 >} 1/2, использование кода Хэмминга приводит к вероятности передать сообщение в большем количестве случаев, то есть вероятность того, что вы не испортите сообщение шумом уже больше. Да может быть одна ошибка, но вы её успешно исправите. Таким образом, вы немного больше тратите энергии в данном случае, потому что добавляете три информационных символа, но тем не менее вероятность успешной передачи повышается.

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

Рисунок 9

На рисунке 9 как раз представлен такой график. Вы видите две линии: одна из них соответствует сигналу без кодирования , другая соответствует помехоустойчивому коду Хэмминга (31, 26). И обратите внимание, что, начиная примерно с отношения сигнал-шум 4,7 дБ, код Хэмминга становится энергетически равен сигналу без дополнительных информационных символов. А при отношении сигнал-шум 8 дБ использование помехоустойчивого кода (31, 26) уже в десять раз более эффективно с точки зрения вероятности возникновения ошибки, нежели использование сигнала без использования помехоустойчивого кода.

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

Для размышления

Подумайте, за счёт чего могут возникать шумы? Какого рода помехи могут возникать при использовании других методов передачи данных?

Материалы

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