BỘ QUỐC PHÒNG
HỌC VIỆN KỸ THUẬT QUÂN SỰ
NGUYỄN THỊ HỒNG NHUNG
GIẢI MÃ MỀM CHO MÃ KHỐI
DỰA TRÊN KHÔNG GIAN MÃ ĐỐI NGẪU
Chuyên ngành: Kỹ thuật Điện tử
Mã số: 9.52.02.03
TÓM TẮT LUẬN ÁN TIẾN SĨ KỸ THUẬT
HÀ NỘI – NĂM 2019
CÔNG TRÌNH ĐƯỢC HOÀN THÀNH TẠI
HỌC VIỆN KỸ THUẬT QUÂN SỰ - BỘ QUỐC PHÒNG
Người hướng dẫn khoa học:
1. PGS. TS VŨ THANH HẢI
2. PGS. TS PHẠM KHẮC HOAN
Phản biện 1:
Phản biện 2:
Phản biện 3:
Luận án được bảo vệ tại Hội đồng đánh giá luận án cấp Học viện
theo quyết định số……/….., ngày …..tháng…..năm……của
Giám đốc Học viện Kỹ thuật Quân sự, họp tại Học viện Kỹ thuật
Quân sự vào hồi……giờ…ngày….tháng….năm….
Có thể tìm hiểu luận án tại:
- Thư viện Học viện Kỹ thuật Quân sự
- Thư viện Quốc gia
1
MỞ ĐẦU
Một trong các giải pháp nhằm góp phần khai thác tối đa khả năng
truyền dẫn của kênh là sử dụng các loại mã kênh có đặc tính tự sửa sai.
Mã kênh có thể phân làm 2 loại là mã khối và mã chập, đại diện
bởi hai họ mã mạnh và sử dụng phổ biến hiện nay là mã Turbo và
LDPC (Low Density Parity Check). LDPC hiện đang dần thay thế
Turbo trong một số hệ thống truyền tin số nhờ các ưu điểm: chất
lượng giải mã cao, độ phức tạp tính toán thấp với phương pháp giải
mã đơn giản. LDPC không phù hợp với các hệ thống truyền tin yêu
cầu thời gian thực với tốc độ cao và độ trễ thấp nên LDPC chưa phải
là lựa chọn thay thế hợp lý cho mã Turbo trong các hệ thống này.
Mã Turbo là sự kết nối gồm hai hay nhiều bộ mã chập riêng biệt
để tạo ra một mã tốt hơn và cũng lớn hơn. Mã Turbo yêu cầu giải mã
MAP (Maximum A posteriori Probability) trên lưới của các mã
thành phần nên độ phức tạp rất lớn chỉ có thể áp dụng cho các mã
ngắn. Nhược điểm là độ phức tạp rất lớn, tốc độ mã tỉ lệ nghịch với
chất lượng mã. Điều này làm giảm tính khả dụng của mã Turbo trong
các hệ thống truyền tin yêu cầu độ trễ thấp.
Mã tích (Product Codes) có khoảng cách mã lớn được xây dựng từ
các mã thành phần có độ dài và khoảng cách mã nhỏ cho phép đạt chất
lượng và độ phức tạp có thể so sánh với mã Turbo với số vòng lặp giải
mã nhỏ hơn. Có nhiều thuật toán giải mã mã tích được trình bày từ
khi mã tích được biết đến. Các thuật toán này nhìn chung phân làm
hai loại: Các thuật toán đơn giản cho chất lượng giải mã thấp và các
thuật toán cho chất lượng giải mã cao nhưng có độ phức tạp rất cao.
Phương pháp giải mã Viterbi đầu ra mềm (gần giống với giải mã
MAP) cho mã thành phần, trên mã đối ngẫu, nhằm giảm độ phức tạp
2
mã tích, đem lại chất lượng giải mã cao nhưng độ phức tạp vẫn quá
lớn và không có tính khả dụng.
Giải mã quyết định mềm cho phép nâng cao chất lượng giải mã,
nhưng vẫn cần có những cải tiến để giảm độ phức tạp nhất là khi sử
dụng cho các mã có cấu trúc liên kết như mã tích. Mã tích chính là mã
khối dài có thể được xây dựng bởi hai hay nhiều mã khối thành phần
ngắn hơn. Mã tích có tốc độ mã hóa bằng tích các mã thành phần nên
việc lựa chọn các mã thành phần là các mã khối có tốc độ mã hóa cao là
ý tưởng hợp lý. Với các mã có tỉ lệ mã hóa cao, vấn đề giải mã bằng mã
đối ngẫu sẽ giảm được sự phức tạp mà vẫn đảm bảo thông tin giải mã
như mã gốc. Đây chính là lý do lựa chọn đề tài “Giải mã mềm cho mã
khối dựa trên không gian mã đối ngẫu”.
Trong quá trình nghiên cứu, Luận án hướng đến việc xây dựng
được thuật toán giải mã mới nhằm nâng cao chất lượng giải mã của
mã khối để có thể tận dụng khả năng kiểm soát lỗi của mã tích.
Mục đích nghiên cứu:
- Đề xuất các thuật toán giải mã mềm mới cho mã khối có độ phức
tạp thấp, chất lượng giải mã tốt.
- Đề xuất các thuật toán giải mã mềm cho các mã khối thành phần
của mã tích với khả năng ứng dụng thực tế.
Nhiệm vụ nghiên cứu:
- Nghiên cứu mã khối và các thuật toán giải mã mềm cho mã khối
- Nghiên cứu các thuật toán giải mã mã kênh có chất lượng giải mã cao.
- Nghiên cứu mã tích với mã thành phần là các mã khối và các
thuật toán giải mã.
Phương pháp nghiên cứu
- Sử dụng phương pháp phân tích lý thuyết trong mã kênh, đề xuất
các thuật toán giải mã mềm cho mã khối.
3
- Sử dụng kỹ thuật mô phỏng Monte-Carlo trên Matlab để kiểm
chứng các kết quả nghiên cứu.
Ý nghĩa khoa học và thực tiễn:
Vấn đề quan trọng hiện nay là nghiên cứu, đề xuất các thuật toán
giải mã mềm nhận thông tin giải mã trong không gian mã đối ngẫu,
có cơ sở lý thuyết chắc chắn, đồng thời đề xuất ứng dụng cho họ mã
cụ thể, như mã tích với các mã thành phần là mã khối mật độ cao
nhằm giảm độ phức tạp.
Kết quả đạt được của luận án có thể là giải pháp thay thế cho các kỹ
thuật FEC hiện đại mang tính thực tiễn cao trong các hệ thống truyền
dẫn vô tuyến, đặc biệt là các dịch vụ thời gian thực.
Bố cục của Luận án:
Luận án được trình bày gồm 3 chương
Chương 1: Trình bày tổng quan về các phương pháp giải mã khối.
Chương 2: Nghiên cứu, đánh giá các hướng phát triển của đề tài liên
quan đến giải mã mềm cho mã khối từ vai trò mang tin của mã đối
ngẫu, đưa ra hướng nghiên cứu tiếp theo của Luận án.
Chương 3: Xây dựng cơ sở lý thuyết cho các thuật toán giải mã
mềm của các mã khối thành phần của mã tích. Đánh giá chất lượng
các thuật toán đề xuất và so sánh với các công trình đã được công bố.
Chương 1. TỔNG QUAN VỀ MÃ KHỐI TUYẾN TÍNH
Mã hóa kênh đóng vai trò vô cùng quan trọng trong kỹ thuật truyền
dẫn thông tin số, trong đó mã khối là họ mã có khả năng sửa và phát
hiện lỗi khá tốt đảm bảo độ chính xác cho hệ thống truyền tin.
1.1 Mã khối nhị phân tuyến tính
1.1.1 Mô hình hệ thống thông tin
Một hệ thống thông tin số được thể hiện theo sơ đồ khối Hình 1.1.
4
𝐮
Nguồn
Mã hóa
kênh
𝐜
𝐱
Điều
chế
Kênh
truyền
𝐮
Đích
𝐜′
Giải mã
kênh
𝐲
Giải
điều chế
Hình 1. 1. Hệ thống thông tin số
1.1.2 Ma trận sinh
Mã tuyến tính
không gian véctơ
là một không gian con
chiều của một
thành phần. Do vậy có thể tìm được
từ mã độc
lập tuyến tính trong , sao cho:
Với
{
sinh của mã
c u1 g1 u2 g2
}
và
u
g
g1 , g2 ,
(1.1)
,g
là ma trận
.
1.1.3 Ma trận kiểm tra
Đối với một ma trận sinh bất kỳ
tính, tồn tại một ma trận
Do đó, một tổ hợp gồm
được tạo ra bởi ma trận sinh
có
có
hàng độc lập tuyến
hàng độc lập tuyến tính.
thành phần là một từ mã hợp lệ của mã
khi và chỉ khi:
[ ]
(1.5)
1.2 Giải mã mã khối.
1.2.1 Các phương pháp giải mã mã khối
a) Giải mã quyết định cứng
Phương pháp giải mã đơn giản nhất là giải mã quyết định cứng
(HDD: Hard Decision Decoding). Để thuận tiện, trong Luận án gọi
tắt HDD là giải mã cứng.
b) Giải mã quyết định mềm
5
Giải mã tính đến thông tin tin cậy hoặc sử dụng các giá trị xác
suất hay giá trị hợp lý (likelihood) thay vì dữ liệu được lượng tử hóa
tại đầu vào bộ giải mã được gọi là giải mã quyết định mềm (SDD:
Soft Decision Decoding) - Gọi tắt là giải mã mềm.
Giải mã lặp là kỹ thuật sử dụng thuật toán giải mã đầu ra mềm
được lặp lại nhiều lần trước khi cho kết quả giải mã cuối cùng, nhằm
cải thiện xác suất lỗi của hệ thống mã hóa.
Thông tin bên ngoài
(tới bước lặp tiếp theo)
Thông tin từ kênh
Một bước lặp của thuật toán
(Thông tin nội tại)
Thông tin bên ngoài
(từ bước lặp trước đó
Hình 1. 2. Nguyên lý về giải mã lặp
1.2.2 Chất lượng giải mã
a) Chất lượng giải mã mềm
Đối với việc xác định chất lượng giải mã, sử dụng công thức giới
hạn liên kết union bound .
Xác suất phát hiện lỗi cho một symbol
từ mã trong
với
không gian truyền có giới hạn:
⁄
1.6
Xác suất lỗi symbol khi giải mã mềm là [40]:
(
)
Xác xuất lỗi symbol gồm
(√
⁄
)
1.9
bit không mã là:
(√
Vậy,
Độ lợi mã hóa tiệm cận
)
(1.10)
6
b) Chất lượng giải mã cứng
Trường hợp giải mã cứng với xác suất lỗi bit là:
⁄
. Ta có giới hạn xác xuất lỗi symbol là:
√
(
)
(1.14)
Trường hợp không mã :
.
(1.15)
√
So sánh hai trường hợp giải mã cứng và không mã, bỏ qua các hệ
số, độ lợi đạt được của mã cứng là
Độ lợi mã hóa tiệm cận
(1.16)
Hay độ lợi của giải mã mềm so với giải mã cứng là:
Độ lợi mã hóa tiệm cận
(1.17)
Công thức 1.17 chứng minh giải mã mềm tốt hơn giải mã cứng.
1.3 Các thuật toán giải mã mềm mã khối
1.3.1 Thuật toán lan truyền niềm tin
Đầu vào bộ giải mã BPA là tỷ lệ ước lượng theo hàm log:
′
′
1.18
( )
′
Thuật toán BPA là thuật toán giải mã lặp có hai bước chính:
Bước 1: Cập nhật bản tin cho tất cả các nút kiểm tra
và gửi bản tin ( ) từ nút kiểm tra tới các nút bit nối với nó.
Bước 2: Cập nhật bản tin cho tất cả các nút bit
và
gửi bản tin ( ) từ các nút bit tới nút các kiểm tra nối với nó.
Đầu ra của bộ giải mã là giá trị LLR của các bit mã được sử dụng
để quyết định thành từ mã thăm dò ̅. Nếu thỏa mãn điều kiện:
̅
[
]
(1.19)
thì dừng lặp và đưa ra từ mã hợp lệ ̅. Nếu không, thực hiện lại đến
khi đạt số lần lặp cực đại thì dừng và đưa ra từ mã tại lần lặp cuối.
1.3.2 Thuật toán tổng tích
Thuật toán tổng tích SPA có thể miêu tả qua 5 bước, thể hiện trên
lưu đồ thuật toán trình bày ở Hình 1.8.
7
Đọc vectơ nhận 𝑦𝑖 và
số vòng lặp cực đại 𝑛
Bắt đầu
Khởi tạo [𝑐𝑖
𝑦𝑖 ]
và [𝑐𝑖
𝑦𝑖 ]
Khởi tạo 𝑞𝑖𝑗
] và 𝑞𝑖𝑗
𝑖
Tính toán bản tin 𝑟𝑗𝑖 𝑏
và 𝑞𝑖𝑗 𝑏
𝑖
𝑖
𝑄𝑖
Tính toán 𝑄𝑖 𝑏
[𝑐𝑖
𝑏 𝑦𝑖 và các bản tin đã qua]
S
≥ 𝑄𝑖
𝑐̅𝑖
Đ
𝑐̅𝑖
Cho tất cả 𝑖
S
𝐜̅ 𝐇 𝑇
Đ
Kết thúc
Hình 1. 8. Lưu đồ thuật toán tổng tích SPA
1.3.3 Thuật toán tổng cực tiểu
Giai đoạn 1
𝑖
𝐿(𝑞𝑖𝑗 )
Đ
𝑖
>0
<
𝑞𝑖𝑗
𝑞𝑖𝑗
𝑙𝑜𝑔
𝑐̅𝑖
Đ
𝑖<𝑛
1
𝑖<𝑛
S
𝐿(𝑟𝑗𝑖 )
𝑐̅𝑖
𝐿 𝑄𝑖
S
𝛼𝑖 ′ 𝑗
𝛽𝑖 ′ 𝑗
𝑖′
S
𝐜̅ 𝐇
1
𝑇
Đ
𝐿(𝑞𝑖𝑗 )
𝐿 𝑐𝑖
𝐿(𝑟𝑗 ′ 𝑖 )
𝑗 ′ ∈𝐶𝑖~𝑗
𝐿 𝑄𝑖
𝐿 𝑐𝑖
Kết thúc
𝐿(𝑟𝑗 ′ 𝑖 )
𝑗∈𝐶𝑖
Hình 1. 9. Lưu đồ thuật toán MSA
Lưu đồ thuật toán MSA được trình bày trong Hình 1.9.
8
1.4 Đặt vấn đề nghiên cứu
Năm 1971, 1974: Phương pháp giải mã Viterbi có độ phức tạp
tăng theo cấp số nhân với kích thước mã.
Năm 1993, Giải mã Turbo (sử dụng MAP cho mã thành phần)
được giới thiệu và nghiên cứu triển khai cho mã tích. Số lượng phép
tính gấp 4 lần VA.
Năm 1996, Hagenauer đề xuất Thuật toán VA đầu ra mềm
(SOVA), gần giống MAP trên mã đối ngẫu giải mã cho mã tích. Chất
lượng giải mã cao, độ phức tạp quá lớn.
Năm 1998, Pyndiah cải tiến MAP cho các mã thành phần. Chất
lượng xấp xỉ giải mã Turbo và giải mã Map cho mã tích. Tuy nhiên,
chưa chứng minh được bằng cơ sở lý thuyết, rất khó phân tích nên
việc cải thiện hay áp dụng cho các mã khác không khả thi
Năm 2003, Al- Askary đưa ra thuật toán lặp cận tối ưu mới cho
mã tích nhằm tránh giải mã MAP của mã thành phần. Độ phức tạp
còn cao, sự bế tắc là chưa có bộ giải mã thành phần hiệu quả.
Như vậy, vấn đề quan trọng nhất là tìm một thuật toán cho mã
tích với độ phức tạp thấp, có cơ sở lý thuyết đầy đủ và đảm bảo ưu
điểm kiểm soát lỗi tốt của mã tích vẫn chưa được giải quyết.
Từ những phân tích này, Luận án cần giải quyết một số vấn đề:
Thứ nhất: Đưa ra thuật toán giải mã sử dụng nhiều từ mã đối
ngẫu hình thành nên các ma trận kiểm tra khác nhau nhằm cải thiện
thông tin ngoại lai qua mỗi vòng lặp. Ngoài ra, có thể đề xuất thuật
toán tận dụng từ mã đối ngẫu toàn “0” để giải mã với mục đích giảm
số vòng kín ngắn trên đồ hình Tanner.
Thứ hai: Quét toàn bộ thông tin trong bộ mã đối ngẫu tương ứng
nhằm đạt được lượng tin quyết định từ mã đầu ra là lớn nhất.
Thứ ba: Mã tích có hiệu quả kiểm soát lỗi cao nhưng vẫn còn
bất cập về độ phức tạp hay chưa có bộ giải mã các mã thành phần
phù hợp. Như vậy, ý tưởng quan trọng là kết hợp ưu điểm về khả
năng kiểm soát lỗi cao của mã tích và tận dụng tính chất mang tin
giải mã của mã đối ngẫu của các mã thành phần để giải mã mã tích.
9
Chương 2. GIẢI MÃ MỀM MÃ KHỐI SỬ DỤNG MÃ ĐỐI NGẪU
Kết quả nghiên cứu được công bố ở công trình số 1, 2, 3 và 4.
2.1 Mã đối ngẫu
2.1.1 Giới thiệu mã đối ngẫu
a) Định nghĩa:
Cho một mã tuyến tính
thuộc trường Galoa
, khi
đó mã đối ngẫu ′
gồm tất cả các vectơ ′ có:
{ }},
(2.1)
{ ′∈
|
b) Phân bố trọng số
Phân bố trọng số của mã có vai trò quan trọng trong việc tính toán
xác suất lỗi.
,
lần lượt là hàm phân bố trọng số của , ′
và có mối quan hệ dựa vào định lý MacWilliams.
2.1.2 Vai trò mã đối ngẫu trong việc mang tin giải mã
Đối với mã khối tuyến tính, mỗi bit mã trong các từ mã đối ngẫu
đều chứa các thông tin về các bit mã trong các từ mã gốc. Đồng thời,
từ mã đối ngẫu toàn “0” cũng mang thông tin từ mã gốc.
2.2 Đề xuất các thuật toán giải mã mềm cho mã khối áp dụng
tính chất mang tin của mã đối ngẫu
2.2.1 Thuật toán giải mã mềm mã Hamming dựa trên mã đối ngẫu
BPA– DCS (Belief Propagation Algorithm based on Dual Codes)
sẽ sử dụng tại mỗi vòng lặp một ma trận kiểm tra khác nhau để thông
tin ngoại lai ở vòng lặp trước đưa tới vòng lặp sau trong quá trình giải
mã luôn được cải thiện, giúp khắc phục vấn đề “vòng kín ngắn”.
a) uan h gi a ma t n i m t a v đ h nh anne
0 0 0 1 1 1 1
𝑐
𝑐3
𝑐2
𝑐4
𝑐5
𝑐6
[ 0 1 1 0 0 1 1]
𝑐7
𝑛
1 0 1 0 1 0 1
𝑓
Hình 2. 1. Ma trận kiểm tra
𝑓2
𝑓3
và đồ thị Tanner tương ứng của mã Hamming 7,4
7
10
b)
d ng c c ma t n i m t a tư ng đư ng
Ma trận kiểm tra tương đương
được xây dựng từ mã đối ngẫu.
c)
d ng thu t toán giải mã mềm d a trên các ma tr n ki m tra
tư ng đư ng
Khởi tạo: Tính LLR
cho các nút bit
, đặt:
2.12
( )
Giai đoạn 1:
Thực hiện giải mã như trong vòng lặp thứ 1 của thuật toán
BPA, nếu không thỏa mãn (1.19), chuyển sang giai đoạn 2.
Giai đoạn 2: Thay thế các hàng của ma trận kiểm tra bằng cách lấy
hàng đó cộng với hàng tiếp theo được
và thực hiện lại giai đoạn 1
với lần lặp
sử dụng ,... tiếp tục thực hiện đến khi tìm được từ
mã hợp lệ hoặc hết
. Luôn kiểm tra điều kiện (1.19)
Thuật toán BPA– DCS có chất lượng cải thiện so với BPA, tuy
nhiên thời gian cũng như số lượng phép tính lại tăng.
2.2.2 Thuật toán giải mã Hamming sử dụng từ mã đối ngẫu toàn “0”
Mã Hamming là mã khối mật độ cao nên khi áp dụng thuật toán
BPA sẽ không nâng cao được chất lượng giải mã thậm chí còn kém
hơn thuật toán giải mã cứng khi chiều dài từ mã tăng.
a) Đ nh gi hi u quả thu t to n BPA giải mã mã Hamming
Xét mã Hamming 7 và
, điều chế BPSK lý tưởng,
kênh tạp trắng cộng tính.
BER tai cac vong lap cua thuat toan BPA
BER tai cac vong lap cua thuat toan BPA
-4
10
BER Hamming (7,4) tren kenh Gauss
-4.3
10
BER Hamming (31,26) tren kenh Gauss
-4.4
10
-4.5
BER
BER
10
-5
10
-4.6
10
-4.7
10
-4.8
10
-6
0
5
10
15
20
So vong lap
25
30
35
Hình 2. 2. Chất lượng giải mã BPA mã
Hamming (7,4)
40
10
0
5
10
15
20
So vong lap
25
30
35
Hình 2. 3. Chất lượng giải mã BPA mã
Hamming (31,26)
40
11
Kết quả Hình 2.2, Hình 2.3 cho nhận xét: từ lần lặp thứ 5 trở đi
chất lượng giải mã cải thiện không đáng kể thậm chí còn kém hơn.
b) Thu t toán giải mã mềm t ên c sở sử dụng từ mã đối ngẫu to n “0”
Các bit kiểm tra có độ tin cậy thấp dễ dẫn đến cho thông tin giải
mã kém tin cậy ví dụ ở Bảng 2.1).
Bảng 2. 1. Khảo sát một số trường hợp giải mã sai khi truyền tin áp dụng thuật toán BPA cho
mã Hamming 7,4 với ma trận kiểm tra trong Hình 2.1.
Từ mã truyền
2 3 4 5 6 7
Giải mã ̅ 2̅ 3̅ 4̅ 5̅ 6̅ 7̅
tương ứng của
1000110
1010101
1,6135
0,4291
0,2058
0100011
0000000
0,7926
0,1699
1,2368
1110010
0110011
0,5954
1,3045
0,5954
0010111
0000000
1,9698
1,2849
0,9531
0000000
0011001
0,9755
0,1815
0,2757
1000110
1001100
3,1042
0,3243
1,4366
0100011
1000011
1,4595
0,1384
1,2582
0011010
0000000
0,7883
1,1208
0,4190
0111001
0101010
0,4912
0,4786
0,0539
2
3
Như vậy, chỉ nhận thông tin từ các bit kiểm tra có độ tin cậy cao.
Thuật toán BPA– DCZ (BPA– using Dual Code’ codeword of Zeros
được thực hiện như sau:
Bước 1: Thực hiện giải mã theo thuật toán BPA dùng ma trận
kiểm tra với số lần lặp
. Tại mỗi vòng lặp đều kiểm tra
điều kiện 1.19 , nếu thỏa mãn thì đưa ra từ mã tương ứng, nếu
không sẽ tiếp tục giải mã đến vòng lặp tối đa và chuyển sang bước 2.
Bước 2: Xác định nút kiểm tra có giá trị
nhỏ nhất và thực
hiện thay thế hàng trong ma trận ứng với vị trí bit kiểm tra có độ
tin cậy thấp nhất đó bằng từ mã đối ngẫu toàn “0”.
Bước 3: Giải mã lại theo BPA với mới được xây dựng ở bước
2,... tiếp tục thực hiện đến khi tìm được từ mã hợp lệ hoặc hết
.
2.2.3 Kết quả mô phỏng và thảo luận về chất lượng các thuật
toán giải mã mềm BPA– DCS và BPA– DCZ
- BPA– DCS: Thực hiện mô phỏng đánh giá chất lượng giải mã của
BPA– DCS, với thuật toán giải mã cứng, BPA, cho kết quả trên Hình
2.5, Hình 2.6, Hình 2.7 và Hình 2.8. BPA– DCS ứng dụng cho các mã
12
4
Hamming có > 7 tại
cho phép nâng cao chất lượng
khoảng 0,75 dB đến 1,05 dB so với thuật toán giải mã cứng; 0,3 dB
đến 0,45 dB so với BPA khi thực hiện cùng số vòng lặp.
BER Hamming (7,4) tren kenh Gauss
0
BER Hamming (15,11) tren kenh Gauss
0
10
10
giai ma cung
BPA
BPA-DCS
-1
10
giai ma cung
BPA
BPA-DCS
-1
10
-2
10
-2
BER
BER
10
-3
10
-3
10
-4
10
-4
10
-5
10
-5
10
-6
0
1
2
3
4
EbN0[dB]
𝐸𝑏 𝑁
5
6
7
10
8
0
1
2
3
4
EbN0[dB]
𝐸𝑏 𝑁
(dB)
Hình 2. 5. So sánh chất lượng của mã
Hamming 7,4 giữa các thuật toán.
5
6
7
8
(dB)
Hình 2. 6. So sánh chất lượng của mã
Hamming 15,11 giữa các thuật toán.
Thuật toán BPA– DCS cần thêm
phép cộng modulo 2 trong
mỗi vòng lặp và độ phức tạp tăng tối đa so với BPA là
,
nên thời gian giải mã lâu hơn Bảng 2.2 .
BER Hamming (31,26) tren kenh Gauss
0
10
giai ma cung
BPA
BPA-DCS
-1
10
-2
-2
10
-3
-3
10
10
BER
BER
giai ma cung
BPA
BPA-DCS
-1
10
10
-4
10
-4
10
-5
-5
10
10
-6
-6
10
10
-7
10
BER Hamming (63, 57) tren kenh Gauss
0
10
-7
0
1
2
3
4
5
EbN0[dB]
𝐸𝑏 𝑁 (dB)
6
7
8
10
0
1
2
3
4
EbN0[dB]
𝐸𝑏 𝑁
5
6
7
8
(dB)
Hình 2. 7. So sánh chất lượng của mã
Hình 2. 8. So sánh chất lượng của mã
Hamming 31,26 giữa các thuật toán.
Hamming 63,57 giữa các thuật toán.
Bảng 2. 2. So sánh thời gian trung bình xử lý một từ mã giữa BPA và BPA– DCS với các bộ mã
Hamming (7,4); (15,11); (31,26) và (63,57).
Tỷ lệ thời gian của thuật toán
Bộ mã
BPA
BPA– DCS
BPA– DCS so với BPA
C (7,4)
0,4453 ms
1,1297 ms
253,69 %
C (15,11)
C (31,26)
C(63,57)
0,8540 ms
2,8901 ms
15,4322 ms
2,0961 ms
6,8318 ms
33,101 ms
245,445 %
236,386 %
214,493 %
13
- BPA– DCZ: Mô phỏng đánh giá chất lượng của BPA– DCZ với
các thuật toán giải mã cứng, BPA, BPA tối ưu với cùng thông tin đầu
vào, cho kết quả trên Hình 2.9, Hình 2.10, Hình 2.11 và Hình 2.12 [32].
BER Hamming(7,4) tren kenh Gauss
0
10
giai ma cung
BPA
BPA-toiuu
BPA-DCZ
-1
10
-2
-2
10
BER
BER
giai ma cung
BPA
BPA-toiuu
BPA-DCZ
-1
10
10
-3
10
-4
-3
10
-4
10
10
-5
-5
10
10
-6
10
BER Hamming(15,11) tren kenh Gauss
0
10
-6
0
1
2
3
4
5
EbN0[dB]
𝐸𝑏 𝑁 (dB)
6
7
10
8
Hình 2. 9. So sánh BER của mã Hamming
7,4 giữa các thuật toán
0
1
2
3
4
5
EbN0[dB]
𝐸𝑏 𝑁 (dB)
6
7
8
Hình 2. 10. So sánh BER của mã Hamming
(15,11) giữa các thuật toán
Với các mã Hamming (15,11); (31,26) và (63,57), BPA– DCZ
4
cho độ lợi tương ứng 0,3 dB; 0,45 dB; 0,65 dB tại
so
với BPA. Nghĩa là từ mã càng dài, thuật toán mới càng cải thiện chất
lượng nhiều hơn so với BPA.
BER Hamming (31,26) tren kenh Gauss
0
giai ma cung
BPA
BPA-toi uu
BPA-DCZ
-1
10
-2
-2
10
BER
BER
giai ma cung
BPA
BPA-toiuu
BPA-DCZ
-1
10
10
-3
10
-3
10
-4
-4
10
10
-5
-5
10
10
-6
-6
10
BER Hamming(63, 57) tren kenh Gauss
0
10
10
10
0
1
2
3
4
EbN0[dB]
5
6
7
8
𝐸𝑏 𝑁 (dB)
Hình 2. 11. So sánh BER của mã Hamming
31,26 giữa các thuật toán
0
1
2
3
4
5
EbN0[dB]
𝐸𝑏 𝑁 (dB)
6
7
8
Hình 2. 12. So sánh BER của mã Hamming
63,57 giữa các thuật toán
Sử dụng BPA– DCZ, cần thêm bộ so sánh để xác định bít kiểm
tra có giá trị
nhỏ nhất nên hệ thống phức tạp hơn và thời gian
giải mã lâu hơn so với sử dụng BPA. BPA– DCZ giảm được số
2
lượng phép tính tối đa so với BPA là
. Nên, thời gian
giải mã trung bình cho một từ mã giữa BPA và BPA– DCZ có thể
coi là tương đương, thể hiện trên Bảng 2.3.
14
Bảng 2. 3. So sánh thời gian trung bình xử lý một từ mã giữa BPA và BPA–DCZ với các mã
Hamming (7,4); (15,11); (31,26) và (63,57).
Bộ mã
BPA
BPA – DCZ
C (7,4)
0,4743 ms
0,589 ms
C(15,11)
1,006 ms
1,142 ms
C(31,26)
3,625 ms
3,664 ms
C(63,57)
14,229 ms
14,528 ms
BPA– DCS và BPA– DCZ đều có thiết kế hệ thống phức tạp
hơn, chất lượng giải mã tốt hơn. BPA– DCZ được lợi về mặt thời
gian so với BPA– DCS hơn do giảm được số lượng phép tính.
2.3 Giải mã mềm sử dụng mã đối ngẫu
2.3.1 Đề xuất thuật toán giải mã cho các mã khối mật độ cao sử
dụng mã đối ngẫu
Bắt đầu
𝐿 𝑐𝑖
𝑙𝑛
𝐲 𝑐𝑖
𝐲 𝑐𝑖
𝐾
𝑝ℓ tanh(𝐿 𝑐 ′ℓ ⁄ )
với ℓ
𝑛
𝑖
2𝑟
𝑛
𝑗=
ℓ=
𝑐 𝑗ℓ⨁𝛿𝑖ℓ
𝑡𝑎𝑛ℎ(𝐿 𝑐 ′ℓ ⁄ )
𝑃𝑖
>
S
𝑐̅𝑖
𝐾
𝑖
𝐾
𝑖
𝑖
Đ
𝑛
S
𝐜̅
Đ
𝐾
S
𝐾𝑚𝑎𝑥
S
𝐬
𝑐̅𝑖 𝑖
𝐜̅ 𝐇 𝑇
𝑛
[ ]
Đ
Kết thúc
Hình 2. 13. Lưu đồ thuật toán DCA
Đ
𝑐̅𝑖
15
Sau khi nhận được tin đầu vào mềm
của các bit tin từ bộ
giải điều chế, bộ giải mã thực hiện quá trình giải mã gồm các 2 bước:
Bước 1: Tại vòng lặp thứ nhất bộ giải mã tính giá trị ℓ :
Bước 2: Xác định từ mã đầu ra ̅
Lưu đồ thuật toán DCA được thể hiện trong Hình 2.13.
2.3.2 Đánh giá chất lượng thuât toán giải mã dựa trên mã đối ngẫu
Trên cơ sở BPA, sử dụng không gian kiểm soát lỗi là ′
(ký
hiệu là BPDCA) cho kết quả trên Hình 2.14. Từ mã càng dài, chất
lượng càng kém do số lượng vòng kín ngắn càng lớn (Bảng 2.4).
Bảng 2. 4. Số lượng các vòng kín ngắn trong ma
trận , ′
BER Hamming tren kenh Gauss
0
10
-1
10
-2
Mã
10
Vòng kín 4
BER
HDD (7,4)
HDD (15,11)
HDD (31,26)
BPA (7,4)
BPA (15,11)
BPA (31,26)
BPDCA (7,4)
BPDCA (15,11)
BPDCA (31,26)
-4
10
-5
10
-6
10
-7
10
0
1
2
3
4
5
EbNo[dB]
𝐸𝑏 𝑁 (dB)
6
7
Vòng kín 6
(7,4)
(15,11)
3
36
′
21
630
4
224
′
252
31220
(31,26)
280
13020
5600
2744120
-3
10
8
Hình 2. 14. BER của BPDCA, BPA
và HDD cho các mã Hamming
BER Hamming tren kenh Gauss
0
10
-1
10
-2
(23,12)
mo rong (24,12)
(23,12)
mo rong (24,12)
-2
10
10
-3
-3
10
10
BER
BER
HDD Golay
HDD Golay
DCA Golay
DCA Golay
-1
10
-4
10
-4
10
HDD (7,4)
HDD (15,11)
HDD (31,26)
DCA (7,4)
DCA (15,11)
DCA (31,26)
-5
10
-6
10
-7
10
BER Golay tren kenh Gauss
0
10
0
1
2
-5
10
-6
10
-7
3
4
5
EbNo[dB]
𝐸𝑏 𝑁 (dB)
6
7
Hình 2. 15. Chất lượng giải mã theo
thuật toán DCA, HDD cho các mã
Hamming.
8
10
0
1
2
3
4
5
𝐸EbNo[dB]
𝑏 𝑁 (dB)
6
7
8
Hình 2. 16. Chất lượng giải mã theo thuật toán
DCA, HDD cho mã Golay và Golay mở rộng
4
Chất lượng của DCA tại
, cho độ lợi 1,57 dB; 1,4 dB
và 1,39 dB so với HDD khi áp dụng cho các mã Hamming có chiều
dài từ mã tương ứng 7; 15 và 31. Đối với mã Golay và Golay mở
rộng, độ lợi đạt tới 1,85 dB so với HDD.
16
Như vậy, với các mã tốc độ càng thấp, cho độ lợi giải mã DCA so
với giải mã cứng càng cao. Nhưng phải trả giá về kích thước không
gian kiểm soát lỗi lớn, tỉ lệ với
Bảng 2.5
Bảng 2. 5. So sánh kích thước ma trận kiểm tra và độ lợi mã hóa khi sử dụng thuật toán HDD
và DCA.
Bộ mã
H (7,4)
H (15,11)
H (31,26)
G (23, 12)
G (24, 12)
Kích thước ma trận
kiểm tra của HDD
7
Kích thước không gian
kiểm tra của DCA
3
7
4
5
2
Độ lợi mã hóa DCA
so với HDD
1,57 dB
1,4 dB
1,39 dB
1,85 dB
1,85 dB
DCA phù hợp với các mã tốc độ cao, hay các mã có độ dư nhỏ.
2.4 Kết luận chương
Chương 2 đã đề xuất một số thuật toán cải tiến cho thuật toán
BPA trên cơ sở tính chất mang tin của mã đối ngẫu cho các mã mật
độ cao HDPC là thuật toán BPA– DCS và BPA– DCZ. Ngoài ra, nội
dung chương này còn đề cập đến việc nâng cao chất lượng giải mã
HDPC như mã Hamming, Golay,... bằng cách quét toàn bộ thông tin
giải mã trong bộ mã đối ngẫu tương ứng để đạt được lượng tin quyết
định từ mã đầu ra là lớn nhất, đề xuất thuật toán giải mã đối ngẫu
DCA. Khi đó, không gian các từ mã đối ngẫu tăng tỷ lệ với . Từ
hai hướng nghiên cứu này, có thể nhận xét sơ bộ là: chất lượng giải
mã hướng thứ nhất chưa thực sự khả quan, còn hướng nghiên cứu
thứ hai DCA là thuật toán giải mã cho chất lượng giải mã tốt có số
lượng phép tính tỉ lệ với 2
. Vì vậy DCA rất phù hợp với các
mã khối có độ dư nhỏ.
Chương 3. GIẢI MÃ MỀM MÃ TÍCH
Nội dung chương 3 được công bố ở công trình số 2, 3 và 5.
3.1 Mã tích và các đặc điểm
3.1.1 Các tham số cơ bản của mã tích
Cấu trúc mã tích
2 minh họa trong Hình 3.1.
17
𝑛
𝑘
𝑟 𝑘2 bit kiểm tra
chẵn lẻ mã hàng
𝑘2
𝑛2
𝑟 𝑟2 bit kiểm tra chẵn lẻ
mã hóa các bit kiểm tra
chẵn lẻ
𝑟2 𝑘 bit kiểm tra
chẵn lẻ mã cột
Hình 3. 1. Cấu trúc mã tích
3.1.2 Giải mã mã tích
Giải mã Viterbi trên lưới mã tích rất phức tạp.
Giải mã Turbo cho mã tích trên cơ sở giải mã các hàng và các cột
thành phần bằng thuật toán MAP (Hình 3.3).
Bộ giải mã MAP trả về giá trị thực cho mỗi symbol ̅ với:
̅
∑∈
∏ℓ
ℓ
∑∈
∏ℓ
ℓ
( ℓ
ℓ) ℓ
( ℓ
ℓ) ℓ
(3.8)
Phản hồi bước lặp tiếp theo
𝐿 𝐜
𝐿𝑐 𝐲
𝐿𝑒 𝐜̅
Giải mã
hàng 𝐂
𝐿𝑒 𝐜̅
Giải mã
cột 𝐂
𝐿 𝐜̅
𝐿 𝐜̅
Tại lần
lặp cuối
𝐿 𝐜̅
Hình 3. 3. Mô hình giải mã mã tích
Giá trị mềm cho mỗi symbol bởi giải mã MAP trên mã đối ngẫu
được đưa ra như sau:
̅
∑
∑
∏ℓ
(
′
( ℓ
ℓ
) ∏ℓ
ℓ
′
ℓ)
( ℓ
Bảng 3. 1. Độ phức tạp của các phương pháp giải mã tích
Phương pháp giải mã
Độ phức tạp (phép tính)
Turbo
2
(MAP)
′
2
Viterbi
ℓ)
ℓ
′
ℓ
/Đơn vị
Lần lặp
Lần lặp
Mỗi giai đoạn
18
Sự phức tạp của giải mã Viterbi và giải mã Turbo chỉ ra trong
Bảng 3.1. Các thuật toán này đều giải mã trên lưới mã nên độ
phức tạp còn phụ thuộc vào số đỉnh và số nhánh trong lưới.
Thuật toán giải mã lặp cận tối ưu có độ phức tạp điều chỉnh được,
có thể coi là một giải pháp để giải mã tích. Tuy nhiên, nhược điểm là
chưa có bộ giải mã thành phần hiệu quả khiến việc sử dụng mã tích
trong thực tế của thuật toán này bị hạn chế.
3.2 Đề xuất thuật toán giải mã đối ngẫu mã tích
3.2.1 Xây dựng cơ sở lý thuyết cho thuật toán giải mã tích mới
Cho là mã đối ngẫu của . Ký hiệu
∈ { } là xác
suất có điều kiện rằng thu được
khi bit mã
được gửi đi.
Ký hiệu
là tỷ lệ hợp lẽ (Likelihood Ratio)
2
của bit thứ m. Dễ dàng tính được
. Để ứng
dụng phương pháp giải mã đối ngẫu mã tích, cần biến đổi để đầu ra
của tính toán trong bước giải mã hàng (cột) có thể làm đầu vào cho
bước giải mã cột (hàng) sau. Như vậy, ý tưởng quan trọng của Luận
án là đưa ra công thức tính lượng tin đầu vào vòng lặp tiếp theo:
2
3.15
2
với
2
2
=
(
ℓ
(
ℓ
ℓ=
ℓ
)
2
=
ℓ=
ℓ
)
′
ℓ
′
ℓ
3.16
ℓ
3.17
Công thức 3.15 chính là cơ sở lý thuyết cho đề xuất thuật toán
giải mã tích mới.
3.2.2 Thuật toán giải mã mềm mã tích sử dụng mã đối ngẫu
Thuật toán mới cho mã tích được xây dựng trên cơ sở thuật toán
DCA ký hiệu là DCAPC (Dual Codes decoding Algorithm for
Product Codes) (Hình 3.5). Giải mã mỗi hàng hay mỗi cột theo lưu
đồ thuật toán Hình 3.6. DCAPC gồm các bước chính:
- Xem thêm -