Коды, обнаруживающие трёхкратные ошибки

 

Методика построения следующая:

1) Выбор числа корректирующих разрядов

      n_k – количество корректирующих разрядов

Значения логарифма округряется до целых чисел в большую сторону

 

Пример: n_u = 2        = 4

2) Выбор образующего многочлена. Он производится исходя из следующих соображений: для обнаружения трёхкратной ошибки надо иметь d₀ = r + 1 = 3 + 1 = 4 степень обратного многочлена должна быть больше или равна четырём, т.е.

 

Этот многочлен получают как произведение многочлена степени (n_k - 1)т.е. 3, который позволяет обнаруживать все двойственные ошибки и многочлены первой степени (x + 1), который обнаруживают любое количество нечётных ошибок. Полученный многочлен унаследует корректирующие свойства, т.е. он будет обнаруживать одиночную и тройную ошибки, используя корректирующие свойства многочлена x + 1 и будет обнаруживать двойные ошибки, используя свойства Шеннона, например x³ + x² +1.

Произведём умножение

M₁ = x + 1

M₃ = x³ + x² + 1

M₁ x M₃ = (x + 1)(x³ + x² + 1) = x⁴ + x² + x +1 = k(x)

x³ + x³ = 0                k(x) = 10111

x³ + x³ + x³ = x³

 

3) Построение образующей матрицы

Производят нахождением остатка последней строки единичной повёрнутой матрицы на обратный многочлен 100…к(х)     - методика в прошлой лекции. Второй способ умножением строки единичной матрицы на образующий многочлен. Остальные комбинации получают суммированием комбинаций строк.

 

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

 

 

Пример: Строим код на четыре комбинации

 

01 х к(х) = 01 x 10111 = 010111

10 х к(х) = 10 х 10111 = 101110

 

Обратная матрица

 

Обнаружение ошибки

1) Тройная ошибка

 

v₁ = 010111

v_k = 111011 k_x = 10111

  10111

    10101                         R_x = 10 Þ обнаружена ошибка, надо повторить передачу

    10111

      0010

 

2) Двойная ошибка

 

v₁ = 010111

Rx = 1010 – есть остаток, следовательно, посланная комбинация содержит ошибку.

v_k = 110011 k_x = 10111

  10111

    11101                             

    10111

      1010

 

3) Однократная ошибка

 

v₁ = 010111

Rx = 1110 – есть остаток, следовательно, принятая комбинаяция содержит ошибку. Какую ошибку мы не указываем.

v_k = 110111 k_x = 10111

  10111

    11001                             

    10111

      1110

 

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

 

1) Определение количества параметров кода

 

n_u = log₂ 1000 = 10

n_k 1 + log₂(n_u + 1 + log₂(n_u + 1)) = 1 + log₂(11 + log₂11)

n_k = 5

d₀ = r + 1 = 4 – число ненулевых членов образующего многочлена

 

Из таблицы нериводимых многочленов, выбираем многочлен степени n_{k – 1} = 4, который позволяет обнаруживать двойные ошибки.

M₄ = x⁴ + x + 1

M₁ = x + 1

 

k(x) = M₁ + M₄ = (x + 1)(x⁴ + x + 1) = x⁵ + x⁴ + x² + 1 110101

 

 

 

Информация. Язык. Общество......................................................................................................................................................... 2

Измерение информации...................................................................................................................................................................... 2

Структурный метод.......................................................................................................................................................................... 2

Статический метод........................................................................................................................................................................... 2

Энтропия и её свойства.................................................................................................................................................................. 3

Энтропия сложной системы........................................................................................................................................................... 4

Условная энтропия. Объединение зависимых систем............................................................................................................... 4

Полная условная энтропия................................................................................................................................................................ 5

Определение информационных потерь в каналах связи........................................................................................................... 7

Энтропия и информация................................................................................................................................................................... 8

Взаимная информация........................................................................................................................................................................ 9

Частная информация о системе................................................................................................................................................... 10

Количественное определения избыточности........................................................................................................................... 12

Блочное кодирование........................................................................................................................................................................ 15

Передача информации по дискретным каналам связи.......................................................................................................... 19

Код Хэминга........................................................................................................................................................................................ 31

Декодирование кода Хэминга......................................................................................................................................................... 32