`Identified tion Procedurefor at Mimbomputer",
`Adv. In X-ray Analysis, V24 (1980) pp. 83-90
`
`RS 1028 - 000001
`
`
`
`A HANAWALT TYPE PHASE IDENTIFICATION
`
`PROCEDURE FOR A MINICOMPUTER
`
`Robert L. Snyder
`
`New York State College of Ceramics
`
`Alfred University. Alfred, N.Y. 14802
`
`INTRODUCTION
`
`The use of computers to aid in the identification of phages
`from their powder diffraction patterns was pioneered in the mid
`1960's by Frevel, Nichols and Johnson (1-3). Today's most widely
`used Johnson algorithm conducts a reverse sequential search by
`comparing each reference pattern in the JCPDS powder diffraction
`file (PDF)
`to the unknown pattern.
`A figure of merit is computed
`for each match and the patterns with the best figures of merit
`are listed at the end of the search.
`The Nichols approach is a
`reverse search of a singly inverted reference file. An inverted
`.file is one which stores the reference patterns according to the
`d value of the lowest angle 1003 intensity line (dl). This type
`of file is analogous to the Hanawalt search books distributed by
`the JCPDS for manual searching. when an inverted file is stored
`in a random format, along with suitable disk directory files,
`only reference patterns containing d1 values of interest need be
`read in the search.
`. Both the Johnson and Nichols algorithms use the full PDF
`which today contains about 35000 patterns of highly variable
`quality (4).
`The Frevel algorithm is the only one,
`to date,
`which attempts to deal with the problem of poor quality reference
`patterns. This approach also uses a singly inverted reference
`file; however,
`the file is restricted to three hundred commonly
`identified phases in unknowns (5). The use of this drastically
`restricted file enabled this algorithm to be the first to be
`converted to run on a laboratory sized minicomputer. This pro-
`gram has been recently generalized by Edmonds.
`Johnson has also
`converted his algorithm for use on a minicumputer but due to the
`exhaustive search approach it also nust use a greatly reduced
`
`83
`
`1‘!
`
`Pcatumes
`
`ix. ac-3%, Meat"; "'34 Q"°)_f’F‘”"9°'
`
`RS 1028 - 000002
`
`
`
`34
`
`R. L. smvnen
`
`Frevel type of reference file.
`Recent developments in computer technology have brought
`powerful minicomputers with large amounts of mass storage into a
`price range that most laboratories can afford. This in turn has
`increased the desirability of a full PDF minicomputer Search—match
`system, For reasons of either mass storage capacity or computa~
`tional speed none of the existing algorithms are directly convert-
`able to a minicomputer environment. The development of the full
`PDF search-match system described here was done under the sponsor-
`ship of the Siemens Corporation and is currently part of the soft-
`ware supporting their D500 powder diffraction system.
`
`DESIGN CONSTRAINTS
`
`For the implementation of a full file search—match system on
`a modern minicomputer a number of desirable or essential features
`must_be incorporated.
`The following design constraints, once
`established, dictated the form of the Search algorithm.
`1) The entire data base should be contained in less than five
`megabytes of disk storage. This allows for implementation
`on all but the very smallest of current laboratory mini-
`computer configurations.
`To meet this constraint a binary
`compression format was devised for each of the active patterns
`in the PDF. All d values are converted to integer d—codes by
`dividing them into 1000.
`Thus the integers 1 to 2048 will
`represent d values ranging from 1000 to 0.588. This integer
`conversion of the d values introduces an average A29 round off
`error of 0.025°, for Cu radiation d values greater than 1.0,
`with a maximum round off of 0.05°. Since the average A29 for
`the cubic patterns in the PDF is 0.10 (4),
`the maximum round
`off error of 0.050 does not significantly degrade the reference
`data. The advantage is that the integers 1 to 2048 can be
`-
`stored in ll binary bits.
`Using 11 hits to store the integer d—codc leaves five bits
`which can be used to encode the intensity value and result in
`the storing of each d—I pair_in one 16 bit minicomputer word.
`Intensities are therefore stored on a scale of 0 to 30.
`on
`removing the trailing blanks from the formula the above measw
`ures allow for the compression of the 15 megabyte PDF into
`about 2.5 megabytes.
`‘
`Due to the slow input/output speeds of minicomputers the entire
`data base should not be searched. This constraint dictates the
`use of an inverted file with a Hsnawalt search strategy. How-
`ever, a random file structure would violate the file size con-
`straint discussed above. The solution of this dilemma is to
`
`create a pseudo-random or indexed sequential file structure.
`This type of file is inverted by sorting the patterns according
`to their d1 values and then the sorted, binary compressed
`patterns are written sequentially to a disk file.
`A single
`disk access will put the program to within 256 words of the
`
`RS 1028 - 000003
`
`
`
`HANAWALTTYPEPHASEiDENTHWCKWUNPROCEDURE
`
`A double buffered
`_pattern or dl range of patterns desired.
`assembly language subroutine performs this function with a
`negligible amount of time wasted looking at patterns outside
`the desired d1 range.
`'
`'
`Since floating point srithetic is very slow on most mini-
`computers it should be avoided. This design contraint is met
`by first converting the input d values of the unknown pattern
`into integer d-codes. The entire reverse search is then con-
`ducted using only integer arithmetic.
`Each yearly update to the PDF should be added to the search
`system with minimu effort.
`To meet this design constraint
`each of the sets of the PDF are independently inverted and
`stored. This produces 28 data files each with an associated
`d1 and PDF number directory file.
`Due to the large volume of patterns in the ?DF, and the low
`probability of most of them being'found in common unknowns, a
`Strategy which searches the most likely references first will
`greatly minimize search time. Following the work of Frevel
`(5)
`3 file containing approximately 300 of the most common phases
`in unknowns was created in exactly the same format as described
`above. This file called the MICRO file is searched first.
`Any correctly matched phases are quantitatively subtracted from
`the unknown and only the residual pattern is passed on for fur-
`ther searching. The list of 2500 phases which the JCPDS has
`designated as frequently encountered have been gathered into a
`second file called MINI. This file is searched in the second
`phase of a search.
`The full 28 set MAXI file is only searched
`if a residual pattern remains after the MICRO and MINI file
`searches have been completed.
`
`THE SEARCH ALGORITHM
`
`The hierarchical Hanawalt search proceeds as follows:
`1) The dl disk block directory of the MICRO file is read into
`memory.
`2) A binary Search procedure is used to locate the disk blocks
`containing the reference patterns whose d1.values lie within
`a 1 0.10 28 Cu error window around the d1 of the unknown.
`3) Each reference pattern in the correct d1 range must pass the
`following three tests:
`inorganic, mineral, etc.) must agree
`a. Its subfile code (e.g.
`with those specified by_the user.
`b. All diffraction lines with I3;50 must at least be present
`in the unknown.
`they must be met.
`c. If the user specified chemical constraints,
`4) For those patterns which pass the tests a figure of merit
`(FUN)
`is.computed as described in the next section.
`5) The single reference pattern with the highest POM for d1 is
`saved for the MATCH proaedure-
`6) Steps 2 through 5 are repeated for lines dz and d3.
`
`RS 1028 - 000004
`
`
`
`35
`
`-
`
`R.LSNYDEfi.
`
`7) The MATCH routine is where one or more of the'three'saved
`patterns may be quantitatively subtracted from the unknown.
`If a match was found the rescaled residual pattern with a
`new d1 value is returned and the search procedure is repeated
`starting at step 2.
`If no match is found steps 2 through 7
`are repeated with an error window of 1 0.2° 29 Cu.
`If this
`also fails to produce a match the entire procedure is repeated
`using the-next three most intense lines of the unknown (d4
`through d5) and then again for d7 through d9.
`When no (further) matches are found on searching the 9 highest
`intensity lines in the (residual) unknown pattern the MICRO
`file is abandoned.
`Steps 1 through 7 are then repeated on
`the MINI file.
`If any residual pattern remains after the MINI
`file search, steps 1 through 6 are repeated for each of the
`- 28 files in the MAXI file. After the 28 set MAXI file search
`is complete 7 is executed, and the process is repeated for
`lines d4 through d9.
`_
`The search program accepts data from either the d—I file out-
`put by the automated data reduction (ADR) program (6) or from
`manual entry.
`It rejects any K32 lines and only searches patterns
`in the user selected subfiles. Chemical constraints may be applied.
`
`THE MATCH ALGORITHM
`
`The match routine is entered to evaluate the three patterns
`found by the search. Any pattern with a figure of merit less than
`10 is rejected.
`If chemistry checking is in effect this minimu
`acceptable FOM value is lowered to 7.0.
`The acceptance of an
`incorrect pattern at this stage will so distort the residual pat-
`tern as to make any further correct matches unlikely.
`The Figure of Merit contains only three terms:
`
`FOM - dR-x IR2 x du
`
`R = percent of reference lines which match the unknown
`and which have I>I of the lowest matched line.
`
`IR-= percent of the reference intensity matched.
`
`vdu - percent of the uknown lines matched.
`The dR term does not take into account
`the closeness of the
`d agreement.
`If an unknown line falls within the rather wide
`error window of the reference line it is called a match. The
`
`goodness of fit is only considered when the windows of multiple
`lines overlap, and then only to match the correct reference and
`unknown intensities.
`Since the average 329 Cu for the 2000
`indexable
`cubic PDF patterns is 0.10 (4) and over 1000 are not
`indexable within a i 0.5° error window, any term in the FOM which
`considers goodness of fit beyond the matchfno match criterion is
`not justified.
`
`RS 1028 - 000005
`
`
`
`HANAWALT TYPE PHASE IDENTIFICATION PROCEDURE
`
`The IR term is essential to the Hanawalt-strategy. The
`entire file structure and search procedure is based on the
`assumption that the intensities are not distorted beyond recogni-
`tion; This term is given added weight by equating it. The last
`term d
`forces the search to proceed until it has located one of
`the magor phases in the unknown before any reference pattern sub-
`traction occurs. An example of this effect can be seen in sample
`7 discussed below.
`If one or more of the three patterns found in the search
`have acceptable FOM'S, the one with the highest FOM will be sub~
`tracted from the unknown first. Before subtractraction a more
`accurate intensity scale factor is computed_by performing an
`intensity weighted linear regression between the Iref and Iunk
`values.
`The scale factor obtained is used to calculate Iunk
`values from'the Iref values. All lines which calculate lower than
`observed by 5 or more units are rejected as being possibly over-
`lapped by a second phase.
`A second intensity weighted least
`squares is computed on the non—over1apped lines to obtain the
`final scale factor.
`If a second reference pattern also passes the
`acceptance tests it will also be rescaled and subtracted. The
`residual pattern, if one remains, is rescaled, resorted and passed
`‘back to the search_routine for continued searching.
`
`RESULTS
`
`We have to date, passed over one hundred experimental pat-
`terns through this search procedure. Without chemical information
`being specified the program has correctly identified every one or
`two phase unknown given it. This includes unknowns containing
`such complex phases as mullite, spodumine, pedalite ané numerous
`other low symmetry and mildly solid solution prone materials. As
`the number ofunknownphases increases to four or more the prob-
`.ability of finding an incorrect phase increases. The desirability
`of using chemical constraints increases with the number of phases
`in the unknown- The average time it takes to perform a three
`line (d1 to d3) search in each of the three steps of the hierachy
`is: MICRO file — 5 sec., MINI file - 27 sec., an@ 4.22 min.
`for
`the MAXI file.
`
`A standardized test of the algorithm can.be obtained by using
`the Jenkins and Hubbard (7)
`round robin samples. The first six
`of these patterns were synthesized while the seventh was distrib-
`uted as an experimental powder. The results for these samples are
`shown in Table 1.
`A
`
`The right side of the table shows the actual weight percents
`in each sample versus the normalized scale factors found by the
`program. when matrix absorption effects can be ignored, as in
`the artificial samples (RR lB through RR 63), the scale factors
`give the weight fraction quite accurace1y._ However,
`in most real
`specimens where matrix effects are strong, as in the experimental
`pattern (RR 73)
`there is significant disagreement.
`
`RS 1028 - 000006
`
`
`
`TABLE 1. Results of Search Procedure for the Jenkins
`and Hubbard Round Robin (RR) Samples
`I:-r
`.
`1.
`Ia
`SCM.-E FACIUR
`"
`OI5
`
`H. L. SNYDER
`
`.. H
`
`1.2
`
`.15
`
`I3)
`'
`co:
`IBJ (14.6
`2.1 (1-9)
`3 (:6)
`'I|.'I.II(Ml.n
`3-
`.30
`u.)
`.25
`(1)
`.29
`-30
`(5)
`.21
`-20
`(4)
`.2].
`
`2»
`
`an
`
`_
`
`5
`5
`
`(5)
`(5)
`
`E E0 5!.
`Casfiilflg '
`In 2810‘
`51.02
`335103
`ggrisizog
`lq';_aaS1D3'l.Zl7"¢SiG3
`Pull:
`In
`-1
`.3sc.3s)
`812- 2
`.-can‘:
`_._
`2,4-c5lI‘II,_o5
`2,5-c6n‘N.‘.o_._,‘
`C5!!!‘
`"19“aa"£'
`
`3.2(3_-1) 1s.a(11.9}
`a
`(3)
`1
`(4)
`
`32.9<36.6)
`7
`H)
`
`I
`
`(-
`(-)
`
`_
`
`5
`(5!
`35 us}
`
`-
`-
`
`E-J
`(-1
`
`1
`o
`o
`
`an
`(0)
`(0)
`
`' my
`
`6
`'3
`34.: 22.:
`
`1
`
`(1)
`
`u 3’
`- 10
`. 20
`. 12
`
`- ‘ID
`.30
`. 20
`.10
`
`no
`1
`
`(
`
`1}
`
`_
`(M2)
`(5)
`
`-
`«#0
`A
`
`(-1
`‘P
`-
`3.]. (3.1)
`3
`5
`
`*1 accrue E phase
`‘DI Mlhlrs In MMICMMI flier to I ml with fluurcauezlcl abmlstry tpcclflad.
`Th! Itwalbcri Listed for uni: phun am mg 1.433‘ P.“ in yuan “R 9”“ U" ‘ant
`
`RS 1028 - 000007
`
`
`
`HANAWALT TYPE PHASE 1DENT[FlCATlON PROCEDURE
`
`-
`
`39
`
`As shown in the table, Round Robin samples 1B, 2B and 3B,
`each containing four phases, were fully and correctly analyzed in
`about two minutes using the hierarchical search. The values
`listed in parentheses refer to the same problem run with X—ray
`fluorescence chemistry specified (i.e. all elements with Z<Si and
`specific elements with Z>Si treated as present).
`For samples 1B
`to 3B the specification of chemistry merely resulted in slightly
`faster search times. The.results are correct with or without
`
`chemistry. The same correct results are obtained if only the
`full MAXI file is searched; however,
`this increases the search
`time to about fifteen minutes.
`
`to
`
`Sample 43 is interesting because the vaterite pattern (13-192)
`used to synthesize the sample has been deleted from the PDF, due
`to significant errors in it, and replaced by 25-127. The discrep-
`ancies in the old vaterite pattern and the similarities between
`ZnC03 and CDCU3 cause the program, when run without chemistry,
`incorrectly identify the latter phase. The distortion of the
`residual pattern due to the original errors in pattern 13-192 and
`the subtraction of the incorrect COCO3 causes the program.to fail
`to find the current vaterite pattern. Hhen chemical constraints
`are applied, all correct phases are identified. However, errors
`in the original vaterite patterns leave a residual pattern which
`the program exhaustively searches, wasting some search time.
`The M35103 phase in sample SB had a systematic error intro-
`duced into the d values. The hierarchical search identifies the
`other three phases first and then fails to identify any phase
`with the initial error window of 1 .10 20.
`On automatically open-
`ing the error window to r .20 29 on the next pass, however, it
`correctly finds this phase whether or not chemistry was specified.
`- when only the MAXI file is searched two other phases similar to
`MgSi03 are found within the initial error window.
`Since only fluorescence chemistry was specified with all
`elements below Si treated as positive, the single effect on the
`organic sample RR 63 was to lower the acceptable FOM from 10 to 7.
`The hierarchical search finds two correct phases and then a false'
`phase (C5H8N). The subtraction of the incorrect phase prevents
`the identification of the remaining correct phase. The MAXI file
`Search without chemistry finds all three correct phases. However,
`the lower acceptable FOM when chemistry is specified causes two
`incorrect phases to be found along with two correct phases.
`It
`is recommended that for C, H. 0 and N-containing organics that
`chemistry not be used as a constraint.
`Sample 73 was run and analyzed using our automated diffrac-
`tion system (6). This system is adjusted to leave all small
`questionable peaks in the output file for manual deletion upon
`evaluation. However, for the case shown in the table. all false
`peaks were left on the file and it was passed without editing to
`the search program to evaluate a fully automatic analysis.
`The
`sample contained Si as an internal standard and though the search
`listed this phase in each pass it does not subtract it because
`
`RS 1028 - 000008
`
`
`
`99
`
`R.LSNYDER
`
`it only has two matching lines (3 are required for a match by
`default). The three unknown phases are correctly identified in
`this fully automated analysis whether or not chemistry or
`hierarchical searching is employed.
`
`SUMARY OF THE ROUND ROBIN ANALYSES
`
`Of the twenty six unknown phases in the round robin samples,
`at least one run of the Search program produced a completely
`correct analysis. Examining the effects of hierarchical versus
`a MAXI file only strategy and the effects of using chemistry we
`see that:
`
`hierarchical no chemistry
`hierarchical with chemistry '
`MAXI file no chemistry
`MAXI file with chemistry
`
`Correct
`Phases Found
`23
`25
`24
`24
`
`Incorrect
`Phases Found
`
`The preferred approach is clearly to do a hierarchical search
`with fluorescence chemistry as a constraint.
`The average hierar—
`chical Search time when no false peaks are present is about four
`minutes.
`For a MAXI.file search only, or when false residual
`peaks remain, forcing the program to go to a full MAXI file
`search,
`the average time rises to about 25 minutes.
`
`REFERENCES
`
`l. Frevel, L.K., "Computational Aids for Identifying Crystalline
`Phases by Powder Diffraction," Anal. Chem. 37:47l~482 (1965).
`2. Nichols, M-C.,
`"A Fortrsn II Program for the Identification of
`X—ray Powder Diffraction Patterns,” UCRL-70078, Lawrence
`Livermore Laboratory, Oct. 1966.
`3. Johnson, G.G. and Wand, V.,
`"A Computerized Powder Diffraction
`Identification Systemf'Ind. Eng, Chem. 59:19—31 (1967).
`4. Snyder, R.L., Johnson, Q.C., Kahara, E., Smith, G.S. and
`Nichols. M-C-, "An Analysis of the Powder Diffraction File,"
`UCRL-52505, Lawrence Livermore Laboratory, June 1978.
`5. Frevel, L.K., Adams, C.E. and Ruhberg, L.R.,
`"A Fast Search
`Program for Powder Diffraction Analysis," J. A921. Crgst.
`9:3oo—305 (1976).
`"
`6- Mallory, C-L. and Snyder, R.L., "The Alfred University X—ray
`Bouder Diffraction Automation System,“ N.Y.S. College of
`Ceramics Technical Paper 144 (1979).
`7. Jenkins, R. and Hubbard, C.R.,
`"A Preliminary Report on the
`Design and Results of the Second Round Robin to Evaluate
`Search/Match Methods for Quantitative Powder Diffractometry,"
`égg. X~ra3 anal. 22:l33—142 (1979).
`
`RS 1028 - 000009