An improved low-complexity sum-product decoding algorithm for low-density parity-check codes

Roberts Kingston; Jayabalan Ramesh

doi:10.1631/FITEE.1400269

Your Location：

Home >

Browse articles >

An improved low-complexity sum-product decoding algorithm for low-density parity-check codes

Electronic Engineering | Updated：2022-06-06

- An improved low-complexity sum-product decoding algorithm for low-density parity-check codes
- 一种改进的用于低密度奇偶校验码的低复杂度和积译码
- Frontiers of Information Technology & Electronic Engineering Vol. 16, Issue 6, Pages: 511-518(2015)
- Affiliations：
  
  Department of Electronics and Communication Engineering, PSG College of Technology, Coimbatore 641004, India
- Author bio：
  
  †E-mail:king.pane@gmail.com
- Funds：
- DOI：10.1631/FITEE.1400269
  CLC：
- Received：24 July 2014，
  
  Revised：2015-05-07，
  
  Accepted：25 September 2014，
  
  Published：2015-03
- Accepted：
Scan QR Code
Roberts Kingston, Jayabalan Ramesh. An improved low-complexity sum-product decoding algorithm for low-density parity-check codes[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(6): 511-518.
DOI：

Roberts Kingston, Jayabalan Ramesh. An improved low-complexity sum-product decoding algorithm for low-density parity-check codes[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(6): 511-518. DOI： 10.1631/FITEE.1400269.

摘要

目的

为减少校验节点过程总计算量，对低密度奇偶校验译码提出低复杂度的和积译码算法。

创新点

降低和积译码计算复杂度的同时不损失译码性能。

方法

在校验节点过程中使用时移快速傅里叶变换降低计算复杂度；在变量节点过程中使用优化后的常整数提升译码性能。所提算法性能在Wi-MAX和WLAN中的标准低密度奇偶校验码上测试并验证，且与SPA、SSPA和MSPA进行性能比较（图1-3）。

结论

仿真结果表明，整体上所述算法对编码增益的提高值在0.04到0.46 dB之间；与和积算法（SPA）相比，所述算法可以降低译码过程所需42%-67%的全部代数运算操作。

Abstract

In this paper

an improved low-complexity sum-product decoding algorithm is presented for low-density parity-check (LDPC) codes. In the proposed algorithm

reduction in computational complexity is achieved by utilizing fast Fourier transform (FFT) with time shift in the check node process. The improvement in the decoding performance is achieved by utilizing an optimized integer constant in the variable node process. Simulation results show that the proposed algorithm achieves an overall coding gain improvement ranging from 0.04 to 0.46 dB. Moreover

when compared with the sum-product algorithm (SPA)

the proposed decoding algorithm can achieve a reduction of 42%–67% of the total number of arithmetic operations required for the decoding process.

关键词

Keywords

references

VA Chandrasetty , SM Aziz . FPGA implementation of a LDPC decoder using a reduced complexity message passing algorithm . J Netw , 2011 . 6 ( 1 ): 36 - 45 . DOI: 10.4304/jnw.6.1.36-45 http://doi.org/10.4304/jnw.6.1.36-45 .

SY Chung , GD Forney , TJ Richardson , 等 . On the design of low-density parity-check codes within 0.0045 dB of the Shannon limit . IEEE Commun Lett , 2001 . 5 ( 2 ): 58 - 60 . DOI: 10.1109/4234.905935 http://doi.org/10.1109/4234.905935 .

MPC Fossorier , M Mihaljevic , H Imai . Reduced complexity iterative decoding of low-density parity check codes based on belief propagation . IEEE Trans Commun , 1999 . 47 ( 5 ): 673 - 680 . DOI: 10.1109/26.768759 http://doi.org/10.1109/26.768759 .

RG Gallager . Low-density parity-check codes . IRE Trans Inform Theory , 1962 . 8 ( 1 ): 21 - 28 . DOI: 10.1109/TIT.1962.1057683 http://doi.org/10.1109/TIT.1962.1057683 .

A Goupil , M Colas , G Gelle , 等 . FFT-based BP decoding of general LDPC codes over Abelian groups . IEEE Trans Commun , 2007 . 55 ( 4 ): 644 - 649 . DOI: 10.1109/TCOMM.2007.894089 http://doi.org/10.1109/TCOMM.2007.894089 .

YC He , SH Sun , XM Wang . Fast decoding of LDPC codes using quantisation . Electron Lett , 2002 . 38 ( 4 ): 189 - 190 . DOI: 10.1049/el:20020131 http://doi.org/10.1049/el:20020131 .

IEEE IEEE Standard for Local and Metropolitan Area Networks Part 16: Air Interface for Broadband Wireless Access Systems . 2009 . IEEE Std 802.16-2009 . DOI: 10.1109/IEEESTD.2009.5062485 http://doi.org/10.1109/IEEESTD.2009.5062485 .

IEEE IEEE Draft Standard for Information Technology—Telecommunications and Information Exchange Between Systems Local and Metropolitan Area Networks—Specific Requirements Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications . 2015 . IEEE P802.11-REVmc/D4.0 . .

X Jiang , MH Lee , J Qi . Improved progressive edge-growth algorithm for fast encodable LDPC codes . EURASIP J Wirel Commun Netw , 2012 . 2012 178.1 - 17810 . DOI: 10.1186/1687-1499-2012-178 http://doi.org/10.1186/1687-1499-2012-178 .

SG Johnson , M Frigo . A modified split-radix FFT with fewer arithmetic operations . IEEE Trans Signal Process , 2007 . 55 ( 1 ): 111 - 119 . DOI: 10.1109/TSP.2006.882087 http://doi.org/10.1109/TSP.2006.882087 .

MH Lee , JH Han , MH Sunwoo . New simplified sum-product algorithm for low complexity LDPC decoding . 2008 . IEEE Workshop on Signal Processing Systems . 61 - 66 . DOI: 10.1109/SIPS.2008.4671738 http://doi.org/10.1109/SIPS.2008.4671738 .

DJC MacKay , RM Neal . Near Shannon limit performance of low density parity check codes . Electron Lett , 1997 . 33 ( 6 ): 457 - 458 . DOI: 10.1049/el:19970362 http://doi.org/10.1049/el:19970362 .

A Morello , V Mignone . DVB-S2: the second generation standard for satellite broad-band services . 2006 . Proc. IEEE . ( 1 ): 210 - 227 . DOI: 10.1109/JPROC.2005.861013 http://doi.org/10.1109/JPROC.2005.861013 .

S Papaharalabos , P Sweeney , BG Evans , 等 . Modified sum-product algorithm for decoding low-density parity-check codes . IET Commun , 2007 . 1 ( 3 ): 294 - 300 . DOI: 10.1049/iet-com:20060173 http://doi.org/10.1049/iet-com:20060173 .

TJ Richardson , RL Urbanke . The capacity of low-density parity-check codes under message-passing decoding . IEEE Trans Inform Theory , 2001 . 47 ( 2 ): 599 - 618 . DOI: 10.1109/18.910577 http://doi.org/10.1109/18.910577 .

L Safarnejad , MR Sadeghi . FFT based sum-product algorithm for decoding LDPC lattices . IEEE Commun Lett , 2012 . 16 ( 9 ): 1504 - 1507 . DOI: 10.1109/LCOMM.2012.073112.120996 http://doi.org/10.1109/LCOMM.2012.073112.120996 .

HV Sorensen , M Heideman , CS Burrus . On computing the split-radix FFT . IEEE Trans Acoust Speech Signal Process , 1986 . 34 ( 1 ): 152 - 156 . DOI: 10.1109/TASSP.1986.1164804 http://doi.org/10.1109/TASSP.1986.1164804 .

L Yuan , X Tian , Y Chen . Pruning split-radix FFT with time shift . 2011 . Proc. Int. Conf. on Electronics, Communications and Control . 1581 - 1586 . DOI: 10.1109/ICECC.2011.6066654 http://doi.org/10.1109/ICECC.2011.6066654 .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

A lightweight clutter suppression algorithm for passive bistatic radar

Efficient construction of a substitution box based on a Mordell elliptic curve over a finite field

Related Author

Yong WU

Luo ZUO

Dongliang PENG

Zhikun CHEN

Naveed Ahmed AZAM

Umar HAYAT

Ikram ULLAH

Related Institution

Intelligent Transportation School, Zhejiang Institute of Communications

Guangzhou Institute of Technology, Xidian University

School of Automation, Hangzhou Dianzi University

Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University

Department of Mathematics, Quaid-i-Azam University

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰