Các kỹ thuật phát hiện lỗi và sửa lỗi

CÁC KỸ THUẬT PHÁT HIỆN LỖI VÀ SỬA LỖI Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 2 I. CÁC KỸ THUẬT PHÁT HIỆN LỖI 1. Khái niệm lỗi trong truyền tin. Trong các hệ thống truyền tín hiệu số, một lỗi sảy ra khi một bit bị thay đổi giữa bên gửi và bên nhận. Đó là bên gửi gửi đi bit 1 nhưng bên nhận lại nhận được bit 0 và ngược lại. Nhìn chung có hai kiểu lỗi có thể sảy ra đó là lỗi đơn (single error) và lỗi xuất hiện đột ngột. Một lỗi đơn là một trạng thái lỗi biệt lập nó thay đổi một bit nhưng không ảnh hưởng các bit bên cạnh. Một lỗi xuất hiện đột ngột có độ dài B (bit) là một chuỗi B bit kề nhau trong đó bit đầu tiên, bit cuối cùng và một số bit ở giữa hai bit này là nhận được có lỗi. Một cách chính xác, IEEE Std 100 định Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 3 nghĩa một lỗi xuất hiện đột ngột như là một nhóm các bit trong đó hai bit lỗi liên tiếp luôn bị ngăn cách bởi một số x cho trước các bít chính xác. Bít lỗi cuối cùng trong một lỗi xuất hiện đột ngột và bit lỗi đầu tiên trong xuất hiện đột ngột tiếp theo cũng được ngăn cách x hoặc nhiều hơn các bít chính xác. Lỗi đơn có thể sảy ra và được thể hiện như là sự thể hiện của nhiễu nhiệt khi tỷ số SNR bị giảm đáng kể dẫn đến bên nhận bị nhầm lẫn khi nhận một bit Lỗi xuất hiện đột ngột phổ biến hơn lỗi đơn và khó giải quyết hơn, lỗi này thường bị gây ra bởi tạp nhiễu xung lực hoặc sự giảm âm (fading) trong môi trường mạng không dây (mobile wireless). Những Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 4 tác động của lỗi xuất hiện đột ngột sẽ cao hơn với tốc độ truyền cao hơn. 2. Pháp hiện lỗi (Error Detection) Giả sử rằng dữ liệu được truyền theo các chuỗi bít liên tiếp và được gọi là các frames. Khi đó các khả năng có thể sảy ra như sau: - Pb : Khả năng 1 bit nhận được là bị lỗi và còn được gọi là tỷ lệ bit lỗi (bit error rate – BER) - P1: Khả năng một frame nhận được không có lỗi - P2: Khả năng với một giải thuật phát hiện lỗi được sử dụng, một frame nhận được còn một hoặc nhiều lỗi không được phát hiện Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 5 - P3: Khả năng với một giải thuật phát hiện lỗi được sử dụng, một frame nhận được với một hoặc nhiều bit lỗi đã được phát hiện và không có các bit lỗi không được phát hiện. - Khi không có một phương tiện nào được sử dụng để phát hiện lỗi thì P3 bằng 0. Giả sử rằng số lượng bit trong một frame là F khi đó: P1=(1-Pb)F P2=1-P1 Như vậy khả năng một frame nhận được không có bit lỗi giảm khi khả năng lỗi đơn tăng. Hơn nữa, khả năng một frame nhận được không có bit lỗi giảm khi tăng độ dài của frame. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 6 Như vậy P3 là một khả năng một frame có lỗi và cơ chế phát hiện lỗi đã phát hiện được các lỗi này. P2 được biết đến như là tỷ lệ lỗi còn sót lại và là khả năng các lỗi không được phát hiện mặc dù đã sử dụng cơ chế phát hiện lỗi Có nhiều kỹ thuật được dùng để phát hiện lỗi. Tất các các kỹ thuật này tuân thủ theo các nguyên tắc sau đây: Cho một frame gồm các bit, một số bit để tạo thành một mã phát hiện lỗi được thêm vào bởi bên gửi (transmitter). Mã phát hiện lỗi được tính toán như là một hàm của các bit sẽ được được truyền. Thông thường, với một khối gồm k bit dữ liệu, thuật toán phát hiện lỗi sinh ra một mã phát hiện lỗi gồm n-k bit, trong đó (n-k)<k, và Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 7 được gắn vào khối dữ liệu này và tạo thành một frame gồm n bit và được truyền đi. Mã phát hiện lỗi còn được gọi là các bit kiểm tra. Bên nhận chia frame nhận được thành k bit dữ liệu và n-k bit của mã phát hiện lỗi. Bên nhận thực hiện cùng một tính toán phát hiện lỗi trên k bit dữ liệu nhận được và so sánh kết quả tính toán này với mã phát hiện lỗi đã nhận được. Một lỗi được phát hiện khi và chỉ khi có sự khác nhau giữa hai đoạn mã này. 3. Một số kỹ thuật phát hiện lỗi a, Phương pháp phát hiện lỗi bằng kiểm tra chẵn lẻ (parity check – Vertical Redundancy Check – VRC) Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 8 Phương pháp này gắn thêm một bit vào cuối khối dữ liệu. Đơn giản nhất là truyền ký tự, đó là: một ký tự được xem như là một khối gồm 7 bit dữ liệu, một bit kiểm tra chẵn lẻ được gắn vào khối này. Giá trị của bit chẵn lẻ này được lựa chọn sao cho ký tự cần gửi có một số chẵn (even) hay có một số lẻ (odd) các bit 1 Ví dụ: Cần gửi chữ G (1110001) và sử dụng odd parity. Khi đó bit 1 được gắn vào tạo thành 11110001. Bên nhận xem xét ký tự vừa nhận được, nếu số lượng các bit 1 la lẻ (odd) thì giả thiết rằng không sảy ra lỗi. Nếu một hay một số lượng lẻ các bit bị thay đổi trong quá trình truyền thì bên nhận xẽ phát hiện ra lỗi. Tuy nhiên nếu hai hay một số lượng chẵn các bit bị thay đổi bởi lỗi khi truyền thì bên nhận sẽ không được phát hiện được lỗi đã sảy ra. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 9 Thông thường bit kiểm tra chẵn được dùng trong truyền đồng bộ và bit kiểm tra lẻ được dùng trong truyền không đồng bộ. Việc sử dụng bit kiểm tra chẵn lẻ là không dễ ràng chẳng hạn như xung lực tạp nhiễu có thể phá hủy một hay nhiều bit, đặc biệt với tốc độ truyền dữ liệu cao. b, Phương pháp phát hiện lỗi bằng kiểm tra dư thừa theo chiều dọc - Longitudinal Redundancy Check – LRC Một kỹ thuật khác được sử dụng để hỗ trợ cho kỹ thuật kiểm tra bit chẵn lẻ đó là kỹ thuật Longitudinal Redundancy Check – LRC – Kiểm tra dư thừa theo chiều dọc. Kỹ thuật này như sau: Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 10 Thay vì kiểm tra riêng lẻ từng ký tự như trong VRC, dữ liệu được gửi đi như là một khối gồm nhiều ký tự, ta gắn thêm vào một bit ở cuối mỗi hàng và một bit ở cuối mỗi cột sao cho thỏa mãn điều kiện tổng số các bit 1 là chẵn hay lẻ. Thường một khối dữ liệu bao gồm 7 hoặc 8 ký tự phụ thuộc vào cách mã hóa ký tự là 7 hay 8 bit. Nếu mỗi ký tự được mã hóa bằng một mã dài 7 bit khi đó một khối dữ liệu sẽ gồm 7 ký tự và giả sử rằng số các bit 1 là lẻ. Ví du: Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 11 Bit/Value C O N T R O L Odd Parity 1 1 1 0 0 0 1 0 0 2 1 1 1 0 1 1 0 0 3 0 1 1 1 0 1 1 0 4 0 1 1 0 0 1 1 1 5 0 0 0 1 1 0 0 1 6 0 0 0 0 0 0 0 1 7 1 1 1 1 1 1 1 0 8 (Odd Parity) 0 0 1 0 0 0 0 Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 12 Khi đó nếu hai hay một số chẵn bit của một ký tự bị thay đổi thì giá trị của bit chẵn lẻ trên cột kiểm tra không thay đổi nhưng giá tri của bit chẵn lẻ trên hàng kiểm tra sẽ thay đổi. Kỹ thuật này cũng không phát hiện được hết tất cả các lỗi, chẳng hạn như hai hay một số chẵn các bit ở cùng vị trí của hai hay một số chẵn các ký tự bị thay đổi thì vẫn không phát hiện được lỗi. c, Phương pháp phát hiện lỗi bằng kiểm tra dư thừa vòng - Cyclic Redundancy Check (CRC) Đây là một phương pháp phổ biến và có hiệu quả nhất trong việc phát hiện lỗi. Cơ chế hoạt động của phương pháp này như sau: Cho một khối dữ liệu hay một message gồm k bit, bên gửi sinh ra một chuỗi gồm n-k bit được gọi là chuỗi kiểm tra frame (Frame Check Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 13 Sequence – FCS), như vậy sẽ tạo ra một frame gồm n bit và sau đó được gửi đi. Thông thường FCS được tính toán bằng cách chia n bit (bao gồm k bit dữ liệu và n-k bit 0) cho một số P cho trước. Bên nhận sau khi nhận được frame đó cũng đem chia frame nhận được bởi số P này, nếu không có dư thì cho rằng không có lỗi. Phương pháp này được chia thành các loại như modulo 2, đa thức và lô gic số học + Phương pháp Modulo 2: Sử dụng phép cộng không nhớ trong hệ đếm cơ số 2 hoặc phép trừ không nhỡ trong hệ đếm cơ số 2 (XOR), Ví du: Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 14 Phép cộng trừ không nhớ trong hệ đếm cơ số 2: 1111 1111 11001 + 1010 - 0101 x 11 0101 1010 11001 11001 11001 101011 Khi đó: Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 15 + T= một frame gồm n bit để truyền + D= một khối dữ liệu hay một message gồm k bit, đây là k bit đầy tiên của T + F= FCS gồm n-k bit và là các bit cuối cùng của T + P là một mẫu gồm n-k+1 bit là số chia được xác định trước Ta mong muốn rằng T/P không có dư Thuật toán được thực hiện như sau: + Ban đầu ta gắn n-k bit 0 vào cuối D để được n bit + Thực hiện phép chia lấy phần dư của n bit này cho mẫu P để tạo ra n-k bit của FCS + Gắn n-k bit của số dư vào cuối của T để tạo thành một khối dữ liệu và truyền đi Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 16 + Bên nhận sau khi nhận được khối dữ liệu gồm n bit, thực hiện việc chia n bit này cho mẫu P, nếu kết quả chia không có dư thì khẳng định việc truyền là không bị lỗi Ví dụ: Message D=1010001101(10 bits) Mẫu P=110101(6bits) FSC F=Được tính gồm 5 bits Do vậy: n=15, k=10, n-k=5 Từ k bits ban đầu ta có được 15 bits: 101000110100000 Thực hiện phép chia 15 bits này cho mẫu P (110101) Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 17 101000110100000 110101 110101 1 11101110100000 110101 110101 11 111010100000 110101 110101 1 1111100000 110101 110101 1 10110000 110101 110101 1 1100100 110101 110101 1 Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 18 1110 Phần dư là 01110, do đó ta có khối dữ liệu 15 bit: 101000110101110 và được truyền đi. Bên nhận sau khi nhận được chuỗi bit thực hiện phép chia chuỗi bít này cho mẫu P nếu không có dư thì khẳng định không có lỗi, nếu có dư thì cho rằng đã có lỗi do đó có thể vứt bỏ khối dữ liệu vừa nhận được và yêu cầu gửi lại. Mẫu P được chọn sao cho dài hơn FSC 1 bit và mẫu P được chọn phụ thuộc vào các loại lỗi có thể sảy ra, thông thường các bit cao nhất và bit thấp nhất trong mẫu P phải được chọn bằng 1. + Đa thức (Polynomials) Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 19 Một cách khác để diễn tả quá trình của CRC là diễn tả tất cả các giá trị D, P, T như là các đa thức của một Nn số X nào đó với hệ số 2. Các hệ số tương ứng với các bit trong các chuỗi nhị phân, chẳng hạn với D=110011 ta có D(x)=X5+X4+X+1 và P=11001 ta có P(X)=X4+X3+1. Các công việc tính toán tương tự như trong modulo 2. Lấy lại ví dụ trên ta có: D=1010001101 do đó D(X)=X9+X7+X3+X2+1 P=110101 ta có P(X)=X5+X4+X2+1 Thực hiện phép nhân đa thức D(X) với phần tử có số mũ cao nhất trong P(X) khi đó ta có D(X)x X5=x14+X12+X8+X7+X5 Thực hiện phép chia đa thức vừa nhận được cho P(X) Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 20 X14 + X12 +X8+X7 +X5 / X5+X4+X2+1 X14 + X13 +X11 + X9 X9+X8+X6+X4+X2+X X13 +X12 + X11 +X9 + X8 X13 +X12 + X10 +X8 X11 X10+X9 X7 X11 X10 X8 X6 X9 + X8 + X7 + X6 +X4 X9 + X8 + X6 X7 + X5+X4 X7 + X6 + X4 + X2 X6 + X5 + X2 Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 21 X6 + X5 + X3 +X X3+ X2+X Ta có đa thức dư bằng X3+X2+X tương đương với 01110 Cách lựa chọn P(X): Có 4 cách lựa chọn P(x) thường được sử dụng rộng rãi, đó là: CRC - 12 = X12 + X11 + X3 + X2 + X +1 CRC - 16 = X16 +X15 + X2 +1 CRC - CCITT = X16 + X12 + X2 + 1 CRC 32 = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X +1 Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 22 CRC - 12 được sử dụng để truyền các ký tự 6 bit và sinh ra một FCS có độ dài 12 bit. CRC -16 và CRC - CCITT thường được sử dụng để truyền các ký tự 8 bit tại Mỹ và Châu Âu và sinh ra một CRC có độ dài 16 bit. CRC - 32 được lựa chọn trong truyền điểm – điểm đồng bộ và được sử dụng trong các chuNn của LAN (802). Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 23 II. CÁC KỸ THUẬT SỬA LỖI 1. Khái niệm về sửa lỗi trong truyền thông Sửa lỗi là một kỹ thuật có ích được sử dụng trong các giao thức điều khiển liên kết dữ liệu và giao thức truyền tải. Tuy nhiên việc sửa lỗi sử dụng mã phát hiện lỗi đòi hỏi phải truyền lại khối dữ liệu này. Điều này là không thích đáng cho các ứng dụng không dây vì: - Tỷ lệ bit lỗi trong các truyền không dây là tương đối cao, điều này đòi hỏi phải truyền lại nhiều khối dữ liệu. - Trong một vài trường hợp, đặc biệt là truyền vệ tinh độ trễ trong khi truyền là lớn hơn so với thời gian truyền một frame, làm cho hệ thống kém hiệu quả. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 24 Một cách tiếp cận phổ biến để truyền lại là: truyền frame bị lỗi và các frame sau frame lỗi này. Với một liên kết dữ liệu dài một lỗi trong một frame sẽ bắt buộc phải truyền lại nhiều frame do đó nếu phải truyền lại nhiều thì sẽ làm cho hệ thống hoạt động không hiệu quả. Do đó nên cung cấp cho bên nhận một cơ chế sửa lỗi để sửa các lỗi sinh ra trong quá trình truyền dữ liệu. Cơ chế này có thể được mô tả như sau: Với mỗi một khối dữ liệu gồm k bit bên gửi sẽ sinh ra một khối gồm n bit (n >k) được gọi là một từ mã (codeword) bằng cách sử dụng mã sửa lỗi tiến (forward error correction – FEC), khối này sau đó được truyền đi. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 25 Trong quá trình truyền tin, một vài bit lỗi có thể được đưa vào khối này. Tại bên nhận, các tín hiệu đến được giải điều chế để sinh ra một chuỗi bit tương tự như chuỗi ban đầu nhưng có thể có lỗi. Khối này sau đó được chuyển đến bộ phận giải mã sửa lỗi tiến với một trong bốn khả năng sau: i, Nếu không có bit lỗi nào thì dữ liệu vào bộ phận giải mã sửa lỗi tiến sẽ tương tự như mã lệnh nguồn và bộ phận giải mã sẽ sinh ra khỗi dữ liệu ban đầu. ii, Với một vài loại lỗi, bộ phận giải mã có khả năng phát hiện và sửa những lỗi này Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 26 iii, Với một vài loại lỗi, bộ phận giải mã có thể phát hiện nhưng không sửa được các lỗi này, do đó nó chỉ thông báo là có các lỗi không sửa được. iv, Với một vài loại lỗi ít khi sảy ra, bộ phận giải mã không phát hiện được lỗi do đó nó sẽ sinh ra k bit dữ liệu từ n bit và k bit này sẽ khác với k bit ban đầu. Để cho bộ phận giải mã có thể phát hiện và sửa lỗi, ta cần phải truyền dư bằng cách thêm vào các bit dữ liệu một số bit dư để bộ phận giải mã có thể suy ra khối dữ liệu ban đầu, các bit dư này được gọi là khối mã phát hiện lỗi. Một vài giải thuật FEC biến đổi k bit thành n bit sao cho k bit ban đầu không suất hiện trong n bit. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 27 Nguyên tắc cơ bản của mã phát hiện lỗi là dựa trên khoảng cách Hamming (Hamming Distance) như sau: Khoảng cách Hamming giữa 2 chuỗi n bit v1 và v2 là số lượng của các bit khác nhau trong v1 và v2. Ví dụ: V1=011011 và v2= 110001 Do đó d(v1,v2)=3 Giả sử với k= 2 và n=5 và sử dụng mã lệnh ta có: Dữ liệu Mã hóa 00 00000 01 00111 10 11001 11 11110 Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 28 Giả sử bên nhận nhận được 00100, đây là mã không hợp lệ nên bên nhận phát hiện ra lỗi, tuy nhiên ta không biết khối dữ liệu nào đã được gửi đi vì có thể 1,2, 3, 4 thậm chí cả 5 bit đều bị lỗi, song ta cũng có thể nhận thấy được là d(00000,00100) = 1, và d(00111,00100) = 2 … do đó ta có thể suy luận rằng khả năng các bits đã được gửi là 00000 và do đó sẽ sinh ra được khối dữ liệu ban đầu là 00. Một cách tổng quát ta có thể quy định rằng nếu một mã nhận được bị sai thì mã đúng sẽ là mã có khoảng cách ngắn nhất so với nó và chỉ có duy nhất một mã đúng có khoảng cách ngắn nhất so với nó. Với một khối mã (k,n) có 2k mã đúng trong tổng số 2n mã. Tỷ lệ (n-k)/k được gọi tỷ lệ dư và k/n được gọi là tỷ lệ mã hóa. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 29 Cho một mã bao gồm các mã lệnh w1, w2, …., ws (s=2k) khoảng cách ngắn nhất giữa các từ mã được định nghĩa Dmin= min[(wi,wj)] (ij) Khi đó với một số nguyên dương cho trước t nếu một mã thỏa mãn dmin >= 2t+1 khi đó có thể sửa được tất cả các lỗi trong phạm vi từ 0 đến t. Nếu dmin >=2t thì các lỗi <t-1 có thể được sửa và các lỗi gồm t bit có thể được phát hiện nhưng về cơ bản là không được sửa, và ngược lại. 2. Sửa lỗi sử dụng mã soắn a, Mã hoá Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 30 Để sinh ra mã cần truyền có độ dài n bit từ k bit dữ liệu ban đầu ta có thể sử dụng mã soắn (Colvolution code) như sau: - Sinh ra các bit dư liên tục - Việc kiểm tra lỗi và sửa lỗi được thực hiện liên tục - Bộ mã bao gồm 3 thành phần (n,k,K): + Đầu vào xử lý k bit dữ liệu + Đầu ra sinh ra n bit cho mỗi một k bit dữ liệu . + K là hệ số ràng buộc. - n bit đầu ra của (n,k,K) mã phụ thuộc vào: + k bit dữ liệu đầu vào hiện thời + Các khối K-1 trước của k bit đầu vào. Các trạng thái gồm: a, b, c, d. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 31 - Nếu trạng thái là a và bit dữ liệu là 0 thì sinh ra 00 và quay trở lại a. - Nếu trạng thái là a và bit dữ liệu là 1 thì sinh ra 11 và chuyển sang trạng thái b. - Nếu trạng thái là b và bit dữ liệu là 0 thì sinh ra 10 và chuyển sang trạng thái c. - Nếu trạng thái là b và bit dữ liệu là 1 thì sinh ra 01 và chuyển sang trạng thái d. - Nếu trạng thái là c và bit dữ liệu là 0 thì sinh ra 11 và chuyển sang trạng thái a. - Nếu trạng thái là c và bit dữ liệu là 1 thì sinh ra 00 và chuyển sang trạng thái b. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 32 - Nếu trạng thái là d và bit dữ liệu là 0 thì sinh ra 01 và chuyển sang trạng thái c. - Nếu trạng thái là d và bit dữ liệu là 1 thì sinh ra 10 và chuyển sang trạng thái d. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 33 Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 34 Ví dụ: Mã hoá khối dữ liệu 1011000 sử dụng bộ mã hoá (2,1,3) ở trên ta thu được: 11100001011100 b, Giải mã Convolution code: - Sử dụng sơ đồ mắt lưới (Trellis diagram). - Sử dụng thuật toán Viterbi (một kiểu của dạng code soắn) để lựa chọn một đường đi xuyên qua các mắt lưới, đường đi này có sự chênh lệch ít nhất so với chuỗi các giá trị nhận được. Khi một đường đi hợp lệ đã được chọn bộ giải mã có thể khôi phục dữ liệu ban đầu từ dữ liệu nhận được. Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 35 Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 36 Giải thuật Viterbi sử dụng sự chênh lệch = Khoảng cách Hamming: - Đường đi hiệu quả = đường đi hợp lệ xuyên qua lưới có khoảng cách Hamming so với các bit nhận được cho đến thời điểm i là ngắn nhất. - Khoảng cách của đường đi = khoảng cách của một trạng thái cuối + khoảng cách của cạnh cuối. - Mỗi một trạng thái tại thời điểm i được gán nhãn bằng khoảng cách của đường đi hiệu quả của nó so với các bit nhận được. - Xác định trước kích thước của sổ là b. Giải mã Viterbi: - Giải thuật thực hiện trong b+1 bước: Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 37 [Bước i=0]: Trạng thái đầu tiên của mắt lưới tại thời điểm 0 được gán nhãn là 0 vì tại thời điểm này không có sự chênh lệch nào về khoảng cách. [Bước i+1]: Cho mỗi trạng thái S, tìm tất cả các đường đi hiệu quả dẫn đến S, gán nhãn cho S bằng khoảng cách của các đường này. [bước b]: Giải thuật kết thúc tại thời điểm b. Nếu tất cả các đường hiệu quả tại thời điểm này có cùng một cạnh đầu tiên, và nhãn của cạch này là x0x1….xn thì từ mã đầu tiên w0w1….wn sẽ được sửa thành x0x1….xn . Nếu có nhiều hơn một cạnh hiệu quả đầu tiên thì lỗi không thể sửa được Trường Đại học Tây Bắc - Khoa Toán - Lý – Tin. Mai Văn Tám – Bộ môn Kỹ thuật máy tính và Mạng 38