


 
!"
#
Giảng viên hướng dẫn : TS.BÙI VIỆT KHÔI
Học viên cao học : LÊ HOÀI VIỆT
LƯƠNG HỒNG QUÝ
ĐINH VĂN HƯỜNG
ĐỖ HỮU TRỌNG
NGUYỄN HỮU MẠNH
Lớp : BK01-KTTT1B

Hà Nội, tháng 5/2012
$$
#
%&'()*)+,,-.'/0
Mã chập là một kỹ thuật mã hóa sửa sai. Mã chập thuộc họ mã lưới (mã hóa theo
Trellis) và được xây dựng dựa trên một đa thức sinh hoặc một sơ đồ chuyển trạng thái
(trellis mã) đặc trưng. Quá trình giải mã của mã chập phải dựa vào trellis mã thông qua
các giải thuật khác nhau, trong đó nổi tiếng nhất là giải thuật Viterbi.
Tại sao gọi là mã chập vì cấu trúc mã hóa có thể biểu diễn dưới dạng phép tính
chập giữa đa thức sinh mã và chuỗi tín hiệu được mã hóa.
Mã hóa chập và thuật toán giải mã Viterbi được sử dụng trong khoảng hơn một tỉ
điện thoại, có thể là lớn nhất trong các loại thuật toán được ứng dụng. Tuy nhiên, hiện tại
thì thuật toán xử lý viterbi được ứng dụng nhiều nhất trong các thiết bị âm thanh và hình
ảnh kỹ thuật số. Ngày nay, chúng còn được sử dụng trong các thiết bị bluetooth.
Mục đích của mã hóa kênh truyền là nhằm tăng dung lượng kênh truyền, bằng
cách cộng thêm vào tín hiệu những dữ liệu dư thừa được thiết kế một cách cẩn thận
trước khi truyền lên kênh truyền. Mã hóa chập và mã hóa khối là 2 dạng chính của mã

tử mi thuộc trường F) được xem như một chuỗi Laurent:
m
(
X
)
=
∑
e=−∞
e=+∞
m
e
x
e
Tập tất cả các chuỗi Laurent trên F là một trường, ta ký hiệu trường này là F[[X]]
như vậy
m( X )ϵ F [
[
X
]
]
Đối với dòng nhiều bit vào ta dùng ký hiệu m
(1)
(x) biểu thị dòng đầu vào đầu tiên,
m
(2)
(x) biểu thị dòng đầu vào thứ hai. Tập các dòng vào xem như một vectơ:
m(x)=[ m
(1)
(x) m
(2)

Ở đây dấu phẩy phân cách các cặp bít ra ứng với mỗi bít vào.Ta có thể biểu thị
hàm truyền từ đầu vào m(x) từ đầu ra C(1)(x) như sau:
g
1
(x) = 1 + x +x
2
.
Tương tự ta có g
2
(x)= 1 + x
2
.
Dòng vào m = {1, 1, 0, 0, 1, 0, 1} có thể biểu thị như sau:
m (x) = 1+ x+ x4+ x6 GF(2)[[X]].
Các đầu ra sẽ là
4
C
(1)
(x) = m(x)g
1
(x) = (1+ x +x
4
+ x
6
)(1+ x + x
2
) = 1 +x
3
+x
4

∈( X )
(còn gọi là
ma trận truyền). Với mã tốc độ
R=
1
2
ở ví dụ trên ta có:
G
a
(x)=[1+x+x
2
1+x
2
]
Ma trận truyền này không chỉ có dạng các đa thức, ta có thể thấy thông qua ví dụ
sau:
58;"Xét ma trận truyền của mã chập sau:
G
b
(
x
)
=
[
1
1+x+x
2
1+x
2
]

Dãy ra được biểu thị như sau:
C(X) = [C
(1)
(x), C
(2)
(x),…,C
(n)
(x)] = m(x)G(x)
Ma trận truyền G(x) được gọi là hệ thống nếu có thể xác định được một ma trận
đơn vị trong các phần tử của G(x) (chẳng hạn nếu bằng các phép hoán vị hàng và/hoặc
cột của G(x) có thể thu được một ma trận đơn vị).
Từ các ví dụ trên ta có định nghĩa sau cho mã chập
<*'*:'=7: Mã chập tốc độ R = k/n trên trường các chuỗi Laurent hữu tỷ F[[X]]
trường F là ảnh của một ánh xạ tuyến tính đơn ánh của các chuỗi Laurent k chiều m(x)
ϵ F [
[
X
]
]
k
vào các chuỗi Laurent C(x)
ϵ F [
[
X
]
]
n
>&?@4AB.,-.'/0
Mã chập được tạo ra bằng cách cho chuỗi thông tin truyền qua hệ thống các thanh
ghi dịch tuyến tính có số trạng thái hữu hạn. Cho số lượng thanh ghi dịch là m (cũng ký

Giả sử u là véctơ đầu vào, x là véctơ tương ứng được mã hoá, bây giờ chúng ta
mô tả cách tạo ra x từ u. Để mô tả bộ mã hoá chúng ta phải biết sự kết nối giữa thanh ghi
đầu vào vào đầu ra hình 2.5. Cách tiếp cận này có thể giúp chúng ta chỉ ra sự tương tự và
khác nhau cũng như là với mã khối. Điều này có thể dẫn tới những ký hiệu phức tạp và
nhằm nhấn mạnh cấu trúc đại số của mã chập. Điều đó làm giảm đi tính quan tâm cho
mục đích giải mã của chúng ta. Do vậy, chúng ta chỉ phác hoạ tiếp cận này một cách sơ
lược. Sau đó, mô tả mã hoá sẽ được đưa ra với những quan điểm khác.
Để mô tả bộ mã hoá hình 2.5 chúng ta sử dụng N ma trận bổ sung G1,G2…,GN
bao gồm k hàng và n cột. Ma trận Gi mô tả sự kết nối giữa đoạn thứ i của k ô nhớ trong
thanh ghi ngõ vào với n ô của thanh ghi ngõ ra. N ngõ vào của hàng đầu tiên của Gi mô
tả kết nối của ô đầu tiên của đoạn thanh ghi đầu vào thứ i với n ô của thanh ghi ngõ ra.
7
Kết quả là “1” trong Gi nghĩa là có kết nối, là “0” nghĩa là không kết nối. Do đó chúng ta
có thể định nghĩa ma trận sinh của mã chập:
Và tất cả các các ngõ vào khác trong ma trận bằng 0. Do đó nếu ngõ vào là véctơ
u, tương ứng véctơ mã hoá là:
x=u.G
∞
Bộ mã chập là hệ thống nếu trong mỗi đoạn của n chữ số đuợc tạo, k số đầu là
mẫu của các chữ số đầu vào tương ứng. Nó có thể xác định rằng điều kiện này tương
đương có các ma trận k×n theo sau:
Chúng ta xét một vài ví dụ minh hoạ sau đây:
58;" Xét mã (3,2,2). Bộ mã hoá được chỉ trong hình 2.6. Bây giờ mã được định nghĩa
thông qua 2 ma trận:
Bộ mã hoá là hệ thống, ma trận sinh được tạo ra:
8
Chuỗi thông tin u = ( 11011011…) được mã hóa thành chuỗi mã x = (111010100110…)
Hình 4.Bộ mã chập (3,2,2)
Một cách tương tự ta cũng có thể biểu diễn ma trận sinh G = (G1,G2,…,GN).
Như vậy ý nghĩa của ma trận sinh là nó chỉ ra phải sử dụng các hàm tương ứng nào để

dịch vào bộ mã là bit 0 hay bit 1. Với tính chất đó ta có thể biểu diễn mã chập bằng sơ
đồ có dạng hình lưới gọn hơn, trong đó các đường liền nét được ký hiệu cho bit đầu vào
là bit “1” và đường đứt nét được ký hiệu cho các bit đầu vào là bit “0” (xem hình 6). Ta
thấy rằng từ sau tầng thứ hai hoạt động của lưới ổn định, tại mỗi nút có hai đường vào
nút và hai đường ra khỏi nút. Trong hai đường đi ra thì một ứng với bit đầu vào là bit
“0” và đường còn lại ứng với bit đầu vào là bit “1”.
11
Hình 6. Sơ đồ hình lưới bộ mã chập (2,1,3) và bộ phát mã (7,5).
Trạng thái ban đầu toàn bằng “0”
FGHI4AO*:4'()"
Sơ đồ trạng thái được thực hiện bằng cách đơn giản sơ đồ 4 trạng thái có thể có
của bộ mã (00, 01, 10 và 11) và trạng thái chuyển tiếp có thể được tạo ra từ trạng thái
này chuyển sang trạng thái khác, quá trình chuyển tiếp có thể là:
Kết quả ta thu được sơ đồ trạng thái trong hình 7 như sau:
12
Hình 7. Sơ đồ trạng thái của bộ mã chập (2,1,3)
Từ sơ đồ trạng thái hình 2.10, các đường liền nét được ký hiệu cho bit đầu vào là
bit “0” và đường đứt nét được ký hiệu cho các bit đầu vào là bit “1”. So với sơ đồ hình
lưới và sơ đồ hình cây thì sơ đồ trạng thái là sơ đồ đơn giản nhất.
P&@*'MQ.H)D,.R7,-.'/0
P&%@H)D,
Cũng như các mã sửa sai khác, mã chập cho phép chúng ta có thể sửa lại dữ liệu
đã bị sai lệch khi truyền qua kênh truyền để khôi phục chính xác tín hiệu gốc.
Việc thực hiện mã hóa dùng mã chập tương đối đơn giản hơn các loại mã sửa sai
khác mà chất lượng mã hóa lại tốt.
Việc thực hiện mã hóa dùng mã chập có thể được thực hiện bằng phần cứng và
phần mềm.
Dựa trên hình thức mã hóa mã chập cùng thuật giải Viterbi cho nó, các bộ mã hóa
sau này đều kế thừa những đặc tính ưu việt của nó.
P&1&'MQ.H)D,

dây nâng cao có thể tạo ra một bộ giải mã Viterbi với K = 9 hoạt động ở tốc độ lên đến 2
Mbps. NTT tuyên bố rằng họ đã tạo được bộ giãi mã Viterbi hoạt động ở tốc độ 60
Mbps, nhưng tính khả thi của nó vẫn chưa được kiểm chứng.
Y&2'3*45.'4'@/4:)Z))4WAX)
Chúng ta sẽ lấy ví dụ về mã chập có tốc độ mã là
k
n
=
1
2
Hình 8. Bộ mã chập tốc độ ½.
14
FF: thanh ghi dịch. Tại mỗi xung clock, nội dung của thanh ghi dịch được dịch qua phải
1 bit. Bit đầu tiên sẽ là ngõ vào, và bit cuối cùng sẽ là ngõ ra. Một thanh ghi dịch có thể
sẽ xem xét việc cộng trễ vào ngõ vào. Các thanh ghi dịch có thể được hiểu như là bộ nhớ
của bộ mã hóa. Nó ghi nhớ những bit đầu của chuỗi.
Thanh ghi dịch được khởi đầu với tất cả giá trị là 0.
Thuật toán XOR:
Nếu chúng ta làm việc trên một chuỗi ngõ vào là 01011101, ngõ ra là 00 1110 00
01 10 01 002. Bộ mã hóa này cũng có thể được mô hình bởi một bảng trạng thái hữu
hạn. Mỗi một trạng thái được quy định bởi 2 bit nhị phân- trạng thái của 2 thanh ghi
dịch. Mỗi một sự chuyển trạng thái được quy định bởi w/v1v2 với w đại diện cho bit ngõ
vào, và v1v2 là đại diện cho 2 bit ngõ ra, trong trường hợp này chúng ta luôn luôn có w
= v1.
Bảng 1 Trạng thái ngõ vào và ngõ ra của bộ mã hóa tốc độ ½
Hình 9. Đồ hình trạng thái của mã chập ½
15
Bậy giờ chúng ta có thể mô tả thuật toán giải mã, phần chính là thuật toán Viterbi.
Có lẽ, khái niệm quan trọng nhất để hỗ trợ cho việc hiểu được thuật toán Viterbi đó là sơ
đồ Trellis. Hình bên dưới cho chúng ta thấy sơ đồ trellis cho ví dụ của chúng ta ở tốc độ

của ký hiệu nhận được và cặp bit có thể của kênh truyền. Khoảng cách Hamming được
tính một cách đơn giản bằng cách đếm có bao nhiêu bit khác giữa cặp bit nhận được từ
kênh truyền và cặp bit so sánh. Kết quả chỉ có thể là 0, 1, 2. Giá trị của khoảng cách
Hamming (hay thông số metric) mà chúng ta tính toán ở mỗi khoảng thời gian cho
đường dẫn của trạng thái tại thời điểm trước và trạng thái hiện tại được gọi là metric
nhánh (branch metric). Ở thời điểm đầu tiên, chúng ta sẽ lưu những kết quả này như là
“thông số metric tích lũy”, được liên kết đến các trạng thái. Ở thời điểm thứ 2, thông số
metric tích lũy sẽ được tính toán bằng cách cộng thêm thông số metric tích lũy trước đó
vào metric nhánh hiện tại.
Ở thời điểm t=1, ta nhận được 2 bit “00”. Chỉ có một cặp ký hiệu kênh truyền mà
chúng ta có khả năng nhận được là “00” và “11”. Khoảng cách Hamming giữa “00” và
“00” là bằng 0. Khoảng cách Hamming giữa “00” và “11” là 2. Do đó, giá trị thông số
metric nhánh cho nhánh ứng với sự chuyển trạng thái từ “00” đến “00” là 0 và cho
nhánh từ “00” đến “10” là 2. Khi mà thông số metric tích lũy trước đó là 0 thì thông số
metric tổng sẽ chính bằng thông số metric của nhánh vừa xét. Tương tự ta tính được
thông số metric cho 2 trạng thái kia. Hình bên dưới minh họa kết quả tại thời điểm t= 1
Hình 13. Tại thời điểm t=1.
Điều gì sẽ xảy ra ở thời điểm t=2, chúng ta nhận được một cặp kí hiệu kênh
truyền là “11”, trong khi đó cặp ký hiệu kênh truyền mà chúng ta có thể nhận được là
“00” nếu chuyển từ trạng thái “00” sang trạng thái “00” và “11” khi chuyển từ trạng thái
“00” đến trạng thái “10”, “10” khi chuyển từ trạng thái “10” đến trạng thái “01”, “01”
khi chuyển từ trạng thái “10” đến trạng thái “11”. Khoảng cách Hamming giữa 00 và 11
18
là 2, giữa 11 và 11 là 0, giữa 01 hoặc 10 với 11 là 1. Chúng ta cộng các thông số metric
ở mỗi nhánh lại với nhau. ở thời điểm t=1 thì trạng thái chỉ có thể là 00 hoặc 10, thông
số metric tích lũy sẽ được cộng vào là 0 hoặc là 2 một cách tương ứng. Hình bên dưới
thể hiện sự tính toán thông số metric tích lũy ở thời điểm t=2.
Hình 14. Tại thời điểm t=2.
Đó là tất cả sự tính toán cho thời điểm t=2. Đường nét đậm là metric nhánh được
lựa chọn vì theo các nhánh đó, thông số metric là nhỏ nhất. Giờ chúng ta sẽ tính thông số

Việc xử lý giải mã bắt đầu với xây dựng một thông số metric tích lũy cho một số
cặp ký hiệu kênh truyền nhận được, và lưu giữ trạng thái ở mỗi thời điểm t mà thông số
metric là nhỏ nhất. Một khi thông tin này được dựng lên thì bộ giải mã viterbi sẵn sàng
để khôi phục lại chuỗi bit đã đưa vào bộ mã hóa chập, khi mẫu tin được mã hóa để
truyền đi. Điều này đạt được bằng những bước sau:
o Đầu tiên, chọn một trạng thái có thông số metric nhỏ nhất và lưu lại số trạng
thái của trạng thái đó.
o Sử dụng lặp lại cho những bước kế tiếp mãi cho đến khi bắt đầu của trellis đạt
được: dựa vào bảng ghi nhớ trạng thái cho trạng thái được chọn, chọn một trạng thái mới
được liệt kê trong bảng ghi nhớ trạng thái khi chuyển từ trạng thái trước đến trạng thái
đó. Lưu số trạng thái của mỗi trạng thái được chọn. Bước này được gọi là truy hồi
(traceback).
o Chúng ta làm việc tiếp với danh sách những trạng thái được chọn đã được lưu
trong bước xử lý trước đó. Chúng ta tra xem bit ngõ vào nào phù hợp với sự truyền dẫn
từ mỗi trạng thái trước đến trạng thái kế tiếp. Đây là bit mà phải được mã hóa bằng mã
tích chập.
Bảng sau cho chúng ta thấy ma trận tích lũy của đầy đủ 8 bit (cộng với 2 bit phụ
thêm) của bản tin ở mỗi thời điểm t:
Bảng 2: Bảng ma trận tích lũy của cả 8 bit của bản tin
Chú ý rằng ở ví dụ về bộ giải mã Viterbi ngõ vào quyết định cứng này, thông số
metric tích lũy nhỏ nhất ở trạng thái cuối chỉ ra được có bao nhiêu lỗi ký hiệu kênh
truyền xảy ra.
Bảng lịch sử trạng thái bên dưới cho thấy trạng thái tồn tại trước đó cho mỗi trạng
thái tại thời điểm t:
22
Bảng 3: Bảng lịch sử trạng thái
Tương ứng 0,1,2,3 là các vị trí 00,01,10,112.
Bảng sau cho thấy trạng thái được lựa chọn khi truy hồi đường dẫn từ bảng trạng thái
tồn tại ở trên:
Bảng 4: Bảng các trạng thái được lựa chọn khi truy hồi

sau.
• Để thực thi một bộ giải mã Viterbi bằng phần mềm, bước đầu tiên là phải
xây dựng một vài cấu trúc dữ liệu xoay quanh thuật giải mã sẽ được thực
thi. Những cấu trúc dữ liệu này được thực thi tốt nhất khi là các mảng. Sáu
mảng chính mà chúng ta cần cho bộ giải mã viterbi là:
• Một bản sao của “Bảng trại thái kế tiếp” của bộ mã hóa mã chập, bảng
chuyển trạng thái của bộ mã hóa. Kích cỡ của bảng này (hàng x cột) là 2
(K-
1)
x 2
K
. Mảng này phải được khởi đầu trước khi bắt đầu tiến trình giải mã.
• Một bản sao của “bảng ngõ ra” của bộ mã hóa mã chập. Kích cỡ của bảng
này là 2
(K-1)
x 2
K
. Mảng này cũng cần phải được khởi đầu trước khi bắt đầu
tiến trình giải mã.
• Một mảng để lưu trữ trạng thái hiện tại và trạng thái kế của bộ mã hóa mã
chập, với giá trị ngõ vào (0 hoặc 1) sẽ cho ra trạng thái kế tiếp và trạng
thái hiện tại. Chúng ta sẽ gọi bảng này là “bảng ngõ vào”. Kích thước của
bảng là 2
(K-1)
x 2
(K-1)
. Mảng này cũng cần phải được khởi đầu trước khi bắt
đầu tiến trình giải mã.
• Một mảng để lưu trữ lịch sử các trạng thái trước cho mỗi trạng thái của bộ
mã hóa cho Kx5 + 1 cặp kí hiệu kênh truyền nhận được. Chúng ta sẽ gọi