This paper addresses the design of practical short-length coding schemes for Distributed Hypothesis Testing (DHT). While most prior work on DHT has focused on information-theoretic analyses—deriving bounds on Type-II error exponents via achievability schemes based on quantization and quantize-binning—the practical implementation of DHT coding schemes has remained largely unexplored. Moreover, existing practical coding solutions for quantization and quantize-binning approaches were developed for source reconstruction tasks considering very long code lengths, and they are not directly applicable to DHT. In this context, this paper introduces efficient short-length implementations of quantization and quantize-binning schemes for DHT, constructed from short binary linear block codes. Numerical results show the efficiency of the proposed coding schemes compared to uncoded cases and to existing schemes initially developed for data reconstruction. In addition to practical code design, the paper derives exact analytical expressions for the Type-I and Type-II error probabilities associated with each proposed scheme. The provided analytical expressions are shown to predict accurately the practical performance measured from Monte Carlo simulations of the proposed schemes. These theoretical results are novel and offer a useful framework for optimizing and comparing practical DHT schemes across a wide range of source and code parameters.

In the Wyner-Ziv source coding problem, a source X has to be encoded while the decoder has access to side information Y. This paper investigates the indirect setup, in which a latent source S, unobserved by both the encoder and the decoder, must also be reconstructed at the decoder. This scenario is increasingly relevant in the context of goal-oriented communications, where S can represent semantic information obtained from X. This paper derives the indirect Wyner-Ziv rate-distortion function in asymptotic regime and provides an achievable region in finite block-length. Furthermore, a Blahut-Arimoto algorithm tailored for the indirect Wyner-Ziv setup, is proposed. This algorithm is then used to give a numerical evaluation of the achievable indirect rate-distortion region when S is treated as a classification label.

This paper investigates practical coding schemes for Distributed Hypothesis Testing (DHT). While the literature has extensively analyzed the information-theoretic performance of DHT and established bounds on Type-II error exponents through quantize and quantize-binning achievability schemes, the practical implementation of DHT coding schemes has not yet been investigated. Therefore, this paper introduces practical implementations of quantizers and quantize-binning schemes for DHT, leveraging short-length binary linear block codes. Furthermore, it provides exact analytical expressions for Type-I and Type-II error probabilities associated with each proposed coding scheme. Numerical results show the accuracy of the proposed analytical error probability expressions, and enable to compare the performance of the proposed schemes.

We explore the problem of distributed Hypothesis Testing (DHT) against independence, focusing specifically on Binary Symmetric Sources (BSS). Our investigation aims to characterize the optimal quantizer among binary linear codes, with the objective of identifying optimal error probabilities under the Neyman-Pearson (NP) criterion for short code-length regime. We define optimality as the direct minimization of analytical expressions of error probabilities using an alternating optimization (AO) algorithm. Additionally, we provide lower and upper bounds on error probabilities, leading to the derivation of error exponents applicable to large code-length regime. Numerical results are presented to demonstrate that, with the proposed algorithm, binary linear codes with an optimal covering radius perform near-optimally for the independence test in DHT.

In the framework of goal-oriented communications, this paper investigates parametric regression over coded data. For this problem, information-theoretic bounds are provided in terms of rate versus regression generalization error, by considering quantize and binning achievability schemes. Alternatively, this paper focuses on practical implementations by proposing a coding scheme that combines a scalar quantizer with a non-binary LDPC code for the binning part. Given that the LDPC decoder requires prior knowledge of the regression parameters, the paper introduces a novel method to estimate these parameters directly over the LDPC-coded syndrome, without the need for prior decoding. This technique allows to both address the regression task and initialize the LDPC decoder for further data reconstruction. Monte-Carlo simulations show the efficiency of the proposed approach in terms of regression generalization error.

Convolutional neural networks (CNNs) have proven very effective in a variety of practical applications involving artificial intelligence (AI). However, the layer depth of CNN deepens as user applications become more sophisticated, resulting in a huge number of operations and increased memory size. The massive amount of the produced intermediate data leads to intensive data movement between memory and computing cores causing a real bottleneck. In-memory computing (IMC) aims to address this bottleneck by directly computing inside memory, eliminating energy-intensive and time-consuming data movement. On the other hand, the emerging binary neural networks (BNNs), which is a special case of CNN, show a number of hardware-friendly properties, including memory saving. In BNN, the costly floating-point multiply-and-accumulate is replaced with lightweight bitwise XNOR and popcount operations. In this article, we propose an IMC programmable architecture targeting efficient implementation of BNN. Computational memories based on the recently introduced memristor overwrite logic (MOL) design style are employed. The architecture, which is presented in semiparallel and parallel models, efficiently executes the advanced quantization algorithm of XNOR-Net BNN. Performance evaluation based on the CIFAR-10 dataset demonstrates between$1.24\times $and$3\times $speedup and 49% and 99% energy saving compared to state-of-the-art implementations and up to 273-image/s/W throughput efficiency.

Kalman filters are widely used for real-time estimation of dynamic systems, and they sometimes need to be implemented on energy-constrained devices. A Kalman filter implementation from unreliable memories is considered, where the flipping probability of a bit in a memory cell directly depends on its energy consumption. The degradation in estimation performance caused by the noise in the memory is theoretically investigated. Updated equations are then developed for the Kalman filter, taking into account the new source of noise from the unreliable memory. Finally, a method is proposed to optimize the bit energy allocation in the memory, and it is shown from numerical simulations that this method allows for important energy gains.

This paper considers Deep Neural Network (DNN) linear-nonlinear computations implemented on memristor cross-bar substrates. To address the case where true memristor conductance values may differ from their target values, it introduces a theoretical framework that characterizes the effect of conductance value variations on the final inference computation. With only second-order moment assumptions, theoretical results on tracking the mean, variance, and covariance of the layer-by-layer noisy computations are given. By allowing the possibility of amplifying certain signals within the DNN, power consumption is characterized and then optimized via KKT conditions. Simulation results verify the accuracy of the proposed analysis and demonstrate the significant power efficiency gains that are possible via optimization for a target mean squared error.

This paper considers low-density parity-check (LDPC) decoders affected by deviations introduced by the electronic device on which the decoder is implemented. Noisy density evolution (DE) that allows to theoretically study the performance of these LDPC decoders can only consider symmetric deviation models due to the all-zero codeword assumption. A novel DE method is proposed that admits the use of asymmetric deviation models, thus widening the range of faulty implementations that can be analyzed. DE equations are provided for three noisy decoders: belief propagation, Gallager B, and quantized min-sum (MS). Simulation results confirm that the proposed DE accurately predicts the performance of LDPC decoders with asymmetric deviations. Furthermore, asymmetric versions of the Gallager B and MS decoders are proposed to compensate the effect of asymmetric deviations. The parameters of these decoders are then optimized using the proposed DE, leading to better ensemble thresholds and improved finite-length performance in the presence of asymmetric deviations.

International audience

Data acquired over long periods of time like High Definition (HD) videos or records from a sensor over long time intervals, have to be efficiently compressed, to reduce their size. The compression has also to allow efficient access to random parts of the data upon request from the users. Efficient compression is usually achieved with prediction between data points at successive time instants. However, this creates dependencies between the compressed representations, which is contrary to the idea of random access. Prediction methods rely in particular on reference data points, used to predict other data points. The placement of these references balances compression efficiency and random access. Existing solutions to position the references use ad hoc methods. In this paper, we study this joint problem of compression efficiency and random access. We introduce the storage cost as a measure of the compression efficiency and the transmission cost for the random access ability. We express the reference placement problem that trades storage with transmission cost as an integer linear programming problem. Considering additional assumptions on the sources and coding methods reduces the complexity of the search space of the optimization problem. Moreover, we show that the classical periodic placement of the references is optimal, when the encoding costs of each data point are equal and when requests of successive data points are made. In this particular case, a closed-form expression of the optimal period is derived. Finally, the proposed optimal placement strategy is compared with an ad hoc method, where the references correspond to sources where the prediction does not help reducing significantly the encoding cost. The proposed optimal algorithm shows a bit saving of -20% with respect to the ad hoc method.

Recursive estimation is a basic operation in statistical inference that may be implemented and deployed on faulty hardware with error rates governed by energy consumption. We analyze the loss in estimation performance due to noise in recursive probability computation for the binary case, and develop an optimal energy allocation strategy. Simulations show the validity of analytical bounds.

This paper considers the problem of source coding with side information at the decoder, also called Slepian-Wolf source coding scheme. In practical applications of this coding scheme, the statistical relation between the source and the side information can vary from one data transmission to another, and there is a need to adapt the coding rate depending on the current statistical relation. In this paper, we propose a novel rate-adaptive code construction based on LDPC codes for the Slepian-Wolf source coding scheme. The proposed code design method allows to optimize the code degree distributions at all the considered rates, while minimizing the amount of short cycles in the parity check matrices at all rates. Simulation results show that the proposed method greatly reduces the source coding rate compared to the standard low density parity check accumulated (LDPCA) solution.

We consider a network of binary-valued sensors with a fusion center. The fusion center has to perform K-means clustering on the binary data transmitted by the sensors. In order to reduce the amount of data transmitted within the network, the sensors compress their data with a source coding scheme based on binary sparse matrices. We propose to apply the K-means algorithm directly over the compressed data without reconstructing the original sensors measurements, in order to avoid potentially complex decoding operations. We provide approximated expressions of the error probabilities of the K-means steps in the compressed domain. From these expressions, we show that applying the K-means algorithm in the compressed domain enables to recover the clusters of the original domain. Monte Carlo simulations illustrate the accuracy of the obtained approximated error probabilities, and show that the coding rate needed to perform K-means clustering in the compressed domain is lower than the rate needed to reconstruct all the measurements.

In Sequential Massive Random Access (SMRA) [1, 2], a set of correlated sources is jointly encoded and stored on a server, and clients want to access to only a subset of the sources. Since the number of simultaneous clients can be huge, the server is only authorized to extract a bitstream from the stored data: no re-encoding can be performed before the transmission of a request. In this paper, we investigate the SMRA performance of lossy source coding of Gaussian sources with memory. In practical applications such as Free Viewpoint Television, this model permits to take into account not only inter but also intra correlation between sources. For this model, we provide the storage and transmission rates that are achievable for SMRA under some distortion constraint, and we consider two particular examples of Gaussian sources with memory.

In this paper, we consider a network of sensors in which a fusion center applies a clustering method over the sensor measurements. In order to limit their energy consumption, the sensors transmit their measurements in a compressed form. This paper proposes a novel clustering algorithm that applies directly over compressed data, and that does not require the knowledge of the number of clusters. The proposed algorithm is based on a new cost function for centroid estimation, and a theoretical analysis shows that the cluster centroids are the only minimizers of this cost function. The clustering algorithm then estimates the cluster centroids by looking for the minimizers of the cost function, even when their number is unknown. The proposed algorithm shows performance close to that of the K-means algorithm over compressed data, without need to know the number of clusters.

In this paper, we consider the construction of a Slepian-Wolf source coding scheme in a context where only a small amount of data has to be transmitted to the decoder. In this context, we propose a novel rate-adaptive Slepian-Wolf code construction that is based on non-binary LDPC codes. The construction we propose replaces the regular accumulator of the standard LDPCA method by a local graph that is optimized at every rate of interest. In our method, the local graph is specifically designed in order to give good decoding performance at short length, while existing LDPCA constructions are usually optimized under an infinite codeword length assumption. Our simulation results on short codes obtained from our design method show a FER improvement of up to an order to magnitude compared to the standard LDPCA construction.

Lowering the power supply of a circuit can induce transient errors in the memory cells and timing errors in the computation units. In this paper, we consider the Taylor-Kuznetsov (TK) memory architecture with transient errors in the memory cells and with timing errors in the correction circuit. We provide a theoretical analysis of the performance of TK memories under transient errors and timing errors. Our study is based on the analysis of the computation trees of the equivalent Gallager B decoders with and without timing errors. As a main result, we show that as the number of iterations goes to infinity, the error probability of the decoder with timing errors converges to the error probability of the decoder without timing errors. Monte Carlo simulations confirm this result even for moderate code lengths.

A novel fault tolerant methodology known as Codeword Prediction Encoder (CPE) for reliable data transmission using unreliable hardware is proposed. Simulation results show that performance of CPE is much better as compared to transmitting data by employing traditional encoding methodology. It is shown that by employing Min-sum decoding mechanisms and a strong encoder r = 1/2 and dv = 4, it is possible to correct all errors given that gate errors smaller than Pg = 6e-4. In general, CPE performance improvement of upto 10K is observed when compared to the normal encoding mechanism.

LDPC decoders on faulty hardware have received increasing attention over the last few years, mainly motivated by reliability issues in emerging nanotechnologies. As a main result, it was shown that LDPC decoders are naturally robust to hardware faults. LDPC encoders on faulty hardware have received less attention, and they are expected to be less robust to hardware faults. In this work, we propose an LDPC encoding solution that is robust to faulty hardware. Our encoding solution is composed of two steps. First, an Augmented Encoding method is proposed, which consists in computing an augmented codeword that contains both the codeword to be transmitted on the channel and extra parity bits. The augmented codeword is computed from a noisy encoding circuit, and then corrected by a noisy Gallager-B decoder before channel transmission. The augmented codeword is obtained from a rate-compatible construction that guarantees good decoding performance both for the augmented codeword and for the codeword to be transmitted on the channel. In order to further improve the robustness of our encoding solution, we propose a second step, consisting of a circuit-level optimization. We propose to identify the critical gates that are responsible for encoding failures, and to duplicate them in order to reduce their influence on encoding outputs. Based on Monte-Carlo simulation, we show that the proposed solution significantly improves the encoding robustness to hardware faults.

This paper addresses the problem of designing low-density parity check decoders robust to transient errors introduced by faulty hardware. We assume that the faulty hardware introduces errors during the message-passing updates, and we propose a general framework for the definition of the message update faulty functions. Within this framework, we define symmetry conditions for the faulty functions and derive two simple error models used in the analysis. With this analysis, we propose a new interpretation of the functional density evolution threshold introduced by Kameni et al. in the recent literature and show its limitations in the case of highly unreliable hardware. However, we show that under restricted decoder noise conditions, the functional threshold can be used to predict the convergence behavior of finite alphabet iterative decoders (FAIDs) under faulty hardware. In particular, we reveal the existence of robust and nonrobust FAIDs and propose a framework for the design of robust decoders. We finally illustrate robust- and nonrobust-decoder behaviors of finite-length codes using Monte Carlo simulations.

In this paper, we investigate the problem of designing good non-binary LDPC codes for Slepian-Wolf coding. The design method is based on Density Evolution which gives the asymptotic error probability of the decoder for given code degree distributions. Density Evolution was originally introduced for channel coding under the assumption that the channel is symmetric. In Slepian-Wolf coding, the correlation channel is not necessarily symmetric and the source distribution has to be taken into account. In this paper, we express the non-binary Density Evolution recursion for Slepian-Wolf coding. From Density Evolution, we then perform code degree distribution optimization using an optimization algorithm called differential evolution. Both asymptotic performance evaluation and finite-length simulations show the gain at considering optimized degree distributions for SW coding.

This paper investigates the behavior of the Min-Sum decoder running on noisy devices. Our aim is to evaluate the robustness of the decoder to computation noise caused by the faulty logic in the processing units. This type of noise represents a new source of errors that may occur during the decoding process. To this end, we first introduce probabilistic models for the arithmetic and logic units of the finite-precision min-sum decoder and then carry out the density evolution analysis of the noisy min-sum decoder. We show that, in some particular cases, the noise introduced by the device can help the min-sum decoder to escape from fixed points attractors and may actually result in an increased correction capacity with respect to the noiseless decoder. We also point out a specific threshold phenomenon, referred to as functional threshold, which accurately describes the convergence behavior of noisy decoders. The behavior of the noisy MS is demonstrated in the asymptotic limit of the code length through a noisy version of density evolution and is also verified in the finite-length case by Monte Carlo simulations.

This paper considers the problem of lossless source coding with side information at the decoder, when the correlation model between the source and the side information is uncertain. Four parametrized models representing the correlation between the source and the side information are introduced. The uncertainty on the correlation appears through the lack of knowledge on the value of the parameters. For each model, we propose a practical coding scheme based on non-binary Low Density Parity Check Codes and able to deal with the parameter uncertainty. At the encoder, the choice of the coding rate results from an information theoretical analysis. Then we propose decoding algorithms that jointly estimate the source vector and the parameters. As the proposed decoder is based on the Expectation-Maximization algorithm, which is very sensitive to initialization, we also propose a method to produce first a coarse estimate of the parameters.

The objective of this paper is the characterization of the Wyner-Ziv rate-distortion function for memoryless continuous sources, when the correlation between the sources is modeled via an additive noise channel. Modeling the distribution of the correlation noise via a Gaussian mixture, with discrete or continuous mixing variable, provides a unified signal model able to describe a wide class of distributions, useful in the context of practical applications. The Wyner-Ziv rate-distortion function associated with this signal model cannot, in general, be obtained in analytical form. This paper contributes a method for its analysis, by providing computable upper and lower bounds.

This paper considers the problem of universal lossless source coding with side information at the decoder only. The correlation channel between the source and the side information is unknown and belongs to a class parametrized by some unknown parameter vector. A complete coding scheme is proposed that works well for any distribution in the class. At the encoder, the proposed scheme encompasses the determination of the coding rate and the design of the encoding process. Both contributions result from the information-theoretical compression bounds of universal lossless source coding with side information. Then a novel decoder is proposed that takes into account the available information regarding the class. The proposed scheme avoids the use of a feedback channel or the transmission of a learning sequence, which both would result in a rate increase at finite length.

This paper considers the problem of lossy source coding with side information at the decoder only, for Gaussian sources, when the joint statistics of the sources are partly unknown. We propose a practical universal coding scheme based on scalar quantization and nonbinary LDPC codes, which avoids the binarization of the quantized coefficients. We first explain how to choose the rate and to construct the LDPC coding matrix. Then, a decoding algorithm that jointly estimates the source sequence and the joint statistics of the sources is proposed. The proposed coding scheme suffers no loss compared to the practical coding scheme with same rate but known variance.

This paper focuses on the performance of a Wyner-Ziv coding scheme for which the correlation between the source and the side information is modeled by a hidden Markov model with Gaussian emission. Such a signal model takes the memory of the correlation into account and is hence able to describe the bursty nature of the correlation between sources in applications such as sensor networks, video coding etc. This paper provides bounds on the rate-distortion performance of a Wyner-Ziv coding scheme for such model. It proposes a practical coding scheme able to exploit the memory in the correlation. Finally, the contribution to each part of the coding and decoding scheme is analysed.

Pure frequency-based audio fingerprint systems have the capacity of handling very short fingerprints while being highly robust to perturbations such as additive noise or compression. However, these approaches are often complex and fail to identify time stretched signals. We propose in this paper two extensions of an existing system and test the robustness of the overall system in different conditions. It is shown that the search strategy adopted allows for a clear reduction of complexity with very limited degradation of performances and that the new system is robust to additive noise and speed changes up to 5%.