REF ID:A38876 

Cy. /.i.6 

----~- -~--

SCAMP~ 

...L ~ 

Wrn.F Friedman 

WORKING PAPERS - 195B 

@'pp roved for Release by NSA on 09-13-2013 pursuantto E .0. 1352a 

--- ....,..=:.. ~ 
REF ID:A38876 

NATIONAL SECURITY AGENCY 

FORT GEORGE G MEADE, MARYLAND 

Mr Wilham F. Friedman 

310 Second Street, S. E 

Washington 3, D C 

Dear Mr Friedman 

Serial· REMP-1-2.01 

30 October 1958 

The inclosed folder of unclassified 1958 SCAMP 

Workmg Papers, copy number 46, is for your convenience 

and retention 

Incl 

a/s 

Sincerely, 

AINA 

~~ V STENSON 

SCAMP Librarian 
I 

No. 11. 

No .. 15. 

No. 20. 

No .. 22. 

REF ID:A38876 

WORKING PAPERS 

CONTENTS 

The Blankinship Conjecture Examined •••••• J. D. Swift 

The Rand Corporation's Random 

Digit Generator •••••••••••••••••••••••••• H. P. Edmundson 

A Class of Mappings and Some Examples ••• G. A. Hedlund 

A Numerical Simulation to Study the Readings 

of a Fixed Antenna Adcock Radio Direction 

Finder Under Conditions of Fading ••••••••• J. F. Mount 

C. B. Tompkins 
--

-~ 

REF ID:A38876 

UNCLASSIFIED 

wmrnn PAPER NO. ll 

I 

".IBE BLANKINSHIP CONJEC'J.URE EX.AHlDD 

-; r --

J. n. Sw:Lft 

l Auge.st 1958 

ll. pages 

'Jhe period Of' X + l l.n (XJ' + l)/x + l !LS determined 

for '11 primes p < 288 for which p is a pl"Jl1dulve root. Tb.is 

is found to be p ~P';_J- - ~ for dl.l. emh pr:uaee except 37, J.Cll., 

197 ~ 269 :for which it is l/3 of' till.a val~ • 1'1.e four special 

cases gi.ve counter-examples f'or the COilJeC'hl.re that the period is 

aJ.wqs maximal. Some arguments tench.ng to show that the behav:i.or J.B 

consist;ent WJ. th 'random expectat.1 on' are gi van. 

s-110 ou 
REF ID:A38876 

'WORKING PAPER NO. 11 

THE BLANKINSHIP CONJECTURE EXAMINED 

J. D. Swift 

l August 1958 

ll pages 

1. Introductio~. For prl.lnes p having 2 as a pr1m1t:t.ve root, 

the cyclotomic polynomial 

(1) ) x? + 1 f'(x ... r x+ 

is irreducible over GF(2). It is also eVJ.dent. that, nth respect to 

this polyno:rrua.J.., x has order p • The question o:f tne order o:f the 

other linear polynomial in x , y -= x + l , arises. By various 

methods, one of which is included beloW"!' it is easy to see that the 

order of y is pn where n is a dlvisor of s = 'fil - l tfilera 

m = (p - 1)/2 • 

Dr. w. A. Blankinship has conjectured that n = s always. Tins 

conjecture was based on certain empirical evidence concerned with 

p < 100 • Tlie chief' pu:r;pose of this paper is to discuss a method by 

which the proposition was mvestigated for p < 288 • In particular 

the previous evidence was found t.o be fauJ. ty. The .rmaJ. results are 

that n = s for p = 3, 5, ll, 13, 19, 29, 53, 59, 61, 67, 83, 107, 

131, 139, 149, 163, 173, 179, 181, 211, 227; and that n = s/3 for 

p = 37, 101, 197, 269. 

S-110 Oll 
REF ID:A38876 

Certain tables wnich were of use :tn the mvestigation and, not 

being readily available elsewhere, roay be of some general interest, 

are included. 

2. :Jheoretic~ consider8:,~&1. Let the notation be as m the first 

paragraph or the introduction. Fu.rt.her,, let g(y) = r{x) ' i.e., 

(2) ( ) g y = ........ {z. _ + __.y l)P __ + 1 

_ • 

Then defl.ne z=x+ 

1 

x 

and let h(z) .. x·m r{x) • The degree of the 

polynomial h(z) is m 0 Now we Dl.d.:int'ainii The order of y with ---- -- resEect to r{x) is p times the order or z with !:aspect ~ h(z). 

Proof'o y

2 = {l + x) 2 "" 1 + x2 

= xz • The order of y2 J.S the 

same as the order of y smce both are certainly odd. '!'he order of x 

is p ; the order of z is prime to p • Hence the order of y is 

the order or x ti.Irias the order of z by the standard theorem on the 

orders or elements on a Galois Field. Finally if h{z) divides rzP - 1 

as a polynom:t..al in z , :u:. is clear that .f1 = 1 in tr...e GF{#) 

defined by f(x) • 

Thus t..11.e basic problem is reduoed to the evaluation of the order or z 

with respect to h(z) or, in other te:rnis, to finding the period 

of h(z) • 

Blank:lnsh.J.p' s conjecture 1s equiva1ent to the statements h(z) 

is primJ..tive irreducible. Now h(z) is certa.J..:nly irreduc.Lble for 

- 2 -
,.,., -

REF ID:A38876 

all degrees under considerat:J..ono Indeed h(z) may be irreducible 

When f(x) is reducible., This is the case, f'or example, when p = 7 • 

The condition for reducibility of h(z) is that the corresponding 

f(x) have a proper ~trie divisor. Thus in some vague sense h(z) 

is 'more than irreducible• and this idea gives some credence to tne 

conject.ure. It has, however.P been the generally observed fa.et that 

there is no simple cl1aracterization ar prinutive polynomals any more 

than there is a simple numerical fUnction Which always yields pr:unes. 

Indeed such :functions have a statistical property know as Kronecker's 

1f.vpothesis which states that the observed frequency of pr.unes will be 

asymptotically equal to th.at expected on elementB.ljf frequency considerationso 

Now how likely is a polynomcl.J to be pr:unitive? The number of 

pri:rro:tive po~onn.al.s is fd(s)/m while the number of irreducible 

polynonn.als is 

m ± (zn -

where the q1 are the pr:une .factors of m • 711.e ratio of these 

numbers for p "" 3, 5, ll, 13, 19, 29, and 37 is respectively, 1, 1, 

1, .67, .86, .65,, .$lt.. Othe1• flgures are given m a table at the end 

of the paper. Hence it is quite reasonable that 37 should be the 

first case of impnmtivity. Agam the number of po1.ynomia1s belonging 

- 3 -
REF ID:A38876 

to e , an admissible divisor of s, is ¢(e)/m • Hence it e = s/3 

the number is e:i. ther 1/3 or 1/2 of the pl'lllli ti ve polyno:rro..als while 

J.f e ~ a/7 the number is ~ 1/6 of the total. Further 3 is a 

factor of 11 of the 21 composite numbers a considered wh:i.le 7 

(whose presumed asymptotic frequency is also 1/2) is a factor or only 9 

of them. Five is never a factor. 

Hence if h(z) is :imprl.m.itive J."li is most likely to have a period 

tJ/3 • These remarks suf'fJ.ce to suggest that the observed results are 

- consistent with a 'purely random' or 'Kronecker' behavior of h(z). 

3. The computati.ono To test prilTll..tiv.i ty lt suffices to investigate 

•/<lj_ - z where now the qi are the various prlme factors of s • If one 

of these is 1 mod h(z) then h(z} is imprl.lllitlve. Further the 

period will divide all the s/~ which yield J. and will not d1:v1de 

those wh:i.ch do not give l • Thl.s enables a brief calculation of' the 

period. The calculation thus requires a) The polynomials h(z) for 

the req,uired p ; b) the pl""1...mes qi ; c) the numbers s/~ ; 

S/<lj_ d) Z" mod h(z) • We now discuss the procedures used f'or these 

steps. 

a) Let rr(x) = ;x:r-l + xr--2 + • • • + x + 1 , for r an odd 

positive mteger and hic(z) = x-k rr(x) for z = x + x-l and 

k = ( r - 1)/2 • Th.us f'r and 11ic are generalizations o:r r and n 

-4-
REF ID:A38876 

to all odd and all natural nunibers respectively; hm(z) == h(z) o 

The important formula isg 

(.3) 

This recursion was .f'J..rst observed m a somewhat di.f.ferent context by 

Blankinship. Its proof' is trivia11 

( ) 1\:Z -kc 2k 2k-1 > =x x +x + ... •+1 b-.f defini ti.on 

•• + x-l<: 

• bic(z) o 

This fornmla gives a method of computing h(z) which is vastly 

simpler than that given by .Aloert in SCAMP Working Paper 27 of 

15 Febro.ary 1956. Speci.fJ.caJ.ly all that is neeaed is to shi.rt 

'hic-l (z) 1ef't by one and add hk_2(z) • Only- t..i.e output time limlts 

the speed. The hk(z) , k .C::. 1.hh were computed in less than two 

-5-
REF ID:A38876 

lDJ..nutes on SWAC and the specific va1ues required selected rrom the 

resulting deck. 

b) The factorization of numbers rf1' - 1 is found in several 

tables in Kraitcbik1 Introduction! la ~e'orie ~ !ombreJ!I, Paris, 1952. 

Since our prJ.llles p are congruent to t 3 mod 8 (as 2 cannot be a 

quadratic residue of p) , Y is either odd or sing~ eveno Bence 

the tables on pp. 12 and 38 su.f'r:tcedo The fclctorizat:Lons a.re colleoted 

:in a tabl.e appended to this papero The prime factors were first placed 

on punched cards and converted to 4-precision binar,r by a routme 

written for this purpose. 

c) A division routine in 4-prec:i.si.on exact terms was m-itteno 

This took in a nwnber s , divided it by a sequence or exact divisors 

and punched out the quotientso Then it accepted the next s " If a 

non-divisor was entered the ma.chine halted m break-point J this featu.:i:e 

guarded against typographical. errors lil Krai tchik or m:i..s-punch:l.ng i!I!. 

routine b). 

d) This is the principal routme and was d:Lvided into two parts o 

In the first, the input was h(z) • The routine .found, by successive 

squaring, z~ , k = o, 1, • oe J m J reducing the powers mod h(z) 0 

As a check • The powers were stored, as produGed, on succes· 

sive drum channelso The second portion 8.C.'eepted sq.ccessively the 

numbers s/~ and computed z to these powers by mul tiplymg 

-6-
REF ID:A38876 

cons~cutiveq the previously computed powers which appear in the binaey 

expansion of s/<l:t. • As a check on this routine a itself was en'l..ered 

and z

6 

= l computed after the lllBJClJl!al proper d:i:rlsors had been com~ 

pleted. 

'!he routines listed m a), b), and c) were pr:unari'.cy' lllpllt""()utput 

routines in the sense th.at the only time limitations were tne cyc1lie 

rates of these devices. The routines in d) were or rather short 

duration. Tl':le longest were for p = 181 at 6 ~ nn.n. with 11 divisors 

and check and for p == 2ll with 10 divisors and check, a tota.1 or 

6 min. 'l"he total ran takes just over an hour for all primes leas than. 

288. 

However the routme :\,s rather hard on the machine. This seems -vo 

be due to its J,arge number of doublmg commands and repeated extracts 

which cause spill and the periodic drum re£erenees following violent 

spells of computing which produce surging. It has been necessary to 

ohoose dqs of' specia11y good machine behavior to get the routine through. 

Three such runs have been made J on these runs the single case of inconsistency- or failure to cheek occurred on s/3 for p = 269 whi~h fai1ed 

to give 1 on the second run. Th:! s particular exponent has been run 

16 times. 

As a result of these :runs we can states h(z) is 1.11Ipr:unitive :fo:r 

37, 101, 197, 269. It is highly probable that the period ot h(z) for 

- 7 -

• 
REF ID:A38876 

these primes is s/3 • It is highly probable that h(z) is prllDl.tive 

for all other primes p < 288 for which 2 is a primitive rooto The 

difference in degrees of assertion is due to the question putg Is 

this polynomial 1 ? If the probability that the machine has run without 

error is p (m) , the probability that we should get tne anew-er 1 by 

mistake is (1 - f ~2-m while the probabib:ty that we should get a 

value not 1 when the correct answer is l is (1 - p)(l - 211) • The 

second is much greater than the first o For the three runs, the numbers 

(1 - f>)3 2-3m are so small they can be neglected entirely. The numbers (1 - p)3 (1 - 21 )

3 , wh:i.J..e small should not be totally forgott~n. 

It nmst be clearly understood that in all runs mentioned the checks 

never failed; hence p is reasonably large o 

ill routines are on file at NAR-UCLA. 
REF ID:A38876 

Table 1 

p-1 

-;:-

Factors of s • 2 2 .. 1 for primes p having 

2 as a primitive root 

p 

3 t 1 

5 t 3 

11 t 31 

13 t 32 • 7 

19:7•73 

29 : 3 • 43 • 127 

37 : 33 • 7 • 19 • 73 

53 I 3 • 2 731 • 8 191 

59 I 233 • 1 103 • 2 089 

61 I 32 • 7 • 11 • 31 • 151 • 331 

67 I 7 • 23 • 89 • 599 479 

83 t 13 367 • 164 511 353 

Factorization of s 

101 : 3 • 11 • 31 • 2.51 ° 601 ° 1 801 ° 4 051 

107 t 6 361 • 69 431 • 20 394 401 

131 I 31 • 8 191 • 145 295 11.i.3 558 1ll 

139 I 7 • 47 • 178 481 • 10 052 678 938 039 

149 : 3 • 223 • 1 777 • 25 781 033 • 616 318 177 

163 I 7 • 73 • 2 593 • 71 119 • 262 657 • 97 685 839 

173 t 3 • 431 • 9 719 • 2 099 863 ° 2 932 031 007 403 

179 : 618 970 019 642 690 13 7 449 562 lll 

181 : 33 • 7 • 11 • 19 • 31 • 73 • 151 • 331 • 631 • 23 311 • 18 837 001 

197 I 3 • 43 • 127 • 4 363 953 127 297 • 4 432 676 798 593 

211 : 7 • 31 • 71 • 127 • 151 • 337 ° 29 191 • 106 681 • 122 921 ° 152 041 

227 : 3 391 • 23 279 • 65 993 • 1 868 569 • 1 066 818 132 868 207 

269 I 3 • 7 327 657 ° 193 707 721 ° 761 8J8 257 287 ° 6 71J 103 182 899 

- 9 -
REF ID:A38876 

Table 2 

Polynomials h(z) for p:d.mea of which 2 is a prllllJ..tiVe root 

(Notation m octal as m Marsh's Tables of irreducible polynomaJ..s) 

3 3 

5 7 

11 67 

l3 163 

19 1563 

29 71403 

37 16 33407 

53 7156 00067 

*59 67016 00007 

61 1 63006 00003 

67 15 63006 00003 

83 6714 00346 01563 

101 71 56034 00000 33407 

107 670 16334 00000 03467 

131 67 14030 00014 00000 00003 

139 1560 34670 00334 00000 00067 

149 71560 Oo670 16334 00000 03467 

163 156 30060 00003 46014 00006 71403 

173 7140 33460 00000 06714 00346 01563 

179 67140 03460 00000 00714 03346 00163 

181 1 63340 01560 00000 00334 07156 00067 

197 715 60340 00160 00000 00000 67016 00007 

211 l 56300 07140 33460 00000 00000 00346 01563 

227 671 40300 00016 30o60 00000 00000 00000 7lh03 

269 71403 34600 16300 00000 03460 00000 00000 00000 OOJ.63 

*Incorrect in SC.AMP paper 26, 15 Febo 1956, z

17 omitted thereo 

- 10 -
REF ID:A38876 

Table 3 

Frequencies or various classes or polynomials 

p m :rrreducibl.e Primitive 

po1'Vn0mials po1vnomials P1 Pa P3 

5 2 1 1 l 1 

ll 5 6 6 .75 1 

13 6 9 6 056 .67 .67 

19 9 56 48 .44 .86 

29 lh 1 161 756 .283 .65 .93 

37 18 14 532 7 776 .222 .54 .38 

53 26 2 SBO 195 1 719 900 f)l$4 .67 0999 

59 29 18 .$'12 790 16 407 808 f)l38 0994 

61 30 3$ 790 267 17 820 000 .133 So .33 

67 33 260 300 986 2ll 016 608 .lZl -81 

83 h1 .$3 647 lll sso 53 630 700 752 .. 098 09996 

The third column lists the number or irreducible polynomials of degree m .. 

The fourth column lists the number or prim.J. tive polynomia1s of degree m .. 

The fJ.fth column gives the probability that a random polynomial. ot 

degree m lacking a linear factor is irreducib1e .. 

The sixth column gives the probability tbat a random irreducible polynomial or degree m is primitive. 

The •eventh colmnn gives (where applicable) the probabil.it)" that an 

imprimitive irreducible polynomia1 has period 1/3 the maximum .. 

... 11 -
___ UNCLASSIFIED , __ .. 

REF ID:A38876 /.( f .J'O 

• ... -;,,...v-u.;,.Mv 

'WORKING PAPER NO. 15 

THE RAND OORPORATION1S RANDOM DIGIT GENERA'IDR 

H. P. Edmundson 

18 August 19,8 

30 pages 

The theoretical and design considerations of a machine to select 

decimal digits at random and punch them into I.B.M. bookkeeping cards 

are discussed :fn this report. The heart or the mach:tne is an electronic 

binary counter which counts pulses rrom a ~dom pulee source. Periodically, the comter is stopped f'or observation. A.bout 1001 000 counts 

are expected between S\lccessive observations, ~o that the last digi't of 

the total. can be considered random, • 

.Analytical studies indicate that the machine is hl.ghly random in 

its selection except for trivial correlation between suocesstul 

selections. Experimental tests of' large numbers of' the digits :first 

tabllrlated by the machine indicated no irregular! ties except a slight 

excess of odd over even dig! ts. Subsequent evolution in the pulae 

forming and counting circuits appears to have entirely' eliminated the 

possib:lli ty of this kind of bias. 

s-110 015 
REF ID:A38876 

UNCLASSIFIED 

WORKING PAPER NO. 15 

mE RAND CORPORATION'S RANDOM DIGIT GENERATOR I 

H. P. Edmundson 

18 August 1958 

30 pages 

Introduction. Lillu tad tables of random numbers have been published, 

but. :nmch larger tables -- in fact an inexhaustible Sllpply of random 

numbers - are needed to avoid using the same tables over and over again. 

Repetitious use of a table of random n"lllllbers is particularly undesirable 

VJ.thin a single problem. 

'.lhe generation of random digit tables by human or machine methods 

is not as simple as it appears. The remarks of Kendall and Snn.tb.112 

conceming this dif'f'icu1t,r are pertinent: 

11 It is becoming increasingly evident that sampling left 

to the cli.scretion or a human indi vi.dual is not random, 

although he may be completely unconscious of the existence 

of bias, or :Indeed actively endeavoring to avoid it. 

House-to-house sampling, the smnplin~ ot crop yields, ewn 

ticket drawing have been .found to give results widely 

divergent trom expectation ••••••• 

"It has lo~ been held that mechanical methods of producing 

random series of' integers do not JP,ve satisfactory results. 

pica-throwing, f'or example1 to give a random series of' the 

integers l to 6, notoriousJ.y results in bias. Nor are 

1K. G. Kendall and B. Babington Smith, 9Randomness and Random 

Sampling Numbers.," Journal. of the Royal. Statistical Society", pp. 151 

cilld 156, Vol. CI, 1938. 

2Kendall and Smith, Loe. Cit., pp 154-156. 

s-110 OlS 
REF ID:A38876 

UNCLASSIFIED 

roulette tables much better. Ka:rl Pearson hap shown by 

analysis of the gaming results at Monte Carlo that the 

odds against the absence or bias are exceedingly large. 

The source or this bias is not altogether clear, but if 

we exclude the possibilities of deliberate falSl..t'ication,, it would appear to ar.:t.se from small inperfections 

in the roulette wheel which direct the ball. into some 

compartments in preference to others •••••• ·" 

Mr. Cecil Hastings of the RAND Corporation has proposed a scheme 

for accomplishing the selection of digits with a high degree or randomness, and auto:matical.ly recording them at a reasonably hi~h rate ot 

speed. A machine based on a variation of his idea has been designed and 

constructed in the Development Section anq. put into successfUl operation. 

The tol1owing discussion describes the operation or the machine,, 

attempts to discuss its randomness ana1ytic'1-ly,, and mentions a few of 

the design :features intended to insure conf ormiw to the theoret:J.cal 

analysis. 

'lheoi-etical cons:t,derations. The two design cri teri.a or a machine 

intended to produce a table or random digits are 1 

1) The device should be absolutely impartial.. 

2) There should be no correlation between successive selectionsJ 

the machine should have no memory. 

Almost any common devi'9e one might name falls dow;n at one of these 

two criteria. A mechanical roulette wheel, for example,, satisfies 

neither requirement. It is difficult to build a roulette W.ee1 nth such 

precision that one number would not be favored over another by even one 
REF ID:A38876 

UN CLASS IF JED 

percent, let alone, say, one thousandth or a percent, which would be a 

1110re nearly acceptable figure. Furthermore, if', srq, one mllion successive 61s were thrown on a roulette wheel, a groove would be worn to the 

6 compartment. Therefore, the 6 voul.d be favored over the other 

numbers. 

Consider, however, the f'ollow:t.ng system, Figure 1, Which is a 

modL:t'ied electronic roulette Wheel. 

Random Frequency 

Pulse Source 

Constant Frequency 

Gati?Jg Pulse 

Source 

I.B.M. 

Key Punch 

._..~ Input Pt. 

GATE Output 

Ter.rninal 

-311--1 Control Pt. 

B:Lnazy-Decimal 

1---E--1 Transformation 

Relays 

Pulse Shaping 

Circuits 

5~lace 

Figure 1 - Random ])J.g!t Selectin_g s,rstem 

-3-

1--~-.., 
REF ID:A38876 

UNCLASSIFIED 

It is intenqed that sharp pulses from the random .frequency pulse 

source should arrive at the gate at an expected frequency of! about one 

hundred thousand per second. This gate circuit is controlled by broad 

constant frequency pulses from the constant frequency gating pulse 

source, so that the gate allows the random pulses to pass in groups of 

about one second time duration. Each random pulse advances the position 

of the counter one digit, so that each group of random ;pulses advances 

the count about one hundred thousand dl.gi ts. Ai'ter each group o! 

pu1ses, the digit at which the counter rest~ is considered to be random. 

This system is closely analogous to a 32 compartment roulett.e wheel, 

aromid which the ball. spins about three thousand times before stopping. 

'.lhe choice or ,32 numbers results, or course, from the fact that 

~ = 32 is the number of steps in one cycle of a five place b:in~17 

counter. For a reason to be discu,ssed later, the follonng transformation from bi.nary numbers to decimal dig:l. ts is now used 1( this transformation wa«;1 not used or.lg:inally) • 

-4-
REF ID:A38876 

UNCLASSIFIED 

TABLE I 

TRANSFORMATION FROM BINARY TO DECIMAL DIGITS 

Position in Cycle Binary Number Decimal Digit 

0 00000 p 

1 00001 1 

·2 00010 2 

3 OOOll 3 

4 00100 4 

5 00101 5 

6 00110 6 

7 OOlll 7 

8 01000 8 

9 01001 9 

10 01010 discard 

11 OlOll discard 

12 01100 discard 

13 01101 discard 

14 OlllO discard 

15 Ollll dl.scard 

16 10000 discard 

17 10001 discard 

18 10010 discard 

19 10011 discard 

20 10100 discard 

21 10101 discard 

22 10110 9 

23 lOlll 8 

24 llOOO 7 25 11001 6 

26 11.010 , 

27 11011 4 

28 lllOO 3 

29 11101 2 

30 11110 l 

31 lllll 0 

The impartialit:r of this type :rnach:i.ne results f'rom the assumption 

that the pulse shaping circuit standaraizes the shape of a11 pulses 

-5-
REF ID:A38876 

UNOLASSMEJ2 

it passes on to the counter, and that the level and separation of the 

standardized pulses driving the counter is sufficient to unerringly 

advance the counter one count per pulse. Even though the counter flipflops themselves J1UV prefer certain positions to others, the totals 

observed on the counter are determined erxhirely by the number or pulses 

which come f'n>m the pulse f'ol!lllllg circuits during the measured time 

intervals. It was, however, the failure of the initial c~its to 

faithfully perfonn these £unctions that caused the initia1 odd-even bias 

in the tables created. Impartiality also depends upon complete independence of' the gating pulse generator, and the random pulse generator £.rom 

the position or the counter. This is accomplished easily by caretull.y' 

isolatmg the fields and power supplies of these different ccmponents. 

There is no eVJ.dence at present to indicate that the mach:fne does 

not select billary numbers w.i.th complete :impartiality. However, it wuld 

be necessar;r to sample several. million numbers to detect an od.daeven bi's 

of as ll!llch as one tenth percent. As insurance against the possibility 

that the machine m~ have an midetected bias in one of its binar.y 

counters, the peculiar transformation to decima1 digits given m Table I 

is used. Note that the tw binary numbers which transform to each decimal 

dl.gi t are complementary. Thus, if the flip-flop controlling any one binaey 

place is biased by a certain amount, the probability of any particular 

decimal digit be:ing selected is unchanged. b excess (or shortage) :ln 

-6-
REF ID:A38876 

UNCLASSIFIED 

the probability or the digit being selected in the first ten po~tion~ I 

is exactly compensated by the shortage (or excess) in the probability of 

that digi"t being selected in the last ten positions. 

The effect of th:i.s complimentary combination scheme can be fomulated 

ana.J.,-tical.ly. Suppose that O i~ preferred over l in the last. binary 

place by an amount 2c< , in the next place by 2 ~ 1 in the next place by 

28 1 :ln the next place b.r 2 £ , and in the fl.rat place by 2 p • The 

probability ot a 0 deQimal digit equals the probability or a 00000 

binary number plus the probability' o£ a lllll b:lnary number. 

p(O) .,. (1/2 + « )(1/2 + fl)(l/2 + S)(l/2 + c )(1/2 + p) 

+ (1/2 - oc.)(1/2 - p)(l/2 - 8 )(1/2 - e )(1/2 - p) (1) 

Neglecting terms higher than the second degree leaves 

p(o) ... 1/16 + 1/8f:t(3+a& +cu. + «p + ~i +(SS + 13e.. + (JP+ ~e +~E. +Sr+ e.r> 

(2) 

p(l) ... 1/16 + l/B(-o.p-01& -ex~ -exp+ ~s + ~e. + (3p +or + e.r) (.3) 

p(2) .. 1/16+ 1/8(-lJ,B+ois +qe +~f -ru -f3E-(Jp+&e. +of -ip) (4) 

etc. 

Notice'that no first degree errors remain as a result or this 

parb.cular type or transtormation. 

- 7 -
REF ID:A38876 

UNCLASSIFIED 

'?he second criterion, the absence or correlation between Stlccessive 

selections, is certainly satisfied by this system. Actually, it would 

be nearly impossible to intentionally control the frequency or the pulse 

source and the period or the gate switching pulse closely enough that a 

•next" selection could be predicted, since the expected number of' counts 

per gate interval is 100,000. '!'he following analysis indicates how 

small this correlation actually is assuming an idea1 counter, random 

pulse source, and gating system. 

'l'1e probability ot exactfy X randolll pulses occurring 1n any 

constant time interval group is 

p{K) • -fie~ t 

"Ntlere N is the expected number or pulses per group. 

(5) 

If, therefore,, the count sta:rts from a digit d0 1 the propability 

of' its advancing just k digits to digit ~ is 

() ~ -N pk alCT'e • 

The dig:J,t <\ Would also be selected ir the counte,io advanced 

32 + k counts, and the probability or this happening is 

J(c+32 -fl 

p(k + 32) ... (it.,. 32)1 e • 

... 8 -

(6) 

(7) 
REF ID:A38876 

UNCLASSIFIED 

----

Similarly, the di.c digit can be selected by the count advancing k 

plus any multiple of 32 comts. Thus, the entire probability of the 

digit \: being selected after d

0 

is 

( } Mk- -N if+ 32 e-N + i(c+64 -N ( ) f ~ • kT e + (k + j~)f (k + 6liH e + • .. • 8 

S:bnplif:Lcation of this to a finite series can be achieved by the 

use of the identity 

Thus, 

rr- ~+32 ~+64 1 31 

kl + (k + 32)1 + (k + 64)1 .. • .. = '.12 t 

m=o 

31 

p(c\) ... ~ e-N L 

:m.ao 

-ikftr 

e 

This equation reduces easily to the fom 

i:'ll'm 

ik'T(m Ne ib" 

e 'IO e 

i 'fl'm 

Ne T 

e 

• 

• (9) 

(10) 

(11) 

Since N is about 100,000 , the term in the summation corresponding 

to m = 0 is by far the most important. Next are the two terms corresponding to m • 1 and m • .31 , and the remaining te~s are negligible 

in comparison with these. The three retained terms can be written 

- 9 -
REF ID:A38876 

UN CLASS MED 

• (12) 

ff 31 'h' lf'r' 3111" But cos lb = cos -n;- , sin n; • - sin -n;- ; and for k an integer, 

~ n« k IO radians is coincideni t with -k -n;- radians. Thus 

1 [ -N(l-co~){ i(Nsin~ -k/o> -i(Ns:tni16-k~} J 

p(c\) = ~ 1 + e e + e 

1 [ -N(l - cos'.) 1f ] • J2 1 + 2 e cos (N Sl.n ~ - k IO) • (13) 

Since the cosine function can be no greater in absolute magnitude than 

unity, then this probability can differ from the perfect value of 1/.32 

by" no more than 

r 

I 1 -N(l- cos') 

1/32 - P(<\c) t '= IO e • (J.4) 

For N • 1001 000 this deviation is 

11132 _ P<<ic> I " fo e-100,oooc1-.9ao1> 

1 -1930 ,,. I5 e • (15) 

- 10 -
REF ID:A38876 

UNCLASSMED 

Indeed, the correlation between successive selections is negligible. 

~ random pulse source. The circuitry used as a random pulse 

source is a high gain wide band noise amplifier followed by a detector 

biased so that only the noise peaks above a certain high level are trans-

:nn. tted through the detector into the output circuit. Figure 2 is a 

schematic of the circuits used. The source of random noise is simply 

shot effect in the first vacuum tube. The r-m-s value of this noise is 

controlled by the bias applied at the input grid. ~e overall bandwidth 

of the smplifier ;i.s about 6 megacycles. 

The justification £or using a highly biased random noi~e detector 

as a ra?l(iom pulse source may not meet the approval. of the critical. 

reader. However, all that is needed from a practical standpoint is a 

highly irregular and unpredictable source of pulses to drive the counter, 

and the biased random noise detector certainly satisfies tbl.s requirement. 

As a matter of fact, it can be argued that the pu;Lses generated by 

such a device are nearly ~ly random. The requirement of a truly 

random source would be that the probability of a pulse occurring between 

t and t + dt should be some p dt , where p is the expected 

number or pulses per second and is a constant entirely independent of 

the nwnber and distribution of pulses generated up to time t • 

Figure 3 is a typical random noise voltage signal, with one 

detected pulse shown to aid m discussing the problem. 

-11 - I 
I 

I 

' 

6SJ1 

I 

I 

ooe:f 

_J_ 

REF ID:A38876 

) 

~ sooa.μI ~ ooe ; --=-r_·.____~ ~AC"l 

-

--~~--------

o;i; 

~i 

o~ 

" "~ 

'!!f -_ __, 

F"IGURF 2. -RANDOM NOISE GEN(~ATOR ANO BlASED 0[ fLCTOR 
UNCLASSIFIED 

Volts 

bias 

level 

REF ID:A38876 

Figure .3. ~ Typical Random Noise Voltage Signal 

Consider the follow:i..ng argument from thE? st.and.point of an observer 

who stands at the output of the biased detector and observes only the 

detected pulses. Say,, for example,, that starting at the le£t end of the 

signal ot Figure ~,, a pulse has not been detected £or a long time. Then 

proceeding with time to the right, the probability of a dete~tabl(:l pul~e 

occurr.mg between aD:3" t Bl'.ld t + dt is p dt , where p is a constant 

detennined by the r-m•B level of the noise voltage and the bias applied 

to the detector. So far as the waiting observer is concerned, a 

detectable pulse is just as likely to occur at one time as another. 

-13 -
REF ID:A38876 

UNCLASSIFIED 

Suppose that at time t a pulse is .f:inal'.cy' observed. '!hen, however, 0 

the observer is able to predict a trend .f'or a short interval ahead. Knowing the intr:tnsic decB31" behavior of the amplifier in question, he lmows 

that this decB31" voltage superl.lllposed on th~ new random signal voltage 

increases (or decreases as the case ~ be) the probability of a detectable peak being observed. After At , however, the decq trend will 

have expended itself, and the probability of a pulse will remain constant 

(so far as the observer lmows) until another pulse is observed. 

The length of At can be asi:JU,med to be less than one microsecond 

.f'or the amplifier in question, since one-twelfth m:i..crosecond is the 

conventional rule-of-thumb decay time estimate for a low-pass amplifier 

or six megacycles bandw.i.dth. The fact that the amplifier is actuall:y 

banJ(i-pass instead of low-pass can be neglected, sdnoe the ratio of noise 

power in the missing low end of the r:yequency range to the power :in the 

band pass region is quite small. It will become apparent later that this 

' divergence from pure random occurrence in an interval of one microsecond 

follonng each observed pulse is or no extra concern. The pulse forming 

circuits reject any pulse which falls within one lllcrosecond or a previously observed pulse anyhow. 

1'!!! gate circuit~ the gating pulse fenerator. The ttmction of 

' the gate circuit and its controlling gating pulse generato:r is to 

measure out mtervals of one second during which pulses from the random 

pulse generator are amplified and passed on to the pulse shaping circuits. 

-14 -
REF ID : A38B-'7-6-

• 

UNCLASSIFIED 

Between each of these intervals should be a period of about one-tenth 

second Q.uring which the pulses from the random pulse generator are 

blocked, and the digit at which the counter stops is read and recorded 

:in an I.B.M. card. This tiJlll.Dg sequence is obtained easily ~ means of 

an unsymmetrical multivibrator. 

Figure 4 is a schemati.c or this timing mltivibrator and the gate 

circuit. The gate circuit is ' two stage pulse amplifier WJ.th the plate 

of the second amplifier tube tied in common with the plate of the gating 

pulse ii:;olation tube. Notice that when the mu.ltivibrator lies with its 

right-hand tube conducting that the isolation tube is cut off. Thus, 

"lhe pulse amplifier works as a simple amplifier with no interference from 

the :rnultivibrator isolation tube. When the right-hand tube is cut off, 

however, this isolation tube grid goes positive w.i..th respect to its -90 

volt cathode, pulling its plate down to a negative value. Consequently, 

the voltage is removed from the plate of the second pulse amplifier 

tube, and no pu1ses f'rom the random pulse source can pass to trip the 

pulse fonning circuits which follow. 

A second nmltJ.vibrator isolation tube is shown :J,.n Figure 4. When 

the grid o:r this tube goes positive, its plate current actuates the 

co'llllter reading relays and, subsequentfy, the I.B.M. key punch. 

!!! pulse shaping circuits. The pulse shaping circuits have a 

difficult job to perform. The input pul.ses are of various sizes and 

shapes and occur at random in time. From these highly irregular :input 

-15 -
REF ID:A38876 

UNCLASSIFIED 

signals, the pulse shap:tng' circuitp must form output pulses of standard 

size '1\d shape, no two of which can be within one microsecond of each 

otheri' Any input pulse which comes within one mQrosecond of a previous 

pulse must be rejected • 

.Although this would ordinarily be an easy fUnc"\;ion, it. is made very 

di.f.f'l.cul t by the ngid requiremnts p1aced upon the dependability of the 

circuits. The pulse shaping circuits must be perfect, lest counter 

partiality bias the digit selecting system. If any pulse leaks through 

the puJ,se shaping circuits lilich is of such a ai.ze and shape, or is ~o 

close (less than on, microsecond for the counter used) to atliother pulse, 

that the counter might or might not (according to its own preference) 

advance one count, then the unavoidable partiali -cy- of the counter itself 

is a1lowed to contribute partia1ity to the system as a whole. The 

circuits of Figure 5 were arrived at experimentally, and appear to be 

absolutely dependable. 

-16 -
REF ID:A38876 

................... ~ llt ......................................................... l ........... ...i . -

• 

J 

f 

t 

I 

' ' 

l 

! 

I 

) 

• 

0 

0 

0 

.. 

., 

• 

.. 

y 

bAC. '1 PULSt ~10s AM~\.I FltK 

008 

roμ" '--1--------'I L_ -- tO PUlSt .. HAPINfl :r: r CU~f. Ul'T~ 

0 

0 

0 

<r 

rl rr 

Tl!ST 0 _ 

(::.,~~ENCE ~ ooe T ~CH __j 

bA.~1 GATED 

- PUlSt: AMVl \Flt-R 

150,000 

100 \,10(.1 .__ __ - ...J:NN,, 

7~ -90 

6Al 1 MUL HVIBRATOR 

\SOLA HON 

0 

0 

0 

0 

0 

"' 

- TO C'OUN IE R READ l\IQ 

l

- t CARO PUNCHtNQ 

W.ELAV4) 

tl---r __ _J -•~O 6SN1 MULTl'"8RATOR _ C ~ &SN1 MUl TlVtBkA10H 

IC)OU\l\C.IN 

FIGURE 4 CONSlAN T FREQUE NCV GAT,NG PULSE SOURl E 

AND GATE AMPL1r1ER 
REF ID:A38876 

UNCLASSIFIED 

First :1n the circuit a.re two cascaded one-shot nmltivibrator 

circuits (6SN7's), with a pulse width of about one micrc;>second. ihese 

circuits do the major portion of the wrk. Pulses which are too weak to 

trip the circuits do net get through to the output at all, and nearly 

every pulse strong enough to trip the circuit produces a standard one 

:nn.crosecond pulse. Some complications, however, occur. For example, when 

two strong pulses occur just about one microsecond apart, the second 

pulse may catch the one-shot nru.ltivi.brator circuit just as it is resetting 

and produce something different from the standard pulse shape. 

The .f:Lnal insurance against iITegularities is a relatively fast flipflop circuit of 6AK51 s dr:t.ven at the cathode of one of the 6.AK51 s by 

a 6L6 cathode follower. ibis circuit trips to the right if the driven 

cathode is made more positive than +10 volts, and resets to the left :Lt 

the driven cathode is ma.de more negative than -10 volts. Thus, the 

circuit can trip only once for each ftlll pulse from the one-shot multivibrators, and any small input irregular.l.ties will fail to trip the 6AK5 

flip-flop unless they go from -10 to +10 volts. There is little 

chance of trouble with input pulses too closely spaced in this circuit, 

because the flip-flop is ver:r fast conpared to the circuits which drive 

it. The flip-flop has a rise time at its plates of about one tenth microsecond, am stab:Llizes in an exchanged position at the end of about tw 

tenths of a microsecond. 

..I 18 -
REF ID:A38876 

UNCLASSIFIED 

Thus, the output of thl.s circuit is a square wave of about one 

microsecond duration and very steep sides. It this output is di.f'.f'erentiated (not shown in Figure S ee "Fl.go.re 6) the result will be 

;:sharp poSl..tive and negative pulses, and, obviously,, no two positive pulses 

can be closer tqgether than one microl!Jepond. Al.Sb, t;hese pulses will be 

of· stanclar[l .. site atid~ shape, sin6e, ~ reln-ti~iy aluggi*h dri'tiing circuits 

ahead of' the 6AK> .flip-flop cannot e:f':f'ect its rise time appreciab:J..y. 

~counter circuit. The function of the counter oircuit is to 

accurately count the pulses as they come .from the pulse shapmg circuits. 

The resolving time of the ocmnter must be short compared to the one 

microsecond :rrnnimum spacing between successive input pulses, and the 

circuits must be absolutely dependable else counter part:Lali ty might 

contribl.te partiality to the system. 

'!'he counting is done in the binary number system because it is the 

natural system for electronic counters. All the binar,v places except 

the last rive are disregarded, giving a count cycle of 25 = 32 steps, 

the 33rd step being identical with the 1st, the 34th step being 

identical with the 2nd, etc., etc. 

In Figure 6,, the fl.rst two tubes are a cathode follower to isolate 

the fiip-.:f'lop of Figure 5,, and a drJ..ver tube for the following flip-flop. 

Recall that the output of the .flip-flop in Figure 5 is a square wave 

pulse with ver.y steep sides. 

-19 -
4 

1 

I 

IN34 

REF ID:A38876 

0 

0 

~ 

« 

8t 

..I. 008 

0 

-10 

6SN'l ONE·SHOl MUl llV,SRAl'Of.t 

-105 

bl6 CAlHODE FOLlOWf.ff 

0 

0 

IC 

IC 

-10!!» 

0 

0 

0 

... 

0 

0 

"' ... 

l!I+ 

r------ - 008 I 

'l.'!>i1,, a!lcμ. 

·20 -::- • 

6SN7 ONE. S"Ol MUl 1\V,~f•ATOR 

----t\:H 

~ I FIGURE. 5-PUlSE SH~PING CIRCUITS I 

IC.>~ 

..................................................................... l ~ ...... b~A·K-5 ... F·l·'·P·f-"L.o"v ... ___ ~u~~-~-....... M .... ...,~ 
REF ID:A38876 

UNCLASSIFIED 

In the output or the cathode follower circuit this voltage is differentiated by the 50 pp. condenser into the 10,000 ohm resistor, so that 

the input to tl;te 6AK6 driver tube is a sharp positive pulse corresponding to the front edge or the input pulse, and a sharp negative pulse 

I corresponding to the trailing edge of the input pulse. Of course, the 

positive pulse only is effective, since the tube is normally biased 

beyona cutoff. When this sharp positive pulse is applied to the driver 

tube grid, its plate conducts momentarily. 

The basis of the electronic counter is a d-c flip-flop, a circuit 

having two stable positions. Note in Figure 6 that if no external 

dr:Lving pulses are supplied, the 6AK5 fhp-.flop would sit with either 

its right hand tube conducting and the le£t hand tube cut off, or with 

its left hand tube conducting and the right hand tube cut o:rr. Note also 

that if the grid of the 6.AK6 drivmg tube (which is normally cut orr) 

is pulsed with a sharp positive peak causing its plate to conduct 

momentarily that both plates of the 6AK5 f'lip-flop will be momentarily 

brought to almost zero voltage, and the flip-flop circuit will then 

return to the state opposite the one it was resting in when the drJ..ving 

pulse occurred. Tl:u.s exchange or position is caused by th13 two "memor.v" 

condensers shown ( 20 pp.). The condenser to the formerly non-conducting 

plate has a greater voltage across it than the condenser to the conducting plate. Thus, if both plates are momentari~ reduced to nearly zero 

volts, the cond13nser having the greater voltage across it causes the 

- 21 -
REF ID:A38876 

UNCLASSIFIED 

grid or the opposite tube to be the more negative. When released, then, 

the opposite tube becomes non-conducting, while the formerly nonconducting tube conducts. Eacb positive pulse f'rom the pulse shapmg 

circuits reverses the position of' the first .f'lip-flop. 

The output or thl.s f'lJ.p-f'lop, then, l.S a1terna'14e positive and 

negative steps. This ou'l;put is isolated by a cathode follower and 

dl.tferent:La.ted. by circuits similar to the differentiating circuit used 

ahead Of the first .f'll.p-flop. '!he result_, Of' course, l.S again verf' 

sharp positive and negative pulses, and the positive pulses are used to 

drive the second .flip-flop. This chain - £1.ip-f'lop, cathode follower 

stage and driving tube -- is repeated a total of' f'ive times. '!'he f'irst 

flip-flop reverses conduction tubes f'or each input pulse. The second 

.:f1.ip-flop in the chain reverses for each positive pulse from the differentiating circuit f'ollow.i.ng the first :,f'.l.ip-flop - and this occurs on17 

on every second input pulse. Similarl;r, the third fiip-f'lop reverses 

on everr fourth input pulse, etc., etc., and the last flip-flop reverses 

on every SJ..Xteenth pulse. Thus, the counter cycle consists of' the 

following 32 stepst 

- 22 -
REF ID:A38876 

UNCLASSIFIEl> 

TABLE II - COUNTER CYGLE 

I 

Flip-1r.Lop Position \U for right and J. for l.e!"li) 

Step Noo $ Noo h Noo 3 Noo 2 Noo 1 

0 0 0 0 0 0 

l 0 0 I 0 0 J. 

2 0 0 0 1. 0 

3 0 0 u J. 1. 

4 0 0 l 0 0 

5 0 0 J. 0 l 

b u 0 J. l 0 

7 0 0 J. l l 

ij 0 J. 0 0 0 

'I 0 J. u u l. 

J.U 0 J. 0 J. 0 

ll 0 1. 0 l l 

J.2 0 J. l 0 0 

J.j 0 l J. 0 J. 

JJ1 0 1 1. 1 0 

J.~ 0 J. J. l 1 

.U> 1 u 0 u 0 

l."{ J. 0 0 0 1 

J.O l 0 0 1 0 

.:.L9 J. 9 0 ]. J. 

20 J. 0 J. 0 0 

2J. l 0 l. 0 l I 

;!~ ]. 0 ]. ]. 0 

2.3 ]. 0 1. 1. ]. 

2h l J. 0 0 0 

2r, J. J. 0 0 1 

2C> J. J. 0 J. 0 

~-, J. ]. 0 J. l. 

2ts l 1 J. 0 0 

2'i J. J. J. 0 J. 

.::SU l. J. J. ]. 0 

.'J. J. J. l 1 1. 

- 23 -
REF ID:A38876 

UNCLASSIFIED 

~ binarr ~ deciDJa]. transformation. Table I of the section on 

theoretica1 considerations shows the manner in which the positions or 

the binary cycle are to be interpreted as decimal dJ.gi ts. It is 

desirable to 1ndicate each of the digits by a closed circuit rather than 

by a light, voltage, or current, so tha\; any type or automatic device 

such as an electric typewriter or I.B.M. duplicating punch may be used 

to record the selections. 'Figure 7 shows how thl.s may be accomplished 

by the use or multi-pole double-throw relays. 

Note that, depending upon what combination m which the relays are 

open Qr closed, ~ one -- but only one -- path is closed to the common 

input point. If these rel~s are controlled by the position of the d-c 

fiip-.tlops or the binary counter chain, then it is possible to determine 

by inspection the particular comm.nation which closes the circuit to each 

particular output point. In Figure 7 each or the 32 output points is 

labeled with this binal;7 counter combination (assuming l to mean upper 

contacts and 0 to mean lower contacts), and the decimaJ. digit this 

combination should represent is copied from Tabl.e I• 'l'hen the two ou.tput points that indicate each of the decimal digits are tied to a 

common output termina1. 

figure 7 shows how the rel~s a~ driven by thyratrons, the grids 

or which are controlled by the cathode follower voltage of each or the 

five .f'lip-f'lops. The gating pulse output tube in the lower right hand 

- 21.r. -
REF ID:A38876 

UNOLASSIFlED 

comer of Figure 4 closes the master relay - power relq in Figure 7, 

f\lrnishing plate voltage to the five transformation relays. Thus, the 

transformation relays do not attempt to follow the progress or the 

electronic counter, blt merely are controlled by the counter during the 

one-tenth second interval during which the gate is shut and no pulses 

are driVlllg the counter. 

'!he relay-power rela;rs work in conjunction with the master 

transfonnation circuit relay to prevent the application of power to the 

recording circuit until all five transformation relvs have been given 

ample time to set in the selected combination, and to open the recording 

c:trcui"t bef'ore tti.e transformation relays are released. Qtherw:L~e, each 

time the gating pulse occurs, the transformation !'E:4la.ys would give 

m.oment&.17 false circuits when they were pulling iii or releasing. 

- 25 -
r 

.. 

• 

FtlOM PUUl , .. ,_PING -11~rNV't 

C.t"CUtT!t 

6A.K5' 

CA T~')DF. FOL LOWEK 

~10s 

6AKb 

DR.VER 

REF ID:A38876 

105' 

FIRS1 t>AK5 

FLIP FLOP 

Bt 

_j_ 

&A\CS 

CA1'HODE FOLLOWER 

FIGURE 6 -flRST COUNTER FLIP FLOP (tONTROLS LAST181NAR" PlACt.) 

'ft' ,U.ONQ 

., H'P F\OP 

Ulll\'ILlll 1U8t 

CIUD 

' 101 
' ' 

• 

REF ID:A38876 

COUNTER f"LIP- FLOP CATHODE r:oLLOWEf'S (~l E FIGURE b) 

.J"O 

r2.ND 

2050 _c-, 

~ 0 

f\GURE 7- Bl MARV-TO- DEC 'MAL TRANSF"ORMATION CIRCUI rs 
REF ID:A38876 

UNCLASSIFl'ED 

~ ~ monito;t'"ing cirCll.l.ts. Unfortunate1y, it is impossible to 

devise a:n.y kind of Jnonitormg circuit which will indicate whether or not 

the maehine is choosi:pg numbers without 'bias. l]!here are, however, a few 

s:lmp;l..e circuits which checlf tl1.e performance of the components of the 

system. 

Ref'emng to Figure 4, note the •Test Sequence Switch" in the grid 

circuit of the 6AC7 gated pulse amplifl.er. When this switch is closed, 

no:mial bias is applied to the grid of the 6AC7, and the circuit :functions as a pulse amplifier. If the switch is open, however, a bias of 

-105 volts is applied to the 6AC7 grid, and the tube is completely cut 

off• Thus, no pulses from the random pulse generator can dr.ive the 

counter. Hqwever, every tJ..De the gating pulse clamps this 6AC7 circuit, 

one pulse is ~rmed by the puls~ shaping cir~its <:>f Figure 5 (the leading edge of tb,e gating pulse being sbarp enough to trip the pulse 

shaping multi vibrators). llith this happening, the counter should advance 

just one count per selection. This test sequence is va1uable as a 

check on the reliability of the system fro~ the gate circui~ through 

to the output device (which is an I.B.M· key punch at the present time). 

Before and after each running peripd the mach:J,ne is set on "test 

sequence" to:r s~veraJ. mmutes, ~d the punched cards produced are 

chedQd for errors. 

A second circuit monitors the average• rate at which pulses are 

being counted. Thie circuit is a simple electronic frequency meter 

- 28 -
REF ID:A38876 

UNCLASSIFIED 

connected to the last flip-f'lop in the counter chain. A voltage is 

generated proportional to the average .frequency or the counts and is 

indicated by a meter on the f'ront panel or the instrument (see Figu.re 8). 

Also, this voltage is used as an a..iv-c source to regulate the average 

random pulse rate to the frequency desired (about 100,000 per second) 

1'" using it as a "Control Bias" on the noise source tube in Fig. 2. 

Electro-mechanicp. counters were installed in the output circuits 

to indicate total. counts. Ten counters were connected directly across 

the out.put ternn.naJ.s or the transforma:tion relays to indicate the total 

number of times each decimal dig:l. t is selected. .Also, two counters were 

installed to count the number Of times the first flip-£1op Of the 

electro?tic bina:rr counter indicated right and left ( O or 1) -- a measure 

o:f the impart;ia1it7 or the s;rstem up to the bina:cy selections. Recall. 

that the binary-to-decimal dig:i.t transf'omation 'U.Sed, Table 'I, y1.elds 

decimal. digits of improved impartiaJ..it;r. Thus, it is advisable to look 

for partiality in the bmar.r selections since partiali t{y' would be more 

evident there. 

Conclusio;ns. 

lo A machine whl.ch takes as random the last digit of the total. 

random pulses in a fixed period has been constructed and put; into 

successf'lll operation. Initially, an improbable excess of even over odd 

- 29 -
REF ID:A38876 

UNCLASSIFIED 

selections occurred. But, since revisions were made in the origmal. 

circuits, no indication or partiality has occurred. 

2. A complimentary type or transrormKtiion from btnar.r to decimal 

digits is used. If partiality should exist :m the binary numbers 

selected, this particular type or transformation would yield decimal 

digits with considerab1y less partiality • 

.3. The machine is completely au tomat.:i..c • The lllli t buJ.1 t was 

connected to an I.B.M. key pnnch,to compile a table or several million 

random digits. 

References 

A Million Random D:L~ts with 1001 000 Normal Deviates, The RAND 

Corporation, 195'5. 

.. 30 -
REF ID:A38876 

UNCLASSIFIED 

WORKING PAPER No. 20 

A CLASS OF MAPPINGS AND SOME EXAMPLES 

G. A. Hedlund 

28 August 1958 

This note concerns a class of mappings defined and 

studied by Rothaus (SCAMP Working Paper No. 25, August 30, 1957) 

and Blackwell (Ibid and SCAMP Working Paper No. 3, July 9, 1957) • 

The first part of the paper develops some of the general theory. 

Most of the theorems proved are not new, though it appears that 

the proofs are. The second part of the paper gives some examples 

which seem to have been unknown previously. 

length 

Let S denote the set of all sequences of 0 1s and l's of 

n 

n, n a positive integer. Any member of S 

n 

will be called 

an n-block. 

Let S denote the set of all unending sequences of 

0 's and l's • Any member of S is a function with domain 

the set I of all integers (positive, negative or zero) and range 

m s1 • Let 

s = .... and 

t = 

be members of S. We define a distance in S as follows• 

d(s,s) = 0 • 
REF ID:A38876 

If t + s 1 there exists a least non-negative integer k such 

or s _k f t_k 1 and we define 

1 d(s, t) :z k+l" 

It is easily verified that S , with this metric, is a Cantor 

dis continuum. 

Let f be a function with domain S and range in 

n 

Then f defines a mapping g of 

m 

sm+n-1 mto Sm,as follows: Let B E sm+n-1 and let 

B = sl s 2 • • • • sm+n-1 • 

Define 

and let C = t

1 t 2 • • • tm Then g (B) = C. 

m 

Similarly, f defines a mapping g of S into S, as follows 

Let s E S and let s • 

Define 

and let 

t = • • • t _ 1 t

0 

t

1 ••• 

We define g (s) = t. Clearly g is continuous. 

A basic problem is to determine conditions on the 

function of f which will assure that the mapping g is an 

onto mapping, 1. e., g (S) = S. 

- 2 -
REF ID:A38876 

Remark. g 1s an onto mapping 1f)and only 1f, 

g (S + 1) s S fo:r all m , or, equivalently, 1f,and only 1f, m m n- m 

B being any m-block, there exists an (m+n-1)-block C such 

that g (C) = B • 

m 

The stated condition 1s obviously necessary. 

To prove the suff1c1ency, suppose that, B being any 

m-block, there exists an (m+n-1)-block C such that g (C) = Bo 

m 

But then g (S) 1s clearly dense 1n S • Since S 1s compact 

and g is continuous, g (S) is compact, thus closed, and, being 

dense in S, g (S) = S. 

Let s = •• a s _1 s 

0 

s 1 ••• belong to S. Then s is said 

to be periodic 1f there exists a positive integer p such that 

The least such pos1t1ve integer is the period of s • 

Remark. If s E S 1s per1od1c, then g (s) 1s periodic. 

If s has period w then the period of g (s) divides QJ • 

In the following 1f A is a set, crd (A) denotes the 

-1 number of members of A • If B E S , g (B) denotes 

m m 

the collection of all members C of S + 1 such that 

m ngm (C) = B. In general, 1£ D 1s a subset of Sm , g~ 

(D) denotes the collection of all members E of S + 

m n-1 

such that g ( C ) E D • 

m 

- 3 -
REF ID:A38876 

Lemma, Let the mapping g defined by f be an onto 

mapping and let there exist a positive mteger k such that 

-1 -1 crd g (B) = k for some m-block B and crd g (A)z k 

m p 

for all p-blocks A and all positive integers p. Then 

-1 crd g + (BA) = k for all p-blocks A and all positive pm 

integers p. 

Proof. It is sufficient to prove that 

-1 ) -1 ( ) crd gm+l (BO = k = crd gm+l Bl • 

Let 

g~ (B) = [c1 • c 2 ..... ck] • 

-1 ) A member of g (BO cannot be identical with a member m+l 

of gm;~ (Bl) • Thus crd gm;~ [BO , Bl ] 2. 2k • 

But 

and thus 

and 

gm~~ [BO, Bl]= [clo,c2o, •••• CkO'Cll,Czl, •••• Ckl] 

crd gm;~ [BO, Bl] = 2k • 

-1 Since crd g m+l 

-1 (BO) 7 k, crd gm+l (Bl) z. k , 

it follows that 

The conclusion of the lemma now follows by induction. 

- 4 -

• 
REF ID:A38876 

Theorem 

crd -1 

gp {A) 

Let the mapping g be an onto mapping. Then 

~ 2n-l for all p-blocks A and all positive 

integers p. 

Proof. + Let I denote the set of positive integers and let 

k = 

-1 Min crd ~ (B ) 

mEF,B ES • m 

m m 

Since g is an onto mapping. k Z l • Let B be an m-block 

-1 such that crd g (B) = k. It follows from the preceding m 

-1 lemma that crd gp+m (BA) = k for all p-blocks A and all 

positive integers p. 

Let 

Then 

-1 (B) = gm • 

We recall that S denotes the set of all q-blocks and BS 

q q 

denotes the set of all (m+q)-blocks with initial block B. Let 

the collection [c1s q' a • • I ck sq] be donoted by c ; 

The set c* has k • 2q members. 

q 

Now different members of BS cannot have the same 

q 

-1 inverses uqder g + and each member of BS has exactly m q q 

-1 k inverses under g + mq 

-1 Thus crd gm+q {BS ) = k· 2q 1 q 

(BS ) = c* 

q q 

and the mapping g (C*) - BS is 

m+q q - q 

exactly k to 1 o 

- 5 -
REF ID:A38876 

-1 ) Let A be an arbitrary p-block and let crd g (A ~ w. 

p 

Let q = p+n-1 • Now S contains exactly w members, the 

q 

image of each of which under g is A. Thus in C * there are 

p q 

exactly kw members whose images under g + mq are blocks ending 

n-1 

in A. Now BS contains exactly 2 blocks ending in A. Smee 

q 

the mapping g + • C * ~BS is exactly k to 1, the image set 

m q q q 

under g + of kw members of C * must contain at least w 

m q q 

n-1 members. It follows that 2 ~ w and the proof is completed. 

Theorem. Let the mapping g be an onto mapping. Then 

-1 ) ..n-1 crd g (A = ~ for all p-blocks A and all positive integers p. p 

Proof. Let A be a p-block and suppose 

crd g; 

1 {A) + 2n-l • 

-1 ) n-1 From the preceding theorem we infer that crd g (A < 2 and 

p 

-1 ( ) n-1 crd gq B .$. 2 for all q-blocks B and all positive integers 

( ) -n+n-1 

q • Now g S + 1 a S , erd S + 1 = c and 

p p n- p p nerd s B zP • Also crd [S + 1 - g1 (A)] > zP+n-l - 2n-l (2p-l) • 

p p n- p 

and 

gp [sp+n-l - g;

1 

(A)] a SP - A • 

n-1 -1 Not more than 2 members of S - g_ (A) p+n-1 -p 

can 

map, under g , into the same element of S - A • 

p p 

N(B, qi) .S. 2q1 - 2q1 • 2-n+l • 

- 6 -
REF ID:A38876 

Thus 

2P - l = crd [S - A] ~ 2-n+l crd [S + 1 - g-l (A)] > zP - 1. 

p p n- p 

From this contradiction, we infer the truth of the theorem. 

Remark. The preceding theorem shows that the property 

that g be an onto mapping lb equivalent to the property that 

• 

g be noisy in the sense that it transforms a random sequence 

(all blocks equidistributed) into a random sequence. 

Theorem. Let g be an op.to mapping and let s E S • Then 

crd g-l (s) < 2n-l 

Proof. -1 n-1 Suppose that crd g (s) > 2 • Let 

-1 

g (s) = t

1, t 2 , • • • , tk Consider any pair t ,t • i + J. 

1 J 

There exists an integer p such that the central (2p + 1)-blocks lJ lJ 

of t and t are not identical. But then the central (2p+l)-blocks 

i J 

of t , t 

i J differ for all p > p • Let p be an integer such that iJ 

P > max rPiJ I i ~ i < 3 ~k] 

Then no two of the central (2p+l)-blocks of t

1 , t

2, ••• , ~ 

are ahke. But the unages under gZp-n+Z of these k blocks 

are identical. n-1 If k > 2 , this contradicts a preceding theorem. 

The proof of the theorem is completed. 

Remark. It appears that the multiphcitie.s of the mapping g 

at different points may be different. It would be of interest to 

investigate the various possibilities and characterize them. 

- 7 -
Theorem. 

REF ID:A38876 

If g is an onto mapping and 

s = 

-1 is a periodic sequence, then each member of g (s) is 

-1 periodic. Let s have period w , let t 1 g (s) and let μ be 

the period of t • Then μ z p w , and 1 < p < 2n- l 

Proof. Let g be an onto mapping, let 

s = 

be periodic with period -1 w and let t 1 g (s) • Let p (k) be 

s 

the number of different k-blocks in s • Then ps (k) .S. w for 

all k By a preceding theorem we infer that t contains at 

most 2n-l6> different (k+n-1}-blocks for each positive 

integer k. Thus, if pt (m) denotes the number of different 

n-1 m-blocks in t , we have pt (m) ~ 2 OJ for all m • 

Suppose t has no period less than 2n-lw + 1 From 

.,. 

lemma 7. 2 (Morse and Hedlund, Am.erican Journal of Mathematics, 

Vol. 60, 1938, pp 815-866) pt (m) > m + 1 for all values of 

But this is true for all 

m and thus pt (m) 2:.m + 1 for all m 

n-1 Let m = 2 ~ 

n-1 ) n-1 Then pt (2 w 2:. 2 w + 1 , contradictory to 

) n-1 Pt (m .S. 2 w for all m • We infer that t has a period 

n-1 less than 2 w + 1 and t is periodic. 

- 8 -
REF ID:A38876 

Let μ be the period of t • 

n-1 Then μ .5. 2 w From 

a preceding theorem, there exists a positive integer p such 

that μ = p w , and we have w ,$ pw _$2n-l w and 1 S. p ~ z0-l 

Lemma Let m be a positive integer and let B be an 

m-block. For q ~ m , let N(B, q) be the number of q-blocks 

which contain B • Then 

hm 

q~ 00 

N(B, q) 

2q 

= 1 

Proof. We first observe that N(B,q)/2q is a montomc 

increasing function of q. For if c is a q-block which contains B, 

then CO and Cl are different (q+l)-blocks each of which 

contains B • Thus 

and consequently 

N(B, q+l) > 2 N(B, q) 

N(B, q+l) 

2q+l 

N(B, q) 

2q 

Thus we can assume that q =pm and it is sufficient to 

prove that 

hm 

p ~00 

N(B,pm) 

2pm = l 

Let B = B1 , and let B1, B 2 , ••• , m Bk, k = 2 , 

be the set of all m-blocks. Any block of length, pm can be 

written as a p-block of B 1so There are kp such blockso Of 

i 

these there are (k-lf which do not contain B !! B1, and 

thus kp - (k-l)p which do contain B. Thus 

- 9 -
REF ID:A38876 

N(B,pm) > kp - (k-lf = 2mp - (2m-lf 

and 

N(B.em> > 1 - (1 - _!_ )P 

zPm 2m 

But 

hm (1 --

1 f = 0 

p~ co -r 

and hence 

hm N(B,pm) = 1 0 

p-> co zPm 

The proof is completedo 

Lemma. Let B be a blocko For q 2:. n , let D denote 

q 

a partition of the set S of all q-blocks into sets of q-blocks each 

q 

For q sufficiently large, all members 

of some element of the partition D must contain B as a 

q 

sub-block. 

We suppose the theorem falseo That is, there 

exists a sequence of integers q1 < q 2 < ..... , D , D , .. ., .. , and 

q1 qz 

partitions such that some member of each element of D fails to q1 

contain B as a sub-block. But then the number of members of 

D which do not contam B is at least equal to the number of qi 

elements of D , or qi 0 Thus, using the notation of 

the preceding lemma, we have 

- 10 -
But then 

hm sup 

i ---) co 

REF ID:A38876 

This contradicts the preceding lemma. 

Definition• The sequence 

s = 

is said to be transitive provided every finite block appears in s • 

Theorem. Let g be an onto mapping and let s be transitive. 

-1 Then each member of g (s) is transitive. 

Proof. Let B be an arbit.rary k-block. The collection 

g-l (A) I A E S defines a partition D + 1 of all (m+n-1)-blocks m rn nn-1 into sets each containing 2 blocks • From the preceding lemma 

we infer that for m sufficiently large there exists an rn-block 

-1 ) A such that each member of g (A contains B • Now A 

m 

-1 

appears in s and each member of g (s) must contain an 

-1 ) g-1 (s) element of gm (A • It follows that each member of 

contains B and thus is transitive. 

Let fn be a function with domain Sn and range in s1 , 

and let g<::i_> 1 g{n) be corresponding mappings of Sm+n-l 

into S and S into S • respectively. Let f be a function 

m p 

with domain S and range in S and let g(p) g(p) be 

p 1 • m • 

the corresponding mappings. 

- 11 -
REF ID:A38876 

The mappings g~!p-l and g~) can be composed in 

an obvious fashion to define mappings g(p) • g(n) of 

m m+p-1 

Sm+n+p-l mto Sm and thus a mapping g(p) • g(n) of S into S • 

Similarly there is defined a mapping g(n/,. g(p) of S into S • 

It is not necessarily true that g(p) • g(n) = g(n) • g(p) 0 

Let s E S 

s = 

and let 

t • 

be defined by 

The transformation cj> : s ~ t is called the shift transformationo 

It is a homeomorphism of S onto S whose proPerties have 

been studied extensively (see Gottschalk and Hedlund, Topological 

Dynamics. Am. Math. Soc. Colloquium Publications, volo 36, 1955, 

Ch. lZ). A subset Y of S is invariant if cj> (Y) = Y o 

It is easily shown that the transformation g of S into S, 

defined by f , commutes with cl>. i. eo, g cl> = cj> g • 

Theorem. Let f define an onto mapping g of S onto S and 

and let X be a proper closed invariant subset of S , Then 

g OQ is a proper closed invariant subset of s. 

Proof o Suppose g is an onto mapping and .X is a 

proper closed invariant subset of S. Then X is compact, 

g (X) is compact and g ( X) is closed. Since g cj> = cj> g, 

g (XJ is invariant. 

- lZ -
REF ID:A38876 

Suppose g (X) = S. Let s be a transitive point and 

let x E X such that g (x) = s o According to a preceding 

theorem, x must be transitive and thus X = S , contrary to 

hypothesis o The theorem is provedo 

Corollary. g(p)• g(n) 1s an onto mapping if and only 1f both 

g (p) and g(n) are onto mappings. 

Proof. Clearly, 1f g(p) and g(n) are both onto mappings, 

the g (pt g (n) is an onto mapping. 

Suppose g(p) g(n)(S) C g(p)(S) :f: contrary to the 

supposition. Thus, in any case, g(p) 1s onto. Now if g(n) r 

is not onto, then g (n)(S) is a proper closed invariant subset. 

Hence, by the last theorem g(p) g(n)(S) is a proper closed 

subset of S , again contradicting the assumption that 

g (p)" g (n) 1s on too Thus g {n) must also be onto and the secorrl 

part of the corollary is proved. 

The remainder of this paper is devoted to the determination 

of all functions f which determine onto mappings g{n) for 

n 

n ~ 4. 

The totality of functions f which define onto mappings 

in the cases n == Z or 3 are easily compiled and are as 

follows. For n = 2 there are 6 such functions of which 

three are 

" 

" 

- 13 -
REF ID:A38876 

and the other three are the duals of these, that is, the 

functions obtained by adding 1 to each of the function values. 

For n s 3 there are 30 such functions of which 15 are 

as follows: 

l xl 

2 Xz 

3 X3 

4 xl + x2 

5 Xl + X3 

6 Xz + X3 

7 Xl + X2 + X3 

8 Xl + XzX3 

9 X3 + xlx2 

10 Xl + Xz + XzX3 

11 xl + x3 + xl xz 

12 Xl + X3 + XzX3 

13 x2 + x3 + xlxZ 

14 xl + xz + x3 + xlxZ 

15 Xl + Xz + X3 + XzX3 

and the other 15 are the duals of theseo 

Remark. Of the fifteen listed, the first six are compositions 

of mappings for which n :s: Z o 

- 14 -
REF ID:A38876 

For the case n= 4 , it is considerably more difficult 

to determme which functions determine onto mappings. It is 

known that if f is linear in either x1 or x 4 , that is, f 

is defined by 

or 

f(x1,x2 ,x3 ,x4 ) =x4 + f

4(,,x2 ,x3) , 

then the corresponding mapping is onto. There are 496 such 

functions 

It is also known that if f is defined by composing a 

pair of mappings of lower order (in this case a 3 and a 2.) then 

£ defines an onto mapping if and only if each of the composing 

mappings is onto. It is easily verified that there are 22 such 

composed functions which are not linear m ; or x 4 and 

which define onto mappings Of these 11 are given in the following 

table 

1 

2 

3 

4 

5 

6 

7 

8 

9 

10 

11 

- 15 -

Xz 

X3 

Xz + X3 

Xz + X3X4 

X3 + ,X2. 

Xi+ x3 + ;x2 

xz + x3 + x1xz 

Xz + X3 + X3X4 

Xz + X4 + X3X4 

; + Xz + X3 + Xlx2. 

Xz + X3 + X4 + X3X4 
REF ID:A38876 

and the remaining 11 are the duals of these. 

Now a necessary and sufficient condition that the mapping 

g defined by the function f be an onto mapping 1S that 

-1 ) n-1 c rd g (B ;= 2 for each m-block B 1 and each positive m 

integer m • But it is suff1c1ent (theorem due to Blackwell, 

see Rothaus I loc. cit.> that era g-l (B) = zn-l for m • 2n-l 

m 

n-1 and each 2 -block B. 

This criterion is not as difficult to apply as first 

appears if use is made of the following device, illustrated for 

the case n z 4. 

Let the set of all possible 3-blocks be denoted as follows• 

(1) 

000 

001 

010 

011 

100 

101 

110 

111 

0 

1 

2 

3 

4 

5 

6 

7 

Then the 4-blocks can be denoted 

( 2) 

where 

0000 

0001 

0010 

0011 

0100 

0101 

0110 

0111 

1000 

1001 

1010 

1011 

1100 

1101 

1110 

1111 

00 

01 

12 

13 

24 

25 

36 

37 

40 

41 

52 

53 

64 

65 

76 

77 

- 16 -
REE. ID:A38876 

x x 

i J 

(i, J z 0, 1, z ••••• 7 • J .= 2i or 2i + 1, mod 8) 

denotes the 4-block of which the initial 3-block is x 

i 

and the 

terminal 3-block is x 

J 

Now for any specified function f (on the 4-blocks) we 

hst under 0 , those blocks B for which f (B) • 0, and 

under 1, the complementary set. For example: 

0 1 

00 12 

01 24 

13 37 

(3) 25 41 

36 52 

40 64 

53 65 

76 77 

Any 5-block B can be written in the form abc , where 

a, band c are integers from 0 to 7 • a is the integer corresponding 

by (1) to the initial 3-block of B • b is the integer corresponding 

by (1) to the middle 3-block of B and c is the integer corresponding 

by (1) to the terminal 3-block of B . Thus 01011 can be written 

as 253 0 

Now if the 5-block B z abc is to map (under g 2) into 00 , 

then ab and be must appear under 0 in (3) and this condition 

is clearly sufficient. It is thus possible to obtain the 5-blocks 

which map into 00 by taking any element ab under 0 in (3) 

for which the second term b appears as a first term and following 

- 17 -
REF ID:A38876 

ab by the second term of all elements for which b is the first 

termo As an illustration we determine the 5-blocks which m.::i.p 

into 00 and 01 respectively 

00 01 -- -- 000 012 

001 137 

013 252 

136 364 

253 365 

400 537 

401 764 

536 765 

The process can be continued in an obvious fashion. The 

7-blocks which map into 0000 are 

0000 

00000 

00001 

00013 

00136 

40000 

40001 

40013 

40136 • 

But 1t should be noted that in continuing this process, 1t is only 

the digits {representing 3-blocks) which appear at the ends which 

are of concern to us and the intermediate ones can be suppressedo 

We list, m terms of their terminal 3-blocks only, the blocks which 

map into 0, 00, 0000, 00000000 , respectlvelyo 

- 18 -
REF ID:A38876 

0 00 0000 00000000 

00 00 00 00 

01 01 01 01 

13 03 03 03 

25 16 06 06 

36 23 40 40 

40 40 41 41 

53 41 43 43 

76 56 46 46 

When it was found (by hand computation) that there 

existed a function (n=4) which defined an onto mapping, which 

was not linear in any variable and which was not obtained by 

composition of onto mappings of lower order, it appeared that 

it might be worthwhile to determine all such functions. 

This determination was carried through on SWAC. The 

non-restrictive assumption was made that f(O, O, O, 0) = 0 • 

Then of all such functions, those were re3ected which did not 

produce an equal number of 08s and l 1s (eight of each). The 

remainder were then successively sub3ected to tests as to 

whether -1 ) crd g 2 (B 2 = 8 for each 2-blocks B 2 1 crd 

-1 ( ) -1 ) g 4 B4 = 8 for each 4-block B4 • crd g 8 (B8 = 8 for 

each 8-block B 8 • There were 291 such successful matriculants. 

The following data concerning these was recorded on punch cards. 

- 19 -
1) 

2) 

_ BEF ID :A38876 

A tabulation of the function f o 

-1 The eight 4-blocks constituting f (0) m terms 

of their terminal 3-blockso 

3) The coefficients of the polynomial defining f • 

The machine time in carrying through this program 

was 80 minutes o 

Of the 291 functions defining onto maps, the 248 linear 

in the first or last variable were sorted out, leaving a residue 

of 430 Of these 11 were known to be obtainable by compositions 

of lower order onto mappings, leaving a residue of 3Z o These 

3 2 functions are tabulated in the following two tables g 

- 20 -
REF ID:A38876 

Table I Functions on 4-blocks which determine onto mappings, which are not linear in 

either the first or last variables and which are not obtainable by compositions of lower 

order (n < 3) onto mappings 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 

0 0 1 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 0 1 0 1 

0 0 1 1 0 0 1 1 0 0 1 1 1 I 1 1 I 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 0 1 1 0 

0 1 0 0 1 1 1 1 1 I 0 0 0 0 I I I 1 1 1 0 0 1 1 1 0 1 0 I 1 1 1 1 1 1 1 

0 1 0 1 1 1 1 1 0 1 0 0 1 I 0 0 0 I I I 0 1 0 1 1 0 0 1 0 0 1 1 0 0 0 0 

0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 

0 1 1 1 1 1 0 0 1 1 1 1 1 0 0 1 0 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 

1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 

1 0 0 1 0 1 0 1 1 0 1 1 0 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1 0 0 0 0 1 1 1 1 ..... 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 1 1 N 

1 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 

1 1 0 0 1 1 1 1 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 1 1 1 1 1 1 1 

1 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 0 1 1 1 0 0 0 0 0 0 

1 1 1 0 0 1 1 1 0 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 1 0 0 1 1 0 0 

1 1 1 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 0 1 
£ Al Az 

1 1 

z 1 

3 1 

4 1 

5 1 

6 1 

7 

8 

9 

10 

11 1 

12 1 

13 1 

14 1 

15 1 

16 1 

17 1 

18 1 

19 1 1 

zo 1 1 

2.1 1 1 

22. 1 

2.3 1 1 

24 1 

25 1 

26 1 

27 1 

28 1 

29 1 

30 1 

31 1 

32 1 

REF ID:A38876 

Table II. Non-zero coefficients of the polynomials defining the 

functions 11Sted 1n Table I. 

A3 A4 BIZ B13 B14 Bz3 Bz4 B34 c1z.3 c1z.4 

l 

1 

1 1 1 

1 1 

1 1 1 1 

1 1 1 

1 1 1 

1 1 1 1 

1 1 1 1 1 1 

1 1 1 

1 1 1 

1 1 1 1 

1 1 1 1 1 

1 1 1 1 1 1 

1 1 1 1 1 

1 1 1 

1 1 1 1 

1 1 l 1 1 1 

1 1 1 1 

1 1 1 1 1 1 

1 1 1 1 1 

1 1 1 

1 l l l l 

1 l 1 

1 1 1 

1 1 

1 1 1 1 

1 1 1 l 1 

1 1 1 l 

1 1 1 1 

1 1 

1 1 1 1 

- 22 -

cl34 Cz.34 

1 

1 

1 1 

1 

1 1 

1 

1 1 

1 1 

1 

1 

1 1 

1 1 

1 1 

1 

1 

1 1 e 
REF ID:A38876 

It was pointed out by R A Dean and R. C Lyndon 

that the set of 3Z polynomials hated in Table II, can be 

generated from a set of eight by application of two simple 

processes One of these is the substitution (;x4) (x2x 3), i e., 

interchange of x1 an-d. x 4 -and interchange x 2 and x 3 

The other is complementation, i e. , substitution of 1 + x for 

i 

x ,i=l,Z,3,4 i 

7 

10 

Z4 

z.z. 

9 

13. 

14 

23 

The following is a generating set 

-23-
.. ,. 

REF ID:A38876 

UNCLASSIFIED 

WORKING PAPER Noo 22 

A NUMERICAL SIMULATION TO STUDY THE READINGS OF A 

FIXED ANTENNA ADCOCK RADIO DIRECTION FINDER 

UNDER CONDITIONS OF FADING 

Joseph F. Mount 

Co Tompkins 

25 Feb 1958 

10 pages 

In this paper we shall describe a numerical simulation 

from which we try to draw some conclusions concerning the 

behav1c..,r of a perfectly balanced fixed antenna Adcock direction 

fmde1 (1, 2, 3] under conditions of fading. It is assumed that 

fading 1s caused by random cancellation of signals arr1v1ng 

on different transmission paths o Normally these paths might 

differ either in the number of reflections from the ionosphere or 

in the layer from which they are reflected, or botho Minor 

variations in directions of the transmission path from any 

JUmp pattern may occur at the receiving site because of 

variations 1n ionospher1c tilt. variations 1n penetration, local 

reflections, and other causesc 

s - 110 022 
_,.. 

j . 

REF ID:A38876 

UNC:LASSIFIED 

will be centered about two sets of direction cosines, which 

may be specified independently of each other and of other 

simulations at the start of each calculation; an approximate 

intensity is specified precisely for each transmission, independently of all other inputso We allow for the following random 

variations in transmissions, each variation to occur slowly 

enough to justify treatment through use of variables which 

are piecewise constant: 

(a) The relative phase between the two arrivals 

varies randomly and uniformly between 

0 a_pd 2w ; 

(b) The intensity of each arrival will vary from the 

approximate value set by a factor 1 + h, where 

(c) 

h is a sample from an approximately normal 

distribution with mean zero and standard deviation 

which is set as part of the input of the problem; 

The six direction cosines of the arriving signals 

will be modified to direction numbers by the 

addition of independent samples from normal 

distributions each with mean zero and with 

standard deviations which are set as part of,t':i ·~;;,'!>, 

the input to the calculation. 

- 2 -
REF ID:A38876 

UNCLASSIFIED 

These eight standard deviations are set independently of 

each other and independently of other parts of the calculations. 

At least for the time being the calculation will consist 

of the determination of two functions and the recording of 

relations between them. For each choice of the random variates 

the Slgnal strength received at one of the collectors will be 

computed and for each choice the reading of a fixed antenna 

Adcock direction finder will be estimated. The signal strength 

will be calculated straightfo:rwardly. The reading of the 

radio direction finder will be estimated either by computing the 

points of maximum deflection of a Watson Watt [2] type display 

under the stimulus of the two ugnals, or by computing angles 

of minimum deflection for a rotating goniometer [l] type 

display. In each case, it wJll be assumed that the equipment 

receiving the signals is in perfect adJustment, so that none 

of the calibrating complexities of [l] and [2] will be introduced 

except to the extent that the angle of arrival influences the 

octantal error. 

It is proposed that relations between these two functions 

be exhibited by means of tallies in one hundred positions, 

giving a kmd of scatter diagram. Thus, 1f the functions are 

- 3 -
REF ID:A38876 

UN CLASSIFIED 

denoted by f and F 1 we propose that the range of possible 

values of each be divided into ten parts, arbitrarily as part 

of the input routine, and that the number of examples found 

in which the functions fall into each possible pair of cells be 

recorded and presented as output. 

2. The functions to be computed - - the two-channel case. 

For the two-channel case, we examine equations (8) 

of [l] (these equations will be repeated below), and try to 

compute the response of a two-channel direction finder 

under the influence of a pair of Slgnals of the type indicated 

above. 

Explicitly, we assume that signals with frequency 

w/lt• are being received over two paths. The quantities 

pertinent to the two signals will be distinguished by subscripts, 

the subscript 1 for the first signal and the subscript 2 for 

the second. The first signal will arrive with direction cosines 

a 1 , ~land '\'1 , the second will have direction cosines 

a 2 , 132 , and Yz • The signals will have amplitudes (weighted 

by the effectiveness of the collectors) A1 and A 2 respectively. 

The first signal will be taken to set the standard in phase, 

so that the responses of the two antenna pairs to it will be 

given by direct analogues of equations (8) in [l] , 

- 4 -
REF ID:A38876 

UNCLASSIFIED 

(1) 

wa1

d 

EEWl = 2A1 sin 2c sm wt 1 

where, as before, d is the distance between collectors 

of the pair and c is the velocity of radio wave propogat1on. 

For the second arrival the phase is displaced a constant 

amount e2 sampled from a uniform distribution over the 

range [O, 211'] • (Here ~ 2 plays a role somewhat different 

from the role of ~ in [Z].) The responses to the second 

signal are respectively 

(2) 

The analysis here follows that of [2] • 

The total NS signal is the algebraic sum of the two 

- 5 -
REF ID:A38876 

UNCLASSIFIED 

or 

(3) 

wf32d 

s2 sin Zc cos wt] 

Similarly, 

(4) 

wj32

d 

- A 2 sin ~Z sin Zc cos wt] • 

The development of the functions to be tallied follows 

the general development m [ 2] o 

A heterodyning signal EL cos (w + w

0 )t is mixed 

with ENS and EEW • the difference frequency is extracted, 

and the signals amplified to be presented respectively as 

horizontal and vertical deflections. Using (3) and (4) and 

the relations 

(5 > 

cos (w + w )t sin wt = ~:[Sln (Zw + w )t - sm w t] , 0 0 0 

cos (w + w0 )t cos wt = -!;[cos (2w + w )t + cos w t) - 0 0 

the retained signals are proportional to 

- 6 -
(6) 

REF ID:A38876 

UN CLASSIFIED 

w ~ld w~zd 

2c +AZ cos ez sin Zc ) sin w

0

t 

-Azsinez 

w~ d 

sin cos w t ?c 0 

-(A1 sin 

wa1

d 

+AZ cos ez 

waza 

= ) Sln W t 2c sin Zc 0 

- AZ sin e2 Sln 

w~zd cos w t 2c 0 

The deflection may now be calculated as a function of t• 

2 2 2 formally. r =Ev + EH 

The maximuin deflection (and the minimum) occurs when 

dr/dt = 0, hence when 

(7) 

where the dot denotes differentiation with respect to time. 

Since we propose a computational, and not an analyhc-, 

attack on the problem, we propose to simplify the notation 

at this pointo To that end write the computable functions 

(8) 

w~ d wJi2d 

VS = - (A1 sm~ + A 2 cos e2 sm Zc ) • 

w~zd 

V C = - A 2 sin e2 sin Zc 

= -

- 7 -

+ A2. cos 

wazd 

sin Zc 
REF ID:A38876 

UNCLASSIFIED 

so that 

{ EV = vs sin w t + VG cos w t 

0 0 

(9) 

EH = HS sin w t + HG cos w t 

0 0 

Then the condition (7) for maximum or minimum 

deflection gives 

(10) tan 2 w t 

00 

In a complete cycle of 2 Tr radians, this equation (10) is 

sat1sf1ed by four angles w t separated by tr/2 rad1anso 

00 

Values for Ev and EH at these points may be 

found by writing 

tan w t :::: 

00 

-1 + /,tan 2 2w t + 1 

00 

tan 2w

0

t

0 

using a sun1lar formula to find tan w

0 t

0 /2 (choosing the 

ambiguous sign carefully each time) and writing 

(11) 

sin 

cos 

w t 

00 

2 tan w t /2 

0 0 = ~~~....-~~~ 

1 + tan

2 

w

0

t

0 /2 

1 - tan2 w t /2 

0 0 

LI> t = I 2 0 0 i + ta.11 "' t I 2 0 0 

Independently of the choice of sign, the four displacements may be computed easily. 1£ the computed values 

of (11) are written 

- 8 -
REF ID:A38876 

UNCLASSIFIED 

5

0 = sin w t and C = cos w t 0 0 0 0 0 

then at the four extreme deflections the components are 

EV 

l 

=So VS+ Co V C and EH 

l 

= SoHS + CoHC 

E z 

v =co vs - sovc and E 2 

H = CoHS - SoHC 

(12) 3 E 3 EV =--So VS - Co V C and = -SoHS - CoHC I H 

4 and E 4 Ev =-Covs+sovc = -CoHS + SoHC c H 

E 3 

v 

4 l 2 and Ev above are obtainable from Ev and Ev by 

multiplying by -1 , and a similar remark applies to the 

horizontal components, only the first and second of these 

deflections will be considered. Write 

the first or the second of the deflections will be retained 

1 2 2 2 depending on whether (E ) or (E ) is largero We 

choose the first function to be talhed as 

0 

F 1 is a measure of the received signal strength. 

Finally note that for the deflection ret.amed the displacement is at an angle 

- 9 -

cj> where 

0 
REF ID:A38876 

UNCLASSIFIED 

(13) tan <I> = 

Ea 

H 

E a 

v 

for the chosen displacement index a • This is the tangent 

of the angle read on the d1rect1on finding equipment 

For some a , (3 write tan cj>0 = r1' Choose 

a , (3 to be horizontal direction cosines accepted as correct--

say the mean from which a 1 and i3i deviate. Then the 

td.ngent of the "error" in reading {including octantal error) is 

(14) 

tan cj> - tan cp 0 

F Z = tan (cf> - <l>o) = 1 + tan <j> tan cj> 

0 

• 

This function F 2 1s the second function to be tallied. 

BIBLIOGRAPHY 

1. C. Tompkins. Elementary Calibration of Direction 

Finding Equipment from Target Transmitter Tests, and 

Graphical Plotting of Bearings under Idealized Conditions. 

Memorandum with some considerable circulation, 

10 August 1957. 

z. C. Tompkins. Calibration of 2-Channt•l Adcock Direction 

Finders. Memorandum with some considerable circulation, 

22 August 1957. 

3. R. Keen. Wireless Direction Finding, 4th Edition, 

Iliffe, London, 1947, especially p.283-285. 

University of Cahforn1a, Los Angeles 

- 10 -