Mã vòng – Cyclic codes

Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 1 Mã vòng – Cyclic codes I/ Mô tả Mã vòng (Cyclic Codes) là một họ mã có ứng dụng đặc biệt rộng rãi trong thông tin. Mã có tên gọi là cyclic vì do có đặc tính dịch vòng của một từ mã cũng là một từ mã. Mã vòng (hay mã chu kỳ) còn được gọi một lớp con quan trọng của mã tuyến tính. Mã này đáng chú ý vì hai lý do sau đây: - Mạch mã hoá và tính syndrome (hội chứng) có thể được thực hiện dễ dàng nhờ bộ ghi dịch có hồi tiếp (feedback connection). - Nhờ cấu trúc của mã có thể tìm được nhiều phương pháp để giải mã. Định nghĩa: Một mã tuyến tính C(n, k) được coi là mã vòng nếu mỗi lần dịch vòng một từ mã của C thì kết quả cũng là một mã véc tơ của C. Cho véc tơ mã v = (v0,v1,...vn-1), các thành phần của véc tơ mã này có thể xem như là hệ số của đa thức v(x): v(x) = v0 + v1x + ... + vn-1x n-1 . Vậy mỗi véc tơ mã v có chiều dài n tương ứng với đa thức mã v(x) có bậc nhỏ hơn hoặc bằng n-1. Nếu vn-1 ạ 0 thì bậc của v(x) là n-1, nếu vn-1 = 0 thì bậc của v(x) nhỏ hơn vn- 1. Sự tương đương giữa véc tơ mã v và đa thức mã v(x) là 1-1, v(x) được gọi là đa thức mã (code polynomial) của véc tơ mã v. Khi đó từ véc tơ mã và từ đa thức mã được sử dụng như nhau. Ví dụ: Mã tuyến tính ở bảng 1 được goi là mã vòng Khối tin Véc tơ mã: v Đa thức mã v(x) (0000) (0000000) 0 = 0.g(x) (1000) (1101000) 1 + x +x3 = g(x) (0100) (0110100) x + x2 + x4 = x.g(x) (1100) (1011100) 1 + x2 + x3 + x4 = (1 + x).g(x) (0010) (0011010) x2 + x3 + x5 = x2.g(x) (1010) (1110010) 1 + x + x2 + x5 = (1 + x + x2).g(x) (0110) (0101110) x + x3 + x4 +x5 = (1 +x + x2).g(x) (1110) (1000110) x3 + x4 + x6 = x3.g(x) (0001) (0001101) 1 + x + x4 + x6 = (1 + x3).g(x) (1001) (1100101) x + x2 + x3 + x6 = (x + x3).g(x) (0101) (0111001) x + x2 + x6 = (1 + x + x3).g(x) (1101) (1010001) 1 + x2 + x6 = (1+ x + x3).g(x) Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 2 (0011) (0010111) x2 + x4 + x5 + x6 = (x2 + x3).g(x) (1011) (1111111) 1 + x + x2 + x3 + x4 + x5 + x6 = (1 + x2 + x3).g(x) (0111) (0100011) x + x5 + x6 = (x + x2 + x3).g(x) (1111) (1001011) 1 + x3 + x5 + x6 = (1 + x + x2 + x3).g(x) Bảng 1: Mã vòng với đa thức sinh g(x) = 1 + x + x3 Một số tính chất đại số quan trọng của mã vòng: Định lý 1: Đa thức mã khác 0 có bậc nhỏ nhất của mã vòng là duy nhất. Định lý 2: Nếu g(x) = g0 + g1x + ... + gr-1x r-1 + xr là đa thức mã nhỏ nhất của mã vòng C(n, k) thì hệ số g0 bắt buộc phải bằng 1. Định lý 3: Cho g(x) = 1 + g1x + g2x 2 + ... + xr là đa thức mã khác 0 có bậc nhỏ nhất của mã vòng C(n, k), một đa thức nhị phân có bậc nhỏ hơn hoặc bằng n-1 là đa thức mã nếu và chỉ nếu nó là bội của g(x). Định lý 4: Cho mã vòng C(n,k), tồn tại một và chỉ một đa thức mã có bậc n - k: g(x) = 1 + g1x + g2x 2 + ... + gn-k-1x n-k-1 + xn-k. Định lý 5: Đa thức sinh g(x) của một mã vòng C(n,k) là một thừa số của xn+1. Định lý 6: Nếu g(x) là đa thức bậc (n-k) và là một thừa số của xn+1 thì g(x) sinh ra mã vòng C(n, k). Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 3 II/ Ma trận sinh và ma trận kiểm tra của mã vòng. Gọi g(x) là đa thức sinh bậc n-k của mã vòng C(n,k). Một khối dữ liệu k phần tử (m0, m1,... mk-1) có thể được xem là một đa thức thông tin: m(x) = m0 + m1x + ... + mk-1x k-1. Việc mã hoá thông qua việc nhân đa thức thông tin với đa thức sinh. Kết quả ta có: Cm = (c0, c1, ... cn-1) Cm(x) = m(x).g(x) = c0 + c1.x + ... + cn-1.x n-1 Tích đa thức trên được biểu diễn dưới dạng tích ma trận như: Cm(x) = m(x).g(x) = (m0 + m1.x + ... + mk-1.x k-1).g(x) = m0.g(x) + m1.x.g(x) + ... + mk-1.x k-1.g(x) g(x) x.g(x) = [m0 + m1.x + ... + mk-1.x k-1]. . . xk-1.g(x) Dạng tổng quát của ma trận sinh G của mã vòng C(n,k) là: g0 g1 g2 ... ... ... ... gn-k 0 0 ... 0 0 g0 g1 ... ... ... ... ... gn-k 0 ... 0 G = 0 0 g0 gn-k ... 0 .. .. .. .. .. .. .. .. .. .. .. .. 0 0 0 .. 0 g0 gn-k ( với g0 = gn-k = 1) Trường hợp tổng quát G không có dạng hệ thống. Tuy nhiên có thể chuyển G về dạng hệ thống bằng phép biến đổi hàng của ma trận. Ví dụ: Xét mã vòng C(7, 4) cho ở bảng 1 với đa thức sinh g(x) = 1 + x + x3 có ma trận như sau: 1 1 0 1 0 0 0 G = 0 1 1 0 1 0 0 0 0 1 1 0 1 0 0 0 0 1 1 0 1 Ta thấy G không có dạng hệ thống. Nhưng nếu dùng phép biến đổi hàng: h3 = h3 + h1 và h4 = h4 + h1 + h2 ta thu được Ma trận G’ có dạng hệ thống như sau: Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 4 1 1 0 1 0 0 0 G’ = 0 1 1 0 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 0 1 Với g(x) là thừa số của xn + 1, có: xn + 1 = g(x).h(x) Với đa thức h(x) có bậc là k được biểu diễn như sau: h(x) = h0 + h1.x + ... + hk.x k, (với h0 = hk = 1) Cho v = (v0, v1,... vn-1) là véc tơ mã của C. Khi đó v(x) = m(x).g(x). Nhân v(x) với h(x) ta được: v(x).h(x) = a(x).g(x).h(x) = a(x).(xn + 1) = a(x) + xn.a(x) Do bậc của v(x) nhỏ hơn hoặc bằng k-1 nên các giá trị của xk, xk+1, ...xn-1 không có trong biểu thức m(x) + xk.m(x). Nếu khai triển kết quả v(x).h(x) thì hệ số xk, xk+1,... xn phải bằng 0. Do đó nhận được n-k phương trình sau: ồhivn-i-j = 0, với i Ê j Ê n-k. Hàm số ngược của h(x) là: x k.h(x-1) = hk + hk-1x + hk-2x 2 + ... + h0x k Dễ dàng nhận thấy rằng xkh(x-1) cũng là thừa số của (xn + 1). Vậy đa thức sinh xkh(x-1) sinh ra mã vòng (n,n-k) với ma trận H(n-k) x n là ma trận sinh: h k hk-1 hk-2 ..... h0 0 .... 0 0 hk hk-1 hk-2 ... h0 .... 0 H = 0 0 hk hk-1 hk-2 .... h0... 0 ... 0 0 ...0 hk hk-1 hk-2 ... h0 Bất kỳ véc tơ mã nào của C đều trực giao với mỗi hàng của H. Do đó H là ma trận kiểm tra chẵn lẻ của mã vòng C. Do H nhận được tù đa thức h(x) nên h(x) được gọi là đa thức kiểm tra của C. Định lý 7: Gọi C là mã vòng (n,k) với đa thức sinh g(x). Mã đối ngẫu của C cũng là mã vòng và được sinh ra bởi đa thức: xk.h(x-1) với h(x) = (xn + 1)/g(x). Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 5 III/ Mã hoá mã vòng Mã hoá mã vòng (n,k) dạng hệ thống gồm ba bước: Bước 1: Nhân đa thức thông tin u(x) với xn-k. Bước 2: Chia xn-k.u(x) cho g(x) nhận được phần dư b(x). Bước 3: Hình thành từ mã b(x) + xn-k.u(x). Tất cả ba bước này có thể thực hiện bằng mạch chia với thanh ghi dịch n-k tầng có hàm hồi tiếp tương ứng với đa thức sinh g(x): g(x) = 1 + g1x + g2x 2 +... + gn-k-1x n-k-1 + xn-k. Sơ đồ mã hoá được chỉ trong hình 1 Quy ước: Là một khâu của thanh ghi dịch (flip-flop) Cổng cộng modul-2 (XOR) Mối liên kết (g = 0: không có sự liên kết, g = 1 có sự liên kết) Hình 1: Mạch mã hoá vòng (n,k) với đa thức sinh: g(x) = 1 + g1.x + g2.x 2 + ... + gn-k-1.x n-k-1 + xn-k Các bước tạo mã dùng đa thức sinh như sau: Bước 1: Cổng đóng (cho thông tin qua), k chữ số thông tin: u0, u1,... uk-1 (hay ở dạng đa thức là: u(x) = u0 + u1x + u2x 2 + ... + uk-1x k-1) được dịch vào mạng và đòng thời nối vào kênh truyền. Dịch thông tin u(x) vào mạch từ thiết bị đầu cuối để nhân trước u(x) với xn-k. Ngay sau khi thông tin được đưa vào mạch thì n - k chữ số còn lại trong thanh ghi là những số kiểm tra chẵn lẻ. b0 bn-k-1 b2 b1 Cổng g0=1 g1 g2 gn-k-1 Thông tin xn-k.u(x) Các số kiểm tra chẵn lẻ Từ mã Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 6 Bước 2: Cắt đứt đường hồi tiếp bằng cách điều khiển cho các cổng gi (hở không cho thông tin qua). Bước 3: Dịch những con số kiểm tra chẵn lẻ và đưa ra đường truyền. Các chữ số kiểm tra này kết hợp với k chưc số thông tin tạo thành véc tơ mã. Ví dụ: Xét một mạch mã hoá mã vòng (7,4) với đa thức sinh g(x) = 1 + x + x3 như hình 2 Hình 2: Mạch mã hoá mã vòng (n = 7, k = 4) với đa thức sinh g(x) = 1 + x + x3 Việc mã hoá mã vòng cũng có thể thực hiện bằng cách sử dụng đa thức kiểm tra chẵn lẻ h(x) = h0 + h1.x + ... + hk.x k. Có thể coi công thức: Vn-k-j = ồhivn-i-j = 0 , với i Ê j Ê n-k là luật để xác định n-k chữ số kiểm tra chẵn lẻ v0, v1,... vn-k-1. Hình 3 là mạch mã hoá có hệ số h(x) là các kết nối hồi tiếp. Nguyên lý hoạt động của mạch và các bước mã hóa dùng đa thức kiểm tra như sau: Bước 1: Cổng 1 đóng, cổng 2 hở, k chữ số thông tin u(x) = u0 + u1x + ... +uk-1x k-1 được dịch vào thanh ghi đồng thời truyền ra kênh thông tin. Bước 2: Ngay sau khi toàn bộ các chữ số thông tin được dịch vào thanh ghi. Cổng 1 hở, cổng 2 đóng, chữ số kiểm tra đầu tiên là: Vn-k-1 = h0.vn-1 + h1.vn-2 + ... + hk-1.vn-k uk-1 + h1.uk-2 + ...+ hk-1.u0 Vn-k-1 được tạo thành và xuất hiện tại điểm P. Bước 3: Thanh ghi dịch vòng một bit, chữ số kiểm tra được dịch vào kênh thông tin và đồng thời cũng dịch vào thannh ghi, chữ số kiểm tra thứ hai là: Vn-k-2 = h0.vn-2 + h1.vn-3 + .... + hk-1.vn-k = uk-2 + h1.uk-3 + ... + hk-2.u0 + hk-1.un-k-1. Vn-k-2 được tạo thành và xuất hiện tại diểm P. Các số kiểm tra chẵn lẻ b0 b2 b1 Cổng g0=1 g1 Thông tin xn-k.u(x) Từ mã Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 7 Bước 4: Lặp lại bước 3 cho đến khi n-k chữ số kiểm tra được tạo ra và dịch vào kênh thông tin. Hình 3: Mạch mã hoá mã vòng (n, k) dựa vào đa thức kiểm tra h(x) = 1 + h1.x + ... + x k Để minh hoạ, xét ví dụ sau: Hình 4 là sơ đồ mã hoá cho mã vòng (7,4) có đa thức sinh g(x) = 1 + x + x3 dựa vào đa thức kiểm tra: h(x) = x7/1 + x + x3 = 1 + x + x2 + x4 Mỗi từ mã có dạng v = (v0, v1, v2, v3, v4, v5, v6) với v3, v4, v5, v6 là những con số của thông tin, còn v0, v1, v2 là những con số kiểm tra chẵn lẻ (parity), phương trình xác định bởi những con số kiểm tra là: V3-j = 1.v7-j + 1.v6-j + 1.v5-j + 0.v4-j = v7-j + v6-j + v5-j, với 1 Ê j Ê 3 Giả sử thông tin cần mã hoá là (1011) thì: v3 = 1, v4 = 0, v5 = 1, v6 = 1. Chữ số kiểm tra đầu tiên là: v2 = v6 + v5 + v4 = 1 + 1 + 0 = 0 Chữ số kiểm tra thứ hai là: v1 = v5 + v4 + v3 = 1 + 0 + 1 Chữ số kiểm tra thứ ba là: v0 = v4 + v3 + v2 = 0 + 1 + 0 = 1 Vì vậy từ mã tương ứng với thông tin (1011) là (1001011) Hình 4: Mạch mã hoá vòng (n=7, k=4) dựa vào đa thức kiểm tra h(x) = 1 + x + x2 + x4 Cổng1 Cổng2 Vn-k Vn-2 Vn-(k-1) Vn-1 hk-1 hk-2 h2 h0 h0=1 Đầu vào P Đầu ra: Vn-k-1, Vn-k-2,.. Cổng1 Cổng2 h0=1 Đầu vào P Đầu ra: 1001011 h2=1 h1=1 Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 8 IV/ Giải mã vòng Việc giải mã vòng bao gồm ba bước như việc giải mã khối tuyến tính: Bước 1: Tính Syndrome. Bước 2: Dựa vào syndrome để xác định véctơ lỗi. Bước 3: Sửa lỗi, thực hiện phép cộng modul-2 giữa véctơ lỗi và véctơ nhận được. Kết quả là véctơ thông tin thực sự được truyền đi. Nếu sửa tuần tự từng bit một thì chỉ cần một cổng XOR. Ngược lại nếu thực hiện một cách sửa song song thì phải dùng n cổng XOR. Cấu trúc mã vòng cho phép giải mã véctơ nhận r(x) = r0 + r1x + r2x 2+ .... + rn-1x n-1 một cách tuần tự. Những bit nhận được sẽ được giải mã lần lượt bởi cùng một mạch giải mã. Ngay sau khi tính syndrom. Mạch giải mã kiểm tra sự tương ứng của syndrome s(x) với véctơ sửa được e(x) = e0 + e1x + e2x 2 +... +en-1x n-1 với một lỗi sai ở vị trí cao nhất xn-1 (en-1 = 1). Nếu s(x) không có sai ở vị trí bậc cao nhất (en-1ạ0) thì lưu giữ trong thanh ghi đệm (buffer register) và đồng thời thanh ghi sundrome dịch đi một lần. Bằng cách này, r(1)(x) = r0x + r1x 2 + ... + rn-2x n-1 và đa thức syndrome mới của r(1)(x) là s(1)(x). Lúc đó bit thứ hai rn-2 của r(x) trở thành bit thứ nhất của r (1)(x). Mạch giải mã tương tự sẽ kiểm tra s(i)(x) có tương đương với véctơ sai số với lỗi tại vị trí xn-1 hay không. Nếu syndrome s(x) của r(x) tương ứng với một véctơ sai với lỗi sai ở vị trí xn-1 thì bit đầu tiên nhận được rn-1 là bit sai và nó phải được sửa cho đúng. Việc sửa sau được thực hiện qua việc tính tổng rn-1Åen-1. Đa thức sửa lỗi là: r1(x) = r0 + r1x + r2x 2 + ... + rn-2x n-1 + (rn-1Åen-1)x n-1. Sau đó lỗi sai ở bit en-1 được xoá bỏ khỏi syndrome s(x). Việc này thực hiện bằng việc cộng modul syndrome của e’(x) = xn-1 với s(x). Kết quả cộng này là đa thức đã sửa sai r1(x). Tiếp theo dịch vòng r1(x) và đồng thời dịch vòng thanh ghi syndrome. Kết quả việc dịch vòng thu được r1 (1)(x) = (rn-1Åen-1) + r0x + ...+ rn-2x n-1 Vì thế nếu 1 được thêm vào tận cùngbên trái của thanh ghi sundrome trong khi dịch vòng thì thu được s1 (1)(x). Mạch giải mã bắt đầu giải những bit nhận được rn-2. Việc giải mã rn-2 và các loại bit còn lại đều được tính giống như giải mã rn-1. Khi một lỗi được phát hiện và sửa, nó sẽ là cho syndrome thay đổi. Quá trình giải mã sẽ ngừng sau n lần dịch vòng. Nếu e(x) là véctơ lỗi đã được sửa thì thanh ghi syndrome sẽ bằng 0. Kết thúc quá tringhf giải mã sẽ nhận được r(x) được giải mã chính xác. Nếu kết thúc quá trình giải mã mà syndrome khác 0 thì lỗi sai được phát hiện và không sửa sai được. Bộ giải mã vòng (n,k) có sơ đồ như hình 5 gồm các khối: Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 9 - Thanh ghi syndrome. - Bộ phát hiện véctơ lỗi. - Thanh ghi đệm lưu giữ véctơ nhận. Hình 5: Bộ mã vòng với đa thức nhận được ở đầu thu r(x) được dịch vào thanh ghi syndrome từ bên trái. Thủ tục sửa lỗi được mô tả như sau: Bước 1: Syndrome được tạo ra bằng cách dich toàn bộ véctơ nhận vào thanh ghi syndrome và thanh ghi dệm. Bước 2: Bộ phát hiện sai là mạch logic được thiết kế sao cho đầu ra của nó là 1 khi và chỉ khi syndrome trong thanh ghi syndrome tương ứng với véctơ sai có thể sửa được một lỗi tại bit bậc cao nhất xn-1. Do đó nếu bit 1 xuất hiện ở đầu ra của mạch phát hiện sai thì bit nhận được là bit sai phải sửa, nếu bit 0 xuất hiện thì bit nhận được là đúng là không phải sửa. Bước 3: Bit đầu tiên được dịch ra khỏi thanh ghi đệm. Cùng lúc đó thanh ghi syndrome cũng dịch một bit. Nếu ký hiệu vừa đọc ra là sai thì sẽ được sửa và ở đầu ra sẽ nhận được ký hiệu đúng. Đầu ra ở mạch phát hiện sai cũng được mắc hồi tiếp vào thanh ghi syndrome. Kết quả có một syndrome tương ứng với véctơ nhận đã dịch về bên phải. Bước 4: Syndrome mới nhận được ở bước 3 sẽ dùng để phát hiện sai ở ký hiệu kế tiếp sắp được đọc ra khỏi thanh ghi đệm. Mạch giải mã lặp lại ở bước 2 và 3. Bước 5: Mạch giải mã sẽ giải mã lần lượt từng ký hiệu theo cách trên cho đến khi toàn bộ véctơ nhận r được đọc ra khỏi thanh ghi đệm. Sau khi toàn bộ véctơ r đọc ra khỏi thanh ghi đệm: nếu thanh ghi syndrome chứa toàn 0 nghĩa là véctơ lỗi được phát hiện và sửa đúng. Cổng1 Cổng2 Thanh ghi syndrome Thanh ghi dệm Cổng ei Véctơ được sửa sai Cổng r1 Cổng1 Thanh ghi syndrome Chỉnh syndrome Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 10 Ví dụ: Cho mã vòng (7, 4) với ma trận sinh g(x) = 1 + x + x3. Mã này có khoảng cách Hamming nhỏ nhất là 3 và do vậy có khả năng sửa lỗi đơn. Giả sử chuỗi nhận r(x) = r0 + r1x + r2x 2 + r3x 3 + r4x 4 + r5x 5 + r6x 6 được dịch vào thanh ghi syndrome từ sang trái. Bảng véctơ lỗi và các syndrome tương ứng của chúng được kê ở bảng 2: Véctơ lỗi e(x) Syndrome s(x) Véctơ syndrome (s0, s1, s2) e6(x) = x 6 e5(x) = x 5 e4(x) = x 4 e3(x) = x 3 e2(x) = x 2 e1(x) = x 1 e0(x) = x 0 s(x) = 1 + x2 s(x) = 1 + x + x2 s(x) = x + x2 s(x) = 1 + x s(x) = x2 s(x) = x s(x) = 1 101 111 011 110 001 010 100 Bảng 2: Véc tơ lỗi và các syndrome tương ứng với đa thức nhận được chuyển vào thanh ghi syndrome từ trái sang phải. Syndrome s(x) được tính bằng cách lấy phần dư cảu phép chia xi cho g(x). Từ đó suy ra véctơ syndrome tương ứng. Giả sử rằng một lỗi đơn xuất hiện ở vị trí xi. Sau khi chuỗi nhập được dịc vào thanh ghi syndrome. Syndrome trong danh sách ghi sẽ là (101). Tuy nhiên sau (6-i) lần dịch thì nội dung của thanh ghi không phải là (101). Vì thế cần sửa lỗi syndrome (101). Một mạch giải mã hoàn chỉnh được vẽ như hình 6: Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 11 Hình 6: Mạch giải mã cho mã vòng (7,4) với đa thức sinh g(x) = 1 + x + x2 Miêu tả quá trình giải mã như sau: Giả sử véctơ mã v = (1001011) được truyền thành véctơ nhận r = (1011011). Mỗi lỗi đơn xuất hiện ở vị trí x2. Khi nhập được dịch vào thanh ghi đệm và thanh ghi syndrome. Thanh ghi syndrome chứa giá trị (001). ậ hình dưới đây là mô tả quá trình ghi dịch trên các thanh ghi đệm và thanh ghi syndrome. Sau 4 lần dịch nội dung của thanh ghi syndrome là (101) và mẫu lỗi r2 sẽ là số kế tiếp xuất khỏi thanh ghi đệm. Nhược điểm của mạch giải mã hình 6 là thời gian giải mã lâu do phải dịch vòng từng bit một. Bộ giải mã như trên được gọi là bộ giải mã Meggit. ở bộ giải mã này từ mã được đưa vào vị trí bậc cao nhất đến vị trí thấp nhất và khi dịch vòng cả thanh ghi đệm và thanh ghi syndrome đêù dịch vòng sang phải: Bộ giải mã Meggit cũng có thể giải mã ngược, nghĩa là nó sẽ giải mã từ vị trí bậc thấp nhất đến bậc cao nhất. Khi đó, thanh ghi đệm và thanh ghi syndrome sẽ dịch sang trái. Bộ dồn kênh Cổng Đầu ra r(x) Cổng Cổng Đầu vào Mã vòng Hoàng Chiến Thắng - ĐHKTCN Thái Nguyên Email: [email protected] 12 Quá trình sửa sai của mạch được mô tả như trên hình vẽ dưỡi đây: Về nguyên tắc, phương pháp giải mã Meggit có thể áp dụng với bất kỳ mã nào, nhưng trong thực tế mạch giải mã rất phức tạp vì vậy còn nhiều phương pháp giải mã khác đã được phát minh, chúng là các dạng biến thể từ phương pháp giải mã Meggit như là: giải mã bằng phương pháp bẫy lỗi, phương pháp giải mã bẫy lỗi cải tiến... tuỳ theo từng trường hợp cụ thể mà có thể sử dụng một mạch giải mã hoặc kết hợp nhiều mạch giải mã nhằm đảm bảo tốt yêu cầu của từng nhiệm vụ đặt ra. 0 0 1 1 0 1 1 0 1 1 Bắt đầu 0 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 1 1 0 1 1 0 Lần dịch Thứ 2 0 1 1 1 0 1 1 1 0 1 1 Lần dịch Thứ 3 0 1 0 1 1 0 1 1 1 0 1 Lần dịch Thứ 4 0 0 0 0 0 1 0 1 1 1 0 Lần dịch Thứ 5 0 0 0 0 0 0 1 0 1 1 1 Lần dịch Thứ 6 0 0 0 0 1 0 0 1 0 1 1 Lần dịch Thứ7 0 Lần dịch Thứ1