Some nonlinear codes, such as Kerdock and Preparata codes, can be represented as binary images under the Gray map of linear codes over rings. This paper introduces MAP decoding of Kerdock and Preparata codes by working with their quaternary representation (linear codes over$\mathbb {Z}_{4}$) with the complexity of$\mathcal {O}(N^{2}\log _{2} N)$, where N is the code length in$\mathbb {Z}_{4}$. A sub-optimal bitwise APP decoder with good error-correcting performance and complexity of$\mathcal {O}(N\log _{2} N)$that is constructed using the decoder lifting technique is also introduced. This APP decoder extends upon the original lifting decoder by working with likelihoods instead of hard decisions and is not limited to Kerdock and Preparata code families. Simulations show that our novel decoders significantly outperform several popular decoders in terms of error rate.

Evaluating the block error rate of a digital communication system is usually done using the Monte Carlo (MC) simulation method. The main drawback of the Monte Carlo method is the need of a huge sample size for estimating low error rates. Other methods commonly used are the importance sampling technique and the quasi-analytical method. This paper introduces the metric star domain decoder model and shows that many practical decoders fall into this category. The main result is the introduction of a novel SNR-invariant quasi-analytical technique for estimating the block error rate of a communication link over the geodesic channel model (a generalization of a vast number of commonly used channels, including binary symmetric channel, BEC, and AWGN channel) with a metric star domain decoder used at the receiver. This technique outperforms the Monte Carlo and importance sampling methods in both accuracy and speed. It is shown that our quasi-analytical method is at least 103times faster than MC and 10 times faster than IS for the same accuracy.

We introduce a neighborhood-based data access model for distributed coded storage allocation. Storage nodes are connected in a generic network and data is accessed locally: a user accesses a randomly chosen storage node, which subsequently queries its neighborhood to recover the data object. We aim at finding an optimal allocation that minimizes the overall storage budget while ensuring recovery with probability one. We show that the problem reduces to finding the fractional dominating set of the underlying network. Furthermore, we develop a fully distributed algorithm where each storage node communicates only with its neighborhood in order to find its optimal storage allocation. The proposed algorithm is based upon the recently proposed proximal center method-an efficient dual decomposition based on accelerated dual gradient method. We show that our algorithm achieves a (1 + ε)-approximation ratio in O(dmax3/2/ε) iterations and per-node communications, where dmaxis the maximal degree across nodes. Simulations demonstrate the effectiveness of the algorithm.