Рийд-Соломоны код

**Рийд-Соломоны кодууд** () нь тоон холбоо (digital communication) болон хадгалах байгууламж (storage) зэрэгт өргөнөөр хэрэглэгддэг блок суурьтай алдаа засварлахад зориулсан кодууд юм. Reed-Solomon кодууд нь маш олон төрлийн системд алдаа засварлахад ашиглагддаг бөгөөд үүнд дараах системүүд багтдаг:

* Хадгалах төхөөрөмжүүд (storage devices). Жишээ нь: кассет, CD, DVD, бар код гэх мэт.  
* Утасгүй буюу үүрэн холбоо (wireless or mobile communications). Жишээ нь: гар утас, бичил долгионы холбоос гэх мэт  
* Хиймэл дагуулын холбоо  
* Тоон системийн зурагт болон DVB (Digital Video Broadcasting - тоон системийн видео цацалт) 
* Өндөр хурдны модемууд. Тухайлбал: ADSL (asymmetric digital subscriber line), xDSL гэх мэт.

## Reed-Solomon кодуудын шинж чанар 
Reed-Solomon кодууд нь шугаман блок кодууд бөгөөд BCH кодуудын дэд хэсэг юм. (BCH code гэдэг нь алдаа засахад ашиглагддаг Bose, Chaudhuri, Hocquenghem хэмээх математикчдын нээсэн код юм).

Reed-Solomon код нь s тооны бит тэмдэгтүүдтэй RS(n,k) гэж тэмдэглэгддэг. 
Тодруулбал, тус бүрдээ s бит бүхий k тооны дата тэмдэгтүүдийг encoder нь аваад, ижил төстэй тэмдэгтүүд (parity symbols) нэмж n тооны тэмдэгт код болгодог. Тэгэхээр тус бүрдээ s тооны битүүд бүхий n-k ширхэг ижил төстэй (parity) тэмдэгтүүд байна гэсэн үг юм. 
Харин Reed-Solomon decoder нь алдаа агуулсан t хүртэлх тооны тэмдэгтүүд бүхий кодыг засч чадна. Эндэ 2t=n-k байна. Доорх диаграмд нийтлэг Reed-Solomon кодыг дүрслэв. (Энэ нь системтэй буюу дэс дараатай код гэгддэг. Учир нь өгөгдөл нь өөрчлөгдөлгүй үлдэж, ижил төстэй тэмдэгтүүд нэмэгдсэн байгаа юм) 

 

Жишээ: 

Түгээмэл нэгэн Reed-Solomon код нь 8 бит тэмдэгтүүд бүхий RS(255, 223) юм. Код тус бүр 255 код үг байтуудтай ба үүний 223 байтууд нь өгөгдөл, 32 байтууд нь ижил төстэй (parity) тэмдэгт. 
Энэ нь: 
       n= 255, k= 223, s= 8
       2t=255-223=32, t=16 
Тэгэхээр decoder нь аль нэг 16 тэмдэгт алдааг засч чадна. Өөрөөр хэлбэл, кодын аль ч хамаагүй хэсэгт байгаа 16 хүртэлх байтууд автоматаар засагдах боломжтой гэсэн үг. 
S хэмжээний тэмдэгт өгөгдсөн гэж үзвэл, Reed-Solomon кодын maximum код үгийн урт нь n=2s-1 байна. 
Жишээлбэл, 8 бит тэмдэгтүүдтэй кодын maximum урт нь 255 байт. (n=28-1=255)
Reed-Solomon код нь тодорхой тооны тэмдэгт бүхий өгөгдлийг (таамгаар) 0-р орлуулаад, тэднийгээ дамжуулалтгүйгээр decoder-т нь дахин оруулах замаар хялбарчлагдах боломжтой.

Жишээ: 

Дээрх жишээнд өгөгдсөн (255, 223) нь (200, 168) болж хялбарчлагдаж болно. Тэгэхээр Encoder нь 168 байт өгөгдөл бүхий блокийг авч, (таамгаар) 55 байт 0 нэмээд (255, 223) код үгийг үүсгэнэ. Ингээд зөвхөн 168 байт өгөгдөл, 32 байт ижил төстэй тэмдэгт (parity) дамжуулах юм. Encode-лох болон Decode-лоход шаардагдах боловсруулалтын "чадал"-н хэмжээ нь код үг бүрт буй ижил төстэй тэмдэгтүүдийн (parity symbols) тоо ширхэгтэй холбоотой. t-н утга их байх тусам тэр хэмжээний алдаанууд засагдах боловч тэр хэрээрээ илүү их хэмжээний тооцооллын хүчин чадал шаардана гэсэн үг юм. 

Тэмдэгт алдаа:
1 тэмдэгт алдаа гэдэг нь тухайн нэг тэмдэгтийн зөвхөн 1 бит нь буруу байхад эсвэл бүр тухайн тэмдэгтийн бүх битүүд буруу байхад гардаг. 

Жишээ: 

RS(255, 223) нь 16 тэмдэгт алдааг засч чадна. Муугаар бодоход, тус бүр нь өөр өөр тэмдэгтэд (байт) байгаа 16 бит алдаа гарч болох ба decoder 16 бит алдааг л засна. Харин сайнаар бодоход, 16 бүтэн байт алдаа гарахад decoder 16*8 бит алдаа засна. 
Reed-Solomon код нь ялангуяа код үг дэх дараалсан битүүд алдаанд илрэхэд ашиглахад илүү тохиромжтой. 

*Decode-члох:*
Reed-Solomon алгебрийн decode-члох үйл явц нь алдаа болон алдагдлыг засдаг. Буруу бичигдсэн тэмдэгтийн байр/орон зай олдох явцыг алдагдал гэнэ. Decoder нь t хүртэлх алдаа эсвэл 2t хүртэлх алдагдлыг засч чаддаг. Алдагдалтай мэдээлэл нь ихэнхдээ тоон холбооны системийн demodulator-с гардаг. Өөрөөр хэлбэл demodulator-н "flag"-ууд алдаа агуулсан тэмдэгтүүд хүлээн авах нь элбэг байдаг.  
Код үгийн decode-члох явцад дараах 3 янзын үр дүн гарч болдог. 

1. Хэрэв 2s+r
6 register тус бүр 1 тэмдэгт (буюу 8 бит) агуулна. Нэг тэмдэгт дээр төгсгөлөг мужийн нийлбэр эсвэл үржвэр хийгдэнэ. 

3.2 Decoder-н архитектур. 
Reed-Solomon кодын ерөнхий архитектурыг доорх диаграмд дүрслэв. 

 

*Түлхүүр:*

* r(x) хүлээн авсан код үг 
* Si хам шинжүүд (syndromes) 
* L(x) алдааны баршил илрүүлэгч олон гишүүнт 
* Xi алдааны байршил 
* Yi алдааны хэмжээ 
* c(x) сэргээгдсэн код үг 
* v алдааны тоо ширхэг

Хүлээн авсан код үг r(x) нь анх дамжуулагдсан код үг болон алдаануудын нийлбэр. Өөрөөр хэлбэл: 
    r(x)=c(x)+e(x) 
Reed-Solomon decoder нь t хүртэлх тооны алдаа (эсвэл 2t хүртэлх тооны алдагдал)-ны байршил болон хэмжээг тодорхойлж, тэднийг засахыг оролддог. 

*Хам шинжийн тооцоолол:*

Энэ нь ижил төстэй тэмдэгтүүд (parity)-г тооцоолохтой төстэй. Reed-Solomon код үг нь зөвхөн алдаанаас хамааралтай 2t хэмжээний хам шинжийг агуулдаг. (дамжуулагдсан код үгээс харин хамаарахгүй) 
Хам шинж нь r(x)-д g(x)-н 2t язгуурыг орлуулсанаар тооцоологдох боломжтой.  

*Тэмдэгт алдааны байршилыг олох нь*

Үүнийг тооцохын тулд t хувьсагчтай тэгшитгэлүүдийг бодох шаардлага гарна. Үүнд зориулсан маш хурдан ажиллах боломжтой хэд хэдэн алгоритм байдаг. Эдгээр алгоритмууд нь Reed-Solomon кодын онцгой матриц бүтцийг ашиглан тооцооллыг маш хялбараар гүйцэтгэдэг. 
Ерөнхийдөө 2 алхам хэрэгждэг. Үүнд: 
* Алдааны байршил илрүүлэгч олон гишүүнтийг олох 
Энэ үйлдэл Berlekamp-Massey-н алгоритм эсвэл Euclid-н алгоритм-г ашигласнаар гүйцэтгэгдэх боломжтой. Хэдийгээр хэрэглэхэд амархан гэдэг талаасаа Euclid-н алгоритм илүү өргөн хүрээнд хэрэглэгддэг ч Berlekamp-Messey-н алгоритмыг хэрэглэх нь техник болон програм хангамжийг илүү их үр ашигтайгаар ажиллуулахад дөхөм болгодог. 
* Дээрх олон гишүүнтийнхээ язгууруудыг олох 
Энэ үйлдэл Chien хайлтын алгоритмын тусламжтайгаар хийгдэх боломжтой. 

*Тэмдэгт алдааны утгуудыг олох нь*

Энд ч мөн адил t хувьсагчтай тэгшитгэлүүдийг болдох шаардлага гарна. Хурдан ажиллагаатай, өргөн хүрээнд ашиглагддаг алгоритм нь Forney алгоритм юм.

4. Reed-Solomon encoder болон decoder-н хэрэгжилт. 

*Техник хангамжид хэрэглэх нь:*

Зах зээл дээрх олон тооны техник хангамжид хэрэглэсэн байдаг. Бидний ойр тойрон дахь болон системд "off-the-shelf" (off-the-shelf=стандартын) хэмээх хэлхээ нь тодорхой хэмжэний програмчлалыг дэмждэг. (жишээлбэл, RS(255,k) энд t=1-c 16 тэмдэгт). 
Сүүлийн үеийн чиглэлүүд VHDL буюу Verilog Design-ууд (логик цөм) руу чиглэж байна. Эдгээр нь энгийн IC-уудаас илүү хэд хэдэн давуу талтай. Логик цөм нь өөр бусад VHDL буюу Verilog эд ангиудтай нэгтгэгдэх боломжтой ба ингэж FPGA (Field Programmable Gate Array) эсвэл ASIC(Application specific integrated circuit)-г бий болгодог. Энэ нь цаашлаад "System on Chip" буюу ганц хэлхээн дээр олон модулиудыг нийлүүлэх боломжийг олгодог. Үйлдвэрлэлийн багтаамжаас хамаараад логик цөм нь энгийн IC-с харьцангуй бага зардлыг үүсгэдэг.

Ангилал:Кодын онол
Ангилал:Алгоритм
Ангилал:Мэдээллийн онол