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

Расширенный троичный код Голея
Расширенный троичный код Голея
Назван в честь	Марсель Дж. Э. Голей
Классификация
Тип	Линейный блочный код
Длина блока	12
Длина сообщения	6
Ставка	6/12 = 0.5
Расстояние	6
Размер алфавита	3
Обозначения	-код
	v ; т ; и ;

Совершенный троичный код Голея
Совершенный троичный код Голея
Назван в честь	Марсель Дж. Э. Голей
Классификация
Тип	Линейный блочный код
Длина блока	11
Длина сообщения	6
Ставка	6/11 ~ 0.545
Расстояние	5
Размер алфавита	3
Обозначения	-код
	v ; т ; и ;

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

Характеристики

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

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

\left[{\begin{array}{cccccc|ccccc}2&2&2&1&1&0&1&0&0&0&0\\2&2&1&2&0&1&0&1&0&0&0\\2&1&2&0&2&1&0&0&1&0&0\\2&1&0&2&1&2&0&0&0&1&0\\2&0&1&1&2&2&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), равна

\left[{\begin{array}{cccccc|ccccc}1&0&0&0&0&0&1&1&1&1&1\\0&1&0&0&0&0&1&1&2&2&0\\0&0&1&0&0&0&1&2&1&0&2\\0&0&0&1&0&0&2&1&0&1&2\\0&0&0&0&1&0&2&0&1&2&1\\0&0&0&0&0&1&0&2&2&1&1\\\end{array}}\right].

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

Расширенный троичный код Голея

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

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 ₁₂ — группа Матье M ₁₂ .

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

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

Матрица -генератор расширенного троичного кода Голея имеет вид

\left[{\begin{array}{cccccc|cccccc}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].

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

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

\left[{\begin{array}{rrrrrr|rrrrrr}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_{\mathrm {alt} }].

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

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

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

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

История и приложения

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

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

См. также

Ссылки

^ Пракаш, Широман (сентябрь 2020 г.). «Магическая дистилляция состояния с троичным кодом Голея». Труды Королевского общества A: Математические, физические и технические науки . 476 (2241): 20200187.arXiv : 2003.02717 . дои : 10.1098/rspa.2020.0187 .

Барг, Александр (1993), «На заре теории кодов», The Mathematical Intelligencer , 15 (1): 20–26, doi : 10.1007/BF03025254 , MR 1199273
Голэй, MJE (июнь 1949 г.), «Заметки о цифровом кодировании» (PDF) , Proceedings of IRE , 37 : 657, MR 4021352 , заархивировано из оригинала (PDF) 19 апреля 2015 г.

Дальнейшее чтение

Блейк, ИФ (1973), Теория алгебраического кодирования: история и развитие , Страудсбург, Пенсильвания: Дауден, Хатчинсон и Росс
Конвей, Дж. Х .; Слоан, NJA (1999), Сферические упаковки, решетки и группы , Основы математических наук, том. 290 (3-е изд.), Нью-Йорк: Springer-Verlag, номер документа : 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), От кодов с исправлением ошибок через сферические упаковки к простым группам , Carus Mathematical Monographs, vol. 21, Вашингтон, округ Колумбия: Математическая ассоциация Америки, ISBN. 0-88385-023-0 , МР 0749038

[1] Пракаш, Широман (сентябрь 2020 г.). «Магическая дистилляция состояния с троичным кодом Голея». Труды Королевского общества A: Математические, физические и технические науки . 476 (2241): 20200187.arXiv : 2003.02717 . дои : 10.1098/rspa.2020.0187 .

[1]