CYCLIC REDUNDANCY CHECK (CRC)
• Giới thiệu. • Cách xác định CRC-n • Một số đa thức sinh. • Ví dụ. • CRC-4 trong PCM-30
GIỚI THIỆU
• CRC là một phương pháp để phát hiện lỗi bằng cách
gắn thêm một khối bit phía sau khối dữ liệu.
• Thuật toánđể tạo ra khối bit CRC là dựa trên đại số
đa thức số nguyên, modulo 2 (GF(2)).
• CRC là phần dư của phép chia nhị phân không nhớ.
VÍ DỤVỀ PHÉP TOÁN MODULO 2 (mod 2)
3
3
3
(mod
1
2
)2
x
x
x
x
x
(
(
• Trong trường GF(2), các hệ số của đa thức là các số 1 và 0. • Ví dụ cộng hai đa thức: x )1 ) =+
1 =+
+
+
+
+
x
x
)11(
(mod
)2
x
x
=+=
=+
x 00. =
Vì
2
3
2
3
x
(
x
(mod
x
x
x
2 • Phép nhân cũng vậy: x ).( )1 =+
+
x =+
+
+
x 2 )2 • Chúng ta cũng có thể chia đa thức theo mod 2 để tìm thương
(quotient) và số dư (remainder): 3
2
x
x
(
x
(
x
(mod
)2
=
)1 −+
=
)1 ++
+ x
+ 1
x
1
x
1
1 +
1 +
x +
CÁCH BIỂU DIỄN MỘT CHUỖI SỐ NHỊ PHÂN THÀNH ĐA THỨC NHỊ PHÂN
b(m-1) b(m-2) … b2
b1
b0
Chuỗi bit Số bit: m
Đa thức nhị phân biểu diễn chuỗi bit trên là:
b(m-1).x(m-1) + b(m-2).x(m-2) + … + b2.x2 + b1.x1 + b0.x0
• Vídụ: Chuỗi bit 101 có thể được biểu diễn dưới dạng đa thức
2
0
2
.1
x
.0
1 x
.1
x
x
1
nhị phân như sau: +
+
=
+
CÁCH XÁC ĐỊNH CRC-n
• Các bước thực hiện:
xGxQ ). )(
xxM ( ).
xR )(
(
– Biểu diễn chuỗi bit thành đa thức nhị phân M(x). – Nhân M(x) với xn: M(x).xn. – Chia M(x).xn cho đa thức sinh G(x) của CRC-n. – Như vậy ta được thương Q(x) và số dư R(x). – Số dư R(x) chính là CRC-n. • Như vậy tổng quát ta có thểviết: n +
=
MỘT SỐ ĐA THỨC SINH G(x)
CRC-n G(x) USE
x+1 Hardware (parity bit) CRC-1
CRC-4 x4 + x + 1 PCM-30
CRC-5 - CCITT x5 + x3+ x+1 ITU-G.704
CRC-5 - USB USB token packets x5 + x2+ 1
Telecom systems, MMC x7 + x3+ 1 CRC-7
CRC-8 x8 + x7 + x6 + x4 + x2 + 1
CRC-12 use: telecom systems x12 + x11 + x3 + x2 + x + 1
CRC-32 - MPEG2
x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1
…
MỘT SỐ VÍ DỤ TÍNH CRC-n
• Ví dụ 1:
Tìm CRC-1 của chuỗi số nhị phân sau: 1101001010101010
MỘT SỐ VÍ DỤ TÍNH CRC-n (tt)
• Đáp số ví dụ 1: M(x) = x15+x14+x12+x9+x7+x5+x3+x G(x) = x+1 Q(x) = x15+x12+x11+x10+x7+x6+x3+x2 R(x) = 0 (cid:206)CRC-1 = 0
MỘT SỐ VÍ DỤ TÍNH CRC-n (tt)
• Ví dụ 2:
Tìm CRC-7 của chuỗi số nhị phân sau: 1101001010101010
MỘT SỐ VÍ DỤ TÍNH CRC-n (tt)
• Đáp số ví dụ 2: M(x) = x15+x14+x12+x9+x7+x5+x3+x G(x) = x7 + x3 + 1 Q(x) = x15+x14+x12+x11+x10+x9+x7+x6+x5+x4+x3 R(x) = x5+x4+x3 (cid:206)CRC-7 = 0111000
CRC-4 TRONG PCM-30
TS0 TS0 FRA- ME FRA- ME
0 1 1 0 1 1 #8 1 1 1 0 1 0 0 C1
#9
0 0 1 1 0 1 1 #10 1 1 1 0 1 0 0 C2
#11
0 0 1 1 0 1 1 #12 1 1 1 0 1 0 0 C3
#13
0 0 1 1 0 1 1 #14 1 1 1 0 1 0 0 C4
#0 C1 0 #1 #2 C2 #3 #4 C3 #5 #6 C4 #7 #15
Multi-frame
Submultiframe#1 Submultiframe#2
CRC-4 TRONG PCM-30 (tt)
• Giá trị CRC-4 của đa khung con #n được tính từ các bit tin của đa khung con #(n-1) (trừ các bit CRC). • Đếm tổng số bit 1 trong một đa khung con #(n-1). • Đổi số này thành số nhị phân. • Sau đó tính CRC-4 của số nhị phân này. • Truyền CRC-4 này ở đa khung con #n.
VÍ DỤ TÍNH CRC-4
• Ví dụ 3:
Giả sử bộ phát PCM-30 tạo các đa khung con thứ (n- 1) có tổng số bit 1 là 1210.Hãy xác định giá trị CRC- 4 của đa khung con này?
VÍ DỤ TÍNH CRC-4 (tt)
• Đáp số ví dụ 3: CRC-4 = 0101
VÍ DỤ TÍNH CRC-4 (tt)
• Giải ví dụ 3: • Đổi số 1210 ra số nhị phân: 10010111010 • M(x) = x10+x7+x5+x4+x3+x • G(x) = x4+x+1 • Q(x) = x10+x6+x5+x4+x+1 • R(x) = x2+1
VÍ DỤ TÍNH CRC-4 (tt)
• Ví dụ 4:
Giả sử bộ phát PCM-30 tạo các đa khung con thứ (n- 1) với xác suất xuất hiệnbit 1 là 50%. Hãy xác định giá trị CRC-4 của đa khung con này?
VÍ DỤ TÍNH CRC-4 (tt)
• Đáp số ví dụ 4: CRC-4 = 1011
VÍ DỤ TÍNH CRC-4 (tt)
• Giải ví dụ 4: • Tổng số bit 1: 2048*50% = 1024. • SỐ nhị phân: 10000000000 • M(x) = x10 • G(x) = x4 + x + 1 • Q(x) = x10 + x7 + x6+x4 + x2 + x + 1 • R(x) = x3+ x + 1
