- •Циклический код
- •Циклический код
- •Циклические коды
- •Среди групповых кодов можно выбрать такие, у которых строки связаны условием цикличности,
- •Сдвиг осуществляется справа налево, а крайний левый символ перемещается в конец строки, т.е.
- •Любые «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,
- •В результате получается на выходе тот же результат, что и при умножении столбиком
Получили остаток, отличный от нуля.
По нему мы должны определить, в каком разряде имеет место ошибка.
Для этого необходимо определить, какой остатокразряде.ri(x) даст единичная ошибка в i-том
До ошибки в четвертом разряде остаток соответствует самой ошибке, а начиная с ошибки в 4ом разряде происходит деление.
В примере остаток , то есть ошибка в пятом разряде. Исправим ошибку:
Но, получив ƒi(x), мы не получили ai(x), то есть снова приходится делить ƒi(x) на g(x):
Методы построения циклического кода
методом деления
Чтобы получить разделимый код :
ai(x) умножают на xm
что эквивалентно
дописыванию к ai(x) справа m нулей.
Полученный многочлен делится на g(x).
В результате получается частное от деления g(x) и остаток r(x).
Разрешенная кодовая комбинация ƒi(x) получается путем сложения и r(x)
Степень многочлена g(x) – m, а степень остатка – (m – 1).
Поэтому сложение эквивалентно приписыванию остатка r(x) к ai(x), так как m разрядов в – нулевые.
В то же время ƒi(x) делится на g(x) без остатка так как:
Данная методика используется при k > m.
Пример (тот же)
ai(x) = 1011;
g(x) = 1011.
Так получилось потому, что ai(x) совпало с g(x).
Если в линии связи произошла ошибка в пятом разряде , то будем иметь
Поделим на g(x) и получим остаток r(x)