Ta‟lim vazirligi muhammad al-xorazmiy nomidagi

Xatoliklarni o„rama kod bilan tuzatish. Yuqorida ko‗rsatilganidek, har bir kodli kombinatsiyaga trellisdagi (trellis - tizimning holatlarini bitta qadamda o‗zgarishi sxemasi) o‗z yo‗li mos keladi. Lekin teskarisi to‗g‗ri bo‗lmaydi. Istalgan olingan ketma-ketlik uchun ham trellisda yo‗lni chizib bo‗lavermaydi. Masalan, F=(11,11,11) yoki F=(01, 01, 01) kabi kombinatsiyalar uchun yo‗llar mavjud emas. Shuningdek 01 yoki 10 dan boshlanadigan kodli kombinatsiyalar ham mavjud bo‗lmaydi. F dagi bunday juftliklarning bo‗lishi xatoliklarning
borligini bildiradi. Ma‘lumotlarni kanal bo‗yicha uzatilishida halaqitlar bilan ikkilik kodli ketma-ketliklarning buzilishi qandaydir bitning qiymatini qarama-qarshisiga o‗zgarishidan iborat. Agar ma‘lumotlar bloklar bilan kodlansa, u holda blokdagi xatoliklar soni qabul qilingan va dastlabki so‗zlar orasidagi mos kelmasliklar soniga teng bo‗ladi. Eslatamizki, xabarlar orasidagi masofa mos kelmaydigan razryadlar soni sifatida aniqlanadi. Shuning uchun uzatiladigan kodli kombinatsiyadagi har bir xatolik dastlabki qiymatdan uning masofasini oshiradi. Mos ravishda yangi, buzilgan kodli kombinatsiya buzilgan trellis yo‗liga ega bo‗ladi. Ayrim vaziyatlarda esa yo‗l bo‗lmasligi ham mumkin. Xatoliklarni tuzatish masalasi F uchun bo‗lishi mumkin yo‗llar to‗plamini qurilishi va ular orasidan olingan F kodli kombinatsiya bilan minimal masofaga ega bo‗lgan yo‗lni tanlashdan iborat.
1-misol. Uzatiladigan axborot xabari quyidagi ko‗rinishga ega bo‗lsin: a=(1010). Bu xabarga quyidagi kodli kombinatsiya mos

keladi: F = (11,10, 00, 01). Uzatiladigan kodli kombinatsiyada

F (x)

=(11,11,00,10) xatolik vujudga kelsin. Axborot ketma-ketligini qayta tiklash zarur.
Yechish. Birinchi qadamda Trellisning S₀(t=0) tugunidan boshlab

biz olingan
F (x)
kodli kombinatsiya mos vaznli qirrani tanlaymiz. Birinchi

simvollar juftligi uchun biz 11 qiymatga egamiz. Trellis uchun bu S₀ tugundan chiqadigan pastki qirraga mos keladi. Biz t=1da S₂ tugunga o‗tdik.

Ikkinchi qadamda trellisning S₂(t=1) tugunidan biz olingan

F (x)

kodli kombinatsiyaning ikkinchi juftligiga mos 11 vaznli qirrani tanlashimiz kerak. Bunday vaznli qirra bizda yo‗q, u holda biz har ikkala mavjud variantlarni ko‗rib chiqamiz. Yuqoridagi qirra uchun 10 vaznga egamiz. 10 va 11 orasidagi masofani S₁ (t=2) tugunga yozamiz. Pastdagi

qirra uchun 01 vaznga egamiz. 01 va 11 orasidagi masofani S₃ (t=2)
tugunga yozamiz.

Olingan kodli kombinatsiyaning uchinchi juftligi 00 qiymatga ega bo‗ladi.

Uchinchi qadamda biz ikkita marshrutga ega bo‗lamiz. Trellisning S₁(t=2) tugunidan 11 va 00 vaznli ikkita qirra chiqadi. Ular va qabul qilingan qiymat orasidagi masofani mos tugunlarda S₀ uchun 2 va S₂ uchun 0 yozamiz. S₃ tugundan 01 va 10 vaznli ikkita qirralar ham chiqadi. Ular va qabul qilingan 00 qiymat orasidagi 1 ga teng masofa S₁ va S₃(t=3) tugunlarga yoziladi.
To‗rtinchi qadamda bizga maksimal vaznli tugunlarni tashlab yuborish zarur bo‗ladi, chunki ular uzatiladigan ketma-ketliklardan eng kuchli farqlanadigan ketma-ketliklarga mos keladi. Keyingi yo‗l uchun biz faqat S₂ tugunni qoldiramiz. Olingan kodli kombinatsiyaning to‗rtinchi juftligi 10 qiymatga ega. Trellisning S₂(t=3) tugunidan 10 vaznli yuqoridagi qirra chiqadi va biz bu qirra bo‗yicha S₁ tugunga o‗tamiz.

Xulosada biz tugunlardan minimal yig‗indi masofali o‗tadigan yo‗lni aniqlashimiz kerak. Har bir qadamda biz yuqoridagi qirraga mos ravishda 0 qiymatni, pastki qirraga esa 1 qiymatni qo‗yamiz. Koddan chiqarilgan axborot ketma-ketligi quyidagi ko‗rinishga ega bo‗ladi: a =(1010)