Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “integer”

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.

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

At least 433 records · Page 24

Representing Functions in n Dimensions to Arbitrary Accuracy

A method of approximating a scalar function of n independent variables (where n is a positive integer) to arbitrary accuracy has been developed. This method is expected to be attractive for use in engineering computations in which it is necessary to link global models with local ones or in which it is necessary to interpolate noiseless tabular data that have been computed from analytic functions or numerical models in n-dimensional spaces of design parameters.

Scotti, Stephen J.↗

Ka-Band TWT High-Efficiency Power Combiner for High-Rate Data Transmission

A four-port magic-T hybrid waveguide junction serves as the central component of a high-efficiency two-way power combiner circuit for transmitting a high-rate phase-modulated digital signal at a carrier frequency in the Ka-band (between 27 and 40 GHz). This power combiner was developed to satisfy a specific requirement to efficiently combine the coherent outputs of two traveling-wavetube (TWT) amplifiers that are typically characterized by power levels on the order of 100 W or more. In this application, the use of a waveguide-based power combiner (instead of a coaxial-cable- or microstrip-based power combiner, for example) is dictated by requirements for low loss, high power-handling capability, and broadband response. Combiner efficiencies were typically 90 percent or more over both the linear and saturated output power regions of operation of the TWTs . Figure 1 depicts the basic configuration of the magic-T hybrid junction. The coherent outputs of the two TWTs enter through ports 1 and 4. As a result of the orientations of the electromagnetic fields, which also provides a needed high port-to-port isolation, of these two input signals and the interior design of the magic-T junction, the input powers are divided so as to add in phase at one output port (port 2), and to be opposite in phase and hence cancel each other at the opposite coplanar output port (port 3). The net result is that the output power at port 2 is essentially double that of the output of one TWT, minus the power lost in the magic-T hybrid junction. Optimum performance as a high-efficiency power combiner thus requires a balance of both power and phase at the input ports of the magic-T. Replicas of this two-way combiner can be arranged in a binary configuration to obtain a 2n-way (where n is an integer) combiner. For example, Figure 2 illustrates the use of three two-way combiners to combine the outputs of four TWTs.

Wintucky, Edwin G.↗

Simpler Adaptive Selection of Golomb Power-of-Two Codes

An alternative method of adaptive selection of Golomb power-of-two (GPO2) codes has been devised for use in efficient, lossless encoding of sequences of non-negative integers from discrete sources. The method is intended especially for use in compression of digital image data. This method is somewhat suboptimal, but offers the advantage in that it involves significantly less computation than does a prior method of adaptive selection of optimum codes through brute force application of all code options to every block of samples.

Kiely, Aaron↗

Error Rates and Channel Capacities in Multipulse PPM

A method of computing channel capacities and error rates in multipulse pulse-position modulation (multipulse PPM) has been developed. The method makes it possible, when designing an optical PPM communication system, to determine whether and under what conditions a given multipulse PPM scheme would be more or less advantageous, relative to other candidate modulation schemes. In conventional M-ary PPM, each symbol is transmitted in a time frame that is divided into M time slots (where M is an integer >1), defining an M-symbol alphabet. A symbol is represented by transmitting a pulse (representing 1) during one of the time slots and no pulse (representing 0 ) during the other M 1 time slots. Multipulse PPM is a generalization of PPM in which pulses are transmitted during two or more of the M time slots.

Hamkins, Jon↗

Proceedings of the Second NASA Formal Methods Symposium

This publication contains the proceedings of the Second NASA Formal Methods Symposium sponsored by the National Aeronautics and Space Administration and held in Washington D.C. April 13-15, 2010. Topics covered include: Decision Engines for Software Analysis using Satisfiability Modulo Theories Solvers; Verification and Validation of Flight-Critical Systems; Formal Methods at Intel -- An Overview; Automatic Review of Abstract State Machines by Meta Property Verification; Hardware-independent Proofs of Numerical Programs; Slice-based Formal Specification Measures -- Mapping Coupling and Cohesion Measures to Formal Z; How Formal Methods Impels Discovery: A Short History of an Air Traffic Management Project; A Machine-Checked Proof of A State-Space Construction Algorithm; Automated Assume-Guarantee Reasoning for Omega-Regular Systems and Specifications; Modeling Regular Replacement for String Constraint Solving; Using Integer Clocks to Verify the Timing-Sync Sensor Network Protocol; Can Regulatory Bodies Expect Efficient Help from Formal Methods?; Synthesis of Greedy Algorithms Using Dominance Relations; A New Method for Incremental Testing of Finite State Machines; Verification of Faulty Message Passing Systems with Continuous State Space in PVS; Phase Two Feasibility Study for Software Safety Requirements Analysis Using Model Checking; A Prototype Embedding of Bluespec System Verilog in the PVS Theorem Prover; SimCheck: An Expressive Type System for Simulink; Coverage Metrics for Requirements-Based Testing: Evaluation of Effectiveness; Software Model Checking of ARINC-653 Flight Code with MCP; Evaluation of a Guideline by Formal Modelling of Cruise Control System in Event-B; Formal Verification of Large Software Systems; Symbolic Computation of Strongly Connected Components Using Saturation; Towards the Formal Verification of a Distributed Real-Time Automotive System; Slicing AADL Specifications for Model Checking; Model Checking with Edge-valued Decision Diagrams; and Data-flow based Model Analysis.

Munoz, Cesar↗

Massively Parallel Dantzig-Wolfe Decomposition Applied to Traffic Flow Scheduling

Optimal scheduling of air traffic over the entire National Airspace System is a computationally difficult task. To speed computation, Dantzig-Wolfe decomposition is applied to a known linear integer programming approach for assigning delays to flights. The optimization model is proven to have the block-angular structure necessary for Dantzig-Wolfe decomposition. The subproblems for this decomposition are solved in parallel via independent computation threads. Experimental evidence suggests that as the number of subproblems/threads increases (and their respective sizes decrease), the solution quality, convergence, and runtime improve. A demonstration of this is provided by using one flight per subproblem, which is the finest possible decomposition. This results in thousands of subproblems and associated computation threads. This massively parallel approach is compared to one with few threads and to standard (non-decomposed) approaches in terms of solution quality and runtime. Since this method generally provides a non-integral (relaxed) solution to the original optimization problem, two heuristics are developed to generate an integral solution. Dantzig-Wolfe followed by these heuristics can provide a near-optimal (sometimes optimal) solution to the original problem hundreds of times faster than standard (non-decomposed) approaches. In addition, when massive decomposition is employed, the solution is shown to be more likely integral, which obviates the need for an integerization step. These results indicate that nationwide, real-time, high fidelity, optimal traffic flow scheduling is achievable for (at least) 3 hour planning horizons.

Rios, Joseph Lucio↗

Air Traffic Sector Configuration Change Frequency

Several techniques for partitioning airspace have been developed in the literature. The question of whether a region of airspace created by such methods can be used with other days of traffic, and the number of times a different partition is needed during the day is examined in this paper. Both these aspects are examined for the Fort Worth Center airspace sectors. A Mixed Integer Linear Programming method is used with actual air traffic data of ten high-volume low-weather-delay days for creating sectors. Nine solutions were obtained for each two-hour period of the day by partitioning the center airspace into two through 18 sectors in steps of two sectors. Actual track-data were played back with the generated partitions for creating histograms of the traffic-counts. The best partition for each two-hour period was then identified based on the nine traffic-count distributions. Numbers of sectors in such partitions were analyzed to determine the number of times a different configuration is needed during the day. One to three partitions were selected for the 24-hour period, and traffic data from ten days were played back to test if the traffic-counts stayed below the threshold values associated with these partitions. Results show that these partitions are robust and can be used for longer durations than they were designed for

Chatterji, Gano Broto↗

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↗

Definition of the Flexible Image Transport System (FITS), Version 3.0

The Flexible Image Transport System (FITS) has been used by astronomers for over 30 years as a data interchange and archiving format; FITS files are now handled by a wide range of astronomical software packages. Since the FITS format definition document (the "standard") was last printed in this journal in 2001, several new features have been developed and standardized, notably support for 64-bit integers in images and tables, variable-length arrays in tables, and new world coordinate system conventions which provide a mapping from an element in a data array to a physical coordinate on the sky or within a spectrum. The FITS Working Group of the International Astronomical Union has therefore produced this new Version 3.0 of the FITS standard, which is provided here in its entirety. In addition to describing the new features in FITS, numerous editorial changes were made to the previous version to clarify and reorganize many of the sections. Also included are some appendices which are not formally part of the standard. The FITS standard is likely to undergo further evolution, in which case the latest version may be found on the FITS Support Office Web site at http://fits.gsfc.nasa.gov/, which also provides many links to FITS-related resources.

Pence, W. D.↗

Incorporating Active Runway Crossings in Airport Departure Scheduling

A mixed integer linear program is presented for deterministically scheduling departure and ar rival aircraft at airport runways. This method addresses different schemes of managing the departure queuing area by treating it as first-in-first-out queues or as a simple par king area where any available aircraft can take-off ir respective of its relative sequence with others. In addition, this method explicitly considers separation criteria between successive aircraft and also incorporates an optional prioritization scheme using time windows. Multiple objectives pertaining to throughput and system delay are used independently. Results indicate improvement over a basic first-come-first-serve rule in both system delay and throughput. Minimizing system delay results in small deviations from optimal throughput, whereas minimizing throughput results in large deviations in system delay. Enhancements for computational efficiency are also presented in the form of reformulating certain constraints and defining additional inequalities for better bounds.

Gupta, Gautam↗

Theory and Simulation of Real and Ideal Magnetohydrodynamic Turbulence

Incompressible, homogeneous magnetohydrodynamic (MHD) turbulence consists of fluctuating vorticity and magnetic fields, which are represented in terms of their Fourier coefficients. Here, a set of five Fourier spectral transform method numerical simulations of two-dimensional (2-D) MHD turbulence on a 512(sup 2) grid is described. Each simulation is a numerically realized dynamical system consisting of Fourier modes associated with wave vectors k, with integer components, such that k = |k| less than or equal to k(sub max). The simulation set consists of one ideal (non-dissipative) case and four real (dissipative) cases. All five runs had equivalent initial conditions. The dimensions of the dynamical systems associated with these cases are the numbers of independent real and imaginary parts of the Fourier modes. The ideal simulation has a dimension of 366104, while each real simulation has a dimension of 411712. The real runs vary in magnetic Prandtl number P(sub M), with P(sub M) is a member of {0.1, 0.25, 1, 4}. In the results presented here, all runs have been taken to a simulation time of t = 25. Although ideal and real Fourier spectra are quite different at high k, they are similar at low values of k. Their low k behavior indicates the existence of broken symmetry and coherent structure in real MHD turbulence, similar to what exists in ideal MHD turbulence. The value of PM strongly affects the ratio of kinetic to magnetic energy and energy dissipation (which is mostly ohmic). The relevance of these results to 3-D Navier-Stokes and MHD turbulence is discussed.

Shebalin, John V.↗

Air Traffic Sector Configuration Change Frequency

A Mixed Integer Linear Programming method is used for creating sectors in Fort Worth, Cleveland, and Los Angeles centers based on several days of good-weather traffic data. The performance of these sectors is studied when they are subjected to traffic data from different days. Additionally, the advantage of using different sector designs at different times of day with varying traffic loads is examined. Specifically, traffic data from 10 days are used for design, and 47 other days are played back to test if the traffic-counts stay below the design values used in creating the partitions. The primary findings of this study are as follows. Sectors created with traffic from good-weather days can be used on other good-weather days. Sector configurations created with two hours of traffic can be used for 6 to 12 hours without exceeding the peak-count requirement. Compared to using a single configuration for the entire day, most of the sector-hour reduction is achieved by using two sector configurations -one during daytime hours and one during nighttime hours.

Chatterji, Gano B.↗

Optimizing Flight Departure Delay and Route Selection Under En Route Convective Weather

This paper presents a linear Integer Programming model for managing air traffic flow in the United States. The decision variables in the model are departure delays and predeparture reroutes of aircraft whose trajectories are predicted to cross weather-impacted regions of the National Airspace System. The model assigns delays to a set of flights while ensuring their trajectories are free of any conflicts with weather. In a deterministic setting, there is no airborne holding due to unexpected weather incursion in a flight s path. The model is applied to solve a large-scale traffic flow management problem with realistic weather data and flight schedules. Experimental results indicate that allowing rerouting can reduce departure delays by nearly 57%, but it is associated with an increase in total airborne time due to longer routes flown by aircraft. The computation times to solve this problem were significantly lower than those reported in the earlier studies.

Mukherjee, Avijit↗

A Simulation Based Approach to Optimize Berth Throughput Under Uncertainty at Marine Container Terminals

Berth scheduling is a critical function at marine container terminals and determining the best berth schedule depends on several factors including the type and function of the port, size of the port, location, nearby competition, and type of contractual agreement between the terminal and the carriers. In this paper we formulate the berth scheduling problem as a bi-objective mixed-integer problem with the objective to maximize customer satisfaction and reliability of the berth schedule under the assumption that vessel handling times are stochastic parameters following a discrete and known probability distribution. A combination of an exact algorithm, a Genetic Algorithms based heuristic and a simulation post-Pareto analysis is proposed as the solution approach to the resulting problem. Based on a number of experiments it is concluded that the proposed berth scheduling policy outperforms the berth scheduling policy where reliability is not considered.

Golias, Mihalis M.↗

Less-Complex Method of Classifying MPSK

An alternative to an optimal method of automated classification of signals modulated with M-ary phase-shift-keying (M-ary PSK or MPSK) has been derived. The alternative method is approximate, but it offers nearly optimal performance and entails much less complexity, which translates to much less computation time. Modulation classification is becoming increasingly important in radio-communication systems that utilize multiple data modulation schemes and include software-defined or software-controlled receivers. Such a receiver may "know" little a priori about an incoming signal but may be required to correctly classify its data rate, modulation type, and forward error-correction code before properly configuring itself to acquire and track the symbol timing, carrier frequency, and phase, and ultimately produce decoded bits. Modulation classification has long been an important component of military interception of initially unknown radio signals transmitted by adversaries. Modulation classification may also be useful for enabling cellular telephones to automatically recognize different signal types and configure themselves accordingly. The concept of modulation classification as outlined in the preceding paragraph is quite general. However, at the present early stage of development, and for the purpose of describing the present alternative method, the term "modulation classification" or simply "classification" signifies, more specifically, a distinction between M-ary and M'-ary PSK, where M and M' represent two different integer multiples of 2. Both the prior optimal method and the present alternative method require the acquisition of magnitude and phase values of a number (N) of consecutive baseband samples of the incoming signal + noise. The prior optimal method is based on a maximum- likelihood (ML) classification rule that requires a calculation of likelihood functions for the M and M' hypotheses: Each likelihood function is an integral, over a full cycle of carrier phase, of a complicated sum of functions of the baseband sample values, the carrier phase, the carrier-signal and noise magnitudes, and M or M'. Then the likelihood ratio, defined as the ratio between the likelihood functions, is computed, leading to the choice of whichever hypothesis - M or M'- is more likely. In the alternative method, the integral in each likelihood function is approximated by a sum over values of the integrand sampled at a number, 1, of equally spaced values of carrier phase. Used in this way, 1 is a parameter that can be adjusted to trade computational complexity against the probability of misclassification. In the limit as 1 approaches infinity, one obtains the integral form of the likelihood function and thus recovers the ML classification. The present approximate method has been tested in comparison with the ML method by means of computational simulations. The results of the simulations have shown that the performance (as quantified by probability of misclassification) of the approximate method is nearly indistinguishable from that of the ML method (see figure).

Hamkins, Jon↗

Generating a 2D Representation of a Complex Data Structure

A computer program, designed to assist in the development and debugging of other software, generates a two-dimensional (2D) representation of a possibly complex n-dimensional (where n is an integer >2) data structure or abstract rank-n object in that other software. The nature of the 2D representation is such that it can be displayed on a non-graphical output device and distributed by non-graphical means.

James, Mark↗

Domain Compilation for Embedded Real-Time Planning

A recently conceived approach to automated real-time control of the actions of a robotic system enables an embedded real-time planning algorithm to develop plans that are more robust than they would otherwise be, without imposing an excessive computational burden. This approach occupies a middle ground between two prior approaches known in the art as the universal-plan and hybrid approaches. Ever since discovering the performance limitations of taking a sense-plan-act approach to controlling robots, the robotics community has endeavored to follow a behavior-based approach in which a behavior includes a rapid feedback loop between state estimation and motor control. Heretofore, system architectures following this approach have been based, variously, on algorithms that implement universal plans or algorithms that function as hybrids of planners and executives. In a typical universal-plan case, a set of behaviors is merged into the plan, but the system must be restricted to relatively small problem domains to avoid having to reason about too many states and represent them in the plan. In the hybrid approach, one implements actions as small sets of behaviors, each applicable to a limited set of circumstances. Each action is intended to bring the system to a subgoal state. A planning algorithm is used to string these actions together into a sequence to traverse the state space from an initial or current state to a goal state. The hybrid approach works well in a static environment, but it is inherently brittle in a dynamic environment because a failure can occur when the environment strays beyond the region of applicability of the current activity. In the present approach, a system can vary from the hybrid approach to the universal-plan approach, depending on a single integer parameter, denoted n, which can range from 1 to a maximum domain-dependent value of M. As illustrated in the figure, n = 1 represents the hybrid approach, in which each linked action covers a small part of the state space of the system. As n increases, the portion of state space associated with each action and its subgoal grows. When n reaches M, coverage extends over the full state space, so that the system contains a universal plan.

Barrett, Anthony↗

Faster Evolution of More Multifunctional Logic Circuits

A modification in a method of automated evolutionary synthesis of voltage-controlled multifunctional logic circuits makes it possible to synthesize more circuits in less time. Prior to the modification, the computations for synthesizing a four-function logic circuit by this method took about 10 hours. Using the method as modified, it is possible to synthesize a six-function circuit in less than half an hour. The concepts of automated evolutionary synthesis and voltage-controlled multifunctional logic circuits were described in a number of prior NASA Tech Briefs articles. To recapitulate: A circuit is designed to perform one of several different logic functions, depending on the value of an applied control voltage. The circuit design is synthesized following an automated evolutionary approach that is so named because it is modeled partly after the repetitive trial-and-error process of biological evolution. In this process, random populations of integer strings that encode electronic circuits play a role analogous to that of chromosomes. An evolved circuit is tested by computational simulation (prior to testing in real hardware to verify a final design). Then, in a fitness-evaluation step, responses of the circuit are compared with specifications of target responses and circuits are ranked according to how close they come to satisfying specifications. The results of the evaluation provide guidance for refining designs through further iteration.

Stoica, Adrian↗