Đề tài 17: Các kỹ thuật phát hiện lỗi và sửa sai

Chia sẻ: dungnguyenkm

Phát hiện lỗi và sửa sai Mạng cần có khả năng truyền dữ liệu một cách chính xác. Một hệ thống không đảm bảo được tính năng này thì không sử dụng được. Trong quá trình truyền dữ liệu luôn bị tác động bởi nhiều yếu tố như nhiễu, vì vậy hệ thống cần có độ tin cậy tốt với cơ chế phát hiện và sửa lỗi. Việc phát hiện và sửa lỗi được thiết lập ở lớp kết nối dữ liệu hoặc lớp vận chuyển trong mô hình OSI....

Bạn đang xem 7 trang mẫu tài liệu này, vui lòng download file gốc để xem toàn bộ.

Nội dung Text: Đề tài 17: Các kỹ thuật phát hiện lỗi và sửa sai

Đề tài 17: các kỹ thuật phát hiện lỗi và sửa sai



Thành viên của nhóm 8:

1. Nguyễn Văn Dũng

2. Nguyễn Thúy Hà

3. Nguyễn Đức Tâm

4. Đỗ Thị Kim Thanh
Phát hiện lỗi và sửa sai
Mạng cần có khả năng truyền dữ liệu một cách chính xác. Một h ệ th ống
không đảm bảo được tính năng này thì không sử dụng được. Trong quá trình
truyền dữ liệu luôn bị tác động bởi nhiều yếu tố như nhiễu, vì vậy hệ thống
cần có độ tin cậy tốt với cơ chế phát hiện và sửa lỗi.

Việc phát hiện và sửa lỗi được thiết lập ở lớp kết nối dữ liệu hoặc lớp
vận chuyển trong mô hình OSI.

1. Tổng quan:

Khi dữ liệu được truyền đi giữa 2 DTE ( Data Terminal Equipment – thi ết b ị
đầu cuối xử lý số liệu) đây là thiết bị lưu trữ và xử lý thông tin. Trong h ệ th ống
truyền số liệu hiện đại thì DTE thường là máy tính hoặc máy fax hoặc là trạm
cuối (terminal). Như vậy tất cả các ứng dụng của người sử dụng (chương trình,
dữ liệu) đều nằm trong DTE. Chức năng của DTE thường lưu trữ các ph ần
mềm ứng dụng, đóng gói dữ liệu rồi gửi ra DCE ( thiết bị đầu cuối kênh d ữ
liệu – Data circuit terminal equipment) hoặc nhận gói dữ liệu từ DCE theo một
giao thức xác định DTE trao đổi với DCE thông qua m ột chu ẩn giao ti ếp nào đó.
Như vậy mạng truyền số liệu chính là để nối các DTE lại cho phép chúng ta
phân chia tài nguyên, trao đổi dữ liệu và lưu trữ thông tin dung chung đặc bi ệt
nếu các đường dây truyền dẫn ở trong môi truyền xuyên nhiễu nh ư mạng đi ện
thoại công cộng, thì những tín hiệu điện đại diện luồng bit rất d ễ b ị thay đ ổi do
ảnh hưởng của các thiết bị điện gần đó. Điều đó có nghĩa là tín hiệu đại diện
cho bit 1 bị máy thu dịch ra như bit nhị phân 0 và ngược lại.

Có hai phương pháp cho vấn đề này, đó là:

Kiểm soát lỗi hướng tới (FEC-Forward Error Control): trong mỗi ký tự

hay mỗi frame dữ liệu được truyền đi có chứa thông tin bổ sung c ần thi ết
để bên thu phát hiện lỗi và có thể dò tìm v ị trí của các bit l ỗi . Sau đó
chỉ cần đảo ngược các bit lỗi để nhận được dữ liệu đúng.

Kiểm soát lỗi quay lui (Backward Error Control) : Trong mỗi ký t ự hay

mỗi frame dữ liệu được truyền đi chỉ chứa thông tin cần thiết để bên thu
chỉ có thể phát hiện ra lỗi. Một bộ điều khiển sẽ yêu cầu bên phát phát
lại bản dữ liệu đúng.
Trong thực tế, số lượng bit thêm vào để đạt được độ tin cần thiết trong
điều khiển hướng tới sẽ gia tăng nhanh chóng khi số lượng bit thông tin tăng lên.
Do đó, phương pháp điều khiển lỗi quay lui được sử dụng nhiều h ơn trong các
dạng truyền số liệu và các hệ thống mạng.

2. Các khái niệm về lỗi:

Về bản chất, lỗi truyền số liệu là lỗi bit. Nếu tín hiệu mang dữ liệu nhị phân
được mã hóa, những thay đổi như thế có thể làm thay đổi ý nghĩa của dữ liệu.

Nguyên nhân gây ra lỗi:

− Các quá trình vật lý sinh ra: đó là các lỗi xảy ra trong quá trình truy ền số
liệu trên đường truyền vật lý. Bất cứ khi nào một tín hiệu điện từ di
chuyển từ một điểm này tới điểm khác, nó dễ bị nhiễu không đoán tr ước
từ sức nóng, từ tính và các dạng của điện. Sự nhiễu này có thể làm thay
đổi hình dạng và thời gian của tín hiệu.

− Các thiết bị truyền thông gây ra: là các lỗi xẩy ra do chính các thi ết b ị
tham gia truyền số liệu gây ra.

Để xác định xác suất lỗi bit sử dụng Pb

Xác định tỉ suất lỗi bit – BER ( Bit Error Rate)

BER £ 10-9 – đường truyền được xem là tốt

BER £ 10-4 – đường truyền chấp nhận được

Ngoài ra còn một số đơn vị đo khác, ít được sử dụng hơn:

FER (Frame Error Rate)

PER (Packet Error Rate)

Để xác định xác suất lỗi gói số liệu sử dụng công thức:

Pf = 1 – (1 – Pb) N với N – độ dài gói số liệu, đo bằng bit

Pf ≈ N.Pb, nếu N.Pb Phát hiện các lỗi đơn và lỗi ghép, không phát hiện tất cả các lỗi đặc
biệt lỗi tạo ra hình chữ nhật như trường hợp (4)

2. Kiểm tra tổng khối BSC ( Block Sum Check ):
Block Sum Check (BSC): kết hợp parity hàng và cột
• Phát hiện được lỗi sai một số lẻ bit.
• Dò được các lỗi sai một số chẵn bit, ngoại trừ những lỗi xảy ra đồng
thời trên cả hàng và cột.
• Chỉ sửa được sai một bit đơn.
- Khi các khối ký tự đang được truyền, xác suất một ký tự chứa lỗi bit gia
tăng.
- Xác suất một khối ký tự bị lỗi bit được gọi là tỉ lệ lỗi bit BER.
- Phương pháp này sử dụng một tập parity bit được tính từ toàn bộ khối
ký tự trong khung.
- Mỗi ký tự trong khung được phân phối một parity bit ( parity hàng ).
Ngoài ra một bit mở rộng được tính cho mỗi vị trí bit ( parity c ột ) trong toàn b ộ
khung. Tập các parity bit cho mỗi cột được gọi là ký tự kiểm tra khối BCC
( Block Check Character )
Ví dụ:

Data Start Data Parity(even stop
)
B1 B2 B3 B4 B5 B6 B7
H 1 0 0 0 0 0 0 1 1 0
E 1 1 0 0 0 0 0 1 0 0
L 1 0 1 0 0 0 0 1 0 0
L 1 0 1 0 0 0 0 1 0 0
O 1 1 1 0 0 0 0 1 1 0
BCC(odd) 1 1 0 1 1 1 1 0 1 0




3. Kiểm tra CRC ( cyclic redundancy check )
CRC (cyclic redundancy check) là một loại hàm băm, được dùng để sinh ra
giá trị kiểm thử, của một chuỗi bit có chiều dài ngắn và c ố đ ịnh, c ủa các gói tin
vận chuyển qua mạng hay một khối nhỏ của tệp dữ liệu. Giá trị kiểm th ử được
dùng để dò lỗi khi dữ liệu được truyền hay lưu vào thiết bị l ưu trữ. Giá tr ị c ủa
CRC sẽ được tính toán và đính kèm vào dữ liệu trước khi dữ liệu được truyền
đi hay lưu trữ. Khi dữ liệu được sử dụng, nó s ẽ được ki ểm th ử bằng cách sinh
ra mã CRC và so khớp với mã CRC trong dữ liệu.
CRC là một loại mã phát hiện lỗi. Cách tính toán của nó giống như phép
toán chia số dài trong đó thương số được loại bỏ và số dư là kết quả, điểm khác
biệt ở đây là sử dụng cách tính không nhớ (carry-less arithmetic) của một trường
hữu hạn. Độ dài của số dư luôn nhỏ hơn hoặc bằng độ dài của số chia, do đó số
chia sẽ quyết định độ dài có thể của kết quả trả về. Định nghĩa đối với t ừng
loại CRC đặc thù quyết định số chia nào được sử dụng, cũng như nhiều ràng
buộc khác.
CRC dựa chủ yếu vào phần bit bổ sung, kỹ thuật CRC dựa trên phép chia
nhị phân. Trong CRC, thay vì thêm các bit để cùng đạt được m ột tính ch ẵn l ẻ
theo mong đợi, một chuỗi các bit dư thừa được gọi là CRC hay s ố d ư CRC,
được ghép vào cuối đơn vị dữ liệu do đó đơn vị dữ liệu kết qu ả có th ể chia h ết
cho số nhị phân thứ hai được xác định trước. Tại đích của nó, đơn vị dữ liệu
đến được chia bởi cùng số đó. Nếu tại bƣớc này, phép chia có s ố dư bằng 0,
đơn vị dữ liệu đƣợc coi là còn nguyên vẹn và do đó được chấp nhận. Nếu số
dư khác không có nghĩa là đơn vị dữ liệu đó đã bị h ư hại trong quá trình truy ền
và do đó bị loại bỏ. Các bit dư thừa được sử dụng bởi CRC lấy được từ phép
chia đơn vị dữ liệu theo số chia đã xác định trước; ph ần dư của phép chia s ẽ là
CRC. Để có thể phân loại quá trình này, bắt đầu một cách tổng quan và sau đó
đi sâu vào chi tiết hơn.




Bước thứ nhất, một chuỗi n bit được ghép vào đơn vị dữ liệu. Số n là m ột
số nhỏ hơn số các bit trong số chia xác định tước có chiều dài n+1 bit
Bước thứ hai, đơn vị dữ liệu mới kéo dài chia cho số chia sử dụng một
quá trình gọi là chia nhị phân. Phần dư của phép chia là CRC.
Bước thứ 3, CRC của n bit dẫn ra từ bước 2 thay th ế các bit 0 đ ược ghép
vào cuối đơn vị dữ liệu. Chú ý là CRC có thể bao gồm tất cả các bit 0.
Đầu tiên, dữ liệu được nhận, theo đó là CRC. Bên nh ận coi toàn b ộ chu ỗi
dữ liệu đó là một đơn vị và chia nó cho cùng số chia mà đã đ ược s ử d ụng tr ước
đó để tìm ra số dư CRC.
Nếu chuỗi đến mà không có lỗi, bộ kiểm tra CRC sẽ cho kết quả đầu ra là
số dư bằng 0 và đơn vị dữ liệu được qua. Nếu chuỗi đó bị thay đổi trong quá
trình truyền, kết quả phép chia là một số khác 0, do đó đ ơn v ị dữ li ệu không
được qua.
Bộ sinh CRC- CRC generator
Một bộ sinh CRC sử dụng phép chia modulor 2. Trong bước đầu tiên, số
chia 4 bit được trừ đi từ 4 bit đầu tiên của số bị chia. Mỗi bit c ủa s ố chia đ ược
trừ đi tương ứng với bit của số bị chia mà không cần nh ớ sang bit ti ếp theo cao
hơn. Trong ví dụ của , số chia 1101 được trừ từ 4 bit của số bị chia, 1001 cho
kết quả là 100 (số 0 ở đầu của số dư được bỏ đi).
Các bít chưa được sử dụng tiếp theo từ số bị chia sau đó đ ược chuy ển
xuống dưới để tạo ra số các bit trong số dư bằng với số các bit ở số chia. Do
đó, theo bước tiếp theo là 1000-1101=101…
Trong quá trình này, số chia luôn bắt đầu với bit 1; số chia được trừ t ừ
một phần của số bị chia/số dư trước bằng nhau về độ dài; số chia chỉ có thể
được trừ đi từ số bị chia/số dư mà bit trái nhất của nó bằng 1. Tại bất kỳ th ời
điểm nào bit trái nhất này của bị chia/số dư là 0, một chuỗi các số 0, có cùng
chiều dài nhƣ số chia, thay thế số chia trong bƣớc đó của toàn bộ quá trình. Ví
dụ, nếu số chia có độ dài 4 bit, nó đƣợc thay th ế b ằng 4 s ố 0. (Chú ý r ằng đang
xử lý với các mẫu bit, chứ không phải với các giá trị định lƣợng; 0000 không
giống 0.). Hạn chế này có nghĩa rằng tại bất kỳ bước nào bên trái nhất của phép
trừ sẽ là 0-0 hoặc 1-1, cả hai đều bằng 0. Vì v ậy, sau phép tr ừ, bit bên trái nh ất
của số dư sẽ luôn dẫn tới 0, do đó bit này được loại bỏ và bit tiếp theo ch ưa
được sử dụng của số bị chia được đẩy xuống để đưa ra số dư. C ần chú ý là ch ỉ
có bit đầu tiên của số dư được loại bỏ- nếu bit tiếp theo cũng là 0, nó v ẫn đ ược
giữ lại, và số bị chia/số dư cho bước tiếp theo sẽ bắt đầu với 0. Quá trình này
lắp lại cho đến khi toàn bộ số bị chia được sử dụng.
Bộ kiểm tra CRC- CRC Checker
Bộ kiểm tra CRC thực hiện chức năng một cách chính xác như bộ sinh CRC.
Sau khi nhận được dữ liệu được ghép với CRC, nó t ương t ự th ực hi ện phép
chia modulor-2. Nếu số dư tất cả bằng 0, các bit CRC được bỏ đi và dữ li ệu
được chấp nhận, nếu không dòng các bit nhận được bị bỏ đi và dữ liệu được
gửi lại. giải sử rằng không có lỗi xảy ra. Số chia do đó t ất c ả bằng 0 và d ữ li ệu
được chấp nhận.
Các đa thức CRC
Bộ sinh CRC (số chia) thường được biểu diễn không chỉ ở dưới dạng
chuỗi các bit 0 và 1 mà còn là một đa thức đại số. Khuôn dạng c ủa đa th ức là
hữu dụng vì hai lý do: Nó ngắn, và có thể được sử dụng để chứng minh khái
niệm toán học



Mối quan hệ của một đa thức đối với biểu diễn nhị phân
Một đa thức sẽ được lựa chọn sao cho thỏa mãn:
-Nó sẽ không được chia hết bởi x
- Nó có thể được chia hết bởi (x+1)
Điều kiện đầu tiên đảm bảo rằng tất cả các lỗi bit chùm bit có độ dài b ằng
với độ dài của đa thức được dò thấy. Điều kiện thứ 2 đảm bảo rằng mọi l ỗi bit
hàng loạt ảnh hưởng một số lẻ các bit được dò thấy.
Các đa thức sinh chuẩn:
CRC12: x12+x11+x3+x+1
CRC16: x16+x15+x2+1
CRC-ITU-T: x16+x12+x5+1
CRC32: x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1
Hiệu quả của kỹ thuật của CRC
CRC là phương pháp dò tìm lỗi rất hiệu quả. Nếu số chia được ch ọn theo
nguyên tắc đã nếu trước đó thì:
- CRC có thể dò tất cả các lỗi bit chùm bit mà ảnh hưởng một số lẻ các bit
- CRC có thể dò tất cả các lỗi bit chùm có chiều dài nh ỏ hơn hoặc b ằng
bậc của đa thức.
1. - CRC có thể dò tìm với khả năng tìm thấy lỗi bit chùm bit có chiều dài lớn
hơn bậc của đa thức.
Đề thi vào lớp 10 môn Toán |  Đáp án đề thi tốt nghiệp |  Đề thi Đại học |  Đề thi thử đại học môn Hóa |  Mẫu đơn xin việc |  Bài tiểu luận mẫu |  Ôn thi cao học 2014 |  Nghiên cứu khoa học |  Lập kế hoạch kinh doanh |  Bảng cân đối kế toán |  Đề thi chứng chỉ Tin học |  Tư tưởng Hồ Chí Minh |  Đề thi chứng chỉ Tiếng anh
Theo dõi chúng tôi
Đồng bộ tài khoản