 |
Основные сведения о методах помехоустойчивого кодирования
|
|
|
|
Лабораторная работа № 3
Помехоустойчивое кодирование
Основные сведения о методах помехоустойчивого кодирования
Помехоустойчивые коды применяют для уменьшения влияния помех на сообщения. Построение помехоустойчивых кодов основано на добавлении к исходной комбинации из k символов r контрольных символов. Закодированная комбинация будет составлять n символов. Поэтому помехоустойчивые коды часто называют (n, k)-коды.
К простейшим помехоустойчивым кодам относят следующие коды для обнаружения ошибок:
1. код четности, который образуется путем добавления к передаваемой комбинации, состоящей из k информационных символов, одного контрольного символа (0 или 1), так, чтобы общее число единиц в передаваемой комбинации было четным;
2. код с постоянным весом, который содержит постоянное число единиц и нулей;
3. корреляционный код (код с удвоением), при построении которого 1 преобразуется в 10, а 0 – в 01;
4. инверсный код, получаемый при добавлении к исходной комбинации такой же комбинации по длине: если в исходной комбинации четное число единиц, то добавляемая комбинация повторяет исходную комбинацию, если нечетное – то добавляемая комбинация является инверсной относительно исходной;
5. код Грея, для построения которого используются следующие правила:
где AnAn –1… A 0 – исходная двоичная комбинация, а anan –1… a 0 – соответствующий ей код Грея.
Свойства помехоустойчивых кодов определяются кодовым расстоянием. Кодовое расстояние d - это минимальное число символов, в которых одна кодовая комбинация отличается от другой. Если d = 1, то код не обладает помехоустойчивыми свойствами, если d = 2, то код позволит обнаружить одиночные ошибки и т.д. Таким образом, увеличивая кодовое расстояние можно увеличить помехоустойчивость кода. В общем случае кодовое расстояние определяется по формуле
|
|
|
d = t + l + 1,
где t – число исправляемых ошибок, l – число обнаруживаемых ошибок (обычно l > t).
Коды, которые позволяют обнаруживать и исправлять ошибки, называют корректирующими кодами. Большинство корректирующих кодов являются линейными кодами. Линейные коды – это такие коды, у которых контрольные символы образуются путем линейной комбинации информационных символов. Кроме того, корректирующие коды являются групповыми кодами. Групповые коды Gn – это такие коды, которые имеют одну основную операцию. При этом должно соблюдаться условие замкнутости (т.е. при сложении двух элементов группы получается элемент, принадлежащий этой же группе). Число разрядов в группе не должно увеличиваться. Этому условию удовлетворяет операция поразрядного сложения по модулю 2. В группе, кроме того, должен быть нулевой элемент.
Для построения кода способного обнаруживать и исправлять одиночную ошибку необходимое число контрольных разрядов будет составлять
,
где k – число разрядов исходной кодовой комбинации, n – число разрядов после добавления контрольных символов. Если необходимо исправить две ошибки, то
.
В этом случае обнаруживаются однократные и двукратные ошибки. В общем случае, число контрольных символов определяется неравенством Хэмминга:
.
Одними из наиболее широко применяемых корректирующих кодов являются циклические коды. Циклическими кодами называют специальную группу кодов, которые описываются полиномиально. Полиномиальное описание кодовых комбинаций заключается в следующем. Пусть, например, имеется кодовая комбинация 101101, тогда ее можно представить в виде полинома
A (X) = 1× x 5 + 0× x 4 + 1× x 3 + 1× x 2 + 0× x 1 + 1 = x 5 + x 3 + x 2 + 1.
Циклические коды относятся к систематическим (n, k)-кодам, в которых контрольные r и информационные k разряды расположены на строго определенных местах: n = k + r. При выполнении действий над циклическими кодами в многочленной форме операции умножения и вычитания выполняются как сложение по модулю 2.
|
|
|
Для получения циклического кода заданный многочлен h (х) сначала умножается на одночлен хn – k, затем делится на образующий многочлен g (х). В результате получаем:
.
После этого к произведению h (х) хn – k добавляется остаток R (x):
F (x) = Q (x) · g (x) = хn – k h (x) + R (X).
При декодировании, принятую кодовую комбинацию необходимо разделить на g (x). Наличие остатка указывает на ошибку. Образующий полином g (х) является сомножителем при разложении двучлена хn +1. Сомножителями разложения двучлена являются неприводимые полиномы из таблицы 2.
Образующий полином выбирают следующим образом. По заданной кодовой комбинации k определяют число контрольных символов из соотношения r = log2(n + 1) или по эмпирической формуле
r = [log2{(k + 1) + [log2(k + 1)]}].
Соотношение значений n, k, r показано в таблице 1.
Таблица 1
Соотношение между n, k, r
| n | 9…15 | 17…31 | 33…63 | 65…127 | ||||
| k | 5…11 | 12…26 | 27…57 | 28…120 | ||||
| r |
Затем из таблицы 2 выбирают самый короткий неприводимый полином со степенью, равной числу контрольных символов.
Например, пусть требуется закодировать комбинацию вида 1101, что соответствует h (х) = х 3 + х 2 + 1.
1. Определяем число контрольных символов: r = 3.
2. Выбираем образующий полином: g (х) = х 3 + х + 1, т.е. 1011.
3. Умножаем h (х) на хr:
h (x) xr = (x 3 + x 2 + 1) x 3 = x 6 + x 5 + x 3,
что соответствует 11010000.
4. Разделим полученное произведение на образующий полином g (х):
5. Остаток суммируем с h (х) хr:
F (x) = (x 3 + x 2 + 1)(x 3 + x + 1) = (x 3 + x 2 + 1) x 3 + 1, т. е. 1101001.
Полученная кодовая комбинация F (x) циклического кода содержит исходную комбинацию h (х) = 1101 и контрольные символы R (х) = 001. Очевидно, что закодированное сообщение делится на образующий полином без остатка.
Для рассмотренного примера исходное сообщение является одной из 16 возможных комбинаций 4-разрядного кода. Это значит, что если все сообщения необходимо преобразовать в циклический код, то каждое из них необходимо кодировать, выполняя такую же последовательность вычислений, что и для h (x) = 1101. Однако выполнять дополнительные 15 расчетов (в общем случае 2 n – k – 1 расчетов) нет необходимости, если составить образующую (порождающую) матрицу Gk ´ n, которая составляется на основе единичной матрицы Ik, к которой справа дописывается матрица остатков Rk ´( n – k ):
|
|
|
.
Матрица Rk ´( n – k ) содержит остатки от последовательного деления единицы с нулями на образующий многочлен g (x), например:
1000000 / 1011 = 1 (1–й остаток – 011)
011000 / 1011 = 0 (2–й остаток – 110)
11000 / 1011 = 1 (3–й остаток – 111)
1110 / 1011 = 1 (4–й остаток – 101).
При делении, начиная со второго шага, в качестве делимого используется остаток, найденный на предыдущем шаге. Так же отметим, что располагать остатки в матрице нужно, начиная с последнего. Таким образом, для рассматриваемого примера образующая матрица имеет вид
Матрица G 4´7 уже содержит 4 комбинации циклического кода, а остальные 12 ненулевых комбинаций находятся суммированием по модулю 2 всевозможных сочетаний строк образующей матрицы
Для обнаружения и исправления ошибок принятая комбинация делится на образующий многочлен g (х). Если остаток R (х) будет равен 0, то комбинация принята без ошибок. Наличие ненулевого остатка свидетельствует о том, что комбинация принята искаженной. Значение остатка совпадет с одним из опознавателей транспонированной проверочной матрицы 
, который и укажет на местоположение. Проверочная матрица имеет вид:
,
например, для циклического кода из примера проверочная матрица будет следующей
.
Тогда, если вместо 1101001 получена кодовая комбинация 1100001, то остаток от деления 1100001 на 1011 будет равен 011. Остаток совпадает с четвертой строкой матрицы :
.
Это означает, что ошибка содержится в 4-м разряде, исправив который получаем правильную комбинацию 1101001.
Таблица 2
Образующие полиномы
| g (x) | Полином | g (x) | Полином |
| g (x) | x +1 | g 1(x 6) | x 6+ x +1 |
| g (x 2) | x 2+ x +1 | g 2(x 6) | x 6+ x 3+1 |
| g 1(x 3) | x 3+ x +1 | g 3(x 6) | x 6+ x 5+1 |
| g 2(x 3) | x3+x2+1 | …………… | …………… |
| g 1(x 4) | x 4+ x +1 | g 1(x 7) | x 7+ x +1 |
| g2(x4) | x 4+ x 3+1 | g 2(x 7) | x 7+ x 3+1 |
| g 3(x 4) | x 4+ x 3+ x 2+ x +1 | g 3(x 7) | x 7+ x 3+ x 2+ x +1 |
| g 1(x 5) | x 5+ x 2+1 | …………… | …………… |
| g 2(x 5) | x 5+ x 3+1 | g 1(x 8) | x 8+ x 4+ x 3+ x +1 |
| g 3(x 5) | x 5+ x 3+ x 4+ x +1 | g 2(x 8) | x 8+ x 4+ x 3+ x 2+1 |
| g 4(x 5) | x 5+ x 4+ x 2+ x +1 | …………… | …………… |
| g 5(x 5) | x 5+ x 4+ x 3+ x +1 | g 1(x 9) | x 9+ x +1 |
| g 6(x 5) | x 5+ x 4+ x 3+ x 2+1 | g 2(x 9) | x 9+ x 4+ 1 |
|
|
|
|
|
|
