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

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

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

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

Пусть корни многочлена g (x) имеют порядок у, причем y= 2^m— 1, если многочлен g (x) примитивный; и у=d, где d — некоторый делитель числа 2^m — 1, если g (х) непримитив­ный. Тогда в первом случае многочлен g (x) относится к показателю 2^m —1 и является делителем двучлена (х^{2^m} — 1), а во втором — относится к показателю d и является делителем дву­члена (х^n-1) По условию F(x)=xⁿ —1 делится на Р(х), т. е. делится и на g (х). Так как многочлен F (х) делится на g (х), то он должен делиться и на (х^Y — 1), где y — порядок корней многочлена g (x). Аналогично, F (х) делится также на t (х) и (x^v — 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≤(n — k) имеет вид е (х)=xⁱe₁(x) где е₁(х) — многочлен степени b—1. Чтобы обнаружить такую пачку ошибок, необходимо, чтобы многочлен е (х) не делился на Р (х) без остатка. Так как хⁱ на Р (х) не делится, то поставленное требование будет выполняться, если на Р (х) не будет делиться e₁ (х). Но по условию b≤ (п — k), поэтому е₁(х) на Р(х) не делится, так как степень многочлена е₁ (x) будет меньше степени Р(х). Следовательно, остаток от деления многочлена h (х), соответствующего принятой комбина­ции, намногочлен Р (х) всегда отличен от нуля, если длина пачки ошибок b≤(n — k) = (т+с).

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

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

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

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

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

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

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

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

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

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

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

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

P(x)=g(x)t(x)=(x³+x+1)(x⁴+x+1).

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

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

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

g (X)= 1 + x + x ³ и t(x)=1+x+x⁴

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

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

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

Дата добавления: 2015-07-16