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

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

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

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

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

Математическое определение [ править ]

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

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

Двоичный код Голея, G _23, является идеальным кодом . То есть сферы радиуса три вокруг кодовых слов образуют раздел векторного пространства. G ₂₃ - 12-мерное подпространство пространства F ₂ ²³ .

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

Конструкции [ править ]

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

${\ 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).}$

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

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

Удобное представление [ править ]

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

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

Основа начинается с октада Т:

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 ₃ , натянутое на N и 3 додекада, образованных из подмножеств {0,3,5,6}, {0,1,4,6} и {0,1,2,5}.

Практическое применение кодов Голея [ править ]

Миссии НАСА в дальний космос [ править ]

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

Радиосвязь [ править ]

В MIL-STD-188 американские военные стандарты для автоматического установления связи в высокочастотных системах радиосвязи определяют использование расширенного (24,12) Голея код для упреждающей коррекции ошибок . ^{[10] [11]}

См. Также [ править ]

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

Ссылки [ править ]

Источники [ править ]

• Конвей, Джон Хортон ; Слоан, Нил Дж. А. (1999), Сферические упаковки, решетки и группы , Grundlehren der Mathematischen Wissenschaften, 290 (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-98585-5, MR  0920369
• Кертис, RT (1976). «Новый комбинаторный подход к M ₂₄ ». Математические труды Кембриджского философского общества . 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 ( ссылка )