On optimization of wireless XOR erasure codes

In this paper we study the problem of optimizing linear erasure codes over GF(2) for single-hop wireless multicasting. We first present an algorithmic optimization technique which minimizes the number of transmissions given the knowledge of packets received by each of the receivers. We show that the algorithmic optimization technique is equivalent to an NP-complete Boolean constraint satisfaction problem (CSP), using Schaefer's dichotomy theorem. This makes the performance evaluation of such transmission network a difficult problem. We derive closed form expression and upper bound of minimum number of transmissions for restricted classes of the problem which sheds interesting insight about the behavior of optimal erasure codes over GF(2). We also show that the greedy algorithm on the mapped Boolean SAT problem outperforms previously proposed state-of-the art heuristic coding algorithms, and its performance is virtually similar to the optimal maximum distance separable (MDS) code for network parameters of practical interest.