Dissertations / Theses on the topic 'Signed-digit'

Analog-to-digital converters are inevitable in the modern communication systems and there is always a need for the design of low-power converters. There are different A/D architectures to achieve medium resolution at medium speeds and among all those Cyclic/Algorithmic structure stands out due to its low hardware complexity and less die area costs. This thesis aims at discussing the ongoing trend in Cyclic/Algorithmic ADCs and their functionality. Some design techniques are studied on how to implement low power high resolution A/D converters. Also, non-ideal effects of SC implementation for Cyclic A/D converters are explored. Two kinds of Cyclic A/D architectures are compared. One is the conventional Cyclic ADC with RSD technique and the other is Cyclic ADC with Correlated Level Shift (CLS) technique. This ADC is a part of IMST Design + Systems International GmbH project work and was designed and simulated at IMST GmbH. This thesis presents the design of a 12-bit, 1 Msps, Cyclic/Algorithmic Analog-to-Digital Converter (ADC) using the “Redundant Signed Digit (RSD)” algorithm or 1.5-bit/stage architecture with switched-capacitor (SC) implementation. The design was carried out in 130nm CMOS process with a 1.5 V power supply. This ADC dissipates a power of 1.6  mW when run at full speed and works for full-scale input dynamic range. The op-amp used in the Cyclic ADC is a two-stage folded cascode structure with Class A output stage. This op-amp in typical corner dissipates 631 uW power at 1.5 V power supply and achieves a gain of 77 dB with a phase margin of 64° and a GBW of 54 MHz at 2 pF load.

The use of the discrete wavelet transform (DWT) for the JPEG2000 image compression standard has sparked interest in the design of fast, efficient hardware implementations of the perfect reconstruction filter bank used for computing the DWT. The accuracy and efficiency with which the filter coefficients are quantized in a multiplierless implementation impacts the image compression and hardware performance of the filter bank. A high precision representation ensures good compression performance, but at the cost of increased hardware resources and processing time. Conversely, lower precision in the filter coefficients results in smaller, faster hardware, but at the cost of poor compression performance. In addition to filter coefficient quantization, the filter bank structure also determines critical hardware properties such as throughput and power consumption.

This thesis first investigates filter coefficient quantization strategies and filter bank structures for the hardware implementation of the biorthogonal 9/7 wavelet filters in a traditional convolution-based filter bank. Two new filter bank propertiesâ â no-distortion-mseâ and â deviation-at-dcâ â are identified as critical to compression performance, and two new â compensatingâ filter coefficient quantization methods are developed to minimize degradation of these properties. The results indicate that the best performance is obtained by using a cascade form for the filters with coefficients quantized using the â compensating zerosâ technique. The hardware properties of this implementation are then improved by developing a cascade polyphase structure that increases throughput and decreases power consumption.

Next, this thesis investigates implementations of the lifting structureâ an orthogonal structure that is more robust to coefficient quantization than the traditional convolution-based filter bank in computing the DWT. Novel, optimal filter coefficient quantization techniques are developed for a rational and an irrational set of lifting coefficients. The results indicate that the best quantized lifting coefficient set is obtained by starting with the rational coefficient set and using a â lumped scalingâ and â gain compensationâ technique for coefficient quantization.

Finally, the image compression properties and hardware properties of the convolution and lifting based DWT implementations are compared. Although the lifting structure requires fewer computations, the cascaded arrangement of the lifting filters requires significant hardware overhead. Consequently, the results depict that the convolution-based cascade polyphase structure (with â z₁-compensatedâ coefficients) gives the best performance in terms of image compression performance and hardware metrics like throughput, latency and power consumption.

Master of Science

Nos últimos anos, os sistemas integrados em silício (SOCs - Systems-on-Chip) têm se tornado menos imunes a ruído, em decorrência dos ajustes necessários na tecnologia CMOS (Complementary Metal-Oxide-Silicon) para garantir o funcionamento dos transistores com dimensões nanométricas. Dentre tais ajustes, a redução da tensão de alimentação e da tensão de limiar (threshold) tornam os SOCs mais suscetíveis a falhas transientes, principalmente aquelas provocadas pela colisão de partículas energéticas que provêm do espaço e encontram-se presentes na atmosfera terrestre. Quando uma partícula energética de alta energia colide com o dreno de um transistor que está desligado, ela perde energia e produz pares elétron-lacuna livres, resultando em uma trilha de ionização. A ionização pode gerar um pulso transiente de tensão que pode ser interpretado como uma mudança no sinal lógico. Em um circuito combinacional, o pulso pode propagar-se até ser armazenado em um elemento de memória. Tal fenômeno é denominado Single-Event Transient (SET). Como a tendência é que as dimensões dos dispositivos fabricados com tecnologia CMOS continuem reduzindo por mais alguns anos, a ocorrência de SETs em SOCs operando na superfície terrestre tende a aumentar, exigindo a adoção de técnicas de tolerância a falhas no projeto de SOCs. O presente trabalho tem por objetivo avaliar circuitos somadores tolerantes a falhas transientes encontrados na literatura. Duas arquiteturas de somadores foram escolhidas: Ripple Carry Adder (RCA) e Binary Signed Digit Adder (BSDA). O RCA foi escolhido por ser o tipo de somador de menor custo e por isso, amplamente utilizado em SOCs. Já o BSDA foi escolhido porque utiliza o sistema numérico de dígito binário com sinal (Binary Signed Digit – BSD). Por ser um sistema de representação redundante, o uso de BSD facilita a aplicação de técnicas de tolerância a falhas baseadas em redundância de informação. Os somadores protegidos avaliados foram projetados com as seguintes técnicas: Redundância Modular Tripla (Triple Modular Redundancy - TMR) e Recomputação com Entradas e Saídas Invertidas (RESI), no caso do RCA, e codificação 1 de 3 e verificação de paridade, no caso do BSDA. As 9 arquiteturas de somadores foram simuladas no nível elétrico usando o Modelo Tecnológico Preditivo (Predictive Technology Model - PTM) de 45nm e considerando quatro comprimentos de operandos: 4, 8, 16 e 32 bits. Os resultados obtidos permitiram quantificar o número de transistores, o atraso crítico e a potência média consumida por cada arquitetura protegida. Também foram realizadas campanhas de injeção de falhas, por meio de simulações no nível elétrico, para estimar o grau de proteção de cada arquitetura. Os resultados obtidos servem para guiar os projetistas de SOCs na escolha da arquitetura de somador tolerante a falhas mais adequada aos requisitos de cada projeto.
In the past recent years, integrated systems on a chip (Systems-on-chip - SOCs) became less immune to noise due to the adjusts in CMOS technology needed to assure the operation of nanometric transistors. Among such adjusts, the reductions in supply voltage and threshold voltage make SOSs more susceptible to transient faults, mainly those provoked by the collision of charged particles coming from the outer space that are present in the atmosphere. When a heavily energy charged particle hits the drain region of a transistor that is at the off state it produces free electron-hole pairs, resulting in an ionizing track. The ionization may generate a transient voltage pulse that can be interpreted as a change in the logic signal. In a combinational circuit, the pulse may propagate up to the primary outputs and may be captured by the output storage element. Such phenomenon is referred to as Single-Event Transient (SET). Since it is expected that transistor dimensions will continue to reduce in the next technological nodes, the occurrence of SETs at Earth surface will increase and therefore, fault tolerance techniques will become a must in the design of SOSs. The present work targets the evaluation of transient fault-tolerant adders found in the literature. Two adder architectures were chosen: the Ripple-Carry Adder (RCA) and the Binary Signed Digit Adder (BSDA). The RCA was chosen because it is the least expensive and therefore, the most used architecture for SOS design. The BSDA, in turn, was chosen because it uses the Binary Signed Digit (BSD) system. As a redundant number system, the BSD paves the way to the implementation of fault-tolerant adders using information redundancy. The evaluated fault-tolerant adders were implemented by using the following techniques: Triple Module Redundancy (TMR) and Recomputing with Inverted Inputs and Outputs (RESI), in the case of the RCA, and 1 out of 3 coding and parity verification, in the case of the BSDA. A total of 9 adder architectures were simulated at the electric-level using the Predictive Technology Model (PTM) for 45nm in four different bitwidths: 4, 8, 16 and 32. The obtained results allowed for quantifying the number of transistors, critical delay and average power consumption for each fault-tolerant architecture. Fault injection campaigns were also accomplished by means of electric-level simulations to estimate the degree of protection of each architecture. The results obtained in the present work may be used to guide SOS designers in the choice of the fault-tolerant adder architecture that is most likely to satisfy the design requirements.

This M.S. thesis introduces new modulus scaling techniques for transforming a class of primes into special forms which enable efficient arithmetic. The scaling technique may be used to improve multiplication and inversion in finite fields. We present an efficient inversion algorithm that utilizes the structure of a scaled modulus. Our inversion algorithm exhibits superior performance to the Euclidean algorithm and lends itself to efficient hardware implementation due to its simplicity. Using the scaled modulus technique and our specialized inversion algorithm we develop an elliptic curve processor architecture. The resulting architecture successfully utilizes redundant representation of elements in GF(p) and provides a low-power, high speed, and small footprint specialized elliptic curve implementation. We also introduce a unified Montgomery multiplier architecture working on the extension fields GF(p), GF(2) and GF(3). With the increasing research activity for identity based encryption schemes, there has been an increasing need for arithmetic operations in field GF(3). Since we based our research on low-power and small footprint applications, we designed a unified architecture rather than having a seperate hardware for GF{3}. To the best of our knowledge, this is the first time a unified architecture was built working on three different extension fields.

Master thesis work at ITN (Department of Science and Technology) in the areas of A/D-construction and RF-circuit design. Major goal of project were to research suitable possibilities for implementations of direct conversion in transceivers operating in the 160MHz band, theoretic study followed by development of components in the construction environment Cadence. Suitable A/D- converter and other important parts were selected at the end of the theoretic study. Subsampling technique was applied to make A/D sample requirements more realistic to achieve. Besides lowering requirements on A/D-converter it allows a more simple construction, which saves more components than subsampling adds. Subsampling add extra noise, because of that an A/D-converter based on the RSD algorithm was chosen to improve error rate. To achieve high bit-processing rate compared to the used number of transistors, pipeline structure were selected as conversion method. The receiver was that part which gained largest attention because it’s the part which is most interesting to optimise. A/D-conversion is more difficult to construct than D/A conversion, besides there’s more to gain from eliminating mixers in the receiver than in the transmitter.

博士
國立清華大學
電機工程學系
91
We propose the minimally redundant signed-digit (MRSD) number system, including its subsets the asymmetric high-radix signed-digit (AHSD), the minimal redundant positive-digit (MRPD), the symmetric high-radix signed-digit (SHSD) and the binary signed-digit (BSD) number systems, for fast binary addition and multiplication, and show that the MRSD number system supports carry-free (CF) addition. The CF additions in MRSD, to be classified as fully-closed, quasi-closed and sub-closed additions, use only one redundant digit for any radix r≧2. The criterion for the existence of carry-free additions, in terms of redundancy-index and radix, is thus from tightly bounded down to loosely bounded. Novel algorithms for constructing the two-stage and three-stage CF adders (CFA) based on the MRSD number system are also presented. Moreover, if the radix is specified as r= , where m is any positive integer, the binary-to-MRSD conversion can be done in constant time regardless of the word-length. Hence, the MRSD-to-binary conversion dominates the performance of an MRSD-based arithmetic system. We also propose two efficient algorithms for converting MRSD numbers to binary ones. The first one uses a novel structure to achieve high speed, while the second one uses simple transformations and conventional additions to provide hardware reusability. These results are important since the conversion from MRSD numbers to binary ones has been considered the performance bottleneck of the MRSD-based arithmetic systems. Algorithms for converting from asymmetric high-radix signed-digit (AHSD) numbers and minimal redundant positive-digit (MRPD) numbers to binary numbers are proposed. Our approach is based on simple transformation among AHSD, MRPD, and conventional radix-r (CR) number systems. We also show that the conversion from AHSD or MRPD numbers to binary numbers can be reduced to r''s-complement addition. The result is important since the conversion from AHSD or MRPD to binary has been considered the performance bottleneck of the AHSD-based or MRPD-based arithmetic systems. We show that the AHSD-to-binary conversion is similar to the MRPD-to-binary conversion. Therefore, a good hardware architecture for any of the following three applications can be used for the other two: 1) r''s-complement addition, 2) AHSD-to-binary conversion, and 3) MRPD-to-binary conversion. In addition to performance improvement, the main contribution of this work is hardware reusability and design flexibility, so far as the involved number systems are concerned. We also show that Blair''s work is just a special case (for r=2) as discussed in this dissertation. Examples are given to demonstrate the proposed algorithms. The CF adder based on MRSD is especially suited to high-performance arithmetic with long sequences of addition-related computations performed on a massive amount of data. Practical implementations of the high-performance CF adder and array multiplier are presented. We conclude that MRSD is one of the excellent number systems to have the possibility to achieve high-performance operations with the smaller integrated circuits in high circuitry density. The conditions for the existence of various carry-free additions, performed over different digit sets with sufficient redundancy, are also concluded as loosely-bounded, Parhami''s, tightly-bounded and uppermost-bounded criteria in terms of redundancy-index and radix.

碩士
國立虎尾科技大學
資訊工程研究所
102
In 2006, Zang and Wang proposed a novel data hiding based on exploiting modification direction(EMD). This scheme can not only embed or extract the secret data simply, but also keep the excellent quality of stego-image. However, when the number of pixel-group is 2, the largest embedding capacity is 1.16 bpp and the hiding secret data rate will decrease when the number of pixels in a group increases (i.e. n increases) in the Zang-Wang scheme . In this thesis, we will proposed a new data hiding based on the modified signed digit(MSD) and exploiting modification direction(EMD). There are three major contributions in this proposed scheme. The first is only ⌈n/2⌉ pixels will be modified and the value is +1 or -1 when the group has n pixels. Secondly, the embedded capacity maintains at least 1 bpp when n is increasing. The last is the stego-image quality is better than 52 dB when the cover image''s pixels n increase. According to the experimental results, the proposed method does not only to improvement the embedding capacity but also to prevent the RS and visual-attack which were well-known steganalysis techniques. In addition, we will extend this idea to propose two schemes one is a embedding secret data randomly data hiding scheme and the other is a reversible data hiding scheme based on signed digit exploiting modification direction. According to our simulations and experiments, our proposed schem is not only to extract the secret data and recover the cover image but also to maintain good stego image quality.

碩士
國立勤益科技大學
電子工程系
100
Binary Signed-Digit (BSD) number representation has inherently carry-free (CF) addition. Hence, it is widely applied in design of parallel arithmetic and high performance processor. The structure of a BSD adder design is mainly composed of three blocks including binary-to-BSD conversion, BSD computing unit and BSD-to-binary conversion. In design of each block, we find that the binary-to-BSD conversion can be done in constant time. In addition, the performance of BSD-to-binary conversion almost dominates the whole performance of a BSD-based arithmetic system. In this thesis, a high performance BSD adder design is proposed to have the capability of on-line detection all single stuck-at fault and repairing in normal operation mode. The tree-structure two-rail code checker (TRC) is chosen in our self-checking and repair circuits design due to its simple and easier implementation. The BSD adder with self-repair capability can provides higher reliability. The validations and realizations of our design are based on TSMC 0.18μm process technology, and the experimental results have proved our design is valid and can effectively reduce the transistor count, carry propagation delay and power consumption.

碩士
東吳大學
資訊科學系
93
Point operations often need to be used in the elliptic curve cryptosystem. The number of point operations determines the efficiency of the elliptic curve cryptosystem. Thus, there are many researches for finding out how to speed up the computation of the forms of and , where k, l are scalars, and P, Q are the points over an elliptic curve. In this thesis, we propose the signed digit representation applied to twin scalars to reduce the number of non-zero digits and the joint Hamming weight, and to put non-zero digits in the same column as possible. In this thesis, the joint Hamming density is reduced to about 31% via the implementation of the signed digit representation. In the process of scalars transforming, we pre-construct a look-up table to reduce the cost of repeated computing and then use the direct formulae to reduce the number of operations in squaring, multiplication and inverse operations.

碩士
國立勤益科技大學
電子工程系
99
In this thesis, we propose a completely parallel adder design based on BSD (Binary Signed-Digit) representation. The binary signed-digit number representation has inherently carry-free property. Therefore, binary signed-digit number representation is widely used to implement parallel arithmetic and high performance processor. The thesis focuses on the key issues of parallel adder design based on binary signed-digit representation. The proposed parallel adder designs can efficiently reduce the carry propagation delay. Realization and simulation are based on both TSMC 0.35um process technology and TSMC 0.18um process technology, and the experimental results have proved our proposed structure being with high performance and reliability. The structure of a BSD adder design is mainly composed of three blocks including Binary to BSD conversion, BSD Unit and BSD to binary conversion. In design of each block, efforts are focused on functional realization, schematics design, analysis, and comparison of performance. Finally, the checking circuits are partly added for achieving higher reliability. The tree-structure two-rail code checker is chosen in our design due to its simple structure and easier implementation. It is more suitable for high bit-count design than non-tree structure two-rail code checker.

碩士
逢甲大學
資訊工程所
90
Abstract Among the four basic arithmetic operations, addition is the most frequently used one. Therefore, a Micro-controller with a high performance addition unit can have better performance than a Micro-controller with a slow one. CLA (Carry-Lookahead Adder) is an important high-performance adder. Because of the circuits of carry prediction, CLA has small carry propagation delay. SDA (Signed-Digit Adder) is another high-performance adder. SDA is a parallel adder, and is carry-propagation-free. In this paper, we focused on the two types of adders, and analyzed the performance of CLA and SDA. First, we established a power model for SDA and CLA in C language, and this power model can precisely estimate the power consumption of SDA and CLA in an efficient manner. In order to compare the estimated results with actual power consumption, we implemented the CLA and SDA with different word lengths in VHDL language, and estimated the power consumption, area, and timing by using the EDA tools on workstation. We analyzed the area and timing of these two kinds of adders according to the results. Finally, we showed a verification method by using a proposed micro-controller, RISC-sd51. We analyzed the CLA and SDA performance and established a mathematic model under the environment of RISC-sd51. From the C amd VHDL simulation results, we know that the power model can accurately calculate the power consumption. The analysis of the VHDL simulation results, we know the characteristics of the CLA and SDA. The results provide the Micro-controller designer and programmer a direction on how to design a Micro-controller and how to write assembly language.

碩士
國立清華大學
產業研發碩士積體電路設計專班
96
In recent years, digital signal processing (DSP) processors which use in many of the wireless communication systems has been requested high-performance. In this thesis, we propose the high-performance and low-cost design for Computation Sharing Programmable FIR Filter. Today, there are three kinds of methods for FIR filters design. There are common subexpression sharing/elimination method [3], [4], adder graph approach method [7], [8] and difference method [6], [11]. The most commonly used is common sub- expression sharing/elimination. The idea here is to find common patterns in the representation of the multiplier coefficients. This means that the mul- tiplier partial products can be shared. We use this concept to bring up Computation Sharing Programmable FIR Filter and then we base on this architecture to improve it. The Computation Sharing Programmable FIR Filter can replace many of the FIR Filters which is used in the DSP system for different communication specifications, and it can achieve DSP system to high efficiency. In the article, we mentioned a Computation Sharing Multiplier (CSHM) which used Canonic-Signed-Digit (CSD) representation in FIR Filter design can make high performance and low complexity in application. Beside, we improve the Programmable FIR Filter for different Pre-computer bit word lengths and give simulation analysis to validate theories. Finally, we discuss the design what are the difference about the Computation Sharing Programmable FIR Filter and use CSD representation to improve it. Finally, we discuss the difference about area, power, and timing between Computation Sharing Programmable FIR Filter using CSD representation and non-use of CSD representation.

碩士
逢甲大學
資訊工程學系
89
In the four fundamental operations of arithmetic, division is the most complicated and time consuming operation. However, in the recent years, many division algorithms have been developed which can be divided into three classes: digit recurrence, functional iteration and division by convergence. The research presented in this is based on “multiplication-based” design and use multiplication normalization to develop our division algorithm. Signed digit-adders are adopted in the addition operation of the multiplicative normalization. After the last step of the normalization, we use a carry look-ahead adder to convert the signed-digit number to a conventional number system. By taking the advantage of the signed-digit adder, we can perform any word-length divider in a fast easy manner. Because of the similarity between multiplication normalization and multiplication operation, we have proposed the principle for designing a multiplication/division fused unit. In this research, we first used the VHDL language to implement a IEEE 754 standard single precision float-point(FLP) divider and use VSS to verify its functions. Then, the VHDL code is synthesised by using Synopsys tools. Finally, Cadence CAD tool is used to generate the layout file. The layout file of the proposed FLP unit will be sent to CIC for fabrication.

碩士
逢甲大學
資訊工程學系
90
Signed-digit (SD) multiplicative normalization method is proposed to compute the reciprocal in the division-by-reciprocal algorithm. The operations in each SD normalization stage can be performed on a fast SD adder without carry propagation. Furthermore, the SD normalization method can facilitate the adoption of the SD termination algorithm. This termination algorithm can replace half of the normalization stages in the linear normalization method by a half word-length SD multiplier. The speed of the proposed divider is therefore comparable to a linear SD multiplier or just a little slower than a faster binary-tree SD multiplier at the cost of only about full word-length SD multiplier. We conclude that the proposed SD division algorithm is very cost effective in divider design. The proposed algorithms and their error analysis have been verified by C language simulation. Because of the similarity in the array multiplication algorithm and the division-by-reciprocal algorithm, the divider and multiplier can be fused into a single unit. The sharing of the FLP multiplication circuit with FLP division can reduce the hardware cost and power consumption of a high-performance FLP arithmetic unit. Based on our proposed novel array architecture, we have designed a single-precision FLP multiplication/division fused unit. From on simulations, we found that about 20% hardware cost of the multiplier and divider can be reduced. We conclude that on proposed fused unit is a cost-effective design.

碩士
南台科技大學
電子工程系
91
Multiplication operations play an important role in many high-speed DSP and communication systems. For many practical applications, multiplication operations require the fixed-width result so that the n least-significant bits (LSBs) of 2n-bit product must be truncated. The fixed-width property can be applied to significantly reduce the area and power of multiplier by directly omitting about half the adder cells of the conventional multiplier, but an unacceptable product error might be introduced. Many efficient error compensation methods and structures were proposed to reduce the product error. However, most of them designed the fixed-width multiplier based on the Baugh-Wooley multiplier, and none gave attention to the redundant binary signed-digit (RBSD) multiplier. In this thesis, we focus on the design of low-cost truncated RBSD multipliers reduce the area and power of multiplier as well as the whole system. Experimental results show that the proposed fixed-width RBSD multiplier has lower truncation error as compared with other proposed architectures while maintaining smaller area and lower power. Besides, we use our multiplier to realize a low-cost and high-utilization folded architecture for DCT (discrete cosine transform). The proposed VLSI architecture is described in Verilog HDL and synthesized by the Synopsys Design Compiler with 0.35um 1P4M CMOS technology. The gate count of it is 11040, and chip area is 1745×1734um2. Its operation clock frequency is about 57.8 MHz. Finally, a demo system is built by integrating an Altera FPGA chip implemented the proposed DCT with an 8051 microprocessor to verify the performance of our DCT circuit.

碩士
逢甲大學
資訊工程學系
89
To achieve high performance, low lost, and low power objectives, floating-point (FLP) multiplication and FLP addition are usually implemented in one unit for the design of microprocessors. Sign digit addition is adopted in the design of a new floating-point (FLP) multiplication-add fused (MAF) unit. This adoption, together with the proposed two-step normalization method, can reduce the three-word-length addition that is required in the conventional FLP MAF unit to a two-word-length adder. Furthermore, the sign reversion of the intermediate mantissa that requires a three-word-length carry propagation in the conventional MAF unit is replaced by only a one single word sign detection. These two improvements can enhance the speed and cost of the MAF unit significantly. With the use of the SD addition, the circuit of the unit can be designed in a more regular and simple manner, which is a property that is desired in VLSI design. 　　The proposed FLP unit consists of three pipeline states：the first is the alignment and multiplication stage, the second stage is the first-step normalization and SD-to-SM conversion stage, and finally the third stage is the second-step normalization and rounding stage. This double-precision FLP unit has been designed by using Verilog HDL and has been simulated by using Verilog-XL.

Digital filters having sharp transition band play a vital role in modern digital signal processing (DSP) applications. Emerging technologies require digital filters to be both computationally efficient in software/hardware realizations. This thesis is concerned with the design and structural-level optimization of sharp transition band digital filters employing the well known frequency response masking (FRM) approach. Unlike the conventional finite impulse response (FIR) based FRM approach, the FRM technique used in this thesis incorporates infinite impulse response (IIR) digital interpolation subfilters, thereby reducing the overall filter order that results in a reduction of hardware complexity. Two realization methods are discussed in this thesis, namely, the bilinear-lossless-discrete-integrators (bilinear-LDI) digital filter design technique, and the lattice wave digital filter (lattice WDF) digital filter design technique. Diversity controlled (DC) genetic algorithm (GA) is employed to optimize both types of IIR based FRM digital filters over the efficient canonical signed digit (CSD) multiplier coefficient space. DCGAs represent FRM digital filters by a binary chromosome and proceed from a population pool of candidate chromosomes to future generations in order to arrive at the desired FRM digital filter satisfying the design specifications. A novel cost-function is used that allows the DCGA to simultaneously optimize both the amplitude-frequency and group-delay frequency response. A fast convergence speed has been observed.
Communications

It is essential to secure the implementation of cryptosystems in embedded devices agains side-channel attacks. Namely, in order to resist differential (DPA) attacks, randomization techniques should be employed to decorrelate the data processed by the device from secret key parts resulting in the value of this data. Among the countermeasures that appeared in the literature were those that resulted in a random representation of the key known as the binary signed digit representation (BSD). We have discovered some interesting properties related to the number of possible BSD representations for an integer and we have proposed a different randomization algorithm. We have also carried our study to the $\tau$-adic representation of integers which is employed in elliptic curve cryptosystems (ECCs) using Koblitz curves. We have then dealt with another randomization countermeasure which is based on randomly splitting the key. We have investigated the secure employment of this countermeasure in the context of ECCs.

Title: Binary Signed Digit Representations of Integers in Cryptanalysis of Hash Functions Author: Jiří Vábek Department: Department of Algebra Supervisor: doc. RNDr. Jiří Tůma, DrSc., Department of Algebra Abstract: The work summarizes two main papers, A New Type of 2-block Colli- sions in MD5 and On the Number of Binary Signed Digit Representations of a Given Weight, while containing also the wider introduction to the topic of crypt- analysis of MD5 and binary signed digit representations (BSDR's). In the first paper we have implemented and applied Stevens algorithm to the newly proposed initial message differences and constructed a new type of collisions in MD5. In the second paper we have introduced and proved a new improved bound for the number of optimal BSDR's and also a new recursive bound for the number of BSDR's of a given integer with a given overweight. In addition to the results in mentioned papers, the generalized result is stated with the new bound for the number of optimal D-representations of natural numbers with D = {0, 1, 3}. Keywords: hash function, MD5, binary signed digit representation (BSDR), non- adjacent form (NAF) 1