Двійковий код Голея

В математиці і інженерній електроніці, двійковий код Голея — це тип лінійної попередньої корекції помилок, який використовується в передачі даних. Двійковий код Голея, поряд з трійковим кодом Голея, має особливо глибокий і цікавий зв'язок з теорією кінцевої спорадичної групи в математиці.[1] Ці коди названі на честь Марселя Дж. E. Голея. В 1949 році[2] ця стаття була названа Е. Р. Берлекемпом, «найкращою опублікованою роботою» в теорії кодування.[3]

Є два тісно пов'язаних двійкових коди Голея. Розширений двійковий код Голея, G24 (іноді просто називають «код Голея» в теорії кінцевих груп) кодує 12 біт даних в 24-розрядному слові таким чином, що будь-які 3-бітові помилки можуть бути виправлені, або будь-які 7-бітові помилки можуть бути виявлені. Досконалий двійковий код Голея, G23, має кодові слова довжиною 23-біта і виходить з розширеного двійкового коду Голея, якщо видалити одну координатну позицію (і навпаки, розширений двійковий код Голея виходить з досконалого двійкового коду Голея, якщо додати ще біт парності). У стандартному кодовому записі коди мають параметри [24, 12, 8], [23, 12, 7], що відповідає довжині кодових слів, кінцево-вимірного простору коду, і мінімальній відстані Геммінга між двома кодовими словами, відповідно.

Математичне визначення

У математичних термінах, розширений двійковий код Голея G24 складається з 12-вимірного лінійного підпростору W простору V=F224 24-бітових слів таких, що будь-які два різних елемента W відрізняються щонайменше на 8 координат. W називається лінійним кодом, тому що це векторний простір. Взагалі, W містить 4096 = 212 елементів.

  • Елементи W називаються кодовими словами. Вони також можуть бути описані як підмножини набору з 24 елементів, де додавання визначено як прийняття симетричної різниці підмножин.
  • У розширеному двійковому коду Голея, все кодові слова мають вагу Геммінга яка складає 0, 8, 12, 16 або 24-біта. Кодові слова ваги 8 називаються октади і кодові слова ваги 12 називаються додекади.
  • Октади коду G24 є елементами S(5,8,24) системи Штейнера. Існує 759 = 3*11*23 октади і їх 759 додатків . Звідси випливає, що є 2576 = 24*7*23 додекадів.
  • Два октади перетинаються (у 1-х загальних) в 0, 2, 4 або в координатах в бінарного вектора (можливі розміри перетинів подані в підмножинах). Октади і додекади перетинаються в 2, 4 або 6 координатах.
  • До перепризначення координат, W є унікальним.

Двійковий код Голея, G23 є досконалим кодом. Тобто сфери радіуса навколо трьох кодових слів утворюють розбиття векторного простору. G23 це 12-вимірний лінійний підпростір простору F223.

Група автоморфізмів досконалого двійкового коду Голея, G23, це група Матьє . Група автоморфізмів з розширеного двійкового коду Голея є група Матьє ,порядку 210*33*5*7*11*23. транзитивність на октади і на додекади. Інші групи Матьє відбуваються як дія групи одного або кількох елементів W.

Конструкції

  • Лексикографічний код: В свою чергу вектори в V просторі задані лексично (тобто можливо інтерпретувати їх як непідписані 24-розрядні двійкові цілі числа і взяти звичайний порядок). Починаючи з w0 = 0, визначимо w1, w2, …, w12 за правилом: wn найменше ціле число, яке відрізняється від усіх лінійних комбінацій попередніх елементів, щонайменше на вісім координат. Звідси W може бути визначена як проміжок w1, …, w12.
  • Квадратний код залишку: Розглянемо набір N квадратичних невирахувань (mod 23). Це 11-елементна підмножина з циклічною групою Z/23Z. Розглянемо зрушення t+N цієї підмножини. Доповніть кожен переклад, щоб встановити 12-елементне St шляхом додавання елементу до ∞. Потім позначимо базисні елементи V, як 0, 1, 2, …, 22, ∞, W може бути визначена як проміжок слів St разом зі словом, що складає з усі базисні вектори. (Досконалий код отримується шляхом виходу з ∞.)
  • Як Циклічний код: Досконалий G23 код може бути побудований за допомогою факторизации над бінарним полем GF(2):
Це код, згенерований .[4] У будь-якому з 11-ти ступенів нескоротні множники можуть бути використані для генерації коду.[5]
  • Будівництво Тьюріну в 1967 р, "Проста Побудова бінарного коду Голея ", який починається з коду Геммінга довжини 8 і не використовує квадратичних відрахувань mod 23.[6]
  • Від Система Штейнера S(5,8,24), що складається з 759 підмножин і 24-наборів. Якщо інтерпретувати підтримку кожної підмножини, як 0-1-кодового слова довжиною 24-біта (код Геммінга вагою 8), вони є «октадами» в двійковому коді Голея. Весь код Голея може бути отриманий шляхом повторного прийняття симетричної різниці множин в підмножинах, тобто двійковим додаванням. Ще простіше записати системи Штейнера відповідно, октади є дивом октадного генератору Р. Т. Куртісу, який використовує конкретну 1:1 відповідність між 35 розділами 8-набору і 35 розділами кінцевого векторного простору в 4-х площинах.[7] На даний момент часто використовується компактний підхід Гексакоду Конвея, який використовує 4×6 масив квадратних осередків.
  • Головні позиції в математичній грі Могула: в Могулі розташований ряд з 24 монет. Кожен хід складається з перегортання від одного до семи монет таким чином, що найлівіша з перевернутих монет йде від голови до хвоста. Програють ті гравці, які не мають права законного ходу. Якщо голови інтерпретуються як 1 і хвости як 0, то перехід до кодового слова з розширеним двійковим кодом Голея гарантує, що буде можливо отримати перемогу.
  • Генератор матриці для бінарного коду Голея I A, де I це 12×12 одинична матриця, і A є доповненням до матриці суміжності ікосаедра.

Зручне представлення

Зручно використовувати «формат октадного генератору», з координатами в масиві з 4 рядків, 6 стовпців. Додавання приймає симетричну різницю. Всі 6 стовпців мають однакову парність, що дорівнює верхньому рядку.

Перегородка з 6 стовпців в 3-х пар суміжних являє собою тріо. Це розбиття на 3 октадні множини. Підгрупа, проективних лінійних груп PSL(2,7) x S3 трьох підгруп з M24 корисна для генерування основи. PSL(2,7) переставляє октади всередині, паралельно. S3 переставляє 3 октади фізично.

Основа починається з октади T:

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 кодових слів складається з 1-го. Додавання N в кодове слово виробляє його доповнення.

Грісс (p. 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-цикл діє на Т даючи підпростір, включаючи також базисні елементи

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-мірний фактор-простір при ігноруванні останніх 2 октад.

Є 4 інші кодові слова подібної структури, які завершують основу з 12 кодових слів для W.

Слід зазначити, що W має підпростір розмірності 4, симетричною відносно PSL(2,7) x S3, напнуте шляхом N і 3 додекад, утворених з підмножин {0,3,5,6}, {0,1,4,6}, і {0,1,2,5}.

Практичне застосування кодів Голея

Далекі космічні польоти NASA

Програма Вояджер 1-ому і 2-ому космічним апаратам необхідно передавати сотні кольорових фотографій Юпітеру and Сатурну в 1979, 1980 і 1981 роках прольоту в межах лінії пропускання з ускладненою системою телекомунікації.

  • Для передачі кольорового зображення потрібно в три рази більше даних у вигляді чорно-білих зображень, таким чином код Адамара був використаний для передачі чорно-білих зображень працював за системою (24,12,8) коду Голея.[8]
  • Цей код Голея має функцію тільки для потрійної корекції помилок, але він може бути переданий на набагато більш високій швидкості передачі даних, ніж код Адамара, який використовувався під час місії Мерінер.

Засоби радіозв'язку

Нові Американські урядові стандарти для автоматичного встановлення каналів зв'язку на високо частотній системі радіозв'язку, визначає використання розширеного (24,12) блок коду Голея для попередньої корекції помилок (FEC).

  • Розширений (24,12) код Голея зазначений в (24,12) блок коду.
  • Цей код кодує 12 біт даних для отримання 24-бітових кодових слів.
  • Крім того, є систематичний код, а це означає, що 12 біт даних, що присутні в незмінному вигляді в кодовому слові.

Мінімальна відстань Геммінга між будь-якими двома кодовими словами (кількість бітів за допомогою яких будь-яка пара кодових слів відрізняється) є вісім.

Див. також

Примітки

  1. Див. Томпсон, 1983
  2. Голей, (1949)
  3. Берлекемп, Е. Р. (1974). Основні документи в розвитку теорії кодування. I.E.E.E. Видавництво. с. 4.
  4. Roman, 1992, p. 324 Example 7.4.3
  5. Pless, 1998, p. 114
  6. Тьюрін, 1967, Секція VI
  7. http://finitegeometry.org/sc/24/MOG.html
  8. http://www-math.ucdenver.edu/~wcherowi/courses/m7409/mariner9talk.pdf

Посилання

  • Конвей, Джон Хортон; Слоан, Неіл Дж. A. (1999). Сфера Упаковки, решітки та групи. Основні вчення математичних наук 290 (вид. 3-є). Берлін, Нью-Йорк: Springer-Verlag. ISBN 978-0-387-98585-5. MR 0920369.
  • Куртіс, Р. T. (1976). Новий підхід до комбінаторики M24. Математичні Праці Кембриджського філософського товариства 79: 25–42. doi:10.1017/S0305004100052075.
  • Голей, Марсель Дж. E. (1949). Зауваження до цифрового кодування. Proc. IRE 37: 657.
  • Греферас, Маркус (2003). коди Голея. У Проакіс, Джон Дж. Енциклопедія телекомунікацій. Віллі. doi:10.1002/0471219282.
  • Роберт Грісс (1998). Дванадцять спорадичних груп. Спрінгер. с. 167. ISBN 978-3-540-62778-4.
  • Плесс, Вера (1998). Введення в теорію кодів, що виправляють помилки (вид. 3rd). Джон Віллі & Сини. ISBN 978-0-471-19047-9.
  • Роман, Стівен (1996). Кодування і теорія інформації. Випускає Тексти з математики#134. Springer-Verlag. ISBN 0-387-97812-7.
  • Томпсон, Томас M. (1983). Коди, що виправляють помилки через Sphere Packings для простих груп. Карус, Математичні Монографії 21. Американська математична асоціація. ISBN 978-0-88385-023-7.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.