636_Nosov_V.I._Seti_radiodostupa_CH.1_

101

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

1.При отсутствии ошибочных битов вход декодера FEC идентичен исходному кодовому слову, так что на выход декодера поступает исходный блок данных;

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

3.Некоторые последовательности ошибок могут быть обнаружены декодером, но не могут быть исправлены. В этом случае декодер сообщает о наличии неисправимой ошибки;

4.Наличие некоторых (обычно довольно редких) последовательностей ошибок не может быть обнаружено декодером. В результате декодер преобразовывает от входной n- битовый блок в k-битовую последовательность, которая отличается от переданной, но которую кодер считает правильной.

Декодер FEC исправление ошибок осуществляет путем добавления избыточных данных к передаваемому сообщению.

Кодирование с коррекцией ошибок можно рассматривать как инструмент, реализующий различные компромиссы системы. На рисунке 4.2 приведен сравнительный вид двух кривых, описывающих зависимость достоверности передачи от отношения Eb/N0. Одна кривая соответствует обычной схеме модуляции без кодирования, а вторая представляет такую же модуляцию, но уже с использованием кодирования. Ниже подробно рассмотрены компромиссы, имеющие место при канальном кодировании.

Представим себе, что разработана простая, недорогая система речевой связи которая была установлена у заказчика. Система не использует кодирование с коррекцией ошибок Пусть рабочая точка системы совпадает с точкой А на рисунке 4.2 (Eb/N0 = 8 ДБ, PB = 10-2). После нескольких испытаний у заказчика появляются жалобы на качество связи, он полагает, что вероятность появления битовой ошибки должна быть не выше 10-4. Обычным способом удовлетворения требования заказчика является сдвиг рабочей точки из точки А, например, в точку В (рисунок 4.2). В то же время допустим, что, Eb/N0 равное 8 дБ, – это максимальное значение, возможное в данной системе. Из рисунка 4.2 видим что один из возможных выходов из ситуации (компромиссов) – это сдвиг рабочей точки из точки А в точку С. Иными словами, "съехав" по вертикали вниз в точку С на кривой, отвечающей кодированному случаю, можно предоставить заказчику более высокую достоверность передачи данных. Чего это будет стоить? Помимо введения новых компонентов (кодера и декодера), это приведет к увеличению скорости передачи сигнала. Избыточность позволяет приемнику

103

Из рисунка 4.2 следует, что для частоты возникновения ошибок 10-6 использование кодирования позволяет снизить отношение Eb/N0 на 5 дБ. Это улучшение называется эффективностью кодирования. Эффективность кодирования – это снижение необходимого отношения Eb/N0 для системы с кодированием по сравнению с системой без кодирования (при одном и том же виде модуляции) для достижения заданной частоты ошибок.

На рисунке 4.2 кривые для кодированного и некодированного сигналов пересекаются (как правило, при низких значениях Eb/N0). Смысл этого пересечения (порога) в том, что у всех систем кодирования имеется ограниченная способность к коррекции ошибок. Если в блоке имеется больше ошибок, чем способен исправить код, система будет работать плохо. Представим себе, что значение Eb/N0 снижается непрерывно. Что мы увидим на выходе демодулятора? Демодулятор будет допускать все больше и больше ошибок. Следовательно, такое постепенное уменьшение Eb/N0 должно, в конце концов, создать пороговую ситуацию, когда декодер будет переполнен ошибками. При достижении этого порога снижение производительности можно объяснить поглощением энергии избыточными битами, которые не

104

дают никакого выигрыша. Необходимо отметить, что существует класс мощных кодов, называемых турбокодами (turbo code), которые позволяют повысить надежность передачи при низких значениях Eb/N0. У турбокодов точка пересечения графиков находится значительно ниже, чем у других кодов.

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

Отметим, что довольно часто коды с коррекцией ошибок используются по схеме изображенной на рис. 4.2 для кодов обнаружения ошибок. Т.е. в алгоритме FEC к входному k-битовому блоку данных добавляется (n-k) контрольных битов; в результате размер передаваемого блока составляет п бит; все биты исходного k-битового блока содержатся в полученном п-битовом блоке. Для некоторых схем прямого исправления ошибок (например, сверточных кодов, описанных в разделе 5) входная k- битовая последовательность так преобразовывается в п-битовое кодовое слово, что исходные k бит не фигурируют явно в кодовом слове.

4.1 Принципы блочных кодов

Сначала определим термины, которые будут использоваться при рассмотрении блочных кодов. Расстоянием Хэмминга (Hamming distance) d(v1, v2) между двумя п-битовыми двоичными последовательностями v1 и v2 называют число несовпадающих разрядов v1 и v2. Haпример, если

v1 = 011011, v2= 110001,

то

d(v1, v2) = 3.

Рассмотрим теперь метод блочного кодирования с целью коррекции ошибок. Пусть требуется передать определенное количество k-битовых блоков данных. Вместо передачи каждого блока как последовательности k бит, преобразуем каждую k -битовую последовательность в уникальное n- битовое кодовое слово. Рассмотрим эти преобразования на примере для k = 2 и п = 5. имеем следующее присваивание:

Предположим, что кодовое слово было получено на приемной стороне в виде последовательности 00100. Поскольку эта последовательность не

105

соответствует ни одному из кодовых слов, приемник обнаружил ошибку. Как можно ее исправить? Точно узнать какой из блоков данных был передан, невозможно, поскольку шум мог изменить 1, 2, 3, 4 или даже все 5 переданных блоков. Отметим, впрочем, что для преобразования приемлемого кодового слова 00000 в полученную последовательность достаточно изменения одного бита. Соответственно, для преобразования 00111 в 00100 нужно изменить два бита; 11110 в 00100 – три бита; 11001 в 00100 – четыре бита. Таким образом, можно сделать вывод, что с наибольшей вероятностью был передан блок 00000, т.е. искомый блок данных – 00. Подобное рассуждение и есть логика коррекции ошибки. Используя понятие «расстояние Хэмминга», его можно представить в следующем виде

Таким образом, искомое правило коррекции ошибок можно сформулировать так: если получено кодовое слово с ошибкой, его истинное значение принимается равным кодовому слову, которое находится на минимальном расстоянии Хэмминга от искаженного слова. Это правило применимо только тогда, когда для каждого ошибочного кодового слова имеется только одно реальное кодовое слово, находящееся от него на минимальном расстоянии Хэмминга. Для нашего примера приведенное условие не выполняется. Полное количество возможных последовательностей равно 25 = 32, из которых 4 используются как кодовые слова, а 28 являются ошибочными. Для ошибочных кодовых слов можно составить таблицу 4.1.

Из таблицы 4.1 следует, что в 8 случаях ошибочная последовательность находится на расстоянии 2 от различных существующих кодовых слов. Любая такая последовательность может возникнуть в результате двух битовых ошибок, и при этом приемник не может однозначно выбрать правильное кодовое слово. Таким образом, ошибка обнаруживается, но не исправляется. В то же время для всех 1-битовых ошибок полученная последовательность находится на расстоянии 1 только от одного правильного кодового слова, что позволяет принять правильное решение. Следовательно, данный код можно использовать для исправления всех 1-битовых ошибок, но в то же время он не позволяет исправлять ошибки в двух битах. Для иллюстрации сказанного рассмотрим расстояния между существующими (корректными) кодовыми словами

Минимальное расстояние между двумя правильными кодовыми словами равно 3. Следовательно, при появлении 1-битовой ошибки

106

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

Таблица 4.1 Ошибочные кодовые слова

Приведенные выше примеры иллюстрируют важные свойства блочных кодов с коррекцией ошибок. Блочный код (п, k) преобразует k бит данных в п-битовые кодовые слова. В большинстве случаев каждое корректное кодовое слово – это исходные k бит данных плюс (n-k) контрольных битов. Таким образом, структура блочного кода эквивалентна структуре функции вида vс = f (vd), где vd – вектор, состоящий из k бит данных; vс – вектор, состоящий из п бит кодового слова.

В блочном коде (п, k) имеется 2k приемлемых кодовых слов из 2n возможных. Отношение числа избыточных битов к числу битов данных (п - k)/k принято называть избыточностью кода (code redundancy); отношение количества битов данных к полному числу битов R = (k/п) называют степенью кодирования или скоростью кода (code rate). Скорость кодирования это мера того, какая дополнительная полоса потребуется после кодирования, если скорость передачи данных мы хотим сохранить такой же, какая была до кодирования. Например, при степени кодирования R = 1/2 для сохранения скорости передачи данных системе потребуется полоса, в два раза большая, чем та, которая необходима для передачи некодированного сигнала. Для рассмотренного выше примера степень

107

кодирования равна 2/5, следовательно, для сохранения скорости передачи потребуется увеличить ширину полосы в 2,5 раза. Т.е. если скорость передачи сигнала на входе кодера равна 1 Мбит/с, то для сохранения прежних параметров скорость выходного сигнала должна быть равна 2,5 Мбит/с.

Для кода, состоящего из кодовых слов w1, w2,…, ws, где s = 2n, минимальное расстояние кода dmin определяется следующим образом

Можно показать, что если для кода выполняется неравенство dmin > 2t + 1 (t – некоторое положительное целое число), то с помощью данного кода можно исправить все символы, содержащие до t ошибочных битов, включительно. Если dmin > 2t , то можно исправить все символы, содержащие до (t - 1) ошибочных битов. Кроме того, будут обнаружены все символы с t ошибочными битами, исправить которые, в общем случае нельзя. Верно и обратное утверждение — каждый код, позволяющий исправлять до t ошибочных битов, должен удовлетворять условию

условие dmin 2t.

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

где x – наибольшее целое число, не превышающее х (например,

6,3 6). Более того, если нас интересует только обнаружение ошибок, но

не их исправление, количество обнаруживаемых ошибок t удовлетворяет следующему равенству:

Простая верхняя граница для минимального расстояния по Хэммингу dmin двоичного или недвоичного линейного блочного кода (n, k) согласно [20]

Удобно нормировать выражение (4.4) через длину блока п. Это даѐт

называют разделимым кодом с максимальным расстоянием. Исключая случаи тривиального кода (п, 1) для передачи двоичных сообщений с повторением, не существует двоичных разделимых кодов с максимальным расстоянием. Фактически верхняя граница в (3.19) для двоичных кодов весьма неточная. С другой стороны, существуют недвоичные коды с dmin n k 1. Например,

коды Рида-Соломона, которые представляют подкласс БЧХ кодов, являются разделимыми кодами с максимальным расстоянием.

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

добавляемый проверочный символ увеличит минимальное расстояние на 1. Код

(п +1, k) называется расширенным кодом.

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

Укороченный код (n – l, k-l) состоит из 2k l кодовых слов. Минимальное расстояние этих 2k l кодовых слов по крайней мере не меньше, чем минимальное расстояние исходного (п, k) кода.

Теперь рассмотрим конкретные примеры кодов с коррекцией ошибок.

4.2 Коды Хэмминга

Коды Хэмминга – это семейство блочных кодов с коррекцией одиночных ошибок, которые характеризуются следующими параметрами:

109

Для кодов Хэмминга r 3. Согласно (4.7) существуют коды Хэмминга при r = 3 – (7,4), r = 4 – (15,11), r = 5 – (31,11) и т.д.

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

Коды Хэмминга созданы для исправления 1-битовых ошибок. Для начала определим необходимую длину кода. Коды Хэмминга реализуются так же, как методы обнаружения ошибок (см. рис. 3.2) – в процессе кодирования сохраняются k бит данных и добавляются r = (n-k) контрольных битов. При декодировании используются две последовательности из r = (n-k) бит, одна из которых является кодовым словом входящего сигнала, а другая рассчитывается на основе полученных битов данных Последовательности побитно сравниваются с помощью логического исключающего ИЛИ. Результат сравнения называют синдромом. Биту синдрома присваивается значение 0, если биты двух последовательностей совпадают, и 1 – в противном случае. Синдром – это r = (n-k) – битовое слово в диапазоне от 0 до 2(n-k) - 1. Значение 0 свидетельствует об отсутствии ошибки. Если же ошибка присутствует, ее местоположение определяется из синдрома.

Для удобства генерируемый синдром должен обладать следующими свойствами:

•Если синдром состоит только из нулей — ошибки не обнаружены;

•Если один и только один бит синдрома равен 1 — ошибка присутствует в одном из контрольных битов; в этом случае исправлять ошибку не нужно;

•Если синдром содержит более одного бита со значением 1, он является указателем на положение ошибки в слове, для исправления которой указанный бит инвертируется.

Поскольку ошибочным может быть любой из k бит данных или r = (n-k) проверочных битов, должно выполняться следующее соотношение

Приведенное уравнение определяет количество битов, необходимое для исправления 1-битовой ошибки в слове, содержащем k бит данных.

Из (4.8) следует

110