Fair-density parity-check (FDPC) codes have been recently introduced demonstrating improved performance compared to low-density parity-check (LDPC) codes standardized in 5G systems particularly in high-rate regimes. In this paper, we introduce a layered normalized min-sum (LNMS) message-passing decoding algorithm for the FDPC codes. We also introduce a syndrome-guided bit flipping (SGBF) method to enhance the error-correction performance of our proposed decoder. The LNMS decoder leverages conflict graph coloring for efficient layered scheduling, enabling faster convergence by grouping non-conflicting check nodes and updating variable nodes immediately after each layer. In the event of decoding failure, the SGBF method is activated, utilizing a novel reliability metric that combines log-likelihood ratio (LLR) magnitudes and syndrome-derived error counts to identify the least reliable bits. A set of candidate sequences is then generated by performing single-bit flips at these positions, with each candidate re-decoded via LNMS. The optimal candidate is selected based on the minimum syndrome weight. Extensive simulation results demonstrate the superiority of the proposed decoder. Numerical simulations on FDPC$(256,192)$ code with a bit-flipping set size of $T = 128$ and a maximum of $5$ iterations demonstrate that the proposed decoder achieves approximately a $0.5\,\mathrm{dB}$ coding gain over standalone LNMS decoding at a frame error rate (FER) of $10^{-3}$, while providing coding gains of $0.75-1.5\,\mathrm{dB}$ over other state-of-the-art codes including polar codes and 5G-LDPC codes at the same length and rate and also under belief propagation decoding.

We study the problem of transmission of information over classical-quantum (CQ) channels in the one-shot regime where the underlying codes are constrained to be shiftedgroup codes. Given a groupG, a group code of lengthnis a subgroup ofGn. In the achievability part, we introduce a new collection of input probability distributions that incorporates the encoding homomorphism and the underlying channel law. Using a random coding argument, we characterize the performance of group codes in terms of hypothesis testing relative-entropic quantities. In the converse part, we establish bounds by leveraging a hypothesis testing-based approach. Furthermore, we apply the one-shot result to the asymptotic stationary memoryless setting, and establish a single-letter lower bound on thegroup capacityof a CQ channel. Moreover, we derive a matching upper bound on the asymptotic group capacity.

In real-world datasets, leveraging the low-rank and sparsity properties enables developing efficient algorithms across a diverse array of data-related tasks, including compression, compressed sensing, matrix completion, etc. Notably, these two properties often coexist in certain real-world datasets, especially in Boolean datasets and quantized real-valued datasets. To harness the advantages of low-rank and sparsity simultaneously, we adopt a technique inspired by compressed sensing and Boolean matrix completion. Our approach entails compressing a low-rank sparse Boolean matrix by performing inner product operations with a randomly generated Boolean matrix. We then propose a decoding algorithms based on message-passing techniques to recover the original matrix. Our experiments demonstrate superior recovery performance of our proposed algorithms compared to Boolean matrix completion, with equal measurement requirements.

We consider the problem of Multiple-Input SingleOutput (MISO) communication with limited feedback, where the transmitter relies on a limited number of bits associated with the channel state information (CSI), available at the receiver (CSIR) but not at the transmitter (no CSIT), sent via the feedback link. We demonstrate how character-polynomial (CP) codes, a class of analog subspace codes (also, referred to as Grassmann codes) can be used for the corresponding quantization problem in the Grassmann space. The proposed CP codebook-based precoding design allows for a smooth trade-off between the number of feedback bits and the beamforming gain, by simply adjusting the rate of the underlying CP code. We present a theoretical upper bound on the mean squared quantization error of the CP codebook, and utilize it to upper bound the resulting distortion as the normalized gap between the CP codebook beamforming gain and the baseline equal gain transmission (EGT) with perfect CSIT. We further show that the distortion vanishes asymptotically. The results are also confirmed via simulations for different types of fading models in the MISO system and various parameters.

In this paper, we propose a method for obtaining metric functions for each depth of the channel polarization tree through a process that we call polarization of the metric function. One of the major advantages of the proposed metric function is that it can be utilized in fast successive cancellation-based (FSC) and SC list-based (FSCL) decoders, i.e., decoders that opt to skip the so-called rate-1 and rate-0 nodes in the binary tree representation for significantly more efficient implementation. Furthermore, we relate the average and variance values of the polarized metric function of FSC-based decoders to the polarized channel capacity and polarized varentropy. By leveraging this observations, we introduce a pruning technique that keeps only the paths in the FSCL decoder whose metric values are close to the average value. As a result, our proposed technique significantly reduces the number of required sorting operations for FSCL-based decoding algorithms. For instance, for a highrate PAC (128,99) code, SCL decoding with a list size of 32 achieves error-correction performance comparable to the Fano algorithm. FSCL decoding requires visiting only 28 nodes of the polarization tree, significantly fewer than the 254 nodes required for conventional SCL decoding. Additionally, our method reduces the number of sorting operations by a factor of 3, further decreasing latency and complexity.

In this paper, we explore the design and analysis of regular bipartite graphs motivated by their application in lowdensity parity-check (LDPC) codes specifically with constrained girth and in the high-rate regime. We focus on the relation between the girth of the graph, and the size of the sets of variable and check nodes. We derive bounds on the size of the vertices in regular bipartite graphs, showing how the required number of check nodes grows with respect to the number of variable nodes as girth grows large. Furthermore, we present two constructions for bipartite graphs with girth$\mathcal{G}=8$; one based on a greedy construction of ($w_{c}, w_{r}$) -regular graphs, and another based on semi-regular graphs which have uniform column weight distribution with a sublinear number of check nodes. The second construction leverages sequences of integers without any length- 3 arithmetic progression and is asymptotically optimal while maintaining a girth of 8. Also, both constructions can offer sparse parity-check matrices for high-rate codes with medium-to-large block lengths. Our results solely focus on the graph-theoretic problem but can potentially contribute to the ongoing effort to design LDPC codes with high girth and minimum distance, specifically in high code rates.

We propose an efficient algorithm to find a ReedSolomon (RS) codeword at a distance within the covering radius of the code from any point in its ambient Hamming space. To the best of the authors' knowledge, this is the first attempt of its kind to solve the covering problem for RS codes. The proposed algorithm leverages off-the-shelf decoding methods for RS codes, including the Berlekamp-Welch algorithm for unique decoding and the Guruswami-Sudan algorithm for list decoding. We also present theoretical and numerical results on the capabilities of the proposed algorithm and, in particular, the average covering radius resulting from it. Our numerical results suggest that the overlapping Hamming spheres of radius close to the GuruswamiSudan decoding radius centered at the codewords cover most of the ambient Hamming space.

In this paper, we propose a method to obtain the optimal metric function at each depth of the polarization tree through a process we callpolarizationof the metric function. This polarization process generates an optimal metric at intermediate levels of the polarization tree, which can be applied infastsuccessive-cancellation-based (FSC) and SC list-based (FSCL) decoders—decoders that partially explore the binary tree representation. We prove that at each step of the polarization tree, the expected value of the metric function random variable is the mutual information of the corresponding channel, while its variance equals the varentropy of the channel—two parameters that are particularly relevant in finite block-length regimes. Additionally, we show that after polarization, the variances of the bit metrics approach zero for binary-input discrete memoryless channels (BI-DMCs). Moreover, we provide an estimate for calculating the variance of the binary-input additive white Gaussian noise (BI-AWGN) channel. We introduce a list-pruning strategy for FSCL decoding that retains only the paths whose metric values are close to the average. As a result, our method significantly reduces the number of required sorting operations in FSCL-based decoding algorithms. We also derive an upper bound, as a function of the polarized channel varentropy, on the probability that the distance between a bit-metric random variable and the bit-channel mutual information exceeds a given threshold. Leveraging this result, we further propose a varentropy-based list-pruning strategy for the SCL (VPSCL) decoding algorithm that adapts to the varentropy of the corresponding bit-channel. Our proposed pruning strategy also benefits stack decoding (VPStack) by discarding partial paths and avoiding unnecessary extensions.

This paper addresses the gradient coding and coded matrix multiplication problems in distributed optimization and coded computing. We present a computationally efficient coding method which overcomes the drawbacks of the Fractional Repetition Coding gradient coding method proposed by Tandon et al., and can also be leveraged by coded computing networks whose servers are of heterogeneous nature. Specifically, we propose a construction for fractional repetition gradient coding; while ensuring that the generator matrix remains close to perfectly balanced for any set of coding parameters, as well as a low complexity decoding step. The proposed binary encoding avoids operations over the real and complex numbers which inherently introduce numerical and rounding errors, thereby enabling accurate distributed encodings of the partial gradients. We then make connections between gradient coding and coded matrix multiplication. Specifically, we show that any gradient coding scheme can be extended to coded matrix multiplication. Furthermore, we show how the proposed binary gradient coding scheme can be used to construct two different coded matrix multiplication schemes, each achieving different trade-offs.

In this paper, we propose a new algorithm for the problem of string reconstruction from its substring composition multiset. Motivated by applications in polymer-based data storage for recovering strings from tandem mass-spectrometry sequencing, the proposed algorithm leverages the equivalent polynomial formulation of the problem which facilitates efficient parallel implementation. The computational complexity of the proposed reconstruction algorithm is upper bounded by$6.5n^{2}$finite field operations, where the field size is upper bounded by$10n$, implying that the computational complexity is upper bounded by$6.5n^{2}(3.22+\log {n})$binary operations. Furthermore, it allows parallelization leading to$O(n \log n)$reconstruction latency. We characterize sufficient conditions for a length n binary string that guarantee the string’s reconstruction time complexity to be bounded polynomially. Moreover, the sufficient conditions on binary strings that guarantee reconstruction in polynomial time are more general than the conditions for the algorithm by Acharya et al. This is used to construct new codebooks of reconstruction codes that have efficient encoding procedures, and are larger, by at least a linear factor in size, compared to the previously best known construction by Pattabiraman et al., (2023).

Recently, a novel variation of polar codes known as polarization-adjusted convolutional (PAC) codes has been introduced by Arıkan. These codes significantly outperform conventional polar and convolutional codes, particularly for short codeword lengths, and are shown to operate very close to the optimal bounds. It has also been shown that if the rate profile of PAC codes does not adhere to certain polarized cutoff rate constraints, the computation complexity for their sequential decoding grows exponentially. In this paper, we address the converse problem, demonstrating that if the rate profile of a PAC code follows the polarized cutoff rate constraints, the required computations for its sequential decoding can be bounded with a distribution that follows a Pareto distribution. This serves as a guideline for the rate-profile design of PAC codes. For a high-rate PAC (1024,899) code, simulation results show that the PAC code with Fano decoder, when constructed based on the polarized cutoff rate constraints, achieves a coding gain of more than 0.75 dB at a frame error rate (FER) of 10−5compared to the state-of-the-art 5G polar and LDPC codes.

We introduce fair-density parity-check (FDPC) codes targeting high-rate applications. In particular, we start with a base parity-check matrix$H_{b}$of dimension$2\sqrt{n}\times n$, where$n$is the code block length, and the number of ones in each row and column of$H_{b}$is equal to$\sqrt{n}$and 2, respectively. We propose a deterministic combinatorial method for picking the base matrix$H_{b}$, assuming$n=4t^{2}$for some integer$t\geqslant 2$. We then extend this by obtaining permuted versions of$H_{b}$(e.g., via random permutations of its columns) and stacking them on top of each other leading to codes of dimension$k\geqslant n-2s\sqrt{n}+s$, for some$s\geqslant 2$, referred to as order-s FDPC codes. We propose methods to explicitly characterize and bound the weight distribution of the new codes and utilize them to derive union-type approximate upper bounds on their error probability under Maximum Likelihood (ML) decoding. For the binary erasure channel (BEC), we demonstrate that the approximate ML bound of FDPC codes closely follows the random coding upper bound (RCU) for a wide range of channel parameters. Also, remarkably, FDPC codes, under the low-complexity min-sum decoder, improve upon 5G-LDPC codes for transmission over the binary-input additive white Gaussian noise (B-AWGN) channel by almost 0.5dB (for$n=1024$, and rate = 0.878). Furthermore, we propose a new decoder as a combination of weighted min-sum message-passing (MP) decoding algorithm together with a new progressive list (PL) decoding component, referred to as the MP-PL decoder, to further boost the performance of FDPC codes. This paper opens new avenues for a fresh investigation of new code constructions and decoding algorithms in high-rate regimes suitable for ultra-high throughput (high-frequency/optical) applications.

Secret sharing is an instrumental tool for sharing secret keys in distributed systems. In a classical threshold setting, this involves a dealer who has a secret/key, a set of parties/users to which shares of the secret are sent, and a threshold on the number of users whose presence is needed in order to recover the secret. In secret sharing, secure links with no leakage are often assumed between the involved parties. However, when the users are nodes in a communication network and all the links are physical links, e.g., wireless, such assumptions are not valid anymore. In order to study this critical problem, we propose a statistical leakage model of secret sharing, where some noisy versions of all the secret shares might be independently leaked to an adversary. We then study the resilience of the seminal Shamir's secret sharing scheme with statistical leakage, and bound certain measures of security (i.e., semantic security, mutual information security), given other parameters of the system including the amount of leakage from each secret share. We show that for an extreme scenario of Shamir's scheme, in particular when the underlying field characteristic is 2, the security of each bit of the secret against leakage improves exponentially with the number of users. To the best of our knowledge, this is the first attempt towards understanding secret sharing under general statistical noisy leakage.

In this paper, we study the problem of constructing projective systematic authentication schemes based on binary linear codes. In systematic authentication, a tag for authentication is generated and then appended to the information, also referred to as the source, to be sent from the sender. Existing approaches to leverage projective constructions focus primarily on codes over large alphabets, and the projection is simply into one single symbol of the codeword. In this work, we extend the projective construction and propose a general projection process in which the source, which is mapped to a higher dimensional codeword in a given code, is first projected to a lower dimensional vector. The resulting vector is then masked to generate the tag. To showcase the new method, we focus on leveraging binary linear codes and, in particular, Reed-Muller (RM) codes for the proposed projective construction. More specifically, we propose systematic authentication schemes based on RM codes, referred to as RM-A-codes. We provide analytical results for probabilities of deception, widely considered as the main metrics to evaluate the performance of authentication systems. Through our analysis, we discover and discuss explicit connections between the probabilities of deception and various properties of RM codes.

In a classical wiretap channel setting, Alice communicates with Bob through a main communication channel, while her transmission also reaches an eavesdropper Eve through a wiretap channel. In this paper, we consider a general class of polar secrecy codes for wiretap channels and study their finite-length performance. In particular, bounds on the normalized mutual information security (MIS) leakage, a fundamental measure of secrecy in information-theoretic security frameworks, are presented for polar secrecy codes. The bounds are utilized to characterize the finite-length scaling behavior of polar secrecy codes, where scaling here refers to the non-asymptotic behavior of both the gap to the secrecy capacity as well as the MIS leakage. Furthermore, the bounds are shown to facilitate characterizing numerical bounds on the secrecy guarantees of polar secrecy codes in finite block lengths of practical relevance, where directly calculating the MIS leakage is in general infeasible.

A subspace code is defined as a collection of subspaces of an ambient vector space, where each information-encoding codeword is a subspace. This paper studies a class of spatial sensing problems, notably direction of arrival (DoA) estimation using multisensor arrays, from a novel subspace coding perspective. Specifically, we demonstrate how a canonical (passive) sensing model can be mapped into a subspace coding problem, with the sensing operation defining a unique structure for the subspace codewords. We introduce the concept of sensing subspace codes following this structure, and show how these codes can be controlled by judiciously designing the sensor array geometry. We further present a construction of sensing subspace codes leveraging a certain class of Golomb rulers that achieve near-optimal minimum codeword distance. These designs inspire novel noise-robust sparse array geometries achieving high angular resolution. We also prove that codes corresponding to conventional uniform linear arrays are suboptimal in this regard. This work is the first to establish connections between subspace coding and spatial sensing, with the aim of leveraging insights and methodologies in one field to tackle challenging problems in the other.

We study the one-shot channel coding problem over classical and classical-quantum channels, where the underlying codes are constrained to be group codes. In the achievability part, we introduce a new distribution that incorporates the encoding homomorphism and the underlying channel law. Using a random coding argument, we characterize the performance in terms of hypothesis testing relative-entropies. In the converse part, we es-tablish bounds by leveraging a hypothesis testing-based approach. Further we apply the one-shot result to the asymptotic use case and establish the group capacities for both channels.

We propose efficient minimum-distance decoding and list-decoding algorithms for a certain class of analog subspace codes, referred to as character-polynomial (CP) codes, recently introduced by Soleymani and the second author. In particular, a CP code without its character can be viewed as a subcode of a Reed-Solomon (RS) code, where a certain subset of the coefficients of the message polynomial is set to zeros. We then demonstrate how classical decoding methods, including list decoders, for RS codes can be leveraged for decoding CP codes. For instance, it is shown that, in almost all cases, the list decoder behaves as a unique decoder. We also present a probabilistic analysis of the improvements in list decoding of CP codes when leveraging their certain structure as subcodes of RS codes.

Distributed computing has attracted significant recent attention for speeding up large-scale computations by disseminating computational jobs from a central master node across several worker nodes/servers. However, worker nodes are often untrusted and can also collude to gain unauthorized access to sensitive data. Hence, sharing sensitive data with them raises data privacy concerns. Coded computing has emerged as a promising framework for speeding up distributed computing and can be also adapted to address security and privacy concerns utilizing tools from secret sharing and multi-party computing. However, ensuring perfect information-theoretic privacy imposes a strict threshold on the maximum number of colluding workers the protocol can tolerate and, also, necessitates quantizing/mapping data to finite fields. Differential privacy is a widely accepted practical measure to capture the privacy leakage of the shared data. The mainstream approach is then to add perturbations to the data via randomized mechanisms. In this paper, we revisit coded computing, and especially when it is adapted to handle real-valued data, and analyze the privacy guarantees through the lens of differential privacy in terms of the (ϵ,δ)-differential privacy metric, for the first time in the literature. All the computations are done over the field of real/complex numbers and data privacy, in terms of differential privacy, is attained by adding noise terms in a certain structured way. In particular, the noise is added through the secret sharing mechanism (which can be, in principle, decoded and cancelled out at the master) as means of ensuring differential privacy. Furthermore, we propose a differentially private distributed matrix multiplication protocol for matrix multiplications that keeps the privacy of data in the worst adversarial case.

We consider the low rank matrix completion problem over finite fields. This problem has been extensively studied in the domain of real/complex numbers, however, to the best of authors’ knowledge, there exists merely one efficient algorithm to tackle the problem in the binary field, due to Saunderson et al. [1]. In this paper, we improve upon the theoretical guarantees for the algorithm provided in [1]. Furthermore, we formulate a new graphical model for the matrix completion problem over the finite field of size q, ${\mathbb{F}_q}$, and present a message passing (MP) based approach to solve this problem. The proposed algorithm is the first one for the considered matrix completion problem over finite fields of arbitrary size. Our proposed method has a significantly lower computational complexity, reducing it from O(n2r+3) in [1] down to O(n2) (where, the underlying matrix has dimension n × n and r denotes its rank), while also improving the performance.

In this paper, we study the quantitative group testing problem, also known as the heavy hitter detection problem and the coin weighing problem, in a non-adaptive setting. In this problem, the aim is to recover k defective items from a group of n items with the smallest possible number of quantitative/additive tests, where each such test returns the number of defective items participating in the test. In the non-adaptive setting, that we study in this paper, all tests are designed at once and can be, in principle, run in parallel. We establish a novel construction method for designing non-adaptive test matrices with a nested structure inspired by the Plotkin concatenation in the coding theory literature. Our proposed algorithm identifies k defective items among the collection of n items with high probability using $k(1 + o(1))\log \left( {\frac{n}{k}} \right)$ non-adaptive tests in the sub-linear regime of k = o(n). Furthermore, our analysis demonstrates that the probability of decoding failure approaches zero exponentially in k as k, n → ∞. Our approach outperforms existing state-of-the-art methods for designing non-adaptive test schemes with efficient decoders for the quantitative group testing problem in terms of the required number of measurements.

We consider vehicular networking scenarios where existing vehicle-to-vehicle (V2V) links can be leveraged for an effective uploading of large-size data to the network. In particular, we consider a group of vehicles where one vehicle can be designated as the leader and other follower vehicles can offload their data to the leader vehicle or directly upload it to the base station (or a combination of the two). In our proposed framework, the leader vehicle is responsible to receive the data from other vehicles and to process it in order to remove the redundancy before uploading it to the base station. We present a mathematical framework of the considered network. Next, we formulate and solve an optimization problem for selecting the leader vehicle as well as determining the portions of data from other follower vehicles to be offloaded to the leader to take advantage of V2V links in the vehicular network. We also perform simulations to confirm our findings and to compare it with two other alternatives: (1) the follower vehicles offload all their data to the leader vehicle (who will then upload it to the network), and (2) the follower vehicles all upload it directly to the base station. Our numerical results show the superiority of the proposed approach in comparison with these alternatives.

In general, the generator matrix sparsity is a critical factor in determining the encoding complexity of a linear code. Further, certain applications, e.g., distributed crowdsourcing schemes utilizing linear codes, require most or even all the columns of the generator matrix to have some degree of sparsity. In this paper, we leverage polar codes and the well-established channel polarization to design capacity-achieving codes with a certain constraint on the weights of all the columns in the generator matrix (GM) while having a low-complexity decoding algorithm. We first show that given a binary-input memoryless symmetric (BMS) channel$W$and a constant$s \in (0, 1]$, there exists a polarization kernel such that the corresponding polar code is capacity-achieving with the rate of polarization$s/2$, and the GM column weights being bounded from above by$N^{s}$. To improve the sparsity versus error rate trade-off, we devise a column-splitting algorithm and two coding schemes for BEC and then for general BMS channels. The polar-based codes generated by the two schemes inherit several fundamental properties of polar codes with the original$2 \times 2$kernel including the decay in error probability, decoding complexity, and the capacity-achieving property. Furthermore, they demonstrate the additional property that their GM column weights are bounded from above sublinearly in$N$, while the original polar codes have some column weights that are linear in$N$. In particular, for any BEC and$\beta < 0.5$, the existence of a sequence of capacity-achieving polar-based codes where all the GM column weights are bounded from above by$N^{\lambda} $with$\lambda \approx 0.585$, and with the error probability bounded by${\mathcal {O}}(2^{-N^{\beta }})$under a decoder with complexity${\mathcal {O}}(N\log N)$, is shown. The existence of similar capacity-achieving polar-based codes with the same decoding complexity is shown for any BMS channel and$\beta < 0.5$with$\lambda \approx 0.631$.

Due to the surge of cloud-assisted AI services, the problem of designing resilient prediction serving systems that can effectively cope with stragglers and minimize response delays has attracted much interest. The common approach for tackling this problem is replication which assigns the same prediction task to multiple workers. This approach, however, is inefficient and incurs significant resource overheads. Hence, a learning-based approach known as parity model (ParM) has been recently proposed which learns models that can generate ``parities’’ for a group of predictions to reconstruct the predictions of the slow/failed workers. While this learning-based approach is more resource-efficient than replication, it is tailored to the specific model hosted by the cloud and is particularly suitable for a small number of queries (typically less than four) and tolerating very few stragglers (mostly one). Moreover, ParM does not handle Byzantine adversarial workers. We propose a different approach, named Approximate Coded Inference (ApproxIFER), that does not require training any parity models, hence it is agnostic to the model hosted by the cloud and can be readily applied to different data domains and model architectures. Compared with earlier works, ApproxIFER can handle a general number of stragglers and scales significantly better with the number of queries. Furthermore, ApproxIFER is robust against Byzantine workers. Our extensive experiments on a large number of datasets and model architectures show significant degraded mode accuracy improvement by up to 58% over ParM.

We present a low-complexity and low-latency decoding algorithm for a class of Reed-Muller (RM) subcodes that are defined based on the product of smaller RM codes. More specifically, the input sequence is shaped as a multi-dimensional array, and the encoding over each dimension is done separately via a smaller RM encoder. Similarly, the decoding is performed over each dimension via a low-complexity decoder for smaller RM codes. The proposed construction is of particular interest to low-capacity channels that are relevant to emerging low-rate communication scenarios. We present an efficient soft-input soft-output (SISO) iterative decoding algorithm for the product of RM codes and demonstrate its superiority compared to hard decoding over RM code components. The proposed coding scheme has decoding (as well as encoding) complexity of ${\mathcal{O}}(n\log n)$ and latency of ${\mathcal{O}}(\log n)$ for blocklength n. This research renders a general framework toward efficient decoding of RM codes.

In this work, we propose a method for speeding up linear regression distributively, while ensuring security. We leverage randomized sketching techniques, and improve straggler resilience in asynchronous systems. Specifically, we apply a random orthonormal matrix and then subsample in blocks, to simultaneously secure the information and reduce the dimension of the regression problem. In our setup, the transformation corresponds to an encoded encryption in an approximate gradient coding scheme, and the subsampling corresponds to the responses of the non-straggling workers; in a centralized coded computing network. We focus on the special case of the Subsampled Randomized Hadamard Transform, which we generalize to block sampling; and discuss how it can be used to secure the data.

We consider the problem of binary string reconstruction from the multiset of its substring compositions, i.e., referred to as the substring composition multiset, first introduced and studied by Acharya et al. We introduce a new algorithm for the problem of string reconstruction from its substring composition multiset which relies on the algebraic properties of the equivalent bivariate polynomial formulation of the problem. We then characterize specific algebraic conditions for the binary string to be reconstructed that guarantee the algorithm does not require any backtracking through the reconstruction, and, consequently, the time complexity is bounded polynomially. More specifically, in the case of no backtracking, our algorithm has a time complexity of O(n2) in practice, compared to the algorithm by Acharya et al., which has a time complexity of O(n2logn), where n is the length of the binary string. Furthermore, it is shown that larger sets of binary strings are uniquely reconstructable by the new algorithm and without the need for backtracking leading to codebooks of reconstruction codes that are larger, by a linear factor in size, compared to the previously known construction by Pattabiraman et al., while having O(n2) practical reconstruction complexity.

Let A(n, d) denote the maximum number of code-words in a binary code of length n and minimum Hamming distance d. Deriving upper and lower bounds on A(n, d) has been a subject for extensive research in coding theory. In this paper, we examine upper and lower bounds on A(n, d) in the high-minimum distance regime, in particular, when $d = n/2 - \Theta (\sqrt n )$. We will first provide a lower bound based on a cyclic construction for codes of length n = 2m− 1 and show that $A\left({n,d = n/2 - {2^{c - 1}}\sqrt n }\right) \geq {n^c}$, where c is an integer with 1 ⩽ c ⩽ m/2 − 1. With a Fourier-analytic view of Delsarte’s linear program, novel upper bounds on $A(n,n/2 - \sqrt n ){\text{ and }}A(n,n/2 - 2\sqrt n )$ are obtained, and, to the best of the authors’ knowledge, are the first upper bounds scaling polynomially in n for the regime with $d = n/2 - \Theta (\sqrt n )$.

Constructing efficient low-rate error-correcting codes with low-complexity encoding and decoding has become increasingly important for applications involving ultra-low-power devices such as Internet-of-Things (IoT). To this end, schemes based on concatenating the state-of-the-art codes at moderate rates with repetition codes have emerged as practical solutions deployed in various standards. In this paper, we propose a novel mechanism for concatenating outer polar codes with inner repetition codes which we refer to as polar coded repetition. More specifically, we propose to transmit a slightly modified polar codeword by deviating from Arıkan’s standard$2 \times 2$Kernel in a certain number of polarization recursions at each repetition block. We show how this modification can improve the asymptotic achievable rate of the standard polar-repetition scheme, while ensuring that the overall encoding and decoding complexity is kept almost the same. The achievable rate is analyzed for the binary erasure channel (BEC) and additive white Gaussian noise (AWGN) channel. Moreover, we show that the finite-length performance of the polar coded repetition scheme under cyclic redundancy check (CRC) aided successive cancellation list (SCL) decoder over AWGN channel is better than the uncoded polar-repetition scheme at the cost of a slight increase in decoding complexity. We also compare the proposed scheme, in terms of performance and complexity, with other low-rate solution based on polar codes in the literature.

single,double We consider the critical problems of distributed computing and learning over data while keeping it private from the computational servers. The state-of-the-art approaches to this problem rely on quantizing the data into a finite field, so that the cryptographic approaches for secure multiparty computing can then be employed. These approaches, however, can result in substantial accuracy losses due to fixed-point representation of the data and computation overflows. To address these critical issues, we propose a novel algorithm to solve the privacy-preserving distributed computing problem when data is in the analog domain, e.g., the field of real/complex numbers. We characterize the privacy of the data from both information-theoretic and cryptographic perspectives, while establishing a connection between the two notions in the analog domain. More specifically, the well-known connection between the distinguishing security (DS) and the mutual information security (MIS) metrics is extended from the discrete domain to the analog domain. This is then utilized to bound the amount of information about the data leaked to the servers in our protocol, in terms of the DS metric, using well-known results on the capacity of single-input multiple-output (SIMO) channel with correlated noise. It is shown how the proposed framework can be adopted to do computation tasks when data is represented using floating-point numbers. We then show that this leads to a fundamental trade-off between the privacy level of data and accuracy of the result. By extending the setup to distributed learning, we show how to train a machine learning model using the proposed algorithm while keeping the data as well as the trained model private. Then numerical results are shown for experiments on several datasets. Furthermore, experimental advantages are shown comparing to fixed-point implementations over finite fields.

We provide a novel framework to study subspace codes for non-coherent communications in wireless networks. To this end, ananalog operator channelis defined with inputs and outputs being subspaces of${ \mathbb C}^{n}$. Then a certain distance is defined to capture the performance of subspace codes in terms of their capability to recover from interference and rank-deficiency of the network. We also study the robustness of the proposed model with respect to an additive noise. Furthermore, we propose a new approach to construct subspace codes in the analog domain, also regarded as Grassmann codes, by leveraging polynomial evaluations over finite fields together with characters associated to finite fields that map their elements to the unit circle in the complex plane. The constructed codes, referred to as character-polynomial (CP) codes, are shown to perform better comparing to other existing constructions of Grassmann codes in terms of the trade-off between the rate and the normalized minimum distance, for a wide range of values for$n$.

Concatenating the state-of-the-art codes at moderate rates with repetition codes has emerged as a practical solution deployed in various standards for ultra-low-power devices such as in Internet-of-Things (IoT) networks. In this paper, we propose a novel concatenation mechanism for such applications which need to operate at very low signal-to-noise ratio (SNR) regime. In the proposed scheme, the outer code is a hybrid polar code constructed in two stages, one with a binary kernel and another also with a binary kernel but applied over a binary extension field. The inner code is a non-binary multiplicative repetition code. This particular structure inherits low-complexity decoding structures of polar codes while enabling concatenation with an inner non-binary multiplicative repetition scheme. The decoding for the proposed scheme is done using cyclic redundancy check (CRC) aided successive cancellation list (SCL) decoder over additive white Gaussian noise (AWGN) and Rayleigh fading channels. Simulation results demonstrate that the proposed hybrid non-binary repeated polar code provides performance gain compared to a polar-repetition scheme with comparable decoding complexity.

In this paper, we investigate covert communication over millimeter-wave (mmWave) frequencies. In particular, a mmWave transmitter, referred to as Alice, attempts to reliably communicate to a receiver, referred to as Bob, while hiding the existence of communication from a warden, referred to as Willie. In this regard, operating over the mmWave bands not only increases the covertness thanks to directional beams, but also increases the transmission data rates given much more available bandwidths and enables ultra-low form factor transceivers due to the lower wavelengths used compared to the conventional radio frequency (RF) counterpart. We first assume that the transmitter Alice employs two independent antenna arrays in which one of the arrays is to form a directive beam for data transmission to Bob. The other antenna array is used by Alice to generate another beam toward Willie as a jamming signal while changing the transmit power independently across the transmission blocks in order to achieve the desired covertness. For this dual-beam setup, we characterize Willie’s detection error rate with the optimal detector and the closed-form of its expected value from Alice’s perspective. We then derive the closed-form expression for the outage probability of the Alice-Bob link, which enables characterizing the optimal covert rate that can be achieved using the proposed setup. We further obtain tractable forms for the ergodic capacity of the Alice-Bob link involving only one-dimensional integrals that can be computed in closed forms for most ranges of the channel parameters. Finally, we highlight how the results can be extended to more practical scenarios, particularly to the cases where perfect information about the location of the passive warden is not available. Our results demonstrate the advantages of covert mmWave communication compared to the RF counterpart. The research in this paper is the first analytical attempt in exploring covert communication using mmWave systems.

Landmark codes underpin reliable physical layer communication, e.g., Reed-Muller, BCH, Convolution, Turbo, LDPC, and Polar codes: each is a linear code and represents a mathematical breakthrough. The impact on humanity is huge: each of these codes has been used in global wireless communication standards (satellite, WiFi, cellular). Reliability of communication over the classical additive white Gaussian noise (AWGN) channel enables benchmarking and ranking of the different codes. In this paper, we construct KO codes, a computationally efficient family of deep-learning driven (encoder, decoder) pairs that outperform the state-of-the-art reliability performance on the standardized AWGN channel. KO codes beat state-of-the-art Reed-Muller and Polar codes, under the low-complexity successive cancellation decoding, in the challenging short-to-medium block length regime on the AWGN channel. We show that the gains of KO codes are primarily due to the nonlinear mapping of information bits directly to transmit symbols (bypassing modulation) and yet possess an efficient, high-performance decoder. The key technical innovation that renders this possible is design of a novel family of neural architectures inspired by the computation tree of the {\bf K}ronecker {\bf O}peration (KO) central to Reed-Muller and Polar codes. These architectures pave way for the discovery of a much richer class of hitherto unexplored nonlinear algebraic structures.

Concatenating the state-of-the-art codes at moderate rates with repetition codes have emerged as practical solutions deployed in various standards for ultra-low-power devices such as in Internet-of-Things (IoT) networks. In this paper, we propose a novel concatenation mechanism for such applications which need to operate at very low signal-to-noise ratio (SNR) regime. In the proposed scheme, the outer code is a hybrid polar code constructed in two stages, one with a binary kernel and another also with a binary kernel but applied over a binary extension field. The inner code is a non-binary multiplicative repetition code. This particular structure inherits low-complexity decoding structures of polar codes while enabling concatenation with an inner non-binary multiplicative repetition scheme. The decoding for the proposed scheme is done using cyclic redundancy check (CRC) aided successive cancellation list (SCL) decoder over AWGN channel. Simulation results show that the proposed scheme outperforms the straightforward binary polar-repetition scheme at the cost of a negligible increase in the decoding complexity.

Reed-Muller (RM) codes are conjectured to achieve the capacity of any binary-input memoryless symmetric (BMS) channel, and are observed to have a comparable performance to that of random codes in terms of scaling laws. On the negative side, RM codes lack efficient decoders with performance close to that of a maximum likelihood decoder for general parameters. Also, they only admit certain discrete sets of rates. In this paper, we focus on subcodes of RM codes with flexible rates that can take any code dimension from 1 to$n$. where$n$is the blocklength. We first extend the recursive projection-aggregation (RPA) algorithm proposed recently by Ye and Abbe for decoding RM codes. To lower the complexity of our decoding algorithm, referred to as subRPA, we investigate different ways for pruning the projections. We then derive the soft-decision based version of our algorithm, called soft-subRPA, that is shown to improve upon the performance of subRPA. Furthermore, it enables training a machine learning (ML) model to search for good sets of projections that minimize the decoding error rate. Training our ML model enables achieving very close to the performance of full-projection decoding with a significantly reduced number of projections. For instance, our simulation results on a (64,14) RM subcode show almost identical performance for full-projection decoding and pruned-projection decoding with 15 projections picked via training our ML model. This is equivalent to lowering the complexity by a factor of more than 4 without sacrificing the decoding performance.

We consider the problem of coded computing, where a computational task is performed in a distributed fashion in the presence of adversarial workers. We propose techniques to break the adversarial toleration threshold barrier previously known in coded computing. More specifically, we leverage list-decoding techniques for folded Reed-Solomon codes and propose novel algorithms to recover the correct codeword using side information. In the coded computing setting, we show how the master node can perform certain carefully designed extra computations to obtain the side information. This side information is then utilized to prune the output of the list decoder and uniquely recover the true outcome. We further propose folded Lagrange coded computing (FLCC) to incorporate the developed techniques into a specific coded computing setting. Our results show that FLCC outperforms LCC by breaking the barrier on the number of adversaries that can be tolerated. In particular, the corresponding threshold in FLCC is improved by a factor of two compared to that of LCC.

We provide a new algebraic construction for packing subspaces in complex Grassmannian space with respect to the chordal distance metric. The proposed method extends the construction of character-polynomial (CP) subspace codes, recently proposed by the authors, to higher dimensions. Our results indicate the superiority of the packings derived from CP codes in the real Grassmannian space compared with existing explicit construction. Furthermore, we propose a concatenation method in Grassmannian space and characterize the rate and the minimum distance of a concatenated Grassmann code in terms of those of its underlying inner and outer codes. This result is then utilized to arrive at the counterpart of Zyablov bound in Grassmannian space. Finally, we construct Grassmann codes with asymptotically large blocklength simultaneously attaining non-vanishing rate and normalized minimum distance. In particular, we propose a family of concatenated Grassmann codes having CP inner codes that surpass the Zyablov bound in the low-rate regime.

The state-of-the-art approaches to privacy-preserving coded computing rely on quantizing the data into a finite field, so that Shamir's secret sharing can be employed. Such coded computing solutions, however, are not properly scalable with the size of dataset, mainly due to computation overflows. To address such a critical issue, we propose a novel extension of certain coded computing schemes to the analog domain. This includes distributed polynomial evaluation and Lagrange coded computing (LCC) that are widely used in the literature. All the operations in the proposed protocols are done over the infinite fields of R/C but for practical implementations floating-point numbers are used. We characterize the privacy of data in our proposed protocols, against any subset of colluding servers up to a certain size, in terms of the distinguishing security (DS) and the mutual information security (MIS) metrics. Also, the accuracy of outcome is characterized in a practical setting assuming operations are performed using floating-point numbers. Consequently, fundamental trade-offs between the accuracy of the outcome and their privacy level are observed in the analog domain and are numerically evaluated. Moreover, we implement analog LCC (ALCC) to perform matrix-matrix multiplication over a batch of matrices. It is observed that ALCC is superior compared to LCC, implemented using fixed-point numbers, assuming both schemes use an equal number of bits to represent data symbols.

The problem of channel polarization for an arbitrary sequence$\{W_{i}\}_{i=0}^{n-1}$of$n$independent channels, referred to as a nonstationary sequence of channels, is considered. Also, each of the channels is used only once for communication. We consider a general framework for polarization of non-stationary channels and aim at optimizing the framework toward obtaining the best polarization. This framework includes permuting channels before Arıkan's pairwise channel combining operations are applied at each polarization level and skipping certain combining operations. We define an explicit optimization problem with the objective of finding the best permutation and indices of skipped operations in order to minimize a certain measure of polarization in one-level polarization. We then provide a complete solution to this optimization problem in the case of non-stationary binary erasure channels (BECs). We also propose a greedy method for polarizing non-stationary BECs, based on our solution for one-level polarization. Numerical results confirm the superiority of our method, in terms of various performance metrics, for constructing polar codes in certain non-stationary settings compared to prior work.

In this paper, we present a low-complexity recursive approach for massive and scalable code-domain nonorthogonal multiple access (NOMA) with applications to emerging low-capacity scenarios. The problem definition in this paper is inspired by three major requirements of the next generations of wireless networks. Firstly, the proposed scheme is particularly beneficial in low-capacity regimes which is important in practical scenarios of utmost interest such as the Internet-of-Things (IoT) and massive machine-type communication (mMTC). Secondly, we employ code-domain NOMA to efficiently share the scarce common resources among the users. Finally, the proposed recursive approach enables code-domain NOMA with low-complexity detection algorithms that are scalable with the number of users to satisfy the requirements of massive connectivity. To this end, we propose a novel encoding and decoding scheme for code-domain NOMA based on factorizing the pattern matrix, for assigning the available resource elements to the users, as the Kronecker product of several smaller factor matrices. As a result, both the pattern matrix design at the transmitter side and the mixed symbols' detection at the receiver side can be performed over matrices with dimensions that are much smaller than the overall pattern matrix. Consequently, this leads to significant reduction in both the complexity and the latency of the detection. We present the detection algorithm for the general case of factor matrices. The proposed algorithm involves several recursions each involving certain sets of equations corresponding to a certain factor matrix. We then characterize the system performance in terms of average sum rate, latency, and detection complexity. Our latency and complexity analysis confirm the superiority of our proposed scheme in enabling large pattern matrices. Moreover, our numerical results for the average sum rate show that the proposed scheme provides better performance compared to straightforward code-domain NOMA with comparable complexity, especially at low-capacity regimes.

A major hurdle in machine learning is scalability to massive datasets. One approach to overcoming this is to distribute the computational tasks among several workers. Gradient coding has been recently proposed in distributed optimization to compute the gradient of an objective function using multiple, possibly unreliable, worker nodes. By designing distributed coded schemes, gradient coded computations can be made resilient to stragglers, nodes with longer response time compared to other nodes in a distributed network. Most such schemes rely on operations over the real or complex numbers and are inherently numerically unstable. We present a binary scheme which avoids such operations, thereby enabling numerically stable distributed computation of the gradient. Also, some restricting assumptions in prior work are dropped, and a more efficient decoding is given.

In this paper we study codes with sparse generator matrices. More specifically, codes with a certain constraint on the weight of all the columns in the generator matrix are considered. The end result is the following. For any binary-input memoryless symmetric (BMS) channel and any ε> 2ε*, where ε8 = 1/6 - [5/3log4/3] ≈ 0.085, we show an explicit sequence of capacity-achieving codes with all the column weights of the generator matrix upper bounded by (log N)1+ε, where N is the code block length. The constructions are based on polar codes. Applications to crowdsourcing are also shown.

We provide a precise framework to study subspace codes for non-coherent communications in wireless networks. To this end, an analog operator channel is defined with inputs and outputs being subspaces of Cn. Then a certain distance is defined to capture the performance of subspace codes in terms of their capability to recover from interference and rank-deficiency of the network. We also study the robustness of the proposed model with respect to additive noise. Furthermore, we propose a new approach to construct subspace codes in the analog domain, also regarded as Grassmann codes, by leveraging polynomial evaluations over finite fields together with characters associated to finite fields that map their elements to the unit circle in the complex plane. The constructed codes, referred to as characterpolynomial (CP) codes, are shown to perform better compared to other existing constructions of Grassmann codes in terms of the trade-off between the rate and the normalized minimum distance, for a wide range of values for n.

Constructing efficient low-rate error-correcting codes with low-complexity encoding and decoding have become increasingly important for applications involving ultra-low-power devices such as Internet-of-Things (IoT) networks. To this end, schemes based on concatenating the state-of-the-art codes at moderate rates with repetition codes have emerged as practical solutions deployed in various standards. In this paper, we propose a novel mechanism for concatenating outer polar codes with inner repetition codes which we refer to as polar coded repetition. More specifically, we propose to transmit a slightly modified polar codeword by deviating from Arıkan's standard 2 × 2 Kernel in a certain number of polarization recursions at each repetition block. We show how this modification can improve the asymptotic achievable rate of the polar-repetition scheme, while ensuring that the overall encoding and decoding complexity is kept almost the same. The achievable rate is analyzed for the binary erasure channels (BEC).

Two legitimate parties, referred to as Alice and Bob, wish to generate secret keys from the wireless channel in the presence of an eavesdropper, referred to as Eve, in order to use such keys for encryption and decryption. In general, the secret key rate highly depends on the coherence time of the channel. In particular, a straightforward method of generating secret keys in static environments results in ultra-low rates. In order to resolve this problem, we introduce a low-complexity method called induced randomness. In this method, Alice and Bob independently generate local randomness to be used together with the uniqueness of the wireless channel coefficients in order to enable high-rate secret key generation. In this work, two scenarios are considered: first, when Alice and Bob share a direct communication channel, and second, when Alice and Bob do not have a direct link and communicate through an untrusted relay. After exchanging the induced randomness, post-processing is done by Alice and Bob to generate highly-correlated samples that are used for the key generation. Such samples are then converted into bits, disparities between the sequences generated by Alice and Bob are mitigated, and the resulting sequences are then hashed to compensate for the information leakage to the eavesdropper and to allow consistency checking of the generated key bit sequences. We utilize semantic security measures and information-theoretic inequalities to upper bound the probability of successful eavesdropping attack in terms of the mutual information measures that can be numerically computed. Given certain reasonable system parameters this bound is numerically evaluated to be 2-31and 2-10.57in the first and the second scenario, respectively.

The problem of polar coding for an arbitrary sequence of independent binary-input memoryless symmetric (BMS) channels {Wi}i=1Nis considered. Such a sequence of channels is referred to as a non-stationary sequence of channels and arises in applications where data symbols experience different and independent channel characteristics. The sequence of channels is assumed to be completely known to both the transmitter and the receiver (a coherent scenario). Also, at each code block transmission, each of the channels is used only once. In other words, a codeword of length N is constructed and then the i-th encoded bit is transmitted over Wi. The goal is to operate at a rate R close to the average of the symmetric capacities of Wi's, denoted by I̅N. To this end, we construct a polar coding scheme using Arikan's channel polarization transform in combination with certain permutations at each polarization level and certain skipped operations. In particular, given a nonstationary sequence of BMS channels {Wi}i=1Nand Pe, where 0eefor transmission over {Wi}i=1Nsuch that N ≤ κ/(I̅N-R)μ)), where μ is a constant and κ is a constant depending on Peand μ. We further show a numerical upper bound on μ that is: μ ≤ 7.34 for non-stationary binary erasure channels and μ ≤ 8.54 for general non-stationary BMS channels. The encoding and decoding complexities of the constructed polar code preserve O(N log N) complexity of Arıkan's polar codes. In an asymptotic sense, when coded bits are transmitted over a non-stationary sequence of BMS channels {Wi}i=1L, our proposed scheme achieves the average symmetric capacity I̅({Wi}i=1L)deg= limN-L1/N Σi=1NI(Wi), assuming that the limit exists.

In this paper, we consider a relay-assisted uplink non-orthogonal multiple access (NOMA) system. In this system, two radio frequency (RF) users are grouped for simultaneous transmissions, over each resource block, to an intermediate relay. The relay then forwards the amplified version of the users' aggregated signals, in the presence of multiuser interference, to a relatively far destination. In order to cope with the users' ever-increasing desire for higher data rates, a high-throughput free-space optics (FSO) link is employed as the relay-destination backhaul link. It is assumed that the FSO backhaul link is subject to Gamma-Gamma turbulence with pointing error. Also, a Rayleigh fading model is considered for the user-relay access links. Under these assumptions, we derive closed-form expressions for the outage probability and tractable forms, involving only one-dimensional integrals, for the ergodic capacity. Moreover, the outage probability and ergodic capacity analysis are extended to the conventional RF-backhauled systems in the presence of multiuser interference to both relay and destination nodes, and Rician fading for the relay-destination RF link. Our results reveal the superiority of FSO backhauling for high-throughput and high-reliability NOMA systems compared to RF backhauling. This work can be considered as a general analysis of dual-hop uplink NOMA systems as well as the first attempt to incorporate power-domain NOMA in mixed RF-FSO systems.

In this paper, we investigate covert communication over millimeter-wave (mmWave) frequencies. In particular, a dual-beam mmWave transmitter, comprised of two independent antenna arrays, attempts to reliably communicate to a receiver Bob when hiding the existence of transmission from a warden Willie. In this regard, operating over mmWave bands not only increases the covertness thanks to directional beams, but also increases the transmission data rates given much more available bandwidths and enables ultra-low form factor transceivers due to the lower wavelengths used compared to the conventional radio frequency (RF) counterpart. We assume that the transmitter Alice employs one of its antenna arrays to form a directive beam for transmission to Bob. The other antenna array is used by Alice to generate another beam toward Willie as a jamming signal with its transmit power changing independently from a transmission block to another block. We characterize Willie's detection performance with the optimal detector and the closed-form of its expected value from Alice's perspective. We further derive the closed-form expression for the outage probability of the Alice-Bob link, which enables characterizing the optimal covert rate that can be achieved using the proposed setup. Our results demonstrate the superiority of mmWave covert communication, in terms of covertness and rate, compared to the RF counterpart.

A novel framework for sharing common randomness and generating secret keys in wireless networks is considered. In particular, a network of users equipped with pulse oscillators (POs) and coupling mechanisms in between is considered. Such mechanisms exist in synchronized biological and natural systems, and have been exploited to provide synchronization in distributed networks. We show that naturally-existing initial random phase differences between the POs in the network can be utilized to provide almost identical common randomness to the users. This randomness is extracted from the synchronization time in the network. Bounds on the entropy of such randomness are derived for a two-user system and a conjecture is made for a general n-user system. Then, a three-terminal scenario is considered including two legitimate users and a passive eavesdropper, referred to as Eve. Since in a practical setting Eve receives pulses with propagation delays, she can not identify the exact synchronization time. A simplified model is then considered for Eve's receiver and then a bound on the rate of secret key generation is derived. Also, it is shown, under certain conditions, that the proposed protocol is resilient to an active jammer equipped with a similar pulse generation mechanism.

Low-capacity scenarios have become increasingly important in the technology of Internet of Things (IoT) and the next generation of mobile networks. Such scenarios require efficient and reliable transmission of information over channels with an extremely small capacity. Within these constraints, the performance of state-of-the-art coding techniques is far from optimal in terms of either rate or complexity. Moreover, the current non-asymptotic laws of optimal channel coding provide inaccurate predictions for coding in the low-capacity regime. In this paper, we provide the first comprehensive study of channel coding in the low-capacity regime. We will investigate the fundamental non-asymptotic limits for channel coding as well as challenges that must be overcome for efficient code design in low-capacity scenarios.

We consider the problem of coded distributed computing where a large linear computational job, such as a matrix multiplication, is divided into k smaller tasks, encoded using an (n, k) linear code, and performed over n distributed nodes. The goal is to reduce the average execution time of the computational job. We provide a connection between the problem of characterizing the average execution time of a coded distributed computing system and the problem of analyzing the error probability of codes of length n used over erasure channels. Accordingly, we present closed-form expressions for the execution time using binary random linear codes and the best execution time any linear-coded distributed computing system can achieve. It is also shown that there exist good binary linear codes that attain, asymptotically, the best performance any linear code, not necessarily binary, can achieve. We also investigate the performance of coded distributed computing systems using polar and Reed-Muller (RM) codes that can benefit from low-complexity decoding, and superior performance, respectively, as well as explicit constructions. The proposed framework in this paper can enable efficient designs of distributed computing systems given the rich literature in the channel coding theory.

This paper models the crowdsourced labeling/classification problem as a sparsely encoded source coding problem, where each query answer, regarded as a code bit, is the XOR of a small number of labels, as source information bits. In this paper we leverage the connections between this problem and well-studied codes with sparse representations for the channel coding problem to provide querying schemes with almost optimal number of queries, each of which involving only a constant number of labels. We also extend this scenario to the case where some workers can be unresponsive. For this case, we propose querying schemes where each query involves only log n items, where n is the total number of items to be labeled. Furthermore, we consider classification of two correlated labeling systems and provide two-stage querying schemes with almost optimal number of queries each involving a constant number of labels.

The problem of list decoding algebraic subspace codes and rank-metric codes is considered. We develop two separate methods, via two different approaches, for list decoding subspace codes and rank-metric codes. These methods provide, for certain code parameters, improved tradeoffs between rate and error-correction capability than that of the Koetter-Kschischang codes, in the domain of subspace codes, and than that of the Gabidulin codes, in the domain of rank-metric codes, and several other extensions thereof. In the first approach, we introduce the notion of root multiplicities for a certain sub-ring of the ring of linearized polynomials. In the list-decoding algorithm, multiple roots are enforced for the interpolation polynomial in order to achieve an improved error-correction radius for an extended family of Koetter-Kschischang subspace codes. The normalized error-correction radius for this approach is τA=2(L+1)/(r+1)-1-L(L+1)(L+n)/r(r+1)R, where L is the maximum list size, n is the subspace code dimension, R is the rate of the code, and r is the multiplicity parameter. In the second approach, we construct a folded version of Koetter-Kschischang codes. A linear-algebraic list-decoding algorithm is proposed for these codes that achieves the error-correction radius τB=s(1-sR), where s is the folding parameter. As opposed to the first approach, the size of output list in the second approach depends on the underlying field size and is at most qm(s-1), where qmis the size of the field that message symbols are chosen from. It is also shown that the output list size is 1, with high probability, in a probabilistic setting. We utilize the techniques of the second approach in the domain of rank-metric codes to construct folded Gabidulin codes to enable a linear-algebraic list-decoding algorithm for such codes. Our algorithm makes it possible to recover.

Secret key agreement in distributed low-power networks, such as Internet of Things (IoT) networks, is a major requirement for deploying cryptographic protocols to protect the security of sensitive data. However, due to the distributed nature of such networks, the devices need to be able to generate secret keys locally from some common source of randomness. The randomness in the characteristics of the physical layer channel provides such sources, however, this can be quite limited if the devices operate in a static environment and experience static or very slow fading channel. Therefore, fast secret key generation in such environments while keeping a low complexity architecture for the network nodes, such as IoT devices, remains a challenging task. We design a low-complexity protocol for fast secret key generation in static environments. To this end, we propose to use a limited number of random bits independently generated by the legitimate parties, referred to as Alice and Bob, in combination with the fading parameter to create a common source of randomness. In the proposed protocol, Alice and Bob share their random bits over the public channel, assumed to be a fading channel, and then construct a common random sequence. Then they perform several steps for recovery from errors in the shared sequence, privacy amplification to limit the chances of a successful attack, and consistency checking by exploiting universal hash functions. We characterize the reliability of the proposed protocol and provide an upper bound on the probability of accepting a mismatched key by Alice and Bob. The eavesdropper Eve is assumed to be passive and a successful attack by her is the event of guessing the key right based on her observations. We provide an analytical upper bound, that can be numerically evaluated, on the probability of a successful attack by Eve using the cryptographic notion of semantic security. In the simulations, the proposed protocol achieves a bit generation rate of 64-96 bits/packet, bit mismatch rate of 11-24%, bit error rate of 0.005%, 50% randomness efficiency, the probability of successful attack of at most 2-31, and the probability of consistency checking failure of at most 2-16.

A new framework for secure communication in physical layer is proposed. A network of users equipped with coupled dynamical systems is considered. The aim is to securely exchange messages between network nodes in the presence of an eavesdropper, referred to as Eve. Unlike a traditional wireless system, the messages to be conveyed are not sent directly through the medium. Instead, they are mapped to initial conditions of the dynamical system. Once the system converges to a steady state, conditions of the local system at each node is measured to recover the sent messages. A fundamental property of the proposed system which makes it secure is that Eve is not part of the dynamical system and hence, she does not observe the initial conditions of the nodes for steady state comparison measurement. In particular, a situation with two users is considered. The proposed system is then modeled as a two-way wiretap channel and the secrecy capacity region is derived under various conditions. A consequence of our result is that regardless of Eve's physical location and how strong her receiver is the achievable rates are positive, i.e., secure communication is possible. Furthermore, a radio frequency (RF) system is proposed to realize this model in a wireless setting by means of local coupled oscillators. In particular, a unidirectional master-slave coupling architecture is considered where a power-constrained slave node synchronizes its frequency with a high-power master node. It is shown how the coupling mechanism, realized by transmitting and receiving power between the RF front-ends of the master and the slave node, can be used by the slave node to securely send messages or to share secret keys with the master node. To the best of our knowledge, this is the first architecture providing physical layer secret key generation fully designed in the RF front-end. The proposed RF system is simulated using Advanced Design System (ADS). The simulation results are shown for a 10m channel link and confirm the security condition. The secret key generation rate is 2 bits per synchronization time-frame which is dominated by the wave propagation delay between the two nodes.

Nonorthogonal multiple access (NOMA) is a promising technology to meet the demands of the next generation wireless networks on massive connectivity, high throughput and reliability, improved fairness, and low latency. In this context, code-domain NOMA which attempts to serve K users in M ≤ K orthogonal resource blocks, using a pattern matrix, is of utmost interest. However, extending the pattern matrix dimensions severely increases the detection complexity and hampers on the significant advantages that can be achieved using large pattern matrices. In this paper, we propose a novel approach toward code-domain NOMA which factorizes the pattern matrix as the Kronecker product of some other factor matrices each with a smaller dimension. Therefore, both the pattern matrix design at the transmitter side and the mixed symbols' detection at the receiver side can be performed over much smaller dimensions and with a remarkably reduced complexity and latency. As a consequence, the system can significantly be overloaded to effectively support the requirements of the next generation wireless networks without any considerable increase on the system complexity.

A distributed secret sharing system is considered that consists of a dealer, n storage nodes, and m users. Each user is given access to a certain subset of storage nodes where it can download the data. The dealer wants to securely convey a specific secret sjto user j via storage nodes, for j = 1, 2,..., m, in such a way that no user gets any information about other users' secrets in an information-theoretic sense. To this end, we propose to study protocols where the dealer encodes secrets into several secret shares and loads them into the storage nodes. Given a certain number of storage nodes we find the maximum number of users that can be served in such protocols and construct schemes that achieve this. We further define two major properties for such distributed secret sharing systems; communication complexity is defined as the total amount of data that needs to be downloaded by users in order to reconstruct their secrets; and storage overhead is defined as the total amount of data loaded by the dealer into the storage nodes normalized by the total size of secrets. Lower bounds on minimum communication complexity and storage overhead are characterized given any n and m. Furthermore, we construct distributed secret sharing protocols, under certain conditions on the system parameters, that attain these lower bounds thereby providing schemes that are optimal in terms of both the communication complexity and storage overhead.

The problem of analyzing the finite-length scaling behavior of sparse random linear codes is considered. Random linear codes with random generator matrices whose entries are picked according to i.i.d. Bernoulli distribution with parameter q = o(1) are called sparse. The parameter q is referred to as the sparsity of the random linear code. We develop a methodology to show the optimality of the scaling exponent of uniform random linear codes, i.e., q = 1/2, with high probability. The results are then extended to sparse random linear codes with sparsity q = Θ(n-1/2), where n is the code block length. The encoding complexity of such sparse random linear codes is reduced from O(n2), in uniform random linear codes, to O(n3/2). It is also conjectured that q = log n/n is the lowest sparsity of random linear codes with optimal scaling exponent. The connection of these results to an open problem regarding finding binary polar codes with optimal scaling exponent are also discussed. In particular, we point out that as the size of the polarization kernel increases it can be used as the generator matrix for a code with optimal scaling exponent, without the need to do further polarization.

We consider the problem of polar coding for transmission overa non-stationary sequence of independent binary-input memoryless symmetric (BMS) channels {Wi}∞i=1where the i-th encoded bit is transmitted over Wi. We show, for the first time, a polar coding scheme that achieves the average symmetric capacity I̅({Wi}∞i=1) def= limN→∞1/NNΣi=1I(Wi) assuming that the limit exists. The polar coding scheme is constructed using Arikan's channel polarization transformation in combination with certain permutations at each polarization level and certain skipped operations. This guarantees a fast polarization process that results in polar coding schemes with block lengths upper bounded by a polynomial of 1/e, where e is the gap to the average capacity. More specifically, given an arbitrary sequence of BMS channels {Wi}Ni=1and Pe, where 0i}Ni=1such that N ≤ κ/(I̅N- R)μwhere μ is a constant, κ is a constant depending on Pe and μ, and INis the average of the symmetric capacities I (Wi), for i = 1, 2, ...,N. We further show a numerical upper bound on μ that is: μ ≤ 10.78. The encoding and decoding complexities of the constructed polar code preserves O(N log N) complexity of Arikan's polar codes.

A rank-metric code is a subset of Fqn × mwhere Fqis a finite field. Gabidulin codes are a well-known class of algebraic rank-metric codes that meet the Singleton bound on the minimum rank distance of a code. The construction, encoding, and decoding of Gabidulin codes use the extension field Fqm, where the code is regarded as a linear block code of length n over Fqm. However, the parameter m can be large in certain applications and therefore, performing field operations over Fqm can become very complex. In this paper, we investigate methods for constructing and decoding rank-metric codes by looking into linear codes of length nm over the base field Fq. Random coding bounds are derived on the minimum distance of such codes and an explicit structure is demonstrated to construct maximum rank distance codes. It is shown how to construct sparse parity-check matrices for these structures which enables low complexity parallelized decoders with complexity that scales linearly with m.

The problem of constructing sticky-insertion-correcting codes with efficient encoding and decoding is considered. An {n, M, r) sticky-insertion-correcting code consists of M codewords of length n such that any pattern of up to r sticky insertions can be corrected. We utilize BCH codes and their analogous in the Lee space to construct explicit and systematic codes that are immune to up to r sticky insertions. It is shown that the ratio of the number of constructed redundancy bits in the construction to a certain upper bound approaches one as the block length grows large, which implies asymptotic optimality of the construction.

Polar codes are the latest breakthrough in coding theory, as they are the first family of codes with explicit construction that provably achieve the symmetric capacity of binary-input discrete memoryless channels. Polar encoding and successive cancellation decoding have the complexities of N log N , for code length N. Although, the complexity bound of N log N is asymptotically favorable, we report in this work methods to further reduce the encoding and decoding complexities of polar coding. The crux is to relax the polarization of certain bit-channels without performance degradation. We consider schemes for relaxing the polarization of both very good and very bad bit-channels, in the process of channel polarization. Relaxed polar codes are proved to preserve the capacity achieving property of polar codes. Analytical bounds on the asymptotic and finite-length complexity reduction attainable by relaxed polarization are derived. For binary erasure channels, we show that the computation complexity can be reduced by a factor of six, while preserving the rate and error performance. We also show that relaxed polar codes can be decoded with significantly reduced latency. For additive white Gaussian noise channels with medium code lengths, we show that relaxed polar codes can have lower error probabilities than conventional polar codes, while having reduced encoding and decoding computation complexities.

We consider the problem of polar coding for transmission over m-user multiple access channels. In the proposed scheme, all users encode their messages using a polar encoder, while a multiuser successive cancellation decoder is deployed at the receiver. The encoding is done separately across the users and is independent of the target achievable rate. For the code construction, the positions of information bits and frozen bits for each of the users are decided jointly. This is done by treating the polar transformations across all the m users as a single polar transformation with a certain polarization base. We characterize the resolution of achievable rates on the dominant face of the uniform rate region in terms of the number of users m and the length of the polarization base L. In particular, we prove that for any target rate on the dominant face, there exists an achievable rate, also on the dominant face, within the distance at most (m-1)√m/L from the target rate. We then prove that the proposed L MAC polar coding scheme achieves the whole uniform rate region with fine enough resolution by changing the decoding order in the multiuser successive cancellation decoder, as L and the code block length N grow large. The encoding and decoding complexities are O(N log N) and the asymptotic block error probability of O(2-N0.5-ϵ) is guaranteed. Examples of achievable rates for the 3-user multiple access channel are provided.

A design of rate-compatible polar codes suitable for HARQ communications is proposed in this paper. An important feature of the proposed design is that the puncturing order is chosen with low complexity on a base code of short length, which is then further polarized to the desired length. A practical rate-matching system that has the flexibility to choose any desired rate through puncturing or repetition while preserving the polarization is suggested. The proposed rate-matching system is combined with channel interleaving and a bit-mapping procedure that preserves the polarization of the rate-compatible polar code family over bit-interleaved coded modulation systems. Simulation results on AWGN and fast fading channels with different modulation orders show the robustness of the proposed rate-compatible polar code in both Chase combining and incremental redundancy HARQ communications.

We consider a channel model based on the diffusion of particles in the medium which is motivated by the natural communication mechanisms between biological cells based on exchange of molecules. In this model, the transmitter secretes particles into the medium via a particle dissemination rate. The concentration of particles at any point in the medium is a function of its distance from the transmitter and the particle dissemination rate. The reception process is a doubly stochastic Poisson process whose rate is a function of the concentration of the particles in the vicinity of the receiver. We derive a closed-form for the mutual information between the input and output processes in this communication scenario and establish useful properties about the mutual information. We also provide a signaling strategy using which we derive a lower bound on the capacity of the diffusion channel with Poisson reception process under average and peak power constraints. Furthermore, it is shown that the capacity of discretized diffusion channel can be a negligible factor of the capacity of continuous time diffusion channel. Finally, the application of the considered model to the molecular communication systems is discussed.

The problem of constructing error correcting codes for defective memories, where some of the cells are defected and unable to switch their states, is considered. This is a classical problem in coding theory which has recently received renewed attention due to application to new technologies for non-volatile memories such as phase change memories. We show how the state of the art capacity achieving codes, in combination with a coset coding and another error correcting code, can be used in order to asymptotically achieve the capacity of the binary defective memory. The resulting schemes are explicit, have polynomial time encoder and quasilinear time decoder. The model is further generalized by considering erasures on top of the defective cells. We propose the partitioned polar codes for this model and prove that they achieve the capacity.

Arıkan's polar codes are proven to be capacity-achieving error correcting codes while having explicit constructions. They are characterized to have encoding and decoding complexities of l log l, for code length l. In this work, we construct another family of capacity-achieving codes that have even lower encoding and decoding complexities, by relaxing the channel polarizations for certain bit-channels. We consider schemes for relaxing the polarization of both sufficiently good and sufficiently bad bit-channels, in the process of channel polarization. We prove that, similar to conventional polar codes, relaxed polar codes also achieve the capacity of binary memoryless symmetric channels. We analyze the complexity reductions achievable by relaxed polarization for asymptotic and finite-length codes, both numerically and analytically. We show that relaxed polar codes can have better bit error probabilities than conventional polar codes, while having reduced encoding and decoding complexities.

A scheme for concatenating the recently invented polar codes with non-binary MDS codes, as Reed-Solomon codes, is considered. By concatenating binary polar codes with interleaved Reed-Solomon codes, we prove that the proposed concatenation scheme captures the capacity-achieving property of polar codes, while having a significantly better error-decay rate. We show that for any ε > 0, and total frame length N, the parameters of the scheme can be set such that the frame error probability is less than 2-N1-ε, while the scheme is still capacity achieving. This improves upon 2-N0.5-ε, the frame error probability of Arikan's polar codes. The proposed concatenated polar codes and Arikan's polar codes are also compared for transmission over channels with erasure bursts. We provide a sufficient condition on the length of erasure burst which guarantees failure of the polar decoder. On the other hand, it is shown that the parameters of the concatenated polar code can be set in such a way that the capacity-achieving properties of polar codes are preserved. We also propose decoding algorithms for concatenated polar codes, which significantly improve the error-rate performance at finite block lengths while preserving the low decoding complexity.

Flash memory is a nonvolatile computer memory comprising blocks of cells, wherein each cell can take on$q$different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes—known as floating codes (or flash codes) and buffer codes—have been designed in order to maximize the number of times that information stored in a flash memory can be written (and rewritten) prior to incurring a block erasure. An$(n,k,t)_{q}$flash code$\BBC$is a coding scheme for storing$k$information bits in$n$cells in such a way that any sequence of up to$t$writes can be accommodated without a block erasure. The total number of available level transitions in$n$cells is$n(q{-}1)$, and the write deficiency of$\BBC$, defined as$\delta (\BBC)=n(q{-}1)-t$, is a measure of how close the code comes to perfectly utilizing all these transitions. In this paper, we show a construction of flash codes with write deficiency$O(qk\log k)$if$q\geqslant\log_{2}k$, and at most$O(k\log^{2}k)$otherwise. An$(n,r,\ell,t)_{q}$buffer code is a coding scheme for storing a buffer of$r~\ell$-ary symbols such that for any sequence of$t$symbols, it is possible to successfully decode the last$r$symbols that were written. We improve upon a previous upper bound on the maximum number of writes$t$in the case where there is a single cell to store the buffer. Then, we show how to improve a construction by Jiangthat uses multiple cells, where$n\geqslant 2r$.

A scheme for concatenating the recently invented polar codes with interleaved block codes is considered. By concatenating binary polar codes with interleaved Reed-Solomon codes, we prove that the proposed concatenation scheme captures the capacity-achieving property of polar codes, while having a significantly better error-decay rate. We show that for any ε > 0, and total frame length N, the parameters of the scheme can be set such that the frame error probability is less than 2-N 1-ε, while the scheme is still capacity achieving. This improves upon 2-N 0.5-ε, the frame error probability of Arikan's polar codes. We also propose decoding algorithms for concatenated polar codes, which significantly improve the error-rate performance at finite block lengths while preserving the low decoding complexity.

Subspace codes are collections of subspaces of a cer- tain ambient vector space over a finite field. Koetter and Kschi- schang introduced subspace codes in order to correct errors and erasures in noncoherent (random) linear network coding. They have also studied a remarkable family of subspace codes obtained by evaluating certain linearized polynomials. The Koetter–Kschi- schang subspace codes are widely regarded as the counterpart of Reed–Solomoncodes in the domain of network error-correction. Koetter and Kschischang have furthermore devised an algebraic decoding algorithm for these codes, analogous to the Berlekamp– Welch decoding algorithm for Reed–Solomon codes.

Subspace codes and rank-metric codes can be used to correct errors and erasures in network, with linear network coding. Both types of codes have been extensively studied in the past five years. Subspace codes were introduced by Koetter and Kschischang to correct errors and erasures in networks where topology is unknown (the non-coherent case). In this model, the codewords are vector subspaces of a fixed ambient space; thus codes for this model are collections of such subspaces. In a previous work, we have developed a family of subspace codes, based upon the Koetter-Kschichang construction, which are efficiently list decodable. Using these codes, we achieved a better decoding radius than Koetter-Kschischang codes at low rates. Herein, we introduce a new family of subspace codes based upon a different approach which leads to a linear-algebraic list-decoding algorithm. The resulting error-correction radius can be expressed as follows: for any integer s, our list-decoder using s + 1-variate interpolation polynomials guarantees successful recovery of the message sub-space provided the normalized dimension of errors is at most s(1 - sR). The same list-decoding algorithm can be used to correct erasures as well as errors. The size of output list is at most Qs - 1, where Q is the size of the field that message symbols are chosen from. Rank-metric codes are suitable for error correction in the case where the network topology and the underlying network code are known (the coherent case). Gabidulin codes are a well-known class of algebraic rank-metric codes that meet the Singleton bound on the minimum rank-distance of a code. In this paper, we introduce a folded version of Gabidulin codes analogous to the folded Reed-Solomon codes of Guruswami and Rudra along with a list-decoding algorithm for such codes. Our list-decoding algorithm makes it possible to recover the message provided that the normalized rank of error is at most 1 - R - ϵ, for any ϵ >; 0. Notably this achieves the information theoretic bound on the decoding radius of a rank-metric code.

Suppose that Alice wishes to send messages to Bob through a communication channel$C_{1}$, but her transmissions also reach an eavesdropper Eve through another channel$C_{2}$. This is the wiretap channel model introduced by Wyner in 1975. The goal is to design a coding scheme that makes it possible for Alice to communicate both reliably and securely. Reliability is measured in terms of Bob's probability of error in recovering the message, while security is measured in terms of the mutual information between the message and Eve's observations. Wyner showed that the situation is characterized by a single constant${\cal C}_{s}$, called the secrecy capacity, which has the following meaning: for all$\varepsilon \!\! > \!\! 0$, there exist coding schemes of rate$R\! \geqslant {\cal C}_{s} \! \! - \! \varepsilon$that asymptotically achieve the reliability and security objectives. However, his proof of this result is based upon a random-coding argument. To date, despite considerable research effort, the only case where we know how to construct coding schemes that achieve secrecy capacity is when Eve's channel$C_{2}$is an erasure channel, or a combinatorial variation thereof.

Suppose that Alice wishes to send messages to Bob through a communication channel C1, but her transmissions also reach an eavesdropper Eve through another channel C2. This is the wiretap channel model introduced by Wyner in 1975. The goal is to design a coding scheme that makes it possible for Alice to communicate both reliably and securely. Reliability is measured in terms of Bob's probability of error in recovering the message, while security is measured in terms of the ratio of Eve's equivocation about the message to its a priori entropy. Wyner showed that the situation is characterized by a single constant Cs, called the secrecy capacity, which has the following meaning: for all ε > 0, there exist coding schemes of rate R ≥ Cs- ε that asymptotically achieve both the reliability and the security objectives. However, his proof of this result is based upon a nonconstructive random-coding argument. To date, despite a considerable research effort, the only case where we know how to construct codes that achieve secrecy capacity is when Eve's channel C2is an erasure channel, or a combinatorial variation thereof. Polar codes were recently introduced by Arikan. They achieve the capacity of symmetric binary-input discrete memoryless channels with low encoding and decoding complexity. In this paper, we use polar codes to construct a coding scheme that achieves the secrecy capacity of general wiretap channels. Our construction works for any instantiation of the wiretap channel model, as originally defined by Wyner, as long as both C1and C2are symmetric and binary-input.

The operator channel was introduced by Koetter and Kschischang as a model of errors and erasures for randomized network coding, in the case where network topology is unknown (the noncoherent case). The input and output of the operator channel are vector subspaces of the ambient space; thus error-correcting codes for this channel are collections of such subspaces. Koetter and Kschischang also constructed a remarkable family of codes for the operator channel. The Koetter-Kschischang codes are similar to Reed-Solomon codes in that codewords are obtained by evaluating certain (linearized) polynomials. In this paper, we consider the problem of list-decoding the Koetter-Kschischang codes on the operator channel. In a sense, we are able to achieve for these codes what Sudan was able to achieve for Reed-Solomon codes. In order to do so, we have to modify and generalize the original Koetter-Kschischang construction in many important respects. The end result is this: for any integer L, our list-L decoder guarantess successful recovery of the message subspace provided the normalized dimension of the error is at most L - L2(L + 1)/2-R where R is the normalized rate of the code. Just as in the case of Sudan's list-decoding algorithm, this exceeds the previously best-known error-correction radius 1 - R, demonstrated by Koetter and Kschischang, for low rates R.

Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes or flash codes - have been designed in order to maximize the number of times that information stored in a flash memory can be written (and re-written) prior to incurring a block erasure. An (n, k, t)qflash code ¿ is a coding scheme for storing k information bits in n cells in such a way that any sequence of up to t writes (where a write is a transition 0 ¿ 1 or 1 ¿ 0 in any one of the k bits) can be accommodated without a block erasure. The total number of available level transitions in n cells is n(q-1), and the write deficiency of ¿, defined as ¿(¿) = n(q-1)-t, is a measure of how close the code comes to perfectly utilizing all these transitions. For k > 6 and large n, the best previously known construction of flash codes achieves a write defficiency of O(qk2). On the other hand, the best known lower bound on write deficiency is ¿(qk). In this paper, we present a new construction of flash codes that approaches this lower bound to within a factor logarithmic in k. To this end, we first improve upon the so-called ¿indexed¿ flash codes, due to Jiang and Bruck, by eliminating the need for index cells in the Jiang-Bruck construction. Next, we further increase the number of writes by introducing a new multi-stage (recursive) indexing scheme. We then show that the write defficiency of the resulting flash codes is O(qk log k) if q ¿ log2k, and at most O(k log2k) otherwise.