Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
Chương 5

MÃ HOÁ KÊNH KIỂM SOÁT LỖI Ở VÔ TUYẾN SỐ
5.1. GIỚI THIỆU CHUNG
Các chủ đề được trình bầy trong chương
√ Các phương pháp mã hóa kênh kiểm soát lỗi
√ Các mã khối tuyến tính
√ Các mã xoắn
√ Các mã turbo và giải mã MAP
Mục đích chương
√ Hiểu nguyên tắc mã hóa kênh kiểm soát lỗi
√ Hiểu được hoạt động của các bộ mã hóa kênh kiểm soát lỗi điển hình nhất trong các
hệ thống thông tin vô tuyến hiện đại
√ Thiết kế được các bộ mã hóa kênh kiểm soát lỗi đơn giản.
√ Mô phỏng quá trình lập mã khối tuyến tính.
√ Mô phỏng quá trình mã mã và giải mã xoắn.
√ Mô phỏng hiệu năng mã khối tuyến tính và mã xoắn.
5.2. CÁC NGUYÊN TẮC MÃ HOÁ KÊNH KIỂM SOÁT LỖI
5.2.1. Khái quát về mã hóa kênh kiểm soát lỗi
Chức năng, vị trí của mã hoá kênh kiểm soát lỗi: Mã hoá kênh kiểm soát lỗi là
quá trình xử lý tín hiệu số được thực hiện sau nguồn tin số và trước điều chế nhằm
đạt được truyền tin số tin cậy bằng cách bổ xung có hệ thống các ký hiệu dư vào
luồng tin phát để phát hiện lỗi và sửa lỗi. Vì vậy, mục đích của mã hóa kênh kiểm
soát lỗi là:
√ Xác định phân đoạn của luồng số thu chứa lỗi. Thông báo cho nơi gửi hay nơi nhận
về lỗi.
√ Giảm thiểu xác suất không phát hiện lỗi.
√ Giảm được BER (hay xác suất lỗi) tại một Eb/N0 định trước.
√ Với BER cho trước giảm được Eb/N0, lượng giảm này được gọi là độ lợi của mã đối
với xác suất lỗi.

Lưu ý rằng: Khi thiết kế hệ thống truyền dẫn số cần lưu ý hai tham số: Tham số tín
hiệu phát và độ rộng băng tần của kênh truyền dẫn. Hai tham số này cùng với mật độ
phổ công suất tạp âm thu xác định Eb/N0.
√ Do BER là một hàm đơn trị của Eb/N0, nên khi Eb/N0 cố định thì có thể cải thiện
BER bằng cách dùng mã hoá kênh.
√ Dùng mã hoá kênh kiểm soát lỗi để dung hoà giữa BER yêu cầu và Eb/N0 dB (giảm
công suất phát, giảm giá thành phần cứng như sử dụng anten kích thước nhỏ, tái sử
dụng tần số....) chẳng hạn dùng mã hoá kênh kiểm soát lỗi trong các hệ thống thông
tin di động.
√ Để đánh giá lượng bit dư bổ sung phục vụ cho việc phát hiện và sửa lỗi của mã,
tham số tỉ lệ mã r được định nghĩa r = Rb/Rc (Do bổ sung các bit dư vào bản tin phát

-127-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
dẫn đến luồng bit ra bộ lập mã có tốc độ bít Rc cao hơn tốc độ bit đầu vào Rb, tăng
độ rộng băng tần ⇒ ảnh hưởng đến hiệu quả sử dụng phổ tần hệ thống).
Cơ chế phát hiện và sửa lỗi
√ Phát hiện bản tin bị lỗi, sau đó yêu cầu phía phát phát lại bản tin bị lỗi, vì thế cần có
một kênh hồi tiếp.
√ Phát hiện và sửa lỗi ở phía thu.
Kiểm soát lỗi để đảm bảo sự toàn vẹn của số liệu có thể được thực hiện bằng cách
hiệu chỉnh lỗi trước FEC (Forward Error Correction). Hình 5.1a minh họa mô hình của một
hệ thống sử dụng phương pháp này. Bộ mã hoá kênh nhận các bit của bản tin và bổ sung
thêm các bit dư theo một quy tắc được quy định trước, vì thế tạo ra luồng bit được mã hoá
có tốc độ cao hơn. Bộ giải mã sử dụng các bit dư để quyết định bit nào của bản tin là bit
thực tế đã được phát. Mục đích của việc kết hợp giữa mã hoá và điều chế (hình 5.1.b) là để
giảm thiểu ảnh hưởng của tạp âm. Nghĩa là giảm thiểu số lỗi giữa đầu vào của bộ mã hoá
(lấy từ nguồn tin) và đầu ra của bộ giải mã kênh (cung cấp cho người sử dụng).

Ngoài FEC còn có một phương pháp khác được gọi là yêu cầu phát lại tự động
(ARQ: Automatic Retransmission Request) cũng được sử dụng để giải quyết vấn đề kiểm
soát lỗi. ARQ sử dụng các bit ký hiệu dư để phát hiện lỗi. Dựa trên kết quả phát hiện lỗi
máy thu yêu cầu phát lại bản tin bị mắc lỗi, vì thế cần phải có một kênh hồi tiếp.

Hình 5.1. Mô hình đơn giản của hệ thống truyền dẫn số: a) Mã hóa và điều chế kênh riêng
biệt; b) Mã hóa kênh và điều chế kết hợp.
Khi bổ sung các bit dư để phát hiện, sửa lỗi còn dẫn đến tăng độ rộng băng thông.
Ngoài ra khi sử dụng mã hoá kênh còn làm tăng tính phức tạp của hệ thống, nhất là việc
thực hiện giải mã kênh ở máy thu. Như vậy, khi lựa chọn sử dụng mã hoá kênh cần phải
cân nhắc về độ rộng băng tần và mức độ phức tạp.
Yêu cầu về phát hiện và sửa lỗi trước hết được xác định bởi loại thông tin được phát.
Sơ đồ khối chức năng của một máy phát sử dụng mã hoá kênh được cho ở hình 5.2, nó cho
thấy: (1) Tốc độ bit ở đầu ra của bộ mã hoá R luôn luôn lớn hơn tốc độ bit,Rb.; (2) Tỷ lệ mã
có thể được định nghĩa là: Tỷ lệ mã = Rb/R.

-128-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số

bps: bit trên giây; sps: ký hiệu trên giây
Hình 5.2. Sơ đồ khối của máy phát sử dụng mã hóa kênh
5.2.2. Nguyên tắc mã hóa kênh kiểm soát lỗi
Ta xét một số nguyên tắc cơ sở để thực hiện mã hoá kênh kiểm soát lỗi. Có thể phát
biểu vấn đề cơ bản khi thực hiện mã hoá kênh này như sau: ta muốn chuyển đổi m bản tin
có thể có vào m từ mã . Các từ mã này phải thỏa mãn các mục tiêu về phát hiện và sửa lỗi.
Chẳng hạn ta xét một bản tin bao gồm 3 bit. Với 3 bit này sẽ tồn tại 23 = 8 bản tin có thể có.
Ta muốn thay thế từng bản tin nói trên bằng một từ mã. Như đã được đề cập ở trên để đạt
được điều này ta sử dụng các bit dư. Khi này các từ mã sẽ dài hơn bản tin tương ứng mã từ

đó.
Ta có thể phân tích các khả năng phát hiện lỗi và sửa lỗi cuả các mã dư khác nhau
bằng cách trước hết định nghĩa khoảng cách Hamming giữa hai từ mã. Khoảng cách
Hamming giữa hai từ mã bất kỳ có cùng độ dài được định nghĩa là số vị trí mà ở đó chúng
khác nhau. Ta có thể mô tả khoảng cách Hamming này bằng một không gian nhiều chiều
(hình 5.3).

Hình 5.3. Trình bầy từ mã ba bit ở không gian ba chiều
Giả sử ta có một bản tin nguyên tố bao gồm một số "0" hay một số "1". Khi bản tin là
0 ta phát đi "000", còn khi nó là "1" ta phát đi "111". Từ hình lập thể hình 5.3 ta thấy
khoảng cách giữa hai từ mã đúng nói trên là bằng 3 vì để chuyển từ một từ mã này sang từ
mã khác phải chuyển dịch theo ba cạnh.
Tại đây ta lại giả thiết rằng bản tin bao gồm ba bit và sử dụng tất cả các tổ hợp bit
của ba bit này để truyền bản tin. Từ hình vẽ 5.3 ta thấy tất cảc các đỉnh của hình lập thể
đều được sử dụng để biểu thị các bản tin. Mọi lỗi xẩy ra ở một trong ba bit đều dẫn đến
chuyển vào một đỉnh bên cạnh và sẽ dẫn đến lỗi. Trong trường hợp này nếu khoảng cách
của từ mã phát và từ mã thu là một thì chắc chắn sẽ mắc một lỗi vì từ thu được là một trong
số các bản tin có thể có. Ta cải thiện tình trạng trên bằng cách tăng khoảng cách. Chẳng
hạn các từ mã: 0000, 0011, 0101, 1001, 1010, 1100, 1111, đều có khoảng cách tối thiểu là
2. Đối với bốn từ mã này ta cần một hình không gian có 16 đỉnh để biểu diễn. Hay tổng
quát ta cần một không gian n chiều.

-129-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
Giả sử xẩy ra một lỗi ở một vị trí của từ mã bốn bit nói trên: ta thu được 1000 chẳng
hạn. Máy thu có thể nhận định rằng từ mã này có thể là một trong hai từ mã gần từ thu
nhất : 0000 hay 1010.
Trường hợp này chỉ có thể phát hiện được lỗi chứ không sửa được lỗi. Bây giờ ta xét

các từ mã gồm: 01111, 01000 và 10011. Khoảng cách cực tiểu giữa chúng bây giờ là 3.
Nếu thu được một từ mã 01001 thì một máy thu thông minh có thể nhận định từ mã được
phát phải là 01000 vì đây là từ mã gần với từ thu được nhất (có khoảng cách nhỏ nhất =1).
Bây giờ giả thiết từ thu được là 01011, máy thu chỉ có thể nhận định rằng từ phát có thể là
một trong hai từ: 01000 và 10011, vì khoảng cách cuả từ thu với hai từ này đều bằng 2.
Vậy trong trường hợp này máy thu chỉ có thể phát hiện được lỗi chứ không sửa được lỗi.
Khi này ta nói rằng mã trên cho phép phát hiện lỗi kép và sửa lỗi đơn.
Nếu một tin có độ dài k bit ⇒ có 2k bản tin có thể có. Mong muốn thay thế từng bản
tin nói trên bằng một từ mã tương ứng. Theo đó cần sử dụng các bit dư vì thế độ dài từ mã
sẽ dài hơn độ dài bản tin.
Để phân tích khả năng phát hiện và sửa lỗi của mã trước hết định nghĩa khoảng cách
Hamming giữa hai từ mã.
Khoảng cách Hamming: Khoảng cách Hamming giữa hai từ mã bất kỳ có cùng độ
dài được định nghĩa là số vị trí khác nhau giữa chúng.
Khả năng phát hiện và sửa lỗi
Nếu ký hiệu: d m là khoảng cách Hamming cực tiểu giữa các từ mã có thể có trong
tập mã; t Detec là số lỗi phát hiện được; t Corr là số lỗi có thể sửa được thì chúng phải thoả
mãn các biểu thức (5.1) và (5.2) dưới đây.
Khả năng phát hiện t Detec lỗi
d m = t Detec + 1

(5.1)

⇔ t Detec = d m − 1

Khẳ năng sửa t Corr lỗi
d m ≥ 2t Corr + 1
⇔ t Corr ≤

dm −1

2

(5.2)

Mã kênh được phân thành hai loại mã khối tuyến tính và mã xoắn.
5.2.3. Đô lợi mã hóa
Độ lợi mã hóa được định nghĩa là việc sử dụng mã hóa kênh sửa lỗi cho phép giảm tỷ
số Eb/N0 đi bao nhiêu lần mã vẫn giữ nguyên xác suất lỗi bit. Độ lợi mã hóa G được biểu
diễn ở dB như sau:
E 
G ( dB ) =  b  [dB]  N 0 u

 Eb 

 [dB]
 N 0 c

trong đó chỉ số "u" và "c" ký hiệu cho không mã hóa và mã hóa tương ứng.

-130-

(5.3)


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
PB
Co d ed

A
F

C

B

D
E
Un co d ed

Eb / N 0 (dB)

Hình 5.4. Minh họa độ lợi mã hóa kênh
5.3. MÃ KHỐI TUYẾN TÍNH
Khái niệm cơ bản
Khối bản tin: Luồng thông tin được chia thành các khối có độ dài bằng nhau (độ
dài k bit) được gọi là các khối bản tin.
Từ mã: Các bit nhận được ở đầu ra của bộ lập mã tương ứng với mỗi khối bản tin
đầu vào được gọi là từ mã. Mỗi từ mã có độ dài n bit
Các bit kiểm tra: là các bit dư được bổ xung vào các khối bản tin theo một thuật
toán nhất định tuỳ vào loại mã được dùng. Các bít kiểm trs có độ dài (n-k) bit.
Mã khối được gọi là tuyến tính nếu thoả mãn sự kết hợp tuyến tính bất kỳ hai từ mã
nào đó cũng là một từ mã thuộc mã đó. Trong trường hợp nhị phân tổng của hai từ mã bất
kỳ cũng là một từ mã.
Các tham số đặc trưng cho mã khối tuyến tính
Độ dài khối bản tin k.
Độ dài từ mã n.
Khoảng cách Hamming cực tiểu d m .
Tỉ lệ mã r =

k
n


Sơ đồ khối tổng quát của bộ mã hoá khối tuyến tính (n,k) được cho ở hình 5.5.

Hình 5.5. Sơ đồ bộ lập mã khối tuyến tính (n,k)
Hoạt động của bộ lập mã được biểu diễn toán học ở dạng ma trận tạo mã G hay đa
thức tạo mã g(x).
Tóm tắt: Lập mã khối thực hiện ánh xạ (sắp xếp) chuỗi k bit đầu vào thành chuỗi n bit đầu
ra có các đặc điểm sau:
Từ mã đầu ra bộ lập mã C chỉ phụ thuộc vào chuỗi bit đầu vào m hiện thời và ma
trận tạo mã G (hay đa thức tạo mã g(x)) mà không phụ thuộc vào chuỗi đầu vào
trước đó.

-131-


Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s
Trong mó khi tuyn tớnh, cỏc t mó to thnh khụng gian con k chiu trong khụng
gian n chiu (n,k).
Cỏc mó khi tuyn tớnh c mụ t di dng ma trn to mó G cú kớch thc kìn,
mi t mó u ra C c vit dng.

C1ìn =

m1ì k .G kì n
số cột của ma trận m phải bằng số hàng của ma trận G

trong ú m l chui d liu nh phõn u vo b mó hoỏ cú di k bit, lu ý rng
chui n bit 0 cng l mt t mó thuc mó khi tuyn tớnh (n,k).
5.3.1. Ma trn to mó v ma trn kim tra chn l
Ma trn to mó G

Nu a vo b lp mó mt khi bn tin k bit, thỡ ta s nhn c u ra b lp mó
mt t mó cú di n bit dng chui bit sau
Hớng truyền

c = [ c 0 , c1 ,..., c n 1 ]1ìn
= b0 , b1 ,.., b n k 1 , m 0 , m1 ,..., m k 1
( n-k ) bít kiẻm tra chắn lẻ

k bit bản tin

n bit dầu ra bộ mã hoá

trong ú: mj l cỏc bit ca khi bn tin; bi l cỏc bit kim tra. Lu ý rng, cỏc bit cú ch s
cao l cỏc bit cú ngha ln hn v c truyn trc.
Nh vy, u vo b lp mó cú 2k khi bn tin cú th cú, tng ng u ra b lp mó
cú 2k t mó c s dng trong s 2n t mó cú th cú (ng vi mi khi bn tin k bit u
vo nhn c mt t mó n bit u ra)
Biu din k bit bn tin vo dng vector 1ì k
m = [ m 0 , m1 ,..., m k 1 ]1ìk
(5.4)
Biu din n-k bit chn l vo dng vector 1ì (n-k)
b = [ b 0 , b1 ,..., b n k 1 ]1ì( n k )

(5.5)

Biu din n bit ra dng vector 1ì n
c = [c 0 , c1 ,..., c n 1 ]1ìn

(5.6)


trong ú
bi
(n k ) bit
ci =
mi + k n
k bit

i = 0,1, 2,...., n k 1
i = n k, n k + 1,......, n 1

(5.7)

Cỏc vector núi trờn l cỏc vector hng, cỏc bit cú ch s cao hn l cỏc bit cú trng s
cao v c truyn trc, (n-k) bit kim tra chn l c xỏc nh bng tng tuyn tớnh ca
k bit bn tin theo tng quan tng quỏt sau

-132-


Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s

bi

= p i 0 m 0 + p i1m1 + ... + p ij m j + ... + p i , k 1 m k 1

bit kiểm tra thứ i

( n k ) bit kiểm tra chẵn lẻ là tổng tuyến tính của k bit bả n tin

(5.8)


k -1

= p ij m j
j= 0

1
0

trong ú p ij =

i = 0,1,...,n-k-1
và
Nếu b i không phụ thuộc vào m j
j = 0,1,2,...,k-1
Nếu b i phụ thuộc vào m j

Biu din cỏc phng trỡnh trờn gn hn dng ma trn sau

b

= mP

b1ì(n k ) = m1ìk Pk ì(n k )

(5.9)

trong ú P l ma trn k ì (n-k) c xỏc nh theo

p 0,0

p
0,1
..
P=
..
..

p 0,k 1

p1, 0
p1,1
..
..
..
p1,k 1

p n k 1, 0
p n k 1,1
..
..

..
..
..
..

... p n k 1,k 1 kì( n k )

...
...


(5.10)

Các phần tử ma trận p ij , trong dó i là chỉ số cột, j là chỉ số hàng

vi i = 0, 1, 2,..,n-k-1 l ch s ct v j = 0, 1, 2,....k-1 l ch s hng.

b1ì(n k ) = m1ìk Pkì(n k )
p1,0 ... p n k 1,0
p 0, 0
p

p
...
p
1,1
n k 1,1
0,1
..
..
..
..
= [m0 , m1 ,..., m k 1 ]1ìk

..
..
..
..



..
..
..
..


p
p
...
p

n k 1,k 1
0,k 1 1,k 1
kì( n k ); Các phần tử ma trận p ij
trong dó i là chỉ số cột,j là chỉ số hàng
k -1

bi = p ijm j
j= 0

-133-


Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s
T cỏc phng trỡnh (5.4) ( 5.8) biu din c l mt vector hng c phõn on
theo m v b nh sau:


c=
b

:
(n k) bit kiểm tra

m
k bit bản tin



1ìn

(5.11)

từ mã đầu ra n bit

Thay (5.9) vo (5.11) v a tha s chung m ra ngoi thỡ
c1ìn = m1ìk Pkì(n k ) Ikìk

(5.12)

G kìn

trong ú Ik l ma trn n v
1 0 . .
0 1 . .

Ik = . . . .

. . . 1
0 0 . 0


0
0
.

0
1 kì k

(5.13)

Ma trn to mó G c xỏc nh dng


G=


P


Ik
kìn
k ìk

:

k ì( n k )

(5.14)

Khi ny cú th vit biu thc (5.12) dng sau
C1ìn =


m 1ì k .G kì n

(5.15)

số cột của ma trận m phả i bằng số hàng của nma trận G

Ma trn kim tra chn l H
Gi s H l ma trn (n-k)ìn c xỏc nh bi

H = I nk




( n k )ìn
kích thớc (n-k)ì k
PT

(5.16)

trong ú PT l ma trn chuyn v ca P cú kớch thc (n-k)ìk, nhn c t P bng cỏch
chuyn i ct thnh hng. Tng ng ta cú th nhõn cỏc ma trn phõn on nh sau

[

HG T = I n k

P T


: P T ...
I k


]

(5.17)

= I n k P T + P T I k
= PT + PT
=0

Vy: H.G T = 0 G.H T = 0
Sau khi nhõn c hai v ca phng trỡnh (5.15) vi HT ta nhn c

-134-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
c.H T = mG.H T = 0

(5.18)

Ma trận H được gọi là ma trận kiểm tra chẵn lẻ
Như vậy, ma trận tạo mã G được dùng để tạo mã ở phía phát, ma trận kiểm tra chẵn
lẻ H được dùng để giải mã ở phía thu.
Syndrome và phát hiện lỗi
Khái niệm
Syndrome cho phép xác định từ mã thu có bị mắc lỗi hay không và thậm chí cả mẫu
lỗi khi thỏa mãn điều kiện (5.2). Ta xét quá trình giải mã.

Xét mã (n, k) với ma trận sinh G tương ứng ta có ma trận kiểm tra H. Khi truyền một
từ mã qua kênh có tạp âm, từ mã thu y là tổng của vector phát c và vector mẫu lỗi e nghĩa
là
(5.19)
y = c+e
Vector phát đi:
c = (c0, c1, c2....cn-1)
e = (e0, e1, e2....en-1)
Vector mẫu lỗi:
Nếu ei = 1 thì vector thu bị lỗi ở vị trí i, ngược lại nếu ei = 0, vector thu không bị lỗi ở
vị trí thứ i đó ( i=1,2..,n).
Máy thu có nhiệm vụ giải mã vector c từ vector thu y (khôi phục c từ y). Để giải mã,
ta thực hiện tính toán Syndrome. Đặc điểm của Syndrome là chỉ phụ thuộc vào mẫu lỗi e
mà không phụ thuộc vào từ mã c được phát và được xác định bởi:

S = y.H T = e.H T + C.H T = e.H T
=0

(5.20)

Các thuộc tính của Syndrome
Thuộc tính 1: Syndrome chỉ phụ thuộc vào mẫu lỗi chứ không phụ thuộc vào từ mã
được phát.
Thuộc tính 2: Tất cả các mẫu lỗi khác nhau nhiều nhất một từ mã đều có cùng
Syndrome.
Với k bit bản tin ta có 2 k vector từ mã khác nhau được biểu thị bởi ci , i = 0,1,..., 2k − 1 .
Tương ứng với một mẫu lỗi e bất kỳ có thể định nghĩa 2 k vector ei khác nhau như sau:
ei = e + ci , i = 0,1, 2,3,..., 2 k − 1
(5.21)
chỉ khác nhau nhiều nhất một từ mã.

Tập các vector {ei , i = 0,1,..., 2k − 1} theo định nghĩa trên được gọi là Coset của mã.
Nói cách khác, một Coset có đúng 2 k phần tử khác nhau nhiều nhất một từ mã. Số các
tổ hợp từ mã có thể có của một mã khối tuyến tính (n,k) là 2 n trong đó chỉ có một bộ 2 k
từ mã được dùng. Vậy tổng số bộ 2 k từ mã có thể có là 2 n − k (nghĩa là có 2n-k bộ 2 k từ mã)
và tương ứng sẽ có 2 n − k Coset có thể có (trong đó chỉ có một Coset là tương ứng với bộ từ
mã được dùng).
Thuộc tính 3: Syndrome S là tổng các cột của ma trận H tương ứng với nơi xẩy ra
lỗi.
Thuộc tính 4: Bằng cách giải mã Syndronme, một mã khối tuyến tính (n,k) có thể
sửa được t lỗi ở một từ mã, nếu n và k thoả mãn giới hạn Hamming
sau đây.

-135-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
t
n
2 n − k ≥ ∑  
i =0  i 

(5.22)

n

trong đó   là hệ số nhị thức được tính bởi.
i
 

n

n!
  =
 i  (n − i )!i!

(5.23)

Mã nhị phân thoả mãn giới hạn Hamming theo dấu bằng được gọi là mã hoàn hảo.
Ta thấy rằng, một mình Syndrome không thể xác định được mẫu lỗi e. Thực tế nói
chỉ nhận ra được Coset chứa mẫu lỗi. Mẫu lỗi có khẳ năng xẩy ra nhất trong Coset được
đặc trưng bởi Syndrome S là mẫu lỗi có xác suất lớn nhất (trong trường hợp coi rằng tạp
âm của kênh là cộng).

⇒ Vậy, ta có thể tiến hành thuật toán giải mã như sau:

√ Tính Syndrome S = y.H T đối với vector thu y.
√ Trong tập Coset được đặc trưng bởi Syndrome trên, chọn mẫu lỗi có xác suất lớn
nhất gọi là e0.
√ Tính vector mã cho đầu ra c' = y + e 0

Trọng lượng Hamming cực tiểu
Trọng lượng Hamming cực tiểu của một từ mã là tổng số các vị trí bit khác không
trong từ mã, chính là khoảng cách Hamming giữa một từ mã khác không với từ mã toàn
không. Ta lưu ý rằng, tham số quan trọng của mã khối tuyến tính (xác định khả năng phát
hiện và sửa lỗi của nó) là khoảng cách Hamming cực tiểu của mã, được định nghĩa là
khoảng cách Hamming cực tiểu giữa hai từ mã riêng biệt bất kỳ. Khoảng cách cực tiểu của
mã được ký hiệu dmin, d min = min d H ( ci , c j )
i≠ j

Đối với mã tuyến tính, khoảng cách cực tiểu bằng với trọng lượng cực tiểu của mã
được định nghĩa là w min = min w ( ci ) , nghĩa là số các bit “1” ít nhất trong bất kỳ từ mã khác

ci ≠ 0

không nào đó.
Do tính chất của mã khối tuyến tính là tổng (hoặc hiệu, ở số học Modul2 thì phép
cộng & trừ là như nhau) hai từ mã bất kỳ luôn là một từ mã thứ ba của mã ⇒ nên trọng
lượng Hamming cực tiểu của các từ mã khác không của mã khối tuyến tính chính bằng
khoảng cách Hamming cực tiểu.
Ví dụ minh họa được cho VD PL5.1 trong phụ lục 5A.
5.3.2. Đa thức tạo mã
Mã vòng (Cyclic Codes) là một tập con của mã khối tuyến tính, được dùng rộng rãi
để phát hiện lỗi và sửa lỗi trong các hệ thống truyền thông. Lí do chính mà được dùng rộng
rãi là dễ thực hiện bằng các mạch ghi dịch hồi tiếp tuyến tính (LFSR: Linear Feedback
Shift Register).
Định nghĩa: Một mã được gọi là mã vòng nếu thỏa mãn 2 thuộc tính cơ bản: (1)
Thuộc tính tuyến tính, tổng của hai từ mã cũng là một từ mã; (2) Thuộc tính vòng,
mọi dịch vòng của một từ mã cũng sẽ là một từ mã.

-136-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
Biểu diễn từ mã
Dưới dạng vector gồm n thành phần:
c = (c 0 , c1 , c 2 ,...., c n −1 )

(5.24)

Dưới dạng đa thức bậc (n-1):
n −1


c(x) = c0 + c1x + c 2 x 2 + .... + cn −1x n −1 = ∑ ci x i

(5.25)

i =0

trong đó ci=0/1 và mỗi luỹ thừa của x tương ứng với dịch vòng 1 bit theo thời gian. Vì thế
khi nhân đa thức (5.25) với x có nghĩa là dịch vòng một bít sang phải, vì vậy x n −1 phải bằng
1 và bít ngoài cùng bên phải chuyển thành bit ngoài cùng bên trái. Quá trình nhân và dịch
vòng như vậy được biểu diễn như sau:

(

)

x.c( x ) mod x n − 1 = c n −1 + c 0 x + .... + c n − 2 .x n −1

(5.26)

trong đó mod có nghĩa là chia chỉ lấy phần dư.
Tương tự nếu nhân biểu thức (5.25) với x2 có nghĩa dịch vòng sang phải hai bit và
quá trình này được biểu diễn như sau:

(

)

x 2 .c( x ) mod x n − 1 = c n − 2 + c n −1 x + .... + c n −3 .x n −1

(5.27)


chØ cã c i dÞch chuyÓn cßn bËc cña x kh«ng dÞch

Mã vòng (n,k) được đặc tả bởi tập đầy đủ các đa thức bậc (n-1) hay thấp hơn và nhận
một đa thức bậc thấp nhất (n-k) làm thừa số. Thừa số đặc biệt này được gọi là đa thức tạo
mã g(x) của mã này. Đa thức tạo mã g(x) tương ứng với ma trận tạo mã G được biểu diễn
như sau:
Đa thức tạo mã: Ký hiệu g(x) là đa thức tạo mã được biểu diễn bởi.
g ( x ) = g 0 + g 1 x + g 2 x 2 + .... + g n − k .x n − k
n −k

(5.28)

= ∑ gixi
i =0

Đa thức bản tin: Ký hiệu m(x) là đa thức của khối bản tin k bit được biểu diễn bởi:
m( x ) = m 0 + m 1 x + m 2 x 2 + .... + m k −1 x k −1
k −1

(5.29)

= ∑ mixi
i=0

Các thuộc tính của đa thức tạo mã của mã vòng
Thuộc tính 1: Đa thức tạo mã của một mã vòng (n,k) là đơn nhất ở ý nghĩa rằng, nó
là đa thức từ mã bậc (n-k) cực tiểu duy nhất.
Thuộc tính 2: Mọi bội số của đa thức tạo mã g(x) là một đa thức từ mã mới, được
xác định là: c( x ) = a ( x ).g ( x ) mod(x n − 1) , trong đó a(x) là một đa thức

của x.
Hay: Một đa thức bậc n-1 hay thấp hơn là một đa thức từ mã khi và
chỉ khi nó là bội số của g(x)
⇒ Ta sử dụng thuộc tính 2 để xác định đa thức tạo mã c(x):
Nếu cho một đa thức tạo mã g(x) để mã hóa một khối bản tin (m 0 , m 1 , m 2 ,..., m k −1 )
vào một mã vòng hệ thống ở dạng

-137-


Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s
c = (c 0 , c 1 , c 2 ,...., c n 1 )


= b 0 , b 1 ,.., b n k 1 , m 0 , m 1 ,..., m k 1 v cho a thc bn tin


k bit bả n tin
( n - k ) bít kiẻm tra chắn lẻ

n bit dầu ra bộ mã hoá

m( x ) = m 0 + m 1 x + m 2 x 2 + .... + m k 1 x k 1
k 1

(5.30)

= mixi
i=0


thỡ theo cu trỳc c nh ngha cho mt t mó, bit u ca bn tin m k 1 l h s ca x n 1
trong a thc ca t mó. m bo c yờu cu ny nhõn a thc bn tin m(x) vi x n k
nhn c
x n k .m( x ) = m 0 x n k + m 1 .x n k +1 + ... + m k 1 .x n 1

(5.31)

Nu chia a thc x n k .m( x ) cho a thc to mó g(x), thỡ nhn c thng a(x) v
phn d b(x) nh sau:
x n k m( x )
b( x )
= a (x ) +
g(x )
g(x)

(5.32)

x n k .m( x ) = a ( x ).g ( x ) + b( x )

(5.33)

trong ú
k 1

a(x) = a 0 + a1x + a 2 x 2 + .... + a k 1.x k 1 = a i .x i

(5.34)

i=0


b(x) = b0 + b1x + b 2 x 2 + .... + b n k 1.x n k 1 =

n k 1

b .x
i=0

i

i

(5.35)

Trong s hc modul 2 thỡ b(x)=-b(x), nờn (5.33) c vit li nh sau
b( x ) + x n k .m( x ) = a ( x ).g ( x )

(5.36)

a thc ny l bi s ca g(x). Vỡ th theo thuc tớnh 2 nú biu th mt a thc t mó
ca mó tun hon (n,k) c to bi g(x).
Vy t mó u ra b lp mó c biu din di dng a thc sau

c(x) =

b(x)
Bậc luôn nhỏ hơn
bậc của g(x): (n-k)

x n k .m(x)


+

Chỉ chứa các x có luỹ thừa
lớn hơn (n k)

(5.37)

Bc ca phn d b(x) luụn nh hn bc ca s chia: n-k. Thnh phn x n k .m( x ) ch
cha cỏc x cú lu tha bng hay ln hn n-k vic cng hai thnh phn ny nh
phng trỡnh (5.37) s khụng lm thay i bt c thnh phn no trong biu thc.
Túm tt: T kt qu phõn tớch trờn, cỏc bc mó hoỏ cho mt mó vũng (n,k) nh sau:
Nhõn a thc bn tin m(x) vi x n k nhn c x n k .m( x )
Chia x n k .m( x ) cho g(x) c phn d b(x).

-138-


Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s
Cng b(x) vi x n k .m( x ) nhn c a thc t mó c(x).
Thuc tớnh 3: a thc to mó g(x) v a thc kim tra chn l h(x) l cỏc tha s
ca a thc 1 + x n nh sau:
h ( x ).g ( x ) = 1 + x n

(5.38)

Trong ú h(x) l mt a thc kim tra chn l c nh ngha bi:

(

)


h ( x ).g ( x ) mod x n 1 = 0

(5.39)

hay t thuc tớnh 2 nhn c

(

)

h ( x ).c( x ) mod x n 1 = 0

(5.40)

Thuc tớnh ny cho ta c s chn a thc to mó hay a thc kim tra chn l. Ta
cú th phỏt biu rng: (1) nu a thc g(x) l mt a thc bc n-k ng thi l mt tha s
ca 1 + x n thỡ nú l a thc to mó ca mt mó vũng (n,k); (2) nu h(x) l mt a thc bc
k v ng thi l tha s ca 1 + x n thỡ nú l a thc kim tra chn l ca mt mó vũng
(n,k).
Mi tha s ca 1 + x n cú bc (n-k) (s cỏc bớt chn l) u cú th c s dng nh
mt a thc to mó. Khi giỏ tr n ln, a thc 1 + x n cú th cú nhiu tha s bc (n-k).
Chỳng cú th to ra mó vũng tt hoc khụng tt.
Vớ d minh ha c cho VD PL5.2 trong ph lc 5A
S b mó hoỏ vũng
Trong phn trc ó xột cỏc th tc mó hoỏ vũng (n,k) gm ba bc sau:
Nhõn a thc bn tin m(x) vi x n k nhn c x n k .m( x )
Chia x n k .m( x ) cho g(x) c phn d b(x).
Cng b(x) vi x n k .m( x ) nhn c a thc t mó c(x).
B mó hoỏ thc hin ba bc ny c cho hỡnh 5.6 gm mt thanh ghi dch (n-k)

tng cú mch hi tip tuyn tớnh.
CM1
CM1
2
1

g1

F-F

g2

F-F

gn-k-1

F-F

F-F

F-F

Các bit
kiểm
tra
chẵn lẻ

CM2
CM2
1, " nối trực tiếp"

gi =
0, " không nối"

2

Các bit bản tin

x n k .m( x )

Hỡnh 5.6. B lp mó vũng (n,k) vi a thc to mó
g ( x ) = 1 + g 1 .x + g 2 .x 2 + .... + g n k 1 .x n k 1 + x n k

Cu to gm:

-139-

1

Từ mã
đầu ra
đa vào
kênh


Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s
Cỏc Flip-Flop (hay cỏc Triger D, cỏc phn t tr), cỏc Flip-Flop ny nhn mt trong
hai trng thỏi 0 hay 1. Mt ng h ngoi (khụng v trong hỡnh) iu khin hot ng tt
c cỏc Flip-Flop. Mt tp cỏc mch cng Modul2 thc hin cng Modul2 gia u ra ca
1, " nối trực tiếp"
.

0, " không nối"

Flip-Flop vi mch hi tip. Cỏc b nhõn nhõn chỳng vi nhau. g i =

Hai chuyn mch CM1 v CM2. Mi khi cú sn tng ca xung ng h, ni dung ca
thanh ghi dch c dch i mt v trớ theo chiu mi tờn (dch sang phi ).
Hot ng:
Trc khi dch k bit bn tin vo thanh ghi dch, ni dung ca thanh ghi dch ny c
xoỏ v khụng.
Trong khong thi gian k chu k xung ng h u: k bit bn tin (m0, m1,.....,mk-1)
tng ng vi x n k .m( x ) c dch ln lt vo kờnh ng thi chỳng cng c
dch vo thanh ghi dch hi tip tuyn tớnh LFSR to ra (n-k) bit kim tra chn l
(cỏc bit chn l ny cú cựng giỏ tr nh cỏc h s ca phn d b(x)) Vỡ vy cỏc
khoỏ chuyn mch CM1, CM2 u v trớ di (v trớ 1).
Trong khong thi gian (n-k) chu k xung ng h tip theo: Ni dung ca thanh
ghi dch hi tip tuyn tớnh LFSR cha (n-k) bit kim tra chn l c dch vo kờnh
truyn Vỡ vy, cỏc khoỏ chuyn mch CM1 v CM2 chuyn lờn v trớ trờn (v trớ
2).






Hớng truyền


Kt qu t mó u ra cú cu trỳc c = b 0 , b1 ,.., b n k 1 , m 0 , m1 ,..., m k 1
( n-k ) bít kiểm tra chẵn lẻ k bit bản tin đợc dịch vào kênh
xác định bởi nội dung trong k chu kỳ xung đồng hồ đầu

đợc
đồng thời đợc dịch vào LFSR
của LFSR dợc dịch vào
kênh ở n-k chu kỳ xung

đồng hồ sau

Từ mã n bit đầu ra bộ mã hoá

Vớ d minh ha c cho VD PL5.3 trong ph lc 5A.
Syndrome
Gi s t mó c = (c0,c1,c2,....,cn-1) c truyn qua kờnh cú tp õm, nhn c t mó y
= (y0,y1,y2,...,yn-1). gii mó t mó ny trc ht ta tớnh Syndrome cho t mó thu. Nu
Syndrome bng khụng thỡ t mó thu khụng b li, ngc li nu Syndrome khỏc khụng thỡ
t mó ny b mc li. i vi mó vũng dng h thng, thỡ vic tớnh toỏn Syndrome s d
dng.
Gi s t mó thu y, c trỡnh by dng a thc sau.
y = y 0 + y 1 x + .... + y n 1 x n 1

(5.41)

Tớnh Syndrome bng cỏch chia a thc y(x) cho a thc to mó g(x). Nu a(x) l
thng, s(x) l phn d ca kt qu chia, thỡ y(x) c biu din nh sau:
y ( x ) = a ( x )g ( x ) + s ( x )

(5.42)

phn d s(x) l mt a thc bc (n-k-1) hay thp hn c gi l a thc Syndrome. Nu
a thc s(x) khỏc khụng thỡ t mó thu b li.


-140-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
Sơ đồ bộ tính toán Syndrome giống như sơ đồ bộ lập mã chỉ khác ở chỗ các bit của
từ mã thu được đưa vào (n-k) tầng của thanh ghi dịch có hồi tiếp (xem hình 5.7). Sau khi
các bit của từ mã thu được dịch hết vào thanh nghi dịch, thì nội dung của thanh nghi dịch
này xác định Syndrome S. Một khi biết được S sẽ xác định được mỗi lỗi và đưa ra được
quyết định sửa như đã xét ở phần trước.

Hình 5.7. Bộ tính Syndrome của mã vòng (n,k) dựa trên đa thức tạo mã
g ( x ) = 1 + g 1 .x + g 2 .x 2 + .... + g n − k −1 .x n − k −1 + x n − k

Ví dụ minh họa được cho ở VD PL5.4 trong phụ lục 5A.
5.4. MÃ XOẮN
5.4.1. Mở đầu
Các tham số đặc trưng của mã khối tuyến tính gồm: n, k, và một ma trận G hay
đa thức tạo mã.
k là độ dài của khối bit bản tin đầu vào bộ lập mã
n là độ dài (tổng số ký hiệu) đầu ra của bộ lập mã
r = k/n là tỉ lệ mã, đánh giá lượng dư bổ sung
Các tham số đặc trưng của mã xoắn là: n, k, K, và một đa thức tạo mã.
k là số bit dịch vào bộ lập mã tại cùng một thời điểm.
n là số bit ở đầu ra bộ lập mã khi cho k bit đồng thời vào bộ lập mã.
K là độ dài hạn chế, là số lần dịch cực đại của một nhóm k bit bản tin vào mà
nhóm k bit này vẫn còn gây ảnh hưởng tới đầu ra bộ lập mã.
r = k/n là tỉ lệ mã (kbộ lập mã khối.
Đặc tính quan trọng của mã xoắn khác biệt so với mã khối là bộ lập mã của
chúng có nhớ, nên quá trình tạo ra n phần tử đầu ra của các bộ lập mã này không

chỉ phụ thuộc vào k bit đầu vào mà còn phụ thuộc vào (K-1) tổ hợp k bit đầu vào
trước đó.
5.4.2. Lập mã xoắn
Sơ đồ khối tổng quát
Sơ đồ tổng quát của một bộ lập mã xoắn được cho ở hình 5.8 gồm: (1) M bộ nhớ
(tầng nhớ) mỗi tầng có k phần tử nhớ (k bit ở mỗi tầng); (2) n bộ tạo hàm đại số tuyến tính
ở dạng cộng Modul-2 tương ứng với số các bit đầu ra bộ lập mã cho mỗi lần dịch k bit tin
vào đồng thời; (3) quan hệ giữa K và M được xác định là:

-141-


Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s
M + 1, nếu đầu vào bộ nhớ thứ nhất đợc nối đến bộ cộng cơ số hai
trong ú di
K=
nếu đầu vào bộ nhớ thứ nhất không đợc nối đến bộ cộng cơ số hai
M,

hn ch K c nh ngha l s ln dch cc i ca mt nhúm k bit u vo ng thi m
nhúm k bit ny vn cũn nh hng ti u ra b lp mó.
M bộ nhớ (thanh ghi dịch)
với k phần tử ở mỗi bộ nhớ

1
Chuỗi và o
(mỗi lần
dịch k bit)

1

2

M

....

k

1

2

....

k

1

2

....

n bộ cộng Modul-2

Chuỗi từ
mã ra

Hỡnh 5.8. S tng quỏt ca mt b lp mó xon vi t l mó k/n
Nguyờn lý hot ng

Mi khi dch ng thi k bit vo b lp mó hoỏ xon, c mó hoỏ thnh n bit u ra,
mi quan h gia k bit u vo v n bit u ra c xỏc nh bi mt trong cỏc phng
phỏp sau: (1) ma trn to mó; (2) chui to mó; (3) a thc to mó; (4) biu hỡnh cõy;
(5) biu hỡnh li; (6) biu trng thỏi. Cn phi lu ý rng, c tớnh quan trng ca
mó xon khỏc bit so vi mó khi l b lp mó ca chỳng cú nh vỡ th quỏ trỡnh to ra
n bit u ra khụng ch ph thuc vo k bit tin u vo ng thi m cũn ph thuc vo (K1) tp hp k bit u vo trc ú. Hay núi cỏch khỏc n bit u ra (c ly mu t cỏc u
ra ca n b cng Modul-2) khụng ch ph thuc vo k bit vo ng thi m cũn ph thuc
vo trng thỏi trc ú ca b lp mó (l mt trng thỏi thuc mt trong s 2 ( K 1) k trng thỏi
cú th cú ca b lp mó).
Nu k=1 (mi ln dch vo mt bit) b lp mó xon cú M tng nh tr thnh thanh
ghi dch M tng. Mi khi dch mt bit tin vo b lp mó thỡ tt c cỏc bit trc ú c
dch sang bờn phi mt tng, tu theo cu trỳc c th ca b lp mó (c xỏc nh bi a
thc to mó) m nhn c n bit tng ng.
Vỡ vy, ta cú th dựng cỏc phng phỏp k trờn (ma trn to mó, a thc to mó,
chui to mó, biu hỡnh cõy hoc hỡnh li v biu trng thỏi) trỡnh by hot ng
ca b lp mó, trong ú ta dựng cỏc ký hiu ch s sau:
l s th t ca chui bit vo cú di L
= 1,2,..., L :
q = 1,2,..., k :
l s th t u vo
l s th t u ra.
j = 1,2,..., n :
p = 0,1,2,..., M :
l s th t phn t nh (p = 0 tng ng vi u vo
ca b nh th nht)

-142-

k

Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s
l thi im xột.

i:

0,1,2,..., M, khi dầu vào bộ lập mã dợc nối dến nhánh cộng Modul2
p=
1,2,..., M, khi dầu vào bộ lập mã không dợc nối dến nhánh cộng Modul2

Cỏc bit n
n loi 1: Mc ớch l lm cho di chui bit vo l s nguyờn ln ca k. Vỡ
vy, nu di chui bit vo khụng phi l bi s ca k thỡ ta phi n cỏc bit "0"
di l bi s ca k khi ny di bn tin trờn mi u vo q u bng L chui bit bn
tin u vo l Lm = Lìk
n loi 2: Mc ớch l a b lp mó v trng thỏi khi u ton khụng (cỏc on
bn tin di Lm bit khụng nh hng lờn nhau), mun vy ta phi n (K-1)k bit "0" vo
cui chui bn tin trc (u bn tin tip theo) khi bn tin tip theo c np vo cỏc tng
nh ca b lp mó.
Ta lu ý rng: S lng cỏc bit "0" c n ph thuc vo cỏc tham s c trng
ca s lp mó v vic n c thc hin trc khi a chui bit tin vo b lp mó.
Hỡnh hỡnh 5.9a,b,c minh ha mt s s b lp mó xon im hỡnh.

a)
m

ci,1

D

(1)
i

ra

ci,2

Vo

c)

m (2)
i

D

ci,3
ci,1

M = 1, k = 2, n =3, K = 2

Vo

b)

ra

D D D
ci,2

1

Vo
(mi ln 2 bit)

D D

D D

Ra

2

M = 3, k = 1, n = 2, K = 3

3

M = 2, k = 2, n = 3, K = 2

Hỡnh 5.9. Minh ha m s b lp mó xon im hỡnh
5.4.3. Ma trn to mó
Xột hot ng b lp mó xon bng cỏch s dng ma trn to mó khi cho s lp
mó. trỡnh by hot ng b lp mó xon (ngha l tỡm chui bit u ra b lp mó khi cho
chui bit u v s b lp mó) dng ma trn ging nh i vi mó khi tuyn tớnh,
trc ht ta xỏc nh ma trn to mó G v ma trn kim tra H nh sau:

-143-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số

Bước 1: Ma trận tạo mã từ sơ đồ bộ lập mã
Biểu diễn phương trình vào/ra của sơ đồ lập mã.
Biểu diễn phương trình vào ra theo toán tử trễ x.
Xác định kích thước và giá trị cụ thể cho các phần tử của ma trận tạo mã G
Kích thước và các phương trình vào/ra theo các phần tử của G.
Từ các phương trình tổng quát
c i = m.G; s = y.H T vµ c i H T = 0

(5.43)

trong đó: m = (m i(1) ,..., m i( q ) ,..., m i( k ) )1×k là k bit vào; c i = (c i ,1 ,..., c i , j ,..., c i ,n )1×n là n bit đầu ra của
bộ lập mã tại thời điểm i. Kích thước và các phần tử của ma trận tạo mã G tương ứng với
các tham số đặc trưng của sơ đồ lập mã được xác định như sau
 g (p1,)1 ,
 ( 2)
g p ,1 ,
 :
G p =  (q )
g p,1 ,
 :
 (k )
g p,1 ,

g (p1,)2

,...., g (p1,)j

g (p2, 2)

,...,

:

:

g

(q)
p,2

g

(k)
p,2

:

,...,

g (p2, j)
:
g

(q)
p, j

g

(k)
p, j

:
,...,

:

,..., g (p1,)n 

,..., g (p2,n) 
:
: 
(q) 
,..., g p ,n 
:
: 

,..., g (pk,n) 

(5.44)

trong đó k, n, q, p là các giá trị cụ thể tương ứng với sơ đồ đã cho, khi này ta tìm được các
phương trình vào/ra bộ lập mã theo các phần tử của m và các phần tử của ma trận tạo mã G
nghĩa là

(

c i = m (i1) ,..., m i( q ) ,..., m (i k )

= (c i ,1 ,..., c i, j ,..., c i,n )1×n

)

1×k

 g (p1,)1 ,
 ( 2)
g p ,1 ,
 :
×  (q)
g p ,1 ,
 :
 (k)
g p ,1 ,

g (p1,)2
g (p2, 2)
:
(q)
g p,2
:
(k)
g p,2

,....,
,...,
:
,...,
:
,...,

g (p1,)j
g (p2, )j
:
(q )
g p, j
:
(k )
g p, j

,...,
,...,
:
,...,
:
,...,

g (p1,)n 

g (p2,n) 
: 
(q ) 
g p,n 
: 

g (pk,n) 

(5.45)
k ×n

c i ,1 = m (i1) .g (p1,)1 + m i( 2 ) .g (p2,1) + ... + m (i q ) .g (pq,1) + ... + m i( k ) .g (pk,1)

c i , 2 = m i(1) .g (p1,)2 + m i( 2) .g (p2, 2) + ... + m i(q ) .g (pq, 2) + ... + m i( k ) .g (pk, 2)
:
c i , j = m i(1) .g (p1,)j + m i( 2) .g (p2, j) + ... + m i( q ) .g (pq, j) + ... + m (i k ) .g (pk, j)

(5.46)

:
c i ,n = m i(1) .g (p1,)n + m i( 2 ) .g (p2,n) + ... + m (i q ) .g (pq,n) + ... + m i( k ) .g (pk,n)

Giá trị cụ thể cho các phần tử của ma trận tạo mã G
Bằng cách so sánh các phương trình vào ra của sơ đồ theo các phần tử g (pq, )j của ma
trận tạo mã G với các phương trình vào/ra theo toán tử trễ x, ta sẽ tìm được giá trị cụ thể
cho các phần tử của ma trận tạo mã đặc trưng cho sơ đồ lập mã đã cho.

-144-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
Bước 2: Ma trận kiểm tra chẵn lẻ H
Vì quan hệ giữa ma trận kiểm tra chẵn lẻ H và ma trận tạo mã G thông qua ma trận P
nghĩa là
G =  I k : Pk×( n − k ) 

 k×n

(5.47)

H =  P(Tn − k )×k : I n − k 

(5.48)

( n − k )×n

trong đó Ik là ma trận đơn vị kích cỡ kxk. Ta lưu ý rằng, ở đây ma trận Ik đứng trước P vì
các mi có chỉ số i thấp là các bit vào trước, nên ta tìm được P bằng cách biến đổi G về dạng
hệ thống, sau đó tìm H
Bước 3: Dạng hồi tiếp của sơ đồ lập mã
Bằng cách dùng phương trình c i H T = 0 , ta sẽ tìm được phương trình thiết kế sơ đồ hồi
tiếp của bộ lập mã.
Ví dụ minh họa được cho ở VD PL5.5 trong phụ lục 5B.
5.4.4. Chuỗi tạo mã và đa thức tạo mã
Xét hoạt động của bộ lập mã xoắn dựa vào chuỗi tạo mã (đa thức tạo mã). Cách thực
hiện của ta là: trước hết ta tìm các bit đầu ra của bộ lập mã cho trường hợp đơn giản (k=1)
nghĩa là mỗi lần chỉ đưa 1 bit tin vào bộ lập mã, sau đó tổng quát hoá cho trường hợp đưa k
bit đồng thời vào bộ lập mã. Vì vậy, trước hết xác định chuỗi tạo mã (đa thức tạo mã), sau
đó tìm chuỗi bit đầu ra (đa thức đầu ra) bộ lập mã dựa vào chuỗi tạo mã (đa thức tạo mã).
Chuỗi tạo mã
Để tìm đáp ứng ở đầu ra của bộ cộng Modul-2 thứ j đối với đầu vào q, ta dùng chuỗi
tạo mã sau:

(

g (jq ) = g (0q, j) , g 1(,qj) ,..., g (pq, j) ,..., g (Mq ,) j

)

(5.49)

trong đó: g (pq, j) là đáp ứng của đầu ra bộ nhớ thứ p lên đầu vào q của bộ cộng j, nó bằng 0
nếu đầu ra của bộ nhớ không nối đến bộ cộng và bằng 1 nếu đầu này được nối đến bộ cộng

(đầu vào bộ nhớ đầu tương ứng với p=0) nghĩa là
 0, nÕu ®Çu ra bé nhí p kh«ng nèi ®Õn bé céng Modul2 thø j
g (q)
p, j = 
1, nÕu ®Çu ra bé nhí p d−îc nèi ®Õn bé céng Modul2 thø j

Đa thức tạo mã
Ta có thể biểu diễn đáp ứng xung ở đầu ra của bộ cộng modul-2 thứ j ở dạng đa thức
tạo mã cho đầu vào q của bộ lập mã như sau:
M

(q)
(q)
(q) p
(q) M
p
g (q)
= ∑ g (q)
j (x) = g 0, j + g1, j x + ... + g p, j x + ... + g M, j x
p, j x

(5.50)

p =0

trong đó hệ số g (pq, )j = 0 / 1 giống như đối với chuỗi tạo mã.
Sử dụng chuỗi tạo mã để trình bày hoạt động bộ lập mã
Trường hợp mỗi lần đưa 1 bit tin vào bộ lập mã (k=1, r = 1/n):
Hoạt động của bộ lập mã xoắn với k=1, r = 1/n trên cơ sở chuỗi tạo mã được cho bởi
phương trình (5.51). Giả sử luồng bit tin đầu vào được chia thành các đoạn có độ dài L,

-145-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
được phân cách nhau bởi các đoạn đuôi (K-1) bit "0" để các đoạn này không ảnh hưởng lên
nhau, có thể biểu diễn chuỗi bit ở dạng sau:
⇐ H−íng truyÒn


m =  m 0 ,..., m ℓ ,..., m L −1 



(5.51)

trong đó m ℓ là các bit của khối bản tin L bit, ℓ = 0 là bit đầu tiên vào bộ lập mã.
Vì trong trường hợp này q=1 nên có thể viết lại phương trình (5.49) như sau:
g (jq )

(

= g j = g 0, j , g 1, j ,..., g p, j ,..., g M , j

q =1

)

(5.52)

Ký hiệu chuỗi bit ra của các nhánh cộng modul-2 thứ j là c j như sau:




⇐ H−íng truyÒn
c j =  c 0, j , c1, j ,...., c i, j ,..., c L + M −1, j 


bit ra thø i


cña nh¸nh thø j



(5.53)

trong đó: j =1, 2, ….n; c i, j là bit ra i của nhánh j; i = 0,1,...,L+M-1 với i=0 tương ứng với
đầu vào của bộ lập mã được nối đến nhánh cộng modul-2 và M là số bộ nhớ của bộ lập mã.
Vậy ta luôn nhận được số bit ở đầu ra nhánh cộng bằng (L+K-1) bit.
Các phần tử c i , j của chuỗi c j này được xác định theo tổng chập sau
M

c i, j = ∑ g p, j .m i − p ,

i = 0,1,2,..., L + M − 1

p =0

(5.54)

j = 1,2,..., n

trong đó m i − p =0 đối với p > i và (p = 0, i = 0) tương ứng với đầu vào của bộ lập mã được
nối đến nhánh cộng modul-2. Chuỗi đầu ra của bộ lập mã là ghép xen của các chuỗi cj.
Trường hợp tổng quát, mỗi lần đưa k bit tin đồng thời vào bộ lập mã ( r = k/n):
Nếu ký hiệu k bit đồng thời đưa vào bộ nhớ p ở thời điểm i ở dạng vector sau:

(

m i − p = m (i1−)p , m (i −2)p ,..., m (i −q p) ,..., m i(−kp)

)

(5.55)

trong đó m i(−q p) là bit thứ q vào bộ nhớ p tại thời điểm xét i.
Thì các đầu ra tương ứng ở thời điểm i được xác định như sau:
M

c i = ∑ m i−p G p

(5.56)

p=0

trong đó Gp là vector hay ma trận kết nối, nó biểu thị sự kết nối giữa các đầu ra của bộ nhớ
thứ p (p = 0 tương ứng với đầu vào bộ nhớ thứ nhất) với các bộ cộng modul-2 ở đầu ra của
bộ lập mã và nó được xác định như sau:

-146-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
 g (p1,)1 ,
 ( 2)
g p ,1 ,
 :
G p =  (q)
g p,1 ,
 :
 (k)
g p,1 ,

g (p1,)2

,...., g (p1,)j

g (p2, 2)

,...,

:

:

g

(q)

p,2

g

(k)
p,2

:

,...,

g (p2, )j
:
g

(q )
p, j

g

(k )
p, j

:
,...,

:

,..., g (p1,)n 


,..., g (p2, n) 
:
: 
(q) 
,..., g p, n 
:
: 

,..., g (pk, n) 

(5.57)

trong đó các phần tử g (pq, j) của ma trận tương ứng với đáp ứng đầu ra nhánh cộng j của bộ
nhớ p lên bit thứ q trong số k bit vào đồng thời.
Sử dụng đa thức tạo mã để trình bày hoạt động bộ lập mã
Để sử dụng phương trình (5.52) vào việc trình bày hoạt động bộ lập mã xoắn, ta cần
phải viết các đa thức bản tin, đa thức tạo mã, đa thức chuỗi bit ra của bộ lập mã cho hai
trường hợp dưới đây.
Trường hợp mỗi lần đưa 1 bit tin vào bộ lập mã (k=1, r = 1/n):
Đa thức bản tin: Giả sử chuỗi bit tin đầu vào được chia thành các đoạn dài L bit
với đuôi là K-1 bit "0" như đã xét ở trên, từ ptr.(5.51) có thể viết chuỗi bản tin này
vào dạng đa thức bản tin như sau:
L −1

m(x) = m 0 + m1x + ... + m ℓ x ℓ + ... + m L −1x L −1 = ∑ m ℓ x ℓ

(5.58)

ℓ =0

Đa thức tạo mã g (jq ) ( x ) q =1 = g j ( x ) : Đáp ứng của nhánh cộng j (đa thức tạo mã ở
nhánh thứ j ⇔ g (jq ) ( x ) q =1 = g j ( x ) ) lên chuỗi bit vào khi này được biểu diễn ở dạng
đa thức tạo mã sau:
M

g j (x) = g 0, j + g1, j x + ... + g p, j x p + ... + g M, j x M = ∑ g p, j x p

(5.59)

p =0

trong đó g p, j = 0 / 1 tương ứng với phần tử nhớ p không nối hoặc có nối vào bộ
cộng thứ j.
Đa thức chuỗi bit mã đầu ra thứ j:
c j ( x ) = m( x ).g j ( x )
= c 0, j + c 1, j x + ... + c i , j x i + ... + c L + M −1, j x L + M −1
=

(5.60)

L + M −1

∑c
i =0

i, j

xi

trong đó hệ số c i, j = 0 / 1 tương ứng với bit i ở đầu ra j.

Trường hợp tổng quát mỗi lần đưa đồng thời k bit tin vào bộ lập mã ( r = k/n):
Đa thức bản tin: Nếu mỗi lần đồng thời đưa k bit vào bộ lập mã, thì chuỗi bản tin
cho đầu vào thứ q (q=1,2,..,k) có độ dài L được biểu diễn ở dạng đa thức sau:
m (q ) ( x ) = m (0q ) + m 1( q ) x + . . . + m (ℓq ) x ℓ + . . . + m (Lq−)1 x L −1

(5.61)

L −1

= ∑ m ℓ( q ) x ℓ
ℓ =0

-147-


Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s
a thc to mó: c cho phng trỡnh (5.50)
a thc chui bit mó u ra th j ca b lp mó:
k

c j ( x ) = m ( q ) ( x ).g (jq ) ( x )

(5.62)

q =1

trong ú j = 1,2,..., n, g (jq ) ( x ) l a thc to mó cho chui vo u q, nhỏnh ra j.
Chui bit u ra ca b lp mó l ghộp xen ca n cỏc chui nhỏnh.
Vớ d minh ha c cho VD PL5.6 trong ph lc 5B.
5.4.5. Biu trng thỏi

Phn ny ta xõy dng biu trng thỏi v kho sỏt hot ng b lp mó bng cỏch
s dng biu trng thỏi.
Cu to: Biu trng thỏi gm cỏc nỳt trng thỏi c ni vi nhau bi cỏc nhỏnh
cựng vi cỏc t hp bit ra khi chuyn t nỳt trng thỏi ny sang nỳt trng thỏi khỏc. s
dng biu trng thỏi vo vic trỡnh by hot ng b lp mó mó xon, ngha l mi khi
a ng thi k bit tin vo b lp mó, ta xỏc nh c n bit ra tng ng thụng qua biu
trng thỏi m nú c trng cho s lp mó ú. Mun vy, biu trng thỏi phi: (1)
cha tt c cỏc trng thỏi cú th cú ca b lp mó; (2) th hin c s chuyn dch gia
cỏc trng thỏi mi khi a ng thi k bit tin vo b lp mó; (3) quan h cỏc bit vo/ra ca
b lp mó.
T cỏc tham s c trng ca s lp mó ta xỏc nh c:
Trng thỏi ca b lp mó xon: l t hp (K-1) bit vo ng thi trc ú (s bit
trng thỏi l (K-1)k) m vn nh hng lờn s hỡnh thnh cỏc bit ra ca b lp mó
thi im xột.
S nỳt trng thỏi cú th cú: T cỏc tham s c trng ca b lp mó nh: s bit
dch vo b lp mó ti cựng mt thi im; di hn ch th hin s ln dch cc
i ca mt nhúm k bit bn tin m nhúm k bit ny vn cũn nh hng ti u ra b
lp mó; s b nh (mi b nh cú k phn t nh) ca b lp mó M. Ta xỏc nh
c s trng thỏi cú th cú ca b lp mó l
2

(K 1)k

2(M 1)k , nếu đầu vào bộ lập mã không nối với bộ cộng Modul 2
= M.k
2 , nếu đầu vào bộ lập mã nối với bộ cộng Modul 2

Cỏc nhỏnh ni gia cỏc trng thỏi: Nhỏnh th hin: (1) chiu chuyn dch gia cỏc
trng thỏi trong biu trng thỏi; (2) iu kin chuyn dch trng thỏi thỏi (giỏ
tr c th ca cỏc bit trong k bit a vo ng thi b lp mó & cu trỳc c th cho

b lp mó a thc to mó); (3) cỏc giỏ tr c th ca cỏc bit trong n bit u ra.
Theo ú, mi nhỏnh c ỏnh nhón bi cỏc bit vo/ra nh sau
Mỗi khi đa đồng thời k bit vào bộ lập mã,
bộ lập mã mã hoá k bit vào này cho ra n bit ở đầu ra
Đồng thời bộ lập mã chuyển sang trạng thái mới (chiều mũi tên)

mi(1) ...mi( q ) ...mi( k )

ci ,1 ...ci ,j ...ci ,n

k bit vào đồng thời
n bit ra đợc lấy mẫu từ n nhánh cộng Modul-2



-148-


Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s
Vic ỏnh nhón ny cho thy n bit u ra c xỏc nh bi k bit vo ng thi v
trng thỏi trc ú ca b lp mó v s chuyn dch t trng thỏi c sang trng thỏi mi.
Hot ng: Do tớnh cht nh ca b lp mó xon, nờn quỏ trỡnh to ra n bit u ra
khụng ch ph thuc vo k bit tin u vo ng thi m cũn ph thuc vo (K-1) tp hp k
bit u vo trc ú. Hay núi cỏch khỏc n bit u ra (c ly mu t cỏc u ra ca n b
cng Modul-2 tng ng) khụng ch ph thuc vo k bit vo ng thi m cũn ph thuc
vo trng thỏi trc ú ca b lp mó (l trng thỏi thuc mt trong s 2 ( K 1) k trng thỏi cú
th cú ca b lp mó). Bit c trng thỏi hin ti cựng vi k bit vo ng thi tip theo,
d dng xỏc nh c n bit ra tip theo ca b lp mó. Hay núi cỏch khỏc n bit ra
( c i,1c i , 2 ...c i , j ...c i, n ) ti thi im xột c xỏc nh bi: k bit vo ng thi ti thi im xột
v trng thỏi trc ú ca b lp mó.

Biu trng thỏi cho b lp mó hỡnh 5.9a v 5.9b c v hỡnh 5.10. Cỏc nỳt
trng thỏi s hỡnh 5.10a c xỏc nh bi hai bit u vo ca Flip-Flop m i(1) m (i 2 ) cũn
hỡnh 5.10b c xỏc nh bng hai bit u ra ca Flip-flop th nht v th hai D0D1, vỡ
th chỳng u cú bn trng thỏi: s0 = (00), s1= (10), s2=(01) v s3=(11).
i vi s hỡnh 5.10a: Khi 2 bit mi c a vo ng thi ( m i(1) m (i 2 ) ) kt hp
vi hai bit vo ng thi trc ú to ra ba bit u ra v trng thỏi c chuyn i



m(1) m( 2 )
c c c
i

i ,1 i ,2 i ,3

i

2 bit vào đồng thời

3 bit đầu ra đợc lấy mẫu từ 3 nhánh cộng Modul-2

Mỗi khi đa đồng thời 2 bit vào bộ lập mã xoắn, bộ lập mã mã hoá 2 bit vào này,
cho ra 3 bit ở dầu ra. Đồng thời bộ lập mã chuyển sang trạng thái mới (chiều mũi tên)

Vic ỏnh nhón ny cho thy 3 bit u ra c xỏc nh bi 2 bit vo ng thi v
trng thỏi trc ú ca b lp mó v s chuyn dch t trng thỏi c sang trng thỏi mi
cac b lp mó.
i vi s hỡnh 5.10b: Khi mt bit mi c a vo, hai bit trng thỏi (D0D1) s
kt hp vi bit vo to ra hai bit ra (ci,1ci,2) v trng thỏi c chuyn dch. Chuyn dch
trng thỏi c th hin bng mt nhỏnh ni gia trng thỏi c v mi.

mi
ci ,1ci ,2
mỗi lần dịch 1 bit
vào bộ lập mã

2 bit ra bộ lập mã dợc lấy mẫu
từ 2 nhánh cộng Modul-2

Mỗi khi đa 1 bit vào bộ lập mã, bộ lập mã mã hoá
bit vào này cho ra 2 bit ở đầu ra. Đồng thời bộ lập mã
chuyển sang trạng thái mới (chiều mũi tên)

Thụng thng, khi k =1 thỡ nhỏnh cú bit vo l "1" c biu th bng ng khụng
liờn tc cũn nhỏnh cú bit vo l "0" c biu th bng ng liờn tc, vỡ th mi nhỏnh
ch cú cỏc nhón biu th hai bit ra.

-149-


Chng 5: Mó hoỏ kờnh kim soỏt li vụ tuyn s
ci,1

D

a)

m (i1)

b)
ra

ci,2

Vào

ci,1

Vào
mi

ra

D0 D1 D2

c
ci,2

m

( 2)
i

D

ci,3

Các thông số đặc trng: M = 1, k = 2, n =3, K = 2

Các thông số đặc trng: M = 3, k = 1, n =3, K = 3

Các bit trạng thái:

Các bit trạng thái:

(1)
i

m m

( 2)
i

D0 và D1

01/010

S0=
00

10
/0
00

11
/1
11

S2=
01

0/00

00/101

01
/00
1

1/00

00
/1
01

11/100

01/111

10
/1
00
01
/1
10

S0=
00

S2=
01

S1=
10

11/001

0/01

00
/0
11

10/110

S3=
11

1/10

0/10

S3=
11

11
/0
10

10/011

S1=
10

0/11

1/11

1/01
00/000

Trạng thái
hiện tại

mi(1) ...mi(q) ...mi(k )

ci,1...ci, j...ci,n

k bit vào đồng thời bộ lập mã

n bit ra bộ lập mã đợc lấy mẫu
từ n nhánh cộng Modul-2

Trạng thái
tiếp theo

Mỗi khi đa đồng thời k bit, bộ lập mã mã hoá thành n bit mã ở đầu ra

Hỡnh 5.10. Biu trng thỏi cho s lp mó s hỡnh 5.9a v hỡnh 5.9c
5.4.6. Biu hỡnh cõy
Phn ny ta xõy dng biu hỡnh cõy v trỡnh by hot ng b lp mó theo thi
gian bng cỏch dựng biu hỡnh cõy.
Cu to: Biu hỡnh cõy gm cỏc nỳt trng thỏi c ni vi nhau bi cỏc nhỏnh
cựng vi cỏc t hp bit ra khi chuyn t nỳt trng thỏi ny sang nỳt trng thỏi khỏc cú dng
hỡnh cõy. s dng biu hỡnh cõy vo vic trỡnh by hot ng b lp mó (ngha l
mi khi a ng thi k bit tin vo b lp mó xon cú th xỏc nh c n bit ra tng ng
thụng qua biu hỡnh cõy c trng cho s lp mó ú). Thỡ, biu hỡnh cõy phi: (1)
cha tt c cỏc trng thỏi cú th cú ca b lp mó; (2) th hin c s chuyn dch gia
cỏc trng thỏi mi khi ng thi a k bit tin vo b lp mó theo thi gian; (3) th hin
quan h cỏc bit vo/ra ca b lp mó.
i vi s b lp mó hỡnh 5.9a: T mi nut ta c bn nhỏnh tng ng vi cỏc
cp bit u vo: 00; 01; 10; 11.
i vi s b lp mó hỡnh 5.9b: T mi nut ta c hai nhỏnh: nu bit u vo
bng "0" ta c nhỏnh trờn, ngc li nu bit u vo bng "1" ta c nhỏnh di.
Mi nhỏnh cõy cng c ỏnh nhón bng cỏc bit u ra tng ng. Thớ d v dng
biu hỡnh cõy cho b lp mó hỡnh 5.9a v 5.9b c cho hỡnh 5.10a v b.
Khi xem xột k cỏc biu hỡnh cõy núi trờn cho ta thy rừ, sau nhỏnh th K (K:
di hn ch) cỏc nhỏnh lp li quy lut nh trc v na trờn ging nh na di.

-150-


Chương 5: Mã hoá kênh kiểm soát lỗi ở vô tuyến số
Hoạt động: Do các nhánh cây biểu thị các bit đầu ra của bộ lập mã tương ứng với
các bit đầu vào. Vì vậy, nếu cho chuỗi bit vào hoàn toàn xác định được chuỗi bit ra dựa
vào quan hệ giữa các bit vào/ra tương ứng trên các nhánh của cây khi đi từ gốc (t1) lên
ngọn (ti) của biểu đồ cây đặc trưng cho sơ đồ lập mã được xét.

Hình 5.11. Biểu đồ hình cây cho các bộ lập mã
Ta thấy rằng, mặc dù biểu đồ cây khắc phục nhược điểm của biểu đồ trạng thái (biểu
đồ trạng thái không cho phép theo dõi các chuyển đổi trạng thái của bộ lập mã theo thời
gian) bằng cách bổ sung kích thước thời gian cho biểu đồ trạng thái, (cho phép theo dõi
hoạt động bộ lập mã theo thời gian) nhưng khi chuỗi bit vào quá dài thì cây cũng quá
"lớn". Để biểu diễn hoạt động của bộ lập mã theo thời gian thuận tiện hơn ta dùng biểu đồ
lưới.
5.4.7. Biểu đồ lưới
Phần này ta xây dựng biểu đồ lưới và xét hoạt động bộ lập mã dựa vào biểu đồ lưới
đặc trưng cho sơ đồ bộ lập mã theo thời gian.

-151-