- Mã hóa kênh. - Mã chập Mã hóa điều khiển lỗi. - Từ mã n bit được tạo ra duy nhất từ k bit tin và (n-k) là số bit kiểm tra dư. - Mã hệ thống (systematic code) là mã có mặt các bit tin cùng với các bit dư trong từ mã. - Định nghĩa ít nghiêm ngặt hơn thì chỉ yêu cầu trong từ mã có mặt các bit tin chứ không cần phải nằm liên tục thành khối.. - Bộ mã hóa khối n bit. - mã hóa k. - Từ mã n bit. - Hình 5.2 Mã khối hệ thống (n, k). - có các từ mã có tương ứng 1-1 với các phần tử thuộc nhóm toán học. - Mã tuyến tính có chứa từ mã gồm toàn số 0 và có tính chất đóng, chẳng hạn đối với mã tuyến tính nhị phân, với hai từ mã và bất kỳ, ta luôn có , cũng là một từ mã. - Việc có chứa từ mã gồm toàn số 0 và tính chất đóng làm cho việc tính toán đối với mã tuyến tính đặc biệt dễ. - Mã hóa. - Mã vòng (cyclic code) là một lớp con của mã khối tuyến tính không có từ mã gồm toàn số 0.. - Một mã khối tuyến tính được gọi là mã vòng nếu sau một lần dịch vòng một từ mã thì cũng được một từ mã thuộc cùng bộ mã. - Ví dụ các từ mã sau đây được gọi là mã vòng:. - Mã Golay (23, 12) có khả năng sửa được 3 lỗi cho từ mã dài 23 bit. - thể sửa được t lỗi trong từ mã dài n bit, với . - Ví dụ mã. - b) Mã chập. - 5.1.3 Khả năng phát hiện và sửa lỗi của mã khối. - Lý thuyết mã đã chứng minh rằng: khoảng cách Hamming giữa các từ mã trong một bộ mã có liên quan đến khả năng phát hiện sai và sửa sai của bộ mã đó, cụ thể là:. - M có 8 từ mã như sau:. - Ký tự A B C D E F G H. - Từ mã . - Nếu chọn từ mã B (001) làm từ mã xuất phát thì bộ mã M 1 bao gồm 4 từ mã sau:. - Gọi 4 từ mã trên là từ mã dùng và 4 từ mã còn lại là từ mã cấm.. - Trong trường hợp sai 1 lỗi, rõ ràng các từ mã dùng được truyền đi sẽ chuyển thành các từ mã cấm bên thu. - Lúc này có thể dễ dàng phát hiện được lỗi. - Nếu bên thu nhận được từ mã là A, có thể kết luận là từ mã truyền đi bị lỗi nhưng không thể kết luận được từ mã nào (B, C hay E) đã truyền đi. - Nói cách khác, khi số trường hợp sai nhiều hơn số từ mã cấm thì không thể phát hiện được lỗi. - Trong trường hợp sai 2 lỗi, ta thấy từ mã dùng này sẽ chuyển thành từ mã dùng khác nên không thể phát hiện được lỗi.. - Nếu chọn từ mã B (001) làm từ mã xuất phát thì bộ mã M 2 bao gồm 2 từ mã sau:. - Từ mã 001 110. - không trùng nhau và bằng sốú từ mã cấm nên có thể sửa được lỗi. - Trong trường hợp sai 2 lỗi, ta thấy từ mã dùng chuyển thành từ mã cấm nhưng trùng với từ mã cấm trong trường hợp sai 1 lỗi chỉ phát hiện được lỗi chứ không sửa được lỗi.. - Cũng qua ví dụ trên về bộ mã M 2 ta thấy rằng: với số lượng từ mã trong bộ mã là 2 thực sự trong mỗi từ mã chỉ có 1 bit tin. - Nhưng ở đây chiều dài từ mã là 3. - Phần sau ta sẽ xét tổng quát về mối quan hệ giữa độ dài tổng cộng của từ mã và số bit tin.. - b) Mối quan hệ giữa độ dài tổng cộng của từ mã và số bit tin. - Để tìm ra mối quan hệ giữa độ dài tổng cộng của từ mã và số bit tin, trước hết ta đưa ra khái niệm vector lỗi e. - Vector lỗi là vector biểu diễn vị trí các bit lỗi xuất hiện trong từ mã thu, qui ước bit không lỗi được biểu diễn là 0 và bit lỗi được biểu diễn là 1.. - Ví dụ từ mã phát là 1110010 và từ mã thu là 1100110. - Lúc này vector lỗi là e = 0010100 Gọi độ dài tổng cộng của từ mã là: n. - suy ra số từ mã tổng cộng là: 2 n. - Gọi số bit tin trong từ mã là : k. - suy ra số từ mã dùng là: 2 k Vậy số từ mã cấm là: 2 n - 2 k. - Với mỗi từ mã dùng truyền đi thì tối đa có thể xảy ra E trường hợp lỗi. - Vậy với số từ mã dùng là 2 k thì tối đa có thể xảy ra Ex2 k trường hợp lỗi. - Để có thể phát hiện và sửa hết tất cả các lỗi này thì yêu cầu mỗi trường hợp sai phải chuyển từ mã dùng sang một từ mã cấm khác nhau, nói cách khác, số trường hợp sai không được vượt quá số lượng từ mã cấm, nghĩa là:. - Dùng mã parity lẻ sẽ tránh được trường hợp truyền từ mã gồm toàn số 0, tuy nhiên, mã parity chẵn lại được dùng phổ biến hơn.. - Hình 5.4 Ví dụ mã parity. - Giả sử dùng P chẵn, các từ mã mang tin là 7 bit từ 0000000 đến 1111111, các từ mã liên tiếp trong bộ mã này sẽ là:. - Hình 5.6 Ví dụ kiểm tra tổng modulo-2. - Hình 5.7 Ví dụ kiểm tra tổng bù 1. - Nhờ ma trận sinh G, ta có thể tính toán được từ mã bằng cách nhân vector hàng m biểu diễn. - cho từ mã mang tin với G. - Trong ví dụ trên, dãy mang tin là 1011, từ mã khối tuyến tính (4,7) được tạo ra là:. - Ta nhận thấy ma trận kết quả chính là vector biểu diễn cho từ mã khối (4, 7) gồm có hai phần: 4 bit bên trái là 4 bit tin I 1 đến I 4 , 3 bit bên phải chính là 3 bit kiểm tra P 1 đến P 3 . - Syndrome là một từ mã độc lập với từ mã phát và chỉ phụ thuộc vào dãy thu bị lỗi, ký hiệu vector syndrome là s. - Gọi c là vector biểu diễn cho từ mã khối (n, k. - Gọi e là vector lỗi và r là từ mã thu, ta có:. - Bảng syndrome được tính sẵn với giả thiết là truyền đi từ mã gồm toàn bit 0. - Ví dụ trên, giả sử thu được từ mã 1011101, từ mã đúng sửa được sẽ là c như sau:. - Như đã giới thiệu ở trên (5.1.2), mã vòng là một lớp con của mã khối tuyến tính. - Dịch vòng một từ mã cũng được một từ mã thuộc cùng bộ mã.. - Có thể tạo ra từ mã vòng bằng cách nhân modulo-2 vector mang tin với đa thức sinh. - Đặt là đa thức biểu diễn cho từ mã CRC phát. - Rõ ràng là nếu không có lỗi xuất hiện thì bên thu, sau khi chia từ mã thu cho đa thức sinh ta sẽ được phần dư là 0.. - b) Ví dụ. - Từ mã CRC được tạo ra như hình 5.10 sau:. - Sau khi thực hiện tính toán như trên, ta tìm được từ mã CRC là trong đó 8 bit đầu là 8 bit tin và 4 bit sau là 4 bit kiểm tra.. - Giả sử tại bên thu, ta thu được từ mã . - Dư ≠ 0 nên phát hiện được lỗi. - Hình 5.11 Ví dụ giải mã CRC và phát hiện lỗi. - Ví dụ k = 4, n = 7. - Ví dụ:. - Gọi T'(x) là đa thức biểu diễn cho từ mã thu. - Thực hiện mã hóa ta được từ mã phát là 1100 101. - Giả sử bên thu thu được từ mã 1110 101. - Thực hiện phép cộng modulo ta được 0101110, rồi dịch vòng sang phải 3 lần ta được lại từ mã 1100101 giống như bên phát.. - Một từ mã Hamming được biểu diễn dưới dạng tổng quát . - Ví dụ xét khả năng sửa lỗi đơn của mã Hamming (7, 11) trong trường hợp từ mã mang tin là 1011101.. - Từ mã Hamming có dạng: c c 1 c 011 c 101. - Vậy từ mã Hamming phát đi là . - Giả sử ở bên thu, thu được từ mã . - Vậy từ mã thu được sửa lại là giống như từ mã phát.. - 5.4 Mã chập. - 5.4.1 Mã hóa mã chập. - Bộ mã hóa là thanh ghi dịch K bit. - Hình 5.15 Ví dụ bộ mã hóa mã chập tỷ lệ 1/2. - Có thể biểu diễn bộ mã hóa mã chập bằng các đa thức sinh. - biểu diễn một từ mã hai bit ra ứng với một bit vào. - Hình 5.16 Sơ đồ cây biểu diễn bộ mã hóa mã chập ở hình 5.15. - Hình 5.17 Sơ đồ lưới biểu diễn bộ mã hóa mã chập ở hình 5.15. - Khác với mã khối có độ dài từ mã cố định, mã chập không có kích thước đặc thù. - Ta xét lại ví dụ mã hóa mã chập hình 5.15. - Mã khối tuyến tính - còn gọi là mã nhóm - có các từ mã có tương ứng 1-1 với các phần tử thuộc nhóm toán học.. - Mã vòng (cyclic code) là một lớp con của mã khối tuyến tính không có từ mã gồm toàn số 0. - Một mã khối tuyến tính được gọi là mã vòng nếu sau một lần dịch vòng một từ mã thì cũng được một từ mã thuộc cùng bộ mã.
Xem thử không khả dụng, vui lòng xem tại trang nguồn hoặc xem
Tóm tắt