The objective of the proposed research is to compress data such as speech, audio, and images using a new re-ordering vector quantization approach that exploits the transition probability between consecutive code vectors in a signal. Vector quantization is the process of encoding blocks of samples from a data sequence by replacing every input vector from a dictionary of reproduction vectors. Shannon’s rate-distortion theory states that signals encoded as blocks of samples have a better rate-distortion performance relative to when encoded on a sample-to-sample basis. As such, vector quantization achieves a lower coding rate for a given distortion relative to scalar quantization for any given signal. Vector quantization does not take advantage of the inter-vector correlation between successive input vectors in data sequences. It has been demonstrated that real signals have significant inter-vector correlation. This correlation has led to vector quantization approaches that encode input vectors based on previously encoded vectors. Some methods have been proposed in literature to exploit the dependence between successive code vectors. Predictive vector quantization, dynamic codebook re-ordering, and finite-state vector quantization are examples of vector quantization schemes that use intervector correlation. Predictive vector quantization and finite-state vector quantization predict the reproduction vector for a given input vector by using past input vectors. Dynamic codebook re-ordering vector quantization has the same reproduction vectors as standard vector quantization. The dynamic codebook re-ordering algorithm is based on the concept of re-ordering indices whereby existing reproduction vectors are assigned new channel indices according a structure that orders the reproduction vectors in an order of increasing dissimilarity. Hence, an input vector encoded in the standard vector quantization method is transmitted through a channel with new indices such that 0 is assigned to the closest reproduction vector to the past reproduction vector. Larger index values are assigned to reproduction vectors that have larger distances from the previous reproduction vector. Dynamic codebook re-ordering assumes that the reproduction vectors of two successive vectors of real signals are typically close to each other according to a distance metric. Sometimes, two successively encoded vectors may have relatively larger distances from each other. Our likelihood codebook re-ordering vector quantization algorithm exploits the structure within a signal by exploiting the non-uniformity in the reproduction vector transition probability in a data sequence. Input vectors that have higher probability of transition from prior reproduction vectors are assigned indices of smaller values. The code vectors that are more likely to follow a given vector are assigned indices closer to 0 while the less likely are given assigned indices of higher value. This re-ordering provides the reproduction dictionary a structure suitable for entropy coding such as Huffman and arithmetic coding. Since such transitions are common in real signals, it is expected that our proposed algorithm when combined with entropy coding algorithms such binary arithmetic and Huffman coding, will result in lower bit rates for the same distortion as a standard vector quantization algorithm. The re-ordering vector quantization approach on quantized indices can be useful in speech, images, audio transmission. By applying our re-ordering approach to these data types, we expect to achieve lower coding rates for a given distortion or perceptual quality. This reduced coding rate makes our proposed algorithm useful for transmission and storage of larger image, speech streams for their respective communication channels. The use of truncation on the likelihood codebook re-ordering scheme results in much lower compression rates without significantly distorting the perceptual quality of the signals. Today, texts and other multimedia signals may be benefit from this additional layer of likelihood re-ordering compression.

In this thesis I aim to improve phrase-based statistical machine translation (PBSMT) in a number of ways by the use of text harmonization strategies. PBSMT systems are built by training statistical models on large corpora of human translations. This architecture generally performs well for languages with similar structure. If the languages are different for example with respect to word order or morphological complexity, however, the standard methods do not tend to work well. I address this problem through text harmonization, by making texts more similar before training and applying a PBSMT system. I investigate how text harmonization can be used to improve PBSMT with a focus on four areas: compounding, definiteness, word order, and unknown words. For the first three areas, the focus is on linguistic differences between languages, which I address by applying transformation rules, using either rule-based or machine learning-based techniques, to the source or target data. For the last area, unknown words, I harmonize the translation input to the training data by replacing unknown words with known alternatives. I show that translation into languages with closed compounds can be improved by splitting and merging compounds. I develop new merging algorithms that outperform previously suggested algorithms and show how part-of-speech tags can be used to improve the order of compound parts. Scandinavian definite noun phrases are identified as a problem forPBSMT in translation into Scandinavian languages and I propose a preprocessing approach that addresses this problem and gives large improvements over a baseline. Several previous proposals for how to handle differences in reordering exist; I propose two types of extensions, iterating reordering and word alignment and using automatically induced word classes, which allow these methods to be used for less-resourced languages. Finally I identify several ways of replacing unknown words in the translation input, most notably a spell checking-inspired algorithm, which can be trained using character-based PBSMT techniques. Overall I present several approaches for extending PBSMT by the use of pre- and postprocessing techniques for text harmonization, and show experimentally that these methods work. Text harmonization methods are an efficient way to improve statistical machine translation within the phrase-based approach, without resorting to more complex models.

This research focuses on the implementation of the efficient image compression system among the many potential applications of a transform imager system. The study includes implementing the image compression system using a transform imager, developing a novel image compression algorithm for the system, and improving the performance of the image compression system through efficient encoding and decoding algorithms for vector quantization. A transform imaging system is implemented using a transform imager, and the baseline JPEG compression algorithm is implemented and tested to verify the functionality and performance of the transform imager system. The computational reduction in digital processing is investigated from two perspectives, algorithmic and implementation. Algorithmically, a novel wavelet-based embedded image compression algorithm using dynamic index reordering vector quantization (DIRVQ) is proposed for the system. DIRVQ makes it possible for the proposed algorithm to achieve superior performance over the embedded zero-tree wavelet (EZW) algorithm and the successive approximation vector quantization (SAVQ) algorithm. However, because DIRVQ requires intensive computational complexity, additional focus is placed on the efficient implementation of DIRVQ, and highly efficient implementation is achieved without a compromise in performance.

Statistic machine translation to any of the resource scarce South African languages generally results in low quality output. Large amounts of training data are required to generate output of such a standard that it can ease the work of human translators when incorporated into a translation environment. Sufficiently large corpora often do not exist and other techniques must be researched to improve the quality of the output. One of the methods in international literature that yielded good improvements in the quality of the output applies syntactic reordering as pre-processing. This pre-processing aims at simplifying the decod-ing process as less changes will need to be made during translation in this stage. Training will also benefit since the automatic word alignments can be drawn more easily because the word orders in both the source and target languages are more similar. The pre-processing is applied to the source language training data as well as to the text that is to be translated. It is in the form of rules that recognise patterns in the tags and adapt the structure accordingly. These tags are assigned to the source language side of the aligned parallel corpus with a syntactic analyser. In this research project, the technique is adapted for translation from English to Afrikaans and deals with the reordering of verbs, modals, the past tense construct, construc-tions with “to” and negation. The goal of these rules is to change the English (source language) structure to better resemble the Afrikaans (target language) structure. A thorough analysis of the output of the base-line system serves as the starting point. The errors that occur in the output are divided into categories and each of the underlying constructs for English and Afrikaans are examined. This analysis of the output and the literature on syntax for the two languages are combined to formulate the linguistically motivated rules. The module that performs the pre-processing is evaluated in terms of the precision and the recall, and these two measures are then combined in the F-score that gives one number by which the module can be assessed. All three of these measures compare well to international standards. Furthermore, a compari-son is made between the system that is enriched by the pre-processing module and a baseline system on which no extra processing is applied. This comparison is done by automatically calculating two metrics (BLEU and NIST scores) and it shows very positive results. When evaluating the entire document, an increase in the BLEU score from 0,4968 to 0,5741 (7,7 %) and in the NIST score from 8,4515 to 9,4905 (10,4 %) is reported. / Thesis (M.A. (Applied Language and Literary Studies))--North-West University, Potchefstroom Campus, 2011.

Statistic machine translation to any of the resource scarce South African languages generally results in low quality output. Large amounts of training data are required to generate output of such a standard that it can ease the work of human translators when incorporated into a translation environment. Sufficiently large corpora often do not exist and other techniques must be researched to improve the quality of the output. One of the methods in international literature that yielded good improvements in the quality of the output applies syntactic reordering as pre-processing. This pre-processing aims at simplifying the decod-ing process as less changes will need to be made during translation in this stage. Training will also benefit since the automatic word alignments can be drawn more easily because the word orders in both the source and target languages are more similar. The pre-processing is applied to the source language training data as well as to the text that is to be translated. It is in the form of rules that recognise patterns in the tags and adapt the structure accordingly. These tags are assigned to the source language side of the aligned parallel corpus with a syntactic analyser. In this research project, the technique is adapted for translation from English to Afrikaans and deals with the reordering of verbs, modals, the past tense construct, construc-tions with “to” and negation. The goal of these rules is to change the English (source language) structure to better resemble the Afrikaans (target language) structure. A thorough analysis of the output of the base-line system serves as the starting point. The errors that occur in the output are divided into categories and each of the underlying constructs for English and Afrikaans are examined. This analysis of the output and the literature on syntax for the two languages are combined to formulate the linguistically motivated rules. The module that performs the pre-processing is evaluated in terms of the precision and the recall, and these two measures are then combined in the F-score that gives one number by which the module can be assessed. All three of these measures compare well to international standards. Furthermore, a compari-son is made between the system that is enriched by the pre-processing module and a baseline system on which no extra processing is applied. This comparison is done by automatically calculating two metrics (BLEU and NIST scores) and it shows very positive results. When evaluating the entire document, an increase in the BLEU score from 0,4968 to 0,5741 (7,7 %) and in the NIST score from 8,4515 to 9,4905 (10,4 %) is reported. / Thesis (M.A. (Applied Language and Literary Studies))--North-West University, Potchefstroom Campus, 2011.

This study first introduces an order-free chromosome encoding to enhance the performance of genetic algorithms by learning the linkage of building blocks in non-binary encodings. The method introduces a measure called affinity which is based on the statistical properties of gene valuations in the population. It uses the affinity values of the local and global gene pairs to construct a global permutation with tight building block positioning. Method is tested and experimental results are shown for a group of deceptive and real life test problems. Then, study proposes a gene level concurrency model where each gene position is implemented on a different process. This combines the advantages of implicit parallelism and a chromosome structure free approach. It also helps implementation of gene reordering method introduced and probably other non-linear chromosome encodings.

The work presented in this thesis discusses various formalisms for representing the addition of order-controlling and order-relaxing mechanisms to existing formal language models. An immediate example is shuffle expressions, which can represent not only all regular languages (a regular expression is a shuffle expression), but also features additional operations that generate arbitrary interleavings of its argument strings. This defines a language class which, on the one hand, does not contain all context-free languages, but, on the other hand contains an infinite number of languages that are not context-free. Shuffle expressions are, however, not themselves the main interest of this thesis. Instead we consider several formalisms that share many of their properties, where some are direct generalisations of shuffle expressions, while others feature very different methods of controlling order. Notably all formalisms that are studied here have a semi-linear Parikh image, are structured so that each derivation step generates at most a constant number of symbols (as opposed to the parallel derivations in for example Lindenmayer systems), feature interesting ordering characteristics, created either by derivation steps that may generate symbols in multiple places at once, or by multiple generating processes that produce output independently in an interleaved fashion, and are all limited enough to make the question of efficient parsing an interesting and reasonable goal. This vague description already hints towards the formalisms considered; the different classes of mildly context-sensitive devices and concurrent finite-state automata. This thesis will first explain and discuss these formalisms, and will then primarily focus on the associated membership problem (or parsing problem). Several parsing results are discussed here, and the papers in the appendix give a more complete picture of these problems and some related ones.

Os ROBDDs são estruturas utilizadas com sucesso em ferramentas de CAD para microeletrônica. Estas estruturas permitem a representação canônica de funções booleanas ao se estabelecer um ordenamento fixo de variáveis. No contexto de um gerador automático de células lógicas para circuitos integrados, os ROBDDs podem servir de base para a derivação de redes de transistores cujo comportamento elétrico equivale ao comportamento lógico de uma função booleana desejada. Nas redes de transistores derivadas de ROBDDs, o posicionamento relativo dos transistores é determinado pelo ordenamento de variáveis. O efeito do reordenamento de transistores já foi estudado na década de noventa e sabe-se de sua influência sobre características de área, atraso e potência de um circuito digital. Entretanto, estes estudos limitam-se à topologia CMOS complementar série/paralelo, que é a topologia de redes de transistores mais comum. Neste trabalho, explora-se o efeito do reordenamento de variáveis nas características de área e atraso de circuitos mapeados com seis famílias lógicas diferentes, cujas células constituem redes de transistores derivadas de ROBDDs. Em geral, os resultados dos experimentos indicam que, para estas famílias lógicas, selecionar ordenamentos, onde transistores controlados por sinais mais críticos posicionam-se relativamente mais próximos à saída da célula, pode levar ao mapeamento de circuitos com atraso 16,4% inferior, em média, ao atraso do circuito equivalente com ordenamentos selecionados para obtenção da menor área possível e ignorando-se os atrasos de chegada nas entradas de uma célula. / The ROBDDs are structures that have been successfully used in CAD tools for microelectronics. These structures allow canonical representation of boolean functions when established a fixed variable ordering. In the context of an automatic logic cell generator for integrated circuits, ROBDDs may serve as a base for deriving transistor networks from which electrical behavior is equivalent to the logic behavior of a specified boolean function. With ROBDD derived transistor networks, the relative placement of transistors is determined by variable ordering. The effect of transistor reordering was already studied in the nineties and we know about its influence over area, delay and power characteristics of an integrated circuit. However, these studies were limited to complementary series/parallel CMOS topology, which is the standard for transistor networks topology. In this work, the effect of variable reordering is explored over area and delay characteristics of circuits mapped to six different logic families, where cells are designed with ROBDD derived transistor networks. Experimental results indicate that, in general, placing transistors controlled by the most critical signals closer to cell output may lead to a circuit mapping with an average 16.4% less delay than an equivalent circuit where orderings for smallest possible area are selected and input arrival times of a cell are ignored.

Os ROBDDs são estruturas utilizadas com sucesso em ferramentas de CAD para microeletrônica. Estas estruturas permitem a representação canônica de funções booleanas ao se estabelecer um ordenamento fixo de variáveis. No contexto de um gerador automático de células lógicas para circuitos integrados, os ROBDDs podem servir de base para a derivação de redes de transistores cujo comportamento elétrico equivale ao comportamento lógico de uma função booleana desejada. Nas redes de transistores derivadas de ROBDDs, o posicionamento relativo dos transistores é determinado pelo ordenamento de variáveis. O efeito do reordenamento de transistores já foi estudado na década de noventa e sabe-se de sua influência sobre características de área, atraso e potência de um circuito digital. Entretanto, estes estudos limitam-se à topologia CMOS complementar série/paralelo, que é a topologia de redes de transistores mais comum. Neste trabalho, explora-se o efeito do reordenamento de variáveis nas características de área e atraso de circuitos mapeados com seis famílias lógicas diferentes, cujas células constituem redes de transistores derivadas de ROBDDs. Em geral, os resultados dos experimentos indicam que, para estas famílias lógicas, selecionar ordenamentos, onde transistores controlados por sinais mais críticos posicionam-se relativamente mais próximos à saída da célula, pode levar ao mapeamento de circuitos com atraso 16,4% inferior, em média, ao atraso do circuito equivalente com ordenamentos selecionados para obtenção da menor área possível e ignorando-se os atrasos de chegada nas entradas de uma célula. / The ROBDDs are structures that have been successfully used in CAD tools for microelectronics. These structures allow canonical representation of boolean functions when established a fixed variable ordering. In the context of an automatic logic cell generator for integrated circuits, ROBDDs may serve as a base for deriving transistor networks from which electrical behavior is equivalent to the logic behavior of a specified boolean function. With ROBDD derived transistor networks, the relative placement of transistors is determined by variable ordering. The effect of transistor reordering was already studied in the nineties and we know about its influence over area, delay and power characteristics of an integrated circuit. However, these studies were limited to complementary series/parallel CMOS topology, which is the standard for transistor networks topology. In this work, the effect of variable reordering is explored over area and delay characteristics of circuits mapped to six different logic families, where cells are designed with ROBDD derived transistor networks. Experimental results indicate that, in general, placing transistors controlled by the most critical signals closer to cell output may lead to a circuit mapping with an average 16.4% less delay than an equivalent circuit where orderings for smallest possible area are selected and input arrival times of a cell are ignored.

Os ROBDDs são estruturas utilizadas com sucesso em ferramentas de CAD para microeletrônica. Estas estruturas permitem a representação canônica de funções booleanas ao se estabelecer um ordenamento fixo de variáveis. No contexto de um gerador automático de células lógicas para circuitos integrados, os ROBDDs podem servir de base para a derivação de redes de transistores cujo comportamento elétrico equivale ao comportamento lógico de uma função booleana desejada. Nas redes de transistores derivadas de ROBDDs, o posicionamento relativo dos transistores é determinado pelo ordenamento de variáveis. O efeito do reordenamento de transistores já foi estudado na década de noventa e sabe-se de sua influência sobre características de área, atraso e potência de um circuito digital. Entretanto, estes estudos limitam-se à topologia CMOS complementar série/paralelo, que é a topologia de redes de transistores mais comum. Neste trabalho, explora-se o efeito do reordenamento de variáveis nas características de área e atraso de circuitos mapeados com seis famílias lógicas diferentes, cujas células constituem redes de transistores derivadas de ROBDDs. Em geral, os resultados dos experimentos indicam que, para estas famílias lógicas, selecionar ordenamentos, onde transistores controlados por sinais mais críticos posicionam-se relativamente mais próximos à saída da célula, pode levar ao mapeamento de circuitos com atraso 16,4% inferior, em média, ao atraso do circuito equivalente com ordenamentos selecionados para obtenção da menor área possível e ignorando-se os atrasos de chegada nas entradas de uma célula. / The ROBDDs are structures that have been successfully used in CAD tools for microelectronics. These structures allow canonical representation of boolean functions when established a fixed variable ordering. In the context of an automatic logic cell generator for integrated circuits, ROBDDs may serve as a base for deriving transistor networks from which electrical behavior is equivalent to the logic behavior of a specified boolean function. With ROBDD derived transistor networks, the relative placement of transistors is determined by variable ordering. The effect of transistor reordering was already studied in the nineties and we know about its influence over area, delay and power characteristics of an integrated circuit. However, these studies were limited to complementary series/parallel CMOS topology, which is the standard for transistor networks topology. In this work, the effect of variable reordering is explored over area and delay characteristics of circuits mapped to six different logic families, where cells are designed with ROBDD derived transistor networks. Experimental results indicate that, in general, placing transistors controlled by the most critical signals closer to cell output may lead to a circuit mapping with an average 16.4% less delay than an equivalent circuit where orderings for smallest possible area are selected and input arrival times of a cell are ignored.