Как укладка апельсинов в 24 измерениях связана с получением и расшифровкой сигналов от "Вояджеров"?

Я слушал «Решение упаковки сфер в высших измерениях»; Украинский математик решил многовековую задачу упаковки сфер в измерениях 8 и 24. и прочитал там расшифровку.

Математики изучают упаковки сфер по крайней мере с 1611 года, когда Иоганн Кеплер предположил, что самый плотный способ упаковать сферы одинакового размера в космосе — это знакомая пирамидальная стопка апельсинов, которую можно увидеть в продуктовых магазинах. Несмотря на кажущуюся простоту проблемы, она не была решена до 1998 года, когда Томас Хейлз , ныне работающий в Университете Питтсбурга, наконец доказал гипотезу Кеплера на 250 страницах математических аргументов в сочетании с гигантскими компьютерными вычислениями .

позже:

Многомерные упаковки сфер трудно визуализировать, но они являются в высшей степени практичными объектами: плотные упаковки сфер тесно связаны с кодами исправления ошибок, используемыми сотовыми телефонами, космическими зондами и Интернетом для отправки сигналов по зашумленным каналам . Многомерную сферу легко определить — это просто набор точек в многомерном пространстве, которые находятся на фиксированном расстоянии от заданной центральной точки.

и позже

Решетка Пиявки строится аналогичным образом путем добавления сфер к менее плотной упаковке, и она была открыта почти задним числом. В 1960-х годах британский математик Джон Лич изучал 24-мерную упаковку, которую можно составить из кода «Голея» — кода, исправляющего ошибки, который позже использовался для передачи исторических фотографий Юпитера и Сатурна, сделанных зондами «Вояджер». . Вскоре после того, как статья Лича об этой упаковке была отправлена ​​в печать, он заметил, что есть место для установки дополнительных сфер в отверстия в упаковке, и что это удвоит плотность упаковки.

Вопрос: Как укладка апельсинов в 24 измерениях связана с получением и расшифровкой сигналов от "Вояджеров"? Можно ли относительно просто объяснить сообществу Space SE или найти источник, который объясняет связь, подходящую для этого сайта?

Томас Хейлз, изображенный в 1998 году, использовал компьютер, чтобы доказать известную гипотезу о самом плотном способе сложения сфер.

Томас Хейлз, изображенный в 1998 году, использовал компьютер, чтобы доказать известную гипотезу о самом плотном способе сложения сфер.

Лучше подходит для математики SE. Вопрос упрощается до «какая связь между упаковкой 24-мерных сфер и кодом Голея ?»
Я согласен, что это должно идти либо в математическую SE, либо в SE обработки сигналов - для этого есть эксперты.
@asdfex эксперты напишут ответы, которые я не понимаю. Я попросил здесь получить объяснение с точки зрения аппаратного обеспечения и алгоритмов "Вояджера". Эти люди не вернутся назад и не будут смотреть на технологии НАСА 1970-х годов и писать с этой точки зрения. В будущем, когда я лучше разберусь, я мог бы (а может и нет) задать более глубокий вопрос 21-го века. Вот почему я написал : «Можно ли относительно просто объяснить сообществу Space SE или найти источник, который объясняет связь, подходящую для этого сайта?» К вашему сведению, я разместил ссылку в чате DSP SE.
@RussellBorogove смотрите мой комментарий выше. Этот вопрос , как написано , лучше подходит здесь по объясненным причинам. В чате DSP SE я разместил этот вопрос и добавил Asked in Space SE в поисках ответа, подходящего для этой аудитории.
В этом нет ничего особенного для космических зондов. Это просто хороший пример устройств, которые используют коды исправления ошибок в связи (наземная связь часто не заморачивается этим, потому что проще просто обнаружить ошибки и повторно передать). Но связь с удаленными зондами имеет настолько низкую пропускную способность, что это было бы непозволительно.
@Barmar, ваше третье предложение точно объясняет, почему ваше первое предложение неверно.
@uhoh Но, как говорится в цитате, эта технология также используется в мобильных телефонах и Интернете, хотя и не так часто.
@Barmar, но часто ли 24-битные слова (относящиеся к 24 измерениям), которые используют «Вояджеры», появляются в других контекстах? В настоящее время они передают порядка 20 бит в секунду , примеров такой низкой скорости передачи данных не так много, кроме LoRa.
@uhoh Я думаю, они просто говорят об общей математической теории упаковки плотных сфер, а не конкретно о 24 измерениях.
Я вижу, вы говорите конкретно о коде Голея, а не о более общей математике.
@uhoh (&Barmar), умопомрачительно то, как эти мужчины и женщины установили связи между такими далекими областями (чего я до сих пор не могу понять). Эти коды ошибок, какими бы «совершенными» они ни были (в плане эффективности упаковки сфер), довольно слабы по сегодняшним стандартам (см. обзор Костелло « Дорога к пропускной способности канала »). Благодаря uhoh я открыл для себя еще одну грань великолепия Кеплера. Я узнал, что он предположил и вычислил предел упаковки сфер (для измерения 3), пытаясь объяснить форму снежинок. Изысканный!
@NgPh бумага отличная! Это решило мою проблему (Что мне делать на этих выходных?). По-видимому, ответ таков: «Прочитайте эту статью и задайте больше вопросов по SE». Ergo: Использовал ли космический корабль "Вояджер" код Голея, Рида-Соломона и/или код Хэмминга для кодирования передачи данных с целью исправления ошибок? (Требуется уточнение) а также Какое аппаратное обеспечение космического корабля "Вояджер" выполняло такое сложное кодирование передаваемых данных? Использовался ли в наземном декодировании «большой монстр, заполняющий стойку»?

Ответы (1)

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

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

Поскольку я не собираюсь делать никаких рисунков 24-мерных сфер и гиперкубов, я ограничу этот ответ тремя измерениями.

3-битный пример

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

Каждая ошибка передачи, то есть бит, который ошибочно принимает «0» за «1» или наоборот, соответствует перемещению на один шаг по одному из ребер этого куба.

В обычном повседневном общении с достаточно низким уровнем ошибок мы можем считать все кодовые точки действительными:

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

Теперь все допустимые слова находятся на расстоянии двух ребер друг от друга. Один перевернутый бит приводит нас к недопустимому слову, и мы знаем, что произошла ошибка, но мы не можем ее исправить, потому что есть три возможных бита, которые могли перевернуться. Это называется кодом «0 исправлений ошибок, 1 обнаружение ошибок».

Для повышения надежности удалите еще два допустимых кодовых слова:

Теперь все допустимые слова разделены тремя ребрами. Если один бит перевернется, мы получим недопустимое слово, но мы все еще можем сказать, откуда мы пришли. Если поменять местами два бита, мы не сможем исправить слово, потому что другое правильное слово ближе к неправильному коду, чем правильное слово. Следовательно, этот код называется «1 исправление ошибок, 2 обнаружения битов»[*]. Это лучшее, что мы можем получить с нашими простыми 3-битными кодовыми словами.

4-битное расширение кода

Если вы добавите еще один бит, чтобы иметь 4-битные кодовые слова, вы можете увеличить расстояние между действительными точками до трех ребер тогдашнего 4-мерного куба. Это дает еще один уровень смягчения ошибок: если поменять местами два бита, вы получите недопустимое слово прямо «посередине» нескольких допустимых слов. Вы не можете решить, какой из них может быть правильным, но, по крайней мере, вы знаете, что два бита перевернуты. Этот тип кода называется «1 исправление ошибок, 3 обнаружение ошибок».

Вояджер

В случае с «Вояджером» этого было бы недостаточно, поэтому они выбрали кодовое слово длиной 24 бита. Из общего количества 16 миллионов кодовых слов они определили только 4096 как действительные. Т.е. 12 бит несут актуальную информацию, а еще 12 используются для исправления ошибок. Это привело к коду «3 исправления ошибок, 7 обнаружений ошибок». Т.е., если в каком-то слове было неправильно принято 3 бита, то его все равно можно было корректно исправить, а если перевернулось до 7 бит; по крайней мере, будет известно, что что-то не так. Этот код можно представить так же, как я сделал это выше, в виде углов 24-мерного гиперкуба.

Теперь, как это связано с упаковкой сфер? На самом деле три изображения показывают максимально плотную упаковку сфер диаметром 1 , 2 и 3 , соответственно, при условии, что их центры должны располагаться в углах куба.[**]

Очевидно, это не выглядит слишком эффектно, но становится намного сложнее, если мы не рассматриваем цифровые, двоичные данные, а используем передатчик, который также поддерживает промежуточные значения, например, используя не простое включение/выключение. модуляции, но добавьте амплитудную модуляцию сверху. Добавив еще один шаг (например, выключение питания/низкий/высокий уровень) для каждой из трех цифр в нашем примере, мы не получим восемь допустимых кодовых слов, но на самом деле 3 3 "=" 27 - начните упаковывать свои сферы в эту сетку!

[*] Обратите внимание, что "обнаружение" не означает, что вы сможете сказать, сколько именно битовых ошибок имеется. Это относится к количеству битовых ошибок, которые могут произойти, прежде чем вы получите другое допустимое кодовое слово.

[**] Строго говоря, здесь мы имеем дело не со сферами в регулярном евклидовом пространстве, а со сферами Хэмминга, которые определяются набором углов, отстоящих на заданное число ребер от их центра. Это объясняет тот факт, что в двоичном мире только углы куба представляют действительные точки, в то время как любая другая точка будет иметь дробные координаты и просто не существует. Практически нет никакой разницы между ними в приведенных здесь примерах.

В примере с кубом, как вы можете исправить ошибку? Вы не знаете, был ли перевернут один бит или два бита. Т.е. получение 101 может быть 100 с перевернутым битом, но также может быть 011 с перевернутым двумя битами. Даже если первое более вероятно, оно все равно неоднозначно. Я не вижу, как здесь можно выполнить какое-либо исправление ошибок, только обнаружить.
@Innovine Я считаю, что вы можете исправить любые однобитовые ошибки в этом примере, но вы не можете обнаружить двухбитные ошибки. Все двухбитовые ошибки неотличимы от однобитовой ошибки противоположного слова. Таким образом, двухбитная ошибка будет «исправлена» на слово, противоположное тому, что было отправлено.
Имея все нули и все единицы в качестве недопустимого кода (как показано выше), этот подход также обнаруживает эту большую ошибку.
Ответ иллюстрирует код Хэмминга 3,1, который способен обнаруживать до 2 ошибочных битов или исправлять 1 ошибочный бит, но не то и другое одновременно . Добавление дополнительного бита четности позволяет исправлять 1-битные ошибки и обнаруживать 2-битные ошибки, но за счет дополнительного бита. en.wikipedia.org/wiki/…
@LawnmowerMan Да. Точно так же двоичный код Голея может исправить 3 ошибки или обнаружить до 6 ошибок, но не одновременно. (Это код со словами из 23 битов.) Расширенный двоичный код Голея (с 24-битными словами) может исправить 3 ошибки и обнаружить 4 ошибки. Если вам нужно только обнаружение ошибок, расширенный код может обнаружить до 7 ошибок.
Во многих реальных системах передатчик будет передавать чистые 0 и 1, а приемник будет считывать аналоговое значение. Тогда, например, (0,9, 0,3, 0,6) будет скорее 100, чем 011.
Чтобы установить связь с «оранжевой укладкой», вам потребуется ввести геометрическое понятие «расстояние Хэмминга». Так можно показать, что коды Хэмминга (и коды Голея) являются «совершенными» решениями математической проблемы «упаковки сфер».
@NgPh Ответ делает это, фактически рисуя действительные точки в кодах. Думаю, это могло бы добавить апельсинов к рисункам. В смысле, зеленые сферы? Какое это имеет отношение к апельсинам? (Я ребенком)
@OrganicMarble Используйте image.spreadshirtmedia.com/image-server/v1/mp/compositions/… , но замените 1 на 24.
@Yakk, указанные рисунки могут сбивать с толку. Некоторые читатели могут не заметить, что «расстояние» между кодовыми точками — это количество ребер (НЕ обычное евклидово расстояние). Например, на последнем рисунке сфера «размера 2» с центром в (100) покрывает (111), но не (011). Вы можете попробовать нарисовать «апельсины» (сферы) в этой геометрии Хэмминга, и давайте посмотрим, чего у вас получится.
@asdfex, вы предупредили, что ваш ответ выше — это только начало (все равно слава). Тем не менее, этого было достаточно, чтобы показать, насколько сложен вопрос ухо. И этот тип вызова объясняется прямо здесь .
@NgPh На самом деле не имеет значения, говорим ли мы здесь о евклидовом расстоянии или о расстоянии Хэмминга - пока мы остаемся двоичными, вам нужно только заменить расстояние N на Н .
@asdfex, не совсем, если вы работаете с исправлением двоичных ошибок («жесткие» ошибки). Вы можете перемещаться из одной точки в другую в своем «пространстве» только целыми шагами. Когда декодер получает сообщение, он выбирает кодовое слово, наиболее близкое к этому сообщению (с точки зрения расстояния Хэмминга). Расстояние в 1,5 бита по ошибке не имеет для этого декодера никакого значения. Очень важно уточнить, какую метрику расстояния вы используете в общей задаче «упаковки сфер».
@NgPh Должно быть ясно, что проблема упаковки сфер, решаемая решеткой Лича, является евклидовой версией, а не версией Хэмминга. Это правда, что объединение сфер Хэмминга радиуса 3, окружающих кодовые слова Голея, полностью покрывает множество слов длины 23 в двоичном алфавите, что делает код совершенным. В равной степени верно и то, что расширенный код (24 измерения) можно использовать для построения решетки Лича и, следовательно, оптимальной евклидовой упаковки. Есть две разные проблемы упаковки сфер, решаемые двумя разными, но связанными объектами (кодом Голея и решеткой Лича).
Отличный ответ. Я бы предложил добавить: 24-битное кодовое слово имеет 12 бит данных и 12 бит ECC.
@ Уилл Оррик, могу добавить, что демонстрация Марины Вязоской для измерения 8, похоже, также вдохновлена ​​​​сходством между кодом Хэмминга (8,4,4) и решеткой E8 (хотя она не упомянула Хэмминга). Оба математических объекта достигают своей границы упаковки сфер в соответствующей геометрии (Хемминг против Евклида). Вот, наверное, связь?
@asdfex, сохраняй упорство. Никто еще не продемонстрировал проблему упаковки сфер в евклидовой геометрии для размерностей N=4,5,6,7,9 до 23 и >24!
@NgPh Это больше 24 или больше 24 факториала?
@ Мэтт Данн, хорошо замечено. Больше 24.
Если код исправляет 3 ошибки, а не больше, то это означает, что существует по крайней мере одна пара кодовых точек на расстоянии ровно 6 или 7 друг от друга, верно? В противном случае код будет более или менее исправлять ошибки. По крайней мере, я так понимаю этот ответ. Но в то время как такой код может обнаруживать либо 3, либо 4 ошибки, я не понимаю, как он может обнаруживать 7 ошибок. Перестановка более 4 битов может привести к необнаруженной неправильной интерпретации одного элемента вышеупомянутой пары как другого.
@JohnBollinger Ваше понимание кажется правильным. Обратите внимание, что «обнаружение 7 ошибок» не означает, что вы можете узнать, что 7 бит перевернуты — это только означает, что вы не получите другой правильный код случайно, если 7 бит перевернуты. Вполне может быть, что слово с 7 перевернутыми битами будет исправлено другим, неправильным, действительным кодовым словом.
Да, я понимаю. Дело в том, что этот ответ говорит: « Это привело к коду «3 исправления ошибок, 7 обнаружений ошибок». Т.е., если в каком-либо слове 3 бита были приняты неправильно, это все еще можно было исправить правильно, и если до 7 битов перевернуты; по крайней мере, было бы известно, что что-то не так », но это кажется непоследовательным.
@JohnBollinger Если у вас есть лучший способ написать это ... до 3 ошибок -> исправление на правильное слово, 4 ошибки -> ошибка, неисправимая, 5-7 ошибок: исправлено на неправильное слово, 8 ошибок: правильное слово, ошибка не обнаружена
Разве терминология не будет «кодом с исправлением 3 ошибок, кодом обнаружения 4 ошибок»? Я считаю маловажным для номенклатуры тот факт, что логика исправления ошибок будет срабатывать при 5-, 6- и 7-битных ошибках (выдавая общую ошибку слова), поскольку их нельзя отличить от 3-, 2- , и 1-битные ошибки без сравнения с источником. В противном случае, почему бы вашему четырехбитному коду не быть «1 исправление ошибок, 3 обнаружение ошибок»?
@JohnBollinger Число «обнаружения» учитывает все случаи, включая те, которые можно исправить. В четырехбитном случае я напортачил.
СПАСИБО, это самое элегантное объяснение кодов обнаружения/исправления ошибок и кодов Хэмминга, которые я когда-либо видел. Никогда не понимал этого до сих пор. Удивительный
@ Джон Боллинджер, интерпретируйте это следующим образом. При использовании Golay в качестве кода ИСПРАВЛЕНИЯ гарантируется исправление до 3-х ошибок (а также указывается количество ошибок). АЛЬТЕРНАТИВНО, вы можете использовать его как код ОБНАРУЖЕНИЯ. Обнаружение гарантировано до 7 ошибок (хотя сколько - не скажет). Если вы используете его для исправления, с 4 ошибками он будет (систематически) возвращать неправильное кодовое слово. То же самое для 5,6,7 ошибок. Если вы используете его для обнаружения, с 8 ошибками он с радостью «подтвердит» кодовое слово как действительное (что, конечно, неверно).
Небольшая поправка: для расширения 4-битного кода вы должны сказать, что «вы можете увеличить расстояние между допустимыми точками до четырех ребер».
@JohnBollinger Что касается терминологии, Википедия — это всего лишь одна точка данных, но в статье «Блочный код» говорится, что код с минимальным расстоянием д может обнаружить д − 1 ошибки и что он может исправить ⌊ ( д − 1 ) / 2 ⌋ ошибки. Я думаю, что путаница возникает, когда говорят, что расширенный [8,4] код Хэмминга — это «1 исправление ошибок, 3 обнаружение ошибок». Запятая предполагает, что код может делать и то, и другое одновременно, чего он не может, — он может делать только одно или другое. Лучше, я думаю, запятую заменить словом "или".
Как укладка апельсинов в 24 измерениях связана с получением и расшифровкой сигналов от "Вояджеров"?
СпросиСетьПолитика конфиденциальности1y, 0v