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.

Repairing wireless sensor network connectivity in damaged environments

A wireless sensor network can become partitioned due to node failure, requiring the deployment of additional relay nodes in order to restore network connectivity. This introduces an optimisation problem involving a tradeoff between the number of additional nodes that are required and the costs of moving through the sensor field for the purpose of node placement. This tradeoff is application-dependent, influenced for example by the relative urgency of network restoration. In addition, minimising the number of relay nodes might lead to long routing paths to the sink, which may cause problems of data latency. This data latency is extremely important in wireless sensor network applications such as battlefield surveillance, intrusion detection, disaster rescue, highway traffic coordination, etc. where they must not violate the real-time constraints. Therefore, we also consider the problem of deploying multiple sinks in order to improve the network performance. Previous research has only parts of this problem in isolation, and has not properly considered the problems of moving through a constrained environment or discovering changes to that environment during the repair or network quality after the restoration. In this thesis, we firstly consider a base problem in which we assume the exploration tasks have already been completed, and so our aim is to optimise our use of resources in the static fully observed problem. In the real world, we would not know the radio and physical environments after damage, and this creates a dynamic problem where damage must be discovered. Therefore, we extend to the dynamic problem in which the network repair problem considers both exploration and restoration. We then add a hop-count constraint for network quality in which the desired locations can talk to a sink within a hop count limit after the network is restored. For each new problem of the network repair, we have proposed different solutions (heuristics and/or complete algorithms) which prioritise different objectives. We evaluate our solutions based on simulation, assessing the quality of solutions (node cost, movement cost, computation time, and total restoration time) by varying the problem types and the capability of the agent that makes the repair. We show that the relative importance of the objectives influences the choice of algorithm, and different speeds of movement for the repairing agent have a significant impact on performance, and must be taken into account when selecting the algorithm. In particular, the node-based approaches are the best in the node cost, and the path-based approaches are the best in the mobility cost. For the total restoration time, the node-based approaches are the best with a fast moving agent while the path-based approaches are the best with a slow moving agent. For a medium speed moving agent, the total restoration time of the node-based approaches and that of the path-based approaches are almost balanced.

Childhood obesity in Ireland: recent trends and modifiable determinants

Background: Childhood obesity is a global epidemic posing a significant threat to the health and wellbeing of children. To reverse this epidemic, it is essential that we gain a deeper understanding of the complex array of driving factors at an individual, family and wider ecological level. Using a social-ecological framework, this thesis investigates the direction, magnitude and contribution of risk factors for childhood overweight and obesity at multiple levels of influence, with a particular focus on diet and physical activity. Methods: A systematic review was conducted to describe recent trends (from 2002-2012) in childhood overweight and obesity prevalence in Irish school children from the Republic of Ireland. Two datasets (Cork Children’s Lifestyle [CCLaS] Study and the Growing Up in Ireland [GUI] Study) were used to explore determinants of childhood overweight and obesity. Individual lifestyle factors examined were diet, physical activity and sedentary behaviour. The determinants of physical activity were also explored. Family factors examined were parental weight status and household socio-economic status. The impact of food access in the local area on diet quality and body mass index (BMI) was investigated as an environmental level risk factor. Results: Between 2002 and 2012, the prevalence of childhood overweight and obesity in Ireland remained stable. There was some evidence to suggest that childhood obesity rates may have decreased slightly though one in four Irish children remained either overweight or obese. In the CCLaS study, overweight and obese children consumed more unhealthy foods than normal weight children. A diet quality score was constructed based on a previously validated adult diet score. Each one unit increase in diet quality was significantly associated with a decreased risk of childhood overweight and obesity. Individual level factors (including gender, being a member of a sports team, weight status) were more strongly associated with physical activity levels than family or environmental factors. Overweight and obese children were more sedentary and less active than normal weight children. There was a dose response relationship between time spent at moderate to vigorous physical activity (MVPA) and the risk of childhood obesity independent of sedentary time. In contrast, total sedentary time was not associated with the risk of childhood obesity independent of MVPA though screen time was associated with childhood overweight and obesity. In the GUI Study, only one in five children had 2 normal weight parents (or one normal weight parent in the case of single parent families). Having overweight and obese parents was a significant risk factor for overweight and obesity regardless of socio-economic characteristics of the household. Family income was not associated with the odds of childhood obesity but social class and parental education were important risk factors for childhood obesity. Access to food stores in the local environment did not impact dietary quality or the BMI of Irish children. However, there was some evidence to suggest that the economic resources of the family influenced diet and BMI. Discussion: Though childhood overweight and obesity rates appear to have stabilised over the previous decade, prevalence rates are unacceptably high. As expected, overweight and obesity were associated with a high energy intake and poor dietary quality. The findings also highlight strong associations between physical inactivity and the risk of overweight and obesity, with effect sizes greater than what have been typically found in adults. Important family level determinants of childhood overweight and obesity were also identified. The findings highlight the need for a multifaceted approach, targeting a range of modifiable determinants to tackle the problem. In particular, policies and interventions at the shared family environment or community level may be an effective mean of tackling this current epidemic.