Tesis sobre el tema "Transformée de Walsh"

Dans cette thèse, on propose des améliorations qui peuvent être appliquées à plusieurs techniques de cryptanalyse de primitives symétriques. On dédie une attention spéciale à la cryptanalyse linéaire, pour laquelle une technique basée sur la transformée de Walsh rapide était déjà connue (Collard et al., ICISC 2007). On introduit une version généralisée de cette attaque, qui permet de l'appliquer pour la récupération de clé considerant plusieurs tours, ainsi que le réduction de la complexité du problème en utilisant par example des informations provénantes du key-schedule. On propose aussi une technique générale pour accélérer les attaques par récupération de clé qui est basée sur la représentation des boîtes S en tant que arbres binaires. Finalement, on montre comment on a obtenu une approximation linéaire sur la version complète de la permutation Gimli en utilisant l'optimisation par mixed-integer linear programming (MILP)<br>This thesis proposes improvements which can be applied to several techniques for the cryptanalysis of symmetric primitives. Special attention is given to linear cryptanalysis, for which a technique based on the fast Walsh transform was already known (Collard et al., ICISIC 2007). We introduce a generalised version of this attack, which allows us to apply it on key recovery attacks over multiple rounds, as well as to reduce the complexity of the problem using information extracted, for example, from the key schedule. We also propose a general technique for speeding key recovery attacks up which is based on the representation of Sboxes as binary decision trees. Finally, we showcase the construction of a linear approximation of the full version of the Gimli permutation using mixed-integer linear programming (MILP) optimisation

This thesis presents a new algorithm which can be used to register images of the same or different modalities e.g images with multiple channels such as X-rays, temperature, or elevation or simply images of different spectral bands. In particular, a correlation-based scheme is used, but instead of grey values, it correlates numbers formulated by different combinations of the extracted local Walsh coefficients of the images. Each image patch is expanded in terms of Walsh basis functions. Each Walsh basis function can be thought of as measuring a different aspect of local structure, eg horizontal edge, corner, etc. The coefficients of the expansion, therefore, can be thought of as dense local features, estimating at each point the degree of presence of, for example, a horizontal edge, a corner with contrast of a certain type, etc. These coefficients are normalised and used as digits in a chosen number system which allows one to create a unique number for each type of local structure. The choice of the basis of the number system allows one to give different emphasis to different types of local feature (e.g. corners versus edges) and thus the method we present forms a unified framework in terms of which several feature matching methods may be interpreted. The algorithm is compared with wavelet based approaches, using simulated and real images. The images used for the registration experiments are assumed to differ from each other by a rotation and a translation only. Additionally, the method was extended to cope with 3D image sets, while as an add-on, it was also tried in performing image segmentation.

Approved for public release; distribution is unlimited<br>Linear cryptanalysis attacks are a threat against cryptosystems. These attacks can be defended against by using combiner functions composed of highly nonlinear Boolean functions. Bent functions, which have the highest possible nonlinearity, are uncommon. As the number of variables in a Boolean function increases, bent functions become extremely rare. A method of computing the nonlinearity of Boolean functions using the Fast Walsh Transform (FWT) is presented. The SRC-6 reconfigurable computer allows testing of functions at a much faster rate than a PC. With a clock frequency of 100 MHz, throughput of the SRC-6 is 100,000,000 functions per second. An implementation of the FWT used to compute the nonlinearity of Boolean functions with up to five variables is presented. Since there are 22n Boolean functions of n variables, computation of the nonlinearity of every Boolean function with six or more variables takes thousands of years to complete. This makes discovery of bent functions difficult for large n. An algorithm is presented that uses information in the FWT of a function to produce similar functions with increasingly higher nonlinearity. This algorithm demonstrated the ability to enumerate every bent function for n = 4 without the necessity of exhaustively testing all fourvariable functions.

Boolean functions are the main building blocks of most cipher systems. Various aspects of their cryptological characteristics are examined and investigated by many researchers from different fields. This thesis has no claim to obtain original results but consists in an attempt at giving a unified survey of the main results of the subject. In this thesis, the theory of boolean functions is presented in details, emphasizing some important cryptological properties such as balance, nonlinearity, strict avalanche criterion and propagation criterion. After presenting many results about these criteria with detailed proofs, two upper bounds and two lower bounds on the nonlinearity of a boolean function due to Zhang and Zheng are proved. Because of their importance in the theory of boolean functions, construction of Sylvester-Hadamard matrices are shown and most of their properties used in cryptography are proved. The Walsh transform is investigated in detail by proving many properties. By using a property of Sylvester-Hadamard matrices, the fast Walsh transform is presented and its application in finding the nonlinearity of a boolean function is demonstrated. One of the most important classes of boolean functions, so called bent functions, are presented with many properties and by giving several examples, from the paper of Rothaus. By using bent functions, relations between balance, nonlinearity and propagation criterion are presented and it is shown that not all these criteria can be simultaneously satisfied completely. For this reason, several constructions of functions optimizing these criteria which are due to Seberry, Zhang and Zheng are presented.

International Telemetering Conference Proceedings / October 13-16, 1986 / Riviera Hotel, Las Vegas, Nevada<br>In most transmission channels, bandwidth is at a premium and an important attribute of any good digital signalling scheme is to optimally utilise the bandwidth for transmitting the information. The Data Compression System in this way plays a significant role in the transmission of picture data from any Remote Sensing Satellite by exploiting the statistical properties of the imagery. The data rate required for transmission to ground can be reduced by using suitable compression technique. A data compression algorithm has been developed for processing the images of Indian Remote Sensing Satellite. Sample LANDSAT imagery and also a reference photo are used for evaluating the performance of the system. The reconstructed images are obtained after compression for 1.5 bits per pixel and 2 bits per pixel as against the original of 7 bits per pixel. The technique used is uni-dimensional Hadamard Transform Technique. The Histograms are computed for various pictures which are used as samples. This paper describes the development of such a hardware and software system and also indicates how hardware can be adopted for a two dimensional Hadamard Transform Technique.

This thesis presents novel research work on copyright protection of grey scale and colour digital images. New blind frequency domain watermarking algorithms using one dimensional and two dimensional Walsh coding were developed. Handwritten signatures and mobile phone numbers were used in this project as watermarks. In this research eight algorithms were developed based on the DCT using 1D and 2D Walsh coding. These algorithms used the low frequency coefficients of the 8 × 8 DCT blocks for embedding. A shuffle process was used in the watermarking algorithms to increase the robustness against the cropping attacks. All algorithms are blind since they do not require the original image. All algorithms caused minimum distortion to the host images and the watermarking is invisible. The watermark is embedded in the green channel of the RGB colour images. The Walsh coded watermark is inserted several times by using the shuffling process to improve its robustness. The effect of changing the Walsh lengths and the scaling strength of the watermark on the robustness and image quality were studied. All algorithms are examined by using several grey scale and colour images of sizes 512 × 512. The fidelity of the images was assessed by using the peak signal to noise ratio (PSNR), the structural similarity index measure (SSIM), normalized correlation (NC) and StirMark benchmark tools. The new algorithms were tested on several grey scale and colour images of different sizes. Evaluation techniques using several tools with different scaling factors have been considered in the thesis to assess the algorithms. Comparisons carried out against other methods of embedding without coding have shown the superiority of the algorithms. The results have shown that use of 1D and 2D Walsh coding with DCT Blocks offers significant improvement in the robustness against JPEG compression and some other image processing operations compared to the method of embedding without coding. The originality of the schemes enables them to achieve significant robustness compared to conventional non-coded watermarking methods. The new algorithms offer an optimal trade-off between perceptual distortion caused by embedding and robustness against certain attacks. The new techniques could offer significant advantages to the digital watermark field and provide additional benefits to the copyright protection industry.

In this thesis, one finalist cipher of the Advanced Encryption Standard (AES) block cipher contest, Twofish proposed by Schneier et al, is studied in order to observe the validity of the statement made by Arikan about the randomness of the cipher, which contradicts National Institute of Standards and Technology (NIST)&rsquo<br>s results. The strength of the cipher to cryptanalytic attacks is investigated by measuring its randomness according to the avalanche criterion. The avalanche criterion results are compared with those of the Statistical Test Suite of the NIST and discrepancies in the second and third rounds are explained theoretically.

Bladder cancer is one of the most common urogenital cancers worldwide. Two techniques commonly used for bladder cancer diagnosis are urine cytology and cystoscopy. Cytology is not sensitive for detecting tumors. Cystoscopy is an invasive technique which disturbs patient comfort. In the current study, we used Fourier transform infrared (FT-IR) spectroscopy as a novel method which is rapid and non-invasive to investigate the bladder tumor recurrence using the bladder wash samples collected in the course of control cystoscopy. This study is unique since it is the first one to use the bladder wash sample in the diagnosis of the bladder tumor by using FT-IR spectroscopy. Molecular investigation of the FT-IR spectra revealed many differences between control and tumor samples such as a considerable increase in protein, carbohydrate and nucleic acids content, and changes in protein and carbohydrate structure. On the basis of the spectral differences, cluster analysis was performed to differentiate between the control and tumorous spectra and we reached to an overall sensitivity (including all individuals with tumor) of 91.8%, a PUNLMP sensitivity of 83.3% and a papilloma sensitivity of 77.8% in spectral range 1444-1457 cm-1. Other spectral ranges also gave similar results. Our results showed that FT-IR spectroscopy can be used to detect the bladder tumors in bladder wash sample with higher sensitivity compared to cytology. In summary, we propose the utilization of the FT-IR spectroscopy for the detection of bladder tumors since specific spectral regions might be used as effective markers for the diagnosis.

Boolean functions are accepted to be cryptographically strong if they satisfy some common pre-determined criteria. It is expected that any design criteria should remain invariant under a large group of transformations due to the theory of similarity of secrecy systems proposed by Shannon. One of the most important design criteria for cryptographically strong Boolean functions is the nonlinearity criterion. Meier and Staffelbach studied nonlinearity preserving transformations, by considering the invertible transformations acting on the arguments of Boolean functions, namely the pre-transformations. In this thesis, first, the results obtained by Meier and Staffelbach are presented. Then, the invertible transformations acting on the truth tables of Boolean functions, namely the post-transformations, are studied in order to determine whether they keep the nonlinearity criterion invariant. The equivalent counterparts of Meier and Staffelbach&rsquo<br>s results are obtained in terms of the post-transformations. In addition, the existence of nonlinearity preserving post-transformations, which are not equivalent to pre-transformations, is proved. The necessary and sufficient conditions for an affine post-transformation to preserve nonlinearity are proposed and proved. Moreover, the sufficient conditions for an non-affine post-transformation to keep nonlinearity invariant are proposed. Furthermore, it is proved that the smart hill climbing method, which is introduced to improve nonlinearity of Boolean functions by Millan et. al., is equivalent to applying a post-transformation to a single Boolean function. Finally, the necessary and sufficient condition for an affine pre-transformation to preserve the strict avalanche criterion is proposed and proved.

When considering Boolean switching functions with n input variables, there are 2^(2^n) possible functions that can be realized by enumerating all possible combinations of input values and arrangements of output values. As is expected with double exponential growth, the number of functions becomes unmanageable very quickly as n increases. This thesis develops a new approach for computing the spectral classes where the spectral operations are performed by manipulating the truth tables rather than first moving to the spectral domain to manipulate the spectral coefficients. Additionally, a generic approach is developed for modeling these spectral operations within the functional domain. The results of this research match previous for n < or = to 4 but differ when n=5 is considered. This research indicates with a high level of confidence that there are in fact 15 previously unidentified classes, for a total of 206 spectral classes needed to represent all 2^(2^n) Boolean functions.

博士<br>國立臺灣大學<br>電信工程學研究所<br>102<br>The thesis contains two research topics: The first one is the discussion about the properties and applications of the complete generalized Legendre sequence (CGLS) and the second one is about the generalization between the Walsh-Hadamard transform (WHT) and the DFT and their properties. The CGLS is first defined to solve the DFT eigenvector problem. The proposed CGLS based DFT eigenvectors have the advantages of closed-form solutions, completeness, orthogonality, being well defined for arbitrary N, and fast DFT expansion so that the CGLS is helpful for developing DFT fast algorithms. Based on the CGLS researches, we can extend our results to the finite field operation. That means we can also use the CGLS over finite field (CGLSF) to solve the number theoretic transform (NTT) eigenvector problem. Mean while, we can apply the CGLS and CGLSF to constructing fast DFT(NTT) algorithm, fractional number theoretic transform (FNTT) definition and the switchable perfect shuffle transform (PST) system. The WHT and the DFT are two of the most important transforms for signal processing applications. Our purpose is to generalize these two transform by a single parameter so that the generalized transforms can not only have the advantages of the WHT and DFT but also have flexibility to some applications. We will first define the discrete orthogonal transform (DOT), conjugate symmetric discrete orthogonal transform (CS-DOT) and the fast finite field orthogonal transform (FFFOT). From the above transform, we can furthermore define the sequency ordered generalized Walsh-Fourier transform (SGWFT) and conjugate symmetric sequency ordered generalized Walsh-Fourier transform (CS-SGWFT) and show their properties and applications in CDMA sequence design, spectrum estimation and transform coding.

碩士<br>國立東華大學<br>電機工程學系<br>101<br>This thesis presents the Space-Time Block Codes (STBC) constructed by using the diagonal orthogonal coefficient with decoupling in time domain. The novel Walsh-Hadamard STBC (WHSTBC) gives full rate and full diversity order with appropriate pre-coding of the PSK or QAM modulated symbols, when the number of receiver antennas is at least equal to the number of transmit antennas. Hadamard matrices exist for orders equal to N=2^n, where n≥1, and the receiver allows for some decoupling methods and decoding with Maximal Ratio Combining (MRC). Finally, the performance will be different because of the different antennas and time arrangement.

碩士<br>逢甲大學<br>資訊工程所<br>91<br>The fast Walsh Hadamard transform is a simple and important algorithm in digital signal processing, especially, in digital image compression. The fast Walsh Hadamard transform is a block recursive algorithm, which can be easily expressed as a tensor product formula. Also, the tensor product notation can be used to express the topology of interconnection networks. In this thesis, we will emerge the specification of tensor product formulation of block recursive algorithms and interconnection networks to design fast Walsh Hadamard transform algorithms on various interconnection networks, including hypercube networks, omega networks, and baseline networks. The design process starts from a tensor product formula of the fast Walsh Hadamard transform. Given a specific interconnection network, we will manipulate the tensor product formula of the fast Walsh Hadamard transform to an equivalent formula which fits the form of the tensor product formula of that interconnection network. The resulting algorithms are suitable for designing VLSI circuits of DSP algorithms.

碩士<br>國立交通大學<br>控制工程研究所<br>78<br>The discrete Walsh transform (DWT) is applied to response analysis, identification and model reduction of the 2-D discrete-time LSI system. The data arrays are transformed into discrete Walsh spectrum matrices using DWT. First, with the shift DWT being utilized and the Walsh spectra manipulated by Kronecker product of two matrices, the response of 2-D system can be easily evaluated for arbitrary in- put with zero initial conditions. Next, from the point of view of data matching, the transfer function of 2-D system is identified from finite input-output data, where the output is mixed with uniformly distributed disturbance. In the third part, the 2-D discrete Walsh spectrum matching approach is also used for reducing the transfer function of a given 2-D system to a lower order model. Examples are illustrated to demonstrate the usefulness. Moreover, an electronic circuit, based on a neural net, to compute the DWT is also presented. The circuit behavior is analyzed and the fabrication problem is considered as well. Simulation results show that the proposed circuit is suitable for real-time DWT computation.

碩士<br>大同大學<br>通訊工程研究所<br>97<br>Orthogonal Frequency Division Multiplex (OFDM) is a very suitable technique for achieving high-rate wireless data transmission. High spectral efficiency, robustness to channel fading, immunity to impulse interference and less non linear distortion are among the favorite properties of OFDM. One major drawback of OFDM is high Peak to Average Power Ratio (PAPR) of the transmitted signal. The high peaks of an OFDM signal are distorted nonlinearly by the high power amplifier (HPA) because the HPA heavily distorts all signal parts that come close to or exceed saturation. The distortion causes inter carrier interference (ICI) and out-of-band (OOB) radiation. While ICI disturbs the transmitted signal, it degrades the bit error rate (BER). OOB radiation disturbs signals on adjacent frequency bands, so it should be avoided. Several methods have been proposed in the literature to reduce the peak power of OFDM signals and substantial gains were reported. SLM (selective mapping) method is one of the efficient methods to reduce PAPR in OFDM system. However, SLM method has a serious disadvantage high calculation complexity. In this thesis, the proposed method using modified SLM scheme with WHT (Walsh Hadamard transform) to lower the high PAPR of OFDM system and lower the calculation complexity effectively

碩士<br>國立高雄第一科技大學<br>電腦與通訊工程所<br>92<br>The orthogonal frequency division multiplexing (OFDM) technique is one of the most attractive multicarrier modulation schemes for its high bandwidth efficiency and strong immunity to multipath fading. Even though there are many advantages of OFDM, it has two main drawbacks: high Peak to Average Power Ratio (PAPR) and frequency offset. To overcome these PAPR probblems, different methods have been proposed to mitigate the PAPR problem of OFDM. These techniques can be divided into two categories: Signal scrambling and Signal distortion technique. In the thesis, we study the PAPR reduction of OFDM transmission system by jointly using both Walsh-Hadamard transform and companding technique. First, Hadamard transform is used to decompose the correlation relationship of OFDM input sequence. On the other hand, since OFDM signal is similar to speech signals in the sense that large signals occur very infrequently, the companding technique usually applying to these signals might be used to improve OFDM transmission performance. Finally, we verify our analytical results by using Monte Carlo simulation.

The operational life of wireless sensor network based distributed sensing systems is limited by the energy provided by a portable battery pack. Owing to the inherently resource constrained nature of wireless sensor networks and nodes, a major research thrust in this field is the search for energy-aware methods of operation. Communication is among the most energy-intensive operations on a wireless device. It is therefore, the focus of our efforts to develop an energy-aware method of communication and to introduce a degree of reconfigurability to ensure autonomous operation of such devices. Given this background, three research tasks have been identified and investigated during the course of this research. 1) Devising an energy-efficient method of communication in a framework of reconfigurable operation: The dependence of the energy consumed during communication on the number of bits transmitted (and received) was identified from prior research work. A novel method of data compression was designed to exploit this dependence. This method uses the time-limited, orthonormal Walsh functions as basis functions for representing signals. The L2 norm of this representation is utilized to further compress the signals. From Parseval’s relation, the square of the L2 norm represents the energy content of a signal. The application of this theorem to our research makes it possible to use the L2 norm as a control knob. The operation of this control knob makes it possible to optimize the number of terms required to represent signals. The time-limited nature of the Walsh functions was leveraged to inject dynamic behaviour into our coding method. This time-limited nature allows decomposition of finite time-segments, without attendant limitations like loss of resolution that are inherent to derived, discrete transforms like the discrete Fourier transform or the discrete time Fourier transform. This decomposition over successive, finite time-segments, coupled with innovative operation of the previously mentioned control knob on every segment, gives us a dynamic scaling technique. The amount of data to be transmitted is in turn based on the magnitude of the coefficients of decomposition of each time-segment, leading to the realization of a variable word length coding method. This dynamic coding method can identify evolving changes or events in the quantity being sensed. The coefficients of decomposition represent features present in successive time-segments of signals and therefore enable identification of evolving events. The ability to identify events as they occur enables the algorithm to react to events as they evolve in the system. In other words the data transmission and the associated energy consumption are imparted a reconfigurable, event-driven nature by implementation of the coding algorithm. Performance evaluation of this method via simulations on machine generated (bearing vibration) and biometric (electro-cardio gram) signals shows it be a viable method for energy-aware communication. 2) Developing a framework for reconfigurable triggering: A framework for completely autonomous triggering of the coding method has been developed. This is achieved by estimating correlations of the signal with the representative Walsh functions. The correlation coefficient of a signal segment with a Walsh function gives a picture of the amount of energy localized by the function. This information is used to autonomously tune the abovementioned control knob or, in more proper terms, the degree of thresholding used in compression. Evaluation of this framework on bearing vibration and electro-cardio gram signals has shown results consistent with those of previous simulations. 3) Devising a computationally compact method of feature classification: A method of investigating time series measurements of dynamic systems in order to classify features buried in the signal measurements was investigated. The approach involves discretizing time-series measurements into strings of pre-defined symbols. These strings are transforms of the original time-series measurements and are a representation of the system dynamics. A method of statistically analyzing the symbol strings is presented and its efficacy is studied through representative simulations and experimental investigation of vibration signals recorded from a rolling bearing element. The method is computationally compact because it obviates the need for local signal processing tasks like denoising, detrending and amplification. Results indicate that the method can effectively classify deteriorating machine health, changing operating conditions and evolving defects. In addition to these major foci, another research task was the design and implementation of a wireless network testbed. This testbed consists of a network of netbooks, connected together wirelessly and was utilized for experimental verification of the variable word length coding method.