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.

Decoding semantics across fMRI sessions with different stimulus modalities:a practical MVPA study

Both embodied and symbolic accounts of conceptual organization would predict partial sharing and partial differentiation between the neural activations seen for concepts activated via different stimulus modalities. But cross-participant and cross-session variability in BOLD activity patterns makes analyses of such patterns with MVPA methods challenging. Here, we examine the effect of cross-modal and individual variation on the machine learning analysis of fMRI data recorded during a word property generation task. We present the same set of living and non-living concepts (land-mammals, or work tools) to a cohort of Japanese participants in two sessions: the first using auditory presentation of spoken words; the second using visual presentation of words written in Japanese characters. Classification accuracies confirmed that these semantic categories could be detected in single trials, with within-session predictive accuracies of 80-90%. However cross-session prediction (learning from auditory-task data to classify data from the written-word-task, or vice versa) suffered from a performance penalty, achieving 65-75% (still individually significant at p « 0.05). We carried out several follow-on analyses to investigate the reason for this shortfall, concluding that distributional differences in neither time nor space alone could account for it. Rather, combined spatio-temporal patterns of activity need to be identified for successful cross-session learning, and this suggests that feature selection strategies could be modified to take advantage of this.

The influence on children of the purpose of experiencing reading vocabulary: encoding-retrieval interactions in word perception

This research looked at conditions which result in the development of integrated letter code information in the acquisition of reading vocabulary. Thirty grade three children of normal reading ability acquired new reading words in a Meaning Assigned task and a Letter Comparison task, and worked to increase skill for known reading words in a Copy task. The children were then assessed on their ability to identify the letters in these words. During the test each stimulus word for each child was exposed for 100 msec., after which each child reported as many of his or her letters as he or she could. Familiar words, new words, and a single letter identification task served as within subject controls. Following this, subjects were assessed for word meaning recall of the Meaning Assigned words and word reading times for words in all condi tions • The resul ts supported an episodic model of word recognition in which the overlap between the processing operations employed in encoding a word and those required when decoding it affected decoding performance. In particular, the Meaning Assigned and Copy tasks. appeared to facilitate letter code accessibility and integration in new and familiar words respectively. Performance in the Letter Comparison task, on the other hand, suggested that subjects can process the elements of a new word without integrating them into its lexical structure. It was concluded that these results favour an episodic model of word recognition.

Investigating orthographic and semantic aspects of word learning in poor comprehenders

This study compared orthographic and semantic aspects of word learning in children who differed in reading comprehension skill. Poor comprehenders and controls matched for age (9-10 years), nonverbal ability and decoding skill were trained to pronounce 20 visually presented nonwords, 10 in a consistent way and 10 in an inconsistent way. They then had an opportunity to infer the meanings of the new words from story context. Orthographic learning was measured in three ways: the number of trials taken to learn to pronounce nonwords correctly, orthographic choice and spelling. Across all measures, consistent items were easier than inconsistent items and poor comprehenders did not differ from control children. Semantic learning was assessed on three occasions, using a nonword-picture matching task. While poor comprehenders showed equivalent semantic learning to controls immediately after exposure to nonword meaning, this knowledge was not well retained over time. Results are discussed in terms of the language and reading skills of poor comprehenders and in relation to current models of reading development.

Belief propagation vs. TAP for decoding corrupted messages

We employ two different methods, based on belief propagation and TAP,for decoding corrupted messages encoded by employing Sourlas's method, where the code word comprises products of K bits selected randomly from the original message. We show that the equations obtained by the two approaches are similar and provide the same solution as the one obtained by the replica approach in some cases K=2. However, we also show that for K>=3 and unbiased messages the iterative solution is sensitive to the initial conditions and is likely to provide erroneous solutions; and that it is generally beneficial to use Nishimori's temperature, especially in the case of biased messages.

Separating the influences of prereading skills on early word and nonword reading

The essential first step for a beginning reader is to learn to match printed forms to phonological representations. For a new word, this is an effortful process where each grapheme must be translated individually (serial decoding). The role of phonological awareness in developing a decoding strategy is well known. We examined whether beginner readers recruit different skills depending on the nature of the words being read (familiar words vs. nonwords). Print knowledge, phoneme and rhyme awareness, rapid automatized naming (RAN), phonological short term memory (STM), nonverbal reasoning, vocabulary, auditory skills and visual attention were measured in 392 pre-readers aged 4 to 5 years. Word and nonword reading were measured 9 months later. We used structural equation modeling to examine the skills-reading relationship and modeled correlations between our two reading outcomes and among all pre-reading skills. We found that a broad range of skills were associated with reading outcomes: early print knowledge, phonological STM, phoneme awareness and RAN. Whereas all these skills were directly predictive of nonword reading, early print knowledge was the only direct predictor of word reading. Our findings suggest that beginner readers draw most heavily on their existing print knowledge to read familiar words.

Deconstructing phonological tasks:the contribution of stimulus and response type to the prediction of early decoding skills

Abstract Phonological tasks are highly predictive of reading development but their complexity obscures the underlying mechanisms driving this association. There are three key components hypothesised to drive the relationship between phonological tasks and reading; (a) the linguistic nature of the stimuli, (b) the phonological complexity of the stimuli, and (c) the production of a verbal response. We isolated the contribution of the stimulus and response components separately through the creation of latent variables to represent specially designed tasks that were matched for procedure. These tasks were administered to 570 6 to 7-year-old children along with standardised tests of regular word and non-word reading. A structural equation model, where tasks were grouped according to stimulus, revealed that the linguistic nature and the phonological complexity of the stimulus predicted unique variance in decoding, over and above matched comparison tasks without these components. An alternative model, grouped according to response mode, showed that the production of a verbal response was a unique predictor of decoding beyond matched tasks without a verbal response. In summary, we found that multiple factors contributed to reading development, supporting multivariate models over those that prioritize single factors. More broadly, we demonstrate the value of combining matched task designs with latent variable modelling to deconstruct the components of complex tasks.

Look before you leap : the epistemic violence that sometimes hides behind the word "inclusion"

This paper demonstrates how Indigenous Studies is controlled in some Australian universities in ways that continue the marginalisation, denigration and exploitation of Indigenous peoples. Moreover, it shows how the engagement of white notions of “inclusion” can result in the maintenance of racism, systemic marginalisation, white race privilege and radicalised subjectivity. A case study will be utilised which draws from the experience of two Indigenous scholars who were invited to be part of a panel to review one Australian university’s plan and courses in Indigenous studies. The case study offers the opportunity to destabilise the relationships between oppression and privilege and the epistemology that maintains them. The paper argues for the need to examine exactly what is being offered when universities provide opportunities for “inclusion”.

Word Segmentation for Chinese Wikipedia Using N-Gram Mutual Information

In this paper, we propose an unsupervised segmentation approach, named "n-gram mutual information", or NGMI, which is used to segment Chinese documents into n-character words or phrases, using language statistics drawn from the Chinese Wikipedia corpus. The approach alleviates the tremendous effort that is required in preparing and maintaining the manually segmented Chinese text for training purposes, and manually maintaining ever expanding lexicons. Previously, mutual information was used to achieve automated segmentation into 2-character words. The NGMI approach extends the approach to handle longer n-character words. Experiments with heterogeneous documents from the Chinese Wikipedia collection show good results.

Word-perfect Gatsby overcomes its flaws

Review of 'Gatz', Elevator Repair Company / Brisbane Powerhouse, published in The Australian, 12 May 2009.

Thai word segmentation with hidden Markov Model and decision tree

The Thai written language is one of the languages that does not have word boundaries. In order to discover the meaning of the document, all texts must be separated into syllables, words, sentences, and paragraphs. This paper develops a novel method to segment the Thai text by combining a non-dictionary based technique with a dictionary-based technique. This method first applies the Thai language grammar rules to the text for identifying syllables. The hidden Markov model is then used for merging possible syllables into words. The identified words are verified with a lexical dictionary and a decision tree is employed to discover the words unidentified by the lexical dictionary. Documents used in the litigation process of Thai court proceedings have been used in experiments. The results which are segmented words, obtained by the proposed method outperform the results obtained by other existing methods.

Improvement to Chinese information retrieval by incorporating word segmentation and query expansion

The increasing diversity of the Internet has created a vast number of multilingual resources on the Web. A huge number of these documents are written in various languages other than English. Consequently, the demand for searching in non-English languages is growing exponentially. It is desirable that a search engine can search for information over collections of documents in other languages. This research investigates the techniques for developing high-quality Chinese information retrieval systems. A distinctive feature of Chinese text is that a Chinese document is a sequence of Chinese characters with no space or boundary between Chinese words. This feature makes Chinese information retrieval more difficult since a retrieved document which contains the query term as a sequence of Chinese characters may not be really relevant to the query since the query term (as a sequence Chinese characters) may not be a valid Chinese word in that documents. On the other hand, a document that is actually relevant may not be retrieved because it does not contain the query sequence but contains other relevant words. In this research, we propose two approaches to deal with the problems. In the first approach, we propose a hybrid Chinese information retrieval model by incorporating word-based techniques with the traditional character-based techniques. The aim of this approach is to investigate the influence of Chinese segmentation on the performance of Chinese information retrieval. Two ranking methods are proposed to rank retrieved documents based on the relevancy to the query calculated by combining character-based ranking and word-based ranking. Our experimental results show that Chinese segmentation can improve the performance of Chinese information retrieval, but the improvement is not significant if it incorporates only Chinese segmentation with the traditional character-based approach. In the second approach, we propose a novel query expansion method which applies text mining techniques in order to find the most relevant words to extend the query. Unlike most existing query expansion methods, which generally select the highly frequent indexing terms from the retrieved documents to expand the query. In our approach, we utilize text mining techniques to find patterns from the retrieved documents that highly correlate with the query term and then use the relevant words in the patterns to expand the original query. This research project develops and implements a Chinese information retrieval system for evaluating the proposed approaches. There are two stages in the experiments. The first stage is to investigate if high accuracy segmentation can make an improvement to Chinese information retrieval. In the second stage, a text mining based query expansion approach is implemented and a further experiment has been done to compare its performance with the standard Rocchio approach with the proposed text mining based query expansion method. The NTCIR5 Chinese collections are used in the experiments. The experiment results show that by incorporating the text mining based query expansion with the hybrid model, significant improvement has been achieved in both precision and recall assessments.

Changing lanes : an exploration of the journey from dance through choreography to directing and the spoken word

This paper reveals a journey of theatrical exploration. It is a journey of enquiry and investigation backed by a vigorous, direct and dense professional history of creative work.