Лекции по теории информации. Фурсов teoria_informacii. Лекции по теории информации под редакцией Н. А. Кузнецова

• Название: Лекции по теории информации под редакцией Н. А. Кузнецова
• Анкор: Лекции по теории информации
• Дата: 17.04.2022
• Размер: 1.32 Mb.
• Имя файла: Фурсов teoria_informacii.pdf
• Тип: Лекции; #480820
• страница: 11 из 16

Циклические коды
12.1 Математическое введение к циклическим кодам
Математическим аппаратом циклических кодов является теория колец.
Множество  называется кольцом, если для любой пары элементов из  опре- делены операции сложения и умножения, множество  является аддитивной абелевой группой, а также выполняются аксиомы замкнутости, ассоциативно- сти и дистрибутивности. Подмножество элементов кольца  само являющееся кольцом относительно операций в  называют подкольцом.
Подкольцо  аддитивной группы  называется идеалом, если для любого

из  и любого

из  элемент

принадлежит  . Если все элементы  кратны некоторому элементу кольца

, он называется главным идеалом, а

– образующим элементом идеала.
Кольцо коммутативно, если



. Коммутативное кольцо  называет- ся полем, если выполняются аксиомы:
1) кольцо  содержит элемент 1 такой, что для любого

из 
1 1





 
;
2) для любого
  
существует
1


 
такой, что
1 1
1
 
 





Таким образом, поле  является абелевой группой. Подмножество
 
\ 0

явля- ется мультипликативной абелевой группой.
Пусть на множестве
m
 целых чисел сложение и умножение определены по модулю
m
. Множество
m
 называется кольцом классов вычетов по модулю
m
. Оно является коммутативным кольцом, а также кольцом главных идеалов.
Если
p
– простое число, то кольцо чисел по модулю
p
является полем.
Это поле далее будем обозначать
 
p

. Поле не может иметь менее двух элементов, т.к. в нем должны быть единичные элементы как относительно сло- жения, так и умножения. Поле, включающее только 0 и 1, далее будем обозна- чать
 
2

, а вместо специального знака

, обозначающего операцию сложе- ния по модулю два, для простоты будем использовать обычный знак сложения.

101
Многочленом относительно
x
над полем  называется выражение
 
0 1
n
n
f x
x
x







, где
,
0,
i
i
n


– принадлежат полю  .
Степенью
 
deg f
многочлена
 
f x
называется наибольшее число i та- кое, что
0
i

 . Многочлен нулевой степени называется константой. Если
 
deg f
n

, то
n

– старший коэффициент. Многочлен, у которого
1
n

 назы- вается нормированным.
Множество всех многочленов над полем  с определенными в поле опера- циями сложения и умножения составляют кольцо
 
x

Для любых многочленов
 
a x
и
 
b x
из кольца
 
x

имеем и притом единственным образом
 
   
 
a x
b x q x
r x


,




deg
( )
deg
( )
r x
q x

(12.1)
Если
 
0
r x 
, то
 
b x
является делителем
 
a x
, а сам
 
a x
является много- членом, кратным
 
b x
. Если единственными делителями
 
a x
являются

или
 
a x
 
, где

– некоторый элемент из  , то
 
a x
называется неприводи-
мым многочленом над полем  .
Любой многочлен
 
f x
Const

может быть представлен в виде
 
 
 
 
1 2
1 2
,
0
r
l
l
l
r
i
f x
p x
p x
p x
l




 




 



, где
 
,
1,
i
p x
i
r

– неприводимые нормированные многочлены, а
 
i
l
i
p x



 i=1,r – простые делители многочлена
 
f x
Любой многочлен
 
f x
над полем
 
p

, где
p
– простое число, не де- лящийся на
x
, является делителем многочлена
1
i
x

для некоторого целого i .
Наименьшее положительное число i=T называется показателем, которому при- надлежит многочлен
 
f x
. Если многочлен
n
-й степени принадлежит показа- телю T , то число
1
n
p 
делится на T . Для любого
n
и любого простого
p
су- ществует, по крайней мере, один неприводимый многочлен
n
-й степени, при-

102 надлежащий показателю
1
n
p 
, который называется многочленом, принадле-
жащим максимальному показателю.
Простыми делителями многочлена
k
p
x
x

являются неприводимые много- члены над полем
 
p

, на степени которых делится
k
. Многочлен
1
k
x

де- лится на многочлен
1
h
x

тогда и только тогда, когда
k
делится на
h
12.2 Понятие и общая схема построения циклического кода
Циклическим называется код, каждая комбинация которого может быть получена путем циклического сдвига комбинации, принадлежащей этому же коду. Если сдвиг осуществляется справа налево, крайний левый символ перено- сится в конец кодовой комбинации (таблица 12.1).
Описание циклических кодов удобно проводить с помощью многочленов.
Для этого вводят фиктивную переменную
x
, степени которой соответствуют номерам разрядов, начиная с 0. В качестве коэффици- ентов многочленов берут цифры 0 и 1, т.е. вводятся в рассмотрение многочлены над полем
 
2

. Напри- мер, первая строка из примера (таблица. 12.1) описыва- ется многочленом
5 4
3 2
1 0
3 0
0 1
0 1
1 1
x
x
x
x
x
x
x
x

 
 
 
 
 

 
Многочлен для каждой следующей строки образуется из предыдущего путем умножения на
x
. При этом, если крайний левый символ отличается от нуля для реализации операции переноса единицы в конец комбинации из результата не- обходимо вычесть (сложить по модулю 2) многочлен
1
n
x 
Все комбинации циклического кода могут быть построены на кольце мно- гочленов путем задания на множестве
n
-разрядных кодовых комбинаций двух операций – сложения и умножения. Операция сложения многочленов в данном случае реализуется как сложение соответствующих коэффициентов по моду- лю 2.
Таблица 12.1
0 0
1 0
1 1
0 1
0 1
1 0
1 0
1 1
0 0
0 1
1 0
0 1

103
Операция умножения реализуется в следующей последовательности. Мно- гочлены перемножаются как обычно с последующим приведением коэффици- ентов по модулю 2. Если в результате умножения получается многочлен степе- ни
n
и выше, то осуществляется его деление на заданный многочлен степени
n
, а результатом умножения считают остаток от деления. Ясно, что старшая степень этого остатка не будет превышать величины
1
n 
, а полученный оста- ток будет соответствовать некоторой
n
-разрядной кодовой комбинации, т.е. обеспечивается замкнутость.
Для реализации циклического сдвига с использованием описанной опера- ции умножения необходимо после умножения на
x
выполнить деление на дву- член
1
n
x 
. Эта операция называется взятием остатка или приведением по
модулю
1
n
x 
, а сам остаток называют вычетом:
1 2
1 2
1 2
(
1)
1 1
1 0
1
n
n
n
n
n
n
n
x
x
x
x
x
x
x
x x
x
x
x
x






 












 
Нетрудно заметить, что в данном случае остаток (вычет) формируется путем сложения по модулю 2 двучлена
1
n
x 
с результатом умножения на
x
12.3 Построение циклического кода на кольце многочленов
Выделим в кольце подмножество всех многочленов, кратных некоторому многочлену
 
g x
. Ясно, что это подмножество будет идеалом, а многочлен
 
g x
– порождающим или образующим многочленом идеала. Если
 
0
g x 
, то весь идеал состоит из одного этого многочлена. Если
 
1
g x 
, то в идеал вой- дут все многочлены кольца.
В кольце 2
n всех возможных многочленов степени n-1 над полем GF(2) не- приводимый многочлен
 
g x
степени
m
n
k
 
порождает
2
k
элементов идеа- ла. Следовательно, можно определить циклический двоичный код как идеал, каждому многочлену которого ставится в соответствие
n
-разрядная разрешен-

104 ная кодовая комбинация. Установим, каким требованиям при этом должен удовлетворять образующий многочлен идеала –
 
g x
По определению идеала все его многочлены
 
 
1 2
,
,...
g x
g
x
должны де- литься без остатка на
 
g x
. На множестве многочленов идеала выделим под- множество так называемых базовых полиномов
 
 
 
1 2
,
,...,
k
g x
g
x
g
x
, сумми- рованием которых во всех возможных комбинациях могут быть построены все многочлены идеала.
В соответствии с описанной выше схемой циклического сдвига базовые полиномы могут быть образованы последовательным умножением на
x
с по- следующим приведением по модулю
1
n
x 
:
 
 
 
 


 
 


1 2
1 1
,
1 ,
...,
1 ,
n
n
k
k
g x
g x
g
x
g x x
c x
g
x
g
x x
c x








(12.2) где
1
c 
, если степень
 
i
g x x
превышает
1
n 
и
0
c 
, если степень
 
i
g x x
не превышает
1
n 
Для того чтобы все многочлены, соответствующие комбинациям цикличе- ского кода, делились без остатка на
 
g x
, достаточно чтобы на него делились без остатка указанные выше базовые полиномы. Из (12.2) следует, что для это- го должен делиться без остатка на
 
g x
многочлен
1
n
x 
. Таким образом, что- бы порождающий идеал многочлен
 
g x
являлся образующим элементом цик- лического кода, он должен быть делителем многочлена
1
n
x 
Если
 
g x
удовлетворяет этому требованию, то кольцо многочленов мож- но разложить на классы вычетов по идеалу. Для наглядности схема разложения представлена в таблице 12.2. Первой строкой в этой таблице является сам идеал вместе с нулевым многочленом. В качестве образующих элементов классов бе- рутся (соответствующие векторам ошибок) многочлены
 
r x
, не принадлежа-

105 щие идеалу, а классы вычетов по идеалу образуются путем сложения элементов идеала с образующими многочленами.
Таблица 12.2
0
 
g x
 
xg x

  
1
x
g x

…
 
 
f x
g x

 
1
r x
 
 
1
g x
r x

 
 
1
xg x
r x


  
 
1 1
x
g x
r x


…
 
 
 
1
f x
g x
r x


 
2
r x
 
 
2
g x
r x

 
 
2
xg x
r x


  
 
2 1
x
g x
r x


…
 
 
 
2
f x
g x
r x


…
…
 
z
r x
 
 
z
g x
r x

 
 
z
xg x
r x


  
 
1
z
x
g x
r x


…
 
 
 
z
f x
g x
r x


Если реализована указанная схема образования классов вычетов, а много- член
 
g x
степени
m
n
k
 
является делителем двучлена
1
n
x 
, то каждый элемент кольца либо делится на
 
g x
без остатка (тогда он элемент идеала), либо появляется остаток от деления
 
r x
– это многочлен степени не выше
1
m 
. Элементы кольца, дающие один и тот же остаток
 
r x
, относят к одному классу вычетов.
Корректирующая способность кода тем выше, чем больше классов вычетов, т.е. ос- татков
 
r x
. Наибольшее число остатков
2 1
m

дает неприводимый многочлен. В каче- стве примера в таблице 12.3 приведены не- приводимые многочлены до третьей степени включительно. Таблицы, включающие боль- шое число неприводимых многочленов, можно найти, например, в [2], [3].
12.4 Выбор образующих многочленов для обнаружения
и исправления одиночных ошибок
Обнаружение одиночных ошибок. В данном случае искаженная кодовая комбинация может быть представлена в виде
 
 
 
i
q x
a x
x



, где
Таблица 12.3
M Код
 
g x
Обозна- чение
1 11 1
x 
 
1
P x
2 111 2
1
x
x
 
 
2
P x
3 1011 3
1
x
x
 
 
3 1
P x
3 1101 3
2 1
x
x


 
3 2
P x

106
 
,
0,
1
i
i
x
x
i
n




– соответствуют множеству одиночных ошибок. Если
 
0
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
существует хотя бы один неприводимый

107 многочлен степени
m
, входящий сомножителем в разложение двучлена
1
n
x 
Этот многочлен и может быть принят в качестве образующего.
Например, для рассматривавшегося в разделах 11.4, 11.5 случая построе- ния кода (7,4), т.е. для n=7 и m=3, двучлен
3 7
2 1
1 1
x
x

 
 можно записать в виде произведения следующих неприводимых многочленов
(см. таблицу 12.3):



 

1 1
1 2
3 3







x
x
x
x
x
, степени которых являются делителями числа 3. Любой из сомножителей треть- ей степени в данном случае может быть принят в качестве образующего много- члена.