Browse Prior Art Database

Method for Generation of Well-Distributed Sequences

IP.com Disclosure Number: IPCOM000039395D
Original Publication Date: 1987-Jun-01
Included in the Prior Art Database: 2005-Feb-01
Document File: 2 page(s) / 24K

Publishing Venue

IBM

Related People

Tezuka, S: AUTHOR

Abstract

This article describes a new method for generation of well-distributed sequences. A well-distributed sequence is an infinite [0,1] sequence whose initial N segments satisfy the following condition, for any N and k, where v(N) denotes the number of the elements that belong to any region [m/2k, (m+1)/2k), m=0,1,...,2k-1]. The proposed method for generation of such sequences is described in detail in the following. Let Wp be a p x p 0-1 matrix. W1 = 1, and Wp(p=2,3,...) is defined as follows. where (bij, j=1,2,...,p) for i=1,2,... are arbitrary binary patterns. Thus, the following sequence U1, U2,..., is well-distributed. (Image Omitted) Here, T(a1,a2,...,ap) = Wp T(i1,i2,...,ip), where the binary representation of i is given as (i1,i2,..., ip)2, and operations are done over GF(2).

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 100% of the total text.

Page 1 of 2

Method for Generation of Well-Distributed Sequences

This article describes a new method for generation of well-distributed sequences. A well-distributed sequence is an infinite [0,1] sequence whose initial N segments satisfy the following condition, for any N and k, where v(N) denotes the number of the elements that belong to any region [m/2k, (m+1)/2k), m=0,1,...,2k-1]. The proposed method for generation of such sequences is described in detail in the following. Let Wp be a p x p 0-1 matrix. W1 = 1, and Wp(p=2,3,...) is defined as follows. where (bij, j=1,2,...,p) for i=1,2,... are arbitrary binary patterns. Thus, the following sequence U1, U2,..., is well-distributed.

(Image Omitted)

Here, T(a1,a2,...,ap) = Wp T(i1,i2,...,ip), where the binary representation of i is given as (i1,i2,..., ip)2, and operations are done over GF(2). The most important application of well-distributed sequences is the construction of Wald sequences, which is an ideally random sequence in a sense [*]. The drawing shows the generation of Wald sequences from well-distributed sequences. The way of choice of a set of subsequence rules is discussed in [*]. The proposed method will provide so many different well-distributed sequences that a resultant Wald sequence will have better quality. Reference D. E. Knuth, The Art of Computer Programming, 2, 142-177, Addison Wesley Publishing Co.

1

Page 2 of 2

2

[This page contains 2 pictures or other non-text objects]