close

Вход

Забыли?

вход по аккаунту

?

IT labs part2 twoside

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное бюджетное образовательное
учреждение высшего профессионального образования
Санкт-Петербургский государственный университет аэрокосмического
приборостроения
ТЕОРИЯ ИНФОРМАЦИИ
ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ
ДИСКРЕТНЫХ СООБЩЕНИЙ
Методические указания
к выполнению лабораторных работ
Санкт-Петербург
2011
Составители: Е. А. Беляев, С. С. Осипов , А. М. Тюрликов
Рецензент кандидат технических наук Г. С. Евсеев
Методические указания предназначены для выполнения лабораторных работ по курсу ѕТеория информацииї студентами направления ѕИнформационные системыї. Включают исследование классических алгоритмов помехоустойчивого кодирования дискретных сообщений на примере линейных кодов Хемминга и циклических кодов.
Подготовлены кафедрой информационно-сетевых технологий и рекомендованы к изданию редакционно-издательским советом СанктПетербургского государственного университета аэрокосмического приборостроения.
©
ГОУ ВПО Санкт-Петербургский государственный универси-
тет аэрокосмического приборостроения, 2011
Редактор
А.В. Подчепаева
Подписано к печати 19.04.11. Формат 60Ч84 1/16.
Бумага офсетная. Печать офсетная.
Усл. печ. л. 2,0. Тираж 100 экз. Заказ ќ443.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б.Морская ул., 67
Лабораторная работа ќ1
ЛИНЕЙНЫЕ КОДЫ ХЕММИНГА
Целью работы является приобретение практических навыков построения помехоустойчивых кодов на примере линейных кодов Хемминга, а также программная реализация алгоритмов обнаружения и
исправления ошибок.
1.1.
Постановка задачи
Пусть m0 , m1 , ..., mi , ... последовательность символов, подлежащих передаче по цифровому каналу связи, mi ? M , M =
{m0 , m1 , ..., mN ?1 }, где M входной алфавит канала; mj символ алфавита, i = 0, 1, 2, ..., j = 0, 1, 2, ..., N ? 1, N количество символов в
алфавите. Передающее устройство каждому символу mi сопоставляет
сигнал si (t), существующий на промежутке времени T равном 1/F , где
F скорость передачи символов по каналу связи. Передача сигнала
si (t) это возмущение некоторой физической среды, например электромагнитного поля в радиоканале. Принимающая сторона анализирует состояние среды, пытаясь обнаружить переданный сигнал. Поскольку на любую физическую среду влияют другие объекты (например, в
радиоканале: другие передающие устройства, линии электропередачи,
все электрические устройства, электромагнитные поля Земли, Солнца
и т.п.), сигнал на входе приемника всегда будет отличаться от переданного сигнала. Это может привести к ошибке распознавания сигнала, то
есть вместо mi будет принято решение, что передавался другой символ
из множества M . Такую ситуацию принято называть ошибкой передачи
символа.
Далее будем предполагать, что количество разных символов N = 2,
то есть множество M = {m0 , m1 }, символу m0 соответствует сигнал
s0 (t), а символу m1 сигнал s1 (t). Тогда возможно только два варианта ошибки приема символа: переход m0 в m1 и наоборот m1 в m0 .
Обозначим m0 цифрой 0, а m1 цифрой 1. Тогда последовательность
сообщений на входе и выходе канала можно представить как двоичные
последовательности, а влияние помех как действие некоторого внеш-
3
него источника. Этот источник генерирует символ 0, если переданный
символ принят правильно, и символ 1, если произошла ошибка приема, как это показано на рис. 1.1. на котором символы mi , ei , yi ? {0, 1},
i = 0, 1, 2, ....
????????
?????
e0 e1 ... ei ...
m0 m1 ... mi ...
???? ??????
????????
?????
y0 y1 ... yi ...
????? ??????
Рис. 1.1. Передача данных по цифровому каналу
Для уменьшения количества ошибок при передаче сообщений используют так называемые помехоустойчивые коды. Основная идея, заложенная в их построении, состоит в том, что помимо информационных
символов, подлежащих доставке получателю, в передаваемую последовательность вводят проверочные символы. Проверочные символы связываются с информационными по тому или иному правилу, известному
как передающей, так и приемной стороне. В большинстве случаев, используя это правило можно как обнаруживать ошибки передачи, так
и устранять их, если количество проверочных символов достаточно велико. Таким образом, в системе передачи информации появляются еще
два устройства: кодер канала, устанавливающий связь между информационными и проверочными символами, и декодер канала, обнаруживающий и, при возможности, устраняющий ошибки передачи символов
(рис. 1.2).
????????
?????
e0 e1 ... ei ...
m0 m1 ... mi ...
?????
??????
c0 c1 ... ci ...
????????
?????
y0 y1 ... yi ... ??????? m'0 m'1 ... m'i ...
??????
Рис. 1.2. Помехоустойчивая передача данных по цифровому каналу
4
1.2.
Предварительные сведения
1.2.1.
Конечные поля
Конечное множество элементов произвольной природы X называется конечным полем (или полем Галуа), если имеют место следующие
свойства.
1. На множестве определены операции сложения и умножения. Результат сложения и (или) умножения принадлежит множеству X
(множество является замкнутым по операциям сложения и умножения).
2. Для любых элементов множества xi , xj , xk ? X справедливы
аксиомы ассоциативности, коммуникативности и дистрибутивности:
(xi + xj ) + xk = xi + (xk + xj ),
(xi · xj ) · xk = xi · (xk · xj ),
xi + xj = xj + xi ,
xi · xj = xj · xi ,
(xi + xj ) · xk = xi · xk + xj · xk .
3. Существует нулевой элемент x0 ? X для сложения и единичный
элемент x1 ? X для умножения:
xi + x0 = x0 + xi = xi ,
xi · x1 = x1 · xi = xi .
4. Для каждого элемента множества xi ? X существует единственный элемент xj ? X , который является обратным для сложения:
xi + xj = 0,
5. Для каждого элемента множества xi ? X , кроме элемента x0 , существует элемент xj ? X , который является обратным для умножения:
xi · xj = 1.
5
В литературе конечное поле обозначается через GF (q), где q количество элементов в конечном поле, которое представляется в виде
q = pm , где p простое число; m положительное целое число. Простейшим случаем конечного поля является поле GF (p), которое состоит
из вычетов по модулю p.
GF (5). Данное поле состоит из пяти элементов и
GF (5) = {0, 1, 2, 3, 4}. Нейтральный
элемент по сложению x0 = 0, нейтральный элемент по умножению x1 = 1. В табл. 1.1
Пример 1.1.
Рассмотрим поле
включает в себя все вычеты по модулю 5, то есть
показаны таблицы сложения и умножения элементов поля.
Таблица 1.1.
Cложение (слева) и умножение (справа) в поле GF (5)
0
1
2
3
4
0
1
2
3
4
0
0
1
2
3
4
0
0
0
0
0
0
1
1
2
3
4
0
1
0
1
2
3
4
2
2
3
4
0
1
2
0
2
4
1
3
3
3
4
0
1
2
3
0
3
1
4
2
4
4
0
1
2
3
4
0
4
3
2
1
Как видно из табл. 1.1, для каждого элемента поля существует обратный элемент по сложению (например, для элемента 4 обратный элемент 2, так как
(4 + 2)
mod 5 = 1) и по умножению (например, для элемента 4 обратный элемент 4, так как
(4 · 4) mod 5 = 1).
1.2.2.
Линейные пространства над конечным полем
Пусть X конечное поле и x = (x1 , x2 , ..., xn ) ? X n вектор, каждая
компонента которого является элементом этого конечного поля. Тогда
n
и y ? X n определяется как
сумма векторов x ? X
x + y = (x1 + y1 , x2 + y2 , ..., xn + yn ).
(1.1)
Если c ? X , то умножение вектора x на скаляр c определяется как
c · x = (c · x1 , c · x2 , ..., c · xn ).
Пример 1.2.
Пусть даны два вектора
x = (1, 2, 3, 4) и y = (4, 2, 3, 1), каждая комGF (5). Тогда x + y = (0, 4, 1, 0).
понента которых является элементом конечного поля
Пусть
c = 2, тогда c ·
x = (2, 4, 1, 3).
(1.2)
6
Произвольное множество векторов V образует линейное простран, если это множество является замкнутым по отношению к операциям сложения и умножения на скаляр. Это означает, что для любого
k = {1, 2, 3, ...} вектор
k
X
z=
ci · xi
(1.3)
ство
i=1
принадлежит множеству V при любых ci ? X и xi ? X n . Правую часть выражения (1.3) называют линейной комбинацией векторов
x1 , x2 , ..., xk .
Пример 1.3.
Рассмотрим два множества векторов
V1 и V2 над полем GF (2) =
{0, 1}.
V1
?
?
000 ?
?
?
?
?
?
110
=
,
? 011 ?
?
?
?
?
101
V2
?
?
000 ?
?
?
?
?
?
100
=
.
? 010 ?
?
?
?
?
001
V1 является линейным пространством, так как сумма произвольных
V1 принадлежит множеству V1 . Множество V2 не является линейным
пространством. Например, результатом суммы векторов (100) + (010) является вектор (110), который не входит во множество V2 .
Множество
векторов из
Подмножество линейного пространства, для которого выполняются все свойства линейного пространства, называется линейным подпространством.
Пример 1.4.
Рассмотрим два множества векторов
V1 и V2 над полем GF (2) =
{0, 1}.
V1
Множество
?
?
000 ?
?
?
?
?
?
?
?
?
001 ?
?
?
?
?
?
?
?
?
? 010 ?
,
=
100
?
?
?
?
?
?
101
?
?
?
?
?
?
?
?
?
?
? 110 ?
?
?
111
V2
?
?
000 ?
?
?
?
?
?
110
=
.
?
? 011 ?
?
?
?
101
V2 является линейным подпространством линейного пространства V1 .
Векторы x1 , x2 , ..., xk называются линейно независимыми, если равенство
c1 · x1 + c2 · x2 + ... + ck · xk = 0,
(1.4)
где 0 нулевой вектор, справедливо только в том случае, если
c1 = c2 = ... = ck = 0.
Пример 1.5.
Векторы
зависимыми, поскольку
(1.5)
(0, 1, 1, 1) и (0, 2, 2, 2) в поле GF (5) являются линейно
2 · (0, 1, 1, 1) = (0, 2, 2, 2).
7
В каждом линейном пространстве существуют такие линейно независимые векторы x1 , x2 , ..., xk , что любой вектор линейного пространства
xi = c1 · x1 + c2 · x2 + ck · xk .
(1.6)
Такие векторы называются базисными
ства.
Пример 1.6.
векторами
Рассмотрим два множества векторов
{0, 1}.
V1
?
?
000 ?
?
?
?
?
?
?
?
?
001 ?
?
?
?
?
?
?
?
?
010
?
?
=
,
100
?
?
?
? 101 ?
?
?
?
?
?
?
?
?
? 110 ?
?
?
?
?
?
111
Векторы, входящие во множество
ного пространства
V1 .
V2
линейного простран-
V1 и V2 над полем GF (2) =
?
?
? 100 ?
=
.
010
?
?
001
V2 , являются базисными векторами для линей-
Пусть множество векторов G = {g1 , g2 , ..., gk } являются базисом
линейного подпространства V. Выберем два произвольных базисных
вектора gi ? G и gj ? G и образуем вектор g0i как линейную комбинацию следующего вида:
g0i = c1 · gi + c2 · gj ,
(1.7)
где c1 6= 0, c2 6= 0. Заменим во множестве G вектор gi на вектор g0i .
Можно показать, что полученное в результате множество векторов
G0 = {g1 , g2 , ..., gi?1 , g0i , gi+1 , ..., gk } также является базисом линейного подпространства V.
Пример 1.7.
V1 и V2 из примера 1.6. Во
V2 заменим первый вектор на сумму первого и вто-
Рассмотрим два множества векторов
множестве базисных векторов
рого. В результате получится множество векторов
V
0
2
?
?
? 110 ?
=
,
010
?
?
001
которые также являются базисными векторами для линейного пространства
V1 .
Из этого примера следует, что одному линейному подпространству
может соответствовать несколько множеств базисных векторов.
8
Пусть X конечное поле и x ? X n , y ? X n векторы, каждая
компонента которых является элементом этого конечного поля. Тогда
скалярное произведение векторов x и y определяется следующим образом:
n
X
x·y=
xi · yi ? X.
(1.8)
i=1
Векторы x и y называются ортогональными, если x · y = 0.
Пусть Vk ? X n линейное пространство размерности k (то есть
содержит q k векторов и любые k линейно независимых векторов образуют базис линейного пространства) и W ? X n множество векторов,
ортогональных к Vk , то есть любое скалярное произведение векторов
x · y = 0 для любой пары векторов x ? Vk и y ? W. Множество
W называется ортогональным дополнением пространства Vk . Можно
доказать [1], что ортогональное дополнение W является линейным подпространством пространства Vk и имеет размерность n ? k .
1.2.3.
Порождающая матрица линейного пространства
Пусть векторы g1 = (g11 , ..., g1n ), g2 = (g21 , ..., g2n ), ..., gk =
(gk1 , ..., gkn ) образуют базис линейного пространства Vk . Тогда любой
вектор x в линейном пространстве Vk может быть получен как линейная комбинация базисных векторов:
x = m1 · g1 + m2 · g2 + ... + mk · gk .
(1.9)
Выражение (1.9) может быть записано в матричном виде как
g11
? g21
x = (m1 , m2 , ..., mk ) · ?
? .
gk1
?
g12
g22
.
gk2
?
. g1n
. g2n ?
? = m · G,
.
. ?
. gkn
(1.10)
где m = (m1 , m2 , ..., mk ) и k Чn матрица G имеет в качестве своих строк
базисные векторы линейного пространства Vk . Матрица G называется
порождающей матрицей линейного пространства Vk . Перебирая все
возможные комбинации вектора m = (m1 , m2 , ..., mk ) путем произведения m · G можно получить все векторы линейного пространства Vk .
9
1.2.4.
Проверочная матрица линейного пространства
Линейное пространство также может быть задано при помощи ортогонального дополнения. Пусть Vk ? X n линейное пространство
размерности k и Wr ? X n ортогональное дополнение для Vk . Размерность Wr равна r = n ? k . Следовательно, в Wr имеется r базисных
векторов. Обозначим эти базисные векторы через h1 = (h11 , ..., h1n ),
h2 = (h21 , ..., h2n ), ..., hr = (hr1 , ..., hrn ). Обозначим через H матрицу,
строками которой являются векторы h1 , h2 , ..., hr :
h11
? h21
H=?
? .
hr1
?
h12
h22
.
hr2
.
.
.
.
?
h1n
h2n ?
?.
. ?
hrn
(1.11)
Произвольный вектор x = (x1 , ..., xn ) ? Vk удовлетворяет следующей системе линейных уравнений:
?
h11 · x1 + ... + h1n · xn = 0,
?
?
?
h21 · x1 + ... + h2n · xn = 0,
? ......
?
?
hr1 · x1 + ... + hrn · xn = 0,
(1.12)
или в матричной записи
x · HT = 0.
(1.13)
Систему уравнений (1.13) следует рассматривать как проверку принадлежности вектора x линейному пространству Vk . Поэтому H называется проверочной матрицей линейного пространства Vk .
Из (1.10) и (1.13) следует, что
m · G · HT = 0.
(1.14)
Так как равенство (1.14) выполняется для всех векторов m, то любая пара порождающих и проверочных матриц линейного пространства
связаны следующим образом:
G · HT = 0.
10
(1.15)
1.3.
1.3.1.
Линейные коды
Формирование кодового слова линейного кода по
информационной последовательности
q -ичным кодом длины n c k информационными символами, или (n, k)-кодом над полем GF (q), называется k -мерное подпространство линейного n-мерного пространства всех векторов над полем
GF (q).
Все свойства линейного пространства переносятся и на линейные
коды. Как и линейное пространство, линейный (n, k)-код задается базисными векторами g1 = (g11 , ..., g1n ), g2 = (g21 , ..., g2n ), ..., gk =
(gk1 , ..., gkn ), gij ? GF (q) или порождающей матрицей
Линейным
g11
? g21
G=?
? .
gk1
?
g12
g22
.
gk2
?
. g1n
. g2n ?
?,
.
. ?
. gkn
(1.16)
при этом кодовое слово c = (c1 , c2 , ..., cn ) является линейной комбинацией базисных векторов:
c = m1 · g1 + ... + mk · gk = m · G,
(1.17)
где m = (m1 , m2 , ..., mk ) информационная последовательность. Соотношение (1.17) представляет собой правило кодирования, по которому
информационная последовательность m = (m1 , m2 , ..., mk ) отображается в кодовое слово c = (c1 , c2 , ..., ck ).
Если порождающую матрицу G можно представить как
G = [Ik |G2 ],
(1.18)
где Ik единичная матрица размером k Ч k , то говорят, что порождающая матрица имеет левую каноническую форму.
Если порождающая матрица имеет каноническую форму, то линейный код называется систематическим. Для систематического кода кодовое слово представляется как
с = m · G = m · [Ik |G2 ] = (m, m · G2 ),
11
(1.19)
то есть кодовое слово состоит из двух подслов. Левое подслово является
информационной последовательностью m = (m1 , m2 , ..., mk ) длиной k ,
правое подслово состоит из r = n ? k проверочных символов.
Пример 1.8.
дового слова
Пусть порождающая матрица для линейного кода с длиной ко-
n = 7 и информационной последовательности длины k = 4 имеет
следующий вид:
?
G
1
? 0
=?
? 0
0
0
1
0
0
0
0
1
0
0
0
0
1
Необходимо сформировать кодовое слово
сти
m
0
1
1
1
?
1
1 ?
?.
0 ?
1
1
0
1
1
c для информационной последовательно-
= (0101). В соответствии с (1.19) кодовое слово формируется как
?
с=m·G
1.3.2.
1
? 0
?
= (0101) ?
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
1
1
?
1
1 ?
? = (0101010).
0 ?
1
Минимальное расстояние линейного кода
Пусть x и y два слова из X n . Расстоянием Хемминга d(x, y)
между x и y называется число позиций, в которых эти два слова различаются.
Пример 1.9.
Пусть
x = (0, 2, 1, 1) и y = (0, 1, 1, 2), тогда d(x, y) = 2.
Пусть С = (c1 , ..., cM ) код длины n над алфавитом X . Минимальным расстоянием кода C называется наименьшее из попарных расстояний Хемминга между различными кодовыми словами из C. Минимальное расстояние обозначается через d и вычисляется как
d=
min
x ,x ?C,i6=j
i
d(xi , xj ).
(1.20)
j
Для определения минимального расстояния линейного кода можно
воспользоваться следующими теоремами [1].
Теорема 1.1. Минимальное расстояние линейного кода C равно минимальному из весов ненулевых кодовых слов:
d=
min w(c).
c?C,c6=0
(1.21)
Теорема 1.2. Если любые l ? d?1 столбцов проверочной матрицы H
линейного кода линейно независимы, то минимальное расстояние кода
будет по меньшей мере d. Если при этом найдутся d линейно зависимых
столбцов, то минимальное расстояние кода равно d.
12
Говорят, что код обнаруживает ошибки кратности f , если найдется
алгоритм, позволяющий определить наличие искажений в любом принятом слове при условии, что число ошибочных символов в слове не
превосходит f . Говорят, что код исправляет ошибки кратности t, если найдется алгоритм, позволяющий указать положение ошибок и их
величины при условии, что число ошибочных символов в слове не превосходит t.
Следующие теоремы [1] связывают минимальное расстояние кода d
со способностью обнаруживать или исправлять ошибки.
Теорема 1.3. Код с минимальным расстоянием d обнаруживает любые ошибки кратности f ? d ? 1.
Теорема 1.4. Код с минимальным расстоянием d исправляет любые
ошибки кратности t = (d ? 1)/2.
1.4.
1.4.1.
Коды Хемминга
Построение проверочной и порождающей матрицы
Коды Хемминга относятся к линейным кодам, которые обеспечивают минимально возможное количество проверочных символов для минимального кодового расстояния d = 3. Рассмотрим метод построения
проверочной и порождающей матрицы систематического кода Хемминга над полем GF (2).
Пусть порождающая матрица кода G записывается в левой канонической форме:
G = [Ik |G2 ],
(1.22)
где Ik единичная подматрица размером k Ч k и G2 подматрица
размером r Ч k .
Проверочную матрицу кода H запишем как
H = [H1 |H2 ],
(1.23)
где H1 подматрица размером r Ч k , H2 подматрица размером r Ч r.
Из (1.15) следует, что
0 = G · HT = [Ik |G2 ]
HT
1
HT
2
13
= HT1 + G2 · HT2 .
(1.24)
Пусть проверочная матрица H представлена в правой канонической
форме, то есть HT2 является единичной подматрицей. Тогда,
T
T
0 = HT
1 + G2 · H2 = H1 + G2 .
(1.25)
С учетом того, что код строится над полем GF (2), из (1.25) получим
G2 = HT
1.
(1.26)
Из теоремы 1.2 следует, что для построения линейного кода с минимальным расстоянием d = 3 любые два столбца проверочной матрицы H должны быть линейно независимы. В случае кода над полем
GF (2) это означает, что любые два столбца матрицы H должны быть
различны и матрица H не должна содержать нулевого столбца. Легко
показать, что это справедливо в том случае, когда n = k + r ? 2r ? 1 [2].
При этом, для удобства построения, матрица H должна быть записана в
правой канонической форме, то есть содержать единичную подматрицу
в правой части.
Таким образом, алгоритм построения проверочной и порождающей
матрицы состоит из трех основных шагов.
Алгоритм 1.1. Построение проверочной и порождающей
матрицы кода Хемминга над полем GF (2)
Входные данные.
Длина кодового слова n.
Длина информационной последовательности k .
Шаг 1.
r := n ? k .
Сформировать H1 размером r Ч k из k различных столбцов,
каждый из которых содержит более одной единицы.
Шаг 2.
Сформировать H2 как единичную матрицу r Ч r.
H := [H1 |H2 ].
Шаг 3.
Сформировать G1 как единичную матрицу k Ч k .
G := [G1 |HT
1 ].
14
Проиллюстрируем построение проверочной и порождающей матрицы кода Хемминга на следующем примере.
Пример 1.10.
Требуется построить проверочную и порождающую матрицу кода
Хемминга с длиной кодового слова
длины
n = 7 и информационной последовательностью
k = 4. В соответствии с шагом 1 алгоритма формируется подматрица
H1
?
0
=? 1
1
1
0
1
1
1
0
?
1
1 ?,
1
затем в соответствии с шагом 2 формируется единичная матрица
и формируется проверочная матрица в виде:
?
0
= [ 1| 2] = ? 1
1
H H H
1
0
1
1
1
0
1
1
1
1
0
0
0
1
0
?
0
0 ?
1
В соответствии с шагом 3 формируется единичная подматрица
и порождающая матрица в виде:
?
1
? 0
T
?
= [ 1| 1 ] = ?
0
0
G G H
1.4.2.
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
1
1
H2 размером 3 Ч 3,
G1 размером 4 Ч 4
?
1
1 ?
?.
0 ?
1
Расширенные коды Хемминга
Расширенные коды Хемминга относятся к линейным кодам, которые обеспечивают минимально возможное количество проверочных
символов для минимального кодового расстояния d = 4. Увеличение
минимального расстояние кода достигается путем замены одного информационного символа исходного кода Хемминга на проверочный символ. Поэтому проверочная матрица такого кода должна иметь на одну
строку больше, чем в коде Хемминга.
В соответствии с теоремой 1.2 в проверочной матрице расширенного
кода Хемминга любые три столбца должны быть линейно независимые.
В случае кода над полем GF (2) это означает, что любые два столбца
матрицы H должны быть различны, матрица H не должна содержать
нулевого столбца и любые два столбца в сумме не должны давать третий.
15
Обозначим через H3 проверочную матрицу
мальным расстоянием d = 3. Тогда матрица
?
1 1 1 ... 1
?
?
H4 = ?
?
H3
кода Хемминга с мини-
?
?
?
?
?
(1.27)
удовлетворяет приведенным выше требованиям для кода с минимальным расстоянием d = 4. Во-первых, матрица H4 не содержит двух одинаковых столбцов и не содержит нулевой столбец, поскольку в матрице
H3 нет нулевых столбцов и все столбцы разные. Во-вторых, сумма по
модулю 2 любых двух столбцов не равна никакому третьему столбцу,
так как сумма двух столбцов будет содержать 0 в первом разряде, тогда
как все столбцы в H4 в первом разряде равны 1.
Для формирования порождающей матрицы расширенного кода
Хемминга проверочную матрицу H4 необходимо представить в правой
канонической форме. Так как строки матрицы H4 являют базисным
векторами линейного пространства, то каждый базисный вектор можно заменить другим базисным вектором, который является линейного
комбинацией исходных базисных векторов. В случае кодов над полем
GF (2) можно менять любую строку матрицы H4 на сумму двух или
более строк по модулю 2 до тех пор, пока матрица H4 не примет правую каноническую форму. Затем, аналогично коду Хемминга можно
построить порождающую матрицу.
Таким образом, алгоритм построения проверочной и порождающей
матрицы состоит из четырех основных шагов.
16
Алгоритм 1.2. Построение проверочной и порождающей
матрицы расширенного кода Хемминга над полем GF (2)
Входные данные.
Длина кодового слова n.
Длина информационной последовательности k .
Шаг 1.
r := n ? k .
Сформировать H31 размером (r ? 1) Ч k из k различных
столбцов, каждый из которых содержит более одной единицы
и последний столбец H31 содержит четное число единиц.
Шаг 2.
Сформировать H32 как единичную матрицу (r ? 1) Ч (r ? 1).
H3 := [H31 |H32 ].
Шаг 3. "
#
11 ... 1
4
H :=
.
3
H
Сложить все строки H4 и поместить результат в первую строку.
Привести H4 в правую каноническую форму путем сложения
первой строки с остальными строками.
Шаг 4.
Сформировать G41 как единичную матрицу k Ч k .
G4 := [G1 |(H41 )T ].
Проиллюстрируем построение проверочной и порождающей матрицы расширенного кода Хемминга на следующем примере.
Пример 1.11.
Требуется построить проверочную и порождающую матрицу рас-
ширенного кода Хемминга с длиной кодового слова
следовательностью длины
n = 7 и информационной поk = 3. В соответствии с шагом 1 алгоритма формируется
подматрица
H
?
3
1
0
=? 1
1
1
0
1
1
1
1
?
1
1 ?,
0
затем в соответствии с шагом 2 формируется единичная матрица
и формируется проверочная матрица в виде
H3
?
0
= [ 31 | 32 ] = ? 1
1
H H
1
0
1
17
1
1
1
1
1
0
1
0
0
0
1
0
?
0
0 ?.
1
H32 размером 3 Ч 3,
В соответствии с шагом 3 формируется проверочная матрица расширенного
кода как
?
H4
Затем сумма всех строк
1
? 0
=?
? 1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
1
0
0
?
1
0 ?
?.
0 ?
1
1
0
1
0
H4 по модулю 2 записывается в первую строку:
?
H4
1
? 0
=?
? 1
1
1
1
0
1
0
1
1
1
1
1
1
0
0
1
0
0
?
0
0 ?
?.
0 ?
1
0
0
1
0
Для формирования правой канонической формы первая строка матрицы
H4 склады-
вается со второй, результат сложения записывается во вторую строку. Затем первая
строка складывается с третьей, результат сложения записывается в третью строку.
В итоге матрица
H4 представляется как
?
H4
1
? 1
4
4
?
= [ 1| 2] = ?
0
1
H H
1
0
1
1
0
1
1
1
1
0
0
0
0
1
0
0
0
0
1
0
?
0
0 ?
?.
0 ?
1
В соответствии с шагом 4 формируется единичная подматрица
3 Ч 3 и порождающая матрица в виде
G = [G H
4
1 |(
1.4.3.
?
4 T
1) ]
1
=? 0
0
0
1
0
0
0
1
1
1
0
1
0
1
0
1
1
G41 размером
?
1
1 ?.
1
Декодирование по минимуму расстояния
Пусть требуется передать по цифровому каналу связи сообщение
m длиной k информационных символов при помощи кода Хемминга. В
соответствии с моделью системы передачи информации (см. рис. 1.2)
кодер канала формирует кодовое слово c = m · G длиной n символов,
где G порождающая матрица кода. В канале связи могут возникнуть
ошибки, в результате которых на вход декодера канала поступает сообщение
y = c + e,
(1.28)
где e вектор ошибок длины n. Если ошибок не было, то e = 0.
18
Операция декодирования линейного кода выполняется на стороне
декодера канала, который либо исправляет возникшие в пришедшем
сообщении ошибки, либо сигнализирует системе о том, что в пришедшем
сообщении обнаружены ошибки.
При декодировании по минимуму расстояния декодер канала хранит в памяти весь список кодовых слов ci ? C.
В режиме обнаружения ошибок по минимуму расстояния декодер
сравнивает поступившее сообщение y со списком кодовых слов. Если y
не совпадает ни с одним кодовым словом из C, то выносится решение,
что в пришедшем сообщении обнаружены ошибки.
В режиме исправления ошибок по минимуму расстояния декодер
попарно вычисляет расстояние Хемминга d(y, ci ) между пришедшим
сообщением y и всеми кодовыми словами из C. Затем из списка кодовых слов выбирается слово, которому соответствует меньшее значение
расстояния Хемминга. Другими словами, выбирается кодовое слово с
номером
j = arg min d(y, ci ).
(1.29)
i
Если в списке содержится несколько кодовых слов, которым соответствует наименьшее значение расстояния Хемминга, то выбирается любое из них. Из найденного слова cj извлекается сообщение m0 , которое
является выходом декодера канала. Причем, согласно теореме 1.4, равенство m0 = m гарантируется только тогда, когда количество возникших в канале связи ошибок t ? (d?1)/2, где d минимальное расстояние
кода.
Пример 1.12.
Пусть для передачи сообщения
m = (101) использовался расши-
ренный код Хемминга из примера 1.11 с порождающей матрицей
G
?
1
=? 0
0
0
1
0
0
0
1
Кодер канала формирует кодовое слово
c=m·G
?
1
= (101) ? 0
0
0
1
0
1
1
0
1
0
1
0
1
1
?
1
1 ?.
1
1
0
1
0
1
1
?
1
1 ? = (1011010).
1
c как
0
0
1
1
1
0
e = (0010000).
y = c + e = (1001010). Декодер
канала попарно вычисляет расстояние d(y, ci ) между пришедшим сообщением y с
каждым кодовым словом из C как показано в табл. 1.2:
Пусть в процессе передачи возникла одна ошибка и вектор ошибок
Тогда на входе декодера канала поступает сообщение
19
Таблица 1.2.
Декодирование кодов Хемминга по минимуму расстояния
i
mi ci = mi · G
0
000
0000000
2
1
001
0010111
4
2
010
0101011
4
3
011
0111100
6
4
100
1001101
6
5
101
1011010
1
6
110
1100110
3
7
111
1110001
5
Так как минимальное расстояние
y ci )
d( ,
y c5 ) = 1 соответствует кодовому слову c5 ,
d( ,
то декодер канала принимает решение о том, что на стороне кодера канала было
сформировано кодовое слово
1.4.4.
c = (1011010) и исходное сообщение m = (101).
Синдромное декодирование
Недостатком декодирования по минимуму расстояния является то,
что с увеличением длины кодового слова экспоненциально увеличивается количество кодовых слов, которые необходимо хранить в памяти
декодера. Поэтому, на практике такой способ декодирования применяется для кодовых слов малой длины.
Если кодовые слова имеют большую длину эффективнее использовать синдромное декодирование. Из свойств проверочной матрицы линейного кода (1.13) следует, что c · HT = 0. Поэтому величина
s = y · HT = (c+e) · HT = c · HT + e · HT = e · HT ,
(1.30)
называемая синдромом, зависит только от вектора ошибки e и не зависит от исходного кодового слова с. Причем если ошибок в канале не
было, то s = 0.
20
Для синдромов линейных кодов может быть доказана следующая
теорема [1].
Теорема 1.5. Пусть d минимальное расстояние линейного кода.
Тогда если e1 , e2 ? Xn два различных вектора ошибок, таких, что вес
каждого вектора ошибок меньше (d ? 1)/2, то s(e1 ) 6= s(e2 ). Другими
словами синдромы различных ошибок, вес которых не превышает (d ?
1)/2, различны.
Из теоремы следует, что для исправления ошибок, число которых не
превышает (d ? 1)/2, в декодере канала достаточно хранить синдромы,
которые соответствуют векторам ошибок веса не более (d ? 1)/2.
Алгоритм синдромного декодирования кодов Хемминга можно описать при помощи следующих трех шагов.
Алгоритм 1.3. Синдромное декодирование кодов Хемминга
Входные данные.
Длина кодового слова n.
Длина информационной последовательности k .
Проверочная матрица H.
Входная последовательность y.
Шаг 1.
Для i = 0, ..., n ? 1.
ei := 0.
ei [i] := 1.
si := ei · HT .
Шаг 2.
s? := y · HT .
Если s? = 0.
c := y.
Иначе
j := ?1.
Для i = 0, ..., n ? 1.
Если si = s? , то
j := i,
c := y + ei .
Шаг 3.
Если j 6= ?1, то
Извлечь сообщение m из c.
Иначе сообщить системе, что произошло более одной ошибки.
21
Следует отметить, что в алгоритме 1.3 шаг 1, связанный с построением таблицы соответствия синдромов и векторов ошибок, выполняется
только один раз. Полученная таблица хранится в памяти декодера канала и используется при декодировании всех поступающих сообщений.
Продемонстрируем процедуру декодирования в режиме исправления на
следующем примере.
Пример 1.13.
m = (101) использовался расши-
Пусть для передачи сообщения
ренный код Хемминга из примера 1.11 с порождающей матрицей
G
?
1
=? 0
0
0
1
0
0
0
1
c=m·G
1
= (101) ? 0
0
0
1
0
1
0
1
0
1
1
?
1
1 ?.
1
1
0
1
0
1
1
?
1
1 ? = (1011010).
1
c как
Кодер канала формирует кодовое слово
?
1
1
0
0
0
1
1
1
0
e = (0010000).
y = c + e = (1001010).
Пусть в процессе передачи возникла одна ошибка и вектор ошибок
Тогда на вход декодера канала поступает сообщение
Декодер канала вычисляет синдром
?
s? = y · HT
?
?
?
?
?
= (1001010) ?
?
?
?
?
1
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
1
1
1
0
0
0
1
?
?
?
?
?
?
? = (0111).
?
?
?
?
Затем выполняется поиск полученного синдрома в таблице синдромов 1.3:
s
Полученный синдром совпадает с синдромом 2 , который соответствует вектору
e2 = (0010000). Поэтому декодер канала принимает решение, что на стороне
c = y + e2 = (1011010) и исходное
сообщение m = (101).
ошибок
кодера канала было сформировано кодовое слово
Продемонстрируем процедуру декодирования в режиме обнаружения на следующем примере.
Пример 1.14.
Пусть для передачи сообщения
m
= (101) использовался рас-
ширенный код Хемминга из примера 1.11 и было сформировано кодовое слово
c = (1011010) из примера 1.13. Пусть в процессе передачи возникли две ошибки
e = (0010001). Тогда на вход декодера канала поступает сообщение
y = c + e = (1001011).
и вектор ошибок
22
Таблица 1.3.
Синдромное декодирование кодов Хемминга
i
ei
si = ei · HT
0
1000000
1101
1
0100000
1011
2
0010000
0111
3
0001000
1000
4
0000100
0100
5
0000010
0010
6
0000001
0001
Декодер канала вычисляет синдром
?
s? = y · HT
?
?
?
?
?
= (1001011) ?
?
?
?
?
1
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
1
1
1
0
0
0
1
?
?
?
?
?
?
? = (0110).
?
?
?
?
s
Так как синдром ? отличен от нулевого, то декодер канала выносит решение о
том, что в канале произошла ошибка.
Продемонстрируем процедуру декодирования в режиме обнаружения в случае, когда количество ошибок более чем d ? 1 (не выполняется
условие теоремы 1.3) на следующем примере.
Пример 1.15.
Пусть для передачи сообщения
m
= (101) использовался рас-
ширенный код Хемминга из примера 1.11 и было сформировано кодовое слово
c = (1011010) из примера 1.13. Пусть в процессе передачи возникли четыре ошибки
e = (1110001). Тогда на вход декодера канала поступает сообщение
y = c + e = (0101011).
и вектор ошибок
Декодер канала вычисляет синдром
?
s? = y · HT
Так как синдром
?
?
?
?
?
= (0101011) ?
?
?
?
?
1
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
1
1
1
0
0
0
1
?
?
?
?
?
?
? = (0000).
?
?
?
?
s? является нулевым, то декодер канала выносит ошибочное
решение о том, что в канале не было ошибок.
23
1.5.
Порядок выполнения лабораторной работы
В соответствии с вариантом задания:
1) построить проверочную и порождающую матрицы кода Хемминга;
2) сформировать кодовое слово, убедиться, что кодовое слово удовлетворяет (1.13);
3) внести в кодовое слово одну ошибку и выполнить декодирование
в режиме исправления, затем в режиме обнаружения;
4) внести в кодовое слово более одной ошибки и выполнить декодирование в режиме обнаружения.
1.6.
Требования к содержанию отчета
1. Постановка задачи.
2. Описание алгоритмов построения порождающей и проверочной
матрицы кода Хемминга и алгоритма декодирования в соответствии с вариантом задания.
3. Выводы по работе.
24
1.7.
ќ
Варианты заданий
Длина
Длина информацион-
Минимальное
кодо-
ной последовательно-
расстояние,
вого
сти,
Декодирование
d
k
слова,
n
1
7
4
3
По минимуму
расстояния
2
7
4
3
Синдромное
3
7
3
4
По минимуму
расстояния
4
7
3
4
Синдромное
5
15
11
3
По минимуму
расстояния
6
15
11
3
Синдромное
7
15
10
4
По минимуму
расстояния
8
15
10
4
Синдромное
9
31
26
3
Синдромное
10
31
25
4
Синдромное
11
63
57
3
Синдромное
12
63
56
4
Синдромное
25
Лабораторная работа ќ2
ЛИНЕЙНЫЕ ЦИКЛИЧЕСКИЕ
КОДЫ
Целью работы является приобретение практических навыков построения циклических кодов, а также программная реализация алгоритмов обнаружения и исправления ошибок.
2.1.
Предварительные сведения
Пусть имеется конечное поле GF (q). Многочленом a(x) степени n
называется следующее математическое выражение:
a(x) = an · xn + an?1 · xn?1 + ... + a1 · x1 + a0 · x0 ,
(2.1)
в котором коэффициенты a0 , ..., an принадлежат конечному полю
GF (q), q число элементов в этом поле, x формальная переменная.
Пусть a(x) и b(x) многочлены с коэффициентами из поля GF (q).
a(x) = an · xn + ... + a0 · x0 ,
b(x) = bn · xn + ... + b0 · x0 .
Тогда над многочленами определены следующие операции.
1. Операция сложения.
a(x) + b(x) = (an + bn ) · xn + ... + (a0 + b0 ) · x0 .
Пример 2.1.
Пусть заданы два многочлена с коэффициентами из поля
GF (2):
a(x) = x2 + x + 1,
b(x) = x + 1.
Тогда сумма многочленов
a(x) + b(x) вычисляется следующим образом:
a(x) + b(x) = x2 + (1 + 1) ·x + (1 + 1) ·x0 = x2 .
| {z }
| {z }
0
26
0
2. Операция умножения.
a(x)·b(x) = (an ·bn )x2n +...+(an ·b0 )xn +...+(a0 ·bn )xn +...+(a0 ·b0 )x0 .
Пример 2.2.
Пусть заданы два многочлена с коэффициентами из поля
GF (2):
a(x) = x2 + x + 1,
b(x) = x + 1.
Тогда произведение многочленов
a(x)·b(x) вычисляется следующим образом:
a(x) · b(x) = (x2 + x + 1)(x + 1) = x3 + x2 + x + x2 + x + 1 = x3 + 1.
3. Деление многочленов с остатком. Пусть четыре многочлена с коэффициентами из конечного поля связаны следующим образом:
a(x) = b(x) · c(x) + d(x).
Тогда многочлен d(x) называется остатком от деления многочлена a(x) на многочлен b(x) и обозначается через a(x) mod b(x).
Для вычисления остатка от деления используется так называемое
деление ѕв столбикї, в котором используются операции умножения и сложения многочленов.
Пример 2.3.
Пусть заданы два многочлена с коэффициентами из поля
GF (2):
a(x) = x3 + x + 1,
b(x) = x + 1.
Тогда остаток от деления
a(x) на b(x) вычисляется следующим образом:
x3 +x +1 x + 1
x3 +x2
x2 + x
2
x +x +1
x2 +x
1
Таким образом,
a(x) mod b(x) = 1.
27
2.2.
2.2.1.
Циклические линейные коды
Определение и свойства циклических кодов
Пусть y = (y0 , y1 , ..., yn ) является вектором линейного пространства
Y. Этому вектору можно поставить в соответствие многочлен y(x) от
формальной переменной x следующим образом:
y(x) = y0 + y1 · x + ... + yn?1 · xn?1 .
(2.2)
Такое сопоставление взаимно однозначно, так как каждому вектору соответствует единственный многочлен и каждому многочлену соответствует единственный вектор. Линейной комбинации y = m1 · a + m2 · b
пары векторов a = (a0 , a1 , ..., an?1 ) ? Y и b = (b0 , b1 , ..., bn?1 ) ? Y соответствует линейная комбинация многочленов
y(x) =
n?1
X
(m1 · ai + m2 · bi ) · xi = m1 · a(x) + m2 · b(x).
(2.3)
i=0
Если c = (c0 , c1 , ..., cn?1 ) кодовое слово линейного кода C, то соответствующий многочлен c(x) также будем называть кодовым словом.
Линейным циклическим кодом называется такой линейный код, для
которого циклический сдвиг любого кодового слова на любое количество разрядов влево или вправо также является кодовым словом. Это
означает, что если кодовое слово c = (c0 , c1 , ..., cn?1 ) принадлежит линейному циклическому коду C, то и слова c1 = (c1 , c2 , ..., cn?1 , c0 ) и
c2 = (cn?1 , c0 , c1 , ..., cn?2 ) также принадлежат коду C. В дальнейшем
для краткости линейные циклические коды будем называть циклическими.
Пример 2.4.
Рассмотрим два линейных кода
C1
?
?
000 ?
?
?
?
?
?
110
=
,
?
?
011
?
?
?
?
101
C2
C1 и C2 :
?
?
0000000 ?
?
?
?
?
?
?
0010111 ?
?
?
?
?
?
?
?
?
?
0101011 ?
?
?
?
?
?
?
0111100
=
.
?
?
1001101
?
?
?
?
?
?
? 1011010 ?
?
?
?
?
?
?
?
? 1100110 ?
?
?
?
?
?
1110001
28
Код
C1 является циклическим, так как при циклическом сдвиге любого слова
на произвольное количество разрядов влево или вправо получается кодовое слово.
Код
C2 не является циклическим, так как при циклическом сдвиге могут получиться
слова не принадлежащие коду.
Пусть вектору c длины n в поле GF (2) соответствует многочлен
c(x). Тогда многочлен c0 (x) = c(x) · xL mod (xn + 1) соответствует циклическому сдвигу вектора c на L разрядов влево.
c = (1100000) в поле GF (2) и необходимо
с0 , который является сдвигом вектора c на один разряд влево,
то есть L = 1. Вектору c соответствует многочлен c(x) = x6 + x5 . Тогда c0 (x) =
(x7 + x6 ) mod (x7 + 1) = x6 + 1. Значит вектор с0 = (1000001).
Пример 2.5.
Пусть имеется вектор
вычислить вектор
Для циклических кодов справедлива следующая теорема [1].
s
Теорема 2.1. Пусть m(x) = m0 + m1 · x + ... + ms · x произвольный
многочлен с коэффициентами из поля GF (q) и c(x) = c0 + c1 · x + ... +
cn?1 · xn?1 кодовое слово циклического кода С. Тогда c0 (x) = m(x) ·
c(x) mod (xn ? 1) также является словом из кода С.
Порождающим многочленом циклического кода C с кодовыми словами длины n и информационной последовательностью длины k называется такой ненулевой многочлен
g(x) =
r
X
gi · xi
(2.4)
i=0
из кода C, который имеет минимальную степень и коэффициент gr = 1.
Для порождающего многочлена циклического кода справедливы
следующие теоремы [1].
Теорема 2.2. Пусть C циклический код с кодовыми словами длины n и информационной последовательностью длины k и g(x) его
порождающий многочлен. Тогда степень g(x) равна r = n ? k и каждое
кодовое слово из C может быть единственным образом представлено в
виде
c(x) = m(x) · g(x),
(2.5)
где m(x) имеет степень меньшую или равную k ? 1.
Теорема 2.3. Пусть g(x) порождающий многочлен циклического
кода с кодовыми словами длины n и информационной последовательностью длины k . Тогда (xn ? 1) mod g(x) = 0.
29
2.2.2.
Кодирование циклическими кодами
Пусть для информационного многочлена m(x) (многочлена, соответствующего информационной последовательности m) необходимо
сформировать кодовое слово c(x), принадлежащее циклическому коду
с поро??дающим многочленом g(x). Cогласно теореме 2.2, кодовое слово
вычисляется как
c(x) = m(x) · g(x).
(2.6)
Такой способ формирования кодового слова называется несистематическим.
При несистематическом кодировании в кодовом слове нельзя выделить подслово, содержащее исходную информационную последовательность в явном виде. Для ее получения, согласно (2.6), необходимо
выполнить деление c(x) на g(x).
Поэтому на практике чаще всего используется систематическое кодирование при котором кодовое слово c формируется из двух подслов
c = (m|a), где m информационная последовательность, a проверочные разряды. То есть, первое подслово кодового слова в явном виде
содержит информационную последовательность.
При систематическом кодировании кодовое слово c(x) вычисляется
как
c(x) = m(x) · xr + a(x).
(2.7)
Из условия того, что c(x) mod g(x) = 0 следует, что многочлен a(x)
вычисляется как
a(x) = ?xr · m(x) mod g(x).
(2.8)
Для случая циклических кодов в поле GF (2), выражение (2.8) принимает вид
a(x) = xr · m(x) mod g(x).
(2.9)
Таким образом, алгоритм построения кодового слова при систематическом кодировании состоит из двух основных шагов.
30
Алгоритм 2.1. Построение кодового слова
систематического циклического кода над полем GF (2)
Входные данные.
Длина кодового слова n.
Порождающий многочлен g(x).
Информационная последовательность m длины k .
Шаг 1.
r := n ? k .
В соответствии с (2.2) по m сформировать m(x).
a(x) := xr · m(x) mod g(x).
c(x) := m(x) · xr + a(x).
Шаг 2.
В соответствии с (2.2) по c(x) сформировать кодовое слово c.
Проиллюстрируем построение кодового слова систематического
циклического кода на следующем примере.
g(x) = x3 + x + 1,
длина кодового слова n = 7, длина информационной последовательности k = 4.
Необходимо сформировать кодовое слово для сообщения
= (1001). Информационной последовательности
соответствует многочлен m(x) = x3 + 1. Произведение
x3 · m(x) = x6 + x3 . Многочлен a(x) = xr · m(x) mod g(x) вычисляется следующим
Пример 2.6.
Порождающий многочлен циклического кода
m
c
m
образом:
x6 +x3
x3 + x + 1
x6 +x4 +x3
x3 + x
x4
x4 +x2 +x
x2 +x
a(x) = x2 + x, c(x) = m(x) · xr + a(x) = x6 + x3 + x2 + x.
c(x) соответствует кодовому слову = (1001110).
В результате деления
С учетом (2.2)
2.2.3.
c
Декодирование циклических кодов
По определению циклические коды являются линейными. Поэтому при их декодировании могут быть использованы подходы, которые
применяются для декодирования линейных кодов, в том числе и синдромное декодирование.
Пусть c(x) кодовое слово циклического кода с порождающим многочленом g(x) и e(x) многочлен, соответствующий вектору ошибок e в
канале связи. Тогда на вход декодера канала поступает последователь-
31
ность y, которой соответствует многочлен
(2.10)
y(x) = c(x) + e(x).
Из теоремы 2.2 следует, что c(x) mod g(x) = 0. Поэтому, если
y(x) mod g(x) 6= 0,
(2.11)
то в режиме обнаружения декодер канала сообщает системе о том, что
в пришедшем сообщении обнаружены ошибки.
В режиме исправления ошибок декодер канала вычисляет синдром
S(x) следующим образом:
S(x) = y(x) mod g(x).
(2.12)
С учетом того, что c(x) mod g(x) = 0 синдром
S(x) = y(x) mod g(x) = (c(x) + e(x)) mod g(x) = e(x) mod g(x). (2.13)
Из (2.13) следует, что синдром S(x) зависит только от значения вектора ошибок. При этом выполняется теорема, аналогичная теореме 1.5,
согласно которой синдромы различных ошибок, вес которых не превышает (d ? 1)/2, различны, где d минимальное расстояние кода.
Таким образом, алгоритм синдромного декодирования, за исключением правила вычисления синдрома, полностью аналогичен алгоритму
синдромного декодирования кодов Хемминга (см. алгоритм 1.3). Процедуру декодирования продемонстрируем на следующем примере.
Пример 2.7.
Пусть для сообщения
m = (1001) использовался циклический код
с порождающим многочленом из примера 2.6, который сформировал кодовое слово
c
= (1001110). Пусть в процессе передачи возникла одна ошибка на шестой
позиции, то есть многочлен, соответствующий вектору ошибок равен
e(x) = x6 .
Тогда многочлен, соответствующий последовательности на входе декодера канала
y(x) = c(x) + e(x) = x3 + x2 + x. Декодер канала вычисляет синдром S(x) =
y(x) mod g(x) = x2 + 1. Затем выполняется поиск полученного синдрома в таблице синдромов (табл. 2.1). Полученный синдром совпадает с синдромом
который соответствует многочлену ошибок
S6 (x),
e6 (x) = x6 . Поэтому декодер канала
принимает решение, что на стороне кодера канала был сформирован многочлен
c(x) = x6 + x3 + x2 + x, соответствующий кодовому слову
ное сообщение
m = (1001).
32
c = (1001110) и исход-
Таблица 2.1.
Синдромное декодирование циклических кодов
i
ei (x)
Si (x) = ei (x) mod g(x)
0
1
1
1
x
x
2
x2
x2
3
x3
x+1
4
x4
x2 + x
5
x5
x2 + x + 1
6
x6
x2 + 1
Следует отметить, что для циклических кодов синдром S(x) может
быть определен как
S(x) = xr · y(x) mod g(x),
(2.14)
что позволяет перейти к более простым схемам декодирования [1, 2].
2.3.
Порядок выполнения лабораторной работы
В соответствии с вариантом задания:
1) сформировать кодовое слово, убедиться, что c(x) mod g(x) = 0;
2) внести в кодовое слово одну ошибку и выполнить синдромное
декодирование в режиме исправления, затем в режиме обнаружения;
3) внести в кодовое слово более одной ошибки и выполнить декодирование в режиме обнаружения.
2.4.
Требования к содержанию отчета
1. Постановка задачи.
2. Описание алгоритмов построения кодового слова и синдромного
декодирования.
3. Выводы по работе.
33
2.5.
ќ
Длина
Длина
кодо-
ционной
вого
слова,
информапосле-
довательности,
n
Варианты заданий
Минимальное
Порождающий полином,
g(x)
расстояние,
d
k
1
7
4
3
x3 + x + 1
2
7
4
3
x3 + x2 + 1
3
15
11
3
x4 + x + 1
4
15
11
3
x4 + x3 + 1
5
31
26
3
x5 + x2 + 1
6
31
26
3
x5 + x3 + 1
7
31
26
3
x5 + x3 + x2 + x + 1
8
63
57
3
x6 + x + 1
9
63
57
3
x6 + x5 + x3 + x + 1
10
63
57
3
x6 + x5 + 1
11
7
3
4
(x + 1)(x3 + x + 1)
12
7
3
4
(x + 1)(x3 + x2 + 1)
13
15
10
4
(x + 1)(x4 + x + 1)
14
15
10
4
(x + 1)(x4 + x3 + 1)
15
31
25
4
(x + 1)(x5 + x2 + 1)
16
31
25
4
(x + 1)(x5 + x3 + 1)
17
31
25
4
(x + 1)(x5 + x3 + x2 + x + 1)
18
63
56
4
(x + 1)(x6 + x + 1)
19
63
56
4
(x + 1)(x6 + x5 + x3 + x + 1)
20
63
56
4
(x + 1)(x6 + x5 + 1)
34
Библиографический список
1.
2.
Кодирование и декодирование сообщений: учебное
пособие. СПбГУАП. СПб., 2008.
Колесник В.Д.
Евсеев Г.С., Тюрликов А.М. Кодирование при хранении и передаче
информации: методические указания к выполнению лабораторных
работ / ГААП. СПб., 1993.
35
?лементов и
GF (5) = {0, 1, 2, 3, 4}. Нейтральный
элемент по сложению x0 = 0, нейтральный элемент по умножению x1 = 1. В табл. 1.1
Пример 1.1.
Рассмотрим поле
включает в себя все вычеты по модулю 5, то есть
показаны таблицы сложения и умножения элементов поля.
Таблица 1.1.
Cложение (слева) и умножение (справа) в поле GF (5)
0
1
2
3
4
0
1
2
3
4
0
0
1
2
3
4
0
0
0
0
0
0
1
1
2
3
4
0
1
0
1
2
3
4
2
2
3
4
0
1
2
0
2
4
1
3
3
3
4
0
1
2
3
0
3
1
4
2
4
4
0
1
2
3
4
0
4
3
2
1
Как видно из табл. 1.1, для каждого элемента поля существует обратный элемент по сложению (например, для элемента 4 обратный элемент 2, так как
(4 + 2)
mod 5 = 1) и по умножению (например, для элемента 4 обратный элемент 4, так как
(4 · 4) mod 5 = 1).
1.2.2.
Линейные пространства над конечным полем
Пусть X конечное поле и x = (x1 , x2 , ..., xn ) ? X n вектор, каждая
компонента которого является элементом этого конечного поля. Тогда
n
и y ? X n определяется как
сумма векторов x ? X
x + y = (x1 + y1 , x2 + y2 , ..., xn + yn ).
(1.1)
Если c ? X , то умножение вектора x на скаляр c определяется как
c · x = (c · x1 , c · x2 , ..., c · xn ).
Пример 1.2.
Пусть даны два вектора
x = (1, 2, 3, 4) и y = (4, 2, 3, 1), каждая комGF (5). Тогда x + y = (0, 4, 1, 0).
понента которых является элементом конечного поля
Пусть
c = 2, тогда c ·
x = (2, 4, 1, 3).
(1.2)
6
Произвольное множество векторов V образует линейное простран, если это множество является замкнутым по отношению к операциям сложения и умножения на скаляр. Это означает, что для любого
k = {1, 2, 3, ...} вектор
k
X
z=
ci · xi
(1.3)
ство
i=1
принадлежит множеству V при любых ci ? X и xi ? X n . Правую часть выражения (1.3) называют линейной комбинацией векторов
x1 , x2 , ..., xk .
Пример 1.3.
Рассмотрим два множества векторов
V1 и V2 над полем GF (2) =
{0, 1}.
V1
?
?
000 ?
?
?
?
?
?
110
=
,
? 011 ?
?
?
?
?
101
V2
?
?
000 ?
?
?
?
?
?
100
=
.
? 010 ?
?
?
?
?
001
V1 является линейным пространством, так как сумма произвольных
V1 принадлежит множеству V1 . Множество V2 не является линейным
пространством. Например, результатом суммы векторов (100) + (010) является вектор (110), который не входит во множество V2 .
Множество
векторов из
Подмножество линейного пространства, для которого выполняются все свойства линейного пространства, называется линейным подпространством.
Пример 1.4.
Рассмотрим два множества векторов
V1 и V2 над полем GF (2) =
{0, 1}.
V1
Множество
?
?
000 ?
?
?
?
?
?
?
?
?
001 ?
?
?
?
?
?
?
?
?
? 010 ?
,
=
100
?
?
?
?
?
?
101
?
?
?
?
?
?
?
?
?
?
? 110 ?
?
?
111
V2
?
?
000 ?
?
?
?
?
?
110
=
.
?
? 011 ?
?
?
?
101
V2 является линейным подпространством линейного пространства V1 .
Векторы x1 , x2 , ..., xk называются линейно независимыми, если равенство
c1 · x1 + c2 · x2 + ... + ck · xk = 0,
(1.4)
где 0 нулевой вектор, справедливо только в том случае, если
c1 = c2 = ... = ck = 0.
Пример 1.5.
Векторы
зависимыми, поскольку
(1.5)
(0, 1, 1, 1) и (0, 2, 2, 2) в поле GF (5) являются линейно
2 · (0, 1, 1, 1) = (0, 2, 2, 2).
7
В каждом линейном пространстве существуют такие линейно независимые векторы x1 , x2 , ..., xk , что любой вектор линейного пространства
xi = c1 · x1 + c2 · x2 + ck · xk .
(1.6)
Такие векторы называются базисными
ства.
Пример 1.6.
векторами
Рассмотрим два множества векторов
{0, 1}.
V1
?
?
000 ?
?
?
?
?
?
?
?
?
001 ?
?
?
?
?
?
?
?
?
010
?
?
=
,
100
?
?
?
? 101 ?
?
?
?
?
?
?
?
?
? 110 ?
?
?
?
?
?
111
Векторы, входящие во множество
ного пространства
V1 .
V2
линейного простран-
V1 и V2 над полем GF (2) =
?
?
? 100 ?
=
.
010
?
?
001
V2 , являются базисными векторами для линей-
Пусть множество векторов G = {g1 , g2 , ..., gk } являются базисом
линейного подпространства V. Выберем два произвольных базисных
вектора gi ? G и gj ? G и образуем вектор g0i как линейную комбинацию следующего вида:
g0i = c1 · gi + c2 · gj ,
(1.7)
где c1 6= 0, c2 6= 0. Заменим во множестве G вектор gi на вектор g0i .
Можно показать, что полученное в результате множество векторов
G0 = {g1 , g2 , ..., gi?1 , g0i , gi+1 , ..., gk } также является базисом линейного подпространства V.
Пример 1.7.
V1 и V2 из примера 1.6. Во
V2 заменим первый вектор на сумму первого и вто-
Рассмотрим два множества векторов
множестве базисных векторов
рого. В результате получится множество векторов
V
0
2
?
?
? 110 ?
=
,
010
?
?
001
которые также являются базисными векторами для линейного пространства
V1 .
Из этого примера следует, что одному линейному подпространству
может соответствовать несколько множеств базисных векторов.
8
Пусть X конечное поле и x ? X n , y ? X n векторы, каждая
компонента которых является элементом этого конечного поля. Тогда
скалярное произведение векторов x и y определяется следующим образом:
n
X
x·y=
xi · yi ? X.
(1.8)
i=1
Векторы x и y называются ортогональными, если x · y = 0.
Пусть Vk ? X n линейное пространство размерности k (то есть
содержит q k векторов и любые k линейно независимых векторов образуют базис линейного пространства) и W ? X n множество векторов,
ортогональных к Vk , то есть любое скалярное произведение векторов
x · y = 0 для любой пары векторов x ? Vk и y ? W. Множество
W называется ортогональным дополнением пространства Vk . Можно
доказать [1], что ортогональное дополнение W является линейным подпространством пространства Vk и имеет размерность n ? k .
1.2.3.
Порождающая матрица линейного пространства
Пусть векторы g1 = (g11 , ..., g1n ), g2 = (g21 , ..., g2n ), ..., gk =
(gk1 , ..., gkn ) образуют базис линейного пространства Vk . Тогда любой
вектор x в линейном пространстве Vk может быть получен как линейная комбинация базисных векторов:
x = m1 · g1 + m2 · g2 + ... + mk · gk .
(1.9)
Выражение (1.9) может быть записано в матричном виде как
g11
? g21
x = (m1 , m2 , ..., mk ) · ?
? .
gk1
?
g12
g22
.
gk2
?
. g1n
. g2n ?
? = m · G,
.
. ?
. gkn
(1.10)
где m = (m1 , m2 , ..., mk ) и k Чn матрица G имеет в качестве своих строк
базисные векторы линейного пространства Vk . Матрица G называется
порождающей матрицей линейного пространства Vk . Перебирая все
возможные комбинации вектора m = (m1 , m2 , ..., mk ) путем произведения m · G можно получить все векторы линейного пространства Vk .
9
1.2.4.
Проверочная матрица линейного пространства
Линейное пространство также может быть задано при помощи ортогонального дополнения. Пусть Vk ? X n линейное пространство
размерности k и Wr ? X n ортогональное дополнение для Vk . Размерность Wr равна r = n ? k . Следовательно, в Wr имеется r базисных
векторов. Обозначим эти базисные векторы через h1 = (h11 , ..., h1n ),
h2 = (h21 , ..., h2n ), ..., hr = (hr1 , ..., hrn ). Обозначим через H матрицу,
строками которой являются векторы h1 , h2 , ..., hr :
h11
? h21
H=?
? .
hr1
?
h12
h22
.
hr2
.
.
.
.
?
h1n
h2n ?
?.
. ?
hrn
(1.11)
Произвольный вектор x = (x1 , ..., xn ) ? Vk удовлетворяет следующей системе линейных уравнений:
?
h11 · x1 + ... + h1n · xn = 0,
?
?
?
h21 · x1 + ... + h2n · xn = 0,
? ......
?
?
hr1 · x1 + ... + hrn · xn = 0,
(1.12)
или в матричной записи
x · HT = 0.
(1.13)
Систему уравнений (1.13) следует рассматривать как проверку принадлежности вектора x линейному пространству Vk . Поэтому H называется проверочной матрицей линейного пространства Vk .
Из (1.10) и (1.13) следует, что
m · G · HT = 0.
(1.14)
Так как равенство (1.14) выполняется для всех векторов m, то любая пара порождающих и проверочных матриц линейного пространства
связаны следующим образом:
G · HT = 0.
10
(1.15)
1.3.
1.3.1.
Линейные коды
Формирование кодового слова линейного кода по
информационной последовательности
q -ичным кодом длины n c k информационными символами, или (n, k)-кодом над полем GF (q), называется k -мерное подпространство линейного n-мерного пространства всех векторов над полем
GF (q).
Все свойства линейного пространства переносятся и на линейные
коды. Как и линейное пространство, линейный (n, k)-код задается базисными векторами g1 = (g11 , ..., g1n ), g2 = (g21 , ..., g2n ), ..., gk =
(gk1 , ..., gkn ), gij ? GF (q) или порождающей матрицей
Линейным
g11
? g21
G=?
? .
gk1
?
g12
g22
.
gk2
?
. g1n
. g2n ?
?,
.
. ?
. gkn
(1.16)
при этом кодовое слово c = (c1 , c2 , ..., cn ) является линейной комбинацией базисных векторов:
c = m1 · g1 + ... + mk · gk = m · G,
(1.17)
где m = (m1 , m2 , ..., mk ) информационная последовательность. Соотношение (1.17) представляет собой правило кодирования, по которому
информационная последовательность m = (m1 , m2 , ..., mk ) отображается в кодовое слово c = (c1 , c2 , ..., ck ).
Если порождающую матрицу G можно представить как
G = [Ik |G2 ],
(1.18)
где Ik единичная матрица размером k Ч k , то говорят, что порождающая матрица имеет левую каноническую форму.
Если порождающая матрица имеет каноническую форму, то линейный код называется систематическим. Для систематического кода кодовое слово представляется как
с = m · G = m · [Ik |G2 ] = (m, m · G2 ),
11
(1.19)
то есть кодовое слово состоит из двух подслов. Левое подслово является
информационной последовательностью m = (m1 , m2 , ..., mk ) длиной k ,
правое подслово состоит из r = n ? k проверочных символов.
Пример 1.8.
дового слова
Пусть порождающая матрица для линейного кода с длиной ко-
n = 7 и информационной последовательности длины k = 4 имеет
следующий вид:
?
G
1
? 0
=?
? 0
0
0
1
0
0
0
0
1
0
0
0
0
1
Необходимо сформировать кодовое слово
сти
m
0
1
1
1
?
1
1 ?
?.
0 ?
1
1
0
1
1
c для информационной последовательно-
= (0101). В соответствии с (1.19) кодовое слово формируется как
?
с=m·G
1.3.2.
1
? 0
?
= (0101) ?
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
1
1
?
1
1 ?
? = (0101010).
0 ?
1
Минимальное расстояние линейного кода
Пусть x и y два слова из X n . Расстоянием Хемминга d(x, y)
между x и y называется число позиций, в которых эти два слова различаются.
Пример 1.9.
Пусть
x = (0, 2, 1, 1) и y = (0, 1, 1, 2), тогда d(x, y) = 2.
Пусть С = (c1 , ..., cM ) код длины n над алфавитом X . Минимальным расстоянием кода C называется наименьшее из попарных расстояний Хемминга между различными кодовыми словами из C. Минимальное расстояние обозначается через d и вычисляется как
d=
min
x ,x ?C,i6=j
i
d(xi , xj ).
(1.20)
j
Для определения минимального расстояния линейного кода можно
воспользоваться следующими теоремами [1].
Теорема 1.1. Минимальное расстояние линейного кода C равно минимальному из весов ненулевых кодовых слов:
d=
min w(c).
c?C,c6=0
(1.21)
Теорема 1.2. Если любые l ? d?1 столбцов проверочной матрицы H
линейного кода линейно независимы, то минимальное расстояние кода
будет по меньшей мере d. Если при этом найдутся d линейно зависимых
столбцов, то минимальное расстояние кода равно d.
12
Говорят, что код обнаруживает ошибки кратности f , если найдется
алгоритм, позволяющий определить наличие искажений в любом принятом слове при условии, что число ошибочных символов в слове не
превосходит f . Говорят, что код исправляет ошибки кратности t, если найдется алгоритм, позволяющий указать положение ошибок и их
величины при условии, что число ошибочных символов в слове не превосходит t.
Следующие теоремы [1] связывают минимальное расстояние кода d
со способностью обнаруживать или исправлять ошибки.
Теорема 1.3. Код с минимальным расстоянием d обнаруживает любые ошибки кратности f ? d ? 1.
Теорема 1.4. Код с минимальным расстоянием d исправляет любые
ошибки кратности t = (d ? 1)/2.
1.4.
1.4.1.
Коды Хемминга
Построение проверочной и порождающей матрицы
Коды Хемминга относятся к линейным кодам, которые обеспечивают минимально возможное количество проверочных символов для минимального кодового расстояния d = 3. Рассмотрим метод построения
проверочной и порождающей матрицы систематического кода Хемминга над полем GF (2).
Пусть порождающая матрица кода G записывается в левой канонической форме:
G = [Ik |G2 ],
(1.22)
где Ik единичная подматрица размером k Ч k и G2 подматрица
размером r Ч k .
Проверочную матрицу кода H запишем как
H = [H1 |H2 ],
(1.23)
где H1 подматрица размером r Ч k , H2 подматрица размером r Ч r.
Из (1.15) следует, что
0 = G · HT = [Ik |G2 ]
HT
1
HT
2
13
= HT1 + G2 · HT2 .
(1.24)
Пусть проверочная матрица H представлена в правой канонической
форме, то есть HT2 является единичной подматрицей. Тогда,
T
T
0 = HT
1 + G2 · H2 = H1 + G2 .
(1.25)
С учетом того, что код строится над полем GF (2), из (1.25) получим
G2 = HT
1.
(1.26)
Из теоремы 1.2 следует, что для построения линейного кода с минимальным расстоянием d = 3 любые два столбца проверочной матрицы H должны быть линейно независимы. В случае кода над полем
GF (2) это означает, что любые два столбца матрицы H должны быть
различны и матрица H не должна содержать нулевого столбца. Легко
показать, что это справедливо в том случае, когда n = k + r ? 2r ? 1 [2].
При этом, для удобства построения, матрица H должна быть записана в
правой канонической форме, то есть содержать единичную подматрицу
в правой части.
Таким образом, алгоритм построения проверочной и порождающей
матрицы состоит из трех основных шагов.
Алгоритм 1.1. Построение проверочной и порождающей
матрицы кода Хемминга над полем GF (2)
Входные данные.
Длина кодового слова n.
Длина информационной последовательности k .
Шаг 1.
r := n ? k .
Сформировать H1 размером r Ч k из k различных столбцов,
каждый из которых содержит более одной единицы.
Шаг 2.
Сформировать H2 как единичную матрицу r Ч r.
H := [H1 |H2 ].
Шаг 3.
Сформировать G1 как единичную матрицу k Ч k .
G := [G1 |HT
1 ].
14
Проиллюстрируем построение проверочной и порождающей матрицы кода Хемминга на следующем примере.
Пример 1.10.
Требуется построить проверочную и порождающую матрицу кода
Хемминга с длиной кодового слова
длины
n = 7 и информационной последовательностью
k = 4. В соответствии с шагом 1 алгоритма формируется подматрица
H1
?
0
=? 1
1
1
0
1
1
1
0
?
1
1 ?,
1
затем в соответствии с шагом 2 формируется единичная матрица
и формируется проверочная матрица в виде:
?
0
= [ 1| 2] = ? 1
1
H H H
1
0
1
1
1
0
1
1
1
1
0
0
0
1
0
?
0
0 ?
1
В соответствии с шагом 3 формируется единичная подматрица
и порождающая матрица в виде:
?
1
? 0
T
?
= [ 1| 1 ] = ?
0
0
G G H
1.4.2.
0
1
0
0
0
0
1
0
0
0
0
1
0
1
1
1
1
0
1
1
H2 размером 3 Ч 3,
G1 размером 4 Ч 4
?
1
1 ?
?.
0 ?
1
Расширенные коды Хемминга
Расширенные коды Хемминга относятся к линейным кодам, которые обеспечивают минимально возможное количество проверочных
символов для минимального кодового расстояния d = 4. Увеличение
минимального расстояние кода достигается путем замены одного информационного символа исходного кода Хемминга на проверочный символ. Поэтому проверочная матрица такого кода должна иметь на одну
строку больше, чем в коде Хемминга.
В соответствии с теоремой 1.2 в проверочной матрице расширенного
кода Хемминга любые три столбца должны быть линейно независимые.
В случае кода над полем GF (2) это означает, что любые два столбца
матрицы H должны быть различны, матрица H не должна содержать
нулевого столбца и любые два столбца в сумме не должны давать третий.
15
Обозначим через H3 проверочную матрицу
мальным расстоянием d = 3. Тогда матрица
?
1 1 1 ... 1
?
?
H4 = ?
?
H3
кода Хемминга с мини-
?
?
?
?
?
(1.27)
удовлетворяет приведенным выше требованиям для кода с минимальным расстоянием d = 4. Во-первых, матрица H4 не содержит двух одинаковых столбцов и не содержит нулевой столбец, поскольку в матрице
H3 нет нулевых столбцов и все столбцы разные. Во-вторых, сумма по
модулю 2 любых двух столбцов не равна никакому третьему столбцу,
так как сумма двух столбцов будет содержать 0 в первом разряде, тогда
как все столбцы в H4 в первом разряде равны 1.
Для формирования порождающей матрицы расширенного кода
Хемминга проверочную матрицу H4 необходимо представить в правой
канонической форме. Так как строки матрицы H4 являют базисным
векторами линейного пространства, то каждый базисный вектор можно заменить другим базисным вектором, который является линейного
комбинацией исходных базисных векторов. В случае кодов над полем
GF (2) можно менять любую строку матрицы H4 на сумму двух или
более строк по модулю 2 до тех пор, пока матрица H4 не примет правую каноническую форму. Затем, аналогично коду Хемминга можно
построить порождающую матрицу.
Таким образом, алгоритм построения проверочной и порождающей
матрицы состоит из четырех основных шагов.
16
Алгоритм 1.2. Построение проверочной и порождающей
матрицы расширенного кода Хемминга над полем GF (2)
Входные данные.
Длина кодового слова n.
Длина информационной последовательности k .
Шаг 1.
r := n ? k .
Сформировать H31 размером (r ? 1) Ч k из k различных
столбцов, каждый из которых содержит более одной единицы
и последний столбец H31 содержит четное число единиц.
Шаг 2.
Сформировать H32 как единичную матрицу (r ? 1) Ч (r ? 1).
H3 := [H31 |H32 ].
Шаг 3. "
#
11 ... 1
4
H :=
.
3
H
Сложить все строки H4 и поместить результат в первую строку.
Привести H4 в правую каноническую форму путем сложения
первой строки с остальными строками.
Шаг 4.
Сформировать G41 как единичную матрицу k Ч k .
G4 := [G1 |(H41 )T ].
Проиллюстрируем построение проверочной и порождающей матрицы расширенного кода Хемминга на следующем примере.
Пример 1.11.
Требуется построить проверочную и порождающую матрицу рас-
ширенного кода Хемминга с длиной кодового слова
следовательностью длины
n = 7 и информационной поk = 3. В соответствии с шагом 1 алгоритма формируется
подматрица
H
?
3
1
0
=? 1
1
1
0
1
1
1
1
?
1
1 ?,
0
затем в соответствии с шагом 2 формируется единичная матрица
и формируется проверочная матрица в виде
H3
?
0
= [ 31 | 32 ] = ? 1
1
H H
1
0
1
17
1
1
1
1
1
0
1
0
0
0
1
0
?
0
0 ?.
1
H32 размером 3 Ч 3,
В соответствии с шагом 3 формируется проверочная матрица расширенного
кода как
?
H4
Затем сумма всех строк
1
? 0
=?
? 1
1
1
1
0
1
1
1
1
1
1
1
1
0
1
1
0
0
?
1
0 ?
?.
0 ?
1
1
0
1
0
H4 по модулю 2 записывается в первую строку:
?
H4
1
? 0
=?
? 1
1
1
1
0
1
0
1
1
1
1
1
1
0
0
1
0
0
?
0
0 ?
?.
0 ?
1
0
0
1
0
Для формирования правой канонической формы первая строка матрицы
H4 склады-
вается со второй, результат сложения записывается во вторую строку. Затем первая
строка складывается с третьей, результат сложения записывается в третью строку.
В итоге матрица
H4 представляется как
?
H4
1
? 1
4
4
?
= [ 1| 2] = ?
0
1
H H
1
0
1
1
0
1
1
1
1
0
0
0
0
1
0
0
0
0
1
0
?
0
0 ?
?.
0 ?
1
В соответствии с шагом 4 формируется единичная подматрица
3 Ч 3 и порождающая матрица в виде
G = [G H
4
1 |(
1.4.3.
?
4 T
1) ]
1
=? 0
0
0
1
0
0
0
1
1
1
0
1
0
1
0
1
1
G41 размером
?
1
1 ?.
1
Декодирование по минимуму расстояния
Пусть требуется передать по цифровому каналу связи сообщение
m длиной k информационных символов при помощи кода Хемминга. В
соответствии с моделью системы передачи информации (см. рис. 1.2)
кодер канала формирует кодовое слово c = m · G длиной n символов,
где G порождающая матрица кода. В канале связи могут возникнуть
ошибки, в результате которых на вход декодера канала поступает сообщение
y = c + e,
(1.28)
где e вектор ошибок длины n. Если ошибок не было, то e = 0.
18
Операция декодирования линейного кода выполняется на стороне
декодера канала, который либо исправляет возникшие в пришедшем
сообщении ошибки, либо сигнализирует системе о том, что в пришедшем
сообщении обнаружены ошибки.
При декодировании по минимуму расстояния декодер канала хранит в памяти весь список кодовых слов ci ? C.
В режиме обнаружения ошибок по минимуму расстояния декодер
сравнивает поступившее сообщение y со списком кодовых слов. Если y
не совпадает ни с одним кодовым словом из C, то выносится решение,
что в пришедшем сообщении обнаружены ошибки.
В режиме исправления ошибок по минимуму расстояния декодер
попарно вычисляет расстояние Хемминга d(y, ci ) между пришедшим
сообщением y и всеми кодовыми словами из C. Затем из списка кодовых слов выбирается слово, которому соответствует меньшее значение
расстояния Хемминга. Другими словами, выбирается кодовое слово с
номером
j = arg min d(y, ci ).
(1.29)
i
Если в списке содержится несколько кодовых слов, которым соответствует наименьшее значение расстояния Хемминга, то выбирается любое из них. Из найденного слова cj извлекается сообщение m0 , которое
является выходом декодера канала. Причем, согласно теореме 1.4, равенство m0 = m гарантируется только тогда, когда количество возникших в канале связи ошибок t ? (d?1)/2, где d минимальное расстояние
кода.
Пример 1.12.
Пусть для передачи сообщения
m = (101) использовался расши-
ренный код Хемминга из примера 1.11 с порождающей матрицей
G
?
1
=? 0
0
0
1
0
0
0
1
Кодер канала формирует кодовое слово
c=m·G
?
1
= (101) ? 0
0
0
1
0
1
1
0
1
0
1
0
1
1
?
1
1 ?.
1
1
0
1
0
1
1
?
1
1 ? = (1011010).
1
c как
0
0
1
1
1
0
e = (0010000).
y = c + e = (1001010). Декодер
канала попарно вычисляет расстояние d(y, ci ) между пришедшим сообщением y с
каждым кодовым словом из C как показано в табл. 1.2:
Пусть в процессе передачи возникла одна ошибка и вектор ошибок
Тогда на входе декодера канала поступает сообщение
19
Таблица 1.2.
Декодирование кодов Хемминга по минимуму расстояния
i
mi ci = mi · G
0
000
0000000
2
1
001
0010111
4
2
010
0101011
4
3
011
0111100
6
4
100
1001101
6
5
101
1011010
1
6
110
1100110
3
7
111
1110001
5
Так как минимальное расстояние
y ci )
d( ,
y c5 ) = 1 соответствует кодовому слову c5 ,
d( ,
то декодер канала принимает решение о том, что на стороне кодера канала было
сформировано кодовое слово
1.4.4.
c = (1011010) и исходное сообщение m = (101).
Синдромное декодирование
Недостатком декодирования по минимуму расстояния является то,
что с увеличением длины кодового слова экспоненциально увеличивается количество кодовых слов, которые необходимо хранить в памяти
декодера. Поэтому, на практике такой способ декодирования применяется для кодовых слов малой длины.
Если кодовые слова имеют большую длину эффективнее использовать синдромное декодирование. Из свойств проверочной матрицы линейного кода (1.13) следует, что c · HT = 0. Поэтому величина
s = y · HT = (c+e) · HT = c · HT + e · HT = e · HT ,
(1.30)
называемая синдромом, зависит только от вектора ошибки e и не зависит от исходного кодового слова с. Причем если ошибок в канале не
было, то s = 0.
20
Для синдромов линейных кодов может быть доказана следующая
теорема [1].
Теорема 1.5. Пусть d минимальное расстояние линейного кода.
Тогда если e1 , e2 ? Xn два различных вектора ошибок, таких, что вес
каждого вектора ошибок меньше (d ? 1)/2, то s(e1 ) 6= s(e2 ). Другими
словами синдромы различных ошибок, вес которых не превышает (d ?
1)/2, различны.
Из теоремы следует, что для исправления ошибок, число которых не
превышает (d ? 1)/2, в декодере канала достаточно хранить синдромы,
которые соответствуют векторам ошибок веса не более (d ? 1)/2.
Алгоритм синдромного декодирования кодов Хемминга можно описать при помощи следующих трех шагов.
Алгоритм 1.3. Синдромное декодирование кодов Хемминга
Входные данные.
Длина кодового слова n.
Длина информационной последовательности k .
Проверочная матрица H.
Входная последовательность y.
Шаг 1.
Для i = 0, ..., n ? 1.
ei := 0.
ei [i] := 1.
si := ei · HT .
Шаг 2.
s? := y · HT .
Если s? = 0.
c := y.
Иначе
j := ?1.
Для i = 0, ..., n ? 1.
Если si = s? , то
j := i,
c := y + ei .
Шаг 3.
Если j 6= ?1, то
Извлечь сообщение m из c.
Иначе сообщить системе, что произошло более одной ошибки.
21
Следует отметить, что в алгоритме 1.3 шаг 1, связанный с построением таблицы соответствия синдромов и векторов ошибок, выполняется
только один раз. Полученная таблица хранится в памяти декодера канала и используется при декодировании всех поступающих сообщений.
Продемонстрируем процедуру декодирования в режиме исправления на
следующем примере.
Пример 1.13.
m = (101) использовался расши-
Пусть для передачи сообщения
ренный код Хемминга из примера 1.11 с порождающей матрицей
G
?
1
=? 0
0
0
1
0
0
0
1
c=m·G
1
= (101) ? 0
0
0
1
0
1
0
1
0
1
1
?
1
1 ?.
1
1
0
1
0
1
1
?
1
1 ? = (1011010).
1
c как
Кодер канала формирует кодовое слово
?
1
1
0
0
0
1
1
1
0
e = (0010000).
y = c + e = (1001010).
Пусть в процессе передачи возникла одна ошибка и вектор ошибок
Тогда на вход декодера канала поступает сообщение
Декодер канала вычисляет синдром
?
s? = y · HT
?
?
?
?
?
= (1001010) ?
?
?
?
?
1
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
1
1
1
0
0
0
1
?
?
?
?
?
?
? = (0111).
?
?
?
?
Затем выполняется поиск полученного синдрома в таблице синдромов 1.3:
s
Полученный синдром совпадает с синдромом 2 , который соответствует вектору
e2 = (0010000). Поэтому декодер канала принимает решение, что на стороне
c = y + e2 = (1011010) и исходное
сообщение m = (101).
ошибок
кодера канала было сформировано кодовое слово
Продемонстрируем процедуру декодирования в режиме обнаружения на следующем примере.
Пример 1.14.
Пусть для передачи сообщения
m
= (101) использовался рас-
ширенный код Хемминга из примера 1.11 и было сформировано кодовое слово
c = (1011010) из примера 1.13. Пусть в процессе передачи возникли две ошибки
e = (0010001). Тогда на вход декодера канала поступает сообщение
y = c + e = (1001011).
и вектор ошибок
22
Таблица 1.3.
Синдромное декодирование кодов Хемминга
i
ei
si = ei · HT
0
1000000
1101
1
0100000
1011
2
0010000
0111
3
0001000
1000
4
0000100
0100
5
0000010
0010
6
0000001
0001
Декодер канала вычисляет синдром
?
s? = y · HT
?
?
?
?
?
= (1001011) ?
?
?
?
?
1
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
1
1
1
0
0
0
1
?
?
?
?
?
?
? = (0110).
?
?
?
?
s
Так как синдром ? отличен от нулевого, то декодер канала выносит решение о
том, что в канале произошла ошибка.
Продемонстрируем процедуру декодирования в режиме обнаружения в случае, когда количество ошибок более чем d ? 1 (не выполняется
условие теоремы 1.3) на следующем примере.
Пример 1.15.
Пусть для передачи сообщения
m
= (101) использовался рас-
ширенный код Хемминга из примера 1.11 и было сформировано кодовое слово
c = (1011010) из примера 1.13. Пусть в процессе передачи возникли четыре ошибки
e = (1110001). Тогда на вход декодера канала поступает сообщение
y = c + e = (0101011).
и вектор ошибок
Декодер канала вычисляет синдром
?
s? = y · HT
Так как синдром
?
?
?
?
?
= (0101011) ?
?
?
?
?
1
1
0
1
0
0
0
1
0
1
0
1
0
0
0
1
1
0
0
1
0
1
1
1
0
0
0
1
?
?
?
?
?
?
? = (0000).
?
?
?
?
s? является нулевым, то декодер канала выносит ошибочное
решение о том, что в канале не было ошибок.
23
1.5.
Порядок выполнения лабораторной работы
В соответствии с вариантом задания:
1) построить проверочную и порождающую матрицы кода Хемминга;
2) сформировать кодовое слово, убедиться, что кодовое слово удовлетворяет (1.13);
3) внести в кодовое слово одну ошибку и выполнить декодирование
в режиме исправления, затем в режиме обнаружения;
4) внести в кодовое слово более одной ошибки и выполнить декодирование в режиме обнаружения.
1.6.
Требования к содержанию отчета
1. Постановка задачи.
2. Описание алгоритмов построения порождающей и проверочной
матрицы кода Хемминга и алгоритма декодирования в соответствии с вариантом задания.
3. Выводы по работе.
24
1.7.
ќ
Варианты заданий
Длина
Длина информацион-
Минимальное
кодо-
ной последовательно-
расстояние,
вого
сти,
Декодирование
d
k
слова,
n
1
7
4
3
По минимуму
расстояния
2
7
4
3
Синдромное
3
7
3
4
По минимуму
расстояния
4
7
3
4
Синдромное
5
15
11
3
По минимуму
расстояния
6
15
11
3
Синдромное
7
15
10
4
По минимуму
расстояния
8
15
10
4
Синдромное
9
31
26
3
Синдромное
10
31
25
4
Синдромное
11
63
57
3
Синдромное
12
63
56
4
Синдромное
25
Лабораторная работа ќ2
ЛИНЕЙНЫЕ ЦИКЛИЧЕСКИЕ
КОДЫ
Целью работы является приобретение практических навыков построения циклических кодов, а также программная реализация алгоритмов обнаружения и исправления ошибок.
2.1.
Предварительные сведения
Пусть имеется конечное поле GF (q). Многочленом a(x) степени n
называется следующее математическое выражение:
a(x) = an · xn + an?1 · xn?1 + ... + a1 · x1 + a0 · x0 ,
(2.1)
в котором коэффициенты a0 , ..., an принадлежат конечному полю
GF (q), q число элементов в этом поле, x формальная переменная.
Пусть a(x) и b(x) многочлены с коэффициентами из поля GF (q).
a(x) = an · xn + ... + a0 · x0 ,
b(x) = bn · xn + ... + b0 · x0 .
Тогда над многочленами определены следующие операции.
1. Операция сложения.
a(x) + b(x) = (an + bn ) · xn + ... + (a0 + b0 ) · x0 .
Пример 2.1.
Пусть заданы два многочлена с коэффициентами из поля
GF (2):
a(x) = x2 + x + 1,
b(x) = x + 1.
Тогда сумма многочленов
a(x) + b(x) вычисляется следующим образом:
a(x) + b(x) = x2 + (1 + 1) ·x + (1 + 1) ·x0 = x2 .
| {z }
| {z }
0
26
0
2. Операция умножения.
a(x)·b(x) = (an ·bn )x2n +...+(an ·b0 )xn +...+(a0 ·bn )xn +...+(a0 ·b0 )x0 .
Пример 2.2.
Пусть заданы два многочлена с коэффициентами из поля
GF (2):
a(x) = x2 + x + 1,
b(x) = x + 1.
Тогда произведение многочленов
a(x)·b(x) вычисляется следующим образом:
a(x) · b(x) = (x2 + x + 1)(x + 1) = x3 + x2 + x + x2 + x + 1 = x3 + 1.
3. Деление многочленов с остатком. Пусть четыре многочлена с коэффициентами из конечного поля связаны следующим образом:
a(x) = b(x) · c(x) + d(x).
Тогда многочлен d(x) называется остатком от деления многочлена a(x) на многочлен b(x) и обозначается через a(x) mod b(x).
Для вычисления остатка от деления используется так называемое
деление ѕв столбикї, в котором используются операции умножения и сложения многочленов.
Пример 2.3.
Пусть заданы два многочлена с коэффициентами из поля
GF (2):
a(x) = x3 + x + 1,
b(x) = x + 1.
Тогда остаток от деления
a(x) на b(x) вычисляется следующим образом:
x3 +x +1 x + 1
x3 +x2
x2 + x
2
x +x +1
x2 +x
1
Таким образом,
a(x) mod b(x) = 1.
27
2.2.
2.2.1.
Циклические линейные коды
Определение и свойства циклических кодов
Пусть y = (y0 , y1 , ..., yn ) является вектором линейного пространства
Y. Этому вектору можно поставить в соответствие многочлен y(x) от
формальной переменной x следующим образом:
y(x) = y0 + y1 · x + ... + yn?1 · xn?1 .
(2.2)
Такое сопоставление взаимно однозначно, так как каждому вектору соответствует единственный многочлен и каждому многочлену соответствует единственный вектор. Линейной комбинации y = m1 · a + m2 · b
пары векторов a = (a0 , a1 , ..., an?1 ) ? Y и b = (b0 , b1 , ..., bn?1 ) ? Y соответствует линейная комбинация многочленов
y(x) =
n?1
X
(m1 · ai + m2 · bi ) · xi = m1 · a(x) + m2 · b(x).
(2.3)
i=0
Если c = (c0 , c1 , ..., cn?1 ) кодовое слово линейного кода C, то соответствующий многочлен c(x) также будем называть кодовым словом.
Линейным циклическим кодом называется такой линейный код, для
которого циклический сдвиг любого кодового слова на любое количество разрядов влево или вправо также является кодовым словом. Это
означает, что если кодовое слово c = (c0 , c1 , ..., cn?1 ) принадлежит линейному циклическому коду C, то и слова c1 = (c1 , c2 , ..., cn?1 , c0 ) и
c2 = (cn?1 , c0 , c1 , ..., cn?2 ) также принадлежат коду C. В дальнейшем
для краткости линейные циклические коды будем называть циклическими.
Пример 2.4.
Рассмотрим два линейных кода
C1
?
?
000 ?
?
?
?
?
?
110
=
,
?
?
011
?
?
?
?
101
C2
C1 и C2 :
?
?
0000000 ?
?
?
?
?
?
?
0010111 ?
?
?
?
?
?
?
?
?
?
0101011 ?
?
?
?
?
?
?
0111100
=
.
?
?
1001101
?
?
?
?
?
?
? 1011010 ?
?
?
?
?
?
?
?
? 1100110 ?
?
?
?
?
?
1110001
28
Код
C1 является циклическим, так как при циклическом сдвиге любого слова
на произвольное количество разрядов влево или вправо получается кодовое слово.
Код
C2 не является циклическим, так как при циклическом сдвиге могут получиться
слова не принадлежащие коду.
Пусть вектору c длины n в поле GF (2) соответствует многочлен
c(x). Тогда многочлен c0 (x) = c(x) · xL mod (xn + 1) соответствует циклическому сдвигу вектора c на L разрядов влево.
c = (1100000) в поле GF (2) и необходимо
с0 , который является сдвигом вектора c на один разряд влево,
то есть L = 1. Вектору c соответствует многочлен c(x) = x6 + x5 . Тогда c0 (x) =
(x7 + x6 ) mod (x7 + 1) = x6 + 1. Значит вектор с0 = (1000001).
Пример 2.5.
Пусть имеется вектор
вычислить вектор
Для циклических кодов справедлива следующая теорема [1].
s
Теорема 2.1. Пусть m(x) = m0 + m1 · x + ... + ms · x произвольный
многочлен с коэффициентами из поля GF (q) и c(x) = c0 + c1 · x + ... +
cn?1 · xn?1 кодовое слово циклического кода С. Тогда c0 (x) = m(x) ·
c(x) mod (xn ? 1) также является словом из кода С.
Порождающим многочленом циклического кода C с кодовыми словами длины n и информационной последовательностью длины k называется такой ненулевой многочлен
g(x) =
r
X
gi · xi
(2.4)
i=0
из кода C, который имеет минимальную степень и коэффициент gr = 1.
Для порождающего многочлена циклического кода справедливы
следующие теоремы [1].
Теорема 2.2. Пусть C циклический код с кодовыми словами длины n и информационной последовательностью длины k и g(x) его
порождающий многочлен. Тогда степень g(x) равна r = n ? k и каждое
кодовое слово из C может быть единственным образом представлено в
виде
c(x) = m(x) · g(x),
(2.5)
где m(x) имеет степень меньшую или равную k ? 1.
Теорема 2.3. Пусть g(x) порождающий многочлен циклического
кода с кодовыми словами длины n и информационной последовательностью длины k . Тогда (xn ? 1) mod g(x) = 0.
29
2.2.2.
Кодирование циклическими кодами
Пусть для информационного многочлена m(x) (многочлена, соответствующего информационной последовательности m) необходимо
сформировать кодовое слово c(x), принадлежащее циклическому коду
с поро?
Документ
Категория
Без категории
Просмотров
0
Размер файла
908 Кб
Теги
part, labs, twoside
1/--страниц
Пожаловаться на содержимое документа