josh@polaris.UUCP (Josh Knight) (09/03/86)
*** REPLACE THIS LINE WITH YOUR MESSAGE *** %A Malcolm C. Easton %T Key-Sequence Data Sets on Indelible Storage %J IBM J R&D %V 30 %N 3 %P 230-241 %D 1986 MAY %X Methods for creating and maintaining key-sequence data sets without overwriting the storage medium are described. These methods may be applied to erasable or to write-once storage devices, and they are compatible with conventional device error-management techniques. All past values of data records are preserved in a data structure called a Write-Once B-Tree. Rapid random access is available to records by key value; rapid sequential access is available to records in key-sequence order. Moreover, queries requesting data as of a previous time are processed as rapidly as requests for current data. Access time is proportional to the logarithm of the number of current records in the data base. Efficient methods for inserting, updating, and deleting records are described. Upper bounds for tree depth and for storage consumption are given and compared with results from simulation. It is concluded that, with rapidly improving storage technologies, indelible databases will become practical for many applications. %A Harold S. Stone %A Paolo Sipala %T The Average Complexity of Depth-First Search with Backtracking and Cutoff %J IBM J R&D %V 30 %N 3 %P 242-258 %D 1986 MAY %X This paper analyzes two algorithms for depth-first search of binary trees. The first algorithm uses a search strategy that terminates the search when a successful leaf is reached. The algorithm does not use internal cutoff to restrict the search space. If N is the depth of the tree, then the average number of nodes visited by the algorithm is as low as O(N) and as high as O(2**N) depending only on the value of the probability parameter that characterizes the search. The second search algorithm uses backtracking with cutoff. A decision to cut off the search at a node eliminates the entire subtree below that node from further consideration. The surprising result for this algorithm is that the average number of nodes visited grows linearly in the depth of the of the tree, regardless of the cutoff probability. If the cutoff probability is high, then the search has a high probability of failing without examining much of the tree. If the cutoff probability is low, then the search has a high probability of succeeding on the leftmost path of the tree without performing extensive backtracking. This model sheds light on why some instances of NP-complete problems are solvable in practice with a low average complexity. %A Arvind M. Patel %T On-the-fly Decoder for Multiple Byte Errors %J IBM J R&D %V 30 %N 3 %P 259-269 %D 1986 MAY %X Multiple-error-correcting Reed-Solomon or BCH codes in GF(2**b) can be used for correction of multiple burst errors in binary data. However, the relatively long time required for decoding multiple errors has been among the main objections to applying these schemes to high-performance computer products. In this paper, a decoding procedure is developed for on-the-fly correction of multiple symbol (byte) errors in Reed-Solomon or BCH codes. A new decoder architecture expands the concept of Chien search of error locations into computation of error values as well, and creates a synchronous procedure for complete on-the-fly error correction of multiple byte errors. Forney's expression for error values is further simplified, which results in substantial economies in hardware and decoding time. All division operations are eliminated from the computation of the error-locator equation, and only one division operation is required in the computation of error values. The special cases of fewer errors are processed automatically, using the corresponding smaller set of syndromes through a single set of hardware. The resultant decoder implementation is well suited for LSI chip design with pipelined data flow. The implementation is illustrated with an example. %A D.M. Cannon %A W.R. Dempwolf %A J.M. Schmalhorst %A F.B. Shelledy %A R.D. Silkensen %T Design and Performance of a Magnetic Head for a High-Density Tape Drive %J IBM J R&D %V 30 %N 3 %P 270-277 %D 1986 MAY %X The design of a magnetic head for use in the tape drive portion of the IBM 3480 Magnetic Tape Subsystem required that advances be made in track density and linear recording density while meeting requirements for signal quality, manufacturability, and reliability. The design that was developed to fulfill these needs combines ferrite pole-pieces, magnetoresistive read elements, and planar-deposited write turns. This paper describes the read and write elements of the head and the approach used in the selection of the design parameters. %A Lindsay A. Prisgrove %A Gerald S. Shedler %T Symmetric Stocastic Petri Nets %J IBM J R&D %V 30 %N 3 %P 278-293 %D 1986 MAY %X The stocastic Petri net (SPN) model is well suited to formal representation of concurrency, synchronization, and communication. In the paper we focus on discrete event simulation methods for SPN models with special structure and define a symmetric SPN. Exploiting properties of a symmetric SPN and underlying regenerative process structure, we establish steady state estimation procedures based on the marking process. We also establish estimation procedures for passage times in the symmetric SPN setting. These results lead to efficient estimation procedures for delay/throughput characteristics of ring networks with identical ports. %A Bijan Arbab %T Compiling Circular Attribute Grammars into Prolog %J IBM J R&D %V 30 %N 3 %P 294-309 %D 1986 MAY %X This paper describes an algorithm for compiling attribute grammars into Prolog. The attribute grammars may include inherited and synthesized attributes and contain recursive (circular) definitions. The semantics of the recursive definitions is defined in terms of a fixed-point finding function. The generated Prolog code stands in direct relation to its attribute grammar, where logical variables play the role of synthesized or inherited attributes. Thus an effective method for the execution of recursive attribute grammars has been defined and applied. %A J.M. Cioffi %T Least-Squares Storage-Channel Identification %J IBM J R&D %V 30 %N 3 %P 310-320 %D 1986 MAY %X Pulse (dibit) and step (transition) responses for magnetic-storage channels are important for detection-circuity design and for comparison of various media, heads, and other channel components. This presents a least-squares procedure that can be used to identify the dibit and transition responses from measurements of the read-head response to any known data sequence written on the medium. The method yields significantly higher-quality estimates for the dibit and step shapes than does determining these same characteristics by measuring the average response to isolated transition or by performing a Discrete Fourier Transform (DFT) on the response to a pseudorandom data pattern. The new method can be implemented off line but also can be made sufficiently efficient to be implemented with a microprocessor for use in self-optimizing (adaptive) channel detection circuitry. %A Lineu C. Barbosa %T A Maximum-Energy-Concentration Spectral Window %J IBM J R&D %V 30 %N 3 %P 321-325 %D 1986 MAY %X A time-discrete solution method is proposed for realization of a spectral window which is ideal from an energy concentration viewpoint. This window is one that concentrates the maximum amount energy in a specified bandwidth and hence provides optimal spectral resolution. %A C.H. Stapper %T On Yield, Fault Distributions, and Clustering of Particles %J IBM J R&D %V 30 %N 3 %P 326-338 %D 1986 MAY %X Increasing the levels of semiconductor integration to larger chips with more transistors causes the fault and defect distributions of VLSI memory chips to deviate increasingly further from simple random Poisson statistics. The spatial distributions of particles on semiconductor wafers have been analyzed to gain insight into the nature of integrated circuit defect statistics. The analysis was done using grids of squares known as quadrats. It was found that the cluster parameter, which until now has been treated as a constant, did vary with quadrat area. The results also show that the deviation from Poisson statistics continues to increase into the realm of wafer-scale integration or WSI. Computer simulations were used to verify this effect. -- Josh Knight, IBM T.J. Watson Research josh@ibm.com, josh@yktvmh.bitnet, ...!philabs!polaris!josh