Построение циклического кода

Исправление ошибок в коде Хэмминга

Исправление ошибок в линейном систематическом коде

Производится по проверочной матрице Н (см.рисунок 4.10): производится суммирование по mod 2 проверочных символов кодовой комбинации и проверочных символов вычисленных по принятым информационным:

S₁ =b₁ Å a₂ Å a₃ Å a₄

S₂ = b₂ Å a₁ Å a₃ Å a₄

S₃ = b₃ Å a₁ Å a₂ Å a₄

В результате ρ таких проверок получаем ρ – разрядное двоичное число – синдром, которое будет равно 0, при отсутствии ошибок.

Если ошибка в первом разряде а₁ (он используется при образовании S₂ и S₃), то получим S₁ = 0, S₂ = 1, S₃ = 1, т.е. синдром 011. При ошибке в а₂ синдром 101, и т.д.

4.4.5 Построение кода Хємминга

Код строится таким образом, чтобы в результате ρ = n – k проверок получить ρ – разрядное двоичное число, указывающее номер ошибочног разряда в кодовой комбинации.

Для этого проверочные символы должны находиться на позициях в кодовой комбинации, номера которых равны целой степени двойки, т.е. 2⁰, 2¹, 2²,…, 2^{ρ -1}, т.к. каждый из них входит только в одно из проверочных уравнений. Т.о. проверочные символы должны находиться на 1 – й, 2 – й, 4 – й … позициях (нумерация слева-направо).

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

Таким образом, в первой проверке должны участвовать символы, номера которых содержат единицы в двоичной записи в первом разряде: 001₂=1₁₀, 011₂=3₁₀, 101₂=5₁₀, 111₂=7₁₀, …

Вторая проверка дает цифру второго разряда синдрома т.е, во второй проверке должны участвовать символы, номера которых содержат единицу во втором разряде: 010₂=2₁₀, 011₂=3₁₀, 110₂=6₁₀, 111₂=7₁₀,… и т.д.

Т.о., синдром должен быть:

S₁ =b₁ Å a₃ Å a₅ Å a₇

S₂ = b₂ Å a₃ Å a₆ Å a₇

S₃ = b₃ Å a₅ Å a₆ Å a₇

Пример: Построить код Хэмминга 9,5 для информационной комбинации 10011. Т.к. информационные символы должны быть на третьей, пятой, шестой, седьмой, девятой позициях, то:

a₃ a₅ a₆ a₇ a₉

1 0 0 1 1.

Находим проверочные символы:

a₁ =b₁ = a₃ Å a₅ Å a₇ Å a₉ = 1 Å 0 Å 1 Å 1 = 1

a₂ = b₂ = a₃ Å a₆ Å a₇ = 1 Å 0 Å 1 = 0

a₄ = b₃ = a₅ Å a₆ Å a₇ = 0 Å 0 Å 1 = 1

a₈ = b₄ = a₉ = 1

Т.о. код Хэмминга будет: a₁ a₂ a₃ a₄ a₅ a₆ a₇ a₈ a₉

1 0 1 1 0 0 1 1 1

b₁ b₂ b₃ b₄

Пусть получена кодовая комбинация в коде Хэмминга: 101110111.

Определить есть ли ошибка, и при наличии ее исправить.

Считаем синдром для принятой комбинации:

a₁ a₂ a₃ a₄ a₅ a₆ a₇ a₈ a₉

1 0 1 1 1 0 1 1 1

S₁ = a₁ Å a₃ Å a₅ Å a₇ Å a₉ = 1 Å 1 Å 1 Å 1 Å 1 = 1

S₂ = a₂ Å a₃ Å a₆ Å a₇ = 0 Å 1 Å 0 Å 1 = 0

S₃ = a₄ Å a₅ Å a₆ Å a₇ = 1 Å 1 Å 0 Å 1 = 1

S₄ = a₈ Å a₉ = 1 Å 1 = 0

Получаем: 0101₂ = 5₁₀. Т.е.ошибка в пятом разряде.

Исправляем ее: a₁ a₂ a₃ a₄ a₅ a₆ a₇ a₈ a₉

1 0 1 1 1 0 1 1 1

Получаем правильную комбинацию: 101100111

Информационная кодовая комбинация G(x) степени (k-1) умножается на одночлен x ^n-k и прибавляется R(x) - остаток от деления данного произведения на образующий многочлен Р(х) степени ρ:

F(x) = x ^n-k×G(x) Å R(x)

Т.о. первые k символов полученной кодовой комбинации будут совпадать с информационными символами.

Пример:

Пусть k = 12. Построить циклический код с помощью образующего многочлена пятой степени Р(х) = х⁵ Å х⁴ Å х² Å 1.

Пусть G(x) = х¹⁰ Å х⁶ Å х⁴ Å х³ Å1, т.е. G(x) = 010001011001. Найти F(x).

Дата добавления: 2015-08-31