Federated learning (FL) with differential privacy (DP) provides a framework for collaborative machine learning, enabling clients to train a shared model while adhering to strict privacy constraints. The framework allows each client to have an individual privacy guarantee, e.g., by adding different amounts of noise to each client's model updates. One underlying assumption is that all clients spend their privacy budgets uniformly over time (learning rounds). However, it has been shown in the literature that learning in early rounds typically focuses on more coarse-grained features that can be learned at lower signal-to-noise ratios while later rounds learn fine-grained features that benefit from higher signal-to-noise ratios. Building on this intuition, we propose a time-adaptive DP-FL framework that expends the privacy budget non-uniformly across both time and clients. Our framework enables each client to save privacy budget in early rounds so as to be able to spend more in later rounds when additional accuracy is beneficial in learning more fine-grained features. We theoretically prove utility improvements in the case that clients with stricter privacy budgets spend budgets unevenly across rounds, compared to clients with more relaxed budgets, who have sufficient budgets to distribute their spend more evenly. Our practical experiments on standard benchmark datasets support our theoretical results and show that, in practice, our algorithms improve the privacy-utility trade-offs compared to baseline schemes.

For applications in concatenated coding for optical communications systems, we examine soft-demapping of short spherical codes constructed as constant-energy shells of the Cartesian power of pulse amplitude modulation constellations. These are unions of permutation codes having the same average power. We construct a list decoder for permutation codes by adapting Murty’s algorithm, which is then used to determine mutual information curves for these permutation codes. In the process, we discover a straightforward expression for determining the likelihood of large subcodes of permutation codes. We refer to these subcodes, obtained by all possible sign flips of a given permutation codeword, as orbits. We introduce a simple process, which we call orbit demapping with frozen symbols, that allows us to extract soft information from noisy permutation codewords. In a sample communication system with probabilistic amplitude shaping protected by a standard low-density parity-check code that employs short permutation codes, we demonstrate that orbit demapping with frozen symbols provides a gain of about 0.3 dB in signal-to-noise ratio compared to the traditional symbol-by-symbol demapping. By using spherical codes composed of unions of permutation codes, we can increase the input entropy compared to using permutation codes alone. In one scheme, we consider a union of a small number of permutation codes. In this case, orbit demapping with frozen symbols provides about 0.2 dB gain compared to the traditional method. In another scheme, we use all possible permutations to form a spherical code that exhibits a computationally feasible trellis representation. The soft information obtained using the BCJR algorithm outperforms the traditional symbol-by-symbol method by 0.1 dB. Overall, using the spherical codes containing all possible permutation codes of the same average power and the BCJR algorithm, a gain of 0.5 dB is observed compared with the case of using one permutation code with the symbol-by-symbol demapping. Comparison of the achievable information rates of bit-metric decoding verifies the observed gains.

Probabilistic shaping (PS) techniques, when combined with forward error correction, enable reliable transmission at rates close to capacity by inducing a favorable probability distribution on channel input symbols. In this paper, we introduce the parallelized block-based distribution matching (PB-DM) shaping architecture. To facilitate high-throughput PS, the method operates by combining blocks of bits, generated in parallel by multiple binary distribution matchers, and mapping them to blocks of symbols from a non-binary alphabet. The sizes of bit and symbol blocks, and the mapping rule between such blocks, are key design parameters. The parameters bestow the PB-DM architecture with a high degree of customizability, which distinguishes it from other PS schemes. In particular, different PB-DM instances – each characterized by a particular trade-off between shaping performance, latency and memory footprint – can be constructed. Considering a scenario in which constraints are imposed on the allowable latency and memory usage, we propose a heuristic approach to determine design parameters that produce well-performing PB-DM schemes that satisfy the given constraints. We present simulation results over the additive white Gaussian noise channel, demonstrating the performance-complexity trade-offs realizable by different short-blocklength PB-DM designs, and compare them against the trade-offs achieved by other commonly used schemes.

Consider a communication setup consisting of two terminals, each with access to one of two correlated sources. The terminals can swap information and both terminals want to reconstruct a deterministic function of the two sources under the requirements that reconstructions at the two terminals must satisfy average distortion constraints and the two reconstructions must be identical with high probability. In this paper, we develop an achievability and a converse to the problem assuming discrete memoryless sources. Furthermore, we demonstrate that our bounds are separately tight for a few special cases of the problem.

Federated Learning (FL) is a privacy-centric frame-work for distributed learning where devices collaborate to develop a shared global model while keeping their raw data local. Since workers may naturally form groups based on common objectives and privacy rules, we are motivated to extend FL to such settings. As workers can contribute to multiple groups, complexities arise in understanding privacy leakage and in adhering to privacy policies. In this paper, we propose differ-ential private overlapping grouped learning (DP-OGL), which shares learning across groups through common workers. We derive formal privacy guarantees between every pair of workers under the honest-but-curious threat model with multiple group memberships. Our experiments show that DP-OGL improves privacy-utility trade-offs compared to a baseline FL system.

The paper considers a communication constrained distributed hypothesis testing problem in which the transmitter sends a message about its local observation to the receiver, and the receiver tries to decide whether or not its own observation is independent of the observation at the transmitter. We analyze the problem in the one-shot setting and derive an achievability region under both the fixed-length and the variable-length communication constraints. Novel information-theoretic tools, including the generalized Poisson matching lemma and the strong functional representation lemma, are applied. It is shown that the proposed one-shot schemes, when applied to the asymptotic case, recover the optimal fixed-length and variable-length type-II error exponents for testing against independence.

We present two strategies to reduce the complexity of the alternating direction method of multipliers when applied to linear programming (ADMM-LP) decoding of low-density parity-check codes. First, to address the high complexity of computing a projection onto the parity polytope, the complexity bottleneck of ADMM-LP decoding, we propose the sparse affine projection algorithm (SAPA). SAPA projects onto the affine hull of χ ≤dnearby local codewords where the check degree isdand where χ can be significantly smaller thand. Unlike exact projection, SAPA does not require a water-filling process, and thus can be implemented with lower per-iteration complexity. Second, to reduce the number of effective iterations needed for ADMM-LP decoding, we propose a randomized layered scheduling framework. Rather than updating checks in round-robin fashion in each iteration, more “problematic” checks have a higher probability of being updated. The probability mass function that governs the selection of which checks to update is based upon the location of replica vectors inside (or on) the parity polytope. The resultant decoder converges significantly faster under this randomized scheduling than under round-robin scheduling. This makes it well suited for use in applications that limit the number of iterations.

We consider the problem of stragglers in distributed computing systems. Stragglers, which are compute nodes that unpredictably slow down, often increase the completion times of tasks. One common approach to mitigating stragglers is work replication, where only the first completion among replicated tasks is accepted, discarding the others. However, discarding work leads to resource wastage. In this article, we propose a method for exploiting the work completed by stragglers rather than discarding it. The idea is to increase the granularity of the assigned work, and to increase the frequency of worker updates. We show that the proposed method reduces the completion time of tasks via experiments performed on a simulated cluster as well as on Amazon EC2 with Apache Hadoop.

Distributed optimization is widely used to solve large-scale optimization problems by parallelizing gradient-based algorithms across multiple computing nodes. In asynchronous optimization, the optimization parameter is updated using stale gradients, which are gradients calculated with respect to out-of-date parameters. Although large degrees of staleness can slow convergence, little is known about the impact of staleness and its relation to other system parameters. In this work, we study and analyze centralized asynchronous optimization. We show that the process of gradient arrival to the master node is similar in nature to a renewal process. We derive bounds on expected staleness and show its connection to other system parameters such as the number of workers, expected compute time and communication delays. Our derivations can be used in existing convergence analyses to express convergence rates in terms of other known system parameters. Such an expression gives further details on what factors impact convergence.

We present the problem of two-terminal source coding with Common Sum Reconstruction (CSR). Consider two terminals, each with access to one of two correlated sources. Both terminals want to reconstruct the sum of the two sources under some average distortion constraint, and the reconstructions at two terminals must be identical with high probability. In this paper, we develop inner and outer bounds to the achievable rate distortion region of the CSR problem for a doubly symmetric binary source. We employ existing achievability results for Steinberg's common reconstruction and Wyner-Ziv's source coding with side information problems, and an achievability result for the lossy version of Körner-Marton's modulo-two sum computation problem.

Probabilistic shaping methods induce a desired nonuniform distribution on the transmitted symbols in order to realize a favorable trade-off between the communication rate and average transmission energy. In this work, we study a probabilistic shaping architecture wherein the central component is a binary linear code, employed as a lossy source code. The rate-distortion performance of the linear code directly determines the realized shaping rate-energy performance. We use this connection to establish the rate-energy optimality of the investigated shaping architecture. Although the primary focus of this paper is on shaping for two-symbol alphabets, extensions to non-binary alphabets will be briefly discussed.

Coded computing was recently introduced to mitigate the effect of stragglers on distributed computing systems. This paper combines ideas of approximate and coded computing to further accelerate computation. We propose approximated coded distributed computing (ACDC) that realizes a tradeoff between accuracy and speed, allowing the distributed computing system to produce approximations that increase in accuracy over time. If a sufficient number of compute nodes finish their tasks, ACDC exactly recovers the desired computation. We theoretically provide design guidelines for ACDC, and numerically show its benefits over previous methods.

We present a randomized schedule for alternating direction method of multipliers with linear programming (ADMM-LP) decoding of low-density parity check (LDPC) codes. The randomized schedule is based on horizontal layered decoding, where nodes are updated sequentially. Unlike existing layered decoding frameworks where all check nodes are updated exactly once per iteration, we propose a randomized schedule where more problematic nodes are updated more frequently. To do so, we sample from a probability mass function (PMF) over all check nodes and the check with sampled index is updated. The probability of each check to be updated is determined by its state. The PMF is constructed based on the distribution of replica (check) vectors inside or on the parity polytope. The randomized decoder usually converges faster than both standard and horizontal layered decoders, making it suitable for limited-iteration decoding in high-throughput applications.

We study the problem of community recovery from coarse measurements of a graph. In contrast to the problem of community recovery of a fully observed graph, one often encounters situations when measurements of a graph are made at low-resolution, each measurement integrating across multiple graph nodes. Such low-resolution measurements effectively induce a coarse graph with its own communities. Our objective is to develop conditions on the graph structure, the quantity, and properties of measurements, under which we can recover the community organization in this coarse graph. In this paper, we build on the stochastic block model by mathematically formalizing the coarsening process, and characterizing its impact on the community members and connections. Accordingly, we characterize an error bound for community recovery. The error bound yields simple and closed-form asymptotic conditions to achieve the perfect recovery of the coarse graph communities.

Elasticity is offered by cloud service providers to exploit under-utilized computing resources. The low-cost elastic nodes can leave and join any time during the computation cycle. The possibility of elastic events occurring together with the problem of slow nodes, referred to as stragglers, increases the uncertainty of the system, leading to computation delay. Recent results have shown that coded computing can be used to reduce the negative effect of elasticity and stragglers. In this paper, we propose two hierarchical coded elastic computing schemes that can further speed up the system by exploiting stragglers and effectively allocating tasks among available nodes. In our simulations, our scheme realizes 45% improvement in average finishing time compared to the state-of-the-art coded elastic computing scheme.

In distributed computing systems slow working nodes, known as stragglers, can greatly extend finishing times. Coded computing is a technique that enables straggler-resistant computation. Most coded computing techniques presented to date provide robustness by ensuring that the time to finish depends only on a set of the fastest nodes. However, while stragglers do compute less work than non-stragglers, in real-world commercial cloud computing systems (e.g., Amazon’s Elastic Compute Cloud (EC2)) the distinction is often a soft one. In this paper, we develophierarchicalcoded computing that exploits the work completed by all nodes, both fast and slow, automatically integrating the potential contribution of each. We first present a conceptual framework to represent the division of work amongst nodes in coded matrix multiplication as a cuboid partitioning problem. This framework allows us to unify existing methods and motivates new techniques. We then develop three methods of hierarchical coded computing that we termbit-interleavedcoded computation (BICC),multilevelcoded computation (MLCC), andhybridhierarchical coded computation (HHCC). In this paradigm, each worker is tasked with completing a sequence (a hierarchy) of ordered subtasks. The sequence of subtasks, and the complexity of each, is designed so that partial work completed by stragglers can be used, rather than ignored. We note that our methods can be used in conjunction with any coded computing method. We illustrate this by showing how we can use our methods to accelerate all previously developed coded computing techniques by enabling them to exploit stragglers. Under a widely studied statistical model of completion time, our approach realizes a 66% improvement in the expected finishing time. On Amazon EC2, the gain was 27% when stragglers are simulated.

Resistive memories store information in a crossbar arrangement of two-terminal devices that can be programmed to patterns of high or low resistance. While extremely compact, this technology suffers from the “sneak-path” problem: certain information patterns cannot be recovered, as multiple low resistances in parallel make a high resistance indistinguishable from a low resistance. In this paper, a multi-layer device is considered, and the number of bits it can store is derived exactly and asymptotic bounds are developed. The information density of a series of isolated arrays with extreme aspect ratios is derived in the single- and multi-layer cases with and without peripheral selection circuitry. This density is shown to be non-zero in the limit, unlike that of the arrays with moderate aspect ratios previously considered. A simple encoding scheme that achieves capacity asymptotically is presented.

We consider decentralized consensus optimization when workers sample data from non-identical distributions and perform variable amounts of work due to slow nodes known as stragglers. The problem of non-identical distributions and the problem of variable amount of work have been previously studied separately. In our work we analyse them together under a unified system model. We propose to combine worker outputs weighted by the amount of work completed by each. We prove convergence of the proposed method under perfect consensus, assuming straggler statistics are independent and identical across all workers for all iterations. Our numerical results show that under approximate consensus the proposed method outperforms the non-weighted scheme for both convex and non-convex objective functions.

We present convergence analysis of Anytime Minibatch with Delayed Gradients (AMB-DG) algorithm. In AMB-DG, workers compute gradients in epochs of fixed duration while the master uses stale gradients to update the optimization parameters. We analyze AMB-DG in terms of its regret bound and convergence rate. We present results for convex smooth objective functions which show that AMB-DG achieves the optimal regret bound and convergence rate. To complement our theoretical contribution, we deploy AMB-DG on SciNet, an academic high performance cloud computing platform, and compare its performance with that of the K-batch async scheme. K-batch async provides a baseline for schemes that exploit works completed by all workers while using stale gradients. In our experiments, for MNIST AMB-DG converges 2.45 times faster than K-batch async.

Gradient-based algorithms play an important role in solving a wide range of stochastic optimization problems. In recent years, implementing such schemes in parallel has become the new paradigm. In this work, we focus on the asynchronous implementation of gradient-based algorithms. In asynchronous distributed optimization, the gradient delay problem arises since optimization parameters may be updated using stale gradients. We consider a hub-and-spoke system and derive the expected gradient staleness in terms of other system parameters such as the number of nodes, communication delay, and the expected compute time. Our derivations provide a means to compare different algorithms based on the expected gradient staleness they suffer from.

A correction is made in the statement and proof of a lemma used to prove codeword symmetry. In addition, an important typo is noted and corrected.

Coded computation is a method to mitigate “stragglers” in distributed computing systems through the use of error correction coding that has lately received significant attention. First used in vector-matrix multiplication, the range of application was later extended to include matrix-matrix multiplication, heterogeneous networks, convolution, and approximate computing. A drawback to previous results is they completely ignore work completed by stragglers. While stragglers are slower compute nodes, in many settings the amount of work completed by stragglers can be non-negligible. Thus, in this work, we propose a hierarchical coded computation method that exploits the work completed by all compute nodes. We partition each node's computation into layers of sub-computations such that each layer can be treated as (distinct) erasure channel. We then design different erasure codes for each layer so that all layers have the same failure exponent. We propose design guidelines to optimize parameters of such codes. Numerical results show the proposed scheme has an improvement of a factor of 1.5 in the expected finishing time compared to previous work.

In cloud computing systems slow processing nodes, often referred to as “stragglers”, can significantly extend the computation time. Recent results have shown that error correction coding can be used to reduce the effect of stragglers. In this work we introduce a scheme that, in addition to using error correction to distribute mixed jobs across nodes, is also able to exploit the work completed by all nodes, including stragglers. We first consider vector-matrix multiplication and apply maximum distance separable (MDS) codes to small blocks of sub-matrices. The worker nodes process blocks sequentially, working block-by-block, transmitting partial per-block results to the master as they are completed. Sub-blocking allows a more continuous completion process, which thereby allows us to exploit the work of a much broader spectrum of processors and reduces computation time. We then apply this technique to matrix-matrix multiplication using product code. In this case, we show that the order of computing sub-tasks is a new degree of design freedom that can be exploited to reduce computation time further. We propose a novel approach to analyze the finishing time, which is different from typical order statistics. Simulation results show that the expected computation time decreases by a factor of at least two in compared to previous methods.

Recent advancements in polar coding have achieved practical performance competitive with other capacity-achieving codes such as low-density parity-check codes. In this paper, we propose a new family called irregular polar codes, where polarlization units are irregularly inactivated to achieve additional degrees of freedom for code design. We first discuss the code construction for irregular polar-coded modulation by taking non-uniform bit-reliability into consideration. We then apply the proposed polar codes to wireless massive multiple-input multiple- output (MIMO) communication channels. Simulation results show that the irregular polar codes can significantly reduce encoding/decoding complexity up to 50% while also yielding a marginal improvement in error rate performance.

We detail a field-programmable gate array (FPGA) based implementation of linear programming (LP) decoding. LP decoding frames error correction as an optimization problem. This is in contrast to variants of belief propagation (BP) that view error correction as a problem of graphical inference. LP decoding, when implemented with standard LP solvers, does not easily scale to the block-lengths of modern error-correction codes. This is the main challenge we surmount in this paper. In earlier work we demonstrated how to draw on decomposition methods from optimization theory to build an LP decoding solver competitive with BP, in terms of both performance and speed, but only in double-precision floating point. In this paper we translate the novel computational primitives of our new LP decoding technique into fixed-point. Using our FPGA implementation, we demonstrate that error-rate performance very close to double-precision is possible with 10-bit fixed-point messages.

Machine-to-machine (M2M) communications play an important role for applications that involve connections between a massive number of heterogeneous devices in home and industrial networks. For M2M networks, realizing low latency and high reliability is of great importance. In this paper, we show the great potential of polar-coded orthogonal frequency-division multiplexing (OFDM) to fulfill those requirements. We show that polar codes with list decoding plus cyclic redundancy check (CRC) can outperform state-of-the-art low-density parity-check (LDPC) codes at short block lengths. In addition, we introduce an efficient interleaver and constellation shaping for polar-coded high-order modulations, where a coded sequence is carefully mapped across subcarriers and modulation bits to exploit non-uniform reliability for higher diversity gains. Through computer simulations, we demonstrate that a significant gain greater than 2 dB can be achieved by quadratic polynomial permutation (QPP) interleaver with optimized parameters in comparison to the conventional random interleaver for high-order 256-ary quadrature-amplitude modulation (QAM) OFDM transmission in frequency-selective wireless channels.

In this paper we propose an approach to parallelizing synchronous stochastic gradient descent (SGD) that we term “Anytime-Gradients”. The Anytime-Gradients is designed to exploit the work completed by slow compute nodes or “stragglers”. In many approaches work completed by these nodes, while only partial, is discarded completely. To maintain synchronization in our approach, each computational epoch is of fixed duration, and at the end of each epoch, workers send updated parameter vectors to a master mode for combination. The master weights each update by the amount of work done. The Anytime-Gradients scheme is robust to both persistent and non-persistent stragglers and requires no prior knowledge about processor abilities. We show that the scheme effectively exploits stragglers and outperforms existing methods.

Compression of multispectal images is of great importance in an environment where resources such as computational power and memory are scarce. To that end, we propose a new extremely low-complexity encoding approach for compression of multispectral images, that shifts the complexity to the decoding. Our method combines principles from compressed sensing and distributed source coding. Specifically, the encoder compressively measures blocks of the band of interest and uses syndrome coding to encode the bitplanes of the measurements. The decoder has access to side information, which is used to predict the bitplanes and to decode them. The side information is also used to guide the reconstruction of the image from the decoded measurements. Our experimental results demonstrate significant improvement in the rate-distortion trade-off when compared to coding schemes with similar complexity.

Future servers will incorporate many active low-power modes for different system components, such as cores and memory. Though these modes provide flexibility for power management via Dynamic Voltage and Frequency Scaling (DVFS), they must be operated in a coordinated manner. Such coordinated control creates a combinatorial space of possible power mode configurations. Given the rapid growth of the number of cores, it is becoming increasingly challenging to quickly select the configuration that maximizes the performance under a given power budget. Prior power capping techniques do not scale well to large numbers of cores, and none of those works has considered memory DVFS. In this paper, we present FastCap, our optimization approach for system-wide power capping, using both CPU and memory DVFS. Based on a queuing model, FastCap formulates power capping as a non-linear optimization problem where we seek to maximize the system performance under a power budget, while promoting fairness across applications. Our FastCap algorithm solves the optimization online and efficiently (low complexity on the number of cores), using a small set of performance counters as input. To evaluate FastCap, we simulate it for a many-core server running different types of workloads. Our results show that FastCap caps power draw accurately, while producing better application performance and fairness than many existing CPU power capping methods (even after they are extended to use of memory DVFS as well).

In this paper, we introduce a new way of constructing and decoding multipermutation codes. Multipermutations are the permutations of a multiset that generally consist of duplicate entries. We first introduce a class of binary matrices called multipermutation matrices, each of which corresponds to a unique and distinct multipermutation. By enforcing a set of linear constraints on these matrices, we define a new class of codes that we term linear program (LP)-decodable multipermutation codes. In order to decode these codes using an LP, thereby enabling soft decoding, we characterize the convex hull of multipermutation matrices. This characterization allows us to relax the coding constraints to a polytope and to derive two LP decoding problems. These two problems are, respectively, formulated by relaxing the maximum likelihood decoding problem and the minimum Chebyshev distance decoding problem. Because these codes are non-linear, we also study efficient encoding and decoding algorithms. We first describe an algorithm that maps consecutive integers, one by one, to an ordered list of multipermutations. Based on this algorithm, we develop an encoding algorithm for a code proposed by Shieh and Tsai, a code that falls into our class of LP-decodable multipermutation codes. Regarding decoding algorithms, we propose an efficient distributed decoding algorithm based on the alternating direction method of multipliers. Finally, we observe from the simulation results that the soft decoding techniques we introduce can significantly outperform hard decoding techniques that are based on quantized channel outputs.

Linear programming (LP) decoding for low-density parity-check codes was introduced by Feldman et al. and has been shown to have theoretical guarantees in several regimes. Furthermore, it has been reported in the literature-via simulation and via instanton analysis-that LP decoding displays better error rate performance at high signal-to-noise ratios (SNR) than does belief propagation (BP) decoding. However, at low SNRs, LP decoding is observed to have worse performance than BP. In this paper, we seek to improve LP decoding at low SNRs while maintaining LP decoding's high SNR performance. Our main contribution is a new class of decoders obtained by applying the alternating direction method of multipliers (ADMM) algorithm to a set of non-convex optimization problems. These non-convex problems are constructed by adding a penalty term to the objective of LP decoding. The goal of the penalty is to make pseudocodewords, which are non-integer vertices of the LP relaxation, more costly. We name this class of decoders-ADMM penalized decoders. For low and moderate SNRs, we simulate ADMM penalized decoding with ℓ1and ℓ2penalties. We find that these decoders can outperform both BP and LP decoding. For high SNRs, where it is difficult to obtain data via simulation, we use an instanton analysis and find that, asymptotically, ADMM penalized decoding performs better than BP but not as well as LP. Unfortunately, since ADMM penalized decoding is not a convex program, we have not been successful in developing theoretical guarantees. However, the non-convex program can be approximated using a sequence of linear programs; an approach that yields a reweighted LP decoder. We show that a two-round reweighted LP decoder has an improved theoretical recovery threshold when compared with LP decoding. In addition, we find via simulation that reweighted LP decoding significantly attains lower error rates than LP decoding at low SNRs.

In this paper, we develop efficient decoders for non-binary low-density parity-check codes using the alternating direction method of multipliers (ADMM). We apply ADMM to two decoding problems. The first problem is linear programming (LP) decoding. In order to develop an efficient algorithm, we focus on non-binary codes in fields of characteristic two. This allows us to transform each constraint in F2m to a set of constraints in F2that has a factor graph representation. Applying ADMM to the LP decoding problem results in two types of non-trivial sub-routines. The first type requires us to solve an unconstrained quadratic program. We solve this problem efficiently by leveraging new results obtained from studying the above factor graphs. The second type requires Euclidean projections onto polytopes that are studied in the literature. Such projections can be solved efficiently using off-the-shelf techniques, which scale linearly in the dimension of the vector to project. ADMM LP decoding scales linearly with block length, linearly with check degree, and quadratically with field size. The second problem we consider is a penalized LP decoding problem. This problem is obtained by incorporating a penalty term into the LP decoding objective. The purpose of the penalty term is to make non-integer solutions (pseudocodewords) more expensive and hence to improve decoding performance. The ADMM algorithm for the penalized LP problem requires Euclidean projection onto a polytope formed by embedding the constraints specified by the non-binary single parity-check code, which can be solved by applying the ADMM technique to the resulting quadratic program. Empirically, this decoder achieves a much reduced error rate than LP decoding at low signal-to-noise ratios.

In this paper, we consider joint routing, scheduling, and resource allocation to maximize the throughput of OFDMA based wireless ad-hoc networks subject to MAC layer and network layer constraints. Comparing with previous work (e.g., Rashtchi et al., ICC 2012) that assumes each subchannel to be orthogonally accessed by all network links through time sharing, we schedule the orthogonal multiple access (e.g., CDMA) among the outgoing links of each node to each subchannel and treat the interferences caused by other nodes as noise. We propose an iterative heuristic approach to decompose the original problem into subproblems, each of which can be solved approximately through linearization. Simulations demonstrate that, particularly in large networks, our proposed cross-layer design significantly outperforms the previously proposed “orthogonal-only” access.

Alternating direction method of multipliers (ADMM) decoding is a new decoding framework for low-density parity-check (LDPC) codes. It can be used to implement linear programming (LP) decoding or penalized LP decoding. Similar to belief propagation (BP) decoding, ADMM decoding consists of local “check” and “variable updates”. However, ADMM decoding performs better than BP at high signal-to-noise ratios (SNRs). To understand why these two locally operating algorithms result in different error floor behaviors, we study the dynamics of ADMM decoding in this paper. In particular, we focus on trapping sets, which are observed to cause error floors in ADMM decoding. Our results show that the dynamics of ADMM decoding on trapping sets can be characterized as a jump linear system. Furthermore, these results indicate that the Lagrange multipliers involved in ADMM play an important role in correcting trapping set errors. Finally, we present simulation results that support this understanding.

LP-decodable multipermutation codes are a class of multipermutation codes that can be decoded using linear programming (LP). These codes are defined using linearly constrained multipermutation matrices, which are binary matrices that satisfy particular row sum and column sum constraints. Although generic LP solvers are capable of solving the LP decoding problem, they are not efficient in general because they do not leverage structures of the problem. This motivates us to study efficient decoding algorithms. In this paper, we focus on encoding and decoding algorithms for LP-decodable multipermutation codes. We first describe an algorithm that “ranks” multipermutations. In other words, it maps consecutive integers, one by one, to an ordered list of multipermutations. By leveraging this algorithm, we develop an encoding algorithm for a code proposed by Shieh and Tsai. Regarding decoding algorithms we propose an iterative decoding algorithm based on the alternating direction method of multipliers (ADMM), each iteration of which can be solved efficiently using off-the-shelf techniques. Finally, we study decoding performances of different decoders via simulation.

Many code constraints can be represented using factor graphs. By relaxing these factorable coding constraints to linear constraints, it is straightforward to form a decoding optimization problem. Furthermore, by pairing these factor graphs with the alternating directions method of multipliers (ADMM) technique of large-scale optimization, one can develop distributed algorithms to solve the decoding optimization problems. However, the non-trivial part has always been developing an efficient algorithm for the subroutines of ADMM, which directly relates to the geometries of the relaxed coding constraints. In this paper, we focus on summarizing existing results and distilling insights to these problems. First, we review the ADMM formulation and geometries involved in the subroutines. Next, we present a linear time algorithm for projecting onto an ℓ1ball with box constraints.

We consider the secret key generation problem when sources are randomly excited by the sender and there is a noiseless public discussion channel. Our setting is thus similar to recent works on channels with action-dependent states, where the channel state may be influenced by some of the parties involved. We derive single-letter expressions for the secret key capacity through a type of source emulation analysis. We also derive lower bounds on the achievable reliability and secrecy exponents, i.e., the exponential rates of decay of the probability of decoding error and of the information leakage. These exponents allow us to determine a set of strongly achievable secret key rates. For degraded eavesdroppers, the maximum strongly achievable rate equals the secret key capacity; our exponents can also be specialized to previously known results. In deriving our strong achievability results, we introduce a coding scheme that combines wiretap coding (to excite the channel) and key extraction (to distill keys from residual randomness). The secret key capacity is naturally seen to be a combination of both source- and channel-type randomness. Through examples, we illustrate a fundamental interplay between the portion of the secret key rate due to each type of randomness. We also illustrate inherent tradeoffs between the achievable reliability and secrecy exponents. Our new scheme also naturally accommodates rate limits on the public discussion. We show that under rate constraints, we are able to achieve larger rates than those that can be attained through a pure source emulation strategy.

We study a form of unequal error protection that we term unequal message protection (UMP). The message set of a UMP code is a union of m disjoint message classes. Each class has its own error protection requirement, with some classes needing better error protection than others. We analyze the tradeoff between rates of message classes and the levels of error protection; our analysis reveals new tradeoffs, which were not captured by prior works on UMP codes. To obtain our results, we generalize finite block length achievability and converse bounds due to Polyanskiy-Poor-Verdú. We evaluate our bounds for the binary symmetric and binary erasure channels, and analyze the asymptotic characteristic of the bounds in the fixed error and moderate deviations regimes. In addition, we consider two questions related to the practical construction of UMP codes. First, we study a header construction that prefixes the message class into a header followed by data protection using a standard homogeneous (classical) code. We show that, in general, this construction is not optimal at finite block lengths. We further demonstrate that our main UMP achievability bound can be obtained using coset codes, which suggests a path to implementation of tractable UMP codes.

Power consumption in data centers has been growing significantly in recent years. To reduce power, servers are being equipped with increasingly sophisticated power management mechanisms. Different mechanisms offer dramatically different trade-offs between power savings and performance penalties. Considering the complexity, variety, and temporally-varying nature of the applications hosted in a typical data center, intelligently determining which power management policy to use and when is a complicated task. In this paper we analyze a system model featuring both performance scaling and low-power states. We reveal the interplay between performance scaling and low-power states via intensive simulation and analytic verification. Based on the observations, we present SleepScale, a runtime power management tool designed to efficiently exploit existing power control mechanisms. At run time, SleepScale characterizes power consumption and quality-of-service (QoS) for each low-power state and frequency setting, and selects the best policy for a given QoS constraint. We evaluate SleepScale using workload traces from data centers and achieve significant power savings relative to conventional power management strategies.

Linear programming (LP) decoding using the alternating direction method of multipliers (ADMM) has been shown to be an efficient algorithm. A non-convex variation based on the ADMM LP decoder called the ADMM penalized decoder was introduced by Liu et al. (IEEE ITW, Sep. 2012) to close the signal-to-noise ratio (SNR) gap between LP decoding and classic belief propagation (BP) decoding. This algorithm was shown to achieve or outperform BP decoding at all SNRs, including high SNRs where BP decoding suffers from the error floor effect. In this paper, we study the behaviors of the ADMM penalized decoder at high SNRs where simulation is infeasible. We use a generic tool called instanton analysis and propose an instanton search algorithm for the ADMM penalized decoder. We then apply the algorithm to the [155, 64] Tanner code and a [1057, 813] LDPC code. We show that the instanton information we obtained provides good predictions for word-error-rate curve at high SNRs. In addition, our results suggest that the ADMM penalized decoder can suffer from trapping sets.

In this paper, we develop an efficient algorithm for linear programming (LP) decoding of non-binary low-density parity-check (LDPC) codes. We build our algorithm on the decomposition method based on the alternating direction method of multipliers (ADMM). Although expressing the LP decoding problem using ADMM is not hard, a sub-routine of ADMM - projection onto a polytope formed from embeddings of the non-binary single parity-check code - is not straightforward. In this work, we focus on non-binary codes in fields of characteristic two. This allows us to use operations in F2to relax the polytope under consideration into a form that is computational friendly. We introduce a rotation step that normalizes the geometry under consideration. We then apply ADMM a second time to solve the projection problem, which is a quadratic program (QP). Our decoding algorithm scales linearly with block length, linearly with check degree, and quadratically with field size.

We study the problem of lossless joint source-channel coding (JSCC) in the finite block length regime from an unequal message protection (UMP) perspective. We demonstrate that the problem of lossless JSCC can be cast in terms of UMP codes previously studied. We show that an optimal JSCC can be constructed from a matched UMP code. We further derive a finite block length bound that characterizes the performance of a JSCC constructed from a UMP code not perfectly matched to the source. This bound is evaluated for a binary memoryless source transmitted over a binary symmetric channel. Two-class schemes previously studied in literature are compared with the proposed scheme. Empirically the JSCCs based on UMP codes approach the performance of the optimal matched code quite fast in number of classes used.

We study achievability bounds for a class of unequal error protection codebooks with m > 1 different classes of codewords called unequal message protection (UMP) codes. We extend the dependence testing bound due to Polyanskiy-Poor-Verdú to be applicable to UMP codes and use this extension to obtain refined asymptotic expansions for the performance of such codes over discrete memoryless channels. In addition, we consider two questions related to the practical construction of UMP codes. First, we study a “header” construction that prefixes the message class into a header followed by data protection using a standard homogeneous (classical) code. We show that, in general, this construction is not optimal at finite block lengths. We further demonstrate that our main UMP achievability bound can be obtained using coset codes, which suggests a path to tractable implementation of UMP codes.

Distributed source coding is traditionally viewed in a block coding context wherein all source symbols are known in advance by the encoders. However, many modern applications to which distributed source coding ideas are applied, are better modeled as having streaming data. In a streaming setting, source symbol pairs are revealed to separate encoders in real time and need to be reconstructed at the decoder with subject to some tolerable end-to-end delay. In this paper, a causal sequential random binning encoder is introduced and paired with maximum likelihood (ML) and universal decoders. The latter uses a novel weighted empirical suffix entropy decoding rule. We derive a lower bounds on the error exponent with delay for each decoder. We also provide upper bounds for the special case of streaming with decoder side information and discuss when upper and lower bounds match. We show that both ML and universal decoders achieve the same (positive) error exponents for all rate pairs inside the Slepian-Wolf achievable rate region. The dominant error events in streaming are different from those in block-coding and result in different exponents. Because the sequential random binning scheme is also universal over delays, the resulting code eventually reconstructs every source symbol correctly with probability one.

We consider the sequential transmission of a stream of messages over a block-fading multi-input-multi-output channel. A new message arrives at the beginning of each coherence block, and the decoder is required to output each message sequentially, after a delay of T coherence blocks. In the special case when T = 1, the setup reduces to the quasi-static fading channel. We establish the optimal diversity-multiplexing tradeoff (DMT) in the high signal-to-noise-ratio (SNR) regime, and show that it equals T times the DMT of the quasi-static channel. The converse is based on utilizing the delay constraint to amplify a local outage event associated with a message, globally across all the coherence blocks. This approach appears to be new. We propose two coding schemes that achieve the optimal DMT. The first scheme involves interleaving of messages, such that each message is transmitted across T consecutive coherence blocks. This scheme requires the knowledge of the delay constraint at both the encoder and decoder. Our second coding scheme involves a sequential tree code and is delay universal, i.e., the knowledge of the decoding delay is not required by the encoder. However, in this scheme, we require the coherence block length to increase as log (SNR), in order to attain the optimal DMT. Finally, we discuss the case when multiple messages arrive at uniform intervals within each coherence period. Through a simple example, we exhibit the suboptimality of interleaving and propose another scheme that achieves the optimal DMT.

We study converse bounds for unequal error protection codebooks with k > 1 different classes of codewords. We dub these unequal error protection codes “assorted codes”. We extend a finite blocklength converse bound due to Polyanskiy-Poor-Verdú to apply to assorted codes and use this extension to obtain a refined asymptotic expansion for the performance of assorted codes over a discrete memoryless channel. Our main contribution is to demonstrate that there is indeed a loss in the rates of an assorted code compared to equivalent homogeneous (classical) codes. Notably, when the number of codeword classes is polynomial in blocklength n the loss is apparent in the third order O(log n) term of the asymptotic expansion of the logarithm of the maximum number of codewords. This is in sharp contrast to the previous literature which only considers this problem within regimes where no such loss could be observed.

This paper investigates generation of a secret key from a reciprocal wireless channel. In particular we consider wireless channels that exhibit sparse structure in the wideband regime and study the impact of sparsity on the secret key capacity. We explore this problem in two steps. First, we study key generation from a state-dependent discrete memoryless multiple source. The state of the source captures the effect of channel sparsity. Secondly, we consider a wireless channel model that captures channel sparsity and correlation between the legitimate users' channel and the eavesdropper's channel. Such dependency can significantly reduce the secret key capacity. According to system delay requirements, two performance measures are considered: (i) ergodic secret key capacity and (ii) outage probability. We show that in the wideband regime when a white sounding sequence is adopted, a sparser channel can achieve a higher ergodic secret key rate than a richer channel can. For outage performance, we show that if the users generate secret keys at a fraction of the ergodic capacity, the outage probability will decay exponentially in signal bandwidth. Moreover, a larger exponent is achieved by a richer channel.

When binary linear error-correcting codes are used over symmetric channels, a relaxed version of the maximum likelihood decoding problem can be stated as a linear program (LP). This LP decoder can be used to decode error-correcting codes at bit-error-rates comparable to state-of-the-art belief propagation (BP) decoders, but with significantly stronger theoretical guarantees. However, LP decoding when implemented with standard LP solvers does not easily scale to the block lengths of modern error correcting codes. In this paper, we draw on decomposition methods from optimization theory, specifically the alternating direction method of multipliers (ADMM), to develop efficient distributed algorithms for LP decoding. The key enabling technical result is a “two-slice” characterization of the parity polytope, the polytope formed by taking the convex hull of all codewords of the single parity check code. This new characterization simplifies the representation of points in the polytope. Using this simplification, we develop an efficient algorithm for Euclidean norm projection onto the parity polytope. This projection is required by the ADMM decoder and its solution allows us to use LP decoding, with all its theoretical guarantees, to decode large-scale error correcting codes efficiently. We present numerical results for LDPC codes of lengths more than 1000. The waterfall region of LP decoding is seen to initiate at a slightly higher SNR than for sum-product BP, however an error floor is not observed for LP decoding, which is not the case for BP. Our implementation of LP decoding using the ADMM executes as fast as our baseline sum-product BP decoder, is fully parallelizable, and can be seen to implement a type of message-passing with a particularly simple schedule.

Consider the following unequal error protection scenario. One special message, dubbed the “red alert” message, is required to have an extremely small probability of missed detection. The remainder of the messages must keep their average probability of error and probability of false alarm below a certain threshold. The goal then is to design a codebook that maximizes the error exponent of the red alert message while ensuring that the average probability of error and probability of false alarm go to zero as the blocklength goes to infinity. This red alert exponent has previously been characterized for discrete memoryless channels. This paper completely characterizes the optimal red alert exponent for additive white Gaussian noise channels with block power constraints.

We present an approach to designing capacity-approaching high-girth low-density parity-check (LDPC) codes that are friendly to hardware implementation, and compatible with some desired input code structure defined using a protograph. The approach is based on a mapping of any class of codes defined using a protograph into a family of hierarchical quasi-cyclic (HQC) LDPC codes. Whereas the parity check matrices of standard quasi-cyclic (QC) LDPC codes are composed of circulant submatrices, those of HQC LDPC codes are composed of a hierarchy of circulant submatrices that are, in turn, constructed from circulant submatrices, and so on, through some number of levels. Next, we present a girth-maximizing algorithm that optimizes the degrees of freedom within the family of codes to yield a high-girth HQC LDPC code, subject to bounds imposed by the fact that HQC codes are still quasi-cyclic. Finally, we discuss how certain characteristics of a code protograph will lead to inevitable short cycles and show that these short cycles can be eliminated using a “squashing” procedure that results in a high-girth QC LDPC code, although not a hierarchical one. We illustrate our approach with three design examples of QC LDPC codes-two girth-10 codes of rates 1/3 and 0.45 and one girth-8 code of rate 0.7-all of which are obtained from protographs of one-sided spatially coupled codes.

In this paper, we aim to develop scheduling policies to maximize the stability region of a wireless network under the assumption that mutual information accumulation is implemented at the physical layer. This enhanced physical layer capability enables the system to accumulate information even when the link between two nodes is not good and a packet cannot be decoded within a slot. The result is an expansion of the stability region of the system. The accumulation process does not satisfy the i.i.d assumption that underlies many previous analysis in this area. Therefore it also brings new challenges to the problem. We propose two dynamic scheduling algorithms to overcome this difficulty. One performs scheduling every T slot, which inevitably increases average delay in the system, but approaches the boundary of the stability region. The second constructs a virtual system with the same stability region. Through controlling the virtual queues in the constructed system, we avoid the non-i.i.d difficulty and attain the stability region. We derive performance bounds under both algorithms and compare them through simulation results.

A key challenge in wireless networking is the management of interference between transmissions. Identifying which transmitters interfere with each other is crucial. Complicating this task is the fact that the topology of wireless networks can change from time to time, and so the identification process may need to be carried out on a regular basis. Injecting active probing traffic to assess interference can lead to unacceptable overhead, and so this paper focuses on interference estimation based on passive traffic monitoring in networks that use the CSMA/CA (Carrier Sense Multiple Access/Collision Avoidance) protocol. A graph is used to represent the interference in the network, where the nodes represent transmitters and edges represent interference between pairs of transmitters. We investigate the problem of learning the graph structure based on passive observations of network traffic transmission patterns and information about successes or failures in transmissions. Previous work has focused on algorithms and validations in small testbed networks. This paper focuses on the scaling behavior of such methods which is unaddressed in prior work. In particular we establish bounds on the minimum observation period required to identify the interference graph reliably. The main results are expressed in terms of the total number of nodes n and the maximum number of interfering transmitters per node (i.e., maximum node degree) d. The effects of hidden terminal interference (i.e., interference not detectable via carrier sensing) on the observation time requirement are also quantified. We show that it is necessary and sufficient that the observation period grows like d2log n, and we propose a practical algorithm that reliably identifies the graph from this length of observation. We conclude that the observation requirements scale quite mildly with network size, and that the networks with sparse interference patterns can be more rapidly identified than those with dense interference patterns.

In this paper, we present a new class of decoders for low density parity check (LDPC) codes. We are motivated by the observation that the linear programming (LP) decoder has worse error performance than belief propagation (BP) decoders at low SNRs. We base our new decoders on the alternating direction method of multipliers (ADMM) decomposition technique for LP decoding. The ADMM not only efficiently solves the LP decoding problem, but also makes it possible to explore other decoding algorithms. In particular, we add various penalty terms to the linear objective of LP decoding with the goal of suppressing pseudocodewords. Simulation results show that the new decoders achieve much better error performance compared to LP decoder at low SNRs. What is more, similar to the LP decoder, no error floor is observed at high SNRs.

We design and analyze a method to extract secret keys from the randomness inherent to wireless channels. We study a channel model for a multipath wireless channel and exploit the channel diversity in generating secret key bits. We compare the key extraction methods based both on entire channel state information (CSI) and on single channel parameter such as the received signal strength indicators (RSSI). Due to the reduction in the degree-of-freedom when going from CSI to RSSI, the rate of key extraction based on CSI is far higher than that based on RSSI. This suggests that exploiting channel diversity and making CSI information available to higher layers would greatly benefit the secret key generation. We propose a key generation system based on low-density parity-check (LDPC) codes and describe the design and performance of two systems: one based on binary LDPC codes and the other (useful at higher signal-to-noise ratios) based on four-ary LDPC codes.

We present a theoretical framework for the analysis of privacy and security trade-offs in secure biometric authentication systems. We use this framework to conduct a comparative information-theoretic analysis of two biometric systems that are based on linear error correction codes, namely fuzzy commitment and secure sketches. We derive upper bounds for the probability of false rejection$(P_{FR})$and false acceptance$(P_{FA})$for these systems. We use mutual information to quantify the information leaked about a user's biometric identity, in the scenario where one or multiple biometric enrollments of the user are fully or partially compromised. We also quantify the probability of successful attack$(P_{SA})$based on the compromised information. Our analysis reveals that fuzzy commitment and secure sketch systems have identical$P_{FR}$,$P_{FA}$,$P_{SA}$, and information leakage, but secure sketch systems have lower storage requirements. We analyze both single-factor (keyless) and two-factor (key-based) variants of secure biometrics, and consider the most general scenarios in which a single user may provide noisy biometric enrollments at several access control devices, some of which may be subsequently compromised by an attacker. Our analysis highlights the revocability and reusability properties of key-based systems and exposes a subtle design trade-off between reducing information leakage from compromised systems and preventing successful attacks on systems whose data have not been compromised.

We study the fundamental limits to secret key generation from an excited distributed source (EDS). In an EDS, a pair of terminals observe dependent sources of randomness excited by a pre-arranged signal. We first determine the secret key capacity for such systems with one-way public messaging. We then characterize a tradeoff between the secret key rate and exponential bounds on the probability of key agreement failure and on the secrecy of the key generated. We find that there is a fundamental tradeoff between reliability and secrecy.

This paper establishes information-theoretic limits for estimating a finite-field low-rank matrix given random linear measurements of it. These linear measurements are obtained by taking inner products of the low-rank matrix with random sensing matrices. Necessary and sufficient conditions on the number of measurements required are provided. It is shown that these conditions are sharp and the minimum-rank decoder is asymptotically optimal. The reliability function of this decoder is also derived by appealing to de Caen's lower bound on the probability of a union. The sufficient condition also holds when the sensing matrices are sparse—a scenario that may be amenable to efficient decoding. More precisely, it is shown that if the$n\times n$-sensing matrices contain, on average,$\Omega ({n}{\log n})$entries, the number of measurements required is the same as that when the sensing matrices are dense and contain entries drawn uniformly at random from the field. Analogies are drawn between the aforementioned results and rank-metric codes in the coding theory literature. In fact, we are also strongly motivated by understanding when minimum rank distance decoding of random rank-metric codes succeeds. To this end, we derive minimum distance properties of equiprobable and sparse rank-metric codes. These distance properties provide a precise geometric interpretation of the fact that the sparse ensemble requires as few measurements as the dense one.

The increasing power consumption of processors has made power reduction a first-order priority in processor design. Voltage scaling is one of the most powerful power-reduction techniques introduced to date, but is limited to some minimum voltageVDDMIN. BelowVDDMINon-chip SRAM cells cannot all operate reliably due to increased process variability with technology scaling. The use of larger SRAM cells, which are less sensitive to process variability, allows a reduction inVDDMIN. However, since the large-scale memory structures such as last-level caches (LLCs) often determine theVDDMINof processors, these structures cannot afford to use large SRAM cells due to the resulting increase in die area. In this paper we first propose a joint optimization of LLC cell size, the number of redundant cells, and the strength of error-correction coding (ECC) to minimize total SRAM area while meeting yield andVDDMINtargets. The joint use of redundant cells and ECC enables the use of smaller cell sizes while maintaining design targets. Smaller cell sizes more than make up for the extra cells required by redundancy and ECC. In 32-nm technology our joint approach yields a 27% reduction in total SRAM area (including the extra cells) when targeting 90% yield and 600 mVVDDMIN. Second, we demonstrate that the ECC used to repair defective cells can be combined with a simple architectural technique, which can also fix particle-induced soft errors, without increasing ECC strength or processor runtime.

To date dynamic voltage/frequency scaling (DVFS) has been one of the most successful power-reduction techniques. However, ever-increasing process variability reduces the reliability of static random access memory (SRAM) at low voltages. This limits voltage scaling to a minimum operating voltage (VDDMIN). Larger SRAM cells, that are less sensitive to process variability, allow the use of lower VDDMIN. However, large-scale memory structures, e.g., the last-level cache (LLC) (that often determines the VDDMINof the processor), cannot afford to use such large SRAM cells due to the die area constraint. In this paper we propose low-voltage LLC architectures that exploit 1) the DVFS characteristics of workloads running on high-performance processors, 2) the trade-off between SRAM cell size and VDDMIN, and 3) the fact that at lower voltage/frequency operating states the negative performance impact of having a smaller LLC capacity is reduced. Our proposed LLC architectures provide the same maximum performance and VDDMINas the conventional architecture, while reducing the total LLC cell area by 15%-19% with negligible average runtime increase.

In this paper we quantify an achievable error-exponent for the problem of content identification from a large database based on noisy queries.

We study delay constrained sequential streaming over block fading channels. The transmitter observes a stream of messages, one message in each coherence block, and the receiver needs to output a sequence of messages, each with a fixed delay of T coherence blocks. We characterize the associated diversity-multiplexing tradeoff (DMT) for this model. The proposed coding scheme involves a semi-infinite random Gaussian tree-code and a sequential decision directed decoder. The converse applies an outage amplification argument that exploits the delay constraint to amplify the error event associated with a single message to an entire sequence of messages.

This paper establishes information-theoretic limits in estimating a finite field low-rank matrix given random linear measurements of it. Necessary and sufficient conditions on the number of measurements required are provided. It is shown that these conditions are sharp. The reliability function associated to the minimum-rank decoder is also derived. Our bounds hold even in the case where the sensing matrices are sparse. Connections to rank-metric codes are discussed.

Cooperation between the nodes of wireless multihop networks can increase communication reliability, reduce energy consumption, and decrease latency. The possible improvements are even greater when nodes perform mutual information accumulation. In this paper, we investigate resource allocation for unicast and multicast transmission in such networks. Given a network, a source, and a destination, our objective is to minimize end-to-end transmission delay under energy and bandwidth constraints. We provide an algorithm that determines which nodes should participate in forwarding the message and what resources (time, energy, bandwidth) should be allocated to each. Our approach factors into two sub-problems, each of which can be solved efficiently. For any transmission order we show that solving for the optimum resource allocation can be formulated as a linear programming problem. We then show that the transmission order can be improved systematically by swapping nodes based on the solution of the linear program. Solving a sequence of linear programs leads to a locally optimal solution in a very efficient manner. In comparison to the proposed cooperative routing solution, it is observed that conventional shortest path multihop routing typically incurs additional delays and energy expenditures on the order of 70%. Drawing inspiration from this first, centralized, algorithm, we also present two distributed algorithms. These algorithms require only local channel state information. Simulations indicate that they yield solutions about two to five percent less efficient than the centralized algorithm.

The “Divide and Concur” (DC) algorithm introduced by Gravel and Elser can be considered a competitor to the belief propagation (BP) algorithm, in that both algorithms can be applied to a wide variety of constraint satisfaction, optimization, and inference problems. We show that DC can be interpreted as a message-passing algorithm on a “normal” factor graph. The “difference-map” dynamics of the DC algorithm enables it to avoid “traps” which may be related to the “trapping sets” or “pseudo-codewords” that plague BP decoders of low-density parity check (LDPC) codes in the error-floor regime. We investigate two decoders for LDPC codes based on these ideas. The first decoder is based directly on DC, while the second decoder borrows the important “difference-map” concept from the DC algorithm and translates it into a BP-like decoder. We show that this “difference-map belief propagation” (DMBP) decoder has dramatically improved error-floor performance compared to standard BP decoders, while maintaining a similar computational complexity. We present simulation results for LDPC codes comparing DC and DMBP decoders with other decoders based on sum-product BP, linear programming, and mixed-integer linear programming. We also describe the close relation of the DMBP decoder to reweighted min-sum algorithms, including those recently proposed by Ruozzi and Tatikonda.

The increasing power consumption of processors has made power reduction a first-order priority in their design. Voltage scaling is one of the most successful power-reduction techniques introduced to date, but it is limited to some minimum voltage, VDDMIN, below which all components cannot operate reliably. In particular, ever-increasing process variability due to shrinking feature size further degrades the low-voltage reliability of, e.g., SRAM cells. Larger SRAM cells are less sensitive to process variability and their use would allow a reduction in VDDMIN. However, large-scale memory structures, e.g., last-level caches (LLCs) that often determine the VDDMIN of processors, cannot afford to use such large SRAM cells due to the resulting increase in die area. In this paper we propose a joint optimization of LLC cell size, number of redundant cells, and ECC (error-correction coding) strength to minimize total SRAM area while meeting target yields and VDDMIN. The use of redundant cells and ECC enable the use of smaller cell sizes while maintaining target yields and VDDMIN. Smaller cell sizes more than make up for the extra cells required by redundancy and ECC. We first assess each approach individually, i.e., only redundancy or ECC for various cell sizes. We then consider a combined approach and observe significant improvements. For example, in 32nm technology our combined approach yields a 27% reduction in total SRAM area (including redundant cells) when targeting a VDDMIN of 600mV.

We study secret key generation from reciprocal multipath wireless channels modeled as multiple parallel fading channels. We consider two channel characteristics that heavily impact secret key capacity: channel sparsity and correlation between main and eavesdropper's channels. We propose a joint model to capture the channel sparsity and correlated eavesdropping. For the case without eavesdroppers, we show that at each transmitter SNR γ there is an optimal sparsity 0 ≤ ρopt≤ 1, which specifies the fraction of non-zero channel coefficients, that yields the maximum secret key capacity. The reduction in secret key capacity due to eavesdropping is due to two sources. First is the overlap between the main and eavesdropper channels, i.e., the pattern of non-zero subchannels common to both. The second is the correlation between the channel coefficients of the overlapping channels. We show that when the power of the training signal is uniformly distributed over the non-zero channels, there is a cutoff SNR γcbelow which the secret key rate is zero, but non-zero (and increasing in γ) when γ > γc. We also show that in the low SNR regime, the optimal input signal is peaky (a non-uniform training signal) by which the secret key capacity is non-zero at all γ > 0.

In this paper we bound the reliability function of decoding with errors and erasures for a streaming multiple-access channel with feedback. We show that, subject to an arbitrarily small bound on the probability of erasure, the best known lower bound on the reliability function (i.e., achievable error exponent) for the single-user version of our problem can also be achieved in the multi-user setting for high sum-rates. In other words, at high rates the interference of another user need not decrease the achievable error exponent of either.

We develop compressed sensing results for sources drawn from finite alphabets. We apply tools from linear coding and large deviations. We establish strong connections between our results and error exponents of lossless source coding in the case of no measurement noise, and modified channel coding error exponents in the case of measurement noise. We connect to standard results on compressed sensing in the real field.

We study fundamental limits on the generation of secret keys based on the randomness inherent to reciprocal wireless multipath channels. Estimates of the common channel at the two ends of a link are jointly Gaussian sources from which secret keys can be generated. The key generation problem is cast as an equivalent communication problem to characterize the secret key capacity. We analyze the low-SNR regime to quantify the minimum energy per secret key bit required for reliable key acquisition. Our results show that, in contrast to the low SNR behavior of conventional channel capacity, there is a non-zero SNR ¿* that achieves the minimum energy per key bit. A time-sharing scheme is proposed to achieve the minimum energy per key bit at any SNR below ¿*. We also investigate the reliability of secret key generation via error exponent analysis. In particular, our results yield a tight upper bound on the minimum energy required to generate a finite-length key with a specified probability of error in key acquisition.

In this paper we present a three-stage decoding strategy that combines quantized and un-quantized belief propagation (BP) decoders with a mixed-integer linear programming (MILP) decoder. Each decoding stage is activated only when the preceding stage fails to converge to a valid codeword. The faster BP decoding stages are able to correct most errors, yielding a short average decoding time. Only in the rare cases when the iterative stages fail is the slower but more powerfulMILP decoder used. The MILP decoder iteratively adds binary constraints until either the maximum likelihood codeword is found or some maximum number of binary constraints has been added. Simulation results demonstrate a large improvement in the word error rate (WER) of the proposed multi-stage decoder in comparison to belief propagation. The improvement is particularly noticeable in the low crossover probability (error floor) regime. Through introduction of an accelerated ¿active-set¿ version of the quantized BP decoder we significantly speed up the pace of simulation to simulate low density parity check (LDPC) codes of length up to around 2000 down to a WER of around 10-10on the binary symmetric channel. We demonstrate that for certain codes our approach can efficiently approach the optimal ML decoding performance for low crossover probabilities.

Rateless coding has recently been the focus of much practical as well as theoretical research. In this paper, rateless codes are shown to find a natural application in channels where the channel law varies unpredictably. Such unpredictability means that to ensure reliable communication block codes are limited by worst case channel variations. However, the dynamic decoding nature of rateless codes allows them to adapt opportunistically to channel variations. If the channel state selector is not malicious, but also not predictable, decoding can occur earlier, producing a rate of communication that can be much higher than the worst case. The application of rateless or ldquofountainrdquo codes to the binary erasure channel (BEC) can be understood as an application of these ideas. Further, this sort of decoding can be usefully understood as an incremental form of erasure decoding. The use of ideas of erasure decoding result in a significant increase in reliability.

Cooperation between the nodes of wireless multi-hop networks can increase communication reliability, reduce energy consumption, and decrease latency. The possible improvements are even greater when nodes perform mutual-information accumulation, e.g., by using rateless codes. In this paper, we investigate routing problems in such networks. Given a network, a source and a destination, our objective is to minimize end-to-end transmission delay under a sum energy constraint. We provide an algorithm that determines which nodes should participate in forwarding the message and what resources (time, energy, bandwidth) should be allocated to each. Our approach factors into two sub-problems, each of which can be solved efficiently. For any node decoding order we show that solving for the optimum resource allocation can be formulated as a linear problem. We then show that the decoding order can be improved systematically by swapping nodes based on the solution of the linear program. Solving a sequence of linear program leads to a locally optimum solution in a very efficient manner. In comparison to the cooperative routings, it is observed that conventional shortest-path multihop routings incur additional delays and energy expenditures on the order of 70%. Since this initial solution is centralized, requiring full channel state information, we exploit the insights to design two distributed routing algorithms that require only local channel state information. We provide simulations showing that in the same networks the distributed algorithms find routes that are only about 2-5% less efficient than the centralized solution.

Though the schemes are different, both Horstein's and Kudryashov's non-block strategies for communication with feedback over the binary-symmetric channel asymptotically achieve the identical reliability function (error exponent); a function that displays some curious features. For positive rates it is strictly larger than Burnashev's reliability function and transitions discontinuously at the channel capacity from a strictly positive value to zero. The purpose of this paper is to connect this reliability function to familiar coding contexts and to demonstrate that it provides an upper bound on the error exponents achievable in these contexts. We first show that this function gives a lower bound on the minimum probability of decoding error across codewords in a block-coding context with (or without) feedback. We then show that the same reliability function also gives an upper bound on the maximum probability of bit error in a non-block "streaming" context where noiseless feedback is available and the destination is (occasionally) allowed to declare erasures (per Forney). The basic insight underlying the bound leads to the moniker the "hallucination" bound.

We present an information-theoretically secure biometric storage system using graph-based error correcting codes in a Slepian-Wolf coding framework. Our architecture is motivated by the noisy nature of personal biometrics and the requirement to provide security without storing the true biometric at the device. The principal difficulty is that real biometric signals, such as fingerprints, do not obey the i.i.d. or ergodic statistics that are required for the underlying typicality properties in the Slepian-Wolf coding framework. To meet this challenge, we propose to transform the biometric data into binary feature vectors that are i.i.d. Bernoulli(0.5), independent across different users, and related within the same user through a BSC-p channel with small p< 0.5. Since this is a standard channel model for LDPC codes, the feature vectors are now suitable for LDPC syndrome coding. The syndromes serve as secure biometrics for access control. Experiments on a fingerprint database demonstrate that the system is information-theoretically secure, and achieves very low false accept rates and low false reject rates.

Hardware signatures have been recently proposed as an efficient mechanism to detect conflicts amongst concurrently running transactions in transactional memory systems (e.g., bulk, LogTM-SE, and SigTM). Signatures use fixed hardware to represent an unbounded number of addresses, but may lead to false conflicts (detecting a conflict when none exists). Previous work recommends that signatures be implemented with parallel Bloom filters with two or four hash functions (e.g., H3). Two problems exist with current signature designs. First, H3implementations use many XOR gates. This increases hardware area and power overheads. Second, signature false positives can result from conflicts with signature bits set by private memory addresses that do not require isolation. This paper develops Notary, a coupling of two signature enhancements to ameliorate these problems. First, we use address entropy analysis to develop page-block-XOR (PBX) hashing and show it performs similar to H3at lower hardware cost. Second, we introduce a privatization interface that explicitly allows the programmer to declare shared and private heap memory allocation. Privatization reduces false conflicts arising from private memory accesses and can lead to a reduction in the signature size used. Results from custom transistor-level layouts of H3and PBX, along with full-system simulation of a 16-core chip-multiprocessor implementing LogTM-SE, show (a) PBX hashing performs similar to H3hashing while requiring up to 24% less area and 4.7% less power overhead and (b) privatization can improve execution time by up to 86% (by reducing false conflicts by up to 96%).

We present a framework for compressing encrypted media, such as images and videos. Encryption masks the source, rendering traditional compression algorithms ineffective. By conceiving of the problem as one of distributed source coding, it has been shown in prior work that encrypted data are as compressible as unencrypted data. However, there are two major challenges to realize these theoretical results. The first is the development of models that capture the underlying statistical structure and are compatible with our framework. The second is that since the source is masked by encryption, the compressor does not know what rate to target. We tackle these issues in this paper. We first develop statistical models for images before extending it to videos, where our techniques really gain traction. As an illustration, we compare our results to a state-of-the-art motion-compensated lossless video encoder that requires unencrypted video input. The latter compresses each unencrypted frame of the ldquoForemanrdquo test sequence by 59% on average. In comparison, our proof-of-concept implementation, working on encrypted data, compresses the same sequence by 33%. Next, we develop and present an adaptive protocol for universal compression and show that it converges to the entropy rate. Finally, we demonstrate a complete implementation for encrypted video.

We consider video sequences that have been encrypted uncompressed. Since encryption masks the source, traditional data compression algorithms are rendered ineffective. However, it has been shown that through the use of distributed source-coding techniques, the compression of encrypted data is in fact possible. This means that it is possible to reduce data size without requiring that the data be compressed prior to encryption. Indeed, under some reasonable conditions, neither security nor compression efficiency need be sacrificed when compression is performed on the encrypted data (Johnson et al., 2004). In this paper we develop an algorithm for the practical lossless compression of encrypted gray scale video. Our method is based on considering the temporal correlations in the video. This move to temporal dependence builds on our previous work on memoryless sources, and one- and two-dimensional Markov sources. For comparison, a motion-compensated lossless video encoder can compress each unencrypted frame of the standard "Foreman" test video sequence by about 57%. Our algorithm can compress the same frames, after encryption, by about 33%

We describe a method to encode fingerprint biometrics securely for use, e.g., in encryption or access control. The system is secure because the stored data does not suffice to recreate the original fingerprint biometric. Therefore, a breach in database security does not lead to the loss of biometric data. At the same time the stored data suffices to validate a probe fingerprint. Our approach is based on the use of distributed source coding techniques implemented with graph-based codes. We present a statistical model of the relationship between the enrollment biometric and the (noisy) biometric measurement taking during authentication. We describe how to validate or reject a candidate biometric probe given the probe and the stored encoded data. We report the effectiveness of our method as tested on a database consisting of 579 data sets, each containing roughly 15 measurements of a single finger. We thereby demonstrate a working secure biometric system for fingerprints.

We introduce a novel source coding problem, compound conditional source coding. We describe how a number of media coding problems can be cast into this framework. We develop the achievable rate region for this problem and error exponent results. We show that the reliability function of compound conditional source coding is as least as large as the list-decoding error exponent of Slepian-Wolf coding, which we develop in addition. A message of the paper is that a number of media coding scenarios where distributed source coding techniques are being used are more exactly stated as compound conditional problems. This insight can lead to improved system performance, as we demonstrate for error exponents.

Linear programming (LP) decoding was introduced by Feldman et al. (IEEE Trans. Inform. Theory Mar. 2005) as a novel way to decode binary low-density parity-check codes. Taghavi and Siegel (Proc. ISIT 2006) describe a computationally simplified decoding approach they term "adaptive" LP decoding. Adaptive LP decoding starts with a sub-set of the LP constraints, and iteratively adds violated constraints until an optimum of the original LP is found. Usually only a tiny fraction of the original constraints need to be reinstated, leading to huge efficiency gains compared to ordinary LP decoding. Here we describe a modification of the adaptive LP decoder that results in a maximum likelihood (ML) decoder. Whenever the adaptive LP decoder returns a pseudo-codeword rather than a codeword, we add an integer constraint on the least certain symbol of the pseudo-codeword. For certain codes, and especially in the high-SNR (error floor) regime, only a few integer constraints are required to force the resultant mixed-integer LP to the ML solution. We demonstrate that our approach can efficiently achieve the optimal ML decoding performance on a (155,64) LDPC code introduced by Tanner et al.

Coding schemes for secure and efficient communication over noiseless public channels traditionally compress and then encrypt the source data. In some cases reversing the ordering of compression and encryption would be useful, e.g., in enabling the efficient distribution of protected media content. Indeed, not only is it possible to reverse the order, but under some conditions neither security nor compression efficiency need be sacrificed. In earlier work on this problem we have assumed that the source data is either memoryless or has a 1-D Markov structure. Such models are poor matches for the 2-D structure of images. In this work, we use a 2-D source model, and develop a scheme to compress encrypted images based on LDPC codes. We present practical simulation results for compressing bi-level images. In tests, we are able to compress an encrypted 10, 000 bit bi-level image to 4, 299 bits and successfully recover the image exactly. In previous works, the best analogous 1-D model (operating on a raster scanned data sequence of the same source) could only compress the image to 7, 710 bits.

We explore the use of rateless coding for communication over fading channels with delay constraints. Both quasi-static fading and block-fading channels are considered. When only the receiver has channel information, we show there exist rateless codes that are both reliable and efficient for every channel realization of such channels. We then apply these codes to a wireless streaming application with a sequence of playback deadlines. Rateless strategies demonstrate benefits in terms of throughput and outage probability compared to fixed-rate schemes

We show how to exploit a noisy feedback link to implement high-reliability communication. We specify a variable-length coding strategy that achieves the error exponent (in delay) of erasure decoding using any noisy feedback channel which has a positive zero-rate random coding error exponent. Building on this result, we give a second approach that, depending only on the capacity of the feedback link, achieves an error exponent up to half of the Burnashev exponent - the maximum exponent that can be achieved with a noiseless feedback link. The resulting exponent can be far larger than the exponent of erasure decoding, particularly at rates close to capacity

We consider "bit stealing" scenarios where the rate of a source code must be reduced without prior planning. We first investigate the efficiency of source requantization to reduce rate, which we term successive degradation. We focus on finite-alphabet sources with arbitrary distortion measures as well as the Gaussian-quadratic and high-resolution scenarios. We show an achievable rate-distortion tradeoff and prove that this is the best guaranteeable tradeoff for any good source code. This tradeoff is in general different from the rate-distortion tradeoff with successive refinement, where there is prior planning. But, we show that with quadratic distortion measures, for all sources with finite differential entropy and at least one finite moment, the gap is at most 1/2 bit or 3 dB in the high-resolution limit. In the Gaussian-quadratic case, the gap is at most 1/2 bit for all resolutions. We further consider bit stealing in the form of information embedding, whereby an embedder acts on a quantized source and produces an output at the same rate and in the original source codebook. We develop achievable distortion-rate tradeoffs. Two cases are considered, corresponding to whether or not the source decoder is informed of the embedding rate. In the Gaussian-quadratic case, we show the informed decoder need only augment the regular decoder with simple post-reconstruction distortion compensation in the form of linear scaling for the resulting system to be as efficient as bit stealing via successive degradation. Finally, we show that the penalty for uninformed versus informed decoders is at most 3 dB or 0.21-bit in the Gaussian-quadratic case and that their performance also lies within the 1/2-bit gap to that of successive refinement.

Random binning arguments underlie many results in information theory. In this paper we introduce and analyze a novel type of causal random binning "sequential" binning. This binning is used to get streaming Slepian-Wolf codes with an "anytime" character. At the decoder, the probability of estimation error on any particular symbol goes to zero exponentially fast with delay. In the non-distributed context, we show equivalent results for fixed-rate streaming entropy coding. Because of space constraints, we present full derivations only for the latter, stating the results for the distributed problem. We give bounds on error exponents for both universal and maximum-likelihood decoders

For the point-to-point additive white Gaussian noise (AWGN) channel with noiseless feedback and an average power constraint, Schalkwijk and Kailath's scheme achieves a doubly-exponential decay of the probability of error. While some coding schemes for networks with noiseless feedback incorporate variations on the Schalkwijk-Kailath scheme, they do not in general achieve better than single-exponential decays in their probabilities of error everywhere in their achievable rate regions. We give a technique that can boost the reliability as high as desired of any from a large class of block coding schemes for networks with feedback. The technique relies crucially on the average nature of the power constraints. We explain and illustrate our results in the context of Ozarow's feedback strategy for the AWGN multiple-access channel

In multiuser communication systems the exchange of some number of rate-limited messages both between encoders, and between decoders, can enlarge the achievable rate region. We consider interaction between a pair of Slepian-Wolf encoders, and a pair of deterministic broadcast channel decoders. For these systems, a single one-way message is sufficient. More generally, we make connections to relay channels and consider how to quantize data for relaying.

We present a strategy for the reliable communication of a message, in a variable number of channel uses, over an unknown discrete memoryless channel (DMC). The decoder periodically tests the received sequence and, when it can decode, sends an acknowledgment to the transmitter, which then stops transmitting. By choosing the size of the codebook large enough, the rate that is reliably realized by the strategy can be made to approach arbitrarily closely the mutual information between channel input and output induced by the user-chosen input distribution. The strategy presented can be considered as a generalization to arbitrary unknown DMCs of earlier variable length coding schemes, such as digital fountain codes for binary erasure channels (BECs), and a coding strategy for binary symmetric channels (BSCs) presented by Tchamkerten and Telatar

We develop coding strategies for estimation under communication constraints in tree-structured sensor networks. The strategies have a modular and decentralized architecture. This promotes the flexibility, robustness, and scalability that wireless sensor networks need to operate in uncertain, changing, and resource-constrained environments. The strategies are based on a generalization of Wyner-Ziv source coding with decoder side information. We develop solutions for general trees, and illustrate our results in serial (pipeline) and parallel (hub-and-spoke) networks. Additionally, the strategies can be applied to other network information theory problems. They have a successive coding structure that gives an inherently less complex way to attain a number of prior results, as well as some novel results, for the Chief Executive Officer problem, multiterminal source coding, and certain classes of relay channels.

We consider source requantization in two forms - successive degradation (i.e., source fidelity reduction) and bit stealing (i.e., information embedding) when no forward planning has been done to facilitate the requantization. We focus on finite-alphabet sources with arbitrary distortion measures as well as the Gaussian-quadratic scenario. For the successive degradation problem, we show an achievable distortion-rate trade-off for non-hierarchically structured rate-distortion achieving codes, and compare it to the distortion-rate trade-off of successively refinable codes. We further consider source requantization in the form of bit stealing, whereby an information embedder acts on a quantized source, producing an output at the same rate. Building on the successive degradation results, we develop achievable distortion-rate trade-offs. Two cases are considered, corresponding to whether the source decoder is informed of any bit stealing or not. In the latter case, the embedder must produce outputs in the original source codebook. For the Gaussian-quadratic scenario, all trade-offs are within 0.5 bits/sample of the distortion-rate bound. Furthermore, for bit stealing, the use of simple post-reconstruction processing that is only a function of the embedded rate can eliminate the loss experienced by uninformed decoders.

There are numerous contexts in which systems need to buffer multimedia signal content. If such a buffer overflows, signal data are lost in an uncontrolled manner, which can lead to large end-to-end distortions. However, if the queued signals are distortion-tolerant, overflows can be avoided, and significant performance gains realized, by reducing the fidelity of the signals in a gradual, controlled, manner. Based on ideas of successive-approximation source coding, we design an adaptive-buffering algorithm to minimize end-to-end distortion. This algorithm performs nearly as well as a performance bound on all possible algorithms. Perhaps most importantly, the algorithm's performance remains robust across a wide range of (unpredictable) utilization rates (input rate/output rate).