Bài giảng Kỹ thuật truyền dữ liệu - Chương 2: Truyền dẫn số

 Chương 2
Truyền dẫn số
Sơ đồ khối chức năng của hệ thống 
thông tin số đầy đủ 
Chức năng của các khối
• Khối định dạng: làm nhiệm vụ chuyển đổi tín hiệu 
 tương tự sang dãy từ mã số. 
• Khối mã hóa: nguồn làm giảm số bit nhị phân yêu 
 cầu để truyền bản tin .
• Khối mật mã hóa: làm nhiệm vụ mật mã hóa bản tin 
 gốc nhằm mục đích an ninh
• Khối mã hóa kênh: làm nhiệm vụ đưa them các bit 
 dư vào tín hiệu số theo một quy luật nào đấy
• Giải mã nguồn,giải mật mã và giải mã hóa kênh 
 được thực hiện ở bộ thu ,các quá trình này ngược 
 với quá trình mã hóa bên bộ phát.
tt
• Khối ghép kênh: giúp cho tuyến truyền thông tin có 
 thể cùng chia sẻ một đường truyền vật lý chung như 
 là cáp,đường truyền vô tuyến
• Khối điều chế: giúp cho dòng tín hiệu số có thể 
 truyền qua một phương tiện vật lý cụ thể theo một 
 tốc độ cho trước,với mức độ méo chấp nhận 
 được,yêu cầu một băng thông tần số cho phép.
• Khối đa truy cập: liên quan đến các kỹ thuật hoặc 
 nguyên tắc nào đó,cho phép nhiều cặp thu phát cùng 
 chia sẻ một phương tiện vật lý chung
→
 Khái niệm mã hóa
 • Cho nguồn tin rời rạc X sinh ra N tin hay ký tự
 độc lập (x 1,x 2,.,x i,,x N).Xét một tập hợp M
 có M phần tử hữu hạn (m 1,m 2,,m q).
 • Mã hóa (encoding) nguồn tin X bằng tập M có
 nghĩa là biến đổi mỗi tin x của nguồn tin X
 thành một tập các phần tử thuộc M nhằm
 thỏa mãn một yêu cầu nào đó của hệ thống
 thông tin:
 • Phép biến đổi ngược lại được gọi là giải mã
 (decoding).
Các tham số cơ bản của mã hóa:
• Tập M được gọi là mã hiệu(code),các phần 
 tử m gọi là ký hiệu mã (symbol),số ký hiệu 
 mã khác nhau trong mã gọi là cơ số của mã 
• Dãy liên tục các ký hiệu mã dùng để mã hóa 
 một tin của nguồn được gọi là từ mã
 (codeword) 
• Số ký hiệu mã có trong một từ mã được gọi 
 là độ dài của từ mã (codeword length) 
• Khoảng cách mã (distance),ký hiệu là d,là số 
 ký hiệu cùng vị trí khác nhau giữa hai từ mã 
 dài bằng nhau 
Các phương pháp biểu diễn mã
a/Phương pháp liệt kê:
• Chỉ cần liệt kê các tin của nguồn và các từ 
 mã tương ứng.
• Ví dụ: nguồn tin có 8 tin (ký tự),các tin được 
 mã hóa như bảng dưới đây:
Các phương pháp biểu diễn mã(tt)
b/Phương pháp ma trận:
• Từ ví dụ trên,ta thấy:có những từ mã là tổ
 hợp tuyến tính của các từ mã khác.Chẳng
 hạn:
• Ví dụ ma trân sinh tương ứng với bảng mã
 trên là :
Các phương pháp biểu diễn mã(tt)
c/Phương pháp cây :
• Cây mã(code tree)
 – nút gốc (root node), 0 1
 – nút lá (leaf node) và các
 – nút nhánh (branch).
• Mỗi nhánh mang một ký hiệu mã,đó là giá trị của
 nhánh.
• Nhánh được bắt đầu ở nút mức i và kết thúc ở nút
 mức i+1.
• Từ mỗi nút nhánh phân ra tối đa q nhánh.
• Từ mã bao gồm các ký hiệu mã là giá trị của các
 nhánh theo thứ tự đi từ nút gốc qua các nút nhánh
 đến nút lá.
Ví dụ
• Hình dưới đây là ví dụ về cây mã cho bộ mã
 gồm các từ mã là 00, 01, 10, 1101, 11001
Các phương pháp biểu diễn mã(tt)
d/Phương pháp đa thức: 
• Phương pháp này dùng làm mô hình toán để 
 biểu diễn mã vòng
• Từ mã k bit m k-1m k-2m 2m 1m 0 (theo thứ tự
 từ trái qua phải là msb đến lsb) có thể được
 biểu diễn bằng đa thức sau:
• Ví dụ từ mã nhị phân 1101001 có thể biểu
 diễn bằng đa thức:
Mục đích của mã hóa
• Định dạng: để chuyển tin từ dạng gốc tự nhiên sang
 dạng chuẩn ví dụ sang dạng số PCM.
• Mã hóa đường: để đảm bảo dạng song của ký tự
 truyền đi phù hợp với các đặc điểm của kênh truyền.
• Mã hóa nguồn (source encoding): nhằm giảm số
 ký tự trung bình yêu cầu để truyền bản tin.
• Mật mã hóa (encryption): để mã hóa bản tin bằng
 một khóa mật mã nhằm tránh sự thâm nhập trái
 phép,đảm bảo độ an toàn cho thông tin.
• Mã hóa kênh truyền (channel encoding): cho phép
 bên thu có thể phát hiện,kể cả sửa được các lỗi trong
 bản tin thu để tăng độ tin cậy của thông tin.Do những
 đặc điểm riêng,phần mất mã hóa sẽ không được đề
 cập trong môn học này.
Điều mã xung (Pulse code modulation- PCM)
 • Mã hóa: là một phương pháp biến đổi tín
 hiệu tương tự sang tín hiệu số trong đó thông
 tin đầu vào biến đổi theo mã tín hiệu thành
 các tổ hợp bit nối tiếp ở đầu ra
a/ Lấy mẫu và giữ mẫu
• Rời rạc hóa tín hiệu theo thời gian, thay vì
 truyền tín hiệu f(t) liên tục theo thời gian thì ta
 chỉ phải truyền tín hiệu tại các thời điểm f(Ts),
 f(2Ts), f(3Ts)
tt
• Ts : là chu kỳ lấy mẫu, thỏa mãn định lý lấy
 mẫu
• Định lý lấy mẫu (Shannon) : Nếu một tín
 hiệu f(t) có phổ tần hữu hạn, fm là thành
 phần phổ có tần số cao nhất thì các mẫu
 được lấy với chu kỳ Ts 1/2fm.
• Chức năng của bộ lấy mẫu trong bộ phát
 PCM là lấy mẫu một cách chu kỳ
tt
• Có hai kiểu lấy
 mẫu tuỳ theo dạng
 của đỉnh độ rộng
 xung
• + Lấy mẫu tự
 nhiên
• + Lấy mẫu đỉnh
 phẳng.
b/ Lượng tử hóa
• Lượng tử hóa biên độ: là các ánh xạ các
 mẫu tín hiệu vào có biên độ liên tục trên một
 tập hữu hạn các mức biên độ
tt
• Đặc điểm:
 + Rời rạc hóa tín hiệu
 + Ép thang đo vào dải tín hiệu
 + Đo biên độ mẫu tín hiệu và làm tròn tín hiệu
 đó, thành một mức biên độ chuẩn đã được
 định nghĩa sẵn trong một dải biên độ tín hiệu
 cho trước.
tt
• : Bước lượng tử hóa 
tt
c/ Mã hóa
• Mã hoá là một quá trình so các giá trị rời rạc
 nhận được bởi quá trình lượng tử hoá với
 các xung mã.
• Thông thường các mã nhị phân được sử
 dụng cho việc mã hoá là các mã nhị phân tự
 nhiên, các mã Gray (các mã nhị phân phản
 xạ), và các mã nhị phân kép.
tt
 a/ Tín hiệu tương tự liên tục
 b/ Xung PAM sau lấy mẫu
 0111
 0110
 0101
 0100
 0011
 0010
 0001
 0000
 1000
 1001
 1010
 c/ Tín hiệu thu được sau khi lượng tử 
 hóa
tt
• Dãy xung PCM thu được: 0011 0100 0101 
 0110 0110 0111 0111 0111 ..
• Mã hóa tín hiệu hai mức bit 0= 0V, bit 1= +5V
Định dạng tín hiệu số
• 1/Các yếu tố cần xem xét khi chọn mã đường
• 2/Một số loại mã đường phổ biến
Định dạng tín hiệu số
• 1/Các yếu tố cần xem xét khi chọn mã
 đường
• 2/Một số loại mã đường phổ biến
1/Các yếu tố cần xem xét khi chọn 
mã đường:
• Thành phần một chiều DC : Nếu trong thành phần
 của mã đường có chứa thành phần DC thì thành
 phần này sẽ bị ngăn lại gây méo tín hiệu thu khi
 đường truyền kết nối AC như dùng tụ điện,biến áp.
• Băng thông : Băng thông của mã đường càng nhỏ
 sẽ càng tiết kiệm được băng thông
• Tỷ lệ lỗi bit BER : càng nhỏ càng tốt
• Tính trong suốt (transparancy) : phải bảo đảm tính
 trong suốt có thể truyền chính xác tới bên thu.
• Khả năng dễ dàng khôi phục đồng hồ
• Khả năng tự phát hiện lỗi : Căn cứ vào quy luật mã
 hóa để phát hiện lỗi.
• Đơn giản trong việc thực hiện mã hóa và giải mã.
Định dạng tín hiệu số
• 1/Các yếu tố cần xem xét khi chọn mã đường
• 2/Một số loại mã đường phổ biến
2/Một số loại mã đường phổ biến:
• a/Mã Unipolar
• b/Mã Polar
• c/Mã Bipolar
• d/Mã Manchester
• e/Mã HDB3
2/Một số loại mã đường phổ biến:
a/Mã Unipolar :
• Bit 1 biểu diễn bởi mức điện áp cap (+V),
• Bit 0 biểu diễn bởi mức 0 gọi là space.
b/Mã Polar :
• Bit 1 biểu diễn bởi mức cao (+V),
• Bit 0 biểu diễn bởi mức thấp (-V)
c/Mã Bipolar :
• Dùng 3 mức điện áp để biểu diễn hai loại bit nhị phân
• +Dòng bit 1 biểu diễn bởi sự thay đổi mức luân
 phiên (+V,-V)
• +Dòng bit 0 biểu diễn bởi mức 0
tt
d/Mã Manchester :
• Bit 1 biểu diễn bởi mức +V trong một nửa 
 đầu và –V trong một nửa sau.
• Bit 0 biểu diễn bởi mức –V trong một nửa đầu 
 và +V trong một nửa sau.
e/Mã HDB3 :
• Là một loại mã Bipolar nhưng khi trong dòng 
 bit PCM có xuất hiện 4 bit 0 liên tiếp thì thay 4 
 bit 0 đó bằng một cụm 4 bit đặc biêt.Cụm 4 
 bit đặc biệt đó là 000V hay B000V trong đó B 
 là bit tuân theo luật bipolar,V là bit trái luật 
 bipolar(+V,+V hoặc –V,-V).
Cực tính của xung Số bít 1 từ lần thay 
 trước đó thế cuối cùng
 Lẻ chẵn 
 - 000- +00+
 + 000+ -00-
tt
tt
Mã hóa nguồn
• Nguồn tin có 2 loại chính :
 +nguồn liên tục(continuos source) như nguồn
âm thanh,nguồn video
 +nguồn rời rạc (discrete source) như nguồn dữ
liệu từ máy tính
• Do đó có hai kỹ thuật mã hóa nguồn chính là
 +mã hóa nguồn liên tục
 +mã hóa nguồn rời rạc.
• Nguyên tắc của mã hóa nguồn rời rạc là mã hóa các
 ký tự có xác suất sinh ra lớn bằng các từ mã ngắn và
 mã hóa các ký tự có xác suất sinh ra bé bằng các từ
 mã dài.Loại mã này gọi là mã hóa thống kê(statistical
 encoding)
Lý thuyết tin
• Đo tin tức
• Entropy của nguồn
• Tốc độ lập tin tức
• Thông lượng kênh
Đo tin tức
• Lượng tin liên quan đến giá trị của tin: khả
 năng dự đoán của tin → một tin có khả năng
 dự đoán dự đoán càng nhiều thì càng chứa ít
 tin.
• Xác suất càng cao thì bản tin càng chứa ít
 các tin và ngược lại.
• P(bản tin)=1 : không mang tin
• P(bản tin)=0 : mang một lượng tin vô hạn
• Hàm loga(1/p(i)) được chọn để đánh giá định 
 lượng cho tin.Lượng tin của một tin i là :
• Đơn vị đo của lượng tin phụ thuộc vào cơ số 
 của loga
• Đơn vị của lượng tin là bit, nat hay harley khi 
 cơ số của loga lần lượt là 2,e,10
• Khi chọn cơ số 2 thì lượng tin của i là :
Entropy của nguồn tin
• Entropy H được định nghĩa là giá trị trung
 bình thống kê của lượng tin
• Xét một nguồn tin sinh ra M ký tự độc lập
 thống kê.Entropy của nguồn này là:
• Trong đó p(m) là xác suất chon ký tự thứ m
• Lý thuyết tin đã chứng minh giá trị lớn nhất
 của Entropy là:
• Đối với nguồn tin ASCII có M=128 thì
 entropy cực đại là :
• Thực tế điều này khó xảy ra
• Đối với nguồn tin nhị phân có M=2, nếu
 p(1)=p; p(0)=1-p thì entropy cực đại
 của nguồn là :
Mã hóa Huffman
• Huffman đưa ra thuật toán dựa trên xác suất 
 xuất hiện của các ký tự
• Không có tính sửa lỗi nhưng có tính giải mã 
 duy nhất và tức thời
• Mã hóa Huffman thực hiện mã hóa sử dụng ít 
 bit hơn cho các ký tự có xác suất xuất hiện 
 cao vì chúng được truyền đi thường xuyên 
 hơn và ngược lại, nhiều bit hơn cho các ký tự 
 có xác suất xuất hiện thấp nên có thể tăng 
 được hiệu suất.
Thuật toán Huffman gồm các bước 
sau : 
• Sắp xếp các ký tự theo xác suất giảm
 dần.Gán cho hai ký tự có xác suất xuất hiện
 thấp nhất với hai nhánh (0) và (1) của cây
 mã.Từ hai ký tự có xác suất thấp nhất giảm
 còn một ký tự với xác suất bằng tổng của
 hai xác suất.
• Lặp lại từ bước 1 cho đến khi chỉ còn lại
 một ký tự duy nhất với xác suất là 1.
• Duyệt cây mã để tìm ra từ mã tương ứng
 với từng ký tự của nguồn.
B1: Sắp xếp ký tự theo thứ tự xs 
giảm dần
Tin A B C D E F G H
Từ 000 001 010 011 100 101 110 111
mã
Xác 0,1 0,18 0,4 0,05 0,06 0,1 0,07 0,04
suất
B1: Sắp xếp ký tự theo thứ tự xs 
giảm dần
C 0,4
B 0,18
A 0,1
F 0,1
G 0,07
E 0,06
D 0,05
H 0,04
B2: Gán 2 ký tự có xs thấp nhất thành một ký
tự có xs bằng tổng của 2 xs đó rồi làm lại B1
C 0,4 0,4 0,4 0,4 0,4 0,4 0,6
 1
B 0,18 0,18 0,18 0,19 0,23 0,37 0,4
A 0,1 0,1 0,13 0,18 0,19 0,23
F 0,1 0,1 0,1 0,13 0,18
G 0,07 0,09 0,1 0,1
E 0,06 0,07 0,09
D 0,05 0,06
H 0,04
B3: Gán cho hai nhánh có xs thấp 
nhất giá trị 0 và 1
C 0,4 0,4 0,4 0,4 0,4 0,4 0,6
 11
B 0,18 0,18 0,18 0,19 0,23 0,37 10,4 0
A 0,1 0,1 0,13 0,18 0,19 10,23 0
F 0,1 0,1 0,1 0,13 0,18
 1 0
G 0,07 0,09 0,1 10,1 0
E 0,06 0,07 1 0,09 0
D 0,05 1 0,06 0
H 0,04 0
B4: Duyệt cây mã
C 0,4 0,4 0,4 0,4 0,4 0,4 0,6
 11
B 0,18 0,18 0,18 0,19 0,23 0,37 10,4 0
A 0,1 0,1 0,13 0,18 0,19 10,23 0
F 0,1 0,1 0,1 0,13 0,18
 1 0
G 0,07 0,09 0,1 10,1 0
E 0,06 0,07 1 0,09 0
D 0,05 10,06 0
H 0,04 0
 F(1111) G(1011)
 C(0) B(110) A(100)
Tin A B C D E F G H
Từ 100 110 0 11101 100 1010 1111 11100
mã
Xác 0,1 0,18 0,4 0,05 0,06 0,1 0,07 0,04
suấ
t
Cây mã
tt
• Nhìn vào cây mã ta thấy kết quả mã hóa 
 Huffman của nguồn tin trên như sau:
• Độ dài từ mã trung bình bây giờ là :
• Vậy độ lợi mã hóa là :
• Vậy hiệu suất của đường truyền đã tăng từ 
 85% lên 97,7%
Mã hóa nguồn Huffman
• “AN TOAN GIAO THONG”
Mã hóa nguồn Shanon_Fano
• B1 : Sắp xếp tất cả các tin của nguồn tin X 
 theo thứ tự xs xuất hiện tăng dần (giảm dần)
• B2 : Chia toàn bộ các tin của nguồn tin thành 
 2 nhóm có tổng xs xấp xỉ nhau
• B3 : Gán cho mỗi nhóm một chữ mã nhị phân 
 (0,1)
• B4 : Lặp lại các bước 2,3 cho đến khi mỗi 
 nhóm còn lại một ký hiệu
• B5 : Duyệt từ mã từ gốc đến ngọn