Файл: Теория и техника передачи данных и телеграфия учебник..pdf

комбинации

V„ сведя его к умножению

кодовой

комбинации

на проверочную матрицу по правилам умножения

матриц

ViHf„,b),

где Н(в, к) — транспонированная

матрица

Н ( п , *>. Если

комбинация

Vt принадлежит коду, то в результате умножения

получим

(п — /г)-разрядный нулевой вектор. Если

ж е

VL

коду

не принадлежит, то в результате

произведения

получим

(n—k)-

разрядный ненулевой вектор. На основе произведения

V^Jn.k)

строится процедура декодирования групповых кодов.

Каноническая

форма

матрицы

Н ( „ , *> имеет

вид

Н(л, *) = П ( л - й ) R ( n - f c ) > - * ] .

где \n~k — единичная матрица из

п — k

строк

и

п — k

столб­

цов, занимающая

места,

которые

соответствуют

избыточным

элементам

кодовой

комбинации;

R , „

х * — матриц а из

n — k

строк и k

столбцов,

расположенная на местах,

соответствующих

информационным

элементам.

Каждая строка матрицы R' указывает, какие информацион­

ные элементы кодовой комбинации входят в

проверочное со­

отношение. Вид

матрицы

R'

устанавливается

на

основе

сле­

дующей

теоремы.

Теорема

6.3.

Если

G ( n ,

=

[ R * x m-*) I * ]

— порождающая

порождающей

матрицы

G ( „ , на

Н (

л , * ) , т. е.

умножение G ( „ , и)

на Н(л.*) дает

нулевую

матрицу

из

k строк

и n — k столбцов:

G ( n , *) Н(„, ft)

= 0.

Решение

данного

матричного

уравнения

и

позволило

установить

вид

проверочной матрицы,

т. е. то,

что

b ( n - f t ) X f t =

RftX(n—ft).

Итак,

между порождающей

и

проверочной

матрицами

ной из матриц можно построить другую. Например, для

рассмот­

ренного

выше

(5,3)-кода

проверочные векторы

имеют вид

0 1 0

1 1

(а 4 + а 2 + а , = 0 ) и

1 0

1 1 0

(а5 + а 3 + а 2

= 0 ) .

Прове­

рочная

матрица

в канонической

форме

равна

1

0

1

1

01

н (5.3)

і

о

і

і

Здесь

№

р'

—

пг

= І2

" • 2 Х З ~ ~ ^ 3 X 2

" 1 0

0

1 Я =

0

1

0

.0

0

1 .

и

приписываем к ней слева

матрицу

1

0"

^ 3 / 2

~

*

'

'

-0

1 .

полученную

из R ^ x 3 переменой

строк

и столбцов местами.

В

результате

получим

" 1 0

1

0

0

0 ( 5 , з > =

1 1 0

1 0

-

0

1

0

0

1 .

Эффективность использования

корректирующего

кода

для

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

рас­

стояния. Желательно уметь вычислять duaH,

не рассматривая

всех

кодовых

комбинаций. Дл я групповых кодов

существует

сравнительно простой способ

определения dultH

по виду

матри­

цы

проверок,

основанный

на

использовании

соотношения

F j H ( n , *) = 0. Процедура

умножения

кодовой

комбинации

на

матрицу

W{n,k)

сводится

к сложению тех строк

матрицы

Н{п,*>,

которым

соответствуют

единицы

комбинации

Vt.

Так как в результате

умножения

кодовой

комбинации

на

матрицу

H(n.k)

должен быть

получен

нулевой

(п —

k)-разряд­

ный

вектор, то, следовательно, суммируемые

строки

матрицы

Н^, k)

являются

линейно-зависимыми. Значит, каждой

кодовой

комбинации веса w соответствует

w линейно-зависимых

столб­

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

комбина­

ция Vi

трансформировалась

в принятую Vi.

Инвертируя эле­

менты

V/, соответствующие

единицам в

получаем

передан­

строки, которой принадлежит принятая комбинация. Эта

зада­

ча решается

вычислением

произведения VI Н[„, *}

= SL, называ­

емого синдромом.

Покажем, что каждой

строке

таблицы

де­

кодирования

соответствует

свой

синдром:

Si

= V/Hln,k)

=

(Vl + Ei)^{n,k)

=

Так как

варианты ошибок Et в первом

столбце

различны,

то и произведение

EiH[n,k),

являющееся (я—&)-разрядным век­

тором, для

различных Et различно и может

принимать всего

2"~* различных значений,

т. е. для каждой строки таблицы

существует

свой

синдром,

определяемый

видом

варианта

ошибок.

принятой

комбинации.

2.

Суммируя

по модулю 2

предполагаемый

вариант

ошибок

с принятой комбинацией, получают переданную комбинацию.

При данной процедуре декодирования количество исправляе­

мых

вариантов

ошибок

определяется числом

строк

таблицы

декодирования

и равно

2 П _ Й — 1 .

Для того чтобы код исправлял все варианты ошибок крат­

кости

до

t

включительно,

необходимо

выполнить

условие

t

2 ™ *

> 2

Сп,

известное

под

названием

границы Хемминга.