- •Циклический код
- •Циклический код
- •Циклические коды
- •Среди групповых кодов можно выбрать такие, у которых строки связаны условием цикличности,
- •Сдвиг осуществляется справа налево, а крайний левый символ перемещается в конец строки, т.е.
- •Любые «k» строк этой матрицы линейно независимы и могут служить основой для получения
- •В циклическом коде кодовые комбинации удобно записывать в виде многочлена (n – 1)
- •Например:
- •Посмотрим, делится ли полученный
- •Образующий многочлен g(x).
- •Для обнаружения ошибок
- •Широко применяется потому что
- •Циклический код
- •Разрешенную кодовую комбинацию Ц.К. можно рассматривать как
- •Обе коммутативны
- •Правила выполнения операций
- •Правило 1. Сложение
- •Правило 2. Умножение
- •Пример: Сдвиг с переносом единицы из старшего разряда в младший
- •Поделим на многочлен
- •ИДЕАЛ
- •Количество элементов в идеале зависит от вида g(x)
- •Циклический код
- •Разрешенная кодовая комбинация Ц.К. должна делиться на g(x) без остатка
- •поэтому iтую строку матрицы ƒi(x) можно записать:
- •делится на g(x) без остатка.
- •Если мы выбрали g(x) так, что он является делителем двучлена то :
- •Наибольшее число остатков дает неприводимый многочлен степени «m», когда m; n и k
- •Выбор образующего многочлена циклического кода по требуемой корректирующей способности
- •Принятую искаженную кодовую комбинацию можно
- •Выбираем многочлен g(x), чтобы при делении на g(x) получился остаток
- •Выбираем многочлен g(x), чтобы при делении на g(x) получился остаток
- •Например, для кода (7; 4)
- •Обратим внимание,
- •во многих случаях целесообразно
- •.К.К. будет делится на без остатка, если в ней будет четное число единиц.
- •Где ее записывать, вначале К.К. или в конце значения не имеет
- •Замечание
- •Неприводимые многочлены
- •Еще таблица
- •Выбор образующего многочлена циклического кода по требуемой корректирующей способности
- •Для исправления одиночных ошибок в n разрядной К.К. необходимо определить, какой разряд был
- •Из последнего равенства определяется число проверочных разрядов – это целое число с округлением
- •Для исправления одиночных ошибок минимальная дистанция между двумя Р.К.К. должна быть:
- •Например:
- •Нас интересуют
- •Векторы ошибок младших разрядов имеют вид:
- •Степени соответствующих им многочленов меньше степени образующего многочлена g(x). Поэтому они сами являются
- •Однако использовать для тех же целей многочлен
- •Из приведенного примера следует, что в качестве образующего следует выбирать такой неприводимый многочлен
- •Выбор образующего многочлена циклического кода по требуемой корректирующей способности
- •Вектор двойных ошибок можно записать:
- •Таким образом, образующий многочлен, исправляющий одиночные ошибки, может обнаруживать и двойные ошибки. Но
- •Выбор образующего многочлена циклического кода по требуемой корректирующей способности
- •Если известен образующий многочлен g(x) степени m, обнаруживающий ошибки кратности до R включительно
- •Например:
- •Это эквивалентно добавлению еще одного проверочного разряда,
- •Но возможно и другое решение: n оставляется равным 15,
- •Чтобы построить код, обнаруживающий ошибки произвольной кратности R следует :
- •Методы построения
- •Зная кодовую комбинацию из «k» информационных символов – ai(x) и образующий многочлен –
- •Методы построения циклического кода
- •Информационный многочлен ai(x) умножается на образующий многочлен g(x)
- •Пример
- •Для получения Р.К.К. –умножим и получим
- •В линии связи произошла ошибка , на выходе из л.с. получим кодовую комбинацию:
- •На приемной стороне, чтобы судить есть ошибка или нет, необходимо принятую кодовую комбинацию
- •Получили остаток, отличный от нуля.
- •До ошибки в четвертом разряде остаток соответствует самой ошибке, а начиная с ошибки
- •В примере остаток , то есть ошибка в пятом разряде. Исправим ошибку:
- •Но, получив ƒi(x), мы не получили ai(x), то есть снова приходится делить ƒi(x)
- •Методы построения циклического кода
- •Чтобы получить разделимый код :
- •Разрешенная кодовая комбинация ƒi(x) получается путем сложения и r(x)
- •Степень многочлена g(x) – m, а степень остатка – (m – 1).
- •Пример (тот же)
- •Если в линии связи произошла ошибка в пятом разряде , то будем иметь
- •Исправим принятую К.К.:
- •Методы построения циклического кода
- •Ц.К. является разновидностью группового кода (Г.К.),
- •Зная значения информационных разрядов a0 (старший разряд); a1; a2;... ak–1 можно
- •Реализация кодирующих устройств циклического кода
- •Нарисуем схему умножения образующего многочлена g(x) на любой многочлен ai(x).
- •Входной сигнал подается в ячейки памяти слева, начиная со старших разрядов.
- •В нашем случае это x3; x1 и x0,
- •В результате получается на выходе тот же результат, что и при умножении столбиком
Выбираем многочлен g(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) выбираем из таблицы многочленов, не
приводимых над |
по условию d = 2. |
Таких многочленов |
один |
во многих случаях целесообразно
пользоваться таблицей наилучших двоичных циклических кодов, предлагаемой ITU (International Telecommunication Union)
Из соотношения (2n–k – 1) ≥ числа ошибок, которые мы хотим обнаруживать.
Так как мы обнаруживаем лишь факт есть ошибка (в любом разряде) или ее нет, то неравенство можно записать так:
2n–k – 1 ≥ 1, то есть, 2n–k ≥ 2, то есть n – k = 1; n = k + 1.
Это соответствует одному дополнительному разряду, который
следует заполнить нулем или единицей, так, чтобы полученная Р.К.К. делилась без остатка
.К.К. будет делится на без остатка, если в ней будет четное число единиц. Убедимся в этом.
Пусть k = 7. Имеем К.К.
Дополним ее поверочным разрядом:
так как в информационных разрядах всего 3 единицы, то в поверочном разряде должна быть записана единица, чтобы полученная Р.К.К. делилась без остатка.
Где ее записывать, вначале К.К. или в конце значения не имеет
Поделим РКК
Замечание
циклический код с проверкой на четность обнаруживает не только единичные, но и любые ошибки нечетной кратности,
так же как не обнаруживает
любые ошибки четной кратности.