35. Определение минимального кодового расстояния в кодах Хэмминга. Определение общего числа элементов кодовых комбинаций кодов Хэмминга, числа информационных и числа проверочных элементов.

1. Определение минимального кодового расстояния

d_min = 2S + 1 = 21 + 1 = 3.

2. Определение общего количества элементов кодовых комбинаций систематического кода - n.

N_p = =

где: С - количество вариантов состояний кодовых комбинаций, когда искажение отсутствует (C = 1).

С - количество вариантов кодовых комбинаций, когда возникают одиночные искажения ( в рассматриваемом примере C = =n.

3. Из формулы для определения N_p определяют общее количество элементов систематического кода

2^k = ; 2⁵ = ; 32 =

при определении n выбирают минимальный верхний предел, т.е. sup n sup n = 9, т.к. 32 должно быть меньше или равно , то выбирая наименьший верхний предел, получают n=9, т.е. n=9; k=5.

4. Определение числа проверочных элементов систематического кода r = n - k = 9 - 5 = 4. Для случая r=4 строится множество кодовых комбинаций N_r = 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, !001, 1010, 1011, 1100, 1101, 1110, 1111.Из полученного множества для построения проверочной подматрицы производящей матрицы выбирают пять (к=5) комбинаций (любых), вес каждой из которых p d_min-1=3-1=2. Такое подмножество определится как N₅=0011, 0101, 0110, 0111, 1001, общее же количество комбинаций, удовлетворяющих условию p 2 имеет вид N_{p 2} = 0011, 0101, 0110,0111, 1001, 1010, 1011, 1100, 1101, 1110, 1111, т.е. N_{p 2}=12.

36. Исправление одиночных искажений в циклических кодах.

Обнаружение и исправление одиночных искажений в циклических кодах при кодовом расстоянии d_min=3 осуществляется следующим образом:

1. Принятая комбинация циклического кода F^’(1,0) делится на образующий многочлен P(x), она считается достоверной, если остаток от деления равен нулю, в противном случае комбинация принята с искажением.

2. Определяется вес остатка p₀. При p₀  S принятая комбинация суммируется по модулю 2 с полученным остатком, образованная сумма определяет исправленную комбинацию (переданную комбинацию).

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

4. Производится циклический сдвиг полученной суммы на один разряд вправо. Образованная после сдвига кодовая комбинация м является восстановленной (исправленной) комбинацией.

5. Если в результате второго деления условие p₀ S не выполняется, то указанная операция продолжает выполняться до тех пор, пока не будет реализовано неравенство p₀ S.

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

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

Пример.

произошло искажение в пятом разряде. Передавалась кодовая комбинация 1100101, принятая кодовая комбинация имеет вид 1110101. В рассматриваемом примере число исправляемых искажений S=1, число информационных символов кодовой комбинации k=4, число проверочных символов r=3. Следовательно образующий многочлен будет иметь вид P(x)=x³+x²+1.

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

1. Деление принятой кодовой комбинации на образующий многочлен P(x)=x³+x²+1  1101.

1110101  1101

1101

1110

1101

111  остаток p₀=3.

2. При сравнении веса остатка (p₀=3) с числом исправляемых искажений S=1, имеем p₀  S. Условие p₀  S не выполняется.

3. Производится циклический сдвиг принятой кодовой комбинации на один разряд влево и повторное деление на образующий многочлен P(x).

1101011  1101

1101

011  остаток (вес остатка p₀=2). Условие p₀S не выполняется.

4. Сдвиг поразрядно влево и деление на образующий многочлен осуществляется до тех пор пока не будет выполнено условие p₀S.

1010111  1101

1101

1111

1101

1011

1101

110  остаток p₀=2S

0101111 1101

1101

1101

1101

1  остаток p₀=1=S. Условие p₀S выполнено.

5.При суммировании по модулю 2 последнего делимого 0101111 с остатком, получают комбинацию 0101110

6. Производится циклический сдвиг вправо полученной комбинации на 3 разряда (т.к. трижды при делении на образующий многочлен влево сдвигалась принятая кодовая комбинация).

0101110  0010111  10011  1100101.

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