| T(x) xatolar lokatorlari ko‗phadini hisoblashni formula ko‗rinishga
keltiramiz: S1; S2;…;S2t sindrom komponentlari aniqlangan bo‗lsin va
T0(x) = 1, V0(x) = 1 , L0 = 0 boshlang‗ich shartda
L
n Tj Sn j j0
tenglik o‗rinli bo‗lsin.
Bu yerda Δn - GF(2m), n = 1:2, …., 2t maydon elementlari orqali hisoblanuvchi hisoblash xatoligi;
V(x) – qo‗shimcha element.
Agar
n 0 va
2 Ln1 n 1
shart bajarilsa, u holda
Ln n Ln1
va B
( x) 1 T
( x)
bo‗ladi.
n n n1
Agar
2Ln1 n 1 shart bajarilmasa, u holda
Ln Ln1 va
Bn (x) x Bn1 (x)
bo‗ladi.
bo‗ladi. U holda T2 t(x) ko‗pxad kichik darajali ko‗pxad
Berlekemp – Messi algoritmining blok-sxemasi 3.11 – rasmda keltirilgan.
Xatolar lokatorlarining ko‗phadi hisoblangandan so‗ng, xatolar lokatorlarining ko‗phadini ildizlari izlanadi. Bu esa Chen protsedurasi orqali amalga oshiriladi. U GF(2m) maydonning hamma elementlarini T(x) – xatolar lokatorlarining ko‗phadiga ketma-ket qo‗yib chiqishdan iborat. T(x) ko‗phadga qo‗yganda uni nolga aylantiradigan GF(2m) maydonning elementlari, bu ko‗phadning ildizlari deyiladi. Xatolar lokatorlarining ko‗phadini ildizlariga teskari bo‗lgan qiymat – xato sodir bo‗lgan pozitsiyalarni bildiradi.
Rid – Solomon kodini dekoderlashning keyingi bosqichi Y1; Y2; Yt xatolar qiymatini topishdan iborat. Xatolar qiymatini topishda Forni algoritmidan foydalaniladi. Bu algoritmni keltirishdan avval xatolar lokatorlarining ko‗phadini quyidagi ko‗rinishda yozamiz:
t
T (x) Tt x
Tt 1
xt1 ... T
x 1
i
1
ildizlari
x 1, i 1;2;...; t
dan iborat.
n = n +1
Yo‗ Hа
2Ln-T ≤ n-1
Hа
Yo‗
Yo‗
degT(x)=Ln
n = 2t
Hа Dekoderning keyingi bosqichiga
Qabul qilingan kombinatsiyada
t dan ortiq xato bor
3.11-rasm. Berlekemp – Messi algoritmi
Sindromlar ko‗phadini quyidagicha yozamiz:
i
2 t 2 t t
X
j
S (x) S j X
Y i X j j
j 1
j 1 i1
Endi S(x) – sindromlar ko‗pxadi bo‗yicha (x) – xatolar qiymatining ko‗phadini yozish mumkin:
(x) S (x) T (x)(mod
x 2 t )
mod x2t ning ko‗rsatkichi x ga kiruvchi xadlarning darajasi 2t dan oshmasligini bildiradi.
Bu ko‗pxadni yana quyidagicha yozish mumkin:
t
(x) Yi Xi П (1 - Xi X )
i1
va ushbu ifodadan Y i ni topish mumkin:
Yi
(x) T ' (x)
T‘(x) – t (x) dan olingan hosila.
Rid-Solomon kodida kodlangan axborotlarni dekodlash algoritmini tushuntirib o„tamiz. Dekodlash algoritmi (3.12-rasm) quyidagi ketma-ketlik (blok)lardan iborat:
(19) – t1 xatolar soni kiritiladi;
(20) – n1 kodli kombinatsiyadagi xato o‗rni kiritiladi;
(21) – xatolar qiymati v (d) kiritiladi;
(22) – xato o‗rni va uning qiymati chop etiladi;
(23) – joylashgan o‗rniga bog‗liq holda xatolarni n1 kodli kombinatsiyaga kiritiladi va n2 kodli kombinatsiya hosil bo‗ladi;
(24) – xato kodli kombinatsiya n2 chop etiladi. Keyingi bosqich – xatolar sindromlari S(x) ni hisoblash.
(25) – sindromlar soni beriladi;
(26) – sindromni tashkil etgan elementlar soni beriladi;
3.12-rasm. Rid-Solomon kodini dekodlash algoritmi
3.12-rasm. Rid-Solomon kodini dekodlash algoritmi (davomi)
3.12-rasm. Rid-Solomon kodini dekodlash algoritmi (davomi)
(27) – quyidagi formula bo‗yicha sindromlar qiymatlari S
hisoblanadi:
j
n 2
X
S j Yi i i 1
o‗rni.
Y – Galua maydoni elementi ning qiymati;
X – Galua maydoni elementining kodli kombinatsiyada joylashish
(28) – sindrom qiymatlari tekshiriladi. Agar hamma sindromlar
nolga teng bo‗lsa, unda kombinatsiyada xato yo‗q va 11-blokka o‗tiladi. 11-blokda n2 kodli kombinatsiyani chop etish bajariladi va dastur ishi yakunlanadi. Agar sindromlarning ixtiyoriy bittasi ham nolga teng bo‗lmasa, unda xato mavjud deb topiladi va uni aniqlash hamda to‗g‗irlash talab etiladi;
12 (30) – sindromlarning ko‗pxadi S(x) hisoblanadi.
Endi Berlekemp-Messi algoritmi bo‗yicha xatolar lokatorlarining ko‗phadini hisoblashga o‗tiladi.
13 (31) – algoritm ishini ta‘minlash maqsadida boshlang‗ich shartlar kiritiladi;
14 (32) – Berlekemp-Messi algoritmi bo‗yicha izlash qadamining nomeri beriladi;
15 (33) – xatolik n hisoblanadi;
16 (34) – bu xatolik qiymati tekshiriladi. Agar n 0, u holda Tn(x) ko‗pxad 17-blokdagi formula bo‗yicha hisoblanadi. Agar n = 0 bo‗lsa, u holda Tn(x) oldingi ko‗phad Tn-1(x) ga teng (18-blok);
19 (37) 2Ln-1 n-1 shart tekshiriladi.
L – xatolar soni;
n - izlash qadami.
Agar ushbu shart bajarilmasa, xatolar soni L oldingi qiymati ( Ln-1) ga teng bo‗lib qoladi (21-blok). Agar shart bajarilsa xatolar soni L ortadi (20- blok);
(40) n = 2t – xatolar lokatorlarining ko‗phadini izlash qadami 2t qiymatdan oshib ketmasligi kerak degan shart tekshiriladi. Agar ushbu shart bajarilsa, u holda 23-blokka o‗tiladi, aks holda 14-blokka;
(41) T(x) ko‗phad darajasi tekshiriladi. U topilgan xatolar sonidan oshmasligi kerak. Agar shart bajarilmasa, unda: «Qabul qilingan kombinatsiyada t dan ortiq xato mavjud» - degan xabar chop etiladi va dastur tugallanadi. Agar shart bajarilsa, unda 24-blokka o‗tiladi;
(42) – xatolar qiymatlarining ko‗pxadi (x) hisoblanadi;
(43) – T(x) ning hosilasi topiladi;
(44) – natija chop etiladi;
(45) – Chen protsedurasiga mos ravishda xatolar o‗rnini aniqlash uchun siklning boshi beriladi;
(46) – xatolar lokatorlarining ko‗phadi T(x) ni ildizlarini topish uchun tekshirishlar soni aniqlanadi;
(47) – xatolar lokatorlarining ko‗phadi ildizlarini hisoblash uchun Galua maydonining boshlang‗ich elementi beriladi;
(48) – Xatolar mavjud bo‗lgan pozitsiyalarning nomerlari hisoblanadi. Buning uchun Galua maydonining hamma elementlari navbatma – navbat T(x) ko‗pxadga qo‗yib tekshiriladi;
(49) – T(x) ko‗phad tekshiriladi. Agar T(x) = 0 bo‗lsa, unda ushbu qiymat ildiz deb topiladi va T(x) ko‗phad ildizining teskari qiymati hisoblanadi (34-blok). Bu qiymat esa xato yuz bergan pozitsiya nomerini bildiradi;
(50) – Galua maydonining navbatdagi elementiga o‗tiladi;
(51) – T(x) ning ildizlarini topishda Galua maydonining hamma elementlari ishtirok etganligi tekshiriladi;
(53) – xatolar lokatorlarining ko‗phadini navbatdagi ildizini aniqlashga o‗tiladi;
(54) – ko‗pxadning hamma ildizlari topilganligi tekshiriladi;
(55) – xatolar soni beriladi;
(56) – xatolarning qiymatlarini hisoblash uchun boshlang‗ich element beriladi;
(57) – xatolarning qiymatlari hisoblanadi;
(58) – n2 kombinatsiyadagi xatolarni to‗g‗irlash amalga oshadi.
Buning uchun esa hisoblab topilgan xatolarning qiymatlarini kombinatsiyadagi xatolarning qiymatlari bilan o‗zaro mod m bo‗yicha qo‗shiladi;
(59) – to‗g‗irlangan kodli kombinatsiya chop etiladi;
(60) – dastur ishi yakunlanadi.
Rid-Solomon kodida kodlangan axborotlar dekoderi 3.13-rasmda blok sxema ko‗rinishida berilgan.
|
O‗zgarishlarni hisoblash
|
|
|
| |
Tenglamani yeching
|
|
|
|
|
3.13-rasm. Rid-Solomon kodini dekodlash blok-sxemasi
Dekoder kirishiga kodlangan axborot va xatolar vektori yig‗indisidan iborat bo‗lgan kodli kombinatsiya F(x) kelib tushadi. F(x) kodli kombinatsiya buferda saqlanadi. Shuningdek ushbu F(x) kodli kombinatsiya o‗zgarishlarni hisoblash qurilmasiga ham tushadi. Unda sindromlar hisoblanadi. Sindromlardan xatolar lokatorlarining ko‗pxadi T(x) ni aniqlovchi tenglamani yechishda foydalaniladi.
Dekoder tenglamani yechish bilan bir vaqtning o‗zida hosil qilinuvchi xatolar qiymatlarining ko‗pxadi (x) ni hisoblashni amalga oshiradi.
«Chen prodedurasi»ni bajaruvchi qurilma xatolar o‗rnini aniqlaydi.
«Xatolarni hisoblash» blokida esa xatolarning qiymatlari aniqlanadi va bu qiymatlar ventil hamda summator yordamida, xatolar mavjud bo‗lgan pozitsiyadagi simvollar bilan qo‗shiladi. Shu tariqa to‗g‗irlangan kodli kombinatsiya f (x) summator chiqishida hosil qilinadi.
| 