close

Вход

Забыли?

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

?

MarkovskyTyrlikov

код для вставкиСкачать
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
Федеральное государственное автономное образовательное учреждение
высшего профессионального образования
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ
С. Г. Марковский, А. М. Тюрликов
ЭЛЕМЕНТЫ ТЕОРИИ
ПОМЕХОУСТОЙЧИВОГО
КОДИРОВАНИЯ
Учебное пособие
Санкт-Петербург
2014
УДК 004.5
ББК 32.811.4
М27
Рецензенты:
доктор технических наук, профессор В. А. Богатырёв;
кандидат технических наук, доцент В. П. Попов
Утверждено
редакционно-издательским советом университета
в качестве учебного пособия
Марковский, С. Г.
М27 Элементы теории помехоустойчивого кодирования: учеб. пособие / С. Г. Марковский, А. М. Тюрликов. – СПб.: ГУАП, 2014. – 95 с.
ISBN 978-5-8088-0977-2
Рассмотрены блоковые, линейные и циклические коды. Приведены алгоритмы кодирования и декодирования для этих кодов,
большое число примеров, поясняющих работу представленных алгоритмов. Пособие является основой для дальнейшего изучения используемых на практике алгоритмов помехоустойчивого кодирования и декодирования.
Издание предназначено для студентов, обучающихся по специальностям 230400, 210700, может быть использовано для самостоятельной работы студентов, а также при выполнении заданий по
НИР.
УДК 004.5
ББК 32.811.4
ISBN 978-5-8088-0977-2
©
©
Марковский С. Г., Тюрликов А. М., 2014
Санкт-Петербургский государственный
университет аэрокосмического
приборостроения, 2014
ВВЕДЕНИЕ
Практически во всех современных системах передачи и хранения
информации используется помехоустойчивое кодирование. Помехоустойчивое кодирование позволяет исправлять или обнаруживать
ошибки, которые могут возникать из-за наличия помех в каналах
связи. Отсюда и возник данный термин. Основная идея помехоустойчивого кодирования состоит в том, что в передаваемое сообщение,
по определенному правилу, вносится некоторая дополнительная информация, т. е. добавляется некоторая избыточность. Поэтому помехоустойчивое кодирование, иногда, называют избыточным кодированием. За счет внесения дополнительной информации (избыточности) могут быть исправлены, либо обнаружены ошибки.
Следует различать такие научные дисциплины как теория информации и теория помехоустойчивого кодирования. Теория информация (см., например, учебное пособие [6]) позволяет установить
предельные границы как скорости передачи информации, так и степени сжатии информации. В частности, теория информации позволяет ответить на вопрос, с какой максимальной скоростью можно,
за счет внесения избыточности, передавать данные по спутниковому
каналу, если известны мощность передатчика, затухание в канале
и уровень шумов в приемнике. При этом не рассматривается, каким
образом следует вводить избыточность. Теория помехоустойчивого
кодирования указывает как способы внесения этой избыточности
(кодирование), так и способы обработки при приеме (декодирование).
Существует множество способов помехоустойчивого кодирования, которые можно разбить на две группы – блоковое кодирование
и неблоковое кодирование. При блоковом кодировании последовательность данных разбивается на фрагменты, которые называют
блоками. Как на передающей, так и на приемной стороне, каждый
блок обрабатывается независимо от других блоков. Простейшим
примером блокового кодирования является кодирование с проверкой на четность. При этом кодировании последовательность бит
разбивается на блоки, например байты, т. е. в каждом блоке содержится восемь бит. К этим восьми битам добавляется еще один
дополнительный (избыточный) бит. Образовавшуюся последовательность из девяти бит называют кодовым словом. Значение избыточного бита формируется таким образом, чтобы число единиц в
кодовом слове было четным. Кодовые слова последовательно друг
за другом передаются по каналу. На приемной стороне, для каждой
принятой из канала последовательности, состоящей из девяти бит,
3
вычисляется число единиц. Если это число нечетно, то это значит,
что произошла ошибка при передаче данного кодового слова. Более
подробно, данный пример будет рассмотрен в подразд. 1.2.
При неблоковом кодировании обработка каждого последующего
фрагмента информации зависит от обработки предыдущего фрагмента.
Неблоковое кодирование часто называют сверточным кодированием.
В современных системах находят широкое применение как блоковое, так и неблоковое кодирование. Однако приступить к изучению
неблоковых кодов можно только после того как освоены основные
принципы кодирования и декодирования блоковых кодов. Поэтому в
настоящем учебном пособии рассматриваются только блоковые коды.
Краткое описание неблоковых кодов приведено в [4, подразд. 1.1.3].
Более подробное описание неблоковых кодов можно найти в [3].
Пособие состоит из трех разделов. Каждый раздел содержит большое число примеров, часть примеров взята из [2]. В первом разделе
формулируются основные задачи помехоустойчивого кодирования и
вводятся понятия блокового кода и его характеристик, рассматриваются алгоритмы кодирования и декодирования, изучаются свойства
этих алгоритмов. Первый раздел учебного пособия является основой,
на базе которой строятся последующие разделы. Во втором разделе
рассматривается частный случай блоковых кодов – линейные коды.
Сначала вводится математический аппарат, который необходим для
изучения линейных кодов (конечные поля и линейные пространства).
Затем вводится понятие линейного кода, формулируются алгоритмы
кодирования и декодирования. По аналогии со вторым разделом построен третий раздел, в котором рассматривается частный случай линейных кодов – циклические коды. Математические аппарат, который
используется при рассмотрении циклических кодов – это многочлены
с коэффициентами из конечного поля. В третьем разделе рассматриваются только начальные сведения из циклических кодов. Более подробное рассмотрение циклических кодов приведено в учебном пособии [5].
Специалистам, разрабатывающим системы передачи и хранения
информации, материал, изложенный в данном учебном пособии можно рассматривать как теоретическую основу, на базе которой в дальнейшем можно самостоятельно изучать используемые на практике
алгоритмы помехоустойчивого кодирования и декодирования. Обзор
таких алгоритмов содержится в работах [1,8]. Для тех, кто хочет более
углубленно изучить теорию помехоустойчивого кодирования могут
быть рекомендованы как классические работы [7,10], так и учебное
пособие одного из ведущих отечественных специалистов в области помехоустойчивого кодирования Виктора Дмитриевича Колесника [4].
4
1. ОСНОВНЫЕ ЗАДАЧИ ПОМЕХОУСТОЙЧИВОГО
КОДИРОВАНИЯ. БЛОКОВОЕ КОДИРОВАНИЕ
1.1. Модель системы передачи (хранения) информации
Модель системы передачи информации была впервые предложена Шенноном в 1948 г. Структурная схема системы передачи (хранения) цифровой информации представлена на рис. 1.1[6]. Рассмотрим кратко основные блоки схемы.
Источник информации (И) – любой объект, способный порождать сообщения для перемещения в пространстве (передача информации) или во времени (хранение информации): например, человек, файл на жестком диске, звуковой сигнал с выхода микрофона
и т. д. Если входной сигнал источника аналоговый, то его необходимо преобразовать в дискретный при помощи АЦП.
Кодер источника (КИ) удаляет из входных сообщений избыточную информацию для эффективного использования ресурса канала связи или памяти.
Декодер приемника (ДП) вносит во входную последовательность естественную избыточность, удаленную КИ.
Различают кодеры с потерей качества, когда данные на входе КИ
и данные на выходе ДП не совпадают (mp3,h264 и другие), и кодеры, работающие без потери качества, когда эти данные совпадают
(архиваторы winzip, winrar и т.п., аудиокодек FLAC (Free Lossless
Audio Codec), свободный аудиокодек сжатия без потерь).
Кодер канала (КК) специальным образом вносит избыточную
информацию в сообщения с целью защиты сообщений от помех при
передаче по каналу связи, либо от возможных искажений при хранении информации.
И
КИ
КК
М
С
П
ДП
ДК
Д
ИШ
Рис. 1.1. Блок-схема системы связи
5
Декодер канала пытается обнаружить и исправить ошибки в канале.
Канал (К) включает в себя модулятор (М), среду распространения
сигналов или хранения (С) и демодулятор (Д). Модулятор сопоставляет с входным символом некоторый сигнал, который передается в
заданной среде. Передача сигнала – это возмущение некоторой физической среды, например, электромагнитного поля в радиоканале.
Источник шума (ИШ) составляют объекты, которые влияют
на физическую среду (например, в радиоканале: тепловой шум на
входе приемника, другие передающие устройства, линии электропередачи и т. п.).
Демодулятор сопоставляет принятую из канала смесь сигнала и
шума с некоторым символом. Этот символ может совпадать с тем, который поступил на вход модулятора, при невысокой интенсивности
шума в канале или отличаться при большом значении интенсивности.
1.2. Помехоустойчивое кодирование
Для уменьшения числа ошибок при передаче сообщений (хранении информации) используют помехоустойчивые коды, которые
изучает теория помехоустойчивого кодирования. Основная идея,
заложенная в построение этих кодов, состоит в том, что в передаваемые сообщения вносится некоторая избыточность. Хотя шум
искажает информационные и избыточные (проверочные) символы,
всегда остается достаточная информация, позволяющая восстанавливать сообщения при помощи специально разработанных методов
декодирования, если только шум не является слишком сильным.
Блоки, которые входят в систему помехоустойчивого кодирования
(рис. 1.1), выделены в отдельный блок.
Пример системы.
Рассмотрим систему обеспечения сжатия информации на жестком диске.
Здесь КИ – это программа архивации, работающая в режиме
сжатия. К – это магнитный носитель и аппаратура, обеспечивающая запись/чтение на магнитный носитель. ИШ – это дефекты магнитного носителя.
КК и ДК – аппаратные средства, реализующие алгоритмы помехоустойчивого кодирования и декодирования.
ДП – это программа архивации, работающая в режиме восстановления.
6
В дальнейшем под словом кодер будем иметь в виду КК, а под
словом декодер – ДК.
Рассмотрим еще один пример.
Пусть имеется параллельный канал связи (набор проводов) и
требуется передавать по этому каналу информацию в виде отдельных байт, и при этом иметь возможность обнаружить любую одиночную ошибку. Под ошибкой здесь понимается изменение значения бита на противоположное.
Для решения этой задачи потребуется к 8 проводам добавить
еще один избыточный провод и построить систему следующим образом (рис. 1.2).
Кодер формирует сигнал A9 = X1 Å X2 Å X3 Å X4 Å X5 Å X6 Å X7 Å X8 .
Å X5 Å X6 Å X7 Å X8 . Декодер формирует сигнал E = B1 Å B2 Å B3 Å B4 Å B5 Å B6 Å B7 Å B
3 Å B4 Å B5 Å B6 Å B7 Å B8 Å B9 .
Если сигнал E = 1, то ошибка обнаруживается. Пример демонстрирует справедливость следующих утверждений:
1. Любая одиночная ошибка обнаруживается.
2. Любая двойная ошибка не обнаруживается.
3. Любое нечетное число ошибок обнаруживается.
4. Любое четное число ошибок не обнаруживается.
Применительно к этой схеме, теория помехоустойчивого кодирования может ответить на следующие вопросы:
1. Какое минимальное количество избыточных проводов следует
ввести, чтобы можно было обнаружить ошибки кратности f (f > 1)?
В данной схеме f = 1.
X1
X2
A1
B1
A2
B2
A8
B8
X8
=1
B9
A9
Кодер
Канал
Y1
Y2
Y8
=1
E
Декодер
Рис. 1.2. Кодер кода с проверкой на четность
7
2. Сколько избыточных проводов следует ввести, чтобы можно
было исправлять ошибки кратности t > 0 (в данном случае t = 0)?
3. Как будут выглядеть схемы кодера и декодера при обнаружении ошибок кратности f и исправлении ошибок кратности t?
1.3. Блоковое кодирование. Основные определения
Пусть Х – множество, состоящее из q элементов: Х = {x1, x2, ….,
xq}. Будем называть его кодовым алфавитом. Число элементов множества Х называется мощностью множества (|X|= q). Через Хn обозначается множество всех последовательностей длины n и |Xn|= qn.
Пример 1.1. Х = {0, 1}. Тогда Х2 = {(00), (01), (10), (11)} – множество всех двоичных последовательностей длины 2.
Определение. Пусть имеется алфавит Х и |X|= q. Блоковым q-м
кодом называется любое подмножество A последовательностей из
Xn. Элементы этого подмножества называют кодовыми словами.
Если q = 2, то код называют двоичным. Число n называют длиной
кода. Количество кодовых слов в A называется мощностью кода
(|A|= M). Числа q, n и M называют параметрами блокового кода.
Пример 1.2. Пусть имеется алфавит: Х = {0, 1}, q = 2 – двоичный код.
Построим множество всех возможных последовательностей длины 3:
X3 = {(000),(001),(010),(011),(100),(101),(110),(111)}. В соответствии с определением любое подмножество A этого множества является двоичным кодом (|Х|= 2) длины 3.
Приведем пример блокового кода: A = {(000), (111)}. Это блоковый код с параметрами: q = 2 – двоичный код, длина кода n = 3,
мощность кода M = 2. Код имеет два кодовых слова: a1 = (000) и
a2 = (111). Каждое кодовое слово представляет собой q-й вектор.
Поэтому используются соответствующие обозначения.
Пусть I = {i1,i2, …, iM} – произвольное конечное множество, состоящее из M элементов. Будем называть I множеством сообщений.
Определение. Кодированием для блокового кода называется взаимно однозначное отображение множества сообщений на множество кодовых слов.
Имеем: множество сообщений I и множество кодовых слов А.
Каждому сообщению соответствует свое кодовое слово и наоборот,
каждому кодовому слову соответствует свое сообщение. В общем
случае, если код состоит из М слов (A = {a1, a2, …, aM}), то с помощью этого кода можно выполнить кодирование множества сообщений (I = {i1,i2, …, iM}) (рис. 1.3).
8
A
I
.1
i
a1
.
.
.
.
aM
.
iM
Рис. 1.3. Кодирование множества из M сообщений
Пример 1.3. Пусть имеется код из примера 1.2, т. е. a1 = (000) и
a2 = (111). С помощью такого кода можно передать два сообщения
(рис. 1.4).
Пример 1.4. Пусть A = {(00), (01), (10), (11)}. I = {0, 1, 2, 3}. Кодирование данного множества сообщений представлено на рис. 1.5.
A
I
0
(000)
1
(111)
Можно задать и такое правило
Рис. 1.4. Кодирование двух сообщений
A
I
0
(00)
1
(01)
2
(10)
3
(11)
Рис. 1.5. Кодирование множества из 4 сообщений
9
1.4. Скорость кодирования
Скорость блокового кода (бит/символ) определяется следующей
формулой:
R ≜(log2M) / n.
Скорость равна количеству двоичных единиц информации (бит),
которые могут быть переданы с помощью одного символа кодового
слова. Максимальное значение скорости кода равно log2q. При q = 2
максимальное значение скорости R = 1. При такой скорости кодовыми словами являются всевозможные двоичные последовательности, и каждый символ переносит один бит информации.
Пример 1.5. X3 = {(000),(001),(010),(011),(100),(101),(110),(111)}.
M = 8, n = 3, R = 1.
Такой код является безызбыточным. Он не позволяет ни обнаруживать, ни исправлять ошибки, так как любая ошибка переводит одно кодовое слово в другое. Уменьшение числа используемых
кодовых слов при сохранении их длины, с одной стороны, приводит к уменьшению скорости и появлению избыточности, а, с другой
стороны, дает возможность обнаруживать и исправлять ошибки.
Избыточность кода определяется как разность между максимальным значением скорости и ее действительным значением. В двоичном случае избыточность равна 1 – R.
Пример 1.6. Пусть имеем два кодовых слова a1 = (000) и a2 = (111).
M = 2, n = 3, q = 2. R = (log22)/3 = 1/3, т. е. каждые три символа переносят один бит информации. Избыточность кода равна 1 – 1/3 = 2/3.
1.5. Основные принципы декодирования
Основную идею декодирования поясним на следующем примере.
Пример 1.7. Пусть X = {0,1} – множество символов на входе канала (входной алфавит канала), Y = {0,1}– множество символов на
выходе (выходной алфавит канала). Для передачи по каналу будем
использовать код, состоящий из двух слов: a1 = (000) и a2 = (111).
Таким образом, на входе канала могут появиться последовательности только из множества A = {(000), (111)}. Поскольку в канале
могут происходить ошибки, то на выходе канала может появиться любая последовательность из множества: Y3 = {(000), (001), …,
(111)} – множество всех последовательностей длины 3 над выходным алфавитом канала.
10
Y3
A
(000)
(000)
(001)
(010)
(011)
(100)
(111)
(101)
(110)
(111)
Рис. 1.6. Декодер, исправляющий одиночные ошибки
Задача декодера – определить по выходу канала, какое из кодовых слов поступало на вход канала. Если декодер будет исправлять
любые одиночные ошибки, то эта задача может быть решена следующим образом (рис. 1.6).
Обобщая предыдущий пример, можно дать следующее определение.
Определение. Декодирование – это отображение множества последовательностей на выходе канала на множество кодовых слов.
Это отображение можно задать путем разбиения множества последовательностей на выходе канала на так называемые решающие
области.
Определение. Решающей областью Yi – называется множество
из таких последовательностей на выходе канала, при появлении
которых декодер выносит решение, что передавалось кодовое слово
ai. Yi: = {y∈Yn: декодер по последовательности y выносит решение,
что передавалось кодовое слово ai}.
Решающие области обладают следующим свойством: если i ≠ j,
то Yi ∩ Yj = ∅, т.е. решающие области для разных слов не пересекаются. Объединим решающие области для всех кодовых слов и
удалим полученное множество из множества всех последовательностей на выходе канала: Yn \ (Y1 U Y2 U …. U YM) = Y0. Символ “\”
означает удаление множества, например, {1,2,3,4} \ {2,3} = {1,4}.
Образованное в результате этой операции множество называют областью отказа. При появлении на выходе канала последовательности из области отказа декодер формирует сигнал обнаружения
ошибки, которую он не в состоянии исправить.
11
Если передаваемое кодовое слово принадлежит решающей области Yi, но y относится к решающей области Yj, то при декодировании происходит ошибка и получателю выдается неверное решение.
Пример 1.8. Для декодирования, описанного в примере 1.7, решающие области имеют следующий вид: Y1 = {(000), (001), (010),
(100)}, Y2 = {(111), (110), (101), (011)}, Y0 = ∅. Любая однократная
ошибка не выводит принятое кодовое слово a1 = (000) или a2 = (111)
из своей решающей области. Поэтому при любых однократных
ошибках декодер правильно определит кодовое слово.
Пример 1.9. Для кода, состоящего из двух слов: (000), (111), составим решающие области так, чтобы обнаруживать любые одиночные и двойные ошибки (рис. 1.7).
Заметим, что в предыдущем примере, двойная ошибка приводит к
ошибке декодирования. Решающие области имеют следующий вид:
Y1 = {(000)}, Y2 = {(111)}, Y0 = {(001), (010), (011), (100), (101),
(110)}. При любых однократных или двукратных ошибках принятая последовательность попадет в область отказа, и ошибки будут
обнаружены.
Пример 1.10. Для кода, состоящего из всех последовательностей
множества X3 = {(000), (001), …, (111)}, решающие области будут
иметь следующий вид:
Y1 = {(000)}, Y2 = {(001)}, Y3 = {(010)}, Y4 = {(011)}, Y5 = {(100)},
Y6 = {(101)}, Y7 = {(110)}, Y8 = {(111)}. В отсутствии ошибок последовательность на выходе канала принадлежит той решающей области, которая соответствует переданному кодовому слову. Область
отказа пуста. Любая ошибка переводит переданное кодовое слово
Y3
A
(000)
(000)
(001)
(010)
(011)
(100)
(101)
(110)
(111)
(111)
Рис. 1.7. Декодирование с использованием решающих областей
12
в решающую область, соответствующую другому кодовому слову,
т. е. приводит к ошибке декодирования. Данный код – безызбыточный. Он не может обнаруживать и исправлять ошибки.
Теперь опишем алгоритмы работы кодера и декодера (декодирование с использованием решающих областей).
1.6. Алгоритмы кодирования и декодирования
1. Алгоритм кодирования. Кодер хранит список кодовых слов
и таблицу соответствия между сообщениями и кодовыми словами.
Для каждого кодируемого сообщения кодер находит в этой таблице
соответствующее кодовое слово. Для двоичного кода объем памяти
кодера будет равен V = M × n.
2. Алгоритм декодирования. Декодер должен хранить разбиение множества последовательностей на выходе канала, на множество решающих областей (рис. 1.8).
Yn
Решающая область
a1
Решающая область
a2
.
.
.
Область отказа
Отказ
.
.
.
Решающая область
aM–1
Решающая область
aM
Рис. 1.8. Память декодера
13
Если на выходе канала появляется последовательность y, то декодер выполняет следующие действия:
1. Определяет к какой решающей области принадлежит последовательность (y∈Yi).
2. Выносится решение в пользу кодового слова ai или решение –
отказ от декодирования, если принятая последовательность попадает в область отказа.
Для двоичного кода объем памяти декодера: V = n × 2n, так как в
общем случае в памяти декодера хранятся все последовательности,
которые могут появиться на выходе канала.
Цель дальнейшего изложения – рассмотреть алгоритмы, при реализации которых существенно уменьшается объем памяти декодера.
1.7. Расстояние Хэмминга
Определение. Пусть x и y – две последовательности из Xn. Расстоянием Хемминга d(x,y) называется число несовпадающих позиций в последовательностях x и y.
Пример 1.11. Рассмотрим все возможные двоичные последовательности длины 3. Их можно отобразить в вершинах трехмерного куба, каждое ребро которого соответствует расстоянию, равному 1 (рис. 1.9). Например, d((010),(110)) = 1. Тогда, d((000),(111)) =
110
100
111
101
010
000
011
001
Рис. 1.9. Расстояние Хэмминга
14
d((000),(010)) + d((010),(110)) + d((110),(111)) = 3. Или, d((000),(111)) =
d((000),(001)) + d((001),(011)) + d((011),(111)) = 3.
Расстояние Хэмминга обладает следующими свойствами:
1. d(x,y) = d(y,x) – свойство симметричности.
2. d(x,y) ≥0, d(x,y) = 0, если x = y – свойство неотрицательности.
3. d(x,y) ≤ d(x,z) + d(y,z) – неравенство треугольника.
Первые два свойства непосредственно следуют из определения
расстояния Хемминга. Докажем третье свойство.
Пусть x = (x1,x2, …, xn), y = (y1,y2, …, yn) , z = (z1,z2, …, zn) – три
последовательности из Xn.
Используем очевидное свойство расстояния Хэмминга – свойство аддитивности. Расстояние между последовательностями x и y
равняется сумме расстояний между их компонентами, т. е.
n
d(x,y) = å d(xi , yi ), где d(xi,yi) = 0, если xi = yi и d(xi,yi) = 1,
i=1
если xi ≠ yi .
Пример 1.12. Для q = 2 и n = 3 определим расстояние Хэмминга
между последовательностями x = (010) и y = (110). d(x,y) = d(x1,y1) +
d(x2,y2) + d(x3,y3) = 1 + 0 + 0 = 1.
Рассмотрим неравенство d(xi,yi) ≤ d(xi,zi) + d(zi,yi).
При d(xi,yi) = 0 неравенство справедливо в силу свойства неотрицательности расстояния. При d(xi,yi) = 1, хотя бы одно из слагаемых в правой части равно 1, и, следовательно, неравенство верно.
Далее, суммируя обе части неравенства по всем значениям i, доказываем свойство 3.
1.8. Алгоритм декодирования
по минимуму расстояния Хэмминга
Описание этого и ряда других алгоритмов будем приводить в
виде таблицы (табл. 1.1), состоящей из двух частей. В левой части
даем формализованное описание шагов алгоритма, в правой части
иллюстрируем эти шаги на конкретном примере.
Замечание к алгоритму: на втором шаге алгоритма минимум может быть достигнут одновременно для нескольких кодовых слов.
Если это так, то на третьем шаге решение декодера выбирается случайным образом среди этих кодовых слов. Можно показать, что в
некотором смысле такое поведение декодера будет оптимальным.
В практических реализациях часто, в качестве решения на третьем
15
Таблица 1.1
Алгоритм декодирования по минимуму расстояния Хэмминга
Шаг
Общий вид алгоритма
Конкретный пример
алгоритма
Исходные Декодер хранит список кодовых a1 = (00000), a2 = (01110),
данные слов A = {a1, a2, …, aM}, и для a3 = (10101), a4 = (11011),
каждой принятой из канала y = (11111)
последовательности y выполняются
следующие действия:
1
Вычисляются расстояния между d1 = 5, d2 = 2, d3 = 2, d4 = 1
принятой из канала последовательностью y и всеми кодовыми
словами: d1 = d(a1,y), …, dM = d(aM,y)
2
Находится кодовое слово, для i0 = 4, di0 = 1
которого расстояние от принятой
последовательности минимальное:
i0 такое, что di0 = min di
i=1,M
3
Декодер выносит решение, что Решение: a4
передавалось кодовое слово ai0
шаге, декодер принимает первое из кодовых слов, для которых достигнут минимум.
Теперь рассмотрим алгоритм, который в отличие от алгоритма
декодирования по минимуму расстоянию Хэмминга, в ряде случаев отказывается от декодирования и при этом формирует сигнал
обнаружения ошибки. Такой алгоритм называют алгоритмом декодирования в шаре (табл. 1.2).
1.9. Алгоритм декодирования в шаре
Применительно этому алгоритму, могут быть сформулированы
следующие вопросы:
1. В каком диапазоне может выбираться параметр t0 для заданного кода, чтобы на третьем шаге алгоритма решение всегда выносилось однозначным образом (т. е. если di0 ≤ t0, то минимум при
этом достигнут только на одном кодовом слове)?
2. Сколько ошибок можно исправить и обнаружить для заданного кода и алгоритма декодирования при каком-либо фиксированном значении параметра d?
16
Таблица 1.2
Алгоритм декодирования в шаре
Шаг
алгоритма
Общий вид алгоритма
Конкретный пример
Исходные Декодер хранит список кодовых a1 = (000000), a2 = (011101),
данные слов A = {a1, a2, …, aM} и некоторое a3 = (101011), a4 = (110110),
число t0, которое является пара- t0 = 1
метром алгоритма (радиус шара), y = (111111)
и для каждой принятой из канала
последовательности y выполняются
следующие действия:
1
Вычисляются расстояния между d1 = 6, d2 = 2, d3 = 2, d4 = 2
принятой из канала последовательностью y и всеми кодовыми
словами: d1 = d(a1,y), …, dM = d(aM,y)
2
Находится кодовое слово, для i0 = {2,3,4}, di0 = 2
которого расстояние от принятой
последовательности минимальное:
i0 такое, что di0 = min di
i=1,M
3
Если di0≤t0, то декодер выносит (di0 = 2)>(t0 = 1)
решение о том, что передавалось Решение: ошибка
кодовое слово ai0, иначе отказ от
декодирования и формирование
сигнала ошибки
Для того чтобы ответить на сформулированные вопросы, нам потребуется ввести еще два понятия – шар и минимальное расстояние
кода.
Определение. Шаром радиуса t называется подмножество всех
последовательностей y∈Xn, находящихся на расстоянии d(y, x) ≤ t
от некоторого фиксированного слова x, называемого центром шара:
St(x) = {y: d(y, x) ≤ t}.
Пример 1.13. Пусть x = (1000), тогда можно построить шары с
радиусом t = 1, t = 2 и t = 3 (рис. 1.10).
Определение. Объемом шара, называется число последовательностей, входящих в шар.
Утверждение 1.1. Объем шара не зависит от центра шара, а зависит только от его радиуса.
Доказательство утверждения следует непосредственно из определения объема шара.
17
1111
0100
0111
1110
1001
1011
t=3
1000
0011
1010
1100
t=1
t=2
0001
0101
0000
1101
0010
0110
Рис. 1.10. Шары радиуса 1,2 и 3
Вычислим объем шара. Обозначим через Vt объем шара радиуса t, т. е. Vt =|St(x)|. Ограничимся рассмотрением только двоичного
случая и получим формулу для Vt. Множество St(x) можно представить как объединение из t множеств:
St(x) = {x} U {y: d(y, x) ≤ 1} U … U {y: d(y, x) ≤ t}.
Откуда легко получить, что:
t
Vt = St (x) = Cn0 + Cn1 + ... + Cnt = å Cni , (1)
i=0
n!
n(n -1)...(n - i + 1)
=
, где n – длина кода.
(n - i)! i !
i!
Для примера 1.13 (рис. 1.10) объем шара радиуса 1 – V1 = 5, радиуса 2 – V2 = 11, радиуса 3 – V3 = 15.
Введем понятие минимального расстояния кода.
Определение. Минимальным расстоянием кода называется наименьшее расстояние между всеми его кодовыми словами:
где Cni =
d = min(ai , aj ), i = 1, M, j = 1, M.
i¹ j
18
Пример 1.14. Вычислить минимальное расстояние для кода, состоящего из трех слов a1 = (00000), a2 = (11011), a3 = (11111). Определим расстояния между отдельными кодовыми словами: d(a1, a2) = 4,
d(a1, a3) = 5, d(a2, a3) = 1. Следовательно, минимальное расстояние
кода d = 1.
В общем случае, если код состоит из M слов, то для поиска мини2
мального расстояния потребуется вычислить CM
расстояний. Минимальное расстояние кода также является одним из параметров кода.
1.10. Анализ алгоритма декодирования в шаре
Утверждение 1.2. Для алгоритма декодирования в шаре с радиусом t0 решающие области являются шарами радиуса t0 с центрами
в кодовых словах.
Доказательство следует из определений шара и решающей области.
Проиллюстрируем это утверждение на следующем примере.
Пример 1.15. Пусть a1 = (0000), a2 = (1111) и t0 = 1.
Разобьем множество всех последовательностей, которые могут
появиться на выходе канала, на три подмножества: Y1, Y2, Y0.
Всего на выходе канала может появиться 16 различных последовательностей. Для каждой из них выполним алгоритм декодирования и выясним, какое решение выносит декодер (табл. 1.3).
Решающие области имеют следующий вид.
Y1 = {(0000), (0001), (0010), (0100), (1000)}.
Y0 = [Область отказа] = {(0011), (0101), (0110), (1001), (1010),(1100)}.
Y2 = {(1111), (1110), (1101), (1011), (0111)}.
Из табл. 1.3 следует, что S1 ((0000)) = Y1 и S1 ((1111)) = Y2: т.е.
решающая область для кодового слова (0000) является шаром радиуса единица с центром в точке (0000). Аналогично, для кодового
слова (1111).
Утверждение 1.2 иллюстрирует рис. 1.11.
Непосредственно из утверждения 1.2 и определения решающих
областей следует утверждение 1.3.
Утверждение 1.3. Параметр t0 должен выбираться таким образом,
чтобы шары радиуса t0 с центрами в кодовых словах не пересекались.
Например, в предыдущем примере выбирается t0 ≤ 1.
Выбор t0 основан на следующей теореме.
Теорема 1.1. Пусть имеется код с минимальным расстоянием d,
и построены шары радиуса t0 с центром в кодовых словах.
19
Таблица 1.3
Алгоритм декодирования в шаре радиуса 1
Y
d(a1, y)
d(a2, y)
0000
0
4
a1
0001
1
3
a1
0010
1
3
a1
0011
2
2
Отказ
0100
1
3
a1
0101
2
2
Отказ
0110
2
2
Отказ
0111
3
1
a2
1000
1
3
a1
1001
2
2
Отказ
1010
2
2
Отказ
1011
3
1
a2
Решение декодера
1100
2
2
Отказ
1101
3
1
a2
1110
3
1
a2
1111
4
0
a2
Множество
кодовых
слов
a1
Множество
последовательностей
на выходе канала
a1
t0
...
a2
a2
Отказ
Рис. 1.11. Декодирование в шаре радиуса 1
20
t0
1. Шары не пересекаются тогда и только тогда, когда t0 < d/2
или t0 ≤ (d – 1)/2.
2. Шары обязательно пересекаются, когда t0 ≥ d/2 или t0 > (d – 1)/2.
Доказательство 1. Будем доказывать от противного. Предположим, что два шара с центрами в кодовых словах ai и aj радиуса t0
пересекаются, т. е. имеют некоторую общую точку z. Следовательно, d(ai, z) ≤ t0 и d(aj, z) ≤ t0. Тогда, согласно неравенству треугольника имеем: d(ai, aj) ≤ d(ai, z) + d(aj, z) ≤ 2t0 < d.
А это противоречит предположению, что d – минимальное расстояние кода. Следовательно, наше допущение неверно, и при t0 ≤
(d–1)/2 шары не пересекаются. Первая часть теоремы доказана.
Доказательство 2. Пусть имеются два кодовых слова ai, aj и выбрано некоторое значение t0, такое, что шары с центрами в кодовых
словах ai и aj радиуса t0 пересекаются. По доказательству первой
части теоремы, если шары пересекаются, то d(ai, aj) ≤ 2t0. С другой
стороны, расстояние между любыми кодовыми словами не меньше
минимального расстояния кода, d(ai, aj) ≥ d. Имеем систему не-
ìd(ai , aj ) £ 2t0
ï
равенств: ï
Складывая левые и правые части нераí
ï
ïî-d(ai , aj ) £-d.
венств, получим 2t0 – d ≥ 0. Откуда t0 ≥ d/2. Вторая часть теоремы
доказана.
Проиллюстрируем теорему с помощью рис. 1.12.
Пусть имеется код с минимальным расстоянием d. В этом коде
обязательно найдутся два кодовых слова ai и aj такие, что d(ai, aj) = d.
Следствие. Код с минимальным расстоянием d исправляет ошибки кратности t ≤ (d–1)/2. В этом случае любая ошибка оставляет
переданное слово в своей решающей области.
Теорема 1.1 дает ответ на первый вопрос, сформулированный
для алгоритма декодирования в шаре. При t0 ≤ (d–1)/2 шары не
пересекаются, и решение принимается однозначным образом (если
di0 ≤ t0, то минимум достигается на одном кодовом слове).
Для алгоритма декодирования в шаре в зависимости от того, каким выбран радиус шара, меняется количество обнаруживаемых
и исправляемых ошибок. При этом согласно предыдущей теореме
радиус шара может меняться от 0 до (d–1)/2.
Пример 1.16. Рассмотрим код с минимальным расстоянием d = 4.
Значит, в коде всегда найдутся два кодовых слова ai и aj, расстояние Хэмминга между которыми равно 4. Если используется алгоритм декодирования в шаре, то в зависимости от параметра t0 (радиус шара), код позволяет исправить и обнаружить определенное
21
a1
t0
a2
t0
. . .
t0
d
ai
aj
t0
. . .
t0
aM
Рис. 1.12. Минимальное расстояние кода
число ошибок. Например, при t0 = 0, код не может исправить ни
одной ошибки, но может обнаружить 1,2 или 3 ошибки (рис. 1.13).
Если t0 = 1, то код может исправить одну ошибку и обнаружить
две ошибки (рис. 1.14).
Число исправляемых t и обнаруживаемых ошибок f при t0 ≤ 1 и
d = 4 приведено в табл. 1.4.
3 ошибки
1
2
ai
aj
d (ai , aj ) = 4
t0 = 0
Рис. 1.13. Декодирование в шаре радиуса 0
22
2 ошибки
1
ai
aj
d(ai , aj ) = 4
Рис. 1.14. Декодирование в шаре радиуса 1
Таблица 1.4
Число исправляемых и обнаруживаемых ошибок при d = 4
t0
Число исправляемых ошибок
Число обнаруживаемых ошибок
0
1
0
1
1,2,3
2
Пример 1.17. Пусть минимальное расстояние кода d = 3. Если
t0 = 1, то код может исправить одну ошибку, но не обнаруживает ни
одной ошибки (рис. 1.15).
В табл. 1.5 приведено число исправляемых t и обнаруживаемых
ошибок f при t0 ≤ 1 и d = 3.
Для того чтобы обобщить примеры 1.16 и 1.17 на общий случай и выяснить, сколько ошибок можно исправить и обнаружить,
рассмотрим различные ситуации, которые могут происходить при
работе алгоритма декодирования в шаре радиусом t0 ≤ (d–1)/2 в
предположении, что по каналу передавалось некоторое кодовое
слово ai.
1 ошибка
ai
aj
d (a i , a j ) = 3
Рис. 1.15. Декодирование в шаре радиуса 1
23
Таблица 1.5
Число исправляемых и обнаруживаемых ошибок при d = 3
t0
Число исправляемых ошибок
Число обнаруживаемых ошибок
0
1
0
1
1,2
–
а)
б)
t
ai 0
d
aj
t0
ai
t0
y1
aj
d
t0
y2
Рис. 1.16. Число ошибок меньше, чем d–t0
а)
t
ai 0
б)
d
y3
aj
t0
t
ai 0
d
aj
t0
y3
Рис. 1.17. Число ошибок больше или равно, чем d–t0
Ситуация 1. Число ошибок e≤ t0 (рис. 1.16, а), следовательно,
d(ai, y1) ≤ t0. Поскольку при этом y1∈St0(ai), то декодер выносит
решение, что передавалось кодовое слово ai (верное решение), т. е.
если число ошибок в канале e≤ t0, то декодер ошибки исправляет.
Ситуация 2. Число ошибок e > t0, но e < d – t0 (рис. 1.16, б), следовательно, t0 < d(ai, y2) < d – t0. Поскольку при этом не найдется aj
такое, что y2∈St0(aj), то декодер выносит решение об обнаружении
ошибки (верное решение).
Ситуация 3. Число ошибок e ≥ d–t0 (рис. 1.17). В этом случае, в
зависимости от того, какое кодовое слово передавалось и в каких
разрядах произошли ошибки, возможны два варианта:
а) декодер выносит неверное решение, что передавалось кодовое слово aj (y3∈St0(aj)), т. е. произошла ошибка декодирования
(рис. 1.17, а);
б) декодер выносит решение об обнаружении ошибки (y3 ∉ St0(aj))
(рис. 1.17, б).
Еще раз отметим, что, так как на приемной стороне неизвестно
передаваемое слово, то декодер не может различить ситуацию 1 и
24
ситуацию 3,а. Именно поэтому в ситуации 3,а декодер выносит неверное решение.
На основе рассмотренных ситуаций можно сделать следующий
вывод.
При использовании алгоритма декодирования в шаре, число обнаруженных f и исправляемых ошибок t, и минимальное расстояние кода d, связаны следующими соотношениями: t + f ≤ d–1, t ≤
(d–1)/2 и f > t, если декодер может обнаруживать какие-то ошибки.
1.11. Анализ алгоритма декодирования
по минимуму расстояния Хэмминга
Теперь после детального анализа алгоритма декодирования в
шаре можно ответить на следующий вопрос для алгоритма декодирования по минимуму расстояния Хэмминга.
Какое максимальное количество ошибок можно исправить с помощью заданного алгоритма, причем вне зависимости от того, в каких разрядах они произошли, и какое кодовое слово передавалось?
Утверждение 1.4. Для алгоритма декодирования по минимуму
расстояния Хэмминга кода с минимальным расстоянием d для любого кодового слова ai в решающую область входит шар с центром в
кодовом слове ai и радиусом (d–1)/2.
Утверждение приводится без доказательства, которое можно
найти в [4]. Для иллюстрации утверждения рассмотрим следующий пример.
Решающая область для a1
Решающая область для a2
1100
1110
1000
0100
0001
0010
0101
0110
1001
1101
0000
1010 0011
1111
1011
0111
Рис. 1.18. Решающие области для кодовых слов
25
Пример 1.18. Пусть a1 = (0000), a2 = (1111) и d = 4. При этом на
выходе декодера могут появиться 16 различных последовательностей. Образуем решающие области для кодовых слов a1 и a2, в которые входят все слова шара радиуса 1.
Y1‘ = {(0000), (0001), (0010), (0100), (1000)}. Y2 = {(1111), (1110),
(1101), (1011), (0111)}. Для последовательностей, которые отличаются от кодовых слов на двух позициях, декодер принимает решение
в пользу кодового слова с наименьшим номером. Тогда окончательный вид решающей области для слова a1: Y1 = {(0000), (0001), (0010),
(0100), (1000), (0011), (0101), (0110), (1001), (1010), (1100)} (рис. 1.18).
В этом примере исправляются любые однократные ошибки вне зависимости от того, какое кодовое слово передается. Если передается
кодовое слово a1, то удается исправить также двукратные ошибки.
Из утверждения следует, что любые ошибки, число которых
t £ êë(d -1) / 2úû , могут быть исправлены.
1.12. Двоичный симметричный канал без памяти
Рассмотрим канал связи (рис. 1.19), где X = {0,1} – входной алфавит канала, а Y = {0,1} – выходной алфавит канала. Такой канал
называют двоичным каналом.
Если на вход канала поступает символ “0”, то при передаче по
каналу на выходе может появиться символ “1” (рис. 1.20). Такое
событие будем называть ошибкой. Вероятность такого события
обозначим через p (Pr{y = 1|x = 0} = p). При отсутствии ошибки на
X={0 ,1 }
Y ={0 ,1 }
Канал
Рис. 1.19. Канал связи
1–p
0
0
p
1
Рис. 1.20. Передача символа “0” по каналу связи
26
выходе канала будет символ “0”. Вероятность такого события: 1–p
(Pr{y = 0|x = 0} = 1–p).
Подобные события можно рассмотреть и для передачи символа 1. При этом возможны следующие события с вероятностями:
Pr{y = 0|x = 1} = p и Pr{y = 1|x = 1} = 1–p. В результате получим двоичный симметричный канал (рис. 1.21).
Поскольку вероятность ошибки в канале p одинакова для всех
символов, то канал называется стационарным[1].
Пусть на вход канала поступает некоторое слово x∈ Xn, а на выходе канала формируется последовательность y∈Yn. Пусть n = 4.
Если выходной символ yi зависит только от соответствующего входного символа xi и не зависит ни от каких других символов на входе
и выходе канала в другие моменты времени (рис. 1.22), то канал
называется каналом без памяти.
Пример 1.19. Пусть x = (0110) – последовательность на входе канала, а y = (1100) – выходная последовательность. p(y, x) – вероятность события {на выходе канала появляется последовательность y
при условии, что на вход канала поступает последовательность x}.
Для канала без памяти вероятность p(y, x) определяется как произведение вероятностей отдельных символов:
p(y, x) = p(1–p)p(1–p) = p2(1–p)2.
1–p
0
0
p
p
1–p
1
1
Рис. 1.21. Двоичный симметричный канал
x =( * | 1 | * | *)
x =( * | 1 | * | *)
y =( * | 1 | * | *)
y =( * | 0 | * | *)
Вероятность
1–p
p
* – передается произвольный символ
Рис. 1.22. Канал без памяти
27
t
n–t
E ... E
...
E – ошибочный символ
n
Рис. 1.23. t ошибок на старших позициях
Ошибки
i
1
E
...
...
E
t –1
t
E
E
n
Рис. 1.24. t ошибок на произвольных позициях
Теперь обобщим введенные понятия на произвольную длину
кода. Пусть на старших t позициях последовательности длины
n произошли ошибки (рис. 1.23). Тогда вероятность такого события – pt (1 - p)(n-t) .
Если рассмотреть другую ситуацию и предположить, что t ошибок возникнут на произвольных позициях (рис. 1.24), то вероятность такой ситуации также будет pt (1 - p)(n-t) , так как канал стационарный.
Если обобщить сказанное на все ситуации, то вероятность события {в канале произошло t ошибок на n позициях} можно записать
следующим образом:
(2)
Pr{t,n} = Cnt pt (1 - p)(n-t) , где pt (1 - p)(n-t) – вероятность конкретной ситуации; Cnt – число
таких ситуаций.
1.13. Вычисление оценки вероятности
ошибки декодирования для алгоритма декодирования
по минимуму расстояния Хэмминга
Под ошибкой декодирования будем понимать такое событие,
когда на вход канала поступало одно кодовое слово, а декодер принимает решение, что передавалось какое-то другое слово. Вероят28
A
B
Множество, в котором декодер
не исправляет ошибки
Рис. 1.25. Множества A и B
ность этого события обозначим: Pe. Введем в рассмотрение следующие два события:
А = {в канале произошли такие ошибки, которые приводят к
ошибке декодирования}. Pe ≜ Pr{A}.
B = {число ошибок больше чем t}, где t = (d – 1)/2; d – минимальное расстояние кода. Напомним, что если t ≤ (d – 1)/2, то все
ошибки исправляются. Событиям A и B соответствуют множества
A и B (рис. 1.25).
Из сопоставления множеств A и B следует, что: Pe = Pr{A} ≤
Pr{B}. Отметим, что во множестве B\A все ошибки исправляются.
Событие B можно представить как объединение независимых событий:
B = {число ошибок – t + 1} U {число ошибок – t + 2} U … U {число
ошибок – n}.
Для вычисления вероятности события B, воспользуемся формулой (2):
Pr{B} = Pr{число ошибок t + 1} + Pr{число ошибок t + 2}… +
Pr{число ошибок n} = Cnt+1 pt+1 (1 - p)n-t-1 +  + Cnn pn (1 - p)0 =
n
å
i=t+1
Cni pi (1 - p)n-i . И, наконец, получаем верхнюю границу для
вероятности ошибки декодирования, Pe £
n
å
i=t+1
Cni pi (1 - p)n-i .
Полученное выражение содержит Cni – биномиальные коэффициенты, которые несложно рассчитать при небольших значениях
n. При больших значениях n формулу удобно преобразовать к следующему виду:
t
Pe £ 1 - å Cni pi (1 - p)n-i .
i=0
29
1.14. Вычисление оценки ошибки декодирования
для алгоритма декодирования в шаре
Рассмотрим алгоритм декодирования в шаре с минимальным
расстоянием кода d и радиусом шара t0 ≤ (d – 1)/2.
Введем в рассмотрение два события:
А = {в канале произошли такие ошибки, которые приводят к
ошибке декодирования},
B = {число ошибок ≥ d – t0}. Pe = Pr{A} ≤ Pr{B}. Событиям A и B соответствуют множества A и B (рис. 1.26). Напомним, что если число ошибок < d – t0, то они или исправляются, или обнаруживаются.
Отметим, что во множестве B\A все ошибки обнаруживаются.
t
0
d
t
0
A
B
Рис. 1.26. Множества A и B
Повторяя такие же рассуждения, как для алгоритма декодирования по минимуму расстояния Хэмминга, получаем:
Pe £
n
å
i=d-t0
Cni pi (1 - p)n-i = 1 -
d-t0 -1
å
i=0
Cni pi (1 - p)n-i .
1.15. Вычисление оценки вероятности отказа
от декодирования для алгоритма декодирования в шаре
Под отказом от декодирования будем понимать такое событие,
когда декодер обнаруживает ошибку. Вероятность этого события
обозначим Po.
Введем в рассмотрение следующие два события:
С = {в канале произошли ошибки, которые привели к тому, что
декодер сформировал сигнал обнаружения ошибки},
D = {t0 < число ошибок < d – t0} (все ошибки обнаруживаются),
где t0 – радиус шара, в котором мы декодируем. Событиям C и D
соответствуют множества C и D (рис. 1.27). Напомним, что число
ошибок £ t0 декодер исправляет. Отметим, что множество C\D со30
C
D
Рис. 1.27. Множества C и D
ответствует событию {ошибки, которые обнаруживаются, когда
число ошибок ³ d – t0}.
Po = Pr{C} ≥ Pr{D}. Pr{D} =
d-t0 -1
å
i=t0 +1
Cni pi (1 - p)n-i (нижняя граница
для вероятности отказа от декодирования).
Задания на самостоятельную работу.
1. Для кода, состоящего из двух слов a1 = (0000) и a2 = (1111) и
для всех допустимых значений радиуса шара, рассчитать точные
значения вероятности ошибки декодирования и вероятности отказа от декодирования и сравнить с полученными ранее оценками.
2. Для кода, состоящего из двух слов a1 = (0000) и a2 = (1111),
рассчитать точное значение вероятности ошибки декодирования
для алгоритма декодирования по минимуму расстояния Хэмминга
и сравнить с полученной оценкой.
1.16. Границы для числа кодовых слов. Граница Хэмминга
Сформулируем следующую задачу. Пусть имеется некоторый
код A = {a1,a2, …, aM} с минимальным расстоянием d и длиной кода
n. Необходимо определить: какое максимальное число кодовых
слов M может содержать этот код?
Пусть имеется множество всех последовательностей Xn. Ограничимся рассмотрением двоичного кода (|Xn|= 2n). A∈Xn. Построим шары радиуса t = (d – 1)/2 с центрами в кодовых словах
t
(рис. 1.28). Объем каждого шара: Vt = å Cni (см. формулу (1)).
i=0
31
t
2
a1
n
t
a2
. . .
t
aM
Рис. 1.28. Покрытие пространства
из 2n последовательностей шарами радиуса t
Суммарный объем всех шаров равен M × Vt. По ранее доказанной
теореме 1.1 шары не пересекаются. Следовательно, M ≤ 2n/Vt . Откуда M £
2n
t
å
i=0
. Полученную верхнюю оценку называют границей
Cni
Хэмминга (границей плотной упаковки).
Границу Хэмминга следует трактовать следующим образом
(рис. 1.29).
Пусть n и d – фиксированы. Отложим на числовой оси точки, соответствующие возможному числу слов в коде. Тогда не существует кода, число слов в котором больше M, где M соответствует границе Хэмминга. Если число слов в коде равно M, то этот код, при
заданных n и d, имеет максимальный объем. Такой код называют
совершенным (плотно упакованным). При этом шары заполняют
Коды не существуют
Число, вычисленное
по границе Хэмминга
Рис. 1.29. Граница Хэмминга
32
пространство Xn максимально плотно так, что общее число точек
во всех шарах равно|Xn|.
Пример 1.20. Пусть требуется построить код, который имеет длину n = 7, минимальное расстояние d = 3, число кодовых слов M = 20.
Для ответа на этот вопрос необходимо определить границу Хэмминга.
27
27
128
M£ 1
= 0
=
= 16.
1
C7 + C7 1 + 7
i
å C7
i=0
Вывод: Данная задача не имеет решения, так как не выполняется условие М ≤ 16.
Пример 1.21. Рассмотрим код, состоящий из двух слов a1 = (000),
a2 = (111). Этот код имеет длину n = 3 и минимальное расстояние
d = 3. Определим границу Хэмминга.
23
23
8
M£ 1
= 0
= = 2.
1
4
C +C
å C3i 3 3
i=0
Следовательно, это код является совершенным.
1.17. Граница Варшамова–Гилберта
Эта граница указывает, какие коды обязательно существуют
(рис. 1.30).
Опишем алгоритм, с помощью которого может быть построен
код, лежащий на границе Варшамова – Гилберта или выше этой
границы, но обязательно не выше границы Хэмминга.
Алгоритм. 
1. Выберем первую последовательность из 2n произвольным образом. Будем считать эту последовательность кодовым словом a1,
для которого построим шар Sd–1(a1) с центром в этом слове и радиусом d–1. Внутри шара не может быть других кодовых слов, так как
минимальное расстояние кода равно d.
2. Если вне этого шара в 2n имеется еще хотя бы одна последовательность, то произвольным образом выбираем второе слово a2
из множества 2n/ Sd–1(a1), т. е. a2∈2n/ Sd–1(a1) и построим шар
Sd–1(a2) радиуса d–1.
33
3. Исключим из 2n точки, лежащие в объединении обоих шаров,
т. е. 2n/ (Sd–1(a1) U Sd–1(a2)). Если полученное множество не будет
пустым, то произвольным образом выбираем слово a3∈2n/ (Sd–1(a1)
U Sd–1(a2)) и т. д.
Алгоритм завершается на шаге M, если выполняется условие
M
2n /  Sd-1 (ai ) = Æ , т. е. это множество оказывается пустым.
i=1
После шага M, выбраны М кодовых слов: a1, a2, …, aM, (рис. 1.31),
причем каждое слово оказывается на расстоянии не меньшем чем d
от всех других выбранных слов. Поскольку шары могут пересекаться, т. е. каждая из 2n последовательностей может входить более,
чем в один шар, то справедливо следующее неравенство: 2n ≤ M ×  
Vd–1. Окончательно, для случая двоичного кода, получаем, что:
M ≥2n/Vd–1.
M³d
2n
–1
å
i=0
.
Cni
Пример 1.22. Вычислим границу Варшамова–Гилберта для кода
с параметрами n = 7 и d = 3.
27
27
27
128
M³ 2
= 0
=
=
= 4,414.
1
2
C7 + C7 + C7 1 + 7 + 21 29
i
å C7
i=0
Отсюда можно сделать вывод, что обязательно существует код
с 4 кодовыми словами. По границе Варшамова–Гилберта о существовании кода, который имеет более 4 слов, ничего определенного
сказать нельзя.
Граница Хэмминга для кода с этими же параметрами n = 7 и
d = 3 была вычислена в примере 1.20 и равнялась 16. Окончательно
Коды существуют
Коды в этой области
могут существовать
Граница
Варшамова–
Гилберта
Коды не существуют
Граница
Хэмминга
Рис. 1.30. Границы существования кодов
34
2n
Шары могут пересекаться
d–1
a2
. . .
a1
d–1
aM
d–1
Рис. 1.31. Покрытие пространства
из 2n последовательностей шарами радиуса t
можно сделать вывод, что код с 4 кодовыми словами точно существует, и могут существовать коды с числом кодовых слов в диапазоне от 5 до 16. Заметим, что далее при изучении линейных кодов
мы построим конкретный код с параметрами n = 7 и d = 3, который
содержит точно 16 слов. Этот код является совершенным кодом.
1.18. Выводы по первому разделу
В первом разделе было введено понятие блокового кода, определены параметры кода и введены соответствующие обозначения:
длина кода n, число кодовых слов M (см. подразд. 1.3), скорость
кода R (см. подразд. 1.4) и минимальное расстояние d (см. подразд. 1.9).
Описаны подходы к кодированию и декодирования блокового кода.
Декодирование на основе решающих областей (см. подразд. 1.5) –
это подход, на основе которого базируются другие походы к декодированию блоковых кодов. Описываются и анализируются конкретные алгоритмы декодирования – декодирование по минимуму расстояния Хемминга (см. подразд. 1.8) и декодирование в шаре (см.
подразд. 1.9).
35
Проведен анализ алгоритмов декодирования и показано, что корректирующая способность кода в первую очередь определяется минимальным расстоянием кода d. Доказаны следующие утверждения.
Алгоритм декодирования по минимуму расстояния Хемминга
гарантирует исправление t ошибок, где t ≤ d/2 (см. подразд. 1.11).
Свойства алгоритма декодирования в шаре (см. подразд. 1.10)
зависят от параметра алгоритма t0 (радиус шара). Параметр t0 может изменяться в диапазоне 0 до (d – 1)/2. При t0 = 0, алгоритм
не может исправлять ошибки (т. е. число исправляемых ошибок
t = 0), но гарантирует обнаружение любых f ошибок, где f ≤ d–1.
В подразд. 1.10 указано, как при t0 > 0 связаны между собой значения t, f и d.
Следует отметить, что в реальных системах алгоритмы кодирования и декодирования, рассмотренные в этом разделе, практически не используются. Основная причина состоит в сложности реализации этих алгоритмов для кодов с большим числом кодовых
слов. Как кодер, так и декодер, должны хранить весь список кодовых слов – большие затраты памяти. Кроме того, при декодировании требуется сравнить принятую последовательность со всеми
кодовыми словами – большие временные затраты.
В первом разделе введена в рассмотрение простейшая модель канала связи – двоичный симметричный канал без памяти (см. подразд. 1.12). Применительно к этой модели канала для рассмотренных алгоритмов декодирования описана методика оценки вероятности ошибки декодирования. Следует отметить, что данная методика может быть использована для оценки вероятности ошибки
декодирования и при использовании алгоритмов декодирования,
которые будут рассмотрены в последующих разделах.
В завершении первого раздела рассмотрены границы для числа
кодовых слов в коде (см. подразд. 1.16 и 1.17).
36
2. ЛИНЕЙНЫЕ КОДЫ
Для того чтобы строить коды и быстрые алгоритмы кодирования и декодирования, не связанные с перебором, необходим специальный математический аппарат, к изучению элементов которого
мы и приступаем.
2.1. Конечные поля
Конечным полем называется множество элементов X, где|X|= q –
мощность множества, для элементов которого определены две операции: сложение и умножение. При этом выполняются следующие
аксиомы:
1. Замкнутость относительно операций сложения и умножения:
∀a,b∈X, a + b∈X, a × b∈X.
2. Операции сложения и умножения коммутативны: a + b = b +
a, a × b = b × a, ассоциативны: (a + b) + c = a + (b + c), (a × b) × c =
a × (b × c) и дистрибутивны: (a + b) × c = a × c + b × c.
3. В поле существует единственный нулевой элемент e0∈X:
∀a∈X a + e0 = a, a × e0 = e0.
4. В поле существует единственный единичный элемент e1∈X:
∀a∈X a × e1 = a.
5. Для любого ∀a∈X, существует единственный противоположный элемент ∀x∈X: a + x = e0. Его обозначают –a.
6. Для любого ∀a∈X, кроме a = 0, существует единственный обратный элемент ∀x∈X: a × x = e1. Его обозначают a–1.
Пример 2.1. Пусть X = {0,1,2}.|X|= 3. Элементы поля в данном
примере рассматриваются как числа, над которыми определены
операции сложения и умножения по модулю 3. Проверим, является ли это множество конечным полем?
Для проверки аксиомы 1 построим таблицу операций сложения
и умножения для множества из 3 элементов (табл. 2.1).
Таблица 2.1
Замкнутость относительно операций сложения и умножения
для множества из 3 элементов
+
0
1
2
0
0
1
2
1
1
2
0
2
2
0
1
×
0
1
2
0
0
0
0
1
0
1
2
2
0
2
1
37
Нулевой элемент e0 = 0.
Единичный элемент e1 = 1.
Противоположный и обратный элементы приведены в табл. 2.2.
Поскольку все аксиомы для множества X выполняются, то множество X является конечным полем.
Пример 2.2. Пусть X = {0,1,2,3}.|X|= 4. Как и в предыдущем примере, элементы поля рассматриваются как числа, над которыми
определены операции сложения и умножения по модулю 4. Проверим, является ли это множество конечным полем?
Для проверки аксиомы 1 построим таблицу операций сложения
и умножения для множества из 4 элементов (табл. 2.3).
Нулевой элемент e0 = 0.
Единичный элемент e1 = 1.
Противоположный и обратный элементы представлены в табл. 2.4.
Таблица 2.2
Противоположный и обратный элементы
для множества из 3 элементов
0
1
2
–a
0
2
1
a–1
–
1
2
Таблица 2.3
Замкнутость относительно операций сложения и умножения
для множества из 4 элементов
+
0
1
2
3
0
0
1
2
3
1
1
2
3
0
2
2
3
0
1
×
0
1
2
3
3
3
0
1
2
0
0
0
0
0
1
0
1
2
3
2
0
2
0
2
3
0
3
2
1
Таблица 2.4
Противоположный и обратный элементы
для множества из 4 элементов
0
1
2
3
38
–a
0
3
2
1
a–1
–
1
–
3
Таблица 2.5
Операции сложения и умножения
для расширенного поля Галуа из 4 элементов
+
0
1
2
3
0
0
1
2
3
1
1
0
3
2
2
2
3
0
1
3
3
2
1
0
×
0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
3
1
3
0
3
1
2
Не выполняется аксиома 6. Для элемента 2 нет обратного элемента. Следовательно, X не является конечным полем. Рассмотренный пример можно обобщить, используя утверждение из теории конечных полей, которое здесь приводится без доказательства.
Теорема 2.1. Если имеется множество Х = {0, 1, …, q–1} и заданы
операции по модулю q, то данный объект является полем тогда и
только тогда, когда q – простое число (т.е. делится только на 1 и на
себя: 1, 2, 3, 5, 7, …).
Поля, описанные в этой теореме, называются простыми полями Галуа и обозначаются как: GF(q). Кроме того, существуют так
называемые расширенные поля Галуа, которые обозначаются:
GF(qk). Например, существует поле из 4 элементов, которое обозначается GF(22) и для этого поля операции задаются не по модулю 4,
а по другим более сложным правилам. Операции сложения и умножения для этого поля представлены в табл. 2.5.
Задача. Самостоятельно проверить, что все аксиомы для этого
поля выполняются.
В дальнейшем ограничимся рассмотрением только простых полей [5,7,9,10].
2.2. Линейные пространства и подпространства
Пусть имеется некоторое поле GF(q). Введем в рассмотрение векторы длины n, с элементами из этого поля:
x = (x1,x2, …, xn), где xi∈GF(q). При этом сами элементы поля
Галуа будем называть скалярами.
Зададим следующие операции для векторов:
1. Сложение векторов a и b:
a = (a1,a2, …, an), b = (b1,b2, …, bn),
c = b + a = (a1 + b1, a2 + b2, …, an + bn).
39
Пример 2.3. Пусть имеется поле GF(3) и вектора a = (0121),
b = (1211). Тогда, c = a + b = (0 + 1,1 + 2,2 + 1,1 + 1) = (1002).
2. Умножение вектора a на скаляр α∈GF(q).
c = αa = (αa1, αa2, …, αan).
Пример 2.4. Пусть имеется поле GF(3), вектор a = (0122) и скаляр α = 2. Тогда c = αa = (0211).
Определение. Пусть имеется поле GF(q) и множество векторов с
элементами из этого поля:
A = {a1,a2, …, aM}. Данное множество называется линейным
пространством, если оно является замкнутым относительно операций сложения векторов и умножения вектора на скаляр:
а) ∀ai,aj∈A: ai + aj∈A;
б) ∀ai∈A, α∈GF(q): αai∈A.
Пример 2.5. Рассмотрим двоичное поле GF(2) и множество векторов длины 3, содержащих нечетное число единиц. Выясним, является ли это множество векторов линейным пространством?
Множество А состоит из следующих векторов: a1 = (001), a2 = (010),
a3 = (100), a4 = (111). Оно не является линейным пространством,
так как a1 + a2 = (011) ∉ A.
Теперь, рассмотрим множество векторов длины 3, которые
содержат четное число единиц: a1 = (000), a2 = (011), a3 = (110),
a4 = (101). Данное множество векторов является линейным пространством.
Обобщая предыдущий пример, легко доказать, что справедливо
следующее утверждение.
Утверждение 2.1. В любом линейном пространстве обязательно
должен быть вектор, состоящий из всех нулей (нулевых элементов
поля). Доказательство очевидно, так как в поле Галуа обязательно
есть нулевой элемент, и умножение этого скаляра на любой вектор
даст в результате вектор, состоящий из всех нулей.
Задача. Самостоятельно рассмотреть, какие блоковые коды
(коды в табл. 1.1 и табл. 1.2 и примере 1.14), которые были ранее
рассмотрены в разд. 1, являются линейными пространствами. При
этом предположим, что кодовые слова являются векторами с коэффициентами из поля GF(2).
Определение. Пусть имеется некоторое множество векторов
A = {a1,a2, …, aM}, образующих линейное пространство. Некоторое подмножество B⊂A называется линейным подпространством,
если это подмножество соответствует определению линейного про40
странства, т. е. оно является замкнутым, относительно операций
сложения векторов и умножения вектора на скаляр.
Пример 2.6. Пусть имеем множество векторов A = {(000),(011),
(110),(101)} с элементами из поля GF(2). Найдем какое-нибудь линейное подпространство этого линейного пространства. Например,
B = {(000), (011)}.
Замечание. B = {(000), (011), (110)} не может быть линейным
подпространством, так как (011) + (110) = (101) ∉ В.
2.3. Линейно зависимые и линейно независимые векторы
Определение. Линейной комбинацией векторов a1,a2, …, ak называется вектор y = α1a1 + α2a2 + … + αkak. Из определения следует, что для любых a1,a2, …, ak∈A и любых α1,α2, …, αk∈GF(q) вектор y∈A, т. е. входит в линейное пространство.
Определение. Линейной оболочкой векторов L(a1,a2, …, ak) называются всевозможные линейные комбинации этих векторов
L(a1,a2, …, ak) = {y = α1a1 + α2a2 + … + αkak}.
Пример 2.7. Пусть имеются два вектора: a1 = (011), a2 = (110) и
поле GF(2). Найдем всевозможные линейные комбинации.
y1 = 0 × (011) + 0 × (110) = (000), y2 = 0 × (011) + 1 × (110) = (110),
y3 = 1 × (011) + 0 × (110) = (011), y4 = 1 × (011) + 1 × (110) = (101).
Пример 2.8. Найдем всевозможные линейные комбинации из
следующих двух векторов: a1 = (000), a2 = (110) в поле GF(2).
y1 = 0 × (000) + 0 × (110) = (000), y2 = 0 × (000) + 1 × (110) = (110),
y3 = 1 × (000) + 0 × (110) = (000), y4 = 1 × (000) + 1 × (110) = (110).
Определение. Векторы являются линейно независимыми, если
равенство α1a1 + α2a2 + … + αkak = 0 справедливо тогда и только
тогда, когда все скалярные величины равны нулю: α1 = α2 = … =
αk = 0, где 0 – вектор, состоящий из всех нулей. Если предыдущее
равенство справедливо, даже в тех случаях, когда есть отличные от
нуля коэффициенты, то векторы являются линейно зависимыми.
В соответствии с определением векторы (011), (110) из примера 2.7 – линейно независимые, а векторы (000), (110) из примера
2.8 – линейно зависимые. Действительно равенство: α1 × (011) +
α2 × (110) = (000) = 0 справедливо только, если α1 = α2 = 0. В свою
очередь, векторы (000), (110) – линейно зависимы: α1 × (000) +
α2 × (110) = (000) = 0, если α1 = 1, α2 = 0.
Задача. Самостоятельно привести пример трех линейно зависимых векторов и трех линейно независимых векторов, где n = 3.
41
При этом при выборе векторов исключить из рассмотрения нулевой
вектор. Убедиться, что если векторы линейно зависимы, то один
из этих векторов можно представить в виде линейной комбинации
других векторов. Привести пример, как из трех линейно зависимых векторов, один вектор можно получить из линейной комбинации других векторов.
Теорема 2.2. Пусть a1,a2, …, ak – линейно независимые векторы.
Тогда все линейные комбинации векторов, входящие в линейную
оболочку L(a1,a2, …, ak) различны.
Доказательство от противного. Предположим, что при двух различных наборах коэффициентов α1,α2, …, αk и β1, β2, …, βk имеет
место равенство α1a1 + α2a2 + … + αkak = β1a1 + β2a2 + … + βkak.
Прибавляя к обеим частям равенства вектор –(α1a1 + α2a2 + … +
αkak), где α – обратный элемент по сложению, для α получим:
0 = (β1–α1) a1 + (β2–α2) a2 + … + (βk–αk)ak. Поскольку наборы коэффициентов α и β различны, т. е. хотя бы для одного значения индекса i выполняется неравенство (βi–αi) ≠ 0. Следовательно, последнее равенство противоречит предположению о линейной независимости векторов. Тогда наше допущение неверно, и все линейные
комбинации векторов, входящие в линейную оболочку, различны.
Рассмотренный пример 2.7 иллюстрирует доказанную теорему.
2.4. Базис линейного пространства
Теорема 2.3. (О базисе линейного пространства и подпространства).
Пусть имеется поле GF(q). Рассмотрим множество Xn всех векторов длины n с коэффициентами из этого поля, которое образует
линейное пространство.
Выберем a1,a2, …, ak линейно независимые векторы. Тогда справедливы следующие утверждения.
Утверждение 2.2. Множество А (линейная оболочка векторов:
А = L(a1,a2, …, ak) является линейным подпространством пространства всех векторов длины n: A⊂Xn.
Утверждение 2.3. Число векторов, входящих в это подпространство, равно qk, т. е. мощность множества|A|= qk, где число k – размерность подпространства, а a1,a2, …, ak – базис подпространства.
Сначала проиллюстрируем теорему на следующем примере.
Пример 2.9. Пусть имеем поле GF(2) и рассмотрим всевозможные векторы длины 3 (n = 3 и |Xn|= 23 = 8). Выберем в качестве ба42
зиса векторы: (011), (110). Как было показано в примере 2.7, линейная оболочка (множество A = {(000),(011),(110),(101)}) является
линейным подпространством и мощность этого множества:|A|= 22.
Теперь перейдем к доказательству теоремы.
Доказательство утверждения 2.2.
1. Замкнутость множества относительно сложения векторов.
Пусть x∈A и x’∈A. Нужно показать, что x + x’∈A. Пусть α1,α2,
…, αk и β1, β2, …, βk – различные наборы коэффициентов из поля
GF(q). x и x’ – линейные комбинации векторов: x = α1a1 + α2a2 +
… + αkak, x’ = β1a1 + β2a2 + … + βkak.
Складываем эти два вектора: x + x’ = (α1 + β1)a1 + (α2 + β2)a2 +
… + (αk + βk)ak.
Поскольку ∀αi∈GF(q) и ∀βi∈GF(q), то (∀αi + ∀βi )∈GF(q). Следовательно, x + x’ – линейная комбинация векторов a1,a2, …, ak и x + x’∈A.
2. Замкнутость множества относительно умножения вектора на
скаляр.
Пусть x∈A и β∈GF(q). Нужно показать, что βx∈A. x – линейная
комбинация векторов a1,a2, …, ak: x = α1a1 + α2a2 + … + αkak. Умножим скаляр β на вектор x:
βx = (βα1) a1 + (βα2)a2 + … + (βαk)ak. Поскольку ∀(βαi )∈GF(q), то
βx – линейная комбинация векторов a1,a2, …, ak и, следовательно,
βx∈A. Следовательно, множество A – линейное подпространство и
A⊂Xn. Утверждение доказано.
Доказательство утверждения 2.3.
Ограничимся рассмотрением векторов с коэффициентами из
поля GF(2).
Любой вектор x∈A полностью задается набором коэффициентов
α1,α2, …, αk. Общее число различных наборов таких коэффициентов 2k. Поскольку векторы a1,a2, …, ak – линейно независимы, то
каждому набору коэффициентов соответствует свой вектор. Следовательно, общее количество векторов линейного подпространства
A равно 2k (см.пример 2.9). Утверждение доказано.
Определение. Базисом линейного пространства A называется
система линейно независимых векторов a1,a2, …, ak такая, что все
векторы линейного пространства A являются различными линейными комбинациями этих векторов. Векторы a1,a2, …, ak называют базисными векторами линейного пространства. Количество
базисных векторов k называется размерностью линейного пространства.
В примере 2.9 рассмотрено двумерное линейное пространство
над полем GF(2).
43
Следствие. В одном и том же линейном пространстве может существовать несколько различных систем базисных векторов, состоящих из k векторов. В k-мерном линейном пространстве любые
k линейно независимых векторов могут быть выбраны в качестве
базиса (доказать самостоятельно).
Пример 2.10. Выберем в качестве базиса векторы: (101), (110).
Эти векторы линейно независимые, так как их линейная оболочка
содержит различные векторы {(000),(101),(110),(101)} и образует
линейное пространство.
Задача. Привести пример линейного пространства, построенного из векторов длины 4: n = 4, k = 3.
2.5. Определение линейного кода
Определение. Пусть имеется некоторое поле GF(q) и линейное
пространство Xn, состоящее из всевозможных векторов длины n с
коэффициентами из поля GF(q). Линейным (n, k) q-ичным кодом,
называется линейное подпространство A⊂Xn размерности k.
Число n – длина кода. Число k называется числом информационных символов в коде. Число r = n – k называется числом проверочных символов в коде. При этом по теореме о базисе линейного
пространства мощность кода М = qk, а скорость кода при этом равна
R = logqM/n = k/n.
Пример 2.11. Сравним определение линейного кода с определением блокового кода. Пусть есть поле GF(2). Множество различных
векторов длины 3 над полем GF(2) – X3 = {(000),(001), …, (111)}.
Построим сначала блоковый код, состоящий из 4 слов (М = 4): В =
{любые последовательности из X3} = {(000),(001),(010),(100)}. Построим линейный (n, k) – код, где n = 3, k = 2, M = 2k = 4 слова.
Для этого выберем множество из 4 векторов длины n, которое является линейным подпространством. Например, множество: А =
{(000),(011),(110),(101)}. Следовательно, линейный код является
частным случаем блокового кода.
2.6. Порождающая матрица линейного кода
Определение. Пусть имеется линейный (n, k) код, т. е. имеется
линейное k – мерное подпространство A = {a1,a2, …, aM}, где M =
qk. Выберем базисные векторы этого линейного подпространства
44
(таких векторов будет k: {g1,g2, …, gk}) и составим из этих векторов
матрицу G, которая имеет k строк и n столбцов. Такую матрицу называют порождающей матрицей кода.
ég ù ég g g ù
ê 1 ú ê 11 12
1n ú
ê ú ê
ê g2 ú g21 g22  g2n úú
G = ê ú = êê
ú.
ê ú ê

ú
ê ú ê
ê g ú ëê gk1 gk2  gkn úûú
ëê k ûú
Построим порождающую матрицу для линейного кода из примера 2.11:
é101 ù
ú (k = 2,n = 3).
G=ê
ê011 ú
ë
û
2.7. Кодирование линейного кода
В общем случае, кодирование – это отображение множества сообщений на множество кодовых слов (см. разд. 1.3). Для линейного
кода это отображение задается следующим образом: m – кодируемое сообщение; G – порождающая матрица линейного кода;
a = mG – кодовое слово. Это соотношение представляет собой
правило кодирования, по которому сообщение m = (m1,m2, …, mk)
отображается в кодовое слово a = (a1,a2, …, an).
Пример 2.12. В предыдущем примере k = 2. Пусть I – множество
сообщений, а A – множество кодовых слов. Кодирование представлено на рис. 2.1.
A
I
00
(000)
01
(011)
10
(101)
11
(110)
Рис. 2.1. Кодирование для линейного кода
45
Формирование кодовых слов приведено на рис. 2.2.
Напомним правило умножения вектора на матрицу (Прил. 1).
Замечание. Если перемножаются векторы и матрицы с коэффициентами из поля GF(2), то операцию умножения можно выполнять по следующему правилу: результат умножения вектора на
матрицу, это сумма тех строк матрицы, которые соответствуют ненулевым компонентам вектора. Это – частный случай умножения.
Предыдущий пример также иллюстрирует, что такое информационные и проверочные символы кода. В нашем примере кодовое
слово имеет следующий вид (рис. 2.3), где r – число проверочных
символов, а k – число информационных символов.
Местоположение информационных символов зависит от вида
порождающей матрицы. В общем случае, чтобы информационные
символы были расположены в начале кодового слова, порождающая матрица должна иметь следующий вид (рис. 2.4). Такие ма(00)
101
011
= (000 )
(01)
101
011
= (011 )
(10)
101
011
= (101 )
(11)
101
011
= (110 )
Рис. 2.2. Получение кодовых слов для линейного кода
k =2
r=1
Информационные
символы
n= k+r=3
Проверочные
символы
Рис. 2.3. Структура кодового слова
10
...
00
01
...
00
G=
G2
.......
00
...
10
00
...
01
k
r
k
n
Рис. 2.4. Порождающая матрица в левой канонической форме
46
10
110
01
101
G=
Рис. 2.5. Порождающая матрица
трицы будем называть матрицами, представленными в левой канонической форме.
Если порождающая матрица G имеет левую каноническую форму, то кодирование называется систематическим. Для систематического кодирования:
a = mG = m[Ik|G2] = (m,mG2), где Ik – единичная матрица размерности k × k: т.е. кодовое слово содержит сообщение m = (m1,m2,
…, mk), которое размещается в левой части кодового слова.
Пример 2.13. Пусть имеется код из 4 кодовых слов: (00000),
(01101), (10110), (11011). n = 5, M = 4, M = 2k, k = 2. Это – линейный код. Построим порождающую матрицу этого кода в левой канонической форме (рис. 2.5). Для этого возьмем в качестве базисных векторов векторы (01101) и (10110), чтобы в левой части матрицы образовалась единичная подматрица.
2.8. Алгоритм работы кодера линейного кода
Кодер линейного кода хранит порождающую матрицу G и для
каждого кодируемого сообщения m формирует кодовое слово a по
следующему правилу: a = mG.
Определим объем памяти кодера для линейного кода. Он определяется размерностью порождающей матрицы и равен V = k × n.
Для двоичного кода M = 2k, и V = log2M × n. Напомним, что для
блокового кода (см. разд. 1.6) объем памяти кодера – V = M × n, так
как кодер должен хранить весь список кодовых слов.
2.9. Ортогональное дополнение линейного подпространства
Пусть имеется поле GF(q) и два вектора x и y длины n.
Определение. Скалярным произведением векторов, называется
скалярный элемент α, вычисленный следующим образом:
n
α = å xi yi . Скалярное произведение обозначается как (x,y).
i=1
47
Пример 2.14. Пусть имеются векторы: x = (1011), y = (1010) с коэффициентами из поля GF(2). Вычислим скалярное произведение
векторов (x,y) = 1 × 1 + 0 × 0 + 1 × 1 + 1 × 0 = 0.
Определение. Два вектора называются ортогональными, если
их скалярное произведение равно нулю.
Следовательно, векторы из предыдущего примера ортогональны.
Определение. Пусть имеются поле GF(q), множество всех последовательностей Xn с коэффициентами из этого поля и некоторое
линейное подпространство A⊂Xn. Множество, состоящее из векторов, ортогональных всем векторам из линейного подпространства
A, называется ортогональным дополнением линейного подпространства A. Обозначим это множество W:
W = {y∈Xn: ∀a∈A, (a,y) = 0}.
Пример 2.15. A = {(000),(110),(011),(101)} – линейное подпространство размерности 2. Построим ортогональное дополнение
этого линейного подпространства в поле GF(2). W = {(000),(111)}.
Каждый из этих векторов ортогонален всем векторам множества A.
Теорема 2.4. Пусть имеется множество всех последовательностей длины n: Xn, линейное подпространство A размерности
k A⊂Xn, и построено ортогональное дополнение W. Тогда справедливы следующие утверждения:
1) ортогональное дополнение W является линейным подпространством Xn, т. е. W⊂Xn;
2) размерность этого линейного подпространства (n–k), т. е.|W| =
qn–k.
Доказательство утверждения 1). Рассмотрим пару векторов y1 = (y11, y12, …, y1n) и y2 = (y21, y22, …, y2n) из множества
W. Из определения ортогонального дополнения W следует, что
(a,y1) = (a,y2) = 0 для любого вектора a∈A.
Тогда,
n
n
n
i=1
i=1
i=1
(a, y1 + y2 ) = å ai (y1i + y2i ) = å ai y1i + å ai y2i = (ay1 ) + (ay2 ) = 0.
Следовательно, вектор y1 + y2 также ортогонален любому вектору
n
n
i=1
i=1
a∈A, и вектор (y1 + y2)∈W. (a, α y1 ) = å ai αy1i = α å ai y1i = α(ay1 ) = 0,
где α∈GF(q). Следовательно, вектор αy1 также ортогонален любому
вектору a∈A, и вектор αy1 ∈W. Поскольку множество W замкнуто
относительно операций сложения векторов и умножения вектора
48
на скаляр, то оно является линейным подпространством (см. подразд. 2.2), что и требовалось доказать.
Доказательство утверждения 2) приведено в [4].
Проиллюстрируем справедливость теоремы на предыдущем
примере.
Мощность множества A:|A|= 4 = 2k. Следовательно, k = 2. Утверждение 1) W = {(000), (111)} – два составляющие его вектора,
образуют линейное подпространство.
Утверждение 2)|W|= 2. Следовательно, размерность 1, а по теореме 2.3: n – k = 3 – 2 = 1.
2.10. Проверочная матрица линейного кода
Определение. Пусть имеется линейный (n, k) код, т. е. имеется некоторое линейное подпространство. В соответствии с теоремой 2.4 ортогональное дополнение W этого подпространства будет
иметь размерность n – k = r. Выпишем базисные векторы ортогонального подпространства. Таких векторов будет r: {h1,h2, …, hr}.
Составим из этих векторов матрицу H (рис. 2.6). Эту матрицу называют проверочной матрицей кода. В матрице будет r – строк и
n – столбцов.
Пример 2.16. Имеем линейный (3,2) код A:
a1 = (000), a2 = (101), a3 = (011), a4 = (101).
Следовательно, g1 = (101), g2 = (011). Порождающая матрица
кода представлена на рис. 2.7.
Ортогональное дополнение является линейным подпространством.
W = {(000), (111)} – размерность этого подпространства: r = n – k = 1.
Следовательно, существует только один базисный вектор h1 =
(111), и проверочная матрица будет иметь вид: H = [111].
Непосредственно из определения проверочной матрицы следует
основное свойство проверочной матрицы.
H=
h1
h2
...
hr
=
h11 h12 . . . h1n
h21 h22 . . . h2n
...
hr1 hr2 . . . hrn
Рис. 2.6. Проверочная матрица кода
49
101
G=
011
Рис. 2.7. Порождающая матрица кода
Свойство. Произведение любого кодового слова на транспонированную проверочную матрицу равно нулевому вектору (aHT = 0).
Умножение кодового слова на транспонированную проверочную
матрицу можно рассматривать как r последовательных умножений
кодового слова на базисные векторы ортогонального дополнения.
Каждое такое произведение будет равняться 0.
Пример 2.17. Из предыдущего примера возьмем кодовое слово
a2 и умножим его на транспонированную проверочную матрицу
HT:
é1ù
ê ú
T
T
a2H = (101)[111] = (101) êê1úú = 0, где r – длина нулевого вектора
ê1ú
ëê ûú
(в данном примере, r = 1).
Пример 2.18. Из примера 2.16 возьмем вектор (001), который не
является кодовым словом, и умножим его на транспонированную
проверочную матрицу HT:
é1ù
ê ú
T
T
(001)H = (001)[111] = (001) êê1úú = 1. В результате получили неê1ú
êë úû
нулевой вектор. Следовательно, вектор (001) не является кодовым
словом.
2.11. Алгоритм получения проверочной матрицы
из порождающей матрицы кода
Для начала получим порождающую матрицу для следующего
линейного кода:
А: a1 = (00000), a2 = (01101), a3 = (10110), a4 = (11011).
Мощность:|A|= 4, k = 2, n = 5.
Порождающая матрица кода представлена на рис. 2.8.
Если порождающая матрица задана в левой канонической форме, то проверочную матрицу можно получить следующим образом.
50
10
110
01
101
G=
Рис. 2.8. Порождающая матрица кода
1. Строим матрицу H размерности r×n в правой канонической
форме (в примере 3×5, рис. 2.9); т.е. справа размещаем единичную
матрицу Ir размерности 3×3.
2. В левые 2 столбца матрицы записываем транспонированную
матрицу G2.
aHT = mGHT = 0. Поскольку равенство справедливо для любых
m, то проверочная и порождающая матрицы связаны следующим
соотношением: GHT = 0.
Порождающая матрица кода G записывается в левой канонической форме:
G = [Ik|G2]. Проверочную матрицу H представим в правой канонической форме:
H = [H1|Ir].
éH1ù
T
Тогда, 0 = GHT = éëIk | G2 ùû éëH1 | Ir ùû = éëIk | G2 ùû ê ú = H1T + G2 . С учетом
êIr ú
ë û
того, что код строится над полем GF(2) , имеем: G2 = H1T .
Рассмотрим на конкретном примере, как работает декодер в случае обнаружения ошибки.
Пример 2.19. Пусть требуется закодировать сообщение m = (11).
Это сообщение поступает на вход кодера (рис. 2.10). Кодер формирует кодовое слово a = (11|011). Кодовое слово передается по каналу
связи. На выходе канала формируется последовательность y. Рассмотрим две различные ситуации:
1. Пусть при передаче по каналу не было ошибок a = (11|011) –
выход кодера, y = (11|011) – выход канала.
11
100
H = 10
010
01
001
Рис. 2.9. Проверочная матрица кода
51
Информационные
символы
a = mG = (11)
10 110
01 101
Проверочные
символы
= ( 11 | 011 )
Кодовое
слово
Сообщение
Кодер
Рис. 2.10. Кодирование сообщения
Декодер вычисляет вектор S.
é110 ù
ê
ú
ê101 ú
ê
ú
S = yHT = (11011) êê100 úú = (000). Поскольку S = 0, то декодер выê010ú
ê
ú
ê
ú
êë001úû
носит решение о том, что ошибок не было.
2. Теперь рассмотрим случай, когда при передаче по каналу произошло 2 ошибки. a = (11|011) – выход кодера, y = (00|011) – выход
канала.
Декодер вычисляет S.
é110 ù
ê
ú
ê101 ú
ê
ú
S = yHT = (00011) êê100 úú = (011). Поскольку S ≠ 0, то декодер выê010ú
ê
ú
ê
ú
êë001úû
носит решение об обнаружении ошибки.
Применительно к алгоритму сформулируем следующий вопрос:
сколько ошибок обнаруживает данный алгоритм? Можно показать, что данный алгоритм, с точки зрения обнаружения ошибок,
полностью эквивалентен алгоритму декодирования в шаре радиуса 0 (см. подразд. 1.9). Следовательно, можно обнаружить f ≤ d–1
ошибок, где d – минимальное расстояние кода (см. подразд. 1.10).
Для рассматриваемого кода d = 3 (f ≤ 2). Далее приведен пример
третьей ситуации, когда при передаче по каналу произошло три
ошибки, и так как S = 0, то декодер выносит неверное решение, что
ошибок не было.
52
é110 ù
ê
ú
ê101 ú
ê
ú
S = yHT = (01101) êê100 úú = (000).
ê010ú
ê
ú
ê
ú
êë001úû
2.12. Алгоритм работы декодера для случая
обнаружения ошибок
Ранее, когда код не был линейным, декодер должен был хранить
все кодовые слова и сравнивать принятую из канала последовательность со всеми кодовыми словами (алгоритм декодирования по минимуму расстояния Хэмминга, см. подразд. 1.8 и алгоритм декодирования в шаре, см. подразд. 1.9). Для линейного кода декодер
хранит проверочную матрицу H и для каждой принятой последовательности на выходе канала y выполняет следующие действия:
1. Вычисляет вектор S = y HT.
2. Если S ≠ 0, то формирует сигнал обнаружения ошибки.
Объем памяти декодера совпадает с размерностью проверочной
матрицы и равен V = r×n = (n–k)×n.
2.13. Минимальное расстояние линейного кода
Вспомним, что такое минимальное расстояние кода.
Пример 2.20.
Имеем код, который состоит из следующих кодовых слов:
a1 = (00000), a2 = (10101), a3 = (01110), a4 = (11011).
Вычислим расстояния между отдельными словами кода:
d1,2 = 3, d1,3 = 3, d1,4 = 4, d2,3 = 4, d2,4 = 3, d3,4 = 3.
Минимальным расстоянием кода, называется наименьшее расстояние между всеми кодовыми словами.
Следовательно, в нашем примере, минимальное расстояние будет d = 3 ⇒ минимальное расстояние будет равно трем, т.е. d = 3.
Это определение справедливо для любого кода.
Определение. Весом кодового слова w(a) называется число ненулевых компонент слова a.
53
Теорема 2.5. Для линейного кода A минимальное расстояние
кода равно минимальному весу среди всех ненулевых кодовых слов:
d = min w(a).
aÎ A,a¹0
Доказательство. Для любых двух векторов x∈A и y∈A имеет место равенство d(x,y) = w(x–y). Разность любых двух слов линейного
кода также является кодовым словом. Следовательно,
d=
min
x,yÎ A,x¹y
w(x - y) = min w(a).
aÎ A,a¹0
Таким образом, линейность кода является свойством, позволяющим определять минимальное расстояние, рассматривая только
веса кодовых слов, а не их всевозможные попарные расстояния.
Пример 2.21. Иллюстрация теоремы для кода из примера 2.20.
Код: a1 = (00000), a2 = (10101), a3 = (01110), a4 = (11011) является линейным кодом. Следовательно, w(a2) = 3, w(a3) = 3, w(a4) = 4,
и минимальное расстояние кода d = 3.
2.14. Определение минимального расстояния
по проверочной матрице линейного кода
Теорема 2.6. Пусть имеется проверочная матрица H линейного
(n,k) кода с минимальным расстоянием d. Тогда в этой матрице любые i < d столбцов линейно независимы, и найдется d линейно зависимых столбцов.
Доказательство. Минимальное расстояние кода равно d. Следовательно, вес любого кодового слова, кроме слова, состоящего из
всех нулей, больше либо равен d. Для любого кодового слова имеем:
a HT = 0, где a = (a1, a2, …, an). Выберем кодовое слово веса d. Пусть
ненулевые символы расположены на позициях: a1,a2, …, ad. Тогда
a1H1 + a2H2 + … + adHd = 0, где Hi – i-й столбец матрицы H. Следовательно, по определению d столбцов проверочной матрицы являются линейно зависимыми. Если в предыдущей формуле исключить один столбец, например, столбец H2, то a1H1 + … + adHd ≠ 0.
Следовательно, по определению (см. разд. 2.3) i = d–1 столбцов
(столбцы H1,H3, …, Hd) – линейно независимы. Аналогично, можно доказать, что любые i < d столбцов линейно независимы, так как
сумма этих столбцов не дает нулевой столбец.
Пример 2.22. Иллюстрация теоремы для кода из примера 2.20.
54
n = 5, d = 3, M = 2k, k = 2 – число информационных символов;
r = n–k = 3 – число проверочных символов
Построим порождающую (рис. 2.11) и проверочную матрицы
кода (рис. 2.12).
Применительно к матрице H, любые 2 столбца линейно независимы (i<3). Можно указать в матрице три столбца (2-й, 3-й и 4-й),
сумма которых дает нулевой столбец, т. е. три столбца матрицы –
линейно зависимы.
Непосредственно из теоремы, вытекает алгоритм определения
минимального расстояния кода по проверочной матрице. Проиллюстрируем этот алгоритм на конкретном примере.
Пример 2.23. Пусть имеется код со следующей проверочной матрицей (рис. 2.13).
Требуется определить минимальное расстояние кода.
1. Предположим, что минимальное расстояние кода d = 1. По
теореме 2.6 в этом случае в матрице должен был бы найтись один
линейно зависимый столбец, т. е. столбец из всех нулей. Такого
столбца нет, следовательно, переходим к шагу 2.
2. Предположим, что минимальное расстояние равно двум
(d = 2). В этом случае в матрице нашлось бы два линейно зависимых столбца (для двоичного кода два столбца, в сумме дающих ну-
G=
10
101
01
110
Рис. 2.11. Порождающая матрица кода
H=
11
100
01
010
10
001
Рис. 2.12. Проверочная матрица кода
10 1000
01 0100
H=
11 0010
11 0001
Рис. 2.13. Проверочная матрица кода
55
G=
10
1 011
01
0111
Рис. 2.14. Порождающая матрица кода
левой столбец, это столбцы, совпадающие друг с другом). В нашем
примере таких столбцов нет, следовательно, переходим к шагу 3.
3. Проверяем, нет ли трех линейно зависимых столбцов? Нет,
тогда переходим к шагу 4.
4. Проверяем, нет ли четырех линейно зависимых столбцов.
В нашем примере есть такие 4 столбца (столбцы 1,2,3,4). Следовательно, минимальное расстояние кода d = 4.
В общем случае для кода длины n на i-м шаге алгоритма проверяется, нет ли в проверочной матрице i линейно зависимых столбцов. Следует перебирать комбинации из Cni столбцов.
Вывод: зная проверочную матрицу кода, можно определить все
параметры этого кода.
Например, для кода с приведенной проверочной матрицей параметры будут следующими: n = 6, r = 4, k = n –r = 2, число кодовых
слов: 2k = 22 = 4, d = 4.
Кроме того, зная проверочную матрицу, можно выписать все кодовые слова.
Из проверочной матрицы строим порождающую матрицу G
(рис. 2.14).
Затем умножим на нее всевозможные комбинации информационных символов:
(00) × G = (000000), (01) × G = (010111), (10) × G = (101011),
(11) × G = (111100).
Можно еще раз убедиться, что минимальное расстояние кода d = 4.
2.15. Анализ работы алгоритма декодирования линейного кода
для случая обнаружения ошибок
Пусть имеется линейный (n, k) – код с минимальным расстоянием d, и построена следующая система передачи информации
(рис. 2.15).
Пусть на вход канала поступило кодовое слово a. В канале
произошли ошибки, и на выходе появилась последовательность:
y = a + e, где e – некоторый вектор, называемый вектором ошибки.
56
Кодер
Канал
a = mG
m
Информационные Кодовое
символы
слово
Декодер
≠ 0=>формируется сигнал
T
yH =
обнаружения ошибки
Шумовое
= 0=>декодер выдает получателю
воздействие
последовательность y
y
как кодовое слово
Рис. 2.15. Система передачи информации
В этом векторе ненулевые символы расположены в тех позициях,
в которых произошли ошибки. Вес вектора e равен числу ошибок.
Выясним сколько ошибок можно обнаружить в такой системе.
Напомним алгоритм работы декодера.
1. Декодер вычисляет вектор S = yHT.
2. Если S ≠ 0, то формирует сигнал обнаружения ошибки.
Проанализируем данный алгоритм. S = yHT = (a + e)HT = aHT +
T
eH = eHT, так как aHT = 0. Следовательно, можно сказать, что
декодер не обнаруживает ошибку только в случае, если eHT = 0,
т. е. когда вектор ошибки e совпадает с одним из кодовых слов. Это
значит, что минимальный вес вектора e в этом случае равен минимальному расстоянию кодового слова.
Вывод. Данная система позволяет обнаружить любые ошибки
кратности f ≤ d –1. (Таким образом, данный алгоритм обнаруживает столько же ошибок, сколько обнаруживает алгоритм декодирования в шаре радиуса 0, см. подразд. 1.8).
Пример 2.24. Пусть построена система передачи с использованием проверочной матрицы из примера 2.23. Для этой системы,
так как d = 4, ошибки кратности 1, 2, 3 всегда будут обнаружены,
а ошибки кратности 4, в зависимости от того, в каких разрядах они
произошли, могут быть либо обнаружены, либо могут привести к
ошибке декодирования.
Задача. Самостоятельно привести примеры 4-кратных ошибок,
которые обнаруживаются и которые не обнаруживаются.
2.16. Построение кодов с минимальным расстоянием d = 3
Рассмотрим конкретный пример.
Пример 2.25. Требуется построить код, для которого зафиксировано число проверочных символов r = 3 и минимальное расстояние
d = 3, чтобы длина кода была максимальной.
57
11 0110 0
H=
10 1101 0
11 1000 1
Рис. 2.16. Проверочная матрица
1 0 110 0
H=
0 1 101 0
1 1 000 1
Рис. 2.17. Проверочная матрица
Укажем те условия, которым должна удовлетворять проверочная матрица такого кода. Если в матрице разместить нулевой столбец, то по теореме 2.6 минимальное расстояние кода будет d = 1.
Также невозможно размещать два идентичных столбца, так как в
этом случае d = 2. Следовательно, в матрице будут расположены все
столбцы длины 3, кроме нулевого столбца (рис. 2.16).
Получаем следующие параметры кода:
r = 3, n = 7, k = n–r = 4, M = 24 = 16 слов.
Решим задачу в общем виде.
Пусть задано произвольное число r-проверочных символов в коде
и требуется построить код с минимальным расстоянием d = 3 и максимально возможным числом информационных символов k и, следовательно, с максимально длиной кода n. В проверочной матрице
располагаются всевозможные ненулевые столбцы длины r, отличающиеся друг от друга. n = 2r –1 (здесь –1 обозначает нулевой столбец).
Таким образом, получен алгоритм построения двоичных кодов
со следующими параметрами: n = 2r–1, k = 2r–1–r, M = 2k, d = 3.
Можно показать, что эти коды являются самыми лучшими кодами при таких параметрах, т. е. при таком значении n и d = 3 имеют максимальное число кодовых слов (M–>max). Можно доказать,
что эти коды лежат на границе Хэмминга (см. подразд. 1.16).
Рассмотренные нами коды, были впервые описаны Р. Хэммингом в 1950 г. и называются кодами Хэмминга.
На практике часто возникает следующая задача.
Задано число информационных символов в коде k (т. е. задано
число кодовых слов: М = 2k). Требуется построить код с d = 3 и минимально возможным числом проверочных символов r и, следовательно, минимально возможной длиной кода n.
58
Пример 2.26. Пусть требуется построить код с параметрами k = 3,
d = 3 и с минимально возможным числом проверочных символов r.
Попытаемся решить эту задачу, используя только два проверочных символа.
n = 2r–1 = 22–1 = 3, т. е. у самого лучшего кода число информационных символов k = n–r = 3–2 = 1 и, следовательно, двух проверочных символов не хватит.
Попытаемся воспользоваться тремя проверочными символами:
r = 3, n = 2r–1 = 7, k = 7–3 = 4. Таким образом, при r = 3 в коде могут
быть 4 информационных символа. Нам требуются, только 3 информационных символа. Следовательно, число r = 3 удовлетворяет решению задачи, и теперь построим проверочную матрицу (рис. 2.17),
исключив из матрицы на рис. 2.16 крайний левый столбец.
Задание. Выписать все слова кода при помощи этой проверочной
матрицы. Для этого получить порождающую матрицу и умножить
всевозможные комбинации информационных символов на порождающую матрицу. Непосредственно по полученному списку кодовых слов проверить, что d = 3.
Замечание. Полученный в этом примере код называется укороченным кодом Хэмминга, и в практических системах как раз используются эти коды.
Обобщим данный пример.
Пусть задано число информационных символов в коде (k) и требуется построить код с минимальным расстоянием d = 3 и с минимально возможным числом проверочных символов r.
Как было в ранее рассмотренном примере, это происходит в два
шага:
1. Определяем число проверочных символов. Поскольку n ≤ 2r –1,
то k ≤ 2r –1–r; следовательно, надо выбрать такое наименьшее значение r, для которого справедливо следующее неравенство: k ≤ 2r –1–r.
2. Построим проверочную матрицу (см. рис. 2.18).
H=
В этой части матрицы располагаются
различные столбцы, содержащие 2 и
более единицы
Ir
Единичная матрица
Рис. 2.18. Структура проверочной матрицы
59
2.17. Построение кодов с минимальным расстоянием d = 4
Рассмотрим конкретный пример.
Пример 2.27. Пусть имеется код Хэмминга с n = 7 и k = 4, т. е.
(7,4) код с минимальным расстоянием d = 3. Следовательно, проверочная матрица, будет иметь вид (рис. 2.19).
Требуется построить код, который также будет иметь 4 информационных символа, но с минимальным расстоянием d = 4 и минимально возможным числом проверочных символов.
Поскольку исходный (7,4) код – оптимальный, то увеличивать
минимальное расстояние кода, не увеличивая при этом число проверочных символов нельзя. Добавим к этому коду один проверочный символ, т. е. получим код со следующими параметрами: k = 4,
r = 4, n = 8. Это означает, что к проверочной матрице надо добавить
одну строку и один столбец, так чтобы d = 4.
Добавим к исходной матрице нулевой столбец, а далее к полученной матрице добавим снизу строку, состоящую из всех единиц
(рис. 2.20).
Если d = 4, то по теореме 2.6 это означает, что любые i < 4 столбцов матрицы должны быть линейно независимыми и в матрице
найдется 4 линейно зависимых столбца. Для поля GF(2) это означает, что в матрице не должно быть нулевых и одинаковых столбцов, и, кроме того, любые три столбца в сумме не должны давать
нулевой столбец 0. В матрице (рис. 2.20) нет нулевых столбцов и
все столбцы разные. Сумма любых трех столбцов будет давать столбец, у которого последний разряд равен 1, т. е. эта сумма не будет
равна нулевому столбцу 0.
11 0110 0
H=
10 1101 0
11 1000 1
Рис. 2.19. Проверочная матрица кода Хэмминга
11 0110 0 0
H=
10 1101 0 0
11 1000 1 0
11 11 11 1 1
Рис. 2.20. Проверочная матрица кода с r = 4 и n = 8
60
Можно показать, что в матрице найдется 4 линейно зависимых
столбца. Для этого надо найти любые три столбца матрицы, сумма
которых равняется последнему столбцу матрицы. Например, 4-й,
5-й и 6-й столбцы матрицы. Таким образом, добавив один проверочный символ, получаем код с минимальным расстоянием d = 4.
Этот код является разновидностью кода Хэмминга и называется
расширенным кодом Хэмминга.
Преобразуем проверочную матрицу так, чтобы минимальное
расстояние кода сохранялось, а матрица приняла правую каноническую форму.
Можно показать, что если складывать между собой строки проверочной матрицы некоторого линейного двоичного кода, а результат сложения записывать в матрицу вместо одной из строк, участвующих в сложении, то полученная в результате этих операций
матрица останется проверочной матрицей того же кода.
Сложим все строки матрицы между собой, и результат сложения запишем на место последней строки (рис. 2.21). В результате
операции сложения последняя строка является дополнением до нечетности каждого столбца.
Теперь решим задачу в общем виде.
Введем следующие обозначения: H3 – матрица с минимальным
расстоянием 3 (рис. 2.19); H4 – матрица с минимальным расстоянием 4 (рис. 2.21).
Задача. Пусть требуется построить код с заданным числом информационных символов k, минимальным расстоянием кода d = 4
и минимально возможным числом проверочных символов r.
1. Решаем вспомогательную задачу. Строим код с тем же числом
информационных символов k, но с d = 3 и минимальным r. (Решение этой задачи было рассмотрено ранее).
2. На основе проверочной матрицы H3, построенной на предыдущем шаге, строится проверочная матрица кода H4 с d = 4 (рис. 2.22).
Последняя строка формируется так, чтобы последний элемент
каждого столбца, являлся дополнением до нечетности всех элементов этого столбца.
H=
11 0110 0 0
10 1101 0 0
11 1000 1 0
01 1100 01
Рис. 2.21. Проверочная матрица в правой канонической форме
61
0
H4 =
H3
r+1
0
xx
xxx
x 1
n = 2r
x – дополнение до нечетности элемента столбца
Рис. 2.22. Проверочная матрица кода с d = 4
Вывод. Длина и число проверочных символов в расширенном
коде Хэмминга на единицу больше, чем в коде Хэмминга с d = 3.
Число информационных символов кода при этом не изменяется.
Задача. Подтвердить или опровергнуть следующее утверждение: “Все кодовые слова кода с проверочной матрицей (рис. 2.21)
имеют четный вес”.
2.18. Построение кодов с минимальным расстоянием d = 2
Рассмотрим конкретный пример.
Пример 2.28. Пусть число информационных символов k = 3.
Требуется построить код с d = 2 и минимально возможным числом
проверочных символов r.
Попытаемся построить код с помощью одного проверочного символа (r = 1). В этом случае проверочная матрица будет иметь вид:
H = [1111] и n = k + r = 4.
Построим порождающую матрицу этого кода (рис. 2.23).
Следовательно, при r = 1 удается построить требуемый код.
Обобщим задачу. Пусть задано произвольное число информационных символов, и требуется построить код с d = 2 и минимально
возможным числом проверочных символов r.
G=
100 1
010 1
k= 3
001 1
n= 4
Рис. 2.23. Порождающая матрица кода с d = 2
62
Для d = 2 требование, вытекающее из теоремы 2.6, состоит в
том, чтобы все столбцы проверочной матрицы были ненулевыми.
При r = 1 матрица будет иметь следующий вид: H = [11…1]. В этом
случае, кодовые слова удовлетворяют следующему уравнению:
aHT = 0, где a = (a1, a2, …, an), т. е. aHT = a1 + a2 + … + an = 0. Отсюда следует, что все кодовые слова должны иметь четный вес. Поэтому такие коды называют кодами с проверкой на четность.
Вывод. Были рассмотрены алгоритмы решения следующих задач. Задано число информационных символов, зафиксировано d
и строились коды с минимально возможным числом проверочных символов. Задачи были решены при следующих значениях
d: d = 2 – коды с проверкой на четность, d = 3 – коды Хэмминга,
d = 4 – расширенные коды Хэмминга. Заметим, что простые решения задач при d > 4 не существуют.
2.19. Пример построения линейного кода,
исправляющего одиночные ошибки
Рассмотрим следующий элементарный подход для построения
кода с проверкой на четность. Пусть требуется передать по каналу
сообщение, состоящее из k = 4 информационных символов, с возможностью исправить любую одиночную ошибку. Возьмем следующее сообщение m = (a1a2a3a4) = (0110). Представим сообщение
в виде таблицы (рис. 2.24), где первые два символа сообщения образуют первую строку таблицы, а последние два – вторую строку.
Выполним кодирование, добавив в таблицу символы, дополняющие каждую строку и столбец таблицы до четности. Получим таблицу (рис. 2.25), нумерация символов, в которой представлена на
рис. 2.26.
01
10
Рис. 2.24. Входное сообщение
01 1
10 1
11 0
Рис. 2.25. Кодовое слово
63
a1 a2 a5
a3 a4 a6
a7 a8 a9
Рис. 2.26. Нумерация символов в кодовом слове
В канал передается следующее кодовое слово (011011110). Пусть
на выходе канала получаем последовательность (011111110). Выполним алгоритм декодирования. Представим принятую из канала
последовательность в виде таблицы и проверим на четность каждую
строку и каждый столбец таблицы (рис. 2.27). Видно, что ошибка
произошла во второй строке и втором столбце таблицы. Следовательно, элемент на пересечении этой строки и этого столбца и есть
ошибочный символ.
Таким образом, одиночная ошибка и ее позиция в принятой последовательности была обнаружена, что позволяет ее исправить.
Получили код со следующими параметрами: k = 4, n = 9, r = 5.
Построим проверочную и порождающую матрицу кода. Получим зависимость проверочных символов кода от информационных
символов.
ìïa5 = a1 + a2
ïï
ïïa6 = a3 + a4
ïï
.
ía7 = a1 + a3
ïï
ïïa8 = a2 + a4
ïï
ïîa9 = a5 + a6 = a1 + a2 + a3 + a4
На основе этих выражений получим проверочную матрицу кода
в правой канонической форме (рис. 2.28). По проверочной матрице
строим порождающую матрицу кода в левой канонической форме
(рис. 2.29).
01
1
+
11
1
–
11
0
+
+ – +
Рис. 2.27. Декодирование последовательности
64
1234
5678 9
1100
1000 0
0011
0100 0
H= 1010
0010 0
0101
1111
0001 0
5
0000 1
9
Рис. 2.28. Проверочная матрица кода
1234
56 78 9
1000
10 10 1
0100
10 01 1
G = 0010
0 1 10 1
0001
0 1 01 1
9
4
Рис. 2.29. Порождающая матрица кода
Если умножить сообщение m = (0110) на порождающую матрицу G, получим следующее кодовое слово (011011110), которое мы и
передавали в канал. По проверочной матрице кода можно определить минимальное расстояние кода d = 4.
Выясним, какое минимальное число проверочных символов необходимо для решения поставленной задачи (k = 4, t = 1)? В подразд. 2.16 было показано, что при k = 4 можно построить код с минимально возможным числом проверочных символов r = 3, n = 7,
d = 3. При таком минимальном расстоянии код может исправить 1
ошибку. Следовательно, код с такими параметрами подойдет для
решения задачи.
2.20. Синдромное декодирование линейных кодов
Вернемся к системе передачи информации на рис. 2.15. Пусть
H – проверочная матрица (n,k) кода A.
Определение. Синдромом последовательности y∈Xn, X = GF(q),
называется вектор S(y), определяемый как S(y) = yHT. Очевидно,
что для любого кодового слова a∈A S(a) = 0. Поэтому ненулевой
синдром S(y) указывает на наличие ошибок в принятом слове y.
65
Теорема 2.7. Синдром зависит только от вектора ошибки и не зависит от того какое кодовое слово передавалось.
Доказательство. На вход кодера, поступает последовательность
m. Кодер формирует кодовое слово a = mG. В канале происходят
ошибки, описанные вектором e, и на выходе канала появляется последовательность y = a + e.
Вычислим синдром: S(y) = yHT = (a + e)HT = aHT + eHT = eHT =
S(e), так как aHT = 0.
Теорема доказана.
Теорема 2.8. Для кода с минимальным расстоянием d, синдромы
различных векторов ошибок, вес которых w(e) ≤ t, где t = (d–1)/2,
отличаются друг от друга, т. е. если e1 ≠ e2 и w(e1) ≤ (d–1)/2, w(e2) ≤
(d–1)/2, то S(e1) ≠ S(e2).
Доказательство от противного. Предположим, что синдромы
различных векторов ошибок совпадают, т. е. S(e1) = S(e2). Тогда,
из определения синдрома, e1HT = e2HT. Следовательно, e1HT –
e2HT = (e1–e2)HT = e1–e2HT = 0 и вектор (e1–e2) является кодовым
словом. Используя неравенство треугольника, можно показать, что
w(e1–e2) = d(e1, e2) ≤ w(e1) + w(e2) ≤ 2t < d. Но это невозможно, так
как e1–e2 – кодовое слово, и, следовательно, w(e1–e2) ≥ d. Поэтому
наше предположение неверно, и синдромы различны.
Аналогично, можно доказать, что синдром вектора ошибки e1
такого, что t < w(e1) < d – t отличен от нуля и не совпадает ни с одним из синдромов векторов ошибок e2, для которых w(e2) ≤ t.
Проиллюстрируем теорему на следующем примере.
Пример 2.29. Пусть есть код Хэмминга (7,4) с минимальным расстоянием d = 3 и проверочной матрицей, представленной на рис. 2.30.
Составляем следующую табл. 2.6.
Из табл. 2.6 видно, что при одиночной ошибке синдромы отличаются, а при двойной ошибке синдромы могут совпадать.
Пример 2.30. Данный пример показывает, как можно использовать теорему 2.8 для исправления ошибок в системе передачи
информации (рис. 2.31). Будем использовать код из предыдущего
примера. Порождающая матрица кода приведена на рис. 2.32.
11 0110 0
H=
10 1101 0
11 1000 1
Рис. 2.30. Проверочная матрица кода Хэмминга
66
Таблица 2.6
Синдромы векторов ошибок
Условие теоремы
Вектор ошибки e
Синдром S
Выполняется w(e) ≤ t
0000000
1000000
0100000
0010000
0001000
0000100
0000010
0000001
1000001
0000110
1100000
000
111
101
011
110
100
010
001
110
110
010
Не выполняется w(e) > t
Кодер
Канал
Декодер
y S = yH T
a = mG
m
Информационные Кодовое Шумовое
символы
слово воздействие
Рис. 2.31. Система передачи информации
1000 111
G=
0100 101
0010 011
0001 110
Рис. 2.32. Порождающая матрица
Пусть на вход канала поступает следующее сообщение: m = (1010).
Кодер при этом формирует кодовое слово a = (1010100). При передаче по каналу произошла ошибка, например, во втором разряде,
т. е. y = (1110100).
Декодер вычисляет синдром (рис. 2.33).
Далее декодер по табл. 2.6, находит вектор ошибки, соответствующий этому синдрому. В данном случае, e = (0100000). Поэтому декодер складывает векторы y = (1110100) и e = (0100000) и исправляет ошибку.
Приведенный пример показывает, что любые одиночные ошибки исправляются, так как различным векторам ошибок соответствуют различные синдромы.
67
11 1
10 1
S = yHT= (1110100)
01 1
11 0
= (101)
100
010
001
Рис. 2.33. Вычисление синдрома
Двукратные ошибки приведут к неправильному декодированию. Например, если при передаче по каналу произойдет ошибка
во втором и третьем разрядах: y = (1100100). Декодер вычислит
синдром S = (110). По табл. 2.6 вектор ошибки – e = (0001000). Декодер складывает y = (1100100) и e = (0001000) и выдает неверное
слово y + e = (1101100), которое хотя и является кодовым, но отличается от слова, которое передавалось a = (1010100).
2.21. Алгоритм синдромного декодирования
На основе предыдущего примера и теоремы 2.8 составим общий
алгоритм декодирования линейных кодов, который называется алгоритмом синдромного декодирования и позволяет исправлять все
ошибки кратности t ≤ (d–1)/2 и обнаруживать все ошибки кратности t < f < d – t.
Отметим, что алгоритм для кода в примере 2.30 исправлял одну
ошибку и не обнаруживал никаких ошибок.
Пусть имеется код с минимальным расстоянием d и требуется
исправить t ошибок, причем 0 ≤ t ≤ (d–1)/2. Декодер должен хранить проверочную матрицу H и таблицу соответствия между векторами ошибок и синдромами. Общий вид таблицы представлен на
рис. 2.34.
Для каждой принятой из канала последовательности декодер
выполняет следующие действия:
1. Вычисляет вектор синдрома S = yHT.
2. В таблице для вектора S находит соответствующий ему вектор e.
3. Выносит решение о том, что передавалось кодовое слово a = y + e.
4. Если вектор S в таблице отсутствует, то формирует сигнал обнаружения ошибки.
68
S = eHT
e
00... 0
Cn1
10 ...0
01 ...0
...
0 0 . . .1
...
.
.
.
.
.
.
Cnt
Вектора,
содержащие
t единиц
Рис. 2.34. Таблица синдромов векторов ошибок
Теперь покажем, что алгоритм синдромного декодирования позволяет обнаруживать ошибки, которые не могут быть исправлены.
Пример 2.31. Рассмотрим расширенный двоичный (8,4) код
Хэмминга с расстоянием 4 и проверочной матрицей (рис. 2.35).
Этот код с d = 4 позволяет исправлять однократные и обнаруживать
двукратные ошибки. Векторы исправляемых ошибок и их синдромы представлены в табл. 2.7.
В табл. 2.7 представлены только 9 из 16 возможных синдромов.
Приведенные синдромы соответствуют ошибкам кратности 1. Все
ошибки кратности 2 имеют другие синдромы, часть из которых
представлена в табл. 2.8. Из табл. 2.8 видно, что различные векторы ошибок могут иметь одинаковые синдромы, поэтому исправить
такие ошибки нельзя.
Декодер хранит только проверочную матрицу (рис. 2.35) и таблицу векторов исправляемых ошибок и их синдромов (табл. 2.7).
Поэтому при двух ошибках декодер не сможет найти нужный
синдром в табл. 2.7 и соответствующий ему вектор ошибки. В этом
11 0110 0 0
H= 1 0 1 1 0 1 0 0
11 1000 1 0
01 1100 0 1
Рис. 2.35. Проверочная матрица расширенного кода Хэмминга
69
Таблица 2.7
Векторы исправляемых ошибок и их синдромы
для расширенного кода Хэмминга
Вектор ошибки e
Синдром S
00000000
10000000
01000000
00100000
00010000
00001000
00000100
00000010
00000001
0000
1110
1011
0111
1101
1000
0100
0010
0001
Таблица 2.8
Некоторые векторы ошибок кратности 2 и их синдромы
10000001
00010010
00000110
11000000
00110000
00000011
00001001
00001100
1111
1111
0110
0101
1010
0011
1001
1100
случае декодер выдает сигнал обнаружения ошибки, исправить которую нельзя.
Утверждение 2.4. Рассмотренный алгоритм синдромного декодирования полностью эквивалентен алгоритму декодирования в
шаре радиуса t. Доказательство этого утверждения следует из рассуждений, приведенных в [4, подразд. 2.3].
2.22. Выводы по второму разделу
Во втором разделе были рассмотрены линейные коды, которые
являются частным случаем блоковых кодов. В отличие от блоковых
кодов (см. разд. 1) множество слов линейного кода должно образовывать линейное подпространство (см. подразд. 2.2). При этом для
двоичного кода число слов в коде всегда является степенью числа
2. По сравнению с параметрами блокового кода (см. подразд. 1.3):
70
длина – n, число кодовых слов – M и минимальное расстояние – d,
для линейного кода добавляются параметры (см. подразд. 2.5): число информационных символов – k = log2 M и число проверочных
символов r = n – k. Скорость кода через эти параметры вычисляется
следующим образом: R = k/(k + r) = k/n.
За счет введения ограничения на множество кодовых слов для
задания кода не требуется указывать весь список из M кодовых
слов, а достаточно задать так называемую порождающую матрицу
кода, которая для двоичного кода содержит всего log2 M кодовых
слов (см. подразд. 2.6). Также существенно уменьшается сложность алгоритмов кодирования (см. подразд. 2.8) и декодирования
(см. подразд. 2.12). При этом не изменяется количество ошибок,
которые может исправить или обнаружить код c некоторым минимальным расстоянием d по сравнению с переборными алгоритмами, которые были рассмотрены в первом разделе.
Во втором разделе также описаны способы построения линейных кодов с минимальным расстоянием 2, 3 и 4, которые при заданном числе информационных символов имеют минимально возможное число проверочных символов (см. подразд. 2.16–2.18),
т. е. имеют максимальную скорость. Построение линейных кодов с
большим минимальным расстоянием является сложной математической проблемой, решение которой в общем виде для произвольных значений числа информационных символов и минимального
расстояния не известно. Частные случаи решения этой задачи имеются только для некоторых значений k и d (см., например [4]).
71
3. ЦИКЛИЧЕСКИЕ КОДЫ
3.1. Определение циклического кода
Определение. Циклическим кодом называется такой линейный
код, для которого циклический сдвиг любого кодового слова также
является кодовым словом.
Рассмотрим следующие три кода и выясним, какие из этих кодов являются циклическими:
a1 = (001), a2 = (010), a3 = (100), a4 = (111) – этот код нелинейный, следовательно, он нециклический;
a1 = (110), a2 = (101), a3 = (011), a4 = (000) – этот код линейный,
выполняется условие замкнутости для циклического кода, следовательно, код циклический;
a1 = (00000), a2 = (01011), a3 = (10101), a4 = (11110) – этот код
линейный, но при циклическом сдвиге существуют слова, не принадлежащие этому коду, следовательно, код нециклический.
Замечание. Второй код – это линейный код с двумя информационными символами и одним проверочным (проверочный символ
формируется, как сумма по модулю 2 информационных символов).
Доказать самостоятельно, что код с проверкой на четность при
любом числе символов является циклическим кодом.
Для математического описания циклических кодов используются многочлены с коэффициентами из конечного поля.
3.2. Многочлен с коэффициентами из конечного поля.
Операции над многочленами
Пусть имеется некоторое конечное поле GF(q). Многочленом
степени n называется следующее математическое выражение:
g(x) = an xn + an-1xn-1 +  + a1x1 + a0 x0 , ai Î GF (q), где q – число
элементов в этом поле; x – формальная переменная.
Над многочленами определены следующие операции:
1. Сложение многочленов:
a(x) = an xn +  + a1x1 + a0 x0 , b(x) = bn xn +  + b1x1 + b0 x0 , тогда c(x) = a(x) + b(x) = (an + bn )xn +  + (a1 + b1 )x1 + (a0 + b0 )x0 .
Пример 3.1. Задано поле GF(2), a(x) = x3 + x2 + x, b(x) = x4 + x3 + x2 + x + 1.
) = x4 + x3 + x2 + x + 1. Тогда c(x) = x3 + x2 + x + x4 + x3 + x2 + x + 1 = x4 + 1.
Пусть степень многочлена deg(a(x)) = n1, deg(b(x)) = n2 , тогда
из операции сложения многочленов deg(a(x) + b(x)) £ max(n1,n2 ).
72
2. Умножение многочленов:
Пример 3.2. Задано поле GF(2), a(x) = x2 + x + 1, b(x) = x + 1.
Тогда a(x)b(x) = (x2 + x + 1)(x + 1) = x3 + x2 + x2 + x + x + 1 = x3 + 1.
Если deg(a(x)) = n1, deg(b(x)) = n2 , то deg(a(x)b(x)) = n1 + n2 .
3. Деление многочленов с остатком:
Пример 3.3. Задано поле GF(2), b(x) = x3 + x + 1, g(x) = x + 1.
Тогда b(x)mod g(x) = (x3 + x + 1)mod(x + 1) = 1 (рис. 3.1), где mod –
операция взятия остатка.
Запишем равенство, которое связывает 4 многочлена: b(x) = m(x) g(x) +
b(x) = m(x) g(x) + c(x), deg(c(x)) < deg(g(x)).
Для двоичных многочленов (многочленов в поле GF(2)) используется сокращенная запись в виде списка степеней с ненулевыми
коэффициентами.
Пример 3.4. Сокращенная запись для примера 3.2: a(x) = x2 + x + 1
a(x) = x2 + x + 1 –> (210), b(x) = x + 1 –>(10). (210)(10) = (322110) = (30)
–> x3 + 1 .
Многочлену  a(x) = an xn + an-1xn-1 +  + a1x1 + a0 x0  степени
deg(a(x)) = n соответствует вектор a = (an an-1 a1a0 ) длины n + 1.
Пример 3.5. Задан многочлен: a(x) = x2 + 1. Какой вектор соответствует этому многочлену? a = (101), a(x) = 1× x2 + 0 × x + 1×1.
Для сложения многочленов справедливо следующее утверждение.
Утверждение 3.1. Пусть имеется взаимно-однозначное соответствие между многочленами и векторами: a(x) « a, , b(x) « b. Тогда, a(x) + b(x) « a + b.
Пример 3.6. Иллюстрация утверждения. Пусть заданы многочлены a(x) = x2 + x « (110) и b(x) = x + 1 « (011). Складываем многочлены: a(x) + b(x) = x2 + 1 « (101).
Для того чтобы провести аналогию между операциями умножения многочленов и операциями над векторами рассмотрим следующий пример.
–
–
b (x)
g (x)
x3 +x+1
x+1
x3 +x2
x2 +x
m (x)
x2 +x+1
x2 +x
1
c (x)
Рис. 3.1. Деление многочленов с остатком
73
Пример 3.7. Задан многочлен: a(x) = x2 + 1 « (101). Получим
многочлен: a(x) × x = x3 + x « (1010). Этот многочлен можно получить путем сдвига вектора влево на 1 разряд.
Утверждение 3.2. Многочлену a(x), умноженному на xw, соответствует вектор a, сдвинутый на w позиций влево.
3.3. Порождающий многочлен циклического кода
Неформально порождающий многочлен циклического кода
можно определить как некоторый многочлен, с помощью которого
можно получить весь список кодовых слов.
Пример 3.8. Пусть имеется следующий код:
a1 = (0000), a2 = (0101), a3 = (1010) – сдвиг a2 влево на 1 разряд, a4 = (1111) – сложение a2 и a3. Поставим каждому кодовому слову в соответствие свой многочлен: a1 (x) = 0, a2 (x) = x2 + 1,
a3 (x) = x3 + x, a4 (x) = x3 + x2 + x + 1.
Далее при изложении материала вместо использования утверждений типа: многочлен a(x) , соответствующий кодовому слову a,
будем кратко говорить: кодовое слово a(x) .
Определение. Ненулевое кодовое слово наименьшей степени называется порождающим многочленом циклического кода.
Пример 3.9. Укажем порождающий многочлен для кода из предыдущего примера. Код состоит из 4 кодовых слов. Если исключить из рассмотрения слово a1 (x) = 0, состоящее из всех нулей, то
наименьшую степень имеет кодовое слово a2 (x) = x2 + 1. Следовательно, оно и является порождающим многочленом, т.е порождающий многочлен этого кода: g(x) = x2 + 1.
Порождающий многочлен обладает следующими свойствами.
Свойство 1. Степень порождающего многочлена равна r, т. е.
deg(g(x)) = r , где r – число проверочных символов в коде.
Свойство 2. Все кодовые слова делятся без остатка на порождающий многочлен:
"a(x) : a(x)mod g(x) = 0.
Проиллюстрируем свойства порождающего многочлена на следующем примере.
Пример 3.10. Возьмем код из примера 3.8.
1. Длина кода n = 4, M = 4 = 2k, k = 2, r = n – k = 2. Следовательно, deg(g(x)) = 2.
2.  a3 (x)mod g(x) = 0, a4 (x)mod g(x) = 0 (рис. 3.2).
74
–
x3 +x
x2 +1
x3 +x
x
0
– остаток ноль
x3 +x2 +x+1 x2 +1
– 3
x +x
x+1
–
x2 +1
x2 +1
0
– остаток ноль
Рис. 3.2. Деление кодовых слов на порождающий многочлен
Непосредственно из свойства 2 следует алгоритм работы кодера/
декодера циклического кода для случая обнаружения ошибок.
Декодер хранит порождающий многочлен циклического кода и
для каждой, принятой из канала, последовательности y выполняет
следующие действия:
1. Представляет последовательность y в виде многочлена y <–>
y(x).
2. Вычисляет многочлен S(x) = y(x)mod g(x).
3. Если S(x) ¹ 0, то формируется сигнал обнаружения ошибки.
3.4. Определение параметров циклического кода
по порождающему многочлену
Справедливо следующее утверждение.
Утверждение 3.3. Длина циклического кода с порождающим
многочленом g(x) – это такое наименьшее значение n, для которого
xn mod g(x) = 1. Доказательство утверждения приведено в [4, теорема 3.3].
Воспользуемся этим утверждением и свойством 1 порождающего многочлена для определения параметров циклического кода со
следующим порождающим многочленом g(x) = x3 + x + 1.
В соответствии со свойством 1 определяем число проверочных
символов в коде r = deg(g(x)) = 3.
По утверждению 3.1 определяем длину кода. Для этого выполним следующую итерационную процедуру:
x0 mod(x3 + x + 1) = 1,
x1 mod(x3 + x + 1) = x,
x2 mod(x3 + x + 1) = x2 ,
x3 mod(x3 + x + 1) = x + 1, n ¹ 3,
75
x4 mod(x3 + x + 1) = (x3 × x)mod(x3 + x + 1) =
= ((x3 mod(x3 + x + 1)) × x)mod(x3 + x + 1) =
= ((x + 1) × x)mod(x3 + x + 1) = x2 + x, n ¹ 4,
x5 mod(x3 + x + 1) = (x3 + x2 )mod(x3 + x + 1) = x2 + x + 1, n ¹ 5,
x6 mod(x3 + x + 1) = (x3 + x2 + x)mod(x3 + x + 1) = x2 + 1, n ¹ 6,
x7 mod(x3 + x + 1) = (x3 + x)mod(x3 + x + 1) = 1.
Длина кода n = 7, число информационных символов кода k = n –
r = 4.
Таким образом, по порождающему многочлену можно определить все параметры циклического кода.
3.5. Кодирование циклических кодов
Кодер хранит порождающий многочлен g(x) и для каждой кодируемой последовательности m выполняет следующие действия:
1. Для вектора m формируем многочлен: m <–>m(x).
2. Вычисляем многочлен a(x) = m(x) × g(x).
3. По многочлену a(x) формируем вектор a.
Пример 3.11. g(x) = x3 + x + 1, m = (1001). Выполнить кодирование.
1.  m(x) = x3 + 1.
2.  a(x) = m(x) g(x) = (x3 + 1)(x3 + x + 1) =
= x6 + x4 + x3 + x3 + x + 1 = x6 + x4 + x + 1.
3. Получаем вектор длины 7: a = (1010011).
Замечание. Рассмотренный способ кодирования называется несистематическим кодированием. При этом способе информационные символы не располагаются в начале кодового слова, а как бы
“размазываются” по кодовым словам. Поэтому на практике чаще
используется другой способ кодирования циклических кодов.
3.6. Систематическое кодирование циклических кодов
Кодер хранит порождающий многочлен циклического кода
g(x) и для каждой кодируемой последовательности m выполняет
следующие действия:
76
1) вектору m ставится в соответствие многочлен: m <–>m(x);
2) вычисляется многочлен c(x) = m(x)xr mod(g(x));
3) многочлен a(x) формируется как: a(x) = m(x)xr + c(x);
4) многочлену a(x) ставится в соответствие вектор a.
Многочлен c(x) называется контрольной суммой. m(x)xr – сдвиг
вектора m влево на r позиций.
Алгоритм систематического кодирования представлен на
рис. 3.3.
Пример 3.12. g(x) = x3 + x + 1, m = (1001). Выполнить систематическое кодирование.
1)  m(x) = x3 + 1;
2)  c(x) = m(x)xr mod(g(x)) = (x3 + 1)x3 mod(g(x)) =
= (x6 + x3 )mod(g(x)) = x6 mod(g(x)) + x3 mod(g(x)) =
= x2 + 1 + x + 1 = x2 + x;
3)  a(x) = m(x)xr + c(x) = x6 + x3 + x2 + x;
4) a = (1001110).
Старшие 4 символа вектора a – информационные символы, 3 младших символа – проверочные символы.
Из приведенного алгоритма следуют следующие выводы:
1. В результате кодирования получаются слова линейного кода.
2. Данный линейный код – циклический код.
3. Все кодовые слова делятся без остатка на порождающий многочлен (a(x)mod g(x) = 0).
Проиллюстрируем эти выводы на конкретных примерах.
Пусть на вход кодера поступает последовательность m1, на выходе формируется кодовое слово a1. Также на вход кодера поступаm (x)
m (x)
c (x)
k
r
Рис. 3.3. Алгоритм систематического кодирования
77
m1
Кодер
m2
Кодер
m3 = m1 + m2
Кодер
a1
a2
a3 = a1 + a2
Рис. 3.4. Пример систематического кодирования
ет последовательность m2, на выходе формируется кодовое слово a2
(рис. 3.4).
Пример 3.13. m1 = (1001), m2 = (1000).
Кодовое слово a1 = (1001110) (см. пример 3.12).
m2 (x) = x3 . c2 (x) = x3 x3 mod(g(x)) = x6 mod(g(x)) = x2 + 1. a2 (x) = x6 + x2 + 1
a2 (x) = x6 + x2 + 1. a2 = (1000101).
m3 = m1 + m2 = (1001) + (1000) = (0001).
m3 (x) = 1. c3 (x) = x3 mod(g(x)) = x + 1. a3 = (0001011).
Для линейного кода: a3 = a1 + a2 = (1001110) + (1000101) =
(0001011).
Пример 3.14. Проиллюстрируем вывод 3. Для этого проверим
кодовое слово a1. a1 (x) = x6 + x3 + x2 + x –> (6321). Определяем
остаток от деления кодового слова на порождающий многочлен
(рис. 3.5).
Пример 3.15. Для иллюстрации вывода 2 покажем, что циклический сдвиг кодового слова a1 также является кодовым словом.
a1 = (1001110). a* = (0011101) – циклический сдвиг влево первого кодового слова.
(6321)
–
(643 )
–
(310)
31
(421)
(421)
0
– остаток ноль
Рис. 3.5. Проверка кодового слова
78
(4320 )
–
(421 )
–
(310 )
10
(310 )
(310 )
0
– остаток ноль
Рис. 3.6. Проверка кодового слова
Покажем, что вектор a* является кодовым словом, т. е. соответствующий ему многочлен делится на порождающий многочлен без
остатка (рис. 3.6).
a* (x) = x4 + x3 + x2 + 1 –> (4320).
3.7. Сравнение алгоритмов кодирования и декодирования
циклических кодов
Из рассмотренного алгоритма кодирования следует, что операция кодирования фактически сводится к вычислению многочлена
c(x) = m(x)xr mod(g(x)). А операция декодирования сводится к вычислению S(x) = y(x)mod(g(x)). Несложно показать, что при декодировании вместо многочлена S(x) = y(x)mod(g(x)) можно использовать S(x) = y(x)xr mod(g(x)). Тогда можно сделать вывод, что кодирование и декодирование реализуются при помощи одной и той
же схемы, и, следовательно, при аппаратной реализации кодер и
декодер – идентичные устройства.
3.8. Синдромное декодирование циклических кодов
Поскольку циклические коды являются линейными, то все, что
мы говорили о синдромном декодировании линейных кодов, может
быть перенесено на циклические коды. Однако в случае циклических кодов можно упростить вычисление синдрома.
Пусть g(x) – порождающий многочлен циклического (n,k) кода,
a(x) – переданное слово и y(x) = yn-1xn-1 +  + y1x1 + y0 – многочлен, соответствующий принятой из канала последовательности.
В канале произошли ошибки, описанные вектором e, которому
79
соответствует полином ошибок e(x) = en-1xn-1 +  + e1x1 + e0 . На
вход декодера канала поступает y(x) = a(x) + e(x).
Полином S(x), определяемый соотношением S(x) = y(x)xr mod(g(x)),
r
x) = y(x)x mod(g(x)),r = n - k, называется синдромом принятой из канала последовательности y(x). Синдром равен нулю только в том случае,
если y(x) – кодовое слово.
Теорема 3.1. Синдром S(x) не зависит от переданного слова, а
определяется только полиномом ошибок.
Доказательство.
S(x) = y(x)xr mod(g(x)) = (a(x) + e(x))xr mod(g(x)) =
= a(x)xr mod(g(x)) + e(x)xr mod(g(x)) =
= e(x)xr mod(g(x)).
Можно показать, что для циклических кодов (также как и для
линейных) синдромы различных ошибок, вес которых не превышает t = êë(d -1) / 2úû , различны (см. теорему 3.6 в [4]).
Таким образом, алгоритм синдромного декодирования, за исключением правила вычисления синдрома, полностью совпадает с
алгоритмом синдромного декодирования линейных кодов.
Пример 3.16. Задан порождающий многочлен g(x) = x3 + x + 1.
Построим таблицу соответствия синдромов и полиномов ошибок
(табл. 3.1).
S(x) = 1× x3 mod(x3 + x + 1) = x + 1.
S(x) = x × x3 mod(x3 + x + 1) = (x + 1)x = x2 + x.
S(x) = x2 × x3 mod(x3 + x +1) = (x2 + x)× x mod(x3 + x +1) = x2 + x +1.
S(x) = x3 × x3 mod(x3 + x +1) = (x2 + x +1)× x mod(x3 + x +1) = x2 +1.
S(x) = x4 × x3 mod(x3 + x + 1) = (x2 + 1) × x mod(x3 + x + 1) = 1.
S(x) = x5 × x3 mod(x3 + x + 1) = x mod(x3 + x + 1) = x.
S(x) = x6 × x3 mod(x3 + x + 1) = x2 mod(x3 + x + 1) = x2 .
Пример 3.17. Задан порождающий многочлен g(x) = x3 + x + 1.
На вход кодера поступает сообщение m = (1001). На выходе кодера
формируется кодовое слово:
a = (1001110). Пусть в процессе передачи возникла ошибка на
четвертой позиции, т. е. y = (1011110). Выполним алгоритм синдромного декодирования в режиме исправления ошибок.
1. Ставим в соответствие принятой из канала последовательности многочлен
y(x) = x6 + x4 + x3 + x2 + x.
80
Таблица 3.1
Синдромное декодирование циклических кодов
е(х)
S(х)
0
1
x
x2
x3
x4
x5
x6
0
x+1
x2 + x
x2 + x + 1
x2 + 1
1
x
x2
2. Вычисляем синдром
S(x) = y(x)x3 mod(g(x)) = (x6 + x4 + x3 + x2 + x)x3 mod(g(x)) =
= (x9 + x7 + x6 + x5 + x4 )mod(g(x)) =
= x9 mod(g(x)) + x7 mod(g(x)) + x6 mod(g(x)) + x5 mod(g(x)) +
+x4 mod(g(x)) = x2 + 1 + x2 + 1 + x2 + x + 1 + x2 + x = 1.
3. Выполняем поиск полученного синдрома в табл. 3.1. Полученному синдрому соответствует многочлен ошибок e(x) = x4 .
4. y(x) + e(x) = x6 + x4 + x3 + x2 + x + x4 = x6 + x3 + x2 + x. Декодер принимает решение в пользу кодового слова a = (1001110).
Код с порождающим многочленом g(x) = x3 + x + 1 имеет минимальное расстояние d = 3. Поэтому в режиме исправления ошибок он может исправить только одну ошибку.
Пример 3.18. Покажем работу декодера в режиме обнаружения
ошибок. В этом случае декодер не исправляет ошибки, но может
обнаружить 1 или две ошибки.
Введем в вектор y еще одну ошибку на пятой позиции:
y = (1111110). Вычислим синдром:
S(x) = y(x)x3 mod(g(x)) = (x6 + x5 + x4 + x3 + x2 + x)x3 mod(g(x)) =
= (x9 + x8 + x7 + x6 + x5 + x4 )mod(g(x)) = x9 mod(g(x)) +
+x8 mod(g(x)) + x7 mod(g(x)) + x6 mod(g(x)) + x5 mod(g(x)) +
+x4 mod(g(x)) = x2 + x + 1 + x2 + 1 + x2 + x + 1 + x2 + x = x + 1.
S(x) ¹ 0, следовательно, декодер обнаружил две ошибки.
81
Примеры синдромного декодирования циклических кодов представлены в [9].
Задача. Самостоятельно привести примеры, когда декодер не обнаруживает три ошибки и когда декодер обнаруживает три ошибки.
3.9. Реализация операций над многочленами
на сдвигающих регистрах с обратными связями
Пусть требуется вычислить следующее выражение:
c(x) = m(x)d(x)mod g(x), где m(x), d(x) и g(x) – некоторые многочлены, для которых deg(g(x)) = r , deg(d(x)) £ r , deg(m(x)) = k -1.
Эту операцию можно выполнить при помощи устройства, представленного на рис. 3.7.
В этой схеме каждая ячейка памяти – элемент задержки, поступающего на вход схемы символа поля GF(q), на элемент времени,
называемый тактом. Если задано поле GF(2), то каждая ячейка
памяти хранит один бит. На каждом такте состояния ячеек памяти
изменяются в зависимости от предыдущего состояния и очередного
входного символа. Сумматоры в схеме для поля GF(2) представляют
собой сумматоры по модулю 2. Овал в схеме представляет умножитель, который в поле GF(2) означает, что если соответствующий коэффициент многочлена равен единице, то соединение в схеме является
линией. Если коэффициент равен нулю, то связь в схеме отсутствует.
Вместе ячейки памяти 0,1, …, r–1 можно рассматривать как сдвигающий регистр, между разрядами которого вставлены сумматоры.
. . .
g0
+
gr–1
g1
0
+
1
. . .
+
gr
r –1
+
r ячеек памяти
d0
Вход
dr–1
d1
dr
. . .
Рис. 3.7. Устройство для выполнения операций над многочленами
82
x3
x
1
C0
+
C2
C1
+
x3
Вход
Рис. 3.8. Устройство для вычисления многочлена c(x)
Схема работает следующим образом. В начальный момент времени все ячейки памяти обнулены. На такте с номером 1 на вход схемы поступает коэффициент при самой старшей степени многочлена
m(x)–mk–1. На такте с номером 2–mk–2 и т. д. На такте с номером k на
вход схемы поступает коэффициент m0, и в конце такта с номером
k в ячейках памяти формируются коэффициенты многочлена c(x).
Пример 3.19. Пусть требуется разработать схему для вычисления c(x) = m(x)x3 mod(x3 + x + 1). Схема строится на основе устройства, представленного на рис. 3.7. При этом потребуются три ячейки памяти (рис. 3.8).
Проиллюстрируем работу схемы для случая, когда m(x) = x3 + x = 1×
m(x) = x3 + x = 1× x3 + 0 × x2 + 1× x1 + 0 × x0 . Работа схемы по тактам приведена в табл. 3.2.
Проверим работу схемы. Для этого вычислим многочлен c(x) = m(x)x3 mo
c(x) = m(x)x3 mod(x3 + x + 1).  
Сначала выполним умножение: m(x)x3 = (x3 + x)x3 = x6 + x4 .
Далее вычислим остаток от деления многочлена x6 + x4 на многочлен (x3 + x + 1):
c(x) = (x6 + x4 )mod(x3 + x + 1) = 1 + x.
Полученный многочлен полностью совпадает с многочленом,
который можно сформировать, используя коэффициенты последней строки табл. 3.2.
Таблица 3.2
Работа схемы по тактам
С0
С1
С2
0
0
0
1
1(x3)
1
1
0
2
0(x2)
0
1
1
3
1(x1)
0
0
1
4
0(x0)
1
1
0
Номер такта
Вход
0
83
3.10. Синтез схемы кодера
для систематического кодирования
Рассмотрим синтез схемы кодера для кода с порождающим
многочленом: g(x) = (x3 + x + 1). Этот код имеет следующие параметры: r = 3, n = 7, k = 4 (см. подразд. 3.4). Проверочные символы
кода в соответствии с алгоритмом систематического кодирования
вычисляются как
c(x) = m(x)x3 mod(x3 + x + 1). (3)
Синтез кодера (рис. 3.9) включает следующие этапы.
Этап 1. Составление схемы для вычисления проверочных символов на основе типовой схемы (рис. 3.7) в соответствии с формулой (3). Построение этой схемы (рис. 3.8) было рассмотрено в подразд. 3.9.
Этап 2. Добавление выхода в схему. На вход схемы поступают
четыре информационных символа. Выход схемы – четыре информационных и три проверочных символа.
Этап 3. Установка ключей, коммутирующих работу схемы.
Ключ К1 предназначен для выбора выходного символа схемы (информационный или проверочный). Ключ К2 управляет работой
схемы вычисления проверочных символов.
Рассмотрим работу схемы по тактам. В течение первых четырех
тактов на вход кодера поступают информационные символы, которые одновременно передаются на выход кодера. При этом ключ К1
находится в нижнем положении, а ключ К2 замкнут, и проверочные символы вычисляются по формуле (3). В течение последующих
трех тактов эти проверочные символы поступают на выход кодера.
При этом ключ К2 разомкнут (т. е. регистр практически превраща-
К2
+
Вход
Выход
+
К1
Рис. 3.9. Кодер для систематического кодирования
84
ется в сдвигающий регистр), ключ К1 находится в верхнем положении, а на вход кодера должны подаваться нули.
3.11. Синтез схемы декодера
для случая обнаружения ошибок
Выполним синтез схемы декодера для кода с тем же порождающим многочленом. При декодировании необходимо вычислить
S(x) = y(x)xr mod(g(x)) (см. подразд. 3.8). В частном случае,
S(x) = y(x)x3 mod(g(x)). (4)
Синтез схемы включает следующие этапы.
Этап 1. Составление схемы вычисления многочлена на основе
типовой схемы (рис. 3.7) в соответствии с выражением (4). При
этом схема полностью совпадает с соответствующей схемой кодера.
Этап 2. Формирование выходного сигнала схемы – сигнала обнаружения ошибки E. Сигнал обнаружения ошибки E равен нулю
только в том случае, если все ячейки памяти обнулены.
Схема декодера (рис. 3.10) работает следующим образом. В течение семи тактов на вход декодера поступает принятая из канала последовательность, которая сохраняется в регистре длины 7.
В конце седьмого такта формируется сигнал обнаружения ошибки.
Если сигнал обнаружения ошибки равен нулю, то ошибок в принятой последовательности нет.
+
+
Вход
1
E
Выход
Регистр длины 7
Рис. 3.10. Декодер для случая обнаружения ошибок
85
3.12. Синтез схемы декодера
для случая исправления одиночных ошибок
Рассмотрим подробнее схему декодера для случая обнаружения
ошибок (рис. 3.10). На вход схемы поступает принятая из канала
последовательность. В конце такта с номером n принятая последовательность будет записана в регистре, а в ячейках S0, …, Sr–1 будут сформированы коэффициенты многочлена S(x). Если в канале
не было ошибок, то в ячейках S0, …, Sr–1 будут содержаться нули
(см. подразд. 3.11).
Утверждение 3.4. Если при передаче кодового слова по каналу произошла ошибка в первом передаваемом символе, а в других
символах ошибок не было, то в конце такта с номером n, этот ошибочный символ будет расположен в последней ячейке регистра.
Многочлен S(x) = xr–1, т. е. в ячейках памяти S0, S1, …, Sr–2 будут
записаны нули, а в ячейке Sr–1 будет записана единица.
Доказательство. Докажем, что в конце последнего такта S(x) =
xr–1. Пусть a – передаваемое кодовое слово; e – вектор ошибки; y –
принятая из канала последовательность, а a(x), e(x) и y(x) – соответствующие им многочлены. Если нам известны a и e, то y = a + e.
Следовательно, y(x) = a(x) + e(x) = a(x) + xn–1.
Вычислим значение многочлена: S(x) = y(x)xr mod g(x) = (a(x) +
n–1
x
) xr mod g(x) = a(x)xr mod g(x) + xr + n–1 mod g(x) = (xn xr–1) mod
g(x) = xn mod g(x) xr–1 mod g(x) = xr–1 mod g(x) = xr–1, что и требовалось доказать. При доказательстве учитывалось, что все кодовые
слова делятся без остатка на порождающий многочлен (a(x)xr mod
g(x) = 0) и xn mod g(x) = 1 (утверждение 3.3).
Вернемся к схеме. Для исправления ошибки, расположенной в
последнем разряде, нужно его инвертировать, добавив сумматор
(рис. 3.11). Следовательно, данная схема позволяет исправлять
одиночные ошибки в первом переданном разряде. Теперь предположим, что ошибка произошла во втором переданном разряде
(y(x) = a(x) + xn–2). Найдем значение многочлена S(x) на такте с
номером n, применив те же действия, что и при доказательстве утверждения 3.4: S(x) = y(x)xr mod g(x) = (a(x) + xn–2) xr mod g(x) =
xr–2. При этом на выходе схемы коррекции в точке e будет нулевой
сигнал, и на выход схемы поступит первый, принятый из канала,
символ. Рассмотрим состояние схемы на следующем n + 1-м такте.
При этом будем предполагать, что в последующих тактах на вход
схемы поступают нули. На такте n + 1 ошибочный символ поступает в последнюю ячейку регистра (рис. 3.12). S’(x) = S(x) x = x xr–2 =
86
Регистр длины r
S(x) = y (x)x r modg (x)
0
. . .
1
r –1
.
.
.
&
e
Рис. 3.11. Блок коррекции
Регистр длины r
0
0
0
. . .
0
0
0
. . .
1
0
На такте n
0
1
На такте n + 1
Рис. 3.12. Сдвигающий регистр
xr–1. Операция умножения на x эквивалентна операции сдвига.
При этом сигнал e на выходе схемы коррекции принимает значение
1, что приводит к формированию на выходе схемы исправленного
сигнала.
Можно показать, что если одиночная ошибка будет происходить
в других разрядах, то данная схема будет их исправлять. Остается нарисовать схему декодера для исправления одиночных ошибок
(рис. 3.13).
Регистр (Рг1) длины n
Регистр (Рг2) длины n
Sr–1Sr–2 ...
S(x) = y(x)xr modg(x)
. . .
0 1
r–1
.
.
.
&
e
Рис. 3.13. Декодер для исправления одиночных ошибок
87
Схема работает следующим образом. В исходном состоянии
ячейки памяти вычислителя синдрома обнулены. В течение первых n тактов на вход декодера поступает принятая из канала последовательность, которая сохраняется в регистре Рг1. После такта
с номером n в сдвигающем регистре сформирован синдром S(x). На
тактах n + 1,n + 2, …, 2n на вход схемы поступают нулевые символы. В результате работы в регистре Рг2 формируется исправленная
последовательность для случая одиночных ошибок.
Пример 3.20. Разработаем схему декодера для кода с порождающим многочленом g(x) = x3 + x + 1. Этот код имеет следующие
параметры: n = 7, r = 3, k = 4, d = 3 (см. подразд. 3.4). Это означает, что код может исправить любую одиночную ошибку (t = 1) и обнаружить две ошибки (f = 2). Для построения схемы исправления
ошибок необходимо синтезировать схему вычисления синдрома в
соответствии с выражением S(x) = y(x)x3mod(x3 + x + 1)(см. пример
3.19, рис. 3.8) и далее использовать схему декодера для случая исправления ошибок (рис. 3.13). Схема декодера для случая обнаружения двух ошибок была представлена на рис. 3.10. Схема декодера для исправления одиночных ошибок для кода с полиномом x3 +
x + 1 приведена на рис. 3.14.
Пример 3.21. Рассмотрим пример работы схемы на рис. 3.14.
Пусть в канал передается кодовое слово a = (1010011). На вход декодера поступает принятая из канала последовательность, которая
имеет одну ошибку в первой позиции y = (0010011). Работа схемы
по тактам представлена в табл. 3.3. Из табл. 3.3 видно, что после
7-го такта, когда завершается вычисление синдрома, 1 размещается в старшей позиции S2. В течение следующих семи тактов на вход
схемы подаются нули и после последнего такта в Рг2 будет исправленная последовательность, совпадающая с переданным кодовым
словом a.
Регистр (Рг1) длины 7
1
S0
Вход
x
+
Регистр (Рг 2) длины 7
x3
S1
+
S2
x3
&
e
Рис. 3.14. Декодер для случая исправления ошибок
88
Таблица 3.3
Работа схемы по тактам
Номер такта
Вход
S0
S1
S2
0
1
2
3
4
5
6
7
–
0
0
1
0
0
1
1
0
0
0
1
0
1
0
0
0
0
0
1
1
1
1
0
0
0
0
0
1
1
1
1
Пример 3.22. Рассмотрим другой пример. Пусть в канал передается кодовое слово a = (1010011). На вход декодера поступает принятая из канала последовательность, которая имеет одну ошибку в
шестой позиции y = (1010001). Работа схемы по тактам представлена в табл. 3.4. Из табл. 3.4 видно, что вычисление синдрома завершается после 7-го такта. Дальше в следующих тактах на вход
схемы подаются нули. После 12-го такта 1 размещается в старшей
позиции S2. В течение следующих двух тактов на вход схемы подаются нули и после последнего такта в Рг2 будет исправленная последовательность, совпадающая с переданным кодовым словом a.
Таблица 3.4
Работа схемы по тактам
Номер такта
Вход
S0
S1
S2
0
1
2
3
4
5
6
7
8
9
10
11
12
–
1
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
1
0
1
1
1
0
0
0
1
1
0
1
1
1
1
1
0
0
1
0
0
0
1
1
0
1
1
1
1
1
0
0
1
89
3.13. Выводы по третьему разделу
В третьем разделе были рассмотрены циклические коды, которые являются частным случаем линейных кодов. По сравнению с
линейными кодами на множество кодовых слов накладывается дополнительное ограничение: циклический сдвиг любого кодового
слова в циклическом коде также является кодовым словом.
Для описания циклических кодов и алгоритмов кодирования/
декодирования используется представление кодовых слов, кодируемых сообщений и последовательностей на выходе канала в виде
многочленов (см. подразд. 3.2). Для задания циклического кода достаточно указать одно единственное слово кода (см. подразд. 3.3).
Все остальные слова можно получить из данного слова путем циклических сдвигов этого слова и операций сложения результатов
сдвига. Многочлен, соответствующий данному кодовому слову, называют порождающим многочленом циклического кода.
В разделе рассмотрены алгоритмы кодирования и декодирования, основой которых является вычисление остатка от деления некоторого многочлена на порождающий многочлен. По количеству
обнаруживаемых и исправляемых ошибок алгоритмы декодирования эквивалентны ранее рассмотренным алгоритмам синдромного
декодирования линейных кодов (см. подразд. 2.21), но допускают
более простую реализацию. Задача нахождения порождающих
многочленов для кодов с заданными характеристиками (длиной,
числом информационных символов и минимальным расстоянием)
требует использования сложного математического аппарата, и в
настоящем учебном пособии не рассматривается. Возможные подходы к решению этой задачи можно найти, например в [4]. Следует
отметить, что существуют обширные таблицы, в которых содержатся порождающие многочлены с указанием параметров кодов.
90
Заключение
В учебном пособии были изложены основные сведения из теории блоковых помехоустойчивых кодов. При изложении материала применялась терминология, которая использовалась в данной
предметной области в русскоязычной литературе, начиная с 60-х
годов XX века, и продолжает использоваться в настоящее время.
Однако наряду с этой терминологией в отечественной инженерной
практике и соответствующей литературе встречается терминология, заимствованная из англоязычной литературы. Дадим разъяснение ряда из этих терминов на примерах систем, в которых используется помехоустойчивое кодирование.
В системах широковещательной передачи данных по радиоканалу,
как правило, отсутствует канал обратной связи от получателя к источнику (например, цифровое телевидение). В таких системах декодер
работает в режиме исправления ошибок (например, декодирование по
минимуму расстояния Хемминга). Такой способ использования помехоустойчивого кодирования в англоязычной литературе получил
название FEC (Forward error correction – прямая коррекция ошибок).
В качестве следующего примера рассмотрим систему, в которой по
прямому каналу, от источника к получателю, передаются некоторые
данные, а по обратному каналу, от получателя к источнику, передаются короткие сообщения, так называемые квитанции (например, в
системе LTE от абонентского устройства передаются данные к базовой
станции, базовая станция при приеме данных передает соответствующую квитанцию). В такой системе может быть использован алгоритм
декодирования в шаре радиуса ноль. Если декодер формирует сигнал
обнаружения ошибки, то принятая из канала последовательность стирается, и по обратному каналу посылается отрицательная квитанция,
если ошибка не обнаружена, то посылается положительная квитанция. При получении положительной квитанции источник посылает
следующее сообщение. При получении отрицательной квитанции
производится повторная посылка исходного сообщения. Передача исходного сообщения повторяется до тех пор, пока не будет получена положительная квитанция. Такой способ использования помехоустойчивого кодирования в англоязычной литературе получил название
BEC(Backward Error Correction – обратная коррекция ошибок) или
ARQ (Automatic repeat request – автоматический запрос повтора).
Во многих современных системах используются подходы, когда
при обнаружении ошибки принятая из канала последовательность
не стирается, а используется определенным образом при декодировании последовательности, которая принимается при повторной передаче. Такие походы получили название (Hybrid automatic repeat
request – гибридные методы автоматического запроса повтора).
91
Библиографический список
1. Золотарев В. В. Помехоустойчивое кодирование. Методы и
алгоритмы: справочник. – М.: Горячая линия – Телеком, 2004. –
126 с.
2. Евсеев Г. С., Тюрликов А. М. Кодирование в информационных системах: задачи и упражнения / СПб ин-т авиац. приборостр.
СПб., 1992. 30 с.
3. Витерби А., Омура Дж. Принципы цифровой связи и кодирования. – М.: Радио и связь, 1982. – 585 с.
4. Колесник В. Д. Кодирование при передаче и хранении информации. Алгебраическая теория блоковых кодов: учеб. пособие. М.:
Высш. шк., 2009. – 550 с.
5. Крук Е. А., Овчинников А. А. Основы теории кодирования:
учеб. пособие. СПб.: ГУАП, 2013. – 107 с.
6. Кудряшов Б. Д. Теория информации: учеб. пособие. – СПб.:
Питер, 2009. – 320 с.
7. Мак-Вильямс Ф. Дж. Теория кодов, исправляющих ошибки /
пер. с англ. Бассалыго и др. – М.: Связь, 1979. – 743 с.
8. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. – 320 с.
9. Теория информации: помехоустойчивое кодирование дискретных сообщений: метод. указ. к вып. лаб. работ / Е. А. Беляев,
С. С. Осипов, А. М. Тюрликов. – СПб.: ГУАП, 2011. – 34 с.
10. Питерсон У. Коды, исправляющие ошибки. – М.: Мир,
1976. – 594 с.
92
ПРИЛОЖЕНИЕ
Правило умножения вектора на матрицу
Для линейного кода алгоритм кодирования заключается в умножении входного вектора m длины k на порождающую матрицу
размерности k×n (рис. П.1). При умножении вектора на матрицу
обязательно, чтобы размерность вектора совпадала с числом столбцов матрицы. Элементы выходного вектора формируются в соответствии со следующим выражением:
k
aj = å mi gij , j = 1,n.
i=1
a 1a 2 ... ak...an = m 1m 2 ...mk x
g 11g 12...
g 21g 22...
g1n
g2n
…………………
gk1gk2... gkn
Рис. П.1. Алгоритм кодирования
93
СОДЕРЖАНИЕ
Введение...................................................................................... 3
1. Основные задачи помехоустойчивого кодирования. Блоковое
кодирование................................................................................. 5
1.1. Модель системы передачи (хранения) информации.................. 5
1.2. Помехоустойчивое кодирование............................................ 6
1.3. Блоковое кодирование. Основные определения ....................... 8
1.4. Скорость кодирования......................................................... 10
1.5. Основные принципы декодирования...................................... 10
1.6. Алгоритмы кодирования и декодирования.............................. 13
1.7. Расстояние Хэмминга.......................................................... 14
1.8. Алгоритм декодирования по минимуму расстояния Хэмминга.. 15
1.9. Алгоритм декодирования в шаре........................................... 16
1.10. Анализ алгоритма декодирования в шаре.............................. 19
1.11. Анализ алгоритма декодирования по минимуму расстояния
Хэмминга................................................................................. 25
1.12. Двоичный симметричный канал без памяти.......................... 26
1.13. Вычисление оценки вероятности ошибки декодирования
для алгоритма декодирования по минимуму расстояния Хэмминга.. 28
1.14. Вычисление оценки ошибки декодирования для алгоритма
декодирования в шаре................................................................ 30
1.15. Вычисление оценки вероятности отказа от декодирования
для алгоритма декодирования в шаре........................................... 30
1.16. Границы для числа кодовых слов. Граница Хэмминга............ 31
1.17. Граница Варшамова–Гилберта............................................ 33
1.18. Выводы по первому разделу ................................................ 35
2. Линейные коды......................................................................... 37
2.1. Конечные поля.................................................................... 37
2.2. Линейные пространства и подпространства............................. 39
2.3. Линейно зависимые и линейно независимые векторы .............. 41
2.4. Базис линейного пространства.............................................. 42
2.5. Определение линейного кода................................................. 44
2.6. Порождающая матрица линейного кода................................. 44
2.7. Кодирование линейного кода................................................ 45
2.8. Алгоритм работы кодера линейного кода................................ 47
2.9. Ортогональное дополнение линейного подпространства............ 47
2.10. Проверочная матрица линейного кода.................................. 49
2.11. Алгоритм получения проверочной матрицы из порождающей
матрицы кода........................................................................... 50
2.12. Алгоритм работы декодера для случая обнаружения ошибок... 53
2.13. Минимальное расстояние линейного кода............................. 53
2.14. Определение минимального расстояния по проверочной
матрице линейного кода............................................................. 54
2.15. Анализ работы алгоритма декодирования линейного кода
для случая обнаружения ошибок................................................. 56
94
2.16. Построение кодов с минимальным расстоянием d = 3.............. 57
2.17. Построение кодов с минимальным расстоянием d = 4.............. 60
2.18. Построение кодов с минимальным расстоянием d = 2.............. 62
2.19. Пример построения линейного кода, исправляющего
одиночные ошибки.................................................................... 63
2.20. Синдромное декодирование линейных кодов......................... 65
2.21. Алгоритм синдромного декодирования ................................ 68
2.22. Выводы по второму разделу ................................................ 70
3. Циклические коды.................................................................... 72
3.1. Определение циклического кода ........................................... 72
3.2. Многочлен с коэффициентами из конечного поля. Операции
над многочленами ..................................................................... 72
3.3. Порождающий многочлен циклического кода......................... 74
3.4. Определение параметров циклического кода по порождающему
многочлену............................................................................... 75
3.5. Кодирование циклических кодов........................................... 76
3.6. Систематическое кодирование циклических кодов................... 76
3.7. Сравнение алгоритмов кодирования и декодирования
циклических кодов.................................................................... 79
3.8. Синдромное декодирование циклических кодов...................... 79
3.9. Реализация операций над многочленами на сдвигающих
регистрах с обратными связями................................................... 82
3.10. Синтез схемы кодера для систематического кодирования........ 84
3.11. Синтез схемы декодера для случая обнаружения ошибок........ 85
3.12. Синтез схемы декодера для случая исправления одиночных
ошибок.................................................................................... 86
3.13. Выводы по третьему разделу ............................................... 90
Заключение................................................................................. 91
Библиографический список............................................................ 92
Приложение. Правило умножения вектора на матрицу...................... 93
95
Учебное издание
Марковский Станислав Георгиевич,
Тюрликов Андрей Михайлович
ЭЛЕМЕНТЫ ТЕОРИИ
ПОМЕХОУСТОЙЧИВОГО
КОДИРОВАНИЯ
Учебное пособие
Редактор В. П. Зуева
Компьютерная верстка С. Б. Мацапуры
Сдано в набор 29.04.14. Подписано к печати 24.12.14.
Формат 60×84 1/16. Бумага офсетная. Усл. печ. л. 5,9.
Уч.-изд. л. 6,3. Тираж 100 экз. Заказ № 678.
Редакционно-издательский центр ГУАП
190000, Санкт-Петербург, Б. Морская ул., 67
Документ
Категория
Без категории
Просмотров
0
Размер файла
5 393 Кб
Теги
markovskytyrlikov
1/--страниц
Пожаловаться на содержимое документа