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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 09.04.2024

Просмотров: 271

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
Рис. 6.3.

отличающиеся от нее в t элементах и менее. Любая комбинация

с* ошибками отличается от переданной в f элементах, а ог

другой кодовой комбинации — в 2t+\ —?>t элементах и поэтому будет отождествлена декодирующим устройством с переданной комбинацией. Если ж е dymH<^2t, то возможен хотя бы один слу­ чай, когда сшибка кратности t трансформирует переданную ком­ бинацию в такую запрещенную комбинацию, которая столь же близка к одной из непередававшихся разрешенных комбинаций, как и к переданной (рис. 6.3).

Аналогичными рассуждениями можно показать, что для од­ новременного исправления всех ошибок кратности до t включи­ тельно и обнаружения всех оши­

бок

кратности до

s^-t

необхо-

димо

и достаточно,

чтобы

выпол­

нялось уСЛОВИе Ямин ^ + S + 1. Приведенные результаты име­

ют общий характер. Они справед­

ливы

для любого корректирую­

щего

кода,

удовлетворяющего

единственному

условию

NK<Na.

То или иное использование потен­ циальной корректирующей спо­ собности кода реализуется только при удачном выборе разрешен­ ных и запрещенных комбинаций в коде, т. е. зависит от структур­ ных свойств кода.

В зависимости от требований, предъявляемых к корректирующему коду в конкретной системе передачи дискретной информации, возможны следующие различ­ ные задачи, связанные с особенностями построения корректи­ рующих кодов:

—при заданных я и k построить код с максимальным зна­

чением минимального кодового расстояния d M I I H ;

—

по заданным

я и d M H H

построить код с максимальным k;

—

по заданным

k

и d^,ma

построить код с минимальным я;

—

по заданным

 

г

и djnra найти код с максимальным k и ряд

других задач.

Указанные задачи требуют отыскания функциональной зави­

симости между основными параметрами кода я, k

и d M I , H .

6.1.3. Классификация

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

кодов

Все корректирующие коды могут быть подразделены на два обширных класса — блоковые и непрерывные коды.

Блоковыми называют такие коды, в которых каждому от­ дельному сообщению соответствует кодовая комбинация (блок) из определенного числа элементов.

Непрерывными называют такне коды, в которых операция кодирования и декодирования производится непрерывно над всей последовательностью элементов, составляющих сообщение. Деление передаваемой информации (сообщения) на блоки в этом случае отсутствует.

Блоковые коды в свою очередь делятся на разделимые и не­ разделимые. Разделимыми называют такие коды, в которых из­ вестны места информационных и избыточных элементов. В не­ разделимых кодах не известно, какие элементы относятся к информационным, а какие к избыточным. Очень часто в разде­ лимых кодах избыточные и информационные элементы связы­ ваются между собой системами линейных проверочных соотно­ шений. Такие разделимые коды принято называть систематиче­ скими кодами. Избыточные элементы в систематических кодах

ноды

6лемоб°/>/е

Не/Оаэделг/мь/е

Рис. 6.4.

обычно вводятся как результат проверки на четность определен­ ной совокупности информационных элементов. В силу этого избы­ точные элементы кодовой комбинации называют проверочными.

На рис. 6.4 приведена схема, иллюстрирующая рассмотрен­ ную классификацию корректирующих кодов.

В настоящее время в технике связи широкое распространение получили как блоковые, так и непрерывные коды. Из блоковых кодов наиболее перспективными с точки зрения применения в современных системах связи являются систематические коды.

§ 6.2. Групповые коды и способы их описания

6.2.1. Представление

кодовых

комбинаций

Д л я удобства описания и пояснения принципов построения корректирующих кодов множество кодовых комбинаций отож­ дествляют с векторами или многочленами.

Для двоичных кодов такое соответствие устанавливается сле­ дующим образом;

(а„

а , , . . . , а„) <==> alel

f

а2е2

+ . . . +

апеп

 

 

и

 

 

 

 

 

 

 

 

 

 

 

 

 

(а„

«г. • - •, "« )

«<A '° +

й 2 * '

-г • • • +

а п - * я _ 1 ,

 

где а,-— элемент

кодовой

комбинации;

 

орт

векторного

пространства;

х — формальная

переменная.

 

 

 

 

 

Введем действия над кодовыми

комбинациями, аналогичные

действиям над векторами и многочленами:

(аи

а.г,...,

ап)-\-

— сложение

кодовых

комбинаций—

-+-(*„ Ь2 , . . . A

) =

(ai +

* „

at +

bt,

. . . , a „

+

6 J ;

 

 

 

 

— умножение

кодовой

комбинации

на

скаляр

(двоичный

элемент) — 0

(av

а 2 , . . . , а„) =

(0, 0

 

0);

1 (а,,

а 2

, . . . ,

а„)

=

= ( а „ а „ , . . . , а я ) ;

 

 

 

 

 

 

 

 

 

 

 

 

— скалярное

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

кодовых комбинаций —

 

( a l t a 2 , . . . , ап) (bu

b,

bn)=axbl

+

аф2

+ . . . +

anbn.

 

Во всех этих действиях

сложение

 

производится

по модулю

2.

В результате скалярного произведения комбинаций получаем двоичный элемент — «0» или «1». Если скалярное произведение

комбинаций

равно нулю, то такие комбинации

называются орто­

гональными.

 

 

 

 

 

6.2.2.

Определение

группового

кода

Групповым

кодом

называют такой корректирующий код, мно­

жество кодовых комбинаций которого содержит нулевую комби­ нацию и является замкнутым в отношении сложения комбина­ ций, т. е. сумма любых кодовых комбинаций также является кодовой комбинацией.

Если в кодовой комбинации группового кода известны места информационных и избыточных элементов, то такой групповой код является систематическим.

Групповые коды обладают рядом важных свойств. Приведен­ ная ниже теорема определяет связь между минимальным кодо­ вым расстоянием и весами кодовых комбинаций.

Теорема 6.1. Минимальное кодовое расстояние группового кода равно минимальному весу его ненулевых кодовых комби­ наций.

Действительно, кодовое расстояние между двумя комбина­ циями определяется как вес суммы этих комбинаций. Однако сумма двух кодовых комбинаций, по определению кода, также является кодовой комбинацией, следовательно, кодовое расстоя­ ние между двумя комбинациями определяется весом некоторой кодовой комбинации. Если рассмотреть расстояние между всеми возможными парами кодовых комбинаций, то можно сделатьвывод, что списку кодовых расстояний группового кода одно­ значно соответствует описок весов кодовых комбинаций. Следо-

216

вательно, и минимальному кодовому расстоянию в групповом коде соответствует ненулевая кодовая комбинация с минималь­ ным весом.

Другие важные свойства групповых кодов будут изучены в связи с матричным описанием этих кодов. Для систематических кодов общепринято обозначение— (га, &)-код.

6.2.3. Матричное описание (п, k)-кодов

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

дать, что для задания

(га, 6)-кода

достаточно

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

k ли­

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

кодовы'Х комбинаций.*)

Если известно

k линейно-независимых кодовых

комбинаций

группового

кода,,

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

комбинаций

может

быть

различным для одного

и

того ж е

(га, k) -кода.

 

 

 

 

 

Обычно принято записывать комбинации, с помощью

которых

задают (га, £)-код,

в виде

прямоугольной таблицы

(матрицы) v

имеющей k

строк и га столбцов, где строками являются

линейно-

независимые кодовые комбинации. Такую матрицу называют порождающей матрицей группового кода и обозначают G(„, h).

Рассмотрим в качестве примера (5,3)-код. Этот код должен иметь 2f t = 2 3 —8 кодовых комбинаций. Условимся первых три разряда в кодовой комбинации а ь а2 , а 3 отводить под информа­ ционные элементы, а два последних а4 , as—>под избыточные- (проверочные). Пусть проверочные элементы формируются как

сумма по модулю 2 определенных информационных

элементов:

а4 = а\ + а2, аь — а2 + аг.

Эти

соотношения можно

представить в.

'Эквивалентном виде:

at +а2

+ а4 = 0 и a 2 + a3 -)-a5

=0,

т. е. сумма

по модулю 2 значений элементов, входящих в каждое из прове­ рочных соотношений, равна нулю. Используя такой принцип по­

строения кодовой

комбинации,

получаем все

комбинации

(5,3)-кода в виде, представленном

в табл. 6.1.

 

Минимальное кодовое расстояние в данном коде равно двум-

((представляется

читателю

проверить самостоятельно). Код

имеет несколько

наборов

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

комбинаций,,

которые можно использовать в качестве порождающей матрицы

(например, комбинации № 1,2,4; 4,5,6 ; 4,6, 7

и т. д . ) .

 

Для того чтобы исключить неоднозначность

в записи

порож­

дающей

матрицы, вводят понятие о канонической

форме

порож­

дающей

матрицы (га, 6)-кода.

 

 

*) Набор из k кодовых комбинаций называют линейно-независимым, если- •их сумма не равна нулю. В противном случае данный набор кодовых комби­ наций является линейно-зависимым.

G(5,3) имеет вид

 

 

 

 

 

 

 

 

 

Т а б л и ц а 6.1

№

Комбинация

Комбинация

корректи­

Вес кодовой

простого

кода

 

рующего

(5,3)-кода

 

 

п.п.

а3

 

«1

 

 

 

а2

 

комбинации

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

0

0

1

0

1

0

0

1

2

• • і

2

0

1

0

1

1

0

1

0

3

 

3

0

1

1

1

0

0

1

1

3

 

4

1

0

0

1

0

1

0

0

2

 

5

1

0

1

1

1

1

0

1

4

 

6

1

1

0

0

1

1

1

0

3

 

7

1

1

1

0

0

1

1

1

3

 

8

0

0

0

0

0

0

0

0

0

 

Каноническая форма порождающей матрицы группового кода

имеет вид

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

G(n, k) = [Rft х (л -

*) 1*1 >

 

 

 

где \k — единичная

матрица

размерности

(kXk),

т. е. квадрат­

ная матрица из k строк и k

столбцов,

у

которой

на

главной

диагонали

находятся

единицы,

а

все остальные элементы —

нули;

\k располагается на местах

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

элементов

кодовых

комбинаций

и служит

для

формирования

информа­

ционных

элементов

 

кодовых

комбинаций; Rkx(n-k) — матрица

из k

строк

и п — k

столбцов, расположенная на

местах

избы­

точных

элементов

кодовых

комбинаций,

составленная

из про­

верочных элементов базисных кодовых комбинаций и предназ­ наченная для формирования избыточных элементов этих ком­ бинаций.

Для (5,3)-кода каноническая форма матрицы

10

1

0

0"

G(5,3, = 11

0

1

0

01

0

0

1 .

Порождающая матрица может быть преобразована к кано­ нической форме при любом исходном базисе путем перестановки и сложения строк. Пусть, например, (5,3)-код задан матрицей ^справа указан номер соответствующей комбинации).

"10

1

0

0

(4)

G(5,3) = 11

1

0

1

(5)

.01

1

1

0.

(6)

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

218

строке прибавим первую и запишем результат в качестве третьей строки. В результате получим порождающую матрицу в кано­ нической форме:

"10

100]

(4)

 

10

100~

(4)

 

 

 

 

11

101 I

(5)

~

11

010

(4)

+

(6)

=

(2)

01

110.1(6)

 

L01

' 0 0 1 .

(4)

+

(5)

=

(1).

Широкое применение нашел также и другой способ матрич­ ного описания кодов. Сущность его сводится к следующему. Если записать правило формирования каждого из проверочных соотношений кода в виде «-элементного проверочного вектора -из нулей и единиц, в котором единицы расположены на местах элементов кодовой комбинации, входящих в проверочное соот­

ношение,

то получим п — k

проверочных векторов. В

отношении

связи проверочных векторов и кодовых комбинаций

групповых

кодов справедлива следующая

теорема.

 

 

 

 

Теорема

6.2.

Любая

кодовая

комбинация

ортогональна каж­

дому проверочному вектору для данного кода.

 

 

Действительно,

если

Н =

(къ

д2 , . . . ,

я„) — проверочный

вектор,

а

V—

(vt,

v 2 , . . . ,

vn)

— кодовая

комбинация,

то их

скалярное

произведение равно г»,я, -f- v2h2

-f- . . . +

=

S ^ A - -

Здесь

сумма берется

по

всем

слагаемым,

в которых

ht = \,

т. е. сводится

к сумме

по модулю

2 тех

элементов

кодовой

комбинации, которые входят в проверочное соотношение, и,

значит, должна равняться нулю.

 

 

 

Записав проверочные векторы группового кода

в прямо­

угольную

таблицу,

получим

матрицу

из я — k

строк и я столб­

цов, называемую

проверочной,

матрицей кода или

матрицей

проверок

и обозначаемую

Н(Л , *>.

Каждая

строка

матрицы

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

крайней мере

видом элементов, соответствующих

избыточным

разрядам,

то

все ее строки линейно-независимы и,

следова­

тельно, Н(„,к)

является порождающей матрицей

(я, я — &)-кода,

каждая кодовая комбинация которого ортогональна

кодовым

комбинациям

исходного (я, &)-кода. Код, порождаемый матри­

цей Н,п , *),

называют нулевым пространством

(я,

&)-кода или

двойственным

 

кодом.

 

 

 

Проверочная матрица позволяет формализовать процесс

вычисления

проверочных соотношений для

любой

кодовой

Смотрите также файлы