Global ETD Search

11	Applications of graph-based codes in networks: analysis of capacity and design of improved algorithms Vellambi, Badri Narayanan 25 August 2008 (has links) The conception of turbo codes by Berrou et al. has created a renewed interest in modern graph-based codes. Several encouraging results that have come to light since then have fortified the role these codes shall play as potential solutions for present and future communication problems. This work focuses on both practical and theoretical aspects of graph-based codes. The thesis can be broadly categorized into three parts. The first part of the thesis focuses on the design of practical graph-based codes of short lengths. While both low-density parity-check codes and rateless codes have been shown to be asymptotically optimal under the message-passing (MP) decoder, the performance of short-length codes from these families under MP decoding is starkly sub-optimal. This work first addresses the structural characterization of stopping sets to understand this sub-optimality. Using this characterization, a novel improved decoder that offers several orders of magnitude improvement in bit-error rates is introduced. Next, a novel scheme for the design of a good rate-compatible family of punctured codes is proposed. The second part of the thesis aims at establishing these codes as a good tool to develop reliable, energy-efficient and low-latency data dissemination schemes in networks. The problems of broadcasting in wireless multihop networks and that of unicast in delay-tolerant networks are investigated. In both cases, rateless coding is seen to offer an elegant means of achieving the goals of the chosen communication protocols. It was noticed that the ratelessness and the randomness in encoding process make this scheme specifically suited to such network applications. The final part of the thesis investigates an application of a specific class of codes called network codes to finite-buffer wired networks. This part of the work aims at establishing a framework for the theoretical study and understanding of finite-buffer networks. The proposed Markov chain-based method extends existing results to develop an iterative Markov chain-based technique for general acyclic wired networks. The framework not only estimates the capacity of such networks, but also provides a means to monitor network traffic and packet drop rates on various links of the network. Capacity Improved MP decoder LDPC codes Rateless codes Finite-buffer networks Graph-based codes Network codes Coding theory Graph theory Markov processes
12	Trapping Sets in Fountain Codes over Noisy Channels OROZCO, VIVIAN 04 November 2009 (has links) Fountain codes have demonstrated great results for the binary erasure channel and have already been incorporated into several international standards to recover lost packets at the application layer. These include multimedia broadcast/multicast sessions and digital video broadcasting on global internet-protocol. The rateless property of Fountain codes holds great promise for noisy channels. These are more sophisticated mathematical models representing errors on communications links rather than only erasures. The practical implementation of Fountain codes for these channels, however, is hampered by high decoding cost and delay. In this work we study trapping sets in Fountain codes over noisy channels and their effect on the decoding process. While trapping sets have received much attention for low-density parity-check (LDPC) codes, to our knowledge they have never been fully explored for Fountain codes. Our study takes into account the different code structure and the dynamic nature of Fountain codes. We show that 'error-free' trapping sets exist for Fountain codes. When the decoder is caught in an error-free trapping set it actually has the correct message estimate, but is unable to detect this is the case. Thus, the decoding process continues, increasing the decoding cost and delay for naught. The decoding process for rateless codes consists of one or more decoding attempts. We show that trapping sets may reappear as part of other trapping sets on subsequent decoding attempts or be defeated by the reception of more symbols. Based on our observations we propose early termination methods that use trapping set detection to obtain improvements in realized rate, latency, and decoding cost for Fountain codes. / Thesis (Master, Electrical & Computer Engineering) -- Queen's University, 2009-10-29 14:33:06.548 rateless codes Fountain codes belief propagation algorithm trapping sets Luby Transform (LT) codes LDGM codes Raptor codes early termination methods stopping criteria graph codes
13	Cooperative Communication In Store And Forward Wireless Networks Using Rateless Codes Bansal, Gaurav 05 1900 (has links) (PDF) In this thesis, we consider a cooperative relay-assisted communication system that uses rateless codes. When multiple relays are present, the relay with the highest channel gain to the source is the first to successfully decode a message from the source and forward it to the destination. Thus, the unique properties of rateless codes ensure that both rate adaptation and relay selection occur without the transmitting source or relays acquiring instantaneous channel knowledge. We show that in such cooperative systems, buffering messages at relays significantly increases throughput. We develop a novel analysis of these systems that combines the communication-theoretic aspects of cooperation over fading channels with the queuing-theoretic aspects associated with buffering. Closed-form expressions are derived for the throughput and end-to-end delay for the general case in which the channels between various nodes are not statistically identical. Results are also shown for the benchmark system that does not buffer messages. Though relay selection combined with buffering of messages at the relays substantially increases the throughput of a cooperative network, it also increases the end-to-end delays due to the additional queuing delays at the relay nodes. In order to overcome this, we propose a novel method that exploits a unique property of rateless codes that enables a receiver to decode a message from non-contiguous and unordered portions of the received signal. In it, each relay, depending on its queue length, ignores its received coded bits with a given probability. We show that this substantially reduces the end-to-end delays while retaining almost all of the throughput gain achieved by buffering. In effect, the method increases the odds that the message is first decoded by a relay with a smaller queue. Thus, the queuing load is balanced across the relays and traded off with transmission times. We derive conditions for the stability of this system when the various channels undergo fading. Despite encountering analytically intractable G/GI/1 queues in our system, we also gain insights about the method by analyzing a similar system with a simpler model for the relay-to-destination transmission times. Next we combine the single relay selection scheme at the source with physical layer power control at the relays (due to the diversity provided by the rateless codes, power control at the source is not needed). We derive an optimal power control policy that minimizes the relay to destination transmission time. Due to its computational and implementation complexity, we develop another heuristic easily implementable near optimal policy. In this policy, power allocated turns out to be inversely proportional to the square root of channel gain. We also see that this policy performs better than the channel inversion policy. Our power control solution substantially decreases the mean end-to-end delays with a marginal increase in throughput also. Finally, we combine bit dropping with power control at the relays which further improves the system performance. Wireless Communication Networks Cooperative Relay-Assisted Communication Queued Cooperative Communication Rateless Codes Relay Load Balancing Relays - Power Control Queued Cooperative Wireless Networks Cooperative System Buffered Relays Communication Engineering
14	Wireless Broadcasting with Network Coding Lu, Lu January 2011 (has links) Wireless digital broadcasting applications such as digital audio broadcast (DAB) and digital video broadcast (DVB) are becoming increasingly popular since the digital format allows for quality improvements as compared to traditional analogue broadcast. The broadcasting is commonly based on packet transmission. In this thesis, we consider broadcasting over packet erasure channels. To achieve reliable transmission, error-control schemes are needed. By carefully designing the error-control schemes, transmission efficiency can be improved compared to traditiona lautomatic repeat-request (ARQ) schemes and rateless codes. Here, we first study the application of a novel binary deterministic rateless (BDR) code. Then, we focus on the design of network coding for the wireless broadcasting system, which can significantly improve the system performance compared to traditional ARQ. Both the one-hop broadcasting system and a relay-aided broadcasting system areconsidered. In the one-hop broadcasting system, we investigate the application of systematic BDR (SBDR) codes and instantaneously decodable network coding (IDNC). For the SBDR codes, we determine the number of encoded redundancy packets that guarantees high broadcast transmission efficiencies and simultaneous lowcomplexity. Moreover, with limited feedback the efficiency performance can be further improved. Then, we propose an improved network coding scheme that can asymptotically achieve the theoretical lower bound on transmission overhead for a sufficiently large number of information packets. In the relay-aided system, we consider a scenario where the relay node operates in half duplex mode, and transmissions from the BS and the relay, respectively, are over orthogonal channels. Based on random network coding, a scheduling problem for the transmissions of redundancy packets from the BS and the relay is formulated. Two scenarios; namely instantaneous feedback after each redundancy packet, and feedback after multiple redundancy packets are investigated. We further extend the algorithms to multi-cell networks. Besides random network coding, IDNC based schemes are proposed as well. We show that significant improvements in transmission efficiency are obtained as compared to previously proposed ARQ and network-coding-based schemes. / QC 20110907 wireless broadcasting relay-aided system random network coding instantaneously decodable network coding Engineering and Technology Teknik och teknologier
15	Modern Error Control Codes and Applications to Distributed Source Coding Sartipi, Mina 15 August 2006 (has links) This dissertation first studies two-dimensional wavelet codes (TDWCs). TDWCs are introduced as a solution to the problem of designing a 2-D code that has low decoding- complexity and has the maximum erasure-correcting property for rectangular burst erasures. The half-rate TDWCs of dimensions N<sub>1</sub> X N<sub>2</sub> satisfy the Reiger bound with equality for burst erasures of dimensions N<sub>1</sub> X N<sub>2</sub>/2 and N<sub>1</sub>/2 X N<sub>2</sub>, where GCD(N<sub>1</sub>,N<sub>2</sub>) = 2. Examples of TDWC are provided that recover any rectangular burst erasure of area N<sub>1</sub>N<sub>2</sub>/2. These lattice-cyclic codes can recover burst erasures with a simple and efficient ML decoding. This work then studies the problem of distributed source coding for two and three correlated signals using channel codes. We propose to model the distributed source coding problem with a set of parallel channel that simplifies the distributed source coding to de- signing non-uniform channel codes. This design criterion improves the performance of the source coding considerably. LDPC codes are used for lossless and lossy distributed source coding, when the correlation parameter is known or unknown at the time of code design. We show that distributed source coding at the corner point using LDPC codes is simplified to non-uniform LDPC code and semi-random punctured LDPC codes for a system of two and three correlated sources, respectively. We also investigate distributed source coding at any arbitrary rate on the Slepian-Wolf rate region. This problem is simplified to designing a rate-compatible LDPC code that has unequal error protection property. This dissertation finally studies the distributed source coding problem for applications whose wireless channel is an erasure channel with unknown erasure probability. For these application, rateless codes are better candidates than LDPC codes. Non-uniform rateless codes and improved decoding algorithm are proposed for this purpose. We introduce a reliable, rate-optimal, and energy-efficient multicast algorithm that uses distributed source coding and rateless coding. The proposed multicast algorithm performs very close to network coding, while it has lower complexity and higher adaptability. Multicast Rateless codes Wyner-Ziv limit Reiger bound Error control coding Wavelet two-dimensionl codes Lossy distributed source coding Slepian-Wolf limit Distributed source coding Coding theory Multicasting (Computer networks)
16	Coding for wireless ad-hoc and sensor networks: unequal error protection and efficient data broadcasting Rahnavard, Nazanin 27 August 2007 (has links) This thesis investigates both theoretical and practical aspects of the design and analysis of modern error-control coding schemes, namely low-density parity-check (LDPC) codes and rateless codes for unequal error protection (UEP). It also studies the application of modern error-control codes in efficient data dissemination in wireless ad-hoc and sensor networks. Two methodologies for the design and analysis of UEP-LDPC codes are proposed. For these proposed ensembles, density evolution formulas over the binary erasure channel are derived and used to optimize the degree distribution of the codes. Furthermore, for the first time, rateless codes that can provide UEP are developed. In addition to providing UEP, the proposed codes can be used in applications for which unequal recovery time is desirable, i.e., when more important parts of data are required to be recovered faster than less important parts. Asymptotic behavior of the UEP-rateless codes under the iterative decoding is investigated. In addition, the performance of the proposed codes is examined under the maximum-likelihood decoding, when the codes have short to moderate lengths. Results show that UEP-rateless codes are able to provide very low error rates for more important bits with only a subtle loss in the performance of less important bits. Moreover, it is shown that given a target bit error rate, different parts of the information symbols can be decoded after receiving different numbers of encoded symbols. This implies that information can be recovered in a progressive manner, which is of interest in many practical applications such as media-on-demand systems. This work also explores fundamental research problems related to applying error-control coding such as rateless coding to the problem of reliable and energy-efficient broadcasting in multihop wireless ad-hoc sensor networks. The proposed research touches on the four very large fields of wireless networking, coding theory, graph theory, and percolation theory. Based on the level of information that each node has about the network topology, several reliable and energy-efficient schemes are proposed, all of which are distributed and have low complexity of implementation. The first protocol does not require any information about the network topology. Another protocol, which is more energy efficient, assumes each node has local information about the network topology. In addition, this work proposes a distributed scheme for finding low-cost broadcast trees in wireless networks. This scheme takes into account various parameters such as distances between nodes and link losses. This protocol is then extended to find low-cost multicast trees. Several schemes are extensively simulated and are compared. Efficient broadcasting Wireless sensor networks Unequal error protection Multicast Density evolution Data dissemination Rateless codes Low-density parity-check codes Modern error-control coding Wireless ad-hoc networks LT codes Raptor codes Ad hoc networks (Computer networks) Computer networks Coding theory
17	Performance evaluation and protocol design of fixed-rate and rateless coded relaying networks Nikjah, Reza 06 1900 (has links) The importance of cooperative relaying communication in substituting for, or complementing, multiantenna systems is described, and a brief literature review is presented. Amplify-and-forward (AF) and decode-and-forward (DF) relaying are investigated and compared for a dual-hop relay channel. The optimal strategy, source and relay optimal power allocation, and maximum cooperative gain are determined for the relay channel. It is shown that while DF relaying is preferable to AF relaying for strong source-relay links, AF relaying leads to more gain for strong source-destination or relay-destination links. Superimposed and selection AF relaying are investigated for multirelay, dual-hop relaying. Selection AF relaying is shown to be globally strictly outage suboptimal. A necessary condition for the selection AF outage optimality, and an upper bound on the probability of this optimality are obtained. A near-optimal power allocation scheme is derived for superimposed AF relaying. The maximum instantaneous rates, outage probabilities, and average capacities of multirelay, dual-hop relaying schemes are obtained for superimposed, selection, and orthogonal DF relaying, each with parallel channel cooperation (PCC) or repetition-based cooperation (RC). It is observed that the PCC over RC gain can be as much as 4 dB for the outage probabilities and 8.5 dB for the average capacities. Increasing the number of relays deteriorates the capacity performance of orthogonal relaying, but improves the performances of the other schemes. The application of rateless codes to DF relaying networks is studied by investigating three single-relay protocols, one of which is new, and three novel, low complexity multirelay protocols for dual-hop networks. The maximum rate and minimum energy per bit and per symbol are derived for the single-relay protocols under a peak power and an average power constraint. The long-term average rate and energy per bit, and relay-to-source usage ratio (RSUR), a new performance measure, are evaluated for the single-relay and multirelay protocols. The new single-relay protocol is the most energy efficient single-relay scheme in most cases. All the multirelay protocols exhibit near-optimal rate performances, but are vastly different in the RSUR. Several future research directions for fixed-rate and rateless coded cooperative systems, and frameworks for comparing these systems, are suggested. / Communications acknowledgment signals amplify-and-forward relaying average capacity average power constraint bit error rate cooperative gain cooperative communication decode-and-forward relaying degree of freedom direct transmission distributed space-time coding dual-hop relaying energy efficiency energy per bit energy per symbol feedback communication fixed-rate coded relaying fixed-rate codes fixed-rate coding large SNR approximation maximal ratio combining maximum achievable rates maximum likelihood multiple access channels mutual information nonconcave fractional programming numerical optimization optimal power allocation orthogonal relaying outage optimality outage probability parallel channel coding peak power constraint power allocation schemes power fairness protocol design rateless coded relaying rateless codes rate efficiency rateless coding Rayleigh fading relay-to-source usage ratio relaying networks repetition coding selection relaying single-hop communication superimposed relaying symbol error rate
18	Performance evaluation and protocol design of fixed-rate and rateless coded relaying networks Nikjah, Reza Unknown Date No description available. acknowledgment signals amplify-and-forward relaying average capacity average power constraint bit error rate cooperative gain cooperative communication decode-and-forward relaying degree of freedom direct transmission distributed space-time coding dual-hop relaying energy efficiency energy per bit energy per symbol feedback communication fixed-rate coded relaying fixed-rate codes fixed-rate coding large SNR approximation maximal ratio combining maximum achievable rates maximum likelihood multiple access channels mutual information nonconcave fractional programming numerical optimization optimal power allocation orthogonal relaying outage optimality outage probability parallel channel coding peak power constraint power allocation schemes power fairness protocol design rateless coded relaying rateless codes rate efficiency rateless coding Rayleigh fading relay-to-source usage ratio relaying networks repetition coding selection relaying single-hop communication superimposed relaying symbol error rate

Search results