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

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

ОГЛАВЛЕНИЕ

Следующая >>

Пример: Синдромное декодирование (7, 4)-кода Хэмминга.

Используя (2.5) и (2.8), построим проверочную матрицу из по-
рождающей матрицы кода Хэмминга (2.2). Она имеет вид


/10 0 10 11
(2.11)
Н3х7= 0 10 1110
\0 0 10 1 11


При передаче информационного слова и = (1010) по каналу без шу-
ма г = v = (0011010). Можем убедиться, что в этом случае синдром
равен

/1 0 0
01 0
1
00
=(000).
11 (2.12)
s =(0011010)© 0
01 1
11 1
о \)
Если, например, в кодовом слове произошла одиночная ошибка на
2.3. Синдромное декодирование

Таблица 2.3. Таблица синдромов однократной ошибки (7,4)-
кода Хэмлинга.

Кодовое слово г гз re .
тъ
П) ГА
Г1 Г2

010 001 ПО 011 101
Синдром s 100 111




четвертой позиции (г = (0010010)), то синдромом является четвертая
строка транспонированной проверочной матрицы

/1 0 0\
0 10
0 01
= (но). (2.13)
1 10
s = (0010010) ©
0 11
1 11
V1 0 1/
Перебрав вес возможные позиции одиночной ошибки, получим пол-
ную таблицу синдромов однократных ошибок - таблицу соответ-
ствий номера ошибочного разряда получающемуся при этом синдро-
му (табл. 2.3). Можно заметить, что ошибке в г-ой позиции кодового
слова соответствует синдром, образованный г-ым столбцом матрицы
Н. Так как все столбцы матрицы различны, мы можем с помощью
таблицы 2.3 исправлять одиночную ошибку, вносимую каналом.
Обобщим приведенные выше рассуждения, используя аппарат
линейной алгебры.


л- мерное двоичное
векторное пространство с
арифметикой по модулю 2




Рис. 2.3. Структура кодовых векторных пространств.
Глава 2. Линейные блоковые коды

Исходным материалом для построения кодовых копструкций слу-
жит п -мерное двоичное векторное пространство, в котором заданы
операции арифметики по модулю 2 (табл. 2.2).
к
В него вложено fc-мерное линейное пространство, содержащее 2
кодовых слов (рис. 2.3). Код С образуется с помощью 2 комбинаций
линейно независимых базисных векторов {gi, • • • ,g/t}- Иногда
к
говорят, что код С «натянут» на векторы {gi,... , gfc}. Эти векторы
образуют строки порождающей матрицы кода С

gl #1,1 s i , 2 • • • g\,n
02,1 52,2 • • • <?2,n
= (Pfcx(n-fc)-I*)- (2-14)
g2
9k,2 ••• 9k,n)

\ gfc
Заметим, что порождающая матрица может быть разложена на мат-
рицу Р и единичную матрицу I только в случае систематических
кодов.
Для кода С существует дуальный код Сд такой, что скалярное
произведение любой пары векторов, один из которых принадлежит
пространству С, а другой пространству С^, всегда равно нулю.
Это значит, что векторы кода С^ ортогональны векторам кода С. С
другой стороны, если некоторый вектор ортогонален всем векторам
кода С, то он принадлежит коду Cj, и наоборот.
Дуальное векторное подпространство «натянуто» на. п — к ли-
нейно независимые базисные векторы { h i , . . . ,h n _jt}- Эти векторы
образуют строки проверочной матрицы

\
hi
h2
(2.15)
Н (п—кух.п '

К-к/

(In-fc




причем, правая часть равенства справедлива только для системати-
ческих кодов.
При синдромном кодировании приемник использует свойство ор-
тогональности кодов
G © H T = O. (2.16)
2.3. Синдромное декодирование I39J

Таким образом, для каждого кодового слова v 6 С справедливо
T
s =v © H = O. (2.17)

Каждому принятому слову, не принадлежащему коду, соответствует
отличный от нуля синдром

8 =г©Нт/0дляг^С. (2.18)

Проведем анализ синдромного декодирования на уровне двоичных
компонент (рис. 2.4). В канале производится покомпонентное сложе-
ние по модулю 2 кодового вектора v с двоичным вектором ошибки е.
Таким образом, если г'-ая компонента вектора г равна «1», то в г-ой
компоненте кодового вектора v возникает ошибка.
В рассмотренном выше примере, единичной ошибке в четвертом
разряде соответствует вектор е = (0001000).
Замечание. Операция сложения по модулю 2 двоичных символов
эквивалентна операции «исключающего или» XOR.

Кодовое слово j ^ ^ Принятое слово

г = v®e и
Кодер Декодер

I•
Информационное •
слово Шумовое слово Декодированное
слово

Р и с . 2.4. Модель передачи информации на двоичном
уровне.

В силу свойств линейности и ортогональности векторов имеем

s =r © H T = ( v © e ) © H T =e © H T . (2.19)

Последнее равенство является основой синдромного декодирования.
В процессе декодирования могут возникнуть следующие ситуации:

Случай 1: s = 0 • е е С
»
Случай 1.1: е = 0 - безошибочная передача информации;
Случай 1.2: е ф 0 - передача информации с неисправляемой
ошибкой;
Глава 2. Линейные блоковые коды

Случай 2: s ^ О Ф е ^ С
> ошибка будет обнаружена при декоди-
ровании.

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

• Распознавание ошибок. Декодер всегда определяет наличие ошиб-
ки в принятом векторе г. В зависимости от требований потре-
бителя, принятое информационное слово или «стирается», или
производится запрос на его повторную передачу.

• Коррекция ошибок. Корректирующая способность декодера мо-
жет быть пояснена на примере (7,4)-кода Хэмминга, рассмот-
ренного выше.

Таблица 2.3 показывает, что в случае одночной ошибки, ее пози-
ция однозначно определяется по синдрому, и, таким образом, одно-
кратная ошибка всегда исправляется. Ошибки же большей кратно-
сти декодер всегда исправляет как одиночные, и потребителю выда-
ется ошибочное информационное слово. Пусть, например, передает-
ся кодовое слово ,v = (0011010), соответствующее информационному
вектору и = (1010), и вектор ошибки равен е = (1100000), т.е. в
канале произошла двукратная ошибка. Тогда для принятого слова
г = (1111010) синдром равен s = (110). Из табл. 2.3 следует, что этот
синдром соответствует четвёртой ошибочной компоненте вектора г.
Таким образом, потребителю будет выдан вектор й = (0010).
Декодер может выдавать потребителю ошибочное информацион-
ное слово тогда и только тогда, когда в канале произошли необнару-
жимые ошибки, или кратность канальной ошибки превышает кор-
ректирующую способность кода. Из рассмотренного выше примера
следует, что эффективность конкретного кода зависит от области
его применения и, в особенности, от канала, связи. Если мы переда-
ем информацию по каналу с аддитивным белым гауссовским шумом
(АБГШ), то ошибки в кодовом слове независимы. Если при этом от-
ношение сигнал/шум достаточно велико, то вероятность одиночной
ошибки во много раз превышает вероятность ошибок высших крат-
ностей, поэтому, использование в таком канале кода Хэмминга с ис-
правлением однократной ошибки может оказаться весьма эффектив-
ным. С другой стороны, в каналах, где преобладают многократные
2.4- Свойства линейных блоковых кодов


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


2.4. Свойства линейных блоковых кодов
В предыдущих разделах на примере (7,4)-кода Хэмминга были пока-
заны основные свойства линейных блоковых кодов и приведен метод
синдромного декодирования. Теперь возникает следующий вопрос:
Чем отличаются «хорошие» коды от «плохих» и как их искать? В
следующих параграфах, раскрывая структуру линейных кодов более
подробно, мы постараемся коротко сформулировать ответ на этот во-
прос.

2.^.1. Расстояние Хэмминга и корректирующая
способность
Для лучшего понимания процесса декодирования будем использо-
вать геометрическое представление векторного пространства. На
рис. 2.5 показан сектор n-мерного двоичного векторного простран-
ства. В нем особое место занимает я-мерный кодовый вектор 0, ко-
торый всегда принадлежит любому линейному коду (это следует из
свойств линейных кодов). Здесь же показаны п-мерные кодовые век-
торы vi,v2,V3, обозначенные символами «о». Возможные принимае-
мые векторы г обозначены символами «х». Области декодирования
кодовых слов vi,уз, V3 показаны как окружности с центрами в точ-
ках, соответствующих изображениям этих кодовых слов на плоско-
сти. Это значит, что если принятый вектор г находится, например,
внутри затемненной области (рис. 2.5), то декодер выдаст потреби-
телю кодовое слово vi. 1
Пусть в канал посылается слово vi. В результате искажения в ка-
нале могут иметь место три варианта приема и декодирования (рис. 2.5).

• В первом случае, вектор ошибки ei отображает переданный
вектор в точку, принадлежащую области декодирования vi.
Декодер выдает потребителю переданное слово vi, исправляя
при этом возникающие в канале ошибки.
Представление n-мерных векторов точками на плоскости не должно смущать
читателя, т.к. такое наглядное описание кодов позволяет только лучше понять
их свойства и никакой другой цели перед собой не ставит. Прим. перев.
142 Глава 2. Линейные блоковые коды


Во втором случае, вектор ег переводит переданный вектор vi
в область декодирования V2. Таким образом, потребителю вы-
дается ошибочное слово V вместо vi. Тем не менее, ошибка
2
распознается, так как принятый вектор Г2 не является кодо-
вым словом.

В третьем случае, вектор ошибки ез отображает переданное
слово в ошибочное кодовое слово V3. Имеет место необнару-

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

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

ОГЛАВЛЕНИЕ

Следующая >>