Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Encoding”

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 577 records · Page 32
All sourcesNASA NTRSDOE OSTI
DOE OSTI2021

Revisiting Huffman Coding: Toward Extreme Performance on Modern GPU Architectures

Today's high-performance computing (HPC) applications are producing vast volumes of data, which are challenging to store and transfer efficiently during the execution, such that data compression is becoming a critical technique to mitigate the storage burden and data movement cost. Huffman coding is arguably the most efficient Entropy coding algorithm in information theory, such that it could be found as a fundamental step in many modern compression algorithms such as DEFLATE. On the other hand, today's HPC applications are more and more relying on the accelerators such as GPU on supercomputers, while Huffman encoding suffers from low throughput on GPUs, resulting in a significant bottleneck in the entire data processing. In this paper, we propose and implement an efficient Huffman encoding approach based on modern GPU architectures, which addresses two key challenges: (1) how to parallelize the entire Huffman encoding algorithm, including codebook construction, and (2) how to fully utilize the high memory-bandwidth feature of modern GPU architectures. The detailed contribution is fourfold. (1) We develop an efficient parallel codebook construction on GPUs that scales effectively with the number of input symbols. (2) We propose a novel reduction based encoding scheme that can efficiently merge the codewords on GPUs. (3) We optimize the overall GPU performance by leveraging the state-of-the-art CUDA APIs such as Cooperative Groups. (4) We evaluate our Huffman encoder thoroughly using six real-world application datasets on two advanced GPUs and compare with our implemented multithreaded Huffman encoder. Experiments show that our solution can improve the encoding throughput by up to 5.0× and 6.8× on NVIDIA RTX 5000 and V100, respectively, over the state-of-the-art GPU Huffman encoder, and by up to 3.3× over the multithread encoder on two 28-core Xeon Platinum 8280 CPUs.

Tian, Jiannan↗
DOE OSTI2021

Lightweight LSTM for CAN Signal Decoding

This paper describes an approach to identify undecoded Controller Area Network (CAN) data from one vehicle, based on the data similarity to previously decoded CAN data from another vehicle. Modern vehicles communicate data and signals from on-board sensors and controllers through the CAN bus. Networked sensors contain information such as wheel speeds, fuel gauges, turn signals, and radar signals. In the effort to use this information and make cars safer through human-in-the-loop CPS, signals on the CAN bus such as wheel speed and radar can be used to support the driver. However, data from the CAN bus are encoded and in some cases compressed, and different car manufacturers use different encoding schemes to represent data on the CAN bus. With hundreds of messages and thousands of possible encoding schemes to consider, it is laborious to identify the unique bits and encoding schemes that represent signals on each vehicle. In this study, we propose a method for training a Long Short-Term Memory (LSTM) neural network on known radar signals from one vehicle manufacturer, a Toyota, and successfully apply the network to identify the encoding for radar signals on a different vehicle, a Honda. By augmenting the training dataset with varied encoding bit boundaries, a small and lightweight LSTM network can learn to recognize radar data across different encoding schemes. The results are an improvement on exhaustive-search algorithms and other methods previously used in the search for such signals.

Ngo, Paul↗
NASA NTRS1984

Comparison of voice types for helicopter voice warning systems

Three related studies were conducted to compare different types of human voice warnings. In the first study, a comparison of three LPC-encoded voices, human female, human male, and phoneme-synthesized, by the criteria of pilot flight task performance showed no differences due to the voice type. In the second study, pilots' preferences were investigated, by comparing preference for direct synthesized speech to the LPC-encoded human female speech and to LPC-encoded synthesized speech. Most pilots were found to prefer direct synthesized speech over both LPC-encoded human female speech and the LPC-encoded synthesized speech. In the third study, phonetically balanced (PB) words heard in simulated helicopter noise were used to compare the intelligibility of direct synthesized and LPC-encoded phoneme-synthesized speech types. PB word intelligibility was found to be better for direct synthesized speech than for the LPC-encodes synthesized speech.

Simpson, C. A.↗
NASA NTRS2008

Fault-Tolerant Coding for State Machines

Two reliable fault-tolerant coding schemes have been proposed for state machines that are used in field-programmable gate arrays and application-specific integrated circuits to implement sequential logic functions. The schemes apply to strings of bits in state registers, which are typically implemented in practice as assemblies of flip-flop circuits. If a single-event upset (SEU, a radiation-induced change in the bit in one flip-flop) occurs in a state register, the state machine that contains the register could go into an erroneous state or could hang, by which is meant that the machine could remain in undefined states indefinitely. The proposed fault-tolerant coding schemes are intended to prevent the state machine from going into an erroneous or hang state when an SEU occurs. To ensure reliability of the state machine, the coding scheme for bits in the state register must satisfy the following criteria: 1. All possible states are defined. 2. An SEU brings the state machine to a known state. 3. There is no possibility of a hang state. 4. No false state is entered. 5. An SEU exerts no effect on the state machine. Fault-tolerant coding schemes that have been commonly used include binary encoding and "one-hot" encoding. Binary encoding is the simplest state machine encoding and satisfies criteria 1 through 3 if all possible states are defined. Binary encoding is a binary count of the state machine number in sequence; the table represents an eight-state example. In one-hot encoding, N bits are used to represent N states: All except one of the bits in a string are 0, and the position of the 1 in the string represents the state. With proper circuit design, one-hot encoding can satisfy criteria 1 through 4. Unfortunately, the requirement to use N bits to represent N states makes one-hot coding inefficient.

Naegle, Stephanie Taft↗
NASA NTRS2011

Method and System for Temporal Filtering in Video Compression Systems

Three related innovations combine improved non-linear motion estimation, video coding, and video compression. The first system comprises a method in which side information is generated using an adaptive, non-linear motion model. This method enables extrapolating and interpolating a visual signal, including determining the first motion vector between the first pixel position in a first image to a second pixel position in a second image; determining a second motion vector between the second pixel position in the second image and a third pixel position in a third image; determining a third motion vector between the first pixel position in the first image and the second pixel position in the second image, the second pixel position in the second image, and the third pixel position in the third image using a non-linear model; and determining a position of the fourth pixel in a fourth image based upon the third motion vector. For the video compression element, the video encoder has low computational complexity and high compression efficiency. The disclosed system comprises a video encoder and a decoder. The encoder converts the source frame into a space-frequency representation, estimates the conditional statistics of at least one vector of space-frequency coefficients with similar frequencies, and is conditioned on previously encoded data. It estimates an encoding rate based on the conditional statistics and applies a Slepian-Wolf code with the computed encoding rate. The method for decoding includes generating a side-information vector of frequency coefficients based on previously decoded source data and encoder statistics and previous reconstructions of the source frequency vector. It also performs Slepian-Wolf decoding of a source frequency vector based on the generated side-information and the Slepian-Wolf code bits. The video coding element includes receiving a first reference frame having a first pixel value at a first pixel position, a second reference frame having a second pixel value at a second pixel position, and a third reference frame having a third pixel value at a third pixel position. It determines a first motion vector between the first pixel position and the second pixel position, a second motion vector between the second pixel position and the third pixel position, and a fourth pixel value for a fourth frame based upon a linear or nonlinear combination of the first pixel value, the second pixel value, and the third pixel value. A stationary filtering process determines the estimated pixel values. The parameters of the filter may be predetermined constants.

Lu, Ligang↗
NASA NTRS2013

Bilayer Protograph Codes for Half-Duplex Relay Channels

Direct to Earth return links are limited by the size and power of lander devices. A standard alternative is provided by a two-hops return link: a proximity link (from lander to orbiter relay) and a deep-space link (from orbiter relay to Earth). Although direct to Earth return links are limited by the size and power of lander devices, using an additional link and a proposed coding for relay channels, one can obtain a more reliable signal. Although significant progress has been made in the relay coding problem, existing codes must be painstakingly optimized to match to a single set of channel conditions, many of them do not offer easy encoding, and most of them do not have structured design. A high-performing LDPC (low-density parity-check) code for the relay channel addresses simultaneously two important issues: a code structure that allows low encoding complexity, and a flexible rate-compatible code that allows matching to various channel conditions. Most of the previous high-performance LDPC codes for the relay channel are tightly optimized for a given channel quality, and are not easily adapted without extensive re-optimization for various channel conditions. This code for the relay channel combines structured design and easy encoding with rate compatibility to allow adaptation to the three links involved in the relay channel, and furthermore offers very good performance. The proposed code is constructed by synthesizing a bilayer structure with a pro to graph. In addition to the contribution to relay encoding, an improved family of protograph codes was produced for the point-to-point AWGN (additive white Gaussian noise) channel whose high-rate members enjoy thresholds that are within 0.07 dB of capacity. These LDPC relay codes address three important issues in an integrative manner: low encoding complexity, modular structure allowing for easy design, and rate compatibility so that the code can be easily matched to a variety of channel conditions without extensive re-optimization. The main problem of half-duplex relay coding can be reduced to the simultaneous design of two codes at two rates and two SNRs (signal-to-noise ratios), such that one is a subset of the other. This problem can be addressed by forceful optimization, but a clever method of addressing this problem is via the bilayer lengthened (BL) LDPC structure. This method uses a bilayer Tanner graph to make the two codes while using a concept of "parity forwarding" with subsequent successive decoding that removes the need to directly address the issue of uneven SNRs among the symbols of a given codeword. This method is attractive in that it addresses some of the main issues in the design of relay codes, but it does not by itself give rise to highly structured codes with simple encoding, nor does it give rate-compatible codes. The main contribution of this work is to construct a class of codes that simultaneously possess a bilayer parity- forwarding mechanism, while also benefiting from the properties of protograph codes having an easy encoding, a modular design, and being a rate-compatible code.

Divsalar, Dariush↗
DOE OSTI2025

Author Correction: Genome-guided isolation of the hyperthermophilic aerobe Fervidibacter sacchari reveals conserved polysaccharide metabolism in the Armatimonadota

Correction to: Nature Communicationshttps://doi.org/10.1038/s41467-024-53784-3, published online 4 November 2024 In the version of this article initially published, Table 1 did not include the properties of the taxa being proposed or refer directly to another location in the main manuscript describing the properties. As such, the original manuscript did not comply with Rule 27 (2)(c) of the ICNP. Also, Table 1 listed the order Fervidibacterales as the nomenclatural type for the class Fervidibacteria, which violates latest emended version of Rule 15 stating that the nomenclatural type for a class must be a genus. Below we provide a modification of Table 1 containing protologues with these errors corrected. We have also changed the order of the taxa in the table to meet the most common ordering. (Table presented.) Taxon names proposed under the ICNP Proposed taxon Etymology Description Genus Fervidibacter Fer.vi.di.bac’ter. L. masc. adj. fervidus, hot, steaming; N.L. masc. n. bacter, a rod; N.L. masc. n. Fervidibacter, a hot rod Thermophilic or hyperthermophilic inhabitants of freshwater thermal environments. All members are likely polysaccharide-degrading chemoheterotrophs with numerous carbohydrate-active enzymes encoded in their genomes. Aerobic, with high-affinity and/or low-affinity terminal oxidases present in the genomes. The oxidative pentose phosphate pathway and the tricarboxylic acid cycle are complete in genomes belonging to the genus. Gram-stain-negative and diderm cell envelope structure. Ovoid- to rod-shaped morphology. Spores are not formed. The genus is a distinct phylogenetic lineage in the family Fervidibacteraceae, the order Fervidibacterales, and the class Fervidibacteria in the phylum Armatimonadota. The type species is Fervidibacter sacchariT. Species Fervidibacter sacchari sac’cha.ri. N.L. gen. n. sacchari, of sugar Hyperthermophilic, microaerophilic, facultatively anaerobic, and grows chemoheterotrophically on monosaccharides and polysaccharides. Cells are ovoid- to rod-shaped, Gram-stain negative, and are 0.9–1.3 µm in width and 1.6–3.6 µm in length. Grows between 65 and 87.5 °C and an optimum temperature of 80 °C, and a pH range of 6.5–8.6 with an optimum pH of 7.5. Grows at an optimum O2 concentration of 5–10%. Grows on D-arabinose, D-galactose, D-glucose, D-rhamnose, D-ribose, D-xylose, chondroitin sulfate, colloidal chitin, galactan, gellan gum, guar gum, karaya gum, locust bean gum, xantham gum, xyloglucan, β-glucan, glycogen, starch, AFEX-pretreated corn stover, miscanthus, sugarcane bagasse, acetate and casamino acids. Grows weakly on xyloglucan under fermentation conditions. The major fatty acids (>10%) are C16:0, C18:0 and/or cyclo-C17:0, and iso-C16:0. The major respiratory quinones (>10%) are MK-8 and MK-9. The isolate and genomes of the species have been recovered from geothermal springs in the Great Basin, Nevada, USA. GC content of genomes range between 51–52%. Subunits for both the high-affinity and low-affinity terminal oxidases are encoded in the genomes. Genomes also encode a Group 3d [NiFe] hydrogenase, which produces hydrogen as an electron sink for NAD+ regeneration. The type strain PD1T (= JCM 39283T = DSM 113467T) was isolated from Great Boiling Spring in Nevada, USA. Family Fervidibacteraceae Fer.vi.di.bac.te.ra’ce.ae. N.L. masc. n. Fervidibacter type genus of the family; L. suff. -aceae ending to denote a family; N.L. fem. pl. n. Fervidibacteraceae the family of the genus Fervidibacter Thermophilic or hyperthermophilic inhabitants of freshwater thermal environments. All members are likely polysaccharide-degrading chemoheterotrophs with numerous carbohydrate-active enzymes encoded in their genomes. Aerobic, with high-affinity and/or low-affinity terminal oxidases present in the genomes. The oxidative pentose phosphate pathway and the tricarboxylic acid cycle are complete in genomes belonging to the family. The family is a distinct phylogenetic lineage in the order Fervidibacterales and the class Fervidibacteria in the phylum Armatimonadota. The type genus is Fervidibacter. Order Fervidibacterales Fer.vi.di.bac.te.ra’les. N.L. masc. n. Fervidibacter type genus of the order; L. suff. -ales ending to denote an order; N.L. fem. pl. n. Fervidibacterales the order of the genus Fervidibacter Thermophilic or hyperthermophilic inhabitants of freshwater thermal environments. All members are likely polysaccharide-degrading chemoheterotrophs with numerous carbohydrate-active enzymes encoded in their genomes. Aerobic or strictly anaerobic. Phylogenomic placement of this lineage within the Fervidibacteria and relative evolutionary divergence supports delineation of this lineage as an order within the class Fervidibacteria and phylum Armatimonadota. The type genus is Fervidibacter. Class Fervidibacteria Fer.vi.di.bac.te’ri.a. N.L. masc. n. Fervidibacter type genus of the type order of the class; L. suff. -ia ending to denote a class; N.L. neut. pl. n. Fervidibacteria the class of the order Fervidibacterales Thermophilic or hyperthermophilic inhabitants of freshwater thermal environments. All members are likely polysaccharide-degrading chemoheterotrophs with numerous carbohydrate-active enzymes encoded in their genomes. Aerobic or strictly anaerobic. Phylogenomic placement of this lineage within the Armatimonadota and relative evolutionary divergence supports delineation of this lineage as a class within the Armatimonadota. The type genus is Fervidibacter. The error has not been corrected in the PDF or HTML versions of the Article.

Nou, Nancy O↗
DOE OSTI2025

Noisy quantum trees: infinite protection without correction

We study quantum networks with tree structures, in which information propagates from a root to leaves. At each node in the network, the received qubit unitarily interacts with fresh ancilla qubits, after which each qubit is sent through a noisy channel to a different node in the next level. Therefore, as the tree depth grows, there is a competition between the irreversible effect of noise and the protection against such noise achieved by the delocalization of information. In the classical setting, where each node simply copies the input bit into multiple output bits, this model has been studied as the broadcasting or reconstruction problem on trees, which has broad applications. In this work, we study the quantum version of this problem. We consider a Clifford encoder at each node that encodes the input qubit in a stabilizer code, along with a single qubit Pauli noise channel at each edge. Such noisy quantum trees describe a scenario in which one has access to a stream of fresh (low-entropy) ancilla qubits, but cannot perform error correction. Therefore, they provide a different perspective on quantum fault tolerance. Furthermore, they provide a useful model for describing the effect of noise within the encoders of concatenated codes. We prove that above certain noise thresholds, which depend on the properties of the code such as its distance, as well as the properties of the encoder, information decays exponentially with the depth of the tree. On the other hand, by studying certain efficient decoders, we prove that for codes with distance d ≥ 2 and for sufficiently small (but non-zero) noise, classical information and entanglement propagate over a noisy tree with infinite depth. Indeed, we find that this remains true even for binary trees with certain 2-qubit encoders at each node, which encodes the received qubit in the binary repetition code with distance d = 1.

Quantum information↗
DOE OSTI2021

The tortoise and the hare: a causality puzzle in AdS/CFT

Here, we pose and resolve a holographic puzzle regarding an apparent violation of causality in anti-de Sitter (AdS)/conformal field theory. If a point in the bulk of AdS moves at the speed of light, the boundary subregion that encodes it may need to move superluminally to keep up. With AdS 3 as our main example, we prove that the finite extent of the encoding regions prevents a paradox. We show that the length of the minimal-size encoding interval gives rise to a tortoise coordinate on AdS that measures the nonlocality of the encoding. We use this coordinate to explore circular and radial motion in the bulk before passing to the analysis of bulk null geodesics. For these null geodesics, there is always a critical encoding where the possible violation of causality is barely avoided. We show that in any other encoding, the possible violation is subcritical.

72 PHYSICS OF ELEMENTARY PARTICLES AND FIELDS↗
DOE OSTI2024

Mo than meets the eye: genomic insights into molybdoenzyme diversity of Seleniivibrio woodruffii strain S4T

Abstract Seleniivibrio woodruffii strain S4T is an obligate anaerobe belonging to the phylum Deferribacterota. It was isolated for its ability to respire selenate and was also found to respire arsenate. The high-quality draft genome of this bacterium is 2.9 Mbp, has a G+C content of 48%, 2762 predicted genes of which 2709 are protein-coding, and 53 RNA genes. An analysis of the genome focusing on the genes encoding for molybdenum-containing enzymes (molybdoenzymes) uncovered a remarkable number of genes encoding for members of the dimethylsulfoxide reductase family of proteins (DMSOR), including putative reductases for selenate and arsenate respiration, as well as genes for nitrogen fixation. Respiratory molybdoenzymes catalyze redox reactions that transfer electrons to a variety of substrates that can act as terminal electron acceptors for energy generation. Seleniivibrio woodruffii strain S4T also has essential genes for molybdate transporters and the biosynthesis of the molybdopterin guanine dinucleotide cofactors characteristic of the active centers of DMSORs. Phylogenetic analysis revealed candidate respiratory DMSORs spanning nine subfamilies encoded within the genome. Our analysis revealed the untapped potential of this interesting microorganism and expanded our knowledge of molybdoenzyme co-occurrence.

Louie, Tiffany S.↗
DOE OSTI2023

The State of the Art in Visualizing Dynamic Multivariate Networks

Abstract Most real‐world networks are both dynamic and multivariate in nature, meaning that the network is associated with various attributes and both the network structure and attributes evolve over time. Visualizing dynamic multivariate networks is of great significance to the visualization community because of their wide applications across multiple domains. However, it remains challenging because the techniques should focus on representing the network structure, attributes and their evolution concurrently. Many real‐world network analysis tasks require the concurrent usage of the three aspects of the dynamic multivariate networks. In this paper, we analyze current techniques and present a taxonomy to classify the existing visualization techniques based on three aspects: temporal encoding, topology encoding, and attribute encoding. Finally, we survey application areas and evaluation methods; and discuss challenges for future research.

Kale, Bharat↗
NASA NTRS1989

A recursive technique for adaptive vector quantization

Vector Quantization (VQ) is fast becoming an accepted, if not preferred method for image compression. The VQ performs well when compressing all types of imagery including Video, Electro-Optical (EO), Infrared (IR), Synthetic Aperture Radar (SAR), Multi-Spectral (MS), and digital map data. The only requirement is to change the codebook to switch the compressor from one image sensor to another. There are several approaches for designing codebooks for a vector quantizer. Adaptive Vector Quantization is a procedure that simultaneously designs codebooks as the data is being encoded or quantized. This is done by computing the centroid as a recursive moving average where the centroids move after every vector is encoded. When computing the centroid of a fixed set of vectors the resultant centroid is identical to the previous centroid calculation. This method of centroid calculation can be easily combined with VQ encoding techniques. The defined quantizer changes after every encoded vector by recursively updating the centroid of minimum distance which is the selected by the encoder. Since the quantizer is changing definition or states after every encoded vector, the decoder must now receive updates to the codebook. This is done as side information by multiplexing bits into the compressed source data.

Lindsay, Robert A.↗
NASA NTRS1989

Noiseless compression using non-Markov models

Adaptive data compression techniques can be viewed as consisting of a model specified by a database common to the encoder and decoder, an encoding rule and a rule for updating the model to ensure that the encoder and decoder always agree on the interpretation of the next transmission. The techniques which fit this framework range from run-length coding, to adaptive Huffman and arithmetic coding, to the string-matching techniques of Lempel and Ziv. The compression obtained by arithmetic coding is dependent on the generality of the source model. For many sources, an independent-letter model is clearly insufficient. Unfortunately, a straightforward implementation of a Markov model requires an amount of space exponential in the number of letters remembered. The Directed Acyclic Word Graph (DAWG) can be constructed in time and space proportional to the text encoded, and can be used to estimate the probabilities required for arithmetic coding based on an amount of memory which varies naturally depending on the encoded text. The tail of that portion of the text which was encoded is the longest suffix that has occurred previously. The frequencies of letters following these previous occurrences can be used to estimate the probability distribution of the next letter. Experimental results indicate that compression is often far better than that obtained using independent-letter models, and sometimes also significantly better than other non-independent techniques.

Blumer, Anselm↗
NASA NTRS1993

Determining the locations of the various CIRC recording format information blocks (user data blocks, C2 and C1 words and EFM frames) on a recorded compact disc

Just prior to its being EFM modulated (i.e., converted to eight-to-fourteen channel data by the EFM encoder) and written to a Compact Disc (CD), information that passes through the CIRC Block Encoder is grouped into 33-byte blocks referred to as EFM frames. Twenty four of the bytes that make up a given EFM frame are user data that was input into the CIRC encoder at various (different) times, 4 of the bytes of this same EFM frame were created by the C2 ECC encoder (each at a different time), and another 4 were created by the C1 ECC encoder (again, each at a different time). The one remaining byte of the given EFM frame, which is known as the EFM frame C&D (for Control & Display) byte, carries information that identifies which portion of the current disc program track the given EFM frame belongs to and also specifies the location of the given EFM frame on the disc (in terms of a time stamp that has a resolution of l/75th second, or 98 EFM frames). (Note: since the program track and time information is stored as a 98-byte word, a logical group consisting of 98 consecutive EFM frames must be read, and their respective C&D bytes must be catenated and decoded, before the program track identification and time position information that pertains to the entire block of 98 EFM frames can be obtained.) The C&D byte is put at the start (0th byte) of an EFM frame in real time; its placement completes the construction of the EFM frame - it is assigned just before the EFM frame enters the EFM encoder. Four distinct blocks of data are referred to: 24-byte User Input Data Blocks; 28-byte C2 words; 32-byte C1 words; and 33-byte EFM frames.

Howe, Dennis G.↗
NASA NTRS2008

Scheme for Quantum Computing Immune to Decoherence

A constructive scheme has been devised to enable mapping of any quantum computation into a spintronic circuit in which the computation is encoded in a basis that is, in principle, immune to quantum decoherence. The scheme is implemented by an algorithm that utilizes multiple physical spins to encode each logical bit in such a way that collective errors affecting all the physical spins do not disturb the logical bit. The scheme is expected to be of use to experimenters working on spintronic implementations of quantum logic. Spintronic computing devices use quantum-mechanical spins (typically, electron spins) to encode logical bits. Bits thus encoded (denoted qubits) are potentially susceptible to errors caused by noise and decoherence. The traditional model of quantum computation is based partly on the assumption that each qubit is implemented by use of a single two-state quantum system, such as an electron or other spin-1.2 particle. It can be surprisingly difficult to achieve certain gate operations . most notably, those of arbitrary 1-qubit gates . in spintronic hardware according to this model. However, ironically, certain 2-qubit interactions (in particular, spin-spin exchange interactions) can be achieved relatively easily in spintronic hardware. Therefore, it would be fortunate if it were possible to implement any 1-qubit gate by use of a spin-spin exchange interaction. While such a direct representation is not possible, it is possible to achieve an arbitrary 1-qubit gate indirectly by means of a sequence of four spin-spin exchange interactions, which could be implemented by use of four exchange gates. Accordingly, the present scheme provides for mapping any 1-qubit gate in the logical basis into an equivalent sequence of at most four spin-spin exchange interactions in the physical (encoded) basis. The complexity of the mathematical derivation of the scheme from basic quantum principles precludes a description within this article; it must suffice to report that the derivation provides explicit constructions for finding the exchange couplings in the physical basis needed to implement any arbitrary 1-qubit gate. These constructions lead to spintronic encodings of quantum logic that are more efficient than those of a previously published scheme that utilizes a universal but fixed set of gates.

Williams, Colin↗
NASA NTRS2005

Improved Compression of Wavelet-Transformed Images

A recently developed data-compression method is an adaptive technique for coding quantized wavelet-transformed data, nominally as part of a complete image-data compressor. Unlike some other approaches, this method admits a simple implementation and does not rely on the use of large code tables. A common data compression approach, particularly for images, is to perform a wavelet transform on the input data, and then losslessly compress a quantized version of the wavelet-transformed data. Under this compression approach, it is common for the quantized data to include long sequences, or runs, of zeros. The new coding method uses prefixfree codes for the nonnegative integers as part of an adaptive algorithm for compressing the quantized wavelet-transformed data by run-length coding. In the form of run-length coding used here, the data sequence to be encoded is parsed into strings consisting of some number (possibly 0) of zeros, followed by a nonzero value. The nonzero value and the length of the run of zeros are encoded. For a data stream that contains a sufficiently high frequency of zeros, this method is known to be more effective than using a single variable length code to encode each symbol. The specific prefix-free codes used are from two classes of variable-length codes: a class known as Golomb codes, and a class known as exponential-Golomb codes. The codes within each class are indexed by a single integer parameter. The present method uses exponential-Golomb codes for the lengths of the runs of zeros, and Golomb codes for the nonzero values. The code parameters within each code class are determined adaptively on the fly as compression proceeds, on the basis of statistics from previously encoded values. In particular, a simple adaptive method has been devised to select the parameter identifying the particular exponential-Golomb code to use. The method tracks the average number of bits used to encode recent runlengths, and takes the difference between this average length and the code parameter. When this difference falls outside a fixed range, the code parameter is updated (increased or decreased). The Golomb code parameter is selected based on the average magnitude of recently encoded nonzero samples. The coding method requires no floating- point operations, and more readily adapts to local statistics than other methods. The method can also accommodate arbitrarily large input values and arbitrarily long runs of zeros. In practice, this means that changes in the dynamic range or size of the input data set would not require a change to the compressor. The algorithm has been tested in computational experiments on test images. A comparison with a previously developed algorithm that uses large code tables (generated via Huffman coding on training data) suggests that the data-compression effectiveness of the present algorithm is comparable to the best performance achievable by the previously developed algorithm.

Kiely, Aaron↗
NASA NTRS2004

Serial-Turbo-Trellis-Coded Modulation with Rate-1 Inner Code

Serially concatenated turbo codes have been proposed to satisfy requirements for low bit- and word-error rates and for low (in comparison with related previous codes) complexity of coding and decoding algorithms and thus low complexity of coding and decoding circuitry. These codes are applicable to such high-level modulations as octonary phase-shift keying (8PSK) and 16-state quadrature amplitude modulation (16QAM); the signal product obtained by applying one of these codes to one of these modulations is denoted, generally, as serially concatenated trellis-coded modulation (SCTCM). These codes could be particularly beneficial for communication systems that must be designed and operated subject to limitations on bandwidth and power. Some background information is prerequisite to a meaningful summary of this development. Trellis-coded modulation (TCM) is now a well-established technique in digital communications. A turbo code combines binary component codes (which typically include trellis codes) with interleaving. A turbo code of the type that has been studied prior to this development is composed of parallel concatenated convolutional codes (PCCCs) implemented by two or more constituent systematic encoders joined through one or more interleavers. The input information bits feed the first encoder and, after having been scrambled by the interleaver, enter the second encoder. A code word of a parallel concatenated code consists of the input bits to the first encoder followed by the parity check bits of both encoders. The suboptimal iterative decoding structure for such a code is modular, and consists of a set of concatenated decoding modules one for each constituent code connected through an interleaver identical to the one in the encoder side. Each decoder performs weighted soft decoding of the input sequence. PCCCs yield very large coding gains at the cost of a reduction in the data rate and/or an increase in bandwidth.

Divsalar, Dariush↗
NASA NTRS2012

System and method for calibrating a rotary absolute position sensor

A system includes a rotary device, a rotary absolute position (RAP) sensor generating encoded pairs of voltage signals describing positional data of the rotary device, a host machine, and an algorithm. The algorithm calculates calibration parameters usable to determine an absolute position of the rotary device using the encoded pairs, and is adapted for linearly-mapping an ellipse defined by the encoded pairs to thereby calculate the calibration parameters. A method of calibrating the RAP sensor includes measuring the rotary position as encoded pairs of voltage signals, linearly-mapping an ellipse defined by the encoded pairs to thereby calculate the calibration parameters, and calculating an absolute position of the rotary device using the calibration parameters. The calibration parameters include a positive definite matrix (A) and a center point (q) of the ellipse. The voltage signals may include an encoded sine and cosine of a rotary angle of the rotary device.

Davis, Donald R.↗