Digital communication systems inherently operate through physical media governed by partial differential equations (PDEs). In this paper, we introduce a physics-aware decoding framework that integrates gradient descent-based error correcting algorithms with PDE-based channel modeling using differentiable PDE solvers. At the core of our approach is gradient flow decoding, which harnesses gradient information directly from the PDE solver to guide the decoding process. We validate our method through numerical experiments on both the heat equation and the nonlinear Schrödinger equation (NLSE), demonstrating significant improvements in decoding performance. The implications of this work extend beyond decoding applications, establishing a new paradigm for physicsaware signal processing that shows promise for various signal detection and signal recovery tasks.

This paper introduces a novel cost-aware structure learning framework for optimizing distributed algorithms, balancing computational performance and aggregation costs. We demonstrate its effectiveness through application to multiple measurement vector compressed sensing (MMV-CS) problems. Our proposed Learned Distributed Multiple Measurement Vector Iterative Shrinkage Thresholding (LDM-IST) algorithm extends a single measurement vector distributed recovery algorithm to the MMV model, incorporating deep unfolding to optimize hyperparameters and enhance convergence. Moreover, cost-aware structure learning is applied to improve the aggregation efficiency of the LDM-IST. Numerical experiments show that LDM-IST achieves normalized mean square error performance comparable to the centralized recovery algorithm, and takes a good tradeoff between recovery performance and the in-network computing overhead.

Abstract The f-fault-tolerant connectivity labeling (f-FTC labeling) is a scheme of assigning each vertex and edge with a small-size label such that one can determine the connectivity of two vertices s and t under the presence of at most f faulty edges only from the labels of s, t, and the faulty edges. This paper presents a new deterministic f-FTC labeling scheme attaining $$O(f^2 \textrm{polylog}(n))$$ O ( f 2 polylog ( n ) ) -bit label size and a polynomial construction time, which settles the open problem left by Dory and Parter (in: Proceedings of the 2021 ACM symposium on principles of distributed computing (PODC), pp 445–455, 2021). The key ingredient of our construction is to develop a deterministic counterpart of the graph sketch technique by Ahn et al. (in: Proceedings of the 31st ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems (PODS), pp 5–14, 2012), via some natural connection with the theory of error-correcting codes. This technique removes one major obstacle in de-randomizing the Dory–Parter scheme. The whole scheme is obtained by combining this technique with a new deterministic graph sparsification algorithm derived from the seminal $$\epsilon $$ ϵ -net theory, which is also of independent interest. As byproducts, our result deduces the first deterministic fault-tolerant approximate distance labeling scheme with a non-trivial performance guarantee and an improved deterministic fault-tolerant compact routing. The authors believe that our new technique is potentially useful in the future exploration of more efficient FTC labeling schemes and other related applications based on graph sketches.

In this paper, we introduce the LWCoopPG (Learned Weighting Cooperative Projected Gradient Descent) algorithm for fully distributed MIMO signal detection. The proposed algorithm is a fully distributed algorithm, implementing the projected gradient method over a network, and incorporating a trainable step size and trainable weight parameters, which are tuned by deep unfolding. The computations of the proposed algorithm are fully distributed, eliminating the need for a central processor. Numerical experiments affirmed the superiority of the LWCoopPG algorithm over the conventional MMSE algorithm in terms of detection performance.

This paper introduces an extension of Gradient Flow (GF) decoding for LDPC codes. GF decoding, a continuous-time methodology based on gradient flow, employs a potential energy function associated with bipolar codewords of LDPC codes. The original GF decoding was designed for AWGN channels but in this paper, we introduce the negative log-likelihood function of the channel for generalizing the original method. The proposed method is shown to be tensor-computable, which means that the gradient of the objective function can be evaluated with the combination of basic tensor computations. This characteristic is well-suited to emerging AI accelerators, potentially applicable in wireless signal processing. The paper assesses the decoding performance of the generalized GF decoding in LDPC-coded MIMO channels. Our numerical experiments reveal that this method's decoding performance rivals that of established techniques such as MMSE + BP. A further benefit of the proposed method is its suitability for deep unfolding. This advantage stems from the fact that each component of the method is differentiable.

This paper introduces a deep unfolding-assisted proximal decoding for low-density parity-check (LDPC) codes. Proximal decoding method is a decoding algorithm based on the proximal gradient method. Our proposal, deep unfolding-assisted proximal (DU-Proximal) decoding, is obtained by applying deep unfolding to the proximal decoding. We especially focus on the decoding performance in multiple-input multiple-output (MIMO) channels. In numerical experiments, we compare the error correcting capability of the proposed algorithm with the minimum mean squared error (MMSE) signal detection method, the tanh signal detection method, and the MMSE jointly with belief propagation (BP) algorithm for LDPC decoding. The experimental results demonstrate that parameter optimization via DU yields significant performance gains, especially at high signal-to-noise ratio levels.

In this paper, we study an optical MIMO (Multiple-Input Multiple-Output) signal detection circuit based on the projected gradient method. The projected gradient method is an iterative algorithm that iteratively performs a gradient descent step and a projection step. In the proposed optical MIMO signal detection circuit, the gradient descent step is implemented by an optical analog circuit in the optical domain, and the projection step is implemented by a nonlinear processing circuit in the electrical domain. The system noise due to the optical amplifier significantly degrades the detection performance of the optical MIMO detection circuit, which is a crucial issue for the optical implementation. In order to mitigate the effect of the system noises, we present how to apply deep unfolding, a technique for improving the performance of iterative algorithms, to the design of an optical MIMO signal detection circuit. The results of numerical experiments show that the proposed deep unfolding-based design achieves improved convergence performance and reduces the influence of the system noises.

This paper presents a design method for Mach-Zehnder interferometers (MZIs)-based optical circuits intended for MIMO signal detection that are robust against fabrication errors in MZIs. Typically, faulty MZIs can critically impair the functioning of optical circuits. Our primary objective is to devise a design strategy that ensures the reliability of optical circuits for MIMO linear detection even when faced with faulty MZIs. The cornerstone of our approach is the adjustment of parameters in functional MZIs by minimizing the receiver's mean squared error using a gradient descent method. Numerical experiments underscore that our method enables signal detectors, even with faulty MZIs, to approach the performance of an ideal, faultless MMSE MIMO detector.

The f-fault-tolerant connectivity labeling (f-FTC labeling) is a scheme of assigning each vertex and edge with a small-size label such that one can determine the connectivity of two vertices s and t under the presence of at most f faulty edges only from the labels of s, t, and the faulty edges. This paper presents a new deterministic f-FTC labeling scheme attaining O(f2 polylog(n))-bit label size and a polynomial construction time, which settles the open problem left by Dory and Parter [18]. The key ingredient of our construction is to develop a deterministic counterpart of the graph sketch technique by Ahn, Guha, and McGreger [4], via some natural connection with the theory of error-correcting codes. This technique removes one major obstacle in de-randomizing the Dory-Parter scheme. The whole scheme is obtained by combining this technique with a new deterministic graph sparsification algorithm derived from the seminal ϵ-net theory, which is also of independent interest. As byproducts, our result deduces the first deterministic fault-tolerant approximate distance labeling scheme with a non-trivial performance guarantee and an improved deterministic fault-tolerant compact routing. The authors believe that our new technique is potentially useful in the future exploration of more efficient FTC labeling schemes and other related applications based on graph sketches.

Motivated by emerging technologies for energy ef-ficient analog computing and continuous-time processing, this paper proposes continuous-time minimum mean squared error estimation for multiple-input multiple-output (MIMO) systems based on an ordinary differential equation. Mean squared error (MSE) is a principal detection performance measure of estimation methods for MIMO systems. We derive an analytical MSE formula that indicates the MSE at any time. The MSE of the proposed method depends on a regularization parameter which affects the convergence property of the MSE. Furthermore, we extend the proposed method by using a time-dependent regularization parameter to achieve better convergence performance. Numerical experiments indicated excellent agreement with the theoretical values and improvement in the convergence performance owing to the use of the time-dependent parameter.

This paper presents fully analog noise-resilient dynamical systems for storing a binary sequence. The proposed dynamical system is a gradient descent dynamical system based on a potential energy function defined based on a parity check matrix of a binary linear code. We assume that the dynamical system operates with stochastic disturbances such as thermal noises. We formulate the whole system, including stochastic disturbances, using stochastic differential equations (SDE). From a discretized stochastic difference equation, i.e., the Euler-Maruyama equation, we can study the covariance evolution of error vectors regarding the random walk of the system state around an equilibrium state. Some numerical evaluations for the (7,4) Hamming code and related codes indicate the robustness of the proposed dynamical system against the stochastic disturbances.

A continuous-time average consensus system is a linear dynamical system defined over a graph. Each node has its state value, and it evolves according to a simultaneous linear differential equation where a node is allowed to interact with neighboring nodes. An average consensus process eventually converges to the state where all the state values are identical to the average of the initial state values. We first formulate the noisy average consensus system by using stochastic differential equations (SDE). This enables us to use the Euler-Maruyama method, which is a numerical method to solve the SDEs. Error analysis on the Euler-Maruyama method provides the mean squared error (MSE) formula on the noisy average consensus systems. We finally show several bounds on the achievable sum- rate for the MAC realized by noisy average consensus systems.

Chebyshev-periodical successive over-relaxation was recently proposed as a method of accelerating the convergence speed of fixed-point iterations. If a PSOR iteration is influenced by stochastic disturbances, such as Gaussian noise, then the behavior of the PSOR iteration deviates from the predicted behavior of the noiseless iterations, i.e., the convergence behavior of the Chebyshev-PSOR is highly sensitive to the noises. This paper presents a concise formula for the asymptotic mean squared error (AMSE) of the noisy PSOR iterations. A PSOR iteration can be regarded as a stochastic difference equation and spectral decomposition plays a key role to reveal the asymptotic behaviors of the error covariance. Based on the AMSE formula, a noise mitigation method is developed to reduce the effects of the stochastic disturbance.

Successive interference cancellation (SIC) is a fundamental decoding technique for Gaussian multiple access channels (GMAC). In SIC, transmit signals of each user are separately decoded. In this paper, we analyze an asymptotic decoding threshold of SIC decoding for practical low-density parity-check (LDPC) codes over$N$-user GMAC. Conventionally, the decoding thresholds are evaluated based on the so-called channel approximation (CA) in which the channel model of each decoding stage of a SIC decoder is approximated by simple Gaussian noise channels resulting in errors of decoding thresholds. To avoid this, we propose a refined density evolution (DE) analysis called DE-SIC which uses mixed-Gaussian noise channels corresponding to each decoding stage. We demonstrate DE-SIC by solving a received power optimization problem in GMAC and comparing it to the conventional DE analysis with CA. The results show that DE-SIC accurately evaluates the decoding thresholds whereas the conventional analysis underestimates the thresholds.

A novel linear transform is presented which is suitable for noisy fronthaul channels in distributed MIMO C-RAN systems. A linear transform based on the Karhunen-Loeve transform is optimized in terms of mean squared error (MSE). Using MSE as the objective function enables us to derive a concise closed MSE formula. By using this MSE formula and the Lagrange multiplier method, the optimal linear transform can be derived in a closed form and no optimization processes are required for designing this transform. We also present a dimension expansion method with a Vandermonde matrix as a noise mitigation method. The MSE formula for the Vandermonde dimension expansion indicates an explicit tradeoff relation be-tween spectral efficiency and energy efficiency of the fronthaul channel. Results from numerical experiments and evaluations support our theoretical arguments.

We propose a novel optimization-based decoding algorithm for LDPC-coded massive MIMO channels. The proposed decoding algorithm is based on a proximal gradient method for solving an approximate maximum a posteriori (MAP) decoding problem. The key idea is the use of a code-constraint polynomial penalizing a vector far from a codeword as a regularizer in the approximate MAP objective function. The code proximal operator is naturally derived from code-constraint polynomials. The proposed algorithm, called proximal decoding, can be described by a simple recursion consisting of the gradient descent step for a negative log-likelihood function and the code proximal operation. Several numerical experiments show that the proposed algorithm outperforms known massive MIMO detection algorithms, such as an MMSE detector with belief propagation decoding.

A novel method, termed Chebyshev periodical successive over-relaxation (PSOR), for accelerating the convergence speed of fixed-point iterations is presented. Chebyshev PSOR can be regarded as a variant of successive over-relaxation utilizing the inverse of roots of a Chebyshev polynomial as iteration-dependent PSOR factors. One of the most notable features of the proposed method is that it can be applied to nonlinear fixed-point iterations in addition to linear fixed-point iterations. From several numerical experiments, it is shown that Chebyshev PSOR leads to faster convergence for wide classes of linear and non-linear fixed-point iterations including proximal gradient methods such as ISTA.

Multicast beamforming is a promising technique for multicast communication. Providing an efficient and powerful beamforming design algorithm is a crucial issue because multicast beamforming problems such as a max-min-fair problem are NP-hard in general. Recently, deep learning-based approaches have been proposed for beamforming design. Although these approaches using deep neural networks exhibit reasonable performance gain compared with conventional optimization-based algorithms, their scalability is an emerging problem for large systems in which beamforming design becomes a more demanding task. In this paper, we propose a novel deep unfolded trainable beamforming design with high scalability and efficiency. The algorithm is designed by expanding the recursive structure of an existing algorithm based on projections onto convex sets and embedding a constant number of trainable parameters to the expanded network, which leads to a scalable and stable training process. Numerical results show that the proposed algorithm can accelerate its convergence speed by using unsupervised learning, which is a challenging training process for deep unfolding.

Complex-field signal recovery problems from noisy linear/nonlinear measurements appear in many areas of signal processing and wireless communications. In this paper, we propose a trainable iterative signal recovery algorithm named complex-field TISTA (C-TISTA) which treats complex-field nonlinear inverse problems. C-TISTA is based on the concept of deep unfolding and consists of a gradient descent step with the Wirtinger derivatives followed by a shrinkage step with a trainable complex-valued shrinkage function. Importantly, it contains a small number of trainable parameters so that its training process can be executed efficiently. Numerical results indicate that C-TISTA shows remarkable signal recovery performance compared with existing algorithms.

Compute-and-forward (CAF) relaying is an effective way to increase bandwidth efficiency of wireless two-way relay channels. Design of error-correcting codes and their decoding algorithms suitable for CAF relaying schemes remains an important issue to be studied. In this paper, we will analyze an asymptotic behavior of LDPC codes over two-way relay channels based on density evolution (DE). Because of the asymmetric characteristics of the channel, we use the population dynamics DE combined with DE formulas for asymmetric channels to obtain the belief propagation (BP) thresholds. Additionally, we also evaluate the asymptotic performance of spatially coupled LDPC codes for two-way relay channels. The results indicate that the spatially coupled codes yield improvements in the BP threshold compared with corresponding uncoupled codes for two-way relay channels.

The paper presents a deep learning-aided iterative detection algorithm for massive overloaded MIMO systems. Since the proposed algorithm is based on the projected gradient descent method with trainable parameters, it is named as trainable projected descent-detector (TPG-detector). The trainable internal parameters can be optimized with standard deep learning techniques such as back propagation and stochastic gradient descent algorithms. This approach referred to as data-driven tuning brings notable advantages of the proposed scheme such as fast convergence. The numerical experiments show that TPG-detector achieves comparable detection performance to those of the known algorithms for massive overloaded MIMO channels with lower computation cost.

The compute-and-forward (CAF) scheme has attracted great interests due to its high band-width efficiency on two-way relay channels. In the CAF scheme, a relay attempts to decode a linear combination of transmitted messages from other terminals or relays. It is a crucial issue to study practical error-correcting codes in order to realize the CAF scheme with low computational complexity. In this paper, we present an efficient bit-interleaved coded modulation (BICM) scheme for the CAF scheme with phase shift keying (PSK) modulations. In particular, we examine the asymptotic decoding performance of the BICM scheme with low-density parity-check (LDPC) codes by using the density evolution (DE) method. Based on the asymmetric nature of the channel model, we utilize the population dynamics method for the DE equations without the all-zero codeword assumption. The results show that, for two-way relay channels with QPSK and 8PSK modulations, the LDPC-BICM scheme provides higher achievable rate compared with an alternative separation decoding scheme.

We present a novel optimization-based decoding algorithm for LDPC codes that is suitable for hardware architectures specialized to feed-forward neural networks. The algorithm is based on the projected gradient descent algorithm with a penalty function for solving a non-convex minimization problem. The proposed algorithm has several internal parameters such as step size parameters, a softness parameter, and the penalty coefficients. We use a standard tool set of deep learning, i.e., back propagation and stochastic gradient descent type algorithms, to optimize these parameters. Several numerical experiments show that the proposed algorithm outperforms the belief propagation decoding in some cases.

Connectivity of wireless sensor networks (WSNs) is a fundamental global property expected to be maintained even though some sensor nodes are at fault. In this paper, we investigate the connectivity of random geometric graphs (RGGs) in the node fault model as an abstract model of ad hoc WSNs with unreliable nodes. In the model, each node is assumed to be stochastically at fault, i.e., removed from a graph. As a measure of reliability, the network breakdown probability is then defined as the average probability that a resulting survival graph is disconnected over RGGs. We examine RGGs with general connection functions as an extension of a conventional RGG model and provide two mathematical analyses: the asymptotic analysis for infinite RGGs that reveals the phase transition thresholds of connectivity, and the non-asymptotic analysis for finite RGGs that provides a useful approximation formula. Those analyses are supported by numerical simulations in the Rayleigh SISO model reflecting a practical wireless channel.

A low-precision analog-to-digital converter (ADC) is required to implement a frontend device of wideband digital communication systems in order to reduce its power consumption. The goal of this paper is to present a novel quantizer optimization method for minimizing lower-precision quantizers matched to the sum-product algorithms. The principal idea is to introduce a quantizer that includes a feed-forward neural network and the soft staircase function. Since the soft staircase function is differentiable and has non-zero gradient values everywhere, we can exploit backpropagation and a stochastic gradient descent method to train the feed-forward neural network in the quantizer. The expected loss regarding the channel input and the decoder output is minimized in a supervised training phase. The experimental results indicate that the quantizer optimization method successfully provides an 8-level quantizer for a low-density parity-check (LDPC) code that achieves only a 0.1-dB performance loss compared to the unquantized system.

Compute-and-forward relaying is effective to increase bandwidth efficiency of wireless two-way relay channels. In a compute-and-forward scheme, a relay tries to decode a linear combination composed of transmitted messages from other terminals or relays. Design for error correcting codes and its decoding algorithms suitable for compute-and-forward relaying schemes are still important issue to be studied. In this paper, we will present an asymptotic performance analysis on LDPC codes over two-way relay channels based on density evolution (DE). Because of the asymmetric nature of the channel, we employ the population dynamics DE combined with DE formulas for asymmetric channels to obtain BP thresholds. In addition, we also evaluate the asymptotic performance of spatially coupled LDPC codes for two-way relay channels. The results indicate that the spatial coupling codes yield improvements in the BP threshold compared with corresponding uncoupled codes for two-way relay channels.

In this paper, we propose a simple probabilistic construction of connected dominating sets (CDS) that is useful for virtual backbones of wireless ad-hoc networks. In the construction, each node in a network has a random bit and the node joins the virtual backbone if and only if the random bit is one. Our main contribution is to derive the exact formula of the expected success probability of the probabilistic CDS construction over regular graph ensembles. The derivation of the formula is based on a counting argument for a special class of labeled simple graphs with socket nodes. The ensemble average indicates the typical performance of the proposed probabilistic CDS construction and the expected values can be efficiently evaluated in polynomial time.

k-connectivity of random graphs is a fundamental property indicating reliability of multi-hop wireless sensor networks (WSN). WSNs comprising of sensor nodes with limited power resources are modeled by random graphs with unreliable nodes, which is known as the node fault model. In this paper, we investigate k-connectivity of random graphs in the node fault model by evaluating the network breakdown probability, i.e., the disconnectivity probability of random graphs after stochastic node removals. Using the notion of a strongly typical set, we obtain universal asymptotic upper and lower bounds of the network breakdown probability. The bounds are applicable both to random graphs and to random geometric graphs. We then consider three representative random graph ensembles: the Erdös-Rényi random graph as the simplest case, the random intersection graph for WSNs with random key predistribution schemes, and the random geometric graph as a model of WSNs generated by random sensor node deployment. The bounds unveil the existence of the phase transition of the network breakdown probability for those ensembles.

We discuss secure transmission via an untrusted relay when we have a multiple access phase from two nodes to the relay and broadcast phase from the relay to the two nodes. To realize the security, we construct a code that securely transmits the modulo sum of the messages of two nodes via a multiple access channel. In this code, the relay cannot obtain any information for the message of each node, and can decode only the messages of the two nodes. Our code is constructed by simple combination of an existing liner code and universa12 hash function.

In [1], the existence of a nonadaptive group testing scheme with arbitrarily small error probability is shown (Theorems 2 and 3) as the number of defective items scales linearly with the number of items. The claims of Theorems 2 and 3 are invalid.

In the present paper, we derive an upper bound on the average network breakdown probability of packet networks with unreliable relay nodes. We here assume that relay nodes get independently broken with a given node breakdown probability. A survivor graph is the induced subgraph obtained by removing the broken relay nodes and their connecting edges from the original graph. If the survivor network is disconnected, we consider a network breakdown happens. The primal contribution of the paper is to derive an upper bound on the average network breakdown probability, where the expectation is taken over a regular graph ensemble. The proof of the bound is based on a natural one-to-one correspondence between a regular graph and a regular bipartite graph, and also on enumeration of bipartite graphs satisfying certain conditions. This proof argument is inspired by the analysis of weight distribution for low-density parity-check codes. Compared with estimates of the average network breakdown probability obtained by computer experiments, it is observed that the upper bound provides the values which are not only upper bounds but also precise estimates of the network breakdown probability when the node breakdown probability is small.

An information theoretical analysis of nonadaptive group testing schemes based on sparse pooling graphs is presented. A pooling graph is a bipartite graph for which the adjacency matrix is a pooling matrix. The binary status of the objects to be tested are modeled by independent identically distributed. Bernoulli random variables with probability p. An (l, r, n)regular pooling graph is a bipartite graph in which the left nodes have degree l, the right nodes have degree r, and n is the number of left nodes. The main contribution of this paper is a direct coding theorem that gives the conditions for the existence of an estimator that can achieve an arbitrarily small probability of error. An estimator is a function that uses observations to infer the state of an object. The direct coding theorem is proved by averaging the upper bound on the probability of the estimation error of the typical set estimator over an (l, r, n)regular pooling graph ensemble. Numerical results indicate sharp threshold behaviors in the asymptotic regime. These results can provide a concrete benchmark for nonadaptive group testing of existing and emerging detection algorithms over a noiseless system.

In this paper, we will present analysis of the fault erasure BP decoders based on the density evolution. In a fault BP decoder, messages exchanged in a BP process are stochastically corrupted due to unreliable logic gates and flip-flops; i.e., we here assume circuit components with transient faults. We derived a set of the density evolution equations for the fault erasure BP processes. Our density evolution analysis reveals the asymptotic behaviors of the estimation error probability of the fault erasure BP decoders. In contrast to the fault free cases, it is observed that the error probabilities of the fault BP decoder converge to positive values, and that there exists a discontinuity in an error curve corresponding to the fault BP threshold. It is also shown that an message encoding technique provides higher fault BP thresholds than those of the original decoders at the cost of increase of its circuit size.

In order to prevent capacitive crosstalk in on-chip buses, several types of capacitive crosstalk avoidance codes have been devised. These codes are designed to prohibit transition patterns prone to capacitive crosstalk from any consecutive two words transmitted to on-chip buses. This paper provides a rigorous analysis of the asymptotic rate of (p, q)-transition free word sequences under the assumption that coding is based on a pair of a stateful encoder and a stateless decoder. The symbols p and q represent k-bit transition patterns that should not appear in any consecutive two words at the same adjacent k-bit positions. It is proved that the maximum rate of the sequences is equal to the subgraph domatic number of (p, q)-transition free graph. Based on the theoretical results on the subgraph domatic partition problem, a lower and an upper bound on the asymptotic rate is derived. We also show that the asymptotic rate 0.8325 is achievable for p = 01 and q = 10 transition free word sequences.

In the present paper, a simplified two-dimensional magnetic recording (TDMR) channel model is proposed in order to capture the qualitative features of writing and read-back processes of TDMR systems. The proposed channel model incorporates the effects of both linear interference from adjacent bit-cells and signal-dependent noise due to irregular grain boundaries between adjacent bit-cells. The simplicity of the proposed model enables us to derive the closed form of the conditional PDF representing the probabilistic nature of the channel. The conditional PDF is Gaussian distributed and is parameterized by a signal-dependent covariance matrix. Based on this conditional PDF, a Monte Carlo method for approximating the symmetric mutual information of this channel is developed. The symmetric mutual information is closely related to the areal density limit for TDMR systems. The numerical results suggest that we may need low-rate coding, e.g., 2/3 or 1/2, when the jitter-like noise becomes dominant.

The main contribution of this paper is a non-trivial expression, that is called dual expression, of the posterior values for a non-adaptive group testing problem. The dual expression is useful for exact bitwise MAP estimation. We assume a simplest non-adaptive group testing scenario including N-objects with binary status and M-disjunctive tests. If a group contains a positive object, the test result for the group is assumed to be one; otherwise, the test result becomes zero. Our inference problem is to evaluate the posterior probabilities of the objects from the observation of M-test results and from our knowledge on the prior probabilities for objects. The derivation of the dual expression of posterior values can be naturally described based on a holographic transformation to the normal factor graph (NFG) representing the inference problem. In order to handle OR constraints in the NFG, we introduce a novel holographic transformation that converts an OR function to a function similar to an EQUAL function.

A code design problem for memory devices with restricted state transitions is formulated as a combinatorial optimization problem that is called a subgraph domatic partition (subDP) problem. If any neighbor set of a given state transition graph contains all the colors, then the coloring is said to be valid. The goal of a subDP problem is to find the valid coloring that has the largest number of colors for a subgraph of a given directed graph. The number of colors in an optimal valid coloring indicates the writing capacity of that state transition graph. The subDP problems are computationally hard; it is proved to be NP-complete in this paper. One of our main contributions in this paper is to show the asymptotic behavior of the writing capacity C(G) for sequences of dense bidirectional graphs; this is given by C(G) = Ω(n/ ln n), where n is the number of nodes. A probabilistic method, Lovász local lemma (LLL), plays an essential role in deriving the asymptotic expression.

The capacity (or maximum flow) of an unicast network is known to be equal to the minimum s-t cut capacity due to the max-flow min-cut theorem. If the topology of a network (or link capacities) is dynamically changing or unknown, it is not so trivial to predict statistical properties on the maximum flow of the network. In this paper, we present a probabilistic analysis for evaluating the accumulate distribution of the minimum s-t cut capacity on random graphs. The graph ensemble treated in this paper consists of weighted graphs with arbitrary specified degree distribution. The main contribution of our work is a lower bound for the accumulate distribution of the minimum s-t cut capacity. From some computer experiments, it is observed that the lower bound derived here reflects the actual statistical behavior of the minimum s-t cut capacity of random graphs with specified degrees.

In this paper, an information theoretic analysis on non-adaptive group testing schemes based on sparse pooling graphs is presented. The binary status of the objects to be tested are modeled by i.i.d. Bernoulli random variables with probability p. An (l, r, n)-regular pooling graph is a bipartite graph with left node degree l and right node degree r, where n is the number of left nodes. Two scenarios are considered: a noiseless setting and a noisy one. The main contributions of this paper are direct part theorems that give conditions for the existence of an estimator achieving arbitrary small estimation error probability. The direct part theorems are proved by averaging an upper bound on estimation error probability of the typical set estimator over an (l, r, n)-regular pooling graph ensemble. Numerical results indicate sharp threshold behaviors in the asymptotic regime.

The Invertible Bloom Lookup Tables (IBLT) is a data structure which supports insertion, deletion, retrieval and listing operations of the key-value pair. The IBLT can be used to realize efficient set reconciliation for database synchronization. The most notable feature of the IBLT is the complete listing operation of the key-value pairs based on the algorithm similar to the peeling algorithm for low-density parity check (LDPC) codes. In this paper, we will present a stopping set (SS) analysis for the IBLT which reveals finite length behaviors of the listing failure probability. The key of the analysis is enumeration of the number of stopping matrices of given size. We derived a novel recursive formula useful for computationally efficient enumeration. An upper bound on the listing failure probability based on the union bound accurately captures the error floor behaviors. It will be shown that, in the error floor region, the dominant SS have size 2. We propose a simple modification on hash functions, which are called SS avoiding hash functions, for preventing occurrences of the SS of size 2.

In this paper, we present a new exact algorithm for counting perfect matchings, which relies on neither inclusion-exclusion principle nor tree-decompositions. For any bipartite graph of 2n nodes and Δn edges such that Δ ≥ 3, our algorithm runs with O*(2(1-1/O(Δ log Δ))n) time and exponential space. Compared to the previous algorithms, it achieves a better time bound in the sense that the performance degradation to the increase of Δ is quite slower. The main idea of our algorithm is a new reduction to the problem of computing the cut-weight distribution of the input graph. The primary ingredient of this reduction is MacWilliams Identity derived from elementary coding theory. The whole of our algorithm is designed by combining that reduction with a non-trivial fast algorithm computing the cut-weight distribution. To the best of our knowledge, the approach posed in this paper is new and may be of independent interest.

A set of linearly constrained permutation matrices are proposed for constructing a class of permutation codes. The main feature of this class of permutation codes, called linear programming (LP)-decodable permutation codes, is this LP decodability. It is demonstrated that the LP decoding performance of the proposed class of permutation codes is characterized by the vertices of the code polytope of the code. Two types of linear constraints are discussed: one is structured constraints and the other is random constraints. The structured constraints allow an efficient encoding algorithm. On the other hand, the random constraints enable us to use probabilistic methods for analyzing several code properties such as the average cardinality and the average weight distribution.

We evaluate average error exponent of the undetected error probability of binary matrix ensembles by applying statistical-mechanics approach, which is called the “quenched” average error exponent. In the exixting analysis, the “annealed” average error exponent, which is the error exponent of the average undetected error probability, has been evaluated. The quenched average error exponent is more suitable to capture typical behaviors. We show that there are some cases where the annealed exponent is overestimated for the irregular sparse matrix ensemble. We also show that the quenched average error exponent is equivalent to the annealed average error exponents for the regular sparse matrix ensemble.

In this paper, a modified Index-Less Indexed Flash Codes (ILIFC) for flash memory storage system is presented. Although, the ILIFC proposed by Mahdavifar et al. has excellent worst case performance, the ILIFC can be further improved in terms of average case performance. The proposed scheme, called layered-ILIFC, is based on the original ILIFC but our main focus is on the average case performance. It includes an idea of layer-coding for representing indices of information bits. The layer coding promotes uniform use of cells, which leads to better average case performance. In addition, it is shown that the average number of rewritings can be derived by using a Markov chain model. From some experiments, it is observed that the proposed scheme achieves larger average number of rewritings than that of the ILIFC without deterioration of the worst case performance.

A set of linearly constrained permutation matrices are proposed for constructing a class of permutation codes. Making use of linear constraints imposed on the permutation matrices, we can formulate a minimum Euclidian distance decoding problem for the proposed class of permutation codes as a linear programming (LP) problem. The main feature of this novel class of permutation codes, called LP decodable permutation codes, is this LP decodability. It is demonstrated that the LP decoding performance of the proposed class of permutation codes is characterized by the vertices of the code polytope of the code. In addition, based on a probabilistic method, several theoretical results for randomly constrained permutation codes are derived.

We use the replica method of statistical mechanics to examine a typical performance of correctly reconstructing N-dimensional sparse vector x = (xi) from its linear transformation y = Fx of P dimensions on the basis of minimization of the Lp-norm ∥x∥p= lim∈→+0ΣNi=1|xi|p+∈. We characterize the reconstruction performance by the critical relation of the successful reconstruction between the ratio α = P/N and the density ρ of non-zero elements in x in the limit P, N → ∞ while keeping α ~ O(1) and allowing asymptotically negligible reconstruction errors. We show that the critical relation αc(ρ) holds universally as long as FTF can be characterized asymptotically by a rotationally invariant random matrix ensemble and FFTis typically of full rank. This supports the universality of the critical relation observed by Donoho and Tanner (Phil. Trans. R. Soc. A, vol. 367, pp. 4273-4293, 2009; arXiv: 0807.3590) for various ensembles of compression matrices.

A novel class of bit-flipping (BF) algorithm for decoding low-density parity-check (LDPC) codes is presented. The proposed algorithms, which are referred to as gradient descent bit flipping (GDBF) algorithms, can be regarded as simplified gradient descent algorithms. The proposed algorithms exhibit better decoding performance than known BF algorithms, such as the weighted BF algorithm or the modified weighted BF algorithm for several LDPC codes.

In this paper, an ensemble analysis of the undetected error probability of a standard error detection scheme based on a sparse binary parity check matrix is presented. TheBernoulli ensemble, the members of which are considered to be matrices generated from an i.i.d. Bernoulli source, is primarily considered herein. The main contributions of the present study are (i) the derivation of the error exponent of the average undetected error probability and (ii) closed form expressions for the variance of the undetected error probability. The behavior of the exponent for an ensemble of sparse matrices is shown to be somewhat different from that for an ensemble of dense matrices. Furthermore, as a byproduct of the proof of the variance formula, a simple covariance formula of the weight distribution is derived.

In the present paper, a novel decoding algorithm for low-density parity-check (LDPC) codes based on convex optimization is presented. The decoding algorithm, which is referred to hereinafter as interior point decoding, is designed for linear vector channels. The linear vector channels include several practically important channels, such as inter-symbol interference channels and partial response (PR) channels. It is shown that the maximum likelihood decoding (MLD) rule for a linear vector channel can be relaxed to a convex optimization problem, which is called a relaxed MLD problem. The proposed decoding algorithm is based on a numerical optimization technique known as the interior point method with barrier functions. Approximate variations of an interior point method based on the gradient descent and Newton methods are used to solve the relaxed MLD problem. Compared with a conventional joint message-passing decoder, from computer simulations, it is observed that the proposed decoding algorithm achieves better BER performance on PR channels with less decoding complexity in several cases. Furthermore, an extension of the proposed algorithm for high-order modulation formats, such as PAM and QAM, is presented.

The paper presents an implementation of LP decoding algorithm based on the primal path-following interior point method. Numerical examples show some behaviors of an LP decoder based on the exact interior point method. It is shown that very accurate solution can be obtained after 40-50 iterations of the outer loop of the interior point method. Complexity analysis on the proposed algorithm is given as well.

Decoding performance of linear programming (LP) decoding is closely related to geometrical properties of a fundamental polytope: fractional distance, pseudo codeword, etc. In this paper, an idea of the cutting-plane method is employed to improve the fractional distance of a given binary parity-check matrix. The fractional distance is the minimum weight (with respect to lscr1-distance) of nonzero vertices of the fundamental polytope. The cutting polytope is defined based on redundant rows of the parity-check matrix. The redundant rows are codewords of the dual code not yet appearing as rows in the parity-check matrix. The cutting polytope plays a key role to eliminate unnecessary fractional vertices in the fundamental polytope. We propose a greedy algorithm and its efficient implementation based on the cutting-plane method. It has been confirmed that the fractional distance of some parity-check matrices are actually improved by using the algorithm.

In this paper, an analysis of the undetected error probability of ensembles of m × n binary matrices is presented. The ensemble called the Bernoulli ensemble whose members are considered as matrices generated from i.i.d. Bernoulli source is mainly considered here. The main contributions of this work are (i) derivation of the error exponent of the average undetected error probability and (ii) closed form expressions for the variance of the undetected error probability. It is shown that the behavior of the exponent for a sparse ensemble is somewhat different from that for a dense ensemble. Furthermore, as a byproduct of the proof of the variance formula, simple covariance formula of the weight distribution is derived.

In this paper, a novel decoding algorithm for low-density parity-check (LDPC) codes based on convex optimization is presented. The decoding algorithm, called interior point decoding, is designed for linear vector channels. The linear vector channels include many practically important channels such as inter symbol interference channels, partial response channels and MIMO channels. It is shown that the maximum likelihood decoding (MLD) rule for a linear vector channel can be relaxed to a convex optimization problem, which is called a relaxed MLD problem. Approximate variations of gradient descent and Newton methods are used to solve the convex optimization problem.

In this paper, redundant random ensembles are defined and their average stopping set (SS) weight distributions are analyzed. A redundant random ensemble consists of a set of binary matrices with linearly dependent rows. These linearly dependent rows significantly reduce the number of stopping sets (SS) of small size. Upper and lower bounds on the average SS weight distribution of the redundant random ensembles are proved based on a combinatorial argument. Asymptotic forms of these bounds reveal asymptotic behavior of the average SS weight distributions. From these bounds, a tradeoff between the number of redundant rows (corresponding to decoding complexity of belief propagation on binary erasure channel) and the average SS weight distribution (corresponding to decoding performance) can be derived.

In this paper, redundant random matrix ensembles (abbreviated as redundant random ensembles) are defined and their stopping set (SS) weight distributions are analyzed. A redundant random ensemble consists of a set of binary matrices with linearly dependent rows. These linearly dependent rows (redundant rows) significantly reduce the number of stopping sets of small size. Upper and lower bounds on the average SS weight distribution of the redundant random ensembles are shown.

Syndrome entropy of a binary linear code is the entropy corresponding to a product of a binary m times n matrix and a vector of length n generated from a binary i.i.d. source. In this paper, we investigate the syndrome entropy of a matrix contained in an ensemble of m times n binary matrices such as constant row weight ensembles. In the analysis, the first and the second moment of the coset weight distribution of an ensemble play a crucial role

In this paper, the average coset weight distribution (ACWD) of structured ensembles of low-density parity-check (LDPC) matrices, which are called combined ensembles, is discussed. A combined ensemble is composed of a set of simpler ensembles such as a regular bipartite ensemble. Two classes of combined ensembles have prime importance; a stacked ensemble and a concatenated ensemble. The ACWD formulas of these ensembles are shown in this paper. Such formulas play a key role to evaluate the average weight distribution of some classes of combined ensembles

In this paper, an authentication scheme based on an LDPC (low-density parity-check) matrix is presented. Upper bounds on probabilities of impersonate attack and substitution attack have been derived using combinatorial argument on an LDPC ensemble

Linear codes for a coding problem of correlated sources are considered. It is proved that we can construct codes by using low-density parity-check (LDPC) matrices with maximum-likelihood (or typical set) decoding. As applications of the above coding problem, a construction of codes is presented for multiple-access channel with correlated additive noises and a coding theorem of parity-check codes for general channels is proved.

In this correspondence, the average coset weight distributions of Gallager's low-density parity-check (LDPC) code ensemble are investigated. Gallager's LDPC code ensemble consists of regular mtimesn-LDPC matrices with column weight j and row weight k. The average coset weight distribution can be derived by enumerating the number of parity-check matrices in the ensemble satisfying certain conditions. Based on combinatorial arguments, a formula for the average coset weight distribution will be proved. From the formula, we can show some properties of the average coset weight distributions such as equivalence classes of syndromes, symmetry of the distributions, and a lower bound on coset weight

An efficient algorithm for calculating the ith bit error probability of a binary linear code over the binary symmetric channel (BSC) is presented. It is proved that the exact ith bit error probability of maximum-likelihood (ML) decoding, bounded distance decoding, and symbol-wise maximum a posteriori probability (MAP) decoding can be obtained with time complexity O(n2/sup n-k/), where n and k denote the length and the dimension of the target code. The proposed methods are applicable to any binary linear code with redundancy up to nearly 25-30 bits with a typical personal computer.

The paper considers linear matrices for a coding problem for multiple access networks. It is proved that we can construct codes by using sparse matrices, which are also called low density parity check (LDPC) matrices.

A novel DC-free binary convolutional coding scheme is presented. The proposed scheme achieves the DC-free coding and error-correcting capability simultaneously. The scheme has a simple cascaded structure of the running digital sum (RDS) control encoder and the conventional convolutional encoder. A given sequence becomes DC-free if and only if the absolute RDS value of the sequence is bounded by a constant for any time instant. The RDS control encoder generates a sequence which gives the convolutional-coded sequence with a bounded RDS value. The structure allows us to exploit efficient soft-decision decoding which attains additional coding gains compared with hard-decision decoding over an additive white Gaussian noise (AWGN) channel. Bounds on the RDS value are explicitly established for the proposed scheme. By using the bounds, we have performed computer searches for finding good RDS control encoders. The proposed scheme provides wide varieties of reasonable tradeoffs between the coding gain, the RDS constraint, and decoding complexity. For example, a 64-state DC-free coding scheme with the overall rate 6/16 and the minimum free distance 10 has been obtained. This scheme satisfies a bounded RDS constraint (from -18 to +18) and it yields a considerably high asymptotic coding gain (over an AWGN channel) of 5.7 dB.