SEARCH · Engineering Papers

Results for “hash algorithms”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

SourceResearch connectionFrom yearThrough year

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

11 records

All sources NASA NTRS DOE OSTI

NASA NTRS2010

Algorithm That Synthesizes Other Algorithms for Hashing

An algorithm that includes a collection of several subalgorithms has been devised as a means of synthesizing still other algorithms (which could include computer code) that utilize hashing to determine whether an element (typically, a number or other datum) is a member of a set (typically, a list of numbers). Each subalgorithm synthesizes an algorithm (e.g., a block of code) that maps a static set of key hashes to a somewhat linear monotonically increasing sequence of integers. The goal in formulating this mapping is to cause the length of the sequence thus generated to be as close as practicable to the original length of the set and thus to minimize gaps between the elements. The advantage of the approach embodied in this algorithm is that it completely avoids the traditional approach of hash-key look-ups that involve either secondary hash generation and look-up or further searching of a hash table for a desired key in the event of collisions. This algorithm guarantees that it will never be necessary to perform a search or to generate a secondary key in order to determine whether an element is a member of a set. This algorithm further guarantees that any algorithm that it synthesizes can be executed in constant time. To enforce these guarantees, the subalgorithms are formulated to employ a set of techniques, each of which works very effectively covering a certain class of hash-key values. These subalgorithms are of two types, summarized as follows: Given a list of numbers, try to find one or more solutions in which, if each number is shifted to the right by a constant number of bits and then masked with a rotating mask that isolates a set of bits, a unique number is thereby generated. In a variant of the foregoing procedure, omit the masking. Try various combinations of shifting, masking, and/or offsets until the solutions are found. From the set of solutions, select the one that provides the greatest compression for the representation and is executable in the minimum amount of time. Given a list of numbers, try to find one or more solutions in which, if each number is compressed by use of the modulo function by some value, then a unique value is generated.

James, Mark↗

NASA NTRS2010

NASA Tech Briefs, July 2010

Topics covered include: Wirelessly Interrogated Wear or Temperature Sensors; Processing Nanostructured Sensors Using Microfabrication Techniques; Optical Pointing Sensor; Radio-Frequency Tank Eigenmode Sensor for Propellant Quantity Gauging; High-Temperature Optical Sensor; Integral Battery Power Limiting Circuit for Intrinsically Safe Applications; Configurable Multi-Purpose Processor; Squeezing Alters Frequency Tuning of WGM Optical Resonator; Automated Computer Access Request System; Range Safety for an Autonomous Flight Safety System; Fast and Easy Searching of Files in Unisys 2200 Computers; Parachute Drag Model; Evolutionary Scheduler for the Deep Space Network; Modular Habitats Comprising Rigid and Inflatable Modules; More About N2O-Based Propulsion and Breathable-Gas Systems; Ultrasonic/Sonic Rotary-Hammer Drills; Miniature Piezoelectric Shaker for Distribution of Unconsolidated Samples to Instrument Cells; Lunar Soil Particle Separator; Advanced Aerobots for Scientific Exploration; Miniature Bioreactor System for Long-Term Cell Culture; Electrochemical Detection of Multiple Bioprocess Analytes; Fabrication and Modification of Nanoporous Silicon Particles; High-Altitude Hydration System; Photon Counting Using Edge-Detection Algorithm; Holographic Vortex Coronagraph; Optical Structural Health Monitoring Device; Fuel-Cell Power Source Based on Onboard Rocket Propellants; Polar Lunar Regions: Exploiting Natural and Augmented Thermal Environments; Simultaneous Spectral Temporal Adaptive Raman Spectrometer - SSTARS; Improved Speed and Functionality of a 580-GHz Imaging Radar; Bolometric Device Based on Fluxoid Quantization; Algorithms for Learning Preferences for Sets of Objects; Model for Simulating a Spiral Software-Development Process; Algorithm That Synthesizes Other Algorithms for Hashing; Algorithms for High-Speed Noninvasive Eye-Tracking System; and Adapting ASPEN for Orbital Express.

Source record↗

NASA NTRS2008

Self-Adjusting Hash Tables for Embedded Flight Applications

A common practice in computer science to associate a value with a key is to use a class of algorithms called a hash-table. These algorithms enable rapid storage and retrieval of values based upon a key. This approach assumes that many keys will need to be stored immediately. A new set of hash-table algorithms optimally uses system resources to ideally represent keys and values in memory such that the information can be stored and retrieved with a minimal amount of time and space. These hash-tables support the efficient addition of new entries. Also, for large data sets, the look-up time for large data-set searches is independent of the number of items stored, i.e., O(1), provided that the chance of collision is low.

James, Mark↗

NASA NTRS1993

Digital camera with apparatus for authentication of images produced from an image file

A digital camera equipped with a processor for authentication of images produced from an image file taken by the digital camera is provided. The digital camera processor has embedded therein a private key unique to it, and the camera housing has a public key that is so uniquely based upon the private key that digital data encrypted with the private key by the processor may be decrypted using the public key. The digital camera processor comprises means for calculating a hash of the image file using a predetermined algorithm, and second means for encrypting the image hash with the private key, thereby producing a digital signature. The image file and the digital signature are stored in suitable recording means so they will be available together. Apparatus for authenticating at any time the image file as being free of any alteration uses the public key for decrypting the digital signature, thereby deriving a secure image hash identical to the image hash produced by the digital camera and used to produce the digital signature. The apparatus calculates from the image file an image hash using the same algorithm as before. By comparing this last image hash with the secure image hash, authenticity of the image file is determined if they match, since even one bit change in the image hash will cause the image hash to be totally different from the secure hash.

Friedman, Gary L.↗

NASA NTRS1996

Digital Camera with Apparatus for Authentication of Images Produced from an Image File

A digital camera equipped with a processor for authentication of images produced from an image file taken by the digital camera is provided. The digital camera processor has embedded therein a private key unique to it, and the camera housing has a public key that is so uniquely related to the private key that digital data encrypted with the private key may be decrypted using the public key. The digital camera processor comprises means for calculating a hash of the image file using a predetermined algorithm, and second means for encrypting the image hash with the private key, thereby producing a digital signature. The image file and the digital signature are stored in suitable recording means so they will be available together. Apparatus for authenticating the image file as being free of any alteration uses the public key for decrypting the digital signature, thereby deriving a secure image hash identical to the image hash produced by the digital camera and used to produce the digital signature. The authenticating apparatus calculates from the image file an image hash using the same algorithm as before. By comparing this last image hash with the secure image hash, authenticity of the image file is determined if they match. Other techniques to address time-honored methods of deception, such as attaching false captions or inducing forced perspectives, are included.

Friedman, Gary L.↗

NASA NTRS1993

Proposed data compression schemes for the Galileo S-band contingency mission

The Galileo spacecraft is currently on its way to Jupiter and its moons. In April 1991, the high gain antenna (HGA) failed to deploy as commanded. In case the current efforts to deploy the HGA fails, communications during the Jupiter encounters will be through one of two low gain antenna (LGA) on an S-band (2.3 GHz) carrier. A lot of effort has been and will be conducted to attempt to open the HGA. Also various options for improving Galileo's telemetry downlink performance are being evaluated in the event that the HGA will not open at Jupiter arrival. Among all viable options the most promising and powerful one is to perform image and non-image data compression in software onboard the spacecraft. This involves in-flight re-programming of the existing flight software of Galileo's Command and Data Subsystem processors and Attitude and Articulation Control System (AACS) processor, which have very limited computational and memory resources. In this article we describe the proposed data compression algorithms and give their respective compression performance. The planned image compression algorithm is a 4 x 4 or an 8 x 8 multiplication-free integer cosine transform (ICT) scheme, which can be viewed as an integer approximation of the popular discrete cosine transform (DCT) scheme. The implementation complexity of the ICT schemes is much lower than the DCT-based schemes, yet the performances of the two algorithms are indistinguishable. The proposed non-image compression algorith is a Lempel-Ziv-Welch (LZW) variant, which is a lossless universal compression algorithm based on a dynamic dictionary lookup table. We developed a simple and efficient hashing function to perform the string search.

Cheung, Kar-Ming↗

NASA NTRS2008

NASA Tech Briefs, November 2008

Topics covered include: Digital Phase Meter for a Laser Heterodyne Interferometer; Vision System Measures Motions of Robot and External Objects; Advanced Precipitation Radar Antenna to Measure Rainfall From Space; Wide-Band Radar for Measuring Thickness of Sea Ice; Vertical Isolation for Photodiodes in CMOS Imagers; Wide-Band Microwave Receivers Using Photonic Processing; L-Band Transmit/Receive Module for Phase-Stable Array Antennas; Microwave Power Combiner/Switch Utilizing a Faraday Rotator; Compact Low-Loss Planar Magic-T; Using Pipelined XNOR Logic to Reduce SEU Risks in State Machines; Quasi-Optical Transmission Line for 94-GHz Radar; Next Generation Flight Controller Trainer System; Converting from DDOR SASF to APF; Converting from CVF to AAF; Documenting AUTOGEN and APGEN Model Files; Sequence History Update Tool; Extraction and Analysis of Display Data; MRO DKF Post-Processing Tool; Rig Diagnostic Tools; MRO Sequence Checking Tool; Science Activity Planner for the MER Mission; UAVSAR Flight-Planning System; Templates for Deposition of Microscopic Pointed Structures; Adjustable Membrane Mirrors Incorporating G-Elastomers; Hall-Effect Thruster Utilizing Bismuth as Propellant; High-Temperature Crystal-Growth Cartridge Tubes Made by VPS; Quench Crucibles Reinforced with Metal; Deep-Sea Hydrothermal-Vent Sampler; Mars Rocket Propulsion System; Two-Stage Passive Vibration Isolator; Improved Thermal Design of a Compression Mold; Enhanced Pseudo-Waypoint Guidance for Spacecraft Maneuvers; Altimetry Using GPS-Reflection/Occultation Interferometry; Thermally Driven Josephson Effect; Perturbation Effects on a Supercritical C7H16/N2 Mixing Layer; Gold Nanoparticle Labels Amplify Ellipsometric Signals; Phase Matching of Diverse Modes in a WGM Resonator; WGM Resonators for Terahertz-to-Optical Frequency Conversion; Determining Concentration of Nanoparticles from Ellipsometry; Microwave-to-Optical Conversion in WGM Resonators; Four-Pass Coupler for Laser-Diode-Pumped Solid-State Laser; Low-Resolution Raman-Spectroscopy Combustion Thermometry; Temperature Sensors Based on WGM Optical Resonators; Varying the Divergence of Multiple Parallel Laser Beams; Efficient Algorithm for Rectangular Spiral Search; Algorithm-Based Fault Tolerance Integrated with Replication; Targeting and Localization for Mars Rover Operations; Terrain-Adaptive Navigation Architecture; Self-Adjusting Hash Tables for Embedded Flight Applications; Schema for Spacecraft-Command Dictionary; Combined GMSK Communications and PN Ranging; System-Level Integration of Mass Memory; Network-Attached Solid-State Recorder Architecture; Method of Cross-Linking Aerogels Using a One-Pot Reaction Scheme; An Efficient Reachability Analysis Algorithm.

Source record↗

NASA NTRS1991

Massively parallel algorithms for trace-driven cache simulations

Trace driven cache simulation is central to computer design. A trace is a very long sequence of reference lines from main memory. At the t(exp th) instant, reference x sub t is hashed into a set of cache locations, the contents of which are then compared with x sub t. If at the t sup th instant x sub t is not present in the cache, then it is said to be a miss, and is loaded into the cache set, possibly forcing the replacement of some other memory line, and making x sub t present for the (t+1) sup st instant. The problem of parallel simulation of a subtrace of N references directed to a C line cache set is considered, with the aim of determining which references are misses and related statistics. A simulation method is presented for the Least Recently Used (LRU) policy, which regradless of the set size C runs in time O(log N) using N processors on the exclusive read, exclusive write (EREW) parallel model. A simpler LRU simulation algorithm is given that runs in O(C log N) time using N/log N processors. Timings are presented of the second algorithm's implementation on the MasPar MP-1, a machine with 16384 processors. A broad class of reference based line replacement policies are considered, which includes LRU as well as the Least Frequently Used and Random replacement policies. A simulation method is presented for any such policy that on any trace of length N directed to a C line set runs in the O(C log N) time with high probability using N processors on the EREW model. The algorithms are simple, have very little space overhead, and are well suited for SIMD implementation.

Nicol, David M.↗

NASA NTRS1993

A Report on Stochastic Fairness Queueing (SFQ) Experiments

SRI International (SRI) has developed an improved queueing algorithm, known as Stochastic Fairness Queueing (SFQ), for best-effort traffic (i.e., traffic that does not require any guaranteed service). SFQ is a probablistic variant of strict fair queueing where instead of a single queue being allocated per flow, a fixed number of queues are used and a hash function maps the IP source and destination to a particular queue. A seed to the hash function is also perturbed occasionally to help distribute the flows amongst different queues when more than one flow maps to the same queue during the lifetime of the flow. SFQ provides 'fair' access by trying to ensure that each flow from source to destination host obtains equal access to the available bandwidth. This report covers a series of experiments performed on DARTnet evaluating the behavior and performance of SFQ against a FIFO queueing discipline. These experiments were designed to show SFQ's advantages and performance, and include tests demonstrating: Fair utilization of available resources; Starvation prevention; Graceful degradation under overload conditions; and Resource usage. In general, the experiments do show that SFQ is better than FIFO queueing at allocating bandwidth equally among a set of flows. SFQ also prevents a stream from dominating the available bandwidth, which seems to be a tendency with FIFO queueing (i.e., if a flow demands more than its share of the available bandwidth, with FIFO queueing that stream receives a disproportionate amount when compared to flows demanding less than their share). Furthermore, SFQ seems to reward 'nice' users of the network by providing a lower variance in delay and more throughput when their resource demand is less than their available share. Both SFQ and FIFO queueing seem to degrade fairly well as the network becomes saturated and to recover well as the network becomes less congested. Not unexpectedly, FIFO queueing is a little more efficient than SFQ-the delays are less and the throughput slightly higher because SFQ requires more processing. However, the performance difference between the two queueing disciplines is relatively small. However, the experiments do point out some interesting behavior. FIFO queueing can behave better than SFQ with seed perturbation. We recommend further evaluation of the hash function and the seed perturbation technique. There are probably weaknesses in their current selection that cause this unexpected behavior. SFQ also seems to possess good scaling properties. To verify this, more experiments with a larger number of streams from more hosts need to be executed and examined, including the staggered introduction of streams. Staggering the streams may prove important, because graphs in the degradation experiment revealed some unexpected increases and decreases in throughput, which should be examined. This may again be due to the interaction of the hash function with the seed perturbation but it may also be related to some other unknown problem.

Denny, Barbara A.↗

NASA NTRS2008

A Data Type for Efficient Representation of Other Data Types

A self-organizing, monomorphic data type denoted a sequence has been conceived to address certain concerns that arise in programming parallel computers. A sequence in the present sense can be regarded abstractly as a vector, set, bag, queue, or other construct. Heretofore, in programming a parallel computer, it has been necessary for the programmer to state explicitly, at the outset, what parts of the program and the underlying data structures must be represented in parallel form. Not only is this requirement not optimal from the perspective of implementation; it entails an additional requirement that the programmer have intimate understanding of the underlying parallel structure. The present sequence data type overcomes both the implementation and parallel structure obstacles. In so doing, the sequence data type provides unified means by which the programmer can represent a data structure for natural and automatic decomposition to a parallel computing architecture. Sequences exhibit the behavioral and structural characteristics of vectors, but the underlying representations are automatically synthesized from combinations of programmers advice and execution use metrics. Sequences can vary bidirectionally between sparseness and density, making them excellent choices for many kinds of algorithms. The novelty and benefit of this behavior lies in the fact that it can relieve programmers of the details of implementations. The creation of a sequence enables decoupling of a conceptual representation from an implementation. The underlying representation of a sequence is a hybrid of representations composed of vectors, linked lists, connected blocks, and hash tables. The internal structure of a sequence can automatically change from time to time on the basis of how it is being used. Those portions of a sequence where elements have not been added or removed can be as efficient as vectors. As elements are inserted and removed in a given portion, then different methods are utilized to provide both an access and memory strategy that is optimized for that portion and the use to which it is put.

James, Mark↗

NASA NTRS1993

Investigation of aerodynamic design issues with regions of separated flow

Existing aerodynamic design methods have generally concentrated on the optimization of airfoil or wing shapes to produce a minimum drag while satisfying some basic constraints such as lift, pitching moment, or thickness. Since the minimization of drag almost always precludes the existence of separated flow, the evaluation and validation of these design methods for their robustness and accuracy when separated flow is present has not been aggressively pursued. However, two new applications for these design tools may be expected to include separated flow and the issues of aerodynamic design with this feature must be addressed. The first application of the aerodynamic design tools is the design of airfoils or wings to provide an optimal performance over a wide range of flight conditions (multipoint design). While the definition of 'optimal performance' in the multipoint setting is currently being hashed out, it is recognized that given a wide range of flight conditions, it will not be possible to ensure a minimum drag constraint at all conditions, and in fact some amount of separated flow (presumably small) may have to be allowed at the more demanding flight conditions. Thus a multipoint design method must be tolerant of the existence of separated flow and may include some controls upon its extent. The second application is in the design of wings with extended high speed buffet boundaries of their flight envelopes. Buffet occurs on a wing when regions of flow separation have grown to the extent that their time varying pressures induce possible destructive effects upon the wing structure or adversely effect either the aircraft controllability or passenger comfort. A conservative approach to the expansion of the buffet flight boundary is to simply expand the flight envelope of nonseparated flow under the assumption that buffet will also thus be alleviated. However, having the ability to design a wing with separated flow and thus to control the location, extent and severity of the separated flow regions may allow aircraft manufacturers to gain an advantage in the early design stages of an aircraft, when configuration changes are relatively inexpensive to make. The goal of the summer research at NASA Langley Research Center (LaRC) was twofold: first, to investigate a particular airfoil design problem observed under conditions of strong shock induced flow separation on the upper surface of an airfoil at transonic conditions; and second, to suggest and investigate design methodologies for the prediction (or detection) and control of flow separation. The context of both investigations was to use an existing two dimensional Navier-Stokes flow solver and the constrained direct/iterative surface curvature (CDISC) design algorithm developed at LaRC. As a lead in to the primary task, it was necessary to gain a familiarity with both the design method and the computational analysis and to perform the FORTRAN coding needed to couple them together.

Gally, Tom↗