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

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

Thêm vào BST

Báo xấu

327
lượt xem 76
download

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

Phần 1 Tài liệu Lý thuyết thông tin và mã hóa cũng cáo cho người đọc các nội dung: Mở đầu về lý thuyết thông tin và mã hóa, lượng tin và en-tro-py, nguồn rời rạc và kênh rời rạc, mã hóa nguồn rời rạc, mã hóa kênh rời rạ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 1

T H0 NG VA HOA GUYEN i LIEU
VOHy VI/M VA N il ONQH1 I I A O H J . A T
VU N G O C PHAN l_Y T H U Y ^ T THONG TIN VA MA HOA NHA XUAT BAN B l/U OIEN Ha Noi, th a n g 10 - 2 0 0 6
L d l N O ID A U Ngay nay, cac mang may tinh, mang dien thoai so him tuyen va vo tuyen, mang truyen hinh cap... dang co xu the hoi tu thdnh mang chung, da dich vu, co kha nang chuyen tdi thong tin tich horp vai toe do len den hang tram Mbit/s. Nhin tie gdc do khoa hoc, cac he thong thong tin ngay nay la cac he thong co do phirc tap cau true rat lan va chiu tdc dong cua nhieu loqi nhieu khde nhau. De cac he thong do co the lam viec on dinh va tin cay, dap ung duac yeu cau cua nguai su dung trong viec lieu giu, chuyen tdi vd chia se thong tin, khong the khong dua vao kien thi'cc ve ly thuyet thong tin vd ma hoa. Co the noi, khong co ly thuyet thong tin vd md hoa thi khong the giai quyet duac van de truyen tin chinh xdc tren cac duang truyen ddi hang ngdn km. Nham dap ung nhu cau tim hieu ve ly thuyet thong tin vd md hoa, Nhd xudt ban Buu dien xudt ban cuon sach Ly thuyet thong tin vd m d hoa ” cua tdc gid Vu Ngoc Phan giai thieu den ban doc. Ly thuyet thong tin vd md hoa Id cong cu huu hieu de giai quyet nhung van de cong nghe thong tin dang dat ret nhu ndng cao tdc do truyen dan theo thai gian thuc, nen dir lieu , boo mat dir lieu,... Bo cuc cuon sdeh gom 8 chuang. Tu chuang 1 den chuang 7 trinh bay cu the cac cac van de ve ly thuyet thong tin rai rac nhu: luang tin vd En-tro-py, nguon rai rac vd kenh rai rac, md hoa nguon vd md hoa kenh , cac phuang phdp md hoa vd giai md, mat md. Dae biet chuang 8 giai thieu ve ly thuyet thong tin cac he lien tuc duac xem nhu la sir m a rong cua ly thuyet thong tin cac he rai rac. Trong khi trinh bay nhirng noi dung ly thuyet, cuon such dua ra nhirng vi du kha true quan, giiip nguai doc de theo ddi. Ngodi ra cudi cuon such co phdn Phil luc giai thieu mot so chuang trinh mo phong cue thudt loan md hoa viet tren Mat Lab giup cho ban doc hieu mot each true quan ve cdc md dd neliien ciru.
Cuon sach la tai lieu tham khao rat huu ich cho cac chuyen gui. ky thuat vien, cung nhu can bo giang day va dac biet hoc vien nganh vien thong muon tim hieu nhung kiin thuc co ban va nghien ciru sdu vcrly thuyet thong tin va md hoa. Nha xudt ban xin tran trong giai thieu den ban doc va rat mong nhan d u a c y kien go p y cua q u i vi. M oi y kien gop y xin g u i ve Nha xu d t ban Buu dien - 18 Nguyen Du, Ha Noi. Tran trong cam cm./. Ha Noi, thang 10 nam 2006 NHA XUAT BAN B l/U DIEN
Chuang 1 MG DAU 1.1. KHAI QUAT Sau chien tranh the gicri thu hai, co ba ly thuyet ra doi va da cung anh hucmg rat manh me den su phat trien khoa hoc va cong nghe. Do la ly thuyet he thong (System Theory), ly thuyet dieu khien (Control Theory) va ly thuyet thong tin (Information Theory). Trong cuon sach “ Five More Golden Rules” xuat ban nam 2000 tai My. khong phai khong co ly khi John L. Casti xep ba ly thuyet tren cung vcri ly thuyet day (Knot Theory) va giai tich ham (Functional Analysis) la nam trong so nhung ly thuyet lan cua the ky XX. Luc dau ly thuyet thong tin duac phat trien chu yeu de phuc vu cho ky thuat truyen tin. Nhung ngay sau do nguai ta nhan ra rang, nhung ung dung cua ly thuyet thong tin khong chi dung lai a ky thuat truyen tin ma a ca cac linh vuc khac nhu sinh y. kinh te, ngon ngu. am nhac, nghe thuat. hoi hoa... Ly thuyet thong tin co vai tro het sue quan trong trong viec nghien cuu cac he thong tu to chuc, tu dieu chinh va tu on dinh. Ly thuyet thong tin. cung vai ly thuyet he thong va ly thuyet dieu khien. da dat nen mong cho qua trinh chuyen doi tir cach tiep can dua tren quan he hinh thuc-noi dung (Form-Content-Relation) sang cach tiep can dua tren quan he cau truc-chuc ndng (Structure-Function- Relation). Cach tiep can sau da gop phan tao ra nhung thanh tuu vo cung to lan cua nhan loai suot nua the ky qua trong viec phan tich va thiet ke he thong, dac biet la cac he thong lan (Large-scale Systems). Vao nam 1948 khi Shannon cong bo ly thuyet thong tin cua minh qua cuon sach noi tieng "A Mathematical Theory o f Communication", d u a n g cap lan nhat the giai luc bay gia mai chi cho phep thuc hien dong thai 1800 cuoc thoai. D uai tac dong cua ly thuyet thong tin. 20 nam sau so cuoc thoai dong thai tren d uang truyen da la 230.000. Nam 2001 d u an g cap quang
8 Ly thuyet thong tin va md hoa Ngay nay nguai ta da thira nhan, ben canh qua trinh van dong vat chat la qua trinh van dong thong tin khong kern phan quan trong. N h u da biet, cac nhiem sac the va chat long trang trung tao thanh bo n h a sinh hoc. Ly thuyet thong tin la mot cong cu huu hieu de hieu ban chat cua nhung bo n h a sinh hoc nay. Duai goc do cua ly thuyet thong tin ta thay hoat dong cua te bao khong khac gi hoat dong cua mot nha may, trong do nhan te bao la ban giam doc dieu hanh toan bo qua trinh san xuat. cac nhiem sac the la ho so ve qui trinh cong nghe va ke hoach san xuat. te bao chat la nguyen vat lieu, cac en-zim la doi ngu ky su va cong nhan. Neu vi mot ly do nao do, cac thong tin ehua trong nhiem sac the bi sai lech thi hoat dong cua nha m ay te bao se khong dung ke hoach va qui trinh cong nghe, san pham tao ra khong dam bao tieu chuan ve chat lugng va so lugng, benh tat xuat hien. N h u da biet, nhiem sac the la mot chuoi rat dai cac phan tu chua thong tin. Trong qua trinh phan chia te bao, cac thong tin phai duac bao toan va chia deu cho ca hai nira (hai te bao mai). Cac thong tin ton tai trong nhiem sac the d uai dang m a d u ac tao nen tu bon phan tu c a sa (ly thuyet thong tin va m a hoa goi la m a hieu). Do la Adenin (ky hieu la A), Thymin (ky hieu la T), Guanin (ky hieu la G) va Cytosin (ky hieu la C). Theo luat so m u cua sir lira chon (Exponential Law o f Choice), neu mot nhiem sac the gom mot chuoi L phan tu nu-clein thi se co 4 l cau true khac nhau. Vai L = 100 ta co 4 100 « 1,6 x 10 60 cau true nhiem sac the khac nhau. Tren thuc te, mot nhiem sac the co the bao gom hang ngan phan tu nu-clein. Dieu nay giai thich day dii tinh da dang phong phu cua the giai sinh vat. Trong ITnh \ uc than kinh hoc. nguai ta thay rang mot te bao thAn kinh co the d uac mo ta hoan toan bai mot o-to-mat huu han va he than kinh co the xem nhu mot mang cac o-to-mat huu han. Mot na-ron bao gom phan than va cac sy-nap. Cac sy-nap bat dau tir than cua mot na-ron nay va noi tai mot na-ron khac. C u nhu vay. nhi^u na-ron k^t n 6 i vai nhau thanh mot mang na-ron. Moi aa-ron chi co the co hai trana thai. kich hoat (active) hoac khong kich hoat (passive), tucmg d u a n e he nhi phan trong cac m ay tinh va cac thiet bj dien tu s 6 thong dune. Q ua trinh liru trCr thong tin trong bo nao d uac hinh thanh n h a hoat done cua
Chuang 1: M d dau 9 cac sy-nap. Den nay nguai ta biet rang, moi na-ron chira nhieu han 1 bit. Theo Schaefer thi moi na-ron co dung lugng khoang 102 bit. N hu vay mot bo nao trung binh vai khoang 10 10 na-ron co the luu giu 1000 Gbit thong tin. Ly thuyet thong tin cung da tra lai cau hoi, mot he thong tu thich nghi hay mot he thong tu hoc co the co bac bang bao nhieu trong moi truang cua no. D uai goc nhin cudUy thuyet thong tin, nguai ta co the giai thich van de nay mot each kha thuyet phuc. Truac het chung ta tarn sir dung khai niem do du thira va luang tin se duac lam sang to a cac phan sau. Ta dat: I r = 1— ( 1 . 1- 1) I Trong bieu thuc (1.1-1), r la do du thira, I la lugng tin thuc te cua nguon tin va Imax la lugng tin cuc dai co the co. Doi vai cac he thong tu thich nghi hoac cac he thong tu hoc, ta luon co: f d\^ ai. -I dr dt at — > 0 hay - - >o ( 1 - 1- 2 ) dt iL Tir (1.1-2) suy ra: dl, > i m a x *- v (1.1-3) r*t at Bieu thirc (1.1-3) noi len mot cach tong quat rang, gia tri ciia trang thai thong tin va su bien thien ciia no lien quan chat che vai nhau. Tir day ta co the rut ra ket luan rang, neu lugng tin cuc dai ciia mot he thong tu thich nghi hay he thong tu hoc khong thay doi thi lugng tin thuc te se giant. NghTa la: dl 1... = const
10 Ly thuyit thong tin va ma hoa I = const —> —— > 0 (M -5) dt Cac bieu thuc rat don gian vira trinh bay tren cho phep giai quyet mot van de da ton tai rat lau trong ljch sir nhan loai nhung chua d u a c tra lai mot cach thoa dang, do la vi sao cac cau true sinh hoc co kha nang thich ung vai moi tru ang va tu phat trien. Cac cau true sinh hoc khac cac cau true vo c a a cho no co kha nang chong lai su tang en-tro-py. Nhieu nghien ciru ly thuyet thong tin tren tinh tinh va nguai da di den ket luan, kha nang nhan biet sir vat la ket qua cua mot qua trinh hoc rat da dang. Cac thi nghiem da cho thay rang, mot nguai mu bam sinh co dau oc tucmg doi thong minh, sau khi tru ang thanh d u a c phau thuat mat va nhin duac, nhung ho phai can nhieu thang de co the nhan ra cac do vat het sue dan gian, trong khi nguai binh thuang lam d u a c viec nay ngay tir cai nhin dau tien. Doi vai tinh tinh va tre nho, nhung nghien ciru da cho thay rang, khi quay mot tam giac di mot goc 90 do thi tre nho va tinh tinh cung phai nghieng dau di 90 do m ai nhan ra duac. Tom lai, khong co qua trinh hoc thi khong co su giam en-tro-py thong tin. Trong dai song hang ngay, con nguai da tiep xuc vai rat nhieu hien tugng m a ho khong d u doan truac d uac, hoac chi doan truac d u ac mot cach m a ho, khong cu the. Mot can loc xoay ap den bat nga. mot tran m u a lut chua tirng thay trong lich sir hang tram nam, mot con tau bong nhien mat tich ngoai bien khai. Cac nha ky thuat th u a n g gap nhirng hien tugng kho chiu m a ho goi la tap am (noise) hoac sir thay doi bat thuang (fluctuation). Tat ca nhung hien tugng tren it nhieu lien quan den khai niem en-tro-py ta vira nhac den va se dugc lam ro dan trong nhirng phan sau cua cuon sach. Xet a mot goc do nao do, muc dich cuoi cung cua ly thuyet thong tin chinh la giup con ngu ai trong viec lam giam en-tro-py thong tin. Khai niem en-tro-py dung trong ly thuyet thong tin ma chunt; ta vira goi la en-tro-py thong tin, co nguon goc tir khai niem en-tro-p\ troniz nhiet dong hoc. Dinh luat thir 2 cua nhiet dong hoc chi ra rang, nhiet chi co the truyen tir nai co nhiet do cao han den nai co nhiet do thap hon \ a khong the ngugc lai. Trong tu nhien. nguai ta nhan thay co hai loai qua
Chuang 1: Ma dau 11 trinh: qua trinh dao nguac duac (Reversible Process) va qua trinh khong dao nguac dupe (Non-Reversible Process). Qua trinh truyen nhiet la mot qua trinh khong dao nguac duac. Chung ta se phac hoa rat so luge khai niem en-tro-py cua nhiet dong hoc. Goi S la trang thai nhiet cua mot he thong va Q la nhiet lugng, ta co: Lay tich phan tir trang thai Si den trang thai S 2, ta co: f ^ Q = s 2 - S |= A S (1.1-7) s T AS dugc goi la en-tro-py. Nam 1829, Cac-no, mot nha khoa hoc nguai Phap, da chirng minh rang, trong mot he thong kin, AS > 0. Dinh luat nay ve sau dugc m a rong thanh: trong mot he thong kin, en-tro-py khong tu giam theo nghTa chung nhat. N h u vay nghTa la, mot he thong khong tiep xuc vai mot he nao khac (khong co quan he trao doi vai moi truang cua no), luon luon co xu hucrng tra ve trang thai xac suat dong deu, trang thai co en-tro-py cuc dai. Trang thai xac suat dong deu la trang thai hoan toan hon loan. Theo dinh luat nay, cac he thong kin cuoi cung se rai vao trang thai hon loan va huy diet. Trong ky thuat do la su hao mon, trong sinh hoc do la su gia coi, trong hoa hoc do la sir phan huy, trong xa hoi do la sir phan hoa, trong lich sir do la sir suy tan. Dieu nay cung dung vai cac he thong thong tin ma a do sir tang en-tro-py thong tin se dan tai sir bat dinh hoan toan. 1.2. NHUNG DINH HITONG CHINH CUA LY THUYET THONG TIN VA MA HOA Ly thuyet thong tin de cap den tat ca cac hinh thai van dong cua thong tin nhu: qua trinh hinh thanh thong tin ciia mot nguon tin. qua trinh thu nhan thong tin, qua trinh bien doi thong tin, qua trinh truyen dan thong tin, qua trinh xir ly thong tin va qua trinh luu trir thong tin. Nhimg qua trinh nay co the dien ra mot cach tuang minh nhu cac qua trinh thong tin trong ky thuat vien thong, nhung cung co khi khong tu ang minh nhir
12 Ly t huy i t thong tin va nui hoa qua trinh thong tin trong cac te bao cua co the song vira de cap a phan tren. Doi vai qua trinh hinh thanh thong tin cua mot nguon. Iv thuyet thong tin de cap den nhung van de nhu toe do lap tin. do d u thua cua nguon va ma hoa nguon. Doi voi qua trinh truyen dan thong tin. ly thuyet thong tin da chi ra rang, hoan toan co the nhan dugc mot ban tin chinh xac qua mot kenh truyen co nhieu. Doi voi qua trinh luu giu thong tin. ly thuyet thong tin chi ra mire do nen thong tin chira trong mot moi truan g luu tru. De tiet kiem bo nha, nguai ta co gang giam toi da do d u thira cua tep tin can nha. Nhung nguai sir dung may tinh deu rat quen thuoc vai cac tep tin nen duoi ZIP hoac RAR. Thong tin khong ton tai rieng biet ma luon gan lien voi mot vat mang no (Carrier). Vat mang thong tin la mot khai niem tu a n g doi. Tieng noi la vat mang thong tin khi con nguai noi chuyen vai nhau. Chir viet la vat mang thong tin ciia nha van, nha bao den vai nguai doc. Birc tranh la vat mang thong tin ciia hoa si muon chuyen tai nguai xem. Tren cac may vi tinh, cac bit thong tin dugc mang tren cac xung dien, v.v... Tat ca cac qua trinh trao doi thong tin deu dien ra qua ba buac chinh. Buac 1, ma hoa thong diep tai nguon phat. B uac 2. truyen thong diep qua mot kenh trao doi thong tin. B uac 3, giai ma thong diep tai nai thu. Tai buac 1, thong diep can gui dugc dien ta du ai dang m ot tap hcrp nhung ky hieu hay tin hieu. Nhirng ky hieu nay co the la tir ngu. not nhac, bieu tugng, cong thirc toan hoc, v.v... Khi noi “xin chao" tire la nguai noi da ma hoa su chao hoi ciia minh vao hai tir do. Khi viet mot ban nhac nguai nhac sT da ma hoa cac am thanh khac nhau qua cac ky hieu am nhac. Ma hoa tro nen huu hieu vi no se dugc truyen den mot nguai hay mot vat khac. Viec truyen thong diep da ma hoa co the thong qua mot la thu viet tay. mot cuoc thoai hay mot thu dien tu, v.v... Tai nai thu, thong diep se dugc giai ma de tra lai dang ban dau no da sinh ra a nguon. Khi nghe thay hai tir "xin chao”. nguai biet tieng Viet se suii md va ho hieu nguai ta dang chao minh. N guai khong biet tieng \ :c: se khong the giai ma hai tir "xin chao" va se khong hieu nguon noi ch.. Cn vai minh muon truyen dat thong diep gi vi ho khong biet qui luat ma hoa thong tin trong hai tir do.
Chuang I : M a dau 13 Theo cach nhin nhan thong thuang, mot tin doi vai nguai nhan co hai dac trung: do bat nga cua tin va y nghTa cua tin. De so sanh hai tin vai nhau, co the lay mot trong hai hoac ca hai dac tinh ke tren. Y nghTa cua tin la mot van de ca nhan thuoc ve nhung nguai cu the muon trao doi thong tin vcri nhau. Vi du, tin “ tdi nay tai rap Thang Tam chieu phim khong mat l i e n Doi vai nhung nguai thich xem phim thi day la mot tin quan trong. Nhung doi vai nhung nguai khong thich xem phim thi tin do chang co y nghTa gi. Viec xir ly y nghTa rieng biet cua tin la mot van de ngay nay cung dugc nhieu nguai quan tarn, dac biet la khi xay dung cac he chuyen gia hay tri tue nhan tao. Nhung y nghTa cua mot tin lai khong lam anh hucrng den cac he thong truyen tai, xir ly va luu giur thong tin. Mot dac trung nua cua thong tin la do bat n ga cua tin. Vi du, mot tin cang bat nga, sir xuat hien cua no cang hiem thi thai gian no chiem trong he thong truyen tin cang it. N hu vay, muon nang cao hieu suat cua cac he thong truyen tin, ta khong the coi cac tin nhu nhau neu chung xuat hien nhieu it khac nhau. Do bat nga cua tin co sire cuon hut manh me va nganh bao chi hay khai thac dac diem nay. Ly thuyet thong tin truac het lay do bat nga cua thong tin lam dac trung de so sanh cac tin vai nhau. Nhu vay, mot tin co lugng tin cang lan neu no co do bat n ga lan. Dieu nay la hgp ly vi nhan mot tin da biet truac thi coi nhu khong nhan dugc gi' ca. Noi cach khac, neu nguai nhan da biet tin do thi ho can gi phai nhan nua. Chung ta co the coi thong tin la mot dai lugng ngau nhien. Xac suat xuat hien mot tin lien quan den do bat nga cua tin do. Xac suat xuat hien tin cang nho thi do bat nga cang lan. Cung giong nhu nhieu ly thuyet khac. ly thuyet thong tin su dung cac mo hinh toan hoc chu khong sir dung true tiep cac nguon va cac kenh vat ly cu the. Ly thuyet thong tin xem qua trinh thong tin nhu la nhung qua trinh ngau nhien vai nhung dac trung xac suat cho truac hoac khong cho tnrac. Mo hinh nguon la nhung c a che ngau nhien sinh ra cac tin. N guai ta tlnrang lay dac tinh cua qua trinh ngau nhien tao ra nguon de dat ten cho nguon. thi du nguon dung, nguon Markov. Trong truang hgp nguon rai rac. mo hinh nguon la mot bang an-pha-be gom L chu' cai vai xac suat chu cai do dugc chon ra trong nhung tinh huong nhat dinh nao
14 Ly thuyet thong tin va mu hoa do. Nguon co the con dugc dac trung boi trang thai va cac xac suat chuyen trang thai. Khi thong tin dugc truyen tren kenh (moi truan g truyen tin) no thuang chiu tac dong cua nhung nguon tin khong mong muon (nguon nhieu) va do vay mo hinh kenh thuong dugc dac trung qua mo hinh nguon nhieu. Do tin cay cua mot he thong truyen tin la do do xac suat thong diep dugc truyen di dung dan. 0 cac kieu truyen tin chac chan, do tin cay cung co the la do do su xuat hien cua thong diep. Theo ly thuyet thong tin, lugng tin cua mot thong diep khong the tang a bat ky noi nao tren duong truyen tin cay mot khi thong diep da rai nguon phat (su giam en-tro-py thong tin). H an nua. trong cac he truyen tin khong nhieu, khong co thong tin them nao nhan dugc a bo thu neu n hu mot thong diep dugc truyen lai. N gugc lai, tren cac kenh co nhieu. en-tro-py luon co chieu h uang tang. Tuy nhien, doi vai nhung tuyen truyen co nhieu. do tin cay cua su truyen tai co the tang nho do du thua (Redundance). Su tang do tin cay n h a do d u thua dugc goi la su giam nhieu (Noise Reduction). Chang han. truyen hai lan mot thong diep la bien phap de giam nhieu. Ly thuyet thong tin dem lai mot sir phan tich dinh lugng nhung c a che giam nhieu va gia tri thuc cua viec giam nhieu a cac he th 6 ng khac nhau. Trong nhung bien phap chong lai tac dong cua nhieu la m a hoa. Day cung chinh la ly do vi sao ma hoa khong tach rai ly thuyet thong tin va de nhan manh tam quan trong cua no. cuon sach nay co ten “ ly thuyet thong tin va ma h oa” thay vi “ ly thuyet thong tin ” n h u cac cu 6 n sach khac cung loai. 1.3. SO DO TONG QUAT CUA HE THONG TRUYEN TIN Hinh 1.3-1 dien ta so do khoi mot he thong truyen tin (mang nhieu y nghTa ky thuat) th uang gap hien nay. N hiem vu cua ho md hoa nguon (Source Encoder) la dien ta thone tin dau ra cua nguon duai mot dang thich hop nao do (chang han duai dang mot chuoi cac bit nhi phan). Ma hoa nguon con can thiet de phat hien loi va sua sai trong qua trinh truyen tin. Mot cau hoi quan trone dugc dat ra la. phai tao ra bao nhieu bit nhi phan trong mot dan \ i thai
Chuang 1: M a dau 15 gian de dien ta dau ra cua cac mo hinh nguon khac nhau. Ducmg nhien, neu 6 dau phat thong tin dugc ma hoa thi a dau thu phai co bo giai md nguon (Source Decoder) de thu dugc thong tin nguyen thuy. Bo md hoa kenh (Channel Encoder) va bo giai md kenh (Channel Decoder) cho phep nang cao do chinh xac cua cac chuoi thong tin tir bo ma hoa nguon di qua kenh den noi nhan. Ngoai ra ma hoa kenh con co the lam tang thong lugng kenh. Cau hoi quan trong nhat cua ma hoa kenh la, phai ma hoa nhu the nao de xac suat giai ma sai duai tac dong cua nhieu la nho nhat. Hinh 1.3-1: Sa do khoi cua he thong truyen tin Tir goc do ung dung, viec tach biet cac bo ma hoa va giai ma cho nguon va kenh la rat tien lgi. Bai vi cac kenh truyen tin hien nay phan lan truyen cac tin hieu nhi phan va viec thiet ke cac bo m a hoa va giai ma kenh hoan toan doc lap vai viec thiet ke cac bo ma hoa va giai ma nguon. Dieu nay rat can thiet cho viec ghep cac nguon khac nhau len cung mot kenh. Han nua. doi hoi ve do chinh xac trong truyen tin cung khac nhau doi vai cac nguon khac nhau. Chang han cac thong tin co ban chat am thanh (dien thoai) khong can do chinh xac cao nhu cac thong tin co ban chat d u lieu (data). Ngay nay cac kenh truyen tin mang tinh cong nghe n hu mang vien thong B-1SDN hay NGN thuang dugc dung de truyen cac thong tin da phu an g tien (Multimedia Information) vai nhung yeu cau ve chat lugng khac nhau va do do da hinh thanh cac giao thuc truyen tin khac nhau. Do dac diem vat ly cua moi truang truyen tin. khi truyen tin
16 Ly t huy i t thong tin va md hoa di xa. ngucri ta phai dieu che cac tin hieu (vat mang) thong tin. C hang han cac tin hieu truyen hinh so phat vao khong trung la cac thong tin da d u a c dieu che bai cac song dien tir vai tan so rat cao. Nhin a goc do ciia ly thuyet thong tin, cac giao thuc truyen tin, cac ph u an g phap ma hoa, cac phucmg phap dieu che tin hieu,... khong gi khac la nhirng giai phap ngSn chan su tang en-tro-py thong tin trong qua trinh van dong cua no. Tuy nhien cung can phai lam ro mot van de la, khong phai luc nao cung co the dien ta cac qua trinh thong tin dua tren viec ap dung s a do khoi a hinh 1.3-1. Chang han, khong the ap dung so do khoi hinh 1.3-1 de nghien ciru cac qua trinh truyen tin trong c a the sinh vat. Bai vi, nhu trong phan tren da neu, cac bo phan nguon va kenh cung n h u cac chirc nang ma hoa va giai ma duac ket hop trong mot tong the het sire phirc tap, khong the de dang phan biet. Mac dau vay s a do he thong truyen tin neu tren van giCr mot vai tro dac biet trong suot cuon sach nay vi no duac viet chu yeu cho nhung nguai hoat dong tren lmh vuc vien thong va cong nghe thong tin. Hai c a cau trong so do khoi hinh 1.3-1 se d u ac de cap nhieu trong cac phan tiep theo la nguon va kenh. Viec nghien ciru nguon va kenh duai goc nhin ciia ly thuyet thong tin, chung ta se dua chu yeu vao cac mo hinh toan hoc chir khong quan tam den cac nguon va kenh vat ly cu the. Day la viec lam can thiet bai vi cung nhu ly thuyet he thong hay ly thuyet dieu khien, mo hinh toan hoc giiip cho viec phan tich cac tinh chat ciia doi tugng de dang va hieu qua hern. 1.4. NHLrNG KIEN THLfC CO SO VE XAC SUAT VA QUA TRINH NGAU NHIEN N hu tren vira nhac den. ly thuyet thong tin sir dung nhi£u mo hinh toan hoe dac biet la mo hinh ngau nhien. Muc dich ciia phdn nay la giup nguai doc. jiac biet nhung nguai khong co diSu kien nghien ciru ky mon ly thuyet xac suat va qua trinh ngau nhien, de dang trong viec tiep can Iv thuyet thong tin. 1.4.1. Phep th ir v a bien co Viec thuc hien mot so cac dieu kien c a sa roi quan sat xem hien tugng gi se xay ra va xay ra nhu the nao goi la thirc hien mot phep thu
Chuang 1: M a dau 17 Vi du ta dat len mot dau day dan mot tin hieu dien co dang hinh sin voi tan so 1000 Hz roi do xem tin hieu a dau kia cua day dan xuat hien nhu the nao. Ngudi ta thuang dat cho moi phep thu mot cai ten de phan biet, thi du “phep tung dong xu”, “phep tung con xuc xac”, hay tong quat han, “phep thu a ”, “phep thu P”, v.v... Nhung hien tu an g co the xay ra khi phep thu dugc tien hanh goi la bien co. N guai ta phan biet ba loai bien co sau: • Bien co luon luon xay ra moi lan lap lai phep thu dugc goi la bien co chdc chan xay ra. Vi du, tung mot vat ran len trai chac chan no se rai tra lai xuong mat dat; tha mot mieng xop xuong nuac chac chan no se noi. • Bien co khong bao gia xay ra du co lap lai phep thu bao nhieu lan tiiy y dugc goi la bien co khong the xay ra. Vi du, cho ga ap trung da luoc chin chac chan khong the nao no ra ga con. • Bien co khi thi xay ra. khi thi khong xay ra dugc goi la bien co ngau nhien. Vi du, khi quay chiec non cua chuang trinh “Chiec non ky dieu” tren VTV3 cua Dai Truyen hinh Viet Nam, khong ai co the noi truac, trong mot lan quay mui kim co chi vao o “phan thuang” hay khong. Viec phan biet ba loai bien co tren day khong can thiet va mang tinh chat tuang doi. Vi rang, nhu sau nay se thay, bien co chac chan xay ra co the xem la bien co ngau nhien vai xac suat xuat hien bang 1, bien co khong the xav ra co the coi la bien co ngau nhien vai xac suat xuat hien bang 0. N guai ta thuang dung cac chu cai hoa de chi cac bien co. Vi du, bien co A, bien co B|, bien co B?,... 1.4.2. Djnh nghTa xac suat Kha nang khach quan xuat hien bien co ngau nhien khi thuc hien phep thu dugc goi la xac suat xuat hien hay xac suat cua bien co. Co nhieu cach dinh nghTa xac suat khac nhau. chang han xac suat dugc cac nha toan hoc dinh nghTa kha trim tugng nhu la mot do do trong truang a (khong gian metric). Chung ta xet mot vai dinh nghTa mang tinh true giac thuang dugc su dung.
18 L y thuyet thong tin vd md Iwa Dinh nglila 1.4-1: Xac suat xudt hien hien co A Id ty so giiia cac ket cuc thuan loi cho A vd long so cac ket cuc duy nhat dong kha nang co the co khi thuc hien mot phep thu. Ky hieu so eae ket cuc thuan loi cho bien co A la n A va tong so cac ket cuc duy nhat dong kha nang co the co cua phep thir la N. Khi do xac suat xuat hien bien co A se dugc tinh bang: p(A) = — (1 4 - 1 ) N Vi du doc ngau nhien mot byte trong bo nho may vi tinh. tinh xac suat de byte do gom 4 bit 0 va 4 bit 1. Ky hieu bien co nay la A. Ta thay rang moi byte gom 8 bit va nhu vay ta co tong cong 256 bien co dong kha nang. Ta thay trong 256 byte khac nhau co 70 byte bao gom dung 4 bit 0 va 4 bit 1, nghTa la co 70 ket cuc thuan lgi cho bien co A. Theo dinh nghTa 1.4-1 va bieu thuc (1.4-1), xac suat xuat hien bien co A dugc xac dinh bai: p(A) = — = 0.273 (1.4-2) 256 Tir dinh nghTa tren ta rut ra cac tinh chat sau day cua xac suat: • Xac suat cua mot bien co ngau nhien la mot so d u a n g nam trong khoang 0 va 1, nghTa la 0 < p(A) < 1. Dieu nay rat de chimg minh vi so ket cuc thuan lgi cho bien co A luon luon thoa man bat dang thirc 0 < n A < N. • Xac suat cua bien co chac chan xay ra bang 1. That vay. vi khi bien co A chac chan xay ra thi moi ket cuc deu thuan lgi cho A hay nA = N. • Xac suat cua bien co khong the xay ra bang 0. That vay. \ i bi^n co A khong bao gia xay ra nen nA = 0. Dinh nghTa tren day cho phep tinh xac suat ciia mot bien co kha don gian. khong can phai tien hanh phep thu that ma chi can phep thu eia dinh. Tuy nhien iru diem nay chi dugc phat huy khi ma so ket cuc cua phep thu la nho. de dang kiem tra tinh duy nhat dong kha nang cua cac bien co. Neu so ket cuc Ion hoac vo han thi dinh nghTa tren khong ap
Chuang 1: M a dau 19 dung dugc nua. Trong truang hgp nay, nguai ta dinh nghia xac suat mot cach tong quat han. D inh nghTa 1.4-2: Gia sic mot phep thu duac tien hanh K lan vd quan sat thay bien co A xudt hien nA lan. Dai luang: li(A) = %r (1.4-3) K duac goi la tan suat xudt hien bien co A. Neu ton tai giai han: lim \x{A)~ lim — = p (A ) (1.4-4) K— ►co K-»co fc thi p(A) duac goi la xac suat cua bien co A. Trong thuc te khi ta tang K len tai mot gia tri K* du lan nao do thi |a(A) bat dau thay doi rat it. Vai gia tri K* do co the lay: p (A )« n (A ) = ^ (1.4-5) IV 1.4.3. Nguyen ly xac suat nho va xac suat loti Trong nhieu truan g hgp ta gap cac bien co co xac suat xuat hien rat nho, gan nhu bang khong. Ve mat ly thuyet, xac suat du rat nho bien co van co the xay ra. va dieu dang noi la khong biet no xay ra a lan thir thu may. Tuy nhien qua kinh nghiem thuc te nguai ta thay rang, cac bien co co xac suat nho hau nhu se khong xay ra khi tien hanh phep thir trong K lan thir dau tien. H an nua, viec tien hanh nhieu phep thir se gay ra nhung ton kern ve thai gian va nguon lire. Vi vay, trong hau het cac ung dung thuc te, ta chap nhan nguyen ly xac suat nho sau day: Neu mot bien co ngau nhien co xac suat rat nho thi thuc te co the cho rang trong mot vai lan tien hanh phep thu, bien co do khong xay ra. Theo quan diem img dung, viec qui djnh xac suat bang bao nhieu thi goi la nho phai tiiy thuoc vao van de cu the. Trong ky thuat vien thong hien nay, xac suat loi bit tren mot kenh truyen so lieu theo khuyen cao ciia ITU la 10’ . Dieu nay co nghTa la, khi truyen di 10 trieu bit moi dugc phep sai mot bit. Trai lai. xac suat mot khach hang den cira hang bang 10"'
20 Ly tliuyei thong tin va ma hoa co the coi la nho, nghTa la cua hang co the dong cua vi tren thuc te hau nhu khong co ai den mua hang. Lap luan tu ang tu nhu tren, ta co nguyen ly xac suat lan sau day: Neu mot hien co ngau nhien co xac suat xudt hien Ion gun hang 1 thi thuc te co the cho rang trong mot vdi lan tien hanh phep thu hien co do se xay ra. Cung nhu truang hap xac suat nho. xac suat bang bao nhieu thi duac coi la lan hoan toan tuy thuoc vao dac diem cu the cua van de ma ta quan tarn. 1.4.4. Nguyen ly cong va nhan xac suat Bien co C duac goi la tong cua hai bien co A va B neu C xay ra khi A xay ra hoac B xay ra. ky hieu la: C =A+ B (1.4-6) Vi du, ta goi A la bien co xuat hien mat 2, B la bien co xuat hien mat 4 va C la bien co xuat hien mat chan khi tung con xuc xac. Ta de dang nhan ra rang C = A + B vi mat 2 hoac mat 4 deu la mat chan. Mot cach tong quat. bien co C dugc goi la tong cua cac bien co A |, A :.....A„ neu C xay ra khi co it nhat mot bien co A, xay ra, ta ky hieu la: C=£ a, (1.4-7) 1=1 Hai bien co A va B goi la xung khac vai nhau neu chung khong the xay ra trong cung mot phep thu. Vi du, goi A la bi£n co nhan dugc bit 0 va B la bien co nhan dugc bit 1 tren kenh truydn tin thi A va B la xung khac nhau. vi hien nhien bit 0 va bit 1 khong thS xudt hien dong thai. Ngugc lai. A va B dirge goi la khong xung khac nhau neu chung co the xay ra trong cung mot phep thir. Vi du, n£u goi A la bic;n c 6 m ua va B la bien co gio thi hai bien co nay khong xung khac nhau vi m ua \ a gio co the cung xay ra. Neu A], A;...., An la n bien co xung khac nhau timg doi mot thi chung lap thanh mot nhom day du. Ta co djnh ly sau:
Chuang 1: M a dau 21 Dinh ly 1.4-1: Neu {A,} = {A„ A,,..., A,,} (1.4-8) Id mot nhom day du thi: p(As + A,) = p(A s) + p(A,) (1.4-9) va T A, = 2 > w = i (1.4-10) /’=! Neu A va B la hai bien co lap thanh mot nhom day du thi B goi la bien co bu cua A va ng u ac lai, ky hieu la B = A va A = B . Vi du bien co “con trai” va bien co “con gai” la hai bien co bu nhau cua nhom bien co “ giai tinh tre s a sinh” khi mot dua tre ra dai. Ta de dang thay rang: p(A ) = l - p ( A ) (1.4-11) Bien co C dugc goi la tich cua hai bien co A va B neu C xay ra khi va chi khi ca hai bien co A va B xay ra, ky hieu la: C = A.B (1.4-12) Vi du, bien co “den dien sang” la tich cua hai bien co “co dien" va “cong tac dong” . Mot cach tong quat, bien co C dugc goi la tich cua n bien co A |, A:,..., A n neu C xay ra khi va chi khi tat ca cac bien co A, xay ra, ky hieu la: c= n A , (1.4-13) Hai bien co A va B goi la doc lap (hay doc lap thong ke) vai nhau neu viec xay ra bien co nay khong lam thay doi xac suat xuat hien bien co kia va ngugc lai. Neu mot bien co xay ra lam thay doi xac suat xuat hien bien co kia thi chung khong doc lap vai nhau. Cac bien co A |, A :.....A n goi la doc lap tung doi mot vcri nhau neu moi cap hai trong n bien co do doc lap vai nhau. Cac bien co A |. A :.......\ n goi la doc lap toan phan voi nhau neu moi bien co doc lap voi mot to hop bat ky cua cac bien co con lai.