Лекции по теории информации. Фурсов В.А. - 106 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

Составители: 

Рубрика: 

106
, 0, 1
i
i
x x i n
– соответствуют множеству одиночных ошибок. Если
i
x
, то
q x
должен делиться без остатка на
g x
. Если
0
i
x
, то по-
является остаток – признак ошибки, это означает, что
i
x
не должен делится на
g x
.
Среди неприводимых многочленов, входящих в разложение
1
n
x
, много-
членом наименьшей степени, удовлетворяющим этому требованию, является
1
x
. Остатком от деления любого многочлена на
1
x
является многочлен ну-
левой степени, принимающий два значения: либо 0, либо 1. Поэтому все кольцо
в данном случае состоит из идеала и одного класса вычетов, соответствующего
единственному остатку, равному 1.
Таким образом, для обнаружения одиночных и любого нечетного количе-
ства ошибок необходим один проверочный разряд. Проверочный символ в этом
разряде выбирается так, чтобы число единиц в любой разрешенной комбинации
было четным.
Исправление одиночных ошибок. Каждой одиночной ошибке в одном из
n
разрядов должен соответствовать свой класс вычетов и свой опознаватель – ос-
таток от деления на образующий многочлен
g x
. Как указывалось выше, наи-
большее число остатков дает неприводимый многочлен. Если
m n k
степень
этого многочлена, число ненулевых остатков будет
2 1
n k
. Таким образом, для
исправления всех
n
одиночных ошибок необходимо, чтобы выполнялось
1
2 1
n k
n
С n
. Откуда степень образующего многочлена
2
log 1
m n k n
.
Выше было показано, что образующий многочлен должен быть делителем
1
n
x
. С другой стороны, известно, что любой двучлен вида
2 1
1 1
m
n
x x
всегда может быть представлен в виде произведения всех неприводимых мно-
гочленов, степени которых являются делителями числа
m
от 1 до
m
включи-
тельно. Следовательно, для любого
n
существует хотя бы один неприводимый

Страницы