ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

TRƯƠNG MINH CHÍNH

MÃ LƯỚI CHO KÊNH FADING RAYLEIGH

LUẬN VĂN THẠC SĨ

Hà Nội, 2010


i

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ

TRƯƠNG MINH CHÍNH

MÃ LƯỚI CHO KÊNH FADING RAYLEIGH
Lattice coding for Rayleigh fading channels

Ngành: Công nghệ Điện tử - Viễn thông
Chuyên ngành: Kỹ thuật điện tử
Mã số: 60.52.70

LUẬN VĂN THẠC SĨ
NGƯỜI HƯỚNG DẪN KHOA HỌC:

TS. NGUYỄN LINH TRUNG

Hà Nội, 10/2010


ii

LỜI CẢM ƠN

Tơi xin bày tỏ lịng biết ơn sâu sắc đến thầy giáo, TS. Nguyễn Linh Trung, người đã
hướng dẫn tơi tận tình, chu đáo trong q trình thực hiện luận văn. Sự chỉ bảo tận tâm
của thầy đã mang lại cho tôi hệ thống các phương pháp, kiến thức cũng như kỹ năng hết
sức quý báu để có thể hồn thiện đề tài một cách tốt nhất.
Tơi xin chân thành cảm ơn Ban Giám hiệu Nhà trường, quí thầy giáo, cơ giáo ở
phịng Đào tạo Sau đại học và thầy giáo, cô giáo khoa Điện tử viễn thông, trường đại học
Công nghệ, đặc biệt là các thầy giáo Bộ môn Xử lý thông tin, khoa Điện tử viễn thông những người mà trong thời gian qua đã dạy dỗ, truyền thụ kiến thức khoa học, giúp tôi
từng bước trưởng thành.
Tôi xin trân trọng cảm ơn Ban Giám hiệu Nhà trường, khoa Vật lý, khoa Sư phạm
Kỹ thuật và phịng Kế hoạch Tài chính trường Đại học Sư phạm, Đại học Huế đã hỗ trợ
tôi trong suốt thời gian học tập và thực hiện luận văn.
Xin chân thành cảm ơn những người thân, gia đình và bạn bè - những người đã hỗ
trợ tôi rất nhiều về cả vật chất lẫn tinh thần để tơi có thể học tập đạt kết quả tốt và thực
hiện thành công luận văn này.
Luận văn này nằm trong khuôn khổ và được hỗ trợ bởi đề tài nghiên cứu khoa học
số QG.10.44 cấp ĐHQG Hà Nội.
Tôi xin chân thành cảm ơn!
Hà Nội, ngày 08 tháng 10 năm 2010
Trương Minh Chính



iii

LỜI CAM ĐOAN

Tôi xin cam đoan luận văn do tôi thực hiện. Những kết quả từ những tác giả trước
mà tơi sử dụng trong luận văn đều được trích dẫn rõ ràng, cụ thể. Khơng có bất kỳ sự
khơng trung thực nào trong các kết quả tính tốn.
Nếu có gì sai trái, tơi xin hồn tồn chịu trách nhiệm.
Hà Nội, ngày 08 tháng 10 năm 2010
Học viên

Trương Minh Chính


iv

TĨM TẮT

Nhiệm vụ chính của luận văn là tìm hiểu về mã lưới cho kênh fading Rayleigh, cụ
thể là tìm hiểu về các chịm sao tín hiệu cấu trúc lưới (lattice constellation) cho kênh
fading Rayleigh đơn antenna và mã Space - Time Blocks Code (STBC) hoàn hảo cho
kênh fading Rayleigh MIMO.
Luận văn đi vào tìm hiểu mơ hình kênh fading Rayleigh đơn antenna và fading
Rayleigh MIMO, các tiêu chí trong thiết kế mã lưới, cơ sở toán học của thiết kế mã lưới
(Algebraic Number Theory và Cyclic Division Algebras) và xây dựng mã lưới cho kênh
fading Rayleigh đơn antenna, mã STBC hồn hảo cho kênh MIMO. Đối với những chịm
sao tín hiệu cấu trúc lưới, giải mã hình cầu trên cơ sở giải mã hợp lẽ cực đại (Maximum
Likelihood ) là một phương thức giải mã tốt. Luận văn đã thực hiện mơ phỏng mã Golden
(là mã STBC hồn hảo cho kênh fading Rayleigh MIMO 2 × 2) và mơ phỏng so sánh giải
mã hình cầu và giải mã hợp lẽ cực đại.

Bên cạnh, luận văn còn thực hiện một mục tiêu phụ là bước đầu tìm hiểu về tiền
mã hóa tuyến tính (linear precoding) với hy vọng tìm thấy mối quan hệ giữa kỹ thuật tiền
mã hóa tuyến tính và kỹ thuật STBC để từ đó có thể có những hướng phát triển mới.


1

MỤC LỤC

LỜI CẢM ƠN

ii

LỜI CAM ĐOAN

iii

TÓM TẮT LUẬN VĂN

iv

DANH MỤC CÁC KÝ HIỆU

3

DANH MỤC CÁC CỤM TỪ VIẾT TẮT

4

DANH SÁCH HÌNH VẼ


5

GIỚI THIỆU

6

1 MÃ LƯỚI CHO KÊNH FADING RAYLEIGH

8

1.1

Mơ hình hệ thống . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2

Các tiêu chí cho việc thiết kế mã lưới . . . . . . . . . . . . . . . . . . . . . 10

1.3

1.4

8

1.2.1

Các tiêu chí dựa trên xác suất lỗi cặp . . . . . . . . . . . . . . . . . 10

1.2.2


Tiêu chí về hình dạng chịm sao lưới . . . . . . . . . . . . . . . . . 13

Xây dựng mã lưới cho kênh fading Rayleigh . . . . . . . . . . . . . . . . . 13
1.3.1

Cách xây dựng mã lưới cho kênh fading Rayleigh . . . . . . . . . . 13

1.3.2

Xây dựng mã lưới từ trường vòng . . . . . . . . . . . . . . . . . . . 14

Giải mã hình cầu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
1.4.1

Tổng quan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17


2
1.4.2

Thuật tốn giải mã hình cầu . . . . . . . . . . . . . . . . . . . . . . 17

2 MÃ LƯỚI CHO KÊNH FADING RAYLEIGH MIMO

23

2.1

Mơ hình kênh MIMO fading Rayleigh . . . . . . . . . . . . . . . . . . . . . 23


2.2

Các tiêu chí thiết kế mã STBC hồn hảo cho kênh MIMO . . . . . . . . . 24

2.3

2.2.1

Các tiêu chí dựa trên xác suất lỗi . . . . . . . . . . . . . . . . . . . 24

2.2.2

Các tiêu chí khác . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

Xây dựng mã STBC hoàn hảo . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.3.1

Cách xây dựng mã STBC hoàn hảo . . . . . . . . . . . . . . . . . . 27

2.3.2

Mã Golden . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.3.3

Mã STBC hồn hảo cho hệ thống 3 × 3 antenna . . . . . . . . . . . 30

2.3.4


Mã STBC hoàn hảo cho hệ thống 4 × 4 antenna . . . . . . . . . . . 32

2.4

Giải mã . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

2.5

Tính tốn mơ phỏng mã golden . . . . . . . . . . . . . . . . . . . . . . . . 35
2.5.1

Tính tốn các tham số mơ phỏng . . . . . . . . . . . . . . . . . . . 35

2.5.2

Mô phỏng mã Golden . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3 TIỀN MÃ HĨA TUYẾN TÍNH VÀ STBC CHO HỆ THỐNG MIMO 40
3.1

Cấu trúc hệ thống . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.1.1

Cấu trúc của bộ lập mã . . . . . . . . . . . . . . . . . . . . . . . . 41

3.1.2

Cấu trúc bộ tiền mã hóa tuyến tính . . . . . . . . . . . . . . . . . . 42

3.1.3


Cấu trúc thu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2

Thiết kế tiền mã hóa tối ưu . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.3

Một số vấn đề cần bàn luận . . . . . . . . . . . . . . . . . . . . . . . . . . 44

KẾT LUẬN

45

TÀI LIỆU THAM KHẢO

46

PHỤ LỤC A. CƠ SỞ TOÁN HỌC CỦA MÃ LƯỚI

48

PHỤ LỤC B. GIẢI MÃ HÌNH CẦU BẰNG MATLAB

61


3


DANH MỤC CÁC KÝ HIỆU

N

Tập hợp số tự nhiên

Z

Tập hợp số nguyên

Q Tập hợp số hữu tỉ
R

Tập hợp số thực

C

Tập hợp số phức

OK Vành O của trường số K
R Phần thực của một số phức
J

Phần ảo của một số phức


4

DANH MỤC CÁC CỤM TỪ VIẾT TẮT


Danh mục các cụm từ viết tắt
STT

Cụm từ
viết tắt

Cụm từ đầy đủ

Nghĩa tiếng Việt

1

BER

Bit Error Rate

Tỷ lệ lỗi bit

2

CSI

Channel State Information

Thơng tin về tình trạng kênh

3

CSIT


Channel State Information

Thơng tin về tình trạng kênh được biết

at the Transmitter

tại phía phát

4

ML

Maximum Likelihood

Hợp lẽ cực đại

5

MIMO

Mutilple input - multiple

Nhiều đầu vào - nhiều đầu ra

output
6

QAM

Quadrature


Amplitude

Điều chế biên độ vng góc

Modulation
7

SNR

Signal to Noise Ratio

Tỷ số tín hiệu trên nhiễu

8

ST

Space - Time

Không gian - thời gian

9

STBC

Space - Time Blocks Code

Mã khối không gian - thời gian



5

DANH SÁCH HÌNH VẼ

1.1

Mơ hình kênh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.2

Mô hình hệ thống truyền dẫn . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3

Hình cầu bao gồm những điểm phải đếm . . . . . . . . . . . . . . . . . . . 19

1.4

Hình cầu chuyển thành hình elipsoid trong miền lưới nguyên . . . . . . . . 20

1.5

Hình elipsoid với tọa độ nguyên có thể đếm được . . . . . . . . . . . . . . 20

1.6


Lưu đồ thuật tốn giải mã hình cầu . . . . . . . . . . . . . . . . . . . . . . 22

2.1

Mô phỏng mã Golden cho hệ thống fading Rayleigh MIMO 2 × 2

2.2

So sánh giải mã hình cầu và giải mã ML . . . . . . . . . . . . . . . . . . . 38

3.1

Cấu trúc hệ thống khai thác CSIT . . . . . . . . . . . . . . . . . . . . . . 41

3.2

Cấu trúc mã hóa hợp kênh khơng gian . . . . . . . . . . . . . . . . . . . . 41

3.3

Cấu trúc STBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.4

Cấu trúc bộ tiền mã hóa tuyến tính . . . . . . . . . . . . . . . . . . . . . . 42

. . . . . 38



6

GIỚI THIỆU

Các chịm sao tín hiệu cấu trúc lưới nhiều chiều với độ phân tập điều chế (modulation
diversity) cao đã được nghiên cứu nhiều và được đánh giá là phù hợp cho q trình truyền
thơng tin qua hệ thống đơn antenna fading Rayleigh. Những cơng trình nghiên cứu đầu
tiên về chịm sao tín hiệu cấu trúc lưới (sau đây gọi tắt là chòm sao lưới) cho kênh fading
[1, 2] được xây dựng trên trường số đại số khai thác độ phân tập điều chế với giả thiết
thơng tin về tình trạng kênh (CSI - Channel State Information) là được biết ở phía thu.
Tuy nhiên, những chịm sao lưới này, với đánh giá là tốt trong mơi trường fading, lại có
nhược điểm là thủ tục gán nhãn bit phức tạp. Để tránh vấn đề này, những cơng trình
tiếp sau tập trung vào việc tìm ra những chịm sao lưới đảm bảo độ phân tập điều chế và
là phiên bản quay của lưới Zn [3, 4]. Như vậy là cùng với sự ra đời của các kiểu thiết kế
chòm sao lưới đối với kênh fading Rayleigh trong hệ thống không dây, các tiêu chí thiết
kế và các cơng cụ thiết kế dần được nâng cấp và hoàn thiện.
Trong những năm gần đây, nhu cầu truyền dẫn tốc độ cao qua hệ thống không dây
đã thành động lực cho việc nghiên cứu các hệ thống truyền thông không dây sử dụng
nhiều antenna ở cả phía phát và phía thu (MIMO). Với mong muốn nâng cao hiệu suất
của hệ thống MIMO, những chiến lược mã hóa và tiền mã hóa cho các kênh MIMO đã
được nghiên cứu nhiều, và hiện nay MIMO vẫn là lĩnh vực nghiên cứu hấp dẫn đối với
những người nghiên cứu về kỹ thuật khơng dây. Các chịm sao lưới cũng được nghiên cứu
để phát triển và áp dụng cho hệ thống MIMO.
Mục tiêu chính của đề tài là tìm hiểu mã lưới cho kênh fading Rayleigh đơn antenna
và fading Rayleigh MIMO.
Bên cạnh, đề tài cịn có một nhiệm vụ có tính chất mở là tìm hiểu về tiền mã hóa
tuyến tính (linear precoding) cho kênh MIMO. Đây cũng là một kỹ thuật nhằm khai thác


7

CSI, mục đích và tiêu chí thực hiện tiền mã hóa tuyến tính có những điểm tương đồng
với kỹ thuật mã hóa STBC.
Luận văn gồm 3 chương, nội dung cụ thể như sau:
Chương 1 trình bày chi tiết mơ hình kênh, các tiêu chí trong thiết kế mã lưới và
thiết kế mã lưới cho kênh fading Rayleigh đơn antenna. Một phần rất quan trọng của
chương 1 là trình bày về giải mã hình cầu (sphere decoder ), là một hình thức giải mã trên
cơ sở Maximum Likelihood (ML), một đặc trưng và là ưu điểm của mã lưới.
Chương 2 mở rộng chương 1 về mã lưới cho kênh fading Rayleigh MIMO và trình
bày về Space - Time Blocks Code (STBC) hoàn hảo cho kênh MIMO fading Rayleigh.
Kết cấu của chương 2 tương tự như chương 1 bao gồm: mơ hình hệ thống, các tiêu chí
cho việc thiết kế STBC hồn hảo và việc thiết kế STBC hồn hảo từ cơng cụ đại số vòng
chia được (Cyclic Division Algebras). Phần giải mã trình bày cách biến đổi STBC về cấu
trúc lưới để có thể sử dụng giải mã hình cầu như đã trình bày ở chương 1. Phần cuối
của chương 2 trình bày việc tính tốn các tham số mơ phỏng và kết quả mơ phỏng mã
Golden, là mã STBC hồn hảo cho hệ thống fading Rayleigh MIMO 2 × 2.
Chương 3 trình bày tổng quan về kỹ thuật tiền mã hóa tuyến tính. Đây là một kỹ
thuật nhằm khai thác CSI, tác động vào tín hiệu đã mã hóa trước khi phát sao cho phù
hợp với CSI có được ở phía phát. Kỹ thuật tiền mã hóa nói chung và tiền mã hóa cho
STBC nói riêng cũng đã được nghiên cứu nhiều [5, 6]. Tuy nhiên các cơng trình nghiên
cứu tiền mã hóa tuyến tính đã thực hiện với giả thiết sau khi đã có mã STBC, xem chúng
là hai quá trình độc lập. Phần cuối của chương gợi ra một số hướng cho sự phát triển của
đề tài.
Phần phụ lục A trình bày cơ sở tốn học của mã lưới và mã STBC hoàn hảo, cụ
thể là lý thuyết số đại số (Algebraic Number Theory) và đại số vòng chia được (Cyclic
Division Algebras).
Phần phụ lục B là đoạn chương trình Matlab thực hiện giải mã hình cầu.


8


Chương 1
MÃ LƯỚI
CHO KÊNH FADING RAYLEIGH
Chương này trình bày việc xây dựng mã lưới cho hệ thống truyền thông tin qua
kênh fading Rayleigh, 1 antenna phát và 1 antenna thu. Phần 1.1 trình bày về mơ hình
kênh fading Rayleigh. Phần 1.2 trình bày các tiêu chí cho việc thiết kế mã lưới. Phần 1.3
trình bày thiết kế mã lưới từ trường vịng và phần cuối cùng trình bày về giải mã hình
cầu (sphere decoder ), đây là một đặc trưng và là lợi thế của mã lưới. Các khái niệm tốn
học liên quan được trích dẫn trong phần phụ lục A.

1.1

Mơ hình hệ thống
Giả sử mơ hình kênh khơng dây là một kênh fading phẳng Rayleigh độc lập [1, 2, 7].

Giả thiết rằng thơng tin về tình trạng kênh (Channel State Information) được biết tại
phía thu và khơng có sự xuất hiện của nhiễu xun ký hiệu. Mơ hình rời rạc theo thời
gian của kênh như sau:
r =αx+n,

(1.1)

trong đó x là một ký hiệu (symbol ) từ tập hợp tín hiệu phức, n là nhiễu Gauss trắng
phức và α là hệ số fading phức theo phân bố Gauss trung bình 0 (hình 1.1). Các hệ số
fading đối với một ký hiệu được giả thiết là độc lập đối với các ký hiệu tiếp theo.
Vì phía thu biết được CSI nên các pha ϕ của các hệ số fading α = |α| eiϕ có thể
được loại bỏ, do đó ta có:
r = αx + n,

(1.2)



9

Transmitter

x

r

Channel
α, n

Receiver

α

Hình 1.1: Mơ hình kênh [7]
trong đó α = α là hệ số fading thực theo phân bố Rayleigh và n = n e−jϕ vẫn là nhiễu
Gauss trắng phức. Với mơ hình (1.2), ta có thể giả sử rằng x ∈ R và n là biến ngẫu nhiên
thực và các hệ số fading là độc lập giữa một ký hiệu thực được phát và ký hiệu tiếp theo.
Khi xem xét quá trình truyền dẫn mã, mỗi từ mã là một vector thực n chiều
x = (x1 , x2 , ..., xn ) được lấy ra từ chịm sao tín hiệu hữa hạn S ⊆ Rn . Mỗi thành phần
vector bị ảnh hưởng bởi một hệ số fading thực độc lập.
Xét hệ thống truyền dẫn như hình vẽ (1.2): Bộ ánh xạ (mapper ) kết hợp một bộ

Information

u


Bit mapper

Lattice

x

Encoder M

bits

α

*
α

n

+
x
ˆ, u
ˆ
1

ML

r

Detection

Hình 1.2: Mơ hình hệ thống truyền dẫn [7]

các bit đầu vào với một điểm u ∈ Zn . Tiếp theo đó u được ánh xạ đến một điểm x sử
dụng mã hóa lưới.
Như vậy, x thuộc chịm sao tín hiệu n chiều S lấy ra từ tập hợp các điểm lưới


10
Λ = {x = uM }, trong đó u là một vector nguyên, M là ma trận sinh của lưới.
Các điểm chòm sao được phát qua kênh fading Rayleigh độc lập như đã mô tả ở
phần trước:
r = xH + n,

(1.3)

trong đó r = (r1 , r2 , ..., rn ) là điểm thu được; n = (n1 , n2 , ..., nn ) là vector nhiễu, có các
thành phần thực ni là các biến ngẫu nhiên độc lập phân bố Gauss với trung bình 0 và
phương sai bằng N0 , H là ma trận fading kênh có dạng đường chéo H = diag (α1 , α2 , ..., αn ),
với αi giá trị thực là các biến ngẫu nhiên độc lập phân bố Rayleigh với moment bậc hai
bằng 1.
Với giả thiết CSI được biết tại phía thu, giải mã trên cơ sở hợp lẽ tối đa (Maximum
Likelihood - ML) yêu cầu tối thiểu hóa độ đo sau:
n

m (x |r, α) =

1

|ri − αi xi |2

(1.4)


ˆ phải thỏa mãn:
Nói cách khác, điểm giải mã x
ˆ = arg min r − xH
x
x∈S

2

= arg min r − x

2

(1.5)

x ∈S

trong đó S = HS.
Việc tối thiểu hóa (1.5) là một phép tốn có độ phức tạp cao đối với một chịm sao
tín hiệu bất kỳ, với số lượng nhiều điểm. Trong trường hợp của chúng ta là mã lưới, một
thuật toán giải mã dựa trên ML hiệu quả hơn đó là giải mã hình cầu mà chúng ta sẽ bàn
tiếp trong phần cuối của chương này.

1.2

Các tiêu chí cho việc thiết kế mã lưới
Việc xây dựng các tiêu chí cho thiết kế mã lưới được xem xét trên cơ sở xác suất lỗi

cặp và hình dạng của chịm sao tín hiệu.

1.2.1


Các tiêu chí dựa trên xác suất lỗi cặp

Để đưa ra các tiêu chí cho việc thiết kế mã cho hệ thống như đã đề cập ở phần
trước, trước hết chúng ta ước lượng xác suất lỗi của nó [1, 8].


11
Ký hiệu Pe (S) là xác suất lỗi khi phát một điểm của chịm sao tín hiệu hữu hạn S,
ˆ ) là xác suất lỗi cặp, đây là xác suất mà khi x được phát, điểm nhận được
và P (x → x
ˆ hơn so với x theo độ đo đã xác định trong công thức (1.4).
gần với x
Đối với một chịm sao tín hiệu S bất kỳ, với |S| là số phần tử của chịm sao, ta có:
1
|S|

Pe (S) =

Pe (S|x)
x∈S

Cơng thức này có thể đơn giản hơn nhiều trong trường hợp mã lưới. Vì một lưới vơ
hạn là đồng dạng hình học, chúng ta có thể viết một cách đơn giản xác suất lỗi khi phát
một điểm thuộc lưới Pe (Λ) = Pe (Λ|x) cho bất kỳ điểm x ∈ Λ được phát. Giả sử rằng S
là một chòm sao hữu hạn lấy ra từ Λ, ta có:

Pe (S) ≤ Pe (Λ) =

ˆ =x

x

ˆ) ≤
P (x → x

ˆ =x
x

ˆ)
P (x → x

Tức là, xác suất của hợp các biến cố nhỏ hơn hoặc bằng tổng các xác suất của các biến
cố thành phần.
ˆ |α). Một
Trước hết, chúng ta đưa ra biên trên của xác suất lỗi có điều kiện P (x → x
ˆ hơn x.
lỗi xuất hiện, trong khi giải mã với quy tắc ML, nếu điểm nhận được r gần với x
Có nghĩa là, m (ˆ
x|r, α) ≤ m (x|r, α). Xác suất lỗi cặp có điều kiện là:
n

ˆ |α) = P
P (x → x

n

2

i=1
n


|ri − αi xˆi | ≤

i=1

|ri − αi xˆi |2 |x
n
2

=P
i=1
n

=P
i=1

|αi (xi − xˆi ) + ni | ≤

i=1

|ni |2

n

αi2 (xi − xˆi )2 + 2

i=1

αi (xi − xˆi ) ni ≤ 0


n

Đặt χ =
i=1

αi (xi − xˆi ) ni là tổ hợp tuyến tính của các biến ngẫu nhiên Gauss ni .

Ta có χ là biến ngẫu nhiên Gauss với trung bình bằng 0 và phương sai bằng:
n

σχ2

= N0
i=1

1
Cho A =
2

αi (xi − xˆi )2 .

n

i=1

αi (xi − xˆi )2 là hằng số. Chúng ta có thể viết xác suất lỗi cặp có điều

kiện theo χ và A.
ˆ |α) = P (χ ≥ A) = Q (A/σχ ) ,
P (x → x



12
trong đó hàm Q (x) được định nghĩa bởi Q (x) = (2π)

∞

−1
x

exp −t2 /2 dt. Vì Q (x) bị

1
chặn trên với exp −x2 /2 , xác suất lỗi cặp có điều kiện trở thành:
2
A2
1
ˆ |α) ≤ exp − 2
P (x → x
2
2σχ

1
1
= exp −
2
8N0

n


αi (xi − xˆi )2

i=1

ˆ |α) qua hệ số fading α:
Xác suất lỗi cặp được tính bằng trung bình P (x → x

ˆ) =
P (x → x

∞
0

1
2

ˆ |α) P (α) dα ≤
P (x → x

∞
0

exp −

1
8N0

n

i=1


αi (xi − xˆi )2 P (α) dα,
2

Thay P (α) dα = P (α1 ) . . . P (αn ) dα1 . . . dαn , trong đó P (αi ) = 2αi e−αi là phân
bố Rayleigh chuẩn, vào biểu thức cuối cùng chúng ta thu được:
ˆ) ≤
P (x → x
=

1
2
1
2

n

i=1
n

i=1

∞
0
∞
0

exp −

1

8N0

n

i=1

αi (xi − xi )2 P (αi ) dαi =

2αi exp −Ci αi2 dαi

(xi − xˆi )2
trong đó Ci = 1 +
8N0
Tính tích phân ta được:
1
ˆ) ≤
P (x → x
2

n

1
(xi − xˆi )2
i=1 1 +
8N0

(1.6)

Đối với trường hợp tỷ số tín hiệu trên nhiễu (SN R) lớn thì:
n


1
1
1 (8N0 )
ˆ) ≤
P (x → x
2 =
2 x =ˆx (xi − xˆi )
2 dp (x, xˆ)2
i
i
8N0

(1.7)

ˆ khi
|xi − xˆi | là khoảng cách ( − product distance) giữa x và x

ˆ) =
trong đó dp (x, x

xi =ˆ
xi

hai điểm khác nhau

thành phần
n

Pe (S) ≤


=L

1 (8N0 )
.
2 dp (x, x
ˆ)2

(1.8)

Trong (1.8), L là số thành phần khác nhau nhỏ nhất của hai điểm bất kỳ thuộc chòm sao
và được gọi là độ phân tập điều chế (modulation diversity) hay bậc phân tập (diversity
order ) của chòm sao lưới.
Để hạn chế biên trên của bất đẳng thức (1.8), các tiêu chí của chúng ta là tối đa
(L)

hóa L và và dp,min (với dp,min = min dp ).


13

1.2.2

Tiêu chí về hình dạng chịm sao lưới

Để thiết kế chòm sao lưới, hai hoạt động quan trọng là tạo nhãn bit (bit labelling)
và tạo hình dạng chịm sao (constellation shaping). Hai vấn đề này có quan hệ chặt chẽ
với nhau và có sử thỏa hiệp giữa độ phức tạp và hiệu suất thực hiện.
Quá trình gán nhãn bit bao gồm quá trình ánh xạ các bit đầu vào với một điểm
thuộc chịm sao tín hiệu. Nếu chúng ta muốn tránh sử dụng một bảng tìm kiếm (look-up

table) lớn để thực hiện gán nhãn bit thì chúng ta cần một thuật toán đơn giản hơn để
kết hợp các bit với các điểm tín hiệu.
Trong q trình thiết kế chịm sao lưới cho kênh fading, các chịm sao có hình khối
là một lựa chọn tối ưu trong nghĩa là lưới thiết kế là một phiên bản quay của lưới Zn
[3, 7].

1.3

Xây dựng mã lưới cho kênh fading Rayleigh

1.3.1

Cách xây dựng mã lưới cho kênh fading Rayleigh

Trong phần trước, chúng ta đã xét các tiêu chí cho việc thiết kế mã lưới, cụ thể như
sau:
1. Tối đa hóa bậc phân tập L.
(L)

ˆ)
2. Tối đa hóa giá trị dp,min = min dp (x, x
3. Các chòm sao lưới là một phiên bản của lưới Zn .
Ta xây dựng lưới thỏa mãn các tiêu chí trên thơng qua trường số đại số. Điều này
xuất phát từ những cơ sở và phương thức thực hiện như sau:
1. Tối đa hóa bậc phân tập L: Xây dựng lưới đại số thực trên vành OK , do lưới đại
số xây dựng trên trường số thực có bậc phân tập lớn nhất L = n, với n là bậc của
trường số K. (xem Định lý 9 phần Phụ lục A). Từ cơ sở nguyên thuộc OK , nhúng
vào Rn qua phép nhúng chính tắc để nhận được một lưới đại số. (xem Định nghĩa
27, Phụ lục A).



14
2. Tối đa hóa dp,min : Để đánh giá tiêu chí về dp,min , ta xây dựng lưới từ một ideal thuộc
vành OK , vì ideal của vành OK cũng có cơ sở nguyên n thành phần (xem Định lý
10, Phục lục A). Đặc biệt trong trường hợp lưới sinh ra từ cơ sở nguyên của một
ideal chính (ideal được sinh ra từ một phần tử) của vành OK thì dp,min của lưới có
thể được tính một cách tường minh và chỉ phụ thuộc vào dK . (Xem Định nghĩa và
Tính chất của ideal chính của một vành, Phụ lục A). Do đó ta phải tối thiểu hóa
biệt thức của trường số dK . (xem Định nghĩa 25, Phụ lục A).
3. Các chòm sao lưới là một phiên bản của lưới Zn : Với một giá trị n cho trước, chúng
ta phải xác định một trường số K bậc n và một ideal I ⊆ OK sao cho lưới Λ = (I, qβ )
là tương đương với Zn . (xem Định nghĩa 31, Phụ lục A). Một phiên bản tỷ lệ của
√ n
Zn có dạng: ( cZ) , c ∈ Z, do đó định thức của lưới này là det (G) = cn .

Ta lại có: (Cơng thức (8), Phụ lục A)
det (Λ) = N (β) N (I)2 |dK |
Do đó:
N (β) N (I)2 |dK | = cn

(1.9)

Như vậy, ta phải xác định β thỏa mãn (1.9).

1.3.2

Xây dựng mã lưới từ trường vịng

Phần này trình bày tổng qt việc xây dựng mã lưới từ trường vòng (xem [7]) Q (ζp ),
trong đó ζ = ζp = e−2iπ/p là căn bậc p của đơn vị, và quan tâm đến trường hợp p ≥ 5


[7, 8]. Bậc của Q (ζp ) trên Q là (p − 1). Trường K = Q ζp + ζp−1 là một trường con của
Q (ζp ), được sinh ra bởi phần tử ζp + ζp−1 = 2 cos (2π/p). Đây là trường thực và có bậc
trên Q là n = (p − 1) /2 và biệt thức của nó được xác định bằng:
dK = p(p−3)/2

(1.10)

Trường K có vành nguyên là OK = Z ζp + ζp−1 .
Một cơ sở nguyên của K được xác định như sau: ej = ζpj + ζp−j

n
j=1

. Có n phép

nhúng của K vào C được xác định là:
σk (ej ) = ζpkj + ζp−kj

(1.11)


15
Điều kiện cần để có được một lưới ideal Zn là tìm một phần tử β thỏa mãn:
N (β) p

(p−3)
2

= cn = p


(p−1)
2

(1.12)

Phần tử β = (1 − ζp ) 1 − ζp−1 có N (β) = p.
Định lý sau chỉ ra rằng, với việc sử dụng thành phần này, chúng ta hồn tồn có
thể xây dựng lưới Zn .
Định lý 1.1.
Cho K = Q ζp + ζp−1 và β = (1 − ζp ) 1 − ζp−1 thì Λ = OK , p1 qβ

tương đương

với Zn , trong đó qβ = Tr (βxy)

Ta chứng minh định lý này bằng cách tính trực tiếp:
Ta có:
β = (1 − ζp ) 1 − ζp−1 = 2 − ζp + ζp−1

(1.13)

σj (ζp ) và σj = σj (β) với j = 1, . . . , n là các liên hiệp của ζp và β.
n

Tr ζpk + ζp−k =
j=1

σj ζpk + ζp−k = −1,


∀k = 1, . . . , n

(1.14)

Sử dụng (1.14) ta có:
n
j=1

βj σj ζpk + ζp−k =

n
j=1

2 − σj ζp + ζp−1

σj ζpk + ζp−k

= −2 − nj=1 σj ζpk+1 + ζp−k−1 + ζp−k+1 + ζpk−1

 −p nếu k = ±1
=
 0 khác

Chúng ta tính tiếp qβ (ei ej ) với i = j và i = j sử dụng (1.14) và (1.15):

qβ (ei ei ) =
=
=

n

j=1

βj σj ζp2i + ζp−2i + 2

n
β σ ζ 2i + ζp−2i + 2
 j=1 j j p
 p nếu i = n

 2p khác

−(i+j)

n
βk σk ζpi+j + ζp
 k=1
 −p nếu |i − j| = 1
=
 0 khác

qβ (ei ej ) =

n
j=1

+

2 − σj ζp + ζp−1

n

k=1

−(i−j)

βk σk ζpi−j + ζp

(1.15)


16
Với kết quả trong phần chứng minh trên, ta suy ra ma trận của qβ trong cơ sở {e1 , . . . , en }
là:















2

−1


0

−1

2

−1

0
..
.
0

...



0






... ...

−1 2



... ... ...
−1 0 


..
. −1 2 −1 

...
0 −1 1
..

.

(1.16)

Ma trận này mà một đồng hình của ma trận đơn vị, ta có thể kiểm tra điều này bằng
cách chọn cơ sở mới {e1 , . . . , en } mà en = en và ej = ej + ej+1 , j = 1, . . . , n, ma trận trên
trở thành ma trận Gram của lưới Zn .

Ma trận chuyển đổi cơ sở từ ej sang ej là:







T =






1

1

...

0
..
.

1

1 ...
..
.

1
..
.

0

1

1

...


0

1

0 ...
0

0

1

1













(1.17)

Như vậy, lưới Zn tương ứng thu được như sau:
Lưới sinh ra bởi vành nguyên có ma trận sinh n × n, trong đó n là số phép nhúng

trường K:
Mk,j = σk (ej ) = ζpkj + ζp−kj = 2 cos

2πkj
p

Thành phần β biểu diễn dưới dạng ma trận đường chéo:
A = diag

σk (β)

Kết quả cuối cùng, ma trận sinh của lưới Zn quay là:
1
R = √ T MA
p
Ta có: dp,min = p−

n−1
2

.


17

1.4

Giải mã hình cầu

1.4.1


Tổng quan

Giải mã hình cầu [7, 9, 10] là phương thức giải điều chế trên cơ sở ML cho các chịm
sao tín hiệu lưới bất kỳ. Nó giải quyết vấn đề điểm lưới gần nhất: tức là tìm các điểm lưới
gần nhất với một điểm nhận được.
Vấn đề có tính chất chìa khóa tạo nên tính hiệu quả của giải mã hình cầu là số
lượng các điểm lưới tìm thấy trong một hình cầu nhỏ hơn rất nhiều so với số lượng điểm
trong hình lập phương chứa hình cầu này.
Để tránh liệt kê tất cả các điểm của chịm sao tín hiệu, thuật tốn giải mã lưới tìm
√
trong các điểm thuộc lưới Λ những điểm nằm trong hình cầu với bán kính C cho trước,
tâm tại mỗi điểm nhận được. Sau đó, chỉ tính độ đo đối với những điểm thuộc hình cầu
này.
Những bước chủ yếu của thuật toán này là:
1. Thiết lập điểm gốc tại điểm nhận được r.
2. Xét lưới Λ = {x = uM | u ∈ Zn }.
3. Định nghĩa hàm Q (u) = x

2

= xxT = uGuT trong đó G = M M T là ma trận

Gram của lưới.
4. Tìm tất cả các điểm trong hình cầu bán kính

√

C bằng cách giải bất đẳng thức:


Q (u) ≤ C
5. Chọn x thỏa mãn min r − x

1.4.2

2

Thuật tốn giải mã hình cầu

Chúng ta xem lưới Λ như là kết quả của phép biến đổi tuyến tính. Vấn đề đặt ra là
phải giải phương trình:
min r − x
x∈Λ

2

= min

w∈r−Λ

w

2

(1.18)

Điều này có nghĩa là: Vì lưới Λ là kết quả của biến đổi tuyến tính nên r − Λ cũng là một
lưới và chúng ta phải xác định vector w ngắn nhất thuộc lưới này.



18
Ta có: x = uM với u ∈ Zn .
Đặt: r = ρM với ρ = (ρ1 , . . . , ρn ) ∈ Rn
w = ξM với ξ = (ξ1 , . . . , ξn ) ∈ Rn
n
i=1 ξi vi

Ta có w =

trong đó vi là các vector cơ sở của lưới và ξi = ρi − ui , i =

1, . . . , n là sự dịch chuyển các trục tọa độ.
√
Hình cầu bán kính C, tâm tại điểm nhận được được biến đổi thành hình ellipsoid
với tâm lại gốc của hệ tọa độ mới được xác định bằng ξ:
n

w

2

n

= Q(ξ) = ξM M T ξ T = ξGξ T =
i=1 j=1

gij ξi ξj ≤ C.

(1.19)


.
Phân tích Cholesky ma trận Gram G = M M T đưa ra G = RT R, trong đó R là ma
trận tam giác trên, đo đó:
n
T

T

Q(ξ) = ξR Rξ = Rξ

T 2

=

n

(rii ξi +
i=1

j=i+1

rij ξj )2 ≤ C.

(1.20)

Thế qii = rii2 với i = 1, . . . , n và qij = rij /rii với i = 1, . . . , n, j = i + 1, . . . , n, ta có
thể viết lại như sau:
n

n


Q(ξ) =

n

rij ξj )2 =

qii (ξi +
i=1

j=i+1

i=1

qii Ui2 ≤ C,

(1.21)

trong đó, hệ tọa độ mới được định nghĩa là:
n

Ui = ξi +

rij ξj ,

i = 1, . . . , n,

(1.22)

j=i+1


xác định một elipsoid với hình dạng chính tắc. Bắt đầu từ Un và tính lùi, chúng ta thu
được các công thức xác định biên của elipsoid như sau:
−
−

C
≤
qnn

Un

≤

C − qnn Un
≤ Un−1 ≤
qn−1,n−1
..
.

C
qnn
C − qnn Un
qn−1,n−1

(1.23)

Các khoảng tương ứng của thành phần nguyên un và un−1 xác định bằng cách thay



19
ξi = ρi − ui trong (1.22) và (1.23):
−
−

C
+ ρ n ≤ un ≤
qnn

C
+ ρn
qnn

C − qnn ξn2
+ ρn−1 + qn−1, nξn ≤ un−1
qn−1,n−1
≤

C − qnn ξn2
+ ρn−1 + qn−1, nξn
qn−1,n−1

trong đó x là giá trị nguyên nhỏ nhất lớn hơn x và x là giá trị nguyên lớn nhất nhỏ
hơn x. Đối với thành phần nguyên thứ i ta có:


n
n
n
− 1 (C −

qll (ξl +
qlj ξj )2 ) + ρi +
qij ξj 

 ≤ ui
q
ii


j=i+1
l=i+1
j=l+1




n
n
n

 1
2
qlj ξj ) ) + ρi +
qij ξj 
qll (ξl +
(C −
≤
qii
j=i+1
j=l+1

l=i+1

(1.24)

Để đơn giản, ta thiết lập gốc của tọa độ r = 0 (có nghĩa là ρi = 0, i = 1, . . . , n), lúc đó
362

The Sphere Decoder

thuật tốn giải mã hình cầu trở thành thuật tốn đếm điểm Finke-Pohst [9].

inside the ellipse in Fig. 4.4 are visited from the bottom to
thehọc
topcủa
andphương
from leftpháp
to right.
Minh họa hình
được thể hiện như hình 1.3, 1.4 và 1.5.

v2
P

v1

Fig. 4.2 The sphere is centered at the origin and includes the lattice points to be enumerated. Hình 1.3: Hình cầu bao gồm những điểm phải đếm [7]

The search algorithm proceeds very much like a mixed radix counter
on the digits ui , with the addition that the bounds change whenever
there is a carry operation from one digit to the next. In practice, the

bounds can be updated recursively by using the following equations
n

Si = Si (ξi+1 , . . . , ξn ) = ρi +

qil ξl
l=i+1
n

⎛

n

⎞2


20

4.1. The Sphere Decoder Algorithm

2

U
2

U
1

u


363

u1

HìnhFig.
1.4:
cầu ischuyển
thành
hình
elipsoid
tronglattice
miềndomain.
lưới nguyên [7]
4.3 Hình
The sphere
transformed
into an
ellipsoid
in the integer
This value is compared to the minimum square distance d2 (initially
set equal to C) found so far in the search. If it is smaller then we have
a new candidate closest point and the search can go on using a new
sphere
with
smaller
radius.
364 The
Sphere
Decoder
The advantage of this method is that we never test vectors with a

norm greater than the given radius.U2Every tested vector requires the
computation of its norm, which entails n multiplications and n − 1
additions. The increase in the number of operations needed to update
the bounds (4.7) is largely compensated for by the enormous reduction
in the number of vectors tested especially when the dimension increases.
In order to
√ be sure to always find13a lattice point inside the sphere we
10
11radius
of the lattice.
Otherwise,
must select C equal to the covering
9
12
U1
7
we do bounded distance decoding6 and the8 decoder can signal an erasure
2
3
4 5
whenever no point is found inside the
sphere. A judicious choice of C
1
can greatly speed up the decoder. In practice the choice of C can be
adjusted according to the noise variance N0 so that the probability of

Fig.
4.4 The
rotation enables
to enumerate

the Zn
–lattice
Hình
1.5:coordinate
Hình elipsoid
với tọa
độ ngun
có
thể points.
đếm được

[7]

a decoding failure is negligible. If a decoding failure is detected, the
operation can either be repeated with a greater radius or an erasure
can be declared.
The kernel of the Sphere
√ Decoder (the enumeration of lattice points
inside a sphere of radius C) requires the greatest number of operations. The complexity is obviously independent of the constellation size,
i.e. the number of operations does not depend on the spectral efficiency