In this thesis, we extend applications of Low-Density Parity-Check (LDPC) codes to a combination of constituent sub-channels, which is a mixture of Gaussian channels with erasures. This model, for example, represents a common channel in magnetic recordings where thermal asperities in the system are detected and represented at the decoder as erasures. Although this channel is practically useful, we cannot find any previous work that evaluates performance of LDPC codes over this channel. We are also interested in practical issues such as designing robust LDPC codes for the mixture channel and predicting performance variations due to erasure patterns (random and burst), and finite block lengths. On time varying channels, a common error control strategy is to adapt the coding rate according to available channel state information (CSI). An effective way to realize this coding strategy is to use a single code and puncture it in a rate-compatible fashion, a so-called rate-compatible punctured code (RCPC). We are interested in the existence of good puncturing patterns for rate-changes that minimize performance loss. We show the existence of good puncturing patterns with analysis and verify the results with simulations. Universality of a channel code across a broad range of coding rates is a theoretically interesting topic. We are interested in the possibility of using the puncturing technique proposed in this thesis for designing universal LDPC codes. We also consider how to design high rate LDPC codes by puncturing low rate LDPC codes. The new design method can take advantage of longer effect block lengths, sparser parity-check matrices, and larger minimum distances of low rate LDPC codes.

<p dir="ltr">We study the communication model with perfect feedback considered by Berlekamp (PhD Thesis, 1964), in which Alice wishes to communicate a binary message to Bob through a noisy adversarial channel, and has the ability to receive feedback from Bob via an additional noiseless channel. Berlekamp showed that in this model one can tolerate 1/3 fraction of errors (a.k.a., bit-flips or substitutions) with non-vanishing communication rate, which strictly improves upon the 1/4 error rate that is tolerable in the classical one-way communication setting without feedback. In the case when the channel is corrupted by erasures, it is easy to show that a fraction of erasures tending to 1 can be tolerated in the noiseless feedback setting, which also beats the 1/2 fraction that is maximally correctable in the no-feedback setting. In this thesis, we consider a more general perfect feedback channel that may introduce both errors and erasures. We show the following results:</p><p dir="ltr">1. If α, β ∈ [0, 1) are such that 3α + β < 1, then there exists a code that achieves a positive communication rate tolerating α fraction of errors and β fraction of erasures. Furthermore, no code can achieve a positive-rate in this channel when 3α + β ≥ 1.</p><p dir="ltr">2. For the case when 3α + β < 1, we compute the maximal asymptotic communication rate achievable in this setting.</p>

Thesis (MScEng)--Stellenbosch University, 2014. / ENGLISH ABSTRACT: The discovery of sparse graph codes, used in forward error correction strate- gies, has had an unrivaled impact on Information theory over the past decade. A recent advancement in this field, called Fountain codes, have gained much attention due to its intelligent rate adaptivity, and lend itself to applications such as multicasting and broadcasting networks. These particular properties can be considered valuable in a wireless sensor network setting as it is capable of providing forward error correction, and the added conceptual network protocol related extensions. A wireless sensor network testbed in France, called SensLAB, provides an experimental facility for researchers to develop and evaluate sensor network protocols, aside from a simulation environment. Tremendous value can be added to the SensLAB community if an appropriate forward error correction design, such as Fountain codes, is deemed feasible for use on such a platform. This thesis investigates the use of Fountain codes, in a binary erasure channel environment, as a forward error correction strategy for the distribution of reliable data content over the SensLAB platform. A short message length LT code using two different decoding mechanisms were developed and evaluated for possible implementation. Furthermore, a short message length Raptor code was developed by using supplementary theory and optimisation techniques that permit scalability in terms of the message size. The results favoured the Raptor code design as it performs close to near optimal while still satisfying the rateless- and universality property, at low computational complexity. / AFRIKAANSE OPSOMMING: Die ontdekking van yl-grafiekkodes, van toepassing op foutkorreksie strategieë, het onlangs 'n ongeewenaarde impak op Informasieteorie gehad. In 'n onlangse vooruitgang in hierdie veld, genoem Fonteinkodes, word daar meer fokus geplaas op die intelligente tempo aanpassingsvermoë van hierdie kodes, wat nuttige toepassing kan inhou in multi-saai- en uitsaai netwerke. Hierdie eienskappe kan moontlik as waardevol beskou word in draadlose sensor netwerke weens die fout regstellingsvermoë en die bykomende konseptuele netwerk protokol verwante uitbreidings. 'n Draadlose sensor netwerk toetsplatvorm in Frankryk, genoem die SensLAB, bied navorsers die geleentheid om eksperimentele sensor netwerk protokolle te ontwikkel en te toets buite 'n tipiese simulasie-omgewing. Groot waarde kan bygevoeg word aan die SensLAB gemeenskap indien 'n geskikte foutkorreksie strategie ontwikkel word, soos Fonteinkodes, en as geskik beskou kan word vir hierdie platvorm. In hierdie tesis word Fonteinkodes saam met die SensLAB platvorm ondersoek, binne die raamwerk van 'n binêre verlieskanaal, om vir foutkorreksie oor die verspreiding van betroubare data in SensLAB op te tree. 'n Kort boodskap LT kode word voorgestel deur van twee verskillende dekoderings meganismes gebruik te maak. 'n Alternatief, genaamd Raptorkode, was ook ondersoek. 'n Raptorkode. 'n Kort boodskap Raptor kode, wat ontwikkel is met bykomende teorie en optimeringstegnieke, word ook voorgestel. Die bykomende tegnieke bied 'n skaleerbare boodskap lengte terwyl dit tempoloos en universeel bly, en lae kompleksiteit bied.

Made available in DSpace on 2016-04-28T18:23:04Z (GMT). No. of bitstreams: 1 Vera Lucia Pires.pdf: 2922868 bytes, checksum: aee07512c47b0cd256113720ea449aac (MD5) Previous issue date: 2015-06-29 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / This research focuses on the tense relationship between children and their own writing skill at school. Reading and writing are intermingled and simultaneous through the literacy process, though not coincident in their effects. The expression "tense relationship" here adopted disclaims any possibility of taking for granted that writing skills would undertake a natural trend, i.e., free from deep conflict, once the child is already a "language speaker . This argument seems not to be sustained by the serious and enigmatic problems the child has when s/he has to deal with the teaching-learning of her/s mother tongue. True enough, the effects of mentioned tension student-writing has a heterogeneous profile, which can be apprehended through the multifaceted ways of reformulating one s writings: different erasure markings and/or internal sequential unstable text rearrangements. In this sense, the present dissertation dealt with such occurrences, both from an empirical and a theoretical approach, taking into account the two initial years of Brazilian School, named Fundamental II. At such a stage, it is expected that students writings are better stabilized and with few errors. Those unwilling manifestations, from the teachers point of view, indicate that the writer has been affected by he/s own writing. This seems to be a crucial turning point in the learning process, since s/he may overcome her/s difficulty or, worse, get stuck in a doing-redoing task. From the theoretical perspective regarding language, this study is assumes the European Structuralism scientific proposal (SAUSSURE, 1916) and (JAKOBSON, 1954;1960) and follows J-C Milner s approach to those authors, and also the developments put forward by Cláudia de Lemos in the realm of Language Acquisition and Lier-DeVitto in the field of Language Pathology and Clinic. The theoretical option for that structural approach is due to the relevance they place in error, which questions the psychological subject and favors the hypothesis of the unconscious, introduced by Freud (1900). It is understood here that such a theoretical framework sheds light on the literacy process, since tension and conflict are constitutive moves in the subject-language relationship. There are three proposed structural shifts which are qualified as the child s changing of position as far as language acquisition is concerned. The child s starting point has to do with her/s (1) attachment (dependency) to the others oral or written production. In a given structural logical moment, (2) the functioning of language itself operates on the incorporated segments, producing errors and strange textual composition, which are listened to (3) when the subjective split takes place (a division between an instance who hears and another who speaks), allowing for the listening to one s own speech/writing. This is the most relevant structural position for the present study, which discusses erasures and textual rearrangements in the sphere of the child-writing relationship / Esta pesquisa focaliza a relação tensa da criança com a escrita, quando do encontro formal, escolar, com essa modalidade de linguagem. Considera-se, aqui, tanto a alfabetização, quanto a extensão e a eficácia do processo de letramento. Fiz menção a uma relação tensa para descartar qualquer possibilidade de se supor que, por ser um já falante , a entrada na escrita seria um passo natural e sem muito conflito argumento que os sérios e enigmáticos problemas escolares, decorrentes do que se concebe como ensino-aprendizagem da Língua Materna, parecem não sustentar. A tensão na relação aluno-escrita assume perfil heterogêneo, que se inscreve em formas variadas de rasuras, desordens e rearranjos sequenciais/textuais instáveis, entre outras manifestações, que serão trabalhadas nesta tese, cujo recorte destaca os dois anos iniciais do Ensino Fundamental II; períodos escolares em que já se espera uma escrita mais estabilizada e sem muitos erros ortográficos. Na maioria das vezes tais manifestações sensíveis indicam que o escrevente é afetado pelo que ele mesmo escreve. Acontece que o aluno pode ficar fixado num fazer-refazer sem saída satisfatória desse impasse frente a escrita de sua língua materna. Do ponto de vista teórico, e no que diz respeito à linguagem, esta tese aproxima-se do estruturalismo europeu (Saussure, 1916; Jakobson, 1954; 1960), conforme releitura de Milner (1978[2012], 2000[2002]) - de que se aproxima o Interacionismo em Aquisição da Linguagem (De LEMOS, 1992) e a Clínica de Linguagem (LIER-DeVITTO, 1999; 2000, 2006 e outros). A opção teórica por estas abordagens de cunho estrutural decorre da relevância nelas atribuída ao erro, que interroga a posição do sujeito no processo de aquisição da linguagem e na clínica. Tensão é parte constitutiva da relação sujeito-linguagem. Três deslocamentos estruturais são propostos e qualificados como mudanças de posição da criança: (1) em relação à fala do outro, (2) à Língua e (3) à própria fala (De LEMOS, 2002). Na terceira posição, emerge a escuta para a própria fala/escrita, posição que é da maior relevância para esta tese, que aborda os conflitos que ela pode introduzir na esfera da relação criança-escrita