BCH kodi - BCH code - Wikipedia

Yilda kodlash nazariyasi, BCH kodlari yoki Bose-Chaudhuri-Hocquenghem kodlari sinfini tashkil qilish tsiklik xatolarni tuzatuvchi kodlar yordamida qurilgan polinomlar ustidan cheklangan maydon (shuningdek, deyiladi Galois maydoni ). BCH kodlari 1959 yilda frantsuz matematikasi tomonidan ixtiro qilingan Aleksis Xokvenxem va mustaqil ravishda 1960 yilda Raj Bose va D. K. Rey-Chaudxuri.[1][2][3] Ism Bose-Chaudhuri-Hocquenghem (va qisqartma BCH) ixtirochilar familiyasining bosh harflaridan kelib chiqadi (adashib Ray-Chaudhuri misolida).

BCH kodlarining asosiy xususiyatlaridan biri shundan iboratki, kodni loyihalash paytida kod tomonidan tuzatilishi mumkin bo'lgan belgi xatolar soni ustidan aniq nazorat mavjud. Xususan, bir nechta bitli xatolarni tuzatadigan ikkilik BCH kodlarini loyihalashtirish mumkin. BCH kodlarining yana bir afzalligi - ularni dekodlashning osonligi, ya'ni algebraik usuli sifatida tanilgan sindromni dekodlash. Bu kichik kuchga ega bo'lmagan elektron apparatlardan foydalanib, ushbu kodlar uchun dekoderning dizaynini soddalashtiradi.

BCH kodlari sun'iy yo'ldosh aloqasi,[4] ixcham disk futbolchilar, DVD disklari, disk drayverlari, qattiq holatdagi drayvlar,[5] kvantga chidamli kriptografiya[6] va ikki o'lchovli shtrix-kodlar.

Ta'rif va illyustratsiya

Ibtidoiy tor ma'noda BCH kodlari

Berilgan asosiy raqam q va asosiy kuch qm musbat butun sonlar bilan m va d shu kabi dqm − 1, ibtidoiy tor ma'noda BCH kodi cheklangan maydon (yoki Galois maydoni) GF (q) kod uzunligi bilan n = qm − 1 va masofa kamida d quyidagi usul bilan qurilgan.

Ruxsat bering a bo'lishi a ibtidoiy element ning GF (qm).Har qanday musbat tamsayı uchun men, ruxsat bering mmen(x) bo'lishi minimal polinom koeffitsientlari bilan GF (q) ning amen.The generator polinom ning BCH kodi eng kichik umumiy g(x) = lcm (m1(x),…,md − 1(x)).Bu narsa ko'rinib turibdi g(x) koeffitsientlari bo'lgan polinomdir GF (q) va ajratadi xn − 1.Shuning uchun, tomonidan belgilangan polinom kodi g(x) tsiklik koddir.

Misol

Ruxsat bering q = 2 va m = 4 (shuning uchun n = 15). Ning turli xil qiymatlarini ko'rib chiqamiz d. Uchun GF (16) = GF (2)4) polinomga asoslangan x4 + x + 1 ibtidoiy ildiz bilan a = x+0 minimal polinomlar mavjud mmen(x) koeffitsientlari bilan GF (2) qoniqarli

Ning o'n to'rt kuchining minimal polinomlari a bor

Bilan BCH kodi generator polinomiga ega

Bu minimal Hamming masofasi kamida 3 va bitta xatoni tuzatadi. Jeneratör polinomasi 4-darajaga ega bo'lganligi sababli, ushbu kodda 11 ta ma'lumotlar biti va 4 ta nazorat summasi mavjud.

Bilan BCH kodi generator polinomiga ega

Bu kamida Hamming masofasi kamida 5 ga teng va ikkita xatoni tuzatadi. Jeneratör polinomasi 8-darajaga ega bo'lganligi sababli, ushbu kod 7 ta ma'lumot biti va 8 ta nazorat sumiga ega.

Bilan BCH kodi generator polinomiga ega

U kamida 7 ta Hamming masofasiga ega va uchta xatolikni tuzatadi. Jeneratör polinomasi 10 daraja bo'lganligi sababli, ushbu kod 5 ta ma'lumot biti va 10 ta nazorat summasiga ega. (Ushbu maxsus generator polinomining haqiqiy shaklda qo'llanilishi mavjud QR kod.)

Bilan BCH kodi va undan yuqori generator polinomiga ega

Ushbu kod Hamming minimal masofasiga 15 ega va 7 ta xatolikni to'g'irlaydi. Unda 1 ta ma'lumot biti va 14 ta nazorat summasi mavjud. Aslida, ushbu kodda faqat ikkita kod so'z mavjud: 000000000000000 va 111111111111111.

Umumiy BCH kodlari

Umumiy BCH kodlari ibtidoiy tor ma'noli BCH kodlaridan ikki jihatdan farq qiladi.

Birinchidan, bu talab ning ibtidoiy elementi bo'ling bo'shashishi mumkin. Ushbu talabni yumshatib, kod uzunligi o'zgaradi ga The buyurtma elementning

Ikkinchidan, generator polinomining ketma-ket ildizlari ishga tushishi mumkin o'rniga

Ta'rif. Cheklangan maydonni aniqlang qayerda asosiy kuchdir. Musbat butun sonlarni tanlang shu kabi va bo'ladi multiplikativ tartib ning modul

Oldingi kabi, ruxsat bering bo'lishi a ibtidoiy birlikning ildizi yilda va ruxsat bering bo'lishi minimal polinom ustida ning Barcha uchun BCH kodining generator polinomini quyidagicha aniqlanadi eng kichik umumiy

Eslatma: agar soddalashtirilgan ta'rifdagi kabi, keyin 1 ga teng, va tartibi modul bu Shuning uchun soddalashtirilgan ta'rif haqiqatan ham umumiyning alohida holatidir.

Maxsus holatlar

  • Bilan BCH kodi deyiladi a tor ma'noda BCH kodi.
  • Bilan BCH kodi deyiladi ibtidoiy.

Jeneratör polinom BCH kodining koeffitsientlari bor Umuman olganda, tsiklik kod tugadi bilan chunki generator polinomiga BCH kodi deyiladi BCH kodi tugadi va generator polinom ning ketma-ket vakolatlari bilan chunki ildizlar bir turidir Reed - Sulaymon kodi bu erda dekoder (sindromlar) alifbosi kanal (ma'lumotlar va generator polinomlari) alifbosi bilan bir xil, barcha elementlari .[7] Reed Solomon kodining boshqa turi an asl ko'rinishi Reed Sulaymon kodi bu BCH kodi emas.

Xususiyatlari

BCH kodining generator polinomasi ko'pi bilan darajaga ega . Bundan tashqari, agar va , generator polinomasi ko'pi bilan darajaga ega .

Isbot

Har bir minimal polinom eng yuqori darajaga ega . Shuning uchun, ning eng kichik umumiy ko'paytmasi ularning ko'pi eng yuqori darajaga ega . Bundan tashqari, agar keyin Barcha uchun . Shuning uchun, ko'pi bilan eng kichik umumiy ko'paytmasi minimal polinomlar toq indekslar uchun har bir daraja .

BCH kodi kamida Hamming masofasiga ega .

Isbot

Aytaylik dan kam bo'lgan kodli so'z nolga teng bo'lmagan shartlar. Keyin

Buni eslang ning ildizlari shu sababli . Bu shuni anglatadiki har biri uchun quyidagi tenglamalarni qondiring :

Matritsa shaklida bizda mavjud

Ushbu matritsaning determinanti tengdir

Matritsa a bo'lishi ko'rinib turibdi Vandermond matritsasi va uning aniqlovchisi

bu nolga teng emas. Shuning uchun bundan kelib chiqadi shu sababli

BCH kodi davriydir.

Isbot

Uzunlik polinom kodi faqat uning generatori polinom bo'linadigan bo'lsa, tsiklik bo'ladi Beri bu ildizlar bilan minimal polinom har birini tekshirish kifoya ning ildizi Bu darhol haqiqatdan kelib chiqadi , ta'rifi bo'yicha, an birlikning ildizi.

Kodlash

Jeneratör polinomining ko'pligi bo'lgan har qanday polinom haqiqiy BCH kod so'zi bo'lganligi sababli, BCH kodlash faqat generatorni omil sifatida topadigan ba'zi bir polinomlarni topish jarayonidir.

BCH kodining o'zi ko'pburchak koeffitsientlarining ma'nosi to'g'risida ko'rsatma bermaydi; kontseptual ravishda, BCH dekodlash algoritmining yagona maqsadi - qabul qilingan kod so'ziga minimal Hamming masofasi bilan to'g'ri kod so'zini topishdir. Shuning uchun, BCH kodi yoki sistematik kod yoki yo'q, bu amalga oshiruvchi qanday qilib xabarni kodlangan polinomga kiritishni tanlashiga bog'liq.

Tizimli bo'lmagan kodlash: Xabar omil sifatida

Generatorning ko'paytmasi bo'lgan polinomni topishning eng to'g'ri usuli bu ba'zi bir ixtiyoriy polinomlar va generatorlarning ko'paytmasini hisoblashdir. Bunday holda, ixtiyoriy polinomni koeffitsient sifatida xabarning belgilaridan foydalanib tanlash mumkin.

Masalan, generator polinomini ko'rib chiqing , tomonidan ishlatiladigan (31, 21) ikkilik BCH kodida foydalanish uchun tanlangan POCSAG va boshqalar. 21-bitli xabarni kodlash uchun {101101110111101111101}, avval uni ko'pburchak sifatida ifodalaymiz :

Keyin, hisoblang (shuningdek tugadi) ):

Shunday qilib, uzatilgan kod so'zi {1100111010010111101011101110101}.

Qabul qilgich ushbu bitlardan koeffitsient sifatida foydalanishi mumkin va to'g'ri kodli so'zni ta'minlash uchun xatolarni tuzatgandan so'ng, qayta hisoblashi mumkin

Tizimli kodlash: Xabar prefiks sifatida

Tizimli kod - bu kod kodning ichida biron bir joyda so'zma-so'z paydo bo'ladigan kod. Shuning uchun BCHni sistematik kodlash avval kod polinomiga xabar polinomini kiritishni, so'ngra qolgan (xabar bo'lmagan) atamalarning koeffitsientlarini sozlashni o'z ichiga oladi. ga bo'linadi .

Ushbu kodlash usuli dividenddan qoldiqni olib tashlash, bo'linuvchining ko'paytmasiga olib kelishi faktidan foydalanadi. Shuning uchun, agar biz xabar polinomini olsak oldingi kabi va uni ko'paytiring (xabarni qolgan qismini "siljitish" uchun), undan keyin foydalanishimiz mumkin Evklid bo'linishi hosil bo'lish uchun polinomlarning soni:

Mana, biz buni ko'rib turibmiz to'g'ri kod so'zi. Sifatida har doim darajadan kam (bu daraja ), biz uni xavfsiz ravishda olib tashlashimiz mumkin har qanday xabar koeffitsientini o'zgartirmasdan, shuning uchun bizda mavjud kabi

Ustida (ya'ni ikkilik BCH kodlari bilan), bu jarayonni qo'shib qo'yishdan farq qilmaydi ishdan bo'shatishni tekshirish va agar sistemali ikkilik BCH kodi faqat xatolarni aniqlash maqsadida ishlatilsa, biz BCH kodlari shunchaki umumlashtirish ekanligini ko'ramiz tsiklli ortiqcha tekshiruvlar matematikasi.

Tizimli kodlashning afzalligi shundaki, qabul qiluvchining hammasini birinchisidan keyin tashlab, asl xabarni tiklashi mumkin xatolarni tuzatgandan so'ng, koeffitsientlar.

Kod hal qilish

BCH kodlarini dekodlash uchun ko'plab algoritmlar mavjud. Eng keng tarqalganlari ushbu umumiy tasavvurga amal qiladi:

  1. Sindromlarni hisoblang sj qabul qilingan vektor uchun
  2. Xatolar sonini aniqlang t va xatolarni aniqlovchi polinom Λ (x) sindromlardan
  3. Xato joylarini topish uchun xato joylashuvi polinomining ildizlarini hisoblang Xmen
  4. Xato qiymatlarini hisoblang Ymen o'sha xato joylarda
  5. Xatolarni tuzating

Ushbu qadamlardan ba'zilari davomida dekodlash algoritmi qabul qilingan vektor juda ko'p xatolarga ega ekanligini va ularni tuzatib bo'lmasligini aniqlashi mumkin. Masalan, tegishli qiymat bo'lsa t topilmadi, keyin tuzatish muvaffaqiyatsiz tugadi. Qisqartirilgan (ibtidoiy emas) kodda xato joylashuvi doiradan tashqarida bo'lishi mumkin. Agar qabul qilingan vektorda kod tuzatgandan ko'ra ko'proq xatolar bo'lsa, dekoder bilmagan holda yuborilgan xabar emas, balki ko'rinadigan haqiqiy xabarni chiqarishi mumkin.

Sindromlarni hisoblang

Qabul qilingan vektor to'g'ri kod so'zning yig'indisi va noma'lum xato vektori Sindrom qiymatlari hisobga olingan holda hosil bo'ladi polinom sifatida va uni baholash Shunday qilib sindromlar[8]

uchun ga

Beri ning nollari ulardan ko'p sonli, Shuning uchun sindrom qiymatlarini o'rganish xato vektorini ajratib turadi, shuning uchun uni hal qilishni boshlash mumkin.

Agar xato bo'lmasa, Barcha uchun Agar sindromlarning barchasi nolga teng bo'lsa, u holda dekodlash amalga oshiriladi.

Xato joylashuvi polinomini hisoblang

Agar nol bo'lmagan sindromlar bo'lsa, unda xatolar mavjud. Dekoder qancha xatolarni va bu xatolarning joylashishini aniqlashi kerak.

Agar bitta xato bo'lsa, buni quyidagicha yozing qayerda xatoning joylashuvi va uning kattaligi. Keyin birinchi ikkita sindrom

shuning uchun ular birgalikda hisoblashimizga imkon beradi haqida ba'zi ma'lumotlarni taqdim eting (Rid-Sulaymon kodlari bo'yicha buni to'liq aniqlash).

Agar ikkita yoki undan ko'p xato bo'lsa,

Natijada paydo bo'lgan sindromlarni noma'lum narsalar uchun qanday hal qilishni boshlash darhol aniq emas va

Birinchi qadam hisoblash sindromlariga mos keladigan va minimal darajadagi topishdir lokator polinom:

Ushbu vazifaning ikkita mashhur algoritmi:

  1. Peterson-Gorenshteyn-Zierler algoritmi
  2. Berlekamp - Massey algoritmi

Peterson-Gorenshteyn-Zierler algoritmi

Peterson algoritmi - bu BCH kodlashning umumlashtirilgan protsedurasining 2-bosqichi. Peterson algoritmi xatolarni aniqlash polinomlari koeffitsientlarini hisoblash uchun ishlatiladi polinomning

Endi Peterson-Gorenshteyn-Zierler algoritmining protsedurasi.[9] Bizda kamida 2 bor deb kutingt sindromlar sv, …, sv+2t−1. Ruxsat bering v = t.

  1. Yaratish orqali boshlang sindrom qiymatlari bo'lgan elementlar bilan matritsa
  2. A hosil qiling elementlar bilan vektor
  3. Ruxsat bering tomonidan berilgan noma'lum polinom koeffitsientlarini belgilang
  4. Matritsa tenglamasini tuzing
  5. Agar matritsaning determinanti bo'lsa nolga teng, demak biz aslida ushbu matritsaning teskari tomonini topamiz va noma'lum qiymatlarni echamiz qiymatlar.
  6. Agar keyin ergashing
           agar        keyin Peterson protsedurasini to'xtatish uchun bo'sh xatolarni aniqlovchi polinomni e'lon qiling. oxiri o'rnatilgan 
    Peterson dekodlash boshidan kichikroq qilib davom eting
  7. Sizda qadriyatlarga ega bo'lgandan keyin , sizda xatolarni aniqlovchi polinom mavjud.
  8. Peterson protsedurasini to'xtating.

Faktor xatosini aniqlovchi polinom

Endi sizda polinom, uning ildizlarini shaklda topish mumkin qo'pol kuch bilan, masalan Chien qidiruvi algoritm. Ibtidoiy elementning eksponent kuchlari qabul qilingan so'zda xatolar yuzaga keladigan pozitsiyalarni beradi; shuning uchun "xatolarni aniqlovchi" polinom nomi.

Λ ning nollari (x) bor amen1, …, amenv.

Xato qiymatlarini hisoblang

Xato joylari ma'lum bo'lgach, keyingi qadam ushbu joylarda xato qiymatlarini aniqlashdir. Keyinchalik xato kodlari asl kod so'zini tiklash uchun o'sha joylarda olingan qiymatlarni tuzatish uchun ishlatiladi.

Ikkilik BCH uchun (barcha belgilar o'qilishi mumkin) bu ahamiyatsiz; qabul qilingan so'z uchun bitlarni ushbu pozitsiyalarda aylantiring va bizda kod so'zi tuzatilgan. Umuman olganda, xato og'irliklari chiziqli tizimni echish orqali aniqlanishi mumkin

Forney algoritmi

Biroq, deb nomlanuvchi yanada samarali usul mavjud Forney algoritmi.

Ruxsat bering

Va xatolarni baholovchi polinom[10]

Nihoyat:

qayerda

Agar sindromlarni xato pozitsiyasi bilan izohlash mumkin bo'lsa, bu faqat pozitsiyalarda nolga teng bo'lishi mumkin , keyin xato qiymatlari

Tor ma'noda BCH kodlari uchun, v = 1, shuning uchun ifoda soddalashtiriladi:

Forney algoritmini hisoblash haqida tushuntirish

Bunga asoslanadi Lagranj interpolatsiyasi va texnikasi ishlab chiqarish funktsiyalari.

Ko'rib chiqing va soddalik uchun faraz qiling uchun va uchun Keyin

Biz noma'lum narsalarni hisoblamoqchimiz ni olib tashlash orqali kontekstni soddalashtirishimiz mumkin shartlar. Bu xatolarni baholovchi polinomga olib keladi

Rahmat bizda ... bor

Rahmat (Lagrange interpolatsiya hiyla-nayrang) yig'indisi faqat bitta yig'indiga aylanadi

Olish uchun; olmoq biz faqat mahsulotdan qutulishimiz kerak. Biz mahsulotni to'g'ridan-to'g'ri allaqachon hisoblangan ildizlardan hisoblashimiz mumkin ning ammo biz oddiyroq shakldan foydalanishimiz mumkin edi.

Sifatida rasmiy lotin

yana bitta chaqiruvni olamiz

Va nihoyat

Ning formulasini hisoblashda ushbu formula foydalidir shakl

hosildorlik:

qayerda

Kengaytirilgan Evklid algoritmi asosida dekodlash

Ikkala polinomni va xatolarni aniqlovchi polinomni topishning muqobil jarayoni Yasuo Sugiyamaning moslashtirishga asoslangan Kengaytirilgan evklid algoritmi.[11] Algoritmga o'qib bo'lmaydigan belgilarni tuzatish ham osonlikcha kiritilishi mumkin.

Ruxsat bering o'qilmaydigan belgilar pozitsiyalari bo'ling. Ulardan biri ushbu pozitsiyalarni lokalizatsiya qiladigan polinomni yaratadi O'qilmaydigan holatdagi qiymatlarni 0 ga qo'ying va sindromlarni hisoblang.

Forney formulasi uchun biz allaqachon aniqlaganimizdek

Polinomlarning eng kam umumiy bo'luvchisini topish uchun kengaytirilgan evklid algoritmini ishga tushiramiz va Maqsad eng kichik umumiy bo'luvchini topish emas, balki polinom eng ko'p daraja va polinomlar shu kabi Past daraja kafolatlar, bu kengaytirilgan qondiradi (tomonidan ) uchun shartlarni belgilash

Ta'riflash va foydalanish joyida Fourney formulasida bizga xato qiymatlari beriladi.

Algoritmning asosiy afzalligi shundaki, u shu bilan birga hisoblab chiqadi Forney formulasida talab qilinadi.

Kod hal qilish jarayonini tushuntirish

Maqsad - qabul qilinadigan so'zdan o'qiladigan pozitsiyalar bo'yicha imkon qadar minimal darajada farq qiladigan kod so'zini topish. Qabul qilingan so'zni eng yaqin kod so'zi va xato so'zining yig'indisi sifatida ifodalashda biz o'qiladigan pozitsiyalar bo'yicha nolga teng bo'lmagan minimal sonli xato so'zni topishga harakat qilamiz. Sindrom xato so'zini shart bo'yicha cheklaydi

Ushbu shartlarni alohida yozishimiz yoki polinom yaratishimiz mumkin edi

va kuchlar yaqinidagi koeffitsientlarni taqqoslash ga

Deylik, pozitsiyada o'qilmagan xat bo'lsa sindromlar to'plamini almashtirishimiz mumkin sindromlar to'plami bo'yicha tenglama bilan belgilanadi Dastlabki to'plam bo'yicha barcha cheklovlar xato so'zi bilan aytaylik sindromlarning tutilishi, nisbatan

Yangi sindromlar to'plami xato vektorini cheklaydi

xuddi shu tarzda dastlabki sindromlar to'plami xato vektorini cheklab qo'ydi Koordinatadan tashqari bizda qayerda an nolga teng, agar bo'lsa Xato pozitsiyalarini aniqlash uchun biz sindromlar to'plamini o'xshash tarzda barcha o'qib bo'lmaydigan belgilarni aks ettirishimiz mumkin. Bu sindromlar to'plamini qisqartiradi

Polinomial formulada sindromlarni almashtirish o'rnatiladi sindromlar bo'yicha olib keladi

Shuning uchun,

O'zgartirilgandan so'ng tomonidan , kuchga yaqin koeffitsientlar uchun tenglama kerak bo'ladi

Berilgan pozitsiyalar ta'sirini yo'q qilish nuqtai nazaridan xato pozitsiyalarini qidirishni o'qish mumkin bo'lmagan belgilar kabi ko'rib chiqish mumkin. Agar topsak ularning ta'sirini bartaraf etish, barcha nollardan iborat bo'lgan sindromlar to'plamini olishga olib keladigan pozitsiyalar, chunki bu koordinatalarda xatolar mavjud bo'lgan vektor mavjud. bu koordinatalarning ta'sirini yo'q qiladigan polinomni bildiradi, biz olamiz

Evklid algoritmida biz ko'pi bilan tuzatishga harakat qilamiz xatolar (o'qilishi mumkin bo'lgan holatlarda), chunki xatolarni kattaroq hisoblashi bilan qabul qilingan so'zdan bir xil masofada ko'proq kodli so'zlar bo'lishi mumkin. Shuning uchun, uchun Biz qidirmoqdamiz, tenglama kuchdan yaqin koeffitsientlarni bajarishi kerak

Forney formulasida, bir xil natijani beradigan skalar bilan ko'paytirilishi mumkin.

Evklid algoritmi topishi mumkin darajadan yuqori uning darajasiga teng bo'lgan turli xil ildizlarning soni, bu erda Furney formulasi barcha ildizlardagi xatolarni tuzatishi mumkin edi, baribir bunday ko'p xatolarni tuzatish xavfli bo'lishi mumkin (ayniqsa, olingan so'zga boshqa cheklovlarsiz). Odatda olgandan keyin yuqori darajadagi xatolarni tuzatmaslikka qaror qilamiz. Ishda tuzatish muvaffaqiyatsiz bo'lishi mumkin ko'p sonli ildizlarga ega yoki ildizlar soni uning darajasidan kichikroq. Failni uzatilgan alifbodan tashqarida qaytaradigan xatoni qaytaradigan Forni formulasi ham aniqlay olmadi.

Xatolarni tuzating

Xato qiymatlari va xato joyidan foydalanib, xatolarni to'g'irlang va xato joylarida xato qiymatlarini olib tashlab, tuzatilgan kod vektorini yarating.

Kodlarni dekodlash

Ikkilik kodni o'qib bo'lmaydigan belgilarsiz dekodlash

GF (2) da BCH kodini ko'rib chiqing4) bilan va . (Bu ishlatiladi QR kodlari.) Xabar uzatilsin [1 1 0 1 1] yoki polinom belgilarida, "Tekshirish summasi" belgilari bo'linish yo'li bilan hisoblanadi tomonidan va qolganini olib, natijada yoki [1 0 0 0 0 1 0 1 0 0]. Ular xabarga qo'shilgan, shuning uchun uzatilgan kod so'z [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Endi tasavvur qiling, uzatishda ikkita bit-xato mavjud, shuning uchun olingan kod so'z [1 0 0 1 1 1 0 0 0 1 1 0 1 0 0]. Polinom belgilarida:

Xatolarni tuzatish uchun avval sindromlarni hisoblang. Qabul qilish bizda ... bor va Keyingi kengaytirilgan matritsani qatorlarni kamaytirish orqali Peterson protsedurasini qo'llang.

Nolinchi qator tufayli, S3×3 bitta, bu ajablanarli emas, chunki kod so'ziga faqat ikkita xato kiritilgan, ammo matritsaning yuqori chap burchagi xuddi shunday [S2×2 | C2×1], bu esa echimni keltirib chiqaradi Olingan xatolarni aniqlovchi polinom nolga ega bo'lgan va Ning eksponentlari xato joylariga mos keladi.Bu misolda xato qiymatlarini hisoblashning hojati yo'q, chunki mumkin bo'lgan yagona qiymat 1 ga teng.

O'qib bo'lmaydigan belgilar bilan dekodlash

Xuddi shu stsenariyni taxmin qilaylik, lekin olingan so'zda ikkita o'qib bo'lmaydigan belgi bor [1 0 0 ? 1 1 ? 0 0 1 1 0 1 0 0]. Biz o'qilmaydigan belgilarni ularning pozitsiyalarini aks ettiruvchi polinomni yaratishda nolga almashtiramiz Biz sindromlarni hisoblaymiz va (GF da mustaqil bo'lgan log yozuvlaridan foydalanish (24) izomorfizmlar. Hisoblashni tekshirish uchun biz avvalgi misolda ishlatilgan qo'shimchani taqdim etishimiz mumkin. Ning kuchlarining o'n oltinchi tavsifi ketma-ket 1,2,4,8,3,6, C, B, 5, A, 7, E, F, D, 9 ga qo'shilib bitorli xor asosida tuzilgan.)

Sindrom polinomini tuzamiz

hisoblash

Kengaytirilgan Evklid algoritmini ishga tushiring:

We have reached polynomial of degree at most 3, and as

biz olamiz

Shuning uchun,

Ruxsat bering Don't worry that Find by brute force a root of Ildizlari va (after finding for example we can divide by corresponding monom and the root of resulting monom could be found easily).

Ruxsat bering

Let us look for error values using formula

qayerda are roots of Biz olamiz

Fact, that should not be surprising.

Corrected code is therefore [ 1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Decoding with unreadable characters with a small number of errors

Let us show the algorithm behaviour for the case with small number of errors. Let the received word is [ 1 0 0 ? 1 1 ? 0 0 0 1 0 1 0 0 ].

Again, replace the unreadable characters by zeros while creating the polynomial reflecting their positions Compute the syndromes va Create syndrome polynomial

Let us run the extended Euclidean algorithm:

We have reached polynomial of degree at most 3, and as

biz olamiz

Shuning uchun,

Ruxsat bering Xavotir olmang Ning ildizi bu

Ruxsat bering

Formuladan foydalanib xato qiymatlarini qidiramiz qayerda polinomning ildizlari

Biz olamiz

Haqiqat ajablanarli bo'lmasligi kerak.

Shuning uchun tuzatilgan kod [1 1 0 1 1 1 0 0 0 0 1 0 1 0 0].

Iqtiboslar

  1. ^ Reed & Chen 1999 yil, p. 189
  2. ^ Xokvenhem 1959 yil
  3. ^ Bose & Ray-Chaudhuri 1960 yil
  4. ^ "Phobos Lander kodlash tizimi: dasturiy ta'minot va tahlil" (PDF). Olingan 25 fevral 2012.
  5. ^ "Sandforce SF-2500/2600 mahsulot haqida qisqacha ma'lumot". Olingan 25 fevral 2012.
  6. ^ http://pqc-hqc.org/doc/hqc-specification_2020-05-29.pdf
  7. ^ Gill nd., p. 3
  8. ^ Lidl va Pilz 1999 yil, p. 229
  9. ^ Gorenshteyn, Peterson va Zierler 1960 yil
  10. ^ Gill nd., p. 47
  11. ^ Yasuo Sugiyama, Masao Kasaxara, Shigeichi Xirasava va Toshixiko Namekava. Goppa kodlarini dekodlash uchun asosiy tenglamani echish usuli. Axborot va nazorat, 27: 87–99, 1975.

Adabiyotlar

Birlamchi manbalar

Ikkilamchi manbalar

Qo'shimcha o'qish