3.8.5. Граница Хэмминга

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

Найдем связь между максимально возможной корректирующей способностью КСК, длиной n кодового слова и максимальным числом Q разрешенных кодовых слов в случае использования ДСК.

В круг (шар) диаметром КСК поместится кодовых слов.

Поскольку подмножества не пересекаются, то

. (3.1)

Коды, число кодовых слов которых равно Q, называются оптимальными или плотноупакованными.

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

3.8.6. Избыточность помехоустойчивых кодов

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

Различают абсолютную и относительную избыточность.

Абсолютная избыточность И_абс равномерных помехоустойчивых кодов находится по формуле:

И_абс=n-k.

Относительная избыточность:

И_отн= И_абс/n=1-k/n.

При определенных условиях избыточность помехоустойчивого кода связана с избыточностью сообщения.

Если предположить равновероятность появления разрешенных кодовых слов, то избыточность D сообщения в виде кодового слова, вычисляемая по формуле D=H_max – H, будет равна абсолютной избыточности кода: D=n-k=И_абс .

Это легко доказать, учитывая, что

и .

3.8.7. Математическое введение к алгебраическим кодам

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

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

Под двухместной операцией здесь понимается однозначное сопоставление двум элементам множества с третьим по определенным правилам.

Под одноместной операцией понимается однозначное сопоставление одному элементу множества с другим по определенным правилам.

Обычно основные операции называются сложением (a+b=c) и умножением (ab=d), а обратные им вычитанием и делением, даже если этим операции производятся не над числами (например, над оттенками цветов или геометрическими фигурами) и не идентичны соответствующим арифметическим операциям. С точки зрения высшей алгебры элементарная школьная алгебра − одна из бесконечного множества других возможных алгебраических систем.

Свойства и наименования систем зависят от законов, которые в них определены.

Пусть S – множество некоторых элементов, а а и b - элементы, принадлежащие множеству S (последнее записывается в виде ).

В таблице 3.9 определены некоторые важные для нас законы (Элементы теории передачи дискретной информации. –М.:Связь, 1972):

Таблица 3.9.

Законы композиции	Операция
	Сложение		Умножение
	Обозн.	Формула	Обозн.	Формула
Замкнутость (если , то ).	А1	a+b=c	M1	ab=c
Ассоциативность	А2	(a+b)+c= a+(b+c)	M2	(ab)c=a(bc)
Коммутативность	А3	a+b=b+a	M3	ab=ba
Наличие нулевого для операции сложения и единичного для операции умножения элемента е.	А4	a+e=e+a=a	M4	ae=ea=a
Наличие для обратного элемента .	А5		M5
Дистрибутивность	D1	a(b=c) = ab=ac
	D2	(b+c)a = ba+bc

Система, в которой определены две основные операции (сложение и умножение) и которая соответствует всем отмеченным в таблице свойствам, называется полем.

Система, в которой определены обе основные операции и выполняются законы А1−А5, М1, М2, D1 и D2, называется кольцом.

Если дополнительно в некотором кольце выполняется закон М3, то это кольцо – коммутативное.

Система, в которой задана лишь одна операция (сложение или умножение) и выполняются законы А1, А2, А4, А5 или М1, М2, М4, М5 называется группой.

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

Группа называется коммутативной или абелевой, если в ней выполняется закон коммутативности (А3 или М3) в зависимости от введенной операции.

Группы, имеющие конечное число элементов, называются конечными.

Построим алгебраическую систему, удобную для описания кодов равномерных двоичных кодов.

Предположим, что кодовые комбинации образуют множество S. Определим теперь операцию суммирования, обладающую свойствами А1, А2, А4, А5 и образуем таким образом группу. Операцию суммирования определим таким образом, чтобы удовлетворялось условие замкнутости А1. Следовательно, число разрядов при выполнении этой операции меняться не должно. Этому условию отвечает операция поразрядного сложения кодовых слов по модулю 2 (обозначается знаком ). Результатом такого сложения будет 1, если число единиц в разряде слагаемых четно, и 0 − если нечетно.

Пример:

1 0 1 1 1 0 1

0 1 1 1 1 0 1

0 0 0 1 1 1 0

1 1 0 1 1 1 0

Выбранная операция коммутативна, поэтому группа будет абелевой.

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

Противоположным элементом является сама кодовая комбинация, а обратная операция – вычитание – тождественна основной операции суммирования.