We investigate the problem of coded caching for nonuniform demands when the structured clique cover algorithm proposed by Maddah-Ali and Niesen for decentralized caching is used for delivery. We apply this algorithm to all user demands regardless of their request probabilities. This allows for coding among the files that have different request probabilities but makes the allocation of memory to different files challenging during the content placement phase. As our main contribution, we analytically characterize the optimal placement strategy that minimizes the expected delivery rate under a storage capacity constraint. It is shown that the optimal placement follows either a two or a three group strategy, where a set of less popular files are not cached at all and the files within each of the other sets are allocated identical amounts of storage as if they had the same request probabilities. We show that for a finite set of storage capacities, that we call the base-cases of the problem, the two group strategy is always optimal. For other storage capacities, optimal placement is achieved by memory sharing between certain base-cases and the resulting placement either follows a two or a three group strategy depending on the corresponding base-cases used. We derive a polynomial time algorithm that determines the base-cases of the problem given the number of caches and popularity distribution of files. Given the base-cases of the problem, the optimal memory allocation parameters for any storage capacity are derived analytically.

Coded caching is an effective technique to reduce the redundant traffic in wireless networks. The existing coded caching schemes require the splitting of files into a possibly large number of subfiles, i.e., they perform coded subfile caching. Keeping the files intact during the caching process would actually be appealing, broadly speaking because of its simpler implementation. However, little is known about the effectiveness of this coded file caching in reducing the data delivery rate. In this paper, we propose such a file caching scheme that uses a decentralized algorithm for content placement and either a greedy clique cover or an online matching algorithm for the delivery of missing data. We derive approximations to the expected delivery rates of both schemes using the differential equations method, and show them to be tight through concentration analysis and computer simulations. Our numerical results demonstrate that the proposed coded file caching is significantly more effective than uncoded caching in reducing the delivery rate. We, furthermore, show the additional improvement in the performance of the proposed scheme when its application is extended to subfile caching with a small number of subfiles.

A number of recent works have used a variety of combinatorial constructions to derive Tanner graphs for LDPC codes and some of these LDPC codes have been shown to perform well in terms of their probability of errors and error floors. Such graphs are bipartite and many of these constructions yield biregular graphs, where the degree of left vertices is a constant c + 1 and that of the right vertices is a constant d + 1. Such graphs are termed (c+1, d +1) biregular bipartite graphs. Two properties of interest in such work is the girth of the graph and the number of short cycles in the graph, cycles of length either the girth or slightly larger. Such numbers have been shown to be related to the error floor of the probability of error curve of the related LDPC code. Using known results of graph theory, it is shown how the girth and the number of cycles of length equal to the girth may be computed for these (c + 1, d + 1) biregular bipartite graphs knowing only the parameters c and d and the numbers of left and right vertices. While numerous algorithms to determine the number of short cycles in arbitrary graphs exist, the reduction of the problem from an algorithm to a computation for these biregular bipartite graphs is of interest.

The use of partial geometries to construct parity-check matrices for binary low-density parity-check (LDPC) codes has resulted in the design of successful codes with a probability of error on the AWGN channel close to the Shannon capacity at bit error rate down to $10^{-15}$ . Such considerations have motivated this further investigation. A new and simple construction of a type of partial geometries with a quasi-cyclic (QC) structure is given and their properties are investigated. Two new classes of this type of partial geometries, one based on prime fields and the other based on cyclic subgroups of prime orders of finite fields, are constructed. QC-LDPC codes with good error performances are constructed based on these two new classes of partial geometries. The trapping sets of the partial geometry codes were previously considered using the geometric aspects of the underlying structure to derive information on the size of allowable trapping sets. This topic is further considered here. Finally, there is a natural relationship between partial geometries and strongly regular graphs. The eigenvalues of the adjacency matrices of such graphs are well known, and it is of interest to determine if any of the Tanner graphs derived from the partial geometries are good expanders for certain parameter sets, since it can be argued that codes with good geometric and expansion properties might perform well on the AWGN channel under message-passing decoding.

Radio frequency identification (RFID) is a ubiquitous wireless technology which allows objects to be identified automatically. An RFID tag is a small electronic device with an antenna and has a unique identification (ID) number. RFID tags can be categorized into passive and active tags. For passive tags, a standard communication protocol known as EPC-global Generation-2, or briefly EPC Gen-2, is currently in use. RFID systems are prone to transmission collisions due to the shared nature of the wireless channel used by tags. The EPC Gen-2 standard recommends using dynamic framed slotted ALOHA technique to solve the collision issue and to read the tag IDs successfully. Recently, some researchers have suggested to replace the dynamic framed slotted ALOHA technique used in the standard EPC Gen-2 protocol with the code division multiple access (CDMA) technique to reduce the number of collisions and to improve the tag identification procedure. In this paper, the standard EPC Gen-2 protocol and the CDMA-based tag identification schemes are modeled as absorbing Markov chain systems. Using the proposed Markov chain systems, the analytical formulae for the average number of queries and the total number of transmitted bits needed to identify all tags in an RFID system are derived for both the EPC Gen-2 protocol and the CDMA-based tag identification schemes. In the next step, the performance of the EPC Gen-2 protocol is compared with the CDMA-based tag identification schemes and it is shown that the standard EPC Gen-2 protocol outperforms the CDMA-based tag identification schemes in terms of the number of transmitted bits and the average time required to identify all tags in the system.

Radio frequency identification (RFID) is a ubiquitous wireless technology which allows objects to be identified automatically. An RFID tag is a small electronic device with an antenna and has a unique identification number. RFID tags can be categorized into passive and active tags. For passive tags, there exists a standard communication protocol called EPC-global Generation-2, or briefly EPC Gen-2 [1]. In this paper, we investigate the EPC Gen-2 protocol and model it using an absorbing Markov chain. We formulate the proposed model and calculate the expected number of queries required to identify all tags in the system. Extensive simulations validate and confirm the accuracy of our proposed analytical model. Without this model, one has to run simulations and average the results to obtain the expected number of required queries for any given number of tags in the system. Using the mathematical formulations provided, there is no need to rely on simulations for studying the behavior of the EPC Gen-2 protocol and we are able to calculate the number of required queries directly. Our proposed analytical model is also useful in studying and comparing other RFID protocols, and in deploying better protocols for RFID systems.

There are two main approaches, static and dynamic, to broadcast algorithms in wireless ad hoc networks. In the static approach, local algorithms determine the status (forwarding/nonforwarding) of each node proactively based on local topology information and a globally known priority function. In this paper, we first show that local broadcast algorithms based on the static approach cannot achieve a good approximation factor to the optimum solution (an NP-hard problem). However, we show that a constant approximation factor is achievable if (relative) position information is available. In the dynamic approach, local algorithms determine the status of each node "on-the-fly” based on local topology information and broadcast state information. Using the dynamic approach, it was recently shown that local broadcast algorithms can achieve a constant approximation factor to the optimum solution when (approximate) position information is available. However, using position information can simplify the problem. Also, in some applications it may not be practical to have position information. Therefore, we wish to know whether local broadcast algorithms based on the dynamic approach can achieve a constant approximation factor without using position information. We answer this question in the positive-we design a local broadcast algorithm in which the status of each node is decided "on-the-fly” and prove that the algorithm can achieve both full delivery and a constant approximation to the optimum solution.

Radio frequency identification (RFID) is a ubiquitous wireless technology which allows objects to be identified automatically. An RFID tag is a small electronic device with an antenna and has a unique serial number. For some RFID applications and in the ALOHA-based anticollision algorithms, the number of tags in the system needs to be estimated. In Trans. Autom. Sci. Eng., vol 6, no. 1, pp. 9-15, Jan. 2009, Chen, a probabilistic method for tag estimation in ALOHA-based RFID systems was proposed, based on the maximum a posteriori probability. Although this approach is novel and useful, it has a mathematical error in modeling the problem. In this short paper, we address this problem and provide the correct probabilistic model for the ALOHA-based RFID systems. Some consequences of correcting the error in Trans. Autom. Sci. Eng., vol 6, no. 1, pp. 9-15, Jan. 2009, Chen, are discussed and the model is validated via simulation. Using the correct model, the performance of the ALOHA-based anticollision algorithm can be improved.

Radio-frequency identification (RFID) is a ubiquitous wireless technology which allows objects to be identified automatically. An RFID tag is a small electronic device with an antenna and has a unique serial number. Using RFID tags can simplify many applications and provide many benefits. Meanwhile, the privacy of the customers should be taken into account. A potential threat for the privacy of a user is that of anonymous readers obtaining information about the tags in the system. The use of a blocker tag has been proposed as a solution to avoid unwanted tag interrogations. A blocker tag can simulate all or a portion of tag IDs in the system. This prevents the malicious readers from identifying the tags and obtaining information from the system. Although this solution is simple to implement and has a low cost, it may add another threat to the RFID system if used as a malicious tool to attack the system. A malicious blocker tag can deteriorate the performance of an RFID system by simulating fake tag IDs. In this paper, we study the use of blocker tags for malicious attacks that can prevent nearby legitimate readers from correctly receiving the reply messages from the tags. The blocker attack is a medium access control (MAC)-layer denial of service (DoS) threat and we propose a lower-layer solution for this attack. We mathematically model the blocker attack for RFID systems which operate based on the binary tree walking or ALOHA singulation techniques. Using the developed analytical framework, we propose a probabilistic blocker tag detection (P-BTD) algorithm to detect the presence of an attacker in the RFID system. The P-BTD algorithm can detect the existence of a blocker tag using the information extracted from the interrogations performed by the reader. Simulation results show that our proposed algorithm has a better performance than the threshold-based detection algorithm in terms of the number of required interrogations.

Cooperative diversity systems have received significant attention recently as a distributed means of exploiting the inherent spatial diversity of wireless networks. In this paper, we consider a cooperative diversity system consisting of a source, a destination, and multiple single-hop amplify-and-forward relays, and provide a mathematical framework for the asymptotic analysis of this system in generic noise and interference for high signal-to-noise ratios. Assuming independent Rayleigh fading for all links in the network and orthogonal relay-destination channels, we obtain simple and elegant closed-form expressions for the asymptotic symbol and bit error rates valid for arbitrary linear modulation formats, arbitrary numbers of relays, and arbitrary types of noise and interference with finite moments including co-channel interference, ultra-wideband interference, impulsive ε-mixture noise, generalized Gaussian noise, and Gaussian noise. Furthermore, we exploit the derived analytical error rate expressions to develop power allocation, relay selection, and relay placement schemes that are asymptotically optimal in environments with generic noise and interference. In general, the power allocation problem results in a geometric program which can be solved efficiently numerically. For the special case of only one relay, we provide a closed-form result for the optimal power allocation. Simulation results confirm our analysis and illustrate that, in non-Gaussian noise, the proposed power allocation, relay selection, and relay placement schemes lead to large performance gains compared to their conventional counterparts optimized for Gaussian noise.

Radio frequency identification (RFID) is a ubiquitous wireless technology which allows objects to be identified automatically. An RFID tag is a small electronic device with an antenna and has a unique serial number. In this paper, we study the use of blocker tags by malicious attackers which can cause the nearby readers not being able to successfully receive the reply messages from the RFID tags. We mathematically model the blocker tag attack problem using information extracted from the interrogations performed by the reader. Using this analytical framework, we propose a probabilistic blocker tag detection (PBTD) algorithm to detect the presence of an attacker in the system. The probability of false alarm for the P-BTD algorithm is determined via simulation. Simulation results show that our proposed algorithm has a better performance than the threshold-based detection algorithm in terms of using a shorter time (i.e., fewer interrogations) to detect the presence of blocker tags.

Algebraic curves over a finite field have played a central role in both coding theory and cryptography over the past three decades. In coding theory the use of algebraic curves led to the discovery of asymptotically good codes whose parameters lie above the Varshamov-Gilbert bound in certain cases while in cryptography the use of elliptic curves led to public key cryptosystems that are more efficient, in some sense, for a given level of security than integer factorization based ones. It would seem natural that the use of higher dimensional varieties might lead to even better results for both applications. Such has not so far been the case in any dramatic way. The purpose of this talk is to review the situation on the use of Abelian varieties in these two areas.

Quasi-cyclic LDPC codes are the most promising class of structured LDPC codes due to their ease of implementation and excellent performance over noisy channels when decoded with message-passing algorithms as extensive simulation studies have shown. In this paper, an approach for constructing quasi-cyclic LDPC codes based on Latin squares over finite fields is presented. By analyzing the parity-check matrices of these codes, combinatorial expressions for their ranks and dimensions are derived. Experimental results show that, with iterative decoding algorithms, the constructed codes perform very well over the AWGN and the binary erasure channels.

Establishing a secure communication link in a wireless sensor network is a challenging task due to resource limitation and wireless nature of transmission. A symmetric key distribution is a practical and efficient solution which has been studied extensively [4][5][6][7][9][11]. A secure communication link is established between sensors that hold common keys, which are discovered by each node broadcasting the key identifiers of its key ring. We make modifications to existing schemes to reduce communication overhead during the key discovery phase. This is achieved without weakening network connectivity or system resiliency against key compromise. We also introduce families of new deterministic key distribution schemes with low-communication overhead.

The design of erasure correcting codes and their decoding algorithms is now at the point where capacity achieving codes are available with decoding algorithms that have complexity that is linear in the number of information symbols. One aspect of these codes is that the overhead (number of coded symbols beyond the number of information symbols required to achieve decoding completion with high probability) is linear in k. This work considers a new class of random codes which have the following advantages: (i) the overhead is constant (in the range of 5 to 10) (ii) the probability of completing decoding for such an overhead is essentially one (iii) the codes are effective for a number of information symbols as low as a few tens. The price for these properties is that the decoding complexity is greater, on the order of k3/2. However, for the lower values of k where these codes are of particular interest, this increase in complexity might be outweighed by other significant advantages. The parity check matrices of these codes are chosen at random as windowed matrices i.e. for each column an initial starting position of a window of length w is chosen and the succeeding w positions are chosen at random by zero or one. It can be shown that it is necessary that w = O(k1/2) for the probabilistic matrix rank properties to behave as a non-windowed random matrix. The sufficiency of the condition has so far been established by extensive simulation, although other arguments strongly support this conclusion

A new modulation method for linear space-time codes is proposed based on using constellations of different sizes for different symbols. It is shown that the proposed method significantly reduces the complexity of the sphere decoding algorithm. The complexity reduction is more pronounced in high-rate codes, where each code matrix carries a large number of symbols. We also show that the choice of constellation size provides a tradeoff between performance and complexity. Using this, some guidelines for choosing constellation size are presented. As one introduces more constellation disparity in the code, the complexity is further reduced, while the performance loss grows. Typically, a complexity reduction of one to two orders of magnitude can be achieved at the expense of about 3 dB coding gain. We suggest a simple modification in our design to reduce this loss to about 2 dB.

A new modulation method for linear space-time codes is proposed based on using constellations of different sizes for different symbols. It is shown that the proposed method significantly reduces the complexity of the sphere decoding algorithm. Typically, a complexity reduction of one to two orders of magnitude can be achieved at the expense of about 3 dB coding gain. With a simple modification in our design, we reduce this loss to about 2 dB.

We consider the problem of sending messages into the future, commonly known as timed release cryptography. Existing schemes for this task either solve the relative time problem with uncontrollable, coarse-grained release time (time-lock puzzle approach) or do not provide anonymity to senders and/or receivers and are not scalable (server-based approach). Using a bilinear pairing on any Gap Diffie-Hellman group, we solve this problem by giving scalable, server-passive and user-anonymous timed release public-key encryption schemes allowing precise absolute release time specifications. Unlike the existing server-based schemes, the trusted time server in our scheme is completely passive - no interaction between it and the sender or receiver is needed; it is even not aware of the existence of a user, thus assuring the privacy of a message and the anonymity of both its sender and receiver. Besides, our scheme also has a number of desirable properties including a single form of update for all users, self-authenticated time-bound key updates, and key insulation, making it a scalable and appealing solution. It could also be easily generalized to a more general policy lock mechanism

A new family of fully diverse high rate space time codes is proposed based on number theoretic results and a property of a certain family of matrices. The code is linearly encodable and can be decoded using the sphere decoding algorithm.

A new family of fully diverse high rate space time codes is proposed based on number theoretic results and a property of a certain family of matrices. The code is linearly encodable and can be decoded using the sphere decoding algorithm.

The discrete logarithm problem (DLP) on elliptic curves over finite field has been extensively studied as a cryptographic building block. The DLP recently was considered over other algebraic structures such as Jacobian of hyperelliptic curves, superelliptic curves, and Abelian varieties in general. The main objective is to determine a large subgroup of prime order for which no index calculus attack is known. We investigate the Jacobian of two towers of function fields that have good asymptotic property as another potential source of Abelian groups for the DLP. This paper is the first step in this direction and compute the size of the Jacobian via the zeta function.

The notion of product block codes, whose generator matrix is the tensor product of the constituent generator matrices, is well established. Typically, they have good performance and a decoding algorithm with complexity on the order of the complexity of the decoding algorithms of the constituent codes. There has been much recent attention on the construction of bipartite graphs for low density parity check codes whose parity check matrices are the incidence matrices of right versus left vertices of the graph. The relation of the properties of the incidence matrix to code performance is difficult to establish precisely, although some guidelines are available. Two types of incidence matrix constructions are given here that show promise. In the first instance, a combinatorial construction is given, and, secondly, two types of graph products are considered for their application to LDPC codes.

This article presents simple and highly regular architectures for finite field multipliers using a redundant representation. The basic idea is to embed a finite field into a cyclotomic ring which is based on the elegant multiplicative structure of a cyclic group. One important feature of our architectures is that they provide area-time trade-offs which enable us to implement the multipliers in a partial-parallel/hybrid fashion. This hybrid architecture has great significance in its VLSI implementation in very large fields. The squaring operation using the redundant representation is simply a permutation of the coordinates. It is shown that, when there is an optimal normal basis, the proposed bit-serial and hybrid multiplier architectures have very low space complexity. Constant multiplication is also considered and is shown to have an advantage in using the redundant representation.

A new surviving paths unit (SPU) is described wherein the decision bits produced in the add-compare-select unit (ACSU) of a parallel architecture for the Viterbi algorithm are prepared for efficient storage in a single compact random access memory (RAM). A significant reduction in the size of the RAM is achieved by pre-processing the data in an especially designed unit. The new SPU never requires a memory bandwidth more than the least possible bandwidth imposed by the throughput of the ACSU. A novel interface unit, hereafter referred to as the ACS interface unit (ACSIU), resolves surviving paths down to a pre-determined depth on the trellis diagram of a finite state Markov chain, and breaks the decision bits into a sequence of successive vectors, each of the same size as the word-size of the RAM. At any trace-back step, a subset of the previous content of the trace-back register is used to generate the address for the current output of the RAM. A disjoint subset of the current content of the trace-back register is used to select a pre-determined number of bits from the output of the RAM. The selected bits are used to update the content of the trace-back register. The trace-back register after a sufficient number of trace-back steps, contains the estimated bits.

Trellis complexity of root lattices A/sub n/, D/sub n/, E/sub n/, and their duals is investigated. Using N, the number of distinct paths in a trellis, as the measure of trellis complexity for lattices, a trellis is called minimal if it minimizes N. It is proved that the previously discovered trellis diagrams of some of the above lattices (D/sub n/, n odd, A/sub n/, 4/spl les/n/spl les/9, A/sub 4/*, A/sub 5/*, A/sub 6/*, A/sub 9/*, E/sub 6/, E/sub 6/*, and E/sub 7/*) are minimal. We also obtain minimal trellises for A/sub 7/* and A/sub 8/*. It is known that the complexity N of any trellis of an n-dimensional lattice with coding gain /spl gamma/ satisfies N/spl ges//spl gamma//sup n/2/. Here, this lower bound is improved for many of the root lattices and their duals. For A/sub n/ and A/sub n/* lattices, we also propose simple constructions for low-complexity trellises in an arbitrary dimension n, and derive tight upper bounds on the complexity of the constructed trellises. In some dimensions, the constructed trellises are minimal, while for some other values of n they have lower complexity than previously known trellises.

New structures of bit-parallel weakly dual basis (WDB) multipliers over the binary ground field are proposed. An upper bound on the size complexity of bit-parallel multiplier using an arbitrary generating polynomial is given. When the generating polynomial is an irreducible trinomial x/sup m/+x/sup k/+1, 1/spl les/k/spl les/[m/2], the structure of the proposed bit-parallel multiplier requires only m/sup 2/ two-input AND gates and at most m/sup 2/-1 XOR gates. The time delay is no greater than T/sub A/+([log/sub 2/ m]+2)T/sub x/, where T/sub A/ and T/sub X/ are the time delays of an AND gate and an XOR gate, respectively.

We present an analytical method for evaluating the performance of noninterleaved concatenated codes over channels modeled as a nonfrequency selective correlated Rician fading channel with a known power spectral density. The main idea is to model the communication system from the modulator input to the demodulator output as a finite state channel (FSC) model, and apply powerful enumeration techniques to such a discrete channel in order to gain useful information on the system performance. The concatenated scheme makes use of two codes; Reed-Solomon codes are employed for the outer code, and binary block codes are used as the inner code. Next, the method is extended to study the effect on the performance when an interleaving with finite depth is incorporated into the communication system. A comparison between symbol and bit interleaving is made. Finally, we study the potential gain produced when channel information is passed on to the outer decoder in the form of an erasure symbol. In all cases, analytical expressions for the probability of the number of error symbols produced by the FSC model were obtained in terms of a coefficient in a formal power series. This is an interesting alternative approach with respect to computer simulations.

This paper presents results on trellis complexity and low-complexity trellis diagrams of lattices. We establish constructive upper bounds on the trellis complexity of lattices. These bounds both improve and generalize the similar results of Tarokh and Vardy (see ibid., vol.43, p.1294-1300, 1997). We also construct trellis diagrams with minimum number of paths for some important lattices. Such trellises are called minimal. The constructed trellises, which are novel in many cases, can be employed to efficiently decode the lattices via the Viterbi algorithm. In particular, a general structure for minimal trellis diagrams of D/sub n/ lattices is obtained. This structure corresponds to a new code formula for D/sub n/. Moreover, we develop some important duality results which are used in both deriving the upper bounds, and finding the minimal trellises. All the discussions are based on a universal approach to the construction and analysis of trellis diagrams of lattices using their bases.

The theory of error-correcting codes derived from curves in an algebraic geometry was initiated by the work of Goppa as generalizations of Bose-Chaudhuri-Hocquenghem (BCH), Reed-Solomon (RS), and Goppa codes. The development of the theory has received intense consideration since that time and the purpose of the paper is to review this work. Elements of the theory of algebraic curves, at a level sufficient to understand the code constructions and decoding algorithms, are introduced. Code constructions from particular classes of curves, including the Klein quartic, elliptic, and hyperelliptic curves, and Hermitian curves, are presented. Decoding algorithms for these classes of codes, and others, are considered. The construction of classes of asymptotically good codes using modular curves is also discussed.

The binary input N-user adder channel models a communication media accessed simultaneously by N users. Each user transmits a binary codeword of length n chosen from its codebook and the channel output consists of a componentwise arithmetic sum of the binary digits. Van Tilborg (1978) gave an upper bound on the size of a uniquely decodable code for the two-user case. His work is generalized here to the N-user case. The results give interesting information on the existence and properties of such codes.

The analysis of a communication system operating over finite state channel (FSC) models includes the calculation of the probability of subsets of error sequences. In this paper we first present an analytical method for evaluating the performance of non-interleaved Reed-Solomon (RS) codes over channels modeled as FSC models with an arbitrary number of states. The main idea is to express the probability of the number of error symbols produced by the channel in terms of a coefficient in a formal power series. Next, the method is extended to study the effect on the performance when an interleaving with finite depth is incorporated into the communication system. The general expressions are specialized for a Gilbert-Elliott channel (GEC) with known model parameters, and numerical results are derived.

The determination of normal bases for finite fields, particularly over the finite field F/sub 2/, is of importance in applications such as coding and cryptography. This correspondence gives an explicit normal basis for a finite field F/sub 2/(p-1)p/sup m/ over F/sub 2/, when 2 is a primitive element module p/sup 2/. In the case when p=3, an explicit dual basis is also obtained.

An inequality relating the trellis complexity of lattices to their dimension and Hermite parameter is established. Using this inequality, a conjecture of Forney is proved indicating that the trellis complexity of the densest lattice packings in $\mathbb{R}^n $ grows exponentially as a function of their coding gain.

The paper investigates a technique to reduce the computational complexity of fractal image compression on gray-scale images. The technique uses a clustering process on image domain blocks with the clusters formed with the use of k-d trees and the fast pairwise nearest neighbor algorithm of Equitz (1984). Results indicate the method is effective for smaller domain block sizes and generally shows improvement in terms of picture peak signal-to-noise ratio (SNR) over the quadrant variance classification method.

The best possible tradeoff between the coding gain and trellis complexity for lattices is studied. Three trellis complexity functions are defined for lattices as a measure of minimum trellis decoding complexity per dimension required for achieving a coding gain /spl gamma/. The properties of these functions are studied from an analytic perspective. It is also shown that the trellis decoding complexity per dimension is lower-bounded by an explicit power of /spl gamma/.

For pt.I see ibid., vol. 42, no.6, p.1796-1802, 1996. Every rational lattice has a finite trellis diagram which can be employed for maximum-likelihood decoding over the additive white Gaussian noise channel via the Viterbi algorithm. For an arbitrary rational lattice L with gain /spl gamma/, the average number of states (respectively, branches) in any given trellis diagram of L is bounded below by a function of /spl gamma/. It is proved that this function grows exponentially in /spl gamma/. In the reverse direction, it is proved that given /spl isin/>0, for arbitrarily large values of /spl gamma/, there exist lattices of gain /spl gamma/ with an average number of branches and states less than exp(/spl gamma//sup (1+/spl isin//)). Trellis diagrams of block codes obtained from truncated convolutional codes are employed to show that, inside the trellis model, the problem of decoding lattices is not much harder than exponential.

The problem of decoding cyclic error correcting codes is one of solving a constrained polynomial congruence, often achieved

One of the proposed techniques for the third generation of mobile communications is code division multiple access (CDMA). Some attributes of CDMA which are important to indoor systems include desirable anti-multipath properties, the lack of a need for frequency management or assignment, coexistence with other systems and suitability for micro-cell and in-building systems. The anti-multipath feature turns out to be a key issue for indoor systems and derives from the property that a signal with path delay greater than one chip interval is treated much like an interfering user. The number of users that share the same spectrum, and still maintain an acceptable performance, is determined by the interference generated by the set of remaining users and leads to soft degradation as the number of users increases. This work describes and analyzes a model for the discrete-input continuous-output Gaussian multiple-access channel, that uses spread spectrum techniques. The notion of sum capacity is used to characterize the system performance. Bounds on the sum capacity of this essentially binary input, continuous output channel, where the variance of the output noise is dependent on the number of users present, are obtained. The users are noncooperative in that no common codebook or synchronization is assumed. A novel feature of the work is the use of the modeling of the activity of the user community as a birth-death process. An information theoretic approach is used and the sum capacity is then considered in light of the various regimes to determine the effect of this modeling.>

The present paper is interested in a family of normal bases, considered by Sidel’nikov [Math. USSR-Sb., 61 (1988), pp. 485–494], with the property that all the elements in a basis can be obtained from one element by repeatedly applying to it a linear fractional function of the form $\varphi ( x ) = ( ax + b )/( cx + d ),a,b,c,d \in F_q $. Sidel’nikov proved that the products for such a basis $\{ \alpha _i \}$ are of the form $\alpha _i \alpha _j = e_{i - j} \alpha _i + e_{j - i} \alpha _j + \gamma ,i = j$, where $e_k ,\gamma \in F_q $. It is shown that every such basis can be formed by the roots of an irreducible factor of $F( x ) = cx^{q + 1} + dx^q - ax - b$. The following are constructed: (a) a normal basis of $F_{q^n } $ over $F_q $ with complexity at most $3n - 2$ for each divisor n of $q - 1$ and for $n = p$, where p is the characteristic of $F_q$; (b) a self-dual normal basis of $F_{q^n } $ over $F_q $ for $n = p$ and for each odd divisor n of $q - 1$ or $q + 1$. When $n = p$, the self-dual normal basis constructed of $F_{q^p } $ over $F_q$ also has complexity at most $3p - 2$. In all cases, the irreducible polynomials and the multiplication tables are given explicitly.

The applications of multivariate Edgeworth series and higher-order statistics to the discrete-time detection of a known constant signal in multivariate non-Gaussian noise are considered. A technique to derive suboptimum detectors from the Neyman-Pearson optimum and locally optimum detectors is described. A numerical algorithm based on knowledge of the noise cumulants is presented in order to analyze the finite-sample size performance of the suboptimum detectors. As an example, the performance of the detectors as compared with the linear detector in multivariate Gaussian-Gaussian mixture noise is presented via receiver operating characteristic curves. Numerical results indicate that the suboptimum detectors, when exploiting knowledge of the dependence structure of the noise, can have very good performance with respect to the linear detector.>

The complete weight enumerator of a code enumerates the code words by the number of symbols of each kind contained in each code word. As for the ordinary weight enumerators, the complete weight enumerators for linear codes satisfy a duality theorem. These weight enumerators are studied here for certain realizations of Reed–Solomon codes of dimensions two, three, and four over a field of characteristic two. Some applications of these results are considered.

Bit serial multiplication schemes for hardware implementation of arithmetic in a finite field of characteristic two are considered. In addition, certain aspects of polynomial bases in finite fields are investigated.

A procedure based on the generalized Lloyd algorithm approach using a sequence of independent noise samples to design M-region generalized quantizers for signal detection is presented. Included in this case are the conventional M-interval quantizer detectors. The quantizer parameters for S.A. Kassam's (1985) four-region generalized quantizer detector are computed using various sample sizes for the known sequence of independent noise samples. Two families of densities which cover a wide spectrum of possible nonGaussian densities are considered: the generalized Gaussian densities and the Johnson S/sub u/ family of densities. The performance of the quantizer detector is compared to that of the locally optimum detector, and the results are presented as the asymptotic relative efficiencies of the respective detectors. The case when the noise density is not known before analysis is considered, and the detection performance is examined using an estimate of the density. A mean-squared-error distortion criterion is used in the proposed algorithm to obtain quantizers that yield maximum efficacy. It is shown through numerical examples that the design procedure is simple, fast, and applicable to a wide range of nonGaussian distributions.>

For pt.1 see ibid., vol.COM-35, p.1329-41 (1987). A performance evaluation is presented for selective diversity with feedback for frequency-hopping M-ary frequency-shift-keyed systems operating over Rayleigh faded channels in the presence of partial-band noise and partial-band tone jamming. The behavior of uncoded and coded systems is studied. For coded systems, the performance is evaluated for hard-decision receivers without channel state information and soft-decision receivers with perfect jammer state information. The results demonstrate that the performance of uncoded FH/MFSK with selective diversity is unacceptable. However, this diversity technique can offer definite improvements for coded FH/MFSK systems. Specifically, the effectiveness of selective diversity signaling depends on the provision of a feedback channel between the transmitter and receiver to provide the transmitter with the fading gains of the independently faded channels. To obtain an improvement from the selective diversity signaling scheme described here, there must be multiple independently faded channels between the transmitter and receiver. If not, the performance of the selective diversity signaling scheme will be identical to the performance of FH/MFSK without diversity.>

A novel type of diversity signaling for an M-ary frequency-shift keyed modulation format involving the transmission of multiple tones on each diversity branch is considered. The properties of such a system are investigated, and its performance in the presence of tone jamming is analyzed. It is shown that significant gains can be realized with such a technique. The performance in the presence of worst-case partial band noise is briefly considered and shown to be worse than, though comparable to, that of the single-tone case.>

Time-invariant trellis codes for stationary, ergodic, discrete-time sources are designed by unconstrained, nonlinear optimization of the performance in a simulated source encoding with the Viterbi algorithm. A nonderivative conjugate directions algorithm and a conjugate gradient algorithm with restarts are applied to design low-constraint-length, unit-rate, binary codes for the memoryless Gaussian source. The latter algorithm is also used to design codes for the memoryless Laplacian source and a third-order autoregressive model for speech. Good codes are tabulated and compared to other known results on a performance versus complexity basis. Those for the Gaussian source are tested in a joint (tandem) trellis-coding system with known convolutional channel codes.>

The authors present a feedback rate control technique for FH/BFSK (frequency-hop/binary phase-shift keying) signaling over a jammed flat-flat fading channel. An algorithm is developed for tracking the channel fade level, dynamically adjusting the transmitted data rate, and mitigating the effects of partial-band noise jamming. Simulation studies indicate that improvements of about 2 dB can be obtained in the coded performance with the proposed adaptive rate system, when compared to a nonadaptive system operating over the same communication medium with identical power and bandwidth resources.>

The design of time-invariant trellis codes for stationary ergodic discrete-time sources is cast as an unconstrained, nonlinear optimization problem, where the objective function and its derivatives are evaluated by simulation. Using classical real analysis and the ergodic theorem, convergence of the sample encoding distortion and its partial derivatives (with respect to the code quantization levels) to their ensemble average values is investigated. It is found that in the common code design situation, the expected per-symbol distortion and its first derivatives are available and piecewise continuous, but second-derivative information is unreliable. This indicates that efficient optimization should be performed using a nonderivative or first-derivative method that does not compute approximate second derivatives to determine search directions.>

This paper gives an evaluation of the performance of adaptive signaling techniques for jammed fading channels. These techniques perform remarkably well for fading channels with AWGN. The performance of both uncoded and coded systems is examined in the presence of jamming. Adaptive signaling schemes are shown to offer little improvement for uncoded antijam systems. However, for coded antijam systems, they provide improvements in the performance and, in some cases, simplify the receiver implementation.

The performance of diversity and/or coding is evaluated for FH/MFSK signaling over Rayleigh fading channels in the presence of jamming. The effects of partial-band tone and partial-band noise jamming on uncoded and coded systems are considered. The results indicate that FH/MFSK signaling with diversity provides satisfactory performance for jammed fading channels. For coded FH/MFSK signaling over fading channels, noise jamming may be more effective than tone jamming. The amount of improvement resulting from the use of diversity in conjunction with coding depends upon many factors, including the nature of the channel, the degree of channel state information available at the decoder, the type of decoding, and the modulation alphabet size.

Upper and lower bounds for the probability in the tails of a binomial distribution are investigated. New bounds are obtained which are computationally simple and, in the case of the lower bound, significantly better than previously known bounds.

The results obtained by Cohen, Heller, and Viterbi (1971) for an orthogonal coding technique for a particular asynchronous multiple access channel are generalized to nonorthogonal coding to investigate the gains that may be realized. It is shown that in the range of bit error probabilities of interest, for a given channel bandwidth, modest gains can be realized using nonorthogonal signaling.

A construction technique is given for complex sequences, each component of magnitude unity, with Iow autocorrelation and cross correlation. The construction is based on an application of the Carlitz-Uchiyama theorem to cyclic equivalence classes of maximal period of Reed-Solomon codes over GF(p),pbeing an odd prime.

The recently introduced notion of a miracle octad generator can be viewed as a means of identifying a codeword of weight eight of the extended binary Golay code, given five of its nonzero positions. It is shown that this fact can be used as the basis of a new decoding algorithm for this code which decodes all the information positions simultaneously. The performance of this algorithm, as well as methods for its implementation, are considered.

The relationship between certain techniques for the storage of information in a computer and a cell occupancy problem is shown Specifically, consider n cells or buckets each capable of holding k balls.Balls are distributed into the cells randomly A ball sent to the/th cell is placed either into the ]th cell or into the first cell to the right of the/th cell which has k -1 or fewer balls The placement of balls into cells requires comparisons to determine the status of the cells The distribution and expected value of the number of such comparisons and in particular the behavior as n --~ ~ are determined

The notion of supplementary difference sets is used to construct codes which are one-step majority logic decodable using orthogonal parity checks. An infinite family of single and double error-correcting codes is constructed. Strong evidence is given which suggests that there exists an analogous infinite family of triple error-correcting codes.

If the vectors of some constant weight in the dual of a binary linear code support a(\nu,b,r,k,\lambda)balanced incomplete block design (BIBD), then it is possible to correct[(r + 2 - 1)/2\lambda]errors with one-step majority logic decoding. This bound is generalized to the case when the vectors of certain constant weight in the dual code support at-design. With the aid of this bound, the one-step majority logic decoding of the first, second, and third order Reed-Muller codes is examined.

Properties of configuration matrices of group codes for the Gaussian channel are considered. It is shown that the configuration matrix of a code generated by a real-irreducible representation is a scalar multiple of an idempotent matrix. A spectral resolution of the configuration matrix of a code generated by an arbitrary real representation is given, and all of its eigenvalues are determined. A relatively simple criterion to determine when the group code spans the space is derived.

A class of nonlinear codes for discrete channels is defined with the use of permutation groups. Several examples of such codes are given; their parameters are similar to those for Reed-Solomon codes in some cases. Decoding algorithms are discussed.

The problem of labeling the vertices of an undirected, connected graph with binaryn-tuple addresses is considered. These addresses are to have the property that if two vertices are a distancekapart in the graph then the Hamming distance between the corresponding addresses must bekdwheredis a positive integer which is constant for the graph. Not all graphs may be so addressed. A weak characterization of addressable graphs in terms of the eigenvalues of a certain matrix associated with the graph is given. It is shown that any addressable bipartite graph may always be addressed withd = 1. For nonbipartite addressable graphs,dmust be even, and it is shown that there exist graphs requiring an arbitrarily largedfor addressing. An addressing algorithm is given which is guaranteed to address any addressable graph.

In a variety of practical problems involving random processes, it is necessary to have statistical information on their level-crossing properties. This paper presents a survey of known results on certain aspects of this problem and provides a basis for further study in the area. The goal has been to give a broad view of the problems considered in the literature and a brief indication of the techniques used in their solution. Much material of a more or less historical nature has been included since, to the authors' knowledge, no other survey of this nature exists.

For a class of piecewise linear correlation functions, it is shown that optimal linear mean-square filtering is achieved with a finite number of samples of the process for any finite observation interval. The class of correlation functions is defined by a particular property of the points at which they change slope. Conditions are discussed under which an arbitrary piecewise linear function is a correlation function. An example demonstrating various aspects of the theory is given, and applications of the theory are considered.

This paper considers a class of stochastic processes, called {\em spherically invariant},which have the property that all mean-square estimation problems on them have linear solutions. It is shown that their multivariate characteristic functions are univariate functions of a quadratic form. The corresponding densities are easily found by means of the Hankel transform. Relations between spherical invariance and normality are discussed. Properties relating to the linear estimation problem are given.