Virtual Laboratory Wiki
Регистрация
Advertisement

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

В трехмерном пространстве[]

Задача о плотной упаковке шаров[]

Задача о плотной упаковке шаров, такая простая на вид и столь трудная по существу, остаётся одной из важных нерешённых проблем в математике.

Она заключается в том, чтобы выяснить, насколько плотно можно уложить в пространстве большое количество одинаковых шаров. Если бы вместо шариков нужно было уложить одинаковые кубики, найти ответ было бы легко. Поскольку кубики плотно прилегают друг к другу и между ними не остаётся пустого места (не считая небольших просветов вдоль стен и потолка). Однако шары нельзя упаковать так же плотно, как кубики: между ними всегда остаётся свободное место.

Многие люди, потратив несколько минут на эксперименты с апельсинами или бильярдными шарами, приходят к ошибочному выводу, что проблема тривиальна. Уложим три шара на плоской поверхности так, чтобы их центры образовали равносторонний треугольник, а сами они касались друг друга. Затем будем подкладывать к ним другие шары так, чтобы каждый новый касался двух уже уложенных. Так получится первый слой шаров. Затем уложим второй слой, помещая каждый новый шар в «глубокую яму», или углубление, образовавшееся в центре каждой треугольной группы шаров первого слоя. В законченном виде второй слой не отличается от первого, он только сдвинут в горизонтальной плоскости. Если и следующие слои строить таким же способом, то получится так называемая гранецентрированная кубическая упаковка шаров, хорошо знакомая химикам и кристаллографам. При этом шары заполняют чуть больше 74% объёма пространства и каждому ясно, что уложить шары плотнее невозможно.

К сожалению, математически не доказано, что это максимально достижимая плотность. Из полученных до сих пор верхних оценок плотности наименьшая была найдена в 1958 году К. А. Роджерсом из Бирмингемского университета; он доказал, что никакая упаковка шаров не может иметь плотность большую чем ~0,7796.

Sphere1a

А

Sphere1b

Б

Sphere1c

В

Sphere1d

Г

Sphere1e

Д

Sphere1f

Е

Sphere1g

D1

Sphere1h

D2

Sphere1i

D3

Sphere1j

D4

Sphere1k

D5

Sphere1l

D6

Sphere0

Рис. 1. Гранецентрированная кубическая упаковка шаров. Каждый шар в этой упаковке касается 12 других; доказательство того, что это максимальное число касаний, было получено лишь в 1874 году. Если центр одного из шаров фиксирован, то множество всевозможных вращений и отражений, меняющих местами 12 окружающих шаров, образует группу, которая называется группой симметрии этой упаковки. Группа симметрии гранецентрированной кубической упаковки состоит из 48 элементов. Их легче всего сосчитать, если рассматривать центры шаров как вершины изображённого справа многогранника, который называется кубооктаэдром. Каждая из шести квадратных граней кубооктаэдра может стать передней гранью после подходящего вращения фигуры вокруг зелёной или синей оси (A–E). Каждое множество четырёх сфер, образующих квадратную грань (скажем, четвёртую), при вращении всей фигуры вокруг красной оси может оказаться в одной из четырёх конфигураций (D1–D4). Наконец, каждую конфигурацию (например, третью) можно отразить в вертикальной плоскости и получить новую конфигурацию (D3a, D3b). Следовательно, общее число элементов группы симметрии равно 6×4×2, т.е. 48.


Конфигурации плотной упаковки шаров изучаются уже многие годы. Отчасти это объясняется тем, что они тесно связаны с изучением свойств твёрдых тел и жидкостей. Так, например, физические свойства многих кристаллических материалов можно описывать, по крайней мере в первом приближении, исходя из модели кристалла как системы огромного числа твёрдых шаров (изображающих атомы) в плотной упаковке. Не менее важное применение эта модель находит при исследовании порошков и пористых материалов.

Если экспериментальное изучение упаковок шаров важно для понимания свойств некоторых физических систем, то имеются достаточно веские причины и для чисто математического изучения идеально плотных упаковок. Тот факт, что до сих пор в отношении ни одной известной упаковки не доказано, что она самая плотная, говорит о том, что математическое исследование обычного трёхмерного евклидова пространства ещё далеко от завершения. Кроме того, математики обобщили понятие шара и задачу об упаковке шаров на многомерные пространства и рассматривают объекты, называемые n-мерными шарами, алгебраическое описание которых напоминает алгебраическое описание обычных шаров. Оказалось, что поиск плотной упаковки шаров в n-мерном пространстве математически эквивалентен разработке конечного множества закодированных цифрами сообщений, которые допускают их передачу без искажений при минимальных затратах энергии. Более того, найденные в последние годы плотные упаковки в пространствах 24 и более измерений привели к крупным открытиям в самой математике — в той её области, которая называется теорией групп.


Sphere2a

РАЗМЕРНОСТЬ 1;

Sphere2b

РАЗМЕРНОСТЬ 2;

Sphere2c

РАЗМЕРНОСТЬ 2;


Рис. 2. Упаковки «шаров» можно рассматривать не только в трёхмерном, но также и в одномерном или двумерном пространствах. В пространстве размерности 1 шарами являются прямолинейные отрезки единичной длины с центрами в целых точках. Они покрывают 100% прямой, и каждый из них касается двух других. Очевидно, что это наиплотнейшая возможная упаковка; она называется Z1. На плоскости шарами являются круги; известны три представляющие интерес упаковки. В упаковке Z2 центры кругов расположены во всех точках с целыми координатами; в упаковке D2 центры расположены в тех же точках через одну в шахматном порядке. Если изменить масштаб на координатных осях и повернуть их на 45°, то упаковка Z2 перейдёт в D2, следовательно, эти упаковки эквивалентны. Чтобы найти их плотность, нужно вычислить, какую долю площади квадрата покрывают круги или их части (т.е. сосчитать площадь закрашенной части квадрата); она равна π/4, или примерно 0,7854 (слева). Плотнейшей упаковкой кругов на плоскости является гексагональная решётчатая упаковка L2. Круговые секторы в этой упаковке покрывают π√3/6 каждого равностороннего треугольника; следовательно, плотность этой упаковки равна приблизительно 0,9069 (справа).

Задача о числе касаний шаров[]

Эта задача заключается в следующем: сколько одинаковых шаров можно расположить вокруг одного такого же центрального шара, чтобы все они касались его? В 1694 году эта задача (в случае трёхмерного пространства) стала предметом получившего широкую известность диспута между Исааком Ньютоном и шотландским астрономом Джеймсом Грегори. Ньютон утверждал, что число касаний равно 12, и для описанной выше гранецентрированной кубической упаковки это действительно так (см. рис. 1). Грегори, по-видимому, не соглашался, настаивая на том, что можно «втиснуть» ещё один дополнительный шар, хотя он и не мог это доказать.

Грегори, скорее всего, вообразил, что 12 окружающих шаров можно так передвинуть по центральному шару, чтобы все просветы между ними скопились в одном месте и туда вошёл бы ещё один шар. И действительно, как легко показать, телесный угол, под которым один из окружающих шаров виден из центра центрального шара, составляет меньше 1/13 полного телесного угла, и, таким образом, если судить только по объёму, вокруг центрального шара в самом деле могли бы уместиться 13 шаров. Однако часть полного телесного угла с неизбежностью приходится на просветы между окружающими шарами. Вопрос о числе касаний был разрешён лишь в 1874 году. Как показал Р. Хоппе, прав был Ньютон.

Задача о редчайшем покрытии шаров[]

Вторая важная задача, связанная с упаковкой шаров, — это так называемая задача о редчайшем покрытии: как наиболее экономно расположить одинаковые шары в пространстве, чтобы каждая точка пространства оказалась внутри или на границе хотя бы одного из них? В отличие от задачи о плотнейшей упаковке, в которой речь шла о неперекрывающихся шарах, в этой задаче шары обязательно перекрываются. Возможен такой способ покрытия пространства шарами: рассмотрим какую-нибудь упаковку шаров и затем «раздуем» каждый шар так, чтобы заполнились все пустоты исходной упаковки. Однако оказалось, что в общем случае «раздутие» шаров самой плотной упаковки не приводит к оптимальному решению задачи о покрытии. Так, например, в трёхмерном пространстве наилучшим принято считать покрытие шарами с центрами в узлах так называемой объёмноцентрированной кубической решётки. Но если расположить в этих же узлах центры одинаковых неперекрывающихся шаров, то получится упаковка, которая уже не будет столь плотной, как другие известные упаковки шаров, например рассмотренная выше гранецентрированная кубическая. Правда, и сама гипотеза о том, что объёмноцентрированная кубическая решётка даёт решение задачи о покрытии, тоже не доказана.

Аналитическое представление шаров в прямоугольной системе координат[]

Для того чтобы продвинуться в решении трёх указанных задач, математики подкрепляют свою геометрическую интуицию аналитическим представлением шаров в прямоугольной системе координат. Хорошо известно, что любую точку на плоскости можно задать двумя координатами: x — по горизонтальной оси и y — по вертикальной. Обычно точка плоскости записывается в виде упорядоченной пары (x, y). Так, например, (3, 4) — это точка на плоскости, находящаяся на три единицы правее начала координат вдоль оси x и на четыре единицы выше вдоль оси y.

Расстояние между этой точкой (3, 4) и любой другой точкой (x, y) можно сосчитать по теореме Пифагора: квадрат искомого расстояния равен сумме квадратов расстояний вдоль оси x и вдоль оси y, т.е. (x–3)2 + (y–4)2. Так как окружность, по определению, есть множество всех точек на плоскости, равноудалённых от некоторого центра, скажем (a, b), то любая точка (x, y) окружности должна удовлетворять уравнению (x–a)2 + (y–b)2 = R2, где R — радиус этой окружности. Если радиус равен 1, а центр находится в начале координат — точке (0, 0), то уравнение упрощается и принимает вид x2 + y2 = 1.


Sphere3a

СЛОЁНАЯ РЕШЁТЧАТАЯ УПАКОВКА L3

Sphere3b

ГЕКСАГОНАЛЬНАЯ ПЛОТНАЯ УПАКОВКА (НЕРЕШЁТЧАТАЯ)

Рис. 3. Построение слоёной решётчатой упаковки L3, которая эквивалентна гранецентрированной кубической упаковке D3, осуществляется наложением друг на друга слоёв, в которых центры шаров расположены в соответствии с гексагональной решётчатой упаковкой L2. Если уложить слои таким образом, что шары третьего слоя окажутся в точности над шарами первого, то получится упаковка, которая называется гексагональной плотной упаковкой. Эта упаковка столь же плотная, что и L3, однако центры шаров в этой упаковке не образуют решётку.


Подобным же образом любая точка трёхмерного пространства задаётся тремя координатами x, y и z; в более симметричном виде её можно представить так: (x1, x2, x3). Поверхность шара (сфера) радиуса 1 с центром в начале координат состоит из точек вида (x1, x2, x3), удовлетворяющих уравнению x12 + x22 + x32 = 1, которое, как и в двумерном случае, можно получить из геометрического определения сферы, применяя теорему Пифагора (на этот раз дважды).

Более трех измерений[]

В пространстве более трёх измерений геометрическая интуиция уже не помогает, и приходится полностью перейти на язык координат. Например, «точкой» четырёхмерного пространства является математический объект, для однозначного задания которого требуются четыре числа; такая точка записывается в виде (x1, x2, x3, x4).Если у нас есть некий список лиц с указанием сведений о них и если по росту, весу, возрасту и годовому доходу можно однозначно найти по списку соответствующую фамилию, то эти четыре величины задают точку в четырёхмерном пространстве.

Четырёхмерный шар определяется по аналогии с предыдущими случаями. Все точки (x1, x2, x3, x4) на его поверхности (сфере) находятся на одном и том же расстоянии R от некоторой точки (a1, a2, a3, a4) — центра шара. Сумма квадратов расстояний по всем независимым координатным осям между любой точкой сферы (x1, x2, x3, x4) и центром (a1, a2, a3, a4) должна равняться .

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

Sphere4

Рис. 4. Точка в двумерном пространстве задаётся двумя координатами, скажем x и y. Окружность радиуса 1 с центром в начале координат — точке (0, 0) — это множество всех точек (x, y), удовлетворяющих уравнению (слева). В трёхмерном пространстве для задания точки требуются три координаты, скажем x1, x2 и x3. Поверхность шара радиуса 1 с центром в точке (0, 0, 0) — это множество всех точек (x1, x2, x3), удовлетворяющих уравнению . В n-мерном пространстве точка задаётся n координатами x1, x2, ..., xn, а поверхность n-мерного шара радиуса 1 с центром в точке (0, 0, ..., 0) есть множество точек (x1, x2, ..., xn), удовлетворяющих уравнению .


Определение понятия сферы при помощи соотношения между координатами позволяет по-новому посмотреть на некоторые задачи, внешне никак не связанные с упаковкой шаров, и свести их к одной из трёх задач, описанных выше.

Надежность в цифровой связи[]

Одна из главных задач при осуществлении цифровой связи заключается в построении набора закодированных символов, или кодовых слов, который можно передать с максимальной надёжностью при минимальных затратах энергии. Допустим, что каждое кодовое слово представлено в виде восьмиразрядного символа, в каждом разряде которого стоит одно из пяти различных значений: 0, ½, 1, –½, –1. На первый взгляд кажется, что такая система обеспечит передачу различных кодовых слов. Однако некоторые пары этих слов настолько мало различаются, что при передаче такая система будет слишком подвержена случайным ошибкам или электрическим помехам. Например, кодовые слова (1, 1, 1, 1, 1, 1, 1, 1) и (1, 1, 1, 1, 1, 1, 1, ½) так мало отличаются друг от друга, что если использовать их оба, то часто одно будет принято за другое. Иначе можно сказать, что если два кодовых слова столь же мало различаются, как (1, 1, 1, 1, 1, 1, 1, 1) и (1, 1, 1, 1, 1, 1, 1, ½), то потребуются очень большие затраты энергии, чтобы гарантировать различимость этих слов при наличии фонового шума.

Различимость кодовых слов и количество энергии, необходимое для их надёжной передачи, связаны общим математическим соотношением. Оно было впервые сформулировано в 1948 году Клодом Шенноном, работавшим тогда в фирме Bell Telephone Laboratories, в его статье «Математическая теория связи».

Шеннон показал, что при любом фиксированном количестве энергии всегда существует такая система кодовых слов, которая может быть передана практически без ошибок. При этом появляется лишь ограничение на скорость передачи кодовых слов: она не должна превышать некоторого критического порога, называемого пропускной способностью канала передачи. К сожалению, теорема Шеннона неконструктивна: в ней утверждается только существование таких систем кодирования, но нет и намёка на то, как их построить. И хотя с тех пор разработано много различных систем сигналов, ни одна из них не действует так прекрасно, как обещает теорема Шеннона.

Один из способов приблизиться к соотношению, указанному теоремой Шеннона, состоит в том, чтобы представить каждый сигнал как некоторую точку n-мерного пространства. Рассмотрим, например, произвольную последовательность из восьми чисел, принадлежащую системе сигналов. Физически каждому из этих чисел соответствует некоторый уровень напряжения в линии передачи, поэтому каждое кодовое слово можно графически представить на плоскости в виде набора из восьми отдельных импульсов заданной высоты на восьми интервалах временной оси. Ту же информацию можно выразить математически при помощи одной точки восьмимерного пространства: возьмём первое число каждой последовательности в качестве первой координаты такой точки, второе — в качестве второй координаты и т.д. Поскольку задание восьми координат определяет точку восьмимерного пространства, каждое кодовое слово нашей системы будет представлено определённой точкой восьмимерного пространства.


Sphere5a
Sphere5b
Sphere5c
Sphere5d
Sphere5e


Рис. 5. Разработка кода для эффективной передачи информации тесно связана с задачей об упаковке шаров. Такой код представляет собой конечное множество сигналов, называемых кодовыми словами, которые должны быть легко различимы при минимальных затратах электроэнергии. Если каждое кодовое слово есть последовательность трёх дискретных уровней напряжения, то эту последовательность можно представить точкой трёхмерного пространства: первая координата этой точки равна численному значению первого уровня напряжения, вторая — значению второго уровня и т.д. (А–Г). Энергия, требуемая для передачи каждого импульса, пропорциональна квадрату напряжения, поэтому полная энергия, необходимая для передачи одного кодового слова, равна сумме квадратов трёх дискретных напряжений, составляющих это кодовое слово. Эта сумма равна квадрату расстояния от начала координат до точки трёхмерного пространства, которая представляет это кодовое слово. Таким образом, проблема минимизации затрат энергии эквивалентна задаче размещения всех точек, представляющих кодовые слова, как можно ближе к началу координат. С другой стороны, необходимость отчётливой различимости кодовых слов можно рассматривать как требование, чтобы соответствующие им точки в пространстве не подходили друг к другу ближе, чем на некоторое минимальное расстояние d. Сочетание двух этих требований геометрически эквивалентно поиску наиболее плотной упаковки неперекрывающихся твёрдых шаров радиуса d/2 вокруг начала координат (Д).


Превратив кодовые слова в точки, можно поискать геометрическую интерпретацию двух важных условий, которым должна удовлетворять система кодовых слов. Во-первых, вспомним, что кодовые слова должны быть надёжно различимы. На геометрическом языке это означает, что соответствующие точки восьмимерного пространства должны быть разделены некоторым минимальным «расстоянием». Можно ли считать пифагорово расстояние между двумя точками восьмимерного пространства мерой различимости соответствующих кодовых слов? При определении пифагорова расстояния разности между координатами двух рассматриваемых точек возводятся в квадрат. Следовательно, малые разности (скажем, меньшие 1) при этом уменьшаются, а большие (бóльшие 1) увеличиваются. Поскольку при малой разнице в величине напряжения для двух сигналов опасность перепутать соответствующие кодовые слова гораздо более вероятна, чем при большой, пифагорово расстояние можно считать разумной мерой различимости.

Sphere6

Рис. 6. Квантование данных, полученных от непрерывно изменяющегося источника, тесно связано с задачей о редчайшем покрытии пространства перекрывающимися шарами. Например, чтобы выполнять квантование в двумерном пространстве, входные данные объединяют в пары и каждую пару рассматривают как координаты точки на плоскости. Затем каждую точку, скажем А, отвечающую паре данных, округляют до ближайшей отмеченной точки (Б), лежащей в той же заранее выбранной области плоскости, что и А. Проблема состоит в том, чтобы выбрать разбиение плоскости и отмеченные точки таким способом, при котором была бы минимальной средняя ошибка квантования. Если данные распределены равномерно, а отмеченные точки лежат в центрах квадратов, то средняя ошибка равна 1/12. При помощи редчайшего покрытия плоскости кругами можно получить лучший способ квантования. Такое покрытие порождается гексагональной упаковкой (чёрные круги), если радиусы кругов немного увеличить — ровно настолько, чтобы каждая точка плоскости оказалась внутри или на границе хотя бы одного круга (цветные круги). Радиус R кругов покрытия равен расстоянию от центра до самой «глубокой ямы» в соответствующей упаковке. Если соединить эти «глубокие ямы» подходящими прямыми, то плоскость разобьётся на правильные шестиугольники; выбор отмеченных точек в центрах правильных шестиугольников при квантовании равномерно распределённых данных даёт среднюю ошибку 5√3/108, т.е. около 0,0802, что немного меньше, чем 1/12.


Рассмотрим, например, два кодовых слова: (1, 1, 1, 1, 1, 1, 1, 1) и (½, ½, ½, ½, ½, ½, ½, ½). Квадрат расстояния между соответствующими точками равен сумме восьми квадратов вида , и, значит, само расстояние равно √2. Кодовые слова (1, 1, 1, 1, 1, 1, 1, 1) и (0, 0, 1, 1, 1, 1, 1, 1), хотя у них все координаты, кроме двух первых, совпадают, тоже удалены друг от друга на расстояние √2, и потому их так же легко различить, как и предыдущие слова.

Вторая важная характеристика хорошей системы кодовых слов состоит в том, что энергия, затрачиваемая на их передачу, должна быть минимальной. Из элементарных определений энергии и напряжения следует, что энергия прямо пропорциональна квадрату напряжения: для простой электрической цепи энергия равна квадрату напряжения, делённому на сопротивление этой цепи. Следовательно, суммарная энергия, необходимая для передачи восьмиразрядного кодового слова, равна сумме квадратов восьми составляющих его чисел. А эта сумма есть не что иное, как квадрат расстояния от точки, представляющей это кодовое слово в восьмимерном пространстве, до начала координат (0, 0, 0, 0, 0, 0, 0, 0).

Таким образом, задача разработки надёжной системы сигналов, обеспечивающей к тому же эффективное использование энергии, сводится к геометрической задаче размещения точек внутри некоторой области пространства при дополнительном условии, что они не должны находиться слишком близко друг к другу. Если требуется, чтобы расстояние между этими точками было, скажем, не меньше √2, то задача эквивалентна построению плотнейшей упаковки шаров, радиус которых равен половине этого расстояния, т.е. √2/2. Другая задача, тесно связанная с предыдущей, заключается в том, чтобы найти множество кодовых слов, требующих одинаковой энергии. Она эквивалентна задаче размещения на поверхности n-мерного шара максимального количества точек, подчинённых дополнительному условию — не подходить слишком близко друг к другу. А это в свою очередь есть не что иное, как обобщённый вариант задачи о числе касаний.

Упаковка E8[]

Оказывается, в восьмимерном пространстве существует особенно плотная упаковка шаров, называемая E8. Она была открыта в последней трети XIX века русскими математиками А. Н. Коркиным и Е. И. Золотарёвым, а также английским юристом и математиком-любителем Торолдом Госсетом. Центры шаров в упаковке E8 лежат в точках, все координаты которых — только целые числа или только целые числа, сложенные с ½. При этом сумма координат каждой точки должна быть чётным числом. Имеется 240 таких точек на расстоянии √2 от начала координат: 112 точек вида (±1, ±1, 0, 0, 0, 0, 0, 0), где две единицы с произвольной комбинацией знаков могут стоять на любом месте, и 128 точек вида (±½, ±½, ±½, ±½, ±½, ±½, ±½, ±½) с чётным числом минусов.

Упаковка E8 могла бы стать основой практичной и эффективной схемы сигналов. Если бы схема включала в себя ровно 240 кодовых слов, то в качестве представляющих эти слова точек можно было бы выбрать 240 равноудалённых от начала координат точек упаковки E8. Однако для большинства применяемых на практике систем требуется число кодовых слов, равное некоторой целой степени двойки. Так, например, в телефонной связи на средние расстояния сейчас широко применяется система цифровой передачи, называемая импульсно-кодовой модуляцией. Напряжение, отвечающее речевому сигналу, измеряется через каждые 1/8000 с, и эти выборочные измеренные значения затем квантуются, т.е. заменяются одним из = 256 дискретных значений. Затем каждое такое значение выражается в виде восьмиразрядного двоичного числа, и эти двоичные числа образуют так называемый код источника.

Реконструкция речевого сигнала[]

То, что речевой сигнал можно реконструировать по одним только выборочным значениям, известно со времени появления в 20-х годах нашего века работ Гарри Найквиста, сотрудника фирмы Bell Laboratories. Речевой сигнал можно рассматривать как некую величину, которая, подобно давлению воздуха или напряжению, меняется непрерывно в зависимости от времени. В самом начале XIX века Жан Батист Жозеф Фурье доказал, что график любой такой величины можно с любой требуемой точностью аппроксимировать при помощи наложения синусоид и косинусоид подходящих амплитуды и частоты. Эти синусоиды и косинусоиды (в случае произвольной кривой их может оказаться бесконечное множество) называются компонентами Фурье рассматриваемой кривой.

Допустим, что график некоторой величины получается наложением конечного числа компонент Фурье, частоты которых не превышают W Гц. Результат Найквиста состоял в том, что этот график можно восстановить по значениям, которые он принимает через каждые ½W с. Так, например, речевой сигнал, не имеющий компонент с частотой выше 4000 Гц, может быть полностью восстановлен по выборочным значениям, измеренным через каждые 1/8000 с. Таким образом, вместо полного речевого сигнала можно передавать только выборочные значения, которые представлены кодовыми словами в коде источника. Если бы эти выборочные значения передавались без округления, то теорема Найквиста показывала бы, что длящийся целую секунду речевой сигнал, которому соответствуют 8000 выборочных значений, может быть представлен всего одной точкой 8000-мерного пространства. Вот какая мощная штука математика!

Для осуществления эффективной передачи чисел в коде источника, представляющих выборочные значения, их нужно преобразовать ещё раз при помощи кода канала; именно эта стадия процесса имеет отношение к задаче упаковки шаров. Прекрасный способ получить код канала при помощи упаковки E8 состоит в следующем. Каждая пара последовательных восьмиразрядных двоичных чисел в коде источника объединяется в одно 16-разрядное число, которое приписывается центру одного из = 65 536 шаров упаковки E8, ближайших к началу координат. На приёмном конце телефонной линии кодовые слова, отвечающие координатам каждого такого центра, преобразуются в двоичные числа кода источника, и по ним реконструируется исходный речевой сигнал.

Устройством для квантования (аналого-цифровой преобразователь)[]

Кратко рассмотрим ещё одно важное применение упаковок шаров в проблемах цифровой связи. Вспомним, что, прежде чем получить из речевого сигнала в телефоне двоичные числа кода источника, нужно свести точную величину интенсивности сигнала к одному из 256 дискретных уровней. Реальный мир полон несуразных чисел вроде 0,7913..., но мир компьютеров и цифровых систем в конечном счёте имеет дело только с «круглыми» числами наподобие 0 и 1. Устройство, которое приводит непрерывную переменную величину к некоторому множеству дискретных значений, называется аналого-цифровым преобразователем или устройством для квантования.

Квантование можно выполнять не только вдоль одной координатной оси, а сразу в двух и более измерениях. Допустим, что плоскость разбита на некоторые области, конгруэнтные или нет, и в каждой области отмечена одна точка. Любой такой массив точек и областей может функционировать как двумерный преобразователь: вместо пары вещественных чисел на входе, задающей некоторую произвольную точку плоскости, он выдаёт на выходе координаты отмеченной точки, лежащей в той же области, что и эта произвольная точка. Таким способом каждая точка плоскости «округляется» до одной из отмеченных точек. Этот процесс сжимает входные данные: вместо точных значений координат заданной точки можно передавать один только индекс соответствующей отмеченной точки.

Однако квантование вносит ошибки, поэтому обычно стараются так выбрать отмеченные точки, чтобы свести среднюю ошибку к минимуму. Если, например, входные данные распределены равномерно, т.е. все входные значения равновероятны, то нетрудно вычислить среднюю ошибку для разных схем квантования. Допустим, что одна координатная ось разбивается на равные отрезки единичной длины и в качестве отмеченных точек берутся середины этих отрезков; тогда средняя ошибка равна 1/12, или около 0,0833. Те же данные можно проквантовать в двух измерениях: поступающие значения объединяются в пары и каждая пара рассматривается как точка на плоскости. Если затем разбить плоскость на квадраты и выбрать отмеченную точку в центре каждого квадрата, то средняя ошибка будет по-прежнему равна 1/12. С другой стороны, если разбить плоскость на правильные шестиугольники той же площади, что и квадраты, и выбрать в качестве отмеченных точек центры этих шестиугольников, то средняя ошибка квантования немного уменьшится и станет равной 5√3/108, т.е. примерно 0,0802.

Рис. 7. «Слоёные» решётчатые упаковки шаров в n-мерном пространстве строятся путём прикладывания друг к другу слоёв, образованных при помощи подходящей слоёной решётчатой упаковки в пространстве предыдущей размерности n–1. Так, двумерную гексагональную упаковку L2 можно построить, прикладывая друг к другу ряды кругов с центрами в точках решётки Z1. Подобным же образом слои из шаров, уложенные в соответствии с гексагональной решёткой, кладутся друг на друга и образуют решётчатую упаковку L3, плотнейшую известную упаковку в трёхмерном пространстве. Джон X. Конвей из Кембриджского университета и автор продолжили это построение и нашли все слоёные решётки в размерностях вплоть до 25. Оказалось, что в размерностях 1–10 и 14–24 слоёные решётки единственны, в размерности 11 их две, в размерностях 12 и 13 по три. В размерности 25 их уже 23, а в размерности 26 — по крайней мере 75 000.


Замечательно, что такого улучшения всегда можно добиться, даже если исходные данные не являются равномерно распределёнными. В 1963 году П. Л. Задор из Станфордского университета в своей докторской диссертации показал, что среднюю ошибку всегда можно уменьшить, выполняя квантование в пространстве более высокой размерности. Таким образом, вместо того чтобы квантовать данные по мере их поступления вдоль одной оси, лучше подождать, пока соберётся несколько значений, и затем квантовать их все вместе как одну точку в n-мерном пространстве. При квантовании не стоит торопиться!

К сожалению, результат Задора, как и теорема Шеннона, неконструктивен. Проблема нахождения хороших многомерных схем квантования даже для равномерно распределённых данных всё ещё остаётся нерешённой. Однако известно несколько упаковок шаров, на основе которых, как оказалось, можно построить отличные схемы квантования. Рассмотрим упаковку шаров в двумерном пространстве, т.е. упаковку кругов на плоскости. С 1940 года известно, что плотнейшей упаковкой кругов является такая, при которой каждый круг опоясан шестью другими (см. рис. 6).

Допустим теперь, что каждый из этих кругов ограничен тонкой эластичной плёнкой и внутренность круга начинает раздуваться. По мере увеличения кругов плёнки смыкаются друг с другом и свободное пространство на плоскости заполняется. Если «раздувание» происходит равномерно на всей плоскости, то круги превращаются в правильные шестиугольники. Как уже говорилось, схема квантования равномерно распределённых данных, основанная на шестиугольниках, приводит к минимальной средней ошибке. Подобное же «раздувание» восьмимерных шаров упаковки E8 также даёт малую ошибку квантования, даже ещё меньшую, чем в двумерном случае. Общая проблема квантования, в которой требуется, чтобы пространство было разбито на конечные области, или иначе говоря, покрыто такими областями, тесно связана с задачей нахождения редчайшего покрытия пространства шарами.

Поиск плотнейших упаковок шаров в многомерных пространствах сильно упрощается, если сосредоточить внимание лишь на самых регулярных конфигурациях — так называемых решётчатых упаковках. Вернёмся к шестиугольной, или гексагональной, упаковке кругов, о которой только что говорилось. Центры любых двух соседних опоясывающих кругов вместе с центром среднего круга образуют равносторонний треугольник. Чтобы вычислить плотность такой упаковки, достаточно подсчитать, какая доля каждого треугольника покрыта кругами или их частями. Поскольку эти треугольники заполняют плоскость, а конфигурация кругов внутри каждого треугольника всегда одна и та же, то плотность кругов в одном треугольнике равна плотности всей упаковки в целом. Пользуясь формулами элементарной геометрии, можно убедиться, что эта плотность равна π√3/6, или приближённо 0,9069.

Провести это вычисление было бы невозможно, если бы не существовало бесконечно повторяющейся ячейки, заполняющей всю плоскость. Тем не менее легко представить себе и такие совсем нерегулярные упаковки, для которых подобной ячейки не существует. Такие упаковки гораздо труднее поддаются изучению: мало того, что трудно или вообще невозможно вычислить их плотность, иногда не удаётся даже описать координаты центров. От этих неприятностей нас гарантирует определение решётчатой упаковки. Упаковка шаров называется решётчатой, если для любых двух шаров с центрами в точках (u1, u2, ..., un) и (v1, v2, ..., vn) этой упаковке принадлежат и все шары с центрами в точках вида (au1 + bv1, au2 + bv2, ..., aun + bvn), где a и b — произвольные целые числа. Про координаты центров таких шаров говорят, что они порождаются координатами центров двух первых шаров.

Простейшей решётчатой упаковкой является кубическая; в этой упаковке центры шаров находятся в точках с целочисленными координатами. Кубическая решётка (или упаковка) в пространстве произвольной размерности n обозначается Zn. Одномерная «кубическая» упаковка Z1 состоит из отрезков единичной длины с центрами в целых точках на прямой. Эти «шары» покрывают 100% прямой, и каждый из них касается двух других. Следовательно, упаковка Z1 решает в одномерном пространстве обе задачи: о плотнейшей упаковке и о числе касаний.

Однако в двумерном случае квадратная упаковка Z 2 не является плотнейшей. Её плотность равна π/4, или примерно 0,7854, т.е. намного меньше, чем для гексагональной упаковки кругов (см. рис. 2). Упаковка, соответствующая кубической решётке Z3, также имеет низкую плотность, и равна π/6, т.е. около 0,5236. Значительно более плотное семейство решётчатых упаковок можно получить при помощи кубических решёток, если располагать центры шаров поочередно в шахматном порядке. Чтобы построить новое семейство решёток, покрасим узлы кубической решётки попеременно в красный и чёрный цвета и расположим центры шаров в чёрных точках. Это эквивалентно тому, что центрами шаров новой упаковки будут точки, координаты которых — целые числа с чётной суммой. В пространстве произвольной размерности n такая упаковка обозначается Dn. Так, например, в упаковке D3 начало координат (0, 0, 0) и точка (1, 1, 0) — «законные» центры шаров, а точка (1, 0, 0) — нет, потому что 1+0+0 — нечётное число.

Последовательность решётчатых упаковок D3, D4, D5 имеет важное значение для решения проблемы упаковки шаров.

Решётка D3 — это гранецентрированная кубическая решётка. Построив модель из шариков для пинг-понга, можно убедиться в том, что повторяющейся элементарной ячейкой этой решётки служит куб со стороной 2 с шаром в центре; радиус каждого шара равен √2/2. Плотность этой упаковки можно вычислить, подсчитав, какую долю объёма куба заполняют шары; она равна π √2/6, или примерно 0,7405. Хотя не исключено, что в трёхмерном пространстве существуют и более плотные упаковки шаров, среди решётчатых упаковок D3 является плотнейшей: это доказал Карл Фридрих Гаусс в 1831 году. Известно, что в четырёх и пяти измерениях D4 и D5 также являются плотнейшими решётчатыми упаковками.

Однако в размерностях выше пяти упаковки Dn уже не обладают этим свойством, а в случае D8 пробелы между шарами так велики, что в эти пробелы можно втиснуть ещё один экземпляр такой же упаковки, так что шары останутся неперекрывающимися. В результате получится упаковка E8. В 1934 году Г. Ф. Блихфельдт из Станфордского университета доказал, что E8 — плотнейшая решётчатая упаковка в восьмимерном пространстве и, более того, что некоторые сечения упаковки E8, названные E6 и E7, являются плотнейшими решётчатыми упаковками в шести и семи измерениях. Никаких более плотных упаковок (заведомо нерешётчатых) в пространствах этих размерностей не обнаружено.

В 1965 году Джон Лич, работавший тогда в Университете г. Глазго, построил замечательную решётчатую упаковку шаров в 24-мерном пространстве. Его построение кратко описано под рис. 8. Изучение решётки Лича привело к более глубокому пониманию свойств других многомерных решёток и к получению важных результатов в теории групп. Эта решётка почти наверняка даёт плотнейшую упаковку в 24-мерном пространстве. К. А. Роджерс, рассуждая по аналогии с трёхмерным пространством, нашёл верхнюю оценку максимальной плотности упаковки в пространстве произвольной размерности n. В случае n=24 его оценка лишь чуть-чуть больше плотности упаковки Лича. Каждый шар в этой упаковке касается 196 560 других шаров, и в 1979 году А. М. Одлижко из фирмы Bell Laboratories и я доказали, что это число решает задачу о числе касаний в 24-мерном пространстве. Тем же методом решается эта задача в восьмимерном случае: здесь ответ равен 240 и совпадает с числом шаров, касающихся одного шара в упаковке E8. Оба этих результата были независимо получены В. И. Левенштейном из Института прикладной математики им. М. В. Келдыша в Москве. Заметим, что эта задача остается нерешённой во всех других размерностях, кроме 1, 2 и 3 (где ответ равен соответственно 2, 6 и 12).


Рис. 8. Построение решётки Лича, самой плотной известной упаковки шаров в 24-мерном пространстве, основано на показанных выше 24-разрядных двоичных последовательностях. Множество всевозможных сумм по модулю 2 этих 12 последовательностей состоит из 212, или 4096, двоичных последовательностей, называемых кодовыми словами (при сложении по модулю 2 сумма 1+1 равна 0; цифры, которые при обычном сложении держат в уме и переносят в следующий разряд, в двоичной арифметике игнорируются). Эти 212 кодовых слов образуют эффективный код для передачи информации, разработанный в 1949 году Марселем Дж. Э. Голеем из US Army Signal Corps. Engineering Laboratories. Центры всех шаров в упаковке Лича находятся в точках вида 2C + 4X или I + 2C + 4Y, где C — кодовое слово кода Голея, I — точка (1, 1, ..., 1) в 24-мерном пространстве, а X и Y пробегают все точки 24-мерного пространства с целочисленными координатами. Сумма координат каждой точки X должна быть чётной, а точки Y — нечётной. Радиус каждого шара равен 2√2. Центры шаров, ближайших к началу координат, находятся в точках вида (±4, ±4, 0, 0, ..., 0), (±2, ±2, ±2, ±2, ±2, ±2, ±2, ±2, 0, 0, ..., 0) и (±3, ±1, ±1, ..., ±1). Каждый шар касается 196 560 других шаров.


Рис. 9. Самые плотные известные упаковки шаров в пространствах вплоть до размерности 48 изображены на этом графике, построенном по методу, предложенному Джоном Личем; показана зависимость «нормализованной» плотности упаковки от размерности пространства. Определение нормализованной плотности основано на том факте, что отношение плотности 24-мерной решётки Лича к объёму 24-мерного шара единичного радиуса равно 1. (Объём n-мерного шара радиуса 1 равен πn/2

1·2·3·...·(n/2) при чётном n; 2·(2π)(n–1)/2

1·3·5·...·n при нечётном n.)


Такое отношение в пространстве произвольной размерности n называется плотностью центров D. Нормализованная плотность, показанная на графике, по определению равна log2D + n(24–n)/96; для слоёных решётчатых упаковок график симметричен относительно нормализованной плотности решётки Лича. На графике видно, что плотности упаковок L3, L8 и L24 очень близки к наилучшей известной верхней границе плотности произвольной упаковки шаров. Слоёные решётчатые упаковки — самые плотные известные упаковки шаров во всех размерностях вплоть до 32, кроме 10–13. Имеется ещё одно семейство решёток, обозначенных Kn, которое начинается в L6 и возвращается к слоёному семейству в L18. В размерностях 11, 12 и 13 упаковки Kn плотнее, чем Ln. Показаны ещё упаковки Pn, тоже решётчатые. Однако плотнейшие известные упаковки в размерностях 10, 11 и 13 нерешётчатые; все эти упаковки построены при помощи кодов для передачи цифровой информации.


Решётка Лича оказала неоценимую помощь специалистам по теории групп в построении некоторых конечных простых групп. Эти группы являются «строительными блоками», из которых можно «собрать» любую группу, состоящую из конечного числа элементов. Классификация конечных простых групп, которая только что завершена3), занимала умы многих математиков более полувека. Простые группы играют в теории групп такую же роль, как простые числа в теории чисел или химические элементы в химии. Недавно удалось построить несколько важных простых групп, рассматривая множество всех жёстких вращений и отражений решётки Лича, оставляющих неподвижным некоторый центральный шар и переставляющих окружающие его шары. Это множество операций называется группой симметрии данной упаковки. Аналогичная группа симметрии для трёхмерной гранецентрированной кубической решётки показана на рис. 1.

Группа симметрии решётки Лича была найдена в 1968 году Джоном Хортоном Конвеем из Кембриджского университета. Её порядок, т.е. число элементов этой группы, огромен, хотя для теории групп в этом нет ничего особенного. Он равен 222 × 39 × 54 × 72 × 11 × 13 × 23, или 8 315 553 613 086 720 000. При помощи этой группы, которая не является простой, Конвей построил три ранее неизвестные простые группы, порядки которых являются делителями её порядка. В 1981 году решётка Лича позволила Роберту Л. Гриссу-младшему из Мичиганского университета построить одну из последних конечных простых групп, которые ещё оставалось найти. Она оказалась ещё больше группы Конвея и была прозвана «монстром». Число элементов этой группы равно 246 × 320 × 59 × 76 × 112 × 133 × 17 × 19 × 23 × 29 × 31 × 41 × 47 × 59 × 71, или 808 017 424 794 512 875 886 459 904 961 710 757 005 754 368 000 000 000. Однако конструкция Грисса отнюдь не является непосредственной, и одна из прелестей решётки Лича в том, что кажется, будто должна существовать более прямая связь между ней и простой группой-монстром.

Решётка Лича приводит к такой плотной упаковке, что её влияние ощущается во всех меньших размерностях. Нет ничего удивительного в том, что «срез» хорошей упаковки даёт хорошую упаковку в пространстве предыдущей размерности: например, в одном из «срезов» упаковки D3 обнаруживается плоскость с гексагонально упакованными кругами. Но подходящие сечения решётки Лича приводят к плотнейшим известным упаковкам во всех размерностях, меньших 24, кроме 10, 11 и 13. Например, в одном её восьмимерном «срезе» получается решётка E8.

Если при помощи решётки Лича можно строить плотные упаковки, двигаясь, так сказать, сверху вниз, то соблазнительно узнать, нельзя ли построить решётку Лича снизу вверх, т.е. исходя из плотных упаковок в низших размерностях. Оказывается, это построение возможно, причём есть очень простой способ. Начнём с плотнейшей одномерной упаковки Z1. В центре каждого одномерного шара из Z1 построим двумерный шар радиусом ½. Затем построим второй слой двумерных шаров, идентичный первому, и вставим его в углубления между шарами первого слоя настолько плотно, насколько это возможно. Уложив таким способом бесконечное множество слоёв, мы получим в результате плотную двумерную гексагональную упаковку. Учитывая способ построения, её можно назвать «слоёной» двумерной упаковкой. Она обозначается L2.

Теперь уже ясно, как перейти к трём измерениям: помещаем шар радиуса ½ в центр каждого круга из L2, а затем строим идентичные слои и располагаем их над предыдущими так, чтобы заполнить углубления и получить решётку. Поскольку эта упаковка эквивалентна D3, «послойная» процедура даёт самую плотную известную упаковку и в трёхмерном случае. Продолжая действовать таким же способом и дальше и прибавляя каждый раз по одному измерению, мы будем получать очень плотные решётчатые упаковки. Уже давно известно, что L4 и L5 эквивалентны D4 и D5, a L6, L7 и L8 — соответственно E6, E7 и E8. Таким образом, слоёные решётки приводят к плотнейшим возможным упаковкам вплоть до размерности 8.

См. также[]

Ссылки[]

Н. Дж. А. Слоэн. Упаковка шаров. В мире науки, 1984, № 3, с.72–82.

Advertisement