CYCLIC REDUNDANCY CHECK (CRC)

Chia sẻ: Ngoc Hanh | Ngày: | Loại File: PDF | Số trang:18

Thêm vào BST

Báo xấu

621
lượt xem 116
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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: ( x 3 + x) + ( x + 1) = x 3 + 2 x + 1...

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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: ( x 3 + x) + ( x + 1) = x 3 + 2 x + 1 = x 3 + 1 (mod 2) Vì 2x = x + x = x(1 + 1) = x.0 = 0 (mod 2) • Phép nhân cũng vậy: ( x 2 + x).( x + 1) = x 3 + 2 x 2 + x = x 3 + x (mod 2) • Chúng ta cũng có thể chia đa thức theo mod 2 để tìm thương (quotient) và số dư (remainder): x +x +x 3 2 1 1 = ( x + 1) − = ( x + 1) + (mod 2) x +1 x +1 x +1
CÁCH BIỂU DIỄN MỘT CHUỖI SỐ NHỊ PHÂN THÀNH ĐA THỨC NHỊ PHÂN Chuỗi bit b(m-1) b(m-2) … b2 b1 b0 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 nhị phân như sau: 1.x 2 + 0.x1 + 1.x 0 = x 2 + 1
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: M ( x).x n = Q( x).G ( x) + R ( x)
MỘT SỐ ĐA THỨC SINH G(x) CRC-n G(x) USE CRC-1 x+1 Hardware (parity bit) CRC-4 x4 + x + 1 PCM-30 CRC-5 - CCITT x5 + x3+ x+1 ITU-G.704 CRC-5 - USB x5 + x2+ 1 USB token packets CRC-7 x7 + x3+ 1 Telecom systems, MMC CRC-8 x8 + x7 + x6 + x4 + x2 + 1 CRC-12 x12 + x11 + x3 + x2 + x + 1 use: telecom systems 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 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- FRA- TS0 TS0 ME ME #0 C1 0 0 1 1 0 1 1 #8 C1 0 0 1 1 0 1 1 #1 #9 #2 C2 0 0 1 1 0 1 1 #10 C2 0 0 1 1 0 1 1 #3 #11 #4 C3 0 0 1 1 0 1 1 #12 C3 0 0 1 1 0 1 1 #5 #13 #6 C4 0 0 1 1 0 1 1 #14 C4 0 0 1 1 0 1 1 #7 #15 Submultiframe#1 Submultiframe#2 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