Материал: 1832

Графическое представление кода

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

ми. Точки графа называются вершинами, а соединяющие их линии – Сибребрами. Начальная вершинаАД, от которой начинаетсяИрасхождение ре-

бер, называется корнем дерева, а число ребер, которое надо пройти от корня к некоторой вершине, – порядком этой вершины. Максимальное число ребер, которые могут выходить из каждой вершины дерева, равно основан ю кода, а максимальный порядок вершин, которое оно содерж т, равен макс мальной длине кодовых комбинаций. Значения разрядов комб нац , приписываемой каждой вершине, соответствуют направлен ям дв жения по ребрам от корня дерева к данной вершине. Ребра, ведущ е от корня к вершинам первого порядка, определяют значен е первого слева разряда комбинации; ребра, соединяющ е верш ны первого второго порядков, дают значение второго

разряда комб нац т.д.

На рис. 2.3.4 показано кодовое дерево для двоичного трехразрядного кода.

Рис. 2.3.4. Графическое представление кодового дерева

36

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

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

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

СибАДдвоичного кода И

Любая n-разрядная двоичная кодовая комбинация может быть интерпрет рована как вершина n-мерного единичного куба, т.е. куба с

длиной ребра, равной 1.

При n=2 кодовые комбинации располагаются в вершинах квадра-

та (рис. 2.3.5), при n=3 – в вершинах единичного куба (рис. 2.3.6).

В общем случае n-мерный единичный куб имеет 2n вершин, что равно на большему возможному числу кодовых комбинаций. Такая

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

На рис. 2.3.7 и 2.3.8 представлены геометрические модели троичного двухразрядного и трехразрядного кодов соответственно.

37

СибР с. 2.3.7. ГеометрическаяАДмодель троичногоИ двухразрядного кода

Рис. 2.3.8. Геометрическая модель троичного трёхразрядного кода

Классификация двоичных кодов

По возможности обнаружения и исправления ошибок различают простые корректирующие коды. Дальнейшая классификация приведена на рис. 2.3.9.

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

Коды в зависимости от методов внесения избыточности подразделяются на разделимые и неразделимые. В разделимых кодах четко разграничена роль отдельных символов. Одни символы являются ин-

38

формационными, другие являются проверочными и служат для обнаружения и исправления ошибок.

Разделимые блочные коды называются обычно n, k-кодами, где n – длина кодовых комбинаций; k – число информационных символов в комбинациях.

Неразделимые коды не имеют четкого разделения кодовой ком- СибАДИбинации на информационные и проверочные символы.

Раздел мые блочные коды делятся на систематические несистематическ е. Нес стематические коды строятся таким образом, что проверочные с мволы определяются как сумма подблоков длины l , на которые разделяется блок информационных символов. У систематическ х кодов проверочные символы определяются в результате проведен я л нейных операций над определенными информационными с мволами.

Рис. 2.3.9. Классификация двоичных кодов

Основные характеристики двоичных кодов

Двоичные коды характеризуются весом кода w, кодовым расстоянием d и весовой характеристикой F(w) . Весом кода w называется количество единиц в кодовой комбинации. Например, для кодовой комбинации 1011110 вес кода w=5.

39

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

довых комбинаций 10101 и 00110 d=3, так как 10101 00110 = 10011 (w=3).

СибАДИТаким образом, кодовое расстояние определенного кода – это

минимальное ч сло элементов, которыми любая кодовая комбинация отличается от другой (по всем парам кодовых слов). Например, для кода, состоящего з комбинаций 1100, 1000, 1011, 1101, dmin=1, так как

1100 1101=0001 (w=1).

Весовая характер стика кода F(w) – число кодовых комбинаций

определенного веса w. Например, для кода, представленного комби-

нациями 00001 (w=1); 11010 (w=3); 10110 (w=3); 11110 (w=4), имеем

F(1)=1; F(3)=2; F(4)=1, т.е. код состоит из одного кодового слова веса 1, двух слов веса 3 одного слова веса 4.

Корректирующие коды имеют некоторые дополнительные ха-

рактеристики.

Абсолютная из ыточность кода определяется числом проверочных символов (r), т.е. количеством разрядов, отводимых для коррек-

ции ошибок.

Относительная избыточность кода (R) есть отношение числа проверочных символов к длине кода: R r/n. В общем случае отно-

сительную избыточность рассчитывают по формуле

R I log2 Np /log2 N , где Np – число кодовых комбинаций, исполь-

зуемых для передачи сообщений (рабочая мощность кода); N – полное число кодовых комбинаций (мощность кода).

2.3.3. Простые двоичные коды

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

40