[go: up one dir, main page]

WO1991010182A1 - Generateur de sources de bruit multiples independantes - Google Patents

Generateur de sources de bruit multiples independantes Download PDF

Info

Publication number
WO1991010182A1
WO1991010182A1 PCT/US1990/004407 US9004407W WO9110182A1 WO 1991010182 A1 WO1991010182 A1 WO 1991010182A1 US 9004407 W US9004407 W US 9004407W WO 9110182 A1 WO9110182 A1 WO 9110182A1
Authority
WO
WIPO (PCT)
Prior art keywords
cells
bit streams
plural
outputs
cell
Prior art date
Application number
PCT/US1990/004407
Other languages
English (en)
Inventor
Joshua Alspector
Robert Ray Chu
Joel Wright Gannett
Stuart Alan Haber
Michael Benjamin Parker
Original Assignee
Bell Communications Research, Inc.
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Bell Communications Research, Inc. filed Critical Bell Communications Research, Inc.
Publication of WO1991010182A1 publication Critical patent/WO1991010182A1/fr

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F7/58—Random or pseudo-random number generators
    • G06F7/582—Pseudo-random number generators
    • G06F7/584—Pseudo-random number generators using finite field arithmetic, e.g. using a linear feedback shift register
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06N—COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS
    • G06N3/00—Computing arrangements based on biological models
    • G06N3/02—Neural networks
    • G06N3/06—Physical realisation, i.e. hardware implementation of neural networks, neurons or parts of neurons
    • G06N3/063—Physical realisation, i.e. hardware implementation of neural networks, neurons or parts of neurons using electronic means
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/58—Indexing scheme relating to groups G06F7/58 - G06F7/588
    • G06F2207/581—Generating an LFSR sequence, e.g. an m-sequence; sequence may be generated without LFSR, e.g. using Galois Field arithmetic
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F2207/00—Indexing scheme relating to methods or arrangements for processing data by operating upon the order or content of the data handled
    • G06F2207/58—Indexing scheme relating to groups G06F7/58 - G06F7/588
    • G06F2207/583—Serial finite field implementation, i.e. serial implementation of finite field arithmetic, generating one new bit or trit per step, e.g. using an LFSR or several independent LFSRs; also includes PRNGs with parallel operation between LFSR and outputs

Definitions

  • Neural learning algorithms such as this capture correlations seen by neural states to perform classification based on input data.
  • stochastic elements are necessary for, among other reasons, performing unbiased averaging over neural states elsewhere in the network. Correlations in the noise they see would cause errors in the learning since these undesired correlations would be captured by the learning rule.
  • Other reasons for stochastic elements in neural networks include the search of a large solution space, helping a network settle while avoiding local minima, and interpolating between discrete values of weights by time averaging.
  • thermal noise generator seems simple and unbiased it has implementation problems. In particular, it exacts a substantial area penalty; and, in fact, occupies much more area than the neuron itself. More significantly, the large gain needed to amplify thermal noise can lead to cross coupling of the on-chip amplifiers thereby frustrating the original purpose of using separate noise amplifiers to obtain zero cross correlation. Despite this, the small network on the prior art test chip demonstrated satisfactory learning for small problems. To scale this network to larger size, it would have to be sensitive to more subtle correlations and therefore the noise sources must show minimal correlation.
  • a linear feedback shift register produces a pseudo-random bit stream (PRBS) that can be used to make an analog noise source.
  • PRBS pseudo-random bit stream
  • the PRBS is processed by a low-pass filter with cutoff frequency just a few percent of the clock frequency. This has the effect of performing a time integration over many bits. If each bit's value is randomly distributed with a probability of 0.5 for 0 or 1, then the value of this integration follows a binomial distribution that approaches a Gaussian distribution for a large number of bits. This creates a Gaussian analog pseudo-random noise source whose statistical properties are similar to the thermal noise which is to be modeled with a simulated annealing technique. Variable amplifiers with gains low enough to avoid coupling problems are then sufficient to perform the annealing process.
  • An ⁇ T-stage LFSR creates a PRBS of maximal length, 2 N — 1, when the feedback taps are chosen appropriately.
  • One useful property of such a PRBS is that it has cross correlation — 1/
  • This shifting could be accomplished by using a collection of identical LFSR s, one per neuron . Each would be loaded with a specified initial state to obtain a desired shift relative to the other LFSR s. All LFSRs would be clocked simultaneously. The overhead of such an approach, however, is unacceptable. For instance, a single 25-stage shift register (with a maximal period of 34 million clock cycles) would require approximately 400,000 square microns in 2 micron CMOS technology, which is considerably larger even than the thermal noise amplifier of the prior art implementation in the same technology.
  • An object of the present invention is reduce to a minimum the hardware necessary to generate multiple pseudo-random noise sources required for annealing in neural networks.
  • An additional object of the present invention is to amortize the space required for a single generator of plural noise sources amongst many neurons in a neural network so that an acceptable small area overhead for VLSI implementations results.
  • a single maximal length linear feedback shift register is used to generate multiple, arbitrarily-shifted, pseudo-random bit streams.
  • Each bit stream is converted to an analog noise source by filtering.
  • each bit stream is obtained by tapping the outputs of selected LFSR cells and feeding these tapped cell outputs through a parity tree consisting of exclusive-OR gates.
  • the particular cells of the LFSR tapped to form each bit stream are selected to meet certain constraints.
  • the taps are chosen so that: (1) the shift variation between bit streams is within a set limit; (2) each cell is tapped to provide an input to no fewer than and no greater than preset numbers of bit streams; and (3) each bit stream is formed from no fewer than and no greater than preset numbers of cell outputs.
  • An advantage of the present invention is that the number of cells needed to produce P bit streams grows as log( P ) rather than linearly with P.
  • FIG. 1 is a schematic diagram of a conventional prior art linear feedback shift register used to make an analog noise source
  • FIG . 2 is a schematic diagram of a single linear feedback shift register used to generate multiple pseudo-random bit streams in accordance with the present invention.
  • the single /V-stage LFSR 101 also denoted Y in the equations derived hereinbelow, consists of N clocked D-type flip-flops 102-(N-1) - 102-0.
  • the N stages also called cells, are arrayed horizontally with the shift direction from left to right, i.e. , the input of every cell except the leftmost cell is connected directly to the output of the cell on its left.
  • the cells are numbered consecutively from (_V - 1) to 0, with the (.V - l)th cell, 102-(N-1), on the left and the zeroth cell, 102-0, on the right.
  • the signal fed to the D input of the (N - l)th (leftmost) cell, 102- (N-l) , is obtained from the feedback function H.
  • This is the modulo 2 sum of the outputs belonging to a subset of the N cells, that is,
  • Exclusive-OR gate 103 forms the modulo 2 sum of the two fed back outputs of cells 102-0 and 102-3. The output of gate 103 provides the D-input to cell 102-(N-1).
  • To shift register Y 101 means to apply one or more clock pulses simultaneously to the CK clock inputs cells of Y 101.
  • the clock is not shown.
  • the PRBS generated by Y is, by definition, the sequence of bits generated by the zeroth (rightmost) cell, one bit per clock cycle, as Y is shifted.
  • the sequence of states that Y evolves through as it is shifted is determined by the initial state and the feedback function H .
  • the PRBS for a given LFSR depends on its initial state. If Y sequences through all possible nonzero states whenever it starts in a nonzero initial state, Y is said to be maximal. Maximality occurs only for certain choices of the feedback coefficients c,-, namely, if the polynomial c(x), where c(x) is defined by the expression
  • N-maximal PRBS A PRBS generated by a maximal N-stage LFSR starting in a nonzero initial state is called an N-maximal PRBS.
  • the pseudo-random bit sequence is taken at the Q output of the rightmost cell, 102-0.
  • This digital bit sequence on lead 104 is processed by a low pass filter having a cutoff frequency just a few percent of the clock frequency, and consisting of resistor 105 and capacitor 106..
  • An essentially Gaussian analog pseudo-random noise source is thus created at output 107.
  • LFSR consists of ⁇ cells, 202-( ⁇ -l) - 202-0.
  • Feedback is provided to the D input of cell 202-(N-l) as determined by a primitive polynomial of the N-stage register.
  • feedback is provided in this illustrative example from the Q outputs of the 0th and 3rd cells, 202-0 and 202-3, respectively, which are modulo 2 summed by exclusive-OR gate 203.
  • these particular cells are selected just for purposes of illustration.
  • the cells tapped can be chosen such that in addition to meeting a shift constraint, other constraints can be met that affect the physicality of a VLSI implementation.
  • the number of bit streams that can be generated from the single LFSR is not limited to the number of cells in the shift register.
  • P sources of random Gaussian noise are generated.
  • these noise sources are generated from P pseudo-random bit streams, which are shifted versions of each other, by modulo 2 combining the Q outputs of selected cells in the register.
  • the first bit stream on lead 205-1 is produced from the modulo 2 combination of the Q outputs of cells 202-0, 202-1, and 202-3 which are combined by exclusive-OR gates 206-1,1 and 206-1,2.
  • the bit stream on lead 205-1 is low-pass filtered by the RC filter, consisting of resistor 207-1 and capacitor 208-1, to produce the random noise source on lead 209-1.
  • the other noise sources on leads 205-j, for 2 ⁇ j ⁇ P, are similarly produced by modulo 2 combining, through exclusive-OR gates 206-j, 1 and 206-j,2, the outputs of selected of the cells.
  • the resultant bit stream is then filtered through a low-pass filter consisting of resistor 207-j and capacitor 208-j, to produce random noise at output
  • each output bit stream is generated from three cell outputs.
  • the minimum and maximum number of cells needed to be tapped to form any of the bit streams from the LFSR is a factor that can be controlled in selecting the tap patterns.
  • the minimum and maximum number of taps on any one cell in the LFSR is controllable.
  • a 0 denote an N-maximal PRBS.
  • a m is obtained from A 0 by shifting forward in time by m clock cycles.
  • Lemma 1 Let m and n be nonnegative integers. Let B — ⁇ bo » bi » b 2 » ' ' ' ⁇ denote the sequence obtained by a bitwise exclusive-OR of A m € S and Apreparing € S, that is, b ( ⁇ a m ⁇ i + a n +i ( mod 2 ) . Then B € S.
  • the first N bits of B cannot all be zero (otherwise, Eq. (3) would imply that B is the all-zero sequence) .
  • a o is an N-maximal PRBS, all possible combinations of N consecutive bits except the all-zero combination must occur in A Q.
  • there must be some nonnegative r such that the first N bits of A r equal the first N bits of B.
  • a Q is periodic with period 2 ⁇ r — 1 , there is no loss of generality in assuming r ⁇ 2 N - 1.
  • B A r € S. Q.E.D.
  • Lemma 1 is a special case of the more general Abelian group property of S under bitwise modulo 2 addition.
  • a pair of taps from an LFSR gives two particular shifted sequences from a restricted set. Their exclusive-OR gives a third sequence by Lemma 1.
  • This sequence in turn, can be exclusive-OR 'ed with another tap to give still other shifted versions of the main sequence.
  • Lemma 1 thus implies that given a maximal LFSR generating a PRBS, the outputs of a collection of cells of this LFSR can be tapped and the mod 2 sum of these outputs taken to obtain a shifted version of the PRBS. The question arises whether any specified shift can be obtained by appropriate choice of the taps.
  • Lemma 2 hereinbelow answers this question in the affirmative.
  • Lemma 2 Let Y denote an N-stage maximal LFSR that is initialized to a nonzero state, and let z ⁇ , 0 ⁇ i ⁇ N — 1, k ⁇ 0, denote the output of cell i of Y at clock cycle k.
  • ⁇ N denotes the set of N-dimensional vectors with components 0 and 1.
  • F can be identified with GF( 2 ).
  • bit streams should be shifted far enough apart so that the network can settle without seeing a shifted version of a noise source in two places. This implies close to equal spacing of the bit streams. In practice, this constraint can be relaxed considerably or eased by simply increasing the shift register size.
  • the fan-out per cell is limited; that is, loading any flip-flop in the register more than is necessary should be avoided.
  • Y denote a maximal N-stage LFSR
  • p ⁇ 2 N — 1 denote the period of the PRBS A Q generated by Y for some specified nonzero initial state.
  • L be a nonnegative integer
  • L , F_, F , and P be positive integers
  • r be a real number such that 0 ⁇ r ⁇ 1.
  • d ⁇ , dj , • • • • , dp_j ⁇ F ⁇ denote a collection of P tap coefficient vectors to be determined, and let G.- ⁇ .
  • S denote the sequence corresponding to d f , as in the proof of Lemma 2.
  • Two vectors, 1 ⁇ IL N and f € R ⁇ , both of which have integer-valued components, are associated with a given collection of tap coefficient vectors d 0 , di , • • • , d _j ⁇ F N .
  • the component ,- of 1 is the number of taps connected to cell i of Y.
  • the component f t of f is the number of Is in (i.e. , the number of cell taps represented by) the tap vector d f .
  • No cell of Y has fewer than L_ taps or more than L taps ( ⁇ l t ⁇ L for
  • the integer L is the aforenoted minimum (resp. , maximum ) allowed cell load.
  • No tap coefficient vector d,- has fewer than F components equal to 1 or more than F components equal to 1 (F ⁇ f ⁇ F for 0 ⁇ i ⁇ P — 1) .
  • the integer F (resp., F) is the aforenoted minimum (resp., maximum ) allowed fan -in. Note: if an N X P matrix is formed such that column i equals vector d,-, then condition 2 says that no row has fewer than Is or more than L Is, and condition 3 says that no column has fewer than F Is or more than F Is.
  • the cost function C is chosen so that minimizing it tends to minimize the components of 1, f, and u. Minimizing the components of 1 alleviates the speed degradation caused by capacitive loading on the cells of Y. Minimizing f minimizes the fan-in (number of inputs) of the exclusive-OR gates whose outputs form the bit streams.
  • state transition matrix M is defined as follows:
  • I ( t f -i ) ⁇ ( w-i ) denotes the (N — l) x (N — 1) identity matrix
  • 0 # _ ⁇ denotes the (N — l)-component all-zero column vector
  • the c t are the feedback coefficients from Eq. (1) .
  • Lemma 3 hereinbelow says that the taps for a given shift t are obtained explicitly by merely calculating the matrix M' and inspecting its first row.
  • Lemma 3 Let Y denote a maximal LFSR initialized in a nonzero state and with state transition matrix M. Let t be a nonnegative integer. Then the tap coefficient vector d for Y that gives a shift forward in time by t clock cycles is the transpose of the first row of the matrix M'. Proof: Let z k denote the vector with components z
  • the set of essential ⁇ T-tap patterns is defined to be the smallest subset from which all _?-tap patterns can be obtained by right-shifting a pattern from this subset by zero or more positions. When right-shifting a pattern, zeros are padded on the left.
  • bit stream shifts for the essential __T-tap patterns are found, the bit stream shifts for all other K-tn ⁇ p patterns can be found trivially. For example, if the shift of 1010000000 is q, then the shift of 0001010000 is q - 3 because the latter pattern is obtained from the former by right-shifting three bit positions.
  • Finding the shift associated with each d € X can take significant CPU time.
  • One straightforward way to do this is a method called simple shifting.
  • an efficient representation Y of the shift register is implemented using the word operations of the host computer.
  • the first N bits of the sequence G corresponding to a given tap coefficient vector d can be calculated easily using Y.
  • g € F ⁇ denote the first N bits of G.
  • g represents the state of Y at the clock cycle that equals the shift of G.
  • Y is shifted one clock cycle at a time until its state is found to equal g .
  • the clock cycle where this equality occurs is the shift associated with d.
  • the simple shifting method uses 0( 1 ) (i.e. , constant) memory and 0( 2 N ) CPU time. It can exact a large time penalty for practical problems. For example, a maximal 25-stage shift register has a sequence length of 34 million clock cycles. Thus, it would be expected that it would be necessary to shift Y an average of 17 million times for each d € X. In practice, however, it has been found that simple shifting is too slow for problems of "practical" size, i.e., when the shift register has more than about 20 cells.
  • Shanks' giant step/baby step method (see, for example, D . E . Knuth, The Art of Computer Programming, Vol. Ill: Sorting and Searching. Reading, MA: Addison-Wesley, 1973, p. 9.)
  • Shanks' giant step/baby step method (see, for example, D . E . Knuth, The Art of Computer Programming, Vol. Ill: Sorting and Searching. Reading, MA: Addison-Wesley, 1973, p. 9.)
  • bit patterns representing the states of the shift register at uniformly-spaced clock cycle intervals.
  • d the associated shift register state g is calculated, as was done for the simple shifting method.
  • the shift register representation Y is started in the state g . It is then shifted one clock cycle at a time until its state is found to equal one of the bit patterns stored in the table.
  • the shift associated with d is then the shift of the table bit pattern less the number of shifts needed to bring Y to that state.
  • this method proceeds as follows.
  • a "reasonable" giant step size h is chosen.
  • a small h implies a fast calculation of the shift for each tap pattern, but the cost in memory usage and table setup time grows as h becomes smaller. Therefore, a compromise value of h must be chosen.
  • h — 5000 might be chosen.
  • a hash table is filled with records, each containing the integer ih and the bit pattern M a z° for some specified nonzero initial state z°.
  • Y denote an efficient representation of the shift register
  • d denote a tap pattern
  • g * denote the first N bits of the bit stream corresponding to d when the initial state of Y is z°.
  • Y is initialized to the state g * .
  • counter r is initialized to zero. Then t is found as follows:
  • a listing of the program appears in APPENDIX A .
  • the user inputs the number of cells in the register, the feedback pattern, and the number of bit streams required. Also input is the maximum and minimum allowable loading on a cell, the maximum and minimum allowed fan-in, and the maximum allowed shift variation.
  • weighting factors are assigned to the u, 1, and f components, which are also specified by the user.
  • the user specifies the coefficients of a penalty function used when a potential solution falls outside the specified ranges.
  • the program was used to derive the tap patterns for 32 bit streams as generated from a 25-stage shift register. Since a 25-stage shift register produces a PRBS of maximal length 33,554,432 C 2 25 - 1 ) , the time separation between bit streams is approximately one million clock cycles.
  • Each tap pattern line in TABLE I indicates the cells to be tapped to produce the bit stream having the particular shift.
  • the first bit stream is generated from the modulo 2 combination from the outputs of the cells 9, 13, and 21, the cells being numbered from 0 to 24 from right to left, as hereinabove.
  • each bit stream is separated from repetition by its nearest neighbor by approximately 10 milliseconds.
  • Each bit stream is low pass filtered to about 5 MHz.
  • An anneal cycle of 10 microseconds would therefore have about 50 analog zero crossings.
  • each neuron would see noise that would not be repeated anywhere else in the network for about 1000 anneal cycles which is a substantially greater separation than is required.
  • This same LFSR could conceivably be used for 1000 times as many neurons. For neural network applications, therefore, shift spacing is less important for design than fan-in or fan-out considerations.
  • the hardware advantage of the present invention is particularly important when such large numbers of bit streams need to be generated.
  • the number of cells in the shift register grows as log(P ), where P is the number of bit streams.
  • the hardware requirement for prior art methods grows directly with P.
  • the hardware advantage of the present invention will be significant.
  • bit-error rate testers use a pseudo-random bit stream to test communication systems at high speed. The speed is limited by the rate at which the shift register can be clocked. By providing multiple uncorrelated noise sources and then multiplexing them, a new pseudo ⁇ random bit stream at higher speed can be provided because a multiplexer can operate faster than a shift register in a given technology.
  • the bit-error rate tester can provide multiple outputs for parallel testing, which is generally not available in currently available equipment .

Landscapes

  • Engineering & Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • Theoretical Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • Health & Medical Sciences (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Biomedical Technology (AREA)
  • Biophysics (AREA)
  • Neurology (AREA)
  • Mathematical Physics (AREA)
  • General Health & Medical Sciences (AREA)
  • Molecular Biology (AREA)
  • Computing Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Computational Linguistics (AREA)
  • Evolutionary Computation (AREA)
  • Software Systems (AREA)
  • Artificial Intelligence (AREA)
  • Computational Mathematics (AREA)
  • Mathematical Analysis (AREA)
  • Mathematical Optimization (AREA)
  • Pure & Applied Mathematics (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

Des trains binaires multiples pseudo-aléatoires décalés arbitrairement sont générés à partir d'un seul registre à décalage à réaction (LFSR) (201). On obtient chacun des trains de bits par piquage des sorties de cellules séléctionnées du registre (202) et par application desdites sorties de cellules à des portes OU exclusif (206). Les sorties sont séléctionnées afin d'effectuer le décalage désiré entre trains binaires. De plus, on peut séléctionner les configurations de sorties de sorte que le nombre d'entrées (facteurs pyramidaux d'entrée) de chaque train binaire soit situé dans des limites prédétérminées et que le nombre de piquages par cellule (charge de cellule) soit situé dans des limites prédéterminées. Un programme informatique présenté génère les configurations de sorties en fonction du nombre de cellules et de la structure du registre, du nombre de trains binaires de sortie, de la variation de décalage maximum autorisée des trains binaires, et des limites de facteur pyramidal d'entrée et de charge de cellule. Chaque train binaire pseudo-aléatoire sert d'entrée à un filtre passe-bas qui produit une sortie de bruit essentiellement gaussien. Les sorties de bruit multiples sont sans rapport direct et peuvent être utilisées au sein d'un réseau neuronal à apprentissage stochastique parallèle pour des traitements comme le recuit.
PCT/US1990/004407 1989-12-21 1990-08-07 Generateur de sources de bruit multiples independantes WO1991010182A1 (fr)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US454,763 1982-12-30
US45476389A 1989-12-21 1989-12-21

Publications (1)

Publication Number Publication Date
WO1991010182A1 true WO1991010182A1 (fr) 1991-07-11

Family

ID=23805984

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/US1990/004407 WO1991010182A1 (fr) 1989-12-21 1990-08-07 Generateur de sources de bruit multiples independantes

Country Status (1)

Country Link
WO (1) WO1991010182A1 (fr)

Cited By (18)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
GB2353155A (en) * 1999-08-05 2001-02-14 Mitsubishi Electric Inf Tech A random binary signal generator with a narrowed autocorrelation function
EP1242859A1 (fr) * 1999-11-23 2002-09-25 Mentor Graphics Corporation Procede de synthese de machines d'etats finis lineaires
US7263641B2 (en) 1999-11-23 2007-08-28 Janusz Rajski Phase shifter with reduced linear dependency
US7302624B2 (en) 2003-02-13 2007-11-27 Janusz Rajski Adaptive fault diagnosis of compressed test responses
US7370254B2 (en) 2003-02-13 2008-05-06 Janusz Rajski Compressing test responses using a compactor
US7437640B2 (en) 2003-02-13 2008-10-14 Janusz Rajski Fault diagnosis of compressed test responses having one or more unknown states
US7478296B2 (en) 1999-11-23 2009-01-13 Janusz Rajski Continuous application and decompression of test patterns to a circuit-under-test
US7493540B1 (en) 1999-11-23 2009-02-17 Jansuz Rajski Continuous application and decompression of test patterns to a circuit-under-test
US7500163B2 (en) 1999-11-23 2009-03-03 Janusz Rajski Method and apparatus for selectively compacting test responses
US7506232B2 (en) 1999-11-23 2009-03-17 Janusz Rajski Decompressor/PRPG for applying pseudo-random and deterministic test patterns
US7509546B2 (en) 1999-11-23 2009-03-24 Janusz Rajski Test pattern compression for an integrated circuit test environment
US7509550B2 (en) 2003-02-13 2009-03-24 Janusz Rajski Fault diagnosis of compressed test responses
US7818644B2 (en) 2006-02-17 2010-10-19 Janusz Rajski Multi-stage test response compactors
US9134370B2 (en) 1999-11-23 2015-09-15 Mentor Graphics Corporation Continuous application and decompression of test patterns and selective compaction of test responses
US9664739B2 (en) 1999-11-23 2017-05-30 Mentor Graphics Corporation Continuous application and decompression of test patterns and selective compaction of test responses
WO2020025252A1 (fr) * 2018-07-31 2020-02-06 Telefonaktiebolaget Lm Ericsson (Publ) Procédé, émetteur, structure, émetteur-récepteur et point d'accès pour la fourniture d'un signal de modulation par tout ou rien multiporteuse
WO2020025253A1 (fr) * 2018-07-31 2020-02-06 Telefonaktiebolaget Lm Ericsson (Publ) Structure, procédé, émetteur, émetteur-récepteur et point d'accès appropriés pour une mise en œuvre à faible complexité
US11281431B2 (en) * 2019-01-24 2022-03-22 Fujitsu Limited Random number generating circuit and semiconductor apparatus

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3811038A (en) * 1971-09-15 1974-05-14 Int Computers Ltd Pseudo-random number generators
US3881099A (en) * 1972-12-15 1975-04-29 Lannionnais Electronique Pseudo-random binary sequence generator
US4325129A (en) * 1980-05-01 1982-04-13 Motorola Inc. Non-linear logic module for increasing complexity of bit sequences
US4748576A (en) * 1984-02-06 1988-05-31 U.S. Philips Corporation Pseudo-random binary sequence generators

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US3811038A (en) * 1971-09-15 1974-05-14 Int Computers Ltd Pseudo-random number generators
US3881099A (en) * 1972-12-15 1975-04-29 Lannionnais Electronique Pseudo-random binary sequence generator
US4325129A (en) * 1980-05-01 1982-04-13 Motorola Inc. Non-linear logic module for increasing complexity of bit sequences
US4748576A (en) * 1984-02-06 1988-05-31 U.S. Philips Corporation Pseudo-random binary sequence generators

Cited By (41)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7145933B1 (en) 1999-08-05 2006-12-05 Mitsubishi Denki Kabushiki Kaisha Method and apparatus for generating random signals
GB2353155A (en) * 1999-08-05 2001-02-14 Mitsubishi Electric Inf Tech A random binary signal generator with a narrowed autocorrelation function
US7493540B1 (en) 1999-11-23 2009-02-17 Jansuz Rajski Continuous application and decompression of test patterns to a circuit-under-test
US7523372B2 (en) 1999-11-23 2009-04-21 Janusz Rajski Phase shifter with reduced linear dependency
US7260591B2 (en) 1999-11-23 2007-08-21 Janusz Rajski Method for synthesizing linear finite state machines
US7263641B2 (en) 1999-11-23 2007-08-28 Janusz Rajski Phase shifter with reduced linear dependency
EP1242859A1 (fr) * 1999-11-23 2002-09-25 Mentor Graphics Corporation Procede de synthese de machines d'etats finis lineaires
US9664739B2 (en) 1999-11-23 2017-05-30 Mentor Graphics Corporation Continuous application and decompression of test patterns and selective compaction of test responses
US10234506B2 (en) 1999-11-23 2019-03-19 Mentor Graphics Corporation Continuous application and decompression of test patterns and selective compaction of test responses
US7478296B2 (en) 1999-11-23 2009-01-13 Janusz Rajski Continuous application and decompression of test patterns to a circuit-under-test
US9134370B2 (en) 1999-11-23 2015-09-15 Mentor Graphics Corporation Continuous application and decompression of test patterns and selective compaction of test responses
US7500163B2 (en) 1999-11-23 2009-03-03 Janusz Rajski Method and apparatus for selectively compacting test responses
US7506232B2 (en) 1999-11-23 2009-03-17 Janusz Rajski Decompressor/PRPG for applying pseudo-random and deterministic test patterns
US7509546B2 (en) 1999-11-23 2009-03-24 Janusz Rajski Test pattern compression for an integrated circuit test environment
EP2144134A1 (fr) * 1999-11-23 2010-01-13 Mentor Graphics Corporation Procédé de synthèse de machines linéaires à état fini
EP1242859A4 (fr) * 1999-11-23 2006-01-11 Mentor Graphics Corp Procede de synthese de machines d'etats finis lineaires
US7509550B2 (en) 2003-02-13 2009-03-24 Janusz Rajski Fault diagnosis of compressed test responses
US7743302B2 (en) 2003-02-13 2010-06-22 Janusz Rajski Compressing test responses using a compactor
US7437640B2 (en) 2003-02-13 2008-10-14 Janusz Rajski Fault diagnosis of compressed test responses having one or more unknown states
US7370254B2 (en) 2003-02-13 2008-05-06 Janusz Rajski Compressing test responses using a compactor
US7302624B2 (en) 2003-02-13 2007-11-27 Janusz Rajski Adaptive fault diagnosis of compressed test responses
US8418007B2 (en) 2006-02-17 2013-04-09 Mentor Graphics Corporation On-chip comparison and response collection tools and techniques
US8914694B2 (en) 2006-02-17 2014-12-16 Mentor Graphics Corporation On-chip comparison and response collection tools and techniques
US9250287B2 (en) 2006-02-17 2016-02-02 Mentor Graphics Corporation On-chip comparison and response collection tools and techniques
US7913137B2 (en) 2006-02-17 2011-03-22 Mentor Graphics Corporation On-chip comparison and response collection tools and techniques
US9778316B2 (en) 2006-02-17 2017-10-03 Mentor Graphics Corporation Multi-stage test response compactors
US10120024B2 (en) 2006-02-17 2018-11-06 Mentor Graphics Corporation Multi-stage test response compactors
US7818644B2 (en) 2006-02-17 2010-10-19 Janusz Rajski Multi-stage test response compactors
KR20210028730A (ko) * 2018-07-31 2021-03-12 텔레호낙티에볼라게트 엘엠 에릭슨(피유비엘) 멀티캐리어 온-오프 키잉 신호의 프로비전을 위한 방법, 송신기, 구조체, 트랜시버 및 액세스 포인트
WO2020025253A1 (fr) * 2018-07-31 2020-02-06 Telefonaktiebolaget Lm Ericsson (Publ) Structure, procédé, émetteur, émetteur-récepteur et point d'accès appropriés pour une mise en œuvre à faible complexité
WO2020025252A1 (fr) * 2018-07-31 2020-02-06 Telefonaktiebolaget Lm Ericsson (Publ) Procédé, émetteur, structure, émetteur-récepteur et point d'accès pour la fourniture d'un signal de modulation par tout ou rien multiporteuse
JP2021532666A (ja) * 2018-07-31 2021-11-25 テレフオンアクチーボラゲット エルエム エリクソン（パブル） 低複雑度実装に好適な構造、方法、送信機、トランシーバおよびアクセスポイント
RU2761280C1 (ru) * 2018-07-31 2021-12-06 Телефонактиеболагет Лм Эрикссон (Пабл) Структура, способ, передающее устройство, приемо-передающее устройство и точка доступа, подходящие для реализации с низкой сложностью
US11362869B2 (en) 2018-07-31 2022-06-14 Telefonaktiebolaget Lm Ericsson (Publ) Method, transmitter, structure, transceiver and access point for provision of multi-carrier on-off keying signal
US11398935B2 (en) 2018-07-31 2022-07-26 Telefonaktiebolaget Lm Ericsson (Publ) Structure, method, transmitter, transceiver and access point suitable for low-complexity implementation
JP2022160416A (ja) * 2018-07-31 2022-10-19 テレフオンアクチーボラゲット エルエム エリクソン（パブル） マルチキャリアオンオフキーイング信号の提供のための方法、送信機、構造、トランシーバおよびアクセスポイント
KR102463555B1 (ko) * 2018-07-31 2022-11-07 텔레호낙티에볼라게트 엘엠 에릭슨(피유비엘) 멀티캐리어 온-오프 키잉 신호의 프로비전을 위한 방법, 송신기, 구조체, 트랜시버 및 액세스 포인트
US11750425B2 (en) 2018-07-31 2023-09-05 Telefonaktiebolaget Lm Ericsson (Publ) Method, transmitter, structure, transceiver and access point for provision of multi-carrier on-off keying signal
EP4270173A3 (fr) * 2018-07-31 2024-01-10 Telefonaktiebolaget LM Ericsson (publ) Procédé, émetteur, émetteur-récepteur et point d'accès pour la fourniture d'un signal de modulation par tout ou rien multiporteuse
US12028195B2 (en) 2018-07-31 2024-07-02 Telefonaktiebolaget Lm Ericsson (Publ) Method, transmitter, structure, transceiver and access point for provision of multi-carrier on-off keying signal
US11281431B2 (en) * 2019-01-24 2022-03-22 Fujitsu Limited Random number generating circuit and semiconductor apparatus

Similar Documents

Publication Publication Date Title
WO1991010182A1 (fr) Generateur de sources de bruit multiples independantes
Hortensius et al. Parallel random number generation for VLSI systems using cellular automata
Serra et al. The analysis of one-dimensional linear cellular automata and their aliasing properties
EP0240546B1 (fr) Generateurs de sequences aleatoires
Chattopadhyay et al. Highly regular, modular, and cascadable design of cellular automata-based pattern classifier
Tsalides et al. Pseudorandom number generators for VLSI systems based on linear cellular automata
EP1782181A1 (fr) Procede et dispositif pour generer des donnees aleatoires
EP1776757A1 (fr) Generation de nombres aleatoires basee sur des circuits logiques avec retraction
JPH0682528A (ja) 制御可能な重み付き２進シーケンスを発生するための回路
O'Reilly Series-parallel generation of m-sequences
WO2010034326A1 (fr) Machine à états et générateur pour produire une description d'une fonction de rétroaction d'une machine à états
US8023649B2 (en) Method and apparatus for cellular automata based generation of pseudorandom sequences with controllable period
US6560727B1 (en) Bit error rate tester using fast parallel generation of linear recurring sequences
US7263540B1 (en) Method of generating multiple random numbers
JP2940517B2 (ja) 非線形フィードバック・シフトレジスタ回路
Ackermann et al. Parallel random number generator for inexpensive configurable hardware cells
US20030078951A1 (en) Random number generators implemented with cellular array
Salehi Area-efficient lfsr-based stochastic number generators with minimum correlation
Hortensius et al. Importance sampling for Ising computers using one-dimensional cellular automata
US4998263A (en) Generation of trigger signals
US6910057B2 (en) Truth table candidate reduction for cellular automata based random number generators
Spencer Pseudorandom Bit Generators from Enhanced Cellular Automata.
PV et al. Design and implementation of efficient stochastic number generator
Abdellatef et al. Characterization of correlation in stochastic computing functions
RU2427885C1 (ru) Быстродействующий генератор случайных перестановок и сочетаний

Legal Events

Date Code Title Description
AK Designated states

Kind code of ref document: A1

Designated state(s): JP

AL Designated countries for regional patents

Kind code of ref document: A1

Designated state(s): AT BE CH DE DK ES FR GB IT LU NL SE