Este trabalho trata de conceitos relacionados à qualidade da Energia Elétrica (EE) e, neste contexto, apresenta a proposta de técnicas para a compressão da representação de transitórios rápidos e da análise tempo-frequência de distúrbios elétricos em geral. A qualidade da Energia Elétrica é medida pelo coeficiente de desvios que os sinais de tensão e corrente apresentam em relação ao sinal senoidal ideal. Tais desvios são denominados de distúrbios, podendo ser classificados como quase estacionários (e.g. distorção de harmônicas) e eventos (e.g. transitórios rápidos). No contexto de EE, os transitórios rápidos possuem pequena duração (i.e. na ordem dos microssegundos), são detectados por altas taxas de amostragem (i.e. na ordem dos MHz) e possuem difícil parametrização. Portanto, as representações das formas de onda geralmente são armazenadas para auxiliar a avaliação subjetiva dos transitórios e dos parâmetros de interesse. Consequentemente, a compressão destas formas de onda torna-se de extrema importância para armazenar dados adquiridos por longos períodos de tempo, e estes modos de compressão são tratados nesta dissertação. Em virtude das altas taxas de amostragem utilizadas, uma técnica baseada em Análise de Componentes Principais (PCA – Principal Component Analysis) é proposta para esta representação mais compacta de transitórios. Resultados mostram que o desempenho em compressão versus qualidade de reconstrução é semelhante ao de trabalhos relacionados com a vantagem de atender aos requisitos de altas taxas de amostragem. A análise tempo-frequência é um mecanismo que auxilia na classificação e caracterização dos distúrbios elétricos. Neste trabalho, a Transformada de Hilbert-Huang é estudada e uma proposta de melhoria na Decomposição Empírica de Modos (EMD – Empirical Mode Decomposition) é apresentada. Nossos resultados mostram que a técnica proposta economiza o custo computacional se comparada com o estado da arte. Em virtude disso, a técnica proposta apresenta uma taxa de redução no tempo médio de execução de 99,76 % em relação à técnica do estado da arte. Além disso, uma verificação acerca do desempenho em eficiência de compressão versus qualidade de reconstrução de trabalhos anteriores é também desenvolvida nesta dissertação. Foi utilizada uma sistemática de avaliação experimental com base em amostras de sinais AC, de forma a avaliar as taxas de compressão atingidas pelas técnicas estudadas, como a Transformada Wavelet Discreta. Resultados mostram que a Transformada Wavelet falha para compressão de todo e qualquer tipo de distúrbio elétrico quando analisado o compromisso entre acuidade de reconstrução versus eficiência de compressão. / This work deals with concepts related to the AC Power Quality theoretical framework and, in this scope, proposes techniques for the representation of fast transient data compression and for the power line disturbances time-frequency analysis. The AC power quality is measured by the differences between actual and ideal sinusoidal voltage/current signals. These differences are known as electrical disturbances, which can be classified as quasi-stationary (e.g. harmonic distortion) or events (e.g. surge or fast transients) disturbances. In the AC Power Quality scope, the fast transients have short duration (i.e. typically on the order of microseconds), are detected by high sampling rates (i.e. typically on the order of MHz), and are hard to characterize and parameterize. Hence, the resultant representation of the waveforms is in general stored to help in the subjective evaluation of these fast transients and their parameters of interest. As a consequence the compression turns out to be of main concern, in order to store this information acquired over long periods of time (like weeks or months). In this work, a compression technique is proposed taking into account the high sampling rates. The proposed technique makes use of the Principal Component Analysis (PCA) for such compact representation of fast transients. The Compression efficiency versus reconstruction accuracy results show a similar performance for the proposed technique when compared to the related works. On the other hand, the proposed technique can handle the large amount of data provided by the high sampling rates. The time-frequency analysis helps in the classification and characterization of AC power quality disturbances. In this work, the Hilbert-Huang Transform is studied and a modification is proposed in order to improve the Empirical Mode Decomposition (EMD) performance. Our results show that the proposed modification can save computational cost when compared to the state-of-the-art. Therefore, the average execution time is reduced to 99.76 % in comparison with the state-of-the-art technique. Besides that, this work also revisits previous techniques based on the Discrete Wavelet Transform (DWT) in order to verify the trade-off between reconstruction accuracy versus compression efficiency under a more systematic experimental evaluation setup, considering samples of real AC signals. Results show that DWT fails as a general-purpose technique in AC Power Quality scope.

abstract: Fundamental limits of fixed-to-variable (F-V) and variable-to-fixed (V-F) length universal source coding at short blocklengths is characterized. For F-V length coding, the Type Size (TS) code has previously been shown to be optimal up to the third-order rate for universal compression of all memoryless sources over finite alphabets. The TS code assigns sequences ordered based on their type class sizes to binary strings ordered lexicographically. Universal F-V coding problem for the class of first-order stationary, irreducible and aperiodic Markov sources is first considered. Third-order coding rate of the TS code for the Markov class is derived. A converse on the third-order coding rate for the general class of F-V codes is presented which shows the optimality of the TS code for such Markov sources. This type class approach is then generalized for compression of the parametric sources. A natural scheme is to define two sequences to be in the same type class if and only if they are equiprobable under any model in the parametric class. This natural approach, however, is shown to be suboptimal. A variation of the Type Size code is introduced, where type classes are defined based on neighborhoods of minimal sufficient statistics. Asymptotics of the overflow rate of this variation is derived and a converse result establishes its optimality up to the third-order term. These results are derived for parametric families of i.i.d. sources as well as Markov sources. Finally, universal V-F length coding of the class of parametric sources is considered in the short blocklengths regime. The proposed dictionary which is used to parse the source output stream, consists of sequences in the boundaries of transition from low to high quantized type complexity, hence the name Type Complexity (TC) code. For large enough dictionary, the $\epsilon$-coding rate of the TC code is derived and a converse result is derived showing its optimality up to the third-order term. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2018

Este trabalho trata de conceitos relacionados à qualidade da Energia Elétrica (EE) e, neste contexto, apresenta a proposta de técnicas para a compressão da representação de transitórios rápidos e da análise tempo-frequência de distúrbios elétricos em geral. A qualidade da Energia Elétrica é medida pelo coeficiente de desvios que os sinais de tensão e corrente apresentam em relação ao sinal senoidal ideal. Tais desvios são denominados de distúrbios, podendo ser classificados como quase estacionários (e.g. distorção de harmônicas) e eventos (e.g. transitórios rápidos). No contexto de EE, os transitórios rápidos possuem pequena duração (i.e. na ordem dos microssegundos), são detectados por altas taxas de amostragem (i.e. na ordem dos MHz) e possuem difícil parametrização. Portanto, as representações das formas de onda geralmente são armazenadas para auxiliar a avaliação subjetiva dos transitórios e dos parâmetros de interesse. Consequentemente, a compressão destas formas de onda torna-se de extrema importância para armazenar dados adquiridos por longos períodos de tempo, e estes modos de compressão são tratados nesta dissertação. Em virtude das altas taxas de amostragem utilizadas, uma técnica baseada em Análise de Componentes Principais (PCA – Principal Component Analysis) é proposta para esta representação mais compacta de transitórios. Resultados mostram que o desempenho em compressão versus qualidade de reconstrução é semelhante ao de trabalhos relacionados com a vantagem de atender aos requisitos de altas taxas de amostragem. A análise tempo-frequência é um mecanismo que auxilia na classificação e caracterização dos distúrbios elétricos. Neste trabalho, a Transformada de Hilbert-Huang é estudada e uma proposta de melhoria na Decomposição Empírica de Modos (EMD – Empirical Mode Decomposition) é apresentada. Nossos resultados mostram que a técnica proposta economiza o custo computacional se comparada com o estado da arte. Em virtude disso, a técnica proposta apresenta uma taxa de redução no tempo médio de execução de 99,76 % em relação à técnica do estado da arte. Além disso, uma verificação acerca do desempenho em eficiência de compressão versus qualidade de reconstrução de trabalhos anteriores é também desenvolvida nesta dissertação. Foi utilizada uma sistemática de avaliação experimental com base em amostras de sinais AC, de forma a avaliar as taxas de compressão atingidas pelas técnicas estudadas, como a Transformada Wavelet Discreta. Resultados mostram que a Transformada Wavelet falha para compressão de todo e qualquer tipo de distúrbio elétrico quando analisado o compromisso entre acuidade de reconstrução versus eficiência de compressão. / This work deals with concepts related to the AC Power Quality theoretical framework and, in this scope, proposes techniques for the representation of fast transient data compression and for the power line disturbances time-frequency analysis. The AC power quality is measured by the differences between actual and ideal sinusoidal voltage/current signals. These differences are known as electrical disturbances, which can be classified as quasi-stationary (e.g. harmonic distortion) or events (e.g. surge or fast transients) disturbances. In the AC Power Quality scope, the fast transients have short duration (i.e. typically on the order of microseconds), are detected by high sampling rates (i.e. typically on the order of MHz), and are hard to characterize and parameterize. Hence, the resultant representation of the waveforms is in general stored to help in the subjective evaluation of these fast transients and their parameters of interest. As a consequence the compression turns out to be of main concern, in order to store this information acquired over long periods of time (like weeks or months). In this work, a compression technique is proposed taking into account the high sampling rates. The proposed technique makes use of the Principal Component Analysis (PCA) for such compact representation of fast transients. The Compression efficiency versus reconstruction accuracy results show a similar performance for the proposed technique when compared to the related works. On the other hand, the proposed technique can handle the large amount of data provided by the high sampling rates. The time-frequency analysis helps in the classification and characterization of AC power quality disturbances. In this work, the Hilbert-Huang Transform is studied and a modification is proposed in order to improve the Empirical Mode Decomposition (EMD) performance. Our results show that the proposed modification can save computational cost when compared to the state-of-the-art. Therefore, the average execution time is reduced to 99.76 % in comparison with the state-of-the-art technique. Besides that, this work also revisits previous techniques based on the Discrete Wavelet Transform (DWT) in order to verify the trade-off between reconstruction accuracy versus compression efficiency under a more systematic experimental evaluation setup, considering samples of real AC signals. Results show that DWT fails as a general-purpose technique in AC Power Quality scope.

Orientador: Guido Costa Souza de Araujo / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-08T22:09:00Z (GMT). No. of bitstreams: 1 Borin_Edson_D.pdf: 1623538 bytes, checksum: 6e51b4bb1114ccaa088f88712c601000 (MD5) Previous issue date: 2007 / Resumo: Microprogramação é uma técnica comum no projeto de unidades de controle em processadores. Além de facilitar a implementação da unidade de controle, o microcódigo pode ser modificado para adicionar novas funcionalidades ou aplicar correções a projetos já existentes. À medida que novas funcionalidades são adicionadas à CPU, a área e o consumo de energia associados ao microcódigo também aumentam. Em um projeto recente de um processador da Intel, direcionado a baixo consumo de energia e área reduzida, estimou-se que a área e o consumo de energia associados ao microcódigo corresponderiam a 20% do total do chip. Neste trabalho, investigamos a utilização de técnicas de compressão para reduzir o tamanho do microcódigo. A partir das restrições impostas no projeto de processadores de alto desempenho, fizemos uma análise qualitativa das técnicas de compressão de código e microcódigo e mostramos que a compressão de microcódigo em dois níveis é a técnica mais adequada para se comprimir o microcódigo nesses processadores. Na compressão de microcódigo em dois níveis, as microinstruções são substituídas por apontadores para dicionários que armazenam os padrões de bits extraídos do microcódigo. Os apontadores são armazenados em uma ROM denominada ¿vetor de apontadores¿ e os padrões de bits residem em ROMs distintas, denominadas ¿dicionários¿. A técnica também permite que as colunas do microcódigo sejam agrupadas em conjuntos de forma a reduzir o número de padrões de bits nos dicionários. O agrupamento de colunas similares é fundamental para minimizar o número de padrões de bits nos dicionários e, conseqüentemente, maximizar a redução do tamanho do microcódigo. A principal contribuição desta tese é um conjunto de algoritmos para agrupar as colunas do microcódigo e maximizar a compressão. Resultados experimentais, com microcódigos extraídos de processadores em produção e em estágios avançados de desenvolvimento, mostram que os algoritmos propostosmelhoram de 6% a 20% os resultados obtidos com os outros algoritmos encontrados na literatura e comprimem o microcódigo em até 50% do seu tamanho original. Ainda neste trabalho, identificamos a necessidade de se comprimir o microcódigo com restrições no número de dicionários e na quantidade de colunas por dicionário. Também provamos que, com essas restrições, o agrupamento de colunas do microcódigo é um problema NP-Completo. Por fim, propomos um algoritmo para agrupar colunas sob estas restrições. Os resultados experimentaismostram que o algoritmo proposto é capaz de produzir bons resultados de compressão / Abstract: Microprogramming is a widely known technique used to implement processor control units. Microcode makes the control unit design process easier, as it can be modified to enhance functionality and to apply patches to an existing design. As more features get added to a CPU core, the area and power costs associated with the microcode increase. In a recent Intel internal design, targeted to low power and small footprint, the area and the power consumption costs associated with the microcode approached 20% of the total die. In this work, we investigate the use of compression techniques to reduce the microcode size. Based on the constraints imposed by high performance processor design, we analyze the existing microcode and code compression techniques and show that the two level microcode compression technique is the most appropriate to compress the microcode on high performance processor. This technique replaces the original microinstructions by pointers to dictionaries that hold bit patterns extracted from the microcode. The ¿pointer arrays¿ and the ¿dictionaries¿ are ROMs that store the pointers and the bit patterns, respectively. The technique allows the microcode columns to be grouped into clusters, so that the number of bit patterns inside the dictionaries is reduced. In order to maximize the microcode compression, similar columns must be grouped together. The main contribution of this thesis is a set of algorithms to group similar microcode columns into clusters, so as to maximize the microcode size reduction. Experimental results, using microcodes from production processors and processors in advanced development stages, show that the proposed algorithms improve from 6% to 20% the compression results found by previous works and compress the microcode to 50% of its original size. We show the importance of compressing microcode under design constraints such as the number of dictionaries and the number of columns per dictionary. We also prove that, under these constraints, the problem of grouping similar columns is NP-Complete. Finally, we propose an algorithm to group similar columns under such constraints. The experimental results show that the proposed algorithm provides good compression results / Doutorado / Arquitetura de Computadores / Doutor em Ciência da Computação

Progressive mesh (PM) representation can perfectly meet the requirements of generating multi-resolutions for a detailed 3D model. This research proposes a new PM representation method to improve the PM representation storage efficiency and reduce PM generation time. In existing PM representation methods, more than 4 adjacent vertices will be stored for one vertex in the PM representation. Furthermore, the methods always use the inefficient vertex and face list representation during the generation process. In our proposed method, only three vertices are stored by using the √3 subdivision scheme and the efficient half-edge data structure replaces the vertex and face list representation. To evaluate the proposed method, a designed experiment is conducted by using three common testing 3D models. The result illustrates the improvements by comparing to other previous methods. / 0707671386

Detta är ett 10-poängs examensarbete på C-nivå, som vi under vårterminen avlagt vid Karlstads universitet. Målet med vårt projekt var att skapa ett nytt grafiskt gränssnitt till en komprimeringsalgoritm vid namn PAZ. Nuförtiden finns en hel uppsjö av grafiska gränssnitt till komprimeringsalgoritmer, men inget av dem stöder möjligheten att plugga in en egenutvecklad algoritm. Därför var vi tvungna att skapa vårt eget gränssnitt, som förutom PAZ också skulle stödja ZIP, RAR och andra etablerade algoritmer. Vi har alltså skapat ett grafiskt gränssnitt, vilket är anpassat för en implementation av den nya PAZ-algoritmen. Algoritmen har utvecklats av vår uppdragsgivare Martin Larsson. Gränssnittet har vi, i samarbete med Martin, valt att kalla för Winpaz. Vi började med att göra två prototyper, som vi bland annat delade ut till personer på universitetet för att få respons på användarvänligheten hos gränssnitten. Med utgångspunkt från resultaten av dessa tester, konstruerade vi sedan vårt slutgiltiga gränssnitt. Kravet vi hade på oss var att skapa ett användarvänligt grafiskt gränssnitt, som skulle stödja de vanligaste algoritmerna. Vi nådde målet att implementera stöd för algoritmerna ZIP och TAR. Dock fick vi göra avkall på implementationen av algoritmerna PAZ och RAR på grund av tidsbrist, men anpassade gränssnittet så att en senare inpluggning av dessa algoritmer är möjlig. Vi är nöjda med vår slutprodukt, men inser också att det troligen krävs en del ytterligare funktionalitet för att gränssnittet ska fungera exemplariskt. Under projektet har vi, förutom att vi stärkte våra kunskaper i C++-programmering, även lärt oss att använda utvecklingsverktyget wx-DevCpp. Utöver detta har vi lärt oss att programmera grafiska gränssnitt med hjälp av wxWidgets. / This is a bachelor´s project that we have been working on during a period of ten weeks, full time. The goal of our project was to design and implement a GUI for a new data compression algorithm called PAZ. At present, a vast array of compression/extraction GUIs is available, but none of them provide the possibility to incorporate a user developed algorithm. Thus, we had to create our own, with support for not only PAZ, but also ZIP, RAR, and other well known archiving algorithms. And so, we have created a GUI that is well suited for an implementation of the new PAZ algorithm. The PAZ algorithm has been developed by Martin Larsson. We chose, in collaboration with Martin, to name the GUI application Winpaz. We began by implementing two separate prototypes, which we sent out to be tested by a closed group of beta testers. The reason for this test was to investigate how to design various parts of the application to be user friendly. Using the results from the testers, we then began the development of our final version of the GUI. Our goals were to implement a user friendly GUI, that supported PAZ as well as the most widespread algorithms already in use. We achieved our first goal, to design a user friendly GUI, and we implemented support for both ZIP and TAR, but had to abandon our efforts in implementing RAR and PAZ support due to lack of time. The interface is however designed with the future incorporation of these algorithms in mind. We are fairly pleased with our work, but we also recognize the need for added functionality in order to make the GUI a commercial grade product. During this project we have, apart from broadening our knowledge and skill in C++ programming, also learned to use the IDE wxDevCpp, a powerful open source tool for developing GUI applications based on the wxWidgets framework.

The diploma thesis is focused on possibilities of spline approximation and interpolation of CAD imported by CAD Reader to control system. First chapter describes mathematical meaning of curves, the second chapter shows possibilities of approximation and interpolation in control system Sinumerik 840D and the third chapter applies these possibilities on practical example.

Tato diplomová práce se zabývá možností využití bezeztrátových kompresních algoritmů ke klasifikaci biologických sekvencí. Nejdříve je představena literární rešerše o bezeztrátových kompresních algoritmech, která byla využita k výběru slovníkového algoritmu vytvořeného A. Lempelem a J. Zivem v roce 1976 (LZ77). Tento algoritmus je běžně používán k datové kompresi a v předkládané práci byl modifikován tak, aby umožnil klasifikaci biologických sekvencí. K algoritmu byly navrženy další modifikace, které rozvíjí jeho klasifikační možnosti. V průběhu práce byla sestavena sada datasetů biologických sekvencí, která umožnila podrobné testování algoritmu. Algoritmus byl porovnán s klasickými zarovnávacími metodami: Jukes-Cantor, Tamura a Kimura. Bylo ukázáno, že algoritmus dosahuje srovnatelných výsledků v oblasti klasifikace biologických sekvencí a dokonce je u 20% datasetů překonává. Lepší výsledky dosahuje zejména u sekvencí, jež jsou si vzájemně vzdálené.

Audio data compression seeks to reduce the size of sound files, making them easier to store and transfer, and is thus a highly valued tool for those working with large sets of audio data. For example, some biologists work with audio recordings of bats, which are well known for their frequent use of ultrasonic echolocation, and so these biologists can accrue massive amounts of high frequency audio data. However, as many methods of audio compression are designed to specialize in the more common range of frequencies, they are not able to sufficiently compress bat audio, and many bat biologists instead work without compressing their data at all. This paper investigates the desiderata of a data compression method in the context of bat biology, experimentally compares several modern data compression algorithms, and discusses their pros and cons in terms of their potential use across various relevant contexts. The paper concludes by suggesting the algorithm Monkey’s Audio for machines able to handle the higher resource demands it has. Otherwise, FLAC and WavPack yield similar size reduction rates at a significantly faster speed while being less resource intensive. Of note is the interesting result produced by the algorithm 7-ZIP PPMd Solid, which achieved consistently outstanding results within a single dataset, but its generalizability has yet to be determined.

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第18405号 / 情博第520号 / 新制||情||92(附属図書館) / 31263 / 京都大学大学院情報学研究科知能情報学専攻 / (主査)教授 阿久津 達也, 教授 山本 章博, 教授 永持 仁 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM