Đề tài Cyclic Redundancy Check (CRC)

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) • 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: Vì • Phép nhân cũng vậy: • Chúng ta cũng có thể chia đa thức theo mod 2 để tìm thương (quotient) và số dư (remainder): )2(mod112)1()( 333 +=++=+++ xxxxxx )2(mod00.)11(2 ==+=+= xxxxx )2(mod2)1).(( 3232 xxxxxxxx +=++=++ )2(mod 1 1)1( 1 1)1( 1 23 +++=+−+=+ ++ x x x x x xxx CÁCH BIỂU DIỄN MỘT CHUỖI SỐ NHỊ PHÂN THÀNH ĐA THỨC NHỊ PHÂN • Vídụ: Chuỗi bit 101 có thể được biểu diễn dưới dạng đa thức nhị phân như sau: Số bit: m Đa thức nhị phân biểu diễn chuỗi bit trên là: Chuỗi bit b(m-1) b(m-2) … b2 b1 b0 b(m-1).x(m-1) + b(m-2).x(m-2) + … + b2.x2 + b1.x1 + b0.x0 1.1.0.1 2012 +=++ xxxx CÁCH XÁC ĐỊNH CRC-n • Các bước thực hiện: – 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: )()().().( xRxGxQxxM n += MỘT SỐ ĐA THỨC SINH G(x) CRC-n G(x) USE CRC-1 x+1 Hardware (parity bit) PCM-30 ITU-G.704 USB token packets Telecom systems, MMC use: telecom systems CRC-32 - MPEG2 x32 + x26 + x23 + x22 + x16 + x12 + x11 + x10 + x8 + x7 + x5 + x4 + x2 + x + 1 … CRC-4 x4 + x + 1 CRC-5 - CCITT x5 + x3+ x+1 CRC-5 - USB x5 + x2+ 1 CRC-7 x7 + x3+ 1 CRC-8 x8 + x7 + x6 + x4 + x2 + 1 CRC-12 x12 + x11 + x3 + 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 Î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 ÎCRC-7 = 0111000 CRC-4 TRONG PCM-30 FRA- ME TS0 #0 C1 0 0 1 1 0 1 1 1 1 1 Submultiframe#1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 0 0 0 #1 #2 C2 #3 #4 C3 #5 #6 C4 #7 Submultiframe#2 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 #15 C4#14 #13 C3#12 #11 C2#10 #9 C1#8 TS0FRA-ME Multi-frame 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