- •Циклический код
- •Циклический код
- •Циклические коды
- •Среди групповых кодов можно выбрать такие, у которых строки связаны условием цикличности,
- •Сдвиг осуществляется справа налево, а крайний левый символ перемещается в конец строки, т.е.
- •Любые «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,
- •В результате получается на выходе тот же результат, что и при умножении столбиком
Циклический код
Циклический код
представляет собой разновидность группового кода и не отличается от него по уровню помехозащищенности, но благодаря простоте технической реализации нашел широкое применение.
Циклические коды
незаменимы при передаче информации в каналах связи, в которых отсутствует возможность повторной передачи данных
Циклические коды применяются:
при записи и считывании на HDD, CD и DVD,
при использовании USB-портов для обмена информацией,
при передаче аудио и видео информации.
Среди групповых кодов можно выбрать такие, у которых строки связаны условием цикличности,
т.е. все строки матрицы могут быть получены циклическим сдвигом одной строки, которая
называется образующей или
производящей.
Сдвиг осуществляется справа налево, а крайний левый символ перемещается в конец строки, т.е. в крайнее правое положение.
Например:
Коды, у которых строки матрицы удовлетворяют этому условию, называются циклическими
Любые «k» строк этой матрицы линейно независимы и могут служить основой для получения любой разрешенной кодовой комбинации циклического кода.
Число возможных циклических кодов существенно меньше числа групповых кодов.
В циклическом коде кодовые комбинации удобно записывать в виде многочлена (n – 1) степени относительно фиктивной переменной x.
Показатель степени при x соответствует номеру разряда, уменьшенному на единицу.
Младший разряд соответствует x0 = 1. Коэффициенты при x имеют значения 0 или 1.
Например:
Посмотрим, что происходит при циклическом сдвиге:
Предыдущие строки, кроме последней, давали кодовую комбинацию путем умножения сомножителя на x в степени, соответствующей количеству сдвигов влево с
переносом на освобождающееся знакоместо нуля.
Последняя кодовая комбинация получена путем переноса на крайнее правое место единицы.
Посмотрим, делится ли полученный
Образующий многочлен g(x).
Многочлен, с помощью которого образуются все разрешенные кодовые комбинации, называется образующим и в дальнейшем будем обозначать его g(x).