<< Предыдущая

стр. 23
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>

еще понизить. Такая ситуация часто возникает, в вычислительных
сетях и в интернете. Типичное значение вероятности ошибки на бит
без кодирования в вычислительных сетях составляет 10˜6. Исполь-
зование простейших кодов с небольшой избыточностью позволяет
достигнуть вероятности 10˜9 и ниже.
Замечание. Требование к вероятности ошибки 10˜9 не является
чрезмерно завышенным. В вычислительных сетях, например, мо-
жет возникнуть обрыв связи в результате повреждения оптово-
локна при производстве земляных работ, небрежного подключения
кабеля к модему и т.д. Такой обрыв должен быть быстро обна-
ружен декодером, который в случае резкого возрастания частоты
переспросов выдает сигнал обрыва связи.
В последующих разделах идеи помехоустойчивого кодирования
будут подробно объяснены на примерах линейных блоковых кодов.
Здесь же мы рассмотрим простейшую модель передачи данных с
использованием помехоустойчивого кодирования (рис. 2.1).

Сообщение Кодовое слово

Кодер U Кодер
Источник



Кодирование
канала


Декодер
Декодер
Получатель 4-


Принятое слово
Декодированное
сообщение


Р и с . 2 . 1 . Модель к а н а л а связи с кодированием.


Будем исходить из того, что при передаче информации исполь-
зуется блоковый код Хэмминга1, структура которого будет подробно
раскрыта в дальнейшем. Сейчас мы ограничимся его табличным опи-
санием. Пусть кодер источника последовательно выдает информаци-
онные слова фиксированной длины. Кодер канала заменяет каждое
информационное слово и кодовым словом v в соответствии с табл. 2.1.
Передатчик генерирует сигналы, соответствующие кодовому сло-
ву v и посылает их в канал. Приемник производит обратное пре-
1
Ричард В. Хэмминг: 1915/1998, американский математик.
132 Глава 2. Линейные блоковые коды

Таблица 2.1. Кодовая таблица (7,4)-кода Хэмминга.

Информационное Кодовое Информационное Кодовое
слово слово слово слово
0000 000 0000 0001 101 0001
1000 П О 1000 1001 011 1001
0100 011 0100 0101 П О 0101
1100 101 1100 000 1101
1101
ООП
0010 111 0010 010 ООП
1010 001 1010 100 1011
1011
0110 100 О Н О 0111 001 0111
1110 010 1110 1111 111 1111



образование, в результате которого на декодер поступает двоичное
принятое слово г.
Декодер сравнивает принятое слово г со всеми кодовыми словами
табл. 2.1. Если слово г совпадает с одним из кодовых слов, то соот-
ветствующее информационное слово G выдается потребителю. Если
г отличается от всех кодовых слов, то в канале произошла обнару-
живаемая ошибка.2
Из всего вышесказанного уже можно сделать два важных вывода:
• Если в процессе передачи по зашумленному каналу кодовое
слово отобразится в другое кодовое слово, не совпадающее с
переданным, то происходит необнаружимая ошибка. Назовем
ее остаточной ошибкой декодирования.

• «Хорошие коды» обладают некоторой математической струк-
турой, которая позволяет эффективно распознать, а в некото-
рых случаях и исправлять ошибки, возникающие при передаче
информации по каналу связи.


2
Из структуры кода Хэмминга следует одно интересное свойство, которое может
быть проверенно простым перебором:
Для любого произвольного вектора г существует ближайшее кодовое слово,
которое или полностью совпадает с г или отличается от него только в одном
двоичном разряде. Таким образом, если в векторе v при передаче по каналу
произошла только одна ошибка, она всегда может быть исправлена в процессе
декодирования.- Прим. перев.
2.2. Порождающая матрица


2.2. Порождающая матрица
Важное семейство кодов образуют линейные двоичные блоковые ко-
ды. Эти коды замечательны тем, что представляя информационные
и кодовые слова в форме двоичных векторов, мы можем описать
процессы кодирования и декодирования с помощью аппарата линей-
ной алгебры, при этом, компонентами вводимых векторов и матриц
являются символы 0 и 1. Операции над двоичными компонентами
производятся по привычным правилам двоичной арифметики, так
называемой, арифметики по модулю 2 (Табл. 2.2).
Таблица 2.2. Арифметика по модулю 2.

Сложение Умножение

е 0 1 0 1
©
0 0 0
1 0 0
1 1 1 1
0
0



Замечание. С математической точки зрения, определив операции
с двоичными символами согласно таблице 2.2, мы построили поле
Галуа характеристики 2 первого порядка GF(2). Общая теория по-
лей Галуа позволяет строить поля характеристики р порядка т
- GF(pm), где р - простое, т - любое конечное целое. Переход к
расширенным полям GF(pm) дает возможность конструировать
коды, обладающие рядом новых свойств, полезных по сравнению с
двоичными кодами.
m
В частности, коды Рида-Соломона с символами из GF(2 ), m >
2 с успехом применяются для защиты информации в аудио, CD
проигрывателях (Полям Галуа и кодам Рида-Соломона посвящена
глава 5 данной книги).
Кодер двоичого блокового (п, /г)-кода отображает множество 2к
возможных двоичных информационных слов в множество 2к га-мерных
кодовых слов (в теории кодирования между этими множествами все-
гда существует взаимно однозначное соответствие) (см. рис. 2.2).
Вместо к бит информационного вектора в канал передаетсягабит
кодового вектора. В этом случае говорят об избыточном кодирова-
нии со скоростью
(2.1)
R=-.
т
Чем ниже скорость, тем больше избыточность кода и тем большими
Глава 2. Линейные блоковые коды

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

Кодовое
Информационное
слово
слово
V = (V0,V|,...,V,,.|)
| НЫ)
Кодер




Рис. 2.2. Кодер блокового (п, ?)-кода.

. Кодирование линейного блокового (п, &)-кода задается порожда-
ющей матрицей G/t Xn . В рассмотренном выше (7,4)-коде Хэмминга
порождающая матрица имеет вид

1 1 0 10 0 0
0 1 1 0 10 0 (2.2)
1 1 1 0 0 10
10 10 0 0 1
Таким образом, кодовое слово v и информационное слово и свя-
заны соотношением
v = u©G. (2.3)
Например, информационный вектор и = (1010) отображается в ко-
довый вектор

/1 10 1 0 00
0 110 10 0
v = (1010)0 = (0011010). (2-4)
1 110 0 10
V1 010 001

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

(2.5)
Gfcxn = (Pfcx(n-fc)
2.3. Сипдромное декодирование 135)

где нижние индексы обозначают размерность матрицы, а 1ц - еди-
ничная матрица размерности k x к.
Замечание. В литературе часто единичная матрица ставится на
первое место. Заметим, что перестановка столбцов матрицы не
оказывает никакого влияния на корректирующую способность кода.

Таким образом, в кодовом векторе систематического кода всегда
можно выделить информационные и проверочные символы

V=( • • Vn-l
• )• (2.6)
Щ .. Vn-k-1 Vn-k
n-fc проверочных символов к информационных символов

Роль проверочных символов и их использование будут подробно
разъяснены в следующих разделах.


2.3. Синдромное декодирование
Задача декодера заключается в том, чтобы используя структуру ко-
да, по принятому слову г, восстановить переданный информацион-
ный вектор.
Д л я рассмотренного выше (7, 4)-кода Хэмминга можно предло-
жить следующий алгоритм обнаружения ошибок. Так как рассмат-
риваемый код является систематическим, выразим каждый из трех
проверочных символов через символы информационного вектора VQ =
= v-s © «5 ® Щ, Vi = г>з © «4 Ф «5 и «2 = V4 © v$ © v&. ЕСЛИ в канале про-
изошла ошибка, то в принятом векторе г хотя бы одно из равенств не
будет выполняться. Запишем полученные проверочные соотношения
в виде системы уравнений для компонент вектора г:

го© 7-зФ г5ф г6ф = s0
П© г3® г4© г5© = «1 (2.7)
Г5Ф Г6© = S2-

Таким образом, из первых трех столбцов порождающей матрицы G
(2.2), мы получили систему трех проверочных уравнений, в которой
операция ф производится по правилам арифметики но модулю 2 (см.
табл. 2.2). Если в полученной системе уравнений хотя бы одна из
компонент {.so, si, S2} не равна нулю, то в канале произошла ошибка.
Запишем систему проверочных уравнений в общем виде. Для лю-
бого систематического кода с порождающей матрицей (2.5), прове-
рочная матрица определяется как

• (2-8)
H ( n _ f c ) x n = (i n _ f c pL(n-fc))' •
Глава 2. Линейные блоковые коды

где Hj.x(n_j.) - транспонированная матрица, т. е. матрица размерно-
сти к х (п — к), получаемая из Ркх(п-к) путем замены строк мат-
рицы на ее столбцы. Тогда систему проверочных уравнений можно
записать в в'иде
7
(2.9)
s =г0 Н


Вектор s принято называть синдромом. Таким образом, ошибка бу-
дет обнаружена, если хотя бы одна из компонент s не равна нулю.
Равенство (2.9) можно переписать в виде



(г 1 »-' ). (2.10)
S = Г©


Замечание. В медицине термин синдром используется для обозна-
чения сочетания признаков, характеризующих определенное болез-
ненное состояние организма.

<< Предыдущая

стр. 23
(из 50 стр.)

ОГЛАВЛЕНИЕ

Следующая >>