Доказательство. Так как 1 д\ а равенство достигаеа ся тогда и только тогда, когда i = О, то 2г?> S i-

15.575. Лемм а. Справедливо неравенство Wq {х + у) < Wq (х) + Wq (у), причем равенство достигается тогда и только тогда, когда Xi + У, < g для всех г.

Доказательство. Положим c i = О и для i > О опре-. делим Ci и Zi равенством

(15-5751) Ciq + Zi--Ci. + Xi+Yi,

где 0<Zi<g и С; 0. Умножая (15.5751) на д и суммируя но i,-получим 2 Ziq =х + у и, значит, Wq{x + y)=Zi. Непосредственнс

суммируя равенства (15.5751), получаем (д - 1) 2с< + 2=1

= Si-f2b так что Wq{x + y)=Wq{x) Wq{y)-{q-l)Ci.

i i j

15.576. Лемма, Еслиx°\ x\ x, произвольные целые 4ucj,

=-2iV, 0<;Xf<g, mo wqij] x>)KWq{x<>), приче

i i=0 i=0

равенство достигается тогда и только тогда, когда 2Г<

г = 0

для всех ].

Доказательство. Лемма 15.576 вытекает непосредственн( из леммы 15.575, если применить индукцию но к. щ

15.577. Лемма. Если qp\ пю Wp{x)>Wp(Wq{x)).

S- 1

Доказательство. Пусть 2 2 г, jpV- 0<Хг</7

3 г = 0

S- 1 S- 1 .

Тогда Wq{x)Yi 2 Xi,jp\ По лемме 15.576 (2 2 грО]

3 1=0 3 i=0

< 2 2 {Хи jp) 2 2 = и. ш

i г=0 3 г=0

15.578. Лемма. Если a>Q и s>Q, то (а [р- 1]) > s (j3 - 1)J

Доказательство. Пусть q = p\ ж*»=а (р-1) и =

= u;g(a;)- Ввиду леммы 15.574, <а:<, причем равенстве

юстигается тогда и только тогда, когда х < д. Положим = lima:. Ясно, что а:=а;°° для всех достаточно больших i.

г->-оо

Согласно лемме 15.573, a:<+i=а:<*mod (д-1), так что а;(°° = а:«» = ..-l)mod(g -1). Так как из а:О следует, что а:<+О, тоа:<~=50 и, значит, а;°" = д -1. По лемме 15.577 Шр(а:<+1) = (wg (х>)Х .ii (а:), так что (ж<~)<№р (а:"*)- Так как а:°°-=д-1 =

S- 1

-{Р-) 2 Р% то ap(x->) = (p-l)s. I

15.58. Теорема (Грэхем, Мак-Вильямс [1966], Мак-Вильямс, Манн [1968], Гёталс, Делзарт [1968] и Смит [1967, 1969]). р-ичный иГ-код порядка (m-i, s) с длиной ге= (р""-1)/(р -1) имеет

1р + т-2у lp + m - 2\

j проверочных ы и-1 -

1

iihix символов.

информацион-

Доказательство. Пусть q = р\ Р - примитивный корень п-й степени из единицы, а р GF (д™). В силу определения 15.53, т(>оремы 14.74 и леммы 15.571 - корень порождающего многочлена кода тогда и только тогда, когда для всех ;

(15.581)

Wq ([g- i]ip)q-i.

Для вычисления числа проверочных символов кода достаточно найти число целых чисел i по mod п, удовлетворяющих условию (15.581). Однако легче найти число целых чисел х = [д - 1] i по модулю д"- 1, удовлетворяющих условиям

(15.582)

0<х<д"- 1, (д-1)х, Wq {хр) q - i для всех /.

Если (д - 1) I X, то (д - 1) I хр для всех По лемме 15.573 7 - 1) I хр тогда и только тогда, когда Wq {хр) = О mod (g - 1). Поэтому условия (15.582) для всех / можно заменить условиями

(15.583)

0<х<д"-1, Щ {хр) = I Q

Если ж > 1, то х = д""- 1 не удовлетворяет условию Wq{x) = - g - 1, тай что условие О х < д™- 1 можно заменить неравенством -х <i g". Если для некоторого / имеем Wq {хр) = О, то

X = 0. Следовательно, любое ненулевое решение системы (15.583 должно быть также решением системы

О < а; < д™,

(15.584) iVq (хр) = q - i для всех /.

m-ls-l

Положим теперь х- 2 ipq, тде 0<Ай, г<р. Согласно! г=о fe-о

лемме 15.572,

(15.585) Wq (V) = 2 YkP- + S ПР,

(15.586)

Уь - 2 Xk, I.

Если Ук>P для некоторого К, то в силу (15.585) Wg {хр--) YfiP д, что усиливает условия (15.584). Из равенства (15.585) вытекает также, что Wg {хр~) = У к mod р. Так как {q - 1) = - 1 mod р, то заключаем, что Yk = р - 1 для всех К. Следова тельно, условие (15.584) эквивалентно условиям

(15.5871) 2 Xk,i = p-l для всех к = 0, 1, s-l.

Последовательность Zo, Z, 1, . . ., Xm-i длины т можно запи- сать в виде последовательности Х,о единиц, за которыми следуе запятая, за ней Х, единиц, затем снова запятая, .... Следовав тельно, число способов выбора неотрицательных чисел Х, о, fc, и . .., Xk, m-l, в сумме дающих р - 1, равно числу способов, которы-i ми можно разместить р - 1 единиц и та - 1 запятых в (р + та - 2) позициях. Следовательно, число чисел х, удовлетворяющих условиям (15.587), или число ненулевых решений системы (15.583), равно (р + т2у

[ P-i )

В заключение этого раздела опишем процедуру вычисления числа проверочных символов в ЕГ-кодах порядка (О, s).

15.59. Вычисление числа проверочных сим- волов в ЕГ-коде порядка (О, s). Пусть g = р и а -j примитивный элемент поля GF (д"). Согласно определению 15.51,1 свойству 14.74 и лемме 15.571, сс" - корень порождающего много-! члена 1-укороченного р-ичного ЕГ-кода порядка (О, s) и длины д"- 1 тогда и только тогда, когда для всех /

(15.591)

гд (а;р) > 9 - 1-

Число проверочных символов 1-укороченного ЕГ-кода равно, таким образом, числу целых чисел х, О х < д""- 1, удовлетворяющих условию (15.591). В неукороченный ЕГ-код входит, кроме того, общая проверка на четность, которую можно связать с числом х = д""- 1. Так как Wq {Iq"- 1] р) (g - 1) для всех то число проверочных { имволов в ЕГ-коде равно числу таких целых х, что О а; <; д"

т-1S - 1

II выполняются условия (15.591). Если положить х = 2 S Х ipq

1=0 h = 0

где О Xfe, I < Р, то в силу леммы 15.572 условия О х < д™ и (15.591) могут быть записаны в виде

;15.592) 2\>V- + 2пр"+>(д-1) для всех /,

(15.593)

h=s-i h=0

n= 2 А.ь oXk,i<p.

Пусть By - число последовательностей Xf,, Х, ны та, удовлетворяющих уравнениям

у= 2 Xi, o<:z,<p

для Z = о, 1, 2, . . ., та - 1.

Число By зависит от р и та. Если р = 2, то By =

., Xm-i дли-

Если

у •< р, то, как следует из заключительных рассуждении в доказа-

-та- 1

точное

/?/-f та- 1\

тельстве теоремы 15.58, By = I. При 2 < р г/

\ У /

выражение для By имеет более сложный вид. Рекурсивные формулы iT производящие функции для By были получены Риорданом [1958], причем он рассматривал By как число разложений величины у -\- т точно на та слагаемых, каждое из которых не превосходит р.

Для заданной последовательности неотрицательных чисел Fs-i, ) s 2, . . ., YQ, удовлетворяющих неравенству (15.592), величины Х,

удовлетворяющие условию (15.593), моншо выбрать [ Ву способами.

Условие (15.592) на самом деле относится к последовательности 5 S-1, 5 S-2 . . ., 10 и всем ее циклическим сдвигам. Как и в гл. 12, мы будем рассматривать эту последовательность как спепление нескольких базисных последовательностей. Они вводятся следующим образом:

. . ., Yq называется дефектной, если 2 <- 1 ДЛЯ ;

; = 1, 2, . . ., к. Если Уй 1, Ffe-a, . . ., Уо - дефектная последова-;

тельпость, то ее дефектом называется число р - 1 - 2 h-iP"

Базисной называется недефектная последовательность, все собственные префиксы которой дефектны.

Пусть Z)f -число выборов чисел Z,;, О < Z < m; О < /с < /, для которых последовательность У-х, У-г • • м определенная;

согласно (15.593), имеет дефект i. Пусть Z)() (г) = 2 f- Так как

дефект пустой последовательности равен О, то положим

(15.595)

(z) = 1,

Если дефект последовательности У-х, Уу-2, • • •> равен i иУо<:; < pi + р - 1, то дефект последовательности У;-1,. Уу-г, • • •. Yii У о равен I тогда и только тогда, когда Z=pf4-P -i-Уо- Отсюда заключаем, что для Z 1

(15.596)

D {z) = zBpUp.iD (z).

Для любых заданных р w. т можно определить производящие! функции Д() (г), Z)(2) (z), . . . как решения системы линейных урав- нений (15.595) И(15.596).

Если через Vj обозначить число выборов чисел Z, i, О I <i О к <С j, которые в соответствии с условием (15.593) приводя к базисной последовательности У-t, У; 2! • • • > то для производЯ"г

щей функции F(z)= 2 Vj очевидно, выполняется равенство

ОО оо

(15.597) F(z)-z2( S Bj)D>{z) =

i = 0 3=pi+P-l

ОС p-2 ОС оо

= z(2 Bj- 2 Bj)+z 2 ( 2 Bj)D>{z)

- " • " i=l 3=ip+P-l

+ z 2 ( 2 5,-)z)<*>(z).

/1 J=l 3=>P+P-1

3 = 0

p"-

j = 0

m + p -2\ m

Используя определение 15.594 и непосредственную анало!

с доказательством теоремы 12.23, можно доказать следующую лемму

15.598. Лемма. Любая последовательность неотрицательных чисел Ys-i, У8-2> • • Yg, удовлетворяющая условию (15.592), однозначно представима в виде сцепления базисных последовательностей {включая окаймляющую последовательность).

Так же, как теорема 12.33 сразу приводит к теореме 12.35 (или, )i обозначениях производящих функций, к уравнению (12.61)), так ! лемма 15.598 сразу н})иводит к теореме 15.599.

15.599. Теорема. Если г {р, т, у, s) - число проверочных сц.чволов р-ичного ЕТ-кода порядка (у, s) с длиной п = р"", то

2 г{р, т, О, s)z-j5-

где V (z) определяется уравнением (15.597) и V (z) = dV/dz. Примеры.

Если m = 1, то

F(z) = z; r(z)= 2 z.

s= 1

Если 772 - 2 ), TO

F(z)z(p-()) = ,(

s=l V

P+i\

fp + i\ 2

r(z) =

Если 777 = 3 и p = 2, TO

r(z)

- 72 + 40z2--6033 "~ (1 -10z + 20z2) (1

10-40z

I / 10-

3z)-\ 1-lOz

+ 20z2

1 -3z /

15.6. Сверточные коды - обзор

15.61. Введение. Кодер блокового кода со скоростью передачи R и длиной 77 разбивает поступающие из источника данных символы на блоки по к = Rn символов. Каждый из блоков кодируется оолее длинным блоком из п символов и передается затем по зашум-ленному каналу.

) Этот сличай совпадает с частным случаем задачи 15.8.

15,594. Определение. Последовательность Уй 2>