Главная страница  Алгебраическая теория кодирования 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [ 32 ] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78]

ИЗ коэффициентов при неизвестных о, Oj,

Sk • • • S2 Si

Oft имеет вид

.Szk-i • Sk+i Sk Если определитель матрицы oMk отличен от нуля, то система имеет единственное решение о, Оа, . . ., о. Традиционным методом отыскания решения {о/,} по заданным величинам {Sj} является определение наибольшего к, для которого eSk невырожденна, и последующее решение соответствующих уравнений.

Вопрос о вырожденности матриц е#й можно решить с помощью следующей теоремы:

7.51. Теорема.

Дефект oS = \ D {2к-\-i) - к \, = k-\D "

., 2/с - 1

Ранг cSk = k-\D{2k-{-l)-k\.

Доказательство. Для i = к, к + I, к + 2, определим многочлены

т) тогда и только тогда, когда i - D{i)-k-l; 2k-i-i(j(i) тогда и только тогда, когда i - D{i)>k.

Так как i - D{i)>k тогда и только тогда, когда 2А; -г -1 + + £>(г)<А; -1, то для i = k, k-i, ..., 2k - l

degp(»)<A; -1.

Сопоставим каждому многочлену р() /с-мерный вектор-столбец

Введем теперь (А; X А;)-матрицу р, столбцы которой совпадают с векторами р():

(2h-l)

pW p(ft+l)

p(2ft-l)

Lpf-ipri" ... Pi-Vi Мы утверждаем, что эта матрица невырожденна. Действительно, если линейная комбинация ее столбцов равна нулю, то

2ft-1 i=ft

2ft-1 2ft-1

i=ft

если i - D{i)k, в остальных случаях, если г -D(i)<A;-1, в остальных случаях.

Если агфО, то (1-f 5) pW =22--ico(*) modz* и degz--W)< <2A;-i-l-f Z)(0<A;-1. Если ЪгФО, то (1+ 5)т(») = v(*-+z*modz*+ и degY(*)<A;-1. Следовательно, если ih = bft+i=... ... = h.j.l = О, но feft+y ф О, то

2ft-1

{i + S) S Cip(*) = i + bft+z+ modz++i,

2ft-1

где deg К/с -1. Значит, если ЗсгР*)=0, то 6 = 0 для г = А;,

2ft-1

i=ft

А;-1-1, к + 2, ...,2к-1 и S aiz2-*-%W=0. Но если азфО

i=ft

И akJt-j+i = aft+j+2 = ... = a2ft-i = О, то

2ft-1

2 aiz-aii) aft+fz"--! modz""". [t=ft

2ft-l

Таким образом,- 2 Cip = Q тогда и только тогда, когда Cj=0

для всех i, и, значит, р - невырожденная матрица.

Так как матрица р невырожденна, то ранг е#й равен рангу произведения матриц aSkp - al- Столбцы матрицы имеют вид ор(*), i~k, к-{-1, ...,2к - 1, или, с учетом структуры матрицы оЖи,

вид Р*> = [

ft >

ft-fl)

4ft-i], где Sfz = (l+5)p(*).Ecли

p(i)=.z2"-*-%(i), то i-D{i)>k, degz2--ia«<A;-l, (l + 5)p<«) = = z*"--!©) mod z", так что P< = е#р() = 0. С другой стороны, если р(*)=т(0, то degv<*)<j -D(iXA;-1 и (1-j-) р(«) = v*) = = z*modz+i. так что Р<*> =айрО) = [О, О, ...,0, 1, ...]. (Номер первой ненулевой координаты вектора Р* равен г-(А;-1).) Отсюда следует, что ( - треугольная матрица с нулями над главной диагональю; каждый ее элемент на главной диагонали равен нулю или единице, а через нули главной диагонали проходят нулевые



D{i+l)

I i + l--D.(i)

если D (i) > или если Aj,* = 0, J4-l-;Z).(i) в остальных случаях.

v(i)

Очевидно, что D (i) - монотонная неубывающая функция аргумента i и что D (i) < i/2 только тогда, когда D (i) = D (i - 1)-

Следующее замечание состоит в том, что отрезок целых чисел i, для которых D (i) i - к, не должен иметь пропусков. Действительно, если£» (0< i - А; < j -Ь 1 - А; < i> (i + 1), то£» (i -f 1) = = i + 1 - £» (О > А; -f 1 и£» (у) = £> (j + 1) > А; + 1 > / + 1 - А;

для / = i + 1, i + 2, . . ., 2А;- 1. Если £» (2А; - 1) = А; - /, / > О, то

Г k - ji - k для i = 2k - j, . .., 2А;-1; = \ >j A;, для ik, k + i, 2k-j-l.

В этом случае дефект аМ равен j = к - D {2к - 1). С другой стороны, при D (2А; - 1) = А; -f /, / > О, существует такое т, что если D (2А; - 1) = А; - /, / > О, то

( k + j>i - k прм i = m, m + i, ..., 2k - i;

" \ m - i- ki - k при f = wi -/,..., wi-l.

В этом случае дефект Ли равен / = D(2A; -1) -А;. Значит,

дефект aMk=\D{2k-i) - k\; ранг cSk = k-\D{2k~i)-k\.

Это эквивалентно теореме 7.51. щ

*7.6. Упрощение алгоритма 7.4 для двоичных БЧХ-кодов

Алгоритм 7.4 предназначен для определения многочленов а (z) и (О (z) наиболее низких степеней, дающих решение ключевого уравнения (7.23) для произвольной заданной последовательности S, S, . . ., St- Однако в случае двоичных БЧХ-кодов последовательность Si, S, S3, . . ., St не произвольна. Величины Sj должны быть симметрическими функциями от е локаторов ошибок Xi, Х, • • •

. . ., Хе. Даже если e>t, то Sn = % Х\, а = S Zf =

- (.S = Sh- Следовательно, производящая функция S (z)

удовлетворяет уравнению [S (z)] = 2 Sh = S (z), где, так же

как и в разд. 3.2, знак «"» употребляется для обозначения четной части, а знак j<~"» - для обозначения нечетной части функции. Уравнение S = S для производящей функции, как будет сейчас показано, позволяет значительно упростить итеративный алгоритм.

7.61. Лемма. Пусть \ -\- S и l-fi? взаимно обратные производящие функции в поле характеристики 2: (1 -f 5) (1 -f Л) = = 1. Равенство R = О выполняется тогда и только тогда, когда S = S\

Доказательство. Разложение равенства (1+5) (1+ Л) = = на четную и нечетную части дает: (1 + 5) (1 + Л) + 5Л = 1 и 5 (1 + Д) + (1 + 5) Л = 0. Вычтем из первого равенства, умноженного на (1 - 5), второе, умноженное на 5. Тогда [(1 - 5) -

- 51(1 + Д)= 1 + , откуда

1 +

В поле характеристики 2 имеем (1 + 5) - 5 = 1 + 5 + 5 = = 1 + (5 + 5)* = 1 + 5 и R = О тогда и только тогда, когда 1 + 5 = 1 + 52 или 5 = 52. щ

7.62. Те о р е м а. Если в поле характеристики 2 выполняется равенство 5 (z) = [5 (z)], то величины, участвующие в алгоритме 7.4, удовлетворяют условиям

Af =0,

I т(0,

если i четно; если i нечетно; если i нечетно.

Доказательство. Применим индукцию по числу 1. Для 1 = 0 теорема справедлива. Мы утверждаем,\ что если

столбцы. Нуль-подпространство матрицы Ли является линейной оболочкой столбцов pW = z~~o<>, ранговое пространство e#ft натянуто на столбцы матрицы для которых < =(1+5)т>. Дефект матрицы аМи равен дефекту а последний в свою очередь равен числу таких i, А;<г<2А;-1, что i-D{i)>k, или D{i)i - k. Из алгоритма 7.4 вытекает, что



И, следовательно,

(j(2ft+2)o(2ft+l), (0<2+2)=(0<2А+1), тЬ+З) = zxtft+D, .y{2fe+2) = zV<2ft+l), (0<2+2) = aft+S), Y<+2 = T(2ft+2).

He очевидно здесь только равенство А[= 0. Для его доказательства* рассмотрим сравнение

(1 + 5) а(2А+1) = 0(2"+!) + Д l*+>z2+ mod гг+з. Умножив обе части на 1+i?, согласно лемме 7.61, получим

a<2h+l) = o(2ft+l) Л0(2Ь+1) Д(2й+1)22(1+2 mod z2+3, а(2й+1) Л0(2)!+1) = д(2Н1)226+2 mod z2+3.

Так как функция в левой части нечетная, то Ai""* = 0.i

7.63. Теорема.

degaW = D(A:), degt:W=k~D{k).

Доказательство. Предположим, что deg o> = D (к) и deg xt") = к - D (к). Равенство deg = deg xt") + 1 выполняется только тогда, когда А; нечетно, причем в этом случае Д(Ь) = 0. Отсюда следует, что deg а") Ф deg А*") zxt"). Согласно алгоритму 7.4, at) = о*") - Azxt"). Так как слагаемые в правой части этого равенства имеют разные степени, то deg о"*) = = max (deg a), deg Azxt")} = D (к + 1). Легко проверить, что deg x(*) = к + i - D (к + i). Так как deg о(«) = deg х(") = О = = D ф), то, используя индукцию по к, получаем утверждение теоремы, щ

Теоремы 7.62 и 7.63 позволяют вычислить функции оС), хС), а(2), х(), . . ., а(), х() с помощью сокращенного алгоритма, в котором не участвуют многочлены (о, у. и нечетные части многочленов опт.

7.64. Сокращенный алгоритм (для двоич-. ных БЧХ -кодов). Сначала полагаем оС) = 1 и х(") = 1. Строим рекурсию следующим образом. Если величина S2k+i неизвестна, то вычисление останавливается; в противном случае полагаем величину Д<2*) равной коэффициенту при z* в произведении

7.6. Упрощение алгоритма 7.4 для двоичных БЧХ-кодов (1 + S) о). Пусть

<j(2fe+2) q2k) Д(2)2т;(2й),

z2x(2fe), если Д = 0 ИЛИ если dega(2fe)>A:;

T;(2ft+2) i (2h)

д(2й)

если А[фО и если dego(2fe)<A:.

Из этого алгоритма очевидно следует, что

(7.65) . 7">-0, если А:>0.

Можно также упростить формулу для общего решения сравнения (1 +5)a = amodz2+i при начальном условии а(0) = 1. Ссялас-но теореме 7.43,

а = С/а(20 + Ут<2). После умножения на 1 + 5 получим

(1 + 5) а = С/ (1 + 5) о(2) + F (1 + 5) х(2«),

(l + 5)a = C/o(20 + Fx(20. Эта функция является четной только тогда, когда

(7.66) ии, F = F.

Указанные упрощения для двоичного случая основаны на свойствах матрицы

1 0

0 .......

52 Si Si 5з

1 .......

So 5, 1

• Sk-i

52fe-2 .

Следующей, достаточно утомительной, но необходимой задачей является доказательство равенства

-;i dega(2)-

(7.67)

Дефект еЖк =

где квадратные скобки обозначают наибольшее целое число, не превосходящее содержимого скобок ([5/2]=2;[-1/2]== -1). Доказательство этой теоремы вполне аналогично доказательству теоремы 7.51, если для 1 = 0, 1, 2, . . ., А: - 1 положить

f x(2i), если degx(2)<A: -1,

о(2») = <

1 z2-2i-ia(2i), если dega(2i)<2i -А. Это доказательство мы предоставляем читателю.




[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [ 32 ] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78]

0.0167