Wireless sensor networks are used in many diverse application scenarios that require the network designer to trade off different factors. Two such factors of importance in many wireless sensor networks are communication reliability and battery life. This paper describes an efficient, low complexity, high throughput channel decoder suited to decoding low-density parity-check (LDPC) codes. LDPC codes have demonstrated excellent error-correcting ability such that a number of recent wireless standards have opted for their inclusion. Hardware realisation of practical LDPC decoders is a challenging area especially when power efficient solutions are needed. Implementation details are given for an LDPC decoding algorithm, termed adaptive threshold bit flipping (ATBF), designed for low complexity and low power operation. The ATBF decoder was implemented in 90？nm CMOS at 0.9？V using a standard cell design flow and was shown to operate at 250 MHz achieving a throughput of 252？Gb/s/iteration. The decoder area was 0.72？mm2 with a power consumption of 33.14？mW and a very small energy/decoded bit figure of 1.3？pJ. 1. Introduction Wireless sensor networks (WSN) have been deployed in many applications, from oceanography, environmental monitoring, understanding wildlife behaviour to intrusion detection, and building structural analysis, see [1]. WSNs are composed of a number of cheap, small, resource-limited nodes with some form of sensor and wireless communication capability. As such, careful design of the overall network is necessary to ensure sufficient robustness of the network to node failures, deleterious communications, and sensor data correlation. The radio system can be a major source of power drain compared to other systems within the sensor node, as stated in [2]. Of the many functions performed within a radio system, channel decoding is one of the most computationally intensive and, thus, resource demanding. Low-density parity-check (LDPC) channel codes were described by Gallager [3] in 1963 and subsequently rediscovered by Mackay [4]. LDPC codes are capacity approaching codes, coming within 0.0045？dB of the Shannon capacity limit [5], whilst being attractive from an implementation viewpoint due to the availability of iterative decoding algorithms. In addition to describing error-correcting codes based on low-density parity-check matrices, Gallager presented a number of practical decoding algorithms. A probabilistic soft decision message passing algorithm referred to as the sum-product (SP) algorithm capable of achieving optimum performance was one class of
References
[1]
J. Beutel, K. Rmer, M. Ringwald, and M. Woehrle, “Deployment techniques for sensor networks,” in Sensor Networks, G. Ferrari, Ed., Signals and Communication Technology, pp. 219–248, Springer, Berlin, Germany, 2009.
[2]
A. Bachir, M. Dohler, T. Watteyne, and K. K. Leung, “MAC essentials for wireless sensor networks,” IEEE Communications Surveys and Tutorials, vol. 12, no. 2, pp. 222–248, 2010.
[3]
R. G. Gallager, Low Density Parity Check Codes,, Monograph, M.I.T. Press, 1963.
[4]
D. J. C. MacKay, “Good codes based on very sparse matrices,” in Proceedings of the 5th IMA Conference on Cryptography and Coding, pp. 100–111, Springer, London, UK, 1995.
[5]
S. Y. Chung, G. David Forney, T. J. Richardson, and R. Urbanke, “On the design of low-density parity-check codes within 0.0045？dB of the Shannon limit,” IEEE Communications Letters, vol. 5, no. 2, pp. 58–60, 2001.
[6]
M. Mansour and N. Shanbhag, “A 1.6？Gbit/sec 2048-bit programmable and code-rate tunable LDPC decoder chip,” in Proceedings of the 3rd International Symposium on Turbo Codes & Related Topics (ISTC '03), pp. 137–140, Brest, France, September 2003.
[7]
M. Mansour and N. Shanbhag, “High-throughput LDPC decoders,” IEEE Transactions on Very Large Scale Integration Systems, vol. 11, no. 6, pp. 976–996, 2003.
[8]
D. E. Hocevar, “A reduced complexity decoder architecture via layered decoding of LDPC codes,” in Proceedings of the IEEE Workshop on Signal Processing Systems Design and Implementation (SIPS '04), pp. 107–112, October 2004.
[9]
M. Ismail, I. Ahmed, J. Coon, S. Armour, T. Kocak, and J. McGeehan, “Low latency low power bit flipping algorithms for LDPC decoding,” in Proceedings of the IEEE 21st International Personal Indoor and Mobile Radio Communications (PIMRC '10), pp. 278–282, 2010.
[10]
Y. Kou, S. Lin, and M. P. C. Fossorier, “Low-density parity-check codes based on finite geometries: a rediscovery and new results,” IEEE Transactions on Information Theory, vol. 47, no. 7, pp. 2711–2736, 2001.
[11]
Y. Kou, S. Lin, and M. P. C. Fossorier, “Low density parity check codes based on finite geometries: a rediscovery,” in Proceedings of the IEEE International Symposium on Information Theory, p. 200, ita, June 2000.
[12]
J. Zhang and M. P. C. Fossorier, “A modified weighted bit-flipping decoding of low-density parity-check codes,” IEEE Communications Letters, vol. 8, no. 3, pp. 165–167, 2004.
[13]
T. Wadayama, K. Nakamura, M. Yagita, Y. Funahashi, S. Usami, and I. Takumi, “Gradient descent bit flipping algorithms for decoding LDPC codes,” in Proceedings of the International Symposium on Information Theory and its Applications (ISITA '08), pp. 1–6, December 2008.
[14]
D. J. C. Mackay, “Encyclopedia of sparse graph codes,” http://www.inference.phy.cam.ac.uk/mackay/codes/data.html.
[15]
Z. Wang, Y. Zhang, and K. K. Parhi, “Study of early stopping criteria for turbo decoding and their applications in WCDMA systems,” in Proceedings of the IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP '06), pp. III1016–III1019, May 2006.
[16]
J. Li, X. Hu You, and J. Li, “Early stopping for LDPC decoding: convergence of mean magnitude (CMM),” IEEE Communications Letters, vol. 10, no. 9, pp. 667–669, 2006.
[17]
F. Kienle and N. Wehn, “Low complexity stopping criterion for LDPC code decoders,” in Proceedings of the IEEE 61st Vehicular Technology Conference (VTC '05), vol. 1, pp. 606–6609, May 2005.
[18]
Z. Cui, L. Chen, and Z. Wang, “An efficient early stopping scheme for LDPC decoding,” in Proceedings of the 13th NASA Symposium on VLSI Design, Moscow, Idaho, USA, June 2007.
[19]
T. Mohsenin, D. N. Truong, and B. M. Baas, “A low-complexity message-passing algorithm for reduced routing congestion in LDPC decoders,” IEEE Transactions on Circuits and Systems I, vol. 57, no. 5, pp. 1048–1061, 2010.
[20]
T. Mohsenin, D. Truong, and B. Baas, “A low-complexity message-passing algorithm for reduced routing congestion in LDPC decoders,” IEEE Transactions on Circuits and Systems I, vol. 57, no. 5, pp. 1048–11061, 2010.
[21]
A. Darabiha, A. Carusone, and F. Kschischang, “Block-interlaced LDPC decoders with reduced interconnect complexity,” IEEE Transactions on Circuits and Systems II, vol. 55, no. 1, pp. 74–778, 2008.
[22]
T. Brack, M. Alles, T. Lehnigk-Emden et al., “A survey on LDPC codes and decoders for OFDM-based UWB systems,” in Proceedings of the IEEE 65th Vehicular Technology Conference (VTC '07), pp. 1549–1553, 2007.
[23]
A. Blanksby and C. Howland, “A 690-mW 1-Gb/s 1024-bit, rate-1/2 low-density parity-check code decoder,” IEEE Journal of Solid-State Circuits, vol. 37, no. 3, pp. 404–412, 2002.
[24]
M. Mansour and N. Shanbhag, “A 640-Mb/s 2048-bit programmable LDPC decoder chip,” IEEE Journal of Solid-State Circuits, vol. 41, no. 3, pp. 684–698, 2006.
