Файл: Кодирования.pdf

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ
Федеральное государственное бюджетное образовательное учреждение высшего образования
«САНКТ-ПЕТЕРБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ
им. проф. М. А. БОНЧ-БРУЕВИЧА»
С. С. Владимиров
МАТЕМАТИЧЕСКИЕ ОСНОВЫ
ТЕОРИИ ПОМЕХОУСТОЙЧИВОГО
КОДИРОВАНИЯ
Учебное пособие
Санкт-Петербург
2016

УДК 621.391(075.8)
ББК 32.88173
В 57
Рецензенты профессор кафедры СС и ПД, доктор технических наук О. С. Когновицкий;
ведущий инженер ЗАО «НПП «ИСТА-Системс», кандидат технических наук А. А. Березкин
Утверждено редакционно-издательским советом СПбГУТ
в качестве учебного пособия
В 57
Владимиров, С. С.
Математические основы теории помехоустойчивого кодирования : учеб- ное пособие / С. С. Владимиров ; СПбГУТ. — СПб, 2016. — 96 с.
ISBN 978-5-89160-131-4
Настоящее учебное пособие призвано ознакомить студентов старших курсов с математическими основами теории помехоустойчивого кодирования.
Предназначено для студентов, обучающихся по направлениям 11.03.02
«Инфокоммуникационные технологии и системы связи» и 09.03.01 «Инфор- матика и вычислительная техника».
УДК 621.391(075.8)
ББК 32.88173
ISBN 978-5-89160-131-4
c
Владимиров С. С., 2016
c
Федеральное государственное бюджетное образовательное учреждение высшего образования
«Санкт-Петербургский государственный университет телекоммуникаций им. проф. М. А. Бонч-Бруевича», 2016

СОДЕРЖАНИЕ
Предисловие
5 1.
Помехоустойчивое кодирование
6 1.1.
Основные параметры помехоустойчивых кодов
7 1.2.
Классификация помехоустойчивых кодов
8
Контрольные вопросы
10 2.
Элементы двоичной алгебры
11 2.1.
Понятие системы счисления. Основные системы счисления
11 2.2.
Перевод чисел между системами счисления
13 2.3.
Операции над двоичными числами
17
Контрольные вопросы
. . . . . . . . . . . . . . . . . . . . . . . . 26 3.
Матрицы и действия над ними
. . . . . . . . . . . . . . . . . 27 3.1.
Понятие матрицы
. . . . . . . . . . . . . . . . . . . . . . . . 27 3.2.
Операции с матрицами
. . . . . . . . . . . . . . . . . . . . . 29
Контрольные вопросы
31 4.
Элементы комбинаторики
. . . . . . . . . . . . . . . . . . . . 32
Контрольные вопросы
. . . . . . . . . . . . . . . . . . . . . . . . 32 5.
Полиномы и действия над ними
. . . . . . . . . . . . . . . . . 33 5.1.
Операции с полиномами
. . . . . . . . . . . . . . . . . . . . . 34
Контрольные вопросы
. . . . . . . . . . . . . . . . . . . . . . . . 35 6.
Понятие группы, кольца и поля
. . . . . . . . . . . . . . . . . 36 6.1.
Группа
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 6.2.
Подгруппы и смежные классы
. . . . . . . . . . . . . . . . . . 38 6.3.
Кольцо
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 6.4.
Поле
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Контрольные вопросы
41 7.
Математика полей Галуа
. . . . . . . . . . . . . . . . . . . . 42 7.1.
Поле Галуа и его свойства
. . . . . . . . . . . . . . . . . . . . 42 7.2.
Основные действия над элементами поля
47 7.3.
Алгоритмы для проведения расчетов в двоичных полях Галуа и их реализации
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
Контрольные вопросы
. . . . . . . . . . . . . . . . . . . . . . . . 66 3

8.
Элементы теории графов
. . . . . . . . . . . . . . . . . . . . 67 8.1.
Основные понятия
67 8.2.
Матричное представление графа
. . . . . . . . . . . . . . . . . 70 8.3.
Линейные графы сигналов и передача графа
73
Контрольные вопросы
. . . . . . . . . . . . . . . . . . . . . . . . 77 9.
Модели каналов передачи данных
78 9.1.
Параметры моделей каналов ПД
. . . . . . . . . . . . . . . . . 79 9.2.
Двоичный симметричный канал
. . . . . . . . . . . . . . . . . 80 9.3.
Двоичный симметричный канал со стираниями
. . . . . . . . . . 82 9.4.
Двоичный несимметричный канал (Z-канал)
. . . . . . . . . . . 83 9.5.
Канал Гилберта–Эллиотта
. . . . . . . . . . . . . . . . . . . . 84 9.6.
Модель канала Поля
. . . . . . . . . . . . . . . . . . . . . . 86 9.7.
Канал с аддитивным белым гауссовским шумом
. . . . . . . . . 88
Контрольные вопросы
. . . . . . . . . . . . . . . . . . . . . . . . 89
Заключение
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
Список литературы
91 4

ПРЕДИСЛОВИЕ
При разработке систем передачи данных одним из важнейших этапов является выбор методов повышения достоверности при передаче информа- ционных сообщений по каналам связи. Использование избыточных помехо- устойчивых кодов является одним из наиболее эффективных методов борьбы с ошибками при передаче дискретных сообщений по каналам связи. Соответ- ственно, вопросам изучения теории помехоустойчивого кодирования прида- ется большое внимание в программах подготовки бакалавров и магистров,
обучающихся по специальностям из области телекоммуникаций.
В настоящем пособии приведены основы математического аппарата, ко- торый используется при изучении теории помехоустойчивого кодирования,
исследовании алгоритмов кодирования и декодирования, разработке и по- строении кодеров и декодеров приемопередающих устройств.
Пособие состоит из девяти разделов. В разд. 1 рассмотрены основные понятия и классификация помехоустойчивых кодов. Разд. 2 посвящен осно- вам двоичной алгебры и реализации основных операций над двоичными чис- лами. В разд. 3 описаны матрицы и основные действия над ними. В разд. 4 при- водятся основные понятия комбинаторики. В разд. 5 — полиномы и основные операции с полиномами. Разд. 6 посвящен понятиям группы, кольца и поля, а в разд. 7 описан основной математический аппарат блочных помехоустойчи- вых кодов (Боуза–Чоудхури–Хоквингема и Рида–Соломона) — двоичные по- ля Галуа. В разд. 8 приводятся основы теории графов. В разд. 9 рассмотрены основные модели каналов передачи данных.
5

1. ПОМЕХОУСТОЙЧИВОЕ КОДИРОВАНИЕ
Помехоустойчивое кодирование (англ. Error Correcting Coding,
ECC) — процесс преобразования информации, предоставляющий возмож- ность обнаружить и исправить ошибки, возникающие при передаче инфор- мации по каналам передачи данных.
Под ошибкой при этом понимают ситуацию, когда в результате дей- ствия помех и искажений в канале передачи данных приемник принимает неверное решение, отождествляя принятый сигнал не с фактически передан- ным символом, а с каким-либо другим [
1
].
Процесс помехоустойчивого кодирования заключается во введении из- быточности, т. е. для передачи информации используется код, у которого используются не все возможные комбинации, а только некоторые из них. Та- кие коды называют избыточными или корректирующими.
Соответственно, процесс введения избыточности (преобразование ин- формационных символов в кодовое слово) называется кодированием, а об- ратный процесс восстановления информации из кодового слова, возможно со- держащего ошибки, — декодированием.
В рамках цифровой системы передачи данных задачи кодирования и де- кодирования возложены на кодер и декодер соответственно. Структура циф- ровой системы передачи данных показана на рис.
1.1
[
2
].
Источник данных
Кодер
Модулятор
Физический канал
Демодулятор
Декодер
Получатель данных
Помехи n
(t)
Двоичные данные
S
(t)
ˆ
S
(t)
Двоичные данные
Дискретный канал
Информация о надежности
Рис. 1.1. Структура цифровой системы передачи данных
Часто декодеру доступна информация, указывающая на надежность ре- шений, принимаемых о различных символах кодового слова. Такая информа- ция может быть использована для упрощения процесса декодирования, либо для улучшения его характеристик [
2
].
В целом, способность помехоустойчивых кодов определять и исправ- лять ошибки — их корректирующие свойства — зависит от правил постро-
6

ения этих кодов и параметров кода (числа разрядов, избыточности и др.), а также от используемых алгоритмов декодирования.
1.1. Основные параметры помехоустойчивых кодов
Основными параметрами, характеризующими корректирующие свой- ства кодов являются:
1) избыточность кода;
2) кодовое расстояние;
3) кратность гарантированно обнаруживаемых ошибок;
4) кратность гарантированно исправляемых ошибок.
1.1.1. Избыточность корректирующего кода
Избыточность корректирующего кода может быть абсолютной и отно- сительной. Под абсолютной избыточностью понимают число вводимых до- полнительных разрядов r
= n − k,
где n — число кодовых символов на выходе кодера, соответствующих k ин- формационным символам на его входе.
Относительной избыточностью корректирующего кода называют ве- личину
R
отн
=
r n
=
n
− k n
= 1 −
k n
С ней связана так называемая относительная скорость передачи ин- формации или скорость кода, которая показывает, какую часть общего чис- ла символов кодовой комбинации составляют информационные символы.
k n
= 1 − R
отн
Если производительность источника равна H символов в секунду, то скорость передачи после кодирования этой информации будет равна
R
= H ·
k n
1.1.2. Кодовое расстояние
Кодовое расстояние d или расстояние Хемминга характеризует cте- пень различия любых двух кодовых комбинаций. Оно выражается числом раз- рядов, в которых комбинации отличаются одна от другой.
Чтобы получить кодовое расстояние между двумя комбинациями дво- ичного кода, достаточно подсчитать число единиц в поразрядной сумме этих
7

комбинаций по модулю 2:
10011 ⊕ 11001 = 01010
⇒
d
= 2.
Кодовое расстояние может быть различным. Так, в первичном натураль- ном безызбыточном коде это расстояние для различных комбинаций может различаться от единицы до n, где n — длина (значность) кода.
Для помехоустойчивого кода наиболее важным является минимальное кодовое расстояние d min
— наименьшее кодовое расстояние из всех между всеми парами кодовых комбинаций.
В безызбыточном коде все комбинации являются разрешенными,
d min
= 1. Поэтому искажение хотя бы одного символа в комбинации будет приводить к получению ошибочного сообщения.
1.1.3. Кратности гарантированно обнаруживаемых и гарантированно исправляемых ошибок
Эти параметры напрямую зависят от минимального кодового расстоя- ния. Под кратностью понимается количество поражённых ошибками симво- лов кодовой комбинации.
В общем случае при необходимости обнаруживать ошибки кратности t
обн минимальное кодовое расстояние должно быть, по крайней мере, на еди- ницу больше t обн
, т. е.
d min
≥ t обн
+ 1.
Соответственно, кратность гарантированно обнаруживаемых кодом оши- бок равна t
обн
≤ d min
− 1.
Кратность гарантированно исправляемых кодом ошибок вычисляет- ся по формуле t
≤
d min
− 1 2
Таким образом, код, имеющий минимальное кодовое расстояние d
min
= 3, позволяет гарантированно обнаружить t обн
= 2 и менее ошибок и гарантированно исправить t = 1 ошибку.
1.2. Классификация помехоустойчивых кодов
Помехоустойчивые коды классифицируются по различным признакам.
Одной из основных классификаций является деление кодов на блочные и непрерывные.
8

Блочный (блоковый) код является кодом без памяти. Кодер блочного кода отображает подающийся на вход блок информационных символов дли- ной k в кодовую последовательность из n выходных символов. Термин «без памяти» указывает, что каждый блок из n символов зависит только от соот- ветствующего блока из k символов и не зависит от других блоков [
2
].
Основыми параметрами блочных кодов являются длина информацион- ного блока k, длина кодового слова n, скорость кода k
n и минимальное кодовое расстояние d min
Непрерывные или древовидные коды — это помехоустойчивые ко- ды использующие непрерывную, или последовательную, обработку информа- ции короткими фрагментами (блоками). Кодер древовидного кода является устройством с памятью. На его вход поступают наборы из k входных инфор- мационных символов, а на выходе появляются наборы из n кодовых символов.
Каждый набор n кодовых символов зависит от текущего входного набора и от v предыдущих входных символов. Следовательно кодер должен содержать устройство памяти на m = k + v входных символов. Параметр m часто назы- вают длиной кодового ограничения кода [
2
].
Также непрерывные коды характеризуются скоростью кода k
n и свобод- ным расстоянием d св
[
2
].
Чаще всего используются линейные древовидные коды, называемые сверточными.
Особое место в классификации помехоустойчивых кодов занимают кас- кадные коды и турбо коды, представляющие из себя комбинации блочных и/или непрерывных кодов [
3
].
Другой подход к классификации делит коды на линейные и нелиней- ные. Линейные коды образуют векторное пространство, в котором два кодо- вых слова при сложении по определенному правилу дают в результате третье кодовое слово [
2
].
Практически все применяемые на практике схемы кодирования осно- ваны на использовании линейных кодов. Двоичные линейные блоковые коды часто называют групповыми кодами, так как их кодовые слова образуют ма- тематическую структуру, называемую группа [
2
].
Нелинейные коды применяются гораздо реже линейных. К нелинейным кодам относится код с контрольным суммированием, в котором провероч- ные разряды являются записью суммы единиц в кодовой комбинации [
1
].
По способу кодирования коды делятся на систематические и несисте- матические. В первом случае информационные символы передаются на вы- ход декодера без изменения и к ним добавляются проверочные символы. В
9

случае несистематического кодирования информационные символы в явном виде в кодовом слове отсутствуют.
Большинство помехоустойчивых кодов может быть использовано как для обнаружения, так и для исправления ошибок, хотя есть коды, которые позволяют лишь обнаруживать ошибки. Поскольку избыточность, требуемая для обнаружения ошибок, меньше избыточности для исправления ошибок, то коды с обнаружением ошибок часто используют в системах с обратной связью
[
1
].
Ещё одним вариантом деления помехоустойчивых кодов является раз- деление их на коды, исправляющие случайные ошибки, и коды, исправля- ющие пакеты (пачки) ошибок. Хотя для исправления пачек ошибок было разработано большое количество кодов с хорошими характеристиками, часто оказывается выгодным использовать коды, исправляющие случайные ошиб- ки, совместно с устройствами перемежения/деперемежения [
2
]. Также стоит отметить, что существуют алгоритмы декодирования, позволяющие исполь- зовать коды, рассчитанные на исправление случайных ошибок, для исправ- ления пачек ошибок без использования перемежителей. К таким алгоритмам относится, например, мажоритарное декодирование на основе двойственного базиса [
4
].
Контрольные вопросы

1. Что такое помехоустойчивое кодирование?
2. Опишите структуру цифровой системы передачи данных.
3. Дайте понятие избыточности корректирующего кода. Что такое аб- солютная и относительная избыточности? Как определяется скорость кода?

4. Что такое кодовое расстояние? Как оно определяется?
5. Как рассчитываются кратности гарантированно обнаруживаемых и гарантированно исправляемых ошибок?
6. Приведите классификацию помехоустойчивых кодов.
10

2. ЭЛЕМЕНТЫ ДВОИЧНОЙ АЛГЕБРЫ
2.1. Понятие системы счисления. Основные системы счисления
Под системой счисления как правило понимают совокупность приемов записи и наименования чисел [
5
].
Системы счисления разделяют на непозиционные, в которых значение цифры не зависит от ее положения в записи числа, и позиционные, где значе- ние каждой цифры изменяется с изменением ее позиции в числе [
5
].
На сегодняшний день в основном используются позиционные системы счисления. Главной характеристикой позиционной системы можно считать основание системы счисления p, определяющее количество цифр/знаков (от
0 до p − 1), использующихся для записи чисел. Сами цифры 0 . . . p − 1 называ- ются базисными числами [
5
,
6
].
Любое число N в системе счисления представляется в виде комбина- ции степеней основания p с коэффициентами (цифрами) a i
, относящимися к множеству базисных чисел 0 . . . p − 1, как показано в формуле a
k p
k
+ a k
−1
p k
−1
+ . . . + a
1
p
+ a
0
,
и сокращенно записывается в виде (a k
a k
−1
. . . a
1
a
0
)
p
[
6
].
В настоящее время широко используются четыре системы счисления.
1. Десятичная система счисления — позиционная система счисления с основанием 10. Для записи чисел в десятичной системе используются циф- ры: 0, 1, . . . , 9. Это основная система счисления, использующаяся повсеместно
[
5
].
2. Двоичная система счисления — позиционная система счисления с основанием 2. Для записи чисел в двоичной системе используются две цифры:
0 и 1 [
5
]. Каждая цифра двоичного числа соответствует в десятичной системе счисления двойке в степени, равной номеру позиции цифры слева. В табл.
2.1
приведены значения первых двенадцати степеней.
Таблица 2.1
Степенной ряд двойки (до 12-й степени включительно)
Показатель степени
1 2
3 4
5 6
7 8
9 10 11 12
Значение
2 4
8 16 32 64 128 256 512 1024 2048 4096 3. Восьмеричная система счисления — позиционная система счисле- ния с основанием 8. Для записи чисел используются цифры: 0, 1, . . . , 7 [
5
]. Ис- пользуется, например, в некоторых справочниках для представления полино- мов.
4. Шестнадцатеричная система счисления — позиционная систе- ма счисления с основанием 16. Для записи чисел используются цифры:
11

0, 1, . . . , 9, A, B,C, D, E, F [
5
]. Широко используется в программировании и те- лекоммуникациях, так как позволяет компактно и удобно представлять длин- ные двоичные последовательности.
Также стоит отметить так называемую двоично-десятичную систему счисления, в которой каждая цифра десятичного числа записывается соот- ветствущим ей двоичным четырехразрядным числом. Эта система счисления используется в ЭВМ как промежуточная при преобразовании десятичных чи- сел в двоичные [
5
].
Для того, чтобы отличать числа в разных системах счисления (если надо записывать их вперемешку), используется несколько способов.
1. В конце числа указывается нижний индекс со значением основания системы счисления.
2. В конце числа указывается нижний индекс с названием системы счис- ления. Обычно используются первые три буквы латинского названия.
3. После числа указывается буквенный постфикс. Обычно используют первую букву латинского названия.
4. Перед числом указывается определенный префикс.
Последние два способа записи широко применяются в информатике, в частности в программировании, где невозможно использовать верхние и ниж- ние индексы.
В табл.
2.2
показаны примеры различной записи чисел в разных системах счисления. Приведены только некоторые формы записи. В различных языках программирования и языках разметки могут использоваться другие префик- сы и постфиксы. Также необходимо отметить, что при записи десятичных чисел постфиксы и префиксы не используются. Число без них по умолчанию считается десятичным, если иное не следует из контекста.
Таблица 2.2
Формы записи чисел в различных системах счисления
Основание
Ниж. индекс
Ниж. индекс
Постфикс
Префикс системы со значением с названием
2 1010 2
1010
bin
1010b
0b1010 8
1724 8
1724
oct
1724o
0o1724 10 1942 10 1942
dec
—
—
16 3AF5 16 3AF5
hex
3AF5h
0x3AF5 12