The Clique Distribution In Powers Of Hypercubes

In the design of LDPC codes for 4G and 5G channel coding applications,the code distance constraint is a basic starting point,and the design of a check matrix with clear rules based on the code distance is the key to further improve the efficiency of coding and decoding,as well as the key to improve the performance of LDPC codes.Thus,the two most basic problems in coding theory are to find the values of A(n,d)and A(n,d,w),where A(n,d)and A(n,d,w)are respectively the size of the maximum binary code set and the maximum binary constant code set with length n and minimum Hamming distance d.Many famous scholars,such as Hamming and Gilbert-Varshamov,have conducted in-depth researches,but these two problems have not been completely solved.On this basis,this paper,from the perspective of graph theory,has done some related exploration for these two issues.First of all,this paper regards A(n,d)as the size of the maximum independent set of Qnd-1 which is the d-1th-power of n-dimensional hypercube.Thus,the problem of finding the value of A(n,d)is transformed into the problem of finding the maximum independent set of Qnd-1.In order to study the maximum independent set of Qnd,we analyzed the distribution and structural characteristics of its maximum clique from the perspective of structure.According to the structural characteristics of Qnd,we give a distance partition of Qn relative to the vertex(0,0,…,0)to obtain different distance sets,and then construct the largest subset of these distance sets satisfying a certain distance condition.On this basis,the number,structural characteristics and distribution of the maximum cliques in Qnd are completely obtained.Secondly,A(n,d,w)is viewed as the size of maximum independent set of Qnd-1,w which is the subgraph of Qnd induced by some vertices.In order to further study A(n,d,w),this paper gives the definition of Qnd,w for the first time,studies some of its basic properties,and obtains the regularity,vertex transitivity of Qnd,w and the structural characteristics of its maximum clique.Finally,using the relationship between the clique number and the independence number in the vertex transitive graph,an upper bound of A(n,d,w)is very concisely given for 3 ?d ?4.