Simplified decoding techniques for linear block codes

Error correcting codes are combinatorial objects, designed to enable reliable transmission of digital data over noisy channels. They are ubiquitously used in communication, data storage etc. Error correction allows reconstruction of the original data from received word. The classical decoding algorithms are constrained to output just one codeword. However, in the late 50’s researchers proposed a relaxed error correction model for potentially large error rates known as list decoding. The research presented in this thesis focuses on reducing the computational effort and enhancing the efficiency of decoding algorithms for several codes from algorithmic as well as architectural standpoint. The codes in consideration are linear block codes closely related to Reed Solomon (RS) codes. A high speed low complexity algorithm and architecture are presented for encoding and decoding RS codes based on evaluation. The implementation results show that the hardware resources and the total execution time are significantly reduced as compared to the classical decoder. The evaluation based encoding and decoding schemes are modified and extended for shortened RS codes and software implementation shows substantial reduction in memory footprint at the expense of latency. Hermitian codes can be seen as concatenated RS codes and are much longer than RS codes over the same aphabet. A fast, novel and efficient VLSI architecture for Hermitian codes is proposed based on interpolation decoding. The proposed architecture is proven to have better than Kötter’s decoder for high rate codes. The thesis work also explores a method of constructing optimal codes by computing the subfield subcodes of Generalized Toric (GT) codes that is a natural extension of RS codes over several dimensions. The polynomial generators or evaluation polynomials for subfield-subcodes of GT codes are identified based on which dimension and bound for the minimum distance are computed. The algebraic structure for the polynomials evaluating to subfield is used to simplify the list decoding algorithm for BCH codes. Finally, an efficient and novel approach is proposed for exploiting powerful codes having complex decoding but simple encoding scheme (comparable to RS codes) for multihop wireless sensor network (WSN) applications.

Uniformly convergent finite element methods for singularly perturbed parabolic partial differential equations

This thesis is concerned with uniformly convergent finite element methods for numerically solving singularly perturbed parabolic partial differential equations in one space variable. First, we use Petrov-Galerkin finite element methods to generate three schemes for such problems, each of these schemes uses exponentially fitted elements in space. Two of them are lumped and the other is non-lumped. On meshes which are either arbitrary or slightly restricted, we derive global energy norm and L2 norm error bounds, uniformly in the diffusion parameter. Under some reasonable global assumptions together with realistic local assumptions on the solution and its derivatives, we prove that these exponentially fitted schemes are locally uniformly convergent, with order one, in a discrete L∞norm both outside and inside the boundary layer. We next analyse a streamline diffusion scheme on a Shishkin mesh for a model singularly perturbed parabolic partial differential equation. The method with piecewise linear space-time elements is shown, under reasonable assumptions on the solution, to be convergent, independently of the diffusion parameter, with a pointwise accuracy of almost order 5/4 outside layers and almost order 3/4 inside the boundary layer. Numerical results for the above schemes are presented. Finally, we examine a cell vertex finite volume method which is applied to a model time-dependent convection-diffusion problem. Local errors away from all layers are obtained in the l2 seminorm by using techniques from finite element analysis.

Untangling unstructured programs

A method is presented for converting unstructured program schemas to strictly equivalent structured form. The predicates of the original schema are left intact with structuring being achieved by the duplication of he original decision vertices without the introduction of compound predicate expressions, or where possible by function duplication alone. It is shown that structured schemas must have at least as many decision vertices as the original unstructured schema, and must have more when the original schema contains branches out of decision constructs. The structuring method allows the complete avoidance of function duplication, but only at the expense of decision vertex duplication. It is shown that structured schemas have greater space-time requirements in general than their equivalent optimal unstructured counterparts and at best have the same requirements.

“Fiction makes a better job of the truth”: dialogism, oppositional consciousness and re-membering in the novels of Helena María Viramontes

This thesis comprises close textual analyses of Chicana author Helena María Viramontes' two published novels, Under the Feet of Jesus (1995) and Their Dogs Came With Them (2007). These analyses fall under three broad frameworks: space, time and body. Chapter One engages with the first of these frameworks, space, and explores concepts of cognitive mapping and heteroptopias. Chapter Two, which looks at time, employs theories of intertextuality and the palimpsest, while Chapter Three looks at the interrrelationship between mythology and images of the body in the texts. This study emerges five years after the publication of Viramontes' last novel, Their Dogs Came With Them, but offers fresh insight into the contribution of the author to both the Chicano literary tradition and also the U.S. canon through her critique of hegemonic power structures that suppress not only the voices of lower class ethnic citizens but also of ethnic writers. In particular, her work chastises the paucity of attention given to ethnic women writers in the U.S. This thesis reaffirms Viramontes' position as one of the most important writers living and writing in the U.S. today. It corroborates her work as a contestation against ethnic and gender suppression, and applauds the craftsmanship of her narrative style that delicately but decisively exposes the socio-political wrongs that occur in ocntemporary U.S. society.

The multiple reality: A critical study on Alfred Schutz’s sociology of the finite provinces of meaning

This work is a critical introduction to Alfred Schutz’s sociology of the multiple reality and an enterprise that seeks to reassess and reconstruct the Schutzian project. In the first part of the study, I inquire into Schutz’s biographical context that surrounds the germination of this conception and I analyse the main texts of Schutz where he has dealt directly with ‘finite provinces of meaning.’ On the basis of this analysis, I suggest and discuss, in Part II, several solutions to the shortcomings of the theoretical system that Schutz drew upon the sociological problem of multiple reality. Specifically, I discuss problems related to the structure, the dynamics, and the interrelationing of finite provinces of meaning as well as the way they relate to the questions of narrativity, experience, space, time, and identity.