Truyền dẫn thông tin - Chương 5

MÃ SỬA LỖINhững thông tin truyền từ A B như ta đã thấy thông thường bị sai: di(t) di(t) = (... , di-1 , di , di+1 ...) Sự sai số đó do nhiều nguyên nhân: đường dây truyền, lưu lượng truyền, loại mã dùng, loại điều chế, loại thiết bị phát, loại thiết bị thu... Thường sai số đó cho phép trong khoảng: 10-4 10-7 và nhóm sai phụ thuộc loại mạch. Thường có 2 cách: • Nếu bộ giải mã tự sửa được nó sẽ sửa trực tiếp. ...
Nội dung trích xuất từ tài liệu:
Truyền dẫn thông tin - Chương 5 Bµi gi¶ng TruyÒn dÉn II CHƯƠNG V MÃ SỬA LỖINhững thông tin truyền từ A B như ta đã thấy thông thường bị sai: di(t) di(t) d’i(t) di(t) = (... , di-1 , di , di+1 ...)Sự sai số đó do nhiều nguyên nhân: đường dây truyền, lưu lượng truyền, loại mã dùng,loại điều chế, loại thiết bị phát, loại thiết bị thu... Thường sai số đó cho phép trongkhoảng: 10-4 10-7 và nhóm sai phụ thuộc loại mạch.Thường có 2 cách:• Nếu bộ giải mã tự sửa được nó sẽ sửa trực tiếp.• Nếu bộ giải mã không tìm được sai thì cần phải truyền lại một bộ phận dữ liệu để thựchiện sự sửa sai. Người ta còn gọi cách đó là sửa sai bằng cách truyền lại và gọi tắt làARQ (Automatic Repeat Request)1. Các phương pháp phát hiện lỗi đơn giản1.1. Truyền dư thừaTruyền dư thừa hay còn gọi là phương pháp truyền mỗi ký tự hai lần. Nếu như ở phía đầuthu hai ký tự nhận được kế tiếp nhau mà không giống nhau tức có lỗi truyền xuất hiện1.2. Truyền phản hồiĐây là phương pháp đơn giản để phát hiện lỗi được sử dụng một thời khi người điều hànhlàm công việc truyền dữ liệu bằng trực tiếp gõ vào bàn phím. Truyền phản hồi yêu cầuđường truyền là song công, trong đó mỗi ký tự được truyền ngay sau khi gõ bản phím. Ởđầu thu, mỗi lần nhận đuợc một ký tự thì lập tức truyền ngược lại ký tự đó cho phía phátvà ký tự đó cũng được hiển thị trên màn hình1.3. Dùng mã lặpMã lặp được cấu trúc như sau: Nếu như số phần tử “1” trong các phần tử thông tin là sốlẻ thì các phần tử kiểm tra được lặp lại đúng các phần tử thông tin. Nếu như số phần tử“1” trong các phần tử thông tinlà số chẵn thì các phần tử kiểm tra là nghịch đảo của cácphần tử thông tinVd: Cho hai từ mã, mỗi từ mã có 5 phần tử thông tin là : 10110 và 10100Từ mã lặp là: 1011010110 và 10100010111.4. Phương pháp kiểm tra chẵn lẻBé m«n HTTT & M¹ng 1 Bµi gi¶ng TruyÒn dÉn IIĐơn giản nhất là phương pháp VRC (Vertical Redundancy Check).Mỗi xâu bit biểu diễnmột ký tự cần truyền đi được thêm vào một bit ( gọi là parity bit).Bit này có giá trị (tuỳquy ước) là 0 nếu số lượng các bít 1 trong xâu là chẵn,và ngược lại. Bên nhận sẽ căn cứvào đó để phát hiện lỗiNhược điểm của VRC là không định vị được bit lỗi nên không thể tự sửa mà phải yêu cầutruyền lại. Mặt khác dùng phương pháp này có thể không phát hiện được các lỗi khôngphải là bit đơn ( chẳng hạn co 2 bit trong xâu cùng bị lỗi, giá trị của parity bit cũng khôngthay đổi).Để khắc phục, người ta dùng thêm phương pháp LRC (Longitudinal Redundancy Chech).LRC áp dụng kiểm tra parity bit cho từng khối các ký tự ( ví dụ cho vùng dữ liệu trongmột frame).Kết hợp cả hai phương pháp VRC-LRC sẽ cho phép kiểm soát lỗi theo cả haichiều, nâng cao hiệu quả đáng kể so với việc dùng riêng từng phương pháp. Hình 4-1 choví dụ minh họa kiểm soát lỗi theo cả 2 phương pháp VRC-LRC.1.5. Mã phát hiện lỗi và sửa lỗi1.6. Mã tuyến tính1.6.1. Định nghĩaTa có vectơ thông tin I của k bíti = (i1,i2,…ik)khi đó ta tạo một từ mã có độ dài là nc = (i1, i2, …ik, Ck+1, …Cn) Ci € {0,1}1.6.2. Tính chất1.7. Mã vòngViệc nghiên cứu mã tuyến tính trên đây nhằm mục đích là sao ta có thể tìm một họ mã cóđủ các tính chất sau: • mã hóa và giải mã đơn giản. • khả năng tìm và sửa lỗi độc lập theo các gói đã truyền.Ở phần trên chúng ta đã thấy việc kiểm tra theo VRC hoặc LRC còn những sai sót mà takhó tránh khỏi, với mã VRC, nếu sai số theo chiều V là số chẳn bit thì bit kiểm tra cũngkhông có gì thay đổi.Tương tự ta có nếu số bit sai là 2n, ta cũng không thể phát hiện gì được.Mã vòng với kiểm tra CRC (Cyclic Redundancy Check) có nhiều hiệu quả hơn trong việcthông báo lỗi.1.7.1. Định nghĩaBé m«n HTTT & M¹ng 2 Bµi gi¶ng TruyÒn dÉn IIMã vòng (n,k) là một mã tuyến tính (n,k) với sự hoán vị vòng của một từ mã là một từmã. C= (Cn-1 , ... , C0) € C (Cn-2 , ... , C0 , Cn-1) € CTa có thể viết một từ mã dưới dạng đa thức: C(x) = Cn-1Xn-1 + …C1X + Covà theo định nghĩa trên ta có: Xi.C(X) modul (Xn + 1) € C C(X) € C1.7.2. Đa thức sinhSự nhận biết ma trận phát G của một mã vòng được đưa đến từ sự nhận biết của đa thứcbậc n-k.Do sự chính xác của tính chất sau:Tính chất: Tất cả các từ mã vòng (n, k) là sự nhân của đa thức g(x) bậc (n-k) kết hợp từdòng cuối của G và gọi là đa thức phát.Ví dụ: Với mã tuyến tính biểu diễn ở trên, ta có ma trậnVậy: ...