Пример 2. Пусть n=3. Множество различных 23=8 трехразрядных кодовых слов образует группу M={000, 001, 010, 011

Пусть n=3. Множество различных 2³=8 трехразрядных кодовых слов образует группу M={000, 001, 010, 011, 100, 101, 110, 111}.

Выделим подгруппу H группы M (H M), включающую два кодовых слова: H={000, 111}. Построим таблицу разложения (таблица 1) группы M по подгруппе H с образующими элементами {001, 010, 100}.

Выберем первый образующий элемент 001 H и построим первый смежный класс {001, 110}:

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

Таблица 1 - Таблица разложения (групповая таблица).

			Подгруппа H M
Образующие элементы				Смежный класс 1
			Смежный класс 2
			Смежный класс 3

Аналогично, с помощью образующего элемента 010, построим второй смежный класс {010, 101}, а с помощью образующего элемента 100 - третий смежный класс {100, 011}. При передаче кодового слова 000 одиночная ошибка может привести к появлению на приемном конце одной из запрещенных комбинаций {001, 010, 100}. Эта ошибка может быть скорректирована в соответствии с методом максимального правдоподобия (хеммингово расстояние между разрешенной кодовой комбинацией 000 и соответствующими запрещенными комбинациями 001, 010, 100 равно единице).

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

Все 8 элементов группы присутствуют и дальнейшее разложение невозможно.

2.5.1. Построение группового кода Хэмминга (7, 4)

Для построения группового кода задаются следующие исходные данные:

(1) Объём кода Q (число различных разрешённых кодовых слов).

(2) Данные о наиболее вероятных ошибках.

Вектором ошибки будем называть n-разрядную кодовую комбинацию, имеющую единицы в разрядах, подвергшихся искажению, и нули - во всех остальных разрядах. Любую искажённую кодовую комбинацию можно рассматривать как результат поразрядного сложения по модулю 2 разрешённой кодовой комбинации и вектора ошибки (в примере 2 векторами ошибки являются образующие элементы 001, 010, 100).

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

Шаг 1. Число k информационных разрядов определяется из неравенства

2^k -1≥ Q. (2.6)

Шаг 2. Каждой из 2^k -1 ненулевых комбинаций k-разрядного безызбыточного кода надо поставить в соответствие комбинацию из n символов. Значения (n-k) проверочных символов определяются в результате сложения по модулю 2 значений соответствующих информационных символов.

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

Линейные, так как контрольные разряды образуются с помощью линейных операций над информационными разрядами. Систематические, так как информационные разряды не меняют свои позиции в кодовых комбинациях. Эти коды называются ещё и кодами с проверкой на чётность, так как значение проверочного символа вычисляется в результате сложения некоторых информационных символов таким образом, чтобы суммарное число выбранных разрядов было чётным.

Можно показать, что если множество k-разрядных комбинаций в количестве 2^k (включая комбинацию 00…0) образует группу, то подмножество соответствующих n-разрядных 2^k кодовых слов, полученных по указанному правилу, образует подгруппу H группы M, состоящей из 2ⁿ комбинаций n-разрядных кодовых слов.

Разложим группу 2ⁿ всех n-разрядных векторов по подгруппе 2^k разрешённых кодовых слов. Помимо самой подгруппы H в разложении будет насчитываться 2^n-k -1смежных классов. Если за образующие принять наиболее вероятные для заданного канала связи векторы ошибок, которые должны быть исправлены, то в каждом классе сгруппируются кодовые комбинации, полученные в результате воздействия одного и того же вектора ошибок.

Для исправления любой ошибки достаточно определить класс смежности. Для определения класса смежности ему должна быть сопоставлена комбинация из (n-k) контрольных разрядов, называемая опознавателем или синдромом. Каждый символ синдрома вычисляется на приёмном конце путем сложения по модулю 2 значений соответствующих информационных разрядов. Нулевое значение синдрома соответствует отсутствию ошибок. Исправление ошибок возможно лишь при наличии взаимно однозначного соответствия между множеством синдромов и множеством смежных классов, а, следовательно, и множеством векторов ошибок.

Таким образом, количество проверочных символов (n-к) определяется числом опознавателей. Очевидно, число различных ошибок, исправляемых (n-к) проверочными символами, не более 2^n-k -1.

Если требуется исправить все одиночные ошибки, то должно выполняться неравенство

(2.7)

двойные ошибки - (2.8)

ошибки кратности S - (2.9)

Приведённые формулы используются для определения длины кодового слова n. При этом нужно учитывать, что формулы определяют теоретический предел, который часто не достигается.

Составление таблицы опознавателей и определение проверочных равенств

Данную тему рассмотрим с помощью конкретного примера.

Поиск по сайту: