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

Тип линейного кода, исправляющего ошибки

В математике и электронике двоичный код Голея — это тип линейного кода с исправлением ошибок, используемый в цифровой связи . Бинарный код Голея, наряду с троичным кодом Голея , имеет особенно глубокую и интересную связь с теорией конечных спорадических групп в математике. ^[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 _{24 являются элементами} системы Штейнера S(5,8,24) . Всего 759 = 3 × 11 × 23 октад и 759 их дополнений. Отсюда следует, что существует 2576 = 2 ⁴ × 7 × 23 додекады.
• Две октады пересекаются (имеют общие единицы) по координатам 0, 2 или 4 в представлении двоичного вектора (это возможные размеры пересечения в представлении подмножества). Октада и додекада пересекаются по 2, 4 или 6 координатам.
• С точностью до перемаркировки координат W уникальна.

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

Группа автоморфизмов совершенного бинарного кода Голея G ₂₃ (имеется в виду подгруппа группы S ₂₃ перестановок координат 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 квадратичных невычетов (по модулю 23). Это 11-элементное подмножество циклической группы Z /23 Z. Рассмотрим переводы t + N этого подмножества. Дополните каждый перевод до набора S _t из 12 элементов, добавив элемент ∞. Тогда, помечая базисные элементы 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), это «октады» в двоичном коде Голея. Весь код Голея можно получить путем многократного взятия симметричных разностей подмножеств, т.е. двоичного сложения. Более простой способ записать систему Штейнера. октады - это чудо-генератор октад Р.Т. Кертиса, который использует особое соответствие 1:1 между 35 разбиениями 8-множества на два 4-множества и 35 разбиениями конечного векторного пространства на 4 плоскости. ^[8] В настоящее время часто используется компактный подход гексакода Конвея, который использует массив квадратных ячеек 4×6. ${\displaystyle \mathbb {F} _{2}^{4}}$
• Выигрышные позиции в математической игре Могул: позиция в Могуле представляет собой ряд из 24 монет. Каждый ход состоит из подбрасывания от одной до семи монет, при этом крайняя левая из подброшенных монет идет от головы к хвосту. Проигрышными являются позиции, в которых нет законного хода. Если орел интерпретируется как 1, а решка как 0, то переход к кодовому слову из расширенного двоичного кода Голея гарантирует, что можно будет добиться победы.
• Матрица -генератор для двоичного кода Голея — IA , где I — единичная матрица 12×12, а A — дополнение матрицы смежности икосаэдра .

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

Удобно использовать формат « Чудесный генератор октад », с координатами в массиве из 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» и «Вояджер-2», особенно потому, что ограничения памяти требовали практически мгновенной выгрузки данных, не оставляя второго шанса. Сотни цветных изображений Юпитера и Сатурна во время их пролетов в 1979, 1980 и 1981 годах будут передаваться в рамках ограниченной полосы пропускания телекоммуникаций. Для передачи цветного изображения требовалось в три раза больше данных, чем для черно-белых изображений, поэтому код Рида-Мюллера, исправляющий 7 ошибок , который использовался для передачи черно-белых изображений Маринера, был заменен кодом Голея с гораздо более высокой скоростью передачи данных (24,12 ,8) код. ^[9]

Радиосвязь

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

Смотрите также

• Решетка пиявки
• Линейный код

Рекомендации

1. Томпсон 1983
2. Голей, Марсель Дж. Э. (1949). «Заметки о цифровом кодировании» (PDF) . Учеб. ИРЭ . 37 : 657. Архивировано из оригинала (PDF) 10 апреля 2023 г.
3. Берлекамп, Э.Р. (1974), Ключевые статьи по развитию теории кодирования , IEEE Press, стр. 4
4. Хансен, Роберт Питер. «Построение и простота больших групп Матье». Научные труды ГЖГУ .
5. Роман 1996, с. 324 Пример 7.4.3
6. Плесс 1998, с. 114
7. Турин 1967, Раздел VI.
8. Каллинейн, Стивен Х. «Чудесный генератор октад». Конечная геометрия квадрата и куба .
9. Черовицо, Билл. «Комбинаторика в космосе — телеметрическая система Mariner 9» (PDF) . Университет Колорадо в Денвере . Архивировано из оригинала (PDF) 27 сентября 2013 г. Проверено 6 июня 2012 г.
10. Джонсон, Эрик Э. (24 февраля 1991 г.). «Эффективный кодек Голея для MIL-STD-188-141A и FED-STD-1045» (PDF) . Проверено 9 декабря 2017 г.
11. «Военный стандарт: Стандарт планирования и руководства по применению автоматизированного управления КВ-радиостанцией» (PDF) . EverySpec: спецификации, стандарты, справочники и документы военного стандарта . 04.04.1994 . Проверено 9 декабря 2017 г.

Источники

• Конвей, Джон Хортон ; Слоан, Нил Дж. А. (1999), Упаковки сфер, решетки и группы, Grundlehren der Mathematischen Wissenschaften, vol. 290 (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-98585-5, МР  0920369
• Кертис, RT (1976). «Новый комбинаторный подход к М ₂₄ ». Математические труды Кембриджского философского общества . 79 (1): 25–42. Бибкод : 1976MPCPS..79...25C. дои : 10.1017/S0305004100052075. S2CID  122860631.
• Греферат, Маркус (2003). «Коды Голея». В Проакисе, Джон Г. (ред.). Энциклопедия телекоммуникаций . Уайли. дои : 10.1002/0471219282.eot371. ISBN 0471219282.
• Грисс, Роберт Л. (1998). Двенадцать спорадических групп . Спрингер. п. 167. ИСБН 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.
• Тьюрин, Ричард Дж.; и другие. (1967). Исследования по развитию алгебраической теории кодов (Раздел VI) (PDF) (Отчет). Кембриджские исследовательские лаборатории ВВС. Архивировано из оригинала (PDF) 30 октября 2018 г.