MÃ HOÁ KHỐI TUYẾN TÍNH (linear block coding):

Trong mã hoá khối tuyến tính các nhóm của bản tin có chiều dài không đổi được mãhoá sang các nhóm bit mã hoá có chiều dài cố định. Nhóm các bit để hình thành số bản tin mong muốn. Chẳng hạn như bằng cách kết hợp các nhóm 3 bits, ta có thể hình thành nên 8 bản tin có từ mãnhư sau: 000, 001, 010, 011, 100, 101, 110, 111. Mỗi một trong 8 từ bản tin này có thể được mã hoá sang một trong 8 từ mã khác. Các từ mã không cần thiết phải có chiều dài bản tin giống như từ bản tin gốc. Thật vậy, để điều khiển được lỗi, các từ mã phải dài hơn từ bản tin gọi là phần dư (redundancy).

Ta có thể kiểm tra khả năng sửa lỗi cho các lỗi được phân bố ngẫu nhiên. Ta giả sử rằng các bit thực tế đảo ngược trong khi truyền đi, được phân bố một cách ngẫu nhiên trong suốt bản tin. Đây không phải là trường hợp các lỗi ngẫu nhiên (burst error) mà ở đây xác suất lỗi bit cao xảy ra trong số các bit lân cận.

KHOẢNG CÁCH GIỮA CÁC TỪ MÃ

Khoảng cách giữa hai từ nhị phân có chiều dài bằng nhau được định nghĩa như số vị trí bit khác nhau giữa hai từ này. Ví dụ như khoảng cách giữa 000 và 111 là 3 trong khi khoảng cách giữa 010 và 011 là 1. Khoảng cách giữa bất cứ từ nào với từ được hình thành bằng sự thay đổi một bit là 1.

Giả sử bây giờ ta truyền một trong 8 từ mã 3 bit. Và ta truyền trên một kênh bị nhiễu và có một bít vị trí nhận sai vì mỗi tổ hợp 3 bít được dùng cho một bản tin, nên thu được chính là một trong các từ mã và một lỗi được tạo ra. Chẳng hạn như nếu giá trị 101 được truyền và có một lỗi xảy ra trong bit thứ ba nên ở hệ thống thu được sẽ là 100.

Bây giờ giả sử rằng từ vựng của các từ mã là khoảng cách giữa bất cứ hai từ mã nào ít nhất là hai. Tám từ mã sau đây có tính chất trên:

0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111

Bây giờ ta truyền một trong 8 từ mã và một bit lỗi xảy ra trong khi truyền. Vì khoảng cách giữa từ nhận được và từ truyền là 1, từ nhận được không thể ghép bất cứ từ nào trong từ vựng. Ví dụ như giá trị 0101 được truyền và bit lỗi xảy ra ở bit thứ 3, hệ thống thu nhận được 0111. Đây không phải là một trong 8 từ trên. Không thể sửa lỗi được nếu từ mã truyền là một trong các trị sau: 0011, 0101, 0110, 1111.

Bây giờ ta sẽ vẽ các từ mã trong một không gian n chiều, 8 từ mã trở thành các góc của hình khối đơn vị như trình bày trong hình 7.44.Bắt đầu tại mỗi góc của hình khối, nếu một lỗi bit được tạo ra, ta sẽ di chuyển một trong những cạnh đến một góc kế bên với khoảng cách là một đơn vị. Vì thế khoảng cách giữa hai từ là số cạnh nhỏ nhất phải được xoay quanh trục để di chuyển từ một từ đến những từ khác.

Hình 7.44 Mã hoá 3 bit trong không gian 3 chiều.

Trong ví dụ trên vơi các từ mã 4 bit ta cần một hình vẽ với 8 điểm thể hiện các từ mã 4 chiều. Đây là một hình khối trong một không gian 4 chiều. Ta tìm ít nhất hai cạnh được xoay quanh một trục từ một từ đến những từ khác.

Trong trường hợp tổng quát nếu khoảng cách nhỏ nhất giữa hai từ mã là 2, các từ mã được chia ít nhất là hai cạnh trong một không gian n chiều. Ta sẽ minh hoạ điều này trong hình 7.45. Trong hình này ta chỉ ra3 trong số các từ mã từ ví dụ trên. Khối cầu n chiều với bán kính đơn vị bao gồm tất cả các từ với khoảng cách bằng 1 được tính từ tâm.

Hình 7.45 Không gian 4 chiều.

Giả sử bây giờ khoảng cách nhỏ nhất giữa các từ mã được tăng lên bằng 3. Ta thấy rằng nếu một lỗi được tạo ra, từ nhận được có khoảng cách bằng 1 từ một từ mã đúng và ít nhất 2 đơn vị so với khoảng cách từ mỗi từ mã khác. Ta sẽ giải mã với từ gần nhất có thể chấp nhận được. Vì thế mã này có khả năng sửa lỗi một bit lỗi. Nhưng khi truyền chắc gì không xảy ra hai bit lỗi. Đối với trường hợp này, tiến trình mã hoá của ta sẽ dẫn đến câu trả lời không đúng. Tuy nhiên xác suất của 2 bit lỗi, nhỏ hơn xác suất của một bit lỗi. Ví dụ nếu ta truyền các từ 5 bits và xác suất của bit lỗi là 10^-4, xác suất của một bit lỗi được xác định như sau:

Và xác suất của 2 bit lỗi sẽ là:

Vì thế một bit lỗi, nhiều hơn khoảng 500 lần so với 2 bit lỗi. Vì thế chiến thuật của ta có một kết quả trung bình giữa việc ước lượng 500 lần lỗi được sửa đúng và một lần ước lượng sửa lỗi không đúng.

Tổng quát nếu khoảng cách nhỏ nhất giữa các từ mã là D_min, ta có số các lỗi là D_min – 1. Để chuyển từ từ mã được truyền sang từ mã có thể chấp nhận khác ít nhất là D_min lỗi được tạo ra, ta có thể nhận ra nếu có nhiều hơn số lỗi được tạo ra.

Nếu ta sửa lỗi bằng cách di chuyển đến từ gần nhất có thể chấp nhận, ta sửa (D_min - 2)/2 lỗi cho D_min chẵn và (D_min - 1)/2 lỗi cho D_min lẻ.

CÁC MÃ SỐ HỌC (algebraic codes)

Giả sử rằng từ bản tin của ta bao gồm k bits và ta thêm phần dư với m bits thêm vào. Lúc đó chiều dài của mỗi từ mã vào là n = k + mbits. Vì thế mỗi từ thông tin k bits có liên quan đến một từ mã n bit. Nếu từ thông tin xuất hiện rõ như một phần của từ mã, ta qui ước cho điều này như một mã hệ thống. Nếu ta biểu thị các bit thông tin này là u_i và các bit thêm vào là c_i, từ mã có thể được viết như sau:

c₁c₂ . . . c_mu₁u₂ . . . u_k

Ta đã đặt các bit thông tin ở phần kết thúc của từ mã. Điều này, không cần thiết và chúng có thể xuất hiện bất cứ ở đâu trong từ.

Một mã toán học là một mã mà các từ mã và từ thông tin có liên hệ bằng một biểu thức ma trận.

Đây là một mã tuyến tính (n, k) trong đó n là chiều dài của các từ mã.

Ví dụ 7.10: Từ mã tuyến tính A(4, 3) được phát bởi ma trận:

Hãy tìm các từ mã liên quan với mỗi từ thông tin.

Giải:

Mã A(4, 3) có các từ thông tin với chiều dài 3 bits và các từ mã có chiều dài 4 bits. Như vậy ta có 8 từ mã thông tin 3 bits. Ta nhân mỗi từ mã cho ma trận phát để tìm các từ mã như sau:

Trước khi qua ví dụ này ta có một số chú ý. Chú ý đầu tiên là 3 bit mã cuối cùng ghép với từ thông tin. Vì thế mã này là mã hệ thống. Điều này xảy ra khi vế phải của ma trận [G] là một ma trận 3 chiều. Ta cũng chú ý rằng các bit dư thêm vào là một parity bit được chọn để cung cấp cho parity chẳn. Các bits thêm vào trong mã số học, luôn luôn là các bit kiểm tra parity. Mà ở đây ta chọn ký hiệu c_i cho các bits dư này.

Ví dụ 7.11: Mã tuyến tính A(7, 4) được phát bởi ma trận [G]:

Hãy tìm các từ mã liên hệ với mỗi từ thông tin và tìm khoảng cách nhỏ nhất cho mã này.

Giải:

Với mã A(7, 4) có 4 bits thông tin 3 bits parity. Các từ thông tin và từ mã liên quan, được cho như sau:

Việc kiểm tra của ma trận [G] cho thấy rằng:

Bit parity đầu tiên cung cấp parity chẵn khi kết hợp với các bit thông tin thứ nhất thứ 3 và thứ tư.

Bit parity thứ hai cung cấp parity chẵn khi kết hợp với các bit thông tin thứ nhất thứ hai và thứ ba.

Bit parity thứ tư cung cấp parity chẵn khi kết hợp với các bit thông tin thứ hai thứ ba và thứ tư.

Ta có thể kiểm tra khoảng cách giữa mỗi cặp từ mã (có 120 cặp để kiểm tra). Nếu ta làm như thế, ta tìm khoảng cách nhỏ nhất của 3 bit parity. Mã này có thể sửa lỗi một bit hoặc 2 bits. Việc kiểm tra 3 bits parity của từ nhận được cho phép ta xác định các lỗi bằng phép đo đạc tam giác (triangulation).

Kiểm tra các khoảng cách trong ví dụ 7.11 là một tiến trình xử lý toàn diện. Một số phép toán tạo ra tiến trình hầu như đơn giản. Ta bắt đầu định nghĩa độ lớn của từ mã như số số 1 chứa trong từ đó. Nếu ta thêm hai từ (phép toán modulo -2), tổng chứa một số 1 trong mỗi vị trí bit với hai từ khác nhau. Vì thế khoảng cách giữa hai từ là độ lớn của tổng.

Ta có thể nhìn thấy từ biểu thức 7.23 mà tổng của các từ mã là một từ mã có thể chấp nhận được. Nếu ta cộng hai từ thông tin với nhau, kết quả từ mã là tổng của hai từ mã gốc. Đây là một thuộc tính cơ bản của mã toán học. Xem lại ví dụ 7.11 tổng của bất kỳ 2 trong số 16 vector mã phải bằng với một trong các vector mã khác. Vì thế một trong các vector mã nonzero thể hiện tổng của hai vector khác (vector zero là tổng của vector mã với chính nó). Khoảng cách nhỏ nhất giữa các từ mã chính là độ lớn nhỏ nhất của các từ mã nonzero. Đây là giá trị 3 cho ví dụ trước mà ta chỉ cần kiểm tra độ lớn là 15 thay vì 120 khoảng cách.

Mỗi ma trận phát [k x n] có một ma trận kiểm tra parity [(n - k) x n]được định nghĩa là [H]. Ta thiết lập ma trận này bằng lấy hoán vị của phần không xác định của [G] và biến chúng thành ma trận xác định. Vì thế ma trận [H] tương ứng với ma trận [G] trong ví dụ 7.11 là:

Ma trận kiểm tra parity có thuộc tính là:

Bất cứ từ mã nào được nhân với chuyển vị của [H] trở thành một vector zero. Ví dụ hãy chọn từ mã thứ 3 trong ví dụ 7.11 là 1001011. Ta tìm được:

Bây giờ giả sử rằng ta truyền mã vecotor

và có một lỗi xảy ra trong vị trí bit thứ tư. Đây là biểu thức được thêm vào vector lỗi.

Với vector truyền vectơ n. Ta thu được vector vecto r=vecto n+vecto e và nhân với [H]^T. Kết quả sẽ là:

Nếu vecto e chứa giá trị 1, e[H]^T kết hợp với dòng của [H]^T tương ứng với vị trí lỗi. Chẳng hạn như nếu ta thay đổi bit thứ tư trong ví dụ trên, ta sẽ nhận được 1000011. Nó được nhân với [H]^T tạo thành [1 1 0]. Đây chính là dòng thứ tư của [H]^T. Ta sẽ nhận ra sự ghép nối của dòng thứ tư. Do đó ta biết được nơi lỗi xảy ra và có thể sửa chúng. Kết qủa là vector nhận được với [H]^T là một dấu hiệu.

Nếu có nhiều hơn một lỗi xảy ra, dấu hiệu là tổng của các dòng có liên quan đến ma trận. Nếu tổng này là duy nhất (tức là nó chỉ có thể có được bằng cách cộng một tập hợp các dòng đặc biệt lại với nhau), mã có khả năng đúng nhiều hơn là lỗi.

Các mã Hamming là một trong những ví dụ quan trọng của các mã toán học có khả năng sửa một lỗi. Các mã Bose, Chaudhuri, Hocquenghem (BCH) là một trong những ví dụ quan trọng của mã số học có thể sửa được nhiều hơn một lỗi.

CÁC MÃ CHU KY (cyclic codes)

Công cụ của các mã số học đòi hỏi khả năng về thực hiện nhân ma trận và so sánh kết quả với những số nhị phân biến đổi. Các mã phổ biến nhất, được hệ thống lại như các mạch tích hợp.

Các mã chu kỳ là một trường hợp đặc biệt của các mã khối mà nó có thể hình thành rất đơn giản. Chúng có thể trình bày như một bộ ghi lại các từ mã của mã số học. Ta có các mã chu kỳ như các đa thức. Ví dụ như một từ 1101 tương đương với đda thức 1 + X + X³. Mỗi vị trí trong từ nhị phân có liên hệ với một biến X. Và mã này tượng trưng cho đa thức phát và các từ mã bắt nguồn từ việc nhân đa thức với vector thông tin để tạo thành đa thức phát.

MÃ PN (pseudonoise)

Một lớp đặc biệt của đa thức phát hình thành một tập hợp các mã chu kỳ với các thuộc tính khoảng cách mong muốn. Những điều này được hiểu như các đa thức tối giản cực đại.

Kết quả mã hoá từ các đa thức tối giản được hiểu như mã PN hay pseudonoise. Pseudonoise là một dãy số nhị phân với các thuộc tính giống như nhiễu bạch (white noise). Mã được phát với các thanh ghi dịch hồi tiếp. Ta minh hoạ điều này bằng một ví dụ với sơ đồ khối hình 7.46. Ta cho giá trị ban đầu vào bộ phát bằng hồi tiếp trong dãy số 3 bits. Bộ phát bắt đầu hoạt động và phát mỗi bit thành công bằng cách cộng vào hai bit trước đó lại với nhau. Giả sử rằng ta thêm vào bộ phát 3 bit 010., ngõ ra sẽ là: 010111001011100101110. . .

Hình 7.46 Bộ phát mã PN.

Chú ý rằng điều này lặp lại với chu kỳ 7 bits. Nếu ta lấy bất cứ 7 bits liên tiếp nào trong dãy số này, ta có một từ mã mới. Vì thế nếu ta thêm vào dãy số giá trị 101, kết quả từ mã sữ là 1011100. Và kết quả này trông giống như từ 2 đến 8 bit trong dãy số này. Ta có thể nhận ra 7 từ mã nonzero như sau:

0111001

1110010

1100101

1001011

0010111

0101110 1011100

Những từ này có thuộc tính khoảng cách bằng nhau. Khoảng cách giữa bất cứ hai từ luôn luôn là 4.

Các dãy số PN dài hơn có các thuộc tính giống nhau. Nếu ta xây dựng một bộ phát với một tế bào lưu trữ nhiều hơn trong thanh ghi dịch và các tiếp điểm hồi tiếp phù hợp, các dãy số thêm vào sẽ có chiều dài 4 bits và các từ mã sẽ tăng chiều dài lên 15 bits. Bất cứ hai trong số 15 từ mã khác nhau sẽ có một khoảng cách cách giữa chúng là 8.

Tổng quát các mã PN với các dãy số thêm vào có chiều dài n, sẽ có các từ mã với chiều dài 2ⁿ – 1 và khoảng cách giữa hai từ mã là 2^n-1. Điều này cho ta một kỹ thuật đơn giản về việc phát các dãy số dài với thuộc tính khoảng cách phù hợp. Khi dịch bất cứ từ mã nào sẽ cho kết quả bằng một từ mã khác, khoảng cách giữa bất cứ từ nào và bản sao của chính nó là 2^n-1. Điều này tạo cho các mã PN hữu dụng trong các ứng dụng điều hoà thời gian. Ví dụ như khi một từ mã 127 bit PN, được so sánh với chính nó, có 127 đối số bằng nhau. Với một sự dịch chỉ một vị trí, số đối số giảm xuống còn 63.

MÃ HOÁ CHỒNG (Convolutional Coding)

Sự cải tiến trong thực hiện lỗi cho mã hoá khối là khi phần dư được thêm vào. Đó là các bit parity được thêm vào bản tin để tăng khoảng cách giữa các từ mã. Bằng cách đó sẽ cung cấp cho sự phát hiện lỗi và hoặc sửa lỗi. Để gia tăng khả nămg sửa lỗi, phải gia tăng số phần dư thêm vào.

Sự lựa chọn cho mã hoá khối là mã hoá chồng. Trong loại mã này ta không xem các khối bit độc lập như các từ mã nữa. Thay vì một dòng thông tin các bits liên tục được hoạt động trên hình dạng của bản tin mã hoá. Nguồn này phát một chuổi của bản tin liên tục các bit 1 và 0 và dãy số truyền được phát từ dãy số nguồn này. Dãy số được phát có thể hoặc không thể dài hơn dãy số của bản tin. Kỹ thuật này không thêm các bit dư. Nó sẽ giữ lại khả năng sửa lỗi bằng cấu trúc bộ nhớ trong hệ thống.

Kỹ thuật phát dãy số truyền là lấy chồng dãy số nguồn với dãy số nhị phân cố định. Vì thế một bit truyền đặc biệt t_n được phát từ sự kết hợp của các bits, s_n, s_n-1, s_n-2,. . ., s_n-k­ tuỳ theo biểu thức chồng.

(7.24)

Giá trị h trong biểu thức 7.24, hoặc là 1 hoặc là 0 và thêm vào một mạch cộng modulo-2. Biểu thức này có thể được thiết lập lại với một thanh ghi dịch và một mạch cộng modulo-2. Hình 7.47 trình bày cách thiết lập tổng quát của biểu thức 7.24. Các công tắc trong hình đóng nếu giá trị h trong biểu thức 7.24 là 1 và mở nếu giá trị h là 0.

Trong ứng dụng của mã hoá chồng ta thường truyền nhiều hơn một bit cho mỗi ngõ vào 1 bit. Trong hình 7.47 ta có thể dịch ở một bit ngõ vào đặt các công tắc tương ứng với tập giá trị của h và phát bit ngõ ra đầu tiên. Trước khi cho vào một

Hình 7.47 Phát mã PN.

bit ngõ vào khác ta reset các công tắc tương ứng với tập giá trị thứ hai của h và truyền một bit thứ hai. Nếu hai bit ngõ vào được truyền cho một bit ngõ vào, mã đó được gọi là mã chồng với tỉ lệ ½ (rate ½ convolutional code). Trong khi truyền mã chồng với tỉ lệ tỉ lệ ½, ta thường chọn một bit trong mỗi cặp truyền được xác định để chỉ ra dãy số thông tin. Đây là một mã hệ thống.

Ví dụ 7.12: Hình 7.48 trình bày một bộ phát cho mã chồng tỉ lệ ½. Ta đưa ra hai qui ước của việc vẽ thanh ghi dịch. Hình 7.48 a và 7.48 b trình bày hệ thống gống nhau. Dãy số ngõ vào cũng được chỉ ra, bit ngõ vào đầu tiên cũng được chỉ ra ở bên trái và bit ngõ vào cuối cùng (gần nhất ) ở bên phải. Hãy tìm dãy số ngõ ra.

Giải:

Ta cho hệ thống được thêm vào với một chuổi các số zero phù hợp đến việc nhận bit đầu tiên của dãy số ngõ vào và bit cuối cùng là một chuổi số zero., ngõ ra sẽ là:

1 1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 1 0 0 0 0. . .

Ngõ ra của giải mã chồng phụ thuộc vào bit ngõ vào hiện tại và các bit ngõ vào trước đó. Trong ví dụ 7.12 ta cần biết ngõ vào hiện tại và hai ngõ vào trước đó để tìm ngõ ra.

Một cách hữu dụng đặc biệt của việc trình bày mã chồng là một sơ đồ trạng thái. Trạng thái của hệ thống được định nghĩa bằng hai ngõ vào gần nhất.

Vì thế hệ thống có thể là một trong 4 trạng thái tuỳ thuộc vào hai ngõ vào là 00, 01, 10, 11. Khi hệ thống ở trong một trạng thái đặc biệt và nhận một bit ngõ vào hai việc này có thể xảy ra tuỳ thuộc vào bit ngõ vào là 1 hoặc 0. Khi ngõ vào tiếp theo được nhập vào hệ thống,, hệ thống sẽ tạo ra một sản phẩm ở ngõ ra và cũng di chuyển đến một trạng thái mới.

Ta có thể xem lại hệ thống phát của hình 7.48 và phát triển tành sơ đồ trạng thái. Hai ngõ vào trước đó tập trung vào các bước 1 và 2 của thanh ghi dịch. Ngõ vào tiếp theo dịch mọi thứ sang bên trái một ô và tạo ra sản phẩm ở ngõ ra. Trạng thái mới được chỉ ra bởi các nội dung mới của trạng thái 1 và 2.

Hình 7.48 Bộ phát mã hoá chồng cho ví dụ 7.12.

Trong tình trạng này ta phát triển sơ đồ trạng thái của hình 7.49. Trong trạng thái a cả bước 1 và 2 đều chứa chứa giá trị 0 trong khi ở trạng thái d đều chứa giá trị 1. Trạng thái b xảy ra khi bước 1 chứa một giá trị 1 và bước 2 chứa giá trị 0 còn bước c ở vị trí của bước b. Có hai đường rời khỏi mỗi trạng thái nó thể hiện các đường xảy ra bởi hệ thống khi ngõ vào hiện tại hoặc là 0 hoặc là 1. Kết quả ở ngõ ra (là hai bit khi tỉ lệ là ½) được chỉ ra trong ngoặc đơn trên mỗi đường trực tiếp.

Ví dụ 7.12 Có thể giải bằng bằng cách kiểm tra sử đụng sơ đồ trạng thái. Cho mỗi ngõ vào được chỉ ra các trạng thái kết quả 1101001 (giả sử ta bắt đầu ở trạng thái a) là:

b d c b c a b c a a a a a . . .

Ngõ ra được đọc bằng cách kiểm tra từ sơ đồ và hoàn toàn phù hợp với lời giải của ví dụ 7.12.

Hình 7.49 Lược đồ trạng thái của bộ phát cho hình 7.48.

Thách thức thật sự của mã hoá chồng là việc giải mã ở hệ thống thu. Ta có thể thiết lập trạng thái yêu cầu giải mã trong các số hạng của sơ đồ trạng thái mà kết quả trong một từ mã gần nhất nhận được. Số đường dẫn có thể gia tăng với số bit nhận được. Chẳng hạn như với hai bit nhận được sẽ có hai đường dẫn qua lược đồ (giả sử ta bắt đầu ở trạng thái cuối cùng). Với 4 bit nhận được sẽ có 2² hoặc 4 đường. Với 6 bit nhận được sẽ có 2³ hoặc 8 đường. Điều này sẽ xuất hiện ở một tiến trình kết thúc cho chiều dài các dòng bit và thực sự nó không phải là thuật toán Vertibi. Thuật toán này rút ngắn số đường cần thiết được dùng cho sự giải mã. Nó tạo ra vị trí để xây dựng các bộ giải mã đơn giản.