Tài liệu Giải mã mềm mã hamming dựa trên các mã đối ngẫu - Nguyễn Thị Hồng Nhung: Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 27
GIẢI MÃ MỀM MÃ HAMMING DỰA TRÊN CÁC MÃ ĐỐI NGẪU
Nguyễn Thị Hồng Nhung1*, Phạm Xuân Nghĩa2, Vũ Thị Thắng3, Lê Tiến Cường4
Tóm tắt: Trong bài báo này, chúng tôi đề xuất thuật toán giải mã BPA (Belief
Propagation Algorithm) cải tiến dựa trên tính chất đối ngẫu của mã khối tuyến tính.
Thuật toán mới đề xuất thực hiện giải mã mềm với các ma trận kiểm tra tương
đương ứng dụng cho mã Hamming, trong đó, các ma trận kiểm tra tương đương
được xây dựng trên cơ sở sử dụng các từ mã đối ngẫu. Kết quả khảo sát cho thấy độ
lợi của thuật toán giải mới tốt hơn từ 0.45 dB đến 0.5 dB so với thuật toán BPA
truyền thống mà thời gian và độ phức tạp giải mã tăng không đáng kể.
Từ khóa: Mã kênh, Giải mã mềm, Mã Hamming.
1. ĐẶT VẤN ĐỀ
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à loại mã có khả năng sửa và phát hi...
9 trang |
Chia sẻ: quangot475 | Lượt xem: 677 | Lượt tải: 0
Bạn đang xem nội dung tài liệu Giải mã mềm mã hamming dựa trên các mã đối ngẫu - Nguyễn Thị Hồng Nhung, để tải tài liệu về máy bạn click vào nút DOWNLOAD ở trên
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 27
GIẢI MÃ MỀM MÃ HAMMING DỰA TRÊN CÁC MÃ ĐỐI NGẪU
Nguyễn Thị Hồng Nhung1*, Phạm Xuân Nghĩa2, Vũ Thị Thắng3, Lê Tiến Cường4
Tóm tắt: Trong bài báo này, chúng tôi đề xuất thuật toán giải mã BPA (Belief
Propagation Algorithm) cải tiến dựa trên tính chất đối ngẫu của mã khối tuyến tính.
Thuật toán mới đề xuất thực hiện giải mã mềm với các ma trận kiểm tra tương
đương ứng dụng cho mã Hamming, trong đó, các ma trận kiểm tra tương đương
được xây dựng trên cơ sở sử dụng các từ mã đối ngẫu. Kết quả khảo sát cho thấy độ
lợi của thuật toán giải mới tốt hơn từ 0.45 dB đến 0.5 dB so với thuật toán BPA
truyền thống mà thời gian và độ phức tạp giải mã tăng không đáng kể.
Từ khóa: Mã kênh, Giải mã mềm, Mã Hamming.
1. ĐẶT VẤN ĐỀ
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à loại 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. Tuy nhiên, phần lớn các họ mã khối
trước đây còn tồn tại những mặt hạn chế đáng kể như đánh đổi chất lượng giải mã
để giảm lượng tính toán và tăng tỷ lệ mã hóa hoặc để đạt chất lượng mong muốn
lại phải tăng độ phức tạp tính toán cũng như giảm tỷ lệ mã hóa.
Mã Hamming do Richard Hamming lần đầu tiên giới thiệu tại [1] là một loại mã
thuộc họ mã khối có thể sửa được 1 lỗi đơn hoặc phát hiện được các lỗi kép (bội
2). Với tính chất đơn giản của thuật toán mã hóa và giải mã, mã Hamming đã được
ứng dụng khá rộng rãi trong các hệ thống truyền tin số với vai trò là mã phát hiện
lỗi. Với mục đích sử dụng mã Hamming vừa có khả năng sửa lỗi, vừa có khả năng
phát hiện lỗi, trong bài báo đề xuất thuật toán giải mã mềm cải tiến ứng dụng cho
loại mã này.
Từ việc nghiên cứu thuật toán giải mã BPA [4] và tính chất đối ngẫu của mã sửa
sai [2], [3], chúng tôi đưa ra ý tưởng xây dựng thuật toán giải mã mới cho mã khối
tuyến tính trong đó có mã Hamming. Phần còn lại của bài báo được trình bày như
sau: Mục 2 trình bày các cơ sở lý luận để xây dựng thuật toán giải mã mới, mục 3
của bài báo trình bày các bước của việc xây dựng thuật toán giải mã mới, mục 4 thực
hiện khảo sát đánh giá chất lượng của thuật toán giải mã mới thông qua các kết quả
mô phỏng trên kênh AWGN với các mã Hamming, cuối cùng là phần kết luận.
2. CƠ SỞ LÝ LUẬN XÂY DỰNG THUẬT TOÁN GIẢI MÃ MỀM
CẢI TIẾN CHO CÁC MÃ HAMMING
2.1. Phương pháp giải mã khối dựa trên các mã đối ngẫu
Như ta đã biết, tính chất của ma trận kiểm tra G và ma trận sinh H của mã
khối tuyến tính thể hiện như sau:
T. 0.GH (1)
Bên cạnh đó, tính chất đối ngẫu của mã khối tuyến tính được hiểu như sau: ma
trận kiểm tra của mã gốc đóng vai trò là ma trận sinh của mã khối tuyến tính khác.
Từ các tính chất nêu trên cho thấy có thể xây dựng các ma trận kiểm tra của một
mã khối tuyến tính dựa trên các từ mã trong bộ mã đối ngẫu. Trên cơ sở này hình
thành nên phương pháp giải mã khối sử dụng mã đối ngẫu trình bày trong [2] và
Kỹ thuật điều khiển & Điện tử
N. T. H. Nhung, P. X. Nghĩa, , “Giải mã mềm mã Hamming dựa trên các mã đối ngẫu.” 28
[3]. Phương pháp giải mã này được mô tả như sau: khi truyền từ mã bất kỳ
1 2
( , ,...., )
n
c c cc của mã tuyến tính ( , )n kC qua kênh, dưới tác động của nhiễu và
tạp âm ta nhận được từ mã
1 2
ˆ ˆ ˆ ˆ( ' , ' ,...., ' )
n
c c cc' , quá trình giải mã ở phía thu với
từ mã đầu vào mềm cˆ' , sử dụng các từ mã đối ngẫu của mã đối ngẫu '( , )n rC ta
tính ra các bit nhận c
( 1 n ) với xác suất cao nhất (trong đó, n là chiều dài
từ mã, k là chiều dài từ tin, 2 1 rr n k k là số lượng các bít kiểm tra).
Ký hiệu exp[2 / ]p là biểu diễn phức của nghiệm nguyên thủy p ; 1
i
nếu i và 0
i
với các trường hợp khác; là đơn vị ảo; Pr( )x là xác suất
của x và Pr( | )x y là xác suất có điều kiện của x cho bởi ;y '''t ic là bít thứ i của
từ mã thứ ''t trong mã đối ngẫu; , 't t là số phần tử trong trường ( )GF p và có giá
trị là các số nguyên 0,1,..., 1.p Nếu s thuộc trường ( )GF p ta có c s khi
( )A s
đạt cực đại với:
''
1 1
'( ' )
0 '' 1 ' 01
ˆ( ) Pr( ' | ') .
r
t i i
p p pn
t c tst
i
t t ti
A s c t
(2)
Kết quả chứng minh trong [2] khẳng định đối với mã nhị phân ( 2p ), điều
kiện quyết định cứng (ở lần lặp cuối cùng), bít 0c
khi:
'''2
'' 1 1
1
0
1
r t i icn
i
t i i
(3)
và 1c
nếu (3) xảy ra theo chiều ngược lại, ở đây:
ˆPr( ' |1)
ˆPr( ' | 0)
i
i
i
c
c
; là phép
cộng modulo 2.
Để làm rõ tính chất trên ta xét mã Hamming (7,4) với mã nhận được ký hiệu là
1 2 7
ˆ ˆ ˆ ˆ( ' , ' ,...., ' )c c cc' , theo (3) điều kiện quyết định bit mã
1
c là:
'
'' 178
1
'' 1 1
1
0 0.
1
t i ic
i
t i i
c khi
(4)
Ta có ma trận kiểm tra H của mã Hamming (7, 4) cũng là ma trận sinh của mã
đối ngẫu:
1 1 1 0 1 0 0 ( )
0 1 1 1 0 1 0 ( )
0 0 1 1 1 0 1 ( )
a
b
c
H
= .
Như vậy, các từ mã của bộ mã đối ngẫu 'C (ở đây ký hiệu a, b, c là các từ mã
đối ngẫu) là:
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 29
1 2 3 4 5 6 7
'
c c c c c c c
0 0 0 0 0 0 0
1 1 1 0 1 0 0 (a)
0 1 1 1 0 1 0 (b)
: 1 0 0 1 1 1 0 (a b)
0 0 1 1 1 0 1 (c)
1 1 0 1 0 0 1 (a c)
0 1 0 0 1 1 1 (b c)
C .
1 0 1 0 0 1 1 (a b c)
(5)
Đặt (1 ) / (1 )
i i i
điều kiện quyết định đối với bít
1
c là:
1 1 2 3 5 1 2 3 4 6 4 5 6 1 3 4 5 7
2 4 7 1 2 5 6 7 3 6 7
0
0;
c khi
(6)
1
1c khi (6) xảy ra theo chiều ngược lại.
Như vậy, đến đây ta có thể nhận xét rằng: Đối với mã khối tuyến tính, mỗi bít
mã trong các từ mã đối ngẫu đều chứa các thông tin về các bít mã trong các từ mã
gốc [2]. Bên cạnh đó, từ các từ mã đối ngẫu ta có thể thành lập các ma trận kiểm
tra khác nhau. Những nhận định trên đây là cơ sở để xây dựng thuật toán giải mã
mới được trình bày ở nội dung tiếp theo của bài báo.
2.2. Thuật toán giải mã BPA
2.2.1. Quan hệ giữa ma trận kiểm tra và đồ hình Tanner
0 0 0 1 1 1 1
= 0 1 1 0 0 1 1
1 0 1 0 1 0 1
H
Hình 1. Ma trận kiểm tra H và đồ thị Tanner tương ứng
của mã Hamming (7, 4).
Mã khối tuyến tính nói chung, mã Hamming nói riêng được giải mã nhờ việc sử
dụng ma trận kiểm tra H có kích thước r n . Hiện nay, một trong những cách
được coi là hiệu quả nhất biểu diễn mã khối chính là thông qua đồ hình song biên
(n =7)
6c 5c C
1
2c 3c
3f 2f 1f
4
c
7c1c
(r =3)
Kỹ thuật điều khiển & Điện tử
N. T. H. Nhung, P. X. Nghĩa, , “Giải mã mềm mã Hamming dựa trên các mã đối ngẫu.” 30
Tanner [5], đồ hình này có quan hệ chặt chẽ với ma trận kiểm tra của bộ mã, điều
này được minh chứng qua ví dụ thể hiện trên hình 1.
Trên đồ hình này có hai hàng nút gồm các nút mã 1 2, ,... nc c cc và các nút kiểm
tra 1 2, ,... rf f ff . Nút kiểm tra jf nối với nút ic khi và chỉ khi ( , ) 1H j i
( ( , )H j i là phần tử ở vị trí hàng ,j cột i của ma trận kiểm tra H ). Bộ giải mã sử
dụng thuật toán giải mã lặp như thuật toán lan truyền niềm tin BPA. Khi đó, thông
tin sẽ được truyền qua lại giữa các nút bít và các nút kiểm tra khi có kết nối trên đồ
thị Tanner. Nội dung tiếp theo của bài báo đi sâu phân tích bản chất của thuật toán
giải mã này.
2.2.2. Thuật toán giải mã BPA cho mã Hamming
Xét mã Hamming ( , )n k , đầu vào bộ giải mã BPA là tỷ lệ ước lượng theo hàm
log (Log Likelihood Ratio – LLR):
ˆˆPr( ' 0| )
( ) ( ) log
ˆˆPr( ' 1| )
ˆ ' .i
ij
i
i
c
L q L
c
c
c'
c'
(7)
Ở đây, cˆ' là tập các symbol nhận từ kênh. ˆˆPr( ' | )ic b c' là xác suất điều kiện
với 0,1;b Trước khi đi sâu vào phân tích các thuật toán chúng ta cùng định nghĩa
một số ký hiệu:
ic : bit thứ i của từ mã n bit.
jR : tập hợp các cột ở đó ( , ) 1H i j với j là thứ tự hàng.
iC : tập hợp các hàng ở đó ( , ) 1H j i với i là thứ tự cột.
~ j iR : tập jR trừ cột thứ i .
~ i jC : tập iC trừ hàng thứ j .
jip b : Pr [nút kiểm tra jf thỏa mãn | ˆ ' ( ) ~ .& ] i ij jb ic q b R
ˆ[ ': Pr ~| ) ( ].,iij ji i ic pq b b b j c C
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 1, 2, , j r và gửi bản
tin ( )jiL p 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 1, 2, , i n và gửi bản tin
( ) ijL q 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ò 1 2, ,..., nc c cc . Nếu syndrome s thỏa mãn điều kiện:
[0, 0, ..., 0]
T
s c.H (8)
thì dừng lặp và đưa ra từ mã hợp lệ c . Nếu điều kiện (8) không thỏa mãn thì quá
trình được thực hiện lại cho đến khi đạt số lần lặp cực đại axm thì dừng và đưa ra
từ mã tại lần lặp cuối.
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 31
Thuật toán BPA và các phiên bản cải tiến của thuật toán này được ứng dụng cho
mã mật độ kiểm tra thấp LDPC (là mã khối tuyến tính có ma trận H là một ma trận
thưa với số lượng các phần tử "1" trên mỗi hàng và mỗi cột rất ít) mang lại chất
lượng giải mã rất tốt. Với mục đích ứng dụng thuật toán giải mã BPA cho các mã
khối tuyến tính khác, trong đó có mã Hamming với ma trận kiểm tra H không đảm
bảo tính thưa, khi đó tồn tại nhiều chu kỳ ngắn trong nó, điều này làm ảnh hưởng
lớn tới chất lượng giải mã (các chu kỳ ngắn tạo ra những tập bẫy (trapping sets) là
nguyên nhân chính dẫn đến hiệu ứng sàn “error floor”), vì vậy, để ứng dụng thuật
toán BPA cho mã Hamming đòi hỏi phải có những cải tiến nhất định mới đạt được
mục đích đặt ra. Đây cũng là nội dung sẽ được trình bày trong nội dung tiếp theo
của bài báo.
3. ĐỀ XUẤT THUẬT TOÁN GIẢI MÃ BPA CẢI TIẾN
DỰA TRÊN MÃ ĐỐI NGẪU
Ở mục này trình bày thuật toán BPA cải tiến bằng việc sử dụng các ma trận
kiểm tra tương đương, các ma trận này được xây dựng trên cơ sở sử dụng các từ
mã đối ngẫu BPA – DCS (Belief Propagation Algorithm base on dual codes). Ở
đây, thay vì sử dụng một ma trận kiểm tra với số lần lặp tối đa max sau đó mới sử
dụng ma trận kiểm tra tương đương mới [6], thuật toán cải tiến sẽ sử dụng tại mỗi
vòng lặp một ma trận kiểm tra tương đương khác nhau để giải mã, bằng cách thực
hiện như trên sẽ làm cho 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, điều này đã khắc phục được vấn đề
“vòng kín ngắn” đã nêu ở trên.
3.1. Xây dựng các ma trận kiểm tra tương đương
Một cách tổng quát, với mã ( , )n k sẽ tồn tại 2
r
từ mã đối ngẫu, tương ứng
2r
rC
ma trận kiểm tra tương đương
e
H để sử dụng cho quá trình giải mã. Các ma trận
kiểm tra tương đương
e
H được xây dựng dựa trên các từ mã đối ngẫu. Ví dụ với
mã Hamming (7,4), các ma trận kiểm tra tương đương sẽ được xây dựng như sau:
a
b
c
H = → .e
a b
b c
a b c
H =
Với cách thực hiện như trên, ma trận kiểm tra tương đương He được hình thành
từ các từ mã đối ngẫu khác so với ma trận H, bằng cách đó ta có thể xây dựng số
lượng ma trận kiểm tra tương đương khá lớn (phụ thuộc vào số từ mã đối ngẫu 2r )
phục vụ cho mỗi vòng giải mã lặp.
3.2. Xây 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 iL(c ) cho tất cả các nút bit ,...,n,i 21 và đặt:
(1)
ij
ˆˆPr( ' 0| )
( ) ( ) log
ˆˆPr( ' 1| )
ˆ ' i
i
i
c
L q L
c
c
c'
c'
(9)
Kỹ thuật điều khiển & Điện tử
N. T. H. Nhung, P. X. Nghĩa, , “Giải mã mềm mã Hamming dựa trên các mã đối ngẫu.” 32
tại vị trí ( , )j i thỏa mãn 1jiH cho lần lặp thứ nhất.
Giai đoạn 1:
Bước 1: Đối với tất cả các nút kiểm tra ( 1,2,..., )j j mf , tính toán
( ) ) (γ jipL
ứng với các vị trí ( , )j i có 1jiH tại lần lặp thứ 1 theo phương trình sau:
) ) )
~~
,
jj
(γ (γ (γ
ji i'j i'j
i' ii' i
L (p ) sign L (q ) .φ φ L (q )
RR
(10)
với
1
1
log2tanhlog
x
x
e
e
)(x/φ(x) .
Sau đó gửi bản tin ( )jiL p từ nút kiểm tra tới các nút bit nối với nó.
Bước 2: Tính toán ijL(q ) đối với tất cả các nút tin ˆ ' ( 1, 2,..., )ic i n tại các vị trí
( , )j i có 1jiH theo phương trình sau:
)
~
ˆ ' .
i
(γ
ij i j'i
j' j
L(q ) L(c ) L (p )
C
(11)
Tiếp đó gửi bản tin ijL(q ) từ các nút bit tới nút các kiểm tra nối với nó. Đầu ra
bộ giải mã là giá trị LLR của các bit mã ( 1,2,..., )ic i n tại lần lặp thứ nhất:
) )ˆ ' .
i
(γ (γ
i i ji
j
L L(c ) L (p )
C
(12)
Khi đó từ mã thăm dò ( )c = ( ) ( ) ( )1 2( , ,..., )nc c c
tại lần lặp thứ nhất được quyết
định là:
)
( )
1,2,..., )
0 1
1 1
(γ
i
i n (γ
i
, sign(L )
c
, sign(L )
(13)
và kiểm tra điều kiện:
. [0,0,...,0],
T c H (14)
nếu thỏa mãn thì đưa ra từ mã c , nếu không thỏa mãn (14) thì chuyển sang giai
đoạn 2.
Giai đoạn 2: Ở giai đoạn 1, nếu (14) không thỏa mãn, thực hiện 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 ta nhận
được ma trận kiểm tra tương đương
e
H và thực hiện lại giai đoạn 1 với lần lặp
2 sử dụng ma trận kiểm tra tương đương
e
H . Nếu thấy (14) thỏa mãn thì dừng
và đưa ra từ mã. Nếu không, thực hiện lại giai đoạn 2, xây dựng ma trận kiểm tra
tương đương mới và tiếp tục giải mã ứng với
e
H mới đó, Tại mỗi lần lặp luôn
kiểm tra điều kiện (14), nếu thỏa mãn thì đưa ra từ mã, nếu không tiếp tục thực
hiện giải mã đến khi tìm được từ mã hợp lệ hoặc hết max lần lặp.
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 33
4. KẾT QUẢ MÔ PHỎNG VÀ THẢO LUẬN
4.1. Sơ đồ hệ thống
Để đánh giá chất lượng của thuật toán giải mã mới được xây dựng ta sử dụng sơ
đồ mô phỏng thể hiện trên hình 2.
Xét mô hình hệ thống sử dụng mã Hamming mô tả trên hình 2. Các bít tin
1 2, ,... ku u uu được mã hóa Hamming ( , )n k với tỷ lệ /R k n (trong đó, n là độ
dài từ mã, k là chiều dài thông tin) thành từ mã 1 2, ,... nc c cc , sau đó được điều
chế và truyền qua kênh. Tại đầu thu, khi nhận được từ mã ˆ 'c , tiến hành giải mã và
đưa ra từ mã c .
Hình 2. Mô hình hệ thống sử dụng mã Hamming.
4.2. Kết quả mô phỏng
Xét các mã Hamming (7, 4), (15, 11), (31, 26), (63, 57) giả thiết điều chế BPSK
lý tưởng và kênh truyền AWGN. Thực hiện mô phỏng đánh giá chất lượng giải mã
của thuật toán giải mã mới BPA – DCS với các thuật toán giải mã cứng, thuật toán
BPA, cho kết quả trên hình 3, hình 4, hình 5 và hình 6.
0 1 2 3 4 5 6 7 8
10
-5
10
-4
10
-3
10
-2
10
-1
10
0
EbN0[dB]
B
E
R
BER Hamming (7,4) tren kenh Gauss
giai ma cung
BPA
BPA-DCS
0 1 2 3 4 5 6 7 8
10
-6
10
-5
10
-4
10
-3
10
-2
10
-1
10
0
EbN0[dB]
B
E
R
BER Hamming (15,11) tren kenh Gauss
giai ma cung
BPA
BPA-DCS
Hình 3. So sánh chất lượng của mã
Hamming (7, 4) giữa các thuật toán.
Hình 4. So sánh chất lượng của mã
Hamming (15, 11) giữa các thuật toán.
Từ kết quả mô phỏng ta thấy thuật toán giải mã Hamming dựa vào các ma trận
kiểm tra tương đương mới ứng dụng cho các mã Hamming có độ dài từ mã 7,n
tại tỷ lệ lỗi bít 5 10BER cho phép nâng cao chất lượng khoảng 0.9 dB đến 1.05
dB so với thuật toán giải mã cứng, 0.45 dB đến 0.5 dB so với thuật toán BPA khi
thực hiện cùng số vòng lặp. Độ phức tạp thuật toán tăng không đáng kể so với
thuật toán BPA. Để đạt được kết quả này, dù cải tiến rồi nhưng thuật toán BPA-
DCS vẫn phải trả giá về mặt thời gian. Tuy nhiên, khi chiều dài từ mã tăng, thời
c c
)...2,1( ku
ˆ 'c
(1,2... )
ˆ ' nc (1,2,... )n
c
u Mã hóa
Hamming
Điều chế
Kênh
truyền
Giải điều
chế
Giải mã
Hamming
Kỹ thuật điều khiển & Điện tử
N. T. H. Nhung, P. X. Nghĩa, , “Giải mã mềm mã Hamming dựa trên các mã đối ngẫu.” 34
gian giải mã của thuật toán BPA – DCS rút ngắn khoảng cách so với thuật toán
BPA. Điều này có thể giải thích như sau:
0 1 2 3 4 5 6 7 8
10
-7
10
-6
10
-5
10
-4
10
-3
10
-2
10
-1
10
0
EbN0[dB]
B
E
R
BER Hamming (31,26) tren kenh Gauss
giai ma cung
BPA
BPA-DCS
0 1 2 3 4 5 6 7 8
10
-7
10
-6
10
-5
10
-4
10
-3
10
-2
10
-1
10
0
EbN0[dB]
B
E
R
BER Hamming (63, 57) tren kenh Gauss
giai ma cung
BPA
BPA-DCS
Hình 5. So sánh chất lượng của mã
Hamming (31, 26) giữa các thuật toán.
Hình 6. So sánh chất lượng của mã
Hamming (63, 57) giữa các thuật toán.
Bảng 1. So sánh thời gian trung bình xử lý một từ mã giữa hai thuật toán giải mã
BPA và BPA - DCS với các bộ mã Hamming (7, 4), (15, 11), (31, 26), (63, 57).
Bộ mã BPA BPA - DCS Tỷ lệ thời gian của thuật
toán BPA –DCS so với BPA
Hamming (7, 4) 0,4453 ms 1,1297 ms 253,69 %
Hamming (15, 11) 0,8540 ms 2,0961 ms 245,445 %
Hamming (31, 26) 2,8901 ms 6,8318 ms 236,386 %
Hamming (63, 57) 15,4322 ms 33,101 ms 214,493 %
Tại mỗi vòng lặp thuật toán BPA – DCS chỉ thêm phép tính cộng modulo giữa
các hàng. Mặt khác, thuật toán mới sử dụng nhiều ma trận kiểm tra tương đương
nên thông tin kiểm tra các bit tin tích lũy được nhiều hơn, thời gian hội tụ thông tin
kiểm tra theo điều kiện (14) nhanh hơn khi chiều dài từ mã tăng nên chất lượng
giải mã tốt hơn, và thời gian giải mã với các mã càng dài càng rút ngắn về tỷ lệ
thời gian so với BPA. Bảng 1 là kết quả so sánh thời gian giải mã trung bình cho
một từ mã giữa thuật toán giải mã BPA và thuật toán giải mã BPA - DCS của các
mã Hamming (7, 4), (15, 11), (31, 26), (63, 57) được thực hiện trên cùng một máy
tính cũng cho kết quả phù hợp với phân tích.
5. KẾT LUẬN
Từ đặc điểm của thuật toán giải mã mềm BPA và tính chất đối ngẫu của mã
sửa sai, bài báo đã đưa ra thuật toán cải tiến mới dựa vào các ma trận kiểm tra
tương đương nhằm cải thiện BER đối với các mã Hamming có chiều dài lớn hơn 7.
Chất lượng thuật toán giải mã mới tăng 0.9 dB đến 1.05 dB so với thuật toán giải
mã cứng, so với thuật toán BPA cải thiện 0.45 dB đến 0.5 dB. Độ chênh lệch về
thời gian giải mã so với BPA giảm dần khi chiều dài từ mã tăng trong khi độ phức
tạp và mức độ tính toán không tăng đáng kể.
Nghiên cứu khoa học công nghệ
Tạp chí Nghiên cứu KH&CN quân sự, Số 46, 12 - 2016 35
TÀI LIỆU THAM KHẢO
[1]. Hamming,R.W.,” Error detecting and error correcting codes”, Bell System Tech.
J. 29 (1950) 147–160.
[2]. Carlos R .P . Hartmann, Luther D . Rudolph, " An Optimum Symbol-by Symbol
decoding rule for linear codes", Electrical Engineering and Computer Science
Technical Reports, Paper 8, September 1975.
[3]. H, Greenberger, " An iterative algorithm for decoding block codes transmitted
over a memoryless channel", DSN progress report 42-47, July and August
1978.
[4]. M. P. C. Fossorier, M.Mihaljevic, and H. Imai, “Reduced complexity iterative
decoding of low density parity check codes based on belief propagation”,
IEEE Trans. Commun., vol. 47, no. 5, pp. 673–680, May 1999.
[5]. R. Tanner. "A recursive approach to low complexity codes", IEEE
Transactions on Information Theory, IT-27(5):533--547, September 1981.
[6]. Nguyen Tung Hung, “A new decoding algorithm based on equivalent parity
check matrix for LDPC codes”, REV Journall on Electronics and
Communications, Vol.3, No. 1-2, Jannuary – June 2013, pp.73-76.
ABSTRACT
SOFT- DECISION DECODING OF HAMMING CODE
BASED ON DUAL CODES
In this article, the BPA which is improved based on the duality of linear
block codes is proposed. The new algorithm proposed soft decision decoding
with equivalent parity check matrixs applied for Hamming codes, in which
the equivalent parity check matrixs are developed using dual codes. It is
shown that the gain of the new algorithm is 0,45 dB to 0,5 dB better
compared to the traditional BPA whereas the decoding time and complexity
faces a negligible increase.
Keywords: Channel codes, Soft- decision decoding, Hamming code.
Nhận bài ngày 29 tháng 6 năm 2016
Hoàn thiện ngày 03 tháng 11 năm 2016
Chấp nhận đăng ngày 14 tháng 12 năm 2016
Địa chỉ: 1 Đại học Kinh tế Kỹ thuật Công nghiệp;
2 Học viện Kỹ thuật quân sự;
3 Đại học Sư phạm Kỹ thuật Nam Định;
4 Trung tâm di động, Tổng Công ty mạng lưới Viettel.
* Email: nhungnh13@gmail.com
Các file đính kèm theo tài liệu này:
- 04_nghia_4338_2150938.pdf