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

Циклические коды, исправляющие пачки ошибок (коды Файра)

I. АЛГЕБРАИЧЕСКИЕ ОСНОВЫ ТЕОРИИ ЦИКЛИЧЕСКИХ КОДОВ | Поля Галуа и их свойства | Сложение многочленов | Умножение многочленов | Деление многочленов | Реализация операций умножения и деления многочленов в поле двоичных чисел | Матричное представление циклических кодов | Принципы исправления ошибок кодами БЧХ | ЦИКЛИЧЕСКИЕ КОДЫ РИДА—СОЛОМОНА | Кодированиеи декодирование кодов PC |


Читайте также:
  1. Азотсодержащие гетероциклические соединения
  2. Брана и циклические мультивселенные
  3. Глава 11 КАК ИЗБЕЖАТЬ ХАРАКТЕРНЫХ ОШИБОК
  4. Детекция ошибок
  5. ЕСЛИ ВЫ БЫ НАЧАЛИ СВОЮ СЕМЕЙНУЮ ЖИЗНЬ СНАЧАЛА, КАКИХ ОШИБОК ЗАХОТЕЛОСЬ БЫ ВАМ ИЗБЕЖАТЬ?
  6. Задание 4.Циклические вычислительные процессы. Решение задач, содержащих вычисление конечных сумм и произведений
  7. Зная источники ошибок, лучше понимаем метод

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

В общем виде коды Файра представляют собой цикличе­ские коды, производящий многочлен для которых имеет вид Р (х) = g (x)t(x), где g(x) и t(x) — неприводимые многочлены степени т и с соответственно над полем GF (р).

Из свойства 2.2 следует, что многочлен Р (х) должен быть делителем функции F (х) = хn — 1, где п — длина комбинации циклического кода. Выясним теперь, чему должна быть равна величина n. Пусть a1, а2,..., am, аm+1,..., a т+с —все корни многочлена Р (х). Из этих корней, например элементы α1,a2.., аm, являются корнями многочлена g (x), а остальные с элемен­тов являются корнями многочлена t(x).

Пусть корни многочлена g (x) имеют порядок у, причем y= 2m— 1, если многочлен g (x) примитивный; и у=d, где d — некоторый делитель числа 2m — 1, если g (х) непримитив­ный. Тогда в первом случае многочлен g (x) относится к показателю 2m —1 и является делителем двучлена (х2^m — 1), а во втором — относится к показателю d и является делителем дву­члена n-1) По условию F(x)=xn —1 делится на Р(х), т. е. делится и на g (х). Так как многочлен F (х) делится на g (х), то он должен делиться и на Y — 1), где y — порядок корней многочлена g (x). Аналогично, F (х) делится также на t (х) и (xv — 1), где v — порядок корней многочлена t(x). Из свойства 1.7 следует, что двучлены хY — 1 и хv —1 могут быть делителями функции F (х) = хп — 1 только тогда, когда у и v являются делителями п. Следовательно, длина кодовой комбинации п равна наименьшему общему кратному чисел y и х, т. е,

n=HOK(Y, v). (4.1)

Итак, комбинация кода Файра длины п имеет число прове­рочных элементов, равное степени многочлена Р (х), т. е. с+т, а число информационных элементов равно k = n— тс.

Коды Файра предназначены для борьбы с ошибками, груп­пирующимися в пачки. При этом код может работать как в ре­жиме обнаружения, так и в режиме исправления ошибок. В ре­жиме исправления коды Файра могут исправить любую оди­ночную пачку ошибок длины b≤ т, если т < с, или b ≤.с, если т > с. В режиме обнаружения коды позволяют обнаруживать любую одиночную пачку ошибок длины, не превосходящей (т + с).

Пусть многочлен пачки ошибок длины b≤(nk) имеет вид е (х)=xie1(x) где е1(х) — многочлен степени b—1. Чтобы обнаружить такую пачку ошибок, необходимо, чтобы многочлен е (х) не делился на Р (х) без остатка. Так как хi на Р (х) не делится, то поставленное требование будет выполняться, если на Р (х) не будет делиться e1 (х). Но по условию b≤ (п — k), поэтому е1(х) на Р(х) не делится, так как степень многочлена е1 (x) будет меньше степени Р(х). Следовательно, остаток от деления многочлена h (х), соответствующего принятой комбина­ции, намногочлен Р (х) всегда отличен от нуля, если длина пачки ошибок b≤(nk) = (т+с).

В [7] приведены и другие возможности кодов Файра по об­наружению пачек ошибок.

Перейдем теперь к описанию процесса исправления кодами Файрапачки ошибок длиной b. Пусть т < с, тогда b ≤т.

Предположим, что переданной кодовой комбинации соответ­ствует многочлен f(x), а принятой комбинации—многочлен h (х)=f (х) +e (х), где е (х) — многочлен ошибок. Так как многочлен е (х) соответствует пачке ошибок длины b≤т, то многочлен ошибки можно переписать как e (х) = хe(х), где e (х) — многочлен степени b — 1.

Отличительной чертой рассматриваемого метода является раздельное деление принятой комбинации, соответствующей многочлену h(x), на многочлен g (x) степени т и намногочлен t (х) степени с. В результате такого деления в регистрах сдви­га, соответствующих многочленам g (x) и t (x), получаются не­которые синдромы S1 (x) и S2 (x), которые будут нулевыми, ес­ли ошибок не было.


Учитывая, что корни многочлена g (x) имеют порядок у, акорни многочлена t (x) — порядок v, запишем

  Так как для кодов Файра п = НОК (у, v), из (4.3) следует, что

Пусть произошла одиночная пачка ошибок длиной b≤ т, соответствующая многочлену е(х). Тогда в результате деле­ния h (х) на g (х) и на t (x) получим синдромы S1(x) и S3(x), равные остаткам от деления е (х) на указанные многочлены, т. е.


Следовательно, как видно из сравнений (4.2) и (4.4), через (n-i) сдвигов синдромы в обоих регистрах будут одинаковыми и равными исправляемой комбинации ошибок e1(x). Действительно, умножая (4.2) на xn-i и приводя результат по модулям g(x) и t(x), что соответствует n-i сдвигам, с учетом (4.4) получим

 

 

Совпадение синдромов в обоих регистрах свидетельствует об обнаружении исправляемой комбинации ошибок, соответствующей многочлену e1(x). Это состояние обнаруживается специальным устройством на (n-i)-м сдвиге и с (n-i+1)-го сдвига должно начаться исправление. Этому сдвигу соответствует появление на выходе буферного накопителя элемента, равного коэффициенту при xn-(n-i+1)=xi-1 в h(x), т.е. обнаружение происходит уже после считывания из буферного накопителя пачки ошибок e1(x). Поэтому для исправления пачки ошибок e1(x) необходима задержка после буферного запоминающего устройства на m элементов. Но даже задержка в m элементов не может устранить ложное исправление, если пачка ошибок длиной b≤m будет расположена в m младших разрядах принятой комбинации. Избежать ложного исправления можно, если осуществить автоматическое умножение принимаемой комбинации h(x) на xm. При этом обнаружение пачки ошибок e1(x) по совпадению синдромов в обоих регистрах будет происходить на m тактов раньше. Действительно, сравнение (4.2) преобразуется так:

 

Отсюда, по аналогии с (4.5), совпадение синдромов, и, следова­тельно, обнаружение пачки ошибок, произойдет через п +i) сдвигов. Исправление начнется с [n-(m+i)+1]-го сдвига, при котором на выходе буферного накопителя появится элемент, являющийся коэффициентом при xn-(n-m-i+1)=xm+i-1 в h (x) и соответствующий старшему разряду в комбинации ошибок е(х). В течение т следующих сдвигов после обнаруже­ния e1 (х) произойдет полное исправление пачки ошибок е(х). В результате на выходе декодирующего устройства появится сумма h (x)+e(x) [mod 2], что соответствует переданной кодо­вой комбинации.

Заметим, что если c> т, то в момент обнаружения много­член e1 (х) будет находиться в первых m младших разрядах регистра, соответствующего многочлену t(х), в остальных же (с—т) разрядах должны быть нули, что проверяется специ­альным дешифратором.

Пример построения декодирующего устройства для рассмот­ренного метода исправления одиночных пачек ошибок длиной b≤ m приведем для производящего многочлена

P(x)=g(x)t(x)=(x3+x+1)(x4+x+1).

Здесь c=4,m=3, b≤3 и n=НОК (7,15)=105; (п,k)=(105,98).

Схема декодирующего устройства с автоматическим умно­жением на хm= х3 приведена на рис. 4.1.

Рис. 4.1. Декодирующееустройство кода Файра с раздельным делением h(x)на многочлен

g (X)= 1 + x + x 3 и t(x)=1+x+x4

 

 

В момент обнаружения исправляемой комбинации ошибок e1 (х), т. е. при совпадении остатков и при наличии нулей в ос­тавшихся т) разрядах регистра деления на t(x), переклю­чается ключ из положения I в положение 2, благодаря чему е1(х) поступает на выходной сумматор, в котором происходит исправление ошибок.

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

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


Дата добавления: 2015-07-16; просмотров: 165 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Принципы обнаружения и исправления ошибок циклическими кодами| ЦИКЛИЧЕСКИЕ КОДЫ БЧХ

mybiblioteka.su - 2015-2024 год. (0.009 сек.)