Zemorlarni dekodlash algoritmi - Zemors decoding algorithm - Wikipedia

Yilda kodlash nazariyasi, Zemor algoritmi, Gilles Zemor tomonidan ishlab chiqilgan va ishlab chiqilgan,^[1] kodni tuzishda rekursiv past murakkablik yondashuvi. Bu algoritmini takomillashtirishdir Sipser va Spielman.

Zemor Sipser-Spielman qurilishining odatiy sinfini ko'rib chiqdi kengaytiruvchi kodlar, bu erda asosiy grafik mavjud ikki tomonlama grafik. Sipser va Spielman xatolarning doimiy qismini olib tashlaydigan oddiy parallel algoritm bilan birga asimptotik jihatdan yaxshi chiziqli xato kodlari konstruktiv oilasini taqdim etishdi. Maqola doktor Venkatesan Gurusvamining kurs yozuvlari asosida tayyorlangan ^[2]

Kod tuzilishi

Zemor algoritmi bir turiga asoslangan kengaytiruvchi grafikalar deb nomlangan Tanner grafigi. Kodni qurish birinchi marta Tanner tomonidan taklif qilingan.^[3] Kodlar asoslanadi ikki qavatli qopqoq ${ displaystyle d}$, muntazam kengaytirgich ${ displaystyle G}$, bu ikki tomonlama grafik. ${ displaystyle G}$ =${ displaystyle chap (V, E o'ng)}$, qayerda ${ displaystyle V}$ bu tepaliklar to'plami va ${ displaystyle E}$ bu qirralarning to'plami va ${ displaystyle V}$ = ${ displaystyle A}$ ${ displaystyle cup}$ ${ displaystyle B}$ va ${ displaystyle A}$ ${ displaystyle cap}$ ${ displaystyle B}$ = ${ displaystyle emptyset}$, qayerda ${ displaystyle A}$ va ${ displaystyle B}$ 2 tepaliklar to'plamini bildiradi. Ruxsat bering ${ displaystyle n}$ har bir guruhdagi tepaliklar soni, ya'ni, ${ displaystyle | A | = | B | = n}$. Chegarasi o'rnatilgan ${ displaystyle E}$ hajmda bo'lish ${ displaystyle N}$ =${ displaystyle nd}$ va har bir chekka ${ displaystyle E}$ ikkalasida ham bitta so'nggi nuqta bor ${ displaystyle A}$ va ${ displaystyle B}$. ${ displaystyle E (v)}$ o'z ichiga olgan qirralarning to'plamini bildiradi ${ displaystyle v}$.

Buyurtmani qabul qiling ${ displaystyle V}$, shuning uchun buyurtma har bir chekkada amalga oshiriladi ${ displaystyle E (v)}$ har bir kishi uchun ${ displaystyle v in V}$. Ruxsat bering cheklangan maydon ${ displaystyle mathbb {F} = GF (2)}$va bir so'z bilan aytganda ${ displaystyle x = (x_ {e}), e in E}$ yilda ${ displaystyle mathbb {F} ^ {N}}$, so'zning pastki so'zi indekslangan bo'lsin ${ displaystyle E (v)}$. Ushbu so'z bilan belgilansin ${ displaystyle (x) _ {v}}$. Tepaliklarning pastki qismi ${ displaystyle A}$ va ${ displaystyle B}$ har bir so'zni keltirib chiqaradi ${ displaystyle x in mathbb {F} ^ {N}}$ qism ${ displaystyle n}$ bir-biriga qo'shilmaydigan pastki so'zlar ${ displaystyle chap (x o'ng) _ {v} in mathbb {F} ^ {d}}$, qayerda ${ displaystyle v}$ elementlari bo'yicha intervallarni ${ displaystyle A}$. Kodni yaratish uchun ${ displaystyle C}$, chiziqli pastki kodni ko'rib chiqing ${ displaystyle C_ {o}}$, bu a ${ displaystyle [d, r_ {o} d, delta]}$ kod, qaerda ${ displaystyle q}$, alifbo hajmi ${ displaystyle 2}$. Har qanday tepalik uchun ${ displaystyle v in V}$, ruxsat bering ${ displaystyle v (1), v (2), ldots, v (d)}$ ning ba'zi buyurtmalari bo'lishi mumkin ${ displaystyle d}$ tepaliklari ${ displaystyle E}$ qo'shni ${ displaystyle v}$. Ushbu kodda har bir bit ${ displaystyle x_ {e}}$ chekka bilan bog'langan ${ displaystyle e}$ ning ${ displaystyle E}$.

Biz kodni aniqlay olamiz ${ displaystyle C}$ ikkilik vektorlar to'plami bo'lish ${ displaystyle x = chap (x_ {1}, x_ {2}, ldots, x_ {N} o'ng)}$ ning ${ displaystyle {0,1 } ^ {N}}$ Shunday qilib, har bir tepalik uchun ${ displaystyle v}$ ning ${ displaystyle V}$, ${ displaystyle left (x_ {v (1)}, x_ {v (2)}, ldots, x_ {v (d)} right)}$ kodining so'zidir ${ displaystyle C_ {o}}$. Bunday holda, biz har bir chekka bo'lganida maxsus ishni ko'rib chiqishimiz mumkin ${ displaystyle E}$ aniq qo'shni ${ displaystyle 2}$ tepaliklari ${ displaystyle V}$. Bu shuni anglatadiki ${ displaystyle V}$ va ${ displaystyle E}$ navbati bilan vertikal to'plam va chekka to'plamni tashkil qiladi ${ displaystyle d}$ muntazam grafik ${ displaystyle G}$.

Kodni chaqiramiz ${ displaystyle C}$ kabi qurilgan ${ displaystyle chap (G, C_ {o} o'ng)}$ kod. Berilgan grafik uchun ${ displaystyle G}$ va berilgan kod ${ displaystyle C_ {o}}$, bir nechtasi bor ${ displaystyle chap (G, C_ {o} o'ng)}$ kodlar, chunki berilgan tepaga tushgan qirralarning tartibini har xil usullari mavjud ${ displaystyle v}$, ya'ni, ${ displaystyle v (1), v (2), ldots, v (d)}$. Aslida bizning kodimiz ${ displaystyle C}$ barcha kod so'zlaridan iborat ${ displaystyle x_ {v} C_ {o}} da$ Barcha uchun ${ displaystyle v in A, B}$. Kod ${ displaystyle C}$ chiziqli ${ displaystyle [N, K, D]}$ yilda ${ displaystyle mathbb {F}}$ chunki u subkoddan hosil bo'ladi ${ displaystyle C_ {o}}$, bu chiziqli. Kod ${ displaystyle C}$ sifatida belgilanadi ${ displaystyle C = {c in mathbb {F} ^ {N} :( c) _ {v} in C_ {o} }}$ har bir kishi uchun ${ displaystyle v in V}$.

G chizmasi va C kodi

Ushbu rasmda, ${ displaystyle (x) _ {v} = chap (x_ {e1}, x_ {e2}, x_ {e3}, x_ {e4} right) C_ {o}} da$. Bu grafikani ko'rsatadi ${ displaystyle G}$ va kod ${ displaystyle C}$.

Matritsada ${ displaystyle G}$, ruxsat bering ${ displaystyle lambda}$ ikkinchisiga teng o'zgacha qiymat ning qo'shni matritsa ning ${ displaystyle G}$. Bu erda eng katta tabiiy qiymat hisoblanadi ${ displaystyle d}$. Ikki muhim da'vo:

1-da'vo

${ displaystyle chap ({ dfrac {K} {N}} o'ng) geq 2r_ {o} -1}$
. Ruxsat bering ${ displaystyle R}$ raqamli tugunlari darajaga ega bo'lgan ikki tomonlama grafikadan tuzilgan chiziqli kodning tezligi ${ displaystyle m}$ va pastki kod tugunlari darajaga ega ${ displaystyle n}$. Agar parametrlarga ega bo'lgan bitta chiziqli kod bo'lsa ${ displaystyle chap (n, k o'ng)}$ va darajasi ${ displaystyle r = chap ({ dfrac {k} {n}} o'ng)}$ pastki kod tugunlarining har biri bilan bog'liq, keyin ${ displaystyle k geq 1- chap (1-r o'ng) m}$.

Isbot

Ruxsat bering ${ displaystyle R}$ ga teng bo'lgan chiziqli kodning tezligi bo'ling ${ displaystyle K / N}$Bor ${ displaystyle S}$ grafadagi pastki kod tugunlari. Agar pastki kodning darajasi bo'lsa ${ displaystyle n}$, keyin kod bo'lishi kerak ${ displaystyle chap ({ dfrac {n} {m}} o'ng) S}$ raqamlar, chunki har bir raqamli tugun ulangan ${ displaystyle m}$ ning ${ displaystyle chap (n o'ng) S}$ grafadagi qirralar. Har bir subkod tuguni o'z hissasini qo'shadi ${ displaystyle (n-k)}$ jami tenglikni tekshirish matritsasiga tenglamalar ${ displaystyle chap (n-k o'ng) S}$. Ushbu tenglamalar chiziqli ravishda mustaqil bo'lmasligi mumkin. Shuning uchun, ${ displaystyle chap ({ dfrac {K} {N}} o'ng) geq chap ({ dfrac {({ dfrac {n} {m}}) S- (nk) S} {({ dfrac {n} {m}}) S}} o'ng)}$
${ displaystyle geq 1-m chap ({ dfrac {n-k} {n}} o'ng)}$
${ displaystyle geq 1-m chap (1-r o'ng)}$, Ning qiymati beri ${ displaystyle m}$, ya'ni ushbu ikki tomonlama grafikning raqamli tuguni ${ displaystyle 2}$ va bu erda ${ displaystyle r = r_ {o}}$, biz quyidagicha yozishimiz mumkin:
${ displaystyle chap ({ dfrac {K} {N}} o'ng) geq 2r_ {o} -1}$

2-da'vo

${ displaystyle D geq N chap ({ dfrac {( delta - ({ dfrac { lambda} {d}}))} {(1 - ({ dfrac { lambda} {d}}) }}) o'ng) ^ {2}}$

${ displaystyle = N chap ( delta ^ {2} -O chap ({ dfrac { lambda} {d}} o'ng) o'ng)}$ ${ displaystyle rightarrow (1)}$

Agar ${ displaystyle S}$ chiziqli stavka kodidir ${ displaystyle r}$, blok kodining uzunligi ${ displaystyle d}$va minimal nisbiy masofa ${ displaystyle delta}$va agar bo'lsa ${ displaystyle B}$ a ning vertikal tushish grafigi ${ displaystyle d}$ - ikkinchi qiymatga ega bo'lgan doimiy grafik ${ displaystyle lambda}$, keyin kod ${ displaystyle C (B, S)}$ hech bo'lmaganda stavkaga ega ${ displaystyle 2r_ {o} -1}$ va hech bo'lmaganda minimal nisbiy masofa ${ displaystyle chap ( chap ({ dfrac { delta - chap ({ dfrac { lambda} {d}} o'ng)) {1- chap ({ dfrac { lambda} {d} } o'ng)}} o'ng) o'ng) ^ {2}}$.

Isbot

Ruxsat bering ${ displaystyle B}$ dan olingan bo'lishi ${ displaystyle d}$ muntazam grafik ${ displaystyle G}$. Shunday qilib, ning o'zgaruvchilar soni ${ displaystyle C (B, S)}$ bu ${ displaystyle chap ({ dfrac {dn} {2}} o'ng)}$ va cheklovlar soni ${ displaystyle n}$. Alon-Chungning so'zlariga ko'ra,^[4] agar ${ displaystyle X}$ ning pastki qismidir ${ displaystyle G}$ hajmi ${ displaystyle gamma n}$, keyin subgrafada joylashgan qirralarning soni bilan induksiya qilinadi ${ displaystyle X}$ yilda ${ displaystyle G}$ ko'pi bilan ${ displaystyle chap ({ dfrac {dn} {2}} o'ng) chap ( gamma ^ {2} + ({ dfrac { lambda} {d}}) gamma chap (1- gamma right) right)}$.

Natijada, har qanday to'plam ${ displaystyle chap ({ dfrac {dn} {2}} o'ng) chap ( gamma ^ {2} + chap ({ dfrac { lambda} {d}} o'ng) gamma chap (1- gamma o'ng) o'ng)}$ o'zgaruvchilar hech bo'lmaganda ega bo'ladi ${ displaystyle gamma n}$ qo'shnilar sifatida cheklovlar. Shunday qilib, har bir cheklov uchun o'rtacha o'zgaruvchilar soni: ${ displaystyle left ({ dfrac {({ dfrac {2nd} {2}}) left ( gamma ^ {2} + ({ dfrac { lambda} {d}}) gamma left ( 1- gamma right) right)} { gamma n}} right)}$${ displaystyle = d chap ( gamma + ({ dfrac { lambda} {d}}) chap (1- gamma right) right)}$ ${ displaystyle rightarrow (2)}$

Shunday qilib, agar ${ displaystyle d left ( gamma + ({ dfrac { lambda} {d}}) chap (1- gamma right) right) < gamma d}$, keyin nisbiy vazn so'zi ${ displaystyle left ( gamma ^ {2} + ({ dfrac { lambda} {d}}) gamma left (1- gamma right) right)}$, ning kod so'zi bo'lishi mumkin emas ${ displaystyle C (B, S)}$. Tengsizlik ${ displaystyle (2)}$ uchun mamnun ${ displaystyle gamma < chap ({ dfrac {1 - ({ dfrac { lambda} {d}})} { delta - ({ dfrac { lambda} {d}})}} o'ng )}$. Shuning uchun, ${ displaystyle C (B, S)}$ nisbiy vaznning nolga teng bo'lmagan kod so'ziga ega bo'lishi mumkin emas ${ displaystyle chap ({ dfrac { delta - ({ dfrac { lambda} {d}})} {1 - ({ dfrac { lambda} {d}})}} o'ng) ^ { 2}}$ yoki kamroq.

Matritsada ${ displaystyle G}$, deb taxmin qilishimiz mumkin ${ displaystyle lambda / d}$ bilan chegaralangan ${ displaystyle 1}$. Ning bu qiymatlari uchun ${ displaystyle d}$ unda ${ displaystyle d-1}$ g'alati tub, ketma-ketliklarining aniq konstruktsiyalari mavjud ${ displaystyle d}$ - har ikki grafaga o'xshash o'zboshimchalik bilan ko'p sonli vertikal grafikalar ${ displaystyle G}$ ketma-ketlikda a Ramanujan grafigi. U tengsizlikni qondirgani uchun Ramanujan grafigi deb ataladi ${ displaystyle lambda (G) leq 2 { sqrt {d-1}}}$. Grafada ma'lum kengayish xususiyatlari ko'rinadi ${ displaystyle G}$ o'zgacha qiymatlar orasidagi ajratish sifatida ${ displaystyle d}$ va ${ displaystyle lambda}$. Agar grafik ${ displaystyle G}$ bu Ramanujan grafigi, keyin bu ifoda ${ displaystyle (1)}$ bo'ladi ${ displaystyle 0}$ oxir-oqibat ${ displaystyle d}$ katta bo'ladi.

Zemor algoritmi

Quyida yozilgan takroriy dekodlash algoritmi tepaliklar bilan almashtiriladi ${ displaystyle A}$ va ${ displaystyle B}$ yilda ${ displaystyle G}$ va kod kodini tuzatadi ${ displaystyle C_ {o}}$ yilda ${ displaystyle A}$ va keyin u kod so'zini tuzatish uchun o'tadi ${ displaystyle C_ {o}}$ yilda ${ displaystyle B}$. Bu erda grafaning bir tomonidagi tepalik bilan bog'langan qirralar u tomonning boshqa tepasiga to'g'ri kelmaydi. Aslida, tugunlar to'plami qaysi tartibda bo'lishi muhim emas ${ displaystyle A}$ va ${ displaystyle B}$ qayta ishlanadi. Verteksni qayta ishlash parallel ravishda ham amalga oshirilishi mumkin.

Kod hal qiluvchi ${ displaystyle mathbb {D}: mathbb {F} ^ {d} rightarrow C_ {o}}$dekoderni anglatadi ${ displaystyle C_ {o}}$ dan kam bo'lgan kodli so'zlar bilan to'g'ri tiklanadi ${ displaystyle chap ({ dfrac {d} {2}} o'ng)}$ xatolar.

Kod hal qiluvchi algoritmi

Qabul qilingan so'z: ${ displaystyle w = (w_ {e}), e in E}$
${ displaystyle z leftarrow w}$
Uchun ${ displaystyle t leftarrow 1}$ ga ${ displaystyle m}$ qil //${ displaystyle m}$ takrorlash soni
{if (${ displaystyle t}$ g'alati) // Bu erda algoritm o'zining ikkita tepalik to'plami o'rtasida o'zgarib turadi.
${ displaystyle X leftarrow A}$
boshqa ${ displaystyle X leftarrow B}$
Takrorlash ${ displaystyle t}$: Har bir kishi uchun ${ displaystyle v in X}$, ruxsat bering ${ displaystyle (z) _ {v} leftarrow mathbb {D} ((z) _ {v})}$ // Kod hal qilish ${ displaystyle z_ {v}}$ eng yaqin kod so'ziga.
}
Chiqish: ${ displaystyle z}$

Algoritmni tushuntirish

Beri ${ displaystyle G}$ ikki tomonlama, to'plam ${ displaystyle A}$ tepaliklar chekka to'plamining bo'linishini keltirib chiqaradi ${ displaystyle E}$ = ${ displaystyle cup _ {v in A} E_ {v}}$ . To'plam ${ displaystyle B}$ boshqa bo'limni keltirib chiqaradi, ${ displaystyle E}$ = ${ displaystyle cup _ {v in B} E_ {v}}$ .

Ruxsat bering ${ displaystyle w in {0,1 } ^ {N}}$ qabul qilingan vektor bo'ling va buni eslang ${ displaystyle N = dn}$. Algoritmning birinchi takrorlanishi induksiya qilingan kod uchun to'liq dekodlashni qo'llashdan iborat ${ displaystyle E_ {v}}$ har bir kishi uchun ${ displaystyle v in A}$ . Bu shuni anglatadiki, almashtirish uchun, har bir kishi uchun ${ displaystyle v in A}$, vektor ${ displaystyle left (w_ {v (1)}, w_ {v (2)}, ldots, w_ {v (d)} right)}$ ning eng yaqin kod so'zlaridan biri tomonidan ${ displaystyle C_ {o}}$. Qirralarning pastki to'plamlaridan beri ${ displaystyle E_ {v}}$ uchun ajratilgan ${ displaystyle v in A}$, bularning dekodlanishi ${ displaystyle n}$ subvektorlari ${ displaystyle w}$ parallel ravishda amalga oshirilishi mumkin.

Takrorlash yangi vektor beradi ${ displaystyle z}$. Keyingi takrorlash avvalgi protsedurani ${ displaystyle z}$ lekin bilan ${ displaystyle A}$ bilan almashtirildi ${ displaystyle B}$. Boshqacha qilib aytganda, u vertikallari tomonidan induktsiya qilingan barcha subvektorlarning dekodlanishidan iborat ${ displaystyle B}$. Kelgusi takrorlashlar ushbu ikki bosqichni navbatma-navbat vertikallari tomonidan induksiya qilingan subvektorlarga parallel dekodlashni qo'llaydi. ${ displaystyle A}$ va tepaliklari tomonidan induktsiya qilingan subvektorlarga ${ displaystyle B}$.
Eslatma: [Agar ${ displaystyle d = n}$ va ${ displaystyle G}$ to'liq ikki tomonlama grafik, keyin ${ displaystyle C}$ mahsulot kodidir ${ displaystyle C_ {o}}$ o'zi va yuqoridagi algoritm bilan mahsulot kodlarini tabiiy qattiq iterativ dekodlashgacha kamaytiradi].

Mana, takrorlash soni, ${ displaystyle m}$ bu ${ displaystyle chap ({ dfrac {( log {n})} { log (2- alfa)}} o'ng)}$. Umuman olganda, yuqoridagi algoritm Hamming og'irligi ko'p bo'lmagan kod so'zini tuzatishi mumkin ${ displaystyle ({ dfrac {1} {2}}). alfa N delta chap (({ dfrac { delta} {2}}) - ({ dfrac { lambda} {d}} ) o'ng) = chap (({ dfrac {1} {4}}). alfa N ( delta ^ {2} -O ({ dfrac { lambda} {d}}) o'ng)}$ ning qiymatlari uchun ${ displaystyle alfa <1}$. Bu erda dekodlash algoritmi o'lchov sxemasi sifatida amalga oshiriladi ${ displaystyle O (N log {N})}$ va chuqurlik ${ displaystyle O ( log {N})}$ Bu xato vektorining og'irligi kamroq bo'lganligi sababli kod so'zini qaytaradi ${ displaystyle alpha N delta ^ {2} (1- epsilon) / 4}$ .

Teorema

Agar ${ displaystyle G}$ har qanday kishi uchun etarlicha yuqori darajadagi Ramanujan grafigi ${ displaystyle alfa <1}$, dekodlash algoritmi tuzatishi mumkin ${ displaystyle ({ dfrac { alpha delta _ {o} ^ {2}} {4}}) (1- in) N}$ xatolar, ichida ${ displaystyle O ( log {n})}$ dumaloq (bu erda katta ${ displaystyle O}$ yozuvlar bog'liqlikni yashiradi ${ displaystyle alpha}$). Buni bitta protsessorda chiziqli vaqtda amalga oshirish mumkin; kuni ${ displaystyle n}$ protsessorlarni har bir tur doimiy ravishda amalga oshirish mumkin.

Isbot

Kod hal qilish algoritmi qirralarning qiymatiga va chiziqlilikka befarq bo'lgani uchun, biz uzatilgan kod so'zni barcha nol - vektor deb hisoblashimiz mumkin. Qabul qilingan kod so'zi bo'lsin ${ displaystyle w}$. Dekodlash paytida noto'g'ri qiymatga ega bo'lgan qirralarning to'plami ko'rib chiqiladi. Bu erda noto'g'ri qiymat bilan biz demoqchimiz ${ displaystyle 1}$ bitlarning har qandayida. Ruxsat bering ${ displaystyle w = w ^ {0}}$ kod so'zining boshlang'ich qiymati bo'lishi, ${ displaystyle w ^ {1}, w ^ {2}, ldots, w ^ {t}}$ birinchi, ikkinchisidan keyin qiymatlar bo'ling. . . ${ displaystyle t}$ dekodlash bosqichlari. Bu yerda, ${ displaystyle X ^ {i} = {e in E | x_ {e} ^ {i} = 1}}$va ${ displaystyle S ^ {i} = {v in V ^ {i} | E_ {v} cap X ^ {i + 1}! = emptyset}}$. Bu yerda ${ displaystyle S ^ {i}}$ kodidagi so'zni muvaffaqiyatli hal qila olmagan tepaliklar to'plamiga to'g'ri keladi ${ displaystyle i ^ {th}}$ dumaloq. Yuqoridagi algoritmdan ${ displaystyle S ^ {1}$ chunki har bir takrorlashda muvaffaqiyatsiz tepalar soni tuzatiladi. Biz buni isbotlashimiz mumkin ${ displaystyle S ^ {0}> S ^ {1}> S ^ {2}> cdots}$Bu kamayib boruvchi ketma-ketlikdir. ${ displaystyle | S_ {i + 1} | <= ({ dfrac {1} {2- alfa}}) | S_ {i} |}$. Biz taxmin qilgandek, ${ displaystyle alfa <1}$, yuqoridagi tenglama a da joylashgan geometrik kamayish ketma-ketligi. Shunday qilib, qachon ${ displaystyle | S_ {i} |$, Bundan ko'proq ${ displaystyle log_ {2- alfa} n}$ turlar kerak. Bundan tashqari, ${ displaystyle sum | S_ {i} | = n sum ({ dfrac {1} {(2- alfa) ^ {i}}}) = O (n)}$va agar biz amalga oshirsak ${ displaystyle i ^ {th}}$ dumaloq ${ displaystyle O (| S_ {i} |)}$ vaqt, keyin umumiy ketma-ket ishlash vaqti chiziqli bo'ladi.

Zemor algoritmining kamchiliklari