Тернарный код Голея

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

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

В теории кодирования , то тройные коды Голея две тесно связанные коды коррекции ошибок . Код, обычно известный как троичный код Голея, является -кодом, то есть это линейный код над троичным алфавитом; относительное расстояние кода как большое , как это возможно , может быть для кода тройного, и , следовательно, тройной кодом Голе является совершенным кодом . Расширенный код Голея тройной является [12, 6, 6] линейным кодом , полученного добавления нулевой суммы контрольного символа в [11, 6, 5] коду. В теории конечных групп${\ displaystyle [11,6,5] _ {3}}$, расширенный троичный код Голея иногда называют троичным кодом Голея. ^{[ необходима цитата ]}

Свойства [ править ]

Тернарный код Голея [ править ]

Тернарный код Голея состоит из 3 ⁶  = 729 кодовых слов. Его матрица контроля по четности является

${\displaystyle \left[{\begin{array}{ccccccccccc}1&1&1&2&2&0&1&0&0&0&0\\1&1&2&1&0&2&0&1&0&0&0\\1&2&1&0&1&2&0&0&1&0&0\\1&2&0&1&2&1&0&0&0&1&0\\1&0&2&2&1&1&0&0&0&0&1\end{array}}\right].}$

Любые два разных кодовых слова отличаются как минимум 5 позициями. Каждое тернарное слово длины 11 имеет расстояние Хэмминга не более 2 от ровно одного кодового слова. Код также может быть построен как код квадратичного вычета длины 11 над конечным полем F ₃ ( т. Е. Поле Галуа GF (3) ).

Используемый в футбольном пуле с 11 играми, троичный код Голея соответствует 729 ставкам и гарантирует ровно одну ставку с максимум 2 неверными исходами.

Набор кодовых слов с Хэмминга весом 5 представляет собой 3- (11,5,4) конструкции .

Порождающая матрица задается Голея (1949, табл.1) является

${\displaystyle \left[{\begin{array}{ccccccccccc}1&0&0&0&0&|&1&1&1&2&2&0\\0&1&0&0&0&|&1&1&2&1&0&2\\0&0&1&0&0&|&1&2&1&0&1&2\\0&0&0&1&0&|&1&2&0&1&2&1\\0&0&0&0&1&|&1&0&2&2&1&1\\\end{array}}\right]=[X|Y].}$

Группа автоморфизмов (исходного) тернарного кода Голея - это группа Матье M11 , которая является наименьшей из спорадических простых групп.

Расширенный тернарный код Голея [ править ]

Полная масса Перечислитель кода расширенного тройная Голея является

${\displaystyle x^{12}+y^{12}+z^{12}+22\left(x^{6}y^{6}+y^{6}z^{6}+z^{6}x^{6}\right)+220\left(x^{6}y^{3}z^{3}+y^{6}z^{3}x^{3}+z^{6}x^{3}y^{3}\right).}$

Группа автоморфизмов расширенного тернарного кода Голея равна 2. M ₁₂ , где M ₁₂ - группа Матье M12 .

Расширенный троичный код Голея может быть построен как промежуток строк матрицы Адамара порядка 12 над полем F ₃ .

Рассмотрим все кодовые слова расширенного кода, которые содержат всего шесть ненулевых цифр. Наборы позиций, в которых встречаются эти ненулевые цифры, образуют систему Штейнера S (5, 6, 12).

Порождающая матрица для кода расширенных тройных Голея является

${\displaystyle \left[{\begin{array}{ccccccccccccc}1&0&0&0&0&0&|&0&1&1&1&1&1\\0&1&0&0&0&0&|&1&0&1&2&2&1\\0&0&1&0&0&0&|&1&1&0&1&2&2\\0&0&0&1&0&0&|&1&2&1&0&1&2\\0&0&0&0&1&0&|&1&2&2&1&0&1\\0&0&0&0&0&1&|&1&1&2&2&1&0\\\end{array}}\right]=[I_{6}|B].}$

Соответствующая матрица проверки на четность для этой порождающей матрицы - это , где обозначает транспонирование матрицы. ${\displaystyle [-B|I_{6}]^{T}}$${\displaystyle T}$

Альтернативная матрица генератора для этого кода:

${\displaystyle \left[{\begin{array}{rrrrrrcrrrrrr}1&0&0&0&0&0&|&0&1&1&1&1&1\\0&1&0&0&0&0&|&1&0&1&-1&-1&1\\0&0&1&0&0&0&|&1&1&0&1&-1&-1\\0&0&0&1&0&0&|&1&-1&1&0&1&-1\\0&0&0&0&1&0&|&1&-1&-1&1&0&1\\0&0&0&0&0&1&|&1&1&-1&-1&1&0\\\end{array}}\right]=[I_{6}|B_{alt}].}$

И его матрица проверки на четность есть .${\displaystyle [-B_{alt}|I_{6}]^{T}}$

Три элемента лежащего в основе конечного поля представлены здесь с помощью , а не с помощью . Также понятно, что ( то есть аддитивная величина, обратная 1) и . Произведения этих элементов конечного поля идентичны произведениям целых чисел. Суммы строк и столбцов вычисляются по модулю 3. ${\displaystyle \{0,1,-1\}}$${\displaystyle \{0,1,2\}}$${\displaystyle 2=1+1=-1}$${\displaystyle -2=(-1)+(-1)=1}$

Линейные комбинации или векторное сложение строк матрицы дают все возможные слова, содержащиеся в коде. Это называется диапазоном строк. Внутреннее произведение любых двух строк порождающей матрицы всегда будет равно нулю. Эти строки или векторы называются ортогональными .

Матричное произведение матриц генератора и проверки на четность является матрицей всех нулей и по назначению. Действительно, это пример самого определения любой матрицы проверки на четность относительно ее порождающей матрицы.${\displaystyle [I_{6}|B_{alt}]\,[-B_{alt}|I_{6}]^{T}}$${\displaystyle 6\times 6}$

История и приложения [ править ]

Тройной код Голея был опубликован Голеем  ( 1949 ). Он был независимо обнаружен двумя годами ранее финским энтузиастом футбольного пула Юхани Виртакаллио , который опубликовал его в 1947 году в выпусках 27, 28 и 33 футбольного журнала Veikkaaja . ( Барг 1993 , стр.25)

Было показано, что троичный код Голея полезен для подхода к отказоустойчивым квантовым вычислениям, известного как дистилляция магического состояния . ^[1]

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

• Граф Берлекампа – ван Линта – Зейделя
• Двоичный код Голея

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

• Барг Александр (1993), "На заре теории кодов", Математическая Интеллидженсер , 15 (1): 20-26, DOI : 10.1007 / BF03025254 , МР  1199273
• Голей, MJE (июнь 1949 г.), «Заметки о цифровом кодировании», Proceedings of the IRE , 37 : 657, MR  4021352

Дальнейшее чтение [ править ]

• Блейк, И. Ф. (1973), Алгебраическая теория кодирования: история и развитие , Страудсбург, Пенсильвания: Дауден, Хатчинсон и Росс
• Конвей, JH ; Sloane, NJA (1999) , Сферические упаковки, решетки и группы , Grundlehren der Mathematischen Wissenschaften, 290 (3-е изд.), Нью-Йорк: Springer-Verlag, DOI : 10.1007 / 978-1-4757-6568-7 , ISBN 0-387-98585-9, Руководство по ремонту  1662447
• Грисс, Роберт Л. мл. (1998), Двенадцать спорадических групп , Монографии Спрингера по математике, Берлин: Springer-Verlag, DOI : 10.1007 / 978-3-662-03516-0 , ISBN 3-540-62778-2, Руководство по ремонту  1707296
• Коэн, Жерар; Хонкала, Ииро; Лицын, Симон; Лобштейн, Антуан (1997), Покрывающие коды , Математическая библиотека Северной Голландии, 54 , Амстердам: Северная Голландия, ISBN 0-444-82511-8, Руководство по ремонту  1453577
• Томпсон, Томас М. (1983), От кодов с исправлением ошибок через упаковку сфер до простых групп , Математические монографии Каруса, 21 , Вашингтон, округ Колумбия: Математическая ассоциация Америки, ISBN 0-88385-023-0, Руководство по ремонту  0749038