A multi-dimensional shaping scheme based on multi-level Maximum Average Weight (MAW)-codes is presented. One can reduce the average energy of transmitted signal, by using low energy signal points more frequently than high energy ones. The proposed scheme employs a multi-dimensional region of 2,4,6 and 8 dimensions; these regions are selected using a multi-level MAW-code. A multi-level MAW-code is a q-ary code and has unequal probability of the occurrence of a symbol. The scheme can achieve a shaping gain of 0.6-1.0 dB with small constellation expansion ratio and peak to average energy ratio. This scheme is based on a two-level table look up algorithm. Therefore, the less complexity of encoding/decoding can be realized.

This paper studies the zero error capacity of the Nearest Neighbor Error (NNE) channels with a multilevel alphabet. In the NNE channels, a transmitted symbol is a d-tuple of elements in {0,1,2,...,l-1}. It is assumed that only one element error to a nearest neighbor element in a transmitted symbol can occur. The NNE channels can be considered as a special type of limited magnitude error channels, and it is closely related to error models for flash memories. In this paper, we derive a lower bound of the zero error capacity of the NNE channels based on a result of the perfect Lee codes. An upper bound of the zero error capacity of the NNE channels is also derived from a feasible solution of a linear programming problem defined based on the confusion graphs of the NNE channels. As a result, a concise formula of the zero error capacity is obtained using the lower and upper bounds.

An Invertible Bloom Lookup Tables (IBLT) is a data structure which supports insertion, deletion, retrieval and listing operations for the key-value pair. An 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 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 that 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.

In this paper, we will present analysis on the fault erasure BP decoders based on the density evolution. In the fault BP decoder, the messages exchanged in a BP process are stochastically corrupted due to unreliable logic gates and flip-flops; i.e., we 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 erasure 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 increased circuit size.

In this paper, an iterative decoding algorithm for channels with additive linear dynamical noise is presented. The proposed algorithm is based on the tightly coupled two inference algorithms: the sum-product algorithm which infers the information symbols of an low density parity check (LDPC) code and the Kalman smoothing algorithm which infers the channel states. The linear dynamical noise are the noise generated from a linear dynamical system. We often encounter such noise (i.e., additive colored noise) in practical communication and storage systems. The conventional iterative decoding algorithms such as the sum-product algorithm cannot derive full potential of turbo codes nor LDPC codes over such a channel because the conventional algorithms are designed under the independence assumption on the noise. Several simulations have been performed to assess the performance of the proposed algorithm. From the simulation results, it can be concluded that the Kalman smoothing algorithm deserves to be implemented in a decoder when the linear dynamical part of the linear dynamical noise is dominant rather than the white Gaussian noise part. In such a case, the performance of the proposed algorithm is far superior to that of the conventional algorithm.

The main contribution of this paper is a non-trivial expression, that is called dual expression, of the posterior values for non-adaptive group testing problems. 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-tests. If a group contains one or more 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 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.

We present an 8-dimensional trellis-coded 8-PSK with a symbol transition constraint that is similar to that of π/4-shift quadrature phase shift keying (QPSK). This scheme can achieve a coding gain of 1.6 to 2.4 dB at the same rate of π/4-shift QPSK on Gaussian channel, and it has also an immunity against the integer multiples of 90 phase ambiguities. In order to label the constellation of the proposed scheme, a constellation partitioning algorithm is presented. This algorithm, on the basis of set partitioning, can be used to label the signal constellation with no coset structure.

In this paper, we present a method for evaluating the minimum free Chernov distance of trellis-codes for a discrete memoryless channels (DMC). In order to design an efficient trellis-code for the DMC, we need to evaluate the minimum free Chernov distance of the target code. However, the lack of the additive property of the Chernov distance prevents a conventional branch-and-bound search for evaluating the minimum distance. To overcome the difficulty, we present a lower bound on the Chernov distance with an additive property. The lower bound plays a key role in the minimum distance evaluation algorithm presented here. By using the proposed algorithm, we have derived the minimum free Chernov distance of some binary linear convolutional codes over Z-channel.

A new design method, which is referred to as the matched design method, for concatenated trellis-coded modulation (TCM) is presented. Most of the conventional concatenated TCM employs TCM designed to maximize the minimum squared Euclidean free distance, d2free. With the matched design method, we maximize d21(t) instead of d2free, where d21(t) is the effective minimum squared Euclidean distance (MSED) when the outer code has a t-error correcting capability. The effective MSED is derived from the Euclidean/Hamming (E/H) joint weight distribution of terminated TCM. We here assume the concatenated TCM whose transmitted symbol corresponds to a symbol of outer code. The new classes of 2-dimensional (2D) and 4-dimensional (4D) codes are found by a computer search. Under the performance measures of the effective MSED or the effective multiplicity, these codes are superior to the conventional codes such as the Ungerboeck's 2D-codes when those are used as an inner code. We disclose an interesting fact that the new class of codes using rate-1/2 encoder is superior to the class of codes using rate-2/3 encoder. This fact implies that the codes using rate-1/2 encoder have two advantages: 1) better overall decoding performance and 2) less decoding complexity.

An algorithm for augmenting a binary linear code is presented. The input to the code augmenting algorithm is (n,k,d) code C and the output is an (n,k*,d) augmented code C (k* k) satisfying C C and the Gilbert bound. The algorithm can be considered as an efficient implementation of the proof of Gilbert bound; for a given binary linear code C, the algorithm first finds a coset leader with the largest weight. If the weight of the coset leader is greater than or equal to the minimum distance of C, the coset leader is included to the basis of C.

Gallager has defined an ensemble of regular low density parity check (LDPC) codes for deriving the ensemble performance of regular LDPC codes. The ensemble is called the Gallager ensemble. In this paper, we define a new ensemble of LDPC codes, called extended Gallager ensemble, which is a natural extension of the Gallager ensemble. It is shown that an extended Gallager ensemble has potential to achieve larger typical minimum distance ratio than that of the original Gallager ensemble. In particular, the extended Gallager ensembles based on the Hamming and extended Hamming codes have typical minimum distance ratio which is very close to the asymptotic Gilbert-Varshamov bound. Furthermore, decoding performance of an instance of an extended Gallager ensemble, called an extended LDPC code, has been examined by simulation. The results show good block error performance of extended LDPC codes.

In the present paper, we propose a broadcast ARQ protocol based on the concept of index coding. In the proposed scenario, a server wishes to transmit a finite sequence of packets to multiple receivers via a broadcast channel with packet erasures until all of the receivers successfully receive all of the packets. In the retransmission phase, the server produces a coded packet as a retransmitted packet based on the side-information sent from the receivers via feedback channels. A notable feature of the proposed protocol is that the decoding process at the receiver side has low decoding complexity because only a small number of addition operations are needed in order to recover an intended packet. This feature may be preferable for reducing the power consumption of receivers. The throughput performance of the proposed protocol is close to that of the ideal FEC throughput performance when the erasure probability is less than 0.1. This implies that the proposed protocol provides almost optimal throughput performance in such a regime.

We present a new class of trellis-codes for partial-response channel. Our code configuration is based on the coded 1 - D scheme due to Wolf and Ungerboeck. However, no precoder between a convolutional encoder and the partialresponse channel is used. A new lower bound on the minimum free squared Euclidean distance of channel code is shown. The bound is available for any PR channel with a finite response. New codes for 1 - D and (1 - D) (1 + D)2 channels are found by computer code search using the lower bound. Some of the new codes have excellent properties: a significant d2free and a small decoding complexity.

This paper presents a new upper bound on overall bit error rate (BER) for a concatenated code which consists of an inner convolutional code and an outer interleaved Reed-Solomon code. The upper bound on BER is derived based on a lower bound on the effective minimum distance of the concatenated code. This upper bound can be used for the cases when the interleaver size is small such that the conventional upper bound is not applicable.

In this paper, we propose a construction of non-binary WOM (Write-Once-Memory) codes for WOM storages such as flash memories. The WOM codes discussed in this paper are fixed rate WOM codes where messages in a fixed alphabet of size M can be sequentially written in the WOM storage at least t*-times. In this paper, a WOM storage is modeled by a state transition graph. The proposed construction has the following two features. First, it includes a systematic method to determine the encoding regions in the state transition graph. Second, the proposed construction includes a labeling method for states by using integer programming. Several novel WOM codes for q level flash memories with 2 cells are constructed by the proposed construction. They achieve the worst numbers of writes t* that meet the known upper bound in the range 4≤q≤8, M=8. In addition, we constructed fixed rate non-binary WOM codes with the capability to reduce ICI (inter cell interference) of flash cells. One of the advantages of the proposed construction is its flexibility. It can be applied to various storage devices, to various dimensions (i.e, number of cells), and various kind of additional constraints.

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

It is well known that spatially coupled (SC) codes with erasure-BP decoding have powerful error correcting capability over memoryless erasure channels. However, the decoding performance of SC-codes significantly degrades when they are used over burst erasure channels. In this paper, we propose band splitting permutations (BSP) suitable for (l,r,L) SC-codes. The BSP splits a diagonal band in a base matrix into multiple bands in order to enhance the span of the stopping sets in the base matrix. As theoretical performance guarantees, lower and upper bounds on the maximal burst correctable length of the permuted (l,r,L) SC-codes are presented. Those bounds indicate that the maximal correctable burst ratio of the permuted SC-codes is given by λmax≃1/k where k=r/l. This implies the asymptotic optimality of the permuted SC-codes in terms of burst erasure correction.

In the field of computer science, the network reliability problem for evaluating the network failure probability has been extensively investigated. For a given undirected graph G, the network failure probability is the probability that edge failures (i.e., edge erasures) make G unconnected. Edge failures are assumed to occur independently with the same probability. The main contributions of the present paper are the upper and lower bounds on the expected network failure probability. We herein assume a simple random graph ensemble that is closely related to the Erds-Rényi random graph ensemble. These upper and lower bounds exhibit the typical behavior of the network failure probability. The proof is based on the fact that the cut-set space of G is a linear space over F2 spanned by the incident matrix of G. The present study shows a close relationship between the ensemble analysis of the expected network failure probability and the ensemble analysis of the error detection probability of LDGM codes with column weight 2.

A coded modulation scheme based on a low density parity check (LDPC) code is presented. A modified sum-product algorithm suitable for the LDPC-coded modulation scheme is also devised. Several simulation results show the excellent decoding performance of the proposed coding scheme. For example, an LDPC-coded 8PSK scheme of block length 3976 symbols achieves the symbol error probability 10-5 at only 1.2 dB away from the Shannon limit of the channel.

This paper presents a novel optimization-based decoding algorithm for LDPC codes. The proposed decoding algorithm is based on a proximal gradient method for solving an approximate maximum a posteriori (MAP) decoding problem. The key idea of the proposed algorithm is the use of a code-constraint polynomial to penalize a vector far from a codeword as a regularizer in the approximate MAP objective function. A code proximal operator is naturally derived from a code-constraint polynomial. The proposed algorithm, called proximal decoding, can be described by a simple recursive formula consisting of the gradient descent step for a negative log-likelihood function corresponding to the channel conditional probability density function and the code proximal operation regarding the code-constraint polynomial. Proximal decoding is experimentally shown to be applicable to several non-trivial channel models such as LDPC-coded massive MIMO channels, correlated Gaussian noise channels, and nonlinear vector channels. In particular, in MIMO channels, proximal decoding outperforms known massive MIMO detection algorithms, such as an MMSE detector with belief propagation decoding. The simple optimization-based formulation of proximal decoding allows a way for developing novel signal processing algorithms involving LDPC codes.