Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:

algebcodes_1

.pdf
Скачиваний:
54
Добавлен:
03.06.2015
Размер:
2 Мб
Скачать
☆

8.3. Асимптотические границы

 

 

 

 

261

и потому

 

 

 

 

 

 

 

 

 

 

1

 

1

 

1

 

√

 

 

exp −(

+

) ≥ exp(−

) = 0.895 ≥

π

= 0.887.

 

 

 

 

 

12λn

12µn

9

2

Собирая найденные результаты, получим нижнюю границу

 

 

Cnλn

= Cnµn >

√

 

 

1

.

 

 

 

 

λnµµn

 

 

 

8λµnλ

 

Примем теперь во внимание,что

 

 

 

 

 

 

 

1

= q− logq(λ

n

n

 

 

 

 

 

 

 

 

µ

 

) = qnHq(λ),

 

 

λ

λn

µn

 

 

 

 

 

 

µ

 

 

 

 

 

 

 

 

 

где

 

 

 

 

 

 

 

 

 

 

(8.3.14)

Hq(λ) = −λ logq λ − (1 − λ) logq(1 − λ).

(Иногда функцию Hq(x) определяют, как

Hq(x) = x logq(q − 1) − x logq x − (1 − x) logq(1 − x);

ее называют энтропией q-ичного симметричного канала с вероятностью ошибки x. Здесь же символ Hq(x) употребляется в смысле (8.3.14)).

Окончательно имеем

 

 

 

 

1

qnHq(λ) < Cnλn = Cnµn <

1

qnHq(λ)

(8.3.15)

 

√

 

√

 

 

8λµn

2πλµn

Читателю предлагается убедиться, что неравенства справедливы и на случай λn, µn < 3. Например, если λn = µn = 1, то

λn + µn = 2, (λ + µ)n = 2, n = 2, λ = µ = 1/2. Подставив эти

 

 

 

 

1

 

4

 

 

значения в (8.3.15), получим 2 = C2

<

√

 

.

 

π

 

Оценим теперь сумму n

Ci , положив λn целым числом

 

 

 

n

 

 

 

 

 

при условии 1/2 < λ < 1. ∑i=λnlnλ

,

где l есть некоторое поло-

Для этого умножим ее на 2

жительное число, и рассмотрим цепочку неравенств

 

 

n

n

n

 

 

 

 

 

 

 

∑

i∑

∑

 

 

 

 

 

 

2lnλ

Cni ≤

2liCni ≤

2liCni

= (1 + 2l)n.

(8.3.16)

 

i=λn

=λn

i=0

 

 

 

 

 

 

262 Глава 8. Сводка границ

Разделив выражение (8.3.16) на величину 2lnλ, а затем положив l = log2(λ/(1 − λ)), получим

∑n Ci ≤ (2−lλ + 2l(1−λ))n = i=λn n

=(2−λ log2(λ/(1−λ)) + 2(1−λ) log2(λ/(1−λ))n =

=((λ/(1 − λ))−λ + (λ/(1 − λ))1−λ)n =

=((λ/(1 − λ))−λ(1 − 1/(1 − λ)))n == (λ−λ(1 − λ)−(1−λ))n =

=q(−λ logq λ−(1−λ) logq(1−λ))n = qnHq(λ).

Благодаря (8.3.16), при 0 < µ < 1/2 выполняется также и

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

µn

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

∑i

< qnHq(µ).

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ci

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

µ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

=0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Тривиальным образом

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

−

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

µn

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

∑i

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

qnHq(µ) < Cnµn <

Cµi .

 

 

 

 

 

 

 

 

 

 

 

 

√

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

8(1 µ)µn

 

 

 

 

 

 

 

 

 

 

=0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Окончательно

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

√

−

 

 

 

 

 

 

 

 

 

 

 

 

µn

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

∑i

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1

 

 

 

qnHq(µ) < Ci

< qnHq(µ)

 

 

 

 

 

 

 

 

 

 

 

 

 

8(1

 

 

µ)µn

 

 

 

 

 

µ

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

=0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Теперь асимптотические границы выглядят следующим об-

разом:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Граница Хэмминга

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

t

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

t

 

 

 

k

1

 

 

∑i

Cni (q −1)i ≤ 1 −

 

t

 

 

 

1

 

∑

Cni ≤

 

 

≤ 1 −

 

logq

 

 

 

 

logq(q

−1)

−

 

logq

 

 

n

n

=0

n

n

i=0

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

t

 

 

1

 

 

 

 

 

t

 

 

 

d

 

 

 

 

 

 

 

d

≤ 1−

 

 

 

logq(q−1)−

 

logq qnHq

(

 

 

) = 1−

 

logq(q−1)−Hq (

 

) .

 

 

 

 

n

n

n

2n

2n

На случай четного d граница совпадает с (8.3.17).

(8.3.17)

 

 

 

 

 

Граница Бассалыго — Элайеса

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

k

(1 −

1

) (1 − √1 −

 

 

qd

 

) logq(q − 1)−

 

 

 

 

 

 

 

≤ 1 −

 

 

 

 

 

 

 

 

 

n

q

(q − 1)n

 

 

8.3. Асимптотические границы

263

−Hq

((1 − q ) (1 − √

 

 

)) .

1 −

(q − 1)n

 

1

 

 

qd

Не сообщая вывода неасимптотической формы "границы четырех" (граница Мак-Элиса— Родемича — Рамсея—Велча), приведем ее асимптотическую форму1

 

 

 

 

k

 

≤ x logq(q − 1) + Hq(x),

 

 

 

 

n

где

 

 

 

 

 

 

 

 

 

x =

q − 1 − nd (q − 2) − 2√

 

 

 

.

(q − 1) nd (1 − nd )

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

q

 

 

 

 

 

 

Граница Варшамова—Гилберта.

 

 

 

 

 

 

Если выполняется условие

 

 

 

 

 

 

 

 

k

 

d

 

 

 

d

 

 

 

≤ 1

−

 

logq(q −

1) − Hq

(

 

) ,

 

 

n

n

n

то существует код с параметрами (n, k, d).

1С подробностями читатель может ознакомиться по книгам [7, 12].

Глава 9.

Регистры сдвига с линейными обратными связями

9.1. Элементарные устройства

Регистр сдвига действует в режиме дискретного времени и состоит из элементарных устройств трех видов:

1. Двухвходовый сумматор. Если на входы поступают величины a и b, то на выходе в тот же момент времени появляется сумма a + b (рис. 9.1a).

2. Устройство умножения на константу поля GF (q). Оно имеет один вход и один выход. Если устройство производит умножение на константу α GF (q), и на вход поступает элемент β GF (q), то в тот же момент времени на выходе появляется произведение αβ. В случае поля GF (2) умножение на константу 1 есть прямое соединение, а умножение на константу 0 есть отсутствие соединения, разрыв (рис. 9.1b.)

Сложение и умножение выполняются в поле GF (q).

3. Элемент задержки на такт. Этот элемент как раз и осу-

ществляет сдвиг. Значение на его выходе в момент времени t+1 равно значению на его входе в момент времени t, т.е. в преды-

дущий момент. Этот элемент есть также элемент памяти. Он "помнит" , что было на его входе, или что то же, что было его содержимым в предыдущий момент времени. (рис. 9.1 c.)

Нас совершенно не интересуют электрические характеристики перечисленных устройств. Их различные соединения открывают возможности графического выполнения чисто математических операций. Начнем с простейших.

9.2. Вычисления в полях Галуа

265

β

AB

α GF(q)

xt

 

xt+1 = xt

 

 

 

 

 

 

 

 

 

 

 

A + B

αβ

 

A)

B)

C)

Рис. 9.1. a) сумматор; b) элемент умножения на константу поля; c) элемент задержки.

9.2. Вычисления в полях Галуа

Рассмотрим устройство, изображенное на рис. 9.2.

Рис. 9.2. Генератор поля GF (24) по модулю многочлена x4 + x + 1.

Во-первых, оно содержит четыре элемента задержки, которые составляют регистр сдвига. В каждом из элементов задержки (памяти) может содержаться одно из значений 0 или 1. В каждый момент времени содержимое этого регистра может рассматриваться как векторное изображение элемента поля GF (24).

Поместим в регистр вектор (1000) и будем производить его последовательные сдвиги слева направо, как это показано стрел-

ками. В результате первых трех сдвигов содержимое регистра будет последовательно меняться следующим образом: (0100), (0010), (0001). В результате следующего сдвига содержимое регистра станет (1100). Читатель уже вспомнил, что именно так

266

Глава 9. Регистры сдвига

строилось поле GF (24) (3.4.11) по модулю многочлена x4+x+1. Как только происходит очередной сдвиг единицы, находящейся в последнем элементе задержки, она прибавляется к символам, находящимся в первом и втором элементах задержки. Это в

точности соответствует формуле x4 = x+1. Если α4 +α+1 = 0, т.е. α есть примитивный элемент поля, то излагаемый процесс работы регистра сдвига есть возведение α в последовательные

степени и построение мультипликативной группы поля GF (24).

Рис. 9.3. Генератор поля GF (24) по модулю многочлена x4 + x + 1. Показатели степеней порождающего элемента убывают.

Рассмотрим также устройство, изображенное на рис. 9.3.

Как и выше, поместим в регистр вектор (1000). Будем производить его последовательные сдвиги справа налево, как это

показано стрелками. В результате первого сдвига содержимым регистра будет вектор (1001), в котором читатель узнает элемент α14 = α−1 GF (24). Устройство реализует построение поля GF (24) в порядке убывания степеней элемента α.

Совместное применение обоих устройств может выполняться следующим образом.

Поместим в устройство рис. 9.2 элемент αi, а в устройство

рис. 9.3. — элемент αj. Одновременные сдвиги обоих регистров приведут к тому, что в регистре рис. 9.2 показатели степеней α, будут расти, а в регистре рис. 9.3 — убывать. Когда в ре-

гистре рис. 9.3 наблюдатель увидит элемент 1=(1000)=α0, он будет знать, что произошло в точности j сдвигов, а значит, содержимое регистра рис. 9.2 умножится на αj и станет равным

αi+j. Так происходит умножение двух произвольных элементов поля Галуа.

Пусть теперь требуется разделить элемент αi на элемент

αj. Поместим α−j в регистр устройства рис. 9.2, а элемент αi

— в регистр рис. 9.3. Одновременные сдвиги обоих регистров приведут к тому, что, когда в регистре рис. 9.2 окажется вектор

1=(1000)=α0, в регистре рис. 9.3 будет вектор αi−j. Читатель без труда проведет самостоятельно соответствующее рассужде-

9.3. Умножение и деление многочленов

267

ние. Регистры сдвига с линейными обратными связями находят более значительное практическое применение.

9.3. Умножение и деление многочленов

Рассмотрим регистр сдвига, показанный на рис. 9.4.

 

 

 

...

 

 

 

В••••

HR

HR 1

HR 2

HR 3

 

H2

H1

H0

В•••

AI

AI 1

...

AI R 3

AI R 2

 

AI R 1

AI 2

 

Рис. 9.4. Регистр сдвига для умножения на многочлен h(x).

Он реализует умножение произвольного многочлена

a(x) = a0 + a1x + . . . + ak−1xk−1 + akxk

(9.3.1)

над GF (q) на фиксированный многочлен

h(x) = h0 + h1x + . . . + hr−1xr−1 + hrxr

(9.3.2)

с коэффициентами из того же поля. Все элементы умножения реализуют умножение на коэффициенты hi, i = k, k − 1, . . . , 0 многочлена h(x). Перед началом процесса умножения элементы задержки содержат нули. В начальный момент времени на вход регистра поступает коэффициент ak, и на выходе тотчас появляется произведение akhr, т.е. коэффициент при xk+r многочлена a(x)h(x). В следующий момент времени на вход поступает ak−1, и на выходе появляется сумма akhr−1+ak−1gg, т.е. ко-

эффициент при xr+k−1. Процесс продолжается до тех пор, пока последний коэффициент a0 не появится на выходе последнего элемента задержки, а на выходе регистра — a0h0, т.е. младший коэффициент произведения многочленов.

Вслед за последним коэффициентом a0 многочлена a(x) на вход регистра поступают нули, которые заполняют регистр к

моменту появления на его выходе коэффициента a0h0. Умножение закончено.

268

 

 

 

Глава 9.

Регистры сдвига

 

 

...

 

 

 

В••••

H0

H1

H2

HR 3

HR 2

HR 1

HR

В•••

Рис. 9.5. Регистр сдвига для умножения на многочлен h(x). Сумматоры встроены в регистр

Умножение произвольного многочлена a(x) на фиксированный многочлен h(x) можно выполнить и на другом регистре, который показан на рис. 9.5.

Его отличие от предыдущего состоит в том, что сумматоры вынесены из линии обратной связи и встроены в регистр между элементами задержки, а коэффициенты многочлена h(x) следуют в порядке возрастания, а не убывания индексов.

В первый момент времени, когда содержимое регистра равно нулю, старший коэффициент ak многочлена a(x), поступивший на вход регистра, немедленно и одновременно умножается на все коэффициенты hi. Но на выходе в этот момент времени появляется только старший коэффициент akhr произведения многочленов. После первого сдвига в элементах задержки содержатся произведения akh0, akh1, . . . , akhr−1, вход равен ak−1, а на выходе появляется сумма akhr−1 + ak−1hr, т.е.

второй коэффициент многочлена-произведения. Читатель без труда проследит процесс умножения до конца.

... В••••

H

H

H

H

3

H

2

H

H 1

0

1

2

R

R

R 1

R

В•••

...

Рис. 9.6. Регистр сдвига для деления на многочлен h(x).

На рис. 9.6 представлен регистр сдвига, предназначенный для деления произвольного многочлена

a(x) = a0 + a1x + . . . + anxn

(9.3.3)

9.3. Умножение и деление многочленов

269

над GF (q) на фиксированный многочлен

 

h(x) = h0 + h1x + . . . + hr−1xr−1 + hrxr

(9.3.4)

с коэффициентами из того же поля. Читатель заметил две

основные черты схемы деления: все коэффициенты делителя, кроме старшего, взяты со знаком минус, а вместо старшего ко-

эффициента делителя взят обратный ему элемент h−r 1 GF (q). Именно эти черты и характеризуют процесс деления. Действительно, рассмотрим процесс деления "столбиком".

На первом шаге деления старший член anxn делимого делится на старший член hrxr делителя, т.е. умножается на h−r 1.

Первое неполное частное есть anh−r 1xn−r.

(Так как показатели степеней определяются нижними ин-

дексами соответствующих коэффициентов, то упоминание о них опускается, что и усматривается непосредственно из строе-

ния регистра. Поэтому далее будем говорить только о делении коэффициентов).

Затем делитель умножается на неполное частное и вычитается из делимого. Но это равносильно тому, что на неполное частное умножается делитель, взятый с противоположным знаком, и складывается с делимым. Это обстоятельство и изоб-

ражено на рис. 9.6. Так получается первый остаток. С ним происходит то же самое, что и с делимым, и т.д.

Перед началом работы регистра он заполнен нулями, и деление начинается, как только старший член делимого достигнет выхода последнего элемента задержки. Это случится на (r + 1)−м шаге работы регистра. Процесс деления заканчивается, когда коэффициент a0 поступит на вход регистра. В этот момент в последнем элементе задержки окажется коэффици-

ент при xr−1. Степень содержимого регистра меньше степени делителя. Деление прекращается. В регистре оказывается остаток. На рис. 9.7 представлен регистр сдвига для деления на

многочлен g(x) = 1 + x3 + x4 + x5 над GF (2).

В •••

В•••

Рис. 9.7. Регистр сдвига для деления на многочлен g(x) = 1 + x3 + x4 + x5 над GF (2)

270

Глава 9. Регистры сдвига

Как уже наверняка догадался читатель, регистры сдвига для умножения и деления на многочлен заведомо могут быть употреблены для целей кодирования и декодирования.

9.4.Линенйные рекуррентные соотношения и генераторы с регистром сдвига

Построенные в предыдущем разделе схемы можно рассматривать как результат некоторой общей теории.

Пусть в выражении

∑k

hjai+j = 0

(9.4.5)

j=0

hj GF (q), h0 ≠ 0, hk = 1. Это равносильно соотношению

k−1

 

 

∑j

hjai+j = 0.

(9.4.6)

ai+k = −

=0

 

 

Решением этих уравнений является последовательность

a0, a1, . . . , ak−1.

По любому комплекту k известных последовательных значений al вычисляется (k + 1)−е. Линейная комбинация решений есть снова решение, и все решения образуют линейное векторное пространство размерности k.

Пусть величины hj, j = 0, 1, . . . , k, h0 ≠ 0, трактуются как коэффициенты нормированного многочлена

∑k

h(x) =

hjxj,

(9.4.7)

 

0

 

и условимся, что n это минимальное натуральное число, при котором h(x) делит двучлен xn − 1. Будем также интерпретировать решения уравнения (9.4.6), т.е. последовательности a0, a1, . . . , an−1, как коэффициенты многочлена

a(x) = a0xn−1 + a1xn−2 + . . . + an−1,

(9.4.8)

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]