Выбор образующего многочлена циклического кода по требуемой корректирующей способности
Число проверочных разрядов – «m» и вид образующего многочлена g(x) зависят от числа ошибок, которые необходимо исправлять.
Выбор образующего многочлена для обнаружения одиночных ошибок
Принятую искаженную кодовую комбинацию можно представить как:
,
где ЗККi+j – запрещенная (искаженная) кодовая комбинация;
ƒi(x) – i-тая разрешенная кодовая комбинация;
– вектор ошибки в j-том разряде, то есть X j.
Ошибка обнаруживается, если при делении ЗККi+j на g(x) образуется остаток. Но ƒi(x) делится на g(x) без остатка. Поэтому нужно выбрать такой многочлен g(x), чтобы при делении на g(x) получился остаток.
Из всех многочленов g(x), удовлетворяющих этому условию необходимо взять тот, который имеет минимальную степень, так как это обеспечивает минимум проверочных разрядов. Кроме того, g(x) должен входить в разложение многочлена . Таким многочленом является многочлен , который при делении всех элементов кольца на него дает два случая:
- R(x) = 0, то есть элемент кода принадлежит идеалу;
- R(x) = 1, то есть элемент кода имеет ошибку.
Вектор ошибки X j имеет единицу в одном из разрядов.
Например, для кода (7; 4) ошибка в четвертом разряде имеет вид 0001000. При делении X j на всегда получаем остаток R(x) = 1.
Обратим внимание, что для обнаружения одиночной ошибки дистанция между двумя Р.К.К. должна быть не менее, чем в 2 символа, так как d ≥ r + 1 = 1 + 1 = 2 и в принятом нами тоже 2 символа.
Как получить Р.К.К. рассмотрим позднее (в следующем параграфе), а g(x) выбираем из таблицы многочленов, не приводимых над полем (таблица 6.1) по условию d = 2. Таких многочленов всего один .
Из соотношения (2n–k – 1) ≥ числа ошибок, которые мы хотим обнаруживать. Так как мы обнаруживаем лишь факт есть ошибка (в любом разряде) или ее нет, то неравенство можно записать так:
2n–k – 1 ≥ 1, то есть, 2n–k ≥ 2, то есть n – k = 1; n = k + 1.
Это соответствует одному дополнительному разряду, который следует заполнить нулем или единицей, так, чтобы полученная Р.К.К. делилась на без остатка. Р.К.К. будет делится на без остатка, если в ней будет четное число единиц. Убедимся в этом.
Пусть k = 7. Имеем К.К. .
Дополним ее поверочным разрядом: так как в информационных разрядах всего 3 единицы, то в поверочном разряде должна быть записана единица, чтобы полученная Р.К.К. делилась на без остатка. Где ее записывать, вначале К.К. или в конце значения не имеет.
Поделим Р.К.К. на .
Замечание: циклический код с проверкой на четность обнаруживает не только единичные, но и любые ошибки нечетной кратности, так же как не обнаруживает любые ошибки четной кратности. После того как вы ознакомились с содержанием данного раздела, предлагаем вам решить задачу. http://peredacha-informacii.ru/ Если у вас в процессе решения возникнут затруднения, то предлагаем вам воспользоваться помощью.
|