Research Of Bounds On The Minimum Distance And Constructions Of Locally Repairable Codes

Locally Repairable Codes(LRCs)are a family of Erasure Codes(ECs),they can recover any coded symbol by at most r other coded symbols.Because of the locality of LRCs,LRCs become a research hotspot and have been widely applied in distributed storage system.This thesis is focused on researching the bounds on the minimum distance and constructions of LRCs,the main contributions and research contents are as follows:In terms of the parameters of LRCs,this thesis analyzes the performance of bounds on the minimum distance,dimension and locality and proposes the relationship among these three bounds.Firstly,the relationship of different bounds on the minimum distance with various of code length,dimensions and locality is proposed based on theoretic derivation and simulation analysis,it presents the performance comparison of different bounds given specific conditions.Secondly,this thesis analyzes Singleton-like bound,Cadambe and Mazumdar bound and two bounds on dimension introduced in existing literatures,and then presents the relationship and performance of these four bounds.Thirdly,the analysis of bounds on average locality and the performance comparison of two different bounds on average locality are given.In terms of bounds on the minimum distance of LRCs,this thesis proposes two bounds on the minimum distance based on Singleton-like bound.Firstly,this thesis proposes two new bounds on the minimum distance based on theoretic derivation,the first one applies to the LRCs which meet r(?)k and r|(n-k-(?)n/(r+1)(?)),the second one applies to the LRCs that meet r(?)k and r+1|n or nmod(r+1)?(k+(?)k/ r(?))mod(r+1)+1.Secondly,the relationship between new bounds and the existing bounds is analyzed based on theoretic derivation.Thirdly,the performance of new bounds is simulated and analyzed.Simulation results show that the performance of these two new bounds on the minimum distance within the scope of application is same as that of existing bounds on the minimum distance,these new bounds also expand the scope of some existing bounds.In terms of constructions of LRCs,this thesis proposes two construction algorithms of Binary Locally Repairable Codes(BLRCs)based on degree distributions.Through the analysis of BLRCs constructed by existing literatures,BLRCs constructed by existing literatures are irregular.And BLRCs with different degree distributions have different performance.Inspired by this,this thesis proposes constructions of BLRCs based on degree distributions.Firstly,according to whether the degree distributions of check nodes are given or not,this thesis proposes a construction algorithm with the given degree distributions of check nodes and a construction algorithm with the unknown degree distributions of check nodes given code length n,dimension k,the minimum distance d,locality r and the degree distributions of variable nodes.Secondly,this thesis proposes the modified algorithms for the two constructions,and the analysis shows that the modified algorithms can reduce the complexity of algorithms effectively.Thirdly,this thesis gives the recovery percentage of failure nodes of constructed BLRCs through simulations and analysis.Simulation results show that the proposed BLRCs with the given degree distributions of check nodes have the same performance with the existing codes,and the proposed BLRCs with the unknown degree distributions of check nodes have the better performance than the existing codes.