Tài liệu Bài tập lớn mạng truyền thông mô phỏng phương pháp phát hiện lỗi crc

Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC Phần I : Lý thuyết 1. Định nghĩa. CRC ( Cyclic Redundancy Check ) còn gọi là phương pháp mã đa thức hoặc mã vòng. Phương pháp này được sử dụng trong hầu hết các hệ thống truyền thông. Tuy cái tên của nó không biểu hiện nhiều, nhưng ý tưởng ở đây là thông tin kiểm lỗi ( ở đây được gọi là checksum ) phải được tính bằng một thuật toán thích hợp, trong đó giá trị mỗi bit của thông tin nguồn đều được tham ra nhiều lần vào quá trình tính toán. Để tính toán thông tin kiểm lỗi đó, người ta dùng một “ đa thức sinh ” G ( generator polynomial ) có một dạng đặc biệt. Chính vì thế phương pháp này còn được gọi là phương pháp dùng đa thức. G được quy ước dưới dạng nhị phân, tức các hệ số của nó chỉ có giá trị 1 hoặc 0 tương ứng với các chữ số trong một dãy bit. Ví dụ : Dạng đa thức : G = x7 + x6 + x5 + x2 + 1 Dạng nhị phân : G = 11100101 2. Phương pháp 3. - Coi bản tin phát đi như một đa thức - Máy phát chia đa thức bản tin cho một đa thức sinh cho trước - Phần dư được gắn vào cuối bản tin - Dữ liệu(bản tin với phần dư) được phát đến máy thu - Máy thu chia dữ liệu đã nhận được cho cùng một đa thức sinh - Nếu số dư bằng 0 thì không có lỗi xảy ra trong đường truyền - Nếu số dư khác 0 thì đã có lỗi xảy ra trong đường truyền Cách tạo phần dư CRC - Giả sử G là đa thức sinh có bậc n;I là dãy thong tin nguồn - Thêm n bit 0 vào cuối chuỗi bit I được đa thức nhị phân P - Chia đa thức P cho đa thức G theo quy tắc của phép trừ không nhớ Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 1 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC - - Phần dư R của phép chia được thay thế cho n bit 0 bổ sung trong P để được đa thức D là dãy bit được gửi đi thay cho I (D=P+R) - Theo quy tắc của phép chia đa thức nhị phân nếu P-R chia hết cho G thì P+R cũng chia hết cho G Dãy bit nhận được (D’) sẽ được đem chia cho G. Nếu phép chia không có dư máy thu sẽ xóa phần CRC đi và dữ liệu được chấp nhận. Nếu phép chia có dư dữ liệu bị từ chối và yêu cầu truyền lại Ví dụ : - Dãy bit truyền đi là: I=100100 - Đa thức sinh: G=x3+x2+1 (tương ứng với chuỗi 1101) - Đa thức nhị phân: P=100100000 - Phần dư CRC: Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 2 Bài tập lớn Mạng truyền thông 4. Mô phỏng phương pháp phát hiện lỗi CRC Cách chọn đa thức sinh Đa thức được chọn phải thỏa mãn hai tính chất sau: Không chia hết cho x. Điều này đảm bảo tất cả các lỗi đa bit có độ tương đương bậc của đa thức được phát hiện. - Không chia hết cho x+1. Điều này đảm bảo tất cả các lỗi đa bit có số lẻ các bit bị lỗi được phát hiện 5. Đánh giá - CRC có thể phát hiện được tất cả các lỗi có một số lẻ bit bị lỗi CRC có thể phát hiện được tất cả các lỗi đa bit có độ dài nhỏ hơn hoặc bằng bậc của đa thức CRC có thể phát hiện được các lỗi đa bit có độ dài lớn hơn bậc của đa thức với xác xuất cao Một điều đáng chú ý là tuy phương pháp CRC có vẻ như phức tạp, nhưng thực sự việc thể hiện nó lại rất đơn giản. Phép chia đa thức nhị phân được thực hiện thuần túy bởi các phép trừ không có nhớ - hay chính là các phép logic XOR. Bên cạnh đó chỉ cần các phép sao chép và so sánh bit thông thường. Loại lỗi Chất lượng phát hiện lỗi Các lỗi bit đơn Các lỗi bit kép Một số lẻ các bit bị lỗi 100% 100% khi đa thức sinh có ít nhất 3 bit 1 100% khi đa thức sinh không chia hết cho x+1 Một cụm lỗi có chiều dài < 100% n+1 Một cụm lỗi có chiều dài = Xác suất bằng 1-(1/2)n-1 n+1 Một cụm lỗi có chiều dài > Xác xuất bằng 1-(1/2)n-1 n+1 Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 3 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC Phần II : Demo mô phỏng thuật toán CRC 1. Yêu cầu của chương trình. - Nhập đa thức sinh ( có thể kiểm tra điều kiện của đa thức sinh ), xâu bít dữ liệu, tính ra xâu bít truyền đi. - Mô phỏng được phép chia đa thức không nhớ giống như Silde của thầy. 2. Thực hiện kiểm tra dữ liệu nhận được. Phân tích thuật toán CRC - Giả sử đa thức G có bậc n, dãy bit mang thông tin I được thêm n bit 0 và coi như một đa thức nhị phân P. - Đa thức P được chia cho đa thức G, dựa vào các quy tắc đơn giản của phép trù không nhớ như sau: 1–1=0 0–0=0 1–0=1 0–1=1 Không cần quan tâm đến kết quả của phép chia, phần dư R ( lấy n chữ số ) của phép chia được thay thế vào chỗ của n chữ số 0 bổ sung trong P , tức là ta có D = P + R. Theo tính chất của phép chia đa thức nhị phân, nếu D – R chia hết cho G thì D = P + R cũng vậy. R được gọi là checksum và D chính là dãy bit được gửi đi thay cho I. - Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 4 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC - Giả sử dãy bit nhận được là D’ không chia hết cho G thì tức là D khác D’, ta có thể khẳng định rằng chắc chắn bức điện bị lỗi. Ngược lại, nếu D’chia hết cho G, thì bức điện đó không bị lỗi và ta tách bỏ đi n bit cuối lấy các bit còn lại là thông tin nhận được.  Từ những vấn đề trên để thực hiện truyền thông tin hay kiểm tra dãy bit nhận được ta chỉ cần thực hiện được phép chia đa thức nhị phân không nhớ. 3. Phân công công việc cho các thành viên trong nhóm. Nhóm có 3 sinh viên cùng thực hiện và chương trình gồm có các phần công việc như sau : • Định nghĩa quy tắc của phép trừ không nhớ, chuyển dãy nhị phân của đa thức sinh về đa thức tương ứng (Sinh viên thực hiện Nguyễn Thị Huệ) • Xây dựng phép chia đa thức nhị phân không nhớ, thực hiện mô phỏng phép chia đa thức không nhớ và đưa ra kết quả yêu cầu kiểm tra hay tính ra dãy bit cần truyền (Sinh viên thực hiện Cao Thị Phương Anh) Kiểm tra điều kiện đa thức sinh, thiết kế Form chương trình (Sinh viên thực hiện Nguyễn Quý Sơn) • a. Phần thực hiện của Sinh viên Nguyễn Thị Huệ. - Thuật toán thực hiện trên phép chia không nhớ với quy tắc đơn giản 1–1=0 0–0=0 1–0=1 0–1=1 Nên em đã viết một phương thức pheptinh(char a, char b) với giá trị trả về là 1 kí tự kiểu char là kết quả của phép trừ với các quy tắc đơn giản ở trên. - Tiếp theo là việc thực hiện chuyển dãy nhị phân của đa thức sinh về đa thức thức tương ứng. Em đã viết một phương thức đó là phương thức sinhbieuthuc(string s) phương thức này trả về một chuỗi biểu diễn đa thức tương ứng với dãy nhị phân của đa thức sinh. - Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 5 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC Trong phương thức này thì ta nhậ thấy chuỗi nhị phân của đa thức sinh cứ vị trí nào là kí tự 1 thì khi chuyển sang đa thức tương ứng là 1*xt với t là số ngũ tại vị trí i thuộc dãy và t được tính bằng cách lấy chiều dài của chuỗi trừ đi ( vị trí i + 1), ta sẽ dùng 1 vòng lặp for cho i chạy từ đầu đến hết chuỗi. Nếu tại vị trí i nào đó có giá trị của kí tự là 1 thì ta thực hiện in ra “x^t”. Cuối cùng ta được đa thức tương ứng của dãy nhị phân của đa thức sinh. - b. Phần thực hiện của Sinh viên Cao Thị Phương Anh. • Xây dựng phép chia nhị phân không nhớ. - Phương thức phepchia(string a, string b) với đầu vào string a là số chia và string b là số bị chia phương thức này thực hiện việc tính ra phần dư của dãy a chia b, phục vụ cho việc kiểm tra điều kiện của đa thức sinh. Ý tưởng : dựa trên ví dụ ta thấy - Nhận thấy số chia khi chia cho số bị chia nếu kí tự đầu của số chia là 1 thì số chia sẽ trừ cho đa thức sinh, nếu là kí tự 0 thì trừ cho chuỗi bit toàn kí tự 0 có độ dài bằng độ dài chuỗi đa thức sinh. Trong phương thức này ta sẽ sử dụng một mảng kí tự char[] bandau = new char[a.Length] để copy lại toàn bộ Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 6 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC chuỗi kí tự của string a hay số chia. Ta sẽ thao tác phép chia trên mảng này, và xây dựng chuỗi string c2 toàn các bit 0 có độ dài bằng độ dài đa thức sinh. - Giờ ta tính các bước thực hiện: khởi tạo một biến đếm h = 0, nhận thấy bandau[h] = ‘1’ => ta có kết quả như dưới. - Lúc này, sang bước tiếp theo ta sẽ cho h tăng lên 1 lúc này h = 1, bandau[h] = ‘1’ => kết quả là - Cứ làm như trên đến khi h tăng và h = 5 = dộ dài của số chia trừ đi độ dài của số bị chia thì ta nhận được phần dư cần tìm Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 7 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC  Ta sẽ sử dụng một vòng lặp while vòng lặp kết thúc khi h > độ dài của chuỗi số chia trừ đi độ dài của số bị chia. Ở đây là không quan tâm đến thương mà chỉ quan tâm đến phần dư. Thực hiện mô phỏng phép chia không nhớ phép chia đa thức không nhớ và đưa ra kết quả yêu cầu kiểm tra hay tính ra dãy bit cần truyền. • Để thực hiện mô phỏng phép chia không nhớ, mô phỏng từng bước của phép chia thì giống như phương thức phép chia nhưng vì phải mô tả từng bước phép chia nên em khởi tạo phần đầu của phương thức bằng một phương thức init(string dulieu, string dtsinh) với đầu vào là xâu bit cần kiểm tra hoặc cần tính là dulieu và dtsinh là đa thức sinh, để chương trình sẽ chạy theo từng bước của phép chia em xây dựng phương thức thuchienchia() đây chính là tách từ vòng lặp while của phương thức phepchia và dùng một time để thay thế vòng lặp, trong phương thức thực hiện cứ mỗi bước sẽ vẽ ra một kí tự kết quả của phép trừ, cuối cùng khi không thỏa mãn điều kiện biến đếm để tính phép trừ nhỏ hơn hoặc bằng độ dài của dulieu trừ dtsinh thì kết quả sẽ được in ra, các vị trí in ra đều được tính toán tùy theo đầu đề, nếu phép chia quá dài nó có thể mất chữ vì tràn ra khỏi pictureBox. Và khi người dùng nhấn nút Thuật toán - Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 8 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC CRC thì time này sẽ thực hiện, trong sự kiện click button thì sẽ thực hiện các yêu cầu bài toán và các điều kiện kiểm tra sẽ được thông báo kết quả. c. Phần thực hiện của Sinh viên Nguyễn Quý Sơn. • Kiểm tra điều kiện đa thức sinh. Đa thức sinh phải thỏa mãn điều kiện. - Không chia hết cho x - Không chia hết cho x+1 Dựa trên phương thức phepchia(string a, string b) ta sẽ viết phương thức kiemtradk(string a) với đầu vào là đa thức sinh nếu đa thức sinh chia hết cho “10” hoặc “11” thì đa thức sinh đó không thỏa mãn điều kiện ngược lại đã thỏa mãn điều kiện của đa thức sinh. • Thiết kế Form chương trình. Với yêu câu nhập chuỗi thông tin hoặc chuỗi kết quả nhận được trong quá trình truyền tin, và nhập đa thức sinh ta sẽ có 1 Textbox để nhập thông tin cần xét và 1 comboBox để nhập đa thức sinh. Một 2 groupBox, trong đó có 1 groupBox chưa nút điều khiển và 2 text nhập liệu, 2 nút chọn để cho người dùng chọn việc tính xâu cần truyền hay kiểm tra thông tin nhận được. groupBox còn lại gồm các label thể hiện thông tin của bài toán. Một pictureBox để thể hiện mô phỏng phép chia không nhớ và hiển thị kết quả của yêu cầu. Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 9 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 10 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC Phần III : Hướng dẫn sử dụng chương trình Bước 1 : nhập xâu bit cần thực hiện vào textbox Bước 2 : nhập hoặc chọn đa thức sinh từ comboBox • Nếu đa thức sinh không thỏa mãn yêu cầu thì chương trình sẽ đưa ra thông báo và bạn sẽ nhập lại đa thức sinh và nhấn nut Thuật toán CRC để thực hiện lại. Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 11 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC Bước 3: chọn yêu cầu. • Nhấn ô chọn Xâu cần truyền là chọn yêu cầu tính ra xâu bit cần truyền đi. Nhấn ô chọn Kiểm tra dữ liệu nhận được là thực hiện yêu cầu kiểm tra thông tin nhận được có lỗi hay không. • Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 12 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC • Nếu bạn không nhấn chọn yêu câu thì chương trình sẽ hiện ra thông báo và lúc đó bạn phải chọn lại yêu cầu và nhấn nút Thuật toán CRC để thực hiện chương trình. Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 13 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC Sau khi chọn lại: Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 14 Bài tập lớn Mạng truyền thông Mô phỏng phương pháp phát hiện lỗi CRC Cao Thị Phương Anh – Nguyễn Thị Huệ - Nguyễn Quý Sơn – Lớp TH-7B Page 15