Burst xatolarni tuzatuvchi kod - Burst error-correcting code - Wikipedia

Yilda kodlash nazariyasi, xatolarni tuzatuvchi kodlar tuzatish usullarini qo'llang portlash xatolari, bu bitlar bir-biridan mustaqil ravishda emas, balki ketma-ket ko'plab bitlarda yuzaga keladigan xatolar.

Ko'p kodlar tuzatish uchun mo'ljallangan tasodifiy xatolar. Ba'zida kanallar qisqa vaqt ichida lokalizatsiya qilingan xatolarni keltirib chiqarishi mumkin. Bunday xatolar portlashda (chaqiriladi) sodir bo'ladi portlash xatolari ) chunki ular ketma-ket bitlarda uchraydi. Portlash xatolarining misollarini saqlash vositalarida juda ko'p topish mumkin. Ushbu xatolar simsiz kanallarda diskda tirnalish yoki chaqmoq urishi kabi jismoniy shikastlanishlarga bog'liq bo'lishi mumkin. Ular mustaqil emas; ular fazoviy kontsentratsiyaga moyil. Agar bitta bitda xato bo'lsa, ehtimol qo'shni bitlar ham buzilgan bo'lishi mumkin. Tasodifiy xatolarni tuzatish uchun ishlatiladigan usullar portlash xatolarini tuzatish uchun samarasiz.

Ta'riflar

Uzunlik 5

Uzunlik portlashi [1]

Kod so'zini ayting uzatiladi va u quyidagicha qabul qilinadi Keyin, xato vektori uzunlik portlashi deyiladi ning nolga teng bo'lmagan tarkibiy qismlari bo'lsa cheklangan ketma-ket komponentlar. Masalan, uzunlikning yorilishi

Ushbu ta'rif portlash xatosi nima ekanligini tavsiflash uchun etarli bo'lsa-da, portlash xatosini tuzatish uchun ishlab chiqarilgan vositalarning aksariyati tsiklik kodlarga tayanadi. Bu bizning keyingi ta'rifimizga turtki beradi.

Uzunlikning tsiklik portlashi [1]

Xato vektori uzunlikning tsiklik yorilish xatosi deyiladi agar uning nolga teng bo'lmagan tarkibiy qismlari cheklangan bo'lsa ketma-ket ketma-ket komponentlar. Masalan, ilgari ko'rib chiqilgan xato vektori , uzunlikning tsiklik yorilishi , chunki biz xatoni pozitsiyadan boshlaymiz va pozitsiyada tugaydi . Indekslarga e'tibor bering -baza asosida, ya'ni birinchi element holatidadir .

Ushbu maqolaning qolgan qismida, agar boshqacha ko'rsatilmagan bo'lsa, biz portlash atamasini tsiklli portlashga nisbatan ishlatamiz.

Burst tavsifi

Portlash xatosining ixcham ta'rifiga ega bo'lish ko'pincha foydalidir, bu nafaqat uning uzunligini, balki uning tuzilishi va joylashuvini ham qamrab oladi. Burst tavsifini biz korniş deb belgilaymiz qayerda bu xato naqshidir (ya'ni xato naqshidagi birinchi nolinchi yozuv bilan boshlanadigan va oxirgi nolga teng bo'lmagan belgi bilan tugaydigan belgilar qatori) va portlash mavjud bo'lgan kod so'zidagi joy.[1]

Masalan, xato naqshining portlash tavsifi bu . E'tibor bering, bunday tavsif noyob emas, chunki xuddi shu portlash xatosini tavsiflaydi. Umuman olganda, agar nolga teng bo'lmagan komponentlar soni bu , keyin bo'ladi har birining nolga teng bo'lmagan yozuvidan boshlanadigan har xil portlash tavsiflari . Quyidagi teorema bilan portlash tavsiflarining noaniqligidan kelib chiqadigan muammolarni hal qilish uchun, avval buni amalga oshirishdan oldin bizga ta'rif kerak.

Ta'rif. Berilgan xato naqshidagi belgilar soni bilan belgilanadi

Teorema (portlash tavsiflarining o'ziga xosligi). Aytaylik uzunlikning xato vektori ikkita portlash tavsifi bilan va . Agar unda ikkita tavsif bir xil, ya'ni ularning tarkibiy qismlari tengdir.[2]
Isbot. Ruxsat bering bo'lishi og'irlik (yoki nolga teng bo'lmagan yozuvlar soni) ning . Keyin aniq bor xato tavsiflari. Uchun isbotlaydigan narsa yo'q. Shunday qilib, biz buni taxmin qilamiz va tavsiflar bir xil emas. Biz har bir nolga teng bo'lmagan yozuvni qayd etamiz naqshda paydo bo'ladi va shuning uchun, ning tarkibiy qismlari naqshga kiritilmagan, nolga teng bo'lgan so'nggi yozuvdan keyin boshlanadigan va naqshning birinchi nolga teng bo'lmagan kiritilishidan oldin davom etadigan nollarning tsiklik ishini tashkil qiladi. Ushbu yugurishga mos keladigan indekslar to'plamini nol yugurish deb ataymiz. Biz darhol har bir portlash tavsifida u bilan bog'liq bo'lgan nol ishlashga ega ekanligini va har bir nolinchi ishning ajralganligini darhol kuzatamiz. Bizda bor ekan nol ishlaydi, va har biri ajratilgan, bizda jami barcha nol ishlarida aniq elementlar. Boshqa tomondan, bizda:
Bu zid Shunday qilib, portlash xatolarining tavsiflari bir xil.

A xulosa yuqoridagi teoremadan biri shundaki, biz uzunlik portlashlari uchun ikkita aniq portlash tavsifiga ega bo'lolmaymiz

Burst xatolarni tuzatish uchun tsiklik kodlar

Tsiklik kodlar quyidagicha ta'riflanadi: o'ylab ko'ring elementlari sifatida belgilar . Keling, so'zlarni ko'pburchaklar deb hisoblashimiz mumkin bu erda so'zning alohida belgilari ko'pburchakning turli koeffitsientlariga mos keladi. Tsiklik kodni aniqlash uchun biz chaqirilgan sobit polinomni tanlaymiz generator polinom. Ushbu tsiklik kodning kod so'zlari ushbu generator polinomiga bo'linadigan barcha polinomlardir.

Kodli so'zlar - bu daraja polinomlari . Aytaylik, generator polinomasi darajaga ega . Daraja polinomlari ga bo'linadigan ko'payishdan kelib chiqadi daraja polinomlari bo'yicha . Bizda ... bor bunday polinomlar. Ularning har biri kod so'ziga mos keladi. Shuning uchun, tsiklik kodlar uchun.

Tsiklik kodlar barcha uzunlikdagi portlashlarni aniqlay oladi . Keyinchalik, har qanday odamning portlashda xatolikni aniqlash qobiliyatini bilib olamiz kod yuqoridan chegaralangan . Tsiklik kodlar portlashda xatolikni aniqlash uchun maqbul hisoblanadi, chunki ular ushbu yuqori chegaraga mos keladi:

Teorema (Siklik portlashni tuzatish qobiliyati). Darajali generator polinomiga ega bo'lgan har bir tsiklik kod barcha uzunlikdagi portlashlarni aniqlay oladi
Isbot. Agar siz uzunlik portlashini qo'shsangiz, buni isbotlashimiz kerak kod so'ziga (ya'ni bo'linadigan polinomga) ), unda natija kod so'zi bo'lmaydi (ya'ni mos keladigan polinom bo'linmaydi) ). Uzunlikning hech qanday portlashi yo'qligini ko'rsatish kifoya ga bo'linadi . Bunday portlash shaklga ega , qayerda Shuning uchun, ga bo'linmaydi (chunki ikkinchisi darajaga ega ). ga bo'linmaydi (Aks holda, barcha kod so'zlar boshlanishi kerak edi ). Shuning uchun, ga bo'linmaydi shuningdek.

Yuqoridagi dalil tsikli kodlarda portlashda xatolarni aniqlash / tuzatish uchun oddiy algoritmni taklif qiladi: uzatilgan so'z berilgan (ya'ni daraja polinomasi) ), bo'linishda ushbu so'zning qolgan qismini hisoblang . Agar qoldiq nolga teng bo'lsa (ya'ni so'z bo'linadigan bo'lsa) ), keyin bu to'g'ri kod so'zi. Aks holda, xato haqida xabar bering. Ushbu xatoni tuzatish uchun uzatilgan so'zdan ushbu qoldiqni olib tashlang. Chiqarish natijasi ikkiga bo'linadi (ya'ni bu to'g'ri kod so'zi bo'ladi).

Burst xatosini aniqlashning yuqori chegarasi bo'yicha (), biz bilamizki, tsiklik kod aniqlay olmaydi barchasi uzunlik portlashlari . Biroq tsiklik kodlar haqiqatan ham aniqlay oladi eng uzunlik portlashlari . Sababi shundaki, portlash ikkiga bo'linib bo'lgandagina aniqlash muvaffaqiyatsiz bo'ladi . Ikkilik alifbolar mavjud uzunlik portlashlari . Ulardan faqat bo'linadi . Shuning uchun, aniqlash qobiliyatsizligi ehtimoli juda kichik () barcha uzunlikdagi portlashlar bo'yicha bir xil taqsimotni nazarda tutadi .

Biz portlashlarni turli xil kosetlarga ajratish orqali samarali portlash-xatolarni tuzatish kodlarini ishlab chiqishda yordam beradigan tsiklik kodlar haqidagi asosiy teoremani ko'rib chiqamiz.

Teorema (aniq Kozetlar ). Lineer kod bu -burst-xatolarni tuzatuvchi kod, agar barcha uzunlikdagi xatolar bo'lsa aniq yotmoq kosets ning .
Isbot. Ruxsat bering uzunlikdagi aniq yoriqlar kodning bir xil kosetasida joylashgan . Keyin kod so'zi. Demak, agar olsak biz uni dekodlashimiz mumkin yoki . Aksincha, agar barcha portlash xatolar bo'lsa va bir xil kosetda yotmang, keyin har bir portlash xatosi uning sindromi bilan belgilanadi. Keyin xatoni uning sindromi orqali tuzatish mumkin. Shunday qilib, chiziqli kod bu -burst xatolarni tuzatuvchi kod, agar faqat barcha uzunlikdagi xatolar bo'lsa ning aniq kosetalarida yotish .
Teorema (Burst xato kodlash tasnifi). Ruxsat bering chiziqli bo'ling -burst-xatolarni tuzatuvchi kod. Keyin noldan uzoq bo'lmagan yorilish bo'lmaydi kod so'zi bo'lishi mumkin.
Isbot. Ruxsat bering uzunlikdagi portlash bilan kod so'zi bo'ling . Shunday qilib u naqshga ega , qayerda va uzunlikdagi so'zlar Demak, so'zlar va uzunlikning ikkita portlashi . Ikkilik chiziqli kodlar uchun ular bir xil kosetga tegishli. Bu aniq Cosets teoremasiga ziddir, shuning uchun nolga teng bo'lmagan uzunlik kod so'zi bo'lishi mumkin.

Burst xatolarni tuzatish chegaralari

Portlashda xatolikni aniqlash va tuzatishda yuqori chegaralar

Yuqori chegara deganda, biz xatolarni aniqlash qobiliyatimiz chegarasini nazarda tutamiz, u biz hech qachon oshib ketolmaymiz. Tasavvur qilaylik, biz an uzunlikdagi barcha portlash xatolarini aniqlay oladigan kod Tabiiy savol: berilgan va , maksimal nima? biz bundan keyin hech qachon erisha olmaymiz? Boshqacha qilib aytganda, uzunlikning yuqori chegarasi nima? har qanday foydalanib aniqlashimiz mumkin bo'lgan portlashlar kodmi? Quyidagi teorema bu savolga javob beradi.

Teorema (Burst xatosini aniqlash qobiliyati). Har qanday odamning portlash xatosini aniqlash qobiliyati kod
Isbot. Dastlab biz kod barcha uzunliklarni aniqlay olishini kuzatamiz agar va faqat ikkita kodli so'z uzunlik portlashi bilan farq qilmasa . Bizda ikkita kodli so'z bor deylik va portlash bilan farq qiladi uzunlik . Qabul qilgandan keyin , biz uzatilgan so'z haqiqatan ham yoki yo'qligini aniqlay olmaymiz uzatish xatolarisiz yoki shunday bo'ladimi portlash xatosi bilan uzatish paytida sodir bo'lgan. Keling, har ikki kod so'z uzunlikning yorilishidan ko'proq farq qiladi deb taxmin qiling Agar uzatilgan kod so'z bo'lsa ham portlashi bilan uriladi uzunlik , u boshqa tegishli kod so'ziga o'tmoqchi emas. Qabul qilgandan so'ng, biz buni aytishimiz mumkin portlash bilan Yuqoridagi kuzatuvga ko'ra, biz bilamizki, ikkita kod so'z birinchisini baham ko'rmaydi belgilar. Sababi shundaki, ular boshqasida farq qilsalar ham ramzlar, ular hali ham uzunlik portlashi bilan farq qiladi Shuning uchun kodli so'zlarning soni qondiradi Qo'llash ikkala tomonga va tartibga solish, biz buni ko'rishimiz mumkin .

Endi biz bir xil savolni takrorlaymiz, ammo xatoni tuzatish uchun: berilgan va , uzunlikning yuqori chegarasi nima? har qanday yordamida tuzatishimiz mumkin bo'lgan portlashlar kodmi? Quyidagi teorema bu savolga dastlabki javobni beradi:

Teorema (Burst xatosini tuzatish qobiliyati). Har qanday odamning portlash xatosini tuzatish qobiliyati kod qondiradi
Isbot. Dastlab biz kod barcha uzunlikdagi yoriqlarni to'g'irlashi mumkinligini kuzatamiz agar va faqat ikkita kodli so'zlar ikkita uzunlik portlashlari yig'indisi bilan farq qilmasa Ikkita kodli so'z va portlashlar bilan farq qiladi va uzunlik har biri. Qabul qilgandan keyin portlash bilan urilgan , biz buni xuddi shunday talqin qilishimiz mumkin portlash bilan urilgan . O'tkazilgan so'z yoki yo'qligini aniqlay olmaymiz yoki . Keling, har ikki kod so'zning uzunligi ikkitadan ortiq uzunlik bilan farq qiladi deb taxmin qiling . O'tkazilgan kod so'z bo'lsa ham uzunlik portlashi bilan uriladi , bu boshqa portlash bilan urilgan boshqa kod so'zga o'xshamaydi. Har bir kod so'z uchun ruxsat bering dan farq qiladigan barcha so'zlar to'plamini belgilang uzunlik portlashi bilan E'tibor bering o'z ichiga oladi o'zi. Yuqoridagi kuzatuvga ko'ra, biz ikki xil kod so'zlari uchun buni bilamiz va va ajratilgan. Bizda ... bor kod so'zlar. Shuning uchun, biz buni aytishimiz mumkin . Bundan tashqari, bizda bor . Ikkinchisini tengsizlikni avvalgisiga qo'shib, keyin bazani oling logarifma va qayta tashkil etish, biz yuqoridagi teoremani olamiz.

Rieger tomonidan yanada kuchli natija berilgan:

Teorema (Rieger bilan bog'langan). Agar portlash xatosini to'g'rilash qobiliyatidir chiziqli blok kodi, keyin .
Isbot. Uzunlikning har qanday portlash naqshini to'g'irlashi mumkin bo'lgan har qanday chiziqli kod uzunlik portlashi mumkin emas kod so'zi sifatida. Agar uning uzunligi yorilib ketgan bo'lsa kod so'zi sifatida, keyin uzunlik portlashi kod so'zini uzunlik portlash naqshiga o'zgartirishi mumkin , shuningdek, uzunlikdagi portlash xatosini olish yo'li bilan olinishi mumkin barcha nol kodli so'zlarda. Agar vektorlar avval nolga teng bo'lmasa belgilar, keyin vektorlar massivning turli kichik to'plamlaridan bo'lishi kerak, shunda ularning farqi uzunlik portlashlarining kod so'zi emas. . Ushbu shartni ta'minlagan holda, bunday kichik to'plamlar soni kamida vektorlar soniga teng. Shunday qilib, pastki to'plamlarning soni hech bo'lmaganda bo'ladi . Demak, bizda hech bo'lmaganda alohida belgilar, aks holda, bunday ikkita polinomning farqi ikkita uzunlik portlashlarining yig'indisi bo'lgan kod so'z bo'lishi mumkin. Shunday qilib, bu Rieger chegarasini tasdiqlaydi.

Ta'rif. Yuqoridagi Rieger chegarasiga erishilgan portlash-xatolarni to'g'rilaydigan chiziqli chiziq, portlash-xatolarni to'g'rilashning optimal kodi deb nomlanadi.

Burst xatolarni tuzatish bo'yicha qo'shimcha chegaralar

Bir necha bosqichli burstlarni tuzatish (MPBC) uchun chiziqli blok kodlarining erishiladigan kod tezligi bo'yicha bir nechta yuqori chegaralar mavjud. Bunday cheklovlardan biri har bir pastki blokda maksimal darajada tuzatiladigan tsiklik yorilish uzunligiga yoki teng ravishda har bir bosqichli portlash ichidagi minimal xatosiz uzunlik yoki bo'shliqqa cheklovga ega. Ushbu chegara, bitta portlashni to'g'rilash uchun chegaraning maxsus holatiga tushirilganda, tsiklli portlash uzunligi blok uzunligining yarmidan kam bo'lganida, Abramson bog'langan (portlash-xatolarni tuzatish uchun Xamming bog'lanishining natijasi).[3]

Teorema (portlashlar soni). Uchun ikkilik alifbo ustida mavjud uzunlik vektorlari bu uzunlik portlashlari .[1]
Isbot. Portlash uzunligi bo'lgani uchun portlash bilan bog'liq noyob portlash tavsifi mavjud. Portlash har qanday vaqtda boshlanishi mumkin naqshning pozitsiyalari. Har bir naqsh bilan boshlanadi va uzunligini o'z ichiga oladi . Biz buni boshlanadigan barcha satrlarning to'plami deb hisoblashimiz mumkin va uzunlikka ega . Shunday qilib, jami mavjud mumkin bo'lgan bunday naqshlar va jami uzunlik portlashlari Agar biz nol darajadagi portlashni qo'shsak, bizda bor uzunlik portlashlarini ifodalovchi vektorlar
Teorema (kodli so'zlar soniga bog'liq). Agar ikkilik - portlashda xatolikni tuzatish kodi ko'pi bilan kod so'zlar.
Isbot. Beri borligini bilamiz uzunlik portlashlari . Kod borligini ayting kod so'zlar, keyin bor kod so'zlaridan uzunlik portlashi bilan farq qiladigan kod so'zlar . Har biri so'zlar aniq bo'lishi kerak, aks holda kod masofaga ega bo'lar edi . Shuning uchun, nazarda tutadi
Teorema (Abramson chegaralari). Agar ikkilik chiziqli - portlashda xatolikni tuzatish kodi, uning blok uzunligi quyidagilarni qondirishi kerak:
Isbot: Lineer uchun kod bor kod so'zlar. Avvalgi natijamizga ko'ra, biz buni bilamiz
Izolyatsiya qilish , biz olamiz . Beri va tamsayı bo'lishi kerak, bizda bor .

Izoh. kodning ortiqchaligi deb nomlanadi va Abramson chegaralari uchun muqobil formulada

Yong'in kodlari[3][4][5]

Esa tsiklik kodlar Umuman olganda portlash xatolarini aniqlash uchun kuchli vositalar, endi biz yong'in kodlari deb nomlangan ikkilik tsiklik kodlar oilasini ko'rib chiqamiz, ular bitta portlash xatolarini tuzatish qobiliyatiga ega. Bitta portlash bilan, uzunlikni ayting , shuni anglatadiki, qabul qilingan kod so'zida mavjud bo'lgan barcha xatolar belgilangan muddat ichida bo'ladi raqamlar.

Ruxsat bering bo'lish kamaytirilmaydigan polinom daraja ustida va ruxsat bering davri bo'ling . Davri , va haqiqatan ham har qanday polinomning eng kichik musbat butunligi aniqlangan shu kabi Ruxsat bering qoniqtiradigan musbat tamsayı bo'ling va bo'linmaydi , qayerda davri . Yong'in kodeksiga ta'rif bering quyidagi tomonidan generator polinom:

Biz buni ko'rsatamiz bu -burst-xato tuzatish kodi.

Lemma 1.
Isbot. Ruxsat bering ikki polinomning eng katta umumiy bo'luvchisi bo'ling. Beri qisqartirilmaydi, yoki . Faraz qiling keyin ba'zi bir doimiy uchun . Ammo, ning bo'luvchisi beri ning bo'luvchisi . Ammo bu bizning taxminimizga ziddir bo'linmaydi Shunday qilib, lemmani isbotlash.
Lemma 2. Agar davr polinomidir , keyin agar va faqat agar
Isbot. Agar , keyin . Shunday qilib,
Endi faraz qiling . Keyin, . Biz buni ko'rsatamiz ga bo'linadi induksiya bo'yicha . Asosiy ish quyidagilar. Shuning uchun, taxmin qiling . Biz buni bilamiz ikkalasini ham ajratadi (chunki uning davri bor )
Ammo kamaytirilmaydi, shuning uchun u ikkalasini ham ajratishi kerak va ; Shunday qilib, u oxirgi ikkita polinomning farqini ham ajratadi, . Keyin, bundan kelib chiqadiki ajratadi . Va nihoyat, u quyidagilarni ajratadi: . Induktsiya gipotezasi bo'yicha, , keyin .

Lemma 2-ning xulosasi shundan beri davri bor , keyin ajratadi agar va faqat agar .

Teorema. Yong'in kodeksi - portlashda xatolikni tuzatish[4][5]

Agar biz barcha uzunlikdagi portlashlarni namoyish qila olsak yoki kamroq har xilda bo'ladi kosets, ulardan foydalanishimiz mumkin koset rahbarlari tuzatiladigan xato naqshlarini shakllantiradigan. Sababi oddiy: biz bilamizki, har bir koset o'ziga xos xususiyatga ega sindromni dekodlash u bilan bog'liq va agar har xil kosetsda har xil uzunlikdagi barcha portlashlar sodir bo'lsa, unda barchasi xatolarni tuzatishni osonlashtiradigan noyob sindromlarga ega.

Teoremaning isboti

Ruxsat bering va daraja bilan polinomlar bo'ling va , uzunlik portlashlarini ifodalaydi va bilan mos ravishda Butun sonlar portlashlarning boshlang'ich pozitsiyalarini ifodalaydi va kodning blok uzunligidan kam. Qarama-qarshilik uchun, deb taxmin qiling va bir xil kosetda. Keyin, to'g'ri kod so'zidir (chunki ikkala shart ham bir xil kosetada joylashgan). Umumiylikni yo'qotmasdan, tanlang . Tomonidan bo'linish teoremasi biz yozishimiz mumkin: butun sonlar uchun va . Biz polinomni qayta yozamiz quyidagicha:

E'tibor bering, ikkinchi manipulyatsiya paytida biz ushbu atamani kiritdik . Bizga bunga ruxsat beriladi, chunki yong'in kodlari ishlaydi . Bizning taxminimizcha, to'g'ri kod so'zidir va shuning uchun u ko'p sonli bo'lishi kerak . Yuqorida aytib o'tganimizdek, ning omillari nisbatan asosiy, bo'linishi kerak . Uchun olingan so'nggi iborani diqqat bilan ko'rib chiqamiz biz buni sezamiz ga bo'linadi (Lemma 2 xulosasi bilan). Shuning uchun, ga bo'linadi yoki shunday . Bo'linish teoremasini yana qo'llaganimizda, ko'pburchak borligini ko'ramiz daraja bilan shu kabi:

Keyin yozishimiz mumkin:

Ikkala tomonning darajasini tenglashtirish, bizga beradi Beri xulosa qilishimiz mumkin shuni anglatadiki va . Kengayishda e'tibor bering:

atama paydo bo'ladi, lekin beri , hosil bo'lgan ifoda o'z ichiga olmaydi , shuning uchun va keyinchalik Bu shuni talab qiladi va . Biz o'z bo'linmamizni qayta ko'rib chiqishimiz mumkin tomonidan aks ettirmoq anavi . Qayta almashtirish bizga beradi,

Beri , bizda ... bor . Ammo kamaytirilmaydi, shuning uchun va nisbatan bosh darajali bo'lishi kerak. Beri kod so'zi, bo'linishi kerak , chunki uni ajratish mumkin emas . Shuning uchun, ning ko'paytmasi bo'lishi kerak . Ammo bu ham ko'paytma bo'lishi kerak , bu uning ko'paytmasi bo'lishi kerakligini anglatadi ammo bu aniq kodning blok uzunligi. Shuning uchun, ning ko'paytmasi bo'lishi mumkin emas chunki ularning ikkalasi ham kamroq . Shunday qilib, bizning taxminimiz kod so'zi bo'lish noto'g'ri va shuning uchun va noyob kosmik sindromlar bilan ajralib turadi va shuning uchun ularni tuzatish mumkin.

Misol: yong'in kodini tuzatishda 5 ta xatolik

Yuqoridagi bobda keltirilgan nazariya bilan a qurilishini ko'rib chiqing - Yong'in kodini tuzatishda xato. Yong'in kodini tuzish uchun biz qaytarib bo'lmaydigan polinomga ehtiyoj borligini unutmang , butun son , bizning kodimizning xatolarni to'g'irlash qobiliyatini ifodalaydi va biz bu xususiyatni qondirishimiz kerak davriga bo'linmaydi . Ushbu talablarni inobatga olgan holda, kamaytirilmaydigan polinomni ko'rib chiqing va ruxsat bering . Beri ibtidoiy polinom, uning davri . Biz buni tasdiqlaymiz ga bo'linmaydi . Shunday qilib,

yong'in kodi generatoridir. Kodning blok uzunligini eng kichik umumiy ko'paytmani baholash orqali hisoblashimiz mumkin va . Boshqa so'zlar bilan aytganda, . Shunday qilib, yuqoridagi Yong'in kodeksi har qanday uzunlikdagi portlashni to'g'irlashga qodir tsiklik koddir yoki kamroq.

Ikkilik qamish-Sulaymon kodlari

Kabi ba'zi bir kodlar oilalari Rid - Sulaymon, ikkilikdan kattaroq alifbo o'lchamlari bo'yicha ishlaydi. Ushbu xususiyat bunday kodlarni kuchli portlash xatolarini tuzatish qobiliyatiga ega. Ishlayotgan kodni ko'rib chiqing . Alfavitning har bir belgisi quyidagicha ifodalanishi mumkin bitlar. Agar bu Reed - Sulaymon kodi tugadi , biz o'ylashimiz mumkin sifatida kod tugadi .

Bunday kodlarning yorilish xatosini tuzatish uchun kuchli bo'lishining sababi shundaki, har bir belgi quyidagicha ifodalanadi bit, va umuman olganda, ularning qanchasi ahamiyatsiz bitlar noto'g'ri; bitta bitmi yoki barchasi bitlar xatolarni o'z ichiga oladi, dekodlash nuqtai nazaridan bu hali bitta belgi xatosi. Boshqacha qilib aytganda, portlashda xatolar klasterlarda paydo bo'lishga moyil bo'lganligi sababli, bitta belgi xatosini keltirib chiqaradigan bir nechta ikkilik xatolar ehtimoli katta.

E'tibor bering, portlash xatolar ko'pi bilan ta'sir qilishi mumkin ramzlari va yorilishi eng ko'p ta'sir qilishi mumkin belgilar. Keyin, portlash eng ko'p ta'sir qilishi mumkin belgilar; bu shuni anglatadiki a -symbols-xato tuzatish kodi maksimal uzunlikdagi yoriqni to'g'irlashi mumkin .

Umuman olganda, a -Rid-Sulaymon kodini tuzatishda xatolik yuz berdi ning har qanday birikmasini tuzatishi mumkin

yoki kamroq uzunlikdagi portlashlar , tuzatishga qodir bo'lishning ustiga - tasodifiy yomon holatdagi xatolar.

Ikkilik RS kodiga misol

Ruxsat bering bo'lishi a RS kod tugadi . Ushbu kod ishlatilgan NASA ularning ichida Kassini-Gyuygens kosmik kemalar.[6] Bu tuzatishga qodir ramzdagi xatolar. Endi biz Ikkilik RS kodini tuzamiz dan . Har bir belgi yordamida yoziladi bitlar. Shuning uchun Ikkilik RS kodi bo'ladi uning parametrlari sifatida. U har qanday uzunlikdagi portlashni to'g'rilashga qodir .

Interleaved kodlari

Interleaving konvolyutsion kodlarni tasodifiy xato tuzatuvchilardan burst xato tuzatuvchilarga aylantirish uchun ishlatiladi. Interleaved kodlardan foydalanishning asosiy g'oyasi - qabul qilgichdagi belgilarni chalkashtirishdir. Bu yaqindan joylashgan qabul qilingan xatolar portlashlarini tasodifiylashishiga olib keladi va biz tasodifiy kanal uchun tahlilni qo'llashimiz mumkin. Shunday qilib, transmitterda interleaver tomonidan bajariladigan asosiy funktsiya kirish belgisi ketma-ketligini o'zgartirishdir. Qabul qilgichda deinterleaver qabul qilingan ketma-ketlikni o'zgartiradi va transmitterda asl o'zgartirilmagan ketma-ketlikni qaytaradi.

Interleaverning sig'imini to'g'irlashda xatolik yuz berdi

Qator va ustunli buyruqlar tasviri
Teorema. Agar ba'zi bir kodlarning portlash xatolarini tuzatish qobiliyati bo'lsa keyin uning xatolarini to'g'rilash qobiliyati - yo'llararo
Isbot: Aytaylik, bizda barcha uzunlikdagi portlashlarni to'g'irlaydigan kod Interleaving bizni a bilan ta'minlashi mumkin barcha uzunlikdagi portlashlarni to'g'irlaydigan kod har qanday berilgan uchun . Agar o'zaro ixtiyoriy uzunlikdagi xabarni interleaving yordamida kodlashni xohlasak, avval uni uzunlik bloklariga ajratamiz . Biz yozamiz har bir blokning yozuvlari qatorli buyurtma yordamida matritsa. Keyin, har bir qatorni kod. Biz nima olamiz a matritsa. Endi, ushbu matritsa ustun tartibida o'qiladi va uzatiladi. Agar hiyla-nayrang shuki, agar uzunlik yorilib ketsa uzatilgan so'zda har bir satr taxminan o'z ichiga oladi ketma-ket xatolar (aniqrog'i, har bir satrda kamida uzunlik portlashi bo'ladi va ko'pi bilan ). Agar keyin va kod har bir qatorni tuzatishi mumkin. Shuning uchun, interleaved kod uzunlik yorilishini to'g'irlashi mumkin . Aksincha, agar unda kamida bitta qatorda ko'proq bo'lishi kerak ketma-ket xatolar va kod ularni tuzatolmay qolishi mumkin. Shuning uchun, interleavedning xatolarni tuzatish qobiliyati kod to'liq Interfaaved kodining BEC samaradorligi asl nusxada saqlanib qoladi kod. Bu to'g'ri, chunki:

Interleaver blokirovkasi

Quyidagi rasmda 4 dan 3 gacha bo'lgan bo'shliq ko'rsatilgan.

Bloklarning interleaveriga misol

Yuqoridagi interleaver a deb nomlanadi blokirovka qilish. Bu erda kirish belgilari qatorlarga ketma-ket yoziladi va ustunlar ketma-ket o'qish orqali chiqadigan belgilar olinadi. Shunday qilib, bu shaklda qator. Odatda, kod so'zining uzunligi.

Blok interleaverining sig'imi: Uchun blok interleaver va uzunlik portlashi xatolar sonining yuqori chegarasi Bu biz chiqish ustunini oqilona o'qiyotganimizdan va qatorlar sonidan aniq . Gacha bo'lgan xatolarni tuzatish qobiliyati uchun yuqoridagi teorema bo'yicha ruxsat etilgan maksimal yorilish uzunligi Yorilish uzunligi uchun , dekoder ishlamay qolishi mumkin.

Blok interleaverining samaradorligi (): Bu dekolder interleaver xotirasida ishlamay qolishi mumkin bo'lgan portlash uzunligining nisbati bo'yicha aniqlanadi. Shunday qilib, biz shakllantirishimiz mumkin kabi

Blok interleyerining kamchiliklari: Rasmdan ko'rinib turibdiki, ustunlar ketma-ket o'qiladi, qabul qilgich bitta qatorni undan oldin emas, balki to'liq xabar olgandan keyingina izohlashi mumkin. Shuningdek, qabul qilgich qabul qilingan belgilarni saqlash uchun juda ko'p xotirani talab qiladi va to'liq xabarni saqlashi kerak. Shunday qilib, ushbu omillar ikkita kamchilikni keltirib chiqaradi, biri kechikish, ikkinchisi esa saqlash (juda katta miqdordagi xotira). Quyida tavsiflangan konvolyutsion interleaver yordamida bu kamchiliklardan saqlanish mumkin.

Konvolyutsion interleaver

Cross interleaver - bu multipleksor-demultiplekser tizimining bir turi. Ushbu tizimda kechikish chiziqlari uzunlikni tobora oshirish uchun ishlatiladi. Kechikish liniyasi asosan signalni ma'lum vaqt davomiyligini kechiktirish uchun ishlatiladigan elektron zanjirdir. Ruxsat bering kechikish satrlari soni va bo'lishi kerak har bir kechikish chizig'i tomonidan kiritilgan belgilar soni. Shunday qilib, ketma-ket kirishlar orasidagi ajratish = belgilar. Kod so'zining uzunligi bo'lsin Thus, each symbol in the input codeword will be on distinct delay line. Let a burst error of length sodir bo'lishi. Since the separation between consecutive symbols is the number of errors that the deinterleaved output may contain is By the theorem above, for error correction capacity up to , maximum burst length allowed is For burst length of decoder may fail.

An example of a convolutional interleaver
An example of a deinterleaver

Efficiency of cross interleaver (): It is found by taking the ratio of burst length where decoder may fail to the interleaver memory. In this case, the memory of interleaver can be calculated as

Thus, we can formulate quyidagicha:

Performance of cross interleaver : As shown in the above interleaver figure, the output is nothing but the diagonal symbols generated at the end of each delay line. In this case, when the input multiplexer switch completes around half switching, we can read first row at the receiver. Thus, we need to store maximum of around half message at receiver in order to read first row. This drastically brings down the storage requirement by half. Since just half message is now required to read first row, the latency is also reduced by half which is good improvement over the block interleaver. Thus, the total interleaver memory is split between transmitter and receiver.

Ilovalar

Yilni disk

Without error correcting codes, digital audio would not be technically feasible.[7] The Reed - Sulaymon kodlari can correct a corrupted symbol with a single bit error just as easily as it can correct a symbol with all bits wrong. This makes the RS codes particularly suitable for correcting burst errors.[5] By far, the most common application of RS codes is in compact discs. In addition to basic error correction provided by RS codes, protection against burst errors due to scratches on the disc is provided by a cross interleaver.[3]

Current compact disc digital audio system was developed by N. V. Philips of The Netherlands and Sony Corporation of Japan (agreement signed in 1979).

A compact disc comprises a 120 mm aluminized disc coated with a clear plastic coating, with spiral track, approximately 5 km in length, which is optically scanned by a laser of wavelength ~0.8 μm, at a constant speed of ~1.25 m/s. For achieving this constant speed, rotation of the disc is varied from ~8 rev/s while scanning at the inner portion of the track to ~3.5 rev/s at the outer portion. Pits and lands are the depressions (0.12 μm deep) and flat segments constituting the binary data along the track (0.6 μm width).[8]

The CD process can be abstracted as a sequence of the following sub-processes:-> Channel encoding of source of signals-> Mechanical sub-processes of preparing a master disc, producing user discs and sensing the signals embedded on user discs while playing – the channel-> Decoding the signals sensed from user discs

The process is subject to both burst errors and random errors.[7] Burst errors include those due to disc material (defects of aluminum reflecting film, poor reflective index of transparent disc material), disc production (faults during disc forming and disc cutting etc.), disc handling (scratches – generally thin, radial and orthogonal to direction of recording) and variations in play-back mechanism. Random errors include those due to jitter of reconstructed signal wave and interference in signal. CIRC (Cross-Interleaved Reed–Solomon code ) is the basis for error detection and correction in the CD process. It corrects error bursts up to 3,500 bits in sequence (2.4 mm in length as seen on CD surface) and compensates for error bursts up to 12,000 bits (8.5 mm) that may be caused by minor scratches.

Encoding: Sound-waves are sampled and converted to digital form by an A/D converter. The sound wave is sampled for amplitude (at 44.1 kHz or 44,100 pairs, one each for the left and right channels of the stereo sound). The amplitude at an instance is assigned a binary string of length 16. Thus, each sample produces two binary vectors from yoki 4 bytes of data. Every second of sound recorded results in 44,100 × 32 = 1,411,200 bits (176,400 bytes) of data.[5] The 1.41 Mbit/s sampled data stream passes through the error correction system eventually getting converted to a stream of 1.88 Mbit/s.

Input for the encoder consists of input frames each of 24 8-bit symbols (12 16-bit samples from the A/D converter, 6 each from left and right data (sound) sources). A frame can be represented by qayerda va are bytes from the left and right channels from the sample of the frame.

Initially, the bytes are permuted to form new frames represented by qayerda vakillik qilish left and right samples from the frame after 2 intervening frames.

Next, these 24 message symbols are encoded using C2 (28,24,5) Reed–Solomon code which is a shortened RS code over . This is two-error-correcting, being of minimum distance 5. This adds 4 bytes of redundancy, forming a new frame: . The resulting 28-symbol codeword is passed through a (28.4) cross interleaver leading to 28 interleaved symbols. These are then passed through C1 (32,28,5) RS code, resulting in codewords of 32 coded output symbols. Further regrouping of odd numbered symbols of a codeword with even numbered symbols of the next codeword is done to break up any short bursts that may still be present after the above 4-frame delay interleaving. Thus, for every 24 input symbols there will be 32 output symbols giving . Finally one byte of control and display information is added.[5] Each of the 33 bytes is then converted to 17 bits through EFM (eight to fourteen modulation) and addition of 3 merge bits. Therefore, the frame of six samples results in 33 bytes × 17 bits (561 bits) to which are added 24 synchronization bits and 3 merging bits yielding a total of 588 bits.

Decoding: The CD player (CIRC decoder) receives the 32 output symbol data stream. This stream passes through the decoder D1 first. It is up to individual designers of CD systems to decide on decoding methods and optimize their product performance. Being of minimum distance 5 The D1, D2 decoders can each correct a combination of errors and erasures such that .[5] In most decoding solutions, D1 is designed to correct single error. And in case of more than 1 error, this decoder outputs 28 erasures. The deinterlever at the succeeding stage distributes these erasures across 28 D2 codewords. Again in most solutions, D2 is set to deal with erasures only (a simpler and less expensive solution). If more than 4 erasures were to be encountered, 24 erasures are output by D2. Thereafter, an error concealment system attempts to interpolate (from neighboring symbols) in case of uncorrectable symbols, failing which sounds corresponding to such erroneous symbols get muted.

Performance of CIRC:[7] CIRC conceals long bust errors by simple linear interpolation. 2.5 mm of track length (4000 bits) is the maximum completely correctable burst length. 7.7 mm track length (12,300 bits) is the maximum burst length that can be interpolated. Sample interpolation rate is one every 10 hours at Bit Error Rate (BER) and 1000 samples per minute at BER = Undetectable error samples (clicks): less than one every 750 hours at BER = and negligible at BER = .

Shuningdek qarang

Adabiyotlar

  1. ^ a b v d Coding Bounds for Multiple Phased-Burst Correction and Single Burst Correction Codes
  2. ^ The Theory of Information and Coding: Student Edition, by R. J. McEliece
  3. ^ a b v Ling, San, and Chaoping Xing. Coding Theory: A First Course. Cambridge, UK: Cambridge UP, 2004. Print
  4. ^ a b Moon, Todd K. Error Correction Coding: Mathematical Methods and Algorithms. Hoboken, NJ: Wiley-Interscience, 2005. Print
  5. ^ a b v d e f Lin, Shu, and Daniel J. Costello. Error Control Coding: Fundamentals and Applications. Upper Saddle River, NJ: Pearson-Prentice Hall, 2004. Print
  6. ^ http://quest.arc.nasa.gov/saturn/qa/cassini/Error_correction.txt Arxivlandi 2012-06-27 da Orqaga qaytish mashinasi
  7. ^ a b v Algebraic Error Control Codes (Autumn 2012) – Handouts from Stanford University
  8. ^ McEliece, Robert J. The Theory of Information and Coding: A Mathematical Framework for Communication. Reading, MA: Addison-Wesley Pub., Advanced Book Program, 1977. Print