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

Рийд-Соломоны кодууд (Англи: Reed-Solomon codes) нь тоон холбоо (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<2t (s алдааны тоо, r алдагдлын тоо) бол анх дамжуулагдсан код үг бүрэн сэргээгдсэн байна

ЭСВЭЛ

2. Decoder нь анхны дамжуулагдсан код үгийг бүрэн сэргээж чадахгүйгээ мэдээд энэ тухайгаа мэдэгдэнэ.

ЭСВЭЛ

3. Decoder нь буруу decode-члол хийж, үүнийхээ талаар ямар ч мэдээлэл өгөгдөлгүйгээр анх дамжуулсан код үгийг буруу сэргээнэ. Дээрх 3 төрлийн үр дүнгийн илрэх магадлал нь тухайн үед ашиглагдаж байгаа Reed-Solomon код болон алдааны тоо, тархалтаас хамаарна. Кодчлолын ашиг:

Reed-Solomon ны кодыг хэрэглэх нь хэрэглээгүйгээсээ үргэлж илүү давуу талтай байдаг. Өөрөөр хэлбэл Reed-Solomon ны код хэрэглэсний дараа алдаа үлдэх магадлал нь Reed-Solomon ны код хэрэглээгүй байх үед гэрэх алдааны магадлалаас ихэнхдээ маш бага байдаг. Үүнийг кодчлолын ашиг гэнэ.

Жишээ:

Нэгэн тоон холбооны систем 10-9 BER(Bit Error Ratio - бит алдааны харьцаа)-т ажиллахаар зохион бүтээгдсэн гэж үзье. Өөрөөр хэлбэл 109 битээс 1-с ихгүй нь алдаанд илэрсэн. Тэгвэл энэ үр дүн нэг бол дамжуулагчийн хүчин чадлыг хэт нэмэгдүүлснээр эсвэл Reed-Solomon юм уу өөр ямар нэг алдаа засах код нэмснээр л бий болох боломжтой. Reed-Solomon код нь системийг аль болох бага дамжуулагчийн чадал ашиглан дээрх хэмжээний BER-тай ажиллах боломжийг олгодог. Энэхүү Reed-Solomon ны тусламжтайгаар хэмнэсэн дамжуулагчийн хүчин чадлыг Кодчлолын ашиг гээд байгаа юм.

3. Reed-Solomon ны кодыг encode-лох болон decode-лох архитектур. Reed-Solomon encode, decode-лолт нь програм хангамж эсвэл онцгой зориулалтын техник хангамжид ашиглагдаж болно.

Төгсгөлөг (Галойсын) мужийн арифметик:

Reed-Solomon код нь Төгсгөлөг муж буюу Галойсын муж хэмээгдэх математикын ойлголтоос үндэслэлтэй. Төгсгөлөг мужийн нэгэн шинж чанар бол тухайн нэг мужийн элементүүд дээр гүйцэтгэсэн арифметик үйлдүүд (нэмэх, хасах, үржих, хуваах г.м. ) нь үргэлж тухайн муж дээрээ шийдтэй гэсэн чанар юм. Reed-Solomon encoder/decoder нь эдгээр арифметик үйлдүүдийг биелүүлэх шаардлагатай. Эдгээр үйлдүүдийг хэрэгжүүлэхэд онцгой техник хангамж эсвэл програм хангамж шаардлагатай.

Үүсгэгч олон гишүүнт:

Reed-Solomon код үгийг тусгай олон гишүүнтийг ашиглан үүсгэдэг. Бүх хүчинтэй код үг нь үүсгэгч олон гишүүнтдээ хуваагддаг(үлдэгдэлгүйгээр) байна. Үүсгэгч олон гишүүнт ерөнхийдөө доорх хэлбэрийнх байна.

g(x)=(x-ai)(x-ai+1)...(x-ai+2t) Харин код үг нь доорх томъёог ашиглан байгуулагддаг байна.

c(x)=g(x).i(x)

энд

g(x) нь үүсгэгч олон гишүүнт, i(x) нь блок мэдээлэл, c(x) нь хүчинтэй код үг ба а нь мужийн үндсэн элемэнт.

Жишээ:

 RS(255, 249)-н үүсгэгч g(x)=(x-a0)(x-a1)(x-a2)(x-a3)(x-a4)(x-a5)
 g(x)=x6+g5x5+g4x4+g3x3+g2x2+g1x1+g0

3.1 Encoder-н архитектур. Системтэй буюу дэс дараатай Reed-Solomon дахь 2t ижил төстэй тэмдэг нь дараах байдалаар өгөгдсөн гэе.

 p(x)=i(x).xn-k mod g(x)

Дараах диаграмд системтэй RS(255, 249) encoder-н архитектурыг үзүүлэв.

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-с харьцангуй бага зардлыг үүсгэдэг.