Декодирование систематических кодов

1. Декодирование с помощью полной кодовой таблицы. Рассчитаем параметры этой таблицы

 

N = 2⁵ = 32 – код пяти значений

N₀ = 2³ = 8 – разрешённая комбинаяция

N - N₀=32-8=24 – запрещённая коибинация (кодовых исправлений 24 ошибки)

 

Строим полную кодовую таблицу. В качестве первой строки используем разрешенные комбинации v₁ – v₈

 

00000	00011	01101	11010 01110 10111 11001 10100
00001 00100 01000	00010 00111 01011	01100 01001 00101	…

 

Общий метод декодирования состоит в следующем: Приняв некий вектор v_x, содержащий ошибку, его отыскивают в полной кодовой таблице и соотносят с тем кодовым вектором, который стоит в верхней строке этого столбца.

 

Пример: v_x=00111, находим в таблице и соотносят с 01 строкой, т.е. v = 00011

 

Достоинство метода: его универсальность, возможность применять различные стратегии.

 

Недостаток: громоздкость кода и только 3-и ошибки.

 

2. Декодирование с проверкой на четность.

 

С помощью ортогональных векторов u из матрицы Н можно установить связь между составляющими векторов v.

 

Используя условие ортогональности:

Составляющие  - берутся из матрицы Н, а  - из принятого вектора.

  схема проверок:

На основании векторов u можно записать схему проверок

 

 

Пример:, пусть принят вектор v_x = 00110. Он имеет координаты а₁ а₂ а₃ а₄ а_5. Составим схему проверок.

Если бы ошибок не было бы, то здесь были бы нули.

 

Возможность кода к исправлению ошибки можно объяснить схемой

 

	N символов
N-проверки	1	2	3	4	5
1		+		+	+
1	+	+	+

 

Следовательно, данный код может исправить во втором бите, обнаружить ошибку четвёртом или пятом бите, обнаружить ошибку в первом и третьем бите.

Для исправления всех ошибок надо, чтобы каждый бит появлялся в оригинальной комбинации строк в таблице проверки, и так будет, когда d₀=3 и добавиться ещё одна проверка.

 

3. Декодирование с помощью корректирующего вектора

 

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

Составляющие вектора С c₁,c₂,..,c_i представляют собой скалярное произведение принятого вектора v_x  на строки исправляющей матрицы . Вектор представляется двоичным числом С = c₁,c₂,…,c_к. Если ошибок нет, то С = 0

 

Рассмотрим i-ую строку полной кодовой таблицы

 - i-ая строка полная кодовая таблица

 

Умножим эту строку на вектор u_j, то получим

                    =0                         =0          =0

 

 - в каждой строке будет одной и той же величиной для любой кодовой комбинации.

Метод декодирования состоит из следующих операций:

1) По полной кодовой таблице и матрицы Н вычисляют корректирующий вектор С;

2) Принятый вектор v_x умножают на векторы матрицы Н и вычисляют корректирующий вектор.

3) Сравнивают полученные значения корректирующего вектора с имеющимся шаблоном и определяют ошибку

 

Пример: Нужно выбрать систему кодирования. Возьмём ту же систему кодов и H.

1. Определение шаблонов корректирующего вектора

                                                                  Векторы ошибок

шаблоны

                                      

Для вектора e₁ построение шаблона.

e₁:

      e₁×u₁ = 00001×01011 = 1 Þ C₁ = 1

      e₁×u₂ = 00001×11100 = 0 Þ C₂ = 0

Следовательно, вектору e₁ ставится в соответствие вектор С = (10)

Для e₂:

      e₂×u₁ = 00100×01011 = 0 Þ C₁ = 0

      e₂×u₂ = 00100×11100 = 1 Þ C₂ = 1

Для e₃:

      e₃×u₁ = 01000×01011 = 1 Þ C₁ = 1

      e₃×u₂ = 01000×11100 = 1 Þ C₂ = 1

 

Шаблоны известны на приёмной стороне ещё до посылки комбинации

 

2. Определение корректирующего вектора

 

Пусть принят вектор v_x = 01001

 

Сравниваем полученный вектор ошибки с нашим шаблоном и определяем, что это e₂.

 

3) Исправляем ошибку

, что соответствует комбинации v₃.

Можно строить образующую матрицу достаточно простым способом, например, единичной матрицей n_u ´ n_i.

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

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

 

Код Хэминга

 

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

, n = n_u + n_k, n – значность кода,

Количество контрольных разрядов можно определить по таблице. Номера позиций контрольных символов выбирают по закону 2ⁱ, i = 0,1,2… Значения контрольных разрядов выбирают следующим образом.

 

Алгоритм:

1) Составляется вспомогательная таблица для ряда натуральных чисел в двоичной коде, Число строк в таблице n – значность кода. В каждой i –й строке вспомогательной таблицы ставится в соответствие a_i коэффициент, который участвует в проверке, a_i – коэффициенты, из которых составлена кодовая комбинация

 

n	Код	Коэффиц-иенты	n	Код	Коэффици-енты
1	0001	а1	7	0111	a7
2	0010	a2	8	1000	a8
3	0011	a3	9	1001	a9
4	0100	a4	10	1010	a10
5	0101	a5	11	1011	a11
6	0110	a6	12	1100	a12

 

На основании этой таблицы составляется схема проверок, которые производятся суммированием выбранных проверочных коэффициентов . Для каждой поверки выбираются свои проверочные коэффициенты. В первую проверку входят коэффициенты, которые содержат в младших разрядах единицы. Во вторую проверку входят коэффициенты содержащие единицу во втором разряде(a₂,a₃,a₆,_…). В третью проверку входят коэффициенты содержащие единицу в третьем разряде.

Схему проверок сведём в отдельную таблицу.

Nпроверок	Схема	Nконтрольных. символов
1	a1 + a3 + a5 + a7 + a9 + a11	1
2	a2 + a3 + a6 + a7 + a10 + a11	2
3	a4 + a5 + a6 + a7 + a12	3
4	a8 + a9 + a10 + a11 + a12 +…	4

 

Количество проверок равно количеству разрядов. Контрольные коэффициенты выбираются таким образом, чтобы проверочная сумма была равна нулю. Т.е. если количество единиц чётное, то контрольный разряд нулевой, если нечётнно, то контрольный разряд равен единице.

 

Пример: Построить код Хэминга по комбинации

0101                        n_u = 4           n_k = 3        n_k = log(n_u + 1) + log(n_u + 1)

1,2,3                                                                        k = 7 2ⁱ = 1,3,4,8

Контрольные разряды будут занимать позиции 1,2,4.

 

Код Хэминга

а₁a₂a₃a₄a₅a₆a₇

k₁k₂0 k₃1 0 1          - макет

 

1) a₁ + a₃ + a₅ + a₇ = k₁ + 0 + 1 + 1 = 0 Þ k₁ = 0

2) a₂ + a₃ + a₆ + a₇ = k₂ + 0 + 0 + 1 = 0 Þ k₂ = 1

3) a₄ + a₅ + a₆ + a₇ = k₃ + 1 + 0 + 1 = 0 Þ k₃ = 0

 

Код Хэминга будет иметь вид 0100101

 

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

 

В процессе декодирования производится проверка на чётность по схеме проверок и строится вектор ошибок S(S_k, …,S₁). Если проверочная сумма равна нулю, то в вектор ошибки записывается ноль иначе записывается единица. Всего делается n_k проверок. В результате первой проверки определяется составляющая S₁, последней составляющая S_k. Если принятая кодовая комбинация содержит ошибку, то в векторе S образуется число, которое указывает номер ошибочной позиции.

	a1a2a3a4a5a6a7

 

Пример: Послана комбинация v_k = 0100101. Принятая комбинация v_x = 0100111, т.е. имеется ошибка в шестом разряде Составим схему проверок.

 

1) a₁ + a₃ + a₅ + a₇ = 0 + 0 + 1 + 1 = 0 Þ S₁ = 0

2) a₂ + a₃ + a₆ + a₇ = 1 + 0 + 1 + 1 = 1 Þ S₂ = 1

3) a₁ + a₅ + a₆ + a₇ = 0 + 1 + 1 + 1 = 1 Þ S₃ = 1

 

S = 110 ® это двоичное число шесть, что соответствует разряду a₆, следовательно, ошибка в шестом разряде.

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

 

Особенности декодирования.

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

 

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

0001            n_u = 4           n_k = 3

 

Макет кода

а₁а₂а₃а₄а₅а₆а₇

k₁k₂0k₃001k₄

 

Схема проверок:

1) a₁ + a₃ + a₅ + a₇ = k₁ + 0 + 0 + 1 = 0 Þ k₁ = 1

2) a₂ + a₃ + a₆ + a₇ = k₂ + 0 + 0 + 1 = 0 Þ k₂ = 1

3) a₁ + a₅ + a₆ + a₇ = k₃ + 0 + 0 + 1 = 0 Þ k₃ = 1

	11010010

1101001k₄             Количество единиц чётное, следовательно сам код

 

Рассмотрим пример для v_k = 01001011. Пример обнаружения единичной ошибки.

	a1a2a3a4a5a6a7

 

v_k = 01001011          Þ ошибка в четвёртом разряде

v_x = 01011011

 

1) Проведим проверки на чётность, которые указывают наличие одиночной ошибки.

2) Проведим проверку по позициям.

Составляем схему проверок

1) a₁ + a₃ + a₅ + a₇ = 0 + 0 + 1 + 1 = 0 Þ s₁ = 0

2) a₂ + a₃ + a₆ + a₇ = 1 + 0 + 0 + 1 = 0 Þ s₂ = 0          Þ S = (001) ® a₄

3) a₁ + a₅ + a₆ + a₇ = 1 + 1 + 0 + 1 = 1 Þ s₄ = 1

 

Пример: Обнаружение двойной ошибки.

 

V_k = 01001011

V_x = 11011011

 

1) Делаем проверку на чётность, число единиц чётное, следовательно, проверка ошибки не обнаруживает.

2) Делаем проверки по позициям

 

 

Схема

1) a₁ + a₃ + a₅ + a₇ = 1 + 0 + 1 + 1 = 1 Þ s₁ = 1

2) a₂ + a₃ + a₆ + a₇ = 1 + 0 + 0 + 1 = 0 Þ s₂ = 0          Þ S = (101)

3) a₁ + a₅ + a₆ + a₇ = 1 + 1 + 0 + 1 = 1 Þ s₃ = 1

 

В этом случае S не указывает разряд ошибки, но S просто показывает, что она есть.

 

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

 

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

Идея построения циклических кодов базируется на использовании неприводимых в поле двоичных чисел многочленов.

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

                          x³x²x¹x⁰

Например: u(x) = x³ + x² +1 ® 1 1 0 1

 

Построим циклический код. Образующий многочлен к(х) = х³ + х + 1 = 1011. При построении циклических кодов существует несколько приёмов.

1. Умножим кодовый вектор u(x) на одночлен той же степени, что и образующий многочлен.

u(x) * xⁿ = (x³ + x² + 1) * x³ = x⁶ + x⁵ + x³ = 1101000

                                                        инф.. корректирующие разряды

                                                       часть

Чтобы уточнить значения корректирующих разрядов производят деление . Делить можно используя полиномы и значения двоичных разрядов.

 

Разделим один многочлен на другой

1101 000 1011                              ®                001

1011                                                             1101001

1100

1011

1110

1011

   1010

   1011

     001 ® остаток от деления - он прибавляется к исходной комбинации

 

1101000

      +   001

        1101001 - искомый циклический код

 

В общем виде можно записать

 , где Q(x) – частное; K(x) – остаток

Умножим левую и правую часть k(x) и получим:

u(x) * xⁿ = Q(x) * K(x) + R(x)

u(x) * xⁿ + R(x) = Q(x) * K(x) – знак перед R(x) не имеет значение

= F(x) – это цикловой код.

 

Т.о. получается дваспособа образования циклического кода:

1) Путём умножения одной из комбинаций информационной части кода на образующий многочлен:

Q(x) * K(x) = I(x)

 

2) Умножение заданной комбинации на одночлен и той же степени, что и выбранный образующий многочлен с добалением остатка от деления.

Эти способы являются теоретическим основанием для построения кодирующих и декодирующих устройств.

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

Для построении циклических кодов обычно используют образующую матрицу.

 

Способы построения образующей матрицы:

Первый способ

1) Образующая матрица получатся как результат слияния двух матриц: Первая - единичная повёрнутая размером n_u.

 

n_u = 4                         

 

Дополнительная матрица имеет n_u – строк и n_k – столбцов. Для определения строк дополнительной матрицы используют результаты делений последней строки первой повёрнутой матрицы на образующий многочлен.

 

1 0000 … k(x)

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

 

Пример: k(x) = 1011

Рассмотрим процедуру деления

 

Остаток 011 110 111 101 001 010 100

100000… 1011

1011

01100

1011

1110

1011

    1010

    1011

      001000

          1011

В дополнительной матрице используются лишь те остатки, вес которых W = d₀ – 1.  d₀ – минимальное кодовое расстояние. Строки образующей матрицы представляют собой первые комбинации искомого кода. Остальные комбинации получают суммированием различных сочетаниям строк.

 

Второй способ

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

 

Третий способ

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

 

Декодирование циклических кодов

 

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

 

Таблица неприводимых двоичных многочленов

 

Код	Многочлен	Код	Многочлен
11	x + 1	10001	x^4 + 1
101	x^2+ 1	10011	x^4+ x + 1
111	x^2 + x +1	10101	x^4+ x^2 +1
1001	x^3+ 1	10111	x^4 + x^2 +x + 1
1011	x^3 + x +1	11001	x^4 + x^3 + 1
1101	x^3+ x^2 + 1	11011	x^4 + x^3 + x + 1
1111	x^3+ x^2 + x + 1	11101	x^4 + x^3 + x^3 +1
		11111	x^4 + x^3 + x^2 + x + 1

 

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

 

Код, исправляющий одиночную ошибку. d₀ = 3.

1) Расчёт соотношении между контрольными и информационными символами кода.

 

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

 

2) Выбор образующего многочлена производится по таблице непреводимых двоичных многочленов. Образующий многочлен следует выбирать с минимальным числом элементов. Его степень должна быть больше или равна числу контрольных разрядов. Число элементов должно быть .

 

Пример: Построим циклический код d₀ = 3 для передачи шестнадцати сообщений.

n_u = 4           n_k = 3

 

k(x) = 1011               Строим единичную повёрнутую матрицу размером n_u

Находим остатки от делений последовательной строкина образующий многочлен.

 

Остаток 011 110 111 101

10000 1011

1011

01100

1011

1110                                              

1011

   101

 

 

1+2  2+4  1+2+3+4

1+3  3+4

1+4  1+2+3

2+3