Tornado kodi - Tornado code

Yilda kodlash nazariyasi, Tornado kodlari sinfidir o'chirish kodlari bu qo'llab-quvvatlash xatolarni tuzatish. Tornado kodlari ma'lumotlarning samaradorligidan ko'ra doimiy ravishda ko'proq C bloklarini talab qiladi Reed - Sulaymon o'chirish kodlari, lekin ularni yaratish juda tezroq va o'chirishni tezroq tuzatishi mumkin. Tornado kodlarining dasturiy ta'minot asosida amalga oshirilishi Rid-Sulaymon o'chirish kodlariga qaraganda kichik uzunliklarda 100 baravar tezroq, katta uzunliklarda esa 10 000 baravar tezroq.[1] Tornado kodlari kiritilgandan beri, shunga o'xshash boshqa ko'plab o'chirish kodlari paydo bo'ldi, eng muhimi Onlayn kodlar, LT kodlari va Raptor kodlari.

Tornado kodlari qatlamli yondashuvdan foydalanadi. Oxirgi ishlatishdan tashqari barcha qatlamlar LDPC tezkor, ammo ishlamay qolishi mumkin bo'lgan xatolarni tuzatish kodi. Oxirgi qatlamda Reed-Solomon tuzatish kodi qo'llaniladi, bu sekinroq, ammo qobiliyatsizlikni tiklash nuqtai nazaridan maqbuldir. Tornado kodlari har bir darajadagi qancha darajani, qancha tiklash bloklarini va yakuniy bo'lmagan qatlamlar uchun bloklarni yaratish uchun taqsimlanishini belgilaydi.

Umumiy nuqtai

Kirish ma'lumotlari bloklarga bo'linadi. Bloklar - bu bir xil o'lchamdagi bitlarning ketma-ketligi. Qayta tiklash ma'lumotlari kirish ma'lumotlari bilan bir xil blok o'lchamidan foydalanadi. Blokni o'chirish (kiritish yoki tiklash) boshqa usullar bilan aniqlanadi. (Masalan, diskdan blok CRC tekshiruvidan o'tmaydi yoki ketma-ketlik raqami berilgan tarmoq paketi hech qachon kelmaydi.)

Qayta tiklash bloklari soni foydalanuvchi tomonidan beriladi. Keyin har bir darajadagi bloklar soni bilan birga darajalar soni aniqlanadi. Har bir darajadagi raqam B koeffitsienti bilan belgilanadi, u birdan kam. Agar N kirish bloklari bo'lsa, birinchi tiklash darajasida B * N bloklari, ikkinchisida B * B * N, uchinchisida B * B * B * N va boshqalar mavjud.

Oxirgi darajadan tashqari barcha tiklash darajalari xor (exclusive-or) tomonidan ishlaydigan LDPC-dan foydalanadi. Xor 1s va 0s ikkilik qiymatlarda ishlaydi. A xor B 1 ga teng, agar A va B qiymatlari har xil bo'lsa, 0 va A va B bir xil qiymatlarga ega bo'lsa. Agar sizga (A xor B) va A natijalar berilgan bo'lsa, siz B qiymatini aniqlay olasiz (A xor B xor A = B) Xuddi shunday, agar sizga (A xor B) va B natijalar berilsa, siz aniqlay olasiz A qiymati bu bir nechta qiymatlarga cho'ziladi, shuning uchun (A xor B xor C xor D) natijasi va qiymatlarning istalgan 3 natijasi yo'qolgan qiymatni tiklashi mumkin.

Shunday qilib, birinchi darajadagi tiklash bloklari ba'zi kirish bloklari to'plamining xoridir. Xuddi shunday, ikkinchi darajadagi tiklash bloklari ham har biri birinchi darajadagi ba'zi bloklar xoridir. Xorda ishlatiladigan bloklar tasodifiy, takrorlanmasdan tanlanadi. Biroq, raqam Qayta tiklash blokini yaratish uchun xor'ed bloklari har bir daraja uchun juda aniq taqsimotdan tanlanadi.

Xor tezkor operatsiya bo'lgani uchun va qutqaruv bloklari kirishdagi bloklarning faqat bir qismining xoridir (yoki undan past darajadagi tiklash darajasida), tiklash bloklari tezda yaratilishi mumkin.

Oxirgi daraja Reed-Sulaymon kodidir. Rid-Sulaymon kodlari muvaffaqiyatsizliklarni tiklash nuqtai nazaridan maqbuldir, ammo ularni yaratish va tiklash sekin. Har bir sath avvalgilariga qaraganda kamroq bloklarga ega bo'lganligi sababli, Reed-Solomon kodida qutqaruv bloklarini yaratish va ulardan foydalanishda kam sonli qutqaruv bloklari mavjud. Shunday qilib, Rid-Sulaymon sust bo'lsa ham, unda ishlash uchun ozgina ma'lumot bor.

Qayta tiklash paytida avval Reed-Solomon kodi tiklanadi. Keyingi bosqichgacha etishmayotgan bloklar soni oxirgi darajadagi mavjud bloklardan kam bo'lsa, bu ishlashga kafolat beradi.

Pastga tushganda, LDPC (xor) tiklanish darajasi ostidagi darajani tiklash uchun ishlatilishi mumkin yuqori ehtimollik bilan agar barcha qutqaruv bloklari mavjud bo'lsa va ostidagi daraja ko'p bo'lsa, tiklash darajasidan C 'kamroq bloklar mavjud. Qayta tiklash algoritmi quyi darajadan faqat bitta ishlab chiqaruvchi to'plami etishmayotgan ba'zi qutqaruv bloklarini topishdir. Keyin mavjud bo'lgan barcha bloklar bilan tiklash blokining xor etishmayotgan blokga teng.

Patent masalalari

Tornado kodlari ilgari Amerika Qo'shma Shtatlarida patentlangan.[2] US6163870 A (1997 yil 6-noyabrda rasmiylashtirilgan) va 6081909 A-sonli (1997 yil 6-noyabrda) patentlari Tornado kodlarini tavsiflaydi va ularning amal qilish muddati 2017 yil 6-noyabrda tugagan. US6307487 B1 (1999 yil 5-fevralda berilgan) va US6320520 B1 (topshirilgan) patentlari 1999 yil 17-sentabr) Tornado kodlarini ham eslatib o'tdi va 2019 yil 5-fevral va 2019-yil 17-sentabrgacha amal qilish muddati tugadi.

Iqtiboslar

Maykl Lubi Tornado kodlarini yaratdi.[3][4]

Tashqi havolalar

CMU-dan o'qiladigan tavsif (PostScript) [1] va yana Lubidan boshqa Xalqaro kompyuter fanlari instituti (PostScript) [2].

Shuningdek qarang

Izohlar

  1. ^ Ommaviy ma'lumotlarning ishonchli taqsimlanishiga raqamli favvora usuli. http://portal.acm.org/citation.cfm?id=285243.285258
  2. ^ (Mitzenmaxer 2004 yil )
  3. ^ (Luby 1997 yil )
  4. ^ (Luby 1998 yil )

Adabiyotlar

  • M. Mitzenmaxer (2004). "Raqamli favvoralar: So'rov va oldinga qarab". Proc. 2004 yil IEEE Axborot nazariyasi bo'yicha seminar (ITW).
  • M. Lyubi, M. Mitzenmaxer, A. Shokrollaxi, D. Spielman , V. Stemann (1997). "Amaliy zararga chidamli kodlar". Yigirma to'qqizinchi yillik ishlar ACM hisoblash nazariyasi bo'yicha simpozium (STOC ): 150–159.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)
  • M. Lyubi, M. Mitzenmaxer, A. Shokrollaxi (1998). "Va daraxtlarni baholash orqali tasodifiy jarayonlarni tahlil qilish". 9 yillik yillik pro ACM - Diskret algoritmlar bo'yicha SIAM simpoziumi: 364–373.CS1 maint: bir nechta ism: mualliflar ro'yxati (havola)