Лекция 25
ЦИКЛИЧЕСКИЕ КОДЫ
25.1 Способы описания циклических кодов
25.2 Матричное задание кодов
25.3 Декодирование циклического кода
25.4. Свойства циклических кодов по обнаружению ошибок
25.1 Способы описания циклических кодов
Циклические коды получили широкое распространение благодаря их эффективности при обнаружении и исправлении ошибок.
Схемы кодирующих и декодирующих устройств для этих кодов чрезвычайно просты и строятся на основе обычных регистров
сдвига.
Циклическим кодом
называется линейный блочный (
n
,
m
)-код, который характеризуется свойством цикличности, т.е. сдвиг
влево на один шаг любого разрешенного кодового слова дает также разрешенное кодовое слово, принадлежащее этому же
коду и у которого, множество кодовых слов представляется совокупностью многочленов степени (
n
-1) и менее, делящихся на
некоторый многочлен
g
(
x
) степени
k
=
n
-
m
, являющийся сомножителем двучлена
xn
+1.
Название кода произошло от его свойства, заключающегося в том, что каждая кодовая комбинация может быть получена путем
циклической перестановки
символов комбинации, принадлежащей этому же коду. Это означает, что если кодовая
комбинация
а
0
а
1
а
2…
аn
-1 является разрешенной комбинацией циклического кода, то комбинация вида
аn
-1
а
0
а
1
а
2…
аn
-2 так
же является разрешенной комбинацией и принадлежит этому коду. Запись
а
0
а
1…
аn
-1 означает, что кодовая комбинация
состоит из
n
разрядов, первый из которых
а
0 , последний
аn
-1.
Отличие комбинации
аn
-1
а
0
а
1
а
2…
аn
-2 от комбинации
а
0
а
1
а
2…
аn
-1 состоит в том, что последний разряд
аn
-1 становится
первым, а предпоследний
аn
-2 становится последним. Такая перестановка называется циклической.
Циклические коды часто описываются с использованием многочленов (полиномов) переменной
X
X
=
G
(
x
);
G
(
x
) =
an
-1
xn
-1 + … +
a
1
x
+
a
0,
(25.1)
где
аi
– цифры данной системы исчисления (в двоичной системе 0 и 1). Так, например, двоичное семиразрядное число 1010101
может быть записано в виде полинома:
G
(
x
) = 1
x
6 + 0
x
5 + 1
x
4 + 0
x
3 + 1
x
2 + 0
x
1 + 1
x
0 =
x
6 +
x
4 +
x
2 + 1. (25.2)
То есть цифры двоичного кода рассматриваются как коэффициенты многочлена
G
(
x
). Наибольшая степень
х
в слагаемом с
ненулевым коэффициентом называют степенью многочлена (полинома). Представление кодовых комбинаций в виде (25.1)
позволяет свести действия над комбинациями к действиям над многочленами. При этом сложение двоичных многочленов
сводится к сложению по модулю 2 коэффициентов при равных степенях переменной
х
ха
+
ха
= 0 ;
ха
+0 =
ха
; 0 + 0 = 0.
(25.3)
Умножение производится по обычному правилу перемножения степенных функций, но полученные при этом коэффициенты при
равных степенях переменой
х
складываются по модулю 2:
.
0
0
;
1
;
=
Ч
=
Ч
=
Ч
+
a
a
a
b
a
b
a
x
x
x
x
x
x
(24.4)
Рассмотрим пример умножения многочленов
(
)
;
110
2
=
+
x
x
и
(
)
;
11
1
=
+
x
(
)
(
)
.
1010
1
3
2
3
2
2
=
+
=
+
+
+
=
+
Ч
x
x
x
x
x
x
x
x
x
Либо умножение можно произвести следующим образом
1 1 0
ґ
1 1
1 1 0
Е
1 1 0
1 0 1 0.
Деление осуществляется по правилу деления степенных функций, при этом операции вычитания заменяются операциями
суммирования по модулю 2.
Рассмотрим пример деления многочлена
;
111010
3
4
5
=
+
+
+
x
x
x
x
на бином
;
1001
1
3
=
+
x
Вначале рассмотрим деление комбинаций
1 1 1 0 1 0
1 0 0 1
Е
1 0 0 1
1 1 1
- результат деления –
1
2
+
+
x
x
новый многочлен
0
1 1 1 1 0
Е
1 0 0 1
новый многочлен
0 1 1 0 0
Е
1 0 0 1
0 1 0 1
- остаток
.
А теперь рассмотрим деление полиномов
х
5+
х
4+
х
3+
х
х
3+1
Е
х
5+
х
2
х
2+
х
+1
- результат деления –
1 1 1
х
4+
х
2+
х
3+
х
новый многочлен
Е
х
4+
х
х
3+
х
2
новый многочлен
Е
х
3+ 1
х
2+1
- остаток-
0 1 0 1.
Представления комбинаций в формах (25.1) и (25.2) удобно еще тем, что упомянутая ранее циклическая перестановка есть
результат простого умножения данного полинома на
х
. Если одна из кодовых комбинаций выражается полиномом
G
(
x
) =
a
0 +
a
1
x
+
a
2
x
2 +
a
3
x
3 + … +
an
-1
xn
-1, (25.5)
то новая комбинация за счет циклического сдвига будет
x
Ч
G
(
x
):
x
Ч
G
(
x
) =
a
0
x
+
a
1
x
2 +
a
2
x
3 +
a
3
x
4 +
an
-2
xn
-1 +
an
-1
xn
.
(25.6)
В последнем члене необходимо заменить
хn
на
х0
. Новую комбинацию обозначим
G
1(
x
)
G
1(
x
) =
an
-1
х0
+
a
0
x
+
a
1
x
2 +
a
2
x
3 + … +
an
-2
xn
-1.
(25.7)
Пример.
Рассмотрим, как получить новую комбинацию из кодовой комбинации
1010101 =
x
6 +
x
4 +
x
2+1
путем циклического сдвига. Циклический сдвиг получается умножением многочлена, соответствующего исходной комбинации
на
х
G
(
x
)Ч
х
=
х
Ч(
x
6 +
x
4 +
x
2+1) =
x
7 +
х
5 +
x
3 +
x
.
(25.8)
Заменив
х
7 на
х
0 т.е. на «1» получим новую кодовую комбинацию
G
1(
x
) в виде полинома:
G
1(
x
) =
х
5 +
x
3 +
x
+ 1.
(25.9)
G
1(
x
) соответствует кодовой комбинации 0101011. Таким образом, в результате циклической перестановки исходной кодовой
комбинации 1010101 получена новая кодовая комбинация 0101011 также принадлежащая циклическому коду. Заметим, что
запись кода в виде многочлена получается более компактной, чем в матричном виде.
Циклический сдвиг на один разряд соответствует алгебраическому умножению некоторого многочлена
g
(
x
), который выбран в
качестве исходного на
х
. Процесс получения новых комбинаций кода можно представить следующим образом
g
(
x
),
х g
(
x
),
х
2
g
(
x
),
х
3
g
(
x
),…,
хn
-1
g
(
x
).
Многочлен, взятый в качестве исходного, называют
образующим
или
порождающим
.
Принцип обнаружения ошибок
при помощи циклического кода заключается в том, что в качестве разрешенных принимаются
только те комбинации, которые
без остатка
делятся на заранее выбранный
образующий
многочлен
g
(
x
). Если принимаемая
комбинация искажена, то это условие на приемной стороне не будет выполнено. В результате этого формируется сигнал,
указывающий на наличие ошибки.
Задача состоит в том, чтобы сформировать кодовые комбинации на передаче, удовлетворяющие указанному условию. Метод
построения кодовых комбинаций используется следующий. В процессе кодирования многочлен
G
(
x
) отображающий двоичный
код передаваемого сообщения (примитивный код) умножаются на
хk
. При этом длина кодовой комбинации увеличивается на
k
разрядов. Эти дополнительные разряды будут проверочными. Полученное произведение
G
(
x
)Ч
xk
делят на специально
подобранный образующий многочлен
g
(
x
). При этом получают остаток
R
(
x
). Данный остаток
R
(
x
) суммируют с произведением
G
(
x
)Ч
xk
. Получают кодовую комбинацию
F
(
x
)=
G
(
x
)Ч
xk
+
R
(
x
), которая будет без остатка делиться на
g
(
x
). Алгоритм формирования
комбинаций циклического кода показан на рис. 25.1.
Рис. 25.1. Алгоритм формирования циклического кода
Покажем справедливость такого способа формирования циклического кода. Обозначим частное от деления
G
(
x
)Ч
xk
на
g
(
x
) как
f
(
x
). Тогда справедливо равенство
G
(
x
)Ч
xk
=
f
(
x
)
g
(
x
) –
R
(
x
) где
R
(
x
) остаток деления
G
(
x
)Ч
xk
на
g
(
x
).
Перенося
R
(
x
) за знак равенства получим:
G
(
x
)Ч
xk
+
R
(
x
) =
f
(
x
)Ч
g
(
x
)
При таком методе построения коэффициенты при высших степенях являются обозначениями информационных разрядов, а
коэффициенты при степенях порядка
k
-1 и ниже – проверочными.
Рассмотрим использование описанного алгоритма формирования комбинаций циклического кода на примере.
Пример.
Требуется закодировать сообщение 1011. Дано: порождающий полином
g
(
x
) =
х
3 +
х
2 + 1, общее число разрядов
n
= 7, число информационных разрядов
m
=4, число избыточных разрядов
k
= 3.
Решение:
1. Для кодирования сообщения 1011 определим, какому многочлену оно соответствует:
G
(
x
) = 1Ч
x
3 + 0Ч
x
2 + 1Ч
x
1 + 1Ч
x
0 =
x
3 +
x
+ 1.
2. Разделим полином
G
(
x
)Ч
xk
на порождающий
g
(
x
) для определения остатка
R
(
x
):
G
(
x
)Ч
xk
=
G
(
x
)
x
3 = (
x
3 +
x
+ 1)Ч
x
3 =
x
6 +
x
4 +
x
3
(25.10)
х
6+
х
4+
х
3
х
3+
х
2+1
Е
х
6+
х
5
+ х
3
х
3+
х
2
х
5+
х
4
(25.11)
Е
х
5+
х
4
+ х
2
х
2
- остаток
R
(
x
)=
x
2
3. Суммируем произведение
G
(
x
)Ч
x
3
с полученным остатком
x
2 получим кодовый многочлен
F
(
x
)
F
(
x
) =
G
(
x
)Ч
x
3 +
R
(
x
) =
x
6+
х
4+
х
3 +
х
2
(25.12)
В двоичном коде этому многочлену соответствует кодовая комбинация (
а
6 = 1,
а
5 = 0,
а
4 = 1,
а
3 = 1,
а
2 = 1,
а
1 = 0,
а
0 = 0) -
1011
100
. В этой кодовой комбинации последние три позиции занимают проверочные разряды (выделены).
Проверим, возможно, ли обнаружить ошибку
при приеме
кодовой комбинации циклического кода указанным выше алгоритмом.
Пусть принимается рассмотренная выше комбинация
F
(
x
) = 1011100. Порождающий полином должен быть известен на приеме.
Вынесение решения о наличии ошибки основывается на анализе остатка
R
(
x
) от деления комбинации на порождающий полином
g
(
x
) если
R
(
x
) = 0 , то ошибки нет.
Кодовой комбинации 1011100 соответствует многочлен
F
(
x
)=
x
6+
x
4+
x
3+
х
2.
Делим
F
(
x
) на
g
(
x
)
х
6+
х
4+
х
3+
х
2
х
3+
х
2+1
Е
х
6+
х
5
+ х
3
х
3+
х
2
х
5+
х
4+
х
2
(25.13)
Е
х
5+
х
4
+ х
2
0
Остаток
R
(
x
)=0, следовательно ошибки нет.
Допустим, в результате воздействия помех в канале связи вместо комбинации 1011100 принято 0011100. Этой комбинации
соответствует многочлен х4+х3+х2. Деление на
g
(
x
) дает:
х
4+
х
3+
х
2
х
3+
х
2+1
Е
х
4+
х
3
+х
х
х
2+
х
Остаток R
(
x
) №0
(25.14)
Ошибка обнаружена.
Возможно применение циклического кода в качестве кода с исправлением ошибок. В этом случае на приеме получают остаток
от деления принятой комбинации кода на порождающий многочлен. Места искаженных разрядов определяются путем анализа
остатка.
25.2 Матричное задание кодов
Для повышения быстродействия кодирования используется образующая матрица циклического кода, состоящая из единичной
транспонированной матрицы, характеризующей информационные разряды и матрицы контрольных разрядов
k
m
m
R
I
m
n
G
ґ
=
)
,
(
где
m
I
- единичная матрица;
k
m
R
ґ
- прямоугольная матрица контрольных разрядов.
Строки матрицы
k
m
R
ґ
определяются из выражений
й
щ - остаток от деления
на образующий полином
,
где
- значение
i
-той строки матрицы
;
i
- номер строки матрицы
k
m
R
ґ
.
Пример. Матрица
)
,
(
m
n
G
для (7,4)-кода на основе порождающего многочлена
1
)
(
2
3
+
+
=
x
x
x
g
, строится в
следующей последовательности
3
4
4
)
4
,
7
(
ґ
=
R
I
G
.
0
1
2
3
4
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
x
x
x
x
I
=
=
.
Определяется
3
4
ґ
R
, используя
)
(
)
(
x
g
i
R
x
r
=
й
k
i
x
a
щ
при
1
=
i
6
3
3
3
1
x
x
x
x
a
=
=
.
Определим остаток от деления
6
x
на образующий полином
1
)
(
2
3
+
+
=
x
x
x
g
.
х
6
х
3+
х
2+1
Е
х
6+
х
5+
х
3
x
5+
х
3
Е
x
5+
х
4
+ х
2
x
4
+х
3
+х
2
Е
x
4
+х
3
+ x
х
2+
x
- остаток
110
)
(
1
=
x
r
при
2
=
i
5
3
2
3
2
x
x
x
x
a
=
=
.
Определим остаток от деления
5
x
на образующий полином
1
)
(
2
3
+
+
=
x
x
x
g
.
х
5
х
3+
х
2+1
Е
х
5+
х
4+
х
2
x
4+
х
2
Е
x
4+
х
3
+ x
х
3
+х
2
+ х
Е
х
3
+х
2
+
1
x
+ 1
- остаток
011
)
(
2
=
x
r
при
3
=
i
4
3
1
3
3
x
x
x
x
a
=
=
.
Определим остаток от деления
4
x
на образующий полином
1
)
(
2
3
+
+
=
x
x
x
g
.
х
4
х
3+
х
2+1
Е
х
4+
х
3
+ х
x
3+
х
Е
x
3+
х
2
+
1
х
2
+ х
+1
- остаток
=
)
(
3
x
r
111
при
.
х
3
х
3+
х
2+1
Е
х
3+
х
2
+
1
x
2+
1
- остаток
=
)
(
4
x
r
101
В результате получаем
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
)
4
,
7
(
2
3
2
4
5
2
6
+
+
+
+
+
+
+
+
+
=
=
x
x
x
x
x
x
x
x
x
x
G
.
Процесс кодирования с помощью такой матрицы производится следующим образом. Пусть требуется закодировать
информационные разряды
1 0 1 1=
x
3
+х+
1.
Суммируются соответствующие строки 1-ю, 3-ю и 4-ю
2
3
4
6
2
3
2
4
5
2
6
0
0
1
1
1
0
1
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
1
1
0
1
)
4
,
7
(
x
x
x
x
x
x
x
x
x
x
x
x
x
x
G
+
+
+
=
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
=
=
Образующая матрица позволяет кодировать циклическим кодом информационные разряды за счет сложения по модулю 2 тех
строк матрицы, которые в результате сложения дают требуемые информационные разряды. При этом контрольные разряды
получаются автоматически при сложении по модулю 2 соответствующих строк матрицы.
Преимуществами кодирования с помощью образующей матрицы являются:
большое быстродействие (не требуются сдвиги кодируемого числа),
компактная запись всех комбинаций кода.
25.3 Декодирование циклического кода
1. Способы декодирования с обнаружением ошибок
Процедура декодирования циклического кода с обнаружением ошибок, по аналогии с процессом кодирования, использует два
способа:
- при кодировании "классическим" способом декодирование основано на использовании свойства делимости без остатка
кодового многочлена
G
(
x
) циклического (
n
,
m
)-кода на порождающий многочлен
g
(
x
). Поэтому алгоритм декодирования включает
в себя деление принятого кодового слова, описываемого многочленом
G
ў(
x
) на
g
(
x
), вычисление и анализ остатка
R
(
x
). Если
R
(
x
)=0, то принятое кодовое слово считается неискаженным. Если
R
(
x
)№0, то принятое кодовое слово стирается и формируется
сигнал "ошибка".
- при кодировании способом МККТТ декодирование основано на свойстве получения определенного контрольного остатка
R
0(
x
)
при делении принятого кодового многочлена
G
ў(
x
) на порождающий многочлен
g
(
x
). Поэтому, если полученный при делении
остаток
)
(
x
R
=
R
0(
x
), то принятое кодовое слово считается неискаженным. Если остаток
)
(
x
R
№
R
0(
x
), то принятое кодовое
слово стирается и формируется сигнал "ошибка". Значение контрольного остатка определяется из выражения
R
0(
x
)=
Rg
(
x
) й
x
(1)
r
-1
xk
щ.
2 Способы декодирования с исправлением ошибок
Декодирование заключается в определении номера искаженного разряда и его автоматического исправления. А также
отделения информационных разрядов от контрольных.
Рассмотрим три методики декодирования
Определение искаженного разряда с помощью матрицы ошибок.
Если ошибок нет, то остаток от деления равен нулю
0
)
(
=
x
g
F
ост
.
Матрица одиночных ошибок имеет вид
n
m
n
H
I
E
ґ
=
где
n
I
- единичная матрица;
n
m
H
ґ
- прямоугольная проверочная матрица.
Строки матрицы
n
m
H
ґ
определяются из выражений
)
(
)
(
x
g
a
ост
x
h
i
i
=
- остаток от деления
на образующий полином
,
где
- значение
i
-той строки матрицы
;
i
- номер строки матрицы
.
Пример. Матрица
)
,
(
m
n
G
для (7,4)-кода на основе порождающего многочлена
1
)
(
2
3
+
+
=
x
x
x
g
имеет вид
1
1
1
1
0
1
1
1
1
1
1
0
0
1
1
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
)
,
(
2
3
2
4
5
2
6
+
+
+
+
+
+
+
+
+
=
=
x
x
x
x
x
x
x
x
x
x
m
n
G
.
Единичная матрица размерности 7х7
0
1
2
3
4
5
6
7
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
1
x
x
x
x
x
x
x
I
=
=
.
Рассчитаем проверочную матрицу
)
(
)
(
x
g
a
ост
x
h
i
i
=
при
1
=
i
6
1
x
a
=
.
Определим остаток от деления
6
x
на образующий полином
1
)
(
2
3
+
+
=
x
x
x
g
.
110
)
(
1
=
x
h
.
При
2
=
i
5
2
x
a
=
.
Определим остаток от деления
5
x
на образующий полином
1
)
(
2
3
+
+
=
x
x
x
g
.
011
)
(
2
=
x
h
.
При
3
=
i
4
3
x
a
=
.
Определим остаток от деления
4
x
на образующий полином
1
)
(
2
3
+
+
=
x
x
x
g
.
=
)
(
3
x
h
111.
При
4
=
i
3
4
x
a
=
.
=
)
(
4
x
h
101.
При
5
=
i
2
5
x
a
=
.
=
)
(
5
x
h
100.
При
6
=
i
x
a
=
6
.
=
)
(
6
x
h
010.
При
7
=
i
1
7
=
a
.
=
)
(
7
x
h
001.
Тогда матрица ошибок
1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0
1
0
1
0
0
0
1
0
0
0
1
1
1
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
0
0
1
1
0
0
0
0
0
0
1
=
E
H
I
4
8
4
7
6
4
4
4
4
8
4
4
4
4
7
6
Для определения искаженного разряда необходимо определить остаток от деления принятой кодовой комбинации
F
на
порождающий многочлен
)
(
x
g
.
Пример
1011100
=
F
Внесем искажения
1010100
'
=
F
Находим остаток
1 0 1 0 1 0 0
Е 1 1 0 1
1 1 1 1
Е 1 1 0 1
0 0 1 0 0 0
Е 1 1 0 1
1 0 1
- остаток
Находим строку в матрице ошибок с полученным остатком
Искаженный разряд – это разряд в данной строке в которой стоит «1».
Искаженный разряд исправляем посредством сложения строки в матрице ошибок полученной комбинации
0
0
1
1
1
0
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
-
-
-
-
-
-
-
-
-
-
-
-
-
Е
=
F
.
Метод дополнительного деления первоначального остатка на образующий многочлен
Метод дополнительного деления основывается на предыдущем методе т.к. каждый такт дополнительного деления
(приписывания нуля справа) соответствует переходу от данной строки матрици ошибок (строка с первоначальным остатком) к
строке следующей вверх матрицы.
Дополнительное деление продолжается до получения остатка с «1» в первом разряде и нулями в остальных разрядах потому
что этот остаток равен остатку последней строки матрицы ошибок. Остчет искаженного разряда производится от старшего
разряда сообщения, по количеству тактов дополительного деления. Такой отсчет соответствует возвратному движению в
матрице ошибок.
Пример
1011100
=
F
Внесем искажения
1010100
'
=
F
Находим остаток
1 0 1 0 1 0 0
Е 1 1 0 1
1 1 1 1
Е 1 1 0 1
0 0 1 0 0 0
Е 1 1 0 1
1 0 1
- остаток
Дополниетльное деление
1 0 1 0
Дополнительное деление 1
Е 1 1 0 1
1 1 1 0
Дополнительное деление 2
Е 1 1 0 1
0 0 1 1 0 0
Дополнительное деление 3, 4
Е 1 1 0 1
0 0 1
- остаток
Понадобилось 4 такта дополнителоного деления. Тогда
0
0
1
1
1
0
1
0
0
1
0
1
0
1
'
4
3
2
1
=
=
F
F
такты
Метод циклических сдвигов
Метод циклических сдвигов заключается в следующем:
Находится остаток от деления
F
на
)
(
x
g
. Если остаток равен нулю, то ошибок нет.
Если остаток отличен от нуля определяется вес остатка и выполнения условия
и
ост
t
W
Ј
.
Если условие выполняется, то производится суммирование по модулю 2 полученного остатка с комбинацией из которой он
получен. Затем производятся сдвиги вправо столько раз сколько было сделано сдвигов влево В результате получаем
исправленной сообщение.
Если вес остатка больше кратности исправляемых разрядов, то производится сдвиг влево полученной комбинации, т.е.
умножение кодовой комбинации на
x
. И снова находится остаток от деления и переход к п.2.
Пример
1
=
и
t
1011100
=
F
Внесем искажения
1010100
'
=
F
Находим остаток 1 0 1.
Вес остатка
и
ост
t
W
>
=
2
.
1-й циклический сдвиг
1
0
0
1
0
1
0
1010100
'
®
=
F
Находим остаток
0 1 0 1 0 0 1
Е 1 1 0 1
0 1 1 1 0
Е 1 1 0 1
1 1 1
- остаток
Вес остатка
и
ост
t
W
>
=
3
.
2-й циклический сдвиг
0
1
0
0
1
0
1
1
0
0
1
0
1
0
®
Находим остаток
1 0 1 0 0 1 0
Е 1 1 0 1
1 1 1 0
Е 1 1 0 1
1 1 1 0
Е 1 1 0 1
0 0 1 1
- остаток
Вес остатка
и
ост
t
W
>
=
2
.
3-й циклический сдвиг
1
0
1
0
0
1
0
0
1
0
0
1
0
1
®
Находим остаток
0 1 0 0 1 0 1
Е 1 1 0 1
0 1 0 0 0
Е 1 1 0 1
0 1 0 1 1
Е 1 1 0 1
0 1 1 0
- остаток
Вес остатка
и
ост
t
W
>
=
2
.
4-й циклический сдвиг
0
1
0
1
0
0
1
1
0
1
0
0
1
0
®
Находим остаток
1 0 0 1 0 1 0
Е 1 1 0 1
0 1 0 0 0
Е 1 1 0 1
0 1 0 1 1
Е 1 1 0 1
0 1 1 0 0
Е 1 1 0 1
0 0 0 01
- остаток
Вес остатка
и
ост
t
W
=
=
1
.
Вес равен «1» поэтому циклические сдвиги закончились. Теперь необходимо остаток сложить с той комбинацией с которой мы
его получили
1 0 0 1 0 1 0
Е 0 0 0 1
1 0 0 1 0 1 1
Затем производятся сдвиги вправо столько раз сколько было сделано сдвигов влево
1 0 0 1 0 1 1
1-й сдвиг
1 1 0 0 1 0 1
2-й сдвиг
1 1 1 0 0 1 0
3-й сдвиг
0 1 1 1 0 0 1
4-й сдвиг
1 0 1 1 1 0 0
Сообщение исправлено
1011100
=
F
.
25.4. Свойства циклических кодов по обнаружению ошибок
Свойства циклических кодов полностью определяются выбранным порождающим (образующим) многочленом
.
I. Если порождающий многочлен
содержит более одного члена, то циклический код обнаруживает все одиночные
ошибки. При представлении циклического кода многочленами одиночная ошибка описывается одночленом
, где
-
указывает номер искаженного разряда
1
0
-
Ј
Ј
n
i
. Поскольку одночлен не делится на многочлен без остатка, то ошибка
будет обнаружена.
2. Циклический код с порождающим многочленом
1
)
(
+
=
x
x
g
обнаруживает все нечетные ошибки. Используя правила
построения проверочной матрицы для
1
)
(
+
=
x
x
g
, получим
1
...
111
=
T
H
. При такой проверочной матрице остаток
определяется суммой по модулю 2 всех элементов принятой кодовой комбинации (проверка на четность). Поэтому все
искажения на нечетном количестве позиций будут обнаружены.
3. Циклический код обнаруживает все одиночные и двукратные ошибки, если разрядность кода
n
не больше длины цикла
c
l
используемого порождающего многочлена, т.е.
c
l
n
Ј
. Под длиной цикла многочлена понимают минимальный показатель
степени двучлена
1
+
n
x
, при котором этот двучлен делится без остатка на образующий многочлен
)
(
x
g
.
4. Циклический код с многочленом
)
(
x
g
степени
k
обнаруживает все групповые ошибки длительностью в
k
разрядов и
менее. Любая групповая ошибка в
k
разрядов описывается многочленом степени
1
-
k
, т.е.
)
1
...
(
)
(
2
1
+
+
+
=
-
-
k
k
i
x
x
x
x
E
. Многочлен же степени
1
-
k
на многочлен степени
k
не делится и, таким образом,
ошибка обнаруживается.
5. Циклический код с порождающим многочленом
)
(
x
g
степени
k
не обнаруживает
1
2
1
-
k
часть ошибок
1
+
k
-й
кратности.
6. Циклический код с порождающим многочленом
)
(
x
g
степени
k
не обнаруживает
k
2
1
часть ошибок более
1
+
k
-й
кратности.
Анализируя перечисленные свойства циклического кода, можно увидеть, что способности кода по обнаружению и исправлению
ошибок полностью определяются выбранным образующим многочленом
)
(
x
g
.
При обнаружении ошибок стандартные многочлены имеют вид:
1
)
(
2
8
+
+
+
=
x
x
x
x
g
,
4
=
d
при длине кодовой
комбинации
7
2
Ј
n
или
1
)
(
3
5
11
13
15
16
+
+
+
+
+
+
+
=
x
x
x
x
x
x
x
x
g
,
6
=
d
при длине кодовой комбинации
7
2
Ј
n
;
1
)
(
5
13
12
16
+
+
+
+
=
x
x
x
x
x
g
,
4
=
d
при длине кодовой комбинации
15
2
Ј
n
.
Разработан ряд методик по выбору порождающего многочлена
)
(
x
g
. В литературе коды называют по фамилиям ученых,
предложивших ту или иную методику. Так получили свое название коды Боуза-Чоудхури-Хоквингема (БЧХ), коды
Рида-Соломона, коды Файра и др.
