Бинарные коды Голея: теория и применение

Введение

Тип кода коррекции линейных ошибок

В математике и электротехнике двоичный код Голея — это тип кода коррекции линейных ошибок, используемый в цифровой связи. Двоичный код Голея, наряду с троичным кодом Голея, имеет особенно глубокую и интересную связь с теорией конечных спорадических групп в математике. Эти коды названы в честь Марселя Дж. Э. Голея, чья статья 1949 года, представляющая их, была названа Э. Р. Берлекампом «лучшей единичной опубликованной страницей» в теории кодирования. Существует два тесно связанных двоичных кода Голея. Расширенный двоичный код Голея, G24 (иногда просто называемый «кодом Голея» в теории конечных групп), кодирует 12 бит данных в 24-битное слово таким образом, что любые 3-битные ошибки могут быть исправлены или любые 7-битные ошибки могут быть обнаружены. Другой, совершенный двоичный код Голея, G23, имеет кодовые слова длиной 23 и получается из расширенного двоичного кода Голея путем удаления одной координатной позиции (обратно, расширенный двоичный код Голея получается из совершенного двоичного кода Голея путем добавления бита четности). В стандартном обозначении кодирования коды имеют параметры [24, 12, 8] и [23, 12, 7], соответствующие длине кодовых слов, размерности кода и минимальному расстоянию Хэмминга между двумя кодовыми словами, соответственно.

Математическое определение

В математическом выражении расширенный двоичный код Голея G24 состоит из 12-мерного линейного подпространства W пространства 24-битных слов, причем любые два различных элемента W отличаются по крайней мере в 8 координатах. W называется линейным кодом, поскольку это векторное пространство. В целом, W содержит 2¹² = 4096 элементов. Элементы W называются кодовыми словами. Они также могут быть описаны как подмножества множества из 24 элементов, где сложение определяется как взятие симметрической разности подмножеств. В расширенном двоичном коде Голея все кодовые слова имеют веса Хэмминга 0, 8, 12, 16 или 24. Кодовые слова весом 8 называются октадами, а кодовые слова весом 12 – додекадами. Октады кода G24 являются элементами системы Штейнера S(5,8,24). Существует 3 × 11 × 23 = 759 октад и 759 их дополнений. Следовательно, существует 24 × 7 × 23 = 3864 додекады. Две октады пересекаются (имеют общие 1) в 0, 2 или 4 координатах в бинарном векторном представлении (это возможные размеры пересечения в представлении подмножества). Октада и додекада пересекаются в 2, 4 или 6 координатах. С точностью до переобозначения координат, W уникален. Бинарный код Голея G23 является совершенным кодом. То есть, сферы радиуса три вокруг кодовых слов образуют разбиение векторного пространства. G23 – 12-мерное подпространство пространства F. Автоморфическая группа совершенного двоичного кода Голея G23 (то есть подгруппа группы S23 перестановок координат F, которые оставляют G23 инвариантным) является группой Матье. Автоморфическая группа расширенного двоичного кода Голея – группа Матье порядка 2¹⁰ × 3³ × 5 × 7 × 11 × 23. является транзитивной относительно октад и додекад. Другие группы Матье возникают как стабилизаторы одного или нескольких элементов W. Существует единственное слово весом 24, которое является 1-мерным инвариантным подпространством. Следовательно, имеет 11-мерное неприводимое представление над полем из 2 элементов. Кроме того, поскольку двоичный код Голея является 12-мерным подпространством 24-мерного пространства, также действует на 12-мерное фактор-пространство, называемое двоичным кокодом Голея. Слово в кокоде находится в том же классе эквивалентности, что и слово длины 0, 1, 2, 3 или 4. В последнем случае 6 (непересекающихся) кокодовых слов лежат в одном и том же косете. Существует 11-мерное инвариантное подпространство, состоящее из кокодовых слов с нечетным весом, что дает второе 11-мерное представление над полем из 2 элементов.

In mathematical terms, the extended binary Golay code G24 consists of a 12 dimensional linear subspace W of the space of 24 bit words such that any two distinct elements of W differ in at least 8 coordinates. W is called a linear code because it is a vector space. In all, W comprises 1=4096 = 212 elements. The elements of W are called code words. They can also be described as subsets of a set of 24 elements, where addition is defined as taking the symmetric difference of the subsets. In the extended binary Golay code, all code words have Hamming weights of 0, 8, 12, 16, or 24. Code words of weight 8 are called octads and code words of weight 12 are called dodecads. Octads of the code G24 are elements of the S(5,8,24) Steiner system. There are 1=759 = 3 × 11 × 23 octads and 759 complements thereof. It follows that there are 1=2576 = 24 × 7 × 23 dodecads. Two octads intersect (have 1's in common) in 0, 2, or 4 coordinates in the binary vector representation (these are the possible intersection sizes in the subset representation). An octad and a dodecad intersect at 2, 4, or 6 coordinates. Up to relabeling coordinates, W is unique. The binary Golay code, G23 is a perfect code. That is, the spheres of radius three around code words form a partition of the vector space. G23 is a 12 dimensional subspace of the space F.

The automorphism group of the perfect binary Golay code G23 (meaning the subgroup of the group S23 of permutations of the coordinates of F which leave G23 invariant), is the Mathieu group The automorphism group of the extended binary Golay code is the Mathieu group , of order 210 × 33 × 5 × 7 × 11 × 23. is transitive on octads and on dodecads. The other Mathieu groups occur as stabilizers of one or several elements of W.

There is a single word of weight 24, which is a 1 dimensional invariant subspace. therefore has an 11 dimensional irreducible representation on the field with 2 elements. In addition, since the binary golay code is a 12 dimensional subspace of a 24 dimensional space, also acts on the 12 dimensional quotient space, called the binary Golay cocode. A word in the cocode is in the same coset as a word of length 0, 1, 2, 3, or 4. In the last case, 6 (disjoint) cocode words all lie in the same coset. There is an 11 dimensional invariant subspace, consisting of cocode words with odd weight, which gives a second 11 dimensional representation on the field with 2 elements.

Строительство

Лексикографический код: упорядочивайте векторы в V лексикографически (т.е. интерпретируйте их как беззнаковые 24-битные двоичные целые числа и используйте обычный порядок). Начиная с w0 = 0, определите w1, w2, ..., w12 по правилу, что wn – наименьшее целое число, которое отличается от всех линейных комбинаций предыдущих элементов по крайней мере в восьми координатах. Тогда W можно определить как пространство, порожденное w1, ..., w12. Группа Матье: Витт в 1938 году опубликовал конструкцию наибольшей группы Матье, которая может быть использована для построения расширенного двоичного кода Голея. Код квадратичных вычетов: рассмотрим множество N квадратичных невычетов (mod 23). Это подмножество из 11 элементов циклической группы Z/23Z. Рассмотрим сдвиги t+N этого подмножества. Дополните каждый сдвиг до множества из 12 элементов St, добавив элемент ∞. Затем, обозначив базисные элементы V числами 0, 1, 2, ..., 22, ∞, определите W как пространство, порожденное множествами St вместе со словом, состоящим из всех базисных векторов. (Совершенный код получается, исключив ∞.) Как циклический код: совершенный код G23 может быть построен посредством факторизации над двоичным полем GF(2): это код, порожденный любым из неприводимых множителей степени 11, которые могут быть использованы для генерации кода. Конструкция Турина 1967 года, "Простое построение двоичного кода Голея", которая начинается с кода Хэмминга длины 8 и не использует квадратичные вычеты по модулю 23. Из системы Штейнера S(5,8,24), состоящей из 759 подмножеств множества из 24 элементов. Если интерпретировать носитель каждого подмножества как кодовое слово 0-1 длины 24 (с весом Хэмминга 8), то это "октады" в двоичном коде Голея. Весь код Голея можно получить, многократно вычисляя симметрические разности подмножеств, то есть выполняя двоичное сложение. Более простой способ записи системы Штейнера, соответственно, октад – генератор чудесных октад Р.Т. Кертиса, который использует конкретное взаимно однозначное соответствие между 35 разбиениями множества из 8 элементов на два множества по 4 элемента и 35 разбиениями конечного векторного пространства на 4 плоскости. В настоящее время часто используется компактный подход гексакода Конвея, который использует массив из квадратных ячеек 4×6. Выигрышные позиции в математической игре Могул: позиция в Могуле – это ряд из 24 монет. Каждый ход состоит в переворачивании от одной до семи монет таким образом, чтобы самая левая из перевернутых монет изменила положение с орла на решку. Проигрышные позиции – это те, для которых нет допустимого хода. Если орёл интерпретируется как 1, а решка как 0, то переход к кодовому слову из расширенного двоичного кода Голея гарантирует возможность вынудить победу. Матрица-генератор для двоичного кода Голея – I A, где I – единичная матрица 12×12, а A – дополнение к матрице смежности икосаэдра.

Lexicographic code: Order the vectors in V lexicographically (i. e., interpret them as unsigned 24 bit binary integers and take the usual ordering). Starting with w0 = 0, define w1, w2, , w12 by the rule that wn is the smallest integer which differs from all linear combinations of previous elements in at least eight coordinates. Then W can be defined as the span of w1, , w12. Mathieu group: Witt in 1938 published a construction of the largest Mathieu group that can be used to construct the extended binary Golay code. Quadratic residue code: Consider the set N of quadratic non residues (mod 23). This is an 11 element subset of the cyclic group Z/23Z. Consider the translates t+N of this subset. Augment each translate to a 12 element set St by adding an element ∞. Then labeling the basis elements of V by 0, 1, 2, , 22, ∞, W can be defined as the span of the words St together with the word consisting of all basis vectors. (The perfect code is obtained by leaving out ∞.) As a cyclic code: The perfect G23 code can be constructed via the factorization of over the binary field GF(2): It is the code generated by Either of degree 11 irreducible factors can be used to generate the code. Turyn's construction of 1967, "A Simple Construction of the Binary Golay Code," that starts from the Hamming code of length 8 and does not use the quadratic residues mod 23. From the Steiner System S(5,8,24), consisting of 759 subsets of a 24 set. If one interprets the support of each subset as a 0 1 codeword of length 24 (with Hamming weight 8), these are the "octads" in the binary Golay code. The entire Golay code can be obtained by repeatedly taking the symmetric differences of subsets, i. e. binary addition. An easier way to write down the Steiner system resp. the octads is the Miracle Octad Generator of R. T. Curtis, that uses a particular 1:1 correspondence between the 35 partitions of an 8 set into two 4 sets and the 35 partitions of the finite vector space into 4 planes. Nowadays often the compact approach of Conway's hexacode, that uses a 4×6 array of square cells, is used. Winning positions in the mathematical game of Mogul: a position in Mogul is a row of 24 coins. Each turn consists of flipping from one to seven coins such that the leftmost of the flipped coins goes from head to tail. The losing positions are those with no legal move. If heads are interpreted as 1 and tails as 0 then moving to a codeword from the extended binary Golay code guarantees it will be possible to force a win. A generator matrix for the binary Golay code is I A, where I is the 12×12 identity matrix, and A is the complement of the adjacency matrix of the icosahedron.

Миссии НАСА в глубоком космосе

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

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

Американские военные стандарты MIL STD 188, регламентирующие автоматическое установление связи в высокочастотных радиосистемах, предписывают использование расширенного (24,12) кода Голея для прямой коррекции ошибок. В системах цифрового кодированного шумоподавления (DCS, CDCSS) в двухсторонней радиосвязи применяется 23-битное кодовое слово Голея (23,12), способное обнаруживать и исправлять ошибки в 3 или менее битах.