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

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. Всякий элемент группы обладает элементом, однозначно определенным уравнением:

(-а) – противоположный элемент

– обратный элемент

Для коммутативной (абелевой) группировки выполняются условия коммутативности.

Одной из основных операций при рассмотрении п/у кодов является определение сложения по m2:

Особенностью операции суммирования по mod2 является, то что сложение по mod2 однозначно равно вычитанию по mod2 т.к. а а=0, то

а =- а

12.3 Построение двоичного группового кода

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

Построение конкретного корректирующего кода производится исходя из требуемого объема кода 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;

13 Лекция 13. Помехоустойчивые корректирующие коды.

Цель лекции: ознакомление cпомехоустойчивыми корректирующими кодами.

Содержание:

а) cоставление таблиц опознавателей;

б) определение проверочных равенств;

в) Коды Хэмминга;

г) Коды Рида-Соломона;

д) Код Голея;

е) коды Финка-Хагельбаргера

13.1 Составление таблиц опознавателей.

Рассмотрим случай обнаружения одиночных ошибок. Допустим Q=15 тогда , с другой стороны:

Из этого выражения можно получить следующую таблицу:

Составим таблицу соответствия вектора ошибки и опознавателей КК n=7:

13.2 Определение проверочных равенств.

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

Тогда проверка №1:

.

Проверка №2 – аналогично, во втором разряде опознавателя:

.

Проверка №3 – аналогично в третьем разряде определителя:

.

Теперь нужно определить NN проверочных и информационных разрядов в КК. Нужно чтобы контрольные символы входили во все проверки только один раз. Это обеспечит независимость декодирования, т.е. значения контрольных разрядов может быть определено решением одного из проверочных равенств:

то получим размещение:

Пример. Код Хэмминга d=3, n=7, k=4, m=3 KK = 1011

то выходная КК:

Проверка:

Опознаватель = 101 > ошибка в разряде №5

Вектор ошибки: 0000100

Исправление ошибки: 0110111

0000100

Исправленная КК: 0110011

13.3 Коды Хэмминга.

Эти коды являются примером линейных кодов, исправляющих одну единственную ошибку. Длина блока кодов удовлетворяет соотношению n=2^(n-k)-1, где n-k количество проверочных символов. Например, при n-k=3 получаем код (7,4).

13.4 Коды Рида-Соломона.

Коды РС относятся к классу недвоичных кодов БЧХ. В кодере сообщение, состоящее из k q-ичных символов, выбираемых из алфавита, содержащего q=2^m символов, преобразуется в кодовое слово РС- кода, содержащее n двоичных символов. Поскольку обычно входные и выходные алфавиты равны степени 2, то входные и выходные символы могут быть представлены m- разрядными двоичными словами. Таким образом, входное сообщение можно рассматривать как km- разрядное слово, а выходное кодовое слово – как nm- разрядное двоичное слово. Длина кода РС равна n=q-1. Если исправляющая способность кода равна t ошибочным символам, то имеет место соотношение n-k=2t. Коды РС существуют при , а их расширение имеют длины блока: n= q и n= q+1.

13.5 Код Голея.

Этот код относится к числу наиболее интересных. Он позволяет исправить ошибки высокой кратности (t>1) и является также совершенным кодом. Код Голея (23,12) является циклическим и исправляет все конфигурации ошибок, кратность которых не превышает трех. С кодом Голея (23,12) связан код (24,12), который образуется добавлением к кодовым словам кода дополнительного проверочного символа. Коды (23,12) и (24,12) имеют минимальное кодовое расстояние, равное соответственно 7 и 8. Поэтому код (24,12), кроме исправления ошибок кратности 4 при незначительном изменении кода обнаруживает ошибки выше кратности 4. Код (24,12) относится к числу наиболее распространенных.

13.6 Непрерывные коды.

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

e_ik=c_i+c_k; e_i+1, _k+1=c_i+1+c_{k+1; …}

Расстояние между информационными символами l=k-i определяет основные свойства кодов и называется шагом сложения. Число контрольных символов при таком способе кодирования равно числу информационных символов, поэтому избыточность кода æ=0,5. Важное преимущество непрерывных кодов состоит в их способности исправлять не только одиночные ошибки, но и группы ошибок. Если задержка контрольных символов выбрана равной 2l, то можно показать, что максимальная длина исправляемого пакета ошибок также равна 2l при интервале между пакетами 6l+1. Таким образом, возможность исправления длинных пакетов связана с увеличением шага сложения l, а следовательно, и с усложнением кодирующих и декодирующих устройств.

14 Лекция 14. Циклические коды.

Цель лекции: ознакомление cциклическими кодами

Содержание:

а) циклические коды;

б) свойства символического умножения;

в) требования, предъявляемые к образующему многочлену;

г) выбор образующего многочлена по заданному объему кода и заданной корректирующей способности;

д) обнаружение одиночных ошибок (d=2);

е) исправление одиночных или обнаружение двойных ошибок (d=3).

14.1 Циклические коды

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

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

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

Исх. КК 001011

Матрица КК

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

При описании ЦК КК можно представить в виде многочленов некоторой переменной х. Показатели степени у переменной х соответствуют NN разрядам (начиная с нулевого), а коэффициентами при х, в общем случае, являются элементы поля GF(q). Поэтому для двоичного ЦК коэффициентами могут быть 0 или 1.

Так, например: КК 001011 –

или .

Наибольшая степень х в слагаемом с ненулевым коэффициентом называется степенью многочлена.

Циклический сдвиг многочлена без переноса “1” в конец КК можно получить простым умножением на х исходной КК:

* х

Если эти КК (001011 и 010110) сложить по m2, то результат сложения будет соответствовать умножению g(x) на (х+1):

001011

Å => х +1 ,

010110

011101 Å

.

Циклический сдвиг строки матрицы с “1” в старшем разряде равносилен умножению соответствующего многочлена на х c одновременным вычитанием из результата многочлена , т.е. с приведением по m2 ( ).

Т.о. любая разрешенная КК ЦК могла быть получена в результате умножения g(x) на некоторый другой многочлен с приведением результата по m( ), т.е. при соответственном выборе g(x).