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

↑

▷ Содержание

⇐ ПредыдущаяСтр 6 из 8Следующая ⇒

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

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

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

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

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

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

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

А₁=0001

А₂=0101

А₃=1110

А₄=1111

Bj=А_к+l_i

Разбиение

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

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

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

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

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

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

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

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

Кодовый вектор – последовательность 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

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

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

Познавательные статьи:



Формы дистанционного обучения

Передача мяча двумя руками снизу

Значение правильной осанки для жизнедеятельности человека

Основные ошибки при выполнении передач мяча на месте