проверки на четность к проверочной матрице (5.21)

1111111111111111"

0001001101011110 0010011010111100 0100110101111000 1000100110101110

0 11110 11110 11

0 0 1 0 1 0 0 1 0

(10.35)

0 0 10 0 0 0 1 10 0 0

0 0 0 1 1 0 0 0 1

1 1 1 1

1 0 0 0 1 1 0 0 0 1 0

(а»)« (ai)« (а)» (а»)! (ai)i (а2)1 Ка")» («!)= (а2)з

. (а-)" (а-1)« О»

. (а-(а~) 01 . (а-2)з (а-1)з 03J

В качестве локатора этой дополнительной проверки выберем нулевой элемент поля. Так как все ненулевые локаторы являются степенями элемента а, то О также удобно представить в виде степени а, положив а°° = 0. Это соглашение является тастой условностью; оно не может быть получено предельным переходом, так как lim а" не существует. Если положить также О" = 1, то общую

проверку на четность можно интерпретировать как число ошибок, 5о = общем случае она представляет собой сумму значе-

ний ошибок: 5о = ] YiXl = Yt.

Многочлен локаторов ошибок для 1-удлиненного БЧХ-кода определяется уравнением (10.11); многочлен значений ошибок определяется уравнением (10.34), где суммы и произведения распространяются на все локаторы ошибок, возможно включая и Zj = а°°. Если ни одна из фактических е ошибок не имеет своим локатором а°°, то, как обычно, deg о = е и deg Q е. Однако если одной нз е ошибок соответствует локатор а°°, то deg а = е - 1 и deg Q = е, что следует из (10.34) и соотношения

degzl\{i-Xjz)=-.\

Зфг I с 1,

если Xl =а°°,

если Xj=a=° для некоторого

Мы подытожим этот результат в виде теоремы.

10.36. Теорема. Для i-удлиненного БЧХ-ко9а deg о < deg Q тогда и только тогда, когда имеется ошибка с локатором а».

Для декодирования 1-удлиненного БЧХ-кода можно использовать слабо модифицированный алгоритм 10.33. Используя теорему

10.36 на шаге 10.333, определяем наличие ошибки с локатором а°°; локаторы остальных ошибок могут быть определены с помощью процедуры Ченя. Значения всех ошибок можно затем вычислить на основании (10.32). Если произошла ошибка с локатором а°°, то ее величина определяется равенством

Q(0)

Й(2) = 21+чее"й(2-1).

Эта процедура декодирования 1-удлиненных БЧХ-кодов может быть представлена и в другой форме. Положим

о(") (z) = z(")o(") (z-i) и Q" (z) = z(»)Q" (z-i),

где многочлены a(") (z), (z) и D (n) задаются алгоритмом 7.4 как решения уравнения

(1+5 5ftz"+i)a(z) = Q(z).

fe=0

При такой формулировке ошибка с локатором а°° определяется точно так же, как и любая другая.

Если в 1-удлиненном БЧХ-коде .произошло не более t ошибок, то их локаторы задаются корнями многочлена о) (г) и их значения определяются при помощи формулы

Yi=-

Q<2<> (Xj)

П (Xi-Xj) ]ф1

Каждый элемент поля GF (q) является локатором некоторой позиции 1-удлиненного частного БЧХ-кода с блоковой длиной q. Эти коды обладают даже большей симметрией, чем обычные БЧХ-коды; 1-удлиненные БЧХ-коды инвариантны не только относительно циклических перестановок и подстановок Z,- -> Z? (следствие 5.82), а также относительно афинной группы подстановок над GF {q). Этот результат принадлежит Питерсону. Мы начнем с теоремы 10.37, доказанной Казами и являющейся слабым обобщением теоремы Питерсона.

10.37. Теорема. Пусть а - примитивный элемент поля GF (q), и пусть порождающий многочлен циклического кода с блоковой длиной q - I над GF (q) имеет вид g (х) = U (х - а"), zdt

К - множество целых чисел по модулю q" - 1. Предположим, чтс

О К и 1=5 О, если j К\]0. Пусть нуль поля выбран в качестве

локатора общей проверки на четность в 1-удлиненном коде. Тогда 1-удлиненный код инвариантен относительно аффинной группы подстановок, т. е. относительно группы подстановок вида

Xi -> uXi + v, и, vEGF (g"), и ф 0.

Замечания. Прежде чем доказывать теорему 10.37, рассмотрим следствия из нее. Согласно следствию из теоремы Лукаса

4.72, j О в поле характеристики р тогда и только тогда, когда

каждая цифра в р-ичном представлении числа / не превосходит по величине соответствующей цифры в р-ичном представлении числа к. В сокращенных обозначениях ( j ) тоща и только тогда, когда j S к.

В случае БЧХ-кода с исправлением t ошибок к К тогда и только тогда, когда для к выполняется сравнение к = iq mod {q - 1), где О < i < 2t. Если / к, то q~J сравнимо с числом <i, так что j € К [} 0. Следовательно, из теоремы 10.37 вытекает следующее утверждение.

10.371. Теорема (Питерсон). Каждый 1-удлиненный ВЧХ-код над GF (q) с блоковой длиной q" инвариантен относительно аффинной группы подстановок над GF {q).

10.372. Пример. Согласно теореме 10.37, код, задаваемый проверочной матрицей (10.38), инвариантен относительно подстановки Zj + а, которая переводит кодовое слово С =jCo,i,

С2, . .

С.о, Cs

Ci4, Cool в слово [С4, Со Се, Ci3, С12, С7, Cjl.

С5, С9, Со, С2, Сц, Ci4, Ci

Доказательство теоремы 10.37. Пусть Х-, ... - локаторы ненулевых позиций кодового слова в исходном 1-удлиненном коде, а У; - значения символов, соответствующие этим локаторам. Пусть Xi = uZ,- + - локаторы позиций кодового слова после подстановки. Если к К [) О, го = YiXi = = 0. Перестановка символов в кодовом слове дает кодовое слово тогда и только тогда, когда 5=2! (иг -\~ vf О для всех

к К \j 0. Согласно свойствам биномиальных коэффициентов, = = 2 У, 2 ( - ) X{v- = 2 ( ) ~Sj Согласно предположению

теоремы, если к К \] О, то для каждого / либо . j =0, либо

Sj = 0. В любом случае j 5 = О и 5 = 2 О = О Для всех

Казами, Лин и Питерсон [1967] показали, что если 1-удлиненный циклический код инвариантен относительно аффинной группы,

то к К, ."j фО =Ф i К и 0. Другими словами, условия теоремы 10.37 являются не только достаточными, но и необходимыми.

Группа подстановок, действующая на множестве М, называется транзитивной, если для любых двух элементов а, b М существует подстановка группы, переводящая а в Ь. Аффинная группа над GF (q"), очевидно, транзитивна. Этим свойством обладает также циклическая группа корней п-й степени из единицы, если (п, q) = i.

Из инвариантности 1-удлиненного двоичного кода относительно транзитивной группы подстановок вытекает следующее свойство его весовой структуры:

10.38. Теорема (П р е й н д ж). Пусть а - число кодовых слов веса г в линейном двоичном коде с блоковой длиной п, и пусть Ai - число кодовых слов веса i в i-удлиненном коде с блоковой длиной JV = п + i. Если {-удлиненный код инвариантен относительно транзитивной группы подстановок, то для всех j

aj i = 2;2;/Л = 2ia2jl{N - 2j).

Доказательство. 1-удлиненный код содержит точно = o-ij-i + a-ij кодовых слов веса 2/. Точно в aj- из них локатору а°° соответствует символ 1, и точно в aj из них локатору а~ соответствует символ 0. Суммарный вес кодовых слов с весом 2; равен 272; = 2/ {aj-x + aj). Так как 1-удлиненный код инвариантен относительно транзитивной группы подстановок, то этот суммарный вес должен быть равномерно распределен по локаторам кода. Каждому локатору должна соответствовать 1 в 2/ {aj- + + <2j)IN кодовых словах веса 2/. Так как локатор а°° не отличается от любого другого локатора, то

2]A2j i (aij-i-aj)

что эквивалентно утверждению теоремы, щ

10.39. Следствие. Если 1-удлиненный линейный двоичный код инвариантен относительно транзитивной группы подстановок, то минимальный вес исходного {неудлиненного) кода нечетен.

Из Jeopeмы Питерсона 10.371 и следствия 10.39 вытекает, что каждый двоичный БЧХ-код имеет нечетный минимальный вес.

(10.44)

а = ЛЯ.

При декодировании в проверочных соотношениях стертым символам приписываются произвольные значения. Если а" - корень порождающего многочлена, то затем в декодере определяются величины

5ft = S>A = i?(a")=-rW(a").

Если Xi - локаторы стираний, то У,- - разности между выбранными значениями стертых символов с локаторами Xi и передававшимися символами с локаторами Х;; если Xi - локаторы ошибок, то Yi - разности между полученными символами с локаторами Xi и передававшимися символами с локаторами Xi.

Ключевое уравнение (1 + S) о = со может быть записано в виде (1 S) АК = ы. В случае БЧХ-кодов общего типа, рассмотренных в разд. 10.3, ключевое уравнение выглядит так:

i+d-2

(1+2 5ftz+i-0A?, = Qmodz*.

Здесь d = 2< + 1 - конструктивное расстояние БЧХ-кода общего типа с исправлением t ошибок; величины - известные взвешенные степенные симметрические функции от локаторов искаже-

(10.46)

й-(1+ 2 Tz)X

Подстановка (10.46) в предыдущее уравнение дает

(10.47)

( S Tkz)Kszin-k)modz\

( 2 Thz-)X.r\ - Xmodz,

h=s+l

(1+2 nz-)X~цmodz-\

Если произошло t ошибок, то deg X = t я deg ц t. Если t < <: (d - s)/2, TO эта система уравнений может быть решена с помощью алгоритма 10.48.

10.48. Алгоритм.

10.481. Вычислить взвешенные степенные симметрические функции Si, iSj+i, . . ., »5г.£) 2 от локаторов искажений; вычислить по формуле (10.41) многочлен локаторов стираний и определить S = deg Л.

10.4. Совместное декодирование стираний и ошибок

Во многих приложениях при демодуляции иногда предпочтительнее не делать принудительного выбора среди наиболее вероятных возможностей и демодулировать достаточно сомнительные полученные сигналы не как одну из q букв входного алфавита, а как некоторую дополнительную букву, ?, называемую стиранием. При этом дополнительно к определению локаторов и значений ошибок декодер должен также пытаться определить стертый символ. Таким образом, задачей декодера является исправление всех искажений двух типов: стираний, для которых локаторы известны, а величины искаженных символов не известны, и ошибок, для которых не известны ни локаторы, ни величины. При декодировании полезно ввести в рассмотрение три различных многочлена локаторов:

(10.41) Многочлен локаторов стираний: Л = Д(1 -ZjZ),

Xi - стирания,

(10.42) Многочлен локаторов ошибок: Я. = [ (1 - Xiz),

Xi - ошибки, *

(10.43) Многочлен локаторов искажений: а = [j (1 - Xiz),

Xi - искажения, *

НИИ; Л - известный многочлен локаторов стираний; Я, - неизвестный многочлен локаторов ошибок; Q - неизвестный многочлен значений искажений.

Чтобы упростить ключевое уравнение, можно известные величины 5 объединить с известным многочленом локаторов стираний и использовать величины Г, введенные Форни [1965], которые определятся из уравнения

d-l l+d-Z

(10.45) 1+S 7j,z"=(l+ S 5ftz+i-)A.

При этом A И Q определяются уравнением

(l+S rftz)X = Qmodz.

Если произошло s стираний и t ошибок, то degk - t и degQ = s + f. Тогда

8 d-i

(l+S Jftz* + S Tftz") Я s Q mod z<,

( Tkz-) Я s Q (1 + S Tftz") mod z".

Так как левая часть делится на z*, то правая часть также делится на z. Определим многочлен т] равенством