Исправление ошибок с помощью полной

Кодовой таблицы

Процесс исправления ошибок поясняется с помощью диаграммы.

A_k – разрешённые комбинации                    B_j – запрещённые комбинации

 

А₁ может искажена и может превратиться в B₁ или B₂ и т.д. в любую из запрещённых комбинаций. Запрещённые комбинации делятся на подмножества H_k.

Способ приема состоит в том, что если принимается комбинация B_j, которая попадает в подмножество М_к, то считается, что принята комбинация А_к (M₁ соответствует тому, что передавалась комбинация A₁).

Исправляющая способность кода будет зависеть от выбора разбиения или от стратегии.

 

Пример: Рассмотрим пример построения КУ. Пусть l_i – вектор ошибки, он имеет те же размерность, что и кодовая комбинация. 1 – искажения есть, 0 - искажений нет. Пусть кодируется набор из 4-х комбинаций.

 

А₁=0001

А₂=0101

А₃=1110

А₄=1111

 

 

Bj=А_к+l_i

 

li	Ак				q
	0001	0101	1110	1111	1
0001 0010 0100 1000	0000 0011 - 1001	0100 0111 - 1101	- 1100 1010 0110	- 1101 1011 0111
0011 0101 1001 0110 1010 1100	0010 0100 1000 0111 1011 1101	0110 0000 1100 0011 - 1001	1101 1011 0111 1000 0100 0011	1100 1010 0110 1001 - 0011	2
0111 1011 1101 1110	0110 1010 1100 -	0010 - 1000 1011	1001 - 0011 0000	1000 0100 0010 -	3
1111	-	1010	-	0000	4

 

Разбиение

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

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

 

М1	М2	М3	М4	q
0000 0011 1001	0100 0111 -	1100 1010 0110	1101 1011 -	1
0010	-	1000	-	2

 

Т.е. Исправили десять одинарных и две двойные ошибки.

Если статистика ошибок такова, что большую вероятность имеют ошибки высшей кратности, то разбиение изменяют: оставляют комбинации в строках с высшей кратностью и вычеркивают в строках с низшей.

 “-“ значит действие помехи переходит в разрешенную комбинацию и мы ее обнаруживаем.

 

М1	М2	М3	М4	q
1101	-	0111	-	2
0110 1100	1000 1011	0001 0011	0100 0010	3
-	1010	-	0000	4

 

Если статистика ошибок такова, что какая-нибудь комбинация искажается больше, чем другие, например, комбинация А₁, то стратегия разбиения будет другая: оставляем все кодовые комбинации соответствующие А₁, т.е. М₁, а остальные вычеркиваем: комбинации, которые не совпадают, остаются

А1 М1	А2 М2	А3 М3	А4 М4	q
0000 0011 1001	- - -	1100 0010 0110		1
0010 0100 1000 0111 1011 1101				2

Систематические коды

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

Кодовый вектор – последовательность 0-й и 1-й кодовой комбинации.

Вес кодового вектора – число единиц в кодовой комбинации.

Нулевой вектор – кодовая комбинация, состоящая из одних нулей.

 

n – значность кода (из скольки символов состоит кодовая комбинация);

n_u – число информационных разрядов;

n_k – число контрольных разрядов;

 

Пример: Для систематических кодов применяют обозначение:

Код(n, n_u)            Код (5,3)

 

Построение систематических кодов производится следующим образом: в качестве первого берется нулевой вектор, затем составляется производящая матрица. Она имеет n_и – строк, n – столбцов. В качестве строк производящей матрицы берутся любые линейно независимые n-значные векторы, отстоящие друг от друга не менее, чем на заданное кодовое расстояние. Строки матрицы G – являются кодовыми векторами. Первый вектор - нулевой.

Линейно независимыми называются векторы, для которых выполняется условие:

v₁, v₂,...,v_к

v₁ + v₂ +...+ v_к ≠ 0

 

Остальные кодовые векторы определяются количеством:

 где

 - всего (общее число кодовых векторов);

  - находится в производящей матрице;

1 –нулевой вектор.

 

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

Для обнаружения ошибок составляется множество проверочных векторов, ортогональных векторам кода. Т.е. если кодовый вектор v образован символами а₁, а₂,…, а_n, а ортогональный вектор u образован символами – b₁, b₂,..., b_n, то

Из векторов u составляется проверочная матрица Н. Она имеет n_к – строк, n-столбцов. Строками матрицы Н являются любые линейно-независимые векторы u.

 

Пример: Пусть строится код (5,3) с минимальным кодовым расстоянием d₀=2. Он позволяет обнаруживать все одиночные ошибки. Составим производящую матрицу G:

                   Три строки, т.к. n_u = 3, n = 5 – столбцы

                                                       Комбинации        Результат комбинации

1 + 3

1 + 2 + 3

2 + 3

1 + 2

Строки матрицы G

Нулевой вектор

                                              

 

Можно было бы построить G из любой другой тройки векторов, кроме сочетаний v₂v₃v₅, v₂v₄,v₁ и т.д. (семь штук), т.к. эти сочетания линейно зависимы, т.е. v₂ + v₄ + v₇ ≠0.

Построим ортогональные векторы u (проверочные).

 Составим для векторов v₂, v₃, v_8. Эти вектора имеют минимальное количество единиц.

v₂ 0 × b₁ + 0 × b₂ + 0 × b₃ + 1 × b₄ + 1 × b₅ = 0

  b₄ + b₅ = 0

v₃ b₂ + b₃ + b₅ = 0

v₈ b₁ + b₃ = 0

 

Для любого вектора u должно выполняться

 

Перебирая все удовлетворяющие этим условия сочетания, получили:

u₁ = 00000

u₂ = 01011

u₃ = 10111

u₄ = 11100

 

Из этих векторов необходимо составить проверочную матрицу Н

- т.к. они линейно независимы