CHƯƠNG 1: CƠ SỞ LÝ THUYẾT 1.1 Tổng quan về mã khối 1.1 Mã khối Mã khối là mã gồm k bit thông tin, người ta sẽ tính toán và tạo ra r bit kiểm tra tạo thành một từ mã (n, k) với n là tổng số bit (n = k + r). Nếu k bit được truyền từ bên phát qua môi trường đến bên thu. Nếu bên thu nhận được k bit nguyên vẹn thì sẽ tính ra được r bit giống bit kiểm tra đi kèm. Có một tham số được quan tâm là R = k/n được gọi là tỉ lệ thông tin chứa dữ liệu có ích trên tổng số thông tin truyền, tỉ lệ này liên quan mật thiết đến tốc độ truyền dữ liệu: ở điều kiện kênh truyền tốt thì ta cho tỉ lệ này cao lên, điều chế bậc cao hơn để cho tăng tốc độ, ngược lại trong điều kiện kênh truyền xấu thì phải cho tỉ lệ này thấp, bit kiểm tra nhiều lên và loại điều chế mang ít thông tin, bảo đảm độ tin cậy dữ liệu.
Với k bits ta có thể tạo ra 1 bộ dữ liệu gồm 2k thông tin, tương tự với n bits ta có 2n từ mã. Bởi vì n > k cho nên số lượng từ mã luôn luôn lớn hơn số lượng thông tin, suy ra rằng: sẽ có (2n – 2k) từ mã sẽ không phù hợp với bất kì thông tin nào, các từ mã này được gọi là từ mã không hợp lệ. Ví dụ: Mã Hamming (7, 4) với độ dài từ mã là n = 7 bit, có 3 bit mang dữ liệu và 7 bit chẵn lẻ. Khoảng cách Hamming Khoảng cách Hamming giữa hai dãy ký tự có chiều dài bằng nhau được định nghĩa là tổng số lượng các bit ở vị trí tương đương có giá trị khác nhau.
Khoảng cách Hamming dùng để đo số lượng thay thế cần phải có để đổi giá trị của một dãy ký tự sang một dãy ký tự khác. Ví dụ: Khoảng cách Hamming giữa hai từ x và y, kí hiệu là d(x, y). Từ x 0 0 0 Khoảng cách Hamming d(000,011) = 2 Từ y 0 1 1 Từ x 1 0 1 0 1 Khoảng cách Hamming d(10101,11110) = 3 Từ y 1 1 1 1 0 Các lỗi xảy ra trong quá trình truyền và khoảng cách Hamming có mối liên hệ với nhau: khoảng cách Hamming giữa từ mã nhận được và từ mã được gửi đi là số bit bị hỏng trong quá trình truyền. 3 Ví dụ: Trong ví dụ bên dưới từ mã có 2 lỗi và khoảng cách Hamming giữa 2 từ mã là d(11111, 01101) = 2.
Khoảng cách tối thiểu Khoảng cách tối thiểu là khoảng cách Hamming nhỏ nhất giữa tất cả các cặp ký tự có thể có trong một tập hợp các ký tự.1: Minh họa bộ mã (5,2). Datawords Codewords 00 00000 01 01011 10 10101 11 11110 Các cặp khoảng cách Hamming: d (00000, 01011) = 3 d (00000, 10101) = 3 d (00000, 11110) = 4 d (01011, 10101) = 4 d (01011, 11110) = 3 d (10101, 11110) = 3 Khoảng cách tối thiểu dmin = 3. Bằng cách xác định khoảng cách tối thiểu của bộ mã từ đó sẽ cung cấp cho chúng ta khả năng phát hiện lỗi ngẫu nhiên của bộ mã. Từ mã nhận được là tổng (phép cộng modulo-2) của từ mã được truyền và mẫu lỗi.
Vì vậy, lỗi có thể phát hiện được khi chúng không bị thay đổi từ từ mã được truyền thành từ mã hợp lệ khác hoặc bị thay đổi thành từ mã không hợp lệ. Theo định nghĩa của khoảng cách tối thiểu, hai từ mã bất kỳ của cùng một bộ mã khác nhau ít nhất là dmin bit. Trường hợp luôn đáp ứng điều kiện này là số lỗi nhỏ hơn khoảng cách tối thiểu dmin vì từ mã được truyền đi trong trường hợp này sẽ không bị biến thành từ mã hợp lệ khác. Do đó, có thể phát hiện đến t lỗi: t d min 1 (1.1) 4 Bên cạnh đó, khoảng cách tối thiểu còn có mối quan hệ với khả năng sửa lỗi ngẫu nhiên theo biểu thức sau đây d min 1 w (1.2) 2 Với w là khả năng sửa lỗi ngẫu nhiên của mã.
Trong ví dụ trên w = 1, mã này có khả năng sửa được lỗi 1 bit. Từ hai biểu thức (1.2) có kết luận: bất kì mã nào có khả năng phát hiện được tất cả lỗi đôi thì có khả năng sửa được lỗi 1 bit.2: Các mô hình mã hóa kênh truyền. ARQ FECC Dừng Mã & ARQ liên tục Mã khối chập đợi Mã Go- Selective không back- Mã tuyến tính repeat tuyến N tính Mã không Mã tuần hoàn tuần hoàn Golay BCH Reed- Binary BCH Solomon e Hamming > (e = 1) 1 Trong thực tế, luôn luôn tồn tại nhiễu và các yếu tố khác can thiệp làm thay đổi thông tin mà chúng ta muốn gửi đi. Việc mã hóa dữ liệu sẽ giúp cho chúng ta có khả năng kiểm soát lỗi (Error control) từ đó cải thiện hiệu suất của hệ thống.
Có 2 loại kiểm soát lỗi đó là: 5 + Forward error control: thông tin sửa sai được thêm vào các ký tự hoặc các frame truyền đi, để bên nhận có thể phát hiện khi nào có lỗi và lỗi nằm ở đâu để sửa (có khả năng sửa lỗi). Cơ chế yêu cầu truyền lại ký tự/frame sai được dùng trong trường hợp này (Automatic Repeat Request – ARQ).2 Mã Hamming Là một mã cao cấp hơn của các mã kiểm tra chẵn lẻ đơn thuần. Mã Hamming chia dữ liệu thành các khối để tính các bit chẵn lẻ. Lấy ví dụ chúng ta có một từ dữ liệu dài 7 bit với giá trị là 0110101.
Đầu tiên, các bit của dữ liệu được đặt vào vị trí tương thích của chúng, sau đó các bit chẵn lẻ cho mỗi trường hợp được tính toán dùng quy luật bit chẵn lẻ số chẵn.3: Ví dụ mã hóa của mã Hamming (7,4). Thứ tự bit 1 2 3 4 5 6 7 8 9 10 11 Vị trí bit chẵn lẻ và các bit dữ liệu p1 p2 p1 p3 p2 p3 p4 p4 p5 p6 p7 Nhóm dữ liệu (không parity) 0 1 1 0 1 0 1 p1 1 0 1 0 1 1 p2 0 0 1 0 0 1 p3 0 1 1 0 p4 0 1 0 1 Nhóm dữ liệu (có parity) 1 0 0 0 1 1 0 0 1 0 1 Trong Bảng 1.3, bit parity p1 được tính cho các bit dữ liệu (d1d2d4d5d7), tương tự cho p2, p3 và p4. Bằng phương pháp này, các bit chẵn lẻ của từng nhóm dữ liệu sẽ kết hợp với nhau và tìm ra chính xác vị trí bit bị sai. Giả sử bit cuối cùng trong nhóm dữ liệu là d7 bị sai từ 1 0.
Nhóm dữ liệu mới sẽ là 10001100100.4 chúng ta sẽ phân tích quy luật giải mã của mã Hamming. Trong đó, vị trí bit bị sai là 1011 (đọc từ dưới lên) tương ứng với giá trị thập phân là 11.4: Ví dụ giải mã và sửa lỗi của mã Hamming (7,4). Thứ tự bit 1 2 3 4 5 6 7 8 9 10 11 Vị trí bit chẵn lẻ Kiểm tra Bit p1 p2 p1 p3 p2 p3 p4 p4 p5 p6 p7 và các bit dữ liệu chẵn lẻ chẵn lẻ Nhóm dữ liệu 1 0 0 0 1 1 0 0 1 0 0 1 nhận được p1 1 0 1 0 1 0 Sai 1 p2 0 0 1 0 0 0 Sai 1 p3 0 1 1 0 Đúng 0 p4 0 1 0 0 Sai 1 Hamming (7,4) có thể sửa bất cứ một bit lỗi nào và phát hiện tất cả lỗi của 1, 2 bit.2 Mã CRC Để đảm bảo phát hiện được lỗi hiện trong truyền thông nên cơ chế mã kiểm tra CRC được ứng dụng trong các giao thức như USB, CAN, Bluetooth… CRC được sử dụng làm cờ thông báo dữ liệu bị hỏng và ngăn không cho nó được gửi qua bus. Với việc các giao thức ngày nay thường hỗ trợ băng thông và tốc độ cao hơn, CRC là yếu tố cơ bản để giữ cho dữ liệu sạch và toàn vẹn trong một hệ thống nhúng.
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. Các bit bổ sung thêm vào được gọi là các bit CRC: giá trị chuỗi bit kiểm tra hay chuỗi CRC là số dư của phép chia chuỗi bit thông tin (message) cho một chuỗi bit đa thức sinh. Đa thức sinh sẽ khác nhau tùy theo các giao thức quy định. Phép chia trong tính toán CRC sử dụng phép modulo-2.
CRC rất phổ biến, vì nó rất đơn giản để lắp đặt trong các máy tính sử dụng hệ cơ số nhị phân, hiệu quả trong việc kiểm tra, và rất phù hợp để dò ra các lỗi gây ra bởi nhiễu trong khi truyền dữ liệu. Các hàm CRC thường dùng và được chuẩn hóa Các mã kiểm tra CRC được chia thành nhiều tiêu chuẩn, mỗi ứng dụng khác nhau sẽ có các mã CRC phù hợp.5: Một số đa thức sinh g(x) thông dụng của mã CRC. Tên mã Ứng dụng Đa thức biểu diễn CRC-1 Bit chẵn lẻ x+1 7 CRC-5-EPC RFID x5 + x 3 + 1 CRC-8-WCDMA Mạng di động x8 + x7 + x4 + x3 + x + 1 Mạng điều khiển cục CRC-15-CAN x15 + x14 + x10 + x8 + x7 + x4 + x3 + 1 bộ USB, Modbus, ANSI, CRC-16-ANSI x16 + x15 + x2 + 1 X3.25, HDLC, CRC-16-CCITT x16 + x12 + x5 + 1 Bluetooth… Điện thoại không dây CRC-16-DECT x16 + x10 + x8 + x7 + x3 + 1 (cordless) x32 + x26 + x23 + x22 + CRC-32-IEEE Ethernet, Wifi, x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 Phần thiết kế sẽ được tiến hành với mã CRC-16-ANSI trong Bảng 1. Bên gửi Bên nhận Bộ mã hóa Bộ giải mã a3 a 2 a 1 a0 a 3 a 2 a1 a0 0 0 0 Loại bỏ Decision logic Thương a3 a2 a1 Số chia Generator d 3 d 2 d1 d 0 Checker Kênh truyền a3 a 2 a 1 a0 r2 r1 r0 b3 b 2 b1 b0 q 2 q1 q0 Từ mã Từ mã Hình 1.1: Bộ mã hóa và bộ giải mã CRC.
Bộ tạo mã CRC Trong mô hình mã hóa ở Hình 1.1, chuỗi bit dữ liệu gồm k bits (ở hình minh họa là 4 bit a3a2a1a0) và từ mã phát đi gồm n bit nhị phân (ở hình minh họa là 7 bit: a3a2a1a0r2r1r0). Kích thước của chuỗi dữ liệu được nối thêm vào n - k bits số 0 (trong hình minh họa n – k = 7 – 4 = 3 bits) phía trước chuỗi dữ liệu. Tiếp theo, chuỗi dữ liệu 8 sau khi đã chèn thêm các bit 0 sẽ đi qua bộ tạo mã CRC (generator).