Comparing torus hypergraph erasure resilient code with a K-ring hypergraph code

2006-03-08

The torus hypergraph consist of vertices, sides (3-hyper edges) each connecting three vertices, and no edges. Each side can be regarded as a triangle. Now imagine regular triangles placed such that they cover a flat surface, which nearly forms a rectangle. Each vertex will have a degree of 6 (i.e. there are 6 triangles adjacent to each vertex). We can roll around the edges of the obtained nearly rectangular surface and form a torus. In such a torus we will have twice as much triangles as there are nodes. This torus leads to an erasure resilient code, where nodes are the source packets and the triangles are the redundant packets – the checksums of their three adjacent nodes. The below diagrams show similarly obtained torus with 18 nodes and a torus with 32 nodes:

[eps] 3x3 torus with 18 nodes and 36 sides

[eps] The same 18-nodes torus with the nodes placed along a circle

[eps] 4x4 torus with 32 nodes and 64 sides

[eps] The same 32-nodes torus with the nodes placed along a circle

Compared with the all-sides K-ring hypergraph the torus hypergraph does not however perform better:

[xls]

The performance index of the 18-nodes torus hypergraph is 31.6 and the performance index of the best all-sides K-ring hypergraph [ ch | us ] is 32.526.

Links:

- C++ program generating the torus hypergraph and computing its decoding performance [ cpp | txt | out ]

- Comparison on a relative scale of a 64-nodes torus with the 18-nodes all-sides K-ring [xls]

- MS Word version of this page [doc]

- The best all-sides K-ring hypergraph with 18 nodes compared with the best half/half K-ring hypergraph with 9 nodes [ ch | us ]

- Computing the packet recovery probabilities for 9 source packets and 18 redundant packets corresponding to hypergraphs with edges and sides (i.e. 3-hyperedges) [ ch | us ]

- Computing the packet recovery probabilities for random linear fountain codes, whose recovery probabilities depend on the number of excess packets only and do not become worse when the number of source packets increases [ ch | us ]

- Computing the curves of packet recovery probabilities (as functions of number of excess packets) for various numbers of source packets, when the redundant packets are XOR checksums of pairs of source packets and they are selected according to a K-ring graph [ ch | us ]

- Comparing the recovery probabilities of a Torus graph and a K-ring graph with 9 nodes and 18 edges [ ch | us ]

- Computing the recovery probabilities for 2500 random graphs with 18 edges [ ch | us ]

- Computing the recovery probabilities for a double cycle graph [ ch | us ]

- Computing the recovery probabilities for a torus graph [ ch | us ]

* * *