Engineering Papers⌕ Search

SEARCH · Engineering Papers

Results for “Hamming distance”

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 19 records
All sourcesNASA NTRSDOE OSTI
NASA NTRS2009

LDPC Codes with Minimum Distance Proportional to Block Size

Low-density parity-check (LDPC) codes characterized by minimum Hamming distances proportional to block sizes have been demonstrated. Like the codes mentioned in the immediately preceding article, the present codes are error-correcting codes suitable for use in a variety of wireless data-communication systems that include noisy channels. The previously mentioned codes have low decoding thresholds and reasonably low error floors. However, the minimum Hamming distances of those codes do not grow linearly with code-block sizes. Codes that have this minimum-distance property exhibit very low error floors. Examples of such codes include regular LDPC codes with variable degrees of at least 3. Unfortunately, the decoding thresholds of regular LDPC codes are high. Hence, there is a need for LDPC codes characterized by both low decoding thresholds and, in order to obtain acceptably low error floors, minimum Hamming distances that are proportional to code-block sizes. The present codes were developed to satisfy this need. The minimum Hamming distances of the present codes have been shown, through consideration of ensemble-average weight enumerators, to be proportional to code block sizes. As in the cases of irregular ensembles, the properties of these codes are sensitive to the proportion of degree-2 variable nodes. A code having too few such nodes tends to have an iterative decoding threshold that is far from the capacity threshold. A code having too many such nodes tends not to exhibit a minimum distance that is proportional to block size. Results of computational simulations have shown that the decoding thresholds of codes of the present type are lower than those of regular LDPC codes. Included in the simulations were a few examples from a family of codes characterized by rates ranging from low to high and by thresholds that adhere closely to their respective channel capacity thresholds; the simulation results from these examples showed that the codes in question have low error floors as well as low decoding thresholds. As an example, the illustration shows the protograph (which represents the blueprint for overall construction) of one proposed code family for code rates greater than or equal to 1.2. Any size LDPC code can be obtained by copying the protograph structure N times, then permuting the edges. The illustration also provides Field Programmable Gate Array (FPGA) hardware performance simulations for this code family. In addition, the illustration provides minimum signal-to-noise ratios (Eb/No) in decibels (decoding thresholds) to achieve zero error rates as the code block size goes to infinity for various code rates. In comparison with the codes mentioned in the preceding article, these codes have slightly higher decoding thresholds.

Divsalar, Dariush↗
NASA NTRS1989

Associative memory - An optimum binary neuron representation

Convergence mechanism of vectors in the Hopfield's neural network is studied in terms of both weights (i.e., inner products) and Hamming distance. It is shown that Hamming distance should not always be used in determining the convergence of vectors. Instead, weights (which in turn depend on the neuron representation) are found to play a more dominant role in the convergence mechanism. Consequently, a new binary neuron representation for associative memory is proposed. With the new neuron representation, the associative memory responds unambiguously to the partial input in retrieving the stored information.

Awwal, A. A.↗
NASA NTRS1989

Machine parts recognition using a trinary associative memory

The convergence mechanism of vectors in Hopfield's neural network in relation to recognition of partially known patterns is studied in terms of both inner products and Hamming distance. It has been shown that Hamming distance should not always be used in determining the convergence of vectors. Instead, inner product weighting coefficients play a more dominant role in certain data representations for determining the convergence mechanism. A trinary neuron representation for associative memory is found to be more effective for associative recall. Applications of the trinary associative memory to reconstruct machine part images that are partially missing are demonstrated by means of computer simulation as examples of the usefulness of this approach.

Awwal, Abdul Ahad S.↗
NASA NTRS2017

Analog Correlator Based on One Bit Digital Correlator

A two input time domain correlator may perform analog correlation. In order to achieve high throughput rates with reduced or minimal computational overhead, the input data streams may be hard limited through adaptive thresholding to yield two binary bit streams. Correlation may be achieved through the use of a Hamming distance calculation, where the distance between the two bit streams approximates the time delay that separates them. The resulting Hamming distance approximates the correlation time delay with high accuracy.

Prokop, Norman↗
NASA NTRS1989

Auto- and hetero-associative memory using a 2-D optical logic gate

An optical associative memory system suitable for both auto- and hetero-associative recall is demonstrated. This system utilizes Hamming distance as the similarity measure between a binary input and a memory image with the aid of a two-dimensional optical EXCLUSIVE OR (XOR) gate and a parallel electronics comparator module. Based on the Hamming distance measurement, this optical associative memory performs a nearest neighbor search and the result is displayed in the output plane in real-time. This optical associative memory is fast and noniterative and produces no output spurious states as compared with that of the Hopfield neural network model.

Chao, Tien-Hsin↗
NASA NTRS1992

Auto and hetero-associative memory using a 2-D optical logic gate

An optical system for auto-associative and hetero-associative recall utilizing Hamming distance as the similarity measure between a binary input image vector V(sup k) and a binary image vector V(sup m) in a first memory array using an optical Exclusive-OR gate for multiplication of each of a plurality of different binary image vectors in memory by the input image vector. After integrating the light of each product V(sup k) x V(sup m), a shortest Hamming distance detection electronics module determines which product has the lowest light intensity and emits a signal that activates a light emitting diode to illuminate a corresponding image vector in a second memory array for display. That corresponding image vector is identical to the memory image vector V(sup m) in the first memory array for auto-associative recall or related to it, such as by name, for hetero-associative recall.

Chao, Tien-Hsin↗
DOE OSTI2024

Prompt Phrase Ordering Using Large Language Models in HPC: Evaluating Prompt Sensitivity

Large language models (LLMs) have demonstrated effective performance in domain-specific tasks, often requiring a well-designed prompt to guide their responses. However, optimizing the right prompt is challenging due to prompt sensitivity—the phenomenon where small changes in the prompt can lead to significant variations in performance. In this study, we evaluate prompt performance by examining all permutations of independent phrases to investigate prompt sensitivity and robustness. We used two datasets: the GSM8k dataset, which assesses mathematical reasoning, and a custom template prompt for summarizing database metadata. Our goal was to evaluate the performance across all permutations of a sequence of prompt phrases. The study was conducted using the llama3-instruct- 7B model hosted on Ollama, with computations parallelized in a high-performance computing environment. By comparing the average index of phrases in the best and worst-performing prompts, we found that the order of independent phrases within a prompt significantly impacts LLM performance. Additionally, we used Hamming distance to assess changes between phrase orderings, concluding that prompt modifications can dramatically affect scores, often by almost random chance. These findings support existing research on prompt sensitivity. We discuss the challenges of prompt optimization, noting that altering phrases in a successful prompt does not always result in another successful prompt.

97 MATHEMATICS AND COMPUTING↗
NASA NTRS1973

Algebraic decoding of block codes over a q-ary input, Q-ary output channel, Q greater than q.

Decoding algorithms designed for one output alphabet are shown to be effectively usable for channels with a different output alphabet. The described technique that makes this possible can be used in conjunction with an arbitrary distance measure between input and output vectors. Thus, Hamming distance, Lee distance, or a burst distance can be assumed. Examples are presented for each of these distances.

Wainberg, S.↗
NASA NTRS1990

Performance comparison of combined ECC/RLL codes

In this paper, we present a performance comparison of several combined error correcting/run-lenth limited (ECC/RLL) codes created by concatenating a convolutional code with a run-length limited code. In each case, encoding and decoding are accomplished using a single trellis based on the combined code. Half of the codes under investigation use conventionally (d,k) run-length limited codes, where d is the minimum and k is the maximum allowable run of 0's between 1's. The other half of the combined codes use a special class of (d,k) codes known as distance preserving codes. These codes have the property that pairwise Hamming distances out of the (d,k) encoder are at least as large as the corresponding distances into the encoder (i.e., the codes preserve distance). Thus a combined code, created using a convolutional code concatenated with a distance preserving (d,k) code, will have a free distance (dfree) no smaller than the free distance of the original convolutional code. It should be noted that this does not hold if the (d,k) code was not distance preserving. A computer simulation is used to compare the performance of these two types of codes over the binary symmetric channel for various (d,k) constraints, rates, free distances, and numbers of states. Of particular interest for magnetic recording applications are codes with run-length constraints (1,3), (1,7), and (2,7).

French, C.↗
NASA NTRS1985

Codes with Parity Conditions on Subsets of Coordinates

Binary codes with the constraint that the codes restricted to certain subsets of columns must be contained in particular codes of the shorter lengths are considered. In particular, codes of even length 2k, and of minimum distance approximately greater than d, where in the code obtained by restricting to the first k positions has even weight and at the same time the code obtained by restricting to the last k positions also has even weight are considered. If k = 2n, n odd, and d = 2n, it is proved that the code has at most 8n - 4 codewords, and 8n - 4 is attainable for n = 3. This permits a file-transfer protocol control function assignment for personal computers to be chosen for 20 control functions using essentially just pairs of upper-case alphabetic ASCII characters where the Hamming distance between the binary forms of every two different control functions is at least six.

Posner, E. C.↗
NASA NTRS1989

Bandwidth efficient coding for fading channels - Code construction and performance analysis

The authors apply a general method of bounding the event error probability of trellis-coded modulation schemes to fading channels and use the effective length and the minimum-squared-product distance to replace the minimum-free-squared-Euclidean distance as code design parameters for Rayleigh and Rician fading channels with a substantial multipath component. They present 8-PSK trellis codes specifically constructed for fading channels that outperform equivalent codes designed for the additive white Gaussian noise channel when v is greater than or equal to 5. For quasiregular trellis codes there exists an efficient algorithm for evaluating event error probability, and numerical results on Pe which demonstrate the importance of the effective length as a code design parameter for fading channels with or without side information have been obtained. This is consistent with the case for binary signaling, where the Hamming distance remains the best code design parameter for fading channels. The authors show that the use of Reed-Solomon block codes with expanded signal sets becomes interesting only for large values of E(s)/N(0), where they begin to outperform trellis codes.

Schlegel, Christian↗
DOE OSTI2026

Extreme Temperature Cryptography Based On Nitrogen-Incorporated Ultrananocrystalline Diamond

Physical entropy sources that remain stable under extreme temperatures are essential for cryptography in emerging technological frontiers in deep space exploration, geothermal energy harvesting, and nuclear energy. However, conventional semiconductor platforms fail to generate stable and reliable cryptographic keys above 200 degrees C due to performance degradation. Here, we report a diamond-based cryptographic primitive that exploits the defect-rich sp 2 -bonded grain boundary network in nitrogen-incorporated ultrananocrystalline diamond (n-UNCD) film as a robust entropy source to generate cryptographic keys that remain operationally stable even after enduring extreme temperatures of 700 degrees C for 54 h while also surviving thermal cycling between room temperature and 700 degrees C for 48 h. The strength of the generated keys is assessed through several cryptographic metrics such as bit uniformity, entropy, hamming distances, and correlation coefficients, all of which are found to be near their respective ideal values. Moreover, the generated keys pass the NIST SP 800 and SP 800-90B tests and are also resilient to supply bias variations and a regression-based machine learning attack model based on the Fourier series. The robustness of the keys is attributed to the better thermal stability and chemical inertness of the n-UNCD film. This is supported by high-resolution energy-dispersive X-ray spectroscopy (EDS), which shows no significant lateral diffusion of metal atoms into the n-UNCD layer, and by Raman spectroscopy, which reveals no significant changes in the bonding configuration of the n-UNCD structure. Our findings highlight the remarkable potential of n-UNCD film for extreme environment cryptography by expanding the operational limits of conventional hardware security platforms.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗
DOE OSTI2025

Q-Cluster: Quantum Error Mitigation Through Noise-Aware Unsupervised Learning

Quantum error mitigation (QEM) is critical in reducing the impact of noise in the pre-fault-tolerant era, and is expected to complement error correction in fault-tolerant quantum computing (FTQC). In this work, we propose a novel QEM approach, Q-Cluster, that uses unsupervised learning (clustering) to reshape the measured bit-string distribution. Our approach starts with a simplified bit-flip noise model. It first performs clustering on noisy measurement results, i.e., bit-strings, based on the Hamming distance. The centroid of each cluster is calculated using a qubit-wise majority vote. Next, the noisy distribution is adjusted with the clustering outcomes and the bitflip error rates using Bayesian inference. Our simulation results show that Q-Cluster can mitigate high noise rates (up to 40% per qubit) with the simple bit-flip noise model. However, real quantum computers do not fit such a simple noise model. To address the problem, we (a) apply Pauli twirling to tailor the complex noise channels to Pauli errors, and (b) employ a machine learning model, ExtraTrees regressor, to estimate an effective bit-flip error rate using a feature vector consisting of machine calibration data (gate & measurement error rates), circuit features (number of qubits, numbers of different types of gates, etc.) and the shape of the noisy distribution (entropy). Our experimental results show that our proposed Q-Cluster scheme improves the fidelity by a factor of 1.46x, on average, compared to the unmitigated output distribution, for a set of low-entropy benchmarks on five different IBM quantum machines. Our approach outperforms the state-of-art QEM approaches RZNE [28], M3 [24], Hammer [35], and QBEEP [33] by 1.26x,1.29x,1.47x, and 2.65 x, respectively.

42 ENGINEERING↗
NASA NTRS1972

Error-erasure decoding of product codes.

Two error-erasure decoding algorithms for product codes that correct all the error-erasure patterns guaranteed correctable by the minimum Hamming distance of the product code are given. The first algorithm works when at least one of the component codes is majority-logic decodable. The second algorithm works for any product code. Both algorithms use the decoders of the component codes.

Wainberg, S.↗
NASA NTRS1974

Performance analysis of a frame sync algorithm for uncoded PSK telemetry

The optimum procedure for locating a frame sync word periodically inserted in uncoded binary data received over a binary symmetric channel is based on the Hamming distance metric. In this paper, a practical frame sync acquisition and maintenance algorithm is described, and its performance is analyzed. Specifically, with respect to this algorithm, an upper bound on the probability of false sync acquisition, the mean time to sync acquisition, and the subsequent mean time to loss of sync are computed for arbitrary bit error rates, frame lengths, sync word lengths, and algorithm parameters.

Levitt, B. K.↗
NASA NTRS1987

The capacity of the Hopfield associative memory

Techniques from coding theory are applied to study rigorously the capacity of the Hopfield associative memory. Such a memory stores n-tuple of + or - 1s. The components change depending on a hard-limited version of linear functions of all other components. With symmetric connections between components, a stable state is ultimately reached. By building up the connection matrix as a sum-of-outer products of m fundamental memories, it may be possible to recover a certain one of the m memories by using an initial n-tuple probe vector less than a Hamming distance n/2 away from the fundamental memory. If m fundamental memories are chosen at random, the maximum asymptotic value of m in order that most of the m original memories are exactly recoverable is n/(2 log n). With the added restriction that every one of the m fundamental memories be recoverable exactly, m can be no more than n/(4 log n) asymptotically as n approaches infinity. Extensions are also considered, in particular to capacity under quantization of the outer-product connection matrix. This quantized memory-capacity problem is closely related to the capacity of the quantized Gaussian channel.

Mceliece, Robert J.↗
NASA NTRS1988

Sparse distributed memory prototype: Principles of operation

Sparse distributed memory is a generalized random access memory (RAM) for long binary words. Such words can be written into and read from the memory, and they can be used to address the memory. The main attribute of the memory is sensitivity to similarity, meaning that a word can be read back not only by giving the original right address but also by giving one close to it as measured by the Hamming distance between addresses. Large memories of this kind are expected to have wide use in speech and scene analysis, in signal detection and verification, and in adaptive control of automated equipment. The memory can be realized as a simple, massively parallel computer. Digital technology has reached a point where building large memories is becoming practical. The research is aimed at resolving major design issues that have to be faced in building the memories. The design of a prototype memory with 256-bit addresses and from 8K to 128K locations for 256-bit words is described. A key aspect of the design is extensive use of dynamic RAM and other standard components.

Flynn, Michael J.↗