Методы построения циклических кодов

Лекция 15. Методы построения циклических кодов.

Выбор образующего многочлена по заданному объему кода и заданной корректирующей способности.

По заданному объему кода однозначно определяется количество информационных разделов.

Далее имеется min количество m, обеспечивающее необходимую корректирующую способность кода. Для ЦК – это нахождение соответствующего g(x).

14.2.1 Обнаружение одиночных ошибок (d=2).

Любая принятая по КС КК может быть представлена:

h(x)=f(x)

f(x) – неискаженная КК, - вектор ошибки.

Понятно что F(x) должна делится на g(x) без остатка.

Вектор ошибки имеет “1” в искаженных разрядах и “0” – в правильно принятых. Вектор ошибки имеет вид:,

где i- N искаженного разряда. Следовательно, многочлен (одночлен) х не должен делиться на g(x). Таким наиболее простым многочленом g(x) является х+1 остаток от деления на х+1 может иметь два значения:.

Т.е. при любом числе информационных символов необходим только 1 контрольный разряд.

Это – циклический код с проверкой на четность. Т.к. в разрядах КК данного ЦК будет число единиц.

14.2.2 Исправление одиночных или обнаружение двойных ошибок (d=3).

Для исправления одиночной ошибки как уже ранее говорилось, предварительно необходимо локализовать её, т.е. найти место, где произошла ошибка.

Следовательно, как и в случае с КК каждой одиночной ошибке должен соответствовать свой опознаватель.

Т.к. в ЦК роль опознавателя играют остатки от деления на g(x), то g(x) должен обеспечить необходимое число остатков.

Наибольшее число остатков дает неприводимый g(x):,

где m=n-k – степень многочлена.

Следовательно, необходимым условием исправления любой ошибки является выполнение неравенства:,

где – число комбинаций по 1 в КК из n символов.

Тогда:

Зависимость между n, m и k.

m
n
k	n	-	k

С другой стороны, g(x) должна быть делителем многочлена (). Все полиномы удовлетворяющие этим требованиям приведены в соответствующих таблицах в учебниках: Дмитриев, Тутевич, Шувалов и т.д.

Цель лекции: ознакомление cметодами построения циклических кодов

Содержание:

а) методы построения циклических кодов;

б) декодирование ЦК;

1) Прямые умножения.

Недостатки: такой код не является систематическим поэтому не получил применения.

1011…..

2) Систематические ЦК.

Умножим КК на одночлен х, имеющий степень = степени g(x).

Делим произведение на образующий элемент g(x):

Умножим равенство (*) на g(x) и перенесем r(x) в левую часть, равенства получим:

f(x)= g(x)* g(x) =.