3 

4 

NECEISARY 

ACTION 

llOTEAND 

RETURN 

SEE llE 

SISllATURE 
-

SESRSI' 

PRELIMINARY REfURT ON AFSAM 9'DEPTH S1'UDY 

INTRODUCTION: 

One ot the greatest ditticulties encountered in assessing the securitJ 

or cJ"1Ptographic devices which operate on principles similar to that or the 

AFSAM 9 is the determination or the probabilit7 of depth. It has been 

possible to derive sat1sracto1"7 a• priori estinates or the probabilit7 or 

depth tor the class ot structures wherein each setting has a unique pred-

- ecessor; e.g. the AFSAM 7. However, a• priori estilllates or the probabilit1 

ot depth. are not at all adequate tor structures, such as those generated 

by the AFSAM 9, which are comprised not onlJ or single points (i.e. setting• 

which have a unique predecessor), but also or critical points (e.g. branch 

points and origins). 

Thus the onlJ' PMOt.ieal means or ascertaining t.he incidence ot depth 

tor ati"Ucture• containing eritical poirats is bf means ot aqplj.ns. As to 

what apecitic lllQll>l'-ng pl'Oeedur•s should be emplo78d, there are obviouaJ.7 

ve17 EnJ' theoretioall.7 IO\lnd procedures one could propose; however, whether 

o:r not a particu.lar sampling prooedUl'e is teaaible will be largel.7 determined 

by the kind ot hish 1peed arual;vtio equipnant that is available. 

In Part I ot the zreport which follows is given a description and 

ana]Jrsie ot the 1ampl:lng procedures that have been dmaed to determine the 

incidence ot depth.tor AFSAM 9 trattla together with a deacription of tha 

vartoua tnea of atatiat.101 ttat can be secured bf utilizing thaae procedure&. In Part Il ot the report,, the 1dentit:S.cation and evaluation ot 

UKUSA 848 - :...... :.e--=-== SEGRE'F 
szcan 

those notch pattern parameters, on which the incrdence or depth depende, 

are discussed. 

Part I 

The aampling procedure which ia ourrentl.1 being uaed in the study ot 

the AFSAM 9 atructure utilizes the tacilitiea attorded bf PLUTO. Another 

sampling procedure which will make uae ot ATLAS II ie ourrentlJ' being 

J)rogramed and will be read7 for uae in the amar future. The t'iret hall 

or Part I will deeoribe the PLUTO prosralfl. Thi• will be followed b7 a 

description ot the ATLAS II program, 

The aamplins procedure on PLUTO ia logicall.7 (but not chronologiaall.7) 

equivalent to the following 1tepa1 

(1) A quaai-:random initial aetting ia t1rat generated (b)" a method 

to be deacribed later). 

(2) With the wheela aet to thia initial aettins, the AFSAM 9 11 then 

atepped through a meaaa.se ot length 5000, and the 5000 th aetting ia than 

atored in a "memory." 

(3) The wheels are now aet to a new quaei-re.ndom initial aetting, 

and the device ie then stepped through a aacond meaaage, laah aubaequen\ 

setting that :la s:enel'ated ia compared with tha setting :ln the ttmemor1•" 

The reaults ot this compariaon can be oharaot.eriead br the tollowina 

tigurea, where Mi,j 11 the jth setting on the 1th ma11age1 

2 
--

Ml,l Hi,1 M2,1 Mi,1 "2,1 

"i,,5000 ~.500J I ~.5000 "2, k ( k > 5000) 

C&ae I Case II Case III a,b, 

It there ia a hit before the drdce has stepped more than 5000 times, 

aa in C&ae I, the tirat •aaage is in dept.h witb the aecold tor at least one 

setting. It there ia no bit. before tbe second •asap has been stepped 

through 10,000 settings, aa shown b7 caae II, the two Maaages are not in 

depth. 

(4) It tbere ia a hit. before the second mauge baa been atepped 

through leas than 10,000 settings, but more than 5,000 settings, as inrllcatacl 

by Case DI, the 5000th setting of the second •aaage ia then inserted in the 

"memor;y,• aid •ch setting of the first •asap is now compared with tbe 50006b 

setting ot the second •asage. If there ia a hit before the first ••sage baa been 

stepped through 5000 settings, the two •aaagea are then known to be in deP'h tor 

at least one setting. 

' 

SE€RE'f 
Hi,1 ,1 

~.10000 

Case III a 

Dept.h 

M 2,10000 

~.5000 

Case III b 

Ho Depth 

(5) It the first and aeconl •aaagee are found not. to be in depth, 11 

new quasi-random initial setting la generated. am this }bird ••aa.:e ia then oomparad tor dep;h with each ot the tirat two •aaagea in the mnner outlined 

in atepa (1) through (4). 

(6) Sampling according to the atapa prescribed in (1) through (5) ia 

continued until aom •aaage j ia found to be 1n depth with •o• ••aage i, 

where j > i. The "statistic j" thus obtained. correspond.a to the number ot 

measagea that had to be sent in order to insure that the jth •asage waa 

the first one Ji.elding depth with &n7 prior message aent in the amm cl'1J)to• 

period. It an adequate n\Dlber ot runs are Ede, aa7 n, Jielding the distribution ot the j 1 a, this statistic can then be utilised as a reliable 

criterion to determine the a.munt ot traffic laa.d that the AFSAM 9 can 

aatel.T c&1T7 in al'Q" given cr,ptoperiod. 

§JEcCiffiJE1P 
In a similar fashion other types of statistics can also be obtained, 

such as a statistic corresponding to the number of messages which have to be 

sent in order to insure ttat exactl.7 k pairs 01 mssagea be in depth tor at. 

least r settings; or a statistic corresponding to the number or messages which , 

}lave to be sent in order ttat k n-tuples be in depth tor at least r settl.nga .. 

The above sampling procedure was not feasible until just recently, as 

the time involved in obtaining a single statistic or the t11>e j required 

about 120 hours. The samplihg process has now been alm>at completelf 

autonati111ed by' devising a program which enables PLUTO to generate its own 

"quasi-random" initial settings. At the present ti• PLUTO can obt.ain a 

j statistic in about 45 minutes. 

Concerning the sampling procedure currently being used on PLUTO, the 

feature which is most likeq to incur adverse criticism is the Mthod b,- which 

initial settings are generated. The initial settings of Maaages that are 

to be used in obtaining an observed value of j are generated in the toll.cRring •nner. In addition to the actual AFSAM 9 notch pat.tams, separate 

rand.o~ constructed. notch pa.ttems are inserted on the wheels W-2, W-3, W-51 

w-6, W-7 and will be referred to as the secondart patterns. The wheels are 

now initiall.1' set to so• randoml.7 selected setting (designated. here as the 

priml'1' setting) and stepped through massage 1. Attar the final setting ot 

the •ssage has been generated., the rules ot motion ot the AFSA.M 9 are amended. b7 the addition of the toll.owing rules: 

1. W-1, W-2, W-5 and W-6 are del.&7ad bJ" the simultaneous occurrence 

ot a no-notch on the seconda17 pattern of W-5 and a no-notch on an awdli.&17 

5 

SECRE'F 
two point wheel which steps eve17 time. 

2. W-i is stepped by the occurrence of a notch on the aeconcla17 

pattem of wheel W - Ci-1)_, where 1 • 31 41 11 I. 

The wheels are now stepped according to the amend.eel rules ot mtion 

for acme fixed intenal, 11a7 101 000 1tepa. The 101 000 th set.ting arrived 

at under the amended rulea of motion ia now defined as the initial eettiq 

for ••sage .2. BT •king this procedure it.erat.ive, a Ht of initial set.tlag• 

can thaa be generated. 

It is apparent that the aboYe procedure will ultimatelf result in the 

generation of a cycle, ao that alter a certain point in the itleration the 

proceaa will beco• periodic. There is therefore a lilld.t to the number of 

initial starts that can be generated by the a.bcmJ procedure. Since it la 

eas7 to ascertain at just what point the process bacmms periodic, this limit. 

ia determined and ia nnar exceeded. 

Inas1111ch aa the AFSAM 9 notch pattema are held constant throughout 

a111 given run, it is the aeconia.17 J&tterns and the priar;y setting which 

determine what initial settings are used in securing 11. statistic. It ia 

therefore iaportant that a new random. pri.1111H7 setting and a new random set 

ot seconda17 patterns be selected tor each statistic that ia to be obtained. 

In regard to the selection of the amended rules of motion ref erred to 

in the aforementioned procedure tor generating initial settings, the selectitfb 

was not oompletel.1' arbitaey but was gonrnad by the following factors 1 

(a) It is desirable that the amended rules ot motion be eas7 to 

implement on PLUTO, 

6 

§JECCRIE1r 
(b) In comparison with the actual AFSAM 9 structure,. the 

structure generated by the amended rules or motie>n should not be comprised 

or a disproport.ionatel;y large number or confluences. 

(c) It baa been ahown in [1] that the cycle structure ot the 

AFSAM 9 is comprised ot 108 disjoint sets or structures, where the selection 

or the initial setting of W-1, W-2, W-5 and W-6 detennines which ot the 

structures is being used. It was desired that dept.h studies be confined to 

a particular one ot the 108 mutuall.J' exclusive sets into which the structure 

or the AFSA.M 9 can be resolved, rather than to study the entire structure. 

Therefore, a sat ot amended rules of motion in order to be eatiaractor7 muat 

maintain the relationship or the settings or W-1, W-2, W-5 and W-6 nace1Sa17 

to this chosen one ot the structures. 

Inasmuch as it is desirable ttat &n.J' method of generation or initial 

settings a:lmulate a rand.om process, one would like to know it it is 

atatisticallJ' teasible to assume that the initial settings generated by 

the procedure described above could arise tty random sampling from the 

population at large. To determine whether or not the hn>otheais that the 

generated initial settings could have been obtained by random selection can 

be statisticall.J' rejected, one could devise &DJ' number of tests to exhibit the 

degree to which the 1111thod ot generation ot initial settings is characterized 

bJ" nathematical randonness. However, it should be pointed out ttat e'V'en 

though one were able to reject statisticall.J' the hJpothesis that the generated 

initial settings are mathamaticall.J' random, the net.hod of generation might. 

still be acceptable. That is, a sat of initial settings nay tail to exhibit 

1 SECRET 
characteristics or mathematical randonmes• and )'8\ be dispersed eo 

haphazardl.7 over the, entire AFSAM 9 structure that their use dues not 

invalidate a117 statistical analyses pertaining to dept,h studies. All that. 

is required here as regards the conditions of selection of initial aettinsa 

is that there- should be no mrked element ot pr.rterence or bias that would· 

tend toward the inclusion or exclusion or certain local areas of the AFSAM 9 

structure. 

Suppose, then, one were to compa:te sneral prominent oharacteriiitica 

(such aa precentage of frequenc7 of occurrence of the •tnaturee, trequeno7 of 

incidence or certain entl"J points, expected length ot leact-in tor each or 

several ent1'7 points) ot the statistical picture at a particular AFSAM 9 

structure obtained fl'Oll N •thematicall.7 random initial stazota with these 

same characteristic& of Ille statistical picture obtained fl'Oll N initial 

settings that haft bB8n generated by the method in question. It it were 

found that in both oases these characteristics were subetant.ial~ the aame, 

it would then aem quite reasonable to regard the •thod ot "S>seudo-random." 

generation as aat.i1tactor1' for the pdrpoae ot dept,h stud,.. 

A comparison teat ot this t1J>9, baaed on a sample ot 1000 initial starta, 

baa been applied to one or the 108 sets or strtlctures generated by the AFSAM 9 

tor an arbitnril.1' chosen set of notch patterns. The results ot this te11t &N 

described in Appendix A. 

The ATLlS II procedure involves a more direct approach to the solution 

ot the deJ,'Jth probl•, stllpJ.7 bf answering the question, "How •111' •aaage• 

!!!! be sent which rill be in depth with a given •saagef" Thia 11U111ber can 

be found bJ' reproducing that port.ion or the cycle structure which coiltaina 

8 

SJEECJRtIE1P 
SISRiT 

all patha leading into the giTen message and tor which no path exceeds the 

mximum me11&age length, aa1 5000. In order to simplify the pro.blem and thus 

decrease nachine time, the assumption ha.a been made that the proba.bilit1 of 

depth with an indicator &J'Btem (restricting the number ot possible message 

starting pointa) ia ~ aignil'icantl7 greater than the probability ol' depth 

with no restrictions. At this writing there ha.a bean no conclusive evidence . daD1ing this asaumption. 

A more detailed description ot the ATLAS program follows: In a manner 

analogous to a CJCla stud7, whereby a picture of a particular cycle structure 

is desired, consider the massage as a "c:rcle" or length 5000. The antey points 

to this "cycle" are then all the branch point.a on the massage together with the 

initial or starting point or the message. Then the lead.-irmwill be the paths 

taken by other messages such that depth occurs. 

The method or obtaining this sub-structure is a two-phase procedure. 

The first phase involves no:rnal (forward) stepping ot the derlce trmn soma 

setting M1 to produce the massage as tar as setting M5000• The second phase 

uses reverse (backward) stepping starting from the branch points and M1 and 

continuing 5000 points or until an origin terminates the stream. Thia can be 

shown graphical]Jr in the following diagram, where 0 represents an origin, B 

0 a branch point: 0 

0 5000 0 

5000 

() l 

B 

c M1 MESSAGE M5000 

SECRET 
In order to aim.pli!)' a description ot \he ATLAS procedure, oonaider 

the tollowing diagram, where an arc centered at ~he maaaase bra.nob point ii 

drawn through each aucceaaive point in the structure (backvard) such that. a 

point on arc Ai ia 1 aettinga removed from the meaaage branch point • 

.......... 

MESSA GB 

Two or more points on the .._arc have in conaon the 3-wheel CCM setting 

contained in the APSlM 9 setting. PurthermDre, t'lie motion of t..he ramining 

five wheels proceeding f'ran a branch point (necceaaarilJ' or mu.ltiplioitJ two) 

in one direction ia the complementaey mot.ion or the opposite dil'ection. These 

two statements constitute the ba.aia ot the counting procedure, wberebJ aucceHift 

CCM settings account tor the i associated with .A1 along one stream (direction), 

and the number ot auch strea• r

1 interaect.ing or tel'Jld.nat.ing on At ia 

where 91_1 aid o1_

1 are the number ot branch pOinta and origins reapactiwl.J' 

along A1_

1• Bence the tota]J,t7 ot points in this sub-structure 11 

'4999 

T • & t 1 1•1 

--

§JE~JE1F 
If one calla the stream originating (backwards) trom the meaaage 

"machine number 1", or m1, then in detennining the two predecessors ot a 

branch point, let the predecessor that ia reached bJ' moring W j (one ot the 

5 wheels not contained in the three CCM wheels) originate a nav achine, ~· 

while the other predecessor will continue along ~. Continue this procedure 

tor each branch point. Then at some arc Ai there will be t 1 machines still 

active in the backward generation and counting procedure. Therefore the 

procedure is first to move the CCM wheelll; secondly (tor •ch 111:1.) to determine 

whether the point is a single point, branch point or origin (a1multaneoual.1' 

finding the motion pattern).; finally to JDOYe the wheels it necessar,y. U 

mi is at a single point, no "machine" change is necassar,y. A branch point 

inYOlves setting up a new "machine", while an origin causes that •machine" 

. to be rad.a awil.able tor a new branch when needed. 

The preceding paragraphs show how T, the tot.$1 number ot points trm 

which a depth of at least one can occur, is found. In general onw ia looking 

tor TJ>1 the number of points pelding a depth ot at least D :> 1: 

5000-D 

To • E t 1 1 

Then the total sub-structure will give Rn • E T0 + 5000-(D-1) points whi<:h 

will result in a depth ot D, where the summation is over 

the ant17 points to the •saage, sa7 lft• where 1 ~ 5000-(D-1). Other counts 

to be tabulated are the number of branch points and origina in the sub-structure. 

Let the total number of points in the structure be designated by H. With 

each of several sets of notch pattems, a sufficient; number ot runs will gift 

enough statistical data to peld p • ND/N' which can be used to estimate the 

ll 

SE€RE'f 
SECIUiil' 

true probabilit7 of deptho 

Part II 

In &D1 empirical approach to the problm of determining the incidence 

ot depth, the question quite naturall1 ariae1 as to whether one should con-

. tine his atud.7 to sanral sets of notch pattame that have bean delibaratei7 

selected eo a1 to amplif)' or exaggerate certain attributes of the notch 

pattern population at large; or whether one should amplo7 the mthod of l'&lld• 

, . selection. It enough information concerning the relation between the notch 

• 

pattem parameters and the genaaloa ot the AFSAH 9 structure ia available, 

the tormr procedure would se• to be the more expedient. It therefore ia 

'desirable to devote som effort to the problem ot ident:ltying and ewluating 

those notch pattem par~ers of which the incidence ot depth is a tanction. 

The moat important. attribute affecting t.he incidence of depth ia the 

number of branch point.I tl'at are contained in the motion structure generated 

by a set of notch pattema. Let It {B) be the function which relates the number 

of branch poirdi s to the notch p1tt.era paranmtars. The CCII aetttngs distribute 

themselves into three claaaee Of 1&ise ('Jb)3 /3, liince (21,1,) • 3. Ona of the 

criteria tor a branch point is that W-3 be on a minus (-). Hance the number 

of settings of" the COit 'which ._, :rJ.•ld branch -points ia (36) 

2

15/3 • 6"8(). 

Th• 16 branch point patterns on 5 1'beela gi"fe 

where Ci is the number of no-notches preceaded "7 no-notches (-) OD w-1. Hance 

12 

§IECCRIE1F 
N (B) • 6480 Bi.. a, Ba ~B5 (15+c6) + 186 (15+C5>]. 

• 25 1 920 B4 S., B9 ~5 (30-B6) +• B(, (30-B5)] 

• 51,840 s,., a, Bs G5 (B5+B6) - B5 B6] 

In the above expression s1 (i • 4,5,6,7,S) corresponds to the number at 

blocks or which the notch pattern on wheel wi is comprised. The number 

ot blocks ia defined aa one halt the number ot changes of sign. BecaUH 

ot the criteria that are used in defining whether or not a giTen notch pattern 

ia an admiaaable one, N (B) ia independent ot the pat.terns on W-1, W-2 and 

W-.3, and the Bi are limited to the range or values 5.; Bi,_ 15. It ia 

apparent t:tat the function N (B) ia mximized when: 

( 1) B

4 • S., • B8 • 15 

(2) a

5 

• 15 and/or a

6 • 15 

and is minimized when: 

(l) 81 - 5 (i • 4,5,6,7,8) 

Therefore, the number of branch points in Bll7 AFSAM 9 structure cannot 

exceed 11.8,098,000,000; nor can the number ot branch points be leas than 

2,430,000,000. It the aTimlJID number ot branch points that ia realiuble 

ia defined aa 100 percent aaturation, it then tollowa that the totallt7 of 

branch point.a can nnar be leas than 2.05 percent ot saturation. 

Statistics releY&nt to the incidence ot depth Which have been secured 

tor a particular set of notch J11.tterna would be much mre significant it 

the probabllit7vith respect to a given notch parameter of selecting the 

SECRET 
set ia known. For example, 1£ a set or patterns is selected tdlich generates a 

structure with the number or branch J"Ointa classd.tied as la.8-1&9 percent 

saturation, it would be Tel7 useful to be ablo to estiate the pro'tabilit.1 of 

securing bJ' random selection a set or patterns tor which the number of branch 

points would have a clansitication which exceeds 1+9 percent saturation • .J - ... -

Because the degree or branch point saturation ia the moat important 

attribute affecting the incidence 9£ depth, it is expedient to devote some 

time to the problem or deriving a probabd.lit7 distribution which can be uaed 

to determine the probabilit1 ot selecting a set ot patterns for which the 

degree ot saturation is greater than x percent. Inasmuch aa the number of 

branch points is, in terms ot the notch pattern parameters, a function 

onlJ ot the number or blocks, the problem or obtaining such a diat.ri'ba.t.ion 

obviousl.T entails a means ot counting or est:iating the number of adJDiaable 

notch patterns which have i blocka ( 5 ~ i :6 15). The probl• of 1ac11ri.na 

such counts is not exactl.7 trivial, but could be progrumed tor ATLAS II. 

However, the probabilit7 distribution tor the population of pLt.terne which 

aatist7 only that portion ot the criterion ot admiaaabilit.7 which requires 

that there be no more than tiTe contiguous notches or no-notches can be 

obtained directly from known results obtained in a report by B. Harria, 

' 

NSA-314, "On the Number ot Cyclic Bina:r;y Patt.ems"• Thia distribution 

appears on page number 15. 

ll 

SIE<CiffiJE9P 
M:~~B 

SIGRD DISTRillJTION A 

! ?ill RegrouDld P' 1 l 

Theoretical 

Freguencz: 

l o.5] 0.003 .038 ... 

7 0.035 

8 O,l.IJe, .11.r. 182. 

9 o.as2 .282 355. 10 0.291. .291t 370. 11 0.172 .172 217. 12 0.058 .058 72. 13 o.:J l4 0.001 .012 15. 

15 o. 1259. 

The working hJpotheala waa now ad.a ta.t the above dlatrlbutloa 

tor the population ot patt.ema whiab are on17 sart.iall.7 acllllaalble 

doe1 not e11ential.l1 dltter t... the dlat.ribat.lon tor the population of 

adnd.aaable i:atit.ema ~nit could therefore be uaed to eat:late the pro--

portion Of adnd.aaable .. t.tel'bl Which haft i blockae Thia eat.mt.a 

was then lncoprorated in to an ATLAS ptoaram to obt.lt~ the dea1red 

probabillt.7 d~.st.ribtlM on, which la si wn in Appendix B, 

lmpirlcal l'elUl.t a which lend crade'nce to the vol"ld.ng hJpotheala nterred to in the preceding para11raph ware aecurecl in the following mnner. 

The diatrUut.ion of the amaber of adnd.aaable pat.tame which tan l bloclal 

waa obtained tor a prniou~ conat.ru.ct.ed and a-1.lable aample of 1258 

t'ul.11' adlld.aaable pat.tens, ( Por a deacript.lon of the mt.hod "1 which 

these admiaaable pat.tame wen conatru.cted, aea reference i)Jat the aid ot. 

t.Jd.a report,). Thia aupla d:latributlon together with the camputat.loa ot 

2 -Y.:. la gl Ten on PAI• 16. 

15 

SE€RE'f 
DISTRIBUTION B 

P(i) 

2 

1 !9. Regrouped f 0 (to - ft). f ft - 5 

~D 6 47 .037 .021 

1 

8 185 185 .147 .049 ., 

9 359 ,,9 .285 .045 

10 372 372 .296 .Oll 

11 195 195 .155 2.230 

12 83 83 .066 1.681 

13 

14 lD 17 .014 .6"3 

15 4.679 

Fl"Om a table ot :ic. 2 it ia aeen that when the number ot degrees ot-treedom 

is 6 a value ot X. 2 aa great or greater than '4.?79 would occur purei., as a 

result of chance in more than two out of three random samples. Therefore 

the working b1J>otheatia that distribution A is not eaaential~ different fl'Olll 

distribution B 1• mtiNlt oonaiatent. with tha abova :results. 

An examination ot the distribution in Appendix a •haw• that the 

probability ot aaauring by random aelect.ion a sat. of adnd.aeable pattema lla'Yiilg 

a percentage of saturation greater than 50 per.cent ia le1a t.han 0.0005. If, 

t.heretore, it were known tha. t the onl3' important, attribute affecting the 

incidence ot depth 1a the number ot branch point. a comprising a structure, 

statistics releYBnt to the incidence ot depth could then be securecl b7 the 

procedures described in Part. I for several set.a ot JBtt.ems haring, aa7, 

tro.m 48 percent to 50 percent, saturation. These atatiatica could then t. 

used as criteria t.o determine the amount ot traffic load that can be aatei, 

tolerated, since the probability of a situation arising tor which these 

saturation c~iteria are not satisfied. would be lass than 0.0005 • 

.. - --

S'Ei:IffiIE1P 
Sl!iGm' 

The identification and e'V8.luation or other notch pattern parameters 

which attect the incidence ot depth are therefore matters or practical 

importance. Before attempting to identify aJ'l1' other JBttem-parametere which 

might affect the incidence or depth, however, it is first necessa17" to 

detennine how the genealogical characteristics'or a general structure of \he 

AFSAM 9 tfPe are related to the incidence of depth. Those characteristics 

ot the structure which do significantly affect the incidence of depth 11&7 

perhaps then be expressed as some tuncti\.on of the p1.ttem parameters, as ha1 

alread.7 been done tor the function N ( B) • 

An investigation or the characteristics of a general structure revaill 

that there are three distinct types or classes or branch points. Those 

branch points which have as their two predecessors (either illlnediate or 

removed by one or more single points) two branch points are here clasaitied 

as t;ype I. Those branch points which have as their tw predecessors two 

origins are classified as t1Pe II, am those which have as their two 

predeceaaora one origin and one branch point as t)'JJ9 III. 

In terms ot these three classes of branch point.a, the two limiting 

distributions tor &111' tree comprised of N critical points ares 

TJpe I 

TJpe II 

T;ypa III 

Distribution I 

N/2 

H/2 

0 

17 

-SE~RET 

Distribution II 

1 

1 

R-2 
(The configuration compriaad. of an n""°1cle branch point together with !t1 

entire associated aft-crcle net."MOrk ot prad.eceeaora ia here retel'l'8d to al 

a "t.re•" •) 

From the illuatra.tiond of two trees which are p.nn below,, it. h 

apparent that tor atNcturea comprised aolel.7 of critical points tbtl 

function r (P) 1 corresponding to the probabilit1' of a pair ot m1aap1 

being in depth, ia maximised tor the set ot treea haYing the l:lmitl111 

distribution I• 

Distribution I : H • 32 Distribution II: R • 32 

ff PE II 'l'Rll 
SICR.m 

The function r- (PI) has been tormulat.ed tor "thra part.iculal' Diatri'bllticm 

I cnse tor which N • -tt: 

2· f ~ L-2 ] Lal x.-1] P (Pz) • N2 t l3 (2) -1 N - (2 -1» · 2 

In the above expression L ia the length ot the !lllessage and N iii the wigh! 

ot the tree, ioao the total number ot points or setting& of 'llhicb thra tfNGil 

is comprisedo The function r (J'i) give~ the exact probabilit7 of depth foJP c 

•ssagas ot length L 'Whan N is a power of two11 and is a ire&&on&bl.7 sood 

approximation tor all other admissable values ot No (·Tl'e•s having tins 

limiting distribution I require that N:ao (mod 8') 0 while \hoBQ ha'ring thg 

limiting distribution II require that N:!O (mod 2)) o 

The corresponding function F (PII) has bean formulated tor all 

' 

admissable valum ~ N, and appears below: 

It is apparent that when L 1:1 2, 

and that when L ~ 3, F (P1) > P (P11) o Moreover0 when L 1111 approxiatel.7 

50 or 111Dre and N >> L0 the ratio 

!J!l!... .. ! Plpt:[} 2 

L-2 L-1 L-1] (3°2 -1) N - (2

2 

-1) 2 

L (N+2) - L - (N+l) 

It would thus appear that the t1J>9 ot branch points of which & atructuro 

SEGRE'f 
san 

is _predom:lnantlY comprised ia a factor which doe• eigrdticantl.7 atreot tbe 

~ncidence or depth. 

It has been conjectured that the distribution of single points be-I 

tween branch-origin segments and branch-branch segments may •teriallf arrect . tbe probabilit7 ot depth. In accordance with this conjecture, it is belieTed 

that the moat favorable distribution consists or distributing single points 

as unitohil.y a.a possible between· branch-origin segments or the tree. Therefore, • :1 

one ma7 conditionallJ' regard tbe diatri"1tion or single points aa a factor 

affecting the incidence or depth. 

Aa regard.a this third factor, it can be demonstrated that the 

distribution or airgle points between branch-branch segments or the structure 

cannot be •de to differ .substantiall.7 f"rOJR the distribution ot single points 

between branch-origin a'9gment.s; so that it is illposaible to distribute the 

qingle points in the ideal mnner described above. To illustrate this tact, I 

•.;unsider the functions FBO (t:i,wj,Xic), r 88 (Ci,Wj,Xk), 0888 (CpWJj1t1Y1) and 

OoBO (C1,W j•lic• Y1), where rBO determine• the nwnber ot branch points which haft 

I uactl.7 one immediate predecessor that is an origin, r BB determine• the number 

ot branch points which ban exactlf one imediat.e predecessor that is a branch 

point, GBBB datermlnea the number or branch points whose two iaediate 

predecessors al'tl branch points, and o

0

B> determines the llUlllber ot branch points· 

whose two immediate predecessors are orlgina. :ft can be Pz-own that. the 

function corresponding to the number of branch point.a whose tw 1--siate 

predecessors are a \)ranch point and an origin is al..,. null tor AFSAM 9 

atl'Ucturee am therefore need not be considered. The functions '.BO' 0

08,., 

•• 

§ IECCIIBJE1P 
818Bf 

'ss• and OBBB are expressed below in tel'lll8 or tbe notch parameters 

Ci' Wj' Ik and Y1, where c

1 corresponda to the number of blocks on Wi' w3 

co:rresponda to the number of 010 contigurationa on V j' 'ic corraaponda to the 

numbet of lOi contiguratibna on Wk' Jd Yl COl"l"88ponda to the nmnber of 

t ' 000 oontigu.rationa on w1• In all of the following expraeaiona Hoo ia the 

tunction corresponding to the number of 00 configuration• in tba dilated 

outfJ'li stream ot W-3. 

,, 

+ C4 c, (15-06) C7 's • C4 C5 (15-06) X7 Cs + X4 c, (15-06) w7 w8 

+ c4 (15-05) 16 c~ c

8 + 14 (15-05

) 16 c

7 w8 + c4 (15-05> c6 17 C8 

+ C4 15 (15-06) C7 Cs + w 4 (15-05) c6 w7 ws + W4 x, (15-06) C7 w8 

+ W4 'f5 (15-06) 17 XS + c,. w, (15-06) W7 Ia + w,. (15-C5) c6 c., Cs 

+ c4 (15-C5} c6 c

7 18} • GOB> 

GOB> • Hoo {x,. r, w6 x., Is + 14 w, y6 W7 Xe + W4 Y5 w6 "1 18 

+ W4 W5 ?6 '7 Xe + W4 1, (15-06) 17 "s + X4 x, (15-06) W7 Ws 

+ W4 (15-C5) 16 w7 Ws + X4 (15-05) 16 X., w8} 

21 

SE€KE'f 
Siem' 

'BB Cl Hoo {X4 C5 (l5-C6) x., Cg + c,. 15 (l5-C6) C7 la + w4 (lS-C5) C(. x., Ca 

+ c

4 (15-05

) -16 c

7 18 + 14 ~15-0 ) x6 o.1 cs + c4 <1s-c5> c6 w7 x8 

+ w,,. x, (15-06) C7 Cs + C4 c, (15-C6) W7 Is + 14 c, (15-c,> C7 "a 

+ c,. w, (l5-C6) x,, Ca + W4 (15-05) c6 C7 Wg + C4 (15-05) w6 x., cs 

+ 04 (15-05) 06 c,, Cs + X4 (15-c,> "6 W7 Ws + 04 c5 (15-06) C7 cs 

W4 W5 (15-06) W7 W8} - ~ 

0BBB • 8oo {x4 w, 16 X., wa + W4 Y5 w6 11 ws + 14 1s w6 w7 "s + •4 "s t6 "1 "a 

+ x4 1

5 (J.5-c6) "? 18 + w4 (15-05) x6 x

7 x8 + x4 c1s-c5

> 16 w7 Is 

+ W4 I~ (15-06) W7 Is} 

Tbe function ifloo has not been explicitl.7 formulated in terms ot the 

notch pa.ttem ~era of W-1, W-2 and W-3; however, empirical study 

atrongl:' 1111ggest.a ttia~ ~ is relative}7 1rdependent ot the patterns on I 

W-1 and W-2 and 1• pr!mrl17 a function of the number ot 00 cont1gurat1om 

in the pattern on W-3· ln ~case, tor any gtftn. set ot pa.ttems it ia 

eaa1' to determine bJ' actual count. the exact value ot ffoo• 

A cursoey examination or the functions 'so' 'BB' Gmm• and 0080 reveals , , 

that it ia impossible to design a set of pat.tame tor which PIK> differs 

appreciabl.7 from P BB and tor which OBBB differs from °om o Therefore the 

ideal distribution of single points referred to abow, Tis, that no single 

points occur between branch-branch segment.a of the atructun0 ia phyaicallJ' 

unattainable, and cannot even be approximated.. 
However, although the distribution of pingle points between branchbranch segments cannot be nade to differ radicall7 from the distribution 

ot single points be~ween branch-origin segments, it is possible by 

maximizing or minimizing GOB> or 0

888 to cause the number ot branch points 

harlng as their two immediate predecessors two branch points or two org:ins I 

to vary over a considerable range. It has already' been demonstrated that, 

for N (B) held constant, the incidence of depth is very mch greater for 

structures characterized by a t1P8 I limiting distribution than tor those 

characterized by a t1P8 n limiting distribution. Therefore, it would aa• 

quite logical to hypothesize that, with N (B) held constant, the incidence 

of depth for a general structure (one that is comprised of a nmch greater 

number or single points than of critical points) can be significantl.T 

increased or decreased by increasing or decreasing the rmmber ot branch 

points having as their two illDlled.iate predecessors two branch points. 

It the aforementioned hypothesis is valid, it then follows tlat the 

function Gees is an important parameter affecting the incidence or dept#h. 

To determine the statistical teasibilit1 or the above hypothesis the following 

test was mde: Two sets ot patterns were constructed so that the structure 

generated by Pattern I was comprised or the same number of critical points, 

vis., 48 percent - 49 percent saturation, as that generated by Pattern II. 

Moreover, Patt.em I was designed so as to make the function 0

888 relativel.T 

small, while Pattern II wa11 designed to make 0

888 relativelJ' large. Pattern I 

and Pattern II are listed in Appendix c. Reference to the distribution in 

Appendix B indicates that the probability or select-ing at rand.cm a set ot 

pat\erns which generates a structure in which the critical points comprise 

more than 49 percent saturation is less than 0.0002." Therefore, the 

•...;,;t 
parameter N (B) ia very much larger for Patterns l and II than it would I 

ordinar111 be for an oper&t.irin.'Ll AF:-,jAM 9 derice. The actual value of N (B) 

tor Patt.em I was 5·1;2ll,.'.31.'.3,280 branch point.a and tor Pattern II waa 

56,862,000,000 branch pointao 

It will be recalled at thie point that the 6rcle structure or t.he APSAM 9 

can be resolved into three pair-wise disjoint set.a or atructurea Ci (i•l,21 3) 

and that each aet c1 r.an in turn be reeolYed into 36 pair-wiae disjoint aubaeta 

ci,j (i•l,2,3, j•0,1,2, •••• 35). It ia ea~1 to deduce that the number or 

branch points ia the aama tor each one ot the 108 aeta of atructu:rea c1, J • 

However, the £unction 0

888 will in general dirter tor each c

1

,j. The function 

Hoo will, ot course, take on three values, i.e. a Y&lue tor each of the three 

aeta or atructurea c

1 where Ci• t

5 c

1 j (i•l,2,3). For both Pattern I ard 

i•o ' Patt.em 119 it was decided to contine obaervationa to the claaa of atruaturaa 

c

1 ,

0

• For Patt.em I, ffoo(C1) • 2625, G888 (C1) • 90,578,250 (0.47 percent of 

all branch point.a in c

1 ) and 0

888 (c1,o> • 2, 529,6~0 (>.48 percent of all branoh J 

point• in c1, 0) For Pat.tam II, Hoo (C1) • 5195, 9 cc1> • 3,991,754,seo 

(21.06 percent ot all branch points 1n c1) .ind O~ (C1 O • ll0,911,0SO I J 

(21.07 percent ot all branch point.a in c1,o·> -

I • The distribution of the j - at.atiatic ror a 'sample of size 30 waa next. 

secured tor the two 1et1 ot patterns, I nncl II, where in both oaeea obaenationa 

were limited to the aat of atructuraa c

110• (The 3 - atatiatic baa alre&d7 

been defined in Part I aa the number of meSt:1agea that had to be aent in order 

to insure ttat the .1th maaaage waa tba first one 7ielding deP,h with &DJ 

prior message.) These two diatribu.tiona are giYan in Appendix Do 

......... 

24 

§IECCRJE1F 
'• 

The meana tor the above two sample distr1DUt;ion were now compared to 

determine whether both di atribut.ions could have baftn drawn from the aame 

parent-population. Aaauming ttat the two underl)'ing diatributiona are nornal 

with identical varianca, one may teat the hypotheaia tiat the two means are 

equal b,y using "Student•s 11 .'t distribution. 

The measuremnt needed tor testing the above hJpothesia ia computed from 

the relation 

~ -~6~go> + C7~2) 

' -~ 474 • 21.8 

The value of D, the difference between the two means, ia 201.7 - 160.5, 

or U.2. Thia value of D :la to be judged with reference to a hn>othetical 

value of zero. Accordingl.7 tor T (the d~"Scre):lancy axpreaaed aer.a norm.1 ........ 

deviate) we haw 

1tL.a 1 dn T • 21.8 • •""7 

It the true value of D were zero, a discrepancy as Br9&t as this or greater 

would occur as a result of chance more than § times out of 100 as a result ot 

random fluctuations of sampling. Therefore, even with a standard significance 

ot 1 out ot 201 one aamiot reject the hJpothesis' that the two aampla 

25 

SEGRE'f 
, :::f 'but+an• ot the 1tatbUc 3 could lsft !Jean d ........ trcm t"'i,- parent. 

pol'Ulf tlOllo 

fow~er.11 one cannot conclude on the baaia ot the results ot the aboYe 

1 teat l hat the function 0

888 ia not a parameter atf'ect:lng the incidence ot 

depth' rctr it the proba.bilit7 P (P) ot a pail' ot ••sages/being in depth 11 

· inde1 a ~unction of H (B) and of 0888.11 i.e. P (P) -+JF'(B), Oses], then 

the •r• teat aimJ>l.7 provide• empirical evidence t; .Support the etatemnt t•\ 

~r<P> I rv 0 ~<JaBB N (B) • AS perc,- saturation 

lt -~ft~ well be that if' a similar teat had bem conducted tor the case 

WbeN .ff (,} cE 30 percent saturation 

might have aaaumad algn:lf'icant propol't.:l.ona;.. ) 

ftlei'e Ila qo- loPcal reaaon to assume that 

'l F(P) and:: F~PJ are linear. '710mm NB f' 

Therefore rnotber teat to determine the ettect ot '- on the incidence of I 

depth ·ren I (B) N 20 ot- 30 percent saturation baa been conducted. In anr 

caaeo rinc19 tor.l(B) -.x, 0ssB • 0.11 it is apparent t.hat if CJsss ia a pa.ruat;er 

atfecJ.ng ~ha I incidmce ot depth11 it i• not a wrr ~tioant , __ paraaa\er -.. 

M (B) ~ le8 perc!8ftt aaturationa 

'I" rttema IV and V the j-atatiet.ic was o~lnede A aampla ain o~ 

40 W.•·•atlv:ltda a 22.53 percent saturation. The ... theo17 that waa uaed on ': I I 

. 
Jllttern I and pattem II will be used to obtain the tollowing results in 

the comparison of pattems IV and V 

2 

• (122.7575) + (J.42.452) 

40 

The value ot D is computed : 

thus: 

T • ~t~: • 2.46 

From. this T value one finds when compared with the norna.l curve or distribution, 

• that this value places us at the 2 percent level ot confidence ot approximation 

ot the normal curve. Since this sample of j-statistica so nearq tits the 

normal one may conclude tlat with the larger sample and the cut to 22.53 

percent saturation that this sample does come trom the pa.rent population. 

To provide some 1daa ot just how sensitive a parameter N (B) is, a 

, distribution ot j statistics tor a sample ot size 20 was obtained. Thia 

distribution, labeled distribution III, is given in Appendix. D. Notch pattem 

set 111 (listed in Apendix C) tor which N (B) • 22.53 percent saturation, •• I 

issued-, to obtain this distribution. It will be noted that the man tor 

distribution III is signiticahtq greater than that tor distributions I and II. 

'Z1 

SEERET 
A more detailed analysis of the patterns I, lI, IV, V appea~s iJ! App~n41x 1 .. .. , .. ,_ 

CONCLUSIONS: 

Logical deduction supplement~ in some instances by statistical,~ntetence strongly- auggea~e tt&t when N (B) is relativel.7 lar~e, i.e. N, (B) > $0 

pe.rc.ent saturation, the onl.1' important. parameter Jif~.ecting the i~idepce of deP'h ..J 

is N (B). However, it is quite probable that G

888 becomes a significant 

parameter when N (B) ass\,\11l8s values ttat are, in the probabilit1' sense, llJON . nonnal, viz. 15 percent - 30 percent. saturation. Additional statistical te1ta 

will have to be conducted. belore any conclusions can be Ede regarding this 

last possibilitr. 

Because the incidence of depth is so dependent upon the 'Value ot M (B), it 

is suggested. that the AF~ 9 be utilized in such a manner aa will preclude the 

possibilit7 or N (B) ever exceeding, sa1 25 percent or 30 percent saturation. 

This could be easily accomp1i.&J'!ed it it were not -oblectionable-to ext~Odi 

further the definition ot admissabilitJ" ror notch patterns. For example, we ... -..... "' } ..., ... ·"- ' - .. ~ ·~ .. 

could define an. ad.miaaable "set" of pattams as one tor whieh N (B) <JO 

per~ent saturation tor all p>ssible aubji~t~ cotnprisM ,or,·•igl\'b pr.tt&rna. 

Onl.T sets of pat.tame which a~e· admissible in the above senSG woUld t.hea be 

.1 ~ .... I I "o I"' p I 

· se:tect trcinl. his eat ot pat.tams a subset ot eight pattems tor which 

N (B) > 30 percent saturation. 

The abov'e redeti~tion ot admiasibiliti wouid pennit ~g~ei.ter vt>ltime or 

ttoaftic flow and would thua increase the efficiency of the device, provided, 

ot course, that the security artorded bJ' the AFSAM 9 ia'a function ot notch 

J>att~m-identitication rather than of recovery. 

§~CCJ!RJE1P 
Sl!i9RB'f 

In this study no attempt was nade to determine whether the incidence 

or depth is appreciably greater when message starts are restricted. by an 

indicator system. Tlie only data relevant to this question that are current11' 

available are the statistical pictures in Appendix A. If probability of 

depth is not independent of the proposed indicator S7Bt•, it would seem 

logical to conjecture that the alignment or the alphabet ring with respect to the 

notch pattern sequence is significantly arrecting the incidence or depth. 

To detennine whether the alphabet ring alignment is a depth para.mater, 

the following test is proposed. For a suitable set of notch patterns two 

distributions or a j -· statistic are obtained. One distribution is obtained 

for the case tor which the alignment or the alphabet M.ngs minimizes the 

number or indicator settiqgs that are origins. The other distribution ie 

obtained for the case for which the alignment or the alphabet rings minimi.1ea 

the number of indicator settings that are origins. The mean of the two 

distributions could then be compared to determine whether their difference 

is significant. 

Whether or not it will be necessaey to un:lert;ake &IJ1' investigations to 

determine the degree of dependence of F (P) on the proposed indicator ayatam 

has not yet been determined. 

l "Some Genealogical Characteristics of the C70le Structure ot the 

AFSAM 9 For a Particular Set ot Notch Rings":, R. P. MurphJ' and 

Warren Lot1, C84.2 

2 "Notch Rings Suitable tor Use in AFSAM '1 and AFSAM 911 : 

Marguerite D. Newell, C90.0214 

SE€RET 
Robert P. Murphf 

RSA-314 

March 1955 

!bis ))aper•• in draft tonn when Mr. MurJ>h7 reaigned. lt• 

pxoeparation to:r publication ha• been the l'eault ot a oo-operatiw 

etton ot Manin Basa, NSA-311, Bernard Harria, RSA-314 and 

Lt. Wtl14am H. Corneliue, Jr., RSA-314. 

SECRET 
OEblt1Jt APPENDIX A 

In order to ascertain whether the clusterjng or message starts in 

various parts or the cycle structure exhibit any "non-random" characteristics 

when quasi-random or indicator starts are employed, a sample of 1,000 random., 

19 000 quasi-random, and 1,000 indicator starts were obtained. These were 

grouped according to points at which their successors entered a CJCle. The 

frequencies or each group are presented in fable I. 

To teat the hJpothesis that these three samples na1 be regarded a1 three 

aamplea from the same population, we construct the likelihood ratio teat tor 

homogeneit1 or samples from a multinomial distribution. 

Let x1j be the number or elements in the 1th call in the jth B&!llple 

(i•l,2, ••• ,m1j • 1,2, ••• ,k) 

Fornd.ng the likelihood ratio, we get: 

I;< rij n . .Lj ,J 

SE€RET 
2 log\. • rJ: • 2 E E "1 • (101 _it - log E ~ \ - I' ~~-:l)(o1-l) i j " "'J j n "/ 

· We know that. t.hia q.uant.it7 S.1 approximata].J d:lltributad aa 'J,.! 'Id.th 

I 

(k-l)(m-1) degreee of freedom. (Logarithms are baae •) \ 

~~ \ AJJP17ing the above te1t 0 we find ~ 111 17 .621 anll we thentor1 •4,oept, 

tbe null hJpotheai1 at the .05 lrtal ot 1ignificanca. I 

. 

In Tabla II, the average length• ot lead-ina to T&riou1 07011 1nt17 poia\1 

are shown. Due to the non-onhogonalit1 ot the data, a r1gre11ion anaJ:11:l1 

was not carried out at this U.•. Sina• the tabla augeat1 ttat n.ncloll ' .. tan1 

. 

' 181' give ri•• to longer lead-tn1, some anal;rlla of tll:l• t)1MI vtll be carried 

out at som 1'lture date. ''lha data doe a not rnaggaat tl•t reaul.ta ft'Oll the 

quaai-ranclm start.a would lead to 1-eaa depbh than the rand.ca atan•• 

ENTRY RANDOii CIUASI-RANOOM IQICA'§)I 

AA lU 14'1 128 

AB 194 179 1?3 

AO 60 " ,. B\ 133 143 131 

BB 68 72 83 

BO 30 24 24 

II) 42 30 ,, 

Bl 71 72 85 

Reaidue 260 269 :113 

§IECCiffiJE1F 
g~im~a 

~~~ ..... ~ .... 

TABLB II 

ENTRY RANDOM QUASI-RANDOM INDICIA'roR 

AA 3llll0 295353 272378 AB 3840ll 386665 373349 AC 183975 198623 17'1730 Bl 289334 282557 283168 BB 316828 309518 300674 BC 200403 168741 185079 BD 24<XXYI 206810 228950 BB 323878 321169 346601 

3 

SE€RET 
) 

I 

PERC»IT J PROBABILITY OF SELECTillJ 

SATURATION .l SET OF PATTERNS HA VINO 

00 

01 

02 

°' 04 

05 

06 

~ 09 . 10 

11 

12 

13 

14 

15 

16 

17 

18 

19 

20 

21 

22 

23 

24 

25 

l HIGHER PERC»IT SATURATION 

1.000 

1.000 

1.000 

1.000 

1.000 

1.000 

1.000 

l.000 

1.000 

0.999 

0.998 

0.994 

0.986 

0.9'14 

0.952 

0.923 

o.s79 

0.828 

0.766 

0.697 

0.621 

0.51.6 

0.1.76 

0.399 

0.331 

0.281 

PERCENT PROBABILITY OF SELICTINO 

SATURATIOI A SIT OF PATTERNS HAVIIO A 

26 

27 

28 

29 

3Q 

31 

32 

33 

34 

35 

36 

37 

38 

39 

40 

Ll 

42 

43 

44 

45 

46 

47 

lt8 

49 

50 

51 - 99 

.;PGllllll fucENT SATURl!IOI 

0.221 

0.177 

0.141 

0.109 

0.085 

0.065 o.oLS 

0.035 

0.025 

0.019 

o.ou. 

0.010 

0.007 

0.005 

0.004 

0.003 

0.002 

0 .. 002 

0.001 

0.001 

0.001 

0.001 

0.001 

0.001 

o.ooo 

o.ooo 
APPF.NDIX C 

f'ATI'ERN I PA 'l'TERN II PATTERN- III 

1 2 .3 " 5 6 7 8 12.31&5678 1 2 3 " 5 6 7 8 

0 0 1 1 1 l l l 1 01111111 11100000 

1 l l 0 1 1 1 l l 11100000 0 1 1 1 1 0 0 1 

2 01100000 0 1 l l l 1 l 1 1 1 1 0 l l 1 1 

3 10000000 10100000 00010111 

4 1 l 1 l 1 1 1 1 1 1 1 1 1 l l 1 11010110 

5 11011111 11000000 01010110 

6 11100000 11011111 11011001 

7 01000000 01000000 01101100 

8 l 0 1 1 l 1 1 1 l 0 0 1 1 1 :( 1 10111111 

9 00011111 00001100 00101011 

10 01100000 0 1 1 11 l'l 1 11001010 

11 11000000 11101100 11010010 

12 00111111 00111111 10001101 

13 01011111 01101100 01101000 

14 10100000 10111111 00111000 

15 11010111 11001100 01110111 

16 01111111 01011111 11101011 

17 00001000 00001100 00100001 

18 1 1 1 1 0 1 1 1 11011111 11010010 

19 10011111 10001100 10111101 

20 11101000 l l l l 1 l l l 01111000 

21 01010111 01101100 01101111 

22 00111111 00111111 10100100 

23 01001000 01101100 11001111 

24 10110111 10111111 10111100 

25 01011111 01010000 01100011 

26 01101000 01010011 11100111 

27 11010111 11010000 01011111 

28 11111111 11110011 11111101 

29 10101000 10110011 10111111 

30 00110111 00110011 10100100 

31 10101000 10110011 00010011 

32 10l'l1111 10110011 10010110 

'' 11100000 11000011 11010111 

34 10111111 10100011 00011111 

35 10000000 10000000 10011000 

SE€RET 
,.. 

- APPDIDU q I 

PATTERN IV PATTERN V \ 

l 2 3 4 5 6"7 8 \~34567S 

0 01i"f1111 01111111 

1 11100000 11011111 

2 01111111 01101100 

) 10100000 10000000 

4 1111112.l 11110011 

5 11000000 11011111 

6 l:tllllll !!J-0110-G 

.,. &1~00000 01001100 

8 10011111 10110011 

9 00000000 00010011 

10 01111111 01101100 

11 11100000 11001100 

12 00111111 00111111 

l3 01100000 01010011 

u 10111111 10100000 

15 11001100 11001101 

16 01011111 01111111 

17 00011111 00011110 

18 11011111 11100001 

19 10011110 10000001 

20 1 1 1 1 1 l 1 l 11111110 

21 01111110 01011111 

22 00111111 00101101 

23 01111111 01000000 

24 10111111 10110011 

25 01011111 01011111 26 01011111 01111110 

27 11011111 11001101 

28 11110011 11110011 

29 10100001 10110010 

30 00100001 00111111 

31 10100001 10101100 32 10100000 10110011 

'' 11000000 11110010 

34 10100000 10111111 

35 1 o o o o' o o o 10000000 

(Both patterns have the aama saturation aa i:attem 3, vis 22053 percent) 

a 

' §JECCJR.IE1F 
APPENDIX D I 

(j - 1tati1tic1 tor messap,e1 of lens'h 5000) 

DISTRIBUTION I 

1 234 

2 203 

3 189 

4 .305 

5 69 

6 150 

7 283 

8 220 

9 1.38 

10 182 

11 .39 

12 108 

13 182 

14 365 

15 157 

16 144 

17 275 

18 231 

19 209 

20 229 

21 299 . 22 228 

23 99 

21t 156 

25 176 

26 244 

Z1 ]J6 

28 118 

29 434 30~ 

6050 

j - 201.67 

0 - 85.28 

DISTRIBUTION II 

2.30 

199 

154 

283 

118 

237 

75 

214 

144 

146 

151 

105 

1.32 

20 

192 

159 

85 

126 

379 

lo6 

187 

48 

162 

2ll 

174 

364 

122 

61 

58 

17] 

1.815 

']' - 160.50 

a • 83.37 

SE€RET 

DISTRIBUTION II! 

197 

381 

355 

187 

314 

209 

263 

355 

il5 

350 

214 

126 

290 

201 

404 

359 

261 

27 

383 

295 

5592 

a • 101.8 
DISTRIBUTION IV 

1 113 

2 310 

3 90 

4 JU 

5 173 

6 60 

7 252 

8 536 

9 154 

10 56 

11 273 

12 83 

13 106 

14 294 

15 291 

16 109 

17 161 

18 122 

19 157 

20 221 

21 200 

22 71 

23 361 

24 2:17 

25 212 

26 2C11 

'Z1 113 

2S 208 

29 485 

30 140 

31 l'n32 82 

33 53 

34 .358 

35 183 

36 23 

YI 461 

38 166 

39 380 

40 151 

i . 206.75 

0 .. 122.7575 

APPENDIX D 

a ... 

DISTRIBUTION V 

3.03 

138 

390 

59 

174 

99 

421 

355 

150 

273 

116 

40 

364 

208 

250 

296 

606 

286 

83 

.304 

559 

199 

.384 

.304 

459 

2!J 

48 

378 

' 384 

98 

262 

278 

260 

3.36 

348 

439 

256 

"49 

470 

342 

'J • 2'190925 

0 • 142.542 
APPENDIX E 

SUMMARY AND RESULTS 

I. 'lbe four sets of observations J11, J121 ,J211 J22 were plotted on 

probability paper. No severedeviations from nonnality were noted. J

11 

corresponds to pattern I, J

12 to pattern II, J21 to pattem IV, and J22 

to pattern v. 

II Sample means and sample variances ware computed. The tact that 

the tour sets or observations are heteroscedastic was noted and verified bf 

Bartlett's Test establishing significanc~ at the 1 percent level. 

III An analysis ot variance was carried out by inverse weighting of 

'V'ariancea per Theorem ot David and Neynan ("Extension of the Markoff Theorem 

on Least Squares," Statistical Research Memoirs., 2: 105-116 (1938)). 

Let Ho:P11 • .)112 •ft 21 -.AJ22 

In accordance with the linear hypothesis write 

and 

H0 is then,<91 • )"j • o. 

/j1 is the effect of saturation level, );_ is the effect or the branching pattem 

within saturation level. 

eijk is the residual error; furthemore, e ijk is N (O,o

2

ij) • For convenience let r.~ 1 • o, E ~i • o. Let a1j

2

• 02/'rlilj wherew1j are weight.a uaad 

to correct tor heteroscedast1ci~7. Designate sample estimates ot 

A, 191, ~ j• a

2

ij by M, b, c, s. t b1 • t ci • o 

In ·the Neyman-David Theorem, the Wij are known ccnstanta. In the problem, 

they were derived from the data, a procedure which will tend to weaken the 

SE€RET 
eifplicance lenl of the test somewhat. In new or the large number of d,agrea1 

2 

ot freedom for estimation of each aij' it is felt tlm.t this will not be too ser1ous, 

.A.) To deterndne·,Jihe atfec\,._ot.J! ~ reduotion of the total 8Ulll a_t lquares 

unler the null hypothesis. 

Compute .the least squares estimate of .JI• .~ 

Assmne: Yijk • }( + E, ijk 

than>?• M 

2 

SSE • E Wij (Yijk - M) ijk 

SSM • TSS - SSE 

~SSE ~ • -2 E Wij (Yijk - M) • 0 

ijk 

Mij is the number of observations in group Jij 

M • 

SJECCRIET 
2 

SSE • E Wij (Yijk - M) ijk 

Since M • 

SE€RE'F ' 
SICRl!l' 

Thie gina the partition or t.be sum of squares wder tine Qllll I 

h71>ot.heaie o A07 ettect duia to .j1 and Y mst provide a further ~-

due ti on ot S8Bo Since the data is non-orthosanal we can not iast.!ate 

parametara aeparatal.T but must repeat the entire prooeae ot obtain.aimu.a.• . i ··-· I I .,.,., .. I ,_.. ....... ,.. 

taneoua eatimateao 

Let 8i • 03 • o, 

tben Mu • }{ 12 • l<.1• 'h • .)-f..22 a J<.2 

anc1 Y1Jk • Jt.+ ~1 • e i.1k 

~S::' • · 2 E Wl,l (tl,lk •Mt - bi) • 0 

jk 

I 

l 

I 

\... 

i 

l 

l 

i 

I 

.. 
S:\nce ~ • - "i bJ nrt.w of f bi • 0 

E wij tijk • Ml E wij •13 + bl t (Nlj wlj - N2j W23) ijk !3 .1 

Solution ot this set ot equations provides the estillata1 "i,• b

2

, 111 

tor 81• {J 2, /{• 

\' 

I 

5 
SISRB'l' 

SSE - SSE' is the reduction :lb au ot equarea dUe to the in\roduction 

ot bi. 

r • Reduction where ~. ia t.he number ot dagreea of treadam clUe to 

SSl1/N8 

el"l'Or -., be used to, teat the 11Jpothe1i1 ~ i • o, 

I Row conaider ~I Y13k • .I(+ p s. + r j + e ijk 

vbe~ {j 1

, not all s~ro and 7f 3 not. all 1aro, 

Aa before, compute tbe l.eaat equarea eatiatea and the partition of 

the awa of aquarea, 

' 

§JE<CJFcIE1F 
SICRm' 

.. E wij yijk • M11 E W1j Nij + b1 i E W1j Nij + E W1j N1j cj j,k j j I j 

Since b~ • - b'1 

We get: 

The solution of these equations IB7 be obtained using conYentional 

a.trix methods (e.g. Ga.use - Doolitt.J.e, Crout, etc.), 

The reduction in BWll ot squares due to' error ia obtained aa tollOWB: 

7 
... 

Designate M11 + b1

1 + C j by ~j 

SSE0 - SSE" .~is the additional reducti,o,n in smp.s_ot aq~rea due to .I ...... .. , .. 

error obtained b7·int~cing Cj• 

8 

§IECCiffiJE1P 
Due to 

Total Sum of Square1 M . 

SSE 

Reduction due to b1 SSE' 

Reduction due to c.1 

SSB" 

ANALYSIS OF VARIANCE 

d.t. 

140 

_l.,. 

lJ9 

__!.. 

1.38 

-1.. 

137 

* aisniticapt at .01 level. 

s.s. 

The Jvpot,haaia ffoiKu • I< 12 • J.(21 • Jca2 is then rejected at tbe 

.OI' level aaCl the riF-test" indicates a aigniticant effect due to both 

saturation level aid branching pattern tor theae tour aeta or obserY&tions. 
E yijk 

2 

E yijk 

W13 

Nij 

Wij Nij 

M 

M' 

cj 

A 

A X1j 

":'- ij Wij Nij 

- 28.650 

180.615 

-30.286 

6,697001.SU 

211.494 

28.650 

23·7.915 

30.286 

215.701.. 

5582,41952 

§IE~RJE1f 

Total 

10,,32 

8,661.,974 

140 

129.500 
@!~~a U IUI 'l:All CL lL2J 11 

'( II 

SSB l,551,362.2ac, 

SSM 5,209,152.502 

SSE1 11 4541 870.382 

SIB" 11 367,518.195 

2 

§IE£IffiIE1F 

... 
.. 

81 • 201,545150 

s

2 • 210,866.50 

83 • 602.779.50 

s

4 • 812,672.79 

s • 1,e27,86k129 

BARTI,ElT1S TEST 

Nl 29 6949.84 8.84806 

R2 29 7271.26 

R3 39 15455.ed 

B4 39 20837.76 

R • 136 l,34lt.0.18 

Si 

N log .§ - t ft1 log -;"'; . N pi 

e.e91J,7 

9.61..750 

9.91J{33 

9.~0771 

• 1293.04856 - 12~.69854 

• u..35002 

2 2 

s1 • E X1 - JI 11 

2'6159374 

. 257.94543 

376.25250 

387190667 

129310'4856 

1 l 1 1 1 1 

c • 1 + ?; {~ + '29 + 39 + 39 - i36} 

• (.121786 - .007353) 

• 1 + .01907 • 1.01907 

M • lZ...0815 

M is ai§li tlcant at .01 level. 

SE€R1E1f