Search

The capacity region of the finite-state multiple-access channel (FS-MAC) with feedback that may be an arbitrary time-invariant function of the channel output samples is considered. We characterize both an inner and an outer bound for this region, using Massey's directed information. These bounds are shown to coincide, and hence yield the capacity region, of indecomposable FS-MACs without feedback and of stationary and indecomposable FS-MACs with feedback, where the state process is not affected by the inputs. Though "multiletter" in general, our results yield explicit conclusions when applied to specific scenarios of interest. For example, our results allow us to do the following. * Identify a large class of FS-MACs, that includes the additive mod2 noise MAC where the noise may have memory, for which feedback does not enlarge the capacity region. * Deduce that, for a general FS-MAC with states that are not affected by the input, if the capacity (region) without feedback is zero, then so is the capacity (region) with feedback. * Deduce that the capacity region of a MAC that can be decomposed into a "multiplexer" concatenated by a point-to-point channel (with, without, or with partial feedback), the capacity region is given by [[summation].sub.m] [R.sub.m] [less than or equal to] C, where C is the capacity of the point to point channel and m indexes the encoders. Moreover, we show that for this family of channels source--channel coding separation holds. Index Terms--Capacity region, causal conditioning, code-tree, directed information, feedback capacity, multiple-access channel (MAC), source--channel coding separation, sup-additivity of sets.

Low-density parity-check (LDPC) codes may be decoded using a circuit implementation of the sum-product algorithm which maps the factor graph of the code. By reusing the decoder for encoding, both tasks can be performed using the same circuit, thus reducing area and verification requirements. Motivated by this, iterative encoding techniques based upon the graphical representation of the code are proposed. Code design constraints which ensure encoder convergence are presented, and then used to design iteratively encodable codes, while also preventing 4-cycle creation. We show how the Jacobi method for iterative matrix inversion can be applied to finite field matrices, viewed as message passing, and employed as the core of an iterative encoder. We present an algebraic construction of 4-cycle free iteratively encodable codes using circulant matrices. Analysis of these codes identifies a weakness in their structure, due to a repetitive pattern in the factor graph. The graph supports pseudo-codewords of low pseudo-weight. In order to remove the repetitive pattern in the graph, we propose a recursive technique for generating iteratively encodable codes. The new codes offer flexibility in the choice of code length and rate, and performance that compares well to randomly generated, quasi-cyclic and extended Euclidean-geometry codes. Index Terms--Bipartite graph, block codes, codes on graphs, cycles in a graph, encoding, iterative decoding, linear codes, low-density parity-check (LDPC) codes, sparse matrices.

Unification grammars are widely used for encoding human knowledge. For unification systems, one major difficulty is the debugging of rules. In this paper, the authors suggest a novel method based on model checking to theoretically verify a complex grammar system for a unification-based parser. We propose the modeling method of the grammar and, more importantly, the abstraction method to compress the state space. We apply partial Kripke structures to model the rules. We prove that the state space can be reduced by several orders of magnitude while still keeping the behaviors of a noncompressed one. Practical verification issues are discussed, including the restrictions on specifications, the properties to check, etc. The proposed method will contribute to the effective debugging and application of unification grammars. Index Terms--Model checking, natural language understanding, unification grammar.

We report a new method for designing (M, d, k) constrained codes for use in multi-level optical recording channels. The method allow us to design practical codes, which have simple encoder tables and decoders having fixed window length. The codes presented here for the d = 1 and d = 2 cases, achieve higher storage densities than previously reported codes, and come within 0.3 - 0.7% of capacity. Index Terms--Multi-level optical recording, runlength-limited sequences, channel capacity, (M, d, k) sequences.

This paper presents a HD1080p 30-frames/s H.264 intra encoder operated at 140 MHz with just 94 K gate count and 0.72-[mm.sup.2] core area for digital video recorder or digital still camera applications. To achieve high throughput and low area cost for high-definition video, we apply the modified three-step fast intra prediction technique to reduce the cycle count while keeping the quality as close as full search. Then, in architecture scheduling, we further adopt the variable pixel parallelism instead of constant four-pixel parallelism to speed up performance on the critical intra prediction part while keeping other parts unchanged for low area cost. The achieved design only needs half of the working frequency and reduces the gate count cost by 23.5% compared with the previous design with the same HD720p 30-frames/s requirement. Besides, our design at 140 MHz can support HD1080p 30 frames/s for digital video encoder or 4096 x 2304 images with 6.78 frames/s for digital still camera application. Index Terms--H.264, intra prediction, VLSI architecture.

The highly error-prone nature of wireless environments and limited computational power of mobile devices necessitates the implementation of robust yet simple error concealment in H.264/AVC. In this paper, we propose to use data hiding to facilitate the error concealment on intra-coded frames that utilizes the temporal redundancy in a wireless video bitstream. At the encoder side, the motion vector of a macroblock (MB) is encoded and imperceptibly embedded into other MB within the same intra-frame. If an MB is found missing at the decoder, the embedded information will be retrieved from the corresponding MB for the recovery of the lost MB. In order to isolate erroneous MBs caused by packet loss, a block shuffling scheme is applied. It is shown that the proposed method is able to shift the computation burden from decoder to encoder, and reduce the computation complexity of conventional error concealment methods. In addition, due to the use of real motion vectors for temporal concealment, the proposed method provides improved picture quality over the reference methods in H.264/AVC. Index Terms--Error concealment, video transmission, wireless video.

Moran, Naor, and Segev have asked what is the minimal r = r(n, k) for which there exists an (n, k)-monotone encoding of length r, i.e., a monotone injective function from subsets of size up to k of {1, 2, ..., n} to r bits. Monotone encodings are relevant to the study of tamper-proof data structures and arise also in the design of broadcast schemes in certain communication networks. To answer this question, we develop a relaxation of k-superimposed families, which we call [alpha]-fraction k-multiuser tracing [sub.*]((k, [alpha])-FUT (fraction user-tracing) families). We show that r(n, k) = [THETA](k log(n/k)) by proving tight asymptotic lower and upper bounds on the size of (k, [alpha])-FUT families and by constructing an (n, k)-monotone encoding of length O(k log(n/k)). We also present an explicit construction of an (n, 2)-monotone encoding of length 2 log n + O(1), which is optimal up to an additive constant. Index Term--Monotone encoding, multiuser tracing, superimposed codes.

In this paper, we describe and analyze the source and channel coding properties of a class of sparse graphical codes based on compounding a low-density generator matrix (LDGM) code with a low-density parity-check (LDPC) code. Our first pair of theorems establishes that there exist codes from this ensemble, with all degrees remaining bounded independently of block length, that are simultaneously optimal for both channel coding and source coding with binary data when encoding and decoding are performed optimally. More precisely, in the context of lossy compression, we prove that finite-degree constructions can achieve any pair (R, D) on the rate-distortion curve of the binary symmetric source. In the context of channel coding, we prove that the same finite-degree codes can achieve any pair (C, p) on the capacity-noise curve of the binary symmetric channel (BSC). Next, we show that our compound construction has a nested structure that can be exploited to achieve the Wyner--Ziv bound for source coding with side information (SCSI), as well as the Gelfand--Pinsker bound for channel coding with side information (CCSI). Although the results described here are based on optimal encoding and decoding, the proposed graphical codes have sparse structure and high girth that renders them well suited to message passing and other efficient decoding procedures. Index Terms--Channel coding, coding with side information, distributed source coding, Gelfand--Pinsker problem, graphical codes, information embedding, low-density generator matrix code (LDGM), low-density parity-check code (LDPC), source coding, weight enumerator, Wyner--Ziv problem.

We present a novel technique for encoding and decoding constant weight binary vectors that uses a geometric interpretation of the codebook. Our technique is based on embedding the codebook in a Euclidean space of dimension equal to the weight of the code. The encoder and decoder mappings are then interpreted as a bijection between a certain hyper-rectangle and a polytope in this Euclidean space. An inductive dissection algorithm is developed for constructing such a bijection. We prove that the algorithm is correct and then analyze its complexity. The complexity depends on the weight of the vector, rather than on the block length as in other algorithms. This approach is advantageous when the weight is smaller than the square root of the block length. Index Terms--Constant weight codes, encoding algorithms, dissections, polyhedral dissections, bijections, mappings, Dehn invariant.

We present a new class of irregular low-density parity-check (LDPC) codes for moderate block lengths (up to a few thousand bits) that are well-suited for rate-compatible puncturing. The proposed codes show good performance under puncturing over a wide range of rates and are suitable for usage in incremental redundancy hybrid-automatic repeat request (ARQ) systems. In addition, these codes are linear-time encodable with simple shift-register circuits. For a block length of 1200 bits the codes outperform optimized irregular LDPC codes and extended irregular repeat-accumulate (eIRA) codes for all puncturing rates 0.6~0.9 (base code performance is almost the same) and are particularly good at high puncturing rates where good puncturing performance has been previously difficult to achieve. Index Terms--Efficient encoding, low-density parity-check (LDPC) code, puncturing, rate-compatible code.

The partition function pertaining to finite-temperature decoding of a (typical) randomly chosen code is known to have three types of behavior, corresponding to three phases in the plane of rate versus temperature: the ferromagnetic phase, corresponding to correct decoding, the paramagnetic phase, of complete disorder, which is dominated by exponentially many incorrect codewords, and the glassy phase (or the condensed phase), where the system is frozen at minimum energy and dominated by subexponentially many incorrect codewords. We show that the statistical physics associated with the two latter phases are intimately related to random coding exponents. In particular, the exponent associated with the probability of correct decoding at rates above capacity is directly related to the free energy in the glassy phase, and the exponent associated with probability of error (the error exponent) at rates below capacity, is strongly related to the free energy in the paramagnetic phase. In fact, we derive alternative expressions of these exponents in terms of the corresponding free energies, and make an attempt to obtain some insights from these expressions. Finally, as a side result, we also compare the phase diagram associated with a simple finite-temperature universal decoder, for discrete memoryless channels, to that of the finite-temperature decoder that is aware of the channel statistics. Index Terms--Error exponents, free energy, partition function, phase transitions, random coding, random energy model (REM).

This paper extends the theory of data synchronization with timing for fixed-rate codes, previously developed by the authors, to the variable-rate case. Given a source code, a class of sync-timing codes called variable-rate cascaded (VRC) codes is considered that "wrap around" the source code in such a way as to enable the decoder to not only resynchronize rapidly when the encoded bits are corrupted by insertion, deletion, or substitution errors, but also produce estimates of the time indices of the data symbols encoded by the source code. The estimates of the time indices are modulo-T reductions of the actual time indices, for some integer T called the timing span of the code. These sync-timing codes are analyzed on the basis of the maximum timing span achievable for a given coding rate R and permissible resynchronization delay D. It is shown that the timing span of VRC codes is upper-bounded by [2.sup.D(1-R)+o(D)], and that this upper bound is achievable asymptotically in D. This exponential rate of growth of timing span with delay is the same as that found previously for certain fixed-rate sync-timing codes, e.g., (fixed-rate) cascaded codes. Index Terms--Cascaded codes, resynchronization delay, sync-timing codes, timing span, variable-rate cascaded (VRC) codes.

A new technique to lower-bound the minimum distance of certain types of quasi-cyclic codes with large dimension by reducing the problem to lower-bounding the minimum distance of a few significantly smaller codes has been developed. These codes have the property that they have extremely efficient software encoders. Using this technique, it is proved that a code which is similar to the SHA-1 (Secure Hash Algorithm, to be explained shortly) message expansion code has minimum distance 82, and that too in just the last 64 of the 80 expanded words. In fact, the proposed code has much greater distance than that of SHA-1 code, which makes our proposed hashing scheme robust against cryptographic attacks. The technique is further used to find the minimum weight of the SHA-1 code itself (25 in last 60 words), which was an open problem. Estimating minimum distance of a code given by its parity-check matrix is well known to be a hard problem. Our technique is expected to be helpful in estimating minimum distance of similar codes as well as in designing future practical cryptographic hash functions. Index Terms--Collision-resistant hash functions, linear codes, minimum distance, quasi-cyclic codes, Secure Hash Algorithm (SHA-1).

An XML publish/subscribe system needs to filter a large number of queries over XML streams. Most existing systems only consider filtering the simple XPath statements. In this paper, we focus on filtering of the more complex Generalized- Tree-Pattern (GTP) queries. Our filtering mechanism is based on a novel Tree-of-Path (TOP) encoding scheme, which compactly represents the path matches for the entire document. First, we show that the TOP encodings can be efficiently produced via shared bottom-up path matching. Second, with the aid of this TOP encoding, we can 1) achieve polynomial time and space complexity for postprocessing, 2) avoid redundant predicate evaluations, 3) allow an efficient duplicate-free and merge join-based algorithm for merging multiple encoded path matches, and 4) simplify the processing of GTP queries. Overall, our approach maximizes the sharing opportunity across queries by exploiting the suffix as well as prefix sharing. At the same time, our TOP encodings allow efficient postprocessing for GTP queries. Extensive performance studies show that GFilter not only achieves significantly better filtering performance than state-of-the-art algorithms but also is capable of efficiently filtering the more complex GTP queries. Index Terms--XML filtering, XML streams, generalized-tree-pattern queries, result encoding.

In this paper, a unified framework for the analysis of differential detection (DD) schemes in time-variant multiple--input multiple--output Rayleigh fading channels is provided. The present results are very general in that they apply to transmission with differential phase-shift keying, unitary differential space--time modulation (DSTM), and block DSTM and reception with conventional DD (CDD), multiple-symbol DD (MSDD), decision--feedback DD (DFDD), and (differentially) coherent detection (CD). New result for general quadratic forms of Gaussian random variables are derived which allows us to obtain elegant closed--form expressions for the pairwise error probabilities (PEPs) of the dominant error events of the considered detectors. Furthermore, it is shown that a unified treatment of all considered detectors is possible with a properly defined effective signal--to--noise ratio (ESNR) and a useful connection between MSDD and minimum--mean--squared--error (MMSE) interpolation is established. Interesting novel results obtained from this analysis include: (i) DSTM constellations designed for CDD and CD are also optimum for MSDD and DFDD; (ii) the error floor entailed by MSDD and DFDD in time--variant fading decreases exponentially with the observation window size N; and (iii) in time--variant fading with effective normalized fading bandwidth [B.sub.h,eff]T MSDD with N [right arrow] [infinity] suffers only from an SNR loss of (1 - 2[B.sub.h,eff]T) compared to CD, whereas DFDD suffers from a diversity loss of (1 - 2[B.sub.h,eff]T). Index Terms--Performance analysis, differential space time modulation, MIMO fading channels.

The impact of side information about the distortion measure in problems of quantization is analyzed. It is shown that such "distortion side information" is not only useful in general, but that in many cases knowing it at only the encoder is as good as knowing it at both encoder and decoder, and knowing it at only the decoder is useless. Moreover, it is shown that the strategy of exploiting distortion side information at the encoder by describing it for the decoder is inefficient. Thus, distortion side information is a natural complement to side information about the source signal, as studied by Wyner and Ziv, which if available only at the decoder is often as good as knowing it at both encoder and decoder. When both types of side information are present, conditions are established under which encoder-only distortion side information and decoder-only signal side information are sufficient in the high-resolution limit, and the rate penalty for deviating from this configuration is characterized. Index Terms--Data compression, distributed source coding, quantization, sensor networks, Wyner-Ziv coding.

A large amount of biological data is semi-structured and stored in any one the following file formats such as flat, XML and relational files. These databases must be integrated with the structured data available in relational or object-oriented databases. The sequence matching process is difficult in such file format, because string comparison takes more computation cost and time. To reduce the memory storage size of amino acid sequence in protein database, a novel probability-based variable bit length encoding technique has been introduced. The number of mapping of triplet CODON for every amino acid evaluates the probability value. Then, a binary tree has been constructed to assign unique bits of binary codes to each amino acid. This derived unique bit pattern of amino acid replaces the existing fixed byte representation. The proof of reduced protein database space has been discussed and it is found to be reduced between 42.86 to 87.17%. To validate our method, we have collected few amino acid sequences of major organisms like Sheep, Lambda phage and etc from NCBI and represented them using proposed method. The comparison shows that of minimum and maximum reduction in storage space are 43.30% and 72.86% respectively. In future the biological data can further be reduced by applying lossless compression on this deduced data. Key words: Binary tree, protein sequence, amino acid, INTRODUCTION RNA sequences are composed of four nucleotides: adenine (A), uracil (U), guanine (G), and cytosine (C). Any of the three combinations of the nucleotide bases is called as triplets [...]

Fitness landscape analysis techniques are used to better understand the influence of genetic representations and associated variation operators when solving a combinatorial optimization problem. Five representations are investigated for the multidimensional knapsack problem. Common mutation operators, such as bit-flip mutation, are employed to generate fitness landscapes. Measures such as fitness distance correlation and autocorrelation are applied to examine the landscapes associated with the tested genetic encodings. Furthermore, additional experiments are made to observe the effects of adding heuristics and local optimization to the representations. Encodings with a strong heuristic bias are more efficient, and the addition of local optimization techniques further enhances their performance. Index Terms--Fitness landscape analysis, heuristic bias, local improvement methods, representation.

We prove a new outer bound on the rate--distortion region for the multiterminal source-coding problem. This bound subsumes the best outer bound in the literature and improves upon it strictly in some cases. The improved bound enables us to obtain a new, conclusive result for the binary erasure version of the "CEO problem." The bound recovers many of the converse results that have been established for special cases of the problem, including the recent one for the Gaussian two-encoder problem. Index Terms--CEO problem, erasure distortion, multiterminal source coding, outer bound, rate region, rate--distortion.

We determine the rate region of the quadratic Gaussian two-encoder source-coding problem. This rate region is achieved by a simple architecture that separates the analog and digital aspects of the compression. Furthermore, this architecture requires higher rates to send a Gaussian source than it does to send any other source with the same covariance. Our techniques can also be used to determine the sum-rate of some generalizations of this classical problem. Our approach involves coupling the problem to a quadratic Gaussian "CEO problem." Index Terms--CEO problem, Gaussian sources, multiterminal source coding, rate region, remote source, vector quantization, worst case source.

The improvement rate in microprocessor speed by far exceeds the improvement in DRAM memory. This increasing processor-memory performance gap is the primary obstacle to improved computer system performance. As a result, the size of main memory has increased gradually. To utilize main memory's resources effectively, data compression can be applied. Through compression, the data can be compressed by eliminating redundant elements. Thus, this study incorporates compression to main memory in order to fully utilize its resources and improve performance of data access. This project evaluates the performance of the compression algorithms in order to increase the performance of memory access. The compression algorithms are string matching based which are LZW and LZSS. Through simulation, the effectiveness and compressibility of the algorithms were compared. The performances of the algorithms were evaluated in term of compression time, decompression time and compressed size. The simulation result shows that LZSS is an efficient compression algorithm compared to LZW. Key words: LZSS, LZW, string matching, lossless compression, INTRODUCTION Data compression is a technique of encoding information using fewer bits than an unencoded representation would use through specific encoding or compression algorithm. All forms of data, which includes [...]

The application of matching pursuit (MP) in progressive coding of memoryless Gaussian sources is analyzed. The results have shown that matching pursuit can produce an embedded bitstream with comparable quality to existing quantizers.

The performance analysis of a method based on transmitting pseudo-random sequences for spatial encoding in synthetic transmit aperture ultrasound imaging is presented.

A high-speed VLSI design of an area-efficient JPEG2000 encoder is given. Recursive multilevel 2-D discrete wavelet transform (DWT) architecture with dual buffers is proposed to reduce the wavelet coefficients memory to 1/4 tile size, prerate allocation is used to reduce the compressed code memory to 3/4 tile size. A highly pipelined and parallelism implementation of line-based 1-level DWT is proposed using two line-buffers in 5/3 wavelet type and its input speed is up to 2 samples/cycle; code block based address mapping in access wavelet coefficients memory, concurrent state variables generation and multiple parallel and pipeline coding methods are used in the bit plane encoder (BPE) which encodes on average at 40.5M samples/s at 100 MHz with no memory used; the conditional two-symbol pipeline arithmetic encoder (AE) encodes at 1.3 symbols/cycle. Parallel units in BPE and buffer control between BPE and AE are optimally implemented with low cost without performance loss. Byte representation of rate-distortion slope used reaches a near optimal implementation of post-coding rate distortion in Tier2 with low cost. The compressed file generated by the encoder is fully compatible with ISO/IEC FCD15444-1[1]. The encoder is verified on field-programmable gate array platform with a direct interface to digital video input with tile size 256 x 256 and code block size 32 x 16. The resulting input sampling rate is up to 58 M samples/s when Tierl operates at 100 MHz. Difference of the peak signal-to-noise ratio of images compressed by our encoder and JasPer [2] is less than 0.2 dB when the compression ratio is greater than 1 bps. Equivalent NAND2 gates synthesized are 90.6 K and on-chip RAM size is 626.75 kb. Unlike other designs the proposed design of JPEG2000 encoder has high compression quality as well as high speed and area-efficiency. Index Terms--Arithmetic encoder, bit plane encoder (BPE), discrete wavelet transform (DWT), field programmable gate array (FPGA), JPEG2000 encoder, Tier2, VLSI.

We introduce the fixed-rate bit stuff (FRB) algorithm for efficiently encoding and decoding maximum-runlength-limited (MRL) sequences. Our approach is based on a simple, variable-rate technique called bit stuffing. Bit stuffing produces near-capacity achieving codes for a wide range of constraints, but encoding is variable-rate, which is unacceptable in most applications. In this work, we design near-capacity fixed-rate codes using a three-step procedure. The fixed-length input data block first undergoes iterative preprocessing, followed by variable-rate bit stuffing, and finally dummy-bit padding to a fixed output length. The iterative preprocessing is key to achieving high encoding rates. We discuss rate computation for the proposed FRB algorithm and show that the asymptotic (in input block length) encoding rate is close to the average rate of the variable-rate bit stuff code. Then, we proceed to explore the effect of decreasing/increasing the number of preprocessing iterations. Finally, we derive a lower bound on the encoding rate with finite-length input blocks and tabulate the parameters required to design FRB codes with rate close to 100/101 and 200/201. Index Terms--Bit stuffing, constrained coding, fixed-rate codes.

A new rate control scheme for H.264 video encoding with enhanced rate and distortion models is proposed in this work. Compared with existing H.264 rate control schemes, our scheme has offered several new features. First, the inter-dependency between rate-distortion optimization (RDO) and rate control in H.264 is resolved via quantization parameter estimation and update. Second, since the bits of the header information may occupy a larger portion of the total bit budget, which is especially true when being coded at low bit rates, a rate model for the header information is developed to estimate header bits more accurately. The number of header bits is modeled as a function of the number of nonzero motion vector (MV) elements and the number of MVs. Third, a new source rate model and a distortion model are proposed. For this purpose, coded 4 x 4 blocks are identified and the number of source bits and distortion are modeled as functions of the quantization stepsize and the complexity of coded 4 x 4 blocks. Finally, a R-D optimized bit allocation scheme among macroblocks (MBs) is proposed to improve picture quality. Built upon the above ideas, a rate control algorithm is developed for the H.264 baseline-profile encoder under the constant bit rate constraint. It is shown by experimental results that the new algorithm can control bit rates accurately with the R-D performance significantly better than that of the rate control algorithm implemented in the H.264 software encoder JM8.1a. Index Terms--H.264, optimal bit allocation, rate control, rate-distortion (R-D) optimization.

In this correspondence, we consider one-to-one encodings for a discrete memoryless source, which are "one-shot" encodings associating a distinct codeword with each source symbol. Such encodings could be employed when only a single source symbol rather than a sequence of source symbols needs to be transmitted. For example, such a situation can arise when the last message must be acknowledged before the next message can be transmitted. We consider two slightly different types of one-to-one encodings (depending on whether the empty codeword is used or not) and obtain lower and upper bounds on the expected length of optimal one-to-one codes. We first give an extension of a known tight lower bound on the expected length of optimal one-to-one codes for the case that the the size of the source alphabet is finite and partial information about the source symbol probabilities is available. As expected, our lower bound is no less than the previously known lower bound obtained without side information about the source symbol probabilities. We then consider the case that the source entropy is available and derive arbitrarily tight lower bounds on the expected length of optimal one-to-one codes. We also derive arbitrarily tight lower bounds for the case that the source entropy and the probability of the most likely source symbol are available. Finally, given that the probability of the most likely source symbol is available, we obtain an upper bound on the expected length of optimal one-to-one codes. Our upper bound is tighter than the best upper bound known in the literature. Index Terms--Nonprefix codes, one-to-one codes, source coding.

A fast feature-based intra/inter coding mode selection scheme for the H.264/AVC video coding standard is proposed in this paper. First, three features are extracted from a macroblock to form a feature space. Then, the feature space is partitioned into three regions, i.e., risk-free, risk-tolerable, and risk-intolerable regions, where the risk is calculated using the rate-distortion (RD) performance loss due to wrong mode decision as well as the probability distribution of inter/intra modes in the feature space obtained from an off-line training process. Depending on the region where the feature vector of a macroblock is located, we can apply mechanisms of different complexity for final mode decision. To calculate the likelihood function of the risk, both parametric and nonparametric density estimation schemes are developed to offer different rate-distortion-complexity tradeoffs. It is demonstrated by experimental results that the proposed algorithm can save approximately 20%-32% of the total encoding time of H.264 (JM7.3a) with little degradation in the rate-distortion performance. Index Terms--Bayes-risk minimization, coding mode prediction, density estimation, encoder complexity, H264/AVC, mode decision.

The length-restricted code-construction problem arises when using prefix codes for large messages and also for search-tree depth minimization. A problem instance comprises an ordered set of input probabilities which in this paper are assumed, without loss of generality, to be a set of unnormalized integer frequencies {[f.sub.1], [f.sub.2],..., [f.sub.n]}, and a maximum codeword length L bits. The package-merge algorithm of Larmore and Hirschberg constructs a minimum-redundancy length-restricted code in O(n L) time. Here we present an algorithm which computes a minimum-redundancy length-restricted code in O(( H - L + 1 )n) time, by starting with a minimum-redundancy (Huffman) code with a maximum codeword length of H, and then refining it to meet the length limit L. The new algorithm is suited to problems where H - L is small; and when H - L > L - [log n], the new algorithm outperforms all previous methods. Experimental results confirm the behavior of the new algorithm. Index Terms--Codes, encoding, Huffman codes, source coding.

We investigate the differences between allowable differential encoding strategies and their associated bit-error probability performances for quadrature phase-shift keying (QPSK) and offset QPSK modulations when the carrier demodulation reference signals are supplied by the optimum (motivated by maximum a posteriori estimation of carrier phase) carrier-tracking loop suitable for that modulation. In particular, we show that in the presence of carrier-synchronization phase ambiguity but an otherwise ideal loop, both the symbol and bit-error probabilities in the presence of differential encoding are identical for the two modulations. On the other hand, when in addition the phase error introduced by the loop's finite signal-to-noise ratio is taken into account, it is shown that the two differentially encoded modulations behave differently, and their performances are no longer equivalent. A similar statement has previously been demonstrated for the same modulations when the phase ambiguity was assumed to have been perfectly resolved by means other than differential encoding. Index Terms--Bit-error probability (BEP), carrier synchronization, differentially encoded offset QPSK (DE-OQPSK), differentially encoded quadrature phase-shift keying (DE-QPSK).

With the superior error correction capability, low-density parity-check (LDPC) codes have initiated wide scale interests in satellite communication, wireless communication, and storage fields. In the past, various structures of single code-rate LDPC decoders have been reported. However, to cover a wide range of service requirements and diverse interference conditions in wireless applications, LDPC decoders that can operate at both high and low code rates are desirable. In this paper, a 9-k code length multi-rate LDPC decoder architecture is presented and implemented on a Xilinx field-programmable gate array device. Using pin selection, three operating modes, namely, the irregular 1/2 code mode, the regular 5/8 code mode, and the regular 7/8 code mode, are supported. Furthermore, to suppress the error floor level, a characterization on the conditions for short cycles in a LDPC code matrix expanded from a small base matrix is presented, and a cycle elimination algorithm is developed to detect and break such short cycles. The effectiveness of the cycle elimination algorithm has been verified by both simulation and hardware measurements, which show that the error floor is suppressed to a much lower level without incurring any performance penalty. The implemented decoder is tested in an experimental LDPC orthogonal frequency division multiplexing system and achieves the superior measured performance of block error rate below [10.sup.-7] at signal-to-noise ratio of 1.8 dB. Index Terms--Block-error rate, channel encoding, cycle elimination, forward error correction (FEC), field-programmable gate array (FPGA), low-density parity-check (LDPC) codes, multi-rate, orthogonal frequency division multiplexing (OFDM), signal-to-noise ratio (SNR), VLSI.

A Slepian-Wolf coding scheme for compressing two uniform memoryless binary sources using a single channel code that can achieve arbitrary rate allocation among encoders was outlined in the work of Pradhan and Ramchandran. Inspired by this work, we address the problem of practical code design for general multiterminal lossless networks where multiple memoryless correlated binary sources are separately compressed and sent; each decoder receives a set of compressed sources and attempts to jointly reconstruct them. First, we propose a near-lossless practical code design for the Slepian-Wolf system with multiple sources. For two uniform sources, if the code approaches the capacity of the channel that models the correlation between the sources, then the system will approach the theoretical limit. Thus, the great advantage of this design method is its possibility to approach the theoretical limits with a single channel code for any rate allocation among the encoders. Based on Slepian-Wolf code constructions, we continue with providing practical designs for the general lossless multiterminal network which consists of an arbitrary number of encoders and decoders. Using irregular repeat-accumulate and turbo codes in our designs, we obtain the best results reported so far and almost reach the theoretical bounds. Index Terms--Data compression, distributed source coding, Slepian-Wolf coding, multiterminal source coding.

A new parameter set for designing permutors is introduced. it is called the set of higher order separations and can be considered as a generalization of the well-known symbol separation (spreading factor). The respective permutor is called a higher order permutor and we show how such a permutor can be constructed. For a second-order permutor in a serially concatenated convolutional encoding scheme we give a lower bound on the minimum distance of the resulting overall code. The integers that determine the sufficiently large separations, i.e., the smallest separations for which the distance properties can be guaranteed, are derived from the active distances of the convolutional component encoders. Additionally, a growth rate of the minimum distance like O ([([d.sup.o.sub.free]).sup. [??][rho]/2[??] + 1]) is proved for serially concatenated convolutional encoders with permutors having large separations of order [rho]. Index Terms--Interleaver design, minimum distance, permutor design, serially concatenated convolutional codes, turbo codes.

In this article, the authors propose to characterize sequence learning in terms of automatic versus nonautomatic processing and to apply this contrast independently to knowledge acquisition and retrieval. In several experiments of sequence learning, automaticity of both the acquisition and retrieval of the acquired knowledge was independently assessed. It was found that the sequence learning order can be demonstrated under all combinations of knowledge acquisition and retrieval. In particular, at least in the simple sequences the authors used, this applies in cases in which both the acquisition and the retrieval of knowledge are strictly automatic--that is, when neither is required for the task nor beneficial to deliberate behavior. The proposed framework has implications for the notion of sequence learning and the investigation of learning in general. Keywords: sequence learning, implicit learning, automaticity, mode of retrieval, mode of acquisition

The presentation of a subset of learned items as retrieval cues can have detrimental effects on recall of the remaining items. For 2 types of encoding conditions, the authors examined in 3 experiments whether such part-list cuing is a transient or a lasting phenomenon. Across the experiments, the detrimental effect of part-list cues was consistently found to be transient with a high degree of interitem associations and lasting with a low degree. These results indicate that the persistence of part-list cuing depends on encoding, thus challenging both strategy disruption and retrieval inhibition as general accounts of part-list cuing. A 2-mechanism account is provided according to which the 2 mechanisms mediate the effect in different encoding conditions. Keywords: episodic forgetting, part-list cuing, interitem associations, strategy disruption, retrieval inhibition

Quasi-cyclic (QC) low-density parity-check (LDPC) codes form an important subclass of LDPC codes. These codes have encoding advantage over other types of LDPC codes. This paper addresses the issue of efficient encoding of QC-LDPC codes. Two methods are presented to find the generator matrices of QC-LDPC codes in systematic-circulant (SC)form from their parity-check matrices, given in circulant form. Based on the SC form of the generator matrix of a QC-LDPC code, various types of encoding circuits using simple shift registers are devised. It is shown that the encoding complexity of a QC-LDPC code is linearly proportional to the number of parity bits of the code for serial encoding, and to the length of the code for high-speed parallel encoding. Index Terms--Array of circulants, quasi-cyclic (QC) low-density parity-check (LDPC) codes, systematic-circulant (SC) form.

Differential encoding is known to simplify receiver implementation because it by-passes channel estimation. However, over rapidly fading wireless channels, extra transceiver modules are necessary to enable differential transmission. Relying on a basis expansion model for time and frequency selective (doubly selective) channels, we derive such a generalized block-differential (BD) codec and prove that it achieves maximum Doppler and multipath diversity gains, while affording low-complexity maximum-likelihood decoding. We further show that existing BD systems over frequency-selective or time-selective channels follow as special cases of our novel system. Simulations using the widely accepted Jakes' model corroborate our theoretical analysis. Index Terms--Differential encoding, diversity, Doppler, doubly selective channels, multipath.

Given a type hierarchy, a subtyping test determines whether one type is a direct or indirect descendant of another type. Such tests are a frequent operation during the execution of object-oriented programs. The implementation challenge is in a space-efficient encoding of the type hierarchy that simultaneously permits efficient subtyping tests. We present a new scheme for encoding multiple-and single-inheritance hierarchies, which, in the standard benchmark hierarchies, reduces the footprint of all previously published schemes. Our scheme is called PQ-encoding (PQE) after PQ-trees, a data structure previously used in graph theory for finding the orderings that satisfy a collection of constraints. In particular, we show that in the traditional object layout model, the extra memory requirements for single-inheritance hierarchies is zero. In the PQE subtyping, tests are constant time, and use only two comparisons. The encoding creation time of PQE also compares favorably with previous results. It is less than 1 s on all standard benchmarks on a contemporary architecture, while the average time for processing a type is less than 1 ms. However, PQE is not an incremental algorithm. Other than PQ-trees, PQE employs several novel optimization techniques. These techniques are applicable also in improving the performance of other, previously published, encoding schemes. Categories and Subject Descriptors: D.1.5 [Programming Techniques]: Object-Oriented Programming; D.3.3 [Programming Languages]: Language Constructs and Features--Data types and structures; G.4 [Mathematical Software]: Algorithm design and analysis General Terms: Algorithms, Design, Measurement, Performance, Theory Additional Key Words and Phrases: Casting, encoding, hierarchy, inheritance, partially ordered sets, PQ, PQE, subtyping, type inclusion

The process in which the priority encoding transmission (PET) framework might be leveraged to exploit both unequal error protection and limited retransmission for RD-optimized delivery of streaming media is illustrated. PET framework allows for a decoupled optimization algorithm with only modest complexity.

The chaotic closed-loop system's performance, including that of the fiber transmission was evaluated numerically using the chaos shift keying and chaotic modulation approach. Acceptable system performance could be obtained for approximately 200 km at 2.4 Gbps.

The problematic real-work applications of low-density parity-check (LDPC) codes are discussed. A joint (3,k)-regular LDPC code and decoder/encoder design technique, to construct a class of (3,k)-regular LDPC codes, is presented.

Tailbiting codes encoded by feedback convolutional encoders are studied. A condition for when tailbiting will work is given and it is described how the encoder starting state can be obtained for feedback encoders in both controller and observer canonical forms. Finally, results from a search for systematic feedback encoders that encode tailbiting codes with good decoding bit error probabilities are presented. Index Terms--Convolutional codes, systematic feedback convolutional encoders, tailbiting trellis encoders.

The well-known uniform error property for signal constellations and codes is extended to encompass information bits. We introduce a class of binary labelings for signal constellations, called bit geometrically uniform (BGU) labelings, for which the uniform bit error property holds, i.e., the bit error probability does not depend on the transmitted signal. Strong connections between the symmetries of constellations and binary Hamming spaces are involved. For block-coded modulation (BCM) and trellis-coded modulation (TCM) Euclidean-space codes, BGU encoders are introduced and studied. The properties of BGU encoders prove quite useful for the analysis and design of codes aimed at minimizing the bit, rather than symbol, error probability. Applications to the analysis and the design of serially concatenated trellis codes are presented, together with a case study which realizes a spectral efficiency of 2 b/s/Hz. Index Terms--Coding, concatenated codes, constellations, encoding, labeling, trellis codes, uniform error property.

Encoders for convolutional codes with large free distances can be constructed by combining several less powerful convolutional encoders. This paper is devoted to constructions in which the constituent convolutional codes are woven together in a manner that resembles the structure of a fabric. The general construction is called twill and it is described together with two special cases, viz., woven convolutional encoders with outer warp and with inner warp. The woven convolutional encoders inherit many of their structural properties, such as minimality and catastrophicity, from their constituent encoders. For all three types of woven convolutional codes upper and lower bounds on their free distances as well as lower bounds on the active distances of their encoders are derived. Index Terms--Active distances, concatenated convolutional codes, free distance, minimal convolutional encoders, woven convolutional codes.

This paper presents sensorless position estimation using a conventional or 'symmetric' cage induction motor. The rotor position information is obtained by high-frequency injection and using the modulating effect of the rotor slots. This makes true sensorless position control possible. The deteriorating effect of saturation harmonics for operation at full flux and higher loads is suppressed by using a harmonic compensation scheme based on parameters obtained from an automated commissioning process. Experimental results are shown, demonstrating sensorless position estimation at full flux and high loads. Initial experimental results are presented for encoderless position control under full flux. Index Terms--Harmonic compensation, rotor slot harmonics, saturation, sensorless position control, symmetric induction machine, vector control.

The main purpose of this paper is to introduce genetic programming into civil engineering problem solving. This paper describes a genetic programming-based approach for simultaneous sizing, geometry, and topology optimization of structures. An encoding strategy is presented to map between the real structures and the genetic programming parse trees. Numerical results for two examples reveal that the proposed approach is capable of producing the topology and shape of the desired trusses and the sizing of all the structural components. Hence, this approach can potentially be a powerful search and optimization technique in civil engineering problem solving.