2014-02-24
1031
Построение двоичного группового кода
Математическое введение к групповым кодам
Основой математического описания линейных кодов является линейная алгебра (теория группы, полей, теория векторных пространств, теория матриц). КК рассматривается как элементы множеств.
Например:
КК двоичного кода принадлежащей множеству положительных двоичных чисел.
Алгебраические системы – множества для которых определены некоторые алгебраические операции.
Алгебраические операции – однозначное сопоставление двум элементам некоторого 3-го элемента по определенным правилам.
| Основные операции | Обратные операции | ||
| Сложение | (a+b)=c | Вычитание | (a-b)=c |
| Умножение | A*b=c | Деление | a/b=c |
Рассмотрим основные алгебраические системы, использующиеся в теории корректирующих кодов.
Группа – множество элементов в которых определена одна основная операция и выполняются следующие аксиомы:
1. В результате применения операции к любым двум элементам группы образуется элемент этой же группы.
|
|
|
2. Для любых трех элементов группы a, b и с удовлетворяется равенство:
(a+b)+c=a+(b+c)
или
a(bc)=(ab)c.
3. В любой группе G существует однозначный определенный элемент, удовлетворяющий для всех а из G условию:
Осн. сложение - > a+0 = 0+a =a.
Умножение -> a*1 = 1*a =a.
4. Всякий элемент группы обладает элементом, однозначно определенным уравнением:
| Сложение | а+(-а)=-а+а=0 |
| Умножение |
(-а) – противоположный элемент
– обратный элемент
Для коммутативной (абелевой) группировки выполняются условия коммутативности.
| Сложение | а+b=b+а |
| Умножение | ab=ba |
Одной из основных операций при рассмотрении п/у кодов является определение сложения по m2:
| 0 0 = 0 0 1 = 1 1 0 = 1 1 1 = 0 |
Особенностью операции суммирования по mod2 является, то что сложение по mod2 однозначно равно вычитанию по mod2 т.к. а а=0, то
а =- а
Построение конкретного корректирующего кода производится исходя из требуемого объема кода Q, т.е. необходимого числа передающих КК.
Вектор ошибки – КК, которая имеет нули в правильно принятых разрядах и единицы в искаженных разрядах.
Если необходимо передать Q информационных сообщений, то число разрядов К должно быть равно: k – число информационных символов.
Чтобы иметь возможность получить информацию об искаженном разряде каждому вектору должен быть поставлен в соответствие некоторая контрольная последовательность символов, называемая опознавателем (синдром).
Каждый символ опознавателя оценивается в результате проверки на полученной стороне одной из частых проверок.
Проверки составляются т.о. чтобы сумма всех символов по модулю 2 (включая проверочный), включенных в каждое из равенств = 0., т.е. числа “1” в таком равенстве всегда четные. Поэтому эти равенства называют проверками на четность.
|
|
|
Если искажение среди проверочных разрядов отсутствует, то такая проверка дает 0.
Если среди проверочных разрядов имеются искажения, то в в результате проверки =>1.
В результате всех проверок образуется определитель:
если искажений нет > 00..00; искажения нет > 1 в искаженных разрядах.
То количество исправленных ошибок определяет количество избыточных символов. Их число должно быть достаточным для обеспечения необходимого количества опознавателей.
Для исправления одиночных ошибок достаточно иметь: n векторов ошибок
Тогда число ненулевых определителей должно быть:
m – число контрольных символов или.
Для исправления двойных независимых ошибок:.
Для исправления ошибок кратности S:.
13.7 Код Хэмминга с исправлением одиночной и обнаружением двойной ошибки (d=4).
Реализуется следующим образом: путем добавления дополнительного контрольного разряда общей проверки на четность. Для кода (8.4) дополнительная проверка имеет вид:.
При приеме возможны следующие виды:
1) ошибок нет: - - общая проверка даст нуль
- частные проверки дают “0”
2) одиночная ошибка в разрядах:
- общая проверка 0;
- частные проверки 0;
3) ошибка в разряде: - частные проверки 0;
- общая проверка 0;
4) двойная ошибка: - частные проверки = 0;
- общая проверка 0;
