In this work we consider the impact of eBook reader location surveillance on freedom of association. We begin with a survey of Amazon's Kindle patents, indicating the types of surveillance that may be used in the Kindle. We then consider the impact of location surveillance on freedom of association through a study of the US and European law. Particular emphasis is placed on the chilling effect of loss of anonymity in a group setting.

No abstract available.

While the intersection of blockchains and the Internet of Things (IoT) have received considerable research interest lately, Nakamoto-style blockchains possess a number of qualities that make them poorly suited for many IoT scenarios. Specifically, they require high network connectivity and are power-intensive. This is a drawback in IoT environments where battery-constrained nodes form an unreliable ad hoc network such as in digital agriculture. In this paper we present Vegvisir, a partition-tolerant blockchain for use in power-constrained IoT environments with limited network connectivity. It is a permissioned, directed acyclic graph (DAG)-structured blockchain that can be used to create a shared, tamperproof data repository that keeps track of data provenance. We discuss the use cases, architecture, and challenges of such a blockchain.

A clear understanding of the nature of cryptography would have a positive impact on the law of forced decryption in particular, and other cases involving cryptography in general. Computer scientists and engineers should also be concerned about the broader issues raised in these cases. Prosecutors have repeatedly asserted that cryptography is the refuge of miscreants and scoundrels, and that upstanding citizens have no need for such technology. This is demonstrably false. Strong cryptography is a powerful defense against hackers and misplaced or stolen laptops. Given that the hackers may be supported by rogue states, the best possible cryptography should be available to prevent identity theft and the other evils pursuant to the loss of personal data. Cryptography also has a strong role to play in civil liberties with regard to protecting press sources and personal financial data against unwarranted surveillance. The mere presence of encrypted information is not a sign of foul play, and computer scientists and engineers are well placed to make the argument.

The "cloud paradigm" can provide a wealth of sophisticated emergency communication services that are gamechangers in emergency response, but its current implementation is not suitable to the challenging environments in which these responses often take place. The networking infrastructure may be all but unavailable, and access to centralized datacenters may be impossible.

Location sharing applications (LSA) have proliferated in recent years. Current research principally focuses on egocentric privacy issues and design but has historically not explored the impact of surveillance on location sharing behavior. In this paper, we examine homophily in friendship and surveillance networks for 65 foursquare users. Our results indicate that location surveillance networks are strongly homophilous along the lines of race and gender while friendship networks are weakly homophilous on income. Qualitatively, an analysis of comments and interviews provides support for a discourse around location surveillance, which is mainly social, collaborative, positive and participatory. We relate these findings with prior literature on surveillance, self-presentation and homophily and situate this study in existing HCI/CSCW scholarship.

Prior research shows that people often engage in deception when sharing location. Privacy concerns, social surveillance and impression management are the primary drivers of these types of behaviors. One methodological question that arises in this research context is the problem of reliable measurement to study predictors of deceptive location disclosure from usage data. In this note, we propose a simple experience sampling method (ESM) approach that is useful for studying this phenomenon. We describe our ESM deployment and report the results of a long term, quantitative study of 204 foursquare users over 1 year. Results indicate that physical distance, tie strength and order of visibility on the foursquare feed are significant predictors (with moderate to high effect sizes) of deceptive location disclosure. We connect these findings to the rich tradition of location disclosure behavior research in ubiquitous computing.

This paper begins with a brief overview of how digital rights management (DRM) technologies are being used to limit consumer rights. Next we show how this code is combined with a legal component, including the use of contractual agreements, to further narrow user rights. Providing a summary of the legal history, we build up to the current legal environment surrounding DRM in the United States, showing the need for DRM policy and coding changes to better balance the interests of copyright holders and the public.

This paper proposes a new approach to channel estimation and channel feedback, based on continuous time-domain parameter (CTDP) extraction. The improvement in channel feedback overhead and channel estimation accuracy are shown to range from an order of magnitude to more than two orders of magnitude depending on channel conditions. Due to its extremely low channel feedback overhead, CTDP extraction enables two key features in LTE-advanced: coordinated multipoint transmission (CoMP) and multi-user MIMO (MU-MIMO), both of which aim to increase the network capacity multi-fold. CTDP extraction is also computationally efficient.

This paper presents a novel time-domain parameter (TDP) extraction scheme for channel estimation and feedback in the LTE-advanced systems. The TDP extraction improves the channel estimation accuracy by an order of magnitude over the interpolation-based methods, has extremely low complexity compared to MMSE approaches, and is very close to or even outperforms the Bayesian MMSE lower bound. The mobile device feeds back the extracted TDPs instead of the complex amplitudes of the channel at reference signal (RS) subcarriers, reducing the feed-back overhead by an order of magnitude and making possible for implementation of CoMP, a key feature in the LTE-advanced.

This paper analyzes layer 2 contention resolution strategies for wireless networks with multipacket reception by using noncooperative game theory. Necessary and sufficient conditions are obtained for a strategy profile to be a Nash equilibrium. Applications of the derived equilibrium conditions to predict selfish behavior and the resulting equilibrium performance are illustrated in specific communication scenarios along with various design insights. The collective equilibrium behavior of wireless networks with large user populations is also studied, and a Poisson-Bernoulli type approximation is obtained for the total number of packet arrivals. Finally, random access control with imperfect information structure is considered, the form of equilibrium strategies as well as uniqueness and existence results for general wireless channel models are obtained, and the best-response learning dynamics achieving an equilibrium are illustrated in specific instances.

Key distributions based on cover-free families have been recently proposed for secure rekeying in group communication systems after multiple simultaneous user ejections. Existing literature has not quantified how difficult this rekeying operation might be. This study provides upper bounds on the number messages necessary to rekey a key distribution based on symmetric combinatorial designs after one or two simultaneous user ejections. Connections are made to results from finite geometry to show that these bounds are tight for certain key distributions. It is shown that in general determining the minimal number of messages necessary to rekey a group communication system based on a cover-free family is NP-hard.

Privacy has become a critical topic in the engineering of networked systems. Electronic surveillance, both covert and overt, has a negative impact on both the individual and society, and the public's perception of engineered systems that forsake the privacy issue is increasingly negative. Engineers and computer scientists thus have a moral obligation to avoid design choices that are unnecessarily privacy invasive. To fully illustrate this point, we provide an overview of the philosophical, legal, moral, and epistemological literature on the subject of privacy and related implications of its invasion. We then introduce a series of privacy-aware design principles that lead to less invasive information technologies. We develop a smart grid/demand response case study to illustrate the impact of the proposed design rules that protect individual privacy and promote understanding of ethical issues underlying the need for privacy for individuals and society.

We consider the connectivity of finite two-dimensional wireless networks consisting of a finite number of randomly deployed nodes and sinks at fixed locations. First, we focus on the likelihood that each node is able to convey a message to at least one of the few sinks. We then consider the potential for partial network connectivity under the same configuration. We derive approximate solutions using geometric random graphs theory and evaluate their tightness through stochastic simulation of network realizations. We show the benefits of using more than one sink and provide an approximate formula for the connectivity of such networks. We show how partial connectivity with sinks improves some network metrics at the cost of having a small number of isolated nodes, a situation that would be acceptable, for example, in a large network of redundant sensors.

We consider a wireless network and address the problem of detecting and localizing malicious nodes in a single source/destination configuration. The malicious nodes are found through the use of Reed-Muller codes. Reed-Muller codes are used to select the necessary paths between source and destination. Based on the graph connectivity matrix, these necessary paths, and the probability that a node is malicious, our algorithm determines all the paths in the network. The minimum distance of the code determines how many malicious nodes can be localized. We develop an algorithm for the case when a set of paths is not realizable in the network and compare the performance of the algorithm with other techniques.

One of the most important topological characteristics of a network is its connectivity. This work analyzes the connectivity of one-dimensional wireless networks considering finite number of randomly deployed nodes with random communication ranges. In particular, it focuses on the probability of being able to convey a message from the source to the sink given certain number of nodes. The method to address the problem is by mapping it to the problem of covering a circle with arcs of random sizes. This paper provides an analytical solution when the communication ranges of the nodes are distributed uniformly over the field of interest. In addition, and of practical relevance, it shows how the random communication radii model can represent certain kind of randomness in the communication channel. Specifically there is a comparison between our model and the log-normal shadowing statistical model. Stochastic simulations validate the derived formula as well as its approximation to the standard shadowing model. In agreement to previous results for wireless networks, this work verifies that the requirements on the number of nodes to have a connected network may be relaxed when the nodes have random communication radii.

This paper addresses the following question: how reliable is it to use the unbounded path-loss model G(d) = d-α, where α is the path-loss exponent, to model the decay of transmitted signal power in wireless networks? G(d) is a good approximation for the path-loss in wireless communications for large values of d but is not valid for small values of d due to the singularity at 0. This model is often used along with a random uniform node distribution, even though in a group of uniformly distributed nodes some may be arbitrarily close to one another. The unbounded path-loss model is compared to a more realistic bounded path-loss model, and it is shown that the effect of the singularity on the total network interference level is significant and cannot be disregarded when nodes are uniformly distributed. A phase transition phenomenon occurring in the interference behavior is analyzed in detail. Several performance metrics are also examined by using the computed interference distributions. In particular, the effects of the singularity at 0 on bit error rate, packet success probability and wireless channel capacity are analyzed.

Connectivity is a basic quality of a network since it is required to obtain useful information out of the network. Research literature has mainly focused on the connectivity of wireless networks having a single connected network. However, due to diverse factors, it is feasible that a wireless network will have multiple base stations or sinks, i.e. it will have infrastructure. In this paper we analyze the connectivity of wireless networks with infrastructure and provide formulas to calculate the probability of having a connected network considering finite number of node platforms. With infrastructure the requirements for having a connected network may be relaxed since there can be more than one single-connected component of a network. Using combinatorics arguments we analyze the connectedness of a one- dimensional network over a line segment as a function of the available infrastructure-base stations and wireless nodes. This paper contains definitions for connected subnetworks that form a connected communication network; it also presents a one-dimensional network model and provides probability formulas for network connectivity for any given base stations arbitrary locations and the number of nodes. Through simulation we show the large increase in the probability of having a connected network when comparing a deployment with two base stations versus one with just one base station. This is of strong relevance when designing a wireless network.

This paper analyzes the asymptotic behavior of a multiple-access network comprising a large number of selfish transmitters competing for access to a common wireless communication channel, and having different utility functions for determining their strategies. A necessary and sufficient condition is given for the total number of packet arrivals from selfish transmitters to converge in distribution. The asymptotic packet arrival distribution at Nash equilibrium is shown to be a mixture of a Poisson distribution and finitely many Bernoulli distributions.

The 26 papers in this special issue focus on game theory in communication systems. The papers are grouped in four clusters according to their topics: (1) Physical layer models in wireless communications, (2) higher layer and cross-layer issues in wireless communications, (3) wire-line communication networks, and (4) specific topics including peer-to-peer networking, network coding, and network security.

A new technique based on first passage processes is presented as a means for calculating the detection time of an event by wireless mobile sensors located in Rd, d = 1,2 and 3. Our proposed method is valid for any type of mobility model, and is amenable to a variety of extensions. We consider heterogenous networks in which sensor platforms have different mobility patterns. The second extension considers unreliable sensors with randomly distributed operational lifetimes. The second generalization is of paramount importance if the network is deployed in a hostile environment. Our main results are illustrated for random linear motion and Brownian motion. An approach for applying our theorems when sensors move according to a time- homogenous Markov process is also considered.

Many of the routing protocols that have been designed for wireless ad-hoc networks focus on energy-efficiency and guaranteeing high throughput in a non-adversarial setting. However, given that ad-hoc and sensor networks are deployed and left unattended for long periods of time, it is crucial to design secure routing protocols for these networks. Over the past few years, attacks on the routing protocols have been studied and a number of secure routing protocols have been designed for wireless sensor networks. However, there has not been a comprehensive study of how these protocols compare in terms of achieving security goals and maintaining high throughput. In this paper, we focus on the problem of analyzing the inherent security of routing protocols with respect to two categories: multi-path and single-path routing. Within each category, we focus on deterministic vs. probabilistic mechanisms for setting up the routes. We consider the scenario in which an adversary has subverted a subset of the nodes, and as a result, the paths going through these nodes are compromised. We present our findings through simulation results.

Sleep strategies can be used in dense, redundant wireless sensor networks to increase network lifetime, but this comes at the expense of increased network management complexity. In this paper we consider the problem of queue stability in multi-hop networks with sleeping sensors. We derive stability constraints on a variety of sleep strategies as a function of network loading, channel noise, and data aggregation. We then compare and evaluate the performance of stable routing and scheduling policies over a set of relay nodes with and without queue length information. Through our analysis, we provide precise guidelines for the optimal design and operation of reliable sensor networks employing sleep strategies for a wide range of traffic patterns and applications.

This paper analyzes the behavior of selfish transmitters when they contend for the access of a noise impaired wireless channel with and without capture effect. We first focus on nodes with single packet detection capability contending for the access of a noisy wireless channel. We identify the effect of noise on selfish nodes' transmission probabilities. We show the existence of a critical threshold c*, which only depends on the noise distribution, such that if the cost of a packet failure is greater than c*, then backing-off is in transmitters' best-interest regardless of strategies of others. Otherwise, they may transmit, or back-off, or randomize among these two actions depending on their opponents' strategies. We finally turn our attention to channels with capture effect where it is possible to receive up to k packets simultaneously. We analyze the impact of such a capture effect on transmission probabilities of selfish nodes.

In this correspondence, we show that solutions to the multiple description coding problem and the broadcast channel coding problem share a common encoding procedure: successive source encoding. We use this connection as the basis for establishing connections between the achievable multiple description rate region and Marton's region for broadcast channels. Specifically, we show that Marton's encoding scheme can be viewed as a multiple description coding procedure. We also explore the dual problem, namely, the relationship between successive channel decoding in multiple access communication and distributed source coding. By illuminating these connections to multiple description, we hope to motivate a solution to what remains a mostly unsolved problem

In this paper we consider a wireless sensor network consisting of a single sink node at the center of a field of randomly distributed sensors. An anchor-free node localization algorithm is proposed in which the sink node imparts radial location information through the phased-array transmission of a series of beacons. The individual sensors use knowledge of received beacons and information from nearest neighbors to identify the sub-sectors in which they reside. This location information can then be used as the basis for an emergent routing algorithm. We present the localization algorithm, deduce the partition error analytically, and then provide simulation results. The results indicate that the localization performance improves with node density, and is robust against RSS measurement noise

We give a rigorous mathematical analysis of a game-theoretic MAC protocol for wireless networks. We begin with a wireless communication network in which n selfish nodes (agents), which might have different perceived utilities, contend for access on a common wireless communication channel. We first formulate this distributed multiple access problem in terms of a one-shot random access game, and characterize the Nash equilibria of the game. We then look at the asymptotic properties of the system as n rarr infin. When all nodes are identical, the best possible bounds on the rate of convergence of the asymptotic packet arrivals and the channel throughput are given. The analysis of the asymptotic packet arrivals in the heterogeneous case concludes the paper

A multihop ad hoc network with mobile elements is considered. A model is created and analytic expressions derived to characterize the statistics for link lifetime, new link interarrival time, link breakage interarrival time, and link change interarrival time. Applications of these expressions to protocol design are discussed. As an example application, the link model is used to find an optimal balance between reactive and proactive routing strategies. It is shown that, when control traffic generated through proactive route updating is matched to link lifetimes, control traffic is significantly reduced while the goodput and delay benefits of the proactive approach are retained

We consider the use of distributed source and network coding in networks of redundant, unreliable sensors. A design algorithm is described for distributed joint source and network coding that creates an optimal balance between compression efficiency and network robustness.

This article considers the problem of distributing sensors to observe a random field while meeting a series of energy and coverage constraints. In the network under consideration, N identical sensors are to be distributed, with each sensor sending data to a single fusion center at a fixed rate Δ R . The problem of sensor allocation to the coverage area is reduced to the problem of allocating sensors to cells by first partitioning the coverage field into cells, and then assuming that sensors in the same cells make the same observations. It is shown that the resulting sensor allocation problem is equivalent to a discrete form of the rate allocation problem, a well-known problem in the field of information theory. General guidelines for solving this problem are provided.

As the capacity and communication ability of mobile ad hoc and sensor networks are dependent on the set of communication links of the nodes, the design of any protocol for such networks should take into account the link dynamics. In this work, we investigate the behavior of the communication links of a node in a random mobility environment. Analytical expressions characterizing various properties related to the creation, lifetime and expiration of links are presented. The derived link properties can be used to design efficient algorithms for routing and medium access, or to analyze the performance of existing network protocols. A number of applications of the derived properties, such as the selection of a stable set of routes, route cache lifetime optimization, design of efficient proactive updating strategies and analysis of route lifetime are discussed.

In this paper, we study the optimal way of distributing sensors in a random field to minimize the estimation distortion. We show that this problem is equivalent to certain problems in optimal sampling design and multiterminal source coding. In our model, we partition the field into cells within which the observations are assumed to be the same. A number of identical sensors that can report the observed data to the fusion center at communication rate ¢R are to be allocated to cells so that the distortion achieved at the fusion center is minimized. We find optimal solutions for the Gaussian, binary and simplified Gaussian vector cases.

In this work, we develop an analytical framework to investigate the behavior of the communication links of a node in a random mobility environment. Analytical expressions characterizing various properties related to the formation, lifetime and expiration of links are derived. The derived framework can be used to design efficient algorithms for medium access, routing and transport control, or to analyze and optimize the performance of existing network protocols. A number of applications of the characteristics investigated, such as selection of stable routes, route cache lifetime optimization, providing Quality-of-Service (QoS) data communication and analysis of route lifetime are discussed. In particular, we focus on designing an efficient updating strategy for proactive routing protocols based on the derived statistics. Using simulations, we show that the proposed strategy can lead to significant performance improvements in terms of reduction in routing overhead, while maintaining high data packet delivery ratio and acceptable latency.

We consider a distributed sensor network in which several observations are communicated to the fusion center using limited transmission rate. The observation must be separately encoded so that the target can be estimated with minimum average distortion. We address the problem from an information theoretic perspective and establish the inner and outer bound of the admissible rate-distortion region. We derive an upper bound on the sum-rate distortion function and its corresponding rate allocation schemes by exploiting the contra-polymatroid structure of the achievable rate region. The quadratic Gaussian case is analyzed in detail and the optimal rate allocation schemes in the achievable rate region are characterized. We show that our upper bound on the sum-rate distortion function is tight for the quadratic Gaussian CEO problem in the case of same signal-to-noise ratios at the sensors.

A biologically inspired algorithm is presented to route messages in mobile wireless ad-hoc networks. The principles of swarm intelligence are used to define a probabilistic algorithm for which routing through paths of maximum throughput is an emergent property. This adaptive algorithm, dubbed termite, uses stigmergy to reduce the amount of control traffic needed to maintain a high data goodput. Stigmergy is a process by which information is indirectly communicated between individuals through their environment The termite environment is the contents of all routing tables. The movement of packets is influenced at each node, and communicating nodes observe this influence to update their own tables. Strong routing robustness is achieved through the use of multiple paths; each packet is routed randomly and independently.

Wireless sensor networks consisting of large numbers of inexpensive energy-constrained nodes are an area of emerging networking research. Routing algorithms in these networks are required to provide tolerance to temporary or lasting faults in individual devices. The conventional methodology is to set radio transmit powers to the minimum levels required for connectivity and use multipath routing to provide robustness. We show in this paper through an analytical example and detailed simulation results that using a single path routing scheme with higher transmit power can also be an energy-efficient solution for robustness to node failures.

Aloha is perhaps the simplest and most-studied medium access control protocol in existence. Only in the recent past, however, have researchers begun to study the performance of Aloha in the presence of selfish users. In this paper, we present a game-theoretic model of multipacket slotted Aloha with perfect information. We show that this model must have an equilibrium and we characterize this equilibrium. Using the tools of stochastic processes, we then establish the equilibrium stability region for some well-known channel models.

There are many contexts in distributed wireless networks where there is a critical threshold, corresponding to a minimum amount of the communication effort or power expenditure by individual nodes, above which a desirable global property exists with high probability. When this individual node effort is below the threshold the desired global property exists with a low probability. This "phase transition" is typically seen to become sharper as the number of nodes in the network increases. We discuss some examples of properties that exhibit such critical behavior: node reachability with probabilistic flooding, ad-hoc network connectivity, and sensor network coordination. We discuss the connections between these phenomena and the phase transitions that have been shown to arise in random graphs. We argue that a good understanding of these phase transition phenomena can provide useful design principles for engineering distributed wireless networks.

Game theory is a set of tools developed to model interactions between agents with conflicting interests, and is thus well-suited to address some problems in communications systems. We present some of the basic concepts of game theory and show why it is an appropriate tool for analyzing some communication problems and providing insights into how communication systems should be designed. We then provided a detailed example in which game theory is applied to the power control problem in a CDMA-like system.

We present some results regarding the paging cost gains and the cost-delay tradeoff that can be achieved by using sequential paging to locate mobile users in cellular networks. We describe tight bounds on the average paging cost and the paging delay and quantify the intuition that greater gains are achieved when the mobile user's location probabilities are concentrated in a small portion of the location area. We also examine the impact of errors in the location estimates on the paging cost.

Past studies of Aloha have emphasized system-wide goals such as achieving maximum throughput or minimum delay. We use game theory to analyze Aloha from the perspective of a selfish user. we construct an Aloha game and examine the optimal behavior of individual users. We show that the Aloha game has an equilibrium and that an Aloha system in which the users are selfish will be stable provided the attempt rate is sufficiently low. We then compare the performance of a selfish Aloha system with the performance of a centrally controlled slotted Aloha system. With some system parameters performance is near the optimum performance obtained by a centrally-controlled system. By utilizing a selfish-user assumption, it is possible to build systems which are robust and scalable.

The basic channel allocation problem (CAP) is known to be NP-hard. In this paper, splitting algorithms are proposed that significantly decrease computational load for centralized CAP algorithms by segmenting a problem, sequentially solving the smaller individual problems and then combining the solutions. This method is shown to have comparable performance with the non-splitting scheme for the same CAP algorithm. Experimental results using the random walk algorithm are presented.

A robust image transmission system incorporating perceptually-based coding and error protection is proposed for wireless channels. The perceptually-based image coder consists of a wavelet transformation, uniform quantization, and variable-length entropy encoding. The coded data is placed in a spatially scalable stream divided into segments of varying perceptual importance and tolerance to transmission errors. A novel unequal error protection system is designed using turbo codes for the wireless channel, neural networks to predict decoder error and calculate erasures, and outer turbo-code concatenation of Reed-Solomon codes at different rates. A model of error tolerance is developed to minimize the added redundancy required to meet the desired throughput performance and visual quality level. The proposed system provides excellent reliability allowing the transmission of high visual quality images at a small additional redundancy and low signal-to-noise ratio (4.5 dB).

It is shown that a neural network can be trained to observe the cross entropy of the outputs of component decoders in a turbo error control system and to accurately predict the presence of errors in the decoded data. The neural network can be used as a trigger for retransmission requests at either the beginning or the conclusion of the decoding process, providing improved reliability and throughput performance at a lower average decoding complexity than turbo decoding with cyclic redundancy check error detection.

An improved two-stage trellis decoder for Reed-Solomon (RS) codes is presented. This decoder uses reliability information as a basis for reordering the symbols in the received word. The coset trellis for the resulting code has the same structure and complexity as the standard two-stage trellis decoder, but an efficient means can now be implemented for the selection of the sub-trellis that contains the best path prior to decoding. Simulation results for the RS(7, 3) code are presented for AWGN and Rayleigh fading channels.

An iterative trellis search technique is described for the maximum-likelihood (ML) soft decision decoding of block codes. The proposed technique derives its motivation from the fact that a given block code may be a subcode for a parent code whose associated trellis has substantially fewer edges. Through the use of list-Viterbi (1967) decoding and an iterative algorithm, the proposed technique allows for the use of a trellis for the parent code in the ML decoding of the desired subcode. Complexity and performance analyses, as well as details of potential implementations, indicate a substantial reduction in decoding complexity for linear block codes of practical length while achieving ML or near-ML soft decision performance.

A methodology is presented for the design and development of efficient trellis-based soft decision decoders for extended Hamming and BCH codes. A new metric for noncoherent discriminator detection is proposed that substantially improves the performance of trellis-based decoders over additive white Gaussian noise (AWGN) channels. Minimal edge trellises are then presented for the class of extended Hamming codes and the (32, 21) extended BCH code. The latter is in extensive use in narrow-band wireless data systems. An automatic request (ARQ) protocol is described that allows the soft decision decoders to outperform their hard decision counterparts in both reliability and throughput.

An overview of the many practical applications of channel coding theory in the past 50 years is presented. The following application areas are included: deep space communication, satellite communication, data transmission, data storage, mobile communication, file transfer, and digital audio/video transmission. Examples, both historical and current, are given that typify the different approaches used in each application area. Although no attempt is made to be comprehensive in the coverage, the examples chosen clearly illustrate the richness, variety, and importance of error-control coding methods in modern digital applications.

The concatenation of an equalizer and a Viterbi decoder is a powerful means for improving the performance of mobile radio. The best system performance is obtained when the Viterbi algorithm is used with soft decisions. The soft output equalizer enables the use of soft decision Viterbi decoding. This paper proposes new soft output adaptive equalization techniques based on the SOVA and the modified-MAP algorithm for /spl pi//4-DQPSK mobile radio over multipath fading channels. Simulation results were obtained by using a modified version of the common functional blocks which were used previously by Hamied and Stuber (1996). A complexity analysis is also presented.

Sigma-trees (/spl sigma/-trees) are a class of geometric structures that include lattices as a constrained special case. These structures allow for signal sets, in spaces of arbitrary dimension, that are more spherical in shape than signal sets based on lattices. In this correspondence, it is shown that /spl sigma/-trees can be used in the construction of non-lattice trellis-coded modulation schemes (TCM) schemes. A low-complexity /spl sigma/-tree encoder is presented for multidimensional TCM codes. An optimal TCM decoder that uses the efficient sequential search property of /spl sigma/-trees is then described. Simulation results based on one- and two-dimensional examples are used to show that the performance of /spl sigma/-tree-based codes is comparable to that provided by conventional lattice-based codes.

The Viterbi algorithm is a maximum likelihood means for decoding convolutional codes and has thus played an important role in applications ranging from satellite communications to cellular telephony. In the past, Viterbi decoders have usually been implemented using digital circuits. The speed of these digital decoders is directly related to the amount of parallelism in the design. As the constraint length of the code increases, parallelism becomes problematic due to the complexity of the decoder. In this paper an artificial neural network (ANN) Viterbi decoder is presented. The ANN decoder is significantly faster than comparable digital-only designs due to its fully parallel architecture. The fully parallel structure is obtained by implementing most of the Viterbi algorithm using analog neurons as opposed to digital circuits. Several modifications to the ANN decoder are considered, including an analog/digital hybrid design that results in an extremely fast and efficient decoder. The ANN decoder requires one-sixth the number of transistors required by the digital decoder. The connection weights of the ANN decoder are either +1 or -1, so weight considerations in the implementation are eliminated. This, together with the design's modularity and local connectivity, makes the ANN Viterbi decoder a natural fit for VLSI implementation. Simulation results are provided to show that the performance of the ANN decoder matches that of an ideal Viterbi decoder.

In order to fully utilize the SDD (soft-decision decoding) capacity of the outer codes in a concatenated system, reliability information on the inner decoder outputs (called soft outputs) needs to be provided to the outer decoder. This paper shows that a modified MAP algorithm can be effectively and accurately used to generate such information. In the course of the presentation, a metric based on the reliability information is proposed for the outer decoder. This metric has the Euclidean metric on AWGN channels as its special case, which leads to the concept of generalized SDD (GSDD). Several practical concerns regarding the proposed soft-output decoder are addressed through theoretical analysis and simulation: the effect of finite decoding depth, computational complexity, range overflow, and scaling. Comparisons to previous work on soft-output decoders are made.

Previously (1994) the authors have analyzed the steady state performance of a random access code combining CDMA system. In this paper, the analysis is extended to the dynamic performance. We follow an approach similar to that used by Raychaudhuri (1981). The system is represented as a discrete-time Markov chain with the state being the number of backlogged terminals. At the start of a given time slot, each backlogged user k is characterized by P/sub k/(L) (the probability that user k transmits successfully a data packet formed by the combination of L previously transmitted copies). Unlike Raychaudhuri's system where the error rate on the channel is viewed by all transmitting users as the same constant during each time slot, P/sub k/(L) varies from one user to another. Its value is substantially increased through the code combining operation (increases with L). As a result, the number of retransmissions is minimized. The throughput and time-delay performance are significantly improved. We show through numerical analysis that the code combining system performs better than the conventional one. The effect of code combining on the stability is also investigated.

A trellis-coded, type-I hybrid-ARQ protocol using CRC codes as the error-detecting mechanism is described and analyzed. Bounds on both the reliability and throughput performance of the resulting error-control scheme are derived for AWGN channels and slowly fading Rician channels. Examples are included to illustrate the achievable gain of the proposed system relative to ordinary FEC trellis-coded systems. For slowly fading Rician channels, hybrid-ARQ protocols based on ordinary trellis-coded modulation and multiple trellis-coded modulation are also compared. All analytical results are supported by data from a series of simulations.>

Trellis coded modulation is widely used for digital transmission over fading channels. Classical diversity techniques are also frequently employed to combat fading. Two different combining strategies are compared. One scheme is based on an interleaved code combining technique. The alternative scheme is based on averaged diversity combining. The well known transfer function bounding technique for trellis codes is used to obtain expressions for the bit error rate performance of the two trellis coded diversity receivers over a slowly fading Rayleigh channel. The analysis of interleaved code combining is a straightforward modification of the analysis for multiple trellis coded modulation. The analysis of averaged diversity combining is accommodated through a more involved, novel modification of the branch labeling of the error state diagram.

Type-I hybrid-ARQ protocols can be used to construct powerful adaptive rate algorithms through the use of packet combining techniques. In this paper several packet combining schemes are presented for use in conjunction with the Viterbi decoder over stationary and time-varying channels. The first technique presented is an averaged diversity combiner, which is shown to be identical in performance to an interleaved code combiner over an AWGN channel. The averaged diversity combiner is then generalized to make use of packet weights based on either ideal channel state information or weights derived from side information generated by the Viterbi decoder. It is shown that the weighted diversity combiner using decoder side information performs almost as well as the system using ideal channel state information. All of the packet combining schemes discussed in this paper provide improved throughput and reliability performance relative to that provided by the standard type-I hybrid-ARQ or EEC systems. This performance improvement is obtained at the expense of negligible to moderate modifications to the transmitter and receiver. Performance bounds are derived for each of the combining schemes and their tightness verified through simulation results.>

Presents an adaptive error control technique based on the use of type-I hybrid-ARQ protocols. The communication channel is assumed to be slowly varying and is modeled using a finite state Markov chain. The system counts the number of retransmission requests during an observation interval called a frame and, together with knowledge of the error control strategy in use and a set of thresholds, estimates the state of the channel. The coding strategy which maximizes throughput while maintaining a minimum required level of reliability is chosen for use in the next frame. Examples are provided showing system design and performance using families of Reed-Solomon codes.>

Improved performance of error control techniques over slowly varying channels can be realized by a system which adapts itself to changes in the channel conditions. Such action requires a method for monitoring the channel state and detecting a change in it. The frequency of retransmission requests in ARQ and type-I hybrid-ARQ error control strategies provides a natural source of channel state information. The proposed scheme incorporates the retransmission requests into the scoring of a statistical sequential inspection scheme proposed by E. Page in 1954. Each transmitted packet is scored based on the outcome of the decoding process (i.e., whether it is accepted or rejected). When the cumulative score crosses a decision boundary, the coding strategy is altered and the sequential inspection scheme is restarted using the same scoring routine with different weighting and boundary constants. In this way the channel encoder/decoder is able to alter its strategy and adapt itself to changes in the channel. The analysis of this system is based on the average run length of the tests in the various channel states. These values indicate the delay the system experiences in reacting to a change in the channel and the tendency the test has to terminate prematurely. These factors are a function of the test constants which are determined algorithmatically by maximizing the system throughput using the system reliability as a constraint. Results show that the performance of this system is close to that of the ideal system with perfect channel state information.>

It is shown that the Green machine decoder can be modified to allow for the use of first-order Reed-Muller codes in both type-I and type-II hybrid-ARQ protocols. The type-I protocols offer substantially better reliability performance than their FEC counterparts, though at the expense of a reduction in throughput at low SNR. The type-II protocols offer similar reliability performance to that provided by the the type-I protocols, but offer much better throughput performance at low SNR. Both the type-I and type-II protocols are obtained though minor modifications of the Green machine that do not appreciably increase the complexity or decrease the speed of the decoder.>

MDS codes possess several properties that make them an ideal choice for type-II hybrid-ARQ protocols. These properties include "strong separability", "strong invertibility", and excellent reliability performance when used for simultaneous error detection and correction. In this paper these properties are shown to lead to a natural definition of an MDS (maximum distance separable) type-II hybrid-ARQ protocol. An (n, k) MDS code is decomposed into a pair of (n/2, k) punctured MDS codes. The original code and the two derivative codes are used individually in type I hybrid-ARQ protocols. These three type-I protocols combine to form a single type II protocol. The performance of this system is analyzed in detail, with particular attention paid to the definition of an effective channel model for code words that are known to have caused the generation of retransmission requests.>

A method is described for modifying trellis coded modulation systems for use in type-1 hybrid-ARQ protocols. The difference between the partial path metric of the survivor and that of the best nonsurvivor at each node in the trellis is used to determine the desirability of a retransmission request for a given received packet. Bounds on the reliability and throughput performance of the resulting error control scheme are derived for AWGN channels and slowly fading Rician channels. Examples are included to illustrate the achievable gain of the proposed system relative to ordinary forward-error-correcting trellis coded systems. Hybrid-ARQ protocols based on ordinary trellis coded modulation and multiple trellis coded modulation are also compared over slowly fading Rician channels. The dependence of performance on packet length is examined and illustrated by examples. All analytical results are supported by data from a series of simulations.>

Reliability information provided by sets of orthogonal check sums in a majority logic decoder for block codes is used in a type-I hybrid automatic-repeat-request (ARQ) error control scheme. The reliability information is obtained through a simple modification of the majority logic decoding rule. It is shown that the reliability performance of Reed-Muller and other majority logic decodable codes can be substantially improved at the expense of a very small reduction in throughput. The simplicity of the decoding circuit permits implementation in systems with very high data rates.>

Diversity combining and majority-logic decoding are combined to create a simple but powerful hybrid automatic repeat request (ARQ) error control scheme. Forward-error-correcting (FEC) majority-logic decoders are modified for use in type-I hybrid-ARQ protocols through the identification of reliability information within the decoding process. Diversity combining is then added to reduce the number of retransmissions and their consequent impact on throughput performance. Packet combining has the added benefit of adapting the effective code rate to channel conditions. Excellent reliability performance coupled with a simple high-speed implementation makes the majority-logic system and ideal choice for high-data-rate error control over both stationary and nonstationary channels.>

A method is demonstrated for modifying majority-logic convolutional decoders fur use in type-1 hybrid-ARQ protocols. Majority-logic decoders generate reliability information in the form of orthogonal sets of parity check sums. The modified decoder uses this information to identify received packets whose decoded data may be unreliable and to request their retransmission.>

A new method is discussed for modifying majority-logic convolutional decoders for use in a type-I hybrid-ARQ protocol. In standard forward error correcting (FEC) operation, these decoders generate reliability information in the form of orthogonal sets of parity check sums. The modified decoder uses this information to identify received packets whose decoded data may be unreliable and to request retransmission of these packets. It is shown through analysis and simulation that the resulting error control system provides substantially higher data reliability than its FEC counterpart at the expense of a very small reduction in data throughput.>