Лекции.Орг


Поиск:




Категории:

Астрономия
Биология
География
Другие языки
Интернет
Информатика
История
Культура
Литература
Логика
Математика
Медицина
Механика
Охрана труда
Педагогика
Политика
Право
Психология
Религия
Риторика
Социология
Спорт
Строительство
Технология
Транспорт
Физика
Философия
Финансы
Химия
Экология
Экономика
Электроника

 

 

 

 


Основные теоремы об ошибках, обнаруживаемых циклическими кодами




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

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

Вектор одиночной ошибки е(х) имеет вид е(х)=хi, где . Очевидно, что хi не делится без остатка на многочлен, который состоит из более одного члена. Следовательно, теорема доказана.

Теорема 2. Любой кодовый многочлен циклического кода с порождающим многочленом g(x)=1+x содержит четное число членов.

Пусть v(x)=(1+x)*a(x) и информационный полином a(x) содержит «m» членов. После умножения будет два многочлена а(х) и х*а(х) каждый их которых также будет содержать по «m» членов. Из общего числа 2m членов часть может попарно уничтожится. Пусть таких пар m1. Остается членов 2m-2m1=2(m-m1) – четное число. Следствием этого является факт,

а) что g(x)=1+x обнаруживает все нечетные ошибки. Полином ошибок с нечетным числом единиц не является кодовым по теореме.

, следовательно Р(х) содержит нечетное число единиц запрещенных комбинаций.


б) Любой циклический код, образованный полиномом 1+х также обнаруживает все нечетные ошибки, такие как

1+х=(1+х)(1+х+х2+…+хl-1).

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

е(х)=хi+…+хj, i<j£n-1.

Длиной пачки называют число b=j-i+1, то есть это число символов в пачке, Очевидно, что b£n.

Теорема 3. Любой циклический код, образованный при помощи полинома степени (n-k), обнаруживает любую пачку ошибок длиной b=n-k и менее. Пачке ошибок длиной b=n-k соответствует полином

e(x)=xi+xi+1+…+xj=xi(xn-k-1+…+1).

Первый множитель xi не делится на образующий полином g(x), состоящий более, чем из одного члена. Второй множитель имеет степень n-k-1 или меньше. Степень полинома g(x)=(n-k) больше степени многочлена делимого. Следовательно, деление t(x) на g(x) без остатка невозможно, то есть пачка ошибок обнаруживается всегда.

Теорема 4. Относительная доля пачек ошибок длиной b=n-k+1, обнаруживае-мых циклическим (n,k) кодом равна (по отношению ко всем возможным пачкам длины n-k+1).

Вектор ошибки в этом случае будет иметь вид: e(x)=xi×e1(x), гду е1(х) обязательно содержит члены нулевой степени и степени n-k. Члены со степенями 1,2,… и n-k-1 могут либо присутствовать, либо их нет. Число таких наборов равно 2n-k-1.

Если ошибка e1(x) не обнаруживается, то e1(x)=g(x)×q(x), где e1(x) делится на образующий полином без остатка. Т.к. степень g(x) равна n-k, то степень q(x) равна n-k-n+k=0. Значит q(x)º1, то есть имеется ровно один вектор е1(х), который делится без остатка (он имеет вид образующего полинома). Получаем, что из 2n-k-1 различных пачек длиной n-k-1, не обнаруживается только одна, а относительное число необнаруживаемых пачек ошибок равно .

Теорема 5. Относительная часть пачек ошибок длиной b>n-k+1, необнаруживае-мых циклическим кодом (n,k), составляет от общего числа всех возможных пачек ошибок длиной b.

Для необнаруживаемых ошибок вектор ошибки e1(x)=g(x)×q(x). Если b>n-k+1, то полином q(x) имеет члены от x0 до xb-n+k-1, число слагаемых между этими крайними степенями, которые могут быть, а могут и не быть b-n+k-2, то есть имеется различных результатов от деления на g(x)2b-n+k-2 (необнаруживаемых пачек ошибок).

Число различных вариантов пачек ошибок длиной b будет равно 2b-2. Следовательно, часть необнаруживаемых пачек ошибок составляет , что и следовало доказать.





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


Дата добавления: 2016-11-19; Мы поможем в написании ваших работ!; просмотров: 566 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Есть только один способ избежать критики: ничего не делайте, ничего не говорите и будьте никем. © Аристотель
==> читать все изречения...

2217 - | 2173 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.008 с.