非二进制LDPC码的低复杂度X-EMS算法
89 浏览量
更新于2024-08-27
收藏 314KB PDF 举报
"低复杂度X-EMS算法在非二进制LDPC码中的应用"
本文是一篇关于非二进制LDPC（低密度奇偶校验）码的研究论文，主要探讨了低复杂度的X-EMS（扩展最小和）算法。在介绍中，X-EMS算法被重新定义为一种称为M-EMS的简化搜索树算法。同时，文章提出了M-EMS算法的两个变体：T-EMS算法和D-EMS算法。
一、引言
非二进制LDPC码最早由Gallager在1963年提出，它利用模算术进行编码。Davey和MacKay在后续的工作中引入了一类定义在有限域𝔽𝑞上的非二进制LDPC码，即我们常说的 Quarternary LDPC（四元）码，并提出了一种用于解码的和积算法，即Q-ary Sum-Product Algorithm (QSPA)。
二、X-EMS算法及其变体
X-EMS算法家族包括基本的M-EMS算法以及其衍生的T-EMS和D-EMS算法。这些算法旨在降低解码过程中的计算复杂度，同时保持良好的解码性能。通过仿真结果，作者们证明了这三种算法（统称为X-EMS算法），结合因子校正技术，在性能上几乎可以与QSPA相媲美，但计算复杂度显著降低。
三、算法原理
X-EMS算法的核心思想是减少搜索空间，以降低计算量。M-EMS算法通过构建简化搜索树结构来实现这一目标，而T-EMS和D-EMS算法则在此基础上进行了进一步的优化，可能涉及到不同的信息更新策略或搜索路径选择。
四、性能比较与分析
通过对比实验，X-EMS算法家族显示出与QSPA相当的误码率性能，这表明它们在保持高效解码的同时，降低了硬件实现的难度和功耗。因子校正技术的引入进一步提升了算法的性能，帮助算法在接近最优解的同时，减少了计算资源的需求。
五、总结与展望
该研究对非二进制LDPC码的高效解码算法提供了新的视角，X-EMS算法族为实际系统中的应用提供了可能性。未来的研究可能进一步优化这些算法，探索更多降低复杂度的方法，或者将这些算法应用到更广泛的通信和数据存储场景中。
关键词：EMS算法，非二进制LDPC码，Q-ary和积算法（QSPA），简化搜索树算法。
IEEE TRANSACTIONS ON COMMUNICATIONS, VOL. 60, NO. 1, JANUARY 2012 9
Low Complexity X-EMS Algorithms for Nonbinary LDPC Codes
Xiao Ma, Kai Zhang, Haiqiang Chen, and Baoming Bai
Abstract—The extended min-sum (EMS) algorithm is re-
described as a reduced-search trellis algorithm (called 𝑀 -EMS
algorithm). Two variants of the 𝑀-EMS algorithm, called 𝑇 -
EMS algorithm and 𝐷-EMS algorithm, are presented. Simulation
results show that, these three algorithms (referr ed to as 𝑋-EMS
algorithms for convenience), combined with factor correction
techniques, perform almost as well as the Q-ary sum-product
algorithm (QSPA) but with a much lower complexity.
Index Terms—EMS algorithms, nonbinary low-density parity-
check (LDPC) codes, Q-ary sum-product algorithm (QSPA),
reduced-search trellis algorithm.
I. INT RODUCTION
N
ONBINARY low-density parity-check (LDPC) codes
were first introduced by Gallager [1] using modulo
arithmetic. In [2], Davey and MacKay presented a class
of nonbinary LDPC codes defined over the finite field 𝔽
𝑞
,
referred to as 𝑄-ary LDPC codes here. They also introduced
a sum-product algorithm for decoding 𝑄-ary LDPC codes,
which is known as QSPA. A straightforward implementation
of the QSPA has a very high computational complexity, which
makes the nonbinary LDPC codes limited in certain applica-
tions. To reduce the decoding complexity, a more efficient
decoding algorithm based on fast Fourier transform (FFT),
known as FFT-QSPA [3], [4], can be implemented for the
nonbinary codes over finite fields with characteristic 2. In
2007, Declercq et al proposed an extended min-sum (EMS)
algorithm [5], [6] for nonbinary LDPC codes, which can be
viewed as a generalized min-sum algorithm for binary LDPC
codes.
In this letter, we first redescribe the original EMS algorithm
as a reduced-search trellis algorithm that retains only those
states/branches at each trellis section with the 𝑀 largest met-
rics, thus called 𝑀-EMS algorithm here. We then present two
variants of the 𝑀-EMS algorithm, called 𝑇 -EMS algorithm
and 𝐷-EMS algorithm, respectively. The 𝑇 -EMS algorithm
retains only those states/branches at each trellis section who se
metrics exceed a designated threshold T; while the 𝐷-EMS
algorithm retains only those states/branches at each trellis
Paper approved by T. M. Duman, the Editor for Coding Theory and
Applications of the IEEE Communications Society. Manuscript received April
28, 2011; re vised July 23, 2011.
This work was supported by NSFs of China (No.61172082, No.61102090
and No.U0635003), and the Guangdong Provincial Program for High-Level
Talents in University.
X. Ma, K. Zhang, and H. Chen are with the Department of
Electronics and Communication Engineering, Sun Yat-sen University ,
Guangzhou 510275, China. H. Chen is also with the School of Com-
puter, Electronics and Information, Guangxi University, Nanning 530004,
China (e-mail: maxiao@mail.sysu.edu.cn, zhangkai_sysu@163.com, chen-
haiq@mail2.sysu.edu.cn).
B. Bai is with the State Ke y Lab of ISN, Xidian University, Xi’an 710071,
China (e-mail: bmbai@mail.xidian.edu.cn).
Digital Object Identifier 10.1109/TCOMM.2011.092011.110082
section whose metrics deviate from the maximum one within
a designated parameter 𝐷.
II. D
ECODING NONBINARY LDPC CODES USING
SUM-PRODUCT AL GORITHMS
A. Normal Graphical Realizations of Nonbinary LDPC Codes
Let 𝔽
𝑞
be the finite field with 𝑞 elements, which is simply
denoted by 𝔽
𝑞
= {0, 1, 2, ⋅⋅⋅,𝑞 − 1}. A nonbinary LDPC
code C
𝑞
[𝑛, 𝑘] over 𝔽
𝑞
can be defined as the null space of a
sparse parity-check matrix H =[ℎ
𝑖,𝑗
]
𝑚×𝑛
with ℎ
𝑖,𝑗
∈ 𝔽
𝑞
.A
vector 𝑣
=(𝑣
0
,𝑣
1
, ⋅⋅⋅ ,𝑣
𝑛−1
) ∈ 𝔽
𝑛
𝑞
is a codeword if and only
if H𝑣
T
=0. For convenience, we define the following two
index sets
𝒩
𝑖
= {𝑗 :0≤ 𝑗 ≤ 𝑛 − 1,ℎ
𝑖,𝑗
∕=0}
for each row 𝑖 of H and
ℳ
𝑗
= {𝑖 :0≤ 𝑖 ≤ 𝑚 −1,ℎ
𝑖,𝑗
∕=0}
for each column 𝑗 of H.
Given the parity-check matrix H, we can realize the code
by a normal graph as shown in Fig. 1(a). In a general
normal graph [7], edges represent variables, while vertices
represent constraints. Similar to [8], we have the following
specifications in the scenario of nonbinary LDPC codes: 1) a
left vertex (represented by
=
) is called a v-node,which
corresponds to a column of H; 2) a right vertex (represented
by
+
) is called a c-node, which corresponds to a row of
H;3)ifℎ
𝑖𝑗
∕=0, we introduce a middle vertex (represented
by
H
), called an h-node (denoted by ℋ
𝑖𝑗
). The h-node
corresponding to ℎ
𝑖𝑗
∕=0bridges the 𝑗-th v-node with the 𝑖-th
c-node. The degree of any h-node is exactly two, where the
edge from the 𝑗-th v-node is denoted by 𝑋
𝑖𝑗
and the edge to
the 𝑖-th c-node is denoted by 𝑌
𝑖𝑗
; and 4) all edges (variables)
connecting to the 𝑗-th v -node must take identical values and
all edges (variables) connecting to the 𝑖-th c-node must add
up to zero.
B. Iterative Message Processing/Passing Algorithms
A message associated with a discrete variable is defined
as its pro bability mass function (pmf) here. For example, a
message associated with a random variable 𝑋 over 𝔽
𝑞
can
be represented by a real vector 𝑃
𝑋
(𝑥),𝑥 ∈ 𝔽
𝑞
.Let𝑋 be
a random variable corresponding to the edge connecting two
vertices 𝒜 and ℬ. We use the notation 𝑃
(𝒜→ℬ)
𝑋
(𝑥),𝑥∈ 𝔽
𝑞
to
indicate the direction of the message flow.
To describe the algorithm more clearly, we introduce a basic
rule for message processing at an arbitrary node. Let 𝒜 be a
node connecting to ℬ
𝑗
with random variables 𝑍
𝑗
defined over
𝔽
𝑞
(0 ≤ 𝑗 ≤ 𝑑 − 1), as shown in Fig. 1(b). Assume that
0090-6778/12$31.00
c
2012 IEEE
下载后可阅读完整内容，剩余4页未读，立即下载
2021-05-29 上传
2022-07-13 上传
2021-01-20 上传
2012-10-28 上传
2023-07-28 上传
2021-02-11 上传
2021-02-21 上传
2021-05-06 上传
weixin_38699726
- 粉丝: 5
- 资源: 927
我的内容管理
展开
最新资源
- MATLAB新功能：Multi-frame ViewRGB制作彩色图阴影
- XKCD Substitutions 3-crx插件：创新的网页文字替换工具
- Python实现8位等离子效果开源项目plasma.py解读
- 维护商店移动应用：基于PhoneGap的移动API应用
- Laravel-Admin的Redis Manager扩展使用教程
- Jekyll代理主题使用指南及文件结构解析
- cPanel中PHP多版本插件的安装与配置指南
- 深入探讨React和Typescript在Alias kopio游戏中的应用
- node.js OSC服务器实现：Gibber消息转换技术解析
- 体验最新升级版的mdbootstrap pro 6.1.0组件库
- 超市盘点过机系统实现与delphi应用
- Boogle: 探索 Python 编程的 Boggle 仿制品
- C++实现的Physics2D简易2D物理模拟
- 傅里叶级数在分数阶微分积分计算中的应用与实现
- Windows Phone与PhoneGap应用隔离存储文件访问方法
- iso8601-interval-recurrence：掌握ISO8601日期范围与重复间隔检查
