• A construction for strength-3...

Treffer: A construction for strength-3 covering arrays from linear feedback shift register sequences

Title:
A construction for strength-3 covering arrays from linear feedback shift register sequences
Authors:
RAAPHORST, Sebastian, MOURA, Lucia, STEVENS, Brett
Source:
Designs, codes and cryptography. 73(3):949-968
Publisher Information:
New York, NY: Springer, 2014.
Publication Year:
2014
Physical Description:
print, 34 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Security, safety, Sécurité (multidisciplinaire, général), Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Combinatoire. Structures ordonnées, Combinatorics. Ordered structures, Combinatoire, Combinatorics, Plans d'expériences et configurations, Designs and configurations, Analyse combinatoire, Combinatorial analysis, Análisis combinatorio, Borne supérieure, Upper bound, Cota superior, Corps fini, Finite field, Campo finito, Facteur qualité, Q factor, Factor calidad, Méthode combinatoire, Combinatorial method, Método combinatorio, Méthode récursive, Recursive method, Método recursivo, Méthode simplicielle, Simplicial method, Método simplicial, Plan bloc, Block design, Plan bloque, Plan expérience, Experimental design, Plan experiencia, Polynôme primitif, Primitive polynomial, Polinomio primitivo, Registre décalage, Shift register, Registro dispersión, Rétroaction, Feedback regulation, Retroacción, Complexe simplicial, Simplicial complex, Complejo simplicial, Plan orthogonal, Orthogonal array, Diseño ortogonal, Plan recouvrement, Covering designs, Diseño recubrimiento, 05B05, 05B15, 05B40, Combinatorial designs, Covering arrays, Linear feedback shift registers, Variable strength orthogonal arrays
Document Type:
Fachzeitschrift Article
File Description:
text
Language:
English
Author Affiliations:
School of Electrical Engineering and Computer Science, University of Ottawa, 800 King Edward Avenue, Ottawa, ON K1K 6N5, Canada
School of Mathematics and Statistics, Carleton University, 1125 Colonel By Drive, Ottawa, ON K1S 5B6, Canada
ISSN:
0925-1022
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=28700887
Rights:
Copyright 2015 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Mathematics
Accession Number:
edscal.28700887
Database:
PASCAL Archive

Weitere Informationen

We present a new construction for covering arrays inspired by ideas from Munemasa (Finite Fields Appl 4:252-260, 1998) using linear feedback shift registers (LFSRs). For a primitive polynomial f of degree m over Fq, by taking all unique subintervals of length qm-1/q-1 from the LFSR generated by f, we derive a general construction for optimal variable strength orthogonal arrays over an infinite family of abstract simplicial complexes. For m = 3, by adding the subintervals of the reversal of the LFSR to the variable strength orthogonal array, we derive a strength-3 covering array over q2 + q + 1 factors, each with q levels that has size only 2q3 - 1, i.e. a CA(2q3 - 1; 3, q2 + q + 1, q) whenever q is a prime power. When q is not a prime power, we obtain results by using fusion operations on the constructed array for higher prime powers and obtain improved bounds. Colbourn maintains a repository of the best known bounds for covering array sizes for all 2 ≤ q ≤ 25. Our construction, with fusing when applicable, currently holds records of the best known upper bounds in this repository for all q except q = 2, 3, 6. By using these covering arrays as ingredients in recursive constructions, we build covering arrays over larger numbers of factors, again providing significant improvements on the previous best upper bounds.