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

Совершенный троичный код Голея
Названный в честь	Марсель Дж. Э. Голей
Классификация
Тип	Линейный блочный код
Длина блока	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 т е

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

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

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

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

${ Displaystyle влево [{ начинают {массив} {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 конец {массив}} право].}$

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

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

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

В матрица генератора данное Голеем (1949, Таблица 1.)

${ Displaystyle влево [{ BEGIN {массив} {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 конец {массив}} право] = [X | Y].}$

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

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

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

${ 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₁₂ это Матьё группа М12.

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

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

А матрица генератора для расширенного тернарного кода Голея

${ Displaystyle влево [{ BEGIN {массив} {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 конец {массив} } right] = [I_ {6} | B].}$

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

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

${ Displaystyle влево [{ BEGIN {массив} {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}}$.

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

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

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

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

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

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

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

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

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

• Барг, Александр (1993), "На заре теории кодов", Математический интеллект, 15 (1): 20–26, Дои:10.1007 / BF03025254, МИСТЕР 1199273
• Голей, М. Дж. Э. (Июнь 1949 г.), "Заметки о цифровом кодировании", Труды IRE, 37: 657, МИСТЕР 4021352

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

• Блейк, И. Ф. (1973), Алгебраическая теория кодирования: история и развитие, Страудсбург, Пенсильвания: Дауден, Хатчинсон и Росс
• Конвей, Дж. Х.; Слоан, Н. Дж. А. (1999), Сферы, решетки и группы, Grundlehren der Mathematischen Wissenschaften, 290 (3-е изд.), Нью-Йорк: Springer-Verlag, Дои:10.1007/978-1-4757-6568-7, ISBN 0-387-98585-9, МИСТЕР 1662447
• Грисс, Роберт Л. мл. (1998), Двенадцать спорадических групп, Монографии Springer по математике, Берлин: Springer-Verlag, Дои: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