Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf

В этом

случае

значение модуля J V = 5 + 1 = 6 И В соответствии с пер­

вым и

вторым

способами вычисления

контрольного кода получаем:

I-i'i способ

2-й способ

11011101

111

11011101 010

00100100

101

00100100 000

метричных каналов, так как

можно синтезировать код

с обнаружением

ошибок

произвольной кратности.

В любом другом

канале (в том числе ДСК) код с сум­

асимметричном

канале.

Для

получения такого кода

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

разрядам последовательно

приписы­

ваются веса 1, 2,

2 6 - 1 ,

1, 2,

2 6 - 1 ... В

качестве

Информационные разряды

Обратный код

суммы

1 2

4

1 2

4

1 2

4 8

1 1 0 1 0 1

• 1 1 1 0

Данный код позволяет обнаружить ошибку произвольной крат­

ности в асимметричном

канале и любую

вспышку ошибок

длиной

не

более 3 {е ь е2 , es] в произвольном канале (в том числе

в ДСК),

так

как ± e j ± 2 e 2 ± 4 e s = 0

только в том случае, если ei = e 2 =e 3 =0 .

которые

подмножества Л ' е У п , минимальное

расстояние

между

эле­

ментами

которых равно <1 Из данного

определения

следует,

что

эти

коды

не относятся к числу групповых

(или линейных)

кодов,

так

как не накладывается условие замкнутости подмножества

К от­

носительно некоторой операции. Поэтому

в данном

случае матричное

описание

кода с помощью порождающей

матрицы

G или контроль­

строк,

где т — мощность

кодового

подмножества,

и

п столбцов.

Вторая особенность рассматриваемых кодов заключается

в том,

что они имеют большое минимальное расстояние d^n/2.

Однако при

этом мощность

кодового подмножества (количество

кодовых

слов)

оказывается относительно небольшой и определяется

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

если d четно, то

2[d/{2d

— п)] при

2d>n^d;

(4-16

2а

при 2d =

/г;

(4-17)

если d нечетно, то

Например,

пусть

/1=20 разрядов,

rf=10,

тогда

т = 4 0 кодовых

слов, если же « = 2 0 ,

rf=12,

то т = 6 .

Практический

интерес

к

данным

кодам

связан,

прежде

всего,

с построением дешифраторов

с разделенной нагрузкой.

Матрицей

Адамара,

или

А„-матрицей,

называется

квадратная

(п X п)

матрица

\[ац\\,

элементами

которой

являются

1 и — 1 , а ее

строки

ортогональны, т. е.

Это название связано

с тем, что, как было

доказано

Адамаром,

определитель некоторой

матрицы пор'ядка п из элементов

± 1

дости­

гает максимального значения л " ' 2

тогда

и только тогда, когда

стро­

ки матрицы ортогональны.

А,,-матрица

порядка

п. (л четно)

обладает

следующим

заме­

чательным свойством. Если в А-матрнце

все элементы —1 заменить

на 0, то расстояние (по Хэммингу)

между любыми

двумя

ее строка­

ми будет в точности равно н/2.

Например,

1

1

1

А4

1—1

1—1

1

1—1—1

1 —1 —1

1

В качестве

кодовых

слов выберем

строки матрицы А4 (при этом

-1 заменяется

на 0), а также их дополнения

по модулю 2:

1 1 1 1

1 0

1 0

1 1 0

0

1 0

0 1

0

0 0 0

0

1 0 1

0

0J

1

0

1 1 0

Полученное

кодовое

множество

содержит

т = 2 - 4 = 8

слов, ми­

Таким образом, если известна А„-матрица, то аналогичным об­

разом

можно

построить код с параметрами: т = 2 л ,

d=n/2.

Если в кодовой

книге, построенной

вышеописанным способом

с

помощью

An-матрицы, вычеркнуть крайний правый столбец

(в

принципе

можно вычеркнуть любой столбец), то в полученном

коде минимальное расстояние

уменьшится на 1 и его параметры

равны: т=2п,

d=n/2—1. Обозначим длину кодовых

слов через п*=

=n — 1,

тогда

параметры кода

(выраженные через его длину) равны:

т=2(п*

+ \),

2d+\=n*,

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

оценке (4-19).

Прежде чем сформулировать

условие существования кодов, удов­

летворяющих

оценкам

(4-17)

и

(4-19), следуя В. И. Левенштейну,

можно сформулировать следующим образом: если d=2k,

n=2d=4k

или d—2k—1, re=4fe—1, то для справедливости

формулы

/п=2п=8/г

необходимо и достаточно, чтобы число k было

правильным.

Теперь необходимо рассмотреть метод построения кодов с за­

данными

п и d, соответствующими

оценкам

(4-16) и (4-18). Пусть

заданы

матрицы A=|la<jli и

В = ||6; д ||,

0 < t < m b

О^/г^/г,,

0 ^ / ^ m 2 , O ^ A ; ^ n 2 . Определим операцию

присоединения

матриц А

и'В

следующим

образом:

«11^,2

• • • « ! „ ,

^11*12

•••

Ып2

А +

В :

Я 2 | Я

2 2

• • - Я 2 л ,

^21^22

•••

Ь2п2

« m i «m2' • •атп.

^ п и ^ т г -

• - Ь,

П1Ла

где

т = м и н (т,,

т2). Операция присоединения

может быть выпол­

нена и над одной и той же матрицей,

например

А + А + А = З А .

В основу построения

рассматриваемых

ниже кодов

положен

рами

;t|, d\ и /П[, а

строки

матрицы

В — код с параметрами

п2, d2

и пг2,

то

строки

матрицы а А + 6 В ,

где а

и

Ь — целые неотрицатель­

ные числа, образуют код с параметрами

n =

ani+bn2;

d=ad\+bd2,

/я=мин {mi,

mi).

Если

2d>n^d

и

k=[d/(2d—я)],

где (И

означает

целую

часть

числа

х,

то алгоритм

построения

кода,

соответствующего оценкам

(4-16) и (4-18), будет следующим:

1.

По заданным

значениям

d, п и ft из системы

уравнений

ka + (ft +

1) 6 =

d;

(4-20)

(2k— 1) +

(2ft +

1) 6

вычисляются значения а и 6.

Т а б л и ц а

4-10

d

Условие

л

существо­

2d—л

*=

Щ

вания кода

Матрица

(число

пра­