Cơ sở lý thuyết thông tin và mã hóa: Phần 2

Chia sẻ: Minh Vũ | Ngày: | Loại File: PDF | Số trang:125

Thêm vào BST

Báo xấu

203
lượt xem 61
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Nối tiếp nội dung của phần 1 Tài liệu Lý thuyết thông tin và mã hóa, phần 2 cung cấp cho người học các kiến thức: Phương pháp mã hóa và giải mã, mật mã, lý thuyết thông tin và các hệ liên tục. Mời các bạn cùng tham khảo nội dung chi tiết.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Cơ sở lý thuyết thông tin và mã hóa: Phần 2

Chircmg 6 CAC PHU0NG PHAP MA HOA VA GIAI MA 6.1. MO DAU 6.1.1. Khai q uat Trong chuang truac chung ta da de cap den ma khoi va dung no de nghien cuu cac gioi han xac suat loi giai ma doi vai cac kenh co nhieu. Nhin tu goc do toan hoc, ma hoa khong gi khac la phep anh xa mot thong diep vao tap cac ma tu va giai ma la phep anh xa chuoi ma tu thu duoc vao tap cac thong diep. N hu vay bat ky phep anh xa toan hoc nao cung co the dung de ma hoa. Tuy nhien de co the giai ma mot cach duy nhat, anh xa do phai la anh xa mot-mot. Ngoai ra anh xa dung de ma hoa va giai ma phai phu hop voi dac tinh vat ly cua cac kenh truyen thong trong thuc te va phai thuan tien cho viec thuc hien bai cong nghe hien thai. Ma hoa khong chi la bien phap de truyen chinh xac mot thong diep qua mot kenh co nhieu n hu chung ta da tim hieu trong ch u an g 5. Ma hoa con la giai phap de nen d u lieu (data compression), mot trong nhung van de dang duoc cong nghe thong tin rat quan tam. Muc dich cua nen du lieu la lam giam do du thira, dong thoi cung lam tang mat do thong tin huu dung cua nguon tin can luu tru hoac chuyen tai di xa. Viec nen du lieu co irng dung rat quan trong trong ltnh vuc luu tru tep tin va o cac he thong phan tan (nhu truyen hinh Internet). Cac kv thuat nen d u lieu duoc xay dung tren nen tang lv thuyet thong tin va th u a n g d u ac nhac den nhu la mot truong hop cua ma hoa. trong do ma hoa dugc hieu mot cach chung nhat. Nhiem vu quan trong nhat cua nen du lieu bao gom viec bien doi mot xau thong tin (string) tir mot cach dien ta nao do (chang han ASCII) sang mot xau thong tin khac (chang han chuoi nhi phan) sao cho noi dung thong tin khong mat di nhimg co do dai xau ngan den muc co
Chuang 6: Cac phuang phap md hoa vd giai md 151 the. N hieu cong cu ngay nay cho phep dat do nen trung binh tren 50%, ca bi?t toi 90%. Ma hoa (mat ma hoa) cung la phu an g tien de bao mat thong tin rat hieu qua. Truoc day mat ma chi duoc dung trong mot so linh vuc dac biet (an ninh, quan su,...). N gay nay mat ma da tro thanh cong cu pho bien trong cac hoat dong kinh te, ngan hang, thuang mai dien tir,... Chung ta se de cap den mat m a trong chu an g 7. Trong ch uang nay chiing ta tap trung nghien ciru mot so phu an g phap ma hoa va giai ma da duoc phat trien va ung dung rong rai nhu ma kiem tra chan le, ma cuon, ma BCH,... Hau het cac phuong phap ma hoa va giai ma nay deu dua tren nhirng ket qua ciia ly thuyet truong (Field Theory). Vi vay de tien loi cho nhung trinh bay tiep theo, chung ta nhac lai ngan gon a day mot so khai niem co so ciia cong cu toan hoc nay. 6.1.2. Nhom, vanh va trirong N hom . Tap hop G gom cac phan tir a, b, c,... ciing voi mot toan phap © goi la mot nhom (group) neu: i. a,beG->a@beG ii. a, b, c e G —> a © (b © c) = (a © b) © c (tinh ket hop) iii. Ton tai phan tir don vi e e G sao cho a© e = e© a = aVae G iv. Voi moi a e G ton tai a ' 1 e G (goi la phan tu nghich dao ciia a) sao cho a © a ' 1 = a ’1 © a = e Nhom (G, ©) goi la nhom Abel neu a © b = b © a (tinh hoan vi). Tap hop con ciia nhom goi la nhom con (subgroup). Neu G chi co huu han cac phan tir thi goi la nhom huu han (finite group). Vi du, tat ca cac chuoi nhi phan co do dai N va phep cong modj tao thanh mot nhom huu han. PhSn tir don vi la chuoi 0. Phan tir nghich dao ciia chuoi la chinh chuoi do. Cho (G, ©) la mot nhom huu han va a e G. Ta ky hieu a 2 = a © a. a 3 = a © a © a, v.v... Vi nhom la huu han nen se co cac luv thira i va j voi j > i sao cho:
152 Ly thuyet thong tin va md hoa a' = a, = a ' © a J-' (6.1-1) Bi£u thuc (6.1-1) ham nghTa a 1'1 la phan tu d an vi. Bac (order) ciia phan tir a e G la so nguyen duong nho nhat k sao cho ak = e. De dang thay rang, voi X la so nguyen duong bat ky thi a>vk = e. N hom co tinh chat vira neu duoc goi la nhom tuan hoan (cyclic group). Can luu y rang, khai niem luy thira o day khong hoan toan giong khai niem luy thira trong so hoc thong thuong boi vi toan phap © khong dong nghTa vcri phep nhan so hoc. Vdnh. Tap hop G gom cac phan tir a, b, c,... cung voi hai toan phap © va
Chuomg 6: Cac phuang phap md hoa vd giai md 153 nghTa la h = 1. Phin tu nghjch dao cua a theo toan tir © duoc ky hieu boi a 1, phan tir nghich dao cua a theo toan tir duoc ky hieu boi a+1. Ta co the thay mot so tinh chit sau day cua truing: •a®0=0®a=0 • a * 0, b * 0 - » a < 8 > b * 0 • (a b )+1 = a+l ® b = a 0 b +1 • a * 0 , a ® b = ac-»b = c Truong (G, ©, ) voi huu han phan tir duoc goi la truang huu han (finite field). Trir&ng Galois. Tap hop G gom cac phan tir a, b, c,... ciing voi hai toan phap © va goi la truang Galois (Galois field) neu: i. (G, ©) la m ot nhom Abel voi phan tir 0 la phan tir don vi ii. Toan tir ® trong G co tinh giao hoan va tinh ket hop. iii. a * 0 , b * 0 - » a ® b * 0 iv. Phep ® co tinh phan phoi (distributive) doi voi phep ©. NghTa la a (b © c) = (a b) © (a c) Va, b, c e G. Be don gian cho cac thao tac tren GF(q), goi toan phap © la phep cong va toan phap la phep nhan va sir dung cac dau cong va nhan ciia so hoc. Noi dung chinh cu the cua cac phep toan nay se duoc xac dinh boi van canh. Xet tap s 6 nguyen 0 , 1,.., i,.., p -1 voi p la so nguyen to. Ap dung phep cong va phep nhan modp cho tap so nguyen ta se co mot truong Galois. Ta dung ky hieu GF(q) de chi mot truong Galois gom q phan tir. Mot phan tir khac 0 ciia GF(q) co bac nhan bang q - 1 goi la phan tu sa dang (primitive element) ciia GF(q). Noi cach khac, neu a la phan tir so dang ciia GF(q) thi aq_l = 1. Neu a la phan tir so dang ciia GF(q) thi (a, a2,..., aq'') lap thanh m ot nhom tuan hoan. Da tliuc tren GF(q). Bieu thirc: f(D ) = fnD" + f n_,D1’”1+--- + f0 (6.1-2)
154 Ly thuyet thong tin va ma hoa dugc goi la da thuc (polynomial) bac n tren GF(q) neu cac he so f„, f0 la cac phan tu cua GF(q). Mot da thuc tren GF(q) co he so fn = 1 duoc goi la da thuc dinh chuan (monic polynomial). Ky hieu D trong f(D) mang tinh uoc le. NghTa la, no khong dien ta mot bien hay mot phan tir chua biet ciia truong. Mot phan vi sau nay chung ta se thay the D bang mot phan tir khac, mot phan vi chiing ta quan tam den cac he so ciia da thirc hon la ban than da thirc. Hai da thirc goi la bang nhau neu chung co ciing chuoi he so, n gugc lai chung khong bang nhau. Vi du cac da thirc tren truong mod 2, f(D) = D 3 + D 2 + D va g(D) = D la hai da thirc khong bang nhau. Mat khac, neu chiing ta thay D bang cac phan tir 0 hoac 1 ciia truong ta se thay rang f(0) = 0, f(l) = 1 va g(0) = 0, g( l ) = 1. N h u vay, voi tu cach la cac ham so ciia bien trong truong mod 2 thi f(D) va g(D) bang nhau, mac dii voi tu cach la da thirc thi chung khong bang nhau. Tong hai da thuc tren GF(q) cho truoc la mot da thuc tren truong do va dugc xac djnh boi: f(D ) + g(D ) = i ( f , + g , ) D ' (6,1-3) 1=0 Bac ciia f(D) + g(D) la so n Ion nhat sao cho fn + gn * 0. Vi du: (D : + D + 1) + (D : +1) = m o d ,(l + 1)D: + D + m o d ,(l +1) = D (6.1-4) Tich ciia hai da thirc tren GF(q) cho truoc cung la mot da thirc tren truong do va dugc xac dinh boi: ( ' \ f(D )g (D ) = X X ^ g , . , D' (6.1-5) ' V J=° > Cho f(D) va g(D) * 0 la hai da thirc tren GF(q). Khi do ton tai duy nhat hai da thirc h(D) va r(D) tren GF(q) thoa man: f ( D) = g (D )h(D ) + r(D) ( 6 . 1- 6 ) Trong (6.1-6) bac ciia r(D) nho hon bac cua g(D). Vi du voi cac da thirc g(D) = D* + D + 1 va f(D) = D 3 + D + 1 tren truong m od;, ta co h(D) = D + 1 va r(D) = D.
Chuang 6: Cac phuang phap md hoa vd giai md 155 Neu f(D) * 0, g(D) * 0 va: f(D) = g(D)h(D) (6.1-7) thi ta noi rang f(D) kha qui (reducible), ngugc lai ta noi rang f(D) khong khd qui (irreducible). Bat ky da thuc nao tren GF(q) cung co the phan tich thanh cac da thuc khong the rut gon tren truong do. Mot phan tir a e GF(q) dugc goi la nghiem (root) ciia da thuc f(D) tren GF(q) neu f(a) = 0. De dang chung minh dugc rang, a la nghiem ciia f(D) khi va chi khi (D - a ) la mot thira so ciia f(D). Vi cac phan tir khac 0 ciia GF(q) lap thanh mot nhom Abel theo phep nhan nen chung co bac nhan (bac theo nhom nhan) chia het cho q - 1. Gia sir a la mot phan tir khac 0 cua GF(q), khi do aq_l = 1. Noi cach khac, a la nghiem cua da thuc f(D) = Dq_l - 1. Vi da thuc f(D) = Dq"' - 1 co q - 1 nghiem khac biet nen ta phai co: D q"' - * = f t (D —a,) (6.1-8) i=l Vi du truong cac so nguyen voi phep cong va nhan m odj ta co: D2 - 1 = ( D - l ) ( D - 2 ) (6.1-9) Truong con ciia mot truong la mot truong gom tap con ciia cac phan tir ciia truong nguyen thuy va tuan thii cac toan phap ciia truong nguyen thiiy. N£u F co mot truong con la E thi ta noi rang F la m d rong cua E. N 6 u E la truong con ciia F va a la phan tir cua F, mot da thirc dinh chuan f(I(D) tren truong E co bac nho nhat sao cho a la nghiem ciia no thi dugc goi la da thirc tdi thieu (minimal polynomial). Vcri mdi truong con E ciia truong Galois GF(q) va mot phan tu a khac 0 trong GF(q), a co duy nhat mot da thirc toi thieu fu(D) tren E va fa(D) la bdt kha qui. Ngoai ra, neu f(D) la da thirc tren E thi fa(D) chia het cho f(D) khi va chi khi a cung la nghiem ciia f(D). Goi E la truong con ciia truong Galois GF(q). Goi fi(D). f;(D)..... fi (D) la cac da thirc toi thieu nhau tren E irng voi cac phan tu khac nhau ciia GF(q). Khi do ta co:
156 Ly thuyet thong tin va ma hoa D q-' = n f.(D ) (6 M 0 > i=l E la trucmg con cua truang Galois GF(q) va co p (p la so nguyen to) phan tu, a la phan tu so din g trong GF(q). Goi k (D ) la da thuc toi thiSu cua a . Gia thi£t bac cua fa(D) b in g n. Khi do GF(q) co dung pn phan tu va cac phan tu nay co the dien ta boi: P = ] T i ka k ; i o = l (6.1-11) k=0 Trong (6.1-11) ik la cach dien ta GF(q) bai cac s6 nguyen. Vi du, de thay r5 cach dien ta truong GF(24) ta khao sat truang da thuc tren GF(2) theo modulo f(D) = D 4 + D + 1. Chung ta co the bien doi bang cach chia f(D) cho cac da thuc bac 1 va 2 tren GF(2) va rut ra ket luan f(D) la da thuc bat kha qui. Bang 6.1-1 duoi day chi ra hai cach dien ta cac phan tu cua GF(24), m o rong cua GF(2). Cach thu nhat thong qua luy thua cua phan tir sinh a . Cach thu hai thong qua da thirc g(t) = g3t3 + g2t2 + git + go. Phep cong va phep nhan thuc hien theo modulo f(t) = t4 + t +1. Can luu y o day rang, cac he so cua da thuc dugc tinh theo mod2. Bang 6.1-1: Dien ta cac phan tic cua truang GF(24) Diln ta Diin ta qua da thirc g(t) qua phin tCr sinh a 93 92 9i go Da thi>c tdi thiiu 0 0 0 0 0 1 0 0 0 1 D + 1 a 0 0 1 0 D4 + D +1 2 a 0 1 0 0 D4 + D +1 a3 1 0 0 0 D4 + D3 + D2 D +1 a4 0 0 1 1 D4 + D +1 5 a 0 1 1 0 D2 + D +1 6 a 1 1 0 0 D4 + D3 + D2 ♦ D ♦1 7 a 1 0 1 1 D4 + D3 +1 8 a 0 1 0 1 D4 + D -M 9 a 1 0 1 0 D4 + D3 + D2 ♦ D +1
Chiromg 6: Cac phucmg phap md hoa vd giai md 157 Diin ta Diin Ml qua da thirc g(t) qua ph£n ti> sinh a Oi 92 9i go Da thirc t6i thiiu 0 0 0 0 0 a 10 0 1 1 1 D2 + D +1 a 11 1 1 1 0 D4 + D3 + 1 a 12 1 1 1 1 D4 + D3 + D2 + D +1 a 13 1 1 0 1 D4 + D3 +1 14 a 1 0 0 1 D4 + D3 +1 Vi du, de tim g(t) tu a n g ung vai a 5 ta ap dung cong thuc: g (t) = m o d (t4+(+|) t 5 ( 6 . 1- 12 ) Phan d u cua t 5/(t 4 + t + 1) bang - 12 - 1. Tren GF(2) mod 2 (-1) = 1 nen mod 2( - 12 - 1) = m od 2(t 2 + t) = g(t). Dieu nay ham nghTa g 3 = 0, g 2 = 1, gi = 1 va go = 0 n h u ta thay trong bang 6.1-1. De chi ra rang a k la nghiem cua da thuc toi thieu tu a n g ung, vi du a 12 la nghiem cua da thuc D 4 + D 3 + D 2 + D +1, ta phai chi ra rang: m od 2( a 48 + a 36 + a 24 + a 12 + 1) - 0 (6.1-13) Vi a 15 = 1 nen (6.3-13) co the rut gon thanh: m od 2( a 12 + a 9 + a 6 + a 3 +1) = 0 (6.1-14) Thay the cac gia tri tuong ung cua a k vao (6.1-14) ta co: m od2(15 + 1 0 + 12 + 8 + 1) = m od2(46) = 0 (6.1-15) Cac truong G F(pm) trong do p la s 6 nguyen t 6 va m > 1, co mot vai tinh chat dac biet. N eu a va (3 la cac phan tu trong GF(pm) thi: ( a + P)P" = a p" ' + p pm (6.1-16) N 6 u: f (D ) = I f 1D i (6.1-17) i=0 la da thuc tren GF(p) va a la ph&n tu cua G F(pm) thi voi m > 1 ta co:
158 Ly thuyet thong tin vd md hoa m nm f ( a p ) = [f(a)] (6.1-18) Bi£u thuc (6.1-18) x u it phat tu thuc te (fj)p‘‘ = 1 va (f,)p = f, va: [ f ( a ) ] pm = ^ fja ' p” = f ( a pm) (6.1-19) 1=0 6.2. MA KIEM TRA CHAN LE Ma kiem tra chan le (Parity-Check Code) la mot dang dac biet cua phep anh xa tu chuoi nhj phan co do dai L (chuoi thong tin, thong diep) vao mot chuoi nhj phan khac co do dai N > L (chuoi m a tu). Truong hop don gian nhat cua ma kiem tra pa-ri-ty chung ta da gap trong ky thuat vi tinh. 6 do nguoi ta them vao cuoi chuoi nhj phan dien ta mot kv tu mot ma hieu nua sao cho tong cac ma hieu 1 (duoc goi la bac cua ma tu) cua chuoi la mot so chan. Trong phan ma hoa nguon roi rac ta da chi ra rang, mot ma nhu vay co kha nang phat hien loi xuat hien 6 mot m a hieu. Neu co hai ma hieu bj loi thi bac cua ma tu bj loi se tro thanh chan va loi xuat hien khong the duoc phat hien. Viec kiem tra bac chan le cua ma tu duoc thuc hien qua phep tinh modulo co so 2 . Ta co the m d rong cach lam tren bang cach su dung mot tap ma hieu kiem tra, trong do moi ma hieu kiem tra co nhiem vu kiem tra mot tap con cua chuoi thong tin. Vi du, goi U = (ui, u2,..., u L) la chuoi gom L ma hieu nhj phan mang thong tin va X la ma tu co do dai N > L duoc xay dung cho U theo luat sau: un 1< n < L l ( 6 . 2 - 1) m o d ; 2_ u,g, n L+l
C huang 6: Cac phuang phap md hoa vd giai md 159 Digits). N h u vay, vai viec chon gj, n khac nhau chung ta se co nhung ma kiem tra bac khac nhau. Bang 6.2-1 chi ra vi du mot ma kiem tra pa-ri-ty duoc thiet lap cho L = 3 va N = 6 . De dang nhan ra rang, trong vi du a bang 6.2-1, g,,n duoc cho boi: fl i=n [0 t l* n 11 < n < L; (6 2 ‘2) U u diem cua ma kiem tra pa-ri-ty la su don gian cua bo ma hoa. De the hien bo ma hoa kiem tra pa-ri-ty can mot thanh ghi de ghi chuoi thong tin U, mot thanh ghi de ghi ma tu X tuong ung va mot so bo cong modulo co so 2 ty le voi NL. N h u vay ma kiem tra pa-ri-ty khong doi hoi so o nho tang theo ham mu cua L nhu cac loai ma khoi phi cau true khac. Bang 6.2-1: Vi du ve md kiem tra pa-ri-ty X u Ma hieu thong tin Ma hieu ki§m tra x4 = mod2 x5 = mod2 x6 = mod2 W — II II U 1U 2U 3 x3 = u3 c C X X k K} -k (u2 + u3) (U1 + u3) (u1 + u2) 000 0 0 0 0 0 0 001 0 0 1 1 1 0 010 0 1 0 1 0 1 011 0 1 1 0 1 1 100 1 0 0 0 1 1 101 1 0 1 1 0 1 110 1 1 0 1 1 0 111 1 1 1 0 0 0 Chung ta co the dien ta qui luat ma hoa mot cach tong quat hon cho cac ma kiem tra pa-ri-ty bang cach su dung ma tran sinh G. Ma tran G la mot ma tran gom L hang va N cot, co dang: O £>1.1 § 1. 2 Sl.N §:.i § 2,2 § 2.N (6.2-3) £>L.l §L,2 §1..N
160 Ly thuyet thong tin va md hoa Dien ta U va X duoi dauig cac vec-to hang, chung ta co: X = m od 2 U G (6.2-4) Trong truong hop m3 kiem tra dugc xay dung 6 bang 6.2-1, ma tran G co dang: G = [I D ] (6.2-5) Trong (6.2-5) I la m a tran don vi cap (L x L) va D la m a tran co cap (L x N - L). Bieu thuc (6.2-4) cho phep ta tien hanh cac thao tac qua trinh ma hoa kha thuan tien. Gia su ta co hai chuoi thong tin U ’ va U ” . Ta dinh nghTa phep cong modulo co so 2 cua hai vec-to boi: U = m od 2(U ’ + U ” ) = ( u , , u 2,...,u L) Uj = m o d ,(u ',+ u " ) ; i = 1, 2,..., L (6.2-6) Khi do ta se thu dugc: X = mod2UG = m od 2(U ’ + U ” )G = m od 2U ’G + m od 2U ” G = X ’ + X ” (6.2-7) ,i * ■» i Bieu thuc (6.2-7) chi ra rang, tong cua hai m a kiem tra pa-ri-ty cung la mot m a kiem tra pa-ri-ty. Ta cung co the nhan ra rang, neu chuoi thong tin chua duy nhat mot m a hieu 1, ch in g han 6 vi tri th u j, thi m§ tu tuong ung chinh la hang thu j cua ma tran G. Ta dinh nghTa ma tran kiem tra pa-ri-ty H la ma tran gom N hang va (N - L) cot, co dang nhu sau: H= ( 6 .2 - 8 ) Trong do, I la m a tran don vi cap (N - L)*(N - L) va F la ma tran co cap L x (N - L). De lam noi bat vai tro cua H ta sir dung cach dien ta gia tri cua ma hieu theo ( 6 .2 - 1): L x n = m o d ; ^ x 1g in ; L < n < N (6.2-9) 1=1 Them xn vao ca hai ve ciia (6.2-9) ta thu dugc:
Chuang 6: Cac phuang phap md hoa va giai md 161 m o d 2( x n + x n) = mo d 2 2 > i gi n+ x n = 0 (6.2- 10) L
162 Ly thuyet thong tin vu md hoa Ta da bi£t trong cac ch uang truac, so cac ma hieu khac nhau giua hai chuoi nhj phan dugc goi la khoang cach Hamming. Ta thay rang, Pr(Y/Xm) la mot ham giam theo khoang cach Hamming giua Y va Xm. C a ch£ giai ma hgp ly nhat chinh la chon ma tu co khoang cach Hamming voi Y nho nhat. Ta cung nhan thay rang, khoang cach giua Y va X m b in g so cac s6 1 cua chuoi Z m (con goi la trong so). N h u vay, ca che giai ma hgp ly nhat chinh la chon ra ma tu X m sao cho chuoi Zm co trong so nho nhat. Ta co th£ tom tat qua trinh giai ma cho kenh nhj phan doi ximg voi e = — nhu sau: 2 • Nhan chuoi dau ra Y • Tinh S = m od 2YH (H dugc xac dinh theo (6.2-8)) • Giai phuang trinh S = mod; ZH de tim Z • Tinh X = mod 2 (Y + Z) Trong cac buac tinh toan tren day, quan trong va kho nhat la giai phuang trinh S = mod^ZH de tim Z. Mot trong nhung cach hoan thien van de nay la dung bang giai ma. Ta co the liet ke tat ca 2 N L gia tri co the co cua S va tim ra vai trong so nho nhat tu a n g ung vai tung Sr Tuy nhien ta co the lam cach ngugc lai dan gian han. Ta bat dau chon Z) co trong so bang 0, tinh Sj = m od 2ZjH. Tiep den ta chon ZJ+i co trong so bang 1 va tinh Sr i = mod 2Zr iH. Cir tiep tuc nhu vay cho den khi tim du 2 N-L gia t ■- . • c tri cua S. Vi du vai N - L = 10 co tat ca 1024 gia tri cua S. Ta co cam giac cach lam tren khong kha thi. Tuy nhien vai ky thuat tinh toan hien nay thi day khong phai la van de lan. Bang 6.2-2 va 6.2-3 cho thay bang ma hoa va giai ma kiem tra pa-ri-ty vai L = 3 va N = 6 . Bung 6.2-2: Bang md hoa U X u X 000 I 000000 100 100011 001 I 001110 101 101101 010 010101 110 110110 011 i 011011 111 111000
Chuang 6: Cac phuang phap md hoa vd giai md 163 Bang 6.2-3: Bang giai md Syn-drom Chuoi sai lech Ma tran kiem tra S Z 000 000000 'on' 011 100000 1 01 IUI 101 010000 110 001000 110 100 000100 1 00 010 000010 010 001 000001 001 111 100100 Gia su ta nhan dugc chuoi dau ra cua kenh Y = 010011. Khi do ta co S = mod 2YH = 110. Tir bang 6.2-3 ta tim dugc Z = 001000. T u Y va Z ta tim dugc X = m od; (Y + Z) = 011011. Tim trong bang ma hoa 6.2-2 ta thay chuoi thong tin tuong ung U = 011. Ta cung co the thay qua bang giai ma 6.2-3, chuoi sai lech Z chua cac loi co the sua dugc ma khong can biet truac ma tu nao da giri di. Khi mot chuoi sai lech xuat hien, bo giai ma se tinh dugc syn-drom S tuang ung. Sau do bo giai ma se tim xem trong bang giai m a co chuoi sai lech do khong. Neu trong bang giai ma khong co chuoi sai lech tuan g ung ma mot chuoi sai lech nao do trong bang giai ma van dugc chon ra thi loi giai ma se xuat hien. Noi cach khac, kha nang sira loi ciia ma phu thuoc vao viec chon ma tran sinh G va ma tran kiem tra H. Vi du tren cho thay, vai H da chon, tat ca cac loi don va mot cap gom hai loi dan (co S = 111) se dugc bo giai ma chinh sira. Nhirng cap loi don khong co S = 111 se khong the sira dugc. N hu vay vai H khac nhau, kha nang sira loi ciia ma co the se khac nhau a timg loi cu the. N h u chiing ta da thay, syn-drom ung vai mot chuoi sai so Z dugc xac dinh bai S = ZH. Neu Z chira mot loi duy nhat, chang han loi a vi tri thir j, thi ZH triing vai hang thir j cua H. Neu moi hang ciia H deu khac 0 va khac biet nhau, moi chuoi sai so co bac bang 0 hoac bang 1 se co syn drom khac nhau va nhu vay ma do co kha nang sira mot loi. Doi vai ma gom N - L m a hieu kiem tra se co tat ca 2N‘L- 1 chuoi khac 0 co the chon lam cac hang ciia ma tran H. Han nua, neu N < 2N' L - 1 thi cac hang cua H co the chon khac 0 va khac biet nhau. Ta goi cac ma trong do cac hang
164 Ly thuyet thong tin vd ma hoa cua H khac biet nhau va gom cac chuoi khac 0 vai do dai N - L la md Hamming. Ta de dang thay rang, doi vai m a H am m ing N va L thoa man dieu kien: N = 2 n' l - 1 (6.2-17) Nen n ha lai rang, trong chuang 3 da chi ra, mot bang ma co khoang cach Hamming cuc tieu bang D min co the phat hien dugc int(Dmm/2) loi va co kha nang sira dugc int((Dmm- l)/2) loi. Bang 6.2-4 cho thay cac gia tri N va L thoa man dieu kien (6.2-17) va ma tran kiem tra H cho truang hgp N = 7, L = 4. Bang 6.2-4: Cac gia tri N vd L cua md Hamming N L H 3 1 011 7 4 101 15 11 110 31 26 111 63 57 100 127 120 010 255 247 001 Mot trong nhirng ma kiem tra pa-ri-ty dac biet co y nghTa la md ket hap (coset code). M a ket hgp (N, L) la ma bao gom 2 1 ma tu vai do dai khoi N > L, trong do cac thong diep la nhung chuoi nhi phan do dai L va anh xa tir chuoi thong tin U vao ma tu X dugc the hien bai: X = UG © V (6.2-18) Trong (6.2-18) G la ma tran sinh co dinh cap (L x N) vcri cac phan tir bang 0 va 1, V la mot chuoi nhi phan co dinh gom N phan tu. Ta thay rang, ma ket hgp la ma kiem tra pa-ri-ty n hu da trinh bay a phan tren cong them chuoi V. NghTa la X = UG © V = X ’ © V. Dinh ly sau day cho biet giai han tren ciia xac suat loi giai ma cho kenh BSC sir dung ma ket hgp. D inh lv 6.2-1 Clio md ket hap (X . L) trong do ma tran sinh G vd vec-to I' nhan cac phan tu 0 hoac 1 vai xdc sudt nhu nhau. Gia thiet ca che giai md hap
Chuang 6: Cac phuang phap md hoa vd giai md 165 ly nhat duac dp dung. Ky hieu Er(R) la so mil md hoa ngdu nhien (dinh nghTa tai muc 5.4). Toe do khoi R duac chon bang (L In 2)/N. Khi do xdc sudt loi trung binh khi giai md mot thong diep truyen qua kenh BSC thoa man dieu kien: K.m - exp { ~ N E r(R)} (6.2-19) Chung minh Goi U m la chuoi thong tin tuy y va X m la ma tu tuong ung. Xac suat de U m duoc anh xa vao X m bang: Q N(Xm) = 2' n (6.2-20) That vay, ta thay co tat ca 2N(L+I) cach chon G va V va moi cach chon do xac suat bang 2 'N(L+I). Vcri moi cach chon G ta co mot cach chon V tao ra gia tri co dinh cho X m. Vi co 2NL cach chon G nen: Q N(X m) = 2 n l x 2 'N(L+I) = 2'n (6.2-21) Gia sir co chuoi thong tin U 'm khac voi U m va ma tu tuong ung la X ’m. Theo djnh nghTa ta co: X m © X ’m = (U m © U ’m)G (6.2-22) Gia thiet rang U m va U ’m khac nhau o vj tri j. Khi do voi mot tap cac gi, g 2,..., gj-i, gj+i,..., gL da cho nao do, se co mot cach chon gj tao cho Xm © X ’m mot gia tri co dinh. Tiep theo ta co the chon V de lam cho gia tri X m co dinh. Co tat ca 2N(L' I) cach chon G va V de nhan dugc mot cap (Xm, X ’m) voi gia trj mong muon va voi xac suat bang 2 ‘2N. Cung voi (6.2-20) ta suy ra tinh doc lap cua X m va X ’m- Vi cac ma tu dugc chon mot cach doc lap voi nhau, van dung cac dinh ly 5.3-2 va 5.3-5 ta suy ra ket qua (6.2-19). Truoc khi ket thuc muc nay, chung ta tim hieu hai dang ma kiem tra pa-ri-ty rat dac biet. Do la md hinh chu nhat (Rectangular Code) va md tam giac (Triangular Code). Chung ta se trinh bay cac ma nay duoi dang vi du cu the. M d hinh c h u nhat. Gia su ta co chuoi ma hieu thong tin U gom 16 ma hieu nhj phan. Ta xep cac ma hieu thanh hinh vuong, moi canh co do
166 Ly thuyet thong tin vd ma hoa dai 4 ma hieu. Ta dung i de chi cac ma hieu thong tin va x de chi cac m3 hieu kiem tra. Cac ma hieu kiem tra duoc viet vao cot thu 5 va hang thu 5, trir ma hieu o goc (xem hinh 6.2-1). x x x x Hinh 6.2-1. Ma hinh chit nhat Cac ma hieu kiem tra cr cot thu 5 duoc tao ra bang phep cong cac ma hieu thong tin cung hang theo modulo co so 2. Cac m a hieu kiem tra 6 hang thu 5 duoc tao ra nho phep cong cac ma hieu thong tin cung cot theo modulo co so 2. Ma tu ket qua thu duoc bang cach chuyen cac ma hieu lan lugt tung hang thanh chuoi. Gia su ta co chuoi ma hieu thong tin 1010110101011011. Ta lap duoc hinh vuong va tinh duoc cac ma hieu 1 0 1 0 0 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 0 1 Hinh 6.2-2: Vi du ve md hinh chu nhat T u hinh 6.2-2 ta thu duoc ma tu sau: X = 101001101101010101111001 Ma hinh chu nhat co kha nang sua sai 6 1 loi. That vay, gia sir loi xuat hien a ma hieu (i, j). Khi do ta se thay ket qua khong phu hop voi ma hieu kiem tra o hang thir i va cot thu j. N h o hai ma hieu kiem tra nay ta se djnh vi ra ma hieu loi o vj tri (i, j) va sira no. N eu mot ma hieu kiem tra o hang sai thi no se dugc cac ma hieu kiem tra o cot djnh vj va ngugc lai. M d tam giac. Chuoi ma hieu thong tin U se dugc xep thanh hinh tam giac nhu trong hinh 6.2-3. Cac ma hieu kiem tra nam tren canh
Chuang 6: Cac phuang phap ma hoa vd giai md 167 huyen dugc tao ra bang phep cong cac ma hieu thong tin tren hang hoac cot theo m odulo c a so 2 . i i i i x i i i x i i x i x x Hinh 6.2-3: M d tam giac Vi du vai chuoi ma hieu thong tin U = 1011010011 ta co ma tam giac nhu trong hinh 6.2-4. 1 0 1 1 1 0 1 0 1 0 1 1 1 0 0 x = 101110101011100 Hinh 6.2-4: Vi du ve md tam giac M a hieu kiem tra thu 1 bang tong hang thir 1 theo m odulo c a so 2. Ma hieu kiem tra th u 2 bang tong hang th u 2 theo m odulo c a so 2. Ma hieu kiem tra thu 3 bang tong cot th u 3 theo m odulo c a so 2. M a hieu kiem tra thu 4 bang tong cot thu 2 theo m odulo c a so 2. M a hieu kiem tra thu 5 bang tong cot thu 1 theo m odulo c a so 2. Ma tam giac cung co kha nang sira 1 loi. Neu ta thay ma hieu kiem tra thir 1 khong thoa m an con tat ca cac ma hieu kiem tra khac deu thoa man thi ta suy ra ngay loi da xuat hien a ma hieu thir 4 cua hang thir 1. Neu ta thay ma hieu kiem tra thir 4 khong thoa man con tat ca cac ma hieu kiem tra khac deu thoa man thi ta suy ra ngay loi da xuat hien a ma hieu thir 2 ciia hang thir 3... 6.3. MA T l AN HOAN Ma tuan hoan (cyclic code) la mot dang md tuyen tinh (linear code) hay con goi la md nhom (group code). Ky hieu U = (U], u ;.....U |) la mot
168 Ly thuyet thong tin vd md hoa chuoi thong tin bat ky (khong nhat thiet la chuoi nhi phan), trong do Uj la phan tir ciia GF(q). De don gian cach viet, trong ch u an g nay toan tir ® va ® cua GF(q) se dugc thay bang cac dau cong va nhan ciia so hoc thong thuang. M a tuyen tinh (N, L) co cac m a tu X = ( x i , X2,..., x N) tu an g irng vai U la m ot chuoi gom N > L ma hieu d u ac sinh ra theo luat: x n = Z Ujgj.n ; 1 ^ n < N (6.3-1) Trong (6.3-1) gj, n duac chon tiiy y tir cac phan tir cua GF(q), cac toan tir cong va nhan la cac toan tir ciia GF(q). Ta co the dien ta gj. n boi ma tran sinh G nhu trong muc 6.2 va tu o n g tu ta co m a hieu X duoc sinh ra boi: X = UG (6.3-2) Cho a la phan tir bat ky trong GF(q). Tir (6.3-2) ta suy ra rang, neu X la m a tu cua U thi a X la m a tu ciia a U . H an nua, neu X| la m a tu ciia U] va X 2 la m a tu cua U 2 thi m a tu cua (Ui + U 2) se dugc xac dinh bai (Xi + X 2). Noi cach khac, tap hap cac m a tu la khong gian con tuyen tinh ciia khong gian cac chuoi co do dai N tren GF(q). M a tuyen tinh he thong (system atic linear code) la m a tuyen tinh trong do L thanh phan dau tien ciia m a tu thoa m an dieu kien: Xj = Uj ; 1 < j < L (6.3-3) D ieu kien (6.3-3) duoc thoa m an bang cach dat gj, n = 1 khi j = n va gj, n = 0 khi j * n vai n < L. M a tran sinh G ciia m a tuyen tinh he thong la cap L x N, ma tran kiem tra H ciia ma tuyen tinh he thong la cap N x (L x N). Cac bieu thirc (6.3-4) va (6.3-5) cho thay dang ciia cac m a tran G va H. 1 0 • •• 0 Sl.L +l 81, N 0 1 •• 0 82. N G— (6.3-4) •• 0 0 0 • 1 §L.L-I '• S l .n
Chuang 6: Cac phuang phap ma hoa vd giai md 169 Sl.L+l Sl.L+2 81. N S 2 . L +1 8 2 .L + 2 8 2 .N 8 l .l + i 8 l_,L +2 8 l ,n -1 0 •• 0 0 0 •• _1 Chung ta cung co the phat bieu cach khac ve m a tuan hoan. M a tuan hoan tren G F(q) la m a tuyen tinh co tinh chat, neu dich chuyen tuan hoan m ot m a tu se thu duoc m a tu khac. Dieu nay co nghTa la, neu (xi, X 2 , . .. , xn ) la m ot m a tu thi (X 2, X 3 ,..., xn , x i) cung la m ot m a tu. N hu vay, se rat thuan tien neu chung ta ky hieu cac phan tu cua X theo th u tu giam dan, nghTa la X = ( x n - i , x n - 2 ,— , * o) . Tuong tu, chung ta cung co the dien ta X duoi dang da thuc tren GF(q): x(D ) = x n.)D n'' + xN-2D n'2 +... + x ,D + x 0 (6.3-6) N eu cac he so cua da thuc x(D) tao thanh m ot m a tu cua m a tuan hoan thi Dx(D ) theo m odulo D N_I cung la m ot ma tu. That vay, tu (6.3-6) ta co: D x(D ) = xn-iD n + xn ^ ' 1 +... + x ,D 2 + x0D = Xn-i (D n - 1) + xn-2D n 1 +... + X|D 2 + xoD + xn-i (6.3-7) Lay m odulo D N'' cua (6.3-7) ta co: m odDN 1[D X (D )]= x N-2D n‘1 +... + x ,D 2 + x0D + x N., (6.3-8) Ky hieu g(D ) la da thuc dinh chuan co bac thap nhat tren GF(q) ma he so cua no dien ta m ot m a tu cua ma tuan hoan, bac cua g(D) bang m. Nhu da biet, neu g(D) la mot ma tu va ao la mot phan tu cua GF(q) thi aog(D) cung la m ot m a tu. Do tinh tuan hoan nen aiD g(D ) cung la m ot m a tu voi moi ai la phan tir cua GF(q). M ot cach tong quat, voi moi i < N - m - 1, a,D'g(D) la m a tu. C ong tat ca cac m a tu nay lai ta se nhan thay rang, voi bdt ky da thirc a(D) tren GF(q) co bac nho hon N - m - 1 thi a(D )g(D ) la m a tu. Ta se chi ra rang, tat ca ma tu ciia m a tuan hoan deu co dang bieu dien nay. Gia sir x(D) co bac bang hoac nho hon N - 1 co the dien ta boi: