CHƯƠNG I CƠ SỞ LÝ LUẬN SVTH : đàn «ng Yin - Lop 97KDD Trang- 2 - LUẬN VAN TỐT NGHIỆP GVHD : LE MINH THANH CHUONG I CƠ SỞ LÝ LUẬN A. CÁC KHÁI NIỆM CƠ BẢN [MÃ HÓA 1. Định nghĩa: Mã hóa nguồn tin X theo bộ mã M là phép ánh xạ 1: 1 biến đổi một tin x; € X thành một tổ hợp các ký hiệu của bộ mã M. my} Trong đó : K là cơ số của bộ mã.
Ví đu : K=2: là mã nhị phân K= 10: là mã thập phân K=16: là mã thập lục phân 2. Các khái niệm về mã hóa : a) Chiều dài từ mã : Chiều dài từ mã là tổng số các ký hiệu dùng để mã hóa cho từ mã đó. Vídu : Từ mã 0010110 dùng 7 ký hiệu của bộ mã nhị phân nên có chiều dài là 7. SVTH : đâu «ng Ởúa — Lớp 97KĐĐ Trang - 3 - LUẬN VĂN TỐT NGHIỆP GVIID : LÊ MINH THÀNH b) Trọng lượng từ mã : “Trọng lượng từ mã là tổng số các ký hiệu khác 0 của từ mã đó.
Ký hiệu w (Wj) : là trọng lượng của từ mã W;. Ví dụ : Từ mã 0110101 có trọng lượng là 4. €) Quảng cách mã : Quấng cách mã là số ký hiệu khác nhau ở cùng vị trí tương ứng của 2 từ mã có cùng chiều dai. Gọi W¡, Wj là 2 từ mã có cùng chiêu dải.
Mục đích mã hóa: Trong các hệ thống thông tin, mã hóa nhằm mục đích : - Tăng tính hữu hiệu của hệ thống thông tin, nghĩa là tăng tốc độ truyền tin. Trong các hệ thống thông tin, tốc độ lập tin R còn cách xa thông lượng kênh. Nhiệm vụ của mã hóa là biến đổi tính thống kê của nguồn làm cho tốc độ lập tin tiếp cận với khả năng thông lượng của kênh. - Tăng độ tin cậy của hệ thống thông tin, nghĩa là tăng khả năng chống nhiễu.
Trong các kênh truyển có nhiễu, điều ta cần quan tâm đến nhiều nhất là độ chính xác của tin tức, nghĩa là các tin truyền đi và nhận được ít bị sai nhầm. - Bảo mật tin tức. SVTH : Tidn Trung Fin- Lép 97KDD Trang - 4 LUAN VAN TOT NGHIEP GVHD : LE MINH THANH Khi hai bên A và B muốn truyền tin tức cho nhau mà không muốn cho người khác biết được nội dung của tin tức đó thì họ sẽ dùng mã hóa để bảo mật tin tức của họ. Phân loại theo cách tạo mã.
Trong việc truyễn tin có 2 loại mã được sử dụng phổ biến là mã khối (Block code) và mã xoắn (Convolutional code). a) Mã khối: Bộ mã hóa của khối sẽ chia dòng thông tin thành những khối tin (message block) ¢6 k bịt Mỗi tin được biểu diễn bằng khối k thành phần nhi phan u = (u), us. uj), u duge gọi là vector thông tin (message). Có tổng cdng 2° vector thong tin khac nhau, Bộ mã hóa sẽ chuyển vector thông tin u thành một bộ n thành phân (n-tuple) v = (vj, v¿.
vạ) được gọi là từ mã. Nhu va y ting với 2* vector thông tin sẽ có 2" từ mã khác nhau. Tap hgp 2* từ mì u đài n được gọi là một mã khối (n, k). Tỉ số R = k/n được gọi là tỉ số mã.
R chính là số bit thông tin đưa vào bộ giải mã trên số bit được truyền. Do n bit ra chỉ phụ thuộc vào k bít thông tin vào, bộ giải mã không cần nhớ và có thể thực hiện được bằng mạch logic tổ hợp. b) Ma xodn: Bộ mã hóa của mã xoắn giống như bộ mã hóa của mã khối, cũng nhận k bit thông tin u và tạo thành từ mã v là những khối n bit. Nhưng n bit của từ mã v không chỉ phụ thuộc vào k bit thông tin, mà còn phụ thuộc vào m bít thông tin trước đó.
Do đó bộ mã hóa có một bộ nhớ m. Tập hợp dòng mã hóa n bit sinh bởi k thông tin và bộ nhớ m được gọi là mã xoắn (n, k, m). TỶ số R = k/n cũng được gọi là tỉ số mã. Do tính chất của mã xoắn nên phải được thực hiện bằng mach day.
CÁC PHƯƠNG PHÁP BIỂU DIỄN MÃ. Phương pháp liệt kê: Đây là cách trình bày đơn giản nhất : liệt kê trong một bảng những nguồn tin của nguồn và chỉ rõ các từ mã tương tứng. SVTH: đâu Trung Fin - Lop 97KDD Trang- 5 - LUAN VAN TOT NGHIEP GVHD : LE MINH THANH Ví dụ : Nguén tin A = {a), a9, a3, a4, as}, cdc I6p tin cia nó được mã hóa lần lượt như bẳng sau : Tin ay | a a3 ag as | Từ mã 00 | 01 | 100 | 1000 | 1001 Bảng 1.1 : Bằng mã các tin trong nguồn tin A Phương pháp này tuy rõ ràng nhưng không thích hợp bộ mã lớn và cổng kênh 3, Phương pháp mại phẳng tọa độ của mã. Phương pháp này chỉ thích hợp cho các loại mã có trọng số.
Dựa trên 2 thông độ dài n và trọng số b của từ mã để lập nên một mặt phẳng tọa độ. Mỗi từ mã được biểu diễn bằng một điểm trên mặt phẳng tọa độ (n, b). Nếu từ mã V = (vo. Vz) được mã hóa bở bộ mã m có cơ số là m; vị eM và v;=0,l.
Trong đó qui ước vị trí đầu tiên bên trái ứng với ký hiệu vị là vị trí có trọng số nhỏ nhất : m), vị trí thứ ¡ tính từ trái sang phải ứng với ký hiệu vị có trọng số là m'Ì ; vị trí cuối cùng thứ n tương ứng với vạ có trọng số là m”, Khi đó, trọng số b của từ mã là tổng các ký hiệu có trong từ mã sẽ được tính theo công thức : b= Ey, -m”1 Trong đó : vị: Giá trị ký hiệu thứi trong tif ma vj e M. ¡: Số thứ tự ký hiệu từ ma i=1.n m: cơ số của mã Ví dụ : Trọng số của từ mã 1011 là : b=1x2°+0x2!+1x2?+1x2*=13 SVTH : Øiân 2y Øúa - Lớp 97KĐĐ Trang - 6 - LUAN VAN TOT NGHIEP GVHD ; LE MINH THANH Định ló : Không có 2 từ mã của cùng bộ mã nào có thể cùng được biểu diễn cùng một điểm trên mặt phẳng tọa độ (n, b) Ví dụ : Bộ mã : 00, 01, 100, 1010, 1011 sẽ được biểu diễn như sau : uh Hos cme 8 ——— +2.2 : Biểu diễn một bộ mã trên mặt phẳng tọa độ 3. Phương pháp cây : Cây mã gồm có nút lá, nút gốc và các nút trung gian. Gốc của cây gọi là nút gốc (mức 0) từ nút gốc và nút trung gian có thể phát triển tối đa m nhánh (tương ứng với cơ số m) hoặc ít hơn, mỗi nhánh mang một giá trị và kết thúc ở nút mức ¡ + 1.
Ví du :Cây mã cho bộ mã 00, 01, 100, 1010, 1011 được biểu diễn trên hình dưới đây. Từ cây mã, có thể nhận biết mã đã cho là loại mã đều hay không đều, loại mã đầy hay vơi. Mã là đều khi các nút lá có cùng bậc, còn ngược lại là không đều; mã là mã đầy khi tất cả các nút trung gian bậc trước các nút lá đều có m nhánh. SVTH: Tian «uy Za— Lớp 97KĐĐ Trang- 7- LUAN VAN TOT NGHIEP GVHD : LÊ MINH THÀNH Mức gốc (0) Mức 1 (n=1) Mức 2 (n=2) Mức 3 (n=3) Mức 4 (n=4) (1010) (01) Hinh 1.1’: Cây mã nhị phân cho bộ mã 00, 01, 100, 1010, 1011 4.
Phương pháp đồ hình kết cấu : Gốm những mút và nhánh có hướng. Mỗi từ mã được biểu diễn bằng một vòng kín xuất phát từ nút gốc theo các nhánh có hướng (chiều mũi tên) qua các núi trung gián và trở về kết thúc tại nút gốc.2 : Đô hình kết cấu của bộ mã 00, 01, 100, 1010, 1011 Ví du : Đồ hình kết cấu của bộ mã 00, 01, 100, 1010, 1011 được vẽ như hình 1. Dấu v: toán th OR 5. Phương pháp hàm cấu trúc mã: Phương pháp này mô tả rõ ràng một đặc tính quan trọng của mã là sự phân bố các từ mã có độ dài khác nhau.
Ví du : Bộ mã 00, 01, 100, 1010, 1011 có G(n): 2, m=2 Gin, 41,0, =3 2, 7, =4 SVTH : Tién Trung Fin - Lop 97KDB Trang- 8~ LUAN VAN TOT NGHIEP GVHD : LÊ MINH THÀNH 6. Phương pháp dàng ma trận sinh : Phương pháp này là mô hình toán để biểu diễn mã tuyến tính. Đây là công cụ toán học được dùng để tạo mã tuyến tính. Phương pháp dàng đa thức sinh: Phương pháp này là mô hình toán để biểu diễn mã đa thức (mã vòng).
Nhờ công cụ toán này có thể dễ dàng tạo mã và giải mã đối với mã vòng B. CƠ SỞ TOÁN HỌC, 1 TRƯỜNG. L Định nghĩa : Lãy F là một tập hợp. định nghĩa 2 phép toán 2 ngôi : phép cộng (+) và phép nhân (.
Tập F gồm 2 phép toán (+) va (.) là một trường nếu thỏa mãn cúc điều kiện sau : - E là một nhóm giao hoàn đóng với phép cộng. Phần tử đơn vị trong quan hệ phép cộng gọi là phan tử zero (0) và ký hiệu là 0. - Tập hợp các phần tử khác 0 (non zero) trong F là một nhóm giao hoàn dưới phép nhân. Phan tử đơn vị trong phép nhân gọi là đơn vi (unit) và ký hiệu là 1.
- Phép nhân có tính chất phân phối đối với phép cộng : khi cho 3 phần tử a, b, c trong F thì a.c Từ định nghĩa trên ta thấy một trường bao gồm tối thiểu 2 phần tử : phần tử đơn vị của phép cộng và phân tử đơn vị của phép nhân. Số phần tử trong một trường gọi là bậc của trường. Một trường với số phần tử giới hạn gọi là trường hữu hạn. Tính chất: a) Tinh chat 1: Mọi phần tử a và b trong trường thỏa mãn : a.a = 0 SVTH : Fidn Tung Tin - Lop 97KDD Trang - 9~ LUẬN VĂN TỐT NGHIỆP GVHD : Li MINH THANH b) Tính chất 2: Từ 2 phần tử a và b bất kỳ # 0 trong một trường luôn có a.
©) Tỉnh chất 3: Nếu a.b =0 và a #0 thì b=0 d) Vinh chat 4: Cho 2 phan tử a và b bất kỳ trong một trường ta luôn có : (a.(-b) e) Tinh chdt S: Nếu a #0 và á. Các ví dụ : Vi du 1: Xét tập {0,1} cing phép cộng và phép nhân modul-2. Trong ví dụ 2-1 ta thấy {0,1} là một nhóm giao hoán đồng đối với phép cộng modul-2. Dễ dàng kiểm tra phép nhân modul-2 là sự phân phối trên phép cộng modul-2 : a.