Основные понятия и определения теории информации и кодирования. Задачи теории информации и кодирования, страница 15

произошла ошибка в первом разряде кодовой комбинации ( искажён символ a1 ).Тогда проверочные операции дадут следующий результат:S1=0;

S2=1;S3=1.Таким образом будет получен синдром S = 011,что соответствует первому столбцу матрицы H.

При ошибке во втором разряде a2 кодовой комбинации будет получен синдром S = 101,что соответствует второму столбцу матрицы H и т.д.

При ошибке в шестом разряде кодовой комбинации,что соответствует искажению второго проверочного символа b2,будет получен синдром

S = 010,что соответствует шестому столбцу матрицы H или второму столбцу единичой подматрицы.

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

!/* К систематическим кодам относятся:

а) коды с обнаружением ошибок:

- код с чётным числом единиц;

- код с удвоением элементов;

- инверсный код;

б) коды с обнаружением и исправлением ошибок:

- коды Хэмминга;

- циклические коды. */!

К О Д Ы   Х Э М М И Н Г А .

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

К этим кодам обычно относят коды с исправлением одиночных ошибок и коды с исправлением одиночных и обнаружением двукратных ошибок.

Код Хэмминга,обеспечивающий исправление всех одиночных ошибок должен иметь минимальное кодовое расстояние d min = 3.

n = k + p, где k - количество информационных символов;

p - кол - во проверочных символов;

n - общее кол - во символов в коде.

При передаче кода может быть искажён любой символ (n комбинаций).

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

Поэтому

2^p = > n + 1.

Вместе с тем 2^n = 2^(k+p) = 2^k * 2^p, или

2^n = 2^k * 2^p = > ( n + 1 )2^k.

Отсюда число информационных символов кода,корректирующего одиночную ошибку

2^k < = 2^n / (n + 1).

Критерий оптимальности таких кодов - близость к нижней границе

Хэмминга

r

___   i

2^p = 2^(n - k) = >  >    C  ,

---   n

i=1

где r - кратность ошибки.

Для r = 1    2^(n - k) - 1 = n.

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

Коды,оптимальные по этому условию называются ПЛОТНОУПАКОВАННЫМИ.

Код Хэмминга является плотноупакованным.

Код строится таким образом,чтобы в результате p = n - k проверок получить p - разрядное двоичное число,указывающее номер искажённой позиции кодовой комбинации.Для этого проверочные символы должны находиться на номерах позиций,которые выражаются степенью двойки

( 2^0,2^1,2^2,...,2^(p-1) ),так как каждый из них входит только в одно из проверочных уравнений.Таким образом,если нумеровать позиции слева направо,то контрольные символы должны находиться на 1-й,2-й,

4-й,16-й и т.д.позициях.

Результат первой проверки даёт цифру младшего разряда синдрома в двоичной записи.Если результат проверки даст 1 ,то один из символов проверенной группы искажён.Таким образом,первой проверкой должны быть охвачены символы с номерами,содержащими в двоичной записи единицы в первом разряде:1,3,5,7,9 и т.д.Результатвторой проверки даёт цифру второго разряда синдрома.Следовательно,второй проверкой должны быть охвачены символы с номерами,содержащими в двоичной записи единицы во втором разряде:2,3,6,7,10 и т.д.

Аналогично при третьей проверке должны проверяться символы,номера которых в двоичной записи содержат единицы в третьем разряде:4,5,6,

7,12 и т.д.

Таким образом,проверочные равенства должны иметь вид:

a1 = a3 + a5 + a7 + a9    + ...

a2 = a3 + a6 + a7 + a10   + ...

a4 = a5 + a6 + a7 + a12   + ...

a8 = a9 + a10 + a11 + a12 + ...