Chương 5 Mã hóa kênh truyền – Tài liệu, ebook, giáo trình, hướng dẫn

 Khái niệm về mã phát hiện sai và sửa sai. – Cơ chế phát hiện sai của mã hiệu. – Khả năng phát hiện và sửa sai. – Hệ số sai không phát hiện được.  Mã khối tuyến tính – Định nghĩa – Ma trận kiểm tra – Mạch mã hóa – Giải mã – Syndrome và sự phát hiện lỗi – Sửa lỗi

50 trang

Bạn đang đọc: Chương 5 Mã hóa kênh truyền – Tài liệu, ebook, giáo trình, hướng dẫn

| Chia sẻ : lylyngoc

| Lượt xem: 3251

Xem thêm: Các loại mã vạch | Ứng dụng loại mã vạch ngành nghề phù hợp

| Lượt tải: 3

Xem thêm: Các loại mã vạch | Ứng dụng loại mã vạch ngành nghề phù hợp

Bạn đang xem trước 20 trang

tài liệu Chương 5 Mã hóa kênh truyền, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

CHƯƠNG 5 Mã hóa kênh truyền 1  Khái niệm về mã phát hiện sai và sửa sai. – Cơ chế phát hiện sai của mã hiệu. – Khả năng phát hiện và sửa sai. – Hệ số sai không phát hiện được.  Mã khối tuyến tính – Định nghĩa – Ma trận kiểm tra – Mạch mã hóa – Giải mã – Syndrome và sự phát hiện lỗi – Sửa lỗi Nội dung 2 Vấn đề 3  Lỗi khi truyền tài liệu trên một mạng lưới hệ thống truyền tin : • Lỗi khi truyền tin là một điều khó tránh. • Nguyên nhân : Do nhiễu bên ngoài xâm nhập, tác động ảnh hưởng lên kênh truyền, làm thông tin truyền đi bị sai. 1 → 0 0 → 1 • Việc khắc phục và trấn áp lỗi là một yếu tố rất là quan trọng. Nguyên lý mã hóa trấn áp lỗi 4 • Nguyên lý chung là thêm vào tập mã cần truyền một tập bit kiểm tra nào đó để bên nhận hoàn toàn có thể trấn áp lỗi. • Bên phát : Bổ sung thêm thông tin ( thêm bit ) vào bit cần gửi. • Bên thu : Nhận thông tin bổ trợ ở phía phát, kiểm tra, phát hiện và sửa lỗi. Với n-k : bit kiểm tra Bộ mã KSL + ( n-k ) bit k bit tin tức k + n-k = n bit Phát Thu  Dạng sai lầm đáng tiếc của mã hiệu được truyền tùy thuộc đặc thù thống kê của kênh :  sai độc lập dẫn đến sai ngẫu nhiên : 1 hoặc 2 sai.  Sai đối sánh tương quan dẫn đến sai chùm ( sai cụm )  Người ta thống kê : sai ngẫu nhiên xẩy ra 80 %, sai chùm xảy ra 20 %.  Xác suất Open một từ mã n ký hiệu có t sai bất kể : p ( n, t ) = Cn tps t ( 1 – ps ) n-t 5 Khái niệm về mã phát hiện sai và sửa sai.  Số từ mã hoàn toàn có thể có : N0 = 2 n  Số từ mã mang tin : N = 2 k.  Số từ mã không dùng đến : 2 n – 2 k ( số tổng hợp cấm )  Để mạch hoàn toàn có thể phát hiện hết i lỗi thì phải thỏa mãn nhu cầu điều kiện kèm theo :  Trong đó EΣ = E1 + E2 +. .. + Ei  E1, E2 ,. . Ei là tập hợp các vector sai 1,2. .. i lỗi.  Để phát hiện và sửa hết sai 1 lỗi ta có : 6 Cơ chế phát hiện sai của mã hiệu.    E n k 1 2 2 1 2 2   n n k  Trọng số Hamming của vector t : ký hiệu : w ( t ) được xác lập theo số các thành phần khác không của vector.  Ví dụ : t1 = 1 0 0 1 0 1 1  w ( t1 ) = 4  Khoảng cách giữa 2 vector t1, t2 : ký hiệu, d ( t1, t2 ) được định nghĩa là số các thành phần khác nhau giữa chúng.  Ví dụ : t2 = 0 1 0 0 0 1 1  d ( t1, t2 ) = 3 chúng khác nhau ở vị trí 0, 1 và 3  Khoảng cách Hamming giữa 2 vector mã t1, t2 = trọng số của vector tổng t1  t2 : d ( t1, t2 ) = w ( t1  t2 ). t1 = 1 0 0 1 0 1 1  t2 = 0 1 0 0 0 1 1 t1  t2 = 1 1 0 1 0 0 0  w ( t1  t2 ) = 3 = d ( t1, t2 ) Khả năng phát hiện và sửa sai  Điều kiện để một mã tuyến tính hoàn toàn có thể phát hiện được t sai : d  t + 1  ví dụ : t = 1  d  2 ; t = 2  d  3 t = 5  d  6  Điều kiện để một mã tuyến tính hoàn toàn có thể phát hiện và sửa được t sai : d  2 t + 1 t = 1  d  3 ; t = 2  d  5 ; t = 5  d  11 8 Điều kiện phát hiện sai  Ví dụ : so với bộ mã ( 5,2 ) có trọng số Hamming w = 2 ta xác lập được thông số sai không phát hiện được : p ’ = C2 1 pqC3 1 pq2 + C2 2 p2C3 2 p2q nếu p = 10-3  p ’  6 p2 = 6.10 – 6 nghĩa là có 106 bit truyền đi, 103 bit bị sai thì có 6 bit sai không phát hiện được. 9 Hệ số sai không phát hiện được • Gọi từ mã phát đi là T. • Gọi từ mã nhận được là R • Gọi từ mã sai do đường truyền gây ra là E.  phương trình đường truyền : R = T  E T = R  E E = T  R  Đối với mã nhị phân 3 phương trình trên tương tự nhau. 10 Phương trình đường truyền  Vector sai : E = ( e0, e1, …, en )  Ví dụ : E = ( 1 0 0 1 0 1 0 )  sai ở vị trí 0, 3, 5  Trong các mạng lưới hệ thống truyền số liệu có 2 chính sách sửa lỗi : • Cơ chế ARQ ( Automatic Repeat Request-cơ chế tự động hóa phát lại ) : chính sách nhu yếu phát lại số liệu một cách tự động hóa ( khi phát hiện sai ). chính sách này có 3 dạng cơ bản :  Cơ chế ARQ dừng và chờ ( stop and wait ARQ )  Cơ chế ARQ quay ngược N vector ( N go back ARQ ).  Cơ chế ARQ lựa chọn việc lặp lại. • Cơ chế FEC ( Forward Error Control ) : phát hiện và tự sửa sai sử dụng các loại mã sửa lỗi.  Khi có sai đơn ( 1 sai ) người ta thường dùng các loại mã như : mã khối tuyến tính, mã Hamming, mã vòng …  Khi có sai chùm ( > 2 sai ) người ta thường dùng các loại mã như : mã BCH, mã tích chập, mã Trellis, mã Tubor, mã Tubor Block, mã tổng hợp GC … 11 Vector sai – cô cheá söûa loãi Mã khối tuyến tính 12 • Mã khối tuyến tính được thiết kế xây dựng dựa trên các hiệu quả của đại số tuyến tính là một lớp mã được dùng rất phổ cập trong việc chống nhiễu. • Định nghĩa : • Một mã khối có chiều dài n, k bit gồm 2 k từ mã tuyến tính C ( n, k ) nếu và chỉ nếu 2 k từ mã hình thành một khoảng trống vectơ k chiều 2 n, gồm toàn bộ các vectơ n thành phần trên trường Galois sơ cấp GF ( 2 ) ( gồm có 2 thành phần { 0,1 } với 2 phép tính + và * ). • Mã tuyến tính C ( n, k ) có mục tiêu mã hóa những khối tin ( hay thông tin ) k bit thành những từ mã n bit. Hay nói cách khác trong n bit của từ mã có chứa k bit thông tin. • Ví dụ : C ( 7,4 ) : Từ mã dài 7 bit. Thông tin cần truyền : 4 bit. Cách trình diễn mã – Ma trận sinh 13 • Mã tuyến tính C ( n, k ) là một khoảng trống k chiều của khoảng trống vectơ n thành phần, do đó sống sót k từ mã độc lập tuyến tính ( g0, g1, …, gk-1 ) sao cho mỗi từ mã trong C là một tổng hợp tuyến tính của k từ mã này : • k từ mã này tạo thành một ma trận sinh cấp k x n như sau : Với : gi = ( gi0, gi1 … gi ( n-1 ) ) với i = 0, 1, …, k-1 ) 1, …, 1,0 } 1,0 { ( … 111100           kia gagagaw i kk                                     ) 1 ) ( 1 ( 1 ) 1 ( 0 ) 1 ( ) 1 ( 11110 ) 1 ( 00100 1 1 0 … … … … nkkk n n k nk ggg ggg ggg g g g G     Cách mã hóa 14 • Nếu u = ( a0, a1, …, ak-1 ), với ai = 0/1 và 0  i  k-1, là thông tin cần được mã hóa. • Goïi t laø töø maõ phaùt ñi : t = t0 t1 …. tn-1, Vôùi tj = 0 hoaëc 1 vaø 0  j  k-1 thì từ mã w tương ứng với t được hình thành bằng cách lấy t x G w = t x G = a0g0 + a1g1 + … + ak-1gk-1 • Vì các từ mã tương ứng với các thông tin được sinh ra bởi G theo cách trên nên G được gọi là ma trận sinh của bộ mã. • Maõ khoái tuyeán tính heä thoáng coù caáu truùc : n-k bits kiểm tra K bits mang tin  Độ dài từ mã : n Ví dụ 15 • Cho ma trận sinh của một mã tuyến tính C ( 7,4 ) sau : • Nếu u = ( u0 u1 u2 u3 ) = ( 1101 ) là thông tin cần mã hóa thì từ mã tương ứng là : t0 = u0. 1 + u1. 0 + u2. 1 + u3. 1 = u0 + u2 + u3 = 1 + 0 + 1 = 0 t1 = u0. 1 + u1. 1 + u2. 1 + u3. 0 = u0 + u1 + u2 = 1 + 1 + 0 = 0 t2 = u0. 0 + u1. 1 + u2. 1 + u3. 1 = u1 + u2 + u3 = 1 + 0 + 1 = 0 t3 = u0. 1 + u1. 0 + u2. 0 + u3. 0 = u0 = 1 t4 = u0. 0 + u1. 1 + u2. 0 + u3. 0 = u1 = 1 t5 = u0. 0 + u1. 0 + u2. 1 + u3. 0 = u2 = 0 t6 = u0. 0 + u1. 0 + u2. 0 + u3. 1 = u3 = 1 • => w = ( 0001101 )                          1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 g g g g G 3 2 1 0 74 ( u0, u1, u2, u3 ) 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1   ~ ~. Gut • Bất kỳ k từ mã độc lập tuyến tính nào cũng hoàn toàn có thể được dùng để làm ma trận sinh cho bộ mã. • Một bộ mã tuyến tính ( khoảng trống mã ) hoàn toàn có thể có nhiều ma trận sinh khác nhau cùng trình diễn. • Mỗi ma trận sinh tương ứng với một cách mã hóa khác nhau. 16 Ma trận sinh Cách giải thuật 17 • Từ ma trận sinh ở ví dụ trước, gọi : u = ( a0, a1, a2, a3 ) là thông tin, w = ( b0, b1, b2, b3, b4, b5, b6 ) là từ mã tương ứng. • Ta có hệ phương trình liên hệ giữa u và w w = u x G ↔ b0 = a0 + a1 + a3 ( 1 ) b1 = a0 + a2 ( 2 ) b2 = a1 + a3 ( 3 ) b3 = a0 + a1 ( 4 ) b4 = a1 ( 5 ) b5 = a2 ( 6 ) b6 = a2 + a3 ( 7 )                            1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 4 3 1 0 74 g g g g G Cách giải thuật ( tt ) 18 • Chọn bốn phương trình đơn thuần nhất để giải các ai theo các b1 • Chọn các phương trình ( 4 ), ( 5 ), ( 6 ), ( 7 ) ta giải được : a0 = b3 + b4 a1 = b4 a2 = b5 a3 = b5 + b6 • Hệ phương trình trên gọi là hệ phương trình giải thuật. • Có thể có nhiều hệ phương trình giải thuật khác nhau, nhưng tác dụng sẽ giống nhau.                            1 1 0 0 0 1 0 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 1 1 0 1 1 4 3 1 0 74 g g g g G Mã tuyến tính mạng lưới hệ thống 19 • Một mã tuyến tính C ( n, k ) được gọi là mã tuyến tính mạng lưới hệ thống nếu mỗi từ mã có một trong hai dạng sau : • Dạng 1 : Từ mã gồm có phần thông tin k bit đi trước và phần còn lại ( gồm n-k bit ) đi sau ( phần này còn được gọi là phần dư thừa hay phần kiểm tra ) • Dạng 2 : trái lại của dạng 1, từ mã gồm có phần kiểm tra đi trước và phần thông tin đi sau. . k bit thông tin n – k bit kiểm tra n – k bit kiểm tra k bit thông tin Ma trận sinh mạng lưới hệ thống 20 • Ví dụ :               1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ) 74 ( htG Mã hóa u = 1101 → w = u x Ght = 1101000 Giãi mã w = 0110100 → u = 0110                                                              ) ( ) 1 ) ( 1 ( ) 1 ( 0 1 ) 1 ( 11 01 0 ) 1 ( 10 00 ) ( ) 1 ( 1 1 0 0 0 1 0 0 0 1 | knk knk kn kk kk knkkknk P P P P P P P P P PIG kn xét mã khối tuyến tính C ( 7,4 ) có thông tin cần mã hóa u = ( u0, u1, u2, u3 ) và từ mã phát đi tương ứng t = ( t0, t1, t2, t3, t4, t5, t6 ) Cho G ( 4,7 ) dạng không chính tắc ta đi tìm G ( 4,7 ) dạng chính tắc : Ví dụ G ( 4,7 ) = 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 ( 1 ) ( 2 ) ( 3 )  = ( 4 ) 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 1 ’ = 1 2 ’ = 2 3 ’ = 1 + 3 4 ’ = 1 + 2 + 4 ) 7,4 ( ~ G 21 Cho tin cần phát đi : u = ( u0, u1, u2, u3 ) = ( 1 0 1 1 ) ta tìm từ mã phát đi theo 2 công thức 5 và 8 từ đó rút ra nhận xét Ví dụ ( u0, u1, u2, u3 ) 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1   ~ ~. Gut t0 = u0. 1 + u1. 0 + u2. 0 + u3. 0 = u0 = 1 t1 = u0. 1 + u1. 1 + u2. 0 + u3. 0 = u0 + u1 = 1 + 0 = 1 t2 = u0. 0 + u1. 1 + u2. 1 + u3. 0 = u1 + u2 = 0 + 1 = 1 t3 = u0. 1 + u1. 0 + u2. 1 + u3. 1 = u0 + u2 + u3 = 1 + 1 + 1 = 1 t4 = u0. 0 + u1. 1 + u2. 0 + u3. 1 = u1 + u3 = 0 + 1 = 1 t5 = u0. 0 + u1. 0 + u2. 1 + u3. 0 = u2 = 1 t6 = u0. 0 + u1. 0 + u2. 0 + u3. 1 = u3 = 1 Vậy ta có từ mã phát đi t = ( 1 1 1 1 1 1 1 ) không có dạng mã khối tuyến tính 22 ( u0, u1, u2, u3 ) 1 1 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1   ~ ~. Gut t0 = u0. 1 + u1. 0 + u2. 1 + u3. 1 = u0 + u2 + u3 = 1 + 1 + 1 = 1 t1 = u0. 1 + u1. 1 + u2. 1 + u3. 0 = u0 + u1 + u2 = 1 + 0 + 1 = 0 t2 = u0. 0 + u1. 1 + u2. 1 + u3. 1 = u1 + u2 + u3 = 0 + 1 + 1 = 0 t3 = u0. 1 + u1. 0 + u2. 0 + u3. 0 = u0 = 1 t4 = u0. 0 + u1. 1 + u2. 0 + u3. 0 = u1 = 0 t5 = u0. 0 + u1. 0 + u2. 1 + u3. 0 = u2 = 1 t6 = u0. 0 + u1. 0 + u2. 0 + u3. 1 = u3 = 1 Vậy ta có từ mã phát đi : ( 1 0 0 1 0 1 1 ) có dạng mã khối tuyến tính 23 Ví dụ 24 • Dùng các phép đổi khác sơ cấp biển đổi các ma trận sinh sau thành ma trận sinh mạng lưới hệ thống. • Không phải mọi ma trận sinh đều hoàn toàn có thể biến hóa thành ma trận sinh mạng lưới hệ thống.               1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1 1 74G               1 1 1 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 1 1 1 0 0 1 74G Phát hiện sai và sửa sai 25 • Nguyên lý phát hiện sai : Kiểm tra xem tổng hợp nhận có phải là từ mã hay không, nếu không thì tổng hợp nhận là sai. • Nguyên lý sửa sai : Kiểm tra xem tổng hợp nhận có khoảng cách Hamming gần với từ mã nào nhất, thì đó chính là từ mã đúng đã phát đi. • → Nguyên lý khoảng cách Hamming tối thiểu.  Không gian bù trực giao : • Cho S là một khoảng trống k chiều của khoảng trống V n chiều. Gọi Sd là tập tổng thể các vectơ v trong V sao cho : • Sd được chứng tỏ là một khoảng trống con của V và có số chiều là n-k. • Sd được gọi là khoảng trống bù trừ trực giao của S và ngược lại. 0,     vuSu Cách phát hiện sai 26 • Hệ quả : • Mỗi ma trận G bất kể size ( k x n ) với k hàng độc lập tuyến tính luôn sống sót ma trận H size ( n-k ) n với ( n-k ) hàng độc lập tuyến tính sao cho G x HT = 0, trong đó HT là ma trận chuyển vị của ma trận H. • Hay : các vectơ hàng của H đều trực giao với các vectơ hàng của G. • Cách phát hiện sai : • Nếu v là một từ mã được sinh ra từ ma trận G có ma trận trực giao tương ứng là H thì : V x HT = 0 • trái lại nếu V x HT = 0 thì v là một từ mã. Ma trận kiểm tra 27 • Ma trận kiểm tra H của một bộ mã có ma trận sinh Gkxn là ma trận có kích cỡ ( n-k ) n sao cho : G x HT = 0 • Ma trận sinh mạng lưới hệ thống có dạng Gkxn = [ Ikk | Pk ( n-k ) ] thì ma trận H ( n-k ) n = [ Pk ( n-k ) T | I ( n-k ) ( n-k ) ] Trong đó : I ( n-k ) ( n-k ) là ma trận đơn vị chức năng size ( n-k ) ( n-k ), còn Pk ( n-k ) T là ma trận chuyển vị của ma trận Pk ( n-k ). Cho G không mạng lưới hệ thống, tính H ? • VD : trên Z3, cho ma trận sinh của một mã như sau • Ta chuyển thành ma trận sinh của mã mạng lưới hệ thống tương tự bằng một phép hoán vị p = ( 1,4,6,2,5,3 ) các cột về dạng [ I | B ]. • Ta tính được H * tươngứng với G * là p-1. • • Tính H bằng hoán vị ngược Thử lại : GHT = 0. 17 28 Ma trận kiểm tra 29 • Ví dụ : Tìm ma trận kiểm tra của ma trận sinh mạng lưới hệ thống sau :               1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ) 74 ( htG             1 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 ) 73 ( htH Cách sửa sai 30 Syndrome – vectơ sửa sai ( corrector )  S = v x HT được gọi là Syndrome hay vectơ sửa sai của v và được kí hiệu là s ( v ). v là từ mã khi và chỉ khi s ( v ) = 0.  Từ ma trận H ( n-k ) n thành phần của Syndrome như sau : S0 = v0p00 + v1p10 +. .. + vk-1pk-1, 0 + vk S1 = v0p01 + v1p11 +. .. + vk-1pk-1, 1 + vk + 1 … … … … …. Sn-k-1 = v0p0, n-k-1 + v1p1, n-k-1 + … + vk-1pk-1, n-k-1 + vn-1 – Gọi từ mã phát đi : t = ( t0 t1. .. . tn-1 ) ( 1 ) – Gọi từ mã thu được : r = ( r0 r1. .. . rn-1 ) ( 2 ) – Vector sai : e = ( e0 e1. .. en-1 ) ( 3 ) – Trong đó ei = 1 nếu ti  ri và ei = 0 nếu ti = ri Để phát hiện sai ta dùng thuật toán thử Syndrome : – S = r. HT = ( s0 s1. .. . sn-k-1 ) ( 4 ) gồm n-k thành phần – S = 0 nếu và chỉ nếu r là từ mã phát ( r  t ) hoặc là tổng hợp tuyến tính của các từ mã ( gọi là vector sai không phát hiện được ). – S  0 thì r không phải là từ mã phát đi ( r  t ) và do đó có sai ( e  0 ) Phương pháp giải thuật mã khối tuyến tính : 31 Từ ma trận kiểm tra thành phần của Syndrome như sau :  S0 = r0 + rn-kp00 + rn-k-1p10 +. .. + rn-ipk-1, 0  S1 = r1 + rn-kp01 + rn-k-1p11 +. .. + rn-ipk-1, 1  … … … … …. ( 5 )  Sn-k-1 = rn-k-1 + rn-kp0, n-k-1 + rn-k+ip11 +. + rn-ipk-1, n-k-1 Từ ( 5 ) tương tự như như mạch mã hóa, ta có mạch tính Syndrome như sau : Phương pháp giải thuật mã khối tuyến tính 32 Mạch tính Syndrome r0 r1 rn-k p00 + p01 + + …. pk-1, 0 Pk-1, 1 Pk-1, n-k-1 P0, n-k-1 rn-1 so s1 sn-k-1 … 33  Tính Syndrome của mã khối tuyến tính C ( 7,4 ) với ma trận H đã cho với vector thu : r = ( r0 r1 r2 r3 r4 r5 r6 ) Ví dụ : S = r. HT = ( r0 r1 r2 r3 r4 r5 r6 ) 1 0 0 0 1 0 0 0 1 1 1 0 0 1 1 1 1 1 1 0 1 = ( S0 S1 S2 ) 34  S0 = r0. 1 + r1. 0 + r2. 0 + r3. 1 + r4. 0 + r5. 1 + r6. 1 = r0 + r3 + r5 + r6  S1 = r0. 0 + r1. 1 + r2. 0 + r3. 1 + r4. 1 + r5. 1 + r6. 0 = r1 + r3 + r4 + r5  S2 = r0. 0 + r1. 0 + r2. 1 + r3. 0 + r4. 1 + r5. 1 + r6. 1 = r2 + r4 + r5 + r6 Mạch tính Syndrome của mã mạng lưới hệ thống tuyến tính C ( 7,4 ) 35  Khi xác lập được một giá trị Syndrome S = ( S0, S1. .. . Sn-k-1 ) ta có đến 2 k vector sai tương ứng, nhưng ta chỉ chọn các vector sai nào có trọng số nhỏ nhất là vector sai có nhiều năng lực nhất.  Trong thực tiễn khi tìm được Syndrome ta thấy S trùng với cột nào của ma trận kiểm tra H thì có sai ở vị trí tương ứng.  Ví dụ : “ 1 1 1 ” trùng với cột thứ sáu tính từ trái sang của ma trận H, ta Tóm lại vector nhận được r sai ở vị trí r5. Ta chỉ việc đổi trị số của r5 từ 0 sang 1 hoặc ngược lại là được vector nhận được đúng ( r = t ) r = 1 0 0 1 0 0 1  e = 0 0 0 0 0 1 0 t = 1 0 0 1 0 1 1 -> hòn đảo bit tại r5 Cách sửa sai 36 Ví dụ tính Syndrome 37 • Tính Syndrome của mã khối tuyến tính C ( 7,4 ) với ma trận sinh mạng lưới hệ thống sau : giả sử gửi tin : u = 1001. Nhận được v = 1011011. Nhận xét gì về mẫu tin nhận được.               1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ) 74 ( htG Ví dụ tính Syndrome 38 S ( v ) = v. HT = ( 111 )               1 1 1 0 0 1 1 1 1 1 0 1 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 ) 74 ( htG             1 0 0 0 1 0 0 0 1 1 0 1 1 1 1 1 1 0 0 1 1 ) 73 ( htH                         100 010 001 101 111 110 011 ) 73 ( T htH Cách sửa sai 39 • Qua ví dụ trên, ta thấy : • S ( v ) = ( 111 ) trùng với cột thứ 3 của H, nên ta sửa giá trị ở vị trí thứ 3. v  r = t 1011011  0010000 = 1001011 Vậy tin gửi đi là : 1001. Mã Hamming 40 • Với mọi số nguyên dương m  3, sống sót mã Hamming với các thông số kỹ thuật sau : Chiều dài từ mã : n = 2 m – 1. Chiều dài phần tin : k = 2 m – m – 1. Chiều dài phần kiểm tra : m = n – k Khả năng sửa sai : t = 1 • Cấu trúc ma trận kiểm tra H với các cột là một vector m chiều khác không. • H = [ Imxm | P ( n-k ) k ] • Mỗi cột của ma trận P. là vector m chiều, có trọng số là 2 hoặc lớn hơn. Ví dụ : với m = 3, ma trận kiểm tra của mã ( 7,4 ) được viết dưới dạng ( 1 ) Trong trong thực tiễn để việc tạo và giải thuật Hamming một cách đơn thuần người ta đổi vị trí các cột trong ma trận H. Khi đó các bit kiểm tra xen kẽ với các bit mang tin chứ không còn đặc thù khối, từ ( 1 ) ta có : ( 2 ) H ( 3,7 ) = 1 0 0 1 0 1 1 0 1 0 1 1 1 0 0 0 1 0 1 1 1 H = 0 0 0 1 1 1 1 0 1 1 0 0 1 1 1 0 1 0 1 0 1 41 Để việc tạo mã đơn thuần ta chọn các bit kiểm tra x, y, z ở các vị trí tương ứng 2 i với i = 0, 1, 2 ,. .., nghĩa là các vị trí thứ nhất, thứ hai và thứ tư của các ký hiệu từ mã : t = ( x, y, u0, z, u1, u2, u3 ) ( 3 ) Tạo mã : t. HT = ( x, y, u0, z, u1, u2, u3 ) x 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 = 0 42 t = ( x, y, u0, z, u1, u2, u3 ) ( 2 ) x. 0 + y. 0 + u0. 0 + z. 1 + u1. 1 + u2. 1 + u3. 1 = 0  z = u1 + u2 + u3 x. 0 + y. 1 + u0. 1 + z. 1 + u1. 0 + u2. 1 + u3. 1 = 0  y = u0 + u2 + u3 x. 1 + y. 0 + u0. 1 + z. 1 + u1. 1 + u2. 0 + u3. 1 = 0  x = u0 + u1 + u3 43 Tin cần phát đi : U = ( u0, u1, u2, u3 ) = ( 1 0 1 1 ) x = u0 + u1 + u3 = 1 + 0 + 1 = 0 y = u0 + u2 + u3 = 1 + 1 + 1 = 1 z = u1 + u2 + u3 = 0 + 1 + 1 = 0  Vậy từ mã phát đi sẽ là : t = ( 0 1 1 0 0 1 1 ) không có dạng mã khối. Giải mã Haming cũng giống như giải thuật khối tuyến tính nhưng đơn thuần hơn nhờ sử dụng ma trận kiểm tra H có dạng 2. Khi đó việc xác lập vị trí ký hiệu sai tương đối thuận tiện. Ví dụ : 44 Mã Hamming ( tt ) 45 • Ví dụ : Với m = 3, ta có ma trận kiểm tra của bộ mã C ( 7,4 ) như sau :             1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 0 1 0 0 0 1 73H Mã Hamming ( tt ) 46 • Trong thực tiễn để việc tạo và giải thuật Hamming một cách đơn thuần người ta đổi vị trí các cột trong ma trận H. Khi đó các bit kiểm tra xen kẽ với các bit mang tin chứ không còn đặc thù khối. Và giá trị của cột hi khi này bằng i ( i = 1,2, … ) • Vị trí các bit kiểm tra ở các vị trí tương ứng 2 i, với i = 0,1,2, … Ứng với các vị trí tương ứng của từ mã.  c = ( x, y, u0, z, u1, u2, u3 )             1 1 1 0 1 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 0 73H Tạo mã 47 • Theo đặc thù mã khối tuyến tính ta có : c. HT = 0  ( x, y, u0, z, u1, u2, u3 ) x = 0.  x = u0 + u1 + u3  y = u0 + u2 + u3  z = u1 + u2 + u3                       111 011 101 001 110 010 100 Tạo mã 48 • Với tin cần phát : u = 1011 • x = u0 + u1 + u3 = 1 + 0 + 1 = 0 • y = u0 + u2 + u3 = 1 + 1 + 1 = 1 • z = u1 + u2 + u3 = 0 + 1 + 1 = 0 • Vậy từ mã phát đi : c = 0110011 Giải mã 49 • Cách giải thuật giống với giải thuật, phát hiện lỗi sai và sửa lỗi của mã khối tuyến tính. • Tính Syndrome – vectơ sửa sai • S ( v ) = v. HT • Nếu S ( v ) khác 0, ta xem giá trị s ( v ) trùng với cột thứ mấy của ma trận H, thì có sai ở vị trí đó, và sửa lỗi. Giải mã 50 • Với từ mã thu được v = 0 0 1 1 0 1 1 • S ( v ) = v x HT = 110. Trùng với cột thứ 6 của ma trận H. Có nghĩa ký hiệu sai là ký hiệu thứ 6. 

Source: https://thomaygiat.com
Category : Kỹ Thuật Số