Бинарлық Голей коды: Қателерді түзету кодының математикалық сипаттамасы

Кіріспе

Сызықтық қателерді түзейтін кодтың түрі – математика және электроника салаларында, бинарлық Голай коды – цифрлық байланыстарда қолданылатын сызықтық қателерді түзейтін кодтың түрі. Бинарлық Голай коды, үштік Голай кодымен бірге, математикадағы шекті спорадикалық топтар теориясымен ерекше терең және қызықты байланысқа ие. Бұл кодтар Марсель Ж. Е. Голайдың құрметіне аталған, ал оның 1949 жылғы мақаласын Э. Р. Берлекамп «кодтау теориясындағы ең жақсы жарияланған бет» деп атады. Екі бір-бірімен тығыз байланысты бинарлық Голай коды бар. Кеңейтілген бинарлық Голай коды, G24 (кейде шекті топтар теориясында жай ғана «Голай коды» деп аталады), 24 биттік сөздерде 12 бит деректі кодтайды, осылайша кез келген 3 биттік қателерді түзетуге немесе кез келген 7 биттік қателерді анықтауға болады. Екіншісі – G23, толық бинарлық Голай коды, оның код сөздерінің ұзындығы 23-ке тең және кеңейтілген бинарлық Голай кодынан бір координаталық позицияны жою арқылы алынады (керісінше, кеңейтілген бинарлық Голай коды толық бинарлық Голай кодына паритет битін қосу арқылы алынады). Стандартты кодтау белгілемесінде кодтардың параметрлері [24, 12, 8] және [23, 12, 7] болып табылады, бұл сәйкесінше код сөздерінің ұзындығын, кодтың өлшемділігін және екі код сөзі арасындағы ең аз Хамминг қашықтығын көрсетеді.

Математикалық анықтамасы

Математикалық тұрғыдан алғанда, кеңейтілген бинарлық Голай коды G24 24 биттік сөздер кеңістігінің 12 өлшемді сызықтық W субкеңістігінен тұрады, сондықтан W-ның кез келген екі түрлі элементі кем дегенде 8 координатада ерекшеленеді. W – векторлық кеңістік болғандықтан, ол сызықтық код деп аталады. W-ның барлығы 1=4096 = 212 элементтен тұрады. W элементтері кодтық сөздер деп аталады. Оларды 24 элементтен тұратын жиынның ішкі жиыны ретінде де сипаттауға болады, онда қосу ішкі жиынның симметриялық айырмасын алу ретінде анықталады. Кеңейтілген бинарлық Голай кодта барлық кодтық сөздердің Хамминг салмағы 0, 8, 12, 16 немесе 24-ке тең болады. 8 салмақты кодтық сөздер октадалар, ал 12 салмақты кодтық сөздер додекадалар деп аталады. G24 кодының октадалары S(5,8,24) Штайнер жүйесінің элементтері болып табылады. 1=759 = 3 × 11 × 23 октада және олардың 759 толықтыруы бар. Одан 1=2576 = 24 × 7 × 23 додекада бар екендігі көрінеді. Екі октада бинарлық векторлық өрнекте 0, 2 немесе 4 координатада қиылысады (бұл ішкі жиын өрнектегі қиылысудың мүмкін мөлшері). Октада мен додекада 2, 4 немесе 6 координатада қиылысады. Координаттарды қайта белгілегенде W бірегей болады. G23 бинарлық коды – толық код. Яғни, кодтық сөздердің айналасындағы радиусы үшке тең сфералар векторлық кеңістікті бөліп жатады. G23 – F кеңістігінің 12 өлшемді субкеңістігі. Толық бинарлық Голай кодының автоморфизм тобы G23 (G23-ті өзгермейтін F координаталарының пермутациялары S23 тобының кіші тобы) – Матье тобы. Кеңейтілген бинарлық Голай кодының автоморфизм тобы – Матье тобы, 210 × 33 × 5 × 7 × 11 × 23 ретімен. Октадалар мен додекадалар бойынша транзитивті. Басқа Матье топтары W-ның бір немесе бірнеше элементтерінің тұрақтандырғыштары ретінде пайда болады. 24 салмақты бір сөз бар, ол 1 өлшемді инвариантты субкеңістік. Сондықтан, 2 элементі бар өрісте 11 өлшемді қайталанбайтын бейнелеуге ие. Сонымен қатар, бинарлық Голай коды 24 өлшемді кеңістіктің 12 өлшемді субкеңістігі болғандықтан, сонымен қатар 12 өлшемді үлестік кеңістікте әрекет етеді, оны бинарлық Голай кокоды деп атайды. Кокодтағы сөз 0, 1, 2, 3 немесе 4 ұзындығы бар сөзбен бірдей косетте болады. Соңғы жағдайда 6 (қосылмаған) кокод сөздері бірдей косетте жатыр. 2 элементі бар өрісте екінші 11 өлшемді бейнелеуді беретін, біркелкі салмақты кокод сөздерден тұратын 11 өлшемді инвариантты субкеңістік бар.

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 жылы кеңейтілген бинарлық Голай кодын құруға қолданылатын ең ірі Матье тобының құрылысын жариялады. Квадраттық қалдық емес код: 23-ке модуль бойынша квадраттық қалдық емес сандардың N жиынын қарастырыңыз. Бұл Z/23Z циклдік тобының 11 элементтен тұратын ішкі жиыны. Осы ішкі жиынның t+N түрлендірілімдерін қарастырыңыз. Әрбір түрлендірілімді ∞ элементін қосып, 12 элементтен тұратын St жиынына толықтырыңыз. Содан кейін V-дің негізгі элементтерін 0, 1, 2, ..., 22, ∞ деп белгілеп, W-ді St сөздерінің құрамы ретінде, сондай-ақ барлық негізгі векторлардан тұратын сөзбен бірге анықтауға болады. (Толық код ∞-ны алып тастау арқылы алынады.) Циклдік код ретінде: Толық G23 кодын бинарлық өріс GF(2)-дегі факторлау арқылы құруға болады: Кодты құру үшін 11-ші дәрежелі екі азайғысыз фактордың кез келгенін пайдалануға болады. Туриннің 1967 жылғы «Бинарлық Голай кодын қарапайым құру» жұмысы, ол 8 ұзындығындағы Хамминг кодын бастапқы нүкте ретіне алады және 23 модуль бойынша квадраттық қалдықтарды қолданбайды. Штайнер жүйесінен S(5,8,24), 24 элементтен тұратын жиынның 759 ішкі жиынынан тұрады. Егер әрбір ішкі жиынның қолдауы 24 ұзындығындағы (Хамминг салмағы 8) 0-1 код сөзі ретінде қарастырылса, онда бұл бинарлық Голай кодын құрайтын «октадтар» болады. Голай кодың толық жиынтығын ішкі жиындардың симметриялық айырмасын қайталап алу арқылы алуға болады, яғни бинарлық қосу арқылы. Штайнер жүйесін немесе октадтарды жазудың оңай жолы – Р.Т. Кертистің «Керемет октад генераторы», ол 8 элементтен тұратын жиынның 35 бөлінісі мен шекті векторлық кеңістіктің 35 бөлінісі арасындағы 1:1 сәйкестікті пайдаланады. Бүгінде көбінесе Конвейдің гексакодының ықшам тәсілі қолданылады, ол 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.

NASA ғарышқа ұшырауы

Қателерді түзету Voyager 1 және 2 ғарыш кемелерінде деректерді беру үшін маңызды болды, әсіресе жад шектеулері деректерді дерлік бірден түсіруді талап етіп, екінші мүмкіндік болмады. 1979, 1980 және 1981 жылдарғы Юпитер мен Сатурнның жүздеген түсті суреттері шектеулі телекоммуникациялық өткізу қабілеті арқылы жіберілді. Түсті суреттерді беру үшін қара-ақ суреттерге қарағанда үш есе көп дерек қажет болды, сондықтан қара-ақ Маринер суреттерін беру үшін қолданылған 7 қате түзетуші Рид-Мюллер коді, жоғарырақ дерек жылдамдығына ие Голай (24,12,8) кодімен ауыстырылды.

Радиобайланыс

MIL STD 188 жоғары жиілікті радио жүйелерінде автоматты байланыс орнатуға арналған американдық әскери стандарттар алға қателерді түзету үшін кеңейтілген (24,12) Голай кодын пайдалануды белгілейді. Екі тарапты радиобайланыста цифрлық кодталған скваш (DCS, CDCSS) жүйесі 23 биттік Голай (23,12) кодты сөзді қолданады, ол 3 немесе одан аз бит қателерді анықтау және түзету мүмкіндігіне ие.