Performance Investigation of Reduced
Complexity Bit-Flipping using Variable
Thresholds and Noise Perturbation
Julian Webber, Toshihiko Nishimura, Takeo Ohgane, Yasutaka Ogawa
Graduate School of Information Science and Technology, Hokkaido University,
Kita 14, Nishi 9, Kita-ku, Sapporo 060-0814, Japan
jwebber@ieee.org, {nishim, ohgane, ogawa}@ist.hokudai.ac.jp

Abstract—The near Shannon capacity approaching low-density parity-check (LDPC) linear block codes are now in widespread use inmodern systems including the long term evolution advanced (LTE-A) cellular, 802.11n Wi-Fi and DVB-S2 satellite communications
standards. The decoders based on the iterative belief propagation algorithm provide near optimum performance but also have very highcomputational complexity. Therefore significant research has recently focused on reduced complexity architectures based on the group of
so-called bit-flipping algorithms. In the basic bit-flipping algorithm the number of failed parity checks for each bit is computed and the
bit with the maximum failed parity checks is inverted. Inverting bits above a certain threshold removes the complexity involved with amaximum-search and adaptive thresholds on each bit can further reduce the computation overhead. The criterion for threshold updates
affects the error and convergence performances. Here, we describe a low-complexity architecture that has two (or more) decoder
branches each with a different threshold scaling factor and select the threshold and bits at each iteration from the branch with the lowest
syndrome sum. We then investigate the effect of adding a random Uniform or Gaussian noise perturbation to the threshold in order toreduce the average iteration count further in order to provide the opportunity to escape from stuck decoding states.
Keyword—bit-flip algorithm, gradient-descent, reduced-complexity, noise perturbation, LDPC decoding.
Julian WEBBER received the M.Eng. and Ph.D. degrees from the University of Bristol, UK in 1996 and 2004 respectively. From 1996 to1998, he was with Texas Instruments working on ASIC and DSP. From 2001-07 he was a Research Fellow at Bristol University working on
real-time MIMO-OFDM test beds and digital pre-distortion systems. Since 2007, he has been with Hokkaido University, where he is aResearch Fellow. His current research interests are in LDPC and MIMO signal processing. Dr Webber is a member of the IEEE and IEICE.

Toshihiko NISHIMURA received the B.S. and M.S. degrees in physics and Ph.D. degree in electronics engineering from Hokkaido
University, Sapporo, Japan, in 1992, 1994, and 1997, respectively. In 1998, he joined the Graduate School of Engineering (reorganized toGraduate School of Information Science and Technology at present) at Hokkaido University, where he is currently an Assistant Professor ofthe Graduate School of Information Science and Technology. His current research interests are in MIMO systems using smart antennatechniques. Dr. Nishimura received the Young Researchers' Award of IEICE Japan in 2000, and the Best Paper Award from IEICE Japan in2007. Dr. Nishimura is a member of the IEEE.

Takeo OHGANE received the B.E., M.E., and Ph.D. degrees in electronics engineering from Hokkaido University, Sapporo, Japan, in 1984,
1986, and 1994, respectively. From 1986 to 1992, he was with Communications Research Laboratory, Ministry of Posts andTelecommunications. From 1992 to 1995, he was on assignment at ATR Optical and Radio Communications Research Laboratory. Since
1995, he has been with Hokkaido University, where he is an Associate Professor. During 2005-2006, he was at Centre for Communications
Research, University of Bristol, U.K., as a Visiting Fellow. His interests are in MIMO signal processing for wireless communications. Dr.
Ohgane received the IEEE AP-S Tokyo Chapter Young Engineer Award in 1993, the Young Researchers' Award of IEICE Japan in 1990,
and the Best Paper Award from IEICE Japan in 2007. Dr. Ohgane is a member of the IEEE.

Yasutaka OGAWA received the B.E., M.E. and Ph.D. degrees from Hokkaido University, Sapporo, Japan, in 1973, 1975, and 1978,
respectively. Since 1979, he has been with Hokkaido University, where he is currently a Professor of the Graduate School of Information
Science and Technology. During 1992-1993, he was with ElectroScience Laboratory, the Ohio State University, U.S.A., as a Visiting
Scholar, on leave from Hokkaido University. His interests are in adaptive antennas, mobile communications, super-resolution techniques,and MIMO systems. Dr. Ogawa received the Young Researchers' Award of IEICE Japan in 1982, and the Best Paper Award from IEICE
Japan in 2007. Dr. Ogawa is a Fellow of the IEEE.