Search

Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials (when codewords are viewed as evaluation vectors of degree r polynomials in m variables). It then overviews some of the algorithms for decoding RM codes. It covers both algorithms with provable performance guarantees for every block length, as well as algorithms with state-of-the-art performances in practical regimes, which do not perform as well for large block length. Finally, the paper concludes with a few open problems. [ABSTRACT FROM AUTHOR]

This paper shows that for any random variables $X$ and $Y$ , it is possible to represent $Y$ as a function of $(X,Z)$ such that $Z$ is independent of $X$ and $I(X;Z|Y)\le \log (I(X;Y)+1)+4$ bits. We use this strong functional representation lemma (SFRL) to establish a bound on the rate needed for one-shot exact channel simulation for general (discrete or continuous) random variables, strengthening the results by Harsha et al. and Braverman and Garg, and to establish new and simple achievability results for one-shot variable-length lossy source coding, multiple description coding, and Gray–Wyner system. We also show that the SFRL can be used to reduce the channel with state noncausally known at the encoder to a point-to-point channel, which provides a simple achievability proof of the Gelfand–Pinsker theorem. [ABSTRACT FROM AUTHOR]

This paper introduces Manhattan sampling in two and higher dimensions, and proves sampling theorems for them. In 2-D, Manhattan sampling, which takes samples densely along a Manhattan grid of lines, can be viewed as sampling on the union of two rectangular lattices, one dense horizontally and the other vertically, with the coarse spacing of each being a multiple of the fine spacing of the other. The sampling theorem shows that the images bandlimited to the union of the Nyquist regions of the two rectangular lattices can be recovered from their Manhattan samples, and an efficient procedure for doing so is given. Such recovery is possible even though there is an overlap among the spectral replicas induced by Manhattan sampling. In three and higher dimensions, there are many possible configurations for Manhattan sampling, each consisting of the union of special rectangular lattices called bi-step lattices. This paper identifies them, proves a sampling theorem showing that the images bandlimited to the union of the Nyquist regions of the bi-step rectangular lattices are recoverable from Manhattan samples, presents an efficient onion-peeling procedure for doing so, and shows that the union of Nyquist regions is as large as any bandlimited region, such that all images supported by such can be stably reconstructed from samples taken at the rate of the Manhattan sampling. It also develops a special representation for the bi-step lattices with a number of useful properties. While most of this paper deals with continuous-space images, Manhattan sampling of discrete-space images is also considered, for infinite, as well as finite, support images. [ABSTRACT FROM AUTHOR]

This paper considers the signal-to-noise ratio (SNR)-evolution, meaning the behavior as a function of the SNR, of the minimum mean-square error (MMSE) function of code sequences in several multi-user settings in the additive white Gaussian noise regime. The settings investigated in this context include the Gaussian wiretap channel, the Gaussian broadcast channel (BC), and the Gaussian BC with confidential messages (BCC). This paper shows that the specific properties of the SNR-evolution of the MMSE and conditional MMSE functions are necessary and sufficient conditions for capacity or equivocation achieving code sequences. In some cases, the complete SNR-evolution of a family of code sequences can be determined, providing significant insight into the disturbance (in terms of MMSE) such codes have on unintended receivers at other SNRs. Moreover, the effects of an additional MMSE constraint on the capacity region and on the SNR-evolution of code sequences are considered in the BC and BCC settings. Such an analysis emphasizes the tradeoff between rates and limited disturbance on unintended receivers. [ABSTRACT FROM AUTHOR]

Many problems in areas such as compressive sensing and coding theory seek to design a set of equal-norm vectors with large angular separation. This idea is essentially equivalent to constructing a frame with low coherence. The elements of such frames can in turn be used to build high-performance spherical codes, quantum measurement operators, and compressive sensing measurement matrices, to name a few applications. In this paper, we allude to the group-frame construction first described by Slepian and further explored in the works of Vale and Waldron. We present a method for selecting representations of a finite group to construct a group frame that achieves low coherence. Our technique produces a tight frame with a small number of distinct inner product values between the frame elements, in a sense approximating a Grassmannian frame. We identify special cases in which our construction yields some previously known frames with optimal coherence meeting the Welch lower bound, and other cases in which the entries of our frame vectors come from small alphabets. In particular, we apply our technique to the problem choosing a subset of rows of an Hadamard matrix so that the resulting columns form a low-coherence frame. Finally, we give an explicit calculation of the average coherence of our frames, and find regimes in which they satisfy the strong coherence property described by Mixon, Bajwa, and Calderbank. [ABSTRACT FROM AUTHOR]

This paper proposes an adaptive coding (AC) scheme for multilevel bit-interleaved coded modulation (ML-BICM) with minimum mean-square error (MMSE) turbo equalization in frequency-selective multiple-input-multiple-output (MIMO) channels. The aim of this paper is to minimize the information rate loss due to the mismatch between channel realization and channel coding. With the aid of the knowledge about extrinsic information transfer characteristics at the receiver, code parameters such as code rates and/or generator polynomials are adaptively selected independently for each ML-BICM layer. Model-based simulation results show that an achievable average throughput can be significantly improved with the proposed AC technique over automatic repeat request with fixed coding rate. Furthermore, the advantageous points of the proposed scheme are verified through field-measurement-data-based simulations. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

One formidable difficulty in quantum communication and computation is to protect information-carrying quantum states against undesired interactions with the environment. To address this difficulty, many good quantum error-correcting codes have been derived as binary stabilizer codes. Fault-tolerant quantum computation prompted the study of nonbinary quantum codes, but the theory of such codes is not as advanced as that of binary quantum codes. This paper describes the basic theory of stabilizer codes over finite fields. The relation between stabilizer codes and general quantum codes is clarified by introducing a Galois theory for these objects. A characterization of nonbinary stabilizer codes over Fq in terms of classical codes over Fq2 is provided that generalizes the well-known notion of additive codes over F4 of the binary case. This paper also derives lower and upper bounds on the minimum distance of stabilizer codes, gives several code constructions, and derives numerous families of stabilizer codes, including quantum Hamming codes, quadratic residue codes, quantum Melas codes, quantum Bose-Chaudhuri-Hocquenghem (BCH) codes, and quantum character codes. The puncturing theory by Rains is generalized to additive codes that are not necessarily pure. Bounds on the maximal length of maximum distance separable stabilizer codes are given. A discussion of open problems concludes this paper. [ABSTRACT FROM AUTHOR]

Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while sector-disk (SD) codes are erasure codes that address the mixed failure mode of current redundant arrays of independent disk (RAID) systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID 5 and RAID 6. [ABSTRACT FROM AUTHOR]

This paper considers the four-node relay-eavesdropper channel, where a relay node helps the source to send secret messages to the destination in the presence of a passive eavesdropper. For the discrete memoryless case, we propose a hybrid cooperative coding scheme, which is based on the combination of the partial decode-forward scheme, the noise-forward scheme and the random binning scheme. The key feature of the proposed hybrid cooperative scheme is that the relay integrates the explicit cooperation strategy and the implicit cooperation strategy by forwarding source messages and additional interference at the same time. The derived achievable secrecy rate shows that some existing works can be viewed as special cases of the proposed scheme. Then, the achievable secrecy rate is extended to the Gaussian channel based on Gaussian codebooks, and the optimal power policy is also identified in the high power region. Both the analysis and numerical results are provided to demonstrate that the proposed hybrid cooperative coding scheme outperforms the comparable ones, especially in the high power region. [ABSTRACT FROM AUTHOR]

A relatively new model of error correction is the limited magnitude error model. That is, it is assumed that the absolute difference between the sent and received symbols is bounded above by a certain value l. In this paper, we propose systematic codes for asymmetric limited magnitude channels that are able to correct a single error. We also show how this construction can be slightly modified to design codes that can correct a single symmetric error of limited magnitude. The designed codes achieve higher code rates than single error correcting codes previously given in the literature. [ABSTRACT FROM AUTHOR]

It has been known that relaying can provide spatial diversity while satisfying the size-limited constraint of the users' devices in wireless communications systems. For a practically attractive decode-and-forward (DF) relaying system with maximal-ratio combining at the destination, spatial diversity is lost, except when the source-relay link is reliable. To deal with the problem and inspired by the work of Wang et a!., this paper considers and analyzes an adaptive transmission scheme, which is referred to as smart relaying, when only the average relay-destination (R-D) signal-to-noise ratio (SNR) is available at the relay. In the system under consideration, the source continuously transmits the information to the destination. The relay adaptively scales its transmitted power to changes in the channel condition but never exceeds the total power that the conventional relaying used. Performance analysis proves that a diversity order of 2 is always obtained for binary phase-shift keying (BPSK) and quaternary phase-shift keying (QPSK). A diversity order of 2 is also observed for higher order rectangular quadratic-amplitude modulation (QAM) constellations through numerical results. The result on diversity order does not depend on how perfect the R-D feedback channel and how exact the quantization of the power scaling are. All the corresponding results of Wang et al. are subsumed in our analysis. [ABSTRACT FROM AUTHOR]

In this paper, we derive an accurate and simple statistical model for other-cell interference and received signal-to-interference-and-noise ratio (SINR) in single-tier cellular net- works and propose an effective radio channel-estimation scheme from the current and previous feedback information to extract 2-D information on geometry and mobility about the radio channel status of mobile stations. We validate the effectiveness of the proposed scheme by evaluating the performance through mathematical analysis and simulations. Furthermore, we propose a linear SINR prediction scheme to alleviate the performance degradation due to delayed channel state information (CSI), and simulation results demonstrate that the predicted CSI provides a significant increase in throughput gain for the normalized SLNR scheduling, providing a 78.5% increase for a single-tap finite-impulse response (FIR) filter and a 105% increase for a three-tap FIR filter. [ABSTRACT FROM AUTHOR]

In general, link-adaptive schemes, such as adaptive modulation and coding (AMC) and hybrid automatic repeat re- quest (HARQ), enhance system capacity in time-varying wireless channels. For these link-adaptive schemes to be applied, resources have to be adaptively and dynamically allocated every frame. Thus, the system needs control messages to send information to users about dynamic resource allocation. Such information includes user ID, resource position, level of modulation, and coding and automatic repeat request (ARQ) information. However, the transmission of these resource-allocation messages causes control overhead. In this paper, we introduce a scheme that applies AMC to the transmission of resource-allocation messages and analyze its performance in systems that support truncated ARQ, such as link-layer ARQ and HARQ. In addition, we show that using AMC to transmit control messages is a good way to reduce control overhead; in particular, it is very effective when the number of users per frame is large, as in voice over Internet Protocol (VoIP) services. [ABSTRACT FROM AUTHOR]

In conventional interference cancellation (IC)-based turbo receivers, extrinsic information (EXT) from the soft-input-soft-output (SISO) decoders is used to compute the statistical mean (SM) of the interfering signals. In this paper, we present a class of Bayesian minimum mean-square-error (MMSE) turbo receivers for coded multiple-input-multiple-output (MIMO) systems. Instead of using the EXT to estimate the prior SM, we use it in the posterior Bayesian MMSE estimation of the interfering signals. The estimation accuracy is, therefore, improved, leading to better bit-error-rate (BER) performance from our proposed Bayesian receivers. For the cases that we have studied, the proposed receiver with two iterations has a lower BER than the conventional one with five iterations, thus significantly reducing the receiver processing delay and the implementation complexity. Its superior performance is also demonstrated by the higher detector output mutual information and fewer iterations to achieve convergence, which is obtained from the extrinsic information transfer (EXIT) chart analysis. [ABSTRACT FROM AUTHOR]

In orthogonal frequency-division multiplexing (OFDM) systems, a cyclic prefix (CP) is often added at the transmitter and discarded at the receiver. When the length of the CP exceeds the delay spread of the channel, a portion of the CP can be used to recover additional signal energy. In the past, Nyquist windowing techniques have been proposed to recover signal energy, thereby improving performance. In this paper, linear maximum-likelihood (ML) and minimum-mean-square-error (MMSE) approaches are developed, which further improve performance, particularly when the signal-to-noise ratio (SNR) is low. Simpler two-valued windowing (TVW) solutions are also provided, which generally employ one or two non-Nyquist windows. [ABSTRACT FROM AUTHOR]

A recently proposed space-time block-coding (STBC) signal construction method that combines orthogonal design with sphere packing (SP) (referred to here as STBC-SP) has shown useful performance improvements over Alamouti's conventional orthogonal de- sign. In this paper, we propose a purely symbol-based, low-density parity-check (LDPC)-coded scheme, demonstrating that the performance of STBC-SP systems can further be improved by concaterating SP-aided modulation with nonbinary LDPC and by performing symbol-based turbo detection between the nonbinary LDPC decoder and a rate-i nonbinary inner precoder. We also investigate the convergence behavior of this symbol-based concatenated scheme with the aid of novel nonbinary extrinsic information transfer (EXIT) charts. Finally, we demonstrate that in the investigated scenarios, it requires 1-2 dB lower power in comparison with the equivalent effective-throughput 0.5-, 0.75-, and 1-bit-symbol systems employing bit-based turbo detection. [ABSTRACT FROM AUTHOR]

In this paper, a new algorithm for lossless compression of hyperspectral images is proposed. The spectral redundancy in hyperspectral images is exploited using a context-match method driven by the correlation between adjacent bands. This method is suitable for hyperspectral images in the band-sequential format. Moreover, this method compares favorably with the recent pro- posed lossless compression algorithms in terms of compression, with a lower complexity. [ABSTRACT FROM AUTHOR]

Blocking artifacts are major obstacles in block-based transform coding (BTC) for low bit-rate mobile video. In this paper, we present a locally adaptive deblocking technique based on block activities around block boundaries in order to improve the visual quality of mobile video. Pre-processing makes an appropriate filtering mode chosen by removing undesired signals. The proposed filter consists of four modes depending on the types of the artifacts. Experimental results show the effectiveness of the proposed scheme compared with conventional deblocking filters including the H. 264/A VC post-filter with regard to objective and subjective performance. The proposed filter improves PSNR up to 0.8dB compared with the non post-processed video and outperforms conventional filters with reduced complexity compared with the MPEG-4 deblocking filter. [ABSTRACT FROM AUTHOR]

Distributed classification fusion using error-correcting codes (DCFECC) has recently been proposed for wireless sensor networks operating in a harsh environment. It has been shown to have a considerably better capability against unexpected sensor faults than the optimal likelihood fusion. In this paper, we analyze the performance of a DCFECC code with minimum Hamming distance fusion. No assumption on identical distribution for local observations, as well as common marginal distribution for the additive noises of the wireless links, is made. In addition, sensors are allowed to employ their own local classification rules. Upper bounds on the probability of error that are valid for any finite number of sensors are derived based on large deviations technique. A necessary and sufficient condition under which the minimum Hamming distance fusion error vanishes as the number of sensors tends to infinity is also established. With the necessary and sufficient condition and the upper error bounds, the relation between the fault-tolerance capability of a DCFECC code and its pair-wise Hamming distances is characterized, and can be used together with any code search criterion in finding the code with the desired fault-tolerance capability. Based on the above results, we further propose a code search criterion of much less complexity than the minimum Hamming distance fusion error criterion adopted earlier by the authors. This makes the code construction with acceptable fault-tolerance capability for a network with over a hundred of sensors practical. Simulation results show that the code determined based on the new criterion of much less complexity performs almost identically to the best code that minimizes the minimum Hamming distance fusion error. Also simulated and discussed are the performance trends of the codes searched based on the new simpler criterion with respect to the network size and the number of hypotheses. [ABSTRACT FROM AUTHOR]

In this paper, we propose an innovative channel coding scheme called accumulate-repeat-accumulate (ARA) codes. This class of codes can be viewed as serial turbo-like codes or as a subclass of low-density parity check (LDPC) codes, and they have a projected graph or protograph representation; this allows for high-speed iterative decoding implementation using belief propagation. An ARA code can be viewed as precoded repeat accumulate (RA) code with puncturing or as precoded irregular repeat accumulate (IRA) code, where simply an accumulator is chosen as the precoder. The amount of performance improvement due to the precoder will be called precoding gain. Using density evolution on their associated protographs, we find some rate-½ ARA codes, with a maximum variable node degree of 5 for which a minimum bit SNR as low as 0.08 dB from channel capacity threshold is achieved as the block size goes to infinity. Such a low threshold cannot be achieved by RA, IRA, or unstructured irregular LDPC codes with the same constraint on the maximum variable node degree. Furthermore, by puncturing the inner accumulator, we can construct families of higher rate ARA codes with thresholds that stay close to their respective channel capacity thresholds uniformly. Iterative decoding simulation results are provided and compared with turbo codes. In addition to iterative decoding analysis, we analyzed the performance of ARA codes with maximum-likelihood (ML) decoding. By obtaining the weight distribution of these codes and through existing tightest bounds we have shown that the ML SNR threshold of ARA codes also approaches very closely to that of random codes. These codes have better interleaving gain than turbo codes. [ABSTRACT FROM AUTHOR]

Practical applications that employ entropy coding for large alphabets often partition the alphabet set into two or more layers, and encode each symbol by using some suitable prefix coding for each layer. In this paper, we formulate the problem of finding an alphabet partitioning for the design of a two-layer semiadaptive code as an optimization problem, and give a solution based on dynamic programming. However, the complexity of the dynamic programming approach can be quite prohibitive for a long sequence and a very large alphabet size. Hence, we also give a simple greedy heuristic algorithm whose running time is linear in the length of the input sequence, irrespective of the underlying alphabet size. Although our dynamic programming and greedy algorithms do not provide a globally optimal solution for the alphabet partitioning problem, experimental results demonstrate that superior prefix coding schemes for large alphabets can be designed using our new approach. [ABSTRACT FROM AUTHOR]

Error exponents are studied for recursive decoding of Reed-Muller (RM) codes and their subcodes used on a binary-symmetric channel. The decoding process is first decomposed into similar steps, with one new information bit derived in each step. Multiple recursive additions and multiplications of the randomly corrupted channel outputs ±1 are performed using a specific order of these two operations in each step. Recalculated random outputs are compared in terms of their exponential moments. As a result, tight analytical bounds are obtained for decoding error probability of the two recursive algorithms considered in the paper. For both algorithms, the derived error exponents almost coincide with simulation results. Comparison of these bounds with similar bounds for bounded distance decoding and majority decoding shows that recursive decoding can reduce the output error probability of the latter two algorithms by five or more orders of magnitude even on the short block length of 256. It is also proven that the error probability of recursive decoding can be exponentially reduced by eliminating one or a few information bits from the original RM code. [ABSTRACT FROM AUTHOR]

The stopping redundancy of the code is an important parameter which arises from analyzing the performance of a linear code under iterative decoding on a binary erasure channel. In this paper, we will consider the stopping redundancy of Reed-Muller codes and related codes. Let R(l, m) be the Reed-Muller code of length 2m and order l. Schwartz and Vardy gave a recursive construction of parity-check matrices for the Reed-Muller codes, and asked whether the number of rows in those parity-check matrices is the stopping redundancy of the codes. We prove that the stopping redundancy of R(m - 2, m), which is also the extended Hamming code of length 2m, is 2m - 1 and thus show that the recursive bound is tight in this case. We prove that the stopping redundancy of the simplex code equals its redundancy. Several constructions of codes for which the stopping redundancy equals the redundancy are discussed. We prove an upper bound on the stopping redundancy of R(1, m). This bound is better than the known recursive bound and thus gives a negative answer to the question of Schwartz and Vardy. [ABSTRACT FROM AUTHOR]

The H.264/A VC adopted an intra prediction scheme that enables high coding efficiency for intra-coded frames. However, the intra prediction scheme of H. 264/A VC may cause flicker in intra-coded frames of the intra prediction modes are not appropriately selected for coding. In this paper, we propose an intra prediction mode selection method for H.264/A VC by using a modified distortion measure for rate distortion optimized mode selection that does not only consider the distortion between the input and the reconstructed macro blocks, but also the between-frame consistency of distortion between two successive frames to reduce flicker in intra-coded frames. Experimental results demonstrate that our proposed method reduces significant amount of flicker with a negligible change in PSNR and bitrate. [ABSTRACT FROM AUTHOR]

In this paper, the construction of new families of error-correcting codes adapted from Boutros and Lentmaier's generalized low-density (GLD) codes, which we called generalized irregular low-density (GILD) codes, is investigated. By introducing irregular base matrices, significant improvements on Boutros and Lentmaier's results are achieved. Two cases are considered; in the first case, the same constituent code is used, and in the second case, different constituent codes are used. It is proved by an ensemble performance argument that these codes exist and are asymptotically good in the sense of the minimum-distance criterion. It is also proved that the performance of GILD codes approaches the binary symmetric channel capacity limit. Iterative decoding of GILD codes for communication over an additive white Gaussian noise channel is also studied. The high flexibility in selecting the parameters of GILD codes and their better performance and higher rate make them more attractive than GLD codes, and hence, suitable for small and medium block lengths forward-error-correcting schemes. Comparisons of simulation results between some GILD codes and some good low-density parity-check codes show very close performances. [ABSTRACT FROM AUTHOR]

The case when the modulation index is 0.5 in continuous phase frequency shift keying (CPFSK) is called fast frequency shift keying (FFSK). In this paper, a trellis-coded multidimensional modulation scheme using FFSK is proposed. In implementing a multidimensional modulation system, the complexity of decoding associated with the maximum likelihood decoding based on a Viterbi algorithm and the trellis coding design become problematic. In particular, the latter is influenced significantly by the path memory of the Viterbi decoder and the size of the scale of the ACS circuit, becoming a big problem in implementing the system. Thus, in this scheme, the complexity of decoding is alleviated by constructing the trellis decoder from multiple finite state machines and using a pseudo-multistage decoding method. Thus, the search and optimization of codes capable of using this multistage decoding algorithm are investigated. The bit error rate performance of codes having less decoding complexity as compared with the past best decoding is evaluated by computer simulation and the efficacy of the proposed scheme is shown. ©1999 Scripta Technica, Electron Comm Jpn Pt 3, 83(3): 70–83, 2000 [ABSTRACT FROM AUTHOR]

This paper examines different designs for combined channel estimation and decoding for a point to point time varying frequency selective fading channel. The channel state information (CSI) is not known a priori at either the transmitter or the receiver. Channel estimation is performed through a combination of conventional pilots and manufactured pilots from previously decoded data. The paper examines how different interleaver structures affect the tradeoff between achievable rates, delay and complexity. When there is no delay constraint at all, the conventional pilots can be eliminated completely and a proper interleaving scheme can convert half the symbols into manufactured pilots. When there is a delay constraint, the paper explores various interleaver structures that combine the conventional pilots with the manufactured pilots in different ways to get much better achievable rates than conventional pilot-symbol aided channel estimation. [ABSTRACT FROM AUTHOR]