Dissertations / Theses on the topic 'Round and communication complexity'
To see the other types of publications on this topic, follow the link: Round and communication complexity.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Round and communication complexity.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Pankratov, Denis. "Communication complexity and information complexity." Thesis, The University of Chicago, 2015. http://pqdtopen.proquest.com/#viewpdf?dispub=3711791.
Full textAbstract:
Information complexity enables the use of information-theoretic tools in communication complexity theory. Prior to the results presented in this thesis, information complexity was mainly used for proving lower bounds and direct-sum theorems in the setting of communication complexity. We present three results that demonstrate new connections between information complexity and communication complexity.
In the first contribution we thoroughly study the information complexity of the smallest nontrivial two-party function: the AND function. While computing the communication complexity of AND is trivial, computing its exact information complexity presents a major technical challenge. In overcoming this challenge, we reveal that information complexity gives rise to rich geometrical structures. Our analysis of information complexity relies on new analytic techniques and new characterizations of communication protocols. We also uncover a connection of information complexity to the theory of elliptic partial differential equations. Once we compute the exact information complexity of AND, we can compute exact communication complexity of several related functions on n-bit inputs with some additional technical work. Previous combinatorial and algebraic techniques could only prove bounds of the form Θ( n). Interestingly, this level of precision is typical in the area of information theory, so our result demonstrates that this meta-property of precise bounds carries over to information complexity and in certain cases even to communication complexity. Our result does not only strengthen the lower bound on communication complexity of disjointness by making it more exact, but it also shows that information complexity provides the exact upper bound on communication complexity. In fact, this result is more general and applies to a whole class of communication problems.
In the second contribution, we use self-reduction methods to prove strong lower bounds on the information complexity of two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product mod 2 (IP). In our first result we affirm the conjecture that the information complexity of GHD is linear even under the uniform distribution. This strengthens the Ω(n) bound shown by Kerenidis et al. (2012) and answers an open problem by Chakrabarti et al. (2012). We also prove that the information complexity of IP is arbitrarily close to the trivial upper bound n as the permitted error tends to zero, again strengthening the Ω(n) lower bound proved by Braverman and Weinstein (2011). More importantly, our proofs demonstrate that self-reducibility makes the connection between information complexity and communication complexity lower bounds a two-way connection. Whereas numerous results in the past used information complexity techniques to derive new communication complexity lower bounds, we explore a generic way, in which communication complexity lower bounds imply information complexity lower bounds in a black-box manner.
In the third contribution we consider the roles that private and public randomness play in the definition of information complexity. In communication complexity, private randomness can be trivially simulated by public randomness. Moreover, the communication cost of simulating public randomness with private randomness is well understood due to Newman's theorem (1991). In information complexity, the roles of public and private randomness are reversed: public randomness can be trivially simulated by private randomness. However, the information cost of simulating private randomness with public randomness is not understood. We show that protocols that use only public randomness admit a rather strong compression. In particular, efficient simulation of private randomness by public randomness would imply a version of a direct sum theorem in the setting of communication complexity. This establishes a yet another connection between the two areas. (Abstract shortened by UMI.)
2
Ada, Anil. "Communication complexity." Thesis, McGill University, 2014. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=121119.
Full textAbstract:
Communication complexity studies how many bits a certain number of parties need to communicate with each other in order to compute a function whose input is distributed among those parties. Although it is a natural area of investigation based on practical considerations, the main motivation comes from the myriad of applications in theoretical computer science.This thesis has three main parts, studying three different aspects of communication complexity.1. The first part is concerned with the k-party communication complexity of functions F:({0,1}^n)^k -> {0,1} in the 'number on the forehead' (NOF) model. This is a fundamental model with many applications. In this model we study composed functions f of g. These functions include most of the well-known and studied functions in communication complexity literature. A major goal is to understand which combinations of f and g lead to hard communication functions. In particular, due to important circuit applications, it is of great interest to understand how powerful the NOF model becomes when k is log n or more. Motivated by these goals, we show that there is an efficient O(log^3 n) cost simultaneous protocol for sym of g when k > 1+log n, sym is any symmetric function and g is any function. This class of functions includes some functions that were previously conjectured to be hard and our result rules this class out for possible very important circuit complexity applications. We also give Ramsey theoretic applications of our efficient protocol. In the setting of k < log n, we study more closely functions of the form majority of g, mod_m of g, and nor of g, where the latter two are generalizations of the well-known functions Inner Product and Disjointness respectively. We characterize the communication complexity of these functions with respect to the choice of g. As the main application, we answer a question posed by Babai et al. (SIAM Journal on Computing, 33:137--166, 2004) and determine the communication complexity of majority of qcsb, where qcsb is the "quadratic character of the sum of the bits" function. 2. The second part is about Fourier analysis of symmetric boolean functions and its applications in communication complexity and other areas. The spectral norm of a boolean function f:{0,1}^n -> {0,1} is the sum of the absolute values of its Fourier coefficients. This quantity provides useful upper and lower bounds on the complexity of a function in areas such as communication complexity, learning theory and circuit complexity. We give a combinatorial characterization for the spectral norm of symmetric functions. We show that the logarithm of the spectral norm is of the same order of magnitude as r(f)log(n/r(f)) where r(f) = max(r_0,r_1), and r_0 and r_1 are the smallest integers less than n/2 such that f(x) or f(x)parity(x) is constant for all x with x_1 + ... + x_n in [r_0, n-r_1]. We present some applications to the decision tree and communication complexity of symmetric functions. 3. The third part studies privacy in the context of communication complexity: how much information do the players reveal about their input when following a communication protocol? The unattainability of perfect privacy for many functions motivates the study of approximate privacy. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) defined notions of worst-case as well as average-case approximate privacy, and presented several interesting upper bounds, and some open problems for further study. In this thesis, we obtain asymptotically tight bounds on the trade-offs between both the worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey Auction, which is the canonical example of a truthful auction. We also prove exponential lower bounds on the approximate privacy of protocols computing the Intersection function, independent of its communication cost. This proves a conjecture of Feigenbaum et al.La complexité de communication étudie combien de bits un groupe de joueurs donné doivent échanger entre eux pour calculer une function dont l'input est distribué parmi les joueurs. Bien que ce soit un domaine de recherche naturel basé sur des considérations pratiques, la motivation principale vient des nombreuses applications théoriques.Cette thèse comporte trois parties principales, étudiant trois aspects de la complexité de communication.1. La première partie discute le modèle 'number on the forehead' (NOF) dans la complexité de communication à plusieurs joueurs. Il s'agit d'un modèle fondamental en complexité de communication, avec des applications à la complexité des circuits, la complexité des preuves, les programmes de branchement et la théorie de Ramsey. Dans ce modèle, nous étudions les fonctions composeés f de g. Ces fonctions comprennent la plupart des fonctions bien connues qui sont étudiées dans la littérature de la complexité de communication. Un objectif majeur est de comprendre quelles combinaisons de f et g produisent des compositions qui sont difficiles du point de vue de la communication. En particulier, à cause de l'importance des applications aux circuits, il est intéressant de comprendre la puissance du modèle NOF quand le nombre de joueurs atteint ou dépasse log n. Motivé par ces objectifs nous montrons l'existence d'un protocole simultané efficace à k joueurs de coût O(log^3 n) pour sym de g lorsque k > 1 + log n, sym est une function symmétrique quelconque et g est une fonction arbitraire. Nous donnons aussi des applications de notre protocole efficace à la théorie de Ramsey.Dans le contexte où k < log n, nous étudions de plus près des fonctions de la forme majority de g, mod_m de g et nor de g, où les deux derniers cas sont des généralisations des fonctions bien connues et très étudiées Inner Product et Disjointness respectivement. Nous caractérisons la complexité de communication de ces fonctions par rapport au choix de g.2. La deuxième partie considère les applications de l'analyse de Fourier des fonctions symmétriques à la complexité de communication et autres domaines. La norme spectrale d'une function booléenne f:{0,1}^n -> {0,1} est la somme des valeurs absolues de ses coefficients de Fourier. Nous donnons une caractérisation combinatoire pour la norme spectrale des fonctions symmétriques. Nous montrons que le logarithme de la norme spectrale est du même ordre de grandeur que r(f)log(n/r(f)), avec r(f) = max(r_0,r_1) où r_0 et r_1 sont les entiers minimaux plus petits que n/2 pour lesquels f(x) ou f(x)parity(x) est constant pour tout x tel que x_1 + ... + x_n à [r_0,n-r_1]. Nous présentons quelques applications aux arbres de décision et à la complexité de communication des fonctions symmétriques.3. La troisième partie étudie la confidentialité dans le contexte de la complexité de communication: quelle quantité d'information est-ce que les joueurs révèlent sur leur input en suivant un protocole donné? L'inatteignabilité de la confidentialité parfaite pour plusieurs fonctions motivent l'étude de la confidentialité approximative. Feigenbaum et al. (Proceedings of the 11th Conference on Electronic Commerce, 167--178, 2010) ont défini des notions de confidentialité approximative dans le pire cas et dans le cas moyen, et ont présenté plusieurs bornes supérieures intéressantes ainsi que quelques questions ouvertes. Dans cette thèse, nous obtenons des bornes asymptotiques précises, pour le pire cas aussi bien que pour le cas moyen, sur l'échange entre la confidentialité approximative de protocoles et le coût de communication pour les enchères Vickrey Auction, qui constituent l'exemple canonique d'une enchère honnête. Nous démontrons aussi des bornes inférieures exponentielles sur la confidentialité approximative de protocoles calculant la function Intersection, indépendamment du coût de communication. Ceci résout une conjecture de Feigenbaum et al.
3
Chen, Lijie S. M. Massachusetts Institute of Technology. "Fine-grained complexity meets communication complexity." Thesis, Massachusetts Institute of Technology, 2019. https://hdl.handle.net/1721.1/122754.
Full textAbstract:
Thesis: S.M., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2019Cataloged from PDF version of thesis.
Includes bibliographical references (pages 215-229).
Fine-grained complexity aims to understand the exact exponent of the running time of fundamental problems in P. Basing on several important conjectures such as Strong Exponential Time Hypothesis (SETH), All-Pair Shortest Path Conjecture, and the 3-Sum Conjecture, tight conditional lower bounds are proved for numerous exact problems from all fields of computer science, showing that many text-book algorithms are in fact optimal. For many natural problems, a fast approximation algorithm would be as important as fast exact algorithms. So it would be interesting to show hardness for approximation algorithms as well. But we had few techniques to prove tight hardness for approximation problems in P--In particular, the celebrated PCP Theorem, which proves similar approximation hardness in the world of NP-completeness, is not fine-grained enough to yield interesting conditional lower bounds for approximation problems in P.
In 2017, a breakthrough work of Abboud, Rubinstein and Williams [12] established a framework called "Distributed PCP", and applied that to show conditional hardness (under SETH) for several fundamental approximation problems in P. The most interesting aspect of their work is a connection between fine-grained complexity and communication complexity, which shows Merlin-Arther communication protocols can be utilized to give fine-grained reductions between exact and approximation problems. In this thesis, we further explore the connection between fine-grained complexity and communication complexity. More specifically, we have two sets of results. In the first set of results, we consider communication protocols other than Merlin-Arther protocols in [12] and show that they can be used to construct other fine-grained reductions between problems. [sigma]₂ Protocols and An Equivalence Class for Orthogonal Vectors (OV).
First, we observe that efficient [sigma]₂[superscripts cc] protocols for a function imply fine-grained reductions from a certain related problem to OV. Together with other techniques including locality-sensitive hashing, we establish an equivalence class for OV with O(log n) dimensions, including Max-IP/Min-IP, approximate Max-IP/Min-IP, and approximate bichromatic closest/further pair. · NP · UPP Protocols and Hardness for Computational Geometry Problems in 2⁰([superscript log*n]) Dimensions. Second, we consider NP · UPP protocols which are the relaxation of Merlin-Arther protocols such that Alice and Bob only need to be convinced with probability > 1/2 instead of > 2/3.
We observe that NP · UPP protocols are closely connected to Z-Max-IP problem in very small dimensions, and show that Z-Max-IP, l₂₋-Furthest Pair and Bichromatic l₂-Closest Pair in 2⁰[superscript (log* n)] dimensions requires n²⁻⁰[superscript (1)] time under SETH, by constructing an efficient NP - UPP protocol for the Set-Disjointness problem. This improves on the previous hardness result for these problems in w(log² log n) dimensions by Williams [172]. · IP Protocols and Hardness for Approximation Problems Under Stronger Conjectures. Third, building on the connection between IP[superscript cc] protocols and a certain alternating product problem observed by Abboud and Rubinstein [11] and the classical IP = PSPACE theorem [123, 155]. We show that several finegrained problems are hard under conjectures much stronger than SETH (e.g., the satisfiability of n⁰[superscript (1)]-depth circuits requires 2(¹⁻⁰[superscript (1)n] time).
In the second set of results, we utilize communication protocols to construct new algorithms. · BQP[superscript cc] Protocols and Approximate Counting Algorithms. Our first connection is that a fast BQP[superscript cc] protocol for a function f implies a fast deterministic additive approximate counting algorithm for a related pair counting problem. Applying known BQP[superscript cc] protocols, we get fast deterministic additive approximate counting algorithms for Count-OV (#OV), Sparse Count-OV and Formula of SYM circuits. · AM[superscript cc]/PH[superscript cc] Protocols and Efficient SAT Algorithms. Our second connection is that a fast AM[superscript cc] (or PH[superscript cc]) protocol for a function f implies a faster-than-bruteforce algorithm for a related problem.
In particular, we show that if the Longest Common Subsequence (LCS) problem admits a fast (computationally efficient) PH[superscript cc] protocol (polylog(n) complexity), then polynomial-size Formula-SAT admits a 2[superscript n-n][superscript 1-[delta]] time algorithm for any constant [delta] > 0, which is conjectured to be unlikely by a recent work of Abboud and Bringmann [6].
by Lijie Chen.
S.M.
S.M. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science
4
Dam, Wim van. "Nonlocality and communication complexity." Thesis, University of Oxford, 1999. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.325982.
Full text
5
Lerays, Virginie. "Quantum nonlocality and communication complexity." Paris 7, 2014. http://www.theses.fr/2014PA077151.
Full textAbstract:
Les fondements de l'informatique ont subi un bouleversement face à l'émergence du calcul quantique comme nouveau modèle de calcul. Nous nous intéresserons dans cette thèse à la complexité de la communication, vue sous l'angle de la théorie de l'information quantique. En complexité de la communication, on cherche à savoir combien de communication il faut pour résoudre des problèmes où les entrées sont réparties entre les entités de calcul. Cette thèse présente un moyen d'obtenir des bornes inférieures en complexité de la communication en exploitant des idées liées à l'étude de phénomènes quantiques tels que la nonlocalité. Ces méthodes sont alors comparées aux méthodes déjà connues dans la littérature et permettent d'obtenir une nouvelle famille d'inégalités de Bell. Nous montrons aussi dans cette thèse, en utilisant les connections entre complexité de la communication et nonlocalité quantique, que toutes les bornes inférieures connues utilisées en complexité de la communication sont des bornes inférieures pour la complexité de l'information. Ceci renforce l'idée que ces deux quantités sont équivalentes et permet d'obtenir plusieurs résultats de sommes directes en complexité de la communication pour des fonctions souvent étudiéesQuantum computing raises a lot of questions related to the foundations of computing. We study, in this thesis, a complexity model called communication complexity, where we study the amount of communication required to solve a distributed task. We study this model from the perspective of quantum information theory. This thesis introduces a new way of obtaining lower bounds on communication complexity, using ideas developed in the study of quantum nonlocality. These methods are compared to previously known lower-bound methods and allow us to define a new family of Bell inequalities. We also prove in this thesis that ail previously known lower bounds for communication complexity are also lower bounds on information complexity. This witnesses the potential equivalence between these two measures of complexity and allows us to obtain direct sum results on the communication complexity of very-well studied functions
6
Lacayo, Virginia. "Communicating Complexity: A Complexity Science Approach to Communication for Social Change." Ohio University / OhioLINK, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1367522049.
Full text
7
Angus, Simon Douglas Economics Australian School of Business UNSW. "Economic networks: communication, cooperation & complexity." Awarded by:University of New South Wales. Economics, 2007. http://handle.unsw.edu.au/1959.4/27005.
Full textAbstract:
This thesis is concerned with the analysis of economic network formation. There are three novel sections to this thesis (Chapters 5, 6 and 8). In the first, the non-cooperative communication network formation model of Bala and Goyal (2000) (BG) is re-assessed under conditions of no inertia. It is found that the Strict Nash circle (or wheel) structure is still the equilibrium outcome for n = 3 under no inertia. However, a counter-example for n = 4 shows that with no inertia infinite cycles are possible, and hence the system does not converge. In fact, cycles are found to quickly dominate outcomes for n > 4 and further numerical simulations of conditions approximating no inertia (probability of updating > 0.8 to 1) indicate that cycles account for a dramatic slowing of convergence times. These results, together with the experimental evidence of Falk and Kosfeld (2003) (FK) motivate the second contribution of this thesis. A novel artificial agent model is constructed that allows for a vast strategy space (including the Best Response) and permits agents to learn from each other as was indicated by the FK results. After calibration, this model replicates many of the FK experimental results and finds that an externality exploiting ratio of benefits and costs (rather than the difference) combined with a simple altruism score is a good proxy for the human objective function. Furthermore, the inequity aversion results of FK are found to arise as an emergent property of the system. The third novel section of this thesis turns to the nature of network formation in a trust-based context. A modified Iterated Prisoners' Dilemma (IPD) model is developed which enables agents to play an additional and costly network forming action. Initially, canonical analytical results are obtained despite this modification under uniform (non-local) interactions. However, as agent network decisions are 'turned on' persistent cooperation is observed. Furthermore, in contrast to the vast majority of non-local, or static network models in the literature, it is found that a-periodic, complex dynamics result for the system in the long-run. Subsequent analysis of this regime indicates that the network dynamics have fingerprints of self-organized criticality (SOC). Whilst evidence for SOC is found in many physical systems, such dynamics have been seldom, if ever, reported in the strategic interaction literature.
8
McGinty, Nigel, and nigel mcginty@defence gov au. "Reduced Complexity Equalization for Data Communication." The Australian National University. Research School of Information Sciences and Engineering, 1998. http://thesis.anu.edu.au./public/adt-ANU20050602.122741.
Full textAbstract:
Optimal decision directed equalization techniques for time dispersive communication channels are often too complex to implement. This thesis considers reduced complexity decision directed equalization that lowers complexity demands yet retains close to optimal performance. The first part of this dissertation consists of three reduced complexity algorithms based on the Viterbi Algorithm (VA) which are: the Parallel Trellis VA (PTVA); Time Reverse Reduced State Sequence Estimation (TR-RSSE); and Forward-Backward State Sequence Detection (FBSSD). The second part of the thesis considers structural modifications of the Decision Feedback Equalizer (DFE), which is a special derivative of the VA, specifically, optimal vector quantization for fractionally spaced DFEs, and extended stability regions for baud spaced DFEs using passivity analysis are investigated.¶
For a special class of sparse channels the VA can be decomposed over a number of independent parallel trellises. This decomposition will be called the Parallel Trellis Viterbi Algorithm and can have lower complexity than the VA yet it retains optimal performance. By relaxing strict sparseness constraints on the channel a sub-optimal approach is proposed which keeps complexity low and obtains good performance.¶
Reduced State Sequence Estimation (RSSE) is a popular technique to reduce complexity. However, its deficiency can be the inability to adequately equalize non-minimum phase channels. For channels that have energy peaks in the tail of the impulse response (post-cursor dominant) RSSE's complexity must be close to the VA or performance will be poor. Using a property of the VA which makes it invariant to channel reversal, TR-RSSE is proposed to extend application of RSSE to post-cursor dominant channels.¶
To further extend the class of channels suitable for RSSE type processing, FBSSD is suggested. This uses a two pass processing method, and is suited to channels that have low energy pre and post-cursor. The first pass generates preliminary estimates used in the second pass to aid the decision process. FBSSD can range from RSSE to TR-RSSE depending on parameter settings.¶
The DFE is obtained when the complexity of RSSE is minimized. Two characterizing properties of the DFE, which are addressed in this thesis, are feedback and quantization. A novel fractionally spaced (FS) DFE structure is presented which allows the quantizer to be generalized relative to the quantizer used in conventional FS-DFEs. The quantizer can be designed according to a maximum a posteriori criterion which takes into account a priori statistical knowledge of error occurrences. A radically different quantizer can be obtained using this technique which can result in significant performance improvements.¶
Due to the feedback nature of the DFE a form of stability can be considered. After a decision error occurs, a stable DFE will, after some finite time and in the absence of noise, operate error free. Passivity analysis provides sufficient conditions to determine a class of channels which insures a DFE will be stable. Under conditions of short channels and small modulation alphabets, it is proposed that conventional passivity analysis can be extended to account for varying operator gains, leading to weaker sufficient conditions for stability (larger class of channels).
9
Tesson, Pascal. "An algebraic approach to communication complexity." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape7/PQDD_0026/MQ50894.pdf.
Full text
10
Dhulipala, Anand. "On communication complexity and universal compression." Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 2007. http://wwwlib.umi.com/cr/ucsd/fullcit?p3284204.
Full textAbstract:
Thesis (Ph. D.)--University of California, San Diego, 2007.Title from first page of PDF file (viewed January 10, 2008). Available via ProQuest Digital Dissertations. Vita. Includes bibliographical references (p. 93-95).
11
Tesson, Pascal. "An algebraic approach to communication complexity /." Thesis, McGill University, 1998. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=21653.
Full textAbstract:
In this work, we define the communication complexity of a monoid M as the maximum complexity of any language recognized by M, and show that monoid classes defined by, communication complexity classes form varieties. Then we prove that a group G has constant communication complexity for k players if and only if G is a nilpotent group of class at most ( k - 1), and has linear complexity otherwise. When M is aperiodic, we show that its 2-party communication complexity is constant if M is commutative, logarithmic if M is not commutative but is in the variety DA, and is linear otherwise. Moreover, we show that if M is in DA, there exists a k such that M has constant k-party communication complexity. We conjecture that this condition is also necessary and prove lower bounds in that direction.These results lead us to state a conjecture which would generalize Szegedy's theorem to O(1) players. They also suggest several interesting possibilities to further uncover algebraic characterizations of communication complexity classes. (Abstract shortened by UMI.)
12
Kamath, Pritish. "Communication complexity of permutation-invariant functions." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/99861.
Full textAbstract:
Thesis: S.M. in Computer Science & Engineering, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.Cataloged from PDF version of thesis.
Includes bibliographical references (pages 68-71).
Motivated by the quest for a broader understanding of communication complexity of simple functions, we introduce the class of "permutation-invariant" functions. A partial function f : {0, 1}n x {0, 1}n --> {0, 1, ?} is permutation-invariant if for every bijection [pi]: {1,..., n} --> {1,.. ., n} and every x, y [sum] {0, I}n, it is the case that f (x, y) = f (x[pi], y[pi]). Most of the commonly studied functions in communication complexity are permutation-invariant. For such functions, we present a simple complexity measure (computable in time polynomial in n given an implicit description of f) that describes their communication complexity up to polynomial factors and up to an additive error that is logarithmic in the input size. This gives a coarse taxonomy of the communication complexity of simple functions. Our work highlights the role of the well-known lower bounds of functions such as SET-DISJOINTNESS and INDEXING, while complementing them with the relatively lesser-known upper bounds for GAP-INNER-PRODUCT (from the sketching literature) and SPARSE-GAP-INNER-PRODUCT (from the recent work of Canonne et al. [ITCS 2015]). We also present consequences to the study of communication complexity with imperfectly shared randomness where we show that for total permutation-invariant functions, imperfectly shared randomness results in only a polynomial blow-up in communication complexity after an additive O(log log n) loss.
by Pritish Kamath.
S.M. in Computer Science & Engineering
13
Alvarez, George Francisco Centre of Health Informatics UNSW. "Interruptive communication patterns in the intensive care unit ward round." Awarded by:University of New South Wales. Centre of Health Informatics, 2006. http://handle.unsw.edu.au/1959.4/23430.
Full textAbstract:
Medical error and patient safety have become important issues. It is clear that medical error is more influenced by systemic factors rather than human characteristics. Communication patterns, in particular interruptive communication, maybe one of the systemic factors that contribute to the burden of medical error. Objective: An exploratory study to examine interruptive communication patterns of healthcare staff within an intensive care unit during ward rounds. Methods: The study was conducted in a tertiary hospital in Sydney, Australia. Nine participants were observed individually, for a total of 24 hours, using the Communication Observation Method (COM). The amount of time spent in conversation, the number of conversation initiating and number of turn-taking interruptions were recorded. Results: Participants averaged 75% [95% confidence interval 72.8-77.2] of their time in communication events during ward rounds. There were 345 conversation-initiating interruptions (C.I.I.) and 492 turn-taking interruptions (T.T.I.). C.I.I. accounted for 37% [95%CI 33.9-40.1] of total communication event time (5hr: 53min). T.T.I. accounted for 5.3% of total communication event time (56min). Conclusion: This is the first study to specifically examine turn-taking interruptions in a clinical setting. Staff in this intensive care unit spent the majority of their time in communication. Turn taking interruptions within conversations occurred at about the same frequency as conversation initiating interruptions, which have been the subject of earlier studies. These results suggest that the overall burden of interruptions in some settings may be significantly higher than previously suspected.
14
Herrmann, Andrew F. "Understanding Complexity in a Polymediated Age." Digital Commons @ East Tennessee State University, 2014. https://dc.etsu.edu/etsu-works/786.
Full text
15
Kamat, Angad Mohandas. "Improvements in communication complexity using quantum entanglement." Texas A&M University, 2008. http://hdl.handle.net/1969.1/86008.
Full textAbstract:
Quantum computing resources have been known to provide speed-ups in computational complexity in many algorithms. The impact of these resources in communication, however, has not attracted much attention. We investigate the impact of
quantum entanglement on communication complexity. We provide a positive result,
by presenting a class of multi-party communication problems wherein the presence of
a suitable quantum entanglement lowers the classical communication complexity. We
show that, in evaluating certains function whose parameters are distributed among
various parties, the presence of prior entanglement can help in reducing the required
communication. We also present an outline of realizing the required entanglement
through optical photon quantum computing. We also suggest the possible impact of
our results on network information flow problems, by showing an instance of a lower
bound which can be broken by adding limited power to the communication model.
16
Ferdinand, N. S. (Nuwan Suresh). "Low complexity lattice codes for communication networks." Doctoral thesis, Oulun yliopisto, 2016. http://urn.fi/urn:isbn:9789526210964.
Full textAbstract:
Abstract Lattice codes achieve AWGN capacity and naturally fit in many multi-terminal networks because of their inherited structure. Although extensive information theoretic research has been done to prove the importance of lattice codes for these networks, the progress in finding practical low-complexity lattice schemes is limited. Hence, the motivation of this thesis is to develop several methods to make lattice codes practical for communication networks. First, we propose an efficient lattice coding scheme for real-valued, full-duplex one- and two-way relay channels. Lattice decomposition, superposition, and block Markov encoding are used to propose a simple, yet near capacity achieving encoding/decoding schemes for these relay channels. By using information theoretic tools, we prove the achievable rates of these schemes, which are equal to the best known rates. Then, we construct practical, low-complexity implementations of the proposed relay schemes using low-density lattice codes. Numerical evaluation is presented and they show that our schemes achieve performance as close as 2.5dB away from theoretical limits. The effect of shaping/coding loss on the performance of relay channels is studied. Then, we propose a low complexity lattice code construction that provides high shaping and coding gains. First, integer information is encoded to shaped integers. Two methods are proposed for this task: ''Voronoi integers'' and ''non uniform integers''. These shaped integers have shaping gains over the integer lattice. Then for the second step, we present a general framework to systematically encode these integers, using any high dimensional lattice with lower-triangular generator or parity check matrices, retaining the same shaping gain. The proposed scheme can be used to shape high dimensional lattices such as low density lattice codes, LDA-lattice, etc. Comprehensive analysis is presented using low density lattice codes. By using E8 and BW16 as shaping lattices, we numerically show the Voronoi integers result in the shaping gain of these lattices, that is, as much as 0.65dB and 0.86dB. It is numerically observed that non-uniform integers have shaping gains of up to 1.25dB. These shaping operations can be implemented with less complexity than previous low density lattice codes shaping approaches and shaping gains are higher than in previously reported cases, which are in the order of 0.4dB. Lastly, we propose a low complexity practical code construction for compute-and-forward. A novel code construction called ''mixed nested lattice code construction'' is developed. This code construction uses a pair of distinct nested lattices to encode the integers where shaping is provided by a small dimensional lattice with high shaping gain and coding is performed using a high coding gain and a high dimensional lattice. This construction keeps the shaping and the coding gains of respective shaping and coding lattices. Further, we prove an existence of an isomorphism in this construction such that linear combination of lattice codes can be mapped to a linear combination of integers over a finite field. Hence, this construction can be readily used for any compute-and-forward applications. A modified LDLC decoder is proposed to estimate a linear combination of messages. Performance is numerically evaluatedTiivistelmä Hilakoodit saavuttavat AWGN kapasiteetin ja sopivat luonnollisesti moniin monen päätelaitteen verkkoihin niihin sisältyvän rakenteen vuoksi. Vaikka lukuisat informaatioteoreettiset tutkimustyöt todistavat hilakoodien tärkeyden näille verkoille, käytännössä alhaisen kompleksisuuden hilajärjestelmiä on vielä vähän. Näin ollen tämän tutkielman tarkoitus on kehittää useita metodeja, jotta hilakoodeista saadaan käytännöllisiä viestintäverkkoihin. Aluksi, ehdotamme tehokkaan hilakoodausjärjestelmän reaaliarvoisille, full duplexisille yksi- ja kaksisuuntaisille välittäjäkanaville. Käytämme hilan hajottamista, superpositiota ja lohko-Markov -koodausta ehdottaessamme yksinkertaiset ja siltikin kapasiteetin saavuttavat koodaus- ja dekoodausjärjestelmät näihin välityskanaviin. Käyttämällä informaatioteoreettisia työkaluja, osoitamme näiden järjestelmien saavutettavat nopeudet, jotka ovat yhtä suuret kuin parhaimmat tunnetut nopeudet. Sitten rakennamme käytännölliset ja alhaisen monimutkaisuuden toteutukset ehdotetuille välitysjärjestelmille käyttäen alhaisen tiheyden hilakoodeja. Esitämme näille järjestelmille numeeriset arvioinnit, jotka näyttävät että nämä toteutukset saavuttavat tehokkuuden, joka on 2.5dB:n päässä teoreettisista rajoista. Tutkimme muotoilu- ja koodaushäviön vaikutusta välityskanavien tehokkuuteen. Sitten, ehdotamme alhaisen monimutkaisuuden hilakoodirakenteen, joka tarjoaa korkean muotoilu- ja koodausvahvistuksen. Ensin, kokonaislukuinformaatio on koodattu muotoiltuihin kokonaislukuihin. Esitämme kaksi metodia tähän tehtävään; 'Voronoi kokonaisluvut' ja 'ei yhtenäiset kokonaisluvut'. Näillä muotoilluilla kokonaisluvuilla on muotoiluvahvistusta kokonaislukuhilalle. Toisena askeleena, esitämme yleiset puitteet systemaattiseen kokonaislukujen koodaukseen käyttäen korkeaulotteisia hiloja alhaisen kolmiogeneraattori- tai pariteettivarmistusmatriiseja, jotka säilyttävät samalla muotoiluvahvistuksen. Ehdotettua järjestelmää voidaan käyttää muotoilemaan korkeaulotteisia hiloja kuten alhaisen tiheyden hilakoodeja, LDA-hiloja, jne. Esitämme kattavan analyysin käyttäen alhaisen tiheyden hilakoodeja. Käyttämällä muotoiluhiloina E8aa ja BW16a, näytämme numeerisesti 'Voronoi kokonaislukujen' käyttämisen seurauksena saavutettavat hilojen muotoiluvahvistukset, jotka ovat jopa 0.65dB ja 0.86dB. Näytämme myös numeerisesti että 'ei yhtenäisillä kokonaisluvuilla' on muotoiluvahvistusta jopa 1.25dB. Nämä muotoiluoperaatiot voidaan toteuttaa alhaisemmalla monimutkaisuudella kuin aikaisemmat 'alhaisen tiheyden hilakoodien muotoilumenetelmät' ja muotoiluvahvistukset ovat suuremmat kuin aikaisemmin raportoidut tapaukset, jotka ovat suuruusluokaltaan 0.4dB. Viimeiseksi, ehdotamme käytännöllisen koodikonstruktion alhaisella monimutkaisuudella 'laske ja lähetä' -menetelmään. Kehitämme uuden koodikonstruktion, jota kutsumme 'sekoitetuksi sisäkkäiseksi hilakoodikonstruktioksi'. Tämä koodikonstruktio käyttää kahta eroteltavissa olevaa sisäkkäistä hilaa koodaamaan kokonaisluvut siellä, missä muotoilu tehdään pienen ulottuvuuden hiloilla korkean muotoiluvahvistuksella ja koodaus toteutetaan käyttäen korkean koodausvahvistuksen omaavaa korkeaulottuvuuksista hilaa. Tämä konstruktio säilyttää muotoilu- ja koodausvahvistukset kullekin muotoilu- ja koodaushilalle. Lisäksi, todistamme isomorfismin olemassaolon tässä konstruktiossa siten, että lineaarisen hilakoodien kombinaatio voidaan kuvata lineaarisena kokonaislukujen kombinaationa äärellisessä kunnassa. Näin ollen tätä konstruktiota voidaan helposti käyttää missä tahansa 'laske ja lähetä' -sovelluksessa. Esitämme muokatun LDLC dekooderin lineaarisen viestikombinaation estimointiin. Arvioimme tehon numeerisesti
17
Baudic, Gwilherm. "Complexity Efficient Decoder Design for Vehicular Communication." Thesis, KTH, Kommunikationsteori, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-124014.
Full textAbstract:
Vehicular communication is currently seen as a key technology for enabling safer and more comfortable driving. In the general effort to reduce the number of casualties and improve the traffic flow despite an increasing number of vehicles, this field has a promising future. IEEE 802.11p has been chosen as the standard for the Physical Layer (PHY) design for wireless vehicular communication. However, the channels encountered in such situations pose several challenges for reliable communications. Time and frequency selectivity caused by dispersive environments and high mobility lead to doubly-selective channels. The systems are expected to conduct proper operation, in spite of these disturbances. In this thesis, we focus on the design of receivers working on the PHY layer, with an emphasis on limited complexity. This poses high constraints on the algorithms, which already have to cope with the limited amount of information provided by the training sequences. The solutions considered all involve joint channel estimation and decoding, characterized by the use of an iterative structure. Such structures allow the channel estimation to benefit from the knowledge brought by the decoder, which ultimately decreases the error rate. Following a previous work, we use algorithms based on Minimum Mean Square Error (MMSE) or Maximum A Posteriori (MAP) estimation. These receivers were modified to operate on full frames instead of individual subcarriers, and various improvements were studied. We provide a detailed analysis of the complexity of the proposed designs, along with an evaluation of their decoding performance. The trade-offs between these two parameters are also discussed. A part of these analyses isused in [10]. Finally, we give an insight into some considerations which may arise when implementing the algorithms on testbeds.
18
Ada, Anil. "Non-deterministic communication complexity of regular languages." Thesis, McGill University, 2007. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=112367.
Full textAbstract:
The notion of communication complexity was introduced by Yao in his seminal paper [Yao79]. In [BFS86], Babai Frankl and Simon developed a rich structure of communication complexity classes to understand the relationships between various models of communication complexity. This made it apparent that communication complexity was a self-contained mini-world within complexity theory. In this thesis, we study the place of regular languages within this mini-world. In particular, we are interested in the non-deterministic communication complexity of regular languages.We show that a regular language has either O(1) or O(log n) non-deterministic complexity. We obtain several linear lower bound results which cover a wide range of regular languages having linear non-deterministic complexity. These lower bound results also imply a result in semigroup theory: we obtain sufficient conditions for not being in the positive variety Pol(Com).
To obtain our results, we use algebraic techniques. In the study of regular languages, the algebraic point of view pioneered by Eilenberg ([Eil74]) has led to many interesting results. Viewing a semigroup as a computational device that recognizes languages has proven to be prolific from both semigroup theory and formal languages perspectives. In this thesis, we provide further instances of such mutualism.
19
Sun, Yean. "Effective length factors for solid round diagonals in guyed communication towers." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1999. http://www.collectionscanada.ca/obj/s4/f2/dsk1/tape8/PQDD_0033/MQ62290.pdf.
Full text
20
Hahne, Ellen Louise. "Round robin scheduling for fair flow control in data communication networks." Thesis, Massachusetts Institute of Technology, 1986. http://hdl.handle.net/1721.1/14932.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1987.MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING
Bibliography: leaves 216-218.
by Ellen Louise Hahne.
Ph.D.
21
Weisenhorn, Martin. "Low-complexity techniques for ultra-wideband communication systems." kostenfrei, 2007. http://mediatum2.ub.tum.de/doc/625801/document.pdf.
Full text
22
Luo, Zhi-Quan. "Communication complexity of some problems in distributed computation." Thesis, Massachusetts Institute of Technology, 1989. http://hdl.handle.net/1721.1/14344.
Full textAbstract:
Thesis (Sc. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1989.Includes bibliographical references (leaves 153-158).
by Zhi-Quan Luo.
Sc.D.
23
Reed, Delanna. "A Round Peg in a Square Hole: Lesbian Teachers Fitting In." Digital Commons @ East Tennessee State University, 2014. https://dc.etsu.edu/etsu-works/1288.
Full text
24
Reed, Delanna. "A Round Peg in a Square Hole: Lesbian Teachers Fitting In." Digital Commons @ East Tennessee State University, 2016. https://dc.etsu.edu/etsu-works/1279.
Full textAbstract:
Her show, “A Round Peg in a Square Hole: Lesbian Teachers Fitting In,” is the culmination of her dissertation research in which she studied the impact of heterosexism on eleven K-12 lesbian teachers in public and private life. In this performance ethnography, she tells stories that reveal the cultural intermingling of family, community, and work to shape their identities as lesbians and teachers, divulging ways they succumb to and resist heteronormative society.
25
Tasneem, Khawaja Tauseef. "Reduced Complexity Detection Techniques for Multi-Antenna Communication Systems." Thesis, University of Canterbury. Electrical and Computer Engineering, 2013. http://hdl.handle.net/10092/8611.
Full textAbstract:
In a multiuser system, several signals are transmitted simultaneously within the same frequency band. This can result in significant improvements both in spectral efficiency and system capacity. However, a detrimental effect of the shared transmissions (both in time and bandwidth), is that the signal received at the base station (BS) or access point (AP) suffers from cochannel interference (CCI) and inter-symbol interference (ISI). This situation presents challenges to receiver design. To combat the destructive nature of multipath fading, a receiver often employs multiple antennas to collect the faded superimposed versions of the transmitted signals. The multiple signals are combined and processed in such a way that the effects of CCI and ISI are minimized and the desired information is reliably recovered. The situation is even more challenging when the system is operating under overload, i.e. when there are fewer receive antennas than there are transmitted signals. Multiuser detection (MUD) is used to simultaneously estimate the information sent by the transmitters. To do this, the receiver exploits differences among the cochannel signals (through unique spatial signatures in this case).
We consider a cochannel communication system where multiple transmitted signals arrive at a receiver (equipped with multiple receive antennas) after propagating through a Rayleigh fading channel. It is assumed that the receiver is operating in an overloaded scenario. For such systems, an optimum maximum a posterior probability (MAP) detector estimates the transmitted signal by maximizing the probability of correct decision. The MAP detector reduces to the maximum likelihood (ML) detector when all the transmitted signals are equiprobable. The computational complexity of both MAP and ML detectors increases exponentially with the number of transmitted signals and the channel memory. For large systems suffering severe CCI and ISI, this is clearly not a good choice for real-time implementation due to the associated computational expenses. The main factors that influence the complexity of MAP / ML detection are: (i) the number of transmitted signals (or equivalently the number of users sharing the system resources), (ii) modulation alphabet size, and (iii) length of the channel memory. On the other hand, linear detection approaches fail to offer acceptable performance while other nonlinear sub-optimum approaches incur high computational costs for reasonably improved system performance and exhibit an irreducible error-floor at medium to high signal to noise ratio (SNR) values.
We develop receiver signal processing techniques for the frequency-flat fading channel (where all the multipaths of the transmitted signal arrive at the receiver within a symbol period). We develop an ant colony optimization (ACO) assisted soft iterative detection approach for binary phase-shift keying (BPSK) modulated signals which employs a simplified MAP criteria to extract the most probable signals from the search space. The structure of the receiver is such that it can continue operating under overloaded conditions. The technique achieves near maximum likelihood (ML) performance in critically loaded cases using much lower complexity. For the challenging case of overload it still offers performance close to ML at low to moderate SNR values. Second, an integrated framework comprising of ACO metaheuristic and a recursively defined ML search criteria is developed to handle multilevel modulations. The proposed receiver is capable of achieving near-ML performance for the considered system with significant savings in computational complexity. The receiver framework is independent of the system loading condition, and therefore it remains suitable for overloaded scenarios. Due to the branch and bound nature of the algorithm, an exact expression for the complexity cannot be determined. Instead, an upper bound on computational complexity is developed.
26
Steinberg, David Charles. "Why Hollywood lost the Uruguay Round : the political economy of mass communication revisited." Thesis, London School of Economics and Political Science (University of London), 1999. http://etheses.lse.ac.uk/1568/.
Full textAbstract:
In this dissertation I examine the reasons why the U.S. film industry lost the GATT-Uruguay Round negotiations on audiovisual services and intellectual property rights (IPRs) related to copyright. I revisit the political economy approach to communication and implement Mosco's (1996) suggestions on the approach's renewal. Mosco notes that political economists of communication thematically view the state as supporting transnational business (1996, p. 94). However, Jarvie's (1992) analysis of the relationship between the U.S. government and film industry between 1920 and 1950 suggests that this 'support' theme does not adequately capture the often antagonistic and unproductive relationship between the two parties. I extend Jarvie's (1992) work by developing themes from his scholarship and applying them to a case study on the Uruguay Round. I review the literature on the media-cultural imperialism thesis and focus on Herbert Schiller's (1969 [1992], 1976, 1989) scholarship. Schiller's thesis implies that outcomes in international relations are dictated by domestic determinants such as the influence of corporate lobbyists. However, I argue that the reasons why Hollywood lost lie not in domestic determinants alone, but in a broader perspective (derived from the discipline of international relations) that focuses on the interaction between domestic trade politics and international relations (Putnam, 1988 [1993]). Putnam characterises international negotiations as an interactive process involving the bargaining between negotiators and the separate discussions each delegation has with constituents in its domestic market on the ratification of the agreement. I assess themes from Jarvie's work and propositions from Schiller's thesis using Putnam's (1988 [1993]) two-level analysis and empirical evidence from primary documents and thirty-five interviews conducted over a three-year period (1994 to 1997) with U.S. and European negotiators and film executives. I argue that U.S. domestic trade politics hampered efforts by U.S. negotiators to reach a bilateral accord on audiovisual services and IPRs related to copyright because of linkages forged by EU Member States between progress in those talks and progress in talks on agriculture, maritime transport services, geographic indications related to wines and anti-dumping. A second obstacle to a bilateral accord was an influential hawkish minority of the Hollywood lobby, who set an aggressive agenda for U.S. negotiators and set off a chain reaction in the final moments of the Round that led to Hollywood's defeat. Finally, I present an alternative scenario to the argument (cf. Waregne, 1994; Dehousse and Havelange, 1994; Joachimowicz and Berenboom, 1994) that the French government dictated the outcome of the audiovisual services and IPRs negotiations. My scenario emphasises the preeminent status of the General Affairs Council, the role of EU Member States other than France, and Commission efforts to forge a bilateral deal. In the end, the hawks dictated the outcome of the audiovisual services talks, while a majority of EU Member States dictated the outcome of the talks on IPRs related to copyright.
27
Khazan, Roger Igor. "A one-round algorithm for virtually synchronous group communication in wide area networks." Thesis, Massachusetts Institute of Technology, 2002. http://hdl.handle.net/1721.1/29235.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2002.Includes bibliographical references (p. 159-165).
Group communication services, and especially those that implement Virtual Synchrony semantics, are powerful middleware systems that facilitate the development of fault-tolerant distributed applications. In this thesis, we present a high quality, theoretical design of a group communication service that implements Virtual Synchrony semantics and is aimed for deployment in wide-area networks (WANs). The design features a novel algorithm for implementing Virtual Synchrony semantics; the algorithm is more appropriate for WANs than the existing solutions because it involves fewer rounds of communication and operates in a scalable WAN-oriented architecture. The high quality of the design refers to the level of formality and rigor at which it is done: The design includes formal and precise specifications, algorithms, correctness proofs, and performance analyses. We develop the necessary supporting theory and methodology required for producing and evaluating this design. In particular, we develop a formal, inheritance-based, methodology that supports incremental construction of specifications, models, and proofs. This methodology helps us manage the complexity of the design and makes it evident which part of the algorithm implements which property of the system. We also develop new, formal approaches in the area of performance evaluation.
by Roger I. Khazan.
Ph.D.
28
Bull, David R. "Signal processing techniques with reduced computational complexity." Thesis, Cardiff University, 1998. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.388006.
Full text
29
Li, Yunxi. "Study of low-complexity modal multiplexing for optical communication links." Thesis, University of Cambridge, 2015. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.708925.
Full text
30
Ooi, James M. 1970. "A framework for low-complexity communication over channels with feedback." Thesis, Massachusetts Institute of Technology, 1998. http://hdl.handle.net/1721.1/10050.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1998.Includes bibliographical references (p. 181-185).
by James Meng-Hsien Ooi.
Ph.D.
31
Al-Askery, Ali Jaber Abdulwahab. "Reduced complexity detection for massive MIMO-OFDM wireless communication systems." Thesis, University of Newcastle upon Tyne, 2017. http://hdl.handle.net/10443/3880.
Full textAbstract:
The aim of this thesis is to analyze the uplink massive multiple-input multipleoutput with orthogonal frequency-division multiplexing (MIMO-OFDM) communication systems and to design a receiver that has improved performance with reduced complexity. First, a novel receiver is proposed for coded massive MIMO-OFDM systems utilizing log-likelihood ratios (LLRs) derived from complex ratio distributions to model the approximate effective noise (AEN) probability density function (PDF) at the output of a zero-forcing equalizer (ZFE). These LLRs are subsequently used to improve the performance of the decoding of low-density parity-check (LDPC) codes and turbo codes. The Neumann large matrix approximation is employed to simplify the matrix inversion in deriving the PDF. To verify the PDF of the AEN, Monte-Carlo simulations are used to demonstrate the close-match fitting between the derived PDF and the experimentally obtained histogram of the noise in addition to the statistical tests and the independence verification. In addition, complexity analysis of the LLR obtained using the newly derived noise PDF is considered. The derived LLR can be time consuming when the number of receive antennas is very large in massive MIMO-OFDM systems. Thus, a reduced complexity approximation is introduced to this LLR using Newton’s interpolation with different orders and the results are compared to exact simulations. Further simulation results over time-flat frequency selective multipath fading channels demonstrated improved performance over equivalent systems using the Gaussian approximation for the PDF of the noise. By utilizing the PDF of the AEN, the PDF of the signal-to-noise ratio (SNR) is obtained. Then, the outage probability, the closed-form capacity and three approximate expressions for the channel capacity are derived based on that PDF. The system performance is further investigated by exploiting the PDF of the AEN to derive the bit error rate (BER) for the massive MIMO-OFDM system with different M-ary modulations. Then, the pairwise error probability (PEP) is derived to obtain the upper-bounds for the convolutionally coded and turbo coded massive MIMO-OFDM systems for different code generators and receive antennas. Furthermore, the effect of the fixed point data representation on the performance of the massive MIMO-OFDM systems is investigated using reduced detection implementations for MIMO detectors. The motivation for the fixed point analysis is the need for a reduced complexity detector to be implemented as an optimum massive MIMO detector with low precision. Different decomposition schemes are used to build the linear detector based on the IEEE 754 standard in addition to a user-defined precision for selected detectors. Simulations are used to demonstrate the behaviour of several matrix inversion schemes under reduced bit resolution. The numerical results demonstrate improved performance when using QR-factorization and pivoted LDLT decomposition schemes at reduced precision.
32
Urrutia, Florent. "Information theory for multi-party peer-to-peer communication protocols." Thesis, Sorbonne Paris Cité, 2018. http://www.theses.fr/2018USPCC015/document.
Full textAbstract:
Cette thèse a pour sujet les protocoles de communication peer-to-peer asynchrones. Nous introduisons deux mesures basées sur la théorie de l'information,la Public Information Complexity (PIC) et la Multi-party Information Complexity (MIC), étudions leurs propriétés et leur relation avec d'autres mesures fondamentales en calcul distribué, telles que la communication complexity et la randomness complexity. Nous utilisons ensuite ces deux mesures pour étudier la fonction parité et la fonction disjointnessThis thesis is concerned with the study of multi-party communicationprotocols in the asynchronous message-passing peer-to-peer model. We introducetwo new information measures, the Public Information Complexity(PIC) and the Multi-party Information Complexity (MIC), study their propertiesand how they are related to other fundamental quantities in distributedcomputing such as communication complexity and randomness complexity.We then use these two measures to study the parity function and the disjointness function
33
Baker, Elise, and A. Lynn Williams. "Complexity Approaches To Intervention." Digital Commons @ East Tennessee State University, 2010. https://dc.etsu.edu/etsu-works/2232.
Full textAbstract:
Book Summary: With detailed discussion and invaluable video footage of 23 treatment interventions for speech sound disorders (SSDs) in children, this textbook and DVD set should be part of every speech-language pathologist's professional preparation. Focusing on children with functional or motor-based speech disorders from early childhood through the early elementary period, this textbook gives preservice SLPs critical analyses of a complete spectrum of evidence-based phonological and articulatory interventions.
This textbook fully prepares SLPs for practice with a vivid inside look at intervention techniques in action through high-quality DVD clips large and varied collection of intervention approaches with widespread use across ages, severity levels, and populations proven interventions in three categories: direct speech production, broader contexts such as perceptual intervention, and speech movements clear explanations of the evidence behind the approaches so SLPs can evaluate them accurately contributions by well-known experts in SSDs from across the US, Canada, Australia, and the UK
An essential core text for pre-service SLPs—and an important professional resource for practicing SLPs, early interventionists, and special educators—this book will help readers make the best intervention decisions for children with speech sound disorders.
Evidence-based intervention approaches—demonstrated in DVD clips—such as: minimal pairs perceptual intervention core vocabulary stimulability treatment intervention for developmental dysarthria the psycholinguistic approach
34
Lallo, Madeline M. "Good Vibrations: Signal Complexity in Schizocosa Ethospecies." University of Cincinnati / OhioLINK, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=ucin1554215678769319.
Full text
35
Warmke, Daniel A. "Complexity, Fun, and Robots." Ohio University / OhioLINK, 2019. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1565298442450712.
Full text
36
Bonnett, John. "Communication, complexity and empire, the systemic thought of Harold Adams Innis." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 2002. http://www.collectionscanada.ca/obj/s4/f2/dsk3/ftp05/NQ66124.pdf.
Full text
37
Mohd, Salleh Lailawati. "The relationship among leadership communication competence, emotional intelligence, and cognitive complexity." Ohio : Ohio University, 2007. http://www.ohiolink.edu/etd/view.cgi?ohiou1173101143.
Full text
38
Dai, Xiaoguang, and 戴晓光. "Receiver complexity reduction of multiple-input multiple-output wireless communication systems." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2011. http://hub.hku.hk/bib/B46589508.
Full text
39
Chan, Albert M. (Albert Michael) 1975. "A framework for low-complexity iterative interference cancellation in communication systems." Thesis, Massachusetts Institute of Technology, 2004. http://hdl.handle.net/1721.1/28537.
Full textAbstract:
Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2004.Includes bibliographical references (p. 211-215).
Communication over interference channels poses challenges not present for the more traditional additive white Gaussian noise (AWGN) channels. In order to approach the information limits of an interference channel, interference mitigation techniques need to be integrated with channel coding and decoding techniques. This thesis develops such practical schemes when the transmitter has no knowledge of the channel. The interference channel model we use is described by r = Hx + w, where r is the received vector, H is an interference matrix, x is the transmitted vector of data symbols chosen from a finite set, and w is a noise vector. The objective at the receiver is to detect the most likely vector x that was transmitted based on knowledge of r, H, and the statistics of w. Communication contexts in which this general integer programming problem appears include the equalization of intersymbol interference (ISI) channels, the cancellation of multiple-access interference (MAI) in code-division multiple-access (CDMA) systems, and the decoding of multiple-input multiple-output (MIMO) systems in fading environments. We begin by introducing mode-interleaved precoding, a transmitter preceding technique that conditions an interference channel so that the pairwise error probability of any two transmit vectors becomes asymptotically equal to the pairwise error probability of the same vectors over an AWGN channel at the same signal-to-noise ratio (SNR). While mode-interleaved precoding dramatically increases the complexity of exact ML detection, we develop iterated-decision detection to mitigate this complexity problem. Iterated-decision detectors use optimized multipass algorithms to successively cancel interference from r and generate symbol
(cont.) decisions whose reliability increases monotonically with each iteration. When used in uncoded systems with mode-interleaved preceding, iterated-decision detectors asyrmptotically achieve the performance of ML detection (and thus the interference-free lower bound) with considerably lower complexity. We interpret these detectors as low-complexity approximations to message-passing algorithms. The integration of iterated-decision detectors into communication systems with coding is also developed to approach information rates close to theoretical limits. We present joint detection and decoding algorithms based on the iterated-decision detector with mode-interleaved precoding, and also develop analytic tools to predict the behavior of such systems. We discuss the use of binary codes for channels that support low information rates, and multilevel codes and lattice codes for channels that support higher information rates.
by Albert M. Chan.
Ph.D.
40
Vinyals, Marc. "Space in Proof Complexity." Doctoral thesis, KTH, Teoretisk datalogi, TCS, 2017. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-206571.
Full textAbstract:
ropositional proof complexity is the study of the resources that are needed to prove formulas in propositional logic. In this thesis we are concerned with the size and space of proofs, and in particular with the latter. Different approaches to reasoning are captured by corresponding proof systems. The simplest and most well studied proof system is resolution, and we try to get our understanding of other proof systems closer to that of resolution. In resolution we can prove a space lower bound just by showing that any proof must have a large clause. We prove a similar relation between resolution width and polynomial calculus space that lets us derive space lower bounds, and we use it to separate degree and space. For cutting planes we show length-space trade-offs. This is, there are formulas that have a proof in small space and a proof in small length, but there is no proof that can optimize both measures at the same time. We introduce a new measure of space, cumulative space, that accounts for the space used throughout a proof rather than only its maximum. This is exploratory work, but we can also prove new results for the usual space measure. We define a new proof system that aims to capture the power of current SAT solvers, and we show a landscape of length-space trade-offs comparable to those in resolution. To prove these results we build and use tools from other areas of computational complexity. One area is pebble games, very simple computational models that are useful for modelling space. In addition to results with applications to proof complexity, we show that pebble game cost is PSPACE-hard to approximate. Another area is communication complexity, the study of the amount of communication that is needed to solve a problem when its description is shared by multiple parties. We prove a simulation theorem that relates the query complexity of a function with the communication complexity of a composed function.QC 20170509
41
Brandeho, Mathieu. "New bounds for information complexity and quantum query complexity via convex optimization tools." Doctoral thesis, Universite Libre de Bruxelles, 2018. https://dipot.ulb.ac.be/dspace/bitstream/2013/277139/4/Main.pdf.
Full textAbstract:
Cette thèse rassemble trois travaux sur la complexité d'information et sur la complexité en requête quantique. Ces domaines d'études ont pour points communs les outils mathématiques pour étudier ces complexités, c'est-à-dire les problèmes d'optimisation.Les deux premiers travaux concernent le domaine de la complexité en requête quantique, en généralisant l'important résultat suivant: dans l'article cite{LMRSS11}, leurs auteurs parviennent à caractériser la complexité en requête quantique, à l'aide de la méthode par adversaire, un programme semi-définie positif introduit par A. Ambainis dans cite{Ambainis2000}. Cependant, cette caractérisation est restreinte aux modèles à temps discret, avec une erreur bornée. Ainsi, le premier travail consiste à généraliser leur résultat aux modèles à temps continu, tandis que le second travail est une démarche, non aboutie, pour caractériser la complexité en requête quantique dans le cas exact et pour erreur non bornée.Dans ce premier travail, pour caractériser la complexité en requête quantique aux modèles à temps discret, nous adaptons la démonstration des modèles à temps discret, en construisant un algorithme en requête adiabatique universel. Le principe de cet algorithme repose sur le théorème adiabatique cite{Born1928}, ainsi qu'une solution optimale du dual de la méthode par adversaire. À noter que l'analyse du temps d'exécution de notre algorithme adiabatique est basée sur preuve qui ne nécessite pas d'écart dans le spectre de l'Hamiltonien.Dans le second travail, on souhaite caractériser la complexité en requête quantique pour une erreur non bornée ou nulle. Pour cela on reprend et améliore la méthode par adversaire, avec une approche de la mécanique lagrangienne, dans laquelle on construit un Lagrangien indiquant le nombre de requêtes nécessaires pour se déplacer dans l'espace des phases, ainsi on peut définir l'``action en requête''. Or ce lagrangien s'exprime sous la forme d'un programme semi-defini, son étude classique via les équations d'Euler-Lagrange nécessite l'utilisation du théorème de l'enveloppe, un puissant outils d'économathématiques. Le dernier travail, plus éloigné, concerne la complexité en information (et par extension la complexité en communication) pour simuler des corrélations non-locales. Ou plus précisement la quantitié d'information (selon Shannon) que doive s'échanger deux parties pour obtenir ses corrélations. Dans ce but, nous définissons une nouvelle complexité, denommée la zero information complexity IC_0, via le modèle sans communication. Cette complexité a l'avantage de s'exprimer sous la forme d'une optimization convexe. Pour les corrélations CHSH, on résout le problème d'optimisation pour le cas à une seule direction où nous retrouvons un résultat connu. Pour le scénario à deux directions, on met numériquement en évidence la validité de cette borne, et on résout une forme relaxée de IC_0 qui est un nouveau résultat.Doctorat en Sciences de l'ingénieur et technologie
info:eu-repo/semantics/nonPublished
42
Kohl, Lisa Maria [Verfasser], and D. [Akademischer Betreuer] Hofheinz. "On Improving Communication Complexity in Cryptography / Lisa Maria Kohl ; Betreuer: D. Hofheinz." Karlsruhe : KIT-Bibliothek, 2019. http://d-nb.info/1201414814/34.
Full text
43
Stader, Sally. "Impacts of Complexity and Timing of Communication Interruptions on Visual Detection Tasks." Doctoral diss., University of Central Florida, 2014. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/6361.
Full textAbstract:
Auditory preemption theory suggests two competing assumptions for the attention-capturing and performance-altering properties of auditory tasks. In onset preemption, attention is immediately diverted to the auditory channel. Strategic preemption involves a decision process in which the operator maintains focus on more complex auditory messages. The limitation in this process is that the human auditory, or echoic, memory store has a limit of 2 to 5 seconds, after which the message must be processed or it decays. In contrast, multiple resource theory suggests that visual and auditory tasks may be efficiently time-shared because two different pools of cognitive resources are used. Previous research regarding these competing assumptions has been limited and equivocal. Thus, the current research focused on systematically examining the effects of complexity and timing of communication interruptions on visual detection tasks. It was hypothesized that both timing and complexity levels would impact detection performance in a multi-task environment.
Study 1 evaluated the impact of complexity and timing of communications occurring before malfunctions in an ongoing visual detection task. Twenty-four participants were required to complete each of the eight timing blocks that included simple or complex communications occurring simultaneously, and at 2, 5, or 8 seconds before detection events. For simple communications, participants repeated three pre-recorded words. However, for complex communications, they generated three words beginning with the same last letter of a word prompt. Results indicated that complex communications at two seconds or less occurring before a visual detection event significantly impacted response time with a 1.3 to 1.6 second delay compared to all the other timings. Detection accuracy for complex communication tasks under the simultaneous condition was significantly degraded compared to simple communications at five seconds or more prior to the task. This resulted in a 20% decline in detection accuracy. Additionally, participants' workload ratings for complex communications were significantly higher than simple communications.
Study 2 examined the timing of communications occurring at the corresponding seconds after the visual detection event. Twenty-four participants were randomly assigned to the communication complexity and timing blocks as in study 1. The results did not find significant performance effects of timing or complexity of communications on detection performance. However the workload ratings for the 2 and 5 second complex communication presentations were higher compared to the same simple communication conditions.
Overall, these findings support the strategic preemption assumption for well-defined, complex communications. The onset preemption assumption for simple communications was not supported. These results also suggest that the boundaries of the multiple resource theory assumption may exist up to the limits of the echoic memory store. Figures of merit for task performance under the varying levels of timing and complexity are presented. Several theoretical and practical implications are discussed.Ph.D.
Doctorate
Psychology
Sciences
Psychology; Human Factors Psychology
44
Mekhitarian, Araxi. "Reducing Software Complexity in a Distributed Publish-Subscribe system using Multicast communication." Thesis, KTH, Skolan för elektroteknik och datavetenskap (EECS), 2018. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-232120.
Full textAbstract:
Systems of distributed character are increasing in size and becoming more complex. Managing and adapting to constant changes of requirements is a challenge during the entire system development life cycle. While new functionalities are implemented, the software may change in design and may lead to poor software quality and increased system complexity. This thesis focuses on tackling the complexity issue in a distributed Electronic Warfare system used in military aircraft. The system consists of a server and several clients which acts as publishers or subscribers for different events sent in the system. The communication is based on unicast and uses a publish/subscribe pattern for the client nodes to register as publishers or subscribers to the server. The system is created to handle message passing in high rate and is sensitive for message delays. Due to this, the system is dependent on a reliable network structure with a continuous necessity for development. An implementation of a multicast prototype will be replacing the topic-specific unicast communication and the publish/subscribe registration process to the server. The system will be evaluated by a comparison of the old communication version with the new multicast implementation using software metrics. The result is to evaluate if the behavior and functionality of the distributed Electronic Warfare system change.System av distribuerad karaktär ökar i storlek och blir alltmer komplex. Att hantera och anpassa sig till ständiga kravändringar är emellertid en utmaning under hela systemets utvecklingsprocess. Medan nya funktioner implementeras kan mjukvaran ändras i design vilket kan leda till dålig programkvalitet och ökad systemkomplexitet. Denna rapport fokuserar på att hantera komplexiteten i ett distribuerat telekrigföringssystem som används i militära flygplan. Systemet består av en server och flera klienter som publicerar och prenumererar för olika typer av meddelanden som skickas i systemet. Kommunikationen baseras på enkelsändning och använder ett publish/subscribe meddelandemönster där klienterna registrerar sig som publicerare eller prenumeranter till servern. Systemet är skapat för att kunna hantera höga meddelandehastigheter och har låg tolerans för meddelandeförseningar. På grund av detta är tillförlitlighet i nätverksstrukturen ett essentiellt kvalitetsattribut då nätverket är i behov av en ständig utveckling. En prototyp av multisändning kommer att implementeras och ersätta kommunikationen baserad på enkelsändning och publish/subscribe registreringsprocessen till servern. Systemet kommer att utvärderas genom en jämförelse av den gamla kommunikationsversionen av systemet med den nya multicast-implementeringen med hjälp av mjukvarukomplexitetsmätningar. Resultatet är att utvärdera om beteendet och funktionaliteten hos det distribuerade telekrigföringssystemet ändras.
45
Sjöberg, Frank. "High speed communication on twisted-pair wires and low complexity multiuser detectors." Licentiate thesis, Luleå tekniska universitet, 1998. http://urn.kb.se/resolve?urn=urn:nbn:se:ltu:diva-18771.
Full textAbstract:
This thesis deals with two different topics: High speed communication on twisted pair wires (digital subscriber lines) and low complexity multiuser detectors. The major part of this thesis concerns a technique for high speed communication over the telephone network called Very high bit rate Digital Subscriber Line VDSL). VDSL is not standardized yet but it is intended to offer bit rates up to 52 Mbit per second on twisted-pair wires. An important problem in VDSL is crosstalk between wire pairs, especially Near End Cross Talk (NEXT). A novel duplex method, called Zipper, that mitigates NEXT is presented herein. Zipper is a flexible duplex method that has high duplex efficiency and offers compatibility with existing services. It is based on Discrete Multi Tone (DMT) modulation, and uses different subcarriers in the two different transmission directions. The method relies on an additional cyclic extension to ensure orthogonality between the transmission directions. Zipper achieves best performance when all transmitters in the access network are synchronized, but it can also operate in an asynchronous mode with only a small loss in performance. Another important issue for VDSL is the problem with Radio Frequency Interference (RFI). The copper wires can act as large antennas and hence can transmit and receive radio signals. Herein the problem of radio frequency signals interfering with VDSL systems (called RFI-ingress) is addressed. The proposed method for suppressing the RFI works in the frequency domain of the DMT-receiver and can be used by any DMT-based VDSL system. By modeling the RFI and measuring the disturbance on some unmodulated subcarriers we can extrapolate and subtract the disturbance on all the other subcarriers. For a typical scenario with an average Signal-to-Noise Ratio (SNR) of 30 dB without RFI, about 20 dB can be lost due to RFI, but with the presented RFI-canceller this SNR-loss is reduced to less than 1 dB. The last part of this thesis deals with low complexity multiuser detection in a direct sequence code division multiple access system. The Maximum Likelihood Sequence Detector (MLSD) gives very good performance but is known to be very computationally complex. The detector presented herein is a simple threshold detector that makes MLSD-decisions on some, but not necessarily all, bits. A pipelined structure of the detector is presented which is attractive from an implementation point of view, since it allows parallel processing of the data. Using a single-user matched filter detector as post processor, taking care of the previously undetected bits, a complete multiuser detector with very low complexity is achieved. This detector gives better performance than the decorrelator receiver for a limited number of simultaneous users, e.g. up to 25 users with a spreading factor of 127.Godkänd; 1998; 20070404 (ysko)
46
Mohd, Salleh Lailawati. "Communication Competence of Malaysian Leaders as a Function of Emotional Intelligence and Cognitive Complexity." Ohio University / OhioLINK, 2007. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1173101143.
Full text
47
Boyce, Kelsey Lewis. "Effects of Syntactic Complexity on Speech Motor Performance." BYU ScholarsArchive, 2013. https://scholarsarchive.byu.edu/etd/3417.
Full textAbstract:
This study evaluated the possible influence of linguistic demands on speech motor control by measuring articulatory movement stability during conditions of increasing grammatical complexity. There were 60 participants in three age groups: 20-30 years, 40-50 years, and 60-70 years, with equal numbers of men and women in each group. These speakers produced 10 repetitions of five different sentence or phrase conditions. These five conditions included two baseline measurements and three sentences of varying complexity. Each complexity condition had an MLU count of 23, word length of 17, syllable length of 25, and contained the phrase open boxes of pompoms. Complexity was measured by node-count and grammatical structure. Lower lip movements during production of the target phrase were used to compute the spatiotemporal index (STI), a measure of lip movement stability over 10 repetitions. It was predicted that STI would be lower (indicating greater stability) in the baseline and low complexity conditions. Comparison of complexity conditions against the baseline-counting condition demonstrated significant differences in the upper lip's STI, displacement, and velocity, as well as in vocal intensity. Speech motor differences between the grammatical complexity levels were minimal and could be attributed to several factors, such as speaking rate or semantic differences. An unexpected finding of this study was the influence of age on speech production. Participants from the 60 year-old group had significantly longer utterance duration, while those from the 20 year-old group had the highest lower lip and jaw STI values. These findings suggest that speech motor control matures even beyond young adulthood and that linguistic complexity does not appear to have a consistent effect on speech movement variables.
48
Oh, Min-seok. "Low complexity bit-level soft-decision decoding for Reed-Solomon codes." Thesis, University of Surrey, 1999. http://epubs.surrey.ac.uk/842687/.
Full textAbstract:
Reed-Solomon codes (RS codes) are an important method for achieving error-correction in communication and storage systems. However, it has proved difficult to find a soft-decision decoding method which has low complexity. Moreover, in some previous soft-decision decoding approaches, bit-level soft-decision information could not be employed fully. Even though RS codes have powerful error correction capability, this is a critical shortcoming. This thesis presents bit-level soft-decision decoding schemes for RS codes. The aim is to design a low complexity sequential decoding method based on bit-level soft- decision information approaching maximum likelihood performance. Firstly a trellis decoding scheme which gives easy implementation is introduced, since the soft-decision information can be used directly. In order to allow bit-level soft-decision, a binary equivalent code is introduced and Wolf's method is used to construct the binary-trellis from a systematic parity check matrix. Secondly, the Fano sequential decoding method is chosen, which is sub-optimal and adaptable to channel conditions. This method does not need a large amount of storage to perform an efficient trellis search. The Fano algorithm is then modified to improve the error correcting performance. Finally, further methods of complexity reduction are presented without loss of decoding performance, based on reliability-first search decoding using permutation groups for RS codes. Compared with the decoder without permutation, those schemes give a large complexity reduction and performance improvement approaching near maximum likelihood performance. In this thesis, three types of permutation, cyclic, squaring and hybrid permutation, are presented and the decoding methods using them are implemented.
49
Zhou, Li. "Low Complexity PSP-MLSE receiver for H-CPM with receive diversity." Thesis, University of Canterbury. Department of Electrical and Computer Engineering, 2009. http://hdl.handle.net/10092/4455.
Full textAbstract:
This thesis is a study of harmonized continuous phase modulation (H-CPM)
coupled with receive diversity as applied to mobile radio communication applications.
H-CPM is the modulation technique specified by the American Public Safety
Communication Official Project 25 (APCO P25) Phase 2 standards, which is focused on public safety applications. Practical implementation of an H-CPM maximum likelihood sequence estimator (MLSE) receiver requires complex reduction techniques to ensure a cost effective form. In addition, it must be able to handle a fast fading environment, which is often encountered in public safety applications. Here, the reduction of receiver complexity and the combating of fast fading situations are
investigated via MATLAB simulation.
By using tilted phase and frequency pulse truncation techniques, the
complexity of an H-CPM MLSE receiver is successfully reduced. In particular, the original 384-state receiver is first reduced to a 192-state receiver through the use of
tilted phase. Then it is further reduced to 48-states and finally to 12-states by applying frequency pulse truncation. Simulation, assuming static channels, shows that the bit
error rate (BER) performance of a 12-state receiver is essentially identical to that of a 384-state receiver, despite a 97% reduction in computational complexity.
To take into account the effects of fading, channel gain estimation via persurvivor processing (PSP) is incorporated into the reduced complexity MLSE receiver. Using a weighted-sum approach to the PSP gain estimates, it was found that
at Doppler shifts of 5 Hz, 40 Hz and 80 Hz, the receiver performance was comparable to that obtainable by rival techniques. To further reduce the effect of fading, receive diversity combining was investigated, where a three-antenna diversity scheme
is applied to the reduced state PSP-based MLSE receiver. Three different combining techniques, namely selective combining (SC), equal gain combining (EGC) and maximum ratio combining (MRC) were compared. It was found via simulation that the best performance is achieved using MRC, with as much as 14dB improvement achieved by applying triple diversity MRC.
50
Kei, Chun-Ling. "Efficient complexity reduction methods for short-frame iterative decoding /." View Abstract or Full-Text, 2002. http://library.ust.hk/cgi/db/thesis.pl?ELEC%202002%20KEI.
Full textAbstract:
Thesis (M. Phil.)--Hong Kong University of Science and Technology, 2002.Includes bibliographical references (leaves 86-91). Also available in electronic version. Access restricted to campus users.