17.7. АСИМПТОТИЧЕСКИЕ ГРАНИЦЫ

В этом разделе рассматриваются асимптотические оценки, применимые, когда велико. Оказывается, что в этом случае проще всего записывать результаты как функцию скорости кода наибольшей мощности

от отношения Наилучшие известные к настоящему времени оценки изображены на рис. 17.7. Все коды лежат не выше верхней границы Родемича — Рамсея — Велча (теоремы 35, 37), в то время как наилучшие коды лежат не ниже нижней границы Варшамова — Гилберта. Последняя была приведена в гл. 1 (теорема 12) и асимптотически имеет следующий вид.

Теорема 30. (Нижняя граница Варшамова — Гилберта.) Предположим, что Тогда существует бесконечная последовательность двоичных линейных -кодов с и скоростью удовлетворяющей неравенству для всех

Обозначения. Неравенство когда означает, что где при Кроме того, -двоичная энтропия (см. § 10.11).

Доказательство. Следует из теоремы 12 гл. 1 и следствия 9 гл. 10.

Имеется целый ряд кодов, в том числе альтернантные коды (теорема 3 гл. 12), коды Гоппы (упражнение (9) гл. 12), дважды циркулянтные или квазициклические коды (§ 16.7) и самодуальные коды (§ 19.6), которые достигают границы Варшамова — Гилберта (см. также задачу (нерешенную) (9.2)). Чтобы показать, что семейство кодов содержит коды, достигающие границы Варшамова — Гилберта, часто бывает достаточным следующее очень простое утверждение.

Теорема 31. Предположим, что существует бесконечное семейство двоичных кодов множество кодов таких, что: каждый ненулевой вектор длины , принадлежит одинаковому числу кодов в Тогда в этом семействе существуют коды, асимптотически достигающие границы Варшамова — Гилберта, или, более точно, такие, что

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

Число векторов веса меньше чем равно

и, следовательно, число кодов в семействе с минимальным расстоянием меньше чем равно самое большее

Если это число меньше чем т. е. если выполняется неравенство

то семейство содержит код с минимальным расстоянием по крайней мерс Утверждение теоремы следует теперь из следствия 9 гл. 10.

Упражнения. (30). Показать, что для любой заданной скорости существуют линейные коды, удовлетворяющие границе Варшамова — Гилберта. [Указание. В качестве надо выбрать множество всех линейных кодов длины и размерности

(31). (Кошелев [779], Козлов [781], Пирс [1044]; см. также Галлагер Пусть представляет собой двоичную матрицу размера все элементы которой выбраны случайно, и пусть обозначает код с порождающей матрицей Показать, что если фиксировано и то с вероятностью, стремящейся к единице, код удовлетворяет границе Варшамова — Гилберта.

Если то из границы Плоткина следует, что при и поэтому в дальнейшем мы будем считать, что

Приведем ряд верхних оценок, последовательно усиливающих друг друга (доказательства, конечно, усложняются). Первой является граница сферической упаковки (теорема 12), асимптотически принимающая следующий вид.

Теорема 32. (Граница сферической упаковки или верхняя граница Хэмминга.) Для любого -кода

Перейдем теперь к границе Элайеса, которая выводится с помощью следующего простого результата (функция была определена в § 17.1).

Доказательство. Пусть обозначает -код с максимально возможным числом кодовых слов,

Для любых векторов положим

Оценим двумя способами следующую сумму:

Теорема 34. (Верхняя граница Элайеса [1192].) Для любого -кода

Доказательство. В силу теоремы 2

Положим

Тогда и согласно теореме 33

Отсюда, учитывая лемму 7 из гл. 10, получаем оценку (17.60).

Мы переходим, наконец, к наилучшей из известных в настоящее время верхних оценок. Она состоит из двух частей; начнем с более простой.

Теорема 35. (Первая верхняя граница Мак-Элиса - Родемича — Рамсея — Велча Для любого -кода

Доказательство. Оно будет следовать из второй границы линейного программирования (следствие 21) с помощью соответствующего выбора многочлена Положим

где параметры будут сейчас выбраны.

По формуле Кристоффеля — Дарбу (см. упражнение (47) гл. 5)

и поэтому

Так как а многочлен от степени то он может быть представлен как

Выберем теперь

Чтобы воспользоваться следствием 21, надо показать, что:

В силу если и поэтому при условие (i) выполняется. Так как многочлены Кравчука образуют семейство ортогональных многочленов (см. теорему 16 гл. 5), то из теоремы 3.3.1 Сеге [1297] получаем, что:

(a) многочлен в интервале имеет различных действительных корней;

(b) если корни многочлена и если положить то многочлен имеет точно один корень в каждом интервале (см. рис. 17.5). Чтобы выполнялись условия (ii) и (iii), выберем число а в диапазоне Тогда для значений

Теперь согласно следствию 4 гл. 21 следует, что при

где коэффициенты сыт — целые неотрицательные числа. Из формул (17.63) — (17.65) следует, что коэффициенты а, неотрицательны, что доказывает условие (ii).

Рис. 17.5. Расположение корней многочленов Кравчука

В силу теоремы 20 гл. 5

что приводится (если воспользоваться (17.63)) к виду и доказывает условие (iii). Поэтому если выполняются условия и то следствие 21 применимо и приводит к следующей оценке:

где

Здесь нам необходим результат об асимптотическом поведении корня при и при фиксированном (приблизительно) отношении

Лемма 36. Если где то

Доказательство леммы. Предположим, что (17.67) не выполняется. Тогда существуют фиксированное и бесконечная последовательность чисел такие, что

Для каждого из этой последовательности положим Тогда

Положим так что и

Аналогично

Следовательно,

Далее из упражнения (46) гл. 5 имеем, что

или

Если мы положим то из соотношений (17.69) и (17.70) получаем, что

Согласно и поэтому

Так как действительное число, то должно выполняться неравенство

Но и поэтому

Но это неравенство не может выполняться для больших так как

что завершает доказательство леммы.

С помощью контуоного интегрирования можно показать, что при но для доказательства теоремы 35 нам хватит грубой нижней оценки. Предположим, что Так как , то из теоремы [1297] вытекает, что для значений Следовательно,

Теперь мы можем выбрать параметры для доказательства теоремы. Согласно рис. 17.5 существует значение а, скажем, в диапазоне для которого Положим Согласно лемме если мы выберем где X такое, что

другими словами, если

то при больших Используя эти значения, из неравенства (17.66) получаем, что

и поэтому

(если воспользоваться (17.72) и леммой 7 из гл. 10)

(в силу (17.73)).

Подобные же рассуждения могут быть применены к границе: линейного программирования для (см. с. 527). Сочетание получающейся при этом оценки с теоремой 33 дает следующий результат.

Теорема 37. (Вторая верхняя граница Родемича — Рамсея — Велча [947].) Для любого -кода имеет место неравенство

где

и

Доказательство этой теоремы мы опускаем.

Заметим, что поэтому

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

и теоремы 35 и 37 совпадают в этом диапазоне. Для значений теорема 37 несколько сильнее, что показывает таблица на рис. 17.6. Наилучшие верхняя и нижняя границы изображены на рис 17.7.

Задача (нерешенная). (17.9). Чему равна истинная верхняя граница величины как функции от при

(В настоящее время даже не известно, существует ли предел

когда фиксировано и заключено между 0 и 1/2).

Рис. 17.6 Границы для скорости наилучшего двоичного кода как функции от при больших значениях

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

Теорема 38. (Мак-Элис [944]) Для любого положительного такого, что справедливо неравенство

Доказательство. На этот раз в качестве выберем многочлен третьей степени, корни которого равны где

Рис. 17.7 Асимптотические границы для наилучших двоичных кодов 1 — нижняя граница Варшамова — Гилберта, 2 — верхняя граница Мак Элиса-Родемича-Рямсея-Врлча

Тогда

где

Положим Так как все положительны и для то следствие 21 применимо, и поэтому

Для случая оценка (17.75) утверждает, что что слабее теоремы Но для значений эта оценка является наилучшим известным асимптотическим результатом

ЗАМЕЧАНИЯ К ГЛ. 17

(см. скан)