Неприводимые многочлены

№	Вид неприводимого многочлена
	x+1
	x2+x+1
	x3+x+1 x3+x2+1
	x4+x+1 x4+x3+1 x4+x3+x2+x+1
	x5+x2+1 x5+x3+1 x5+x3+x2+x+1 x5+x4+x2+x+1 x5+x4+x3+x+1 x5+x4+x3+x2+1
	x6+x+1 x6+x3+1 x6+x4+x2+x+1 x6+x4+x3+x+1 x6+x5+1 x6+x5+x2+x+1 x6+x5+x3+x2+1 x6+x5+x4+x+1 x6+x5+x4+x2+1

Обнаружение и исправление одиночных искажений в циклических кодах при кодовом расстоянии d_min=3 осуществляется следующим образом:

1. Принятая комбинация циклического кода F^’(1,0) делится на образующий многочлен P(x), она считается достоверной, если остаток от деления равен нулю, в противном случае комбинация принята с искажением.

2. Определяется вес остатка p₀. При p₀ £ S принятая комбинация суммируется по модулю 2 с полученным остатком, образованная сумма определяет исправленную комбинацию (переданную комбинацию).

3. При p₀>S производят циклический сдвигпринятой кодовой комбинации на один разряд влево. Полученная комбинация снова делится на образующий многочлен. Если в результате второго деления вес полученного остатка меньше или равен числу исправляемых искажений p₀£ S, то делимое суммируется с остатком.

4. Производится циклический сдвиг полученной суммы на один разряд вправо. Образованная после сдвига кодовая комбинация м является восстановленной (исправленной) комбинацией.

5. Если в результате второго деления условие p₀£ S не выполняется, то указанная операция продолжает выполняться до тех пор, пока не будет реализовано неравенство p₀£ S.

6. Полученная кодовая комбинация в результате последнего циклического сдвига суммируется с остатком от деления этой комбинации на образующий многочлен.

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

Пример.

При передаче кодовой комбинации циклического кода, исправляющего одиночные ошибки, произошло искажение в пятом разряде. Передавалась кодовая комбинация 11 0 0101, принятая кодовая комбинация имеет вид 11 1 0101. В рассматриваемом примере число исправляемых искажений S=1, число информационных символов кодовой комбинации k=4, число проверочных символов r=3. Следовательно, образующий многочлен будет иметь вид P(x)=x³+x²+1.

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

1. Деление принятой кодовой комбинации на образующий многочлен P(x)=x³+x²+1 ® 1101.

1110101 ë 1101

1101

1101

111 остаток p₀=3.

2. При сравнении веса остатка (p₀=3) с числом исправляемых искажений S=1, имеем p₀ > S. Условие p₀ £ S не выполняется.

3. Производится циклический сдвиг принятой кодовой комбинации на один разряд влево и повторное деление на образующий многочлен P(x).

1101011 ë 1101

1101

011 остаток (вес остатка p₀=2). Условие p₀£S не выполняется.

4. Сдвиг поразрядно влево и деление на образующий многочлен осуществляется до тех пор пока не будет выполнено условие p₀£S.

1010111 ë 1101

1101

1101

1101

110 остаток p₀=2>S

0101111 ë1101

1101

1101

1 остаток p₀=1=S. Условие p₀£S выполнено.

5.При суммировании по модулю 2 последнего делимого 0101111 с остатком, получают комбинацию

Å

1

6. Производится циклический сдвиг вправо полученной комбинации на 3 разряда (т.к. трижды при делении на образующий многочлен влево сдвигалась принятая кодовая комбинация).

0101110 ® 0010111 ® 10011 ® 11 0 0101.

Последняя кодовая комбинация полностью совпадает с переданной неискаженной кодовой комбинацией, т.е. произошло исправление принятой с искажением кодовой комбинации.

7.1.2.3. Коды Боуза-Чоудхури-Хоквингема (БЧХ) – относятся к классу циклических кодов и по своей разрешающей способности позволяют обнаруживать и исправлять два и более искажений кодовых комбинаций, возникающих при их передаче по каналам связи. Для таких кодов кодовое расстояние определяется как d_min³5. Образующий многочлен построения множества кодовых комбинаций кодов БЧХ формируется на основании заданного количества кодовых комбинаций n, которое в сою очередь определяется полным множеством кодовых комбинаций кодов БЧХ - N и по числу исправляемых искажений S. Число элементов кодовой комбинации БЧХ определяется как n=2^m-1, где m - любое целое число (3, 4, 5,...), число проверочных элементов кодовой комбинации выбирается из условия r£ m·S = (log₂(n+1))·S, а число информационных элементов будет равно k=n-r.

Образующий многочлен P(x) кода БЧХ представляет собой произведение нечетных минимальных многочленов m_i(x) и является их наименьшим общим кратным (НОК), т.е. наименьшим многочленом который без остатка делится на каждый минимальный многочлен m_i(x), где i=(1, 3, 5,..., (2S-1)). Порядок многочлена P(x) равняется наименьшему общему кратному P(x)=НОК[m₁(x) m₃(x)... m_2S-1(x)]. Значения минимальных многочленов приведены в таблице 4.11.

Таблица 4.11