Only a single example is known of a regenerating code with both small field size and efficient repair, and with parameters in a corner point on the cutset bound different from the MSR and MBR points. Here we present another such code, based on a vector space partition of a 9-dimensional binary space into 73 subspaces of dimension 3 that is strongly related to the projective plane PG(2, 8); the coding spaces of the code consist of 72 of the subspaces in the partition. The new storage code comes with an efficient repair algorithm that can be described in terms of the underlying geometry.

In some lattice-based cryptosystems, the encryption and decryption processes can be interpreted as a noisy communication channel. In this work, we focus on cryptosystems based on the ring learning with errors (RLWE) and module learning with errors (MLWE) problems, e.g. Kyber. We provide new coding schemes for the communication channel involved in these cryptosystems. For encoding we use an error-correction code (ECC) along with modulo Q pulse amplitude modulation (PAM) (for some fixed small prime power Q), and vector dequantization. For decoding we perform vector quantization followed by hard/soft decision decoding (HDD/SDD) for the ECC. This construction provides remarkable reduction in the decryption failure rate (DFR), compared to some earlier proposed coding schemes for the same bitrate. For example, in Kyber encryption scheme, we reduce the DFR from 2−174(uncoded) to 2−1325(using HDD) or 2−1414(using SDD).

Let ${{\mathcal{U}}_n}$ be the multiplicative group of order n in the splitting field ${{\mathbb{F}}_{{q^m}}}$ of xn− 1 over a finite field ${{\mathbb{F}}_q}$. Any map of the form x → cxtwith $c \in {{\mathcal{U}}_n}$ and t = qi, 0 ≤ i < m, is ${{\mathbb{F}}_q}$-linear on ${{\mathbb{F}}_{{q^m}}}$ and fixes ${{\mathcal{U}}_n}$ set-wise; maps of this type will be called standard. Occasionally there are other, non-standard ${{\mathbb{F}}_q}$-linear maps on ${{\mathbb{F}}_{{q^m}}}$ fixing ${{\mathcal{U}}_n}$ set-wise, and in that case we say that the pair (n, q) is non-standard. We show that an irreducible cyclic code of length n over ${{\mathbb{F}}_q}$ has “extra” permutation automorphisms (others than the standard permutations generated by the cyclic shift and the Frobenius mapping that every such code has) precisely when the pair (n, q) is non-standard; we refer to such irreducible cyclic codes as non-standard or NSIC-codes. In addition, we relate these concepts to that of a non-standard linear recurring sequence subgroup as investigated in a sequence of papers by Brison and Nogueira. We present several families of NSIC-codes, and two constructions called “lifting” and “extension” to create new NSIC-codes from existing ones. We show that all NSIC-codes of dimension two can be obtained in this way, thus completing the classification for this case started by Brison and Nogueira.

Let G be a finite abelian group. If f : G → C is a nonzero function with Fourier transform f, the Donoho-Stark uncertainty principle states that |supp(f)||supp(f̂)| ≥ |G|. The purpose of this paper is twofold. First, we present the shift bound for abelian codes with a streamlined proof. Second, we use the shifting technique to prove a generalization and a sharpening of the Donoho-Stark uncertainty principle. In particular, if f : G → F is a non-zero function from G to a field F, and if f has a Fourier transform f̂, the sharpened uncertainty principle states that |supp(f)||supp(f̂)| ≥ |G|+|supp(f)|-|H(supp(f))|, where H(supp(f)) is the stabilizer of supp(f) in G.

We present a method to increase the dynamical range of a Residue Number System (RNS) by adding virtual RNS layers on top of the original RNS, where the required modular arithmetic for a modulus on any non-bottom layer is implemented by means of an RNS Montgomery multiplication algorithm that uses the RNS on the layer below. As a result, the actual arithmetic is deferred to the bottom layer. The multiplication algorithm that we use is based on an algorithm by Bajard and Imbert, extended to work with pseudo-residues (remainders with a larger range than the modulus). The resulting Recursive Residue Number System (RRNS) can be used to implement modular addition, multiplication, and multiply-and-accumulate for very large (2000+ bits) moduli, using only modular operations for small (for example 8-bits) moduli. A hardware implementation of this method allows for massive parallelization. Our method can be applied in cryptographic algorithms such as RSA to realize modular exponentiation with a large (2048-bit, or even 4096-bit) modulus. Due to the use of full RNS Montgomery algorithms, the system does not involve any carries, therefore cryptographic attacks that exploit carries cannot be applied. A full version of this paper is accessible at: http://www.arxiv.org/abs/1801.07561

The newly presented (k + m, k) Hadamard minimum storage regenerating (MSR) codes are a class of high rate storage codes with optimal repair property for single node failure. In this paper, we propose a new simple optimal repair strategy for (k + m, k) Hadamard MSR codes, which can considerably reduce the computation compared with the original one during the node repair.

The repair locality of a storage code is the maximum number of nodes that may be contacted during the repair of a failed node. Having small repair locality is desirable since it is proportional to the number of disk accesses required during a node repair, which for certain applications seems to be the main bottleneck. However, recent publications show that small repair locality comes with a penalty in terms of code distance or storage overhead, at least if exact repair is required. Here, we first review some of the recent work on possible (information-theoretical) trade-offs between repair locality and other code parameters like storage overhead (or, equivalently, coding rate) and code distance, which all assume the exact repair regime. Then, we present some new information theoretical lower bounds on the storage overhead as a function of the repair locality, valid for most common coding and repair models.

We present a precise characterization of linear functional-repair storage codes in terms of admissible states, with each state made up from a collection of vector spaces over some fixed finite field. To illustrate the usefulness of our characterization, we provide several applications. We first describe a simple construction of functional-repair storage codes for a family of code parameters meeting the cutset bound outside the MBR and MSR points; these codes are conjectured to have optimal rate with respect to their repair locality. Then, we employ our characterization to develop a construction method to obtain functional repair codes for given parameters using symmetry groups, which can be used both to find new codes and to improve known ones. As an example of the latter use, we describe a beautiful functional-repair storage code that was found by this method, with parameters belonging to the family investigated earlier, which can be specified in terms of only eight different vector spaces.

Distributed storage systems need to store data redundantly in order to provide some fault-tolerance and guarantee system reliability. Different coding techniques have been proposed to provide the required redundancy more efficiently than traditional replication schemes. However, compared to replication, coding techniques are less efficient for repairing lost redundancy, as they require retrieval of larger amounts of data from larger subsets of storage nodes. To mitigate these problems, several recent works have presented locally repairable codes designed to minimize the repair traffic and the number of nodes involved per repair. Unfortunately, existing methods often lead to codes where there is only one subset of nodes able to repair a piece of lost data, limiting the local repairability to the availability of the nodes in this subset. In this paper, we present a new family of locally repairable codes that allows different trade-offs between the number of contacted nodes per repair, and the number of different subsets of nodes that enable this repair. We show that slightly increasing the number of contacted nodes per repair allows to have repair alternatives, which in turn increases the probability of being able to perform efficient repairs. Finally, we present pg-BLRC, an explicit construction of locally repairable codes with multiple repair alternatives, constructed from partial geometries, in particular from Generalized Quadrangles. We show how these codes can achieve practical lengths and high rates, while requiring a small number of nodes per repair, and providing multiple repair alternatives.

In this paper, we study ternary monomial functions of the formf(x) = Trn(axd), wherexisin \BBF3nandTrn: \BBF3nrarr \BBF3is the absolute trace function. Using a lemma of Hou, Stickelberger's theorem on Gauss sums, and certain ternary weight inequalities, we show that certain ternary monomial functions arising in the 2006IEEE Transactions on Information Theorypaper (vol. 52, pp. 2018-2032, 2006) are weakly regular bent, thus settling a conjecture of Helleseth and Kholosha. We also prove that the Coulter-Matthews bent functions are weakly regular.

We give recursive constructions, valid for any field, of [n,k] codes capable of correcting a (wrap-around) burst of n - k erasures.

Recently there has been interest in the construction of small parity-check sets for iterative decoding of the Hamming code with the property that each uncorrectable (or stopping) set of size three is the support of a codeword and hence uncorrectable anyway. Here we reformulate and generalize the problem and improve on this construction. We show that a parity-check collection that corrects all correctable erasure patterns of size m for the Hamming code with codimension r provides, in fact, for all codes of codimension r a corresponding "generic" parity-check collection with this property. This leads in a natural way to a necessary and sufficient condition for such generic parity-check collections. We use this condition to construct a generic parity-check collection for codes of codimension r correcting all correctable erasure patterns of size at most m, for all r and mlesr, thus generalizing the known construction for m=3. Then we discuss optimality of our construction and show that it can be improved for mges3 and r large enough. Finally, we discuss some directions for further research

A generic (r,m)-erasure correcting set is a collection of vectors in F2rwhich can be used to generate, for each binary linear code of codimension r, a collection of parity check equations that enables iterative decoding of all correctable erasure patterns of size at most m. That is to say, the only stopping sets of size at most m for the generated parity check equations are the erasure patterns for which there is more than one manner to fill in the erasures to obtain a codeword. We give an explicit construction of generic (r,m)-erasure correcting sets of cardinality Sigmai=0m-1(ir-1). Using a random-coding-like argument, we show that for fixed m, the minimum size of a generic (r,m)-erasure correcting set is linear in r

In this article, the computation of the entropy rate H(y) of a binary-valued stochastic process (Y/sub 1/, Y/sub 2/,...) which is a function of a stationary, time-invariant and irreducible Markov chain (X/sub 1/, X/sub 2/,..) is considered. The central idea of this article is to replace the summation over all words of length n by a summation over a complete set of prefixes (or prefixset for brevity). A prefixset W is a finite set of words (not necessarily of equal length) containing a unique prefix for each word of sufficient length. The method of prefixsets is of interest beyond computing the entropy rate. For the problem of estimating the next state of a Markov chain from observed output sequences, we can precompute a prefixset W of these sequences and associate a unique estimate of the state with each of the elements of W. The method also has a strong relation with variable-to-fixed length (Tunstall) codes. It replaces the set of all words of a given length by a prefixset of "more typical" words, effectively balancing the contributions of all words in the bounds.

We consider lists of distinct q-ary addresses of length n. We wish that any b consecutive addresses in such a list agree in many positions. We give upper bounds on what can be achieved. Moreover, for each q and n, we give explicit constructions of address lists, among which is the conventional q-ary reflected Gray code, that attain these bounds for all b simultaneously. This work has applications in address retrieval on optical disc.

Modern packaging technology combined with densely populated assemblies requires efficient design for test features. In particular, modern memories with complex interfaces need to be addressed. This paper presents the details of a test technology that makes assembly test more efficient. The method is based on the implementation of XOR and XNOR gates to bypass a functional circuit. It is compatible yet complimentary to boundary-scan. Mathematical proof and simulation results show the effectiveness of this method for detection and diagnosis of assembly faults. Known alternatives are compared for test coverage.

Besides timing recovery and automatic gain control, data receivers often perform adaptive slope or bandwidth control. This note presents a set of maximum run-length constraints that facilitates the joint accomplishment of these three tasks. Simple polarity-bit codes that introduce these constraints are described. The study is of particular interest in digital magnetic recording.

Let S be a constrained system of finite type, described in terms of a labeled graph M of finite type. Furthermore, let C be an irreducible constrained system of finite type, consisting of the collection of possible code sequences of some finite-state-encodable, sliding-block-decodable modulation code for S. It is known that this code could then be obtained by state splitting, using a suitable approximate eigenvector. In this correspondence, we show that the collection of all approximate eigenvectors that could be used in such a construction of C contains a unique minimal element. Moreover, we show how to construct its linear span from knowledge of M and C only, thus providing a lower bound on the components of such vectors. For illustration we discuss an example showing that sometimes arbitrary large approximate eigenvectors are required to obtain the best code (in terms of decoding-window size) although a small vector is also available.

We introduce and investigate the class of bounded-delay-encodable block-decodable (BDB) codes. Several characterizations for this class of codes are given, and some construction methods, especially for one-symbol look-ahead BDB codes, are described. In another direction, we use our results to show the existence of a decision procedure for some basic coding problems.

We present a new technique to construct sliding-block modulation codes with a small decoding window. Our method, which involves both state splitting and look-ahead encoding, crucially depends on a new "local" construction method for bounded-delay codes. We apply our method to construct several new codes, all with a smaller decoding window than previously known codes for the same constraints at the same rate.>

We report on block-coding techniques for partial-response channels with transfer function (1/spl mnplus/D/sup m/), m=1, 2, ... . We consider various constructions of block codes with prescribed minimum Euclidean distance. Upper and lower bounds to the size of a code with minimum squared Euclidean distance greater than unity are furnished. A table is presented of cardinalities of codes of small length with prescribed minimum squared Euclidean distance.

Describes a (d,k)=(1,8) runlength-limited (RLL) rate 8/12 code with fixed codeword length 12. The code is block-decodable; a codeword can be decoded without knowledge of preceding or succeeding codewords. The code belongs to the class of bounded delay block-decodable (BDB) codes with one symbol (8 bits) look-ahead. Due to its format, this code is particularly attractive for use in combination with error-correcting codes such as Reed-Solomon codes over the finite field GF(2/sup 8/).>

A code is a collection of words or strings, not necessarily all of the same length, over come fixed alphabet. A relation is established between the insertion-and-deletion correcting capability of a code and its minimum distance for suitable Levenshtein-type distance measures.>

In digital recorders, the coded information is commonly grouped in large blocks, called frames. The authors concentrate on the frame synchronization problem of run-length-limited sequences, or (d, k) sequences. They commence with a brief description of (d, k)-constrained sequences, and proceed with the examination of the channel capacity. It is shown that for certain sync patterns, called repetitive-free sync patterns, the capacity can be formulated in a simple manner as it is solely a function of the (d, k) parameters and the length of the sync pattern. For each forbidden pattern and (d, k) constraints, methods for enumerating constrained sequences are given. Design considerations of schemes for encoding and decoding are addressed. Examples of prefix-synchronized (d, k) codes, based for the purpose of illustration on the sliding-block coding algorithm, are presented.>

The author describes the collection of all possible transfer functions of digital recursive filters that, when operating at p times the original data rate on runlength-limited (RLL) (d,k) bipolar data, can transform each allowable input signal into a bipolar output signal. For all integer values of p, d, and k with p>or=1 and 0>

The problem of appraising the spectral performance of codes based on a new algorithm for generating zero-disparity codewords presented by D.E. Knuth (1986) is addressed. In order to get some insight into the efficiency of Knuth's construction technique, the authors evaluate the spectral properties of its code streams. The structure of Knuth codes allows the derivation a simple expression for (an approximation to) the sum of variance of these codes. This quantity plays a key role in the spectral performance characterization of DC-balanced codes. The authors evaluate this expression and compare the sum variance of Knuth codes with the sum variance of the polarity bit codes for fixed redundancy. Under the premise that the sum variance can serve as a quantity to judge the width of the spectral notch, the authors conclude that codes based on Knuth's algorithm offer less spectral suppression than polarity bit codes with the same redundancy.>

Consider a shift register (SR) of length n and a collection of designated subsets of (0,1, . . ., n-1). The problem is how to add feedback to the SR such that the resulting linear feedback shift register (LFSR) exercises (almost) exhaustively each of the designated subsets and is of small period. Several previously known results for maximum-length LFSR are extended to more general LFSR, and in particular a previously known algorithm is simplified and extended. Applications to the problems of VLSI self-testing are discussed and illustrated.>

A new algorithm is presented for the fast computation of the Discrete Fourier Transform. This algorithm belongs to that class of recently proposed 2n-FFT's which present the same arithmetic complexity (the lowest among any previously published one). Moreover, this algorithm has the advantage of being performed "in-place", by repetitive use of a "butterfly"- type structure, without any data reordering inside the algorithm. Furthermore, it can easily be applied to real and real symmetric data with reduced arithmetic complexity by removing all redundancy in the algorithm.