Основы теории информации и криптографии - -Учебное пособие (В.В. Лидовский)

9. лекция: групповые коды

Объясняется, какой блочный код называется групповым. Математическое обоснование выводов. Упражнения для самопроверки. Совершенные и квазисовершенные коды. Их свойства. Полиномиальные коды. Частный случай полиномиальных кодов – циклические коды. Очень хорошее и доходчивое объяснение материала характерно для данной лекции

Множество всех двоичных слов a=a_1ldots a_mдлины mобразует абелеву (коммутативную) группу относительно поразрядного сложения.

Пусть E- кодирующая m	imes n-матрица, у которой есть m	imes m-подматрица с отличным от нуля определителем, например, единичная. Тогда отображение a
ightarrow aEпереводит группу всех двоичных слов длины mв группу кодовых слов длины n.

Предположим, что a=a_1ldots a_m=a'+a". Тогда для b=b_1cdots b_n=aE, b'=a'E, b"=a"E, получаем

b_j = a_1e_{1j}+a_2e_{2j}+cdots+a_me_{mj} =

= (a_1'+a_2')e_{1j}+(a_2'+a_2")e_{2j}+cdots+(a_m'+a_m")e_{mj}
= b_j'+b_j",

т.е. b=b'+b". Следовательно, взаимно-однозначное отображение группы двоичных слов длины mпри помощи заданной матрицы Eсохраняет свойства групповой операции, что означает, что кодовые слова образуют группу.

Блочный код называется групповым, если его кодовые слова образуют группу.

Если код является групповым, то наименьшее расстояние между двумя кодовыми словами равно наименьшему весу ненулевого слова.

Это следует из соотношения d(b_i,b_j)=w(b_i+b_j).

В предыдущем примере наименьший вес ненулевого слова равен 3. Следовательно, этот код способен исправлять однократную ошибку или обнаруживать однократную и двойную.

При использовании группового кода незамеченными остаются те и только те ошибки, которые отвечают строкам ошибок, в точности равным кодовым словам.

Такие строки ошибок переводят одно кодовое слово в другое.

Следовательно, вероятность того, что ошибка останется необнаруженной, равна сумме вероятностей всех строк ошибок, равных кодовым словам.

В рассмотренном примере вероятность ошибки равна 4p^3q^3+3p^2q^4.

Рассмотрим задачу оптимизации декодирования группового кода с двоичной матрицей кодирования E. Требуется минимизировать вероятность того, что D(T(aE))
e a.

Схема декодирования состоит из группы Gвсех слов, которые могут быть приняты (\#G=2^n). Так как кодовые слова Bобразуют нормальную (нормальность следует из коммутативности G) подгруппу G, то множеству Gможно придать структуру таблицы: будем записывать в одну строку те элементы G, которые являются членами одного смежного класса Gпо B. Первая строка, соответствующая нулевому слову из G, будет тогда всеми кодовыми словами из B, т.е. b_0, b_1, ldots, b_{2^m-1}. В общем случае, если g_iin G, то строка, содержащая g_i(смежный класс g_iB) имеет вид b_0+g_i, b_1+g_i, ldots, b_{2^m-1}+g_i.

Лидером каждого из таких построенных смежных классов называется слово минимального веса.

Каждый элемент gиз Gоднозначно представляется в виде суммы g_i+b_j, где g_iin G- лидер соответствующего смежного класса и b_jin B.

Множество классов смежности группы образуют фактор-группу, которая есть фактор-множество множества Gпо отношению эквивалентности-принадлежности к одному смежному классу, а это означает, что множества, составляющие это фактор-множество, образуют разбиение G. Отсюда следует, что строки построенной таблицы попарно либо не пересекаются, либо совпадают.

Если в рассматриваемой таблице в первом столбце записать лидеры, то полученная таблица называется таблицей декодирования. Она имеет вид:

centerline{vbox{offinterlineskiphalign{&strutquad#hfilcr
b_0&           b_1&               b_2&     cdots& b_{2^m-1}cr
g_1&           g_1+b_1&           g_1+b_2& cdots& g_1+b_{2^m-1}cr
cdots&        cdots&            cdots&  cdots& cdotscr
g_{2^{n-m}-1}& g_{2^{n-m}-1}+b_1& g_{2^{n-m}-1}+b_2& cdotsquad&
   g_{2^{n-m}-1}+b_{2^m-1}.cr}}}

То, что строк будет 2^{n-m}следует из теоремы Лагранжа1) , т.к. 2^{n-m}- это порядок фактор-группы G/B, \#(G/B)=\#(G)/\#(B), \#B=2^m.

Декодирование слова g=b_j+g_iсостоит в выборе кодового слова b_jв качестве переданного и последующем применении операции, обратной умножению на E. Такая схема декодирования сможет исправлять ошибки.

Для (3,6)-кода из рассматриваемого примера таблица декодирования будет следующей:

centerline{vbox{offinterlineskiphalign{&#&struthskip7pt#cr
000000 && 100110 && 010011 && 110101 && 001111 && 101001 && 011100 && 111010cr
100000 && 000110 && 110011 && 010101 && 101111 && 001001 && 111100 && 011010cr
010000 && 110110 && 000011 && 100101 && 011111 && 011001 && 001100 && 101010cr
001000 && 101110 && 011011 && 111101 && 000111 && 100001 && 010100 && 110010cr
000100 && 100010 && 010111 && 110001 && 001011 && 101101 && 011000 && 111110cr
000010 && 100100 && 010001 && 110111 && 001101 && 101011 && 011110 && 111000cr
\%}}}
\%centerline{vbox{offinterlineskiphalign{&#&struthskip7pt#cr
000001 && 100111 && 010010 && 110100 && 001110 && 101000 && 011101 && 111011cr
000101 && 100011 && 010110 && 110000 && 001010 && 101100 && 011001 &&
111111.cr
}}}

Первая строка в ней - это строка кодовых слов, а первый столбец - это лидеры.

Чтобы декодировать слово b_j+e, следует отыскать его в таблице и выбрать в качестве переданного слово в том же столбце и в первой строке.

Например, если принято слово 110011 (2-я строка, 3-й столбец таблицы), то считается, что было передано слово 010011; аналогично, если принято слово 100101 (3-я строка, 4-й столбец таблицы), переданным считается слово 110101, и т.д.

Групповое кодирование со схемой декодирования посредством лидеров исправляет все ошибки, строки которых совпадают с лидерами. Следовательно, вероятность правильного декодирования переданного по двоичному симметричному каналу кода равна сумме вероятностей всех лидеров, включая нулевой.

В рассмотренной схеме вероятность правильной передачи слова будет p^6+6p^5q+p^4q^2.

Кодовое слово любого столбца таблицы декодирования является ближайшим кодовым словом ко всем прочим словам данного столбца.

Пусть переданное слово b_iпринято как b_i+e, d(b_i,b_i+e)=w(e), т.е. это расстояние равно весу соответствующего лидера. Расстояние от b_i+eдо любого другого кодового слова b_jравно весу их поразрядной суммы, т.е. d(b_j,b_i+e)=w(b_j+b_i+e)=d(b_j+b_i,e)=d(b_k,e)=w(b_k+e)ge
w(e),т.к. e- лидер смежного класса, к которому принадлежат как b_k+e, так и b_i+e.

Доказано, при схеме декодирования лидерами по полученному слову берется ближайшее к нему кодовое.

Упражнение 40 Для кодирующих матриц

E_1=leftlbrackmatrix{
1& 0& 1& 0& 1cr
0& 1& 1& 1& 0cr}
ight
brack

, E_2=leftlbrackmatrix{
1& 0& 0& 1cr
0& 1& 0& 1cr
0& 0& 1& 0cr}
ight
brack:

Построить соответственно (2,5)-код и (3,4)-код.

Найти основные характеристики полученных кодов: минимальное расстояние между словами кода; вероятность необнаружения ошибки; максимальную кратность ошибок, до которой включительно они все исправляются или обнаруживаются.

Построить таблицы декодирования.

Уточнить характеристики полученных кодов, при использовании их для исправления ошибок, т.е. найти вероятность правильной передачи и описать ошибки, исправляемые этими кодами.

Во что будут декодированы слова: 10001, 01110, 10101, 1001, 0110, 1101?

Совершенные и квазисовершенные коды

Групповой (m,n)-код, исправляющий все ошибки веса, не большего k, и никаких других, называется совершенным.

Свойства совершенного кода1):

Для совершенного (m,n)-кода, исправляющего все ошибки веса, не большего k, выполняется соотношение sum^k_{i=0}C^i_n=2^{n-m}. Верно и обратное утверждение;

Совершенный код, исправляющий все ошибки веса, не большего k, в столбцах таблицы декодирования содержит все слова, отстоящие от кодовых на расстоянии, не большем k. Верно и обратное утверждение;

Таблица декодирования совершенного кода, исправляющего все ошибки в не более чем kпозициях, имеет в качестве лидеров все строки, содержащие не более kединиц. Верно и обратное утверждение.

Совершенный код - это лучший код, обеспечивающий максимум минимального расстояния между кодовыми словами при минимуме длины кодовых слов. Совершенный код легко декодировать: каждому полученному слову однозначно ставится в соответствие ближайшее кодовое. Чисел m, nи k(1<k<{n-1over2}), удовлетворяющих условию совершенности кода очень мало. Но и при подобранных m, nи kсовершенный код можно построить только в исключительных случаях.

Если m, nи kне удовлетворяют условию совершенности, то лучший групповой код, который им соответствует называется квазисовершенным, если он исправляет все ошибки кратности, не большей k, и некоторые ошибки кратности k+1. Квазисовершенных кодов также очень мало.

Двоичный блочный (m,n)-код называется оптимальным, если он минимизирует вероятность ошибочного декодирования. Совершенный или квазисовершенный код - оптимален. Общий способ построения оптимальных кодов пока неизвестен.

Для любого целого положительного числа rсуществует совершенный (m,n)-код, исправляющий одну ошибку, называемый кодом Хэмминга (Hamming), в котором m=2^r-r-1и n=2^r-1.

Действительно, sum^1_{i=0}C^i_n=1+2^r-1=2^r=2^{n-m}.

Порядок построения кода Хэмминга следующий:

Выбираем целое положительное число r. Сообщения будут словами длины m=2^r-r-1, а кодовые слова - длины n=2^r-1;

В каждом кодовом слове b=b_1b_2ldots b_nrбит с индексами-степенями двойки (2^0, 2^1, ldots, 2^{r-1})- являются контрольными, остальные - в естественном порядке - битами сообщения. Например, если r=4, то биты b_1, b_2, b_4, b_8- контрольные, а b_3, b_5, b_6, b_7, b_9, b_{10}, b_{11}, b_{12}, b_{13}, b_{14},
b_{15}- из исходного сообщения;

Строится матрица Mиз 2^r-1строк и rстолбцов. В i-ой строке стоят цифры двоичного представления числа i. Матрицы для r=2, 3 и 4 таковы: M_{3	imes2}=leftlbrackmatrix{01cr
                                      10cr
                                      11cr}
ight
brackqquad
M_{7	imes3}=leftlbrackmatrix{001cr
                            010cr
                            011cr
                            100cr
                            101cr
                            110cr
                            111cr}
ight
brackqquad
M_{15	imes4}=leftlbrackmatrix{0001cr
                             0010cr
                             0011cr
                             0100cr
                             0101cr
                             0110cr
                             0111cr
                             1000cr
                             1001cr
                             1010cr
                             1011cr
                             1100cr
                             1101cr
                             1110cr
                             1111cr}
ight
brack;

Записывается система уравнений bM=0, где M- матрица из предыдущего пункта. Система состоит из rуравнений. Например, для r=3:

leftlbracematrix{
   b_4+b_5+b_6+b_7=0cr
   b_2+b_3+b_6+b_7=0cr
   b_1+b_3+b_5+b_7=0cr}
ight.;

Чтобы закодировать сообщение a, берутся в качестве b_j, jне равно степени двойки, соответствующие биты сообщения и отыскиваются, используя полученную систему уравнений, те b_j, для которых j- степень двойки. В каждое уравнение входит только одно b_j, j=2^i. В выписанной системе b_4входит в 1-е уравнение, b_2- во второе и b_1- в третье. В рассмотренном примере сообщение a=0111будет закодировано кодовым словом b=0001111.

Декодирование кода Хэмминга проходит по следующей схеме. Пусть принято слово b+e, где b- переданное кодовое слово, а e- строка ошибок. Так как bM=0, то (b+e)M=bM+eM=eM. Если результат нулевой, как происходит при правильной передаче, считается, что ошибок не было. Если строка ошибок имеет единицу в i-й позиции, то результатом произведения eMбудет i-я строка матрицы Mили двоичное представление числа i. В этом случае следует изменить символ в i-й позиции слова b+e, считая позиции слева, с единицы.

Пример. (4,7)-код Хэмминга имеет в качестве одного из кодовых слов b=0001111. Матрица M_{7	imes3}приведена на шаге 3 хода построения кода Хэмминга. Ясно, что bM=0. Добавим к bстроку ошибок e=0010000. Тогда b+e=0011111и (b+e)M=011=3_{10}, т.е. ошибка находится в третьей позиции. Если e=0000001, то b+e=0001110и позиция ошибки - (b+e)M=111=7_{10}и т.п. Если ошибка допущена в более чем в одной позиции, то декодирование даст неверный результат.

Код Хэмминга - это групповой код.

Это следует из того, что (m,n)-код Хэмминга можно получить матричным кодированием, при помощи m	imes n-матрицы, в которой столбцы с номерами не степенями 2 образуют единичную подматрицу. Остальные столбцы соответствуют уравнениям шага 4 построения кода Хэмминга, т.е. 1-му столбцу соответствует уравнение для вычисления 1-го контрольного разряда, 2-му - для 2-го, 4-му - для 4-го и т.д. Такая матрица будет при кодировании копировать биты сообщения в позиции не степени 2 кода и заполнять другие позиции кода согласно схеме кодирования Хэмминга.

Пример. Кодирующая матрица для (4,7)-кода Хэмминга -

E=leftlbrackmatrix{1110000cr
                        1001100cr
                        0101010cr
                        1101001cr}
ight
brack.

Ее столбцы с номерами 3, 5, 6 и 7 образуют единичную подматрицу. Столбцы с номерами 1, 2 и 4 соответствуют уравнениям для вычисления контрольных бит, например, уравнению b_1=b_3+b_5+b_7соответствует столбец 1101, т.е. для вычисления первого контрольного разряда берутся 1, 2 и 4 биты исходного сообщения или биты 3, 5 и 7 кода.

К (m,n)-коду Хэмминга можно добавить проверку четности. Получится (m,n+1)-код с наименьшим весом ненулевого кодового слова 4, способный исправлять одну и обнаруживать две ошибки.

Коды Хэмминга накладывают ограничения на длину слов сообщения: эта длина может быть только числами вида 2^r-r-1: 1, 4, 11, 26, 57, ldotsНо в реальных системах информация передается байтам или машинными словами, т.е. порциями по 8, 16, 32 или 64 бита, что делает использование совершенных кодов не всегда подходящим. Поэтому в таких случаях часто используются квазисовершенные коды.

Квазисовершенные (m,n)-коды, исправляющие одну ошибку, строятся следующим образом. Выбирается минимальное nтак, чтобы

{2^nover n+1}ge2^m.

Каждое кодовое слово такого кода будет содержать k=n-mконтрольных разрядов. Из предыдущих соотношений следует, что

2^k=2^{n-m}ge
n+1=C^1_n+C^0_n=m+k+1.

Каждому из nразрядов присваивается слева-направо номер от 1 до n. Для заданного слова сообщения составляются kконтрольных сумм S_1, ldots,
S_kпо модулю 2 значений специально выбранных разрядов кодового слова, которые помещаются в позиции-степени 2 в нем: для S_i(1le ile k)выбираются разряды, содержащие биты исходного сообщения, двоичные числа-номера которых имеют в i-м разряде единицу. Для суммы S_1это будут, например, разряды 3, 5, 7 и т.д., для суммы S_2- 3, 6, 7 и т.д. Таким образом, для слова сообщения a=a_1ldots a_mбудет построено кодовое слово b=S_1S_2a_1S_3a_2a_3a_4S_4a_5ldots a_m. Обозначим S^*_iсумму по модулю 2 разрядов полученного слова, соответствующих контрольной сумме S_iи самой этой контрольной суммы. Если S^*_kldots S^*_1=0, то считается, что передача прошла без ошибок. В случае одинарной ошибки S^*_kldots
S^*_1будет равно двоичному числу-номеру сбойного бита. В случае ошибки, кратности большей 1, когда S^*_kldots S^*_1>n, ее можно обнаружить. Подобная схема декодирования не позволяет исправлять некоторые двойные ошибки, чего можно было бы достичь, используя схему декодирования с лидерами, но последняя значительно сложнее в реализации и дает незначительное улучшение качества кода.

Пример построения кодового слова квазисовершенного (9,n)-кода, исправляющего все однократные ошибки, для сообщения 100011010.

{2^{12}over13}={4096over13}<2^9=512quadhbox{и}quad
{2^{13}over14}={4096over7}>512,hbox{ т.е. }n=13.

Искомое кодовое слово имеет вид lower.1exhbox{vbox{halign{&hbox to 1.1em{hfil # hfil}cr
_1& _2& _3& _4&_5&_6&_7& _8&_9&_{10}&_{11}&_{12}&_{13}cr
S_1&S_2& 1&S_3& 0& 0& 0&S_4& 1&    1&    0&    1&    0cr}}}. Далее нужно вычислить контрольные суммы.

matrix{hfill1_{10}=0001_2cr
hfill2_{10}=0010_2cr
hfill3_{10}=0011_2cr
hfill4_{10}=0100_2cr
hfill5_{10}=0101_2cr
hfill6_{10}=0110_2cr
hfill7_{10}=0111_2cr
hfill8_{10}=1000_2cr
hfill9_{10}=1001_2cr
hfill10_{10}=1010_2cr
hfill11_{10}=1011_2cr
hfill12_{10}=1100_2cr
hfill13_{10}=1101_2cr}qquad
matrix{S_1=b_3+b_5+b_7+b_9+b_{11}+b_{13}=0hfillcr
S_2=b_3+b_6+b_7+b_{10}+b_{11}=0hfillcr
S_3=b_5+b_6+b_7+b_{12}+b_{13}=1hfillcr
S_4=b_9+b_{10}+b_{11}+b_{12}+b_{13}=1hfillcr}

Таким образом, искомый код - 0011000111010. Если в процессе передачи этого кода будет испорчен его пятый бит, то приемник получит код 0011100111010. Для его декодирования опять вычисляются контрольные суммы:

$$matrix S_1^*=b_1+b_3+b_5+b_7+b_9+b_{11}+b_{13}=1hfillcr\
S_2^*=b_2+b_3+b_6+b_7+b_{10}+b_{11}=0hfillcr\
S_3^*=b_4+b_5+b_6+b_7+b_{12}+b_{13}=1hfillcr\
S_4^*=b_8+b_9+b_{10}+b_{11}+b_{12}+b_{13}=0hfillcr}\
ifdimhsize>155mmqquadelse$${}$$fi S_4^*S_3^*S_2^*S_1^*=0101_2=5_{10}.$$

Приемник преобразует изменением пятого бита полученное сообщение в отправленное передатчиком, из которого затем отбрасыванием контрольных разрядов восстанавливает исходное сообщение.

Совершенный код Хэмминга также можно строить по рассмотренной схеме, т.к. для него 2^n/(n+1)=2^m.

Для исправление одинарной ошибки к 8-разрядному коду достаточно приписать 4 разряда (2^{12}/13>2^8), к 16-разрядному - 5, к 32-разрядному - 6, к 64-разрядному - 7.

Упражнение 41 Может ли (6,14)-код, минимальное расстояние между кодовыми словами которого 5, быть совершенным?

Упражнение 42 Построить кодовые слова квазисовершенного (9,n)-кода, исправляющего однократные ошибки, для тех сообщений, которые соответствуют числам 55, 200 и декодировать слова 1000001000001, 1100010111100, полученные по каналу связи, использующему этот код.

Полиномиальные коды

При полиномиальном кодировании каждое сообщение отождествляется с многочленом, а само кодирование состоит в умножении на фиксированный многочлен. Полиномиальные коды - блочные и отличаются от рассмотренных ранее только алгоритмами кодирования и декодирования.

Пусть a=a_0ldots a_{m-1}- двоичное сообщение. Тогда сопоставим ему многочлен a(x)=a_0+a_1x+cdots+a_{m-1}x^{m-1}. Все вычисления происходят в поле классов вычетов по модулю 2, т. е. от результата любой арифметической операции берется остаток от его деления на 2.

Например, последовательности 10011 при m=5соответствует многочлен 1+x^3+x^4.

Зафиксируем некоторый многочлен степени k,

g(x)=g_0+g_1x+cdots+g_kx^k,quad g_0
e0,quad
g_k
e0.

Полиномиальный код с кодирующим многочленом g(x)кодирует слово сообщения a(x)многочленом b(x)=a(x)g(x)=b_0+b_1x+cdots+b_{n-1}x^{n-1}или кодовым словом из коэффициентов этого многочлена b=b_0ldots b_{n-1}. Условия g_0
e0и g_k
e0необходимы, потому что в противном случае b_0и b_{n-1}не будут нести никакой информации, т.к. они всегда будут нулями.

Пример. Рассмотрим кодирующий многочлен g(x)=1+x^2+x^3. Сообщение 01011, отвечающее многочлену a(x)=x+x^3+x^4, будет закодировано коэффициентами многочлена b(x)=g(x)a(x)=x+x^5+x^7, т.е. b=01000101.

Полиномиальный код с кодирующим многочленом g(x)степени kявляется матричным кодом с кодирующей матрицей Gразмерности m	imes(m+k):

G=leftlbrackmatrix{
g_0   & g_1  & g_2  & cdots & g_k     & 0       & 0
 & cdots & 0cr
0     & g_0  & g_1  & cdots & g_{k-1} & g_k     & 0
 & cdots & 0cr
0     & 0    & g_0  & cdots & g_{k-2} & g_{k-1} & g_k
 & cdots & 0cr
cdots&cdots&cdots& cdots &cdots   & cdots  &cdots& cdots &cdotscr
0     &0     &0     & cdots &cdots   & cdots  &cdots& cdots
&g_kcr}

ight
brack.

Т е. ненулевые элементы в j-й строке - это последовательность коэффициентов кодирующего многочлена, расположенных с j-го по (j+k)-й столбцах.

Например, (3,6)-код с кодирующим многочленом 1+x+x^3отвечает матрице

G=leftlbrackmatrix{1&1&0&1&0&0cr
                        0&1&1&0&1&0cr
                        0&0&1&1&0&1cr}
ight
brack

или отображению: 000
ightarrow000000; 001
ightarrow001101; 010
ightarrow011010; 011
ightarrow010111; 100
ightarrow110100; 101
ightarrow111001; 110
ightarrow101110; 111
ightarrow100011.

Полиномиальные коды являются групповыми.

Это следует из того, что коды, получаемые матричным кодированием, - групповые.

Рассмотрим (m,n)-код с кодирующим многочленом g(x). Строка ошибок e=e_0ldots e_{n-1}останется необнаруженной в том и только в том случае, если соответствующий ей многочлен e(x)=e_0+e_1x+cdots+e_{n-1}x^{n-1}делится на g(x).

Действительно, a(x)g(x)+e(x)делится на g(x)тогда и только тогда, когда e(x)делится на g(x). Поэтому любая ошибка, многочлен которой не делится на g(x), будет обнаружена и, соответственно, любая ошибка, многочлен которой делится на g(x), не может быть обнаружена.

Таким образом, обнаружение ошибки при использовании полиномиального кода с кодирующим многочленом g(x)может быть реализовано при помощи алгоритма деления многочленов с остатком: если остаток ненулевой, то при передаче произошло искажение данных.

Коды Хэмминга можно строить как полиномиальные, например, кодирующий многочлен x^3+x^2+1определяет совершенный (4,7)-код, отличный от рассмотренного ранее.

Вообще же, если кодирующий многочлен g(x), порождающий соответствующий (m,n)-код, не является делителем ни одного из многочленов вида x^j+1при j<n, то минимальное расстояние между кодовыми словами порожденного им кода не меньше 3.

Пусть d- минимальное расстояние между кодовыми словами, оно равно минимуму среди весов ненулевых кодовых слов. Предположим d=2. Тогда существует a(x)такой, что