Giáo trình Lý thuyết thông tin

iền nhau gọi là sai cụm
	Sự lựa chọn cấu trúc của mã chống nhiễu phải dựa trên tính chất thống kê của kênh, nói cách khác dựa trên sự phân bố xác suất sai nhầm trong kênh.
Ví dụ:
	Hãy xác định quy luật phân bố xác suất sai nhầm trong một kênh nhị phân đối xứng. Kênh nhị phân đối xứng thuộc loại kênh chứa sai nhầm không tương quan và p(1|0) = p(0|1) = ps.
	Xác suất nhận đúng một ký hiệu sẽ là: 1-ps và xác suất nhận đúng một từ mã có độ dài n là (1-ps)n, xác suất nhận sai từ mã đó là pn = 1-(1-ps)n
Bây giờ ta xác định xác suất nhận sai t ký hiệu trong một từ mã gồm n ký hiệu. Trước tiên xác suất xảy ra t sai đồng thời: pst và xác suất xảy ra trong một từ mã có n ký hiệu, n-t ký hiệu xuất hiện đúng: (1-ps)n-t, vậy xác suất xảy ra trong một từ mã n ký hiệu có một ký hiệu sai là: p1(n,t) = pst(1-ps)n-t.
Tổng số các từ mã n ký hiệu có t ký hiệu sai là Cnt = n!/((n-t)!t!).
Xác suất xuất hiện một từ mã n ký hiệu có t ký hiệu sai là: p(n,t)= Cnt pst(1-ps)n-t. 
Khi trị số ps nhỏ thì xác suất nhận các từ mã sai ít ký hiệu lớn hơn xác suất nhận các từ mã sai nhiều ký hiệu: p(n,t) > p(n,t’) nếu t < t’.
Điều này cho phép ta xây dựng các mã hiệu chống nhiẽu hữu hiệu trong kênh nhị phân đối xứng. Các mã hiệu này có khả năng phát hiện và sửa sai các tổ hợp mã có số ký hiệu sai bé, nhiều hơn là đối với các tổ hợp mã có số ký hiệu sai lớn.
 Cơ chế phát hiện sai
Nếu mã hiệu là tập hợp các từ mã n ký hiệu thì số từ mã được chọn phải bé hơn tổng số các tổ hợp có thể có từ n ký hiệu. Những tổ hợp không dùng làm từ mã gọi là tổ hợp cấm. Khi nhận tin nhận được tổ hợp cấm ta phát hiện ra sai
Với mã nhị phân có n ký hiệu thì có số tổ hợp là: 
Mã muốn phát hiện sai được thì số tổ hợp dùng và ta có số tổ hợp cấm là: 
Ví dụ: dùng 4 tổ hợp mã hoá tin như sau:
Khi nhận được bất kỳ tổ hợp nào ta cũng thấy hợp lý vì vậy ta không phát hiện ra sai nhầm.
Nếu ta chỉ dùng 3 tổ hợp như sau: 
Khi nhận được tổ hợp 11 ta biết là đã có sự sai nhầm. Tổ hợp 11 chính là tổ hợp cấm
 Cơ chế sửa sai
Cơ chế sửa sai của mã hiệu đồng thời cũng là nguyên lý giải mã phải dựa vào tinh chất thống kê của kênh để đảm bảo mục tiêu sai nhầm tối thiểu. Muốn vậy cần phải dựa vào tính chất nhiễu trên kênh để phân nhóm các tổ hợp cấm, mỗi nhóm tương ứng với một từ mã mà chúng có khả năng bị chuyển đổi sang nhiều nhất.
Căn cứ vào đặc tính thống kê số từ mã sai ít ký hiệu xảy ra nhiều hơn nên ta ưu tiên xử lý trước.
Coi mối từ mã là một véc tơ, mỗi ký hiệu là một toạ độ của véc tơ. Nhiễu cũng được coi như là một véc tơ gọi là véc tơ sai. Từ mã sai coi như là tổng hợp của véc tơ mã và véc tơ sai.
Ví dụ 1: 
 Véc tơ mã: 0101
 Véc tơ sai: 0100
 Từ mã sai: 0001
Từ mã trên bị sai ký hiệu thứ 2 (bít 1 trở thành bít 0)
Ví dụ 2: Với một từ mã có 4 ký hiệu véc tơ sai cũng có 4 ký hiệu, có các phương án sai 1 ký hiệu, 2 ký hiệu, 3 ký hiệu .. Ta có bảng sau:
Vec tơ mã
a1
a2
a3
a4
Số k. h sai
Vec tơ sai
0001
0101
1110
1111
0001
0000
0100
-
-
1
0010
0011
0111
1100
1101
0100
-
-
1010
1011
1000
1001
1101
0110
0111
0011
0010
0110
1101
1100
2
0101
0100
0000
1011
1010
1001
1000
1100
0111
0110
1010
1011
-
0100
-
1100
1101
1001
0010
0011
0111
0110
0010
1001
1000
3
1011
1010
-
-
0100
1101
1100
1000
0011
0010
1110
-
1011
0000
-
1111
-
1010
-
0000
4
Với nhận xét trên ta có các tổ hợp cấm được phân thành nhóm, các từ mã cấm trong nhóm Bi tương ứng với từ mã đúng ai. Ta dược bảng sau:
B1
B2
B3
B4
t
0000
0100
1100
1101
1
0011
0111
1010
1011
1001
1101
0110
0111
Ta thấy nhận được tổ hợp ‘0111’ hoặc ‘1101’ do sai 1 ký hiệu ta có thể giải mã và sửa thành ‘0101’ (), như vậy theo nguyên tắc trên ta có thể sửa sai cho bộ mã. Tuy nhiên như bộ mã trên cũng cho thấy có thể sửa không chính xác vì tổ hợp ‘1101’ có thể sửa thành cũng có thể sửa thành . Để giải quyết người ta khắc phục bằng cách dùng bảng chọn hoặc tính khoảng cách mã của bộ mã.
 Xây dựng bộ mã sửa sai bằng bảng chọn
Bằng cách lập bảng chọn ta chọn được tổ hợp từ mã dùng, hợp lý đảm bảo sửa sai được.
Ví dụ: Xâydựng bảng mã có 4 từ mã mỗi từ mã có 4 ký hiệu. 
Xây dựng bảng có cột như sau:
SỐ CỘT
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
0011
0011
0010
0001
0000
0111
0110
0101
0100
1011
1010
1001
1000
1111
1110
1101
1100
0110
0110
0111
0100
0101
0010
0011
0000
0001
1110
1111
1100
1101
1010
1001
1000
1001
1100
1100
1101
1110
1111
1000
1001
1010
1011
0100
0101
0110
0111
0000
0001
0010
0011
: vec tơ mã, : vec tơ sai.
Từ bảng trên ta chọn các từ mã để sử dụng bằng cách:
Chọn một từ bất kỳ ví dụ chọn từ mã = 0001 ta xem bản thân nó và các tổ hợp cấm của nó nếu trùng với các tổ hợp của từ mã nào đó thì đánh dấu cột i để loại. Như trên loại cột 3, 5, 8, 12, 14, 15. Chọn từ mã thứ 2 trong các cột còn lại giả sử chọn loại các cột có các tổ hợp trùng với các tổ hợp cấm của ta sẽ loại cột 1, 4, 7, 10, 11, 16.. Chọn tiếp tương tự ta chọn được 4 từ mã là:
 (cột 2)
 (cột 6)
 (cột 9)
 (cột 13)
Với 4 từ mã trên khi nhận được mã sai ứng với kênh đã phân tích ở trên ta sẽ sửa sai tương đối chính xác ví dụ:
B1: 0010, 0111, 1101 sẽ sửa duy nhất thành a1
B2: 0110, 0011, 1001 sẽ sửa duy nhất thành a2
B3: 1011, 1110 , 0100 sẽ sửa duy nhất thành a3
B4: 1111, 1010, 0000 sẽ sửa duy nhất thành a4
Thuật toán:
V: Tập các từ mã
Bi: ai và Tập các tổ hợp cấm tương ứng với ai
B: Tập các tổ hợp cấm tương ứng với các từ mã và các từ mã được chọn
N: Số tin nguồn, tương ứng với số từ mã
V=Æ;
B=Æ;
k=0;
For i:=1 to 2n do
Begin
 if Bi Ç B = Æ then
 Begin
 V=V È ai;
 B = B È Bi;
 k:=k+1;
 if k=N then break;
 End;
End; 
Xây dựng bộ mã sửa sai bằng trọng số Hamming và khoảng cách Hamming
Trọng số Hamming
Trọng lượng Hamming (Hamming weight) của một dãy ký tự là số phần tử trong dãy ký tự có giá trị khác không (0): đối với một dãy ký tự nhị phân (binary string), nó chỉ là số các ký tự có giá trị một (1), lấy ví dụ trọng lượng Hamming của dãy ký tự 11101 là 4
Cho V(v1,v2,v3,..,vn) là một vec tơ n thành phần nhị phân. Trọng số Hamming của V, ký hiệu là W(V) được định nghĩa là số thành phần khác 0 của V.
Ví dụ: Véc tơ V(v) = 01011 có W(v) = 3 
Khoảng cách Hamming
Trong lý thuyết thông tin, Khoảng cách Hamming (tiếng Anh: Hamming distance) giữa hai dãy ký tự (strings) có chiều dài bằng nhau là số các ký hiệu ở vị trí tương đương có giá trị khác nhau. Nói một cách khác, khoảng cách Hamming đo số lượng thay thế cần phải có để đổi giá trị của một dãy ký tự sang một dãy ký tự khác, hay số lượng lỗi xảy ra biến đổi một dãy ký tự sang một dãy ký tự khác.
Lấy ví dụ:
Khoảng cách Hamming giữa 1011101 và 1001001 là 2. 
Khoảng cách Hamming giữa 2143896 và 2233796 là 3. 
Khoảng cách Hamming giữa "toned" và "roses" là 3. 
 Khoảng cách Hamming giữa hai véc tơ U(u1,u2,u3,..,un), V(v1,v2,v3,..,vn) là số các toạ độ khác nhau giữa chúng. Ký hiệu là D(U,V).
Ví dụ: Tính khoảng cách hai véc tơ 11001 và 10110 là 4
Từ định nghĩa khoảng cách Hamming giữa hai vec tơ ta có kết quả sau:
D(U,V) = W(U+V). Trong đó U+V là một vec tơ có được từ phép cộng modul 2 giữa hai vec tơ U và vec tơ V.
Ví dụ: U = 11001 V = 10110: U + V = 01111
Như vậy khoảng cách của U và V là W(U + V) = 4
Cơ chế phát hiện sai bằng khoảng cách Hamming
Ta thấy khoảng cách giữa hai từ mã sẽ thay đổi 1 đơn vị nếu thay đôỉ 1 ký hiệu nào đó trong một từ mã. Khoảng cách bằng 0 nếu 2 từ mã trùng nhau (không phân biệt được). Vậy nếu 2 mã hiệu có khoảng cách D = 1 thì không phát hiện được sai 1 ký hiệu. Muốn phát hiện sai 1 ký hiệu giữa hai từ mã phải có khoảng cách mã D tối thiểu bằng 2. 
Vậy muốn phát hiện từ mã sai t ký hiệu thì khoảng cách mã phải thoả mãn điều kiện sau: D ³ t+1
Ví dụ1: Từ mã 1110 dưới tác dụng của từ mã sai 0001 sẽ thành 1111, vậy nếu ta chọn a1 = 1110, a2 = 1111 (D =1) thì khi a1 sai một ký hiệu thành ‘1111’ khi nhận ta không phát hiện ra sai được.
Ví dụ 2: Giả sử có bộ mã: a1 = 0011; a2 = 0101; a3 = 1100; a4 = 1111
Bộ mã này có D = 2 khi một từ mã bất kỳ sai đi 1 ký hiệu ta nhận ra ngay. Giả sử từ mã a1 sai 1 ký hiệu trở thành 0111, 1011, 0001, 0010 ta nhận thấy các tổ hợp này là tổ hợp không dùng vậy đã có hiện tượng sai.
Cơ chế sửa sai bằng khảng cách Haming
Bây giờ hãy xét điều kiện mã không những chỉ phát hiện sai mà còn sửa chữa được sai nhầm.
Điều kiện này được thoả mãn nêú sự sai nhầm làm chuyển đổi từ mã ban đầu thành những tổ hợp mã gần từ mã đó hơn là bất cứ một từ mã nào khác.
Ta thấy khi từ mã sai đi t ký hiệu thì khoảng cách của nó so với một từ mã bất kỳ khác cũng lệch đi t đơn vị. Vậy một từ mã sai lệch đi so với từ mã gốc của nó khoảng cách nhỏ hơn D/2 thì ta sẽ quy về từ mã gốc của nó được.
Do đó từ mã sai t ký hiệu, ta muốn xác định được tổ hợp sai thuộc từ mã nào thì khoảng cách mã phải thoả mãn điều kiện: D ³ 2t +1
Ví dụ: Cho bộ mã: a1 = 00000, a2 = 01101, a3 = 10110, a4 = 11011
Bộ mã này có D = 3 nên có thể sửa sai cho 1 ký hiệu. Giả sử từ mã a2 bị sai 1 ký hiệu thành a2’ = 01111. Ta tính khoảng cách mã của a2’ với các từ trong bộ mã trên có: D(a1,a2’) = 4, D(a2’,a2) = 1, D(a2’,a3) = 3, D(a2’,a4) = 2
Như vậy a2’ gần a2 nhất ta sửa a2’ thành a2 = 01101. Rõ ràng việc sửa này là chính xác.
 Một số biện pháp phát hiện sai đơn giản
Dùng Parity
Khi xây dựng bảng tin để phát đi ta thêm vào một bit vào cuối nội dung thông tin để tạo ra tổng số các bít mang trị 1 là chẵn (Parity chẵn) hay lẻ (Parity lẻ). Khi nhận tin ta kiểm tra tổng các bít 1 để xem có bị thay đổi không (chẵn-lẻ) nếu dùng Parity chẵn mà tổng số bít 1 lẻ thì ta biết nhận tin sai. Muốn khôi phục tin ta tách các bít parity ra khỏi tin
Ví dụ: Ta có parity chẵn các bít parity thêm vào như sau:
Thông tin 	 Parity
0
1
1
0
1
1
1
1
1
0
0
1
0
1
1
0
0
0
Mã khối
Phương pháp này ta làm giống như dùng Parity nhưng mức độ cao hơn. Ta tạo tin thành từng khối và trên các dòng, cột ta đều thêm các bít parity theo cách trên. Như vậy ta kiểm tra hai lần theo dòng và theo cột nên khả năng phát hiện cao hơn nhiều, ngoài ra ta còn có khả năng sửa sai nếu xác định được toạ độ sai chính xác.
Ví dụ: 
1
1
0
0
1
1
0
1
0
1
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
0
1
0
1
 Mã tuyến tính
	Mã tuyến tính thuộc phạm vi đại số tuyến tính, cho nên cách biểu diễn mã thuận tiện và gọn nhất là phương pháp biểu diễn bằng ma trận.
 Phương pháp xây dựng mã tuyến tính
Người ta sử dụng các phép toán của đại số tuyến tính để biểu diễn mã. Giả sử bộ mã gồm các từ mã có độ dài , mỗi từ mã được gọi là một vec tơ mã gồm thành phần. Cơ số mã là (trong trường hợp nhị phân thì ).
Biểu diễn bằng ma trận sinh
Dùng ma trận gồm hàng, mỗi hàng là một từ mã thuộc được gọi là vec tơ nền của mã , khi đó được gọi là ma trận sinh của mã khi và chỉ khi bất kỳ một từ mã nào thuộc cũng là một tổ hợp tuyến tính của các hàng của ma trận .
 được gọi là không gian hàng của ma trận sinh , nếu số chiều của không gian vec tơ là k thì ma trận sẽ có hàng.
Như vậy các tổ hợp tuyến tính khác nhau tương ứng với những vec tơ mã khác nhau, Nếu có vec tơ nền thì hệ gồm vec tơ đó sẽ là hệ độc lập tuyến tính. Giả sử G = thì khi đó một vec tơ mã . Trong đó là các ký hiệu của mã. Mã sẽ có từ mã.
Ví dụ: Ta có ma trận sinh sau: ; 
Mã có và , các từ mã như sau:
	{00000; 01101; 10110; 11011}
Ví dụ: Xác định mã từ có ma trận sinh :
Ta thấy số tổ hợp là 25 sẽ có 32 tổ hợp nhưng ta chỉ dùng 8 tổ hợp (8 vec tơ mã) còn lại là những tổ hợp không dùng, mã này cũng cho phép ta phát hiện và sửa sai được. Cách biểu diễn này rất gọn và thuận tiện, nhất là khi các số và lớn trong khi nếu ta biểu diễn bằng bảng mã thì rất cồng kềnh và có thể không thực hiện được. Ngoài ra, ma trận sinh còn được gọi là ma trận sinh mã kiểm tra chẵn lẻ.
Biểu diễn bằng ma trận thử
	Xây dựng một ma trận gồm n-k hàng độc lập tuyến tính (trong đó k là số hàng của ma trận ), là ma trận mà bất kỳ một vec tơ mã thì (0 là vec tơ không, là chuyển vị của ). Không gian vec tơ tạo bởi ma trận được gọi là không gian không của không gian hàng ( hay là không gian hàng của ma trận , không gian không của ). được gọi là ma trận thử của mã .
	Mỗi vec tơ mã của đều trực giao với mỗi vec tơ thuộc .
Ví dụ : 
 có ma trận thử 
Mã hệ thống
Xét bộ mã nhị phân. Nếu bằng một phép biến đổi ta chuyển ma trận G về dạng sau: 
Với mỗi bộ ta có một vectơ mã 
	 trong đó 
 thành phần đầu của được gọi là những ký hiệu mang tin, thành phần sau được gọi là các ký hiệu dư hay ký hiệu thử (ký hiệu là ).
	Ta thấy thành phần sau là tổ hợp của các thành phần đầu. Vì vậy quá trình mã hoá đơn giản. Bộ mã này được gọi là mã hệ thống.
 Nguyên lý giải mã
	Trong nội dung trên, việc giải mã thực hiện đối chiếu vec tơ nhận được trong các lớp kề của bảng giải mã, tuy nhiên cách làm này không hiệu quả khi lớn. Để khắc phục hạn chế ta thực hiện theo thuật toán dựa trên cơ sở tính Syndrom. Cho là mã tuyến tính bao gồm các từ mã là các vec tơ : (vec tơ không) và những vec tơ mã còn lại . Các vec tơ sai . Để thuận tiện trong quá trình lập thuật toán giải mã ta định nghĩa khái niệm lớp kề như sau :
Định nghĩa 1 : là lớp kề thứ nếu , và được gọi là vec tơ tạo lớp kề.
Định lý 1: Nếu bảng giải mã theo cách xếp lớp kề, khi nhận được vec tơ sẽ giải mã đúng thành vec tơ khi và chỉ khi vec tơ sai là vec tơ tạo lớp kề.
Định nghĩa 2 : Syndrom của vec tơ gồm thành phần được xác định .
	Khi là từ mã đúng thì Syndrom sẽ bằng không, ngược lại Syndrom khác 0.
Định lý 2: Hai vec tơ cùng nằm trong một lớp kề khi và chỉ khi Syndrom của chúng bằng nhau.
Trên cơ sở các Định lý trên, ta có thuật toán giải mã :
Bước 1: Thiết lập bảng giải mã bằng cách xếp các lớp kề với những Syndrom tương ứng cho từng lớp.
Bước 2 : Khi nhận được một dãy dài thì tính Syndrom của và tìm lớp kề ứng với Syndrom đã tính.
Bước 3 : Từ mã gốc . là vec tơ tạo lớp kề .
Ví dụ : Cho ma trận sinh G
 có ma trận thử 
Bước 1: Xếp lớp kề:
00000
00101
01010
01111
10011
10110
11001
11100
00001
00100
01011
01110
10010
10111
11000
11101
00010
00111
01000
01101
10001
10100
11011
11110
10000
10101
11010
11111
00011
00110
01001
01100
Tính Syndrom của các lớp 1, 2, 3 lần lượt bằng : 01, 10, 11.
	Các vec tơ tạo lớp kề : 00001, 00010, 10000 là những vec tơ sai. Mã này không sửa được hết tất cả các từ mã sai một bit, vì khoảng cách mã tối thiểu . Muốn sửa được thì .
Bước 2: Giả thiết nhận được , Syndrom ứng với vec tơ tạo lớp kề 00001.
Bước 3: Từ mã gốc: 
 Một số giới hạn của mã tuyến tính
	Trong một mã tuyến tính, khả năng sửa sai của mã là một tiêu chuẩn hàng đầu. Khả năng này được biểu thị bằng số ký hiệu sai tối đa có thể sửa được trong một tổ hợp mã và có liên quan đến trọng lượng tối thiểu của mã (Khoảng cách mã). Cho nên khi xây dựng mã sửa sai tối ưu, cần phải xác định trước một số giới hạn của mã tuyến tính của mã như giới hạn trên về trọng lượng tối thiểu (hay khoảng cách mã), giới hạn dưới về số ký hiệu thử đối với mã tuyến tính. Dưới đây là một số giới hạn đối với mã nhị phân.
Giới hạn trên của khoảng cách mã tối thiểu
Tổng trọng số của mã tuyến tính (n,k) như sau:
Mỗi từ mã có ký hiệu, bộ mã có 2k từ mã. Như vậy có tổng số ký hiệu là . Trong đó có 1 ký hiệu khác 0. Giả thiết .
- Tổng trọng số là: .
Ta thấy khoảng cách mã của từ mã 0 đến từ mã có trọng số thấp nhất chính là trọng số của từ mã đó giả thiết đó là trọng số tối thiểu . Rõ ràng trọng số tối thiểu thì phải nhỏ hơn trọng số trung bình. Từ đó ta có thể rút ra điều kiện cho khoảng cách mã phải thoả mãn điều kiện: 
Như vậy phải nhỏ hơn hoặc lớn nhất là bằng tỷ số trên, đây chính là giới hạn trên của khoảng cách mã tối thiểu.
Giới hạn Plotkin(về số ký hiệu thử)
Điều kiện đã xét trên nếu r nhỏ quá những ký hiệu mang tin sẽ có trị làm cho D vượt quá giới hạn đã xét trên. Bằng tính toán ta có giới hạn về số ký hiệu thử r sau gọi là giới hạn Plotkin: .
trong đó số ký hiệu mang tin, : độ dài của từ mã.
Giới hạn Haming
Ta thấy Bộ mã có cơ số 2, từ mã có độ dài n nếu có t ký hiệu sai thì số phương án sai là: . Cả bộ mã sẽ có từ mã nên có số phương án sai là: . Để phát hiện ra sai thì số tổ hợp cấm phải không ít hơn số các phương án sai ta có điều kiện sau: Û Û Û 
Giới hạn trên được gọi là giới hạn Haming.
Định lý: Một mã bất kỳ dài với trọng số tối thiểu hoặc lớn hơn phải có số ký hiệu thử ít nhất là: .
 Mã vòng
Khái niệm: 
Mã vòng là loại mã mà một từ mã có thể được biểu diễn dưới dạng một đa thức: và có các đặc điểm sau:
Nếu là một từ mã thì tổ hợp được dịch chuyển một bậc cũng sẽ là một tổ hợp mã.
Những từ mã đều chia chẵn cho một đa thức gọi là đa thức sinh (Đa thức tạo mã, từ đa thức này có thể tạo ra các từ mã của mã vòng xuất phát từ mã đơn giản). Nếu bậc của mã đơn giản là k, bậc của mã vòng là n thì bậc của đa thức sinh là r=n-k.
Nguyên lý lập mã
	Nếu đa thức sinh được biểu diễn dưới dạng tổ hợp: , thì mã vòng có thể được biểu diễn bằng một ma trận sinh có dạng:
	Bằng những phép biến đổi tuyến tính ma trận G có thể được biến đổi về dạng chuẩn tắc sau:
Cách biểu diễn của ma trận sinh dưới dạng chuẩn tắc cho thấy: một từ mã gồm có hai phần, một phần có r ký hiệu thử và phần còn lại có k ký hiệu mang tin. Để xác định đa thức sinh cần dựa trên tính chất chia chẵn nhị thức .
Từ những tính chất trên có thể trực tiếp xây dựng ma trận sinh dạng chuẩn tắc bằng cách chia cho , các số thừa trong phép chia sẽ thành một ma trận , hợp với ma trận .
 tạo thành ma trận sinh 
Ví dụ : Xây dựng một mã vòng .
	Trước hết xác định đa thức sinh lấy trong những thừa số chung của nhị thức: 
, viết dưới dạng tổ hợp nhị phân là: 1101.
Xác định ma trận các số thừa của phép chia cho . Sau khi thực hiện phép chia nhị phân ta được ma trận: => 
Để có thể thực hiện một cách thuận tiện các thiết bị tạo mã và giải mã, cần có thuật toán lập và giải mã. Các thuật toán này đều dựa trên tính chất cơ bản là các từ mã chia chẵn cho đa thức sinh. Từ mã tìm được: . Trong đó .
Ví dụ : Tổ hợp mã đơn giản , . Đem chia cho ta được: . Vì vậy tổ hợp mã sẽ là: , viết dưới dạng tổ hợp mã nhị phân là 101110.
Nguyên lý giải mã
Đem chia từ mã nhận được cho đa thức , nếu phép chia chẵn chứng tỏ từ mã thu được là đúng, trong trường hợp phép chia còn số thừa thì chứng tỏ từ mã thu được có ký hiệu sai. Số thừa cho phép xác định vị trí của ký hiệu sai. Vec tơ gốc . Trong đó v: vec tơ thu được, e: vec tơ sai.
	Phương pháp thực hiện sửa sai có thể dựa trên ma trận phát hiện và sửa sai 
Ví dụ: Đối với mã vòng ta có các ma trận sau:
Các hàng của ma trận đại biểu cho các vec tơ sai, vị trí của số đơn vị cho biết vị trí của ký hiệu sai trong tổ hợp mã tuyến tính từ trái sang phải theo bậc từ cao giảm xuống thấp: . 
Ví dụ: hàng thứ ba của ma trận số đơn vị ở vị trí thứ 5 tương ứng với ký hiệu sai . Ma trận phát hiện sai và sửa sai của mã là:
Giả thiết thu được từ mã: 0111100, trong khi đó ở đầu phát đã gửi đi từ mã: 0110100. Như vậy trong quá trình truyền tin đã gây sai ký hiệu thứ 4 kể từ trái. Quá trinh phát hiện sai và sửa sai được thực hiện như sau: 
Đa thức sinh được chọn như trước .
Kiểm tra tổ hợp mã thu được là đúng hay sai bằng cách đem chia từ mã đó cho đa thức sinh . Sau khi thực hiện phép chia được số thừa là: 101, đem đối chiếu trong ma trận thấy số thừa thuộc hàng thứ tư tương ứng với vec tơ sai: 0001000, điều này cho thấy bit thứ tư của từ mã đã sai. Vec tơ gốc = 0111100+0001000 =0110100.
	Để thực hiện các sơ đồ tạo mã và giải mã vòng, sử dụng các mạch nhân, chia đa thức với đa thức. Các mạch này được xây dựng trên cơ sở các phần tử cơ bản của mạch như sau:
: Cộng mođun 2
: Nhân với một hệ số bằng ai
: Mạch ghi chuyển
Sơ đồ nhân hoặc chia một đa thức cho một đa thức là những dạng tổ hợp khác nhau của các phần tử cơ bản trên.
Sơ đồ nhân một đa thức với một đa thức: 
Output
Input
aj
aj+1
aj+2
aj+r-2
aj+r-1
br
br-1
br-2
b1
b0
Output
Input
1
2
3
r-1
r
-b0
-b1
-b2
-br-1
-br
Sơ đồ chia một đa thức cho một đa thức: 
Mục lục