Browse Prior Art Database

DIGITAL RANDOMIZER COMBINING CELLULAR AUTOMATA AND LINEAR FEEDBACK SHIFT REGISTERS

IP.com Disclosure Number: IPCOM000009022D
Original Publication Date: 1999-Jan-01
Included in the Prior Art Database: 2002-Aug-01
Document File: 7 page(s) / 324K

Publishing Venue

Motorola

Related People

Ezzy Dabbish: AUTHOR [+5]

Abstract

Pseudo-random sequences are often generated using a Linear Feedback Shift Register (LFSR). It is well known that an LFSR can be designed to gen- erate pseudo-random sequences with statistically good randomness properties. Another type of pseu- do-random sequence generator that has more recent- ly been investigated is known as Cellular Automata Shift Register (CASR). Linear cellular automata shift registers have been found to provide better pseudo-random sequences than LFSRs. The ran- dom number generator described in this paper com- bines an LFSR and CA into a new type of random number generator circuit.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 21% of the total text.

Page 1 of 7

MO-LA Technical Developments

DIGITAL RANDOMIZER COMBINING CELLULAR AUTOMATA

AND LINEAR FEEDBACK SHIFT REGISTERS

by Euy Dabbish, Ann Dahlien, Tom Messerges, Steve Tugenberg and Greg Bare

ABSTRACT

  Pseudo-random sequences are often generated using a Linear Feedback Shift Register (LFSR). It is well known that an LFSR can be designed to gen- erate pseudo-random sequences with statistically good randomness properties. Another type of pseu- do-random sequence generator that has more recent- ly been investigated is known as Cellular Automata Shift Register (CASR). Linear cellular automata shift registers have been found to provide better pseudo-random sequences than LFSRs. The ran- dom number generator described in this paper com- bines an LFSR and CA into a new type of random number generator circuit.

INTRODUCTION

  The production of random binary sequences is often useful in the fields of encryption and data compaction. Pseudo-random sequence generators can be used in many applications, but often it is desirable to generate truly random data. Due to the nature of digital logic it can be difficult to generate truly random binary sequences. Digital logic can always be described with deterministic equations that precisely predict the future state of the circuit, thus eliminating true random behavior. Truly ran- dom noise generators have been designed utilizing analog techniques such as amplification of thermal noise, but such devices cannot be easily implement- ed in standard cell or gate array integrated circuits. Most randomizers are built using discrete compo- nents. These components take up valuable space on a circuit board, so the ability to incorporate a ran- domizer on a single digital integrated chip is a big advantage.

  To generate a truly random source on a chip, some sort of physical attribute of the device, which varies over time, can be exploited. Examples of this include propagation delays which vary as a result of temperature and age, chip noise, or current draw.

  The circuit described in this paper can be used to generate truly random binary sequences. Due to an all-digital design, this new design also has the advantage of being easy to implement in a digital integrated circuit.

DESCRIPTION

  Pseudo-random sequences are often generated using a Linear Feedback Shift Register (LFSR). It is well known that an LFSR can be designed to gen- erate pseudo-random sequences with statistically good randomness properties. Another type of pseu- do-random sequence generator that has more recent- ly been investigated is known as Cellular Automata Shift Register (CASR). Linear cellular automata shift registers have been found to provide better pseudo-random sequences than LFSRs. The ran- dom number generator described in this paper is composed of six major components:

1. A linear feedback shift register (LFSR)
2. A cellular automata shift register (CASR)
3. An unpredictable clock source (ring oscillator)
4. A control unit
5. A power-on reset (P...