Методическое пособие 640

Кроме того, из заданного (n,k,d) кода можно получить новый, обладающий теми же параметрами, если в каждом кодовом слове поменять местами символы, стоящие на одинаковых позициях. Получаемый по такому алгоритму код называется эквивалентным. Порождающие матрицы G и G эквивалентных кодов связаны друг с другом элементарным преобразованием. Так обмен символами на одинаковых позициях кодовых слов (или, что то же самое, перестановка координат кода) эквивалентна перестановке столбцов матрицы G . Следовательно, два кода эквивалентны тогда и только тогда, когда их порождающие матрицы получаются одна из другой посредством перестановки столбцов, либо в результате элементарных операций над строками.

В том случае, когда существует необходимость построения кода Хэмминга в систематической форме, единственное, что необходимо сделать – это определенным образом упорядочить столбцы исходной проверочной матрицы, выделив в явном виде m m единичную матрицу, как составную часть проверочной. Из полученной таким способом матрицы H легко построить и порождающую матрицу. Иллюстрацией описанного алгоритма могут служить матрицы H и G , представленные ниже, основой для получения которых послужила матрица (7,4) кода Хэмминга.

	1011100		1000111
H	1110010		G 0100011 .
			0010110
	1101001
			0001101

Например, третьей проверочной матрицей Н для кода #5 является матрица

"	=	1	1	1	0	1	0	0	,
		0	1	1	1	0	1	0
		0	0	1	1	0	0	1

содержащая те же самые столбцы, но уже в другом по-

191

рядке (матрица Н" является проверочной матрицей не кода

#5, а эквивалентного ему кода). Эта матрица задает циклический код, т.е. циклический сдвиг любого кодового слова снова является кодовым словом. Далее мы увидим (раздел 7.15), что двоичные коды Хэмминга могут быть всегда сделаны циклическими.

Процесс декодирования происходит следующим образом. Предположим, что мы используем матрицу Н, когда i -й столбец Нi равен двоичному представлению числа i. Если произошла ошибка в l -м символе, то из (7.16) следует, что синдром S = Н·уT = Н·еT = Нi , т.е. равен двоичному представлению числа l . Очень простое декодирование!

Так как код может исправлять любую одиночную ошибку, то его минимальное расстояние d ≥ 3. Следовательно, коды Хэмминга являются совершенными кодами, исправляющими одиночные ошибки.

Существуют также и не двоичные коды Хэмминга, однако, их ценность по сравнению с двоичными значительно ниже. Параметры кодов Хэмминга этого типа определяются соотношениями:

n	qm 1	,	k	qm 1	m,	q pm .
	q 1			q 1

7.13. Коды расширения и укорочения

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

192

деляют шесть основных преобразований кода, к числу которых относятся:

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

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

–код с выбрасыванием – это уменьшение числа информационных символов без изменения длины кода, что приводит

кснижению меньшего размера порождающей матрицы;

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

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

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

1) Расширение кода (добавление общей проверки на четность или прямоугольный код). Пусть будет [n, k, d] двоич-

ным кодом, в котором некоторые кодовые слова имеют нечет-

ный вес. Образуем новый код	добавляя 0 в конце каждого
кодового слова c четным весом′	и добавляя 1 в конце каждого
слова с нечетным весом. Тогда	обладает тем свойством, что
каждое кодовое слово имеет четный′		вес, т.е. этот код удовле-

творяет новому уравнению проверки на четность х1 + х2 + ... + хn = 0, а именно уравнению общей проверки на четность.

Расстояние между каждой парой кодовых слов теперь четное число. Если минимальное расстояние кода было нечетным, то новое минимальное расстояние равно d+1 и ′ представляет собой [n+1, k, d+1] -код. Этот способ присоеди-

193

нения добавочных проверочных символов будем называть

расширением кода.

Если имеет проверочную матрицу Н, то ′ имеет проверочную матрицу

1 1 1 . . . 1

0

H 0

=…

0

Пример. Код #8. Добавление общей проверки на чет-

ность к коду #5 дает [8, 4, 4] расширенный код Хэмминга с про-

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

	1	1	1	1	1	1	1	1
=	0	0	0	1	1	1	1	0
	0	1	1	0	0	1	1	0 .
позиции 11		20	31	40	51	60	71	0.0

Так как расстояние этого кода равно d=4, то согласно теореме он может исправлять любую одиночную ошибку и обнаруживать любую двойную ошибку. В самом деле, вспоминая, что синдром S равен сумме тех столбцов Н, где произошли ошибки, получаем следующую схему декодирования. Если ошибок нет, то S = 0. Если произошла одна ошибка на пози-

ции с номером i , то

1

=,

где вектор (х, у z) — двоичное представление числа i (см. Код #8). Наконец, если произошли две ошибки, то

194

0

=

и декодер обнаруживает, что произошли две (или более) ошибок.

2) Выкалывание кодовых координат. Операция, обратная расширению кода , называется выкалыванием и состоит в удалении одной или более координат из каждого кодового слова. Так, например, пусть у нас имеется [3, 2]-код #9:

000 код #9 011 101 110

Выкалывание последней координаты этого кода дает

[2, 2, 1]-код

00

01

10

11

Выколотый код обычно обозначается через *. В общем случае каждый раз, когда удаляется одна координата, длина кода п уменьшается на 1, число кодовых слов не изменяется и (до тех пор, пока нам не везет) минимальное расстояние d уменьшается на 1.

3) Код с выбрасыванием. Простейший способ получения кода с выбрасыванием состоит в следующем. Предположим, что двоичный [n, k, d]-код содержит кодовые слова обоих весов, четного и нечетного. Тогда, половина кодовых слов имеет четный вес и половина нечетный. Выбросим из кода все кодовые слова нечетного веса, и тогда получим [n, k—1, d'] -код. Часто d' > d (например, если d — нечетное).

195

Пример. Из [7, 4, 3]-кода #5 выбрасыванием всех слов нечетного веса получаем [7, 3, 4]-код.

4) Пополнение кода путем добавления новых кодовых слов. Простейший способ пополнения кода заключается в добавлении к нему вектора 1 из всех единиц при условии, что он не принадлежит коду. Это эквивалентно добавлению вектора 1 к порождающей матрице. Если — [п, k, d] двоичный код, который не содержит вектора 1, то пополненный код равен

(	)	=		{1+ }.
Другими словами
		( )		(a)
			состоит из кодовых слов и их до-
полнений и является [n, k+1, d					]-кодом, где

d(a)=min{d, n—d'}

и d' — наибольший вес кодовых слов кода.

Пример. Пополнение кода #9 дает [3, 3, 1]-код, состоящий из всех векторов длины 3.

5)Удлинение кода путем добавления информационных символов. Обычный способ удлинения кода состоит из последовательного выполнения двух операций: пополнения кода путем добавления вектора 1 и расширения его с помощью общей проверки на четность. В результате этих операций число информационных символов увеличивается на единицу.

6)Укорочение кода. Эта операция является обратной к только что описанной операции удлинения и заключается в выборе всех кодовых слов, первая координата которых равна нулю, x1 = 0, и в удалении этой координаты в выбранных словах. Описанная операция будет использоваться в дальнейших главах для укорочения нелинейных кодов.

Все эти шесть операций показаны на рис. 7.8. для кода Хэмминга.

196

Рис. 7.8. Применение конструкций к коду Хэмминга

7.14. М-арная передача сигналов

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

На практике при М -арной передаче сигналов процессор за один такт работы принимает сразу k бит данных. После этого он указывает модулятору произвести один из М = 2k сигналов; частным случаем k = 1 является двоичная передача сигна-

197

ла. Для k > 1 М -арную передачу сигналов можно рассматривать как процедуру кодирования формы сигнала. При ортогональной передаче сигналов (например, сигналов MFSK) увеличение k приводит к повышению достоверности передачи или уменьшению требуемого отношения сигнал/шум Eb/N0 за счет увеличения полосы пропускания; при неортогональной передаче сигналов (например, сигналов MPSK) улучшение эффективности использования полосы пропускания происходит за счет снижения достоверности передачи или возрастания требуемого Eb/N0 . Подходящий выбор формы сигнала позволяет найти компромисс между вероятностью ошибки Рb , отношения сигнал/шум Eb/N0 и эффективностью использования полосы пропускания W.

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

дами (orthogonal), биортогональными кодами (biorthogonal) и

трансортагональными (симплексными) кодами. В процессе кодирования каждый сигнал набора пытаются сделать настолько непохожим на другие, насколько это возможно, чтобы для всех пар сигналов коэффициент взаимной корреляции zij имел наименьшее возможное значение. Строго это условие выполняется тогда, когда сигналы антикоррелируют (zij = -1); этого можно добиться только в том случае, если в наборе всего два значения (M = 2) и они антиподны (дуальны) друг другу. Вообще, все коэффициенты взаимной корреляции можно сделать равными нулю. В этом случае набор будет ортогональным. Наборы антиподных сигналов являются оптимальными в том смысле, что все сигналы максимально удалены друг от друга (см. рис. 7.9).

198

Рис. 7.9. Изображение кода #9

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

Расстояние d между векторами сигналов определяется

как d = 2√ , где Е — энергия сигнала на интервале Т, опреде-

ляемая как = ∫ ( ) .

Данный вид кодирования на практике используется применительно к реализации широкополосных сигналов для даль- номерно–временных измерительных систем связи в спутниковых радионавигационных системах второго поколения типа GPS NAVSTAR (США) и ГЛОНАСС (СССР/Россия). Для данной разновидности сигналов характерно наличие большого значения частотно–временного произведения WT, измеряемого в тысячах. Также широкополосные сигналы используются в системах маскирования речевых данных и защиты передаваемой информации.

199

7.14.1. Ортогональные коды

Более простой конструкцией построения кода по сравнению с симплексными (трансортогональными) кодами являются

ортогональные коды.

Набор ортогональных кодовых слов формируется следующим образом:

= .

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

ченная таким образом m 2m матрица является порождающей матрицей 2m,m ортогонального кода длины n 2m с k m

информационными символами (а значит, сM 2m n кодовыми словами). Очевидно, что веса всех ненулевых слов ортогонального кода одинаковы и равны n/2, следовательно, код

длины n 2m имеет минимальное расстояние d n/2 2m 1. Это означает возможность исправлять все ошибки кратности

до t (n/4) 1 2m 2	1 включительно и обнаруживать
ошибки кратности 2m 2	n/4.
Основанием для подобного названия кода служит тот

факт, что при замене двоичных 0,1 символов кода на 1 каждое кодовое слово становится одной из ортогональных функций Уолша.

7.14.2. Биортогональные коды

Биортогональный набор сигналов, состоящий из М сигналов или кодовых слов, получается из ортогонального набора,

200