Двоичный код Голея

Расширенный двоичный код Голея
Генераторная матрица
Назван в честь	Марселя Дж.Э. Голея
Классификация
Тип	Код линейного блока
Длина блока	24
Длина сообщения	12
Скорость	12/24 = 0,5
Расстояние	8
Размер алфавита	2
Обозначение	$[24,\; 12,\; 8]\; 2\; \{\backslash \; displaystyle\; [24,12,8]\; \_\; \{2\}\}$-code
v t

Совершенный двоичный код Голея
Назван в честь	Марселя Дж.Э. Голея
Классификация
Тип	Линейный блочный код
Длина блока	23
Длина сообщения	12
Скорость	12/23 ~ 0,522
Расстояние	7
Размер алфавита	2
Обозначение	$[\; 23,\; 12,\; 7]\; 2\; \{\backslash \; displaystyle\; [23,12,7]\; \_\; \{2\}\}$-code
v t

В математике и электронике, двоичный код Голея является типом линейного кода исправления ошибок, используемого в цифровой связи. Двоичный код Голея, наряду с троичным кодом Голея, имеет особенно глубокую и интересную связь с теорией конечных спорадических групп в математике. Эти коды названы в честь Марселя Дж. Э. Голея, чья статья 1949 года, вводящая их, была названа Э. Р. Берлекамп, «лучшая отдельная опубликованная страница» в теории кодирования.

Есть два тесно связанных двоичных кода Голея. расширенный двоичный код Голея, G 24 (иногда называемый просто «кодом Голея» в теории конечных групп) кодирует 12 бит данных в 24-битном слове таким образом, что любые 3-битные ошибки могут быть исправлены или любые 7-битные ошибки могут быть обнаружены. Другой, совершенный двоичный код Голея, G 23, имеет кодовые слова длиной 23 и получается из расширенного двоичного кода Голея путем удаления одной координатной позиции (наоборот, расширенный двоичный код Голея код получается из совершенного двоичного кода Голея путем добавления бита четности ). В стандартной нотации кодирования коды имеют параметры [24, 12, 8] и [23, 12, 7], соответствующие длине кодовых слов, размерности кода и минимальному Расстояние Хэмминга между двумя кодовыми словами соответственно.

• 1 Математическое определение
• 2 Конструкции
  • 2.1 Удобное представление
• 3 Практическое применение кодов Голея
  • 3.1 Полеты НАСА в дальний космос
  • 3.2 Радиосвязь
• 4 См. также
• 5 Ссылки
  • 5.1 Источники

С математической точки зрения расширенный двоичный код Голея G 24 состоит из 12-мерного линейного подпространства W пространства V = F224-битных слов такое, что любые два различных элемента W отличаются по крайней мере в 8 координатах. W называется линейным кодом, потому что это векторное пространство. Всего W состоит из 4096 = 2 элемента.

• Элементы W называются кодовыми словами. Их также можно описать как подмножества набора из 24 элементов, где сложение определяется как взятие симметричной разности подмножеств.
• В расширенном двоичном коде Голея все кодовые слова имеют веса Хэмминга из 0, 8, 12, 16 или 24. Кодовые слова веса 8 называются октадами, а кодовые слова веса 12 называются додекадами .
• октадами кода G 24 являются элементами системы Штейнера S (5,8,24) . Всего 759 = 3 × 11 × 23 октад и 759 их дополнений. Отсюда следует, что существует 2576 = 2 × 7 × 23 додекада.
• Две октады пересекаются (имеют общие единицы) в координатах 0, 2 или 4 в двоичном векторном представлении (это возможные размеры пересечения в представление подмножества). Октада и додекада пересекаются в координатах 2, 4 или 6.
• До перемаркировки координат W уникален.

Двоичный код Голея, G 23 - это идеальный код. То есть сферы радиуса три вокруг кодовых слов образуют раздел векторного пространства. G 23 - 12-мерное подпространство пространства F2.

. Группа автоморфизмов совершенного двоичного кода Голея, G 23, это группа Матье $M\; 23\; \{\backslash \; displaystyle\; M\_\; \{23\}\}$. группа автоморфизмов расширенного двоичного кода Голея - это группа Матье $M\; 24\; \{\backslash \; displaystyle\; M\_\; \{24\}\}$порядка 2 × 3 × 5 × 7 × 11 × 23. $M\; 24\; \{\backslash \; displaystyle\; M\_\; \{24\}\}$транзитивен по октадам и додекадам. Другие группы Матье встречаются как стабилизаторы одного или нескольких элементов W.

• Лексикографический код : упорядочить векторы в V лексикографически (т. Е. Интерпретировать их как беззнаковые 24-битные двоичные целые числа и взять обычный порядок). Начиная с w 0 = 0, определите w 1, w 2,..., w 12 по правилу, что w n - наименьшее целое число, которое отличается от всех линейных комбинаций предыдущих элементов как минимум по восьми координатам. Тогда W можно определить как промежуток w 1,..., w 12.
• группа Матье : Витт в 1938 г. опубликовал конструкцию самой большой группы Матье, которую можно использовать для построения расширенный двоичный код Голея.
• Квадратичный код остатка : Рассмотрим набор N квадратичных невычетов (модуль 23). Это 11-элементное подмножество циклической группы Z/ 23 Z . Рассмотрим трансляции t + N этого подмножества. Увеличьте каждый перевод до набора из 12 элементов S t, добавив элемент ∞. Тогда маркировка базисных элементов V числами 0, 1, 2,..., 22, ∞, W может быть определена как промежуток слов S t вместе со словом, состоящим из всех базисных векторов. (Идеальный код получается путем исключения ∞.)
• Как Циклический код : Совершенный код G 23 может быть построен путем факторизации $x\; 23\; -\; 1\; \{\backslash \; displaystyle\; x\; ^\; \{23\}\; -1\}$над двоичным полем GF (2) :

$x\; 23\; -\; 1\; =\; (x\; -\; 1)\; (x\; 11\; +\; x\; 9\; +\; x\; 7\; +\; x\; 6\; +\; x\; 5\; +\; x\; +\; 1)\; (x\; 11\; +\; x\; 10\; +\; x\; 6\; +\; x\; 5\; +\; x\; 4\; +\; x\; 2\; +\; 1).\; \{\backslash \; displaystyle\; x\; ^\; \{23\}\; -1\; =\; (x-1)\; (x\; ^\; \{11\}\; +\; x\; ^\; \{9\}\; +\; x\; ^\; \{7\}\; +\; x\; ^\; \{6\}\; +\; x\; ^\; \{5\}\; +\; x\; +\; 1)\; (x\; ^\; \{11\}\; +\; x\; ^\; \{10\}\; +\; x\; ^\; \{6\}\; +\; x\; ^\; \{5\}\; +\; x\; ^\; \{4\}\; +\; x\; ^\; \{2\}\; +1).\}$

Это сгенерированный код на $(x\; 11\; +\; x\; 10\; +\; x\; 6\; +\; x\; 5\; +\; x\; 4\; +\; x\; 2\; +\; 1)\; \{\backslash \; displaystyle\; \backslash \; left\; (x\; ^\; \{11\}\; +\; x\; ^\; \{10\}\; +\; x\; ^\; \{6\}\; +\; x\; ^\; \{5\}\; +\; x\; ^\; \{4\}\; +\; x\; ^\; \{2\}\; +1\; \backslash \; right)\}$. Для генерации кода может использоваться любой из неприводимых множителей степени 11.

• Конструкция Турина 1967 года «Простая конструкция двоичного кода Голея», которая начинается с кода Хэмминга длины 8 и выполняет не использовать квадратичные остатки по модулю 23.
• Из системы Штейнера S (5,8,24), состоящей из 759 подмножеств 24-набора. Если интерпретировать поддержку каждого поднабора как кодовое слово 0-1 длины 24 (с весом Хэмминга 8), это будут «октады» в двоичном коде Голея. Полный код Голея может быть получен путем многократного взятия симметричных разностей подмножеств, то есть двоичного сложения. Более простой способ записать систему Штайнера соотв. октады - это Miracle Octad Generator RT Curtis, который использует конкретное 1: 1-соответствие между 35 разделами 8-набора на два 4-набора и 35 разделами конечного векторного пространства $F\; 2\; 4\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{F\}\; \_\; \{2\}\; ^\; \{4\}\}$на 4 плоскости. В настоящее время часто используется компактный подход гексакода Конвея, который использует массив квадратных ячеек 4 × 6.
• Выигрышные позиции в математической игре Mogul: позиция в Mogul - это ряд из 24 монет. Каждый ход состоит из подбрасывания от одной до семи монет таким образом, что самая левая из подброшенных монет проходит от головы к хвосту. Проигрышные позиции - те, у которых нет легального хода. Если головы интерпретируются как 1, а хвосты - как 0, то переход к кодовому слову из расширенного двоичного кода Голея гарантирует, что будет возможно добиться выигрыша.
• A матрица генератора для двоичного кода Голея равна IA, где I - это единичная матрица 12 × 12, а A - дополнение к матрице смежности для икосаэдра.

A удобное представление

Удобно использовать формат «Miracle Octad Generator », с координатами в массиве из 4 строк, 6 столбцов. Сложение берет симметричную разность. Все 6 столбцов имеют одинаковую четность, равную четности верхней строки.

Разделение 6 столбцов на 3 пары соседних столбцов образует трио. Это разделение на 3 восьмеричных набора. Подгруппа проективная специальная линейная группа PSL (2,7) x S 3 подгруппы трио в M 24 полезна для создания базиса. PSL (2,7) переставляет октады внутри параллельно. S 3 телесно переставляет 3 октады.

Базис начинается с октады T:

0 1 1 1 1 1

1 0 0 0 0 0

1 0 0 0 0 0

1 0 0 0 0 0

и 5 подобных октад. Сумма N всех 6 этих кодовых слов состоит из всех единиц. Добавление N к кодовому слову дает его дополнение.

Грисс (стр. 59) использует маркировку:

∞ 0 | ∞ 0 | ∞ 0

3 2 | 3 2 | 3 2

5 1 | 5 1 | 5 1

6 4 | 6 4 | 6 4

PSL (2,7), естественно, является дробно-линейной группой, порожденной (0123456) и (0∞) (16) (23) (45). 7-цикл действует на T, чтобы дать подпространство, включающее также базисные элементы

0 1 1 0 1 0

0 0 0 0 0 0

0 1 0 1 0 1

1 1 0 0 0 0

и

0 1 1 0 1 0

0 1 0 1 0 1

1 1 0 0 0 0

0 0 0 0 0 0

Результирующее 7-мерное подпространство имеет 3-мерное факторное пространство при игнорировании последних двух октад.

Есть еще 4 кодовых слова аналогичной структуры, которые завершают основу из 12 кодовых слов для этого представления W.

W имеет подпространство размерности 4, симметричное относительно PSL (2,7) x S 3, состоящий из N и 3 додекадов, образованных из подмножеств {0,3,5,6}, {0,1,4,6} и {0,1,2,5}.

Миссии НАСА в дальний космос

Исправление ошибок было жизненно важным для передачи данных на космических кораблях Вояджер 1 и 2, особенно потому, что память Ограничения вынуждали выгружать данные практически мгновенно, не оставляя вторых шансов. Сотни цветных изображений Юпитера и Сатурна в их пролете 1979, 1980 и 1981 годов будут передаваться в пределах ограниченной полосы частот связи. Следовательно, было использовано кодирование Голея. Для передачи цветного изображения требовалось в три раза больше данных, чем для черно-белых изображений, поэтому код Адамара, который использовался для передачи черно-белых изображений, был переключен на код Голея (24,12,8). Этот код Голея исправляет только тройные ошибки, но он может передаваться с гораздо более высокой скоростью передачи данных, чем код Адамара, который использовался во время миссии Mariner.

Радиосвязь

MIL-STD-188 Американские военные стандарты для автоматического установления связи в высокочастотных радиосистемах. укажите использование расширенного (24,12) кода Голея для упреждающего исправления ошибок.

• Решетка пиявки

Источники

• Конвей, Джон Хортон ; Sloane, Neil JA (1999), Sphere Packings, Lattices and Groups, Grundlehren der Mathematischen Wissenschaften, 290 (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag, ISBN 978-0-387-98585-5, MR 0920369
• Curtis, RT (1976). «Новый комбинаторный подход к M 24 ». Математические материалы Кембриджского философского общества. 79: 25–42. doi : 10.1017 / S0305004100052075.
• Греферат, Маркус (2003). «Коды Голая». В Proakis, Джон Г. (ред.). Энциклопедия телекоммуникаций. Вайли. doi : 10.1002 / 0471219282.eot371.
• Грисс, Роберт Л. (1998). Двенадцать спорадических групп. Springer. п. 167. ISBN 978-3-540-62778-4.
• Плесс, Вера (1998), Введение в теорию кодов, исправляющих ошибки ( 3-е изд.), John Wiley Sons, ISBN 978-0-471-19047-9
• Роман, Стивен (1996), Теория кодирования и информации, Тексты для выпускников по математике # 134, Springer-Verlag, ISBN 0-387-97812-7
• Томпсон, Томас М. (1983). От кодов с исправлением ошибок до сферических упаковок и простых групп. Математические монографии Каруса. 21 . Математическая ассоциация Америки. ISBN 978-0-88385-023-7. CS1 maint: ref = harv (ссылка )
• Турин, Ричард Дж.; и др. ( 1967). Исследования по развитию алгебраической теории кодов (Раздел VI) (PDF) (Отчет). Исследовательские лаборатории ВВС Кембриджа. Архивировано из оригинального (PDF) 30 октября, 2018. CS1 maint: ref = harv (ссылка )

.