Циклические коды.

Циклические коды

Оглавление

Циклические коды являются частным случаем линейных и представляют собой наиболее разработанную часть последних. Основным их достоинством является простота технической реализации, благодаря чему они и обратили на себя внимание специалистов. Ценным свойством таких кодов является способность обнаруживать не только одиночные ошибки, но и пакеты ошибок. Пакетом ощибок длиной L называют число разрядов сообщения, искаженных подряд.
Свое название циклические коды получили из-за следующего свойства: если комбинация
a_n-1a_n-2 ... a₁a₀ относится к коду, то комбинация, полученная путем циклического сдвига элементов, т.е. комбинация
a_n-2 ... a₁a₀a_n-1, также относится к коду. Направление сдвига не имеет значения. Один сдвиг в одном направлении эквивалентен n-1 сдвигам в другом направлении.

Математической основой построения циклических кодов является представление кодовых комбинаций в виде многочленов от некоторой переменной x с коэффициентами, равными элементам кодовых комбинаций, и операцией по mod2. Кодовая комбинация

a_n-1a_n-2 ... a₁a₀ представляется многочленом
a_n-1x^n-1 + a_n-2x^n-2 + ... + a₁x + a₀

Пример:

Многочлен кодовой комбинации 01001 имеет вид x³ + 1.

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

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

Кодовый полином

Циклический код строится с помощью так называемого порождающего многочлена g(x) степени r. Признаком принадлежности n-разрядной комбинации данному коду является делимось соответствующего ей многочлена на порождающий. Если многочлен принятой комбинации делится на порождающий, то считается, что она совпадает с посланной. Если деление происходит с остатком, то принятая комбинация к коду не относится, т.е. произошло наложение ошибки. Вид остатка при достаточной избыточности позволяет указать место ошибки.

Способы образования кодового многочлена:

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

Пример:

Информационным элементам 1111 соответствует информационный многочлен

P(x) = x³ + x² + x + 1. Пусть порождающий многочлен
g(x) = x + 1. Произведение
P(x)*g(x) = x⁴ + 1, что соответствует кодовой комбинации 10001, в которой исходные информационные элементы не сохранены. Для исключения этого недостатка используют следующий прием.

2. Информационный многочлен P(x) умножается на x^r, где r - старшая степень образующего многочлена g(x), и полученное выражение делится на
g(x). В результате получится чястное Q(x) и остаток R(x) степени меньше r:

x^rP(x) = g(x)Q(x) + R(x). Перенесем R(x) в левую часть:
x^rP(x) + R(x) = g(x)Q(x) . Правая часть последнего равенства кратна g(x) и, следовательно, является кодовым многочленом F(x), т.е.
x^rP(x) + R(x) = F(x) . Именно так получаются кодовые многочлены. Первое слагаемое кодового многочлена имеет нулевые коэффициенты в r младших членах. Этот многочлен соответствует сдвинутой влево на r разрядов информационной части P(x). Степень многочлена R(x) меньше r, поэтому его коэффициенты не изменяют нулевые коэффициенты первого многочлена при их сложении. Таким образом, информационные элементы в кодовой комбинации сохраняются, а проверочными элементами являются коэффициенты остатка R(x), число которых равно степени порождающего многочлена.

Пример:

Определить кодовую комбинацию при информационной части 101011 и порождающем многочлене

g(x) = x² + x + 1. Очевидно,
P(x) = x⁵ + x³ + x + 1,
F(x) = x⁷ + x⁵ + x³ + x² + x + 1, чему соответствует кодовая комбинация 10101111. Шесть первых элементов - информационные, остальные два - проверочные, соответствующие остатку
R(x) = x + 1.

Свойства циклических кодов:

Минимальное кодовое расстояние d циклического кода не превышает числа членов порождающего многочлена.
Циклический код с порождающим многочленом степени r>1 обнаруживает любую одиночную и любую двойную ошибку, т.е. имеет d>3.
Код с порождающим многочленом x + 1 является кодом с четным числом единиц.
Циклический код с порождающим многочленом g(x)(x+1) имеет d>4.
Код с порождающим многочленом g(x) степени r обнаруживает все пакеты ошибок длины r или меньше.

Коды Боуза - Чоудхури - Хоквингема (БЧХ)

Коды БЧХ относятся к циклическим кодам и являются лучшими конструктивными кодами для каналов с независимыми ошибками. Конструктивность кодов заключается в сравнительной легкости выбора порождающего многочлена по заданной корректирующей способности кода.
Порождающие многочлены кодов БЧХ задаются корнями. Корни многочлена являются элементами расширения поля, которое включает элементы 0 и 1. Поле образуют многочлены, являющиеся остатками от деления на некоторый неприводимый многочлен p(x). Если степень p(x) равна s, то число различных остатков равно 2^s, т.е. поле состоит из 2^s элементов.
Корректирующая способность кода связана с корнями порождающего многочлена следующим образом. Если среди корней порождающего многочлена g(x) содержится b последовательных степеней a^c, a^c+1, ..., a^c+b-1, то минимальное кодовое рассстояние этого кода не меньше b+1.

Предыдущий

Следующий