Bài giảng Chương 3 Mã hoá môn Lý thuyết truyền tin | Học viện Công Nghệ Bưu Chính Viễn Thông

HỌC VIỆN CÔNG NGHỆ BƯU CHÍNH VIỄN THÔNG BÀI GIẢNG MÔN
LÝ THUYẾT TRUYỀN TIN Bộ môn:
Tín hiệu & Hệ thống - Khoa VT1
Học kỳ/Năm biên soạn: II/2022 BÀI GIẢNG MÔN LÝ THUYẾT TRUYỀN TIN Nội dung
▪ Chương 1 : Giới thiệu về lý thuyết truyền tin
▪ Chương 2 : Cơ sở lý thuyết truyền tin
▪ Chương 3 : Mã hóa
▪ Chương 4 : Ghép kênh
▪ Chương 5 : Điều chế tín hiệu
▪ Chương 6 : Nhiễu và bộ thu tối ưu www.ptit.edu.vn
BỘ MÔN: TH & HT - KHOA VT1 Trang 2 BÀI GIẢNG MÔN
LÝ THUYẾT TRUYỀN TIN Ch ương 3 - Mã hóa . ▪ Tổng quan về mã hóa
▪ Một số vấn đề cơ bản trong mã hóa
. Mã hiệu và thông số cơ bản của mã hiệu
. Phương pháp biểu diễn mã
. Điều kiện phân tách của mã hiệu
. Mã hệ thống
. Phát hiện và sửa lỗi ▪ Mã hóa nguồn
. Mã hóa cho các nguồn tin rời rạc
. Mã hóa cho các nguồn tin liên tục ▪ Mã hóa kênh
. Mã kiểm tra chẵn lẻ
. Các mã đa thức
. Mã khối tuyến tính
. Mã tích chập www.ptit.edu.vn
BỘ MÔN: TH & HT - KHOA VT1 Trang 3
– Trong các HTTT rời rạc/ liên tục đã được rời rạc hóa, bản tin
thường qua các chuyển đổi:
. Phía phát: bản tin được chuyển đổi thành số (nhị phân) dưới
dạng các từ mã - quá trình mã hóa,
. Phía thu thực hiện chuyển đổi ngược lại từ các từ mã thành
bản tin - quá trình giải mã.
– Mã hóa/giải mã: cho phép tăng tính hiệu quả và độ tin cậy của
hệ thống truyền tin, nghĩa là tăng tốc độ truyền tin và khả năng
chống nhiễu của hệ thống.
– Nhiệm vụ mã hóa/giải mã:
. Biến đổi tính thống kê của nguồn làm cho tốc độ lập tin tiệm
cận với khả năng truyền của kênh.
. Trường hợp truyền tin trong kênh có nhiễu: cần đảm bảo độ
17/03/2022chính xác của quá trình truyền tin (các tin truyền đi ít bị sai lỗi)4.
3.2.1 Mã hiệu và thông số cơ bản của mã hiệu
• Các khái niệm liên quan đến mã hiệu:
– Mã hiệu gồm một tập hữu hạn các ký hiệu có phân bố xác suất nào
đó, gọi là dấu mã hay ký hiệu mã
– Tập hợp một số dấu mã gọi là tổ hợp mã
– Trong tập hợp tất cả các tổ hợp mã, một tập hợp các tổ hợp mã được
xây dựng theo một quy luật nào đó, gọi là tổ hợp mã hợp lệ
– Trong quá trình mã hóa, một tin nguyên thủy được ánh xạ vào một
tổ hợp mã. Một tổ hợp mã như vậy gọi là từ mã. Những tổ hợp mã
khác gọi là tổ hợp cấm (không sử dụng).
– Một dãy từ mã bất kỳ tạo thành một từ thông tin
– Quá trình ngược lại của quá trình mã hóa được gọi là giải mã
– Ngoại lệ: mã hóa một chuỗi các tin của nguồn tin nguyên thủy thành
một hoặc nhiều từ mã: mã khối (mã theo từ) 6
3.2.2 Phương pháp biểu diễn mã
– L à cách trình bày toàn bộ mã hiệu với các tin được mã hóa .
– Các dạng biểu diễn mã thường được dùng là : các bảng
mã , đồ hình mã và các hàm cấu trúc mã . 17/03/2022 11
3.2.2 Phương pháp biểu diễn mã
Đồ hình kết cấu: được dùng 3.2.2.2 Đồ hình mã:
để xét cách vận hành của
thiết bị mã hoá và giải mã15. – Đồ hình kết cấu:
. Cách biểu diễn cây mã rút gọn: gồm các nút và nhánh có hướng.
. Mỗi nhánh có hướng: biểu diễn một hoặc nhiều ký hiệu.
. Một từ mã: biểu diễn bằng một vòng kín đi
từ nút gốc theo các nhánh có hướng qua các
nút trung gian và trở về nút gốc.
. Trị của các nhánh: được ghi bên trái, ở đầu
xuất phát của nhánh. . Dấu V: dấu “hoặc”, đại
diện cho trị bên trái hoặc phải của dấu V.
. Các nút được đánh số theo thứ tự xa dần
nút gốc (số ghi trong vòng tròn của nút). . Thứ
tự trị các ký hiệu lấy theo thứ tự các
17nhánh/03/2022 trên đường đi.
Ví dụ: Đồ hình kết cấu cho bộ mã 00, 01, 100, 1010, 1011.
3.2.2 Phương pháp biểu diễn mã
Bài tập : Cho bộ mã 00 , 10 , 110 , 1110 , 10010 , 11100 .
Hãy biểu diễn mã bằng : • Bảng đối chiếu • M ặt tọa độ • Cây nhị phân • Đồ hình kết cấu
• Hàm cấu trúc của mã 17/03/2022 17
3.2.3 Điều kiện phân tách của mã hiệu
3.2.3.1 Điều kiện để mã phân tách được:
– Các tin mã hoá là một dãy ký hiệu mã liên tiếp nhau khi truyền.
– Để giải mã (khôi phục các tin):
. Điều kiện: chuỗi ký hiệu mã có quy luật đảm bảo tách duy nhất các
từ mã. Nghĩa là: bất kỳ một dãy các từ mã nào của bộ mã cũng
không được trùng với một dãy các từ mã khác của cùng bộ mã.
Mã prefix: bộ mã không có bất kỳ từ mã nào là phần đầu (prefix) của
một từ mã khác trong cùng bộ mã. Ví dụ:
Tập mã 1: {1,00,01,10}: không có tính prefix
Tập mã 2: {0,10,110,111}: có tính prefix
. Nếu điều kiện không được thỏa mãn: có nhiều cách để tách hoặc
không tách được → bản tin sau giải mã khác bản tin đã phát. Bộ
mã như vậy, gọi là mã không phân tách được (không giải mã duy nhất) 18
3.2.3 Điều kiện phân tách của mã hiệu
3.2.3.1 Điều kiện để mã phân tách được:
Ví dụ: Xét bộ mã ={0,10,11}mã hóa cho nguồn ={,,} theo quy luật: →0; →10; →11. -
Phía phát gửi bản tin = , tương ứng dãy từ mã được phát đi là =0100011. -
Phía thu chỉ có một khả năng để tách mã đúng là: 0 | 10 | 0 |
0 | 11 và xác định được bản tin đã được gửi đi là .
Ví dụ: Xét bộ mã ={0,10,01}mã hóa cho nguồn ={,,} theo quy luật: →0; →10; →01. -
Phía thu nhận được dãy =01010và thực hiện tách mã, có thể
có ba khả năng: 0 | 10 | 10 ; 01 | 0 | 10 hoặc 01 | 01 | 0 → Phía thu
không biết chính xác phía phát đã gửi đi bản tin nào
17/03/2022 trong 3 bản tin: hay hay . 19
3.2.3 Điều kiện phân tách của mã hiệu
3.2.3.2 Bảng thử mã và độ chậm giải mã:
– Dựa vào tính prefix, để nhận biết một bộ mã có phân tách được hay
không, thường dùng một công cụ gọi là bảng thử mã.
– Bản chất của bảng thử mã: phân tích những từ mã dài thành những từ mã ngắn dần.
– Cách thực hiện bảng thử mã:
. Xếp các từ mã thành cột (cột 1): theo thứ tự chiều dài tăng dần.
. Đối chiếu các từ mã ngắn với từ mã dài hơn, nếu từ mã ngắn là phần
đầu (prefix) của từ mã dài thì ghi tiếp phần còn lại vào cột 2.
. Tiếp tục đối chiếu các từ mã trong cột 2 và cột 1: nếu là prefix của
một từ mã trong cột kia, phần còn lại sẽ được ghi vào cột 3.
. Tiếp tục xét theo qui tắc này (nếu đang xét ở cột thứ j thì đối chiếu
các chuỗi trong cột này với cột 1), đến khi nào thu được cột trống. 20
3.2.3 Điều kiện phân tách của mã hiệu
3.2.3.2 Bảng thử mã và độ chậm giải mã:
– Định lý: Điều kiện cần và đủ để mã có tính phân tách là không có một
từ mã nào trong các cột j≥2, trùng với một từ mã trong cột 1.
– Độ chậm giải mã: là số ký hiệu cần phải nhận được đủ để có thể phân tách được từ mã.
– Đối với mã phân tách: độ chậm giải mã thường là hữu hạn, nhưng
cũng có trường hợp độ chậm giải mã là vô hạn.
– Bảng thử mã phân tách cho phép đánh giá độ chậm giải mã. Nếu
là số hiệu cột rỗng, thì độ chậm giải mã được tính: ≤ ≤ (3.4) trong đó:
và là độ dài từ mã ngắn nhất và dài nhất, là ký
hiệu chỉ phần nguyên của . 17/03/2022 21 3.2.4 Mã hệ thống
3.2.4.1 Mã hệ thống tổng quát:
– Mã hệ thống: từ mã được tạo thành từ một bộ các từ mã gốc.
– Mã hệ thống thường dùng:
. Các từ mã thuộc mã gốc chia làm 2 loại: từ mã đầu và từ mã cuối.
. Từ mã hệ thống được tạo ra từ các từ mã đầu và một từ mã cuối.
– Biểu diễn mã hệ thống:
. Sử dụng đồ hình kết cấu thay đổi. Trong đó: từ mã đầu kết thúc ở
nút gốc, còn các từ mã cuối kết thúc ở một nút kết thúc riêng.
. Từ mã hệ thống được biểu diễn bằng các nhánh đi từ nút gốc, qua
nút gốc nhiều lần, rồi kết thúc ở một nút kết thúc.
– Giải mã mã hệ thống: qua 2 bước
. B1: Tách từ mã nhận được thành từ mã đầu và từ mã cuối.
. B2: Tách các từ mã hệ thống, bằng cách tìm các từ mã cuối và
17/03/2022 xác định điểm kết thúc từ mã tại đây. 25
3.2.4 Mã hệ thống 3.2.4.3 Mã có dấu phân tách:
– Các mã hệ thống có tính prefix đều có tính phân tách được, nhưng
quá trình phân tách mã khá phức tạp.
– Để đơn giản hóa, trong điều kiện có nhiễu dùng một từ mã kết thúc
gọi là dấu phân cách để tách các từ mã hệ thống.
– Tống quát, có thể dùng một ký hiệu, một chuỗi ký hiệu đặc biệt để
phân tách các từ mã. Chuỗi này không được trùng với bất cứ một từ mã nào trong bộ mã.
– Dấu phân cách thường được thiết kế để có khả năng chống nhiễu.
Khi đó quá trình truyền (xử lí) tin được chia thành nhiều công đoạn
độc lập lẫn nhau bằng các dấu phân cách (đồng bộ hóa).
– Khi giải mã, các ký hiệu nhận được được ghi vào một bộ đệm rồi so
sánh với dấu phân cách (ví dụ: Bộ lọc tuyến tính điều chỉnh theo
17/03/2022 dấu phân cách). 27
3.2.5 Phát hiện và sửa lỗi 3.2.5.1
Nguyên tắc phát hiện lỗi:
– Số các từ mã (tổ hợp mã mang tin) được chọn phải nhỏ hơn tổng số
các tổ hợp mã có thể.
– Sử dụng các tổ hợp cấm để phát hiện việc truyền tin sai. Cần lựa
chọn các từ mã và các tổ hợp bị cấm để: . Hiệu quả: số lượng tổ hợp
mã có thể không quá nhiều . Chính xác: đảm bảo sai lỗi luôn sinh ra một tổ hợp cấm
– Đảm bảo một từ mã không bị truyền sai thành một từ mã khác.
– Khả năng phát hiện lỗi: tỷ lệ có tổ hợp cấm khi có lỗi .
– Để khả năng phát hiện lỗi lớn: từ mã phải có độ dài lớn hơn nhiều
so với chiều dài tối ưu.
→ Một bộ mã cho phép phát hiện lỗi: bộ mã được xây dựng sao cho
mọi từ mã bị lỗi trên đường truyền phải được chuyển thành tổ hợp 17/03/2022cấm. 30
3.2.5 Phát hiện và sửa lỗi
3.2.5.2 Nguyên tắc sửa lỗi:
– Cơ chế sửa lỗi đồng thời cũng là nguyên lý giải mã phải dựa vào tính
thống kê của kênh để đảm bảo lỗi tối thiểu.
– Khi nhận được một tổ hợp cấm, thiết bị sửa lỗi có nhiệm vụ quy về
từ mã phát đi với xác suất lỗi tối thiểu.
– Cần phải dựa vào tính chất nhiễu trong kênh để phân nhóm các tổ
hợp cấm, mỗi nhóm tương ứng với một từ mã mà chúng có khả năng
bị chuyển đổi sang nhiều nhất.
→ Một bộ mã cho phép sửa được lỗi: bộ mã được xây dựng sao cho
mỗi từ mã khi bị lỗi sẽ chuyển thành những tổ hợp cấm và là những tổ
hợp cấm của chỉ riêng nó. 17/03/2022 31
3.3.1 Một số khái niệm chung
– M ã hóa nguồn là phép biến đổi đầu tiên cho nguồn nguyên thủy .
– Đ ầu vào của phép biến đổi này có thể là : nguồn tin rời rạc hoặc nguồn tin nguyên thủy .
– M ục đích chính của phép mã hóa nguồn là : biểu diễn thông tin với tài nguyên tối thiểu r
( út ngắn các bit tín hiệu dư thừa để có thể sử
dụng tối đa dung lượng của kênh truyền) .
– Tín hiệu được mã hóa thành các bit thông tin theo những quy tắc
khác nhau, để nhằm đạt được tới giới hạn Entropi của nguồn .
– Các vấn đề cần nghiên cứu đối với mã hóa nguồn là :
. Mã hóa nguồn liên tục
. Mã hóa nguồn rời rạc . Nén dữ liệu . 32
3.3.1 Một số khái niệm chung
– Nguồn thông tin tạo ra các đầu ra một cách ngẫu nhiên. – Nguồn rời
rạc: tạo ra một chuỗi các ký hiệu ngẫu nhiên.
. Nguồn không nhớ: các ký hiệu xuất hiện độc lập với nhau . Nguồn
có nhớ: các ký hiện xuất hiện phụ thuộc vào các ký hiệu đã xuất hiện trước đó
. Nguồn dừng: các mối liên hệ thống kê giữa các thời điểm không
phụ thuộc vào thời gian.
– Khi mã hóa nguồn rời rạc: thay đổi bảng chữ cái và phân bố xác suất
để giảm bớt lượng ký hiệu cần dùng. Cần quan tâm: Entropi của
nguồn trước khi mã hóa; Entropi của nguồn sau khi mã hóa; Hiệu
quả của phép mã hóa; Giới hạn của phép mã hóa.
. Với nguồn không nhớ: sử dụng từ mã có độ dài cố định hoặc từ mã
có độ dài thay đổi (phương pháp mã hoá nguồn như: Huffman, Shanon Fano)
17/03/2022 . Với nguồn dừng: thường dùng thuật toán mã hoá Lempel-Ziv. 33
3.3.1 Một số khái niệm chung
– Nguồn liên tục: tạo ra tín hiệu liên tục thể hiện một quá trình ngẫu nhiên liên tục.
. Trong HTTT: nguồn liên tục thường được biến đổi thành nguồn rời
rạc, xử lý và truyền tới phía thu lại biến đổi thành nguồn liên tục. .
Các kỹ thuật mã hóa nguồn tương tự: mã hoá dạng sóng miền (t),
mã hóa dạng sóng miền tần số và mã hoá dựa trên mô hình.
– Mô hình toán học của nguồn thông tin:
. Do các nguồn thông tin tạo ra các bản tin một cách ngẫu nhiên, nên
đầu ra của nguồn được đặc trưng bởi các luật thống kê. . Nguồn rời
rạc: Dạng đơn giản nhất là nguồn tạo ra một chuỗi các ký hiệu từ
một bảng chữ cái hữu hạn.
+ Tổng quát, nguồn rời rạc có thể tạo ra một chuỗi các ký hiệu trong
ký hiệu của bảng chữ cái ,,…, có xác suất xuất hiện là . (3.6)34
3.3.1 Một số khái niệm chung . Nguồn rời rạc : Ti ( ếp theo)
+ Xét hai mô hình toán học của nguồn rời rạc :
Mô hình thứ nhất : nguồn rời rạc không nhớ DMS ( ) nếu ký hiệu
xuất hiện một cách độc lập với nhau .
M ô hình thứ hai : nguồn dừng rời rạc ( hay còn gọi nguồn rời rạc có nhớ) .
. Nguồn liên tục : tạo ra một tín hiệu , một thể hiện của một quá trình ngẫu nhiên .
+ Nguồn liên tục có thể được biến thành một chuỗi các biến ngẫu
nhiên ( liên tục) bằng phép lấy mẫu .
+ Lượng tử hóa cho phép biến đổi các biến ngẫu nhiên này thành
các biến ngẫu nhiên rời rạc, với sai số nhất định . 17/03/2022 35