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

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.
Nội dung trích xuất từ tài liệu:
Cơ sở lý thuyết thông tin và mã hóa: Phần 2 Chircmg 6 CAC PHU0NG PHAP MA HOA VA GIAI MA6.1. MO DAU6.1.1. Khai q uat Trong chuang truac chung ta da de cap den ma khoi va dung no denghien 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 thongdiep vao tap cac ma tu va giai ma la phep anh xa chuoi ma tu thu duocvao tap cac thong diep. N hu vay bat ky phep anh xa toan hoc nao cung cothe dung de ma hoa. Tuy nhien de co the giai ma mot cach duy nhat, anhxa do phai la anh xa mot-mot. Ngoai ra anh xa dung de ma hoa va giaima phai phu hop voi dac tinh vat ly cua cac kenh truyen thong trong thucte 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 diepqua mot kenh co nhieu n hu chung ta da tim hieu trong ch u an g 5. Ma hoacon la giai phap de nen d u lieu (data compression), mot trong nhung vande dang duoc cong nghe thong tin rat quan tam. Muc dich cua nen dulieu la lam giam do du thira, dong thoi cung lam tang mat do thong tinhuu dung cua nguon tin can luu tru hoac chuyen tai di xa. Viec nen dulieu co irng dung rat quan trong trong ltnh vuc luu tru tep tin va o cac hethong phan tan (nhu truyen hinh Internet). Cac kv thuat nen d u lieu duocxay dung tren nen tang lv thuyet thong tin va th u a n g d u ac nhac den nhula mot truong hop cua ma hoa. trong do ma hoa dugc hieu mot cachchung nhat. Nhiem vu quan trong nhat cua nen du lieu bao gom viec biendoi mot xau thong tin (string) tir mot cach dien ta nao do (chang hanASCII) sang mot xau thong tin khac (chang han chuoi nhi phan) sao chonoi 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 151the. N hieu cong cu ngay nay cho phep dat do nen trung binh tren 50%, cabi?t toi 90%. Ma hoa (mat ma hoa) cung la phu an g tien de bao mat thong tin rathieu 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 bientrong cac hoat dong kinh te, ngan hang, thuang mai dien tir,... Chung tase de cap den mat m a trong chu an g 7. Trong ch uang nay chiing ta taptrung nghien ciru mot so phu an g phap ma hoa va giai ma da duoc phattrien 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 ketqua ciia ly thuyet truong (Field Theory). Vi vay de tien loi cho nhungtrinh bay tiep theo, chung ta nhac lai ngan gon a day mot so khai niem coso 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 toanphap © 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 huuhan cac phan tir thi goi la nhom huu han (finite group). Vi du, tat ca cacchuoi nhi phan co do dai N va phep cong modj tao thanh mot nhom huuhan. PhSn tir don vi la chuoi 0. Phan tir nghich dao ciia chuoi la chinhchuoi 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 voij > 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 11 la phan tu d an vi. Bac (order) ciiaphan tir a e G la so nguyen duong nho nhat k sao cho ak = e. De dangthay rang, voi X la so nguyen duong bat ky thi a>vk = e. N hom co tinh chatvira neu duoc goi la nhom tuan hoan (cyclic group). Can luu y rang, khainiem luy thira o day khong hoan toan giong khai niem luy thira trong sohoc thong thuong boi vi toan phap © khong dong nghTa vcri phep nhanso 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 153nghTa la h = 1. Phin tu nghjch dao cua a theo toan tir © duoc ky hieu boia 1, phan tir nghich dao cua a theo toan tir duoc ky hieu boi a+1. Ta cothe 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 haitoan phap © ...