Woven Graph Codes: Asymptotic Performances and Examples
Irina E. Bocharova, Boris D. Kudryashov, Rolf Johannesson, Victor Zyablov · 2008
Constructions of woven graph codes based on constituent block and convolutional codes are studied. It is shown that within the random ensemble of such codes based on s-partite, s-uniform hypergraphs, where s depends only on the code rate, there exist codes satisfying the Varshamov-Gilbert (VG) and the Costello lower bound on the minimum distance and the free distance, respectively. A connection between regular bipartite graphs and tailbiting codes is shown. Some examples of woven graph codes are presented. Among them an example of a rate Rwg = 1/3 woven graph code with dfree = 32 based on Heawood’s bipartite graph and containing n = 7 constituent rate R c = 2/3 convolutional codes with overall constraint lengths ν c = 5 is given. An encoding procedure for woven graph codes with complexity proportional to the number of constituent codes and their overall constraint length ν c is presented.