- Date:19 Nov 2020
- Views:1
- Downloads:0
- Pages:17
- Size:783.88 KB

Transcription:

IJRET International Journal of Research in Engineering and Technology ISSN 2319 1163. Since DFT and IDFT involve basically the same type of But WN2 WN 2 With this substitution the equation can be. computations our discussion of efficient computational expressed as. algorithms for the DFT applies as well to the efficient. computation of the IDFT, We observe that for each value of k direct computation. of X k involves N complex multiplications 4N real, multiplications and N 1 complex additions 4N 2 real. additions Consequently to compute all N values of the DFT. requires N 2 complex multiplications and N 2 N complex Where F1 k and F2 k are the N 2 point DFTs of the. additions sequences f1 m and f2 m respectively, Direct computation of the DFT is basically inefficient Since F1 k and F2 k are periodic with period N 2 we. primarily because it does not exploit the symmetry and have F1 k N 2 F1 k and F2 k N 2 F2 k In addition the. periodicity properties of the phase factor W N In particular factor WNk N 2 WNk Hence the equation may be expressed. these two properties are as, The computationally efficient algorithms described in this. section known collectively as fast Fourier transform FFT. algorithms exploit these two basic properties of the phase We observe that the direct computation of F1 k requires. factor N 2 2 complex multiplications The same applies to the. computation of F2 k Furthermore there are N 2 additional. 2 1Radix 2 FFT Algorithms complex multiplications required to compute WNkF2 k Hence. the computation of X k requires 2 N 2 2 N 2 N 2 2 N 2. Let us consider the computation of the N 2v point DFT by complex multiplications This first step results in a reduction. the divide and conquer approach We split the N point data of the number of multiplications from N 2 to N 2 2 N 2. sequence into two N 2 point data sequences f1 n and f2 n which is about a factor of 2 for N large. corresponding to the even numbered and odd numbered. samples of x n respectively that is, Thus f1 n and f2 n are obtained by decimating x n by a.

factor of 2 and hence the resulting FFT algorithm is called. a decimation in time algorithm, Now the N point DFT can be expressed in terms of the DFT s. of the decimated sequences as follows, Figure 1 1 First step in the decimation in time algorithm. By computing N 4 point DFTs we would obtain the N 2 point. DFTs F1 k and F2 k from the relations, Volume 01 Issue 01 Sep 2012 Available http www ijret org 30. IJRET International Journal of Research in Engineering and Technology ISSN 2319 1163. The decimation of the data sequence can be repeated again. and again until the resulting sequences are reduced to one. point sequences For N 2v this decimation can be performed. v log2N times Thus the total number of complex, multiplications is reduced to N 2 log2N The number of. complex additions is Nlog2N, For illustrative purposes Figure 1 2 depicts the computation.

of N 8 point DFT We observe that the computation is. performed in three stages beginning with the computations of. four two point DFTs then two four point DFTs and finally. one eight point DFT The combination for the smaller DFTs to. form the larger DFT is illustrated in Figure 2 3 for N 8. Figure 1 3 Eight point decimation in time FFT algorithms. Figure 1 4 basic butterfly computations in the decimation in. time FFT algorithm, An important observation is concerned with the order of the. input data sequence after it is decimated v 1 times For. example if we consider the case where N 8 we know that. Figure 1 2 Three stages in the computation of an N 8. the first decimation yields the sequence x 0 x 2 x 4 x 6. x 1 x 3 x 5 x 7 and the second decimation results in the. sequence x 0 x 4 x 2 x 6 x 1 x 5 x 3, x 7 This shuffling of the input data sequence has a well. defined order as can be ascertained from observing Figure1 5. which illustrates the decimation of the eight point sequence. Volume 01 Issue 01 Sep 2012 Available http www ijret org 31. IJRET International Journal of Research in Engineering and Technology ISSN 2319 1163. where we have used the fact that WN2 WN 2, The computational procedure above can be repeated through. decimation of the N 2 point DFTs X 2k and X 2k 1 The. entire process involves v log2N stages of decimation where. each stage involves N 2 butterflies of the type shown in. Figure2 7 Consequently the computation of the N point DFT. via the decimation in frequency FFT requires N 2 log2N. complex multiplications and Nlog2N complex additions just. as in the decimation in time algorithm For illustrative. purposes the eight point decimation in frequency algorithm is. given in Figure 1 8,Figure 1 5 Shuffling of the data and bit reversal. Another important radix 2 FFT algorithm called the. decimation in frequency algorithm is obtained by using the. divide and conquer approach To derive the algorithm we. begin by splitting the DFT formula into two summations one. of which involves the sum over the first N 2 data points and. the second sum involves the last N 2 data points Thus we. Figure 1 6 First stage of the decimation in frequency FFT. Now let us split decimate X k into the even and odd algorithm. numbered samples Thus we obtain, Volume 01 Issue 01 Sep 2012 Available http www ijret org 32.

IJRET International Journal of Research in Engineering and Technology ISSN 2319 1163. examples are Morse code and ASCII Simple ciphers include. the substitution of letters for numbers the rotation of letters in. the alphabet and the scrambling of voice signals by. inverting the sideband frequencies More complex ciphers. work according to sophisticated computer algorithms that. rearrange the data bits in digital signals Encryption finds its. use in many scenarios as follows, Figure 1 7 Basic butterfly computation in the decimation in. We observe from Figure TC 3 8 that the input data x n occurs. in natural order but the output DFT occurs in bit reversed. Figure 3 1 Uses of encryption methods, Encryption refers to algorithmic schemes that encode plain. text into non readable form or cipher text providing privacy. The receiver of the encrypted text uses a key to decrypt the. message returning it to its original plain text form The key is. the trigger mechanism to the algorithm Until the advent of the. Internet encryption was rarely used by the public but was. largely a military tool Today with online marketing banking. Figure 1 8 N 8 piont decimation in frequency FFT healthcare and other services even the average householder is. algorithm aware of encryption As more people realize the open. nature of the Internet email and instant messaging. We also note that the computations are performed in place encryption will undoubtedly become more popular. However it is possible to reconfigure the decimation in Without encryption information passed on the Internet. frequency algorithm so that the input sequence occurs in bit. is not only available for virtually anyone to snag and. reversed order while the output DFT occurs in normal order. Furthermore if we abandon the requirement that the. read but is often stored for years on servers that can. computations be done in place it is also possible to have both change hands or become compromised in any number of. the input data and the output DFT in normal order ways For all of these reasons encryption is a goal worth. pursuing In order to easily recover the contents of an. 3 ENCRYPTION encrypted signal the correct decryption key is required The. key is an algorithm that undoes the work of the encryption. Encryption is the conversion of data into a form called a algorithm Alternatively a computer can be used in an attempt. cipher text that cannot be easily understood by unauthorized to break the cipher The more complex the encryption. people Decryption is the process of converting encrypted data algorithm the more difficult it becomes to eavesdrop on the. back into its original form so it can be understood communications without access to the key Often there has. been a need to protect information from prying eyes In the. The use of encryption decryption is as old as the art of electronic age information that could otherwise benefit or. communication In wartime a cipher often incorrectly called educate a group or individual can also be used against such. a code can be employed to keep the enemy from obtaining the groups or individuals Industrial espionage among highly. contents of transmissions Technically a code is a means of competitive businesses often requires that extensive security. representing a signal without the intent of keeping it secret. Volume 01 Issue 01 Sep 2012 Available http www ijret org 33. IJRET International Journal of Research in Engineering and Technology ISSN 2319 1163. measures be put into place And those who wish to exercise Cryptography is used to change readable text called plaintext. their personal freedom outside of the oppressive nature of into an unreadable secret format called cipher text using a. governments may also wish to encrypt certain information to process called encryption Encrypting data provides additional. avoid suffering the penalties of going against the wishes of benefits besides protecting the confidentiality of data Other. those who attempt to control Still the methods of data benefits include ensuring that messages have not been altered. encryption and decryption are relatively straightforward and during transit and verifying the identity of the message sender. easily mastered I have been doing data encryption since my All these benefits can be realized by using basic encryption. college days when I used an encryption algorithm to store methods. game programs and system information files on the university Hashing. mini computer safe from prying eyes These were files that. raised eyebrows amongst those who did not approve of such The first encryption method called hashing creates a unique. things but were harmless I was occasionally asked what this fixed length signature of a group of data Hashes are created. rather large file contained and I once demonstrated the with an algorithm or hash function and are used to compare. program that accessed it but you needed a password to get to sets of data Since a hash is unique to a specific message any. certain files nonetheless And some files needed a separate changes to that message would result in a different hash. encryption program to decipher them thereby alerting a user to potential tampering. Encryption decryption is especially important in wireless A hash algorithm also known as a hash function is a. communications This is because wireless circuits are easier to. mathematical procedure used in computer programming to. tap than their hard wired counterparts Nevertheless. turn a large section of data into a smaller representational. encryption decryption is a good idea when carrying out any. kind of sensitive transaction such as a credit card purchase symbol known as a hash key The major use of hash. online or the discussion of a company secret between algorithms occurs in large databases of information Each. different departments in the organization The stronger the collection of data is assigned a hash key which is a short. cipher that is the harder it is for unauthorized people to symbol or code that represents it When a user needs to find. break it the better in general However as the strength of that piece of data he inputs the symbol or code and the. encryption decryption increases so does the cost In recent computer displays the full data piece. years a controversy has arisen over so called strong. encryption This refers to ciphers that are essentially For hashing as this process is called to work it needs a hash. unbreakable without the decryption keys While most function or hash algorithm This tells the computer how to. companies and their customers view it as a means of keeping take the hash key and match it with a set of data it represents. secrets and minimizing fraud some governments view strong Areas in the computer program known as slots or buckets. encryption as a potential vehicle by which terrorists might store information and each key links to a specific slot or. evade authorities These governments including that of the bucket The entire process is contained within a hash. United States want to set up a key escrow arrangement This table or hash map This table records data and the. means everyone who uses a cipher would be required to matching keys that correspond to it It then uses a hash. provide the government with a copy of the key Decryption algorithm to connect a key to a piece of data when the. keys would be stored in a supposedly secure place used only user requests it. by authorities and used only if backed up by a court order. Opponents of this scheme argue that criminals could hack into A key difference between a hash and the other two encryption. the key escrow database and illegally obtain steal or alter the methods is that once the data is encrypted the process cannot. keys Supporters claim that while this is a possibility be reversed or deciphered This means that even if a potential. implementing the key escrow scheme would be better than attacker were able to obtain a hash he would not be able to. doing nothing to prevent criminals from freely using use a decryption method to discover the contents of the. encryption decryption original message Some common hashing algorithms are. TEXT FILE ENCRYPTION USING FFT TECHNIQUE IN Lab VIEW 8 6 Sudha Rani K1 T C Sarma2 K Encryptor Decryptor Fast Fourier transforms FFT 1 INTRODUCTION Encryption has long been used by militaries and governments to facilitate secret communication It is now commonly used in protecting information within many kinds of civilian systems For example the Computer Security

Recent Views:

- Ei ip 501 determination of aluminum silicon vanadium
- Pengurusan harta melalui hibah kepentingan dan manfaat
- Building capacity for eq transformation proven practical
- Center to prepare plan for iowa legislature inside this issue
- Volvo penta workshop manual f4ewz free fr
- Kd x40 jvc
- San gabriel valley jr all american football conference inc
- Kinematika gerak lurus gerak melingkar beraturan dan
- 2010 spp 4 rlas docs 201 209
- Chapter 7 resource masters ktl math classes