Ikkilik Golay kodi - Binary Golay code

Kengaytirilgan ikkilik Golay kodi
BinaryGolayCode.svg
NomlanganMarcel J. E. Golay
Tasnifi
TuriLineer blok kodi
Blok uzunligi24
Xabar uzunligi12
Tezlik12/24 = 0.5
Masofa8
Alifbo hajmi2
Notation-kod
Zo'r ikkilik Golay kodi
NomlanganMarcel J. E. Golay
Tasnifi
TuriLineer blok kodi
Blok uzunligi23
Xabar uzunligi12
Tezlik12/23 ~ 0.522
Masofa7
Alifbo hajmi2
Notation-kod

Yilda matematika va elektron muhandislik, a ikkilik Golay kodi chiziqli turidir xatolarni tuzatuvchi kod ichida ishlatilgan raqamli aloqa. Ikkilik Golay kodi, bilan birga uchlamchi Golay kodi, nazariyasi bilan ayniqsa chuqur va qiziqarli aloqaga ega cheklangan sporadik guruhlar matematikada.[1] Ushbu kodlar sharafiga nomlangan Marcel J. E. Golay kimning 1949 yilgi qog'ozi[2] ularni tanishtirish deb nomlangan E. R. Berlekamp, kodlash nazariyasida "nashr etilgan eng yaxshi bitta sahifa".[3]

Golay kodlari bir-biriga chambarchas bog'liq ikkita. The kengaytirilgan ikkilik Golay kodi, G24 (ba'zan cheklangan guruh nazariyasida "Golay kodi" deb ham atashadi) 24 bitli so'zda 12 bit ma'lumotni har qanday 3 bitli xatolar tuzatilishi yoki har qanday 7 bitli xatolar aniqlanishi uchun kodlaydi. Boshqa, the mukammal ikkilik Golay kodi, G23, 23 uzunlikdagi kodli so'zlarga ega va bitta koordinatali pozitsiyani o'chirish orqali kengaytirilgan ikkilik Golay kodidan olinadi (aksincha, kengaytirilgan ikkilik Golay kodi mukammal ikkilik Golay kodidan a qo'shib olinadi parite bit ). Standart kodlash yozuvlarida kodlar [24, 12, 8] va [23, 12, 7] parametrlarga ega bo'lib, ular kod so'zlarining uzunligiga mos keladi, o'lchov kod va minimal Hamming masofasi navbati bilan ikkita kodli so'z o'rtasida.

Matematik ta'rif

Matematik nuqtai nazardan kengaytirilgan ikkilik Golay kodi G24 12 o'lchovdan iborat chiziqli pastki bo'shliq V bo'shliq V = F224 ning har qanday ikkita alohida elementi kabi 24 bitli so'zlar V kamida 8 koordinatada farqlanadi. V chiziqli kod deyiladi, chunki u vektor maydoni. Umuman olganda, V tarkibiga kiradi 4096 = 212 elementlar.

  • Ning elementlari V deyiladi kod so'zlari. Ularni 24 ta elementlar to'plamining pastki to'plamlari sifatida ham ta'riflash mumkin, bu erda qo'shimchalar pastki simmetrik farqni olish sifatida aniqlanadi.
  • Kengaytirilgan ikkilik Golay kodida barcha kod so'zlari mavjud Hamming og'irliklari 0, 8, 12, 16 yoki 24 raqamlari. 8 vaznli kod so'zlari deyiladi sakkizta va 12 ta vaznli kod so'zlari chaqiriladi dodecads.
  • Kodning sakkizligi G24 S elementlari (5,8,24) Shtayner tizimi. Lar bor 759 = 3 × 11 × 23 oktadalar va ularning 759 ta qo'shimchalari. Demak, bor 2576 = 24 × 7 × 23 dodecads.
  • Ikkita oktad ikkitomonlama vektorli tasvirda 0, 2 yoki 4 koordinatalarda kesishadi (umumiy 1 ga ega) (bu kichik to'plam tasvirida mumkin bo'lgan kesishish o'lchamlari). Oktad va dodecad 2, 4 yoki 6 koordinatalarda kesishadi.
  • Koordinatalarni qayta nomlashgacha, V noyobdir.

Ikkilik Golay kodi, G23 a mukammal kod. Ya'ni kod so'zlari atrofida radius uchi sharlari vektor makonining bo'linmasini tashkil qiladi. G23 12 o'lchovli subspace bo'shliq F223.

The avtomorfizm guruhi mukammal ikkitomonlama Golay kodi, G23, bo'ladi Mathieu guruhi . The avtomorfizm guruhi kengaytirilgan ikkilik Golay kodining Mathieu guruhi , buyurtma 210 × 33 × 5 × 7 × 11 × 23. oktadlarda va o'n ikki dekodda o'tish davri. Boshqa Matyo guruhlari quyidagicha uchraydi stabilizatorlar ning bir yoki bir nechta elementlaridan iborat V.

Qurilishlar

  • Leksikografik kod: Vektorlarni buyurtma qilish V leksikografik jihatdan (ya'ni, ularni imzo qo'yilmagan 24-bitli ikkilik tamsayılar sifatida izohlang va odatdagi tartibni oling). Bilan boshlanadi w0 = 0, aniqlang w1, w2, ..., w12 qoidaga ko'ra wn oldingi elementlarning barcha chiziqli kombinatsiyalaridan kamida sakkizta koordinatalar bilan farq qiladigan eng kichik butun son. Keyin V oralig'i sifatida belgilanishi mumkin w1, ..., w12.
  • Mathieu guruhi: Witt 1938 yilda kengaytirilgan ikkilik Golay kodini yaratish uchun ishlatilishi mumkin bo'lgan eng katta Mathieu guruhining qurilishini nashr etdi. [4]
  • Kvadrat qoldiq kodi: To'plamni ko'rib chiqing N kvadratik qoldiqlarning miqdori (23-mod). Bu 11 elementli kichik to'plam tsiklik guruh Z/23Z. Tarjimalarni ko'rib chiqing t+N ushbu ichki qism. Ularning har birini 12 elementli to'plamga tarjima qiling St adding elementini qo'shish orqali. Keyin ning asosiy elementlarini belgilash V 0, 1, 2, ..., 22, by, tomonidan V so'zlarning oralig'i sifatida aniqlanishi mumkin St barcha asosiy vektorlardan tashkil topgan so'z bilan birga. (Ajoyib kod ∞ ni qoldirib olinadi.)
  • Kabi tsiklik kod: Mukammal G23 kodini faktorizatsiya orqali tuzish mumkin ikkilik maydon ustida GF (2):
Bu tomonidan yaratilgan kod .[5] Kodni yaratish uchun 11 darajadagi har qanday kamaytirilmaydigan omillardan foydalanish mumkin.[6]
  • Dan boshlangan Turinning 1967 yildagi qurilishi, "Ikkilik Golay kodining oddiy konstruktsiyasi" Hamming kodi uzunligi 8 ga teng va 23-moddaning kvadratik qoldiqlaridan foydalanmaydi.[7]
  • Dan Shtayner tizimi S (5,8,24), 24 to'plamning 759 to'plamidan iborat. Agar har bir kichik to'plamning qo'llab-quvvatlanishini 0 uzunlikdagi 24-so'zli kod sifatida (Hamming og'irligi 8 bilan) izohlasa, bu ikkitomonlama Golay kodidagi "oktadalar". Golay kodini qayta-qayta olish orqali olish mumkin nosimmetrik farqlar kichik to'plamlar, ya'ni ikkilik qo'shimchalar. Shtayner tizimini yozishni osonroq usuli resp. oktadlar Miracle Octad Generator 8-to'plamning 35 ta bo'limi ikkita 4-to'plamga va cheklangan vektor makonining 35-bo'limi orasidagi ma'lum 1: 1-moslikdan foydalanadigan R. T. Kurtis. 4 samolyotga. [8] Hozirgi kunda ko'pincha 4 × 6 kvadrat kataklardan foydalanadigan Conway hexakodining ixcham usuli qo'llaniladi.
  • Da yutuqli pozitsiyalar matematik o'yin Mogul: Moguldagi mavqe - 24 tanga qatori. Har bir burilish birdan ettigacha tangalarni aylantirishdan iborat bo'lib, shunda tangalarning qolgan qismi boshdan quyruq tomon o'tadi. Yo'qotadigan pozitsiyalar - bu qonuniy harakatga ega bo'lmaganlar. Agar boshlar 1, quyruqlar 0 deb talqin qilinsa, kengaytirilgan ikkilik Golay kodidan kodli so'zga o'tish, g'alaba qozonishga majbur bo'lishini kafolatlaydi.
  • A generator matritsasi ikkilik Golay kodi uchun Men A., qayerda Men 12 × 12 identifikatsiya matritsasi va A ning to‘ldiruvchisi qo'shni matritsa ning ikosaedr.

Qulay vakolatxona

"Dan foydalanish qulayMiracle Octad Generator "formati, 4 qatordan iborat koordinatalar, 6 ta ustunlar. Qo'shish nosimmetrik farqni oladi. Barcha 6 ustunlar bir xil paritetga ega, bu yuqori qatorga teng.

6 ta ustunning uchta juft qo'shni qismga bo'linishi a ni tashkil qiladi trio. Bu 3 oktadli to'plamga bo'linish. Kichik guruh, proektsion maxsus chiziqli guruh PSL (2,7) x S3 trio kichik guruhining M24 asos yaratish uchun foydalidir. PSL (2,7) oktadlarni ichki qismida, parallel ravishda almashtiradi. S3 3 oktadni tanada buzadi.

Asos oktad T bilan boshlanadi:

0 1 1 1 1 1
1 0 0 0 0 0
1 0 0 0 0 0
1 0 0 0 0 0

va shunga o'xshash 5 ta oktad. Yig'indisi N ushbu 6 so'zning hammasi 1 ta so'zdan iborat. Kod so'ziga N qo'shilsa, uning to'ldiruvchisi hosil bo'ladi.

Griess (59-bet) yorliqdan foydalanadi:

∞ 0 |∞ 0 |∞ 0
3 2 |3 2 |3 2
5 1 |5 1 |5 1
6 4 |6 4 |6 4

PSL (2,7) tabiiy ravishda (0123456) va (0∞) (16) (23) (45) tomonidan hosil qilingan chiziqli kasr guruhidir. 7 tsikl $ T $ ga asos bo'lib, pastki fazoni beradi

0 1 1 0 1 0
0 0 0 0 0 0
0 1 0 1 0 1
1 1 0 0 0 0

va

0 1 1 0 1 0
0 1 0 1 0 1
1 1 0 0 0 0
0 0 0 0 0 0

Olingan 7 o'lchovli pastki bo'shliq, oxirgi 2 sekundni e'tiborsiz qoldirganda 3 o'lchovli bo'shliqqa ega.

V ning ushbu vakili uchun 12 ta kodli so'zni asosini olgan shunga o'xshash tuzilishdagi yana 4 ta kodli so'zlar mavjud.

W PSL (2,7) x S ostida nosimmetrik bo'lgan 4 o'lchamdagi kichik bo'shliqqa ega3, {0,3,5,6}, {0,1,4,6} va {0,1,2,5} kichik to'plamlardan tashkil topgan N va 3 dodecadlar tomonidan tashkil etilgan.

Golay kodlarining amaliy qo'llanilishi

NASA chuqur kosmik missiyalari

Xatolarni tuzatish ma'lumotlar uzatish uchun juda muhim edi Voyager 1 va 2 kosmik kemalari, ayniqsa, xotira cheklovlari ma'lumotlarning zudlik bilan zudlik bilan yuklanishini talab qilganligi sababli, ikkinchi imkoniyatni qoldirmaydi. Ning yuzlab rangli rasmlari Yupiter va Saturn ularning 1979, 1980 va 1981 yillarda uchib ketishlari cheklangan telekommunikatsiya o'tkazuvchanligi kengligida uzatiladi. Shuning uchun Golay kodlash ishlatilgan. Rangli tasvirni uzatish uchun ma'lumotlarning oq-qora tasvirlari kabi uch baravar ko'pligi kerak edi, shuning uchun Hadamard kodi qora va oq tasvirlarni uzatish uchun ishlatilgan Golay (24,12,8) kodiga o'tkazildi.[9] Ushbu Golay kodi faqat uch marta xatolarni to'g'rilaydi, ammo uni Mariner missiyasi paytida ishlatilgan Hadamard kodidan ancha yuqori ma'lumot tezligida uzatish mumkin.

Radioaloqa

The MIL-STD-188 Uchun Amerika harbiy standartlari avtomatik havolani o'rnatish yilda yuqori chastota radio tizimlari kengaytirilgan (24,12) Golay kodidan foydalanishni belgilaydi oldinga xatoni tuzatish.[10][11]

Shuningdek qarang

Adabiyotlar

  1. ^ Tompson 1983 yil
  2. ^ Golay, Marcel J. E. (1949). "Raqamli kodlash bo'yicha eslatmalar". Proc. IRE. 37: 657.CS1 maint: ref = harv (havola)
  3. ^ Berlekamp, ​​ER (1974), Kodlash nazariyasini rivojlantirishning asosiy hujjatlari, I.E.E.E. Matbuot, p. 4
  4. ^ Xansen, Robert Piter. "Katta Matye guruhlarining qurilishi va soddaligi". SJSU Scholar Works.
  5. ^ Rim 1996 yil, p. 324 7.4.3-misol
  6. ^ Pless 1998 yil, p. 114
  7. ^ Turin 1967 yil, VI bo'lim
  8. ^ Kullineyn, Stiven H. "Mo''jizaviy oktad generatori". Kvadrat va kubning yakuniy geometriyasi.
  9. ^ Cherowitzo, Bill. "Kosmosdagi kombinatorika - Mariner 9 telemetriya tizimi" (PDF). Kolorado universiteti Denver.
  10. ^ Jonson, Erik E. (1991-02-24). "MIL-STD-188-141A va FED-STD-1045 uchun samarali Golay kodek" (PDF). Olingan 2017-12-09.
  11. ^ "Harbiy standart: HF radiosi uchun avtomatlashtirilgan boshqaruv aplikasi uchun rejalashtirish va ko'rsatma standarti" (PDF). EverySpec: Texnik shartlar, standartlar, qo'llanmalar va Mil-Spec hujjatlari. 1994-04-04. Olingan 2017-12-09.

Manbalar