Использование циклических кодов для обнаружения пакетов ошибок

Глава 1.

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

В сетях для обнаружения ошибок используются метод добавления контрольной суммы (КС), которая вычисляется на основе передаваемых данных.

Основную задачу можно сформулировать следующим образом: по принятому сообщению определить, возникли ли ошибки в ходе передачи данного сообщения.

Ниже на рис. 1.1 приведен алгоритм формирования контрольной суммы. Кодер хранит порождающий многочлен g(x), для каждой передаваемой последовательности

Общий вид алгоритма		Конкретный пример
Кодер хранит порождающий многочлен g(x). Степень многочлена deg(g(x)) = r равна количеству бит в КС. k – число информационных символов передаваемого сообщения Для выполняются следующие действия:		g(x)=x³+x+1, deg(g(x)) = 3.
1.	На основе последовательности формируется многочлен m(x). Степень многочлена m(x) при этом меньше или равно k–1.	m(x)=x³+x
2.	Вычисляется многочлен c(x)=m(x)x^r mod g(x). Степень многочлена c(x) при этом меньше или равно r–1.	c(x)=(x³+x)x³mod (x³+x+1)=x+1
3.	Вычисляется многочлен a(x)=m(x)x^r+c(x).	a(x)=x⁶+ x⁴+x+1
4.	На основе многочлена a(x) формируется последовательность длина которой n бит, где n=k+r.

Рис. 1.1. Описание алгоритма формирования КС с примером

Теорема 1.1. Для любого передаваемого сообщения многочлен a(x), сформированный на третьем шаге алгоритма, делится без остатка на порождающий многочлен g(x), то есть a(x)mod g(x) = 0.

Доказательство:

Предположим, что выбрана произвольная последовательность

Следовательно, a(x)=m(x)x^r+(m(x)x^rmod g(x)).

a(x)mod g(x)=[m(x)x^r+(m(x)x^rmod g(x)] mod g(x)=m(x)x^r mod g(x)+

+(m(x)x^r mod g(x)) mod g(x)= m(x)x^rmod g(x)+ m(x)x^rmod g(x)=0.

По данной теореме может быть предложен следующий алгоритм декодирования. Декодер хранит g(x)и n (длину кодового слова).

1. Принятое сообщение переводится в многочлен b(x)

2. Вычисляется синдром: s(x) = b(x) mod g(x)

3. Если s(x) ≠ 0, то декодер выносит решение, что произошли ошибки (Е = 1), иначе декодер выносит решение, что ошибки не произошли (Е = 0).

Пример 1.1.

g(x)=x³+x+1, =1010011, =0000011→b(x)=x+1.

Пример 1.2.

g(x)=x³+x+1, =1010011, =0001011→b(x)= x³+x+1.

Определение 1.1. Кодом называется множество последовательностей, которое может появиться на выходе кодера, при поступлении на вход всевозможных информационных последовательностей.

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

Определение 1.3. Линейный код

Одним из главных свойств линейных кодов является следующее свойство:

На рис. 1.2 приведена структурная схема системы передачи информации. Рассмотрим работу кодера, канала и декодера.

Канал связи

s(x)=b(x) mod g(x)

Рис. 1.2. Система передачи информации

где – вектор ошибок, он описывает, в каких битах произошли ошибки при передаче по каналу связи.

1 –ошибка произошла.

0 – ошибка не произошла.

Ошибка декодирования равна

В примере 1.2:

Теорема 1.2. Ошибка декодирования происходит только в том случае, когда вектор ошибки принадлежит множеству кодовых слов A.

Доказательство:

Рассмотрим случай, когда Вектор ошибок Тогда декодер вычисляет следующим образом:

Из теоремы 1.2 следует теорема 1.3.

Теорема 1.3. Ранее описанная система кодирования и декодирования позволяет найти количество ошибок, равное d–1 вне зависимости от того, где эти ошибки произошли.

Доказательство:

Доказательство основано на методе от противного.

Предположим, что число ошибок f≤ d–1,

Это означает, что и декодер не обнаруживает ошибки.

Следовательно: минимальный вес меньше d получили противоречие.

Замечание: предположим, что число ошибок f≥d. В зависимости от того, на каких позициях эти ошибки произошли, декодер может их обнаружить или не обнаружить.

Использование циклических кодов для обнаружения пакетов ошибок

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

l=4

Рис. 1.3. Примеры пакетов ошибок

Теорема 1.4. Если предположить, что в системе используется порождающий многочлен g(x), у которого deg(g(x)) = z и известны n и d, то в таком случае, данная система позволит обнаруживать любые одиночные пакеты ошибок, длина которых меньше, либо равна r.

Проиллюстрируем теорему 1.4 на следующем примере.

Пример 1.3.

Пусть g(x)=x³+x+1, r=3, n=7, d=3. По теореме 1.3 значение f≤2. Сообщение m(x)=x³+x². Контрольная сумма (x⁶+x⁵) mod (x³+x+1)=x. Тогда кодовое слово . Если ошибка , то слово, полученное на выходе из канала связи равно

Доказательство:

Рассмотрим частный случай, когда вектор ошибок расположен в младших разрядах кодового слова (рис. 1.4).

n

00…0

n

1

1

n

l

По условию теоремы l≤r

Рис. 1.4. Частный случай вектора ошибок

Тогда s(x)=b(x) mod g(x)=(a(x)+e(x) mod g(x)= a(x) mod g(x)+ e(x) mod g(x)

Левое слагаемое в последнем выражении равно нулю по теореме 2, следовательно, deg(e(x)) = (l – 1) < r.

Дата добавления: 2018-06-01; просмотров: 951; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 4 5 6 7 8 9 10 Следующая ⇒

Мы поможем в написании ваших работ!