THE ANALYSIS OF ONE-DIMENSIONAL LINEAR CELLULAR AUTOMATA AND THEIR ALIASING PROPERTIES

被引：108

作者：

SERRA, M

SLATER, T

MUZIO, JC

MILLER, DM

机构：

[1] Department of Computer Science, University of Victoria, Victoria

来源：

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS | 1990年 / 9卷 / 07期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Applied linear algebra; automata theory; cellular automata (CA); linear feedback shift registers (LFSR's); pseudorandom pattern generators; signature analysis; testing; VLSI;

D O I：

10.1109/43.55213

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

The recent interest in one-dimensional linear hybrid cellular automata (CA) raised two outstanding questions, both of which are answered in this paper: how to construct a general linear hybrid cellular automata such that it has a maximum length cycle, and how the aliasing properties of such automata compare with linear feedback shift registers, when used as signature analyzers. This is accomplished by formally demonstrating the isomorphism which binds this kind of cellular automata to the linear feedback shift registers. Consequently these cellular automata can be analyzed as linear machines; linear algebraic techniques are applied appropriately for the transformations; and a useful search algorithm is developed which, given an irreducible characteristic polynomial, finds a corresponding linear hybrid cellular automata. Such cellular automata are tabulated for all irreducible and primitive polynomials up to degree 16, plus a selection of others of higher degree. © 1990 IEEE

引用

页码：767 / 778

页数：12

共 22 条

[1]

BARDELL PH, 1987, BUILT TEST VLSI

[2]

BIRKOFF G, 1985, SSURVEY MODERN ALGEB

[3]

DAMIANI M, 1989, APR P EUR TEST C, P346

[4]

Elspas B., 1959, IRE T CIRCUIT THEORY, V6, P45, DOI DOI 10.1109/TCT.1959.1086506

[5]

Horn R.A, 2012, MATRIX ANAL, V2nd ed.

[6] PARALLEL RANDOM NUMBER GENERATION FOR VLSI SYSTEMS USING CELLULAR AUTOMATA [J].

HORTENSIUS, PD ;

MCLEOD, RD ;

CARD, HC .

IEEE TRANSACTIONS ON COMPUTERS, 1989, 38 (10) :1466-1472

[7]

HORTENSIUS PD, 1988, 3RD TECHN WORKSH NEW

[8]

IVANOV A, 1988, JUN P INT S FAULT TO, P70

[9]

KAUTZ WH, 1965, LINEAR SEQUENTIAL SW

[10]

Knuth D.E., 1981, ART COMPUTER PROGRAM, V2

← 1 2 3 →