Bài giảng Cơ sở lí thuyết thông tin - Chương 4: Mã vòng CRC - Phạm Hải Đăng

Cơ sở lí thuyết thông tin Chương 4: Mã vòng CRC TS. Phạm Hải Đăng 11/12/2013 Slice 1 Trường ĐH Bách Khoa Hà Nội Phần 1: Khái niệm cơ bản  Định nghĩa Mã vòng  Mã vòng là mã khối tuyến tính C(n,k).  Nếu c là từ mã của mã vòng C(n,k), các dịch vòng của từ mã c cũng là từ mã của mã vòng C(n,k).  Cấu trúc dịch vòng giúp cho việc tính toán mã hóa và giải mã, tính toán vector syndrome trở nên dễ dàng. 11/12/2013 Slice 2 Trường ĐH Bách Khoa Hà Nội 0 1 1 (1) 1 0 1 2 ( , ,..., ) ( , , ,..., n n n c c c c c c c c c      Phần 1: Khái niệm cơ bản  Biểu diễn mã vòng dưới dạng đa thức  Mỗi từ mã c(x) đều có bậc lớn hơn hoặc bằng n-k, nhỏ hơn hoặc bằng n-1 11/12/2013 Slice 3 Trường ĐH Bách Khoa Hà Nội 2 1 0 1 2 1 (1) 2 1 1 0 1 2 ( ) ... ( ) ... n n n n n c x c c x c x c x c x c c x c x c x                Phần 1: Khái niệm cơ bản  Đa thức sinh g(x)  Chỉ có duy nhất một đa thức sinh g(x) với mỗi mã vòng.  Bậc của đa thức sinh g(x) phải nhỏ hơn hoặc bằng n-k.  Đa thức từ mã c(x) phải chia hết cho đa thức sinh g(x).  Đa thức từ mã đều có thể biểu diễn dưới dạng trong đó là đa thức bản tin 11/12/2013 Slice 4 Trường ĐH Bách Khoa Hà Nội 2 0 1 2 0 g( ) ... 1 n k n k n k x g g x g x g x g g           ( ) ( ) ( )c x m x g x 2 1 0 1 2 1( ) ... k km x m m x m x m x       Phần 1: Khái niệm cơ bản  Tính chất của đa thức sinh  Đa thức sinh g(x) luôn được là đa thức con của đa thức  Tất cả các đa thức con của đa thức với bậc (n-k) đều có thể sử dụng làm đa thức sinh.  Do chia hết cho g(x) trong đó h(x) là đa thức kiểm tra của đa thức sinh g(x) của mã vòng (n,k). 11/12/2013 Slice 5 Trường ĐH Bách Khoa Hà Nội 1 ( ) ( )nx h x g x  1nx  1nx  1nx  2 0 1 2 0 ( ) ... 1 k k k h x h h x h x h x h h        Phần 1: Khái niệm cơ bản  Ví dụ:  Các đa thức con có bậc 1, 2, 4, 4, 4.  Đa thức được sử dụng cho mã vòng (15,5)  Đa thức có thể sử dụng cho mã vòng (15, 10) 11/12/2013 Slice 6 Trường ĐH Bách Khoa Hà Nội Bảng mã chuẩn CRC 11/12/2013 Slice 7 Trường ĐH Bách Khoa Hà Nội Phần 2: Mã hóa và giải mã không hệ thống  Vector bản tin biểu diễn dạng đa thức  Từ mã dạng không hệ thống (nonsystematic)  Quá trình mã hóa không hệ thống biểu diễn dạng ma trận 11/12/2013 Slice 8 Trường ĐH Bách Khoa Hà Nội Phần 2: Mã hóa và giải mã không hệ thống  Biểu diễn dạng ma trận 11/12/2013 Slice 9 Trường ĐH Bách Khoa Hà Nội Phần 2: Mã hóa và giải mã không hệ thống  Ví dụ: với mã vòng n=7 Ma trận sinh G dạng không hệ thống được biểu diễn  Bảng quan hệ giữa bản tin và từ mã (dạng vector và dạng đa thức) 11/12/2013 Slice 10 Trường ĐH Bách Khoa Hà Nội Phần 2: Mã hóa và giải mã không hệ thống Giải mã vòng dạng không hệ thống  Đa thức thu được phía thu r(x). Để kiểm tra r(x)  s(x) là đa thức syndrome. s(x)=0 khi và chỉ khi r(x) là từ mã. 11/12/2013 Slice 11 Trường ĐH Bách Khoa Hà Nội   ( ) ( ) ( ) ( ) ( ) m(x) 1 0 n c x h x m x g x h x x     Phần 2: Mã hóa và giải mã không hệ thống Xây dựng ma trận kiểm tra dạng không hệ thống  Do bậc của m(x) nhỏ hơn k, do đó các hệ số bằng 0 trong đa thức Do đó, có hệ số bằng 0 trong đa thức  Ma trận kiểm tra dạng không hệ thống được biểu diễn dạng 11/12/2013 Slice 12 Trường ĐH Bách Khoa Hà Nội Phần 2: Mã hóa và giải mã không hệ thống Xây dựng ma trận kiểm tra dạng không hệ thống  Do bậc của m(x) nhỏ hơn k, do đó các hệ số bằng 0 trong đa thức Do đó, có hệ số bằng 0 trong đa thức  Ma trận kiểm tra dạng không hệ thống được biểu diễn dạng 11/12/2013 Slice 13 Trường ĐH Bách Khoa Hà Nội Phần 2: Mã hóa và giải mã không hệ thống  Ví dụ: Cho mã vòng (7,3) với đa thức sinh Xây dựng ma trận sinh và ma trận kiểm tra dạng không hệ thống. 11/12/2013 Slice 14 Trường ĐH Bách Khoa Hà Nội Phần 3: Mã hóa và giải mã dạng hệ thống Cho đa thức bản tin m(x) và đa thức sinh g(x). Từ mã dạng hệ thống được xây dựng theo công thức sau:  Thực hiện phép chia đa thức lấy phần dư d(x)  Từ mã dạng hệ thống của bản tin m(x) được tính như sau  Từ mã c(x) thỏa mãn điều kiện chia hết cho đa thức sinh g(x), có bậc lớn hơn (n-k) và nhỏ hơn n.  Từ mã được biểu diễn dạng vector 11/12/2013 Slice 15 Trường ĐH Bách Khoa Hà Nội ( ) ( ) ( ) ( )n kx m x q x g x d x   ( ) ( ) ( )n kc x x m x d x  0 1 1 0 1 1[ , ,..., , , ,..., ]n k kc d d d m m m      Phần 3: Mã hóa và giải mã dạng hệ thống  Biểu diễn ma trận sinh và ma trận kiểm tra dạng hệ thống Tương đương với việc thực hiện phép chia lấy phần dư với các hàng trong ma trận G Thu được ma trận sinh dạng hệ thống 11/12/2013 Slice 16 Trường ĐH Bách Khoa Hà Nội mod(x )n k 1mod(x )n k  2mod(x )n k  1mod(x )n  |P I Phần 3: Mã hóa và giải mã dạng hệ thống  Ma trận kiểm tra dạng hệ thống 11/12/2013 Slice 17 Trường ĐH Bách Khoa Hà Nội | TI P    Phần 3: Mã hóa và giải mã dạng hệ thống  Ví dụ: Cho đa thức sinh Biểu diễn ma trận sinh và ma trận kiểm tra dạng hệ thống. 11/12/2013 Slice 18 Trường ĐH Bách Khoa Hà Nội Phần 4: Thực hiện phần cứng mã hóa giải mã vòng CRC  Mạch nhân đa thức 11/12/2013 Slice 19 Trường ĐH Bách Khoa Hà Nội Phần 4: Thực hiện phần cứng mã hóa giải mã vòng CRC  Mạch chia đa thức  Ví dụ: Mạch chia đa thức Giá trị khởi tạo của các FF-D là ‘0’. 11/12/2013 Slice 20 Trường ĐH Bách Khoa Hà Nội Phần 4: Thực hiện phần cứng mã hóa giải mã vòng CRC  Ví dụ: Mạch chia đa thức Bảng quan hệ đầu vào – đầu ra mạch chia 11/12/2013 Slice 21 Trường ĐH Bách Khoa Hà Nội 8 7 5( ) 1a x x x x x    