International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1832
ISSN 2229-5518
M. M. Jadhav1, Chetna N. Kharkar2 , Dr. A. M. Sapkal3
Abstract — Low Density Parity Check (LDPC) codes are one of the best error correcting codes that enable the future generations of wireless devices. In this paper we have presented an FPGA based self error checking & correction system with higher capability. We implemented the error correction algorithms such as belief propagation & bit flip algorithm. The number of error corrected is simulated using Xilinx High level Synthesis tool & Modelsim simulator. A complete self checking system is implemented on Xilinx Spartan 3E FPGA & synthesis is done using ISE13.2. The decoded codeword of the decoder is displayed on PC HyperTerminal using serial Rs232 interface. The system is capable of correcting large & different size of codeword. Self error detection & correction capability of the system is compared & verified in presence of noise.
—————————— —————————
IJSEOptimizationRresults for various channels, such
Low-density parity-check (LDPC) codes are
forward error-correction codes [1], first proposed in the 1962 PhD thesis of Gallager at MIT[2].The computational effort in implementing coder & encoder are more for these codes.LDPC codes is then rediscovered by Mackay and Neal [3].These codes are decoded iteratively by Belief propagation decoding on their associated factor graph [4]. In the mean time the field of forward error correction was dominated by highly structured algebraic block and convolution codes.
1 M. M. Jadhav is presently perusing PHD from Government college of Engineering, Pune in the field of communication. He has guided graduates & more than ten Post graduates students, His area of Interest is communication system .Email- makj123@yahoo.com
2 Chetna N. Kharkar is Currently Working as a Sr. Design Engineer at Qualitat systems, Pune (India).She has a 6+ years of experience in Embedded domain. Perusing Master of Engineering from Sinhgad college of Engineering,Pune,India,Email-chetnakharkar@gmail.com
3 Dr. A. M. Sapkal is HOD of E&TC Department at government college of Engineering, Pune.He has 23 years of experience in teaching, 3 years Industrial & 14 years of Research experience. He has guided More than 100 post graduates students. Email -hod.extc@coep.ac.in
as the Additive White Gaussian Noise (AWGN) channel and the Binary Symmetric Channel (BSC) have produced specific degree distributions such that the corresponding codes come very close to capacity [5].In fact, the state of art in the coding field is currently achieved by LDPC codes, which was accomplished by Chung et al. [6].It was soon recognized that these block codes were in fact a rediscovery of the LDPC codes developed years earlier by Gallager. New generalizations of Gallager’s LDPC codes by a number of researchers produced new irregular LDPC codes. These codes easily outperform the best turbo codes, as well as offering certain practical advantages and cleaner setup for theoretical results. Today, design techniques for LDPC codes exist which enable the construction of codes which approach the Shannon’s capacity to within hundredths of a decibel. Low density parity check (LDPC) codes have been extensively adopted in next-generation forward error correction applications. They achieve very good performance using the iterative decoding approach of the belief-propagation (BP) [7].The main contribution of this paper is implementation of self error checking system on Xilinx Spartan 3E FPGA using High level synthesis tool and Synthesis has been done for LDPC codes Construction & Bit-flipping decoding. Self error checking system is flexible to
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1833
ISSN 2229-5518
use for any length of code word (or) data word and also for any rate of code word. So the usage
of this code leads to high performance. The above decoding algorithms can recover the original codeword in the presence of large amounts of noise.Decoding algorithms such as belief propagation & Bit flip algorithm are simulated, error detection and correction capability of both algorithms compared & verified
The decoding algorithm can be stated in three steps:
The decoding algorithm is fed by the log- likelihood ratio as represented in equation (2).
r0 [i] = log{P(ci = 0 | yi ) / P(ci = 1 | yi)} -------(1)
Ej’,i = (∏ αj,i’ ) g (Σ f(β j,i’ ))
where αj,i’ = sign (Mj,i)’ and β j,i’ = | Mj,i |’
3. Two math functions are used in step 2 for transposing the initial needed convolution in the log-Fourier domain. These functions are defined as,
f(x) = log [tanh (|x|/2)]
g(x) = 2 x tanh -1 (exp( x) )
4. The hard decision process that computes the estimated value of each symbol of the code. For each data node:
Li = ri + Σ Ej,i
Mi = y i
IJSErepeat R
The code word simply multiplied by the transpose of H . If the result is all zero vectors then the code word is valid.
HT*Z = 0 -------(2)
The algorithms used to decode LDPC codes are the belief propagation algorithm or the sum- product algorithm, bit flipping algorithm.
Decoding algorithm consists of three steps computed iteratively
1. The data node process (data update) computes Mj,i messages from Ej,i messages and log-likely hood ratios. For each data node, i being the degree of the node and r i is the log-likelihood ratio entering this node:
M j,i = Σ Ej’,i +ri
j’∊Ai,j’≠j
2. The check node process (check update)
computes E j,i messages. For each check node (j being the degree of the node):
Ej,i = ∑i′εBj ,i′, i≠i’ (Mi′ mod 2)
if the messages E j,i disagree with yi then
Mi = (r i + 1 mod 2)
for j = 1 : m do Lj = ∑ i′εBj (Mi′ mod 2)
if all Lj = 0 or I = I max then Finished
I = I + 1
We have Implemented Bit flip decoder & belief propagation decoder algorithm on Xilinx Spartan
3E starter Board .The output of the decoder is shown on PC (computer) HyperTerminal. Figure
1 shows the experimental setup & figure 2 shows
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1834
ISSN 2229-5518
Decoder codeword on PC HyperTerminal the hardware for hardware implementation of the
decoder algorithm. The results of bit flip decoder
& belief propagation algorithm is compared in
terms of number of error recovered. The results show that belief propagation algorithm has a better error correction capability than the bit flip decoder.
Synthesis is done using the High level synthesis
& Xilinx ISE 13.2, built in synthesis tool. Table 1,
shows synthesis report which gives information of the Slice flip flops, LUTs usage, device utilization constraint, timing summary. Figure 3, shows the simulation results which show the working of the decoder. The reset & clock activates the other signals ,when reset is ‘1’ ,the decoder is in Idle condition, when reset’0’
,decoder operation starts on the clock tick event. Figure1 shows the H-matrix used for decoding& the output Z required decoded codeword
Figure 1: ExperimeIntal seJtup SER
Table 1: Xilinx device utilization summary
The decoding performance of belief propagation and bit flip algorithms in recovering original codeword, shown in the table Table 2.
Figure 2: Decoded codeword on serial Port
HyperTerminal
FPGA implementation of the decoder is done for large H matrix & results are simulated using High level Simulator. The design is synthesized
and implemented using Xilinx ISE 13.2. The Xilinx High level synthesis Tool converts the High level c language code into HDL. The
Table 2: Comparison of Number of errors recovered by Belief propagation & Bit flip Algorithm
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 4, Issue 12, December-2013 1835
ISSN 2229-5518
Reset
Clock
H-matrix (4, 8)
Z-Decoded code word
Figure 3: Simulation Result for H-matrix 4X8 on Modelsim simulator
The decoder was designed using High level
[3]. D.I.C. MacKay, and R.M. Neal, "Near
Shannon limit performance of low density parity check codes," lEE Electronics Letters, vol. 32, pp.
IJSER
Language & synthesized using Xilinx High level
synthesis tool to Implemented on Hardware. The simulation results shows how the clock & reset signal controls the decoder operation. The implementation of self checking system on FPGA for belief propagation algorithm has resulted in correction & detection of errors on large size codeword. Belief propagation & bit flip algorithm results are compared & verified using Simulation & implementation. From the performance parameter it is concluded that Belief propagation decoding algorithm improves the performance of system in terms of error correction rate. Error recovery rate of belief propagation algorithm is better than bit flip decoding algorithm. The detailed decoder design and architecture are presented and the results are explained.
[1]. Susmitha Remmanapudi and Balaji Bandaru, “An FPGA Implementation of low density Parity-check codes construction & Decoding”Devices ,Circuits & Systems International conference,pp .216-220,April 2012
[2]. R. Gallager, Low-Density Parity-Check
Codes. Cambridge, M.I.T,Press, 1963.
1645-1655, Aug. 1996.
[4]. F. Kschischang, B. Frey, and H.A. Loeliger, "Factor Graphs and the Sum Product Algorithm," IEEE Trans. Inform. Theory, vol. 47, pp. 498-519, Feb, 2001.
[5].C. Berrou, A. Glavieux, and P. Thitimajshima, "Near Shannon limit error- correcting coding and decoding: Turbo codes," Proceedings of the IEEE International Conference on Communications, Geneva, Switzerland, pp. 1064-1070, 1993.
[6]. S.Y. Chung, G. D. 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 Trans. Inform. Theory, vol.
47, pp. 638-656, Feb. 2001.
[7]. R. Lucas, M. P. C. Fossorier, Y. Kou and S. Lin 2000 Iterative decoding of one-step majority logic decodable codes based on belief propagation. IEEE Transaction communication,
48: 931–937
IJSER © 2013 http://www.ijser.org