NHIỆM VỤ ĐỒ ÁN
Nghiên cứu về giải mã chập dùng thuật toán Viterbi
Nội dung nghiên cứu gồm 4 chương:
Chương 1: Hệ thông tin và ảnh hưởng của môi trường đến hệ thông tin số.
Chương 2: Tìm hiểu về mã chập.
Chương 3: Giải mã chập dùng thuật toán Viterbi.
Chương 4: Mô phỏng.

1


LỜI CAM ĐOAN
Tôi xin cam đoan đồ án này do cá nhân em nghiên cứu và xây dựng nên,
được thực hiện dưới sự hướng dẫn của Thạc sỹ Trịnh Thị Diệp.
Các số liệu, những kết luận nghiên cứu được trình bày trong đồ án này trung
thực và chưa từng được công bố dưới bất cứ hình thức nào.
Em xin chịu trách nhiệm về nghiên cứu của mình.

Sinh viên thực hiện Dương Thị Thuyến

2


MỤC LỤC

DANH MỤC HÌNH VẼ

3


Hình 3.14. Tại thời điểm t = 9..

Inter Symbol Interference

Nhiễu liên ký hiệu

PAM

Pulse Amplitude Modulation

Điều chế biên độ xung

DS - CDMA

Direct Spread - Code Division
Multiple Access

OFDM

Phương pháp trải phổ chuỗi
trực tiếp đa truy nhập theo mã

Orthogonal Frequency Division

Ghép kênh phân chia theo tần

Multiplexing

số trực giao

GI



AWGN

Additive White Gaussian Noise

Nhiễu Gauss trắng

BER

Bits Error Rate

Tỷ lệ lỗi bit

MỞ ĐÀU
Cùng với sự phát triển của khoa học và công nghệ phục vụ cho cuộc sống
của con người, công nghệ viễn thông trong những năm qua đã có những bước phát
triển mạnh mẽ cung cấp ngày càng nhiều tiện ích cho con người.
5


Thế kỷ 21 chứng kiến sự bùng nổ thông tin, trong đó thông tin di động đóng
một vai trò rất quan trọng. Nhu cầu trao đổi thông tin ngày càng tăng cả về số
lượng, chất lượng và các loại hình dịch vụ kèm theo, điều này đòi hỏi phải tìm ra
phương thức trao đổi thông tin mới ngày càng ưu việt và mang lại hiệu quả cao hơn.
Các công nghệ di động và viễn thông ngày một phát triển nhanh chóng để hướng tới
mục đích tăng tốc độ cũng như chất lượng của các dịch vụ nhằm đáp ứng nhu cầu
ngày càng cao của con người về các thiết bị không dây bỏ túi.
Một trong những khâu quan trọng nhất của việc thông tin không dây đó là
việc truyền và nhận tín hiệu. Điều này cần thiết phải có một loại mã hóa dành riêng
cho kênh truyền có khả năng sửa chữa sai sót của tín hiệu truyền đi do các tác động

ẩ hư ta đã biết, thông thường ở nguồn thông tin, dữ liệu sẽ được mã hóa
trước khi nó được đưa vào kênh truyền, mục đích của việc làm này là giảm thiểu lỗi
và nâng cao hiệu suất đường truyền cũng như làm giảm ảnh hưởng của một số tác
nhân không mong muốn như hiệu ứng đa đường, noỉse, nhiễu và nhiễu liên kí hiệu
(ISI).
Chúng ta có thể miêu tả tóm tắt của một quá trình truyền tin trong hệ thông
tin cơ bản như sau:
ẩ guồn thông tin là dữ liệu mà ta muốn gửi đến người đùng khác trong hệ
thông tin. Trước tiên, nguồn thông tin được cho đi qua một bộ mã hóa nguồn, sau
đó, dữ liệu này được đưa đến bộ mã kênh (sử dụng các bộ mã như Hamming,
Vỉterbỉ...) để mã hóa thành các từ mã cho mục đích giải mã, kiếm soát và sửa lỗi ở
bên thu. Kênh truyền là một trong những nguyên nhân chính gây ra lỗi cho tín hiệu
thu bởi vì nó chịu ảnh hưởng của các tác nhân không mong muốn như ồn, nhiễu liên
kí hiệu...do vậy, bộ mã kênh có thể đưa thêm các bỉt kiểm ưa vào chuỗi thông túi
nhằm giảm thiểu, phát hiện các lỗi ưong quá trình dữ liệu đi qua kênh truyền. Tiếp
đó, dữ liệu được điều chế trước khi truyền để hạn chế lỗi và nâng cao dung lượng
kênh truyền.
Để tín hiệu đầu ra bộ mã kênh phù hợp với kênh truyền, bộ điều chế được
thực hiện sắp xếp các chuỗi số đầu ra bộ mã kênh thành chuỗi dạng sóng phù hợp
với đặc tính kênh truyền. Để tăng tốc độ truyền, mỗi kí hiệu có thể mang nhiều bit
thông tin như hệ thống điều chế nhiều mức (QPSK, PSK, QAM...).
Sau khi điều chế, nó đuợc đưa lên kênh truyền. Kênh là phương tiện được sử dụng
để truyền tải tin như là kênh hữu tuyến, kênh vô tuyến, kênh sợi quang... Tuy nhiên,
kênh truyền lại là nơi chịu ảnh hưởng nhiều nhất của tạp nhiễu, hơn nữa, nếu chúng
ta xét trong truyền thông vô tuyến thì nó còn chịu tác động thêm của nhiều tác nhân
không mong muốn. Bên phía thu, một quá trinh ngược lại được tiến hành, bắt đầu từ
việc nhận tín hiệu, giải điều chế, sau đó đến giải mã kênh và giải mã nguồn để đưa
ra nguồn thông tin cuối cùng sao cho xác suất có lỗi trong nó là chấp nhận được.
7


này có chiều dài so sánh được với chiều dài bước sóng.
- Nhiễu xạ: khi sóng va chạm với các vật có kích thước lán hơn nhiều chiều
dài bước sống.

9


1.2.5. Nhiễu liên kí hiệu (ISI)
Trong môi trường truyền dẫn đa đường, nhiễu liên ký hiệu (ISI) gây bởi tín
hiệu phản xạ có thời gian trễ khác nhau từ các hướng khác nhau từ phát đến thu là
điều không thể tránh khỏi. Ảnh hưởng này sẽ làm biến dạng hoàn toàn mẫu tín hiệu
khiến bên thu không thể khôi phục lại được tín hiệu gốc ban đầu.
ÀMPtlTEE

1

Hình 1.4. Minh họa khoảng thời gian của 1 kí hiệu và trải trễ tương ứng của kí
hiệu đó ở bên thu.
Trong chu kỳ đầu tiên của quá trình truyền dẫn, các tín hiệu nhận được có xu
AtofHit£E

hướng làm cho dài ra và bị lẫn vào nhau. Hình 1.5 chỉ ra dòng dữ liệu
1,1,

1,1,0, chuỗi dữ liệu mong muốn phát đi. Chuỗi dữ liệu này có dạng xung

vuông. Các xung vuông được mô tả trìu tượng và mang tính chất lý thuyết nhưng
trong thục tế chứng rất khó được tạo ra. Do đó chúng ta chỉ tạo ra được các xung
vuông có hình dáng giống như được chỉ ra ừong đường ngắt quãng như hình dưới
TIME

cảm hon đến nhiễu và sự thể hiện sai và hiện tượng này là kết quả của ứễ những kí
hiệu và trùng lên nhau.

AA*=1IU0E

Hình 1.7. Tín hiệu nhận được và tín hiệu thực tế được phát đi.
1.3. Một số phvơng pháp khắc phục
Trong các hệ thống đơn sóng mang, ISI là một vấn đề khá nan giải. Lí do là độ
rộng băng tần tỉ lệ nghịch với khoảng thời gian kí hiệu, do vậy, nếu muốn tăng
tốc độ truyền dữ liệu ừong các hệ thống này, tức là giảm khoảng kí hiệu, vô
hình chung đã làm tăng mức trải trễ tương đối. Lúc này hệ thống rất nhạy với
trải trễ. Và việc thêm khoảng bảo vệ khó triệt tiêu hết ISI. Để giảm nhiễu xuyên
âm người ta phải làm thế nào hạn chế dải thông mà vẫn không gây ra ISI. Khi
dải thông bị giới hạn, xung sẽ có đỉnh tròn thay vì đỉnh phẳng. Một trong
những phương pháp để loại bỏ nhiễu ISI là dùng cách tạo dạng xung thích
hợp như bộ lọc cos nâng.

1
1


1.3.1. Bộ lọc cos nâng

Hình 1.8. Sơ đồ khối của hộ lọc cos nâng.
Tín hiệu từ nguồn gồm có M phần tử, song chúng ta chỉ hạn chế khảo sát
trường hợp khi các phần tử Sị(t) của tập tín hiệu chỉ khác nhau về biên độ, tức là ta
sẽ hạn chế chỉ xét hệ thống điều chế biên độ xung PAM.
Thực tế hệ thống này có thể xem như gán cho mỗi một tin mk một hằng số
ak mà biên độ của xung đầu ra của bộ tạo xung sẽ được nhân với nó.
Ta hãy giả sử rằng bộ tạo xung cho ra các xung Dừăc tại các thời điểm t =

Có giá trị cực đại bằng 1 tại t = 0 và có giá trị bằng 0 tạo t = kîi/cûo- Giả sử
rằng đầu vào bộ lọc lý tưởng này có tín hiệu được tạo bởi bộ tạo xung như trên hình
1.8, tức là tín hiệu lối vào bộ lọc T(oa)được cho bởi:
s(t) = ^ akS(t - kT)
k=-00

Trong trường hợp này, phản ứng xung đầu ra sẽ không gây nên ISI nếu tần
số cắt của bộ lọc là f0 = Cữ(j2ĩi = 1/2T.
Do đom giản trong tính toán, hàm số cong dạng cosine thường ưa được sử
dụng để phân tích các bộ lọc này. Hàm truyền tổng cộng khi đó có dạng:
Và phản ứng xung có dạng:
sinnt/T cosant/T
=
nt/T 1-4 a 2 t 2 /T 2
Hàm truyền liên tục thì có biên độ gọn sóng suy giảm theo luỹ thừa 3 của
biến t. Do vậy ngay cả khi đồng bộ không lý tưởng thì giá trị của phản ứng xung
đầu ra của các bộ lọc này sẽ bị chặn. Do đó, ISI sẽ nhỏ ngay cả khi đồng bộ không
lý tưởng.
1.3.2.

Bộ lọc ngang ép không
K’AUOU SỐ

At .'(Im)

LIỆU

BẬ LỌC

-►

tưởng zero- ISI đom giản là một bộ lọc nghịch đảo đáp ứng tần số của bên phát và
kênh truyền. Bộ lọc đảo này thường được xấp xỉ bởi một bộ lọc FIR như hình vẽ
dưới.

13


Hình 1.10. Bộ lọc cân bằng kênh.
Đáp ứng xung của bộ lọc cân bằng kênh là:
N

hE(t) = ^ Cnỗ(t - nT)
n=-N

Đáp ứng tần số tương ứng là:
N

H E (f) = 2 Cne~i2ĩmTf
n=-N

Vấn đề của bộ lọc đảo chính là lựã chọn các hệ số của bộ lọc sao cho xấp xỉ
được điều kiện zero- ISI.
Trong môi trường truyền dẫn đa đường, nhiễu xuyên ký tự (ISI) gây bởi tín
hiệu phản xạ có thời gian trễ khác nhau từ các hướng khác nhau từ phát đến thu là
điều không thể tránh khỏi. Ảnh hưởng này sẽ làm biến dạng hoàn toàn mẫu tín hiệu
khiến bên thu không thể khôi phục lại được tín hiệu gốc ban đầu. Các kỹ thuật sử
dụng trải phổ trực tiếp DS-CDMA như trong chuẩn 802.11b rất dễ bị ảnh hưởng bởi
nhiễu đa đường vì thời gian trễ có thể vượt quá khoảng thời gian của một ký tự.
OFDM sử dụng kỹ thuật truyền song song nhiều băng tần con nên kéo dài thời gian
truyền một kỷ tự lên nhiều lần. Ngoài ra, OFDM còn chèn thêm một khoảng bảo vệ

hợp cho các hệ thống truyền dẫn hữu tuyến và một số hệ thống vô tuyến không yêu
cầu vể thời gian trễ. Thay vào đó, với các hệ thống thông tin không dây ngày nay,
người ta hay sử dụng một loại mã có thể phát hiện và khắc phục lỗi một cách tự
động. Việc này giảm thiểu thời gian trể so với các hệ thống yêu cầu truyền lại. Bộ
mã này thường được gọi là mã điều khiển lỗi (ECC), hay chính xác hơn là FEC.
Mục đích của lý thuyết Mã hóa trên kênh truyền là tìm những mã có thể
truyền thông nhanh chóng, chứa đựng nhiều từ mã tự họp lệ và có thể sửa lỗi hoặc ít
nhất phát hiện các lỗi xảy ra. Các mục đích trên không phụ thuộc vào nhau, và mỗi
loại mã có công dụng tối ưu cho một ứng dụng riêng biệt. Những đặc tính mà mỗi
loại mã này cần còn tuỳ thuộc nhiều vào xác suất lỗi xảy ra trong quá trình truyền
thông.
Đối với một đĩa CD thông thường, lỗi trong âm thanh xảy ra chủ yếu là do
bụi và những vết xước trên mặt đĩa. Vì thế, các mã được lồng vào với nhau. Dữ liệu
được phân bổ trên toàn bộ mặt đĩa. Tuy không được tốt cho lắm, song một mã tái
diễn đơn giản có thể được dùng làm một ví dụ dễ hiểu. Chẳng hạn, chúng ta lấy một
khối số liệu bit (đại diện cho âm thanh) và truyền gửi chúng ba lần liền. Bên máy
thu, chúng ta kiểm tra cả ba phần lặp lại ở trên, từng bit từng bit một, rồi lấy cái nào
có số bầu cao nhất. Điểm khác biệt ở đây là, chúng ta không chỉ truyền gửi các bit
theo thứ tự. Chúng ta lồng nó vào với nhau. Khối dữ liệu này, trước tiên, được chia
ra làm 4 khối nhỏ. Sau đó chúng ta gửi một bit ở khối đầu tiên, tiếp theo một bit ở
khối thứ hai v.v tuần tự qua các khối. Việc này được lặp đi lặp lại ba lần để phân bổ
số liệu ra trên bề mặt đĩa. Trong ngữ cảnh của mã tái diễn đơn giản ở trên, việc làm
này hình như không được hiệu quả cho lắm.
Song hiện nay có những mã có hiệu ứng cao, rất phù hợp với việc sửa lỗi xảy ra đột
ngột do một vết xước hay một vết bụi, khi dùng kỹ thuật lồng số liệu nói trên.
Mỗi mã thường chỉ thích hợp cho một ứng dụng nhất định. Viễn thông trong
vũ trụ bị giới hạn bởi nhiễu nhiệt trong thiết bị thu. Hiện trạng này không xảy ra
một cách đột phát bất thường, song xảy ra theo một chu trình tiếp diễn. Tương tự
như vậy, modem vởỉ dải tần hẹp bị hạn chế vì nhiễu âm tồn tại trong mạng lưới điện
thoại. Những nhiễu âm này có thể được biểu hiện rỗ hơn bằng một mô hình tạp âm



tính, song khó mà chứng minh được rằng một mã nào đó là một mã tốt nếu mã ấy
không có đặc tính này.
Bất cứ mã khối tuyến tính nào cũng được đại diện là (n,m,dmin), trong đó
- n, là chiều dài của từ mã, trong ký hiệu,
- m, là số ký hiệu nguồn được dùng để mã hóa tức thời,
- dmin. là khoảng cách hamming tối thiểu của mã.
Có nhiều loại mã khối tuyến tính, như:
- Mã vòng (Mã Hamming là một bộ phận nhỏ của mã tuần hoàn).
- Mã chẵn lẻ.
- Mã Reed-Solomon.
- MãBCH.
- Mã Reed-Muller.
- Mã hoàn hảo.
Mã khối được gắn liền với bài toán “đóng gói đồng xu” là bài toán gây một
số chú ý trong nhiều năm qua. Trên bề diện hai chiều, chúng ta có thể hình dung
được vấn đề một cách dễ dàng. Lấy một nắm đồng xu, để nằm trên mặt bàn, rồi dồn
chúng lại gần với nhau. Kết quả cho chúng ta một mẫu hình lục giác tương tự như
hình tổ ong. Các mã khối còn dựa vào nhiều chiều khác nữa, không dễ gì mà hình
dung được. Mã Golay có hiệu ứng cao, dùng trong truyền thông qua khoảng không
vũ trụ, sử dụng những 24 chiều. Nếu được dùng là mã nhị phân (thường thấy), các
chiều ám chỉ đến chiều dài của từ mã như đã định nghĩa ở trên.
b) Mã chập
Mã chập (kết hợp) hay còn gọi là mã trellis được sử dụng trong các modem
dải tần âm (V.32, V.17, V.34) và trong các điện thoại di động GSM, cũng như trong
các thiết bị truyền thông của quân đội vũ trang và trong các thiết bị truyền thông với
vệ tinh.
Mục đích của việc tạo ra mã chập là nhằm làm cho tất cả các ký hiệu từ mã
trở thành tổng trọng số của nhiều loại ký hiệu thông điệp trong nhập liệu. Nó tương



Mã chập khác xa so với mã khối, trên phương diện về cấu trúc, công cụ phân
tích và thiết kế. Đặc tính đại số là quan trọng trong cấu trúc của một bộ mã khối tốt
và nâng cao hiệu suất của bộ giải mã. Ngược lại, các bộ mã chập tốt hầunhư đều
được nhận ra qua việc nghiên cứu tính toán toàn diện, và hiệu suất các thuật giải của
việc giải mã xuất phát trực tiếp từ bản chất trạng thái chuỗi của các bộ mã chập hơn
là từ tính chất đại số của mã.
Trong phần này, ta sẽ bắt đầu tìm hiểu cấu trúc của mã chập, cách biểu diễn
mã chập thông qua các giản đồ: hình cây, hình lưới, và trạng thái.
2.2. Cấu trúc mã chập và giản đồ biểu diễn
2.2.1.

Cấu trúc mã chập

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à
N, mỗi thanh ghi dịch có k ô nhớ và đầu ra bộ mã chập có n hàm đại số tuyến tính.
Tỷ lệ mã là R = k/n, số ô nhớ của bộ ghi dịch là Nxk và tham số N còn gọi là chiều
dài ràng buộc (Contraint length) của mã chập (xem hình 2.2).
Giả thiết, bộ mã chập lảm việc với các chữ số nhị phân, thì tại mỗi lần dịch

sẽ có k bit thông tin đầu vào được dịch vào thanh ghi dịch thứ nhất và tương ứng có
k bit thông tin trong thanh ghi dịch cuối cùng được đẩy ra ngoài mà không tham gia
vào quá trình tạo chuỗi bit đầu ra. Đầu ra nhận được chuỗi n bit mã từ n bộ cộng
môđun-2. ẩ hư vậy, giá trị chuỗi đầu ra kênh không chi phụ thuộc vào k bit thông
tin đầu vào hiện tại mà còn phụ thuộc vào (a -l)k bit trước đó, cấu thành lên bộ nhớ
V = (ẩ-l)k và được gọi là mã chập (n, k,ẩ ).
Đen bỏ điéu chế
Hình 2.2. Sơ đồ tổng quát của mã chập.


G.

Gj G, ... Gv

G,

G

GK

(2.1)
Và tất cả các lối vào

L

khác trong ma

trận bằng 0. Do đó nếu lối vào là véctơ ụ, tương ứng véctơ mã

hoá là:
X

= ÍLG

(2.2)

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 tương
đương là có các ma trận (n


Do đó, ma trận sinh từ (2.1) là :
%

111 011

001

000

000 111

011

001 000

000 000

111

01

......

001 000

Từ (2.2) ta có thể suy ra: Nếu chuỗi thông tin vào U = (11011...) được mã hoá
thành chuỗi x=(l 11100010110100...). Bộ mã hoá là hệ thống. Chú ý rằng chuỗi mã
hoá có thể được tạo bằng tổng modul-2 các hàng của tương ứng với “1” trong chuỗi
thông tin.


Hình 2.4. Sơ đồ bộ mã chập với N=3, k=l, n=3 và đa thức sinh (2.8).
2.3.
Biểu dỉễn mã chập
Có ba phương pháp để biểu diễn mã chập đó là: sơ đồ lưới, sơ đồ trạng thái,
và sơ đồ hình cây. Để làm rõ phương pháp này ta tập trung phân tích dựa trên ví dụ
2.2.
2.3.1.
Sơ đồ hình cây
Từ ví dụ 2.2, giả thiết trạng thái ban đầu của các thanh ghi dịch trong bộ mã
đều là trạng thái “toàn 0”. Nếu bit vào đầu tiên là bit “0” (k = 1) thì đầu ra ta
nhận được chuỗi “000” (n = 3), còn nếu bit vào đầu tiên là bit “1” thì đầu ra ta
nhận được chuỗi “111”. Nếu bit vào đầu tiên là bit “1” và bit vào tiếp theo là bit
“0” thì chuỗi thứ nhất là “111” và chuỗi thứ hai là chuỗi “001”. Với cách mã hoá
như vậy, ta có thể biểu diễn mã chập theo sơ đồ có dạng hình cây (xem hình
2.5). Từ sơ đồ hình cây ta có thể thực hiên mã hoá bằng cách dựa vào các bit
đầu vào và thực hiện lần theo các nhánh của cây, ta sẽ nhận được tuyến mã,
từ đó ta nhận được dãy các chuễỉ đầu ra.

23


2.3.2.
Sơ đồ hình lưới
Do đặc tính của bộ mã chập, cấu trúc vòng lặp được thực hiện như sau: chuỗi
n bit đầu ra phụ thuộc vào chuỗi k bit đầu vào hiện hành và (N-l) chuỗi đầu
vào trước đó hay (N-l) X k bit đầu vào trước đó. Từ ví dụ 2.2 ta có chuỗi 3 bit
đầu ra phụ thuộc vào 1 bit đầu vào là “1” hoặc “0” và 4 trạng thái có thể có của
hai thanh ghi dịch, ký hiệu là a=“00”; b = “01”; c = “10”; d = “11”. Nếu ta đặt tên
cho mỗi nút ưong sơ đồ hình cây (hình 2.5) tương ứng với 4 trạng thái của


—

'—*c,b—

—

ìb,d

»

a,b— '—¥C,C—
—'—>d 1

í

-—^b,c—

l

—>d,d

—

^—

Ký hiệu a -> (3 là quá trình chuyên tiêp từ trạng thái a sang trạng thái (3 với
bit đầu vào là bit “1”.
Kết quả ta thu được sơ đồ trạng thái trong hình 2.7 như sau: