25-08-2012, 04:29 PM
FPGA IMPLEMENTATION OF HIGH SPEED CONVOLUTION AND DECONVOLUTION USING VEDIC MULTIPLIER
FPGA Implementation.docx (Size: 785.9 KB / Downloads: 41)
ABSTRACT
We propose the generation of a pseudorandom bit sequence (PRBS) using a Coupled Quadratic Congruential Generator (CQCG). For this we need to couple quadratic congruential generators. The output of CQCG is “1” if the first Quadratic Congruential Generator (QCG) produces an output that is greater than the output of the second Quadratic Congruential Generator (QCG) else “0”. Breaking this scheme would require one to obtain the seeds of the two independent generators given the bits of the output sequence.
We prove that the problem of uniquely determining the seeds for the CQCG requires the following: Knowledge of at least log2 m2 (m being the QCG modulus) bits of the output sequence. The solution of at least log2 m2 inequalities, where each inequality (dictated by the output bit observed) is applied over positive integers. Computationally, we show that this task is exponential in n (where n = log2m is the number of bits in m) with complexity O(22n). Dual CLCG offers a series of advantages based on its mathematical structure it is more secure and high degree of randomness. If we use this random sequences in cryptography and other applications means security will be in very high degree. Wherever the fixed output not is necessary we use DCLCG, but most of the applications like spread spectrum modulation, cryptography need fixed bit length. Therefore CQCG gives fixed length output along with high consistency, randomness and security.
INTRODUCTION
RANDOM bits generation is a key issue in many applications, such as cryptography, stochastic simulations, testing of digital circuits and telecommunication systems. Randomness is a tricky thing. It is easily found in the world around us, but if you want to actively generate, say, a random sequence of numbers, it suddenly becomes quite elusive. The more advanced hand-held calculators have a program that generates, seemingly, random numbers by using specific algorithms, but the fact is that this is not true randomness, but rather pseudo randomness. This means that although the number sequence generated may seem random to a person, a statistical analysis may reveal subtle patterns and skews in the data. For the applications of a pocket calculator, this is probably not a big deal. However, random numbers are a big part of modern cryptography, and are used in, for example, Internet banking. It would be inherently bad if your personal bank ID could be easily predicted by a large statistical analysis of ID-data, so true randomness would be an advantage for these applications.
PSEUDORANDOM NUMBERS GENERATION
Generators of number sequences are used in various branches of science. A special role is attributed to random and pseudorandom generators. The chaos phenomenon has introduced a new dimension into relations between existing random and pseudorandom generators and enabled numerous new propositions of generating sequences with desired statistical properties to be introduced .A good introduction can be found in the end of this project and in the references there in .One of potential applications of chaos-based generators is cryptography, where there is often a need for sources of secure number sequences.
LINEAR CONGRUENTIAL GENERATOR (LCG)
The linear congruential generator (LCG) was proposed by Lehmer. Linear congruential generators (LCGs) of the form xi+1 = axi + b (mod m), have been used to generate pseudorandom numbers. However these generators have been known to be insecure. This implies that if a small sequence of numbers generated by an LCG is known then it is possible to predict the remaining numbers in the sequence that will be generated. We propose to generate a secure pseudorandom bit sequence by coupling two LCGs as follows. A 1 is output if the first LCG produces an output that is greater than the output of the second LCG and a 0 is output otherwise. The security of this sequence is shown by demonstrating the difficulty of obtaining the initial conditions of the two LCGs given the pseudorandom bit sequence output. If the modulus m is a power of 2 then efficient circuits can be designed for the proposed generators.
CONCLUSION
We have proposed a new pseudorandom bit sequence (PRBS) generator based on QCGs. Such generators are moderately secure in the sense that it is hard to find the seed if the parameters of the QCGs and the output bit sequence are known. We also proposed an efficient scheme to generate parameters for the coupled QCG such that the resulting PRBSs they generate random bits that gives high pseudo randomness with a high degree of consistency. Therefore, coupled QCGs can be used as PRBS generators where high security is needed or they can be used where simply good PRBSs. Examples of applications where good PRBSs are required are simulation and randomized algorithms.