mã phát hiện và sữa lỗi - Pdf 14

Đồ án môn học Truyền dẫn vô tuyến
LỜI MỞ ĐẦU
Cùng với sự phát triển của Khoa học – Công Nghệ của thế giới, nước ta đã và
đang áp dụng ngày càng nhều các thành tựu của Khoa học – Công Nghệ vào trong các
lĩnh vực kinh tế, khoa học, xã hội và đời sống…nói chung và trong ngành viễn thông
nói riêng.
Trong cuộc sống hàng ngày thông tin liên lạc đóng một vai trò rất quan trọng
và không thể thiếu. Nó quyết định nhiều mặt hoạt động của xã hội, giúp con người
nắm bắt nhanh chóng các thông tin, các giá trị văn hoá, kinh tế, khoa học kỹ thuật rất
đa dạng và phong phú.Với nhu cầu cả về số lượng và chất lượng của khách hàng sử
dụng các dịch vụ viễn thông ngày càng cao, đòi hỏi phải có những phương tiện thông
tin hiện đại nhằm đáp ứng các nhu cầu đa dạng của khách hàng “mọi lúc, mọi nơi” mà
họ cần.Thông tin di động ngày nay đã trở thành một dịch vụ kinh doanh không thể
thiếu được của tất cả các nhà khai thác viễn thông trên thế giới. Đối với các khách
hàng viễn thông, nhất là các nhà doanh nghiệp thì thông tin di động trở thành phương
tiện liên lạc quen thuộc và không thể thiếu.
Với sự đa dạng về các loại hình kết nối và yêu cầu của mạng thông tin rộng khắp
thì việc thiết kế, thi công và lắp đặt các mạng truyền dẫn đòi hỏi phải mềm dẻo và phù
hợp với yêu cầu của khách hàng. Chính vì thế, việc phát triển mạng truyền dẫn vô
tuyến là đương nhiên và rất cần thiết. Với Truyền Dẫn Vô Tuyến, chúng ta có thể khắc
phục được sự hạn chế về mặt địa lý, đồng thời thúc đẩy sự phát triển của các dịch vụ
thông tin vô tuyến, nhất là trong thông tin di động. Do vậy, việc lựa chọn sản
phẩm phụ thuộc rất nhiều vào nhà cung cấp sản phẩm. Đồng thời, viêc đào tạo đội ngũ
cán bộ kỹ thuật, công nhân viên phụ vụ cho việc vận hành, khai thác và bảo trì cũng là
vấn đề cấp thiết.
SVTH: Nguyễn Mùi 1
Đồ án môn học Truyền dẫn vô tuyến
MỤC LỤC
LỜI MỞ ĐẦU 1
MỤC LỤC 2
CHƯƠNG 1: GIỚI THIỆU CHUNG 3

đẻ của máy điện báo Samuel Finley Breese Morse sau bao ngày đêm nghiên cứu vất
vả, ông đã sáng chế chiếc máy điện báo đầu tiên. Bức điện báo đầu tiên dùng mã
Morse được truyền đi trên trái đất từ Nhà Quốc Hội Mỹ tới Baltimore cách đó 64 km
đã đánh dấu kỷ nguyên mới của viễn thông. Trong bức thông điệp đầu tiên này Morse
đã viết "Thượng Đế sáng tạo nên những kỳ tích". Nói đến lịch sử của Viễn thông,
không thể không nhắc đến Alexader Graham Bell, ông là người đầu tiên sáng chế ra
điện thoại. Để tưởng nhớ ông, ngày 7 tháng 8 năm 1922 mọi máy điện thoại trên nước
Mỹ đều ngừng hoạt động để tưởng nhớ và bày tỏ lòng biết ơn nhà khoa học xuất sắc
A.G Bell (1847 - 1922). Trên quy mô xã hội, nếu điện tín (1884), điện thoại (1876),
radio (1895) và vô tuyến truyền hình (1925) đã làm thay đổi cách giao tiếp trong quan
hệ con người thì sự xuất hiện của vệ tinh viễn thông (1960) sợi quang học (1977),
công nghệ không dây đã làm nên một hệ thần kinh thông minh nhạy bén trên trái đất.
Có thể nói lĩnh vực viễn thông đã làm thay đổi bộ mặt, tính cách của trái đất, đã hiện
thực hóa khả năng liên kết của mỗi người của mỗi quốc gia, gắn kết mọi người với
nhau nhờ một mạng lưới viễn thông vô hình và hữu hình trên khắp trái đất và vũ
trụ. Sự hội tụ trong lĩnh vực viễn thông Chữ xiên Cùng với sự phát triển của xã hội,
nhu cầu sử dụng và truyền dữ liệu của con người cũng tăng lên theo hàm số mũ.
Ngành VT đóng góp vai trò lớn lao trong việc vận chuyển đưa tri thức của loài người
đến mỗi người, thúc đẩy quá trình sáng tạo đưa thông tin khắp nơi về các ngành lĩnh
vực khoa học, các thông tin giải trí cũng như thời sự khác. Viễn thông đem lại sự hội
tụ, hay sự thống nhất về các loại hình dịch vụ truyền dữ liệu dịch vụ như thoại, video
(truyền hình quảng bá và truyền hình theo yêu cầu), và dữ liệu Internet băng rộng thúc
đẩy ngành công nghệ thông tin phát triển lên một mức cao hơn với đa dạng các loại
hình dịch vụ và chi phí rẻ hơn. Mạng viễn thông giúp người sử dụng có thể gọi điện
SVTH: Nguyễn Mùi 3
Đồ án môn học Truyền dẫn vô tuyến
thoại qua mạng Internet, có thể xem hình ảnh của bạn bè trên khắp thế giới, có thể chia
sẻ nguồn dữ liệu, có thể thực hiện những giao dịch mua bán tới mọi nơi trên thế giới
một cách đơn giản. Viễn thông ngày càng tạo nên một thế giới gần hơn hội tụ cho tất
cả mọi người

thành bit 0 hay ngược lại.
Ta định nghĩa tỷ lệ lỗi bởi tỷ số sau:
τ = Số bít bị lỗi / Tổng số bít được truyền
SVTH: Nguyễn Mùi 5
Đồ án môn học Truyền dẫn vô tuyến
Tỷ lệ lỗi này có giá trị từ 10
-5
đến 10
-8
. Tùy thuộc vào từng loại ứng dụng, một lỗi
có mức độ nghiêm trọng khác nhau, chính vì thế cần có các cơ chế cho phép phát hiện
lỗi cũng như sửa lỗi.
Các thống kê cho thấy rằng 88% các lỗi xẩy ra do sai lệch một bit và 10% các lỗi
xảy ra do sự sai lệch 2 bit kề nhau. Chính vì thế ta ưu tiên cho vấn đề phát hiện các lỗi
trên một bit và sửa đổi chúng một cách tự động.
Với ý tưởng như thế, ta sử dụng các mã phát hiện lỗi: bên cạnh các thông tin hữu
ích cần truyền đi, ta thêm vào các thông tin điều khiển. Bên nhận thực hiện việc giải
mã các thông tin điều khiển này để phân tích xem thông tin nhận được là chính xác
hay có lỗi. Hình 2.1: Mô hình xử lý lỗi trong truyền dữ liệu
2.3 PHÂN LOẠI
Thông tin điều khiển được đưa vào có thể theo 2 loại:
• Loại thứ nhất gọi là bộ mã sửa lỗi (Error-correcting codes).
• Loại thứ hai gọi là bộ mã phát hiện lỗi (Error-detecting codes).
Bộ mã sửa lỗi cho phép bên nhận có thể tính toán và suy ra được các thông tin bị
lỗi (sửa dữ liệu bị lỗi). Trong khi bộ mã phát hiện lỗi chỉ cho phép bên nhận phát hiện
ra dữ liệu có lỗi hay không. Nếu có lỗi bên nhận sẽ yêu cầu bên gởi gởi lại thông tin.
Với tốc độ của đường truyền ngày càng cao, người ta thấy rằng việc gởi lại một khung

Các bit của mã Hamming chèn vào vị trí 2n và dùng cho kiểm tra chẵn lẻ. Các
bit khác là bit thông tin (dữ liệu).
Dưới đây là một ví dụ để thấy cách xác định mã Hamming:
Giả sử chuỗi dữ liệu cần truyền gồm 4 bit như sau :
1 0 1 0
Với m = 4, ta chọn n = 3, bất đẳng thức trên được thỏa
Gọi các bit của mã Hamming là H1 H2 và H4 (1, 2, 4 là các vị trí mà ta sẽ đặt 3
bit của mã Hamming vào dòng dữ liệu). Gọi các bit dòng dữ liệu là X3, X5, X6, X7.
Tổ hợp các bit dữ liệu và bit mã, ta đươc
1 2 3 4 5 6 7
H1 H2 X3 H4 X5 X6 X7
SVTH: Nguyễn Mùi 7
Đồ án môn học Truyền dẫn vô tuyến
Giả sử ta chọn Parity chẵn, các bit mã sẽ được xác định như sau:
H1 ⊕ X3 ⊕ X5 ⊕ X7 = 0
H1 = X3 ⊕ X5 ⊕ X7 = 1 ⊕ (0 ⊕ 0) = 1 ⊕ 0 = 1
Tương tự:
H2 = X3 ⊕ X6 ⊕ X7 = 1 ⊕ (1 ⊕ 0) = 1 ⊕ 1 = 0
H4 = X5 ⊕ X6 ⊕ X7 = 0 ⊕ (1 ⊕ 0) = 0 ⊕ 1 = 1
Bản tin bao gồm bit mã trở thành: 1 0 1 1 0 1 0
Ở máy thu để kiểm tra người ta thực hiện các phép toán:
C1 = H1 ⊕ X3 ⊕ X5 ⊕ X7
C2 = H2 ⊕ X3 ⊕ X6 ⊕ X7
C4 = H4 ⊕ X5 ⊕ X6 ⊕ X7
Nếu C1 = C2 = C4 = 0, không có lỗi xảy ra.
Nếu C1 = 1, C2 = C4 = 0, một trong các bit ở vị trí 1, 3, 5, 7 bị lỗi.
Nhưng C2 = C4 = 0 có nghĩa là các bit ở vị trí 2, 3, 6, 7 và 4, 5, 6, 7 đã đúng.
Vậy bit sai phải ở vị trí 1. Lý luận tương tự ta có các trường hợp khác.
Thí dụ nếu C1 = C2 = C4 = 1 thì bit lỗi là bit ở vị trí 7
Thí dụ bản tin nhận được là 1 0 1 1 1 1 0

3.2.3. Dùng kiểm tra chẵn lẻ để dò ra một chuỗi bit sai
Đôi khi nhiễu làm sai cả một chuỗi dữ liệu (ta gọi là burst errors), để dò ra được
chuỗi bit sai này, người ta làm theo cách lưu và truyền dữ liệu của máy tính (lưu từng
bit của một byte trong các chip riêng để truyền trên các đường khác nhau và nơi nhận
sẽ tái hợp) để thực hiện việc kiểm tra. Chuỗi dữ liệu sẽ được chia ra thành các khung
(frames), thực hiện kiểm tra cho từng khung, thay vì phát mỗi lần một khung, người ta
phát các tổ hợp bit cùng vị trí của các khung, nhiễu có thể làm hỏng một trong các tổ
hợp này và chuỗi bit sai này có thể được nhận ra ở máy thu.
Ví dụ dưới đây minh họa cho việc kiểm tra phát hiện chuỗi dữ liệu sai:
Máy thu dò ra các khung có lỗi (các bit parity có dấu *) nhưng không xác định
được cột nào bị sai do đó phải yêu cầu máy phát phát lại tất cả các cột
SVTH: Nguyễn Mùi 9
Đồ án môn học Truyền dẫn vô tuyến
3.2.4. Kiểm tra khối
Một cải tiến của kiểm tra chẵn lẻ là kiểm tra khối (Block Check Character, BCC).
Bản tin được viết thành khối và việc kiểm tra chẵn lẻ được thực hiện theo cả 2 chiều
dọc (Vertical Redundancy Check, VRC) và ngang ( Longitudinal Redundancy Check,
LRC)
Gọi các bit của mỗi ký tự là bij (i=1, , n là thứ tự các bit trong ký tự ; j=1, , m
là thứ tự của ký tự)
Rj là bit parity của ký tự thứ j, giả sử chọn parity chẵn, ta có :
Rj = b1j + b2j + + bnj
Ci là bít parity của tất cả bít thứ i
Ci = bi1 + bi2 + + bim +
Tập hợp các bit Ri (j = 1, ,m) dùng kiểm tra chiều dọc và tập hợp các bit Ci
(i = 1, ,n) dùng kiểm tra chiều ngang.
Phương pháp kiểm tra khối cho phép phát hiện và sửa một lỗi vì xác định được vị
trí của lỗi đó, chính là giao điểm của hàng và cột có bit sai. Máy thu có khả năng phát
hiện hai lỗi sai trên cùng một hàng hoặc cột nhưng không xác định được vị trí bit lỗi.
Ví dụ hai bit 1 và 3 của ký tự thứ nhất cùng sai thì bit kiểm tra VRC không phát hiện

1 và 3 của ký tự 5 cũng bị lỗi, phương pháp này sẽ không phát hiện được điểm sai.
3.4. MÃ KIỂM TRA PHẦN DƯ
Để cải thiện hơn nửa việc kiểm tra lỗi người ta dùng phương pháp kiểm tra dư
thừa theo chu kỳ (Cyclic Redundancy Check, CRC)
Nguyên tắc tạo mã CRC : Xét khung dữ liệu gồm k bit và nếu ta dùng n bit cho
khung kiểm tra FCS (Frame check sequence) thì khung thông tin kể cả dữ liệu kiểm tra
gồm (k+n) bit sao cho (k+n) bit này chia đúng cho một số P có (n+1) bit chọn trước
(dùng phép chia Modulo-2). Ở máy thu khi nhận được khung dữ liệu, lại mang chia
cho số P này và nếu phép chia đúng thì khung dữ liệu không chứa lỗi * Nhắc lại một
số tính chất của phép toán Mod-2 :
Phép cộng Mod-2 là phép cộng nhị phân không nhớ, dưới đây là thí dụ về phép
cộng và phép nhân
Phép cộng Mod-2 được thực hiện bởi cổng EX-OR
Phép trừ Mod-2 giống như phép cộng
Nhân Mod-2 một số với 2n
Tương ứng với dời số đó n bit về bên trái và thêm n bit 0 vào bên phải số đó, thí
dụ 11001* 23 = 11001000
Phép chia Mod-2 được thực hiện giống như phép chia thường nhưng nhớ là phép
trừ trong khi chia được thực hiện như phép cộng.
3.4.1. Xác định mã CRC dùng thuật toán Mod-2
Gọi T = (k+n) bit là khung thông tin được phát , với n < k
M = k bit dữ liệu, k bit đầu tiên của T
F = n bit của khung FCS, n bit cuối của T
P = (n+1) bit, số chia trong phép toán
Số T được tạo ra bằng cách dời số M sang trái n bit rồi cộng với số F :
T = 2n M + F
SVTH: Nguyễn Mùi 12
Đồ án môn học Truyền dẫn vô tuyến
Chia số 2nM cho P ta được : 2n
Vì phép chia thực hiện với số nhị phân nên số dư luôn luôn ít hơn số chia 1 bit.

SVTH: Nguyễn Mùi 13
Đồ án môn học Truyền dẫn vô tuyến

0001110 ← R
Ta có R = 01110, cộng với 25M, sẽ cho số T phát đi là :
T = 101000110100000 + 01110 = 101000110101110
Nếu bản tin không có lỗi T phải chia đúng cho P.
Thực hiện phép chia T/P ta thấy số dư = 0
Tóm lại, để có một khung FCS n bit , người ta phải dùng một số P có n+1 bit để
tạo số R có n bit dùng cho khung FCS. P được gọi là đa thức sinh (generator
polynomial), dạng của nó do các giao thức qui định, tổng quát P phải có bit đầu và bit
cuối là bit 1.
3.4.2. Dùng phép biểu diễn đa thức
Để thấy quá trình hình thành mã CRC, ta có thể dùng phép biểu diễn một số nhị
phân dưới dạng một đa thức của biến x với hệ số là các số nhị phân và bậc của x là giá
trị chỉ vị trí của số nhị phân đó.
Ví dụ số nhị phân 110101 có thể biểu diển bởi
1.x5 + 1.x4 + 0.x3 + 1. x2 + 0.x1 + 1.x0 = x5 + x4 + x2 + 1
Chú ý mã số n bit cho bậc cao nhất của đa thức là n-1
Quá trình hình thành mã CRC thực hiện như sau :
Gọi M là đa thức biểu diễn thông tin cần truyền
P là đa thức sinh, bậc n (chứa n+1 bit)
Thực hiện phép chia xn
Khung thông tin truyền đặc trưng bởi
T(x) = xn
SVTH: Nguyễn Mùi 14
Đồ án môn học Truyền dẫn vô tuyến
M(x) + R(x)
Lưu ý là nhân M(x) với xn tương đương với việc dời M(x) sang trái n bit
Ở máy thu thực hiện phép chia T(x) cho P(x) số dư phải bằng không


Nhờ tải bản gốc

Tài liệu, ebook tham khảo khác

Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status