Кодирование информационных сигналов.

Кодирование (Forward Error Correction) – математическая задача, основанная на высшей алгебре. При кодировании используют поля Галуа: GF(2) и GF(m). В большинстве кодов оперируют в полях Галуа GF(2). В этом случае операции сложения и вычитания заменяют операцией сложения по модулю 2.

3.2.1. Блочное кодирование.

В основе блочного кодирования лежит понятие "расстояния по Хэммингу". Закодированное слово – это вектор длиной n, где к информационному вектору длиной k добавлены n-k проверочных бит (в частном случае, бит паритета). "Расстояние по Хэммингу" - это мера разницы между двумя кодовыми словами C_i и C_i в (n,k). Расстояние по Хэммингу равно числу ненулевых бит в выражении C_i + C_i в GF(2), где знаком "+" обозначена операция сложения по модулю 2. Так, если исходные слова C_i и C_i отличаются в одном бите, то после кодирования разница между ними может составлять 3, 5, 7 и более бит.

По назначению блочные коды подразделяют на проверочные коды (например, CRC – Check Redundancy Code) и коды, исправляющие ошибки.

Информационный блок можно представить вектором i, и к нему добавляют проверочную часть – вектор b = i´P, где Р – порождающая матрица. В результате по каналу связи передают кодовое слово

c = i + b = i ´ G,

где G=[I P] называют порождающей матрицей систематического кода. Она имеет размер [k´n].

При декодировании принятого кодового слова используют проверочную матpицу H размера [(n-k)´n], удовлетворяющую условию ортогональности,

G´H^т=0,

где т – символ транспонирования.

Если при прохождении по каналу связи в кодовом слове с появятся ошибки, так что принятое слово w=с+e, где e – вектор ошибок, то, выполняя при декодировании операцию

w´H^т=(с+e)´H^т = i´G ´H^т + e´H^т = e´H^т ,

получаем вектор синдрома s = w´H^т = e´H^т длиной (n–k), зависящий только от вектора ошибок и проверочной матрицы. Если ошибки отсутствуют, то s = 0.

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

Процесс поиска можно пояснить с помощью двумерной модели на плоскости (рис.3.3). Каждое кодовое слово – точка в n-мерном пространстве. Минимальное расстояние по Хэммингу d_min определяют как минимум расстояния по всем возможным парам различных слов.

Рис.3.3. К определению корректирующей способности кода

Корректирующая способность кода – это сфера, определяемая числом бит, которое может быть исправлено (радиус t на рис. 1.1). Общее число обнаруженных e_d и исправленных e_c ошибок подчиняется правилу

e_d + e_c ≤ d_min – 1, причем e_c ≤ e_d .

Так, если кодовое расстояние d_min = 7, то можно обнаружить и исправить 3 ошибки (радиус t = 3). Можно построить код так, что будут обнаружены 4 ошибки, но исправлены только 2 (сузить радиус t). Во всяком случае, если в принятом слове будет более 4-х ошибок, то будет принят неверный результат, т.е. процесс декодирования– это всегда вероятностный процесс.

Существует большое разнообразие блочных кодов, начиная от проверочных кодов (CRC – Check Redundancy Code) до кодов, исправляющих групповые ошибки. Пример такого кода – код Рида-Соломона 1-го рода, используемый в стандарте cdma2000 при передаче телефонии вверх (в фундаментальном канале от мобильной станции к базовой). Здесь при декодировании используют мягкое решение, основанное на нахождении корреляционной функции принятого сигнала и правильного кода. Каждые 6 бит информационного блока кодируют 64-битовым словом функции Уолша wal₀…. wal₆₃ (рис.3.4). При приеме сигнал подают на 64 коррелятора и правильный ответ определяют по максимуму полученных корреляционных функций.

При использовании жестких решений принятый сигнал квантуют (каждому биту присваивают значение или "0" или "1"), а затем проверяют синдром. Ошибки определяют по полученному синдрому. Например, код (8,5) позволяет найти и исправить одну ошибку при передаче 5-битового слова (табл. 3.1).

Рис.3.4. Функции Уолша

Таблица 3.1.

3.2.2. Сверточное кодирование.

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

Закон кодирования определяет n образующих полиномов q₁ … q_n. Рассмотрим простейший СК (2,1,3) с полиномами

q₁ = 1+z² ;

q₂ = 1+z+z² ,

Будем передавать последовательность 11101, начиная с младшего бита. После кодирования имеем последовательность 1001001011, которую передают по каналу связи, также начиная с младшего бита. Декодирование основано на использовании алгоритма Витерби (алгоритм максимального правдоподобия). На рис.3.5. приведен алгоритм Витерби с жестким решением, в основе которого лежит минимизация расстояния по Хэммингу.

Рис.3.5. Алгоритм Витерби с жестким решением.

Алгоритм Витерби с мягким решением –максимум корреляционной метрики.

Пример избыточного кодирования – технология GPRS в стандарте GSM (табл.3.2)

В GSM при сверточном кодировании используют полиномы

q₁ = 1 + z³ + z⁴ и q₂ = 1 + z + z³ + z⁴ или при записи в восьмиричном коде (31, 33).

Таблица 3.2.

П

3.. Перемежение (рис.3.6).

Рис. 3.6. Блоковое перемежение

1 В более редких случаях соту делят на 6 секторов, используя 6 направленных антенн с раскрывом сектора 60°.

1 От английского глагола to page - выкликать.

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

1 Согласно федеральному стандарту абонентам сотовых сетей присваивают номера вида 7 DEF ХХХХХХХ, где 7 - код России, DEF - код сети подвижной связи. В Северо-Западном регионе используют коды DEF: 901 – сети SkyLink, 904 – TELE 2, 903, 905, 906, 909, 960 – БиЛайн, 911 – MTC, 921 – Мегафон. Кроме федеральной нумерации, на практике также используют местную нумерацию абонентов сотовой сети, подключая MSC непосредственно к ТфОП, минуя междугородный коммутатор.

1 Мощность в дБм связана с мощностью в милливаттах соотношением Р(дБм) = 10 lg Р(мВт).

[1] В каждой соте выделяют одну частоту: частоту маяка, которая в соте фиксирована и не изменяется при работе с прыгающей частотой.