We present a list decoding algorithm for quaternary negacyclic codes over the Lee metric. To achieve this result, we use a Sudan-Guruswami type list decoding algorithm for Reed- Solomon codes over certain ring alphabets. Our decoding strategy for negacyclic codes over the ring ${\mathbb{Z}_4}$ combines the list decoding algorithm by Wu with the Gröbner basis approach for solving a key equation due to Byrne and Fitzpatrick.

In a user-private information retrieval (UPIR) scheme, a set of users collaborate to retrieve files from a database without revealing to observers which participant in the scheme requested the file. To achieve privacy, users retrieve files from the database in response to anonymous requests posted to message spaces; assuming that each message space can be accessed by a subset of the participants in the scheme. Privacy with respect to the database is easily achieved, but privacy with respect to coalitions of other users within the scheme is sensitive to the choice of incidence structure determining which users can access each message space. Earlier schemes were based on pairwise balanced designs and symmetric designs, and involved at most one step of message passing to retrieve a file. We propose a new class of UPIR schemes based on generalised quadrangles (GQs), which need up to two steps of message passing in each file retrieval. We introduce a new message passing protocol in which messages are encrypted. Even using this protocol, previously proposed schemes are compromised by finite coalitions of users. We construct a family of GQ-UPIR schemes which maintain privacy with high probability even when $$O(n^{1/2-\epsilon })$$ users collude, where n is the total number of users in the scheme. We also show that a UPIR scheme based on any family of generalised quadrangles is secure against coalitions of $$O(n^{1/4-\epsilon })$$ users.

We present a new algorithm for solving the closest vector problem. The algorithm is called the double-plane algorithm and it is an extension of Babai's nearest plane algorithm. The algorithm is an approximative algorithm, and the performance of the algorithm depends on the quality of the lattice basis. However, given a high quality basis, the algorithm achieves correctness for lattices of sufficiently low rank, and very low error-rates when correctness can no longer be achieved. The computational complexity of the double-plane algorithm is upper bounded by that of sphere decoding using the Schnorr-Euchner enumeration strategy, and the higher the rank of the lattice, the larger the gap between the complexities of these decoding algorithms.

By using the value assignment of Chen and Kløve we present new results on the pseudocodeword redundancy of binary linear codes. In particular, we give some upper bounds on the pseudoredundancies of certain codes with repeated coordinates and of certain shortened subcodes. We also investigate several kinds of k-dimensional binary codes and compute their exact pseudocodeword redundancy.

Revisiting an approach by Conway and Sloane we investigate a collection of optimal non-linear binary codes and represent them as (non-linear) codes over ℤ4. The Fourier transform will be used in order to analyze these codes, which leads to a new algebraic representation involving subgroups of the group of units in a certain ring. One of our results is a new representation of Best's (10, 40, 4) code as a coset of a subgroup in the group of invertible elements of the group ring ℤ4[ℤ5]. This yields a particularly simple algebraic decoding algorithm for this code. The technique at hand is further applied to analyze Julin's (12, 144, 4) code and the (12, 24, 12) Hadamard code. It can also be used in order to construct a (non-optimal) binary (14, 56, 6) code.

We present a notion of generalized Frobenius extension for finite rings, and study related trace functions. Then we show applications of such extensions for algebraic coding theory.

A framework for linear-programming (LP) decoding of nonbinary linear codes over rings is developed. This framework facilitates LP-based reception for coded modulation systems which use direct modulation mapping of coded symbols. It is proved that the resulting LP decoder has the ldquomaximum-likelihood (ML) certificaterdquo property. It is also shown that the decoder output is the lowest cost pseudocodeword. Equivalence between pseudocodewords of the linear program and pseudocodewords of graph covers is proved. It is also proved that if the modulator-channel combination satisfies a particular symmetry condition, the codeword error rate performance is independent of the transmitted codeword. Two alternative polytopes for use with LP decoding are studied, and it is shown that for many classes of codes these polytopes yield a complexity advantage for decoding. These polytope representations lead to polynomial-time decoders for a wide variety of classical nonbinary linear codes. LP decoding performance is illustrated for ternary Golay code with ternary phase-shift keying (PSK) modulation over additive white Gaussian noise (AWGN), and in this case it is shown that the performance of the LP decoder is comparable to codeword-error-rate-optimum hard-decision-based decoding. LP decoding is also simulated for medium-length ternary and quaternary low-density parity-check (LDPC) codes with corresponding PSK modulations over AWGN.

In previous work, we demonstrated how decoding of a non-binary linear code could be formulated as a linear-programming problem. In this paper, we study different polytopes for use with linear-programming decoding, and show that for many classes of codes these polytopes yield a complexity advantage for decoding. These representations lead to polynomial-time decoders for a wide variety of classical non-binary linear codes.

This correspondence revisits the idea of constructing a binary [mn,mk] code from an [n,k] code over F/sub 2//sup m/ by concatenating the code with a suitable basis representation of F/sub 2//sup m/ over F/sub 2/. We construct two nonequivalent examples of doubly even self-dual binary codes of length 160 which turn out to be of minimum distance 24. This improves the lower bound for this class of codes, whereas the upper bound is given by 28. The construction at hand seems to be of interest beyond this particular example.

A new method is given to construct low-density parity check codes the graphs of which are of designed girth. We give examples to illustrate the new method, and also present performance diagrams that suggest that these codes are as good as random codes in low SNR, and preferable to random codes at higher SNR.

We use a generalized Gray isometry in order to construct a previously unknown nonlinear (96,2/sup 36/,24) code as the image of a Z/sub 8/-linear Hensel lift of the binary Golay code. The union of this code with a relevant coset yields a (96,2/sup 37/,24) code. We show that this code and some of its shortenings are better than the best (non)linear binary codes known so far. For instance, the best earlier known code of length 96 and minimum distance 24 had 2/sup 88/ words.

Using tensor product constructions for the first-order generalized Reed-Muller codes, we extend the well-established concept of the Gray isometry between (Z/sub 4/, /spl delta//sub L/) and (Z/sub 2//sup 2/, /spl delta//sub H/) to the context of finite chain rings. Our approach covers previous results by Carlet (see ibid., vol.44, p.1543-7, 1998), Constantinescu (see Probl. Pered. Inform., vol.33, no.3, p.22-8, 1997 and Ph.D. dissertation, Tech. Univ. Munchen, Munchen, Germany, 1995), Nechaev et al. (see Proc. IEEE Int. Symp. Information Theory and its Applications, p.31-4, 1996) and overlaps with Heise et al. (see Proc. ACCT 6, Pskov, Russia, p.123-9, 1998) and Honold et al. (see Proc. ACCT 6, Pskov, Russia, p.135-41, 1998). Applying the Gray isometry on Z/sub 9/ we obtain a previously unknown nonlinear ternary (36, 3/sup 12/, 15) code.

We analyze Z/sub 4/S- and Z/sub 9/-linear lifts of the binary [24, 12] and ternary [12, 6]-Golay code under different weight functions on the underlying ring, and present algebraic decoding schemes for these codes.

We present a method for lifting a decoding scheme for a linear code over Z/sub p/ to a decoding scheme for a linear code over Z/sub p/k and characterize the class of codes for which this kind of lifting works. Its interest lies in its great generality and efficiency.

We prove extended error-correcting capabilities of the quaternary Preparata codes. These are metrically reflected by a slight and simple modification of the Lee distance on Z/sub 4/: we change the weight of the element 2 to 4/3 and leave all remaining weights untouched.