Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC
Phần I : Lý thuyết
1. Định nghĩa.
CRC ( Cyclic Redundancy Check ) còn gọi là phương pháp mã đa thức hoặc mã vòng.
Phương pháp này được sử dụng trong hầu hết các hệ thống truyền thông. Tuy cái tên
của nó không biểu hiện nhiều, nhưng ý tưởng ở đây là thông tin kiểm lỗi ( ở đây được
gọi là checksum ) phải được tính bằng một thuật toán thích hợp, trong đó giá trị mỗi
bit của thông tin nguồn đều được tham ra nhiều lần vào quá trình tính toán.
Để tính toán thông tin kiểm lỗi đó, người ta dùng một “ đa thức sinh ” G ( generator
polynomial ) có một dạng đặc biệt. Chính vì thế phương pháp này còn được gọi là
phương pháp dùng đa thức. G được quy ước dưới dạng nhị phân, tức các hệ số của nó
chỉ có giá trị 1 hoặc 0 tương ứng với các chữ số trong một dãy bit.
Ví dụ :
Dạng đa thức : G = x
7
+ x
6
+ x
5
+ x
2
+ 1
Dạng nhị phân : G = 11100101
2. Phương pháp
- Coi bản tin phát đi như một đa thức
- Máy phát chia đa thức bản tin cho một đa thức sinh cho trước
- Phần dư được gắn vào cuối bản tin
- Dữ liệu(bản tin với phần dư) được phát đến máy thu
- Máy thu chia dữ liệu đã nhận được cho cùng một đa thức sinh
- Nếu số dư bằng 0 thì không có lỗi xảy ra trong đường truyền
- Nếu số dư khác 0 thì đã có lỗi xảy ra trong đường truyền

đương bậc của đa thức được phát hiện.
- Không chia hết cho x+1. Điều này đảm bảo tất cả các lỗi đa bit có số lẻ các
bit bị lỗi được phát hiện
5. Đánh giá
- CRC có thể phát hiện được tất cả các lỗi có một số lẻ bit bị lỗi
- CRC có thể phát hiện được tất cả các lỗi đa bit có độ dài nhỏ hơn hoặc bằng
bậc của đa thức
- CRC có thể phát hiện được các lỗi đa bit có độ dài lớn hơn bậc của đa thức
với xác xuất cao
- Một điều đáng chú ý là tuy phương pháp CRC có vẻ như phức tạp, nhưng
thực sự việc thể hiện nó lại rất đơn giản. Phép chia đa thức nhị phân được thực
hiện thuần túy bởi các phép trừ không có nhớ - hay chính là các phép logic XOR.
Bên cạnh đó chỉ cần các phép sao chép và so sánh bit thông thường.
Loại lỗi Chất lượng phát hiện lỗi
Các lỗi bit đơn 100%
Các lỗi bit kép 100% khi đa thức sinh có ít nhất 3 bit 1
Một số lẻ các bit bị lỗi 100% khi đa thức sinh không chia hết
cho x+1
Một cụm lỗi có chiều dài <
n+1
100%
Một cụm lỗi có chiều dài =
n+1
Xác suất bằng 1-(1/2)
n-1
Một cụm lỗi có chiều dài >
n+1
Xác xuất bằng 1-(1/2)
n-1
Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 3

Nhóm có 3 sinh viên cùng thực hiện và chương trình gồm có các phần công việc như
sau :
• Định nghĩa quy tắc của phép trừ không nhớ, chuyển dãy nhị phân của đa thức
sinh về đa thức tương ứng (Sinh viên thực hiện Nguyễn Thị Huệ)
• Xây dựng phép chia đa thức nhị phân không nhớ, thực hiện mô phỏng phép
chia đa thức không nhớ và đưa ra kết quả yêu cầu kiểm tra hay tính ra dãy bit cần
truyền (Sinh viên thực hiện Cao Thị Phương Anh)
• Kiểm tra điều kiện đa thức sinh, thiết kế Form chương trình (Sinh viên thực
hiện Nguyễn Quý Sơn)
a. Phần thực hiện của Sinh viên Nguyễn Thị Huệ.
- Thuật toán thực hiện trên phép chia không nhớ với quy tắc đơn giản
1 – 1 = 0
0 – 0 = 0
1 – 0 = 1
0 – 1 = 1
- Nên em đã viết một phương thức pheptinh(char a, char b) với giá trị trả về
là 1 kí tự kiểu char là kết quả của phép trừ với các quy tắc đơn giản ở trên.
- Tiếp theo là việc thực hiện chuyển dãy nhị phân của đa thức sinh về đa thức
thức tương ứng. Em đã viết một phương thức đó là phương thức
sinhbieuthuc(string s) phương thức này trả về một chuỗi biểu diễn đa thức
tương ứng với dãy nhị phân của đa thức sinh.
Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 5
Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC
- Trong phương thức này thì ta nhậ thấy chuỗi nhị phân của đa thức sinh cứ
vị trí nào là kí tự 1 thì khi chuyển sang đa thức tương ứng là 1*x
t
với t là số
ngũ tại vị trí i thuộc dãy và t được tính bằng cách lấy chiều dài của chuỗi trừ đi
( vị trí i + 1), ta sẽ dùng 1 vòng lặp for cho i chạy từ đầu đến hết chuỗi. Nếu tại
vị trí i nào đó có giá trị của kí tự là 1 thì ta thực hiện in ra “x^t”. Cuối cùng ta

phép chia nên em khởi tạo phần đầu của phương thức bằng một phương thức
init(string dulieu, string dtsinh) với đầu vào là xâu bit cần kiểm tra hoặc cần
tính là dulieu và dtsinh là đa thức sinh, để chương trình sẽ chạy theo từng bước
của phép chia em xây dựng phương thức thuchienchia() đây chính là tách từ
vòng lặp while của phương thức phepchia và dùng một time để thay thế vòng
lặp, trong phương thức thực hiện cứ mỗi bước sẽ vẽ ra một kí tự kết quả của
phép trừ, cuối cùng khi không thỏa mãn điều kiện biến đếm để tính phép trừ
nhỏ hơn hoặc bằng độ dài của dulieu trừ dtsinh thì kết quả sẽ được in ra, các vị
trí in ra đều được tính toán tùy theo đầu đề, nếu phép chia quá dài nó có thể
mất chữ vì tràn ra khỏi pictureBox. Và khi người dùng nhấn nút Thuật toán
Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 8
Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC
CRC thì time này sẽ thực hiện, trong sự kiện click button thì sẽ thực hiện các
yêu cầu bài toán và các điều kiện kiểm tra sẽ được thông báo kết quả.
c. Phần thực hiện của Sinh viên Nguyễn Quý Sơn.
• Kiểm tra điều kiện đa thức sinh.
Đa thức sinh phải thỏa mãn điều kiện.
- Không chia hết cho x
- Không chia hết cho x+1
Dựa trên phương thức phepchia(string a, string b) ta sẽ viết phương thức
kiemtradk(string a) với đầu vào là đa thức sinh nếu đa thức sinh chia hết cho
“10” hoặc “11” thì đa thức sinh đó không thỏa mãn điều kiện ngược lại đã thỏa
mãn điều kiện của đa thức sinh.
• Thiết kế Form chương trình.
- Với yêu câu nhập chuỗi thông tin hoặc chuỗi kết quả nhận được
trong quá trình truyền tin, và nhập đa thức sinh ta sẽ có 1 Textbox để nhập
thông tin cần xét và 1 comboBox để nhập đa thức sinh.
- Một 2 groupBox, trong đó có 1 groupBox chưa nút điều khiển và 2
text nhập liệu, 2 nút chọn để cho người dùng chọn việc tính xâu cần truyền
hay kiểm tra thông tin nhận được. groupBox còn lại gồm các label thể hiện