Polarization is an unprecedented coding technique in that it not only achieves channel capacity, but also does so at a faster speed of convergence than any other technique. This speed is measured by the "scaling exponent" and its importance is three-fold. Firstly, estimating the scaling exponent is challenging and demands a deeper understanding of the dynamics of communication channels. Secondly, scaling exponents serve as a benchmark for different variants of polar codes that helps us select the proper variant for real-life applications. Thirdly, the need to optimize for the scaling exponent sheds light on how to reinforce the design of polar code. In this paper, we generalize the binary erasure channel (BEC), the simplest communication channel and the protagonist of many polar code studies, to the "tetrahedral erasure channel" (TEC). We then invoke Mori-Tanaka’s 2 × 2 matrix over 𝔽_4 to construct polar codes over TEC. Our main contribution is showing that the dynamic of TECs converges to an almost-one-parameter family of channels, which then leads to an upper bound of 3.328 on the scaling exponent. This is the first non-binary matrix whose scaling exponent is upper-bounded. It also polarizes BEC faster than all known binary matrices up to 23 × 23 in size. Our result indicates that expanding the alphabet is a more effective and practical alternative to enlarging the matrix in order to achieve faster polarization.

Over any discrete memoryless channel, we offer error correction codes such that: for one, their block error probabilities and code rates scale like random codes'; and for two, their encoding and decoding complexities scale like polar codes'. Quantitatively, for any constants π, ρ > 0 π +2ρπ) , code rate N-ρless than the Shannon capacity, and encoding and decoding complexity O(N log N}) per code block. The core theme is to incorporate polar coding (which limits the complexity to polar's realm) with large, random, dynamic kernels (which boosts the performance to random's realm). The putative codes are optimal in the following manner: Should π +2ρ>1 , no such codes exist over generic channels regardless of complexity.

A pruned variant of polar coding is proposed for binary erasure channel (BEC). Fix any BEC. For sufficiently small ε > 0, we construct a series of capacity achieving codes with block length N = ε-4.9, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. The given per-bit complexity bC is log-logarithmic in N, in Capacity - R, and in P. Beyond BEC, there is a generalization: Fix a prime q and fix a symmetric, q-ary-input, discrete-output memoryless channel. For sufficiently small ε > 0, we construct a series of error correction codes with block length N = ε-constant, code rate R = Capacity - O(ε), block error probability P = ε, and encoding and decoding time complexity bC = O(log|log ε|) per information bit. Over general channels, this family of codes has the lowest per-bit time complexity among all capacity-achieving codes known to date.

For general exact repair regenerating codes, the optimal trade-offs between the storage size and repair bandwidth remain undetermined. Various outer bounds and partial results have been proposed. Using a simple chain rule argument, we identify nonnegative differences between the functional repair and the exact repair outer bounds, and one of the differences is then bounded from below by the repair data of a shortened subcode. Our main result is a new outer bound for an exact repair regenerating code in terms of its shortened subcodes. In general, the new outer bound is implicit and depends on the choice of shortened subcodes. For the linear case, we obtain explicit bounds.

We study the problem of constructing balanced generator matrices for Reed-Solomon and Tamo-Barg codes. More specifically, we are interested in realizing generator matrices, for the full-length cyclic versions of these codes, where all rows have the same weight and the difference in weight between any columns is at most one. The results presented in this paper translate to computationally balanced encoding schemes, which can be appealing in distributed storage applications. Indeed, the balancedness of these generator matrices guarantees that the computation effort exerted by any storage node is essentially the same. In general, the framework presented can accommodate various values for the required row weight. We emphasize the possibility of constructing sparsest and balanced generator matrices for Reed-Solomon codes, i.e., each row is a minimum distance codeword. The number of storage nodes contacted once a message symbol is updated decreases with the row weight, so sparse constructions are appealing in that context. Results of similar flavor are presented for cyclic Tamo-Barg codes. In particular, we show that for a code with minimum distance d and locality r, a construction in which every row is of weight d+r-1 is possible. The constructions presented are deterministic and operate over the codes' original underlying finite field. As a result, efficient decoding from both errors and erasures is possible thanks to the plethora of efficient decoders available for the codes considered.

We extend the notion of locality from the Hamming metric to the rank and subspace metrics. Our main contribution is to construct a class of array codes with locality constraints in the rank metric. Our motivation for constructing such codes stems from the need to design codes for efficient data recovery from correlated and/or mixed (i.e., complete and partial) failures in distributed storage systems. Specifically, the proposed local rank-metric codes can recover locally from crisscross errors and erasures, which affect a limited number of rows and/or columns of the storage array. We also derive a Singlet-on-like upper bound on the minimum rank distance of (linear) codes with rank-locality constraints. Our proposed construction achieves this bound for a broad range of parameters. The construction builds upon Tamo and Barg's method for constructing locally repairable codes with optimal minimum Hamming distance. Finally, we construct a class of constant-dimension subspace codes (also known as Grassmannian codes) with locality constraints in the subspace metric. The key idea is to show that a Grassmannian code with locality can be easily constructed from a rank-metric code with locality by using the lifting method proposed by Silva et al. We present an application of such codes for distributed storage systems, wherein nodes are connected over a network that can introduce errors and erasures.

Network transfer and disk read are the most time consuming operations in the repair process for node failures in erasure-code-based distributed storage systems. Recent developments on Reed-Solomon codes, the most widely used erasure codes in practical storage systems, have shown that efficient repair schemes specifically tailored to these codes can significantly reduce the network bandwidth spent to recover single failures. However, the I/O cost, that is, the number of disk reads performed in these repair schemes remains largely unknown. We take the first step to address this gap in the literature by investigating the I/O costs of some existing repair schemes for full-length Reed-Solomon codes.

Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth. A naive repair approach would require for the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. Their key idea is to recover the erased symbol by collecting a sufficiently large number of its traces, each of which can be constructed from a number of traces of other symbols. We extend the trace collection technique to cope with two and three erasures.

Despite their exceptional error-correcting properties, Reed-Solomon (RS) codes have been overlooked in distributed storage applications due to the common belief that they have poor repair bandwidth: A naive repair approach would require the whole file to be reconstructed in order to recover a single erased codeword symbol. In a recent work, Guruswami and Wootters (STOC'16) proposed a single-erasure repair method for RS codes that achieves the optimal repair bandwidth amongst all linear encoding schemes. We extend their trace collection technique to cope with two erasures.

We construct balanced and sparse generator matrices for Tamo and Barg's Locally Recoverable Codes (LRCs). More specifically, for a cyclic Tamo-Barg code of length n, dimension k and locality r, we show how to deterministically construct a generator matrix where the number of nonzeros in any two columns differs by at most one, and where the weight of every row is d + r - 1, where d is the minimum distance of the code. Since LRCs are designed mainly for distributed storage systems, the results presented in this work provide a computationally balanced and efficient encoding scheme for these codes. The balanced property ensures that the computational effort exerted by any storage node is essentially the same, whilst the sparse property ensures that this effort is minimal. The work presented in this paper extends a similar result previously established for Reed-Solomon (RS) codes, where it is now known that any cyclic RS code possesses a generator matrix that is balanced as described, but is sparsest, meaning that each row has d nonzeros.

Codewords in array format find applications in disk storage where columns are stored on different disks in combination with row parity checks across disks that protect data against disk failures. The addition of global parities protects against sector failures on any of the disks while keeping storage overhead low. We construct sector-disk array codes that tolerate any combination of two disk failures and three sector failures with minimal overhead. The construction is the first for codes of this type that does not rely on exhaustive search.

We consider a simple multiple access network in which a destination node receives information from multiple sources via a set of relay nodes. Each relay node has access to a subset of the sources, and is connected to the destination by a unit capacity link. Arbitrary errors may be introduced by up to z of the relay nodes. We propose an efficient distributed error correction coding scheme, where the relay nodes encode independently such that the overall codewords received at the destination are codewords from a single Reed-Solomon code. We show that it achieves the full capacity region for up to three sources.

Multiplicative linear secret sharing schemes are the building blocks for multiparty computation protocols. Such schemes can be defined in terms of linear codes with an additional algebraic structure. We show that Reed-Muller codes have the required additional structure and we introduce a more general class of Reed-Muller type codes suitable for linear secret sharing and multiparty computation. The codes have highly structured generator and parity check matrices that can be used for very efficient implementations over the binary field.

Giulietti and Korchmáros presented new curves with the maximal number of points over a field of size$q^{6}$. Garcia, Güneri, and Stichtenoth extended the construction to curves that are maximal over fields of size$q^{2n}$, for odd$n \geq 3$. The generalized GK-curves have affine equations$x^{q}+x = y^{q+1}$and$y^{q^{2}}-y = z^{r}$, for$r=(q^{n}+1)/(q+1)$. We give a new proof for the maximality of the generalized GK-curves and we outline methods to efficiently obtain their two-point coordinate ring.

One-point codes on the Hermitian curve produce long codes with excellent parameters. Feng and Rao introduced a modified construction that improves the parameters while still using one-point divisors. A separate improvement of the parameters was introduced by Matthews considering the classical construction but with two-point divisors. Those two approaches are combined to describe an elementary construction of two-point improved codes. Upon analysis of their minimum distance and redundancy, it is observed that they improve on the previous constructions for a large range of designed distances.

The paper presents the vector decomposition problem (VDP) for m-torsion points on an elliptic curve. We prove that any elliptic curve for which the sufficient conditions hold is bound to be supersingular.

We determine the actual parameters for a class of one-point codes of length 64 and 65 over F/sub 8/ defined by Hansen and Stichtenoth (1990). Several codes have a minimum distance that exceeds the Feng-Rao bound. The codes with parameters [64,5,51], [64,10,42], [64,11,42], [64,12,40], [65,5,52], [65,10,43], [65,11,42], [65,12,41], and [65,13,40] are better than any known code.

We define an elementary family of lattices, from which we obtain a family of extended cyclic codes with coefficients in the modular integers. The first nontrivial subfamily is the family of quaternary Preparata codes. The family of dual codes coincides with the extended low-correlation sequences introduced by Kumar, Helleseth, and Calderbank (1995).

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.

We consider certain subcodes of generalized Reed-Muller (GRM) codes, which we call homogeneous generalized Reed-Muller (HRM) codes. In general, they have a much better minimum distance than the GRM codes. The parameters of HRM codes are related to those of projective Reed-Muller (PRM) codes. Unlike most PRM codes, punctured HRM codes are cyclic. Under the trace map, HRM codes map to binary codes. These are in general much larger than classical RM codes, for the same minimum distance.

We give a method to compute the complete weight distribution of translates of linear codes over Z/sub 4/. The method follows known ideas that have already been used successfully by others for Hamming weight distributions. For the particular case of quaternary Preparata codes, we obtain that the number of distinct complete weights for the dual Preparata codes and the number of distinct complete coset weight enumerators for the Preparata codes are both equal to ten, independent of the code length.

A general decoding method for linear codes is investigated for cyclic codes. The decoding consists of solving two systems of linear equations. All but four binary cyclic codes of length less than 63 can so be decoded up to their actual distance. A new family of codes is given for which the decoding needs only O(n/sup 2/) operations.>

A majority coset decoding (MCD) procedure that can be applied to an arbitrary geometric code is discussed. In general, the basic algorithm for decoding of algebraic-geometric codes does not correct up to the designed minimum distance. In MCD, a reduction step is added to the basic algorithm. In case the basic algorithm fails, a majority scheme is used to obtain an additional syndrome for the error vector. Thus a strictly smaller cost containing the error vector is obtained. In this way, the basic algorithm is applied to a decreasing chain of cosets and after finitely many steps the coset will be small enough for successful application of the basic algorithm.>

The basic algorithm for decoding of algebraic-geometric codes corrects up to (d/sub c/-1)2-g/2 errors, where d/sub c/ denotes the designed minimum distance of a code and g denotes the genus of a curve. The modified algorithm improves on this, but applies to a restricted class of codes. An extended modified algorithm that applies to all codes is formulated. It will correct up to (d/sub c/-1)/2-s errors, s is called the Clifford defect of a curve. For curves with g>or=1, this defect satisfies 0>