Decoding Algorithms For LDPC Codes And Their Use In Information Reconciliation

Low-Density Parity Check(LDPC)codes are first proposed by Gallager in the1960 s.With the the discovery of turbo codes the rediscovery of LDPC codes,the related research topic made a historic breakthrough in the 1990 s.For decoding of LDPC codes,the belief-propagation algorithm can perform very well,however,it is not suitable for implementation due to complexity issue.Then,the min-sum algorithm and its variants were proposed for ease of hardware implementation.Compared to the min-sum algorithm,the bit-flipping algorithm has significantly lower complexity,but perform worse in general.In recent years,how to make compromise between performance and complexity becomes a research hot.Information-theoretic security was first proposed by Shannon in 1949.But the problem of key distribution make the implement of information-theoretic security impossible.Therefore,Key generation techniques without need of distribution have become a reseach focus for implementing information-theoretic security.Among various steps for generating keys without key distribution,the information reconciliation is an important step for eliminating the key difference.For the purpose of information reconciliation,Cascade protocol was proposed,however,it requires many rounds of communications,which prohibit its use in some practical scenarioes.This dissertation focuses on the decoding algorithms for LDPC codes and their use on information reconciliation.The contribution can be summerized as follows:(1)The dissertation provides necessary analysis and simulation results for two kinds of decoding algorithms for LDPC codes: belief-propagation algorithms(such as standard belief-propagation algorithm,min-sum algorithm and its improved variants)and bit-flip algorithms(such as WBF algorithm,IMWBF algorithm,GDBF/NGDBF algorithm,PWBF algorithm).(2)The dissertation proposes a P-NGDBF algorithm and its adaptive implementation as the improvement for the M-NGDBF algoritm.Simulations show that the P-NGDBF algorithm has better decoding performance and its adaptive version can perform very close to the min-sum algorithm.(3)The dissertation shows how to evaluate the information reconciliation in both performance and complexity.In particular,the performance of Cascade protocal is extensitvely studied.(4)An new information reconciliation protocol based on RCPIRA code is proposed.Simulation results show that the proposed protocol can ensure high accuracy of increpancy between reconciliated keys,the number of communication rounds can be effectively reduced.