This thesis presents new methods for finding optimal and near-optimal constant weight binary codes with distance d and weight w such that d=2(w-1). These methods have led to the discovery of a number of new codes which are being submitted for publication. Improvements in methods for generating lexicographic codes are also discussed, with suggestions for further research in this area.

Many modern communication networks suffer significantly from the unreliable characteristic of their nodes and links. To deal with failures, traditionally, centralized erasure codes have been extensively used to improve reliability by introducing data redundancy. In this thesis, we address several issues in implementing erasure codes in a decentralized way such that coding operations are spread to multiple nodes. Our solutions are based on fountain codes and randomized network coding, because of their capability of being amenable to decentralized implementation originated from their simplicity and randomization properties. Our contributions consist of four parts. First, we propose a novel decentralized implementation of fountain codes utilizing random walks. Our solution does not require node location information and enjoys a small local routing table with a size in proportion to the number of neighbors. Second, we introduce priority random linear codes to achieve partial data recovery by partition and encoding data into non-overlapping or overlapping subsets. Third, we present geometric random linear codes to decrease communication costs in decoding significantly, by introducing modest data redundancy in a hierarchical fashion. Finally, we study the application of network coding in disruption tolerant networks. We show that network coding achieves shorter data transmission time than replication, especially when data buffers are limited. We also propose an efficient variant of network coding based protocol, which attains similar transmission delay, but with much lower transmission costs, as compared to a protocol based on epidemic routing.

Many modern communication networks suffer significantly from the unreliable characteristic of their nodes and links. To deal with failures, traditionally, centralized erasure codes have been extensively used to improve reliability by introducing data redundancy. In this thesis, we address several issues in implementing erasure codes in a decentralized way such that coding operations are spread to multiple nodes. Our solutions are based on fountain codes and randomized network coding, because of their capability of being amenable to decentralized implementation originated from their simplicity and randomization properties. Our contributions consist of four parts. First, we propose a novel decentralized implementation of fountain codes utilizing random walks. Our solution does not require node location information and enjoys a small local routing table with a size in proportion to the number of neighbors. Second, we introduce priority random linear codes to achieve partial data recovery by partition and encoding data into non-overlapping or overlapping subsets. Third, we present geometric random linear codes to decrease communication costs in decoding significantly, by introducing modest data redundancy in a hierarchical fashion. Finally, we study the application of network coding in disruption tolerant networks. We show that network coding achieves shorter data transmission time than replication, especially when data buffers are limited. We also propose an efficient variant of network coding based protocol, which attains similar transmission delay, but with much lower transmission costs, as compared to a protocol based on epidemic routing.

We will discuss three ways to bound the chromatic number on a Cayley graph. 1. If the connection set contains information about a smaller graph, then these two graphs are related. Using this information, we will show that Cayley graphs cannot have chromatic number three. 2. We will prove a general statement that all vertex-transitive maximal triangle-free graphs on <i>n</i> vertices with valency greater than <i>n</i>/3 are 3-colourable. Since Cayley graphs are vertex-transitive, the bound of general graphs also applies to Cayley graphs. 3. Since Cayley graphs for abelian groups arise from vector spaces, we can view the connection set as a set of points in a projective geometry. We will give a characterization of all large complete caps, from which we derive that all maximal triangle-free cubelike graphs on 2ⁿ vertices and valency greater than 2ⁿ/4 are either bipartite or 4-colourable.

In wireless communication, multipath fading distorts the phase and the amplitude of received signals and increases error rate, which degrades causes communication quality. Multiple-input-multiple-output (MIMO) techniques can be adopted to achieve diversity gain and reduce error rate. However, MIMO is hard to be implemented in mobile devices due to size limitation. With this regard, cooperative communications are proposed to allow users to cooperate each other¡¦s and then achieve diversity without equipping multiple antennas. On the other hand, if source and relays adopt fixed-rate transmission under time-varying wireless channels, it requires timely feedback about channel-information for transmitters to adjust the rate of channel encoder. To reduce overhead required for aforementioned scheme, we adopt rateless fountain codes in cooperative networks. In recent year, most related studies focus on information-theoretical aspect, but it lacks discussion of practical coding. In our work, we use fountain codes in dual-hop cooperative communication and analyse transmission rate in terms of transmitting time. Fountain code was first proposed as Luby transform codes(LTC) for erasure channels. We combine low-density parity-check code( LDPC code) and LTC in cooperative communication networks, and analyze required transmission time under different cooperative protocols.

First, we proved that the - Columnwise Complementary codes is better than - Columnwise Complementary code in time selective channel by explaining the probability of happening MAI elimination in frequency domain and proposing a method to use - Columnwise Complementary codes in one cell. Furthermore, we proposed the method to increase the capability of resisting of frequency selective fading channel without decreasing the capability of resisting of time selective fading channel. Finally, we showed some simulation results about receiver velocity and MAI elimination in frequency domain.

This thesis is intended to provide several new bounding techniques for channel codes over quasi-static fading channels (QSFC). This type of channel has drawn more and more attention recently with the demanding need for higher capacity and more reliable wireless communication systems. Although there have been some published results on analyzing the performance of channel codes over QSFCs, most of them produced quite loose performance upper bounds. In this thesis, the general Gallager bounding approach which provides convergent upper bounds of coded systems over QSFCs is addressed first. It is shown that previous Gallager bounds employing trivial low SNR bounds tended to be quite loose. Then improved low instantaneous SNR bounds are derived for two classes of convolutional codes including turbo codes. Consequently, they are combined with the classical Union-Chernoff bound to produce new performance upper bounds for simple convolutional and turbo codes over single-input single-output (SISO) QSFCs. The new bound provides a much improved alternative to characterizing the performance of channel codes over QSFCs over the existing ones. Next the new bounding approach is extended to cases of serially concatenated space-time block codes, which show equivalence with SISO QSFCs. Tighter performance bounds are derived for this coding scheme for two specific cases: first a convolutional code, and later a turbo code. Finally, the more challenging cases of multiple-input multiple-output (MIMO) QSFCs are investigated. Several performance upper bounds are derived for the bit error probability of different cases of space-time trellis codes (STTC) over QSFCs using a new and tight low SNR bound. Also included in this work is an algorithm for computing the unusual information eigenvalue spectrum of STTCs.

The most popular class of quantum error correcting codes is stabilizer codes. Binary quantum stabilizer codes have been well studied, and Calderbank, Rains, Shor and Sloane (July 1998) have constructed a table of upper bounds on the minimum distance of these codes using linear programming methods. However, not much is known in the case of nonbinary stabilizer codes. In this thesis, we establish a bridge between selforthogonal classical codes over the &#64257;nite &#64257;eld containing q2 elements and quantum codes, extending and unifying previous work by Matsumoto and Uyematsu (2000), Ashikhmin and Knill (November 2001), Kim and Walker (2004). We construct a table of upper bounds on the minimum distance of the stabilizer codes using linear programming methods that are tighter than currently known bounds. Finally, we derive code construction techniques that will help us &#64257;nd new codes from existing ones. All these results help us to gain a better understanding of the theory of nonbinary stabilizer codes.

Thèse de doctorat : Télécommunications : Paris 12 : 2004. / Titre provenant de l'écran-titre.

Thèse doctorat : Traitement du signal et télécommunications : Rennes 1 : 2006. / Bibliogr. p. 197-204.