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

Тип линейного кода с исправлением ошибок

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

Существует два тесно связанных двоичных кода Голея. Расширенный двоичный код Голея , G ₂₄ (иногда называемый просто «кодом Голея» в теории конечных групп) кодирует 12 бит данных в 24-битном слове таким образом, что любые 3-битные ошибки могут быть исправлены или любые 4-битные ошибки могут быть обнаружены. Другой, совершенный двоичный код Голея , 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 ₂₃ — это совершенный код . То есть сферы радиуса три вокруг кодовых слов образуют разбиение векторного пространства. G ₂₃ — это 12-мерное подпространство пространства F²³
₂.

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

Существует одно слово веса 24, которое является 1-мерным инвариантным подпространством. поэтому имеет 11-мерное неприводимое представление на поле с 2 элементами. Кроме того, поскольку двоичный код Голея является 12-мерным подпространством 24-мерного пространства, также действует на 12-мерное фактор-пространство , называемое двоичным кокодом Голея . Слово в кокоде находится в том же смежном классе, что и слово длины 0, 1, 2, 3 или 4. В последнем случае 6 (непересекающихся) кокодовых слов все лежат в одном смежном классе. Существует 11-мерное инвариантное подпространство, состоящее из кокодовых слов с нечетным весом, что дает второе 11-мерное представление на поле с 2 элементами. ${\displaystyle M_{24}}$ ${\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) : Это код, сгенерированный . ^[5] Для генерации кода может быть использован любой из неприводимых множителей степени 11. ^[6] ${\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).}$$ ${\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 RT Curtis, который использует особое соответствие 1:1 между 35 разбиениями 8-множества на два 4-множества и 35 разбиениями конечного векторного пространства на 4 плоскости. ^[8] В настоящее время часто используется компактный подход гексакода Конвея, который использует массив квадратных ячеек 4×6. ${\displaystyle \mathbb {F} _{2}^{4}}$
• Выигрышные позиции в математической игре Могул: позиция в Могул представляет собой ряд из 24 монет. Каждый ход состоит из подбрасывания от одной до семи монет таким образом, чтобы самая левая из подброшенных монет перешла от орла к решке. Проигрышные позиции — это те, в которых нет разрешенного хода. Если орел интерпретируется как 1, а решка как 0, то переход к кодовому слову из расширенного двоичного кода Голея гарантирует, что можно будет принудительно выиграть.
• Генераторная матрица для двоичного кода Голея — IA , где I — единичная матрица 12×12, а A — дополнение матрицы смежности икосаэдра .

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

Удобно использовать формат " 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 11 0 0 0 0 01 0 0 0 0 01 0 0 0 0 0

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

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

∞ 0 | ∞ 0 | ∞ 03 2 | 3 2 | 3 25 1 | 5 1 | 5 16 4 | 6 4 | 6 4

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

0 1 1 0 1 00 0 0 0 0 00 1 0 1 0 11 1 0 0 0 0

и

0 1 1 0 1 00 1 0 1 0 11 1 0 0 0 00 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}.

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

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

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

Радиосвязь

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

В системе двусторонней радиосвязи с цифровым кодированием шумоподавления (DCS, CDCSS) используется 23-битное кодовое слово Голея (23,12), которое позволяет обнаруживать и исправлять ошибки в 3 или менее бит.

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

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

Ссылки

1. Томпсон 1983
2. Golay, Marcel JE (1949). «Заметки о цифровом кодировании» (PDF) . Proc. IRE . 37 : 657. Архивировано из оригинала (PDF) 10 апреля 2023 г.
3. Берлекамп, Э. Р. (1974), Ключевые статьи в развитии теории кодирования , IEEE Press, стр. 4
4. Хансен, Роберт Питер. «Построение и простота больших групп Матье». SJSU Scholar Works .
5. Роман 1996, стр. 324 Пример 7.4.3
6. Плесс 1998, стр. 114
7. Турин 1967, Раздел VI
8. Каллинан, Стивен Х. «Чудо-генератор октад». Конечная геометрия квадрата и куба .
9. Cherowitzo, Bill. "Combinatorics in Space - The Mariner 9 Telemetry System" (PDF) . University of Colorado Denver . Архивировано из оригинала (PDF) 2013-09-27 . Получено 2012-06-06 .
10. Джонсон, Эрик Э. (1991-02-24). "Эффективный кодек Golay для MIL-STD-188-141A и FED-STD-1045" (PDF) . Получено 2017-12-09 .
11. "Военный стандарт: Стандарт планирования и руководства для автоматизированного управления приложением для HF Radio" (PDF) . EverySpec: Технические характеристики, стандарты, справочники и документы Mil-Spec . 1994-04-04 . Получено 2017-12-09 .

Источники

• Конвей, Джон Хортон ; Слоан, Нил Дж. А. (1999), Упаковки сфер, решетки и группы, Grundlehren der Mathematischen Wissenschaften, vol. 290 (3-е изд.), Берлин, Нью-Йорк: Springer-Verlag , ISBN 978-0-387-98585-5, МР  0920369
• Кертис, РТ (1976). «Новый комбинаторный подход к М ₂₄ ». Математические труды Кембриджского философского общества . 79 (1): 25–42. Bibcode : 1976MPCPS..79...25C. doi : 10.1017/S0305004100052075. S2CID  122860631.
• Греферат, Маркус (2003). «Коды Голея». В Proakis, Джон Г. (ред.). Энциклопедия телекоммуникаций . Wiley. doi :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), Кодирование и теория информации , Graduate Texts in Mathematics #134, Springer-Verlag, ISBN 0-387-97812-7
• Томпсон, Томас М. (1983). От кодов исправления ошибок через сферические упаковки к простым группам . Математические монографии Каруса. Т. 21. Математическая ассоциация Америки. ISBN 978-0-88385-023-7.
• Turyn, Richard J.; et al. (1967). Исследования по разработке алгебраической теории кодов (раздел VI) (PDF) (Отчет). Исследовательские лаборатории ВВС Кембриджа. Архивировано из оригинала (PDF) 30 октября 2018 г.